A Note on the Convergence of Denoising Diffusion Probabilistic Models
Authors: Sokhna Diarra Mbacke
Omar Rivasplata
Venue: Accepted by TMLR ()

Abstract: Diffusion models are one of the most important families of deep generative models. In this note, we derive a quantitative upper bound on the Wasserstein distance between the target distribution and the distribution learned by a diffusion model. Unlike previous works on this topic, our result does not make assumptions on the learned score function. Moreover, our result holds for arbitrary data-generating distributions on bounded instance spaces, even those without a density with respect to Lebesgue measure, and the upper bound does not suffer from exponential dependencies on the ambient space dimension. Our main result builds upon the recent work of Mbacke et al. (2023) and our proofs are elementary.

Published in Transactions on Machine Learning Research (06/2024)
A Note on the Convergence of Denoising Diffusion Proba- bilistic Models
Sokhna Diarra Mbacke
sokhna diaooadddara..cm mwwcke.aaa....... @ulavall.cc
Université Loval
Omar Rivasplata University College London
o.rivasplata@uullacccco uc.uk
Reviewed on OpenReview: https: // openreview. net/ met/ forum? id= www.b693ye
Abstract
Diffusion models are one of the most important families of deep generative models. In this note, derive quantitative upper bound on the Wasserstein distance between the target distribution and the distribution learned by diffusion model. Unlike previous works on this topic, our result does not make assumptions on the learned score function. Moreover, our result holds for arbitrary data-generating distributions on bounded instance spaces, even those without a density with respect to Lebesgue measure, and the upper bound does not suffer from exponential dependencies on the ambient space dimension. Our main result builds upon the recent work of Mbacke et al. (2023 and our proofs elementary.
1 Introduction
Along with generative adversarial networks (Goodfellow al. 2014) and variational autoencoders (VAEs)
[Kingma & Welling 2014 Rezende al., 2014), diffusion models (Sohl-Dickstein et al.)
2015 Song & Ermon
2019 Ho ct al.
2020 one of the most prominent familics of deep generative models. They have cxhibited
impressive empirical performance in image (Dhariwal & Nichol 2021 Ho et al. 2022 and audio (Chen et al.
2021
Popov et al. 2021) generation, as well as other applications (Zhou et al. 2021 Sasaki et al. 2021
ct al.
2022 Trabucco et al. 2023
There are two main approaches diffusion models: denoising diffusson probabilistic models (DDPMs) Sohl-
Dickstein et al.) 2015 Ho al.) 2020) and score-based generative models (Song & Ermon 2019 (SGMs).
The former kind, DDPMs, progrossively transform samples from the target distribution into noise through forward process, and train backward process that reverses the transformation and is used to generate
new samples. On the other hand, SGMs use score matching techniques (Hyvärinen & Dayan 2005 Vincent 2011h to learn an approximation of the score function of the data-generating distribution, then generate new samples using Langevin dynamics. Since for real-world distributions the score function might not exist, [Song & EEronn (2019) propose adding different. noise levels to the training samples cover the whole instance space, and train a neural network to simultancously Iearn the score function for all noise levels.
Although DDPMs and SGMs might appear to be different approaches at first, Ho et al. (2020) showed that DDPMs implicitly learn approximation of the score function and the sampling process resembles Langevin dynamics. Furthermore, [Song et al. (2021b) derived unifying view of both techniques using stochastic differential equations (SDEs). The SGM of Song & Ermon (0099) can be seen as a discretization of the Brownian motion process, and the DDPM of Ho et al. (2020) as a discretization of an Ornstein Uhhenbecck process. Hence, both DDPMs and SGMs are usually referred as SGMs in the literature. This explains why the previous works studying the theoretical properties of diffusion models utilize the based formulation, which requires assumptions the performance of the learned score function.

---

Published in Transactions on Machine Learning Research (06/2024)
In this work, take a different approach and apply techniques developed by Mbacke et al. (2023) for VAEs to DDPMs, which can be seen as hierarchical VA with fixed encoders (Luo 2022 This approach allows us to derive quantitative Wasserstein- based upper bounds, with no assumptions on the data distribution, no assumptions on the learned score function, and clementary proofs that do not require the SDE toolbox. Moreover, our bounds do not suller from any costly discretization step, such as the one in De Bortoli (2022) since we consider the forward and backward processes as being discrete-time from the outsot, instead of seeing them as discretizations of continuous-time processes.
1.1 Related Works
There has been growing body of work aiming to establish theoretical results the convergence of SGMs
Song et al.) 2021a Lee et al. 2022 De Bortoli 2022 Kwon et al,, Lee et al. 2023 Chen et al.] 2023 Li et al. 2023 Benton et al. 2023), but these works either rely on strong assumptions on the data-generating distribution, derive non quantitative upper bounds, or suffer from exponential dependencies on some of the parameters. We manage to avoid all three of these pitfalls. The bounds of Lee et al. (2022) rely on very strong assumptions on the data-generating distribution, such as log-Sobolev inequalities. which are not realistic for real-world data distributions. Furthermore, [Song et al.) (2021a); Chen al. (2023 Lee et al. (2023) establish upper bounds the Kullback-Leibler (KT. divergence or the total variation (TV) distance between the data-generating distribution and the distribution learned by the diffusion model; however, as noted by Pidstrigach| (2022) and Chen et al. (2023), unless one makes strong assumptions on the support of the data-generating distribution, KL and TV reach their maximum values. Such assumptions arguably do not hold for real-world data- matta-gnnrratig distributions which are widely believed to satisfy the manifold hypothesis (Narayanan & Mitter] 2010 Fellerman et al.) 2016 Pope et al. 2021
[Block et al. 2020 De Bortoli et al. 2022
2021
[nd[Chen
The work of Pidstrigach (2022) establishes conditions under which the support the input distribution is equal to the support of the learned distribution, and generalizes the bound of [Song ct al. (2021a) to all f-divergences. Assuming L2 accurate score estimation, Chen et al. (2023) and Lee et al. (2023) establish Wasserstein distance upper bounds under weaker assumptions on the data-generating distribution, but their Wasserstein- bounds are not quantitative. De Bortoli (2022) derives quantitative Wasserstein distance upper bounds under the manifold hypothesis, but their bounds suffer from exponential dependencies on some of the problem parameters.
1.2 Our contributions
In this work, we avoid strong assumptions on the data-genorating distribution, and establish a quantitative Wasserstein distance upper bound without exponential dependencies on problem parameters including ambi- ent space dimension. Moreover, common thread in the works cited above is that their bounds depend on the error of the score estimator. According to Chen et al. (2023), "Providing precise guarantees for estimation of the score function is difficult, as it requires an understanding of the non-convex training dynamics of neural network optimization that is currently out of reach." Hence, we derive upper bounds without assumptions on the learned score function. Instead, our bound depends on a reconstruction loss computed on a finito i.i.d. sample. Intuitively, we define a loss function (x(x,, Xo) (see equation 6 which measures the average Euclidean distance between a sample Xo from the data-generating distribution, and the reconstruction Xo obtained by sampling noise XT (xx) and passing it through the backward process (paramcterized by 0). This approach is motivated by the work of Mbacke et al. (2023) on VAEs.
There are many advantages to this approach: no restrictive assumptions on the data- tetta-generatngg distribution, no exponential dependencies on the dimension, and a quantitative upper bound based on the Wasserstein distance. Moreover, our approach has the benefit of utilizing very simple and elementary proofs.
2 Preliminaries
Throughout the paper, we use lower-case letters to denote both probability mcasures and their densitics w.r.t. the Lebesgue measure, and we add variables in parentheses improve readability (e.g. q(x{(x<1) to indicate time-dependent conditional distribution). We consider an instance space X' which is subset of TRD with
2

---

Published in Transactions on Machine Learning Research (06/2024)
q(x/Pta)
Sample
Noise
X
Xe1
Xy-1
Xr
Pe/o)Ks)
PaPt-1k)
Pe(ti.(/x))
Figure 1: Denoising diffusion model
the Euclidean distance underlying metric, and larget data-generating distribution j M (2). Notice that do not assume has density w.r.t. the Lebesgue measure. Moreover, |I-Il denotes the Euclidean (I2) norm and we write Bp(x) as shorthand for Bx~p(x)- Given probability measures q E (X) and a real number & > 1, the Wasserstein distance of order k is defined as Villani 2009):
W&(P. 2)
inf (=El((--))
/ ||x 1xx-
yll* dr(x,y)
where q) denotes the set of couplings of p and 9, meaning the set of joint distributions X x X with respective marginals p and We refer to the product measure p & as the trivial coupling, and we refer to the Wasserstein distance of order simply as the Wasserstein distance.
2.1 Denoising Diffusion Models
Instead of using the SDE arsenal, present diffusion models using the DDPM formulation with discrete- time processes. A diffusion model comprises two discrete-time stochastic processes: forward process and a backward process. Both processes are indexed by time S S T, where the number of time-steps T is a pre-set choice. See Figure for an illustration, and Luo 2022 for a detailed tutorial.
The forward process. The forward process transforms datapoint Xo P into noise distribution for 1
(xo), via sequence of conditional distributions process is defined that for large enough T, the distribution g(xr Xo) is close to a simple noise distribution p(xT) which is referred to as the prior distribution. For instance, Ho et al. (2020) chose p(xr) N (x²; 0, the standard multivariate normal distribution.
T. It is assumed that the forward
The backward process. The backward process a Markov process with parametric transition kernels. The goal of the backward process is to implement the reverse action of the forward process: transforming noise samples into (approximate) samples from the distribution μ.. Following Ho al. (2020), we assume the backward process to be defined by Gaussian distributions pa (x defined for 2 < stsT
p N (xx-1i (x),) of1)
(1)
and
(x(x)(x1)= = gpl (x1);
(2)
where the variance parameters ......, o7 E R>0 are defined by a fixed schedule, the mean functions g
BD + R are learned using a neural network (with parameters 0) for < t I T, and gb : R + X is a
separate function dependent on d1- In practice, Ho et al. (2020) used the same network for the functions gó for 2 T, and separate discrete decoder for 9ø-
Generating new samples from trained diffusion model is done by sampling x,-1 po(x;- (x.) for 15t5 starting from noise vector Xy p(xr) sampled from the prior p(xr).
We make the following assumption on the backward process.
Assumption 1. We assume for each < < T there exists a constant K3 > 0 such that for every x1, X2 E X.
| (x1) ( < K3 ||x - Xx|1-
In other words, of Ki-Lipschitz continuous. We discuss this assumption in Remark 3.2
3

---

Published in Transactions on Machine Learning Research (06/2024)
2.2 Additional Definitions
We define the distribution (=)-) as
no (- (x)
(x (x2)po( (1xx))
(3)
Intuitively, for each X, (=(-(2x)] denotes the distribution on X' obtained by reconstructing samples from ((xr (xo) through the backward process. Another way of secing this distribution is that for any function I : X + R, the following equation holds
E x
[(x0)
f(x)))
(4)
g(xr Xo) P (x))) (x())(
Given finite set S = xi ,e define the regenerated distribution the following mixture:
Hb
To (x))
(5)
This definition is analogous to the empirical regenerated distribution defined by Mbacke et al. 2023 for VAEs. The distribution on X' learned by the diffusion model denoted xx(-) and defined as
Tol (.)- ( 2(T po ( X2 (x)0xx2)p0((x1))
In other words, for any function : + R. the expectation of f w.r.t. me(.) is
f(xo) Ty (Ka)
E
E
E
((xo).
p(xT) (x(
pu (x)) pu (xal(x))
Hence, both TT(-) and (- (xo) are defined using the backward process, with the difference that no(+) starts with the prior p(xT) N (xy; I) while ne(-(xo) starts with the noise distribution q(xT) xo)-
Finally, define the loss function e X x + R
E e Xx) po Po(r (xrr) po (xT 2 XT 1)
E
E
E
||x0
Sull-
(6)
poo po x2) po (Ro x1)
Hence, given noise vector XT and a sample Xo, the loss e (xx, xo) denotes the average Euclidean distance between Xo and any sample obtained by passing Xy through the backward process.
2.3 Our Approach
The goal is to upper-bound the distance Wi (w, TT(-). Since the triangle inequality implies
Wi (M, (-) S (i (g) + Wi (4g mo))),
(7)
we can upper-bound the distance Wi(,, mo(-)) by upper-bounding the two expressions on the right-hand side of equation 7 separately. The upper bound on W, (jr, P.) is obtained using straightforward adaptation of a proof that was developed by Mbacke al. (2023). First, Wi 1()) upper-bounded using the expectation of the loss function (", then the resulting expression is upper-boure bounded using PAC- AAC-Bayesian-style expression dependent on the empirical risk and the prior-matching term.
The upper bound on the second term W1 (MJ, TT(-)) uses the definition of n0- Intuitively, the difference between T=(-)x))) and (-) is determined by the corresponding initial distributions: ((x](x)) for my (+1x)) and p(x7) for (-).). Hence, if the two initial distributions are close, and the stops of the backward process are smooth (sce Assumption D then x-(-(x() and (-(+) are close each other.
More formally, give definition ne(-)x)) expectations of test functions by requiring that equation holds for every function in some appropriate messure-determiinnng function class.
4

---

Published in Transactions on Machine Learning Research (06/2024)
3
Main Result
3.1 Theorem Statement
We now ready to state our main result: quantitative upper bound on the Wasserstein distance ween the data-generating distribution j and the learned distribution mo(-)-
||x- Theorem 3.1. Assume the instance space X has finite diameter A supx.''x - xx'l < oo, and let À > 0 and 8 E (0, 1) be real numbers. Using the definitions and assumptions of the previous section, the following inequality holds with probability at least 1 - over the random drow of {xp..... ....... x std μ
1 7
AA 8n
Wi(n, (-)))
1 (XT, x0)
KL(g(xT xx) (1x(xx)) + log
+
+
11
(xx)(xx))
(8)
1-1
II
K&
E XxT - -crll (ixTlx))err)
Il Kg
E
|c
- cll
c,e'
Where e N (O.I) are standard Gaussian vectors.
Remark 3.1. Before presenting the proof, let us discuss Theorem
3.1
Because the right-hand side of equation S depends on a quantity computed using finite i.i.d. sample S, the bound holds with high probability w.r.t. the randomness of S. This is the price we pay for having quantitative upper bound with no exponential dependencies on problem parameters and no assumptions on the data-generating distribution μ.
The first term of the right-hand side of equation g is the average reconstruction loss computed over the sample S (x).... (x):...,x6)) Note that for each 1 s i S n, the expectation of t (xr (x//x/) is only computed w.r.t. the noise distribution ((xT (x)) defined by x6 itself. Hence, this term measures how well a noise vector ~ (x5) recovers the original sample xh using the backward process, and averages over the set S = (x)....,.x x6
If the Lipschitz constants satisfy Kÿ < 1 for all 1 S S T, then the larger T is, the smaller the upper bound gets. This is because the product of Kj's then converges to O. In Remark 3.2 below, we show that the assumption that Kद- < 1 for all t a quite reasonable one.
The hyperparameter À controls the trade-off between the prior-matching (KI.) term and the diameter 8n If Кジ for all 1 < T and T oc, then the convergence of the bound largely depends on the choice of X. In that case, À x 1/2 leads to a faster convergence, while oc n leads to a slower convergence a smaller quantity. This bocause the bound of Mbacke et al. (2023) stems from PAC-Bayesian theory, where this trade-off common, see e.g. Alquier (2021).
term A2
The last term equation g does not depend on the sample size n. Hence, the upper bound given by Theorem 3.1 does not converge as - co. However, if the Lipschitz factors (K)) are all less than 1, then this term can be very small, specially in low dimensional spaces.
3.2 Proof of the main theorem
The following result is adaptation of result by Mbacke et al. 2023
Lemma 3.2. Let À > 0 and 8 E 10,1) real rumbers. With probability at least 8 over the randomness of the sample S {x] 1x.,...,>x
sid p. the following holds: xiI
1
2
Wi((,1) <
E e (x1, x6) g(x)l(as)
Σ KI(g(x)(xx)) ((((x) + log +
(9)
A
8n

---

Published in Transactions on Machine Learning Research (06/2024)
The proof of this result is straightforward adaptation of Mbacke et al. (2023 Lemma D.1). We provide the proof in the supplementary material (Section A.1 for completeness.
Now, let us focus our attention on the second term of the right-hand side of equation 7 namely Wi Wi(ng Ta(-))
This part trickier than for VAEs, for which the generative model's distribution is simply a pushforward measure. Here, we have a non-deterministic sampling process with T steps.
Assumption ! leads to the following lemma the backward process.
Lemma 3.3. For any given X1, Y1
X
we have
E po (50 X1) (yaly))
E
||0 -vol
Kg ||x, vill-
Moreover, 2 T, then for any given Xt. E X we have
E pa(x-- po ilxx)) ||x - Yc-1ll S K3 ||x; Yell + oz E.
||e 6'1l,
e.e'
where e, é' (0,1), meaning Be,e' is shorthand for Ex, ('
Proof. For the first part, let X1.y1 X. Since according to equation po(yuly)) = (x))).) (Yu), then
we have pa (x0)xx) = 62)(x.)(x0) and
E
E x1) (o(oo)
[xo - yoll = (96 - 36 (y1)) s K3 ||x| - -ylll
For the second part, let 2 2 LLST the reparameterization trick [Kingma & Welling 2014] implies that sampling
T and Xt,y, E X. Since pa px(xx-1 = NN (x 1ibb (xx), o21) by equation
Xt-1 po (x
is equivalent to setting
x,-1 (xx) occs, with (0,
(10)
Using equation T0
the triangle inequality, and Assumption
T we obtain
E
E
[|x,-1 - yt-1
E. Lo (x,) a:e - -
po(x--1 (x) po())
S E E [lob rb(rx))l + o EE 1l-ll-600 - +/l
(x.) :b(rr))l + EE ( &lll
K2 [x, -eel a. EE E e'1
where e' (0,1).
Next, we can use the inequalities of Lemma 3.3 Lemma 3.4. Let T 1. The following inequality holds:
to prove the following result.
E
E
E
E
E Po (Xo ) pa (o(os)))
| 2 5
Po(xr-1 (x) pa (yr-1 yr) po (x XT
po (yy--/l--y---
T
I
K2
||xT
yrll +
K
[|]e
- E'1]],
e.e'
where e ~
Proof Idea. Lemma 3.4 is proven by induction using Lemma in the induction step. The details are the supplementary material (Section A.2

---

Published in Transactions on Machine Learning Research (06/2024)
Using the two previous lemmas, obtain the following upper bound on Wi(ps, ne(-))
Lemma 3.5. The following inequality holds:
12
Wi(pb,a00)) -
II
Kg
E
E
xxT
yrll
Σ
Il
Kg of
E
1
((x))))) p(rr)
c,e'
where e, N (O.I).
Proof. Using the definition of Wi, the trivial coupling, the definitions of pg and TT(-), and Lemmna 3.4 we get
Wi (1 mo(+)) = inf =ET(uB,To(-)) / y(x,y) dx)
||x--Vll yll]
xm# yooooy))
E
E
E
E
E
||x0
yoll
(xxr (xj) plyr) po (xr- (oer) po polyr-llyrr)
po (x1) po (y))
1=1
a
[[ Kg
||XT - +
Σ
K2
ae
E
llle
e'll]
((xr (x)) p(YT)
e,e'
T
|XT ||x- ||x-- YT +
K
E
E
K
E
||
Ell
(xx) p(yr)
Combining Lemmas
3.2 and 3.5 with equation
7 yields Theorem 3.1
3.3 Special case using the forward process of Ho al. (2020)
Theorem 3.1 cstablishes general upper bound that holds for any forward process, long the backward process satisfies Assumption I In this section, specialize the statement of the theorem to the particular case of the forward process defined by Ho et al. (2020).
Let X' CRP. In Ho et al. 22020), the forward process is a Gauss-Markov process with transition densities defined as
((x:|x=-1) N (xx; Vaxx-11 (1 o))
where ,I,,.., aT is fixed noise schedule such that 0 a for all This definition implies that each time step 1 5 T,
(xx((x0)= N (xo: Varxa, (1 I)) with ā a
The optimization objective to train the backward process ensures that for each time step the distribution p=(x--(xx)) remains close to the ground-truth distribution (xx, given by
(xx-11Xx, xo) = -
xo), o??)
where
(x( xu) var(L -a-1)
Vāt-1(1 at) 1- ā X1 +
1- o. X0.
(1I)
Now, we discuss Assumption 1 under these definitions.

---

Published in Transactions on Machine Learning Research (06/2024)
Remark 3.2. We can get a glimpse at the range of K2 for trained DDPM by looking at the distribution (xx+-1[xx, xo), since (x(x--1(x;) is optimized to be as close possible to q(x+-1 Xo).
For a given Xo pa, let us take a look at the Lipschitz norm of x + p (x, xo). Using equation 11
we have
(x) 14(r1, vas(1 - σz-1)
(x; yy))
1- a4
Hence, x 1x,(x,x)) xo) is Ki-Lipschitz continuous with
K2 = var(L az-1)
- at
Now, if < 1 for all S S then we have ar ū:-1 which implies Ki < 1 for all 1 STST.
Remark 3.2 shows that the Lipschitz norm of the mean function (. does not depend on Xq. Indeed, looking at the previous equation, we can see that for any initial Xo, the Lipschitz norm Kj = (a,(1-ā--1) only depends on the noise schedule, not Xy itself. Since 9 is optimized to match to (, xn), for each X in the training set, and all the functions (t xo) have the same Lipschitz norm Ky we believe it is reasonable to assume 9 is Lipschitz continuous well. This is the intuition behind Assumption
1-û,
The prior-matching term. With the definitions of this section, the prior matching term KL(g(xI(x)) (x)) p(xx)) has the following closed form:
(L(((x)(x)) I(x))) = [ - - ār) - Dōr + or |xxo|?]
Upper-bounds on the average distance between Gaussian vectors. If c, are D-dimensional vectors sampled from N (0, I), then
E || 6 S V2D.
e,e'
Morcover, since q(xT|x)) N (xx; (1 (1- II and the prior p(yr) = N (yr:0,1)
||XT yrll S äT | 2 + (2 - ãT)
E (xn
E p(Yr)
Special case of the main theorem. With the definitions of this section, the incquality of Theorem 3.1 implies that with probability at least 1 over the randomness of {x]...., x,],,, pc:
li
Wi(p
E (x (x))
L
(XT,
+
D log(1 aT) Dar + oT |x0l|
+ log
1 I
n
2
T
T
K
|x| 1| + - DD-r)D + V2D
K3
o
8n
1=1
4 Conclusion
This note presents a novel upper bound on the Wasserstein distance between the aata-generating distribution and the distribution learned by diffusion model. Unlike previous works in the field, main result simultancously avoids strong assumptions the data-generating distribution, assumptions score function, and exponential dependencies, while still providing quantitative upper bound. However, our bound holds with high probability on the randomness of finite i.id. sample, on which loss function is computed. Since the loss is a chain of expectations w.r.t. Gaussian distributions, it can either be estimated with high precision or upper bounded using the properties Gaussian distributions.
the learned
8

---

Published in Transactions on Machine Learning Research (06/2024)
Acknowledgments
This research supported by the Canada CIFAR Al Chair Program, and the NSERC Discovery grant RGPIN-2020- 07223. The authors sincerely thank Pascal Germain for interesting discussions and suggestions. The first author thanks Mathieu Bazinet and Florence Clere for proof-reading the manuscript.
References
Pierre Alquier. User-friendly introduction to PAC-Bayes bounds. arXiv preprint arXi::2110.1121 2021.
Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization. arXiv preprint arXiv:2308. 036666, 2023.
Adam Block, Youssef Mrouch, and Alexander Rakhlin. Generative Modeling with Denoising Auto EitooEncoders and Langevin Sampling. arXi preprint arXi::2002.001 2020.
Nanxin Chen, Yu Zhang, Heiga Zen, Ron J Weiss, Mohammad Norouzi, and William Chan. WaveGrad: Estimating Gradients for Waveform Generation. In International Conference on Learning Representations, 2021.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In The Eleventh International Conference on Learning Representations, 2023.
Valentin De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. Transactions on Machine Learning Research, 2022. TSSN 2835-8856.
Valentin De Bortoli, James Thornton, Jeremy Heng, and Arnaud Doucet. Diffusion Schrödinger Bridge with Applications to Score- Based Generative Modeling. In Advances in Neurol Information Processing Systems, volume 34, pp. 17695-17709, 2021.
Prafulla Dhariwal and Alexander Nichol. Diffusion Models Beat GANs on Image Synthesis. In Advonces in Newral Information Processing Systems, volume 34, pp. 8780 8794, 2021.
Charles Fefferman, Sanjoy Mitter, and Hariharan Narayanan. Testing the Manifold Hypot Journal of the American Mathematical Society, 29(4):983 1049, 2016.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Farde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative Adversarial Networks. In Advances in Neural Information Processing Systems, volune 27, 2014.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising Diffusion Probabilistic Models. In Advances in Newral Information Processing Systems, volume 33, pp. 6840-6851, 2020.
Jonathan Ho, Chitwan Saharia, William Chan, David J Flect, Mohammad Norouzi, and Tim Salimans. Cascaded Diffusion Models for High Fidelity Image Generation. Journal of Machine Learning Research, 23(1):2249 2281, 2022.
Aapo Hyvärinen and Peter Dayan. Estimation of Non-Normalized Statistical Models by Score Matching. Journal of Machine Learning Research, 6(4), 2005.
Diederik P. Kingma and M. Welling. Auto-Encoding Variational Bayes. CoRR, abs/ 1131266114, 2014.
Dohyun Kwon, Ying Fan, and Kangwook Lec. Score-based Generative Modeling Secretly Minimizes the Wasserstein Distance. Advances in Neural Informalion. Processing Systems, 35:20205 20217, 2022.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. In Advances in Neural Information Processing Systems, volume 35, pp. 18770-28882, 2022.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. Tn International Conference Algorithmic Learning Theory, pp. 946 946-985. PMLR, 2023.

---

Published in Transactions on Machine Learning Research (06/2024)
Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Towards Faster Non-Asymptotic Convergence for Diffusion- Based Generative Models. aixiv preprint orXiv:23066 09251,, 2023.
Haoying Li, Yifan Yang, Meng Chang, Shiqi Chen, Huajun Feng, Zhihai Xu, Qi Li, and Yueting Chen. SRDiff: Single Image huper-Resolution with Diffusion Probabilistic Models. Neurocomputingg 479:47-59, 2022.
Calvin Luo. Understanding Diffusion Models: Unified Perspective. arXie preprint arXiv:2208.11999 2022.
Sokhna Diarra Mbacke, Florence Clerc, and Pascal Germain. Statistical Guarantees for Variational Autoen- coders using PAC-Bayesian Theory. In Advances in Neural Information Processing Systems, 2023.
Hariharan Narayanan and Sanjoy Mitter. Sample Complexity of Testing the Manifold Hypothesis. In Advances in Newral Information Processing Systems, volume 23, 2010.
Jakiw Pidstrigach. Score-Based Generative Models Detect Manifolds. In Advances in Neural Information Processing Systems, volune 35, pp. 35852 35865, 2022.
Phil Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The Intrinsic Dimension of Images and Its Impact on Learning. In International Conference on Learning Represenlations, 2021.
Vadim Popov, Ivan Vovk, Vladimir Gogoryan, Tasnima Sadekova, and Mikhail Kudinov. Grad-TTS: A Diffusion Probabilistic Model for Text-to-Speech In International Conference Machine Learning, pp. 8599-8608. PMLR, 2021.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic Backpropagation and Approxi- mate Inference in Deep Generative Models. In International Conference Machine Learning, pp. 1278- 1286. PMLR, 2014.
Hiroshi Sasaki, Chris G Willcocks, and Toby Breckon. UNIT-DDPM: UNpaired Image Translation with Denoising Diffusion Probabilistic Models. arXiv preprint arXiv:2104.05358, 2021.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep Unsupervised Learning using Nonequilibriun Thermodynamics. In International Conference on Machine Learning, pp. 2256-2265 PMLR, 2015.
Yang Song and Stefano Ermon. Generative Modeling by Estimating Gradients of the Data Distribution. In Advances in Newral Information Processing Systems, volume 32, 2019.
Yang Song, Conor Durkan, lain Murray, and Stefano Ermon. Maximum Likelihood Training of Score-Based Diffusion Models. In Advances in Newral Information Processing Systems, volume 34, 2021a.
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-Based Generative Modeling through Stochastic Differential Equations. Tn International Conference on Learning Representations, 2021b.
Brandon Trabucco, Kyle Doherty, Max Gurinas, and Ruslan Salakhutdinov. Effective Data Augmentation With Diffusion Models. arXiu preprint arXie:2302.079/4 2023.
Cédric Villani. Optimal Transport: Old and New, volume 338. Springer, 2009.
Pascal Vincent. A Connection Between Score Matching and Denoising Autoencoders. Newral Computation, 23(7):1661 1674, 2011.
Lingi Zhou, Yilun Du, and Jiajun Wu. 3D Shape Generation and Completion through Point- Voxel Diffusion. Proceedings of the IEEE/CVE International Conference on Computer Vision, pp. 5825, 2021.
10

---

Published in Transactions on Machine Learning Research (06/2024)
A
Omitted Proofs
A.1 Proof of Lemma 3.2
Recall Lemma 3.2 states that the following inequality holds with probability 1-
AA
Wi Wi(,, S
E e (xx)(x)))
(xr,
x
+
Σ (L(g(xT|x)) l1 ((
log
72
8n
Proof of Lemma 2.2 Using the trivial coupling (product marginals); the definition of μ (equation and the definition of the loss function 1 we get
5
inf / =ET(K(N)) xxx
Wi(u,
||x- - yll yx
||x 1 yll du(xx) duz
|x -xyl yll
x-up y-up
||x - y11 ]
E
E
X~p
a1x22 (x))) po(eer 1bx7))
po(xi(x2) (x)
1=1
Le (xT,x))
X
((xT(x))) (xf)
Using Mbacke et al. (0023 Lemma B.1), the following inequality holds with probability 1 8:
Wi (8) <
E (XT,
Σ <L(g(xr|<6) + +log 5
((xr(x)))
(12)
(e (xr E. 8 (xx.
n nog
E Sn (xxr)
Now, it remains to upper-bound the exponential moment of equation 9 If supx x- x'1l A co, and A 0 is a real number, then the definition of the loss function 8 and Hoeflding's ' lemma yield
ABx (e" x))=))]+ Ei. (xTxx))) s n log exp xXxxx
2
A
log E E
8n
8n
A.2 Proof of Lemma 3.4
Recall Lemma 3.4 states that the following incquality holds:
E
E
E
E
E Po (Xo (x)) po(yolyr)
||xo - -voll 5
px(x--1 xx) pa palyr-1lye yr) po (x 22/ polyr-aly=-1)
II Kg
||xT ||xT - yrll
K2
E e.e'
[||e E'l]]
Proof of Lemma 3.4
Let's do proof by induction T.
11

---

Published in Transactions on Machine Learning Research (06/2024)
Base case. T 1. The inequality becomes
E
E
-vol
S Kg | yill
(13)
Po Dea N1) (y(a))))
which holds by the first part of Lemma
3.3
Induction step. Assume >> 1. The induction hypothesis
E Po (x XT po (
E
E
IE
|xx
yoll
Po Xi po (Yoly)))
(14)
II Kg
1ll +
Kg
de
E E,
|||e
c'lll
Using the induction hypothesis, the linearity of the expectation, Lemma 3.3 with t: := T,
E polyT lyr)
E Po (xco po(orl))))
||xo - yoll
(x (xy)
E
E
K$
||XT-
-T--1--T-Il--
II
Kg
at
E
[l|e
é'Il]
Do Px (xx) Do ( (yr)
t=2
T-
II
K
E
||xT-1 yr-1lll+
II
K3
E e,e'
[lle
E'll)
po (xT--1Xx))) (yT
T-
K
K XT yrll + or
E ||e e'll +
K
de
E
[||e
e'lll
6,0"
c,e'
(=1
T
II (=1
K2
||xT -yrll+ +
K2
OT
+
K2
E
|l|e
-'lll
Kg
|XT
-rlll +
K
OT
K2
0x
E |||e
c'Il)
T
Kg
||XT
yrll+
K2
at
E e,e'
|||e
- E'1l
B Numerical Experiments
The goal of these experiments to assess the numerical value of the bound of Theorem 3.1 on a synthetic dataset. The gaataagenn distribution is chosen to be the uniform distribution on the square of side 2, centered at the origin. Figure shows samples from this target distribution.
The backward process model is trained on 50, 000 samples from the original distribution, and the bound is computed with = 5, 000 independent samples. Samples from the trained model are shown in Figure
shared network with fully connected layers, and 128 hidden units each. The
We computed the bound for different values of X. Given that the datapoints are confined to a square of side 2, using the primal form of the Wasserstein distance yields a straightforward upper bound of (H, To(-)) < /8 2.828. We estimated the Lipschitz norms K$ using K' from Remark 3.2 and the expected norms in the last two terms of Theorem 3.1 are estimated using 10 independent samples from each distribution.
À
n/10
n/5
n/2
π
n/0.5
n/0.1
Bound value
1.124
1.231
1.5181
2.035
3.056
11.061
12

---

Published in Transactions on Machine Learning Research (06/2024)
100
1.00
0.73
0.75
0.0
0.50
0.5
0.25
0.00
0.00
-0.25
-0.50
-0.75
-100
-1.00
-10
-05
0.0
05
10
-100
-05
0,0
05
1,0
Figure 2: The points represent 2000 samples from the target data-generating distribution.
Figure 3: The points represent 2000 samples from the trained diffusion model.
13


Reviews:
[{"review_id": "cxaUF8zzib", "reviewer": "Reviewer_PJMq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. the problem is fundamental and interesting to study per se\n\nWeakness:\n1. The usefulness of the theory is unclear\n2. Lack of numerical evidence\n3. The theory seems to be standard (?) in the field of the study of VAEs, is this the case?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a bound on the Wasserstein distance between the parameterized distribution and the true data distribution", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am sorry for submitting the review so late. While I think the work can improve on the above three points I mentioned. I have no serious objection to the paper.\n\nPerhaps the main thing to clarify and add to the work is to clarify why the theory is novel -- given that it seems standard to apply it to VAEs.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AGl9sFS7HS", "reviewer": "Reviewer_ckGf", "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 bounds provided on the Wasserstein distance between the data distribution and the learned distribution are \n- novel. \n- do not require any assumptions on the data distribution\n- do not require any assumptions on the score function of the data distribution\n\nWeaknesses: \n- The claims of the paper are ambiguous and misleading at times: \n——For eg., it is not clear “no exponential dependencies” is referring to. Exponential in what parameters? The paper also claims that the results are different from others by providing “quantitative” upper bounds. It is unclear what this is referring to. \n- The upper bounds will of course be exponential in the dimension. \n- The upper bounds are provided in a crude form. It is not clear from this expression when these bounds would be non-trivial. This greatly impacts the usefulness of this paper to the community. It’s not evident where these bounds fit in the context of other density estimation bounds in the literature. \n- In fact, it is not even clear if the bounds imply consistency let alone optimality of the estimator provided by the diffusion model. \n\nMinor Issues: \n- The definition of the distribution \\pi_\\theta(.) is not illustrative or illuminating. \n- Is there a reason we bound the upper bound with the distance from the regenerated empirical distribution? \n- Why is the assumption of the Lipschitz of the functions g_\\theta reasonable?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides upper bounds on the Wasserstein distance between the true distribution and the learned distribution of the diffusion denoising framework. These upper bounds do not require any assumptions on the data distribution or the score function.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Addressing the above concerns will go a long way in making this paper useful to the community. \n\nAddition of some illustrative examples where the proposed bounds imply consistency or optimality of the learned distribution would be very helpful. Moreover, contexts in which the provided bounds are applicable to real world data distribution would be useful. Do the bounds depend on the ambient dimension of the data distribution or the implicit dimension? I would guess the dependence on the dimension would still be exponential but for what other parameters of the problem is it not? Is this the defining difference of the results of this paper as compared to the related work?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tvr5jGDJJU", "reviewer": "Reviewer_3yzG", "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 theorem relaxes some assumptions present in previous theoretical results, including those on the score function and data-generating distribution.\n- Diffusion models are a highly relevant topic.\n\nWeaknesses:\n- As I understand it, the tightness of the bound is inversely related to the likelihood of the bound being true (as controlled by the $\\delta$ term). This is inherited from the underlying PAC-Bayes bound for bounded loss functions.\n- The present manuscript does not provide any numerical experimentation demonstrating the tightness of this bound.\n- To my understanding, there are limited empirical takeaways from this result, despite its nice theoretical properties. If I am missing something, I would appreciate that the authors clarify on this point.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors provide a bound on the approximation quality of the learned distribution in a diffusion model. The proof technique appears to follow closely to a prior work on the approximation quality of variational autoencoders [1].\n\n[1] Statistical Guarantees for Variational Autoencoders using PAC-Bayesian Theory. https://arxiv.org/abs/2310.04935", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am interested in a simple synthetic experiment (e.g. on a 1D Gaussian data-generating distribution) that demonstrates the tightness of the proposed bound (perhaps at different $\\delta$). Is the bound relatively tight? Or is it a loose bound?\n\nIf there are empirical observations that can help guide the design and training of diffusion models, can the author elaborate on them?", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VHVamYNOfF", "reviewer": "Reviewer_js5n", "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": "As far as I know, the obtained error bound of diffusion models is new in the literature. The terms in the error bound is relatively easy to understand, although some detailed discussion should be further provided.\n\nThe paper is also well organized, despite lacking more details on the preliminary of diffusion models. This might make unfamiliar readers struggle a bit.\n\nThe technical derivations are mostly correct and sound. However, there are some undefined notations (or typos) and one particular unjustified claim.\n\nI will discuss weaknesses and raise questions in the next section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper establishes a distribution estimation bound (stated in the Wasserstein distance) of diffusion models. Compared to existing sampling theory of diffusion models, the assumptions in the paper are mild and not imposed directly on the data distribution and the score functions. In this regard, the contribution of the paper is a new error bound of diffusion models, assuming the backward conditional mean is Lipschitz in its argument.\n\nIt is also to be noted that the error bound in the paper does not cover statistical estimation of the score function and the optimization guarantee of minimizing the score estimation loss. Therefore, the obtained result is not directly comparable to some recent advances in the statistical theory of diffusion models.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. $K_i$ in Theorem 3.1 Equation (5) seems undefined.\n\n2. A particular choice of $\\lambda \\propto n^2$ needs further discussion. Substituting $\\lambda \\propto n^2$ will make Equation (5) grow linearly with $n$.\n\n3. Following the second question, I would suggest providing explicit error rate implied by Theorem 3.1. Although an instantiation is provided just before Section 4, the convergence rate is still largely unclear. As the authors claim that the bound is obtained with weaker assumptions, how does the obtained bound compares to existing ones? I am also curious how the last error term $\\sqrt{2D} (\\sum (\\prod K_i) \\sigma_t)$ depends on $n$.\n\n4. There seems to be a mismatch between Assumption 3.1 and Remark 3.2. The justification in Remark 3.2 needs a conditioning on the initial data point $x_0$, while Assumption 3.1 is a marginalized version. How does the justification circumvent this issue? In fact, if we consider the score-based diffusion models, Assumption 3.1 is almost equivalent to requiring the score function being Lipschitz continuous, as $g_\\theta^t$ is determined by the score function (see Sampling is as easy as learning the score, by Chen et al., 2023).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewer js5n has raised multiple concerns and authors addresses most of those in their rebuttal. However, I ask authors to carefully go over the suggested items by this reviewer and make another attempt to address any remaining concerns; in particular, see the reviewers comment 3 and 4.
Decision: Accept (poster)