Nearly $d$-Linear Convergence Bounds for Diffusion Models via Stochastic Localization
Authors: Joe Benton
Valentin De Bortoli
Arnaud Doucet
George Deligiannidis
Venue: ICLR 2024 spotlight (2024)
Keywords: diffusion models
score-based generative models
convergence bounds
stochastic localization
Primary area: learning theory
TL;DR: We provide the first convergence bounds for diffusion models assuming only finite second moments of the data distribution and an L2-accurate score estimate, using tools from stochastic localization.

Abstract: Denoising diffusions are a powerful method to generate approximate samples from high-dimensional data distributions. Recent results provide polynomial bounds on their convergence rate, assuming $L^2$-accurate scores. Until now, the tightest bounds were either superlinear in the data dimension or required strong smoothness assumptions. We provide the first convergence bounds which are linear in the data dimension (up to logarithmic factors) assuming only finite second moments of the data distribution. We show that diffusion models require at most $\tilde O(\frac{d \log^2(1/\delta)}{\varepsilon^2})$ steps to approximate an arbitrary distribution on $\mathbb{R}^d$ corrupted with Gaussian noise of variance $\delta$ to within $\varepsilon^2$ in KL divergence. Our proof extends the Girsanov-based methods of previous works. We introduce a refined treatment of the error from discretizing the reverse SDE inspired by stochastic localization.

Published as a conference paper at ICLR 2024
NEARLY d-LINEAR CONVERGENCE BOUNDS FOR DIFFUSION MODELS VIA STOCHASTIC LOCALIZATION
Joe Benton," Valentin De Bortoli Arnaud Doucet, George Deligiannidis"
ABSTRACT
Denoising diffusions are a powerful method to generate approximate samples from high-dimensional data distributions. Recent results provide polynomial bounds on their convergence ratc, assuming L La-acuratee scores. Until now, the tightest bounds were either superlinear in the data dimension required strong smoothness assumptions, We provide the first convergence bounds which are lin- ear in the data dimension (up to logarithmic factors) assuming only finite second moments of the data distribution. We show that diffusion models require at most
(1/6)) steps to approximate an arbitrary distribution on E corrupted with Gaussian noise of variance á to within =² in KL divergence. Our proof extends the Girsanov- based methods of previous works. We introduce refined treatment of the error from discretizing the reverse SDE inspired by stochastic localization.
Ō d log" (1.6))
INTRODUCTION
Denoising diffusion models are a recent advance generative modeling which have produced state-
of-the-art results in many domains (Sohl-Dickstein et al., 2015 Song & Ermon, 2019 Ho et al.) 2020 Song et al. 2021b). including image and text generation Dhhriwal & Nichol 2022 Austin al. 2021 Ramesh et al. [0222] Saharia et al.) (2022), -ext-to-specch synthesis (Popov al. 2021
and molecular structure modeling (Xu et al. 2022] Trippe et al.) 2023] Watson et al. [023 ). De-
noising diffusion models take data samples, corrupt them through the iterated application of noise, and learn to reverse this noising procedure. For data on Rd, we typically use a stochastic differential equation (SDE) as the noising process. Then, learning the reverse process is equivalent learning
the score of the noised distributions (Vincent 2011 Song & Ermon 2019
Song et al.) 2021bb.
Recently, significant progress has been made improving our theoretical understanding of diffu- sion models, including several works which have established polynomial convergence bounds for such models (Chen et al., 2023a d; Lee al., 2023 Li al. 2023). The current state-of-the-ar bound without Lipschitz assumptions on the score of the data distribution is provided by Chen et al.)
2023ap, who show that diffusion models require at most Ó (1.6)))))))) steps to approximate given distribution to within s" in KL divergence, assuming only a finite second moment the target distribution and early stopping time 5. However, Chen et al. (2023a d) suggest that the iteration complexity ought to scale linearly in the data dimension (see e.g. Chen et al. (2023d, Theorem 6)).
In this work, close this gap. We derive the first convergence bounds for diffusion models which are lincar in the data dimension (up to logarithmic factors) without smoothness assumptions. We de- duce that early stopped diffusion model has iteration complexity Ö ddllo" (1/6)) ). Our proof builds on Chen et al.) (2023a who use Girsanov's 's theorem to measure the distance between the true and approximate reverse paths. However, we provide refined treatment of the time discretization error, using techniques from stochastic calculus to derive a differential inequality for the expected differ- ence between the drift terms different times. By bounding the terms of this differential inequality, we achieve tighter bounds on the difference between the true and approximate path measures.
key ingredient in our proof will be Lemma I which allows to perform several calculations ex- plicitly. This result is inspired by stochastic localization (Eldan 2013 2020), developed to study the
Department of Statistics, University of Oxford, {penton doucet, (alligiannsstatee ox ac. uk CNRS, ENS Ulm, Paris, ent in. debortol @gma i com

---

Published as a conference paper at ICLR 2024
KLS conjecture and applied to sampling. Stochastic localization sampling is equivalent to diffusion models (Montanari 2023). letting us transfer insights from stochastic localization to our proof.
1.1 DIFFUSION MODELS
A diffuusion model starts with a stochastic process (Xo)) constructed by initializing Xo in the data distribution Pdata and then evolving according to the OrnsteinUUllebeec (OU) SDE
dx,- = -x,dt + V2dB, for 0 S t s T,
where (B))) is a Brownian motion Id (Song et al. 2021b). We then learn the dynamics of
the reverse process (Ye)ee(o.T 7) defined by Y; X If we let qu (x() denote the marginals of the
forward process, then under mild regularity conditions on Paam- the reverse process satisfies the SDE
dY, = (Y, + 2V log (T-)(Y)))dt v2d5%,
Yo 9T,
(2)
where (B)))e(o is another Brownian motion (Anderson
2022 J. We can thus generate samples & ~ Paata by sampling Yo Qr, running the reverse SDE, and setting { Yr-
1982 Cattiaux et al.
The OU process is a convenient choice of forward process as its transition densities are analytically tractable, with 2rjo Xx xo) .Nxx;; Xge xge of Ta) where of 1 e-22 In what follows, will
denote the posterior mean mx:) (-)x) [Xo] and variance (xe) := Cov Coe (1xx,) (Xo);
m, is related to the score function via V log qe (x+) -0 + " 2m, (see Lemma 5 below).
For convenience, will assume throughout that data distribution Pdaaa has identity covariance matrix (as is standard in applications). though our analysis holds similarly without this assumption. We also focus OU noising process rather than general noising SDE (as in e.g. Chen et al. (2023e)), since the OU process is most common in practice. However, our results can be straight- forwardly extended any linear SDE (including in particular the VE SDE (Song et al.
202
To simulate (2). we must make three approximations. First, as we do not have access to Vog 9: (xx) directly, we learn an approximation se (xe, t) to log qi (x;) for t E []] by minimising
((se) = 1000=/((
//' E. (Xe,) V log 9: (X dt.
(3)
Although ((9g) cannot be estimated directly, there are techniques such as denoising or implicit score matching which provide equivalent tractable objectives (Hyvärinen) 2005 Vincent 201T). T. In practice, we empirically estimate these objectives using samples drawn from the forward process, which can be analytically simulated. We typically parameterize sp (x, t) via a neural network for vector of parameters 0 E RRD and minimise the objective function using stochastic gradient descent.
Second, since we do not have access to the initial distribution qr of the reverse process, we instead initialize the reverse process in the standard Gaussian, which we denote πd. This is a reasonable approximation since the OU process converges exponentially quickly to F. (Bakry et al. 2014).
Third, since 2 is continuous-time process we must discretize time in order to simulate it. We pick time steps 0 = to < t1 < ... < tN < T, sample Yo Fa and define (Yi))ejo;r)) via the SDE
dř; (8/ + 2s Yre T tx)]dt +idt++d. dB,
(4)
for each interval [K 4+11 and k: 0, N - 1, for Brownian motion (Bo)seo, We use the notation 7A = tx+1 tx for the step size and denote the marginals of the approximate reverse process by Pr (x)). The sampling scheme defined via (4) is known as the exponential integrator (Zhang & Chen 2023 De Bortoli 2022 Chen et al. 2023a). An alternative is the Marryaaa (EM) scheme, which replaces the dipendepnndent drift term in (4) with its value at the start of the associated interval (Song et al.) 2021b; Chen et al., 2023a). Both methods give similar asymptotic convergence rates, as indicated by Chen et al. (2023a). so we focus on the exponential integrator.
Finally, instead of running 4 all the way back to the start time, we perform early stopping and set tN = T 8 for some small 6. We do this because for non-smooth data distributions V V qe can blow up as t - 0. This means that our model will approximate q5 rather than qu Piaaa which is acceptable since for small ó the distance (c.g. in Wasserstein-P metric) between qs and Paata is small. Early stopping is frequently used in practical applications of diffusion models (Song et al. 2021b).
2

---

Published as a conference paper at ICLR 2024
1.2 STOCHASTIC LOCALIZATION
Stochastic localization sampling schemes were developed by El Alaoui et al. (2022); Montanari (2023) To sample from a distribution Pdata we construct a measure-valued stochastic process (Ma).20 such that "localizes" as s + oo, meaning that there a.s. exists some such that Me + bg as s + oo, and ş ~ Pdata- We construct this process by sampling & Pdata and defining a sequence (U.).20 of noisy observations of via
U, === a5 W.,
(5)
where (Ws).20 a Brownian motion on IR MMontnaai 2023). We then define 14, = Law(E (5) Us). so that j4, is random measure depending on U.. Since U./S { almost surely as 0o, (Ha)s20 does indeed localize and lim;-+oc U./s is distributed according to Pdata
However, constructing (Us)a20 via (5) requires sampling ~ Pdnta which we cannot do. Fortu- nately, we avoid this using the observation that if Pdata has finite second moments, then (U.)a20 is equivalent in law the unique solution to the SDE
dU, a, (U.)ds ddW,
where (W")>>o is Brownian motion and a. (U,) En, K 1977 Montanari 2023). This allows us to construct the stochastic localization process without direct Pdata. so long have access to the function a, (U.). We also define (U, = Cov(
EK U.] Liptser & Shiryaev
Diffusion models and stochastic localization are equivalent under a time change (Montanari (023). If we define (X,):20, (U,)220 according to ① respectively and let t(s) = log(1 + then (U.).20 and (se((*) (((a))a20 have the same law. In addition, (U.) and m, have the same law and A, (U,) and Σ, (X₂) have the same law when t(s). We will sometimes suppress the dependence of ag, A, and m,, Σg on U, and X, respectively when the meaning is clear. For more details and an explicit derivation the equivalence, see Appendix
We now recall two lemmas from the stochastic localization literature. The first can be found in Eldan 2013
Alaoui & Montanari (022). The second follows from the first plus the argument in Eldan
2020 We provide proof' for both results in Appendix B for the reader's 's convenience.
Proposition (Alaoui & Montanari 2022). Theorem 2). If we define L., [x,
due, dpaz
(x), then
(x.(x) [x) a.) dW, for all s 2 O.
Proposition 2 (Eldan 2020), Equation 11). For all 2 0, d E = E [A
Translating Proposition 2 into the language of diffusion models, using that A, and D, are equal in
law when = log( 1 + s s),, we get the following directly from Proposition 2 and the chain rule.
Lemma 1. For all t > 0. 20: di
E
Lemma is the key insight that allows us to control the discretization error more precisely than previous works. In 3] we will see that Σ, is related to the Jacobian the score. Control of E, via Lemma] will thus allow us to control time-discretization terms Ex,t (defined in Section 3).
1.3 RELATED WORK
Convergence of diffusion models Initial results on the convergence of diffusion models required restrictive assumptions on the data distribution such as log Sob-oooeev inequality (Lee et al. 2022]
Yang & Wibisono 2022). or produced bounds that were non-quantitative (Pidstrigach) 2022 Liu
et al. 2022) or exponential in the problem parameters (De Bortoli et al., [021] De Bortoli 2022]
Block et al. 2022). Recently however, several works have proven polynomial convergence rates for diffusion models
Chen et al. 2023ald d Lee et al. 2023 Li et al.; 2023).
First, Chen et al. (203dd) gave polynomial TV error bounds, assuming a Lipschitz score for all t 220. They used Girsanov's theorem to measure the KL divergence between the true and ap- proximate reverse processes (similar to (Song et al. (222la), with an approximation argument since the standard assumptions for Girsanov's 's theorem do not hold in their setting. Second, [Chen et al. 2023al developed this method, introducing tighter bound on the drift terms and exponentially
3

---

Published as a conference paper at ICLR 2024
Regularity condition
Metric
Complexity
Result
vt, V log qt L-Lipschitz
(qu: pr)
( ddL""
Chen et al.
2023d
Thm 2)
e2 ddL al log" (1g"(1 (1/6)
Vt, V log qt L-Liipschtzz
(2o pr)
Ô
Chen et al.
2023a
Thm 1)
None
KL (Pt))
Chen et al.
2023a
Thm 2)
None
KL |Px))
dlog (1/5)
This work:
Corollary
Table 1: Summary of previous bounds and our results. Bounds expressed in terms of the number of steps required to guarantee an error of at most s² in the stated metric, assuming perfect score estimation. We assume Pauta has finite second moments and is normalized so that Cov(Páaa) la.
decaying sequence of time steps. They provide two bounds on the KL error. The first (Theorem 1) is linear in the data dimension d but requires Lipschitz scores for t 2 0 and depends quadratically on the Lipschitz constant. This is unideal since the Lipschitz assumption excludes many distributions of interest, such as those supported on a submanifold. In addition, the Lipschitz constant can hide additional dimension dependence in some cases (such when the data are approximately supported on a submanifold). The second (Theorem 2) uses early stopping and applies to any data distribution with finite second moments but is quadratic in d. The latter gives the current best bound on the
iteration complexity of diffusion models without smoothness assumptions of Ó (1/6)
In parallel, Lee et al. (203)) derived weaker polynomial convergence bounds using a x² -based anal- ysis and method to convert 7, -accurate score estimates into T.e-accurate estimates. Most recently, [i et al. (203) demonstrated bounds for several deterministic and non-deterministic discrete-time sampling methods using elementary techniques, assuming control of the approximate score and its derivative. We summarise the results of et al. (2023a and compare them to ours in Table [
In addition, several works have studied the convergence properties of deterministic or approximately deterministic sampling schemes based on diffusion models (Chen et al. 2023c e Albergo & Vanden- Eijnden 2023] [Albergo al. 2023] Benton al. | [2023] [i et al. 2023). Other work has focused on the problem of score estimation. In particular, Oko et al. (2023) bound the error when approximating
the score with a neural network and show that diffusion models are approximately minimax optimal
for certain class of target distributions, while Chen al. (2023b) study the sample complexity and convergence properties of diffusion models when the data lies on linear submanifold.
Stochastic localization Stochastic localization was developed by Ronen Eldan to study isoperi- metric inequalities (Eldan 2013) such as the Kannan-Lovász -immoooiiis (KLS) conjecture (Kan-) nan et al. 1995) and the thin shell conjecture (Anttila et al. 2003 Bobkov & Koldobsky (000)). was based on the original localization methodologies of Lovász, Simonovits and Kannan (Lovász & Simonovits 1993] Kannan et al.) 1995) used to study high- nigg--dimessioall and isoperimetric inequal- ities. Subsequently, stochastic localization has been used to make significant progress towards the KI.S conjecture (Lee & Vempala| [017]] Chen (021). T), as well as to prove measure decomposition results (Eldan 2020]|Alauu Alaoui & Montanari (022) and for studying mixing times of Markov Chains (Chen & Eldan 2022). Recently, several works developed algorithmic sampling techniques based on stochastic localization (El Alaoui al., 2022 Montanari Wu 2023). and Montanari (2023) has
shown that these sampling approaches are equivalent in the Gaussian setting to diffusion models.
Concurrent work: After the first version of our work was made publicly available, an independent work appeared by byCoortt et al. (2023) who derive similar bounds. In contrast to our work, they take a stochastic control perspective and work under finite Fisher information smoothness condition. This condition can be removed with early stopping, giving bounds that are linear data dimension up to logarithmic factors, similar to our own.
MAIN RESULTS
The core assumption required for our main result the following control of the score approximation.
Note that their bound is stated incorrectly in their abstract; the correct bound be found in their Table
4

---

Published as a conference paper at ICLR 2024
noised R
1+% (L+*))
70
71
7M
7M+1
data distribution
distribution
to
tM
fM41
fM42
Ix T
T-1
T
Figure 1: Illustration of a typical choice of step sizes satisfying 7h min tx+2}.
Assumption 1. The score approximation fumction sg(x. t) satisfies
By [l[ (XL) - so (Xtx _- 105-ta7 tx)]1²] S S Excure
We view 7 time- version of ((so), Assumption 1 suggests learn score approximation with L eтror at most Escore. adjusting for the discretization of the reverse process. Though this assumption standard in the literature (Chen al. 2023a b), there may be statistical barriers to efficient estimation of the score in high dimensions (Biroli & Mézard [023] Ghio et al., 2023) and Assumption may not capture the full practical difficulty of learning the score.
Assumption 2. The data distribution Pdata has finite second moments, and Cov Cov(Pám)) = La-
The first part of Assumption 2 is required for the convergence of the forward SDE. We include the second part for convenience when stating our results. Our analysis is not dependent on it, and we outline how adapt our proofs for a general covariance matrix in Appendix C
Theorem 1. Suppose that Assumptions 7 LandZholdd that 2 1, and that there is some K. >> 0 such that for each .,...,N 1 have Thk S min (1, tx+1). Then,
KL(qs (P S e 22coro + 2dN + kdT + de- where f1 S f2 denotes that there is universal constant C such that fi S C2-
This is our main bound, and it consists of three parts. The first term eocore measures the error from using a learned rather than exact score. The second terms x2 xdl are due the discretization of the reverse SDE. The final term de-22 controls the convergence of the forward SDE.
We interpret 6 as controlling the maximum step size; 7 is bounded by for E [0, T 1]. and for t E [T - 1, 7] the condition 7% < <(( fx+1) forces "/k to decay exponentially at rate (1 + k)- We visualise this in Figure As in Corollary beloo,, for any N there is a choice of time steps such that x (1/N), up factors which are linear in T and logarithmic in 1/6. Since T will scale logarithmically in d and Eucores we think of the second terms Theorem as scaling like (d/N).
We expect the first term e to scale linearly in d in many cases, e.g. if the target distribution were the product of i.i.d. components. The convergence of the forward process also linear in d. As such, Theorem improves upon the previous sate-of-theear bounds (Chen et al.) 2023a d), which either require strong smoothness assumptions on Paata or have at least quadratic dependence on
We next show that given N we can choose suitable sequence of time steps. This results in a bound on the iteration complexity of the diffusion model.
Corollary 1. For T > 1, 8 < 1 and N 2 log(1/0), there exist 0 = to < < ... < IN = T ò such that for some x O T (1og(11/5) we have "ik S (1 tx++1 for each . - Then, if we take T log
and N ( (o/T+)og(1/)0) ), we have (L(gs|(ptx) ( &
Hence, the diffusion model requires at most Ō log (1/0)) steps approximate qs to within e² in KL divergence, assuming sufficiently accurate score estimator.
Corollary [ shows that by making suitable choice of T, N and to we achieve bound on the iteration complexity which linear in the data dimension (up to logarithmic factors) under minimal smoothness assumptions, resolving the question raised in Chen et al. (023aa). The proof of Corollary
D is deferred to Appendix[I D where we show that taking half the time steps to be linearly spaced between 0 and T and half to be exponentially spaced between T 1 and T 8, illus- trated in Figure [ is sufficient. This choice similar to that made in Chen et al. (2023a), reflecting their observation that exponentially decaying time steps appear optimal, at least theoretically.
5

---

Published as a conference paper at ICLR 2024
The tightest previous bounds on the iteration complexity were obtained by Chen et al. Assuming only finite second moments of Pdata- Chen et al. (2023a) showed that diffusion models with
(2023a
early stopping have an iteration complexity of Ó log (1/81) Alternatively, Chen et al. (2023a d)
showed that if the score is Z-Lipschitz for all t 2 0 then the iteration complexity is O dl The Lipschitz assumption can be removed using early stopping at the cost of an additional factor of 1/84,
arising from the fact that for an arbitrary data distribution the Lipschitz constant of V log q explodes at rate 1/t as 0 (Chen et al. 2023d Lemma 20). As the distance between qu and q8 scales with d=/2 (e.g. in Wasserstein-p metric), for a fixed Wasserstein-plus- KL (or Wasserstein-plus plus--V) error we should scale ó proportionally to d d=1/2 As result, for fixed approximation error for Paatn the bounds of Chen et al. (023d) and Chen et al. [2023a Theorem 2) also scale superlinearly with d.
3 PROOF OF THEOREM
We now provide the proof of Theorem I which comes in three steps. We view Step our main novel contribution, while Steps 2 and 3 closely follow Chen et al. (203a
Step 1: We bound the error from discretizing the reverse SDE (see Lemma below). Previous works bound E,, := E [[|V log (Y,)
log (Y,))l using a Lipschitz assumption. We
new Itô calculus argument to get differential inequality for F.st (Lemmas 3 and 4 relate the coefficients of this inequality to m, and Σ, using known results (Lemma 5), and bound the
differential inequality coefficients using our key Lemmal (resulting Lemmas and 7
Step 2: We bound the KL distance between the path measures of the true and approximate reverse process (Lemma {). We use an analogous Girsanov-based method to Chen al. (2023a d).
Step 3: We use the data processing inequality to bound KL. (L.g]l(pt))) ) in terms of the distance between reverse path measures and the distance between qr and Ty. We bound the former using Step 2 and the latter using the convergence of the OU process (Proposition 4 as in Chen et al. (2023a d).
Rather than work with two processes (Yt)ee and (Ye)xe which are solutions to and (4) under the same probability measure, it is more convenient follow Chen al. (2023a d) and fix single process (Y.)ee and then define Q and pra to be two different probability measures such that (Ye) (Y,)) is a solution to (2) under Q and to (4) under pT In addition, we define a probability measure por under which (Yo)eEjoTT) is solution to (4) but with the initial condition Yo- ~ Qr.
3.1 BOUNDING THE DISCRETIZATION ERROR
Lemma 2 (Bound on discretization error). If (fY))aejo) is the solution to the SDE 2 then we have
N-1
fk+1
EQ [|V log (r V log 9r (Yww)) 1X))? dt S RdN + RdT.
k
Proof. We start by controlling E.gt for 0 S < T, where (Yi):20 follows the law Q of the exact reverse process ( Since log (x)) is smooth, we may apply Itô's lemma to get the following result, proved Appendix
Lemma 3. If (Vo)ee(oor) is the solution to the SDE ② then for all 1 E (0, we have
d(V log (T-) = -V log - -Y)) + 2 log log dB'.
From Lemma and the product rule, we have ( /2c' log 9r (Y.) dBB.
Since, by (13) below, f e²rEq [[|V2 log 9T (V,) dr < 00 for 0 < s S < T. where we
denote by ||||| F- = Tr(A" A)2/2 the Frobenius norm of matrix A. the RHS is square-integrable martingale. So, we may apply Itô's s isometry (Le Gall 2016 Equation 5.8) and differentiate to get
dt Eq [lle'v log (X) - -Y.)) = 2e "Ed
V log qr -
(8)

---

Published as a conference paper at ICLR 2024
In addition, for 0 S t T where is considered fixed and t may vary, from Lemma we have
d ( v log (r- log ( V Vlog (o
+ 22 log QT' (Y.). V log (X)) dBj.
Since 1: Ee 2 log (X:)) dr < ao for 0 < 8 S < T, the final term is a square- integrable martingale. Integrating and taking expectations, we get
d J. E V (Y.)))-(YY.) v log ( Eq V Floger-s
log (Y))).
where again we may interchange integration and expectation using Fubini. Combining ( and ( deduce the following differential inequality for És (See Appendix for full derivation.)
Lemma 4, For all 0 I $ S t T, we have
d F.tt =2EQ [|[ log Qr - 2E || (o V Voggrr-
+ 2 [[V log or - (Y,)
log qr-)(())) log (r.))l (10)
To further bound the RHS of 10p. note that by Young's 's inequality
Bq [(V log (
log fr (Yi))
log (Y.)))
EQ
V log
log ( EQ
V [Yg))
Therefore,
d.
$ Eq | log loggr--(YY)] + 2EQ log 2r- (X
(11)
dt
We must thus bound IEQ | log (Y:)l1 and EQ [||V² log qT (Y.) We make use of the following lemma, which is found in previous work on diffusion models (see e.g. De Bortoli (2022);
Lee et al. 2023); Benton et al. (2023)) and which we prove for completeness in Appendix
Lemma 5. For all t O, have V log (x)) - 2x, eo 2 2m, and V (x,, -0, te 20, 'E,.
We may use Lemma rewrite |/V log (Y.) and 2 log gr (Y,) PP in terms Y, m, and
Σ. Expanding the resulting expressions, the first can be bounded using elementary properties of the OU process, while the second can be bounded using properties of the OU process plus our key Lemma [ We obtain the following inequalities (see Appendix for derivations).
Lemma 6. If (Y))eejo is the solution to the reverse SDE
2 then for all t, [0, 7") we have
Eq [[| log qr s
< do
(12)
and
1 d
Eq [[ (r- do
2 dr (o Tr (TTE--il)
(13)
Putting the bounds in
and together, we get EQ (lV
2E [[[ log 4T (
d
< do 2 + 2
dr
Let us denote the two parts of this error term by
B01 = 2 + 2d
E(2) a,t
= dr (EEr,))
From 11 it follows that
[[V Qr + 2EQ 10 ds f" Elt) E22) ds.
Eig S
EQ
(14)

---

Published as a conference paper at ICLR 2024
We bound the contributions to E,,, from E and Pi.ss It will be convenient to divide our time period into intervals (0, 7 and [T 11, T- and treat these separately. We therefore assume there is an index M with far = 7 1. This assumption is purely for presentation clarity and our argument works similarly without it. Then, the following lemma bounds the various contributions to E The proof of Lemma]] 7 elementary but technical, so we defer it to Appendix
Lemma 7. The error terms E satisfy
M-1
Σ
1++1
E ds dt S kdT,
Σ J/
N-1 llt1
(
ELEhiaos S Rd
(15)
km0
Ki M bk
and the error terms Eie. satisfy
po+t (f dt S rd + RddN
Σ
(16)
K=
Finally, by combining (4)
with
and (16) we complete the proof of Lemma
3.2 BOUNDING THE KL DISTANCE BETWEEN PATH MEASURES
Lemma 8 (Bound on distance between path measures), IfQ and pur are the true and approximate path measures respectively then KL(Q) por) S Score + - kdl'
Proof. We use the following result from Chen et al. (203dd) (proof recalled in Appendix
Proposition (Section 5.2 Chen et al. (2023d). Q and per be the path measures of the solutions to ( and (4) respectively, both started in Yo qr and run from t = 0 to t = ty. Assume
that
N-1
EQ
Vlog so(Yo,, - tx]]l]] dt 80.
k=
Then, we have
N-1
(L(
BQ [| V (ogggr-(((()) so(Yo,, -xx)] dt.
4x
To apply Proposition
3
we note that by Lemma and Assumption we have
N
ftt1
Eq
[ log (Yi) so T T [x dt
K=-
BBQ [| log -r- (Yox) 20 (Y T tx
0=
EQ
[| loggorr--r (V)) V log qr (Y,,
k=0 4/
S 6220 + 2dN + kdT < 0o.
Therefore, the conditions of Proposition 3 hold and Lemma by applying Proposition
3.3 COMPLETING THE PROOF
Finally, we show how to complete the proof of Theorem I from Lemma As a corollary Lemma
that Q is absolutely continuous with respect to Por Since Por and ard differ only by change of starting distribution, write dpur dppg (y)
dnd (Yo) for path y (y<)se(o.x))-
dgz
8

---

Published as a conference paper at ICLR 2024
and deduce that par and pn are mutually absolutely continuous. It follows that Q is absolutely dQ apir
continuous with respect to pna and apta (y)
dQ xpgy(y
(y) dpp (y) aPoT (y) dad (yo). Therefore,
d
aQ
dgr
(L(Q)|PTd) = EQ log (
dQ dP (Y)
der drd
[ro)] (L(QII + KL(gr]| (17)
(V6)
The first term is bounded by Lemma 8 The second is controlled by the convergence of the forward process in KL divergence and can be bounded using the following proposition (which is very similar to Lemma 9 in Chen et al. (2023a). We defer the proof of Proposition to to Appendix G
Proposition 4. Under Assumption we have (L(TTI|Ta) S de for T 2 1.
Since q6 and ptx are the pushfowards of the path measures Q and pn under f: (We))e H WaNs the data processing inequality implies that KL( ) S (L) Finally, combining this with 17 Lemma 8
and Proposition completes the proof of Theorem
DISCUSSION
Inspecting our bound in Theorem [ the error from approximating 9r by ay decays exponentially in I' and so is typically negligible, If the L error of our score approximation is e then we cannot hope to improve on the term of order a for the KL error due using an approximate score. It remains to consider how tight the term corresponding to the discretization of the reverse process is.
Our proof shows that under our assumptions, with perfect score approximation and initializing the reverse SDE in gr, the KL error induced by discretizing time is of order x² dN + kdT. As explained in Section 2 we can think of this as being (ddNN), assuming suitable choice of time steps and k, or equivalently (ddy) where 77 is the average step size. We note that the linear dependence on d (up to logarithmic factors) here optimal (for justification, see Appendix H).
However, it is unclear whether the linear dependence on is optimal here. On the one hand, the KL divergence between the true and approximate reverse path measures (cd)) in the worst case (consider the case where Pdata is a point mass, or see Theorem 7 in Chen et al. (2023d) in the critically damped Langevin setting). Thus, our Girsanov-based method cannot improve upon the rate of ((dr) without significant modification.
addition, the best known convergence rates in KL divergence for Langevin Monte Carlo (LMC) under various functional inequalities are Ö(d)) (Cheng & Bartleti 2018 Vempala & Wibisono 2019 Chewi et al. 2022) Yang & Wibisono 2022
On the other hand, the increasing noise schedule of diffusion models may allow for improved con- vergence rates compared to LMC. As evidence, Mou al. (2022) show that the EM discretization of an SDE has error O11)²) in reverse KI. divergence, under smoothness assumptions which should be satisfied under early stopping, making only mild additional assumptions on the data distribution such as bounded support. We could apply their results to get O(n²²) convergence bounds for the diffusion model, but the implicit constant would depend on d and on the smoothness parameters, which in turn depend polynomially on d and 1/8. This leads to bounds which are quadratic in 1j but superlinear in d. We expect such bounds to be tighter than our own when 1j > poly(d).
We may also get better convergence bounds by working in weaker metrics. Under some smoothness assumptions on Paata. our KL error bounds imply a bound of ((v1)) in Wasserstein-2 distance via Talagrand inequality (Otto& Villani 2000). However, there evidence that this rate suboptimal. Under smoothness assumptions on the drift, the EM discretization has error Ö(7) in Wasserstein-P metric for 2 (Alfonsi et al., 2015). Under smoothness and convexity assumptions on the data distribution, LMC converges at rate On) (Durmus Moulines 2019 Li et al. 2022). However, these results require additional smoothness assumptions and have superlinaar dependence on d.
Ultimately, there appears to be a trade off between the dependence on the data dimension and the step size. Our key to obtaining bounds which are tight in d was to use bounds the drift coefficient of the reverse SDE which hold in expectation. All methods of which we are aware that achieve a better dependence on 77 require stronger (e.g. L control on the drift. These necessitate worse dimension dependence and additional smoothness assumptions. We leave bridging the gap between these two strands of proofs to future work.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We thank Tyler Farghly for pointing out small gap in the original version of this work. Joe Benton was supported by the EPSRC through the StatML CDT (EP/S023151/1). Arnaud Doucet acknowl- edges support from EPSRC grants EP/R034710/1 and EP/R018561/I.
REFERENCES
Ahmed Alaoui and Andrea Montanari. An Information-Theoree View of Stochastic Localiza- tion. IEEE Transactions Information Theory, (8111::7423-7422 2022.
Michael S Albergo and Eric Vanden-Eijnden. Building Normalizing Flows with Stochastic Inter- polants. In International Conference on Learning Representations, 2023.
Michael S Albergo, Nicholas M Boffi, and Eric Vanden- -ijnden. Stochastic Interpolants: A Unity- ing Framework for Flows and Diffusions. arXiv preprint arXiv:2303.08797 2023.
Aurélien Alfonsi, Benjamin Jourdain, and Arturo Kohatsu- Higa. Optimal transport bounds between the time-marginals of multidimensional diffusion and its Euler scheme. Electronic Journal of Probability, 20:1-31, 2015.
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient Flows: in Metric Spaces and in the Space of Probability Measwres. Springer Science & Business Media, 2005.
Brian D) O Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):313-326, 1982.
Milla Anttila, Keith Ball, and Irini Perissinaki. The central limit problem for convex bodies. Trans- actions of the American Mathematical Society, 355(12):423--4735, 2003.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Struc- tured Denoising Diffusion Models in Discrete State-Spaces. In Advances in Neural Information Processing Systems, 2021.
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and Geometry of Markov Diffusion Operators. Springer, 2014.
Joe Benton, George Deligiannidis, and Arnaud Doucet. Error Bounds for Flow Matching Methods. arXiv preprint arXiv:2305. 2023.
Giulio Biroli and Mare Mézard. Generative diffusion in very large dimensions. arXiv preprint Stti::3006005//8 2023.
Adam Block, Youssef Mroueh, and Alexander Rakhlin. Generative Modeling with Denoising Auto- Encoders and Langevin Sampling. arXiv preprint arXiv:2002.00/07 2022.
Sergey G Bobkov and Alexander Koldobsky. On the Central Limit Property of Convex Bodies In Geometric Aspects of Functional Analysis: Israel Seminar 2001-2002, pp. 44-52. Springer, 2003.
Patrick Cattiaux, Giovanni Conforti, Ivan Gentil, and Christian Léonard. Time reversal of diffusion processes under finite entropy condition. Annales de I' I'Institul Henri Poincaré (B) Probabilités et Statistiques, 2022.
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved Analysis of Score-based Generative Mod- cling: User-Friendly Bounds under Minimal Smoothness Assumptions. In International Confer- ence on Machine Learning, 2023a.
Minshuo Chen, Kaixuan Huang, Tuo Zhao, and Mengdi Wang. Score Approximation, Estima- tion and Distribution Recovery of Diffusion Models on now-Dimensional Data. arXiv preprint arXiv:2302.07/99 2023b.
Sitan Chen, Sinho Chewi. Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ODE is provably fast. arXiv preprint arXiv:2305. /798, 2023c.
10

---

Published as a conference paper at ICLR 2024
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is easy as learning the score: theory for diffusion models with minimal data assumptions. In International Conference on Learning Representations, 2023d.
Sitan Chen, Giannis Daras, and Alexandros G Dimakis. Eestoration-Degraaatii Beyond Linear Diffusions: A Aoymsttpto Analysis For DDIM-Typa Samplers. In International Conference on Machine Learning. 2023e.
Yuansi Chen. An Almost Constant Lower Bound of the Isoperimetric Coefficient in the KLS Con- jecture. Geometric and Functional Analysis, 31:34-61, 2021.
Yuansi Chen and Ronen Eldan. Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains. IEEE 63rd Anmual Symposium on Foundations of Computer Science (FOCS), pp. 110-122, 2022.
Xiang Cheng and Peter Bartlett. Convergence of Langevin MCMC in KL-divergence. In Proceed- ings of Algorithmic Learning Theory, volume 83, pp. 186-211, may 2018.
Sinho Chewi, Murat A Erdogdu, Mufan Bill Li, Ruoqi Shen, and Matthew Zhang. Analysis of Langevin Monte Carlo from Poincaré to Log-Sobolev. In Proceedings of Thirty Fifth Conference on Learning Theory, 2022.
Giovanni Conforti, Alain Durmus, and Marta Gentiloni Silveri. Score diffusion models without early stopping: finite Fisher information is all you need. arXiv preprint arXiv:2308. 12240, aug 2023.
Valentin De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. Transactions Machine Leurning Research, 2022.
Valentin De Bortoli, James Thortoo,, Jeremy Heng, and Arnaud Doucet. Diffusion Schrödinger Bridge with Applications to Score-Based Generative Modeling. Advances in Neural Informa- fion Processing Systems, 2021.
Prafulla Dhariwal and Alex Nichol. Diffusion Models Beat GANs on Image Synthesis. In Advances in Neural Information Processing Systems, 2021.
Alain Durmus and Éric Moulines. High-dimensionall Bayesian inference via the Unadjusted Langevin Algorithm. Bernoulli, 25(44))2854-2882, 2019.
Ahmed EI Alaoui, Andrea Montanari, and Mark Sellke. Sampling from the BeerringtonKirkpaatre Gibbs measure via algorithmic stochastic localization. IEEE 63rd Annual Symposium on Foun- dations of Computer Science (FOCS), pp. 323-334, 2022.
Ronen Eldan. Thin Shell Implies Spectral Gap Up to Polylog via Stochastic Localization Scheme. Geometric and Functional Analysis, 23(2):332-569 2013.
Ronen Eldan. Taming correlations through entropy-efficient measure decompositions with appli- cations to mean-field approximation. Probability Theory and Related Fields, 176(3-4):377-755 2020.
Davide Ghio, Yatin Dandi, Florent Krzakala, and Lenka Zdeborová. Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective. arXiv preprint arXiv:2308.14083 2023.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising Diffusion Probabilistic Models, In Advances in Neural Information Processing Systems, 2020.
Aapo Hyvärinen. Estimation of Non-Normalized Statistical Models by Score Matching. Journal of Machine Learning Research, 6(24))695-709, 2005.
Ravi Kannan, László Lovász, and Miklós Simonovits. Isoperimetric problems for convex bodies and a localization lemma. Discrete & Computational Geometry, 13:541-559, 1995.
Le Gall. Brownian Motion, Martingales, and Stochastic Calculus. Springer, 2016.

---

Published as a conference paper at ICLR 2024
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. In Advances in Neural Information Processing Systems, 2022.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In International Conference on Algorithmic Learning Theory, pp- 946-985, 2023.
Yin Tat Lee and Santosh Vempala. Eldan's 's Stochastic Localization and the KLS Hyperplane Con- jecture: An Improved Lower Bound for Expansion. IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 998-1007, 2017.
Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Towards Faster Non-Asympiotic Convergence for Diffusion- Generative Models. arXiv preprint wrXiv:2306.0925// 2023.
Ruilin Li, Hongyuan Zha, and Molei Tao. Sqrt(d) Dimension Dependence of Langevin Monte Carlo. In International Conference on Learning Representations, 2022.
Robert S Liptser and Albert Shiryaev. Statistics of Random Processes: General Theory. Springer, 1977.
Xingchao Liu, Lemeng Wu, Mao Ye, and Qiang Liu. Let us Build Bridges: Understanding and Extending Diffusion Generative Models. arXiv preprint arXiv:2208. 14699, 2022.
László Lovász and Miklós Simonovits. Random walks in a convex body and an improved volume algorithm. Random Structures & Algorithms, 4(4):359-412, 1993.
Andrea Montanari. Sampling, Diffusions, and Stochastic Localization.
arXiv preprint
arXiv:2305. 10690, 2023.
Andrea Montanari and Yuchen Wu. Posterior Sampling from the Spiked Models via Diffusion Processes. arXiv preprint arXi:2300.11144, 2023.
Wenlong Mou, Nicolas Flammarion, Martin J Wainwright, and Peter I. Bartlett. Improved Bounds for Discretization of Langevin Diffusions: Near-Optimal Rates without Convexity. Bernoulli, 28 (3):1577-1601, 2022.
Kazusato Oko, Shunta Akiyama, and Taiji Suzuki. Diffusion Models are Minimax Optimal Distri- bution Estimators. In ICLR 2023 Workshop on Understanding Foundation Models, 2023.
Felix Otto and Cédric Villani. Generalization of an Inequality by Talagrand and Links with the Logarithmic Sobolev Inequality, Journal of Functional Analysis, 173(2):311-400, 2000.
Jakiw Pidstrigach. Score-Based Generative Models Detect Manifolds. In Advances in Neural Infor- mation Processing Systems, 2022.
Vadim Popov, Ivan Vovk, Vladimir Gogoryan, Tasnima Sadekova, and Mikhail Kudinov. Grad-TTS: A Diffusion Probabilistic Model for Text-to-Speech. International Conference on Machine Learning. 2021.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical Text- Conditional Image Generation with CLIP Latents. arXiv preprint 0rXiv:2204.66/25, 2022.
Herbert Robbins. An Empirical Bayes Approach Statistics. Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, 1:157-164, 1956.
Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kam- yar Seyed Ghasemipour, Burcu Karagol Ayan, S Sara Mahdavi, Rapha Gontijo Lopes, et al. Photorealistic Text-to-Image Diffusion Models with Deep Language Understanding. In Advances in Neural Information Processing Systems, 2022.
Jascha Sohl-Dickstein, Eric A Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep Unsuper- vised Learning Using Nonequilibrium Thermodynamics. In Internationnl Conference on Machine Learning, pp. 2256-2263 2015.
12

---

Published as a conference paper at ICLR 2024
Yang Song and Stefano Ermon. Generative Modeling by Estimating Gradients of the Data Distri- bution. In Advances Neural Information Processing Systems, volume 32. Neural information processing systems foundation, 2019.
Yang Song, Conor Durkan, lain Murray, and Stefano Ermon. Maximum Likelihood Training of Score-Based Diffusion Models. In Advances in Neural Information Processing Systems, 202 a.
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-Based Generative Modeling through Stochastic Differential Equations. Interna- lional Conference on Learning Represenlations, 2021b.
Brian L. Trippe, Jason Yim, Doug Tischer, David Baker, Tamara Broderick, Regina Barzilay, and Tommi Jaakkola. Diffusion probabilistic modeling of protein backbones 3D for the motif- scaffolding problem. In International Conference on Learning Representations, 2023.
Santosh Vempala and Andre Wibisono. Rapid Convergence of the Unadjusted Langevin Algo- rithm: Isoperimetry Suffices. In Advances in Neural Information Processing Systems, 2019.
Pascal Vincent. A Connection Between Score Matching and Denoising Autoencoders. Neural Computation, 23(7):1661-1674, 2011.
Joseph L. Watson, David Juergens, Nathaniel R. Bennett, Brian L. Trippe. Jason Yim, Helen E. Eisenach, Woody Ahern, Andrew J. Borst, Robert J. Ragotte, Lukas F. Milles, et al. De novo design of protein structure and function with RFdiffusion. Nature, 62097976):1089-11000 2023.
Minkai Xu, Lantao Yu, Yang Song, Chence Shi, Stefano Ermon, and Jian Tang. GeoDiff: A Geo- metric Diffusion Model for Molecular Conformation Generation. In International Conference on Learning Representations, 2022.
Kaylee Yingxi Yang and Andre Wibisono. Convergence in KL and Rényi Divergence of the Unad- justed Langevin Algorithm Using Estimated Score. In NeurIPS 2022 Workshop on Score-Based Methods, 2022.
Qinsheng Zhang and Yongxin Chen. Fast Sampling of Diffusion Models with Exponential Integra- for. In International Conference on Learning Representations, 2023.
13

---

Published as a conference paper at ICLR 2024
A EQUIVALENCE OF DIFFUSION MODELS AND STOCHASTIC LOCALIZATION
Suppose that (Xe) follows the OU SDE defined in T Using the integration by parts formula
for continuous semimartingales (Le Gall 2016).
d(e' X₂) = X,dt + d + v2dB, = dBe
By the Dubins-Schward theorem Le Gall 2016 Theorem 5.13), there is process (W.) such that
Wo-11 /
Ve
and (W.)s20 is a standard Brownian motion with respect to the filtration (Fr(s))a2 where T(s) log(1 + s). Then, for all s E (0, oo) we can write
7()) X Xo + W.
we set Up = 0 and
U-: (1 (+(s/s) sXo + sWi/s
for s E (0, 00), then we observe that (U+).20 satisfies the definition the stochastic localization process in (5) since the law of (sW1/a)<2) is the same the law of (Ws).20- Thus the forward diffusion process and the stochastic localization process are equivalent under the chance of time variables t(s) log(1 + =-)).
In addition, we see that conditioning on U, is equivalent to conditioning on X((e) and thus μts and 40 (xx) define the same distributions when t(s). follows that ag (U,) and mx.),) have the same law and A, (Us) and (X,) have the same law when t(s).
B PROOFS OF STOCHASTIC LOCALIZATION RESULTS
Propositions T and 2 are can be found for example in Eldan (2013); Allauu & Montanari (2022): El Alaoui al. (2022)
and we reproduce the proofs here for convenience. Proposition
and our proof of Proposition is based on the argument on pages 8-9 of Eldan (2020).
Proof of Proposition From (). we can deduce that
ps(dx) Z, exp fx U, -/ } (dxx( (dx),
where Z, Squ exp fxx U. x1|x|122 Pdata (dx) is the normalizing constant. Therefore,
d dlog (x) dU, - |x|//ds dlog Z..
(18)
Writing hx(x = x U, ||| and using the definition of U, in 5 plus d[W, W). = ds, we have (x) x dU, || and d[[(xx), h(x)]. | Since h, (x) is continuous semi-marten martinaati and exp is smooth, we may apply Itô's lemma to exp (hx(x)} and integrate with respect Pdma (x) to get
d2. / (dh.(x)+ + [(((())) (x) pammaa
panta (dx)
JRd
Jer x (xx()) (dx)
Z, (a, dU.).
Then, via another application of Itô's lemma, since Z. is continuous and log smooth,
dZ,
1 [[]
d log 7,
2 Z? a, dU, |aa 2ds.
Z,
14

---

Published as a conference paper at ICLR 2024
Substituting this into T8 we that
d log (x(x = (x -as) (dU's a,ds) x
asl12ds
= (x a.) dw"
x a.
where we recall the definition of (W")s20 from (6. The result then follows via final application of Itô's lemma.
Proof of Proposition First, using Proposition we have
da.
x (xlo(x))anl (x)
Rd
xcL, (x)
x % (x a,),,(x)) dW Pauta (dx).
gdd
This implies that
da, E,, I5 s (5 a.]]dW] = A. dw"
then follows from Itó's isometry that
[a 62 = E [A]]
ds
The result then follows from the fact that
E [A.] = E,, [ -
C ADAPTATIONS REQUIRED TO HANDLE A GENERAL COVARIANCE OF Pilata
We briefly outline the changes required in proofs to handle data distribution with general covariance matrix. The main changes required are in the proofs of Lemmas and 7 and Proposition 4 In this section, replace Assumption with the following.
Assumption 3. The data distribution Paata has finite second moments, with M2 := Epa.. ||
First, we note that the proofs of Lemmas 3 and go through unchanged, and so these results also hold in the more general setting. For Lemma 6 the proof of (12) can be adapted, replacing each time we use E | = with E
[||Xo|| |
M2 and noting that since Xo and X, - e e are
independent, we have E [I [2] = E [[](X, ex)) + = dof + 2- M2. We find
that all instances of M2 cancel the final result and (12 holds unchanged. In addition, the proof of 13 needs no alteration.
The only change in the proof of Lemma comes towards the end, when assert that E [Tr(E.)
E E [||x,,] 1 [X ||E [X,]X X
< E [|IXx]]]]] d for t [1. Under Assumption 3 this becomes E [Tr( S E [|]]]]]] M2. Propagating this through the rest of the proof, we find that (6) should be replaced by
[[3]
(F di S kM2 + +
(19)
The final change that must be made is to Proposition 4 which must be replaced by the following more general version that can be proved along identical lines.
Proposition 5. Under Assumption
3 we have (I-(gr[[za) $ (d + M2)e 2T for T F21
Putting all of these changes together, we arrive at the following more general version of Theorem I
Theorem 2. Suppose that Assumptions 7 and 3 hold, that T 2 1, and that there is some k > 0 such that for each = O,..., NN
have 7/k S min T t.+1). Then,
KL pex) S 2 + R² dN + kdT + kM2 + (d + M2)e -7
Theorem 2 holds even in the case where the covariance is not strietly positive definite, and in the case where it is unknown to our diffusion model algorithm. Since we expect M2 to scale linearly in d in most cases, consider this result to be in essentially the same spirit as Theorem
15

---

Published as a conference paper at ICLR 2024
D PROOF OF COROLLARY 1
Proof of Corollary 7 For convenience, we assume that N even. We take to = 0, 12/2 = 7 - 1, and IN = 6, and pick ,,...., ,... such that to...., 12/2 are linearly spaced on [0, T' 1] and exponentially decaying sequence from 1 to å (illustrated in Figure D
T IN/2....... .... IN
Then, 7/: - K. 11, T 1++) for each h: = 0,.... N 1 if and only if K 2 (7 1)/(N/2) and = (1/6)1/N - The former is satisfied if we take R. = S2 (v) and the second is satisfied provided
that x = (2( lo2(1/6)) since 2 log(1/8) and ex' < + (e 1)r for S 1. Therefore, for some have " S min (1, 1x+1] for each k O..... N 1, proving the first
O(2 (T+ (Toloo(11 (/4)
part of Corollary
For the second part, suppose that we T 1 log
and N O d Then,
have x²dN (e kdT O (e and de (E We may therefore apply Theorem to get that (L.(gsllpt.)) = ( The bound on the iteration complexity then follows
since 7 depends only logarithmically d and Excore
E OMITTED PROOFS FROM SECTION 3
Here, we provide the proof's of Lemmas
6 and 7 which were omitted from Section 3
Proof of Lemma
Recall that the reverse process (Vo)ee(oTT satisfies
dY: (Y, 2V log ( + v2dB/. Since V +x)+(r))) is smooth for E [0, 7), by Itô's lemma we can write
d(V d(Vloggr-((Y)) = VV2 log {Y; + 2V log log + A(V gr- de
d(V log qr ( dt + 2 log (r .B (20)
dc
The Fokker-Planck equation for the forward process is
dg. (x) = { V (77.(-xq.,)) (xx (g.)x)d
from which can deduce
d(log (x) = {d+ x V log (x)) Aog + V log (x))
It follows that
d(V log qr 1) (x) --VVlo + 2 log x ((A log (xx))
dt
2 log qr (x()) V log (x))
by interchanging the order of the derivative operators. Substituting this into 20 and simplifying. obtain the desired result.
Proof of Lemma
First, expanding
we get
EQ ||| log o 2EQ [|] V (o))
d dt
2e-
ReQ V logor-s((Y) Vloger
2e (1-s) (t~s) Eg V
yT log V Vloger-((Y))
2Eq [|] 2 log 인r -X))
Combined with ( this shows that
dt Eq V log -r + 2E4 || loggr-((X)111
-EE || log qr (
16

---

Published as a conference paper at ICLR 2024
Then,
d.at dt
dt Ee V log (X))
2 dt
E v log (Ya))) V (Y.))
-2 V log (X)))
22E [ (Y;)
+ Q V (r
< Vlog
which rearranges give
Proof of Lemmaa 5 Part (i) is a classical result, sometimes known Tweedie's s formula (Robbins)
1956). Part (ii) has been established previous works (see e.g. De Bortoli [2022 Lemma C.2) or
Lee al. 2023
Lemma 4.13)). We provide proofs of both results for reference.
For (i), we have
log (x() =
log qe (xxx(x0))0.. (X.: X cbco.
9s (xx) J
Since (x,o(xx(x)) (xxx; xne= oo0oo ooll). I), it follows that log 9ojo (x0) = -0, "x-((x; - Xoe x)e Therefore,
(xx)) [-)x(( [-o, ?xx Xue ")
- Ex + e 00,0,"10 "mc.
For (ii), we can write
2 log gr (x:)
1
2 (xxe xx)
(xx)
1
(V
voo (x))) " "0,x(xx, x, xx)dxo
2e (xx)
1
(fe V Vlog q: (Xo, x dxx ) (Jee
V Voo 2e (x.0 x )dxx)
9c
(x})
1
1 + Bgo (-txx) [or "xe Xoe (xx Xoe [T
0,
1o, Xoe- (Booc(-1xx)) 1-0 (0
-,, I + of (xx) Xoe
-o, 21 + 22
Proof of Lemma 6 First, using the first part of Lemma and expanding, we see that
Ey, [[ log (X.)ll o, "E [||xx]]]] 2e 'o, E [Xe me] "0,0" "E |
where all expectations are with respect X; gr- Then,
[X, mi] [Xe [Xo Xx]] = E [X, Xo] = E [No [Xo = 'E [|| = de
Also, Tr E.) = TE [1Ixo|| |m | so [ [||m.|13] = d Tr Σ ). We conclude that
E [|V log dr Xx || do; .. $1 Tr Σ,)],
where we have used न. -2 This implies that
E2Q [| (og < do
Second, using the second part Lemma along with the definition ||||] Tr(AT A) and expand- ing, we see that
Eyg. [ log qe (x. do, 28.0, STE [Tr(E))] + कद. "T [+})))]
17

---

Published as a conference paper at ICLR 2024
Taking traces in Lemma get of
of [T+(E,)
of E [Tr(Z,)] = [T<(E))]
(Tr(E,)
2c 2F dt
20,0, dt
20, dt
d E [Tr (Ex) 2 Therefore, and since [Tr{)t] 2 0, it follows that
V log qi (X)IIa) do, 20,0, ' [Tr{,,)] ,10 d
Egg
E [T<))))]
de
S do + di
0 E [T (r,))
where we have used that o,6, S 1. This implies that
EQ || log 9r (
r- +
E
(,, E [Tr [, --
2r
S do
4 TT
B
[Tr Σ Im=
2rr
Proof of Lemmal 7
First control the error terms E If [0, [-, then o 1/2
and E(1) < 10d. We therefore have
re+1
(S. [[ElWadds dt S 5d
M
Σ
Σ
2
RdT,
since we have assumed that 7 S K. This proves the first part of (15).
If s, t [T' 1,T - 6] then (T - s)/2 S o7 2(T - 8) and similarly for t. Therefore,
Σ dutt
(Frihiatt di 5 12d
N-1
(s( s) 2ds
Σ
k=
N-1
$ 12d Σ
(T tx+1)
S k dN
since have assumed that 7 S <(T (+1)). This proves the second part of (15)
Next, we control the error terms E(? Note that o is increasing in and E [Tr(Er=))) is
decreasing in & by Lemma Therefore,
N
dE-1 ( F
1--
de
Σ
(oT E. - B (r(E dt
k=
k=
N-1
7i (oT 14
E [T ET - (Tr(Er-us))
We split this sum into k = 0.... M and k = M,..., N - 1. For k: = 0..... M 1, we have
no S 4% S 4k and so
M-1
Th
OTT
E (r
T-- E Tr E (T(ET-tza))
k=0
4k
E -
[r (T
4kE
(Tr(E))
18

---

Published as a conference paper at ICLR 2024
For k .,...,AN 1 we have NOTT-1
-4
4T tx)² - 4x/ tx) and
N-
Σ
Th
T--
4
E2 (Tr - E (T(Er-caa
k= M
N-1
< 4k Σ
1
E [Tr(ET (.))))++))11 (e
(T - 1x)
k=M
N-1
< 4xl [Tr(E,)] + 4x
7k-1
(T((Tr-)))
(T (T) (R-1)
k= M+1
N
< 4RE [T 4x²
Σ
E Tr((TTeee))
(T - tx)
k= M+
We then have E [Tr(E:)] and
E. [ [111xX)
- || [xo 12] S [|| for i [1,7]
E [Tr(E;)]
2E [Tr CoCCCooooe - xx(x))
2E [ [oe
Xx [|]] |E xx,xx] 11
S 2E [| x1 [1]]
S de o²
16dt
fort E (0, 1]. Putting this together, conclude that
N-1
1
( Ei de I 4Rl [Tr(ET)] + 4&E [Tr(E,)
Σ
k=0
+ 4x
Σ
1
E Tr (Trraa-)))
(T (k)
k= M+1
S kd + 12 2NN.
This proves completes the proof of 16
F APPLICATION OF GIRSANOV'S S THEOREM
We now recall the proof of Proposition The following approximation argument essentially identical to that of Chen et al. (202dd Section 5.2) and we reproduce it here simply for clarity of presentation.
The main ingredient in the proof will be Girsanov's theorem, which we recall below. The version we state can be obtained from Theorem 4.13 combined with Theorem 5.22 and Pages 136-139 in Le Gall (2016).
Proposition (Girsanov's Theorem). Suppose that space and (be)rEjo,T is adapted process this space such that Eql Jo [[b]][ds]] < co. Let (Bi)c2 be a Q-Brownian motion and define L. = So b.dB,. Then, L is a square-integrable Q- martingale. Moreover, we define
Q) a filtered probability
[. badB. 2 [// [1..1
E(C). =exp
for E [0,T] and suppose that EEQ (E(C)r] 1 then E(C) is Q-martingale and so we may define a new measure P = EL)rQQ Then, the process
B B. (( b.ds
P-Brownian motion.
19

---

Published as a conference paper at ICLR 2024
Proof of Proposition 3 Q is the path measure of the solution to (2. (B,))20 is our Q-Brownian motion, and
We will apply Girsanov's theorem the interval [0, ty] in the case where
by = 2 {so (z, (&)
Vlog gr (
for & [(x (e+1] and each k ...... N 1. Note that (be)ae(O,ON) is an adapted process and we have
N-1
EQ
|bsl [
= 2
Eq V log (x)) so -- T dt < oo
k=
by the assumptions of Proposition Therefore, if define C, S b,d in Proposition 6 then (E(())))e(oz11 is continuous local martingale (Le Gall 2016 Proposition 5.11). So, we can find an increasing sequence of stopping times (Tn)n21 such that T, + iN almost surely and (E (C)ennt,)))())
continuous martingale for each n.
Let us define DT = S b, (o.r.) for all E [0, and 2 1. Then we have (()) E(C"),, so E(C") is continuous martingale, and follows that Eg [[[[")]]]== Therefore, we may apply Girsanov's theorem (Proposition 6) to L on the interval [0, Łx]. We deduce that we may define a new probability measure P = {(2 )ew Q and new process
6T B / b. (orr
such that (Bf))E)o is Bro-Brnniann motion.
Since 2 holds almost surely under Q, we see that
(t)dl dY = (Y2 + 2Yo(Y,, T - tx)} (...) + (Yr + 2V log ( [T.NNN (t)dt + v2d8..
In addition,
dQ
KI (II(P)) Rg
log
--Qq [log {((")ex)
dPm
1
pinn
Egq
Lr,
+
||b lds
2
N-1 Σ
px++1
EQ
||
log (YY) sY T tx)]13] dt,
(21)
since C is Q-martingale.
Now, we consider coupling pa for each n and per by taking fixed probability space and a single Brownian motion (Wt)r20 on that space and defining the processes (Y [E(],x)))))) and (Ye)kejo,t)) via
dY,"" = (Y," + 2Y. - (o.r, (Y," + 2V log qr (Y, } (t)d /2dW,
and
dy, = (Y, + 28 T tx)]dt + V2dW,,
and taking X₂ or and setting XØ Xo for each Then, the law of y is p for each and the law of por.
Fix > and define T. C((O, ty]: R*) C([O, [y]; by Te (w) w(t A (tx -E)) for uniformly over [w]] almost surely and hence (me) # pr -
I E Ax]] Then, T- T-(")) - n.
(IT) # per weakly (Chen et al. 2023d
Lemma 12). We then have that
KL (L(( Q1| (Te) Por)
lim inf (() PR)
+0000
lim inf (L(
n m00
dx+1
Eo
[|[ log (r so(Y,,, T -4+)l3] dt, (22)
k=0
20

---

Published as a conference paper at ICLR 2024
where in the first line we have used the lower semicontinuity of the KL divergence (Ambrosio al. 2005| Lemma 9.4.3), in the second line we have used the data processing inequality, and the third line we have used (2T)
Finally, letting + 0 we have that [e(W) + w uniformly on [] Chen al. 2023d Lemma 13),
and hence (I.((T=)) (*))) Por) - KL(QQ] PoT) (Ambrosio al. 2005 Corollary 9.4.6). We
therefore conclude by taking E + 0 in (22
G CONVERGENCE OF FORWARD PROCESS
We show that the forward OU process converges exponentially in KL divergence under Assumption We note that the exponential convergence of the OU process under various metrics well-
established, and the particular result we prove here is very similar to Lemma 9 in Chen et al. (2023a)
Proof of Proposition Since gejo (x: xo) = Nxxx Xoe ,00 La), we have
(l.po (x)) = {dlog 0, -- do? + lle :xoll))
By the convexity of the KL divergence,
(L(grl(za) KL J 9r (xx) (dxx) Td)
$ KL(aTrol [xo)][=a]Paun (dxn)
Rd
2 {dlog 0T d dož
28 TTT Eyasa
||
dl log(1 - E 2T
$ de -T
for T 1, where have used that Epan [1|Xo|1]] d since Cov(psata) Ia.
H LINEAR DEPENDENCE ON DATA DIMENSION IS OPTIMAL
Suppose that we have data distribution ps Rd such that diffusion model approximating p. using the exact scores, initialized from @r rather than wd, and using a given sequence of discretiza- tion times to...., fv has KL error of e.. Then, if consider approximating the product measure p&m on (Rd)m,, again using the exact score, initializing from 47 and using the same sequence of discretization times, the reverse process will factorize across the copies of Rdd Consequently, the total KL error will be me² by tensorization the KL divergence. Thus the KL error of the diffusion model scales linearly in the data dimension in this case, demonstrating that the linear dependence of our KL. bounds on is optimal.
21


Reviews:
[{"review_id": "niWSfsYQgp", "reviewer": "Reviewer_sqy6", "summary": "The paper provides bounds on the number of steps of the discretized SDE in diffusion models required to approximate a general distribution with finite second moments upto a certain accuracy. The central novelty of the paper's analysis is the incorporation of the decay of the expected covariance of the denoising posterior measure during the process of the sampling. The rate of the decay is obtained through results in the stochastic localization literature, which is subsequently combined with the existing analysis based on Girsanov's theorem. The analysis leads to an improved dependence of the iteration-complexity on the input dimension in the absence of a uniform-Lipschitz assumption on the score function.", "questions": "## Questions\n- For what classes of distributions is the uniform Lipshitzness assumption restrictive? What iteration complexity could one expect under smoothness assumptions non-uniform in time?\n- In Lemma 5, the covariance bound in Lemma 1 is utilized to bound the expected Frobenius norm of the Jacobian of the score function. Can this be interpreted as establishing an average-Lipschitzness of the score function?\n- Are deterministic sampling schemes expected to yield identical iteration complexities?\n\n## Suggestions\n- In the title, it should be clarified that \"linear convergence\" refers to being linear in the input dimension, to avoid confusion with the use of the term \"linear convergence\" in the optimization literature.\n- To improve clarity, one could clarify that the SDE in Eq. 6 and the noisy observation process in Eq. 5 are equivalent only in law.\n- I suggest mentioning in sections 1.1 and 1.2 how the posterior means are related to the score function.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Theoretical analysis of diffusion models is an active area with several open problems. \n- The contribution to the proof technique, albeit straightforward, could be useful for downstream theoretical analysis of aspects such as sample and computational complexity, as well as for proofs related to algorithmic stochastic localization in spin-glass models.\n- The paper is well written.\n- The proofs are easy to follow and largely self-contained.\n- The paper adequetely acknowledges the inspiration from the stochastic localization literature towards obtaining the bounds, even though the bounds can be obtained directly using Itô calculus. This helps the reader appreciate the connection with stochastic localization and the motivation behind the results.", "weaknesses": "- Majority of the proof closely follows the analysis of Chen et al. (2023a;d).\n- The paper improves upon best existing bounds in the absence of uniform-Lipschitzness of the score function. However, more explanation is required to understand why Lipschitzness is a limiting assumption.  For instance, while for discrete measures it is apparent that one must resort to early stopping on a corrupted version of the distribution, it requires further justification for measures absolutely continuous w.r.t the Lebesgue measure. Futhermore, the proofs in the algorithmic stochastic localization works such as El Alaoui et al. (2022), themselves rely on the Lipschitzness of the estimated score function. \n- Assumption 1 of approximating the score to arbitrary error, while utilized in existing works, is unrealistic for several setups. For instance, some recent works have highlighted statistical and computational barriers towards the estimation of the score function, in particular the works El Alaoui et al., 2022; Montanari & Wu, 2023, as well as:\n\n   Biroli, G., & Mézard, M. (2023). Generative diffusion in very large dimensions. arXiv preprint arXiv:2306.03518.\n\n   Ghio, D., Dandi, Y., Krzakala, F., & Zdeborová, L. (2023). Sampling with flows, diffusion and autoregressive neural networks: A spin-glass \n   perspective. arXiv preprint arXiv:2308.14085.\n\n   A discussion of the limitations of assumption 1 would strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fH2jhOaMcH", "reviewer": "Reviewer_GLNq", "summary": "The paper improves the analysis for diffusion models, primarily in the setting without uniform smoothness of $\\log p_t$. In this setting, it improves the dependence on time discretization (under an $\\epsilon^2$ close score matching estimator) from $d^2$ to $d$, by analogy with techniques in stochastic localization.", "questions": "Have the authors attempted to apply such techniques to other families of diffusion models, beyond those using the Ornstein-Uhlenbeck forward flow? For instance those found in later work by Chen et al. [1]\n \n[1] Chen, Sitan, Giannis Daras, and Alex Dimakis. \"Restoration-degradation beyond linear diffusions: A non-asymptotic analysis for ddim-type samplers.\" International Conference on Machine Learning. PMLR, 2023.\n\nBelow are some minor corrections/questions:\nFrobenius norm squared should be just Tr(A^\\top A) (page 6)\nGirsanov’s Theorem is given with the condition that $b_t$ is “previsible”, but I am not too clear on what previsible means in this context (it is not given in Le Gall). The standard statement is just that $b_t$ is an adapted process satisfying Novikov’s condition.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The tight rate in dimension is genuinely novel, and the setting where $\\log p_t$ is not uniformly smooth is arguably the more important regime.\n\nThe incorporation of stochastic localization techniques, seen also in Montanari (2023) and other works, is quite elegant and possibly suggests additional improvements. See questions.", "weaknesses": "The main contributions of this work are somewhat narrow, found primarily Lemmas 2, 4, 5, 6, which in my opinion are algebraic consequences of insights developed in prior work. For instance, the original perspective of diffusion models as stochastic localizers comes from Montanari, and the key lemmas used in analyzing stochastic localization are from Montanari (2023) and some of Eldan’s works. The score-matching error and OU error are handled by prior work on diffusion models, from Chen et al.\n\nConsequently, the paper could benefit from additional results, see my questions below.\n\nDespite this, the improvement in rate made by this paper is quite significant and definitely merits publication. Consequently, I am voting for acceptance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AKSEP6YHqD", "reviewer": "Reviewer_4GBU", "summary": "The paper gives a new sampling error bound for diffusion models. Roughly speaking, a diffusion model is a method for sampling from a data distribution $q_0$ that \"works\" whenever one can approximate the scores $\\nabla q_t(\\cdot)$ well, where $q_t$ is the density of a particle undergoing Ornstein-Uhlenbeck dynamics from $q_0$. Usually, score approximations would be found with deep neural networks. \n\nPrevious results by other authors obtained bounds relating the quality of score approximations to the distance between $q_0$ and the distribution output by the diffusion model. The present paper gives improved bounds: the main difference is that the error in approximating scores is not multiplied by any time- or -dimension dependent factors, but only by a universal constant.   The proof of this result follows the outline of previous work by Chen, Lee and Lu; the main modification (according to the authors) is in dealing with discretization errors.is", "questions": "Can you give me a better sense on where the restrictions on the discretization come from?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The bound is an improvement over previous results that is quite natural. Proof techniques are elegant.", "weaknesses": "The main proof outline is not too novel. The condition on the final step sizes is not very natural.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RVPGIberd0", "reviewer": "Reviewer_TDrD", "summary": "Many current state-of-the-art generative models are denoising diffusion models. These models take samples from a data distribution, run them through a forward SDE, which progressively adds Gaussian noise to the samples, and then seek to learn the reverse SDE using neural networks. This paper seeks to prove mixing bounds for the reverse diffusion process after the denoising score model has been learned. In particular, under the assumptions of a learned score function with an L2 error bound and a data distribution with identity covariance, the authors use the theory of stochastic localization to yield a bound on the KL divergence between the generated samples and the data distribution. This bound those that the number of iterates to reach error $\\epsilon$ scales linearly in $d$, quadratically in the forward time $T$, and $O(\\epsilon^{-2})$ with respect to $\\epsilon$.", "questions": "- While the linear dependence in the dimension is expected in the worst case, does the analysis of this paper and similar ones point toward dimension-independent rates under further assumptions on the score? Or is this a limitation of the Langevin diffusion? Could other processes help to alleviate this?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- This work tackles a highly relevant problem on the convergence of denoising diffusion models. \n- The bound given scales linearly in the dimension, which seems optimal in the worst case, as the authors point out in the appendix.\n- The bound given accounts for a realistic setting, where the chain has early stopping, approximate initialization, and discrete reverse time discretization.\n- The bound brings new theoretical tools of stochastic localization, which should be more broadly attractive to the community working on diffusion models.\n- The authors explain the proof in detail in the paper.", "weaknesses": "- There are no simulations or experiments to support the results. However, this is a smaller weakness since the work is primarily theoretical.\n- I wish that there was more discussion of the key lemma. Why is stochastic localization needed to prove it? How can we interpret it?\n- I have some issues with the presentation of the main theorem in the paper. This is important since about a third of the paper is dedicated to explaining the proof of Theorem 1. I found their explanation to be hard to follow. First, I would appreciate a roadmap explaining precisely what steps are new/novel and what steps are guided by past work. In particular, it seems that the work on the discretization error is new, so the authors are then able to apply the bound from stochastic localization. However, is the perspective taken where they view the single process $(Y_t)$ as solutions to (2) and (4) under different measures new? The biggest issue, though, in my opinion, is that much of the proof is left to the appendix. I understand this is necessary, but without more interpretation in the paper to help the reader understand what is happening, it is easy to get lost. Improving this explanation would greatly help the paper since it is primarily theoretical. Some suggestions are the following.\n\nSetup\n- More clearly define the measures $P^{\\cdot}$ and $Q$, and explain how $(Y_t)$ is a solution to (2) and (4) under these measures.\nBound on the discretization error\n- An initial lemma saying the final bound for this section so that the reader can put into context the computations being done. Then, put Lemmas 2-6 into context for how they help with the final bound as they are discussed.\nGirasanov\n- Again, state the final bound as a lemma so that the discussion can be put into context. This can then be pointed to throughout.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ogzM8bNMJ7", "reviewer": "Reviewer_73Lh", "summary": "This paper studies sampling from a data distribution on R^d using denoising diffusion. \nThe main result is an improved convergence rate under only a second moment assumption on the data distribution. \nThis bound improves the dependence of rate on d from quadratic in Chen et al. to nearly linear. \nOther parameter dependencies are the same as in Chen et al.", "questions": "1. I encourage the authors to add \"nearly linear\" in the title. This is a standard terminology (at least in theoretical computer science) for hiding log factors. \n\n2. One dumb question: doesn't the second part of Assumption 2 imply its first part? Or am I mis-interpreting the meaning of second moment of a distribution on R^d?\n\n3. It is claimed that the isotropic condition in Assumption 2 is not essential. However, this has never been formally justified, if I'm not missing it. Which nuisance of the proof needs to be changed if the covariance is general? In fact, I have some doubt on the claim that this assumption is immaterial. What if the covariance is not strictly positive definite? What if the covariance is **unknown**?\n\n4. In the line following equation (9), there seems to be some typos in the equations for verifying the applicability of Fubini. \n\n5. Right before the statement of Lemma 6, it's claimed that the existence of t_M = T-1 is WLOG. This is likely technical but I suggest briefly justify it. I guess if this does not hold, a tiny approximation error needs to be introduced.\n\n6. Please introduce the notation $\\lesssim$ somewhere if it's not been done yet. I assume that this means the LHS is upper bounded by the RHS multiplied by a numerical constant. \n\n7. It's argued informally in section 4 (with some details in appendix G) that the linear dependence of the convergence rate on d is necessary. \nThis seems like a nice observation. Is it possible to turn it into a formal proposition and specify how this lower bound depends on other parameters besides d? In fact, this observation is a little surprising to me since for product distribution, the problem is effectively 1-dimensional however denoising diffusion still incurs a dimension-dependence. Could the authors offer some more intuition? Thanks in advance.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is pretty well-written. \nThe punchline is clearly addressed within the first 3 pages. \nThe key technique that makes the rate improvement possible is a differential inequality for one of the error terms, instead of using Lipschitz bounds which apparently require additional model assumptions. \nI particularly appreciate it that the authors make it clear what is novel in their contribution and what has been well-established in the literature. \nIn the latter case, proper references are given.", "weaknesses": "I don't see obvious technical weaknesses. \nHere are two suggestions.\n\n1. Though this is a purely theoretical paper, given how successful diffusion model is in practice, it might add some value to show some experimental results even for very simple data distribution. \n\n2. Several auxiliary results are known in the literature or can be adapted from known results in a straightforward way. However, proofs for many of these results are still given in the appendix. I understand the intention to increase readability. However, according to my personal taste it feels that there's some room to streamline the proof and make the paper more succinct. To clarify, this is a matter of presentation and either way does not affect my evaluation of the result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0ypj6Su6P8", "reviewer": "Reviewer_wcsw", "summary": "The manuscript studies denoising diffusion models and specifically their convergence in KL to the \"ground truth\" distribution in the absence of smoothness assumptions on the ground truth distribution. The authors revisit the analysis of Chen et al. 2023a/b and improve upon it in terms of dimensional dependence (from $d^2$ to $d$, which is further argued to now be optimal). This improvement stems from a refined discretization analysis using ideas from the stochastic localization literature.", "questions": "With regard to the second of part of assumption 2---you mention that your analysis is not dependent on \"it\"---I have clarifying question: would the result incur extra \"condition numbers\" or does it still work even if this covariance matrix has 0 or near 0 eigenvalues?\n\nCould you expand on the steps taken in equation (9)? I do not immediately see how this follows from the standard Ito Isometry relating squares of stochastic integrals and integrals of their squares.\n\nFollowing the statement of proposition 4 could you be a little more precise/remind us about which stochastic transformation is used in the invokation of the data-processing inequality? It seems like it is here the early stopping idea is used but I find it hard to follow.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The paper offers a rather satisfactory improvement on previous analyses of denoising by shaving of a dimensional factor (or alternatively removing extraneous assumptions such as bdd/lip etc.). \n\n- The problem is quite clearly of interest to the community and the solution offered is also quite elegant in the way it draws on the stochastic localization literature. \n\n- Overall, the paper is well-structured and the quality of writing is generally good. There are some caveats here that I detail below but this is nothing that cannot be adressed by a round of further proof-reading. Although I did not check the appendix in sufficient detail to vouch for correctness, I think their math is generally OK to follow.\n\n- In terms of originality, the authors observe that Conforti et al. have produced a similar result in a parallell submission. I don't see this as an issue for publishing this manuscript at ICLR. I think it is safe to say that these have been developed in parallell and given the different techniques used they are both independently of each other of interest to the community---in my view the ideas herein are fairly original and interesting.", "weaknesses": "My feeling is that this is a solid piece of technical work and I did not find many weaknesses. I do have a few remarks on writing though:\n\n- The notation is a little messy throughout and feels somewhat rushed/needs further proofreading. There are quite a few undefined/implicitly defined objects. Let me give a few examples:\n\n    -  Previous to stating the main theorem, the main object of interest $p_{t_N}$ has never been defined. \n    - The use of bold $\\mathbf{x}$  for realization when defining conditional objects is a little confusing when at the same time $\\mathbf{x}_*$ is a random variable. This is also in conflict with the use in equation 3 where $\\mathbf{x}_t$ is a random variable drawn from $q_t$. It would be helpful if there was a consistent distinction between realization and random object throughout and if this were defined early in the manuscript.\n   -  The notation for conditional expectation given the observation (function $\\mathbf{a}$)  following eqn 6 is unnecessarily dense. In particular, that the LHS depends on $U_s$ whereas the RHS depends on $\\mu_s$ is a little confusing at first glance. It would be good if the authors were a little more parsimonious and consistent in their notation---at least when introducing objects for the first time.\n\n\n*Other comments*:\n\n\n- Following Lemma 1 it would not hurt to expound a little on the significance of the covariance matrix and why it will be useful in the sequel. It would be nice if some version of what is stated \"inside\" the proof of thm 1, second paragraph, appears near this lemma.\n\n- Above equation (9) there is an extraneous square in the definition of the Frobenius norm (and the square root should probably be outside of the trace)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)