Towards Non-Asymptotic Convergence for Diffusion-Based Generative Models
Authors: Gen Li
Yuting Wei
Yuxin Chen
Yuejie Chi
Venue: ICLR 2024 poster (2024)
Keywords: diffusion models
score-based generative modeling
non-asymptotic theory
reverse SDE
probability flow ODE
denoising diffusion probabilistic model
Primary area: learning theory

Abstract: Diffusion models, which convert noise into new data instances by learning to reverse a Markov diffusion process, have become a cornerstone in contemporary generative modeling. While their practical power has now been widely recognized, the theoretical underpinnings remain far from mature.  In this work, we develop a suite of non-asymptotic theory towards understanding the data generation process of diffusion models in discrete time, assuming access to $\ell_2$-accurate estimates of the (Stein) score functions. For a popular deterministic sampler (based on the probability flow ODE), we establish a convergence rate proportional to $1/T$ (with $T$ the total number of steps), improving upon past results; for another mainstream stochastic sampler (i.e., a type of the denoising diffusion probabilistic model), we derive a convergence rate proportional to $1/\sqrt{T}$, matching the state-of-the-art theory. Imposing only minimal assumptions on the target data distribution (e.g., no smoothness assumption is imposed), our results characterize how $\ell_2$ score estimation errors affect the quality of the data generation process.  In contrast to prior works, our theory is developed based on an elementary yet versatile non-asymptotic approach without resorting to toolboxes for SDEs and ODEs.

Published as a conference paper at ICLR 2024
TOWARDS NON-ASYMPTOTIC CONVERGENCE FOR DIFFUSION-BASER GENERATIVE MODELS
Gen Li'
Yuting Wei
Yuxin Chen
Yuejie Chi
ABSTRACT
Diffusion models, which convert noise into new data instances by learning to re- verse a Markov diffusion process, have become cornerstone in contemporary generative modeling. While their practical power has now been widely recog- nized, the theoretical underpinnings remain far from mature. In this work, we de- velop a suite non-asymptotic theory towards understanding the data generation process of diffusion models in discrete time, assuming access to æ--accurate esti- mates of the (Stein) score functions. For a popular deterministic sampler (based the probability flow ODE), establish convergence rate proportional 1/T (with T the total number of steps), improving upon past results; for another mainstream stochastic sampler (i.e., type of the denoising diffusion probabilistic model), derive convergence rate proportional to 1/VT, matching the state- of-the-art theory. Imposing only minimal assumptions on the target data distribu- tion (e.g., no smoothness assumption imposed), our results characterize how l score estimation eπrоrs affect the quality of the data generation process. In con- trast to prior works, our theory is developed based on elementary yet versatile aonptsymio approach without resorting to toolboxes for SDEs and ODEs.
INTRODUCTION
Diffusion models have emerged as a cornerstone in contemporary generative modeling, a task that learns to generate new data instances (e.g., images, text, audio) that look similar in distribution to the training data (Ho et al. [2020] (Sohi-Dickstein et al.) [2055] Soog & Ermon
2019 Dhariwal & Nichol 2021 Jolicoeur-Martiness et al. [021] Chen et al. 2022 Kong et al. 2
Austin et al.
2021). Originally proposed by (Sohl-Dickstein et al. (2015) and later popularized by [Song & Ermon
(2019) Ho et al. (220)), the mainstream diffusion generative models - e.g., denoising diffusion probabilistic models (DDPMs) (Ho et al.] 2020) and denoising diffusion implicit models (DDIMs) (ong et al., 2020a) - have underpinned major successes in content generators like DALL
iRamesh et al.] 2022). Stable Diffusion (Rombach al., 2022) and Imagen (Saharia et al. 2022
claiming state-of-the-ar performance in the now broad field of generative artificial intelligence (AI).
See Yang al. 2022); Croitoru al. (2023) for overviews of recent development.
In nutshell, a diffusion generative model is based upon two stochastic processes in Rd:
1) a forward process
Xo X, -
XT
that starts from sample drawn from the target data distribution (e.g., of natural images) and gradually diffuses it into noise-like distribution (e.g., standard Gaussians);
2) reverse process
YT - Yr- Yo
(2)
Department of Statisties, The Chinese University of Hong Kong, Hong Kong.
1 Department Statisties Data Science, Wharton School, University Pennsylvania, Philadelphia, 19104, USA.
Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA 19104, USA.
$ Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA 15213,
USA.

---

Published as a conference paper at ICLR 2024
that starts from pure noise (e.g., standard Gaussians) and successively converts it into new samples sharing similar distributions as the target data distribution.
Transforming data into noise in the forward process is straightforward, often hand-crafted by in- creasingly injecting more noise into the data at hand. What is challenging is the construction of the reverse process: how to generate the desired information out of pure noise? To do so, a diffusion
model learns to build a reverse process (2) that imitates the dynamics of the forward process (1) in time-reverse fashion; more precisely, the design goal is to ascertain distributional proximity
Ye X1, t=
(3)
through proper learning based on how the training data propagate in the forward process. Encour- agingly, there often exist feasible strategies to achieve this goal as long as faithful estimates about the (Stein) score functions the gradients of the log marginal density of the forward process are available, an intriguing fact that can be illuminated by the existence and construction of reverse- time stochastic differential equations (SDEs) (Anderson, 1982 Haussmann & Pardoux 1986) (see Section 2.2 for more precise discussions). Viewed in this light, a diverse array of diffusion models are frequently referred to as score-based generative modeling (SGM). The popularity of SGM was initially motivated by, and has since further inspired, numerous recent studies on the problem of learning score functions, a subroutine that also goes by the name of score matching (e.g.. Hyvärimen (200 ):07): Vincent (2011); Song al. (020b)); Kochler al. (202)). )
Nonetheless, despite the mind--lowing empirical advances, a mathematical theory for diffusion gen- erative models is still in its infancy. Given the complexity of developing full-fledged end-to-end theory, a sride-andd-conuee approach has been advertised, decoupling the score learning phase (i.e., how to estimate score functions from training data) and the generative sampling phase (i.e., how to generate new data given the score estimates). In particular, the past two years have witnessed growing interest and remarkable progress from the theoretical community towards understanding
the sampling phase (Block et al. [220 De Bortoli et al., 2021 Liu et al. 2022; De Bortoli 2022
Lee et al.) 2023] Pidstrigach 2022, Chen al.] 2022b Tang 2023 Chen al.) 2023c] Tang &
Zhao, 2024] Li et al. 2024a). For instance, polynomia time convergence guarantees have been established for stochastic samplers (e.g. Chen et al. (2022h a): [Betton al. (2023a)) and deter-
ministic samplers (e.g.. [Chnn et al. (2020)); Benton et al. (2023b)), both of which accommodated a fairly general family of data distributions.
(e.g..(Chen
This paper. The present paper contributes to this growing list of theoretical endeavors by devel- oping a new suite of non-asymptotic theory for several score-based generative modeling algorithms. We concentrate on two types of samplers (Song al., 2021bb in discrete time: (i) a deterministic sampler based on sort of ordinary differential equations (ODEs) called probability flow ODEs (which is closely related the DDIM); and (ii) a DDPM-type stochastic sampler motivated by reverse-time time SDEs. We impose only minimal assumptions on the target data distribution (e.g., no smoothness condition is needed), and would like to quantify the impact of &g score estimation errors. In comparisons to past works, our main contributions are three-fold.
Non-asymptotic convergence guarantees. For a popular deterministic sampler, we demonstrate that the number of steps needed to yield e-accuracy between the distribution of X, and that of Y, is no larger than e - proportional to 1/E (in addi- tion to other polynomial dimension dependency). This improves upon prior convergence guarantees (Chen et al. (023c) and does not exhibit exponential dependency on the smoothness assumption as in Chen et al. (2023c); [Benton al. (2023b). For another DDPM-type stochastic sampler, tablish an iteration complexity proportional to 1/E?, matching existing theory Chen et al. 2022b a); Benton et al. (023a) in terms of the e-dependency.
meaning that the total variation (TV) distance
Score estimation errors for the determinstic sampler. In our convergence guarantees for the deter- ministic sampler, the TV distance between X; and Y1 are shown to be proportional to the lg score estimation error as well as the associated Jacobian errors. As far as we know, this is the first result for this deterministic sampler that accounts for score estimation errors in discrete time. In compari- son, other theoretical results that accommodate score errors for the probability flow ODE approach
'Two random vectors X and Y are said to obey X Y (resp. X R3 Y) if they are equivalent (resp. close) in distribution.
2

---

Published as a conference paper at ICLR 2024
either study certain stochastic variations of this deterministic sampler (Chen et al. 2023b fall short of accommodating discretization errors (Benton et al. 2023b).
An elementary non-asymptotic analysis framework. From the technical viewpoint, the analysis framework laid out in this paper is fully non-asymptotic in nature. In contrast to prior analyses that take detour study the continuum limits and then control the discretization error, approach tackles the discrete-time processes directly using elementary analysis strategies. No knowledge of SDEs or ODEs is required for establishing our theory, thereby resulting in more versatile frame- work and sometimes lowering the technical barrier towards understanding diffusion models.
Notation. For any two functions f(d,T) and g(d, T), we adopt the notation f(d, T) & g(d, or f(d,T)= = (g, T)) (resp. f(d, T") Z g(d, T)) to mean that there exists some universal constant G such that f(d, T) Cig(d, (resp. f(d, T) 2 Cig(d, for all and T; moreover, the notation f(d, T) x I(d indicates that f(d, T) I g(d,T) and f(d, 2 g(d, hold at once. The notation O(-) is defined similar O(-) except that it hides the logarithmic dependency. Additionally, the notation f(d
(() means that f(d,T)/ g(d T) + 0 d, T tend to infinity. For any two probability measures P and Q, the total variation (TV) distance between them is defined to be TV(P, Q) := 2 |dP - dQ). Throughout the paper, px(-) (resp. px v(-1-) denotes the probability density function of X (resp. X given Y). For any matrix A, we denote by || (resp. [[)[[p) the spectral norm (resp. Frobenius norm) of A. Also, for any vector-valued represent the Jacobian matrix of f.
function f. let J or aee
of
PRELIMINARIES
In this section, we introduce the basics of diffusion generative models. The ultimate goal of generative model can be concisely stated: given data samples drawn from an unknown distribution of interest Pdata in Rd, we wish to generate new samples whose distributions closely resemble Pdata-
2.1 DIFFUSION GENERATIVE MODELS
Towards achieving the above goal, a diffusion generative model typically encompasses two Markov processes: forward process and reverse process, described below.
The forward process. In the forward chain, one progressively injects noise into the data samples to diffuse and obscure the data. The distributions of the injected noise often hand-picked with the standard Gaussian distribution receiving widespread adoption. Specifically, the forward Markov
process produces sequence of d-dimensional random vectors X1 X2
XT follows:
Xo Pdata
(4a)
X, VI - B V B, W
1 1stsT,
(4b)
where (WissisT indicates sequence of independent noise vectors drawn from W, iid. [00 La). The syper-parameter {3r- E (0, 1)} represent prescribed learning rate schedules that control the variance of the noise injected in each step. If we define
04 Be,
02
II Okk
SStsT,
(5)
then it can be straightforwardly verified that for every 1 SIST.
X; = =V + VI- a, W. for some W, (0)
(6)
Clearly, if the covariance of X, is also equal to Ia, then the covariance of X; is preserved throughout the forward process; for this reason, this forward process ( is sometimes referred to as variance- preserving (Song al. 2021b). Throughout this paper, we employ the notation
l = law (X.)
to denote the distribution of X₁. As long as बा is vanishingly small, one has the following property for general family of data distributions:
GT N' Ta).
(8)
3

---

Published as a conference paper at ICLR 2024
The reverse process. The reverse chain Yr Yr-1 7 -...- is designed (approximately) revert the forward process, allowing one to transform pure noise into new samples with matching distributions the original data. To be more precise, by initializing it
YT ~ (O, Ia).
(9a)
we seek to design a reverse-time Markov process with nearly identical marginals as the forward process, namely,
(goal) V, ~ X
1= T
(9b)
Throughout the paper, we often employ the following notation to indicate the distribution of Y;:
Ps == law(Y))
(10)
2.2 DETERMINISTIC VS. STOCHASTIC SAMPLERS: A CONTINUOUS TIME INTERPRETATION
Evidently, the most crucial step of the diffusion model lies in effective design of the reverse process. Two mainstream approaches stand out:
Deterministic samplers. Starting from YT (O, this approach selects a set of func- tions (#(()))ssTT and computes:
Yı-1 = tb (Y:).
t= T, 1.
(11)
Clearly, the sampling process is fully deterministic except for the initialization Yr.
Stochastic samplers. Initialized again at YT (O, Ia), this approach computes another collection of functions (Vx(;; sigt and performs the updates:
Y V (Y,, (Y. Z,),
t= T, 1,
(12)
where the Z 's are independent noise vectors obeying Ze i.d. (O Ta)-
In order elucidate the feasibility of the above two approaches, find it helpful to look at the continuum limit through the lens of SDEs and ODEs. It is worth emphasizing. however, that the development of main theory does rely any knowledge of SDEs and ODEs.
The forward process. continuous- time analog of the forward process can be modeled as dX, = f(x,, l)dl g())WW, (0 (T)L
Xo ~ Pdata
(13)
for some functions f(-,-) and g(-) (denoting respectively the drift and diffusion coefficient), where W, denotes d- d-dimensional standard Brownian motion. As special example, the continuum limit of (4) takes the following form") Song et al. 2021b)
dX, = X() + VB())dW (0SIST).
Xo Pdata
(14)
for some function B(1). As before, denote by ge the distribution of X, 13
The reverse process. As it turns out, the following two reverse processes are both capable
reconstructing the distribution of the forward process, motivating the design of two dis- tinctive samplers. Here and throughout, we use V log (X) to abbreviate V x log (X) for notational simplicity.
One feasible approach is to the so-called probability flow ODE (Song et al. 2021b)
T- dyoode (- (Yydee - t) + g0(T - +)² log lo ( dt (0 T)
(15)
with Yode Qr, which exhibits matching distributions follows:
Y X., 0 OSt5T.
The deterministic nature of this approach often enables faster sampling. It has been shown that this family deterministic samplers is closely related to the DDIM sam- pler (Karras et al. 2022 Song al. 2021b).
To see its connection with 44) suffices to derive from VDW. f X + V.W.W
4 that X, Xe-de vT B,N,-- X
4

---

Published as a conference paper at ICLR 2024
In view of the classical results Anderson (1822): Haussmann & Pardoux (986). one can also construct a "reverse-ting SDE
dY ( f(x T t) + g( - 2)² log qr ) + g(T t)dZa
(16)
for 0 t S T, with Yo qr and Zzde being standard Brownian motion. Strik- ingly, this process also satisfies
T-1 d X,,
OSIST.
The popular DDPM sampler (Ho et al. (2020) falls under this category.
Interestingly, addition to the functions f and that define the forward process, construction of both (T5) and (16) relies only upon the knowledge of the gradient of the log density V log g:(-) of the intermediate steps of the forward diffusion process - often referred to as the (Stein) score function. Consequently, key enabler of the above paradigms lies in reliable learning of the score function, and hence the name score-based generative modeling.
ALGORITHMS AND MAIN RESULTS
In this section, we analyze couple of diffusion generative models, including both deterministic and stochastic samplers. While the proofs for our main theory are all postponed to the appendix, it is worth emphasizing upfront that our analysis framework directly tackles the discrete-time processes without resorting to any toolbox of SDEs and ODEs tailored to the continuous- clementary approach might potentially be versatile for analyzing a broad class of variations of these samplers. For instance, prior ODE-based theory (c.g., Chen et al. (2023b/c) encountered certain technical challenges when analyzing the deterministic sampler directly, and our elementary approach able to shed new light on the convergence of this important sampler.
limits. This
3.1 ASSUMPTIONS AND LEARNING RATES
Before proceeding, we impose some assumptions on the score estimates and the target data distri- butions, and specify the hypter-parameters {a,), which shall be adopted throughout all cases.
Score estimates. Given that the score functions are an essential component in score-based gen- erative modeling, we assume access to faithful estimates the score functions V log ge(+) across all intermediate steps I, thus disentangling the score learning phase and the data generation phase. Towards this end, let us first formally introduce the true score function as follows.
Definition (Score function). The score function, denoted by s Rd - Rd, is defined
(X) == log qr (X),
1 1
(17)
As has been pointed out by previous works concerning score matching (e.g., Hyvärinen (005) Vinceet (201T); Chen et al.) (2022b)), the score function st admits an alternative form as follows (owing properties of Gaussian distributions):
[(Vaioo 1laawW) + VI az
1
8 = arg min 1n o W (1 Xoo
W
(18)
which takes the form of the minimum mean square error estimator for VT-or
W given Va,Yo
+
-I-aa V and is often more amenable to training.
With Definition I in place, we can readily introduce the following assumptions that capture the quality of the score estimate {st higgr have available.
Assumption 1. Suppose that the score function estimate {sthi obeys
T
E
[|s((X)
(x)) < 2 2
(19)
T
Xouga
5

---

Published as a conference paper at ICLR 2024
Assumption 2. For each 1 T, assume that sc(.) is continuously differentiable, and denote Usi by Jæ; az and Js, = 0s. the Jacobian matrices of st and st(.), respectively, Assume that the Be score function estimate {st, [Sth)e ISST obeys
E T X~uqe
< Jacobi-
(20)
In a nutshell, Assumption rrffects the lg score estimation error, whereas Assumption 2 concerns the estimation error in terms of the corresponding Jacobian matrix. Both assumptions consider the average estimation errors over all steps. Our theory for the deterministic sampler relies on both Assumptions and 2 while the theory for the stochastic sampler requires only Assumption [ We shall discuss in Section 3.2 the insufficiency Assumption I alone for the deterministic sampler.
Target data distributions. Our goal is to uncover the effectiveness of difffusinn models in gener- ating a broad family of data distributions. Throughout this paper, the only assumptions we need to impose the target data distribution Pdata are the following:
Xo is an absolutely continuous random vector, and
PIIlXoll2 S 7 Xo ~ Pdata) = -1
(21)
for some arbitrarily large constant CR 0.
This assumption allows the radius of the support of Pdata to exceedingly large (given that the exponent eR can be arbitrarily large).
Learning rate schedule. Let us also take a moment to specify the learning rates to be used for theory and analyses. For some large enough numerical constants co, G1 0, we
1
81
01
(22a)
To00
log T
C1 log T ) 1]. B1 (1+
8:
04
min
(22b)
T
T
Remark 1. As we shall see our analysis, the discretization ervor depends crucially upon the 1-0s, whereas the initialization error relies heavily upon Œ and Øe. Based on these quantity I-8e'
observations, our learning rate schedule (22) is designed make 1-ai as small as possible, while I-3e.
making sure ã1 (resp. orr) close to 1 (resp. 0). These properties will be shown in (43). Moreover, it is worth noting that our analysis can be easily extended to accommodate much broader class of learning rates, although the resulting convergence rates might vary.
3.2 AN ODE-BASED DETERMINISTIC SAMPLER
We begin by analyzing a deterministic sampler: snscrete-time version of the probability flow ODE.
Armed with the score estimates ISIST, a discrete-time version of the probability flow ODE approach (cf. (15) adopts the following update rule:
Yr NN(O,
Y ==1=((())) (Yi) for T,....
(23a)
where (-() is taken to be
1 -
(x
8t (x)
(23b)
Vat
This approach, based on the probability flow ODE 15 often achieves faster sampling compared to the stochastic counterpart (Song et al. 2021b). Despite the empirical advances, however, the theoretical understanding of this type deterministic samplers remained far from mature.
We first derive non-asymptotic convergence guarantees measured by the total variation distance between the forward and the reverse processes for the above deterministic sampler (23). The proof of this result can be found in Li al. 2023 Section 5.2).

---

Published as a conference paper at ICLR 2024
Theorem 1. Suppose that (1) holds true. Assume that the score estimates sc(-) < satisfy
Assumptions 7 and Then the sampling process
(23) with the learning rate schedule (22) satisfies
logo' "
d log" T C1 d Tescoe + C1d(log T)
(V C
+
Jacobi
(24)
T
T
for some universal constants C₁ > 0, where (resp. q1) represents the distribution of (resp. X1).
Implications. Let us highlight the main implications of Theorem I Before proceeding, note that theory is concerned with convergence q1- Given that X1 qi and X, do very close due to the choice of (1, focusing on the convergence w.r.t. qi instead of go remains practically relevant.
(a) Iteration complexity: Consider first the scenario that has access to perfect score estimates (i.e., Escore = 0). In order to achieve e-aceuracy (in the sense that TV(q), Pi) S E), the number of steps T only needs exceed
(25)
(b) Stability. Turning to the general case with imperfect score estimates (i.e., Escore 0), the deterministic sampler (23) yields a distribution whose distance to the target distribution (measured again by the TV distance) scales proportionally with Eccore and Jacobi. addition to the score estimation errors, we are in need of an assumption on the stability of the associated Jacobian matrices, which plays a pivotal in ensuring that the reverse-time deterministic process does not deviate considerably from the desired process.
is noteworthy that in
(c) Insufficiency of the score estimation error assumption alone. The careful reader might wonder why we are in need of additional assumptions beyond the &g score error stated in Assumption To answer this question, we find helpful look at a simple example below.
Example. Consider the case where Xo (O, 1), and hence X1 NOO. 1). Suppose that the reverse process for time t = can lead to the desired distribution if exact score function employed, namely,
Y2
sa(Y2)
Vag
2
Now, suppose that the score estimate s2(-) we have available obeys
02
yr
1
02
2y (322
02
vi
L
with yi
a22
1/2
s
(122)
for L > 0, where [&]] is the greatest integer not exceeding 2. follows that
02
Yi L
Y1 ===Y-
82 s2(22) = L
2/22
Clearly, the score error Ex,~N(0.1) (X2) taking I. + 0. However, the discrete nature of Y1 forces TV(Y, X1) = 1.
s (3 can be made arbitrarily small by
This example demonstrates that, for the deterministic sampler, the TV distance between Y1 and X, might not improve as the score error decreases. If wish to relax Assumption 2 one potential way is to resort to other metrics (e.g., Wasserstein distance) instead of TV distance between Yi and Xi.
(d) Relaxing the boundedness assumption on Xp. As it turns out, the assumption 21 can also be relaxed. Supposing that P(| Xol/2 < B Xo ~ Pdata) = for some quantity B > (which is allowed grow faster than a polynomial in T),, we can readily extend our analysis to obtain
TV(1)PI)) s Ci d² log T Toog" B Ci d log" T log B Ciy d dlog T log Bs + Cid(log Elccoob
T
T
Importantly, the convergence rate depends only logarithmically B.
Comparisons with past works. To the best of our knowledge, the only non-asymptotic analysis for the discretized probability flow ODE approach in prior literature was derived by a very recent work Chen et al. (002c)), which established the first non-asymptotic convergence guarantees that exhibit

---

Published as a conference paper at ICLR 2024
polynomial dependency in both d and 1/E (see, e.g., Chen al. 2023c Theorem 4.1)). However, it fell short of providing concrete polynomial dependency in d and 1/E, suffered from exponential dependency in the Lipschitz constant of the score function, and relied exact score estimates. In contrast, our result in Theorem uncovers a concrete d' / scaling (ignoring lower-order and log- arithmic terms) without imposing any smoothness assumption makes explicit the effect of score estimation errors, both which were previously unavailable for such discrete-time deterministic samplers. Another recent work Benton al. (2023b) studied the conver- gence of the probability flow ODE approach without accounting for the discretization error; the re- sult therein also exhibited exponential dependency on the Lipschitz constant. Finally, while we were wrapping up the current paper, we became aware of the independent work (Cen et al. (2023b) estab- lishing improved polynomial dependency for two variants the probability flow ODE. By inserting an additional stochastic corrector step based on overdamped (resp. underdamped) Langevin dif- fusion - in each iteration of the probability flow ODE (so strictly speaking, these variations are no longer deterministic samplers), Chen et al. (023b) showed that d(Ldd/²²) (resp. O(Livd/s)) steps are sufficient, where L denotes the Lipschitz constant of the score function. In comparison, our result demonstrates for the first time that the plain probability flow ODE already achieves the I/s scaling without requiring either corrector step; one limitation of our result, however, is the sub-optimal d-dependency compared to the variants studied in Chen et al. (2023b).
the target data distribution, and
3.3 A DDPM-TYPE STOCHASTIC SAMPLER
Armed with the score estimates { J. we can readily introduce the following stochastic sampler that operates in discrete time, motivated by the reverse-time SDE (16):
YT NOO,, Ta).
Yz-1 VY,, Zz)
for 1 T :.
(26a)
where Ze L.d. N(0 Ia). and
(1( var (1+
(1+ ( 022
with of
Ox -1.
(26b)
The key difference between this sampler and the deterministic sampler (3 is that: (i) there exists an additional pre-factor of 1/2 injects additional noise Z₂ in each step.
in the deterministic sampler; and (ii) the stochastic sampler
In contrast deterministic samplers, the stochastic samplers have received more theoretical atten- tion, with the state-of-the-ar results established by Chen et al.] (2022b as well as a very recent paper (enton et al. (2023a). The elementary approach developed in the current paper is also appli- cable towards understanding this type of samplers, leading to the following non-asymptotic theory.
Theorem 2. Suppose (2T) holds true. Equipped with the estimates Assumption and the learning rate schedule (22), the stochastic sampler (26) achieves, for some universal constants C1 > 0,
(V(a)))) s V KL (P))
& log VT
+ C1 CiVVdcycore T.
(27)
Theorem establishes non-asympiotic convergence guarantees for the stochastic sampler (26) As asserted by the theorem. we have access to perfect score estimates, then the number of steps needed to attain E-accuracy (measured by the TV distance between 21 and q1) is proportional to 1 1/e", matching the state-of-the-an e-dependency derived in Chen et al. (2022a). albeit exhibiting worse dimensional dependency. In addition, in the presence of score estimation error, the sam- pler achieves a TV distance proportional to Escore again consistent with prior results. Our analysis follows completely different path compared with the SDE-based approach in Chen al. 2022a). thus offering complementary interpretations for this important sampler.
4 OTHER RELATED WORKS
Theory for SGMs. Early theoretical efforts in understanding the convergence score-based stochastic samplers suffered from being either not quantitative (De Bortoli et al.] 2021 Liu et al.) 2022 [Pidstriaach] 2022). or the curse of dimensionality (c.g.. exponential dependencies in the con-
vergence guarantees) (Block et al. 2020 De Bortoli 2022 Lee al. (2022) provided the first
8

---

Published as a conference paper at ICLR 2024
polynomial convergence guarantees with Lu-accurate score estimates, for any smooth distribution satisfying the log- Sobeleev inequality. [Chen et al. (2022b); Lee et al. (023))(Chen et al. (2022a) sub- sequently lifted such stringent data distribution assumption. More concretely, [Chen et al. (2022b) accommodated a broad family of data distributions under the premise that the score functions over the entire trajectory of the forward process are Lipschitz; [Le et al. (2023) only required certain smoothness assumptions but came with worse dependence on the problem parameters; and more recent results in Chen et al. (2022a) applied literally any data distribution with bounded second- order moment. In addition, Wibisono & Yang (022) also established a convergence theory for score-based generative models, assuming that the error of the score estimator has a bounded mo- ment generating function and that the data distribution satisfies the log-Sobelev inequality, Turning attention to samplers based on the probability flow ODE, Chen et al. (2023c) derived the first non- asymptotic bounds for this type of samplers. Improved convergence guarantees have recently been provided by a concurrent work Chen et al. (2023b), with the assistance of additional corrector steps inerspersed in each iteration of the probability flow ODE. It is worth noting that the corrector steps proposed therein are based on Langevin-type diffusion and inject additive noise, and hence the re- sulting sampling processes are not deterministic. Additionally, theoretical justifications for DDPM in the context of image in-painting have been developed by Rout et al. (2023). Moreover, conver- gence results based on the Wasserstein distance have recently been derived well (Tang. 2023 Benton et al. 2023b), although these results typically exhibit exponential dependency on the Lip- schitz constants of the score functions. Theoretical guarantees are also extended to accommodate
popular methods like consistency models and diffusion guidance (Li et al.
2024b; Wu et al. 2024).
Score matching, Hyvärinen 22055) showed that the score function can be estimated via integration
by parts, a result that was further extended in |Hyvärinen (2007). [Song et al. (2020b) proposed sliced
high dimension. The consistency of the score matching estimator was studied in [Hyvärinen| (2005). with asymptotic normality established in Forbes & Lauritzen| (2013). Optimizing the score matching loss has been shown to be intimately connected minimizing upper bounds on the Kullback-Leible divergence (Song et al. (021a) and Wasserstein distance (Kwon et al. (2022) between the generated distribution and the target data dis- tribution. From non-asymptotic perspective, Koehlerr et al. (2023) studied the statistical efficiency of score matching by connecting it with the isoperimetric properties of the distribution.
score matching to tame the computational complexity
Other theory for diffusion models. Oko et al. (2023) studied the approximation and generalization capabilities of diffusion modeling for distribution estimation. Assuming that the data are supported on a low-dimensional linear subspace, [Chnn al. (2023a) developed sample complexity bound for diffusion models. Moreover, Ghimire et al. (2023) adopted a geometric perspective and showed that the forward and backward processes of diffusion models are essentially Wasserstein gradient flows. Recently, the idea of stochastic localization, which is closely related to diffusion models, is adopted
to sample from posterior distributions (Montanari & Wu, 2023 El Alaoui et al. 2022), which has
been implemented using approximate message passing (Donoho et 2009 Li & Wei 2022).
5 DISCUSSION
In this paper, we have developed new suite of non-asymptotic theory for establishing the con- vergence and faithfulness of diffusion generative modeling, assuming access to reliable estimates of the (Stein) score functions. Our analysis framework seeks track the dynamics of the reverse process directly using elementary tools, which eliminates the need to look at the continuous-time limit and invoke the SDE and ODE toolboxes. Only the very minimal assumptions on the target data distribution are imposed. The analysis framework laid out in the current paper might shed light on how to analyze other variants of score-based generative models as well. Moving forward, there are plenty of questions that require in-depth theoretical understanding. For instance, the dimension de- pendency in our convergence results remains sub-optimal; can we further refine our theory in order to reveal tight dependency in this regard? Can we establish sharp convergence results in terms of the Wasserstein distance, which could sometimes be "closer" to how humans differentiate pictures and might potentially help relax Assumption in the case of deterministic samplers? It would also be of paramount interest to establish end-to- and-to-end performance guarantees that take into account both the score learning phase and the sampling phase.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
Y. Wei is supported in part by the the NSF grants DMS-2244554620154477 CAREER award DMS- 2143215, CCF-2106778, and the Google Research Scholar Award. Y. Chen supported in part by the Alfred P. Sloan Research Fellowship, the Google Research Scholar Award, the AFOSR grant FA9550-22-1 1-0198, the ONR grant N00014-22- 1-2354,,, and the NSF grants CCF-2221009 and CCF-1907661. Y. Chi is supported in part by the grants ONR N00014-19-1-2404, NSF CCF- 2106778, DMS-2134080 and ECCS-2126634.
REFERENCES
Brian DO Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Ap- plications, 12(3):313-326, 1982.
Jacob Austin, Daniel Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 14:11981-17993 2021.
Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Linear convergence bounds for diffusion models via stochastic localization. arXiv preprint arXiv:2308. 03660666. 2023a.
Joe Benton, George Deligiannidis, and Arnaud Doucet. Error bounds for flow matching methods. arXiv preprint arXiv:2305. 2023b.
Adam Block, Youssef Mroueh, and Alexander Rakhlin. Generative modeling with denoising auto- encoders and Langevin sampling. arXiv preprint arXiv:2002.00107 2020.
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score- generative modeling:
User-friendly bounds under minimal smoothness assumptions. arXiv preprint arXiv:2211.01911 2022a.
Minshuo Chen, Kaixuan Huang, Tuo Zhao, and Mengdi Wang. Score approximation, estima- tion and distribution recovery of diffusion models on low-dimensional data. arXiv preprint arXiv:2302.07194, 2023a.
Nanxin Chen, Yu Zhang, Heiga Zen, Ron J Weiss, Mohammad Norouzi, and William Chan. Wave- Grad: Estimating gradients for waveform generation. In International Conference on Learning Representations, 2021.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint arXiv:2209.112155 2022b.
Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ode is provably fast. arXiv preprint 23X.:23055.11798 2023b.
Sitan Chen, Giannis Daras, and Alexandros Dimakis. Restoration-deeraaation beyond linear dif- fusions: A non-asymptotic analysis for DDIM-type samplers. arXiv preprint arXiv:2303.03384, 2023c.
Florinel-Alin Croitoru, Vlad Hondru, Radu Tudor lonescu, and Mubarak Shah. Diffusion models in vision: survey, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
Valentin De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. arXiv preprint arXiv:2208.05:. 2022.
Valentin De Bortoli, James Thortoo,, Jeremy Heng, and Arnaud Doucet. Diffusion Schrödinger bridge with applications to based generative modeling. Advances in Neural Information Processing Systems, 34:17695-177099 2021.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat GANs on image synthesis. Ad- vances in Neural Information Processing Systems, 34:8780-8794, 2021.
10

---

Published as a conference paper at ICLR 2024
David L Donoho, Arian Maleki, and Andrea Montanari. Message-passiann algorithms for com- pressed sensing, Proceedings of the National Academy of Sciences, 186449):18914-1811,, 2009.
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Sampling from the sherriggoon-knkkaarice gibbs measure via algorithmic stochastic localization. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 323-334, 2022.
Peter GM Forbes and Steffen Lauritzen. Linear estimating equations for exponential families with application to Gaussian linear concentration models. Linear Algebra and its Applications, 473: 261-283, 2015.
Sandesh Ghimire, Jinyang Liu, Armand Comas, Davin Hill, Aria Masoomi, Octavia Camps, and Jennifer Dy. Geometry of score based generative models. arXiv preprint arXiv:2302.04411, 2023.
Ulrich G Haussmann and Etienne Pardoux. Time reversal of diffusions. The Annals of Probability. pp. 1188-1205, 1986.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-68511 2020.
Aapo Hyvärinen. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4), 2005.
Aapo Hyvärinen. Some extensions of score matching. Computational statistics & data analysis, 51 1112999-25122 2007.
Alexia Seiiceeu-Maartnnall Rémi Piché- Taillefer, loannis Mitliagkas, and Remi Tachet des Combes. Adversarial score matching and improved sampling for image generation. In Inter- national Conference on Learning Representations, 2021.
Tero Karras, Miika Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion- based generative models. Advances in Neural Information Processing Systems, volume 35, pp. 26565-26577, 2022.
Frederic Koehler, Alexander Heckett, and Andrej Risteski. Statistical efficiency of score matching: The view from isoperimetry. International Conference Learning Representations, 2023.
Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. DiffWave: versatile diffusion model for audio synthesis. In International Conference on Learning Representations, 2021.
Dohyun Kwon, Ying Fan, and Kangwook Lee. Score-based generative modeling secretly minimizes the wasserstein distance. In Advances Neural Information Processing Systems, 2022.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. Advances in Neural Information Processing Systems, 2022.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In International Conference Algorithmic Learning Theory, pp- 946-985, 2023.
Gen Li and Yuting Wei. A non-asymptotic framework for approximate message passing in spiked models. arXiv preprint arXiv:2208.03311. 2022.
Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Towards faster non-asymptotic convergence for diffusion-based generative models. arXiv preprint arXiv:2306.0925, 09251. 2023.
Gen Li, Yu Huang, Timofey Efimov, Yuting Wei, Yuejic Chi, and Yuxin Chen. Accelerating conver- gence of score-based diffusion models, provably. arXiv preprint arXiv:2403.0385. 2024a.
Gen Li, Zhihan Huang, and Yuting Wei. Towards a mathematical theory for consistency training in diffusion models. arXiv preprint arKiv:2402.07880 07802, 2024b.

---

Published as a conference paper at ICLR 2024
Xingchao Liu, Lemeng Wu, Mao Ye, and Qiang Liu. Let us build bridges: Understanding and extending diffusion generative models. arXiv preprint arXiv:2208. 14699, 2022.
Andrea Montanari and Yuchen Wu. Posterior sampling from the spiked models via diffusion pro- cesses, arXiv preprint arXiv:2304.11449 2023.
Kazusato Oko, Shunta Akiyama, and Taiji Suzuki. Diffusion models are minimax optimal distribu- tion estimators, arXiv preprinl arXiv:2303.016// 2023.
Jakiw Pidstrigach. Score-based generative models detect manifolds.
arXiv preprint
arXiv:2206.010/6 2022.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with CLIP latents. arXiv preprint arXiv:2204.06125, 2022.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High- resolution image synthesis with latent diffusion models. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10684-10695, 2022.
Litu Rout, Advait Parulekar, Constantine Caramanis, and Sanjay Shakkottai. A theoretical jus- tification for image inpainting using denoising diffusion probabilistic models. arXiv preprint arXiv:2302.012// 2023.
Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al. Photorealistic text-to-image diffusion models with deep language understanding. Advances in Neural Informa- lion Processing Systems, 35:36479-36494, 2022.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference Machine Learn- ing. pp. 2256-2265 2015.
Jiaming Song. Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. arXiv preprint arXiv:2010.02502, 2020a.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Yang Song, Sahaj Garg. Jiaxin Shi, and Stefano Ermon. Sliced score matching: scalable approach to density and score estimation. In Uncertainty in Artificial Intelligence, pp. 574-584, 2020b.
Yang Song, Conor Durkan, Iain Murray, and Stefano Ermon. Maximum likelihood training of score- based diffusion models. Advances in Neural Information Processing Systems, 34:1415-1422, 2021a.
Yang Song, Jascha Sohl-Dickstein, Diederík Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. International Conference on Learning Representations, 2021b
Wenpin Tang. Diffusion probabilistic models, preprint, 2023.
Wenpin Tang and Hanyang Zhao. Score-based diffusion models via stochastic differential equations-a technical tutorial. arXiv preprint arXiv:2402.07489, 2024.
Pascal Vincent. A connection between score matching and denoising autoencoders. Neural compu- tation, 23(7):1661-1644 2011.
Andre Wibisono and Kaylee Yingxi Yang. Convergence in KL divergence of the inexact Langevin algorithm with application to score-based generative models. arXiv preprint arXiv:2211.01512. 2022.
Yuchen WI, Minshuo Chen, Zihao Li, Mengdi Wang, and Yuting Wei. Theoretical insights for diffuuion guidance: A case study for gaussian mixture models. preprint, 2024.
Ling Yang. Zhilong Zhang, Yang Song, Shenda Hong. Runsheng Xu, Yue Zhao, Yingxia Shao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang. Diffusion models: A comprehensive survey of methods and applications. arXiv preprint arXiv=2209.00796, 2022.
12


Reviews:
[{"review_id": "31R2kSZkbC", "reviewer": "Reviewer_TgkF", "summary": "The paper delves into the intricacies of diffusion models, a unique class of models capable of converting noise into fresh data instances through the reversal of a Markov diffusion process. While the practical applications and capabilities of these models are well-acknowledged, there remains a gap in the comprehensive theoretical understanding of their workings. Addressing this, the authors introduce a novel non-asymptotic theory, specifically tailored to grasp the data generation mechanisms of diffusion models in a discrete-time setting. A significant contribution of their research is the establishment of convergence rates for both deterministic and stochastic samplers, given a score estimation oracle. The study underscores the importance of score estimation accuracies. Notably, this research stands apart from prior works by adopting a non-asymptotic approach, eschewing the traditional reliance on toolboxes designed for SDEs and ODEs.", "questions": "- Eq. (14), just want to confirm: should it be $dX_t = \\sqrt{1-\\beta_t}X_td_t$ instead of $-\\frac{1}{2}\\beta(t)X_t d_t$? \n- Eq. (15), maybe I am missing something, but should it be $dY = (-f(...) + \\frac{1}{2}g^2 \\nabla) d_t$? The original paper was taking a reverse form. \n- Eq. (16), similar question to Eq. (15). \n- Eq. (21), I feel a bit weird about the notation: maybe remove the $R$. \n- The results for deterministic samplers may motivate a better training strategy (i.e., incorporating the requirement for Jacobian matrices accuracy). The first step is to verify that this phenomenon exists in experiments (i.e., a worse $\\epsilon_{Jacobi}$ does imply a worse sampling result). It may be worth adding a numerical experiment to confirm this if time permits.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper offers a significant theoretical advancement by providing the convergence bounds for both stochastic and deterministic samplers of diffusion processes. I'm particularly struck by the elegance of their results, especially given the minimal assumptions required—for instance, the results for stochastic samplers rely solely on Assumption 1. These theoretical findings provide a clear understanding of the effects of score estimation inaccuracies. Furthermore, the emphasis on the estimation accuracies of Jacobian matrices for deterministic samplers sheds light on potential training strategies, suggesting the incorporation of penalties in objective functions when learning the score function for these samplers. Additionally, the proof presented is elementary, and potentially useful in a broader context.", "weaknesses": "- While this paper doesn't present any algorithmic advancements, it's understandable considering the depth of their theoretical contributions.\n\n- The proof appears to be procedural. I was hoping for deeper insights into how the proof was constructed. It might be beneficial for the authors to include a subsection detailing the outline and insights behind their proof.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "9MWDNny1bC", "reviewer": "Reviewer_ScYQ", "summary": "This paper aims to provide a systematic analysis of the convergence rate of both deterministic and stochastic samplers of the diffusion models in the context of generative modeling. The authors proves, under certain assumptions, the former has a rate of $T^{-1}$\nwhile the latter has a rate $\\sqrt{T}$ which is consistent with the previous empirical observations. The authors also proposed some improvements, leading to a rate of $T^{-2}$ in the deterministic case, and a rate of $T^{-1}$ in the stochastic case.", "questions": "See the weaknesses.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper provides an early systematic analysis on the convergence rate of samplers in the diffusion models. Both deterministic and stochastic cases are considered, and their results are almost optimal under the assumptions made. The presentation of the paper is good, and I really enjoyed reading it. Especially, I like Theorem 1.", "weaknesses": "As for every (good) paper, there are always plenty of things remained to be done. For instance,\n\n(1) It is worthy to comment on the learning rate (22a)-(22b). I understand these rates are carefully chosen in order to match the rates in the theorems. The author may mention this, or provide some explanations/insights on it.\n\n(2) The paper, like Chen et al., deals with the TV (or KL) divergence. I understand that under these metrics, one can prove \"nice\" theoretical results using some specific algebraic identities (flow...) On the other hand, practitioners may care more about the FID (or Wasserstein distance) -- part of the reason is that Wasserstein distance is \"closer\" to how humans distinguish pictures. The authors may want to add a few remarks on this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "NdlScvNTfm", "reviewer": "Reviewer_h2T8", "summary": "This paper studies the deterministic probability flow ODE-based sampler often used in practice for score-based diffusion. It shows that the ODE-based sampler gets a $1/T$ convergence rate, improving upon the SDE-based sampling rate of $1/\\sqrt{T}$. The techniques are elementary, and do not rely on Girsanov's theorem and other techniques from the SDE/ODE toolboxes. While there was prior work (Chen et. al. 2023b) that obtains an improved guarantee for the ODE-based sampler, their analysis required the use of stochastic \"corrector steps\", while in practice, even just the ODE-based sampler without corrector steps seems to perform well. This is the first work that provides theoretical evidence that the vanilla ODE-based sampler can outperform the SDE-based sampler in practice.", "questions": "- Is it clear that $1/\\sqrt{T}$ is tight for the SDE-based sampler, and $1/T$ is impossible?\n- What are the barriers to getting a $d$ or $\\sqrt{d}$ dependence? Can you write something about this in the main paper?\n- Can you include a proof overview in the main paper?\n- Why is the proof so long? Can it be condensed?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Provides the first analysis of the (vanilla) ODE-based sampler for score-based diffusion models that gives some theoretical evidence for why it outperforms the SDE-based sampler in practice ($1/T$ convergence instead of $1/\\sqrt{T}$)\n- New analysis that doesn't make use of Girsanov's theorem/other results from the ODE/SDE literature.\n- Doesn't require Lipschitzness of score unlike (Chen et al 2023b), but pays in d dependence", "weaknesses": "- $d$ dependence is worse than (Chen et al 2023b). In particular, Chen gets a $\\sqrt{d}$ dependence for the ODE-based sampler when using stochastic corrector steps, which is better than the previous bound of $d$ for the SDE-based sampler. This paper on the other hand gets a $d^3$ dependence, which is significantly worse than both these bounds. \n- Requires Jacobian of score to be estimated accurately, rather than just the score\n- Requires the distribution $q_0$ to be bounded, and bound is stated in terms of this bound. In contrast, some of the prior works only required the second moment of $q_0$ to be bounded.\n- While new analysis is \"elementary\" in that it doesn't require SDE/ODE machinery, it seems much longer/more complicated than the previous analyses. Would really appreciate a condensation/proof overview in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "La3vs3IDeZ", "reviewer": "Reviewer_nMDV", "summary": "This paper develops theoretical analyses for two variants of score-based generative models, those with deterministic (known as the probability flow ODE) and stochastic (known as denoising diffusion probabilistic models) reverse time processes, respectively. The deterministic variant is of particular interest because it has been difficult to analyze with existing techniques, despite being successful in practice. The main contribution of this work is to derive convergence guarantees for each of these processes under mild assumptions on the data distribution and the score function. Briefly, they provide an analysis of the deterministic algorithm which is the first to provide explicit rates of convergence, when the data distribution has bounded support (with only logarithmic dependence on the diameter) and when the score function and its Jacobian have been estimated. For the stochastic algorithm they recover similar results to the state-of-the-art, albeit with worse dimension dependence and stronger assumptions on the data distribution (compact support vs finite second moment).", "questions": "- Please add a remark about the fact that you prove your guarantees for convergence to the first step of the forward process (rather than the true data distribution). Of course, this is what allows for guarantees in TV with minimal assumptions on the data distribution since otherwise the data distribution could be singular, but I wonder how much this changes your results.\n- Are the step-size schemes you consider similar to those used in practice? How robust are your results to variations in the step-sizes?\n- Please discuss the utility and plausibility of the bound on the difference of Jacobians\n- Could you please clarify the meaning of \"continuous\" in the assumption on the data distribution when it is says \"$X_0$ is a continuous random vector, and\". In particular, are you assuming the data distribution has a density wrt Lebesgue here?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work studies an important problem, that of developing theoretical understanding of the efficacy of score-based methods, and focuses in particular on deterministic methods, which are not well understood theoretically. They develop the first analysis to achieve explicit rates of convergence for these methods in the literature, and achieve a strong bound under assumptions which are quite mild (except for the Jacobian assumption). For the stochastic method, they gain results which are close to the best known. Their analysis is necessarily novel and avoids technical difficulties that have forced previous works [1] to study (stochastic) modifications of the fully deterministic methods.\n\n[1] The Probability Flow ODE Is Provably Fast, by Chen et al 2023", "weaknesses": "From my point of view, the main weakness of the results is that they involve the error of the differential of the score function, and it is not clear why this would be well-controlled in general (since the score-matching objective doesn't involve the Jacobian). The prior work [2] didn't use such conditions, but then again achieved far weaker guarantees. It would be good to comment on the importance and plausibility of this condition. Less significant but nonetheless important is the authors' use of very specific step-size schemes, a remark on this would also be helpful. Finally, their convergence results are proved in TV (weaker than KL) and are not for the true data distribution, but for the distribution of the first step of the forward diffusion process.\n\nWith regard to correctness of their arguments, I was not able to carefully check this point due to the long and involved natured of their proofs but everything that I did read in the supplementary material seems correct.\n\n[2] \"Restoration-degradation beyond linear diffusions: A non-asymptotic analysis for DDIM-type samplers\" by Chen, Daras, and Dimakis 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)