Sample Complexity Bounds for Score-Matching: Causal Discovery and Generative Modeling

Summary

This work focus on theoretical analysis on two main score-based approaches. The first one is the score-based casual discovery, where the authors give the sample complexity error bounds for score matching using ReLU NNs as well as an upper bound of the error rate. The second one is the score-based generative modeling, where the authors give a sample complexity bound for the score estimation.

Strengths

This work has strong theoretical results and has provided sufficient backgrounds for the readers to understand the theoretical problems and include a comprehensive discussion on related work.

Weaknesses

- It is unclear why the analysis on score-based casual discovery and that on score-based generative modeling are put together in this work; it seems to me they are unrelated work. The authors might want to put some insights on the relationship between these two work, for example, some shared techniques for proving the sample complexity bounds. - The definition of covering number should be included to make this work more self-contained. - For Assumption 2, since this is an original assumption proposed by this work, the authors should give more justification to how much this assumption holds in practice. An specific example, even a simple one, showing when this assumption holds, would make this work more convincing. - To provide some proof sketch might make this work more convincing and help reader better understand what are the technical contributions of this work. Now it is unclear to me why it provides better analysis than the previous work; specifically, why it does not rely on the assumption of low-dimensional data while the previous work Chen et al. [2023a] does.

Questions

- It seems that the theoretical results of score-based casual discovery are highly specific to the algorithm in Rolland et al. [2022]. I wonder how these results generalize to other related approaches? - Does Lemma 1 play a role in the later analysis? I wonder why we need Lemma 1. - The assumption in Line 148-149 is not properly justified. - Can the authors provide a specific case on when Assumption 2 holds and analysis on how practical this assumption? - As mentioned above, why this work does not rely on the assumption of low-dimensional data while the previous work Chen et al. [2023a] does? Minor issue: - It seems that the case l = 1 in Equation (3) can be merged into the case 2<=l<=L-1. - Line 107: donate -> denotes - The property mentioned in Line 108 seems unrelated to the Definition 1.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes.

Summary

The paper provides sample complexity bounds on score function estimation when (1) the score function is estimated by using SGD to minimize a denoising score matching objective, (2) the probability distribution is induced by a structural causal model (SCM) with additive Gaussian noise, and (3) the score function is Lipschitz, and (4) for each mechanism $f_i$ in the SCM, the expected value of the second derivative of $f_i$ with respect to each parent of $X_i$ is lower-bounded by $C_m$ times $\sigma_i$, the variance of the exogenous noise of $X_i$. They show that, under these conditions, the estimated score function converges at a parametric rate (Theorem 1). Using this bound, they give a sample complexity bound for the event that the SCORE algorithm for causal order search returns a correct topological order (Theorem 2). Finally, they also use the bound from Theorem 1 to provide a sample complexity result for the score-matching objective used in those works.

Strengths

### Significance The paper appears to be a significant theoretical contribution addressing the sample complexity of score function estimation, which as an important topic for both causal structure learning and score-based generative modeling. ### Clarity The paper is written in a fairly clear style. Relevant notations are appropriately defined and summarized in the Appendix. For each theorem, there are accompanying remarks which clearly discuss the implications of the theorem. The motivation and the context for the work are easy to understand.

Weaknesses

### Experimental Results This is clearly a theory paper, and contributes enough theory such that there is no need for an extended section on experiments. In fact, given the space constraints, extensive experiments would most likely hurt the paper. However, a small set of experiments - e.g. corroborating Theorem 1 by plotting the loss function versus the number of samples - would take the paper from a good contribution to a great one (8 instead of 7). In my experience, experimental validation of theoretical results on sample complexity can be fairly difficult to obtain, and thus papers like this one would be a lot more useful in practice if they ran some carefully-chosen experiments.

Questions

### Details 1. The theorems (eg. Theorem 1 and Theorem 3) refer to a DNN trained by SGD. However, this is missing a condition on the learning rate. What is the condition on the learning rate? 2. Presumably the usage of "SGD" in the theorems here implies that batch size = 1. Do the results extend to larger batch sizes? For clarity, I think it would be helpful to encapsulate the assumptions on the architecture and training into an Assumption environment. 3. What is $\tau$, the first argument to the covering number in line 203? Where is it defined? ### Suggestions 1. Since this paper sits at the intersection of score-based generative modeling (SGM) and causal structure learning (CSL), it is important to keep the background of both audiences in mind. In particular, coming from causal structure learning / statistics, I am surprised by Theorem 1, which seems to require that SGD finds a solution close to the global optimum. It looks like Theorem 1 uses some relatively recent results / techniques (e.g. Nguyen et al., 2021), which might be well-known in the SGM community but are not well-known in the CSL community. This paper provides a good opportunity to bring the advances of SGM to the CSL audience, and it would be valuable to provide more intuition about the techniques used here. 2. Please reference all appendices in the paper. Appendices B, C, F, and G are not referenced in the paper. 3. I think Lemma 2 would be more clear if you left out the node $i$ altogether. Since the associated term is zero anyways, it just gets in the way and serves no purpose in the left-hand side of the implication statement. It feels like the point that the variance term associated to $i$ is zero shouldn't be part of this theorem, but a separate observation.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors have adequately addressed the limitations of their work.

Summary

This study aims to investigate the sample complexity associated with score-matching and its applications in the field of causal discovery, providing valuable theoretical bounds. The authors present theoretical evidence that training a conventional deep ReLU neural network using stochastic gradient descent enables the accurate estimation of the score function. Additionally, they establish rigorous bounds on the error rate pertaining to the recovery of causal relationships, employing the score-matching-based methodology introduced by Rolland et al. [2022], under the assumption of an adequately precise estimation of the score function. Furthermore, an analysis is performed to determine the upper bound of score-matching estimation within the framework of score-based generative modeling, which not only bears relevance to causal discovery but also demonstrates independent significance within the wider domain of generative models.

Strengths

There are several main strengths in this paper. First, the authors extensively explored the relevant recent theories, including background research. Second, the error bounds are rigorously derived from well-known assumptions (1 and 3) and novel assumption (2) for causal discovery. Third, the use of this theory seems to have potential in multiple applications relating to causal discovery and SGM given that the architecture is general enough.

Weaknesses

There are some weaknesses in this paper. First, the background section is a bit too long compared to the main body (almost 5 pages with added related work in Section 5) resulting in only 2.5 pages new materials (excluding conclusion). Although it was advantageous to extensively explain the background (where there are multiple topics in this paper), it became a weakness due to its excessive length. The second weakness is about deep ReLU neural networks, but there is no empirical experiments to corroborate theory. For example, one might show causal discovery errors and how the bounds in Theorem 2 are ‘good’ enough. If the bounds are too loose, the usefulness of the bounds will become low. (or how robust the result would be under the violation of the some of assumptions) Given that there are some space that can be saved by removing (or moving) some of related work/preliminaries from main text, I recommend the authors to have some proof-of-concept experiments demonstrating the effectiveness of such theoretical bounds.

Questions

Not a question but there are issues with \begin{align} or other tex related comments. If you have an empty line in between text and mathematical formula, there will be a gap. You can see Eq 1 (and the one before and one next), 4, 5, 6, 7, (one next to 7), 8, next to 8, in Assumption 2, in Theorem 1, in Thm 2, in Thm 3. You can effectively save lots of space. There are many remarks. But I guess they can be incorporated more smoothly just as a text with proper rephrasing (if needed). 98th line contains a typo with missing parentheses in the equation. Theorem 3, Remark 1. Can you elaborate in the main text what enable your theorem applicable to high-dimensional data versus. Chen 2023a's results on low dimensional data?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Assumptions can be restrictive but the authors are well-understanding such restrictions and others also made similar assumptions. For the assumption 2, it is unclear how one can assume C_m properly.

Summary

This paper presents error bounds (sample complexity and convergence rates) for the problems of score based generative modelling and score-order based causal discovery. It is primarily a theory paper, and one of the first few works to present error bounds for a causal discovery algorithm that is not conditional independence based.

Strengths

(+) In score-function based causal discovery (which does not use conditional independence testing), there are no notable error bounds. So this work addresses the gap. Although it is tied to the order based method of Rolland et al, it is interesting as this might lead to more such work for other methods in causal discovery. Theoretical guarantees are important for causal discovery as real world validation is harder due to lack of ground truth. (+) The assumptions and technicalities are fairly well laid out. Although the score requires Lipschitz assumptions, thereby limiting the class of mechanisms, it is still relevant as it still might cover fairly large class of real world settings. (+) The theoretical analysis for score based generative modelling seems similar to what has been done for causal discovery, and is potentially interesting. However, I am unsure about its relevance wrt that field as I am not totally familiar with it.

Weaknesses

(-) My main concern with this work is that it might be a bit too broad in scope. It is definitely okay and also welcome to have a broader scope (causal discovery plus score based generative modelling), but I don't think the current writing/presentation justifies it appropriately. I think a better way to present the results would have been to present the main result a bit more generally and clearly, and explain that result in the context of both causal discovery and score based generative modelling. I would have been happy to see just the causal discovery part alone as it merits quite a bit of discussion (since it is the first work doing so). (-) There are no experiments. Although it is primarily a theory paper, some simple empirical analysis of RELU deep networks for score function in causal discovery would have been very illustrative and relevant. It would have been good to see how the bounds when the assumptions are satisfied and how do they get worse if the assumptions are not satisfied.

Questions

My main question is : Is there a common theoretical part (proof techniques and statements) that can be generalised to both settings? If so, I think it might be good to highlight it. If not, I feel the paper might benefit from studying these two problems separately.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The assumptions are fairly well laid out. A major limitation now is that there is no empirical analysis.

Summary

This paper provides detailed theoretical results for causal discovery and score-based generative modeling. For causal discovery, it first provides a sample complexity analysis for the estimation of the score function for nonlinear additive Gaussian noise models, then it proves that the error rate of a score-matching-based method, SCORE, converges linearly w.r.t the number of training data. For score-based generative modeling, it presents sample complexity bounds for the estimation of the score function in the ScoreSDE.

Strengths

1. This paper provides sound and detailed theoretical results for score matching in the context of both causal discovery and score-based generative modeling. In both cases, the theoretical analyses hold with mild assumptions compared to previous work. 2. This paper well organized overall. It provides a detailed discussion about preliminaries in Section 2, provides theoretical results for causal discovery and score-based generative modeling in Section 3 and Section 4 respectively. Although there are many symbols, I think this paper is relatively easy to follow. 3. This paper points out limitations of the current theoretical results clearly in Section 6.

Weaknesses

1. As demonstrated in Section 6 of this paper, the theoretical results are still not general enough due to some relatively strong assumptions. 2. I suggest the authors change the title "Error Bounds for Score Matching Causal Discovery" because almost half of this paper is about score matching in score-based generative modeling, which has little to do with causal discovery. 3. Although I have no doubt about the soundness of the provided theoretical results, the contribution of this paper is somewhat limited. This paper does not design more advanced algorithm, it only provides sample complexity bounds for existing algorithms under PAC framework. I'm not sure whether it should be regarded as a supplement for previous work or an independent research. However, considering that ScoreSDE and is widely used in respective field, I still recommond "weak accept" for this paper.

Questions

N/A

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

See weakness.

Response to rebuttal

Thank the authors for their work, I think the title "Sample Complexity Bounds for Score-Matching: Causal Discovery and Generative Modeling" is better than the original one. Besides, although I appreciate the theoretical contributions of this work, IMHO, the overall contributions may be somewhat insufficient, because it only derives sample complexity under the widely-used PAC framework. After rebuttal, I decide to maintain my score.