Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions
Authors: Sitan Chen
Sinho Chewi
Jerry Li
Yuanzhi Li
Adil Salim
Anru Zhang
Venue: ICLR 2023 notable top 5% (2023)
Keywords: diffusion models
score-based generative models
sampling
score estimation
Langevin
stochastic differential equations

Abstract: We provide theoretical convergence guarantees for score-based generative models (SGMs) such as denoising diffusion probabilistic models (DDPMs), which constitute the backbone of large-scale real-world generative models such as DALL$\cdot$E 2. Our main result is that, assuming accurate score estimates, such SGMs can efficiently sample from essentially any realistic data distribution. In contrast to prior works, our results (1) hold for an $L^2$-accurate score estimate (rather than $L^\infty$-accurate); (2) do not require restrictive functional inequality conditions that preclude substantial non-log-concavity; (3) scale polynomially in all relevant problem parameters; and (4) match state-of-the-art complexity guarantees for discretization of the Langevin diffusion, provided that the score error is sufficiently small. We view this as strong theoretical justification for the empirical success of SGMs. We also examine SGMs based on the critically damped Langevin diffusion (CLD). Contrary to conventional wisdom, we provide evidence that the use of the CLD does *not* reduce the complexity of SGMs.

Published as a conference paper at ICLR 2023
SAMPLING IS AS EASY AS LEARNING THE SCORE: THEORY FOR DIFFUSION MODELS WITH MINIMAL DATA ASSUMPTIONS
Sitan Chen Sinho Chewi" Jerry Li Yuanzhi Li$
Adil Salim
Anru R. Zhang!
ABSTRACT
We provide theoretical convergence guarantees for score-based generative models (SGMs) such denoising diffusion probabilistic models (DDPMs), which con- stitute the backbone of large-scale real-world generative models such as DALL-E 2. Our main result is that, assuming accurate score estimates, such SGMs can efficiently sample from essentially any realistic data distribution. In contrast to prior works, our results (1) hold for an L'-accurate score estimate (rather than -cccuurrt:: (2) do not require restrictive functional inequality conditions that preclude substantial con-log-concaving problem parameters; and (4) match state-of-the-an complexity guarantees for dis- cretization of the Langevin diffusion, provided that the score error is sufficiently small. We view this as strong theoretical justification for the empirical success of SGMs. We also examine SGMs based on the critically damped Langevin diffusion (CLD). Contrary conventional wisdom, provide evidence that the use of the CLD does not reduce the complexity of SGMs.
(3) scale polynomially in all relevant
INTRODUCTION
Score-based generative models (SGMs) family of generative models which achieve state-of-
the-art performance for generating audio and image data (Sohl-Dickstenis et al., 2015 Ho et al.
2020 Dhariwal & Nichol 202 Kingma al. [021] Song et al. 202
Vahdat et al. 202
see, e.g., the recent surveys (Cao et al. 2022 Croitoru et al. 2022 Yang et al. 2022). For example, denoising diffusion probabilistic models (DDPMs) (Sohl-Dickstein et al. al.] 2015 Ho al. 2020)
a key component in large-scale generative models such as DALL-E 2 (Ramesh et al. 2022). As the importance of SGMs continues grow due newfound applications in commercial domains, it is a pressing question of both practical and theoretical concern to understand the mathematical underpinnings which explain their startling empirical successes.
As we explain in Section 2 at their mathematical core, SGMs consist of two stochastic processes, the forward process and the reverse process. The forward process transforms samples from data distribution g (e.g., images) into noise, whereas the reverse process transforms noise into samples from q, hence performing generative modeling. Running the reverse process requires estimating the score function of the law of the forward process; this is typically done by training neural networks on a score matching objective (Hyvärinen) 2005 Vincent 2011 Song Ermon 2019).
Providing precise guarantees for estimation of the score function is difficult, as it requires an understanding of the non-convex training dynamics of neural network optimization that is currently out of reach. However, given the empirical success of neural networks the score estimation task,
Department of EECS at University of Californa, Berkeley, s aaneesasss harvard edu. 1 DDpparmmnnt of Mathematics Massachusetts Institute of Technology, schewi@mite edu. Part of this work was done while SC was a research intern at Microsoft Research.
*Mierosoft Research, fersseficrosoft.. com.
crosoft
Microsoft Research and Machine Learning yuanzhil 1endrewwww.....r cmu. edu.
Department at Carnegie Mellon
University,
Microsoft Research, adi Liallsalii imeeiiieeirr crosoff......t.....mmmmm.mmm.... com. com.
Departments of Biostatistics & Bioinformatics, Computer Science, Mathematics, and Statistical Science Duke University, anru whro..zanggduue..com

---

Published as a conference paper at ICLR 2023
natural and important question is whether accurate score estimation implies that SGMs provably converge to the true data distribution in realistic settings. This is a surprisingly delicate question, as even with accurate score estimates,
explain in Section 2.1 there are several other sources of emoor which could cause the SGM to fail to converge. Indeed, despite a flurry of recent work (Block
et al. 2020 De Bortoli et al. 2021 De Bortoli 2022] [ee al. 2022a [Pidstrigach; [022] Liu et al.
2022
prior analyses fall short of answering this question, for (at least) one of three main reasons:
1. Super-polynomial convergence. The bounds obtained are not quantitative (c.g.. De Bortoli et al. 2021 Pidstrigach| 2022), scale exponentially in the dimension and other problem parameters like time and smoothness (Block et al., 2020) De Bortoli, 2022 Liu et al. 2022). and hence are typically vacuous for the high-dimensional settings of interest in practice.
Strong assumptions on the data distribution. The bounds require strong assumptions on the true data distribution, such as log-Sobelev inequality (LSI) (see, e.g., [Lee e.g.,Leee et al. (022a). While the LSI slightly weaker than strong log-concavity, it ultimately precludes the presence of substantial non-convexity, which impedes the application of these results to complex and highly multi-modal real-world data distributions. Indeed, obtaining a polynomial that holds for
convergence analysis for SGMs distributions posed an open question in (Lee et al. 2022a).
Strong assumptions on the score estimation error. The bounds require that the score estimate is L -ccurraee (i.e., uniformly accurate), as opposed to I.e-accurate (see, e.g., De Bortoli et al. 2021). This is problematic because the score matching objective is an I,² loss (see Section A.] in the supplement), and there are empirical studies suggesting that in practice, the score estimate is not fact _ -cccuraee (e.g.. Zhang & Chen 2022). Intuitively, this because we cannot expect that the score estimate we obtain will be accurate in regions of space where the true density is very low, simply because we do not expect to see many (or indeed, any) samples from there.
Providing an analysis which goes beyond these limitations a pressing first step towards theoretically understanding why SGMs actually work in practice.
1.1 OUR CONTRIBUTIONS
In this work, we take a step towards bridging theory and practice by providing a convergence guarantee for SGMs, under realistic (in fact, quite minimal) assumptions, which scales polynomially in all relevant problem parameters. Namely, our main result (Theorem (2) only requires the following assumptions on the data distribution q. which we make more quantitative in Section
A1 The score function of the forward process is L-Lipschitz.
A2 The (2 + -/h moment of is finite, where 7) > 0 is an arbitrarily small constant.
A3 The data distribution has finite KL divergence w.r.t. the standard Gaussian.
We note that all of these assumptions are either standard or, in the case of A2, far weaker than what needed in prior work. Crucially, unlike prior works, we do not assume log-concavity, an LSI, or dissipativity; hence, our assumptions cover arbitrarily -onncae--oncave data distributions. Our main result summarized informally as follows.
Theorem 2). Under assumptions A1-A3, and if the score estimation error in L2 is at most Ö(E), then with an appropriate choice of step size, the SGM outputs a measure which is e-close in total variation (TV) distance to in ((L'd/= iterations.
Theorem 1 (informal,
Our iteration complexity is quite tight: it matches state-of the-art discretization guarantees for the Langevin diffusion /Vempala & Wibisono, 2019: Chewi et al. 2021a).
We find Theorem surprising, because shows that SGMs can sample from the data distribution g with polynomial complexity, even when q is highly non-log-concave (a task that is usually intractable). provided that one has access to an accurate score estimator. This answers the open question of (Lee et al. 2022a) regarding whether or not SGMs can sample from multimodal distributions, e.g.. mixtures of distributions with bounded log-Sobolev constant. In the context of neural networks, our result implies that long the neural network succeeds at the score estimation task, the remaining part of the SGM algorithm based on the diffusion model is completely principled, in that it admits a strong theoretical justification.
2

---

Published as a conference paper at ICLR 2023
In general, learning the score function is also difficult task. Nevertheless, result opens the door to further investigations, such as: do score functions for real-life data have intrinsic (e.g.. low-dimensional) structure which can be exploited by neural networks? A positive answer to this question, combined with our sampling result, would then provide an end-to-end guarantee for SGMs.
More generally, result can be viewed task of learning the score function of the forward process, at least for distributions satisfying our mild assumptions. Existing computational hardness results for learning natural high-dimensional
black-box reduction of the task of sampling to the
distributions like mixtures of Gaussians (Diakonikolas et al. 2017] Bruna et al.) [2021] Guple et al.
2022) and pushforwards of Gaussians by shallow ReLU networks (Daniely & Vardi | et al. (2022abb) thus immediately imply hardness of score estimation for these distributions. To our knowledge this yields the first known information-come comppttttooomttiiooonnnn gaps for this task.
Arbitrary distributions with bounded support. The assumption that the score function is Lips- chitz entails in particular that the data distribution has density w.r.t. Lebesgue measure; in particular, our theorem fails when y satisfies the manifold hypothesis, i.e., is supported on a lower-dimensional submanifold of IR But this is for good reason: it is not possible to obtain non-trivial TV guarantees, because the output distribution of the SGM has full support. Instead, we show in Section 3.2 that can obtain polynomial convergence guarantees in the bounded Lipschitz metric by stopping the SGM algorithm early, or in the Wasserstein metric by an additional truncation step, under the sole assumption that the data distribution q has bounded support, without assuming that q has density. Since data distributions encountered in real life satisfy this assumption, our results yield the following compelling takeaway:
Given an T.-accurate score estimate, SGMs can sample from (essentially) any data distribution.
Critically damped Langevin diffusion (CLD). Using our techniques, also investigate the use of the critically damped Langevin diffusion (CLD) for SGMs, which was proposed in (Dockhorn) ct al. 2022). Although numerical experiments and intuition from the log-concave sampling literature suggest that the CLD could potentially speed up sampling via SGMs, we provide theoretical evidence to the contrary. Based on this, in Section 3.3 we conjecture that SGMs based on the CLD do not exhibit improved dimension dependence compared to the original DDPM algorithm.
1.2
PRIOR WORK
We now provide detailed comparison to prior work. By now, there is vast literature providing precise complexity estimates for log-concave sampling; see, e.g.. Chewi] (202)) for an exposition on recent developments. The proofs in this work build upon the techniques developed in this literature.
However, our work addresses the significantly more challenging setting of non-log-concave sampling.
The work De Bortoli al. (202T) provides guarantees for the diffusion Schrödinger bridge (Song cet al. 2021b). However, as previously mentioned their result is not quantitative, and they require an 1 -accurate score estimate. The works Block et al. (2020): Lee et al. (2022a): Liu et al. (2022) instead analyze SGMs under the more realistic assumption of an a--accurate score estimate. However, the bounds of Block al. [2020): [iu et al. (2022) suffer from exponential dependencies on parameters like dimension and smoothness, whereas the bounds of Lee et al. (2022a) require to satisfy an LSI.
The recent work De Bortoli (2022), motivated by the manifold hypothesis, considers a different pointwise assumption on the score estimation error which allows the error to blow up at time 0 and at spatial oo. We discuss the manifold setting in more detail Section 3..2 Unfortunately, the bounds De Bortoli (2022) also scale exponentially in problem parameters such as the manifold diameter.
We also mention that the use of reversed SDEs for sampling is implicit in the interpretation of the proximal sampler (Lee et al. 2022 1) given by Chen et al. (2022c). Our work can be viewed as expanding upon the theory of Chen et al. 2022c using a different forward channel (the OU process).
Concurrent work. Very recently, Lee et al. (002b) independently obtained results similar to our results for DDPM. While our assumptions score error can vary with time but assume the data is compactly supported), our quantitative bounds stronger. Additionally, the upper and lower bounds for CLD are unique to our work.
technically somewhat incomparable (they assume the
3

---

Published as a conference paper at ICLR 2023
2 BACKGROUND ON SGMs
Throughout this paper, given a probability measure which admits a density w.r.t. Lebesgue measure, abuse notation and identify it with its density function. Additionally, will let denote the data distribution from which we want to generate new samples. We assume that is a probability measure on Rd with full support, and that it admits smooth density written exp( (we relax this assumption in Section 3.2)
In this section, we provide a brief exposition to SGMs, following Song al. (022b))
2.1 BACKGROUND ON DENOISING DIFFUSION PROBABILISTIC MODELING (DDPM)
Forward process. In denoising diffusion probabilistic modeling (DDPM), we start with forward process, which stochastic differential equation (SDE). For clarity, we consider the simplest possible choice, which is the Ornstein-Uhlenber (OU) process
dX, XX, vBdB,
Xg
where (B:) is standard Brownian motion in 12d, The OU process is the unique hime-homogeneous Markov process which is also Gaussian process, with stationary distribution equal to the standard Gaussian distribution 7 on Rd. In practice, it is also common to introduce a positive smooth function g: R IR and consider the time-rescaled OU process
dX, = -g())² X, dt + (2)(t)dBB
Xy ~ q.
Although our analysis could be extended to consider these variants, in this work we stick with the choice = for simplicity; see SSng al. 202Tb) for further discussion.
The forward process has the interpretation of transforming samples from the data distribution g into pure noise. From the well-developed theory of Markov diffusions, is known that g. == law(X,) denotes the law of the OU process time f, then q: 7d exponentially fast in various divergences and metrics such as the Wasserstein metric W2; see Bakry et al. (2014).
Reverse process. If reverse the forward process ① in time, then we obtain process that transforms noise into samples from q, which the aim of generative modeling. In general, suppose that we have an SDE of the form
dx, = (x( o2 dB.
where (ot) is a deterministic matrix-valuet process. Then, under mild conditions on the pro- cess (e.g.. Föllmer 1985 Cattiaux et al., (2022), which satisfied for all processes under considera- tion in this work, the reverse process also admits an SDE description. Namely, if we fix the terminal time T and set
X = Xr-
for t E [0,T],
then the process (Xt) Je(o,,1 satisfies the SDE
dX;-- bi (Xi) dt dB.
where the backwards drift satisfies the relation
b. + bb V
q = law (X,).
(3)
Applying this to the forward process
we obtain the reverse process
dx; = (X; + 2 dt + V2dB,
N ~T
(4)
where now (Bx) (B:) is the reversed Brownian motion! Here, V In is called the score function for qr. Since (and hence 4, for t > 0) is not explicitly known, in order to implement the reverse process the score function must be estimated on the basis of samples. The mechanism behind this is the idea of score matching which goes back to Hyvärinen (205)): Vincent 2011): roughly speaking,
For ease of notation, we do not distinguish hetween the forward and the reverse Brownian motions.
4

---

Published as a conference paper at ICLR 2023
Gaussian integration by parts implies that minimizing the (g)) loss achieved by estimate s for the score V qt is equivalent to minimizing the Lg) loss in predicting, given a sample from the forward process at time t. what noise applied to the corresponding sample at time 0 to obtain it.
We defer an exposition of the details of score matching to Sections A. and of of the supplement.
In light of this, it is thus most natural to assume (g:) error bound Ey |||s: V In qell || c E for the score estimator 8z- If 8, is taken to be the empirical risk minimizer for a suitable function class, then guarantees for the (ge) error can be obtained via standard statistical analysis, see, e.g., Block et al. 2020))
Discretization and implementation. We now discuss the final steps required obtain im- plementable algorithm. First, in the learning phase, given samples X( (((n) from q (e.g.. a database of natural images), train neural network via score matching, see Song & Ermon (2019).
Let h > 0 be the step size of the discretization; we assume that we have obtained a score estimate 8kh of V In qah for each time k 0, 1, ..... N, where T -Nh.
In order to approximately implement the reverse SDE ( we first replace the score function V In qr-t with the estimate -1- Then, for t E [khh, (I: + 1)h] freeze the value of this coefficient in the SDE at time kh. It yields the new SDE
dx; {X;- + -M dt v2dB, E [kh, (A: + 1)h]. Since this a linear SDE, it can integrated in closed form; in particular, conditionally on kh the next iterate X X (k+1)6 has an explicit Gaussian distribution.
(5)
There is one final detail: although the reverse SDE (4) should be started at 4r, we do not have access to qr directly. Instead, taking advantage of the fact that qr R 7 we instead initialize the algorithm at X 77, i... from pure noise.
Let pt == law (X;) denote the law the algorithm at time The goal of this work is to bound TV(PT, g). taking into account three sources of error: (1) estimation of the score; (2) discretization of the SDE with step size h > 0; and (3) initialization of the algorithm at 7 rather than at şr.
2.2 BACKGROUND ON THE CRITICALLY DAMPED LANGEVIN DIFFUSION (CLD)
The critically damped Langevin diffusion (CLD) is based on the forward process
dX, = - V dt,
(6)
dV. = - -(x, + +
Compared to the OU process (T). this is now coupled system of SDEs, where have introduced new variable V representing the velocity process. The stationary distribution of the process is yd the standard Gaussian measure on phase space Rd x Rd and we initialize Xo ~ q and Vo 7
More generally, the CLD (6) is an instance of what is referred to as the kinetic Langevin or the underdamped Langevin process in the sampling literature. the context of strongly log- concave sampling, the smoother paths of X lead to smaller discretization error, thereby furnishing an algorithm with Ō vdd/s) gradient complexity (as opposed to sampling based the overdamped Langevin process, which has complexity Ö(d/e²)). see Cheng al. (0118); Shen Lee (019);; Dalalyan & Riou-Durand (2020); Ma et al. (202T). The recent paper Dockhorn et al. (2022) proposed to use the CLD as the basis for an SGM and they empirically observed improvements over DDPM.
Applying (3) the corresponding reverse process is
dx; = =-V, dt,
dV. = (XF +2V + +4V. vVT) dt 2dB,
where == lawa(x X,, V.)) is the law of the forward process at time f. Note that the gradient in the score function is only taken w.r.t. the velocity coordinate. Upon replacing the score function with an estimate 8, we arrive at the algorithm
dx; =V dt,
dvF (X +2V MM Vi5 dt 2dB, for E [kh, (k+ + 1)4e. We provide further background on the CLD in Section C.
5

---

Published as a conference paper at ICLR 2023
3
RESULTS
We now formally state our assumptions and our main results.
3.1 RESULTS FOR DDPM
For DDPM, make the following mild assumptions on the data distribution q- Assumption (Lipschitz score). For all 2 O, the score V qn is L-Lipschitz.
Assumption 2 (second moment bound). For some n 0, E,lll-1[+**] is finite. We also write
m = El- for the second moment of
For technical reasons, we need assume that g has a finite moment of order slightly but strictly bigger than 2, but our quantitative bounds will only depend on the second moment m
Assumption is standard and has been used in the prior works Block et al. 22200; However, unlike Lee et al. (2022a); Liu et al. (2022). we do not assume Lpschitzness of the score estimate. Moreover, unlike Block al. (2020); De Bortoli et al. (202T): y Liu et al. (2022), we do not assume any convexity or dissipativity assumptions on the potential U, and unlike Lee et al. (022a) we do not assume that y satisfies log-Sobolev inequality. Hence, our assumptions cover wide range of highly non-log-coneave data distributions. Our proof technique is fairly robust and even Assumption
: Lee al. (022a).
D could be relaxed (as well as other extensions, such as considering the time-changed forward process ) although focus the simplest setting in order to better illustrate the conceptual significance of our results.
We also assume bound the score estimation error.
Assumption (score estimation error). For all k = l...,, N, Eges [k
V In
[1 I Excare
This is the same assumption in Lee et al. (202aa). and as discussed in Section 2.1 it is natural and realistic assumption light of the derivation of the score matching objective.
Our main result for DDPM is the following theorem.
Theorem (DDPM, see Section of supplement), Suppose that Assumptions 7 and 3 Let
pt be the oulput of the DDPM algorithm (Section 2.7g at time T, and suppose that the step size = T/N satisfies Z L/L. where 2 1. Then, it holds that
TV(PT, S V /KL(q 11 78) exp(-T) (LVdh Lmah) VT
Excore VT
comsergence of forward process
discretization error
score estimation error
To interpret this result, suppose that, e.g., KL(q |l 74) s poly(d) and m2 (g |l 7)) and = T=a: and hiding logarithmic factors,
d Choosing T
L2d
TV(PT, 9) Ö(E Escore),
for N - θ
In particular, in order to have TV q) S e, suffices to have score eπrоr Escore < Ö(E).
We remark that the iteration complexity N = ((42)) matches state-of-the-ane complexity bounds for the Langevin Monte Carlo (LMC) algorithm for sampling under log-Sobolev inequality (LSI), see Vempala & Wibisono (2019) : Chewi et al.] (2021a). This provides some evidence that our discretization bounds of the correct order, least with respect the dimension and accuracy parameters, and without higher-order smoothness assumptions.
3.2 CONSEQUENCES FOR ARBITRARY DATA DISTRIBUTIONS WITH BOUNDED SUPPORT
We now elaborate upon the implications of our results under the sole assumption that the data distribution is compactly supported, supp 9 C B(0, R). In particular, we do not assume that has
For many distributions of interest, c.g., the standard Gaussian distribution or product measures, in fact we have ma O(vd). Also, for applications to images in which each coordinate (i.c., pixel) lies in a bounded range [-1, 1), we also have ma Vd.

---

Published as a conference paper at ICLR 2023
smooth density w.r.t. Lebesgue measure, which allows for studying the case when q is supported lower-dimensional submanifold of I as in the manifold hypothesis. This setting was investigated recently in De Bortoli (2022).
For this setting, our results do not apply directly because the score function of q is not well-defined and hence Assumption 1 fails to hold. Also, the bound in Theorem 2 has term involving KL xd)
which is infinite if is not absolutely continuous w.r.t. 7dh As pointed out by De Bortoli (002)) in general we cannot obtain non-trivial guarantees for TV(PT: g), because pr has full support and therefore (V q) = 1 under the manifold hypothesis. Nevertheless, we show that we can apply our results using an early stopping technique.
Namely, using the following lemma, we obtain a sequence of corollaries.
Lemma 3 (Lemma 21 in supplement). Suppose that s S B(0, R) where R 2 1, and let qe denote the law of the OU process at time i, started at q. Let ēw2 > 0 be such that ew2 < vd and set t z / V vd).. Then, (1) W2(q., 9) S EW2 (2) qi satisfies KL(g (1))) vavavaa and (3) for every t' 2 t, qe satisfies Assumption 7 with L dR3 dR² (RVVa)"
Fi2
2 we obtain Corollary 4 below. We remark that taking as the new target corresponds to stopping the algorithm early: instead of running the algorithm backward for time T, we run the algorithm backward for a time T (note that should be multiple of the step size h).
By substituting qi for this choice of t in place of q Theorem
Corollary 4 (compactly supported data). Suppose that q is supported on the ball of radius R 2 1. Let t eiy,/ /VVd (R V V Vd)). Then, the output pr of DDPM is ery-close in TV to the distribution qt, which is Ew, -close in W2 to 9. provided that the step size h is chosen appropriately according to
Theorem and N = 5 RC (Jovaay"
and Escore S Õ(evv).
<iv Fi2
Observing that both the TV and Wi metrics upper bounds for the bounded Lipschitz metric (B, v) = sup( pd d f: Rd - [-1, is 1-Lipschitz), we immediately obtain the following corollary.
Corollary 5 (compactly supported data, BI. metric). Suppose that q is supported on the ball of /Vdd (RV vd)). Then, the output pr the DDPM algorithm satisfies (Pr- q) S E, provided that the step size h is chosen appropriately according to Theorem 2 and N = O R (RV /d)///l0) and Escore I ((rv).
radius R 2 1. Let x ew, ew,
Finally, if the output pr of DDPM at time T - l is projected onto B(0, Ro) for an appropriate choice of Ro, then the following corollary.
also translate our guarantees to the standard W2 metric, which state as
Corollary 6 (compactly supported data, W2 metric; see Section B.5 in supplement). Suppose that q is supported on the ball of radius R 2 1. Let t x /VV/ Vd)), and let PT denote the output of DDPM at time T - 1 projected onto B(0, Ro) for Ro = @ Then, it holds that W2(PT-t, 4) S E, provided that the step size h is chosen appropriately according to Theorem 2 N (dd R (RV / and Escore S Ö(Erv).
Note that the dependencies in the three corollaries above are polynomial in all of the relevant problem parameters. In particular, since the last corollary holds in the W₂ metric, it is directly comparable to De Bortoli 2022) and vastly improves upon the exponential dependencies therein.
3.3 RESULTS FOR CLD
In order to state our results for score- baseed generative modeling based on the CLD, we must first modify Assumptions [ and accordingly.
Assumption 4. For all 0, the score V. In qi is L-Lipschitz
Assumption 5. For all k 1, .,. N, Egg [l] [K| V, In qkalk e2 é
7

---

Published as a conference paper at ICLR 2023
If we ignore the dependence on L and assume that the score estimate is sufficiently accurate, then the iteration complexity guarantee of Theorem is N (dd/=2). On the other hand, recall from Section 2.2 that based on intuition from the literature on log-concave sampling and from empirical findings in Dockhorn al. (2022), we might expect that SGMs based on the CLD have a smaller iteration complexity than DDPM. We prove the following theorem.
and hold. Let pr be the output of the SGM algorithm based on the CLD (Section (.2) at time T, and suppose the step size ht == T/N satisfies h S / L, where L 2 1. Then, there is universal constant e > 0 such that TV(PT: y @ 7²) is bounded, up a constant factor, by
Theorem 7 (CLD, see Section of supplement). Suppose that Assumptions
v KKL (4) + FI(4 II 78) exp(-cT) + (Lvdh + Lmzh) VT +
Eecore VT
convergence of forword process
discretization
SCOTE extimaation error
where Fl(q || 78) is the relative Fisher information FI(q || >0) = I [n(1/
Note that the result of Theorem is in fact no better than our guarantee for DDPM in Theorem 2 Although it is possible that this is an artefact of our analysis, we believe that it is in fact fundamental. As we discuss in Remark C.2 from the form of the reverse process ( the SGM based on CLD lacks certain property (that the discretization error should only depend on the size of the increment of the X process, not the increments of both the X and V processes) which is crucial for the improved dimension dependence of the CLD over the Langevin diffusion in log-concave sampling. Hence, in general, we conjecture that under our assumptions, SGMs based on the CLD do not achieve a better dimension dependence than DDPM.
We provide evidence for our conjecture via a lower bound. In our proofs of Theorems 2 and 7 we rely on bounding the KL divergence between certain measures on the path space e( 7] P via Girsanov's 's theorem. The following result lower bounds this KL divergence, even for the setting in which the score estimate is perfect (Escore = 0) and the data distribution q is the standard Gaussian.
Theorem (Section C supplement), Let pr be the output of the SGM algorithm based on the CLD (Section 2.2) at time T, where the data distribution q is the standard Gaussian 7dt and the score estimate exact (Escore = 0). Suppose that the step size satisfies S 1/ V 1). Then, for the path measures Pr and QT of the algorithm and the continuous-time process respectively (see
Section Cfoor details), holds that ( |P) 2 dhT.
Theorem 8 shows that in order to make the KL divergence between the path measures small, we must take h S 1/d, which leads to an iteration complexity that scales linearly in the dimension d. Theorem 8 is not a proof that SGMs based on the CLD cannot achieve better than linear dimension dependence, as it is possible that the output pr of the SGM is close to 9 @ 7d even if the path measures are not close, but it rules out the possibility of obtaining better dimension dependence via our Girsanov proof technique. We believe that it provides compelling evidence for our conjecture, i.e., that under our assumptions, the CLD does not improve the complexity of SGMs over DDPM.
We remark that in this section, we have only considered the error arising from discretization of the SDE. is possible that the score function V, In q: for the SGM with the CLD is easier to estimate than the score function for DDPM, providing a statistical benefit of using the CLD. Indeed, under the manifold hypothesis, the score V In qe for DDPM blows up at t = O, but the score V. In qe for CLD is well-defined at 0, and hence may lead to improvements over DDPM. We do not investigate this question here and leave it as future work.
4 TECHNICAL OVERVIEW
We now give a detailed technical overview for the proof for DDPM (Theorem 2) The proof for CLD (Theorem 7 follows along similar lines.
Recall that we must deal with three sources of error: (1) the estimation of the score function; (2) the discretization of the SDE; and (3) the initialization of the reverse process at yd rather than at 9r-
First, we ignore the errors (1) and (2), and focus on the error (3). Hence, we consider the continuous-time reverse SDE 4 initialized from 7dd (resp. qr) and denote by ýe (resp. q)-
8

---

Published as a conference paper at ICLR 2023
its marginal distributions. Note that Pu 7d and that qu 9. the data distribution. First, us- ing the exponential contraction of the KL divergence along the (forward) OU process, we have (L II^") S exp(-2T) KL(g (+), Then, using the data processing inequality along the backward process, we have TV( S TV(7", (T)). Therefore, using Pinsker inequality, we get
TV(pr, 9) S TV("", (r) S V KL (l) & exp(-T)y KL 7(),
i.e, the output fr converges to the data distribution exponentially fast as T -
Next, we consider the score estimation error (1) and the discretization error (2). Using Girsanov's theorem, these emrors can be bounded by
N-1 Σ
(k+1)h
IM V el )1? de
Jch
(see the inequality (T5) in the supplement). Unlike other proof techniques, such as the interpolation method in Lee et al. (2022a). the error term (8) in Girsanov's 's theorem involves an expectation under the law of the true reverse process, instead of the law of the algorithm (see et al. (2022a)). This difference allows us to bound the score estimation error using Assumption 3 directly, which allows a simpler proof that works under milder assumptions on the data distribution. However, the use of Girsanov's theorem typically requires technical condition known as Novikov's 's condition, which fails to hold under under our minimal assumptions. To circumvent this issue, we use an approximation argument relying abstract results the convergence of stochastic processes. A recent concurrent and independent work Liu et al. 2022) also uses Girsanov's theorem, but assumes that Novikov's condition holds the outset.
CONCLUSION
In this work, we provided the first convergence guarantees for SGMs which hold under realistic assumptions (namely, La-accurate score estimation and arbitrarily non-log-concave data distributions) and which scale polynomially in the problem parameters. Our results take a step towards explaining the remarkable empirical success of SGMs, at least assuming the score is learned with small L error.
The main limitation of this work that we did not address the question of when the score function can be learned well. In general, studying the non-convex training dynamics of learning the score function via neural networks is challenging. but we believe that the resolution this problem, even for simple learning tasks, would shed considerable light on SGMs. Together with the results in this paper, it would yield the first end-to-end guarantees for SGMs.
In light of the interpretation of our result reduetion of the task of sampling to the task of score function estimation, we also ask whether there are interesting situations where it is easier to learn the score function (not necessarily via neural network) than (directly) sample.
REFERENCES
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2005.
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markov diffusion oper- ators, volume 348 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer, Cham, 2014.
Adam Block, Youssef Mroueh, and Alexander Rakhlin. Generative modeling with denoising auto- encoders and Langevin sampling. arXiv e-prints, art. arXiv:2002.001177, 2020.
Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang. Continuous LWE. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 694-707, 2021.
Hanqun Cao, Cheng Tan, Zhangyang Gao, Guangyong Chen, Pheng-Am Heng. and Stan Z. Li. A survey generative diffusion model. arXiv e-prints, art. arXiv:2209.026: (2646, 2022.

---

Published as a conference paper at ICLR 2023
Patrick Cattiaux, Giovanni Conforti, Ivan Gentil, and Christian Léonard. Time reversal of diffusion processes under a finite entropy condition. September 2022.
Sitan Chen, Aravind Gollakota, Adam R. Klivans, and Raghu Meka. Hardness of noise-free learning for two-hidden-layer neural networks, arXiv preprint arXiv:2202.0523 0222522... 2022a.
Sitan Chen, Jerry Li, and Yuanzhi Li. Learning (very) simple generative models is hard. arXiv preprint arXiv:2205. /6003, 2022b.
Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for a proximal algorithm for sampling. In Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 9984-3014. PMLR, 7 2022c.
Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, and Michael I. Jordan. Underdamped Langevin MCMC: a aoy-asymiio analysis. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.). Proceedings of the 31st Conference on Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 300-323, PMLR, 2018.
Sinho Chewi. Log-concave sampling. 2022. Book draft available at htttps://chewissettt
github. io/]
Sinho Chewi, Murat A. Erdogdu, Mufan B. Li, Ruoqi Shen, and Matthew Zhang. Analysis of Langevin Monte Carlo from Poincaré to log-Sobolev. arXiv e-prints, art. arXiv:2112.12662 2021a.
Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic, and Philippe Rigollet. Optimal dimension dependence of the Metropolis-adjusted Langevin algorithm. In Mikhail Belkin and Samory Kpotufe (eds.), Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 1260-1300. PMLR, 8 2021b.
Florinel-Alin Croitoru, Vlad Hondru, Radu Tudor Ionescu, and Mubarak Shah. Diffusion models in vision: a survey. arXiv e-prints, art. arXiv:2209.04770 2022.
Arnak S. Dalalyan and Lionel Riou-Durand. On sampling from log-concave density using kinetic Langevin diffusions. Bernoulli, 16(3):1956-199 1988, 2020.
Arnak Dalalyan, Avetik Karagulyan, and Lionel Riou-Durand. Bounding the error of discretized Langevin al algorithms for non-strongly log-concave targets. arXiv e-prints, art. arXiv: 1iii::99000833000 June 2019.
Amit Daniely and Gal Vardi. From local pseudorandom generators to hardness of learning. In Conference on Learning Theory, pp. 1358-1394. PMLR, 2021.
Valentin De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. arXiv e-prints, art. 1xXi:22288005144 2022.
Valentin De Bortoli, James Thornton, Jeremy Heng, and Arnaud Doucet. Diffusion Schrödinger bridge with applications to score-based generative modeling. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan Advances in Neural Information Processing Systems, volume 34, pp. 17695-17709. Curran Associates, Inc., 2021.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat GANs on image synthesis. In M. Ranzato, Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 8780-8794 Curran Associates, Inc., 2021.
Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 73-84. IEEE, 2017.
Tim Dockhor, Arash Vahdat, and Karsten Kreis. Score-based generative modeling with critically- damped Langevin diffusion. In International Conference Learning Representations, 2022.
Hans Föllmer. An entropy approach to the time reversal of diffusion processes. In Stochastic differential systems Caarseille-Luming 1984), volume 69 of Lect. Notes Control Inf. Sci., pp. 166-163. Springer, Berlin, 1985.
10

---

Published as a conference paper at ICLR 2023
Apama Gupte, Neekon Vafa, and Vinod Vaikuntanathan. Continuous LWE is hard as LWE & applications to learning Gaussian mixtures. arXiv preprint arXivv2204.025550 2022.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in 2020.
Neural Information Processing Systems,
Aapo Hyvärinen. Estimation of non-normalized statistical models by matching. J. Mach. Learn. Res., 6:695-709, 2005.
Diederik Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 21696-21707. Curran Associates, Inc., 2021.
Jean-Free Cran-François Le Gall. Brownian motion, martingales, and stochastic calculus, volume 274 of Graduate Texts in Mathematics. Springer, [Cham], French edition, 2016.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. arXiv e-prints, art. arXiv:2206.06227, 2022a.
Holden Lee, Jianfeng Lu, and Yixin Tan, Convergence of score-based generative modeling for general data distributions. 2022b.
Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Structured logconcave sampling with a restricted Gaussian oracle. In Mikhail Belkin and Samory Kpotufe (eds.), Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 Proceedings of Machine Learning Research, pp. 2993-3050. PMLR, 8 2021.
Xingchao Liu, Lemeng Wu, Mao Ye, and Qiang Liu. Let us build bridges: understanding and extending diffusion generative models. arXiv preprint arXiv:2208. /4699, 2022.
Yi-An Ma, Niladri S. Chatterji. Xiang Cheng, Nicolas Flammarion, Peter L. Bartlett, and Michael L. Jordan. Is there an analog of Nesterov acceleration for gradient-based MCMC? Bernoulli, 27(3): 1942 1992, 2021.
Dan Mikulincer and Yair Shenfeld. On the lipschitz properties of transportation along heat flows. arXiv preprint arXiv:2201.0 003382, 2022.
S. G. Bobkov, I. Gentil and M. Ledoux. J. Math. Pures Appl. (9), 80(7):697-700, 2001. Felix Otto and Cédric Villani. Comment on: "Hyyercontractivvty Hamilton-Jacobi equations", by
Jakiw Pidstrigach. Score-based generative models detect manifolds, utXiv:2206.0001 2022.
arXiv e-prints, art.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with CLIP latents. arXiv preprint arXiv:2204.06115, 2022.
Paul T. V. Rolland. Predicting uncertain environments: methods for robust machine learning. PhD thesis, EPFL, 2022.
Ruoqi Shen and Yin Tat Lee. The randomized midpoint method for log-coneave sampling. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Allcé-Buu Buc, E. Fox, and R. Gamnet (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan. and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 2256-2265, 2265, Lille, France, 2015. PMLR.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-BBi Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.
11

---

Published as a conference paper at ICLR 2023
Yang Song. Conor Durkan, lain Murray, and Stefano Ermon. Maximum likelihood training of score- based diffusion models. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 1415-1428. Curran Associates, Inc., 2021a.
Yang Song, Jascha Sohl-Dickstein. Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. International Conference on Learning Representations, 2021b.
J. Michael Steele. Stochastic calculus and financial applications, volume 45 of Applications of Mathematics (New York). Springer-Verlag, New York, 2001.
Arash Vahdat, Karsten Kreis, and Jan Kautz. Score-based generative modeling in latent space. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 11287-11302. Curran Associates, Inc., 2021.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algorithm: isoperimetry suffices. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Allcé-Burt Bucé E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8094-8106. Curran Associates, Inc., 2019.
Cédric Villani. Hypocoercivityy Mem. Amer. Math. Soc., 202 141, 2009.
Pascal Vincent. A connection between matching and denoising autoencoders. Neural Comput., 2367)1661-1164, 2011.
Ling Yang, Zhilong Zhang, Shenda Hong, Wentao Zhang, and Bin Cui. Diffusion models: comprehensive survey of methods and applications. arXiv e-prints, art, XxXiv2220.00079 2022.
Qinsheng Zhang and Yongxin Chen. Fast sampling of diffusion models with exponential integrator. arXiv e-prints, art. arXiv:2204.1 13902, 2022.
12

---

Published as a conference paper at ICLR 2023
A PRELIMINARIES
In this section, we review the notion of score matching and provide list of notation for the proofs.
A.
PRIMER ON SCORE MATCHING
In order to estimate the score function V In qr, consider minimizing the (g) loss over a function class 9,,
minimize 5,E3F
Egg [1ls
V In q:l?),
where & could be, e.g,, class of neural networks. The idea of score matching, which goes back to Hyvärinen (2005); Vincent (201T), is that after applying integration by parts for the Gaussian measure, the problem equivalent to the following problem:
minimize 9.E.3F
(x,) + V1-expo exp(1p2-21
7z
(10)
where Ze ~ normal(O, La) is independent of Xo and X; = exp(-t) (t) 1) Xo exp(-2)) Z. the sense that (9) and (10) share the same minimizers. We give self-contained derivation in Appendix D for the sake of completeness. Unlike (9. however, the objective in (I0) can be replaced with an empirical version and estimated on the basis of samples x
(()) from leading to the
finite-sample problem
1 Σ (((
z
minimize E
+
V exp( (-t)
where (z )im| are iid. standard Gaussians independent of (Xx²) /E(x]- Moreover, if we parame- VI exeexp(-2) 2, then the empirical problem is equivalent to
terize the score as
Σ |x((X - 1,
minimize
8 SE-VI-exy
which has the illuminating interpretation of predicting the added noise z from the noised data x((), i.e., denoising.
NOTATION
For measurable mapping T'; X + X and measure on X, where X is a measurable space, the notation Ty refers to the pushforward of fa by the mapping T,, i.e. X ~ μ4, then T(X) ~ Tape.
Stochastic processes and their laws.
The data distribution is = =Qo-
The forward process
is denoted (X.) and Xt ~ g:.
The reverse process is denoted (X; )11 where 8,- XT-2~ fr-t-
is denoted (X; (X;")e and X;- ~ Pt. Recall that we initialize at Po = the standard Gaussian measure.
The SGM algorithm
The process
)eejorr) is the same as "x"eeeorr except that we initialize this process at qr rather than at 7d We write X ~ pp
Conventions for Girsanov's theorem. When apply Girsanov's theorem, it is convenient to instead think about single stochastic process, which for ease of notation we denote simply via (Xt) T and consider different measures over the path space e((o, 7]: 1R.).
The measures consider path space are:
13

---

Published as a conference paper at ICLR 2023
QF, under which (Xe)ce) has the law of the reverse process
PT", under which (Xt) (Xt)eejo,T has the law of the SGM algorithm initialized at (conre- sponding to the process (X; """"""""" )eeoorry defined above).
We also use the following notion from stochastic calculus (Le Gall 2016 Definition 4.6):
A local martingale (Cr) is stochastic process s.t. there exists sequence of non- decreasing stopping times Т, T s.t. _ (LINTa rejo,,) is martingale.
Other parameters. We recall that > denotes the total time for which we run the forward process; /t >> 0 is the step size of the discretization; L > 1 is the Lipschitz constant of the score function; m == Eg [II-|12]] is the second moment under the data distribution; and Escore is the L score estimation error.
Notation for CLD, The notational conventions for the CLD are similar; however, we must also consider velocity variable V. When discussing quantities which involve both position and velocity (e.g., the joint distribution qe of (Xe, V()), we typically use boldface fonts.
B PROOFS FOR DDPM
B. PRELIMINARIES ON GIRSANOV'S THEOREM AND A FIRST ATTEMPT AT APPLYING GIRSANOV'S THEOREM
First, recall consequence of Girsanov's 's theorem that be obtained by combining Pages Theorem 5.22, and Theorem 4.13 Le Gall (2016).
Theorem 9. For [). let L, b, dB, where B is Q-Brownian motion. Assume that Eq S0 1b.112d ds cc. Then, L is Q-martingale in (Q). Moreover, if
EQ 8(C)T 1 where e(C); = exp exp(S. by dB.
2 '/ |1b.11 ds)
1
(11)
then ((L) is also a Q-martingale and the process
ト B, [ b.ds
is Brownian motion under P = E(C)2 Q, the probability distribution with density E(C)r w.n.t Q.
If the assumptions of Girsunov's theorem are sutisfied (i.e., the condition 11 we can apply Girsanov's theorem to Q =Q and
b, 22 (Xtr) V In (x.))-(X))),,
where E [kh, (k: + 1)k). This tells us that under P. E(C)T QF, there exists a Brownian motion (Bt)eejo,ry s.t.
dB, = (s -x.)r-(XX.)) di d3.
(12)
Recall that under Q we have a.s.
dX, 2
v2dB,,
Xo 4T
(13)
The equation above still holds P-a.s. since P & Q (even if B is longer P-Brownian motion). Plugging (12) into (13) we have P-a.s.
dX, = (X, 2 28T dt v2d3, Xo ~ qr
We still have Xo gr under P because the marginal time t 0 of P is equal to the marginal at time t of Q7. That consequence of the fact that E(C) is (true) QT -martingale.
14

---

Published as a conference paper at ICLR 2023
In other words, under P, the distribution of X is the SGM algorithm started at qr, i.e. P = P. ((C)r QT Therefore,
dQF aP = RQz In E(2)T)
KL(QF] PT") = Eoz In
(14)
(k+t))
BQF
Wh Vingr- dt,
kh
where we used Eq7 L, = 0 because is a martingale.
The equality 14 allows to bound the discrepancy between the SGM algorithm and the reverse process.
B.2 CHECKING THE ASSUMPTIONS OF GIRSANOV'S S THEOREM AND THE GIRSANOV DISCRETIZATION ARGUMENT
In most applications of Girsanov's 's theorem in sampling. sufficient condition for 11 to hold, known as Novikov's 's condition, is satisfied. Here, Novikov's condition writes
(k+1)h || un Vin < 0o,
exp
k= kh
apply Girsanov's theorem directly. However, under Assumptions I. 2 and 3 alone, Novikov's condition need not hold. Indeed, order to check Novikov's condition, would want X, to have sub-Gaussian tails for instance.
and if Novikov's 's condition holds,
Furthermore, we also could not check that the condition [T), which is weaker than Novikov's condition, holds. Therefore, in the proof of the next Theorem, show that
approximation technique to
dQF
KL(QF PIT) Boz In dppr S Eqz In ((()))
(15)
(k+1)h
Bey
||sT (XRn)
V (x)rr de.
kh
We then use a discretization argument based on stochastic calculus to further bound this quantity. The result the following theorem.
Theorem 10 (discretization enror for DDPM). Suppose that Assumptions 7 and 3 hold. Let QT and Pu denote the measures on path space corresponding to the reverse process and the SGM algorithm with 1/2 -accurrat score estimate initialized Qr. Assume that I 2 and S 1/L. Then,
TV(PFT - KL(QF P S (=2core + L2dhh dh + L2 222222) T
Proof. We start by proving
N
(k+1)h
BQF
18T (Xaa) - In (x.))1 S (s T.2th 1.2m31?)7 T.
k=0
ksh
Then, we give the approximation argument to prove the inequality (15).
Bound on the discretization error. For t e [kh, (k + 1)4], we can decompose
Eoz In V (X)))1
S E ||| |T n (Kan) V un (X&a)1
EQ; V In QT -t- (Xxn) - V o
+ Eo²
V (XHb)
(xx))=((X;)13
kh (Xxx) 1
2
Eoj
V
1,2 Bez |1| X X,113.
(16)
-r
15

---

Published as a conference paper at ICLR 2023
We must bound the change in the score function along the forward process. If S R - R T is the
mapping S(x) = exp(- (((t
kh)) 2, then 9h = - normal(0, exp( (t))
We can then use Lee et al. (2022a Lemma C.12) (or the more general Lemma T7 that we prove in
Section C.4 with a = exp(1
kh)
= 1 + (hh) and o² = - exp( - kh)) O(h) to obtain
In
Gr 9r-kh (Xan)
||
- L2 L²h² MM + L2) h2
V In [
9T
X L2 L3 1| | (Xm)-
where the last line uses L 2 1. For the last term,
V (
V h V -V V Vinrr((X))*
V In ( (x.)l + 1.2 | X
where the second term above is absorbed into the third term of the decomposition (16) Hence,
Eog sT ( V (X))I
2 + dh + L2 Eqg X 1
+ 1hhh2 1 V In (x,))
L' E0 [| -X,1
Using the fact that under QF, the process (X the time reversal of the forward process (X (Xe)xe(o.T) we can apply the moment bounds in Lemma 11 and the movement bound in Lemma 12 to obtain
Eoz
sT - (X)))
2 + L2dh L (d+ mb) + dd L2 (mīh² + dh)
2 senre + Ih LL²
Approximation argument. For E [0, let Loe = S0 dB, where B is a QF Brrownian motion and we define
V Vlnqr-((x)),,
for t [kt, (k + 1)4). We proved that l8,; 1or ||ba ds S (E2core + L2dh + L2m3 < co. Using Le Gall 2016 Proposition 5.11), (E(4)t) is local martingale. Therefore, there exists con-decreasing sequence of stopping times Tn / T s.t. (E(A))AT,)ss [ee(..e] martingale. Note that E(C)AT, = E( where & LIAT.. Since E(C") is martingale, have
Eor E((")T = Bez E(C")o 1,
i.e. RoF E(()T. 1.
We apply Girsanov's theorem to LT = - Io. (s) where is a QT Qr-Bnonnian mo- tion. Since E2z /T |bb (s)r ds < Eoz ST | ds < oo (see the last paragraph) and Eo= E((")r 1, we obtain that under pm = E(L"), I QT there exists Brownian motion 3" s.t. fort E [0,T].
dB, (2 V ((ngr-((X)) (1. di d
Recall that under Q we have a.s.
- -x. (x+2 V Xo 4r
The equation above still holds pa-a.s since pm & Q Combining the last two equations we then obtain pa -a.s..
dx,- (X,+2 ST en (Xen)) ( (1) di ( (().))(() d1+ 22 (17)
16

---

Published as a conference paper at ICLR 2023
and Xu 9r In other words, P is the law of the solution of the SDE 17 the bound
At this stage have
TT (/h llb, ds
TT
KL(QF || P*) - Ber In ((C)) = Ber [ +
= -EFF 2
lbb.l
ds
2
/ 1|b,l1 2 ds S (E L2 + L m2 <EaT 2
1
where used that E Lr, because & is QF -martingale and Tn is bounded stopping time (Le Gall 2016 Corollary 3.23). Our goal now to show that we can obtain the final result by an approximation argument.
We consider coupling of (P") Pf sequence of stochastic processes (X") (X")ee same probability space, a stochastic process X and single Brownian motion W over that space s.t
neeN over the
dx;"" = {X, +2 (XHx) (o.r., dt t (X, +2 (t),, dt v
and
dx, (X, + 2ST-MM (X dt + v2dW,,
with X, = =X a.s. and Xo 9r- Note that the distribution of X (resp. X) is Pm (resp. PfT)
Let E > 0 and consider the map [];
e( RR: defined by
Ne (w))((() w(t AT
Noting that X," X, for every E [0, T.] and using Lemma 13 we have x=(X") - (X) a.s., uniformly over [0, T). Therefore, T Pm Te P weakly. Using the lower semicontinuity of the KL divergence and the data-processing inequality (Ambrosio al. 2005 Lemma 9.4.3 and Lemma 9,4.5), we obtain
(L((Te)+ |l (Te) s LiminfKL((TT)e) n
(Tt)*
li KL || P")) n+x
2 (5 (cooe + L2 + L 12m??
Finally, using Lemma 14 Tee (w) - w as 8 + 0, uniformly over [0. T Therefore, using Ambrosio
al. 2005 Corollary 9.4.6), KL (LT(TT) QF (Te) # P KL Pf") as ' 0. Theretore,
KL(QF P(T) S (2200r + L2 + 12 T.
We conclude with Pinsker's inequality (TV2 & KL).
B.3 PROOF OF THEOREM 2
We can now conclude our main result.
Proof of Theorem
We recall the notation from Section 4 By the data processing inequality, TV(pT. < TV(Pr,PPT) + TV(PPT Q+) < TV 78) + TV(P QT).
Using the convergence of the OU process KI. divergence (see, e.g., Bakry et al. 2014 5.2.1) and applying Theorem 10 for the second term,
Theorem
TV(pr. g) / KL (d) exp(-T) + (Escore LV + Lmzh) VT,
which proves the result.
*Such coupling always exists, see Gall 2016
Corollary 8.5).
17

---

Published as a conference paper at ICLR 2023
B.4 AUXILIARY LEMMAS
In this section, prove some auxiliary lemmas which are used in the proof of Theorem 2 Lemma 11 (moment bounds for DDPM). Suppose that Assumptions and 2 hold. Ler (Xe) denote the forward process
1. (moment bound) For all t 2 0,
x.Il s d m
2. (score function bound) For all t 2 0,
E B (x)) Ld.
Proof.
1. Along the OU process, we have X₂ - exp(--t + /1 (0-(xxxp(22) where
{ ~ normal(O, La) is independent of Xo. Hence,
[ = exp( - 2t) X + (1-xpppp1111111--11111111 d S d m
2. This follows from the L-smoothness of In q. (see, e.g.. Vempala & Wibisono 2019
Lemma
9). We give short proof for the sake of completeness.
If Ltf Af (VU, f) is the generator associated with da exp(-U,) then
0 = ge LU, E.g. AU, E (1V.,11 S Ld - E. [1
Lemma 12 (movement bound for DDPM). Suppose that Assumption 2 holds. Let (X1)1ej0,27 denote 8, if S 1, then
the forward process
For with
E| x=1 S 52 + ód.
Proof. We can write
B| - X.1111 E |||- / 8, + v2(B. - B.)
$ E[| 5d 8 (d m3 + 5d
$ 8 m + 5d,
where we used Lemma
We omit the proofs of the two next lemmas as they straightforward.
Lemma 13. Consider fnz f [0, 7] Rd there exists an increasing sequence (Tx)neN S [0, T] satisfying the conditions
T, T + co,
fx(t) = f(t).fo for every $ Tr.
Then, for every > 0. fn + uniformly over [0, T - E). In particular, fal: fA(:AT -c) + f(AAT-AA-- - uniformly over [].
Lemma 14. Consider f: [0, + Rd continuous, and fe [o, T] + Rd s.t. fc(t) = f( (T -)))
for 0. Then fc + uniformly over (0, T] 0.
18

---

Published as a conference paper at ICLR 2023
B.5 PROOF OF COROLLARY 6
Proof of Corollary 6 For Ro > O, let IR denote the projection onto (00, Ro). We want to prove
that W2 (2(( no PPT -P 4)
We use the decomposition
( PT P 4) < (o) RTT (b) + (2 # q)
For the first term, since (TT ) Pr and (IT Ro) # both have support contained in B Rg) can upper bound the Wasserstein distance by the total variation distance. Namely, Rolland (002
Lemma 9) implies that
RI #Pr-c. [R - Roy (V((IIR)) (IR.)) # + Ro exp(
By the data-pross processson inequality,
TV( ( #Pr-4 ( TV(pr-1,9) SVVV
where erv is from Corollary yielding
W2 (IT #Pr-t, n x Roverv + Ro exp(-Roo) Ro).
Next, we take Ry 2 so that (II,,) 7 = 9. Since HR is I-Lipschitz, we have
(2 # (. 9) (2((RRR.)) # (II,,) #4) S W2(9,, q) S EW2
where ew, is from Corollary 4 Combining these bounds,
W2 (T
Ruverv Ro cxp(- Ro) EW2
We now take Ew, e/3, Rg (Rt), and STV = O(s"/ to obtain the desired result. The iteration complexity follows from Corollary
C PROOFS FOR CLD
C.I BACKGROUND ON THE CLD PROCESS
More generally, for the forward process we can introduce a friction parameter y >> 0 and consider
dX, V, dt, dV, = -X, dt - Vz + /2ydBB
we write 0, = (X,, V.), then the forward process satisfies the linear SDE
0
0
d0, A, dt + M, dBc,
where A,
-1 -7 and En
[v27]
The solution to the SDE is given by
0, = exp(IA,, 0o exp((l- A,} dB.,
(18)
which means that by the Itō isometry,
law(O.) exp(tA,)) (aw) normal (o. (o. f''epp((t exp s) A, E,E, exp s) A,) ds).
Since det A., = 1, A., is always invertible. Moreover, from tr A, = -y, one can work out that the spectrum of A, is
spec( (A,) 7
However, A, is not diagonalizable. The case of 7 = is special, as it corresponds to the case when the spectrum is {-1]. and corresponds to the critically damped case. Following Dockhorn et al. (2022), which advocated for setting 7 2, we will also only consider the critically damped case. This also has the advantage of substantially simplifying the calculations.
19

---

Published as a conference paper at ICLR 2023
C.2 GIRSANOV DISCRETIZATION ARGUMENT
In order to apply Girsanov's 's theorem, we introduce the path measures Pf and Q under which
dX; di, dV. = {.X, + + Van)) dt 2dB,
fort E [kh, (k + 1)4 and
dX, -V, dl; dV, = + 2 + +V, -. V() dt + 2dB,
respectively.
Applying Girsanov's theorem, we have the following theorem.
Corollary 15. Suppose that Novikov's condition holds:
N-1
(k+1)
(R Vin) - V. In ( Voll2 dt) co.
EoF exp
k=0
kb
Then,
dQt dP
KL(QT
Ptr) = oF In
[K+1JA
2
EQr
(M Vin) V, In 12)
Similarly Appendix B.2 even if Novikov's condition does not hold, to argue that the KL divergence is still upper bounded by the last expression. Since the argument follows along the same lines, omit it for brevity.
approximation
Using this, we now aim to prove the following theorem.
Theorem 16 (discretization error for CLD)). Suppose that Assumptions 2 and hold. Let Q and P denote the measures path space corresponding the reverse process 7 and the SGM algorithm with I -accurate score estimate initialized at qr- Assume that L 2 1 and h S 1/L. Then,
TV(P ²7)²s KL(QT PPT) S (E2coro + I. I m
Proof. For t [kh, (k: + 1)h},
decompose
Eqz [h) (X VRa) v. In qr vo)
$ EQ; [||ST- kn (XRR, ViA) - V, In qr (KRb, VeA |1
+ EQg V In yT uo VkA) V. In qr - V1a
+ Eqg V, In q VRn) V. In 12)
S 2 + Eq;
V In -h- (Xun, Veaa)
|1]
+ L Eqg []((EA, Vin) (Xe. 119
dr
The change in the score function is bounded by Lemma 17 which generalizes Lee et al. (002aa Lemma C.12). From the representation (18) of the solution the CLDD, note that
qr = -Mo) 91 - normal(0, M,)
with
Mo = exp((1 - kh) A2),
Mi (-¹ /-ah exp((t kh 3) A2) 2n21T exp( kh AT) ds.
20

---

Published as a conference paper at ICLR 2023
In particular, since A| lop & 1, llp and | lopp = Ohh.. Substituting this into Lemma
1, and
Σg
lopp S 1 follows that |M loop 1 Oh)
17
we deduce that h S 1/L, then
V. In 9h (XEn, Van)
V In
qT -T-kh kh
(Xua, VaA)
-r-t
9r
x dh + 1.2 KA
|IVEN (2) + (1 12 1²2 | In (Xan, VEA)
x L' + h² (||
[VV=, 12h V qn Vin)ll
where in the last step we used L 2 1.
For the last term,
V In ( 2l < | In (X,, Vi) + L2 [[( Ven) (X,, VoIl where the second term above absorbed into the third term the decomposition (19). Hence,
Eqg [1 An (Xan, V&A) V. In (X,, V=)
acome + ddh h + h² E MA + |IVRn 13]
122 Bq [1 In @r qr vo)11
+ La; [l] (Xtr, V(A) - (X,, vo)
By applying the moment bounds in Lemma together with Lemma on the movement of the CLD process, we obtain
Eoj ST (a (Xeh, ViA) V, In qr Ve)1
Score + dh + 122 (d + m²) + dh + L (dh + m²)²)
2
Scooe + dh + m²?
The proof is concluded via an approximation argument as in Section B.2
Remark. We now pause to discuss why the discretization bound above does not improve upon the result for DDPM (Theorem TOp. the context log-concave sampling, one instead considers underdamped Langevin process
dX, Ve,
dV, = dt - 7 Vt
d2ydB.
which is discretized to yield the algorithm
dX. Ve,
dV: = -
22
for t E [kth, (k + 1)h). Let Pr denote the path measure for the algorithm, and let QT denote the path measure for continuous-time process. After applying Girsanov's theorem, we obtain
1
(k+1)h
kL PT)
Σ
Eqr
(XU( VU (I
k=
In this expression, note that VU depends only on the position coordinate. Since the X process is smoother (as do not add Brownian motion directly to X), the error [XX))) VU (Xxx)]) is of size Odd??) which allows underdamped Langevin diffusion leads to improved dimension dependence for log-concave sampling.
take step size h. S 1/ id. This explains why the of the
In contrast, consider the reverse process, in which
N-1
(k+1)}
KL(QT P =
Eoz
||sT (N Via) V, In qr Vi)l dr.
0=
kh
Since discretization of the reverse process involves the score function. which depends on both X and V, the eтror now involves controlling V[V Viall which is of size O(dh) (the process V is not very smooth because includes a Brownian motion component). Therefore, from the form of the reverse process, we may expect that SGMs based on the CLD do not improve upon the dimension dependence of DDPM.
In Section C we use this observation in order to prove rigorous lower bound against discretization
of SGMs based on the CLD.
21

---

Published as a conference paper at ICLR 2023
C.3 PROOF OF THEOREM
Proof of Theorem
7 By the data processing inequality.
(P qo I TV PT") TV(PF" QT) S TV(gr, 7 + (T QT).
In Ma et al. (022)) following the entropic hypocoercivity approach of Villani (2009). Ma et al.
consider Lyapunov functional L which is equivalent to the sum of the KL divergence and the Fisher information,
L( م = KL > + F1( >²*)
which decays exponentially fast in time: there exists universal constant >> 0 such that for all 2 0.
L Lg || ) = exp( L(go || 2d)
Since go = q @ 7d and 222 7dh @ nd then L(go || 22d) S KL(g |I 74) + FI(g 7d). By Pinsker's
inequality and Theorem 16 we deduce that
TV(pT. (o) - V KL ll (d) + FI(q ll (8) cxp(-cTp + (Escore + LVdh dh + Lmah) vT,
which completes the proof.
C.4 AUXILIARY LEMMAS
We start with a perturbation lemma for the score function.
Lemma 17 (score perturbation lemma). Let 0 Ç < 1. Suppose that Mo, M1 E 2dx2d two matrices, where M1 is symmetric. Also, assume that [|M Izallop I G, so that Mo is invertible. Let q = ()) be a probability density on 2ddd such that V L-Lipschitz with L S M. Then, it holds that
(Mo) # q normal(O, Mi) (0) $ LV |M |6 + ( L M lop) (H))
In
Proof. The proof follows along the lines of Lee et al. (2022a Lemma C.12). First, show that when Mo Iza, if
S 2 M Top
then
q normal(O, Mi)
O0) S L MM + 1| [VH())]
(20)
q
Let denote the subspace = range Mj. Then, since
(q normal(O, M1) (0) 0+s
exp( - 10 0¹, M,, (0-0))) q(d0))
where M is well-defined on 8, have
* normal(O, Mi)
V In
(0)
q
Sa+8 VH(O) exp (0 0", M, (0-
0')) q(d0')
(H)
Jo4s exp( 0 0', MM (0 - 01))) qdd0')
Eg VH v H (0)ll
Here, go the measure on + such that
qo (d0') x exp( - 2
(0 0', _ (0 (0-)'))) q(d0')
Note that since L < 2 M then if we write qo (0)) x exp(- - -H (H'(')), we have
1
2 H ž ||M
L) la
La 0 + S.
2 Millop
22

---

Published as a conference paper at ICLR 2023
Let 0. arg min He denote mode. We bound
|| VH - ( & L Eo 10 - 0 S L go qo -0.1 + 01 For the first term,
Dalalyan et al. 2019 Proposition 2) yields
Eer~go go 10' - -0.1l S 2| d.
For the second term, since the mode satisfies (H. M, (0, -0-0 0) 0, we have
|0_ 0| < M olp [VH
L M, op |10 01| + || ol / (0)
which is rearranged to yield
0. 0|| s | ol [VH
After combining the bounds, we obtain the claimed estimate (20). Next, we consider the case of general Mo. We have
Vin In (Mo) a * normal Mi)
q
V In (Mo) # q normal(O. Mi)
(Mo) # q
[0)
Vin
(0)
(Mo)
q
We can apply (20 with (Mo) # q in place of q. noting that (Mo) x exp( H') for H' HoMo which is -smoohh for I'' MM Z L,, to get
(Mo) # q normal M)) (0) x M1 d L alp | [M,
V
(Mo)
LV [M d + L M op [
Note that
[ $ (VH + L - 011 S (H 1C ||]|
We also have
(M 9
ln
(0)
V - VH(O))
MoVH((M,) - - [] (M VH
L [lM I2a) 01 + / 1 + (
Combining the bounds,
(Ma) # q normal(0, M,)
V ln
Millop + <C + | 1lop) |la|| + + | (p)p)) (0)I
x L Mi + << 01| (C + L | M
| [()]
so the lemma follows.
Next, we prove the moment and movement bounds for the CLD. Lemma 18 (moment bounds for CLD). Suppose that Assumptions and hold. Let (Xe, Ve)etoo11 denote the forward process (
1. (moment bound) For all 2 0,
E [ Vo) m
23

---

Published as a conference paper at ICLR 2023
2. (score function bound) For all t 0,
(X [.)l Ld.
Proof.
1. We can write
E| (,, PDI = W (0..000 60) S W3 qt, ?2th + (7 ,66) S d W2(g. 721)
Next, the coupling argument of Cheng et al. 2018) shows that the CLD converges exponen- tially fast the Wasserstein metric associated to twisted norm ||IIII which is equivalent (up to universal constants) to the Euclidean norm ||-||- It implies the following result, see, e.g.. Cheng et al. (2018, Lemma 8):
W3 (gt 7 2d) S W (q. 24) W2 60) W2 22d) 2 + m
2. The proof is the same as Lemma 11
Lemma 19 (movement bound for CLD). Suppose that Assumptions 2
holds. Let (Xe, Veleej0.11
denote the forward process (6. For 0 < < t with ê = t 8, i -
E [X,, Vi) (X,, V. 5'm3 + 5d.
Proof. First,
E x.11 = =1] v, dr S S "'EIIVA dr S 6² (d + m3))
where we used the moment bound Lemma 18 Next,
E V. - = |1| ( (-X, 2V,) dr + B.) B.)l 5 = |[V dd
x 6 (d + m3) 8d,
where we used Lemma 18 again.
C.5 LOWER BOUND AGAINST CLD
When proving upper bounds the KL divergence, in Section B.2 in order to invoke Girsanov's theorem. However, when proving lower bounds on the KI. divergence, this approach no longer works, so check Novikov's condition directly for the setting of Theorem
the approximation argument described
Lemma 20 (Novikov's condition holds for CLD). Consider the setting of Theorem condition LS holds.
Then, Novikov's
We defer the proof Lemma 20 to the end of this section. Admitting Lemma
we now prove
Theorem g
Proof of Theoremb Since qo = 8 = > is stationary for the forward process (6) we have
qi > for all t 0. In this proof, since the denote the path measure for the algorithm as P1- P From Girsanov's theorem the form of and from ST (z. v) V, ln An (x, U, have
estimate is perfect and qr 2d simply
Corollary and
N-1
(k+1)A
KL(QT
Pr) 2
Σ
Baz
V
Voll dt.
(21)
kh
k=U
24

---

Published as a conference paper at ICLR 2023
To lower bound this quantity, use the inequality |æ y/1? 2 ||:||² t E [kh, (k + 1)h]
1lvll to write, for
Eoz IIlV voll
BII - -+
kh -2X, ds 2 (Br- Br-
=R T-t
T- {-X, - -2V3] ds 12
BTB||BBTM. -1 -
T-t
T-
2d - kh) - (t - kh)
E|| + 2 V. ds
T-t
T-
2d (t kh) (t kh)
1 | 1| + 8 V. |s
J-1
Using the fact that X, ~ 7dh and V, ~ 7d for all & E [0, T], we can then bound
Eo= V V vi > 2d (t kh) 10d (t kn)² d (t kh),
provided that h < 10. Substituting this into 21
(k+1)
KL(QT Pr) 2 2d
(1 (L- hh) di 2 drT.
This proves the result.
This lower bound shows that the Girsanov discretization argument of Theorem 16 is essentially tight (except possibly the dependence on T.).
We now prove Lemma 20
Proof of Lemma 20
Similarly to the proof of Theorem aboov, we note that
|8 kh kh, VEA) V. In l Vi) = -|Vr-ah kh 12
1-X,-2V,, ds + 2 (B Br-
=
T-1
S 2 sup
(||x,112 [| [V+,11+)+
Br Ball2
sup (k+)-
=E(O,T]
Hence, for universal constant C >>0 0 (which may change from line to line)
N-1
(k+1jA
Eq₁ exp 2
8ST En Van) - V, In 12)1
k=
kh
< Ecxp CTh²
sup (1IX, [1T11 Ch Σ
Br BBll²).
sup SE(T- (k+ [
sE[O.T]
k=
By the Cauchy- Cauchy-Schwarz inequality, prove that this expectation is finite, it suffices to consider the two terms in the exponential separately.
Next, we recall that
dX, = dt
dV. = -(X, + 2 2)) dt + 2dB.
Define Y, = X, + V. Then, dř, =Y, at ddB, which admits the explicit solution
Y, - exp(((-tt Yo 2 / expl-(t dB.
25

---

Published as a conference paper at ICLR 2023
Also, dX,, = -x, dt + Y dt, which admits the solution
=xp( Xu + //- expl-(t-s))
-t- 5]} dt.
Hence,
X + s 2
VAll l|ol + sup
|
sE(0,21
and
+ sup (exp(-1) 1l. exp(s) sE(o.T]
sup rE(o,T]
||a|| - | + ||oo|
Xu
| + sup se[o,T]
|| ((xxp(2))
where B another standard Brownian motion and we use the interpretation of stochastic integrals
as time changes of Brownian motion (ttelle 2001 Corollary 7.1). Since (Xo, Vo) ~ 22d has independent entries, then
Exxp(CTh2 {11Xo|12 (1o119)) II E Eexp(CThh Eexx))) (e), Vo)2) <
provided that h S 1/VT. Also, by the Cauchy-Schwarz inequality, we can give a crude bound: writing r(t) (2xp(2t) 11)/2,
E exp (CTh² sup exp( 2t) (lx LE(O,T]
Eexp 2CTH? sup exp(- 21) ) Br(()) [2)] 1/2
tE(0.1)
Eexp 2CTh sup cxp(-22 2t) || [|Br(o 1/2 (E[|.]]
e.g.,,hewwi where, by standard estimates the supremum of Brownian motion (see, e.g.. Chewi et 2021b Lemma 23), the first factor is finite if h S 1/VT (again using independence across the dimensions). For the second factor, if we split the sum according to exp(- (2) = 2² and use Hölder's inequality,
E Exxp CTh? 2
sup (xp(-2t) (1)))) (E(1.]
K II
sup exp(-2t) || |BB((o)13)) 1/K 2k<e52k11
E exp
CKTh?
where K = OT)). Then.
Eexp 1
exp( 2() || (Br(o)11)))
sup
2
< Eexp
2-2-
sup
[B(())12) 00,
provided h S 1/T, where we again use Chewi et al. (2021b Lemma 23) and split across the coordinates. The Cauchy Schwarz inequality then implies
E Eexp (TTh² sup <E(O.T]
(I,8,11 +[[v&11)) < co.
For the second term, by independence the increments,
E Exxp Ch
Σ
|Br -hh B. sup
(K+
-
| - -B.11) = [Eexp(( Ch sup [|B.1[²]] N sE(o,A]
= II
EXx Ch
sup <E(T (B -kk)
k=
By Chewi
2022bb
Lemma 23), this quantity is finite if h S which completes the proof.
26

---

Published as a conference paper at ICLR 2023
D DERIVATION OF THE SCORE MATCHING OBJECTIVE
In this section, we present self-contained derivation of the score matching objective 100 for the reader's convenience. See also Hyvärinen 2 Vincent (2011); Song & Ermon (2019)
Recall that the problem is to solve
minimize
E [||s,
v In 2:
This objective cannot be evaluated, even if we replace the expectation over 4 with empirical average over samples from qr- The trick is use an integration by parts identity to reformulate the objective. Here, C' will denote any constant that does not depend on the optimization variable st. Expanding the square,
Bgg +| - V In
F. ||1 - 2 (st, Ving)++ +C
We can rewrite the second term using integration by parts:
f (se, v In (z) dge- = / ((on Var) - =- (div 8e) dge
/ʃ (div (exp(())))) 2o + V1 -1--xpp cxp(-2t) cx-cxp(-22)
2.) dg(x)) (2)
where 7 normal I2) and we used the explicit form the law of the OU process at time t.
Recall the Gaussian integration by parts identity: for any vector field Rd R"
(dive) dyd (ddxv))ar==(xxx))))) (x).
Applying this identity,
f (st, v (l du: v1 exp( (2)) / / (2), dg(zo) ( (z)
1
where x. = exp((11) 2o + vI exp( 21) zt. Substituting this in,
2
Eg.llls: Vn 1|] [Xs((X,))1 +
(Z sc s((o)) +C
V exp(-22
= E [x]]s(X.)
1
Z: 19 + +C,
exp(-2t)
where No ~ q and Z, 7 are independent, and X, = exx((1t) Xo + VI-expl (21) Zz.
E DEFERRED PROOFS
Lemma 21. Suppose that supp C B(0, R) where R > 1, and let qe denote the law of the OU process at time t, started at q. Let be such that < /d and set x E² (Vddd(d))) Vd)). Then,
1. Wa(g 9) S.
2. ge satisfies
(d v
KL(g: (l)d) S
e2
3. For every il 2 t, qu satisfies Assumption 7 with
dR
(RV va)
L
g
27

---

Published as a conference paper at ICLR 2023
Proof.
1. For the OU process ① we have X₂ exp(-t) Xo + v - exp( -2t) Z, where 7 ~ normal(O, Ta) is independent of Xo. Hence, for / S 1,
exp(-t)) W 9:) - [ - Xo + v (xp(-2t) -
= (1 - exp(ptp()) E(I xoll || + - cxpc (xp((-2)) S R²t² + dt.
We now take S e to ensure that (2 qt) 62 Since & Vd, it suffices to take = === (RV
2. For this, we use the short-time regularization result which implies that
Otto & Villani 2001 Corollary 2),
(2 W
W2 06) + w 50)
Va(Rv
(L( (1) 5
2
E²
3. Using Mikulincer & Shenfeld 2022
Lemma 4), along the OU process,
exp(-22) R²
1
exp( -2t) Ia
Ia 5 ( exp(-2t)
Id.
(1 exp(-2t))²
With our choice of t,, it implies
V exp(-2t') R²
R 1
dR²
(RV Va) 2
| In llop S
exp(-211)
28


Reviews:
[{"review_id": "bt5n0vS9GaF", "reviewer": "Reviewer_ner6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper provides convergence bounds for score-based models under the assumption that score estimate is $L^2$ accurate. Provided that, the paper derives some remarkable bounds for the score-based sampling methods under pretty weak assumptions.", "summary_of_the_review": "The paper reads well and presents important results which provides clarity to the field. I have the following comments for the authors:\n\n1) It looks like their rate matches the convergence of Langevin diffusions to the target measure under the LSI assumption - but without any stringent assumption on the target (just good score estimates). However, intuitively (or fundamentally), it was left unclear what actually enables this. Perhaps this is not so surprising, since the forward diffusion starts from actual samples from the target (rather than, like in a classical setting, from an arbitrary point in space) - and provided that the gradient is well estimated, sampling does not require any assumptions. Can authors comment clearly about the differences between their setup and a regular Langevin sampling setup where the initialisations are from arbitrary distributions? This can be perhaps done by assuming no gradient error (exact gradients) and discussing the difference between a Langevin diffusion sampler and a forward-backward score based sampler.\n\n2) It would be also nice if the authors clarified the Remark after Corollary 4. As showed in multiple prior works, the real world data structure supports the manifold hypothesis -- therefore, the impressive convergence results presented in the first part may not apply, as authors pointed out (but still valuable). The remark states that a unified error bound can be obtained in the bounded Lipschitz metric but this was not completed. It would be nice if this is done.\n\n3) Assumption 2 might be OK, assuming finite datasets, however, in a realistic setting where the data stream is observed, this may not hold. Can authors comment if this assumption can be relaxed and at what cost?", "strength_and_weaknesses": "Strength: The results are pretty impressive given the state of the field.\n\nWeakness: The results shown under the manifold hypothesis seem incomplete.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "UaxTjXeeu6", "reviewer": "Reviewer_uWLa", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes a theoretical analysis of SGMs that extends Chen et al. (2022c) and the bad set approach from (Lee et al., 2022a).\n\nCompared to Chen et al. the analysis is much more general in a number of ways, and compared to Lee et al. the analysis relaxes an LSI assumption and is applicable to a larger class of generative models (CLD).\n\nMore concretely, the claimed contributions are:\n- more general analysis without LSI assumption and applicable to CLDs\n- particularly interesting special case for distributions with a bounded support (which remove the necessity for a restrictive assumption of Lipschitz score estimate)\n- tight iteration complexity ", "summary_of_the_review": "Overall I think the paper introduces very strong, novel results that give a good foundation for the study of SGMs. Some limitations are present but they are to be expected due to the short format of the conference. Overall I think it's clearly above the bar for ICLR, but due to the close ties to several recent works it would be good to highlight more what separates the tools used in this paper with previous results. ", "strength_and_weaknesses": "Despite the strong claims, the paper seems to deliver on most aspects so everything listed in the summary of contribution should be considered as a core strength of the paper.\n\nHowever each of the strong point presents some slight limitations that could be adressed more clearly.\n\n1) Removing the LSI assumption is a strong result, but ends up introducing new assumptions of smoothness, bounded moment, and of accurate estimation of the score function\n1.a) As the authors explain in the paper, this smoothness assumption is not satisfied when the input distribution lies on a manifold, which is probably the same regime where the accurate score function estimation is feasible at all. However most current SGM models also implicitely assume that q has full support, highlighting that this might be a limitation of the whole field. To make the analysis more relevant the failure modes of the theoretical analysis should shed some light on which modifications should be introduced in the models and training procedures to relax this assumption and be able to automatically detect the manifold and avoid this pitfall, but this would be an important contribution by itself. The authors instead give a good second choice by looking at a simplified but realistic model where the distribution lies in a ball around the origin. However the number of iterations grow quite quickly with the radius (e.g. ~R^8) making it vacuous.\n1.b) The accurate estimation of the score function is the central point of the paper, but the authors spend very little time explaining how this quantity is computed. Beyond a quick description of score matching, they mostly refer the reader to Vincent 2011, but this source actually highlights how minimizing (13) is actually very hard even after the score matching rewriting, and the authors even mention hardness results at the end of page 2. It would be good to point out some more context on when this estimation problem can be solved in an efficient manner.\n1.c) Unlike the other assumptions that are discussed mutliple times in the paper, the moment assumption receives very little attention. For example, the authors should try to justify why their proposed bound of m_2 < d in the discussion of Thm. 2 should hold, especially considering a bound e.g. m_2 < d^2 would result in different value for N and eps_score than the ones reported in the introduction.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "40ffXOujhg", "reviewer": "Reviewer_71Gb", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper examines the convergence of SGMs under fairly general assumptions. The main novelty compared to existing works is the $L^2$ error assumption on the score estimates, as opposed to the more common $L^\\infty$.The main conclusion is that one can basically reduce the difficulty of SGMs to estimating the scores since the sampling part afterward is relatively easy: the authors proved a convergence bound that scales polynomially with respect to the relevant parameters. Extention to CLD is discussed.", "summary_of_the_review": "This paper provides several convergence results for diffusion models with OU process. I think this is a solid paper, but can be significantly improved if the authors can:\n\n1. prove results on DDPM or other SDEs in (Song et al. 2021b).\n\n2. provide more context on the related work, for instance (De Bortoli 2022).\n\n3. figure out the scaling issue.\n\n4. improve the section on CLD.", "strength_and_weaknesses": "Strength:\n\n- The presentation is clear.\n\n- The proof ideas are simple and fairly straightforward. As the authors mentioned, they seem robust enough to generalize to other settings beyond the OU process considered in the present work.\n\nWeaknesses: \n\n- This paper does not really deal with DDPM in the sense of the cited (Song et al. 2021b). First, at least in (Song et al. 2021b), DDPM refers to a specific SDE with time-inhomogeneous diffusion. Although the authors briefly mention that the analysis can be extended to that case, I don't think it is such a straightforward matter. For instance,  the first step in Section 4 would break down, as $\\tilde{p}_0 \\neq \\gamma^d$. How do we handle this? \n\n    Another major difference is, in (Song et al. 2021b), the sampling part is done by a predictor-corrector sampler; see Appendix G. Incorporating this source of error is quite important as it does reduce the variance of the sampling procedure significantly. Instead, the authors opted for an exact sampler by taking advantage of the time-inhomogeneous OU process, which, echoing the above, is not available for DDPM.\n\n\n\n- One thing that is unclear to me is the scaling issue as follows. Since both TV and KL are invariant to scaling, instead of $q(x)$ one may consider a new measure $q(cx)$ for any $c >0$. Inspecting the bound in Theorem 2, it is clear that the first term is invariant, the second moment in the second term scales accordingly, whereas the $\\varepsilon_{\\text{score}}$ term is again left as constant. On the other hand, intuitively, as $c\\rightarrow \\infty$ the error in the score estimate might shrink (since this corresponds to shrinking the moments of $q$).\n\n    To conclude, the bound in Theorem 2 doesn't seem to capture the scale invariance of TV/KL, suggesting that there might be some artifact in the proof. (That being said, I acknowledge that my argument above is no less vague than the authors', so this should not be taken as a major criticism.)\n\n- I find the argument on the deficiency of underdamped Langevin fairly weak. On one hand, as the authors have noticed, no definitive statement is given. On the other hand, all of the bounds in this paper are either given by KL or TV, but these two are not really the \"right\" metric for underdamped Langevin (Desvillettes and Villani 2000).\n\n- The comparison to (De Bortoli 2022) is not entirely fair since the convergence metric there is given in the Wasserstein distance, which makes sense under the manifold hypothesis. The Wasserstein distance is ideal for this setting as it does not rely on the measures being absolutely continuous to each other.\n\n- As the authors acknowledged, a serious limitation is that the score estimate part is assumed away, whereas in practice estimating the score is the bottleneck.\n\n\n\nDesvillettes and Villani 2000, On the trend to global equilibrium in spatially inhomogeneous entropy-dissipating systems: The linear Fokker-Planck equation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "0biiQs1Alj", "reviewer": "Reviewer_gx2o", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work provides a convergence guarantee for using a score-based diffusion model to sample from an arbitrary distribution. The method has significantly looser assumptions than previous work, and accounts for three sources of error: (1) L2 score estimation error, (2) discretization of the reverse SDE sampling algorithm, and (3) initializing the algorithm from noise rather than the true resulting distribution from the forward diffusion process. \n\n", "summary_of_the_review": "While this is a very technical paper, there is immense interest in diffusion models. I expect this will be of high interest to the community.", "strength_and_weaknesses": "Strengths:\n- Well-written and presented clearly.\n- Clearly discusses the relationship to other work in this area. While I am not an expert in the area, I thought this was especially well-done. \n- Bound is in terms of the L2 error of the score estimate.\n- Bound does not assume log-concave data distribution.\n- Assumptions and limitations of the results are described clearly.\n- Explores the consequences of this result with respect to critically damped Langevin diffusion, a variant of the simpler diffusion process.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%