Broadening Target Distributions for Accelerated Diffusion Models via a Novel Analysis Approach
Authors: Yuchen Liang
Peizhong Ju
Yingbin Liang
Ness Shroff
Venue: ICLR 2025 Poster (2025)
Keywords: generative models
denoising diffusion probabilistic model (DDPM)
convergence analysis
accelerated methods
Primary area: learning theory

Abstract: Accelerated diffusion models hold the potential to significantly enhance the efficiency of standard diffusion processes. Theoretically, these models have been shown to achieve faster convergence rates than the standard $\mathcal O(1/\epsilon^2)$ rate of vanilla diffusion models, where $\epsilon$ denotes the target accuracy. However, current theoretical studies have established the acceleration advantage only for restrictive target distribution classes, such as those with smoothness conditions imposed along the entire sampling path or with bounded support. In this work, we significantly broaden the target distribution classes with a new accelerated stochastic DDPM sampler. In particular, we show that it achieves accelerated performance for three broad distribution classes not considered before. Our first class relies on the smoothness condition posed only to the target density $q_0$, which is far more relaxed than the existing smoothness conditions posed to all $q_t$ along the entire sampling path. Our second class requires only a finite second moment condition, allowing for a much wider class of target distributions than the existing finite-support condition. Our third class is Gaussian mixture, for which our result establishes the first acceleration guarantee. Moreover, among accelerated DDPM type samplers, our results specialized for bounded-support distributions show an improved dependency on the data dimension $d$. Our analysis introduces a novel technique for establishing performance guarantees via constructing a tilting factor representation of the convergence error and utilizing Tweedie's formula to handle Taylor expansion terms. This new analytical framework may be of independent interest.

Published as a conference paper at ICLR 2025
BROADENING TARGET DISTRIBUTIONS FOR ACCELER- ATED DIFFUSION MODELS VIA A NOVEL ANALYSIS APPROACH
Yuchen Liang', Peizhong Ju
Yingbin Liang!, Ness Shroff
'hee Ohio State University UUniversity of Kentucky
ABSTRACT
Accelerated diffusion models hold the potential significantly enhance the ef- ficiency of standard diffusion processes. Theoretically. these models have been shown to achieve faster convergence rates than the standard (1)/²²) rate of vanilla diffusion models, where denotes the target accuracy. However, current theoretical studies have established the acceleration advantage only for restrictive target distri- bution classes, such those with smoothness conditions imposed along the entire sampling path or with bounded support. In this work, we significantly broaden the target distribution classes with new accelerated stochastic DDPM sampler. In particular, we show that it achieves accelerated performance for three broad distribution classes not considered before. Our first class relies on the smoothness condition posed only to the target density go. which is far more relaxed than the existing smoothness conditions posed to all q: along the entire sampling path. Our second class requires only a finite second moment condition, allowing for a much wider class of target distributions than the existing inite-support condition. Our third class is Gaussian mixture, for which our result establishes the first accelera- tion guarantee. Moreover, among accelerated DDPM type samplers, our results specialized for bounded-support distributions show improved dependency on the data dimension d. Our analysis introduces novel technique for establishing performance guarantees via constructing a tilting factor representation of the con- vergence error and utilizing Tweedie's ' formula to handle Taylor expansion terms. This new analytical framework may be of independent interest.
INTRODUCTION
Generative modeling is a fundamental task in machine learning, aiming to generate samples out of a distribution similar to that of training data. Classical generative models include variational autoencoders (VAE) (Kingma Welling 2022), generative adversarial networks (GANs) (Goodfellow et all]][2011 20144, and normalizing flows Rezende & Mohamed] (2015), etc. Recently, diffusion models (Sohl-Dee -Sch--Dickstein et al.) 2015 Ho et al. 2020; Song & Ermon 2019) have arisen as an appealing generative model and have received wide popularity due to their excellent performance over variety of tasks and applications as summarized in many surveys of diffusion models (Yang et al.) 2023
Croitoru al. 2023 Kazerouni al., 2023).
The empirical success of diffusion models has also inspired extensive theoretical studies, aiming to characterize the convergence guarantee for diffusion models. The convergence rate (i.e., the total number of steps to attain a target accuracy E) for standard vanilla Denoising Diffusion Probabilistic Models (DDPMs) has been established to be O( for wide classes of target distributions (Chen et al, 2023a Benton et al., 2024a Conforti et al. 2023) (see Appendix A for a more complete summary). More recently, various accelerated samplers have been proposed and been shown to achieve an improved convergence rate of (c=-)). One such acceleration approach is to redesign the (stochastic) DDPM reverse process. This includes augmenting the original reverse process with an additional estimate (Li et al. 2024c). introducing intermediate sampling points along the generation path (Li al. 2024a). and employing special Markov-chail Monte-Cart (MCMC) algorithms
(Huang et al.) 2024b). Another acceleration method is to sample with the corresponding probability
ODE (Li et al. 2024c Chen et al. 2023c Huang al. 2024a Li al. 2024d)

---

Published as a conference paper at ICLR 2025
Target distribution Qo
Method
Num of steps
Results
V log yt, 8t I.-Lips. Vt
ODE-based
vär. e VaL e
(Chnn et al.
2023c
Thm 3)
V loog q: L-Lips. vt
DDPM accl.
O
(Huang et al.
2024b
Thm 4.4)
(0));(r) < Vx,t,a a and Ak S + 1, Qo Bounded Support
ODE
(uaag et al.
2024a
Thm 3.10)
2 log qo M M-Lips.
DDPM accl.
o
d' log
M
(This paper, Thm 4
Qo Gaussian Mixture
DDPM accl.
o
df
(This paper, Thm 2
DDPM accl.
o
dat
Li al.
2024c
Thm 4)
Li al.
2024a
Thm 2)1
Qo Bounded Support
ODE
da
Lr al.
2024c
Thm 2)
Li al.
2024a
Thm I
ODE
da
(Li et al.
2024c
Thm 1)
dl.s
Qo Finite Variance
DDPM accl.
(This paper, Thm
3
Summary of accelerated convergence results in terms of the number of steps needed to achieve E-accuracy in total variation, where d is the dimension. For Gaussian mixture, assume that N S d. The first rows of this table correspond to the results under those target distributions with some smoothness conditions imposed, while the last 4 rows correspond to the results under (possibly) non-smooth targets with finite variance. (*) Those results correspond to an early-stopped procedure that compares the sampling distribution to Q1)6), where W2 (Qu, Q1)² E 5d. Here the dependencies on are omitted. (t) Those studies are concurrent to our work based on the time that they were posted on arXiv. Note that this lable does not include the studies within two months of the conference submission, but those are discussed in the related works.
Table 1:
However, existing results on the acceleration guarantee suffer from strong assumptions on the target distribution. (i) For smooth target distributions, the analyses of Chen et al. (2023c); Huang et al. (2024a b) require that all the scores (or their close estimates or both) satisfy certain Lipschitz-smoote condition along the entire sampling path, i.c., the smoothness condition is posed to the density 9: for all iteration time f. However, such smoothness at intermediate steps is generally restrictive and hard to verify in practice. (ii) For (possibly) non-smooth targets, the analysis of et al. (2024a d) requires the distribution to have finite support for early-stopped sampling procedures. Such an assumption is, however, restrictive if compared to that for early-stopped vanilla samplers, where convergence guarantees have been established only under the assumption of finite variance (Chen et al. 2023a Benton et al. 2024a). The above discussions raise the following important open question:
Question I: Can we obtain an accelerated convergence rate for a much broader set of target distributions? ? Namely, for smooth target distributions, can the smoothness condition be imposed only the target distribution; and for (possibly) non-smooth targets, can we broaden the target distribution to only have finite variance?
Further, the existing accelerated diffusion samplers suffer high dimensional dependencies as O (d8) or O (d2) et al. 20244 c) for target distributions with bounded support. This motivates us explore the following intriguing question:
Question 2: While addressing Question to relax the assumption from finite support to finite variance for possibly non son-shooh distributions, can we achieve lower dimensional dependency?
This paper will provide affirmative answers to both of the above questions.
1.1 OUR CONTRIBUTIONS
Our main contribution is to provide accelerated convergence results for significantly wider range of distributions than those addressed in previous works (see Table [ (particularly column 1) for a comparison). To this end, design new accelerated stochastic DDPM sampler and develop novel analytical technique that characterizes its acceleration guarantees across this broader spectrum of distributions. Our detailed contributions are summarized as follows.
2

---

Published as a conference paper at ICLR 2025
Broadening Target Distributions: Inspired by optimization methods, design new Hessian- based accelerated sampler for the stochastic diffusion processes. We show that our accelerated sampler achieves an accelerated convergence rate of O (d'-5 mij (.).//))).................
/s). O (d). and O (dd.5 log!.5 M/e) respectively for Gaussian mixtures, any target distributions having finite variance (with early-stopping). and any target distributions having M M-Lipschitz Hessian of log-densities. In particular, (i) for smoothness Qu that has p.d.f., the smoothness condition is only imposed on the log-density of Qo. which is much less restrictive than that imposed on all Q 's (Chen et al.] [203c] Huang et 2024a b): (ii) for possibly non-smooth Qo. we only require Qo to have finite variance for the early-stopped procedure, which is much broader class of distributions than those having bounded support (Li et al. 2024a d): (iii) we provide the first accelerated convergence result for Gaussian mixture Qo
For possibly non-smooth targets with bounded support, our sampler improves the dependency of the convergence rate on d by O (d'-s) compared with previous accelerated diffusion samplers (Li et al.
c
Novel Analysis Technique: We develop a novel technique for analyzing the accelerated DDPM process. Our approach features two new elements: (i) characterization of the error incurred at each discrete step of the reverse process using tilting factor; and (ii) analysis of the mean value of tilting factor via Tweedie's 's formula to handle power terms in the Taylor expansion. Such technique enables us to (a) analyze more general distributions beyond those with restrictive distribution assumptions; (b) tightly identify the dominant term and reduce the dimensional dependency; and (c) handle the estimation error in accelerated samplers for both score and Hessian estimation. This analytical framework is different from the main previous theoretical techniques for analyzing the convergence of diffusion models: (a) the SDE-type analysis for regular diffusion samplers (Chen et al., 2023a
Benton al. 2024a Conforti et al. 2023), (b) any ODE-type analysis (Li et al. 2024d
Huang et al.
2024a Gao & Zhu 2024), and (c) the use of typical sets (Li et al. 2024a
1.2 RELATED WORKS ON ACCELERATED SAMPLING
Here, we focus on the related studies of accelerated samplers. Note that all of these works we discuss below, only except[Chen
al. (2023c c): Li al. (2024c), are concurrent to or after ours based on their posting time on arXiv. In Appendix A we provide a thorough summary of convergence analysis of standard samplers as well as other theoretical perspectives of diffusion models.
Accelerated Stochastic Samplers: In Li et al. 2024c), accelerated stochastic variants to the original DDPM sampler are proposed and analyzed, when there is no estimation error. In al. (2024a), a new accelerated stochastic sampler are proposed by inserting intermediate sampling points along the diffusion path. Both algorithms are analyzed only when the target distribution has bounded support and suffer from large dimensional dependencies. In Huang et al. (2024b), the authors proposed the RTK- -MAA and RTK-ULD algorithms which uses MCMC algorithms, such as the Metropolis- adjusted Langevin Algorithm the Underdamped Langevin Dynamics, each diffusion step. The analysis is performed under the assumption that all the scores of log q 's are Lipschitz-smooth In comparison, our work substantially broadens the set of target distributions to include those with unbounded support and with smooth log-density only imposed upon Qo with a completely different analytical technique. Our result also improves the dimensional dependencies of accelerated stochastic samplers in Li ct al. 22024 for distributions with bounded support.
Deterministic Samplers: Beyond stochastic samplers, another line of research to achieve an accel- erated convergence rate is to sample from the corresponding probability flow ordinary differential equation (PF-ODE). Early work provided polynomial guarantees under rather restrictive Lipschitz conditions Chen et al. (2023e). Later in Chen et al. (2023c), an accelerated convergence rate was first derived with the DPUM sampler by mixing the deterministic predictor steps with stochastic corrector steps. The analysis was performed under the assumption of Lipschitz V log q 's and 8, 's. Note that this assumption is relatively restrictive and hard to verify in practice. After that, for target distributions having bounded support, [L et al. (2024c) provided the first analysis of purely deter- ministic sampler (along with an accelerated deterministic sampler), albeit with a high dimensional dependency. Recently, under strong assumptions on 8 ss |Huang al. (2024a) provided acceler- ated rate using the p-th order Runge-Kute Kutta time integrator for ODBs for those target distributions
A Ahhough the technique in Huang et al. 2024a) may be applied to Gaussian mixtures, the authors do not provide explicit dependencies in their paper. Also, Huong et al. (2024)) is posted arXiv after our first draft.
3

---

Published as a conference paper at ICLR 2025
having bounded support. Specifically, for first-order Runge- Kutta methods, it is assumed that the first two orders of partial derivatives of st 's are uniformly bounded in space and time, which implies of 8 and its derivative along the entire sampling path. Most recently, Li et al. (024d) obtained a linear convergence rate both in and 5 using PF-ODEs as long as 8t 's (and their derivatives) well estimated. However, it is analyzed only bounded-support targets. Beyond these works, further acceleration to deterministic samplers is sought in Li et al. (2024a c) that gives the convergence rate of O(E 1/2), which are still performed under -uunded-support targets. In comparison, our work substantially broadens the target distributions include those with unbounded support (yet with finite variance) while achieving an accelerated convergence rate.
Sonschizz-smoothnee
2 PRELIMINARIES OF DDPM
In this section, we provide the background of the DDPM sampler (Ho et al. 2020
2.1 FORWARD PROCESS
Let 20 Rd be the initial data, and let o; E ER / algorithm. Let Qo be the initial data distribution, and let Qt be the marginal latent distribution at time in the forward process, for all 1 1 < T. In the forward process, white Gaussian noise is
{1, .,...,, T be the latent variables in the diffusion
.l....,T]
gradually added to the data: x, = v1 3, + + Vt E {l...., T). where wi Equivalently, this can be expressed as a conditional distribution at each time t:
f.4.d. NO
Q = (1 vI - 11--11--11 -1
1, Bela),
(1)
which means that under Q, Xo + X1 + ..... + Xr. Here Br E (0, 1) captures the "amount" of noise that is injected at time t, and 3r's are called the noise schedule. Define
a₂ = Be, ā :===1lmm ai 1stsT.
An immediate result by accumulating the steps that
Qepo(1s/ = -N(x; (aliivaaa Vaizu, (1 - da)
(2)
or, written equivalently, 2, = V + VI- Wg Vt E (I...., ,T), where N Ia) denotes the aggregated noise at time t. Intuitively, for large T, since Qrjo R NN, Ia) (which is independent of zg), it expected that Qr (O, Ia) when T becomes large, long as the variance under Qo is finite. Finally, since the conditional noises are Gaussian, each Qi 2 1) is absolutely continuous w.r.t the Lebesgue measure. Let the corresponding p.d.f. of each Q, be qe 2 1). Similarly define ft.t11. 9eje-1, and q-1|/ for & > 1. In case Qo is also absolutely continuous w.r.t. the Lebesgue measure, let go be the corresponding p.d.f. of Qo.
2.2 REGULAR REVERSE PROCESS
The goal of the reverse sampling process is to generate samples approximately from the data distribution Qo- We first draw the latent variable at time T from Gaussian distribution: or (O =; Pr. Then, to achieve effective sampling, each forward step is approximated by a reverse sampling step, in which the mean matches the posterior mean of Qt-1jt- Define
(xa)
1 (z+ + (1 o:)) log (: (xx)) fou
Here V log (x) is called the score of qt, which can be estimated via training process called score matching.
each time T, 1.... 1. the true regular reverse process is defined as _t-1 = (2,) + o,2, where ~ A(0, Ia). Two choices of of are commonly used in practice, where of = 1 a or of -- ax), and similar results 2020). Let P. be the marginal distributions of o, in the true regular reverse process, and let Pr be the corresponding f.d.f. of P, w.r.t. the Lebesgue measure.
reported for these choices (Ho et al.
2.3 METRICS
In case where Q is absolutely continuous w.r.t. the Lebesgue measure, we are interested in measuring the mismatch between Q and P through the total-variation distance, defined
TV(Q, P) == SUPAC IQ(A) P(A))
4

---

Published as a conference paper at ICLR 2025
where ((R") contains all Borel- measureable sets in R This metric is commonly used in prior theoretical studies (Chen et al. 2023a). From Pinsker's s inequality, the total-variation (TV) distance is upper bounded TVQQ, & [LLP)))) where the KL divergence is defined as KL(Q]IP) := log de dQ 2 O. Thus, we control the KL divergence when Q is absolutely continuous w.r. P.
When 90 does not exist (say, when Qo has point masses), we the Wasserstein distance to measure the mismatch at = 0. namely W2(Qu. Q1). which is a technique commonly adopted (Chen et al. 2023a; Benton al. (0024)). The Wasserstein-2 distance is defined Wz(Qo. Q1)
V Vminrem(Q..Q SuexR I || y/ dI y), where I1(Qu, Q1) is the set of all joint probability measures on Idd x IRd with marginal distributions Qo and Q1 respectively.
ACCELERATED DIFFUSION SAMPLER
To generate samples from the data distribution Qo. the idea of DDPM is to design a reverse process in which each reverse sampling step well approximates the corresponding forward step. Below, we propose new accelerated sampler along with a new variance estimator, in which both the conditional mean and variance of the reverse process match the corresponding posterior quantities.
3.1 ACCELERATED REVERSE PROCESS
At each time t = T,T 1,..., 1, define the true accelerated reverse process as ž₁-1 = Me(x)) +
Σ/ (zz)z, where is defined in 3 ~ (0, Ia). and (cf. Lemma 8
Ex(r)) == l-at (I& + (1 a.) log (e(z)))
(4)
aa
Let P/ be the marginal distributions of 2, in the true accelerated reverse process, and let p/ be the corresponding p.d.f.. Thus, the transition kernel can be written as P/ (2( P4 (zze, Eg (xx)), and we let Py == Pf (0, Ta). When (1 az) is vanishing for large T, E,, > 0 for all large T's, and thus the conditional Gaussian process is well-defined The above accelerated sampler has a close relationship to Ozaki's ' discretization method to approximate a continuous stochastic
process (Ozaki 1992. Shoji 1998 Stramer & Tweedie 1999).
In practice, one has no access to either V log de or 2 log 4:- Thus, their estimates, denoted as 8, and H,, are used. Define the estimated accelerated reverse process: It- = (xx():)) + E (zx)2, where
(=(x))) == x (1-+(11)))s (z)ss
(5)
:=x)) :- 1-:1 (Ia (1-a) (.))).
(6)
Here, can be obtained through score-matching (Song & Ermon 2019). In Section 3.2 we propose an estimator for 2 log qt. which refer to as Hessian matching. Let P be the marginal distributions of x4 in the estimated reverse process with corresponding p.d.f. p%
3.2 HESSIAN MATCHING ESTIMATOR FOR ACCELERATION
Below we provide method to obtain (z),, which estimates V log (x)). Note that
log (x) (x)
log g. (x)) (x)))
qe(x)
(2)(())
1-6, Ia)
1 Ia (Vlog (oggg
(()))
1-8,
Apart from the original score estimate, we require an additional Hessian estimate:
vx(x) = arg min by Ex,~q. vx()))
('..(X.)
T-ax Lu
1
(x.)
In order to train for 8; the following lemma provides an analogy to score matching, which we refer to as Hessian matching.
2 MMore rigorously, we can project the matrices Dx and Σ, onto the space of positive-semt definite (PSD) matrices for those ze's 's where either of these two matrices is not PSD. Since the probability of the events containing such bad 's decreases to zero asymptotically, all theoretical results in this paper, which are derived in expectation, will not be affected.
5

---

Published as a conference paper at ICLR 2025
Lemma 1.
With the forward process in ① we have
arg ty E Ex,qQ
(xx(
(''g((X)) (x(x))
+ I-a
1 11 11)
arg of E (xx.
volvārto + a.,) - 1-a. W.W.
With the Hessian estimate vs using Lemma from 7 an estimate for log qe (x) is given by
H₂(x) 0r (x
se (z))) (x).
(8)
With the estimator of H, in (8. the Hessian-based sampler using the En later in 2 is the same as the accelerated stochastic sampler in Li et al. (2024c). Yet, our analysis is applicable when estimation errors exist, whereas in Li et al. (2024c) the estimators are assumed to be perfect for the accelerated sampler. In the literature, several other estimators have been proposed for higher order derivatives of log qe (z) (Meng et al., 2021 Lu et al. [2022] Dockhorn et al. 2022). In our paper, we proposed another method, the Hessian matching method, which can guarantee accurate Hessian estimations with extra computation resources. Yet, our analysis can be applied to any estimator for H; as long as Assumption is satisfied.
ACCELERATED CONVERGENCE BOUNDS FOR BROADER TARGETS
In this section, provide convergence guarantees for the accelerated stochastic samplers for general Qo- We will first establish our main result for smooth Qo. and then extend it for more general (possibly non-smooth) Qo- We will also provide sketch of proof to describe key analysis techniques.
4.1 TECHNICAL ASSUMPTIONS FOR ACCELERATED SAMPLER
We first provide the following four technical assumptions for the accelerated sampler. Assumption (Finite Second Moment). There exists a constant M2 < oc (that does not depend on d and 7) such that Ex,~Q0 ||oo < M2d.
Assumption 2 (Absolute Continuity). Qo is absolutely continuous w.r.t. the Lebesgue measure, and thus qo exists. Also, suppose that qo is analytic and that (z) > O.
The above Assumptions I and are commonly adopted in the literature (Chen et al. 2023a d). Assumption (Score and Hessian Estimation Error). The estimates s, 's and H₂ 's satisfy
+ + Exi-Q. (X,, - V log (X,) S S² = ))T
+ Σ Ex He(x,) V log q: (Xx)
S = Ô(T-)).
1/6 = Ō(I)
Also, suppose that H1, satisfies sup
Ex Ex 1|4,(x)11)
The above assumption (Assumption B) describes the estimation error for both the score and Hessian. In particular, compared with regular samplers, the score function needs to be estimated at higher
accuracy in order to achieve acceleration. Such higher accuracy also required in previous analyses
of ODE samplers (e.g.. Li et al. (2024a d)) The regularity condition on H, can be satisfied, for example, when || is bounded as O(1). As another example, it suffices that [Hr)))] has polynomial upper bound in x when Q: is sub-exponential. In Lemma (in Appendix C) we provide sufficient conditions such that the H, in (8) satisfies Assumption 3
Assumption 4 (Regular Partial Derivatives). For all f 2 1, 1, and a E [d]e such that |a| = 2 1,
Ex l0g log qe (X.))* = (1), Ex,-Q. 10% log 9 1 (x))) = (1).
When qu does not exist, this is required only fort 2 2
The above regularity assumption (Assumption 4 on the partial derivatives is needed for our analysis based on Taylor expansion. It is rather soft, and it can be verified on the following two common cases: (1) when Qo has finite variance, and (2) when Qo is Gaussian mixture (see Section 55. Case clearly covers broad set of target distributions of practical interest, such as images, and many theoretical studies of diffusion models have been specially focused on such a distribution (Li et al. 2024a c).
Case 2 has also been well studied for diffusion models (Chen et al. 2024 Gatmiry et al. 2024).
'Here a function is analytic if its Taylor series converges to the functional value at each point in the domain. 'In the Appendix, we have provided the more general Assumption S under which Theorem 1 would hold.

---

Published as a conference paper at ICLR 2025
4.2 ACCELERATED CONVERGENCE BOUNDS
We first define new noise schedule as follows, which will be useful for acceleration. Definition (Noise Schedule for Acceleration). For large T's, the step-size at satisfies that
log T At E (T,...,T). ār = 0f = o (T-
When do does not exist, the upper bound on 1 - is only required for / > 2.
In Definition T the upper bound on at requires that at is large enough to control the reverse-step error, while the upper bound on ürr requires that is small enough to control the initialization error.
An example of ax that satisfies Definition is the constant step-size: 1 0t clog T Vt 2 1 with
> 2. Then, äT Thus, such Og satisfies Definition
clog
= =exp [Tlog ---lag (rpT)) O e prr=llos
(T (T
The following theorem provides the first convergence result for accelerated diffusion samplers for general smooth target distributions that have finite second moment (along with some mild regularity conditions). The complete proof is given in Appendix Theorem (Accelerated Sampler for Smooth Qo). Under Assumptions we have
with the at satisfying
Definition 7
KL(QO))P)) S(log T) + log" T EH
+E az) )z) Bx,_q Eij.k=1 Oz log (x))) log q (X,).
Theorem [ characterizes the convergence in terms of KL divergence (and thus TV distance) for will be further instantiated with explicit
smooth (possibly unbounded) Qu. The bound in Theorem [ dependency system parameters for example distributions Qo in Section 5 To further explain the upper bound in Theorem | the first two terms arise from the score and Hessian estimation error, and the last term captures the errors accumulated during the reverse steps over t = T,...,
which can be further bounded by Ö(T-2) under Assumption 4 (cf. (52)) Thus, when ei satisfies Assumption 3] the upper bound in Theorem | can be more explicitly characterized w.r.t. T as KL(Qoll Po) S Ō(T-2) + (log 2) (where the dependency on d will be explicitly characterized for specific distributions in Section 5). Thus, in order achieve O(s²) error in KL divergence, the number of steps required is (ss-1 This improves the dependency of the convergence rate on E of the regular sampler by a factor of O(s
We next extend Theorem T for smooth Qu to general Qu that can be possibly non-smooth and hence the density function qu does not exist. Such distributions occur often practice; for example, when Qo has a discrete support such as for images, or when Qu is supported on low-dimensional manifold. For non-smooth Qo. its one-step perturbation Q₁ does have a p.d.f. Q), which is further analytic (Lemmalß 6). This enables us to apply Theorem | on Q1 to obtain the following convergence bound. Also, we use the Wasserstein distance to measure the perturbation between Qo and Q1 (Chen et al.)
2023d Lee et al. 2023).
Corollary 1 (General (possibly non-smooth) Qo). Under Assumptions and 4 if the noise 7 a > 2, the distribution P1 satisfies
schedule satisfies Defimition
KL(Qi11P()) S(log T2 2= log"T 57
+ -1 3Ex Eijk=z 2g log (0g))1((((X)))0, log q (Xt),
where Q1 is such that W2(Qo, Q1)² S (1 al)d.
In particular, Corollary applies to any general target distribution when the second moment is finite.
4.3 PROOF SKETCH OF THEOREM
We next provide a proof sketch Theorem to describe the idea of our analysis approach. The full proof is provided in Appendix D Our approach is very different from previous SDE-type approaches, which invoke Fokker-Planck equation to express the evolution of p.d.f. and use Girsanov's 's Theorem develop
to bound the divergence, both along the continuous diffusion path. In comparison, novel Bayesian approach based on tilting factor representation and Tweedie's s formula to handle power terms, which is applicable to much wider class of target distributions, including those having
7

---

Published as a conference paper at ICLR 2025
infinite support. In particular, compared with Li et al. (2024a cd), our approach does not assume that the target distribution has finite support.
To begin, decompose the total error
KL(QolIPP) z Exx~Qr log 9r(Xx) (xT)
initialization
Py Pe- le (x,-1/Xx)) 1|x)) Etm Ex, log Pi- (xt-1|X+]
Et Ex,x X. X
llo 2e-1e(X (x)) P-- I1e (
estimation
step
The initialization error can be bounded easily (Lemma terms in five steps.
Below we focus on the remaining two
Step 1: Bounding estimation error (Lemma 4 At each time t= 1,..., T, rather than upper- bounding via typical sets as in Li et al. (2024c). we directly evaluate the expected value of log(p/-1j.
This is straightforward since P/ and Pi- are Gaus- sian. We then use Taylor expansion for the log det(-) function and the matrix inverse identify the dominant-oree terms under the mismatched variance.
Step 2: Tilting factor expression of log-likelihood ratio (Lemmas and and Equation (20).
With Bayes' rule, we show that Qt-1jt 1jt is an exponentially tilted form of P/-1je with tilting factor:
- (V log (p)) Va, V log 2 (1:))) (xx-1(11111111))0)) s4e)
+ (10-1 10-1-140 1O)T (V log 9 ( 1-a: -
-. Be(xe)
(01-1- - pe) Ep- [p 21-11
where (xxx describes the correction due the modified variance for acceleration (see (4 and (f,,, (2) ()) is the p-th order Taylor power term of function f around x = μ.. With this tilting factor, can upper-bound bound the reverse-step
as, for each fixed 22,
Ex log
(X, 112.)
< Ex..x.-rr...-
1S xx,, - Si 1).
Pl 2t (x,11
For regular DDPMs, there is no control for the variance of the reverse sampling process, and thus (x,),) 0. In this case, the dominating rate is determined by the expected values of T22. With the variance correction in our accelerated sampler, the corresponding B,(xz) enables us to cancel out the second-order Taylor term (see Lemma 11). As result, the rate-determining term becomes the expected values of T3, which decays faster. Thus, the acceleration is achieved.
Step 3: Explicit expression for Xx [S (Lemma) 7). Given the Taylor expansion of G this step can be reduced to calculating the expected values of the power terms, which are the Gaussian centralized moments. They are calculated using the classical Isserlis's Theorem.
Step 4: Explicit expression for (.t=---...,,...-11 (Lemmmas to 10p. While Qtje-1 is Gaussian, Qt-1je is not Gaussian in general, rendering the calculation of all moments non-trivial. To calculate posterior moments, we extend Tweedie's formula (Efron 201 in non-trivial way. Whereas the original Tweedie's formula provides an explicit expression for the posterior mean for Gaussian perturbed observations, we explicitly calculate the first six centralized posterior moments and provide the asymptotic order all higher-order moments, drawing techniques from combinatorics. The results also justify the expressions of i and Σ, in and
In order to employ the moment results for Taylor expansion, guarantee that it is valid to change the limit (in the Taylor expansion) and the expectation operator. Finally, substituting the calculated moments into Ex..X__1~Q... [C..-1l
Step 5: Bounding reverse-step error (Lemma
Ex,~Q..X, 1-Pp P and noting that higher-order partial derivatives do not affect the rate (by Assumption 4),
we can determine the dominating term and obtain the desirable result.
5 EXAMPLE Qo's: ACCELERATED CONVERGENCE RATE WITH EXPLICIT PARAMETER DEPENDENCY
Now, we specialize Theorem and Corollary I to several interesting distribution classes, for which convergence bounds with explicit dependency on system parameters can be derived. The key is to locate the dependency in the dominating terms in the reverse-step error.
8

---

Published as a conference paper at ICLR 2025
5.1 GAUSSIAN MIXTURE Qu
We first investigate the case where Qo is Gaussian mixture. This is a rich class of distributions with strong approximation power (Bacharoglou 2010 Diakonikolas et al. 2017). The following theorem establishes the first accelerated convergence result with explicit dimensional dependencies for such distribution class.
Theorem 2 (Accelerated Sampler for Gaussian Mixture Qo)- Suppose that Qo is Gaussian mixture, whose p.d.f. is given by qu(xa) En= unqu.n (TO), where 9a,n is the p.d.f. of En,n) and
Tn E [0, 1] is the mixing coefficient where En= on 1. Under Assumption if the a₁ satisfies
Definition 7 we have
KL(QolI 2
d (i log 1o + (log T) log² T etH
T
Therefore, for any Gaussian mixture target Qo with N S d, it takes the accelerated algorithm O (d--5 (1155/e) steps reach convergence under accurate score and Hessian estimation. This the first result for accelerated DDPM samplers to achieve an accelerated convergence rate for Gaussian mixture targets under score and Hessian estimation error. Compared with the results for regular samplers, the number of convergence steps improves by a factor of ((=
The proof of Theorem 2 is non-trivial because order to show that Assumption 4 holds for Gaussian mixture distributions with any a according to Definition [ it is generally difficult to evaluate and provide an upper bound for all onders of partial derivatives of the logarithm of a mixture density. To this end, we employ the multivariate Faá di Bruno's 's formula (Constantine & Savits 1996) to develop an explicit bound (Lemmas and 14).
Below we numerically evaluate the performance of our Hessian-accelenaan DDPM when Qo is Gaussian mixture. The original accelerator requires calculating the square-root matrix of S. (see (4), which might be computational burdensome. Below, we propose an approximated Hessian-based accelerated sampler, where The is still defined in (5) and E., is replaced by E, (Iz) where
at (x,))) 1-a1 (La + 1 log (xx))) Ex(xx) = 1-au (La + 1- (xx)))
(9)
With similar tilting-factor analysis in Thcorem I we can verify that the approximated sampler
still achieves an accelerated convergence rate (see Corollaries 2 and 3 and Remark 3).
In Figure T we compare the following four accelerated samplers: (1) the regular DDPM sampler
(in blue); (2) our Hessian-accelerateed sampler (in red); (3) the accelerated stochastic sampler in Li
al. (2024a) (in cyan); and (4) the deterministic sampler using PF-ODE, which analyzed in Li
et al. 2024c d); Huang et al. (2024a). Here N = 4 and d = 4. The performance is averaged over 30 different trials. In a single trial, 200000 samples are used to estimate the KI. divergence. The o, in
(10) is used with 4 and 6 0.001. From the comparison, it is observed that our Hessian- based
sampler achieves the best convergence (at similar computation levels) in non-asymptotic regimes.
Hess Hestan-zcoelentt
Haddanacoderrts
aroneraton don oDe
Accetration by Lia
oce
Comparison of different accelerated samplers for Gaussian mixture Qo's. The r-axes are the number of steps (left) and the computation time of trial (right), respectively.
Figure 1:
5.2 FINITE VARIANCE Qo WITH EARLY-STOPPING Next, we specialize Corollary to a special noise schedule, first proposed in Li et al. 2024c):
- 02 <log min ( (1+ clog T
,1, V2 SIST,
(10)

---

Published as a conference paper at ICLR 2025
and 1 - a1 = 8. Here and 8 satisfy that e > 2 and 8e > 1. Intuitively, ō characterizes the amount
of perturbation between Q1 and Qu (Lemmal 12p. Note that any noise schedule satisfying the above
condition also satisfies Definition[aatt 2 2 (see (49) ) and hence Corollary still holds here.
Theorem 3 (Accelerated Sampler for Qo with Finite Variance). Under Assumptions
and using
the at defined in (10) with c. 2 and = log(1
have
KL(Oi|IPD) E d (1/5) + (logT))² + log log"T 5
where Q1 is such that W2(Qo, Vz(Qo,Q1)2 8d.
Theorem 3 indicates that for any Qo having finite variance, it takes the accelerated algorithm O (d log (1/5)/e) steps to approximate an early-stopped data distribution Q1 within O(e2) error in KL divergence (or (s)) in TV distance). For carly-stopped procedures, this theorem significantly relaxes the previous assumption on the target distribution that requires Qo to have bounded support (Li
2024a Huang et al. 2024a Li et al. 2024d). Compared to previous accelerated diffusion samplers for hounded-suppon targets eLi 2024a c). our number of convergence steps to achieve
e-TV distance has improved by factor of O (d..)).
The proof of Theorem 3 involves the following novel elements. (i) Verifying Assumption requires evaluating and providing an upper bound for all orders of partial derivatives of the logarithm of a continuous mixture density. Differently from the case of Gaussian (discrete) mixture, here we can only have an upper bound in expectation (i.e., in (Q+)) (Lemma 15p. (ii) The second half of Assumption 4 requires an upper bound for the one-step perturbed score, which can be shown using the change-of ohaane--f-vvrribbee formula and the data processing inequality for large T (Lemmas 16 17
5.3 Qo WITH LIPSCIITZ HESSIAN LOG-DENSITY
With the a, in (TO), we derive convergence result when only the log-density of Qo smooth. Theorem 4 (Accelerated Sampler for Smooth Hessian Jog-Density). Suppose that V log go (z()) is 2-norm M Lipschitz. This means that 3M > 0 such that
Vx,y E RR. V2 log go (0))) 4 log go so(v)l S M || yll,
Then, under Assumptions Land using the a in TO with 8 1/(M/T²) and 2 3T)
we have
KL(QolIP)) S
(log" M +loog" T) T + (log T)e 2 + log T T T EH.
T
We also provide accelerated convergence result with linear d dependency when all the 2 log q (z) (t (t20) 0) are 2-norm M-Lipschitz (see Theorem
5 i Appendix G.3
Theorem 4 provides log qu. under the score and Hessian estimation error. In words, in order to reach O(s) TV-distance when e / S e², the number of steps needed under Lipschitz-Hessianl Qn 's is O(d log" 1.5 M/e). This is different from Chen al. (2023c); Huang et al.] (2024a b) in which some smoothness condition is imposed on all V log lt (or 8 's or both). Compared with Theorem 3 this upper bound in Theorem 4 is directly over (L Pi) instead of for some early- sarly-stopped distribution. Our results provide new contributions that complement existing studies by exploring different assumptions of distributions, which enriches the existing set of distributions studied in the literature.
with first accelerated DDPM result with only smoothness constraint
Our analysis is significantly diffcrent from that in (Chen et al., 2023a Theorem 5). There, the Poincaré inequality is key to guarantee that the Lipschitz smoothness in V log 4o is preserved when 5 is small, but this inequality may not hold in our case with smoothness only in V lolog go- Instead, with smooth 2 log 9o. expand the tilting factor only to its third-order Taylor polynomial and directly provide an upper bound with techniques used in proving Theorems and
6 CONCLUSION
In this paper, we have provided accelerated convergence guarantees for a much larger set of target distributions than in prior literature, including both smooth Qo and general Qu with early-stopping. The accelerated rates are achieved with new accelerated Hessian- based DDPM sampler using novel analysis technique. One future direction is to further shrink the dependency for general Qo- It is also interesting investigate other acceleration schemes to further improve diffusion samplers.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work has been supported in part by the U.S. National Science Foundation under the grants: DMS-2134145, CCFF-190145, NSF Institute (AI-EDGE) 2112471, CNS-2312836, CNS-2225561, ONR grant N000142412729, and was sponsored by the Army Research Laboratory under Cooperative Agreement Number W91 INF-23----0225 The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
REFERENCES
Athanassia G. Bacharoglou. Approximation of probability distributions by convex mixtures of gaussian measures. Proceedings of the American Mathematical Society, (18(7)2661-26228 2010.
Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly d-linear con- vergence bounds for diffusion models via stochastic localization. In The Twelfth International Conference on Learning Representations, 2024a.
Joe Benton, George Deligiannidis, and Arnaud Doucet. Error bounds for flow matching methods. Transactions Machine Learning Research, 2024b.
Stefano Bruno, Ying Zhang, Dong-Young Lim, Ömer Deniz Akyildiz, and Sotirios Sabanis. On diffusion-based generative models and their error bounds: The log-concave case with full conver- gence estimates. arXiv preprint 11Xix:2311.13566 2023.
Yu Cao, Jingrun Chen, Yixin Luo, and Xiang ZHOU, Exploring the optimal choice for generative processes in diffusion models: Ordinary vs stochastic differential equations. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Jinyuan Chang, Zhao Ding, Yuling Jiao, Ruoxuan Li, and Jerry Zhijian Yang. Deep conditional generative learning: Model and error analysis. arXiv preprint 2rXiv:2402.01466. 2024.
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative model- ing: user-friendly bounds under minimal smoothness assumptions. In Proceedings of the 40th International Conference Machine Learning, 2023a.
Minshuo Chen, Kaixuan Huang, Tuo Zhao, and Mengdi Wang. Score approximation, estimation and distribution recovery of diffusion models on low-dimensional data. In Proceedings of the 40th International Conference on Machine Learning, 2023b.
Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ODE is provably fast. In Thirty-seventh Conference Neural Information Processing Systems, c023c.
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 Learning Representations, 2023d.
Sitan Chen, Giannis Daras, and Alexandros G. Dimakis. Restoration-degraaatton beyond linear diffu- sions: a non-asymptotic analysis for ddim-type samplers. In Proceedings of the 40th International Conference on Machine Learning, 2023e.
Sitan Chen, Vasilis Kontonis, and Kulin Shah. Learning general gaussian mixtures with efficient score matching, arXiv preprint arXiv:2404.1889. 2024.
Xiuyuan Cheng, Jianfeng Lu, Yixin Tan, and Yao Xie. Convergence of flow-based generative models via proximal gradient descent in wasserstein space. arXiv preprint ArXiv:2310.17556 2023.
Frank Cole and Yulong Lu. Score-based generative models break the curse of dimensionality in learning a family of sub-gaussian distributions. In The Twelfth International Conference on Learning Representations, 2024.
11

---

Published as a conference paper at ICLR 2025
Giovanni Conforti, Alain Durmus, and Marta Gentiloni Silveri. Score diffusion models without early stopping: finite fisher information is all you need. arXiv preprint (rXxi:2308.122400 2023.
G Constantine and T Savits. A multivariate faa di bruno formula with applications. Transactions of the American Mathematical Society, 348(2):503-522 1996.
Croitoru, V. Hondru, R. Ionescu, and M. Shah. Diffusion models in vision: A survey. IEEE
Transactions Pattern Analysis & Machine Intelligence, 4509):18800-1000 Sep 2023.
Valentin De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. Transactions on Machine Learning Research, 2022.
Valentin De Bortoli, James Thornton, Jeremy Heng, and Arnaud Doucet. Diffusion schrödinger bridge with applications to score-based generative modeling. Advances in Neural Information Processing Systems, volume 34, pp. 17695-17709, 2021.
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 73-84, 2017.
Tim Dockhorn, Arash Vahdat, and Karsten Kreis. Genie: higher-order denoising diffusion solvers. In Proceedings of the 36th International Conference on Neural Information Processing Systems, 2022.
Bradley Efron. Tweedie's 's formula and selection bias. Journal of the American Statistical Association, 106(496):1602-166)) 2011.
Xuefeng Gao and Lingjiong Zhu. Convergence analysis for general probability flow odes of diffusion models in wasserstein distances. arXiv preprint arXiv:2401.17958, 2024.
Xuefeng Gao, Hoang M. Nguyen, and Lingjiong Zhu. Wasserstein convergence guarantees for
general class of score-based generative models. arXiv preprint arXiv:2311.11003 2023.
Yuan Gao, Jian Huang, Yuling Jiao, and Shurong Zheng. Convergence of continuous normalizing flows for learning probability distributions. arXiv preprint arXiv:2-404.0055), 2024.
Khashayar Gatmiry, Jonathan Kelner, and Holden Lee. Learning mixtures of gaussians using diffusion models. arXiv preprint rxXv:2244411869 2024.
Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, volume 27, 2014.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, volume 33, pp. 6840-6851, 2020.
Daniel Zhengyu Huang, Jiaoyang Huang, and Zhengjiang Lin. Convergence analysis of probability flow ode for score-based generative models. arXiv preprint arXiv:2404.09730, 2024a.
Xunpeng Huang, Difan Zou, Hanze Dong. Yi Zhang, Yi-An Ma, and Tong Zhang. Reverse transition kerne:: A flexible framework to accelerate diffusion inference. 16387, 2024b.
Yuling Jiao, Yanming Lai, Yang Wang, and Bokai Yan. Convergence analysis of flow matching in latent space with transformers. arXiv preprint arXiv:2404.0P 02538, 2024.
Amirhossein Kazerouni, Ehsan Khodapanah Aghdam, Moein Heidari, Reza Azad, Mohsen Fayyaz, llker Hacihaliloglu, and Dorit Merhof. Diffusion models in medical imaging: A comprehensive survey. Medical Image Analysis, 88, August 2023.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. 1312v:1312.611 2022.
arXiv preprint
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. In Advances in Neural Information Processing Systems, 2022.
12

---

Published as a conference paper at ICLR 2025
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In Proceedings of The 34th International Conference on Algorithmic Learning Theory, volume 201, pp. 946-985, 2023.
Gen Li, Yu Huang, Timofey Efimov, Yuting Wei, Yuejie Chi, and Yuxin Chen. Accelerating convergence of score- based diffusion models, provably, arXiv preprint arXiv:2403.03852 2024a.
Gen Li, Zhihan Huang, and Yuting Wei. Towards mathematical theory for consistency training in diffusion models. arXiv preprint arXiv:2402.071 200002222.7782 2024b.
Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Towards faster non-asymptotic convergence for diffusion-based generative models. In The Twelfth International Conference on Learning Representations, 2024c.
Gen Li, Yuting Wei, Yuejie Chi, and Yuxin Chen. A sharp convergence theory for the probability flow odes of diffusion models. arXiv preprint arXiv:2408.02320 2024d.
Puheng Li, Zhong Li, Huishuai Zhang, and Jiang Bian. On the generalization properties of diffusion models. arXiv preprint arXiv:2311.01797 2024e.
Cheng Lu, Kaiwen Zheng, Fan Bao, Jianfei Chen, Chongxuan Li, and Jun Zhu. Maximum likelihood training for score-based based diffusion odes by high-order denoising score matching. In International Conference on Machine Learning, 2022.
Junlong Lyu, Zhitang Chen, and Shoubo Feng. Sampling is as easy as keeping the consistency: convergence guarantee for consistency models, 2024.
Song Mei and Yuchen Wu. Deep networks as denoising algorithms: Sample-efficient learning of diffusion models in high-dimensional graphical models. arXiv preprint arXiv:2309.11422 2023.
Chenlin Meng, Yang Song, Wenzhe Li, and Stefano Ermon. Estimating high order gradients of the data distribution by denoising. In Advances in Neural Information Processing Systems, 2021.
Pierre Moulin and Venugopal V. Veeravalli. Statistical Inference for Engineers and Data Scientists. Cambridge University Press, Cambridge, UK, 2018.
Kazusato Oko, Shunta Akiyama, and Taiji Suzuki. Diffusion models are minimax optimal distribution estimators. In ICLR 2023 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2023.
Tohru Ozaki. A bridge between nonlinear times series models and nonlinear stochastic dynamical systems: A local lincarization approach. Statistica Sinica,
1992.
Francesco Pedrotti, Jan Maas, and Marco Mondelli. Improved convergence of score-based diffusion models via prediction-correttion arXiv preprint arXiv:2305.14/11 2023.
Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. Proceedings of the 32nd International Conference on Machine Leurning, volume 37, pp. 1530-1538, 2015.
Kulin Shah, Sitan Chen, and Adam Klivans. Learning mixtures of gaussians using the DDPM objective. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Isao Shoji. Approximation of continuous time stochastic processes by local linearization method. Mathematics of Computation, 67(221):287-295 1998.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, pp. 2256-2265, 2015.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In Interna- tional Conference on Learning Representations, 2021.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution.
In Advances in Neural Information Processing Systems, volume 32, 2019.
13

---

Published as a conference paper at ICLR 2025
Yang Song. Prafulla Dhariwal, Mark Chen, and Ilya Sutskever. Consistency models. In Proceedings of the 40th International Conference on Machine Learning, 2023.
O. Stramer and R. L. Tweedie. Langevin-type models ii: Self-targeting candidates for meme algorithms. Methodology And Computing In Applied Probability, 1()):307-328, 1999.
Andre Wibisono, Yihong Wu, and Kaylee Yingxi Yang. Optimal score estimation via empirical bayes 2024.
smoothing. arXiv preprint
Ling Yang. Zhilong Zhang, Yang Song. Shenda Hong, Runsheng Xu, Yue Zhao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang. Diffusion models: A comprehensive survey of methods and applications. ACM Computing Surveys, 56(4), Nov 2023.
Kaihong Zhang, Heqi Yin, Feng Liang, and Jingho Liu. Minimax optimality of score-based diffusion models: Beyond the density lower bound assumptions. arXiv preprint 4:X1::2402.15602, 2024.
14

---

Published as a conference paper at ICLR 2025
Appendix
A Related Works
16
B Full List of Notations
17
Proofs of Lemmas and
17
Proof of Lemmall
17
C.2 Lemma 2 and its Proof
18
D Proof of Theorem
19
D.1 Step 0: Bounding term Initializaiinn Error
20
D.2 Step 1: Bounding term 2 Score and Hessian Estimation Error
D.3
Step Expressing Likelikel Ratio via Tilting Factor
................................
D.4
Step 3: Conditional Expectation of G,,-1 under P7-1
................................
23
D.5
Step 4: Conditional Expectation of G,z-1 under Q 1/t
24
D.6 Step 5: Bounding term 3 Reverse-step Error
26
Proof of Corollary 1
27
F
Auxiliary Proofs for Theorem and Corollary 1
27
Prool of Lemma
27
Proof of Lemmald
28
Proof of Corollary
30
R.4
Proof of Lemma
30
F.5
Proof of Lemma
31
F.6
Proof of Lemmal
31
Proof of Lemma
32
Proof of Lemma
Proof of Lemmal
35
E.
10 Proof of Lemmall
40
Proof of Corollary
42
2 Proof of Lemmal1
43
G Proof of Theorrms 2 to
and
43
Proof of Theorem
43
Proof of Theorem
49
Theorem ald Proof
53
Proof of Theorem
54
15

---

Published as a conference paper at ICLR 2025
H
Auxiliary Proofs of Theorems 4
55
Proof of Lemmal
55
Proof of Lemma
58
Proof of Lemma
59
Proof of Lemma
59
H.5 Proof of Lemma
62
H.6 Proof of Lemmall
62
A RELATED WORKS
Theory Regular DDPM Samplers: Many works have explored the performance guarantees of regular DDPM models. Specifically, a number of studies perform analyses under the L score estimation error De Bortoli et al. 2021 De Bortoli 2022). Later, under L score estimation error, Lee et al. 2022) developed polynomia bounds for distributions that have Lipschitz scores and satisfy log-Sobbe Sobo-ee inequality. Soon after, Chen al. (2023d); Lee et al. (2023) concurrently developed polynomial bounds for those smooth distributions having Lipschitz scores and those non-smooth distributions having bounded support using early stopping. Later, Chen al. (2023a) improved the number of steps for those target distributions with finite second moment. Recently, the convergence result was further improved to linear dimensional dependency using stochastic localization (Benton al. 2024a). Confortt et al. (2023), by transforming the original process to the relative-score process, it is shown that linear dimensional dependency can also be achieved for those target distributions having finite relative Fisher information against Gaussian distribution. In all the works above, the analysis technique is to discretize some continuous time diffusion process use SDE-type analyses. In Li et al.] (2024c), by carefully design typical set, polynomial-time guarantees are obtained directly for the discrete-time samplers under the T.2 estimation error for target distributions having bounded support. Other than the works above, Pedrotti al. (2023) analyzed different sampling scheme (c.g., predictor-corrector and a et (2023); Gao et al. (2023 Gao
Zhu 2024) analyzed sampling errors using different error measure (the Wasserstein-2 2 distance).
Theory Score Estimation: In order to achieve end-to-end analysis, several works developed sample complexity bounds to achieve the L score estimation error for a variety of distributions.
To name few, this includes results for those having bounded support (Oko al. 2023 y Gaussian
mixture (Shah et al. 2023 Gatmiry et al. 2024) Chen et al.) 2024), certain families of sub-Gaussian
distributions (Cole Lu 2024| Zhang et al. 2024), high- digendiimnsional graphical models (Mei &
Wu 2023), and those supported on a low-dimensional linear subspace (Chen et al. 2023b). More recently, Li al. (2024e) considered the generalizability of the continuous-time diffusion models, and Wibisono et al. (2024) proposed regularized score estimator that attains the minimax rate of estimating the scores.
Other Theoretical Works: Other than the works listed above and in Section 1.2 Gao & Zhu 2024
studied the ODE convergence for strongly-concave target distributions under Wasserstein-2 error. Cao al. (2023) compared the performance of SDE and PF-ODE and investigated conditions where one might outperform the other. Besides PF-ODE, Cheng et al. (2023): Benton et al.) (2024b); Jiio
al. )024); Gao et al. (2024) provided guarantees for the closely-related flow-matching model, which learns a deterministic coupling between any two distributions, Chang et al. (2024) proposed
novel ODE for sampling from a conditional distribution. [Lu et al. (2024); Li al. (2024b) provided
convergence guarantees for the more recent consistency models (Song et al. 2023
Relationship to GENIE (Dockhorn et al., 2022): To obtain higher-order scores, another method to use automatic differentiation, in GENTE (Dockhorn et al.] (022). There higher-order score functions are used to accelerate the diffusion sampling process empirically. In particular, Dockhorn al. 2022 shows that GENIE achieves better empirical performance than deterministic samplers such as DDIM (Song et al. 2021 Our paper theoretically justifies the accelerated empirical performance of Dockhor et al. (022) the regime when the Hessian of log qi is well-estimated.
'By "polynomial" mean that the number of steps has polynomial dependency the score estimation error, along with other parameters.
16

---

Published as a conference paper at ICLR 2025
B FULL LIST OF NOTATIONS
For any two functions f(d, 6, T) and g(d, 6, T). we write f(d, ( g(d,6,T) (resp. f(d,
g(d, 6, T)) for some universal constant (not depending on 5, d T) I, 30 (resp. L 0) if lim sump-p-s -oo [f 6, T g(d, 6, T) < L (resp. lim + [f 6, (, 2 L.. We write g(d,
hold. Note that the dependency on 5 and d is retained with S. We write f(d, =gg(T)) (resp. f(d, 5, T) (T) f(d, 6, T) 2 L(d, (T) (resp. 8, 2 L(d, (g holds for some L(d, 5) (possibly depending on and d). We write f(d, =[g(TT) if lim supr-x If(d, 6, T) /g(T) = 0. We write f(d, 6, T) = (g)(T) if 8,)) Ogg(T) ((llgg(()))) (()))* for some constant k. Note that the big-O notation omits the dependency on 6 and d. In the asymptotic when s - oc, write = (d, ()) if f(d, 6, S g(d, 6, " g(s 1)} for some constant k. Unless otherwise specified, we write x' (1 Sis d) as the i-th element of a vector x E R and [A]* the (i. element of matrix A. For function f(x) Rd + R. we write fz)(2) (2) shorthand e
f(d, 6, 1
g(d 6, 2) when both f(d, S o(d.6,1) and f(d,
for dz (() and similarly for higher moments. For matrices A, B. Tr(A) is the trace of A, and A = B means that B - A is positive semi-defiiite For positive integer n, [m] = f1....,.) n).
C PROOFS OF LEMMAS AND 2
In this section, we provide lemmas and proofs related to Hessian estimation.
C.I PROOF OF LEMMA I
The idea similar to score matching. Define rx(x)) == Ue (x)) - I- I
la. For each i, [d].
11 0/
(x)))
(
(x.)(()))
(X,) + 1 1 1 =
Bx.eQ
Oke
=xx,e: (16(x))] - (x))
(((e))
ExInQ (1)6())))1)) 2EXi~ (v6(x.))' (xi) (X,,
+ const
Ex (1/b (x,)))))) -2 -
(drr)da const
where const denotes terms that are independent of 0, and
/ 0z
-(bb(E)))) / o (oo
/ (10o(())))))6(6a.)) & (( (o) (o(())00))
(Zo(xo)drr
@ [ (00(00120)(66(11111 (0tz log (2) + O log
log de 1o (zo)) dQu (zo )z
/1 (nooa
1 [ii==i
+ o Vanzg
x! vayag
dQo(2o)dzr
Ct.
1 Cie
di
E Exx ('6(x,)) ( Xa= VI-aw
1 fi 1 0zt
wiw?
1 i- āz
02,
where (i) follows because for any function f(x) have 8 log f(x)
f(x)
(ō, log (O, log f())), and (ii) follows because 2₁ = Vārzo + VI - a, Therefore,
(x,)(()) (0) {{==}}
Ex,0. 0 (x.)) -
(X.)) 1
17

---

Published as a conference paper at ICLR 2025
(x, (rx()))) X Xo T.
1 1[i==)
1
w:w! )) const.
1 az
1
2
(x,,W)-- X VI-awW
[vo (x,))
W&W?
+ const
1
and the result follows immediately after we sum up over i, E [d].
C.2 LEMMA 2 AND ITS PROOF
The following lemma provides sufficient conditions such that the He in satisfies Assumption 3 with the an, defined in Definition suppose that vs and St satisfy.
Lemma 2. Under Assumption as T - oc,
5
+ EK Ex Ex, |or(X.) (
(V'g(((e) 1-1.1a 1a) - (c(Xe) I-
-
Ö(T-1),
(11)
maxIsIsT(1 oz) Bximq (1x)(X)) V Vlog do (Xx)ll Ō(1I.
(12)
Exirq. [(H((x))) 1/2 = -(1). Then, the
Also suppose that the Hy defined in (8) satisfies sup
H₃ and the St from score matching (Song Ermon 2019) satisfy Assumption 3
Proof of Lemma The condition on the score estimation enror in Assumption 3 is immediately satisfied using Jensen's inequality. We next focus on the condition on the Hessian estimation. Recall that
1
H₂(x) = vt(x)) - a La -
The goal is to show that H, close 2 log qt (i.e., the second relationship Assumption Given that 7 (e)) V²q((m) (V log (x)) log T, the key is to control the error incurred
by (x)) which ((())
Ex,Q
<(()))s((x)) - (laga
i==1
=Bx,Q.
Σ
(s((X.)
(x)( V (V (VV))))(((({())))VVV)V))))))))))
(Vlog((x))))))
1-=1
d
<
Σ
(V log q: (X,))
i/=1
[ls)(X.) = =EX
- v vo
log (x)) |1 || Xx) (x.)
To continue, we use the where (i) follows because (a + b)2 = a² + 1 + 2ab 2a² 2bb.
Kauchy-Schwarce inequality and obtain
Ex,q. (x))s (Vlog log (X.))
s 2
log q E Q [X,) -
(Xx)ll 2xx,0q || [[Vlog (|sxx)
Here the second term has that
(X,))( < (X,, - V Vlog ( SE V llog
< E (o (X)))
Therefore,
T T
ExiaQ Hi(x))
log (X:)l
18

---

Published as a conference paper at ICLR 2025
T
( (x(x,) +
2
E Ex
(x(xx)
1 Cz Id
Ex, (xx((X)) - (V log 2 log
t=1
(xx.) + -
Czz Ia 1 11))
2
Ex,
Qi
vo(Xx)
T
V (xxxello((x)) [|)r(X,) v Vlog ai (X+))* / Exxx- V/V log (X.)ll
(6)
T
(o((x)) ((x))))-0 (((()))(((((())) (Vig((X))
1 la
E
Ex
+ 1- ae
T t=1
(X,)
1
(1 xx)2Exx~Q.. |I log go
T
(152)
T
Ex
[o(x))
(F (x,,)
+ 1 az
1
La
2 + O(TT-)
F
where (iz) follows from 12 using the fact that + Et=l Val and (iii) follows under Assumption
E at by Jensen's inequality,
5
Combining this with (I1)
we finally get
T (X,)
(V(g(X))) + 1- āt Ia I. = o(T
Ex
g((X)) (gx(
and thus the second relationship in Assumption is satisfied. The proof now complete.
D PROOF OF THEOREM
Instead of Assumption 4 we will prove Theorem Jnder the following more general assumption, which obviously implies Assumption for any ag.. Assumption 5 (Regular Partial Derivatives+). For all t 2 1, l 2 1, and E [d] such that |a| 1,
(1 o.) )x 22/ Ex Q 10 log a (xx) = =0((1 pp/e))
(1 a.) pf/2 Ex.qq 10 log ai (Ho(X)))) Ô ((1 (11-ar) (1-a)) (0122)
When go does not exist, this is required only for > 2.
To begin the proof of Theorem
note that
g(Xo X7)
KL(QIIP) Exemn.Xyya
log ((Xo Xr)
log 40 (Xo) ITt 2oje 10 (X.(Xx,
E Exg...
P'Xuu, Xx.)
go (Xx) IT. Orle- (X,lX (x-1)
(11) Exa....Pro
log
(X,))
I 1/pp-1 (Xe(X,-1)
log (Xo)
log 4: 1 (X₂ (x,11)
=Exo~Q0
Ex, 1.x10 1.1
(Xo))
Pelc-1 1 (x, X(-1)
log (X(oo) (Xo)
T
log 9tje-1 1 (Xr (x:11
-Exe~oo
+ Σ
Ex 1x Q
Ex-
p (Xe (x,1))
t=1
19

---

Published as a conference paper at ICLR 2025
T
= -I((Q)l + Σ Ex- (1
t=1
Here (i) holds because the Markov property of the forward process. We explain (ii) below, By the backward Markov property of the reverse process, for any & 2 1, given X,-1 -t-1, each of X Xy is independent with Xt. This implies that
Pite I...- ( (2 mo) (()t-1(2e(2211)
Vt 2 1.
Thus, 77 (2o. ................................ .r) = fo(2)) Ii (1 In other words, Xo...., X2 is also forward Markov under P.
Following from similar arguments,
KL(QII KL(OT))
Σ Ex [KL(Q
Since KL-divergence is non-negative, an upper bound on KL(QolIP() is given by
KT.(Qol)PP)
=KT(Qr\1P4)
Σ
E Exxaq [II(Qr=(((XX))|]==](xx))),
t=1
Σ
Ex, 1~
T
< KL(QTTIPP) + Σ Ex (L(00-11(((X3)))P===m
t=1
= Ex log (XT)
E Ex.xi-I log (
plr
(X Xx,
Term initialization enror
error
log 9t-1 (X (x))
Ex.,
(13)
P 11- (X
Term 3: reverse step
The last equality holds because F ptT Next, we bound the above three terms separately in a few steps.
D. STEP O: BOUNDING TERM INITIALIZATION ERROR
Lemma 3. Suppose ärr Y as as oo. Then, under Assumption 7
Exp~Qr log 9T (x
Maärd + 0 ( T +
Remark Under Assumption if the noise schedule satisfies Definition I we have
E Rx log (XT) -)
Proof. See Appendix F.I
We now introduce the following notation for analyzing the estimation error and the reverse-step error for the accelerated sampler. Definition 2 (Big-O in L space). For random variable Zr, say that 7r(x*) Ozr(q) (1) if (Ex-Q (x))" 0(1) for all 1 as T
oc.
20

---

Published as a conference paper at ICLR 2025
One property is that if Zr(x) (Q) then Ex~Q (X)) O(1). Another property is that if 71 = (0)(Q)(1)) (aT) and 7- = O (br) for all r 2 1, applying Cauchy-Schwartz inequality we get, for all 1,
LE 12, 1/ - [EZ2T 1/(2r) O(arbr),
which implies that O (r(()) (0))(aT)0 (br) - OCT1Q) Now, with this notation, the regularity condition on H2 can be written
(1 04) [X, 01 oz), Vr 2 1.
Also, Assumption 5 can be equivalently written as, 1,
(1- 10 log gr (X,) = ( (11 (11-a)
(1 - az) 10 log qi 1 (px(()) = Ōc)(2))) (1-ax)
D.2 STEP 1: BOUNDING TERM SCORE AND HESSIAN ESTIMATION ERROR
We first bound the estimation error, which includes the errors that come from the score and the Hessian estimation. In particular, Assumption guarantees that all higher Taylor terms are well controlled in expectation over X Qu-
Lemma 4. Under Assumptions 3 andd S
with the on satisfying Definition 7
we have
Pl-1jo(X,-11
log T
Σ
E Ex..X-IN
log 8 1/ (Xx-1(Xx)
I (log T) +
E
T
Remark 2. Under Assumption
Lemma
guarantees that
T
P/ P/-1je X log
1 =
T
Proof. See Appendix F.2
Before we proceed to the reverse-step error, we provide the following lemma to provide upper bound when we use the E. and its estimate according to (
Corollary Under the same conditions of Lemma 4 the upper bound in Lemma 4 on the estimation error still holds with the slightly perturbed E. provided in 99.
Proof. See Appendix F3
D.3 STEP 2: EXPRESSING LOG-LIKELDHOOD RATIO VIA TILTING FACTOR
Next focus the reverse-step error for the accelerated process. Recall that Qo is smooth under Assumption 2 We introduce the following notations for analysis. Let
Ax(x.) == (1 (v.) V log
Br(x)) = la (La Ar(zz))
(14)
which imply that
(x 1- (La Ac(e)),,
(x1)))
(Id --(())))
at
1 az
Now, with the notation in Definition under Assumption 5 Also, when (1 ox) is small, we can perform Taylor expansion on B,(+) around
for each i,j E [d], A (z.) = ocr(e.) (1 - az) for all r > 1
A.(.) and obtain, under Assumption
Bx(X,) Ax(X,) Ocria ((1-a))²).
(15)
21

---

Published as a conference paper at ICLR 2025
Remark 3. In general, suppose that choose P Pi- whose conditional covariance satisfies
EX,), - (Ix A((x) + (c)(Q)) 101-aw (a-)))))) = Ex(X,) + (2)(q)) ((1 - ((x))a)))) as))),
0t
where small perturbation is added to the covariance matrix. An immediate consequence is that
(x)) 1 1-a4 az (Ia (Ia-Br(X)) (x)))) + (c) ((1 ((1 (x,) 0c) (1 at).
Then, with such Pi- having a slightly perturbed covariance, the following Lemmas 5 and still hold with (c())) and Be (2x,) such that
(.( = 1 1 at
at
(x((1x)) - la: Br( = -Ta Ax(x)))-
Note that A((x,) = + ((1 a1)?) and (x(),) = Bx,)) + Ōcies ((1-at))
In the following we write br = p4 (2+), A, = (zz)) and B. = (xx) for brevity.
Lemma 5. For any fixed it E Rdd as long q is defined, we have
(1= 1e. (11 9- (--11(=0-11211)
Ex.-inP(- [e (0188e11))
where
(1s, = log (1---1( log (gg(t-((14) (3t-1-14) ((re--- (16)
and
(T,, (t-1) = St,t-1 (1t, Tt-1) 2(1 - az)
0t
(xt-1 - BB p4)
log 91- (x loo 91-1 10gg:-11(44 (II-1 (Vo
(21-1 1 (1 -4).
(17)
2(1 at)
Proof. See Appendix E.4
In the following we write St.e-1 dencies on Hy and xt-1 for brevity. As we will see, (T6) is the tilting factor for the regular diffusion process. Given the definition of G,--1 in (17), below we analyze log ( around x /e using Taylor expansion. We first provide the following notations for the Taylor expansion. Definition 3 (Taylor Expansion). Recall that x (1 < i < d) denotes the i-th element of a vector Given an analytic function f(r), its Taylor expansion around x = μ is given by
(t-1) and 1
xt-1) and omit depen-
f(x) - s()) + Σ x.
1=1
1 d
[(4)) (x) 1))
Σ
Sh (1) - 11/²+
1
Σ
og (2)((' - -1²) 18)
2 1=1
2
1,f=
ifj
Σ T
3
where, for p 2 1, we define
T) = p!
Pzf(p) II
xx' p
(18)
TEN::E ''
where in [d] the multiplicity of (E [d) is 75
22

---

Published as a conference paper at ICLR 2025
If specialize it to the case where f log 9t-1, 2t-1, and μ Pe. we need the following lemma to guarantee the validity of Taylor expansion for 2 Lemma 6. Fix t 1. For any Qo (not necessarily having p.d.f. w.t.. the Lebesgue measure), given any k 2 and any vector of indices a E [d],, qt exists and 10 log qi (xx) < 20, Vx, E Rd (which possibly depends on T). Further, qt and log qt both analytic.
Proof. See Appendix F33
Thus, by Assumption and Lemma 6 since log qt-1 1o-4:-1 is analytic. its Taylor expansion around
Ft-1 = Rr is equal to (cf. (16))
St,1-1 (V (0 v V log (xL 1e) + Σ 2, (19)
and the Taylor expansion of Gi,-- (#e, 12-1) around 21 = 14 is (cf. (7
- (V log 1 va V log (2)) He)
1 + 2 (a1- -e)
Me) 42 log Loggn-1(())
a1 Bi Bi)
(I1-1 -
-M)) Me)
a1
(log 11-1,
(20)
p=3
In order to differentiate the second-order terms in 19 and 20)
we reserve T2 for 19 and employ
for 20
Tgogog qt 1,
(3 101-1- --] pO)T l log 9t 1
B₁ at
(xt-1 pc)-
Compared with the tilting factor for the regular process in Ç,,--1, additional term that is related to E, (and thus B,) is introduced in G From the perspective of Taylor expansion, we can further control the second-order term in the Taylor expansion of log 4-1 around jr through this extra term, which improves the accuracy of posterior approximation at each step.
To use Taylor expansion to upper-bound the reverse-step error in 13 we first note that, for any fixed
It.
Ex.-i log (a-1je(X,-1) (at)) p/. p/ (X (20)
Exx-inQ:-- [(,,-1 log Ex, ppp 1-1 [efte-1]]
= Ex, 1~ [S,,-_] - log E Ex. P P/ (c
< Ex, 1-Q [ Ex -11
log logelie-
= Ex - -ap_]-Ex__--PP P [S,
(21)
where in (i) we use Jensen's inequality and note that log(:) convex. In the remaining steps, we analyze the expected values of the tilting factor separately.
D.4 STEP 3: CONDITIONAL EXPECTATION OF G,,- UNDER P
With Taylor expansion around the posterior mean, the calculation of the expected values is reduced to that of all the (centralized) moments. To start, it is useful to examine the rate of L-as, A direct implication of Definition is that, with some constant C1. since ag > 0 as T + 0o,
(1
Oge) P
CP log T/TP
(1-C, log T/T) $ - at),, Vp.q 2 1,
(22)
Below, we first calculate the centralized moments under Pi-ije- We employ Isserlis's Theorem for our help, which constitutes the main idea in the lemma below. Note that the results this subsection hold long Qo has a p.d.f..
23

---

Published as a conference paper at ICLR 2025
Lemma 7. Fix t 2 1. For brevity write Z, Xi-1 14. Vi [d]. A Ar(x)). and E||] Note that we have A (xt) (= (1 - ar) for all i.j [d] Thus, the following results hold: vp 2 1,
shorthand for 1x_ H. under Assumption
E
II LiEa
Z;
= 0,
Va : |a| odd,
E
II
Z
Öcr(Qu) (1)))) 4
Va: |a| even.
Liaa
Specifically, for i, k, E [d] all differ, the fourth moment is
E|Z
0t
(1 + A1+)
0t
1 ax
Z
A (1 A")
04
B|2
01
(1+ A ( + AD) + +0
BiZ,2,Z1] =
at
(1+ A A +1 -z)
222,2,2,1 Ô 00 a1)))
For i, E [d] all differ, the sixth moment is
3
E 15
Or
(1 + Anj
Ct
1
Z
3
(1+ A A + A²5) ((- a1)))
((-())((-aa))))
at
1 at
(1+ A A0) Anh) + 0
and EE
[heea:a|== [
= -a)))) otherwise. All the rates are under Assumption 5
Proof. See Appendix F.6
D.5 STEP 4: CONDITIONAL EXPECTATION OF Ç1,1-1 UNDER Q:-1]c
Although each Q is conditionally Gaussian, the posterior Qt-1je not Gaussian in general. In the following, analyze the posterior centralized moments under Q1-1j using the idea of Tweedie's 's formula Efron (201 lb. Then, we apply them to analyze Ex, 1~Q.-1 1- 16) again using the Taylor expansion in 19p. Again, the result more generally applicable to non-smooth Qo / 2 due to
Lemma 6
Lemma 8. Fixt 2 1 such that qt-1 exists. Define He == T-ass St, and
<(t)) lloog qe
Cft 5t
1
||
12
d log (2 o4))
(23)
Vas
20c
2
Let 1 S k,j,k, < d, which are possibly equal to each other. The first 3 centralized moments under
Q Qt-1jt satisfy
Ex in [Xc-1] = -v VK= =
1- at Ex [(X--1 -x V2K=
1-a1
(1 11-au a1) V
11
log (x+)
0t:
a1.
Ex, 1xx00 in (Xi: - -
24

---

Published as a conference paper at ICLR 2025
(1- 0x)) (1-oz)²
= Bx [jan]
Ex,,q, 10j log (: - = -a1))))))
3/2
04
The fourth centralized moment satisfies
Ex.-IXX1- (xL - 12) 1z) pb)
SeinRil00p0 (00) (0 + (0 (0. + (0)x))) + [ighin)
2
1-oi 3
+((1 - )1)
fi= == = k =
1-
+ +0((1 - aa))))
-
(
a()))
otherwise.
Note that all derivatives above are w.r.t Tt. All the rates are under Assumption S
Proof. See Appendix
F.7
Lemma 8 also justifies the expression of μr and Σ, in the diffusion process (i.e.. 3 and (4
which
match the posterior mean and variance, respectively.
Next we turn to calculate the fifth and sixth centralized moment under Qi-1i+ again drawing the idea
of Tweedie's s formula (Efron, 201T). This is a direct extension to Lemma 8 Lemma 9. Fix
such that q:-1 exists. Fix #t B... Under Assumption definitions of ia and n(tt) as in Lemma the fifth centralized moment is
5 with the same
Ex, Q-Q [(xi_ - -xXxx-1)XX - -x)(x==--))X= [(])]
Σ
(0 (1)AA)m)))))))))) + Bx - 1aa--00nne 00. (z)))))))
SE( (E(thaidgmm))
where, given a set A, we define
(
( a1, 02 E A, an # }2).
Let Pk be the set that contains all distinct size-k partitions of [n]. Define partz = [((as, az) {i,5) E Pp p P
The sixth centralized moment is
E Ex,-i~Q m1
-
--4 (XT= - -17²
Σ
x)) k) + 00r1)))(1-
(aar (aart)))aarty((......... (H..k.l...))
15
l-ai
)er(e))(1 - -)))"),
if = j = k === m=
+ (11-0))) -)))
ifi (1--))))
m n n
Dr
1-ax
+ ((-aa))))
ifi vi=l,j- = m, k = n while i, & all differ
O
(=())(((-aa)))
otherwise
Again note that all derivatives above are w.E.f. Zt.
Proof. See Appendix F88
The following lemma provides the correct order (in terms of (1 ax)) for all higher-order posterior centralized moments. In other words, this shows that Qr-1je has nice Gaussian- concentration.
25

---

Published as a conference paper at ICLR 2025
Lemma 10. Fix and p 2 2. Let (a1,..., ap) [d]e be vector of indices of length
Under the same conditions as in Lemma 8 if is odd.
Ex, X. (x m()) = =Ō (1)))
va E [d]. on)) ++)
(24)
If p even,
Ex, 1x L.
a xx - -14
=O((1 =)) Va E [dp.
(25)
Proof. See Appendix F.
D.6 STEP 5: BOUNDING TERM 3 REVERSE- STEP ERROR
We are now ready assemble the respective moments into the final convergence rate. the following lemma, we use the results in the previous lemmas to control the difference Ex.-i-Q--mp S
Ex, 1-P (-1lt Lemma 11. Suppose that Assumption 5 holds and that 4-1 exists, Then,
- [S,, in (2T).
Exi~Q (Ex- Ex._iPP [Sc,0-1l
(1 - 03
Exi_q 10/A log ()))(((()))))0) log (Xi))
+0(( ai)t).
3la,?
3/2
Proof. See Appendix F.10
Therefore, under Assumptions 2 and we combine Lemma and 21 and get
log (X
Ex Ex--1XX
p/. 1/- (X,-
x (1 a)) a1)$
Ex 10 log ( log (X.)). (26)
tJ.R==1
This completes the proof of Theorem
Before we end this section, we provide an upper bound of the reverse-step error when the conditional covariance of Pt slightly perturbed (see Remark 3).
Corollary 3. Suppose that Assumption 5 holds and that q-1 exists. Suppose that the conditional covariance of P/ 1/- is slightly perturbed, which satisfies
E.(x;)= = 1- (La A
where Ex(X,) = Öcr(e ((1 - a1) for all r 2 1. Then,
T
log 9:- ( (x,)
Ex Ex,-1X m1
P/-11/ (X1-
$ - an) Bx
Ir (22 q ( ai V2 log (X,)) Log Ex(),)
(11 on)
Σ
Ex,~Q, log a- l log aoga(( (X.))
=
-
Proof. See Appendix F11
26

---

Published as a conference paper at ICLR 2025
E PROOF OF COROLLARY 1
Therefore, it remains to upper-bound the mismatch between Qo and Q1. In the following lemma we provide such common bound in Wasserstein distance, which is provided only for completeness.
Note that @ always exists and is analytic by Lemma 6
Lemma 12. For any Qu.
W2 Q1) = (1 - (M2 1)d.
Remark 4. If - 01 this implies that
W2(Qu, 01)² ~ ód.
Proof. See Appendix
F.12
The proof of this corollary is thus complete. A consequence of Lemma 12 is that, in order to obtain convergence guarantees for general distributions, between Qo and Qi (in terms of the Wasserstein distance), and 1 - Clz, AI 2 2 as controlling the mismatch between Q1 and P1 (in terms of the Kl.-divergence).
view a controlling the mismatch
F AUXILIARY PROOFS FOR THEOREM 1 AND COROLLARY
In this section, we provide the proofs for those auxiliary lemmas in the proof of Theorem and Corol- lary
F.1 PROOF OF LEMMA
First, note that
(T(T) =
Also note that the function f(x) = x log(z) is convex. Thus, by Jensen's inequality,
/ SEe-EEEx-oi (xxo-oolurooeerxXX0 log Exo~ (ur Xo))drr
Exe~Qr [loger(A) (Xr)
< / Exo-Qo [ero(=r] log (x Xo)] dor
Exo~Qo /f @T X log (ri
Since Qr is conditional Gaussian (VVarroo (1 Ta), its negative conditional entropy equals
/ qT (T(((T122)) log ( doy =
d log(2 āT))
2
for any To R.d. On the other hand, since Pí NO0 Ta),
Ex Dlog (Xr)) log(2n) Ex |1
where
E 2x |x = 5z Qx |ool + (1 oq Bwr (
= -xTExoQQ |ool + (1 (1 - ar)d.
Putting the two together,
log 9T (XT) ply (Xr)
Exp~Qr
Exp~Qr (log (oggr(Xx E Exy~Qr [logrr(XT))
d d
d
1
< log(2 (gg(2i((1 -TT) log(2T) + (aTExx-Qu ||oll + (1 -a-aa) 2
2
| dāt
d
örr ExoExo-
2 log(1 ar).
2
When T is large (and thus when or small), the Taylor expansion w.r.t. ãz around yields
log(1 σT) oō O (a+)
27

---

Published as a conference paper at ICLR 2025
Therefore,
log qr (XT) 1/y (Xr)
dāT d
E Exr~Qr
< xarlExo-oo ||olll
2 ( + + (a
2
Σ 2 ar 10 (a²).
F.2 PROOF OF LEMMA 4
To start, note that both P/ and t-1 are Gaussian (yet having different mean and variance). Thus, for each t = I....,T,
(1
log P/-1 (21-1 (xz)
log
(det (Fx) (xx)()))= - -log det (Sx)))))
2 (EL-1 M2)" (x1-1 14) + (x 11))))(((1000
1
1
)v))) T 1 -Pe))
(oog(det (Ei) - log(cet(22))) (2x)))
+ (at-1 (2, 2);1) (x -44 m4)
2
2
1
+ 2 (xc-1 - -pee (x0-11 - 7v)) (x - " ' - He)
2
2 (log(dot(E)) (E.)) log(dct(Ee))
1
(xi-1 11) ($, Σg (2 - 111)
+ + T (x1-1 Me) + 2
1
1
(It-1
T (me (a) +
1 _ -me) (Me pc).
(27)
There are five terms in (2 We first consider the third and the fourth term, for which we have
Ex--1-Qi-ile (m Tv.)T E, (X+-1 -mo) (14 T5 Ex 1 (X me]
Ex (Xr-1 (e) T "Ne n =Ex [Xc-1 - Mel E5 (mr (ar) O.
Now consider the expectation of the last term in (7). From the definition of E, in (6). for small 04 we have Σn > 0, and we can define B, := Ia - (Ia a1-1-a)100 H.) and thus E, 1-a; (Ia- Bi). From Taylor expansion, we have B. = (1 - a.) + 00 )² Thus, for each / 1,
Ex, Ex,~Q, [mn(X,)) (x.x))) (x), (x.)))
(1 1-0a))xx (x))Ex.~02 (sx(X.) - Voogo
B.(()))(ss(X)) -1----//(//)))-----BLLL/))--)-00 (loga)))))) (xo)
(1
[(x((x,) (X)) + - (x)) (sx({)) Vlog (X.))
& (1 as Ex) [|s - Voog (X)))
where the last line follows from the regularity condition on H, in Assumption expectation the last term (27) can bounded as
Therefore, the
T
Exinq. (Mr(Xe) Ex())) (XX -
T (1 (x V gX.)11
(log T)
(28)
where the last line follows by the score estimation error in Assumption
3
28

---

Published as a conference paper at ICLR 2025
Next we turn to the first two terms in 27 First, note that for all i E [d], we have (1 (1-a))HH (Xt)
(c)(Q.) (1 (4) under Assumption Now, the first term of (27) is given by
log(det({2:) (og(dee(EE.) = log(det( -o)) H.)) log(det((a
V log 4 (x:)))
When (1 (4) is small, can Taylor expansion for the functions det(-) and log(+) to get
log(det la + +1++(1111)) (1-a0) Hi)
=log 1 + (1 a1- + (1 =1)²
(1- (Tr(H,)² - Ir(H,)) + (1-
2
(1 (H,,) + (1 o1) (Tr(H,)2 Tr(H??) (1-o,)²
Tr(H,)² 00 - oz)"))
2
2
[1 a1) (H; + Ōcr(q ((1-a)))
(1 Tr Tr,
Similar expression can be obtained for log(det(La + (1- V2 lo Thus, the first term in is equal to
log(det (Ex)) log(det(Ex))
(1 oo)) (T((H? Tr((V2 log (xx))
= a1-aa: (Tr(H,) Tr( Tr(V (o +1cm(Q.((1 - (
2
For the second term in 27 we first take expectation over - and get
Ex, 1-1 (X1-1 1X-1--193 - E, (X. mm) Tr 1
To proceed, note that
(1-+(1-a)))
(161)
la (1- a1) +
+ (1-aa)²² (1 2 0 (
(29)
To (iii), write S₁ the true inverse of Ia (1 0z) 02) Hy. Its existence is guaranteed if (1 a4) small. Since
(Ia (1 (1) H, + (1-
(1- Ia (1-
we have
(1+
(1
+ (1- 2 - S)) = ((1 a3)3)
which implies that St = Ta - (1 - oz) + (1 21 H Ózr(e. 31)3).. This shows the validity of (iit). Therefore,
Tr (ET - )) )1)
Tr(E, 1
Σ - -aa)
= =Th( [a - He + ax)² म + (1
[Ia + (1- az V
log [x:)] Id
(1 an) 2
TT(He)]
+ (1 o.)² (T( - Tr(H, log ge (xx)) + Ô ((11)) az))))
Adding this to the first term of (2 and taking expectation X, Qs (noting Assumption 5 heree). we get
Ex Ex..I.i (11g0_....11((0 (log(dot(E,(x))) log(ddc(EE((())))
- (X,-1 (x.)) -x,)) (xx(
(1 2)) Exinq. (x,) (X) loga + ge
2
29

---

Published as a conference paper at ICLR 2025
+ +((11aa)) -01 a1)²)
(iv)
(1 az)² Ex (x.)
V 2o Ö(11 -4,)%)
2
where (iv) follows because for two symmetric matrices A and B,
- + =
Tr(AB) Tr(BA) + Tr(B²) Tr((A (A - B)) = () B)) ||A 1-A-
Thus, following from Assumption 3
Ex, 1.rDi ..I
- -ogg(ee((,(()))))
+ (X-- - (x (x.))) x log" T
EH
(30)
Here En the Hessian estimation error. Combining 28 and (30) yields the desired result for the accelerated estimation error, which in the order )
F.3 PROOF OF COROLLARY
Given the perturbed Σ, in (9. following the definition in 14p. we define, vp 2 1.
A, = (1 a.) 2 log (x;) + (1 a²)²
(v² log qt (z,))
4
= (1 - ar) V2 (e()
+ a 2² log (21)
4
1 ai 5--1 = Ta
B, La
A. + A
(1x)))))
at
H, = He +
an H
4
Note that under Assumption 3
(1 ar)
|.. $ (1 a1) H. (1 (01-aa) a.)² |H.ll Óc at), Vr 2
Then, the rest of the proof Lemma still holds with V log de (x,) and H, replaced by 2 log qr (x,) 1-ai 2 log (xx) and He The proof is complete by noting that
22 log gr (Xe) + 1 2 log (Xi) 1 4
Ex.~Q. [i((x.)
(1+ (x)1-a)))Exx@g H((x,) - v² 22 (x)))((X))l???
F.4 PROOF OF LEMMA
By Bayes' rule, for any -1-1 given fixed IG, we have
(1 l
[1+ Varete-11 11??
x qt 10-((x;-1) exp
2(1 - an)
11-1 I2/ / Va
x ( ( exp
5 (5 - (1) - mr)
(xxe1
2(1 art//at
||-111 Ft/
04
= - (2 exp
(It-1 ( B.) - -1+)
2(1 a.)
2(1 (xx)//or 10x
30

---

Published as a conference paper at ICLR 2025
(by Equation
14
1/- (z)) exp (20-1((11
Q4 2(1 - at)
(xt-1
( (1(2)-1-H1))
where the last line follows from the definition of (e,- (Iie; (1te; in 16 Now, with the definition of (x)-((122e11) in (17 we have
01-110(Fe-11 (2x))
Ex (e ((venXe-s))
F.5 PROOF OF LEMMA 6
Recall Equation (2). Let Qo denote the distribution of va, and let g(=) denote the p.d.f. (w.rt. Lebesgue measure) the distribution of -I- de Note that g is scaled version unit Gaussian p.d.f., and SzeRo g(2)d2
Now. for any event A S (()).
L Cc(A) = -Jrss JENER g(x To ddoo JEDERS VrEA g(x
g(x - 5o)dk) dQo(3o)
by Fubini's theorem. A has Lebesgue measure by continuity of g(z) we geget Sre g(x uo)dz= and thus (A) 0. This shows that Qe absolutely continuous w.r.t. the Lebesgue measure, and its p.d.f. exists, denoted as
Now, since any order of derivative of the Gaussian p.d.f. is bounded away from infinity and Qo is probability measure, we can invoke the dominated convergence theorem here change the order of derivative and integral as
(x) = 0h / g(x 2o)dQo(20) = J dág(E - 20)dQo(āo).
(31)
ZOER"
Thus, for any h: 2 and any vector of indices a E [d]* we have
/
(0)(
sup
dQo(To) sup
(1g(()) 00.
#ERd
FOERR
ZER
This also implies that the Taylor term (I 00 for any and μ. and
(x(x)=
JEDERE gl -o)dQo(To)) (1)
lim p-+00
Telo(x Zo), 13)200)
1=
lim
Thlg(z- -io). 2))20(0())
ER k=0
(s88)
lim
k=
where (i) follows because (scaled) Gaussian density is analytic, (ti) follows from dominated conver- gence theorem and the fact that g is a Gaussian density and has an upper bound independent žo. and (Mi) follows from 311. This shows that qe is analytic.
Finally, since 8k log is a smooth function of gr, O'....... Ihe gt, we have @ ge(r)) < ao (possibly depending on T) for all
and fixed (finite) v, Rdd Also, log qi is analytic because log(-) is analytic and qe (xx)) > 0, Vx, E Rd.
F.6 PROOF OF LEMMA
The result follows directly from Isserlis's Theorem, which says that
E
Z = Σ
II E|Z,Z,] = Σ II
Cov 2,) PEP: {i.]eP
PEP3 {R,j)Ep
31

---

Published as a conference paper at ICLR 2025
since each Z is centered. Here PR is the set that contains all distinct size-2 partitions of [n]. For example, Pf {((1,2 2), (3, (3,4)), (11,3), (2, ((1,4) (2,3))). Thus, since A, (Q)
ar) under Assumption
E
2
0, if is odd
) =(r
E
II Z
=
Õcr(Q)) ((1 (1-aas) a1) (l1oa))), if even.
More specifically, following from Isserlis's Theorem, the fourth moment is
2iZ,Z,Z,Zi Cov( Co) Cov Z3 Cov Zi) + Cov Zi) Zz), Vi,j, E [d].
Here Cov( Zi, Z,) 1-ot (1 (1--a)))) The fourth moment result follows immediately by plugging into the formula. Turning to the sixth moment, we note that we are interested only in the coefficients for the terms that grow at a rate Ocr(q.) ((1 aa, az)"). Since the sixth moment consists of sum of product terms in which three covariance matrices
multiplied (giving us a rate least Ô Ocr(Q.)(C ((1 04)) ))), at least one product term in the sum must take covariance values only on the diagonal of the matrix. Therefore, only T [[ E Z 7 and B[Z Z with i, & all differ satisfy this requirement, and we immediately get the desired result from Isserlis's s Theorem.
F.7 PROOF OF LEMMA g
We first fix and will take expectation at the end. Note that dr xt-1)
(2 (1,)) exp |
2(1 2(1-a.) -1"" Following from the idea of Tweedie Efron 201 1), we have
2e 10-16(20-1102) (st))
(0-1(1(-1)
Q6fe-1 (30
(e((re)
(1-1(11-1) (e(xre)
90/1-1 (1rr00 exp
Voi
xy 1t-1
Qt 2(1 1 oz))
||02-
1- 04
(91-( 2 || exp
Voi
xT log (org)( log (0
1- at
f( exp T x(āe))
(32)
where we have used the definitions of 3. and k(..) in (23). This shows that #;-1 a conditional exponential family given 2,. Thus, the first moment can be found (cf. Prop. 11.1 in Moulin & Veeravalli (2018)
0 Ve, / qt- 10-1 Va, / f(21-1) (
(zT_ k(σ,)) dx
f(1-1) exp exp -x(x))(()) dz
/ (xx-1)exp (2 - x(5x)) (I - V ((xx)) dr
/ ((1-1) exp (x x((r)) ---dd Va,K(T))
which implies that
Ex na [X,-1] = VR.
(33)
For the second moment,
0 0i, f (
32

---

Published as a conference paper at ICLR 2025
= = 11x-11 0i0
a exp (x]_1ā= x(āx)) ( - 0rk(T))) doa-1
= 1(0 exp (x_1 n(āt)) ((L (ct-1-Orn -Lx=)))) - 0gK(āi)) 0ff((E.) da
which yields
Ex 1 14) V 1 at Ia + (1 an)² loo (34)
) for brevity. We remind readers that all derivatives are w.r.t. I, instead of I1-1. For the third moment,
Below, we write x = -t-1 and x = k(+))
0 Oifk 11-1// =: / exx) x))
where
Dz(a, = exp (-x i + k) 02 exp (IT - k) ((x' O,ni((o) - -0,K) -0²
= =(x* - 0xx) ((x' - (xx -kk) - k2
+--ofxx)(== - 0g)k) + (-00fx :=) 02x)) D.
(35)
Now, for any function fm)(;)) and i d.
/
((x) exp (x 8 - k) (n( - acx)do== =0
by the first moment result (33.. Thus, we get
Ex
(xi 1))(x( -x mP:]] =ogAA
and by Assumption 5 Ex.e, xx = Ō((1 - )ox))))
For the fourth moment, we have
0 = 0ijus / 21-1joxx= =: / exx) 8) Da 5. 5.)dx
where
Di(2, 21) exp (-xTie cxp(-x + k.) 2 exp ( K)) ((x' Oxx)( - 0sx)((* Ogx)
8yn(1* 0pn) 02 ( - 0nk) - 87 6(x 0yk) 1 -0G 087
= (x' -xx)( - (x* x - (xk) axk) + 0 a(((' (x' -xx))('' - -axx))( - -Oxxi)
8z - (x))(2' - 0Rx) 6 0Kk) + 87,10f.r
Pynls (x)) 3:K) (a 0₂h) 02
- 8Jnn(x' - (sk - d.R) 8 Saaiaaa dxk) + 8z KÖGr
- Lz - 0nx) DEACK
(36)
and
di -cnk (x)) (x*) - 8kxK)
- - a0 - Oyr:) - Oxx)((*
Oxk) - -pan(o (x))) 0yks).
Using the first and second moment results in (33) and 34 we get
Ex -
11)
(0 (0)))) - (8) + (0f))) + S.n
And the fourth moment result follows directly by applying (34) to each of the terms and taking the expectation over X, Qt- The rate follows from Assumption 5 (cf. Definition 2
33

---

Published as a conference paper at ICLR 2025
F.8 PROOF OF LEMMA 9
The proof continues the idea of Lemma 8 The idea is to use the inductive relationship (provided in the proof of Lemmas 8 and I0
Ds(2, ū.) = exp (-x e + k) Om exp (x x)) D4(ar, Rt))
=xx" 0 k) (2, + 0m (z,
Do(2, kz) exp (-x + On exp (x _ क, k) (2(
(x" 0 (r ).) 0 (2.
Let Pk be the set that contains all distinct size-k partitions of [4. We use the definitions:
(2)
A [a ............ ax 01 ........ A, a1 ....... ar all differ): &: s |A
part (A) {((a;; {i.s) E p) p }
Recall the formula for D4 in (36), which can be abbreviated as (here |a = 4):
D,(x, =
0,K)
E o5 II
(a* 0,x) +
Σ
Brden
iEa
bE(S)
i
(b.c)Epart,
0
aa 0,x) 0g.
iEa
Also recall the definition of f(z) in Lemma and that f f(z)e=1ā "x, = 0, through which we can find the expected p-th moments of Ex--i= [TTia (X; 14]]. For reference, the first four moments are
/ f(x) exp exp) (x - x) (x' 0,x)dx== =0
/ ((T)exp(xTã; x) (x' - 0xx)(x² 0xx)do = 87 =1 - ar))
/ exx) (xoxp(=Tae x.) (x' 0x))( (x* O.n)dR 0i (1-(e))(1-aa))
/ e(x exp (x x.) (x' (x))( - (x² - Oxk)((e Ōrk)dx
= (00))) + (0 + (0% + OJ = Ô (c=(q)((1-au)
where we note that 0h = ( ((1 - )²) for all 2 3.
We can calculate D5 as (with al = 5):
Do(z, Zz) = (x - dag D1 D4 (2, Øx) + 0g (x(
II (xt 0,k)
Σ 05 Il (at 0.k))
Σ
83 b/
II
(at 0xk)
iea
(c)
tEaib
be (2)
+
Σ
of End2k(z - -0xx)
JEa
(b.c)epartz(a)(0)
Σ
0d (a 0,x) + Σ
05 2 -g H.Kk
SEa
bE(2)
Therefore,
Ex
II
(x - mi)
tEa:|a|=5
34

---

Published as a conference paper at ICLR 2025
Σ
Exo a + Σ Sa
Cajonofn
Σ
Exda a + 0%x
(5)
be(()
bE(2)
Σ
abb K + 02k = (0 (1,)))
=
(2
Now we turn to calculate De (and let |a] = 6):
Do(æ, .1) (x - Ouo
k Ds (x, k2) + 0ao Ds 2()
II (x' 0,k) Σ
06
II
(x'
dck)
Σ
0
6 II
(a' dxx)
SEa
(E
t
De
iEb
Σ
01 b
II
(xt
d,k)
+
Σ
Pande
II d.x) + Σ
fu(x)((** - 0xx)
BE
iEb
DE(S)
iEb
sEa
(cc))paarz(aab)
Σ
Σ
Σ
Sg..
(b.c.e)(party(a))
bE(
(b.e)Epart,
Here fn((s) function of which does not depend on æ. Note that fn does affect the expected value because Ex, 1~Qe- [Xt-1- - mx] = O. Therefore, we have
E Ex-11
(X:_1 - ui)
iEa:|a/=6
Σ 05
Σ
Seniexx + Tarons
0a BainnoBn Σ
bE())
(c.e)Epart,(aa0)
DE(G)
+ Σ
Ol aap
OKOPKOP
bE (E(
bE(
(c,e))part,
Σ
Σ
Σ
(bac,e))part,(aa)
bE(
(b,c)Epartz(a)
Σ
of x
Σ
Σ
DE(S)
(b.c)Eparty(a) L Bx K
(b.c.e)Epartg(a)
Σ
(1-():(1-aa)
(bar.e)
The proof is now complete.
F.9 PROOF OF LEMMA 10
We fix first and will take the expectation at the end. We first introduce some notations used in the proof. We write z = It-1 and k x(āz). Given a set of indices A, define its bipartition as
bipart == ((B A BUC}
where B and Crree both sets of indices (and therefore the order of indices within each of B and C does not matter). Here Ll refers to the disjoint union of the two sets (which is only defined when the two sets are disjoint). Next, given a set B, define allpart22 ( B) as a set containing all partitionn of such that there are at least 2 elements in each part of the partition. As example, allpart>2 (f1, 2, 3, 4}) {{[1, 2), (3, 4}}, { (1,3), 3), {2, 4)}, {11, 4}, (2, 3}}, and {{1}. {2, 3, 3,4 & allpartz2 ((11, 2, 3, 4}) despite the fact that it is valid partition. For each partition b E allpartz2 define
Oy
alel
EEb
35

---

Published as a conference paper at ICLR 2025
Here note that is also set, and Oy is well defined since the order of indices to take partial derivative with does not matter. Define
Do(a, [.) ==
(x( == exp (-x + k) Ocp exp (x k) D 12-1(z, zi)
for all p 2 1. We again remind readers that all derivatives w.r.t. I, instead of x 21-1-
By working out the derivative, a direct implication of the definition of Dp is a recursive relationship:
Dpla, k2) = (x"x Da, (a,k)D D k.) + Dag 1p-1 (z) Also, if we unroll the recursion of pp. get
Dp(a, it) = exp (-r' _ + 13 Dap
exp (- 1) D 1 Ite)
= exp (-r + k) Dap
exp ( 1)) exp -xt +k)
8ap-1 exp (x
k) D
2(1, Dp-2(1, mt))
exp (-x1ār Te + k) 80 ap-
exp (x Tz k) 222 Tx)
exp (-r 3t + 13) 08 Di (exp (xT x)
and thus
/ U--11de = / f(x)0 (exp(xTTr x) )
0 = 0% ap
/ f(x) exp (xT - k) (2( Bz d1)d
(37)
where we recall the definition of f(x) back in (32)
In the following, Pp(r, R4) satisfies a particular polynomial form. In part 2, we inductively show that this polynomial form results in the desired rates.
present the entire proof into two parts. In part 1, inductively show that each
Part 1 of the proof of Lemma 10: The first step toward proving the desired results is to obtain the form of Dp for all p 2 2. Now, we aim to show inductively that
Dp(r, R1) = II ( k)
Σ
Σ
().
II
(1 0a, k) (38)
(B.C) beallpart
cEC
where (b C') is a constant from combinatorics, which is possibly 0 and which only depends on From Lemma [ the bases cases have been established that (cf. 33) and (36))
D2(0, (x' (x))(x) 0zk) 83
Dz(2, = (x² - 0xx)(2² - (x² 0kk)
-G 0nK) Har 0rk) 0 kx - 0.k)) - ju
D2 11 ūz) (x' (z) (x*) k 2xk) -Dx))
Bf * - (ax 0₁k) - 02 (xx) - -Oxx) 07 0. - 0,x)((² - -ix)
+ Oii(("' (x) - (2* - -0an) - 03 K 3ix) 02 -dak)
-fal - 0gnk (2 -0,n) + 0g n.00 K + 02 K0G + 02, nOGnn Dighet.
In particular, each term of D, (p 2,3.4) 4) is in the form of either [ Oa, k) or
(0,k) [o k), where [g| 2 2, Vg E b and (LeeetE) L = [p]. Therefore, Dz. Dr, Ds all satisfy the hypothesis 38
36

---

Published as a conference paper at ICLR 2025
Turning the inductive step, suppose that Dj satisfies (38, i...
k D2(2, F4) II [x k)
E
Σ
du(b, (O,n) II - k).
(B, (B,C) (M)) beallpert>2(B)
Then, using the recursive relationship, we have
DR-1 (x)
= =xxat1 Dant, H.) (I, F6) + Ousti (x Te)
k+1
II
(x Da.k))
Σ
Σ
de(b, (8,
II
(1 da (z) Daxsi K)
i=1
(B.C)Ebipart((K) beallpart
CEC
01
II (x) 0a, Ri)
E
da ()(bn)
Oan II (2 0ack))
(B,C))hiiarrt(4) beallpartgg2
T3
24
Σ
d& (b, C) ( (8bk))
II
(I
(c,
(B, (B.C))Ebiarrt(k)) beallpart (B)
OEC
T
Ti - 72 T3 T4 T,
where we define each term as .i...., ,,. Now we discuss these terms separately:
1. Ti (and only Ti) in the form I
x++ (x - -0,
2. T2 is summation of individual terms: (0pr) (x (x) Sag R). Here b E allpartz2(B (B) and (B, C) bipart((k)). Thus, by definition of bipart and allpart 22 for each & E b, |5l 2 2 and (Ugge&) L C = [k). Therefore, k & B L C and
(LlgebE) UC L (k + 1} = [6] W + 1} [k: 1].
This implies that each individual term of T2 is in the form of (0px) ILee, (x- where E allpart>2 (B2), such that B3 == B and C2 = C u (1: + 1}. Here C2 is well defined because le + & C. Since (B2, C2) E bipart( + 1]),
T2 (B.C)Ebipart ([++]] beallpartz2(0)
Σ
Σ
d2 (8,k))
II km,
cEC
for some constant d2(b, C).
3. Ta is the derivative of product, which is summation of individual terms: (02 (i s:) - j= l...., Therefore, for each 1,... each term is
of the form (0ak) ITEEss -o. where b E (llpartz((Bs). such that Bs = (j. k+
and C3 = [k] {5). Since (By, Cs) E bipart((k: 1]),
T3
Σ
Σ
(b, (8,k)
(x - 0a,
(B.C))bipart beallpartza(1)
cEC
for some constant da(b, C).
4. T4 is a summation of individual terms: (0xx) (Dor.: Io :a),))) where e
allpartz22B5 (B)) and (B, C) E bipart ([k]). Now,
(0xk) (aet: II (xx= - 0i. - (02 CEC
ay.a (02 x) II (2 - Og,
iEC
37

---

Published as a conference paper at ICLR 2025
-0bh,,k)
II (x -o,kk)
iECa
where 64 := { + 1.c) and fc}. Here by is well defined because & + 1, c & b.
Define B4 |k + 1] C4, and we have by E allpartzz(Ba). Since (Ba, C4) valid
partition of [k: + 1], have
T4
E
Σ
d4 (0s,k)
II dEC
(1 [I
(B.C) bEallpart
for some constant db, C)-
5. 73 is summation of individual terms: (aax (0xx)) Hoc - Dor where b allpartzz2(2 (B) and (B, о) E Dipart((k)) From definition of 0e
Oosts (0oks -Datii
II g FEb
Σ SEb
(als++ Ogiate1
all Σ II ÇEb CAfE
Doe
EEb
where, for each & E b, we have defined new partition bg such that & + is added to the 1]}, which is well defined because ø (b g)) and + & B. Define B, = B Ll {k: + 1} and Cs C, and note that (Bs, Cs) is a valid partition of [k + 1]. Since |<| 2 2, JÇ E b, we have K' 2 2, AÇ' e bę- Since b E allpartz2(B)) we have bg E allpart (B₁) for all & b. Therefore, for any
& in the partition b. Formally, define bg == b E {k:
fixed C(= Cz)
Σ
(b, C) (Danys (0xx))
E
Σ dd.(b,C)o.
beallpart-2a(B)
beallpart (B) ŞEb
Σ
ds C)O,,k
b. sallpart
for some constant do (bs, C), and thus
TB =
Σ
Σ
do ()(xk)
II
(x - -o.k).
EBpC))bipart((k+))) beallpart
CEC
Finally, letting
j=2
for each b allpart22(B) and C such that (B,C) E bipart((k 1J), we have shown that if (x T,) is in the form of 38). D (.) is also in this form. Thus, claim 38 is valid for all p22 2.
Part 2 of the proof of Lemma 10: First, remind readers of the definition of <(āx) in 23 Also, the partial derivatives within the expectation over X, ~ Q do not affect the rate by Assumption 5
Note that Vx M4 from direct differentiation. From 37 and (38) for fixed xe, we have
E Ex Q. m1
II [x 11tt)
=Ō
Ogx(Tr) Bxx
Il (x m22 -
sup
(B, b()part)))))) beallpartza
LEC
I (X 1 (1/0)) - (39)
=
sup
sup
0sk(Tt))
Exi-
(P.C))
(Eallpartgg.
LEE
38

---

Published as a conference paper at ICLR 2025
We first consider the term supbeallparts.115 0gk(āt). Given partition b E 22 direct differentiation yields
@ 1 1- ae +
(1 -l-ay) ar)?
Ou log (x = Ō(1 (s), as), if [ = 2 and E1 = E2
Og
0 (1 - or))
_ log q (z1) = - (4) for all other &.
14//2
at
Since by definition 0b IL de k and LigD = B, the slowest rate of θ, (as function of B) is determined by the partition b containing the most number of equal pairs. The slowest rate is
( (1 - 02) (18 - ax) = Ô ((1 - az)
if [ is odd
Opm(TT)) = { Ö - (11-a,)18113) sup b (B)
if B is even
To proceed, we will again use induction to find the overall rate. From Lemma 8 base cases have been established that
2
Ex
Ix
14
Ö(1 ai), Va E [d]
3
[xp= 14
= Ô 0 - ((1-))))) Va [d]²
4=1
4
Ex 1.1
II
[x
14
= Ô - (z)-))))) Va E [d]..
i=1
These rates satisfy and when 2.3, 4. Now turn to the inductive step. Suppose k > 4
even. For purpose of induction, suppose (24) and 225 hold for all p = 2.... k. Then, following 39 for p 1 1 (odd number), we have
R++
Ex
II
[X - 14++)
=0
(1 - az) (18+5111)+ (10))
sup (app)ibaaat(((tt)] [i] odd, [C] even
(1aa)) 1B1/2 (B//2111/2(11 (1)1101333/2
sup (B, (B.D)abi [B] even, |C] odd
=0 (1 az) (x+t)(++))) (1 0 - a4) (
Then, for p k + (even number), we have
2
E Ex
Il [x - -1:1 (((1)
=0
(1 a.)
sup (B. (B.C))bbpaatt(k+-P) [B]] rdd, CI odd
(1- (1-x))! 11122 ox) 0112
+
sup (B. Cbipart [B] even, even
0 (1 az) (1+
+ (1-11)))) (
0 az (
These show the validity of the claims
24 and
25
The proof is now complete.
39

---

Published as a conference paper at ICLR 2025
F.10 PROOF OF LEMMA II
Before analyzing the rate of each moment, we need to guarantee the validity of exchanging the limit (in the Taylor expansion) and the expectation operator. Intuitively, this is achievable under Assumption 5 where the Taylor series is absolutely convergent in expectation due to its Gaussian-lit moments. Specifically, since log q-11 analytic, all its partial derivatives exist. Following from the Taylor expansion of -,--1 in 20
lim
E X
[6, - E X PI-1
Ti (log X uz) + (1og Qr X1-1, (t)
XI-InPf-111
Tp Q1-1, X1-1,.
3=3
< lim E
Xi^Qi Xi-inff 16
S,,--1 - Ti (1-- -To 1, Xc-1:
k00
Tp (log Q1 9
lim E X
[pog q XI-1,
k000 Xe-INff-ie
p=k+1
1 lim lim inf
Σ
X.mR. XI-InP--11
[log qt- 1- (1-1,1,))
k00 80000
p=k+1
(i))
0.
Here (i) follows from Fatou's lemma, and (it) is because, under Assumption and Lemma 7
have Xy~Qu (log -t-1, X,-1, 14)1 Ô (T-P/2), and thus the infinite sum is convergent X-11-P-11k
for all (k, E) such that 1 < k <<< 0o since
de
ΣE X N, ImPi-1
[7,(0g =
TB/2
The proof for E XimQu is similar due to its Gaussian-like concentration of all centralized Xe-1aQ II1
moments (see Lemma TOP. Thus, are able exchange the infinite sum and the expectation under either P/-1 x Qt or Q1-1.
Next, we put together the rates of the conditional moments. We use abbreviated notations as Tp = (log X m4). To investigate the dominant term, we analyze the expected difference of the first 8 moments in the Taylor expansion 20 separately. First, for any fixed zt.
Ex [Ti]
Ex [T]]
Also, for 77, note that for any random variable Z (regardless of its distribution) with EZ = 0 and Cov(Z) 2) the mean of the quadratic form (with fixed matrix E) is
E = (ZTT(( = Tr (EE).
This implies that, for any fixed Zt+
Exp P/ [Tg]
Ex..~P/ (X,-1- -4) (22log ar 1
at Br (X,-1 m12 a4
2
((
22 20 90- - at
1-20 at Br Ex
- Th
2
ExcINQui
(x 14) ( (2logg0-1(44)
at ABB Be (X -1) -wa
a-a
40

---

Published as a conference paper at ICLR 2025
Ex ~~Qr Qe- T2).
Using Lemmas and B the rate for 73 is
Ex,qu (xx 1 - Ex.-inPP (T2 X,-
IIx-II [Ts(log N,,,,,,,1,1
(1- a1)3
Σ
Ex,~q, (o log 9 (14 (X)))) log (X.))-
3l0, 3/2
6.1k=1
Using Lemmas 7 and I0 and when the partial derivatives satisfy Assumption | and (p 2 8) can also be determined:
the rate for Ts, T7.
Ex,-Q (Ex, 1~ -Ex, IMPi-..)
-Ex-nxX--111. 1,
=ō((1- - a;))),,
Exie (ExI-INReaii - Ex PX..I (1100oge-11 1--1, x1-1,14)]
-Ex--iXeN [T7(log 9--1--1111 X1-1,
= =Ō((1 -ai))),
Ex.-q (Ex. (xx-11 Ex- [Tol at (x-1,
= =Ō((1 - az) 1), vp 28.
The remaining orders are T4 and Tg- The following proof will draw from the results in Lemmas / to Fix p 2 1. Write Z, Xi 14 and A = [A.]* for i,j E [d]. For T4, let i, E [d] all differ, and the difference (in expectation) of each term of T4 is
E Ex--iQQ--1 up [
-
E
[2,1
1-11 111
33
1
a1
2
11a))
ax)
82 log (xz) -3
at (3--))))
1 (1-at)
2
(1 (1+ A") + Öcriq - ((1)
of
az
2
=-3
(A
Öcr(q.) ((1-az)*).
at
Ex. Ex 1 111 [2322
Ex
E
[2,2,]]
(1 - a1)3
8g log (Iz) -3 (L-ai)
= 3
A + A + Õeria ((1 aa))
ap
2
=-3
01
A + Ōcr(Q.) ((1))))
Ex [3
Ex,-x 11 [272
1 1
2
(1 xz)
(8 log (zx) + 08, log (ogg((z))) - (1-ar) 2
)) (1 (0 A3)
of
02
+ +
((1 ((1=
(1=00
A + + ((1 a.))),
C41
Ex, 1~Q1-11 127 27/22211 [k]
Ex, 1Pp 1 [z
(1 az 82, log (z()
1 (1-at)
at) )
2
(1 + Ai* + + (11aa)))
a
(1 a2)
A A Aih + + ((1-a))")
af
41

---

Published as a conference paper at ICLR 2025
Ex, 1- [ZiZ,ZzZi] Ex, -x._ [ZZ2ZZZ1 (r((Q.) ((1 (1-aa)) (a1-))))).
Recall from 14) that A, (1 log
(x = (2F(Q.) ai) under Assumption 5 Hence,
many loweorder terms above are cancelled, and we getet
Ex 1- Ex Pxp-1 (Ta ot X1-1; mc]] (c((q.) ((1 (1-ax)") oz)
Now we turn to Tg. Let k E [d] all differ, and the difference (in expectation) of each lowest-order term of Tg is
Ex Ex
|2,1
Ex._i
12,9
1- 0't
1- Cxi
3
15
15
(1 A") " 01 as)t)
04
at
Ex
[
231
Ex, 1-P/-111 [Z:2
111
3
=3
a1
-
3
1-a1 a1
(1+ (1+ / + +0==)=000)0))
Ex
-x--1Q1--11
7
PEx--IPP 1- i11
3
0f
(1+
+ (1+ + -
O2
Also, by Lemmas and 9 the rest the terms already satisfy Ô cr((q ((1-a))t) under Assumption The low-order terms cancel in the same way for T4, and thus,
(Ex-i~Quu - Ex..IPP...)) (T
XI-1, = Ocr(Q.)(1 oz))
az)3). The proof is now Therefore, the lowest order term above is T3. whose order is Ô Ocr(qu((1 ((1-as))) complete.
F.11 PROOF OF COROLLARY
The proof is very similar to Lemma 11 and (1). except with a perturbed covariance matrix. We employ the notations A, and B, from Remark Here have that A,(X,) A,(X,) EX,,) and thus, Vr 2 1,
(x,,,) (x(),) Õcria ((1 a,)3) A,(X,) Õcriq ((1 az)
= =(1 -1-oa ar) 2 log (X,) + (c)(q.) ((1 (1-aa)) ())))
Compare with the proof of Lemma 11 the only difference is the expected difference of T2. Since (X,) A,(X,) Ô (o()))) ((1-a;)3) a) and B,(X,) B, (X,, + Öc-(Q)) ((1-a,) a,) the expected differences of all higher order T, 's have the same rate as the non-perturbed case.
Now, for any fixed xa and 2
Ex.-iNp
[T]
2 Ex m1
(X1-1- ~1) V2 (22 qr (He)
Ot B,) (Xe-1 - mi) as
( 122 log - 1 1-a0
04
Be Σ
= 2
and, from Lemma 8
Ex.inoL-11 [T]
= Ex, 1- (Xt-1- -4)1 2 at le ((r)
at Br (Xe-1 - -
2
1 a4
(TT(((2oogaa111) (ogggg(((11)) - 01
Tr
Eg
42

---

Published as a conference paper at ICLR 2025
Thus,
Exx 1~ -Xx-r [Tá(log qe- 11,
1 Tr
p 1ologg-
aBB
at
(Ii -s,)
-1 04
((V2 11
Bi) Er
20x
1 1- att
1 1- (VV2 1(4) 04 22 ge (Xx)) E.) + Oct(.) ((1-a))))
20%
Note that here the first term is in the order (Q,)) ((1 - (a1-))))) under Assumption 5 since (x(),) = Öcr(Qa) - (1))) Therefore, under the perturbed case,
Ex
Ex Ex. -Xx---PP
.I) [61,
1 a' Ex,-Q ((V (V ( - le Ex.))
204
(1 a1)3
Σ
Ex.~q.10
log q ( log (X())
3la,
3/2
ij,km
+ Õ(1 oz))).
The final result can be achieved using 21 The proof complete.
F.12 PROOF LEMMA 12
From D the forward process at the first step is
I1 va + v1 ai
where wh ~ (0, Ia) independent of Qo- Thus,
ExixQ1Xo~Qo ||x
Xoll2 = Bw. / |VT- + - -Va--1)xpl)
Ew || VI- Exo-~q (1var- 1)Xool
(i)
I (1 - ajdd + (Vai - 1) M2d
(18)
< (1 (1-ax (z)
1)d
where (i) follows from independence, (ii) follows from Assumption I and (ii) follows be- cause (v2- - 1)² < 1 2 for all E 10. The proof is complete since W2(Qo. Q1)² S
Ex--Q1xoo-Q | Xoll by the definition of Wasserstein-2 distance.
G PROOF OF THEOREMS 2 TO 4 AND 5
In this section, we instantiate Theorem (along with Corollary to provide upper bounds that have explicit parameter dependency for number of interesting distribution classes. In order obtain an upper bound that explicitly depends on system parameters, we need only to provide an explicit bound on the reverse-step error, which is the main topic that address in the following subsections.
G.1 PROOF OF THEOREM 2
We first introduce some relevant notations. Given that Qo is Gaussian mixture, the p.d.f. of qr at each time 2 can be calculated as
/
qc(x))
zv)
T qo. (xo)dxo
ZdE
==1
N
4e (2o(2/2u))00) (20))) =: Σ It. (x)) ==1
ZnERd
n=1
Since the convolution of two Gaussian density is still Gaussian, have that qt is the p.d.f. of N N( Ex,n), where Pt,n := VasHon and Σn, = ā. En,n + (1 a, I Note that Σ,,, has full rank.
43

---

Published as a conference paper at ICLR 2025
G.1.1 CHECKING ASSUMPTION
We first verify Assumption 4 for Gaussian mixture Qo for any a, that satisfies Definition | The intuition is that its Gaussian-like tail (for all 2 0) is sufficient to control all higher-order derivatives of log go-
In the following, Lemma 13 provides an upper bound on any order of partial derivative of a Gaussian mixture density for any fixed Tt, as long as each mixture component is well controlled. This directly implies that the partial derivatives are also well controlled in expectation, and thus we verify Assumption for Gaussian mixture Lemma [4]
Lemma 13. Let g(x|2) be the conditional Gaussian p.d.f. of (N2,, -e). Define q(z)
[((>>>)dl (z) where 11(z) is a mixing distribution (and denote its support). Suppose b == supzez || < oc, and suppose the following conditions on Σg hold for all E Z:
1. There exist u, U E such that u 1 det(E.)= S U:
2. There exists V such that |>, V:
3. There exists w such that sup:ez.a,eidff |3 bps S w.
Then,
| log [(x)] S min { C* BR dh max {w, 1)* U e (1x1)++))) BB d max {w, 13ah
(x))
k/2
k/2
where Bg is the Bell number, C is some constant, and poly some k-th order polynomial in
Proof. See Appendix H.I
Lemma 14. When Qo Gaussian mixture (see Theorem D. Assumption 4
satisfied.
Proof. See Appendix H.2
G.1.2 EXPRESSING Lij log 9:
Now we continue from Theorem to work for an explicit dependency on d. We first calculate the second partial derivative of its log-p.d.f. as
2 log (x)
(x(x)
E (n)),(()) (Eigha pe,n)( Me,) Σn.1)
o (x)
Σ (x) mem) (I Tnnenn in 2 mr,
(40)
x
Now write 2z, (x) 2x Men)) Note that Ozzt,n. (x,(2)( & (z)). We can rewrite (40) as
Dig and that (x)
2) log (o)))(()== (f()) (()
Tnlh (x) (2) - (ET,N)
Ni
Σ (x)
Σ
To calculate the third partial derivative of its log-p.d.f., we need first to calculate the partial derivative of NI and N2. The derivative for N1 is given by
N
35
Tn (2)
(x) - ETT
44

---

Published as a conference paper at ICLR 2025
N
Σ
Tn It (n) (,,( (x) (x) - [
n=l
Ta Tn p =i (2) + Talen (1) =0, (x),
and the derivative for term N2 is given by
N
N Σ
Σ
Tn).n(z) (x)
T qu.n (2) (z)
12
In (x)
(1- (3)) (x) + (
Σ
Anlt. ( (x)
n=1
n=1
(n (x) Σ (1)) (==tt)()))) (2r) + (Σ
Combining these, the derivative for the numerator is
(x(a(())NI - N2) = Oe (x) + (NI) - (N2)
N
N
Σ
(T) (x)
Σ
(n)) (x) - (لري
n=1
+ (x()))
Σ
Tn (x) (x)) (2), (z) (x) (Σ
+ Ut.n (2 ik =i.m (x) + n ut (z) 12 1 i
(i,((r)
(x) (1-2 (x)) (z)) (x) + 1 Σ Un (x) (f)
Σ
Tn In (z) 2 (x) Σ
Enlt.n (z)
(1-2) (x)) (x)) (x) + (ΣTd)
N
N (x)
= (x)
Σ
an
(x)
Tn (x) (x) Σ 1n (x) (1)
n=1
N
N
Ta Ht (I) o/ (x)
Un 2z) (z) (z)
+
Tn Fn (x)
T (t) (x)
nml
+ qe (x)
Tn n (x) E
2n (x)
An (x)) 1
(
In (x)
+ qe (x)
untt, (x: [
22.0 (x)
F Ft (
tn (x) (x))),n(z))
N
N
+ qe (x)
Ty Ta (x)
1,m 22,00 (x) (x)
Tn n = (x)
Tu St, n ( (
Since
(2(()NN N2
83 Uk
log (x)) 0x
(x(x)
N - (2)) 2(x 2((()))) - N2) Σ
Tnde (2) (z)
(x)
n=1
45

---

Published as a conference paper at ICLR 2025
get fx) log
N
NV.
= (x)
Tn (n) (T) (1)= (1) (x) + (c())) Σ
Tnlten (2) (t)) (x)
Σ
Tn (x) (x)
m=
N
+ qr (x)
Tattnn (2) (x)
Tn Un (z)
n=l
+ (x)
Σ
Tn (z)) (x)
n (x) (x)
Taltt (1) (1)
Σ n ( (1)
Σ Tn In (2)=ff((z))
N
N
N
+ of (x)
Tn qnnn (x) (x) | =(,(()) (x) - 2ee
Σ
Tnli
(2)
[
11
Enlt (
aml
n
N
N
N
+ qe (z)
2
An. (z) ( 27,n (x) 2 (x)
Σ
Tn Fn (z) [2 ik
Tn (z))
n=l
n=l
qe (x)
Σ
An ( 2n, (x)) gc(ar) Σ
Ty
(a)) of (x)
Tn n (x:) [5
Below, write (z(2, i) max, c (x) and Σ to be matrix such that Σn max, | Also write (x)) Tndt. (z))/r(()). Note that for any x, >n (x,) = 1. Therefore, we take max, within each summation above and get
L log de (z) < (2, (Z, k) + E k) + (x. 25 i).
G.1.3 ASYMPTOTIC EQUIVALENCE OF (Ix:) AND Xe Intuitively, pe (x,) and 2, are asymptotically close when 1 - is small, which will be useful for later analysis. In this subsubsection, we will show that (,-1(p),)) (,(,,, = Ö(1 as).
Note that for each n and fixed 2a (writing (z(z)) pc).
21-1n - (x,e
=E (14 - (1-1,n) - ET - M1,x)
=(E-11,n E p4-1,n) - -E m4,n)) (M4- p4-1,n))
(41)
Here, since Σn-1, is real symmetrie, we can write the eigen-decompossitonn as Σ,-1, D where U is orthonormal matrix (having unit 2-norm) and D is a diagonal matrix (with all diagonal elements positive). In the same notation, Σ,-1, = UD- and Σ (a:: + (1
Tx) U(a D + (1 Ta) Since
1
|| - (1 a.)
Di a, Di (1 o4.)
(1- (1-a))( D +1)
$ (Di)) + Di
Ö(1 or))
the following holds:
| Enall 0(1 -a)-
Denote [A] as the i-th row of matrix A. Thus, following from 41 for any E [d].
||ا 1d
| Ezall Ö(1 at);
(42)
46

---

Published as a conference paper at ICLR 2025
1
Var
1 at
1
Or log qr (x()
= =01 at);
Vat
12-1,nl
(1
vos) 0(1 ot);
04s
where (i) follows from the definition of matrix 2-norm and from the fact that [_v E 1, (1; the unit vector where the i-th element is I, and recall that 27,1 symmetric). This implies that 22-1, (He)
2f (2x) = Õ(1 ai)). Vi. Thus.
& ( - (x2,, i) = max | I, (m+)) max (zxe
max b 1, (1z) mx)n( = Ô(1 ((1-ch) -ar);
(43)
where the last incquality follows because max, |a, + maxa l6ml 2 (aa (6ml)) 2 max, lan
Following from Theorem
| we have
Ex,=Qi
Sgg log qt 11)1((((()))))) log
log (Xa)
(JAK=1
Ex
22E" (E -2m
+ 12255/E(EE (())( (0E( 2E5 25 EXx,,( 255
(ECX,.0((XX))EEXXX,.) + E' ) 2
ExinQ.
Σ
iriik=l
S 2
Σ
6.1.==
(44)
where (ii) follows from
43
G.1.4 EXPLICIT PARAMETER DEPENDENCY
We are now ready for the explicit parameter dependency for Gaussian mixture Qo- the following, we provide two different ways to upper-hound the terms in 444 depending on how N is compared to The first approach can be applied when N < d. For the {(x, -) (Vz E IRd) terms,
Σ i(
max (M (x (f
2)
( Mt,n))
1=1 n=1
|| | (x (, ml, < N max
| max || Me, l|
N max || 11,
where (i) follows because the following. Since Me,, is a (full-rank) covariance matrix, all its eigenvalues are positive. Let An, > 0 be the smallest eigenvalue of Σp,e, and thus
1
max |
< 30.
(45)
ā, min, An,min + (1-ax) ax) min (1, min, dn,min)
In particular, this bound does not depend on d or T. Also, for the Σ terms,
Σ 1002 Σ
max((2n)))} <
Σ Σ
(122))) = Σ | S Nd,
47

---

Published as a conference paper at ICLR 2025
where the last inequality follows from (45) and the fact that for any matrix full-rank A, ||A|| I vd |l The second approach can be applied when N 2 where we can bound the {(x,-) (Vx Idd terms instead
d Σ 5(2, 1)2
Σ max [_n
(x 11,,,))
max (112)11)) 1|:0 Me,nl 12)
max ||
max ||a: me
[=1
1=1
(His)
(te)
max
max 1 Me,
11
d dmax || Pe.n 112
Here (it) follows from Schwartz inequality, (ii) follows from definition matrix 2-norm and the fact that [Σ E,, (1, is the unit vector where the i-th element 1), and (iv) follows from (45). Also, for the second term, we can obtain an alternative upper bound as follows. Write the dige-ddecomposition as Lo.n Q,,diag(An, (.., An, where Qn. here an orthonormal matrix (that does not depend on T). Then.
tn (2(ārdiia(AAm..... .nd) +11 T.) Q1
Q,ddia(((addn, az))= ..... (ārdn, d +11 5z))
and thus
(ārAn,k + (1 at)) Q -
max ME[M]
max WE[N]
< (min 1, min Ava.min })-1
(Q
max
nE(N),
< (min(1, (1, min An, })
max ne(N).EE
= (min (1, min mn.min))
where the last line follows because Qn is orthonormal for all E [N]. Note that this is uniform bound that does not depend on N, T or d, which further implies that
2 < Ed. d.
V-=1
Combining the two cases, get
i(,,1)² S minnd, N) max ||x Me,1
(46)
Σ (2 S m
(47)
J==1
Therefore, using 44 and 47
continue from
44 and get
Exi~Qu
Σ
bi log at (x)))) log (X,)
WJ.=1
S min NJ 3
||x. max || 11] (d (d, NJ.
Now, note that
max |, S max || < d
48

---

Published as a conference paper at ICLR 2025
since Mo,. 00 is fixed vector. Also, the expected sixth power of the norm be bounded
|| (IIvaro++ -I- xllll + B x x + d
and, when Qo is a Gaussian mixture.
/ |1ool| 20 (o(o))da
Σ Tn / ||oo||
N
(o.((r)d ds.
Therefore, we finally obtain a bound on the reverse-step error with explicit system parameters:
T
log (x
d min (d, .N Sdd log T
Σ E Ex--nN
P (X
T
G.2 PROOF OF THEOREM
3
Throughout the proof of Theorem we adopt the noise schedule oz defined in (1p. We first investigate some nice properties of the noise schedule in (TOp. Since c x log( (1/5), we have
1 04 2 (1/8) log T/T. Using a similar argument from (Li 2024c. Equation (39)),
0₁ a₁
1 at
(o/(1 [og))logT
<
ST
(48)
āt
- ō.
1 1- 0:--
T
ū at)
1 1-ar at
(
log V2
I
d+11
dz-1
1- 81-1
T
We note that al. (2024c) does not highlight 8 dependency in their results. Also, note that T large,
( [ clog T
lox
x de 2 1.
T
Thus, with any fixed r E (0, 1) such that t 2 rT (2
T
we have
lox T
clog? T
{ {8 (1+
clog T
1 clog T
at T
min
.1
T
As result,
clog T) ((-r)T7) 1
(- (_elog T' T
) (((-)))-)))
X exp ((1-r)i]
áT S [=[rT]
(49)
Given any > can always find some r such that (1 -)r 2. For example, this is satisfied when r = (c 2)/4 if c (2,4) 4) and 1/4 otherwise. This shows that the in (10) satisfies äT = o if 2. Therefore, the a, in (0)) satisfies Definition
Since the parameter dependency clear in the bound for the initialization and estimation errors (Lemmas and it remains to provide a bound on the reverse-step error that depends explicitly on the system parameters, which is the main topic below.
G.2.1 CHECKING ASSUMPTION 5
Instead of Assumption 4 we check the more general Assumption below. In particular, we verify Assumption 5 with the aa in (TO). In the following. Lemma 13 is used to establish the first half of Assumption Next, the following Lemma i6 used to establish the behavior of the expected moments under the perturbed posterior Qoje-1 1 (-Ix((X,)) when X, ~ Qt. Both Lemmas 15 and 17
will be useful for establishing the second half of Assumption 5 with the or in TT).
Lemma 15. For all > l and a E [d] such that aal p21
dot/2
Ex,aQ, 10 (X.)) S
(1 -1-68 a. p2/2"
49

---

Published as a conference paper at ICLR 2025
Proof. See Appendix
H.3
Lemma 16. For all t 2 2 and p with the at in (T)).
J 10
(1x(x))) Vou
& d 1221)
Proof. See Appendix H.4
Finally, the following Lemma 17 verifies the second half of Assumption 5 with the or defined in 10)
Lemma 17. For all 2 and a E [d] such that [a] = p 1, with the at (10).
dol/2
Ex,-Q 10g log 9: (1 2 (1 -1-1) pe12
Combining this with Lemma
15
Assumption 5 holds.
Proof. See Appendix H.5
Now, Assumption 5 is satisfied since T-6, S T-a: 5- for all t 2 if 8 is constant. Thus, 5 is a constant, Assumption 4 is already satisfied (as is Assumption 5) This is not necessary, however, when 5 (/poly(T) vanishing with T. Fortunately, in this case, from (48) we still get Ó(1 at). Thus, Assumption
5 is still satisfied.
I-a--1
G.2.2 EXPRESSING L log q: We begin by investigating v log 2 2), for which we can derive the Hessian of log (x(x) as 20 20 2 lo (x) = Ür (ToeEee ( (z
(JanER
(x(x) SaBERS (= - (JroeRe V4.0(zl22)dQ0((s))) (JrDeRs (=)o(t)an)dQ6((z))) (x(x)
(x(x)) /
AEERR (10(0100) ((x vārzo) vonzo) (1 - aa)) dQQ(20)
aq 32 (z)
( VODER (0o(</20) - (aroo) (1
1 ōi Ja+
Exo~Rom((aa) [[x Var va.Xo)
(Exo~Qostk)) [r - -oxoool (Exo-Qoe((a)) Jr varoo)
(50)
For the third-order partial derivatives, we employ the notation
T Vazz
1 Ce
Note that (x (00() Then, can write (50) as
1
83, log (z) =
(x)) (0(x))
N1
(np(((/m)=/dQo((m)) / (noo(((ro)=<dQ((mm))
la-
1 az
N2
50

---

Published as a conference paper at ICLR 2025
Note that the last term is constant. The derivative for term N1 is given by
Oje / a o0
= f ( + 1(k
-a)
+ 1(k - () (z) -1))
and the derivative for term N2 is given by
ahe ( (ono(t(aa)))(a((((( /
-f at [ ((=2))² + 1(k = ()(1- - a.) dQo / (210(1)20)/dQQ0(z))
f (molokoo)=/Q00zo)) / (10())200))) ((-=*)=² 1(k = j)(1 -;)))=aa)))de(ee
(ʃ ("of + 1(k i)(1 - ā.) a,)-' (x)
+ f (1o==lz))=/d000(z))) (f ==
1(k j)(1 a.) a
Combining these, the derivative for the numerator given by
@x(c(<)NN - N2) (x((()))N + (())
-x (N2)
- f (nooltlzo)=="22==000000
+ ( (
Thus.
03 (zg = 0₂ Qr( (x)NNI N2
(F(x))
(x) (Oll:(())NI - N2)q((z) + -N()at)) 2(1 - N2) (no(=l)o))+dQ0((0)))
(-di(0) / a1
(xx)
/ ( dQu / (M
+ (x)
Σ
02 02.03
/ (nolst2o))=d00(z)) / (000))))) / (nol=)zo)==dQQ00
/ 1 =dQu))
/ (00 / d00
Σ
a1=bijk a2<as, 02.
/
2'QQo((zolx)) (201))
/ / (2 (2QQ0)(Zz0))))
(51)
51

---

Published as a conference paper at ICLR 2025
G.2.3 EXPLICIT PARAMETER DEPENDENCY
By Schwartz inequality, we have
Ex
Giju
log (0 log qe (Xp)
S Rx,
Σ
0 15k
log (0g
Ex
Σ (.1k=1
0 log (xg
2
biik=1
(52)
We now analyze the two terms in (52 separately.
We begin with the second term in 52 Recall that Z = Xe-vaixo is standard Gaussian under Qo.- I-a,
Also note that for a standard Gaussian random variable Z, E 2 d(d + 2) + 4) S d= Now.
substituting (5T) into the second term of (52). we get
E Ex (J
2
d
Xi
vanXo)
x x VanXi
X v 2
< (1 04)3
Ex Xi
at
vI 1t
vI at
X, (
X Xx Qo.
(1 āz)²
VI- ai
E 1
(1 ,1)3 )
d
(1 (x)) 13
and
Σ Ex (ʃ
( /
2 2000
kr.k=1
||| x11000)(((0))))
2
( (d
= =Ex-~Qi
J,k=1
2) 3/2 2/3
< Exi-q. // /=d(o)((ooo))
16) 1/3
d Σ
( (2'sAdoo
Exmai
Ju==1
Xt VarXu
< Ex..XerQu.
(1 )3)3 1116
<
0r.) 33
and
Σ ExiaQ (ʃ =dQoo(((ooxx.) / 2dQo X.) / =d (200 x.)
1,1k==1
d
X - Vara 1 1-a
2)
=Ex,Oq
Σ
doo)
52

---

Published as a conference paper at ICLR 2025
Xt vāruo
R x ~x
dQ (20
(1 o1)3
v1 dt
(1 ā.)3 E3 |1
āz)3"
Thus, the second term of (52) satisfies that
d Σ 6.
d3 (1 āz)3
Ponlog lo
Ex
2
Now we turn to the first term in [2)_ Note that Z M4 (x While Z is longer standard
1-ax-1
Gaussian under Qu.t. can still achieve moment bounds using Lemma T6 Now, substituting (5T) into the first term of (2), we apply Lemma I6 and get
Ex (f
(0 (100((())))) ?
Σ AAA==1
Me(x,) /aa
d3
Ex Pop (1-aa-1)
S
v1 ā6-1
(1 ā 31
XemRe
and similarly,
d
Expei (f ((0000n-1oolll(x /
k.jk==1
d3
S (1 ar-1)3²
d
(fttR00 / (tt (((l0x))) / (aQ0ox-
ExieQ
kjik=1
d
(1 -1-a-- 3,133
Thus, the first term of 52 satisfies that
Ex
Σ
(oen log a0 (m(())))))
<
d
2._1
P.j.km
Finally, since
1-a, I-a,"
1-a,
logd 11)) 18) Tog
we arrive at
I- ---.11
d3
loog" (1/8) log T
(1 (1-
0 log 10 log (X,)
S
T3
k.j.k=1
Summation over 2 gives us the desirable result.
G.3 THEOREM AND ITS PROOF
Before enter the proof of Theorem independent interest. Previously, for regular samplers, linear dimensional dependency can be shown
introduce intermediate result which might have
when all Q''s 's (vt 0) have Lipschitz score (Chen et al. 2023a d) The following Theorem provides an accelerated convergence guarantee when all Q (Vi 2 0) have Lipschitz Hessians.
Theorem 5 (Accelerated Sampler for All-Path Lipschitz Hessians), Suppose that 4 log (x)), VI 0 is 2-norm M -ipischhitz i.e.. 3M > 0 such that
2 log (x()) 2 log qe (v)ll & M || yl
(53)
53

---

Published as a conference paper at ICLR 2025
for all 2, y E Rd and t 2 0. Then, under Assumptions aaddd 5 if the ar satisfies Definition 1 the distribution Po from the accelerated sampler satisfies
KL(Qo|IP)) - d log T (log T) log T E
G.3.1 PROOF OF THEOREM 5
In order to continue from Theorem (in particular, the reverse-step enror in (26)). need to introduce
some useful notations for the distribution class in (53). For a matrix A, define its vectorization as vec(.A) == [A ..... Ald A ..... , AddjT E IR".. Define Kr E Idd'dd to be the matrix that reorganizes the third-order partial derivative tensor, i.c..
[K(()) Lig log (2)),, s.t. (i 1)d j, Vi,j, k E [d].
With these notations, consider = x + Eu where u E Rd satisfies ||ul|² = and & E R is some small constant. Then,
vec 2 log (v)) - veel 22 (r (x)) Ki (x x) EKi(x") yu.
Here x² = 7/2 (1 ?) for some 7 E (0, 1). Also, have V (v)) vee 2 ax))))
V2 log ( V2 (t) 2 log q (1)
V (x))(())] ddM lly - x1
where the last inequality comes from 53 Thus, noting that = I Eu and that ||u]]2 1, we take the limit of & to 0 and get
[x(x)] s VdM,
Vx e Rd W 120 0.
(54)
We now derive an explicit upper bound on the reverse-step error. Using Cauchy- Schwartz inequality, for any / and xa Rdd, we have
Σ w1.==1
ijk log 9t 1 log 9: (z,)
(0 k log (0-1(m))2
(0 log q (xx)))
kiikkll
k.
|| (14)l x ([Ki())))l
(Vd (2))) x (V:)),(())II))
2
(55)
Therefore, following from Theorem we obtain
T
Ex, x.x in log -e- (0-1)e(X-1111 (x,)
da 12 log
S
(x-
T2
G.4 PROOF OF THROREM
Throughout the proof of Theorem we adopt the noise schedule a₂ defined (10) with = 1/(M$7)) and e > log(At T Note that such satisfies Definition for all f 2 1, and thus
the bound on the estimation error still applies. Also, Assumption 5 satisfied for > 2, shown
in Appendix G.2.I Thus, Theorem can be applied and the reverse-step error at > 2 satisfies,
Vt
(1 a EXxno.
Σ 1.1
Lz log q (1- log ge (Xe)
54

---

Published as a conference paper at ICLR 2025
(log" M + logg" T) log"
(56)
T
In order to determine the dimensional dependency of the reverse-step emor, the key is thus to establish a similar upper bound
Now, we provide modified version of Theorem | which does not require go to be analytic (as in
Assumption 2 or to have regular partial derivatives (as in Assumption 5). We recall from (21) that the reverse-step error at time & 1 can be upper-bounded as
Quja (X)) Poj1 [2a)
Qu11
log
S IR Xo1 [Si
Xx [Si,o]-
Instead of the Taylor expansion in (20). we employ the following different expansion from Taylor's theorem. The only difference is that the expansion stops the third-order term.
$i (V log (0()))))))))))))))))))) v V logg (x) M1)
1
(Io - p1)T =M1)
22 log (o(()) - - 1- a0
on B1 (xo -H1)
+
2
d
+
Σ
Bi log go (a( - (1) 14) - -ma).
(57)
3!
1.1,==1
Here pi (x11 (21)
s)z0 for some ş [0, 1]. Note that pi is function of both æ1
and øo.
remarkable difference from the proof of Theorem iis that do not require qo be analytic for
this expansion. Indeed, it only requires that the third-order partial derivative exists. With this new
expansion, we have the following lemma, which serves counterpart of Lemma Lemma 18. Suppose that qo exists and 2 log 90 is 2-norm M --Lischhitz. Then, with the at in (TO).
we have
(1
3/2
Exp~Qo [Exo-Qo1 Exo~r% [5, S
d M.
3la
3/2
Proof. See Appendix H.6
Finally, with the chosen 8 = 01 1/M3313
the rate at the first step satisfies
(1-a1) 33/2
dt
M S T9/1 o(T
3l0
3/2
As T becomes large, the rate of the total reverse-step error, which decays Ö(T-2), is not affected. The proof is now complete.
H AUXILIARY PROOFS OF THEOREMS 2 TO
In this section, we provide the proofs for the lemmas in the proofs for Theorems to
H.1 PROOF OF LEMMA
13
Fix k 2 1 and a E [d] Recall that u < det(E2s) - U. ||
< V, and
< w for all E Z. Also write dly) as the p.d.f. of the unit Gaus- sian. We are interested in upper- bounding the absolute partial derivatives of log q(z) with function of x where
g(x) / 0(=12)d(T(=),
where, using the change-of-variable formula,
1
(I.²(1 -Ha))
g(x|2)=
(58)
det
55

---

Published as a conference paper at ICLR 2025
We first identify upper bound the absolute partial derivatives of q(x)). Now,
(1) @ / 01g(x12)d11(2)
IAB
/ 00o (272(0
(x (p=)))) cll(z))
in (E,))
where (i) follows from the dominated convergence theorem (see (31) ). and (ii) follows from (58). To
obtain an upper bound on the k-th derivative of Gaussian density, we invoke the multivariate version
of the Faá di Bruno's ' formula (Constantine & Savits 1996. Theorem 2.1). Since Σg à (x M=)
linear in 2, only the first-order partial derivative is non-zero and is equal to an entry in Σ; à Thus, we have
0 22
5 2xx p2)) =
Σ
D (x 1==))
Daa
d'E
(k)
E (I - -m+)) max {w, 13"h Va: |a| = k.
a'Eldj
Here we define da ( = oly). Since (by) is Gaussian density which is infinitely differentiable and decays exponentially at the tail, its k-th order derivative satisfies oi (v) = poly, (y)o(y) where & (3) is k-th order polynomial function in y1..... Vd (and thus in 21...... za by linearity). Also note that, for any a E [d]
lim
8a
(1)
lim & (v)
vll +
(Ta) S (olly((a) for all By the continuity of da (v), there exists De such that (ol (v) S (
y E Rd. Now, for all Rd.
[0%g(t0) s f del( 1oto EE (3 - (s--)=)) all(2)
< max
max fw, 11th / det(22))
Σ
p ( -a)))))]
( u=)) dll(2)
aEidk
(59)
d max (w, 1) Vu
|poly, (ya)l (Ja).
(60)
We have thus obtained a constant upper bound on all partial derivatives of ((z) of order k.
Next, we convert the partial derivative bound into that for log q(x).. We again invoke Faá di Bruno's formula Constantine & Savits (1996). Note that
8 qxx) = q(x)) -k Σ
by II D J=1
(()) by
Σ bi....bb
Tb Tbi....bb (x)
(61)
which we define each summation term as r. Here (bI,.... by) is some (possibly empty) partition of i.e., Σ, by- = and E, |byl = k (thus, at most k partitions). We order this partition such
that k b ... bk 2 0. Note that the total number of partition can be upper-bounded by d E (I. 1) d Bg, where (-) and Bg are the Bell polynomials and the Bell number, respectively.
We first showcase a simple yet useful upper bound. From 60 we get,
k
bby 0z
((x)
S
a
((x)
1=1
56

---

Published as a conference paper at ICLR 2025
(d ww, 17)2,161
max/max (v),, 11
poly (00,))
min(u, (u, 13k/2
(d max w. 11)2 min uu 1) 1)k/2 maxfmax (1)), 13th max poly (36,) )
8
dh max {w, 13
Ch Cb.....yy by min 134/2
b, is some constant which depends z. On the other hand, we can also obtain a simple lower bound on ((r). Observe that g(x)) is continuous and always positive. Recall that b = supzez || Thus,
where, as noted above, Ub, does not depend on x. Here by only on the partition (b1.....by bj} and is independent of
g(x)= | g(xl=)dIT(=)
exp
sup(x p2)) 1= (x ms)) dll(z) xE2
(2
2/2 d/2
2E2 (E. 22
|
(||=|| + |||=113) alT(z)
exp
sup xe2
(2x) 2/2 sup det(Eg)²
2
| || [|æ|| b2) alT(2)
exp
sup =EZ
(2 1/2 sup SEZ det(E.)²
2
V (2 d exp (-2 (1|=0]
2 + b²)
Therefore, if we set C == ma......... Coi...by. we obtain
da max {w, 11th 1o log a(x) S Bx
minfu, 1/ (001119))
B&
(62)
The upper bound above, though it depends only on parameters u, U, V, w, has an exponential depen- dency æ, which is not desirable. We next derive more refined bound in æ. For brevity of analysis, we re-express r (defined in (61) to avoid empty partitions:
Tb by (x) ((x)))))))))
II
a |by g(x), s.t. |bp+1| =...
[b 0.
1=1
Now, by the boundedness of ||u=|| and such that, Vz E 2,
| 1/2
on Z, for each æ, there exist (bounded) Do, and jib 1/1
Σ
poly [by]
[._ (x (z)
x
Σ
poly [6y1 (5 fx ((o-A1s))) ner,)) co.
BEld |
Beldl |05
Then, following from (5). we obtain
I On (I) g(x) P
Dss
bbyl
q(x)
S (())
II
0 by g(z)
1=1
(dmaxfw, 13) 1310
un/2
p [det(E:) Σ
eg |sg |pllyjea1
(I (z- p=)) & (Ix fr - n=)) all(=)
I (o.) - 2ob
Σソ (rr - pz)) dll(2)
J=1
(dmax{w, (w. 1 m 2//22 x
57

---

Published as a conference paper at ICLR 2025
Σ
poly [byl
(2))) (x (bb)))
(S det(<z)) t - $ (o -+)) dll(z))
II
S dc) a Σx (xr (+=) dII())
max, 13) mi u///2 6/2
Σ
poly|bs
(5)) (xr (
Note that for each j. the number of terms in the summation above upper-bounded by d'es), Thus, expanding the product of summations would result in no more than I d d terms. Also, since poly,, (v) poly &. (t) poly + (v),, and since any bb (xr Pby) is linear in and independent in each product term is k-th order polynomial in Therefore, we obtain
2 max w. 1)th
bb bu (x)1 S min (1, u///2
max
pplly (x)]
cy 22 ky=1....
and thus
10th log a(x)) < Bb dk max { ww 11ah
min u k/22 bi.....bu bu
max
max -y-1.....
Ipoly (2)l-
(63)
We have thus identified upper bound on 1 log ((x)] complete by combining (62 and (63)
which is polynomial in The proof is now
H.2 PROOF OF LEMMA 14
We first identify u, U, V, w for Σe,, such that they are independent of T and for all f 2 1. Fix 1. We the fact that Σt,m ag Co, + (1 - Ta If we let An, 2 2 An, > 0 as the eigenvalues of Eg,n (which do not depend T), the eigenvalues of Ei,a are (āzAn, (1 ā.) ) Therefore, for any n I,...,... N and 1,
min ( min Anai, 1) S (t, I II max (max Xm.i 1}(=U))
Also, following from (45). we have == mine 1,ming An Next, write the cigen-decomposition as
Do,n Qn diag(An, 1 ....... an,a) QT, where Qn here is orthonormal matrix (that does not depend on T). Then, for any 1 1,
Σ = Qn (andiagg)Ann) An,d) + +1 aa) -T Qudiag(((nnnn) + (1 az))= 2,.... (ardn, (1 - -
and thus, for all 2 1.
E b Σ (āydnik (1 ax)) - k=1
(min(1, (1, min An,
max nE(NN],
Q Qui
= w.
Since the identified u, U, V. are all independent of T and k by Lemma 13 we have obtained an upper bound on a log {(x) for any fixed x which independent of T. Thus,
(1 ot)) 1o log (x))) (1 )t,)*/22 |ot log ge- (1-(
=ō =0((1- -0(11-t))57
Tk/2
Hence, have shown Assumption
58

---

Published as a conference paper at ICLR 2025
H.3 PROOF OF LEMMA [5
Fix 2 1. We will draw some notations introduced in Lemma 13 that
Specifically, recall from 61
0g log ((()) (0))))
Σ
II
0 q:
(21)
b
= qe(x))
Σ
II
gejo (=10(z/(20)pol)
Ft -ā,00
dQu(zz)
1 - āt
b1 by J
P
Va /I āi
poly
(dQoje(2o(zre)
(64)
x0
which we have defined poly,(v) as a k-th order polynomial function in y1. ...... ... Dd. Recall that here (b1..... bp) is some (possibly empty) partition of a, i.e., E3 bj a and Σ; bby p.
Thus.
Ex Ex,-Q, 10 log yr (X+)
Xx - Var,0
Bx
poly bsl
(
(1 σ4
4
bI....bp
v1 αr
Σ
II
9
Bxi / poly
X, vār20
(oo
|oy
(1 σt)
v1 αe
bz....bpJJ j=1
1og
X, v ax
ExexXi-Qoi
poly
(1 āt)
v1 C2
by bp j=l j=l
pt (2)
Σ
E poly 1by1
[3g
(1
04
uc
bi..... bp j=l
d
where (0, Ta) a standard Gaussian random variable (that does not depend on T here) and any r-th order of polynomial of Zı,.... ... Za has finite expectation (that does not depend on T and with at most d2/2 dimensional dependency). Here (i) holds by Hölder's inequality, and (ii) holds by Jensen's inequality since pl/ |byl 2 for all by and 2 The proof now complete.
H.4 PROOF OF LEMMA 16
Fix t > 2. We first introduce the following notations. Write pe = (xx)). Let Qu, be the distribution of (X,)) where X, Qt. and let qp, be the corresponding p.d.f. (w.rt. the Lebesgue measure). Let Qui.an be the joint distribution of μl and Zo.
Now, we can re- write the integral
/ J (1x(()))) voo- ((0
-fa I1me Vāu-1zo11" (2ol-
gu. (pt) d (0000
I1 Vor-1
Jo.
q-- - (
59

---

Published as a conference paper at ICLR 2025
100 l1+e - - (
(u,(He) (-1(
(65)
where the last line follows from
inequality.
Now, for the first term of 665 we recovered the matched moment, and have
S Jeom ||
vāc-1u00 22 (000)-1(t0/44))0000-
| - v00-1 20 "Q0, x1-1)
10.00-1
28
(1 ā
T4-1 V0 150
(Q0,--1(00
v1 - δx-1
(1 x
E
1 Sd -x-1)²
where Z ~ N(0, Ia) is Gaussian random variable.
Now we upper bound the second term in
65 whose square is equal to
J.
gun(He)
((-
qur (IC-1)
qr- (
9t (w+-1)
1 X 2 (c-1)
(1)
$ 1 + x2(Q ue 1Qt-1,0)
Oer 20 (Mte (2o)
ac- (1-1)0(441000dm aQo(1a)
-0 (1t (20)
(2)00 4:- (1=))
det ddelzze) dxe/ dQu(zv))
dx
2 (1-1)0((4(22)) (m))
dQr,0(z,
(du((z)) dr:
22
det
20)
where (P(II)Q) is the chi-squared divergence between P and Q. Here (i) follows from the data processing inequality for f-divergence, and (fi) again follows from Cauchy-Schwartz inequality. We can calculate the determinant term above
d44 dx.
1 la V
1- a
v2 log (
det
= det
Var
-2
(1 [1+ (1- - 0x Tr V log (V + ter cx
af
< a
(1- 2(1 a.) (V (
60

---

Published as a conference paper at ICLR 2025
where denote the residual terms (x)) Ep=2(1 aa))" E - cI II (i)er 0g log (xs).
where Cy is some coefficient that does not depend on T. Since from Lemmal 15
Ex.-Q. Jogy log qe (x.)) = (0(-aa)))
1
).)
Vi,j E [4], v v221,
and note that 1-0, = l-
0 log
with the a2 in (10), we have that
Ex,~Q [x,( -
20 (1 a
)
Σ
ofE
II (K))ET
0 log gr (X,)l
p=2
T:|T|
Σ (1 at) )
Σ
C1 II (Ex,qq ( log (x)))))))
p=2
T:|T_pp
(7.))
(1 - 0z)
0
(1-āg)
p=2
Ô ( (log T) (10
T2
and thus
dlie dx,,
log T T
log
Ex del
= oi +
S 1 + Ô
T
Also, since
| [1.
) 90-110(111
(1-0,jd exp
[1=+( loR (e 20
(1- exp
as 1a--at
a--1
d
1102 - vanuol |
1
1 1mm)m)
0rt ))
exp
0t
04 14-04 0t
2(1 az)
V Vlog do (Ix)) T
vanto) + (1 a,)² (x)))
exp
at Ctt
(11)
Varz0
-
cxp
Ctt
a2 α
2(1 a,) V log qo (Ix)) (x, vā,zo) + +1 (1
Vog ge (z, 1l
exp
a1 āt
Fiz (1* | a₁
v T0
1 -
exp
Or 04
(1 - ar) V log qi (z1) (T ((x Vorao) + (1 (1-a))² log 2 (x:)]l [
1 1
02 Gt
where (Mii follows because
1-ār-1 I I-a;
< 1. and (iv) follows because e² = 1 + Ō(z) when -+ 0 and
because
1-ar 1-at a.-āi 1-āe
δ
log T
with the or in 10 Thus,
200 (Xelo))
2
E Exx
(x-1)0((((X))(XX
X,
v V0
1 Ct
2 BxixNon exp 2
VI 0x
a₁ αi
61

---

Published as a conference paper at ICLR 2025
1 1+1 δ Ex..Xor@e.
(1 - ar))
V log Qr (xx)
v Varvol
+ (1 ox)
V log (Iz))l²
az X, Xo
x (1+0
log T
Ex Ro exp 2
vT
T
where (v) follows from Lemma 15 and Cauchy-Schwarr inequality, and
Xt
va:Xo
2
ax
Ex,xXo exp
2
v1 at
@ ||=11 111=11 dz
(2m)
e (=b1lel((4+00000777)
=
(2
log 7
1 =1+0
T
Therefore, arrive bound for the second term in 665
Vin qur (He))
log T T
(Q0n=- 11+0
(
and the lemma follows immediately.
H.5 PROOF OF LEMMA 17
Fix t 2 2. From 64
we also have
E Ex,qq 18% log 41-1 (Hc(()))))
1
p
Σ
Ex
πI poly
(He(X)) - vāg-120
(Q0l-
(1 - 1)
v1 ax-1
bi....bp
[og|
p Σ
II
Ex // poly
[x(x)) 100-1100
d
(1 (1- à1-1
VI - 8;-1
b
byy
Exime / poly|osl
Mr(X,)
va1-120)
Σ by....bp:""
II
(x00
(1 - k(-1)
v1 04-1
1
/
v0--100 [e(e))
max E Exine jEln)
poly
v1 δ.11
Ō(-1)
br.....bp
10
1
(e()))
Va0-120 VI
pe
ExieQ
d20 pi (X.))
11-1)
ar-1
a1-)
where the last line follows from Lemma
16
Now, together with Lemma 15 Assumption 5 is
established noting that 1-81 = log T
Ō(1 - a.) for all t 2 2.
T-a;-1
H.6 PROOF OF LEMMA 18
Recall the expansion of Lo in 57) still have
As in the proof of Lemma I1 with the choice of μr and Σ,, we
E Ex P [Ti] = Exo-Quu [Ti)
62

---

Published as a conference paper at ICLR 2025
Ex Ex 0,1 [Tg] Qoj [T2]-
Define Ty- : 31 2ij.k=1 of log 2o (2T) - 14) - 1 (2 - n4) Here μr = (1 no) is
function of both 21 and zi. A useful result from Lemma 13 is that, with the a in (T), we have, vi,jk l [d] and l 2 1.
(1 Rd
(1 01) )1)(Exx) "x j0 log q1 (X1)
2
de
(66)
(1 - ā1)²
(1 a1 dd
(1 01 Rx xi Bigh log a1 (x1))²
X
(1 an)s d.
(67)
First, using Lemma 8 have that
Xxo.Xi~Qo. [T']
a1)
Σ
E X, XI.. Lo log Xo)) log ai (X1)l
3la 3/2
kjjk=1
(1-a1) 01)
Exo.XinQo. Σ
(0 log (4
Ex
Σ
(0))
log qı (Xx))
3la
3/2
1,j.k=1
1..k=1
11
01)
dM,
Ex
Σ
(0 11 (X1))2.
3la
3/2
i.A.A
Here in the last line have used a similar technique in (5 which assumes that 2 log qu is 2-norm M-Lipschitz. Now, from (77 we have
(1
a1 33/2
Exo.
[T']
x
dt M.
3la
3/2
Also,
E Exo~Po [T'] X1-Q1
Bi log (01,
II (Xx (x(1))
Xx Xi
(1) 1
dM
E Exp XINQI
[ - -x1())11
3!
<
8 M,
E Exo - (x
3!
i=1
X1-Q1
1-
M,
15
ExinQ: (1+ (1 a1)8ß log 91 (X₂))²
3!
01
i=1
(wx)
01
3/2
d
M
3la
3/2
where (i) holds with a similar technique in (55) assuming V log go is M-Lipschitz, (tt) holds by and (182) holds by (66). The proof is now complete.
Lemma 7
63


Reviews:
[{"review_id": "ZgIuCy9ghb", "reviewer": "Reviewer_gLE4", "summary": "This paper introduces a novel accelerated stochastic DDPM sampler that leverages the tilting factor representation and Tweedie's formula. This approach is designed to accommodate a broader class of target distributions, requiring weaker conditions than previous methods.", "questions": "The proof is quite lengthy, and I did not have the opportunity to examine all the details. It would be beneficial if the author could elaborate on how the accelerated convergence is achieved using the proposed novel proof technique (specifically, in Step 2 regarding the tilting factor). Additionally, restating Tweedie's formula and clarifying its extension in this context would help enhance the clarity of the proof for readers.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces a novel accelerated stochastic DDPM sampler and demonstrates its applicability to various distribution classes while relying on weaker smoothness conditions and the bounded second moment condition. Additionally, it establishes the first acceleration guarantees for Gaussian mixture models.", "weaknesses": "Assumption 4 plays a crucial role in the construction of the tilting factor, requiring that the score function has derivatives of all orders and that the $p$-th moment is bounded $p \\ge 1$. In my view, this condition is not as \"rather soft\" as suggested in the submission. The requirement for all derivatives to exist means that the score function is not merely smooth but infinitely differentiable, a level of regularity that is often absent in practical score functions, particularly for complex or non-smooth distributions.\nFurthermore, the requirement that the $p$-th moment of the derivatives is bounded indicates that the derivatives exist and do not grow excessively. This can be quite a restrictive requirement, especially for distributions with heavy tails or irregularities. While this assumption is essential for maintaining theoretical rigor, it may limit the applicability of the models to a narrower range of problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CPQpBFDYCz", "reviewer": "Reviewer_cL12", "summary": "The paper proposes a new approach to diffusion-based generative modeling that leverages second-order derivatives of the log-density function to achieve accelerated convergence. The framework assumes that the underlying distribution has a finite second-order moment and an infinitely smooth density with respect to the Lebesgue measure. For cases where the distribution lacks infinite smoothness, the algorithm is shown to converge to a convolution of the original distribution with a Gaussian distribution.\n\nThe main results provide an upper bound on the KL-divergence between the learned and target distributions. This bound depends on the number of iterations, the error in estimating the gradient and Hessian of the log-density, and a remainder term involving higher-order derivatives of the smoothed density function. The paper also examines Gaussian mixtures and distributions with Lipschitz-continuous log-densities in detail, explicitly characterizing the dependence of the remainder term on the dimension in these cases.", "questions": "I have several questions regarding Theorem 1 and Corollary 1, which form the central results of the paper. \n\nIn Theorem 1, constants are encapsulated within the notation $\\lesssim$. I assume these constants depend on the distribution $Q_0$. It would be valuable to clarify which specific characteristics of $Q_0$ influence these constants. In particular, given that the theorem assumes the density $q_0$ of $Q_0$ is analytic, it would be helpful to know whether the constants depend on the derivatives of $q_0$.\n\nIf these constants are independent of $q_0$ and its derivatives, this would imply that the claim of Theorem 1 might not require the assumption that $q_0$ is infinitely smooth. Conversely, if the constants do depend on $q_0$ or its derivatives, then it raises the possibility that Theorem 1's claim may not be applicable in proving Corollary 1.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper deals with an important and timely problem.\n2. The idea of considering the second-order derivatives to accelerate the convergence is interesting and the results presented in the paper show that it leads to some improvements.\n3. The authors did a great job in discussing the prior work and in comparing their results to previous ones.", "weaknesses": "### **Main concern**\nMy primary concern with this paper is the quality of the writing, which requires significant polishing to reach a publishable standard.\n\nThe main contributions of this work are clearly mathematical and reside in the theorems presented. The proofs are highly technical, involving lengthy and intricate computations. However, the current presentation makes the proofs challenging to follow and verify. This poses a problem, as reviewers often lack the time to check such detailed proofs thoroughly. If an error were to be found in a proof, it would substantially diminish the paper’s value.\n\nI strongly recommend that the authors dedicate additional time and effort to revising the manuscript for clarity, making the technical sections easier to parse and verify.\n\n### **Specific comments/typos**\n- Lines 176-177: Avoid writing expressions such as \"for all $1 \\leqslant t$\" or \"$\\forall 1 \\leqslant t$\", as these read ambiguously as \"for all 1 that are less than $t$,\" which is clearly not the intended meaning. Instead, use \"for all integers $t \\in [0, T]$\" or \"for all $t \\in \\\\{1, \\ldots, T\\\\}$\" to convey the intended range of values.\n- line 215: I find it worrisome that the total variation is defined as the supremum over **all** subsets $A$ of $\\mathbb R^d$. This should be replaced by all the measurable subsets of $\\mathbb R^d$. \n- Lines 213–218: I do not see any reason for using the notation $\\hat P'_0$ in this paragraph. It would be preferable to maintain consistency with the next paragraph by defining the KL-divergence between two measures $Q$ and $P$ instead.\n- Line 220: Instead of 'when $q_0$ exists', it would be more accurate to write \"when $Q_0$ is absolutely continuous with respect to $\\hat P_0'$.\" The existence of $q_0$ alone does not ensure that the KL-divergence is finite.\n- Line 243: For the Ozaki discretization, it would be more suitable to cite the papers\n  1.  T. Ozaki. A bridge between nonlinear time series models and nonlinear stochastic dynamical systems: a local linearization approach. Statistica Sinica, 2(1):113–135, 1992.\n  2. O. Stramer and R. L. Tweedie. Langevin-type models. II. Self-targeting candidates for MCMC algorithms. Methodol. Comput. Appl. Probab., 1(3):307–328, 1999b\n- Line 244: \"estimate\" -> \"estimates\"\n- Eq. (6): There is no guarantee that this matrix is positive semi-definite and, therefore, can be used as a covariance matrix. I agree that for most $x_t$ this will be the case for large $T$, but it is necessary here to have a definition that works for **every** $x_t$. \n- Line 251: \"denote as Hessian matching\" -> \"refer to as Hessian matching\".\n- Line 262: It is better to remove the second equality here and to keep it in the claim of Lemma 1 only.\n- Line 269 (and in several places in the proof): instead of writing the marginal distributions of $X_0$ and $\\bar W_t$, it is necessary to indicate the joint distribution of these random variables. It suffices to write $(X_0,\\bar W_t)\\sim Q_0\\otimes \\mathcal N(0,I_d)$. \n- line 280: \"satisfy\" -> \"satisfies\"\n- lines 277-289: It is generally not recommended to refer to material, such as an assumption, before it has been introduced. In this case, Assumption 3 is mentioned before it is properly stated. Similarly, within the text of Assumption 3, Assumption 4 is referenced prior to its statement. I strongly recommend that the authors adjust the flow of the text to avoid such inversions.\n- Lemma 2: In the statement of this lemma and in other places, the meaning of the Landau notation $O(\\cdot)$ is unclear. It should be specified that this notation is understood in the asymptotic limit $T \\to \\infty$. Additionally, in Eq. (10), there should be no term depending on $t$ on the right-hand side. Either $\\alpha_t$ should be replaced with $\\alpha_T$, or, preferably, the left-hand side should be divided by $(1 - \\alpha_t)^2$ within the maximum. **My recommendation would be to avoid these notation and to prefer more conventional writing** ``there exist constants $C_1$ and $C_2$ such that ... for all $T\\in\\mathbb N$''. \n- Line 281: $\\alpha_t$ is not defined in (1). I guess you wanted to write Definition 1 instead of (1).\n- Lines 287–288: Since $H_t$ first appears on line 287, it would be clearer to move the indication \"defined by (8)\" forward to accompany its first mention.\n- Line 287: It is unclear why the factor $(1 - \\alpha_t)$ is retained on the left-hand side while $O(1 - \\alpha_t)$ is used on the right-hand side. Rather than writing $(1 - \\alpha_t) g_t = O(1 - \\alpha_t)$, wouldn’t it be clearer to simply write $g_t = O(1)$? Additionally, should this relation hold uniformly for $\\ell \\geqslant 1$?\n- Line 300: What is the precise meaning of *analytic* in this context? I was unable to find a definition in the text, either in the main body or in the appendix.\n- Assumption 4: Same remark as above, I guess it is possible to suppress the factors $(1-\\alpha_t)^{p\\ell}/2$ on both sides of the equalities.\n- Assumption 4: What is $p$ in this assumption? Should the boundedness of $p$-th order derivatives hold for every $p$? Should the upper bound be independent of $p$?\n- Definition 1: This should be stated as a condition rather than a definition.\n- Line 342: I did not find the definition of $\\widehat P_0'$. \n- Line 376: \"titling\" -> \"tilting\"\n- Line 389: \"rest two terms\" -> \"remaining two terms\".\n \n- I guess in the claim of Theorem 1 it is also necessary to assume that $q_0(x)>0$ for all $x$. Indeed, if this condition is not satisfied, the term $\\log q_0(\\mu_1(X_1))$ appearing in the right-hand side of the equation on line 344 is meaningless.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WmPMxkFs60", "reviewer": "Reviewer_ZY6t", "summary": "This paper continues the study of proving convergence bounds for diffusion models under the assumption of accurate score estimation, with a focus on improved dependence on the target error. The \"standard\" rate achieved by DDPMs is an iteration complexity of $O(d/\\epsilon^2)$ for sampling any distribution with finite variance to $\\epsilon$ error in TV (after it has been perturbed with a small amount of noise), due to Benton et al. '23 and Conforti et al. '23. A number of recent works have tried to improve the $\\epsilon$ dependence to $1/\\epsilon$, but only in more specialized settings (e.g. assuming smoothness or bounded support). One of the main results of this work is to show such a result under only the assumption of finite variance. They achieve an iteration complexity of $O(d^{3/2}/\\epsilon)$ using a diffusion-based sampler that has approximate access to both the score function *and its Jacobian*. In the smooth setting, they obtain samplers with similar scaling under one of two assumptions: 1) second-order of the smoothness, and 2) Gaussian mixture.", "questions": "- A recent work of [Gatmiry-Kelner-Lee](https://arxiv.org/abs/2404.18869) also established bounds on higher-order scores of Gaussian mixtures, though specifically in the context of identity-covariance components. How do their bounds compare to the ones proved in this submission?\n- To get intuition for the assumption for Theorem 4: Is there an example of a second-order smooth data distribution for which the scores along the trajectory are not all first-order smooth?\n- Perhaps it is worth including in the related work some discussion on the use of higher-order scores for diffusion models in practice like GENIE?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The result in the finite variance setting (Theorem 3) improves upon prior work in a few directions. Firstly, among works that achieve scaling $O(1/\\epsilon)$ or better, theirs achieves the best dimension dependence. Secondly, unlike the most relevant preceding work of Li et al. '24c, the present work can tolerate score error. Finally, compared to those prior works, the present work applies in a more general setting where the distribution only has finite variance rather than bounded support.\n\nThe Gaussian mixture result is interesting as it requires proving new bounds on the higher-order derivatives of the score function for Gaussian mixtures, which are of independent interest.", "weaknesses": "One weakness is that the sampler requires approximate access to *higher-order* score functions (namely, the Jacobian of the score). While there are examples of diffusion generative models in practice that use higher-order scores essentially by applying automatic differentiation to the first-order score (e.g. GENIE), this is not standard and introduces significant computational overhead. Additionally, these models in practice are not actually trained according to some kind of explicit Hessian matching loss, so it is unclear why one should expect the Jacobian of the score estimates to be close to the Jacobian of the scores. That said, the prior work of Li et al. on acceleration, which appeared in a previous ICLR, also works with second-order access, so this weakness is somewhat justifiable.\n\nAlso, not a weakness per se, but note that the result for second-order smoothness (Theorem 4) is technically incomparable to the other previous works getting $1/\\epsilon$ scaling because while it does not assume smoothness along the trajectory, it needs to assume that the *Hessian* of the log-density is Lipschitz. And as mentioned above, this result requires second-order scores whereas the probability flow ODE paper of Chen et al. only uses first-order scores.\n\nAnother note: while the authors are careful to clarify the chronology of the various related works, it is worth pointing out that in the last month or so (and before the ICLR deadline), there have been important developments in this literature that supersede some of the main results of this submission. For instance, [Li & Yan](https://arxiv.org/pdf/2409.18959) showed that even for the standard SDE-based sampler (without second-order score), one can achieve an accelerated rate of $O(d/\\epsilon)$, in fact under only a *first* moment bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)