Reverse Transition Kernel: A Flexible Framework to Accelerate Diffusion Inference
Authors: Xunpeng Huang
Difan Zou
Hanze Dong
Yi Zhang
Yian Ma
Tong Zhang
Venue: NeurIPS 2024 spotlight (2024)
Keywords: diffusion inference
reverse transition kernel
Primary area: probabilistic_methods

Abstract: To generate data from trained diffusion models, most inference algorithms, such as DDPM, DDIM, and other variants, rely on discretizing the reverse SDEs or their equivalent ODEs. In this paper, we view such approaches as decomposing the entire denoising diffusion process into several segments, each corresponding to a reverse transition kernel (RTK) sampling subproblem. Specifically, DDPM uses a Gaussian approximation for the RTK, resulting in low per-subproblem complexity but requiring a large number of segments (i.e., subproblems), which is conjectured to be inefficient. To address this, we develop a general RTK framework that enables a more balanced subproblem decomposition, resulting in $\tilde O(1)$ subproblems, each with strongly log-concave targets. We then propose leveraging two fast sampling algorithms, the Metropolis-Adjusted Langevin Algorithm (MALA) and Underdamped Langevin Dynamics (ULD), for solving these strongly log-concave subproblems. This gives rise to the RTK-MALA and RTK-ULD algorithms for diffusion inference. In theory, we further develop the convergence guarantees for  RTK-MALA and RTK-ULD in total variation (TV) distance: RTK-ULD can achieve $\epsilon$ target error within $\tilde{\mathcal O}(d^{1/2}\epsilon^{-1})$ under mild conditions, and  RTK-MALA enjoys a $\mathcal{O}(d^{2}\log(d/\epsilon))$   convergence rate under slightly stricter conditions. These theoretical results surpass the state-of-the-art convergence rates for diffusion inference and are well supported by numerical experiments.

Reverse Transition Kernel: A Flexible Framework to Accelerate Diffusion Inference
Xunpeng Huang
Difan Zou HKU dzou@cs. hku.
Hanze Dong
HKUST
Salesforce AI Research
xhuangck@connect.co ust.
hanze. wwwg@salessooree.......
Yi Zhang
Yian Ma UC San Diego
Tong Zhang UIUC
HKU yizhang101 Saapanggg@@coonnncie @cwonecct.....cc..oe.cm.. hku
yi rriama@uued.eed
tongzhangttoogzhang--ii org
Abstract
To generate data from trained diffusion models, most inference algorithms, such DDPM [17], DDIM [31], and other variants, rely on discretizing the reverse SDEs their equivalent ODEs. In this paper, we view such approaches decomposing the entire denoising diffusion process into several segments, each corresponding to reverse transition kernel (RTK) sampling subproblem. Specifically, DDPM uses a Gaussian approximation for the RTK, resulting in low per-subproblem complexity but requiring a large number segments (i.e., subproblems), which is conjectured to be inefficient. To address this, we develop general RTK framework that enables a more balanced subproblem decomposition, resulting in Ô(1) subproblems, each with strongly log-coneave targets. We then propose leveraging two fast sampling algorithms, the Aattropolis-Adjuster Langevin Algorithm (MALA) and Underdamped Langevin Dynamics (ULD), for solving these strongly log-concave subproblems. This gives rise to the RTK-MALA and RTK-ULD algorithms for diffusion inference. In theory, we further develop the convergence guarantees for RTK-MALA and RTK-ULD in total variation (TV) distance: RTK-ULD can achieve target error within (ld-/2g-1) under mild conditions, and RTK- MALA enjoys (d log(d/c)) convergence rate under slightly stricter conditions. These theoretical results surpass the state-of-the-art convergence rates for diffusion inference and are well supported by numerical experiments.
Introduction
Generative models have become a core task in modern machine learning, where the neural networks employed to learn the underlying distribution from training examples and generate new data points. Among various generative models, denoising diffusions have produced state-of-the-art performance in many domains, including image and text generation [14, 2, 28, 29], text-to-speech synthesis [27], and scientific tasks [34, 37, 5]. The fundamental idea involves incrementally adding noise and gradually transform the data distribution to prior distribution that is casier sample from, e.g., Gaussian distribution. Then, diffusion models parameterize and learn the score the noised distributions to progressively denoise samples from priors and recover the data distribution [36, 32].
Under this paradigm, generating data denoising diffusion models involves solving series of sampling subproblems, i.e.. generating samples from the distribution after one-step denoising. To this end, DDPM [17], one of the most popular sampling methods in diffusion models, has been developed for this purpose. DDPM uses the Gaussian transition with carefully designed mean and covariance to approximate the solutions to these sampling subproblems. By sequentially stacking
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

series of Gaussian transitions, DDPM successfully generates high-quality samples that follow the data distribution. The empirical success of DDPM has immediately triggered various follow- up work [33, 25], aiming to accelerate the inference process and improve the generation quality. Alongside rapid empirical research on diffusion models and DDPM-like sampling algorithms [19, 39], theoretical studies have emerged to analyze the convergence and sampling error of DDPM. In particular, [21, 24, 8, 7. 3, 9] have established polynomial convergence bounds, in terms of dimension d and target sampling error for the generation process under various assumptions. Previous work usually assume the score estimation error to construct the sampling analysis [8, 13, 3, 19). A typical bound under minimal data assumptions on the score of the data distribution is provided by [8, 3), which establishes Odde= ?) score estimation guarantces to sample from data distribution within e-sampling error in the Total Variation (TV) distance.
In essence, the denoising diffusion process can be approached through various decompositions of sampling subproblems, where the overall complexity depends on the number of these subproblems multiplied by the complexity of solving each one. Within this framework, DDPM can be regarded as a specific solver for the denoising diffusion process that heavily prioritizes the simplicity of subproblems over their quantity. In particular, it adopts simple one-step Gaussian approximations for the subproblems, with ((1) computation complexity, but needs to deal with a relatively large Odd 2 target subproblems to ensure the cumulative sampling error is bounded by e in TV distance. This imbalance raises the question of whether the DDPM-like approaches stand the most efficient algorithm, considering the extensive potential subproblem decompositions of the denoising diffusion process. We therefore aim to:
accelerate the inference of diffusion models via a more balanced subproblem decomposition in the denoising process.
In this work, we propose a novel framework called reverse transition kernel (RTK) to achieve exactly that. Our approach considers a generalized subproblem decomposition of the denoising process, where the difficulty of each sampling subproblem and the total number of subproblems are determined by the step size parameter 1j. Unlike DDPM, which requires setting 1) é resulting in approximately Ö(1/n) = Ó(1/e²) subproblems. our framework allows 1/ to be feasible in a broader range. Furthermore, we demonstrate that a more balanced subproblem decomposition can be attained by carefully selecting 1 = @(1) as a constant, resulting in approximately (1) sampling subproblems, with each target distribution being strongly log-concave. This nice property further enables to efficiently solve the sampling subproblems using well-established acceleration techniques, such as Metropolis Hasting step and underdamped discretization, without encountering many subproblems. Consequently, our proposed framework facilitates the design of provably faster algorithms than DDPM for performing diffusion inference. Our contributions can be summarized as follows.
We propose a flexible framework that enhances the efficiency of diffusion inference by balancing the quantity and hardness of RTK sampling subproblems used to segment the entire denoising diffusion process. Specifically, we demonstrate that with a carefully designed decomposition, the number of sampling subproblems can be reduced to approximately Ö()), while ensuring that all RTK targets exhibit strong log-concavity. This capability allows us to seamlessly integrate a range of well-estaallihed sampling acceleration techniques, thereby enabling highly efficient algorithms for diffusion inference.
Building upon the developed framework, we implement the RTK using the Metropolis-Adjustee Langevin Algorithm (MALA), making it the first attempt to adapt this highly accurate sampler for diffusion inference. Under slightly stricter assumptions the estimation errors of the energy difference and score function, we demonstrate that RTK-MALA can achieve linear convergence with respect to the sampling error c, specifically (log(1/c)), which significantly outperforms the ((1/²) convergence rate DDPM [8. 3]. Additionally, we consider the practical diffusion model where only the score function is accessible and develop a score-only RTK-MAL algorithm. We further prove that the score-only RTK-MALA algorithm can achieve an error e with complexity of Ö(E 22(em1) 22), where u can be an arbitrarily large constant, provided the energy function satisfies the u-th order smoothness condition.
We further implement Underdamped Langevin Dynamics (ULD) within the RTK framework. The resulting RTK-ULD algorithm achieves state-of-the-arr complexity of ( for both d

---

and dependence under some mild assumptions as [13]. Compared with the () complexity guarantee for DDPM, it improves the complexity with (1d factor. This result also matches the state-of-the- convergence rate of the bas-b methods [9], though those methods require Lipschitz conditions for both the ground truth score function and the score neural network.
Preliminaries
In this section, first introduce the notations used in subsequent sections. Then, we present several distinct Markov processes to demonstrate the procedures for adding noise to existing data and generating new data. Besides, we specify the assumptions required for the target distribution in our algorithms and analysis.
Notations, We say a complexity
+ R to be h(n) = (n²*) or h(n) = (n²² if the complexity satisfies h(n)) < c n or h(n)) < c n [log(n)] for absolute contant c, l and k'. We use the lowercase bold symbol to denote random vector, and the lowercase italicized bold symbol represents a fixed vector. The standard Euclidean norm is denoted by -| The data distribution is presented as p. x cxp(- (ep(-f.). Besides, we define two Markov processes R. i.e.,
(xt (x),T))
{ (O) where T = Kn.
In the above notations, T presents the mixing time required for the data distribution converge to specific priors, K denotes the iteration number the generation process, and signifies the corresponding step size. Further details of the two processes are provided below.
Adding noise data with the forward process. The first Markov process {x+} corresponds to generating progressively noised data from p.. In most denoising diffusion models, {x,] } is an Monstin-UUhlebeen (OU) process shown as follows
dx, x, v2dB where Xg ~ P. & exp(-f.)-
(1)
If denote underlying distribution of x, Pt x exp(-It) meaning fo = Sa, the forward OU process provides an analytic form of the transition kernel, i.e.,
x' - e (1' -1-
(ar (x) (er,e(x', .x)
(2 (1-c-2(((0)) 44/2
(x
exp
c 2(1
(2)
for any E' where Pr., denotes the joint distribution of (xy', Xt). According to the Fokker-Planck equation, we know the stationary distribution for SDE. (1) is the standard Gaussian distribution.
Denoising generation with reverse SDE. Various theoretical works [21, 24, 8, 7, 3] based on DDPM [17] consider the generation process of diffusion models as the reverse process of SDE. (1) denoted {xā-). }. According to the Doob's h--rranfform, the reverse SDE, i.e., {xr} }. follows from
dx; = (x, + 2V Pn
pr (xx;))xx)x)))))))))))))))))))(
2dd
whose underlying distribution pt satisfies pr-t pf. Similar to the definition of transition kernel shown in Eq. (2), we define Per (xo x)) = pžr, (x', /pp (x) for any 2 t 2 and name it as reverse transition kernel (RTK).
To implement SDE. (3), diffusion models approximate the score function V In In with parameterized neural network model, denoted by 80,t, where denotes the network parameters. Then, SDE, (3) can be practically implemented by
dx
(x, + 289, (xm))) dt + /2dB, for EE [kn, (k + 1)m)
(4)
with standard Gaussian initialization, No ~ (O,, I). Eq. (4) has the following closed solution
1)4 = e Xan 2(1 -"))so.r + - and E~ (0,,
(5)
which is exactly the DDPM algorithm.
3

---

DDPM approximately samples the reverse transition kernel. DDPM can also be viewed as an approximated sampler for RTK, i.e., P (</|>) [z) for some t' > t. particular, the update of DDPM at the iteration & applies the Gaussian-type transition, i.c.,
kn (2=) N (e 2(1 ko (z); (e 1)
(6)
to approximate the distribution 1ik++)ml (z)) [17]. Specifically, by the chain rule of KL divergence, the gap between the data distribution P. and the generated distribution Pr satisfies
KL. (Dr lI--) s KL (x
po +
Σ
Ex-Tin [T. (Fu (- (PR
(7)
where K T/n is the total number of iterations. For DDPM, to guarantee small sampling error, we need to use a small step size 17 to ensure that p(l++)ynlky is sufficiently close to P(s+1))lkkr" Then, the required iteration numbers K T will be large and dominate the computational complexity. In Chen et al. [8, 10), it shown that one needs to set 1) ( to achieve sampling error in TV distance (assuming no score estimation error) and the total complexity is K - Ó(1/²).
Intuition for General Reverse Transition Kernel. As previously mentioned, DDPM approximately solves RTK sampling subproblems using small step size 17. While this allows for efficient one-step implementation, it necessitates a large number of RTK sampling problems. This naturally creates a trade-off between the quantity of RTK sampling problems and the complexity of solving them. To address this, one can consider a larger step size 1). which results in a relatively more challenging RTK sampling target P(k++ 1)y boy and reduced number of sampling problems (K = 7/n). By examining general choice for the step size 17. the generation process of diffusion models can be depicted through a comprehensive framework of reverse transition kernels, which will be explored in depth in the following section. This framework enables the design of various decompositions for RTK sampling problems and algorithms to solve them, resulting in an extensive family of generation algorithms for diffusion models (that encompasses DDPM). Consequently, this also offers the potential to develop faster algorithms with lower computational complexities, e.g., applying fast sampling algorithms for sampling the RTK, i.c., P(k++ 1)o(ke, with a reasonably large 7).
General Assumptions. Similar to the analysis of DDPM [8, 7], we make the following assumptions on the data distribution p. that will be utilized in the theory.
[A1] For all t 2 O, the score v Im is L-Lipschitz.
[A2] The second moment of the target distribution p. is upper bounded, i.e., Ep. [II-1]] m
Assumption [A1] is standard one in diffusion literature and has been used in many prior works [4, 10, 21, 9]. Moreover, we do not require the isoperimetric conditions, e.g., the establishment of the log-Sobolev inequality and the Poincaré inequality for the data distribution p.. as [21], and the convex conditions for the energy function f. as [4]. Therefore, our assumptions cover a wide range of highly non-log-concave data distributions. We emphasize that Assumption [A1] may be relaxed only to assume the target distribution is smooth rather than the entire OÚ process, based on the technique in [7] (see rough calculations in their Lemmas 12 and 14). We do not include this additional relaxation in this paper clarify our analysis. Assumption [A2] one of the weakest assumptions being adopted for the analysis of posterior sampling.
3 General Framework of Reverse Transition Kernel
This section introduces the general framework of Reverse Transition Kernel (RTK), As mentioned in the previous section, the framework is built upon the general setup of segmentation: each segment has length 77; within each segment, we generate samples according to the RTK target distributions. Then, the entire generation process in diffusion models can be considered as the combination of series of sampling subproblems. In particular, the inference process via RTK is displayed in Alg. 1.
The implementation of RTK framework. We begin with a new Markov process ( (Xa,) ) }== I...,, satisfying K₁ = T, where the number of segments K, segment length 7), and length of the entire process I' correspond to the definition in Section 2. Consider the Markov process (xe,) as the

---

Algorithm 1 INFERENCE WITH REVERSE TRANSITION KERNEL (RTK)
1: Input: Initial particle &o sampled from the standard Gaussian distribution, Iteration number K, Step size 77, required convergence accuracy e:
2: for k = 0 to K do
3: Draw sample (()++)y with MCMCs from P(k-1)nnler) (- {8b)) which approximates the ground-
truth reverse transition kernel, i.e.
| E E-912- )
(nn & exp(-g(()) = exp (f(x-tt
(8)
2(1 e: e-21)
4: return Sk.
generation process of diffusion models with underlying distributions (f we require jo = (O, I) and PK,, P.. which is similar the Markov process {xf,) In order to make the underlying distribution of output particles close the data distribution, can generate Xky with Alg. which is equivalent to the following steps:
Initialize Xy with casy-to-sample distribution, e.g., (V, I). which is close PKm- Update particles by drawing samples from (y which satisfies
p(- 1ylken (-188)))
R2 P(x P(k 1) (118)))
Under these conditions, if Pkey ) R P(K- then we have
P()+1)((2) (P(k+ (2).). Pi,, (2)))
P(N++))(
for any A E I0.,, K}. This means we can implement the generation of diffusion models by solving series sampling subproblems with target distributions P(x+1)m)kk) kny kny (-)+)))))),(((()))))))))))
The close form of reverse transition kernels. determining the analytic form of RTK Prije (a=' (x:) for and t' 2 t 2 0 which is shown in the following lemma whose proof is deferred Appendix B.
implement Alg. 1, the most critical problem is
Lemma 3.1. Suppose Markov process {xi} with SDE. 1, then any t' > t, we have
x e -0)
PT- (x- (x|x') = (x)r(() x exp
-f((z) 2(1 c -1)
The first critical property shown in this Lemma is that RTK Pap is perturbation of pt with l2 regularization. This means if the score of Pt, i.e., Vf-- can be well-estimated, the score of RTK, i.e. V Po e can also be approximated with high accuracy. Moreover, in the diffusion model, Vs+ = log is exactly the score function at time 4, which is approximated by the score network function s (ar), then
log (w/a²) = fx())) 2(1-
e- 10- (1
2(1 2(1 fr e (1' -0w
(0,
1 - 2(p
1 2(1-0
which can be directly calculated with a single query of (x.( The second critical property of RTK is that we can control the spectral information of its score by tuning the gap between and t. Specifically, considering the target distribution, i.c., P(K- k-1) (k-)) for the k-th transition, the Hessian matrix of its energy function satisfies
e
2 log -o
V2 V'S + 1-e-2n I.
P( 1)n can be lower bounded by -LI, which implies that RTK P(K k- )/m k)n will be L-strongly log-concave and 3L-smooth when the step size is set 1 1/2 log(1 + 1/2L). This further implies that the targets
According to Assumption [A1], the Hessian f2 f2 -v2
5

---

of all subsampling problems in Alg. will be strongly log-con,ave, which can be sampled very efficiently by various posterior sampling algorithms.
Sufficient conditions for the convergence. According to Pinsker's inequality and Eq. (7), we can obtain the following lemma that establishes the general error decomposition for Alg. 1.
Lemma 3.2. For Alg I, we have
TV (fkm P.) S (1 +
[VV -xxp0 exp(-Kn)
K
Exnppn
KL
(((x+1)))k((1)))))) (1
(a (11x)
k=0
for any K E N+ and 1) E R.p.
is worth noting that the choice of 1 represents a trade-off between the number of subproblems divided throughout the entire process and the difficulty of solving these subproblems. By considering the choice = 11/2-log(( +1 1/2T), we can observe two points: (1) the sampling subproblems in Alg. tend to be simple, as all RTK targets, presented in Lemma 3.1, can be provably strongly log-concave; (2) the total number of subproblems is K T/n O(),, which is not large. Conversely, when considering a larger that satisfies >> log(1 + 1/), the RTK target will no longer be guaranteed to be log-concave, resulting in high computational complexity, potentially even exponential in d, when solving the corresponding sampling subproblems. On the other hand, if a much smaller step size 77 = (11 is considered, the target distribution of the sampling subproblems can be easily solved, even with one-step Gaussian transition. However, this will increase the total number of sampling subproblems, potentially leading higher computational complexity.
Therefore, we will consider the setup 17 = 1/2-log' + +1/2L) in the remaining part of this paper. Now, the remaining task, which will be discussed in the next section, would be designing and analyzing the sampling algorithms for implementing all iterations of Alg. 1, i.e., solving the subproblems of RTK.
Implementation of RTK inner loops
In this section, we outline the implementation of Step 3 in the RTK algorithm, which aims to solve the sampling subproblems with strong log-concave targets, i... p(k+ (-1xk)) exp(-g). Specifically, we employ two MCMC algorithms, i.e., the Metropolis-adjuster Langevin algorithm (MALA) and underdamped Langevin dynamics (ULD). For each algorithm, we will first introduce the detailed implementation, combined with some explanation about notations and settings to describe the inner sampling process. After that, we will provide general convergence results and discuss them in several thcoretical or practical settings. Besides, we will also compare our complexity results with the previous ones when achieving the convergence of TV distance to show that the RTK framework indeed obtains a better complexity by balancing the number and complexity of sampling subproblems.
RTK-MALA. Alg. 2 presents a solution employing MALA for the inner loop. When it is used to solve the k-th sampling subproblem of Alg. 1, zy equal Sky defined in Section and used to initialize particles iterating in Alg. 2. In Alg. 2, we consider the process {z.)a whose underlying distribution is denoted as [4,]5 15-0- Although we expect μs to be close to the target distribution 1))=1))(k77 (2r)), in real practice, the output particles zş can only approximately follow P( (2)) due to inevitable errors. Therefore, these errors should be explained in order to conduct a meaningful complexity analysis of the implementable algorithm. Specifically, Alg. 2 introduces two intrinsic errors:
[E1] Estimation error of the score function: we assume a score estimator, e.g., a well-trained diffusion model, 8o, which can approximate the score function with an excore error, i.e., [[=),(=)) V log (=)]l S Escare for all z E IRd and E [0, T].
[E2] Estimation error of the energy function difference: we assume an energy difference estimator r which can approximate energy difference with an cenergy error, i.e., |r,(2', 2) + (x'') log (z)) S Conergy for all 2, z' E Rdd.
Under these settings, we provide a general convergence theorem for Alg. 2. To clearly convey the convergence properties, only show an informal version.

---

Algorithm 2 MALA/PROIECTED MALA FOR RTK INFERENCE
1: Input: Returned particle of the previous iteration Zo. current iteration number k, inner iteration number S, inner step size т, required convergence accuracy
2: Draw the initial partiele %g from
po(dz) dz
x exp -I||=112 a100 e "=
2(1 c-2
3:
for to do
4:
Draw sample 2, from the Gaussian distribution NVs s0(2z) 2r1))
5:
if 2 $ (2,,, (i0, , R) then
6:
Ze+1 ze
> This condition step is only activated for Projected MALA.
7: continue:
8:
Calculate the accept rate as
a(z, (Zs T. -0 2z)
|r
50 (z()))
||2, E. 80 21
=min 1, exp Ta(Zs;2a) 2x)
9:
Update the particle #s41 2g with probability a, otherwise 2s+1 2
return zs;
Theorem 4.1 (Informal version of Theorem C.17). Under Assumption [AI]-[A2], for Alg. choose
2L +
and k= 4L log (L L (O]]
n= 2= log
2L
2²
and implement Step 3 of Alg. 1 with Alg. 2. Suppose the score [EI], energy [E2] estimation errors and the inner step size T satisfy
Escore Opd 1/2),
Cenergy (2p) and Ō 2 (d + m2 223-1)
and the hyperparameters, i.e., R and r. are chosen property. We have
TV (pKn.p-) Ö(c)) (O(L(d (m)()++m)))) mā)))- (1 (1- +0
LCanergy pri/2
+0
(9)
P
where p is the Cheeger constant of truncated inner target distribution (xp(--9(2))1k E B(0, R) and denotes the maximal l2 norm of particles appearing in outer loops (Alg. 1).
It should be noted that the choice of choice ensures the L strong log-concavity of target distribution cx)(-g(z)), which means its Cheeger constant is also L. Although the Cheeger constant p in the second term of Eq. 9 corresponding to truncated exp( g( ()) should also be near L intuitively, current techniques only provide a loose lower bound at an O /L/d//d)oonn
(proven in Corollary C.8). While both cases above, the Cheeger constant is independent with e. Combining this fact with an e-independent choice of inner step sizes the second term of Eq. 9 will converge lincarly with respect to e. As for the diameter Z of particles used to upper bound т, though may be unbounded in the standard implementation of Alg. 2, Lemma C. can upper bound with Ô (I + m²)p=1) under the projected version of Alg. 2.
Additionally, to require the final sampling error to satisfy TV (pKn, P.) S Ö Eq. 9 shows that the score and energy difference estimation errors should be c-dependent and sufficiently small, where Escore corresponding to the training loss can be well-controlled. However, obtaining highly accurate energy difference estimation (requiring small Conergy) is hard with only diffusion models. To solve this problem, we can introduce neural network energy estimator similar to [38] to construct r(2', 222,,,1)) 2,)), which induces the following complexity describing the calls the score estimation.
Corollary 4.2 (Informal version of Corollary C.19). Suppose the estimation errors of score and energy difference satisfy
Escore 5 Pe and Cenergy S 12 (d + m2 + Z)
Pe
Ld-/2
7

---

Algorithm 3 ULD FOR RTK INFERENCE
1: Input: Returned particle of the previous iteration 2o. current iteration number k, inner iteration number S, inner step size т, velocity diffusion coefficient 7, required convergence accuracy e;
2: Initialize the particle and velocity pair, i.e., (2u, 06) with Gaussian type product measure, i.e., (0, 3: for t = s to S - do
No e
4:
Draw noise sample pair (Lg (g) from Gaussian type distribution.
5:
2.+1 2,
e-"" jd, - (T 7 1 --> ())))))(())))) + E
6:
0z41 6 Us - 7 (1 e
e->r)))) (0077)ss0 (2s) + +7
7:
return Z5:
we implement Alg. with the projected version of Alg. 2 with the same hyperparameter settings as Theorem 4.1, it has TV (D)m.P.) S (c) with an OL p-2 (d m3)+ 2 z log(d/c)) complexity.
Considering the loose bound for both p and Z, the complexity will be most ( m3) which is the first linear convergence w.r.t. result for the diffusion inference process.
Score-only RTK-MALA. However, the parametric energy function may not always exist in real practice. We consider a more practical case where only the score estimation is accessible. In this case, will make use of estimated score functions to approximate the energy difference, leading to score-only RTK-MALA algorithm. In particular, recall that the energy difference function takes the following form:
2 z' 7
300 e
g(=') -()) = - -oggP(K---1))
2(1 - e e22 + log (ogp(K-- logP((---1))(=))
2(1 e e-20)
Since the quadratic term can be obtained exactly, we only need to estimate the energy difference. Then let f() log P(K-k-1)m (z) and denote h(t) = ((2' - =) + + 2), the energy difference
g(z') (z)) can be reformulated as
(0
and (1)= = d'h(t) (dt)
((1) - (()) = Σ
where we perform the standard Taylor expansion at the point / = 0. Then, we only need the derives of I'' (0), which can be estimated using only the score function. For instance, the (()) can be estimated with score estimations:
+ 2) (t) = V - 2) +
(z' ~ (t) = so((2' - -) + (2' z).
Moreover, regarding the high-order derivatives, we can recursively perform the approximation: (0) = (A() - 7. (1))/A/ Consider performing the approximation up to u-order derivatives, we can get the approximation of the energy difference:
1,00
(x
i
Then, the following corollary states the complexity of the score-only RTK-MALA algorithm.
Corollary 4.3. Suppose the estimation errors of the score satisfies Cscore < pc/ (La and the log-likelihood function of pt has bounded u-order derivative, e.g., | [(z) S L,, we have non- parametric estimation for -ogeeiill to make we have TV (pKn. P.) ) S Ō()) with a complexity shown as follows
ò (L (d m2) 23/2-2/(um1) 2")
This result implies that if the energy function is infinite-order Lipschitz, we can nearly achieve any polynomial order convergence w.r.t. with the non- non- oon-arametric energy difference estimation.
RTK-ULD. Alg. 3 presents a solution employing ULD for the inner loop, which can accelerate the convergence of the inner loop due to the better discretization of the ULD algorithm. When it is used

---

Results
Algorithm
Assumptions
Complexity
Chen et al. [8]
DDPM (SDE-based)
[А]][A2]_Е
O(L2de
Chen et al. [9]
DPOM baseb)
[A]][A2][E]] and &p smoothness
Ó(L
Chen et al. [9]
DPUM SODE-based)
[АΙ]ЛΑЛı[,,] and smoothness
Li al. [24]
ODE-based sampler
[E1] and estimation error of energy Hessian
O(d'c
Corollary 4.2
RTK-MALA
[AI].[A2],EE]], and [E2]
OL log(d/e)
Theorem 4.4
RTK-ULD (ours)
[A1][A22][I]]
O(L2
Table 1: Comparison with prior works for RTK-based methods. The complexity denotes the number of calls for the score estimation to achieve (fKn:P. P.) < Ō(c). d and mean the dimension and error tolerance. Compared with the state-of-thc-art result, RTK-ULD achieves the best dependence for both d and e. Though RTK-MALA requires slightly stricter assumptions and worse dimension dependence, linear convergence w.r.t. makes it suit high-accuracy sampling tasks.
to solve the k-th sampling subproblem of Alg, 1, zo is equal to Xzy defined in Section 3 and used to initialize particles iterating in Alg. 2. Besides, the underlying distribution of noise sample pair is
T
7 (1-e --)) + + 11---2
1 (1 2e -r + 2yT) 1)
(E)
0.
7
y 1 e 2xy
+ (1 20
+ +
In Alg. 3, we consider the process {(2., v=)].=0 whose underlying distribution is denoted as (#x )==0 We expect the z-marginal distribution of nty be close to the target distribution presented in Eq. 8. Then, the complexity of RTT-ULLL to achieve the convergence of TV distance is provided as follows, and the detailed proof is deferred to Theorem D.6. Besides, we compare our theoretical results with the previous in Table 1.
Theorem 4.4. Under Assumptions [A1]-[2] and [E1], for Alg. 1, we choose
7) = 1/2 log (2T. 1)/2T] and K 4T. log[((1 I.2)d + [[VS -
and implement Step 3 of Alg. with projected Alg. 3. For the k-th run of Alg. 3, we require Gaussian-type initialization and high-accurate score estimation, i.e.,
to = N(r,, - 1) (N, and Cecore = =((//VL..
If we set the hyperparameters of inner loops as follows. the step size and the iteration number as
L(d + m2 + | 11 1221) 1/2
T θ
ed 1/2 -1/2
log
2²
S θ
1/2 [og
L(d + m || || [?)]
1/2)
e²
It achieve TV (pkn) px) S with Ô (12d)/2
gradient complexity.
Conclusion and Limitation
This paper presents analysis of a modified version of diffusion models. Instead of focusing on the discretization the reverse SDE, we propose a general RTK framework that can produce a large class of algorithms for diffusion inference, which is formulated as solving sequence of RTK sampling subproblems. Given this framework, we develop two algorithms called RTK-MALA and RTK-ULD, which leverage MALA and ULD solve the RTK sampling subproblems. We develop theoretical guarantees for these two algorithms under certain conditions on the score estimation, and demonstrate their faster convergence rate than prior works. Numerical experiments support our theory.
We would also like to point out several limitations and future work. One potential limitation of this work is the lack of large-scale experiments. The main focus of this paper is the theoretical

---

understanding and rigorous analysis of the diffusion process. Implementing large- scale experiments requires GPU resources and practitioner support, which can be an interesting direction for future work. Besides, though we provided score-only RTK-MALA algorithm, the (11cc) convergence rate can only be achieved by the RTK-MALA algorithm (Alg. 2). However, this faster algorithm requires a direct approximation of the energy difference, which not accessible in the existing pretrained diffusion model. Developing practical energy difference approximation algorithms and incorporating them with Alg. for diffusion inference are also very interesting future directions.
Acknowledgement
The research is partially supported by the NSF awards: SCALE MoDI-2134209, CCF-211 (TILOS). It is also supported, DARPA AIE program, the U.S. Department of Energy, Office of Science, the Facebook Research Award, as well as CDC-RFA-FI--3--OE for Forecasting and Outbreak Analytics. Difan Zou is supported in part by Guangdong NSF 2024A1515012444, NSFC 62306252, and the central fund from HKU IDS.
from the CDC's Center
References
[1] Jason M Altschuler and Sinho Chewi. Faster high-accuracy log-concave sampling via algorithmic warm starts. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2169-2176. IEEE, 2023.
[2] Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34: 1s:117911-79999 2021.
[3] Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly d-linear convergence bounds for diffuusin models via stochastic localization. The Twelfth International Conference on Learning Representations, 2024. URL https://openrevieet wwt.weiwwwwwwwe.runeee/ee net/forum? id=r5njV3BsuD.
[4] Adam Block, Youssef Mroueh, and Alexander Rakhlin. Generative modeling with denoising auto-encoders and Langevin sampling. arXiv preprint arXiv:2002.00107,, 2020.
[5] Nicholas M. Boffi and Eric Vanden- Eijjnenn. Probability flow solution of the Bokker-Plancee equation, 2023.
[6] Peter Buser. A note on the isoperimetric constant. In Annales scientifiques de I' l'école normale supérieure, volume 15, pages 213-230, 1982.
[7] Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learning, pages 4735-4763. PMLR, 2023.
[8] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In International Conference Learning Representations, 2023.
[9] Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ODE is provably fast, Advances in Neural Information Processing Systems, 36, 2024.
[10] Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for proximal algorithm for sampling. Conference on Learning Theory, pages 2984-3014. PMLR, 2022.
[11] Xiang Cheng and Peter Bartlett. Convergence of langevin meme in kl-divergence. In Algorithmic Learning Theory, pages 186-211. PMLR, 2018.
[12] Sinho Chewi. Log-Core Concave Sampling. 2024.
10

---

[13] Valentin De Bortoli, James Thortoo,, Jeremy Heng, and Arnaud Doucet. Diffusion schrödinger bridge with applications score-bar based generative modeling. Advances in Neural Information Processing Systems, 34:17695-17709 2021.
[14] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34:8780-8794, 2021.
[15] Hanze Dong, Xi Wang, LIN Yong, and Tong Zhang. Particle-based variational inference with preconditioned functional gradient flow. In The Eleventh International Conference Learning Representations, 2023. URL https: /twp://veppppeeeeeeeomo net/ wtt.:/orommmndddddidii 60phWWAESSSS..
[16] Raaz Dwivedi, Yuansi Chen, Martin J Wainwright, and Bin Yu. Log-concave sampling: Hetssnss algorithms are fast. Journal of Machine Learning Research, 20(183):1-44 2019.
[17] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 6851,, 2020.
[18] Xunpeng Huang, Hanze Dong, Yifan Hao, Yian Ma, and Tong Zhang. Monte Carlo sampling without isoperimetry: A reverse diffusion approach, 2023.
[19] Xunpeng Huang, Hanze Dong, Yifan HAO, Yian Ma, and Tong Zhang. Reverse diffusion monte carlo. The Twelfth International Conference on Learning Representations, 2024. URL www.rrvviieeeeeeeeeeeeee www. htth:/formmiiddddd i
[20] Holden Lee, Andrej Risteski, and Rong Ge. Beyond log-concavity: Provable guarantees for sampling multi-modal distributions using simulated tempering Langevin Monte Carlo. Advances in neural information processing systems, 31, 2018.
[21] Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. arXiv preprint 2rXiv:2206.06227, 2022.
[22] Yin Tat Lee and Santosh S Vempala. Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1115-1121, 2018.
[23] Yin Tat Lee and Santosh Srinivas Vempala. Eldan's 's stochastic localization and the KLS hyperplane conjecture: an improved lower bound for expansion. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 998- 998-1007. IEEE, 2017.
[24] Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Towards non-asympiotic convergence for diffusion-based generative models. In The Twelfth International Conference on Learning Representations, 2023.
[25] Cheng Lu, Yuhao Zhou, Fan Bao, Jianfei Chen, Chongxuan Li, and Jun Zhu. Dpm-solver: fast ode solver for diffusion probabilistic model sampling in around 10 steps. Advances in Neural Information Processing Systems, 35:5775-5787 2022.
[26] Yi-An Ma, Niladri S Chatterji, Xiang Cheng, Nicolas Flammarion, Peter L. Bartlett, and Michael Jordan. Is there an analog of Nesterov acceleration for gradient-based MCMC? Bernoulli, 27(3), 2021.
[27] Vadim Popov, Ivan Vovk, Vladimir Gogoryan, Tasnima Sadekova, and Mikhail Kudinov. Grad- tts: A diffusion probabilistic model for text-to-speech. In International Conference on Machine Learning, pages 8599-8608. PMLR, 2021.
[28] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with clip latents. arxiv 2022, arXiv preprint arXiv:2204.06125. 2022.
[29] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al. Photorealistic rext-to-image diffusion models with deep language understanding. Advances in neural information processing systems, 15:36479-36494. 2022.

---

[30] Ohad Shamir. A variant of azuma's inequality for martingales with subgaussian tails. arXiv preprint arX1v:1110.2392, 2011.
[31] Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. arXiv preprint arXiv:2010.02550, 2020.
[32] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
[33] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2020.
[34] Brian L. Trippe. Jason Yim, Doug Tischer, David Baker, Tamara Broderick, Regina Barzilay, and Tommi Jaakkola. Diffusion probabilistic modeling of protein backbones 3d for the motif- scaffolding problem. In The Eleventh International Conference on Learning Representations, 2023. URL https: /ttp:://pppeeiieeeeeeeee net/ met/forumiideeeeeeeeeeteetr Xd
[35] Santosh Vempala and Andre Wibisono. Rapid convergence the unadjusted langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems. 32, 2019.
[36] Pascal Vincent. A connection between score matching and denoising autoencoders. Neural computation, 23(7):1661-1674 2011.
[37] Joseph L Watson, David Juergens, Nathaniel R Bennett, Brian L Trippe, Jason Yim, Helen E Eisenach, Woody Ahern Andrew Borst, Robert J Ragotte, Lukas Milles, al. De novo design of protein structure and function with rfdiffusion. Nature, 62097976) 2023.
[38] Xingyu Xu and Yuejie Chi. Provably robust score-based diffusion posterior sampling for plug-and-play image reconstruction. arXiv preprint arXiv:2403. 17042, 2024.
[39] Dinghuai Zhang, Ricky T. Q. Chen, Cheng-Hav Liu, Aaron Courville, and Yoshua Bengio. Diffusion generative flow samplers: Improving learning signals through partial trajectory optimization. In The Twelfth International Conference on Learning Representations, 2024. URL htttps::/openreieeeet tttt:/ttooouut.--IIiiquQQQC.
[40] Shunshi Zhang, Sinho Chewi, Mufan Li, Krishna Balasubramanian, and Murat A Erdogdu. Improved discretization analysis for underdamped Langevin Monte Carlo. In The Thirty Sixth Annual Conference on Learning Theory, pages 36-71. PMLR, 2023.
[41] Difan Zou, Pan Xu, and Quanquan Gu. Faster convergence of stochastic gradient langevin dynamics for non-log-concave sampling. In Uncertainty in Artificial Intelligence, pages 1 1152- 1 1162. PMLR, 2021.
12

---

Contents
1 Introduction
2 Preliminaries
3 General Framework of Reverse Transition Kernel
4 Implementation of RTK inner loops
5 Conclusion and Limitation
A Numerical Experiments
14
Inference process with reverse transition kernel framework
17
C Implement RTK inference with MALA
24
C.I Control the error from the projected transition kernel
27
C.2 Control the error from the approximation of score and energy ................................
C.3 Control the error from Inner MALA to its stationary
35
C.3.1 The Cheeger isoperimetric inequality of i ................................
36
C.3.2 The conductance properties of T.
37
C.4 Main Theorems of InnerMALA
42
Control the error from Energy Estimation
D Implement RTK inference with ULD
50
Auxiliary Lemmas
56
13

---

A Numerical Experiments
In this section, we conduct experiments when the target distribution p. Mixture of Gaussian (MoG) and compare RTK-based methods with traditional DDPM. Specifically, we are considering forward process from an MoG distribution to a normal distribution in the following
K ( of I),
1 K
dx, = - x, + +dB, and Xo
where K is the number of Gaussian components, fa and o are the means and variances of the Gaussian components, respectively. The solution of the SDE follows
+ + v1 e where {~N(0, 1).
X Xge
Since X and & are both sampled from Gaussian distributions, their linear combination x also forms Gaussian distribution, i.c.,
N(ue (1-e=++1--))
K
k=1
Then, we have
K
1
8t p1, - t 0,2 + 1 - c )2)
Vp(x;) =
V
22T (ofe + +1- exp(-
K
2
i=1
K
D1 - Mcl 1 11
(xx)
VmL m
K
o 1 1 - c-
(z) Mse -1)
pi(att)
ofe- + + e-
We can also calculate the score of æt, i.c.,
1/K Eim pi(at))
v logp(æ;;) = Vp(x:) p(x;))
1/K EK Pa(ee)
We consider MoG consisting of 12 Gaussian distributions, each with 10 dimensions, shown in Fig. (f). The means the 12 Gaussian distributions are uniformly distributed along the cireumference of circle with radius of one in the first and second dimensions, while the remaining dimensions are centered at the origin. Fach component of the mixture has an equal probability and variance of 0.007 across all dimensions.
We evaluate Alg. with unadjust Langevin algorithm (ULA), which leads to RTK-ULA, Alg 2, implementations, and DDPM under the same Number of Function Evaluations (NFE). Specifically, while DDPM models X., across sequence 0.001 T (i.e., [0, 0.00iT, 0.002T. ...., T[,, execute Alg. 1, 2, and 3 at fewer timesteps within X/0.0.27.0.47.000 0tt.0..4..0667.000 0.87.) and we distribute the NFE uniformly to these timesteps for MCMC. The experiments taken single NVIDIA GeForee RTX 4090 GPU. We evaluate the sampling quality using marginal accuracy, i.e.,
timesteps spanning from T in increments of
d (V
Marginal Accuracy = 0.5 x d
where pe(x)) is the empirical marginal distribution of the i-th dimension obtained from the sampled data, 2: (x) is the true marginal distribution of the i-th dimension, and d is the total number of dimensions.
14

---

1.0
(b)
Goord Tun
(c)
Orrand Trst
Marg inal Accuracy
0.01
ULA
HALA,
MALA
0.00
593
Number Function Evaluations
DOPM
MALA ES
MALA
(c)
(f)
@
01300
DOEM
012-
00300
9310
0.30
-2.4
Dinsmnation 0.4 -3.4
0.4 -14
0.4
Demeratio
Figure 1: (a) Mariginal accuracy of the sampled MoG by different algorithms along NFE. (b-f) The histograms along a certain direction of sampled MoG by different algorithms. The plots labeled by "ULA', 'ULD', 'MALA', 'MALA_ES correspond to RTK-ULA, RTK-ULD, RTK-MALA, score- only RTK-MALA, respectively. The histogram is oriented along the second dimension when the first dimension is constrained within (0.75, 1.25).
Fig. 1 (a) shows the marginal accuracies of our RTK sampling algorithms and DDPM along NFE. We observe that all algorithms using RTK converge quickly. Among all RTK algorithms. RTK-MALA achieves the highest marginal accuracy. Score-only RTK-MALA is worse than RTK-MALA since the estimated energy contains errors, yet it is still slightly better than RTK-ULD. Along all RTK algorithms, RTK-ULA demonstrates the lowest performance in terms of marginal accuracy, but it still outperforms DDPM with a large margin especially when NFE is small.
Fig. 1 (b-f) shows the histograms of sampled MoG by DDPM and RTK-based methods. We observe that DDPM cannot reconstruct the local structure of MoG. ULA can roughly reconstruct the MoG structure, but it is still weak in complex regions, specifically around the peaks and valleys. In contrast, RTK-ULD, score-only RTK-MALA, and RTK-MALA can reconstruct more fine-grained structures in complex regions.
Fig. 2 (a-e) shows the clusters sampled by DDPM and RTK-based methods. We observe that DDPM fails to accurately reconstruct the ground truth distribution. In contrast, all methods based on RTK can generate distributions that closely approximate the ground truth. Additionally, RTK-MALA shows superior performance in accurately reconstructing the distribution in regions of low probability.
We perform other experiments on various MoG settings. Figure 3 and 4 shows the experiments spiral-shaped and chessboard-shaped MoG as the ground truth distribution, respectively. these experiments, we also compared Annealed Langevin Dynamics (ALD) [] with our RTK-based method. In these figures, we observe that compared to DDPM and ALD, our RTK-based methods achieve significantly better marginal accuracy when NFE is small. Besides, we find that RTK-based methods have a much better estimation on low pow-bbbbayyyity region. Furthermore, in Figure 5, we evaluated the methods using the Wasserstein Distance metric, which corresponds to Fréchet Inception Distance. Our results indicate that our RTK based methods have a lower Wasserstein Distance compared to DDPM and ALD, especially when NFE is small.
Furthermore, we conducted experiments on the MNIST dataset, as shown in Figure 6. We first trained a score model following the typical sampling methods using the Fréchet Inception Distance (FID) evaluation criterion. Figure 6 (a) shows that compared with DDPM, our RTK-based methods achieve better FID scores than DDPM,
noise schedule and then compared different
15

---

(a)
(C)
13
15
18
-14
-22
-15
-15
-15
prarran1
(d)
(c)
15
1.-
18
10-
33
Figure 2: (a-e) Clusters sampled by DDPM, RTK-ULA, RTK-ULD, score-only RTK-MALA, and RTK-MALA, respectively. (f) Clusters sampled by the ground truth distribution. These 20 clusters represent the projection of the original 10/ data onto the first two dimensions.
3.51
Marginal Accurecy
(b)
(c)
6.3
ALD
ULA
075
511
166
200
A6
Number Function Evaluations
(h)
(d)
(e)
(f)
Figure (a) Ground truth clusters sampled by spiral-shaped MoG distribution. (b-g) Clusters sampled using 205 NFE by DDPM, ALD, ULA, ULD, MALA_ES, and MALA, respectively. (h) Marginal accuracy the sampled MoG by different algorithms along NFE.
particularly when NFE small. Figure 6 (b) shows that our RTK-based methods generate images of higher quality than DDPM when NFE is small.
Overall, these numerical experiments demonstrate benefit of the RTK framework for developing faster algorithms than DDPM in diffusion inference. Besides, experimental results also well support our theory, showing that RTK-MALA achieves faster convergence than RTK-ULA and RTK-ULD, with estimated energy difference via score functions.
16

---

E33
Marginal Marginal Accuracy
(b)
DIPH
ALD
MALA
MALA
Number Function Evalustions
(h)
(d)
(c)
(f)
Figure 4: (a) Ground truth clusters sampled by a chessboard-shapel MoG distribution. (b-g) Clusters sampled using 205 NFE by DDPM, ALD, ULA, ULD, MALA ES, and MALA, respectively. (h) Marginal accuracy of the sampled MoG by different algorithms along NFE.
0.35
Wasserstein Distance
ULA
ALD
636-
ALD
ULA
ULD
MALA,ES
MSLA
622-
MALA
Wasserstein
MALA
0.0
6.0
100
300
Number Function Evaluations
Number Function Evaluations
Figure 5: Wasserstein distance of the sampled MoG by different algorithms along NFE. (a) and (b) are the Wasserstein distance plot for spiral-shaped and chessboard shaped MoG distribution, respectively.
B Inference process with reverse transition kernel framework
Proof of Lemma 3.1. According to Bayes theorem, the following equation should validated for any E Rd and t' > t,
Pe pe(x:) - Pije (x)lar) pe (a')d=''
(10)
To simplify the notation, we suppose the normalizing constant of i.e.,
Ze : / exp((
Besides, the forward OU process, i.c., SDE. 1, has closed transition kernel, i.c..
- c - (t'
(221-(2--100 (1-e-2((-0)) 4/2
(=))(((())= (2T -
exp
(1 2 -1)
Then, we have
(x') = / p
x e --(1'-0) (e
= -epp((((f(())) ( (22--)(())) -4/2
cxp
2 (1 2((
17

---

4
6
7
6
3
/
7
3
LLD
8
S
O
3
4
4
3
/
3
2
G
4
9
8
9
5 (d)
3
(a)
(b)
(c)
Figure 6: (a) FID of the sampled MNIST data by different algorithms along NFE. (b-d) Sampled MNIST data by ULD, score-only RTK-MALA, and DDPM respectively, when NFE 20.
Plugging this equation into Eq. 10, and we have
/ Paje (arke') pe (ae yd''
RIIS of Eq. 10 =
x c (e' ((-
=f (oo(x)l / zi- exp((fe(x)) (2T (1 61-0-211-10 -4/2
exp
2 e 2(1 200
dyda'.
Moreover, when we plug the reverse transition kernel
x - (t' (t) 2
Pay (allx)) x exp
-Jc(2)
2(1 c 2 -1)
into the previous equation and have
x (t(/))-
exp
- -fe(a))
2(1 2017 11)
RHS of Eq. 10
100--00--- -0/1?
-f((x))
do
2(1-e -0)
x - e (6' 11'-0
/ Z (ex((-f(()) (2T -1-112(66 o02((-11)) 4/2 exp
dydz'
(1 e 2(05 -0)
x' x (0'-0)
(2x (1 e --(((=)))) 2//2
- exp
2(1 2(00 1)
m'=e a 0rgl
exp
-ft(y)
2 207 200
dy dæ
f exp
-fi(a)
dæ
2(1 (01--
Pr (x)
LHS of Eq. 10.
Hence, the proof is completed.
Lemma B.1 (Chain rule of TV). Consider four random variables, x, 2,2,8,2 2, whose underlying distributions are denoted Pa; Pz, yr 92. Suppose pn.z and 9z.z denotes the densities of joint distribations of (x, z) and (x, 2), which we write terms of the conditionals and marginals as
Pz. 2) = (x)2) (=()) = (=)u(2/x)) .
Jn.a (x., 2) (2)2())))) qs (z) -u (2) qu (x))
18

---

then we have
TV (pa,z: 0x,=) & min { TV (Pz, ) + Exups [TV (1))
TV (pa. qu) + Exxps [TV
Besides, we have
TV (Pes qu) TV (Po, 9x,z).
Proof. According to the definition of the total variation distance, we have
/ [22, - (2, x) dædæ
TV (Po.21 (x,2)
2 -
1
/ / (2= (x//2) Ps (=) Da (=) qa (z())) (2]|z) dædæ
2
- / p=(z) / (1)) dædz + 1 [p=(z) - g=(x)) / (2)=
- (0)2(())))
-1Eg~p, [TV (Pu)=(11)), (=1=(1))) + TV (p=.qz).
With similar technique, we have
TV (pr.2. (x,=) S TV (Px, (o) + Ex-p, [TV (P=jo(-1x (+1))+ Hence, the first inequality of this Lemma is proved. Then, for the second inequality, we have
TV (Px, (u) = / px((x)) (x(x))/ da
/// / / / (e, z)dz - / 20, z)dz dæ
2 / |pe, 2) - qu (2x dzdæ = TV (pe.. L2,2)
Hence, the proof is completed.
Lemma B.2. For Alg we huve
TV (fKm.P.) S V L2)d+ (VI(()) exp(-
Ex-pie
TV (p (( (13)
k=0
for any K E N4 and 17 E R,.
Proof. For any {0, 1,..., K 1}. let 1) and P(k+1)m, 1),,.n denote the joint distribution of (8(++1m &tn) and (x(*+1)m X which we write in term of the conditionals and marginals as p() (x', x)) P(x+ (n (a'|(x) (x)((x) P p(0+1))) Pū++1)m (2', x) 1ii+ (x' (æ)) (x)) (k P(x+1)n (2²).
Under this condition, we have
TV (pKr, P.) TV (pmm Pk.)) S TV (DKm .m: Pko.
TV P( -13)) + ER TV (Dxm)cx-Dn((1))) (1x()))))))))))))))
where the inequalities follow from Lemma B.1. By using the incquality recursively, we have
K Exppen
TV (p P.) STV (Po. Po
TV (De+t1))nn (12)), P(k 1)mlkn (-1xt)
k=
(11)
TTV (Ptet Piottn)
=VV (Poos Pkn)
Ex-pen
k=O
Term
where Poo denotes the stationary distribution of the forward process. In this analysis, Poo is the standard since the forward SDE. 1, whose negative log density 1-strongly convex and also satisfies LSI with constant 1 due to Lemma E.9.
19

---

For Term 1. we have
TV (Po)
SV KL (pKmllpoo)
S V exp (-2Kn) KL (polleso)
2
SV (1+ [O)] exp(-Kn)
where the first inequality follows from Pinsker's inequality, the second one follows from Lemma E.1, and the last one follows from Lemma E.2. It should be noted that the smoothness of po required in Lemma E.2 is given by [A1].
Plugging this inequality into Eq. 11, we have
TV (pKq: P.) S + 12)d IV)((0)) exp(-KX)
K-1
TV (De++1)akk( (m (-12)
Exmpie
kmm
Hence, the proof is completed.
Corollary B.3. For Alg 1, if we set
2L +
(1+ 12 [V)
71 = log
K = 4T. log
2L
2
and
(1+ L2 VJ)
TV (P1+1))) 1) Pyk
S
c
log
K
4L
22
we have the total variation distance between the underlying distribution of Alg I output and the data distribution pa will satisfy TV (fKm P.) S. De.
Proof. According Lemma B.2, we have
TV P=) Sv
L3)d+ [0)] exp(-Kn)
K-1
TV
(p(+ (112) 1nnlen (x))
A=
Term
for any K E N and 1) E Rt. To achieve the upper bound TV (Ko)))))) S e, we only require
2 log (1 (++
T Kn
(12)
22
For Term 2. For any Rdd the formulation of Phi1116 (-12) is
| e-
1) (xll)) P(K- (x exp
-f(K-k-1)n(0)-
2(1 E --2n)
whose negative log Hessian satisfies
v2 log P Dyglen (a)(*)
2 f(x x-1))))))
22
1- 11 I.
22
1-e-20
Note that the last inequality follows from [A1]. this condition, if require
24
2L
L 2 *
n 2 log
1-
2L
20

---

then we have
e 2g
3e 3-
I V2 log (1 (xf@)) 3
e 1.
2(1 22)
2(1
To simplify the following analysis, we choose 1) to its upper bound, and we know for all & e {0, I...., - 13, the conditional density P is strongly-log concave, and score 3I.-Lipschitz. Besides, combining Eq. 12 and the choice of 17, we require
(1 D [V))
2L +
K = ==T/n 2 log
log
2²
2L
which can be achieved by
(1 L [VS
K = 4L log
2 when we suppose I. 2 without loss of generality. In this condition, if there is a uniform upper bound for all conditional probability approximation, i.e.,
log (1 (
TV (1 P(x+ Dyll (-1zt)
S
K 4L
6
then we can find Term 2 Eq. will be upper bounded by Hence, the proof is completed.
Lemma B. (Chain rule of KL). Consider four random variables, x, x. 2, whose underlying distributions are denoted as .r. qu 9s- Suppose Pa.s and 9z,z denotes the densities of joint distributions of (x, 2) and (xx 2), which we write in terms of the conditionals and marginals as
(2, 2) Pu|= (201=) (=(2)= = (=)x(=(())) (x)
2x. (x, = (2)=((212) (2(2) 9atar (z) (2|2z) Qu (x:)
then we have
KL (ps.:|| =KL (ps (l))) + Egpax
KL (P (-))) 9=)=1))))
=KL (p=||gx) + Exups
KL (p (-1x)) (+)xx=
where the latter equation implies
KL (px [lx] I KL (Pa.=
Proof. According to the formulation of KL divergence, we have
KL (px. (p=,=119z.=) = / Pz.:(a, 2) log
(xr, 2)
qu,= xx d(xx, 2)
/ (2,) 2) log (x(
(a
+ log 2 (=|=(2|(z) ) d(x 2)
Gu (x)
/ (c, 2) log
Par a
dlx, 2) + / (c( / (=)((2/z)) log (
Patz(2|a)) dzdæ
Uu (at KIL (pz(llx) + Exxop
KL. (peto (-1x))) (xx)] 2 KT. (pm (pml)
where the last inequality follows from the fact
KL (P (1
20
With a similar technique, it can be obtained that
KL (pa.> (le,=)
/ Pu,= (xr x) log
P=,=(1; (xx, 2)
d(x; 2)
Qu xx, z)
ff Po.o (cc, x)
Pz (2)
+ log Palz (z(()) (z|2))
log
d(xx)) 2)
4: (z)
Oz1= (x
f Panee (20, z) log (z)z) (z)
d (x, 2) + pz(2)) / (2)=()))z) log Pale (x)=
dzdæ
as (z)
-KT. (p=lla=) Exap, KL (pate( (z) (1)))(11)))))))))111111
Hence, the proof is completed.
21

---

Proof of Lemma 3.2. This Lemma uses nearly the same techniques as those in Lemma B.2, while may have a better smoothness dependency in convergence since the chain rule of KL divergence. Hence, we will omit several steps overlapped in Lemma B.2.
For any & E {0, K 1), let P(k-1)) and Pik+1)m,n denote the joint distribution of (K(++1))) Skn) and (x/ X which we write in term of the conditionals and marginals as P(+1))n8n (2r x:) = P()+1)) (20' (ao (a:) (x)((a) = Pan(((+1)n(rraaa)) p((+1))((2))) P(k+1)a, (x', ax) = pik+ (ao' (ar) Pkn = (0)00)))),,,()3)))) P()++1),(2")
Besides, we consider a reference Markov process { whose initial marginal distribution and transition kernels satisfy
X Po po and P(k+1mmbb (a')a))))))))))))))))))))))))( 10 (a (a'l
Under these conditions, we have
TV (pKn: P.) S TV (pKg. PK.) + TV (p) Pw).
Since } and {x] share the same transition kernel, then we have
TV (.) S TV (po,25) S V KL (Pb (166)
(13)
=V KT
KT. (pKn||p>>) S (11+ 12yd+ [V)( eex((xX)
where the first inequality follows from the chain rule of TV distance, the second inequality follows from Pinsker's inequality, and the last inequality follows from Lemma E.2. Besides, we have
TV (pKn pKM) S V KK (pKm (px) & V
} KKL Dxxw,(K-pollxxxxxxu--
VV2k KL (10 1 + Ex-pxx-n KL (1)) (XX (-1x)
where the first inequality follows from Pinsker's inequality, the second and the third inequalities follow from Lemma B.4. By using this inequality recursively, we have
K Σ Am
TV (pKn, PKn)= S
KL (Boll2o)
+ Exnpre Pan
[L (p (p (1) 1) 1o (-15))
2
K- 1
KL Exmpan
(1)))))
2
km=
(14)
where the equation follows from the definition of process Eq. 13, the proof is completed.
{3 Therefore, combining Eq. 14 with
Corollary B.5. For Alg 1, if we set
2L +
(1+ L2 |
1 ク= log
K = 4L log
2L
²²
and
2²
(1+ + (V
KL (pi+ttm)ken(112) PpK- -1)(( (-1)) <
log
2
we have the total variation distance between the underlying distribution of Alg I output and the data distribution pa will satisfy TV (pKn, p.) < De.
22

---

Proof. According to Lemma 3.2, we have
TV (6Km p.) - V (1 L2)d [O)] exp(-Kn)
Term
(15)
Exupen
KL
(-)))))))))))))))))))))) (112))
km0
Term
To achieve the upper bound Term 1 S e, only require
1
(1 +1+ L2)d
+
VS)(
T Km
log
(16)
2
For Term 2, by choosing
1
2L +
11 =
log
2T
know for all & E {0, I,..., K 1}. the conditional density 1) strongly-log concave, and score 3/--Lipschitz In this condition, we require
== llg (1+ L Ld [O
22
when suppose L 1 without loss of generality. Then, achieve Term 2 e, the sufficient condition to require a uniform upper bound for all conditional probability approximation, i.e.,
2 S
e²
log (1+ V
KL (prK+1m kn (+1z) x a(1(0))
K
AL
2
Hence, the proof is completed.
Remark 1. To achieve the TV error tolerance shown in Corollary B.3, .ie.,
log (1+ 1.2 VVV.
TV (p(4+1)) P(x+ ky (-12t)
4L
2²
it requires the KL divergence error to satisfy
TV (1)) (-(0))
V KL
((u+))n1kr711())1111 11) (-12t)
2
(1 +1+ I.2dd IIV.
log
16L2
2
Compared with the results shown in Corollary B.5, this result requires higher accuracy with an (LL) factor, which is not acceptable sometimes.
Lemma B.6. Suppose Assumption [AI]-[A2] hold, the choice of n keeps the same as that in Corollary B.5, and the second moment of the underlying distribution of &kn Mr. then we have
28, + 16(d + m2) + 24M-.
M <
L
Proof. Considering the second moment of {(++1)n we have
Ep ||
f ((x+1)(())) ||x||2d
=f (fBrn (aon(e) (x ||
(17)
= -f (en(e) ((ttm)n ||=:|| 2
23

---

Then, we focus on the innermost integration. suppose (,()))) as the optimal coupling between Pik+t)o and Pin+1)nlkn, (ly)) Then, we have
/ 1(k+1))1kn |=|| dx Pin-Imm (2ly)) |a:|| dx
- / (o x)) (|ı)) - |x01 d( x)) 1 / (e x)) || =x1 d( x))
(18)
W3 (ilk-)))llpPit++t110 Pik-
Since 1(k+e) strongly log-concave, i...
22
Va log Pogg((sti P( Dyl (x) V²J ( 1 e-e-21
LI,
the distribution Pi++110 ly also satisfies 1/L log-Solf Sog-lobolev inequality due to Lemma E.9. By
Talagrand's inequality, we have
W2 (p1++101kn 1))-1) -
2 L
KL (Be-11+440lle4)1444)))
20
(19)
L
Plugging Eq 18 and Eq 19 into Eq 17, we have
{ (
(20e 2 P(++1))(n((2ll)) ||a|
E ||
da
dy.
(20)
To upper bound the innermost integration, we suppose the optimal coupling between P(K P(K-k- 1)n and ((k+1))lkn (.1)) is To (;.)). Then it has
/ kin (xly) ||=|| dæ - 22 / P(K ((x= ||=||| dæ
$ 7 (x', xx) (122112 (1122122111a)) ||01| d(æ'; x)) s "o(a x)) || =112d(x', xx)
(21)
W3 - - Pin Pik
Since Pik+1)ylkn satisfies LSI with constant 1/L. By Talagrand's inequality and LSI, we have
2 S L
(P Pik P(k-l)n
KL (p(k 1im
P(K++))))))))
4 1
/ /DIK-A-In(())
P(K -
v log
dx
P Pik+1)n/ke (xl
e - 20 2
4 T
dx
c-
< 12 1|21122 + 8 () (2))
< 1/ + 8(d + m²).
where the last inequality follows from the choice of 1 = 1/2 log(2L + 1)/2L and the fact Ep (ixk-l-,,,[[x/// < (d + m3) obtained by Lemma E.7. Plugging this results into Eq. 20, we have
E [|
25 + 16(d + m3) + 24 E ||
L
C Implement RTK inference with MALA
In this section, we consider introducing MALA variant sample from P (z/20). To simplify the notation, we set
g(x) = f(K- + |mo e 1
(22)
2(1 e e-2n)
24

---

and consider i and Zo to be fixed. Besides, we set
p (z| = Pk+ (2/111(2/10) exp(-9(z))
According to Corollary B.5 and Corollary B.3, when we choose
1
2
+
" log
2L
the log density will be L-strongly log-concave and 3L-smooth. approximations,
With the following two
s0(z) ~ (z(z) and (2, R - -(z)-g(( g(z').
(23)
We left the approximation level here and determined when we needed the detailed analysis. we can use the following Algorithm to replace Line 3 of Alg. 1.
In this section, we introduce several notations about three transition kernels presenting the standard, the projected, and the ideally projected implementation of Alg. 2.
Standard implementation of Alg. 2. According to Step 4, the transition distribution satisfies
Qx, =N (z+ - T 96 (zs)), 2T)
(24)
with a density function
(Z,) f2r (z. (Zs sz(z)))) Considering a 1/2-lazy version of the update, we set
(25)
Th (dzz) 8z, (dz') + 2 Qz. (dz').
(26)
Then, with the following Metropolis- Hastingss filter,
ax, (z') min { 1, g(= x²)
exp exp(-re(z') (ppro((2,2))) where ax,(x') = (2)0-=(2--))00 z.),
(27)
the transition kernel for the standard implementation of Alg, 2 will be
(dz=+1) = T2, (12x41) az (Zs+1) + (1- (dz')) 82. (dzs+1).
(28)
Projected implementation of Alg. 2. According to Step 4, the transition distribution satisfies
Qz. NV (z. - T (s())),,
with a density function
7(2, 2.) = 2er (2. (z. - TT. Vsa(z.))),
Considering the projection operation, i.e., Step 5 in Alg 1, if suppose the feasible set
Ω -B0 R) and U2 = B(z,r) n B(0, R)
the transition distribution becomes
Ø'e (A) = f Jmn
(dz')) + / JA-Re. (z,''))) (A).
Hence, a 1/2-lazy version of the transition distribution becomes
tg (dz') = - 62, (dz') + 2 Q2,, (dz')
Then, with the following Metropolis-Hasting filter,
(z') min 1, g(z. (=)
exp (-ro(2', ,1,), where àg, āz,(2') (22--()))))0(22))) 2.);
the transition kernel for the projected implementation of Alg, 2 will be
Tz, (dzx+1) T", (dzo+1)= āz, (#o+1) + (1- / āz (2'2) (cte)) 8x, (dze+1).
25

---

Ideally projected implementation of Alg. 2. In this condition, we know the accurate g(z) - -9(z') and (z(z). In this condition, the ULA step will provide
=N - Vg((z)),
(29)
with density function
1e (Z,12,) = P2r (3g (T Vg(z,)))
Considering the projection operation, i.e., Step 5 in Alg I, the transition distribution becomes
2²,,, S JAMO Q1,2, (dz') f
).z,' 8z. (A).
(30)
A-R2,
Hence, a 1/2-lazy version of the transition distribution becomes
Te (dz') 6z, (dzz) 0',,,(zz)
(31)
Then, with the following Metropolis-Hastings Hastings filter,
g. (2.12²)) exp (- -xp(((1())-g(xx)) (x.)z))
(z') min
(32)
the transition kernel for the accurate projected update will be
(.., = -T,,,, (dzst1) a.,2, (2s+1) + (1 (2')x,2 62, (dz,+1). (33)
Lemma C.1. Suppose we have
2T. +
11 = 2 2L
log
then the target distribution of the Inner MALA, i.e., p= (=(ar)) will be L-strongly log-coneave and 3L-smooth for any given Too-
Proof. Consider the energy function g(z) of pp (ptpp"""(aaaa (x|xo), we have
|| [ao 0- 2(1 E 21)
g(z) fiK f(n)
whose Hessian matrix satisfies
e 2-0 2n
e-2n
c-2n
(1 (1-e-2n) 2n) +L) I> (() + (1-e 2-)
I
(1-E 2n) -L) I.
L
Under these conditions, if we have
1
2L +
c
n < log
e 2n 2L.
2
2L
which means
-2n 2n
2n
2 (2g(z) t
2(1 e-2n)
2(1 - 2-1)
For the analysis convenience, we set
2L +
1 log 2L
that is to say g(x) is L-strongly convex and 3L-smooth.
26

---

C.1 Control the error from the projected transition kernel
Here, consider the marginal distribution of {z,} and {2,) to be the random process when Alg. implemented by the standard and projected version, respectively. The underlying distributions of these processes denoted as 2, M4 and & ja. and we would like upper bound TV (us, (s) for any given Zo-
Rewrite the formulation of Es, we have
2g = ng 1 (zg = 2g) + 23 (zg + Eg)
where 1()) is the indicator function. In this condition, for any set A, we have
1 (zs E A) =1 (2s E A) (2s žs) + (zs A) (zs + Es)
(2s E A) - 1 (ăs E AA 1 (zs * 2s) + 1 (zs A) 1 (zs # 2s),
which means
-1 (ās E A) 1 (zs + Es) S (zs A) 1(2s E A) S 1 (zs E A) (zs # ās)
Therefore, the total variation distance between us and jos can upper bounded with
TV (us, I sup (Ms(AA) (s((A)) s (zs + ās). ACRd
Hence, to require TV (us, (ss) I e/4 a sufficient condition is to consider Prizs * žs]. The next step is show that, in Alg. 2, the projected version generates the same outputs that of the standard version with probability at least
e/4. It suffices to show that with probability at least 1 e/4, projected MALA will accept all iterates. In this condition, let {z1, -2,-..p zg} be the iterates generated by the standard MALA (without the projection step), our goal is to prove that with probability least e/4 all z, stay inside the region B(0,, R) and | - -ll S r for all s S S. That means we need to prove the following two facts
1. With probability at least 1 c/8, all iterates stay inside the region ((0, R).
2. With probability at least - e/8. ||x, x,-1ll S for all < S.
Lemma C.2. Let us and jas be distributions the the outputs of standard and projected implementation of Alg. 2. For any (0, 1), we set
d
165
8S
R
8
VT. log
S r (V2++1) VTd 2/ log
12
T
where 2. is denoted as the global optimum of the energy function, i.e., g. defined in Eq. 22. Suppose
P([zzol 2 R/2) S c/4 and set
d
16d
d
5 min
(3LR+ [|Vg(0)| + Escore) 32'
T2
(3LR
[Vg(O]] + Escore)
then we have
TV (us: 4
Proof. We borrow the proof techniques provided in Lemma 6.1 of [41] to control the TVD gap between the standard and the projected implementation of Alg, 2.
27

---

Particles stay inside (00, R). We first consider the expectation of || /| when z, is given, and have
[3 =ʃ ||=111² Tz, (dzz)
E 1
11
11
Tz. (d2') az (2)) + (1- aaz (8)T2, (dz) 82, (dz')
||2 1| / (11='12² -11z,11) azz (2')T2 (dz')
(34)
| 1| + / (11=1)1- - ||2.1²) -|1==1
(z),2') 1
8z, (dz') + 1
Qz (dz')
| 2 + 2 / (11=') - -112011)) min 10)= (zzol2)) exp (-ro 26))) dz'
| 2 + 2 / ||=111 q(<2 1z. )dz',
where the second equation follows from Eq. 28, the forth equation follows from Eq. 26 and the fifth equation follows from Eq. 27 and Eq. 25. Note that q(2' (z,) is Gaussian-type distribution whose mean and variance are 2g T sy (z,) and 27 respectively. It means
/ 1='112 q(='lz))dz' = =||z, -
(00.=,) (0.))1 + 2rd.
(35)
Suppose z. is the global optimum of the function due to Lemma C.I, we have
||z - T- (0.0))2)) = ||2.11 2r 2 s0(2.) + + ||s0 12
=||z,1² 2 -2 2, Vg(2.) + 2T 2 (sa(zs) Vg((z)) + 72 (|00(zz)) Vg(z.) Vo(z.)]l
|z 2 [V)
L
|z.1122 - 2r
+72 |Z [l00(z)) - Vg(2s)]1
2
2L
+ 2r ||Vg(z,))
122 27 ((0) (g(2,))
= (1 - LT -I1-L +7 || 12, + (VV L + (1 + (122 2 + 27
[
(1 (1 36L 3 ||2.1 + 2 (V)] /L 47
O)]l + (1 2r )
(36)
where the first inequality follows from the combination of T.-strong convexity of و and Lemma E.3 the second inequality follows from the 3L-smoothness of The strong convexity and the smoothness of g follow from Lemma C.I.
Combining Eq. 34, Eq. 35 and Eq. 36, we have
E
2
Es
S
Lr
+
1 361.
x2)
||2 12
2
(1 + 27 2 20ome
+
T
+ 2T²)
||Vg((0))
+ Td.
2T.
2
By requiring éscore ST 1./12 72T.)
< 1, we have
E [|zzzz2 12
1 <(1-
Lr
|| 2 -- - (1V (2 d).. ())
25
Suppose a radio R satisfies
00 1 d
R > 8
(37)
T,"
28

---

Then. if 2
2 R/22 4V d/L, it has
[vg(0)|
4
8 V
8 (2
|2,11²
2 16.
L
L
LT
T
|V + (2 d)r
8
L
[/s 1 (1 1, -|,2,1
E
Zat 112
To prove |z,|| < R for all 8 I 5, we only need to consider satisfying || > dv ( /2/L2
d/L, otherwise ||=||| < R/2 I R naturally holds. Then, by the concavity
of the function log()) ) for any ||= 2 R/2, we have
LT, log 000[1=11' 13) s log([1=.113) (38)
LT
E [ogg( 22,- |1-) 2.]
log E [|2.+111/ log(1
4
Consider the random variable
2. n so(zz) + V2 where & I~,(
obtained by the transition kernel Eq. 24, Note that ||E|| is the square root of x(d) random variable, which is subgaussian and satisfies
P |ill 2 vd+ v2l <e-
for any & 2 0. Under these conditions, requiring
S (3LR+ + G + Escore) 2, d where G [V
(39)
we have
[ - | 2 3v + 2 < TP
|2,1| - || 2 3v
(40)
S P [z,)]l
|| + v 2F ||l|| 2 3v + 2V
< /2F 2 + 2/ se-
In Eq. 40, the first inequality follows from the definition of transition kernel Tz, shown in Eq. 28 and the second inequality follows from
|2.1l | S T [[s0(
2r ||E|]
According to the fact
- [|<50(z))11 <T (z(2)) + Teccore ST. (z))))) Vg(O)] + [|vg())] + Escore)
(41)
(3L || [Vv(()]] (score) & VTd
where the second inequality follows from the smoothness of g, and the last inequality follows from Eq. 39 and ||=||| < R, we have
3v - (s0 > 22d + 22/1,
which implies the last inequality of Eq. 40 for all t 2 0. Furthermore, suppose || 2 R/2, it follows that
log(1) (og((1=++1113)) log(11z [| 11?) = log =1, < 1z.++11//|z, -15 2/|
|| - 2||2z
Therefore, we have log( [| = )|3) log(1 2, (2) is also a sub-Gaussian random variable and satisfies
TP [og[[lz++1l]] - logoloo//111 | 13 2 6R 6R- + < exp(-1)).
(42)
We consider any subsequence among {zx) )= with all iterates, except the first one, staying outside the region (0, R/2). Denote such subsequence by {y=]s" where ||yo/| s R/2 and S' S. Then, we know y, and y++1 satisfy Eq. 38 and Eq. 42 for all 1. Under these conditions, by requiring
29

---

|zol| I R/2 with a probability at least - c/16, we only need to prove all points in {y. will stay inside the region ( R) with probability least 1 e/16.
Then, set &g to be the event that
& = (1y S R2AS $}}
which satisfies - C Eg. Besides, suppose the filtration F; = (yo, YI, yi,...., ,y). the sequence
(1(E,-1) (log(ly>+1 + LST LST/4)) 11.......
is a super-martigale, and the martingale difference has subgaussian tail, i.c. for any 2 0,
P 1og(lly++1113 (13) + Lis 1)T log((lys113)
LIs 4
2 7R +R
4
s log(llys+11]) 112) + [(s + 1)T log( (og((ly=11?)
Lst
VTd + 4R WF+ Lt
6π
= log( 2 11?) log( >> (1) 2 6R "R-'VVVd++ 4R 1 tVT 1 exp(-(t)
where the first inequality is established when
Lr
Vrd
16d 2
+
T
and
d 1.
(43)
4 R
Under these conditions, suppose
Td
4l
ul
3 2'
u
1=
4 rd
it implies
R2u2
82 2 64rd
which follows from the fact (a b)2 2 a² b² /3 for all a, R. Then, for any 0, have
P (og((1)++1119 1+)++ L(s + 1)T log(ll y, 113)
LSt
exp (-
64rd +1) s 3 exp
R2u²
R?u²
64rd
which implies that the martingale difference is subgaussian. Then by Theorem in [30], for any s, have
LSt
74 R
log([ly><11) 112)
< log(Ilyoll")
/sTdlog(1/e)
with the probability at least é' conditioned on E--1. Taking the union bound over all S' (S' < S) and set = 16e'5", we have with probability at least c/16, for all ., holds
1, .....
log(lly Lolog( R/2) + (1650/(165/o) LSt
R
74
d
<2log( R/2)
RLL
By requiring
d
165
742 d Alog(116) (165/e)
R 2 63
V log
2log
(44)
R
we have log(lly..11 112) < log l)g( which is equivalent to |ly/ll < R. Combining with the fact that with probability at least </ e/16 the initial point yo stays inside B(0, R/2), we can conclude that with probability least 1 e/8 all iterates stay inside the region (0 R).
30

---

The difference between 2 and 2, is smaller than In this paragraph, we aim to prove 2x41 2, S r for all s I S. Similar the previous techniques, we consider
2 = 2, so (z.) + 2T
where E~N(0,11.
According to the transition kernel Eq. 28, it has
IP [||za+1 2, 2 r] IP || 2oll
2 S
[]]68((2)) + /2 2
(45)
IP
||l||
2 r- [=
S
P
|El
2
r
v rd
V2T
V2T
where the second inequality follows from the triangle inequality, and the last inequality follows from Eq. 41 when the choice of satisfies Eq. 39. Under these conditions, by choosing
-- VTd
(V2+ V Tog((S//)
Vd + V2 Vlg((S//))
2F
Eq. 45 becomes
Vrlll
P Pl|z.41 2 - z 2
|El
I P
|Kl 2 vd+ v2. Vlog(8S/c) $ 88
2T
which means
P Pl|zst1 z sr) 2112-- 85
Taking union bound over all iterates, know all particles satisfy the local condition, i.c., /z,+1 2 S r with the probability at least c/8. Hence, the proof is completed.
C.2
Control the error from the approximation of score and energy
Under Assumption Lemma C.3.
[AI]-[A2], we set
2L +1
17
log
and G= [g]l)
2L
For any E (0, we set
(0
d
16S
88
R R2 max
+
63
log
r 3 V rdlog
L
L
Suppose has
8
3cscore
85
7
7(3LR. + G.)
1 10'
rdlog
and Cenergy S
16
we have
8 55ennrgy)
TT, (2())) S (1+0 5 + 56 F. (22)).
for any set A B(0, R) and point z B(0, R).
Proof. Note that the Markov process defined by Ta (.) and T.,(.) are 1/2-lazy. We prove the lemma by considering two cases: A and A.
When $ A, we have
(x(A) = / Cz (z(2') = 2/1 äz (=(2')
/ az(z') = 1
a=(2' (=')))((')) (=)
Aree
31

---

Similarly, we have
2 (z. |z)dz'.
1
(A)
2 Ann.
In this condition, we consider
= 1 (z,2(=') 12)22' + /
(A) (A),
Ina. ((===)(((((())))
Jrn
SAr ( (2)) 2)dz=
0=(2' (=(22)((22') 10000(10/00 1z)dz'
Anne
which means
[A) - (A)
Jana, (=,=(=)) (0(2'|2) (2'1=)))
(A)
Sanae (0 11 (2' 1z)dz'
Term + Lanaa (āz(z') U ((=11z)d>' SamDs (2.
(46)
Term
First, we try to control Term 1, which can be achieved by investigating 0(= (='{() as follows.
7(21 22)
|| (z=))
4T + || (z Vg(()))1
=0(2))1
exp
7. (=' z)
4T
In this condition, we have
<(>1|z) exp (4T)- (-11z' - =21|² -27 (z' (z'-2) =)) s0(2) - (1))0(2))1
(='1z)
+ || - =|| + 27 (z' =z)² Vg(z)= + [((())1²))
(47)
exp 2 (x' - 2) (- + Vg(z))
_ (- [|s0(2)]1 \V(())1)))
means
In ((='|z)
/ (2'
1
T)((-sa)) (-so(z) + Vg(=)) + 7 - [=)(1 [3)(3))
(2)
1| z|| [[ss(()) - Vg(2)] + T
[[]s0(2) + Vg(2)]|
- [|sa())\V((z)))
2
4
1| 2|| [|50(z) - Vg(2)]] +
+ T
||Vg(z)] [[)(()) - V9(2)]
2
4
2
P'sorre
T
T3LR + G) Cscure
+
2
4
2
where the last inequality follows from the fact z' E B(z, n B(0, R))(2)) E B(0, R) and
|Vg(()]| [V]]=) (g(() + (g( < 3L ||||| + +G < 3LR + G.
According to the definition of R and shown in Lemma C.2, we choose
8S r = 3 VF dlog 2 (V2+1) 1) V + 2/ log
/
85
Under this condition, we require
8 = 3cccore
V rd log
8S T
T(3LR + G) Cscore
1
(48)
16
2
4
2
32
then we have
8
((=1|z) 7. (z'1z)
8
((z112)
In
< In
I In
1+
1
<
1 +
8
8
(x'1z)
8
32

---

and
((211z)
7(='1z)
8
- min
1 S Term Σ
max
-
(49)
8 * A'AAn (z)1z)
*'EAnRs (z'(z)
8
with the definition of Term shown in Eq. 46.
Then, we try to control Term 2 of Eq. 46 and have
SAna, (0z(z') - = (
Lana, (āz(z') 0, (2 ((1))
Lana, (=,2(=')(((== (11)22)((21 12)22
Jana. (z.)(z')0 1á. (z") z)dz'
Sana. - (z') 10(2'))))) (2)==
Lamoe (z') (z)
(50)
According to Eq. 49, it has
1 6 S min ((=12z) Sana, (2)) S Jana, ā. (z'
((='|z)
I
max E'Ann (x'1zz)
S 11 + 8' (51)
8 E'Enn (z'1z)
then we can upper and lower bounding Term 2 by investigating ã.
as follows
(=(=2))
ā., (=,) = min
1, 1-exp(((((2) - g(=)))
7-
āg (=(2') = min 1, 1- ((z|2')
In this condition, for any 0 < 5 < 1, we first consider two cases. When
(=(2²²)
and á=(2') = exp (-ro(22,, 7(2|2')
1
((2)))
1
(2(1z)
((212)
we have
exp (apr-o (((2222))) a(=|=*)
=)
az (z(z²)
exp (-ro(2',2))
0(z|z²)
11
(52)
exp (-(9(z') g(=)))
(x)
(z')
7(2112) 2)
(=
Term 2.1
Besides, when
a. x = exp (-((2')(2)) - -(())) (2122)
((x12')
<1 and (z(2²) = s exp (-ro(z',2)) 2))
(2'1z)
(('' (z)
we have
(=(2)
exp (-ro(z'; z))
g(=|=²)
x(
1 < au dx,2(2' (x')
(53)
exp (-(((z)) - (())))
(z(=²)
exp (-(g(z)) - g (z)))
(z|=²)
(=
Term 2.1
Then, start to consider finding the range of In (Term 2.1) follows
To (= (2)
In ((212')
In (Term 2.1)| = (-ro (z', + (g(2') - g(z))) + In
7<'12) (=(22))
(54)
Stenergy + In (z'(22 ((21|2) +
((2|2²)
g(2 (2))
(2|2")
Eenergy
16 +
(2(2²)
where the last inequality follows from Eq. 48. Besides, similar to Eq. 47, we have
7. (z(x²' exp (47)- 1 (- 1| - 2111² 2r (z
((z|2')
- 7² (|s0(2')11
+||- - z'11² + 2T (z - Vg((z') ([Vo(=)11))
33

---

which means
In ((z|2')
(2 (0-===
1
(=s0(=') + Vo(z()) + T (- |=0(1 ||V0(=))1+)
g- (=12²))
2
|| 211 ||50(z') Vo(>')| + T ||s0(2') + Vg(2')| [|=0(2)) - Vg(2'|I
2
1
||= 2'11 ||so(z') Vg(2')|1 (|so(2')-Vo(z)))) + 7 ||V((')|1 -|000=/)) - -Vg(z))
Pecorr
Te score
T(3LR G) Excore
+
2
4
2
where the last inequality follows from the fact z' E BB(z,)) ((0, R)/{2} and
[Vg(z'Il VV((²) Vg(O) Vo(0)]l - 3L | + G - 3LR + G.
Combining this result with Eq. 48, we have
6
3acore
85
T ceooe
T(3LR G) Escore
rdlog
(2|2')
16
16
2
Plugging this result into Eq. 54, it has
In (Term 2.1)| < 8
+ Cenergy-
By requiring cenergy S 0.1, we have
5 1+
2eenergy
S In (Term 2.1) s
+ 2eenergy
4
8 2eenergy S Term 2.1 S 1+ + 2eenergy
Combining this result with Eq. 52 and Eq. 53, we have
(2('') (z')
4 Zeenerg I
S 1 + 4
+ 2e Zenergy:
which implies
LanA, - - (z)) (á,()))aa,xx3 (2))))((2l))))))) ((212))
min āz (x')
8 2Eenergy
- 11
Jana, a., (z)) 2)(=)
E' a. (z')
(55)
Sana, (az(z') - á,, (()1)=)d>' Sana, (z')())) )z
0= (2')
5
max
<
22energy
A' ū, (2')
Plugging Eq. 55 and Eq. 51 into Eq. 50, we have
8 56energy
(
8
24 energy (1+
S Term 2
(8
2(eergy
(1+
8)
8
5
5energg
3 In this condition, combining Eq. 56, Eq. with Eq. 46, we have
4
8
3
2
(56)
+ 5cenergy
Ta(A) -r.A)-Tra(A4 (A)
< 6 5cenergy
2
(A)
2
(57)
(1-
8 + 5Cenergy
(r, < sT((A)= (1 (1
8 + 5cenergy
)
Tr)((A).
2
2
Hence, we complete the proof for 4 A.
34

---

When E A, suppose there exist some r' satisfying
22 B(z,r') A.
We can split A into A- S2-2 and S2- Note that by our results in the first case, we have
1
8 5Cenergy
(A 22-2) - TA 02-2 -
+ 5eenergy
(A-
2
2
Then for the set O2 we have
1 -1-Tx(92 (122) - -11- T1, (
T0(')) (122)
(12g)
T9,)
Te.= (1 - -(-) T2( - (1)
TS2 -12) Ta (2 (22- (22)
T22 - 22'2
(S22)
T (2-2
(522
+ 56energy 2 = 8 5eeuergy
where the last inequality follows from Eq. 57 and the property of 1/2 lazy, i.e.,
(9- S and (92)) 1
In this condition, we have
(1 8 8 56energy) T (2²) (2()) S (1 + 56energy) (2,)) Hence, we complete the proof for E A.
Corollary C.4. Under the same conditions as shown in Lemma C.3, if we require Eenergy S 8/5,
then we have
(1 (1-28) 28). (A) < (A( s (1+ 28) (A), for any A C B(0, R) and point B(0, R).
C.3
Control the error from Inner MALA to its stationary
In this section, denote the ideally projected implementation of Alg. 2 whose Markov process, transition kernel, and particles' underlying distributions are denoted as {2,.s)s Eq. 33, and j.., respectively. According [41], know the stationary distribution of the time-reversible process { is
e-
Sq e (==9(()) dz
Ω
A. (dz) =
(58)
otherwise.
Here, we denote Ω = B(0, It) and
Ωt B(0, (())r).
In the following analysis, we default
2L +1
1 log 2L
Under this condition, the smoothness of is 3L. and the strong convexity constant T..
we aim to build the connection between the underlying distribution of the output particles obtained by projected Alg 2, i.c., As, and the stationary distribution j., though the process {2., ) Since the ideally projected implementation of Alg. 2 is similar standard MALA except for the projection. we prove its convergence through its conductance properties, which can be deduced by the Cheeger isoperimetric inequality of jo..
Under these conditions, we organize this subsection in the following three steps:
1. Find the Cheeger isoperimetric inequality of j...
2. Find the conductance properties of T..
3. Build the connection between üs and ja, through the process {ž.,e
35

---

C.3.1 The Cheeger isoperimetric inequality of p.
Definition 1 (Definition 2.5.9 in [12]). A probability measure defined on Polish space (X, dis) satisfies a Cheeger isoperimetric inequality with constant p 0 for all Borel set X, it has
p(AA) - p(A)
1 _u(A))(A9)
lim inf
P
Lemma C.5 (Theorem 2.5.14 in [12]). Let p E P1(2) and let Ch > O. The following are equivalent.
1. P satisfies Cheeger isoperimetric inequality with constant Ch.
2. For all Lipschitz f: - I. holds that
By If F. 2p- Ey IV
(59)
Remark 2. For a general non-log-concare distribution, light bound on the Cheeger constant can hardly be provided. However, considering the Cheeger isoperimetric inequality stronger than the Poincaré inequality, [6] lower bound the Cheeger constant p with (2(d-/2cp) where is the Poincaré constant of pt. The lower bound of cp can be generally obtained by the Bakry-Emery criterion and achieve exp(-O(d)). While for target distributions with better properties, p can usually be much better. When the larget distribution is a mixture of strongly log-concave distributions, the lower bound of p can achieve 1/poly(e) (d) by [20]. For log-concave distributions, [23] proved that the covariance matrix of the distribution jus.. When the target P (Q(I/(T(222)))/) where
distribution is m-strongly log log-concave, based on [16], p can even achieve L) In the following. we will prove that the Cheeger constant can be independent of zo-
Lemma C.6. Suppose μ., and J., are defined as Eq. 22 and Eq. 58, respectively, where R in pā, is chosen as that in Lemma C.2. For any E E (0, 1), we have
1 Sa (..
Jad M4 (dzz 1
2
Proof. Suppose μa x exp(-9) and n. are the original and truncated target distributions of the inner loops. Following from Lemma C.13, has
TV (Me, S
when j., is deduced by the R shown in Lemma C.2. Under these conditions, supposing Ω B(O, R). then we have
/ |m. (dz) ft. (dz)]
/ [1.(d)) (d((d))) {
TV (p., p))
JRI (a(dz)
1 JR exp (-g(z')) dz
exp
(-g(z))
cxp (-g(z))
exp g(()))
dz + Jd SE exp (-9(z')) dz dz.
Jn exp ( (-g(2²)) dz'
(60)
Suppose
and Zn / exx((gg(2) dz,
Z exp (x)()g(=)) dz
Rd then the first term RHS of Eq. 60 satisfies
exp (-)))((z)
exp (xp(-g(2)
dz
Je exp (-g(z') dz
exp exp
(=(2()) dz
1 Jg. exp (-g(2"))) dz 1/6 eexp(gg(2'))
Zn
dz' dz'
Jo exp (-g(2")) dz
and the second term satisfies
exp (-g(2)) dz
Ses exp (-((2'))) ) dz' Sn exp (-g(2')) dz'
Zo 7
Ja-n J exp (-9(2)) x2)) dz
Sg exp (-g(z')) dz'
Combining all these things, we have
Zn
- 2
1
2n
2
$
where we suppose 5 without loss of generality. Hence, the proof is completed.
36

---

Lemma C.7. Suppose p.,, ft,, and are under the same settings as those in Lemma C.6, the variance of H. can be upper bounded by 2d L.
Proof. According the fact that pha is L-strongly log-concave distribution defined on Rd with the mean U. which satisfies
d ((z) ||= -mlll d= S T.
Rd
following from Lemma E.8. Suppose
Ω ( R), Z
exp(- cxp(-g(z))dz,
Zo exp(-g(z))dz
RM
where R shown in Lemma C.2, then the variance bound can be reformulated as exp(=x((2)
J/
exp(-g(<) ((())
d L
I| Uml 2 dz
|| Umal 1ml22
2
Z
Rd
which implies
exp( g((1))
d 2d
|| Um 11 dz 5
(61)
Zn
Zn
L
L
Q2
Note that the last inequality follows from Lemma C.6. Besides, suppose the mean of ju, is um then we have
exp(
-(())
-|z--mml1
( [ex((=g(z))
1|| Un Um -um 1m dz
Zn
7n
exp(- ([(())))
expl-g(z))
- -|1--mml] dz + +2.
(2- - Um Um Umm) dz
Zn
Un
52
(62)
exp(
-=(2))
|10m - - dz
Zn
exp(- exp(-g(z))
exp(-9(z))
||z - vm 1-ml-mll' dz
||0m
2, 1
Zn
Zn
Combining Eq. 61 and Eq. 62, the variance of jı, satisfies
exp(-g(z))
|| vmll 22 <
Zn
T.
Hence, the proof is completed.
Corollary C.8. For each truncated target distribution defined as Eq. 58, their Cheeger constant can be lower bounded by p L((L/dd)
Proof. It can be easily found that fr, is log- concave distribution, which means their Cheeger constant can be upper bounded by & = 2(1 ((()(((((E)) 1/2), where Σ is the covariance matrix of the distribution n... Under these conditions, we have
/
exp(-g(z))
2d T.
Tr (Σ)=
||2 -12-0 dz <
Zo
where the last inequality follows from Lemma C.7. Hence, p ((V/L/d) and the proof is completed.
C.3.2 The conductance properties of T.
We prove the conductance properties of T..z with the following lemma.
Lemma C.9 (Lemma 13 in [22]). Let Tu, be be time-reversible Markov chain Ω with stationary distribution P... Fix any have TV TT.z. Ta,z²) S 0.99, then the conductance of satisfies @ 2 CpA some absolute constant C, where p is the Cheeger constant of p..
0, suppose for any 2, E with || - 2'll < we
37

---

In order to apply Lemma C.9, we have known the Cheeger constant of fa, is We only need to verify the corresponding condition, ie., proving that as long as || - x'11 S A, we have TV (Tr,2, TT,x')) - 0.99 for some A. Recalling Eq. 33, have
(dz) =T,, (dz) a. (z) (1
a á= (3)T -2(())
12
1 (d22) + 2'2z (dx)
(2) + 1- | (,,x()) ( )=(())) + / =dxx)()))
(dz)
]] 62(d2)
1 (=((d)) + 1
(2) + (1 1
1 (0,=(())) xdz)
0 (1z)
2 = -
6z (d2)
1 1
ā d,,z(()
V6 (dz)
(d (',2(d)) ax)=
2
1
/ (3.,()))
+ (dž) x 1 [ 2z),
2 2..
(63)
where the second inequality follows from Eq. 31 and the last inequality follows from Eq. 30. Then the rest will be proving the upper bound TV (Tr..: ) and we state another two useful lemmas as follows.
Lemma C.10 (Lemma B.6 in [41]). For any two points z' E Rd. it holds that
TV (z.
(1 + 3LT) (1+ | 2'1l
V2T
Proof. This lemma can be easily obtained by plugging the smoothness of g. i.c. 3L, into Lemma B.6 in [41].
Corollary C.11 (Variant of Lemma 6.5 in [41]). Under Assumption Aessuptiin/A///AAA [AIH-A2], we set
2L +
17 = log 2L
and G ==\Vg((0)]]
If we set
85
16 (3LR + + (ccrre) and r= v rd rdllog log
there exist absolute constants co, such that 6 2 COPVT where is the Cheeger constant of the distribution Pt..
Proof. By the definition of total variation distance, there exists a set A S Q satisfying
TV (T.22()TT..))) = -..=
Due to the closed form of J. shown in Eq. 63, we have
(A) 1 - 2 ienn
a (d) + (2) 1 E Pz) .2.
BEA
Under this condition, we have
- (A) < max
(1-1) à_, ( (d
2 Jaz
$
Term 1
1
+
(2) 1 E Rz) Q. (d2) (2))( 1 1 E Ω..1 2, (dž)
2
ZEA
Term 2
38

---

Upper bound Term 1. We first consider to lower bound ā..,(2) in the following, According to Eq. 32, we have
-g(2) +=-2+7V9(E) =()))+ + 1 2 ++
(,) exp
4T
which means
4 4 4ln (2) T. (
2 (g(2) g (Vg(z), 2 =2)
Term 1.2
+2 (g( ( (Vg(E), 2 -))
Since Term 1.2 and Term 1.3 are grouped to more easily apply the strong convexity and smoothness of (Lemma C.I), ; it has
Term 1.2 2 -3L 2| - 2| and Term 1.3 1 - 21 2 0.
Besides, by requiring 7 1 1/3L, we have
Term 1.1 (Vg(2) ()) Vg( +
2 T. [g()) - V)(²) [Vo3)
3LT || ||| (2]]Vr(²) 31 2 31. ( - 6T. -11/2
Therefore,
4 In (3) 2- 3 |)(2) - 96 1 = | 96 r. Vg(2) v2 5 $
2 - --21L7² ( 36LT |E]1
and
l 2 -6 [ V - 777 |1&11 > -6L (3LR+ (\)))) -
where the last inequality follows from
[V((2)] < [[Vg($) + 3LR [)|-
Under these conditions, we have
exp (-6LT" | min / exp (-9LT||E113) (
Term 1 <1
(-6172 (3LR (0 (E-.N(o.)) /exp (-9LT
=1 exp
(-6L7² (3LL7 ( )) exp (-18LTd),
<1 0.4 exp
(64)
where the last inequality follows from the Markov inequality shown in the following
Bg=A((..) [exp (-9Ir]|<]]?) 2 exp (-18Ird) P Pe-A((..) [exp (-9Tr||ell) 2 exp
exx (-18LTd) - Pe-NN(..) [[]s]] < 2d] 2 exp (-18LTd) (1 -
Then, by choosing
T <
(65)
16VL. (3LR+ | (V)())
it has 6L.2 (3LR + +[V < 1/40. Besides by choosing
1
1
(66)
LR
40 18L (va +
In
10.
40 18L d'
39

---

where the last inequality follows from the range of R shown in Lemma C.2, it has 18Ld7 $ 1//40. Under these conditions, considering Eq. 64, have
/
Term 1 s 1 - 0.5
min EEN,EEn Sg مد (3.,( < 0.4 e
(67)
Then, combining the step size choices of Eq. 65, Eq. 66, and Lemma C.2, since the requirement
T T 16VL (3LR [V)()))I))
T 2 and
(3LR+ Vg Eacore )
can be achieved by the range of can be determined.
T 1 (3LR + [V]()| + cscore) -
(68)
Upper bound Term 2. In This part, we use similar techniques as those shown in Lemma 6.5 of [41]. According to the triangle inequality, we have
/
(1 (1-a. (.)),(())) ((()))(((())1)))))) (1(2))1 22)d / (1 (1- (3)
2 Term 2 <
2x dē
BEA
AEA
(9(2|2)1 2 Ω21 ((1121)1 (2
SEA
(1-
min sE0,,ERs An
u., (2) (dz)
((()))]1(2E 22) ((112))1 [2 d
SEA
Term 2.1
(69)
Then, upper bound Term 2.1 as follows
Term 2.1
<
/ SEA
[ E (2r) (ā(212) - (((121)) +
[1 E 2z] - 1
E Pzrl)) 0(2)2)
SEA
STV (0.=()))).z)))) max
((212)d2
2(
SEA
SEDL--R.
STV Q.. max
/SERi-n ((212)d2
((E1=')d
BER
According to the definition, (.) is Gaussian distribution with mean - - [V(()) 2) and covariance matrix 2TI, thus we have
JE n
1 (r [V-r\V=(=)1))> /-]
(((12)dē < P x
2
S ((1l2'd2 < P PaNx?
(r [VV](=)]] 1|2 1-11--z11 z'11) /T
Then, we start to lower bound
T [[](2)] || z'11-
Then, we require
d
| 2'1l 0.1r and
(70)
35 (3LR + G)
where the latter condition can be easily covered by the choice in Eq. 68 when d 2 without loss of generality. Under this condition, have
d
0.17vd
T S (0.17)2
+
VT
(71)
BLR+GPP
3LR+C
40

---

Since we have
[ = [V))=) Vo(0) + Vo(0))| s 3Z. |=| + 3LR+ G.
by the smoothness, it has
0.17vd
VF -
~][Vo(2)] 5..17V
(72)
[V(())l
Plugging Eq. 72 and Eq. 71 into Eq. 70, have
[=)]| - || 211 2 0.9r - 0.17v 2 v6.4rd
where the last inequality follows from the choice of shown in Lemma C.3, i.e.,
85 r= 3 V rdllog
2 3 Vrd.
Under these conditions, we have
max (SER-- [(Elz)dē,
q((1z')d S Parxa (||z) 2 3.2d) S 0.1. ZER--RD
Then combine the above results and apply Lemma C.10, assume T - 1/(3L), we have
Term 2.1 S 0.1 + TV (Q.x))) s 0.1+ v2/T || z'11
Plugging the above into Eq. 69, we have
1
2
Term 2 < 1 min
(n.
+ - 0.1 + V - || - z'1l
R2
< <(1 - 0.8 e 1/200
+ 0.05 + (2T) - 1/2
|| - 2'11.
where the second inequality follows from Eq. 67.
After upper bounding Term 1 and Term 2, we have
TV (3,
$1 0.4 1/20 + (1 0.8 e --1/20 0.05 + (2r) ||| z'1l
<0.91 + (27)-1/2 || =|=- z'11 S 0.99
where the last inequality can be established by requiring || - 2'11 S v 2T. Combining Lemma C.9, the conductance of jt. satisfies
Co PV2T.
Hence, the proof is completed.
The connection between jıs and f... With the conductance of truncated target distribution, able to find the convergence of the projected implementation of Alg. 2. Besides, the gap between the truncated target jt. and the true target μ., can be upper bounded by controlling R while such an R will be dominated by the range of R shown in Lemma C.2. In this section, we will omit several details since many of them have been proven in [41].
Lemma C.12 (Lemma 6.4 in [41]). Let ūs be distributions of the outputs of the projected implementation of Alg. 2. Under Assumption [AI]-A2], if the transition kernel Tz(-) is 8-close to T. with å < min {1- - 22/2,, & 6/16) (6 denotes the conductance of j.a), then for any X-warm start initial distribution with respect pu, holds that
TV (is, R.) S A (2-32/8) -165/6.
Lemma C.13 (Lemma 6.6 in [41]). For any E (0,1), set R to make it satisfy
n (B(0,, R)) 2 12"
and T. be the truncated target distribution of pa. Then the total variation distance between μ. and t. can be upper bounded by TV (Me,, pa) S e/4.
41

---

C.4
Main Theorems of InnerMALA implementation
Lemma C.14. Under Assumption [AI]-[A], we can upper bound G Vg(()]] as
[V) - L 2 + +m)) + 3L |
Furthermore, we can reformulate R as
16S
R= 63 v (d m² |00 log
make satisfy the requirement shown in Lemma C.3. Then, the range of inner step sizes, i.e., T, will satisfy
TS Cr (12 (d + m2 | loog
168
where the absolute constant C 2 3 .
Proof. To make the bound more explicit, we control R and G in our previous analysis. For =
[[)(( according to Eq. 22, have
Vg(z)= = Vs(K- + 222 - "00
22
which means
|[ s V e a00
e- 2n
2L
V 00) + V 2T. +1
(2L+
|200|| < V K (0) (2L 1) ||00|||
Besides, we should note f(k-&- is the smooth (Assumption [A1]) energy function of P(K-k-1jn
denoting the underlying distribution of time (K k - 1)y in the forward OU process. Then, we have
[ (1) 2 = -Ep -ppx----
|| x)))
$2E PIK 13n
V K 1)
-- (x)] + 2E 2E 1>n
[| - 1 (1)) (1,=
2Thd 21.
2 Ppp
[|x]|*] 2Ld 21 max {d, m23 - 2T. + m3)
(73)
where the first inequality follows from Lemma E.6, and the third inequality follows from Lemma E.7. Under these conditions, we have
[ L. 2(d + m²) + 3L ||z0||
(74)
Then, for R defined as
Vg 12
d
165
R
max
8
63 L
VT. log
1
we can choose R to be the upper bound of RHS. Considering
V
4L + m2)
18L2
Foll +d 63
+
88
V(d (d
m3 + | 122)
L2
L
then we choose
165
R 63 V (d m + || (2) log
After determining R, the choice of be relaxed to
T TS C. (L3 (d + m2 + |(00| log
168
42

---

where the absolute constant 3 .7
since we have
(3LR+G. Escore) " 9 4G
165
$ 00. 632 (d + m² + || log
+ 4 (4L2 (d+ m²) + -18121<z011
165
9 632. 2 (d + m + 20.0 122 log
Hence, the proof is completed.
Theorem C.15. Under Assumption [AI]-A22) for any E (0, let fz.()) & exp(-a(z))1(z B(0, R)] be the truncated targer distribution in ((0, R) with
16S δ (dd -3]+mm++ + 110001)1113
R= (d+ m3 + -1000 log
r in Alg. 2 satisfies
85 r= 3. V Id
= =
and p be the Cheeger constant of P.. Suppose iuol [u[[l|x| 2 R/22) 1 c/16, the step size satisfy
(13 (d m3 + || log
165 -1 = Ō(L (d + m + || (
T T
the score and energy estimation errors satisfy
Cop
1/d-1122) and Cenergy I
CoPV 2T 32
OpT
Cscore 32 36
dog
sS
then for any X-warm starl with respect to ps the oulpul of both standard and projected implementation of Alg. satisfies
TV (us, = + (1- c6p2 :) 4
0p
0pp-1a-112 Cenergy)
Proof. We characterize the condition on the step size т. Combining Lemma C.2 and Corollary C.11, it requires the range of r to satisfy
T T 16 (3LR + [V)ll + Escore)
Under this condition, we have
dlog 8S
d log
88
85 -1
and TS 722 (722.02 2 dlog
T TS G TS
2 Score
which implies
8S and
88
(3LR + G) Escore T Escore F dlog
2 eccoe
< Escore FF. V /dlo
Then, we have
3cccore
85
(3LR + G)sscore T
T
16
rd
+
2
2
4
<16
3 3escore
V rdlog
8
+
Escore
rdlog
88
Escore
V rd
88
c
2
c
85
1
=366score
rrdlog
2
43

---

which matches the requirement of Lemma C.3. Under this condition, if we require
Cacore
Cop
Oppd
and
Cenergy I
CopV2T 2T
= O 1/2),
32 32.36 V dllo
it makes
85
Cupy/2T Φ
+ 5tenergy S 36escore
rd rdlog
+ 5ennrrg
6
16
16
and satisfies the requirements shown Lemma C.12.
Then, we are able to put the results of these lemmas together to establish the convergence of Alg. 2. Note that if Ho is a A-warm start to je, must be a A-warm start to Pl, since (A.( 2 pa (A() for all A E Q. Combining Lemma C.2, Lemma C.12 and Lemma C.13, we have
TV (us; 1.) TV (us, js) + TV (jss TV (Hbo)1a))
0²
16(6 + 5cenergy
+
+
8
Φ
(
s
/dlog
57eenergy
+ 408cscore
2
4
Cup
CUPVT
cpp²
s
(d p- Eacore) + +0 7-/2 Cenergy):
2
4
T
After combining this result with the choice of parameters shown in Lemma C.14, the proof is completed.
Lemma C.16. Under the same assumptions and hyperparameter settings made in Theorem 1.15, use Gaussian-type initialization
No (o(d))
| =21
dz
x exp
2(1 e 2n))
If we set the iteration number as
S ō (d mz) r-)),
the standard and projected implementation of Alg. 2 can achieve
Escore) 3e + (eeero)))))))) +
TV (ps, p.) S
Opp
Eenergy): )
Proof.
We reformulate the target distribution μa and the initial distribution Mo as follows
p+ (dz)
(f(--R-Do(*)+ +
31/12133
)
|1:00 - e 221
|
){
x exp
= <cxp(<(<2) xl22))
dz
2
2(1 c 2-)
2
no (dz)
-| 3|||2||2
||:00
e "2 1
3 2|(2
=||
(x())
x exp
= exp
2
2(1 22)
2
2
Under this condition, have
(o(dz) < exp exp (-0(2') v>(2()) dz' H4 (dz)
exp ((z)
(75)
Jqu e- |2/122 (x'))) dz
2
Due to Assumption [A1], we have
LI
+ 3L = ->)(= = 5LI
1 V2
f(
f(K-
2
2
2
which means
5L
5111=12
5L
x(z) S 0(2.)
-||--20 -2.12 S 6(2z)+ +
+
4
44

---

and
5L =1
5L 2. 11
exp
(())
2 exp ((zz) +
(76)
2
Since the function ((z) is strongly log-concave, it satisfies
/||=|
[V)(0)]
=|
[V)(1)12
Vo(z)
and <(z) 2 16
+ o(z.)
4
L
2L
due to Lemma E.3 and Lemma E.4. Under these conditions, we have
f exp 1-00===))-- (² dz' I exp -0((z)) + [Vo
/ exp
=||2111
(0(2)
de
2L
16
(V(11)1
23L 2211?
D 2/1
= exx
(0((z))
exp
de
2L
16
2(1 - E 27)
(77)
Besides, we have
5T.11211 2/12
d=' = - exp
|100 e 22'11
exp
(b(2))
-1112111
dz
2(1 - e 21)
which implies
=//122112
7T1122113 2/12
exp
xb(z')
d2'
exp
dz'
2
16
(78)
23L|
2'13
000 - e 11-11111
>
exp
dx
16
2(1 e 22)
Plugging Eq. 76, Eq. 77 and Eq. 78 into Eq. 75, have
no (dz)
5L 12
\V(0))1
/
exp
exp
dz'
(79)
n. (dz)
2T.
Due to the strong convexity of σ, it has
Vo(00 vo(z.)11
||. 1 <
L
L2
and
(
| J 00) 10)
< 21 + m²)
where the inequality follows from Eq. 73. Combining with the fact
7L x 1
16T d/2
exp
dz'
16
7L
Eq. 79 can be relaxed to
< max Ho(dz) R., (dz)
16m
d/2
< exp (22L. (d+ mz))
= exp (O(L(d m2)))
L
which is independent on ||æoo|-- Then, In order to ensure the convergence of the total variation distance smaller than e, it suffices choose T and S such that
x (1- 22
poT = 0 - 22 (
e s=
- 1-),
where the last two inequalities follow from Theorem C.15. Hence, the proof is completed.
Theorem C.17. Under Assumption [A1]-[2]], for Alg. I, we choose
2L +
and K 4L log (1 12)d (
11 = log 2L
2
45

---

and implement Step 3 Alg. 1 with projected Alg. 2. For the k-th run of Alg. 2, we use Gaussian-rype initialization po(dz)
-L||=|12 2(1 e 2(1-e-2)
exp
dz
we set the hyperpurameters as shown Lemma C.16, can achieve
TV (pKn. P.) S Set O(Ld cecccee))) with gradient complexity as follows
m2 Z)p Cenergy) (score) + O(f L (d
Ô 11- (d+ m2) z²2
for any i (0,1) where Z denotes the maximal la norm of particles appearing in outer loops (Alg. 1).
Proof. According Lemma B.3, know that under the choice
1
2T. + 1
== 2
In
2L
requires to run Alg. 2 for times where
(1 + L2 + (0]l
K 4L log
For each run of Alg. 2, we require the total variation error to achieve
-1 (1 L [
TV (D(4tam))o((1)))
(11))
s AL
log
2
02d112 (score) + 0(p TT
112
Conergy
Combining with Lemma C.16, we consider step size
(1+1 | (++)))++\V/.(O))
48TS log
Th =Cr La (d + m² + || 112) log
7
=Ō(L-2. (d+ m + |
where 7' (0, 1), solve the k-th inner sampling subproblem. Then, the maximum iteration number will be
S ō 2 (d+ m²)² ||
This means that with the total gradient complexity
K 11'
6 12--1 (d+ (m) z²²
where Z denotes the maximal l2 norm of particles appearing in outer loops (Alg. 1), can obtain
TV (pKn, + 02K (score) - O(KL(d+ m ///1/22-111// 1/2 Cenergy)
= 12 (scoro) + 0(f-111 12 (2) + m2 Z)p Eeeorgy
Hence, the proof is completed.
Lemma C.18. Suppose we implement Alg. with its projected version, we have
z (d p2²
where Z denotes the maximal l2 norm of particles appearing in outer loops (Alg. 1)
46

---

Proof. Suppose we implement Alg. with its projected version, where each update will be projected ball with a ratio y shown Lemma C.2. Under these conditions, we have
K
| 1| =
Σ
21 2
S (K+ + 1) |10l| 2 + (K + 1)
Σ c B; 1111
i=1
For each i E {1,2...
J. we have
S
| - = -12s--200 (S + 1).
Σ
||z - zj-111 $2.522.0 .
j=1
Follows from Lemma C.16, it has
(oBB(/1))
O (rd) = (cllos(N/e)
S =-
3 (T.(d (oild+m3)) m3)²0 3)
p²T
p²
Then, we have
z v O(K)) Ô (L(d+ mz)²p = 0 (I m²)²p
Hence, the proof is completed.
C.5 Control the error from Energy Estimation
Corollary C.19. Suppose the diffusion model se satisfies
pc
|| x t) + V Vloop(())llo S
Ld2/2'
and another parameterized model ig (I., f) is used to estimate the log- eigliiklihhod of pe))) satisfying for (x., t) + px))
pe
S L (d1/2 + m2 + Z)
If we implement Alg. I with the projected version of Alg. 2, it has
TV (DKm:P.) S (()
with the following gradient complexity
LLP 2 2, (d m3)² z²)
Proof. Since we have highly accurate scores and energy estimation, we can construct se and rg- (shown in Eq. 23) for the k-th inner loop as follows
e
21 -=
sz(z)= = s0(2, (K- k - 1)m) +
c c-2n
[bx -- 1
ro x1) = fo (z, (K - k- - 11m) +
2(1 e-22)
(o'(=',( (K- - -1))) + |0 - - 1) 2'112
2(1 222)
Under these conditions, we have
pe 1 (d1/2 m2 Z) and
Ccoore I PE
Cenergy I
Ldt1/2
Plugging these results into Theorem C.17 and setting = =1/2, we have
TV (pK,, P.) 5 p.) Ö())
with the following gradient complexity
Ô (L'' -2 (d+ (d+m3)² E²)
47

---

Corollary C.20. Suppose the score estimation is extremely small, i.e., p
[1 t) V Pe))ll
Ldd/2
and the log-likelihood function of has bounded 3-order derivative, e.g., v s()) L.
we have a non-purametric estimation for tog-likelihood to make we have TV Px) s O(t) with
δ (L'' 3. (d (d) z .e) .).
gradient calls.
Proof. Combining the Alg. 2 and the definition of Eeneryy shown in Lemma C.4, we actually require to control
Cenergy == (a(2s) - 9(x,)) re 2.)
for any E [0, 1). Then, start construct rg (2 zz). Since we have
200 2. e1 2(1 e 2n)
fIK- | 2, e e-1
g(E,) g(z)) = x +
2(1 c 2n)
should only estimate the difference of the energy function f(K-k-1); which will be presented as for abbreviation. Besides, we define the following function
h(t)) ((2. za) t. + ze)
which means
(1) dt(t) di Vf ((Es - 2,) .t 22) (2.- za) dt)(t) (ž, - =x)² v2 ((ā, 20) + z.) (Es zs)
(1)
(di)²
Under the high-order smoothness condition, i.e.,
f())| s
where ||
denotes the nuclear norm, then we have
(0)
L.
2, x.
1 (0)
Lr3
hh11 h(0))
i!
3!
i!
3!
2m
It means need to approximate (9) with high accuracy.
For = 1, the ground truth 4 (0) is
(0) dh(t)
Vf (zx) (Es 2a)
dt
we can approximate it numerically as (,() = 50(2,) (2g - 2o)
since have score approximation. Then it has
(()) (0) - (0) [Vf(z.) s0(2,)ll 113, 2xll S Cscore P.
(80)
Then, for i = 2, we obtain the ground truth (2) by
(²) ( 1' 1120 (T) (0000:1()0 (0) + 1' (T) (
which means
x0( = (()((1) (1)
(0)
/ 12 122)
t
48

---

If we use the differential to approximate (0). i...
1 (0) (1) (0
t
we find the emorr term will be
2 (0) (0) (0) = 1
25(1)
1 1
[/¹ (0)dr
(81)
If we use smoothness to relax the integration term, we have
= || ((z. - 2x) T - 1|
z=l1 - Lr 112 - =z.l1²
which means
1 1 L 0 (2 (0)dr =
11 - 2x
f rdr= S
1Tx
(82)
t
2
Combining Eq. 80, Eq. 81 and Eq. 82, have
8 ( 2ecure
L
t
2
which means the final energy estimation error will be
(1) ((10() (2())))-(0000
h(1) - x(0)-
2t
(0) (22)
3
2ecoor
Tr3t
Lr
(83)
Escore
r
3!
Term 2
Considering Cecore is extremely small (compared with the output performance error tolerance c), we can choose depending on Escore, e.g., / /Escore. to make Term 1 and Term in Eq. 83 diminish. Under this condition, the term Lr /6 will dominate RHS of Eq. 83, Besides, we have
85 ==3- rd (
then we have
(d (d+ m2 + || 3/2 43/22) 28/2 Cenergy = - = ( ---
where the last equation follows from the choice of shown in Theorem C.15. Then, plugging this result into Theorem C.17 and considering éxcore < e, we have
TV (pKn, p-) Se 12 p (score) +0 1/2 L (d + m2 + Z)p Cenergy)
<ō(e) Ô (A(dl/2 + m2 2)p-1)
with gradient complexity as follows
δ (I''p p1-p-22-1 20-1. (d m2)² z²)
Then, by choosing
cp
== d1/2 + my - Z
we have TV (pK,, p.) S Ö(e) with
ô OI'' 3. (d m 73.0)
Hence, the proof is completed.
49

---

Remark 3. If we consider more high-order smooth, i.e.,
b m f(z) S L,
with similar techniques shown in Corollary C.20, have the following bound, i.e..
((Tr")
Fenergy
when Escore is extremely small. Under this condition, since has
85 = - == ld
we have
Cenergy = O(rr") = ((ddd12200)) = - (1, (d m² + |122113)) -u/2 qu/2) -
Then, plugging this result into Theorem C. and considering fscore < we have
TV (pxm.Po) Se OLd Escoro) 00/-1/2. ( m2 Z)p Connrgy)
=O(e)+ + (x(())(001111111--11 (- + m2 + Z)p-1)
=Ō(c)+ (f11-1)/22 + m2 + 2)p=1)
where suppose L 1 in the last equation without loss of generality. Then, by supposing
22((u-1)
f d1/2 + m22 + Z
have TV (pKn, p.) S O(e) with
(d (d z3 -2/(u-1) .2
where the last 2 appears since the estimation of high-order derivatives requires an exponentially increasing call of score estimations.
D Implement RTK inference with ULD
In this section, we consider introducing a ULD to sample from P (2(20)) To simplify the notation, we set
g(z) = (2) + | 2 2 2
(84)
2(1 e-2r)
and consider and xo to be fixed. Besides, we set
x" (=(00)) (2 exp(-g(z))
According to Corollary B.5 and Corollary B.3, when we choose
2L +
y = log 2L
the log density g will be L-strongly log-coneave and 3--smooth.
For the underdamped Langevin dynamics, we utilize a form similar to that shown in [40], i.c.
d2, d,
(85)
dv, = -Vvedt s0 (2rr dt + 22ydB
with little abuse of notation for t [ST, (s 1)7). We denote the underlying distribution of (Z,, v.) as āt. and the exact continuous SDE
dz. v,dt
dv, = -v - Vg(zz)dt + 2
50

---

has the underlying distribution (Z,, vi) ~ Tt. The stationary distribution of the continuous version is defined as
x- (z, v/2o) & exp (-9(a) |000
2
where the z-marginal of x (-(ro) is (- which is the desired target distribution of inner loops. Therefore, by taking small step size for the discretization and a large number of iterations, ULD will yield an approximate sample from p² (-(ro) Besides, in the analysis of ULD, we usually consider an alternate system of coordinates
(b, = = x) (z.
their distributions of the continuous time iterates n. and the target in these alternate coordinates TM, respectively. Besides, we need to define tog-Sobolev inequality as follows Inequality). The target distribution satisfies the following inequality
Definition
Epp [g² logg" (9p_ pg"1 & 2C1sE ||
with constant LLS for all smooth function g: TRd + R satisfying E.p. Bp2 <o.
Remark 4. Log-Sobolev inequality is milder condition than strong log-concavity. Suppose p satisfies m-strongly log-concavity, satisfies 1/m LSI, which is proved in Lemma E.9.
Definition (Poincaré Inequality). The target distribution satisfies the following inequality
Ex-p
[lx(x) Ex-n (xx)11 I CpIEp 1 g
with constant for all smooth function Rd + R satisfying Ep. [9 < oc.
In the following, we mainly follow the idea of proof shown in [40], which provides the convergence of KL divergence for ULD, to control the error from the sampling subproblems.
Lemma D.1 (Proposition 14 in [40]). Let T.M denote the law of the continuous underdamped
Langevin diffusion with & cv/LL for V2 in the (ó, +) coordinates. Suppose the initial
distribution xo has a log- Sobolev (LSI) constant (in the altered coordinates) CLSI(TA then {T( satisfies LSI with constant that be uniformly upper bounded by
CLSI(TMM) S exp (-v
2T. 22 ()
CCSS((TOM) + L
Lemma D.2 (Adapted from Proposition [26]). Consider the following Lyapunov functional
2
F(T' = KL (T' + Ex,
/2 log
where
21
T2T
VOL
8 la-
VBL
For targets nt x exp(-9) 9) which are 3L-smooth and satisfy LSI with constant 1/L, ler y = 2/ Then the law ne of ULD satisfies
VI F(TTTT 10V6
0, 7
Lemma D.3 (Variant of Lemma 4.8 in [t]). Let te denote the law of SDE. 85 and denote the law of the continuous time underdanped Langevin diffusion with the same initialization, i.e., fu = To- If
y x VL and the step size T satisfies
T= δ (166-330-11111111
then we have
x² ( $ 3/2
2
1/2 -1/22
51

---

Proof. The main difference of this discretization analysis is whether the score V log Pr can be exactly obtained or only be approximated by so. Therefore, in this proof, we will omit various steps the same as those shown in [1].
We consider the following difference
(++1)r
GT = V ==0
(Vg(zi) - (
1
(a+1)r
[Vg(zz) sz( dt.
From Girsanov's 's theorem, we obtain immediately using Itt's formula
d drt
1
1)r exp(2G.) Vgg(z) se (zer))) 11
Ear
-
= lexp (2GT))
-
E
27
(++1)r
[exp(44.)] E Vg(zt)) se(2)r)]1
S-1
(0+1)r
E [exp(4GG]] VV((z) Vg(
==0
2
S-1
(e-1)r
soore
[exp(4Gr)]dt
==0
According to Corollary 20 of [40], have
16
()+1)
VVg(z)) so s0(z)r)1 dr ) ]
E [exp(4Gd) S
E
exp
==0
32
8-1
(s+
(stt)
E exp
Vg(2z) - Vg( dr +
eoordd dr
==0
16tc
32
(s+1)rAt
exp
E Eexp
Vg(zz)) (z( dr
?
==0
9-1
(s+1)-At
32
<3
Eexp
[Vg(z,)
[z((sr) 2r
(86)
where the last inequality can be established by requiring
Escore =0 -222/21--12
16te
<
since exp(u) < 1 + 2u for any u E [0, 1].
With similar techniques utilized in Lemma 4.8 of [1], we know that if
2 1/2
33L
3
7 VLL
and T>
6L /L/31//2//2 (log S)1/2'
L L'
it holds that
E Exxp
32
Σ
(++1)778
[Vg(z,) =2( dr exp (o [1,112 1,312d722 2Tgg logs))
s=
Furthermore, for
S L 3/2 d 1/2T 1/2 (log S) 1/2
11/2
52

---

it has
sup E (exp(4G,)) 2 1. re
Then, still with similar techniques utilized in Lemma 4.8 of [1], we have
E [V((zz) Vo( - (3I)² R ||ze Z
zorl1*]
s 1?d
In summary, we have
d dπr
21
Ldd
Sccore" T
2
Buy
1
7
and the proof completed.
Corollary D.A. Under the same assumptions and hyperparameter settings made in Lemma D.3. If the step size and the score estimation error Escore satisfies
and Escore = O (T-1/2))
T
T,3/4//221/2
Then we have ( S 2
Proof. We can easily obtain this result by plugging the choice of T and e into Lemma D.3. Noted that we suppose L 2 1 without loss of generality.
Theorem D.5 (Variant of Theorem 6 in [40]). Under Assumption [A1]-[A2], for any E (0, 1). we require Gaussian-type initialization and high-accurate score estimation, i.e.,
#o NO 2h 1) & (O, and
éscore Ö(e).
If we set the step size and the iteration number
[ldd + m + ||a00121] -1/2
r= θ
cd 1/2 1/-122
log
²²
L(d + m2
(20013)) 112 1 1/2
S= 1/222
log
22
the marginal distribution of output particles frr will satisfy KL (pr||= (11l0=((oo)))) (-1200) S O
Proof. Consider the underlying distribution the twisted coordinates (Ø, v) for SDE. 85, the decomposition of the KL using Cauchy-Schward Schwarz:
KL ( | /
#M TM
MMM) /
log
dāp
KL
(#1
log
dad
TM
(MM |M + /
M
KKL (T
KL
log
c MTM)
dl
7.M
KL
(+
|
KL
(T
M² / x²
||
var
Ilog T
T.M
(87)
Using LSI of the iterations via Lemma D.I, we have
27 $ Enzge
ny T.
var log
s CiSI(T+M)
Enge
Flo
V log
TM
T.M
Then, we start to upper bound the relative Fisher information. Since TM = M nr (- (D): then
π MM, v) x - (M- ())
Therefore, we have
V Mo = (M-1) V To logg==(((zo))) (-120) M-
53

---

and similarly for V log m...
This yields the expression
2
log
EuT
TT log
(88)
π
According to the definition of M, we have
M
MM
1
-7/2 /2/2
-212
For any co > 0 and
MT
T2L
VOT. 4
2 Ia
V6L
we have
LAN C (M- -MM-)M-MMM-
1/4 co
V3L(1/V2 coV2)
V3L(11/V2 + +
3L(4- - co)
The determinant is
3L ( ( (1-co)
1 (12 coV2 )
>0
for co > 0 sufficiently small, which means that
(M- 3 - LmR.
Therefore, Eq. 88 becomes
1
7. x.M
|| log n
E
V
log
S 3L Ber
According to Lemma D.2, the decay of the Fisher information requires us to set
To T T L 1-12 log 2 KL (fol|=²) + E (1102//2
log x 11)
(89)
which yields KL (TM || π M)
< 2. Besides, we can easily have
E
| log
S 3L
FI (TO|(===*
1
Ex
| _o -- 11)
3L
According to the definition of LSII, we also have
CL.sT
2 x
KL (Ta||=*)
FI (Nol [To||TT (T)
2T. Emo
Recall as well that this requires y x vLL in SDE. 85. For the remaining KL (#+1 M and x² (MMM) in Eq. 87, we invoke Lemma D.3 with the value T ST specified and desired accuracy e,, which consequently yields
T
T - θ 13/40//271/2
and S= Ô
(90)
Under this condition, we start to consider the initialization error. Suppose we have To = N(O, c2 1) & (0 I), which implies
FI To (+) Enn
V Wf(K- - V f(KK f(K-K-1 (0)
200
1
2n
-2 2n
<31 <3I. ||| 33, / (0)l +
||200|2
(1 - c 2-2)
30- 27
=312. (6 - 1) + 3 V (0)| +
|
(1 - e 222
54

---

Following the 17 setting, i.e..
1
2L + 1
2L + 1 2L
1 2
log
2L
which yields
FI TTo π
SL + | f( -K- k- -- (0)l L =
(9))
2 + Ld + m²) - 10
where the inequality follows from Eq. 73. Therefore, combining Eq. 91, Eq. 90 and Eq. 89, we have
(1V log 112] () 1/2
[(d m + TD P1]
1/2
E
T 2 --14 log
2 1/4
log
2
LE
which implies
L(d + m2 + || 11 1)
-1/2
θ
ed 1/2 id21 1/2. 1-122.
log
6²
L(d + my + 1| (1110011)) 12)) 1/2)
S θ
d log
In this condition, the score estimation error is required to be
Eacore O ( (/2/2T-1/2 e) 7 (E/VV)
Hence, the proof is completed.
Theorem D.6. Under Assumption [AI]-[A2], for Alg. 1, we choose
2L
and K = 4L log (1+ ++)
11 3= 2
log
2L
2²
and implement Step of Alg. with projected Alg. 3. For the k-th run of Alg. 3, we require Gaussian-type initialization and high-accurate score estimation, i.e.,
to =N 1) & (0,, and (scare = Ō
we set the hyperparameters shown in Lemma D.5, it can achieve TV (pKn, Pa) S e with Ô (22 gradient complexity.
Proof. According to Corollary B.5, we know that under the choice
1 In
2L 1
1 2
2L
it requires to run Alg. 3 for times where
(1 L2)d + (0)l
K = 4L log
22
For each run of Alg. we require the KL divergence error to achieve
2
(1+ I.2 [O]]
KL (p (-))) (m) S 4L
log
2²
Combining with Theorem D.5, consider a step size
Th - I 1I-1 (log [ (d + m3 + || +1xx|13))|
then the iteration number will be
S₁ Ô 12 122 (log I (d m + || || 12))
For an expectation perspective, we have Ep,,, [Io ]| S log [Epan [ [2-]] = Ö(L)
where the last inequality follows from Lemma B.6. This means that with the total gradient complexity
K.S S S- ( (12d((()))
Hence, the proof is completed.
55

---

E
Auxiliary Lemmas
Lemma E.1 (Theorem 4 [35]). Suppose p x exp(- f) defined on Rdd satisfies LSI with constant > O. Along the Langevin dynamics, i.e.,
dx; -Vx(xxx v2dB,
where X, ~ Pt. then it has
KL (p:llp) I exp (- KL (po (Po|(p)
Lemma E.2. Suppose p & exp(-f) defined on IRd satisfies LSI with constant μ >> O where f is L-smooth, i.e.
[V (=()))] L ||æl æ=l-
If Po is the standard Gaussian distribution defined on F then we have
21+21 2 (0))
KL KL (pollp)
1
Proof. According the definition of LSSI, have
/ po(a))
V log Po(
KL (pol (po|lp) - 2/c
dæ 24
v=())] dx
p(x)
[f (o(xx)]ax=1/dder po(x))|V/(<>) - 2
Su4 1
[1 (1+211 21.3) / po(<))l<<\|3dd 2
Sp Sp-1
(1 + 2d 2
where the third inequality follows from the L-smoothness f- and the last equation establishes since Ep, ||| is for the standard Gaussian distribution in Rd.
Lemma E.3 (Variant of Lemma B.1 in [41]). Suppose f: Rd + R is m-strongly convex function and satisfies L-smooth. Then, we have
Vf(x) x m |=
2
2m
where x. is the global optimum of the function f.
Proof. According the definition of strongly convex, the function f satisfies
f(0) f(x) 2 Vf(x)) (0- x) +
||
f((x) 2 f(x) f(0) +
||<=||
Besides, we have
f(z) f(0) (
|
|
-|=11 1
2
2
2m
2m
Combining the above two inequalities, the proof completed.
Lemma E.4 (Lemma A.1 in [41]). Suppose a function f satisfy
Vf(x)) x 2 m2|
V
VO()))
2m
then have
f(x) 2 m | f(xx)
[0)
8
4m
56

---

Lemma E.5 (Lemma in [18]). Consider the Orastein-Uhlenbeck forward process
dx, -xxdt + V2dB
and denote the underlying distribution of the particle x, Pt. Then, the score function can be rewritten as
270 x
V (mpp)))) = (
(1 - E-21)
(92)
| - xx 2 2 - E 21)
(x(0o()))))) & exp (fa(2o)
Lemma E.6 (Lemma 11 [35]). Assume x exp(-f) and the energy function f is L-smooth. Then
Exmp [V
s Ld
Lemma E.7 (Lemma 10 [8]). Suppose that Assumption [A1]-[A2] hold. Let {xi)eeto,7 denote the forward process, i.e., Eq. 1, for all t 2 0,
|x| S max mm)
Lemma E.8. Suppose 9 is a distribution which satisfies LSI with constant μ4, then its variance satisfies
i ((xx) - Eg [x]] dæ d 1
Proof. It is known that LSI implies Poincaré inequality with the same constant, i.e., μ, which means if for all smooth function g: Rdd + R.
var, (g(x)) S -E, [1V
1
In this condition, we suppose b E.g [x], and have the following equation
/ 1 (x)) x - Eg [x]] dx / ((00) || bb12
(xx) (a: b.)² dx Σ / ((()) (120, ei) (b, e:)) 2
dx
Σ g(x) ((x, e;) - By (xx, e;)l) do = Σ var, (g:(x)
where gi (x) defined as (x) = (xx e.) and e; is a one-hot vector ( the i-th element of e; is 1 others are 0). Combining this equation and Poincaré inequality, for each i, have
var, (x:(x)) < Egg [1e:11]] 1
1
Hence, the proof is completed.
Lemma E.9 (Variant of Lemma 10 in [11]). Suppose log p. is m-strongly convex function, for any distribution with density function p. we have
1
p(æ)
KL (p|lp.) - 2m p(z)
V log
dx.
(x)
By choosing p(æ) = (x) (x)) [x)) for the test function g: Rdd + and Ep. [x](x)) < we have
2 Ep. |
Ep. 19² log g²1 - Ep. [g²] log Ep. [9²] = m
which implies pa satisfies 1/m-log-Sobollv inequality.
57

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiiaton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No] ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We have clear claim that we improve the diffusion inference by RTK
framework.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
58

---

Justification:
We discussed the limitation in section 5.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approxinations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faireess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: See Section 4 A1, A2, EI, E2, E3 for Assumptions. Proof are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question:
Does the paper fully disclose all the information needed reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: See our Appendix.
Guidelines:
59

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have detailed information in the Appendix to reproduce the emprical results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
mublic/guides Srriides/CodSSummisse oonibmiiiiio for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / inips.cc/publl hwwpc//gueee..ee/ (CodeSubmiii cimmisssionn sesinnooicy)) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
60

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
See the Appendix for more information.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: We just have illustrative empirical result about the trend and generated samples. Not claims for accuracy or error from the empiral side.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: See appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
61

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /twprri////eep.eeeeeee wctpubbicc/thiccsuiieee.e
Answer: [Yes]
Justification: Conducted
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consideration due laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
It is theoretical paper. No societal impact is visible in a short term.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No real data in this paper.
62

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No real data are used.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi wwwwdhehcode..oo com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Only synthetic data are used with detailed instructions.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
63

---

Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
64


Reviews:
[{"review_id": "QQm4qDl5BS", "reviewer": "Reviewer_81an", "summary": "This paper discusses an acceleration method for the inference of the diffusion models. It considers the denoising diffusion process as a sequence of reverse transition kernel (RTK) sampling subproblems. Then, the paper integrate the RTK subproblems to the Metropolis-Adjusted Langevin Algorithm (MALA) and Underdamped Langevin Dynamics (ULD), for solving strongly log-concave subproblems.", "questions": "1. There is a certain step size choice used in this paper (for example after Lemma 3.1 and Theorem 4.1), and the choices are to ensure the strong long-concavity of target distribution. How is this derived? Is this a unique choice in some sense? There is a paragraph after algorithm 2 commenting on the step size choice, I'm wondering if this result can be made more concrete and precise.\n\n2. What is a practical way of choosing the step size for general target data like real-world image datasets?\n\n3. What are the challenges in complexity analysis compared to the cited results [8, 9, 21] in Table 1? As DDPM can be seen as solving RTK sampling subproblems using a small step size, can you show the method discussed in this paper yields a more general technique in terms of complexity analysis?", "limitations": "The limitations have been discussed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper presents a new modification of diffusion models, where it views DDPM as approximately solving RTK sampling subproblems using a small step size. Based on this, the authors propose two efficient algorithms for diffusion inference and demonstrate the acceleration theoretically and empirically through a mixed Gaussian example.", "weaknesses": "The choice of step size is important as there is a trade-off between the log-concavity of RTK subproblems and the number of subproblems. Either too small or too large of the step size results in a high computational complexity. The convergence results in section 4 are built upon a particular choice in the step size, which depends on the Lipschitz constant associated with the target data. The proposed method will gain more clarity and generality, and be beneficial to algorithm design if a concrete computational complexity in terms of the step size can be analyzed. See questions below for more details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful review. We will answer your concerns one by one in the following.\n\n> W1: The convergence results in section 4 are built upon a particular choice in the step size...\n\nAW1: Sorry for the confusion. The particular step size choice in Section 4 is to simplify our theory. Any step size smaller than such a choice will be feasible, making the target distribution of the sampling subproblem strongly log-concave. \n\nFor general step size $\\eta$ in RTK-ULD, the gradient complexity should be\n\n$$\\tilde{O}\\left( \\underbrace{C_{\\mathrm{LSI}}(\\eta)^{3/2} \\cdot \\left(L+\\frac{e^{-2\\eta}}{1-e^{-2\\eta}}\\right)^{3/2}\\cdot d^{1/2}\\epsilon^{-1}\\eta^{-1/2}}\\_{S} \\cdot \\underbrace{\\eta^{-1}\\cdot \\log \\frac{(1+L^2)d+\\\\|\\nabla f\\**(0)\\\\|^2}{\\epsilon^2}}\\_{K} \\right),$$ which can be obtained with similar proof techniques in Theorem 4.4.\n\nNote that the LSI constants of the subproblems depend on $\\eta$.  If the step size is large ($\\Theta(1)$-level), the constant $C_{\\mathrm{LSI}}$ will blow up and grow exponentially wrt $L\\eta$, i.e., $C_{\\mathrm{LSI}} = \\exp(O(L\\eta))$ (Proposition 1 of [Ma et al.]). If the step size is smaller than $ \\ln (1+1/2L)$, the target distribution of inner loops will be log-concave, and we have\n$$C_{\\mathrm{LSI}}(\\eta) = \\left(-L + \\frac{e^{-2\\eta}}{1-e^{-2\\eta}}\\right)^{-1}.$$\nOmitting the log-terms, the gradient complexity will be\n$$\\tilde{O}\\left(\\underbrace{ \\left(\\frac{L+\\frac{e^{-2\\eta}}{1-e^{-2\\eta}}}{-L+\\frac{e^{-2\\eta}}{1-e^{-2\\eta}}}\\right)^{3/2}\\cdot d^{1/2}\\epsilon^{-1}\\eta^{-1/2}}\\_{S} \\cdot \\underbrace{\\eta^{-1}}\\_{K} \\right).$$\nTherefore, plugging our setting $\\eta=1/2\\cdot \\ln (1+1/2L)$, we can obtain the complexity shown in Theorem 4.4.\n\nWhen $\\eta$ is extremely small ($\\Theta(\\epsilon)$-level), we can use a one-step update for the inner sampler. Under these conditions, we have $S=1$, and the complexity will only be dependent on $K$. We defer the explanation in Question 3. In the next version, we will add this theorem to demonstrate the gradient complexity for general cases.\n\n> Q1: How the step size is derived? Is this a unique choice in some sense?\n\nAQ1: Sorry for the confusion. The step size is derived from Line 188-189. Specifically, we requested the Hessian matrix of the RTK to be $L$-positive-definite,\n$$-\\nabla^2 \\log p_{(K-k-1)\\eta|(K-k)\\eta}(x) = \\nabla^2 f_{(K-k-1)\\eta}(x)+ \\frac{e^{-2\\eta}}{1-e^{-2\\eta}}\\cdot I \\succeq -L\\cdot I + \\frac{e^{-2\\eta}}{1-e^{-2\\eta}}\\cdot I \\succeq L\\cdot I.$$\nwhere the first inequality follows Assumption 1 (L-smoothness of $\\log p_t$). With this inequality, we have $\\eta\\le 1/2\\cdot \\ln(1+1/2L)$. Thus, we can provide the upper bound of the step size rather than the unique one. Some results shown in the para after alg 2 are also derived by the Hessian matrix. We will make it clear in the next version.\n\n> Q2: What is a practical way of choosing the step size for general target data like real-world image datasets?\n\n\nAQ2: Since data distribution smoothness is usually unknown, we tune the step sizes with **grid search**. Practically, we first set the NFE as $M$. Then, we tune the outer iteration number $K$. For any $K$, the outer step size is set as $\\eta = 1.0/K$, and the inner iteration number is $S = M/K$. Finally, we tune the inner step size $\\tau$.\n\n> Q3: What are the challenges in complexity analysis compared to the cited results [8, 9, 21] in Table 1? ... can you show the method discussed in this paper yields a more general technique in terms of complexity analysis? \n\nIn summary, compared with [8, 9, 21] in Tab 1, the technical challenges of this paper are as below\n\n- For the outer complexity analysis, how can we break away from the paradigm (used in [8, 9, 21]) of using the Girsanov Theorem to analyze the discretized reverse process? As a solution, we calculate the close form of the reverse transition kernel (RTK), which considers the inference as a series sampling subproblem.\n- For the inner complexity analysis, how can we derive the gradient complexity when sampling algorithms can only access an approximate drift (score estimation $s_\\theta$) or energy differences rather than the exact ones ($\\nabla\\ln p_t$)?\n- For the total complexity analysis, how can we control the error propagation of a series of sampling sub-problems whose target distributions are RTKs? As a solution, we introduce chain rules of $f$-divergence.\n\nFor the generality, DDPM is a special case of our analysis when $\\eta$ is chosen at an $O(\\epsilon)$-level.\nWhen we choose DDPM to generate data, the ideal and practical reverse transition kernels are shown as follows\n$$p^\\gets(x|x^\\prime) \\propto  \\exp\\\\left(-f_{k\\eta}(x) - \\frac{\\\\|e^\\eta x^\\prime - x\\\\|^2}{2(e^{2\\eta}-1)}\\right).$$\n$$\\hat{p}(x|x^\\prime)\\propto \\exp\\left(-\\frac{\\\\|e^\\eta x^\\prime - 2(1-e^{\\eta})s\\_{\\theta,(k+1)\\eta}(x^\\prime)- x\\\\|^2}{2(e^{2\\eta}-1)}\\right).$$\nwith Lemma 3.1 and Line 123-132 in Section 2.\nWe suppose step size is small, e.g., $e^{2\\eta} - 1 = \\epsilon$, and have\n$$-\\nabla_x^2 \\log p(x|x^\\prime) = \\nabla\\_{x}^2 f_{k\\eta}(x) + \\epsilon^{-1}\\cdot I \\succeq (2\\epsilon)^{-1}\\cdot I.$$\nThis means the RTK is an $1/2\\epsilon$-strongly log-concave distribution. With LSI, we have\n$$\\mathbb{E}\\*{x^\\prime}\\left[ KL\\left(\\hat{p}(\\cdot|x^\\prime)\\|p^\\gets(\\cdot|x^\\prime)\\right)\\right]\\le 2\\epsilon\\cdot \\int \\hat{p}(x,x^\\prime)\\cdot \\left\\|\\nabla \\log \\frac{\\hat{p}(x|x^\\prime)}{p^\\gets(x|x^\\prime)}\\right\\|^2 dx  \\approx  2\\epsilon \\cdot \\int \\hat{p}(x,x^\\prime)\\cdot \\left\\|\\nabla \\ln p\\_{k\\eta} - s_{\\theta,(k+1)\\eta}(x^\\prime)\\right\\|^2 dx,   $$\nwhere RHS of this inequality is the same as the discretization error controlled in [Chen et al.], which can be further relaxed by Eq. (5.6) of [Chen et al.]. Thus, the method discussed yields a more general technique in terms of complexity analysis.\n\n[Ma et al.] Sampling Can Be Faster Than Optimization.\n\n[Chen et al.]  Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions.", "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": "3jwsBeGfdC", "reviewer": "Reviewer_PyUH", "summary": "This paper takes a fresh perspective on simulating the backward SDE in diffusion modelling, proposing to replace the usual Euler-Maruyama discretisation (i.e. based on Gaussian approximations) with a more accurate approximation (based on Metropolis--Hastings and related techniques).  The approach is explored in theoretical detail, and it is argued that in principle fewer time steps are required to simulate from the backward SDE.", "questions": "- Is solving the backward SDE really a computational bottleneck in diffusion modelling?  I had imagined that learning the score function was actually the main bottleneck.\n\n- Do the author(s) results allow for plug-and-play in terms of the sampling method used?  For instance, if I design a new sampling method for use in this context (e.g. some new version of Metropolis--Hastings) what conditions would my method need to satisfy in order to inherit the theoretical guarantees that have been established?  A clear statement could help other researchers to engage with these results.", "limitations": "The main limitation is the lack of empirical support, which the author(s) acknowledge in the conclusion section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Casting the solution of the backward SDE as a sequence of \"simple\" sampling problems is an interesting approach that opens the door to new methods and it is conceivable that these could deliver practical benefit.\n\n- The theoretical analysis appears to be extremely detailed, taking into account both the usual SDE discretisation errors that occur when approximating the backward SDE and the sampling errors that are incurred using Metropolis--Hastings and related techniques.", "weaknesses": "- The principal justification for this strategy is theoretical, and it is not yet clear whether it is practically beneficial.\n\n- Some of the English language was confusing at times, for example referring to \"Gaussian process\" when I believe \"Gaussian approximation\" (or similar) was intended.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive comments and helpful suggestions. We will response to your concerns point by point in the following.\n\n> W1: The principal justification for this strategy is theoretical, and it is not yet clear whether it is practically beneficial.\n\n\nAW1: In this paper, we mainly focus on the theory (RTK framework) about the convergence of the diffusion inference process and highlight how to design algorithms (RTK-ULD and RTK-MALA) to achieve a faster convergence rate in theory. In the meantime, we have also provided some experimental results for the Gaussian mixture targets shown in the Appendix. A, which justifies the effectiveness and efficiency of the RTK-based methods. Besides, we also add some new experiments in our latest supplementary material of rebuttal. These experiments are conducted on another two Mixture of Gaussians (MoG) and the MNIST dataset, which validates RTK-based inference process outperforms DDPM in different settings. More details about the supplementary experiments can be found in the common response. We will add them to our paper in the next version.\n\n> W2: Some of the English language was confusing at times, for example referring to \"Gaussian process\" when I believe \"Gaussian approximation\" (or similar) was intended.\n\n\nAW2: We will revise them in the next version.\n\n> Q1: Is solving the backward SDE really a computational bottleneck in diffusion modelling? I had imagined that learning the score function was actually the main bottleneck.\n \n\nAQ1: In summary, learning the score function and solving the reverse SDE are separate subproblems of diffusion modeling. Specifically, solving the reverse SDE is the bottleneck for the inference process. For the practitioners, if they would like to generate data based on pre-trained models, the efficiency of generation only depend on the inference process , i.e., solving the SDE with well-trained scores. On the other hand, if one would like to develop a diffusion model for some new datasets, learning score in the training process will be the main focus.\n\n> Q2: Do the author(s) results allow for plug-and-play in terms of the sampling method used? For instance, if I design a new sampling method for use in this context (e.g. some new version of Metropolis--Hastings) what conditions would my method need to satisfy in order to inherit the theoretical guarantees that have been established? A clear statement could help other researchers to engage with these results.\n \n\nAQ2: That is a good question. Our RTK framework definitely allows for plug-and-play in terms of the sampling method.  This is one of the core advantages of the RTK framework.\n\nAs for the conditions of a new sampler that need to be satisfied, we require it to converge to any strong log-concave target distribution with arbitrary error tolerance for KL divergence or TV distance. To guarantee the final convergence, we first set the step size $\\eta$ and the iteration number $K$ of outer loops as Corollary C.3 and C.5, i.e.,\n$$\\eta = \\frac{1}{2}\\cdot \\log \\frac{2L+1}{2L},\\quad K = 4L\\cdot\\log \\frac{(1+L^2)d+\\|\\nabla f_*(0)\\|^2}{\\epsilon^2},$$\nwhich is independent of the choice of inner samplers. Then, if the inner sampler can guarantee the TV distance convergence, we require it to converge to the target distribution with an error tolerance at most\n$$TV\\left(\\hat{p}\\{(k+1)\\eta|k\\eta}(\\cdot|\\hat{x}), p^\\gets{(k+1)\\eta|k\\eta}(\\cdot|\\hat{x})\\right)\\le \\frac{\\epsilon}{K}\\le \\frac{\\epsilon}{4L}\\cdot \\left(\\log \\frac{(1+L^2)d+\\|\\nabla f_*(0)\\|^2}{\\epsilon^2}\\right)^{-1}$$\nwhich is shown in our Corollary C.3. A similar result can be found in Corollary C.5 if the inner sampler can achieve the convergence of KL divergence.", "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": "4inWwjU6pB", "reviewer": "Reviewer_kQ8M", "summary": "The manuscript is on accelerating or improving the inference in diffusion models. This denoising process corresponds to the discretization of an ODE or SDE. In this work, the authors view this process as multiple reverse transition kernel sampling subproblems. They introduce a general framework for the reverse transition kernel, and leverage two sampling algorithms to solve it. Theoretical results on the convergence of both sampling methods are presented.", "questions": "### Minor comments\n\n- potential typo on line 118 \"To implement SDE.\"\n- wrong punctuation at the end of eq. 5. \n- Alg. 3 \"of the previous iteration $x_0$\", shouldn't it be $x_{k-1}$?", "limitations": "The authors address the limitations of their work in the manuscript.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The method seems novel and founded on a strong theoretical analysis. The authors find the analytic solution of the RTK for specific SDEs which enables practical algorithms. \n\nThe overall presentation of the manuscript is good, and the theoretical analysis improves on existing ones.", "weaknesses": "The manuscript lacks of experiments and especially comparison with existing inference methods. Theoretically, these methods seem to improve on existing one, but it would be great to show it in practice as well, e.g. comparing FIDs of a pretrained model for different inference methods. \n\nThe discretization of an ODE or SDE is replaced with $K$ subproblems consisting of sampling from the reverse transition probabilities. Within each of these subsampling problems, we need to simulate a chain of size $S$, requiring at least $S$ calls of the score network. My understanding is that you would need to call the score network at least $K\\times S$ times. I wonder if the authors could show experiments comparing the number of function evaluations (or computation time) for different methods and their scores (e.g. FID of generated images). I believe some of this analysis on synthetic datasets is presented in the appendix. It would be great to improve these experiments and move them to the main body of the text; it would help convey that for the same NFE the accuracy is greater, so the proposed method indeed accelerates inference without decreasing the performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments. We will response to your question in the following.\n\n> W1: The manuscript lacks of experiments and especially comparison with existing inference methods. Theoretically, these methods seem to improve on existing one, but it would be great to show it in practice as well, e.g. comparing FIDs of a pretrained model for different inference methods.\n> \n\nWe have conducted additional experiments on both synthetic and real-world data. Additionally, we have included comparisons with an existing method and evaluated a new numerical metric. The detailed results of these experiments are included in the supplementary material of the rebuttal.\n\nFor synthetic data, we conducted additional experiments on spiral-shaped and chessboard-shaped Mixture of Gaussians (MoG), as shown in Figures 1 and 2. Our RTK-based methods achieved significantly better marginal accuracy with a small number of function evaluations (NFE). Comparing Annealed Langevin Dynamics (ALD) [Song et al.] with our RTK-based methods, we found that ALD has much lower marginal accuracy, particularly when NFE is small. Furthermore, using the Wasserstein Distance metric (Figure 3), we found that our RTK-based methods outperformed DDPM and ALD, especially with a small NFE.\n\nFor real-world data, we conducted experiments on the MNIST dataset, as shown in Figure 4. In Figure 4(a), we show that, with the same NFE, the RTK-based methods achieve better FID scores than DDPM, especially when NFE is small. Figures 4(b-d) further illustrate that the RTK-based methods generate images of higher quality than DDPM when NFE is small. We hope these supplementary experiments will address your concerns. \n\nWe will include these additional results and try more real-world dataset in the revision.\n\n> W2: Weakness. 2: The discretization of an ODE or SDE is replaced with K subproblems consisting of sampling from the reverse transition probabilities. Within each of these subsampling problems, we need to simulate a chain of size S, requiring at least S calls of the score network. My understanding is that you would need to call the score network at least K*S times. I wonder if the authors could show experiments comparing the number of function evaluations (or computation time) for different methods and their scores (e.g. FID of generated images). I believe some of this analysis on synthetic datasets is presented in the appendix. It would be great to improve these experiments and move them to the main body of the text; it would help convey that for the same NFE the accuracy is greater, so the proposed method indeed accelerates inference without decreasing the performance.\n> \n\nActually, the gradient complexities (or the number of function evaluations) we analyzed in Theorem 4.1 and Theorem 4.4 are indeed calculated by $K\\cdot S$. For Theorem 4.1, we provide the detailed chose of $K$ and $S$ at Line. 945 — Line. 947. For Theorem 4.4, we provide the $K$ and $S$ at Line. 301 — Line. 302 and Line. 304 — Line. 305 in the main body of this paper.\n\nWe also provided the number of function evaluations (NFE) in our experiments for the Gaussian mixture targets. According to the top-right figure in Figure 1, we compare the marginal accuracy [Mangoubi et al.] of different inference algorithms, whose x-axis explicitly denotes NFE. Therefore, we think the comparison is fair, and we will move our experiments to the main text in revision.\n\nFurthermore, we also provide some comparisons in FID-NFE for both synthetic and real-world data which can be found in Figure. 3 (calculated by Wasserstein 2 distance) and Figure. 4 in our latest supplementary material of rebuttal. Both the FID-NFE graph and the case study illustrate that the RTK-based methods generate images of higher quality than DDPM when NFE is small. We hope these additional experiments will solve your concerns.\n\n> Minor comments:\n> \n\nA: We will revise these typos in our next version.\n\n[Mangoubi et al.]  Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo", "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": "nZeoEJFyLP", "reviewer": "Reviewer_Y93M", "summary": "This paper presents a framework for accelerating the inference process in denoising diffusion probabilistic models (DDPMs) by optimizing the balance between the number and complexity of sampling subproblems.", "questions": "See above.", "limitations": "N/A", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed Reverse Transition Kernel (RTK) framework allows for a more efficient decomposition of the denoising diffusion process, enabling the use of advanced sampling algorithms like the Metropolis-Adjusted Langevin Algorithm (MALA) and Underdamped Langevin Dynamics (ULD). \n- By incorporating MALA and ULD, the paper leverages well-established acceleration techniques. This integration not only improves the convergence rates but also provides robust theoretical guarantees.\n- The authors provide theoretical convergence guarantees for these algorithms surpass current state-of-the-art rates for diffusion inference, supported by numerical experiments.", "weaknesses": "- While the paper focuses on diffusion models, it raises the question of whether the RTK framework can be applied to other generative models or machine learning tasks.\n- The paper lacks sufficient numerical evaluation to thoroughly demonstrate the effectiveness of the proposed method. Additionally, there is a lack of detailed comparison to other related approaches, making it difficult to fully assess the advantages and limitations of the RTK framework in practical settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive comments and helpful suggestions. We will response to your concerns point by point in the following.\n\n> Q1: While the paper focuses on diffusion models, it raises the question of whether the RTK framework can be applied to other generative models or machine learning tasks.\n> \n\nA good question! We should note that the main idea of RTK techniques is to replace the discretization of SDE/ODE with a sampling subproblem. Therefore, this framework can also be applied to some of the latest generative models, especially for flow matching [Lipman et al.]. Instead of defining the forward process as an SDE in diffusion models, flow matching defines the forward process as a distribution conditioning on the initial data distribution. Actually, for their optimal transport implementation, the forward process can be converted to the following SDE\n$$d x_t^\\to = \\frac{x^\\to_t}{t-1}d t + \\sqrt{\\frac{2t}{1-t}}d B_t$$\nequivalently. According to the exponential integrator, we can first calculate the forward transition kernel and then deduce the reverse transition kernel. By decomposing the reverse process of flow matching with a serious of strongly log-concave sampling subproblem and choosing proper inner samplers, I believe it is possible to accelerate the flow matching inference.\n\n> Q2: The paper lacks sufficient numerical evaluation to thoroughly demonstrate the effectiveness of the proposed method. Additionally, there is a lack of detailed comparison to other related approaches, making it difficult to fully assess the advantages and limitations of the RTK framework in practical settings.\n> \n\nA2: In this paper, we mainly focus on the theory (the RTK framework) about the convergence of diffusion inference process, and highlight how to design algorithms (RTK-ULD and RTK-MALA) to achieve faster convergence rate in theory. In the meanwhile, we have also provided some experimental results for the Gaussian mixture targets shown in Appendix. A, which justify the effectiveness and efficiency of the RTK based methods.\n\nWe also added some new experiments in our latest supplementary material of rebuttal. These experiments are conducted on another two Mixtures of Gaussians (MoG) and the MNIST dataset. Besides, we add an additional related approach, i.e., [Song et al.], for comparison. All experimental results validate that the RTK-based inference process outperforms DDPM in different settings. More details about the supplementary experiments can be found in the common response.\n\nWe will add this additional context to our paper in the next version.\n\n[Lipman et al.] Flow Matching for Generative Modeling.\n\n[Song et al.] Generative Modeling by Estimating Gradients of the Data Distribution.", "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": "n9cPkxgnaH", "reviewer": "Reviewer_sbHs", "summary": "Diffusion models rely on the use of the reverse SDE (or ODE) for sample generation, but the discrete-time simulation of the reverse SDE, when regarded as solving a sequence of subproblems, is potentially less efficient compared to the usage of better MCMC samplers for solving each subproblem. This paper suggests that given a fixed computational budget, employing MALA and ULD to simulate samples from a de-noised distribution allows for higher efficiency. The paper then analyzes the theoretical properties of 2 RTK samplers and showcase a more efficient use of computational expenses when compared to SDE based samplers.", "questions": "- The use of an underdamped dynamical system in diffusion modeling is not entirely a new idea: For instance, Dockhorn et al. suggest using a critically dampened Langevin diffusion as the forward process. While a critically dampened LD encodes a different evolution of marginal distributions, solving one discretization step of the backward SDE would be quite similar to the use of ULD in this paper. What do the authors think about the pros and cons of underdamping the forward process directly vs. your approach of only modifying the inference of the backward SDE? \n- Another advantage of SDE or RTK samplers, when compared the deterministic simulation using probability flow ODEs, is the addition of stochasticity that ameliorates possible imperfections in the score estimation. I think it is reasonable to assume that the adoption of RTK as a generator might further improve this issue. \n- The experiment figures in the appendix often show the failures of DDPM, but I'm not sure why there exists a dramatic difference between DDPM and others in figure 1 and 2. I had previously assumed that DDPM should be able to sample from the same data distribution, even though it might be computationally more expensive compared to the methods proposed. Can the authors provide some clarification about why the generated samples are so different (I would assume it's either inaccurate estimates of the scores, or the step size being too large)?\n\n[1] Dockhorn T, Vahdat A, Kreis K. Score-Based Generative Modeling with Critically-Damped Langevin Diffusion. In: International Conference on Learning Representations [Internet]. 2021.", "limitations": "- The paper suggests in the final section several limitations of the current paper. I agree with the characterization of limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper provides a compelling argument of accelerating the inference of reverse SDE, which seems more interesting than previous attempts to solve the same problem using specialized SDE solvers. \n- The paper also presents a valid argument in taking bigger step sizes in order to take advantage of Lipchitz continuity. \n- The paper can help bridge between diffusion modeling and MCMC, which can lead to interesting future work on further improving the sampling of de-noised distributions.", "weaknesses": "I like this paper overall -- the main weaknesses are mostly about how it is written, as there exist small mistakes or confounding statements. \n\n- The paper's usage of the word \"Gaussian process\" (e.g., in L. 125) seems confusing. I would assume Gaussian process mostly refers to infinite-dimensional Gaussian distribution in the space of functions, but finite discretization of the reverse SDEs simply yields a sequence of Gaussian conditional distributions. \n- The paper suggests numerical experiments in the abstract, but only includes the experiments in the appendix. \n- Should the paper clarify the use of the $ \\tilde{\\mathcal{O}} $ notation? It does not seem like a standard notation and has already been used in the abstract. \n- Minor: the paper uses \"closed\" as opposed to \"close\", e.g., in Algorithm 1 and Line 172, 176.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive comments and helpful suggestions. We will response to your concerns point by point in the following.\n\n> W1: (1). Writing Issues, (2). The paper suggests numerical experiments in the abstract, but only includes the experiments in the appendix. (3). Should the paper clarify the use of the  notation \\tilde{O}? Minor: the paper uses \"closed\" as opposed to \"close\".\n> \n\nAW1: (1). We will revise them in the next version. (2). We will move the experiments part to the main body of this paper. (3). We clarified the notation $\\tilde{O}$ in the notations paragraph of Section 2, i.e., Preliminaries. We will highlight it in the next version. Minor: We will revise them in the next version.\n\n> Q1: The use of an underdamped dynamical system in diffusion modeling is not entirely a new idea: For instance, Dockhorn et al. suggest using a critically dampened Langevin diffusion as the forward process. While a critically dampened LD encodes a different evolution of marginal distributions, solving one discretization step of the backward SDE would be quite similar to the use of ULD in this paper. What do the authors think about the pros and cons of underdamping the forward process directly vs. your approach of only modifying the inference of the backward SDE?\n> \n\nAQ1: Although there are some similarities in the use of ULD to accelerate the inference process of diffusion models, our work is orthogonal to [Dockhorn et al.] mentioned in your comments, and the motivations of these two papers are different. Specifically, [Dockhorn et al.] expected to change the way of **modeling the probability flow**, while our work aimed to **utilize well-trained scores** to accelerate the inference process. Compared with the reverse SDE, although we use a different Markov chain to generate the data, we do not require another training process as [Dockhorn et al.]. Under these conditions, we think it is good to combine our work, such as applying RTK in CLD-based probability flow, rather than comparison.\n\n> Q2: Another advantage of SDE or RTK samplers, when compared the deterministic simulation using probability flow ODEs, is the addition of stochasticity that ameliorates possible imperfections in the score estimation. I think it is reasonable to assume that the adoption of RTK as a generator might further improve this issue.\n> \n\nAQ2: This is a good observation. Actually, in order to achieve the same KL/TV convergence as SDE-based methods in theory, existing ODE-based methods require either an SDE corrector (DPOM and DPUM [Chen et al.]) or some strict assumptions (a small estimation error of energy Hessian [Li et al.]), which are shown in our Table. 1. To the best of our knowledge,  whether the pure ODE-based generator can achieve the same theoretical results as those for the SDE-based generator, under mild assumptions, is still an open question. We have known that (1) stochasticity is the only difference between the implementations of ODE and SDE-based methods and (2) the contraction of KL divergence highly depends on the diffusion term from a Fokker-Planck equation perspective. Therefore, it can be inferred that stochasticity could ameliorate possible imperfections in the score estimation.\n\n> Q3: The experiment figures in the appendix often show the failures of DDPM, but I'm not sure why there exists a dramatic difference between DDPM and others in figure 1 and 2. I had previously assumed that DDPM should be able to sample from the same data distribution, even though it might be computationally more expensive compared to the methods proposed. Can the authors provide some clarification about why the generated samples are so different (I would assume it's either inaccurate estimates of the scores, or the step size being too large)?\n> \n\nWe would like to clarify that, to remove the influence of the score estimation error on the convergence, we conduct the experiments on the synthetic data with exact scores, which can be explicitly calculated since the target distribution is a Gaussian mixture. Besides, we tune the hyper-parameters only under small NFE settings, which may require a relatively large step size. Such a large step size may magnify the differences between the generated samples. In the latest supplementary materials for the rebuttal, we added some new experiments. We especially compare RTK-based methods and DDPM on the real-world dataset MNIST, which demonstrates that RTK-based methods are better than DDPM even with score estimation errors in the same setting.", "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:
Thanks for your valuable suggestions. To supplement numerical experiments and demonstrate the benefits of our RTK-based methods in practice, we have conducted the following new experiments.

### Synthetic Data Experiments

---

We performed additional experiments on various Mixture of Gaussians (MoG) settings as described in the manuscript. Figures 1 and 2 in our latest rebuttal submission illustrate these new experiments. Specifically:

- **Figure 1**: Shows experiments with a spiral-shaped MoG as the ground truth distribution.
- **Figure 2**: Shows experiments with a chessboard-shaped MoG as the ground truth distribution.
- **Figure 3**: Shows Fréchet distance comparison among RTK-based methods and other baselines when the target distribution is set as the above two settings.

In these figures, we observed that our RTK-based methods achieve significantly better marginal accuracy when the number of function evaluations (NFE) is small. 

Additionally, we compared Annealed Langevin Dynamics (ALD) [Song et al.] with our RTK-based methods and found that ALD has a lower marginal accuracy, particularly when NFE is small. We hope these experimental results can address the concerns about “comparison to other related approaches” of Reviewer Y93M.

Furthermore, in Figure 3, we evaluated the methods using the Wasserstein Distance metric, which corresponds to Fréchet Inception Distance. Our results indicate that our RTK-based methods have a lower Wasserstein Distance compared to DDPM and ALD, especially when NFE is small. We hope these experimental results can address the concerns about the “comparison of FID” of Reviewer kQ8M.

### Real-World Data Experiments

---

For real-world data, we conducted experiments on the MNIST dataset, as shown in Figure 4. We first trained a score model following the typical variance-preserving noise schedule and then compared different sampling methods using the Fréchet Inception Distance (FID) evaluation criterion:

- **Figure 4(a)**: Demonstrates that the RTK-based methods achieve better FID scores than DDPM, particularly when NFE is small.
- **Figures 4(b-d)**: Illustrate that the RTK-based methods generate images of higher quality than DDPM when NFE is small.

We hope these supplementary experiments address your concerns and provide further evidence of the effectiveness of our RTK-based methods.

Meta-review: This paper notes that MCMC methods can be used to produce consistent simulations from SDEs, and then develops this idea in detail for the specific SDE that must be solved to simulate the reverse process in denoising diffusion models.  The paper is theoretical, and the main result is an analysis of how to select the discrete times at which the SDE is discretised in order that the sampling problem of moving from one state to the next becomes convex, and therefore very amenable to MCMC.  Sufficient conditions are presented for the MALA and ULA MCMC algorithms, but the general framework shows how other MCMC methods could also be considered.  As with all large scale machine learning, one wonders whether the errors in simulating SDEs for large scale denoising diffusion models provides some form of useful implicit regularisation, but small experiments in this paper suggest this may not be the case (meaning that more accurate solution of the SDE could be useful).  One also wonders whether the use of more complicated MCMC algorithms in place of simple Euler-Maruyama is worth the additional effort, but small experiments suggest the number of score function evaluations is not greatly increased when the proposed method is used.  A caveat with these experiments is that the baseline implementation of denoising diffusion models seems sub-optimal, as the authors admit in their response, and this may have exaggerated the advantages of the proposed method.  Overall this paper is well-written (modulo numerous grammatical errors, e.g. closed instead of close in Algorithm 1), with substantial theory and weakly convincing empirical evidence.  I believe the framework will be of interest to a wide section of the NeurIPS community, encompassing both diffusion modellers and MCMC algorithm developers.  I recommend that the paper is accepted.
Decision: Accept (spotlight)