Reverse Diffusion Monte Carlo
Authors: Xunpeng Huang
Hanze Dong
Yifan HAO
Yian Ma
Tong Zhang
Venue: ICLR 2024 poster (2024)
Keywords: posterior Sampling
multi-modal sampling
diffusion process
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)

Abstract: We propose a Monte Carlo sampler from the reverse diffusion process. Unlike the practice of diffusion models, where the intermediary updates---the score functions---are learned with a neural network, we transform the score matching problem into a mean estimation one.
By estimating the means of the regularized posterior distributions, we derive a novel Monte Carlo sampling algorithm called reverse diffusion Monte Carlo (rdMC), which is distinct from the Markov chain Monte Carlo (MCMC) methods. We determine the sample size from the error tolerance and the properties of the posterior distribution to yield an algorithm that can approximately sample the target distribution with any desired accuracy. Additionally, we demonstrate and prove under suitable conditions that sampling with rdMC can be significantly faster than that with MCMC.  For multi-modal target distributions such as those in Gaussian mixture models, rdMC greatly improves over the Langevin-style MCMC sampling methods both theoretically and in practice. The proposed rdMC method offers a new perspective and solution beyond classical MCMC algorithms for the challenging complex distributions.

Published as a conference paper at ICLR 2024
REVERSE DIFFUSION MONTE CARLO
Xunpeng Huang"!
Hanze Dong"
Yifan Hao
Yi-An Ma²
Tong Zhang1
f The Hong Kong University of Science and Technology
$ Salesforce Al Research
1 University of California, San Diego
4 University of Illinois Urbana- Chaaaa-Champaign
ABSTRACT
We propose a Monte Carlo sampler from the reverse diffusion process. Un- like the practice of diffusion models, where the intermediary updates- the score functions-are are learned with a neural network, we transform the score matching problem into mean estimation one. By estimating the means of the regularized posterior distributions, we derive a novel Monte Carlo sampling algorithm called reverse diffusion Monte Carlo (rdMC), which is distinct from the Markov chain Monte Carlo (MCMC) methods. We determine the sample size from the error tolerance and the properties of the posterior distribution to yield an algorithm that can approximately sample the target distribution with any desired accuracy. Ad- ditionally, we demonstrate and prove under suitable conditions that sampling with rdMC can be significantly faster than that with MCMC. For modii- target distributions such as those in Gaussian mixture models, rdMC greatly improves over the Langevin-style MCMC sampling methods both theoretically and in prac- tice. The proposed rdMC method offers a new perspective and solution beyond classical MCMC algorithms for the challenging complex distributions.
INTRODUCTION
Recent success of diffusion models has shown great promise for the the reverse diffusion processes in generating samples from a complex distribution (Song et al., 2020 Rombach et al,, (022). In the existing line of works, one is given samples from the target distribution and aims to generate more samples from the same target. One would diffuse the target distribution into a standard normal one, and use score matching to learn the transitions between the consecutive intermediary distribu- tions (Ho et al. 2220; Song et al. (2020). Reversing the learned diffusion process leads us back to the target distribution. The benefit the reverse diffusion process lies the efficiency conver- gence from any complex distribution to normal one (Chen et al.] 2022a Lee et al. 2023). For example, diffusing a target multi-modal distribution into normal one is not harder than diffusing single mode. Backtracking the process from the normal distribution directly yields the desired multi-modal target. If one instead adopts the forward diffusion process from a normal distribution to the multi-modal one, there is the classical challenge of mixing among the modes, as illustrated in Figure I
This observation motivates us to ask:
Can we create an efficient, general purpose Monte Carlo sampler from reverse diffusion processes?
For Monte Carlo sampling, while we have access to an unnormalized density function p. (z) xx exp( (xp(-f.(z) (z)), samples from the target distribution are unavailable (Neal 1993) Jerrum & Sinclair 1996 Robert et al. 1999). As a result, we need a different and yet efficient method of score esti- mation to perform the reverse SDE. This leads to the first contribution of this paper. We leverage the fact that the diffusion process from our target distribution p. towards standard normal one poe is an Uhieenbeehh (OU) process, which admits explicit solutions. We thereby transform the score matching problem into non- paraamametticc mean estimation one, without training a parameter- ized diffusion model. We name this new algorithm reverse diffusion Monte Carlo (RDMC).
Equull contribution. Random order.

---

Published as a conference paper at ICLR 2024
Figure I: Langevin dynamics (first row) versus reverse SDE (second row). The first and second rows depict the intermediate states of the Langevin algorithm and the reverse SDE, respectively, illustrating the transition from standard normal Po Gaussian mixture p.. It be observed that due to the local nature of the information contained in V pi,,,, the Langevin algorithm tends get stuck in modes close the initializations. In contrast, the reverse SDE excels at transporting particles to different modes proportional to the target densities.
To implement RDMC and solve the aforementioned mean estimation problem, we propose two approaches. One is to sample from a normal distribution ( pr-determined at each time / by the tran- sition kernel of the OU process- compute the mean estimates weighted by the target p.. This approach translates all the computational challenge to the sample complexity in the importance sam- pling estimator. The iteration complexity required to achieve an overall TV accuracy is O -2,, under minimal assumptions. Another approach is to use Unadjusted Langevin Algorithm (ULA) to generate samples from the product distribution of the target density p. and the normal one pr. This approach greatly reduces sample complexity in high dimensions. and yet is a better conditioned al- gorithm than ULA over p. due to the multiplication of the normal distribution. we find that a combination of the two approaches excels at distributions with multiple modes.
our experiments,
We then analyze the efficacy and efficiency of our RDMC method. We study the benefits of the re- verse diffusion approach for both multi-modal distributions and high dimensional heavy-tail distri- butions that breaks the isoperimetric properties (Gross) 1975 Poincare 1890) Vempala & Wibisono, 2019). In multi-modal distributions, the Langevin algorithm based MCMC approaches suffer from an exponential cost for the need of barrier crossing, which makes mixing time extremely long. The RDMC approach can circumvent the hurdle and solve the problem. For nigh-dimensional heavy- tail distributions, our RDMC method circumvents the often-required isoperimetric properties of the target distributions, thereby avoiding the curse of dimensionality.
Contributions. We propose a non-parametric sampling algorithm that leverages the reverse SDE of the OU process. Our proposed approach involves estimating the score function by a mean estimation sub-problem for posteriors, enabling the efficient generation of samples through the reverse SDE. We focus on the complexity of the sub-problems and establish the convergence of our algorithm. We found that our approach effectively tackles sampling tasks with ill-conditioned log Sobolee con- stants. For example, it excels in challenging scenarios characterized by multi-modal and long-tailed distributions. Our analysis sheds light on the varying complexity of the sub- sub-problems at different time points, providing fresh perspective for revisiting score estimation diffusion-bass based models.
2 PRELIMINARIES
In this section, we begin by introducing related work from the perspectives of Markov Chain Monte Carlo (MCMC) and diffusion models, and discuss the connection between these works and the present paper. Next, we provide a notation for the reverse process of diffusion models, which specifies the stochastic differential equation (SDE) that particles follow in RDMC.
We first introduce the related works as below.
Langevin-based MCMC. The mainstream gradient- gradient-based sampling algorithms are mainly based on the continuous Langevin dynamics (LD) for sampling from a target distribution p. x exp(-f.). The Unadjusted Langevin Algorithm (ULA) discretizes L.D using the Fuler-Maruyama scheme and
2

---

Published as a conference paper at ICLR 2024
obtains biased stationary distribution. Due to its simplicity, ULA is widely used in machine learn- ing. Its convergence has been investigated for different criteria, including Total Variation (TV)
distance, Wasserstein distances (Durmus & Moulines) 2019), and Dallback-Leiblee (KL) divergence
[Dalalyan 2017] Cheng & Bartlen 2018: Ma et al., 2019 Freund et al.] 2022). in different set- tings, such as strongly log-concave, -og-Sobolev inequality (LSI) (Vempala & Wibisono 2019). and Poincaré inequality (PI) (Chewi et al. 2021). Several works have achieved acceleration convergence for ULA by decreasing the discretization error with higher-order SDE, e.g., underdamped Langevin dynamics (Cheng et al., 2018] Ma et al., 2021 Mou et al. 2021). and aligning the discretized sta- Langevin algorithm (Dwivedi et al.]
tionary distribution to the target p., e.g.. Metropolis-adjute
2018) and proximal samplers (Lee et al., [202bb Chen et al. 2022b by Altschuler & Chewi [023)
Liu & Wang (206)); Dong et al. (2023) also attempt to perform sampling tasks with deterministic algorithms whose limiting ODE is derived from the Langevin dynamics.
Regarding the convergence guarantees, most of these works have landscape assumptions for the larget distribution pe, e.g., strong log-concavity, LSI, PL. For more general distributions, [Erdogdu & Hosseinzadeh (202T) and Mousavi-Hosseimi et al. (2023) consider KL convergence in modified LSI and weak PI. These extensions allow for slower tail- growth of negative log-density f.. compared to the quadratic or even linear case. Although these works extend ULA to more general distributions, the computational burden of ill-conditioned isoperimetry still exists, e-g., exponentially dependent on the dimension (Raginsky et al., (017). In this paper, we introduce another SDE to guide the sampling algorithm, which mon-Markovian and ineeiihhooggeouuu.....m Our algorithm discretizes such an SDE and can reduce the isoperimetric and dimension dependence wrt TV convergence.
Diffusion Models and Stochastic Localization. In recent years, diffusion models have gained sig- nificant attention due to their ability to generate high-quality samples (Ho et al. 2020: Rombach al. 2022). The core idea of diffusion models is parameterize the score, i.e., the gradient of the log-density, during the entire forward OU process from the target distribution p.. In this condition, the reverse SDE associated with the inference process diffusion models to perform unnormal- ized sampling for intricate target distributions. Apart from conventional MCMC trajectories, the most desirable property of this process is that, if the score function can be well approximated, it can sample from general distribution Chen et al. (0222)); Lee et al. (2022) 2023 This implies the reverse SDE has a lower dependency on the isoperimetric requirement for the target distribution, which inspires the designs of new sampling algorithms. On the other hand, stochastic localiza- tion framework (Eldan) 2013) 2020) 2022] [El Alaoui et al. 2022] Montanari] (023) formalizes the general reverse diffusion and discusses the relationship with current diffusion models. Along this line, Montanari & Wu (2023) consider the unnormalized sampling for the symmetric spiked model.
However, for the properties of the general unnormalized sampling, the investigation is limited.
This work employs the backward path of diffusion models to design sampling strategy which we can prove be more effective than the forward path of Langevin algorithm under suitable condi- tions. Several other recent studies (Vargas et al., 2023a Berner et al. 2022, ZZhang et al., 2023] Vargas et al., 2023c b) have also utilized the diffusion path in their posterior samplers. Instead of the closed form MC sampling approach, the above works learns an approximate score function via parametrized model, following the standard practice of the diffusion generative models. The result- ing approximate distribution following the backward diffusion path is akin to the ones obtained from variational inference, and contains errors that depend on the expressiveness of the parametric models for the score functions. In addition, the convergence of the sampling process using such approach depends on the generalization error of learned score functions (Tzen & Raginsky 2019) (See Ap- pendix for more details). It remains open how to bound sample complexity of such approaches, due to the need for bounding the error of the learned score function along the entire trajectory.
In contrast, RDMC proposed in this paper can be directly analyzed. Specifically, our our algorithm draws samples from the unnormalized distribution without training data and the algorithm is designed to avoid learning based score function estimation. We are interested in the comparisons between RDMC and conventional MCMC algorithms. Thus, we analyze the complexity to estimate the score by drawing samples from the posterior distribution and found that our proposed algorithm is much more efficient in certain cases when the log- log-looolev constant of the target distribution is small.
Reverse SDE in Diffusion Models. In this part, we introduce the notations and formulation of the reverse SDE associated with the inference process in diffusion models, which will also be commonly used in the following sections. We begin with an OU process starting from p. formulated as
3

---

Published as a conference paper at ICLR 2024
dæ v,dt + v2dB,, 20 ~ Po e e
where (Bz) is Brownian motion and Po is assigned p.- This is similar to the forward process of diffusion models (Song et al. 2020) whose stationary distribution is N (0, I) and we can track the random variable at time i with density function Pt-
According to Cattiaux et al. (202I), under mild conditions in the following forward process dæ, = (x, )tt + ,,d the reverse process also admits an SDE description. If we fix the terminal time T > and set Ct ør-t, for t E [0, T], the process (E))) satisfies the SDE dæ, ddt
where the reverse drift satisfies the relation by = 2V Pt: 2t ~ Pt. In this condition, the reverse process of Eq. ①1 is as dă, = (#: + 2V In pr ( dt + v2dB, Et ~ pt- Thus, the score function V In -t is obtained, the reverse SDE induce sampling algorithm.
Discretization and realization of the reverse process. To numerically solve the previous SDE, suppose k [1/n] for any / E [0, 7), we approximate the score function A In pr-+ with eú for t E kk. (k: + 1)m)- This modification results new SDE, given by
dæ (#; + on (āxn)) dt + v2dB,, tE [km, (k + 1)m]
Specifically, when & = set Tp be sampled from Po. which can approximate pr. To find the closed form of the solution by setting an auxiliary random variable as r; (#,, 1) == &z,e we have
dr, (8., = (rr; Ør,
0'r; @
dt Ør. 2ddB
(va.s - xc..) +
aān.
dt + 2e 'B.
where the equalities are derived by the Itô's Lemma. Then, we set the initial value ro (8t, 0) L1.i- and integral on both sides of the equation. We have
Ltts c² + (e" - u + (c - Ia)
For the specific construction of ey to approximate the score, we defer it to Section 3
THE REVERSE DIFFUSION MONTE CARLO APPROACH
we introduce an estimator U1: V ( to implement the reverse diffusion. This section is dedicated exploring viable estimators and the benefits of the reverse diffusion process. We found that we can reformulate the score as an expectation with the transition kernel of the forward OU process. We also derive the intuition that RDMC can reduce the isoperimet- ric dependence the target distribution compared with conventional Langevin algorithm. Lastly, introduce the detailed implementation of RDMC in real practice with different score estimators.
As shown in SDE (2)
3.1 SCORE FUNCTION IS THE EXPECTATION OF THE POSTERIOR
V In Pt do not have analytic form. However, forward process is OU process (SDE whose
We start with the formulation of V (x). In general SDEs, the score functions
transition kernel is given as Pso(#)20) (2 (1-e-2t) 21)) -4/2 exp
m
2g
Such condi-
tional density presents the probability of obtaining He = x given To in SDE T Note that
the property to derive other score formulations. Bayes' theorem demonstrates that the score can be reformulated as an expectation by the following Lemma.
P=( Ppo (z) ar)), we
Lemma 1. Assume that Eq. defines the forward process. The score function can be rewritten as
(T-1) 200
Va In (()) = Emo-or-r(1e)
(1 c 2(T-
z - 1T- -m
( x exp
-f((20)
2 2-2(T-
4

---

Published as a conference paper at ICLR 2024
Algorithm RDMC: reverse diffusion Monte Carlo
Input: Initial particle To sampled from po. Terminal time T, Step size 77, n'. Sample size n.
2: for k 0 to [T/n]] - do
3: Set Uj = 0:
4: Create Monte Carlo samples to estimate
Økn (T' km)
where q o exp (-f. [.((() Reg (x 1e)) km))ael"
Ok Ex-er
(i-e 2:2 kn)
2(2-c 212 ken)
5: 2 [k+1))n e Dnn + (e" 1) ok +
where & is sampled from /N (0, (e.2 - -1) La).
6: end for
7: Return: #LT/n|0
0.3
t= 0.01
constant
Dedersity
0.3
0g ge-ensity
t= 0.4
10-4
0.2
43
10-17
0.1
t-
0.1
0.0
0.0
Figure 2: Illstrations of Pt. and their log-Sobolet (LSI) constants. The target distribution is a Gaussian mixture. We choose (-(1 0) for illustration. As increases, the modes of p. collapse to zero rapidly, corresponding to improving LSI constant. For qr. the barrier height of qi remains small, resulting in relatively large LSI constant as long as O1). Thus initializing with pr and performing RDMC reduces computation complexity for multi-modal p..
The proof of Lemma presented in Appendix C.I For any / >> O, we observe that log (r-t incorporates additional quadratic term. In scenarios where p. adheres to the log-Sobolev inequal- ity (LSI), this term enhances şr-i's 's log-Soboley (LSI) constant, thereby accelerating convergence. Conversely, with heavy-tailed p. (where f. growth is slower than quadratic function), the extra term retains quadratic growth, yielding sub-Gaussian tails and log-Sobolev properties. Notably, as t approaches T, the quadratic component becomes predominant, rendering -r strongly log-concave and facilitating sampling. In summary, every -r-, exhibits a larger LSI constant than p.. As in- creases, this constant grows, ultimately leading qr towards strong convexity. Consequently, this provides a sequence of distributions with LSI constants surpassing those of p., enabling efficient score estimation for V In pr-
From Lemma [] the expectation formula of (--x(- can be obtained by empirical mean estima- tor with sufficient samples from q--x(- Thus, the gradient complexity required in this sam- pling subproblem becomes the bottleneck of our algorithm. Suppose (+) is samples drawn from or -ry when Ti.y x for any x E Rdd, the construction of tb (2) in Eq. (2) can be presented as
uk(x)) Thk En ok (x) where o (x) = 2 --((T-n0)) -1 ( -T kn) (1) -x))
-x) (5)
3.2 REVERSE SDE VS LANGEVIN DYNAMICS: INTUITION
From Figure I we observe that the RDMC method deviates significantly from the conventional gradient-based MCMC techniques, such as Langevin dynamics. It visualizes the paths from Gaus- sian distribution to a mixture of Gaussian distributions. can be observed that Langevin dynamics, being solely driven by the gradient information of the target density p., tends to get trapped in lo- cal regions, resulting in uneven sampling the mixture of Gaussian distribution. More precisely,
p. admits small LSI constant due to the separation of the modes (Ma et al.) 2019 Schlichting 2019 Menz & Schlichting 2014). Consequently, the convergence of conventional MCMC methods becomes notably challenging in such scenarios (Tosh & Dasgupta 2014).
To better demonstrate the effect of our proposed SDE, we compute the LSI constant estimates for Due the shrinkage property of the forward process, the LSI constant of pe
1-d case in Figure 2
5

---

Published as a conference paper at ICLR 2024
can be exponentially better than the original one. Meanwhile, a O1), the LSI constant of qu is also well-behaved, In our algorithm, a well-conditioned LSI constant for both pr and qr reduces the computation overhead. Thus, can choose a intermediate T to connect those local modes and perform reverse SDE towards p.- RDMC can distribute samples more evenly across different modes and enjoy faster convergence in those challenging cases. Moreover, if the growth rate of log P. is slower than the quadratic fuunction (heavy tail), we can choose a large I and use Poo to estimate pr. Then, all - log q: have quadratic growth, which implies log-Sobolev property. These intuitions also explain why diffusion models excel in modeling complex distributions in high- dimeesiionn spaces. We will provide the quantitative explanation in Section 4
3.3 ALGORITHMM FOR SCORE ESTIMATION WITH (--x
According to the expectation form of scores shown in Lemma I detailed reverse sampling algo- rithm can be naturally proposed in Algorithm|] | Specifically, can be summarized as the following steps: (1) choose proper T' and Po such that pr Pp. This step can be done by either ño Poo for large T or performing the ULA for Pr (Algorithm [J in Appendix); (2) sample from a distribution that approximate qr- (Step 4 of Algorithm D: (3) follow Pe with the approximated qr-r samples (Step of Algorithm I: (4) repeat until = T. After (4), we can also perform Langevin algorithm to fine-tune the steps when the gradient complexity limit is not reached.
The key of implementing Algorithm T is to estimate the scores V Pr- via Step with samples from 9r- In what follows, we discuss the implementation that combines the importance weight sampling with the adjusted Langevin algorithm (ULA).
Importance weighted score estimator. We first consider importance sampling approach for esti- mating the score V In p1 From Eq. (4), we know that the key is to estimate:
(T-T))
T (T-(Ttt) 2o 1.((0)
V In (xx Bey (11))
Emg-pr-x(len
(1 - 2
Z
(1 e 2-2((-0)
-|--- (T "moll"
Note that sampling from Pr takes negligible computation resource. The main challenge is the sample complexity of estimating the two expectations.
and Z. = (mo-pr- lexp( fo (xo))], where ( exp
((1---2r-11)
Since (x0o(() is Gaussian with variance of = 2( - we know that as long as 2- (T Umo (=p(-f+(0o)) is G-Lipschitz, the sample complexity scales as N = Ō -
(1-6-2(7-1)
for the resulting errors of the two mean estimators to be less than e (Wainwright 2019). However, the sample size required of the importance sampling method to achieve an overall small error is known to scale exponentially with the KI. divergence between PT and gr- (Chatterjee & Diaco- nis, 2018). which can depend on the dimension. In our current formulation. this is due to the fact that the true denominator Z, = Eno-pr---(ee (e- make the overall score estimation error small, the error tolerance and in turn the sample size required for estimating Z. can scale exponentially with the dimension.
(xxo) can be as little as exp( -d). As result, to
ULA score estimator. An alternative score estimator considers that the mean of the underly- ing distribution ( (r) of these samples needs to sufficiently approach (--1(- which can be achieved by closing the gap of KL. divergence or Wasserstein distance between (-Ix) and (r-)(- Since the additional quadratic term shown in Eq. 4 helps improve a quadratic tail growth for (-1x(- which implies the establishment of the isoperimetric condition. We expect the convergence can be achieved by performing the ULA on a sampling subproblem whose target distribution is (r))). We provide the detailed implementation in Algorithm 2
ULA score estimator with importance sampling initialization. Inspired by the previous esti- mators, we can combine the importance sampling approach with the ULA. In particular, we first implement the importance sampling method to form a rough score estimator. We then perform ULA at the mean estimator and obtain refined accurate score estimate. Via this combination, we are able to efficiently obtain accurate score estimation by virtue of the ULA algorithm when t is close to T. When is close to 0, are able quickly obtain rough score estimates via the importance sampling approach. We discover empirically that this combination generally perform well when t interpolates the two regimes (Figure in Section 4

---

Published as a conference paper at ICLR 2024
Algorithm 2 ULA inner-loop for the gr q-(((a)) sampler (Step of Algorithm
1: Input: Condition and time i, Sample size Initial particles {0));= Iters K, Step size
)
2: for = 1 to K do
3: for 1 to n do
00'00"0p_111 + 2nSE, where E ~ N (0,
4: 4 = =
(zi
1-e-
5: end for
6:
end for Return: { )
7:
ANALYSES AND EXAMPLES OF THE RDMC APPROACH
In this section, analyze the overall complexity of the RDMC via ULA inner loop estimation. Since the complexity of the importance sampling estimate is discussed in Section 3.3 we only consider Algorithm ] with direct ULA sampling of 9--x(- rather than the smart importance sampling initialization to make our analysis clear.
To provide the analysis of the convergence of RDMC, make the following assumptions.
[A1] For all t O, the score v In is L-Lipschitz.
[A2] The second moment of the target distribution p. is upper bounded, i.e., Ep. [I-II]]] m².
These assumptions are standard diffusion analysis to guarantee the convergence to the target dis- tribution (Chen et al. 2022a). Specifically, Assumption [A1] governs the smoothness characteristics of the forward process, which ensure the fcasibility of numerical discretization methods used for approximating the solution of continuous SDE. In addition, Assumption [Ag] introduces essential constraints on the moments of the target distribution. These constraints effectively prevent an ex- cessive accumulation of probability mass in the tail region, thereby ensuring a more balanced and well-distributed target distribution.
4.1 OUTER LOOP COMPLEXITY
According to Algorithm M the overall gradient complexity depends on the number of outer loops k, as well as the complexity to achieve accurate score estimations (Line 5 in Algorithm [T] When the score is well-approximated and satisfies Epr-.. [10x - Vinpr- pr s e², the overall error
in TV distance, (rv(p., (T), can be made ÕEe) by choosing small 17. Under this condition, the number outer loops satisfies k = l0L2de 2). which shares the same complexity as that in diffu- sion analysis (Chen al. 2022a Lee al., 2022 2023). Such complexity of the score estimation oracles independent of the log- Sobolee (LSI) constant of the target density px, which means that the isoperimetric dependence of RDMC is dominated by the subproblem of sampling from QT-t- Specifically, the following theorem demonstrates the conditions for achieving Dpv.P.,rr)
O(c)-
Theorem 1. For any > O, assume that DKL lipo) e for some T >> 0, P as suggested in Algorithm r Ci(d + m If the OU process induced by p. satisfies Assumption [A,]
[2 and Qr ky satisfies the log- log-Sobolev inequality (LSI) with constant μ4 (km) S T). We set
nk = 64Td 282-1 Ex 2-13, 1 -- 22
(6)
where ug is the number of samples to estimate the score, and Ey is the KL error tolerence for the inner loop. With probability at least - 5, Algorithm converges in TV distance with Õ(e) error. Therefore, the key points for the convergence of RDMC can be summarized as
The LSI of target distributions of sampling subproblems, i.c., -r is maintained.
*
The initialization of the reverse process Pu is sufficiently close to
4.2 OVERALL COMPUTATION COMPLEXITY
In this section, we consider the overall computation complexity of RDMC. Note that the LSI con- stants of qr-kk depend on the properties of p.. As result consider specific assumptions

---

Published as a conference paper at ICLR 2024
that bound the LSI constants for 9ry In particular, we demonstrate the benefits of using -r for targets P. with infinite or exponentially large LSI constants. Compared with ULA, RDMC improves the gradient complexity, due to the improved LSI constant of kr over that of p. in finite T. Even for heavy-tailed p. that does not satisfy the Poincaré inequality, target distributions of sampling subproblems, i.e., -ry can still preserve the LSII property, which helps RDMC to alleviate the exponential dimension dependence of gradient complexity for achieving TV distance convergence.
Specifically, Section 4.2.1 consider the case that the LSI constant of p. depend on the radius R exponentially, which can usually be found in mixture models. Our proposed RDMC can reduce the exponent by a factor. Section 4.2.2 consider the case that p. is not LSI, but RDMC can create an LSI subproblem sequence which makes the dimension dependency polynomial.
We first provide an estimate for the LSI constant of qu under general Lipschitzness assumption [A
Lemma 2. Under [Ai] the LSI constant for qe in the forward OU process is 2(1-e-21) when 0 S t S In (1 (1+ ). This estimation indicate that when quadratic term dominate the len-it of Ts. the log-Sobolev property is well- gell-guaranteed.
4.2.1 IMPROVING THE LSI CONSTANT DEPENDENCE FOR MIXTURE MODELS
Apart from Assumption A A2
we study the case where p. satisfies the following assumption:
[Ag] There exists R > O, such that (xx is m-strongly convex when || 2 R.
In this case, the target density P. admits LSI constant which scales exponentially with the radius m of the region of nonconvexity R, ie.. 2 exp(- 1 1 as shown in (Ma et al. 2019). This implies that if we draw samples from p. with ULA, the gradient complexity will have exponential depen- dency with respect to R2_ However, in RDMC with suitable choices of T = O(log R) and po: the exponential dependency on R is removed, which is bottleneck for mixture models.
In the Proposition 1 below, we select values of T and fo to achieve the desired level of accuracy. Notably, Lemma 2 suggest that can choose O(1) termination time make the LSI constant of well-behehaved and pr is much simpler than po- That is to say, RDMC can exhibit lower isoperimetric dependency compared to conventional MCMC techniques. Thus, We find that the overall computation complexity of RDMC reduces the dependency on R.
We estimate pr with po by ULA, where the iterations wrt LSI constant is St (m exp - -2T)). For any 0 and T S ] In (1 ).,) the Algorithm 7 from Po to target distribution convergence with probability at least 1 - ô and total gradient complexity 52 (poly(e, d)) independent of R. Example: Gaussian Mixture Model. We consider an example that
Proposition 1. Assume that the OU process induced by p. satisfies A
A
(=) exp
exp
wl1
y 1.
The LSI constant is O(c D(e-Cooll Collvll) Ma al. corresponding to the complexity of the target distribution. Tosh & Dasgupta (2014) prove that the lower bound iteration complexity by MCMC-based algorithm to sample from the Gaussian mixture scales exponentially with the squared distance ||y|l between the two modes: M(exp(llv (xxp((l/)) [|lyll////// /8)). Note that RDMC not a type of conventional MCMC. With importance sampling score estimator, the Ō(c=2) iteration complexity and Ō(c samples at each step, the TV distance converges with Ōe)) error (Appendix B
2019; Schlichting, 2019 Menz Schlichting 2014
The computation overhead of the outer-loop process does not depend on y. For the inner-loop score estimation we can choose T = 2 log to make the LSI constant of to be 0(1). We can perform ULA to initialize pr, which reduces the barrier between modes significantly. Specifically, the LSI constant of pr is OCo -- vl²), which improves the dependence on ||y|| by 2T factor. Since this factor is the exponent, the reduction is exponential.
Figure 3 is a demonstration for this example. We choose different r to represent the change of It in [Aa] We compare the convergence of Langevin Monte Carlo (LMC), Underdamped LMC (ULMC) and RDMC in terms of gradient complexity. As r increases, we find that LMC fails to converge within a limited time. ULMC, with the introduction of velocity, can alleviate this situation. Notably, our algorithm can still ensure fast mixing for large r. The inner loop is initialized with importance sampling mean estimator. parameeas and more results provided in Appendix F
8

---

Published as a conference paper at ICLR 2024
-3
2.0
NNC
1.5
1.0
1.0
KNG
Www
0.
0.0
0.0
comp
complentty
comproity
F 0.5
1" 1.0
P' = 2.0
Figure 3: Maximum Mean Discrepancy (MMD) convergence of LMC, ULMC, RDMC. First row
shows different target distributions, with increasing mode separation and barrier heights, leading to reduced log- Sobolev (LSI) constants. Second row displays the algorithms' convergence, revealing RDMC's pronounced advantage convergence compared to ULMC/LMC, especially for large
4.2.2 IMPROVING THE DIMENSION DEPENDENCE IN HEAVY-TAILED TARGET DISTRIBUTIONS
In this subsection, study the case where p. satisfies Assumption
Ag and
[A,] For any > O, we can find some R(r) satisfying fx) +r | is convex for ||||| 2 R(r). Without loss generality, we suppose R(r) = CR// r" for some n >> 0, CR > 0.
Assumption A4 can be considered of the negative log-density f. to be slower than quadratic functions. This encompasses certain target distributions that fall outside the constraints of LSI and PI. Furthermore, given that the additional quadratic term present in Eq. 4 dominates the tail, QT -kn satisfies LSI for all >> O.
soft version of [A]] Specifically, it permits the tail growth
Lemma 3. Under [A1]
[
the LSI constant for qe in the forward OU process is 6(1-e-20)
16-3L--
21
for any 2 0. The tail property guarantees a uniform LSI constant.
The uniform bound on the LSI constant enables us to estimate the score for any p:. We can consider cases that are free from the constraints on the properties of pr and let T be sufficiently large. By setting T OIn 1/e) level, we can approximate pr with Pro - stationary distribution of forward process. Furthermore, since ii are log-Sobolev, we can perform RDMC to sample from heavy-tailed p" in the absence of a log- Sobolev inequality. The explicit computational complexity of RDMC, needed to converge to any specified accuracy, is detailed in the subsequent proposition.
Proposition Assume that the target distribution p. satisfies Assumption [A.] [Aa] and [As] We take Poe. to be Po. For any > 0, by performing Algorithm 7 with ULA inner loop and hyper- parameters in Theorem 1 with probability at least 1 5, we have Drv (fr,p.) S Ö(e) with Ω (168-11n-833 exp (E (116)) gradient complexity.
Example: Potentials with Sub-Linear Tails. We consider an example that
(z) exp exp (-(1+=1)++1) +1)²+ where E (0,0.5).
Lemma 5 demonstrates that this pa satisfies Assumption [A,] with (2 2a) < 1. Moreover, these target distributions with sub-linear tails also satisfy weak Poincare incquality (wPI) introduced in MMusavi- vergence in TV distance is proven to be (+3)).++3 Compared with this result, the complexity of RDMC shown in Proposition has a lower dimension dependence when < 4/15.
al. (202)). in which the dimension dependence of ULA to achieve the con-
Conclusion. This paper presents a novel sampling algorithm based on the reverse SDE of the OU process. The algorithm efficiently generates samples by utilizing the mean estimation of a sub- problem to estimate the score function. demonstrates convergence in terms total variation distance and proves efficacy in general sampling tasks with or without isoperimetric conditions. The algorithm exhibits lower isoperimetric dependency compared to conventional MCMC techniques, making it well-suited for multi-modal and nigh-dimensional challenging sampling. The analysis provides insights into the complexity of score estimation within the OU process, given the condi- tional posterior distribution.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
The research is partially supported by the NSF awards: SCALE MoDL-2134209, CCF-21 (TILOS). It is also supported in part by the DARPA AIE program, the U.S. Department of Energy, Office of Science, the Facebook Research Award, as well as DDC-RFA-FFT-2--00 from the CDC's Center for Forecasting and Outbreak Analyties.
REFERENCES
Jason M Altschuler and Sinho Chewi. Faster high-accuracy log-coneave sampling via algorithmic warm starts. arXiv preprint 10X1v:2302.10249, 2023.
Dominique Bakry, Ivan Gentil, Michel Ledoux, et al. Analysis and geometry of Markov diffusion operators, volume 103. Springer, 2014.
Julius Berner, Lorenz Richter, and Karen Ullrich. An optimal control perspective on diffusion-based generative modeling. arXiv preprint urXiv:221..03364 2022.
Patrick Cattiaux, Giovanni Conforti, Ivan Gentil, and Christian Léonard. Time reversal of diffusion processes under finite entropy condition. arXiv preprint arXiv:2104.077000 2021.
Djalil Chafaï. Entropies, convexity, and functional inequalities, on sphi-entropies and \phi-sobolev inequalities. Journal of Mathematics of Kyoto University, 44(2):325-363, 2004.
Sourav Chatterjee and Persi Diaconis. The sample size required in importance sampling. Annals of Applied Probability, 28(2), 2018.
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: freen-friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learming, pp. 4735-4763, PMLR, 2023.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint wrxiv:2209.11215. 2022a.
Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for a proximal algorithm for sampling. In Conference on Learning Theory, pp. 2984-3014, PMLR, 2022b.
Xiang Cheng and Peter Bartlett. Convergence of langevin meme in kl-divergence. In Algorithmic Learning Theory, pp. 186-211. PMLR, 2018.
Xiang Cheng, Niladri S Chatterji, Peter L Bartlett, and Michael Jordan. Underdamped langevin meme: non-asymptotic analysis. In Conference on learning theory, pp. 300-323. PMLR, 2018.
Sinho Chewi, Murat A Erdogdu, Mufan Bill Li, Ruoqi Shen, and Matthew Zhang. Analysis of langevin monte carlo from poincaré to log- soboloo..ev arXiv preprint 12Xiv:21 2021.
Arnak Dalalyan. Further and stronger analogy between sampling and optimization: Langevin monte carlo and gradient descent. In Conference Learning Theory, pp. 678 689. PMLR, 2017.
Hanze Dong, Xi Wang, LIN Yong, and Tong Zhang. Particle-based variational inference with pre-
conditioned functional gradient flow. In The Eleventh International Conference on Learning Representations, 2023. URL https: http::::////peeeeeeeee http:/wwwwweeeeeeeeeeeeee.eeeeee for.mrrrrmiiooro (t-
Alain Durmus and Eric Moulines. High-dimensional bayesian inference via the unadjusted langevin algorithm. 2019.
Raaz Dwivedi, Yuansi Chen, Martin J Wainwright, and Bin Yu. Log-concave sampling: Metropolis- hastings algorithms are fast! In Conference on learning theory, pp. 793-797. PMLR, 2018.
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Sampling from the -iirptttonnkkkpaatiickkkk gibbs measure via algorithmic stochastic localization. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 323-334. IEEF, 2022.
10

---

Published as a conference paper at ICLR 2024
Ronen Eldan. Thin shell implies spectral gap up polylog via stochastic localization scheme. (20)5999-99 Geometric and Functional Analysis, 23(2):532-55) 569, 2013.
Ronen Eldan. Taming correlations through entropy-efficient measure decompositions with appli- cations to mean-field approximation. Probability Theory and Related Fields, 176(3-4):337-755 2020.
Ronen Eldan. Analysis of nigh-dimensional distributions using pathwise methods. Proceedings of ICM, to appear, 2022.
Murat A Erdogdu and Rasa Hosseinzadeh. On the convergence of langevin monte carlo: The inter- play between tail growth and smoothness. In Conference on Learning Theory, pp. 1776-1822 PMLR, 2021.
Yoav Freund, Yi-An Ma, and Tong Zhang. When is the convergence time of langevin algorithms dimension independent? composite optimization viewpoint. Journal of Machine Learning Research, 23(214), 2022.
Leonard Gross. Logarithmic sobolev inequalities. American Journal of Mathematics, 97(4):1061- 1083, 1975.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6851, 2020.
Jian Huang, Yuling Jiao, Lican Kang, Xu Liao, Jin Liu, and Yanyan Liu. Schrödinger-föllmer sampler: sampling without ergodicity. arXiv preprint arXiv:2100 10.880006100880 2021.
Mark Jerrum and Alistair Sinclair. The markov chain monte carlo method: an approach to approx- imate counting and integration. Approximation algorithms for NP-hard problems, pp. 482-520, 1996.
lean-François Le Gall. Brownian motion, martingales, and stochastic calculus. Springer, 2016.
Holden Lee, Chirag Pabbaraju, Anish Sevekari, and Andrej Risteski. Universal approxima- tion for log-concave distributions using well-conditioned normalizing flows. arXiv preprint arXiv:2107.02951, 2021a.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with
polynomial complexity. arXiv preprint 2xXiv:2206.06227, 2022.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In International Conference on Algorithmic Learning Theory, pp. 946-985, PMLR, 2023.
Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Structured sampliing with restricted gaussian oracle. In Conference on Learning Theory, pp. 2993-3050. PMLR, 2021b.
Qiang Liu and Dilin Wang. Stein variational gradient descent: general purpose bayesian inference algorithm. Advances in neural information processing systems, 29, 2016.
Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael I Jordan. Sampling can be faster than optimization. Proceedings of the National Academy of Sciences, 116(42):20881-000 -20885, 2019.
Yi-An Ma. Niladri S Chatterji. Xiang Cheng, Nicolas Flammarion, Peter L Bartlett, and Michael I Jordan. Is there an analog of Nesterov acceleration for gradient-based MCMC? Bernoulli, 27(3), 2021.
Georg Menz and André Schlichting, Poincaré and logarithmic sobolev inequalities by decomposi- tion of the energy landscape. 2014.
Andrea Montanari. Sampling, diffusions, and stochastic localization.
arXiv preprint
arXiv:2305. /06600 2023.

---

Published as a conference paper at ICLR 2024
Andrea Montanari and Yuchen Wu, Posterior sampling from the spiked models via diffusion pro- cesses. arXiv preprint arXiv:2304.11443 2023.
Wenlong Mou, Yi-An Ma, Martin J Wainwright, Peter L Bartlett, and Michael Jordan. High-order langevin diffusion yields an accelerated meme algorithm. The Journal of Machine Learning Research, 22(1):119-11999 2021.
Alireza Mousavi- Tyler Farghly, Ye He, Krishnakumar Balasubramanian, and Murat A Erdogdu. Towards a complete analysis of langevin monte carlo: Beyond poincar', e inequality. arXiv preprint arXiv:2303.03589, 2023.
Radford M Neal. Probabilistic inference using Markov chain Monte Carlo methods. Department of Computer Science, University of Toronto Toronto, ON, Canada, 1993.
Henri Poincaré. Sur les équations aux dérivées partielles de la physique mathématique. American Journal of Mathematics, pp. 211-294, 1890.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. In Conference on Learning Theory, pp- 1674-1703. PMIR, 2017.
Christian P Robert, George Casella, and George Casella. Monte Carlo statistical methods, volume 2. Springer, 1999.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Con- ference on Computer Vision and Pattern Recognition, pp. 10684-10695, 2022.
Rothaus. Diffusion on compact riemannian manifolds and logarithmic sobolev inequalities.
Journal functional analysis, 42(1):102-109, 1981.
André Schlichting. Poincaré and log-sobolev inequalities for mixtures. Entropy, 21(1):89, 2019.
Yang Song, Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011..13456. 2020.
Christopher Tosh and Sanjoy Dasgupta. Lower bounds for the gibbs sampler over mixtures of gaussians. In International Conference on Machine Learning, pp. 1467-1475. PMLR, 2014.
Belinda Tzen and Maxim Raginsky. Theoretical guarantees for sampling and inference in generative models with latent diffusions. In Conference on Learning Theory, pp. 3084-3114, PMLR, 2019.
Francisco Vargas, Will Grathwohl, and Arnaud Doucet. Denoising diffusion samplers. arXiv preprint 3xXiv:2302.13334 2023a.
Francisco Vargas, Andrius Ovsianas, David Fernandes, Mark Girolami, Neil D Lawrence, and Niko- las Nüsken. Bayesian leamning via neural schrödinger-föllmer flows. Statistics and Computing, 33(1):3, 2023b.
Francisco Vargas, Teodora Reu, and Anna Kerekes. Expressiveness remarks for denoising diffusion based sampling. In Fifth Symposium on Advances in Approximate Bayesian Inference, 2023c.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm:
Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2021.
Martin J Wainwright. High-diieesional statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
Dinghuai Zhang, Ricky Tian Qi Chen, Cheng-Hao Liu, Aaron Courville, and Yoshua Bengio. Diffu- sion generative flow samplers: Improving learning signals through partial trajectory optimization. arXiv preprint arXiv:2310.06677 2023.
12

---

Published as a conference paper at ICLR 2024
A
PROOF SKETCH
For better understanding for our paper, we provide a proof sketch as below.
Lemma 1 is direct result of Bayes theorem (Appendix C.I). which the main motivation of algorithm, that estimate the score with samples from g.
Our main contribution is prove the convergence and evaluate the complexity of Algorithm T where the inner loop is performed by Algorithm
Our analysis is based on the TV distance" where use data-processing inequality, triangle in- equality, and Pinsker's inequality (refer to Eq. (19) for details) to provide the upper bound as below
/ DKL. (PT
DTv (iT,P.) V 2 DKL. (TollPr) +
Term
where Term the error between Po and pr and Team is the score estimation loss of the whole trajectory.
Theorem considers the case that all ky is log- log-Sobolev with constant μa (kr S T), where the log-Sobolev constants can further be estimated with additional assumptions on p..
By definition,
N-1
(k+1)
2 2) =
Epr
4 [|vx(X(n)) - 2V In pT (x,)]? dt,
k=0
km
where Term is defined by an integration.
To bound the error between integration and discretized algorithm, have Lemma that when
77 = (ce2)
1 Epr [Ivx 2V WV (x))) 4c² + 2 Ep, [xx 2V In pr bn (xmr) |
Note that the Escore can be controlled by
x - c (T -T
2
Vk (x))
2F N (110)
c 2( kn))
Term 2.1
and
2e kn))
Expro (1x)) Exo [xo]
1 e 2(T km)
Term 2.2
where q' is the estimated inner loop distribution by ULA.
Lemma provide the concentration for Term 2.1.
We also have
Term 2.2 < 8rj "T DKL (1))er-
where the KL divergence is controlled by the convergence of ULA (Lemma 9 Thus, the desired convergence can be obtained.
Note that Theorem is based on the fact that all gr- are Soboleoo.ev. So we aim to estimate the log-Sobolev constants for every -r-
Lemma and provide two approaches to estimate the log-Sobolev constant for different time steps.
Please refer Table for the notation definitions.
13

---

Published as a conference paper at ICLR 2024
When p. is strongly convex outside ball with radius R, derive that Pr reduce the radius so that improve the log- Sobolee constant. Thus, we can choose proper I where pr has larger log-Sobolev constant than Pn and 9: strongly convexity so that the log-Sobolev constants independent of R, which makes the algorithm mix fast.
For general distributions without log-Sobolev constant, Lemma T0 provide the log-Sobolev constant the whole trajectory, so that the computation complexity can be obtained.
B NOTATIONS AND DISCUSSIONS
B. ALGORITIM
Algorithm 3 Initialization of if Pae
Input: Initial particle 2o. OU process terminate time T, Iters To, Step size noo Sample size n.
2: for k = to To do 3: Create nę Monte Carlo samples to estimate
2k-1 E (1-e-20 e-- 2T)
s.t. ge(ar 2x-1) x exp -fa(x)) 1a e- 20
Exz-qi
2(1 - c e-2
4: Compute the corresponding estimator vk-
5: Fy - + Yo 22no where & is sampled from W (0, Ia).
6: end for
7: Return: TT.
B.2 NOTATIONS
According to Cattiaux al. (2021) under mild conditions in the following forward process dx, (x, )dl 2d Br, the reverse process also admits SDE description. If fix the terminal time T > 0 and set & = Xr-t. for i. E [0, 7), the process ($t)1E(oTT) satisfies the SDE d&, = (x, )d v2dB,, where the reverse drift satisfies the relation b, + br 2V In Pt, X, Pt. In this condition, the reverse process of SDE is as follows
dx. (&+ 2V In (&))) Vdd.,
Thus, once the score function V In pr is obtained, the reverse SDE induce sampling algorithm. To obtain the particles along SDE (8) the first step is to initialize the particle with tractable starting distribution. In real practice, it is usually hard to sample from the ideal initialization pr directly due to its unknown properties. Instead, we sample from an approximated distribution p. For large T, Pso is chosen for approximating pr as their gap can be controlled. For the iteration, we utilize the numerical discretization method, i.e., DDPM Ho et al. (2020), widely used in diffusion models' literature. Different from ULA, DDPM divides SDE (8) by different time segments, and consider the following SDE for each segment
dx, (x: + 2V (xpr) dt vdd, t [kn, (k + 1)m),
Xo ~PP
to discretize SDE g Suppose obtain Va approximate 2V In pr at each iteration. Then,
we obtain the SDE for practical updates of particles.
Reiterate Algorithm Once the score function can estimated, the sampling algorithm can be presented. The detailed algorithm is described in Algorithm [ By following these steps, our proposed algorithm efficiently addresses the given problem and demonstrates its effectiveness in practical applications. Specifically, we summarize our algorithm below: (1) choose proper T and proper á such that Pr R p. This step can be done by either ò = P for large T or performing the Langevin Monte Carlo for pri (2) sample from P; (3) sample from distribution that approximate Qr-e: (4) update 5e with the approximated Qr samples. This step can be done by Langevin Monte Carlo inner loop, V log @r + is explicit; (5) repeat (3) and (4) until R T. After (5), we also
14

---

Published as a conference paper at ICLR 2024
Constant
Value
Constant
Value
Co
DELL (pu (oo))ps))
C1
16 L-
C2
48L 62m 22-8m 8m
C
C3
C Coo
C4
2-13, Co 'O00000
Cs
2 .3. 55. C2C C. (2 (2
Cs
6 6
C3.
2
3 5 L L L In + -30T)
C33
641.-1 .C0T
Table 2: Constant List
perform Langevin algorithm to fine-tune the steps when the gradient complexity limit is not reached.
The main algorithm as Algorithm
Here, reiterate notation in Table and the definition of log-Sobolev inequality follows.
Definition 1, (Logarithmic Sobolev inequality) A distribution with density function satisfies the Log-Soboler inequality with constant ps if for all smooth function g: TRd - R with [g 20,
2 Ep. Ep. [9 In g²] Ep. [00] In Ep. [o]] S P
[1V01]]]
(10)
Table 1: Notation List
Symbols
Description
The density function of the centered Gaussian distribution, i.e., / (0, o2).
Poz
Po.Po
The target density function (initial distribution of the forward process)
(xt)
The forward process, i.e., SDE
Pt
The density function of x,, i.c., X; Pt
Pro
The density function of stationary distribution of the forward process.
(xt) (
The ideal reverse process, i.c., SDE
(
Dr
The density function of & i.e., & Pr and Pr pr-
Pr
The law of the ideal reverse process SDE 8
over the path space C (10, TT: R2).
(8))ef0111
The reverse process following from SDE
Pt
The density function of X,, i.e., X, P7
(x.) 1e)
The practical reverse process following from SDE (2) with initial distribution y The density function of R i.c., X; P.
Pt
Pr
The law of the reverse process (Rx) (Re)eejoT) over the path space C ((0, 27; IR.).
(xP"
)(E(o.T
The reverse process following from SDE (2) with initial distribution pr
PP per
The density function of š,, i.c., x²" p."""
The law of the reverse process (x!T) )<e(o,T7 over the path space C (10, (10, R):
Besides, there are many constants used in our proof. We provide notations here to prevent confusion.
B.3 EXAMPLES
Lemma 4. (Proof of the Gaussian Mixture example) The iteration and sample complexity of rdMC
with importance sampling estimator is -2c-2).
15

---

Published as a conference paper at ICLR 2024
Proof. Similar Eq. 19 in Theorem
we have
/ DKL (Prlll (Prll pg
Drv (pr.Po) S
DEL (Poller)
(11)
Term
Term
by using data-processing inequality, triangle inequality, and Pinsker's inequality.
To ensure Term 1 controllable, choose T 2n For Term 2,
DKL (p.))
26a
dPr dP dPP
N
(k+1))
DKL.
(Prl) = Epr
E Bpr
-x++ dt
kg
k=
N --1
1k+1)9
EE
2V ||va(xx))-
||v((X)))
2V
dl,
4
k=
ln
By Lemma
E
[Vx - 2V (x))-
4e2
+
Epr
VI - 2V In (knn )|
2
(12)
Thus, the iteration complexity of the RDS algorithm Ō(c-2) when the score estimator L2 error Óe), which is controlled by concentration inequalities.
For time 4, since we have DKL (Pr-ollrr-) S and pr-t is sub-Gaussian, the density Pr is also Gab-Gaussinn with variance of².
We have
P[ - Exl > 220 In(3/)) S
3
For Gaussian mixture model, (zo) is 2-Lipschitz and function f. is 1-Lipschitz smooth, a-e (T-0)2g (1-0-2(T-1) exx((-f(Zzo) is Lipschitz
For time f, the variance is of e -
1-e-2(
Assume that the expectation and the estimator of xxe-(((-))) exp((=f(xx)) is px and X. The (1-e 2(T 2(1--))
expectation and the estimator exp((fa(xo)) is jy and Y
ne²
P([X uxl > c) S exp
20 G2
nc²
P(YY prl 6) exp
80?
We choose x+ Ex /20 (3 G G
If max 4) In(38-1), 1 with probability 1 1 5, the error of the estimator is at most Moreover, if we choose the inner loop iteration to estimate the posterior. We can start from some T > 0, and estimate pr initially.
Specifically, for the Gaussian mixture, we can get a tighter log-Sobolev bound. For time t, we have Pt x e - + e --x===---'vi which indicate the log-Sobolev constant, CTS. S 1 +
(elle 'vII? + 1). Considering the smoothness, we have
2/2 (6:2/2 2/2((-10))))))) + (e=3/2 1/2(2 1/2(221))))))
log logp(r)
-1+
2 51.
1)
16

---

Published as a conference paper at ICLR 2024
When we choose T - log 21+1 2 log 2, The estimation of pr needs O(e iterations,
2L
which improves the original O(e")) )
Lemma 5, Suppose the negative log density of target distribution S. = In satisfies
f=(x) = (1|=|1 + 1)*
where E 0.5).
Proof. Consider the Hessian of f.. we have
V (x) 2a (x² + 1)0-2 ((2a 1)x² + +1).
If we require
|x| 2 r 1/(2-2a), it has
|x/
|x|| 2 r 1/(22a))
7 |za| 20 2 r-
+ r 2
[r 1-
r (1 - 22)lzr/ -
2a (x² + +1) 1)0-2. ((2a 1)x² +1) 1)) = (+)
+r|a)) 2 0.
(|x|2 2 + 1)2-a
means if we choose CR 1 and n 1/(2 2a)
B.4 MORE DISCUSSION ABOUT PREVIOUS WORKS
Recent studies have underscored the potential of diffusion models, exploring their integration across various domains, including approximate Bayesian computation methods. One line of research (Var- gas et al., 2023a Berner al. 2022 Zhang et al. 2023 Vargas et al. 2023c b involves applying reverse diffusion in the VI framework to create posterior samplers by neural networks. These stud- ies have examined the conditional expected form of the score function, similar to Lemma [ Such score-based VI algorithms have shown to offer improvements over traditional VI. However, upon adopting a neural network estimator, VI-based algorithms are subject an inherent unknown error.
Other research (Tzen & Raginsky 2019 Chen et al., 2022a) has also delved into the characteristics of parameterized diffusion-like processes under assumed error conditions. Yet, the comparative ad- vantages of diffusion models against MCMC methods and the computational complexity involved in learning the score function are not well cell-investigated. This gap hinders straightforward comparison with Langevin-based dynamics.
Another related work the Schrödinger-Föliie Sampler (SFS) (Huang et al.) 2021 which also tend to estimate the drift term with non -arramerrii estimators. The main difference of the proposed algorithm is that SES leverages Schrödinger-Föllmee
process. In this process, the target distribution p- is transformed into a Dirac delta distribution. This transformation often results in the gradient V log Pt becoming problematic when pt closely resembles delta distribution, posing challenges for maintaining the Lipschitz continuity of the drift term. Huang al. (202I); Tzen & Raginsky (2019) note that the assumption holds when both p. exp(||=||>/) and its gradient are Lipschitz continuous, and the former is bounded below by positive value. However, this condition may not be met when the variance of p. exceeds 1, limiting its general applicability in the Schrödinger-Föllmee process. The comparison of SFS with traditional MCMC methods under general conditions remains an open question. However, given that the Pao of the OU process represents smooth distribution a standard Gaussian, the requirement for the Lipschitz continuity of Vp, much weaker, as diffusion analysis suggested (Chen et al.) 2022a| (023). Additionally, Lee et al. (2021a) indicated that L-smoothness in log-coneave p. implies the smoothness in Pt. Moreover, the SFS algorithm considers the importance sampling estimator and the error analysis is mainly based on the Gaussian mixture model. As we mentioned in our Section 3.3 importance sampling estimator would suffer from curse of dimensionality in real practice. Our ULA-based analysis can be adapted to more general distributions for both ill-behaved LSI and non-LSI distributions. In a word, our proposed RDMC provide the complexity for general distributions and SFS is more task specific. It remains open to further investigate the complexity for SiS-like algorithm, which can be interesting future work. Moreover, it is also possible to adapt the ULA estimator idea to SFS.
Our approach, stands as an asymptotically exact sampling algorithm, akin to traditional MCMC methods. It allows determine overall convergence rate that diminishes with increasing
17

---

Published as a conference paper at ICLR 2024
computational complexity, enabling direct comparison of complexity with MCMC approaches. The main technique of our algorithm is to analyze the complexity of the score estimation with non- parametric algorithm and we found the merits of the proposed one compared with MCMC. Our theory can also support the diffusion-based VI against Langevin-based ones.
18

---

Published as a conference paper at ICLR 2024
C MAIN PROOFS
C.I. PROOF OF LEMMA
Proof. When the OU process, i.e., Eq. is selected as forward path, the transition kernel of (x))120 has a closed form, i.c.,
| e '00ol
p(z, 1/20; 0) (2th (1 - c 4/2
cxp
AOAIST.
2 (1 e 21)
In this condition, we have
(r-((x)= = f Po(x))) Pr- (20/20) )200
x - e (T (T--))2001 1
- po(o)) (2TT (1-e- (1- 1/2
exp
(1 2(T 11)
dxo
Plugging this formulation into the following equation
V In (r))(x)) Vpr-c(a))
pr-((x))
have
Jix po(2))) - (2T (1 - ---2((--))) 4/2
2
exp
2 1--e--0 211--)()-))
dæ0
Ve laInpr--e (x))
SR Po (2:0) (2T (1 2(T ())
-//2
exp
22 c (7 2)
dæo
2(7 12)
Sue po(2ra) exp
2 110-2((-)))
x ---e~-zo|
m-c - (1)
(1-e-2(1-()
dao
(13)
m- (r---(1--)0))
JR (o(oo)))) exp
doc
2(1-e- 1(
- (T-
Exp (()1a)
(1 e 2(T (--(
where the density function QT -e (x) is defined
xx-e" -0-0--1a011 =| 11-- 2
(r=o(x)) = Po( exp
exp (-fa(mo) x - c (T xoo
Po(po))))))))))))) exp
10-0 tm00 daep 2 (1---2()-)
2 (1 2(T -t)
Hence, the proof is completed.
C.2 PROOF LEMMA AND
Lemma 6. (Proposition I in Ma et al. (209 For p. x -V where U is m-strongly convex outside of region of radius R and L-Lipschitz smooth, the log-Sobolev constant of p.
m 16LR PU
Proof. By Lemma 6 for any / T km,, we have the LSI constant of qr- satisfies
2(T 2(T kn)
6(1 6 2 (
2(T kn)
CLSIA 6(1 c k(T- exp --6-33- 3L R²
When 1+2L
24 < è -2(T-km < 1. We have
- 2(T
L
2 0.
2 2 - e-2(T 2km)
19

---

Published as a conference paper at ICLR 2024
which implies
30 2(122
-2(2
max (1 - E e-211 ((])-k))
I V gr kg) - 2 211 - - --2 -k)) I = Ek,min
(14)
Due to the fact that yo- kn is -troongy convex, Σk, mmyoooht and Lemma CLSTT 2 Ek.iin.
20 we have
C.3
PROOF OF MAIN THEOREM
Proof. We have
DTV (iT,P-)) SDTv (Pr, s Drv (Pr, ppr)) + DTV (ppT, Pr))
SDIV (PoPP) Drv (ppr Pr)) s 1 DKL (poller)
V DKL (Pr
(Pr||pp
ppp
Term
Term
(15)
where the first and the third inequalities follow from data- sata-processing inequality, the second inequal- ity follows from the triangle inequality, and the last inequality follows from Pinsker's inequality.
For Term
dPr
N-1
(K+D0
DKL (Pr((PpT))
Err
In
E
Epr
([ 2V In ( dt
d
T
kn
N
(k+1)1
IE Ar
4 [[va(Xen)
- 2V In pr (x+)) de,
0=
Ann
By Lemma
Ex [[vx(X)e))) - 2V In
< 4c2 +
E
[IVA(X)))) - 2V In pr (x 11
Epoore
(16)
According to Eq.
4 for each term of the summation, we have
E B
[ - 2V In pr kn (xke) 112
Xkn c -TT- XDI
=EA,
(x(m)) - 2B 2xxo~gr - an (kk))
2-(
20

---

Published as a conference paper at ICLR 2024
For each Xky æ. we have
a (T (T-ko)) XD
vx(x)) - -2Exx km))
e- 2(T kmn)
x e (T - (uuyy x
(x) - -2Exx 26xx6maar (.1z)
c 2(T km))
2e (T-(T-Am)
+ 1 -2()-ko)) [Exs - kny (11w)) [x6] Ex Exprgr - kny 20) [xo]
(17)
e (1' kn) (2'-kkx) X
2
(a:) 2Txxx 2/ kn (11z)
(1 e 212 kmn)
Term 2.1
2e (T km))
+
Exg r (1x) (xo] Rx and (ax) [xo]
1 e-2(T
2(T kmn))
Term 2.2
where we denote kn (-12) denote the underlying distribution of output particles of the auxiliary sampling task.
For Term 2.2, we denote an optimal coupling between 9r on (z)) and & -2, (112) to be
Y I opt (,, 17 (- (-12:)).
Hence, we have
2e -('-knn)
Fx (13)) (1(aa)((()))
Exo - (-1e) [xo]
1 e- 2(T
--2(T -kn)
1 e km) (xo - x6) ]1|
2e (T-)k)
(ixx my
E E(xox [|x0 - x611
(1 e- 2(1'-k0)
4e -((T-kn)
W2 (gr- (x), 4 kn (-12z)
(1 222(T-kn)
40 -11 kk))
<
CLSTI DKL bn -x
c kn)
<8n -C DKL (--=))(11 (-1x))
(18)
where the first inequality follows from Jensen's inequality, the second inequality follows from the Talagrand inequality and the last inequality follows from
e -kn)
(PT-kn) -2n
n
- 2(T k()) S $n
when 77 S 1/2.
By Lemma and 9 the desired convergence can be obtained.
21

---

Published as a conference paper at ICLR 2024
C.4 PROOF OF THE MAIN PROPOSITIONS
Proof. By Eq. 19 we have the upper bound for
2 PKL (oller)
(Prll por
KL
(19)
Term
Term
We aim to upper bound these two terms in our analysis.
Errors from the forward process For Term of Eq. 19
we can either choose DKL (pl pr) or
choose large T with P Poo-
we choose p = Poos we have
(-T)
T
DKL. (pollPoo) = DRI. (pTllp>>) S Co exp
(-2
where the inequality follows from Lemma 21 By requiring
T
Co 2
Co exp
26
T > 2 In
have Term 1 S c. To simplify the proof, we choose T as its lower bound.
we choose p. then the iteration complexity depend on the log-Sobolev constant of pT. Ma et al. 2019), it is demonstrated that any distribution satisfying Assumptions [A]] and [Ag] has
log-Sobolev constant of m exp(-16I.R)) which scales exponentially with the radius R.
Considering the Pr, we have
Xy e + V1 - e
Assume that the density of T Xo is h.
log hie Tx) log le- TT logPo(r)
log hiee Tx) = log po(x) + dT.
Assume that y = e- r and Assumption
[Ag] holds,
- -VPhly) = = 2T -Vpee' 2 2T mI.
We have outside ball with e- RR, the negative log-density 2T m strongly convex. By Lemma 16 the final log-Sobolev constant is
+ 2T)).
16LRRe 2427)
Errors from the backward process Without loss of generality, we consider the Assumption [A case, where t has been split to two intervals. The Assumption [Ag] case can be recognized as the first interval of Assumption [A,] For Term we first consider the proof when Novikov's condition holds for simplification. A more rigorous analysis without Novikov's condition can be
easily extended with the tricks shown in (Chen al. (0222)). Considering Corollary [
we have
dPr
N-1
(K+
DKL (Pr(((pT)
= Ext
Exp
( - 2V In (x dt
dPPT
4
ken
k=0
N
1k+1))
IF Pr
[|va) - 2V In
xx)1(* dl,
4
0=
(20)
where N [T/n].
22

---

Published as a conference paper at ICLR 2024
We also have
E Pr
[|vx(X)n)) - 2V In pr - - 4e² + BB,, [Vv
- 2V
2V kny (x ||
Cecore
(21)
following Lemma by choosing the step size of the backward path satisfying
1) S 1 (d + m²)
(22)
To simplify the proof, we choose its upper bound. Plugging Eq. into Eq. 20
we have
N-1
DKL Pr pPr
8e In
Co
1
Ep
( - 2V In PP (xmm)
|11
2
2
k=0
Besides, due to Lemma
10 we have
N-1
[|vx(xk)) - 2V In ( S 20c² In Co
Σ
77 Ep
2
k=0
with a probability at least e by requiring an O (max (CyCs, CjC²)) CT Co (d + m2) c 16n-88
exp (5Cze- 18t))
gradient complexity. Hence, we have
1 Term V2 (4e² + 562) T s 3e/
C
In
22
which implies
C
DTv (pr. S Se+3eyll
Ö(())
(23)
26
Hence, the proof is completed.
D IMPORTANT LEMMAS
Lemma 7. (Errors from the discretization) With Algorithm 7 and notation list 7 if we choose the step size outer loop satisfying
1 S C1 (d m3) -1 2,
then for L [kan, (k 1)n] we have
Pr Py (Xke)
+ +L2. ERg ||xxe] -x1l Se:
Epr
v In
PT (
4 Eg, [ 2V (x)))
4e2 + Ep, [Iva(X)n) 2V pn (Xky 1|
Cacora
Proof. According to the choice of f, we have T kn 2 T t. With the transition kernel of the forward process, have the following connection
pr kk) (2) = -f pr (r)) (xc kn/yy,7 T dy
/ pr (p)) 2T (1- 2 -((--(())))
x
(t (t-kn) y
27
exp
dy
2 (1
2(1 kvl)
= =f (((1-kn) pr (clt-balz)
12m ( e )
) exp
10 z
dz,
2 2(1
e 2(1 - (((-kn))
(24)
23

---

Published as a conference paper at ICLR 2024
where the last equation follows from setting = e- -(t-kny y. We should note that (z- == e( kn)d PT p x)
is also a density function. For each element Xlen 2:, we have
V In pT-
2
V In PT (r))
elt kn)d pr (elt-kr)zz) x)
12
V In
PT
(tt-ky)dpp pr - (e(t-kn)zz)
pr Pr-kn (2)
pr-((2)
elt-krid pT- (elt-kn)gg)
< In e(t (tt-kn)dp -t (elt~ko)x)) x3)
+ 2
V
D' * (01-- 201 2(-))))) kml)) (xx)
where the inequality follows from the triangle inequality and Eq. 24 For the first term, we have
(x)) V In ell clt-knidpr - (elt = In pr ((x)) - elt Vinpr- (0)-
V Vimpr-tf - clt- V Vinpr-e(x>) + clt Vinpr-((x)) - Vinpr- (elt-br)zz)
(t km) -1) (x)) + (()) (cle-ko) - 1) L |0|||
(25)
For the second term, the score - Vin is (e2lt-kn) L.) -smooth. Therefore, with Lemma 13 and the requirement
1
4(t kn) $ 2L
2 e (t (1
1 s
1 1 88L 2
$
+ = min
L
1
t t-
2
we have
V In 1mmpr-1(0)) (x) V ( 10(1 e1-e -())))))))))) (20)
2(1 <6e km)
<6e
((62((-k))))) /// (1 - e- kml) 12 + 30 km) L (1- 2(t -(t(t)))))
|| Vippr- (clt-bm)))
<60 km)
// (1 -(- )d/2
+ (t
(22(= - - 1) V In p (c(t-mnl)) V In (m + VInpr-((x))
<6e ((1 km)
LV (1-e-2(t-bn) 12 + 222ee (e2(--hn)-1) -1 (elt-bm)- - 1) ||
+ 2t kn) (22tt-kn) 1) \n)p--(<>)]
(26)
Due to the range S 1/2, we have the following incqualities
k(t-kn) < 20 < 1 + 4n. 1 1-c - 2(t-kan) < 2(t - kn) s 2n and (ll S ed $ 1 + 2n.
Thus, Eq. 25 and Eq. 26 can be reformulated as
PT (2))
V In e km) pr (elt-kooz))
2m V (m)r-((x)] + +mLL ||||||
(27)
pT (2)
V In ((t-kn)dpr- - (elt-
S 8n |/ (2)r + +32n² 222 1
and
V (Vnnpr_(()) - V In (p * (1- 20 km) (x))
<6 (4n + 1) T.T. + 21. (2n + 1) 4n 2n ||=||| ||
2T (2n + 1) 4n ([Vhn
<18L 2nd + 3212,²² ||0||| + 167 | inpr-(())1
24

---

Published as a conference paper at ICLR 2024
which is equivalent to
(VIpp-.(()) Vin (pr : 9((1 -((---20--0)) (z:) (z))
33 22 1.3 1pd 2 -= |
2d 1 | [
(28)
<2 ndd + 212 I=1)² || + 220 - In PT (x)).
Without loss of generality, we suppose I. 2 combining Eq. bound
27 and Eq
28 we have the following
V In Px PT -yy (Xby)
ppr
<2 Lnnd + 2 LL ||xxn| [1]
+ + L2n1"BB
V In pn
$2 Land + 23. 1.212BB.p ||xxay]1 12²
+ + .T211BB
(
||xxe -xal-xxll + + L L'12"Ep
xxl1?
(29)
Besides, we have
E In Pr- (Kb))
+ LL
||xn] xil²]]
pT - (Xin)
<4
214, Land + 2.. 11211"B.p,
||xx)]| 11
213 ,1,,,
[ ln pr p
(30)
+ (2 12 + 1) L Le | - -xeli xx11
<6 Lajd + 2 12212 (d + mb) + 25 L 28. 1 (2(m3 + d)v? + 4dd),
where the last inequality with Lemma 14 and Lemma 15 require the step size of backward sampling. i.e., satishes
To diminish the discretization error, we
1 --1d-12
16 Lnd s
752-5 5 --1 (d m
0.5
20 1d + m²) S
7S2 75 - --
2 L'd
" 0.5 (d+ m
0.5
23. L (2(m² + d)n² 4dn) 5
1 152 2--
Specifically, if we choose
1 S 2-6.
16, - =d (d+ mī)
-1 2 Ci(d+mi) -t62
we have
PT Ph- (Xin) 12
EA,
V In
+ L'
[|xxn -x.l" S
(31)
pr (x
Hence, the proof is completed.
Thus, for E [K17, (Is + 1)v)), it has
[[vx(x))) 2V (xx))
pp
4
<2E Pr
I kny - V VlupT=:(x.))
+ Ep, [ [Iva(xen) - 2V 2Vlnnn In (xx,))1
VIn Pr- pn- 2
+ Epp [|xxnv - Xx 12]
<AE Pr
Pr (x
1
E2 [|vx((x)n) 2 W (x 113]
+ 2
1
<4e²
+ 2
Epy
- In (2
Escore
(32)
25

---

Published as a conference paper at ICLR 2024
where the second inequality follows from Assumption A1]
Lemma 8. For each inner loop, we denote (=(-(z) and q(-(2=) to be the underlying distribution of output particles and the target distribution, respectively, where q satisfies LSI with constant p.. When we set the step size of outer loops to be by requiring
2 64 11 3-28--1 and DRL (qella) 13-13.T-40 - 22
we have
PO (1)) (
Σ
12
v
E
12
(x)
20c I exp (- (-0/217/m))
6
2[T/nl
72
72
where
( vi(2) = -2 c 2(T-km) km) i E n1.
Proof. For each inner loop, we abbreviate the target distribution as q, the initial distribution as go- Then the iteration of the inner loop is presented as
X = xx + V In (xx + V2,N( I).
We suppose the underlying distribution of the z-th iteration to be ga (-122) following inequality
Hence, we expect the
x - x ((a) - - 1 9=((mo) 1- 2(T
P
S 2 2 1 8
is established, where v(x) = 1/n Ei= vz(x). In this condition, we have
P P(x (1)" (1o)) J.=.-
1 n2
-
1 E
v((w))
E
vi(2))
(v)(
+
n
n
71
x2
n
a
n
-2( -(mT-m)
-P -P((20) (1) (x0 J.=.
(-(a)
E
(8)
E
X;
E
(i)
2e (T-
(33)
To simplify the notations, we set
b. = (-10 (x0],
= T=B(x [255)___000 (
X; E
b b: Eg(())) xo)] and == B 1011 1==
Σ X; E
Then, we have
12
1 2(1'-kn)
P No J. (1(m)
nb
2 0/ +
26- (T -km)
716
1 - -2()-kn)
<P % } --(10(-120)
n
2 0/4 +
26- (I -km)
nE
+ Drv (+)x) (-Ixa)
1 e -k)))))
<P (()) Nr (-(0)()11))
(x(0)) J.==
Σ nb
2 0/3 +
2e- (I kkm)
mE
+ n Drv(((( (-x=)
(34)
26

---

Published as a conference paper at ICLR 2024
Consider the first term, we have the following relation
1 (T
nb;
2 U2 +
2e 2--2(7- 2(T-
nc
X
(1)
nb
Σ
(1) X
nb.
n bb b.l
==1
i=1
e -k))
(35)
U/
2e (T-
b
-byl
E 222 -ky)
U+ +
ne n2 b bzll + (V= - v)
26- kk))
204 - 6 --(T-(T-k)
2e (r') ne (2(a(11ar..0=(11))) Vndu-1
where the last inequality follows from
| b. -
= /// (((=0o=²) q: (x00 zadaro
= 11 (xo xz2) (( x ) x::)
1/2 $ 20:0000)):
(ʃ (z) ||300 - x=1 d(z xz))
1/2
(36)
and
=n E
( (1) n
(13))
x
(8) b
< n
var Σ
0
(8)
Jim1
1=1
i=1
(1)
nvar
Xg
S ndp
deduced by Lemma
23 By requiring
1 e -k) km)
64c 2(T kn)
and
n 2
(37)
8e- km))
(1 --(
2(T -((T-kn)) kn))) pe2
in Eq. 35
we have
Y2
1 e -kn
((x))) (" Jim (1())
nb.
2 0/z +
(T-kn)
(38)
T2
1 kk))
SP 10)" (x()) J,m (m))
nb
2 +
(T-
116
According to Lemma 16 the LSI constant of
q
is u/n. Besides, considering the function F (α:) = x
Rdd - R is 1-Lipschitz because
FF(x)
F(y)
| Lip
sup
sup
1, (1 b)ll
x
yl
2
we have
-om) 4e (1 (7')
Pr Pram)" (1(=) J,=1
Σ
x
(1)
nb
2 v
(39)
(1 (1- (T (T- kn)) 2 P
<exp
32c 2(T km)
27

---

Published as a conference paper at ICLR 2024
due to Lemma
18
Plugging Eq.
39
and Eq.
38
into Eq.
34
and Eq.
33
have
P { 1 (.
n2 Σ
1
(2)
1
(2))
E
v.(x)
Bv
+E
x Jun
n
n
I <exp (1 - e (T- -kn)
)ne p
+ 9=)(
32e 2(1 kkn
(40)
Besides, we have
1
n
E ( J J
(-10)
11 Σ v.(x) (x) $
var
Vi
vV1
2e -7- -7-)n)
var(xo)
1- e-21 kkn
Suppose the optimal coupling of (=(-1<>) and q( (((1 is 7 E Topt (g=(-1x;, ((112)), then we have
(2xx2=(a)) | - bull dæ= = / ||== b.11"dd(ax2.....
var (-la) (xo)
/ || xo + 20 b+ b=ll² dd((x,,
33 ||00 - xoll dd 2o) + / | b1l dy(xx, + +/1bb ||b - b,1l
<6W2 (g. + 3dp -1
where the last inequality follows from Eq. and Lemma 23 have
By requiring W2(1. (z) S
d we
6
2e (T')k))
varg. (xo)
4
e c(T-km)
d
e kw))
Vn
2(T
km)
Combining this result with Eq. 40
we have
P "
(x00)
x Jizi - (-10)) n
Σ
n
vx)
n
E
Σ
(x)
vn 1 1 c
4 (T
2(T
V
d
+e
(1 - (T (k)) n
< exp
+ Dro(((((o)),111111))
32e - 2(T'-
By requiring
4 e (T-
d
16e 16E-2(T 2(T-)))) d
Se
n ス
Vn 1 - 6 km)
1
(1 c -(T -(T--or) kn))
1.c2
(T kn) ) 2
< - TT//
2
n T/nl
64c 64c-2(2 2(T-kx))
(41)
32c 2(T kkm)
(T- p2
and Drv(ū.9.) 9z) S 2n [T/ml
have
2 < exp (- 1
P P(1001 ),_, (11x)
Σ
v xx)
E
(x)
(~8/(11\\)) + 2[T//
28

---

Published as a conference paper at ICLR 2024
Combining the choice of n and the gap between (-|la;) and (=(-(z)) in Eq. 37 and Eq. 41
have
64e (4e-2(T-kk)) d
n 2 (1 2-T 2kn)) km)) pc?
-(7
(1(a() S 8p (T-(T-Am)
64c 2(T -ky)
n 2 T /n|
and
Wi(a((l)). <d/(6p)
(1 e- (T 12
8
π1 16e 2(T 22(T-ku) d
Drv(a(())) S2n [T/ml
- 2(T 2(T)) Me?
(42)
Without loss of generality, we suppose v S 1/2, due to the range of e -2(22' as follows
--(
km) I 6 S =
((TT-((T-kn)) S $1
we obtain the sufficient condition for achieving Eq. 42 is
n 2 64Tdu "n 22228-1 2 max {64dμ ', c2 64T -3 31 11-1622-- 16dp 161 2
and DTv 9x) S 81 DKL (q=ll)) S p < 2- 13 T 'd 3
Hence, the proof is completed.
Lemma 9. With A Mani notation list if we choose the initial distribution of the k-th inner loop to be
x - e -('--kn))000
Or km (2n x)) x exp
2 E 2(1 --2(1
2(T km))
then suppose the the LSI constant of -kn is CLSST.K. their KL divergence can be upper bounded as
L? 2(T
DKL (1)- <
(d+ ||x0|²²
2C1.T.
Proof. According to the fact that the LSI constant of qn is CLSI,E then we have
/ 4 kn (x0 f dæy
DKL (4r (n (-1) (-1z)) s (2CLS1,))
<I2(201SL*) Exo (,))
[|00||]] (2C (var(xo) + |E [xx]](3
Because 4/- kn (-12)) is high- sigh--imensional Gaussian, its mean value satisfies E[xo] cTT-kn)) x.
Besides, we have
2(T -k)))))
2 In k (wo) - e- km) I.
According to Lemma 20
4/ kry (=lz) satisfies the log-Sobolev inequality (and the Poincaré inequal-
ity). Follows from Lemma 23 we have
e varxoroyy (lw) [xo] - d. - (22--2((-)n))
2( kn) - de
Hence, we have
122 2CLSLK
2(T-kn) (d+ 2|x)1
DKL
S
and the proof completed.
Lemma 10. (Errors from the inner loop sampling task) Suppose Assumption
A A2 A
hold.
With Algorithm 1
notation list and suitable 1) = C1 (d + m2) e², there
N-1
n E Ep, (X(e)) 2V In pr (x < 20c² In Co
26
k=
29

---

Published as a conference paper at ICLR 2024
with probability least 1 - 8. The gradient complexity of achieving this result is max (CaOs; C3C²)) CT (d + where constants C and C2 are independent with d and c.
(dd+))) mm) 6 exp (5C2t" (66m) 8-6
Proof. To upper bound it more precisely, we divide the backward process into two stages.
Stage I: when e km) < 2L/(11 + 2L).
It implies the iteration &o satisfies
1
2T In 1 2T.
k - 27
N1.
(43)
2L
In this condition, we set
x (T 200
9r (2 [x) expl 9T -T (2n)=)) exp (fa((o)
(44)
2 (1 e- 2(T -(T
Hence, can reformulate gT (2o [z)
e 2-2
@r An (xolz) = (x00) +
|
3(1 e-2(T-km)) kn))
part
-2
(T (T))))
| |
|100||
(1 e 2(T km)) Fy x +
6(1 - e 2(T kk))
2(1 --T -((T-kn))
part 2
According to Assumption ball with radius R(e-2(T 2(T km) (6(1 2-2(T ))). With Lemma 22 the function (--xx(-| is e -2(T'-An /3((1 e -2( ( (n)((r-k))))-roorol )tttrnggy convex outside the ball. Besides, the gradient Lipschitz constant of (n (+ can be upper bounded
[A,] we know part and part 2 are both strongly convex outside the
-((TT-k)
- 2(T-kk))
) I 3LI
- = V² (20) + ((T-k) I L 2-T-kk
where the last inequality follows from the choice of 2(T--kn) in the stage.
When the total time satisfies exp(-T/2) 2ca/Cu. we have
-- -km)
LSL 56(1 c 2e 2(T exp (8L 122
6(1 e- 2(T 2(T-)bo))
2n <6exp 2(T - -kn) + 48L (6(1 - -2 2(7) e )
<6exp (2(T- -mn) 48L - 6 e An((T-k))
The second inequality follows from Assumption [A,] and the last inequality follows from the setting n, L 2 without loss of generality.
LSTT 2- ..e - exp (48L- 62n. 2-8n. C8n c Cge exp (C2-c- 116n) (45)
For Term 1, due to Lemma g if we set the step size of outer loop to be
= (d m3) 2
the sample number of each iteration satisfies
nh =O3 (d + m3) e -18 exp (C2 E - 8-1 = 64 3 (d+ m2) -18 exp (C2 -16m) ) 8-1
-11eex
264 2 Co
d. (Cd + -1 -3 -2 C&e -8 exp (C2 c 166) 82 64Tdn 33 -2 1
C
2ea
30

---

Published as a conference paper at ICLR 2024
and the accuracy of the inner loop meets
DKL (y
S C4 + (d) -10 E exp exeepp-202 (-2C2 - 1-16)) 8r
=2-13 13 0 C9 (d +
m²)
10 258 C 16 exp (-202 i 166)
52-13 21n
Co
d e 8t Ci (d + m²) - 16 LSLA 2 22-13.T-41 2
LLLA
2x
(46)
when e2 1/2. In this condition, have
a e e
(7-
x0
P vx(xx) 2Bx, ~ (np())))))))
S 4
(1 - e 2112 (2122-k1) kn))
(47)
5
6
21 exp
5/(2LT/n))
2[T/n]
T/m
where T (-kz) denotes the underlying distribution of output particles of the k-th inner loop. To achieve
DKL. (n (ran)) |!Tr (orT-Ar)) Any (zkk)) S C4 (d+ mm) 10 644
exp (-202 ee 16m) 8 dKL.
Lemma
19 requires the step size to satisty
The 3 -0,0 (d m2)
52 exp (-30ge 16n) 8²
<C exp (-C2e
C2e 166)
1
C4 (d + m²)
10 et exp (-202 - 166) 8
4(3)22
4d
CLSII&K -
jKL
4d
and the iteration number Z& meets
2DL 10)
Z
ln
CLSIAT
dKL
where (- denotes the initial distribution of the k-th inner loop. By choosing to be its upper bound and the initial distribution of k-th inner loop to be
| - e - km) 1o 11² (-I1a
dr o (x) x exp
2 (1 e- 2(1 kn))
we have
I
DKL
S (kT (d 21
2CLSS
<2
L2-' exp (O2 - - 166)) kk) (d + ||x0|)3)
with Lemma 9 and Eq. 45 It implies the iteration number Zμ of inner loops to be required as
Zx 20s (d + m3) 12 16m-61 exp (4C2e (1C2)-16). (d+
[| 8-5
=2 3t 34 522 C2T c8 In (2 +12 CG) (d + m2) 12 16n
16n 61
exp (4C2e -16n) (d + || 8-5
-Cac 8 exp (C2 c 111) (24. 3 Co (d + m²) 11 52
cx exp (3C2c 8-1)
Co) + 3C2c 16n + 60 + 4ln 8
+ 10 + m²) + In(d + |1x113)
2DKL
1
In
CI.SIAATR
OKT.
when In(1/c) 2 2 and In d 2 2 without loss of generality.
31

---

Published as a conference paper at ICLR 2024
A sufficient condition obtain Term 2 < c² is make the following inequality establish
DKL. (nr- (1)))))) 2- .ffe? C exp (-C2e 16m)
which will dominated by Eq. 46 almost cases obviously.
Hence, combining Eq.
17
Eq.
47
and Eq. 18 there is
N1
En
n
Ep |Ivx(x)n) 2V InpT- (x S 10N e²
(48)
k=
with probability at least - Ni- 6/([T/n]) which is obtained by uniformed bound. We require the gradient complexity in this stage will be
cost
ng E By (Zx)
Eo (d + mž) c- cxp (C2 . 16n) 16n) 8-1
k=
By [Cs (d m²) c-nn- 61 exp (4O2c 16m) (d+ ||x,,| (11)) 8 8-81
<N1 - C3C3(d + m 16n exp (50ge-16n) 8-6
(49)
where the last inequality follows from Lemma 14
21. Stage 2: when I+2Z S e 2(T kn) < 1. We have the LSI constant for this stage. It is a constant level LSI constant, which mean we should choose the sample and the iteration number similar to Stage 1. Therefore, for Term 1, by requiring
64 Thk - L COCTS. (d + m²) 108-1
Co d (Ci (d
264 21n
1, 2 64Tdn -2 CiSL
2²
and
DKL (4r (=)1 2- 12 C (d m²) 100
Co 262
<2-13.
2ln
.d
C (d+ 26 Gist c.. 22-3..-11-2255 G
(50)
In this condition, we have
e (T- km) (T- xo
P
2.Exx, ~oh - (1)x) va((x)
S 4e²
(1 - e 2(T e-2
(51)
5
8
21 exp
8/(2(T/n))
2[T/n]
T/n]
where o/ kn (-1z) denotes the underlying distribution of output particles of the k-th inner loop. To achieve
DKL. (or- (112,,))) |l (AA)))
<2 13 C (d + mz) 10 28 = ÒKT.
Lemma 19 requires the step size to satisfy
Tk <2 17 3
--- k,max
LL 4 C² (d mm) 28
Ekmii
1
2
13 L²
- (d + 113-100250 28
> k maxx max
m2x.
4d
CL.ST,
1
8K1.
V kn (:12)
4d
and the iteration number Z₁ meets
2D (-t-)m
Zx 2 CLSIATK
In
δKL
32

---

Published as a conference paper at ICLR 2024
where kn (-1z)) denotes the initial distribution of the k-th inner loop. By choosing T3 to be its upper bound and the initial distribution of k-th inner loop to be
2 (1 c- 2(T 2((T=kr)) )
x (T km)) I 12)
L - ( az) x exp
we have
I
Akn) (d || I I.
DKL (or-knn (-12)))))))) (1)))]ll (-)x)) _
-kn) (d+ ||x||²)
2.T.s..
with Lemma 9 and Eq. 14 implies the iteration number Zx of inner loops to be required as
Zk 20' (d m2) 12 29 (d + || 8=-
5 12- c in 1 C (d + mž) (262828--21 (d |x:11
2
22 3
12177.3 3-
3-
L' C (d+ m²) 2005))
kmmax
Ek.min
2 L
1 / 10 + m2) + In(d + ||x||
In
C8 C8OT + 36 + 4411
2DKL nm (12))
2 CLSIAT
5KL
when (n(c/) 2 2 and nd 2 2 without loss of generality.
For Term 2, we denote an optimal coupling between qr qr (z) and -n to be
E opp (9r (-1x), - An (-12))).
Hence, we have
2e (T-Kk)
Ex Ex bo (1/ (16)
Exoror en (,(( [x0]
1 e- e-2(T -(T
-T km)
x6) |I
4e 2(T
E(xoxx)
1 - e 2(T (xo (xx))
$ (1 -1-e-2 e -(T
E (xxox)) [1x0 - x611²
4e 4e- -2m
W2 (gT (122),, 4/ kn (-12))
(1 -2(
-2 2(T
DKL (dr- kn (11 (1x))
-2((T))n))
CLSIA
<81j C DKL
(52)
where the first inequality follows from Jensen's 's inequality, the second inequality follows from the Talagrand inequality and the last inequality follows from
2(T kn)
E -kn) <e-20 22 < -
e 2(T-- S 2
when 17 S 1/2. Therefore, sufficient condition obtain Term 2 S e2 to make the following
inequality establish
DKL (d (=1=)
2- 3- 22-3.p22 2 --
which will be dominated by Eq. 50 in almost cases obviously.
Hence, combining Eq. 17 Eq. 51 and Eq. 52 there is
[T/ml
Σ
n
EA
(x(en) 2V In - (xxm))1 s 10([T/n] N1)m-
(53)
33

---

Published as a conference paper at ICLR 2024
with probability at least (IT/n] - N1) 8/((T/nnl) which is obtained by uniformed bound. We require the gradient complexity in this stage will be
[T/ml
TT/ml
64
cost Σ
(Zx))
(Zx)
Σ
COTT (d (d+ 1-18111
L
k=
k=N++1
(54)
B [ (d+ mž) -29
29 (d | 8-5]
<([T/n] N1) CyC' m
17
39 8-6
where the last inequality follows from Lemma 14 Combining Eq. 49 and Eq. 54 we know the total gradient complexity will be less than
max (C CjOO)) C (d + m²) c-16n
16n-88 83 exp (5Oze 16n) 8-6.
Hence the proof is completed.
E AUXILIARY LEMMAS
Lemma 11. (Lemma of Vempala Wibisono (201 Assume = exp(-f) L-smooth. Then E2 V fll < dL.
Lemma 12. (Girsanov's 's theorem, Theorem 5.22 in Le Gall (2016)) Let Pr and Qr be two proba- bility measures on path space C ([0, T", ). Suppose under Pr, the process (
d&, = b,dt + o,dB,.
Under Qr, the process (Kt) (KE))E follows
dx: b, o,d and %0 X0-
We assume that for each 0, E Raxd is non-singular diffusion matrix. Then, provided that Novikov's condition holds
1 (T) 0. (b. - 6.) 60)1²²
Eqr
exp
< oo.
2 20
have
dPr
exp (f, of (Tr -bx) dB. /") | -i: (ir- br) 11" )((x) )
aQT
Corollary 2. Plugging following settings
Pr = ppr Qr Pr, b, == V by = x,+ 2 In pr pT
(x)), p V2a, and & (kn, (k++1)))
into Lemma 12 and assuming Novikov's 's condition holds, then we have
dPr
N
(k+1))
DKL. (Pr(l = Epr
E
[[ - 2V (xx)
d
Pr
k==
km
Lemma 13. (Lemma C.II in Lee al. (2022)) Suppose that p(æ) ((()) is a probability density function on Rd, where í fxx) is L-smooth, and let ()a(w) be the density function of (O, Ia Then for 202, it has
p(x)
S 6Lod 2Lo² |
(p* o
(x)
Lemma 14. (Lemma 9 in Chen al. (x) denote the forward process]
2022aa) Suppose that Assumption A and [A
hold. Let
1. (moment bound) For all I 2 0.
E
Xx |2] < d V m
34

---

Published as a conference paper at ICLR 2024
2. (score function bound) For all t 2 0,
E |
Ld. Ld.
Lemma 15. (Variant of Lemma 10 Chen et (222aa) Suppose that Assumption A2 holds. Let
(x),) denote the forward process For 0 _ < if S then
E ||x: - 2 (m +d) (t s)² 2 4d (t =s
Proof. According to the forward process, we have
EE I1I. x, + V2(B. Bs)
S E 2 J. x,
E
|x
x,
+ -B,1?
[ ||x,|| l1xp)l(drr)
27
f E
S2E
+ +4d 4d - (t s) 2
|| [|?
dr (t 5) + 4d (t [0-5
2 (m3 d) (1 5)² 4d (1 8)
where the third inequality follows from Holder's inequality and the last one follows from Lemma 14 Hence, the proof is completed.
Lemma 16. (Corollary 3.1 in Chafai 2004 ) If V satisfy LSI with constants o., & > 0, respectively, then D satisfies LSI with constant
Lemma 17. Let x be a real random variable. If there exist constants C, A < oo such that E [e>x] S
CE for all X 0 then
P(x20SCCn)
4A
Proof. According to the non-decreasing property of exponential function Ax we have
E
Axx S C exp (Ax² Xt),
P
= =P Ar
edt
The first incquality follows from Markov inequality and the second follows from the given condi- tions. By minimizing the RHS, i.c., choosing À t/(2)), the proof is completed.
Lemma 18. If satisfies log-Soboles inequality with log-Sobolec constant μ then every 1- Lipschitz f is integrable with respect and satisfies the concentration inequality
1ut2
v (f 2 [f + S exp
(-2
2
Proof. According Lemma 17 it suffices prove that for any 1-Lipschitz function with expec- tation [, = 0.
[e < (22/(2))
To prove this. it suffices, by a routine truncation and smoothing argument, to prove it for bounded, smooth, compactly supported functions such that /Vʃll S 1. Assume that f such a function. Then for every X 2 () the log-Sobolev inequality implies
2 E, /
|
Ent. (e^1)
which is written
22 E,
E, [AfeV]] - E, [e>]] log E [e>r] x
log
241
35

---

Published as a conference paper at ICLR 2024
With the notation (o(A) E |e^r] and (A)) log (A)), the above inequality be reformulated
as
(A) log + 1a Ey
2/1
A
(og +
2/ (2),
where the last step follows from the fact V I 1. Dividing both sides by (²))(A) gives
log(p(A)))
1
2p
Denoting that the limiting value log(p(A))
=== limx log(p(A))
[f[ O, have
(og(
//¹
A ((0((((())) ) 'tt S
A
24'
which implies that
X2
12
(AA)
(()) exp
2μ
2/1
Then the proof can be completed by trivial argument of Lemmal
17
Lemma 19. (Theorem in Vempala & Wibisono (209)) Suppose p. satisfies LSI with constant
I O and L-smooth. For any Xy ~ Po with DKL (pol(po co, the iterates X Pk of ULA with step size 0 < S TLx satisfy
SrdI.
DEL (pellPoe) S -usk DKL (pollp +
Thus, for any 8 > 0, achieve DKL (pellPoe) 5, it suffices to run ULA with step size
1 min { 1,
8
0 OC
2L
4d
for
1 log
20KL. (pollpco)
2
JUT
Lemma 20. (Variant of Lemma 10 in Cheng & Bartleti (0088) Suppose - -ln is m-strongly functiin for any distribution with density function we have
1
p(x)
DKL (pllp>0) S
p(x)
V In
dæ.
2m
(x)
By choosing p(z) (x))px /Ep [g²(x)) for the test function g: Rdd - and Ep. [92 oo, we have
Ep. [g2 In - Ep. [ In Ep. [o]] < 2 Ep. [IVol]].
which implies p. satisfies nn-log-Sobolev inequality.
Lemma 21. Using the notation in Table. 7 for each t. E [0, oo), the underlying distribution Pt of the forward process satisfies
t DEL (prllPso) S 4(dT. m2)) exp
2
Proof. Consider the Fokker-Planck equation of the forward process, i.e.,
dx: -x,d + V2dBr, Xo Po e- f,
we have
0x)((x)) V (p)(())))) + Apx - (V.(((e)VVnn
Pr (x
1 1
36

---

Published as a conference paper at ICLR 2024
It implies that the stationary distribution is
Pec x exp (-2 [|=o1())
(55)
Then, we consider the KL convergence of (x1)120, and have
(DellPillPee)
d di / ((((z) In (c(a)) dæ
(cp)(a)) In Pt(a)) dx
dl
Poo (xz
Poo (a)
= =f v. (a: Vl
In (x(
In (c dx Poo (z)
(56)
Poo (a:
- -- (2x)
v In pc(x)) (
2
dæ.
Poo (x:
According to Proposition 5.5.1 of Bakry al. (2014). if Pso is a centered Gaussian measure on R" with covariance matrix Σ, for every smooth function f on Rdd we have
Bysc [ log [ By. [ log p [ S 21 p
p EVS VS]
For the forward stationary distribution Eq. 55 we have E I. Hence, by choosing f(x) (2))))/poo(t)) we have
Pr Pr(ar) Poc (x)
|| dac
DEL (pellpoo) $ pz(
Vin
Plugging this inequality into Eq. 56 we have
dDLL (Pellee) pc(z)) V (c(x) |
1
dæ S DKL (De (lp
dt
Poo (x))
Integrating implies the desired bound,i.e..
(p.(pi)l S exp (-1) DKL (Poll>)))= exp (-1)
Lemma 22. Suppose fi IRd R and fo: Rd + - is u-strongly convex for ||>||| 2 R. That means
en (x) = [w //2 ||æe|i (and v2(x)= == f2(Ø) 1/2 || 13) is convex on S = Rd B(0, R).
Specifically, require that æ E Q, any convex combination of Σk= AcE with æ1, 3p satisfies
(x)
S
Auvi (a::).
Then, we have f1 + fo is st-stron convex for [ 2 R.
Proof. We define u(x) = f(x) x=| Hence, by considering E Ω and its convex combination of x: D
Eie Apaz with .1.--., my Ω have
u(x) - v (x)) S
X (x;) + Avu2(a;)) = Σ Arv(as))
Hence, the proof is completed.
Lemma 23. Suppose g is a distribution which satisfies LSI with constant μ. then its variance satisfies
((x)) ||= Eg [x]] dx < d
1
37

---

Published as a conference paper at ICLR 2024
Proof. It is known that LSI implies Poincaré inequality with the same constant (Rothaus 1981
Villani 2021 Vempala & Wibisono 2019). which can be derived by taking p - (1 + 71 v in
Eq. (10 Thus, for L-LLI distribution 9, we have
var, (g(x)) - 1 E.g [IVO(()1
for all smooth function g: R + R. In this condition, we suppose b [x], and have the following equation
/ ((x)) x E.y [x] 2
dx f ((x)) || -bll dx
/ (2x) (a: b,)² dx Σ / g(()) (1x, - (b, ((,,))))aa dx
i=1
Σ
/ ((x)) (ar, e.) - E,g (xx, e;))) dr Σ varg (9:(x))
where gx(x:) defined as gx) = (z, ei) and e; is a one-hot vector ( the i-th element e; is others are 0).
Combining this equation and Poincaré inequality, for each i, we have
var, (x)) - - [leel["] !
1
By combining the equation and inequality above, we have
/ 1x E., [x]1] dx Σ varg (9:(x)) S d
Hence, the proof is completed.
38

---

Published as a conference paper at ICLR 2024
F EMPIRICAL RESULTS
F.1 EXPERIMENT SETTINGS AND MORE EMPIRICAL RESULTS
We choose 1,0 particles in the experiments and use MMD (with RBF kernel) as the metric. We choose 7 E { In 0.99, In 0.95, - 0.9, In 0.8, 0.7). We 10, 50, or 100 iterations to approximate & chosen by the corresponding problem. The inner loop is initialized with importance sampling mean estimator sen from {1, 5, 10, 100). The outer learning rate chosen from (T/20, 1/10, T/5). When the algorithm converges, we further perform LMC until the limit of gradient complexity. Note that the gradient complexity is evaluated by the product of outer loop and inner loop.
100 particles. The inner iteration and inner loop sample-size are cho-
-1
-2
-2
-3
-3
2
4
IMC
2.0
LMC
LMC raMC
rdMC
1.5
rdMC
MMO
MWD
1.0-
w
50
100
150
200
50
100
150
200
50
100
150
200
gradi complexity
grad complexity
grad complexity
0.5
1.0
2.0
Figure 4: Maximum Mean Discrepancy (MMD) convergence of LMC, ULMC, RDMC.
2-
2
0-
-2
-4-
-4
-4.
-5
5
10
-5
0
5
10
-5
0
10
2.0
LMC
1.25
2.0
W
LMC
ULMC
ULMC
1.5
MM MMMMM Mw
ULMC
rdMC
rGMC
nGMC
MMO
0.75
MMD
0.5
0.0
0.0
50
100
150
200
90
100
150
200
50
100
150
200
grad complexity
grad complexity
grad complexity
r= 1.0
= 2.0
r" = 4.0
Figure 5: Maximum Mean Discrepancy (MMD) convergence of LMC, ULMC, RDMC.
F.2 MORE INVESTIGATION ON ILL-BEHAVED GAUSSIAN CASE
Figure demonstrate the differences between Langevin dynamics and the OU process in terms of their trajectories. The former utilizes the gradient information of the target distribution V Inp..
39

---

Published as a conference paper at ICLR 2024
to facilitate optimization. However, it converges slowly in directions with small gradients. On the other hand, the OU process constructs paths with equal velocities in each direction, thereby avoiding the influence of gradient vanishing directions. Consequently, leveraging the reverse process of the OU process is advantageous for addressing the issue uneven gradient sampling across different directions.
42-
40-
cod
-00
30
59
-30
20 30
-18
28
(O0 Ia)
Langevin
OU process
Figure 6: Langevin dynamics (reverse) OU process. We consider the sampling path between the 2-dimensional normal distributions (0, In) and (220,, 20), diagg 1)). The mean μ4 of Langevin dynamics show varying convergence speeds in different directions, while the OU process demonstrates more uniform changes.
In order to further demonstrate the effectiveness of our algorithm, conducted additional exper- iments comparing the Langevin dynamics with our proposed method in our sample scenarios. To better highlight the impacts of different components, chose the 2- 2-dimensional ill-conditioned
400
Gaussian distribution /V (20, 20),
(shown in Figure 7) as the target distribution to
0
showcase this aspect. In this setting, we obtained an oracle sampler for do enabling conduct more precise experimental analysis of the sample complexity.
10
9, made's 3
(00
N ((20, 20). diag 400, 1))
Initial distribution
Target distribution
Figure 7: Initial and Target distribution sample illustration.
SigurreBilluutratee the distributions samples generated by the LMC algorithm at iterations 10, 100, 1000, and 10000. It can be observed that these distributions deviate from the target distribution.
40

---

Published as a conference paper at ICLR 2024
13-
22-
33
-10
T 100
53-
06 74
22
-22
10
22
-10
T
1000
T 10000
Figure 8: Illustration of LMC with different iterations.
Figure 9 demonstrates the performance of the RDMC algorithm in the scenario of infinite samples, revealing its significantly superior convergence compared the LMC algorithm.
".....
(/(m)) = 10
T/(kn) 100
rin Ny 1es Ct..
30
-10
(/(ki) 1000
T/(kr) 10000
Figure 9: Illustration of RDMC (oracle sampler, infinite samples) with different iterations.
Figure 10 showcases the convergence of the RDMC algorithm in estimating the score under dif- ferent sample sizes. It can be observed that our algorithm is not sensitive to the sample quantity, demonstrating its robustness in practical applications.
41

---

Published as a conference paper at ICLR 2024
53
33 1o M/ Amag bortigt Seasery
-33
-10
sample size
sample size 10
41-
23-
13.
10-
-10
10
23
-22
28 20
sample size 100
sample size 1000
Figure 10: Illustration of RDMC (oracle sampler, finite samples, km) 100).
Figure Tacuureeilllseeeee illlstratts the convergence behavior of the RDMC algorithm with an inexact solver. It can be observed that even when employing LMC as the solver for the inner loop, the final convergence of our algorithm surpasses that of the original LMC. This attributed the insensitivity of the algorithm to the precision of the inner loop when t is large. Additionally, when t is small, the log- Sobolev constant of the inner problem is relatively large, simplifying the problem as a whole and guiding the samples towards the target distribution through the diffusion path.
40
32
23-
23
10
10
inner loop = 50
inner loop = 100
32
0
inner loop 500
inner loop = 1000
Figure 11: Illustration of RDMC (inexact sampler, finite samples, T 100).
F.3 SAMPLING FROM HIGH-DIMENSIONAL DISTRIBUTIONS
To validate the dimensional dependency of RDMC algorithm, we consider to extend our Gaussian mixture model experiments.
In the Sobolev distribution context (see Section 4.2.I). both the Langevin-based algorithm and proposed method exhibit polynomial dependence dimensionality. However, the log-Sobolev
42

---

Published as a conference paper at ICLR 2024
constant grows exponentially with radius R, which is the primary influencing factor. This leads to behavior akin to the 2-D example presented earlier. A significant limitation of the Langevin- based algorithm is its inability converge within finite time for large R values, in contrast to the robustness of our algorithm. In higher-dimensional scenarios (e.g., r = 2 for d = 50 and d = 100), observe notable decrease in rdMC performance after approximately 100 computations. This decline may stem from the kernel-based computation of MMD, which tends to be less sensitive in higher dimensions. For these large cases, LMC and ULMC fails to converge in finite time. Overall, Figure 12 exhibits trends consistent with Figure 3 corroborating our theoretical findings.
1.
ULCC rdMC
LLJCC
UUNC
LMC
IEMC
rEM:
2.5
0.5
3.50
1E5
153
700
100
0.0
1.3
53
100
120
230
companaity
1.5
ULMC
1.30
LMC
2.0
INMC
0.25
5.5
6.50
6.35
426
50
160
150
200
50 100
150
0:31
53
366
155
200
3.00
100
150
230
d
= 5
d 10
d
50
d 100
Figure 12: Illustration of RDMC and MCMC for high-ding loab-dimensional Gaussian Mixture model (6 modes). The first row shows the case of The second row shows the case of r 2.
For heavy-tail distribution (refer to Section 4.2.2), the complexity of both RDMC and MCMC are quite high, so it is not feasible to sample from them in limited time. Nonetheless, as our algorithm only has the polynomial dependency of d, but the Langevin-based algorithms have exponential de- pendency with respect to d, we may have more advantages. For example, we can use the 7ihh moment demonstrate the similarity of different distributions. To illustrate the phenomenon, we consider the extreme case - Cauchy distributior According to Figure 13 RDMC has better approximation for the true distribution and the approximation gap increases with respect to dimension.
Grund truth
107
Grond Inth
19a
Gizund tuth
roN:
10
10a
JMC
107
LMC
ULMC
10
104
10a
150
dimersion
clmeridion
dimenaiin
1st moment
2nd moment
3rd moment
Figure 13: Moment estimators for Cauchy distribution when n = 1000. It reflects the closeness between different distributions. For high dimensional moments, we computes the sum across all dimensions (trace) for proper plotting. The algorithm are evaluated with IK gradient complexity.
F.4 DISCUSSION ON THE CHOICE OF po
Note that different 인o may have impacts the algorithm. In this subsection, we discuss the impact of choice of No and try to make a clear demonstration for the influence in real practice.
Practically, selecting T determines the initial distribution for reverse diffusion. While any T choice can achieve convergence, the computational complexity varies with different T' values. According to Figure 14] we can notice that with the increase of T', the modes of pr tend to merge to single mode, and the speed is exponentially fast (Lemma 21). Even with T = - In 0.95, the dis-connectivity of modes can be alleviated significantly. Thus, the choice of T is not sensitive when choosing T from - In 0.95 to - In 0.7.
Thhe mean of Cauchy distribution does exist. We the case for better heavy-tail demonstration.
43

---

Published as a conference paper at ICLR 2024
0.7
T In 0.8
7 In 0.9
0.95
Figure 14: Choice of pr and the approximation by Pu- For T from 0.95 In 0.7, po can approximate pr properly, where each modes are connected to make the approximated distribution well-mixed. Then the RDMC can be performed properly.
However, when choosing too small or too large T, there would be some consequence:
If is too small, the approximation of Po would be extremely hard. For example, if O, the algorithm would similar to Langevin algorithm;
If T is too large, it would be wasteful to transport from T to 0.7 since the distribution in this interval is highly homogeneous
In summary, aside from the 7 - 0 scenario, our algorithm exhibits insensitivity to the choice of T (or Po). Selecting an appropriate T' can reduce computational demands when using a constant step size schedule.
F.5 NEAL'S FUNNEL.
Neal's Funnel a classic demonstration of how traditional MCMC methods struggle with conver- gence unless specific parameterization strategies employed. We further investigate the perfor- mance of our algorithm for this scenario. As indicated in Figure [3| our method demonstrates more rapid convergence compared to Langevin-based MCMC approaches. Additionally, Figure[[6]revall. that while LMC lacks efficient exploration capabilities, ULMC fails to accurately represent density. This discrepancy stems from incorporating momentun/velocity. Our algorithm strikes improved balance between exploration and precision, primarily due to the efficacy of the reverse diffusion path, thereby enhaneing convergence speed.
0.5
LMC
0.30
ULMC
ULMC
ULMC
0.4
nIMC
0.25
nIMC
0.20
HIMC
MMD
0.3
0.20
00.55
0.2
0.15
0.1
300 grad complexty
complexity
grad complexity
d 5
d
Figure 15: Convergence of Neal's Funnel for RDMC, LMC, and ULMC.
Ground Truth
LMC
ULMC
RDMC
Figure 16: Samples from Neal's 's Funnel.
It is possible consider varied step size scheduling, which be interesting future work.
44


Reviews:
[{"review_id": "ZFcngKoZCH", "reviewer": "Reviewer_UPK6", "summary": "This paper considers a diffusion modelling approach to the classical problem of sampling from an unnormalised density.", "questions": "My questions are as follows.\n\n1) at multiple points, the paper claims that the SDE resulting from the diffusion approach has better behaviour, e.g., the last sentence of Section 2.1 claims that the isoperimetric constant of this SDE is better. Right after Lemma 1, another claim is made \"It is important to point out that the property of $q_{T-t}(\\cdot | x)$ is better than $p_*$\". Here as well, the sentence is badly written (what property?) But in any case, these claims, as far as I am able to see are not rigorously proven.\n\n2) Theorem 1 *assumes* that $q_{T-{k\\eta}}$ is log-Sobolev, instead of proving something about it. As such I think the whole motivation is unclear as authors didn't show how ill-posedness is tackled by reverse diffusion approach.  Can authors show, if $p_*$ has a log-Sobolev constant, then $q$ does actually have a better behaviour in terms of this constant?\n\nSmall comments:\n\n- In Lemma 1, point out where the proof is in Appendix", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Sampling with reverse diffusions seem to have multiple advantages (compared to usual Langevin dynamics) in terms of how the algorithms behave. This paper builds on this observation and tries to bring the diffusion modelling methodology into regular Monte Carlo sampling.", "weaknesses": "Unclear writing and claims not supported rigorously. See more below in the questions part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0VTwKzEPFT", "reviewer": "Reviewer_dWe5", "summary": "The paper considers the problem of reverse diffusion Monte Carlo and shows that the score estimation can be viewed as a mean estimation problem by exploiting a decomposition of the transition kernel. The theoretical properties of the proposed method are extensively analysed. The performance of the proposed method is assessed on the Gaussian mixture models; it is illustrated that the proposed approach performed better than existing Langevin-type MCMC methods.", "questions": "It’s ok that for a non-expert in the specific topic, it may be hard to go over the proofs. However, I believe that a good and precise presentation of the theoretical results can lead to even a non-expert with enough theoretical background to follow and verify the results. Some representative things which could be improved:\n-\t In D2 (proof of lemma 2 and 3): the paper refers to Proposition 2 in Ma et al. (2019). However, I cannot find the Proposition 2 in Ma et al. (2019). \n-\tLemma 9: not an obvious mismatch between the statement of the lemma and the final line in the proof (RHS of inequality is d/mu for the former, 1/mu for the latter);\n-\tThe proof of lemma 9 starts with “It is known that LSI implies Poincare inequality with the same constant,…”. Perhaps a reference would help.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "-\tExtensive theoretical analysis of the proposed method.\n\n-\tGood performance on (a single) toy example.", "weaknesses": "-\tIt is quite hard work to verify the theory. I would expect nothing less from such a paper, so by itself, it is, of course, not a problem. However, I believe there is room for improving the clarity and flow of the proofs. \n\n-\tWith the current presentation of the results, it is hard to verify the reproducibility of the results; in the experiments, the robustness of the algorithms to the input hyperparameters (for example, the choice of step size \\eta in Algorithms 1/2).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ta6M9DwGlL", "reviewer": "Reviewer_qHDx", "summary": "This paper explores reverse diffusion in Monte Carlo sampling, transforming score estimation into mean estimation. The algorithm claims to approximate the target distribution accurately, especially for Gaussian mixture models, outperforming Langevin-style MCMC methods. They claim that this algorithm offers a fresh solution for complex distributions.", "questions": "Please refer to the weakness section.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- It is an extremely interesting problem to investigate. \n- It is easy to follow.\n- Theoretical results seem to support most of their claims.", "weaknesses": "- Lack of practical and experimental results for complex distributions e.g. high-dimensional multimodal distributions. The method's performance is based on empirical observations and may not generalize well across diverse datasets or problem domains. Its effectiveness might be limited to specific scenarios and may not be universally applicable.\n- Lack of complexity analysis. The combination of different sampling techniques (importance sampling, ULA) adds algorithmic complexity. Managing the interactions between these techniques and ensuring their proper integration can be challenging.  Also, The method might demand significant computational resources, especially when dealing with large sample sizes and high-dimensional spaces. This could limit its practicality for resource-constrained applications.  The sample size required for accurate estimation scales exponentially with the dimension due to the KL divergence between distributions. This exponential growth can make the method computationally infeasible for high-dimensional spaces. Could the authors please elaborate on these issues?\n- The accuracy of the estimation relies heavily on the dimensionality of the problem. High-dimensional spaces exacerbate the sample size requirement, making it challenging to apply the method effectively in real-world applications.\n- Creating n Monte Carlo samples at each iteration can be computationally expensive, especially if n is large. This might limit the method's scalability and efficiency for high-dimensional or complex distributions.\n- The method uses random samples $\\xi$ at each iteration. The quality of these random samples is crucial; if they are not truly random or are biased in some way, it can introduce errors in the sampled results. Furthermore, the way the samples are generated and combined in the update equation (step 6) could introduce bias if not done correctly. Biased estimators can lead to incorrect conclusions about the target distribution.\n-  The method's performance might degrade in high-dimensional spaces. Monte Carlo methods often face challenges in high-dimensional settings due to the curse of dimensionality, where the sampling space becomes sparse, making it harder to obtain representative samples.\n- How sensitive is this framework to initial distribution $p_0$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2KfT7SbITZ", "reviewer": "Reviewer_NhM6", "summary": "This work takes a very well-known reformulation of the score in VP-SDEs (see [1,2,3]) that is admissible to the sampling setting where one only has access to the density of the target distribution up to a constant unlike in standard diffusion models where one has access to samples. The authors propose estimating the score via MC, 100% akin to the heat-semigroup (Schroedinger Foellmer Sampler) approach in [4], which rather than time reversing a VP-SDE it can be seen as time reversing the h-transform of a pinned Brownian motion [9].\n\nThere is quite a bit of missing literature that has been already explored empirically over the last 2 years in the works of [1,2,3,4]  and also [5, 6, 7, 8].\n\nThe ULA-based estimators proposed in this work are the main novelty focus, furthermore, complexity guarantees are provided for these estimators and are shown to outperform vanilla ULA approaches, which is quite promising combined with the experiments added during the rebuttal. \n\nNotice that in contrast to parametric VI approaches the inner loop scheme proposed has theoretical guarantees for estimating the score that is practically feasible unlike [4,8] which is hindered nonpractical due to the. nonconvex objective required to train the NN estimators of the score.\n\n[1] Vargas, F., Grathwohl, W.S. and Doucet, A., 2022, September. Denoising Diffusion Samplers. In The Eleventh International Conference on Learning Representations. https://openreview.net/forum?id=8pvnfTAbu1f\n\n[2] Berner, J., Richter, L. and Ullrich, K., 2022. An optimal control perspective on diffusion-based generative modeling. In NeurIPS 2022 Workshop on Score-Based Methods.\n\n[3] Zhang, D., Chen, R.T.Q., Liu, C.H., Courville, A. and Bengio, Y., 2023. Diffusion Generative Flow Samplers: Improving learning signals through partial trajectory optimization. arXiv preprint arXiv:2310.02679.\n\n[4] Vargas, F., Reu, T. and Kerekes, A., 2023, July. Expressiveness Remarks for Denoising Diffusion Based Sampling. In Fifth Symposium on Advances in Approximate Bayesian Inference.\n\n[5] Huang, J., Jiao, Y., Kang, L., Liao, X., Liu, J. and Liu, Y., 2021. Schrödinger-Föllmer sampler: sampling without ergodicity. arXiv preprint arXiv:2106.10880.\n\n[6] Vargas, F., Ovsianas, A., Fernandes, D., Girolami, M., Lawrence, N.D. and Nüsken, N., 2023. Bayesian learning via neural Schrödinger–Föllmer flows. Statistics and Computing, 33(1), p.3.\n\n[8]  Tzen, B. and Raginsky, M., 2019, June. Theoretical guarantees for sampling and inference in generative models with latent diffusions. In Conference on Learning Theory (pp. 3084-3114). PMLR.", "questions": "Here are some suggestions:  \n\n1. For the MC estimator of the score of the forward SDE please cite [5] as the original work to propose this class of estimators for sampling with SDEs. This is not the score of an OU process it is instead the score of a \"pinned Brownian motion\" (A Brownian bridge like SDE which starts at the target distribution and maps it to a point mass). The authors might be tempted to argue that this is not the score however note that this quantity  (-logarithmic derivative of the value function) is related to the score by an additive term of $\\nabla \\ln p_t^{\\mathrm{ref}}$ where $p_t^{\\mathrm{ref}}$ is the marginal density of the associated reference process (in the case of an OU forward process this is just a linear term), see Remark 4 and its proof in [4].\n2. The authors should cite and acknowledge that their Lemma 1 (or exactly equivalent versions thereof)  have already been discussed and derived in the works [1,4] in the context of sampling, and mathematical optimization objectives which aim to learn an estimator for this exact same score the context of sampling have been explored empirically and theoretically in [1,2,3] (also 4 but this is concurrent work).\n3. Something that could strengthen the theory contribution is comparing to the Log Sobolev constant of the score in Schrodinger follmer samplers [5] (The score of a pinned brownian motion) and using this to quantify algorithmic design insights for the forward process.  \n4. Overall these theoretical contributions can have a stronger impact if written with the state of the current field on diffusion-based samplers in mind, and contextualizing how these results apply to practically successful methodologies. \n7. Note that since the estimator for the score is a ratio of expectations computed via MC the resulting estimator is itself biased, there is no discussion of this in the paper.\n\n**Update:** in the revised versions authors do a careful literature review of both prior and parametric methods which have already explored score-based time reversals for sampling, furthermore with the updated numerics found in the appendix the proposed schemes offer for a much more compelling story.\n\nTo justify the notable increase in score I will list a couple of points:\n\n* The log Sobolev constants derived for the OU process and the overall context of the analysis could be of further use and impact to works that focus on time reversal and gen modeling or time reversal and sampling. So there is a potential for impact beyond the proposed algorithm.\n* The assumptions in the work have been refined and the sketches are clearer to read in the revised versions.\n* The authors have been responsive and very helpful in clarifying points throughout the discussion (albeit a bit combative ... which is not ideal but to a tolerable level).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and formatted, and has the potential to become a theory-oriented paper with some extra work if the contributions are restructured,  and proper acknowledgments are made, this would require significant re-writing and further development and discussion of lemma 3 and proposition 2, and also theoretical comparison to other methods beyond ULA, simply the statement of these 2 results alone is not a strong enough contribution for ICLR. \n\nNote that the ULA-based estimators proposed in this work can be seen as a novel (e.g. Algorithm 2), however, without proper experimentation/numerics, this is still not a complete contribution either, currently, the paper is a lot of floating ideas without a concrete exploration of any particular, in part, this is due to the authors not being aware of the current state of the field. However, having to run a couple of inner ULA iterations every time one has to evaluate the drift is highly nonpractical, and claims made in the paper such as :\n\n\"\nVia this combination, we are\nable to efficiently obtain accurate score estimation by virtue of the ULA algorithm when t is close\nto T. When t is close to 0, we are able to quickly obtain rough score estimates via the importance\nsampling approach.\n\"\n\nAre highly unvalidated as 2 dimensional toy examples without proper comparison to other diffusion sampling-based approaches.", "weaknesses": "I will break this down into 2 subgroups\n\n1. Lack of Novelty (+ failure to acknowledge prior work)\n\n    *  Lemma 1 is very straight-forward and non-practical as you cannot sample from q, instead in practice the authors do IS and sample from the OU-process' transition kernel which is available analytically, which in turn results in expressing the score as done in [1] ( see equation 84 in [1] and the line that follows it connecting it to the score, or the equation above Equation 24 of the same paper ... or equations 10-13 in [4] ). \n\n2. The paper falls short as a sampling paper empirically\n\n    * Evaluations in 2d simply do not meet the bar for a conference paper. Methodologies such as SMC among many other modern ML variants are able to do quite well in multimodal 2d examples. \n    * This MC-IS method for estimating the score will NEVER work well in high dimensions due to variance and thus why works such as [1,2,3,4] which are clearly aware of this formulation (as they either state it in their appendices or use it for subsequent calculation) pursue an optimization alternative to estimating the drift.  See [5] Figure 2 for how poor the performance of these estimators is compared to LMC and alternative NN approaches for learning the score as dimension scales.  The authors briefly allude to this issue and propose combining with an inner ULA loop, however as before the authors missed that previous and more practical approaches (based on score matching) have already been developed to address this same issue, thus without any empirical validation and careful comparison it is very unclear why one would select the proposed approach.\n\nNote prior results establishing the exact same expressions for the OU-drift and similar expressions for score-matching SDEs applied to sampling have been public since late 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)