Convergence for score-based generative modeling with polynomial complexity
Authors: Holden Lee
Jianfeng Lu
Yixin Tan
Venue: NeurIPS 2022 Accept (2022)
Keywords: Langevin sampling
score-based generative modelling
diffusion model
reverse SDE
annealing
prediction-correction

Abstract:     Score-based generative modeling (SGM) is a highly successful approach for learning a probability distribution from data and generating further samples. We prove the first polynomial convergence guarantees for the core mechanic behind SGM: drawing samples from a probability density $p$ given a score estimate (an estimate of $\nabla \ln p$) that is accurate in $L^2(p)$. Compared to previous works, we do not incur error that grows exponentially in time or that suffers from a curse of dimensionality. Our guarantee works for any smooth distribution and depends polynomially on its log-Sobolev constant. Using our guarantee, we give a theoretical analysis of score-based generative modeling, which transforms white-noise input into samples from a learned data distribution given score estimates at different noise scales. Our analysis gives theoretical grounding to the observation that an annealed procedure is required in practice to generate good samples, as our proof depends essentially on using annealing to obtain a warm start at each step. Moreover, we show that a predictor-corrector algorithm gives better convergence than using either portion alone. 

Convergence for score-based generative modeling with polynomial complexity
Holden Lee
Jianfeng Lu Department of Mathematics Duke University j jianf eng@math duke. edu
Department of Applied Mathematics and Statistics Johns Hopkins University hlee2838jhu. edu
Yixin Tan
Department of Mathematics
Duke University
yixin. tan@duke..... edu
Abstract
Score-based generative modeling (SGM) is highly successful approach for learn- ing probability distribution from data and generating further samples. We prove the first polynomial convergence guarantees for the core mechanic behind SGM: drawing samples from probability density p given of V In p) that is accurate L (p)... Compared to previous works, we do not incur enror that grows exponentially in time that suffers from curse of dimension- ality. Our guarantee works for any smooth distribution and depends polynomially its log-Sobolev constant. Using our guarantee, give theoretical analy- sis of score-based generative modeling, which transforms white-noise input into samples from learned data distribution given score estimates at different noise scales, Our analysis gives theoretical grounding to the observation that an an- nealed procedure required in practice generate good samples, as our proof depends essentially on using annealing to obtain a warm start at each step. More- over, we show that a mrdictor-correede algorithm gives better convergence than using either portion alone.
estimate (an estimate
Introduction
A key task in machine learning is to learn probability distribution from data, in way that al- lows efficient generation of additional samples from the learned distribution. Score-based genera- tive modeling (SGM) is one empirically successful approach that implicitly learns the probability distribution by learning how transform white noise into the data distribution, and gives state- of-the-art performance for generating images and audio [SE19] [9a++19] Gra+19 SE20 [Son+20b) Men+21] Son+21b; [So+22la] Jin+22]. It also yields a conditional generation process for inverse problems DN21]. The basic idea behind score-based generative modeling is to first estimate the score function from data [Son+20a] and then to sample the distribution based on the learned score function. Other approaches for generative modeling include generative adversarial networks (GANs) Goo++14 ACBT 17, normalizing flows [DSB16 16]. variational autoencoders [KW19], and energy- based models [ZML16]. While score-based generative modeling has achieved great success, its theoretical analysis is still lacking and the focus of our work.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.1 Background
General framework. The score function of a distribution P with density p is defined as the gra- dient of the log,pdf, V p. Its significance arises from the fact that knowing the score function allows running a variety of sampling algorithms, based on discretizations of stochastic differential equations (SDE's), to sample from p. SGM consists of two steps: first, learning an estimate of the score function for a sequence of "noisy" versions of the data distribution Paaa. and second, using the score function in lieu of the gradient of the log-pdf in the chosen sampling algorithm. We now describe each of these steps more precisely.
First, a method of adding noise to the data distribution is fixed; this takes the form of evolving (forward) stochastic differential equation (SDE) starting from the data distribution. We fix a se- quence of noise levels 01 < ... < dx. For {oi..... ON ), let the resulting distributions be P.- and the distributions conditional on the starting data point be Pa (-(x). Typically, 01 is chosen so that Poę Paata and P is close to some "prior" distribution that is easy to sample from, such as N N(0, xx Ia). While the score V Pup cannot be estimated directly, turns out that de-noising ob- jective that is equivalent to the score-matching objective can be calculated (SE19]. This de-noising objective can be estimated from samples (X, X) where X ~ (- The objective is represented and optimized within an expressive function class, typically neural networks, to obtain a I.2 -estimatee of the score, that is, se (2, o²) such that
E [Isso 0²) V (x)
(1)
is small.
The reason we estimate the score function V Vln is that there are a variety of sampling algorithms-based on simulating SDE's-that can sample from given access to V In including Langevin Monte Carlo and Hamiltonian Monte Carlo. The second step is then to use the estimated score function sp t) in lieu of the exact gradient in the sampling algorithm to successively ob- tain samples from Poz..... Poz. This sequence interpolates smoothly between the prior distribution (e.g., N (0, x La)) and the data distribution Paan: such an "annealing" or "homotopy" method is required in practice to generate good samples [Son+20b].
Examples of SGM's. There have been several instantiations of this general approach. (SE19 add gaussian noise to the data and then use Langevin diffusion at a discrete set of noise levels ON ... > 01 as the sampling algorithm. [Son+20b] take the continuous perspective and con- sider more general framework, where the forward process can be any reasonable SDE. Then natural reverse SDE evolves the final distribution Paž back to the data distribution; this process can be simulated with the estimated score. They consider methods based on two different SDE's: score-matching Langevin diffusion (SMLD) based adding Gaussian noise and denosing diffusion process. Note
probabilistic models (DDPM) (Soh+15) HJA20), based on the Ornstein-Uhlenbee that a difference with MCMC-based methods is that these SDE's are evolved for fixed amount of time, rather than until convergence. However, they can be combined with MCMC-based methods such as Langevin diffusion in the predictor-corrector approach for improved convergence. [DVK21) include Hamiltonian dynamics: they augment the state space with a velocity variable and consider critically-dampe' version of the Ornstein- Uhbeebbek process. Finally. we note the work of (De) +21], who introduce the Diffusion Schrödinger Bridge method to learn a diffusion that more quickly transforms the prior into the data distribution.
We will give a general analysis framework for SGM's that applies to the algorithms in both SE119 and [Son+20b))
1.2 Prior work and challenges for theory
Although the literature on convergence for Langevin Monte Carlo [DM17 CB18, Che+18, Dal17, DK19; MMS20 EHZ21] and related sampling algorithms is extensive, prior works mainly consider the case of exact or stochastic gradients. contrast, by the structure of the loss function (.. the score function learned in SGM is only accurate in (2)))). This poses a significant challenge for analysis, as the stationary distribution of Langevin diffusion with 1.2 (p)acuuuta gradient can be arbitrarily far from p (see Appendix D). Hence, any analysis must be utilizing the short/medium-

---

term convergence, while overcoming the potential issue of long-term behavior of convergence to an incorrect distribution.
[MR220 give the first theoretical analysis of SGM, and in particular, Langevin Monte Carlo with (p)-acurraee gradients. First, they show using uniform generalization bounds that optimizing the de-noising autoencoder (DAE) objective does in fact give a L (p)-accurate score function, with sample complexity depending on the complexity of the function class. They analyze convergence of LMC in Wasserstein distance. However, the error they obtain (Theorem 13) only decreases e//a where & is the accuracy of the score estimate-so it suffers from the curse of dimensionality-aan increases exponentially in the time that the process is run, the dimension, and the smoothness of the distribution, as in ODE/SDE discretization arguments that do not depend on contractivity.
[De +21] give analysis for [Son+20b] in TV distance that requires a L -accurate score function and depends exponentially on the amount of time the reverse SDE is run. Although exponential de- pendence is bad in general, it is mollified using their Diffusion Schrödinger Bridge (DSB) approach, as it allows running for a shorter, fixed amount of time, before the forward SDE converges to the prior distribution. However, this supposes that good solution can be found for the DSB problem, and theoretical guarantees may be difficult to obtain.
We overcome the challenges of analysis with aaccuurte gradient, and give the first analysis with only polynomial dependence on running time, dimension, and smoothness of the distribution, with rates that are fixed power of s. Our convergence result is in TV distance. We assume only smoothness conditions and a bounded log- Sog-Soboeev constant of the data distribution, a weaker con- dition than the dissipativity condition required by [BMR20). We introduce a general framework for analysis of sampling algorithms given L'-accurate gradients (score function) based on constructing "bad set" with small measure and showing convergence of the discretized process conditioned on not hitting the bad set. We use our framework to give an end-to-end analysis for both the algorithms in [SE19] and [Son+20b), and illuminate the relative performance of different methods in practice.
1.3 Notation and organization
Through out the paper, p(ar) x ev((x) denotes the target distribution in Rdd and V Rdd - R is referred to as the potential. We abuse notation by identifying measure with its density when context allows. We write a A b := minfa, (a, b) and a b == max max(a, b). We use a O(b) or b = D(a) to indicate that I Cb for universal constant C > 0. Also, we write constants e'
(b)) if there are universal cb, and the notation Ö(-) means it hides polylog factors in the parameters. Definite integrals without limits are taken over Rdd
such that eb
In Section 2 we explain our main results for Langevin Monte Carlo with (((p)-accurate score esti- mate and use it to derive convergence bounds for the annealed LMC method of (SE1). In Section we give our main results for the predictor-corrette algorithms of [Son+20b] based on simulating reverse SDE's. Our proofs are based on a common framework which we introduce in Section Full proofs are in the appendix.
2 Results for Langevin dynamies with estimated score
Let p(x) & (v()) be a probability density on Rd such that V C². Langevin diffusion with stationary distribution is the stochastic process defined by the SDE
dx, VV dt + d2
where W/ is standard Brownian Motion in Rdd The rate of convergence p in x² and KL diver- gences are given by the Poincaré and log- Sobolev constants of p, respectively; see Section [E.] To obtain the Langevin Monte Carlo (LMC) algorithm, take the Euler-Murayame discretization of the SDE. We define LMC with score estimate (x) (v and step size h by
D(K+1J& 1JA = Teh + h s(Zak) + /2h- Ekk, where ExA N(0, Ia).
(LMC-SE)
We make the following assumptions on the density p and the score estimate 8, which we will use throughout this paper.
Assumption 1. is probability density on Rd such that the following hold.
3

---

1. In C' and L-smooth, that is. is L-Lipschitz. We assume L 2 1.
2. satisfies a log-Sobolev inequality with constant CLs. We assume Cis 2 1.
3. (Moments)
|Baal < M1 and Ep ||=|| M2-
We note that the uniform Lipschitzness assumption (1) helps ensure a unique strong solution to the Langevin diffusion, as in [BMR20). One special case where one can prove Lipschitzness for all t is when po is strongly log-concave [ee+21, Lemma 28). Although satisfying a log-Sobolev inequality (3) is significant assumption, it standard for analysis of Langevin Monte Carlo [VWI9]. It is much weaker than assumptions in previous works [BMR20]. including log-concave distributions and distributions satisfying strong dissipativity, and is stable under bounded perturbations. See Section E. for background on functional inequalities.
Assumption 2. Let p be a given probability density on H such that In p C³, The score estimate 8 R² + Rd satisfies the following.
1. is C¹ function that is Liplipschitz. We assume Lg
2. The error in the score estimate is bounded in L2:
| In
=1| =1] ()llVV))(())) s².
2.1 Langevin with a'eaccuratee score estimate
Our first main result gives an error bound between the sampled distribution and p. assuming 2 accurate score function estimate.
Theorem 2.1 (LMC with L -ccaccuatee score estimate). Let p Ed + R be a probability density satisfying Assumption 1 with L Z 1 and Rd IRd be a score estimate satisfying Assump-
tion 2 Consider the accuracy requirement in TV and x²: 0 < ETV < 1, 0 < Ex < 1, and
suppose Surthermore the starting distribution satisfies x2(ooll)) S x Then if
ETVE
E =
(2)
dL'C
5/2
then running LMC-SE with score estimate s, step size h = dT. and time T
o (Cissnn 2Kg results in distribution pr such that pr is STV-far in TV distance from dis- tribution Pr, where Pr satisfies (prlll)) S exx In particular, taking εx ETV, we have the error guarantee that TV(pr,P) S 2eTv.
Note that the error bound only achieved when running LMC for moderate time; this is consistent with the fact that the stationary distribution of LMC with a L--score estimate can be arbitrarily far from p. Note also that we need warm start in >dviieege: the required accuracy for the score estimate is inversely proportional to Kx- Intuitively, we must suffer from such dependence because if the starting distribution is very far away, then there is no guarantee that |/ In p(rz) - sxx;)|2 is small on average during the sampling algorithm. Finally, although we can state result purely in terms TV distance, we need this more precise formulation to prove result for annealed Langevin dynamics.
obtain fixed errors eTV, ex
2.2 Annealed Langevin dynamics with estimated score
In light of the warm start requirement in Theorem 2.1 we typically cannot directly sample from Pdata or its approximation. Hence, (SE19) proposed using annealed Langevin dynamics: con- sider sequence of noise levels ON Poa, Soa being the density of N (0,,0 For large enough
> 01
giving rise sequence of distributions
Po........ Po? S Pdata, where paa ON, Po, R Por, provides a warm start to Po We then successively run LMC using score estimates for Pog. with the approximate sample for Pož giving a warm start for Pat algorithm and error estimate.
We obtain the following

---

Algorithm Annealed Langevin dynamics with estimated score (SE19)
INPUT: Noise levels S σi ... < оиi score function estimates Fm) (estimates of V Vin(p= * Poz, step sizes hi,, and number of steps Nm for 1 S m S M. Draw x(M+1) (O, o Ta)-
for m from M to do
Starting from 4i =/)") (m++1) run (LC-SE) with s(x, Jm) and step size hm for Nm steps,
and let the final sample be ((m))
end for
OUTPUT: Return r(), approximate sample from p PPg-
Theorem 2.2 (Annealed LMC with La-accurate score estimate). Let p R - R be a probability
density satisfying Assumption 7 for M1
O(d), and let paa := p * 4p... Suppose farthermore that
A In pap paz is L- L-Lipschitz for every o 2 O. Given min > 0, there exists a sequence Gmin = 01 <
OM with M- =0 (Vdlog
dCis
such that for each m, if
V In(po;) -s(s, s(,, LP(P,2)
Bp.a. [1 VIVmo (x) s(x, o(x,,
4.5
with =
TV
d3.25 L2
then 2(0) is sample from distribution 9 such that TV (o.) S eTV-
Note that we assume score estimate with error at all noise scales; this corresponds to using an objective function that is a maximum of the score-matching objective over all noise levels, rather than an average over all noise levels more commonly used in practice. However, these two losses are at most a factor of M apart.
The proof shows that the noise levels can be chosen as a geometric sequence, which matches the choice used in practice [SE20). The additional dependence on d and вTV Theorem 2.2 compared to Theorem 2.1 comes from requiring a sequence of ((vd) noise levels and an additional factor in x2 -iveeeeree we suffer at the beginning of each level m. In the next section, we will find that using a reverse SDE to evolve the samples between the noise levels-called predictor step-will improve the rate and time complexity.
3 Results for reverse SDE's with estimated score
To improve the empirical performance of score- bosee generative modeling, [Son+20bb consider a general framework where noise is injected into data distribution Pdata via forward SDE,
dī f t) dt + g(t) dwi. E [O,T],
where To Po Pauta- Let denote the distribution of Te (P: is used instead of pt to distin- guish with the Gaussian-convolee distribution used in Annealed Langevin dynamics as $2.2) Remarkably, H. also satisfies a reverse-time SDE,
di, (f, t) (nt)"V + g() EE [0.
where wy is backward Brownian Motion [And82]. By carefully choosing f and g, we can expect that Pr is approximately equal to some prior distribution दr (e.g., centered Gaussian) which we can accurately sample from. Then we hope that starting with some Gr Pprior running the reverse-time process, we will get a good sample Úo Go R Pdiaa-
Gr ss fr and
The case where f = 0 and = 1 recovers the simple case of convolving with Gaussian as used in $2.2) note, however that the reverse-time SDE differs from Langevin diffusion in having larger (and time-varying) drift relative to the diffusion. [Son+20b) highlight the following two special cases. We will focus on DDPM while noting that our analysis applies more generically.
SMLD Score-matching Langevin diffusion: f = 0. In this case, p. To * 'f 9(5)² de so [Son+20b] call this variance-exploding (VE) SDE. As is common for annealing-basse
5

---

algorithms, (SE19] Son+20b] suggest choosing an exponential schedule, so that g = ab for constants a, We take Pprior = (O. (s)) ds Ia).
DDPM Denoising diffusion probabilistic modeling: f(x, t) - - This is an Ornstein- Uhlenbeck process with time rescaling, Pt M Lo a(*) ds;Po --- s(e) das where (x)x) = az. [Son+20b] call this a variance- preservvinn (VP) SDE, as the variance con- verges towards Ip- Because it displays exponential convergence towards N (0, La), it can be run for smaller amount of normalized time So gs)) ds. [Son+20b] suggest the choice g(t) vb+ at. We take Pprior N(0, (1 - e s(e)* de de)Ia) = N(0, Ia).
To obtain algorithm, we consider the following discretization and approximation of 4 note that in all cases of interest the integrals can be analytically evaluated. We reverse time so that t corresponds to T t of the forward process. As are free to rescale time in the SDE, we assume without loss of generality that the step sizes are constant. The predictor step is
(k+11)h
2(b+11 Ekh -Jaa
[s(z
g(( 1)2 s(zkn, T kh)] dt - T-
(k+T))
g(T tt) dwr,
where [ (k++2)k -t" dw; is distributed as N N0, Jih g(T -t² dt Ia). Following (Sb)+20b), we call these predictor steps as the samples aim track the distributions Pr рy- Note that flip the time. For simplicity of presentation, we consider the case though the choice of the schedule does matter practice, what really matters in our theoretical analysis is the integral Je dss This means that different choices of are related by only a can always choose total times T and T,, such that
(k+1))
1. We note that al-
rescaling of time, i.e. for different g and Jo g(s) = -oe ((s)&ss. While it seems that choosing large g(t) could reduce the total time T, in our analysis (e.g., Lemma C.15) we need the time step-size h to be O(1/g(T)²) and hence the total computational cost, which is roughly (T/h), does not change significantly.
estimate, DDPM). Let Pamt Rd R be a proba- bility density satisfying Assumption with M,- = Od)), and let Pt be the distribution resulting from evolving the forward SDE according to DDPM with g Suppose Surthermore that V ln Pr is L-Lipschitz for every & 2 O, and that each s(,,1) satisfies Assumption Then if
Theorem 3.1 (Predictor with L -acuurate
L.) (In(((s)))) v Cis (isL((L/Erv))) = ( ((aSt di 5/2 (L (LV
(
etv
running P starting from Prrior for time T θ (In(Cisd) V Cis In
and step size h
cTV
dry CistCis Cis(Cs+d)uNt. results in a distribution qr so that TV Pama) S STV-
more precise statement of the Theorem can be found in the Appendix. Although we state our theorem for DDPM, we describe in Appendix Chow it can be adapted to other SDE's like SMLD and the sub-VP SDE; the primary SDE-dependent bound we need is a bound on V In pe Because the predictor tracking a changing distribution Pt. we incur more error terms and worse dependence on parameters (Cis. L) than in LMC (Theorem 2.I). Motivated by this, we intersperse the predictor steps with LMC steps-called corrector steps this context-to give additional time for the process to mix, resulting in improved dependence parameters.
Theorem 3.2 prrddictor-correcte with 2 accurate score estimate). Keep the setup of Theorem 3.1
Then for e = O (1411//))( (cdn if
etv 5/2
8 8=0
(5)
d.L.
In(1/E))
then Algorithu 2 with appropriate choices of T = e (In(Cisd) V Cis log (et Nmw correc- for step sizes hmm and predictor step size h produces sample from distribution qr such that TV (gr. Pdaaa) < eTV.

---

Algorithm 2 Predictor-corrector method with estimated score [Son+20b]
INPUT: Time T, predictor step size h; number of corrector steps Nm per predictor step, corrector step sizes hm Draw 20 Pprior from the prior distribution.
for m from 1 to T/h do (Predictor) Take step of (P) to obtain Zmih from F(m with g as in SMLD DDPM
(Corrector) Starting from 2mh,0 = 2mh, run (LMC-SE) with s(2, T mm) and step size h.m
for . steps, and let Zmb f- Zmh,N. end for
OUTPUT: Return 27, approximate sample from Pdata-
The assumption on STy for convenience in stating our bound. In comparison using the predictor step alone (Theorem 3.1 note that in the bound on e, we obtain the improved rate of the corrector step as in Theorem 2.1| this is because the predictor step only needs track the actual distribution in x" di-divergence with emror (1). and the final corrector steps are responsible for decreasing the error ETV. In comparison to the Annealed Langevin sampler (Algorithm Theorem 2.2), which can be viewed as using the corrector step alone, adding predictor step provides a better warm start for the distribution at the next smaller noise level, resulting in better dependence on parameters. Thus the predictor-corrector algorithm combines the strengths of the predictor and corrector steps. For real- world data, it can be challenging to estimate TV-distance between distributions given only samples, and hence difficult to check consistency with empirical observations. However, our claim that using a corrector can improve the convergence rate of DDPM/SMLD consistent with the simulation results in Section 4.2 of [Son+20b).
4 Theoretical framework and proof sketches
The main idea of our analysis framework is to convert a 2 error guarantee to a L error guarantee by excluding bad set, formalized in the following theorem.
Theorem 4.1. Let (P) be probability space and {Fr} be filtration of the sigma field F. Suppose Xn ~ Pn- Zn ~ and Zn ~ an are F Fn-aaaated random processes taking values in Ω and Bn S are sets such that the following hold for every n E No-
1. If Zu E Bg for all 0 S k < n 1, then Zn Zn.
2. x" (7n lpn) D
3. PX,,, Bn) S 6n.
Then the following hold.
n- (y In)) I 2 k=
R-1
TV qn) s Dn +
Σ (Df + 1) k=0
(6)
For our setting, we will take the "bad sets" Bn to be the set of x where [1)) - V Inpl large, 4n to be the discretized process with estimated score, and 7. to be the discretized process with estimated score except B, where the error large. Because 7, uses an L -ccuurate score estimate, we can use existing techniques for analyzing Langevin Monte Carlo [WW19 EHZ21 Che+21 to bound x" (g.llp.)
Proof. We bound using condition and Cauchy-Schwarz:
P (Zn + Zn)
P
U k=1
[Z E Bub
<
IP
(Z E B&) = Σ Egg 1B
k=0
k==
2
1/2
Epp
Ukk
(Ep, 1 1 1/2
E 1)1/222/12
Pk
k=
k=
7

---

The second inequality then follows from the triangle inequality and Cauchy-Schwaard Schwarz:
(p Un) (p Tn) + TV( 4n.
X2 P.)) TV 4n) 9n) Dn
EDi 1
now remains to give x² convergence bounds under -ccuurce score estimate. The following theorem may be of independent interest.
Theorem 4.2 (LMC under 1 bound on gradient error), Let p Rd + R be probability density satisfying Assumption
and s R2 F. be a score estimate s with ervor bounded in L
for some E1 V 48CCs'
Vhp 8l1x0
max [Vlpp(>) s(x))1] S E1.
xER
Let N E No and 0 < h S 4392dChs and assume 1. 2 1. Let qnh denote the nth iterate of LMC with step size h score estimate Then
h x2 (40+11ylll (p)) S exp (AAcis)
x (2(nnnll) 17001? 5eîh
and
Nh
Nh
x2 ((Nn exp
x2 (gollp) + 680dL2nCLs + 20= S exp
x² (gollp) +
4Cis
4Cis
Following [Che+21], we prove this by first defining continuous-time interpolation qe of the discrete process, and then deriving a differential inequality for x² using the log- Sobolev inequality for Compared to [Che+21], incur extra error term arising from the inaccurate gradient.
This allows to sketch the proof of Theorem 2.1 a complete proof is in Section
Proof sketch of Theorem 2.7 We first define the bad set where the error in the score estimate is large,
= [[VVlp((>) s(x))) > $1}
for some E to be chosen. Then by Chebyshev's inequality, P(B) < )==²= =: 8. Let 4nh be the discretized process, but where score estimate set be equal to Inp on B; note it agrees with estimate that has L -eror E1, Theorem 4.2
quh as long as it has not hit B. Because TnA gives a bound for (T [p). Then Theorem 4.1 gives
kh 8C1s
(V 9nh)
(x + +1)1/
exp
x² (goll (p)l //////+1111 8112
k=0
k=0
The theorem then follows from choosing parameters so that x (2qrlpp) - 2x and TV (T) STV.
We remark that the main inefficiency in the proof comes from the use of Chebyshev's inequality, and I.P bound on the error for porp> will improve the bound.
Proof sketch of Theorem 2.2 Choosing the sequence 01 <... GM to be geometric with ratio
1+ Va ensures that the x diveergencc between successive distributions Poz O(1). Then, choosing 0(1)- dCLs noise levels. Chebyshev's inequality can be used to show that the min
Φ ((Cisd) ensures have warm start for the highest noise level: x2 AopmiollPP:33
This uses O (Vdlog
distribution of the final sample (m!) for Par is ((Erv /M) close to distribution that is O(M/erv)
in diverrgeee from Pos.." This gives the warm start parameter Ky (M (M/eTv)112, substituting into Theorem 2.1 then gives the required bound for e. Note that the TV errors accrued from each level add to O(Erv).

---

To analyze the predictor-based algorithms, we also first prove convergence bounds under - accurate score estimate.
Theorem 4.3 (Predictor steps under 1 bound on score estimate, DDPM). Let p Rd + be probability density satisfying Assumption and s(,,t) Rd - R² be score estimate with error bounded in L for each E [0,T]:
max VVn s(xr, ()1l 81 ZER
Consider DDPM with =
and h Cis(4+ (Recall that pkh
and quh are the k-th iterate of LMC with step size h and true/estimated score respectively.) Then
Xla0+1nllDDEEtAn S x22 (9uaelllen) (-sdis t8c)+
O (L3++10 12d))²²)
and ef < 1280's'
x² (aNullpNA) S - x2 + (Gis (e) (L2 L(d))))
Nh. rocis
Moreover, for qo = Pprice. x² (20llppo)) s ST-T/2CLsd.
We give a more precise statement in Section Note that unlike the case for LMC as in Theorem 4.2 the base density p: also evolving in time, which produces additional error terms and necessitates a more involved analysis. The additional error terms can be bounded using the Donsker-Varte Varadhan variational principle, concentration for distributions satisfying LSI, and error bounds between pt and Pe+h for small h.
Here, only state the result about DDPM, which has better bounds than SMLD (when g 1) because both the forward and backwards processes exhibit better mixing properties: the warm start improves exponentially rather than inversely with T, and the log-Sobolev constant is uniformly bounded by that of Paata rather than increasing. However, the analysis in Section C can be directly applied to SMLD and other models as well. We also note there is sense in which DDPM and SMLD are equivalent under a rescaling in time and space (see discussion Section C.2
Note that the choice of h is necessary for exponential decay of error; if h is not small enough, would get an exponential growing instead of decaying factor the one-step error (See Section C for details). Such an h may however still be suitable choice when used in conjunction with corrector step. Moreover, as E + O, with appropriate choice of T and h, 9NN and pNn can be made arbitrarily close.
Theorem 3.1 now follows from the L result (Theorem in the same way that Theorem 2.1 follows from Theorem 4.2
To prove Theorem 3.2, suffices to run the corrector steps only at the lowest noise level, that is, set Nm for 1 < m < T/h, although we note that interleaving the predictor and corrector steps does empirically help with mixing. The proof follows from using the predictor and the corrector theorems in series: first apply Theorem 3.1 with Ex = O(1) to show that the predictor results warm start Pdaa. then use Theorem 2.1 to show the corrector reduces the error the desired ETV.
5 Conclusion
We introduced general framework to analyze SDE-based sampling algorithms given -e-error score estimate, and used to obtain the first convergence bounds for several score-based generative models with polynomial complexity in all parameters. Our analysis can potentially be adapted to other SDE's and sampling algorithms beyond Langevin Monte Carlo. There is also room for im- proving analysis to better smoothing properties of the SDE's and compare different choices of the diffusion speed g.
We present several interesting further directions to explore. In addition to extending the analysis to other SGM's and comparing their theoretical performance (relative to each other as well as other approaches to generative modeling), we propose the following.

---

Analysis for multimodal distributions. Our assumption of bounded log Segoolo constant es- sentially limits the analysis distributions that are close to unimodal. However, SGM's are em- pirically successful at modeling multimodal distributions (SE19), and in fact perform better with multimodal distributions than other approaches such as GAN's. Can we analyze the convergence for simple multimodal distributions, such mixture of distributions each with bounded log-Sobolev constant? Positive results on sampling from multimodal distributions such as [GLRI8) suggest this is possible, as the sequence of noised distributions is natural for annealing and tempering methods (see [GRR88] Remark 7.2)).
Weakening conditions on the score estimate. The assumption that have a score estimate that -aceuuccuraee L2, although weaker than the usual assumptions for theoretical analysis, is fact still a strong condition in practice that seems unlikely to be satisfied (and difficult to check) when learning complex distributions such as distributions images. What would reasonable weaker still obtain reasonable samples?
condition be, and in what sense
Guarantees for learning the score function. Our analysis assumes a L eettiimttee of the score function is given, but the question remains of when can find such estimate. What natural conditions on distributions allow their score functions to be learned by neural network? Various works have considered the representability of data distributions by diffusion-like processes (TR19). but the questions of optimization and generalization appear more challenging.
Acknowledgements
We thank Andrej Risteski for helpful conversations. This work done in part while HL was visiting the Simons Institute for the Theory of Computing. The work was supported in part by National Science Foundation via awards DMS-20122 2012286 and CCF-1934964 (Duke Tripods).
10

---

References
[ACB17] Martin Arjovsky, Soumith Chintala, and Léon Bottou. "Wasserstein generative ad- versarial networks". In: International conference machine learning. PMLR. 2017,
pp. 223.223.
[And82]
Brian DO Anderson. "Reverse-timee diffusion equation models". In: Stochastic Pro- cesses and their Applications 12.3 (1982). pp. 313-326.
[BGL13]
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markov diffusion operators. Vol. 348. Springer Science & Business Media, 2013.
[BL02]
Herm Jan Brascamp and Elliott H Lieb. "On extensions of the Brunn-Minkowski and Prékopa-Leinde theorems, including inequalities for log concave functions, and with application the diffusion equation". In: Inequalities. Springer, 2002, pp. 441 1644. Adam Block, Youssef Mrouch, and Alexander Rakhlin. "Generative modeling with denoising auto-encoders and Langevin sampling". In: arXiv preprint 0rXiv:2002.00107 (2020).
[BMR20]
[CB18]
Xiang Cheng and Peter Bartlett. "Convergence of Langevin MCMC in KL- divergence". In: Algorithmic Learning Theory. PMLR. 2018, pp. 186-211. Djalil Chafai. "Entropies. convexity, and functional inequalities, On t-entropies and 4-Sobolev inequalities". In: Journal of Mathematics of Kyoto University 44.2 (2004), pp. 323-363.
[Cha04]
[Che+18]
Xiang Cheng, Niladri Chatterji, Peter L. Bartlett, and Michael Jordan. "Under- damped Langevin MCMC: A non-asymptotic analysis". In: Conference learning theory. PMLR. 2018, pp. 300-323.
[Che+21]
Sinho Chewi, Murat A Erdogdu, Mufan Bill Li, Ruoqi Shen, and Matthew Zhang. " "Analysis of Langevin Monte Carlo from Poincaré to Log-Sobolev". In: arXiv preprint arXiv:2112. 12662 (2021).
[Dal17]
Arnak S Dalalyan. "Theoretical guarantees for approximate sampling from smooth and log-concave densities". In: Journal of the Royal Statistical Society: Series B (Statistical Methodology) 79.3 (2017), pp. 651-676.
[Dat+19]
Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosinski, and Rosanne Liu. "Plug and play language models: A simple approach controlled text generation". In: arXiv preprint /9/.02/ (2019).
[De +21] Valentin De Bortoli, James Thorton,, Jeremy Heng, and Arnaud Doucet. "Diffusion Schrödinger bridge with applications to score- based generative modeling". In: Ad- vances in Neural Information Processing Systems 34 (2021).
[DK19]
Arnak S Dalalyan and Avetik Karagulyan. "User-friene friendlyy guarantees for the Langevin Monte Carlo with inaccurate gradient". In: Stochastic Processes and their Applications 129.12 (2019), pp. 2278-5314
[DM17] Alain Durmus and Eric Moulines. "Nonasymptotic convergence analysis for the un- adjusted Langevin algorithm". In: The Annals of Applied Probability 27.3 (2017), pp. 1551-1587.
[DN21]
Prafulla Dhariwal and Alexander Nichol. "Diffusion models beat gans image syn- thesis". In: Advances in Neural Information Processing Systems 34 (2021).
[DSB16] Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. "Density estimation using real nvp". In: arXiv preprint arXiv:1605 100.00800388 08803 (2016).
[DVK21]
Tim Dockhor,, Arash Vahdat, and Karsten Kreis. "Score-Based Generative Model- ing with Critieally-Damped Langevin Diffusion". In: arXiv preprint arXiv:21 (2021).
[EHZ21] Murat A. Erdogdu, Rasa Hosseinzadeh, and Matthew S. Zhang. "Convergence of Langevin Monte Carlo in Chi- Chi-Squared and Renyi Divergence". In: arXiv preprint arXiv:2007. 1612 (2021).
[GLR18] Rong Ge, Holden Lee, and Andrej Risteski. "Beyond log- conccviaaity: provable guaran- tees for sampling multi-modal distributions using simulated tempering langevin monte carlo". In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. 2018, pp. 7858-7867.
11

---

[Goo+14] 14] Ian Goodfellow, Jean Pruget-Abadic, Mehdi Mirza, Bing Xu, David Warde-Fate Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. "Generative adversarial nets". In: Advances in neural information processing systems 27 (2014).
[Gra+19] Will Grathwohl, Kuan-Chieh Wang, f6m--enrikk Jacobsen, David Duvenaud, Moham- mad Norouzi, and Kevin Swersky. "Your classifier is secretly an energy based model and you should treat it like one". In: arXiv preprint
(2019).
[Har04]
Gilles Hargé. "A convex/log-conenn
correlation inequality for Gaussian measure and an application to abstract Wiener spaces". In: Probability theory and related fields 130.3 (2004), pp. 415-440.
[HJA20]
Jonathan Ho, Ajay Jain, and Picter Abbeel. "Denoising diffusion probabilistic models". In: Advances in Neural Information Processing Systems 33 (2020), pp. 6840-6851. Bowen Jing, Gabriele Corso, Renato Berlinghieri, and Tommi Jaakkola. "Subspace Diffusion Generative Models". In: arXiv preprini arxii:2205.01-2:: (2022). Diederik P Kingma and Max Welling. "An introduction to variational autoencoders". In: arXiv preprint arXiv:/906.000 0e21999060699 (2019).
[Jin+22]
[KW19]
[Lee+21]
Holden Lee, Chirag Pabbaraju, Anish Sevekari. and Andrej Risteski. "Universal Approximation for Log-concave Distributions using Well-conditioned Normalizing Flows". In: arXiv preprint urXiv:2107.002:0 (2021).
[Men+21] Chenlin Meng, Yutong He, Yang Song, Jiaming Song, Jiajun Wu, Jun- Yan Zhu, and Stefano Ermon. "SDEdit: Guided image synthesis and editing with stochastic differen- tial equations". In: International Conference on Learning Representations. 2021.
[MMS20] Mateusz B Majka, Aleksandar Mijatović, and Lukasz Szpruch. "Nonasymptotic bounds for sampling algorithms without log-concavity". In: The Annals of Applied Probability 30.4 (2020), pp. 1534-1581.
[SE19]
Yang Song and Stefano Ermon. "Generative Modeling by Estimating Gradients of the Data Distribution". In: Proceedings of the 33rd Annual Conference on Neural Infor- mation Processing Systems. 2019.
[SE20]
Yang Song and Stefano Ermon. "Improved techniques for training score-based gener- ative models". In: arXiv preprint arXiv::006. 0901 (2020).
[Soh+15] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. "Deep unsupervised learning using nonequilibrium thermodynamics" In: International Con- ference on Machine Learning. PMLR. 2015, pp. 2256-2265.
[Son+20a]
Yang Song, Sahaj Garg, Jiaxin Shi, and Stefano Ermon. "Sliced score matching: A scalable approach to density and score estimation". In: Uncertainty in Artificial Intel- ligence. PMLR. 2020, pp. 574-584.
[Son+20bb Yang Song, Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Er- mon, and Ben Poole. "Score- -Bsse Generative Modeling through Stochastic Differen- tial Equations". In: International Conference on Learning Representations. 2020.
[Son+21a] Yang Song, Conor Durkan, lain Murray, and Stefano Ermon. "Maximum likelihood training of score-based diffusion models". In: Advances in Neural Information Pro- cessing Systems 34 (2021).
[Son+21b] Yang Song. Liyue Shen, Lei Xing. and Stefano Ermon. "Solving Inverse Prob- lems in Medical Imaging with Score-Based Generative Models". In: arXiv preprint SKKv:2111.0800. (2021).
[TR19] Belinda Tzen and Maxim Raginsky. "Theoretical guarantees for sampling and infer- ence in generative models with latent diffusions". In: Conference on Learning Theory.
PMLR. 2019, pp. 3084-3114.
[VW19] Santosh Vempala and Andre Wibisono. "Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices". In: Advances in neural information processing sys- tems 32 (2019), pp. 8094-8106.
[ZML16) Junbo Zhao, Michael Mathieu, and Yann LeCun. "Energy-based generative adversarial network". In: arXiv preprint arXiv: 1609.0309233 (2016).
12

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report enror bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (c.g., code, data, models) curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "aG-VjId8R0W", "reviewer": "Reviewer_MwKa", "summary": "This paper gives a new theoretical framework to analyze the complexity of score-based generative modeling methods, from Langevin dynamics (including Annealed Langevin dynamics, [SE19]) to forward/backward processes such as DDPM [HJA20] (including the predictor/corrector improvement suggested in [Son+20b]). The authors develop a good set/bad set approach to control the $\\chi_2$ divergence of the target distribution $p$ wrt a distribution $\\bar{q}$, which is arbitrarily close to the estimated distribution $q$ in total variation distance. Their analysis relies on assumptions commonly used in this field: L2-accuracy of $\\nabla \\ln q$ wrt $\\nabla \\ln p$, Log-Sobolev property for $p$ and smoothness properties of $\\ln p$. In contrast to previous works (especially [De+21]), the error term in their bound does not grow exponentially in time and does not suffer from the curse of dimensionality. This is the first known analysis which provides a polynomial dependence on the parameters of the problem.", "questions": "\n- I suggest the authors to move Assumptions 1 and 2 outside of Section 2 (preferably before), since they are used in Section 3 again. More precisely, I advise the authors to introduce these assumptions out of their analysis sections.\n- I suggest the authors to move Appendix E at the beginning of the supplement and to recall the definition of $\\chi_2$-divergence and total variation distance in this section.\n- The authors should recall the notations $p_t$, $q_t$ in Theorem 4.3 when stating the result.\n- In the main paper and the supplements, $\\tilde{q}$ often stands for $\\bar{q}$, which leads to some confusion.\n", "limitations": "- I think there is an error in Theorem 2.2 in the polynomial dependence of $d$; it would rather be $d^{3.25}$ than $d^{2.5}$.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- High quality paper, very well-written, the results are well presented and clear, the authors provide intuition and interpretation for their results, the theoretical framework is solid. \n- The paper is well organized and didactic: Background & related work; Analysis of Langevin Dynamics; Analysis of Forward/Backward SDE; General approach and main technical lemmas.\n- Their convergence bound is better than the bounds stated in state-of-the-art theorems, under close assumptions.\n- Their good set/bad set approach is interesting and convincing.\n\nWeaknesses: \n\n- In my opinion, there is an error in Theorem 4.1 (line 246, the last term in the inequality is the expectation wrt to $p_k$ rather than $q_k$), which leads to a suboptimal bound for TV($q_n$, $\\bar{q_n}$) in the paper. Indeed, the actual bound should be $\\sum_{k=0}^{n-1}\\delta_k$, which is better than the one derived by the authors (since $\\delta_k \\leq 1$, $\\delta_k \\leq 1+D_k$). This suboptimal bound seems to make the proof harder than it is. However, from my understanding, this suboptimal bound does not change the conclusions of the paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZSmjv3xrm-", "reviewer": "Reviewer_8Jhx", "summary": "This work provides a rigorous theoretical analysis on score-based generative modeling, giving the first polynomial convergence guarantees for multiple sampling methods. It is proved that under suitable assumptions, annealed Langevin dynamics converge better than Langevin dynamics (without the need of warm starts), and predictor-corrector converges faster than either predictor-only or corrector-only approaches. ", "questions": "As a byproduct of the proof for Theorem 2.2, authors have a way to choose $M$ and the sequence $\\sigma_1 < \\cdots < \\sigma_M$ for the convenience of theoretical derivation. I wonder whether choosing noise levels in this way has any empirical significance. Can you outperform existing noise schemes with the one used in your theoretical analysis?", "limitations": "Authors have a very comprehensive list of future research directions in conclusion, which is an implicit discussion on limitations. This is a purely theoretical work and I do not see any immediate negative societal impacts.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is an excellent work and I can see many strengths:\n\n1. Theoretical results in this work have weaker assumptions than prior arts. It does not require $L^\\infty$-accurate score function ($L^2(p)$-accurate is sufficient), and assumes no dissipativity. The rates do not have exponential dependency on dimensionality, a significant improvement over existing results.\n\n2. The score estimate has no need to be conservative. This work therefore provides a solid theoretical footing for the common trick in practical applications that employs unconstrained neural networks to directly model and estimate the score function.\n\n3. Theorem 2.1 & 2.2 provide a concrete justification on the importance of annealed Langevin dynamics in terms of avoiding warm starts. Theorem 2.2, 3.1 & 3.2 additionally shows the benefit of predictor-corrector sampling compared to using either part alone. Both are significant theoretical advancements that provide solid understanding for previous empirically driven methods in score-based generative modeling.\n\n4. Very clear writing. A comprehensive conclusion on future directions.\n\nThere are no major weaknesses. A few typos need to be corrected in the revision:\n\nline 53: duplicated \"the\"\n\nline 171: \"corrector step\" -> \"predictor step\"\n\nline 242: \"to the be\" -> \"to be the\"\n\nEquation below line 246: missing $\\sum_{k=0}^{n-1}$ after $\\leq$ on the second row.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CE-iPrJ4VaJ", "reviewer": "Reviewer_JAKh", "summary": "This work provides the first polynomial convergence guarantee for score-based geneative models. The theoreical results supports the current progress in score-based generative models that use an annealed procedure with the combination of predictor-corrector during training.", "questions": "1. Does the claim in Theorem 4.2 means the convergence rate of DDPM/SMLD can be further improved when combined with a corrector? If so, some simulation results might be helpful to verify this claim.\n\n2. Does the improvement on the convergence result only apply to TV distance? What about Wasserstein distance, etc?", "limitations": "The limitations of the assumptions made in the paper are discussed in the last section.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1. The work is the first to provide polynomial complexity in the convergence of score-based generative models to my best knowledge. Polynomial dependency on time, dimension and smoothness of the distribution is a significant improvement compared to existing works.\n\n2. The presentation of the paper is clear. The comparison w.r.t. to previous results in the introduction shows the significant improvement in the convergence rate analysis. Examples of exisiting approaches (SMLD, DDPM) also support those design choices.\n\n3. Key ideas in the proofs are introduced in section 4 without goinging into the details, which makes it easier to follow.\n\nWeaknesses: \n\n1. The relationship between the predictor-corrector method and the current training approach of score-based generative models (for example, DDPM) is not discussed in a very comprehensive way. See Questions 1.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BnVyTVLErHR", "reviewer": "Reviewer_ru9p", "summary": "Score-based generative modeling (SGM) refers to an increasingly popular class of generative models, which implicitly learn a target distribution by using diffusion processes that gradually add noise to the observed samples. An important component of such models is the score function, namely the gradient of the log probability density. This work proposes a theoretical analysis on the convergence of SGM when the score function is estimated, assuming the induced approximation error is bounded in $L^2$ (see Assumption 2.2). The authors motivate their study by pointing out that the literature on that topic exhibit convergence rates that scale exponentially in the dimension or the running time. The main contribution of this paper is then the derivation of convergence rates with polynomial complexity in the parameters of the problem, under a log-Sobolev condition on the data distribution. The contributions of this paper are theoretical results, as explained more precisely below.\n\n1) The error between the target probability density $p$ and the one returned by a SGD based on Langevin diffusion is bounded (Theorem 2.1). As discussed by the authors, the bound in Theorem 2.1 emphasizes the importance of a \"warm start\" and motivates the study of SGD with annealed Langevin dynamics (Algorithm 1). The error bound is refined for the latter approach in Theorem 2.2.\n\n2) Prior work demonstrated that running the diffusion process in reverse can help improve the empirical performance. The authors thus derive the error bound for denoising diffusion probabilistic modeling (DDPM), an existing generative model based on a reverse-time diffusion process (Theorem 3.1). They also show that using a \"predictor-corrector\" generative model, by combining DDPM steps (\"predictor\" steps) with Langevin diffusion steps (\"corrector\" steps), yield to an error bound with improved dependence on the parameters (Theorem 3.2). \n\nNote that the four main error bounds (Theorems 2.1, 2.2, 3.1, 3.2) are in TV distance and hold under specific assumptions on the target $p$ and the estimate score function $s$ (Assumptions 1 and 2): in particular, $p$ must satisfy a log-Sobolev inequality, the score function is $L$-Lipschitz, and $s$ is bounded in $L^2$. The proofs of these results are detailed in the appendix and summarized in the main document (Section 4). The authors conclude by pointing out the limitations of their analysis (Section 5).", "questions": "For now, what prevents me from giving a higher score is, as explained above, the lack of illustration on the main contributions: I encourage the authors to,\n1) If possible, relate their theoretical bounds with existing empirical observations reported in the literature,\n2) Discuss whether their proof sketches (Section 4) are original to better emphasize their contributions, \n3) Discuss if the theoretical framework can foster interesting follow-up work, given that the core assumptions seem unrealistic (according to Section 5),\n4) Clarify the impact of the main parameters on the bounds. In particular, if I am not mistaken, the rates do not seem to avoid the curse of dimensionality mentioned in the introduction: while the dependence on $d$ is not exponential in the derived bounds, one can still observe that $d$ highly impacts the speed and quality of the results (for example, see the accuracy $\\varepsilon$ in all Theorems, or the length of the sequence $M$ in Theorem 2.2).\n\nMinor comments:\n\nTypos: l.42 \"an denoising\", l.242: \"the be\"\n\nl.118: the definition of $W_t$ is missing\n\nl.146-150: I am confused about the interpretations: without warm start, $K_{\\chi}^2$ can be arbitrarily large, therefore $\\varepsilon$ is small; then, why is the error on $s$ not guaranteed to be small on average (l.147-148)? \n\nl.235: $\\mathcal{F}_n$ should be defined\n\nl.246: The sum over $k$ seems to be missing in the derivations, when upper-bounding $\\sum_{k=0}^{n-1} E_{q_k} 1_{B_k}$\n\nl.265: Please give more explanations on why $(1+\\chi^2(\\bar{q}_{kh} || p))^{1/2}$ can be bounded that way. Theorem 4.2 is used but it seems like some factors are missing.", "limitations": "The limitations of this work are clearly addressed in Section 5. The potential negative societal impact of the contributions is not discussed.\n", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Score-based generative models have attracted significant interest in the machine learning community over the past few years, but some successful approaches have been proposed very recently and lack theoretical guarantees. Deriving the convergence rate and bounding the error made by these models according to the parameters of the problem is important, since it helps identify the setups for which such algorithms will perform well or fail in practice. In that sense, the problem addressed by this paper is highly relevant for NeurIPS. \n\nI found the paper very well written and easy to follow: the motivations are clear, prior work is adequately discussed, and the authors put some effort in explaining their main theorems and their proofs from a high level perspective. In light of the discussions and interpretations provided throughout the paper, the contributions of this work seem sound to me; but due to a lack of time and expertise on SGD, I was unable to thoroughly check the proofs in the appendix. \n\nIn my opinion, this work would significantly benefit from more illustration on the derived rates: I am not familiar with related work and after reading this paper, it is still unclear to me how original the proof techniques are and whether they are consistent with empirical analysis in previous work. I also listed some questions in the next section of my review. Besides, this paper does not contain any experiments, although this could have been useful to illustrate and confirm the theoretical contributions. \n\nOn a related note, the authors discuss the limitations of their work in their conclusion, which I appreciated – that being said, it highlights that the assumptions of the theorems do not reflect well what happens in practice, so there is still an important gap between this study and the practice. Specifically, the central assumptions seem too restrictive: bounding the accuracy of the estimated score function in $L^2$ is described as \"a strong condition in practice that seems unlikely to be satisfied (and difficult to check) when learning complex distributions\" (l.326-328) and it is unclear \"when we can find such an estimate\" (l.330); the log-Sobolev condition on the target $p$ implies that $p$ is unimodal, which strongly limits the scope of the theoretical analysis. Hence, I am wondering to what extent the proposed framework is realistic and useful.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8zesNnfghr", "reviewer": "Reviewer_VLZN", "summary": "In this paper, the authors study the convergence of score-based generative models (SGMs) (also called denoising diffusion models) w.r.t. the total variation distance and under the assumption that a logarithmic Sobolev inequality holds for the distribution. They also assume that the score network is close to the true score w.r.t. the $L_2$ distance and not the $L_\\infty$ distance contrary to previous works. They provide quantitative convergence for the annealed algorithm first introduced in [1] and the time-reverse algorithms considered in [2], including the predictor-corrector scheme. The paper is concluded by a short presentation of the theoretical framework including an explanation of the translations of $L_2$ errors to $L_\\infty$ errors. The analysis in the case of the $L_\\infty$ error follows the lines of [3].\n\n* [1] -- Song and Ermon (2019) -- Generative modeling by estimating gradients of the data distribution \n* [2] -- Song et al. (2021) -- Score-based generative modeling through stochastic differential equations \n* [3] -- Chewi et al. (2021) -- Analysis of Langevin Monte Carlo from Poincare to Log-Sobolev", "questions": "In this section, I wrap up my main comments and questions for the authors:\n\n* What is $C_T$ in Theorem 2.1 ? It is a bit hard to know.\n\n* In Theorem 2.2, is the sequence of $(\\sigma_i)_{i=1}^M$ explicit? It seems so and in fact it seems to be geometric but it would be interesting to specify it in the discussion following Theorem 2.2\n\n* In (2) the backward Brownian motion is never introduced. I would have preferred if the authors had sticked with the backward formulation given a positive time element, i.e.\n$d x_{T-t} = -f(x_{T-t}, T-t) + g^2(T-t) \\nabla \\log p_{T-t}(x_{T-t}) + g(T-t) d w_t$, which is also closer to the form that is actually used in the proof.\n\n* It is a bit underwhelming that the authors do not study the influence of $g$ in this paper. The choice of the schedule does matter in practice and is an important topic of investigation in the community.\n\n* There is an error in Theorem 4.1. Indeed after line 246, the equality $\\sum_{k=0}^{n-1} \\mathbb{P}(X_k \\in B_k) = \\sum_{k=0}^{n-1} \\mathbb{E}_{q_k} \\mathbb{1}_k$ is false. In fact, we have $\\sum_{k=0}^{n-1} \\mathbb{P}(X_k \\in B_k) = \\sum_{k=0}^{n-1} \\mathbb{E}_{p_k} \\mathbb{1}_k$. This simplifies the result since we get that $\\mathrm{TV}(q_n, \\bar{q}_n) \\leq \\sum_{k=0}^{n-1} \\delta_k$ and $\\mathrm{TV}(p_n, q_n) \\leq D_n + \\sum+{k=0}^{n-1} \\delta_k$.\n\n* Related to the comment on the mixture of Gaussians : in [1] it is shown that if two distributions $p_0$ and $p_1$ have finite $\\chi_2$ divergence and satisfy logarithmic-Sobolev inequalities then their mixture also satisfies a logarithmic Sobolev inequality. Hence, I think that the authors could mitigate their caveat here.\n\n* There are a few typos in the appendix. For example, line 718 $f(x,t) ==$ should be $f(x,t) =$ and below line 706, $p$ should be $p_t$.\n\n* I really enjoyed reading the proof of Theorem C.1. The proof can be decomposed as follows: first the author derive a differential inequality on $\\chi^2(p_t|q_t)$. To do so the authors use an extension of the computations of [2] to the non-homogeneous setting. Then, they control the errors arising from this decomposition. In particular, they need to control errors involving $\\phi_t = (q_t / p_t) / \\mathbb{E}_{p_t}[\\phi_t^2]$ (Section C.4). This is done with the Donsker-Varadhan variational theorem. A perturbation error needs to be controlled in Section C.5. The differential inequality then gives rise to a $L_\\infty$ control which when combined with the results allowing to go from the $L_2$ error to the $L_\\infty$ error concludes the proof. I would have appreciated such a discussion in Section C.1 to give an overview of the rest of the proof.\n\n* The results of Section C.4 heavily rely on the Donsker-Varadhan variational principle. To my knowledge this principle only applies to bounded function (this comes from the dual representation of the Kullback-Leibler divergence). I'm assuming that the result can be extended to any function but could the authors provide a reference for this result?\n\n[1] Schlichting (2019) -- Poincaré and log–Sobolev inequalities for mixtures\n[2] Chewi et al. (2021) -- Analysis of Langevin Monte Carlo from Poincare to Log-Sobolev\n", "limitations": "The authors discuss the limitations of their work in the conclusion.\nThey are aware of the limitations of their framework regarding the use of the logarithmic Sobolev inequality.\nI would have appreciated a deeper discussion on the assumption that $\\nabla \\log p_t$ needs to be Lipschitz.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS:\n\n* The paper is very well-written with clear exposition. The study is also well motivated. Diffusion models are an attractive research area with a lot of empirical results but very few theoretical ones.\n* The results cover diffusion models with Brownian motion forward (SMLD) or Ornstein-Ulhenbeck forward (DDPM). They also cover the case of predictor-corrector schemes.\n* The approach to prove the convergence of diffusion models is new and likely to be fruitful in the future.\n\nWEAKNESSES:\n\n* Some of the assumptions are too strong. For example proving that a given density satisfies a logarithmic-Sobolev inequality is not trivial, except in easy setting such as strongly convex potentials. For example, to the best of my knowledge, it is not clear that a dissipativity condition suffices to prove some logarithmic Sobolev inequality. The closest condition I could find is the work of [1] which proves that under some dissipativity condition which might depend on the local behavior of the density a logarithmic Sobolev condition is satisfied. Is there a realistic setting in which the density satisfies a logarthmic Sobolev inequality.\n* There is one strong assumption throughout this paper, which is that $\\nabla \\log p_t$ is Lipschitz with a uniform constant $L$. While it seems intuitive that $\\log p_t$ should be Lipschitz, proving it seems quite hard.\n\n[1] Cattiaux et al. (2007) -- Lyapunov conditions for logarithmic Sobolev and Super Poincaré inequality", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept