The probability flow ODE is provably fast
Authors: Sitan Chen
Sinho Chewi
Holden Lee
Yuanzhi Li
Jianfeng Lu
Adil Salim
Venue: NeurIPS 2023 poster (2023)
Keywords: DDIM
deterministic samplers
diffusion models
predictor-corrector
probability flow ODE
score-based generative modeling
TL;DR: We give the first fully polynomial-time bounds for the probability flow ODE, together with a corrector based on underdamped Langevin, and obtain superior dimension dependence compared to existing analyses of SDE-based diffusion models.

Abstract: We provide the first polynomial-time convergence guarantees for the probabilistic flow ODE implementation (together with a corrector step) of score-based generative modeling. Our analysis is carried out in the wake of recent results obtaining such guarantees for the SDE-based implementation (i.e., denoising diffusion probabilistic modeling or DDPM), but requires the development of novel techniques for studying deterministic dynamics without contractivity. Through the use of a specially chosen corrector step based on the underdamped Langevin diffusion, we obtain better dimension dependence than prior works on DDPM ($O(\sqrt d)$ vs. $O(d)$, assuming smoothness of the data distribution), highlighting potential advantages of the ODE framework.

The probability flow ODE is provably fast
Sitan Chen"
Sinho Chewit
Holden Lee
Yuanzhi Li
Jianfeng Lu
Adil Salim!!
Abstract
We provide the first polynomial-time time convergence guarantees for the probability flow ODE implementation (logether with corrector step) of score-based gener- ative modeling with an OU forward process. Our analysis is carried out the wake of recent results obtaining such guarantees for the SDE-based implemen- tation (i.e., denoising diffusion probabilistic modeling or DDPM), but requires the development of novel techniques for studying deterministic dynamics without contractivity. Through the use of a specially chosen corrector step based on the un- derdamped Langevin diffusion, obtain better dimension dependence than prior works DDPM (O(vd) (d)) assuming smoothness of the data distribution), highlighting potential advantages of the ODE framework.
Introduction
Score-based generative models (SGMs) [Soh+15; 15; SE19; HJA20; DN21; Son+2la; Son+21b; VKK21] are class of generative models which includes prominent image generation systems such as DALL-E 2 [Ram+22]. Their startling empirical success at data generation across a range of appli- cation domains has made them central focus of study in the literature on deep learning [Aus+21; DN21; Kin+21; Shi+211; CSY22; Gna+22; Rom+22; Son+22; BV23; WHZ23]. In this paper, we aim to provide theoretical grounding for such models and thereby elucidate the mechanisms driving their remarkable performance.
Our work follows the wake of numerous recent works which have provided convergence guarantees for denoising diffusion probabilistic models (DDPMs) [De +21; BMR22: De 22; LLT22; Liu+22; Pid22; WY22; Che+23a; CLL23; LLT23] and denoising diffusion implicit models (DDIMs) [CDD23]. We briefly recall that the generating process for SGMs is the time reversal of a certain diffusion process, and that DDPMs hinge upon implementing the reverse diffusion process as stochastic differential equation (SDE) whose coefficients are learned via neural network training and the statistical technique of score matching [Hyv05; Vin 1] (more detailed background is provided in $2). Among these prior works, the concurrent results of [Che+23a; LLT23] are remarkable because they require minimal assumptions on the data distribution (in particular, they do not assume log-concavity or similarly restrictive conditions) and they hold when the errors incurred during score matching are only bounded in an 2 sense, which is both natural in view of the derivation of score matching (see [Hyv05; Vin IJ) and far more realistic." Subsequently, the work of [CLL23] significantly sharpened the analysis in the case when no smoothness assumptions are imposed on the data distribution.
Harvard University, si sitansseas. harvard. edu I Institute for Advanced Study, schewi dias.. edu JJhhns Hopkins University, hlee2838jhu, edu 8 Microsoff Research, yuanzhil hi @mi crosoft. com
Duke University, engmmahhh duke. edu ll Microsoft Research, adilsalim@@mirrosei
com
bounded in _ sense, since cannot hope to learn the score function in regions of the state space which are not well-covered by the training data.
'It is unreasonable, for instance. assume that the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Taken together, these works paint an encouraging picture of our understanding of DDPMs which takes into account both the diversity of data in applications (including data distributions which are highly multimodal or supported on lower-dimensional manifolds), as well as the non-convex training process which is not guaranteed to accurately learn the score function uniformly in space.
Besides DDPMs, instead of implementing the time reversed diffusion as an SDE, it is also possible to implement it as an ordinary differential equation (ODE), called the probability flow ODE [Son+21b]; see $2. The ODE implementation is often claimed to be faster than the SDE implementation [Lu+22; ZC23], with the rationale being that ODE discretization is typically more accurate than SDE dis- cretization, so that one could use larger step size. Indeed, the discretization error usually depends on the regularity of the trajectories, which is C' for ODEs but only C# for SDEs (i.e., Hölder continuous with any exponent less than 2)) due to the roughness of the Brownian motion driving the evolution.
Far from being able to capture this intuition, current analyses of SGMs cannot even provide polynomial-time analysis of the probability flow ODE. The key issue is that under our minimal assumptions (i.e., without concavity of the data distribution), the underlying dynamics of either the ODE or SDE implementation are not contractive, and hence small errors quickly accumulate and are magnified. The aforementioned analyses of DDPMs managed overcome this challenge by leveraging techniques specific to the analysis of SDEs, through which we now understand that stochasticity plays an important role in alleviating error accumulation. is unknown, however, how to carry out the analysis for the purely deterministic dynamics inherent to the probability flow ODE.
Our first main contribution is to give the first convergence guarantees for SGMs with OU forward dynamics in which steps of the discretized probability flow ODE-referred to as predictor steps-are interleaved with corrector steps which runs the overdamped Langevin diffusion with estimated score, as pioneered in [Son+21b]. Our results are akin to prior works on DDPMs in that they hold under minimal assumptions on the data distribution and under L bounds on the score estimation error, and our guarantees scale polynomially in all relevant problem parameters. Here, the corrector steps inject stochasticity which is crucial for our proofs; however, we emphasize that the use of corrector steps does not simply reduce the problem to applying existing DDPM analyses. Instead, we must develop an entirely new framework based on Wasserstein to-TVV regularization, which of independent interest; see $4 for a detailed overview of our techniques. Our results naturally raise the question of whether the corrector steps are necessary in practice, and we discuss this further $5.
When the data distribution is log-smooth, then the dimension dependence of prior results on DDPMs, as well as our first result for the probability flow ODE with overdamped corrector, both scale as O(d). Does this contradict the intuition that ODE discretization is more accurate than SDE discretization? The answer no; upon inspecting our proof, we see that the discretization error of the probability flow ODE is indeed smaller than what is incurred by DDPMs, and in fact allows for a larger step size of order 1/Vd. The bottleneck in our result stems from the use of the overdamped Langevin diffusion for the corrector steps. Taking inspiration from the literature on log-concave sampling (see, e.g., [Che22] for an exposition), our second main contribution is to propose corrector steps based on the underdamped Langevin diffusion (see $2) which is known to improve the dimension dependence of sampling. In particular, we show that the probability flow ODE with underdamped Langevin corrector attains ((Vd) dimension dependence. This dependence is better than what was obtained for DDPMs in [Che+23a; CLL23; LLT23] and therefore highlights the potential benefits of the ODE framework. We note that the benefit to which we refer is at generation time, and not at training time.
Previously, [JP22] have proposed "noise- denoise" sampler using the underdamped Langevin diffusion. but to our knowledge, our work is the first to use it in conjunction with the probability flow ODE, Although we provide preliminary numerical experiments in the Appendix, we leave as a question for future work to determine whether the theoretical benefits of the underdamped Langevin corrector are also borne out in practice.
1.1 Our contributions
In summary, our contributions are the following.
We provide the first convergence guarantees for the probability flow ODE with overdamped Langevin corrector (DPOM; Algorithm l).
2

---

We propose an algorithm based on the probability flow ODE with underdamped Langevin corrector (DPUM; Algorithm 2).
We provide the first convergence guarantees for DPUM. These convergence guarantees show improvement over (i) the complexity of DPOM (O(vd) vs O(d)) and (ii) the complexity of DDPMs, ie., SDE implementations of score-based generative models (again, O(vd) vs (d)).
We provide preliminary numerical experiments in a toy example showing that DPUM can sample from a highly non log-concave distribution (see Appendix). The numerical experiments are not among our main contributions and are provided for illustration only. The Python code can be found in the Supplementary material.
Our main theorem can be summarized informally as follows; see $3 for more detailed statements.
Theorem 1 (Informal). Assume that the score function along the forward process is L-Lipschitz. and that the data distribution has finite second moment. Assume that we have access to ( -accucraee score estimates. Then, the probability flow ODE implementation of the reversed Ornstein- Uhlenbeck process, when interspersed with either the overdamped Langevin corrector ( (DPOM: Algo- rithm 1) or with the underdamped Langevin corrector (DPUM: Algorithm 2), oulputs sample whose law is E-close in total variation distance to the data distribution, using ((Ldd/eP) Ö(L iterations respectively.
Our result provides the first polynomial-tine guarantees for the probability flow ODE implementation of SGMs. so long as it is combined with the of corrector steps. Moreover, when the corrector steps are based on the underdamped Langevin diffusion, then the dimension dependence of our result significantly smaller (O(vd) vs. (dd) than prior works on the complexity of DDPMs, and thus provides justification for the use of ODE discretization in practice, compared to SDEs.
Our main assumption on the data is that the score functions along the forward process are Lipschitz distributions, yet does not cover non-smooth
continuous, which allows for highly non-log-concee distributions such as distributions supported on lower-dimensional manifolds. However, as shown in [Che+23a; CLL23; LLT23], we can also obtain polynomial-time guarantees without this smooth- ness assumption via early stopping (see Remark I).
1.2 Related works
The idea of using a reve-reversed diffusion for sampling has been fruitfully exploited in the log- concave sampling literature via the proximal sampler (TP18; LST21; CE22; LC22; FYC23; LC23], as put forth in [Che+22], as well as through algorithmic stochastic localization [EMS22; MW23]. Although we do not aim be comprehensive in discussion of the literature, we mention, e.g.. [ABV23; Che+23b] for alternative approaches for diffusion models. We also note that the recent work of [CDD23] obtained discretization analysis for the probability flow ODE (without corrector) in KL divergence, though their bounds have a large dependence on d and are exponential in the Lipschitz constant of the score integrated over time.
Since the original arXiv submission of this paper, there have been further works studying the probability flow ODE. The work of [BDD23] also studied the probability flow ODE, but without providing discretization guarantees (and with possibly exponential dependencies). The work [Li+23] provides polynomial-tima guarantees for the probability flow ODE (without corrector steps), the cost of larger polynomial dependencies and more stringent score assumptions (namely, bounds on the Jacobian of the score). Also, [PMM23] study another variant of the predictor-corrector framework.
2 Preliminaries
2.1 Score-based generative modeling
Let q. denote the data distribution, i.e., the distribution from which we wish to sample. In score-based generative modeling, define forward process (g;²) 2)20 with go" 9.. which transforms data distribution into noise. In this paper, we focus on the canonical choice of the
3

---

(OU) process,
dr = - di + vdd,,,
T6" ~ q+ 4e = law (27"))
where (22) is standard Brownian motion in Rdd. It is well-known that the OU process mixes rapidly (exponentially fast) to its stationary distribution, the standard Gaussian distribution yd. Once we fix time horizon T > 0, the time reversal of the SDE defined in (1) over [0, T] is given by
dæ = (z) + 2 2n (x))) dl V2dB.,
(2)
where qi= = -7 and the reverse SDE is generative model: of Since 20 47 2 20 , the reverse SDE transforms samples from y (i.e., pure noise) into approximate samples from q.- order to implement the reverse SDE, however, one needs to estimate the score functions V In for t [0, T using the technique of score matching [Hyv05; Vinll] 1]. In practice, the score estimates are produced via a deep neural network, and our main assumption is that these score estimates accurate in L sense (see Assumption 4). This gives rise to the denoising diffusion probabilistic modeling (DDPM) algorithm.
when initialized at zū ~ -0. then
Notation.
Since the reverse process the primary object of interest, we drop the arrow from the notation for simplicity; thus, == T- We will always denote the forward process with the arrow >. For each & [0, 21. let st denote the estimate for the score In V Vn
2.2 Probability flow ODE (predictor steps)
Instead of running the reverse SDE (2), there is in fact an alternative process (#1) which evolves according an ODE (and hence evolves deterministically) and yet has the same marginals (2). This alternative process, called the probability flow ODE, can also be used for generative modeling.
One particularly illuminating way of deriving the probability flow ODE is to invoke the celebrated theorem, due to [JKO98], that the OU process is the Wasserstein gradient flow of the KI. divergence functional (i.e. relative entropy) KL(- >d). From the general theory of Wasserstein gradient flows (see [AGS08; S5n] the Wasserstein gradient flow (He)22 of a functional can be implemented via the dynamics
& - Vw,
20 ~ P4,
KL( || 7d), ) arrive the forward process in that 2, pe for all 0. Applying this F
v In
(z))) - v In (z7").
(3)
Setting = -1 it is easily seen that the time reversal of (3) is
d = Jx V ll i.c., d = V In (x)))
(4)
which is called the probability flow ODE. In this paper. the interpretation of the probability flow ODE as reverse Wasserstein gradient flow is only introduced for interpretability, and the reader who unfamiliar with Wasserstein calculus can take (4) to be the definition the probability flow ODE. Crucially, it has the property that if 2g
qu. then D2 q for all E [0, T).
We can discretize the ODE (4). Fixing step size h > 0, replacing the score function V In q: with the estimated score given by and applying the exponential integrator to the ODE (i.e., exactly integrating the linear part), we arrive the discretized process
Fith 24 S/" Deta du + hx(3)) exp(h) x. (exp(h) 1) sx(x))
(5)
2.3
Corrector steps
Let be distribution over R.d and write U as shorthand for the potential In g.

---

Overdamped Langevin. The overdamped Langevin diffuusion with potential U is stochastic process (#e)220 over I2 given by
dæ, = -UU dt v2dB,
The stationary distribution of this diffusion is & -x)(
We also consider the following discretized process where VU is replaced by score estimate Fix a step size and let (fz) over Rd be given by
dæ s( [t/h)
v2dB,.
Underdamped Langevin. Langevin difsasion is stochastic process (Zz, vt)220 over Rd x Rd given by
Given friction parameter y > 0, the corresponding underdamped
dz, U2 dt, de - (vU(z,) + yv,) + /2ydB..
The stationary distribution of this diffusion is @ 7d.
We also consider the following discretized process, where VU is replaced by estimate Let (2,, 02) 82)220 over Rd x Rdd be given by
d& = 0z dt,
(6)
dē. (s(21e/N) -0.) 2dd
Diffusions as corrector steps. At time i, the law of the ideal reverse process (4) initialized at go is de However, errors are accumulated through the course of the algorithm: the error from initializing at 7d rather than at qo: eπrors arising from discretization of (4); and errors in estimating the score function. That's why the law of the algorithm's 's iterate will not be exactly qr. We propose use either the overdamped or the underdamped Langevin diffusion with stationary distribution and estimated score as corrector, in order to bring the law of the algorithm iterate closer to gt- the case of the underdamped Langevin diffusion, this is done by drawing independent Gaussian random variable To 7d running the system (6) starting from (Eo, Up) (where Eo is the current algorithm iterate) for some time t, and then keeping 2, In our theoretical analysis, the use of corrector steps boosts the accuracy and efficiency of the SGM.
3 Results
3.1 Assumptions
We make the following mild assumptions on the data distribution q. and the score estimate Assumption (second moment bound). We assume that m = E.g [1l-[12] oc.
Assumption 2 (Lipschitz score). For all E [0, TT, the score V In gr is L-Lipschitz, for some L 2 1. Assumption (Liipschtzz score estimate). For all t for which we need to estimate the score function in our algorithms, the score estimate st is L-Lipschitz.
Assumption (score estimation error). For all ffror which we need to estimate the score function in our algorithms,
Eg [1|s gl
Assumptions 2, and 4 are standard and were shown in [Che+23a; CLL23; LLT23] to suffice for obtaining polynomial-time convergence guarantees for DDPMs. The new condition that we require our analysis is Assumption 3, which was used [LLT22] but ultimately shown to be unnecessary for DDPMs. We leave it as open question whether this can be lifted in the ODE setting.
Remark 1. As observed in [Che+23a; CLL23; LLT23], Assumption 2 can be removed via early stopping, the cost of polynomially larger iteration complexity. The idea is that if q. has compact support but does not necessarily satisfy Assumption (e.g.. if q. is supported on a compact and lower-dimensional manifold), then 95* will satisfy Assumption 2 8 > O. By applying our analysis up to time T å instead of time T, one can show that suitable projection of the output distribution close in Wasserstein distance ę+ (see [CLL.23, Corollary 2.4] or [Che+23a, Corollary 5)). For brevity, we do not consider this extension of our results here.
5

---

3.2 Algorithms
We provide the pseudocode for the two algorithms we consider, Diffiusion Predictor + Overdamped Modeling (DPOM) and Diffusion Predictor Underdamped Modeling (DPUM), in Algorithms and 2 respectively. The only difference between the two algorithms is in the corrector step, which we highlight Algorithm 2. For simplicity, we take the total amount of time to be equal to No/ + h pred for an integer No 2 1, and we assume that I/L is multiple of Mpred and that Rpred is a multiple of
(I=
We consider two stages: in the first stage, which lasts until time No/L Apred, we intersperse predictor epochs (run for time L,L, discretized with step size hpped and corrector epochs (run for time (1)L) for the overdamped corrector or for time ((1/vL) )) for the underdamped corrector, and discretized with step size hearr). The second stage lasts from time T Prred to time T 6, and we incorporate geometrically decreasing step sizes for the predictor. Note that this implies that our algorithm uses early stopping.
Algorithm 1: DPOM(T, hpprdd heorrs
Input: Total time T' predictor step size hppred- corrector step size /eorr, score estimates 8 Output: Approximate sample from the data distribution Q.
Draw 20 ~ ~/
for n 0.1,........ No do
Predictor: Starting from L run the discretized probability flow ODE (5) from time z.2 to
12-1 with step size hpred and estimated scores obtain (((+1//L'
I.
Corrector: Starting from (( run overdamped Langevin Monte Carlo for total time
@(1/L) with step size hearr and score estimate $nn+1//r. to obtain ((++)//T.
$ Predictor: Starting from Tr haa run the discretized probability flow ODE (5) with step sizes Mprre/ hppred /4, h/pred/8, 18.ed/ and estimated scores to obtain Ty TT-5-
Corrector: Starting from - 5. run overdamped Langevin Monte Carlo for total time ((1LL)
with step size heorr and score estimate sy-6 to obtain PT-5-
return 2T-5
Algorithm 2: DPUM(T, hpredd bcor:: S)
Input: Total time T, predictor step size hapred- corrector step size heors, score estimates Output: Approximate sample from the data distribution q.
Draw 20 ~ ~/t
2 for n = 0,
do Predictor: Starting from F./LL the discretized probability flow ODE (5) from time ",
n+1 with step size hpred and estimated scores obtain T ((
Corrector: Starting from & (x+1)/L'' run underdamped Langevin Monte Carlo for total time
@(1/VL) with step size hearr and score estimate 8(n+1)/L to obtain B(n+1)/L-
5 Predictor:
Starting from êT hand run the discretized probability flow ODE (5) with step sizes hprea/22 /prea/4, ltpred/ .,.. and estimated scores to obtain 7 Corrector: Starting from - s run underdamped Langevin Monte Carlo for total time 0(1/VL) with step size hearr and score estimate $T-5 to obtain Tr-6-
7 return ZT-8
3.3 Convergence guarantees
Our main results are the following convergence guarantees for the two predictor-comrector schemes described in $3.2:

---

Theorem 2 (DPOM). Suppose that Assumptions 1-4 hold. If q denotes the output of DPOM (Algorithm 1) with 8 La (dvm3)' then
TV(ū,g-) (vdv m2) exp(- + I.2 hpred + /22
corr + 11 + E. (7)
In particular, if we set T = (In( dvm3) )). lipred = O( (=aT1) heam = O ( ( and if the score
estimation error satisfies Esc S ( (T) then we can obtain TV errorg & with total iteration complexity
of ④ L'd) 22 steps.
The five terms in the bound (7) correspond, respectively, to: the convergence of the forward (OU) process; the discretization error from the predictor steps; the discretization error from the corrector steps; the score estimation error; and the early stopping emor.
Theorem 2 recovers nearly the same guarantees as the one in [Che+23a; CLL23; LLT23], but for the probability flow ODE with overdamped Langevin corrector instead of the reverse SDE without corrector. Recall also from Remark that our results can easily be extended compactly supported data distributions without smooth score functions. This covers essentially all distributions encountered in practice. Therefore, our result provides compelling theoretical justification complementing the empirical efficacy of the probability flow ODE, which was hitherto absent from the literature.
However, in Theorem 2, the iteration complexity is dominated by the corrector steps. Next, we show that by replacing the overdamped LMC with underdamped LMC, we can achieve a quadratic im- provement in the number of steps, considering the dependence d. As discussed in the Introduction, this highlights the potential benefits of the ODE framework over the SDE.
Theorem 3 (DPUM). Suppose that Assumptions 1-4 hold. If q denotes the output of DPUM (Algorithm 2) with 5 = L [dvmm]] then
TV(A.-)) S (Vā m2) exp(-T) (xxpp(TT))))) + T.2Td' (2 Miree + T.3/2Td/22ooo + 1. + In particular, if we set T @lnn (((n(=mm²)) lipred O (=ptrs) hear
Ô ( and if the score estimation error satisfies esc S 0 (tt) then we can obtain TV error with total iteration complexity of 0f 122 steps.
4 Proof overview
Here we give a detailed technical overview for the proof of our main results, Theorems 2 and 3. As in [Che+23a; CLL23; LLT23], the three sources of error that we need to keep track of are (1) estimation of the score function; (2) discretization time when implementing the probability flow ODE and corrector steps; and (3) initialization of the algorithm 7d instead of the true law of the end of the forward process, G0 = 47' It turns out that (1) is not so difficult to manage as soon as we can control (2) and (3). Furthermore, as in prior work,
can casily control (3) via the data-procsssing inequality: the total variation distance between the output of the algorithm initialized at go versus at yd is at most TV(?7,""") r()), which is exponentially small in T by rapid mixing of the OU process. So henceforth in this overview, let us assume that both the algorithm and the true process are initialized Zo- It remains control (2).
Failure of existing approaches. the SDE implementation of diffusion models, prior works handled (2) by directly bounding strictly larger quantity, namely the KI. divergence between the laws of the trajectories of the algorithm and the true process; by Girsanov's 's theorem, this has a integrated difference of drifts. Unfortunately, in the ODE implementation. this KL divergence is infinite: in the absence of stochasticity in the reverse process, these laws over trajectories are not even absolutely continuous with respect to each other.
clean formulation
In search of an alternative approach, one might try a Wasserstein analysis. As first attempt, we could couple the initialization of both processes and look at how the distance between them changes over time. If (Z: JoSEST and (rr)oSITT denote the algorithm and true process, then smoothness of the score function allows us to naively bound 0 [[[ ensures that the processes are close if run for time < 1/ T., does not rule out the possibility that they drift apart exponentially quickly after time L/L.
[|]]]]]]] by ((L) El||s 1=1. While this
7

---

Restarting the coupling-fire attempt. What we would like is some way of "restarting" this coupling before the processes drift too far apart, to avoid this exponential compounding. We now motivate how to achieve this by giving an argument that is incorrect but nevertheless captures the intuition for our approach. Namely, let p: == law( denote the law of the algorithm, let ploy denote the result of running the ideal probability flow ODE for time h starting from time tu, and let Pto-h denote the same but for the discretized probability flow ODE with estimated score. For ODE h S L/L, consider the law of the two processes at time 2h, i.c.
P2h To P0.22
and T2h 40 P0.25
(8)
The discussion above implies that qo Polk and go POPE are close in 2- W-ssserstnein distance, so by the data-processin processing inequality, this implies that qu PODE ODE and P A are also close. To show that P2h and 92Λ in Eq. (8) are close, it thus suffices show that Po and go Po t are close. But these two distributions are given by running the algorithm and the true process for time h. both starting from qo PODE So if we "restart" the coupling by coupling the processes based on their locations at time h, rather than time O, of the reverse process, we can again apply the naïve Wasserstein analysis.
ODE
At this juncture, it would seem that we have miraculously sidestepped the exponential blowup and shown that the expected distance between the processes only increases linearly over time! The issue of course is in the application of the "data-processing inequality," which simply does not hold for the Wasserstein distance.
Restarting the coupling with a corrector step. This is where the corrector comes in. The idea is to use short-time regularization: if we apply a small amount of noise to two distributions which are already close in Wasserstein, then they become close in KL divergence, for which data-processing inequality holds. The upshot is that if the noise doesn't change the distributions too much, then we can legitimately restart the coupling as above and prove that the distance between the processes, now defined by interleaving the probability flow ODE and its discretization with periodic injections of noise, increases only linearly in time.
turns out that naïve injection of noise, e.g., convolution with Gaussian of small variance, is somewhat wasteful as it fails to preserve the true process and leads to poor polynomial dependence in the dimension. On the other hand, if we instead run the overdamped Langevin diffusion with potential chosen that the law of the true process is stationary, then can recover the linear in d dependence of Theorem 2. Then by replacing overdamped Langevin diffusion with its underdamped counterpart, which has the advantage of much smoother trajectories, we can obtain the desired quadratic speedup in dimension dependence in Theorem 3.
Score perturbation lemma. In addition to the switch from SDE to ODE and the use of the underdamped corrector, a third ingredient is essential our improved dimension dependence. The former two ensure that the trajectory of our algorithm is smoother than that of DDPMs, so that even over time windows that scale with 1/vd, the process does not change too much. By extension, as the score functions are Lipschitz, this means that any fixed score function evaluated over iterates in such a window does not change much. This amounts to controlling discretization error in space.
It is also necessary to control discretization error in time, i.e., proving what some prior works referred to as a score perturbation lemma [LLT22]] That is, for any fixed iterate x, we want to show that the score function V In qe (x) does not change too much / varies over a small window. Unfortunately, prior works were only able to establish this over windows of length 1/d. In this work, we improve this to windows of length 1/vd d (see Lemma 3 and Corollary 1).
In our proof, we bound the squared 1,2 norm of the derivative of the score along the trajectory of the ODE. The score function evaluated at y can be expressed as Ep, ((lw) [VU]; [VU) here, the posterior distribution P- y) is essentially the prior g. tilted by a Gaussian of variance O(t). Hence we need to bound the change the expectation when we change the distribution from Poje to Pole+Ari Ari because VU is L-Lipschitz, we can bound this by the Wasserstein distance between the distributions. For small enough I, Poje is strongly log-concave, and a transport cost inequality bounds this in terms of KI. divergence, which is more easily bounded. Indeed, we can bound it with the KI divergence between the joint distributions Pa., and Po.tArr which reduces to bounding the KI. divergence between Gaussians of unequal variance.
8

---

However, since our score perturbation lemma degrades near the beginning of the forward process, we require better control the discretization error during this part of the algorithm, hence leading to our choice of geometrically decreasing step sizes. Alternatively, we could use two-stage step size schedule, see Remark
Conclusion
In this work, we have provided the first polynomial guarantees for the probability flow ODE implementation of SGMs with corrector steps and exhibited improved dimension dependence of the ODE framework over prior results for DDPMs (i.e. the SDE framework). Our analysis raises questions relevant for practice, of which we list a few.
Although need the corrector steps for our proof, are they in fact necessary for the algorithm to work efficiently in practice?
Is it possible to obtain even better dimension dependence, perhaps using higher-order solvers and stronger smoothness assumptions?
Can we obtain improved dimension dependence even in the non-smooth setting, compared to the result of [CLL23]]
We also list several limitations of our work, namely:
Our analysis only covers the probability flow ODE corresponding to the OU forward process. We leave the study of more general dynamics for future study.
Our guarantees require the score function to be learned to L accuracy ((e/VL), which is more stringent than the prior works [Che+23a; CLL23; LLT23] and may be an technical artefact of our proof.
We have not validated our theoretical findings with large-scale experiments. In particular, is still unclear whether flw-bbsed methods can outperform the standard DDPM algorithm in practical, high dimensional settings.
Acknowledgments
We want to thank Yin Tat Lee for his valuable comments, shaping the direction of this research project in its early stages. SC was supported by NSF Award 2103300 for part of this work.
References
(ABV23]
S. Albergo, M. Boffi, and E. Vanden-Eijnden. "Stochastic interpolants: a unifying framework for flows and diffusions". In: arXiv preprint 2303.08797 (2023).
[AGS08]
L. Ambrosio, N. Gigli, and G. Savaré. Gradient flows metric spaces and the space of probability measures. Second. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 2008, pp. X+334.
[Aus+21] Austin, D. D. Johnson, Ho, D. Tarlow, and van den Berg. "Structured denoising diffusion models in discrete state-spaces". In: Advances in Neural Information Pro- cessing Systems. Ed. by M. Ranzato, A. Beygelzimer, Dauphin, P. Liang, and W. Vaughan. Vol. 34. Curran Associates, Inc., 2021, pp. 17981-17993.
[BDD23)
J. Benton, G. Deligiannidis, and A. Doucet. "Error bounds for flow matching methods".
In: arXiv preprint 2305. /6860 (2023).
[BGLO1]
S. G. Bobkov, I. Gentil, and M. Ledoux. "Hypercontractivity of Hamilton-Jacon equations". In: Journal de Mathématiques Pures et Appliquées 80.7 (2001), pp. 669 696
[BMR22]
A. Block, Y. Mrouch, and A. Rakhlin. "Generative modeling with denoising auto- encoders and Langevin sampling". In: arXiv preprint 2002.00 00107 (2022). N. M. Boffi and E. Vanden-Eiinden, "Probability flow solution of the Fokker-Planck equation". In: Machine Learning: Science and Technology 4.3 (July 2023), p. 035012.
[BV23]

---

[CDD23]
S. Chen, G. Daras, and A. Dimakis. "Restoration-degradee beyond linear diffusions: non-asymptotic analysis for DDIM-type samplers". In: Proceedings of the 40th International Conference on Machine Learning. Ed. by A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett. Vol. 202. Proceedings of Machine Learning Research. PMLR, July 2023, pp. 1462-4484.
[CE22]
Y. Chen and R. Eldan. "Localization schemes: a framework for proving mixing bounds for Markov chains". In: arXiv preprint 2203.04163 (2022).
[Che+22]
Y. Chen, S. Chewi, A. Salim, and A. Wibisono. "Improved analysis for a proximal algorithm for sampling". In: Proceedings of Thirty Fifth Conference on Learning Theory, Ed. by P.-L. Loh and M. Raginsky. Vol. 178. Proceedings of Machine Learning Research. PMLR, July 2022, pp. 2984-3014.
[Che+23a] S. Chen, S. Chewi, Li, Y. Li, A. Salim, and R. Zhang. "Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions". In: The Eleventh International Conference on Learning Representations. 2023.
[Che+23b] Y. Chen, W. Deng. S. Fang, F. Li, N. T. Yang, Y. Zhang, K. Rasul, S. Zhe, A. Schneider, and Y. Nevmyvaka. "Provably convergent Schrödinger bridge with applications to prob- abilistic time series imputation". " In: Proceedings of the 40th International Conference on Machine Learning. Ed. by A. Krause, E. Brunskill, K. Cho. B. Engelhardt, S. Sabato, and J. Scarlett. Vol. 202. Proceedings of Machine Learning Research. PMLR, July 2023, pp. 4485 4513.
[Che22]
S. Chewi. Log-concave sampling. Book draft available https : / chewisinho. gi github. i...i..2000 2022.
[CLL23]
H. Chen, H. Lee, and J. Lu. "Improved analysis of score-based generative modeling: user-friendly bounds under minimal smoothness assumptions" In: Proceedings of the 40th International Conference on Machine Learning. Ed. by A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett. Vol. 202. Proceedings of Machine Learning Research. PMLR, July 2023, pp. 4735-4763.
(CSY22)
H. Chung, B. Sim, and J. Ye. "Come-closer-diee diffuuse-fssterr accelerating conditional dif- fusion models for inverse problems through stochastic contraction". In: 2022 IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR). Los Alamitos, CA,
USA: IEEE Computer Society, June 2022, pp. 12403-12412.
[De +21]
V. De Bortoli, J. Thornton, J. Heng, and A. Doucet. "Diffusion Schrödinger bridge with applications to score-based generative modeling". In: Advances in Neural Information Processing Systems. Ed. by M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and W. Vaughan. Vol. 34. Curran Associates, Inc., 2021, pp. 17695-17709.
[De 22]
V. De Bortoli. "Convergence of denoising diffusion models under the manifold hypoth- esis". In: Transactions on Machine Learning Research (2022).
[DN21]
P. Dhariwal and A. Nichol. "Diffusion models beat GANs on image synthesis". In: Advances in Neural Information Processing Systems. Ed. by M. Ranzato, A. Beygelz- imer, Y. Dauphin, P. Liang, and J. W. Vaughan. Vol. 34. Curran Associates, Inc., 2021, pp. 8780-8794.
[EMS22]
A. EI Alaoui, A. Montanari, and M. Sellke. "Sampling from the Bheriigton-KKrrpattick Gibbs measure via algorithmic stochastic localization". In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science- FOCS 2022. IEEE Computer Soc., Los Alamitos, CA, 2022, pp. 323-334.
[FYC23]
Fan, B. Yuan, and Y. Chen. "Improved dimension dependence of a proximal algorithm for sampling". In: Proceedings of Thirty Sixth Conference on Learning Theory. Fd. by G. Neu and L. Rosasco. Vol. 195. Proceedings of Machine Learning Research. PMLR, July 2023, pp. 1473-1521.
[Gna+22]
D. Gnaneshwar, B. Ramsundar, D. Gandhi, R. Kurchin, and V. Viswanathan. "Score- based generative models for molecule generation". In: arXiv preprint 2203.0462 (2022).
[GW12]
A. Guillin and F.-Y. Wang. "Degenerate Fokker-Planck equations: Bismut formula, gradient estimate and Harnack inequality". In: Journal of Differential Equations 253.1 (2012), pp. 20 20-40.
(HJA20)
Ho, Jain, and P. Abbeel. "Denoising diffusion probabilistic models". In: Advances in Neural Information Processing Systems 33 (2020), pp. 6840-6851.
10

---

[Hyv05]
A. Hyvärinen. "Estimation of non -ormmnoae statistical models by score matching". In: Mach. Learn. Res. 6 (2005). pp. 695-709.
[JKO98]
R. Jordan, D. Kinderlehrer, and F. Otto. "The variational formulation of the Fokker- Planck equation" In: SIAM J. Math. Anal. 29.1 (1998), pp. 1-17.
[JP22]
A. Jain and B. Poole. "Journey to the BAOAB-limit, finding effective MCMC samplers for score-based models". In: NeurIPS 2022 Workshop on Score- Based Methods. 2022.
[Kin+21]
D. Kingma, T. Salimans, B. Poole, and J. Ho. "Variational diffusion models". In: Ad- vances in Neural Information Processing Systems. Ed. by M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan. Vol. 34. Curran Associates, Inc., 2021,
pp. 21696-1622111 21707.
[LC22]
Liang and Y. Chen. "A proximal algorithm for sampling from non-smooth potentials". In: arXiv preprint 2110.04597 (2022).
[LC23]
Liang and Y. Chen. "A proximal algorithm for sampling". In: Transactions on Machine Learning Research (2023).
[Li+23]
G. Li, Y. Wei, Y. Chen, and Y. Chi. "Towards faster non non-asymptotic convergence for diffusion-basee generative models". In: arXiv preprint 2306 2306.0925/ (2023).
[Liu+22]
X. Liu, L. Wu, M. Ye, and Q. Liu. "Let us build bridges: understanding and extending diffusion generative models". In: arXiv preprint arXiv:2208. 14699 (2022).
[LLT22]
H. Lee, Lu, and Tan. "Convergence for score-based generative modeling with polynomial complexity". In: Advances in Neural Information Processing Systems. Ed. by A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho. 2022.
[LLT23]
H. Lee, J. Lu, and Y. Tan. "Convergence score-based generative modeling for general data distributions". In: Proceedings of the 34th International Conference on Algorithmic Learning Theory. Ed. by S. Agrawal and F. Orabona. Vol. 201. Proceedings of Machine Learning Research. PMLR, Feb. 2023, pp. 946-985.
[LST21]
Y. T. Lee, R. Shen, and K. Tian. "Structured logconcave sampling with restricted Gaussian oracle". In: P Proceedings of Thirty Fourth Conference on Learning Theory. Ed. by M. Belkin and S. Kpotufe. Vol. 134. Proceedings Machine Learning Research. PMLR, Aug. 2021, pp. 2993-3050.
[Lu+22]
C. Lu, Y. Zhou, F. Bao, J. Chen, C. Li, and J. Zhu. "DPM-Solver: fast ODE solver for diffusion probabilistic model sampling in around 10 steps". In: Advances in Neural Information Processing Systems. Ed. by S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh. Vol. 35. Curran Associates, Inc., 2022, pp. 5775-5787. A. Montanari and Y. Wu. "Posterior sampling from the spiked models via diffusion processes". In: arXiv preprint 2304. / /449 (2023).
[MW23]
[Pid22]
Pidstrigach. "Score- generative models detect manifolds". In: Advances in Neural Information Processing Systems. Ed. by S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh. Vol. 35. Curran Associates, Inc., 2022, pp. 35852-35865. F. Pedrotti, J. Maas, and M. Mondelli. "Improved convergence of cosed diffusion models via prediction-correctionn In: arXiv preprint 14164 (2023).
[PMM23]
[Ram+22] A. Ramesh, P. Dhariwal, A. Nichol, C. Chu, and M. Chen. "Hierarchical text-conditional image generation with CLIP latents". In: arXiv preprint arXiv:2204.065 (2022). [Rom+22] R. Rombach, A. Blatmann, D. Lorenz, P. Esser, and B. Ommer. "High-resolution image synthesis with latent diffusion models". .. In: 2022 IEEE/CVF Conference on Computer Vision and Patlern Recognition (CVPR). Los Alamitos, CA, USA: IEEE Computer Society, June 2022, pp. 10674-10685.
[San15]
F. Santambrogio. Optimal transport for applied mathematicians. Vol. 87. Progress in Nonlinear Differential Equations and their Applications. Calculus of variations, PDEs, and modeling. Birkhäuser/Springer Cham, 2015, pp. xxvii+353.
[SE19]
Y. Song and S. Ermon. "Generative modeling by estimating gradients of the data distri- bution". In: Advances in Neural Information Processing Systems. Ed. by H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett. Vol. 32. Curran Associates, Inc., 2019.
11

---

[Shi+21]
C. Shi, S. Luo, M. Xu, and J. Tang. "Learning gradient fields for molecular conformation generation" In: Proceedings of the 38th International Conference on Machine Learning. Ed. by M. Meila and T. Zhang. Vol. 139. Proceedings of Machine Learning Research. PMIR, July 2021, pp. 9558-9568.
[Soh+15]
Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli. "Deep unsuper- vised learning using nonequilibrium thermodynamics" In: Proceedings of the 32nd International Conference on Machine Learning. Ed. by F. Bach and D. Blei. Vol. 37. Proceedings of Machine Learning Research. Lille, France: PMLR, July 2015, pp. 2256- 2265.
[Son+21a]
Y. Song, C. Durkan, I. Murray, and S. Ermon. "Maximum likelihood training of score- based diffusion models". In: Advances Neural Information Processing Systems. Ed. by M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan. Vol. 34. Curran Associates, Inc., 2021, pp. 1415-1428.
[Son+21b] Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole. "Score- based generative modeling through stochastic differential equations". In: International Conference on Learning Representations. 2021.
[Son+22]
Y. Song. L. Shen, L. Xing, and S. Ermon. "Solving inverse problems in medical imaging with score-based generative models". In: International Conference on Learning Representations. 2022.
[TP18]
M. K. Titsias and O. Papaspiliopoulos. " "Auxiliary gradient- based sampling algorithms".
In: J. R. Stat. Soc. Ser. B. Stat. Methodol. 80.4 (2018), pp. 749-767.
[Vinl1]
P. Vincent. "A connection between score matching and denoising autoencoders". In: Neural Comput. 23.7 (201 I), pp. 1661-1674.
[VKK21]
A. Vahdat, K. Kreis, and J. Kautz. "Score-based generative modeling in latent space". In: Advances in Neural Information Processing Systems. Ed. by M. Ranzato, A. Beygelz- imer, Dauphin, Liang, and J. Vaughan. Vol. 34. Curran Associates, Inc., 2021, pp. 11287-11302.
[WHZ23] Z. Wang. J. J. Hunt, and M. Zhou. "Diffusion policies expressive policy class for offline reinforcement learning". In: The Eleventh International Conference on Learning Representations. 2023.
[WY22]
A. Wibisono and K. Yang. "Convergence in KL divergence the inexact Langevin algorithm with application to score-based generative models". In: arXiv preprint 2.11.01512 (2022).
[ZC23]
Q Zhang and Y. Chen. "Fast sampling of diffusion models with exponential integrator".
In: The Eleventh International Conference Learning Representations. 2023.
12

---

A Notation and overview
In this section, we collect together the notation used throughout the proofs and provide road map for the end-to-end analysis in $E.
Throughout the analysis, Assumptions 1-4 are in full force.
We will reserve q for the law of the reverse process (and denote the forward process by q when needed). In SE, the law of the algorithm is denoted by p.
We the following Markov kernels:
1. ODE is the output of running the ODE for time h, starting (reverse) time t.
2. PLD (resp. PULD) is the output of running the continuous-ting overdamped (resp. under- damped) Langevin diffusion for time h. this notation, we have suppressed mention of the stationary distributions of the diffusion, which will be provided by context.
3. Po and PLMc (resp. PULMC) are the corresponding processes once discretized and using the estimated score.
For the ODE, steps, the kernel for the probability flow ODE depends on time (as opposed to the kernels for the diffusions, which are constant within any epoch of corrector steps); moreover, for our analysis in $E, we also need to take time-varying step sizes for the predictor steps. We will omit the dependencies on and h when clear from context. When P = PODE or PODE, we use pt.Ai....,A to denote pt.h pt
more precise with the notation because within a single epoch of predictor
pt t-y-----hhhhhh (we compose kernels on the right).
We refer to $4 for a high-level description of the proof strategy. We begin in $B with our improved score perturbation lemma (Corollary 1); this is the only section of the analysis which is indexed by forward time (instead of reverse time). In Lemma in &C, we establish our main result for the predictor steps, which combines together standard ODE discretization analysis with the score perturbation lemma of $B. Since Corollary 1 degrades near the end of the reverse process (or equivalently, near the start of the forward process, when the regularization has not yet kicked in), our analysis requires geometrically decreasing step size schedule, which leads to the two-stage Algorithms and 2.
In $D, we prove our main regularization results for the overdamped corrector (Theorem 4) and the underdamped corrector (Theorem 5). Finally, put together the various constituent results in the end-to-end analysis in SE.
B Score perturbation
In this section, we prove score perturbation lemma which refines that of [LLT22]. This improved lemma is necessary in order to obtain O(vd) dependence for the probability flow ODE.
Lemma 1 (Score perturbation). Suppose P: = * NN0, tl) and xo Po. d = - V (mpr(
Suppose that ||V In A )vo(=))lop < for all x. Then
V I'd I'd
1 as otherwise, noting that Pt = Pt- st. N (0, I), we may replace Po with Pt- J. and with 1. Suppose po (2) = e V(x), Let Po. denote the joint distribution of (Xo,Xy where X, Xo + v Z with Z A00 I) independent of Xo. and let Poje(- 1T) denote the conditional distribution of X, given X, = Iz. We first note that since
Proof. Without loss of generality, we may assume t S 27,
27.
In Inpe(y) (0)))=in)) In (xp((V(x))
1
1ly xx12) dx,
21
we have the following calculations:
V Vlnp(()) E EPote(la) .) -x --Epast-y) (VV), (VV)
13

---

(mp((() Cov Cov (lp) (VV) - (Po)) (V²V). (V2))
Using 3. V (m))) we calculate
0, V (n
V (mpa (imp((t)))pp((rrr)
2
We bound each term above separately. For the first quick calculation shows that 0
V In (v
- -ov -ooee Pojet v)
11v--11
VV) is finite a.s.: by Cauchy-Schwarz, it suffices to show Po Ill -1
2x2
and Po (-19) |II V are finite for all y, and this follows because for S 2z the measure Poje(. y)
is strongly log-concave and VV can be bounded by quadratic. Because VV is L-Lipschitz,
||[0 V Inpe()))l 21 [I[a, Pou(-l
(VV))l 11
1
lim
E [Par [V EE, Pl)))l [V]] y=
At-10 At
L lim inf
(Po xx), xx)), Pajel-1 xx))
(10)
A0
(At)
Now Paje-- (1) has density Poje(2: [z] 1) po( بلرياااا
so if 2 Inpollop S L and S 2I then
Poje is 27 -stoongly log-concave. By Talagrand's transport cost inequality,
W (Pooot+a æt), Po 21)) S 41 KL (L xx) Poul wx)
Plugging this back in (10) and using Fatou's lemma and the chain rule for KL,
11 s I lim inf At-+0
4t (L (at)) || Poje(- 21))
(At)²
1, lim inf A1-0
41 EL (Pojr+A) (x)) || Poje( xx))
(At)²
2
S L lim inf A1-0
4t KL Pa..)
(1I)
(Ar)2
Now
KL(Po.+A:
Po.s) ExS
KL P A:jo 1x), Prio(- [)) KL(W(O, At) || N(0,
d
t +
At
++ At
1) d , + +0 (
In
2
Plugging into (11) gives
B[ll pn 11 12dd
(12)
For the second term, by assumption we have || In pr lop I L. Then, since x, ~ Pt.
E v (x;)) V (n < L E.
< Ltd
(13)
using the fact E V In [ integration by parts. From (9), (12), and (13), and the elementary inequality (a, b) s ||a]| + ||b|2 we get
< Ld for any measure such that In is L-smooth, which follows from
E
B(] [P] B Vinp(()))1
< (T.a 2
The above result holds for the dynamics é = - V (x,) for which (pt) follows the heat flow; this corresponds to the variance-exploding SGM. In this paper, since we wish to consider the SGM based on the variance-conservingg Orstein-UUllenbek (OU) process, we can apply the following reparameterization lemma.
14

---

Lemma 2 (Reparameterization) Suppose that (21) satisfies the probability flow ODE Brown-
ian motion starting poi that letting Pt po (0, tf), we have 2o po, - V In (e(e). Then, if we set
Yt x I -1:
then (20 satisfies the probability flow ODE for the OU process starting at po; that is, letting qt"
be the density of the OU process at time t. we have yo ~ Po 90 = -t V In qi (v.).
Proof. By direct calculation, one can check that for any E Rd it holds that gv)(v)) x p 1 (e" y) The claim follows from the chain rule.
Lemma 3 (Score perturbation for QU). Suppose qr" is the density of the OU process at time I, started at yo, and yo %0¹, Vt- Vv- oi" (yt). Suppose for all and all x that [| [ In of (x)llop S I, where L 2 1. Then,
EllVVing ( (2d
Proof. Using the relationship (r())) x Past p (E'y),
V In 2 (y) e' V In p2 1 (t'y);
V. ln e' V In 21 (x
0,V (a 26
=A
If | In llop
L, then 2 Impe lop Se-21. By Lemma
Ellla (npa((=)) 189 e L (e 22
2
Hence
E < L'd
Next,
E[A3] < 2d B V - 12] S c2 Ld S Ld.
The result follows.
Finally, we use Lemma to derive bound on how much the score changes along the trajectory of the probability flow ODE. Corollary 1. Consider the setting of Lemma 3, and suppose 0 < <
1. sf 2 2 1/L, then
E Vigg V (x.)11 x d'
2. 1f < 8 stt then
E V[[Ving (x.) - V (x,)l] x L2dh2
Proof. By Lemma 3,
V In (z+) ( =E[|] =Elll L an v In (x du 1
S (t 5) /. Bllla, v In (Iw))
Sh f. I 1ax I., ) )dd.
du.
In the first case, this is bounded by O( In the second case, this is bounded by OLL2dh dh I 1 du) 2 In(t/s)) = OLL2dh2/t).
15

---

C
Predictor step
Next, we need an ODE discretization analysis.
Lemma 4. Suppose the score function satisfies Assumption 2. Assume that L 1, h S 1/L, and
T (to h) z I I- Then
W2 ODE 4 ODE) S 1 (T.12 (T-10)
+ hE
Proof. We have the ODEs
å = 2, V (
a. 8, Stg (Tro))
for to S15 to + h, with 2t. Tto ~ q, th ~ qODE and Tooth ~ yPODE. Then,
0e||zz - Tz11² = 2 (I/z - Tt, #1- - tt)
2 (1 -2,12 + (x+- 24, V (ln)(())) 8to (2t,)))
- (2 + 7) || ã. 11? [[ - 31o (2r0)l )|?
By Grönwall's inequality, noting that h = 0(1,
Elll - [eo+h113] exp((2 + 1 11)
to
h BBll lnge(s)) - sto (Tro (T
1oth
3 h
B|| Ing:(()) - sta (tt
(14)
We split up the error term
V gexe)
(12 x V (xx)) V In gr (ar.)) )l + V In (Its) sto (f2
By Corollary the expectation of the first term bounded by
V In (2x) - V gt (zt ) r. (LV T to
The second term is bounded in expectation by = Plugging back into (14) gives
Ell T + 11 h?? a. (L
T to +
The Wasserstein distance is bounded by the square root of this quantity, and the lemma follows.
Lemma 4 suggests that focusing the dependence on d, we will be able to take h = 1/2 (we need keep one factor of h in the bound, we need sum up the bound over 1/h iterations).
Our improved score perturbation lemma is necessary to obtain this dt/2 dependence. The original score perturbation lemma [LLT222 Lemma C.11-12] combined with space discretization bound gives bound of
Remark 2.
V In (xx) - v
S L
in place of Corollary 1. Note this is a 2 -Hölder continuity bound rather than a Lipschitz bound. The bound in Lemma 4 then becomes
W2(gPta
ODE: q (to.h) S /2 + hesc
and we would only be able to take = d-1, We also note that our bound has an extra factor of ma (T to) 1/23, we do not know if this extra factor necessary.
We now iterate Lemma 4 to obtain the following result. Note that we now need to also assume that the score estimate is L-Lipschitz.
16

---

Lemma's 5. Suppose that both Assumptions 2 and 3 hold. Let hi....,hy > be sequence such that letting tN h1 hy, we have tN I 1/ Let Bmax max SnSN hng
1. If (to + +NN) 2 L,L, then Wo hto...........
.PPODE
Pto.h S 1,3/2 hmaxt + EsclN S /2 mmax
Esc
2. IfT - to S 1/L and hnt1 S I-lg-tu for each then
We(gPoook ...... , PPDDE
ht..hu.... .N. S 12 mmax + ESctN S 122 /
Esc
L
Proof. We abbreviate ODE pla.h by and ODE
Pta.hi.....h AN
ODE
Using the triangle inequality,
W2(1Pobe PODE) W2(q ODE: @ P
1 PODE) W2
ODE PODE, q PobEE
122 max L 1/2 (T to (N)
11/2 112) + hNEse)
+ exx(OO(Lhx) Wa 9 ODE
where the bound on the first term is by Lemma By induction,
N
W2 ODE P
12 L 1/, to tn) 1123 + knEse)
x exp(OO (ha+1 +.... hN))).
By assumption, hn+11 + + hN S IN S 1/L. In the first case, we get
W2(gPote qPobE S 1//22 Amaxty + EsctN
In the second case we get
hn + Excty S 222 EsctN W2 P ÔDE) S Ld Tyaax TT to 1/2
1/221/2
by interpreting the summation as Riemann sum, and noting that the condition hn+1 S T T-to-to implies that this a constant-factor approximation of the integral Jr- by s//2 dt S vT tg-
1
Choice of step sizes. In the first case, we can take all the step sizes to be equal, but the second case, may need take decreasing step sizes. Given target time T to IN 5, by taking hy = Amax and then
T to tn-
hn = mink& 8, Imax,
we can reach the target time
= 0 Lhhmax + In Amax
steps.
D Corrector step
In $D.1 (resp. $D.2), we will show that if 9 are close in Wasserstein distance, then running the corrector step based on the overdamped (resp. underdamped) Langevin diffusion starting from p and from y for some amount of time results in distributions which are close in total variation distance. In the end-to-end analysis $E, we combine this "total variation to Wasserstein" regularization with the Wasserstein discretization analysis of the predictor step in $C in order to establish our final results.
17

---

D.1 Corrector via overdamped Langevin
We will take the potential and score estimate defining the Markov kernels PLD and PLMC from $2.3 to U and & respectively. Recall that these correspond respectively to running the overdamped Langevin diffusion with stationary distribution exp( and running the discretized diffusion with score estimate 5, both for time h.
pPi The main result of this section is show that p LMC and & are close in total variation p and g
close in Wasserstein.
Theorem (Overdamped corrector). For any Teor == NI 1//4
TV(pPIMc:9) 9) & W2(p.9)/ / Esc Teorr L/chTcor.
In particular, for Teom = 1/I,,
TV(pPLMc:9) 9) S VLW2(p.9) se/vL+ LLdh.
We will bound TV(pPL q) and TV LMC pP()) separately, For the former, we use the following short-time regularization result:
Lemma 6 ([BGL01, Lemma 4.2]). Tf S $1/L, then
TV(pP 1) S KL(pPD ll a) S W2(p,g)/ g)/ /
Proof. The first inequality is Pinsker's inequality. The second inequality is a consequence of [BGL01,
Lemma 4.2], which gives a bound of (L(pPLt || q) S L (1 + 1e - 1)) W q). The claim then follows from simplifying by using Teor S L/L.
For the latter term, we introduce notation for two stochastic processes.
dæf V (z)) dt + v2dB,
26 9,
dæ, = VU (xx) dt + v2dB,,
20 ~ p.
Note that for any integer k 2 0,
Thh ~ P Tkh ~ PPL.
Observe that marginally, q for any k 2 0 because is the stationary distribution of the Langevin diffusion. The three processes are coupled by using the same Brownian motion and by coupling Tu = 2o and z ~ 9 optimally.
LD. Before we proceed to bound TV(pP HobpPPi. P.M)). we need the following simple lemma.
Lemma 7, If S T/L,, then
E[[|2 2 $ W2
for all 0 <t S Teoer-
Proof. By Itō's formula,
d([a= =0ll²) - (z, x2, VU(I.) (U(2?)) I 2L || 2f11
By Grönwall's inequality.
|| - 2 < e 2h |00 2
so that if we couple the two processes by coupling zo and 2 optimally, we conclude that
E|||2 2011 < 2L1 Ell|zo = 2Ll ( 4) S (2.
recalling that t < Toor S 1/T. by hypothesis.
It remains to bound TV LMC, pP.)
18

---

Lemma 8. corr S 1/L, then
TV(pPLMc: LMC: pP())= 2 KKL(PPD ll 1 & TV W2(p. 9) + Exc Teom + I di
Proof. As and are driven by the same Brownian motion, by Girsanov's theorem and the data processing inequality we have
N
(k+1))
KL(PPL PPIM)
B(I(((aA)) (U(x)))
k=0
We can decompose the integrand as follows:
[l]ls(z(n) - VU (U(==)))" $ (B(l)))))@___((aaaaaaaa [[(ls(mm)) s(aRn)) + - -U
+ [[ - + - (U(xa))
L B 22a [1 - L - = 11 L E|| xz -1.
2 L (2 g) + + + LL Elll= - 201
(15)
where we used Lemma 7 bound E| | zull" 2l remains to bound E[[
2. Note that
E1 =] E 11 kh
vU(x)) V2 - Bani S l (IIVU(=)))
dh where in the last step we used that B|ll VU S Ld. Substituting this into (15), we obtain
Ldhi + dh S dh,
KL(PPÉ 1PPMc) S I W2 (p. 9) 2 Tear + L2'hTToor
The claimed bound on TV PN LMc) follows by Pinsker's inequality.
Proof of Theorem 4. This is immediate from Lemma and Lemma 8, recalling that Teor 2 1/LL that the bound in Lemma dominates the W2(p. q) term in Lemma 8.
D.2 Corrector via underdamped Langevin Throughout, we set the friction parameter to
VL.
We will take the potential and score estimate defining the Markov kernels PULD and PULMC from $2.3 to be U and respectively. Recall that these correspond respectively to running the underdamped Langevin diffusion with stationary distribution and running the discretized diffusion with score estimate s, both for time h.
Given probability measures p and g, we write = 2 "dd and == q @ % where " is the standard Gaussian measure in Rd
The main result of this section is to show that p PP and are close in total variation if p and close in Wasserstein. Compared ID.1, the discretization error for the underdamped Langevin diffusion is smaller.
Theorem's (Underdamped corrector). For Teorr S 1/VL.
TV(p ULMC, 9) S W2(p.g)
+ 1 1/2/
/1/473/22
1/4
con
In particular, if we take Toor x I/VI, then
TV(pPM PULM q) S VIW2(p.q) q) + e<c/VVL + VLdh.
'Although the validity of Girsanov's 's theorem typically requires Novikov's condition to be satisfied, this can be avoided via approximation argument as in [Che+23a].
19

---

We will bound TV(pPULD q) and TV(pPulMc short-time regularization result [GW12]:
ULMC PLULD) separately. For the former, we use the Lemma 9, Ton S 1/VL, then
W2(p.9)
TV(pPuLD 9) & VKL(pPuO ll
Proof. This is consequence of [GW12, Corollary 4.7 (I)). The condition check therein their Eq. (3.6), which in our setting is satisfied by the constants Ki = L and K2 = y. The Corollary then states that for the cost function
Toer ((2, v), (2',,
inf (e())
t
{
6 + L 12
3y 2t
|| 2'1l (
4
4Lt
27 -1) 11e o''l
2y
we have KL(pPuLD
ULD () S W Year (p 8 Na, y @ 7a). For v = v' and T Toor X 1/VL, note that
1
Te ((z, (), (2), x
|| 2/12
L1/273
cor
so the claim follows by Pinsker's inequality.
Next, we define the following processes: dæp of dt, dæ = 02 dt,
def = yug dt (U() dt + 22
(2 28) ~ q
de, = -y, dt - (2) 1 +
+ 22
(z0: U0) p.
follows that for any integer k: 2 0,
(Ekh, Ukk) PPOLD- We couple these processes by using the same Brownian motion and coupling na and p @ na optimally (in particular, vp- = r))
(zh ( q PoLLD = q,
Before we proceed to bound TV (ULP p PNN ULMC). we start with the following lemma.
Lemma 10. If S I/VI, then for all 0 < < Teom
Bi[l = $ (2
Proof. We have
(f. V-U(2 u2 =u) du) (4. 22)= Hi(2. 2
vU())))
and the operator H4 satisfies
li ol T.
Let = 2/7. For the vectors 6, = (21 + avr) (2] avt)) and n)
21 22, we have
(y- 2) la
(5,, mc) { Vla) 1 Ia
d(16,,12 + [|mel1²) (5,. nT)
1/2 (a7le - Ia)
I VT (1162112 11m)113).
By Grönwall's inequality,
|| + 11m1 s (VEat) (11 1|no113),
so if we couple the two processes by coupling zo and =Ú optimally and taking vo vg. we obtain
E||l - 2, [| E|| | +lmml < (vED Ell|o 2 +1 (VVTo (2 S (2(pp.)
recalling that t < Teor S 1 TT by hypothesis.
It remains to bound TV (LMCP pPND).
20

---

Lemma 11. Tf & 1/VL. then
TV(pPuLMC PN ULMC: pPUL)) S V (KL(PPLL |pP con W2(p, 4) + L 1-1/4/1/2 So
S 1//
cor Sec + 13/41112 2
cor
Proof. As (z, and (z", 00) are driven by the same Brownian motion, by Girsanov's 's theorem' and the data processing inequality have
(k+1)/
KL(pPULD p PLLMC) S
[[]ls(Zan)
VU (z
k= kh
We can decompose the integrand as follows:
((()) - VU(2z))1 x ((kk)
s1 -
+I VU(22)11 + VU (2.)
< L [[[| ZEN 1/ - - + L B([lal=Rn - = = L2
Blll =1 zu |1
2 L2 W 9) + + + = =1.131
(16)
where we applied Lemma 10.
remains bound F[[ = [ Note that
[ u. dol2] s f 11 ds S dh? kh
= = = E
kh
where in the last step we used the fact that Vi ~ Ya. Substituting this into (16), we conclude that
KL |l pPPLmc) $ T.3/2 W2 q) + 1.-1//2 + 1, 3/2 dh 2 Teror
The claimed bound on TV(pPüLD. Biu.pPPll PPPMMc) follows by Pinsker's inequality.
Proof of Theorem 5. This is immediate from Lemma 9 and Lemma 11, recalling that Teor Z 1/VL so that the bound Lemma 9 dominates the W2(p, q) term in Lemma 11.
Remark 3. In all other sections of this paper, abuse notation follows. Given distribution p on Rdd we write pPULMC to denote the projection onto the z-coordinate of PPolMe, i.e. we view PULMC as Markov kernel on Rd rather than on Id x Id (and similarly for PULD).
E End-to-end analysis
Lemma 12 (TV error after one round of predictor and corrector). Choose predictor step sizes hi,..., Junua as in Lemma with Trrd = h1 + +. ... NN S 1/L. That is, if - to T S 1/ L.L, then we ensure that hn+1 < T T-ta-h -.... ha for all and if to Z 1/L, then
take Jo.. (and
h hx- Let hpredd == maxignsN hn and abbreviate P(Nees) PODE similarly for PODE).
1. Consider running the overdamped Langevin corrector for time Teon 1/LL, step size hcomr (NNes))
and stationary distribution Qto ODE 9to + Tmna set Neorr = Teor /hcorr Then,
P.N
TV(pP(NNme)) P.Nace PLire 9to+Tmm)) & TV(p, + o (LVd (ode))+O(WWddddi
+ / Lddicor +
Esc
VT.
2. Consider running the underdamped Langevin corrector for time Teorr 1/VL, step size ficom and stationary distribution Qt, Po ODE 9to+Tonai set Ncor Tcor/hico. Then,
TV D(Npaa ((o))) PULMC: (otTTws) S TV(p, 9to) + O O (IVa + VLd heser + Esc
ODE
VL
Again, avoid checking Novikov's condition using the approximation argument of [Che+23a].
21

---

Proof. By the triangle inequality and the data- processsin inequality,
TV(p (( ODE
LMC Tost
TV(pPod ( ODE PLMe, Qt P ((Nmm)) 1.N
LMC + TV P(Nmes) P. T
ODE
ODE
TV(p, (to) + TV(1to NeN Ne +toots
For overdamped Langevin, applying Theorem 4,
Tg ODE
Pi ((Nans)) PLME Bo+Tpw) S WL (Nar))
4to+I + Ese/VL L + v Ldhcom (17)
ODE
For the Wasserstein term, Lemma yields
W2(40 ((N +moo+Toma) = W2(4o ((N ODE
((Naa) S Vid Apred + Esc ODE
Uto
T.
Combining these bounds yields the result for the overdamped corrector. For the underdamped corrector, we modify (17) by replacing the use of Theorem 4 with Theorem 5.
We also need the following lemma on the convergence of the OU process. Lemma 13. Let (gr²) ):20 denote the marginal law of the OU process started at 90 9.. Then, for all 2 1, holds that
TV(TT,7) (Vd mx)
Proof. This follows from [CLL23, Lemma C.4]. Alternatively, using the short-time regularization result of [BGLO1, Lemma 4.2] for time to and the Wasserstein contraction of the OU process,
W2 S exp(-((T -to) W2 (2
TV(97 S / /KL(TT rl)d) S
Vta
The result follows from W2(an.79) S W2(an, + W2 74) <m + Vd.
now prove our main theorems.
Proof of Theorems 2 and 3. For t [0, let law(2;). From Lemma 13,
TV(po, mo) = TV( 70)) S (vd m2) exp(-T))
We divide our analysis according to the two stages of the algorithm. In the first stage, after iterating Lemma 12 for No x LT steps,
TVppT- Nyess Qr Higeed -
S TV(po, 9o) + 0 L h hpred + Led he +
Esc
x No
VT
S (Vd + m2) exp(-pp (T) 2dd 1/2 hred / /2
L 1/2Tsc
where p = if we use the overdamped corrector and p 1 if we use the underdamped corrector. Applying the second part of Lemma 12 for the second stage of the algorithm, then conclude that
TV(PT=s. S (Vd m2) exp(- + L2Td /2 h1pee + 33 1/2// L 1/2TES
Finally, note that if take 8 = 7 (dvmg) then by [LLT23, Lemma 6.4), TV( 8, (T) triangle inequality thus finishes the proof.
2²
Remurk Alternatively, instead of taking geometrically decreasing step sizes and employing early stopping, we could split the algorithm into two stages: for time / < T hpred we take constant step size hpred, and for time > hpred we use a smaller constant step size as required if working with the original score perturbation lemma (see Remark 2).
22

---

F Numerical experiments
In this section, we provide preliminary numerical experiments to illustrate our theory. We implement DPUM on toy model that is not log-concave (mixture of Gaussians).
Setup. The target distribution is mixture of five Gaussians in dimension 5. On Figures I and 2, the red stars represent the means of the Gaussians and the red ellipses around the stars represent the variances of the Gaussians. We start by sampling 500 independent points (in blue) from standard Gaussian. Then, we run DPUM from the blue dots over 300 iterations and plot the two first coordinates of the dots at iterations O, 100, 200 and 300. This is low-dimensional toy example it does not illustrate our theory, rather we include it as a simple sanity check.
Parameters. We use closed form formula for the score along the forward process. In other words, the score estimation error is equal to zero. The step size of the predictor is 0.01 and the step size of the corrector is 0.001. The corrector consists in 3 steps of the underdamped Langevin algorithm. In the latter algorithm, we initialize the velocity as a centered Gaussian random variable with standard deviation 0.001 and set the parameter y to 0.01.
Observations. We observe the expected behavior: although the target distribution is highly non-log- concave, DPUM is able to provide samples from distribution that is close to the target distribution. In particular, the initial Gaussian distribution splits in clusters that will fit each component of the target mixture of Gaussians. Recall that we experiment without score error but with discretization error: our numerical results illustrate the common wisdom that score knowledge along the forward process can replace convexity assumptions. In particular, we observe that even isolated, low probability components of the Gaussian mixture, are recovered by DPUM
Itevation
100
-2
0.2
Iteration 200
Iteration 300
Figure 1: A realization of DPUM for mixture of Gaussians.
23

---

325
Iteration 200
Iteration 300
Figure 2: realization DPUM for another mixture of Gaussians.
24


Reviews:
[{"review_id": "kTVKPSS64k", "reviewer": "Reviewer_rLPm", "summary": "In this article the authors propose polynomial-time convergence guarantees for probability flow ODEs related to score based generative models. \nPrevious analyses on score based diffusion models have resorted to the use of SDEs and relied on properties of stochastic flows to alleviate error accumulation due to discretisation. Here the authors study the ODE counterparts of diffusion models.\nSince the deterministic dynamics are not contractive without log-concave assumptions on the data distribution, and thereby \ndiscretisation errors accumulate, the authors derive bounds for a modified process which requires interleaving deterministic integration steps (predictor) with stochastic (corrector) steps that smooths the reverse process, drawing inspiration from the purely stochastic framework of [4,9]. They propose two variants of the algorithm, one relying on overdamped Langevin dynamics with dimension dependence that scales as $\\mathcal{O}(d)$ ,and one with underdamped Langevin dynamics that scales more favourably as $\\mathcal{O}(\\sqrt{d})$and thus has improved dimension dependence compared to previous approaches.\n\nThe topic of the paper is interesting and relevant for the audience of  NeurIPS for understanding denoising diffusion probabilistic models, however I find that the article could have been more accessible for the broader audience of NeurIPS, and importantly, I would expect that the authors would provide numerical evidence for their proposed guarantees.", "questions": "- How does the proposed approach relate to the flow matching methods, i.e. [8]?\n\n- How does the method compare with concurrent approaches [7] , [9] and [10]?", "limitations": "- The authors do not provide numerical experiments to support their claims.\n\n- They do not provide comparisons with already proposed bounds on either stochastic or deterministic implementations of diffusion based generative models.\n\n- They do not discuss limitations of their approach.\n\n\n\n\n---\n**References:**\n\n\n[1] Chen, Sitan, et al. \"Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions.\" arXiv preprint arXiv:2209.11215 (2022).\n\n[2] Lee, Holden, Jianfeng Lu, and Yixin Tan. \"Convergence of score-based generative modeling for general data distributions.\" International Conference on Algorithmic Learning Theory. PMLR, 2023.\n\n[3] Maoutsa, D., Reich, S., & Opper, M. (2020). Interacting particle solutions of Fokker–Planck equations through gradient–log–density estimation. Entropy, 22(8), 802.\n\n[4] Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., & Poole, B. (2020). Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456.\n\n[5] Hermoso, A., Homar, V., & Yano, J. I. (2020). Exploring the limits of ensemble forecasting via solutions of the Liouville equation for realistic geophysical models. Atmospheric Research, 246, 105127. \n\n[6] Albergo, Michael S., and Eric Vanden-Eijnden. \"Building normalizing flows with stochastic interpolants.\" arXiv preprint arXiv:2209.15571 (2022).\n\n[7]  Li, Gen, et al. \"Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models.\" arXiv preprint arXiv:2306.09251 (2023).\n\n[8] Benton, Joe, George Deligiannidis, and Arnaud Doucet. \"Error Bounds for Flow Matching Methods.\" arXiv preprint arXiv:2305.16860 (2023).\n\n[9] Lee, Holden, Jianfeng Lu, and Yixin Tan. \"Convergence of score-based generative modeling for general data distributions.\" International Conference on Algorithmic Learning Theory. PMLR, 2023.\n\n[10] Albergo, Michael S., Nicholas M. Boffi, and Eric Vanden-Eijnden. \"Stochastic interpolants: A unifying framework for flows and diffusions.\" arXiv preprint arXiv:2303.08797 (2023).\n\n[9] Jain, Ajay, and Ben Poole. \"Journey to the BAOAB-limit: finding effective MCMC samplers for score-based models.\" NeurIPS 2022 Workshop on Score-Based Methods. 2022.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- the authors provide improved convergence guarantees compared to existing approaches.\n- they relax log-concavity assumptions existing in previous frameworks that are rather restrictive.", "weaknesses": "- The work is purely theoretical and the authors do not provide numerical evidence for their claims excluding a simple experiment in the supplement. I find it a bit odd that they provide a convergence guarantee and propose a scaling with system dimension, but nevertheless they don't explore the said scaling numerically for increasing system dimension. The numerical example they present in the appendix concerns only a single experiment of dimension $d=5$.\n\n- the main theorem of the paper is formulated considering only linear dynamics (Ornstein-Uhlenbeck process). However according to the introduction of the\n paper a reader gets the impression that the provided results are relevant for general dynamics. I would propose to introduce this clarification both in the abstract and the introduction of the \npaper, otherwise the statements may be considered misleading.\n\n\n- the derivation of the probability flow ODE in Eq. 3 is a bit odd, and happens to be correct here because the considered dynamics is conservative. The whole point of [3]  first introduced the\nformalism of ODE dynamics for diffusion that got later named prob. flow ODE by [4], was that there is no need for a stationary solution for the prob. flow ODE and no need to derive the dynamics wrt to the stationary solution. \nFor general systems one can derive the dynamics of the deterministic process by rewriting the Fokker-Planck equation in the form of a Liouville equation\nas\n\\begin{align} \n\\partial_t p_t(\\mathbf{x})& = - \\nabla \\cdot \\left( f(\\mathbf{x}) p_t(\\mathbf{x}) - \\frac{\\sigma^2}{2} \\nabla p_t(\\mathbf{x})  \\right)   \\\\\\\\\n&=- \\nabla \\cdot \\left[p_t(\\mathbf{x})  \\left(  f(\\mathbf{x})  - \\frac{\\sigma^2}{2}  \\nabla \\log p_t(\\mathbf{x})  \\right) \\right] \n\\end{align} \nFrom this formulation one can apply the divergence theorem and obtain the deterministic dynamics similar to [5]. The explanation used in the paper uses the Wasserstein gradient flow structure.\n\n- Poorly written and limited conclusion without discussing the limitations and possible outcomes of the provided guarantees.\n\nMinor:\n\n- The notation of the stationary distribution of the overdamped Langevin dynamics is rather unfortunate, especially considering that then it is used in the same sentences/equations with the parameter $\\gamma$ indicating the damping of the underdamped process.\nI recommend adapting the notation to avoid confusing the readers unnecessarily.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review.\n\n**They propose two variants of the algorithm, one relying on overdamped Langevin dynamics with dimension dependence that scales as $O(d)$, and one with underdamped Langevin dynamics that scales more favourably as $O(\\sqrt{d})$ and thus has improved dimension dependence compared to previous approaches.**\n\nTo be precise, we did not propose the overdamped version DPOM. As mentioned in the paper, DPOM was proposed **and experimented** in [Son+21a, Section 4.2].\n\n**However I find that the article could have been more accessible for the broader audience of NeurIPS**\n\nThanks for the feedback. We hope that the main message of our results, that you summarized in the beginning of your review, is accessible to the community.\n\nBesides, we agree that the theory of diffusion models is a difficult topic. We have tried to make the ideas of our proof accessible by writing an outline in Section 4. Once again, the literature on diffusion models is mainly applied, and we believe that this nicely complements the literature. \n\n\n**The work is purely theoretical and the authors do not provide numerical evidence for their claims excluding a simple experiment in the supplement. [...]**\n\nPlease refer to our general message for all reviewers.\n\nThe experiment we provided is purely illustrative, that’s why we chose to put it in the appendix, and we might remove them from the next version of the paper if it confuses the reader about the theoretical nature of our paper. \n\n**The main theorem of the paper is formulated considering only linear dynamics (Ornstein-Uhlenbeck process) [...]**\n\nThanks for the suggestion. We will apply the recommended change in our revision of the paper. Please consider this weakness fixed.\n\nTo be precise, we work with the Ornstein-Uhlenbeck (OU) process for many reasons: the analysis is involved enough already; our theoretical results are the first ones for this setting and therefore we aim to prove the simplest possible results rather than covering all possible extensions; and from our understanding, the OU setting is already interesting enough for practice. \n\n**The derivation of the probability flow ODE in Eq. 3 is a bit odd, and happens to be correct here because the considered dynamics is conservative [...]**\n\nThe Prob flow ODE is the name given in the ML community when they rediscovered this ODE in 2020. However, this ODE is actually an old topic, already considered in optimal transport, see [AGS08]. We preferred to stick to the original approach of [AGS08] for interpretability. The approach you propose is valid, but we do not think that the approach we use is a weakness of the paper.\n\nBesides, for us, the term \"conservative\" refers to dynamics that preserve the global energy. As a gradient flow, the Prob flow ODE \"maximizes\" the dissipation of energy, so how can it be conservative?\n\n**Poorly written and limited conclusion without discussing the limitations and possible outcomes of the provided guarantees.**\n\nWe will rewrite the conclusion and in particular add the following limitations:\n\n- Our theory only covers the ODE version of the Ornstein–Uhlenbeck process. We leave more general processes for future work.\n- The guarantees we obtain require to learn the score with $L^2$-accuracy $O(\\epsilon / \\sqrt{L})$, which is *a bit* more stringent than the requirement obtained for DDPM (SDE based diffusion model) in [CLL22, Che+23] (They require $O(\\epsilon)$).\n- No large scale experiments. To be clear, we agree that it is a limitation, but we disagree that it is necessary for publication in NeurIPS given our theoretical contribution: we obtain $O(\\sqrt{d})$ whereas all prior works, including DPOM, obtain at least $O(d)$.\n\n**MINOR**: Thanks for the suggestion, please consider it fixed.\n\n**Flow matching [8].** This paper is very interesting and relevant to ours. We will add it to our literature review. Note however that **it appeared on arXiv after NeurIPS deadline.** We can compare our paper to [8] along several axes, we choose to mention some of them here:\n\n1. [8] is more general than our work and therefore the bounds obtained are less precise than ours in the case of the Prob Flow ODE.\n\nIn particular: \n\n2. They cover the Prob flow ODE (without corrector).\n3. They do not consider discretization in time. More precisely, the discretization error is hidden by their Assumption 1.\n4. Their result scales exponentially in the parameter $\\lambda$ which could depend on the dimension.\n\nTL;DR: [8] is more general than us but less precise in the particular case of the Prob Flow ODE.\n\n**Comparison to [7]**. These are interesting results. Again, **this paper appeared online after NeurIPS deadline**. Using a modified ODE they managed to obtain an improved dependence on the accuracy ($O(1/\\sqrt{\\epsilon})$ instead of $O(1/\\epsilon)$ for us). \nHowever a major concern we have is that they assume zero score estimation error (see their Assumption 1), whereas we allow for a score estimation error.\n\n**Comparison to [9]**. Already done. See end of Page 9 (starting line 220)\n\n**Comparison to [10]**. This is also a very interesting paper and we will add it to our literature review. It is a dynamical systems paper (rather than a convergence paper like ours) that obtains a number of ODEs and SDEs for generative modeling using a general framework. \n\n\n**They do not provide comparisons with already proposed bounds on either stochastic or deterministic implementations of diffusion based generative models.**\n\nComparison already done, **with the references that were available before NeurIPS deadline**. Please see the paragraph between Th2 and Th3. \n\n\n\n**We kindly ask you to evaluate our paper with the lens of a theoretician, i.e., in light of our actual contributions (towards theoretical understanding of diffusion models). If you believe that our theoretical contribution is enough for publication please consider raising your score.**\n"}, {"review_id": "En2Wl5aEhm", "reviewer": "Reviewer_tQnV", "summary": "The current study offers a polynomial-time total variation convergence guarantee for score-based generative modeling, given that the generative process is a probabilistic Ordinary Differential Equation (ODE). This differs from previous work, which typically involves a reverse Stochastic Differential Equation (SDE).  To the best of my knowledge, this is the first paper to present such results for an ODE-implemented score-based generative model targeting a general distribution without assuming log-concavity. The proof technique includes analyzing the discretization error of both the ODE and SDE, and employs the Score Perturbation Lemma to limit the error introduced by using estimated score functions.\n\nIt's important to note that the convergence guarantee is provided for a modified version of the ODE-implemented score-based generative model. The authors have added an additional stochastic correction step to the deterministic dynamics, which is an unconventional approach.", "questions": "* Step 5 for Alg 1 and 2: Can authors provide some intuition on why geometric decreasing stepsize is needed for the prediction at the end given that correction step is used eventually? (I understand from the proof that when $t>1/L$, decreasing step size is required to control the ODE discretization error + approximated score error, but cannot form a practical intuition on this.)\n\n* In practice, which one of  DPOM and DPUM is preferred? Or how does one choose the algorithm for practical applications? \n\n* Is it possible to get rid of the correction step for the convergence if the ODE discretization error is reduce by using more sphisticated numerical integrator (e.g., high order sympletic integrator)?  Based on my superfluous understanding of the proof, the answer is probably NO since the key of the corrector is to obtain TV bounds based on Wasserstein bounds, intead of \"correcting\" the introduced error during the ODE simulation. This leads to my next question.\n\n* If intead of TV distance, all we care is just wasserstein distance, can we get rid of the correction step? Or is the correction step beneficial for a faster convergence? \n\n", "limitations": "The author did note limitations or boundaries of the adopted techniques through out the proof (e.g., line 565 in Appendix C), and raised practical questions base on the theoretical framework.  ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The results provided in the work is novel and important in my perspective. As mentioned in the summary, this is the first convergence guarantee for an ODE-based, score-based generative model for general target distributions that I am aware of (this could, of course, be due to my limited familiarity with the relevant literature). While some may contend that the additional stochastic correction step diminishes the impact of the work (given that the primary challenge of the proof is that the ODE transformation is purely deterministic, making Total Variation/Kullback-Leibler control nearly impossible), the theoretical framework employed remains significantly distinct from its SDE counterparts.\n\nThe clarity of the writing and the structure of the proof are commendable. Despite the complexity of the paper, the proof is not difficult to follow, largely owing to a comprehensive preliminary introduction to the proof techniques. I particularly value the fact that the authors dedicated a significant portion of the text to discussing the limitations of some existing proof concepts, and made comparisons with similar intermediate results from the literature. This approach further underscores the contributions of this work.\n\n", "weaknesses": "The inclusion of an additional stochastic corrector in the generative process is somewhat unsatisfying. To the best of my knowledge regarding score-based generative modeling via ODE, this correction step is not typically included in practice. One aspect that I believe is not clearly addressed in the current results is the comparison between the corrected and uncorrected generative processes. Ideally, there would be a result showing that the corrected process converges to the target faster.\nWhile it is mentioned in the paper that we cannot expect such a comparison in terms of Total Variation (TV) or Kullback-Leibler (KL) divergence - as without the stochastic correction, the TV/KL bound would be vacuous - could we not show such a comparison in terms of weak distance or even Wasserstein distance?\n(I've also raised some questions regarding the corrector in the Questions section.)\n\nAnother minor shortcoming pertains to the toy numerical experiments presented in the study. It would have been more desirable if the authors had evaluated Algorithms 1 & 2 on actual image generation tasks and compared the performance of the corrected and uncorrected versions in these scenarios. While I admit it might seem somewhat unfair to expect this from a theory-oriented paper, such empirical evidence would undoubtedly render the study more comprehensive and impactful.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the generous review. \n\n**The inclusion of an additional stochastic corrector in the generative process is somewhat unsatisfying [...]**\n\nRegarding the use of the corrector, we are not the first ones to propose this; in fact, it was shown to achieve superior performances in practice in [Son+21a, Section 4.2] and several subsequent works. Nevertheless, we acknowledge that we could not obtain polynomial-time guarantees without this corrector step, and it is an important open question to determine whether the corrector step is necessary. Note however that in Wasserstein distance, we can easily obtain guarantees for both the corrected and uncorrected algorithms which scale exponentially in the problem parameters (but for this the corrector is useless).\n\n\n**Another minor shortcoming pertains to the toy numerical experiments presented in the study. It would have been more desirable if the authors had evaluated Algorithms 1 & 2 on actual image generation tasks and compared the performance of the corrected and uncorrected versions in these scenarios. While I admit it might seem somewhat unfair to expect this from a theory-oriented paper, such empirical evidence would undoubtedly render the study more comprehensive and impactful.**\n\nThank you for acknowledging that it might seem somewhat unfair to expect this from a theory-oriented paper (see also our answer to all reviewers). We agree that such experiments would make our paper even stronger, but we prefer to let this for future work.\n\n**Step 5 for Alg 1 and 2: Can authors provide some intuition on why geometric decreasing stepsize is needed for the prediction at the end given that correction step is used eventually?**\n\nIn our analysis, we use geometrically decreasing step sizes because our improved score perturbation lemma degrades as time approaches 0. Alternatively, we could use a two-stage step size schedule (see Remark 4) in the Appendix. Intuitively, this suggests that the discretization needs to be more accurate near time 0 due to the poor smoothness of the score function; we are not sure if it is necessary though. We will add comments explaining this to our proof overview.\n\n\n**In practice, which one of DPOM and DPUM is preferred? Or how does one choose the algorithm for practical applications?**\n\nOur theoretical results suggest that DPUM is more effective especially in high dimension. But in reality, it also depends on the score estimation error, and more extensive experiments are needed to properly answer this question. At least, we did not see a difference between DPUM and DPOM on our low dimensional toy experiments (and we didn't expect to see a difference in low dimension). The Python code is provided in the Supplementary if you want to try.\n\n\n**Is it possible to get rid of the correction step for the convergence if the ODE discretization error is reduced by using more sophisticated numerical integrator (e.g., high order symplectic integrator)?**\n\nThis is an interesting idea that deserves to be explored. For the moment, we do not know if it is possible. One issue we see is that higher-order integrators usually require higher-order smoothness assumptions to be effective, which we want to avoid. \n\n**Based on my superfluous understanding of the proof, the answer is probably NO since the key of the corrector is to obtain TV bounds based on Wasserstein bounds, instead of \"correcting\" the introduced error during the ODE simulation. This leads to my next question.**\n\nTo be more precise, the corrector allows us to use the TV distance for which the error accumulates *linearly* over the number of iterations. In contrast, due to the lack of contractivity of the dynamics, the Wasserstein error tends to compound *exponentially* over the iterations. Using higher-order integrators to resolve this issue seems challenging. \n\n**If instead of TV distance, all we care is just wasserstein distance, can we get rid of the correction step? Or is the correction step beneficial for a faster convergence?**\n\nAs we just said, the exponential accumulation of the error in Wasserstein distance is a problem and we are currently unable to get polynomial-time guarantees in Wasserstein distance (with or without corrector). In summary, the corrector is necessary for our proof to give polynomial, non-exponential, bounds.\n\n\n\nHowever, there is a restricted setting in which we can give polynomial bounds in Wasserstein distance and without corrector. For this to work, we need to use the early stopping technique used in [Che+23] and to assume the following:\n\n- Zero score estimation error\n- Zero discretization error.\n\nIn this setting, the \"algorithm\" outputs the distribution obtained by running the Prob Flow ODE **exactly**, but from the standard Gaussian (instead of the end distribution of the forward process). We are able to show polynomial bounds for this \"algorithm\" in terms of the Wasserstein distance to the target distribution. But this is a restricted setting.\n\n-------------------------------------------------------------\n\nDear Reviewer,\n\nGiven your review, you are obviously among the reviewers who understood our work the best. However, you rated your confidence level very low compared to the other reviewers. We kindly ask you to raise your confidence level, by comparison to the others. And we would be happy if you could raise your score if you are satisfied with our answers.\n\n\n\n\n[Son+21a]: Y. Song, C. Durkan, I. Murray, and S. Ermon. “Maximum likelihood training of score based diffusion models”, NeurIPS 2021\n\n[Che+23]: S. Chen, S. Chewi, J. Li, Y. Li, A. Salim, and A. R. Zhang. “Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions”, ICLR 2023"}, {"review_id": "lCCr2RZKV3", "reviewer": "Reviewer_Q98a", "summary": "The authors proposed the convergence guarantees for the probability flow ODE implementation. Through the use of a specially chosen corrector step based on the underdamped Langevin diffusion, a better dimension dependence of $O(\\sqrt{d})$ than DDPM $O(d)$ is achieved.", "questions": "Q1. Do you know any popular real-world examples that probability-flow ODE works well in ultra-high dimensions in practice?\n\nQ2. Growall inequality does suffer from the exponential blowup. \nQ2.a) The authors propose to use the geometric contraction of the corrector (diffusion) step to control the exponential blowup. Is that right? \nQ2.b) Does it mean we can do lots of ODE steps but with only a few diffusion steps, the exponential blowup is still controlled in terms of complexity (ignore the constant) due to the contraction (closer to 1, e.g. alpha=0.999999999 also works, although the error / (1-alpha) is large)?\nQ2.c) Or do you need to maintain at least some amount of diffusion steps to make sure the bound hold?\n\nMinor: a relative work is missing and a short comment on this work would be appreciated: Provably Convergent Schrodinger Bridge with Applications to Probabilistic Time Series Imputation. ICML'23.", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. the theoretical comparison between probability flow ODE and DDPM is less studied in the community. In this sense, analyzing the advantage of the ODE-based method brings new insight to the community. \n\n2. solid and clean derivations.", "weaknesses": "1. the term of fast looks a bit confusing to me. It is fast in inference or training? they have different meanings. As provided in the ranking: https://paperswithcode.com/sota/image-generation-on-cifar-10, **flow-based methods seem to perform quite mediocre in standard datasets**. So at least the claim of fast flow-ODE contradicts the fact of fast training in practice. Clarification is suggested.\n\n2. Flow-based methods are known to work well in **low dimensions** and I am even suspecting it suffers from the curse of dimensionality. As such. I appreciate the authors' solid math techniques, but I personally believe that the advantage of the well-known smaller discretization error $O(\\sqrt{d})$ v.s. $O(d)$ becomes **less interesting if it mainly adapts to low-dimensional problems** (see Q1 below). the authors can correct me if I am wrong.\n\n3. The authors should point out the **limitations of probability-flow ODE methods** compared to DDPM so as not to confuse readers.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review.\n\n**The term of fast looks a bit confusing to me. It is fast in inference or training?**\n\nOur theory shows that sampling is fast, therefore the term fast refers to the inference time, not the training time. We will clarify this point in the introduction.\n\n**Flow-based methods are known to work well in low dimensions and I am even suspecting it suffers from the curse of dimensionality. As such, I appreciate the authors' solid math techniques, but I personally believe that the advantage of the well-known smaller discretization error becomes less interesting if it mainly adapts to low-dimensional problems (see Q1 below). The authors can correct me if I am wrong.**\n\nOur analysis separates the study of score estimation from the sampling (i.e., inference) complexity, and we only study the latter. Specifically, we show that **if score estimation is possible with low error, then the sampling complexity does NOT suffer from the curse of dimensionality.** \n\nThat being said, there may be situations in which score estimation incurs the curse of dimensionality (in general this is true). However, there may be other situations in which score estimation does not incur the curse. For example, this may be the case when the data has some intrinsic low-dimensional structure and the neural network training is able to adapt to it. **Regardless of what situation we are in, our results hold independently.** \n\nFinally, slow training in high dimension is a *practical* observation, whereas our paper *mathematically proves* faster inference. Hence, we disagree with your assessment that our results are only interesting in low dimensions. It depends on the context.\n\n**The authors should point out the limitations of probability-flow ODE methods compared to DDPM so as not to confuse readers.**\n\nThanks for the suggestion. We will mention this limitation (curse of dimensionality in training phase observed in practice) in our paper.\n\n\n**Q1. Do you know any popular real-world examples that probability-flow ODE works well in ultra-high dimensions in practice?**\n\nFor ultra-high dimension, like generating videos, we do not know and we believe it is still an open problem.\n\n\n**Q2. Growall inequality does suffer from the exponential blowup.**\n\n**Q2.a) The authors propose to use the geometric contraction of the corrector (diffusion) step to control the exponential blowup. Is that right?**\n\nTo clarify, the corrector does NOT have a geometric contraction; in fact, the corrector step also suffers from an exponential blowup in the Wasserstein distance. Technically, the role of the corrector step is to *add stochasticity*, which allows us to transfer Wasserstein error to TV error which accumulates linearly, rather than exponentially over iterations. Intuitively, with stochasticity, we can argue that the probability that the reverse diffusion and the algorithm diverge is very small; but without any stochasticity, the analysis must be “worst-case” and hence leads to poor bounds.\n\n\n**Q2.b) Does it mean we can do lots of ODE steps but with only a few diffusion steps, the exponential blowup is still controlled in terms of complexity (ignore the constant) due to the contraction (closer to 1, e.g. alpha=0.999999999 also works, although the error / (1-alpha) is large)?**\n\nThis is answered by the previous point, namely that even with the corrector step, there is no contraction.\n\n**Q2.c)  Or do you need to maintain at least some amount of diffusion steps to make sure the bound hold?**\n\nOur bounds do rely on taking enough diffusion steps to ensure that there is enough added stochasticity.\n\n\n**MINOR**: Thank you for pointing out this work, we will add it to the literature review.\n\n\n\n*We hope we answered your concerns and we would be happy if you could raise your score if you are satisfied with our answers.*\n"}, {"review_id": "ld3gvz1DNr", "reviewer": "Reviewer_L7v8", "summary": "This paper provides polynomial-time convergence guarantees for the probability flow ODE implementation. This paper obtains a better better dimension dependence than prior works on DDPM. However, there is no experiments to prove the effectiveness of the proposed methods.", "questions": "Please see the weaknesses.", "limitations": "The limitations have been fully discussed.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well written.\n2. The theoretical results are solid.", "weaknesses": "1. No experiments are performed to prove the proposed method. I think it is necessary to evaluate the method of diffusion models, such as Stable Diffusion or DeepFloyd. I admit that the theoretical results presented in this paper might be important, but that is not the reason of the lack of experiments.\n2. The proposed method has an extra corrector step, which further introduces extra computational costs. \n3. Some comparisons with previous sampling methods (DPM-Solver++, DEIS, etc) are missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\n\n**No experiments are performed to prove the proposed method.**\n\n\nWe experimented our main algorithm DPUM in the appendix on a toy model, and **the Python code is included in the Supplementary material.** The other algorithm we analyze in the paper, DPOM, was already experimented in [Son+21a, Section 4.2].\n\n**I think it is necessary to evaluate the method of diffusion models, such as Stable Diffusion or DeepFloyd.**\n\nSee our comment to all reviewers above. We strongly disagree with this statement. Nobody asked the Stable Diffusion paper or the DeepFloyd paper to provide extensive theory.  Similarly, we believe that papers with solid theory and with small / without experiments can be published as well.\n\n**The proposed method has an extra corrector step, which further introduces extra computational costs.**\n\n**This is wrong.** The complexity we give is the **TOTAL** complexity including the number of steps in the subroutine. \n\nBesides, the use of correctors has shown superiority in practice, see [Son+21a, Section 4.2] among others.\n\n**Some comparisons with previous sampling methods (DPM-Solver++, DEIS, etc) are missing.**\n\n**Comparison is impossible** because all these other samplers are lacking theory. There is an absolute need for more theory papers, similar to ours, in the field of diffusion models. \n\n\n\n**We kindly ask you to evaluate our paper with the lens of a theoretician, i.e., in light of our actual contributions (towards theoretical understanding of diffusion models). If you believe that our theoretical contribution is enough for publication please consider raising your score.**\n\n\n\n\n\n\n[Son+21a]: Y. Song, C. Durkan, I. Murray, and S. Ermon. “Maximum likelihood training of score based diffusion models”, NeurIPS 2021\n"}, {"review_id": "SFWZhJIXQb", "reviewer": "Reviewer_bw63", "summary": "In this work, authors propose improved solution scheme with the specially chosen corrector step for the the score-based generative models. Within the denoising diffusion probabilistic modeling (DDPM) and the underdamped Langevin diffusion approach authors obtain better dimension dependence within certain restrictions on the smoothness of data distribution (Algorithm DPUM) than prior works.", "questions": "Please see the section \"Weaknesses\" above. I have only one more minor comment: [Line 123] for clarity, it may be worthwhile, in addition to the dimension of the noise, to also indicate the dimension of the x variable.", "limitations": "The proposed approach is based on the assumption that the score functions along the forward process are Lipschitz continuous, and it does not cover non-smooth distributions. However, the authors note that this limitation can potentially be circumvented by using the early stopping technique.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Score-based generative models today are of great interest to the scientific community, while the theoretical establishment of their capabilities and limitations is a powerful impetus for the further development of new effective methods. The extensive analysis carried out in this work is certainly relevant and of direct interest to researchers.\n\n2. The work is well structured, written in a great style and easy to read.\n\n3. The provided approach with the polynomial-time convergence guarantees for the probability flow ODE seems to be essential if it will be successfully implemented in practice and applied to the real-world data.", "weaknesses": "Given the high level of theoretical consideration carried out in the work, I am confused by such a weak study of the experimental part:\n\n1. It seems that a (at least brief) description of the performed numerical experiments should be included as a section of the main text (in the presented text, numerical experiments are contained exclusively in the appendix).\n\n2. I do not quite understand the conclusions that can be drawn from the only simple numerical experiment presented in the appendix for artificially generated data from a mixture of Gaussians. Does the proposed theoretical estimate of the convergence of the method hold in this case? How to interpret a word \"approximately\" in [Line 721, appendix]: \"DPUM is able to provide samples (approximately) from the target distribution\"? Can any quantitative conclusions be drawn from the experiment? Is it possible to do some form of convergence analysis and make a comparison with the baseline?\n\n3. Can numerical experiments be done on real-world datasets using a neural network ([Line 130]: \"the score estimates are produced via a deep neural network\"; [Line 723, appendix]: \"recall that we experiment without score error\")?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive comments.\n\n**I am confused by such a weak study of the experimental part**\n\nPlease refer to our answer to all reviewers above.\n\n As mentioned in the paper: “Although we provide preliminary numerical experiments in the Appendix, we leave it as a question for future work to determine whether the theoretical benefits of the underdamped Langevin corrector are also borne out in practice”. \n\nThe experiment is purely illustrative: we believe experimenting should always start with the simplest relevant model, that’s why we used a mixture of Gaussians as a toy model.\n\n\n**It seems that a (at least brief) description of the performed numerical experiments should be included as a section of the main text (in the presented text, numerical experiments are contained exclusively in the appendix).**\n\nThe experiment we provided is purely illustrative, that’s why we chose to put it in the appendix, and we might remove them from the next version of the paper if it confuses the reader about the theoretical nature of our paper.\n\n**I do not quite understand the conclusions that can be drawn from the only simple numerical experiment presented in the appendix for artificially generated data from a mixture of Gaussians.**\n\nWe experimented DPUM on a toy model so the only conclusion one can draw is that DPUM works on this toy model. But this experiment is not our main contribution. Our theory, which is general and not specific to a toy model, is our main contribution. \n\n\n**Does the proposed theoretical estimate of the convergence of the method hold in this case?**\n\nYes, because in this toy model the score can be obtained in closed form as mentioned in the experiment section “We use a closed form formula for the score along the forward process.” Therefore, the theoretical estimate trivially holds. We will clarify this point.\n\n**How to interpret a word \"approximately\" in [Line 721, appendix]: \"DPUM is able to provide samples (approximately) from the target distribution\"?**\n\nThe word “(approximately)” refers to the fact that the output of the algo DPUM is a distribution that is close (but not equal) to the target distribution. Our theory quantifies the distance between the two distributions. We will clarify this point.\n\n**Can any quantitative conclusions be drawn from the experiment? Is it possible to do some form of convergence analysis and make a comparison with the baseline?**\n\nAbsolutely. Our theory applies to this toy model. \n\nIn particular, we can specify our Theorem3 to the toy model and explicit the values of the constants. Is it what you are asking for? If yes, we can add these calculations to the experimental section. By the way, these calculations were needed to run our simulations (whose code is provided in the Supplementary material). \n\nBesides, could you precise what you mean by “comparison to the baseline” please?\n\n\n**Can numerical experiments be done on real-world datasets using a neural network**\n\nPlease refer to our answer to all reviewers above.\n\n**The proposed approach is based on the assumption that the score functions along the forward process are Lipschitz continuous, and it does not cover non-smooth distributions. However, the authors note that this limitation can potentially be circumvented by using the early stopping technique.**\n\n\nThere is a routine \"early stopping\" technique to overcome the smoothness assumption, see [Che+23; LLT23]. We can apply this technique here: we can add a corollary that covers nonsmoothess if you believe that it is important. All the guarantees will remain polynomial in every parameters of interest. \n\nIn order to keep the paper simple, we chose to explain the early stopping argument (which is quite simple) without giving the final complexity result.\n\n\n**We kindly ask you to evaluate our paper with the lens of a theoretician, i.e., in light of our actual contributions (towards theoretical understanding of diffusion models). If you believe that our theoretical contribution is enough for publication please consider raising your score.**\n\n\n\n\n[Che+23]: S. Chen, S. Chewi, J. Li, Y. Li, A. Salim, and A. R. Zhang. “Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions”, ICLR 2023\n\n[LLT23]: H. Lee, J. Lu, and Y. Tan. “Convergence of score-based generative modeling for general data distributions”, ALT 2023\n\n\n\n\n\n\n\n"}]

Author rebuttal:
**TO ALL REVIEWERS and AC:**

We thank all of the reviewers for their hard work in reviewing our article. All reviewers are in agreement regarding the high quality and novelty of our theoretical results, and that our results are of interest to the NeurIPS community. In particular, we leverage recent techniques to accelerate sampling with the Probability Flow ODE: **when using the right corrector, we obtain a complexity that scales as $O(\sqrt{d})$ whereas all other existing complexity results in the field of diffusion models scale at least as $O(d)$.** This better scaling with the dimension specifically matters when generating large scale objects like videos. We believe this is a technical achievement because accelerating sampling is a challenging topic. 



However, the reviewers have also discussed our lack of extensive experiments. 

*In the field of diffusion models, in recent years there have been tons of "applied" papers claiming experimental breakthroughs published at NeurIPS. Yet, there have been perhaps only a dozen of "theory" papers providing scientific understanding. Moreover, up to one or two exceptions, these applied papers do not provide extensive theory, and we do not think that they need to.*

*So why should we expect a theory paper like ours to provide extensive experiments in order to be published?* 

**From reading the reviewers’ opinions, it would seem that our paper clearly passes the bar for a theoretical contribution, and we ask that our paper be evaluated in this regard.**




Besides, our mathematical analysis suggests that the novel corrector we propose could be potentially useful in practice. However, our aim is not to showcase the superiority of our methods via comprehensive experiments. Again, there are thousands of papers purporting to do exactly this, and it is best left for future work. What separates our work from others in this field is to uncover a **mathematical understanding of diffusion models.**

Meta-review: In this paper, the authors studied the convergence properties of an important class of score-based generative modeling:  (some variations of) the probabilistic flow ODE based implementation. When properly modified by a correction step, the authors established theoretical convergence bounds for the algorithms, and demonstrated improved dimension dependency for smooth data distributions when underdamped Langevin diffusion is incorporated into the probability flow ODE implementation. The paper provides solid theoretical contributions to demonstrate the potential of acceleration via proper correction. As the reviewers pointed out, the paper would have benefited from enhanced numerical experiments, given that the algorithms proposed and analyzed in this paper differ from the implementations widely used in practice. In addition, since the schemes analyzed in this paper are not exactly probability flow ODE (due to the correction steps), the current title and introduction might be a little misleading.
Decision: Accept (poster)