Improved Sample Complexity Bounds for Diffusion Model Training

Authors: shivam  gupta
aditya  parulekar
eric  price
zhiyang  xun
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 22:20:06

Abstract: Diffusion models have become the most popular approach to deep generative modeling of images, largely due to their empirical performance and reliability. From a theoretical standpoint, a number of recent works [CCL+23, CCSW22, BBDD24] have studied the iteration complexity of sampling, assuming access to an accurate diffusion model. In this work, we focus on understanding the *sample complexity* of training such a model; how many samples are needed to learn an accurate diffusion model using a sufficiently expressive neural network? Prior work [BMR20] showed bounds polynomial in the dimension, desired Total Variation error, and Wasserstein error. We show an *exponential improvement* in the dependence on Wasserstein error and depth, along with improved dependencies on other relevant parameters.

Main paper: 
 introduction: 
 Score-based diffusion models are currently the most successful methods for image generation, serving as the backbone for popular text-to-image models such as stable diffusion [RBL + 22], Midjourney, and DALL•E [RDN + 22] as well as achieving state-of-the-art performance on other audio and image generation tasks [SDWMG15, HJA20, JAD + 21, SSXE22, DN21] .The goal of score-based diffusion is to produce a generative model for a possibly complicated distribution q 0 . This involves two components: training a neural network using true samples from q 0 to learn estimates of its (smoothed) score functions, and sampling using the trained estimates. To this end, consider the following stochastic differential equation, often referred to as the forward SDE:dx t = -x t dt + √ 2 dB t , x 0 ∼ q 0 (1)where B t represents Brownian motion. Here, x 0 is a sample from the original distribution q 0 over R d , while the distribution of x t can be computed to bex t ∼ e -t x 0 + N (0, σ 2 t I d ) for σ 2 t = 1e -2t . Note that this distribution approaches N (0, I d ), the stationary distribution of (1), exponentially fast. Let q t be the distribution of x t , and let s t (y) := ∇ log q t (y) be the associated score function. We refer to q t as the σ t -smoothed version of q 0 . Then, starting from a sample x T ∼ q T , there is a reverse Authors listed in alphabetical order.38th Conference on Neural Information Processing Systems (NeurIPS 2024). SDE associated with the above forward SDE in (1) [And82] :EQUATIONThat is to say, if we begin at a sample x T ∼ q T , following the reverse SDE in (2) back to time 0 will give us a sample from the original distribution q 0 . This suggests a natural strategy to sample from q 0 : start at a large enough time T and follow the reverse SDE back to time 0. Since x T approaches N (0, I d ) exponentially fast in T , our samples at time 0 will be distributed close to q 0 . In particular, if T is large enough-logarithmic in m2 ε -then samples produced by this process will be ε-close in TV to being drawn from q 0 . Here m 2 2 is the second moment of q 0 , given by m 2 2 := E x∼q0 [∥x∥ 2 ]. In practice, this continuous reverse SDE (2) is approximated by a time-discretized process. That is, the score s T -t is approximated at some fixed times 0 = t 0 ≤ t 1 ≤ • • • ≤ t k < T , and the reverse process is run using this discretization, holding the score term constant at each time t i . This algorithm is referred to as "DDPM", as defined in [HJA20] .Chen et al. [CCL + 23b] proved that as long as we have access to sufficiently accurate estimates for each score s t at each discretized time, this reverse process produces accurate samples. Specifically, for any d-dimensional distribution q 0 supported on the Euclidean Ball of radius R, the reverse process can sample from a distribution ε-close in TV to a distribution (γ • R)-close in 2-Wasserstein to q 0 in poly(d, 1/ε, 1/γ) steps, as long as the score estimates s t used at each step are O(ε 2 ) accurate in squared L 2 . That is, as long asEQUATIONIn this work, we focus on understanding the sample complexity of learning such score estimates. Specifically, we ask:How many samples are required for a sufficiently expressive neural network to learn accurate score estimates that generate high-quality samples using the DDPM algorithm?We consider a training process that employs the empirical minimizer of the score matching objective over a class of neural networks as the score estimate. More formally, we consider the following setting:Setting 1.1. Let F(D, P, Θ) be the class of functions represented by a fully connected neural network with ReLU activations and depth D, with P parameters, each bounded by Θ. Let {t k } be some time discretization of [0, T ]. Given m i.i.d. samples x i ∼ q 0 , for each t ∈ {t k }, we take m Gaussian samples z i ∼ N (0, σ 2 t I d ). We take s t to be the minimizer of the score-matching objective:EQUATION)We then use { s t k } as the score estimates in the DDPM algorithm.This is the same setting as is used in practice, except that in practice (4) is optimized with SGD rather than globally. As in [CCL + 23b], we aim to output samples from a distribution that is ε-close in TV to a distribution that is γR or γm 2 -close in Wasserstein to q 0 . We thus seek to bound the number of samples m to get such a good output distribution, in terms of the parameters of Setting 1.1 and ε, γ.Block et al. [BMR20] first studied the sample complexity of learning score estimates using the empirical minimizer of the score-matching objective (4). They showed sample complexity bounds that depend on the Rademacher complexity of F. Applied to our setting and using known bounds on Rademacher complexity of neural networks, in Setting 1.1 their result implies a sample complexity bound of O d 5/2 γ 3 ε 2 (Θ 2 P ) D √ D . See Appendix E for a detailed discussion.Following the analysis of DDPM by [CCL + 23b], more recent work on the iteration complexity of sampling [CLL22, BBDD24] has given an exponential improvement on the Wasserstein accuracy γ, as well as replacing the uniform bound R by m 2 -the square root of the second moment. In O hides polylogarithmic factors in d, 1 ε and 1 γ particular, [BBDD24] show that O( d ε 2 log 2 1 γ ) iterations suffice to sample from a distribution that is γ • m 2 close to q 0 in 2-Wasserstein, as long as the score estimates are O ε 2 /σ 2 t accurate, i.e.,EQUATIONInspired by these works, we ask: is it possible to achieve a similar exponential improvement in the sample complexity of learning score estimates using a neural network?We give a new sample complexity bound of O( d 2 ε 3 P D log Θ log 3 1 γ ) for learning scores to sufficient accuracy for sampling via DDPM. Learning is done by optimizing the same score matching objective that is used in practice. Compared to [BMR20] , our bound has exponentially better dependence on Θ, γ, and D, and a better polynomial dependence on d and P , at the cost of a worse polynomial dependence in ε.As discussed above, for the sampling process, it suffices for the score estimate s t at time t to have error O ε 2 /σ 2 t . This means that scores at larger times need higher accuracy, but they are also intuitively easier to estimate because the corresponding distribution is smoother. Our observation is that the two effects cancel out: we show that the sample complexity to achieve this accuracy for a fixed t is independent of σ t . However, this only holds once we weaken the accuracy guarantee slightly (from L 2 error to "L 2 error over a 1δ fraction of the mass"). We show that this weaker guarantee is nevertheless sufficient to enable accurate sampling. Our approach lets us run the SDE to a very small final σ t = γ, which yields a final γ dependence of O(log 3 1 γ ) via a union bound over the times t that we need score estimates s t for. In contrast, the approach in [BMR20] gets the stronger L 2 -accuracy, but requires a poly( 1 σt ) dependence in sample complexity for each score s t ; this leads to their poly( 1 γ ) sample complexity overall. To state our results formally, we make the following assumptions on the data distribution and the training process: A1 The second moment m 2 2 of q 0 is between 1/ poly(d) and poly(d). A2 For the score s t used at each step, there exists some function f ∈ F(D, P, Θ) (as defined in Setting 1.1) such that the L 2 error, E x∼qt [∥f (x)s t (x)∥ 2 ], is sufficiently small.That is: the data is somewhat normalized, and the smoothed scores can be represented well in the function class. Our main theorem is as follows:Theorem 1.2. In Setting 1.1, suppose assumptions A1 and A2 hold. For any γ > 0, consider the score functions trained fromm ≥ O d 2 P D ε 3 • log Θ • log 3 1 γ i.i.d.samples of q 0 . With 99% probability, DDPM using these score functions can sample from a distribution ε-close in TV to a distribution γm 2 -close to q in 2-Wasserstein.We remark that assumption A1 is made for a simpler presentation of our theorem; the (logarithmic) dependence on the second moment is analyzed explicitly in Theorem C.2. The quantitative bound for A2-exactly how small the L 2 error needs to be-is given in detail in Theorem C.3.Barrier for L 2 accuracy. As mentioned before, previous works have been using L 2 accurate score estimation either as the assumption for sampling or the goal for training. Ideally, one would like to simply show that the ERM of the score matching objective will have bounded L 2 error of ε 2 /σ 2 with a number of samples that scales polylogarithmically in 1 σ . Unfortunately, this is false. In fact, it is information-theoretically impossible to achieve this in general without poly( 1 σ ) samples. Since sampling to γm 2 Wasserstein error needs to consider a final σ t = γ, this leads to a poly( 1 γ ) dependence. See Figure 1 , or the discussion in Section 4, for a hard instance. samples from either p1 = (1 -η)N (0, 1) + ηN (-R, 1), or p2 = (1 -η)N (0, 1) + ηN (R, 1) we will only see samples from the main Gaussian with high probability, and cannot distinguish between them. However, if we pick the wrong score function, the L 2 error incurred is large -about ηR 2 . On the right, we take η = 0.001, R = 10000, δ = 0.01. We plot the probability that the ERM has error larger than 0 in the L 2 sense, and our D δ p sense.-R 0 R η √ 2π 1-η √ 2π p1 p2 -R 0 R s1 s2In the example in Figure 1 , score matching + DDPM still works to sample from the distribution with sample complexity scaling with poly(log 1 γ ); the problem lies in the theoretical justification for it. Given that it is impossible to learn the score in L 2 to sufficient accuracy with fewer than poly( 1 γ ) samples, such a justification needs a different measure of estimation error. We will introduce such a measure, showing (1) that it will be small for all relevant times t after a number of samples that scales polylogarithmically in 1 γ , and (2) that this measure suffices for fast sampling via the reverse SDE. The problem with measuring error in L 2 comes from outliers: rare, large errors can increase the L 2 error while not being observed on the training set. We proved that we can relax the L 2 accuracy requirement for diffusion model to the (1δ)-quantile error: For distribution p, and functions f, g, we say thatEQUATIONWe adapt [BBDD24] to show that learning the score in our new outlier-robust sense also suffices for sampling, if we have accurate score estimates at each relevant discretization time. Lemma 1.3. Let q be a distribution over R d with second moment m 2 2 between 1/poly(d) and poly(d). For any γ > 0, there existN = O( d ε 2 +δ 2 log 2 1 γ ) discretization times 0 = t 0 < t 1 < • • • < t N <T such that if the following holds for every k ∈ {0, . . . , N -1}:D δ/N q T -t k ( s T -t k , s T -t k ) ≤ ε σ T -t k then DDPM can sample from a distribution that is within O(δ + ε log (d/γ)) in TV distance to q γ in N steps.With this relaxed requirement, our main technical lemma shows that for each fixed time, a good (1δ)-quantile accuracy can be achieved with a small number of samples, independent of σ t . Lemma 1.4 (Main Lemma). In Setting 1.1, suppose assumptions A1 and A2 hold. By taking m i.i.d. samples from q 0 to train score function s t , whenm > O (d + log 1 δtrain ) • P D ε 2 δ score • log Θ δ train ,with probability 1δ train , the score estimate s t satisfiesD δscore qt ( s t , s t ) ≤ ε/σ t .Combining Lemma 1.4 with Lemma 1.3 gives us Theorem 1.2. The proof is detailed in Appendix C. 
related work: 
 Score-based diffusion models were first introduced in [SDWMG15] as a way to tractably sample from complex distributions using deep learning. Since then, many empirically validated techniques have been developed to improve the sample quality and performance of diffusion models [HJA20, ND21, SE20 On the training side, [BMR20] showed that for distributions bounded by R, the score-matching objective learns the score of q γ in L 2 using a number of samples that scales polynomially in 1 γ . On the other hand, for sampling using the reverse SDE in (2), [CLL22, BBDD24] showed that the number of steps to sample from q γ scales polylogarithmically in 1 γ given L 2 approximations to the scores. Our main contribution is to show that while learning the score in L 2 requires a number of samples that scales polynomially in 1 γ , the score-matching objective does learn the score in a weaker sense with sample complexity depending only polylogarithmically in 1 γ . Moreover, this weaker guarantee is sufficient to maintain the polylogarithmic dependence on 1 γ on the number of steps to sample with γ • m 2 2-Wasserstein error.Our work, as well as [BMR20] , assumes the score can be accurately represented by a small function class such as neural networks. Another line of work examines what is possible for more general distributions [CHZW23, OAS23] . For example, [CHZW23] shows that for general subgaussian distributions, the scores can be learned to L 2 error ε/σ t with (d/ε) O(d) samples. Our approach avoids this exponential dependence, but assumes that neural networks can represent the score.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We discuss limitations of our assumptions in the introduction, after we state them, as well as in the related work and conclusion sections.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
proof overview: 
 In this section, we outline the proofs for two key lemmas: Lemma 1.4 in Section 3.1 and Lemma 1.3 in Section 3.2. The complete proofs for these lemmas are provided in Appendix A and Appendix B respectively.We show that the score-matching objective (4) concentrates well enough that the ERM is close to the true minimizer. Prior work on sampling [BBDD24] shows that estimating the σ-smoothed score to L 2 2 error of ε 2 σ 2 suffices for sampling; our goal is to get something close to this with a sample complexity independent of σ.Background: Minimizing the true expectation gives the true score. In this section, we show that if we could compute the true expectation of the score matching objective, instead of just the empirical expectation, then the true score would be its minimizer. For a fixed t, let σ = σ t and p be the distribution of e -t x for x ∼ q 0 . We can think of a joint distribution of (y, x, z) where y ∼ p and z ∼ N (0, σ 2 I d ) are independent, and x = y + z is drawn according to q t . With this change of variables, the score matching objective used in (4) isE x,z s(x) - -z σ 2 2 2 .Because x = y + z for Gaussian z, Tweedie's formula states that the true score s * = s t is given byEQUATION)The third term does not depend on s, and so does not affect the minimizer of this loss function. Also, for every x, the second term is zero on average over (z | x), so we havearg min s E x,z [l(s, x, z)] = arg min s E x,z [∥s(x) -s * (x)∥ 2 ]This shows that the score matching objective is indeed minimized by the true score. Moreover, an ε-approximate optimizer of l(s) will be close in L 2 , as needed by prior samplers.Understanding the ERM. The algorithm chooses the score function s minimizing the empirical loss,Ê x,z [l(s, x, z)] := 1 m m i=1 l(s, x i , z i ) = Ê x,z [∥s(x) -s * (x)∥ 2 + 2⟨s(x) -s * (x), ∆⟩ + ∥∆∥ 2 ].Again, the Ê[∥∆∥ 2 ] term is independent of s, so it has no effect on the minimizer and we can drop it from the loss function. We thus defineEQUATIONthat satisfies l ′ (s * , x, z) = 0 andEQUATIONfor all candidate score functions s that are "far" from s * . This would ensure that the empirical minimizer of the score matching objective is not "far" from s * . To do this, we show that (10) is true with high probability for each individual s, then take a union bound over a net.Boundedness of ∆. Now, z ∼ N (0, σ 2 I d ) is technically unbounded, but is exponentially close to being bounded: ∥z∥ ≲ σ √ d with overwhelming probability. So for the purpose of this proof overview, imagine that z were drawn from a distribution of bounded norm, i.e., ∥z∥ ≤ Bσ always; the full proof (given in Appendix A) needs some exponentially small error terms to handle the tiny mass the Gaussian places outside this ball. Then, since ∆ = σ 4 + RB σ 3 . We can then apply a Chernoff bound to show concentration of l ′ : for poly(ε, R σ , B, log 1 δtrain ) samples, with 1δ train probability we haveÊ x,z [l ′ (s, x, z)] ≥ E x,z [l ′ (s, x, z)] - ε σ 2 = E[∥s(x) -s * (x)∥ 2 ] - ε 2 σ 2 which is greater than zero if E[∥s(x) -s * (x)∥ 2 ] > ε 2 σ 2 .Thus the ERM would reject each score function that is far in L 2 . However, as we show in Section 4, restrictions (1) and (2) are both necessary: the score matching ERM needs a polynomial dependence on both the distribution norm and the candidate score function values to learn in L 2 .The main technical contribution of our paper is to avoid this polynomial dependence on 1/σ. To do so, we settle for rejecting score functions s that are far in our stronger distance measure D δscore p , i.e., for whichEQUATIONApproach. We want to show (10), which is a concentration over x and z. Now, x is somewhat hard to control, because it depends on the unknown distribution, but z ∼ N (0, σ 2 I d ) is very well behaved. This motivates breaking up the expectation over x, z into an expectation over x and z | x. Following this approach, we could try to show thatÊ x,z [l ′ (s, x, z)] ≥ Ê x [ E z|x [l ′ (s, x, z)]]However, this is not possible to show; the problem is that this could be unbounded, since s(x) is an arbitrary neural network that could have extreme outliers. So, we instead show this is true with high probability if we clip the internal value, making itA x := Ê x [min( E z|x [l ′ (s, x, z)], 10B 2 σ 2 )] = Ê x [min(∥s(x) -s * (x)∥ 2 , 10B 2 σ 2 )].Note that A x is a function of the empirical samples x. If s is a score that we want to reject under (11), then we know that A x is an empirical average of values that are at least ε 2 σ 2 with probability δ score . It therefore holds that, for m > O( log 1 δ train δscore ), we will with 1δ train probability over the samples x haveEQUATION)Concentration about the intermediate notion. Finally, we show that for every set of samples x i satisfying (12), we will haveÊz|x [l ′ (s, x, z)] ≥ A x 2 > 0.This then impliesÊ x,z [l ′ (s, x, z)] ≥ Ê x A x 2 ≳ ε 2 δ score σ 2 ,as needed. For each sample x, we split our analysis of Êz|x [l(s, x, z)] into two cases:Case 1: ∥s(x) -s * (x)∥ > O( B σ ).In this case, by Cauchy-Schwarz and the assumption that∥∆∥ ≤ 2B/σ, l ′ (s, x, z) ≥ ∥s(x) -s * (x)∥ 2 -O( B σ ) ∥s(x) -s * (x)∥ ≥ 10B 2 σ 2so these x will contribute the maximum possible value to A x , regardless of z (in its bounded range).Case 2: ∥s(x) -s * (x)∥ < O( B σ ). In this case, |l ′ (s, x, z)| ≲ B 2 /σ 2 and Var z|x (l ′ (s, x, z)) = 4 E[⟨s(x) -s * (x), ∆⟩ 2 ] ≲ B 2 σ 2 ∥s(x) -s * (x)∥2 so for these x, as a distribution over z, l ′ is bounded with bounded variance.In either case, the contribution to A x is bounded with bounded variance; this lets us apply Bernstein'sinequality to show, if m > O( B 2 log 1 δ train σ 2 A ) ≈ O( B 2 log 1 δ trainε 2 δscore ), for every x we will haveÊ z [l ′ (s, x, z)] ≥ A 2 > 0with 1δ train probability.B 2 log 1 δ train ε 2 δscore ).Then with 1δ train probability we will have (12); and conditioned on this, with 1δ train probability we will have Êx,z [l ′ (s, x, z)] > 0. Hence this m suffices to distinguish any candidate score s that is far from s * . For finite hypothesis classes we can take the union bound, incurring a log |H| loss (this is given as Theorem A.2). Lemma 1.4 follows from applying this to a net over neural networks, which has size log H ≈ P D log Θ.Now we overview the proof of Lemma 1.3, i.e., why having an ε/σ T -t k accuracy in the D δ q sense is sufficient for accurate sampling.To practically implement the reverse SDE in (2), we discretize this process into N steps and choose a sequence of times 0 = t 0 < t 1 < • • • < t N < T . At each discretization time t k , we use our score estimates s t k and proceed with an approximate reverse SDE using our score estimates, given by the following. For tEQUATIONThis is almost the reverse SDE that would give exactly correct samples, with two sources of error: it starts at N (0, I d ) rather than q T , and it uses s T -t k rather than the s T -t . The first error is negligible, since q T is e -T -close to N (0, I d ). But how much error does the switch from s to s introduce?Let Q be the law of the reverse SDE using s, and let Q be the law of (13). Then Girsanov's theorem states that the distance between Q and Q is defined by the L 2 error of the score approximations:EQUATIONThe first line is an equality. The second line comes from approximating x T -t by x T -t k , which for small time steps is quite accurate. So in previous work, good L 2 approximations to the score mean ( 14) is small, and hence KL(Q ∥ Q) is small. In our setting, where we cannot guarantee a good L 2 approximation, Girsanov actually implies that we cannot guarantee that KL(Q ∥ Q) is small.However, since we finally hope to show closeness in TV, we can circumvent the above as follows.We define an event E to be the event that the score is bounded well at all time steps x T -t k , i.e.,E := k∈{1,...,N } ∥ s T -t k (x T -t k ) -s T -t k (x T -t k )∥ ≤ ε σ T -t k .If we have a D δ/N qt k accuracy for each score, we have 1 -P [E] ≤ δ. Therefore, if we look at the TV error between Q and Q, instead of bounding KL(Q ∥ Q). The TV between Q and Q can be then bounded byTV(Q, Q) ≤ (1 -P [E]) + TV((Q | E), ( Q | E)).The second term TV((Q | E), ( Q | E))is bounded because after conditioning on E, the score error is always bounded, so now we can use (14) to bound the KL divergence between Q and Q, then use Pinsker's inequality to translate KL into TV distance.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
hardness of learning in l 2: 
 In this section, we give concrete examples where it is difficult to learn the score in L 2 , even though learning to sufficient accuracy for sampling is possible. Previous works, such as [BBDD24] , require the L 2 error of the score estimate s t to be bounded by ε/σ t . We demonstrate that achieving this guarantee is prohibitively expensive: sampling from a σ t -smoothed distribution requires at least poly(1/σ t ) samples. Thus, sampling from a distribution γ-close in 2-Wasserstein to q 0 requires polynomially many samples in 1 γ . To show this, we demonstrate two lower bound instances. Both of these instances provide a pair of distributions that are hard to distinguish in L 2 , and emphasize different aspects of this hardness:1. The first instance shows that even with a polynomially bounded set of distributions, it is information theoretically impossible to learn a score with small L 2 error with high probability, with fewer than poly(1/γ) samples.0 R η √ 2π 1 √ 2π True Dist. Alternate Dist. 0 10 √ log m R True Score Alternate ScoreFigure 2 : For m samples from N (0, 1), consider the score s of the mixture ηN (0, 1) + (1 -η)N (R, 1) above with η is chosen so that s(10 √ log m) = 0. For this s, the score-matching objective is close to 0, while the squaredL 2 error is Ω R 2 m .2. In the second instance, we show that even with a simple true distribution, such as a single Gaussian, distinguishing the score matching loss of the true score function from one with high L 2 error can be challenging with fewer than poly(1/γ) samples if the hypothesis class is large, such as with neural networks.Information theoretically indistinguishable distributions: For our first example, consider the two distributions (1η)N (0, σ 2 ) + ηN (±R, σ 2 ), where R is polynomially large. Even though these distributions are polynomially bounded, it is impossible to distinguish these in L 2 given significantly fewer than 1 η samples. However, the L 2 error in score incurred from picking the score of the wrong distribution is large. In Figure 1 , the rightmost plot shows a simulation of this example, and demonstrates that the L 2 error remains large even after many samples are taken. Formally, we have: Lemma 4.1. Let R be sufficiently larger than σ. Let p 1 be the distribution (1η)N (0, σ 2 ) + ηN (-R, σ 2 ) with corresponding score function s 1 , and let p 2 be (1η)N (0, σ 2 ) + ηN (R, σ 2 ) with score s 2 , such that η = ε 2 σ 2 R 2 . Then, given m < R 2 ε 2 σ 2 samples from either distribution, it is impossible to distinguish between p 1 and p 2 with probability larger than 1/2 + o m (1). But,E x∼p1 ∥s 1 (x) -s 2 (x)∥ 2 ≳ ε 2 σ 2 and E x∼p2 ∥s 1 (x) -s 2 (x)∥ 2 ≳ ε 2 σ 2 .Simple true distribution: Now, consider the true distribution being N (0, σ 2 ), and, for large S, let s be the score of the mixture distribution ηN (0, σ 2 ) + (1η)N (S, σ 2 ), as in Figure 2 . This score will have practically the same score matching objective as the true score for the given samples with high probability, as shown in Figure 2 , since all m samples will occur in the region where the two scores are nearly identical. However, the squared L 2 error incurred from picking the wrong score function s is large We formally show this result in the following lemma: Lemma 4.2. Let S be sufficiently large. Consider the distribution p = ηN (0,σ 2 ) + (1 -η)N (S, σ 2 ) for η = Se -S 2 2 +10 √ log m•S 10 √ log m, and let s be its score function. Given m samples from the standard Gaussian p * = N (0, σ 2 ) with score function s * , with probability at least 1 -1 poly(m) ,E ∥ s(x) -s * (x)∥ 2 ≤ 1 σ 2 e -O(S √ log m) but E x∼p * ∥ s(x) -s * (x)∥ 2 ≳ S 2 mσ 4 .Together, these examples show that even with reasonably bounded or well-behaved distributions, it is difficult to learn the score in L 2 with fewer than poly(R/γ) samples, motivating our (1δ)-quantile error measure.Lemma A.2 (Score Estimation for Finite Function Class). For any distribution q 0 and time t > 0, consider the σ t -smoothed version q t with associated score s t . For any finite set H of candidate score functions. If there exists some s * ∈ H such thatEQUATIONfor a sufficiently large constant C, then using m > O 1 ε 2 δscore (d + log 1 δtrain ) log |H| δtrain samples, the empirical minimizer ŝ of the score matching objective used to estimate s t satisfiesD δscore qt (ŝ, s t ) ≤ ε/σ t with probability 1 -δ train .Proof. Per the notation discussion above, we set s = s t and σ = σ t . Denote l(s, x, z):= s(x) - -z σ 2 2 2We will show that for all s such that D δscore q (s, s) > ε/σ, with probability 1δ train ,Ê [l(s, x, z) -l(s * , x, z)] > 0,so that the empirical minimizer ŝ is guaranteed to haveD δscore q (ŝ, s) ≤ ε/σ.We haveEQUATION)Note that by Markov's inequality, with probability 1δ train /3,E x ∥s * (x) -s(x)∥ 2 ≤ δ score • ε 2 30 • σ 2 .By Lemma A.3, with probability 1δ train /3,E ⟨s * (x) -s(x), s(x) - -z σ 2 ⟩ ≤ δ score • ε 2 100σ 2Also, by Corollary A.5, with probability 1δ train /3, for all s ∈ H that satisfy D δscore q (s, s) > ε/σ simultaneously,Ê s(x) - -z σ 2 2 -s(x) - -z σ 2 2 ≥ δ score ε 2 16σ 2 .Plugging in everything into equation ( 16), we have, with probability 1δ train , for all s ∈ H with D δscore q (s, s) > ε/σ simultaneously,Ê [l(s, x, z) -l(s * , x, z)] ≥ δ score ε 2 16σ 2 - δ score ε 2 30σ 2 - δ score ε 2 50σ 2 > 0 as required.Lemma A.3. For any distribution q 0 and time t > 0, consider the σ t -smoothed version q t with associated score s t . Suppose s * is such thatE x∼qt ∥s * (x) -s(x)∥ 2 ≤ δ score • δ train • ε 2 Cσ 2 tfor a sufficiently large constant C. Then, using m > O1 ε 2 δscore d + log 1 δtrain samples (x i , y i , z i )where y i ∼ q 0 , z i ∼ N (0, σ 2 I d ) and x i = e -t y i + z i ∼ q t , we have with probability 1δ train ,E ⟨s * (x) -s(x), s(x) - -z σ 2 ⟩ ≤ δ score ε 2 1000σ 2 Proof. Note that s(x) = E z|x -z σ 2 so that E ⟨s * (x) -s(x), s(x) - -z σ 2 ⟩ = 0Also, for any δ, with probability 1δ, by Lemmas F.4 and F.5,∥s(x) - -z σ 2 ∥ 2 ≤ C d + log 1 δ σ 2 .for some constant C. Let E be the event that ∥s(x)--zσ 2 ∥ 2 ≤ C d+log d ε 2 δscore δ train σ 2. Since ∥s(x)--z σ 2 ∥ 2 is subexponential with parameter σ 2 and has mean O d σ 2 by the above, by Lemma F.7, we haveE ∥s(x) - -z σ 2 ∥ 2 | Ē ≲ d + log d ε 2 δscoreδtrain σ 2 Then, since P[E] ≥ 1 - ε 2 δscoreδtrain 100(d+log d ε 2 δscore δ train ) ≥ 1 2 and E ∥s * (x) -s(x)∥ 2 | Ē ≤ E ∥s * (x) -s(x)∥ 2 / P[ Ē],we haveE ⟨s * (x) -s(x), s(x) - -z σ 2 ⟩|E = - E ⟨s * (x) -s(x), s(x) --z σ 2 ⟩| Ē P[ Ē] P[E] ≤ E ∥s * (x) -s(x)∥ 2 | Ē E ∥s(x) --z σ 2 ∥ 2 | Ē P[ Ē] P[E] ≤ 2 E[∥s * (x) -s(x)∥ 2 ] E ∥s(x) - -z σ 2 ∥ 2 | Ē P[ Ē] ≲ 1 σ 2 ε 2 δ score δ train C • d + log d ε 2 δ score δ train • ε 2 δ score δ train 100(d + log d ε 2 δscoreδtrain ) ≤ ε 2 δ score δ train √ Cσ 2 .Moreover,E ⟨s * (x) -s(x), s(x) - -z σ 2 ⟩ 2 |E ≤ E ∥s * (x) -s(x)∥ 2 ∥s(x) - -z σ 2 ∥ 2 |E ≲ E ∥s * (x) -s(x)∥ 2 ( d + log d ε 2 δscoreδtrain σ 2 )|E ≲ δ score • δ train • ε 2 Cσ 2 • d + log d ε 2 δscoreδtrain σ 2 .So, by Chebyshev's inequality, with probability 1δ train /2,E ⟨s * (x) -s(x), s(x) - -z σ 2 ⟩|E ≲ ε 2 δ score δ train √ Cσ 2 + 1 σ 2 δ score • ε 2 • (d + log d ε 2 δscoreδtrain ) Cm ≲ δ score • ε 2 √ Cσ 2for our choice of m. Since E holds except with probabilityε 2 δscoreδtrain 100(d+log d ε 2 δscore δ train) ≪ δ train , we have with probability 1δ train in total,E ⟨s * (x) -s(x), s(x) - -z σ 2 ⟩ ≤ δ score • ε 2 1000σ 2for sufficiently large constant C.Lemma A.4. Consider any set F of functions f : R d → R d such that for all f ∈ F,P x∼p [∥f (x)∥ > ε/σ] > δ score .Then, with m > O 1 m m i=1 -2 -z i σ 2 -E -z σ 2 |x i T f (x i ) + 1 2 ∥f (x i )∥ 2 ≥ δ score • ε 2 16σ 2holds for all f ∈ F.Proof. Defineh f (x, z) := -2 -z σ 2 -E -z σ 2 |x T f (x) + 1 2 ∥f (x)∥ 2We want to show that h f hasEQUATIONfor all f ∈ F with probability 1δ train .Let B = O √ d+log m εδscore δ train σ . For f ∈ F, let g f (x, z) = B 2 if ∥f (x)∥ ≥ 10B h f (x, z) otherwisebe a clipped version of h f (x, z). We will show that for our chosen number of samples m, the following hold with probability 1δ train simultaneously:1. For all i, -ziσ 2 ≤ B. 2. For all i, E[ -z σ 2 |x i ] ≤ B 3. Ê[g f (x, z)] ≥ δscoreε 2 16 for all f ∈ FTo show that these together imply (17), note that wheneverg f (x i , z i ) ̸ = h f (x i , z i ), ∥f (x i )∥ ≥ 10B. So, since ∥ -zi σ 2 ∥ ≤ B and ∥ E[ -z σ 2 |x i ]∥ ≤ B, h f (x i , z i ) = -2 -z i σ 2 -E -z σ 2 |x i T f (x i ) + 1 2 ∥f (x i )∥ 2 ≥ -4B∥f (x i )∥ + 1 2 ∥f (x i )∥ 2 ≥ B 2 ≥ g f (x i , z i ).So under conditions 1, 2, 3, for all f ∈ F,Ê[h f (x, z)] ≥ Ê[g f (x, z)] ≥ δ score ε 216σ 2 So it just remains to show that conditions 1, 2, 3 hold with probability 1δ train simultaneously.1. For all i, -zi σ 2 ≤ B. Holds with probability 1δ train /3 by Lemma F.5 and the union bound.2. For all i, E -z σ 2 | x i ≤ B. Holds with probability 1δ train /3 by Lemma F.6 and the union bound.3. Ê[g f (x, z)] ≥ δscoreε 216σ 2 for all f ∈ F. Let E be the event that 1. and 2. hold. Let a i = min(∥f (x i )∥, 10B). We proceed in multiple steps.• Conditioned on E, |g f (x i , z i )| ≲ B 2 . If ∥f (x i )∥ ≥ 10B, |g f (x i , z i )| = B 2 by definition.On the other hand, when ∥f (x i )∥ < 10B, since we condition on E,|g f (x i , z i )| = |h f (x i , z i )| = -2 -z i σ 2 -E -z σ 2 |x i T f (x i ) + 1 2 ∥f (x i )∥ 2 ≲ B 2 • E [g f (x i , z i )|E, a i ] ≳ a 2 i -O(δ train B 2 ).First, note that by definition of g f (x, z), for a i = 10B,E [g f (x i , z i )|a i = 10B] = B 2 Now, for a i < 10B, E [g f (x i , z i )|a i ] = E [h f (x i , z i )|a i ] = E xi|∥f (xi)∥=ai E -z|xi [h f (x i , z)] Now, note that E z|x [h f (x, z)] = 1 2 ∥f (x)∥ 2 So, for a < 10B E [g f (x i , z i )|a i ] = 1 2 a 2 i Now let g clip f (x i , z i ) be a clipped version of g f (x i , z i ), clipped to ±CB 2 for sufficiently large constant C. We have, by above,E[g f (x i , z i )|a i , E] = E[g clip f (x i , z i )|a i , E] But, E[g clip f (x i , z i )|a i , E] ≥ E[g clip f (x i , z i )|a i ] -O(δ train B 2 ) ≳ a 2 i -O(δ train B 2 ) • Var(g f (x i , z i )|a i , E) ≲ a 2 i B 2. For a i = 10B, we have, by definition of g f (x, z),Var(g f (x i , z i )|a i , E) ≲ B 4 ≲ a 2 i B 2On the other hand, for a i < 10B,Var(g f (x i , z i )|a i , E) ≤ E g f (x i , z i ) 2 |a i , E = E   -2 -z i σ 2 -E -z σ 2 |x i T f (x i ) + 1 2 ∥f (x i )∥ 2 2   ≲ a 2 i B 2 by Cauchy-Schwarz. • With probability 1 -δ train /3, for all f ∈ F, E[g f (x i , z i )] ≳ Ω ε 2 δscore σ 2Using the above, by Bernstein's inequality, with probability 1δ train /6,E [g f (x i , z i )|a i , E] ≳ 1 n n i=1 a 2 i -O(δ train B 2 ) - 1 n B n i=1 a 2 i log 1 δ train - 1 n B 2 log 1 δ train Now, note that since P x∼pσ [∥f (x)∥ > ε/σ] ≥ δ score , we have with probability 1 - δ train /6, for n > O log 1 δ train δscore 1 n n i=1 a 2 i ≥ Ω ε 2 δ score σ 2 So, for n > O B 2 •σ 2 log 1 δ train ε 2 δscore, we have, with probability 1δ train /3,E [g f (x i , z i )|E] ≳ Ω ε 2 δ score σ 2 -O(δ train B 2 ) Rescaling so that δ train ≤ O ε 2 δscore σ 2 •B 2 , for n > O B 2 •σ 2 log B 2 •σ 2 ε 2 δscoreδ train ε 2 •δscore, we have, with probability 1δ train /3,E [g f (x i , z i )|E] ≳ Ω ε 2 δ score σ 2Combining with 1. and 2. gives the claim for a single f ∈ F. Union bounding over the size of F gives the claim.Corollary A.5. Let H bad be a set of score functions such that for all s ∈ H bad ,D δscore q (s, s) > ε/σ.Then, for m > O E ∥s(x) - -z σ 2 ∥ 2 -∥s(x) - -z σ 2 ∥ 2 ≥ δ score ε 2 16σ 2for all s ∈ H bad .Proof. We have, for f (x) := s(x)s(x),∥s(x) - -z σ 2 ∥ 2 -∥s(x) - -z σ 2 ∥ 2 = ∥f (x) + (s(x) - -z σ 2 )∥ 2 -∥s(x) - -z σ 2 ∥ 2 = ∥f (x)∥ 2 + 2(s(x) - -z σ 2 ) T f (x) = ∥f (x)∥ 2 -2( -z σ 2 -E[ -z σ 2 |x]) T f (x)since s(x) = E -z σ 2 |x by Lemma F.1. Then, by definition, for s ∈ H bad , for the associated f , P[∥f (x)∥ > ε/σ] > δ score . So, by Lemma A.4, the claim follows. 
conclusion and future work: 
 In this work, we have addressed the sample complexity of training the scores in diffusion models. We showed that a neural networks, when trained using the standard score matching objective, can be used for DDPM sampling after O( d 2 P D ε 3 log Θ log 3 1 γ ) training samples. This is an exponentially better dependence on the neural network depth D and Wasserstein error γ than given by prior work. To achieve this, we introduced a more robust measure, the 1δ quantile error, which allows for efficient training with poly(log 1 γ ) samples using score matching. By using this measure, we showed that standard training (by score matching) and sampling (by the reverse SDE) algorithms achieve our new bound.One caveat is that our results, as well as those of the prior work [BMR20] focus on understanding the statistical performance of the score matching objective: we show that the empirical minimizer of the score matching objective over the class of ReLU networks approximates the score accurately. We do not analyze the performance of Stochastic Gradient Descent (SGD), commonly used to approximate this empirical minimizer in practice. Understanding why SGD over the class of neural networks performs well is perhaps the biggest problem in theoretical machine learning, and we do not address it here.A Sample Complexity to Achieve (1δ)-Quantile AccuracyThe goal of this section is to prove our main lemma, the sample complexity bound to learn score at a single time. More specifically, we will give a quantitative version of Lemma 1.4. Lemma A.1 (Main Lemma, Quantitative Version). Let q 0 be a distribution with second moment m 2 2 . Let ϕ θ (•) be the fully connected neural network with ReLU activations parameterized by θ, with P total parameters and depth D. Let Θ > 1. Suppose there exists some weight vector θ * with ∥θ * ∥ ∞ ≤ Θ such thatE x∼qt ∥ϕ θ * (x) -s t (x)∥ 2 ≤ δ score • δ train • ε 2 C • σ 2 tfor a sufficiently large constant C. By taking m i.i.d. samples from q 0 to train score s t , whenm > O (d + log 1 δtrain ) • P D ε 2 δ score • log max(m 2 , 1) • Θ δ train ,the empirical minimizer ϕ θ of the score matching objective used to estimate s t (overϕ θ with ∥θ∥ ∞ ≤ Θ) satisfies D δscore qt (ϕ θ , s t ) ≤ ε/σ t . with probability 1 -δ train .In order to prove the lemma, we first consider the case when learning the score over a finite function class H. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We do not have any data or models to release.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: The paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: The main result (Lemma A.2) of this section shows that if there is a function in the function class H that approximates the score well in our D δ p sense (see (6)), then the score-matching objective can learn this function using a number of samples that is independent of the domain size or the maximum value of the score.Notation. Fix a time t. For the purposes of this section, let q := q t be the distribution at time t, let σ := σ t be the smoothing level for time t, and let s := s t be the score function for time t. For m samples y i ∼ q 0 and z i ∼ N (0, σ 2 ), letx i = e -t y i + z i ∼ q t .We use E[f (x, y, z)] to denote the empirical expectation 1 m m i=1 f (x i , y i , z i ).We now state the score matching algorithm.Algorithm 1 Empirical score estimation for s Input: Distribution q 0 , y 1 , . . . , y m ∼ q 0 , set of hypothesis score function H = {s i }, smoothing level σ.1. Take m independent samples z i ∼ N (0, σ 2 I d ), and letx i = e -t y i + z i . 2. For each s ∈ H, let l(s) = 1 m m i=1 s(x i ) - -z i σ 2 2 2 3. Let ŝ = arg min s∈H l(s)Now we are ready to apply the finite function class to neural networks by a net argument. In particular, we first prove a version that uses a Frobenious norm to bound the weight vector. Lemma A.6. Let q 0 be a distribution with second moment m 2 2 . Let ϕ θ (•) be the fully connected neural network with ReLU activations parameterized by θ, with P total parameters and depth D. Let Θ > 1. Suppose there exists some weight vector θ * with ∥θ * ∥ F ≤ Θ such thatE x∼qt ∥ϕ θ * (x) -s t (x)∥ 2 ≤ δ score • δ train • ε 2 C • σ 2 tfor a sufficiently large constant C. By taking m i.i.d. samples from q 0 to train score s t , whenm > O (d + log 1 δtrain ) • P D ε 2 δ score • log max(m 2 , 1) • Θ δ train ,the empirical minimizer ϕ θ of the score matching objective used to estimate s t (over ϕ θ with ∥θ∥ F ≤ Θ) satisfies D δscore qt (ϕ θ , s t ) ≤ ε/σ t . with probability 1δ train .Proof. Per the notation discussion above, we set s = s t and σ = σ t . Note that σ < 1 since σ 2 t = 1e -2t . For any function f denotel(f, x, z) := f (x) - -z σ 2 2 ,we will show that for every θ with ∥ θ∥ F ≤ Θ such that D δscore q (ϕ θ , s) > ε/σ, with probability 1δ train , E l(ϕ θ , x, z)l(ϕ θ * , x, z) > 0 so that the empirical minimizer ϕ θ is guaranteed to haveD δscore q (ϕ θ , s) ≤ ε/σ.First, note that since the ReLU activation is contractive, the total Lipschitzness of ϕ θ is at most the product of the spectral norm of the weight matrices at each layer. For any θ, consider θ such that∥ θ -θ∥ F ≤ τ σDΘ D-1Let M 1 , . . . , M D be the weight matrices at each layer of the neural net ϕ θ , and let M 1 , . . . , M D be the corresponding matrices of ϕ θ .We now show that ϕ θ (x)ϕ θ (x) is small, using a hybrid argument. Define y i to be the output of a neural network with weight matrices M 1 , . . . , M i , M i+1 , . . . , M D on input x, so y 0 = ϕ θ (x) and y D = ϕ θ (x). Then we have∥y i -y i+1 ∥ ≤ ∥x∥ •   j≤i ∥M j ∥   • M i+1 -M i+1 •   j>i+1 M j   ≤ ∥x∥ Θ D-1 θ -θ F and so ϕ θ (x) -ϕ θ (x) 2 = ∥y 0 -y D ∥ ≤ D-1 i=0 ∥y i -y i+1 ∥ ≤ ∥x∥ DΘ D-1 θ -θ F ≤ ∥x∥ • τ /σ.Note that the dimensionality of θ is P . So, we can construct aτ σDΘ D-1 -net N over the set {θ : ∥θ∥ F ≤ Θ} of size O σDΘ D-1 τ P, so that for any θ with ∥θ∥ F ≤ Θ, there exists θ ∈ N with∥ϕ θ (x) -ϕ θ (x)∥ 2 ≤ (τ /σ) • ∥x∥ Let H = {ϕ θ : θ ∈ N }.Then, we have that for every θ with ∥θ∥ F ≤ Θ, there exists h ∈ H such thatE ∥h(x) -ϕ θ (x)∥ 2 ≤ (τ /σ) 2 • 1 m m i=1 ∥x i ∥ 2 (18)Now, choose any θ with ∥ θ∥ F ≤ Θ and D δscore q (ϕ θ , s) > ε/σ, and let h ∈ H satisfy the above for θ.We will set EQUATIONEQUATIONNow, by Corollary A.5, for our choice of m, with probability 1δ train /4 for every h ∈ H with D δscore/2 q (h, s) > ε/(2σ) simultaneously,E ∥h(x) - -z σ 2 ∥ 2 -∥s(x) - -z σ 2 ∥ 2 ≥ δ score ε 2 128σ 2By Markov's inequality, with probability 1δ train /4,E ∥ϕ θ * (x) -s(x)]∥ 2 ≤ δ score • ε 2 250σ 2By Lemma A.3, with probability 1δ train /4,E ⟨ϕ θ * (x) -s(x), s(x) - -z σ 2 ⟩ ≤ δ score ε 2 1000σ 2Plugging into (20) we have that with probability 1 -3δ train /4, for every h satisfyingD δscore/2 q ( h, s) > ε/(2σ), E l(ϕ θ , x, z) -l(ϕ θ * , x, z) ≥ δ score ε 2 128σ 2 - δ score • ε 2 250σ 2 -2 • δ score ε 2 1000σ 2 + 2⟨ϕ θ (x) -h(x), h(x) - -z σ 2 ⟩ ≥ δ score • ε 2 600 • σ 2 + 2⟨ϕ θ (x) -h(x), h(x) - -z σ 2 ⟩ (21)Now, we will show that D δscore/2 q ( h, s) > ε/(2σ), as well as bound the last term above, for every θ satisfying D δscore q (ϕ θ , s) > ε/σ and h ∈ H the rounding of ϕ θ .By the fact that q 0 has second moment m 2 2 , we have that with probability 1δ over x,∥x∥ ≤ m 2 √ δ + σ √ d + 2 log 1 δNow since D δscore q (ϕ θ , s) > ε/σ, and ∥ h(x)ϕ θ (x)∥ ≤ (τ /σ) • ∥x∥, we have, with probability at least δ score /2,∥ h(x) -s(x)∥ ≥ ∥ϕ θ (x) -s(x)∥ -∥ h(x) -ϕ θ (x)∥ ≥ ε/σ -(τ /σ) • m 2 δ score /2 + σ √ d + 2 log 2 δ score ≥ ε/(2σ)for our choice of τ as in (19). So, we have shown that D δscore/2 q ( h, s) > ε/(2σ).Finally, we bound the last term in (21) above. We have by ( 18) and a union bound, with probability 1δ train /8,E ∥ h(x) -ϕ θ (x)∥ 2 ≲ (τ /σ) 2 • m • m 2 2 δ train + σ 2 d + log m δ train ≲ (τ /σ) 2 • m • m 2 2 δ train + d + log m δ train since σ < 1 ≲ C ′2 ε 4 δ 2 score σ 2 Θ 2D • 1 m•max(m 2 2 ,1) δtrain + d + log m δtrain by (19)Similarly, with probability 1δ train /8,E ∥ h(x) - -z σ 2 ∥ 2 ≲ Θ D • m • m 2 2 δ train + σ 2 d + log m δ train + 1 σ 2 d + log m δ trainSo, putting the above together, with probability 1δ train /4,E ∥ h(x) -ϕ θ (x)∥ 2 • E ∥ h(x) - -z σ 2 ∥ 2 ≲ C ′2 ε 4 δ 2 score σ 2 1 + 1 σ 2 ≲ C ′2 ε 4 δ 2 score σ 4 since σ < 1So, with probability 1δ train /4, for some small enough constant C ′ ,E ⟨ϕ θ (x) -h(x), h(x) - -z σ 2 ⟩ ≥ -E ∥ h(x) -ϕ θ (x)∥ 2 • E ∥ h(x) - -z σ 2 ∥ 2 ≥ - δ score ε 2 2000 • σ 2So finally, combining with (21), we have with probability1 -δ train E l(ϕ θ , x, z) -l(ϕ θ * , x, z) ≥ δ score • ε 2 1000 • σ 2 > 0So, we have shown that with probability 1-δ train , for every θ with ∥ θ∥ F ≤ Θ and D δscore q (ϕ θ , s) > ε/σ, E l(ϕ θ , x, z)l(ϕ θ * , x, z) > 0 so that the empirical minimizer ϕ θ is guaranteed to haveD δscore q (ϕ θ , s) ≤ ε/σ.Then we have our main lemma as a direct corollary:Proof of Lemma A.1. For every θ with ∥ θ∥ ∞ ≤ Θ, we have∥ θ∥ F ≤ √ P ∥ θ∥ ∞ ≤ √ P Θ.Then, by applying Lemma A.6 directly, we prove the lemma.In this section, we show that diffusion models can converge to the true distribution without necessarily adhering to an L 2 bound on the score estimation error. A high probability accuracy of the score is sufficient.In order to simulate the reverse process of (1) in an actual algorithm, the time was discretized into N steps. The k-th step ends at time t k , satisfying 0≤ t 0 < t 1 < • • • < t N = T -γ.The algorithm stops at t N and outputs the final state x T -t N .To analyze the reverse process run under different levels of idealness, we consider these four specific path measures over the path space C([0, Tγ]; R d ):• Let Q be the measure for the process thatdx T -t = (x T -t + 2s T -t (x T -t )) dt + √ 2 dB t , x T ∼ q T .• Let Q dis be the measure for the process that for t∈ [t k , t k+1 ], dx T -t = (x T -t + 2s T -t k (x T -t k )) dt + √ 2 dB t , x T ∼ q T .• Let Q be the measure for the process that for t∈ [t k , t k+1 ], dx T -t = (x T -t + 2 s T -t k (x T -t k )) dt + √ 2 dB t , x T ∼ q T .• Let Q be the measure for the process that for t∈ [t k , t k+1 ], dx T -t = (x T -t + 2 s T -t k (x T -t k )) dt + √ 2 dB t , x T ∼ N (0, I d ).To summarize, Q represents the perfect reverse process of (1), Q dis is the discretized version of Q, Q runs Q dis with an estimated score, and Q starts Q at N (0, I d ) -effectively the actual implementable reverse process.Recent works have shown that under the assumption that the estimated score function is close to the real score function in L 2 , then the output of Q will approximate the true distribution closely. Our next theorem shows that this assumption is in fact not required, and it shows that our score assumption can be easily integrated in a black-box way to achieve similar results.Lemma B.1 (Score Estimation guarantee). Consider an arbitrary sequence of discretization times0 = t 0 < t 1 < • • • < t N = T -γ, and let σ t := √ 1 -e -2t. Assume that for each k ∈ {0, . . . , N -1}, the following holds:D δ/N q T -t k ( s T -t k , s T -t k ) ≤ ε σ T -t k .Then, we haveP Q N -1 k=0 ∥ s T -t k (x T -t k ) -s T -t k (x T -t k )∥ 2 2 (t k+1 -t k ) ≤ ε 2 T + log 1 γ ≥ 1 -δ.Proof. Since random variable x T -t k follows distribution q T -t k under Q, for each k ∈ {0, . . . , N -1}, we haveP Q ∥ s T -t k (x T -t k ) -s T -t k (x T -t k )∥ ≤ ε √ 1 -e -2(T -t k ) ≥ 1 - δ N .Using a union bound over all N different σ values, it follows that with probability at least 1δ over Q, the inequality∥ s T -t k (x T -t k ) -s T -t k (x T -t k )∥ 2 2 ≤ ε 2 1 -e -2(T -t k ) .is satisfied for every k ∈ {0, . . . , N -1}. Under this condition, we haveN -1 k=0 ∥ s T -t k (x T -t k ) -s T -t k (x T -t k )∥ 2 2 (t k+1 -t k ) ≤ N -1 k=0 ε 2 1 -e -2(T -t k ) (t k+1 -t k ) ≤ N -1 k=0 t k+1 t k ε 2 1 -e -2(T -t k ) dt ≤ T -γ 0 ε 2 1 -e -2(T -t k ) dt ≤ε 2 T + log 1 γ .Hence, we find thatP Q N -1 k=0 ∥ s T -t k (x T -t k ) -s T -t k (x T -t k )∥ 2 2 (t k+1 -t k ) ≤ ε 2 T + log 1 γ ≥ 1 -δ.Lemma B.2 (Score estimation error to TV). Let q be an arbitrary distribution. If the score estimation satisfies thatEQUATION)then the output distribution p T -t N of Q satisfies TV(q γ , p T -t N ) ≲ δ + ε + TV(Q, Q dis ) + TV(q T , N (0, I d )).Proof. We will start by bounding the TV distance between Q dis and Q. We will proceed by defining Q and arguing that both TV(Q dis , Q) and TV( Q, Q) are small. By the triangle inequality, this will imply that Q and Q are close in TV distance.Defining Q. For k ∈ {0, . . . , N -1}, consider eventE k := k i=0 ∥ s T -ti (x T -ti ) -s T -ti (x T -ti )∥ 2 2 (t i+1 -t i ) ≤ ε 2 ,which represents that the accumulated score estimation error along the path is at most ε 2 for a discretized diffusion process.Given E k , we define a version of Q dis that is forced to have a bounded score estimation error. Let Q over C((0, T ], R d ) be the law of a modified reverse process initialized at x T ∼ q T , and for each tEQUATIONwheres T -t k (x T -t k ) := s T -t k (x T -t k ) E k holds, s T -t k (x T -t k ) E k doesn't hold.This SDE guarantees that once the accumulated score error exceeds ε 2 score (E k fails to hold), we switch from the true score to the estimated score. Therefore, we have that the following inequality always holds:EQUATION)Q dis and Q are close. By ( 22), we haveP Qdis [E 0 ∧ • • • ∧ E N -1 ] = P Qdis [E N -1 ] ≥ P Q [E N -1 ] -TV(Q, Q dis ) ≥ 1 -δ -TV(Q, Q dis ),Note that when a path(x T -t ) t∈[0,t N ] satisfies E 0 ∧ • • • ∧ E N -1, its probability under Q is at least its probability under Q dis . Therefore, we haveTV(Q dis , Q) ≲ δ + TV(Q, Q dis ).Q and Q are close. Inspired by [CCL + 23b], we utilize Girsanov's theorem (see Theorem F.8) to help bound this distance. Defineb r := √ 2( s T -t k (x T -t k ) -s T -t k (x T -t k )),where k is index such that r ∈ [t k , t k+1 ). We apply the Girsanov's theorem to ( Q, (b r )). By Eq. ( 24), we havet N 0 ∥b r ∥ 2 2 dr ≤ N -1 k=0 ∥ √ 2( s T -t k (x T -t k ) -s T -t k (x T -t k ))∥ 2 2 (t k+1 -t k ) ≤ 2ε 2 < ∞.This satisfies Novikov's condition and tells us that forE(L) t = exp t 0 b r dB r - 1 2 t 0 ∥b r ∥ 2 2 dr , under measure Q ′ := E(L) t N Q, there exists a Brownian motion ( B t ) t∈[0,t N ] such that B t = B t - t 0 b r dr,and thus for t∈ [t k , t k+1 ), d B t = dB t + √ 2( s T -t k (x T -t k ) -s T -t k (x T -t k )) dt.Plug this into (23) and we have that for t∈ [t k , t k+1 ) dx T -t = -(x T -t + 2 s T -t k (x T -t k )) dt + √ 2 d B t , x T ∼ q T .This equation depicts the distribution of x, and this exactly matches the definition of Q. Therefore,Q = Q ′ = E(L) t N Q, and we have KL Q Q = E Q ln d Q dQ = E Q ln E(L) t N .Then by using (24), we haveE Q ln E(L) t N ≲ E Q N -1 k=0 ∥ s T -t k (x T -t k ) -s T -t k (x T -t k )∥ 2 2 (t k+1 -t k ) ≲ ε 2 .Therefore, we can apply Pinsker's inequality and getTV( Q, Q) ≤ KL Q Q ≲ ε.Putting things together. Using the data processing inequality, we haveTV(Q, Q) ≤ TV(q T , N (0, I d )).Combining these results, we haveTV(Q, Q) ≤ TV(Q, Q dis ) + TV(Q dis , Q) + TV( Q, Q) + TV(Q, Q) ≲ δ + ε + TV(Q, Q dis ) + TV(q T , N (0, I d )). Since q γ is the distribution for x T -t N under Q and p T -t N is the distribution for x T -t N under Q, we have TV(q γ , p T -t N ) ≤ TV(Q, Q) ≲ δ + ε + TV(Q, Q dis ) + TV(q T , N (0, I d )).Lemma B.3. Consider an arbitrary sequence of discretization times0 = t 0 < t 1 < • • • < t N = T -γ.Assume that for each k ∈ {0, . . . , N -1}, the following holds:D δ/N q T -t k ( s T -t k , s T -t k ) ≤ ε σ T -t k • 1 T + log 1 γ Then, the output distribution q T -t N satisfies TV( q T -t N , q T -t N ) ≲ δ + ε + TV(Q, Q dis ) + TV(q T , N (0, I d )).Proof. Follows by Lemma B.1 and Lemma B.2.The next two lemmas from existing works show that the discretization error, TV(Q, Q dis ), is relatively small. Furthermore, as T increases, q T converges exponentially towards N (0, I d ).Lemma B.4 (Discretization Error, Corollary 1 and eq. ( 17) in [BBDD24] ). For any T ≥ 1, γ < 1 and N ≥ log(1/γ), there exists a sequence of N discretization times such thatTV(Q, Q dis ) ≲ d N T + log 1 γ .Lemma B.5 (TV between true Gaussian and q T for large T , Proposition 4 in [BBDD24] ). Let q be a distribution with a finite second moment of m 2 2 . Then, for T ≥ 1 we haveTV(q T , N (0, I d )) ≲ ( √ d + m 2 )e -T .Combining Lemma B.4 and Lemma B.5 with Lemma B.3, we have the following result:Corollary B.6. Let q be a distribution with finite second moment m 2 2 . For any T ≥ 1, γ < 1 and N ≥ log(1/γ), there exists a sequence of discretization times 0 = t 0 < t 1 < • • • < t N = Tγ such that if the following holds for each k ∈ {0, . . . , N -1}:D δ/N q T -t k ( s T -t k , s T -t k ) ≤ ε σ T -t k ,then there exists a sequence of N discretization times such thatTV(q γ , p T -t N ) ≲ δ + ε T + log 1 γ + d N T + log 1 γ + ( √ d + m 2 )e -T .This implies our main theorem of this section as a corollary. Theorem B.7. Let q be a distribution with finite second moment m 2 2 . For any γ > 0, there existN = O( d ε 2 +δ 2 log 2 d+m2 γ ) discretization times 0 = t 0 < t 1 < • • • < t N < T such that if the following holds for every k ∈ {0, . . . , N -1}, D δ/N q T -t k ( s T -t k , s T -t k ) ≤ ε σ T -t k then DDPM can produce a sample from a distribution that is within O(δ + ε log ((d + m 2 )/γ)) in TV distance of q γ in N steps. Proof. By setting T = log( √ d+m2 ε+δ ) and N = d(T +log(1/γ)) 2 ε 2 +δ 2in Corollary B.6, we haveTV(q γ , p T -t N ) = O δ + ε log d + m 2 γ .Furthermore, we present our theorem under the case when m 2 lies between 1/ poly(d) and poly(d) to provide a clearer illustration. Lemma 1.3. Let q be a distribution over R d with second moment m 2 2 between 1/poly(d) and poly(d). For any γ > 0, there exist N = O( d ε 2 +δ 2 log 2 1 γ ) discretization times 0 = t 0 < t 1 < • • • < t N < T such that if the following holds for every k ∈ {0, . . . , N -1}:D δ/N q T -t k ( s T -t k , s T -t k ) ≤ ε σ T -t k then DDPM can sample from a distribution that is within O(δ + ε log (d/γ)) in TV distance to q γ in N steps.In this section, we present our main theorem that combines our score estimation result in the new (6) sense with prior sampling results (from [BBDD24] ) to show that the score can be learned using a number of samples scaling polylogarithmically in 1 γ , where γ is the desired sampling accuracy. Lemma C.1. Let q 0 be a distribution with second moment m 2 2 . Let ϕ θ (•) be the fully connected neural network with ReLU activations parameterized by θ, with P total parameters and depth D.EQUATIONThen, if we take m > ON (d+log 1 δ train )•P D ε 2 δscore• log max(m2,1)•Θ δtrain samples, then with probability 1δ train , each score ŝT -t k learned by score matching satisfiesD δscore/N q T -t k (ŝ T -t k , s T -t k ) ≤ ε/σ T -t k .Proof. Note that for each t k , q T -t k is a σ T -t k -smoothed distribution. Therefore, we can use Lemma A.1 by taking δ train /N into δ train and taking δ score /N into δ score . We have that for each t k , with probability 1δ train /N the following holds:P x∼q T -t k [∥ŝ T -t k (x) -s T -t k (x)∥ ≤ ε/σ T -t k ] ≥ 1 -δ score /N.By a union bound over all the steps, we conclude the proposed statement. Now we present our main theorem. Theorem C.2 (Main Theorem, Full Version). Let q be a distribution of R d with second moment m 2 2 . Let ϕ θ (•) be the fully connected neural network with ReLU activations parameterized by θ, with P total parameters and depth D. Let Θ > 1. For any γ > 0, there existN = O( d ε 2 +δ 2 log 2 m2+1/m2 γ ) discretization times 0 = t 0 < • • • < t N < T such that if for each t k , there exists some weight vector θ * with ∥θ * ∥ ∞ ≤ Θ such that E x∼q T -t k ∥ϕ θ * (x) -s T -t k (x)∥ 2 2 ≤ δ • ε 3 CN 2 σ 2 T -t k • 1 log d+m2+1/m2γ for sufficiently large constant C, then consider the score functions trained fromm > O N (d + log 1 δ ) • P D ε ′3 • log max(m 2 , 1) • Θ δ • log m 2 + 1/m 2 γ i.i.d. samples of q, with 1δ probability, DDPM can sample from a distribution ε-close in TV to a distribution γm 2 -close in 2-Wasserstein to q in N steps.Proof. Note that for an arbitrary t > 0, the 2-Wasserstein distance between q and q t is bounded byO(tm 2 + √ td). Therefore, by choosing t N = T -min(γ, γ 2 m 2 2 /d), Theorem B.7 shows that by choosing N = O( d ε ′2 +δ 2 log 2 d+m2 min(γ,γ 2 m 2 2 /d) ), we only need D ε/N q T -t k ( s T -t k , s T -t k ) ≤ ε ′ σ T -t k log d+m2 min(γ,γ 2 m 2 2 /d)then DDPM can produce a sample from a distribution within O(ε ′ ) in TV distance to a distribution γm 2 -close in 2-Wasserstein to q in N steps. Note thatlog d + m 2 min(γ, γ 2 m 2 2 /d) ≲ log d + m 2 + 1/m 2 γ .Therefore, we only need to take O( d ε ′ 2 +δ 2 log 2 m2+1/m2 γ ) steps. Therefore, to achieve this, we setδ train = δ, δ score = ε ′ , and ε = ε ′ / log d+m2+1/m2 γ ≲ ε ′ / log d+m2 min(γ,γ 2 m 2 2 /d) in Lemma C.1. This gives us the result that with m > O N (d + log 1 δ ) • P D ε ′3 • log max(m 2 , 1) • Θ δ • log m 2 + 1/m 2 γsamples, we can satisfy the score requirement given the assumption in the statement.For cleaner statement, we present this theorem under the case when m 2 lies between 1/ poly(d) and poly(d) and achieving training success probability of 99%. This gives the quantitative version of Theorem 1.2. Theorem C.3 (Main Theorem, Quantitative Version). Let q be a distribution of R d with second moment m 2 2 . Let ϕ θ (•) be the fully connected neural network with ReLU activations parameterized by θ, with P total parameters and depth D. Let Θ > 1. For any γ > 0, there exist N = O(d log 2 1 γ ) discretization times 0 = t 0 < • • • < t N < T such that if for each t k , there exists some weight vector θ * with ∥θ * ∥ ∞ ≤ Θ such thatE x∼q T -t k ∥ϕ θ * (x) -s T -t k (x)∥ 2 2 ≤ δ • ε 3 CN 2 σ 2 T -t k log d γfor a sufficiently large constant C, then consider the score functions trained fromm ≥ O d 2 P D ε 3 • log Θ • log 3 1 γ i.i.d. samples of q. With 99% probability, DDPM using these score functions can sample from a distribution ε-close in TV to a distribution γm 2 -close in 2-Wasserstein to q in N steps.In this section, we give proofs of the hardness of the examples we mention in Section 4. Lemma 4.1. Let R be sufficiently larger than σ. Let p 1 be the distribution (1η)N (0, σ 2 ) + ηN (-R, σ 2 ) with corresponding score function s 1 , and let p 2 be (1η)N (0, σ 2 ) + ηN (R, σ 2 ) with score s 2 , such that η = ε 2 σ 2 R 2 . Then, given m < R 2 ε 2 σ 2 samples from either distribution, it is impossible to distinguish between p 1 and p 2 with probability larger than 1/2 + o m (1). But,E x∼p1 ∥s 1 (x) -s 2 (x)∥ 2 ≳ ε 2 σ 2 and E x∼p2 ∥s 1 (x) -s 2 (x)∥ 2 ≳ ε 2 σ 2 .Proof.TV(p 1 , p 2 ) ≳ ηSo, it is impossible to distinguish between p 1 and p 2 with fewer than O 1 η samples with probability 1/2 + o m (1).The score L 2 bound follows from calculation. Lemma 4.2. Let S be sufficiently large. Consider the distribution p = ηN (0, σ 2 ) + (1η)N (S, σ 2 )for η = Se -S 2 2 +10 √ log m•S 10 √ log m, and let s be its score function. Given m samples from the standard Gaussian p * = N (0, σ 2 ) with score function s * , with probability at least 1 -1 poly(m) ,E ∥ s(x) -s * (x)∥ 2 ≤ 1 σ 2 e -O(S √ log m) but E x∼p * ∥ s(x) -s * (x)∥ 2 ≳ S 2 mσ 4 .Proof. Let X 1 , . . . , X m ∼ p * be the m samples from N (0, σ 2 ). With probability at least 1 -1 poly(m) , every X i ≤ 2σ √ log m. Now, the score function of the mixture p is given bys(x) = -x σ 2 -x-S σ 2 1-η η e -S 2 2 +Sx 1 + 1-η η e -S 2 2 +Sx For x ≤ 2 √ log m, s(x) = - x σ 2 1 + e -O(S √ log m) S + 1 σ 2 e -O(S √ log m)So,E ∥ s(x) -s * (x)∥ 2 ≤ 1 σ 2 e -O(S √ log m)On the other hand,E x∼p * ∥ s(x) -s * (x)∥ 2 ≳ S 2 mσ 4 E Discussion of [BMR20]Here, we present a brief, self-contained discussion of the prior work [BMR20] . The main result of that work on score estimation is as follows. Theorem E.1 (Proposition 9 of [BMR20], Restated). Let F be a class of R d -valued functions, all of with are L 2 -Lipschitz, with values supported on the Euclidean ball with radius R, and containing uniformly good approximations of the true score s t on this ball. Given n samples from q t , if we let s t be the empirical minimizer of the score-matching loss, then with probability at least 1δ,E x∼qt ∥ s t (x) -s t (x)∥ 2 ≲ (LR + B) 2 log 2 n • R 2 n (F) + d log log n + log 1 δ nHere, B is a bound on ∥s t (0)∥, and R n (F) is the Rademacher complexity of F over n samples.In the setting we consider, for the class of neural networks with weight vector θ such that ∥θ∥ ∞ ≤ Θ with P parameters and depth D, it was shown in [Sel24] that Given n samples from q t , if we let s t be the empirical minimizer of the score-matching loss, then with probability 1δ,R n (F) ≲ R √ d √ n (Θ √ P ) D • √ D Moreover,E x∼qt ∥ s t (x) -ϕ θ * (x)∥ 2 ≤ O ε 2 σ 2 for n > O d 5/2 R 3 σ 3 t ε 2 Θ 2 P D √ D log 1 δ .To learn score approximations in L 2 for all the N relevant timesteps in order to achieve TV error ε and Wasserstein error γ • R, this implies a sample complexity bound ofO d 5/2 γ 3 ε 2 (Θ 2 P ) D √ D log N δ = O d 5/2 γ 3 ε 2 (Θ 2 P ) D √ D log 1 δ for our final choice of N .Lemma F.1 (From [GLP23] ). Let f be an arbitrary distribution on R d , and let f Σ be the Σ-smoothed version of f . That is,EQUATION], restated). Let x be a mean-zero random vector in R d that is Σsubgaussian. That is, for every vector v, E e λ⟨x,v⟩ ≤ e λ 2 v T Σv/2Then, with probability 1δ, ∥x∥ ≲ Tr(Σ) + 2∥Σ∥ log 1 δ Lemma F.3. For s Σ the score function of an Σ-smoothed distribution where Σ = σ 2 I, we have that v T s Σ (x) is O(1/σ 2 )-subgaussian, when x ∼ f Σ and ∥v∥ = 1.Proof. We have by Lemma F.1 that sΣ (x) = E ZΣ|x Σ -1 Z Σ So, E x∼fΣ (v T s Σ (x)) k = E x∼fΣ E ZΣ|x v T Σ -1 Z Σ k ≤ E ZΣ (v T Σ -1 Z Σ ) k ≤ k k/2 σ k since v T Z Σ ∼ N (0, σ 2 )The claim follows.Lemma F.4. Let Σ = σ 2 I, and let x ∼ f Σ . We have that with probability 1δ,∥s Σ (x)∥ 2 ≲ d + log 1 δ σ 2Proof. Follows from Lemmas F.3 and F.2.Lemma F.5. For z ∼ N (0, σ 2 I d ), with probability 1δ,z σ 2 ≲ d + log 1 δ σProof. Note that ∥z∥ 2 is chi-square, so that we have for any 0 ≤ λ < σ 2 /2,E z e λ∥ ∥z∥ σ 2 ∥ 2 ≤ 1 (1 -2(λ/σ 2 )) d/2The claim then follows by the Chernoff bound.Lemma F.6. For x ∼ f Σ , with probability 1δ,E ZΣ|x ∥Z Σ ∥ σ 2 ≲ d + log 1 δ σ Proof. Since Z Σ ∼ N (0, σ 2 I d ) so that ∥Z Σ ∥ 2 is chi-square, we have that for any 0 ≤ λ < σ 2 /2, by Jensen's inequality, E x∼fΣ e λ E Z Σ |x ∥Z Σ ∥ σ 2 2 ≤ E ZΣ e λ ∥Z Σ ∥ 2 σ 4 ≤ 1 (1 -2(λ/σ 2 )) d/2The claim then follows by the Chernoff bound. That is, setting λ = σ 2 /4, for any t > 0,P x∼fΣ E ZΣ|x ∥Z Σ ∥ σ 2 2 ≥ t ≤ E x∼fΣ e λ E Z Σ |x ∥Z Σ ∥ σ 2 2 e λt ≤ 2 d/2 e -tσ 2 /4 = 2 d ln 2 2 -tσ 2 4 For t = O d+log 1 δ σ 2, this is less than δ.). Let X be a non-negative random variable such that for every t ≥ 0, P[X ≥ t] ≤ exp(-λt) for some constant λ ≥ 0. Then, for K ≥ 0,E[X|X ≥ K] ≲ E[X] + 1 λ log 1 P[X ≥ K]Proof. Let p := P[X ≥ K] and denote the distribution of X as P. Consider the sequence of iid samples {X i } i≥0 sampled from P. Let T be the first index i, where X i ≥ K. Then the distribution of X T is the conditional distribution of X given X ≥ K. For any m > 0, Justification: Yes, the main claims are all reflected in the scope and contributions, as discussed in the paper.X T ≤ k≥1 1 ((k -1)m < T ≤ km) sup (k-1)m<i≤km X i ≤ k≥1 1 ((k -1)m < T ) sup (k-1)m<i≤km X i Now, 1 ((k -1)m < T ) and sup (k-1)m<i≤km X i are independent since 1 ((k -1)m < T ) depends only on {X i } i∈[1,(k-1)m] . Thus, E[X|X ≥ K] = E[X T ] ≤ k≥1 E [1 ((k -1)m < T )] E sup (k-1)m<i≤km X i ≲ (1 -p) (k-1)m E[X] + log m λ ≲ 1 1 -(1 -p) m • E[X] + log m λ Choosing m = 1 p so that (1 -p) m ≤ 1 e gives the claim. Theorem F.8 (Girsanov's theorem). For t ∈ [0, T ], let L t = t 0 b s dB s where B is a Q-Brownian motion. Assume Novikov's condition is satisfied: E Q exp 1 2 T 0 ∥b s ∥ 2 2 ds < ∞. Then E(L) t := exp t 0 b s dB s - 1 2 t 0 ∥b s ∥ 2 2 ds is a Q-martingale andGuidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Justification: There are no assets that are used in this work.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 


Decision: Thank you for your valuable contribution to Neurips and the ML community. Your submitted paper has undergone a rigorous review process, and I have carefully read and considered the feedback provided by the reviewers.

The paper analyzes the sample complexity of training a score-based diffusion model. The sample complexity is improved with respect to certain parameters by avoiding an L^2 accuracy on the score function as done in the previous work. Overall, the paper received mostly positive response from the reviewers. Some issues raised by the reviewers were successfully addressed in the rebuttal. These issues include (i) significance of the main contribution,  (ii) presentation issues (moving Theorem C.3 to the main text) (iii) clearly positioning the result relative to prior-work.

Given this positive assessment, I am willing to recommend the acceptance of your paper for publication.

I would like to remind you to carefully review the reviewer feedback and the resulting discussion. While most reviews were positive, the reviewers have offered valuable suggestions that can further strengthen the quality of the paper. In particular, there were valuable suggestions to reorganize the theorems. Please take another careful look a the 'weaknesses' section of each reviewer comment and the issues (i)-(iii) listed above. I encourage you to use this feedback to make any necessary improvements and refinements before submitting the final version of your paper.

Once again, thank you for submitting your work to Neurips.

Best,

Reviews: review: paper_summary: paper_summary: In this paper, the authors studied the sample complexity of training diffusion models. By using a sufficiently expressive neural network, the authors showed an exponential improvement in the dependence on Wasserstein error and network width, which is expressed as $\tilde{O}(d^2PD\log\Theta \log^3(1/\gamma)/\varepsilon^3)$. This bound has a better polynomial dependence on the dimension $d$ and $P$, a better exponential dependence on $\Theta, \gamma$ and $D$ but a worse polynomial dependence on $\varepsilon$ as a cost.
strength_weakness: strength_weakness: This contribution of this paper seems not to be enough for an accept of a top tier machine learning conference. As we know, the TV error or Wasserstein error of learning diffusion models mainly lies in the discretization error caused by solving backward ODE (or SDE) through Euler Maruyama method, as well as the score estimation error. The discretization error is dominated by the latter error according to Chen et al.'s work. In this paper, the authors mainly studied the score estimation error. My biggest concern is that inserting a better generalization bound of score estimation (with regard to polynomial dimensional dependence) is not novel enough. For more questions, please refer to the next section.
questions: questions: 1. For the assumption A2, I think you can directly put the result of Theorem C.3 into the main text since the function approximation is also important, and the statement like "sufficiently small" doesn't seem to be strict. 
2. Please provide some explanations on the novelty of the sample complexity theory, other than an insert of polynomial dimension learning error rate of expressive neural networks. 
3. The work focuses on DDPM. However, in the original work of Song et al, they used VE (variance exploding) for consistency training. Is it possible for the sample complexity bound in the paper adapted to the VE case?
limitations: limitations: There is not potential societal impact of this work since it is a completely theoretical work.
paper_summary: paper_summary: The paper studies the sample complexity of training diffusion models. The bound derived in the paper is exponentially better than the previous results. The paper also discusses the difficulty of learning the score function in $L^2$.
strength_weakness: strength_weakness: 1. The major concern is the presentation of this paper. I understand the results are important. However, the authors should clearly position this work in the literature. I suggest the authors provide a table that compares the sample complexity to the ones in prior work. In particular, the authors should discuss the improvement in terms of both the TV bound and the Wasserstein results. 
2. I notice the authors use BMR20 as a benchmark in Section 1.1. However, there are many better sample complexity results on diffusion models since that work. I suggest the authors carefully state how this work differs from those results. Also, I suggest the authors emphasize the main technical contributions in the proof instead of stating all the steps one by one. In particular, which step and what technique lead to the exponential improvement?
3. The importance of Section 4 is not clear. Recent work has explored the learning score function in $L^2$; see [1-5]. All the work listed shows learning the score in $L^2$ is possible, and some of them show the minimax optimal rate. Specifically, learning the score function for an arbitrary distribution can be hard. However, learning the denoised score function during the forward process can be much easier. Therefore, I suggest the authors clarify why the examples in Section 4 can be interesting.  

[1] Chen, Minshuo, et al. "Score approximation, estimation and distribution recovery of diffusion models on low-dimensional data." International Conference on Machine Learning. PMLR, 2023.

[2] Han, Yinbin, Meisam Razaviyayn, and Renyuan Xu. "Neural network-based score estimation in diffusion models: Optimization and generalization." arXiv preprint arXiv:2401.15604 (2024).

[3] Wibisono, Andre, Yihong Wu, and Kaylee Yingxi Yang. "Optimal score estimation via empirical bayes smoothing." arXiv preprint arXiv:2402.07747 (2024).

[4] Zhang, Kaihong, et al. "Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions." arXiv preprint arXiv:2402.15602 (2024).

[5] Oko, Kazusato, Shunta Akiyama, and Taiji Suzuki. "Diffusion models are minimax optimal distribution estimators." International Conference on Machine Learning. PMLR, 2023.
questions: questions: See weaknesses.
limitations: limitations: NA
paper_summary: paper_summary: In this paper, the authors analyze the sample complexity of training a score-based diffusion model. They show that, with a sufficiently expressive neural network,  \tilde O(d^2 P D log \Theta \log^3 \frac{1}{\gamma} / \epsilon^3) samples are needed to learn an accurate diffusion model. Compared to the existing result, their bound has exponentially better dependence on \Theta, \gamma and D, and a better polynomial dependence on d and P, at the cost of a worse polynomial dependence in \epsilon.
strength_weakness: strength_weakness: 1. Generally, this paper discusses the training sample complexity of a score-based diffusion model. The assumption is somehow strong, e.g., the neural networks can represent the score. Besides, the author do not include the optimization error in the analyses.
questions: questions: 1. As the bound in lemma 1.4 is with probability and in lemma 1.3, the requirement must hold for all N,  what if we make sampling step N \to \infty in Theorem 1.2? Does the bound in lemma 4 for each t independent or is controlled by the same stochasticity?

2. What is the quantitive requirement on \mathcal{F} in Assumption 2? What does the "sufficiently small" mean?

3.Why is it required to constraint the functions represented by a fully connected neural network with ReLU activations and depth D, with P parameters, each bounded by \Theta? Is it possible to be extended to other function classes?
limitations: limitations: Not applicable.
paper_summary: paper_summary: This paper investigates theoretical guarantees for the performance of diffusion models. More precisely, while the previous works have mainly focused on the iteration complexity by assuming to have access to an accurate diffusion model, this paper targets the question of the sample complexity for learning an accurate diffusion model (score function). The main contribution is an exponential improvement of the existing bound with respect to Wasserstein error and depth.
strength_weakness: strength_weakness: - The impact of the results obtained and the scope of the theoretical insights are limited. I am not sure that the results of this paper bring concrete new implications/understandings for diffusion models.

- Some parts of the paper are not clear enough (see Questions section)
questions: questions: 1. Can the authors develop more why and when the dependence on $\theta$, $\gamma$, $D$ and $P$ is more important than the dependence on $\epsilon$? Can a numerical estimate be provided here?


2. Can the authors discuss assumption A2 in more detail? Is it true that the assumption implies $\inf_{f} E_{X \sim q_t} [||f(x) - s_t(x)||_2]=0$? Does this assumption implicitly assume that the score function is "simple" enough to belong to the family $\mathcal{F}$? Does it lead to any limitation in practice?  

3. What are $\gamma$ and $R$ in line 41? They seem to be undefined up to that point.

4.  For clarity, it may be better to replace $z_i$ with $z_{i,t}$ in line 54 to show that such samples are distinct and i.i.d. for each sample and time index.

5. The paper and the considered setting 1.1. depend strongly on the DDPM algorithm. To make the paper self-contained, it is necessary to describe this algorithm.

6. In Setting 1.1, does $P$ denote the number of parameters per layer?
limitations: limitations: Not Applicable.

Comments: comment: Thank you for your reply! We respond to your questions below:

1. Our goal is to understand the sample complexity of using the score matching objective to approximate the score by a neural network for diffusion, because that is the process people are using successfully in practice.  There are a couple questions you might be asking, and we're not sure which:
    - Why study this particular family of neural networks (relu, fully connected, etc.)?  Our techniques are pretty general, and could be applied to any continuous neural network with Lipschitz activation.  This just seemed like the simplest setting to describe (of course we need some bound on the complexity: bigger, more complex networks need more samples).
    - Why would we expect neural networks to be able to represent the score accurately?  We think this is somewhat orthogonal to the sample complexity question: if they can't represent the score, then diffusion isn't going to work no matter how many samples you have.  In practice, neural networks do seem to be able to represent scores accurately.  Why that happens is a very interesting question, but we view it as more a question about *data* than about neural networks or optimization.  (Analogous to: images tend to be sparse in the wavelet basis.)  It's trivial to construct synthetic data that cannot be represented by a neural network (or any other compact representation).

2. **Choice of $N$**.
There are competing factors: $N$ needs to be large enough for the discretization error to be small, but the sample complexity and sampling time degrade with increasing $N$.  As we specify in Lemma 1.3, the sweet spot is $N = \tilde{O}(\frac{d}{\varepsilon^2 + \delta^2} \log^2 \frac{1}{\gamma})$.

3. **Optimization error.**  
We did assume that the global minimum can be achieved, as specified in Setting 1.1. This is a standard setting in the line of works that aim to bound sample complexity. While analyzing the optimization process is indeed interesting, it is also extremely challenging. Our focus is on determining how many samples are needed for the minimizer of the neural network to be effective in the diffusion process.
    
    In practice, SGD has been shown to approximate the global minimum well. Our analysis can easily extend to handle approximation error in the optimization. Given an approximate minimizer with error comparable to the bound we give on line 712, the same analysis would give the same result.

    We can clarify the wording "trained from" to specify that we mean the ERM of the score matching objective on the given samples.
Thank you for your reply!

1. I am still doubt about the assumption that the score function can be effectively. As the authors constraint the functions represented by a fully connected neural network with ReLU activations and depth D, with P parameters, each bounded by \Theta. The question now becomes whether this family is strong enough to represent the score of the complex dynamics? What is the influence of these network parameters other than the representative ability?

2. As confirmed by the authors, I am a little confused. If N could not be too large, so how do we bound the discretizaiton error?  The authors should discuss this more sufficiently, and especially when jump from the individual bound to the union bound. 

3. Note that the authors did not discuss the optimization error, it is really strange to use the description "trained from". Does the authors assume the global minimum can be achieved?
Thank you for your detailed response. I have raised the score. However, the presentation should still be improved before publication.
Thanks for the response and the numerical estimate. Apart from the presentation, which I believe will be improved by the authors, I think the main debate is about the importance of the paper, as I mentioned in the first weakness and discussed in more detail by other reviewers. Unfortunately, I am not in a position to make an informed judgment, but I think the paper contains interesting results and I maintain my rating.