Improved Convergence of Score-Based Diffusion Models via Prediction-Correction
Authors: Francesco Pedrotti
Jan Maas
Marco Mondelli
Venue: Accepted by TMLR ()

Abstract: Score-based generative models (SGMs) are powerful tools to sample from complex data distributions. Their underlying idea is to \emph{(i)} run a forward process for time $T_1$ by adding noise to the data, \emph{(ii)} estimate its score function, and \emph{(iii)} use such estimate to run a reverse process. As the reverse process is initialized with the stationary distribution of the forward one, the existing analysis paradigm requires $T_1\to\infty$. This is however problematic: from a theoretical viewpoint, for a given precision of the score approximation, the convergence guarantee fails as $T_1$ diverges; from a practical viewpoint, a large $T_1$ increases computational costs and leads to error propagation.
This paper addresses the issue by considering a version of the popular \emph{predictor-corrector} scheme: after running the forward process, we first estimate the final distribution via an inexact Langevin dynamics and then revert the process. Our key technical contribution is to provide convergence guarantees which require to run the forward process \emph{only for a fixed finite time} $T_1$.  
Our bounds exhibit a mild logarithmic dependence on the input dimension and the subgaussian norm of the target distribution, have minimal assumptions on the data, and require only to control the $L^2$ loss on the score approximation, which is the quantity minimized in practice.

Published in Transactions on Machine Learning Research (05/2024)
Improved Convergence of Score-Based Diffusion Models via Prediction-Correction
Francesco Pedrotti
bancesco.pedrotti@istee
Institute of Science and Technology Austria
Jan Maas
jon-maas@ista
Institute of Science and Technology Austria
Marco Mondelli
maroo.mondeli@istta..cc
Institute of Science and Technology Austria
Reviewed on OpenReview: https: // opwnreveeew........mmmo net/ formm? id= OzKvllYYAq
Abstract
Score-based generative models (SGMs) are powerful tools to sample from complex data distributions. Their underlying idea is to (i) run a forward process for time Ti by adding noise to the data, (ii) estimate its score function, and (iii) use such estimate to run a reverse process. As the reverse process is initialized with the stationary distribution of the forward one, the existing analysis paradigm requires Ti + oo. This is however problematic: from theoretical viewpoint, for given precision of the score approximation, the convergence guarantee fails as Ti diverges; from practical viewpoint, large Tj increases computational costs and leads to error propagation. This paper addresses the issue by considering version of the popular predictor-corrector scheme: after running the forward process, we first estimate the final distribution via an inexact Langevin dynamics and then revert the process. Our key technical contribution is to provide convergence guarantees which require to run the forward process only for a fired finite time Ty. Our bounds exhibit a mild logarithmic dependence on the input dimension and the subgaussian norm of the target distriiuttin, have minimal assumptions on the score approximation, which is the quantity minimized in practice.
the data, and require only to control the I,2 loss
1 Introduction
Score matching models (Song & Ermon 2019 2020 and diffusion probabilistic models (Sohl-Dickstein ct al. 2015 Ho et al. 2020 recently unified into the single framework of scoro-based generative models (SGMs) [Song et al.) 2020 have shown remarkable performance in sampling from unknown complex data distributions ions, achieving the state of the art in image (Song et al. 2020 Dhariwal & Nichol 2021 and audio PPopov et al. 2021 Kong et al.) 2021 Chen et al. 2021bb generation; see also the recent surveys Yang et al. (0230g Croitoru et al. (2023). The idea is to gradually perturb the data by adding noise, and then to learn to revert the process. Both the forward process that adds noise and the reverse process can be described by a stochastic diffcrential equation and, specifically, the reverse process defined in terms of the score function (ie., the gradient of the logarithm of the perturbed density all noise scales, see Section for details). This time-dependenn score function can be learned with neural network, using efficient techniques such as sliced score matching (Song et al.) 2020) or denoising score matching (Vincent. 2011). Then, to start the reverse process, one would ideally need to sample from the perturbed distribution, which is in principle unknown: instead, one runs the forward process for a long enough time Ti so that the perturbed distribution pr, is well approximated by the stationary distribution म, which is known and can be readily sampled from.
A central theoretical question to understand the quality of the sampling, í.e., measure distance between the output distribution of the reverse process and the true Three sources of error are given by (i)

---

Published in Transactions on Machine Learning Research (05/2024)
starting the reverse process from the stationary distribution x, rather than from the perturbed distribution
PT:: (ii) approximating the score function (e.g., with a neural network), and (ti)) discretizing the reverse
stochastic differential equation. The quantitative characterization of such errors has been carried out in a
number of recent papers, see Song et al. (2021a): Kwon et al.] (2022): : Lee et al. (2022) : Chen et al. (002bb
2022a]; Bortoli (2022) and Section 2 However; to achieve convergence of the output distribution to the
ground truth, this line of work requires to run the forward process for Ti + 0c. This is due to the first source of error mentioned above, i.e., the approximation of pT, with क. At the same time, large values of T1 amplify the other two sources of error and are also responsible for an increased computational cost in the training procedure, because of the need to approximate the score function on large time interval Ti]. Thus, there appears to be a subtle trade-off between the precision in the score approximation and the running time Ti: on the one hand, one needs to take Ti - xo so that pr, approaches тı; on the other hand, for a given precision in the score, the convergence guarantees fail as Ti + оe which highlights the instability of existing results. For these reasons, it is of great interest to characterize an appropriate time Ti where to stop the forward process (Yang al. 2023 Sec. 8).
Main contribution. In this work, we address the trade-off in the choice of the rumning time T1 of the forward process by considering a variant of the predictor-correct precisely, after obtaining Pr, via the forward process, we sample from pr, via an inexact Langevin dynamics that leverages the approximation of the score at time Ti. Then, use the resulting sample to start standard reverse process. Our main convergence result (Theorem 4.1p focuses on the deterministic reverse process, which has the form of an ordinary differential equation (ODE), and analyzes the proposed algorithm: in particular, it provides convergence guarantees in Wasserstein distance for a vast class of data distributions and under realistic assumptions on the score estimation, which are compatible with the training loss used in practice. We highlight that our bounds require a perturbation time Ti that only depends logarithunically on the dimension of the space and on the subgaussian norm of the target distribution, and not on the desired sampling precision. The mild logarithmic dependence suffices to ensure the regularity in the form of a log-Sobolev incquality of the perturbed mcasure pf, which in turn allows the inexact Langevin dynamics to converge exponentially fast.
methods of Song et al. (2021b). More
Our analysis improves upon earlier bounds in Wasserstein distance (Kwon et al., 2022 by removing both the need for Tj - do and an assumption on the score estimator (more precisely, on its one-sided Lipschitz constant, see the discussion after Theorem 4.1 for details). This comes at the cost of requiring a control on a loss function for the score estimate at time Ti, which stronger than the usual I,2 loss. To address this issue, we exploit the fast convergence of the forward process to its stationary distribution in order to correct the score estimator, which in turn allows to translate upper bounds for the L loss into upper bounds for the stronger loss (Theorem 4.2 Finally, when considering instead a stochastic reverse process (SDE), we show how the algorithm is compatible with the existing analyses for the convergence of the discretized reverse SDE in information-diverger variation distance for a discretization of the algorithm. Consequently, we highlight some advantages over previous results that arisc from the choice of a fixed perturbation time Ti, related again to the docreasod computational cost in the training procedure and to the stability of the error bounds.
metrics. This allows us to deduce convergence guarantees in total
Paper organization. Section 2 discusses related works. Section 3 sets up the technical framework by recalling the formal description of SGMs. Section g presents our main contribution: after describing the algorithm, we state the convergence result in Wasserstein distance. Section 4.1 contains a sketch of the proofs, with the full arguments deferred to the appendix. Our main convergence results in Section 4 are stated in continuous time and in Wasserstein distance. Then, Section the algorithm, as well as convergence result in total variation distance. Section concludes the paper with some final remarks.
5 contains discussion about discretizations of
1 See, e.g. Chen al. 2023b Thm. 2) and nate that the third term in the bound diverges when escore is fixed and T cc.
2

---

Published in Transactions on Machine Learning Research (05/2024)
2
Related work
The empirical success of SGMs has led to extensive research aimed at providing theoretical guaranlees on their performance. Specifically, the goal is to give upper bounds on the distance between the true data distribution p and the output distribution po of the sampling mothod. Adopting the description of forward and reverse process in terms of stochastic differential equations (Song et al. 2021b), an upper bound on the KL-divergence (p 11 Pa) is provided in SSng et al. (021a)): under some regularity assumptions, this KL-divergence goes to 0, as Ti + oc and the score approximation error vanishes. In a similar vein, using the theory of optimal transport instead of stochastic tools, an upper bound on the Wasserstein distance? (2 pa) is provided in Kwon et al. (2022). In many important situations, results in Wasserstein distance are more meaningful than in KL-divergence or total variation: for example, under the manifold hypothesis, it is not possible to obtain non-trivial convergence guarantees in those metrics, as one has DKL (p l1 po)
and TV(p.Po) = 1 (cf. Bortoli 2022 Chen et al. (2023b)). However, to obtain convergence, Kwon et al. (2022) imposes strong assumption on the score estimator. A line of work has focused on the discretization of the reverse stochastic differential equation. Specifically, convergence in Wasserstein distance of order I is provided in [Brttlli (2022) under the manifold hypothesis, but the results depend poorly on important parameters, such as the sampling precision, the input dimension and the diameter of the support of p. The works Lee et al. (2023): ; Chen et al. (2023b; (022a) provide convergence guarantecs for general distributions in KL-divergence and total variation (which is weaker by Pinsker's inequality). From these results, bounds in Wasserstein distance are also deduced for some classes of distributions, including bounded support ones. This improves upon Bortoli 2022), but the improvement requires an extra projection step and comes at the cost of a worse dependence on the problem's parameters in comparison with the bounds in KI-divergence and total ioriation. Other works have provided convergence results for SGMs, but they suffer from at least one of the following drawbacks (Chen et al. 2023b): (i) non-quantitative bounds [Pidstrigach] 2022 Bortoli et al, 2021 or poor dependence on important problem parameters (Block et al. 2022), (ti strong assumptions
on the data distribution, typically in the form of functional inequality (Lee el al. 2022 Yingxi Yang & Wibisono 2023 : and (ik) strong assumptions on the score estimation error, such as uniform pointwise
control (Bortoli et al. 2021), which is not observed in practice (Zhang & Chen 2023
In most of these works, to guarantee convergence of to p, it is necessary to have Ti + co. In contrast, Bortoli et al. (2021) introduces a diffcrent approach based on solving the Schrödinger bridge problem (see also Chen et al. (2022b); [Shi et al. (2022); Song (2022)), which allows for a finite time perturbation of the target measure; however, this strategy does not come with quantitative convergence results under realistic assumptions. The work Franzese et al. (2023) adopts an approach closer to ours: an auxiliary model is used to bridge the gap between the limiting distribution of the forward process and the true perturbed distribution, which is then followed by a standard reverse process. However, the design of the auxiliary model appears to be ad hoc for the data distribution, and a theoretical convergence result for general data distributions is missing. Our algorithm can also be considered as an instance of the prodictor-correete approach of [Song] et al. 2021bb: there, the authors suggest to alternate one step of the reverse process with a few steps of a corrector method based on the score function, such as Langevin dynamics, and provide extensive empirical evidence showing an improved performance. In this work, we consider instead the case where all the corrector steps (Langevin dynamics) are performed at the beginning, and they are then followed by a standard (non- corrected) reverse process. We remark that error bounds for (a different variant of) the predictor-correcto. schemes were first provided in Lee et al. 2022). The results therein, however, impose strong assumptions on the data distribution, in the form of a log-Sobolev inequality; the log-Sobolev constant enters crucially in the derived bounds, which depend polynomially on it, and not just logarithmically.
Concurrent work. The concurrent work Chen et al. (2023a) also studies the performance of predictor corrector scheme. Instcad of our two-stage algorithm, Chen et al. (2023a) considers an implementation closer to [Sng et al. (2021b). that alternates deterministic predictor steps with corrector steps based on Langevin dynamics, For this method, the authors provide convergence guarantees in total variation distance:
FFor general data distributions μ, H, there is no relation between (v |] µ) and Wz(u, P), therefore the results in KL- divergence cannot. be translated trivially results in W2, and vice versa. In particular. the analysis in Wa seems to be more challenging, because of expansive term in the reverse process (ef. Chen et all (2023)) Sec. 4)).
3

---

Published in Transactions on Machine Learning Research (05/2024)
interestingly, they show that when the corrector steps are based the underdamped Langevin dynamics (rather then the classical overdamped version), it is possible to obtain a better dependence on the dimension d. Contrary to our results, however, the error bounds in Chen et al. (2023a) still require Ti + oo to obtain convergence, with analogous disadvantages as we discussed for pre-existing results.
After the first version of our paper appeared online, further progress on the theoretical study of SGMs has been made. The work [i et al. (2023) obtains convergence guarantees for both the standard reverse SDE and the deterministic reverse ODE (without corrector), using approach based on studying directly discrete time methods rather than controlling the errors in approximating the continuous time dynamics. The paper Benton ct al. 2023) improves the dimension dependence of convergence guarantees for the reverse SDE, when one does not assume Lipschitzness of V log,t, by exploiting a connection with stochastic localization (Eldan, 2013 Montanari 2023). The work Cooforti et al. (023)) proves convergence in KL-divergence without early stopping when replacing the classical Lipschitzness assumption on Vlogp, with finiteness of the relative Fisher information.
In general, these works can be considered complementary to the present contribution, in that their analysis techniques can be combined with our methods to provide convergence results for the two-stage algorithm under a set of different assumptions, gaining the advantage of fixed perturbation time Ti. We refer the reader to Section 5 for an example of this.
3 Preliminaries
To sample from an unknown data distribution on Rd, the framework of SGMs consists perturbing p through a forward process that converges to known prior distribution and then approximately reverse this process. The forward process is described by a stochastic differential equation (SDE)
Xo ~ p. dX, Xi) dt + g(t) dBe
(3.1)
where B, is a standard Brownian motion, f and g are sufficiently smooth, and the SDE is run until some time Ti > 0. The law of X,, denoted by Pt, correspondingly solves the Fokker-Plance equation
{
po =0=0 P. Oep Oep. v v. (p (f(t)t)))) 2012 V log logpr(z))] = =0
(3.2)
Remarkably, under some regularity conditions, this SDE admits a reverse process, in the sense that, for any smooth function M: Ti] + Rz1, the process (U)), defined by
S Un UD~~ Pr, = - - U,) 2 9(T 2) log Pn (Ui) dt + /M()) Ig - t) dBe
(3.3)
M(L)
is such that UT, ~ p. Usual choices are M(t) = 2 or M(t) = 1 and, considering the latter, the reverse process is deterministic, except for its initialization, see Song al. (2021b) Sec. 4.3). Below, will first focus on M for simplicity, but similar results can be readily deduced for general (t).
To simulate the reverse SDE 3.3) and sample from P. one needs to (i) approximately sample from Pr, to initialize the backward process, and (ii) estimate the score function with so(t,-) ~ V log for e Ti]. For the first. point, one chooses Ti big enough so that pr; is close to a known distribution æ and samples from Yo ~ ग. For the second point, one learns a function st x) that approximates V (x() e.g. with a neural network: specifically, the training loss considered in practice is
(0 A) //" Ti
A(t)Ep. V logp: so(t, -]1]
(3.4)
for some strictly positive weight function X(t). Notably, although the score V log Pa unknown, this loss be estimated with standard score-matching techniques (Vincent) 2011 Song et. al.] 2020 2021b
4

---

Published in Transactions on Machine Learning Research (05/2024)
When x(t) o(t)?, which corresponds to the likelihood weighting of [Song et al. (2021a) simply write (0). The corresponding sampling algorithm simulates the process
Yo ~ n, dY, -----0 -(T) 1, Y.) di MOO 2 2-9 (T) 10 (.) (M(1) 1g(Ti dB,,
(3.5)
until time Ti, and it takes Yz, as an approximate sample of p. This reverse SDE can be approximatod via standard yeneral-purpose numerical solvers, or by laking advantage of the additional knowledge of the approximated score function se(t, R VlogPt: Pe: for example, the predictor-correcto methods of [Song et al. (2021b) alternate one discretized step for the reverse process 3.5) with several steps of a score- score-bascd corrector algorithm, such as Langevin dynamics or Hamiltonian Monte Carlo.
For ease of exposition, we will focus on the popular Ornstein Uhieenbek (OU) forward process
Xo P. dx, = -x + /
(3.6)
which corresponds to method known Denoising Diffusion Probubilistic Models (DDPMs) (Ho et al. 2020), and is also referred to as Variance Preserving SDE in [Song et al. (021b). Its Fokker-Planne Planck equation reads
{
Po - O.p. +V 1p((--- VAsrr-Voo Vlogp((z))]
(3.7)
The standard Gaussian Y is the limiting distribution of the OU process: more precisely, if Z ~ is inde- pendent of Xo, then X2 ~ e "Xo + -1-e Z, and Pt converges to Y e.g. in Wasserstein distance W2 and in relative entropy (- (Villani 2003, Chap. 9). Restricting to the OU process (or its time reparametrization) is commonly done in the theoretical literature, see Lee et al. (2022): [ortoli (2022): Chen et al. 2023b )022a); for these works, our techniques be extended to other choices of the forward process, such those considered in Song et al. 20220 Sec. 3.4).
Notation. We denote by Th,t the density of a normal random variable in Rd with mean y and variance tla, and for compactness we write "t = To and = 71 With abuse of notation, we identify the law of random variable with the corresponding probability density. Given two probability measures μ,, u, the KL-divergence is defined by (K || v) log and (KL(H]) = to otherwise; if have finite second moment, the 2- 2-sasserstein distance is defined by W2(H,)) v) = inf infx~w,y~ [[IX - Y We denote by P(Rd) the space of probability measures on IRd, Throughout this paper, we denote by p the target probability measure and by pt its law following the OU process; correspondingly, we consider random variables X ~ p, X, ~ Pt- We use the symbol X to denote an inequality up to an absolute positive multiplicative constant.
du if μ is absolutely continuous with respect to v, du de
4 Improved Wasserstein-coonerggee in continuous time via prediction-correction
Description of the algorithm. We consider the following predictor- predictor-correctoo algorithm. First, we the OU forward process (3.6) until time Tj and, for 0 < t < Tı, we approximate V legg with so(t,z). Next, we approximale pr, by following an inexact Langevin dynamics started at 7 until time T2:
corrector
{ Zo ~ 7: dZ. (i) V
(4.1)
0
We remark that the Langevin dynamics we have access to the former but not to the latter. The idea that, as these two quantities are close, the random variable Zr, provides approximate sample of pr,, for sufficiently large Tz. Then, we approximate the original distribution by following a deterministic reverse process that starts from Zr₃;
4.1 is incract as it uses so (T(T, in place of log (x), since
{
Yo = ZTz
(4.2)
dY, Y, Y,dl dt So 1, Y.) di,
0 S
5

---

Published in Transactions on Machine Learning Research (05/2024)
We let q: law(Yi) for [0, Til and oe law (z) for t E [2] In particular, we have go oT-- Here, the prediclion-corveccion consists in starting (4.2) from Zr, instead of n. We also note that this reverse process is deterministic except for its initialization Yo = ZT.- This allows to use standard numerical methods for solving ordinary differential equations, and in particularly exponential integrator schemes have shown remarkable performances (Lu et al. 2022 Finally, we take Yr, to be an approximate sample from p. For stability reasons, we can also choose a small time 0 < Ti and stop the reverse process (4.2) at time Ti T, taking YT= as an approximate sample from p. This commonly done in practice, see e.g. Song et al. 2021b Sec. C).
Assumptions.
Throughout this section, we consider the following assumplions.
(A1) The estimator se: [0, -
+ 12 is Lipschitz continuous. Moreover, for E [0, Ti] we denote by (t) I the one-sided Lipschitz constant for so(t, -), such that for all x, y R
(se(t, - se(t, f2x y) - Lo(t)llr-
yll?. -
(A2) X ~~p p is norm-subgaussian.
Condition (A1) is mild: in fact, so is typically given by neural network, which corresponds to Lipschitz function for most practical activations, We emphasize that the requirement on the Lipschitz constant of is purely qualitative, in the sense that it does not enter our bounds (as opposed to the onc-sided Lipschitz constant, which instead plays a quantitative role the bounds).
As for condition (A2) we recall that an -aluul random variable X is nurm-subgaussian its euclidean norm ||||| is subgaussian (for details and a formal definition, see Appendix A).. We denote by | |s the corresponding norm. Bounded random variables and subgaussian ones (in the sense of Vershynin 2018 Def.
3.4.1)) are norm-subgaussan,, which covers most practical cases (e.g., in image generation pixels are usually rescaled in 1)). Other properties of norm-subgaussian random vectors are established in Jin et al. 2019
Performance of the proposed algorithm. Our main result is stated below.
Theorem 4.1. Let Assumptions
A2 hold, and let pt be obtained via the forward OU process in 3.6 Pick < 8 1, T2 0, Ti 2 2 log 172 ixllaa + 28 and a small early stopping time 0 <TS
(A1)
min Ti, 2|| 2|[ Let ps = sT = law (ow(YT,-1)) where Yn-- obtained from the reverse process in 4.2
Consider the loss functions given by
b(1) = Ep. -
sa so((,-))²)
EMGF log Epr, exp ( I
Vloogr sp (Ti, (TT)
Then, the distance between the output and the target distribution p can be bounded as follows:
(2(p.po) S V3rd + J. ("VoCE)L
(.T))) (,)T)) 1- (de (1aaT + +2EMGF
(4.3)
JsM(()
2 [ T (t)) dt + (((T)) (5e- 11-61722 + 22MGF))
$ 333d+
(4.4)
where (t) exp T + (r(r))r)
The right-hand side of 4.3
consists of three error terms, due to (i) the early stopping the reverse process (.2).. (ii) the approximation of the score function sy (t.-) V P; (4.2). and (Mii the approxima- tion qu oTH Pr from the output of the Langevin dynamics 4.1) A key feature of Theorem 4.1 is that, to have vanishing sampling error, does not need Ti In fact, consider sequence of estimators
4.4

---

Published in Transactions on Machine Learning Research (05/2024)
satisfying the additional technical assumption su frd exp (xp(2,, La(r) dr) dt < co. Then, letting T - 0, JsM + 0, EMGF + and T2 - oo, with Ti fixed, the convergence of po to p in W2 distance follows from Theorem
We now discuss the roles of 12, T and of the free parameter 8.
The rolc of 7 is to ensure the regularity of pry. Specifically, we show that Pr, satisfics a log- rog-Soooeev incquality with constant at least. 1 1, 6, which leads to the mild logarithmic dependence of Ti on the subgaussian norm ||x. In fact, the dependence on can be even dropped (although the subgaussian norm ||sG may
still depend on d) if Ti 2 2 log 2 + 172 [x then 4.3 and (.4 hold with d exp (1-6)22 in place
of 6exp -----) (see the last term of the expression). Choosing Ti > 0 is necessary, as performing
Langevin dynamics directly for p works poorly. This was already observed in Song & Ermon 2019 and
served precisely as a motivation for SGMs.
The role of is to improve the accuracy of sampling from pr, and, due to the regularity of this distribution, the convergence is exponential in T2. Taking T. large, instead of Ti, is beneficial, as the neural network
needs to approximate the score of the forward process only until time Ti and, correspondingly, JsM increases with Ti. In contrast, Kwon et al. 20022 Thm. 1, Cor. 2) requires Ti + oo to achieve convergence, and a full quantitative analysis of the dependence of the bounds on T₁ missing.
The role of is to allow for early stopping in the reverse process 4.2 Tf that is not needed (since e.g. the distribution p is sufficiently regular), then one can simply take the limit T 0 in
The role of 5 is to provide a trade-off between Ti and Tz. We remark that the result of Theorem 4.1 holds
for any 8 E (0, 1), and smaller values of give a faster decay of the error term coming from the Langevin dynamics, duc to the larger log-Sobolev constant of pr,- This improvement comes at the price of a tighter lower bound for Ti.
We highlight that our convergence result does not need the condition lim Lt(t) -1, which was intro- duced in Kwon et al. (0022). This requirement was heuristically justified by the ono-sided Lipschitz constant of the stalionary distribution y of the forward process (3.6) being -1, but obtaining a rigorous control on lime-+00 (t) only from the _ loss of the score estimation remained challenging. To circumvent this issue, we instead introduce the additional loss EMGF in Theorem 4.1 which concerns the score estimation only at time Ty. By Jensen's 's inequality, this is a stronger loss than the usual L one (CMGF 2 b-Ti() However, a simple truncation of the estimator so () allows us to control EMGr terms of b(Ti). This formalized in the result below.
Theorem 4.2. Let Assumptions (Ai)
hold, and let pt be obtained via the forward OU process in (3.6) starting from X ~ p. Pick 0 and Ti 2 log( 16 d(IxXllsa + 1)). Define the estimator Sy: Rd + R by
A2)
[sn(Ti,>))
if - - [s0 (Ti Se, if [so [T), < -3,- l
3o [xx],,
24 -l,
(4.5)
xt + e,
if [so(Ti, > -x, + l
where 8= -(xx)= 2a (1 + [[-))) Fix 0 < <<<<<> 1. Then, for all 0 < 35 368", we have
Epg, /expl (8| - Se,
(4.6)
provided that
1 1369882
b(Ti) <
(4.7)
3433
3hhis condition was implicitly needed in Kwon et al. (202)) for the same reasons. To see that it is reasonable, notice that T. is upper hounded by the Lipschita constant Lip(s)); which is expected to be similar to Lip(V Lip(Vlogg)) as J&M + 0. The latter is well behaved by the regularization properties of the OU flow: if p has bounded support, then f Lip(V (op(Vlogpp) dt < oo for all 0 < < Tj (Chen et al. 20233] Lem. 20). Note also that the one-sided Lipschitz constant can be negative (e.g., for % it is equal 7), which helps with the convergence of the integral.
4This passage can be justified by an application monotone convergence, after estimating the one-sided Lipechita constant. (t) with the Lipschitz constant of sg(t.-).
7

---

Published in Transactions on Machine Learning Research (05/2024)
A combination of Theorems 4.1 and 4.2 gives an end-to-end convergence result in W2 distance requiring only control on the 1.2 loss {b(1) [E(oT.) which is the object minimized in practice. We regard the truncation of the estimator se -)( carried out in Theorem 4.2 as purely technical. In fact, even if the estimator se so(Ti,) explicitly minimizes the training loss b(T1), one also expects the stronger loss CMGF to be small, when 8 is sulficiently small. This is confirmed by the numerical results of Figure D for which we do not replace the estimator (T with sp. Specifically, the plots show that, having fixed Tı, both W2(p; po) (in orange) and W2(PT, .0) (in blue) decrease as function of the running time T2 of the inexact Langevin dynamics 4.1 for different standard datasets.
Gaussian mixture
Two
Swiss roll
0.6
W W 9e)
0.5
Wa 90)
Wi(pr. 9o)
Wossertein distance
0.5-
W Wy(p.po pu)
Wasserstein distance
0.4
Wa(p.pl pa)
Wasserstein distance
0.4
Wy(p.
0.4
0.3
0.3
0.3
0.2
0.2
0.1-
0.1
0.1
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.1
0.3
0.4
Running time Langevin
Running time Langevin
Running time Langevin
Figure 1: Simulation results for an asymmotric mixture of two gaussians (lcft), the two moons dataset (center) and the rescaled swiss roll (right). For fixed Ti and variable T2, we plot in blue the W2 distance ween the perturbed measure pr, and the output of (4.1p, while plot in orange the W2 distance between the truc distribution p and the output of the algorithm po. As expected, both quickly decrease as T2 increases.
4.1 Proof ideas
Analysis of the reverse process (4.2). To obtain Theorem 4.1 we start with the analysis of the reverse
process (.2)). By adapting the argument in Kwon et al. (2022) we derive the following bound on the Wasserstein distance between pr and 9n---
Proposition 4.3. Under Assumptions [A1) A2)
for 0 OSST Tı, we have
We(P,, & I, (T.))W(pn, 20) + f" T
b(t))
(4.8)
For completeness we include a proof in Appendix since compared to Kwon et al. (2022) we consider M(I) (and not M(I) 2), different starting distribution for Yo, and early stopping. In addition, we need the following short-time estimate W2 Pr), which is proved in Appendix B
Lemma 4.4. Suppose that M Jg. [==111(()))d co. Then, for 0 < < ,J2, have
W2(p.Pt) S 3rd.
Using the triangle inequality for W2, the combination of Proposition 4.3 and Lemma 4.4 readily gives
Wa(p.om-r) v3rd + (TTT [ Th (b())-(()))
(4.9)
This bound shows that to achieve convergence, we need (i) small T, (i) b(t) + 0 (which is reasonable, since Sy is obtained by minimizing the I,2 loss), and (ii) W2(9o-P)) - 0. The latter condition corresponds choosing good starting distribution for the reverse process (instead of y), and it is ensured by the inexact Langevin dynamics (.1)) which will be analyzed next.
8

---

Published in Transactions on Machine Learning Research (05/2024)
Analysis of inexact Langevin dynamics 4.1
Recall the definition of the log-Sobolev inequality.
Definition 4.5. A probability measure μ satisfies a log-Sobolev inequality with constant & > 0 (notation: LS[(K)) i for all probabilily mensures v,
2x DKL(v1IM) - In(v),
(4.10)
where (v) is the relative Fisher Information, defined by
dv log
| dv =
/
V
du,
if and y E HH))
[n(2)= Rd
du
(4.11)
+00,
otherwise.
Here, (p) denotes the weighted Sobolev space. If satisfies a log- log-Sobolev inequality, we use the notation CIS(H) for its optimal constant.
Remark 4.6. If satisfies LSI(R) for some > 0, then it also satisfies the transport-entropy inequality (Otto 8 Villand 2000) (sec also Gozlan & Léonard 22010 Thm. 8. 8.12) for overview of related results)
2 K W2(1, S V Dxi(vlln).
(4.12)
It is well known that Langevin dynamics for mcasure μ converges exponentially fast in KI-divergence if μ satisfies a log-Sobolev inequality, see e.g. Villani 2003 Vempala & Wibisono 2019). A similar convergence result has recently been proved in Yingxi Yang & Wibisono (2023) for the inexact Langevin dynamics
Zo V,
(4.13)
dz, = so dt + vddB
where approximates the score V logg. For convenience, we state Theorem 1 of Yingxi Yang & Wibisono 2023) below.
Theorem 4.7. Let u.v be probability measures with full support that admit densities with respect to the Lebesgue measure. Suppose that μ satisfies log-Sobolev inequality and let Cis(u). Then, the time- marginal law ve of the ineract Langevin dynamics (4.13) satisfies, for 220
DKL(u: |l ()) S e - DKL(U (1)) + 21og E, exp Vlog VVlom-soll3 soll2)
4.7 requires pr, to satisfy a log-Sobolev inequality, as well as the estimation of The application of Theorem
CLs(Pr;). To ensure this, we notice that pr, = law e TT: Ti e--e--i-- e-2---22222 -7:77) where Z ~ y is an independent Gaussian, and apply recent results from Chen et al. (2021a) that quantify the log-Sobolev constant of the convolution of subgaussian probability measure with Gaussian having sufficiently high variance (ef. Lemma B.3 and Theorem B.4 in Appendix By. In this way, we deduce that CLs(Pr, 2 1 - 8. Next, in order to apply Theorem 4.7 with j pT, and y, need an estimate of (KI ((T)). This is provided by
the result below, which is proved in Appendix B
Lemma 4.8. Let p P(RR)) with M = Jg ||0|| dp(x) oc. Then, for > we have
d M
2 + to logo, oe o0+1..
DKL(T 11 p.) <
e-2
20,
d
with 0, = 1- 2t Thus, for max (2)(( (V3M) we have DKL(7 || pt) S /.
max(1og( (log(
log ((M)///2/6)) we have DKL(y S 6, while for
max [log( max((og((
By combining the estimate on (KI, |PT) given by Theorem 4.7 with the transport-entropy inequal- ity (4.12) (which also uses Cis(pr,) 2 1- > 0) and the above lemma,, we obtain an upper bound on W2(TT, Pr. W2(00 P. Combining this upper bound with (4.9) gives the desired inequality (4.3). The inequality (4.4) then follows from the Cauwhy-Schwarz inequality, which concludes the proof of Theorem 4.1
The complete argument is contained in Appendix B
9

---

Published in Transactions on Machine Learning Research (05/2024)
It is not difficult to construct estimator sæ (Ti..) such that b(Ti) is arbitrarily small and MMGF diverges. In fact, consider estimating the score of the standard Gaussian 7, given by V 7lg) -z, via a sequence of estimators of the form (M(x) = |= Then, we have limas-+s b(Th)= = 0, but CMGF is infinite for all M 2 0. This might seem discouraging, but we can prevent such pathological problems by leveraging our knowledge about the larget score function. This allows us to fix predictions of the estimator so(Ti, 4)) that happen to be very far from the target value V log Pr, (1)
Controlling stronger loss (Theorem 4.2)
More precisely, by choosing Ti according to the prescrip-
tion of Theorem 4.2 can ensure that V loggr, (a:) lies in region around the score of the standard Gaussian V log = -x, i.e.
& logas
1-z 0, lo
1 21 |=-]),, for all E (1,...,d),
2d (1
see Lemma C.2 This is illustrated in Figure 2 in one di- mension: the green dashed line represents V Vlog = -x, and our choice of Ti guarantees that VlogPT, lies in the region delimited by the blue and purple lines. Whenever sg returns value outside this region, we correct it by choosing the closest value the boundary. This leads to the definition of the estimator Se given by (4.5) For
Figure 2: The confinement region for V log pT.
this new estimator, we can now convert an L error into
an upper bound for (MGF, which gives Theorem 4.2 The argument crucially relies on the fast decay of the
tails of pr,, thanks to the similarity with the standard Gaussian 7, and exploits the confinement knowledge
to deduce a converse bound to Jensen's 's inequality, cf. Lemma A.4 Appendix C
The complete proof is contained in
5 Convergence of discretized schemes in total variation distance
In practical implementations, the contimuous time dynamics needs to be approximated by a discrete time scheme. The existing literature for discretizations of the reverse process (Chen et al., 2023b 2022a Lee et al. 2022) focuses on the reverse SDE instead of the ODE (te., (t) = 2 instead of M(t) = 1 in (3.)). and on information-divergnnco metrics instcad of the Wasscrstein distance, as for the latter the analysis seems significantly more complicated &Chen et. al., 2023b Sec. 4). The two-stage algorithm (with a stochastic reverse process) considered in this paper is compatible with such recent analyses: we illustrate this in the present section by providing convergence guarantees for natural discretization of the algorithm. The argument proceeds in a similar way to Section 4 In particular, a key role is played again by Lemmas B.3 and 4.8) the first guarantees that pr; satisfies a log-Sobolev inequality with a good constant, so that a discretization of the inexact Langevin dynamics performs well, while the second ensures that the Gaussian distribution 7 is a good initialization for the algorithm.
For the discretization of 4.1 we consider following the inexact Langevin algorithm with variable step sizes hy O:
{
Zo ~ 7: Z Zx + hTs Zx) + + Bk
(5.1)
where (Ba)a idd ((,, This is run for a variable number of steps N2, and we now denote by o the law of Zz.
Convergence guarantees for Ze as k + co can be obtained from the analysis in Yingxi Yang & Wibisono 20033 Thm. 2), which we slightly modify to take into account decaying step size: this will give a logarithmic improvement on the computational complexity, in the same spirit as Dalalyan & Karagulyan (2019). As in Scction 4 (and as in |Yigxii Yang & Wibisono/ (2023)), the analysis of the Langevin algorithm introduces a modified loss ÊMGF, which is stronger than the standard L' error on the accuracy of the score estimate. However, at time Tj this loss can be controlled again thanks to Theorem 4.2 (cf. also Remark 5.2
10

---

Published in Transactions on Machine Learning Research (05/2024)
As for the reverse process, to take advantage of the existing literature, consider discretization of the reverse SDE instead of the reverse ODF (corresponding to M(I) 2 instead of M(l) = = in (3.5 The
chosen numerical method is the popular exponential integrator scheme (Zhang & Chen 2023), so that the second stage of the algorithm given by
{
Yu- = ZNZ
Yx+1 = Yhe + (1s, Ya) (ebe -1 + Veeho 1Bk
(5.2)
to Ti
k-1 -ooii h4s
for a sequence of step sizes (h=) such that E he Ti and for (Ba)a iid NO0, Ta). The output YN, is finally taken approximate sample from p, and denote now by po its law; under appropriate assumptions, we derive convergence guarantees of to p in total variation distance. In place of the integrated 2 loss in (3.4), for discrete time schemes it is natural to introduce the analogous loss
N1
JSM hr Voloo.t. 80((s, )19
We can think of JsM as an approximation of JsM: it is a standard and realistic assumption that JSM can be made arbitrarily small with sufficient data and model capacity. The errors arising in the reverse process (5.2) (due to the inaccuracy of the score estimate and the use the discrete scheme) can be bounded thanks the recent theoretical literature on the performance of diffusion models, see c.g. Chen et al. (202bb) deduce end-to-end convergence guarantees for
2022a); together with the analysis of (5.1) this allows the two-stage algorithm.
To illustrate this, present below one such result which exploits the analysis of Chen el al. 2022a Thm. 1), and we refer the reader to Appendix D for the proof. Additional results under different assumptions and choices of the step size can be doduced by adapting other arguments (c.g. Chen et al. (2022a Thm. 2)).
Specifically, we consider a constant step size for the reverse process and a standard smoothhess condition Chen et al. 2023b 2022a).
Theorem 5.1. Under Assumption (A1) pick 0 < 1/4 and Ti 2 1 log 2 172 I + $ Suppose in addition that V log Pt is L1 Li-Lipschitz for t E [0, and that so(T),.) is L2 b2-Lipschitz with L1, L2 1, and consider the modified loss at time Ti
9
V logpr; so )1
ÊMGF log E Bpr
exp
(5.3)
1-8
Then, for the algorithm described above with step sizes ha
and h4s = h
T1 N.
S 1, ue have that
24T. LIT
dLTTy N1
L1
2
dL3
TV(p.po) S /
JJM
+ V N2 +1
+
+ EMGF
N2 +
(5.4)
N2 (1111
(
dL3
JsM+ + diITTT+
+ EMGF.
N₂ +
Remark 5.2. To deduce convergence from the above result assuming only I?? accuracy of the score, we need to control ĒMGF. This can be done again using Theorem 4.2 where we now choose B = T-8 and take 0 8 < 0.054 to fulfill /3 < 3657
9
Remark 5.3 (Complexity of sampling). Suppose that the goal is to achieve TVpp. pe) S for some 0 < c A typical assumption is to be able to control the I? error of the score approzimation; hence, by the remark above, we can assume that JSM, ÕMGF Ee, as needed in the bound 5.4 Consequently, 5.4 shows that the algorithm needs most N sleps to ensure TV(p. po) Se, with
N + No. S 2
(L + || L3).
11

---

Published in Transactions on Machine Learning Research (05/2024)
Remark 5.4. If we choose also for the ineract Langevin algorithm 5.1 fixee step size b2 h 24 we oblain instead the bound
dIRTR Ni
TVpp.Po) E / [SSM+ +
Ve + 12(In + L2)dh EMGF-
this case, for the number of steps N to achieve TVp, e, we have that
N N d (13 [12 (d+ | + La(Li L2) Log :)
5.1 Comparison with previous results
To highlight a few favorable propertics of the predictor-corroctor algorithm, we compare the result above with Chen et al. (2022a Thm. 1), translated into total variation distance via Pinsker's inequality. The authors of Chen al. (2022a) consider, under similar assumptions, the standard sampling scheme based on discretization of the reverse SDE without the prior Langevin algorithm any corrector; in other words, they consider (5.2) with constant step size initialized at Zo % For the corresponding output distribution Po they prove the bound
dT?T? / (M d)e- 22, + JSM Ni
TV(, &
(5.5)
v (M d)e 27i + JsM + dL2Tih
where M is the second moment of p. Therefore, to achieve TV(p. I c the reverse SDE needs most N steps with
M +
N S log
22
Comparing the bounds (5.4] and 5.5 shows some advantages of the predictor-corrector schemes, arising from a fixed choice of Ti independent of the desired sampling accuracy e.
1. The convergence result in 5.4 unlike 5.5p, is stable with Ti. In other words, for fixed choice of step size h in the reverse process, the bound in (5.5) explodes as Ti - oc, which is however necessary to minimize the error (M + dd)-221 arising from the approximation pr; m.y Thus, there is a trade-off between the choice of Ti and the step size in the reverse process. In contrast, this problem does not occur for the bound in (5.4), since Ti now fixed. For the specified choice of step sizes hą (which is independent of the desired accuracy), the error goes to as h + and N₂ + oo. At the same time, the bound is now stable for any choice of the variable quantities h < and N₂ 1. Yingxi Yang & Wibisono (2023) also aimed at obtaining stable convergence. However, the results therein apply only to distributions satisfying log-Sobolev inequality and under stronger assumptions on the accuracy of the score.
2. To achieve convergence, the bound 5.5) requires learning the score V log Pt on time interval which increases Ti oc: correspondingly, the error term JsM increases too with Ti. For example, assuming that we have LL-aceuracy of e² at every time (i.e,, b(tx) I e² for every tx, cf. Assumption 3 of Chen al. (023b we have that JsM = eT,, which diverges as Ti 3o with fixed e 0 (see also Chen al. 2023b Thm. 2)). These problems do not occur with the bound in 5..4.. since Ti is fixed; this simplifies the training procedure of the neural network learning the score and contributes to the stability of the convergence result. At the same time, this further pushes the observation by Chen et al.] (2023b) that "sampling is as easy as learning the score", in the sense that knowledge of the score VlggP; for all times suffices for efficient sampling. Indeed, Theorem 5.1 shows the stronger result that, for sunaausuannsi distributions, knowledge of the score on a fized finite time interval actually enough.
Finally, when looking at the dependence on the desired accuracy e, the bound of removes a factor of log?(3 (?) in the number of steps required by the algorithm.
12

---

Published in Transactions on Machine Learning Research (05/2024)
6 Concluding remarks
In this work, give convergence guarantees for variant of the popular predictor-correcto approach in the context of score- based generative modeling. Our analysis provides bounds that (i) require running the forward process only for a fixed time Ti, which does not depend on the final sampling accuracy, (ii) make minimal assumptions on the data (subgaussianity of the norm), (ii) exhibit a mild logarithmic dependence on the input dimension and on the tails of the data distribution, and (tv) allow for realistic assumptions on the score estimation, in the form of control on the standard L loss integrated over the finite time Tí.
Acknowledgement
Francesco Pedrotti and Jan Maas acknowledge support by the Austrian Science Fund (FWF) project 10.55776/F65. Marco Mondelli acknowledges support by the 2019 Lopez- prize.
References
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient flows in metric spaces and in the space of probability measures. Basel: Birkhäuser, 2nd ed. edition, 2008. ISBN 978-3-7643-8721-1.
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markou diffuusion operators, volume 348 of Grundlchren Math. Wiss. Cham: Springer, 2014. ISBN 978-3-319-00226-2; 978-3-319- 00227-9. doi:
Jean-Baptiste Bardet, Nathaäl Gozlan, Florent Malrieu, and Pierre-André Zitt. Functional inequalities for Gaussian convolutions of compactly supported measures: Explicit bounds and dimension dependence. Bernoulli, 24(1):333 353, 2018. ISSN 1350-7265. doi: 10.3150/16-BEJST7 URL https://doi.org// 3150/16-BEJB8
Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Linear convergence bounds for diffusion models via stochastic localization. arXio preprint arXim:2308.0366 2023.
Adam Block, Youssef Mroueh, and Alexander Rakhlin. Generative modeling with denoising auto-encoders and Langevin sampling. arXiv preprint arXiv:221 01122211.1999 1.01916, 2022.
Valentin De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. Transac- tions on Machine Learning Research, 2022. ISSN 2835-8856. URL https:///penrreiier http:/ppprrrrrieei.eeeffrrrrrooo net
MrK5aXo3gB
Valentin De Bortoli, James Thornton, Jeremy Heng, and Arnaud Doucet. Diffusson Schrödinger bridge with applications to score-based generative modeling. In Advances in Neural Information Processing Systems (NeurIPS). 2021.
Hin Chen, Sinho Chewi, and Jonathan Niles-Weod. Dimension-free log-Sobolev inequalities for mixture distributions. Journal of Functional Analysis, 281(11):109236, 2021a.
Hongrui Chen, Holden Loc, and Jianfeng Lu. Improved analysis of score-basod gencrative modcling: User- friendly bounds under minimal smoothness assumptions. arXiv preprint xxXi::2211.01166 2022a.
Nanxin Chen, Yu Zhang, Heiga Zen, Ron J. Weiss, Mohammad Norouzi, and William Chan. Wavegrad: Estimating gradients for waveform generation. Tn International Conference on Learning Representations (ICLR), 2021b. URL httpe:://openreviee.nn http://ewwwe.e.eeee.ooocoeetttta
Sitan Chen, Sinho Chewi, Holden Lee, Yuanzii Li, Jianfeng Lu, and Adil Salim. The probability flow ode is provably fast. arXiv preprint WxXi:2305.11798 2023a.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru Zhang. Sampling as casy as learning the score: theory for diffusion models with minimal data assumptions. In International Conference on Learning Representations (ICLR), 2023b. URL httpss://ppeereeiiee httt:::://ppaeeeeeeeeeee//rrrrrr
13

---

Published in Transactions on Machine Learning Research (05/2024)
Tianrong Chen, Guan-Horng Liu, and Evangelos Theodorou. Likelihood training of Schrödinger bridge using forward-backward SDFs theory. In International Conference Learning Regresentations (TCIR), 2022b.
URL https://openrevier http://wwwweeeeeeeeeooooorooonoo .ett:/orrummmittioooocEEE..
Giovanni Conforti, Alain Durmus, and Marta Gentiloni Silveri. Score diffusion models without early stopping: finite fisher information all you need. arviv preprint Xiv:2300 12240, 2023.
Florincl-Alin Croitoru, Vlad Hondru, Radu Tudor Ionescu, and Mubarak Shah. Diffusion models in vision: A survey. IEEE Transactions on Pallern Analysis and Machine Intelligence, 2023.
Arnak S. Dalalyan and Avetik Karagulyan. User-friendly guarantees for the langevin monte carlo with inaccurate gradient. Stochastic Processes and their Applicntions, 129(12):5278 5311, 2019. ISSN 0304- 4149. doi: httpp::/doo..rrg/ 10.10////1000001///.////o////./ http://..p............ URL httpp::/www..cieneeet... atticle/pp1/S00044444888444
com/science/
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. In Advances in Neurul Information Processing Systems (NeurIPS), 2021.
Ronen Eldan. Thin shell implies spectral gap up to polylog via stochastic localization scheme. Geomelric and Functional Analysis, 23(2):532 2092255992220 2013.
Giulio Franzese, Simone Rossi, Lixuan Yang, Alessandro Finamore, Dario Rossi, Manrizio Filippone, and Pietro Michiardi. How much is enough? A study on diffusion times in score-based generative models. En- Iropy, (4), 2023. ISSN 1099-4300. doi: 10.3390/e25040633. URL https://wwwx mdpi cttppcp.co//01994300000 25/4/633
N. Gozlan and C. Léonard. Transport inequalities. survey. Markov Process. Relat. Fields, 16(4):635-733 736, 2010. ISSN 1024-2953.
Jonathan Ho, Ajay Jain, and Picter Abbecl. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems (NewrIPS), 2020.
Chi Jin, Pranceth Netrapalli, Rong Ge, Sham M Kakade, and Michael Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. ar preprint arXis: 037603736, 2019.
Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. In International Conference on Learning Representations (TCLR), 2021. URL https://openreviers new/ aaadd=aa-xKKymmma
Dohyun Kwon, Ying Fan, and Kangwook Loc. Score-basod generative modcling secretly minimizes the Wasserstein distance. In Advances in Neural Information Processing Systems (NeurIPS). 2022.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. In Advances in Newral Information Processing Systems (NewrIPS), 2022. URL https://
openreview. wwwpeeviwwwweeeeeee.eee
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In Shipra Agrawal and Francesco Orabona (eds.), Proceedings of The 34th International Conference on Algorithmiic Learning Theory, volume 201 of Proceedings of Machine Learning Research. pp. 946 985. PMLR, 2023. URL httpss:/pproceecinggs mlr. presss/200//eee2a. html
Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Towards faster non-asymptotic convergence for diffusion- based generative models. arXiv preprint arXiv:2306.0920 09251, 2023.
Cheng Lu, Yuhao Zhou, Fan Bao, Jianfci Chen, Chongxuan Li, and Jun Zhu. DPM-solver: A fast ODE solver for diffuusion probabilistic model sampling in around 10 steps. In Advances in Neural Information Processing Systems (NearIPS), 2022. URL httpps://opaarevien net net/forum?idee httt//orrumiddeehaaaaiPPP
Andrea Montanari. Sampling, diffusions, and stochastic localization. Xiv preprint or Xiv: 10000.0000000 2023.
14

---

Published in Transactions on Machine Learning Research (05/2024)
F. Otto and C. Villani. Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality. J. Funct. Anal., (73(2):361-400) 2000. ISSN 0022-1236. doi: 10. (0.1006/Jaan.200..c
Jakiw Pidstrigach. Score-based generative models detect manifolds. In Advances in Neural In Information Processing Systems (NeurIPS), 2022. URL https:://ppnrrevie http:pppwwwweooeeeeeccooooooaaaa
Vadim Popov, Ivan Vovk, Vladimir Gogoryan, Tasnima Sadekova, and Mikhail A. Kudinov. Grad-tts: A diffusion probabilistic model for text-to-spoech. In International Conference on Machine Learning (ICML), 2021.
Yuyang Shi, Valentin De Bortoli, George Deligiannidis, and Arnaud Doucet. Conditional simulation using diffusion Schrödinger bridges. In Uncerlainly in Artificial Intelligence (UAT), 2022. URL https://
Jascha Sohk-Dicks,ein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference Machine Learning (ICML), 2015.
Ki-Ung Song. Applying regularized Schrödinger-bridgg-bass stochastic process in generative modeling.
arXiv preprint 220: 07131, 2022.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In Advances in Newral Information Processing Systems (NeurIPS), 2019.
Yang Song and Stefano Ermon. Improved techniques for training score-based generative models. In Advances in Neural Information Processing Systems (NeurIPS), 2020. URL https///rrrpccccdggssoo neurpss.s....rrrr.........
paper happpp/aaappppo/1///222261111111
Yang Song, Sahaj Garg, Jiaxin Shi, and Stefano Ermon. Sliced score matching: A scalable approach to
density and score estimation. In Uncertainty in Artificial Intelligence Conference (UAI), 2020.
Yang Song, Conor Durkan, lain Murray, and Stefano Ermon. Maximum likelihood training of scsre-based diffusion models. In Advonces in Neural Information Processing Systems (NeurIPS), 2021a.
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations (ICLR), 2021b. URL httpa////ppppeeeeeeeeeeerrrrrrre
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algorithm: Tsoperime- try suffices. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Roman Vershynin. High Dimensional Probability. Cambridge University Press, Cambridge, 2018. ISBN 978-1-107-16061-5. URL https://ww.nnthh math. uci.
html
Códric Villani. Topics in optimal transportation, volume 58 of Grad. Stud. Math. Providence, RI: American Mathematical Society (AMS), 2003. ISBN 0-8218-3312-X.
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Pascal Vincent. A connection between score matching and denoising autoencoders. Neural Computation, 23 (7):1661-1674, 2011. doi: 10.1162/NECO 00142.
Feng-Yu Yu Wang and Jian Wang. Functional inequalities for convolution probability measures. Ann. Inst. Henri Poincaré, Probab. Stat., 52(2):898 914, 2016. ISSN 0246-0203. doi: 10.1214/14AAIHP539
Ling Yang, Zhilong Zhang, Yang Song, Shenda Hong, Runsheng Xu, Yue Zhao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang. Diffusion models: A comprchensive survey of methods and applications. arXiv preprint Xiv:22200 007966, 2023.
Kaylee Yingxi Yang and Andre Wibisono. Convergence of the inexact Langevin algorithm and score-basod generative models in KL divergence. arzie preprint arXiv:2211.00 11.01112,. 2023.
15

---

Published in Transactions on Machine Learning Research (05/2024)
Qinsheng Zhang and Yongxin Chen. Fast sampling of diffusion models with exponential integrator. In International Conference on Learning Representations (TCLR), 2023. URL https://oppnreviii net/ (orumiid=Loek/hft446
16

---

Published in Transactions on Machine Learning Research (05/2024)
A
Additional and auxiliary lemmas
Notation
x2 e
Recall that a scalar random variable is subgaussian if there exists constant K 0 such that E
S 2.
Its subgaussian norm is defined by || == inf { 0: E e < < Furthermore, an -allude random
variable is said to be norn-subgaussian its euclidean norm || is subgaussian. We define || |sg == |||| voo Note that both I1-Iles and Illss are norms and, if Supp X B(0, R) for some radius R 0, then
| ||sG
Vlog(2)
For the convenience of the reader, in the table below we recall the relevant notation used in the paper.
Notation
Mcaning
||| Wz
Subgaussian norm of random variable
X ||sa = |||| Ill
Subgaussian norm of random vector
P
Target distribution
Pr
Perturbed distribution at time t
Pe
Output distribution of the algorithm
V (o))
Estimator for the score function
(t)
One-sided Lipschitz constant of sa(t,-)
T 2
Early stopping time
Tj > 0
Running time of the forward process (OU)
Ni > 0
Number of steps for simulated reverse process
T2 2 0
Rumning time of inexact Langevin dynamics
N2 2 0
Number of steps for Langevin algorithm
b(t)= Ep.
V log Pt so(t, )11
eeror for the score approximation
1
EMGF
log Bprs
exp
V loggr (T1,
Stronger losses for the score at time T₃
9
EMGF = log Bpr,
exp
| log (T(
1
Auxiliary lemmas
First of all, we recall the following classical properties of the Gaussian distribution.
Lemma A.1. Let Z ~ Then,
1 I 2vdr.
Moreover, Cr.s (Ts,)) 2 for all x E Rdd and 1. 0.
Proof. Without loss of generality, suppose that Z y (i.c. t = 1). Recalling the moment generating function
of the eddistributton we have that, for S c 5 zd < 2,
1
E
(1 2c)
< 2,
2cd
which proves the first claim.
The statement about the log-loooo Sobolev constant is well known (it follows for example from the Bakry Bakry-Emery criterion, cf. Villani 2003 Thm. 9.9) BBkry et. al. (2014)).
17

---

Published in Transactions on Machine Learning Research (05/2024)
Lemma A.2. For all t, we have
dr S
p
ct?
2ct
Proof. As in Vershynin 2018
Prop 2.1.2), we have
leee co² dæ = / ( dx S se-o2
foe
100 22ts
e dx = e a
2cl.
The next lemma provides some useful estimates for norm-subgaussian random vectors (cf. Vershynin (0118 Jin et al. (2019)).
Lemma A.3. Let X ~ p be a norm-subgaussian random vector. The following hold:
(1) For all 2 0,
2
X[ 8) 2e
1x1
(A.1)
Moreover,
E
| 12]
S X Isc.
(A.2)
(ii For any L 0 and 0 <<<<
1x
J
e| dp(x) S2 1+ 1 - x
cl XI
1x lsa
(iii) For any L > 0,
J B
|
62a
dp(x)) < 2L +
L
Proof.
( As in Vershynin
2018
Prop. 2.5.2), we have
.2 ixiiaa
1x
P(] 2 8) = P
2 e ixiga
Se
E
e
< 2e
xxx 1x
where the first inequality follows from Markov inequality and the second uses the definition of norm-subgaussianity. Using AAI)) we obtain
B 1
P(IXI 2 k)dk 22 f/ -ixiga dk = 2|
which proves A.2
(i) Let Y x (1X]12 Then, S |||1 p(x)ddx(ddrr) B(Y]. Moreover, the following chain of
inequalities holds:
E Y
PPY 2 k)) dk
1 111X1122
log k
< eL?
P(| 2 L)
dk l k " dk
>
Jees
12 < cl
+2
- 1. [
2 1
x||
12
where the third line follows from point
18

---

Published in Transactions on Machine Learning Research (05/2024)
(ii) Similarly to the proof of the previous point, let Y || Then,
BOOLY p = Bly]
Moreover, the following chain inequalities holds:
|| / P(Y 2 k) dk
S L. P(I 2 L) +
P[ 2 k) dk
62
22
$ 2Le IX +2
Ixl
dk
|
2L
1x1ga
+
II xx
|
2L
1x
where the second inequality follows from point i and the third one follows from Lemma A.2
The next lemma will be useful to find an upper bound for eMGP in terms of b(Ti); the corresponding lower bound is easy and follows immediately from Jensen's inequality.
Lemma A.4. Consider a random variable F such that 0 < F S M for some M > 0. Then,
B[e²] 1 ME(F).
Proof. By the mean value theorem, for 2 0 we have the bound e* < + ze". Hence, cf < eM.. from which the conclusion follows by taking the expectation on both sides.
B Proof of Theorem 4.1
We begin with the proof of Proposition 4.3 which gives Wy-estimates for the reverse process Y, satisfying
4.2 Its time-marginals di = law (Y;) satisfy the continuity equation
q0 law (Zzz),
(B.1)
0.g. V (x)( 60 x))] 0.
Here and below we use the symbol (.) to denote the time-reversal of a function on [0, Ti), e.g., P: = PT-t-
(ott, :) = (o .), B(t) b(T1 t), (1) = (T, t).
Our goal is to obtain an upper bound for W2(Pr. -),-), where (f:), satisfies the Fokker-Planck equation
Åo PT.
(B.2)
a,p,(x) + (x) + Vogg 0.
Following Kwon et al. (202)), we apply the following well-known formula for the derivative of the Wasserstein distance between two curves of probability measures, cf. Ambrosio et al. (2008) Thm. 8.4.7, Rink. 8.4.8), Villani 2009 Thm. 23.9).
Theorem B. Let (Pa(R"), W2) be the space of probabilily mensures Rd with finite second moment equipped with the Wasserstein distance W2. Consider two weakly continuous curves (ue)e, (ve) in P2(Rd) that solve the continuity equations
Sepe + V. (Eepe) =0, Oer + V (Erv)) 0.
19

---

Published in Transactions on Machine Learning Research (05/2024)
Suppose moreover that, for some 0 I t 12 00, we have
(ue ||E:|11] Ev ||E&|] ( dt oc.
Then, denoting by ne an optimal coupling for W2(He, vo), we have
d (14. Un) B [xx - y) - Ex())),
dt 2
for a.e. te (2),
To apply the theorem above and deduce differential inequality, first need to prove the following result. Lemma B.2. For 0 < < x0, we have
Eqg [|| + So xt(1)) < 20,
(B.3)
Epa [| + V log (z)) co.
(B.4)
Hence, the curves (4)) and (Pe)ce(O.TI-)) are absolutely continuous in (P2(R.), W2).
Proof. We start with
B.4 Recall first that for t t> 0,
DKL (x) = Ip((p) Eps log dp: dy
|
Ep, |
V log (z))
dt
where, with abuse of notation, we have identified the probability measures pt, with their densities with respect to the Lebesgue measure. Integrating this incquality between т and Ti we find
[ En || + + (=)) dt DPr (1>) oc,
where we used non-negativity of the KL-divergence and that DRL. (1 < co, cf. Villani 2003 The conclusion follows by a change of variable in the integral.
Ruk. 9.4).
As for [B3 we arguc as the proof of Villani (2099] Thm. 23.9). Note first that do E P2 (R))) since Pr. E (2(( and W2(10,PT) < cc. Let (x(x)) denote the velocity field vx()) = x + (p x). Since Ti is finite, it follows from our assumption (A1) in Section 4 that there exists a constant C
such that [=)]l < C(1 ||>|]) for all R= and 0 S S Tj. The Lipschitz assumption on sø in our assumption (AI) in Section ! also implics that is Lipschitz. Therefore, there exists unique trajectory map Tú: Rd R
associated to the continuity equation B.1 i.e.,
To(x) = (T)(x) = (T)()))
Then, by the conservation of mass formula VVillani 2009 pushforward of measure by map. Notice that, for all 0 < t < Ti,
have q: (Ti)49 where # denotes the
[TT(3)] x [ (TT())))))a ||||||
CT C ( [TT(())]dd..
Therefore, by the integral version of Gronwall's lemma applied the continuous function +-+ [x]]())]|, we deduce that
[T(x)l ([K=) CT.
20

---

Published in Transactions on Machine Learning Research (05/2024)
It follows that, for 0 sts Ti,
/ (1|=|] + gd
= [TT - 2
= C 00;
Rd
thus the second moment of gr is uniformly bounded by C for S Ti. Replacing Ô with Ö + 1, we note that also the first moment uniformly bounded by C. Therefore, recalling that || 80(1, x)]] [[=)]=))]|| 2 C(1 + ||=]),, we obtain the following bound, for all <
Byg [||= + so(1, < C(1 + E, [1=]1]]] & C(1 + C)-
This implies the desired estimate B.3
Finally, the absolute contimuity of the curves (e -r] and -r] is an immediate consequence of the bounds B.3 and B.4 in view of Ambrosio et al. (2008 Thm. 8.3.1).
Proof of Proposition 4-3 Thanks to Lemma B.2 we can apply Theorem B.1 Let me be an optimal coupling
in W2 for Pr and qo so that by definition we have Ex, [|| - y/l²] W (Pr 4)) Then, we deduce that, for 8.e. E [0, Ti - -]
d
W (ft. (t))
dt
= -E, - y) (x - v)1 E., [r y) (V Voloog (.()))))))))))))))(() (t, (t,t.t)) y))l
-W 41) + Em,,(( - v) (6. (t, [x y) (V log - (t,
I W: (p:. qt) + Et) -||~ + E,, ||| u VE,, (: - so [
+ (t) W (f:. (r) + ((:: 4t)
From this we doduce the differential incquality
dt W2(De. & Lo(t) W2 [1+ + Vb(t).
We can solve this differential inequality by introducing the auxiliary function I(r,t) exp t + J L,(rdrr), which satisfies
T(T, ((r,))((r,t) I(T,1), T(t,t)=1, and d ((r,t)= (.)
(B.5)
dt
Combining the latter identity with the differential inequality above, we find
[T(TL, - t)e ai) s STTT, (t)Wa(ee)))((ea)))) - -t)/b(1).
for a.e. L. Since the curve - [(T,1) is Lipschitz by (A)) in Section 4 it is also absolutely continuous. Moreover, the triangle inequality for W2 yields
Wa(fe, W2(Ps, 4-)l
|W2 gr) W2 4x) + (2((e, qs) - Wa(Ds.
W2(u, qs) W2(Pr, P.).
Using the absolute continuity of Pe, in (P2(R))) W2) (cf. Lemma B.2 we deduce that + W2(Pe, qt) is absolutely contimuous too on j0, Ti - T]. Therefore, also the function
1 [T1, Ti ()
is absolutely continuous on [0 r]. Hence, we can apply the second fundamental theorem of calculus for the Lebesgue integral and integrate the differential inequality between and Ti r. Doing this gives
(o.)))/(r-n------- -n-r) & Wa(Pn, 9o) 1/-T I(Ti,T Ti t) /(()dtt.
TI-T
(TT,,)
21

---

Published in Transactions on Machine Learning Research (05/2024)
Using the properties of I from
B.5 we find
W2(Pr, -n-r) s [(T,Ti)We(Pn, 20) f TI- / b(t)dt,
j I[r,Ti -
which yields the desired expression afler change of variables 1' := Ti -
We now prove Lemma 1.4 which gives well-known Hölder continuity bound in Wasserstein distance for the Uhlenbeck flow.
Proof of Lemma 4-4 Let X be a random variable with law p, and let be Z be a standard Gaussian random variable that is independent of X. Then X, == e + v e 2 has law Pr- Using independence, we obtain
W x = E [(1 x X V1- 21²]
(1-e 2 + (1- - c " [( S 2rd,
which implics the result.
As discussed in Section 4.1 to establish fast convergence of the approximate Langevin dynamics in 4.1 wC need quantitative estimate for the log-Sobolev constant of pT,, which is provided in the next result. flow starting from norm-subgaussian
Lemma B.3. Let (pe)12o be the law of the random vector X. Then, Pr salisfies tog-Sobolev inequalily with constand.
CLs(p)) 2 1 X| S 21
for all > to log(1 (l)))))
Consequently, for any 5 E (0, 1), the log-Sobolev constant of pt satisfies Cis(p:) 1 whenever max (fo, log([12|||X) (os.))).
The proof is based on the following recent result from Chen et al. 2021a Thm. 2), which gives an estimate for the log-So log-Sobolev constant of Gaussian convolutions of sub- Gab-Gasssian distributions.
Theorem B.4. Let μ be a probabilily measure and a, Csa be such that
[ " - p(dx)u(ddz)) S CsG-
(B.6)
For all t > 0², the measure μ * " satisfies a tog-Sobolev inequality with the constant
[3 1- - Caaa
[ 1 1-2 log OSc ))
Cislu* xx) 7)
(B.7)
Proof of Lemma
B.3 Note that pt is the law of e + - with X and Z y independent.
Consequently, Pt A4 m1-e-e, where Me denotes the law of - Suppose now that 1 + 4 10c < 2
and define a = /2e x|]xI|]] Since - -e- 20² > O, we may proceed as in Chen et al. 2021a and write
Rmk. 3)
Pi #4 2/20 -/-e-22 2
(B.8)
We claim that be satisfics the assumption of Theorem
B.4 with OsG = 4 and a defined above. Indeed,
J Le
1=-='12 .2 (edd)))((dz)5
J
(e(dz))((dzz)
(B.9)
( é "ag ue(dx) 44
22

---

Published in Transactions on Machine Learning Research (05/2024)
where the last step uses definition of Therefore, application of Theorem B.4 yields
C1S(14 * 7202) 2 [6 C) + log [)] 2 [8662]
Using the subadditivity of CTS under convolution (cf. Wang & Wang 2016
Prop. 1.1)) and the estimate
CLs(N--->~22r)) 2 Cis(7) from Lemma A.1 we obtain using B.8
CLS(Pi) 2 CLS 720z) + C
860 2 + 1 1]_
which proves the first part the statement.
The second part follows immediately.
Proof of Lemma 4-8 We proceed in two steps. Suppose first that p = 6g for some x E Rd. Then = 7e-t2,00 is Gaussian with ot == e 21, An explicit calculation gives
d (=-2 ||] + to, log - oe togoo o01)
DKL (> Te (x,0)) 20,
(B.10)
the general case where p Rd has finite second moment, we condition on the initial value using the disintegration formula
pe(dy) S 2e- p(dx).
Using this formula, we employ the joint convexity of the KL-divergence and B.10 to obtain
( 7 dd((x) gd - { DKL(>) To-toan) dp(x)= = M2(p))
(r) (xll/se Yx0 dp(x) = DKL
/
DKL(y (1p:) DKL
Yn-on dp(x)
Rd
e 21 t0, +1
RR
20,
where M2(p) = J || dp(x).
For the second claim, we use the scalar inequalities rlogr + S (r - 1)2 for r 2 0. Thus, whenever e 2t < 21 we have
d M2(p) 2t +
11) xa) (Ma()) d
DKL(TllPn) S 2(1 e-2
This implies the desired result.
We are now ready to prove Theorem
Proof of Theorem 4.1 Note first that, by the triangle inequality for W2, we have
Wa(p. po) = W2(p.97 S W2(p.Pt) + Wo(Pr, (7 -7)
The first term can be estimated with Lemma 4.4 the second with Proposition gives
4.3
Plugging in these estimates
[" T
(p, s /3dr + 1, (TT))
b(t)
Therefore, to prove
4.3 suffices to show that
2
01-9722
We(pn, go) I V
56
+ 2CMGF
23

---

Published in Transactions on Machine Learning Research (05/2024)
To see this, observe that Cis(pn)) 2 - 8 by Lemma B.3 therefore, combine
4.12 with Theorem
1.7 to deduce that
W2(PT: 90) S V
2
(7
|| Pe,, )e O14172
+ 20MOF).
Recalling that E | S 2| by of Lemma A.3 we can use the estimate DrL (7 || pT.) from Lemma
1.8 to prove 4.3 application of Cauchy-Schwarz Schwarz inequality then gives [14b. Finally, if we only know
Ti 2 log 2 172 x Be
then can instead estimate (RI(PT, |])) s d
3 again by Lemma 4.8. which
proves our claim in the discussion on the role of T1 after Thcorem 4.1
C Proof of Theorem 4.2
When starting an Ornstein Uhlenbeck flow from norm-subgaussian distribution, the distribution at time Ti will be norm-subgaussian too, and
estimate its norm.
Let (Xt)120 be an Ornstein Uhlenbeck process Lemma C.1.
3.6 slarting from a normn-subgoussia random
vector X. Then, Ti 2 log ||l|ss vd
have
X2x llsa S 3vd.
(C.1)
Proof. Let Z ~ r be independent of X. Then, XT, is equal in law to - 1 Consequently,
|T Ti X v e 27 Z
Se Se " [|]|ss S <3vd.
SG
where in the last inequality we use Lemma A.1 and the choice of Tı.
The following lemma gives an a priori estimate for V Vlog which can be used to correct predictions of s)(T),,) that are far from the ground-truth.
Lemma C.2. Let (pe)ıo be the law of the Ornstein-Uhlenbeer flow starting from norm-subgoussian random vector X with law p. Fix O < 8 < and lake Ti 2 log( 16 E {l....,d} d}, we have
5 [[[ |sa + 1)) Then, for all x E Rd and
-x; - -0,1og (x)) < 2d
(1 + ||=|]).
Proof. Let be the law of T and set o² 12=1- 2-2 By our choice of Tı, we have
8 and - σ²
8 2
le Ti x
SG I
(C.2)
16d
16d
Notice that Pr, 11 Yoz. Therefore, for all Rd, we can write in Bardet al. 2018
Pn (x) = / (2mo² exp
( 2||2
|| [_1x=-2
pldz) = (2TO²) - exp (- (-
||x:11
+ W (o(c)))
)
202
20
Rdd
where we set
I. ||2113
Wx(x)= -
exp
u(dz).
jdd
o2
20
Taking the logarithm and differentiating, we find that
0, logoppn, pn (x) =
o2 22 -0,Woxx)
(C.3)
24

---

Published in Transactions on Machine Learning Research (05/2024)
Observe now that
Sealzd exp exp((> x= 03
|| jllz))
= Skal 12al2i172,0 (2) (z) fRo Yo (z))((z)
o² o²0,Wo
2n
(C.4)
Size exp
Lall pl(d))
where, with some abuse of notation, Ya, denotes the density of gaussian (2x tla). We claim that
| (2) <
8(1 + |=|l)
/ (z)22))
(C.5)
4d
which we prove later. Using this bound in C.4 deduce that
8(1 + |
0 W. (x)) v
4d
Inserting this estimate in C.3 it follows using C.2 that
o² mi
8(1 1==|))
1 1
||||
8
2
6
0- log (I)
(1
4d
0²
16d
4d
2d
where in the last inequality used that
8
8
6
+
+
S
2²
16d
4d
1
27i
256
4
d
1
12256
3d
2d'
since 0 < 8 < 1 and Tj 2 log(16) This the desired estimate.
Tt remains to prove C.5
To do so, we start by writing
| Ya (=)u(d=) 2
/ B(o.s)) 20.02 (=)
(||=|| + 8)2
2 (2TT²)) exp
P (B))))))
(C.6)
20
(||==|| + 8)2
(2ma²)- exp
[1 2exp(-2260
20²
where the last step we use
(i) of Lemma A.3 and the estimate ||e Ti |lsc I 1od S h/ which holds
5
view of (C.2p. We now split the integral in the left-hand side of (C.5) into two terms that we will estimate separately. Set r d(++|
Then,
8d
8(1 [ell)
/ Ta, (z)
(2) Sr
Y0.02 (z)
B(O.r)
B(0,r)
8d
Therefore, recalling C.6 to conclude the proof of C.5 it is enough to show that
S B
2 Ne (=) 8(1 + ||]|]
[1
2 2exp(-22 (256)) eex
(- [||=|] 5)2
8d
20
To do this, we write
(2 / J Ta, (2))(d)) <
[22])((d2)
B(U,r)
82
256d
2r
exp
256dP
82
28
(1 |x]||)
8
1
exp
(4411 + [==1))))
32d
+
||
36
(1
+ ||]||]
exp
(44(1
|k=l1)*)
8d
25

---

Published in Transactions on Machine Learning Research (05/2024)
where in the second line we have used iiti) of Lemma A.3. [1 2exp(-256)) we have
As o² 2 by C.2 8 < 1, and exp(-44)= S
[||=|| + 8)2
3exp(-4(11 |==1)² & [1 2exp(-2500 exp
20²
for all which concludes the proof.
We are now ready to move to the proof of Theorem 4.2
Proof of Theorem 4.2 Notice that, thanks to Lemma
C.2 and to our definition of se, for all x E R we have
82
V log (x) {0(+)]1 <
|
(C.7)
d
VVlogrr Pr, (I:) -0()))
pr (x) so(T1.
(C.8)
As log(1 +)) S it suffices to show that
J exp exp (BIVVlllggr (1) 5o(x))1 dpp, (x) +c..
Now let us fix radius R O, whose value we specify later. We will show that, for an appropriate choice of R 0,
JAS..p exp (opplllloogpmmoo) =0(2))1²) dpt, (x) (z) s 2'
(C.9)
and
exp (t) 50(1))1²) dpni (x) $ 11 2
(C.10)
B(O,R)
thus concluding the proof.
First, we consider
C.9
Notice that
82
exp
B V log (z) - -x0())1 $ exp
B
(1
+ 1|x:1))
d
2,32
2,552
exp
exp
||=:1|
d
4,82
2,38
exp
|
d
- 2 exp
18d
Here, for the first inequality we use (C.7; for the third inequality, we use that e* < 1 2s for 0 < s < 1 and the condition on 3; the condition on B is used again for the last inequality. Therefore, we deduce that
[ J exp
/ V (z) =x())))) dpr, (x) <
exp 18d |x/(3 dpr, (x)
B(O,
< 8e
184,
where for the last inequality use of Lemma A.3 and Lemma
C.1
Therefore, picking
16
R
18d
readily gives
C.9
With this choice of R, consider
C.10 Let us define the random variable
F = 3 log (Xr,) So (Xn,
1 {I Xm [|sn]'
26

---

Published in Transactions on Machine Learning Research (05/2024)
where X1, Pzi as usual. We note that
J exp B V soll" =601')pm (x)dæ Ele7].
It remains to estimate B|e"), which we will do using Lemma A.4 To show that F satisfics the conditions of Lemma A.4 we check its boundedness. Using [C7] and the constraint on B we obtain
16 = M.
H F
R
+
36336 log
18d
Furthermore, using
C.8 and 4.7
we can estimate E[F] by
B|F] s 3E pT
Voggr - -o((T,
< - 1+3688
34
Notice also that
edd e Tha 163668
36,82
< 16e -366/5 36,98
where we used once more the constraint on B. We can now apply Lemma A.4 to deduce that
16e is
E E[e²] - I [F[F] S
34
2
which concludes the proof.
Proof of Theorem 5.1
The first step of the argument in the proof of Theorem 5.1 consists in giving upper bound for TV po) which allows to control separately the errors originating from (i) taking ZN, as an approximate sample from pr. and (ii) approximating the reverse process with a discretized scheme and with an L accurate score. To do so, we follow the strategy of Chen el al. (2023b) 2022a). Let us denote by S the Markov kernel which associates a probability mcasure j the law of the random variable Un, where (Ut). satisfies the true backward SDE initialised at p, i.e.,
{ Up ~ μ.,
dú, U,dt + 2V log log + V2dB
In particular, we have Pr; S. Similarly, we denote by S the Markov kernel which corresponds to following the approximate reverse process in 5.2 initialised at μ. particular, we have pa = .NN5 (recall that σx law(Zz)) The following chain of inequalities holds:
TV(, S,NN.))
S TV(P PT, + S. SN
(D.I)
V DRL PT. s pT. IV(PT,
V DKL pT,
pr, $) + / DRI(aN, (PT)).
In the above, we have used the triangle incquality for the total variation distance, Pinsker's incquality and the data-po processin inequality. This achieves the desired decomposition, so that we can study the two processes
5.1
5.2 separately.
27

---

Published in Transactions on Machine Learning Research (05/2024)
Convergence of inexact Langevin algorithm.
To control the term PKI(aN, prr), need to study convergence of the process [5.1 This is done by adapting the results of Yingxi Yang & Wibisono (2023) to the case of decaying step size. In particular, we prove the following
1 (A2) hold, pick 0 ō 2: Ti log 2+ 172 1 + 1 and suppose
Proposition D.1.
Let Assumption
in addition that v log Pr, is -=-ppscciitz and that (o is L2- T2-Lipschitz, with I1, La 2 1. Then, for the inezact Langevin algorithm
5.1 with step sizes has 24I, L2tt 11"
we have that
L
dL3
DRI(ON, (PT))
+
+ EMGF,
(D.2)
N₂ +
N₂ +
where ÉMGI is defined in 5.3
The proof is postponed to the end of this section. Using Proposition D.1 gives the desired upper bound for the second error term in (D.1), when using a decaying step size. For the analogous result with a constant step size, (Yingxi Yang & Wibisono 2023 Thm. 2).
Analysis of the reverse process.
It remains to give upper bound for the error due the discretization and approximation of the score in the reverse process, corresponding to the first term in the right hand side of (D.1). This has been analysed in number of recent works, under different assumptions. We recall in particular the following results, proved
in Chen el al. 2022a) building on the Girsanov framework developed in Chen et al. (022b))
Lemma D.2. Suppose that p has finile second moment and that V log is TA TA-Tápschilz for LE [0, Ti] with Tí, Li 2 1. Then, choosing constant step size h Tn
< gives
DKu (p
pr s)
DKu pr, S pr, S JsM + aT?T?
N1
Inserting this bound in D.1 concludes the proof of Theorem 5.1
Proof of Proposition D.1
The proof of Proposition D.1 is based on the results of Yingxi Yang & Wibisono 2023). and particular on Lemma 6 therein, which upper bounds the relative entropy after one step of the inexact Langevin algorithm and which we recall below.
Lemma D.3 (Lemmn of Yingxi Yang & Wibisono 2023 Let vo be probability measures with full support that admit densities with respect to the Lebesgue measure. Suppose that μ satisfies a log-Sobolev incquality and let K S CLs(p). In addition, suppose that so an approrimation of V log u, that so is Lz-Lipschitz and that V log y is L1 L-iisschitzz with L1, 2 1. Set Zo vo and
7 70 + h + 2
where ~ NNO,, Ia) is independent of Zo and 0 < min have
K
11
Then, letting vs = law (Zi), we
12L, Ln 2x
* DRi(u m) & - Dxz( + I4 + +24d1322 + h log E, ||50 V Voog 11l
With this lemma at hand, prove Proposition
D.1
28

---

Published in Transactions on Machine Learning Research (05/2024)
Proof of Proposition D.1
By the choice of Ti, have that Cis(pn) 2 1 - 8 2 2-2 In particular, the step
sizes k==) N2-1 defined by
ha 24T, L2 + 16
satisfy the constraint in Lemma D.3 with μ pT₁ and 59 (T), )) We can therefore apply the lemma to deduce that, after each step of the inexact Langevin algorithm,
DKL pT, - the DKL (1) 30dT hGEAG
for 0 S N2 1. By iterating the above result we find that
DKI Iln)) Se- Ei=0
(30dL3h7 h,EMGF) e 2oj=eti hy
(D.3)
where we have also used that (o ll Pr,) S S by Lemma 4.8 Now, notice that, for 0 S j S k, have the bound
1+1
24I L2 + k+2
dr 16 log
(D.4)
24I, L2 +
2+1
24I, L2
3+1
16
and
hx+1
h1
24L1L2 +
1
1
16
hx
ho
24L, L2 +
Using this in
D.3
find that
24L Lg +
2
24I, L2 + 16
i+2
DKI(ONz 1
16
(30dL3h + hGēMGF)
24 +
Not1
24L L2 + N++1
16
1=0
16
No-1
1 h2
N₂
hi lN22
+ 30dL2
Σ
+ MMF
+ 381L, La
N2
h;+1
1=0
i=0
2
+ 120dL3Ng
+ 2ēMGF
N₂
(D.5)
+ 3841, La
N₂
24L, L2 +
N₂ 16
24L, L2 + 16
N₂
dL2
+ 3072070
32F
+ 38IL,
N₂
L L
dL3
+
+ ÊMGF
N2 +
N₂ +1
This concludes the proof of the proposition.
29


Reviews:
[{"review_id": "8se5cUAB9A", "reviewer": "Reviewer_Qg7R", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Introduces a novel prediction-correction scheme improving convergence in score-based generative models.\n2. The paper Offers theoretical guarantees for accuracy  with minimal assumptions on the data. The theoretical guarantees depend explicity on the constants of the problem: input dimension,  subgaussian norm of the target distribution, etc.\n3. Addresses computational efficiency, making it more feasible for practical applications.\n4. Includes comparative analysis with previous methods, highlighting its advancements and  contributes to the theoretical understanding of the dynamics in generative modeling.\n\nWeaknesses:\n1. Theoretical analysis might not fully account for all practical scenarios and data distributions. Some assumptions are but some assumptions are rather ad-hoc and not sufficiently discussed. Is it reasonable to assume, for example, that the data are \"norm-sub Gaussian\"? and if that's the case [after all, all variables are bounded] what could be the value of this norm for imagenet, for example?\n2. I'm not sure the paper adds anything to our existing understanding of the problem. The algorithms presented are well known, so only the analysis can be considered original. The analysis itself repeats many elements already known, and so the contribution is quite incremental [it \"complements\" a set of known results rather than making a decisive contribution to the subject].\n3. I haven't been able to study all the proofs in detail, but it seems to me that the paper contains errors - missing assumptions. I have some doubts on the statement and the proof of Proposition D.1 which is based on a Lemma 6 of Yang and Wisibono - Some of the assumptions of Lemma 6 are not mentioned - in particular, one of the assumption in Lemma 6 is \n\"Assumption 5 ( $L^{\\infty}$ error assumption). The error of score estimator $s(x)$ has finite $L^{\\infty}$ norm at every $x$, i.e.\n$$\nM_{\\infty}=\\sup _{x \\in \\mathbb{R}^n}\\|\\nabla \\log \\nu(x)-s(x)\\|<\\infty .\n$$\n\"\nand $M_\\infty$ appears in the bound of Lemma 6. In the Lemma D.3 of the present paper [which is simply presented as a restatement of Lemma 6], this assumption has disappeared and, on the top of that,  the statement of Lemma D.3 differs from the statement of Lemma 6 [the supremum norm has disappeared]", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a novel approach to enhancing score-based generative models (SGMs). In traditional score-based generative modeling, the process involves simulating a diffusion process that gradually adds noise to the data until a simple, known distribution is reached, and then learning to reverse this process to generate data from noise. However, this approach faces challenges because the forward diffusion process is run for a finite time.\n\nThe document proposes a prediction-correction scheme to address these challenges. This method consists of two main steps: prediction, where an inexact Langevin dynamics is used to estimate the final distribution after a finite forward process; and correction, where this estimate is refined to more accurately represent the target distribution. This approach is designed to improve the efficiency and accuracy of the reverse generation process, enabling better convergence properties compared to existing methods.\n\nThe theoretical foundation of the proposed method is analyzed in the paper. It establishes improved convergence guarantees with explicit dependence on the input dimension, the early stopping time, the subgaussian norm of the target distribution, the approximation of the score, under minimal assumptions. These guarantees are significant because they allow for a fixed finite time \\(T_1\\) for the forward process, diverging from the traditional requirement of \\(T_1 \\rightarrow \\infty\\).\n\nMoreover, the paper compares the proposed prediction-correction approach with previous works in the field, highlighting its advantages in terms of theoretical and practical performance. It discusses how the method provides a better trade-off between the precision of score approximation and computational costs, which is crucial for the practical application of SGMs in generating complex data samples.\n\nHence, the paper addresses key limitations in the convergence of traditional score-based methods, offering a more efficient and theoretically sound approach to generating high-quality samples from complex distributions. This work contributes to the theoretical understanding of SGMs but also opens up new possibilities for their application in various domains.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* make a table summarizing all the notations \n* I would have liked the authors to have gone a little further in their work. Let's start with simple examples, such as mixtures of sub-Gaussian laws in high dimensions - starting simply from a mixture of Gaussian, with exact score). It would be interesting to see what the theory tells us about the choice of hyperparameters $T_1$, $T_2$, etc... And it would then be interesting to understand whether the theory at least partially reflects the \"right\" choices of these hyperparameters. \n* There are many completely trivial results at the beginning of the appendix on sub-Gaussian variables. It would be simpler to gather on one page the properties of the sub-Gaussian variables you'll have to use\n* Fix the proof of Proposition D.1 and Lemma D.3", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bGsMM8q7n2", "reviewer": "Reviewer_XHhW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The presented convergence result is new, and the balance between the finite time steps for the two phases -- (i) the inexact Langevin to generate initial values, and (ii) the reverse process -- could be of importance and interest in the machine learning community. This could also provide theoretical guidance for practical implementation.\n\nWeakness: I didn't see any notable flaws. This paper could be enhanced by incorporating additional discussion and interpretations for the theoretical findings, as commented below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work introduces new convergence guarantees for a variant of the popular predictor-corrector approach in score-based generative models. As a theoretical study, its main technical contribution lies in offering convergence guarantees that do not require an infinite time (i.e., $T_1<\\infty$) for the forward process. Moreover, it establishes these guarantees under only minimal and realistic assumptions on the data distribution and score estimation error.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall I find the paper well-written and very clear. I have some questions/comments below.\n\nI think the choice of T2 (and N2 in the discretized case) is crucial for the convergence results, and also useful for practical implementations.  It is better to have a more concrete comment regarding the choice or guidance on T2 in Section 4. Related to this, it would also be useful to comment on the tradeoff between the optimal choice of N1 and N2 from eq (5.4).\n\nFrom Theorem 4.1, it can be seen that we do need $T_2\\to \\infty$ in order to ensure vanishing sampling error. Since large $T_2$ also results in an increased computational complexity of the generation process, I wonder how the authors would comment and compare the complexity of the original diffusion models and the current method via Prediction-Correction.\n\nFrom eq (4.4), will it be possible to comment on the optimum choice of early stopping time $\\tau$? (as there is a clear tradeoff between the first term (increasing function of $\\tau$) and the second term (decreasing function of $\\tau$).", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8BQgmYzgVN", "reviewer": "Reviewer_y515", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, this is a solid contribution and merits acceptance. I only have very minor comments.\n\n**Strengths:**\n\nNovel Approach: The idea to start the reverse process at the output of inexact Langevin is an elegant, intriguing, and novel contribution to the field of generative modeling. The methodology suggests improvements which could potentially have practical implications.\n\nTechnical Rigor: The analysis is thorough and builds on recent theoretical tools introduced for diffusion models, offering strong guarantees under practical assumptions.\n\n**Weaknesses:**\n\nMotivation: The manuscript would benefit from slightly more motivation for the importance of keeping $T_1$ as a fixed time horizon, see below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript presents a novel approach to enhancing the convergence of score-based diffusion models by integrating a predictor-corrector scheme that operates within a fixed finite time horizon, $T_1$. Instead of starting the reverse process at a Gaussian, this scheme proposes to start the reverse process at a sample from the final distribution of the forward process, obtained via Langevin dynamics with estimated score. A significant technical contribution is the derivation of error bounds that vanish as both the discretization step size and the score matching error approach zero, even for the specified fixed time horizon $T_1$. This development is grounded in recent theoretical advancements in diffusion models and maintains polynomial-time guarantees with minimal assumptions, primarily requiring the score function to be accurately learned in $L^2$.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Motivation: Prior results already only required $T_1$ to be logarithmic in problem parameters, which seems quite mild. In light of this, it would be helpful to further discuss the importance of taking $T_1$ fixed, especially since the present work only seems to shave off a $\\log(1/\\epsilon)$ factor in the choice of $T_1$ anyway.\n\nTraining vs. Generation: The paper makes a compelling point that reducing $T_1$ leads to smaller score matching error, which is important for training the diffusion model. But another important aspect is the cost of generation itself, for which the main important quantity is the number of evaluations of the neural network. In this regard, although the proposed algorithm shrinks $T_1$, the corrector steps require additional function evaluations, and it is unclear whether this leads to an overall speed-up for generation. Therefore, it is worth remarking that the main implications of the paper are for training, not for generation.\n\nI find Footnote 2 to be a bit inaccurate: there are general tools, such as weighted CKP inequalities or Wasserstein control via weighted TV, which suggest that control in information divergences is typically stronger than Wasserstein control.\n\nThm. 4.1: please comment on the apparent exponential dependence on the one-sided Lipschitz constant.\n\nLem. A.6: I believe this can be improved by using the Taylor expansion of the exponential, $\\exp(x) \\le 1 + x\\exp(x)$ for any $x \\ge 0$. It is an improvement because it leads to the score matching error only needing to be of size $\\epsilon^{1+O(\\delta^2)}$, not $\\epsilon^{2+O(\\delta^2)}$ (and this seems quite important since the accuracy of learning the score is the least well-understood part of the whole theory).", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work studies a variant of the predictor-corrector method. The key idea is to sample from the final time step distribution via (approx) Langevin dynamics and use this sample to start a standard reverse process instead of drawing it from the stationary distribution, i.e., Gaussian. The main result provides convergence guarantees in Wasserstein distance under realistic assumptions on score estimation.

Overall, this paper offers a novel approach to diffusion models, improving practical performance with strong theoretical guarantees. The methodology of starting the reverse process at the output of inexact Langevin dynamics is innovative. The theoretical analysis is comprehensive, providing strong guarantees under mild/practical assumptions. The reviewers have highlighted the thoroughness of the analysis and its practical implications. Given these strengths, I recommend acceptance. This work is a valuable addition to the literature on diffusion models.
Decision: Accept (poster)