Improved Sample Complexity Bounds for Diffusion Model Training
Authors: Shivam Gupta
Aditya Parulekar
Eric Price
Zhiyang Xun
Venue: NeurIPS 2024 poster (2024)
Keywords: Diffusion Models
Learning Theory
Sample Complexity
Primary area: learning_theory

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.

Improved Sample Complexity Bounds for Diffusion Model Training
Shivam Gupta
Aditya Parulekar UT Austin adityaupēcs utexas. edu
Eric Price UT Austin
UT Austin
shivanguptaauuteass.cu
ecprice0cs utexas edu
Zhiyang Xun
UT Austin zxun@cs wtw.aa.eeee.. edu
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, number of recent works [CCL+*3b, 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 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 Wasserstein error and depth, along with improved dependencies other relevant parameters.
Introduction
Score-based diffusion models are currently the most successful methods for image generation, serving as the backbone for popular text-to to---mgeme models such as stable diffusion [RBL+22]] Midjourney, and DALLE [RDN+22] as well as achieving wate-of-theear performance other audio and image generation tasks [SDWMG15, HJA20, JAD+21, SSXE22, DN21].
The goal of score-based diffusion is to produce generative model for a possibly complicated distribution go. This involves two components: training neural network using true samples from go 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 the forward SDE:
dæ, = x, dt /2 dB,
20 qo
where B, represents Brownian motion. Here, 2i is sample from the original distribution go over Rd, while the distribution of a, can be computed to be
St e rxn (N, T²
for of = -- Note that this distribution approaches (/00, Ia), the stationary distribution of (1), exponentially fast.
Let y: be the distribution of æ4, and let sx(y) = V log (v) be the associated score function. We refer to lt. as the o, o.-smoothed version of 40- Then, starting from a sample FT ~v Qr, there a reverse
Authors listed in alphabetical order.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

SDE associated with the above forward SDE in (1) [And82]:
dør- ( 28 v2dB,
(2)
That is to say, if we begin at a sample IT ~ QT, following the reverse SDE in (2) back to time 0 will give us sample from the original distribution go. This suggests a natural strategy to sample from Qu: start at large enough time T and follow the reverse SDE back to time O. Since dr approaches (0,, Ia) exponentially fast in T, our samples time 0 will be distributed close qo- particular, if T is large enough Nruugh--oggrrthmiinn in ma then samples produced by this process will be E-close in
TV to being drawn from qu. Here m2 is the second moment of qo. given by m2 = Eo [1
In practice, this continuous reverse SDE (2) is approximated by time-discretized process. That is, the score 8r-r is approximated at some fixed times 0 = to S ( S ... I l < T. and the reverse process is run using this discretization, holding the score term constant at each time 4, This algorithm is referred to as "DDPM". as defined in [HJA20].
Chen et al. [CCL+23b] proved that long each score St at each discretized time, this reverse process produces accurate samples. Specifically, for any d-dimensional distribution go supported on the Euclidean Ball of radius R. the reverse process can sample from a distribution E-close in TV to a distribution (y R)-close in 2- 2-Wassesttein to go in (oly(d, 1/e, 1/7) steps, as long as the score estimates & used at each step are Ōss²) accurate in squared L That is, long as
have access sufficiently accurate estimates for
E (1) -1 Ō(E²). 2
In 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 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. 9) be the class of functions represented by a fully connected neural network with ReLU activations and depth D, with P parameters, each bounded by O. Let {tx} be some time discretization of [0, TJ. Given m i..d samples I, ~ qo for each E {tx}, we take m Gaussian samples 2; (0, la). We take Se to be the minimizer of the score-matching objective:
m E"1
8, = arg min 1
2i
m JEP
0
We then use (Br,) 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 233], we aim to output samples from distribution that is s-close in TV to distribution that is R or yymg-close in Wasserstein to qo. We thus seek to bound the number of samples m get such a good output distribution, in terms of the parameters of Setting 1.1 and e, 7
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 sample complexity bound of Ô 62/2 222 ( P) VDD See Appendix E for detailed discussion.
Following the analysis of DDPM by [CCL+ 23b], more recent work on the iteration complexity of sampling [CLL22, BBD424] has given an exponential improvement on the Wasserstein accuracy 7, as well as replacing the uniform bound R by m2 - the square root of the second moment. In
Ô hides polylogarithmic factors in d, 1 and 7
2

---

particular, [BBDD24] show that 0 log" ()) iterations suffice to sample from distribution that is 7 m2 close to qu in 2- Wasserstein, as long as the score estimates are Ô (=2/O??) accurate, i.e.,
[1)(()) st (x))
(5)
o
Zm
Inspired by these works, we ask: is it possible to achieve similar exponential improvement in the sample complexity of learning score estimates using a neural network?
1.1
Our Results
We give
sample complexity bound of Ō PD log θ Oog' 4) for learning scores sufficient accuracy for sampling via DDPM. Learning is done by optimizing the same matching objective that is used in practice. Compared to [BMR20], our bound has exponentially better dependence on O, 7. and D, and better polynomial dependence on d and P. at the cost of a worse polynomial dependence in E.
As discussed above, for the sampling process, it suffices for the score estimate 8, time to have error Ô (=²/ This means that scores at larger times need higher aceuracy, but they are also intuitively easier to estimate because the corresponding distribution is smoother. Our observation that the effects cancel out: show that the sample complexity to achieve this accuracy for a fixed / is independent of ot. However, this only holds once we weaken the accuracy guarantee slightly (from L eгror "L²² error over a 6 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 or = which yields a final y dependence of Olog" 4) via a union bound over the times t that we need score estimates for. In contrast, the approach in [BMR20] gets the stronger L2- -cccurccy but requires poly (2) dependence in sample complexity for each score st; this leads to their ( 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 m2 of (oo is between 1/ poly(d) and poly(d).
A2 For the score used each step. there exists some function E F(D, Q) (as defined in Setting 1.1) such that the 2 error, Ez- [I]f(())) ) - st (x) is sufficiently small.
That is: the data 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 Al and A2 hold. For any >> 0, consider the score functions trained from
(PPD ( c3
m 2
-log θ log
i..dd samples of 40- With 99% probability, DDPM using these score functions can sample from distribution s-close TV to distribution "yms- to in 2-Wasserstein.
We remark that assumption Al is made for simpler presentation of our theorem; the (logarithmic) dependence on the second moment analyzed explicitly in Theorem C.2. The quantitative bound for A2- A2-exactly how small the 2 error needs to be-is given in detail in Theorem C.3.
Barrier for 2 accuracy. As mentioned before, previous works have been using L accurate score estimation either as the assumption for sampling or the goal for training. Ideally, one would like simply show that the ERM of the score matching objective will have bounded L error of 2/222 with a number of samples that scales polylogarithmically in 1. Unfortunately. this is false. In fact, it is
impossible to achieve this in general without poly( samples. Since sampling to yym Wasserstein error needs to consider final dependence. See Figure 1, or the discussion in Section 4, for a hard instance.
7, this leads to poly(?)

---

0.6
L' mestic
Buihuee pmokubiilie
DJ mettze
0.2
-25
0.0
-8
it
R
R
100
10P
Figure 1: Given o
samples from either = (0, =2 n) 1)
(R, 1) will only samples from the main Gaussian with high probability, and canmot distinguish between them. However, we pick wrong score function, the L emorr incurred is large about syft". the right, we take = 0.001, 10000, 5 0.01. We plot the probability that the ERM has error larger than in the L sense, and our DØ sense.
In the example in Figure 1, score matching + DDPM still works to sample from the distribution with sample complexity scaling with poly(log ); the problem lies in the theoretical justification for it. Given that it is impossible to learn the score in L to sufficient accuracy with fewer than poly samples, such a justification needs a different measure of estimation error. We will introduce such measure, showing (1) that will be small for all relevant times after number samples that scales polylogarithmically in 4, and (2) that this measure suffices for fast sampling via the reverse SDE.
The problem with measuring error in L comes from outliers: rare, large errors increase the L error while not being observed on the training set. We proved that we can relax the L accuracy requirement for diffusion model to the (1 -'-uuntee error: For distribution p. and functions f.g. we say that
(6) We adapt [BBDD24] to show that learning the score in our new outlier-robus. sense also suffices for sampling, if have accurate score estimates at each relevant discretization time.
De g) SS = Pazp [Ilf(r) - g(x)ll2 5
Lemma 1.3. Let be distribution over Rd with second moment m between 1/poly(d) and poly(d). For any 7 > O, there exist N Ö( 25 log" 1) discretization times 0 < t1 < tt < T such that if the following holds for every 1e E
{O....,N" E 1}:
S/N Qr
(fT-ta: ST ) -I
then DDPM can sample from distribution that is within Ō e ea Vog (d/7)) in TV distance 4+ in N steps.
With this relaxed requirement, our main technical lemma shows that for each fixed time, good
(1 - qu-unatee accuracy can be achieved with small number of samples, independent of at.
Lemma 1,4 (Main Lemma). In Setting 1.1, suppose assumptions Al and A2 hold. By taking m i.idd.
samples from go to train score function S,, when
(d log drme
PD
8yain )
m >>>
loog
E28 Sxcore
with probability 1 8yrin the score estimate S satisfies
Domo (St, 8t) S E/or.
Combining Lemma 1.4 with Lemma 1.3 gives Theorem 1.2. The proof detailed in Appendix C.
2 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. SSDK*21 21, SDME21J. More recently, diffusion models have found several exciting applications, including medical imaging and compressed sensing 2JAD= SSXE22), and text-to- image models like DALL.- [RDN+22] and Stable Diffusion [RBI.+22].
Recentl, a number of works have begun to develop theoretical understanding of diffusion. Different aspects have been studied the sample complexity of training with the score-matching objective [BMR20], the number of steps needed to sample given accurate scores [CCL+233, CLL22, CCSW22, CCL+23a, BBDD24, BTHD21, LLT23], and the relationship more traditional methods such as maximum likelihood [PRS*22 23, KHR23].
On the training side, [BMR20] showed that for distributions bounded by R. the score-matee cotchnna objective learns the score of in T.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 sample from 44, scales polylogarithmically in + given L approximations to the scores.
Our main contribution to show that while learning the score in L requires a number of samples that scales polynomially in 4. the ccore-matching objective does learn the score in weaker sense with sample complexity depending only polylogarithmicaly in t.- Morcover, this weaker guarantee sufficient maintain the polylogarithmic dependence on 7 the number of steps to sample with -- m2 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, OAS23J. For example, [CHZW23] shows that for general subgaussian distributions, the scores can be learned to T,2 error e/a, with (d/e)o(d) samples. Our approach avoids this exponential dependence, but assumes that neural networks can represent the score.
3 Proof Overview
In this section, we outline the proofs for two key lemmas: Lemma Section 3.1 and Lemma 1.3 in Section 3.2. The complete proof' for these lemmas are provided in Appendix A and Appendix B respectively.
3.1 Training
We show that the score- mote-matthinn objective (4) concentrates well enough that the ERM is close to the true minimizer. Prior work on sampling [BBDD24] shows that estimating the o-smoothed score to I3 error = 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 f, let a = d and be the distribution of e " for x go- We think of joint distribution of (y. 2. 2) where y p and z ~ N(0, (a) are independent, and x = + 2 is drawn according to q.- With this change of variables, the score matching objective used in (4) is
E
s(x)
Because x = y + = for Gaussian 2, Tweedie's 's formula states that the true score s" 8, is given by
(
Define A = =-0(x)=
=I
ş so E[A x] = 0. Therefore for any x.
1(8, xr 2) = s(x) σ 2
(7)
5

---

= [|(()) - 5* (z) + A ||<()) - (=)1l² - +|
(8)
The third term does not depend on s, and so does not affect the minimizer of this loss function. Also, for every z; the second term zero on average over ar), so we have
arg min E ((( x, =)] arg min E [1((2) 8* (x)
This shows that the score matching objective is indeed minimized by the true score. Moreover, e-approximate optimizer of ((s) will be close in L as needed by prior samplers.
Understanding the ERM. loss
The algorithm chooses the score function s minimizing the empirical
[[,,,,,, =
((s, 24, 24)
==1
- - ((s))
+ [|A1]]].
Again, the | term is independent of 8, so has no effect on the minimizer and we can drop from the loss function. We thus define
((ss, x. =) = [=(x)) - s* (x))] 2(<(x) - (2))
that satisfies 2x)) 0 and [EI" [[]|>())= 5 (x) Our goal is now to to show that
È (',,,,,,
(10)
for all candidate score functions that are "far" from s*. This would ensure that the empirical minimizer of the score matching objective is not "far" from st. To do this, we show that (10) is true with high probability for each individual 8, then take a union bound over a net.
Boundedness of A. Now, = ~ N(0, is technically unbounded, but is exponentially close to being bounded: ||=||| & a with overwhelming probability. So for the purpose of this proof overview, imagine that & were drawn from a distribution of bounded norm, i.e., |||||| S Bo 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 A
Ezja [. we get ||| S 2B/o.
Warmup: poly( As a warmup, consider the setting of prior work [BMR20]: (1) ||||| S R always, so [x)]l < : and (2) we only optimize over candidate score functions s with value clipped to within 0 R O so ||((z) s" (=)]l S n2- With both these restrictions, then, [1'(s, x, 2) S Rd + .. We can can
then apply a Chernoff bound to show concentration of : for poly(E, R B, log Brate samples, with Suain probability we have
È [' =)] x,,,,, 0
= =]][s(() - 8" (x)
d2
which greater than zero if E[]ls()) - s" (x)) 2- Thus the ERM would reject each score function that is far in 1.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 T,2.
The main technical contribution of our paper is to avoid this polynomial dependence on 1/a. To do so, we settle for rejecting score functions that are far in our stronger distance measure D i.c. for which
P[][(()) s" (x)1l e/0] S
(11)

---

Approach. We want to show (10), which is a concentration over x and 2. Now, x is somewhat hard control, because it depends on the unknown distribution, but (0, La) is very well behaved. This motivates breaking up the expectation over into an expectation over and x. Following this approach, we could try show that
È (s, 2)]
(s, 2/1
However, this is not possible show; the problem that this could be unbounded, since s(x) an arbitrary neural network that could have extreme outliers. So, we instead show this is true with high probability we clip the internal value, making it
Ag := [|min( IE (1( x,, 2)], o² )} = ([inn[]s(()) (x)1l 10B² )}
10B²
=/0
Note that A₂ is a function of the empirical samples æ. If s is a score that we want to reject under (11), then know that Ag is empirical average of values that are at least 5 with probability dscore- It therefore holds that, for m > O
log Suii
we will with 1 - Suain probability over the samples æ have
Sucore
Ag 2
(12)
σ²
Concentration about the intermediate notion. satisfying (12), we will have
Finally, we show that for every set of samples T;
A 0.
E Este (s,
2
This then implies
A₂ Sxcore
as needed. For each sample x, we split our analysis of É [1,, x, 2)] into two cases:
Case 1: [|s(z) s (x)]) O) In this case, by Cauchy- Schwar- and the assumption that
||||| S 2B/0.
B - |ssc)- (|<(o)
10B² σ²
((,,,,))
so these will contribute the maximum possible value Ar, regardless of (in its bounded range). Case 2: [ı(()) - s* (x) < {))). In this case, [1'(s, x, 2)1 < /²/0² and
B² - -s(z) - (z)]
Var(l'(s, 2)) 4B](s(z)
a/
so for these v, as distribution over bounded with bounded variance.
In either case, the contribution to A₂ is bounded with bounded variance; this lets us apply Bernstein's B² log 7eam O B²log Fum ), for every will have :absavve
inequality to show, if m O
A
BI1' (8, x,
2 >
with 1 Swain probability.
log Smin
Then with Swain probability we will have (12); and conditioned on this, with 8rain probability we will have Éz. xr, =)] > 0. Hence this m suffices to distinguish any candidate score that is far from s*. For finite hypothesis classes we can take the union bound, incurring log [7]] loss (this is given as Theorem A.2). Lemma 1.4 follows from applying this to net over neural networks, which has size log H ~ PD log θ.
Conclusion. Suppose m 0
7

---

3.2 Sampling
Now we overview the proof of Lemma 1.3, i.e., why having an e/or-t, accuracy in the D sense is sufficient for accurate sampling.
To practically implement the reverse SDE in (2), discretize this process into N steps and choose sequence of times 0 = ln < 4 <... < T. At each discretization time 42 we use our score estimates St, and proceed with appraximate reverse SDE using score estimates, given by the following. For E [4+. 12+1].
drr- (+T- + 28T (xT v2dB,, IT NNO, La).
(13)
This is almost the reverse SDE that would give exactly correct samples, with two sources of error: starts at (N, La) rather than qr, and it uses Sy-t, rather than the ST-t- The first emrrr is negligible, since is e -close to (0, Ta). But how much error does the switch from 8 to introduce?
Let Q be the law of the reverse SDE using 8, and let Q be the law of (13). Then Girsanov's theorem states that the distance between Q and Q is defined by the I.2 error of the score approximations:
N-1
T-
KL
11 Q
8T ta (XT )| ((ST-((FT-))
T-
N
E
[188T 8r -x) (4++1 - 1x)
(14)
The first line is an equality. The second line comes from approximating 2T- by IT-4 which for small time steps quite accurate. So in previous work, good T,2 approximations to the score mean (14) is small, and hence KL(Q Q) is small. our setting, where we cannot guarantee good 2 approximation, Girsanov actually implies that we cannot guarantee that KL(Q Q) is small.
However, since finally hope to show closeness in TV, We define an event E to be the event that the score is bounded well at all time steps TT tt i.e.
circumvent the above follows.
E = A
(1ST-u ( - -1
OT
KE(1...,.N
If we have
6/N accuracy for each score, we have 1 - 1-P(F) S 8. 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 by
TV(Q, Q) $ (1-P (E)) + TV((Q E), ( E)).
The second term TV((Q E), ( 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.
4 Hardness of Learning in 2
In this section, we give concrete examples where is difficult to learn the score in I.2, even though learning to sufficient accuracy for sampling is possible. Previous works, such [BBDD24], require the T.2 error of the score estimate 8; to be bounded by e/a,- We demonstrate that achieving this guarantee is prohibitively expensive: sampling from -moothhh distribution requires at least poly(1/oz) samples. Thus, sampling from a distribution 7-close in 2-Wasserstein to requires polynomially many samples in 4.
To show this, demonstrate two lower bound instances. Both of these instances provide pair of distributions that are hard to distinguish in T,2, and emphasize different aspects of this hardness:
1. The first instance shows that even with polynomially bounded set of distributions, it is information theoretically impossible learn score with small 7,2 error with high probability, with fewer than poly(1/7) samples.
8

---

True Dist.
True Score
Alternate Dist.
Alternate Score
R
10 Tog
R
Figure 2: For m samples from (0, 1), consider the score the mixture (0, (1 (R, 1) above with is chosen so that (10v/log m) = 0. For this 8, the score-matching objective is close to 0, while the squared L error Ω
R²
2. In the second instance, we show that even with simple true distribution, such as a single Gaussian, distinguishing the score matching loss of the true score function from one with high T,2 error can be challenging with fewer than poly(1/1 (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 n0, o²) -> o²), where R polynomially large. Even though these distributions are polynomially bounded, it is impossible to distinguish these in L given significantly fewer than 1 samples. However, the L error score incurred from picking the score of the 7i
wrong distribution is large. In Figure the rightmost plot shows a simulation of this example, and demonstrates that the L error remains large even after many samples are taken. Formally, we have: 1)) o²) (N(-R, o2) with corresponding score function 81, and let p2 be (1 (0, o²) + nN(RR o?) with score $2, such that 1) impossible to distinguish between p1 and with probability larger than 1/2 + om (1). But.
Lemma 4.1. Let R sufficiently larger than a. Let Pr be the distribution
e²0² T/ Then, given m 260 samples from either distribution, is
B²
8²
E [1) 12(x)111 02 Je-p1
and
E p-Pp
[1)s
2 0²
Now, consider the true distribution being N N(0, o²). and, for large S, let be the score the mixture distribution v,, ((0,)²2) +1 (S) o²), as in Figure 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 nearly identical. However, the squared L error incurred from picking the wrong score function is large We formally show this result the following lemma:
Simple true distribution:
Lemma 4.2.
Let S be sufficiently large. Consider the distribution p 10 +1 (1
for 1 = Se - 1m. 10/logm and let 3 be its score function. Given m samples from the standard Gaussian p² = =N(0,03) with score function s", with probability at least 1 poly(m)'
E [[G(z) (x)))
1 < g2
-O(S m)
but
E [13(x)- s (xx))
S
mo4"
Together, these examples show that with reasonably bounded well- distributions, it is difficult to learn the score in with fewer than poly (R/7) samples, motivating our (1 -ququiie measure.
5 Conclusion and Future Work
In this work, we have addressed the sample complexity of training the scores in diffusion models. We showed that neural networks, when trained using the standard score matching objective, can

---

be used for DDPM sampling after 01 log θ log" 2)) training samples. This is an exponentially better dependence on the neural network depth D and Wasserstein enror than given by prior work. To achieve this, we introduced more robust measure, the å quantile error, which allows for efficient training with poly (log +) 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 understanding the statistical performance of the score matching objective: we show that the empirical minimizer 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 not address it here.
Acknowledgments
We thank Syamantak Kumar and Dheeraj Nagaraj for pointing out an error in a previous version of this work, and for providing a fix (Lemma F.7). This project was funded by NSF award CCF-1751040 (CAREER) and the NSF Al Institute for Foundations of Machine Learning (IFML..
6 References
[And82] Brian D.O. Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):1133326 1982.
[BBDD24] Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly SdS-linear convergence bounds for diffusion models via stochastic localization. In The Twelfth International Conference on Learming Representations, 2024.
[BMR20] Adam Block, Youssef Mrouch, and Alexander Rakhlin. Generative modeling with denoising auto-encoders and langevin sampling. arXiv:2002.00107 [cs, math, stat), June 2020. arXiv: 2002.00107.
[BTHD21] Valentin De Bortoli, James Thornoon, Jeremy Heng, and Arnaud Doucet. Diffu- sion schrödinger bridge with applications to score-basee based generative modeling. In A. Beygelzimer, Dauphin, P. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[33L++33] Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ODE provably fast. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Process- ing Systems, volume 36, pages 68552-68575. Curran Associates, Inc., 2023.
[CCL 22bb Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru Zhang. Sampling is easy learning the score: theory for diffusion models with minimal data assumptions. In The Eleventh International Conference on Learning Representations, 2023.
[CCSW22) Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for a proximal algorithm for sampling. In Conference on Learning Theory, pages 2984-3014. PMLR, 2022.
[CHZW23] Minshuo Chen, Kaixuan Huang. Tuo Zhao, and Mengdi Wang. Score approximation, estimation and distribution recovery of diffusion models on oow-dimensional data. In Proceedings of the 40th International Conference on Machine Learning, ICMI JMLR.org, 2023.
[CLL222 Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learning, 2022.
10

---

[DN21] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans image synthesis. In M. Ranzato, Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 8780-8794. Curran Associates, Inc., 2021.
[GLP23] Shivam Gupta, Jasper C.H.
Lee, and Eric Price. High- dinensiinnsi location estimation norm concentration for subgamma vectors. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 12132-121644 12164. PMLR, 23-29 Jul 2023.
[HJA20] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 6840-6851. Curran Associates, Inc., 2020.
[HKZ12] Daniel Hsu, Sham Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications Probability, 17:1-6, 2012.
[JAD+21]] Ajil Jalal, Marius Arvinte, Giannis Daras, Eric Price, Alexandros G Dimakis, and Jon Tamir. Robust compressed sensing mri with deep generative priors. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 14938-14954, Curran Associates, Inc., 2021.
[KHR23] Frederic Koehler, Alexander Heckett, and Andrej Risteski. Statistical efficiency of score matching: The view from isoperimetry. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
[KN] Syamantak Kumar and Dheeraj Nagaraj. Personal communication.
[LLT23] Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In International Conference on Algorithmic Learning Theory, pages 946-985. PMLR, 2023.
[ND21] Alex Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. CoRR, abs/2102.09672, 2021.
[OAS23] Kazusato Oko, Shunta Akiyama, and Taiji Suzuki. Diffusion models are minimax optimal distribution estimators. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org, 2023.
[PRS+23] Chirag Pabbaraju, Dhruv Rohatgi. Anish Prasad Sevekari, Holden Lee, Ankur Moitra, and Andrej Risteski. Provable benefits of score matching. CoRR, abs/2306.01999, 2023.
[RBL+22] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10684-10695, June 2022.
[RDN+22] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierar- chical text-conditional image generation with CLIP latents. CoRR, abs/2204.06125, 2022.
[SDME21] Yang Song, Conor Durkan, Iain Murray, and Stefano Ermon. Maximum likelihood training of score-based diffusion models. In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
11

---

[SDWMG15] Jascha Sohl- Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermoyynamies. Francis Bach and David Blei, editors. Proceedings of the 32nd International Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 2256-2266 Lille, France, 07-09 Jul 2015. PMLR.
[SE20] Yang Song and Stefano Ermon. Improved techniques for training score-based gen- crative models. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 12438- 12448. Curran Associates, Inc., 2020.
[Se124] Mark Sellke. On size-independent sample complexity of relu networks. Information Processing Letters, 186: 166:10688, 2024.
[SSDK+21] Yang Song, Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Er- mon, and Ben Poole. Score-based generative modeling through stochastic differential equations. International Conference on Learning Representations, 2021.
[SSXE22] Yang Song, Liyue Shen, Lei Xing, and Stefano Ermon. Solving inverse problems in medical imaging with acore-based generative models. In International Conference Learning Representations, 2022.
A Sample Complexity to Achieve (1 - --)-unnntile Accuracy
The goal of this section is to prove our main lemma, the sample complexity bound to learn score at single time. More specifically, we will give quantitative version of Lemma 1.4.
Lemma A.1 (Main Lemma. Quantitative Version). Let qu be distribution with second moment mz. Let (0(-) be the fully connected neural network with ReLU activations parameterized by 9, with P total parameters and depth D. Let θ 1. Suppose there exists some weight vector 6* with 100 10 S ④ such that
8 8yain E²
E gruqe
[l (x) sc(x)]13]
C.
for sufficiently large constant C. By taking m i...d samples from to train score when
m > Ō (d + log 1) PD
log maxx(m2, 1) 1).0)))))))
Oyaai
the empirical minimizer dg of the score matching objective used to estimate st (over de with [00 < )) satisfies
D ( 81) S ee/or
with probability Syrain-
In order to prove the lemma, we first consider the case when learning the score over finite function class H.
A.1
Score Estimation for Finite Function Class
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 sense (see (6)), then the ecore-matchine objective can learn this function using number of samples that is independent of the domain size or the maximum value of the score.
Notation. Fix a time f. For the purposes of this section, let := be the distribution at time f, let = o, be the smoothing level for time f, and let = 8t be the score function for time t. For m samples Vi go and 2 A/ o²), let = e' " + 2, gr.
We use [zf(2, (2, y, 2]] to denote the empirical expectation 1 ΣM f(zi, Wi, 24).
12

---

We now state the score matching algorithm.
Algorithm Empirical score estimation for
Input: Distribution go. M1..... 3m go. set of hypothesis score function H = {{x), smoothing level ø.
1. Take m independent samples 2, ~ N(0, o2la), and let x; = e e + 2z.
2. For each H. let
((5) 3(x,)
3. Let = arg min sew 1())
4. Return
Lemma A.2 (Score Estimation for Finite Function Class). For any distribution qu and time >> consider the o:-smoothed version qe with associated score St. For any finite set H of candidate score functions. If there exists some s* E H such that
Escore Orain E²
[1=((z) - sc())
E gr
(15)
C.
for a sufficiently large constant C, then using m δ 20 (z (d + log Tane log empirical minimizer & of the score matching objective used estimate 8t satisfies Dru 4t
samples, the 8amn
H
(8, 81) S E/O0
with probability
6yroin-
Proof. Per the notation discussion above, set 8t and o oz-
Denote
1(8, 11, s(x)) σ²
We will show that for all such that D2Smm (3,8) > 2/O, with probability
ógain
È [ 2) I(s .x, 2)] O, so that the empirical minimizer á is guaranteed to have
Drseo (8,8) S 8/0.
We have
1(,,r, =1(("",))) 1(,",,,,)))
[(xr)
-2
8" (x)
-
σ²
²²
= -(1xt0) 0²
-2 2
-2 12) s(x)
[10 =xx)) 2(s"(x) s(x), -()) -
(16)
Note that by Markov's inequality, with probability
S /3.
S 62
E. [1|> - (x))))(>)11?3?
S 30 o²
By Lemma A.3, with probability - Surinn /3.
-2 (s (x) - s(x)
8score 22
<
2
13

---

Also, by Corollary A.5, with probability 1 - Sunin/ /3, for all E H that satisfy (3,m( E/O simultaneously.
B
((t)
s(x)
EscoreE?
16a2
Plugging in everything into equation (16), have, with probability 1 - Swain for all & H with D (8, 8) > e/o simultaneously,
=
Oscore
E ((5,,,;) 11s" 20, =]]
0
160²
300
500²
required.
Lemma A.3. For any distribution 4o and time associated score St. Suppose s* is such that
0, consider the oy-smoothed version with
Óxcore Etrain E²
[[I> - s(x)]1 S 2m
Co
for a sufficiently large constant C. Then, using m > Ō Toue
(d+ log ) samples (xi, 2i)
where y: ~ qu. ~ N(0, of Ia and I; = =e e'yy + ~ we have with probability 1 - 8main
dxconet? 2
E
(8 (x) - s(x),, s(x) = S
1000g2
Proof. Note that s(x) Ezjor [ that
(s (x)) s(x)),(()) - -2
g2
Also, for any 6, with probability 8, by Lemmas F.4 and F.5,
[|$(x) o² -2 1|2 I C d log 1
x²
for some constant C. Let E' be the event that (|s(z)- < C d+ dog 2 Saan Since - subexponential with parameter o² and has mean O ( by the above, by Lemma F.7, we have
a²
d + log 2t chhnneniii
|s(z)
121 o
o²
Then, since [[[]] 1
1 and E [1](=(x)) -xx))11B S
100 2 Busaeeeuaa
[[]s (x) +(x))1 / IP| F.]. we have
R (x) ((x))
-
-
E (xr s(x), s(x) PL
P F
E [11x*(x)) s(x) E [1|a(x)
P
2 (x)]stx)) <(>))1 [|(()) G² 12 P[E
1
22 2ooco Swain
d z² Srann
E2 2co0c
v vd+ log
52
100(d + log 2 2
14

---

8" draio
VCo²
Moreover,
E
(s - -
-
s E
|s (x* -s<x)
- 1/
02
0²
d + log x2 22 Nusis
2 E
|s (x) s(x))1?
E
0²
Sscoro Orain 8²
d + log SeDareo
d
Co²
σ²
So, by Chebyshev's 's inequality, with probability
Swain/ /
E (x)) s(x) E
drcone
1
Secore
(d + log Foosen
Escore 8²
VCo²
0²
Cm
VCo²
for our choice of Since E holds except with probability with probability Onnin in total,
Byoar Siii
Syains have
100(d+log Fhoore
B (s0(0)) -5())))(()))(())) s(x), -2)
Sucore e²
1000G²
for sufficiently large constant C.
Lemma A.4. Consider any set F of functions f Rdd + Rd such that for all f E F,
P Pxpp [z) e/o] 8xcore-
Then, with m >
δ
(d + log
log
samples drawn in Algorithm 1, we have with
Bnans
Oman
probability 1 0pain
1
2i
1) f(x,) + 2 11((,:))1 2
Swor E²
-2
0²
0
16g2
1=1
holds for all f F.
Proof. Define
-2(-2 - E
- पे 10)) f(x) + (
hz(2,2) = -2
We want to show that by has
8sconc
(n 2)] = m
Σ
(r 2
(17)
16
for all f E F with probability bynin-
Let B 0 Va+log Checee
For let
g5(2, x) = [B² (x,
[[(())] 2 10B
otherwise
be clipped version of hy h 2). We will show that for our chosen number of samples m, the following hold with probability
Srain simultaneously:
1. For all i, + < B.
15

---

2. For all i,
| B B
3. Eigr (a, 2)]
شلي for all f E F
To show that these together imply (17), note that whenever 95(2;, 2i) + ()) [If 2 10B. So, since
- B and | bx]]l s B,
tr 1)
(15 2;)
-
Ri 0²
((x) + [1(((x))11> -BBI[((+))) + [|<{)))] 2 B² g5(
So under conditions 1,2,3, for all f E F.
e 2
B (a, 2)] 2 Elgg 2)]
160
So it just remains to show that conditions 1, 2, hold with probability 1 8main simultancously.
1. For all i, bound.
|| -
<
B. Holds with probability 1 - -Smainn33 by Lemma F.5 and the union
2. For all i, E union bound.
xra
S
B. Holds with probability 1 Ownin/3 3 by Lemma F.6 and the
3. (1, 2
A for all FFF. 166
Let E' be the event that 1. and 2. hold. Let a, min(I]f(x))1l 10B). We proceed in multiple steps.
Conditioned on E, (1, =)1 B If [f(xx)]l 2 10B, (x,, (x), B by definition. On the other hand, when [If(x:)]l < 10B, since we condition on E,
1) T f(x.) + (1( $ B²
2.)l = 21) = -2
E
E (g 2,) E,) a.l 2 at First, note that by definition of g gx, 2), for a; 10B,
(8 B²)
IE [gr (24, ]a; = 10B = B2
Now, for a; 10B,
E [ 2,)aa,l = E [ [a:]
E [hy
-z|z.
Now, note that
E [, 2)] = =111((=))1? [2 z/2
So, for < 10B
E (gr [a: = 7a?
clip Now let 9f (I 24) be clipped version of gr (xi, (x 2,), clipped +CB² for sufficiently large constant C. We have, by above.
Elgr a))as,, EJ 1B(9)11 (æi, 21)la;, L7]
But,
Blyg cii (1t, 21) E)
2 Eig dlip (2r, 2x) [a,]
O6Erain B2)
ž a (6train
16

---

(ar(gy(Z;,24) 2;),;;)), a, E) I B² For a, 10B, we have, by definition of g 2), Var(gr(æ,, 2))aa, E) x B* S a B²
On the other hand, for 04 10B,
Var(gr(a,, a,) b) < gr (Tis 2i)
00; E}
27
2
21
2 02
(
1)
s(x;) - (11((=))1))
S 0 B2
by Cauchy-Schward
With probability 1 - Swain/3, 33 for all f F,g, 2 M Using the above, by Bernstein's inequality, with probability
=
Oerain 6
E [lgg(t; DJ a - O 1B) 1
Σ a
log Otrain
1
B2 log
Ouain
Now, note that since P Pa-pe [|[(x)]]| > s/0) 2 Secores we have with probability 1
lug Bemn
Ouain main/6., 6. for > O
8
Score
Ω
n
o²
B log apmi Euuce
So, for 7t > O
we have, with probability 1 -Srain /3,
Escore
T [gg 2,)
(Eerain B32)
n12 B² log Pianat h 3 ovcuee
Rescaling so that deriin 0
2 02.133
for n 0
we have, with
probability 1 - Orainn/ 33
==2
(="8score o²
B 19 21)
Combining with 1. and gives the claim for a single F. Union bounding over the size of F gives the claim.
Corollary A.S. Let Hoat be set of score functions such that for all ă E Hind.
Drsa (B, elo.
Then, for m > δ 228mm (d + log dmao
log
[Howrl 6rmm
samples drawn by Algorithm 1, we have with
probability 8pain
P
[[((z)
-2 222_ [|(()) -2 112
2 8 S
σ²
σ²
160²
for all ă H
17

---

Proof. We have, for f(x) == s(x) =s(r),
[|(())
-2 112 ||(())
σ² =1 =1f((a) + (8(x) -2 2111 ||s(z)
r² 12
o²
= =][(()]] + 2(x(x) 02 --- f(x)
= -|](()]] 2( 02
10l االل f(x)
since s(x) E [z] by Lemma F.1. Then, by definition, for E Houd for the associated f.
P[]lf())]l > c/a] > Oscore- So, by Lemma A.4, the claim follows.
L
A.2 Score Training for Neural Networks
Now we are ready to apply the finite function class to neural networks by a net argument. In particular, we first prove version that uses a Frobenious norm to bound the weight vector.
Lemma A.6. Let qo be distribution with second moment m Let Φe(-) be the fully connected neural network with ReLU activations parameterized by 0, with P total parameters and depth D. Let θ > 1. Suppose there exists some weight vector 0* with | || S θ such that
E [lleo (x) se(x))11] & Excom Eman e² C.
gruge
for sufficiently large constant C. By taking m i.i.d. samples from qo to train score 8,, when
> (d + log
PD
mmax(m2 1). 1).6)
Oamin
log
the empirical minimizer 0ū of the score matching objective used to estimate (over de with ||0|| < θ) satisfies
Da (Óg. 8t) S c/Or-
with probability 1 - Oyrain-
Proof. Per the notation discussion above, we set s = 8, and o = or. Note that o < since of 1
For any function denote
I(f,r,=) = [(x)) ②
we will show that for every ē with |00| S θ such that Dame > e/o, with probability Suains
È [( x, 2) l(0g. x, z)] >0
so that the empirical minimizer og is guaranteed to have
D (drg- 8) S eejo.
First, note that since the ReLU activation is contractive, the total Lipschitzness of de is at most the product of the spectral norm of the weight matrices each layer. For any 0, consider such that
B|IF S o D
Let Mi...., Mp be the weight matrices at each layer of the neural net de. and let Mi. Mp be the corresponding matrices dz.-
We now show that || (x) - (>))) is small, using a hybrid argument. Define y/ to be the output of
neural network with weight matrices M M,...., M,. Moti...... Mp on input x, yo Φg(x) and yd Φo(x). Then have
18

---

1 Vi+ill - ||||||
II |ap1
| Mittl|
II II |ل,
55
$ |||||| + D-1 1
0 0
and so
D-1
[ llv0
yDll -
Σ
llvs
Met1ll S ||]||| DO D-1 1 0- 0 s || 7/0.
t=
Note that the dimensionality of 0 is P. So, we can construct a aD -net N over the set {0:
||0|| s ) of size 0 (D P
so that for any 0 with ||0|| S O, there exists 0 N with
1 - (0(x))l2 & (T/O) ||>|||
Let H. tog 0 N}. Then, we have that for every with ||0||
θ there exists & H such that
B [1](x)) - (
= (T/O)²
(18)
Now, choose any 0 with |00|| S and ( E/O, and let h E H satisfy the above for 0.
We will set
C²E²
(19)
@ m max(m2 1) (d log Orean
for small enough constant C². So, [H| = 0 ((DDO0 1 since σ < 1.
D@20 (m 3 Hog ___
So, our final choice of m satisfies m Ō
(d log
log
[Hl Birin
2 Bromn
We have
(60g, 2, 2) - 1(600, x)
[1/g(1) - 1|2 - |1000 (1:)
-2 112
0²
= 11)p(1) - T1(x)112 + 2(0g(1) - Tr(2), ((()))(())))))))))) - -2
-/ + +17(z)
-2
1
(20)
-2 1|2 1 (x) s(x)11 2(d (x) s(x), s(x)
||s(x)
o2
σ²
Now, by Corollary A.5, for our choice of m, with probability 8rniin /4 for every h H with D Sume/ (h, s) > </(20) simultaneously.
S 128
[1(x)) -11--11((0)
[|0(x))
12
>
By Markov's inequality, with probability Serain/
Sucer 8²
É I|loo. (x) - s(x))1[1]
250g
By Lemma A.3, with probability 0trann/4 /4,
M (cgg (x) - s(2))
-2
<
E
10000
19

---

Plugging into (20) we have that with probability 1 30 /4, for every satisfying Di ((,m)1((1,))) 6) > e/(20),
S E² - -2 ó
[10g] x, 2) - -1000 x2 x)]
2
10000² + 2((07(2) - h(x)),(x)) -
=2
128o2
250g²
r²
Sccoee E²
+ -((g(()) - -(xx), )²)
(21)
600 o²
Now, we will show that D/ 2 (h, s) > =/(2),, as well as bound the last term above. for every 0 satisfying (07, 8) > E/O and E H. the rounding of Φzg.
By the fact that qo has second moment ma, we have that with probability 1 over x,
| S m2 vo
(va+v
Vd + V 2 1
+ t
Now since Diumm (0x. 8) > e/o, and [[ī(x)) اz(2)ll s (T/O). ||x]|1, we have, with probability at least 8score /
[1k(x)) - s(x)11 2 110g(x) - s(x)) [1((x))) ا3(+))l
[1a(z)-
( m2
log /ucune/2 +o (vá+ v /2008 &scare
2
2 8/0 (T/O)
2 (20)
for our choice of r as in (19). So, we have shown that > (h,,o
(h,
e/(2).
Finally, we bound the last term in (21) above. We have by (18) and union bound, with probability
1 Ounnn/ 8,
E [1((x)) -g(())11 2 (T/O)².
m- m-m3
+
o²
d +
log
m Oerain
8wnin
m m.m2
$ (T/O)².
d - log
since
Ownin
Oernin
2422 Score
by (19)
o202D
m-max((m..)) (m).))
+ log
Buis
Busin
Similarly, with probability 1 Ouain 88
E h(xx)
-2 02
11 <ep m (m- mm-m3
+ o² d log Seraio
m
1 ))
d log Oraain
m
8reain
0²
So, putting the above together, with probability 1 - Oerain 4,
2288 score
m [[ī((a)) (g(x)]] E [1((z))
-2 -
112
1 0z
C g
482
score
since
So, with probability -Strain/ for some small enough constant C".
1 (05(0) - T((x),
- 2 -
2 [Iī(x)) (b(x))]]] R [1((x))
113
> 2000 o²
20

---

So finally, combining with (21), we have with probability 1 - òvain
òscore E²
E [10gs 2t, 1(bb-, 2, x)] 1000 x²
So, we have shown that with probability 1 1-mmin for every 0 with ||0]| S O and Diumm (bg;;) > e/0.
E [10 x, 1(0gr x, > 0
so that the empirical minimizer Ø3 is guaranteed to have
Drsaee (dg: 8) S e/0.
Then we have our main lemma as direct corollary:
Proof of Lemma A.I. For every 0 with |00| [x S O, we have
|0 S V < VpO.
Then, by applying Lemma A.6 directly, we prove the lemma.
B Sampling with our score estimation guarantee
In this section, we show that diffusion models can converge to the true distribution without necessarily adhering to L bound on the score estimation error. A high probability accuracy of the score is sufficient.
In order simulate the reverse process of (1) in actual algorithm, the time was discretized into N steps. The k-th step ends at time fg2 satisfying 0 S to < < .... <x The algorithm stops at iN and outputs the final state TT-tx-
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 7/: R):
Let Q be the measure for the process that
drr = (xT- + 28t 2 di + V2dB, oT ~ Gr-
Let Qdis be the measure for the process that for [tR, tx+]),
dær (IT-I 2ST (#T-4+)) dt v2dBi, øT Qr.
Let Q be the measure for the process that for [tg, tx-1];
drr (xT- 28t (wT-++)) di d2dBr, oT Qr.
Let Q be the measure for the process that for t E [t,, t 11-
drr- = (IT-1* + 28 (xT- dt + V2dB, Er ~ N(0,
To summarize, Q represents the perfect reverse process of (1), Qui is the discretized version of Q, Q runs Quis with estimated score, and Q starts Q at (0, Ta) 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 1.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 casily integrated in black-box way to achieve similar results.
21

---

Lemma B.1 (Score Estimation guarantee), Consider an arbitrary sequence of discretization times
0 = to < 1 < < IN = T % and let of == v Assume that for each k e ( N 1}, the following holds:
D (sr-tu, 8T-12) -7-44 2r
Then, we have
-T-1 (xr-6a) )|g (k) s E² (T (++ log 1)
Pq
Σ
2 8.
k=0
Proof. Since random variable TT-ts. follows distribution dr-tu under Q, for each &s E {0,-.... N
1}, we have
PQ (CT-ucTT- ST - (xT < VI 2(T
N
Using a union bound over all N different a values, it follows that with probability at least over Q. the inequality
1 (1T- ST (IT (1 2T -1))
N - 1}. Under this condition, we have is satisfied for every & E ,
ST tu (IT- ST (xT ( tx)
N
g²
2(T (16+1 1x)
N-1
14+1
g²
1 e 2-T 2(T dt
k=0
8²
dl.
1 - e -c)
<E² ('+ 10+1og 2)
Hence, find that
Sr tn (xT- ST -T- (1T- 3 (x) tx) Se2 ( T log 1)
PQ
Σ
2 1 6.
Lemma B.2 (Score estimation enror TV). Let q be arbitrary distribution. If the score estimation satisfies that
N PQ
S (xT- (IT tw) s 2 21-6
(22)
0==
then the outpul distribution -x- of Q satisfies
TV P S 8 t TV(Q, Qai) + TV( Ta))
Proof. We will start by bounding the TV distance between Qai and Q We will proceed by defining
Q and arguing that both TV(Qus, Q) and TV(Q, Q) are small. By the triangle inequality, this will imply that Q and Q are close in TV distance.
22

---

Defining Q. For h E {O...., N - 1}, consider event
Ex
TT - (xT- - -T- S
which represents that the accumulated score estimation error along the path at most e² for discretized diffusion process.
Given Ex, we define a version Qdis that is forced to have a bounded score estimation error. Let Q over C(, be the law of a modified reverse process initialized at 2T ~ qr, and for each te (x+t),
dot = -(xT- + 25t (x)) dt + v2dB.,
(23)
where
Sr-t2 (IT == { -t (IT- Es holds, Es doesn' hold.
84 (xT-
This SDE guarantees that once the accumulated score error exceeds e (Ex fails to hold), we switch from the true score the estimated score. Therefore, we have that the following inequality always holds:
N
13 (tT-
8r- (1a((++1 tx) E
(24)
K=
Quis and Q are close. By (22), we have
PQQ.. A FIN-1]= PQs [ 2 PQ [EN-1] TV(Q. Qus) 2 TV(Q,
Note that when path ( satisfies Flg .... A EN 1, its probability under Q is at least its probability under Qdis- Therefore, we have
TV(Q Q) TV(Q, Qais)
Q and Q are close. Inspired by (CCL+23b)] we utilize Girsanov's theorem (see Theorem F.8) to help bound this distance. Define
b, = (17--1 Sy -
where & is index such that [4x, 4+11. We apply the Girsanov's theorem to (Ô, (br)). By Eq. (24), we have
N-1
16
S
Σ ( 3T (2T- (2) (x) 5 2e² oc.
This satisfies Novikov's condition and tells us that for
E(C), eex (L by
1 / [1., ((100113r)) b,d dB,
under measure q' := E=E( 2, there exists a Brownian motion (Br)eejo.nv such that
B, B, - f b, dr,
and thus for t E [tg, tb+1),
dB, = dB, + 22 (IT - 8r (ST (x)) de.
Plug this into (23) and we have that for E [4x, (k+1)
drt-t (IT-1 + 28 - (IT- dt + /2 dB, 2T 4T.
23

---

This equation depicts the distribution of z, and this exactly matches the definition of Q. Therefore,
Q Q' [() Q, and we have
KL (51
E
In
dQ
E
[
Then by using (24), we have
In (()) KE Σ ST- (xT-14) ST (oT (uT--x))) M12 (w) 557
Therefore, we can apply Pinsker's inequality and get
TV( KKL (K((2pl)) Se.
Putting things together.
Using the data processing inequality, we have
TV(Q, Q) < TV(qr,NN(,, Ia)).
Combining these results, we have
TV(Q, Q) S TV(Q, + TViQ Q) + TV( +)+ TV(Q, Q) 88+c+ TV(Q, Qais) + TV( Ia)).
Since 9,, is the distribution for IT-ty under Q and Pr-ty is the distribution for øt-tx under @ have
TV(g,,Pr PT- & TV(Q, ②) (8+2)))6444) +6+ TV(Q, Qas) + TV(qr,N(0,,1)
Lemma B.3. Consider an arbitrary sequence of discretization times 0 = to < 4 < ... < tx
T 7. Assume that for each l E {O...., 1}, the following holds:
DAIN
ST S 9r-42
1
OT-
VT log
Then, the output distribution Tr -t satisfies
TV - 5 TV(Q, Qais) TV(gr, Ia)).
Proof. Follows by Lemma B.1 and Lemma B.2.
The next two lemmas from existing works show that the discretization error, TV(Q, Qai),, is relatively small. Furthermore, as T' increases, qr converges exponentially towards (0, Ia).
Lemma B.4 (Discretization Error, Corollary and (17) in [BBDD24]). For any T 2 1, 7 <1 and N 2 log(1/7), there exists sequence of N discretization times such that
TV Qais) S / d
T (++1og] ( :)
Lemma B.5 (TV between true Gaussian and qT for large T, Proposition in [BBDD24]), Let be distribution with a finite second moment of m Then, for T > have
TV(er, Ia)) & (vd mz)e
Combining Lemma B.4 and Lemma B.5 with Lemma B.3, have the following result:
24

---

Corollary B.6. Let q be distribution with finite second moment m2. For any T 2 1, < and
N 2 log(1/7), there exists a sequence of discretization times to < t < tN T
such that if the following holds for each k E ,0,...,N N 1}:
D 4T (8T-1u; 8T 8t OT-
then there exists a sequence of N discretization times such that
8V log -+ - T 1 log 2) + (Vd + m2)e -T
+(Vd+
This implies our main theorem of this section as a corollary.
Theorem B.7. Let q be distribution with finite second moment m2. For any "( >> O, there exist < t < iN T such that if the
N Ō( 24.82 log" d4m2) ) discretization times to following holds for every E (0....,N-1)
DAAN (5T ty: -T
OI-NN
then DDPM can produce sample from distribution that is within Ö(8 + E Ev/log ((d + m2)/7)) TV distance of 9y in N steps.
in
Proof. By setting T = log(
ddmz)) and N 540
d(T d(T+Hog(]/n)) in Corollary B.6, we have 82482
=
t log
+ m2
Furthermore, we present our theorem under the case when my lies between 1/ poly(d) and poly(d) to provide clearer illustration.
Lemma 1.3. Let q be a distribution over Rd with second moment m between 1/poly(d) and poly(d). For any 7 > O, there exist N = Ō 4.0 oz log" 1) discretization times 0 = to < t1 < ... < ft < T
such that if the following holds for every ke E {O,...,N N-1:: 11}:
DAN
(bT-ty: 81- OT Qr-tz
then DDPM can sample from a distribution that within Ö(6 + E /vlog (d/7)) TV distance to in N steps.
C Sample Complexity of Training Diffusion Model
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 be learned using number samples scaling polylogarithmicaly in 4. where is the desired sampling accuracy.
Lemma C.1. Let qu be distribution with second moment m Let Φo(-) be the fully connected neural network with ReLU activations parameterized by 8, with P total parameters and depth D. Let ④ > L. For discretization times to <... < tN. let ST be the true score function of QT-ty- for each lg, there exists some weight vector 0* with 110 11 I O such that
8ecom Orrain 62 <
E Bruqy t
[10g.
(I) ST ST
(25)
Coz N2
Then, if we take m > δ N(d+loR ) log max(mng.1)).)) )) Srnat
samples, then with probability
1 - 8yain each score -t learned by matching satisfies
Omown/ / (ST- 8T -T) S e
qr -t
25

---

Proof. Note that for each Ek. - is -t- smoothed distribution. Therefore, we can use Lemma A.I by taking / /N into òmin and taking ó /N into Ó We have that for each tg- with probability Onain/N N the following holds:
P P -1 (x) - (x))l e/or-ul 2 Sscore/N.
By 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 be distribution of R& with second moment mē. Let (-)-) be the fully connected neural network with ReLU activations parameterized by 8, with P total parameters and depth D. Let è > 1. For any y >> O, there exist N = Ō ( log² ma2t//g discretization times 0 = la < <.... < IN < T such that for each 1op there exists some weight vector 8 with 1lx S such that
8 8
E 2-000-k
ST 1T ST (s)
(20)
CN log d+ma+1/ma
?
for sufficiently large constant C, then consider the score functions trained from
m > δ [N + log b) PD
mmax(m2, 1)
-log m2 + 1/m2
loog
e²3
i.i.d. samples of q, with 1 probability, DDPM can sample from a distribution e-close in TV distribution yym2-close in 2- Wasserstein to 9 in N steps.
Proof. Note that for an arbitrary t> 0. the 2- Wasserstein distance between q and qe is bounded by Ottm² + vtd). Therefore, by choosing tN T min(y, 7 /2m2/d) Theorem B.7 shows that by choosing N = (g122445 log" min(?.? (anss>2mg/al
d+m2
we only need
DEAN (ST- 97-4y
8T ST
OT
log min( i f
d4-ma
then DDPM can produce sample from distribution within Ö(E') in TV distance to a distribution ym2-close in 2-Wasserstein to q in steps. Note that
min(7, Pm3/dd S log + m2 + 1/m2
d + m2
log
Therefore, we only need take Ō (5 log m=+1/m2) steps. Therefore, to achieve this, we set
d+m, Orain &ecore E', and 5 log dtm++1/ma S 6// log maaas::nmmg//
Lemma C.I. This
gives the result that with
> δ (d + log })) PD
PD
log maxxm22 1) 1).
m2 + 1/m2
log
samples, can satisfy the score requirement given the assumption in the statement.
For cleaner statement, we present this theorem under the case when my 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 TRd with second moment m². Let (bo(.) be the fully connected neural network with ReLU activations parameterized by O, with P total parameters and depth D. Let θ 1. For any x 0, there exist N Ö(d log" 4 discretization times () to .... tN T such that for each ts, there exists some weight vector
gr with ||0* Il S θ such that
5.
E
|1000 (2) -T- (2)11 <
CN log d
26

---

for sufficiently large constant C, then consider the score functions trained from
/D E3
log θ log" 1
i.i.d samples of 9- With 99% probability, DDPM using these score functions can sample from distribution E-close in TV to distribution "ymse in 2- 2-Wasserstein to in N steps.
D Hardness of Learning in L
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 a. Let be the distribution (1 n), (N(-R,o') with corresponding score function 81, and let p2 be (1 n0, d²) + NN o²) with score 82, such that = R impossible distinguish between pı and p2 with probability larger than 1/2 + Om (1). But,
Rt² samples from either distribution, is e² Then, given m < 22g2
E²
e²
[1])(()) - s2(x) 2 amp1
E
and
[1])((z)) - +2(x)]] 2 o²² 2m
02
Proof.
TV(p1, 2
So, it is impossible to distinguish between and p2 with fewer than 0 1/2 + Om (1). The score 2 bound follows from calculation.
samples with probability
17
Lemma 4.2. Let be sufficiently large. Consider the distribution p= +1 o?) for rj Se 42 +10vlogmms and let % be its score function. Given samples from the standard Gaussian p" =N(0, with score function s", with probability at least 1 poly(m))
m0
1 O(Svlugm) but E [1((()) 5 (x))1] <
S2
E xmpp
g2
mo
Proof. Let X1...,, Xm p" be the m samples from N(0,02) With probability at least every X; S 2ooloomm m. Now, the score function of the mixture p is given by
poly(m)
((x)
+
I-n
7
For x S 2/ log m,
1 e O(S /lgg m))
I
3(x)
s
0
So.
[1((<)) s* (-)]]
<
1
O15./ogmm
σ²
On the other hand,
$2
E mmp
[|](()) s" (x)1] v/
mo²
27

---

E Discussion of [BMR20]
Here, present 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 class of -valued functions, all of with are 1/2 -Liisschitz. with values supported on the Euclidean ball with radius R, and containing uniformly good approximations of the true score 8t this ball. Given samples from qu, if we let št be the empirical minimizer of the score ecore-matching loss, then with probability at least 1 8,
d (log log + log !))
E Egrgge (x))(()) (x()))1) S (LR BBR+B*
B)²
log" (.RR,RRR (F)(F) +
n
Here, B is bound [0)], and (F) is the Rademacher complexity of F over samples.
In the setting we consider, for the class of neural networks with weight vector such that ||0||x S θ with P parameters and depth D, it was shown in [Se124] that
Rn(FF & RVd (OVP). VD vn
Moreover, the true score is It de Lipschitz, that if further restrict ourselves neural networks have the same Lipschitzness, = R, can be bounded by vid
Thus, application of the theorem to our setting gives sample complexity bound of δ Ra (0² ()*P) }) for squared L score error O In order to support or
smoothed scores, we need to set R 2 yd for a sample complexity of Ô 122222 1/22 (02P)) ;) to learn approximation to 8, with squared L2 error O
03e²
So, we obtain the following corollary.
Corollary E.2. Let be a distribution over TRd supported over the Euclidean ball with radius R S O Vd/o.). Let F be the set of neural networks de (+), with weight vector 0, parameters and depth D, with |00||> O and values supported on the ball of radius R, and that are O(R/as) o.)- Lipschitz. Suppose F contains a network with weights 0 such that du- provides uniformly good approximation of the true score St over the ball of radius R. Given n samples from qu. if we let S be the empirical minimizer of the score matehig loss, then with probability 1 6.
E z-
[[]{(())) do- (x) Sō
for n > Ō
F P VD 1/)
(02P) oF.
To learn score approximations in L for all the relevant timesteps in order to achieve TV error and Wasserstein error 7 R, this implies a sample complexity bound of Ô 0/2 7
(O*P)PVD log 3
6/2 δ
3 (0² VDlog 1) for our final choice of N.
F
Utility Results
Lemma F.1 (From [GLP23I). Let f be an arbitrary distribution IRdd and let fs be the E-smoothed
version of f. That is, fx(x) = Ey- [(xx) dct(EE)-122 (//ppp/xp)ppppp (-2(x- f-=xx)=+ Y (x - Y))]. Let sg be the score function of fz. Let (X,Y, Y, Zz) be the joint distribution such that f. Zz ~ (0 Σ. are independent, and X
+ 7x ~ Sx. We have for TRd.
fx(2 + =
-x- 1---20 Zz 33 TT
E
(x(x)
Zu/z
so that
Sy (x)
[- 2z]
Zz
28

---

Lemma F.2 (From [HKZ12], restated), Let x be a mean-zero random vector in R that is E- subgaussian. That is. for every vector U,
IE (MMer))) I E0/2
Then, with probability 1 6,
| (T(E))
2/|E|110g
Lemma F.3. For 8y, the score function of an E-smoothed distribution where E o²1, we have that o sx(xx) is O(1/(111/) ((1//o)ssubgaussioon when fx. and |||||| = 1.
Proof. We have by Lemma F.1 that
55(x)
E Zzz/
Σ
So,
E 2~18
[10
sx(())}]
EF
v.-
Σ
fx
ZE|Z
[(v' E -1Zz)
Zx
kk
S o²
since 7>= ~ N(0
The claim follows.
Lemma F4. Let E = I2,, and let x ~ fz. We have that with probability 1 - 6,
d d log 1
||>5(1)]1 x
r²
Proof. Follows from Lemmas E.3 and F2.
Lemma F.5. For o0, La), with probability 1- 8.
log 1
z
Proof. Note that || is chi-square, so that we have for any 0 S 02/2,
(1 -1- 2(A/02))d12
The claim then follows by the Chernoff bound.
Lemma F6. For fg. with probability 1 - 8,
Zx
V d + log
E Z
a2
Proof. Since Zy ~ ~N Ta) so that | 2 is chi-square, we have that for any 0 < 02/2.by Jensen's inequality,
12g
12
E
zm fm
(1 2(A/o2))u/2
The claim then follows by the Chernoff bound. That is, setting 0² 0²/44 for any >
AEzgl
[zzl
Exwís
7
Proff
E Zx:Z
2t 5
2d/2 to
dlna 2r2
ed1
[d+lox 1 gd
For /= =
this is less than d.
29

---

Lemma F.7 ([KN]). Let X be a non-negative random variable such that for every 2 0, P 2 I exp( At) for some constant Then. for K
X|X|X 2 KJ K
log P K
Proof. Letp:= P|x Z K] and denote the distribution of X P. Consider the sequence of iid samples {X;):20 sampled from P. Let T be the first index i, where X; 2 K. Then the distribution
of XT the conditional distribution X given 2 K. For any m 0,
X7
((k 1)m < T S km)
sup (k- mm-skmm
X;
421
((k 1)m < T)
sup
X
(k-1)m<iskm
Now, 1 ((k 1)m < T) and (k- 1)66mmm X, are independent since 1 ((k - 1)m < T) depends only on (X:hie(1((--)))) 1)m] Thus,
E[X|X =|=
Σ
E [[ 1)m < E
sup
X
(k-1)m<isha) Siskm
k21
log m
(1 p) (1-1)m
[[[] +
1
log m
5 1 (1 pmm
E[X]
A
Choosing m so that ()- < gives the claim.
Theorem F.8 (Girsanov's s theorem). For E [0, T1, let Ct = = dB, where a Q- A-Brownian
motion. Assume Novikov's condition is satisfied:
E Q
exp
2
2
b|b 11 ds
< 00.
Then
E(C), == exp (f" 6e dB,
l"
J0 |6 112 cs
is Q-martingale and
B, = B, - 1 b. ds
is a Brownian motion under P where P := Q, the probability distribution with density {(C)
w.E.t. Q.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the main claims are all reflected in the scope and contributions, as discussed in the paper.
Guidelines:
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 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 long is clear that these goals are not attained by the paper.
2. Limitations
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 the related work and conclusion sections.
Guidelines:
The answer NA means that the paper has 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 (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn 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 the scope of the claims made, e.g., if the approach was only tested on few datasets or with 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
31

---

Answer: [Yes]
Justification: The main paper contains proof overviews, and the appendices contain the full rigorous versions of all proofs of all stated lemmas and theorems.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: We do not have any experiments. We have a small simulation that is just a illustration of a lower bound, which is very small in scope.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
32

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: We do not have any experiments. We have small simulation that is just illustration of a lower bound, which is very small in scope.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips...
onnooiccy olycyyyyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. cctpublic/ppeeccccccccccccc gwtpc//g/////////eeoeooo/ /Code//omdmsbiii
otw.eeeuumissisinooooo...o... sswsssolisooooooooooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: We do not have any experiments. We have a small simulation that is just a illustration of a lower bound, which is very small in scope.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: We do not have any experiments. We have a small simulation that is just illustration of a lower bound, which is very small in scope.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
33

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: We do not have any experiments. We have a small simulation that is just illustration of a lower bound, which is very small in scope.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that NeurIPS Code of Ethics https: h//pprrps//////././//// cctpublic//eieeccccceccc wtwtae/teiiitiieeeeiiieeeeeeeeee
didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification:
The authors read through and reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Since this work is entirely theoretical, there are no societal impacts, positive or negative.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
34

---

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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
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 dataset.
The authors should state which version of the asset used and, possible, include 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.
35

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithhaeee thcode. www.coo////oo//o datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. 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/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. Crowdsoureing 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 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 the supplemental material is fine, but if the main contribu- tion 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.
15. 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
36

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
37


Reviews:
[{"review_id": "fNmazVTMYN", "reviewer": "Reviewer_tUeu", "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.", "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. \n2. 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. \n3. 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": "There is not potential societal impact of this work since it is a completely theoretical work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper is clearly written and the presentation is fairly good. The theorems and lemmas proposed in this paper are sound and solid.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and questions.  As you state, prior work\nlike Chen et al. have shown that \"sampling is as easy as learning the\nscore.\"  Thus the main open question is: how easy *is* learning the\nscore?\n\nWe think that question is clearly important enough for top tier\nmachine learning conferences.  We address it by providing the *first* polynomial sample complexity bound, under the assumption that the score can be effectively represented by neural networks. And this assumption is\nboth reasonable (neural networks have proven to be surprisingly\npowerful function approximators) and necessary (if the distribution's\nscore isn't well approximated by a neural network, diffusion won't\nwork).\n\n**Assumption A2**:\n\nThank you for the suggestion, which is the consensus of reviewers.  We will include the precise definition of ``sufficiently small\" into the main text in the final version of the paper. As stated in C.3., the required $L^2$ error is $\\frac{\\delta \\varepsilon^3}{N^2 \\sigma^2\n\\log \\frac{d}{\\gamma}}$.\n\n**Technical novelties**:\n\nHere is a brief summary of our technical contributions:\n\n* We exploit the fact that recent works on *sampling* only require an error of $\\varepsilon^2/\\sigma_t^2$ for each $t$ to show a sample complexity bound *independent* of $\\sigma_t$ for score estimation with this error.  That is, the accuracy required fortuitously matches the accuracy achievable at each scale $\\sigma_t$, with a sample complexity independent of $\\sigma_t$.\n    \n* This lets us run until $\\sigma_t$ is extremely small; this leads to a  sample complexity *logarithmic* in the final Wasserstein error.\n\n* To show our score estimation result for a single time $t$, instead of making the strong assumption that the distribution is bounded as in [BMR20], we observe that *with high probability* the score at time $t$ is bounded in terms of $\\sigma_t$. This observation, combined with a technical argument allows us to remove the $R^3$ dependence in the sample complexity in [BMR20].\n\n\n\n* Other contributions that we will refrain from describing in detail here in the interest of space -- we learn the score in a new $1-\\delta$ robust sense, rather than standard $L^2$, to circumvent barriers in learning in $L^2$, and we make use of a careful net argument to obtain our *exponential* improvements in the  dependencies on the depth and range of the neural network relative to [BMR20].\n    \n**VE vs VP:**\n\nThe VE and VP processes are simply reparameterizations of each other. That is, if $x_t$ denotes a solution to the VE SDE, then $y_t = e^{-t} x_{e^{2t}-1}$ is a solution to the VP SDE. The reverse process and its discretization can be easily adjusted to match this change of variables.  So, these processes are pretty much identical, and the same results hold.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kbtNTSN2HU", "reviewer": "Reviewer_6Nj2", "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$.", "questions": "See weaknesses.", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper derives better sample complexity results for diffusion models. The bound in this work is exponentially better than the existing results.\n2. The paper discusses the difficulties of learning the score in $L^2$. Two examples are provided to show this challenge.", "weaknesses": "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. \n2. 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?\n3. 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.  \n\n[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.\n\n[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).\n\n[3] Wibisono, Andre, Yihong Wu, and Kaylee Yingxi Yang. \"Optimal score estimation via empirical bayes smoothing.\" arXiv preprint arXiv:2402.07747 (2024).\n\n[4] Zhang, Kaihong, et al. \"Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions.\" arXiv preprint arXiv:2402.15602 (2024).\n\n[5] Oko, Kazusato, Shunta Akiyama, and Taiji Suzuki. \"Diffusion models are minimax optimal distribution estimators.\" International Conference on Machine Learning. PMLR, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Comparison to previous work\n----\n\nWe would like to clarify that most of the prior work in the literature, including the works you mentioned, ask about the *approximation* power of neural networks for representing the score of *arbitrary* distributions, and/or make strong assumptions on the distribution. Typically, for $d$ dimensional distributions, the number of parameters necessary is *exponential in $d$* -- indeed, the bounds shown in all the works you mentioned suffer from this exponential dependence. But in practice, neural networks are surprisingly powerful function approximators of real-world functions, and they seem to be able to represent $d$-dimensional distributions with much less than $\\exp(d)$ parameters. \n\nTo circumvent this issue, we take a different route: we assume that a $P$ parameter neural network can approximate the score of the distribution that we are trying to learn.   Note that such an assumption is *necessary*: if our network cannot even represent the scores, there is no hope of learning it.   \n\nWe then ask: if $P$ parameters suffice, how many samples do we need to learn this approximation? We show that the sample complexity for this problem is only *polynomial* in all relevant parameters, and even logarithmic in the Wasserstein error, unlike *all* prior works. We believe that this question and our answer more accurately capture the situation in practice than the one above.\n\nWe appreciate the feedback to provide a table -- please see the general response. \n\nNote that [HRX24], which is focused on the two-layer network case in the NTK regime, actually makes the *assumption* that gradient descent in RKHS using a **sufficient** number of samples is sufficient to learn the score (Assumption 3.11). Our paper *proves* that a small number of samples is sufficient to learn the score under the reasonable assumption that the network can represent it; moreover, we provide a quantitative  bound that is polynomial in all relevant parameters. \n\n\n\nTechnical contributions\n---\n\nHere is a brief summary of our technical contributions:\n\n* We exploit the fact that recent works on *sampling* only require an error of $\\varepsilon^2/\\sigma_t^2$ for each $t$ to show a sample complexity bound *independent* of $\\sigma_t$ for score estimation with this error.  That is, the accuracy required fortuitously matches the accuracy achievable at each scale $\\sigma_t$, with a sample complexity independent of $\\sigma_t$.\n\n* This lets us run until $\\sigma_t$ is extremely small; this leads to a  sample complexity *logarithmic* in the final Wasserstein error.\n\n* To show our score estimation result for a single time $t$, instead of making the strong assumption that the distribution is bounded as in [BMR20], we observe that *with high probability* the score at time $t$ is bounded in terms of $\\sigma_t$. This observation, combined with a technical argument allows us to remove the $R^3$ dependence in the sample complexity in [BMR20].\n\n* Other contributions that we will refrain from describing in detail here in the interest of space -- we show that we learn the score in a new $1-\\delta$ robust sense, rather than standard $L^2$ to circumvent barriers in learning in $L^2$, and we make use of a careful net argument to obtain our *exponential* improvements in the  dependencies on the depth and range of the neural network relative to [BMR20].\n\n\nSection 4\n---\n\n- As above, section 4 shows that learning in $L^2$ *requires* $\\text{poly}(1/\\gamma)$ samples to obtain a final Wasserstein error of $\\gamma$. We can circumvent this barrier by learning the score in our weaker $1-\\delta$ robust sense, to obtain a final sample complexity only logarithmic in $1/\\gamma$. \n\n- Minimax optimality: As explained above, prior works show minimax optimality with respect to the class of arbitrary distrbutions, which results in an exponential in $d$ sample complexity. This does not accurately capture the situation in practice -- neural networks are surprisingly powerful approximators of real-world functions and seem to be able to represent $d$ dimensional distributions with much less than $\\exp(d)$ parameters/samples. We circumvent this by making the reasonable assumption that the scores of the distribution can be represented with a $P$ parameter neural network.\n\n[HRX24]: Neural Network-Based Score Estimation in Diffusion Models: Optimization and Generalization. Yinbin Han, Meisam Razaviyayn, Renyuan Xu. https://arxiv.org/abs/2401.15604", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "C3tVvQBpMG", "reviewer": "Reviewer_r7NG", "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.", "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?\n\n2. What is the quantitive requirement on \\mathcal{F} in Assumption 2? What does the \"sufficiently small\" mean?\n\n3.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": "Not applicable.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper improves the existing bound for training a diffusion model with sufficiently expressive neural network. They analyze the barrier for L_2 accuracy as a criterion and propose to use a (1-\\delta)-quantile error in their analysis, which would finally scale polylogarithmically in 1/\\gamma, and suffices for fast sampling via the reverse SDE. Basically, the organization of this paper is good, and the proof sketch is clear, though it is a hard to check all the details.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your comments and are glad that you like and support the paper.\n\n**The assumption that networks can\n  represent the score is somehow strong.**\nWe agree that it is somewhat strong, but view this more as a statement\nabout data; analogous to \"the data is sparse in X basis\".  Over the\npast decade neural networks have proven to be surprisingly effective\nfunction approximators.  We ask: supposing this is true, how many\nsamples do you need to accurately learn a generative model?\n\n(And if it's not true, then trying to learn the score with a neural network is doomed to fail regardless of how many samples you use.)\n\n**Q1 (Applying Lemma 1.4  for all N):** That's right, Theorem 1.2 applies Lemma 1.4 in a union bound over\nthe N time steps to invoke Lemma 1.3.  Since the dependence on\nprobability $\\delta_{train}$ is logarithmic, this loses at most a\n$\\log N$ factor.  Not good if $N$ is really $\\infty$, but fine for more\nreasonable values of $N$.\n\nThat said, there is an interesting question here.  In our analysis, it\ndoesn't matter if the image samples are chosen independently or\njointly across different scales.  In practice, they are typically\nchosen jointly (so each sample image is then used at all noise\nscales).  It seems plausible to us that jointly sampling images could\nimprove the sample complexity in Theorem 1.2 from $d^2$ down to\n$d$, by correlating the \"bad\" events across scales.\n\n**Q2 (Quantitative Assumption 2):** We give the precise bound in Theorem C.3 in the appendix.  It's a\npolynomial bound, namely $\\frac{\\delta \\varepsilon^3}{N^2 \\sigma^2\n\\log \\frac{d}{\\gamma}}$.\n\n\n**Q3 (Other function classes):** Our proof actually applies to any Lipschitz activation function,\nwe should have specified this.  We think measuring a neural network by\nits parameter count / weight / depth is a simple way to bound its\ncomplexity.  One can certainly analyze other classes -- Lemma A.2\napplies to arbitrary finite function classes, and one can take a net\nfor other classes -- but we're not sure of any more general statement\nthat applies cleanly to neural networks.\n\n(Some work (e.g. BMR20) tries to use Rademacher complexity to get a\ngeneral statement, but the Rademacher complexity of neural networks is\nexponential in their depth so this is unsatisfying.)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nRdZXOkI1P", "reviewer": "Reviewer_acEK", "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.", "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?\n\n\n2. 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?  \n\n3. What are $\\gamma$ and $R$ in line 41? They seem to be undefined up to that point.\n\n4.  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.\n\n5. 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.\n\n6. In Setting 1.1, does $P$ denote the number of parameters per layer?", "limitations": "Not Applicable.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main contribution is to improve the existing sample complexity for learning the score function, exponentially with respect to some on $\\Theta$, $\\gamma$, and $D$. This may contribute to a better theoretical understanding of diffusion-based models.", "weaknesses": "- 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.\n\n- Some parts of the paper are not clear enough (see Questions section)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thorough review and valuable suggestions on the presentation of the paper. We appreciate the time and effort you have invested in providing this feedback. \n\nImplications of our work\n----\n\nOur work is the first to show a polynomial sample complexity for learning a diffusion models using a deep network under a reasonable assumption -- that the scores of the distribution can be represented using \na $P$-parameter neural network. From a theoretical point of view, we believe this is a significant contribution -- it was not clear prior to our work whether minimizing the score-matching objective is sufficient to learn a diffusion model using a small number of samples. \n\nMore broadly, we hope that this style of assumption will inspire future work in understanding diffusion models and other deep learning models.\n%We would like to highlight the concrete new insights our research contributes to the field of diffusion models.\n\n\nResponses to specific questions\n----\n\n> *Can the authors develop more why and when the dependence on $\\theta$, $\\gamma$, $D$ and $P$ is more important than the dependence on $\\varepsilon$? Can a numerical estimate be provided here?*\n\nTo illustrate the dependence on these parameters, we provide some natural choices of parameters:\n\n- TV error $\\varepsilon = 0.01$.\n- Wasserstein error $\\gamma = 0.01$.\n- Space dimension $d = 12288 = 64 \\times 64 \\times 3$.\n- Total Parameter Number $P = 270M = 2.7 \\times 10^8$.\n- Network Depth $D = 12$.\n- Parameter Weight Range $\\Theta = 5$.\n\nFor parameter number and the space dimension, we used the parameters in stable diffusion[1]. Our bound gives $\\frac{d^2 PD}{\\varepsilon^3} \\cdot \\log \\Theta \\cdot \\log^3 \\left(\\frac{1}{\\gamma}\\right) \\approx 7.7 \\times 10^{25}$, compared to the previous bound of $\\frac{d^{5/2}}{\\gamma^3 \\varepsilon^2} \\left(\\Theta^2 P\\right)^D \\sqrt{D} \\approx 5.2 \\times 10^{138}$.\n\nWhile we do not claim that $\\theta$, $\\gamma$, $D$, and $P$ are universally more important than $\\varepsilon$, our results demonstrate a significant *exponential* improvement in $D$ and $\\gamma$ with only a minor loss in $\\varepsilon$, resulting in a substantially better overall bound.\n\n> *Is it true that assumption A2 implies $\\inf_f \\mathbb{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?* \n\nActually, we only need the $L^2$ error to be polynomially small, namely \n$\\frac{\\delta \\cdot \\varepsilon^3}{N^2 \\sigma^2_{T - t_k} \\log \\frac{d}{\\gamma}}$,\nas specified in Theorem C.3. We will put this in the main body of the paper.  Intuitively, this assumption states that neural networks can effectively represent the score function. This assumption is\nboth reasonable (neural networks have proven to be surprisingly\npowerful function approximators) and necessary (if the distribution's\nscore isn't well approximated by a neural network, diffusion won't\nwork).\n\n> *What are $\\gamma$  and $R$ in line 41?*\n\nIn line 41, $R$ represents the radius of the support size of the distribution, and $\\gamma$ is a parameter used to specify the Wasserstein error.\n\n> *In Setting 1.1, does $P$ denote the number of parameters per layer?*\n\nIn Setting 1.1, $P$ denotes the total number of parameters, not just per layer. We will clarify this in the final version to avoid any ambiguity.\n\n[1] Rombach, Robin, et al. \"High-resolution image synthesis with latent diffusion models.\" Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their feedback. 

One common request was for a table placing our results in context of related work.  Here it is:

| **Work** | **Sample Complexity**                                                                                                   | **Notes**                                              |
|-------------|------------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------|
| [ZYLL24]    | $\widetilde O\left( \frac{1}{\epsilon^2 \gamma^{d/2}}\right)$                                                                | Assuming Distribution is $\alpha$-subgaussian, satisfies an LSI.  Gaussian Kernel estimator, rather than NN.                       |
| [WWY24]     | $\widetilde O\left(\frac{d^{d/2} \alpha^d R^{d+2}}{\gamma^{d+2} \epsilon^{d+4}} \right)$                                     | distribution is $\alpha$-subgaussian. Gaussian Kernel estimator, rather than NN.                       |
| [OST23]     | $\widetilde O\left( \frac{1}{\epsilon^{O(d)}}\right)$                                                                        | Density supported on $[-1, 1]^d$, belongs to a Besov space       |
| [CHZ+23]    | $\widetilde O\left(\frac{1}{(\epsilon \gamma)^{O(d)}} \right)$                                                               | Assuming density supported on a $d$-dimensional subspace         |
| [BMR20]     | $\widetilde O\left(\frac{d^{5/2}R^3}{\gamma^3 \epsilon^2} \left(\Theta^2 P \right)^D \sqrt{D} \log \frac{1}{\delta} \right)$ | Assuming NN can represent scores, distribution is bounded        |
| Ours        | $\widetilde O\left(\frac{d^2}{\epsilon^3} PD \log \Theta \log^3 \frac{1}{\gamma} \right)$                                    | Assuming NN can represent scores                                 |

Our paper primarily discusses [BMR20] because it is the only related work that is not exponential in the data dimension $d$; but as you can see, it is exponential in the depth $D$ of the neural network.  
Ours is the only work giving sample complexity polynomial in these parameters.


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

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

[OST23]: Oko, Kazusato, Shunta Akiyama, and Taiji Suzuki. "Diffusion models are minimax optimal distribution estimators." International Conference on Machine Learning. PMLR, 2023.

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

[BMR20]: Generative Modeling with Denoising Auto-Encoders and Langevin Sampling. Adam Block, Youssef Mroueh, Alexander Rakhlin. https://arxiv.org/abs/2002.00107

Meta-review: 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,
Decision: Accept (poster)