Sample Complexity Bounds for Score-Matching: Causal Discovery and Generative Modeling
Authors: Zhenyu Zhu
Francesco Locatello
Volkan Cevher
Venue: NeurIPS 2023 poster (2023)
Keywords: Causal discovery
Score matching
Score-based generative modeling

Abstract: This paper provides statistical sample complexity bounds for score-matching and its applications in causal discovery. We demonstrate that accurate estimation of the score function is achievable by training a standard deep ReLU neural network using stochastic gradient descent. We establish bounds on the error rate of recovering causal relationships using the score-matching-based causal discovery method of Rolland et al. [2022], assuming a sufficiently good estimation of the score function. Finally, we analyze the upper bound of score-matching estimation within the score-based generative modeling, which has been applied for causal discovery but is also of independent interest within the domain of generative models.

Sample Complexity Bounds for Score-Matching: Causal Discovery and Generative Modeling
Francesco Locatello', Volkan Cevher it École Polytechnique Fédérale de Lausanne Hzhenyu.zhh zhu, volkan. cew.ee)eepe11...... ch
Zhenyu Zhu",
Institute of Science and Technology Austria ffanncscco loctteeoosactttt ac at
Abstract
This paper provides statistical sample complexity bounds for score- woore-mathhing and its applications in causal díscovery. We demonstrate that accurate estimation of the score function achievable by training standard deep ReL.U neural network using stochastic gradient descent. We establish bounds on the error rate of recovering causal relationships using the poore-matching-bice Rolland et al. [2022). assuming sufficiently good estimation of the score function. Finally, we analyze the upper bound of score-matching estimation within the score- based generative modeling, which has been applied for causal discovery but is also independent interest within the domain of generative models.
causal discovery method
Introduction
Score matching Hyvärinen 2005]. an alternative to the maximum likelihood principle for unnormal- ized probability density models with intractable partition functions, has recently emerged as a new state-of-the-art the-art approach that leverages machine learning for scalable and accurate causal discovery from observational data Rolland et al. (002).. However, the theoretical analysis and guarantees the finite sample regime are underexplored for causal discovery even beyond score-matching approaches.
Contributions: In this work, we give the first sample complexity error bounds for score-matching using deep ReLU neural networks. With this, we obtain the first upper bound on the error rate of the method proposed by Rolland et al. [022 to learn the topological ordering of a causal model from observational data. Thanks to the wide applicability of matching in machine learning, also discuss applications to the setting of score-based generative modeling. Our main contributions are:
1. We provide the analysis of sample complexity bound for the problem of score function estimation in causal discovery for non-linear additive Gaussian noise models which has convergence rate of log n/n with respect to the number of data. Importantly, our results require only mild additional assumptions, namely that the non-linear relationships among the causal variables are bounded and that the score function is Lipschitz. To the best of our knowledge, this is the first work to provide sampling complexity bounds for this problem.
2. We provide the first analysis of the ttate-of-the-art topological ordering-based causal dis- covery method SCORE (Rolland et 2022 and provide correctness guarantee for the obtained topological order. Our results demonstrate that the algorithm's 's error rate converges linearly with respect to the number of training data. Additionally, we establish a connection between the algorithm's 's eтror rate and the average second derivative (curvature) of the non-linear relationships among the causal variables, discussing the impact of the causal model's inherent characteristics on the algorithm's 's error rate in identification.
Share the senior authorship
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

3. We present sample complexity bounds for the score function estimation problem in the standard score-based generative modeling method, ScoreSDE [Song et al. 202T]. In contrast to previous results [Chen et al., 2023a], our bounds do not rely on the assumption of low-dimensional input data, and we extend the applicability of the model from a specific encoder-decoder network architecture to general deep ReLU neural network.
High-level motivation and background: Causal discovery and causal inference refer to the process of inferring causation from data and reasoning about the effect of interventions. They are highly relevant in fields such as economics [Varian] 2016), biology [Sachs et al. 2005]. and healthcare [Sanchez et al. 2022]. In particular, some causal discovery methods aim to recover the causal structure of problem solely based on observational data.
The causal structure is typically represented as a directed acyclic graph (DAG), where each node is associated with random variable, and each edge represents a causal mechanism between two variables. Learning such model from data is known to be NP-hard [Chickering, 1996]. Traditional approaches involve testing for conditional independence between variables or optimizing goodness-of- fit measures to search the space of possible DAGs. However, these greedy combinatorial optimization methods are computationally expensive and difficult to extend high-dimensional settings.
An alternative approach is to reframe the combinatorial search problem as a topological ordering task [Tessseer and Koller, 2012 Solus et al,, 202T Wang et al. 202 Rolland et al. 2022 Montagna
et al. 2023b a [annchez et al.j 2023]. where nodes are ordered from leaf to root. This can significantly speed up the search process in the DAG space. Once topological ordering is found, feature selection
algorithm can be used to prune potential causal relations between variables, resulting in a DAG.
Recently, Rooland et al. 2022 proposed the SCORE algorithm, which utilizes the Jacobian of the score function to perform topological ordering. By identifying which elements of the Jacobian matrix of the score function remain constant across all data points, leaf nodes can be iteratively identified and removed. This approach provides a systematic way to obtain the topological ordering and infer the causal relations within the entire model. This method has achieved state-of-the-an results on multiple tasks Rolland et al. [2022) and has been extended to improve scalability Montagna et al. (023b also using diffusion models Sanchez et al. [2023] and to Gaussinn noise Montagna et al. 2023a Interestingly. these approaches separate the concerns of statistical estimation of the score function from the causal assumption used to infer the graph (e.g.. non-linear mechanisms and additive Gaussian noise). This opens an opportunity to study the convergence properties of these algorithms in the finite data regime, which is generally under-explored in the causal discovery literature. In fact, if we had error bounds on the score estimate without additional complications from causal considerations, could study their downstream effect when the score is used for causal discovery.
Unfortunately, this is far from trivial as the theoretical research on score matching lags behind its empirical success and progress would have far-reaching implications. Even beyond causal discovery, error bounds on the estimation of the score functions would be useful for score-basee generative modeling (SGM) [Song and Ermon 2019 Song et al. [021]. These have achieved state-of-the- the-art performance in various tasks, including image generation [hhariwal and Nichol, [02T] and audio synthesis (Kong et al. 202T]. There has been significant research investigating whether accurate score estimation implies that score-based generative modeling provably converges to the true data distribution in realistic settings [Chen et al. [2023b] Lee al., 2022 2023]. However, the error bound of score function estimation in the context of score-based generative modeling remains an unresolved issue due the non-convex training dynamics of neural network optimization.
Notations: We use the shorthand [r]] = 21, nu for a positive integer n. We denote by a(n) < b(n): there exists positive constant independent of such that a(n) < cb(n). The Gaussian distribution is ((,,o with the a mean and the o² variance. We follow the standard Machmannn-Landar notation in complexity theory e.g., O, o, Ω, and θ for order notation. Due to space constraints, a detailed notation is deferred to Apppendix A
2 Preliminaries
As this paper concerns topics in score matching estimation, diffusion models, neural network theory, and causal discovery, first introduce the background and problem setting of our work.

---

2.1 Score matching
For a probability density function p(æ:), we call the score function the gradient the log density with respect to the data a. To estimate the score function V log p(x), we can minimize the &g loss over the function space S.
min (())) V logr( #ES
å = arg min Epll [xx) V log p(x)))
#E$
The corresponding objective function to be minimized is the expected squared error between the true score function and the neural network:
[
[
a log p(x: dx
|
(s, p(x)) pp)))
s(z)
(I)
We refer to this formulation explicit score matching (ESM).
Denoising score matching (DSM) proposed by |Vineet [201 to convert the inference of the score function in ESM into the inference of the random noise and avoid the computing of the second derivative. For the sampled data æ, & is obtained by adding unit Gaussian noise a. i.e.
I E, NN I)). We can derive the conditional probability distribution and its score function:
| 21
2 log p(
p a:) (2r)d/2add exp(
20
Oa
Then the DSM is defined by:
1
log p( 2z)
1|1 p(
1
x
(s, p(x, 2)) B ())
s(
s(i)
2
da
2
σ²
Vincent [011] have proven that minimizing DSM is equivalent to minimizing ESM and does not depend on the particular form of p(t) or p(zz).
2.2 Neural network and function space
In this work, we consider standard depth-L width-m fully connected ReLU neural network. Formally, define DNN with the output (xx) each layer
1= 1-15L-1, 1= L,
sı(z)
ol 81-((())
(3)
(WL,8L-10z)
where the input x E Rd, the output is s2(x) E Rd, the weights of the neural networks are
W1 E Rmx W, E Rmxx / 2,..., --1 and WL E Rdxmm The neural network parameters formulate the tuple of weight matrices W == (W.)k E [Rmxdd (RmxmyL--2 x Rdxm) }. The S denotes the function space of Eq. (3)
The 6 max(0, x is the ReLU activation function. According to the property ((x) z06(x)) of ReLU, we have 8; D, Wis--1 where D, is diagonal matrix defined as below.
Definition 1 (Diagonal sign matrix). For I [L and k [m]) the diagonal sign matrix Di is defined as: (Di)a. = ((: 0}.
Initialization: We make the standard random Gaussian initialization [Wilay ~ No0,, 2) for e [L 11] and [Wiks ~ (O0, 4))
2.3 Causal discovery
In this paper, follow the setting in Rolland et al. 2022 and consider the following causal model, a random variable x E Rdd is generated by:
(
f((AA(()) + i [d]
(4)
3

---

where fi is a non-ling non-linear function, ~ (0, o and (a) represent the set of parents of xx() in a.
Then we can write the probability distribution function of as:
p
II p(r (x))
(5)
For such non-linear additive Gaussian noise models Fq.. (4) Rolland et 2022 provides Algorithm to learn the topological order by score matching follows:
Algorithm SCORE matching causal order search (Adapted from Algorithm in Rolland et al. 2022
Input: training data (()(()) 1. Initialize: π = [] nodes = (l,...,d) .d]
for L, . do Estimate the score function Snodes
V log Pnodes by deep ReLU network with SGD.
Estimate V,, Varzaat (w)
nodes larg miny Vi]
T + [1, π]
nodes 4- nodes - (7) Remove /-th element of a:
end for Get the final DAG by pruning the full DAG associated with the topological order и.
2.4
Score-based generative modeling (SGM)
In this section, we give brief overview of SGM following [Song al. [2021]. Chen al. [203bb
2.4.1
Score-based generative modeling with SDEs
Forward process: The success of previous score-based generative modeling methods relies on perturbing data using multiple noise scales, and the proposal of the diffusion model is to expand upon this concept by incorporating an infinite number of noise scales. This will result in the evolution of perturbed data distributions as the noise intensity increases, which will be modeled through stochastic differential equation (SDE).
dx, = f(z,, t)dt + gidw,
Po
(6)
The expression describes Ft, where the standard Wiener process (also known Brownian motion) is denoted as w, the drift coefficient of x; is represented by vector-valued function called f. and the diffusion coefficient of æ, denoted as gr. scalar function. this context, we will refer to the probability density of æ, as Pt. and the transition kernel from æ, to 2; as Par (=r( (x,), where (OU) process is Gaussian process that is both time-
S < T. The Monstin-UUhlenben homogeneous and Markov process. It is distinct in that its stationary distribution is equivalent to the standard Gaussian distribution 7d on IRd.
Reverse process: We can obtain samples of To ~ p by reversing the process starting from samples of æe pSDE An important finding is that the reversal of diffusion process is diffusion process as well. It operates in reverse time and described by the reverse-time SDE:
dæ;- { f((,,
of V log po:)) dt gidw.
When time is reversed from T to 0, w is a standard Wiener process with an infinitesimal negative timestep of dt. The reverse diffusion process be derived from [Eq. once the score of each marginal distribution, V log p. (x.), known for all t. By simulating the reverse diffusion process, we can obtain samples from SDE
order to simplify the writing of symbols and proofs, in this work we choose that f (Zt, = - and g(t)= = which has been widely employed in prior research [Chen al. 2023a De Bortoli et al.) 202T for theoretical analysis in Constenn-Ullenber process in based generative modeling.
Some special settings:

---

2.4.2 Score matching in diffusion model
We aim to minimize the equivalent objective for score matching:
min #ES 0
Ree (ze, ae)) ar log poi (ae, (20) - saa,, 1) dt.
The transition kernel has an analytical form Vay log (aoeeereelaa /20) and h(t) a(t)² = e
-0 (t)m where ax = e
k((()
The empirical score matching loss is:
1 Σ (x()))) # n2 i=1
min ((s)
(8)
where the loss function (z) s) is defined as:
())())) T- { (e: [[[V log log (B()) s(xr, 1)122) de.
1
Here we choose w()) = - and we define the expected loss L()) = Emm=po [f(-)].
and
Theoretical results for causal discovery
In this section, we state the main theoretical results of this work. We present the assumptions on non- linear additive Gaussian noise causal models in [Section 3.1 Then, we present the sample complexity bound for score matching in causal discovery in Sectioo 3.2 In Sectioon 3.3 we provide the upper bound on the error rate for causal discovery using the Algonithm The full proof' of Theorem and 2 are deferred to Appendix E and respectively.
3.1 Assumptions
Assumption (Lipschitz property of score function). The score function V logg(-) is 1-Lipschitz.
The Lipschitz property of the score function is standard assumption commonly used in the existing literature (Block et al. 2020 Lee et al. 2022 Chen al.) 2023b a). However, for causal discovery. this assumption limits the family of mechanisms that we can cover.
Remark:
Assumption 2 (Structural assumptions of causal model). Let p be the probability density function of a random variable x defined via non-linear additive Gaussian noise modelEq. (4) Then, Vi E [d] the non-linear function is bounded, [fal S C₁. And Vi,j E [d], if j is one of the parents of i, i.e. x(( + (.),, then there exist constant Cm that satisfy:
( (((A((())))
2 Cm.
Oxli2
Remark:
This novel assumption that we introduce. relating the average second derivative of mechanism (related to its curvature) to the noise variance of the child variable. This will play crucial
yet intuitive role in our error bound: identifiability is easier when there sufficient non-linearity of mechanism with respect to the noise of the child variable. Consider the example of quadratic mechanism, where the second derivative is the leading constant of the polynomial. this constant small (e.g., close to zero), the mechanism is almost linear and we may expect that the causal model should be harder to identify. Similarly, if the child variable has very large variance, one may expect it to be more difficult to distinguish cause from effect, as the causal effect of the parent is small compared to the noise of the child. According to Assumption we can derive the identified ability margin for leaf nodes and parent nodes.
Lemma If a non-linear additive Gaussian noise model Eg. (4) satisfies Assumption 2 Then, vi,j [d], we have:
i a leaf + Var [ds;(z) Or(1)
(2s((x) Ox(i)
0, j is not a leaf + Var
2 Cm-
5

---

This lemma intuitively relates our identifiability margin with the decision rule of SCORE al. 2022] to identify leaves. Non-leaf nodes should have the variance of their score Jacobian sufficienlly far from zero. As one may expect, we will see in Theorem 2 that the closer Cm is to zero, the more likely that the result of the algorithm will incorrect given finite samples.
3.2 Error bound for score matching in causal discovery
We are now ready state the main result of the score matching in causal discovery. We provide the sample complexity bounds of the explicit score matching Eg. (1) that using denoising score matching Eqq (2) in Algorithm for non non-linear additive Gaussian noise models [q. (4)
Theorem 1. Given DNN defined by Eq. (3) trained by SGD for minimizing empirical denoising score matching objective. Suppose Assumption I and 2 are satisfied. For any & E (0. 1) and 5 E (0, ifa; and C. ~, vi E d]. Then with probability at least 1 - 28 - 4 exp( 32
1 2L clp((-Q((m)) nd over the randomness of initialization W, noise e and C, it holds that:
d'd nd
.c(..
(()x() S
log
+ -
ns²
n
where the S) S) is the covering number of the function space S for deep ReLU neural network.
Remark:
1): To the best of our knowledge, our results present the first upper bound on the explicit sampling complexity of score matching for topological ordering Algorithm T]in non-linear additive Gaussian noise causal models. This novel contribution provides valuable insights into the efficiency and effectiveness of utilizing score matching for topological ordering in non-linear additive Gaussian noise causal models.
2): By choosing s² = 1 the bound is modified to JESM (())( S Vn
o oodllgnn log N.(1/n.S) This vn
expression demonstrates that the & estimation error converges at a rate of is significantly larger than the number of nodes d.
log n yπ
when the sample size
3): The bound is also related to the number of nodes d, the variance of the noise in denoising score matching and causal model o., the covering number of the function space No ( S), and the upper bound of the data Ca. If these quantities increase, it is expected that the error of explicit score matching will also increase. This is due to the increased difficulty in accurately estimating the score function.
4): Theorem is rooted in the generalization by sampling complexity bound. It is independent of the specific training algorithm used. The results are broadly applicable and can be seamlessly extended to encompass larger batch GD.
Next, will establish connection between score matching and the precise identification of the topological ordering.
3.3 Error bound for topological order in causal discovery
Based on the previously mentioned sample complexity bound of score matching, we establish an upper bound on the error rate of the topological ordering of the causal model obtained through Algorithm
Theorem 2. Given DNN defined by Eq. (3) traindd by SGD with step size 1) O( poly(n, 4)m log" m for minimizing empirical score matching objective. Then under Assumption 2 for m 2 poly(n, L), with probability at least:
nC2 d2
1 - ex - 1)=1)exx(--mmmm - 2n exp( 24L+5 (log m m) (m2 + dz)
over the randomness of initialization W and training data that Algorithm 1 can completely recover the correct topological order of the non-linear additive Gaussian noise model.
Remark:

---

1): The foundation of Theorem 2 rests upon Theorem 1 it can be seen as an embodiment of applying
the upper bound of score matching for causal discovery. To the best of our knowledge, our results provide the first upper bound on the enror rate of topological ordering in non-linear additive Gaussian noise causal models using Algorithh I]
2): Considering that when m ~ d and L R the probability degenerates to:
(-0( nC (logm)) m)2
O 2n exp
(log
The first term of the error arises due to the initialization of the neural network. As for the second term of the error, if the number of training data satisfies n
log 2 (log m)², then it will have that
I 1. This implies that the second term of the error probability exhibits linear 2n exp ( - (-O( (Tog mng
convergence towards 0 when n is sufficiently large. Therefore, when the sample size x the contribution of the second term to the full error becomes negligible.
log n 2 (log m)?
3): The theorem reveals that a smaller value of the constant Cm increases the probability of algorithm failure. This observation further confirms our previous statement that smaller average second derivative of the nonlinear function makes it more challenging to identify the causal relationship in the model. Additionally, when the causal relationship is linear, our theorem does not provide any guarantee for the performance of Algorithm
4): Consider the two variables case. If child node is almost deterministic function of its parents, the constant Cm can take on arbitrarily large values, according to AAssmptiin 2 Consequently, the
second term of the error probability, 2n exp (- [log m) )). tends zero. This implies that the errors in Algorithm Tare primarily caused by the random initialization of the neural network. The identifiability of this setting is consistent with classical results Daniušis al. [2010), Janzing et al. [2015). Intuitively, as long as the non-linearity is chosen independently of the noise of the parent variable the application of the non-linearity will increase the distance to the reference distribution of the parent variable (in our case Gaussian). Note that for the derivative in Assumption Assumption to be defined, the parent node cannot be fully deterministic.
nC2
5): Instead of focusing on the kernel regime, we directly cover the more general neural network training. The kernel approach of Rolland et al. [2022] is special case of our analysis. The basis of Theorem lies the proof of SGD/GD convergence of the neural network, These convergence outcomes also apply to BatchGDD, as demonstrated in [Tentzen and Kröger [22T)) Hence, Theorem 2 can naturally expanded to incorporate Batch GD as well.
Proof sketch:
The proof of Theorem 2 can be divided into three steps. The first and most important
step is to derive the upper bound of "att)" Here, we utilize the properties of deep ReLU neural networks to derive the distribution relationship between features of adjacent layers, then accumulate them and combine it with the properties of Gaussian initialization, yielding the upper bound for
(sr((r)
ds:(w). The second step is to use the upper bound of (x)) obtained in the first step combined with Oz(")
Oz((1)
the concentration inequality derive the upper bound of the error of Var (s,(a))) The third step is to compare the upper bound in the second step with Lemma I] to obtain the probability of successfully selecting leaf nodes in each step. After accumulation, we can obtain the probability that Mlggorllti ] can completely recover the correct topological order of the non-linear additive Gaussian noise model.
4 Theoretical results for score-based generative modeling (SGM)
In this section, we present the additional assumption required for the theoretical analysis of score matching in score-based generative modeling. Then, we provide the sample complexity bound associ- ated with score matching this framework. The full proof in this section is deferred to Appendix G
Assumption 3 (Bounded data). We assume that the input data satisfy |20|| S Ca x ~ Pu-
Remark: Bounded data is standard in deep learning theory and also commonly used in practice (Du
et al. 2019b a. Allen--huhh et al. 2019 Oymak and Soltanolkotabi 2020 Malach et al. 2020].
2 Daniušis et al. 2010 Janzing et al. 2015 have formalized independence of distribution and function via
information geometric orthogonality condition that refers to reference distribution (e.g.. Gaussian)
7

---

Theorem 3. Given a DNN defined Eq. (3 frained by fGr minimizing empirical denoising score
matching loss Eq. (8) Suppose Assumption and 3 are satisfied. For any E (0, 1) and i E (0. 1). Then with probabilit at least 26 2T. (mm) over the randomness of initialization W and noise in denoising score matching, holds:
1
[
1 ne²
( d( ((T(-oo((t))) +C3
N.
[Vlogpe()) - 8(., -
dt x
log
=+de²
T to 80
to
8
where the No S) is the covering number of the function space S for deep ReLU neural network.
Remark:
1): [Thoorem 3 and Theorem I |ttdyy similar problems between causal discovery and acore-based generative modeling and share similar techniques drawn from statistical learning theory and deep learning theory. These two domains are connected by a common theoretical foundation centered on the upper bound of score matching.
2): Our result extends the results for score matching in diffusion models presented in Chen et al. [2023a] which rested on the assumption of low-dimensional data structures, employing this to decompose the score function and engineer specialized network architectures for the derivation of the upper bound. Our work takes distinct route. Our conclusions are based on the general deep ReLU neural network instead of a specific encoder-decoder network and do not rely on the assumptions of low-dimensional data used in Chen et al.) [023a]] We harness the inherent traits and conventional techniques of standard deep ReLU networks to directly deduce the upper error bound. This broader scope allows for more comprehensive understanding of the implications and applicability of score-based generative modeling in a wider range of scenarios.
3): Similar to Theorem 1. by choosing
e²
we can obtain the best bound VA
T- S I (og - a(, 01 5
1 Vn
d(T
log(to) + C3 log Nc( This expression
T-to
demonstrates that the & estimation eтror converges at a rate of when the sample size n is significantly larger than the dimensionality d and time steps T.
4): The bound is also related the data dimension d, the variance of the noise in denoising score matching a, the covering number of the function space. No( and the upper bound of the data Ca- these quantities increase, it is expected that the error of explicit score matching will also increase. This is due to the increased difficulty in accurately estimating the score function.
5): When to O, the theorem lacks meaning. However, when >> to ~ 1. the bound simplifies to d+cī Not .S) This indicates that when T' is sufficiently large, the loss estimated by the score v log
function in the diffusion model becomes independent of time steps T'.
6): Similar to Theorem the result of Theorem is also broadly applicable and can be seamlessly extended to encompass larger batch GD.
5 Numerical evidence
We conducted a series of experiments to validate the theoretical findings presented in the paper. We took inspiration from the code provided iroollannd et al. [2022] and employed the structural Hamming distance (SHD) between the generated output and the actual causal graph to assess the outcomes. The ensuing experimental outcomes for SHD, vary across causal model sizes d, sample sizes n, and C..-
The experimental results are shown in Tables to 3
Table 1: Fixed model size d = 100 and the number of sampling n = 100, SHD results of causal discovery using Algorithm 1 for different C. values (10 runs).
C..
2
8
16
SHD
2.4 4: 29.5
2905.7 + 50.8
2900.6 + 80.8
2637. 4 200.4
1512.4 + 283.6
C.n
128
236
512
SHD
413.9 + 93.4
35.0 + 16.0
|
23.9 4.6
21.2 5.0
13.8 1.8
8

---

Table 2: Fixed model size d 10 and C... = 1, SHD results of causal discovery using Algorithm for the different number of sampling n (10 runs).
5
10
20
40
80
100
160
23.3 1: 2.7
23.0 4.0
16.5 13.0 4.0
10 and Cm = 1, SHD results of causal discovery using Algorithm for the different model size d (10 runs).
Table 3: Fixed the number of sampling =
5
10
20
40
80
100
SHD
4.5 + 2.0
29.6 2.2
124.3 4.6
522.8 # 11.6
1965.4 +: 18.7
2923.7 38.5
Analyzing the experimental outcomes, find notable pattern: higher values of C.., augmentedd sample sizes n, and reduced model size d all contribute to the performance off Algorithm I which is consistent with the insights from Theorem
Related Work
Score matching:
Score Matching was initially introduced by Hyvärinen [2055 and extended to
energy-based models by (Sng and Ermon [2019]. Subsequently, Vincent [2011] proposed denoising score matching, which transforms the estimation the score function for the original distribution
into an estimation for the noise distribution, effectively avoiding the need for second derivative
computations. Other methods, such as sliced score matching [Song et al. 2020]. denoising likelihood score matching [Chao et al. 2022), and kernel-based estimators, have also been proposed for score matching. The relationship between score matching and Fisher information [Shao et al. 2019]. as well as Langevin dynamics (Hyvarinen] 2007], has been explored. On the theoretical side, Wenliang and Kanagawa (2020) introduced the concept of "blindness" in score matching. while Koehler et al. 2023) compared the efficiency of maximum likelihood and score matching, although their results primarily focus on exponential family distributions. Our paper, for the first time, analyzes the sample complexity bounds of the score function estimating in causal inference.
Causal discovery: The application of score methods for causal inference for linear additive models began with Ghoshal and Honorio [2018), which proposed a causal structure recovery method based on topological ordering from the precision matrix (equivalent to the score in that setting). Under certain noise variance assumptions, their method can reliably recover the DAG in polynomial time and sample complexity.
In recent years, there have been numerous algorithms developed for causal inference in non-linear additive models. GraNDAG [Lachapelle et al. 2021] aims to maximize the likelihood of the observed data under this model and enforces a continuous constraint to ensure the acyclicity of the causal graph Rolland et al. [2022] proposed novel approach for causal inference which utilize score match- ing algorithms as a foundation for topological ordering and then employ sparse regression techniques to prune the DAG. Subsequently, MMntagnn et al. [2023a] extended the method to non-Gaussian noise, (anchezz et al. [2023) proposed to use diffusion models to fit the score function, and Montagnal al. 2023b] proposed new scalable score-based preliminary neighbor search techniques.
Although advances have been achieved in leveraging machine learning for causal discovery, there is generally lack of further research on error bounds. Other studies concentrate broader non- parametric models but depend on various assumptions like faithfulness, restricted faithfulness, or the sparsest Markov representation (Spirtes al. 2000, Raskutti and Uhler 2018 Solus et al. 2021)) These approaches employ conditional independence tests and construct a graph that aligns with the identified conditional independence relations [Zhang 2008].
Theoretical analysis of score-based generative modeling: Existing work mainly focuses on two
fundamental questions: "How do diffusion models utilize learned score functions to estimate the
data distribution?" [Chen al. 2023b De Bortoli et al. 2021 De Bortoli 2022 Lee al. 2022

---

2023] and "Can neural networks effectively approximate and learn score functions? What are the convergence rate and bounds on the sample complexity?" [Chen et al. 2023a
Specifically, De Bortoli et al. [2021] and et al. 2022 studied the convergence guarantees of diffusion models under the assumptions that the score estimator is accurate under the & and &2 norms. Concurrently (Chen et al. [2023b] and Lee et al. (2023) extended previous results to distributions with bounded moments. De Bortoli 2022] studied the distribution estimation guarantees of diffusion models for low-dimensional manifold data under the assumption that the score estimator is accurate under the & or &g norms.
However, these theoretical results rely on the assumption that the score function is accurately estimated, while the estimation of the score function is largely untouched due to the non-convex training dynamics. Recently, Chen et al.] 2023a] provided the first sample complexity bounds for score function estimation in diffusion models. However, their result is based on the assumption that the data distribution is supported on a low-dimensional linear subspace and they use a specialized Encoder-Decoder Encoder- Decoder network instead of general deep neural network. As result, complete theoretical picture of score-based generative modeling is still lacking.
7 Conclusion and Limitations
In this work, we investigate the sample complexity error bounds of Score Matching using deep ReLU neural networks under two different problem settings: causal discovery and score-base based generative modeling. We provide a sample complexity analysis for the estimation of the score function in the context of causal discovery for nonlinear additive Gaussian noise models, with convergence rate of logn Furthermore, we extend the sample complexity bounds for the estimation of the score funetion in the ScoreSDE method general data and achieve a convergence rate of 1 Additionally. we provide an upper bound on the error rate of the state-of-ther of-tth-arttt causal discovery method SCORE [Rolland al. [022]. showing that the error rate of this algorithm converges linearly with respect to the number of training data.
A core limitation of this work is limiting results to the Gaussian noise assumption. In fact, non-linear mechanisms with additive non-gaussian noise are also identifiable under mild additional assumptions [Peters et al., 2014] and Montagna et al. [2023a] already extended the score-matee coore-matching approach of Rolland et al. [2022] to that setting. Relaxing this assumption would also allow us to apply our bounds to interesting corner cases, such linear non- non-gaussian (Ghoshal and Honorio 2018), and non non-gaussian deterministic causal relations [Daniušis et al.) [anoing et al., (0155). It may be possible for this assumption to be relaxed in future work, but argue that the added challenge, the significant difference in algorithms, and the standalone importance of the non-linear Gaussian case justify
focus.
In addition, we make other assumptions that limit the general applicahility of our bounds. In particular, the assumption of the Lipschitz property for the score function imposes strong constraint the model space. Further investigating the relationship between the noise, the properties the nonlinear functions in the causal model [q. (4) and the resulting Lipschitz continuity of the score function would be an interesting extension of this work.
Acknowledgements
We are thankful to the reviewers for providing constructive feedback and Kun Zhang and Dominik Janzing for helpful discussion on the special case of deterministic children. This work was supported by Hasler Foundation Program: Hasler Responsible Al (project number 21043). This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021 105011. Francesco Locatello did not contribute this work at Amazon. Corresponding author: Zhenyu Zhu.
10

---

References
Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over-parameetrrizatoon In International Conference on Machine Learning (ICML), 2019.
A. Block, Y. Mroueh, and A. Rakhlin. Generative modeling with denoising auto-encoders and langevin sampling, 2020.
C.-H. Chao, W.-F. Sun, B.-W. Cheng, Y.C.. Lo, C.-C. Chang, Y.-I.. Liu, Y.-.. Chang, C.-P. Chen, and C.-Y. Lee. Denoising likelihood score matching for conditional score-based data generation. In International Conference on Learning Representations (ICLR), 2022.
M. Chen, W. Liao, H. Zha, and T. Zhao. Distribution approximation and statistical estimation guarantees of generative adversarial networks, 2020.
M. Chen, K. Huang, Zhao, and M. Wang. Score approximation, estimation and distribution recovery of diffusion models on low-dimensional data. In International Conference on Machine Learning (ICMI., 2023a.
S. Chen, S. Chewi, J. Li, Y. Li, A. Salim, and A. Zhang, Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In International Conference on Learning Representations (ICLR), 2023b.
D. M. Chickering. Learning bayesian networks is np-complete. Learning from data: Artificial intelligence and statistics V. 1996.
P. Daniušís, D. Janzing, J. Mooij, J. Zscheischler, B. Steudel, K. Zhang, and B. Schölkopf. Inferring deterministic causal relations. Uncertainty in Artificial Intelligence, 2010.
V. De Bortoli. Convergence denoising diffusion models under the manifold hypothesis, 2022.
V. De Bortoli, J. Thornton, J. Heng, and A, Doucet. Diffusion schrödinger bridge with applications to score-based generative modeling. In Advances in neural information processing systems (NeurIPS), 2021.
Dhariwal and Nichol. Diffusion models beat gans on image synthesis. In Advances in neural information processing systems (NeurIPS), 2021.
S. Du, J. Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning (ICML), 2019a.
S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes parameterized neural networks. In International Conference on Learning Representations (ICLR), 2019b.
M. Ghosh. Exponential tail bounds for chisquared random variables. Journal of Statistical Theory and Practice, 2021.
A. Ghoshal and Honorio. Learning linear structural equation models in polynomial time and sample complexity. In International Conference on Artificial Intelligence and Stutistics (AISTATS), 2016 8.
A. Hyvärinen. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 2005.
A. Hyvarinen. Connections between score matching, contrastive divergence, and pscudolikelihood for continuous-valure variables. IEEE Transactions on neural networks, 2007.
D. Janzing, B. Steudel, N. Shajarisales, and B. Schölkopf. Justifying cotemaation-goomelle causal inference. Measures of Complexity: Festschrift for Alexey Chervonenkis, 2015.
A. Jentzen and T. Kröger. Convergence rates for gradient descent in the training of overparameterized artificial neural networks with biases, 2021.
Koehler, Heckett, and Risteski. Statistical efficiency of score matching: The view from isoperimetry. In International Conference on Learning Representations (ICLR), 2023.
11

---

Z. Kong, W. Ping, J. Huang, K. Zhao, and B. Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. In International Conference on Learning Representations (ICLR), 2021.
Lachapelle, Brouillard, T. Deleu, and S. Lacoste-Julien. Gradient-based neural dag learning. In International Conference on Learning Representations (ICLR), 2021.
H. Lee, J. Lu, and Y. Tan. Convergence for score-based generative modeling with polynomial complexity. In Advances in neural information processing systems (NeurIPS), 2022.
H. Lee, J. Lu, and Y. Tan. Convergence of score-based generative modeling for general data distributions. In International Conference on Algorithmic Learning Theory, 2023.
E. Malach, G. Ychudai, S. Shalev-Schwartz, and O. Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference Machine Learning (ICML), 2020.
F. Montagna, N. Noceti, I.. Rosasco, K. Zhang, and F. Locatello. Causal discovery with score matching on additive models with arbitrary noise. In CLeaR, 2023a.
Montagna, N. Noceti, L. Rosasco, Zhang, and F. Locatello. Scalable causal discovery with score matching. In CLeaR, 2023b.
Q. Nguyen, M. Mondelli, and G. F. Montufar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks. International Conference on Machine Learning (ICML), 2021.
S. Oymak and M. Soltanolkotabi. Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 2020.
J. Peters, J. M. Mooij, D. Janzing, and B. Schölkopf. Causal discovery with continuous additive noise models. Journal of Machine Learning Research, 2014.
G. Raskutti and C. Uhler. Learning directed acyclic graph models based sparsest permutations. Stat, 2018.
Rolland, V. Cevher, M. Kleindessner, C. Russell, D. Janzing, B. Schölkopf, and Locatello. Score matching enables causal discovery of nonlinear additive noise models. In International Conference on Machine Learning (ICML), 2022.
K. Sachs, O. Perez, D. er, D. A. Lauffenburger, and G. P. Nolan. Causal protein protein-signaling networks derived from multiparameter single-cell data. Science, 2005.
P. Sanchez, J. P. Voisey, T. Xia, H. I. Watson, A. Q. O'Neil, and S. A. Tsaftaris. Causal machine learning for healthcare and precision medicine. Royal Society Open Science, 2022.
Sanchez, X. Liu, A. Q. O'Neil, and S. A. Tsaftaris. Diffusion models for causal discovery via topological ordering. In International Conference on Learning Representations (ICLR), 2023.
S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Shao, P. E. Jacob, Ding, and V. Tarokh. Bayesian model comparison with the hyvärinen score: Computation and consistency. Journal of the American Statistical Association, 2019.
L. Solus, Y. Wang, and C. Uhler. Consistency guarantees for greedy permutation-basee causal inference algorithms. Biometrika, 2021.
Y. Song and S. Ermon. Generative modeling by estimating gradients of the data distribution. In Advances in neural information processing systems (NeurIPS), 2019.
Y. Song, S. Garg. J. Shi, and S. Ermon. Sliced score matching: A scalable approach to density and score estimation. In Uncertainty in Artificial Intelligence. 2020.
Y. Song. J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations (ICLR), 2021.
12

---

P. Spirtes, C. N. Glymour, and R. Scheines. Causation, prediction, and search. MIT press, 2000.
M. Teyssier and D. Koller. Ordering-bascl search: A simple and effective algorithm for learning bayesian networks, 2012.
H. R. Varian. Causal inference in economics and marketing. Proceedings of the National Academy of Sciences, 2016.
R. Vershynin. High- Siggh-Dimensoonll Probability: An Introduction with Applications in Data Science. Taylor & Francis, 2018.
P. Vincent. A connection between score matching and denoising autoencoders. Neural computation, 2011.
X. Wang, Y. Du, Zhu, L. Ke, Chen, J. Hao, and J. Wang. Ordering-based causal discovery with reinforcement learning. In International Joint Conferences Artificial Intelligence (IJCAT), 2021.
L. K. Wenliang and H. Kanagawa. Blindness of score-based methods to isolated components and mixing proportions, 2020.
J. Zhang. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 2008.
Z. Zhu, Liu, G. Chrysos, and V. Cevher. Robustness deep learning: The good (width), the bad (depth), and the ugly (initialization). In Advances in neural information processing systems (NeurIPS), 2022.
13


Reviews:
[{"review_id": "CVNrdpWPPZ", "reviewer": "Reviewer_wqRq", "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.", "questions": "N/A", "limitations": "See weakness.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n\n2. 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.\n\n3. 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.\n\n2. 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.\n\n3. 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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the comments and suggestions from reviewer wqRq. Regarding the questions raised by the reviewer about the relationship between causal discovery and the generative model of the paper, as well as concerns about strong assumptions, we have provided responses in the [general response](https://openreview.net/forum?id=uNnPWR66b8&noteId=VWjUWDv2Kl). Below is the response addressing your additional questions:\n\n**Q1:  This paper does not design a more advanced algorithm.**\n\nA1: In this paper, we introduce the inaugural sample complexity bound for causal discovery in non-linear Gaussian models (to the best of our knowledge). This is an example of theory following practice, with the SCORE algorithm only having identifiability guarantees in the infinite data regime, but being backed up by empirical results with finite data sets. While we anticipate that this paper will establish a path toward statistically efficient causal discovery algorithms, we maintain that formulating a new algorithm falls beyond the scope of our present endeavor."}, {"review_id": "0fHYXaiFWE", "reviewer": "Reviewer_Ndh6", "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. ", "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. ", "limitations": "The assumptions are fairly well laid out. A major limitation now is that there is no empirical analysis.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n(+) 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.\n(+) 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).\n(-) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the input and suggestions provided by reviewer Ndh6. Regarding the issues raised by the reviewer concerning the relationship between causal discovery and the generative model of the paper, as well as the lack of experimental validation, we have addressed these concerns in the [general response](https://openreview.net/forum?id=uNnPWR66b8&noteId=VWjUWDv2Kl). We will also present the main results in a more comprehensive and clearer way in the next version of the paper, highlighting the main points of the paper.\n"}, {"review_id": "kRGLHX4ySr", "reviewer": "Reviewer_RLDi", "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.", "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. \n\nThere are many remarks. But I guess they can be incorporated more smoothly just as a text with proper rephrasing (if needed). \n \n98th line contains a typo with missing parentheses in the equation.\n\nTheorem 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? ", "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. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "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. \n\nThe 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)\n\nGiven 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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the comments and suggestions provided by reviewer RLDi. Regarding the convincing of Assumption 2 and the lack of validation experiments in the paper, we have addressed these concerns in the [general response](https://openreview.net/forum?id=uNnPWR66b8&noteId=VWjUWDv2Kl). In the next version of the paper, we will condense the background part, emphasize the key points of the paper, and provide proof sketches for the main results to present them in a more concise and clearer way. We will now provide responses to the other questions raised by the reviewer. Additionally, for the detailed issues, we will address them and incorporate the changes into the next version of the paper.\n\n**Q1: Low-dimensional assumptions in previous work.**\n\nA1: The previous work [1] rested on the assumption of low-dimensional data structures, employing this to decompose the score function and engineer specialized network architectures for the derivation of the upper bound. Our work takes a distinct route. We harness the inherent traits and conventional techniques of standard deep ReLU networks to directly deduce the upper error bound. We will add such a discussion in the next version of the paper.\n\n**References**\n\n[1] Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data. ICML 2023.\n"}, {"review_id": "eqAUZoBOIW", "reviewer": "Reviewer_FzFv", "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$.\n\nThey 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.", "questions": "### Details\n1. 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?\n2. 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.\n3. What is $\\tau$, the first argument to the covering number in line 203? Where is it defined?\n\n### Suggestions\n1. 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.\n2. Please reference all appendices in the paper. Appendices B, C, F, and G are not referenced in the paper.\n3. 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.", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "### Significance\nThe 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.\n\n### Clarity\nThe 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\nThis 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate the feedback and suggestions from reviewer FzFv. Regarding the issues raised by the reviewer regarding the relationship between causal inference and the generative model aspects of the paper, as well as the lack of experimental validation, we have provided responses in the [general response](https://openreview.net/forum?id=uNnPWR66b8&noteId=VWjUWDv2Kl). We will also enhance the comprehensiveness and clarity of the main results in the next version of the paper, emphasizing the paper's focal points. We will answer the other questions from the reviewer below. Furthermore, for the detailed problems, we will resolve them and incorporate the solutions in the next version of the paper.\n\n**Q1: What is the condition on the learning rate and can we extend the result to a larger batch GD.**\n\n\nA1: The use of SGD training is referenced in our three theorems. However, it's important to note that Theorem 1 and Theorem 3 are rooted in the generalization by sampling complexity bound. This makes them independent of the specific algorithm used, and consequently, we did not delve into learning rates here. The results are broadly applicable and can be seamlessly extended to encompass larger batch GD.\n\nRegarding Theorem 2, its foundation lies in the proof of SGD/GD convergence within deep networks, as elucidated in [1]. This proof necessitates certain conditions related to large network width ($m\\geq\\text{poly}(n,L)$) and a sufficiently small learning rate ($\\mathcal{O}(\\frac{1}{\\text{poly}(n,L)m \\log^2 m})$). These convergence outcomes also apply to BatchGD, as demonstrated in similar convergence results [2]. Hence, Theorem 2 can naturally be expanded to incorporate Batch GD as well.\n\n**Q2: The definition of $\\tau$ in the covering number.**\n\nA2: Sorry for the typo here. Instead of $\\tau$, it should be $\\frac{1}{n}$. We have revised this issue.\n\n**Q3: Modifications for Lemma 2.**\n\nA3: We presented Lemma 2 in this form to facilitate its utilization within the proof. But we concur with the reviewer's perspective that leaving out the reference to node $i$ in this lemma could enhance its clarity. As a result, we have restructured the phrasing of this lemma and subsequently refined the associated proof.\n\n**References**\n\n[1] A Convergence Theory for Deep Learning via Over-Parameterization. ICML 2019.\n\n[2] Convergence rates for gradient descent in the training of overparameterized artificial neural networks with biases.\n"}, {"review_id": "RHUucx07h4", "reviewer": "Reviewer_LFXr", "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.", "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?\n- Does Lemma 1 play a role in the later analysis? I wonder why we need Lemma 1.\n- The assumption in Line 148-149 is not properly justified.\n- Can the authors provide a specific case on when Assumption 2 holds and analysis on how practical this assumption?\n- 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?\n\nMinor issue:\n- It seems that the case l = 1 in Equation (3) can be merged into the case 2<=l<=L-1.\n- Line 107: donate -> denotes\n- The property mentioned in Line 108 seems unrelated to the Definition 1.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n", "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.\n- The definition of covering number should be included to make this work more self-contained.\n- 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.\n- 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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the feedback and suggestions provided by reviewer LFXr. Regarding the issues raised by the reviewer concerning the relationship between causal inference and the generative model aspects of the paper, as well as the convincing of assumption 2, we have addressed these matters in the [general response](https://openreview.net/forum?id=uNnPWR66b8&noteId=VWjUWDv2Kl). Furthermore, in the next version of the paper, we will present the main results in a more comprehensive and clearer way, emphasizing the key points of the paper and providing proof sketches to support the main results. Below, we will provide responses to additional questions raised by the reviewer. Additionally, we will address the details raised and incorporate the solutions in the next version of the paper.\n\n**Q1: The definition of covering number.**\n\n\nA1: The concept of the covering number plays a significant role in statistical learning theory. It is a widely used tool, often appearing in various learning theory textbooks. We appreciate the reviewer's suggestion. To enhance the self-contained nature of our paper, we plan to incorporate a new section in the appendix. This section will provide a comprehensive background definition of the covering number, ensuring that readers can grasp its essence without needing to refer to external sources.\n\n**Q2: Low-dimensional assumptions in previous work.**\n\n\nA2: The previous work [1] rested on the assumption of low-dimensional data structures, employing this to decompose the score function and engineer specialized network architectures for the derivation of the upper bound. Our work takes a distinct route. We harness the inherent traits and conventional techniques of standard deep ReLU networks to directly deduce the upper error bound. We will add such a discussion in the next version of the paper.\n\n**Q3: How do these results generalize to other related approaches?**\n\nA3: Firstly, our theoretical results in Theorems 1 and 3 are not influenced by the choice of algorithm used. Although Theorem 2 is established based on Algorithm 1, our technique provides a comprehensive processing strategy for those analogous algorithms which initially conduct a topological ordering based on the score function, followed by pruning to obtain the final DAG. So through suitable adaptations, our method can also be extended to similar algorithms [2][3].\n\n**Q4: The role of Lemma 1 in the paper.**\n\nA4: While Lemma 1 is not directly employed in the ensuing proofs presented in this paper, it serves as the cornerstone for Algorithm 1 in [2] in our analysis. Furthermore, it sheds light on vital properties of the non-linear additive Gaussian noise model. Its incorporation into the primary content might not be deemed essential, we plan to rectify this in the next version of the paper. We will introduce a dedicated section that delves into the discourse concerning Algorithm 1 and Lemma 1 in the appendix.\n\n**Q5: More discussion about Assumption 2.**\n\nA5: The left-hand side of Assumption 2 represents the expectation of the square of a random variable, this value is 0 when the function f is linear. Correspondingly, the value of $C_m$ is 0 too. For non-linear functions f, this value is greater than 0 (disregarding some extreme mathematical cases), and the corresponding $C_m$ is also greater than 0. \n\nTheorem 2 converges when $C_m$ is greater than 0, indicating that Algorithm 1 can converge for the causal discovery of any nonlinear causal relationships.\n\nDifferent non-linear functions f correspond to different values of $C_m$. The experimental results we provided in the general response demonstrate the varying outcomes of Algorithm 1 under causal relationships with different $C_m$ values.\n\n**Q6: The assumption in Line 148-149 is not properly justified.**\n\nA6: We disagree with the reviewer's view here. The content in lines 148-149 is not an assumption; it is based on the standard setting of theoretical analysis in Ornstein–Uhlenbeck process in score-based generative modeling, which has been widely employed in prior research [1, 4, 5]. However, we appreciate the reviewer's feedback and have added a remark at this point to clarify this setting.\n\n**References**\n\n[1] Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data. ICML 2023.\n\n[2] Scalable Causal Discovery with Score Matching. CLeaR 2023.\n\n[3] Causal Discovery with Score Matching on Additive Models with Arbitrary Noise. CLeaR 2023. \n\n[4] Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. ICLR 2023.\n\n[5] Diffusion Schrödinger Bridge with Applications to Score-Based Generative Modeling. NeurIPS 2021."}]

Author rebuttal:
# General response:

We extend our gratitude to the reviewers for their valuable feedback. In response to recurring issues highlighted by multiple reviewers, we offer a consolidated response as follows:

**Q1:  Relationship between two parts.**

A1: The theoretical foundation of this paper spans two distinct yet interconnected domains: causal discovery and score-based generative modeling. These two domains share intriguing interrelations while also exhibiting notable disparities.

These two domains are connected by a common theoretical foundation centered on the upper bound of score matching. Specifically, Theorems 1 and 3 study similar problems in different domains and share the same techniques drawn from statistical learning theory and deep learning theory. 

However, they also harbor autonomous elements, with the findings in the causal discovery domain having a relatively broader and more consequential scope. The foundation of Theorem 2 rests upon Theorem 1, but its result pertains to entirely separate problems. It can be seen as an embodiment of applying the upper bound of score matching for causal discovery. 

Consequently, we simplified the background part of the paper, relocating certain components to supplementary materials. Additionally, we enhance the explanations and provide succinct proof sketches for the theorem in the causal discovery part. This endeavor aims to present the main results in a manner universally comprehensible and illuminating.

Furthermore, if the reviewers think the title "Sample Complexity Bounds for Score-Matching: Causal Discovery and Generative Modeling" be better aligned with the paper's essence, we are willing to modify the title.

**Q2:  Lack of experiments.**

Following the reviewers' recommendations, we conducted a series of experiments to validate the theoretical findings presented in the paper. We took inspiration from the code provided in [1] and employed the structural Hamming distance (SHD) between the generated output and the actual causal graph to assess the outcomes. The ensuing experimental outcomes for SHD, vary across causal model sizes (d), sample sizes (n), and $C_m$. The specific results are shown in the pdf.

Analyzing the experimental outcomes, we find a notable pattern: higher values of $C_m$, augmented sample sizes $n$, and reduced model size $d$ all contribute to the algorithm's performance. This alignment with the insights from Theorem 2 in our paper is clear.

In the subsequent paper revision, we will incorporate these experimental findings to further enrich the paper's comprehensiveness.

**Q3:  Discussion of the assumptions.**

A3: As the reviewers point out, our assumptions are reasonable, with 1 and 3 being standard in the deep learning theory. Regarding assumption 2, we remark that this assumption is strongly linked with identifiability and that the algorithm does not make use of $C_m$.

This second assumption is particularly interesting because it relates the sample complexity bound with classical identifiability theory: if the mechanisms are linear, even with infinite data the graph is not identifiable. In this sense, this assumption cannot be violated. 

An interesting avenue for future work would be the effect of local assumption violations i.e., what if only one mechanism is linear but others are not? We can add a discussion on this for future work, however, this is far beyond the scope of the present work. In fact, most identifiability results in the infinite data regime still require causal assumptions to hold globally.  

**References**

[1] Score Matching Enables Causal Discovery of Nonlinear Additive Noise Models. ICML 2022.

Meta-review: This paper offers comprehensive theoretical findings concerning both causal discovery and score-based generative modeling. In the realm of causal discovery, it initiates with an in-depth examination of sample complexity, specifically focusing on the estimation of the score function for nonlinear additive Gaussian noise models. Additionally, the paper establishes a proof demonstrating that the error rate of the score-matching-based method, known as SCORE, exhibits linear convergence with respect to the quantity of training data. In the context of score-based generative modeling, the paper also presents sample complexity bounds for the estimation of the score function within the ScoreSDE framework.

The paper addresses a timely analysis of a recent score matching based causal discveory method. It offers a rigorous theoretical analysis of the properties of score-matching-based causal discovery. All the reviewers acknowledge the theoretical contribution of this work. However, the major issues of the paper is that the current version needs a significant revision to account for the comments in the review comments and rebuttal. I recommend recommend acceptance of this paper due to its solid contribution. The authors should carefully revise the paper by taking into the review comments.
Decision: Accept (poster)