Convergence of denoising diffusion models under the manifold hypothesis
Authors: Valentin De Bortoli
Venue: Accepted by TMLR ()

Abstract:   Denoising diffusion models are a recent class of generative models exhibiting state-of-the-art performance in image and audio synthesis. Such models approximate the time-reversal of a forward noising process from a target distribution to a reference measure, which is usually Gaussian. Despite their strong empirical results, the theoretical analysis of such models remains limited. In particular, all current approaches crucially assume that the target density admits a density w.r.t. the Lebesgue measure. This does not cover settings where the target distribution is supported on a lower-dimensional manifold or is given by some empirical distribution. In this paper, we bridge this gap by providing the first convergence results for diffusion models in this setting. In particular, we provide quantitative bounds on the Wasserstein distance of order one between the target data distribution and the generative distribution of the diffusion model.


Published in Transactions on Machine Learning Research (11/2022)
Convergence of denoising diffusion models under the manifold hypothesis
Valentin De Bortoli
Deportment of Computer Science ENS, CNRS, PSL University
Paris, Prance
Reviewed on OpenReview: https: httees//pperreveeu..ee
openreview.net weteeeiiewweee//eeeemme forum? id= NhKK5aX33338
Abstract
Denoising diffusion models are a recent class of generative models exhibiting stae performance in image and audio synthesis. Such models approximate the time-reversal of forward noising process from a target distribution a reference measure, which is usually Gaussian. Despite their strong empirical results, the theoretical analysis of such models remains limited. In particular, all current approaches crucially assume that the target density admits density w.r.t. the Lebesgue mcasure. This does not cover settings where the target distribution is supported on a lower-dimensional manifold or is given by some empirical distribution. this paper, we bridge this gap by providing the first convergence results for diffusion models in this setting. In particular, we provide quantitative bounds on the Wasserstein distance of order one between the target data distribution and the generative distrributin of the diffusion model.
1 Introduction
Diffusion modeling, also called score-based generative modeling, is a new paradigm for generative modeling which exhibits state-of-the-art performance in image and audio synthesis (Song and Ermon 2019 Song et al. 2021b; Ho et al. 2020 Nichol and Dhariwal 2021 Dhariwal and Nichol, 2021 Such models first consider a forward stochastic process, adding noise to the data until a Gaussian distribution is reached. The model then approximates the backward process associated with this forward noising process. It can be shown, see Haussmann and Pardoux 1986) for instance, that in order to compute the drift of the backward trajectory, the gradient the forward logarithmic density (Stein score) must be estimated. Such an estimator then obtained using score matching techniques (Hyvärinen) (2005] Vincent 2011) and leveraging neural network techniques. At sampling time, the backward process initialized with Gaussian and backward in time using the approximation of the Stein score. Despite impressive empirical results, theoretical understanding and convergence analysis of diffusion models remain limited. De Bortoli et al. (2021b) establish the convergence of diffusion models in total variation under the assumption that the target distribution admits a density w.rtt. the Lebesgue measure and under dissipativity conditions. More recently Lee et al. (2022) obtained convergence results for diffusion models, including predictor-correcta schemes, under the assumption that the target distribution admits a density w.r.t. the Lebesgue measure and satisfics a log-Sobolev incquality.
However, these works implicitly assume that the score does not explode t - by imposing that the score of the data distribution is Lipschitz continuous satisfies some growth property. This is not observed in practice and experimentally the norm of the score blows up when f - 0, see (Kim et al. 2022) for instance. Indeed, the assumptions that the target distribution admits a density w.r.l. the Lebesgue measure and has a Lipschitz logarithmic gradient does not hold one assumes the manifold hypothesis (Tenenbaum et al., 2000: Fefferman et al., 20166; Goodfellow et al.] 2016 Brown et al.) (022)) or if the target mcasure is an empirical measure. In this setting, the target distribution is supported on lower dimensional compact set. In the case of image processing, this hypothesis is supported by empirical evidence (Weinberger and Saul,

---

Published in Transactions on Machine Learning Research (11/2022)
Fefferman al. 2016 Under this hypothesis, even though the forward process admits density for all / > 0 its logarithmic gradient explodes for small & + O. Consequently, previous theoretical analyses of diffusion models do not apply to this setting. To our knowledge, (Pidstrigachi 2022) is the only existing work investigating the convergence of diffusion models under such manifold assumptions by showing that the limit of the continuous backward process with approximate score is well-defined and that its distribution is equivalent to the one of the target distribution under integrability conditions on the error of the score. In particular, Pidstrigach (0222) show that these distributions have the same support.
2006
In this work, complement these results and study the convergence rate of diffusion models under the manifold hypothesis. More preciscly, we derive quantitative convergence bounds in Wasserstein distance of order one between the target distribution and the generative distribution of the diffusion model. The rest of the paper is organized as follows. In Section 2 we recall the basics of diffusion models. We present our main results and discuss links with the existing literature Section 3 The rest of the paper is dedicated to the proof of Theorem in Scction 4 We conclude and explore future avenues in Section
2 Diffusion models for generative modeling
In this section, we recall the basics of diffusion models. Henceforth, let x E ((R)) denote the target distribution, also known as the data distribution, and T = N(0, Id) the d-dimensional Gaussian distribution with zero mcan and identity covariance matrix. In what follows, we let T 0 and consider the forward noising process (X))) given by an Ornstein- -uattennUhhleeeedd process as follows
dx,- = -3 + /28,dB., Xo NONT n.
(1)
where (Br) is a d-dimensional Brownian motion and + 3g is a (positive) weight function. In practice, setting &o S 3r allows for better control of the backward diffusion near the target distribution, see (Nichol
and Dhariwal 2021; [Song et al., 20211b) for instance. In what follows, we assume that (1) admits a strong
solution. Under mild assumptions the target distribution (Haussmann and Pardoux 1986 Cattiaux et al.
2021), the backward process (Y:) ()eoo) satisfies
dY, = Br- + 2V logpr- + 28B-
(2)
where {Pr he the family of densities of (c(X:))e(0 w.r.t. the Lebesgue measure. In order to define ( we do not need to assume that π admits a density w.r.t. the Lebesgue mcasure. In practice, instead of sampling from Yo- ~ L(Xx) we sample from Yo ~ To = N(0, Id). For large T> 0 the mismaich bet the distribution of Xy and To is small due to geometric convergence of the
process.
In practice, (V (Vlog Pegeor cannot be computed exactly and is approximated by a family of estimators (s(t, (eeo.. Those estimators minimize the denoising score matching loss function given by
{(s) = So (()))([I((,x - V (x)))
(3)
with Prio is the density of X, given Xo, i.e. the density of the transition kernel associated with 1 and Φ: [0 + R4 is a weighting function. In practice, B is approximated using Monte Carlo samples and the loss function is minimized over the parameters of a neural network.
Once the score estimator is learned, we introduce a contimuous-tine backward process (Yt))ejaa approxi- mating (Y.)eejo,T) and given by
dÝ, BT + 28(T t,, dt) + dd
Yo Too Id).
(4)
In practice, one needs to discretize (4) in order to define an algorithm which can be implemented. We consider a sequence of stepsizes {7*]ke10....,k) such that Σ 7k = T. In what follows, for any & E (O...., ......K) K} we
1 Also called Variance Preserving Stochastic Differential Equation (VPSDE) in Song et al. 2021b For any valuel random variable X, L(X) is the distribution of X.
2

---

Published in Transactions on Machine Learning Research (11/2022)
denote ts+1 Eド=o 7/ and to = Given this sequence of stepsizes, consider the interpolation process (Y))ee(o.T) defined for any l: E {O....,K) K} and t E [ts, 1 by
dY, - f + 2s(TT - 1u Yt, + /2
Yo ~ Too
This process is an for any & {O,..., K + 1}, Yx _Yu, we have for any k E {0....,K]
process on the interval [tx, f4t1]. Denoting (Y.)ke(o....Ktt) K+1) such that
Y4+1 = Y4 + 7.x + 2s(T - the Yx)) + 2/2
(5)
T 11,6 = ex 8,ds] - 22.6 = (expl2 fr B,ds] - 1)/2.
where hEN is a sequence of independent d-dimensional Gaussian random variables with zero mean and identity covariance matrix. The discretization [5] approximately corresponds to the discrete- time scheme
introduced in (Ho et al. 2020), see Appendix B.2 We call this discretization scheme the erponential integralor
(EI) discretization, similarly to Zhang and Chen
2022 who introduced similar scheme in accelerated
deterministic difflusion models. Lee el al. 20222 analyze slightly different scheme corresponding to replacing BT-IY, by Br-rY, Y1, in (4. We summarize the processes we have introduced in Table [ and discuss the
links between 5 and the classical
discrctization in Appendix B.1 As emphasized in the
Description
Evolution equation
Forward process
dX: = X + /B3,BB.
Backward process (BP)
dY, = Pr-r Y: + +V 2V (Y 22
Score approximate BP (SBP)
dÝ. 2 Y.) idB.
2s(T'
El interpolation SBP
dÝ: = 9r- 2s(T Lx Y. )dll + /23r- - 4, Y.)) + 2222kLn Y441 = Y22 77,1 + -
El discretization of SBP
Table Different processes considered in this paper.
introduction, under the manifold hypothesis in the case where the target distribution is an empirical measure, the true score V log explodes when - 0. This behavior has been observed in practice for image
synthesis (Kim et al. 2022 Song and Ermon 2020 One way to deal with this explosive behavior is to
truncate the integration of the backward diffusion, i.e. instead of rumning (Y))e we consider (Y.)rejo,T-e)
for a small hyperparameter = > 0, |Vahdat et al. 2021 Song and Ermon 2020). Translating this condition on the associated discretized process, we assume that {x T E and study (Y+) by disregarding the last sample YK+1- We note that versions of diffusion models defined in discrete time do not suffer from such shortcomings as the truncation is embedded in the discretization scheme, see (Song et al.. 2021b Song and
Ermon 2020 2019 Ho et al. 2020) for instance. Recently Kim et al. (2022) have proposed soft bibisbilistic truncation to replace the proposed hard threshold.
3 Main results
We first start by introducing and discussing our main assumptions. The only assumption we consider on the data distribution π is that it is supported on a compact set M C Rd (i.e. a bounded and closed subset Rd). A 1. n is supported on a compact sel M and 0 E M.
The assumption E M can be omitted but is kept to simplify the proofs. We demote diam(M) the diameter of the manifold defined by diam(M) supfllæ yll x, E M).
An assumption of compactness is natural in image processing images are encoded on a finite range (typically [o, 255] for each channel). We emphasize that this assumption encompasses not only all distributions which admit a contimuous density on a lower dimensional manifold but also all empirical densities of the form (1/N) EA" 8x.. Next, we turn to the temperature schedule & + 3, and make the following assumption. Note that 1441
3

---

Published in Transactions on Machine Learning Research (11/2022)
22 t ++ B1 is continuous, non-decreasing and there erists 3 > 0 such that for any t [0,T], 1/3 2 B = 3.
Under this assumption, the integral of t B1 is well-defined and for any E [0, we have that
X Xo + o.Z,
my expl- Bads],
of = 1 expl- 8,ds),
where the first equality holds in distribution and Z is Gaussian random variable with mean and identity covariance. Note that A2 is satisfied for every schedule used in practice see Appendix G Finally, we make the following assumption on the score network.
3. There erist & E C((O, T| x R RR)) and M 0 such that for any t E [0, and 2, E R
|| - V (o & M( + ||=a)))/o
Contrary to De Bortoli al. 2021bb, we do not assume uniform bound time and space as we allow growth & 0 and |||| + 0. This assumption is more realistic as ||V (o ~c-o (z(z))/of and |/V pe - ei (1) [asell we will show in Appendix C This explosive behavior as + is accounted for in practical implementations. For example (Song et al. (2021b) used parameterization of the score of the form xt,,x) = nat, 2) where n is neural network with lcarnable paramcters. Our assumption is notably different from the one of Lee et al. (022) which assune uniform in time L bound between the score estimator and the true score. Nevertheless, in Appendix [] we derive Theorem I.1 which is the counterpart to our main result under a L error assumption, using the theory of Lee et al. (2022) to derive an L error from a L one. However our L error bounds are weaker than the ones of Lee et al. (2022)
they are estimated w.r.t. to the distribution of the algorithm and not w.r.t. the true backward distribution. We highlight that L bounds more realistic than L as the score is estimated the data.
Finally, we make the following assumption on the sequence of stepsizes. Recall that for any l E NO. have f E}= and to = 0. ......,K.
A4. For any k E (O...., K 1}, we have
30/0 5
In the case where 3t = 30 for any I E [0, A4 is implied by the following condition: for any & E (O...., K K-1}
......,,
7 (Bo + (2 Σ =
(6)
In the next section, we fix 7K = E and in this case, the condition is satisfied if nh S 5e/(2 + 90E).
3.1 Convergence bounds
We are now ready to state our main result.
Theorem 1. Assume All A2 A A4
that T 2 2,(1 log(1 + diam(M)), γK = and e, S 1/32. Then,
there exists Do 2 0 such that
W1(C(Yk),
DM 6// cxxplt/e|cxpl-TT/// E
with diam(M))(1 3)/2 and
Do D(1 + 3)
diam(m)))))(111)) + log(1 + diam(M)))
(7)
and D is numerical constant.
First, we note that letting T + +00, 8,M + 0 and then - O we get that W (C(C(K)) + 0. This consequence is to be expected since lime-so L(Yr-e) = n. An explicit dependency of the bound on these parameters is given in Corollary 2 More generally the error bound depends on four variables (a) e which corresponds to the truncation of the backward process, (b) T the integration time of the forward process, (c) which is related to condition on the stepsizes of the backward discrctization, see A4 (d) which controls the score approximation, see A3 The dependence w.r.t. 81/2 and is linear, whereas the dependence w.r.t. T is of the form exp(-T/3) These two terms are multiplied by quantity depending the truncation
4

---

Published in Transactions on Machine Learning Research (11/2022)
bound which is exponential of the form exp[k/e]. We conjecture that under additional assumptions M this dependence can be improved to also be polynomial, see Theorem 3 for an extension of Theorem [ under general Hessian assumptions. Additional remarks and comments on Theorem ! and its assumptions are considered in Appendix
Proof. We provide a sketch of the proof. The detailed proof is postponed to Section The distribution of Yk given by Ta, where Rx is the transition kernel associated with Yx In order to control Wi W T) we consider the following inequality
Wi(T Rx, T) & (T Too Qti)) + Wi ( (ToaQQI T -PT-(K) + W (T
(8)
where (Px (P:)eejo.1 is the semi-group associated with (Xx)te(0.21 and (Qr)cejo,1) is the semi-group associated with (E))T)) We then control each one of these terms. The first term corresponds to the discretization error and the score approximation. It is upper bounded by term of the form [cexp|</=|[+++ (00MMMM++))///") / The second term corresponds to the convergence of the continuous-time exact backward process and is of order ((exp<</<)xxp) exp[-T//)] The last term corresponds to the error between the data distribution and a slightly noisy version of this distribution and is of order (ss1/2).
As an immediate corollary of Theorem 1 we have the following result. Corollary 2. Assume A
Let 17 E (0, 1/3)), T 2 23(1 + log(1 + diam(M)) and T2 8(x + 1)/m² M expl-x/v²'n?, 8 expl-2n</
A
2
A3
A
YK = =
Then,
(I((()),, v 4Do7,
with diam(M))(1 + 01/2 and Do given in 7
The constant Do appearing in Theorem and Corollary does not depend E, T, 5 and M but only on B, diam(M) and d. In particular, we highlight that the dependence of Du w.r.t. the dimension is O(d) and the dependence w.r.t. the diameter of M is O(diam(M)') up to logarithmic term. Note that the diameter might only depend on intrisic dimension p of M which satisfies p < d in some settings. For example in the case of an hypereube of dimension we have diam(M) = vp.
Contrary to De Bortoli et al. 2202bb;; Lee et al. p2022;g Pidstrigach (2022), our results are stated w.r.t. the Wasserstein distance and not the total variation distance or the Kullback- divergence. We emphasize that studying the total variation or Kullback-Leibler divergence between the distribution of YK and the one of under A with M lower dimensional than Rd lead to vacuous bounds as these quantilies are lower bounded by 1 in the case of the total variation and +oo in the case of the Kullback-Leibler divergence since the densities we are comparing are not supported on the same set This is not the case with the Wasserstein distance of order one. To the best of our knowledge Theorem I is the first convergence result for diffusion models w.r.t. W1. We note that our result could be extended to Wp p for any p 2 1, since we do not rely on any property specific W, among all Wp distances for any p 2 In particular, our analysis does not use the fact that W, is an integral probability metric, (Sriperumbudur el al.) 2009)..
We conclude this section, with improvement upon Theorem in the case where tighter bounds the Hessian 2 log are available.
Theorem 3. Assume 1 addition, assume that there erists M 0 such that for any t E (0,T) and x, E Rd
A3
A4 that T 2 2 + log(1 + diam(M)), 7K = E and e, M,M & 1/32. In
logp < T/O
(9)
Then, there erists Do 2 0 such. that
(i(C())). & Do 0 (/13/// T2 expp- 100e++222 +
We emphasize however that total variation bounds smaller than and finite Lulbback-Leibler divergence have strong implications, namely the generative model has same support as the target. distribution. However, such property is satisfied in practice, see Appendix Frrr (Jolicoeur- (Jnicceur-Vartineau Martinean al. 2021 Figure 2) for instance.
5

---

Published in Transactions on Machine Learning Research (11/2022)
with
Do = D(1+ d (1 diam(M)))) + (T + 2)(1 + log(1 (M)))
and D is a numerical constant.
Proof. The complete proof is postponed to Appendix J. The crux of the proof is to derive an improved
version of Proposition which provides controls on some tangent process. Indeed, in Proposition G we use an upper bound of the form || Pe < T/of which is loose upper bound derived under AL
Theorem improves the bounds of Thoorem since the exponential dependency w.r.t. E is replaced by polynomial dependency with exponent r. At. first. sight, is not. clear when (9) is satisfied. However, in special cases
verify this condition explicitly. For example, in Appendix J.2 we show that this
condition is satisfied if is the uniform distribution on the hypercube, with E {l.....d) d]. The condition (9)
has strong geometrical implications on M. In particular, under appropriate smoothness assumptions on M,
it implies that MM is convex, Appendix J.3
3.2 Statistical guarantees and empirical measure targets
We emphasize that the results of Theorem I hold under the general assumption A[ which only requires the target mcasure to be supported on a compact set. This includes measures which are supported on a smooth manifold of dimension p S but also all empirical measures of the form (1/N) E 8x* with {X') ~ T In particular if we assume that the underlying target measure æ supported on a manifold of dimension p S d and that the diffusson models are trained w.r.t. some empirical measure associated with then we have the following result.
Proposition 4. Assume A
2
A3
3
A4 that T 2 23(1 log(1 diam(MM)), γкK = and e, M, & 1/32.
Then, for any 1j O there eaist Do.
D1
0 such that
W m < Do(exp(x/ee])p
52/3)/ + exp[m// exp[ exp[ + +//3 + + - (()))())+))
with das (M) the Minkowski dimension of M, see = di D1 given in (Weed and Bach 2019 Theorem 1) and
Do = + 3) diam(M)))(1 log(1 + diam(M)))
with D numerical constant.
Proof. For any N N. we denote N~ = -1/N) 8x Using Theorem we have that for any N
W (C(k)))) ~ (o(epp/k//] //82 + exp[x/ee +e,
with a constant Do which does not depend on { and N. Therefore, we have that for any N
E| (C(K)) M)) < Do (o(exp/x/e](C //2
+))
(10)
Using (Weed and Bach 2019 Theorem 1) and WWed and Bach 2019 Proposition 2), for any n > 0, there exists D, 2 0 such that
E W m) s D
which concludes the proof upon combining this result, 10 and the triangle inequality.
The Minkowski dimension d(M) is defined as follows:
d(M) = lim (oVl
(11)
with Vol(A) the volume of a (measurable) set A and M, the e-fattening of M, í.e. for any e >>> 0, M, {i E Rd d(æ, M) SE.. For example M topological manifold of dimension p S then its Minkowski dimension is p, i.c. (M( = p. Hence, in this case the error term in Proposition depends exponentially

---

Published in Transactions on Machine Learning Research (11/2022)
the dimension of M and on its diameter but depends only linearly on d, the dimension of the ambient space. Note again that diam(M) might depend on the dimension of M. For example in the case of the hypercube we have diam(M)- = vP. Hence, the results of Proposition | show that diffusion models exploit the lower-dimensional structure of the target. We highlight that this result does not quantify the diversily of diffusion models, i.e. their ability to produce samples which are distinct from the ones of the training dataset Alaa et al. (2022); Zhho et al.] (2018). There empirical evidence that denoising diffusion models yield generative models with good diversity properties Xiao al. (2021); Dhariwal and Nichol (2021) and we leave the theoretical study of the diversity of denoising ciffusion models for future work.
M=
3.3 Related works
To the best of our knowledge, (De Bortoli et al., 2021b) is the first quantitative convergence results for denoising diffusion models. More precisely, De Bortoli et al. (2021b) show a bound in total variation between the distribution of the diffusion model and the target distribution of the form
[(+ T|l S A(exp[-T] + exp[T](M + +112)).
(12)
This result holds under the assumption that admits density w.r.t. Lebesgue measure which satisfies some dissipativity conditions. Again we emphasize that such results in total variation are vacuous under the manifold hypothesis. The upper bound in 12 is obtained using a similar splitting of the error as in Theorem I However the control of the discretization error is handled using Girsanov formula in (De Bortoli et al.] b021b and relies on similar techniques as (Dalalyan 2017 Durmus and Moulines 2017). In the present work, this error controlled using the interpolation formula from Del Moral and Singh (2019) which, combined with controls on stochastic flows, allows for lighter controls of the discret error w.r.l. WI.
Lee et al. (022) study the convergence of diffusson models under (uniform in time) L controls on the score approximation. Their result is given w.r.t. the total variation and therefore suffers from the same shortcoming as the ones of De Bortoli et al. (2021b). In particular it is assumed that the data distribution admits a density w.r.t. the Lebesgue mcasure which satisfics some regularity conditions as well as a logarithmic Sobolev inequality. Additionally, it is required that V logg Pr is bounded uniformly in time and in space which is not true under the manifold hypothesis and is hard to verify in practice even in simple cases.
Closer to our line of work are the results of Pidstrigach 2022 who proves that the approximate backward process 4 converges to a random variable whose distribution is supported on the manifold of interest. In this work, we complement these results by studying the discretization scheme and providing quantitative bounds between the output of the diffusion model and the target distribution.
Related to the manifold hypothesis and the study of convergence of diffusion models De Bortoli el al. 2022 study the convergence of Riemannian counterpart of diffusion models. Result are given w.r.t. the total variation (defined on the manifold of interest). Even though such diffusion models directly incorporate the manifold information they require the knowledge of the geodesics and the Riemannian metric of the manifold. In the case of the manifold hypothesis these quantities are not known and therefore cannot. be used in practice. In particular, De Bortoli et al. 2022) focus on manifolds which have a well-known structure such as S T2 or (R)..
Franzese et al. ) show that there exists a trade-off between long and short time horizons T. Their analysis is based on rearrangement of the Evidence Lower Bound (ELBO) obtained by Huang et al. (2021). This ELBO can be decomposed in the sum of two terms: one which decreases with T (controlling the bias between ((Xr) and ) and one which increases with T (corresponding to the loss term (3)) Their decomposition
of the ELBO is in fact equivalent to (Song et al. 2021a| Theorem 1). In Appendix H we include a short
derivation of this result.
Finally, we highlight the earlier results of Block et al. 2020a). In this work, the authors study a version of the Langevin algorithm in which the score term is approximated. This is different from the diffusion model setting and is closer to the setting of Plug-and-Play (PnP) approaches (Venkatakrrshhan et al. 2013 Arridge
Fveen though the authors provide discussion on an annealed version of the algorithm they study which corresponds the original framework of Song and Ermon (019))
7

---

Published in Transactions on Machine Learning Research (11/2022)
et al. 2019
Zhang et al, 2017). Related to our manifold assumptions, Block et al. (2020b) show that in setting similar to PnP approaches, the corresponding Langevin dynamics enjoys fast convergence rates if the target distribution is supported on manifold with curvature assumptions. In particular, they show that a noisy version of the target distribution satisfies a logarithmic Sobolev inequality with constant which only depends on the intrisic dimension of the manifold.
4 Proof of Theorem
this section, we present a proof Theorem [ More precisely, we control each term on the right hand side of (8). The bottlencck of the proof resides the control of the discrctization and approximation error W (T Rg, Toe Qtx) which is dealt with in Section 4.1 Then, we turn to the convergence of the backward Finally, control the noising error W, W1(PPr-tx IT) and 4.3 Technical results are postponed to the appendix.
process Wi [m Qexe xPr-tx) in Section 1.2
conclude in Section
4.1 Control of W (Ko Too Q(x)
In this section, control W1 (T
W Rk, To Qxx). To do in Del Moral and Singh (2019). First, recall the definition of the stochastic flows (Y (0, and the interpolation of its discrctization (Y (Y",)) for any Rd and s, T) with
going to use the backward formula introducod
dY 3, - a,t + 2V log (d dd
Y
and for any & E {O...., K} and & [sk; (++1)
dY a.2 fr (Y,, s,t + 28(T - 8k, Y ) dBB
Y =
8,2
where = max(s, 42). We also introduce the tangent process
dVY: s.t = 3r +2V2 log (Y.)
VY 5,8
ld.
(13)
s.1 e.E can also be defined as follows, Under mild regularity assumption, for any s, E [0, with t 2 s, x H Y s.t is a diffeomorphism, see (unita 1981h, and we denote x + VY differential. Then, (Kunita 1981 Section 2) shows under mild assumptions that (VY., Ne, satisfies (13). Hence, (VY",))s
Note that
is a d d stochastic process. The langent process YY
encodes the local variation of the process (Y YY=,),, w.r.t. its initial condition. Our bound the ppprooxmatiion/sscreeiieae relies on the following proposition which first proven by Del Moral and Singh (2019)
Proposition 5. Assume Al] Then, for any s, E [0, T) with t and Rd
Y Y (VY Ab (D)((YY) (Ys,)ee(ss))dd
where for any u E (0, with E (x+1) for some k E (O...., K} and (wo) E C((s, (Rd) we have bu(w) (wn + 27 log bu(w) Br-ulum + 2s(T sk, Wse))s) Abr(w) bu(w) ba(w).
where Sy max(s, tw).
Proof. The proof of this proposition is postponed to Appendix E
Using Proposition our goal is now to control //VY;, . and || ((Y ree))))))) for any s, E [0,T] and x E ddd To do so, we introduce the time which is a lower bound on the supremum time so that the backward process contractive on [0,4*],
- - log(1 diam(M))).
(14)
We then obtain the following bound.
8

---

Published in Transactions on Machine Learning Research (11/2022)
Proposition 6. Assume A and T 2 23(1 + log(1 + diam(M)). Let tk [0, T). Then, for any [0, tk) and E Rd we have
VV sax S expl- T- po cxp(dham((M)))222rr "100:
Proof. Let x RR First, using 13 and Lemma C.2 we have that for any 8, / [0. 7 with 8 S
V| a & 2/r xell 2(1 - (inn
VY )d)
First, assume that - t* and that & 2 t. In that case, using Lemma D.8 we have that
St BT- 2/07- + diam((MM)))
(1122) 1 Br-udu.
Therefore, using that result and the fact that VY 8.8 ld, get that
sxpp((11))) F Budu).
(15)
In addition, using Lemma D we have that
S. (1 2/07 +
(iam(m))// (diam(M) -
Therefore, get that
VY r.ll S exp((diam(MM) a..
Hence, combining this result and 15 in the case where S 6a we have
VY x exp[-(1/2) 1- B,ds] (Pp((iaam(M)/22))
The proof in the cases where
and s S t", S are similar and left to the reader.
Our next goal is to control ||a||| We recall that b, : [0, T C(10, 7], RRd) + Rd where for any E [0, T) such that u E [sk, 1x41) for some E (O.....
(o.....K K} and = (Wo)uE(e.T) C((s, 7). Rd we have
(w) = 3r-u + 2V lo Pr - (ww)), Abr(w) = bul - (w),
bu(w) = $r-u(wa + 2s(T sk, Wer
where 8k (axx(s,ts). We now provide upper bounds Ab. We introduce the intermediate drift functions b(a),8f ((0)),b b(e), b(d) such that d()) and ((d) b. In addition, for any 8, u [0, such that 2 s, E [sx,4441 for some & E (O....,') K} and for any (Wo)ee(e.T) C((s, T], Rd) we have
((hh (w) = Brr-ulwu + 2V (
(w) = -w + 2V log Pr (wae)), A (c,d) ((() b(d)
A (a b- ((0) (())
A (br) = (6) b(cc)
where 5k = max(s, tR). We have that
|Ab|| < | (0.
+ | (bol
+ ||A (c.)))]]]
(16)
In the rest of this section, control each term the right hand side of
16
Lemma 7. For any s, u [0) such that > s, (sk,tu4) for some (O...., K} and w (Wo)rels,Ty E
C(8s, T), Rd) we have
(A (w) < 2 2 (iam (10e:))))22aamMMMMM)))i)aa/// (ddam)())))) + +|[wall)77
WWith slight abuse notation assume that each process on C({s, TJ) is extended C(O0, TJ) by setting wa we any E s].

---

Published in Transactions on Machine Learning Research (11/2022)
Proof. Assume that S th. Then, we have
b. (w))
S - Vog.llloopprrrlee V log tn (wiu)
< 23r 7 :u 1 V logpr- (wa))l
Using Lemma C.3
we have that
| (a b, (w)) & 2 -up + diam(M)) (diam(MM) + |
which concludes the proof in the case where $ S f:- The case where 4 similar and left to the reader.
Lemma 8, For any 8, u E (), such that u 2 s, u [Sk, tx+1) for some E {O....,Ki K} and w = (wb)ne(ssTT E we have
| b, & 2(00r11//tt---- (1 + diam(M)))lus, Woull,
where $; = max(s,ta) tx).
Proof. Assume that $ to. We have
| (bb. bu(wil
s 23 1og - pr (wu)l
S 2 - SUPollu.T 2 log pr- (wo) (wb)ll We.ll
Using Lemma C.2 we have that
(b.e)) bu (w)l s 2(2 1 2(33-u/07_ diam wie
which concludes the proof in the case where < ty. The case where tx is similar and left to the reader.
Finally, combining Lemma Lemma and A3 in 16 get that for any (0, such that 8, E [sk, (4+1) for some k E (0, K) and (e))7) E C((s. T), RR) we have
[w)l[ < suu DE 4441, (B8/a + diam(M (diamm((M)) + [kwll) + 2( 01 diam(M) >|w,, worll
(17)
+ 2 + W 10/
where Sq max(s, 1x).
The following proposition controls the local error between the continuous-time backward process and the interpolation of the discretized where the true score is replaced by the approximation In addition, assume that 8,M,77K 7K I 1/32. Then, we have for any
Proposition 9. Assume A1 s,u [0, [x] with u 2
Ab. (Y..)). S CT 1x 0M 52/2) 1x)²
where Y,,o ~ N(O, Id) and
Co = (1 (1+ 3) 256d + 43664(1 + diam(M)))*.
(18)
Proof. Let s,u E [0, tx] with u 2 s. In what follows, for case of notation, we denote for any & E {O....,
K}
Ky = supoetr-tsa Bu/o
There exists E (O...., K 1} such that E [tx. tx41]. Assume that s S tg. Recall that using we have that for any (Wo)DE(s:T] E C[[sT]],
(w))l 5 2 T - (B diam(M)))(iaam(M)) (ea (wwk))>+www)>>)>)) 1)
10

---

Published in Transactions on Machine Learning Research (11/2022)
+ +2(3r-o/01- + diam wei
- + 1| 1
$ 2(k2g/ 0 -4.1 (2 diam (M))) (diam(()) + ||Wul)
+ 2 + diam(M) wt, /1/ + 2kx + ||w,, II)-
Combining this result with Lemma
D.5 its following remark and Lemma
D.6 we get that
Blllbb
(( s. 2( - (2 diam(MM) (diam(M) + k)/2)
+ +2x (1 diam (M) ) /// 38/2 1/2
+ 2AxM Ko k
7h
Denoting C 022(2 + diam(M))) Ko
) /2
21 1/2 3//33///221 diam M)) + 2(1 + k3 we get that
E| Ab. (....)) S ( / T-
t241 17k +
ki
2 1/2
Mkx)).
Combining this result, 44
4 and Lemma
D.3
have
Ab. (Y..,((YYY))) s.)))((A.))) - C(1 (1+ (x))) MM) +c + (x
< Cc 1x /1/ 1x)² 2 C(1 + 3)( lx 0060/2 -lx).
Finally, using Lemma D.2 we have
Tx -2 ---tx" = (1 expl-2 20- B,ds)) 11+ 3/((13/22331)) Therefore,
using that 7K- T - tk we get that
(AY.))))))))) - c(1 + ()² - 1x + () 82/2 +MM 1x)² 1x)²
$ 20 + (T tx + 3) MT
which concludes the first part of the proof in the case where s t.. The same bound holds the case where 4g- Finally, we conclude upon noticing that 2C(1 + 3)2 Co with Co given by 18]
We are now ready control the global error between the backward process and the interpolation of the associated discrete-time process where the true score has been replaced by its approximation 8.
Proposition 10. Assume AD
and 7K- = E. In addition, assume that e, 6, < 1/32. Then
WI Qtx no Rg) S Do cxp(diam(MM)) + (M (
where Du = (1+ + (8 512d 87328(1 87328 + diam(MM))) log(1 + diam(M))).
Proof. Using Proposition
5 we have
Y Yxll Y|
-Yxx S 1
V
Yo. v.tx
Abu Abb.((Y,,,) (Yo,))oe(o.r))]dd
Combining this result, recalling that is defined in 14 and Proposition 6
we get
|Y - Yxll S5x* ** expl= ST 3,ds (o.r)) (w) (xpp(diaam((M1///07>>1"ll_ ((Y (Yaoaao
s exp((diam((MM}//)))7222
( B,d=]]| (eoor))eto.r)) Ilddu
+ 5 |b. ( (Yo,,))
Using this result and Proposition get
W WTo Qixe Tod
KE YEIl YtK tx YKll
I {exp((diam(MM
(M))mm)))///2)222)mm))) 10 exp(-(1/2) = B,ds][[[ Abr ((
11

---

Published in Transactions on Machine Learning Research (11/2022)
J E|| Ab (X).)
I expl(diam M)² Co tk + (M (12)
x expl-(1/2) -- B,dsjdu + ix - 1*).
(19)
We have that
So¹ expl- (xpl-(1/2)_ff= S,ds]du s So expl- (11l((("))((23))) u)/(23) S 23.
(20)
In addition, using
14 have
log(1 + diam(M))) - 2 + log(1 + diam(MM))). tx -- = T - T - 23 +
(21)
Using Lemma D.2. we have that o-- S (1 + 3)/E. Combining this result, 20 and
21
in
19
we get
WT Qix Tox Rk) s 20g (L (1 + log(1 + diam((m))) 8//2)/E",
which concludes the proof.
4.2 Control of Wi(Too Qux PP-
In this section, we focus on the error WI(T Que, TPr-tx). First, note that xPr-te = xPP Therefore, using Proposition D.9 we have
W (To T TP (I (t T T S exp((1/2)aT=4, W (ITPT mm))
(22)
To control W WT Noo) we use a synchronous coupling, i.e. we set (Y,, (EjoTT) such that
dY = - v 23, dz, -3 + Soadt++2333 23,dBB.
where (Be) is d-dimensional Brownian motion and Yo π. Zo Tee We have that for any t E [0,
Z, Tia- In addition, denoting ,, = E ||| Y, Zell] for any / E [0, T}, we have that us S un exp[- Jo 3.ds).
Therefore, combining this result and (2 we get that
Wi OT Qix TP exp((1/2)o eepp --"
(23)
Therefore, using Lemma
D.2
we have
W W Qux, TP xx) S expp(1 + ()dim((M3/(((2) (x] exp(- diam(M)).
4.3
Control of W W1 T) and conclusion
In this section, we focus on the error W WI(T, xPT-tx) ) and conclude the proof. We have that W ( TPT- E|| X mT-1x X + or I11, with X x and Z N(0, Hence, using mr-Ix I or-ixs we have
WI(T, x xP S diam (iam(MM(1 mT- + or-ex Vd (diam(M) + vd)or-uk-
Using Lemma D.2 and this result we have
=PP S ((aamm)))) + V2)e1/2.
(24)
We conclude the proof upon combining this result,
23 and Proposition
10 in
5
Conclusion
In this work, we have studiod the convergence of diffusion models under the manifold hypothesis and provided convergence guarantees w.r.t. the Wasserstein distance of order one. Our theoretical results show that diffusion models are able to recover target distributions defined on low-dimensional manifolds. One current.
12

---

Published in Transactions on Machine Learning Research (11/2022)
limitation of our results lies in the dependency w.r.t. 1/c which is exponential in the general case and might be overly pessimistic. This dependency can be improved at the cost of imposing conditions on the Hessian of log but further investigations are needed to establish similar results in realistic settings.
Our results can be extended in several directions. First, in this work we focused on the Ornstein Ornstein-Uhlenbedd process as a forward noising process. It. would be interesting to analyze other forward diffusions such as the criticallydammed one (Dockhorn et al., 2021]. Another extension would be study other discretization frameworks such realistic statistical settings. Finally, it is challenge to derive similar bounds for target distributions with E support and tail constraints.
ceedictor-correeto schemes (Song et al., 2021a and to extend analysis to more
Finally, we would like lo deepen our study of the relationship between the geometry of the manifold M and the properties the score function. Preliminary results from Appendix J.3 indicate that the convexity of M can be recovered from the propertics of the score but it remains unclear if more can be said on the geometry of the manifold.
Acknowledgements
We thank Arnaud Doucet, Émile Mathieu and James Thornton for providing leedback on an early version of the paper. We thank George Deligiannidis, Alain Durmus and Éric Moulines for useful discussions. Finally, are indebted to Pierre Del Moral who pointed us toward his work on stochastic interpolation formulac. This work has been supported by The Alan Turing Institute through the Theory and Methods Challenge Fortnights event "Accelerating generative models and nonconvex optimisation", which took place on 6-10 June 2022 and 5-9 Sep 2022 at The Alan Turing Institute headquarters.
References
Absil, P.-A., Mahony, R., and Trumpf, J. (2013). An extrinsic look at the Riemannian Hessian. In International conference on geometric science of information, pages 361-368. Springer.
Alaa, A., van Breugel, B., Saveliev, E. S., and van der Schaar, M. (2022). How faithful is your synthetic data? sample-level metrics for evaluating and auditing generative models. In International Conference on Machine Learning, ICML 2022, volume 162 of PMLR, pages 290-306. PMLR.
Alekseev, V. M. (1961). An estimate for the perturbations of the solutions of ordinary differential equations. Vestn. Mosk. Univ. Ser. Math. Mekh, 2:28-36.
Arridge, S., Maass, P., Öktem, O., and Schönlieb, C.-B. (2019). Solving inverse problems using data-driven models. Acla Numerica, 28:1-174.
Bishop, R. L. (1974). Infinitesimal convexity implies local convexity. Indiona Univ. Math. J, (A(169--72))rm
Bishop, R. L. and Crittenden, R. J. (2011). Geometry of manifolds. Academic press.
Block, A., Mrouch, Y., and Rakhlin, A. (2020a). Generative modeling with denoising auto-encoders and Langevin sampling, arXiv preprint XrX1v:2002.00107.
Block, A., Mroueh, Y., Rakhlin, A., and Ross, J. (2020b). Fast mixing of multi-scale Langevin dynamics under the manifold hypothesis. Xix preprint arXim:006. 11166.
Brown, B. C., Caterini, A. L., Ross, B. L., Cresswell, J. C., and Loaiza- Ganem, G. (2022). The union of manifolds hypothesis and its implications for deep generative modelling. arXiv preprint or 220: 02862.
Bundt, L. (1934). Bijdrage tot de theoric der konuckse puntverzamelingen. PhD thesis, University of Groningen, Ansterdam.
Cattiaux, P., Conforti, G., Gentil, I., and Léonard, C. (2021). Time reversal of diffusion processes under a finite entropy condition. Xio preprint or 2rXin:2104.07700
13

---

Published in Transactions on Machine Learning Research (11/2022)
Combet, E. (2006). Intégrales exponentielles: développements asymptotiques, propriétés lagrangiennes, volume 937. Springer.
Dalalyan, S. (2017). Theoretical guarantees for approximate sampling from smooth and log-concave densities. J. R. Stat. Soc. Ser. B. Stat. Methodol. 79(3):651-676.
De Bortoli, V., Doucet, A., Heng, J., and Thornton, J. (2021a). Simulating diffusion bridges with score matching. XiXiv preprint Xrx: 100:2111.0011 1.07243.
De Bortoli, V., Mathicu, E., Hutchinson, M., Thornton, J., Tch, Y. W., and Doucet, A. (2022). Riemannian score-based generative modeling. arXiv preprinl arXiv:2202.022: 02763..
De Bortoli, V., Thornoon, J., Heng, J., and Doucet, A. (2021b). Diffusion Schrödinger bridge with applications to score-based generative modeling. Advances in Newral Information Processing Systems, 34.
Del Moral, P. and Singh, S. S. (2019). Backward Ito-Ventzell and stochastic interpolation formulae. ar preprint ar xrx: 09145.
Dhariwal, P. and Nichol, A. Q- (2021). Diffusion models beat GANs on image synthesis. Tn Advances in Neural Information Processing Systems, pages 8780 8794.
Dockhorn, T., Vahdat, A., and Krcis, K. (2021). Scoro-basod generative modeling with critically-damped Langevin dilfusion. Xiviv preprinl or arXiv:2112.0020
Durmus, A. and Moulines, E. (2017). Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probubilily, 27
Fefferman, C., Mitter, S., and Narayanan, H. (2016). Testing the manifold hypothesis. Journal of the American Mathematical Society, 29(4):983-1049
Fontaine, X., De Bortoli, V., and Durmus, (2021). Convergence rates and approximation results for sgd and its contimuous-time counterpart. In Conference on Learning Theory, pages 1965-2058. PMLR.
Franzese, G., Rossi, S., Yang, L., Finamore, A., Rossi, D., Filipponc, M., and Michiardi, P. (2022). How much is enough? a study on diffusion times in score-based generative models. arXiv preprinl ar XrXiv:2206.051
Goodfellow, I., Bengio, Y., and Courville, A. (2016). Deep Learning. MIT press.
Haussmann, U. G. and Pardoux, E. (1986). Time reversal of diffusions. The Annals of Probability, 14(4):1188 1205.
Ho, J., Jain, A., and Abbeel, P. (2020). Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems.
Huang, C.-W., Lim, J. H., and Courville, A. C. (2021). A variational perspective on diffusson- based generative models and score matching. Advances in Newral Information Processing Systems, 34:22863-223 -22766.
Hyvärinen, A. (2005). Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4).
Jolicoeur-Martineuu, A., Tailleee,,,, R., Tachet des Combes, R., and Mitliagkas, I. (2021). Adversarial score matching and improved sampling for image generation. International Conference on Learning Representations.
Kim, D., Shin, S., Song, K., Kang, W., and Moon, 1. (2022). Soft truncation: A universal training technique of score-based diffusion model for high precision score estimation. In International Conference on Machine Learning, volume 162 of PMLR, pages 11201 11228.
Kritikos, N. (1938). Sur quelques propriétés des ensembles convexes. Bulletin mathématique de la Société Rowmaine des Sciences, 40(1 40(1/2):87-11 27)-99922.
14

---

Published in Transactions on Machine Learning Research (11/2022)
Kunita, H. (1981). On the decomposition of solutions of stochastic differential equations. In Stochastic integrals (Proc. Sympos., Univ. Durham, Durham, 1980), volume 851 of Lecture Notes in Math., pages 213 255. Springer, Berlin-New York.
Le Loi, T. and Phien, (2014). A numerical approach some basic theorems in singularity theory. Mathematische Nachrichten, 287(7):764 781.
Lee, H., Lu, J., and Tan, Y. (2022). Convergence for score-based generative modeling with polynomial complexity. Xive preprint or arXi:22206.0222
Matsumoto, Y. (2002). An introduction to Morse theory, volume 208. American Mathematical Soc.
Motzkin, T. S. (1935). Sur quelques propriétés caractéristiques des ensembles bornés non convezes. Bardi.
Nichol, A. Q. and Dhariwal, P. (2021). Improved denoising diffusion probabilistic models. In Mcila, M. and Zhang, T., editors, International Conference on Machine Learning, volume 139 of PMLR, pages 8162 8171.
Pidstrigach, J. (2022). Score-based generative models detect manifolds. arXiv preprint Xrxiv:2206.001
Song, Y., Durkan, C., Murray, I., and Ermon, (2021a). Maximum likelihood training of score-based diffusion models. In Advances in Neural Information Processing Systems, volume 34, pages 1415 1428. Curran Associates, Inc.
Song, Y. and Ermon, S. (2019). Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems, pages 11895-11907.
Song, Y. and Ermon, S. (2020). Improved techniques for training scoro-based generative models. In Advances in Neural Information Processing Systems.
Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. (2021b). Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations.
Sriperumbudur, B. K., Gretton, A., Fukumizu, K., Lanckrict, G. R. G., and Schölkopf, B. (2009). A note on integral probability metrics and dedivergences.
Tenenbaum, J. B., Silva, V. d., and Langford, J. C. (2000). A global geometric framework for nonlincar dimensionality reduction. Science, 290(5500):2319 2323.
Vahdat, A., Kreis, K., and Kautz, J. (2021). based generative modeling in latent space, Advances in Neural Information Processing Systems, 34:11287-11302.
Venkatakrishnan, S. V., Bouman, C. A., and Wohlberg, B. (2013). Plug-and- priors for model based reconstruction. In 2013 IEEE Global Conference on Signal and Information Processing, pages 945-948. IEEE.
Vincent, P. (2011). A connection between score matching and denoising autoencoders. Neural Computation, 23(7):1661-1674
Weed, J. and Bach, F. (2019). Sharp asymplotic and finite-samle rates of convergence of empirical measures in wasserstein distance. Bernoulli, 25(4A):262) 26224)286
Weinberger, K. Q. and Saul, L. K. (2006). Unsupervised learning of image manifolds by semidefinite programming. International journal of computer vision, 70(1):77 90.
Xiao, Z., Kreis, K., and Vahdat, A. (2021). Tackling the generative learning trilemma with denoising diffusson gans. Xiv preprint arXiv:2112.071804
Zhang, K., Zuo, W., Gu, S., and Zhang, L. (2017). Learning deep enn denoiser prior for image restoration. Proceedings of the IEEE conference computer vision and paltern recognition, pages 3929-3938.
15

---

Published in Transactions on Machine Learning Research (11/2022)
Zhang. Q. and Chen, Y. (2022). Fast sampling of diffusion models with exponential integrator. ar preprint 2200::2204 20002.9902.
Zhao, S., Ren, H., Yuan, A., Song, J., Goodman, N. D., and Ermon, S. (2018). Bias and generalization in doep generative models: An empirical study. In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa- Desa-Bianchi, N., and Garnelt, R., editors, Advances in Neural Information Processing Systems, pages 10815-10822
A Organization of the appendix
The appendix is organized as follows. We start by discussing discretization scheme in Appendix B In Appendix [ we provide upper bounds on the gradient and Hessian of the logarithmic gradient of the density of the forward process under the manifold assumption. Tn Appendix D we control the stability of several backward processes. In Appendix E we recall and adapt a stochastic interpolation formula from Del Moral and Singh (2019). We check the different assumptions on the noise schedule Appendix G A short proof of the results of Franzese et al. (2022) is presented in Appendix H In Appendix [
we present an extension of our results in the case where error is controlled w.r.t. the L,2 norm, following the work of Lee et al. (2022 We improve on Theorem in Appendix under some Hessian conditions.
B Discretization of backward processes
Appendix B.1 we briefly describe the links between our proposed discretization and the classical Euler-
Maruyama discrotization. In Appendix B.2 we show that the discretization (5) associated to the one of Ho
et al. (2200) under specific settings
B.1 Link with Suler-Maruyama discretization
First, we recall the given by the so-called Euler-Maruyama approximation, Lee we define for any i E
discretization. Given sequence of stepsizes discretization of 44 is
and E [1,. [++1]
dY BM BT- 14 (YE + 2s(T Lu. b/ yddt + +
, dB,,
EE
Too-
(25)
The associated discrete process we have for any to,...,.A K..
is given for any E (o..... + 1) by yEM VEM and
YEM = Y + PRBT (Y. + 2s(T tv, YEM) + / 28r
(26)
where {Zx kEN is sequence of independent d-dimensional Gaussian random variables with zero mean and identity covariance matrix.
Note that 5 describes the same update as (25 additional cost to replace the classical Maruyaaa discretization with the discrotization defined in (5), provided that the integral of the temperature schodule t + 3g can be computed in close form, which is the case in all the cases considered experimentally, see Appendix
to the first order w.r.t. 7h In practice, there is no
However, in our theoretical analysis we found that introduces less error than 26 when compared the approximate backward process ( In our study only consider the discretization scheme (Yk)ke (0.....K+11)
but emphasize that our analysis could be readily extended to derive similar discretization errors for the EM M (++I)...KKI).
process (YEM))
B.2 Equivalence with Ho al. (2020)
In this section, we show that the discretization scheme introduced Ho al. (2020) and the one of are equivalent up to the first order in some parameter.
16

---

Published in Transactions on Machine Learning Research (11/2022)
Setting of [o et al. (2020) We start by recalling the setting of Ho al. 2020 Since, there is conflict between our notalions and the ones of Ho et al. (2020), write our constants in red and the constants of Ho et al. (2020) in blue. The forward process in Ho et al. (0200) is given for any t E {I....,T]
(<rr/20)= = N(z; vatoo, (1 (1-aa) ds))dd) Id),
(27)
and we define
B1 = aze
ag IT== 0z2
(28)
In that case the loss function is given by
((0) = E'= E',
Elle
celv VI- aae t)]l])
(29)
with {e collection of independent Gaussian random variables with zero mean and identity covariance matrix. The backward sampling is given by the following recursion
8t- = a. 1/2 -
()) + 3
(30)
with [= a collection of independent Gaussian random variables with zero mean and identity covariance matrix Note that using these notations, there is conflict of notation between the forward process and the backward process. To clarify our identification, denote yr I₁ for any t {o,...,T), with given by (30). in what follows.
Identification In what follows, we set /. 1= k + T= K and for any / LE {I,...,?)
a; e fT B,ds] expl-2 --Ix- B,ds].
For instance, we have 0₁ expl-2 S0" -Tt B,ds] and or expl-2 2 B,ds]. Note that in this case, using we have
a. 1/2 expl 1ot T- B B,ds] -
Similarly, VI-ar ai or-tx-e- In what follows, we identify the distribution of the forward process 27 with the one of 1 the loss function 29) with the one 3 and the time reversal (30) with the one of
(a) The distribution (( given in 27 is the distribution of XT- No where (X.)eea,77 is given in 1 since -x- = mr- Xo or-tx- with Z ~ N(0, Therefore, we identify 2; and X XT- u for any / (I,...,T) Similarly, for any 1 E (1....,Ty T}, we identify and lk-k-
(b) Using that X, m m, + B., for any i E (0...., "00...,Ty, T3, the loss is given by
((s) S0 ktt) X.) - V log Pajo (X, Xo)l
50" k(t) s(t, ) + B B / 2
= S0" k(1)/o, 2 01 X.) - B,.// /r.///1/' 1
50" k(T t) /)/or-12 [ or- x,)) B /oy-
With slight abuse of notation assume that <(T - = =EK dex (o) for any / E [0, Hence, we get that
((s) = Ek Bille: -
8(T - tK -k: XT-tk=)))
Ak= Bille= (- /I GT (T- tK k, 11
K
= Σ Ellle: - (-VI - 1,, Vārzo + (1
Hence, identifying 60(,)) and - VI :) for any E (I....,T). we recover 29
Note that in Ho et 2020), T is mumber of steps and the total time of the forward. We consider The case where d; = &r.
17

---

Published in Transactions on Machine Learning Research (11/2022)
(c) We now aim recovering 30 from (5) Using the change of variable k - K k and noting that for
any / E (0,7) 7], / is Gaussian random variable with zero mean and identity covariance matrix we have
YK-k+1 YK-K (oxplSr-tk-u B.ds) 1)(K 22(T -K Yk-+))
+(exp12 f k+1 [,ds] - 1))/22x
YK-x + (ax: -1/2 - 1) K- + 29(T - 1K YK + VBilk-k
=a,-1/2YK-t K + 2((, 1/2 - 1)) - KK-ki YK -k) + VBiZK-
ai -12-k/Ykk - -2((a -1/2 1)/ /IVVVI-- a1) (Y (YK k t) + V3IZK-k.
(31)
Finally, since 0t Bg we have a₁ 1/2 - 3./2 + o(3,). This implies that 2(a, -1/2 1) -Bi/ + 0(3 (4) Therefore, combining this result and 31 we get that
Yk-k+1 = = a/-1/ (B//VI (x- + + ol.e
This corresponds to 30 up to term of the form 0l3./ Vo.)
C Gradient and Hessian controls on the logarithmic density
Let n E (RR) be the target probability measure. We denote (p()s>o such that for any ( 0 the density w..tt. the Lebesgue measure of the distribution Xx (with initialization X ~ л) is given by pe- Similarly, IN E (RR) be an empirical version of x, i.e. n = (1/N) ER= X* with {X*] (wi))so such that for any <> the density w.r.t. the Lebesgue measure of the distribution of X;" (with initialization X ~ >>) is given by Pt. order to show the stability and growth the processes at hand we need to control quantities related to the gradient and Hessian log d. where q: = Pt. or pi" We first show a dissipativity condition on the gradient. We recall that for any E [0. T]
l==1 T We denote
my expl- fo B.ds),
of = 1- exp( 2 20 3,ds).
Such dissipativity conditions will allow us to control the moments of the introduced backward processes. Lemma C.1. Assume Al Then for any (0,7) and x, Fd have that
( (Vlog do (It), an) - ||x, 112 /ot + m,diam(M) ||,, //2
with q: = P. or pt- In addition, we have
< || /ot + 2m (M)
(32)
Proof. Let N E N. We have that for any t E [0, T) and Ia E Rd
(xx) = (1/N) Exn expl-1lza- - x
Thercfore, we get that for any t E [0, T] and 2, E RRd
Vlog (xx) = (-1/N)
m4 xx expl -m,xx111/220111 (x (x:)).
Hence, we have
(V logg, (z)) (x)) < - 1|x,11 /0 m.diam(M) || /0
Therefore taking the limit N + to0, the same conclusion holds for Pt- The proof of lines and left to the reader.
32 follows the same
We now provide controls on the Hessian 2 log 4:- Such bounds allow control the growth (or contraction) of the tangent process. This will also allow us to control the growth (or contraction) of the distance between backward processes w.r.t. the Wasserstein distance of order one.
18

---

Published in Transactions on Machine Learning Research (11/2022)
Lemma C.2. Assume A then we have for any t (0,T), E R2 and M Ma(RR))
(M, v2 log (1 S (M (111mmddaam(M$//\2)))/d
In addition, we have
V (o s (1 diam(M)))
More generally, we have
lolge((z))) = - ld /0²
+(20/)) (Bott)-(Mxxx0 (20 -20 xx6) 02 explp - /1 expl- - / (20)))
m,xoll2((227) expl-|[a, m=ddl
Proof. Let N.N. For any L (0, and a E IR, we let Di = p," (2na7t)d/2 and we have
(x) (1/N) expl-11 m, 11 1a
Hence, we have
- 1 (x)).
Hence, we get that
V log (x) = - Id
C==1l (z m X 2 1a (/0p-//===-__"//0///00/// (z))
N
(1/N2² Ek=I( (x m4 mx - 1
m 3C
(z))².
For any & E {O................... N 1}, denote fe = -= and = = expl-1ft
Using the previous result,
we have
2 22 log (x)= -Id= + N Ex 8 ff f EM
- - H E () / et)
= ld/o (1/2) (1 (st A @ U+F M Ehi efee.
(33)
In addition, using that for any E {1...., NN. X E M we have that
11St fill m. I x'1l/o² m,diam(M)/of.
Therefore, we get that
(M, 2 logp? (z)M) I -(1 - m diam(M) (2amm//)//(222)///)))))
Using 33
the fact that M is compact and the strong law of large numbers we have that
lim 2 N. (x:) - IId/o?
+ [x @ (x m4ão) -mo0==
(xpp))l)l//)x)xxpppllll (22 0000mmm.0////// (
Hence, we get that lim 2 lo (x) 22 Pt, which concludes the proof.
Finally, in order to control the local error of the time discretization, we also need control the time derivative of the gradient, i.e. O V log
19

---

Published in Transactions on Machine Learning Research (11/2022)
Lemma C.3. Assume 1 Then for any E (0,T) and xa R we have that
| V log)((z;)l s (2./o)) +
+ ||=]]).
Proof. Let N E N and t E (0,7]. Recall that for any E R p (x) = P. (z)) (2To with
p. (z) (L/N) E (x),
(=
= expl m, 11/ (20
In what follows, we denote f = log e for any k E NI, For any E F we have
log p. (x) aut
Therefore, we have for any x E Rd
V.V log (x) = Enn (
k= O (0w.0///ooo///oltt///c/////////1
Σ R- (1) (ff
(z)e
(34)
In what follows, we fix j E (I....,NN) N} and provide upper bounds for 10.st - a.fi1. VV - V and O Vf.. First, we have that for any E Rdd (x) = (z mmxx)/o oo? Hence, using that m, S 1, we get that for any x E TRd
(x) - ( S m.diam(M))/ = diam(M)/o}.
(35)
In addition, we have that for any R
(2o;) m2 0mm/ / , mx
Combining this result, the fact that 0,0;- = 2m and that dem: = -3mm we get that
(tf = Bemm/ (ml- ||2
x2 + (z - , - Bem/ 02 (xr x -mm+/ (0? (x- x. + x
Beme/o (x- - +X*
-m,
S.m/ (mmll=/ll + mell 1|2 + (1 + m (x, x²1)
(36)
Using this result and that m, < 1, we have that for any x E R
(x) - (z) < 23,m, diam + 3mm(1 + diam
(37)
< 3 o )diam (diam (M) + ||=]])-
Using (36] we have for any R
vo. = 23m / of + (Bem//ot) + m²)x
Therefore, combining this result and the fact that m, S 1, we get that for any æ E Rd
( s 2(3,/o (ddaat))
||-|])
(38)
Combining 35
37 and
38 in
34
we get that for any E Rd
a V log p (x))
< 2(3./o (diam(M) + [|-|]) + (iaM) (diam(M) + ||>|])
s (2./o)) (damm + [|xl]).
which concludes the proof using that lom O V log V (ar+) 0, log
20

---

Published in Transactions on Machine Learning Research (11/2022)
We conclude this section with bounds on the higher-order differentials of log Pt. To compute higher derivatives we will use the following lemma.
Lemma C.4. Let E = (er be family of functions such that for any i [I....,Mi], et C C= R). Similarly, let G = {g:) i=1 be family of functions such that for any i E fl...., ......,,,,...... 9i C CR( R²). Let F(E,G) G) such that for any Id
F(E,))= =E giel/ Ii
Then, we have
(Vlog E e V log E)),
where @ is the tensor product, @ the pointwise product and @ the tensor substraction.
Proof. We assume that p = 1. The proof in the general case is similar and left to the reader. We have that
G) / E e + + a /oog(e)))ee//Ei eie
- -E 9: V log(e))ee, - ceey
= MM Vgies// E e
+(1/2) (9: (e) 9 Vlog(e,) 9: Vlog(ez) 9, Vlog(ei))eses/ Em Cijj
= Ee Vieei Ei= E
+(1/2) Em (gi 93 ( loge, - V Vloge;)) loge;)/E,,f1 e.ey
which concludes the proof.
Lemma C.5. Assume AD Then, there erists C' 2 0 such that for any t E (0, 27 we have
V log
+ (17 C/o
Proof. Let t E (0, First, remark that for any E Rd
V log = Id /o F(ES2 (V log E θ V log E) 02).
where E = (e:) and for any i E [I,...,N]] N), (x()) x (2o Note that V log Ee does not depend æ and there exists Co 2 0 such that for any i,j {l..... N), || (z) V (z)l Co/o?. Hence, using Lemma C.4
X
we have
logg((()) F(E (V log E V log E) 02
V log(E E) V E
Again, note that G = (V log F remarking that
V log F. 02 (V log E @ E) log( E X E)) does not depend x, upon
log E
log
E
v log E log E) @ log E e V Vlo
Finally, have Vologp
F @
G2),
where
G2 = [
02
log Vlog E))) log(E
e ((V log E
log
E)
V log
E e V log(E & E))) o (Vlog(E e GV Vl))(E
Therefore, we get that there exists C 0 such that for any E Rd
V lo
[ C/of,
[z)g S C/O..
We conclude the proof upon using that a; <
21

---

Published in Transactions on Machine Learning Research (11/2022)
D Control of the backward processes
We start by introducing the different processes in Appendix D.1 We gather a few technical results in
Appendix D.2 Then, we turn to the stability and Lipschitz properties of the backward processes Appendix D.3 Finally, we control the growth of the backward tangent process in Appendix D.4
D.1
Introduction of the processes
In this section, we study the stability of the backward process given by
dY, f + 2V log yT (Y:))d + v 2
(39)
where ge either Pt or pi We are also going to consider the following approximate continuous-time process
dÝ, = Br + 2s(T - t, dd + dd
(40)
where .t, .) is approximation of either Ps or Pi
Note that since > 0 and & E C ((0, x R. R
and that 8 E (², x 1 IR)) we have that 39 and 40 admit strong solutions to an explosion time. Finally, we also consider the following interpolating process: for any / E [l,, (x+1)
dÝ, -T 2s(T l2, Yd))dtt+ + .B,
(41)
This process is an interpolation of a modified Marlyama discrctization of (40). Note that the classical Euler Maruyama discretization would be associated with the following interpolation
dÝF = -r EY 2s(T tk. ) + /23r-u.BB.
In 41
we take advantage of the linear part of the drift. Indeed on the interval [E&, fs+1), the process 41 1 is
simple Ornstein Uhlenbeck which can be integrated explicitly. In particular for any k E (O...., N - 1 and E [tk, te+1 we have
= + (exp1S 8,ds] - 1) + 2s(T ty. Y,,)) + (expl2 3,ds] - 1)
where Z is Gaussian random variable with zero mean and identily covariance and the equality holds in distribution independent from Yι.. Denoting (Ee we get that for any k E {0, {O...., -- 13
T-tx Y441 Yo + (cxplsT=1 B.ds] 1)(% + 2s(T tx. Yz)) + (Tx B,ds] 1) Zk.
where (Zekken is collection of independent Gaussian random variables with zero mean and identity covariance matrix. Using this scheme instead of the classical Farur-Maruyama simplifies the analysis of the discretization. Up to the first order this scheme is equal to the classical Euler- Marruama discretization. Once again, we emphasize that computing this scheme as expensive as computing the classical Marey-Maruyama discretization provided that the integral f du are available in close form for all 8, I E [o, which the case for all the discretization schemes usod in practice. We refer to Table for a list of all processes used the proof. In what follows, we control the stability of these processes.
D.2 Some useful technical lemmas
We gather in this section some technical results. Lemma D.I. For any s, t [0, we have
S¹ Br- Brru/of-nda du [[-1/2))og[oxpp]] TT 3.du] - 1)13.
(42)
Sº
du
-T 3.de])
(43)
In particular, 3 Bo then
St 31 -u - du ((- (-1/)) 1)]f,
Srt 3T m 1 [(1/2)/ expp- w)))]{
22

---

Published in Transactions on Machine Learning Research (11/2022)
Proof. We have
So Br Brr-/od- - = S/² Br-a/(1 expl-2 2 TT 8.dul)du
= - Br-u expl2 5o- -T /adv\/ [xde)/(exp22 So p²--a 3,do] 1d
= --11/2 I an log(exp(2 -"'" 3,do] d)..
This concludes the proof of 42
We have
S BT -T - 1 3T m expl-2 T- Bodel)
= S,² fT- expl T- /odo0/(11 expl- - So" TM d.
= (1/2) Se
- - --- Bodul) -du.
This concludes the proof of 43
Lemma D.2. Assume
We have oî s 2t3 and o, + (2t)..
Proof. First, using that for any a 2 0, exp(- 2 a we have
of cxpl So B.ds] s -xxppppp222t - 28t.
Second, using that for any a 2 0, 1/(1 + expl -a]) s 11 1/a we have
o, = (1 - expl B,ds)) 1 (2 Bads))
which concludes the proof.
For any {O..... .0.....Ay K} we introduce Ni -SUPuElT-be4 I I - 3
Lemma D.3. Assume A2 2 Then, we have that for any h: E {0...., N - 11
Kkk 3(1 3/t)-
Proof. Recall that for any s se [0, of= ex-l-xxp222 Sudu]. Using that for any 220, (1 2-201-1 s
1/(2v) we have for any 1 E (0, 7)
3/0 < B + B, B,ds) 3,3, (1 B/t),
which concludes the proof.
D.3 Stability and Lipschitz properties of the backward processes
The controls derived in Appendix alloo for uniform control of the moments of the backward processes. Note that such Lyapunov techniques were used in Fontaine et al. (2021) to control energy functionals in convex optimization problems. The following lemma is not used directly in our final analysis but provides intuitive controls on the backward process.
Lemma D.4. Assume AD A3 and that there erists n 0 such that M ndiam(M) s 1/4. Then, for any E [0,7] we have
El|l 1
8(1 + diam(M)/n)
In particular M < 1/8 then for any & E [0,T] we have
E Y, P d + 8(1 M M))).
23

---

Published in Transactions on Machine Learning Research (11/2022)
Proof. First, using Lemma C.1 have that for any E [0, B|| Y|P?] < too. Hence, using Itô's lemma, we have
d(1/ - +
Y,) + 2 + 2/ dB.
Therefore, using A3 Lemma C.1 and that for any a, 17 0, 2ab S a²n + b² /n we get that for any E (0, we have that (1/2) | I Ut. where ug d/2 and
du 8T- - + 22
32 2M 2 = 2 2 220
+ (2 + 2M + 222rrrr.aaaamm///////2
For any E [), and x E R define F(t, given by
2(t,z)== -2 of 2(M + m
(M+22 2M -l
Using that for any E [0, T], m,, of E [0, 1], we have that for any / E [0,
2 2- - 2 pmr-cdiam(MM) 2 22((221 nydiam (MM) 1/2.
Using Fontaine et al.
2021
Lemma 3) we get that for any t E [0,
" S d/2 21 + + diam(M))n)/CC 2(M + mjdiam(M)) v d/2 + + 4(1 + M (idia((M)n))
which concludes the proof.
Lemma D.5. Assume AD and A3 Assume that there erists > 0 such that for any E (o...., ......,K) K}. 3k /00 /o2-1,
to S 8. Assume that there erists >> such that A(6, M, n), diam((M > with
A M, diam
2 25 325(1 + M²) 8M Arydiam(M))
(6, M, n, diam(M)) =328(M² + diam(M) + 2(1 (diam +M + 4d.
Then, we have for any K E {(,...,,K K}
E 1 S K = d + B(6,M, n,
diam(MM)) + 8).
(44)
In particular if 1/322 and 1/32 then for any E (O,..., K}
B[]] < 5d + 320(1 diam
Proof. Recall that using 5 we have that for any k E {O...., K -
Yet1 = Yi + Texpl=== Bods] 1)(Yx + (T - 4. Vs)) + (expl2 fT Bods) - 1)2/2
(45)
For simplicity, we denote
T 71, (expL B,ds] 1)/ 22,4 (expp2 TT Bads] 1)
Then, 45 can be rewritten for any &s E {O.....K K 1} as
Y = Y2 3, (Ys + 2s 1k, Yi)) + + 272240T-14 Zx-
(46)
In what follows, we denote 71,4 31 and 72,4 -2, u In addition, using that BT 5 1/4, have that 71, I 72,6 $ 27, Indeed, have that for any k (0, ..... K- 1}
/2,4/114 = (1/2)(exp( T-4 B,ds] + 1) 2 1,
72,//11 (
T- B,ds] 1) (1 (exp) + 1) < 2,
24

---

Published in Transactions on Machine Learning Research (11/2022)
Using Lemma C.1
we have that for any t E [0. 2a R and 17
(z x1))
- - 1
(Mdiia(MM)]lz; o1 + MM1 + [e,|/// - (-1 1 + 2M + (mmdiaa(MM)) || 1 /0? + (1
(47)
where we have used that for any a, b 2 0, 2ab S na² + 6² /nj in the last line. In addition, using Lemma for any E [0.7] and zy E Rd we have
C.1
x1)12 - 2 21 xz) - V (x:)) + 2 V pe
I 4M² (1 + || //// + 1|
/// /0 +
4m/diam(M))/or
S 4(1 n² 1111===11///// 4(12 m
(48)
Combining 46
47
and
48 we have for any & E ......., 1
E
[2]
(1 + 71. E ( [1+
tk 1=
+ 471. + 11. (\), s tg. 1x)) | + 22
< (1 + 271 71,, 11+
/07 ) 1B
+ m (M))
+ 41,,((1 +
1, Yv yx)) 471,d
(1 25, /B - ) + 1² B
+ - 1 (aa dim)
+
-1+ 2M + 1 diam (
+ - (1 71,)+ diam (M)) diam. + M) + ,5d
In what follows, we let dū 71, 1/. Using that for any [0, T]. m,, dr E [0. 1] we have
El|lY { (1+ 20 - E1 | 166 +
+ 1M diam(MM)
+ +1x 6x) + 2M + (ddam(MM)
+ 5 + 5x) (M M) + 48,d
Since 8 + Bg is non-decreasing, that Br- 7h S 8 v 1/4 and that for any E 1/2), et S + 2m, we have
expl/T-te T Bads] expl - [x] 7m] 2, t4 Th-
Therefore, we get that 0 S 37 07 -4 < 28. Since 5y S 28 we have
B||| (1 + 25. + 26 + 32 + E1
+ 46 ( 2M (
+ 32 + diam(M)²
+ (1 (dd M) + 45.d.
Hence, we have that
B[[[+++1111 < (1 + 5u[ - + 25 25 325 M²) + 8M 4ydaama))))
+ [328 diam(M)) 2(1 (ddam +M 4d..
Denote A 2-22 -266-666++ 8M - B 3M 2 +21 (//mm////)/9/111/////////////111 4d.
Then, we have
E 1 || <
6z ( B.
25

---

Published in Transactions on Machine Learning Research (11/2022)
Hence, if || 2 B/A we have that ||||++1|||| B[ In addition, if || B/A then, B[I || & B/A+ + dB. Therefore, we conclude by recursion that for any & E {0...., K}
B||[& S d+ 2(1/A+6)
which concludes the first part of the proof. Tf 6,M S 1/32 then, A(,,M, M, 7, diam(M)) 2 1/22- 401ydii(((MM) We conclude upon setting 7 1/166diam(M) In that case A(d, M, 77, diam(M)) 2 1/4 and
B M, diam(M)) - 325(M + diam(M)²) + 2(1 + 8)(16diam + M) + 4d
2 64(1 diam(MM diam(M)) 4d,
which concludes the proof.
Note that the same result holds for (Yo)
Lemma D.6. Assume AT A and A3 In addition, assume that for any k E {o,... K 1},
NBBT T 3051/4 Then, we have for any k E {0...., K K-13 and i E [la, (x+1)
F Y, 11] LBT- 7k:
In particulor if with L = 8(1 ()(1 + Mº 16(4diam(M) ) + 4 and where K is defined in 44 M M 1/32 and 5 1/32
E| Y 11. $ Lo8r-474 = (64d + 20544(1 + diam(M))) 7k-
Proof. Recall that
Y. + (expl T 8,ds] - 1) + 28(T - tx. Y,,)) + (expl2 ST 3,ds] - 1)2/22,
where is a Gaussian random variable with zero mean and identity covariance and the equality holds distribution independent from Ytc- Therefore, we get that
EI - Yr, 11 = 2(exp15==1 - B,ds] ()3 Y, 11 + [E]]|s(T tx. 113)
+expp| ST 9,ds] - 1)d.
(49)
In addition, using A3 Lemma C.1 and that for any t E [0, T1, me E [0, we get that for any u E [0, and
Th RRd
|s x.)ll s M(1 1| 211==11/0² + 2djam |>-a|| + [|=u||
s (1 (1/0
(M+ 2diam (M))).
Combining this result and 49
get that
E|l Y. Y | = 2(expl fT- 3,ds] - 1)3 11
+4E|l|((T (T'
- 4. Y 2)) + (exp|2 f TT 3,ds] - 1)d
$ 2(expl - 3,ds] - 1)3 1| ||
+ +32(4 + (expl
- -ー 3,ds] - 1) 2 Y 1191/77-1
+ 32((xxp - 8,ds] - 1) + +M²) x²)/07
+(exp|2 T 3,ds] 1)d.
(50)
Since 8 ++ Bg is non-decreasing, that BT 5 5 < 1/4 and that for any E [0, 1/2), 2²w - 1 + 4w, we have for any E {1,2}
expla f _f 3,ds] expla 1 20,37 -1. 7k-
26

---

Published in Transactions on Machine Learning Research (11/2022)
Combining this result and 51 get that
B|I|, Yx S -, Th Y + 32(4+ o +32(4diam(MM) + +143)/07-11
+ 4 7
(51)
s 8(37 Nkl - (32(5
2
(32 M Yd, 12 32(4diam(MM) + +M²) + 4,3 ntd.
Therefore, using Lemma
D.5 and
44
we get that.
B - Y l 11
M (2)4iam() (MMddiammMM+++M3)) + 4,3T 7
(2565( N² 4d)) + M²2) + 4d) BT
which concludes the first part of the proof. Now assuming that 6, M. S 1/32 we have
B - Y |1 S (64K + (MV)) + 16d) 9r
64d + 20544(1 + diam(Mi)
which concludes the proof.
D.4 Control of the tangent backward process
We now introduce the tangent process associated with (Y.) We have
dVy, Brd +2V log
VY, ld.
(52)
We recall that controlling the tangent process allows to control the Wasserstein distance between the original process and its target mcasure. Indeed, let (YT) TeEoTTT and (Y²) be the processes given by (39 initial condition x and respectively. Then we have that for any 1 E [0,
with
YY Y S fo VYAA yll.
(53)
where (VY;) is the tangent process given by 52 and associated with (Y, )cE[o,T); where Σ> A + (1 - A)y. Before providing controls in the general setting, we take detour and focus on the case where diam(M) = 0, ie.. = én- In the following proposition ion, we show that in this case the backward process converges finite-time, This highlights the role of the diameter of the manifold in the subsequent analysis.
Proposition D.7. Assume All and that diam(M) = 0, i.e. ा = S Then, we have that for anyy x. E Rdd and f E [0,7]
W (6, S 2xxp((1/2) Sf (exs) f B.ds] - 1) (exp] 1- 9,ds) 1)2/2 |2 -/l-
In particular, we have that for any x E Rd, SrQr x, i.c. the backward diffusion converges in finite time no maller the initialization distribulion.
Proof. Let & E [0, Using Lemma C.2 have that for any M Ma(R)
(M, 1ogg I -0, IM
In particular, have that for any M E (R)
(M, 2 log qr (0g) & (3T-1- 2,r -8r--o722)|M11
(54)
Using Lemma D.1
we have
(rr - -28T-50
= dh3r-ads log(exp|2 - 3,ds] 1) - log(exp(2 10" B,ds) - 1)
- B,ds log(exp/2 1 B,ds] 1) log(exp[2 10d 8,ds) 1).
27

---

Published in Transactions on Machine Learning Research (11/2022)
Finally, we have that
explSo (8T -
-2 )ds] B, (expl B So B.ds] ">='((xxxp2 S0- TT- B.ds] - 1).
Hence, using this result, 52 and 54
we get that
(1/2)IVY,I < expl B.
B,ds) ( fo'" [,ds] -1;
which concludes the first part of the proof, using 53 For the second part of the proof, we first remark that for any 2, E Rd, Wi(8, (r,Q, ,T) O. Therefore, for any probability measures μ, such that fga [lz])d((z) < +oo and fga [æ]]dv(r) < too, we have Wi(nQr, = 0 We conclude upon combining this result and that (r)r 6g-
6g-
Note that it is also possible to explicitly write down the backward stochastic process in this case since V log is available in close form. One can remark that in this case we recover an Ornstein Uhlenbeck bridge.
In the case where the diameter non-zero, we cannot recover such a contraction. However, is possible obtain contraction up lo certain point. The following lemma will allow to control the growth of the tangent process.
Lemma D.8. Assume 2 and that T 2 2,3(1 log(1 diam(M)). Let t E [0, T] given by
T log(1 + diam(MM))
Then, for any E [0, we have
So 01 - + (m0_:_tmmm_ammm)////_a_a____ --12) 3r-
In addition, for any E [T]
1r 31 - 2/07-, +
diam (M))/ot- (diam(M))/2) - o--r)
diam
Proof. Let 8 E [0, Note that we have
- 2/0 + (iim-,diam(M)) (MaammM)/// S 11/2,
(55)
if and only if
304-; 407- + - <
Hence, using this result and the fact that 07 1 - m we have that 155 is satisfied if and only if
3mt_ + 2(diam(M)) 1)m -1
Introduce P(u) 3n² 2(diam (M)² 1)u 1. We have that P(u) for u E [0, uol with
un 1- (diam(( -1) ((diam(M)² 1)2 + 22/3 (ō + (62 + 3/3/3
where 8 = diam diam(M) (M) - 1e too) If diam(M)² 11 2 then, using this result and the fact that for any
+00), (1 + a) 1/2 2 1 a/2 a a² 2/8 we have
uo 2 6
1/3 2 6(1/(28²) - 3/(85))) 2 (1/2 3/8)/8 11(80)).
(56)
In addition, o < then 8² E [0, 1]. Using this result and the fact that for any E [0 v3+a >
(2 - V3)a + v3 we have
un 2 (-8 (3+ 63+6)/12388
((1 (11 v3)/3 2 1/3.
28

---

Published in Transactions on Machine Learning Research (11/2022)
Combining this result and [66 get that
2 1/(8(1 + (8])).
Therefore, we get that for any 1 E [0, 7 such that m I 11/(8(1 + (0))
1 1 2 + _ (M) /) S -1/2.
Hence, for any t E [0, 7] such that expl-2(T t) 1/(8(1 (0)))
1 1- 2/0 + diam (M)² /ot S -1/2.
Let to such that (00-22(T-tj)//
1/( +8])). We get that
10 = T - ( log + (0]))
Using that for any a 2 0, 1+ a² - 1 < 2(1 + a)² and that log(16) - 4, we get that
t 2 - (B/2) + diam(M)) 2 t = - - + log(1 + diam(MM))
Hence, since + mr-t is non-decreasing, we get that for any t E [0, 1*), mr-t S 1/(8(1 + (61)) and therefore
1-2/0ř_
(aa.dmmmmm S 1122,
which concludes the first part of the proof. The second part of the proof follows from Lemma D.1 and
Jr Br- 2/07- + d diam(M))
TT- B,ds)) - (diam (M)) 2 pT 3,ds)) - 2 2/-
x (ilmm(M)2/22((p3 - -o7-r.;
which concludes the proof.
The control of the tangent process in the case where diam(M) > 0 is given in Proposition Proposition D.9. Assume All and T 2 23(1 - log(1 + di)m(MM). Then, for any a, E Rd and t [0, tk]
Wi < exp((diam(MM) (200))//22)0_x____ ||| < -yl--
Proof. This is direct consequence of 53 and Proposition
E A stochastic interpolation formula
In this section, we present formula first introduced in Del Moral and Singh 2019 which is a stochastic extension of the Alekseev Gröbner formula (Alekseev 1961 We recall the definition of the stochastic flows (Y",))..esoor)) and the interpolation its discretization sE(O,,T, for any x E R
dY B S, + log (Y: Jt + dB
Y
s.s
and
dY: 5,t = B 2s 14 T s.1. )dl dBBr
T.
8,8
The following proposition is a straightforward application of (Del Moral and Singh that these results apply since the drift and the volatility of the backward processes have bounded differential up to order three, see Lemmna C.5
2019
Theorem 1.2). Note
Proposition E.I. Assume A Then, for any 8, t (O, with and E Rd
Y a2 Y 5,t J. Y
utt I (Y.s))))eo)))
where for any E [0, T) such that E [le, (x)) for some k {0, ...; K 1} and (uo) E C((s, u) Rd)) have
(w) = 3r- (w + 2V log ar-araal (ww)).
(u(w) = 3r- + 2s(T t wiy ))
Abu(w) ba. bu(w)) (w).
29

---

Published in Transactions on Machine Learning Research (11/2022)
F Additional comments on Theorem i
In this section, we discuss the validity of A3 and then comment the suboptimality of the bound of Theorem 1
F.1 Validity of A3
First, we highlight that under 1
3 is satisfied if for any (0, and 24 E Rd we have [|s(t, 2x))
V log (ex))( I M/ (o;))())) with M, 2 0. Indeed, using this condition A Lemma C.1 and letting M = 4M, (1 + diam(M)),, we get that A3 is satisfied. Hence, A3 is implied by control the relative error between the score function and its approximation.
Assume that π do- Then in that case V log = V log 0) and we can compute explicitly the error [| xz) - V (x)))(>>)] at given query points (4, In Figure 1 we analyze this error in two-dimensionall setting. In particular, we recover that the behavior of the error is explosive as |||||| + +00 and + 0.
10
22
50
0.85
Figure 1: Target is Dirac mass at 0. Left: norm of the truc score || log (o)))))))))l (æ-axis: time evolution (T = 1), y-axis: spatial evolution (along the first coordinate, second coordinate is fixed to 0). Right: norm of the error between the estimated score and the true score ||s(1, x) - V Prjoo))) (æ-axis: time evolution (T = 1), y-axis: spatial evolution (along the first coordinate, second coordinate is fixed to 0).
Finally, we conchude this study by illustrating the explosive behavior of the norm of the score in a two- dimensional setting (we restrict ourselves to this small dimensional setting so that we can get dense grid of query points without encountering memory issues), see Figure] We emphasize that the norm of the score has similar behavior the error term, f.c. it is explosive
x + +oo and 0.
100
104
20
255
-5.6
-75
-100
-105 -25
-30
-23
0.0
25
5.0
7.5
10.0
-10.0
20
Figure 2: Target is the uniform distribution on two concentric circles. Left: samples from the target distribution (orange) and samples from the diffusion model (blue). Middle: trajectories of the diffusion model. Right: of the estimated score [|s((, (æ-axis: time evolution (T 1), y-axis: spatial evolution (along the first coordinate, second coordinate is fixed to 0).
30

---

Published in Transactions on Machine Learning Research (11/2022)
In both settings, the score function is learned by minimizing the Denoising Score Matching objective 3 using the ADAM optimizer. The architecture of the network and training settings are similar to the ones used in De Bortoli et al. (2021a).
F.2 Suboptimality of the bound
Recall that the generative model is given by L(Yk). In Theorem 1 we provide an upper bound on W ()( In this section, we compare the obtained bound with a bound on W ((()) Recall that Yo ~ N(0, Id). Considering any coupling (X, such that X a and Yo ~ Id), we have
Wi(C()), T - E| III + Yoll & diam(M) + vd.
This naive bound can be better than the one obtained in Theorem 1 especially for large values of Do- If that is the case then the derived bound seems to be vacuous at first sight since diffusing the process backward does not improve the Wasserstein distance of order one between the obtained model and the target measure. However, we argue that such cases are possible especially if we are using a poor estimation of the score, i.e. a large value of M in AB Indeed, neglecting the discretization error and sctting f = for simplicity, the backward process given by
d'. (Y. 2s(T - t, Y.) VdB
YO~ Id).
(57)
Assume that 8 = 0 (which is approximately the case at initialization if we parameterize with a neural network with a fully connected last layer and no non-linearity). then the dynamics becomes
dÝ. Yd,t VdB,, Yo TT To Id).
(58)
In that case, for any L E [0, 7], Y, is Gaussian and we have that L(Y.) N(O, ((3exp/21) - 1)/2) Id). In addition, we have that for any f: Rd + R which is 1-Lipschitz we have
wi(C(Y B[S(Y,)) Su ((x)dx(x))
Choosing f(x) -121 for any (II....., x2) Rd in the previous inequality get,
wi(C(Yr), 2 (3 expp/22] 1) di)m(MM.
we get that W (C( WI T). This result implics that even in idcalized setting, the backward process might steer the Gaussian distribution away from the larget distribution æ. This is due to the explosive property of the Ornstein- Uhlenbeck process which should be compared to the contractive behavior of the forward Ornstein- Uhlinne--heebckk process
Therefore, choosing T 2 0 large enough and using 57
(58
G Assumptions on the schedule
In what follows, we consider three schedules commonly used in practice: (a) the constant schedule, (b) the lincar schedule, (c) the cosine schedule. We show that A is satisfied in all those cases. We consider a generalized version of the cosine schedule which makes dillerentiable by replacing the hard clamping by a soft version with level > (note that letting - 0 we recover the original cosine schedule). The constant schedule defined by B, = 3o for all E [0, 2.. The linear schedule was introduced in Ho et al. (2020) and is defined by 8, 3o + (3r Bu)t/T with 37 8o O. Finally, the cosine schedule was introduced in (Nichol and Dhariwal 2021 Equation (17)) in discrete-time and can be defined as follows in continuous-time
8 = softmin, (1, lim (āi-h as)/ = (1, h-10
f(t) = -á,/
with ā defined
a 1 coss///s///////c (TT22))
and where 17 2 0, r are parameters and for any f1, f2 [0, + R+
softmin, (J1, f2): -r - logg((ep(-51( (1
expl- f2(p/)2(()/r)).
31

---

Published in Transactions on Machine Learning Research (11/2022)
In the special case where fi we have
softmin, f2), = -1rrlo + fe(t))/rl).
We have
n/ (TT22))
In particular, t E+ Se is increasing and bounded above and below on [0, [].
Finally, we end this section by remarking that if one aims at studying the Fuler-Maruyama discretization of the approximate backward, iee. the process given by (26) then one needs to also assume some Lipschitz property on the schedule + B..
H short proof of the results of Franzese et al. (2022)
In Franzese et al. 2022 Equation (9)), the authors show that (under mild regularity assumptions
Jg log pe,r (2))p fga log log ( (prplp)))).
(59)
To do so, they rearrange the ELBO result from Huang et al. (2021) We have that 59 is equivalent to
(L(PolPe.T) S G(s,, T) + KL(pl)po)).
(60)
The definition of G(se, T) is given by
G(so, T) (1/2)( (E X.) V log X. Xo)1
- B logga (X,) V log X, 111)
Developing the square and using that E log X, X, = V log (X)) we get that
((s0, T) fo 3 so (1, x,) lo
Hence, combining this result and (60), we have that 59 is equivalent to (Song et al. 2021a Theorem 1) which is obtained upon combining the tata-processing incquality, the decomposition of the Kullback-Leible Leibler via conditioning and the Girsanov theorem.
Wasserstein controls under L errors
In this section, we replace the assumption A3 by the following weaker control.
A5. There erist C((O, T| x Rd, Rd Rd) and M 0 such that for any k E {O..... K} and E Rd,
E [|||s(T L Ye)= log (Yx) E + ||x|||++++))]]]]]] ||
where we recall that (Y)),E is given by
Note that this assumption is different from the one of Lee et al. (022) as the expectation is considered w.r.t. [Y&) and not (Y In order to control the L error, Lee et al. (002) use a change of measure and control the x2 divergence between the density of YE and the one Y., for any i (0...., .,, K). These controls are obtained using logarithmic Sobolev assumption on the target measure æ. Adapting these results to our Wasserstein distance setting is not straightforward and is left for future work. Under AB] we have the following theorem, which is an extension of Theorem | To prove this theorem, extend (Lee et al. 2022 Theorem 4.1) ) to the Wasscrstein distance of order one and weaker growth conditions.
We that all probability measures admit densities w.r.t. the Lebesgue measure and that the integrals we consider well-defined.
32

---

Published in Transactions on Machine Learning Research (11/2022)
Theorem 1.1. Assume A 1 A2 A4
A5
that T
tx - and E, M, M/S. 8 & 1/32.
Then, there erists Do 2 0 such that.
WI(C(Kk), m) - Do(K + (XXX+exe///eM( expl=/ 1!1)),
with k = diam( + 3)/2 and
Dg D(1 + 5) d diam(M))))(1 + log(1 + diam(M))).
and D is numerical constant.
We start with the following lemma, which is an extension of Lemma D.5 to the setting where A3 is replaced by A5
Lemma 1.2. Assume A A2 and A 5 Assume that there crists 8 > 0 such that for any is K}. p.Br--1/o7-- S 5. Assume that there enists 0 such that A(,, M, n, diam(MM) > 0 with
A M, n, (iam(M)
25 325(1 + M²) SM 4ndiaa(MM,, (6 M, 7,, diam(M)) = -325(M² + diam(M)²) + 2(1 + (ddimm) + +M + 4d.
Them, we have for any l E {0,..., K}
E E| 1 S K d + (66,M, n, diam(MM))(144(..M diamm + 8).
In particular if 1/32 and 5 $ 1/32 then for any k E (O....,K) }}
E < Ko = 5d + 320(1 + diam(MM))
Proof. Recall that using 5 we have that for any k E {0,.... K - 1}
Yet1 Vi + (exp) -4 3,ds) 1)(Y: + 2x(T Lx, Yx)) + (expl2//1- T-tx B,ds] 1)2/2 (61)
For simplicity, we denote
7 = (expl,7 B,ds] 1)/3r-1a 12,6 = (exp(2 TT B,ds] - (2)
Then, 61 can be rewritten for any k E (0...... K - 13
Ya+1 = Y& + 11. (Yx + 2s(T tk. Yt)) + 2722t8r- Zx-
(62)
In what follows, we denote 71,6 71, and F2, =2 . In addition, using that BT 5051/4 we have that 71, $ 72.6 S 27, Indeed, we have that for any & E {O....,K'
72,4 (1 (1/2)(c -- B,ds] +1) 1,
72.4 (1/2) (expl B,ds] +1) < (1 (12))(xpp/= + 22
In what follows, for any E [0, T] and x, E Rd. we denote A, ||s((1,xx) - (og)) Using Lemma we have that for any E [0, 2, E Rd and 7> 0
C.1
(x,, (11,8(1, 8(1,
xx)) < - 1 /0/ + m.diam(M))lzzll)) +r(x))]aaal)) (-1 + pm,diam(MM) ||>, /0 (m.diam(M))nn) + Ae(x)))=elll
(63)
where we have used that for any a, 62b2 0, 2ab na² 6² /n in the last line. In addition, using Lemma for any E [0,T] and 2, Rd we have
C.1
x1)(2 < 2l) Vogm 2/
lo (x:)1
(z)) + 4||x>.11//0 4
(64)
33

---

Published in Transactions on Machine Learning Research (11/2022)
In addition, using A5 the Cauchy-Schwarz inequality and (63 we have
E| (T t2 Yo)I I (-1+ + mp (aaaa + diam
+ E|Ar [Y&
< p diam (M) || |x -1) + diam
+ - (X.9
$ (-1 11 diam (M)) || 1////0 + (Ima-i,damm(M)m/n))/
+ M(1 + 1/ (1/ ( | /0/0
< (-11 7 diam (M) - M) 1 + 1ae-++++mmmm- (inm +ME1/2 (| ||/
S + diamm + 21) ( &
1111//07//// + (mr- (iamm,
(65)
Finally, using A5 and 64 we have
+ 4B [T - 1x: |I2] S 4E| AE(AT- + 41 + 4m diam (M))
< 4x² (1 + B (1) 04 + (x /0 + 4m diam(M)
s 4(1 + M² [ 11/ + 4(1²2 + m co /
(66)
Combining 62
65
and
66 we have for any k E {0, ......,,.. 13
[2] = (1 + 71,x) 3 [7
45,, ||||
14. 1=)
+ 41 + 71. (B. (T 12, Yx1) + 27
$ (1 27, + 72, - 1600, )² + M² B[|Y?)?
+ ( + (M))
+ 41 (11x(1+11,11 B s(T t4 {x)) 47
< (1 + 25 + + - 166)1,16(1//////11 07. ) ) + ||||
+ +16(51,1007 (M + + diam (M)
+ + 1 (1 71,+)(11++ + 17m -1, diam 1xll
+ ( (1 (im (M + M) + 47,
The rest of the proof is identical to the one of Lemma
D.5
7
Let <> O. For any &e E fo. fo...., K} we define A such that
A (y E Rd ||s(T (,, v) V Vlogpr-a > (M/C)/o7-12+
We define the process (Y (E such that Yo = Yo and for any k E tO....,,K - 13, if Yv. = -Y and
Yg E A& then + = Yet1. Otherwise, we define
T- Y Yt + (expl[T-tx B,ds) 1) + 2V logpr-1, (Yt)) + (exp(2 f- B,ds] 1)1/2 2k.
This is similar to assuming that there exists s" such that for any t E {0, ........ K- 1}
lu Yt)) + (expl2 -T- Bods] 1)2 Ye+ Y + (expLf--m -M 1a A.ds] 1)(EE + 28
with s* which satisfies 10 A3 with M replaced by M/C and while Ye E Av, Ygt1 YK+1-
We have the following lemma which is extension of (Lee et al. 2022 Theorem 4.1) to the Wasserstein setting. Note that contrary to (Lee et al. 2022 Theorem 4.1) which states results in total variation we also
need control on the moments of the distribution under a I,2 error, which is precisely Lemma I.2
Note that we slightly abuse since random (depending on the behavior of Y2) but one can check that all our proofs remain unchanged in this slightly larger setting
34

---

Published in Transactions on Machine Learning Research (11/2022)
Lemma 1.3. Assume Al
A2 and A5
Assume that there crists 8 > O such that for any 5 /32. Then, we have for any l E {O,..., , K}
"1-BT-4 11/00/00/0 S 5 and that M, C
B Yx - 4(1 Ko)Ck,
where Ky is defined in Lemma
1.2
Proof. Using the Cauchy-Schwarr incquality have
E Yxll 1 - |
A,))
$ v 22 + (X
P(1ss((((( 1,, Yj) ( (M/
(67)
Using the Markov inequality, we have for any E {0....,K) K
F([[s(T- t2) v logPT (Y3) (M/C) (M/C)/o7-1)
$ s( M2) V Pr- (Y,) 100
101 <² 2/2²² S E ||X,
Therefore, combining this result, and Lemma
I.2 we have
B| Y Yxll| S
We are now ready to complete the proof of Theorem Proof. We have Note that using Theorem have
W Wi(C(Yk), (I(C(Y)) + +
(68)
W i #) D expl=/ + 619)).
(69)
In addition, using Lemma
we have
(I((())) s 4(1 Ko)ÇK.
Combining this result and 69 in 668 concludes the proof.
J Improved bounds under Hessian conditions
In Appendix J.1 we prove Theorem 3 which an improvement upon Theorem under tighter conditions on the Hessian 2 log Appendix J.2. we show that this condition is satisfied the case of a uniform
measure over [-1/2, 1/2] for some p E (L....,d}. Finally, in Appendix J.3 we show, under appropriate smoothness conditions, that the condition is never satisfied non-convex sets.
J.1 Proof of Theorem
In this scction, we prove Thcorem We start by deriving an improvement on Proposition main difference between Proposition and Proposition J.1 lies into the dependency w.r.l. Or-tas In
The
Proposition 6 we have an exponential dependency sMp(diam(M)) have a polynomial dependency 0r-tx"
whereas in Proposition J.1 wo
-2
For ease of notation we introduce the following assumption.
A6. There erists I such that for any t e (0,T) and 2, Rd, |o < ST/O..
We start with the following proposition.
35

---

Published in Transactions on Machine Learning Research (11/2022)
Proposition J.1. Assume A A6 and that T 2 23(1 log(1 diam(M)). Let tk (), Then, for ony E [0,45 [x] and x E T&d we have
IVY expl- S p..r (t)r)) 27 expl(T + + M T-r²
P.du).
Proof. Let I E Rdd First, using 13 and Lemma C.2 we have that for any 8, 1 E [0, T with 8 S
d 111 < - 2ell² - 2(1 - diam(()
lY )
First, assume that s t* and that t 2 t* In that case, using Lemma D.8 we have that
St 3T-u(1 2/07-1 + diam du S -1/22 S" ar-
Therefore, using that result and the fact that V 8,8 =
Id we get that
IVY s, S expl- - Budu).
(70)
In addition, using that for any E [0 and 2a E R |2 (x s <T/a? we have
d V x.ll & 20 (1 + -1 <0 l3d.
Pd
In addition, using Lemma D.I we have that
BT + 2r/07 dus (llog(exp? 2 S -/- 3r- - 1)
- -log(exp|2 fo - 3r- - 1]] - 3
Mlog(o?--1)) log + (T + (1+ 1 T-1 3
- - -log(o + (T 1) F Budu.
-
Therefore, combining this result and 70
get that
S -T 2r (( 1) PT Budu) VY s,t'||
$ _xp=1_xppp 1) fT- pud expl FT B,
The proof in the cases where 2 t t. and s S < t are similar and left to the reader.
The rest of the proof follows the proof of Section The following proposition the counterpart of Proposition 10 Again note that the exponential dependency w.r.t. 1/e has been replaced by polynomial dependency.
Proposition J.2. Assume A Then
A
2
and tk T E. In addition, assume that e, 8.M < 1/32.
W1( Qix: Toe Rx) S Do(M + 52/2)/6r+2
where
4(4 256d + 43664(1 + diam(M)))) exp(3(1 () + 2)(1 + log(1 + diam(M))
Proof. Using Proposition 5 we have
Y Yxll S 1d IIVY a, (ll.,,))Ab,(( (Yo,r)eeo)o))) |du.
Combining this result, recalling that t* is defined
14 and Proposition J.1 we get
Yix Yxll S/ exp(-(1/2) ff 3,ds1 oo. (.)) (
2r
36

---

Published in Transactions on Machine Learning Research (11/2022)
expl(T +1 f- (.a.)
S T T- -1- eXpl(T + 1) 1 Bedss(So (xpl((1/2)
fT p,ds]Ab, Aaabu((YYy)) (0)
+ S t Ab Ab,
Using this result and Proposition we get
Wi TT Qix Rx) E Y Yxll
T- exp((T 1 T B,ds](Lo expl-(1/2) (Ya
1/xh ( ((a,))
21 T- cT 1) T-ア - B,ds| tk 3M + 81/3)/(T -tx)²
x(o (xp[-(1/2) f.d
B,dsddu + -xx
1*) 1*) 1k + 3) + ///2)/(T -xx)²
21 T- exp[([ + +1)
x(S² expl-(1/2) Bdd)j
3.dsddu + t*).
(71)
We have that
So expl- (x 3,ds]du S So expl-(t" (10((ttt)(223))) u)/(2 s 23.
(72)
In addition, using 14 we have
tK - = - T + 2 + log(1 + diam(M))) s 2 + log(1 + diam(MM)).
(73)
Finally, using Lemma D.2 we have that oT S (1 + 3)/e. Combining this result, 72 and and that for any 2 0, I a S expla), get
73
in
Wi Qix Too
To Rx) s 4(1 + 3) +3 (1 (1+ + log(1 + dia)(M)))
exp 2 (1 + log(1 + dia 62/3)) 4(1 + By 3 + log
diam(MM)) (
x exp e + () + log (ia + e -(T+2)
2 (1 log(1 8 (TT+2)
which concludes the proof.
We now state the equivalent of Proposition D.9
Proposition J.3. Assume Al A6 and 2 23(1 + log(1 + diam(M)). Then, for any x. E Rdd and
E [0,4k]
W1, Q+) I eXp 11 log(1 diam()M)))) 2r || yll-
Proof. This is direct consequence of 53 Proposition J.1 and
77
Finally, control W1 WI Qix xPT-(x) First, we have
WI Qik x xP)- WT Qix Q(x)
(74)
< exp|2(T + 1) + log(1 + diam(M)))oo72f, 21
To control W1 (TPPr ),o), we synchronous coupling, i.e. set (Y,, Z,) Z)) such that
dY, = - 3, Yd / /2,.BB, dz, -i S00ll++233:/ 23
where (Be)eejo.ry is a d-dimensional Brownian motion and Y, ~ ग. Zo ~ Toc. We have that for any / E [0,T], Zi Too- In addition, denoting 4, = R - Zell] for any E [0, T), we have that
du, un explp 1 B,ds).
37

---

Published in Transactions on Machine Learning Research (11/2022)
Therefore, combining this result and 74
get that
oT Qik xPr- I exp + 11 + log(1 + diam (M))) expl- So W, mo)) Therefore, similarly as in the proof of Proposition 10
wc have
WT Qix: PP s D1 expl exp1-T////E7
with
D1 = ex 2)(1+ + (1 + log(1 + (
We conclude the proof of Theorem upon combining this result, Proposition J.2 and 24
J.2 Hessian bounds for the uniform distribution
The goal of this section is prove the following result.
Proposition J.4. Assume that x the uniform distribution over 1-1/ for some E (I,...,d}. Then, there ezists r such that for any E (0, T] and Rd (o S r/o?.
Proof. Let E (0, T]. We start by deriving closed form expression for ps. We have for any x E Rd
(x(x)
JM expl || m
4/2 -4/2
expl-
2impt1 /2
d
expl m, /2 (f d/2 1 1/
expl-
Limpt1 /
- 2x (20 -d/22m m/²
expl-
Σ Dim++1 27 (20)
(a: t 12) /2) expl- (
(2/////
=(2T) 4/2 (2TOT) -/22 ( (at///)) ((x//01)
x I (xF + m4/
2)/ /2
4(<x; - m 22)////))
where (p(t) = expl- 2m and ((t) = - p(s)ds. Note that from this expression, V log is diagonal. Hence, only need to compute 87 log P: (x) for any IRd and i (l. Let i i {o + 1, I...., d). We have for any x E Rd
0f (z) (z)=
We now turn to the case where E {l,....,p) p}. In this case, we denote F2 b) = 8a + b) - +aa b) and have
logg,.(r) (0 (1 log m/
(75)
We have that for any a, b E R with a a b
o log F. b) b) = Fr b)F. D((
(76)
In what follows, we assume that a > b and we define for any / E TR
erfe(t) (2/ S4 exp[-s?lds
Note that F b) (1/2)(arf(((a- b) erfe((a + b)/))). In addition, there exists C > O such that for any L + 0 we have
In particular, we have
b. (106:4)))== b))(1 + Ro(a, b)), F((2, 2 expl-(a ()/ 6))(1 - Ro(a.
(77)
38

---

Published in Transactions on Machine Learning Research (11/2022)
where
Ro(a, b) = C/ - b)² + Ro(a,b) b) = CC/(a b)2 expl+(a- (a- (f-00//l--b///+++0)////
Note that there exists Co such that for any a, E R with 2 b+1
(Ro(a, b) + Ra b) b)² 5 Co.
(78)
In particular, there exists ag 2 0 such that if a 2 b + do, Ra b) + Ro b) s 1/2. Similarly, we have
Fi(o,,,b) = (2Tt) ( 1/2 (apl-(a (- expl-((e + b)² (a - b))))))..
(79)
We denote (a b) = expl-((a b)² (a /)2 and note that there exists C₁ 2 such that for any a,b with a 2 b+1
Rí Ri b)(a b)2 s SG.
(80)
Finally, we have
Fr(e', b) = (2rt) 1/2 -xp b) + + b)/ (a b) expl- b)² b)2)/))-
(81)
We denote [2 b) = (a + b) expl ((a ((a+ + b)² - (a 1-))) and note that there exists C2 2 0 such that for any a, b E I with a 2 b+1
[a b)(a - b)2 S Cz.
(82)
Combining
76
and 81 we get that for any a, E R with 2 b+1
B log F, S (a- - (11 + R2(a, b))(11 + Ro(a,
- (1 (aaab))) + Ro(a,b)))
In addition, have for any a. E R with b b+1
(1 + R2(a, (a(a, Ro(a. b)) - (1 + (a 6))²/(1++ + Ro(a,b))²
= (R2 ()) + Ro(a, b))² - - (a, + Ro(a, b)))/((1 + Ro(a, b)) (Rooo b))]
Combining this result,
78
S0
and 82 we get that for any a, with a 2 b
R2 (1 Ro b)) (a, b)(1 + Ro(a, b) < 4 C2)((a 6) b)
Therefore, there exists C3 2 0 such that for any a 2 b- au. 10g log Fi a, S C3. Similarly there cxists
C4 2 such that if a S -b ao, 10% log ( a, b)l S C4. By symmetry, there exists C3 2 such that for any 6 + do or -b -a ao: we have 102 log (e a, b) S Cs and we conclude by continuity that there exists C such that for any a, b E R,
8 log ( a, b) < C,
which concludes the proof upon combining this result with 75
J.3 The role of convexity
In this section, for any Rd, we define fa : M -> R4 given for any y E M by fa(y) = || - yll?. Before giving our main result. we need to introduce few useful tools.
For any subset X C dd and empty. We say that a set X is Chebyshev if for all x E Rd, there exists p(x) E X such that P(x) = (p(x)), i.e.
Rd define P(z) {y E X d(x,X) = d(z, v)}. Note that P(x) can be
Chebyshev sets are the subsets of Rd such that each point admits a unique projection on X. It is clear that all closed and convex sets are Chebyshev sets. Note that all Chebyshev sets are closed since for any Chebyshev set X and i.e. x e X. In addition, Chebyshev sets are also convex, see (Kritikos 1938 This result implies the following proposition.
ØX (the frontier of X) we have that there exists p(z) e X such that d(x,, p(z)) =d(x X) 0,
Motzkin 1935 Bundt 1934
39

---

Published in Transactions on Machine Learning Research (11/2022)
Proposition J.5. Let X C R X is closed conver set if and only if X is Chebyshev set.
In order to prove our main result, we introduce some basics on Morse theory. Assume that M is smooth manifold and f E C (M, We say that æ E M is a non-degenerate minimizer if x E .M is minimizer of f and the Hessian of f at x: is not singular. We then have the following proposition (scc Matsumoto 2002 for instance).
Proposition J.6. Let f E (M,R) and a E EM non degenerate minimizer of Then there exist C CM open and ip U (PU) IP local chart such that (p(x) and for any 1 (P())
f(g (0)) = f() + 1111.
In addition, we have Di((x) fzz).
Note that upon considering y (v((U)2) instead of U we can always assume that yp has bounded derivatives. Finally, we introduce the concept of shape operator (also called second fundamental form or Weingarten form), see (Bishop and Crittenden] 2011). We assume that the metric on M is the induced Euclidean metric. Let N E &T(TM') a section on the normal bundle T.T We define 2 :(T.)) - c (M) such that for any V1, 1/2 E T(TM)
(V,, 1/2) = - -VV Vv,
Note that N is symmetric, linear and the scalar product and covariant derivative V are considered w.r.t. the ambient Euclidean metric. The shape operator encodes the local geometry of M. For example in the case of 5d-1, we have that for any N E [TTMT) and V1, V/2 E ((TM)
21 (Vi, (Vi, v2) (No,
(83)
where No is the normal vector field pointing outward of the sphere, see (Absil et al. 2013). We have the following result, see (Bishop and Crittenden 2011 Theorem 3) and (Bishop) 1974). Proposition J.7. If M is conver then for any N P(TMT) such that for any x, M, (y - x, N(x)) 2 0,
I is non-negative.
Finally, let JE C R) and f its restriction to M. Using AAsil al. 2013), we have for any Vi, V/2 E T(TM)
v2 v2) = (VI. + qn" (V. V2),
(84)
where for any M, 1I, is the orthogonal projection operator T.M. We are now ready to state our main result.
Theorem J.8. Assume that M C Rd is smooth manifold and that æ admits smooth density w.r.t. the Hausdorsf measure on M. The following hold:
(a) M is conver then for any x E M we have lim sup, 2 log pi (m) < toc.
(b) If there erists x Rd such that [P(x)] > 1 and for any p(x) E P(x), lim inf,- o V (m > 0.
20(x)== > Id. Then, we have
p(z)
Theorem J.8 implies that one can obtain information about the geometry of M by computing the Hessian of the logarithmic gradient of the densitics of (C(X,))ne(o In the convex case the scaling w.r.t. is of order o. whereas in the second scenario the scaling is of order 0,1. Note that the condition "there exists E Rd such that [P(x)] > 1" is equivalent to assuning that M is not Chebyshev set and hence
convex set in virtue of Proposition J.5 Therefore in Theorem J.S (b) we assume that M is non convex and curvature condition. The condition 20(())= > Id implics that the manifold is not too "negatively curvod" at the projection points. The non-strict inequality is always true, iee. for any p(x) E P(r),, p(())= > - Id since
v²(=(((()) 2 0.
We conjecture that this curvature condition can be relaxed. Indeed, it is not satisfied in the case where 1}, since the only point E IRd such that [P(x) > is 0 and in that case
M (ar Rd |a|||
40

---

Published in Transactions on Machine Learning Research (11/2022)
P(z) M and therefore V p0 0, which implies that for any E M, 2 = - Id. This formula could also However, one can show that we still have lim inf o log pr > 0. In future works, we would like to relax these curvature conditions assuming that the manifold has an analytic structure and using results from |Combet 2006).
have been obtained from 83
Finally, we highlight that Theorem J.8 (a) is weaker than the condition A To bridge the gap between Theorem J.8 and A one would need to strengthen Theorem J.8
a to derive uniform in space bounds.
This would require to use quantitative version of the Morse lemmas, see (Le Loi and Phien 2014) for instance. We postpone this study to future works. However, Theorem J.8 ( implies that A6 does not hold. Hence,
any non convex set which is not too "negatively curved" does not satisfy AG
Proof. (a) First, we assume that M is convex. We show that for any x E Rd and p(x) E P(x), (p("(((a)) > 0, e.e. the Hessian of f is not degenerate. For any E Rd, we define f such that for any E R. (* = | Using 884. we have for any x E Rd
(=(²((())) Id (x(x))== > ld O.
(85)
Since M is convex for any x E Rdd P(x) = {p(z)} and note that P(x) is the set of minimizers of fa. Let
x E IRd. Using Proposition J.6 and 85 there exist U C M open and : + (UU) C RP a local chart such that p(p(x)) = and for any ÿ E (U)
| p (0) || p(z))1 11013,
(86)
with - = p(a).. Note that (0- = (V2 ()(x)))) For any E (0, 7]. denote d = =m//oe. Using 86
we have that
= ( - |m) 21
(wo 2 -mm w0 expl
( (fi)
x ) -
= =(1/A) (1)) (00/At) - ( cxp[ |800 oxp
/opp (2) (0t)
(m p(z))1
where A = admits a positive density w.r.t. the Lebesgue measure. Therefore, there exists Co 2 0 such that for any t E [0,7]
11 fl (yo - y1 022 (ma yo (mm vi =1113/2)drrro)ddr (v))) (2Tz/ x
$ Co (2(t)--Ppp Jaay 1100 91 exp0
1222 expl- 11: /2/
x (xpl-(mm/0,)) ) p(
< 2Copoo expl (m.
(87)
where we have used that ||a 61 - 2[ 2 + [bb12) for any a, 6 RP in the last line. In addition, since is open we have that M n U compact and since for any y E MM lly - æ=I > IIp(x) - x11 there exists such that for any y Mn Us Ily -y-xpp x1|² > (lx(x) - x1|2 + e. Therefore, we have
Ilmmnue) v1) 82 expl- ) 30ll (m) 21 1l (2)
< diam(M)² expl e 11 - p(z) || expp_=
(88)
Combining 187
88 there exists C 2 0 such that for any & (0, and
(2T(/²)) Pll PIlSSe (yo y1) (xp |/ emp (200
C1o² expl - (m. / 12 ((z) |/3]
(89)
In addition, there exists C2 > such that for any t e (0,
(2T expl-(m=/a.)) 2 v112/2)d=
p())
(90)
41

---

Published in Transactions on Machine Learning Research (11/2022)
Therefore, combining (89 and 90
get that there exists C3 such that for any t (0.
M - V1) 20 expl-((4/aa))11a yu [2] (m: NUm expl -lll====ll///d/))))) /1) 2 C307.
We conclude the proof in the convex case upon combining this result and Lemma C.2
(b) Second, we assume that there exists x E IRd such that [P(x)] > and for any p(x) E P(x), 2p(x)-=> -ld.
Using 884 we have for any p(z) E P(x)
(p(()) = Id +d+221()) 0.
Using this fact and that P(x) the set of minimizers of f and compact, we get that P(x)] < +00. Hence, assume that P(x) = {><(x))); with N > 1. Using Proposition J.6 for any E (1,..., N), there exist. U, c M open and pp: U, (U,) C IP local chart such that (p)() 0 and for any E p;(U))
|| - po (0)1 || - p: (x)]l + 11911
with (0) = (x)). Note that Di, (0) (V² fz (p:()))) Without loss of generality we assume that for any j E (1......NY NY, U, Unnu,
= D. We have that
fu,xu, (vo v1 82
- 1 (x
16, (U)x( (v)) (po (0o) 9i (01) (mr ||
x - o,
p(x)]1
= (1 2D (
(10 - pi (D1/Ae))
x exp - |0 expp |
d+ (0) (mp p(x))1
(91)
In addition, using the dominated convergence theorem have
lim (2T) (,, (6o ii ()))
(92)
x expl-1166 1160111 cxp[- /2 d (01)
(x)))
where h is the density of म; ( w.r.t. the Lebesgue measure. In addition, there exists C₁ 2 such that for any t E [0,
(2/ p/2 Ju. (xpl-((m/o)))]1 yo y01l3/2)d
=(T) p/2 J ((,)) )m 1100ol1 /2 (xp)) (mp p(x))1]
- C₁ expl- - 11
(93)
In addition, since Up is open we have that M n Up is compact and since for any y E M Ug. l1I 2112 [lp(x) - 122 there exists > 0 such that for any y E MnUs, Iyy x|1 [lp(z) - z + Therefore, we have
Smnug expl-(m,/o /o, ) goll2/2]dTT(p)) $ Cs (mp
p(=))1 eeppeeeppp(eeeeem
Combining this result and
93 we get that there exists Co such that
(2n/ (2m/X2) SM expl (m:/a, / 1|= 3o 222 < Co exp(-(m;/ ) p(z)11//2).
Combining this result, 91 and 92
there exists C7 >> 0 such that.
lim inf J (No- - 11) 02 exp[ (aapl-(mm/a, Mo |1 / expl- (m) w1
(+0
> (zo 20//0///
We conclude upon combining this result and Lemma C.2
42


Reviews:
[{"review_id": "FtA5waur4m", "reviewer": "Reviewer_W6qc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n- The work considers all the approximations made by DDMs in practice, which are: the approximation of initial condition by $N(0, I)$, the approximation of the drift, the approximation of the $\\pi$ by an empirical measure and the discretization of the SDE.\n- One can read off the  dependence of the bounds on different parameters and approximations.\n- The constants in front of the bounds are made explicit in the proofs. \n- Assumption 3 furthermore is a novel way to measure the error between the approximation, which could guide further research in the area, since it fits the problem well and is more realistic than expecting uniform error bounds. Also the results show, that by measuring the error in this way, one is able to make the Wasserstein depend linearly on $M$, further emphasizing that this a good way to measure the approximation error.\n\n## Weaknesses\nIf the drift approximation is not perfect, the bounds are of the form $\\exp(1/\\epsilon)/\\epsilon^2$, where $\\epsilon$ is the size of the last step. The last step is often chosen as small as possible in practice, e.g. of the order $\\epsilon = 10^{-3}$ or $\\epsilon = 10^{-5}$. To put the derived bounds into context, I want to quickly derive a bound between $\\pi$ and the initial condition of the reverse SDE, $\\mathcal{N}(0, I)$.\n\nTo that end the triangle inequality can be employed to derive\n$$W(N(0, I), \\pi) \\le W(N(0, I), \\delta_0) + W(\\delta_0, \\pi).$$\nThe first term can be bounded by\n$$W(N(0, I), \\delta_0) \\le \\sqrt{d},$$\nsee Lemma 2.4 of [1]. The second term can be upper bounded by $\\text{diam}(\\mathcal{M})$. Therefore, the distance between the initial condition of the reverse SDE and $\\pi$ is of order\n$$W(N(0, I), \\pi) \\le \\sqrt{d} + \\text{diam}(\\mathcal{M}).$$\nThe constant $D_0$ exceeds this bound, and the exponential terms afterwards will amplify this term if the approximation error is not of a very small magnitude. \nTherefore, for realistic choices of the parameters, this bound is probably larger than $\\sqrt{d} + \\text{diam}(\\mathcal{M})$. Nevertheless, I think this work is an important contribution to the literature, since one can read off the relationship between the different parameters and how they influence the Wasserstein distance, see also point 4 in the \"Requested Changes\" section.\n\nFurthermore, some claims and formulations made in this work are not justified from my viewpoint, see the \"Requested changes\" section.\n\n[1] On fine properties of mixtures with respect to concentration of measure and Sobolev type inequalities, Djalil Chafaı and Florent Malrieu, https://arxiv.org/abs/0805.0987", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The author shows a bound in the Wasserstein-1 distance between the distribution output by an DDM and the true data generating distribution. The bound is the applied to the empirical measure using the triangle inequality. A tigther bound is derived in the case that the hessian of the log-likelihood satisfies some more conditions.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "## Major\n1. The sentence directly after Theorem 1 seems misleading. It depends very much on the order in which one takes these limits. If one first takes $M \\to 0$ and $\\delta$ to 0, one is treating the exact case with no error and the statement is trivial. If one lets $\\epsilon \\to 0$ before any of these two, the bound exponentially diverges towards infinity and the statement is not true. Therefore one only sees that the Wasserstein distance actually converges to 0 in the exact case, which is known already, since then $\\mathcal{L}(Y_T) = \\pi$. \n2. In Section 3.2 generalization is treated. For that one applies the earlier Theorems to approximate the empirical distribution and then bounds the Wasserstein distance between the empirical distribution and $\\pi$ by applying other results. Using the triangle inequality one now gets a bound between the law output by a DDM started in the empirical distribution and $\\pi$. It is not really discussed in which way these results relate to generalization. First of all, due to employing the triangle inequality, the distance bound between $\\mathcal{L}(Y_K)$ and $\\pi$ will always be worse than the distance between the empirical measure in which the DDM is started and $\\pi$. Therefore, it can not be deduced from this if the output distribution of the DDM is closer to the empirical measure, the true data generating distribution or anything in between, even if the first terms in the RHS of the bound in Proposition 4 could be made rather small. To be clear, I think the Proposition is interesting, since the result than actually entails all the approximations made by an DDM into one bound, I just think it is not strongly related to generalization, or if it is indeed the case, the authors should provide some discussion on the connection.\n3. In the comparison sections, the authors state that this work goes one step further than [2]. It seems to be that the results are complementary, rather then building on each other, since they neither contain nor employ the results from [2]. The similarity rather seems to be the setting of studying DDMs under the manifold hypothesis.\n4. As stated in the \"Weaknesses\" section the most interesting results from this work is some intuition on how the different parameters influence the Wasserstein distance. Therefore, I would wish the work to focus on this a bit more and discuss these points in more detail. In particular, Assumption 3 seems to be the right kind of Assumption to me, since one gets linear dependence on $M$ in the error bounds. Nevertheless, the proofs rely on the drift not being evaluated on $[T - \\epsilon, T]$. If one wants to choose a small $\\epsilon$ and evaluate the drift approximation also on $[T - \\epsilon, T]$, one would need $M$ to be chosen of order $\\frac{1}{\\epsilon^2}\\exp(\\kappa/\\epsilon)$. Therefore, if I understand it right, if the Wasserstein distance is to be kept constant for different values of $\\epsilon$, the drift approximation quality would actually need to get exponentially better as one lets $\\epsilon \\to 0$ and also evaluates the drift on the final part of the interval. These are some important implications of the results and deserve more treatment from my point of view. \n5. Could it be discussed how realistic the Assumptions of Theorem 3 are or when they could be expected to hold/not hold?\n\n## Minor\n6. Maybe use a different letter than $\\kappa$ in (3), since $\\kappa$ will be used later for another quantity.\n7. \"Our result could be extended to W_p\". Maybe that could be justified a bit more, since especially the Wasserstein-1 distance has some different properties to the other Wasserstein distances.\n8.  In general I think it would help the clarity and readability of the results a lot if the results could be split up in a part that explicitly bounds the distance between the continuous SDE with the true drift and the continuous SDE with the approximate drift, and then another result for the discretization, but that might also be to much work.\n9. In the Proof of Lemma C.2, on the first line it says $p_t^N = \\hat{p}_t^N/(2\\pi\\sigma_t^2)^{d/2}$. This is the definition of $\\hat{p}_t^N$, right? Maybe this could be written as $\\hat{p}_t^N := p_t^N (2 \\pi\\sigma_t^2)^{d/2}$?\n\n\nOverall, I think this work is a great contribution to literature and should be published if the above points are addressed. Also as it is, I think a main interesting point is that Assumption 3 measures the error in a way, that at least for fixed $\\epsilon$, the Wasserstein distance depends linearly on $M$, which is a rather interesting result.\n\n[2] Score-Based Generative Models Detect Manifolds, Jakiw Pidstrigach, https://arxiv.org/abs/2206.01018", "broader_impact_concerns": "As a theoretical study of DDMs I do not think that this work needs a Broader Impact section.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QEXvxgPKzI", "reviewer": "Reviewer_Fneb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\nThe submission analyzes the approximation error under weaker assumptions that those currently assumed in the literature. Whereas the existing literature only apply to target distributions that are absolutely continuous with the d-dimensional Lebesgue measure (Equation 12), the submission's key result (Theorem 1) applies to such target distributions and also more kinds of targets, such as those supported on a lower-dimensional manifold.\n\nThe proof of Theorem 1 is sound. I can verify the correctness of the results in Section 4 (except for Proposition 5 as it is discussed in an external reference).\n\n# Weaknesses\n\nIt is unclear what is the space that realizations of the tangent process of Proposition 5 live in. Based on the initial condition $\\nabla Y_{s,s}^x = \\text{Id}$, it seems like each $\\nabla Y_{s,t}^x$ would be a $d \\times d$ matrix. \nBut based on the equality in Proposition 5, where it is written $\\nabla Y_{u,t}^x (Y_{s,u}^x)$, it seems like $\\nabla Y_{u,t}^x $ is a function that takes in $\\mathbb{R}^d$ vectors and outputs $\\mathbb{R}^d$ vectors.\n\nThere is a small mistake in the statement of Corollary 2. The actual relationship between $T$, $M$, $\\delta$ and $\\gamma_K$ on $\\eta$ is likely something like what’s been written, but can’t be exactly this. For instance, plugging $\\gamma_K = \\eta^2$ into the $D_0 \\epsilon^{1/2}$ part of Theorem 1 already evaluates to $D_0 \\eta$, but we haven’t even evaluated the contributions of the other parts of the bound. \n\nThe claim \"letting $\\epsilon \\to 0, T \\to \\infty, \\delta \\to 0, M \\to 0$, we get that $W_1 \\to 0$\" is not correct. There must be some relationship between the rates at which these quantities approach the limit for the final upper bound of $W_1$ to go to zero. I think Corollary 2 can be used to make the rates more explicit.\n\nThere are some small typos that should be addressed (please see Requested Changes section)", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In Theorem 1, the paper upper bounds the approximation error when a) the target is a compactly-supported probability measure and b) the approximation is a discretization of a continuous-time process coming from the diffusion modelling literature. The idealized continuous-time process (Equation 2) is a time-reversed Ornstein-Ulhenbeck (Equation 1). As Equation 2 depends on an analytically-unavailable family of functions, the first part of the approximation is replacing the family of functions with empirical estimates (replacing Equation 2 with Equation 4). The second part of the approximation is discretizing the continuous time process: the final approximation is Equation 5. The remaining theoretical results (Corollary 2, Theorem 3 and Proposition 4) are either implications of Theorem 1 or improvements of Theorem 1 under more assumptions. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please address my questions from the \"Strengths and Weaknesses\" section. In addition, there are small changes that I would like to see.\n\nThe following are typos that should be fixed\n- After Equation 8, currently it says $Q_{t}$ is associated with the distribution of $\\hat{Y}$ at $t$, but it should be associated with the distribution of $Y$ at $t$ instead.\n- Theorem 3 has a typo in Equation 9. Should be Hessian of log density. Not gradient of the square of log density.\n- Proposition 4 should say $\\epsilon^{1/2}$ rather than $\\epsilon$ to be consistent with Theorem 1\n\nI am confused about the meaning of these following sentences\n- What is the purpose of the sentence “setting $\\beta_0 \\leq \\beta_T$ allows for better control of the backward diffusion”? Sounds redundant given what’s in the previous sentence “$\\beta_t$ is a non-decreasing weight function”\n\n", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2C58ZBCfQJ", "reviewer": "Reviewer_RSJB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of the work is that it works under a realistic assumption on the data distribution. In particular, it is a welcome feature of the analysis that dissipativity and bounds on the score function are derived from the compact support assumption, rather than assumed (as is typical for these analyses).\n\nThere are also some weaknesses of the work:\n- The quantitative bounds depend exponentially on parameters such as the diameter of the support, which can be quite pessimistic.\n- Although the assumption on the score estimation error is weaker than assuming an $L^\\infty$ error bound, it is still unrealistic; it is preferable to work with an $L^2$ error guarantee, especially since the score matching objective is the $L^2$ error. Towards this end, the authors show in Appendix H that an $L^2$ error assumption suffices, but here there is an important distinction from the work of Lee et al. From my understanding, the crucial difficulty of Lee et al. is that they only assume an $L^2$ error bound with respect to the law of the true backwards process (BP), which is realistic as it is based on the score matching objective, whereas in this paper the $L^2$ error bound is with respect to the law of the algorithm (EI discretization of SBP). The latter assumption is far easier to handle as it simply contributes an extra term to the discretization error, whereas the assumption in Lee et al. is more subtle, requiring some delicate change of measure arguments.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors theoretically study denoising diffusion models, which have recently gained immense popularity for generating images. The main theoretical result is a quantitative convergence guarantee that ensures that if the various parameters are chosen correctly (e.g., the step size and score estimation error should be small), then the denoising diffusion model outputs an approximate sample from the data distribution in $W_1$ distance.\n\nDiffusion models have been studied before, but prior works assumed that the score function of the law of the forward process is Lipschitz, uniformly in time. The authors of the present work point out that such an assumption is typically violated in practice, especially if the data distribution is not absolutely continuous w.r.t. Lebesgue measure (e.g., the data distribution is supported on a lower dimensional submanifold, as predicted by the so-called manifold hypothesis). The main novelty of this work, therefore, is to perform the analysis assuming that the data distribution is supported on an arbitrary compact subset of Euclidean space, which necessitates an analysis in a Wasserstein distance (rather than total variation or KL).\n\nI have not checked the proofs in detail but to the best of my knowledge they appear to be correct. The techniques are more or less standard.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "As discussed above, I would like the authors to soften their claims about extending the results of Lee et al. under an $L^2$ error assumption, as I believe the results of this paper are substantially weaker in this regard. Also, please acknowledge the exponential dependencies as limitations of the work.\n\nI have also found minor typos:\n- Ornstein–Uhlenbeck is consistently misspelled throughout the paper.\n- Pg. 3, “on a lower dimensional manifolds”\n- Throughout the paper, in the condition $T \\ge \\bar \\beta\\\\, (1 + \\log(1 + \\text{diam}(\\mathcal M)))$, the closing parenthesis is missing.\n- Pg. 5, in the discussion of the first term, it should say $\\delta^{1/2}$, not $\\delta$. Also, “the second term correspond” should read “the second term corresponds”.\n- Eq. (9), the square should be on the $\\nabla$, not on $p_t$\n- Could the authors please check the definition of the Minkowski dimension in eq. (11)? It makes no sense to me. Why is there a $d - \\cdots$? And should $\\mathcal M_\\varepsilon$ be intersected with $\\mathcal M$ itself? (Does $d$ refer to the intrinsic distance on the manifold, or to the distance on $\\mathbb R^d$? Thus far it has not been assumed that $\\mathcal M$ is a manifold, only a compact set.)\n- Proof of Lemma D.2, there is an extra “$\\le$”.\n- In the display equation below eq. (68), the square should be on the norm, not on $\\nabla \\mathbf Y_{s,t}$. In the chain of display equations below this, there is a missing square on $\\sigma_{T-t}$.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three expert reviewers think that the paper has solid contributions, which I agree with. The author have addressed a few minor concerns, and several claims have been properly worded, which improved the quality of the paper even further. 

AE decision is "accept".

Decision: Accept (poster)