Diffusion Models Adapt to Low-Dimensional Structure Under Flexible Coefficient Choices Changxiao Cai∗†
Yuchen Jiao∗‡
Gen Li‡
arXiv:2606.23627v1 [stat.ML] 22 Jun 2026
June 23, 2026
Abstract Diffusion models are known to exploit unknown low-dimensional structure to accelerate sampling. However, existing convergence theory under low-dimensional data structure has largely focused on update rules with narrowly prescribed coefficient choices. This raises a fundamental question: is adaptation to low-dimensional structure sensitive to the precise choice of update coefficients? In this paper, we show that such adaptation is a robust property of diffusion models. For a broad class of update coefficients, e we prove that O(k/ε) iterations suffice to generate an ε-accurate sample in total variation (TV) distance, independently of the ambient dimension. Our framework substantially broadens the class of diffusion samplers known to enjoy low dimensional adaptation and applies to several commonly used methods in practice. These results provide a theoretical justification for the empirical effectiveness of diffusion samplers across different coefficient choices when applied to structured, high-dimensional data.
Contents 1 Introduction
2
2 Preliminaries and problem setup
3
3 Results
5
4 Other related works
9
5 Experiment
9
6 Discussion
10
A Analysis 13 A.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 A.2 Proof of Theorems 1 and 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 B Proof of lemmas and corollaries 19 B.1 Proof of Lemma 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 B.2 Proof of Lemma 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 B.3 Proof of Lemma 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 B.4 Proof of Corollary 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 B.5 Proof of Corollary 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Corresponding author: Gen Li. ∗ The authors contributed equally. † Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA; Email: [email protected]. ‡ Department of Statistics and Data Science, Chinese University of Hong Kong, Hong Kong; Email: jiao,genli}@cuhk.edu.hk.
1
{yuchen-
1
Introduction
Diffusion models (Sohl-Dickstein et al., 2015; Ho et al., 2020; Song and Ermon, 2019; Song et al., 2020a) have emerged as a powerful class of generative models, achieving remarkable performance across a wide range of high-dimensional data-generation tasks (Ramesh et al., 2022; Popov et al., 2021; Dhariwal and Nichol, 2021). At a high level, these models generate samples by progressively transforming Gaussian noise into data through a sequence of iterative denoising updates guided by learned score functions (Song et al., 2020b). Despite their empirical success, this iterative sampling procedure can be computationally expensive, motivating extensive efforts to understand when and how diffusion sampling can be accelerated. A particularly promising direction exploits the observation that high-dimensional data often exhibit much low-dimensional geometric structure (Pope et al., 2021). Recent theoretical developments have shown that diffusion models can adapt to such unknown structure, with the number of sampling iterations depending on the intrinsic dimension of the data rather than the potentially much larger ambient dimension (Li and Yan, 2024a,b; Huang et al., 2024c; Liang et al., 2025; Potaptchik et al., 2024). Understanding the generality and robustness of this low-dimensional adaptation is therefore central to developing both an accurate theory and more efficient diffusion samplers. To set the stage for formal discussion, given pre-trained score function estimates {st (·)}Tt=1 , a diffusionbased sampling procedure can be expressed by the following general form: YT ∼ N (0, Id )
and
1 Yt + ηt st (Yt ) + σt Zt , Yt−1 = √ αt
t = T, · · · , 1,
i.i.d.
(1)
where Zt ∼ N (0, Id ) is independent Gaussian noise, (αt )Tt=1 is a noise schedule, and (ηt , σt2 )Tt=1 are properly chosen update coefficients. A central design choice in diffusion samplers lies in the selection of the update coefficients (ηt , σt2 ). As the update rules of diffusion models can be equivalently interpreted as numerical discretizations of a reverse-time stochastic differential equation (SDE), these coefficients are typically chosen to match the drift and diffusion coefficients of the SDE. Different discretization schemes therefore lead to different coefficients (ηt , σt2 ) and update rules. For instance, the coefficients of the original DDPM update rule (Ho et al., 2020) correspond to an exponential-integrator discretization of the SDE. Despite their algorithmic importance, the theoretical role of these coefficients remains inadequately understood. One prominent line of research focuses on its role on the sampling convergence when the data distribution exhibits low-dimensional structure (Li and Yan, 2024a; Potaptchik et al., 2024; Huang et al., 2024c; Liang et al., 2025; Li and Yan, 2024b; Tang and Yan, 2026). It investigates whether the iteration complexity to achieve an desired accuracy depends on the intrinsic dimension, instead of the ambient dimension, of the target data distribution. Existing convergence analyses under low-dimensional structure have largely relied on carefully calibrated update coefficients tied to specific discretization schemes. This has naturally led to the prevailing view that such calibration may be essential for exploiting unknown low-dimensional data geometry, and that even modest coefficient perturbations could substantially degrade sampling performance. This viewpoint, however, is in tension with empirical practice: diffusion samplers with noticeably different coefficient choices often perform well in practical applications. These observations suggest that successful adaptation to low-dimensional structure may not rely on a narrowly prescribed choice of drift and variance coefficients. To illustrate this point, we conduct experiments on the CIFAR-10 dataset (Krizhevsky et al., 2009) using Elucidated Diffusion Models (EDM) (Karras et al., 2022). We compare two parameter choices of σt across different numbers of sampling iterations. The results are presented in Fig. 1. For ease of comparison, the figure uses two horizontal axes: the bottom axis shows the number of iterations for the choice σt2 = (1−αt )(αt −αt ) , while the top axis shows the corresponding number of iterations for the choice σt2 = 1 − αt . 1−αt The top axis is a factor-2 rescaling of the bottom axis, reflecting that the latter sampler uses twice as many iterations. After this constant-factor adjustment, the two parameter choices achieve comparable sampling performance. This motivates the central question of our work: Is adaptation to low-dimensional data structure in diffusion models robust to coefficient choices?
2
400 3.4
500
600
700
800
900
1000
250
300
350
400
450
500
3.2
distance
3 2.8 2.6 2.4 2.2 200
Figure 1: Comparison of two parameter choices on CIFAR-10. Our contribution In this paper, we answer this question affirmatively. We show that adaptation to lowdimensional structure is a robust property of diffusion samplers. Specifically, for a broad range of update coefficient choices, the number of iterations required to produce an ε-accurate sample in total variation (TV) distance is at most k ε
(up to logarithmic factors),
where k represents the intrinsic dimension of the data, provided that an accurate pre-trained score function is available. Our theory substantially broadens the class of diffusion samplers known to enjoy provable guarantees under low-dimensional data structure. Previously, such guarantees were established only for a narrow range of coefficients tied to particular discretization schemes. In contrast, our framework accommodates a much wider family of samplers and impose substantially weaker conditions on the coefficient choices. In particular, our results apply to a broad range of methods commonly used in practice, including the original DDPM sampler, improved DDPM samplers, and analytic DPM-type samplers. This provides a theoretical justification for the empirical robustness of diffusion samplers with different coefficient choices when sampling from structured data distributions.
2
Preliminaries and problem setup
Forward process by
Let X0 ∼ pdata denote the target data distribution on Rd . The forward process is defined Xt =
√
αt Xt−1 +
√
1 − α t Zt ,
t = 1, 2, . . . , T,
(2)
i.i.d.
where (αt )Tt=1 are the noise schedules and Z1 , . . . , ZT ∼ N (0, Id ) are d-dimensional independent standard Gaussian random vectors. For convenience, define αt :=
t Y
αk ,
t = 1, 2, . . . , T.
(3)
k=1
Then the marginal distribution at time t admits the representation √ √ Xt = αt X0 + 1 − αt Z t , t = 1, 2, . . . , T,
(4)
where Z t ∼ N (0, Id ) is a standard Gaussian random vector independent of X0 . In particular, when αT is sufficiently small, the terminal distribution pXT is close to the standard Gaussian distribution on Rd . 3
In this work, we focus on the noise schedule (αt )t∈[T ] that satisfies the following condition: log T αt (1 − αt ), t = T, . . . , 2, (5) T where C0 , C1 > 0 are sufficiently large absolute constants with C1 /C0 large enough. The continuous-time limit of (2) is given by the SDE p 1 dXt = − βt Xt dt + βt dBt , X0 ∼ pdata ; t ∈ [0, T ] (6) 2 where βt : [0, T ] → R is a prescribed noise-rate function and (Bt )t∈[0,T ] is a standard Brownian motion in Rd . αT =
1
T C0
,
and
αt−1 = αt + C1
Reverse process Classical time-reversal results for diffusion processes (Anderson, 1982; Haussmann and Pardoux, 1986) show that if (Xt )t∈[0,T ] solves the forward SDE (6), then the reverse-time process (Ytsde )t∈[0,T ] , defined by Ytsde := XT −t , satisfies p 1 dYtsde = βT −t Ytsde + 2∇ log pXT −t Ytsde dt + βT −t dBt , Y0sde ∼ pXT ; t ∈ [0, T ]. (7) 2 Here, pXt denotes the marginal distribution of Xt in (6), and ∇ log pXt (x) is the score function of pXt , which we denote by s⋆t (x). A diffusion sampler seeks to generate samples from pdata by simulating the reverse SDE (7) starting from Y0sde ∼ pXT , which is approximately standard Gaussian. Update coefficient choices. Different update coefficient choices correspond to different discretizations of the underlying reverse-time dynamics and lead to different practical samplers. We summarize several representative examples below. • DDPM. The original DDPM sampler (Ho et al., 2020) uses αt − αt (1 − αt ), 1 − αt . ηt = 1 − αt and σt2 ∈ 1 − αt
(8a)
• Improved DDPM. Improved DDPM (Nichol and Dhariwal, 2021) takes the same drift coefficient as the original DDPM but allows the variance coefficient to vary within an interval, i.e., αt − αt 2 ηt = 1 − αt and σt ∈ (1 − αt ), 1 − αt . (8b) 1 − αt In this case, the specific value of σt2 is learned from data, allowing the sampler to interpolate between the two variance choices above. • Analytic-DPM. Analytic-DPM (Bao et al., 2022) retains the drift coefficient of the original DDPM but replaces the prespecified variance with an analytically derived, score-dependent variance. Under our parametrization, its coefficients are given by ηt = 1 − αt , and σt2 = (1 − αt ) 1 − (1 − αt )Γt , (8c) where h i 1 2 EXt ∼pXt ∥st (Xt )∥2 . d In practice, Γt is estimated using Monte Carlo samples: Γt :=
(m) 2 M X st (Xt ) 2 bt = 1 , Γ M m=1 d
(m) i.i.d.
Xt
∼ pXt .
The resulting variance estimate is further clipped using analytically derived lower and upper bounds to mitigate the effect of score estimation error. 1 1 With probability at least 1 − exp(−Ω(d)), it holds that (1 − α )∥s (X )∥2 ≲ d. Hence, in what follows, we consider t t t 2 b Γt ≲ 1/(1 − αt ).
4
From a theoretical perspective, most existing analysis focuses on a small number of specific coefficient choices. For example, several works (Li and Yan, 2024b) study the simple choice (ηt , σt2 ) = (1 − αt , 1 − αt ), while others (Chen et al., 2023a; Benton et al., 2023b) analyze √ (ηt , σt2 ) = 2(1 − αt ), 1 − αt ,
(8d)
(8e)
which arises naturally from certain discretizations of the reverse-time SDE. These choices are mathematically convenient and closely tied to particular numerical schemes. Intuitively, the samplers discussed above can all be viewed as certain first-order discretizations of a continuous-time reverse-time SDE. This perspective suggests that the coefficients should satisfy ηt , σt2 ≍ 1 − αt , while different samplers may only differ in higher-order terms. One may therefore expect that such higher-order differences should not fundamentally affect sampling performance. Motivated by this intuition, the goal of this paper is to develop a unified theory for DDPM-type samplers of the general form (1). In particular, we aim to understand whether precise coefficient choices are essential for efficient sampling under low-dimensional data structure, or whether low-dimensional adaptation is robust across a broader class of discretization schemes. Intrinsic low-dimensional structure. Let X ⊆ Rd denote the support of the target data distribution pdata , namely, the smallest closed set C ⊆ Rd satisfying pdata (C) = 1. To characterize the intrinsic dimension of X in a general manner, we use the notions of ε-nets and covering numbers; see, for example, Vershynin (2018). For any ε > 0, a set Nε ⊆ X is called an ε-net of X if, for any x ∈ X , there exists some x′ in Nε such that ∥x − x′ ∥2 ≤ ε. The covering number Nε (X ) is defined as the minimum cardinality of an ε-net of X . We impose the following conditions. • (Low-dimensionality) Fix ε = T −cε , where cε > 0 is a sufficiently large absolute constant. We say that X has intrinsic dimension k > 0 if log Nε (X ) ≤ Ccover k log T for some constant Ccover > 0. • (Bounded support) Assume that, for some universal constant cR > 0, where
sup ∥x∥2 ≤ R
R := T cR .
x∈X
Thus, the radius of the support is allowed to grow polynomially with the number of sampling steps T . This formulation accommodates distributions supported on, or concentrated near, low-dimensional manifolds and is therefore less restrictive than assuming an exact linear low-dimensional structure. As a simple sanity check, suppose that X is contained in an r-dimensional subspace of Rd . A standard volumetric argument; see, for example, Vershynin (2018, Section 4.2.1); yields log Nε (X ) ≍ r log(R/ε) ≍ r log T. Hence, in this setting, the intrinsic dimension k is of the same order as the subspace dimension r.
3
Results
We now present our main theoretical result. To characterize the effect of update coefficients, given a noise schedule (αt )Tt=1 , we define a sequence of effective noise variances (vt )Tt=1 recursively by η t 2 vt + σt2 , t = T, . . . , 2. (9) vT := 1 − αT and αt vt−1 = 1 − 1 − αt 5
In words, vT is initialized at the standard terminal noise variance 1 − αT , and the remaining variances are determined recursively by the update coefficients ηt and σt2 . To provide some intuition, the quantity vt can be interpreted as the noise level of an auxiliary forward process that is approximately tracked by the sampling iterates. More precisely, we define an auxiliary random bt )T by process (X t=1 bt = X
√
αt X0 +
√
(10)
vt Z t ,
i.i.d.
where Zt ∼ N (0, Id ) is standard Gaussian noise independent of X0 . We further define the noise deviation δt :=
vt − 1. 1 − αt
(11)
Thus, δt measures the discrepancy between the effective noise level vt induced by the update coefficients and the noise level 1 − αt in the canonical forward process. We are now ready to state the main theorem. Theorem 1. Consider the diffusion sampler defined in (1) with noise schedule (αt )Tt=1 and update coefficients (ηt , σt2 )Tt=1 . Assume that ηt ≤ Cη (1 − αt ),
σt2 ≥ Cσ (1 − αt ),
t ∈ [T ]
(12)
for any constants Cη , Cσ > 0. Suppose that the noise deviation sequence (δt )Tt=1 defined in (11) satisfies |δt | ≤ c
log2 T , T
t ∈ [T ]
for some sufficiently small universal constant c > 0. Then the sampler output Y1 satisfies k log4 T 3/2 b TV X1 , Y1 ≤ C + εsc log T T
(13)
(14)
for some universal constant C > 0, where εsc denotes the average score estimation error T
ε2sc :=
i h 1X bt ) − s⋆t (X bt ) 2 . EXbt ∼p c st (X 2 Xt T t=1
(15)
Theorem 1 shows that, provided the effective variance vt induced by the update coefficients (ηt , σt ) remains close to the canonical forward process variance 1−αt , the sampler output Y1 is close in TV distance to b1 . Importantly, the leading term that captures the discretization error depends the auxiliary random vector X on the intrinsic dimension k rather than the ambient dimension d. This theorem therefore demonstrates that low-dimensional adaptation holds for a broad class of coefficient choices, rather than only for a particular discretization scheme. The second term in (14) captures the effect of imperfect score estimation. It is worth bt )T , noting that the score estimation error εsc is defined with respect to the auxiliary forward process (X t=1 T rather than the canonical forward process (Xt )t=1 . This is because the sampling iterates Yt approximately bt )T rather than the canonical process (Xt )T . track the auxiliary process (X t=1 t=1 To accommodate deterministic samplers such as DDIM for which σt can be zero, we next establish a counterpart of Theorem 1. The result shows that the discretization error continues to adapt to the intrinsic dimension even in the absence of injected Gaussian noise. This extension, however, requires access to the exact score functions. Developing a unified theory that simultaneously captures coefficient robustness and score estimation error for deterministic samplers is left for future work. Theorem 2. Consider the diffusion sampler defined in (1) with noise schedule (αt )Tt=1 and update coefficients (ηt , σt2 )Tt=1 . Assume that the score estimates are exact, i.e., st = s⋆t for all t ∈ [T ], and ηt ≤ Cη (1 − αt ), 6
t ∈ [T ]
(16)
for any constant Cη > 0. Suppose that the noise deviation sequence (δt )Tt=1 defined in (11) satisfies (13) for some sufficiently small universal constant c > 0. Then the sampler output Y1 satisfies 4 b1 , Y1 ≤ C k log T TV X T
(17)
for some universal constant C > 0. We next discuss several important implications of Theorem 1. Low-dimensional adaptation. First, consider the idealized setting where the perfect score functions are available, that is, st = s⋆t for t ≥ 1. Suppose that the update coefficients (ηt , σt ) satisfy the condition (13). b1 , Y1 ≤ ε, it then suffices to take To guarantee TV X e k O ε sampling iterations. Consequently, diffusion models achieve substantial sampling acceleration when the target data distributions has intrinsic dimension k much smaller than the ambient dimension d. Notably, the sampler does not require prior knowledge of the underlying low-dimensional structure to obtain this speedup. The following corollary verifies that the condition on δt is satisfied by several important diffusion samplers used in practice. Corollary 1. The sampling procedures summarized in (8) satisfy the conditions (12) and (13). Therefore, the convergence bound (14) in Theorem 1 holds for all these samplers. e Corollary 1 shows that the convergence guarantee O(k/T ) in Theorem 1 achieves the state-of-the-art scaling established in prior works (Li and Yan, 2024b; Liang et al., 2025), while applying to a substantially broader range of samplers with various coefficient choices. This demonstrates that adaptation to low-dimensional structure is a robust property of diffusion samplers and does not rely on a narrowly prescribed choice of update coefficients. Relating the auxiliary marginal to the canonical marginal. Prior convergence analysis has primarily focused on TV(X1 , Y1 ) as a measure of how accurately the sampler output approximates the target b1 , Y1 ). The two reference distribution (Li and Yan, 2024b; Liang et al., 2025), while Theorem 1 controls TV(X b1 differ only in their noise variances. Indeed, distributions X1 and X d √
X1 =
α1 X0 +
√
1 − α 1 Z1
√ √ d √ b1 = and X α1 X0 + v1 Z1 = α1 X0 +
p (1 + δ1 )(1 − α1 )Z1 ,
b1 where Z1 ∼ N (0, Id ) is independent Gaussian noise. Thus, relative to X1 , the Gaussian noise variance in X is modified by a factor of 1 + δ1 . In particular, for an arbitrary noise schedule (αt )Tt=1 , there exists a choice of update coefficients (ηt , σt )Tt=1 for which the corresponding noise level deviations δt defined in (11) satisfy d b δt = 0 for 1 ≤ t ≤ T (Li and Yan, 2024b; Liang et al., 2025). As a result, X1 = X 1 and the corresponding sampler output Y1 satisfies TV X1 , Y1 ≤ C
k log4 T + εsc log3/2 T T
.
(18)
More importantly, exact variance matching does not require replacing a practical sampler by this special choice of update coefficients. For a given coefficient rule, even when the induced deviations (δt )Tt=1 are nonzero, one can instead modify the noise schedule (αt )Tt=1 while preserving the functional dependence of (ηt , σt ) on the noise schedule αt . The modified noise schedule can be chosen so that the resulting auxiliary marginal has the same signal-to-noise ratio as the original canonical marginal. After a scalar normalization, the two marginals therefore coincide in distribution. This observation is formalized in the following corollary.
7
Corollary 2. Consider an arbitrary noise schedule (αt )Tt=1 and any choice of update coefficients (ηt , σt )Tt=1 satisfying ηt = O(1 − αt ) and σt2 = αt − αt − 1 −
(1 − α )2 η t 2 t . (1 − αt ) + O 1 − αt 1 − αt
(19)
These conditions are satisfied by all the sampling procedures summarized in (8). Then there exists a noise schedule (αt′ )Tt=1 such that the output Y1′ associated with the noise schedule (αt′ )Tt=1 and update coefficients (ηt , σt )Tt=1 , after the normalization Yb1 = Crescale Y1′ for some constant Crescale depending on only α1′ and δ1′ , satisfies TV X1 , Yb1 ≤ C
k log4 T + εsc log3/2 T T
,
(20)
where δt′ is the noise level deviation induced by the noise schedule αt′ . Corollary 2 combines two observations. First, Theorem 1 guarantees low-dimensional convergence of Y1′ b1 . Second, the modified noise schedule matches the signal-to-noise ratio of X b1 to the auxiliary marginal X after some normalization with that of the original canonical marginal X1 , so that the normalized auxiliary marginal is exactly equal in distribution to X1 . Since TV distance is invariant under a common invertible scaling, these two facts together yield the low dimension-dependent convergence guarantee of TV(X1 , Yb1 ) in (20). Importantly, this does not require the coefficient-induced deviations δt to vanish or alter the functional relationship between the update coefficients and the noise schedule, and thus covers a broad range of practical samplers. Comparison with existing lower bounds. We conclude this section by comparing our result with existing lower bounds on one-step discretization error, namely, the sampling error incurred when exact score functions are available after a single update step. For a DDPM sampler with perfect scores, define the one-step update map Φ⋆t : Rd × Rd → Rd by 1 Φ⋆t (x, z) := √ (x + ηt s⋆t (x) + σt z). αt The DDPM update rule (1) can be expressed as Yt−1 = Φ⋆t (Yt , Zt ), where Zt ∼ N (0, Id ) is independent of Yt . Starting from the forward marginal Xt , prior work (Liang et al., 2025) establish the following lower bound on the one-step error:
TV Φ(Xt , Zt ), Xt−1 ≳
√
1 − αt d αt − αt
ηt 1− 1 − αt
2 +
σt2 −1 , αt − αt
where Zt ∼ N (0, Id ) is standard Gaussian noise independent of Xt . This lower bound suggests that the TV distance between the sampling iterate and the canonical forward process may scale with the ambient dimension d. In particular, for this one-step error to vanish as d grows, the coefficient-dependent quantity inside the absolute value must be of order o(d−1/2 ). Viewed solely relative to the canonical forward process, low-dimensional adaptation may therefore appear to fail for coefficient choices that do not satisfy this stringent matching condition. Our analysis reveals a different mechanism. Even when the sampling iterate is not close to the canonical bt−1 , whose effective forward marginal Xt−1 , it may remain close to the corresponding auxiliary marginal X variance incorporates the discrepancy induced by the sampler coefficients. Because this variance discrepancy can either be eliminated through an appropriate coefficient choice or absorbed into a modified noise schedule and final rescaling, the auxiliary process perspective allows us to establish intrinsic dimension-adaptive convergence guarantees for a substantially broader class of diffusion samplers.
8
10 0
TV distance
TV distance
10 0
10 -1
10 -2
200
400
600
800
10 -1
10 -2
1000
1000
2000
3000
4000
5000
b1 , Y1 ) across various ambient dimension d. Figure 2: TV distances TV(X1 , Y1 ) and TV(X
4
Other related works
Adaptation to low-dimensional structures: convergence theory. A substantial body of work has developed convergence guarantees for diffusion samplers, including standard DDPM and DDIM (Chen et al., 2022; Lee et al., 2023; Chen et al., 2023a; Li et al., 2023; Chen et al., 2023c; Huang et al., 2024a; Benton et al., 2023a; Li and Yan, 2024b; Li et al., 2025a) and higher-order accelerated samplers (Li and Cai, 2024; Li and Jiao, 2024; Jiao and Li, 2024; Huang et al., 2024a,b; Li et al., 2024; Yu and Yu, 2025; Li et al., 2025b; Gupta et al., 2024; Wu et al., 2024). More recently, Li and Yan (2024a) showed that the sampling convergence rate of diffusion samplers can depend only on the intrinsic dimension of the underlying distribution, and this dependence was subsequently sharpened in Potaptchik et al. (2024); Huang et al. (2024c); Li and Yan (2024b); Liang et al. (2025). Beyond continuous diffusion models, analogous low-dimensional adaptation results have also been established for discrete diffusion models. (Li and Cai, 2025; Zhao and Cai, 2026; Cai and Li, 2026; Chen et al., 2025; Dmitriev et al., 2026). Adaptation to low-dimensional structures: statistical theory. Complementing this computational perspective, another strand of the statistical efficiency of diffusion models. For general distributions, (Oko et al., 2023; Wibisono et al., 2024; Zhang et al., 2024; Cai and Li, 2025) demonstrate that diffusion samplers achieve minimax optimal rates for distribution learning and sampling. A further question is whether these rates improve when the underlying distribution exhibits low-dimensional structure. For distributions supported on low-dimensional linear subspaces or manifolds, recent works show that the required sample complexity depends on the intrinsic dimension rather than the ambient one Chen et al. (2023b); Azangulov et al. (2024); Tang and Yang (2024); Wu and Cai (2026). Beyond geometric support assumptions, other works establish minimax-optimal sample complexity guarantees for structured dependence models Fan et al. (2025), independent component models Boffi et al. (2025), and low-rank Gaussian mixture models Wang et al. (2024).
5
Experiment
In this section, we present numerical experiments to validate our theoretical findings. As it is challenging to compute the TV distance or to examine the influence of intrinsic dimension k and ambient dimension d on real-world datasets, we use a Gaussian distribution to validate our theoretical findings. Specifically, we consider the case where the target distribution is a d-dimensional Gaussian distribution with zero mean and a diagonal covariance matrix for which k ≤ d entries are equal to 1 and the remaining entries are zero. We set k = 10 or k = 50, and vary d from k to 5k. The total number of iterations is fixed at T = 500. After running DDPM with the two parameter choices in (8a), we numerically compute b1 , Y1 ). The results are shown in Fig. 2. They demonstrate that the TV distances TV(X1 , Y1 ) and TV(X 9
TV distance
TV distance
10 -1
10 -2
10 -2 200
400
600
800
1000
1000
2000
3000
4000
5000
Figure 3: TV distances TV(X1 , Y1 ) and TV(X1 , Yb1 ) across various number of iterations T . b1 , Y1 ) remains almost unchanged as TV(X1 , Y1 ) is not adaptive to the ambient dimension d, whereas TV(X ambient dimension d increases. This observation aligns with our theoretical finding in Theorem 1. In addition, to empirically verify Corollary 2, we compute the TV distances TV(X1 , Y1 ) and TV(X1 , Yb1 ) for varying numbers of iterations T . Here, Y1 is generated using the update coefficients (ηt⋆ , σt⋆ ), while Yb1 is obtained using ηt′ = (σt′ )2 = 1 − αt′ . The modified noise schedule {αt′ }Tt=1 is computed numerically using the bisection method. The results are presented in Fig. 3. As shown in the figure, the TV distances TV(X1 , Y1 ) and TV(X1 , Yb1 ) are comparable across different values of T , and both decrease as T increases. These observations are consistent with the conclusion of Corollary 2.
6
Discussion
In this work, we have explored the robustness of adaptation to low-dimensional data structure in diffusion samplers with respect to coefficient choices. We have shown that a broad class of samplers with various coefficient choices can achieve efficient sampling under low-dimensional structure, thereby providing a theoretical justification for the empirical robustness of diffusion samplers in practice. Looking ahead, several interesting directions remain for future research. First, it would be worthwhile to investigate whether the condition on the effective noise level vt can be further relaxed, thereby extending the theory to an even broader class of diffusion samplers. Second, a more refined analysis could characterize the precise influence of the coefficient choices, beyond the order-wise guarantees established in this work. Third, the current sampling error bound involves a score estimation error evaluated under the auxiliary forward process rather than the canonical forward process used for score training. It would therefore be valuable to determine whether, and to what extent, this distribution shift introduces additional sampling error, and whether it can be controlled under standard score estimation guarantees.
Acknowledgements C. Cai is supported in part by the NSF grant DMS-2515333. G. Li is supported in part by the Chinese University of Hong Kong Direct Grant for Research and the Hong Kong Research Grants Council ECS 24305724 and GRF 14307525.
References Anderson, B. D. (1982). Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):313–326. 10
Azangulov, I., Deligiannidis, G., and Rousseau, J. (2024). Convergence of diffusion models under the manifold hypothesis in high-dimensions. arXiv preprint arXiv:2409.18804. Bao, F., Li, C., Zhu, J., and Zhang, B. (2022). Analytic-dpm: an analytic estimate of the optimal reverse variance in diffusion probabilistic models. arXiv preprint arXiv:2201.06503. Benton, J., De Bortoli, V., Doucet, A., and Deligiannidis, G. (2023a). Linear convergence bounds for diffusion models via stochastic localization. arXiv preprint arXiv:2308.03686. Benton, J., De Bortoli, V., Doucet, A., and Deligiannidis, G. (2023b). Nearly d-linear convergence bounds for diffusion models via stochastic localization. arXiv preprint arXiv:2308.03686. Boffi, N., Jacot, A., Tu, S., and Ziemann, I. (2025). Shallow diffusion networks provably learn hidden low-dimensional structure. In International Conference on Learning Representations, volume 2025, pages 52889–52923. Cai, C. and Li, G. (2025). Minimax optimality of the probability flow ode for diffusion models. arXiv preprint arXiv:2503.09583. Cai, C. and Li, G. (2026). Confidence-based decoding is provably efficient for diffusion language models. arXiv preprint arXiv:2603.22248. Chen, H., Lee, H., and Lu, J. (2023a). Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learning, pages 4735–4763. PMLR. Chen, M., Huang, K., Zhao, T., and Wang, M. (2023b). Score approximation, estimation and distribution recovery of diffusion models on low-dimensional data. In International Conference on Machine Learning, pages 4672–4712. PMLR. Chen, S., Chewi, S., Lee, H., Li, Y., Lu, J., and Salim, A. (2023c). The probability flow ode is provably fast. Advances in Neural Information Processing Systems, 36:68552–68575. Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang, A. R. (2022). Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint arXiv:2209.11215. Chen, S., Cong, K., and Li, J. (2025). Optimal inference schedules for masked diffusion models. arXiv preprint arXiv:2511.04647. Dhariwal, P. and Nichol, A. (2021). Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34:8780–8794. Dmitriev, D., Huang, Z., and Wei, Y. (2026). Efficient sampling with discrete diffusion models: Sharp and adaptive guarantees. arXiv preprint arXiv:2602.15008. Fan, J., Gu, Y., and Li, X. (2025). Optimal estimation of a factorizable density using diffusion models with relu neural networks. arXiv preprint arXiv:2510.03994. Gupta, S., Cai, L., and Chen, S. (2024). Faster diffusion-based sampling with randomized midpoints: Sequential and parallel. arXiv preprint arXiv:2406.00924. Haussmann, U. G. and Pardoux, E. (1986). Time reversal of diffusions. The Annals of Probability, pages 1188–1205. Ho, J., Jain, A., and Abbeel, P. (2020). Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840–6851. Huang, D. Z., Huang, J., and Lin, Z. (2024a). Convergence analysis of probability flow ODE for score-based generative models. arXiv preprint arXiv:2404.09730.
11
Huang, X., Zou, D., Dong, H., Zhang, Y., Ma, Y.-A., and Zhang, T. (2024b). Reverse transition kernel: A flexible framework to accelerate diffusion inference. arXiv preprint arXiv:2405.16387. Huang, Z., Wei, Y., and Chen, Y. (2024c). Denoising diffusion probabilistic models are optimally adaptive to unknown low dimensionality. arXiv preprint arXiv:2410.18784. Jiao, Y. and Li, G. (2024). Instance-dependent convergence theory for diffusion models. arXiv preprint arXiv:2410.13738. Karras, T., Aittala, M., Aila, T., and Laine, S. (2022). Elucidating the design space of diffusion-based generative models. Advances in neural information processing systems, 35:26565–26577. Krizhevsky, A., Hinton, G., et al. (2009). Learning multiple layers of features from tiny images.(2009). Lee, H., Lu, J., and Tan, Y. (2023). Convergence of score-based generative modeling for general data distributions. In International Conference on Algorithmic Learning Theory, pages 946–985. PMLR. Li, G. and Cai, C. (2024). Provable acceleration for diffusion models under minimal assumptions. arXiv preprint arXiv:2410.23285. Li, G. and Cai, C. (2025). Breaking ar’s sampling bottleneck: Provable acceleration via diffusion language models. In The Thirty-ninth Annual Conference on Neural Information Processing Systems. Li, G., Cai, C., and Wei, Y. (2025a). Dimension-free convergence of diffusion models for approximate gaussian mixtures. arXiv preprint arXiv:2504.05300. Li, G., Huang, Y., Efimov, T., Wei, Y., Chi, Y., and Chen, Y. (2024). Accelerating convergence of score-based diffusion models, provably. arXiv preprint arXiv:2403.03852. Li, G. and Jiao, Y. (2024). Improved convergence rate for diffusion probabilistic models. arXiv preprint arXiv:2410.13738. Li, G., Wei, Y., Chen, Y., and Chi, Y. (2023). Towards faster non-asymptotic convergence for diffusion-based generative models. arXiv preprint arXiv:2306.09251. Li, G. and Yan, Y. (2024a). Adapting to unknown low-dimensional structures in score-based diffusion models. arXiv preprint arXiv:2405.14861. Li, G. and Yan, Y. (2024b). O(d/T ) convergence theory for diffusion probabilistic models under minimal assumptions. arXiv preprint arXiv:2409.18959. Li, G., Zhou, Y., Wei, Y., and Chen, Y. (2025b). Faster diffusion models via higher-order approximation. arXiv preprint arXiv:2506.24042. Liang, J., Huang, Z., and Chen, Y. (2025). Low-dimensional adaptation of diffusion models: Convergence in total variation. arXiv preprint arXiv:2501.12982. Nichol, A. Q. and Dhariwal, P. (2021). Improved denoising diffusion probabilistic models. In International conference on machine learning, pages 8162–8171. PMLR. Oko, K., Akiyama, S., and Suzuki, T. (2023). Diffusion models are minimax optimal distribution estimators. In International Conference on Machine Learning, pages 26517–26582. PMLR. Pope, P., Zhu, C., Abdelkader, A., Goldblum, M., and Goldstein, T. (2021). The intrinsic dimension of images and its impact on learning. arXiv preprint arXiv:2104.08894. Popov, V., Vovk, I., Gogoryan, V., Sadekova, T., and Kudinov, M. (2021). Grad-tts: A diffusion probabilistic model for text-to-speech. In International Conference on Machine Learning, pages 8599–8608. PMLR. Potaptchik, P., Azangulov, I., and Deligiannidis, G. (2024). Linear convergence of diffusion models under the manifold hypothesis. arXiv preprint arXiv:2410.09046. 12
Ramesh, A., Dhariwal, P., Nichol, A., Chu, C., and Chen, M. (2022). Hierarchical text-conditional image generation with clip latents. arXiv preprint arXiv:2204.06125, 1(2):3. Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. (2015). Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learning, pages 2256–2265. pmlr. Song, J., Meng, C., and Ermon, S. (2020a). arXiv:2010.02502.
Denoising diffusion implicit models.
arXiv preprint
Song, Y. and Ermon, S. (2019). Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32. Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. (2020b). Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456. Tang, J. and Yan, Y. (2026). Adaptivity and convergence of probability flow odes in diffusion generative models. Tang, R. and Yang, Y. (2024). Adaptivity of diffusion models to manifold structures. In International Conference on Artificial Intelligence and Statistics, pages 1648–1656. PMLR. Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press. Wang, P., Zhang, H., Zhang, Z., Chen, S., Ma, Y., and Qu, Q. (2024). Diffusion models learn low-dimensional distributions via subspace clustering. arXiv preprint arXiv:2409.02426. Wibisono, A., Wu, Y., and Yang, K. Y. (2024). Optimal score estimation via empirical bayes smoothing. arXiv preprint arXiv:2402.07747. Wu, J. and Cai, C. (2026). Diffusion models are statistically optimal for learning low-dimensional multimodal distributions. arXiv preprint arXiv:2605.30153. Wu, Y., Chen, Y., and Wei, Y. (2024). Stochastic runge-kutta methods: Provable acceleration of diffusion models. arXiv preprint arXiv:2410.04760. Yu, Y. and Yu, L. (2025). Advancing wasserstein convergence analysis of score-based models: Insights from discretization and second-order acceleration. arXiv preprint arXiv:2502.04849. Zhang, K., Yin, H., Liang, F., and Liu, J. (2024). Minimax optimality of score-based diffusion models: Beyond the density lower bound assumptions. arXiv preprint arXiv:2402.15602. Zhao, Y. and Cai, C. (2026). Adaptation to intrinsic dependence in diffusion language models. arXiv preprint arXiv:2602.20126.
A
Analysis
A.1
Preliminaries
Recall the score function can be expressed as Z √ 1 pX0 |Xt (x0 | x) x − αt x0 dx0 . s⋆t (x) = − 1 − α t x0 We define Jt (x) :=
Z Z ⊤ √ √ 1 pX0 |Xt (x0 | x) x − αt x0 dx0 pX0 |Xt (x0 | x) x − αt x0 dx0 1 − αt x0 x0 13
Z −
pX0 |Xt (x0 | x) x −
√
⊤ √ αt x0 x − αt x0 dx0 .
x0
Then the Jacobian matrix of the score function is given by 1 ∂s⋆t (x) =− I + Jt (x) . ∂x 1 − αt Next, we record several useful properties of the noise schedule (αt )t∈[T ] defined in (5) in Lemma 1. The proof can be found in Li and Cai (2024). Lemma 1. The learning rates (αt )t∈[T ] specified in (5) satisfy the following bounds for all t = 2, . . . , T : log T ; T log T 1 − αt ≤ C1 ; 1 − αt T 1 − αt log T ≤ 1 + 2C1 ; 1 − αt−1 T
(21a)
1 − αt ≤ C1
(21b) (21c)
where C0 , C1 are defined in (5). In addition, α1 satisfies 1 − α1 ≤
1 . T C1 /4
(21d)
In addition, to facilitate the main analysis, we introduce several auxiliary processes. These processes are used solely for the analysis and do not appear in the sampling algorithm. Auxiliary sequences. To begin with, we define an auxiliary reverse process (Yt⋆ )Tt=0 that uses the true score functions {s⋆t (·)}Tt=1 : 1 ⋆ := √ Yt⋆ + ηt s⋆t (Yt⋆ ) + σt Zt ; Yt−1 αt
YT⋆ ∼ N (0, Id ),
(22)
t = T, . . . , 1.
i.i.d.
where Zt ∼ N (0, Id ) is a sequence of standard Gaussian random vectors independent of (Yt⋆ )Tt=0 . − We subsequently introduce two auxiliary sequences (Y t )Tt=0 and (Y t )Tt=0 that capture the discretization error up to some low probability event. Together with YT , these two sequences form a Markov chain with the transition structure as follows: −
−
−
−
(23)
YT → Y T → Y T → Y T −1 → Y T −1 → · · · → Y 1 → Y 1 → Y 0 → Y 0 . • Initialization. For t = T , define − Y T :=
(
YT , if YT ∈ ET , ∞, otherwise.
(24a)
−
The density of Y T is given by (24b)
pY − (y) = pYT (y)1 y ∈ ET + P YT ∈ / ET δ∞ (y). T
−
−
• Transition from Y t to Y t . For t = T, . . . , 0, we define Y t as follows: conditional on Y t = y, ( y, with prob. pt (y)/pY − (y) ∧ 1, t Y t := ∞, with prob. 1 − pt (y)/pY − (y) ∧ 1 , t
14
(25a)
where we denote pt := pXbt ,
(25b)
∀t ≥ 0.
−
The conditional density of Y t given Y t = y obeys pY t |Y − (x | y) = pt (y)/pY − (y) ∧ 1 δy (x) + 1 − pt (y)/pY − (y) ∧ 1 δ∞ (x). t
t
t
(25c)
We make a critical implication of the above construction: for any t ≥ 0, the density of Y t satisfies pY t (y) = pt (y)/pY − (y) ∧ 1 pY − (y) = pXt (y) ∧ pY − (y), ∀y ∈ Rd . (26) t
t
t
−
• Transition from Y t to Y t−1 . For each t = T, . . . , 1, we first generate an intermediate random variable Yet−1 as follows: 1 Yet−1 := √ Y t + ηt s⋆t (Y t ) + σt Wt , αt
(27a)
i.i.d.
where Wt ∼ N (0, Id ), t ≥ 1 is a sequence of standard Gaussian random vectors independent of (Zt )Tt=1 , and then define ( Yet−1 , if Y t ∈ Et and Yet−1 ∈ Et , − Y t−1 := (27b) ∞, otherwise. −
The density of Y t−1 given Y t = y obeys that when y ∈ Et , ⋆ ⋆ |Y ⋆ (x | y)1 x ∈ Et pY − |Y t (x | y) = pYt−1 + P Yt−1 ∈ / Et | Yt⋆ = y δ∞ (x), t t−1
and when y ∈ / Et ,
(27c) (27d)
pY − |Y t (x | y) = δ∞ (x). t−1
Additionally, we construct two auxiliary sequences (Ybt− )Tt=0 and (Ybt )Tt=0 that form the following Markov chain: YT → YbT− → YbT → YbT−−1 → YbT −1 → · · · → Yb1− → Yb1 → Yb0− → Yb0 . (28) − • Initialization. For t = T , initialize YbT− = Y T .
• Transition from Ybt− to Ybt . For t = T, . . . , 0, the density of Ybt given Ybt− = y satisfies (29)
pYbt |Yb − (x | y) = pY t |Y − (x | y). t
t
− − • Transition from Ybt to Ybt−1 . For t = T, . . . , 1, the density of Y t−1 given Y t = y obeys: when y ∈ Et , pYb − |Ybt (x | y) = pYt−1 |Yt (x | y)1 x ∈ Et + P Yt−1 ∈ / Et | Yt = y δ∞ (x), (30a) t−1
and when y ∈ / Et ,
(30b)
pYb − |Ybt (x | y) = δ∞ (x). t−1
−
The sequences (Ybt− )Tt=0 and (Ybt )Tt=0 are constructed in the same manner as (Y t )Tt=0 and (Y t )Tt=0 , except that the transition from Ybt to Ybt− is based on estimated score functions instead of the true score functions. Moreover, we note that the density of Ybt satisfies pYbt (x) ≤ pYt (x), 15
∀x ∈ Rd ,
(31)
d
and pYbt (x) ≥ pYt (x) for x = ∞. Indeed, observe that the base case t = T is true because Ybt = Yt , which − − by (29). Next, assume that (31) holds for t + 1. Then for any results from Yb − = Y and p b b − = p T
T
Yt |Yt
x ∈ Rd , we have
Y t |Y t
Z
(i)
pYbt (x) = pXt (x)/pY − (x) ∧ 1 pYb − (x) ≤ pYb − (x) = t t t Z (ii) ≤ pYt |Yt+1 (x | y)pYt+1 (y) dy = pYt (x),
Rd
pYb − |Ybt+1 (x | y)pYbt+1 (y) dy t
Rd
where (i) applies (29) and (25c); (ii) arises from the induction hypothesis and (30a). Nε ε Auxiliary sets. Let {x⋆i }N i=1 be a ε-net of the support of the data distribution pdata , and {Bi }i=1 be the ⋆ corresponding ε-cover of the support such that xi ∈ Bi . We first define sets
I := {1 ≤ i ≤ Nε : P(X0 ∈ Bi ) ≥ exp(−θk log T )} , p √ G := ω ∈ Rd : ∥ω∥2 ≤ 2 d + θk log T , and p |(x⋆i − x⋆j )⊤ ω| ≤ θk log T ∥x⋆i − x⋆j ∥2
for all
1 ≤ i, j ≤ Nε .
where θ > 0 is a sufficiently large absolute constant. Then for each t = 1, . . . T , we define a typical set for bt as follows X √ √ αt x0 + vt ω : x0 ∈ ∪i∈I Bi , ω ∈ G , (32) Et,1 := where vt 1 . −1 ≤ 1 − αt k log T Finally, for any xt ∈ Et,1 and any r > 0, define set n o I (xt ; r) := 1 ≤ i ≤ Nε : αt ∥x⋆i − x⋆i(xt ) ∥22 ≤ r · k(1 − αt ) log T .
(33)
Next, we present several technical lemmas regarding the above auxiliary sets, which will be used in the proof of Theorem 1. Lemma 2. There exists some universal constant C1 ≫ θ such that αt P (X0 ∈ Bi | Xt = xt ) ≤ exp − ∥x⋆i(xt ) − x⋆i ∥22 P (X0 ∈ Bi ) 16 (1 − αt ) for any xt ∈ Et,1 and i ∈ / I(xt ; C1 θ). Lemma 3. There exists some universal constant C2 ≫ C1 such that for any x ∈ Et,1 , ∥Jt (x)∥ ≤ ∥Jt (x)∥F ≤ |tr(Jt (x))| ≤ C2 θk log T.
(34)
√ d √ bt = αt X0 + vt Z where Z ∼ N (0, Id ) is independent of X0 . There exists some In addition, recall that X universal constant C0 > 0 such that Z T X 1 − αt 1 − αt t=2
xt
∥Jt (xt )∥2F pXbt (xt ) dxt ≤ C0 k log T.
16
(35)
A.2
Proof of Theorems 1 and 2
By the triangle inequality, we can bound the TV distance between pY1 and pXb1 by (36)
TV pY1 , pXb1 ≤ TV(pY 1 , pXb1 ) + TV pY 1 , pY1 .
The first term represents the discretization error, up to a low probability event, since Y t is defined using the true scores. The second term accounts for the error due to score estimation. In what follows, we bound these two terms separately. To bound TV(pXb1 , pY 1 ), let us first define function ∆t (x) : Rd → R, where for each t = 1, . . . , T : (37)
∀x ∈ Rd .
∆t (x) := pXt (x) − pY t (x),
d We know from R (26) that ∆t (x) ≥ 0 for all t ≥ 0 and x ∈ R . According to the formula for the TV distance TV(p, q) = x : p(x)>q(x) p(x) − q(x) dx, one has
TV pXb1 , pY 1 =
Z Rd ∪{∞}
pXb1 (x) − pY 1 (x) 1 pXb1 (x) > pY 1 (x) dx =
Z ∆1 (x) dx.
(38)
Rd
R As a result, it suffices R to bound ∆1 (x) dx. R To this end, we establish the following lemma, which provides a recursive bound on ∆t (x) dx in terms of ∆t−1 (x) dx. Lemma 4. There exists some universal constant C3 > 0 such that for any t = 1, . . . , T , Z
Z ∆t−1 (x) dx ≤
In addition, one has
∆t (x) dx + C4 R
1 − αt 1 − αt
2 Z
tr Jt (xt ) + ∥Jt (xt )∥2F pXbt (xt ) dxt + T −3 .
Et,1
(39)
∆T (x) dx ≤ T −4 .
Applying Lemma 4 recursively yields Z
Z ∆1 (x) dx ≤
∆T (x) dx + T −2 +
T X
C4
t=2 (i)
≤ 8c1 C4
T X
1 − αt log T T t=2 1 − αt
(ii)
≤ 8c1 C4 C0
Z xt ∈Et,1
1 − αt 1 − αt
2 Z
tr Jt (xt )
xt ∈Et,1
+ ∥Jt (xt )∥2F pXbt (xt ) dxt
∥Jt (xt )∥2F pXbt (xt ) dxt + 64c21 C4
θk log3 T + T −3 T
2
(iii) k log T θk log3 T k log3 T + 64c21 C4 + T −3 ≤ C5 . T T T
(40)
Here, (i), (ii) applies Lemma 3, and (iii) holds as long as C5 is chosen sufficiently large. Consequently, we b1 and Y 1 as can bound the TV distance between X Z TV(pXb1 , pY 1 ) = pXb1 (x) − pY 1 (x) dx pX c (x)>pY (x) 1
1
Z =
∆1 (x) dx ≤ C5
k log3 T . T
Next, we turn to the term TV pY 1 , pY1 . By standard calculations, we have Z pY 1 (x) − pY1 (x) 1 pY 1 (x) > pY1 (x) dx + P Y 1 = ∞ TV pY 1 , pY1 = Rd Z (i) ≤ pY 1 (x) − pYb1 (x) 1 pY 1 (x) > pYb1 (x) dx + P Y 1 = ∞ Rd
(ii)
≤ TV pY 1 , pYb1 + TV pX1 , pY 1 17
(41)
(iii) q
≤
k log3 T KL pY 1 ∥ pYb1 + O . T
(42)
where (i) arises from (31) that pY1 (x) ≥ pYb1 (x) for any x ∈ Rd ; (ii) uses P{Y 1 = ∞} ≤ TV(pXb1 , pY 1 ) since b1 ∈ Rd ; (iii) applies Pinsker’s inequality and (41). X To bound the right hand side of (42), it is sufficient to control KL pY 1 ∥ pYb1 . To this end, observe that (i) KL pY 1 ∥ pYb1 ≤ KL pY − ,Y T ,...,Y − ,Y 1 ∥ pYb − ,YbT ,...,Yb − ,Yb1 T
(ii)
= KL pY − ∥ pYb − + +
T X
=
h
Ext ∼pY − KL pY t |Y − =xt ∥ pYbt |Yb − =xt
h Ext ∼pY
t
h Ext ∼pY
KL pY − |Y t =xt ∥ pYb − |Ybt =xt
t
i
t−1
t−1
KL pY − |Y t =xt ∥ pYb − |Ybt =xt
i
(43)
.
t−1
t−1
t=2
i
t
t
t
t=1
t=2 T (iii) X
T X
T
T
1
T
1
Here, (i) applies the data-processing inequality; (ii) uses the chain rule of KL divergence and the Markov − property; (iii) is true since we initialize YbT− = Y T and the transition kernels from Ybt− to Ybt are the same as − those from Y t to Y t for all t ≥ 1. σ2 ⋆ Observe that Yt−1 | Yt⋆ = xt ∼ N √1αt xt + ηt s⋆t (xt ) , αtt Id and Yt−1 | Yt = xt ∼ N √1αt xt + σ2 ⋆ |Y ⋆ =x (·) and q(·) = pY (·). Then by the ηt st (xt ) , αtt Id . For any xt ∈ Et , let us denote p(·) = pYt−1 t−1 |Yt =xt t t definitions (30a) and (25c), we have R Z p(x) dx Z p(x) Ec KL pY − |Y t =xt ∥ pYb − |Ybt =xt = p(x) log p(x) dx. (44) dx + log R t t−1 t−1 q(x) q(x) dx Etc Et Ec t
Applying Li and Yan (2024b, Lemma 6) gives Z
KL pY − |Y t =xt ∥ pYb − |Ybt =xt ≤
p(x) log
t−1
t−1
Rd
p(x) dx q(x)
⋆ |Y ⋆ =x ∥ pY = KL pYt−1 t−1 |Yt =xt t t
(i)
=
ηt2 2 st (xt ) − s⋆t (xt ) 2 2 2σt
(ii) log T
≲
T
2
st (xt ) − s⋆t (xt ) 2 .
(45)
Here, (i) uses the formula of the KL divergence for two normal distributions; (ii) holds because ηt = O(1−αt ), σt2 = Ω(1 − αt ), and 1 − αt = O(log T /T ). In addition, for any xt ∈ Etc , (30b) implies that KL pY − |Y t =xt ∥ pYb − |Ybt =xt = 0. (46) t−1
t−1
Combining the above with (43), we find T h (i) X i KL pY 1 ∥ pYb1 ≤ Ext ∼pt KL pY − |Y t =xt ∥ pYb − |Ybt =xt t−1
t=2 T Z (ii) log T X
≲
T
t=2
Rd
t−1
(1 − αt )∥st (xt ) − s⋆t (xt )∥22 pXbt (xt ) dxt
(iii)
(47)
= ε2sc log T, 18
where (i) arises from (46) and (26) that pY t (x) ≤ pt (x) for all x ∈ Rd ; (ii) uses (45). Substituting (47) into (42) leads to p k log3 T + εsc log T . (48) TV pY1 , pY 1 ≲ T Finally, combining (41) and (48) yields p k log3 T TV(pXb1 , pY1 ) ≤ C + εsc log T . T
B
Proof of lemmas and corollaries
B.1
Proof of Lemma 2
Notice that P(X0 ∈ Bi | Xt = xt ) ≤
P(X0 ∈ Bi ) exp(−
√ 2 ∥xt − αt x⋆ i∥ ) 2(1−αt ) √ ∥xt − αt x⋆ ∥2 i(x )
t P(X0 ∈ Bi(xt ) ) exp(− ) 2(1−αt ) αt ≤ exp ∥x⋆i − x⋆i(xt ) ∥2 + θk log T P(X0 ∈ Bi ), 4(1 − αt )
where the second line holds according to the definition (32) that √ √ √ √ ∥xt − αt x⋆i ∥2 − ∥xt − αt x⋆i(xt ) ∥2 = αt ∥x⋆i − x⋆i(xt ) ∥2 − 2 αt (x⋆i − x⋆i(xt ) )⊤ (xt − αt x⋆i(xt ) ) αt ⋆ ≥ ∥x − x⋆i(xt ) ∥2 . 2 i
B.2
Proof of Lemma 3
Notice that for x ∈ Et,1 , √ αt x0 ∥2 exp − ∥x− pX0 |Xt (x0 | x) pX0 (x0 ) 2(1−αt ) √ = · pX0 |Xt (x0 (x) | x) pX0 (x0 (x)) exp − ∥x− αt x0 (x)∥2 2(1−αt )
√ √ pX0 (x0 ) αt ∥x0 − x0 (x)∥2 − 2 αt (x0 − x0 (x))⊤ (x − αt x0 (x)) · exp − = pX0 (x0 (x)) 2(1 − αt ) √ 2 pX0 |Xbt (x0 | x) exp − ∥x− 2vαtt x0 ∥ pX0 (x0 ) √ = c(x0 ; x) = c(x0 ; x) · , 2 ∥x− α x (x)∥ t 0 pX0 (x0 (x)) exp − pX0 |Xbt (x0 (x) | x)
2vt
where 34 < c(x0 ; x) < 43 for αt ∥x0 − x0 (x)∥2 ≲ k(1 − αt ) log T . This implies that pX0 |Xt (x0 | x) = R
pX0 |Xt (x0 | x) pX0 |Xt (x′0 | x)dx′0
pX0 |Xt (x0 | x)/pX0 |Xt (x0 (x) | x) p (x′0 | x)/pX0 |Xt (x0 (x) | x)dx′0 αt ∥x′ −x0 (x)∥2 ≲k(1−αt ) log T X0 |Xt
≤R
0
<
16pX0 |Xbt (x0 | x)/pX0 |Xbt (x0 (x) | x) 9 αt ∥x′ −x0 (x)∥2 ≲k(1−αt ) log T pX0 |Xbt (x′0 | x)/pX0 |Xbt (x0 (x) | x)dx′0 R
0
=
16pX0 |Xbt (x0 | x) 9(1 − exp(−Ω(k log T )))
< 2pX0 |Xbt (x0 | x).
Recall that 0 ⪯ −Jt (x) ⪯
1 1 − αt
Z
Z √ pX0 |Xt (x0 | x) x − αt x0 −
x0
x0
19
pX0 |Xbt (x0 | x) x −
√
αt x0 dx0
x−
√
√
Z α t x0 − x0
⪯
1 1 − αt
Z
⊤
pX0 |Xbt (x0 | x) x − αt x0 dx0 dx0 Z √ √ pX0 |Xt (x0 | x) x − αt x0 − pX0 |Xbt (x0 | x) x − αt x0 dx0
αt ∥x0 −x0 (x)∥2 ≲k(1−αt ) log T
x−
√
x0
√
Z α t x0 − x0
pX0 |Xbt (x0 | x) x −
⊤
αt x0 dx0
dx0
+ exp(−Ω(k log T )).
As a result, one has 2 −Jt (x) ⪯ 1 − αt
Z x0
Z √ pX0 |Xbt (x0 | x) x − αt x0 −
x0
Z √ x − α t x0 − x0
pX0 |Xbt (x0 | x) x −
pX0 |Xbt (x0 | x) x −
√
αt x0 dx0
√
αt x0 dx0
⊤
dx0
+ exp(−Ω(k log T ))
=: −2Jbt (x) + exp(−Ω(k log T )).
B.3
Proof of Lemma 4
Observe that pXbt−1 (xt−1 ) − ∆t−1 (xt−1 ) + ∆t→t−1 (xt−1 ) √ Z 2 −1 α d/2 αt xt−1 − ut ηt t ≥ det I − (I + Jt (xt )) dut . pXbt (xt ) exp − 1 − αt 2πσt2 2σt2 xt ∈Et (xt−1 )
(49)
bt−1 admits the following expression: Notice that the density of X Z pXbt−1 (xt−1 ) =
ut
Z x0
η t 2 2πvt 1 − 1 − αt
−d/2
√ ∥ut − αt x0 ∥2 pX0 (x0 ) exp − ηt )2 vt 2(1 − 1−α t
√ 2 α d/2 αt xt−1 − ut t · exp − dx0 dut . 2πσt2 2σt2
Here we apply the change of variable ut = xt + ηt s⋆t (xt ). In addition, we claim that Z ∥x − √α x ∥2 −1 −d/2 ηt t t 0 det I − 2πvt pX0 (x0 ) exp − (I + Jt (xt )) dx0 1 − αt 2vt x0 Z ∥u − √α x ∥2 ηt 2 −d/2 t t 0 = 2πvt 1 − pX0 (x0 ) exp − dx0 ηt 1 − αt 2(1 − 1−α )2 vt x0 t 1 − α 2 t 2 · exp − ξt (xt ) + O k log T + ∥Jt (xt )∥F , αt − αt where ξt (xt ) ≤ 0 satisfies Z 1 − α 2 Z t |ξt (xt )|pXbt (xt )dxt ≤ C3 k log T + ∥Jt (xt )∥2F pXbt (xt )dxt + T −4 1 − αt xt ∈Et,1 xt ∈Et,1 for some universal constant C3 > 0. Then the result follows from Lemma 3. Proof of Claim (50).
Notice that
√ √ √ ηt ηt αt x0 ∥22 ∥ut − αt x0 ∥2 ∥xt − αt x0 ∥22 1−αt (2 − 1−αt )∥xt − = + ηt ηt 2 2 2(1 − 1−αt ) vt 2vt 2(1 − 1−αt ) vt 20
(50)
(51)
√ ηt2 ∥s⋆t (xt )∥22 ηt s⋆t (xt )⊤ (xt − αt x0 ) + ηt ηt 2 )2 vt (1 − 1−αt ) vt 2(1 − 1−α t √ Z ηt ηt (2 − 1−α ) √ ∥xt − αt x0 ∥2 t = pX0 |Xt (x0 | xt )∥xt − αt x0 ∥22 dx0 + 1−αt ηt 2 2vt 2(1 − 1−αt ) vt x0 Z ηt ηt 2 (2 − 1−αt ) √ p (x | x ) x − α x + ζt (xt , x0 ), − 1−αt dx 0 t t t 0 0 X |X ηt 0 t 2(1 − 1−α ) 2 vt x0 2 t +
where we let √ √ ηt ηt αt x0 ∥22 − x0 pX0 |Xt (x0 | xt )∥xt − αt x0 ∥22 dx0 1−αt (2 − 1−αt ) ∥xt − ζt (xt , x0 ) := ηt 2(1 − 1−α ) 2 vt t ⊤ √ R R √ ηt αt x0 − x0 pX0 |Xt (x0 | xt )x0 dx0 p (x0 | xt ) xt − αt x0 dx0 1−αt x0 X0 |Xt . + ηt (1 − 1−α )2 vt t
R
(52)
Then √ √ ∥ut − αt x0 ∥2 ∥xt − αt x0 ∥2 ηt = + log det I − J (x ) t t ηt 2(1 − 1−αt )2 vt 2vt 1 − α t − ηt 1 − α 2 t |Tr(Jt (xt ))| + ∥Jt (xt )∥2F , + ζt (xt , x0 ) + O αt − αt since ηt ηt 1 − α 2 ηt t 1−αt (2 − 1−αt ) = + O . ηt 2v 2(1 − 1−α ) 1 − α − η α − α t t t t t t
B.4
Proof of Corollary 1
Through basic algebra, it can be checked that all the choices of coefficients in (8) satisfy σt2 = αt − αt − 1 −
(1 − α )2 η t 2 t (1 − αt ) + O . 1 − αt 1 − αt
Then we have vt−1 = αt
1 − α
t−1
2
1 − αt
vt +
(1 − α )2 (1 − αt )(1 − αt−1 ) t +O , 1 − αt 1 − αt
which gives vt = 1 − α t +
T X α i 1 − α t 2 i=t+1
αt 1 − αi
·O
(1 − α
i−1 ) log T
T
log2 T = (1 − αt ) · 1 + O , T
log T t provided that 1−α 1−αt ≲ T . As a result, we conclude
|δt | ≲
B.5
log2 T . T
Proof of Corollary 2
Consider ηt⋆ := 1 − αt ,
σt⋆ =
21
r
αt − αt (1 − αt ). 1 − αt
(53)
Denote vt⋆ as the effective noise level in (11) induced by schedule αt . For t = T , we have vT⋆ = 1 − αT and δT = 0. we prove δt = 0 immediately by induction and verifying that 1 − α t 2 αt − αt ηt⋆ 2 ⋆ vt + (σt⋆ )2 = 1 − (1 − αt ) + (1 − αt ) 1− 1 − αt 1 − αt 1 − αt (αt − αt )2 αt − αt = + (1 − αt ) 1 − αt 1 − αt αt − αt (αt − αt + 1 − αt ) = 1 − αt ⋆ . (54) = αt (1 − αt−1 ) = αt vt−1 b1 = X1 and establish (18). By Theorem 1, we have X Next we intend to prove that there exists a learning rate schedule αt′ satisfying 1 − αt (1 + δt′ )(1 − α′t ) = , αt α′t
(55)
1 ≤ t ≤ T.
Denote vt as the effective noise level in (11) induced by schedule αt′ . Then we have the following equation b′ √ √ X 1 p = X1 = α1 X0 + 1 − α1 Z1 , ′ ′ ′ α1 + (1 + δ1 )(1 − α1 )
(56)
since √
q p α1′ X0 + (1 + δ1′ )(1 − α1′ )Z1 q √ √ = α1′ + (1 + δ1′ )(1 − α1′ ) α1 X0 + 1 − α1 Z1 .
b1′ = X
p
α1′ X0 +
v 1 Z1 =
Then we have TV pX1 , pYb1 = TV pXb ′ /√α′ +(1+δ′ )(1−α′ ) , pYb1 = TV(pXb ′ , pY1′ ) 1
1
1
1
1
and by applying Theorem 1, we complete the proof. Now it suffices to prove that there exists αt′ satisfying (55). We prove this by induction. Given α′t and vt obeying vt =
α′t (1 − αt ) . αt
(57)
We need to show the existence of α′t (or αt′ equivalently) such that the above relation holds also for t − 1. Recall that 2 ηt′ ′ αt vt−1 = 1 − vt + (σt′ )2 . (58) 1 − α′t For fixed α′t and vt , we treat vt−1 as a continuous function of αt′ , and examine its values at two specific values of αt′ in the following. • When αt−1 = αt , we have ηt′ = O(1 − αt′ ) = 0 and (σt′ )2 = 1 − α′t − (1 − α′t ) = 0. Thus we have vt−1 = vt = Recall that α1 satisfy
α′ (1 − αt ) α′ (1 − αt−1 ) α′t (1 − αt ) = t−1 ≥ t−1 . αt αt αt−1 1 − α1 C1 log T ≤ . 1 − α1 T 22
• When
C2 log T (t) (1 − αt ), T with C2 ≥ 3C1 is a sufficiently large constant, we intend to prove that αt′ = 1 −
vt−1 ≤
α′t−1 (1 − αt−1 ) . αt−1
(59)
Towards this, we insert ηt′ = O(1 − αt′ ) and (19) into (58) and obtain αt′ vt−1 =
ηt′ 1 − α′t
2
ηt′ 1− 1 − α′t
2
1−
=
vt + (σt′ )2 (vt − 1 + α′t ) + αt′ − α′t + O
ηt′ 1 − α′t (1 − α′ )2 t +O . 1 − α′t
= vt − 1 + α′t +
1−
2
(1 − α′ )2 t
1 − α′t
− 1 (vt − 1 + α′t ) + αt′ − α′t (60)
1−α′
T Recall that 1−αt′ = C2 log , we have T t
2 2 (1 − αt′ )2 ′ C2 log T = (1 − α ) , t 1 − α′t T2 2 2 ηt′ 2ηt′ ηt′ 1− 1− ≤ + 1 − α′t 1 − α′t 1 − α′t 2 ! 1 − αt′ log T 1 − αt′ + O = O , =O 1 − α′t 1 − α′t T log2 T vt − 1 + α′t = O (1 − α′t ) . T
Combining all of these into (60), we have log T log2 T O (1 − α′t ) T T 2 log T + αt′ − α′t + O (1 − α′t ) T2 3 ′ ′ log T = vt − 1 + αt + O (1 − αt ) . T2
αt′ vt−1 = vt − 1 + α′t + O
We can establish (59) by verifying that α′t−1 (1 − αt−1 ) αt−1 log3 T α′ (1 − αt−1 ) = vt − 1 + αt′ + O (1 − α′t ) − t 2 T αt−1 3 ′ αt (1 − αt ) ′ ′ log T = − 1 + αt + O (1 − αt ) αt T2 ′ 3 ′ αt (1 − αt ) 1 − αt 1 − αt ′ ′ log T = (1 − αt ) − + O (1 − αt ) ≤ 0, (1 − α′t )αt 1 − αt 1 − α′t T2
αt′ vt−1 − αt′
23
(61)
where the last inequality comes from α′t (1 − αt ) 1 − αt 1 − αt′ C1 log T α′t (1 − αt ) C2 log T − ≤ − (1 − α′t )αt 1 − αt 1 − α′t T (1 − α′t )αt T C1 log T α′t (1 − αt ) C2 log T vt = − T (1 − α′t ) vt α t T C1 log T C2 log T C1 log T = (1 + δt′ ) − ≤− . T T T T By mean value theorem, we conclude that there exists αt′ ∈ [1 − C2 log (1 − α′t ), 1], such that (57) holds for T t − 1.
24