Adapting to Unknown Low-Dimensional Structures in Score-Based Diffusion Models
Authors: Gen Li
Yuling Yan
Venue: NeurIPS 2024 poster (2024)
Keywords: diffusion models
score-based generative models
low-dimensional structure
coefficient design
Primary area: learning_theory

Abstract: This paper investigates score-based diffusion models when the underlying target distribution is concentrated on or near low-dimensional manifolds within the higher-dimensional space in which they formally reside, a common characteristic of natural image distributions. Despite previous efforts to understand the data generation process of diffusion models, existing theoretical support remains highly suboptimal in the presence of low-dimensional structure, which we strengthen in this paper.  For the popular Denoising Diffusion Probabilistic Model (DDPM), we find that the dependency of the error incurred within each denoising step on the ambient dimension $d$ is in general unavoidable. We further identify a unique design of coefficients that yields a converges rate at the order of $O(k^{2}/\sqrt{T})$ (up to log factors), where $k$ is the intrinsic dimension of the target distribution and $T$ is the number of steps. This represents the first theoretical demonstration that the DDPM sampler can adapt to unknown low-dimensional structures in the target distribution, highlighting the critical importance of coefficient design. All of this is achieved by a novel set of analysis tools that characterize the algorithmic dynamics in a more deterministic manner.

Adapting to Unknown Low-Dimensional Structures in Score-Based Diffusion Models
Gen Li
Yuling Yan
The Chinese University of Hong Kong genli@cuhk, edu. hk
University of Wisconsin-Maddson yuling. mallingyynnwisce yanewisn..eee.ee edu
Abstract
This paper investigates score-based diffusion models when the underlying target distribution concentrated on or near low-dimensional manifolds within the higher-dimensional space in which they formally reside, a common characteristic of natural image distributions. Despite previous efforts to understand the data generation process of diffusion models, existing theoretical support remains highly suboptimal in the presence of low-dimensional structure, which we strengthen in this paper. For the popular Denoising Diffusion Probabilistic Model (DDPM), we find that the dependency of the error incurred within each denoising step on the ambient dimension d general unavoidable. We further identify a unique design coefficients that yields a converges rate the order of O / /VT) (up log factors). where l is the intrinsic dimension of the target distribution and T is the number of steps. This represents the first theoretical demonstration that the DDPM sampler can adapt to unknown fow-dimensional structures in the target distribution, highlighting the critical importance of coefficient design. All this is achieved by novel set of analysis tools that characterize the algorithmic dynamics in more deterministic manner.
Introduction
Score-based diffuusion models are a class of generative models that have gained prominence in the field of machine learning and artificial intelligence for their ability to generate high-quality new data instances from complex distributions, such as images, audio, and text [23, 11, 25, 24, 9]. These models operate by gradually transforming noise into samples from the target distribution through denoising process guided by pre-trained neural networks that approximate the score functions. In practice, score-based diffusion models have demonstrated remarkable performance in generating realistic and diverse content across various domains [19, 20, 21, 7], achieving state-of-the-arr performance in generative AI.
1.1 Diffusion models
The development of score-based diffusion models is deeply rooted in the theory of stochastic processes.
At a high level, we consider forward process:
Xo
add noise
X add noise add ngise
XT:
(1.1)
which draws a sample from the target data distribution (i.e.. Xo Pdata), then progressively diffuses it to Gaussian noise over time. The key aspect of the diffusion model is to construct reverse process:
denoise
denoise
denoise
Yr
Yr-1
Yo
(1.2)
"qqual contribution. Corresponding author: Yuling Yan (Email: yuling yan@wisc.edu)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

satisfying Y, & Xx for all é, which starts with pure Gaussian noise (i... Yr ~ (O La)) and
gradually converts it back new sample Yo sharing a similar distribution to Pdata-
The classical results on time-reversal of SDEs [1, 10] provide the theoretical foundation for the above task. Consider continuous time diffusion process:
- 3tt) + BB(t)dW, (0 Xo ~ Pdata
dx, =
(1.3)
for some function / :0,, T RR+ where (WissssT a standard Brownian motion. For wide
range of functions B3 this process converges exponentially fast to a Gaussian distribution. Let (.)
be the density of Xz. One can construct a reverse-time SDE:
1 ( - dÝ, = -
+ 2V Px. (Y:) + B(t)dZ, (0
Yo ~ Pxxr (1.4)
2
where (2i)oSesT is another standard Brownian motion. Define Y, = Yr- .. It is well-known that X, _ Y, for all 0 t S T. Here, Pxg is called the score function for the law of X,, which is not explicitly known.
The above result motivates the following paradigm: we can construct the forward process (1.1) by dinediiscetiizig the diffusion process (1.3), and construct the reverse process (1.2) by discretizing the eeverse-tmee SDE (1.4) and learning the score functions from the data. This approach leads to the popular DDPM sampler [1 I. 16]. Although the idea of the DDPM sampler is rooted in the theory of SDEs, the algorithm and analysis presented in this paper do not require any prior knowledge of SDEs.
This paper examines the accuracy of the DDPM sampler by establishing the proximity between the output distribution of the reverse process and the target data distribution. Since these two distributions are identical in the continuous time limit with perfect score estimation, the performance of the DDPM sampler is influenced by two sources of error: discretization error (due to finite number of steps) and score estimation error (due to imperfect estimation of the scores). This paper views the score estimation step black box (often addressed by training large neural network) and focuses understanding how time discretization and imperfect score estimation affect the accuracy of the DDPM sampler.
1.2
Inadequacy of existing results
The past few years have witnessed a significant interest in studying the convergence guarantees for the DDPM sampler [4, 6, 3, 14, 13]. To facilitate discussion, we consider an ideal setting with perfect score estimation. In this context, existing results can interpreted as follows: to achieve e-accuracy (i.e., the total variation distance between the target and the output distribution is smaller than e), it suffices to take a number of steps exceeding the order of poly(d) (ignoring logarithm factors), where d is the problem dimension. Among these results, the state-of-the-art is given by [3], which achieved linear dependency on the dimension d.
However, there seems to be a significant gap between the practical performance of the DDPM sampler and the existing theory. For example, for two widely used image datasets, CIFAR- 10 (dimension d = 32 x 32> x 3) and ImageNet (dimension d 2 64 x 64 x 3), it is known that 50 and 250 steps (also known as NFE, the number of function evaluations) are sufficient to generate good samples [16, 9]. This is in stark contrast with the existing theoretical guarantees discussed above, which suggest that the number of steps T should exceed the order of the dimension to achieve good performance.
Empirical evidence suggests that the distributions of natural images are concentrated on or near low-dimensional manifolds within the dimees-dimeniional space in which they formally reside [22, 18]. In view of this, reasonable conjecture is that the convergence rate of the DDPM sampler actually depends on the intrinsic dimension rather than the ambient dimension. However, the theoretical understanding of diffusion models when the support of the target data distribution has oin-dimesiional structure remains vastly under-explored. As some recent attempts, [8] established the first convergence guarantee under the Wasserstein-1 metric. However, their error bound has linear dependence on the ambient dimension and exponential dependence on the diameter of the low-dimensional manifold. Another line of works [5, 26, 17] focused mainly on score estimation with properly chosen neural networks that exploit the low-dimensional structure, which is also different from our main focus.

---

1.3 Our contributions
In light of the large theory-practin gap and the insufficiency of prior results, this paper takes step towards understanding the performance of the DDPM sampler when the target data distribution has low-dimensional structure. Our main contributions can summarized as follows:
We show that, with a particular coefficient design, the error of the DDPM sampler, evaluated by the total variation distance between the laws of X1 and Y1, is upper bounded by
2
T E E[ (X.) - sf (x.)
Σ
up to some logarithmic factors, where & is the intrinsic dimension of the target data distribution (which will be rigorously defined later), and s7 (resp. 82) is the true (resp. learned) score function at each step. The first term represents the discretization error (which vanishes as the number of steps T goes to infinity), while the second term should be interpreted the score matching error. This bound is nearly dimension-free - the ambient dimension d only appears in logarithmic terms.
We also show that our choice of the coefficients is, in some sense, the unique schedule that does not incur discretization error proportional to the ambient dimension d each step. This sharp contrast with the general setting without a low-dimensional structure, where fairly wide range of coefficient designs can lead to convergence rates with polynomial dependence on d. Additionally, this confirms the observation that the performance of the DDPM sampler can be improved through carefully designing coefficients [2, 16].
As far as we know, this paper provides the first theory demonstrating the capability of the DDPM sampler in adapting to unknown low-dimensional structures.
2 Problem set-up
In this section, we introduce some preliminaries and key ingredients for the diffusion model and the DDPM sampler.
Forward process.
We consider the forward process (1.1) of the form
X, = / 3xX,11+ + V.W.W 11.1,...,, T). Xo ~ Pdata:
(2.1)
where Wi,..., W1 Lid (N Ia), and the learning rates Br E (0, 1) will be specified later. For each t > 1, X2 has probability density function (PDF) supported on Rdd and will use qe to denote the law or PDF of X,. Let a; == 1 - Be and = I1 0g It is straightforward to check that
X, X. + VI ae We where
W. (O
(2.2)
We will choose the learning rates 3r to ensure that ā becomes vanishingly small, such that @r RJ NO 12).
Score functions. The key ingredients for constructing the reverse process with the DDPM sampler the score functions of Rd d associated with each qt. defined
st (x) V log (x) (t I.....T), T).
These score functions are not explicitly known. Here we assume access to an estimate s+(-) for each st (+), and we define the averaged Eg score estimation error as
T
Σ
1
Ex - -
-
score
This quantity captures the effect of imperfect score estimation in theory.

---

The DDPM sampler.
To construct the reverse process (1.2), we use the DDPM sampler
1
Y--1 = (Ye + 1788 (Yi) + +.2e) (t= Yr ~ (O,,
(2.3)
Vau
where ZI...., ZT Lid. (0, Ld). Here Tt, oz
the hyperparameters that play an important role in the performance of the DDPM sampler, especially when the target data distribution has low-dimensional structure. As we will see, our theory suggests the following choice
oi (4) (az ai)
T at and
(2.4)
1 - az
For each 1 S.ST, we will use Pt to denote the law or PDF of Y.
Target data distribution. Let X' C Rd be the support set of the target data distribution Pdata i.c., the smallest closed C C Rd such that paata (C)
To allow for the greatest generality, use the notion of e-net and covering number (see e.g., [27]) to characterize the intrinsic dimension of X. For any 0, set Ng X' is said be 8-net of X' if for any X, there exists some x' in NV such that || - x' r'll2 S E. The covering number N₂ (X) is defined as the smallest possible cardinality of s-net X.
(Low-dimensionality = where c > 0 is some sufficiently large universal constant. We define the intrinsic dimension of to be some quantity such that
log (X) S Ccover log
for some constant Ccover >
(Bounded support) Suppose that there exists a universal constant eR > 0 such that
sup
| S
R
where
ToR
#eX
Namely we allow polynomial growth of the diameter of X' in the number of steps T.
Our setting allows be concentrated on near low-dimensional manifolds, which is less stringent than assuming an exact low-dimensional structure. In fact, our definition of the intrinsic dimension the metric entropy of X' (see e.g., [28]), which widely used statistics and learning theory to characterize the complexity of a set or class. The low-dimensionality is also concept of complexity, therefore is natural use covering number, or metric entropy characterize the intrinsic dimension. As sanity check, when A' resides in an r-dimensional subspace of Rd a standard volume argument (see e-g.. (27, Section 4.2.1)) gives log N₂ = log( (R/e) x r log T, suggesting that the intrinsic dimension k is of order in this case. In addition, in applications like image generation, the data is naturally bounded, as pixel values are typically normalized within the range [-1, 1]. For example, the & norm of image from the CIFAR dataset is typically below 60.
Learning rate schedule. Following [14], we adopt the following learning rate schedule
C log T
min $1 1+ C1 log T
1
31 To
B+11
(t 1...... --1) 1) (2.5)
T
T
for some sufficiently large constants > 0. This schedule is not unique any other schedule of 3, satisfying the properties in Lemma can lead to the same result in this paper.
Main results
We are now positioned to present our main theoretical guarantees for the DDPM sampler.
3.1 Convergence analysis
We first present the convergence theory for the DDPM sampler. The proof can be found in Section 4.

---

Theorem 1. Suppose that we take the coefficients for the DDPM sampler (2.3) to be = 77 and ot of (cf. (2.4)), then there exists some universal constant >> 0 Oucch that
(q1,1))) S C C log d)² log T
+ C. log T.
(3.1)
VT
Several implications of Theorem 1 follow immediately. The two terms in (3.1) correspond to discretization error and score matching error, respectively. Assuming perfect score estimation (i.e.. Escore 0) for the moment, our error bound (3.1) suggests an iteration complexity of order k*/E² (ignoring logarithmic factors) for achieving E-aceuracy, for any nontrivial target accuracy level é < 1. In the absence of low-dimensional structure (i.e., k x d), our result also recovers the iteration complexity in [4, 6, 3, 14] of order poly(d) (d)/ This suggests that our choice of coefficients (2.4) allows the DDPM sampler to adapt to any potential (unknown) low-dimensional structure in the target data distribution, and remains valid criterion in the most general settings. The score matching error in (3.1) scales proportionally with Sccore suggesting that the DDPM sampler is stable to imperfect score estimation.
3.2 Uniqueness of coefficient design
In this section, we examine the importance of the coefficient design in the adaptivity of the DDPM sampler to intrinsic low-dimensional structure. Our goal is to show that, unless the coefficients fee de of the DDPM sampler (2.3) are chosen according to (2.4), discretization errors proportional to the ambient dimension d will emerge in each denoising step.
In this paper, as well as most previous DDPM literature, the analysis on the error TV(q). usually starts with the following decomposition
( S 2 (g)
(i)
KL (px, llx))
KL (px Xr |pr.....rs
(3.2)
T
1
KL (px, )
E Ening JKL (px-. (-12e) I| (-1 (-1x)))]
2
initialization error
emvor incurred the (T++ ()) denoising step
Here step (i) follows from Pinsker's inequality, step (ii) utilizes from the pata-processing inequality, while step (iii) uses the chain rule of KL divergence. We may interpret each term in the above decomposition as the error incurred each denoising step. fact, this decomposition is also closely related to the variational bound on the negative log-likelihood of the reverse process, which is the optimization target for training DDPM [11, 2, 16).
We consider target distribution Pdata = (N Lu), where I3 E Rdxd is a diagonal matrix with I,, = 1 for S < k and I,; = for & + 1 < S d. This is a simple distribution over Rd that is supported on a k-dimensional subspace." Our second theoretical result provides a lower bound for the error incurred in each denoising step for this target distribution. The proof can be found in Appendix B.
Theorem 2. Consider the target distribution Pdata = NO, Jx) and assume that k S d/2. For the DDPM sampler (2.3) with perfect score estimation (iee., se(-) s.)) for all t) and arbitrary coefficients ne, oz > 0, we have
Eaygngg [KL (px.-1Ix, (.122) Pl Y, (. (.1 2 d (n n1)²²
d o
2
-1
40 of
for each ST T. See for the definitions of ni and oj
*Our result exhibits quartic dimension dependency, which is worse than the linear dependency in [3]. This is mainly because we use completely different analysis. It is not clear whether their analysis, which utilizes the SDE and stochastic localization toolbox, can tackle the problem with low dew-emissional structure.
Althoouhh this is not a bounded distribution, similar results can be established if we truncate (0, 4x) at the radius Ht = R However this is not essential and will make the result unnecessarily complicated, hence is omitted for clarity.
5

---

Theorem 2 shows that, unless we choose and of to be identical (or exceedingly close) to n) and o²² the corresponding denoising step will incur an undesired error that linear in the ambient dimension d. This highlights the critical importance of coefficient design for the DDPM sampler, especially when the target distribution exhibits a low-dimensional structure.
Finally, we would like to make note that the above argument only demonstrates the impact of coefficient design on an upper bound (3.2) of the error TV(g1, Pi), rather than the error itself. might be possible that a broader range of coefficients can lead to dimensioon-indeeendenn error bound This calls for new analysis
like (3.1), 1), while the upper bound (3.2) remains cemension-depenaee tools (since we cannot use the loose upper bound (3.1) in the analysis), which we leave for future works.
4 Analysis for the DDPM sampler (Proof of Theorem 1)
This section is devoted to establishing Theorem 1. The idea is to bound the error incurred in each denoising step as characterized in the decomposition (3.2), namely for each 2 < s T, we need to bound
Bez,nge KLL (px (.1=4) Py... (+1=))]]
This requires connecting the two conditional distributions PX.- JX, and Py, PY.- It would be conve- nient to decouple the errors from time discretization and imperfect score estimation by introducing auxiliary random variables
Yi
(Y, + +mst (X) + (X))
(2
(4.1)
Vot
On a high level, for each 2 S T, our proof consists the following steps:
1. Identify typical set A, S Rd Rd such that (Xe, Xx-1 A, with high probability.
2. Establish point-wise proximity Px,- (#t-1 (x) ~ Pyt,, (xx-1 (x)) for (r=, 1) E A..
3. Characterize the deviation of py;,,x, |Y, from PY,,.Y, caused by imperfect score estimation.
4.1 Step 1: identifying nigh-probability sets
For simplicity of presentation, we assume without loss of generality that 1: 2 log d throughout the proof.* Let {at be an s-net of X, and let (S.). be a disjoint e-cover for X' such that at E B, Let
= (1 P(X. B,) 2 exp(-CiklogTT); ||ll2 - 2vd v Co and
g = (w e Rd
1a =x)) S VCkklog7[lat - a31l2 for all
where C₁ > 0 is some sufficiently large universal constants. Then UiezB; and G can be interpreted high probability sets for the variable Xu and standard Gaussian random variable in Rd. For each t t= I....., T, we define a typical set for each X₁ as follows
T = { Varzo + vI - di zo E U. E Eg}.
and typical set for (Xe, X₁ 1) jointly as follows
A = (11)) Ie E To, Ft Varti-1 c9}
-1-ai
The following lemma shows that Ar is indeed a high-protf ceab-probbbility set for (Xr, Xt-)).
Lemma 1. Suppose that C1 > Ccover- Then for each 1 I t S T we have
IP ((X,,, $ Av) S exp (
C1 k log T)
4
Proof. See Appendix A.3.
'If' & < log d, we may redefine k = log d, which does change the desired bound (3.1).

---

4.2
Step 2: connecting conditional densities px, x|x, and PYZ,IM
Given the definition of y in (4.1), we can write down the conditional density PY,-,/y, follows
d/2
(-
[Ivaist- - m/. o6 (xx) l1
Py; LI (24-1 (4)
OTT
Oxt
exp
20,²
(4.2)
Next, we will investigate the conditional density Px,-1|X, for the forward process. For each zo E X. we define the shorthand notation
[oo X, = xdl = / ZoPx,IX, (xo xx) dro.
To = E
(4.3)
and define function A Z,, X - IR as follows
Va+
(1 0r))
A - (2o) == at 02
(0424-1--24) (To 50) 2 (at 044) 041
130
roll 20l1
04) Voi
(0t - (T) (1 - T (xg v varta) (og mo)
(4.4)
The next lemma provides a characterization for P that shows an explicit connection with PY:
Lemma 2. For any pair ((-) E R x Rd,
we have
4/2
II It
58 (2t) l1
Px.-i|X, (Fc-1
at
exp
20
fxx exp (Denden (xo) pxo|Xx x. (zo xx) dro-
Proof. See Appendix A.4.
Taking Lemma 2 and (4.2) collectively yields
Px.-1 (xt-1 2x4) = / exp (Azi.e- (zo)) Pxolx, (zo xx)) dæo. PYL,YY (#t-1 xx)
which allows us to control the density ratio by the magnitude of Ar, By a careful analysis the above integral for all (Ir, Tt-1) E Ar, we show in the next lemma that the density ratio is uniformly close to 1 within the typical set A.-
Lemma 3. Suppose that T >> k2 log T. Then there exists some universal constant Cs >> 0 0such that, for any 2 S T and any (Te, E Av. we have
Px Px. (xt-1 (2)
2 log 3
T
< C3
<
Pyz 1% (Iz-1 Iz)
T
2
Proof. See Appendix A.5.
For (Iz, 11 outside the typical set A,, the following lemma gives coarse uniform bound for the density ratio, which is already sufficient for our later analysis.
Lemma 4. Suppose that T >> 1. Then for any 2 < < T and any pair (x,, xt-1) Idd x IRd, have
log P (IL-1 | xx))
< 22oR (llvarr,-1 xella + ||,, 12 1).
pry , (xz-1 xx))
Proof. See Appendix A.6.
Armed with Lemmas and 4, we are ready to bound the expected KI. divergence between the two conditional distributions PX. and PYp,Y.-
7

---

4.3 Step 3: bounding the KL divergence between Px, 1|x; and PV
We first decompose the expected KI. divergence between 1|X, and PYt,11 into
|KL (px--iXx, (-1ar)) Ipy: ,iM (-12+))
Exraag
- - + (.z AE
Pxi-ilXi (xt-1 (24)) Pyr_,ly, (It-1 xze pxi (Ir) 1
-
Px.-ilX, (Ie-1 xz) log
111 + 1122
where Dt,1 and 4,, are the integrals over A and Aç. It boils down to bounding these two terms.
By a direct application of Lemma together with the first-order Taylor expansion of log(z) around I = 1, one can easily show that [Ar,]] S 122 (T),TT) However this naive bound will lead to vacuous final bound on TV( Pı). which depends the of A over all 2 S t T according to (3.2). By a more careful analysis, we achieve a better bound for At.1, as shown in the following lemma.
Lemma 5. Suppose that T >> 2²2 log" T. Then for each 2 S t S T, we have
| s 20g k² log
T
Proof. See Appendix A.7.
For A,, we can employ the course bound in Lemma 4 to show that it is exponentially small.
Lemma 6. Suppose that T >> Then for each S t S T, we have
C1 k log T
A S exp
16
Proof. See Appendix A.8.
By putting together Lemma 5 and Lemma 6, we achieve
oagkt log
Exinge KL (px, 11x, (1))) || Ilpy.,, (-1z0)] A.,1 + A. s 30g
(4.5)
T
provided that T sufficiently large.
4.4 Step 4: bounding the KL divergence between Px,-1 and PY.1
Since our goal to bound the expected KL. divergence between Px.- and PY. Yo we also need upper bound the following difference
Exernge
KL (L (.) Il (: (-1xx))] - Exynn
[LL (L (. Plyy, (. (.12)))
/
[ px (fe-1 [x)) log
Py, 11,, (2i-- (i))
dr a: (2x) dæ
(4.6)
PY. DY, (fi--1 (t))
(- [ 12-1 - 14, (xx) 113
ad aella1-1-1 - Ho (2t)
PX (IC-1,
dı, d
20
20
n1? 20 Exinge [lle: (2x) [2]
n you +
PX (II-1, (x--1 14 (xx)) T (x.) dz
o²2
=KK.
where we define
El (xx) = o (xx) - de (ar), 1i (xx)) = 2t nt (Ir)
Me (x.) Et + m7, (It)
(4.7)
Voi
Vou
It then boils down to bounding Kr. which is presented in the following lemma.

---

Lemma 7. Suppose that T >> k2log' T. Then we have
k² log" T
C1 log
K2 S 4Cg
1//2 [[Is= (Iz) [b]
T
T
Proof. See Appendix A.8.
Hence we know that for 2 2TTT
Exenge [KL (px,-1Ix, (.124) Pr.- (- xx)) - -Exeag [KL (-1zz)
pyz 12 (-1 (124))
(1 a.) (1 ar)
1 - 22 log" T
'c log T
B Berrge [[]=s (Ix)
+ 40'
B1/2
[]|e (xx) l1
2 2 - a+)
0tt - at
T
4c1 log T
k2 log" T
c1 log T
Excage [l|e: (zz)
[2] + 8Cs
E1
[lle (xx) 12
(4.8)
T
T
T
Here the first relation follows from Lemma and (2.4); while the second relation follows from Lemma 8 and holds provided that T is sufficiently large.
4.5 Step 5: putting everything together
By taking (4.5) and (4.8) collectively, have
Exener [KL (px,-.XX) .|x,
(.124) Pr. (-1axa)]
4 log" T
4c1 logT
k² log T
c1 log
s 3Cg
Emingq [|l=: (arz) [12] + 8C's
E 1//2
[[l=:
(2x) [1]]
7
T
T
T
- 7C2 1 log" " T
801 log
I||s: (Ix) [121
(4.9)
T2
T
Here the last relation follows from an application of the AM-GM inequality
2 log
c1 log T
4c1 logT
h log T
8Css
E2/2
[llec (2t) [1 S
Ex,,g.
[llE (zt) [12] + +40g
T
T
T
T
Finally we conclude that
T
TV² I KL (px, (lxx,) ) +
Σ Exing
[KL (px, 11x, (: (x))) Il a (- [-1=))]]
k log
ST
Se1 log T
T
< 8C8
Σ
Exing. [lle, (xx) 112)
T
T
1=2
as claimed. Here the first relation follows from (3.2), while the second relation follows from the fact that KL(px, (Ipy,) 7-000 provided that T is sufficiently large (see Lemma 10).
Simulation study
We conducted a simple simulation to compare our coefficient design (2.4) with another design
= = = ar for 1 S
(5.1)
which has been widely adopted in theoretical analysis of diffusion model (see e.g., [14, 15]). We consider the degenerated Gaussian distribution Pdata (O, Iạ) in Theorem a tractable ex- ample, and run the DDPM sampler with exact score functions (so that the error only comes from discretization). We fix the intrinsic dimension & 8, and let the ambient dimension grow from 10 to 103. We implement the experiment for four different number of steps T E (100, 200, 500, 1000}. Instead of using the learning rate schedule (2.5), which is chosen mainly to facilitate analysis, we use the schedule in [11] that is commonly used in practice. Figure displays the error, in terms of both the TV distance (V(g) PP)) and KL divergence KL [pi), ), as the ambient dimension d varies. As we can see, our design (2.4) leads to dimension-independeee error while the other design (5.1) incures an error that grows increases. This provides empirical evidence that (2.4) represents unique coefficient design for DDPM in achieving dimension-independenn error.

---

T=100 100
T0000
T 500
T- 1000
10
10
104
K1/ (p))
XI1 (p))
Kl/n (m))
10
www.eeeeeennoo.. Toinks
10
10
10
10"
10
ambient
ambient dimorsonn
dimonsion
ambiem dimonsion
200
120
100
102
105
TV P1)
TVin P1)
PV mL)
TVLp Pr)
10
10
10
10
10
10
10'
10
ambient dimer
ambient dimerslond
embient dimension
ambien dimension
The KL divergence between and P1 for T E (100, 200, 500, 1000), when Pdata (O, Ix). We fix the low intrinsic dimension k = 8, and let the ambient dimension d grow from 10 to 1000.
Figure 1:
6 Discussion
The present paper investigates the DDPM sampler when the target distribution is concentrated on or near low-dimensional manifolds. We identify a particular coefficient design that enables the adaptivity of the DDPM sampler to unknown low-dimensional structures and establish a dimension- free convergence rate at the order of k² /VTT (up to logarithmic factors). We conclude this paper by pointing out several directions worthy of future investigation. To begin with, our theory yields an iteration complexity that scales quartically in the intrinsic dimension k. which is likely sub-optimal. Improving this dependency calls for more refined analysis tools. Recent work [15] achieved a convergence rate of order Od/TT), suggesting the potential for enhancing the dependence T. Furthermore, as we have discussed in the end of Section 3.2, it is not clear whether our coefficient design (2.4) is unique in terms of achieving dimension-independee analysis ideas and tools developed for the DDPM sampler might be extended to study another popular DDIM sampler.
error TV((), PI). Finally, the
Acknowledgments and Disclosure of Funding
Gen is supported in part by the Chinese University of Hong Kong Direct Grant for Research. Yuling Yan was supported in part by a Norbert Wiener Postdoctoral Fellowship from MIT.
References
[1] Brian DO Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):313-326 1982.
[2] Fan Bao, Chongxuan Li, Jun Zhu, and Bo Zhang. Analytic-DPM, an analytic estimate of the optimal reverse variance in diffusion probabilistic models. In International Conference Learning Representations, 2022.
[3] Joe Benton, Valentin De Bortoli, Arnadd Doucet, and George Deligiannidis. Linear convergence bounds for diffusion models via stochastic localization. arXiv preprint arXiv:2308.0300 03666088..06..... 2023.
[4] Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. International Conference Machine Learning, pages 4735-4763. PMLR, 2023.
10

---

[5] Minshuo Chen, Kaixuan Huang, Tuo Zhao, and Mengdi Wang. Score approximation, estimation and distribution recovery of diffusion models on cow-dimensional data. In International Conference Machine Learning, pages 1872-4712 PMLR, 2023.
[6] 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.
[7] Florinel-Alin Croitoru, Vlad Hondru, Radu Tudor lonescu, and Mubarak Shah. Diffusion models in vision: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2023.
[8] Valentin De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. arXiv preprint arXiv:2208. 05 2022.
(9] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat GANs on image synthesis. Advances in Neural Information Processing Systems, 34:8780-8794 2021.
[10] Uirich G Haussmann and Etienne Pardoux. Time reversal of diffusions. The Annals of Probability, pages 1188-1205, 1986.
[11] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6851, 2020.
[12] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of statistics, pages 1302-1338, 2000.
[13] Gen Li and Changxiao Cai. Provable acceleration for diffusion models under minimal assump- tions, arXiv preprint arXiv:2410.23285, 2024.
[14] Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Towards non-asympiotic convergence for diffusion-based generative models. In The Twelfth International Conference on Learning Representations, 2024.
[15] Gen Li and Yuling Yan. O(d/T) convergence theory for diffusion probabilistic models under minimal assumptions. arXiv preprint
2024.
[16] Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In International Conference on Machine Learning, pages 8162-8171, 2021.
[17] Kazusato Oko, Shunta Akiyama, and Taiji Suzuki. Diffusion models are minimax optimal distribution estimators. arXiv preprint 20X3v:2303.01861, 2023.
[18] Phillip Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact learning. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[19] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text-conditional image generation with CLIP latents. arXiv preprint arXiv:2204.06125, 2022.
[20] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High- resolution image synthesis with latent diffusion models. In JEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10684-10695, 2022.
[21] Chitwan Saharia, William Chan, Saurabh Saxena. Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Bureu Karagol Ayan, Tim Salimans, et al. Photorealistic text-to-image diffusion models with deep language understanding. Advances in Neural Information Processing Systems, 35:36479-36499 2022.
[22] Fero Simoncelli and Bruno A Olshausen. Natural image statistics and neural representation. Annual review of neuroscience, 2431):1193-1216 2001.

---

[23] Jascha Sohl-Dickstein Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamiis. International Conference on Machine Learning, pages 2256-2265, 2015.
[24] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances neural information processing systems, 32, 2019.
[25] Yang Song, Jascha Dich-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. International Conference on Learning Representations, 2021.
[26] Rong Tang and Yun Yang. Adaptivity of diffusion models to manifold structures, In International Conference on Artificial Intelligence and Statistics, pages 1648-1656. PMLR, 2024.
[27] Roman Vershynin. High-dimensional probability: An introduction with applications data science, volume 47. Cambridge university press, 2018.
[28] Martin J Wainwright. fiigh-dimensonda statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
12

---

A Proof of auxiliary lemmas for the DDPM sampler
A.1 Preliminaries
Fix any Ze E Te, there exists an index i(xx)) E I, two points zo (2+) Bi(z.) and g such that
vorao(Iz) + v1 ayw.
(A.1)
For any >> 0, define set
I ( {1 siis Ne: aello; - 2 sr. k(1 04) log T
(A.2)
For some sufficiently large constant C3 >> define
(xs) (ET((rA:Ca)
B. and
(x))
B igI(Ze:Cs)
U
Namely, (xx)) (resp. (xx)) contains the indices of the e-covering that are close (resp. far) from Bi(n.). We require that
k log T
min
(A.3)
a2
which is guaranteed by our assumption that E = T for some sufficiently large constant > 0.
Under this condition, for any x. x' (x4) we have
Csk(1 - T.) To) log +22 s 3//
(ill-a))ee
Czk(1 - - logT
||0 x'1l2 S | F la ||
T1 lla s /
Hence for any x' E (xx) we have
Te||æ - 2'113 s 9Cpk (1 Tte) log
(A.4)
In addition, for any v, x' E X, suppose that x E B, and x' E By. For any w E G, we have
|w (x z')| w T (z; x3)| + w (x .;} + |ا (a) - x')l
Cik log || - xj1la + || x lla ||ll|2 + l| - x3l12 1Wll2
w. 1Vg
Cgklog x - xj122 + 2 (2v v (gkklogT)
Cog
x x' + 2
+ 2 (2v Vikllog T
/iCiklogT 2'112 (AV 4 log
(A.5)
Here step (i) follows from w and the Cauchy-Schwarz inequality; steps (ii) and (iii) follows from ar x l12 and || - 22112 < E, well |||||2 S vd + Vokk which is property
for w E G.
A.2 Understanding the conditional density px. (-1 xo)
Conditional on X, Zz, for any 1 5 S N: we have
P PXx E B, X, = xn)) = P(x E B,, X, = xx)
P(N E B,, X. = 12)
Px. (xt)
EiSISN. P (No E By.Xt X1 = =1)
P P(o E X,=xx
P E B,
P (X, =xx Xo E B.)
PXo E Bila,).Xi = =x²) P(Xo E Bi(z.))
P P(X;= -x== Xo E Bs(z.))
P P(X, = Fz |No E B.)
< eexp (oiklogT).
.P(o E &B.).
(A.6)
P pXX, =xt No E Bi(x)))
13

---

Here the last relation follows from P(Xo E Bi(a.)) 2 exp(- 1 due to i(x;) E I. We have
(X, Tt, Xo E B.)
PP (X, It Xo E.)
P(x: Iz, Xo a) dē
(Xo E Bi)
PP PXx Bi) JEEB;
PX, = xt Xoo = i) = ž) dž
P (Xo B,) JEEB
S max P P(X: = Ft aEB:
Xo -))
(A.7)
For any 2c E B,, since X, Xg = I ~ NN Tait (1 - - we have
Ix V
P(,, = xe Xo = ă) = 12 (1 - [,) 1/2
-d/2 exp
2 2(1 Tre)
(1122 - vānz, 12 vote)
< [2m (1 - ()) d/2 exp
(A.8)
2(1 (3,)
Taking (A.7) and (A.8) collectively to achieve
[(1 vTn 12 vT(E))
P P(, xe Xo B3) S [2 (1 oz)) exp
(A.9)
2 a+)
By similar argument in (A.7), (A.8) and (A.9), we can show that
(11 VTs ((2,) ll2 + vore)) (A.10)
P (X, = zt Xo E B((r)) 2 [T (1 - a.]]
-//2 exp
4/2
2(1 - -aa)
Combine (A.9) and (0.10) to achieve
P (X, Xo E B,)
(A.11)
P (X, = It Xo E B((
(||23- - Va va,e)
(1|=a - ((. 12 + 2
< exp
211 (1--a aaa)
2 2(1 (Tt)
|| va ||
varz (2x)) 11 - --2/ane((12,,
va || - 12)
< exp
2(1 (vt)
Next, we will discuss the implication of the above analysis for any & I(rs; C3), i.e. B, S ))())))
For any i & I(æ;; C3). we have
||2,
2 - 1| V Vanzizn 12 au ==
2v 0 (2)(p)) - x;;) (Iz - vaLz((z))
ael ((()))
22112- 2/ (1 - (1-a)) (Z) - x;)) w 20 /I (1( x2) (ao r((Zo)
111 2/ CT (1 TTe ) / k log T (( - x - 2T, v1 - J. ( - 2flle
(m
1l.
(A.12)
Here step (i) uses the decomposition (A.1); step (ii) follows from w E G. Cauchy- Schhar- inequality
and the fact that [|<o(x=)) 2 ( Il2 I E; while the correctness of step (iii) is equivalent
Volloa - x ||2 2 4/CG Ci (1 - a.)
4/a, (1 - -.,)e
which follows from & I(I;; C2), the assumptions that C3 > C₁, and (A.3). In addition, we also have
|1 - VT,zille + 1| - Vii
@
Vailzz0020 zilla + v0ll)20(11)) 2ienlll + 221 a. w
S
V
( - =Tll2 + 22 2
2f(r)l12 l12 + 2 I Tee (2vd + (Cg
14

---

(all - 211l2 3vI a VCiklogT).
(A.13)
Here step (i) follows from the decomposition (A.1); step (ii) utilizes the triangle inequality; whereas step (iii) follows from (20 Ei(z,)ll S and the condition (A.3). We can substitute the bounds (A.12) and (A.13) into (A.11) to get
P(X; = 24 Xo E Bi))
I exp
1 ((x)))
x
(A.14)
((,, Xo E B((r)))
(88(1 a+)
provided that (A.3) holds and C3 is sufficiently large. Since i & I(x;; C3). know that on (12) x 12 > C3k(1 oi) log 7, hence when C3 > C₁, we learn from (A.6) and (A.14) that
PXx E B; X, = xz) v exp
Cik log T
a².
||0
x;11 (Xo E B.)
(1 a+)
S exp
| 2;113/ (Xo E Bi).
(A.15)
16 (1
A.3
Proof of Lemma
It is straightforward to check that
P((X,,X,-I) E A,) P E E 9) - P (Xo E Uiez W, E W,W, 9),
where step (i) follows from the update rule (2.1), and step (ii) follows from the relation (2.2).
Therefore have
P (((,,, (1-1) $ A.) (X, & U.ezB:) PW, +)) PP 9)
(A.16)
By definition of the set I, we have
P (Xu U,) N: exp (- T) I cxp (Ccover log T loklog
1
C1 4
exp
kog
(A.17)
3
as long as C1 >> Coover- addition, since Wt, W. NO0 Ia), by the definition of g we know that
N₂ N2
P(W E 9) P (IWella > vd+ CikllogT)
(1(x) - x3) Wil > lo T| x3]12
(N² + 1) exp [-Ikllog]]
(-C C
< (exp (2C log T) + 1) exp
(-2
k log T
Ci log
exp
(A.18)
Here step (i) follows from concentration bounds for Gaussian and chi-square variables (see Lemma 9); while step (ti) holds as long as C1 > Crover- The same bound also holds for P(W, & 9). Taking (A. (A.17) and (A.18) collectively yields
IP (X,,,),-1) Ao) S exp (-
C1 [-
as claimed.
A.4 Proof of Lemma
For any deterministic pairs (1r, 11-), have
1
Px. (x1-1)
PX--1XX, (Fe-1 / px. (xx) PXe- (xT-1,
Px (xx 1
px. (x+)
(A.19)
15

---

Recall that X₂ Xe-1 = =1-1 ~((vai2--11111 (a))(a),
therefore we have
Px (Et (t--1) = 12 (1 - az)] a+)l d/2 exp
2(1 -o4) || var
(A.20)
Next, we analyze the density ratio px. (2 px. (zt). It would be easier to do change of variable
Px,-1 (8t-1) = at 4/2 Pvoix.-- (Vart--)).
(A.21)
Since X Xo = I0 ~ N a,o0, (at - -at) we can write
PeaxXe-1 (Vare1-1)
px, (24) J. Pxo (fo) P. Paaxx.-11 (Varse-1 x0) dzo
px, (Iie)
1
Px. (zo) [2tT (at- - [t)]
6/2 exp
Ilvantee v Va 11
dro. (A.22)
Px. (Ix)
2(ax= a+)
mo
We hope to connect the above quantity with the conditional density
Pxolx, (zo xz) PXo.X, (x), Pxa (2r)
Px. (xt) Px,|Xo (2ts xo)
Px. (xt)
Px. (xo)
2t - v va
[2t(1 01)11/22 cxp
(A.23)
Px. (zt)
2 2(1 a,,
Towards this, we can deduce that
PvatXe (Vares-1)
(A.24)
Px.
(z+)
@
ae
d/2
Pxo (rO)
[2x(1 - -//3 exp
IIvonte Voraol dro
02 T
Px. (xt)
2(a; (z.)
mg
(
1 at
d/2
Pxolx, (Dol xz) exp
| - v /
|1 1a v varvll dæo.
0g
2 2 -1-06 Te))
2(a: T
where step (i) follows from (A.22) and step (ii) utilizes (A.23). The terms in the exponent can be rearranged into
|| v 12
Voy01-1- /
2 (1 [e)
2 (ax (T.)
Ir - v / 112 /11001111 - vo,00l2
(1 - (1-aa)lle 112; - va
2( at)
2 (at ai)) (1 ((4)
|a - Zz (Varst-1 - x1) T (x: - varzo)
(1 - (ts) || v T
2(0z -aa)
2 (a4 az.) (1 0t.)
|Va - xz + (OrIT-11 -
T (Iz varão)
- ax) ||,,, / V 12
+ A am (zO)
2 (a: - -aa)
2 (ax σ.) (1 σx)
where we define
3o = E X, xr) = ToPx,|X, (2o xx) dro,
and
Vā
A A (50) =
(Vonte
xzx) (%o- -(0)
04 ai
(1-ar) a1) V 02
(1 - 04) a
(xi - ( (2o =2)
130 x rol2
(as ) (1 T.,)
2 (a: T.,) (1 [1
Substituting the above relation into (A.24) yields
Poaoxi-- (va(()-1)
1 1- प.
d/2
Waaai=11 x2.12
exp
px. (Iz)
O22
Te
2 (ax Tt.)
16

---

(Vorsh-1- -x1) (I+ vorin)
(1- (1))) |2, - va
exp
at
2 (ar - [x,) (1 -āte
PxolX, (2o (xpeepppp (A (200) dro-
(A.25)
20
Therefore we have
4/2Pva (va(es-1)
Px (I1-1
at
PX. (21) Px (xelxee))
(A.26)
(
d/2
11- - 0'
4/2
(Va - 21) (st - vango)
(1 - az) | - Va.
at
exp
01 0ie
04 - Üz
(at - (i.) (1 - (it)
-1- az) || Vonst-
/ Pxolx, (ro xx)) exp (Dee (xo) dæo
1 (1 - ar))
d/2
exp
2 21 as) (at= σt)
(
04
4/2
2t n 87 (3ra)
[ Px,lx, (ro (2) exp (A (Ho)) dro-
(2
2/2
exp
20²²
Here step (i) follows from (A.19) and (A.21); step (ii) follows from (A.20) and (A.25); whereas step (iii) follows from the definition of vi and of (cf. (2.4)) as well as the fact that
1
1t (x))
The PxolX, (No 1z) (x varso drg
(xt - vario)
T
A.5 Proof of Lemma
For any (t-,);-1) E As, we know that w' = (Ix the integral with two terms
E G. We will upper bound
Pxo|X, (Du (2)) exp (A (I,, 1t-1, 2.)), dxo
PxolXe (0a xx) exp (A (I2,, 2t-1, za)) dxy
+
Pxolx, (Do 21) exp (A (Ir, x1-1, dro.
(((())
=12
where we recall that
A (Ii,, Ft- 11-1, =
02. (1 (t.)
(To no) T w/
(1- 02) va
(To - vo) w
Ti
(ar v1 T
=:)(()))
(1 ar) Te.
(1 - 0₂) Ti
(xo(Z1) - Ro) (To - Io)
1 - roll 112
(at - a.) (1 )
2 (a. 2. a.))
(Fa)))
In what follows, will use A(zo) instead of A(x,, 20) when there is confusion. Since (Ii, It-1) E Ar, we know that w' = (xs- vai are E G. We decompose To into
To = I dopxooxx (a' æ1) da'
(A.27)
Thea + Iac (ab T PXxoxx (2b xx) da'ó + Ixcc (4b (((x)))Xooxx, (26 xx) da
Since (x(rr) is a ball in Idd centered xt it is straightforward to check that To Xe(xz). We also have
||ā||2 5 /
1|=6 - (la.x)laPPxo.x. (wo 21) da
(m.))
17

---

IA3
(12z f,z,)ll + + P P(Xo Bx xz)
(ll;) - sitz)ll2 + +)) exp (-16 (1 ote)
( w113 P P(xo B.).
Here step (i) holds since for any i I(xx; C2) and x/ B;.
| واmرمم I | z((ee) ll2 |26 z lll S || ziaa)llz t
while step (ii) follows from (A.15). For any i & I( C3), we know that T. (.)l)((())) 2;113 Cyk(1 - Tx) log T, hence we can check that
(104 #f(eo)) ll2 + 5) exp
Ce
(1
at l12
16 at)
((V Caki(1 Cak(1-aa) log
log
Cak T
C3k log T
$
t
exp
exp
T
16
32
as long as C3 is sufficiently large and the condition (A.3) holds. Therefore
Vi=
Czkloge T
||01|2 S
E
exp
IP (Xo E B,)
a2
32
(EI(2eCs)
Cgk T
exp
(A.28)
at
32
A.5.1 Step 1: deriving an upper bound for (
Suppose that zo E B, for some 1 sis Ng (notice that here we are not requiring that E I). We will bound each of (ro) for i = 1, 4. We first record two basic facts about the step sizes, which are immediate consequences of Lemma 8:
0e
04
a2
a2
at ai
8c1 log '''
8c1 log T T
S V
1+
0₂ 0x.
ai
0,
02
0t at
-
T
C1 log T
<3/
(A.29)
T
ae
as long as T' is sufficiently large, and
(1 - 02) 0
8c, log T
02
(A.30)
(a-- - oz)) v1 0t
1- a2
We learn from (A.5) that
max
( mo) w| (oo 20) ww'l Vak x + (4V
T)
(A.31)
We also have
|| [. - rolla S [ - -zoll + ||ó1|2 S |لح()ب) x; [|2 + || - -ollz + E + 1|01|2
(1)
Cak(11 - (x,) log
1 a2
Cgk
|2)( - 21112 +//
+
exp
a
32
(1)
Czh(1 - Tee) logT
1 (1(( - 2t1la 1l2 + AV
(A.32)
T
Here step (i) holds since xo E B,, hence ||000 - x lll S E; step (ii) follows from (A.4) and the fact that "iz.)): To E (xx);; while step (iii) follows from (A.3) and holds provided that C33 is sufficiently large. Then we have
Vou (1 - 04)
[A(x))) <
(To xo)" Io)Tw [w
(A.33a)
at 02
18

---

C1 log
T
31
(VCklogTT zoll2 (4vd+ 4v
A CiklogT)s
T
(h)
41
C1 log
T
at
(VCkklogTTaaia - - + 4yCC
a2e
T
T
Here step (a) follows from (A.29) and (A.31); while step (b) utilizes (A.32), (A.3). Similarly can use (A.30) to show that
A2(20)) &
9c1 IogT
T
0+
(VCkklogT(aaa))) - 2; + 4v CoC
a2
T
az.
ar (A.33b)
Notice that
(#n(2x)) - -Ro) (To- =ooo
x | - Toll2 1: xoll2 S (11=0(00s) - -xoll2 + (1112) 130 - -ooll
@/
Cak(1 ai) log T
at
exp
Czk log T
|100 zoll2
at
32
(i))
Cak(l - @ie log T
100
xo xoll2-
where step (i) utilizes the Cauchy-Schwarz, inequality; step (ii) follows from (A.4), (A.28) and the fact that vo(2;), xo E (x+);; step (iii) holds provided that C3 sufficiently large. Therefore we have
(1 - 0z) 0z
[As(zo)] -
(xT((T)) - 3o) T
(To z0)l
(A.33c)
(a: 0() (1 σi.)
(1 - ar) αt
Cak(1 ar)
-V
1 - xoll2
(a: [x) (1 -axe
T
$ 32c2 Css log T
V
at
log
xtl12 +4
Cahi( - oz) log T
T
1-
Tee
where the last relation follows from Lemma and (A.32). Finally we have
(1 - a,)
(x0o) 5
| 2
2 (a, a1) (1 (+))
8c1 log T Tt.
Cak(1 Tre) log T
(
x; 112 + 16
(A.33d)
T 1 0zt
at
Here step (a) follows from (A.32), step (b) follows from (A.4) and the fact that x T((m))) x3 Xe [ the bounds in (A.33) collectively leads to
A (2o)) S 5
5
T
K
LogT
(V1
Oit σz
|1(te 2tll2 + 4 Czklog
801 log
T
|
2..1..
(A.34)
T
1 a
provided that T' sufficiently large.
A.5.2 Step 2: bounding /1
For 2o E (xx),, we know that xo E B, for some i E I(xr; C2), hence R.||o;
Cyk(1 σx) log T. This combined with (A.34) gives
122 log T
8c1 Czk log 2T T
22
log T
A (xo) & 25
26VaCCiss
(A.35)
T
T
T
19

---

provided that T > k² logg T. Similarly we can check that for each 1 S i < 4. [A,())) S 1.
Then we know that for 20 E (z,), we have exp(A(zo)) S 1 1+ A(xo) + +I)( as long as
T > 12t log T. Hence
[
S (xi(er) PxolX, (ro xi)) A (mo) drp
1 S 1
PxolX, (wo [x4) A (wa) dao +
(a(as)
1+ / Pxolx, (2ol xx) A1 (zo) dxo / (i((s))
Pxolx, (zo 224) A (ro) dzo
+ / Pxolx, (zo 2x) A (zo) + Ao (xo) + +1 (2o) + A (2o) dro
xx()))
< +++
Di((r)) PXolX, (ro (T) | (3r) day
=h1
+
PxolXe (xo (xe) [|42 (zo) Da (2o) + Aa (xo) + A (ro) dao-
Ai(2))
Here the last step follows from the fact that J Pxx/ x, (ro A1) 0. The integral I1,1 can be upper bounded similar Iz, hence we defer its analysis the next section. For the integral 1,2. we have
112 S
max (21e)
(10) + Da (mo) A (xo) + A (xa)
{44] (5r) + 5 A (2o)) 5 5 (TT) 5 5 (mo)1}
max (2.)
(i)
128
Ci log T
at
Cik
Czk a.) log T
+ 16C log
1 az The
T
1 1- a
T
45c log T
a²
VaiklogT
4 CiCgh T
ae
T
Te
The
+ 160c1 V CCs
log T
V
T
V
Cski log
+ +41
Czk(1
Tx,)
log T
T
T
40c, log T T a
C3k (1 0F log T
Czk(1 - σz log
+ 16
1-
at
T2.
h2 logg" T T
2181c; CiC3
(A.36)
Here step (i) follows from the Cauchy-Schwarz inequality and the facts that [xa)] I for
i = 2,3,4 4, while step (ii) follows from the bounds (A.33) and the fact that oz a1|1 x (x 11 S
Cyk(11 - Te) Tog
A.5.3 Step 3: bounding /z-
For xe E ((()), we know that vo E B, for some i & I(x;; hence R.||o;
xi(e))
Cyk(1 σn) log T. This combined with (A.34) gives
C.C
log T
log T
8c, log T
α22
A (xe) <
5
T +
20
| - x
C3
C3
T
T
1 a
< 25
C1Cr
log T T
1 - Ti. | - x
a
(A.37)
C2
as long as T is sufficiently large. Therefore we have
1a /
Pxolx, (zo 2x,) exp (A (zo)) dæg
(A.38)
(...)
20

---

(Xo Bi X; 21) max exp (A (zo)) mn
Gci
log
exp
25
|
2:11 P (Xo E B.)
16
C3
T
- --a
exp
1
| - x 1 P (Xo E B.)
(i)) S exp (
C3 log T) 32
32
(1
Here step (i) follows from (A.15) and (A.37); step (ii) holds as long as T is sufficiently large; while step (iii) uses the fact that क |||=;; F((a,) 11 > C3k(1 σ.) log T for & I( C3). By similar analysis, we can show that
/ (a(on)) Pxolx, (oo x4) | (zo) dxo S
11
Σ (CI(x)(Ca)
P |x = xx) max
| (ro)
moEB;
2
C1 log
a2
E
P(x E B xz) (1 - x ll2
T
Cr
201
log T
at
exp
Üt
|,(((.)) - 22113 P P(xo E BB) (1 - x2112
T
1 at
16 - σ4
C(I(#
c T2kklogT
201
exp
T2
|0(((e)) 27113 P P(x E B.)
T
32 (1
a1)
(gT(a(Caa
c1ih T
C3 k log T
20
exp
(A.39)
T
32
Here step (a) follows from (A.33a) and the fact that xe|a= (2,),) 1 Cak(1 -z) log T for
i I(r; Ca); step (b) follows from (A.15); step (c) holds provided that C3 sufficiently large; step
(d) follows again from the fact that Or, || x a l12 > Czk(1 o4) log T for i & I( Cz).
A.5.4 Step 4: putting everything together
Taking (A.36), (A.38) and (A.39) collectively, we have
/ .tc
PXolX, (ro (i)) exp (A (Iie, (t,, dar 11 + $1+ 11, + I2
122 log T
1 2182c1
provided that T is sufficiently large. By similar argument, i.e., using the lower bounding exp(A(xo)) =1+A(2) (xr) in Step 2 and repeat the same analysis, we can show that
k2 log T
Px,|x, (zol 2x)) exp (A (zo)) drg 2 11-2182aCCCs
T
This gives the desired result.
A.6
Proof of Lemma
Recall that
log Px. Ix, (fz-1 1zt) log / pxolx, (2o | x2) exp (A (x,, 10)
PY YY, (xt-1 21)
For any 2o E X, by the definition of 21,, Do) in (4.4), we have
A 1o-1,
21

---

S vol
(1 ar) var
- 1
- xol22 +
I vartoll2|| - zol12
04 04
(az - a2) (1 - aa)
(1 (1.) Ote
+ aa - a4) (1 - x+e)
1 -ooll
S 2R val_ || Vattt11 - 1:112- + 21 (1- (1--a)= vār | + (ar (2t) (1 (is)
(1-04) a14) at
4R2
04 Cit
(at - ( (1 (it)
( < 4 Vartt11 xz + 16e R7 log T || 2 + 32c 12 log T.
Here step (i) follows from Tn, To E X, hence max [ 2, || | & Rt while step (ii) follows from the facts that, for 2 < S T,
Vat 1
II:=1 04 = a (1 (1)
S
- 2T
āt 0t
1 a1
and in view of Lemma
(1 (1-04) The
(1 a4) v
8e1 log T
$
S
I _ -1 log T.
(a: - kt) (1 (x)
(a: σt) (1 Ti))
T
1 - a
Hence we have
log PX--1lXe ( (x4))
PVz.lVe (IC-1 xz)
= log // PXolX, (2o xt) exp (A (z,, It- xt,) dro
S sup
|A (It; 1z-1, zo)l
< 4 4RT (Vaatt11--aa - + 16 RT log T|| |1
32c, R2 log T
S T (IIaaxz-11- xelle + | 1)
as long as T is sufficiently large.
A.7 Proof of Lemma 5
Regarding Ar, we first utilize Lemma 3 to show that for any (Iz, x1-1) E As,
Py;, DY, (#t-1 2x)
k2t log" "o T
I Cs
Px. IX, (ra-1 .rt))
T
Since log(1 - x) 2 x x² holds for any [-1/2, 1/2]. we know that when T > log T, have
Px. X, (xa-1 (xe)
Px.-11Xe (xe-1 xx) log
PYz Vr (xt-1 xx)
Px,-1|X, (Ic-1 xe) ]
PY, DY. (z (x4)
-- (#1-1 2 log
PYz,lY (xt--1 xx))
(1 (1-
PYz,lY, lY, (xt-1 xt))
27
PX. (xe-1 (2:))
Px,-1/X, (Iz-1 xit)
Px. (fo-1 Ixt)
= =Px--ixx, (01-1 - Prz,ly (zt-1 x1) + 1xx, (xx-1 xe) CP k²t log T
T
Hence we have
- 1y2, (ft-1 (x) Px. IIx (x (x0) px, (xt) dd drz, C k2 log T
D
T2
/
Prz,ly (00-1/2)) - Px. (I0- px. (xt) d + C kst log T 72
22

---

kt 1#logg? T
(J)AE Py-- (0x-1 (x) px, (2z) dæ, id +03
T
Here the penultimate step follows from the fact that
I Py:,in IG (It-1 (1-11/1)pp00 (x)) px. (x²) dr / px,- (#t-1 x4) px. (x+) d 1.
boils down to bounding 4.,3 In view of (A.26), we know that
/ PY (Fc-1 xx) px. px. (Zx) 1 for & Ti) 1d
A1.3
+ Dy;;,1X, +DDYi (IC-1 21) (FC-1
It --
& $ drr
(Ix) 1
E To,
VI- a4
P (Xt & Tt) +P X1 E Tt.
X1 - (X, + 17 8 (X.) + +0;2)
#0)
where Z ~~
v1 a4
M (X,, 077
P $ Tt) +P
X1 (.EET.. Tú,
-I-ai aq
Here use the fact that Yi-1 / =x ~ N NN + ni st (3t) (ot (ot2/as)
Notice that
Th (X,, + 0 =-I-- ais; (X,)
a4 α
1 ai. z
V1 -1-a
The following claim is cricial for understanding this random variable.
Claim For any 24 E Te, we have
1 - aist (xi)l1 S 1 ( lok
and for any 1 isisis No.
a (1) - x3) b (fx) s / / -
Proof. See Appendix A.7.1.
Since Z ~ N0, Ia), in view of Lemma 9, with probability exceeding 1 1- exp (-(C1/64)) (og/444//og7) log
a a. C2
1 1 vd+
ViiklogT
and for any 1 isisis Ne.
0: 0i 1-a [ - =2) 2 < (x x;) - 2
C2 T| -x3 12-
These combined with Claim allow us to show that
PP Xxx (x. E m7 (X,) + 2
C1
&G) S exp
VI- ar
Taking the above inequality collectively with Lemma gives
C1 (-Ci logT)
(-CA
C1 k log T
(-91 k log
D S exp
+ +exp
< 2exp
64
64
Hence we have
h log A,1 I D Ch
< 2exp (-
C1
lloo
k log
k log
C
$ 202
T
64
T
T
as long as I' is sufficiently large.
23

---

A.7.1 Proof of Claim 1
Consider the decomposition xt-- = v (2x) + v1 - ayw as in Appendix A.I, where To (x1) E
Bi(a,) for some i(xx) E I and w E G. Notice that
1
1
8/ (1r))
(xt vasto)
[VasTo(()) + v1 ae varlzo + +6]
1 Ott
v αi
(xo(xz) - To)
w
+
8.
1 - Oke
V1 ae
1 Tte
where To = E|Xo| |x,
Xx = mi) is defined in (4.3), whereas To E (xx) and d are defined in (A.27).
Therefore we can check that
Voa(1 (1s)
1 ||ll|2 + V [v,(1 (x.)
|| [ 0187 (se))l2
1(00((2))
Foll2 +
|012 l
1-a
V az
1 02
(1 at) //
Cak(1- (r)
1 at (Vd+ Cik V 11 at
1 at exp
C3klog log T
+
Cit
Cr.
C2.
32
8c1 log T
(- Cak log T'
3 C2kloggT + vd+ VikklogT + exxp
T
32
VV++ + VikklogT)
Here step (i) follows from (A.4), the fact that E 9, and (A.28); step (ii) follows from Lemma 8; while step (iii) holds provided that I' is sufficiently large. In addition, for any 1 S i < j s N₂ we have
ar (2;
25) T 2t (x+)
(2)
Va a4))
1 az
|,,((,)) - xolla|1 231l2
w T (at - 22)
1 at
V
1
at
v ( - ax))
||0||||0; - =2]l2
1- ae
(b)
V 0r( - -rt)
Czk(11 -x,) log T
1 - az
31/
|| 23 212 + V 11- 1-wa a
v Cokkoog -2j12
1- σ
āz
v or( (1 - ar)
1
exp( (
Caklog 1')
V
exp
|| - 2zح12 1|2
1 Ci
32
8c; log
Czk log T
3/ / Cog + Cik + exp
|, 1897-x711 231l2
T
32
WC T|k - 271
Here step (a) utilizes the Cauchy-Schware inequality; step (b) follows from (A.4), the fact that w E G. and (A.28); step (c) follows from Lemma 8; while step (d) holds when T is sufficiently large.
A.8 Proof of Lemma
We can upper bound
| by
/ (1lvaje;11 - - + ||
A
S Teot2eR 22R
+ 1) Px,- (1) ((12, $ Art dx
[[]] Va - X.lla + +| + 1) ((,,, X.-1) $ AcH
@ 2
[[V] 0nl || W.ll2 + || + 1) 1 ((X,, Xx-1) $ AAH
(10)
ta2-oaa 20 II - 1 12 /2 [|] /l/ (Xx,))-1) & Ar) + r - [| F1/2 Xe-1) $ Ar) (A.40)
+l +
$ At).
24

---

Here step (i) follows from Lemma 4; step (ii) follows from the update rule (2.1); step (iii) utilizes the Cauchy-Schward inequality. In view of (2.2), we have
[| X [ E [Ilva, + /1 - ar W. S E [2x + - at) [
20, + 2 (1 - 0i.) d - 2 + 2d,
(A.41)
where we use the fact that [[[ W 11 d. Then we have
Tent
(Va o1)
22 2d) pi/2 ((X,, X1-1) $ At) Tou ((X,, (e-1)) $ As)
(-
C1 log + too exp
C1 (-1
Too 2en
2R 2R+3vd
exp
8
(0)
C1
S exp
k log T
16
Here step (a) utilizes (A.41) and the fact that [, = d; step (b) follows from Lemma I; while
step (c) makes use of the assumption that k 2 log d and holds provided that C₁ > + CR.
A.9 Proof of Lemma
We first decompose K; into
K. / px. 1|X4 (#e-1 px,
px, (2t) (x+-1 mz (xx)) (2x) dr
/ (px. 11xe (xo-1 x1) Pr (00-1 mx) px. (2x) (xt-1 p4 (21)) E (Ix) dr
(Sn (xx) (px (FL-1
Py In (--1 1x)) px. (21) (#1-1 11 (at)) (xx) dr
K,,1 + K2
Here step (i) follows from the fact that f [Pyy,,,, (02-1 (2)) (x+-1 - nt (x=))dxa-1 = 0 for any
Ie Rd. and K₃ and K2 are defined be the two integrals over Ag and AB in step (ii). The following two claims provide bounds for the two integrals K1, and Kg respectively.
Claim 2. Suppose that >>
k log" T. Then for each < t I T, we have
A llog" 3 T
C1 log T
KK,1| 3C,
E Exonn [||e> (ax) [12]
T
Proof. See Appendix A.9.1.
Claim 3. Suppose that T > 1. Then for each 2 < < T, we have
(-
C1
K221 < 2cxp
(- 32
k log T B1/2
[lle (ax) [1a]
Proof. See Appendix A.9.2.
Then conclude that
Ki < |
+
|Kr22
2 log"
T
Ca log T
C1 k log T
3C$
ExIng.
[||e (xx) [2]] + exxp
(-32
E1/2 [[le (xx) [12]
T
T
32
2 log 3 T
C1 log T
4C's
11/2
[||e, (xx) 11
strige
as claimed. Here step (a) follows from Claim and Claim 3; while step (b) utilizes Jensen's 's inequality, and holds provided that T' is sufficiently large.
25

---

A.9.1 Proof of Claim 2
The term K2,1 can be upper bounded by
Px--iXX, (#r-1 2x)
| =
px, 1/s (dte-1 xt) px, (xt) (00-1 - 12 (2x)) T Er (xx) dr. drx
PY2 (ft-1 [it)
PXe (1ir-1 (24)
Pr (0t-1 x4) px, (2te) (0o-1 14 (ae)) T ee (1e) dx idr
1
Pr:,1M MY (Ie-1 xz)
k22 log"
2
T
C3
Py; 18, (#0-112() px. (2e)
- (ze))² Es (2ze) d
T
2 log"?
$
T
oi
IT E4 (x,) {
{(
+ + n107 (X,) + ox %
C5
E
Xx,,
E AAt
T
Vou
Voi
k² log
3 T
[1 - a4) (as σr) E I El (Xx)l]
(v)
12 Foog'1 T
8e1 log T
2 V2n
S Cs
S Cp
E (X))l()))
Or (1 11-0)) (i.)
ka2 log
3 T
Ci log T
30
Eggng. [llE, (xx) [|a]
T
Here step (i) follows from Jensen's inequality; step (ii) utilizes Lemma 3; step (iii) follows from the definition of Y, in (4.1) and of μ in (4.7), and Ze ~ (0, La) is independent of X2; step (iv) follows from Lemma 8 and the fact that Z, e (X,, X₂ (O, || (x)) and hence
2
| a (X)ll E E El (X.)
Xx]]
E (X,,
22x
A.9.2 Proof of Claim 3
The term Ke,1 can be upper bounded by
JAz (px--IXX (01-1 xx) + pvr 11% (xx-1 2.)) px. (xx) ||0111 1t (xx))la || (2t)lla d
|Ke.2 -
1/2
/ (px--ix, (0e-1 2e) + PY; In (re-1 me) px, (xt) ||ae-1 14 (at))12 Id
1/2
(xx (50-1 (xx)) PYL,, i (3e-1 xxe) px, (2ra) lle. (xx)l1 d
Ag
The second term ?/2 can be easily bounded by
72 S 1/
1/2 Be [lle, (ar+) [13]
In what follows, we will bound the first term 71. Note that
g / A PX (0+-1, || - mē (xt) d
PVc, 1Y, (50-1 xx) px, (ot) ||0-11 - ui (st))le da
Ap
2012
We have
71.1 = E [ - -4 (xx))1 ((X,, X,-1) & A.)]
6 S ||x 1/2
15 (XIII)] ((x $
26

---

n S ai 21/2 1IvI-apie + ss (Xt) 11
Ci
exp
k log T
8
(i) < 4 |IVI- W. + si (x.))l exp
C1 k log T
Here step (i) follows from Cauchy-Sehhe Sehwwar inequality; step (ii) follows from Lemma and the definition of 14 in (4.7); while step (iii) uses the fact that 04 2 1/2 (see Lemma 8). Recall the definition of (-)
(ot
V Th
Xo X xz))
=xx)
1 T
which leads to the following upper bound
1
vār R
vān R Cxt
11 (x+) -
||eell2
|VarXo aa.
Cte
Ci.
az.
1
Well
+2 2
Var R.
(A.42)
V1 at
1 at
Hence we have
(
E
[I [ W. + 57 (xx)
I 8 (1 2 E [1
+ (1 (1-ar)) E ||st (xx))
(8)
5 8
C1 log
2
W, [ +
88c log T
E (1[ + R)"]
T
T
(i1)
(d + R²)
16
Here step (i) follows from the elementary inequality 8(x* + y²) 2 (x + +y); step (ii) follows from Lemma and (A.42); step (iii) follows from W,, W ~ NO0 Ia) and the proviso that T being sufficiently large. Hence we have
C [-
Co k log (-To 16
71,1 S v & Rxexp
exp
as long as Co >> and k 2 log d. Regarding 71,2, we have
@
E
X, s (X.) + 7
X, + 1// 8 (X.)
2
1( X $ Ar}
Vas
Vai
2
|122112 2 11 {(X,, 12-1) & Ar}
(
a4)
(as -ar) 12/2 [12zalē]] 121/2 ((Xr.Xe-1) $ As)
(1
[e)) az
(in) 8c, log
exp (- 1 log
B2/2
|122112
(iv)
exp (-16") logg)
(-i,
T
Here step (i) follows from the definition of Y, in (4.1) and of μę in (4.7); step (ii) follows from the Cauchy-Schward inequality; step (ii) utilizes Lemma and Lemma 1; while step (iv) follows from Z, ~ (0, Ia) and holds provided that I' is sufficiently large and k 2 log d. Taking the above bounds collectively yields
log (- C. C1 T
K1,2 S S VTL. + 71,22 S 2exp
B2l2 [llse (xx) [12]
32
B Proof of Theorem 2
In view of the update rule (2.1), the variables Xo, XI...,, Xx are jointly Gaussian, and we can check from (2.2) that
===a.X vI Tt W. ~ N (0, + (1 la)
(B.1)
hence the score functions
51())= - (a,ly (1 T.)Laa 2, V
(B.2)
27

---

We first derive the density of X1-1 conditional on X₁ = Fg. Since the joint distribution of (X
X1-1 Xx
|=| ~~ ([0)
T + -1--3 +1--1-1)44 Va 11- + (1 aa)
var (ar-14 + (113--1)44) aet + - -a
1).
we can derive that
X,-1 X, =t ~ N /Vsl 1/ 1- a01 1-0-1 (La - 1x)) Its (1 - -04) (Ix + 1 - 1-0-1 01-1
(La 1b) 1b))
1- at
1- a₁
In addition, with perfect score estimation, we can use (2.3) and (B.2) to achieve
Y Y1 + 11 (Yi) + or
Yi m (ā + -1-
Yt + o,
vaz
Vat
which indicates that
(vos (1 (1-m)) I + (1- 1/1 āi
ot Id
Y--1 Y- = -
(Id - Ix.) (To-
Ft. at
Vas
Then we can check that for any Tz Rd.
KL (px.-.|x, Xx (.12g) || 112 ( (x2))
(1 0q mTe)
at (1 at)
ar (1 a1-aa)) ar)
|/
1-3 + 2
log
-11
2
of
o7
04 )
[I(La 1x)xz(
xel12
d - k (
((1 (1- 0z) (ar - az)
log
(1 a4) (ar -oz) oz)
-1) 1)
2(1 σ.))
2
of (1 - -kt)
0 (1 - -aa)
One can check that
z log 2 0.1 min
(1, 1)7]. v=>0.
We combine the above two relations as well as the assumption that & S d/2 to achieve
(1 at -1)3
d
( (11-a)) (1) (0)- ar) - 1)
KL (px,-iix, (-124) PY, ( (x)))) 2
2(1 - ai,) 11(La x1 40 of (1 - a())
By taking expectation w.r.t. Tr, we have
Exinge [KL (px--ixx, (.12z) PY,-Ix (-1x;)]] 2 d (1 - a. - = ( (1- az)
(11-a)) (a: - [, -1
=4"
40 of (1 ax)
where we use the fact that
Exysng [[[(Ta - Tx) salle] = (d- (dd-k) k)) (1 - -a)) 2 d
2 (1 ot)
C Technical lemmas
This section collects a few useful technical tools that are useful in the analysis.
Lemma 8. When T is sufficiently large, for 1 < t S T, we have
04 2 1 C1 log T
1
T
2
In addition, for 2 < T, we have
1 at
1 1 02
Sc, log T
<
I ai
02
T
Proof. See Appendix A.2 in [14].
28

---

Lemma 9. For Z ~ (0, 1) and any 2 1, we know thatPropositinn 2.1.2
[| 2 t) S 12,
1
In addition, for chi-square random variable Y (d), we have
P(VY > Vd + t) S E 1/2
VES 1.
Proof. See Proposition 2.1.2 in [27] and Section 4.1 in [12]. Lemma 10. Suppose that T is sufficiently large. Then we have
KL (px,llpr,) T00
Proof. See Lemma 3 in [14].
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in the abstract and introduction reflect the paper's contributions and scope and are justified in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine include aspirational goals motivation long it is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitiation in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate " "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification,
asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g.. if the approach was only tested a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tes system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The full set of assumptions are provided in Section The proof Section and the appendix is complete and correct.
30

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental matcrial, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g.. with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed- source models. it may be that access to the model is limited in some way (e.g.. to registered users), but should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
31

---

Please see the NeurIPS code and data submission guidelines (https://nips) http:///iipps.cppullii//e guides/CodeSubmi ssioniolccy) for more details.
While we encourage the release code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https cctippcccc/pbbcc/////cccc guides/Codeeubbn ssi onoooonPlyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
32

---

8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
Code Of Ethics
Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
ct/ppliccffthicaauieeeeeee.. ines?
Answer: [Yes]
Justification: The research conducted in the paper conformes, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theory paper. There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
33

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses addition attacks, mechanisms for moni- toring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
34

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Sub- jects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such the institution conducting the review.
35


Reviews:
[{"review_id": "G9Havpd4EG", "reviewer": "Reviewer_NxHA", "summary": "This paper discusses the DDPM sampler's capability to adapt to unknown low-dimensional structures in the target distribution, and studies how this informs the coefficient design.", "questions": "1. How does this paper's result compare with [1], which does not require knowing/estimating the manifold? \nCan the result in the paper lead to a tighter bound when a subspace is given a priori? For example, how does it compare to [2]?\n\n[1] Rong Tang and Yun Yang. Adaptivity of diffusion models to manifold structures. In International Conference on Artificial Intelligence and Statistics, 2024. \n[2] Kazusato Oko, Shunta Akiyama, and Taiji Suzuki. Diffusion models are minimax optimal distribution estimators. arXiv preprint arXiv:2303.01861, 2023. \n\n2. Section 3.2 about unique coefficient design is very interesting, however, the results lack generality. \n    - Theorem 2's result is derived in the case that the target data distribution is a standard Gaussian distribution. What can you get when considering a general data distribution?\n    - As the authors noted at the end of the section, the uniqueness shown is with respect to the upper bound of the TV error. How does one make use of the uniqueness with respect to the upper bound in practice? What are the possible ways to address the coefficient design for the actual TV error, or tighten the gap?", "limitations": "The authors have disccussed the limitations.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is written clearly and has a nice structure in general. It contributes to an important topic in diffusion models about adapting to lower dimensional structure. In the first part of the paper, the authors show that, with a particular coefficient design (2.4), the TV error of the DDPM sampler has an upper bound that depends on the intrinsic dimension. In the second part of the paper, the authors exemplify the unique choice of the coefficients.", "weaknesses": "The main weakness of the paper is the generality. The adaptivity to the lower dimensional structure is based on a particular coefficient design, however, this design is not shown to be unique for the TV error, or for general target data. It is this reviewer's opinion that it is better to write the contribution section more precisely in terms of the setup and the scope of the results. The concerns are specified in the questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We address your comments below.\n\n**Comparison with prior works.**\nThank you for the reference. These two works and the current paper approach the diffusion model from different perspectives, making direct comparison challenging. Specifically, the two prior works establish error bounds for estimating density under the assumption that the true target density meets certain smoothness conditions. Their results rely on a score-matching procedure designed based on the level of smoothness, situating their findings within the context of nonparametric statistics.\n\nIn contrast, our paper approaches the problem from an applied mathematics perspective, decoupling the error of DDPM into discretization error and score matching error, and characterizing them separately, akin to prior works [3, 4, 6, 13]. Our results assume minimal conditions on the target distribution, avoiding smoothness assumptions, and accommodating arbitrary score-matching procedures. Therefore, our results cannot be directly compared with these prior works.\n\nOur paper does not require knowledge or estimation of the manifold, and our error bound is expressed as the sum of discretization error and score matching error:\n$$\n\t\\\\mathsf{TV}(q_{1},p_{1})\\leq \\\\underbrace{C\\frac{\\left(k+\\log d\\right)^{2}\\log^{3}T}{\\sqrt{T}}}\\_{ \\text{discretization error}}\n\t+\\\\underbrace{C\\varepsilon_{\\mathsf{score}}\\log T}\\_{\\text{score matching error}}.\n$$\nWhen a subspace is given a priori, we believe it will not help in improving the discretization error bound, as it already adapts to the low-dimensional structure automatically. While there might still be room for improvement (e.g., reducing the polynomial dependency on $k$), we believe this requires new analytical tools rather than assuming access to the low-dimensional structure. However, knowing the subspace can aid in improving the score-matching error, as it is possible to exploit the subspace information to design an efficient score-matching procedure that achieves a smaller $\\varepsilon_{\\mathsf{score}}$. This, however, is not the main focus of our paper, as our result accommodates any score-matching procedure, which we believe is more general. We leave this for future investigation.\n\nWe will incorporate and discuss these references in our next revision. \n\n**Extending the lower bound to arbitrary data distribution.**\nThank you for raising this point. As far as we know, it is quite general to use the worst-case error (or risk) to characterize the inherent difficulty of a problem in areas like statistics (e.g., minimax lower bound) and optimization (e.g., algorithmic lower bound). We believe that establishing a lower bound for the (degenerated) standard Gaussian distribution effectively illustrates our point: if the algorithm cannot perform well without using the proposed coefficient design in probably the simplest case, we can hardly expect it to work well in more complicated examples. However, the good news is that for this problem, we can actually show a similar lower bound for arbitrary low-dimensional data distributions. **Please see our response to all reviewers for this general lower bound, as well as an outline of the proof.** We will include this result in our next revision.\n\n\n**Regarding the gap between our lower bound and the TV error.**\nThank you for raising this point. \nFirst, we would like to point out that we actually have an upper bound for the KL divergence between $q_1$ and $p_1$.\nIn the analysis, we control $\\mathsf{TV}(q_1, p_1)$ by bounding $\\mathsf{KL}(q_1\\parallel p_1)$ (see Eq.~(3.2)).\nThen the established KL lower bound in Theorem 2 is meaningful.\nWe will added the KL divergence bound in our main result.\n\nIn addition, the lower bound for KL divergence can also be extended to TV distance.\nAccording to the calculation in Appendix B (see Line 545 and 547), we know $p_{X_{t-1}|X_t}$ and $p_{Y_{t-1}|Y_t}$ are two gaussian distributions.\nThen with basic calculations, it can also be shown that\n$$\n\\\\mathsf{TV}(p_{X_{t-1}|X_{t}}, p_{Y_{t-1}|Y_{t}}) \\\\gtrsim \\\\min\\\\bigg\\\\{1, d\\\\left(\\eta_{t}-\\eta_{t}^{\\star}\\\\right)^{2}+d\\\\left(\\frac{\\sigma_{t}^{\\star2}}{\\sigma_{t}^{2}}-1\\\\right)^{2}\\\\bigg\\\\}.\n$$\nWe will also include this result in the next revision.\n\nFinally, due to the lack of GPUs, we conducted a numerical experiment using the data distribution considered in Theorem 2. The results demonstrate that the TV error and KL divergence are independent of the ambient dimension $d$ under our coefficient design (2.4), while they grow with $d$ under other widely-used designs. **Please refer to the figures in the attached PDF in the response to all reviewers**, where we plot the error curves of $\\mathsf{KL}(q_1\\parallel p_1)$ and $\\mathsf{TV}(q_1,p_1)$ versus $d$, with all other setups fixed. This supports the conjecture that (2.4) represents a unique coefficient design for achieving dimension-independent error.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YeKIeJKQil", "reviewer": "Reviewer_1aoU", "summary": "This paper investigates score-based diffusion models when the underlying distribution is near low-dimensional manifolds in a higher-dimensional space. It addresses the gap in theoretical understanding of diffusion models, which are suboptimal in the presence of low-dimensional structures. For the DDPM, the error dependency on the ambient dimension $d$ is generally unavoidable during each denoising step in the existing literature. However, the authors identify a unique set of coefficients that yields a convergence rate of $O(k^2/\\sqrt{T})$, where $k$ is the intrinsic dimension and $T$ is the number of steps. The analysis employs novel tools that characterize the algorithmic dynamics in a deterministic manner. Additionally, the paper establishes that the DDPM sampler's error, influenced by time discretization and score estimation, is nearly dimension-free, with the ambient dimension $d$ appearing only in logarithmic terms.", "questions": "**Q1.** Is it widely used in the literature to employ $\\epsilon$-net and cover number to measure the intrinsic dimension of a data distribution? The authors should provide a more thorough discussion on this point. \n\n**Q2.** In Line 126, the authors assume that the support of the data distribution is bounded. However, the support of the Gaussian distribution in Theorem 2 is not bounded. It is believed that this is not a good example to demonstrate the uniqueness of coefficient design.", "limitations": "Not applicable", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**1. Theoretical Advancement in Understanding Diffusion Models.** The paper makes a good contribution to the theoretical understanding of score-based diffusion models in the context of low-dimensional manifolds. By identifying a unique set of coefficients that yield a convergence rate dependent on the intrinsic dimension $k$ rather than the ambient dimension $d$, the authors provide a refined theoretical framework that addresses previously suboptimal theoretical support.  \n\n**2. New Analytical Tools and Methodology.** The paper introduces a new set of analytical tools to characterize the algorithmic dynamics of the DDPM sampler in a deterministic manner. This innovative approach allows for a more precise analysis of the error sources—time discretization and score estimation errors.\n\n**3.** In general, the paper is well-written and joyful to read.", "weaknesses": "**1. Strict Assumption on the Data Distribution** In Line 126, the authors assume that the support set of the data distribution is bounded. This assumption is overly restrictive and may not hold for many real-world data distributions, such as Gaussian distributions, which have unbounded support. The authors should consider relaxing this assumption or providing justification for its necessity, as well as discussing the implications of this restriction on the generalizability and robustness of their findings. \n\n**2.  Lack of Empirical Demonstration.** Although this paper presents a solid and sharp theoretical analysis of the convergence rate of DDPM, the authors don't provide any experimental results to support their theory. Without experimental evidence, it is difficult to assess the real-world performance and robustness of the proposed coefficient design and convergence rate improvements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We address your comments below.\n\n**Bounded assumption on the target distribution.**\n- We agree that the bounded support assumption is stronger than, for example, the bounded second moment assumption, and it excludes Gaussian distributions. However, we argue that this condition is satisfied in most practical scenarios. Arguably, the most important applications of diffusion models are to generate new images from a target distribution, where image data is naturally bounded. For instance, the CIFAR and ImageNet datasets consist of images with pixel values ranging from 0 to 255 or $[0, 1]$, and it is common to normalize them to the range $[-1, 1]$. Then the $\\ell_2$ norm of an image from, e.g., the CIFAR dataset, is typically below $60$. Moreover, for DDPM in image generative tasks, $T$ is typically around $100$. Hence, we believe it is reasonable to assume in theoretical analysis that the radius of the data distribution is bounded by $T^{c_R}$, where $c_R$ is any given fixed constant that can be very large.\n- We acknowledge that it is unfortunate not to cover common distributions like the Gaussian. Although we believe the bounded support assumption is not essential, it greatly facilitates our analysis, especially since we use a novel set of analytical tools that characterize the dynamics of DDPM in a more deterministic manner to establish convergence guarantees in the presence of low-dimensional structure. While we can relax this assumption in some specific cases (e.g., for Gaussian distribution, as illustrated in the next paragraph), we find it challenging to achieve a clean and concise result that holds generally for any distribution with a finite second moment. We leave this to future investigation.\n\nWe will incorporate these discussions in our next revision.\n\n**Truncating Gaussian distribution in the lower bound.**\nWe agree that the degenerated Gaussian distribution considered in Theorem 2 is not a good example because it is unbounded. As we mentioned in footnote 2 on page 5, this lower bound can be extended to the truncated Gauss distribution. We have changed the result to truncated Gaussian in the following.\n\t\nBefore presenting the details, we also want to highlight that we have extended Theorem 2 to a general lower bound that works for arbitrary low-dimensional data distributions, which we believe also helps addressing this comment. **Please see our response to all reviewers for this general lower bound, as well as an outline of the proof.** Now we continue presenting results for the truncated Gaussian. \n\t\nLet $X_0 \\sim \\mathcal{N}(0,I_k)$, and define its truncated counterpart $\\\\widetilde{X}\\_0$  as \n$$\np\\_{\\\\widetilde{X}\\_0} (x_0) \\\\propto p_{X_0} (x_0) 1(\\\\|x_0\\\\|_{\\infty} \\le T).\n$$\nDefine $\\\\widetilde{X}\\_t = \\\\sqrt{\\\\alpha\\_t}\\\\widetilde{X}\\_{t-1} + \\\\sqrt{1-\\\\alpha\\_t}Z\\_t$, and construct the reverse process $\\\\widetilde{Y}\\_t$ with score estimation of $\\\\widetilde{X}\\_t$. Then we can establish exactly the same lower bounds for $\\\\widetilde{X}\\_t$ and $\\\\widetilde{Y}\\_t$.\nNotice that $\\\\widetilde{X}\\_t$ and $\\\\widetilde{Y}\\_t$ have independent entries, hence it suffices to studying each entry separately (we use $\\\\widetilde{X}\\_{t, i}$ and $\\\\widetilde{Y}\\_{t, i}$ to denote their $i$-th entry), i.e.,\n$$\n\\\\mathsf{KL}(p\\_{\\\\widetilde{X}\\_{t-1}|\\\\widetilde{X}\\_t}(\\\\cdot | x\\_t) \\\\parallel p\\_{\\\\widetilde{Y}\\_{t-1}|\\\\widetilde{Y}\\_t}(\\\\cdot | x\\_t)) \\\\ge \\\\sum\\_{i > k} \\\\mathsf{KL}(p\\_{\\\\widetilde{X}\\_{t-1, i}|\\\\widetilde{X}\\_{t, i}}(\\\\cdot | x\\_{t, i}) \\\\parallel p\\_{\\\\widetilde{Y}\\_{t-1, i}|\\\\widetilde{Y}\\_{t, i}}(\\\\cdot | x\\_{t, i})).\n$$\nThe right hand side of the above inequality obeys\n$$\n\\\\text{RHS}= \\\\sum\\_{i > k} \\\\mathsf{KL}(p\\_{X\\_{t-1, i}|X\\_{t, i}}(\\\\cdot | x\\_{t, i}) \\\\parallel p\\_{Y\\_{t-1, i}|Y\\_{t, i}}(\\\\cdot | x\\_{t, i}))\\\\ge \\\\frac{d}{4}\\\\left(\\\\eta\\_{t}-\\\\eta\\_{t}^{\\\\star}\\\\right)^{2}+\\\\frac{d}{40}\\\\left(\\\\frac{\\\\sigma\\_{t}^{\\\\star2}}{\\\\sigma\\_{t}^{2}}-1\\\\right)^{2},\n$$\nwhere the first relation holds since the truncation does not affect the entries with zero variance, and the second relation is proved in Line 550-552 in Appendix B. \t\n\n**Empirical demonstration.**\nThank you for raising this point. \nWe have conducted a numerical experiment using the data distribution considered in Theorem 2. The results demonstrate that the TV error and KL divergence are independent of the ambient dimension $d$ under our coefficient design (2.4), while they grow with $d$ under other widely-used designs. **Please refer to the figures in the attached PDF in the response to all reviewers**, where we plot the error curves of $\\mathsf{KL}(q_1\\parallel p_1)$ and $\\mathsf{TV}(q_1,p_1)$ versus $d$, with all other setups fixed. This supports the conjecture that (2.4) represents a unique coefficient design for achieving dimension-independent error.\n\nWhile the lack of GPUs prevents us from examining this design in more complex, large-scale tasks, we believe that our theoretical findings and empirical observations are already meaningful and interesting. \n\n**Our use of $\\varepsilon$-covering.**\nThanks for raising this point! While we believe that it's a good idea to use covering number for characterizing low-dimensional structure in our problem, we are not aware of other existing literature that does the same. We choose to use $\\varepsilon$-net and covering number to define approximate low-dimensional structure because we believe that this is less stringent and more general than assuming an exact low-dimensional structure (e.g., by assuming that the support of the data distribution lives in a low-dimensional subspace). As a sanity check, we showed in Section 2 that when the support of the data distribution lives in an $r$-dimensional\nsubspace, our intrinsic dimension $k$ defined through covering number is of order $r$, confirming that our definition is indeed more general. We will incorporate these discussions in our next revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BGHSPUbxbJ", "reviewer": "Reviewer_SgF5", "summary": "In DDPM-style diffusion models, we need to discretize a continuous\nprocess.  Benton et al [3] showed that ~ d/eps^2 steps suffice over d\ndimensions.  But what if (as is typical) the data lie in a space of\nlower intrinsic dimension (e.g. k-sparse or a k-dimensional manifold)?\nThis paper shows how to replace the d in the iteration complexity by\nk^4.", "questions": "How does the schedule (2.4) compare to the suggestion from [3]?\n\nWhat happens if X isn't exactly low dimensional, but is close?  Say,\nthere is eps TV mass outside the cover.", "limitations": "None.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This paper shows that DDPM can be nearly dimension independent, up to\nlog factors only depending on the intrinsic dimension.  This holds for\na very general definition of intrinsic dimension---just the log\ncovering number.  I was pretty surprised to learn that such a result\nis possible.\n\nDoing so requires particular choices of step size, which they show is\nnecessary, at least for the typical Girsanov-style proof approach.", "weaknesses": "Obviously it would be nice to see k rather than k^4.  We don't\ntypically expect intrinsic dimension << d^{1/4}, so this isn't giving\na real quantitative improvement.\n\nThere's very little intuition for what's going on.  Why are these the\nright step sizes?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We address your comments below.\n\n**Intuition for our coefficient design.**\nThanks for raising this point. We have extended Theorem 2 to a general lower bound that works for arbitrary low-dimensional data distributions. **Please see our response to all reviewers for this general lower bound, as well as an outline of the proof.** We believe that this general result can help us understand the role of our coefficient design (2.4). To facilitate discussion, we copy the lower bound here:\n$$\\\\mathbb{E}_{x\\_{t}\\sim q\\_{t}}[\\\\mathsf{KL}(p\\_{X\\_{t-1}|X\\_{t}}(\\\\cdot| x\\_{t})\\\\parallel p\\_{Y\\_{t-1}|Y\\_{t}}(\\\\cdot| x\\_{t}))] \\\\geq \\\\bigg(\\\\frac{\\\\sigma\\_{t}^{\\\\star2}}{\\\\sigma\\_t^2} + 2\\\\log\\\\frac{\\\\sigma\\_t}{\\\\sigma\\_t^\\\\star}- 1\\\\bigg)\\\\frac{d}{2} + \\\\frac{c\\_0(\\\\eta\\_{t}-\\\\eta\\_{t}^{\\\\star})^2d}{2\\\\sigma\\_{t}^{2}(1-\\\\overline{\\\\alpha}\\_t)}  - C\\_{5}^2\\\\frac{k^{4}\\\\log^{6}T}{T^2}\\\\bigg(3+\\\\frac{\\\\sigma\\_{t}^{\\\\star2}}{\\\\sigma_t^2}\\\\bigg) - C\\_{5}\\\\frac{k^{2}\\\\log^{3}T}{T}\\\\bigg|\\\\frac{\\\\sigma\\_{t}^{\\\\star2}}{\\\\sigma\\_t^2} - 1\\\\bigg|\\\\sqrt{d} - \\\\exp(-c\\_1k\\\\log T)$$\nThis bound is achieved by a novel set of analysis tools that characterize the algorithmic dynamics in a more deterministic manner, which together with our analysis in Theorem 1 provide a sharp characterization of the impact of coefficient design (i.e., $\\eta_t$ and $\\sigma_t$) in determining the error induced in each denoising step. It can be seen that, unless we take $\\eta_t=\\eta_t^\\star$  and $\\sigma_t=\\sigma_t^\\star$ as suggested in (2.4), there will be inevitable error that scales at least linear in $d$ incurred in each denoising step. \n\n**Comparison with other coefficient designs.**\nThank you for raising this point. In the prior work [3], the marginal distribution of the forward process is $X_{t_k} \\sim e^{-t_k}X_0 + \\sqrt{1-e^{-2t_k}}\\,\\overline{W}$ where $\\overline{W}\\sim\\mathcal{N}(0,I_d)$.\nThis means that $e^{-2t_k}$ plays the role of $\\\\overline{\\\\alpha}\\_t$ in our paper.\nBy examining their discretization rule (see Eq.~(4) therein), we find that they use the following update rule:\n$$\nY_{t-1} = (1+\\Delta_t)Y_t + 2\\Delta_ts_t(Y_t) + \\sqrt{\\Delta_t}Z_t,\n$$\nwhere $\\Delta_t = \\frac{1}{2}\\log\\frac{1}{\\alpha_t}$.\nBy applying a similar calculation as in Theorem 2, we can show that:\n$$\n\\\\mathbb{E}\\_{x\\_{t}\\\\sim q\\_{t}}\\left[\\mathsf{KL}\\left(p_{X_{t-1}|X_{t}}\\left(\\cdot| x_{t}\\right)\\,\\Vert\\,p_{Y_{t-1}|Y_{t}}\\left(\\cdot| x_{t}\\right)\\right)\\right] \n\\gtrsim \\frac{d}{T^2}.\n$$\nHence, the coefficient design in [3] will also incur dimension-dependent error in each denoising step. We will incorporate these discussions in our next revision.\n\n\n**Approximately low-dimensional structure.**\nThank you for raising this point. We first would like to clarify that we are not assuming that the data distribution is exactly low dimensional. Our characterization of low-dimensionality is based on the covering number of the support, as defined in Section 2, which accommodates approximately low-dimensional structure. For example, our setup includes the case that $\\mathsf{supp}(p_\\mathsf{data}) \\in \\cup_{i \\le N_{\\varepsilon}} \\mathbb{B}(c_i, \\varepsilon)$, the balls centered at $c_i$ with $\\varepsilon$ radius, whose dimension is $d$ instead of $k$. Therefore even if the support of the data distribution is not exactly low-dimenaional, our results can still be applied. (We apologies if we misunderstood your question.)\n\nIt is an interesting question whether our result is stable against adding an $\\varepsilon$-mass outside the cover. This setting is beyond our current result, since this mass can be spread out in the full space (thus having large covering number that depends on $d$). We conjecture that our result will be stable to this perturbation, namely it is possible to show an error bound similar to Theorem 1, but has an additional term proportional to $\\varepsilon$ (or $\\varepsilon d$). Currently, we don't know how to prove this result, and we leave this for future investigation.\n\n**Improving the quartic dependency on $k$.**\nThank you for raising this point. Currently, we don't know how to improve this dependency, which we believe requires new analysis frameworks and tools. We leave this for future investigation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "anjx2ppasQ", "reviewer": "Reviewer_kJLP", "summary": "The paper considers the problem of convergence of probability distribution learned by diffusion models to target data distribution when the data distribution lies has some low-dimensional structure. Previous work either provides a convergence rate bound in Wasserstein distance for low-dimensional distribution or provides a bound in total variation distance with polynomial dependence on the ambient dimension. This paper improves the convergence rate to logarithmically depend on the ambient dimension and polynomially on the intrinsic dimension.", "questions": "- I understand that showing the lower bound on the total variation error in section 3.2 might be difficult but can you experimentally show that the claimed coefficient in eq.(2.4) leads to a better convergence compared to other coefficients (e.g., coefficients used in practice) on some synthetic low-dimensional distribution? \n- The final bound on T in theorem 1 seems to depend on polylogarithmically on the dimension of the distribution (instead of polynomially in previous works). Is the polylogarithmical dependence of dimension necessary? \n\nMinor comment: it might be worth including a discussion in the paper on why earlier approaches get the dimension-dependent error.", "limitations": "Yes, the authors discuss the limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- It is interesting that the authors do not only consider the case of data on a k-dimensional manifold but consider a general version of a low-dimensional structure provided by the covering number of the support.   \n- The paper is overall well-written and easy to follow.", "weaknesses": "- The result in the paper is proved under the assumption of the bounded support of the data distribution (i.e. $|| x || \\leq R$ where $R = \\textrm{poly}(T)$). The results in the previous works are under the assumption that the data has a bounded second moment therefore, the bounded support assumption is more restrictive than the assumptions considered in the previous work. \n- The argument about the uniqueness of coefficients that leads to dimension-independent discretization error in Section 3.2 is not convincing because it proves a lower bound on the error incurred in one denoising step which is an upper bound on the total variation distance (the authors also mention it).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We address your comments below.\n\n**Bounded assumption on the target distribution.**\nThank you for raising this point!\n- We agree that the bounded support assumption is stronger than, for example, the bounded second moment assumption, and it excludes Gaussian distributions. However, we argue that this condition is satisfied in most practical scenarios. Arguably, the most important applications of diffusion models are to generate new images from a target distribution, where image data is naturally bounded. For instance, the CIFAR and ImageNet datasets consist of images with pixel values ranging from 0 to 255 or $[0, 1]$, and it is common to normalize them to the range $[-1, 1]$. Then the $\\ell_2$ norm of an image from, e.g., the CIFAR dataset, is typically below $60$. Moreover, for DDPM in image generative tasks, $T$ is typically around $100$. Hence, we believe it is reasonable to assume in theoretical analysis that the radius of the data distribution is bounded by $T^{c_R}$, where $c_R$ is any given fixed constant that can be very large.\n- We acknowledge that it is unfortunate not to cover common distributions like the Gaussian. Although we believe the bounded support assumption is not essential, it greatly facilitates our analysis, especially since we use a novel set of analytical tools that characterize the dynamics of DDPM in a more deterministic manner to establish convergence guarantees in the presence of low-dimensional structure. While we can relax this assumption in some specific cases (e.g., for Gaussian distribution, as illustrated in the next paragraph), we find it challenging to achieve a clean and concise result that holds generally for any distribution with a finite second moment. We leave this to future investigation.\n\nWe will incorporate these discussions in our next revision.\n\n**Regarding the gap between our lower bound and the TV error.**\nThank you for your suggestion! We conduct an experiment to examine whether our coefficient design (3.2) is indeed the unique coefficient design that leads to dimension-independent TV error $\\mathsf{TV}(q_1,p_1)$, described as follows.\n\nUsing the degenerated Gaussian distribution considered in Theorem 2 as a tractable example, we ran the DDPM sampler with exact score functions (so that the error only comes from discretization) and plotted the error curves of $\\mathsf{TV}(q_1,p_1)$ versus the ambient dimension $d$ under several different choices of $T$. We implemented both our coefficient design (2.4) and another widely-used design $\\eta_t = \\sigma_t = 1-\\alpha_t$. The results demonstrate that the TV error $\\mathsf{TV}(q_1,p_1)$ is independent of the ambient dimension $d$ under our coefficient design (2.4), while it grows with $d$ when using the other design. **Please refer to the figures in the attached PDF in the response to all reviewers.** This supports our key message that (3.2) represents a unique coefficient design for DDPM in achieving dimension-independent error.\n\n**Dependency on $\\log d$.**\nThank you for raising this point! The polylogarithmic dependency w.r.t.~the ambient dimension $d$ arises from the analysis tools that allows us to characterize the algorithmic dynamics in a more deterministic manner. This analysis framework is crucial for tackling the convergence of DDPM in the presence of low-dimensional structure. \n\nIn the proof, we identified a \"typical\" high-probability set where we are able to characterize the evolution of conditional density precisely (see our discussion at the beginning of Section 4). However, the algorithmic dynamic outside this set is difficult to track, and we have to bound some quantities related to the dynamics outside the typical set at the order of $d$. As a result, we have to set the radius of the \"typical\" high-probability set to be large enough (larger than some logarithmic factor of $d$), such that the exceptional probability is small (e.g., smaller than $O(1/\\mathsf{poly}(d))$ in order to offset the impact of these terms. We think it might be possible to improve the polylogarithmic dependency on $d$ via more refined analysis, and we leave it to future investigation.\n\n**Discussion on coefficient design.**\nThank you for the suggestion! We have extended Theorem 2 to a general lower bound that works for arbitrary low-dimensional data distributions. **Please see our response to all reviewers for this general lower bound, as well as an outline of the proof.** We believe that this general result can help us understand the role of our coefficient design (2.4), as well as why earlier designs  get the dimension-dependent error. To facilitate discussion, we copy the lower bound here:\n$$\\\\mathbb{E}_{x\\_{t}\\sim q\\_{t}}[\\\\mathsf{KL}(p\\_{X\\_{t-1}|X\\_{t}}(\\\\cdot| x\\_{t})\\\\parallel p\\_{Y\\_{t-1}|Y\\_{t}}(\\\\cdot| x\\_{t}))] \\\\geq \\\\bigg(\\\\frac{\\\\sigma\\_{t}^{\\\\star2}}{\\\\sigma\\_t^2} + 2\\\\log\\\\frac{\\\\sigma\\_t}{\\\\sigma\\_t^\\\\star}- 1\\\\bigg)\\\\frac{d}{2} + \\\\frac{c\\_0(\\\\eta\\_{t}-\\\\eta\\_{t}^{\\\\star})^2d}{2\\\\sigma\\_{t}^{2}(1-\\\\overline{\\\\alpha}\\_t)}  - C\\_{5}^2\\\\frac{k^{4}\\\\log^{6}T}{T^2}\\\\bigg(3+\\\\frac{\\\\sigma\\_{t}^{\\\\star2}}{\\\\sigma_t^2}\\\\bigg) - C\\_{5}\\\\frac{k^{2}\\\\log^{3}T}{T}\\\\bigg|\\\\frac{\\\\sigma\\_{t}^{\\\\star2}}{\\\\sigma\\_t^2} - 1\\\\bigg|\\\\sqrt{d} - \\\\exp(-c\\_1k\\\\log T)$$\nThis bound is achieved by a novel set of analysis tools that characterize the algorithmic dynamics in a more deterministic manner, which together with our analysis in Theorem 1 provide a sharp characterization of the impact of coefficient design (i.e., $\\eta_t$ and $\\sigma_t$) in determining the error induced in each denoising step. It can be seen that, unless we take $\\eta_t=\\eta_t^\\star$  and $\\sigma_t=\\sigma_t^\\star$ as suggested in (2.4), there will be inevitable error that scales at least linear in $d$ incurred in each denoising step.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their feedback. Here we address some common comments and questions.

**Extending the lower bound to arbitrary data distribution.** We agree with several reviewer's comments that the lower bound in Theorem 2 only covers Gaussian distribution, which can be restrictive. Here we generalize Theorem 2 to establish a similar lower bound for general low-dimensional distribution:

**Theorem.** Consider arbitrary data distribution $p\_{\mathsf{data}}$ satisfying the assumptions in Section 2. For the DDPM sampler (2.3) with perfect score estimation and arbitrary coefficients $\eta_t$ and $\sigma_t$, we have
$$\\mathbb{E}_{x\_{t}\sim q\_{t}}[\\mathsf{KL}(p\_{X\_{t-1}|X\_{t}}(\\cdot| x\_{t})\\parallel p\_{Y\_{t-1}|Y\_{t}}(\\cdot| x\_{t}))] \\geq \\bigg(\\frac{\\sigma\_{t}^{\\star2}}{\\sigma\_t^2} + 2\\log\\frac{\\sigma\_t}{\\sigma\_t^\\star}- 1\\bigg)\\frac{d}{2} + \\frac{c\_0(\\eta\_{t}-\\eta\_{t}^{\\star})^2d}{2\\sigma\_{t}^{2}(1-\\overline{\\alpha}\_t)}  - C\_{5}^2\\frac{k^{4}\\log^{6}T}{T^2}\\bigg(3+\\frac{\\sigma\_{t}^{\\star2}}{\\sigma_t^2}\\bigg) - C\_{5}\\frac{k^{2}\\log^{3}T}{T}\\bigg|\\frac{\\sigma\_{t}^{\\star2}}{\\sigma\_t^2} - 1\\bigg|\\sqrt{d} - \\exp(-c\_1k\\log T)$$
for each $2\leq t\leq T$, where $c_0,c_1,C_5>0$ are some universal constants.

Notice the fact that $x^2 - 2\log x -1 \geq 0$ for any $x>0$, and the equality holds only if $x=1$. Therefore the above results suggests that, unless $\eta_t=\eta_t^\star$ and $\sigma_t=\sigma_t^\star$, the corresponding denoising step will incur an error that is linear in $d$, when $d$ is sufficiently large. We will include this result in our next revision.

**Proof sketch.** Following the equation around Line 245 in Section 4.4, we start with the following bound:
$$\\mathbb{E}_{x\_{t}\sim q\_{t}}[\\mathsf{KL}(p\_{X\_{t-1}|X\_{t}}(\\cdot| x\_{t})\\parallel p\_{Y\_{t-1}|Y\_{t}}(\\cdot| x\_{t}))]\\ge 
 \\int\_{x\_{t-1}, x\_{t}} p\_{X\_{t-1}|X\_{t}}\\left(x\_{t-1} |  x\_{t}\\right)\\log\\left(\\frac{p\_{Y\_{t-1}^{\\star}|Y\_{t}}\\left(x\_{t-1} |  x\_{t}\\right)}{p\_{Y\_{t-1}|Y\_{t}}\\left(x\_{t-1} |  x\_{t}\\right)}\\right)p\_{X\_{t}}\\left(x\_{t}\\right)\\mathrm{d}x\_{t-1}\\mathrm{d}x\_{t} 
 =:\\mathcal{I}\_{t},$$
where we recall the definition of $Y\_{t-1}^{\\star}$ in (4.1). It boils down to understanding $\\mathcal{I}\_t$:
$$\\mathcal{I}\_{t}
 = d\\log \\frac{\\sigma\_{t}}{\\sigma\_{t}^{\\star}} + \\int\_{x\_{t}, x\_{t-1}} p\_{X\_{t}}\\left(x\_{t}\\right)p\_{X\_{t-1}|X\_{t}}\\left(x\_{t-1} |  x\_{t}\\right) \\bigg(\\frac{\\Vert\\sqrt{\\alpha\_{t}}z\_t-(\\eta\_{t}-\\eta\_{t}^{\\star})s\_{t}^{\\star}\\left(x\_{t}\\right)\\Vert\_{2}^{2}}{2\\sigma\_{t}^{2}} - \\frac{\\Vert\\sqrt{\\alpha\_{t}}z\_t\\Vert\_{2}^{2}}{2\\sigma\_{t}^{\\star2}}\\bigg)\\mathrm{d}x\_{t-1}\\mathrm{d}x\_{t},$$
where $\\sqrt{\\alpha\_{t}}z\_t := \\sqrt{\\alpha\_{t}}x\_{t-1}-x\_{t}-\\eta\_{t}^{\\star}s\_{t}^{\\star}(x\_{t}).$
Using similar analysis as in Lemma 6, the above integral on $\\mathcal{A}\_{t}^{\\mathrm{c}}$ (outside the typical set) can be controlled to the order of $\\exp(-\\Omega(k\\log T))$. According to Lemma 3, for $(x\_t,x\_{t-1})\\in \\mathcal{A}\_{t}$ we have
$$\\left|\\frac{p\_{X\_{t-1}|X\_{t}}\\left(x\_{t-1} |  x\_{t}\\right)}{p\_{Y\_{t-1}^{\\star}|Y\_{t}}\\left(x\_{t-1} |  x\_{t}\\right)}-1\\right|\\leq C\_{5}\\frac{k^{2}\\log^{3}T}{T}.$$
Therefore,
$$\\mathcal{I}\_{t} \\ge d\\log \\frac{\\sigma\_{t}}{\\sigma\_{t}^{\\star}} + \\int\_{x\_t}\\bigg(\\frac{\\Vert(\\eta\_{t}-\\eta\_{t}^{\\star})s\_{t}^{\\star}\\left(x\_{t}\\right)\\Vert\_{2}^{2}}{2\\sigma\_{t}^{2}} - C\_{5}\\frac{k^{2}\\log^{3}T}{T}\\frac{\\sigma\_{t}^{\\star}\\Vert(\\eta\_{t}-\\eta\_{t}^{\\star})s\_{t}^{\\star}(x\_{t})\\Vert\_{2}}{\\sigma\_{t}^2}\\bigg)p\_{X\_{t}}(x\_{t})\\mathrm{d}x\_{t}  + \\bigg(\\frac{\\sigma\_{t}^{\\star2}}{\\sigma\_t^2} - 1\\bigg)\\frac{d}{2} - C\_{5}\\frac{k^{2}\\log^{3}T}{T}\\bigg|\\frac{\\sigma\_{t}^{\\star2}}{\\sigma\_t^2} - 1\\bigg|\\sqrt{d} - \\exp(-c\_1k\\log T).$$
Here, we make use of the observation that for $0 < \delta < 1$,
$$ \\mathbb{P}\\bigg(\\bigg|\\frac{\\Vert\\sqrt{\\alpha\_{t}}z\_t\\Vert\_{2}^{2}}{\\sigma\_{t}^{\\star2}} - d\\bigg|^2 \\ge 2d\\log \\frac{1}{\delta}\\bigg) \\le \delta.$$
Then the desired lower bound follows from the following facts:
$$\\int\_{x\_t}C\_{5}\\frac{k^{2}\\log^{3}T}{T}\\frac{\\sigma\_{t}^{\\star}\\Vert(\\eta\_{t}-\\eta\_{t}^{\\star})s\_{t}^{\\star}\\left(x\_{t}\\right)\\Vert\_{2}}{\\sigma\_{t}^2}p\_{X\_{t}}\\left(x\_{t}\\right)\\mathrm{d}x\_{t} 
 \\le \\int\_{x\_t}\\frac{\\Vert(\\eta\_{t}-\\eta\_{t}^{\\star})s\_{t}^{\\star}\\left(x\_{t}\\right)\\Vert\_{2}^{2}}{4\\sigma\_{t}^{2}}p\_{X\_{t}}\\left(x\_{t}\\right)\\mathrm{d}x\_{t} + C\_{5}^2\\frac{k^{4}\\log^{6}T}{T^2}\\frac{\\sigma\_{t}^{\\star2}}{\\sigma\_t^2},$$
as well as
$$ \\int\_{x\_t} \\|s\_{t}^{\\star}(x\_{t})\\|\_{2}^{2}p\_{X\_{t}}(x\_{t})\\mathrm{d}x\_{t} \\asymp \\frac{d}{1-\\overline{\\alpha}\_t}.$$
We will add the complete proof to our next revision.

**Setup of the numerical experiment.** We conduct some experiments to examine whether (2.4) is indeed the unique coefficient design that leads to dimension-independent error. We provide the setup for this experiment.
We use the degenerated Gaussian distribution $p_\mathsf{data}=\mathcal{N}(0,I_k)$ in Theorem 2 as a tractable example, and run the DDPM sampler with exact score functions (so that the error only comes from discretization). We fix the low intrinsic dimension $k=8$, and let the ambient dimension $d$ grow from $10$ to $10^3$. We implement the experiment for different number of steps $T \in\\{100,200,500,1000\\}$. We implemented both our coefficient design (2.4) and another widely-used design $\eta_t = \sigma_t = 1-\alpha_t$. The error curve of $\mathsf{KL}(q_1\parallel p_1)$ and $\mathsf{TV}(q_1,p_1)$ versus $d$ can be found in the attached PDF. This supports our key message that (2.4) represents a unique coefficient design for DDPM in achieving dimension-independent error.

Meta-review: The goal of the paper is the analysis of denoising diffusion probabilistic models under the assumption that the underlying target distribution is concentrated on a low-dimensional manifold with respect to the ambient dimension $d$. The Authors characterize the convergence of the model to the target data distribution, whose rate is shown to depend on the dimensionality $k$ of the aforementioned low-dimensional manifold. The paper has been appreciated for its clarity and for its contribution to the study of the performance of diffusion models in the presence of an underlying low-dimensional data structure, also showing how a proper design of the coefficients in the model can allow to reach convergence rate depending on $k$ and not $d$. A limitation stressed by the Reviewers is related to the underlying hypothesis on the target distribution, which is assumed to have bounded support. 

In conclusion, the evaluation of the submission is positive, and I recommend acceptance. As an additional note, numerical experiment has been performed during the rebuttal phase to further support the results. I recommend the authors to incorporate the results presented in the rebuttal phase in the manuscript and clearly discuss the limitations of the results due to the technical assumptions.
Decision: Accept (poster)