Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling
Authors: Wei Guo
Molei Tao
Yongxin Chen
Venue: ICLR 2025 Poster (2025)
Keywords: MCMC
Annealed Langevin Monte Carlo
Non-log-concave sampling
Non-asymptotic analysis
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We obtain the first non-asymptotic complexity analysis of annealed Langevin Monte Carlo for sampling non-log-concave distributions.

Abstract: We consider the outstanding problem of sampling from an unnormalized density that may be non-log-concave and multimodal. To enhance the performance of simple Markov chain Monte Carlo (MCMC) methods, techniques of annealing type have been widely used. However, quantitative theoretical guarantees of these techniques are under-explored. This study takes a first step toward providing a non-asymptotic analysis of annealed MCMC. Specifically, we establish, for the first time, an oracle complexity of $\widetilde{O}\left(\frac{d\beta^2{\cal A}^2}{\varepsilon^6}\right)$ for the simple annealed Langevin Monte Carlo algorithm to achieve $\varepsilon^2$ accuracy in Kullback-Leibler divergence to the target distribution $\pi\propto{\rm e}^{-V}$ on $\mathbb{R}^d$ with $\beta$-smooth potential $V$. Here, ${\cal A}$ represents the action of a curve of probability measures interpolating the target distribution $\pi$ and a readily sampleable distribution.

Published as a conference paper at ICLR 2025
PROVABLE BENEFIT OF ANNEALED LANGEVIN MONTE CARLO FOR NON-LOG-CONCAVE SAMPLING
Wei Guo, Molei Tao, Yongxin Chen Georgia Institute of Technology (wei. guo, mtao, yongchen) (ongchan))gattec... egatech.
ABSTRACT
We consider the outstanding problem of sampling from an unnormalized density that may be non-log-concave and multimodal. To enhance the performance of simple Markov chain Monte Carlo (MCMC) methods, techniques of annealing type have been widely used. However, quantitative theoretical guarantees of these techniques are under-explored. This study takes a first step toward providing a non-asymptotic analysis of annealed MCMC. Specifically, we establish, for the first time, an oracle complexity of Ō (
for the simple annealed Langevin Monte Carlo algorithm to achieve e² accuracy in Kullback-Lebbler divergence to the target distribution π & c-V on Rd with f-smooth potential V. Here, A represents the action of curve of probability measures interpolating the target distribution π and a readily sampleable distribution.
INTRODUCTION
We study the task of efficient sampling from a probability distribution e Rdd. This funda-
mental problem is pivotal across various fields including computational statistics (Liu) [2004] (0004/Broo Brooks
al.
2011), Bayesian inference (Gelman et al. 2013), statistical physics (Newman & Barkema and finance (Dagpunar) (007), and has been extensively studied in the literature (Chewi, The most common approach to this problem is Markov Chain Monte Carlo (MCMC), among
1999
2024..
which Langevin Monte Carlo (LMC) (Durmus et al. 2019 Vempala & Wibisono,
Chewi et al.,
Mousavi-Hosseini al. 2023) is a particularly popular choice. LMC can be understood as dineeiiscretization of diffusion process, known as Langevin diffusion (LD), whose stationary distribution is the target distribution n, and has been attractive partly due to its robust performance despite conceptual simplicity.
2022
Although LMC and its variants converge rapidly when the target distribution æ is strongly log- concave satisfies isoperimetric inequalities such as the log- Sobolev incquality (LSI) (Durmus) ctt al. 2019: Vempala & Wibisono 2019; Chewi et al.) 2002). its effectiveness diminishes when dealing with target distributions that tures of Gaussians. In such scenarios, the sampler often becomes confined to a single mode, severely limiting its ability explore the entire distribution effectively. This results in significant challenges in transitioning between modes, which can dramatically increase the mixing time, making it expo- nential in problem parameters such dimension, distance between modes, etc. (Dong & Tong 2022 Ma et al., 2019). Such limitations highlight the need for enhanced MCMC methodologies that can efficiently navigate the complex landscapes of multimodal distributions, thereby improving convergence rates and overall sampling efficiency.
strongly log-coneave or multimodal, such as mix-
To address the challenges posed by multimodality, techniques around the notion of annealing have been widely employed (Gelfand et al.) 1990 Neal 2001). The general philosophy involves con- structing a sequence of intermediate distributions no, T,,..., RM that bridge the gap between an eas- ily samplable distribution (e.g., Gaussian or Dirac-like), and the target distribution тM S. The process starts with sampling from Fo and progressively samples from each subsequent distribution until RM is reached. When म, and T close enough, approximate samples from m, serve as a warm start for sampling from T thereby facilitating this transition. Employing LMC within this framework gives rise what is known as the annealed LMC algorithm, which is the focus of

---

Published as a conference paper at ICLR 2025
study, Despite its empirical success (Song & Ermon 2019 2020 a thorough theoretical understanding of annealed LMC, particularly its non asymptotic complexity bounds, remains elusive.
Zilberstein al. 2023 2024)
In this work, we take a first step toward developing a non-asymplotic analysis of annealed MCMC. Utilizing the Girsanov theorem to quantify the differences between the sampling dynamics and reference process, we derive an upper bound on the error of annealed MCMC, which consists of two key terms. The first term is the ratio of an action functional in Wasserstein geometry. induced by optimal transport, to the duration of the process. This term decreases when the annealing schedule sufficiently slow. The second term captures the discretization error inherent in practical imple- mentations. Our approach challenges the traditional view that annealed MCMC is simply series of warm starts. Analyses based on this perspective typically require assumptions of log-concavity or isoperimetric inequalities. In contrast, our theoretical framework for annealed MCMC dispenses with these assumptions, marking a significant shift the understanding and analysis of annealed MCMC.
Contributions. Our key technical contributions are summarized as follows.
We propose a novel strategy to analyze the non-asymptotic complexity bounds of annealed MCMC algorithms,, bypassing the need for assumptions such log-concavity isoperimetry.
In Sec. 4. we investigate the annealed LD, which involves running LD with a dynamically chang- ing target distribution. We derive a notable bound on the time required to simulate the SDE for achieving e2 -accuracy in KL divergence.
Building on the insights from the analysis of the continuous dynamic and incorporating discretiza- tion errors, we establish a non-asymptotic oracle complexity bound for annealed LMC in Sec. 5) which is applicable to wide range of annealing schemes.
Comparison of quantitative results. The quantitative results are summarized and compared to other sampling algorithms in Tab. 1 For algorithms requiring isoperimetric assumptions, we in- clude Langevin Monte Carlo (LMC, Vempala & Wibisono (2019) and Proximal Sampler (PS, Fan iet al. (2023)) which converges rapidly but do not have theoretical guarantees without isoperimet- ric assumptions. For isoperimetry-Free samplers, we include Simulated Tempering Langevin Monte Carlo (STLMC, [Ge et al. (2018b)), tempering- -based sampler converging rapidly for specific family of non-log-concave distributions, and three algorithms inspired by score-based generative models: Reverse Diffusion Monte Carlo (RDMC, Huang et al. (2024a)), Recursive Score Diffusion- based Monte Carlo (RS-DMC, Huang et al. (2024b)) and Zeroth Order Diffusion- (ZOD-MC, He al. (2024)) which involve simulating the riverreversal of the Ornstein- Uhlenbech (OU) process and require estimating the scores of the intermediate distributions. Notably, our ap- proach operates under the least stringent assumptions and exhibits the most favorable e-dependence among all isoperimetry-free sampling methods.
Carlo
Related works. We provide a brief overview of the literature, mainly focusing on the algorithms for non-log-concave sampling and their theoretical analysis.
1. Samplers based on tempering. The fundamental concept of tempering involves sampling the sys- tem at various temperatures simultaneously: at higher temparatures, the distribution flattens, al- lowing particles to easily transition between modes, while at lower temperatures, particles can more effectively explore local structures. In simulated tempering (Marinari & Parisi 1992] Woodard et al.) 2009), the system's temperature is randomly switched, while in parallel tempering (also known as replica exchange) (Swendsen & Wang 1986 Lee & Shen 2023), the temperatures of two particles swapped according to specific rule. However, quantitative theoretical results for tempering limited, and the existing results (e.g.. Ge et al.] (2018a b); Dong & Tong (202)) apply primarily to certain special classes of non-log-concave distributions.
2. Samplers based on general diffusions. Inspired by score-based diffusion models (Ho et al. 2020
Song et al. 2022a b). recent advances have introduced sampling methods that reverse the OU pro- cess, as detailed in Huang et al.] 22024a|b;; He et al. (2024). These samplers exhibit reduced sensi- tivity isoperimetric conditions, but rely estimating score functions (gradients of log-density)
2

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of oracle complexities terms of d. E, and the LSI constant for sampling from π x "poly(-)" indicates a polynomial dependence on the specified parameters.
Isoperimetric
Other
Algorithm
Criterion
Complexity
Assumptions
Assumptions
LMC
C-LSS
Potential smooth
6², KT.(-11a)
O(CAde-2)
PS
C-LSI
Potential smooth
8, TV
O(Cd4/2 (ool///log"" loge-
Translated mixture of
STLMC
/
well-conditioned
E, TV
O(poly(d,E-1))
distribution
RDMC /
Potential smooth,
TV
(ppoly (d)ooydd)
nearly convex at do
RS-DMC
/
Potential smooth
[L
exp(O(log* " de d== 2)=
ZOD-MC
/
Potential growing at most quadratically
TV + W2
(xp(O( 1))
ALMC
Potential smooth
2², (L
Ö(dA(d)2E-
(ours)
via importance sampling, which poses significant challenges in high-dimensional settings. Coneur- rently, studies such as ZZhng & Chen (2022); Vargas et al.] (2023) 2024); Richter & Berner (2024) have employed neural networks to approximate unknown drift terms, enabling an SDE trans- port readily sampleable distribution to the target distribution. This approach has shown excellent performance in handling complex distributions, albeit at the expense of significant computational resources required for neural network training. In contrast, annealed LMC runs on a known inter- polation of probability distributions, thus simplifying sampling by obviating the need for intensive score estimation or neural network training.
3. Non-asymptotic analysis for non-log-concave sampling. Drawing upon the stationary-point anal- ysis in non-conves optimization, the seminal work Balasubramanian et al. (2022) characterizes the convergence of non-log-concaye sampling via Fisher divergence. Subsequently, Cheng et al. (2023) applies this methodology to examine the local mixing of LMC. However, Fisher divergence is a relatively weak criterion compared to more commonly employed metrics such total-variational distance or Wasserstein distances. In contrast, our study provides a convergence guarantee in terms of KL divergence, which implies convergence in total-variaton distance and offers a stronger result.
Notations and definitions. For a, b E R, we define [a, 6] b) n E, a ;= min(a, b). and a V b := max(a,b) b). For a, b > O, the notations a S b, a = O(b). and = M2(a)) indicate that Cb for some universal constant C > O, and the notations a x b and
@(b) stand for both a = Ob)) and O(a). Ō(.) hides logarithmic dependence in Q(-). A function U E (R(RR))) is a 0)-strongly-comee notal-variation (TV) distance is defined as TV v) = sup supA (M[A) v(A). and the Kullback- Leibler (KL) divergence is defined as (L(u||v) = E,, log du || represents the e² norm on R For f: d nd and probability measure μ on Rdd []f() (ʃ [[fllppp) $ and the second-order moment of μ is defined as E,p.I 112.
if V²U > aa,, and is 3(> 0)-smooth if -3T AT V 3 ,I. The
PRELIMINARIES
2.1 STOCHASTIC DIFFERENTIAL EQUATIONS AND GIRSANOV THEOREM
A stochastic differential equation (SDE) X (X1)te(0.7) is stochastic process on Ω C(O0, 2]; ITd), the space of continuous functions from [0, to gd The dynamics of X are typ- ically represented by the equation d.X, = (d) + a, (X)d, t E [O, where (Bi)e((o7) is standard Brownian motion in Fd. and (x( Rd. (X) E dddd depends on (X))))
Smoothness has several different definitions such heing C2 or C and the one used here is also common one appearing many standard texthooks in optimization and sampling, such as Chewi (0244
3

---

Published as a conference paper at ICLR 2025
The path measure of X, denoted Px, characterizes the distribution of X over Ω and is defined by IP (A) = Pr(X= E A) for all measurable subset of Q. The following lemma, as a corollary of the Girsanov theorem (Üstünel & Zakai 2013). provides a methodology for computing the KL divergence between two path measures and serves as a crucial technical tool our proof.
Lemma 1. Assume we have the following two SDEs on Ω::
dX,- = ax(X)dt + V2dB;, Xo ps
dy, : b,(Ydd + v2dB,, Yo ~ n.
Let p. and px denote the path measures of X and Y, respectively. Then
KL(PX)PPY) KI(N]))) ExxEx I'" [lax(x) -136)-b6(63 1 (x)
2.2 LANGEVIN DIFFUSION AND LANGEVIN MONTE CARLO
The Langevin diffuusin (LD) with target distribution e is the solution to the SDE
dX2, VVX,)) V2dB,, e [0): Xo μo-
(1)
It is well-known that under mild conditions, is the unique stationary distribution this SDE, and when ı has good regularity properties, the marginal distribution X, converges to т as t - to0, so sample from by simulating Eq. (1) for long time. However, in most of the cases, LD is intractable to simulate exactly, and the Euler-Maruyama discretization of Eq. (I) leads to the Langevin Monte Carlo (LMC) algorithm. LMC with step size h 0 and target distribution is a Markov chain { {X&r) k constructed by iterating the following update rule:
t xx e
((K+1)A Msh (X + V2((((+ BRR); h 0, 1, Xo 14:
where { (B(K+IJA BEN 1o=0, ltd. N (0,
2.3 ISPPERIMETRIC INEQUALITIES
probability measure и on Rd satisfies a log-Sobolev inequality (LSI) with constant C, or C-LSI, if for all f E C (RR)) with E, > 0,
f2 2CE, !
f log
12
A probability measure on Id satisfies a Poincaré inequality (PI) with constant C, or C-PI, if for all f C (TRd).
Var, f S CE.
is worth noting that a-strongly-tog--ooccav distributions satisfy 1 1-LSI, and C-LSI implies C-PI Bakry al. 2014). It is established in Vempala & Wibisono (2019) that when π xx e satisfies C-LSI, the LD converges exponentially fast in KL divergence; furthermore, when the potential V is 3-smooth, the LMC also converges exponentially with a bias that vanishes when the step size approaches 0.
2.4 WASSERSTEIN DISTANCE AND CURVES OF PROBARILITY MEASURES
We briefly introduce several fundamental concepts in optimal transport, and direct readers to author- itative textbooks /Villani 2008 202 Ambrosio et al. 2008 2021 for an in-depth exploration.
For two probability measures μ, on d with finite second-order moments, the Wasserstein-2 (W2) distance between μ and is defined
(11ke= 1100-11127(00 ydl27(dx, dyy) 1
Wo(usv) inf TEll(u.) (fll=
where ((),v) is the set of all couplings of (n, v). i.c., probability measure y on Rd Rd with (AA x Rd) ((A) and (Rd A) v(A), for all measurable set A Rdd
4

---

Published as a conference paper at ICLR 2025
Given vector field (or R re) and curve of probability measures p (pe))e(a.b)) on Ea with finite second-order moments. say that generates p if the continuity equation dep: + V (p.v)) = 0, E [a. holds. The metric derivative of at E [a, 6] is defined as
W2(P
Pplc = lim 8-+0
[8]
which can be interpreted as the "speed" of this curve. If lple exists and is finite for all t [a, b], we say that p is absolutely continuous (AC). AC a fairly weak regularity condition on the curve of probability measures. In Lem_ we present sufficient condition for AC as formal statement.
The metric derivative and the continuity equation are closely related by the following important fact Ambrosio et al. 20008] Theorems 8.3.1 and 8.4.5);
Lemma 2. For an AC curve of probability measures (Pt)te(a.)). any vector field (Vi)ee(a,)) that generates (pe))Eta.N) satisfies lple < [|oxlleP(e)) for a.e. l. E (a, b). Moreover there exists a unique vector field (o, )eEla,b) generating (Po)te(a,6) that satisfies løl = |10 (l(p(p)) for a.e. E (a
Finally, we define the action of an AC curve of probability measures (pr) as f pp As will be shown in the section, the action is key property characterizing the effectiveness of curve in annealed sampling. The following lemma provides additional intuition about the action and may be helpful for interested readers.
Lemma 3. Given an AC curve probability measures (Pt) and let A be its action. Then
A 2 W2 (po, pı), and the equality is attained when (Pr)cE(o,1] is a constant-speed Wasserstein geodesic, i.e., let two random variables (Xo, X1) follow the optimal coupling of (po. P1) such that X 11 W2 (po, p1), and define Pr the law of (1 t)Xo 1X1.
2. If satisfies Ciss (-SSI for all then A S So Ciss(Pt)) V log Pr p
If Pr satisfies Cpi(p:)-P1 for all t, then Σ fo 2Cpr(p:) log p. p1
The proof of Lem. can be found in App. A] The lower bound above can be derived by definition or via variational representations of action and W2 distance, while the two upper bounds relate the action to the isoperimetric inequalities, indicating that finite action requiring the LSI or PI constants along the trajectory. In fact, these bounds may not be tight, as demonstrated by the following surprising example, which the action polynomial with respect to certain problem parameters and even independent of some of them, whereas the LSI and PI constants exhibit exponential dependence. Its proof is detailed in App.
weaker assumption than
Example 1. Consider the curve that bridges a target distribution Po to readily sampleable distri- bution pt, in the form Pt. = po -' (0, 2SLT), / E [0, 1). for some large positive number S. Let A be the action of this curve. Then
1. A SS V log (oggslliap..) ds, where p. Ps/S = N (0, (0,2sl), S],
In particular, when Po is a mixture of Gaussian distribution E w N (mi o2,, then A S Sd log (1 + 25 is independent of the number of components N, the weights wi and the means pa. 3
However, in general, the LSI and Pl constants may depend exponentially on max, || Pýll. the maximum distance between the means.
PROBLEM SETUP
Recall that the rationale behind anncaling involves a gradual transition from To. a simple distribution that is easy to sample from, n the more complex target distribution. Throughout this paper, we define a curve of probability measures (TT) (TT))eEjoLI) along which we will apply annealing- based MCMC for sampling from т. For now, we do not specify the exact form this curve, but instead introduce the following mild regularity assumption:
5

---

Published as a conference paper at ICLR 2025
Assumption 1. Each has finite second-order moment, and the curve (To)ecjo.1) is AC with finite action A - -o | [/0.
For the purpose of non-asymptotic analysis, we further introduce the following mild assumption the target distribution x e on IR, which is widely used in the field of sampling (see Chewi (2024) for an overview):
Assumption 2. The potential V is B-smooth, and there exists global minimizer V such that |..||| S R. Moreover, π has finite second-order moment.
With this foundational setup, now proceed to introduce the annealed LD and annealed LMC al- gorithms. Our goal is to characterize the non-asymptotic complexity of annealed MCMC algorithms for sampling from possibly non-log con-log-concaye distributions.
4 ANALYSIS OF ANNEALED LANGEVIN DIFFUSION
To elucidate the concept of annealing more clearly, we first consider the annealed Langevin dif- fusion (ALD) algorithm, which samples from the e by running LD with dynamically changing target distribution. For the sake of this discussion, we assume the following: (i) we can exactly sample from no, (ii) the scores (V log mo mo))e((,11 are known in closed form, and (iii) we can exactly simulate any SDE with known drift and diffusion terms.
Fix sufficiently long time T. We define a reparametrized curve of probability measures (7, = Ti/T) Starting with an initial sample Xo ~ No. we run the SDE
dx,- V log 7. dX, + 2d, E [0,
and ultimately output XT ALD an approximate sample from the target distribution æ. Intu- itively, when Nt is changing slowly, the distribution of X, should closely resemble Tr, leading to an output distribution ALD that approximates the target distribution. This turns out be true, as is confirmed by the following theorem, which provides convergence guarantee for the ALD process. Theorem 1. When choosing T
1ga, it follows that (L[T||AALD) <
Proof. Let Q be the path measure of ALD (... (3) initialized Xn mo, and define IP as the path measure corresponding to the following reference SDE:
dx, (V log T. (x,, V2dB, Xo mo. t [0, T).
(4)
The vector field v = (v ( is designed such that X, ~ ग. for all E [0, T). According to the Fokker-Planck equation this is equivalent to the following PDE:
0. V (# Voog 7H + vx)) + Am; - (m,)), t E [0,
which means that generates (M == ,T,T) ;T/T) (E(O,TT We can compute KL. using Lem.
QL( Ep [" (X.)(X) 4 2 || [leell2
Leveraging Lem. 2 among all vector fields v that generate (#t Tt/T) 1E
choose the
one that minimizes || [[ thereby making ||va [LLG = |//,, the metric derivative. With the reparameterization ग. Te/r, we have the following relation by chain rule:
W2( mT)
Wo (2( Tt/T)
1
|
lim 8-0
lim
+
[6]
8-0
T/8/T|
Employing the change- launge-of-variiee variaabe formula leads to
KL(PIIQ) = 4 /' F
A
1+
4T
4T
Here, we assume that the solution (in terms of the curve of probability measures) of the Fokker-Plande equation given the drift and diffusion terms exists and is unique, which holds under weak regularity conditions (L Bris & Lions 2008).

---

Published as a conference paper at ICLR 2025
Finally, using data- tuta-proesssing inequality (see, e.g., Chewi (2024 Theorem 1.5.3)), with T
A 4e3
(L(TIIALD)) (L [T)) (L(P) Q) =
where Pr and Qr stand for the marginal distributions of P and Q at time T, respectively.
Let us delve deeper into the mechanics of the ALD. Although time the SDE (Eq. (3) distribution 7., the distribution of X₁ does not precisely align with म.. Nevertheless, by choosing a sufficiently long time T, we actually move on the curve (To))_[(o.1) sufficiently slowly, thus mini- mizing the discrepancy between the path measure of (e))) and the reference curve (Tt (T)))T( Using the data-pros data-processing inequality, we can upper bound the error between the marginal distribu- tions time T by the joint distributions of the two paths. In essence, moving more slowly, sampling more precisely.
targets the
Our analysis primarily addresses the global error across the entire curve of probability measures, rather than focusing solely on the local error at time T. This approach is inspired by (Dalalyan & Tsybakov (2012); Chen et al. (2023), and stands in contrast to the isoperimetry- -based analyses of
LD (e.g.. Vempala & Wibisono (2019); CChwi et al. (202);; [Balasbbramanian et al. (2022)) which focus on the decay of the KL divergence from the distribution of X, to the target distribution, and require LSI to bound the time derivative of this quantity. Notably, the total time T needed to the SDE depends solely on the action of the curve (TT)) obviating the need for assumptions related to log-concavity or isoperimetry.
is also worth noting that ALD plays critical role in the field of non-equilibrium stochastic ther- modynamics (Seifert 2012). Recently, refinement of the fluctuation theorem was discovered in Chen et al. (2020): Fu et al. (2021), showing that the irreversible entropy production in a stochas- tic thermodynamic system is equal the ratio of similar action integral and the duration of the process T, closely resembling Thm.
5 ANALYSIS OF ANNEALED LANGEVIN MONTE CARLO
is crucial to recognize that, in practice, running the algorithm requires knowledge of the score functions ( log No 1) in closed form. Additionally, simulating ALD (Eq. (3) necessitates dis- cretization schemes, which introduces further errors. This section presents a detailed non-asymptotic convergence analysis for the annealed Langevin Monte Carlo (ALMC) algorithm, which is prac- tical approach for real-world implementations.
The outline of this section as follows. We will first introduce family of the interpolation curve (Te | that serves as the basis for our analysis. Next, we propose a discretization scheme tailored to the special structure of (To )ee Finally, we state the complexity analysis in Thm. 2 and provide an example demonstrating the improvement of our bounds over existing results.
5.1 CHOICE OF THE INTERPOLATION CURVE
We consider the following curve of probability measures on Idd:
Th X exp (n](O - x(0) 2 ||- (1-112) 0 [0,
(5)
where the functions n(-) and X(-) are called the annealing schedule. These functions must be differentiable and monotonic, satisfying the boundary conditions t/u- = (0) 7 7111 = and The values of тo E [0, 1] and No E (1,+ are chosen that mo corresponds Gaussian distribution N (0, A 1 or can be efficiently sampled within Õ(1) steps of rejection sampling (see Lem. for details). We also remark that, under Assump. 2, my has a finite second-order moment Lem. 8 the proof), ensuring the W₂ distance between To is well-defined.
Ay X(0) A(1)
This flexible interpolation scheme includes many general cases. For example, Brosse et al. (2018) and Ge et al. (2020) used the schedule 17(-) = 1, while Neal (2001) used the schedule A(6) c(1 (0)). The key motivation for this interpolation is that when 0 predominates, making the potential of uo strongly-conves. with a moderate condition number, thus To is easy sample from; on the other hand, when 0 = л. is just the target distribution æ. As
the quadratic term

---

Published as a conference paper at ICLR 2025
8 gradually increases from to 1, the readily sampleable distribution To slowly transforms into the target distribution T1.
5.2 THE DISCRETIZATION ALGORITHM
With the interpolation curve (TH (=0)e chosen as above, straightforward yet non-optimal method to discretize Eq. (3) involves employing the Euler-Maruyama scheme, i.e.,
X R X; V log (X + V2(B - Bi). 0 s
However, considering that V log ( = - (+) VV(z) - > the integral the linear term be computed in closed form,
the exponential-integraat scheme (Zhang & Chen 2023 Zhang et al. 2023) to further reduce the discretization error. Given the total time 7, we define sequence of points 0 Oo < 01 exponentialiintegrat scheme is then expressed as
0M 1, and set Te T0,, he T(0, 02-1)- The
dx, dx.= (-7
VV(X,)
X, dt V2dB, t [0, X, No+
(6)
where t_ == T2-1 when & 1T ( 11 M
The explicit update rule is detailed in Alg.
with Iz denoting Xy,, and the derivation of Eq. (7) is presented App. C.I Notably, replacing
(V(X,)) with (V(X)) recovers the ALD classical LMC iterations.
Eq. (3),. and setting 1) and reduces to the
Algorithm 1: Annealed LMC Algorithm
Input: Target distribution π x ee-V. total time T, annealing schedule 17(-) and X(-), discrete points Co. ..., 0M.
For < < 0' < 1, define A0(0', exp (-r J A(u)du). (0',0) 0) (0',
/2T 10e O'(
H(0'00) 0) T q(u)Ao(u, d')du, and A, (e.g., using rejection sampling (Alg. 2)): ...,. .M do
Obtain sample
for
l. 1,
Sample independent Gaussian noise & N (0, 1); Update
It = Ao
1000 (1e,, 00
end
Output: TM ALMC, upproximate sample from
We illustrate the ALMC algorithm in Fig. The underlying intuition behind this algorithm is that by setting a sufficiently long total time the trajectory of the continuous dynamic (i.e., annealed IDD approaches the reference trajectory closely, as established in Thm. 1, Additionally, by adopt- ing sufficiently small step sizes h1,..., his, the discretization error can be substantially reduced. Unlike traditional annealed LMC methods, which require multiple LMC update steps for each in- a
termediate distribution T.,..., TMr our approach views the annealed LMC as a discretization continuous-time process. Consequently, it is adequate to perform single step of LMC towards each intermediate distribution Ty, Tru, provided that is sufficiently large and the step sizes appropriately small.
5.3 CONVERGENCE ANALYSIS OF THE ALGORITHM
The subsequent theorem provides a convergence guarantee for the annealed LMC algorithm, with detailed proof available App. C.2
Theorem 2. Under Assumps. and
2 Alg. 1
generate distribution ALMC satisfying
(LMAA & within
δ
5
calls the oracle of V and VV in expectation.
8

---

Published as a conference paper at ICLR 2025
LMC towards Tr.
2 ALMC
annealed LMC
7771
TT:
TT.
WTM-1
P: reference
70
NTM π
Figure 1: Illustration of the ALMC algorithm. The b-th green arrow, proceeding from left to right, represents one step of LMC towards Tr, with step size heg while each red arow corresponds to the application of the same transition kernel, initialized at #T,-, the reference trajectory P. which is depicted in purple. To evaluate (I](P[[Q. the Girsanov theorem implies that we only need to bound the aggregate KL divergence across each small interval (i.e., the sum of the blue "distances").
Sketch of Proof. Let Q be the path measure of ALMC EEq. (3)). the time-discretized sampling
process, whose marginal distribution at time I is the output distribution ALMC, Again, let P denote
the reference path measure of [q. (4) used in the proof of Thm. in which the same vector field
(ve)ee(o,7 ensures that X, ~ T, under P for all t E [0, Tý. Applying Girsanov theorem (Lem. I and carefully dealing with the discretization error, we can upper bound KT.(P]]Q) by
M
B T
-8
(L((II))
S
|= + 33 (1 + he (Bm(Oe) x(0--11))
The first summation is governed by the total time T, which pertains to the convergence of the contin- uous dynamic (i.e., ALD). Setting Tx $ ensures that the first summation remains O(s²), provided that the step size h2 is sufficiently small. The second summation addresses the discretization error, and it suffices determine the appropriate value of 6e to minimize M, the total number of calls to the oracle of V for discretizing the SDE. Combining M with the complexity of sampling from To determines the overall complexity of the algorithm.
Once again, our analysis relies on bounding the global error between two path measures by Girsanov theorem. The annealing schedule 17(-) and A(-) influences the complexity exclusively through the action A. This crucial identity, based on the choice interpolation curve (TT))e{(.1j) significantly affects the effectiveness of ALMC. Our specific choice (Eq. (5),, among all interpolation curves with closed scores, aims at simplifying the discretization error analysis. However, alternative annealing schemes could be explored to find the optimal one in practice. For instance, recent
paper (Fan et al. 2024) proposed an annealing scheme (x) xx To((1 - af)z) 1- ((=00)))) for some a E [0, 1] and E (0, 1]. The extra scaling factor 6+(1-6)0 might improve mixing speed. We leave the choice of the interpolation curve topic for future research.
We also note that our Assummp. encompasses strongly-log woa.gly--loccoccveee target distributions. For sam- pling from these well-conditioned distributions via LMC, the complexity required to achieve s- accuracy in TV distance scales as Ō(=-2) 2) (Chewi, 2024). However, using Pinsker inequality KI 2 2 TV2, our complexity meet the same error criterion is O(e-)), indicating a significantly higher computational demand. While our discretization error as sharp as existing works, the main reason for worse e-dependence is due the time required for the continuous dynamics con- verge, which is based on Girsanov theorem rather than LSI. While sharpening the s-dependence based Girsanov theorem remains challenge, our O(s O(--6) dependence still outperforms all the other bounds in Tab. without isoperimetry assumptions.
Finally, we conclude by demonstrating an example of a class of mixture of Gaussian distributions, which illustrates how our analysis can improve the complexity bound from exponential to polyno- mial. The detailed proof is provided in App.
Example 2. Consider a mixture of Gaussian distributions in IRd defined by EN EE P (ys, B-),, where the weights p; O, Σi=P: Pi 1, and ||yall r for all i E [1.N]. Consequently, the potential V - log n is B-smooth, where B 3(4r² 3 + 1). With an annealing

---

Published as a conference paper at ICLR 2025
schedule defined by n(.) = and X(0) = dB(1 8) for some 1 Y O(1), it follows that A = (d(((())))))) + (+² d
To show the superiority of our theoretical results, consider simplified scenario with 2, y/1 -22 and ,² > 8-1. By applying Ex. 2 and the Pinsker inequality, the total complexity required to obtain e-accurate sample in TV distance is , BB2 V d² d=)e==). In contrast, studies such as Schlichting 2019);; Chen et al. 22021); Dong & Tong (202)) indicate that the LSI constant of π is (( ) so existing bounds in Tab. 1 suggest that LMC, to achieve the same accuracy, can only
provide exponential complexity guarantee of Ō ((r"))
6 EXPERIMENTS
We conduct simple numerical experiments to verify the findings in Ex. which demonstrate that for a certain class of mixture of Gaussian distributions, ALMC achieves polynomial convergence with respect to r. Specifically, we consider target distribution comprising mixture of 6 Gaussians with uniform weights 8. means {r cos iT , rin kg k E [0. 5] }. and the same covariance 0.1/ {2, 10, 15, 20, 25, 30), and compute the number of iterations required for the empirical KI. divergence from the target distribution to the sampled distribution to fall below 0.2 (blue curve) and 0.1 (orange curve). The results, displayed in Fig. 2] use log-log scale for both axes. The near-linear behavior of the curves in this plot confirms that the complexity depends polynomially on r, validating our theory. Further details of the experimental setup and implementation can be found in App. F
(corresponding to 10 Ex. 2p. We experimented
KT. s 0.1
10
KL 5.2
0.2
# of iterations
10a
10
10a
Figure 2: Relationship between norm of means r and the number iterations to reach 0.2 and 0.1
accuracy in KL divergence, both in log scale.
CONCLUSIONS AND FUTURE WORK
In this paper, have explored the complexity of ALMC for sampling from a non-log-concave prob- ability measure, circumventing the reliance on log-concavity or isoperimetric inequalities. Central our analysis are the Girsanov theorem and optimal transport techniques, providing novel ap- proach. While our proof primarily focuses on the annealing scheme as described in Eq. (5) it can potentially adapted to more general interpolations. Further exploration of these applications will be key direction for future research. Technically, our proof methodology could be expanded to broader range of target distributions beyond those with smooth potentials, such as those with Hölder- continuous gradients (Chatterji et al. 2020 Liang & Chen 2022, Fan et al. 2023 Eliminating the assumption of global minimizers of the potential function would further enhance the practical appli- cability of our algorithm. Finally, while this work emphasizes the upper bounds for mon-llo-cconcve sampling, exploring the tightness of these bounds and investigating potential lower bounds for this problem (Chewi al. 2023a b) are intriguing avenues for future research.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We would like to thank Ye He, Sinho Chewi, Matthew S. Zhang, Omar Chehab, Adrien Vacher, and Anna Korba for insightful discussions. MT is supported by the National Science Foundation under Award No. DMS- 1847802, and WG and YC are supported by the National Science Foundation under Award No. ECCS- 1942523 and DMS-2206576.
REFERENCES
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient Flows: In Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics. ETH Zürich. Birkhääser Basel, edition, 2008, doi: 10.
Luigi Ambrosio, Elia Brué, and Daniele Semola. Lectures on optimal transport, volume 130 of UNITEXT. Springer Cham, 2021. doi: 10. 10.1007777----00-2200
pr wingger. com cwm/book/10/ /00ook/110.0 1007 978 030- 72162-6
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markov diffusion operators, volume 103 of Grundlehren der mathematischen Wissenschaften. Springer Cham,
edition, 2014. doi: 10. (0007998--331990000
Krishna Balasubramanian, Sinho Chewi, Murat A Erdogdu, Adil Salim, and Shunshi Zhang. To- wards theory of non-log-concave sampling: First-order stationarity guarantees for Langevin Monte Carlo. In Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Con- ference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 2896-2923, PMLR, 02-05 Jul 2022. URL http:htt:////tttt htttps://proceedingg wtwp:innn..m.....mmmmm.mm ptwss/v178/// ballaubraaanian228 html
Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. Handbbok of Markov chain Monte Carlo. CRC press, 2011.
Nicolas Brosse, Alain Durmus, and Érie Moulines. Normalizing constants of log-concave densities. Electronic Journal of Statistics, 12(1):851 2018. doi: 10.1214/18-ESS1411 URL hetps
//doii.org/// 10.
Niladri Chatterji, Jelena Diakonikolas, Michael I. Jordan, Peter Bartlett. Langevin Monte Carlo without smoothness. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 1716-1726. PMLR, 26-28 Aug 2020. URL httpa/rpprresesoooo/ttttttteeee
ht.l
Hong-Bin Bin Chen, Sinho Chewi, and Jonathan Neles-Weed. Dimension-free log-Sobolev inequalities for mixture distributions. Journal of Functional Analysis, 281(11):109236, 2021. ISSN 0022-
1236. doi: http:///oo.og////00010///.222..0
URL http:::ww..cceendd.i....
t. tt.com/ccii http://iiaaceeett...a./////////.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru Zhang. Sampling is casy as learning the score: theory for diffusion models with minimal data assumptions. In The Eleventh International Conference Learning Representations, 2023. URL dittps://openreviee
.net//foe leet:/forumm1dd=2LLWWgggsg
Yongxin Chen, Tryphon T. Georgiou, and Allen Tannenbaum. Stochastic control and nonequilibrium thermodynamics: Fundamental limits. IEEE Transactions on Automatic Control, 65(7): 2991, 2020. doi: 10. 00.10997AC.201992999900
Xiang Cheng, Bohan Wang. Jingzhao Zhang, and Yusong Zhu. Fast conditional mix- ing of MCMC algorithms for non-log-concave distributions. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural In- formation Processing Systems. volume 36. pp. 13374-13394. Curran Associates, Inc., 2023. URL htRps: http://ttte.e.ooeeeeaannooooooaa
1e/ 11220033330000555eeeeeeeeeerere0

---

Published as a conference paper at ICLR 2025
Sinho Chewi. Cog-Concave Sampling. Book draft, in preparation, 2024. URL http:::/thh/::::
inho. github. 10
Sinho Chewi, Murat A Erdogdu, Mufan Li, Ruoqi Shen, and Shunshi Zhang. Analysis of Langevin Monte Carlo from Poincaré to log-Sobolev. In Po-Ling Loh and Maxim Raginsky (eds.), Pro- ceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 1-2. PMLR, 02-05 Jul 2022. URL https: https:/ppoeeeeigggg .ml.. mmlr.
press/vi78 whwww/hw..weeccc... html
Sinho Chewi, Jaume De Dios Pont, Jerry Li, Chen Lu, and Shyam Narayanan. Query lower bounds for log-concave sampling. In 2023 IEEE 64th Annual Symposium Foundations of Computer Science (FOCS), pp. 2139-2148, 2023a. doi: 10.1 109/FFCS579990020225 200009999...20011111..
Sinho Chewi, Patrik Gerber, Holden Lee, and Chen Lu. Fisher information lower bounds for sam- pling. In Shipra Agrawal and Francesco Orabona (eds.), Proceedings of The 34th International Conference on Algorithmic Learning Theory, volume 201 of Proceedings of Machine Learning Research, pp. 375-410 PMLR, 20 Feb-23 23 Feb 2023b. BRL/stttp://ppoceeddii .om..ss...rr.......m............ mlr. press/v201 chw.w/3wwwwbbbbbb html
John S. Dagpunar. Simulation and Monte Carlo: With Applications in Finance and MCMC. John Wiley & Sons, Ltd, 2007. doi: 10. 00.1002/97804700613333
Arnak Dalalyan and Alexandre B. Tsybakov. Sparse regression learning by aggregation and Langevin Monte-Carlo. Journal of Computer and System Sciences, 7865):1423-1443, 2012. ISSN 0022-0000. doi: https://o..urrr//0000061/eess2s2 eedirect... com
URL https: www..w.w.. scienc JCSS Special Issue:
Cloud Computing 2011.
Jing Dong and Xin T. Tong. Spectral gap of replica exchange langevin diffusion on mixture distri- butions. Stochastic Processes and their Applications, 151:4 151:451 2022. ISSN 0304-4149. doi: 1016
006. URL /ttp:///////////////seeeeeeeeeee wttp://www.iieeneeiretttttctttte com/sc iette//arriccee/////334411222222
Alain Durmus, Szymon Majewski, and Blažej Miasojedow. Analysis of langevin monte carlo via
convex optimization. Journal of Machine Learning Research, 20(73):1-46 2019. URL httht
html
Jiaojiao Fan, Bo Yuan, and Yongxin Chen. Improved dimension dependence of a proximal algorithm for sampling. In Gergely Neu and Lorenzo Rosasco (eds.), Proceedings Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings Machine Learning Research, pp. 1473-1521. PMLR, 12-15 Jul 2023. URL http:///pp.cccccenooooooooeeee/a
Mingzhou Fan, Ruida Zhou, Chao Tian, and Xiaoning Qian. Path-guided particle-based sampling. In Forty-furst International Conference Machine Learning, 2024. URL https://openrre
view.
Rui Fu, Amirhossein Taghvaei, Yongxin Chen, and Tryphon T Georgiou. Maximal power output of a stochastic thermodynanic engine. Automatica, 123:109366, 2021.
Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprinl arXiv:2301.11235. 2023.
Rong Ge, Holden Lee, and Andrej Risteski. Beyond log-concavity: Provable guarantees for sampling multi-modal distributions using simulated tempering Langevin Monte Carlo. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cessa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018a. /tLLattess//pppoeeeess.oo.o.oopp le/ Bec/:55eee220s555577744401300082
wtt.s///apeeee/11/////// pdf
Rong Ge. Holden Lee, and Andrej Risteski. Simulated tempering Langevin Monte Carlo II: An im- proved proof using soft Markov chain decomposition. arXiv preprint arXiv: 18/2,00793, 2018b.
12

---

Published as a conference paper at ICLR 2025
Rong Ge, Holden Lee, and Jianfeng Lu. Estimating normalizing constants for log-concave dis-
tributions: Algorithms and lower bounds. In Proceedings of the 52nd Anmual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pp. 579-586, New York, NY. USA, 2020. Association for Computing Machinery. ISBN 9781450369794. doi: 10.1 10.1145/3377133384299 3384289
URL httthhtss:://dd .rg.
Saul Brian Gelfand, Sanjoy K Mitter, et al. On sampling methods and annealing algorithms. techni- cal report, 1990.
Andrew Gelman, John B. Carlin, Hal S. Stern, and Donald B. Rubin. Bayesian data analysis. Chapman and Hall/CRC, edition, 2013.
Ye He, Kevin Rojas, and Molei Tao. Zeroth-order sampling methods for non-log-concave distribu- tions: Alleviating metastability by denoising diffusion. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL httppss//ppenneevieww.oo
um um? mdm?ii==3A11 jullwwswwwwwww
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 15:6840-6851, 2020.
Xunpeng Huang, Hanze Dong, Yifan Hao. Yian Ma, and Tong Zhang. Reverse diffusion Monte Carlo. In The Twelfth International Conference Learning Representations, 2024a. http
8: s://openreviee net wotee//ooormm/ddkPyyyyee
Xunpeng Huang. Difan Zou, Hanze Dong, Yi-An Ma, and Tong Zhang, Faster sampling with- out isoperimetry via diffusion-basee Monte Carlo. In Shipra Agrawal and Aaron Roth (eds.), Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pp. 2438 2493. PMLR, 30 Jun-03 Jul 2024b. URL https:
/ppoceedings. , mlr. prwps /v24///2447
C. Le Bris and P.-L. Lions. Existence and uniqueness of solutions Fokker-Planck type equa- tions with irregular coefficients. Communications in Partial Differential Equations, 33(7): 1272-1317, 2008. doi: 10. 10.18800056050000111779555 URLlhttss:///c..ooo
1080/
03605300801970957
Holden Lee and Zeyu Shen. Improved bound for mixing time of parallel tempering. arXiv preprint arXiv:2304.01333,, 2023.
Jiaming Liang and Yongxin Chen. A proximal algorithm for sampling from non-smooth potentials. In 2022 Winter Simulation Conference (WSC), pp. 3229-3240, 2022. doi: 10.1109/WSC5734. 0022.10015293
Jaaming Liang and Yongxin Chen. A proximal algorithm for sampling. Transactions Machine Learning Research, 2023. ISSN 2835-8856. URL httpst:://peervvieeeeee wtw.l/eww.eee.oooo.eeoeeoeeooeoe forum?? CkXOw1hf27
Jun S. Liu. Monte Carlo strategies in scientific computing. Springer Series in Statistics. Springer New York, NY, 2004. doi:
Yuan Liu. The Poincaré inequality and quadratic transportation-variane inequalities. Electronic Journal of Probability, 25(none):1 1 16, 2020. doi: 10.1214/19-EJ4403. URL https://d/d...
org/10.1214/11 EJP403
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):20811- 20885, 2019. doi: 10. /10. 1073//0a3..... 820003116
URL https: //tw://wwwwww www..nna..or//oo.....
Enzo Marinari and Giorgio Parisi. Simulated tempering: A new Monte Carlo scheme. Europhysics Letters, 19())451, jul 1992. doi: 10. 12000009955577//1199600 URL https: /xxx do1. org
710.
13

---

Published as a conference paper at ICLR 2025
Alireza Mousavi-Hosseing Tyler K. Farghly, Ye He, Krishna Balasubramanian, and Murat A. Er- dogdu. Towards a complete analysis of Langevin Monte Carlo: Beyond Poincaré inequality. In Gergely Neu and Lorenzo Rosasco (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp- 1 1-35. PMIR, 12-15 Jul 2023. URL https: /ttppceee//cccceddeeeee ing.. mllr prwss http:/111///mmmmm mousavio -hosseini2a.... tm1
Radford M. Neal. Annealed importance sampling, Statistics and Computing, 11(2):125-139, April 2001. ISSN 1573-1375, doi: 10.1023/A:11008923211500 URL ltttps://dii.cg////
1223/: 000 T...//:100992221111111 9232210221188
Mark E. J. Newman and Gerard T. Barkema. Monte Carlo Methods in Statistical Physics. Oxford
University Press, 02 1999. ISBN 9780198517962. doi: 10. 00.1009//00007781188117666666
URL https: //di:
10. /tt.:///...0.000//01111111111111
001 0001
François-Pierra Paty and Marco Cuturi. Subspace robust Wasserstein distances. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5072-5081. 9a.h
PMLR, 09-15 Jun 2019. URI. httttttts////oceeeeeeee ngs. mmlgg.ml... 2oreas/v97/ae
Lorenz Richter and Julius Berner. Improved sampling via learned diffusions. In The Twelfth Inter- national Conference on Learning Representations, 2024. URL https::/ net
André Schlichting. Poincaré and log Sobolev inequalities for mixtures, Entropy, 21(1), 2019. ISSN 1099-4300. doi: 10.3390/e21100099. URL httph::////// h/wp:..://www..///// wwtp:/pwpp... comiiic.ommiii 1099--099999- 4300/21/
1789
Udo Seifert. Stochastic thermodynamics, fluctuation theorems and molecular machines. Reports on progress in physics, (5(12):12600) 2012.
Jaaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In Inter- national Conference on Learning Representations, 2021a. URR.https://ppeeeee net
/Eorum?id-Stlgiarrctt
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distri- bution. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates. Inc., 2019. URL /ttpttttp////rrccedddien/// 12230002554445532111060c71111333
cwtppppppcppppppppppppeppppp.e.. lacbeer__illeee #1les/papee/22199/F
Yang Song and Stefano Ermon. Improved techniques for training score-based generative mod- cls. In H. Larochelle, M. Ranzato. R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 12438-12448. Curran Associates, Inc., nww.inn wtt.rrisss.ccppppeppee ccppaper F1les/paper/2020/ff 2020. L.42239053111555722277722a222222
Yang Song, Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben
Poole. Score-based generative modeling through stochastic differential equations. In Interna- tional Conference on Learning Representations, 2021b. URL httpss://openeeview
Robert Swendsen and Kan-Sheng Wang. Replica Monte Carlo simulation of spin-glasses. Phys. Rev. Lett., 57:2607-2609 Nov 1986. doi: 10. 10.1103/PhysevvLett.5 57.26767 URL https://11
nk. aps / http://////.aaa...a........
Zoltán Szabó. Information theoretical estimators toolbox. Journal of Machine Learning Research, 15(9):283-287, 2014. http:t/:///....oo///...eaaa////e
Ali Süleyman Üstünel and Moshe Zakai. Transformation of Measure Wiener Space. Springer Monographs in Mathematics. Springer Berlin, Heidelberg, edition, 2013. doi: 10.1007/
14

---

Published as a conference paper at ICLR 2025
Francisco Vargas, Will Sussman Grathwohl, and Araud Doucet. Denoising diffusion samplers. In The Eleventh International Conference on Learning Representations, 2023. URL https:
Francisco Vargas, Shreyas Padhy, Denis Blessing, and Nikolas Nüsken. Transport meets variational inference: Controlled Monte Carlo diffusions. In The Twelfth International Conference Learn- ing Representations, 2024. URL
net/ feeetfoorum200 wow.mmiddPPlruddiie..
Santosh S. Vempala and Andre Wibisono. Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperinetry Suffices, volume 32.
Curran Associates, Inc., 2019. URL https: httpttttt:sppcceeeeeeeeee ngs neurips wwtp:sswwrrrrrreeeeeeeeeee cc/paper papppperrflle////eeaaaeeeeeeeeee 151lss/ppper22019/ le/ 65a9966733 905.oo//a511ffeeeeee0assa8833333
pdf
Cédric Villani. Optimal Trunsport: Old and New. Grundlehren der mathematischen Wissenschaften. Springer Berlin, Heidelberg, edition. 2008. doi:
URL https:
wwiik.ssrinnge www.book//coccoccooooooooooooooo 10. 1007
0000000/97700 9 540-71050-9
Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Society, 2021.
Dawn B. Woodard, Scott C. Schmidler, and Mark Huber. Conditions for rapid mixing parallel and simulated tempering multimodal distributions. The Annuls of Applied Probability, 19(2):617
- 640, 2009. doi: 10. 101114/00--AP555 URL https: :/ae:://doo... 1001:/00...1440-AAAA555555
Qinsheng Zhang and Yongxin Chen. Path integral sampler: A stochastic control approach for sampling. In International Conference on Learning Representations, 2022. URL https:
//open
Qinsheng Zhang and Yongxin Chen. Fast sampling of diffusion models with exponential integrator:
In The Eleventh International Conference on Learming Representations, 2023. URL https:
/ooeenevviww. net
Qinsheng Zhang, Molei Tao, and Yongxin Chen. gDDIM: Generalized denoising diffusion implicit models. In The Eleventh International Conference on Learning Representations, 2023. URL
hittps:/ccee httpss///eeereeee..comm net forum?1d=11hk9q4 oetaaa/reeeeee...eoooooooooooooo
Nicolas Zilberstein, Chris Dick, Rahman Doost-Mohammady Ashutosh Sabharwal, and Santiago Segarra. Annealed Langevin dynamics for massive MIMO detection. IEEE Transactions on
Wireless Communications, (2(6):3762-3776 2023. doi: 10. 100/TTC.202..32220000
Nicolas Zilberstein, Ashutosh Sabharwal, and Santiago Segarra. Solving linear inverse problems using higher-order Annealed langevin diffusion. IEEE Transactions on Signal Processing, 72: 492-505, 2024. doi: 10. 00.1009//SP200333348202.
A PROOF OF RESULTS ON ACTION
Lemma (Sufficient Condition for Absolute Continuity (Informal)). Assume that curve of prob- ability distributions (To)0E(0,1) on Rd has density क 1] x Rd (0, (0,z) + n Ta( > that is jointly C². Then, this curve is AC.
Proof. The following proof is informal. We leave the task of formalizing this statement for future work.
We first prove the result in one-dimension. Let Fo(x) f no (u)ddu be the c.d.f. of my, which strictly increasing as (π( > everywhere. As a result, its inverse F--! well-defined, and F-1 (.) also jointly C We know from Ambrosio al. (2008 Theorem 6.0.2) that
W3 (To, To+6) = L. (F Fg (4)
The above quantity should be O(82) d due the C property, and hence the curve is AC.
15

---

Published as a conference paper at ICLR 2025
In d-dimensions, consider the one-dimensional subspace robust W2 distance (Paty & Cuturi 2019) defined as
S2(,,)) = sup W2(py/4, upv), wEgá-1
where Sd-1 (0 E IRd ||a|| = tf is the set of unit vectors RR, and uy24 (respectively, v:2) the law of (u. X when X ~ ls (respectively, X v)) which is probability measure in IR. By Pary & Cuturi 2019 Proposition 2), W2( v) < vd)2(u, Similar argument above shows that (oyTe, 0yT6-66 = O(8²). and hence (T T046) = O(8))
Proof of
1. By Cauchy-Schwarz Schwarz inequality,
A = L/ 1plctt /.- 1dt (L (litt)
It remains to prove that W2(Po. p1) 1 So lt In fact, take any sequence 0 to < t1
IN = 1, and let Al maxisigN - 4-)... By triangle inequality of the W2 distance,
W2(po, p1) s
W2(Pe Pt. Pt.
W2(Pt,> Pti la 1i-1
(ti t;-1)
E(lpl. + o(At)))(t - t--1) S. löl.dt.
Another derivation is by investigating the variational representations of these two quantities. First, by Lem. 2. one can write
inf ve 0.pi (. ( || |1eel122pp)
A
1p7
On the other hand, the Benamou-Brenier formula (Amrossoo et al. 2008 Equation 8.0.3) implies
W/ (po. PL) (0r,ve): 0.pc+ V. (p p=0==00 / || 1
inf
Thus, one can easily conclude the desired inequality. To show that the inequality is attained when (Pt) kejo. is the constant-speed Wasserstein geodesic, note that the derivation implies that the inequality attained when lple is a constant for all E [0, 1]. and for any < L2 < 1, (2 (Pt)) + W2 (Pta Ptg) W2 (Pt,: Pts). We refer readers Ambrosio et al. 22088 Chapter 7.2) for the construction of the constant- Wasserstein geodesic.
2. It is known from Bakry et al. (204)) that satisfies C'-LSI implies
E log du
<L(uI|m) S 2
(L(U]T)) 2
W (H, Vp.
dr
20
Therefore,
V log Pr+s V log lel dp
82 (pt45s S (p.)(
By letting 6 + and assuming regularity conditions, we have
pp < (p.)² [10. pi p:l:pp Crst(P:) log pr
16

---

Published as a conference paper at ICLR 2025
3. By Liu 2020
know that satisfies C-PI implies
d dp (2, - $20 2C
(/
ddddp-1
du- 1). Ay.
do
Therefore,
1
W2 (p pi) s 20pi(pi) /
(pi+s - pi)2
dr.
8²
82pr
By letting 5 + O, we have
/ (Orpe)² dx (Cpr(p:)ll0, log pologpplll pollia()))
lpli s 2Cp1(pi)
Pt
Proof of Ex.
1. The reparameterized curve (px)se(o.s) satisfies the standard heat equation:
O.P: = Ap. = O.Ps + (p.(-V logp.)) = 0,
which means (-V V log Pa PE) (0 generates (p=) ().)] According to the uniqueness result in Lem. and also Ambrosio et al. 22088 Theorem 8.3.1), the Lebesgue-a.e. unique vector field (vf (ef)te(aM)) that generates (Pt)ce(a.0) and satisfies lple | [=)())) for Lebesgue-a.e. & (a, b) can be written in gradient field or" = Ve for some o, RR + R. This implies that
|p V log Ps 11
By the time change [0, 3 8 0 = s/S E [0, 1] and taking integral, we obtain the desired result.
Since P, E W. (ps (02 22))). by Lem. 7 know that V2 log I 02422" Thus
Lem. 6 implies | WVlopplll..gg 02426.50
d
d
Sd log 1+
25 x²
ASS
0² + 28
Finally, the LSI and constant of mixture of Gaussian distributions are, in general, exponential
with respect to the maximum distance between the means. To illustrate this, consider a simpler case where there are only Gaussian components:
|0, 021) (.[(y.o II). Schlichting (2019)
Section 4.1) has shown that (pr(p) s CiST(p) S o² (ellv11/dd +3). while Dong & Tong 2022
Proposition has shown that when ||y|| 2 ovd, Cisi(p) 2 Cpr(p) 2 li 2 1/0
B SAMPLING FROM To
Lemma 5. When vo = 0, mg = =N (0, 10) can be sampled directly; when no E (0, 1}. we choose Õ(1) An 7od3, that under Assump. it takes O v log mu@R² = queries to the oracle of V and VV in expectation to precisely sample from mi via rejection sampling.
Proof. Our proof is inspired by Liang Chen 2023 (0, 1]. The potential of To is Vú := VoV + Aa
We only consider the nontrivial case do which is (Au ston-sstrongyycconve and (An + -mmoot. Note that for any fixed point x' Rdd
112,
<b(x)= x exp (-v(())) < exp -Vo(2a) - (VVo(z)), -2)) Ao
7o a|
x x'(12)
2
The r.h.s. unnormalized density of m == N (s' VVola') 20 To-
The rejection sam-
pling algorithm is follows: sample Thp and accept X sample from To with probability
exp (Vo(X) + Vo(x') + (VVo(2'). x x²)= + Ao - no. || - x²113) E (0, 1].
2
17

---

Published as a conference paper at ICLR 2025
By Chewi 2024 Theorem 7.1.1), the number of queries to the oracle of V until acceptance follows a geometric distribution with mean
exp -VV('²') (VVo(>'), ), x²) 20-1101 || x' x²113) dx
f eexpl (-Vo(z)) dz
f Texp
-Vo(x') (VVo(x'), x x²) An-nol | x' 112 dx
f exp
Vo(x²) - (VV((>'), x²)
An t
| x 113 de
2
f Texp
(VVo(''), - 2u
||,0|3
dr
2
[exp
(VVo x) no | dx
f Texp
x + Ao 7o.5
VVo(=')
2
[Voo''') da
2(A0 No.8
Texp ʃ
VV6(=)
[VVC 2(Ao+
da
Aothoo
( No no,3
$
n
VVo
exp
to
70,33
X
To
g2
3oBd
n 3
S exp
Ao=
n
exp
A
no 32
VVo(2')11
We choose Åy = 7o such that exp also (1) as long as ||VV((=') S 3o.
pood Ao 1o3
S
With this Ao. exp
mo xX ng
VVo('')13)
is
Let x" be the global minimizer of the strongly convex potential function Vo. which satisfies 0 = VVo(=") no (Vx"") + Aox" 7n0 (x + mn.d".
Given the smoothness of Vo.
[VV((')) [Vo(2') VVo(<=)1 < (no.d + 31 x²112.
Therefore, to guarantee [Vo(2')1 2 3n3 it suffices to find an x' such that || - x"Il S Vioz
We first derive upper bound of ||~"| under Assump. 2 Since x. is global minimizer of V. (x") VV
3d||=
= V|VV("")
S B||2" - x.ll |l S *([1==1| + R2,,
R R
|| S
d
When R = O, i.e., 0 is known global minimizer of both V and Vo, we can directly set x' = 0: otherwise, need run optimization algorithms find such x'. According to standard results in convex optimization (see, e.g.. (..riggs & Gower (2023) Theorem 3.6)), rumning gradient descent on function Vú with step size Aut yields the following convergence rate: starting from To O, the 1-th iterate za satisfies
| - 2 (1
Ao - 1/,33
R2 d²
R
110 x
221
S
Àu + n
d
c'
where the last inequality holds when d 2 6. Thus, log Sn
O(1) iterations are sufficient to find
desired x'. We summarize the rejection sampling in Alg. 2 from Ty requires
In conclusion, precisely sampling
o I log 0
N0,3R2 d²
Ō(1)
calls the oracle of V and V in expectation.
18

---

Published as a conference paper at ICLR 2025
Algorithm 2: Rejection Sampling for :To
Input: и x exp (-V), 7o E (0, 1], Ào = noSd.
Let Vo == To + Ao 112:
Use gradient descent to find an r' that is
-close to the global minimizer of Vo:
VnuB
Let क. :=
VV(222 Au no 20.10.3
while True do
Sample th and U E [0, IJ independently; Accept X as sample of ho when
Ao no.3 | x 111))
U exp -Vo(X) Vo(a') + (VVo(x)), -
end
Output: X ~
Remark. The parameter R reffects prior knowledge about global minimizer(s) of the potential function V. Unless it is exceptionally large, indicating scarce prior information about the global minimizer(s) of V, this ((1) complexity is negligible compared to the overall complexity of sam- adjust the
pling. In particular, when the exact location of a global minimizer of is known, potential V so that becomes a global minimizer, thereby reducing the complexity to O(1).
C PROOFS FOR ANNEALED LMC
C.1 PROOF OF Eq. (7)
Define A(1) 1o' > (F) dr, whose derivative is A'(1) =x By Itô's formula, have
((cM()xx) ((1) (x (x(z) Xtdt + dxx,) e
VV + v2dB,
Integrating over E (Te-1, Te) (note that in this case t. = Te-1). 1). we obtain
e ((T)) ((T)) X2, - A(T 11 X',,,_ = (Tm
+V2 v2 (mn(( 1 ((r) A00dt vV(Xn-)) +
Tt
Tems
i...
X1, (A(T)) XTY-1 (1 ((#
t
(M(T)) vV(X
Tt + 2
Th-1
Since
A(Te) A(t) -,"
1TH ( (T)dr dr
( T:/T
JefT
Muuddu,
by defining (o exp (TT 18 M(u)du). we have -A((T)) -A0(0r,0-1)) Simi- larly, we can show that
Te 1"
1
(A(T2) (A(T))-A(t))dg
TT
1
Ao
Te t
dt T
(()) u)du,
T
T T
Jo
and 2 TT
(A(T:) (A(T:)-A())ddL)) is zero-mean Gaussian random vector with covariance
11 ((((T)) 100) = Ag
T
/ 9r
2
di = 2T
A2(0e, u)du T.
TT-1
T
T
19

---

Published as a conference paper at ICLR 2025
C.2 PROOF OF THM.
We denote the path measure of ALMC (Eq. (6) by Q. Then, Qr. the marginal distribution of Xr, serves the output distribution ALMC Similar to the methodology in the proof ThTm. to denote the reference path measure of Eq.. (4) which the vector field (E))) generates the cure of probability distributions (=).)
Using the data drocesssgs inequality, suffices to demonstrate that KL(PIIQ S 5?. By Girsanov theorem (Lem. and triangle inequality, we have
(VV(X))- - VV(X, )) (x,)) 1
(P((IQQ
=
4
Jo
EF
T
de
Ep
V
[VV(X,) - VV(X, )11 11ex dl
0
Ti
Tx
E - X 1l / 1ee.l
$ 1=1
82
T
Th-1
The last inequality arises from the smoothness of V and the increasing property of 17(+). To bound Ep| - X,_ note that under P, for & E (Te-1, Te), we have
X, X1 = ff Tem.
(Vlog + +r
v2(B, BI.-.).
Thanks to the fact that X2 ~ H under P.
Ex x. 11 < E, I'
(Vlog 7. + uz) uz) (X,) V-E/V2(BB BTT_,)112
T
$ (1 Te-1)
EF|[( log + (x+) + d(l - TT-1)
17-1
S Te-1) /"
1Vlog=~1122<0 + || 110=1122(0))) dr dll Te-1)
he 1T) JT-1
(IVlog
+ |1 |10 dr dhe.
The second inequality arises from the application of the Cauchy-Schwerd inequality, and the last inequality is due to the definition h = Ti - Th-1- Taking integral over t E [Te-1, Tel.
1"h (IVlogTellAA + (Ivellea(a))) dt + dh?
Te
E X T--1
X 1d S S22 h2
Te-s
Recall that the potential of गे (1) (+)) smooth. By Lem. 6 and the monotonicity of n(-) and X(-), have
Te <
(Th
d
d(1)
t
(
V log w
Telli
3
A
de
T
T
JT-1
T
T
< dhi
Bn
+
T
dhe (3n (0e) X (0:-1)).
20

---

Published as a conference paper at ICLR 2025
Therefore, QP] is upper bounded by
M
/ E xx_ 12 + [" lIvell IleelBaa,,
1 (0c)² 82
M
dhi (8n (Bn (0s) + A ((6-11) + h2 1"
1 (a dt + dhi + L ll 1
17 (0b)2 82
T
Te L T
(1+m t=1
( dt + n(Oe) dhž (1 he (3m(0z) + x(0--1)))
For the remaining integral, given that (e))) generates (#e (TE)) according choose such that
Lem. 2 we may
= | Thus,
fT
|I I1aellize,, dt /" FR
Te
f Te 1
1 0=
+ 11
1
T
Jn
JT,, T2
T 80-1
through a change-of-variable analogous that used in the proof of Thm.. 1 Therefore,
M
(LI(PIQQ)
S
|= + 3100)) dng (1 + he (Bn(0e) x(0--))))
T
8=1
Assume hi S 32
(which will be verified later), can further simplify the above expression to
M
1
9:
QL(PIIQ
10 n((e)² pdh?
T
1=11
M
A
+
3
11
T
t=1
M
A
T +
3 d Σ
21 0
To bound the above expression by e2, we first select T x 4, mirroring the total time 7 required for running annealed LD as specified in Thm. I This guarantees that the continuous dynamics closely approximate the reference path measure. Given that nT-) S 1, remains only to ensure
1
M
sdd (0())2T22 22 t=1
Σ 0 02-1) S
t=1
which is equivalent to
M
(0 0 0
<
(8)
A2
To minimize M, apply Cauchy-Sehwarz inequality:
Ad
M
M (0
2
Σ
Σ
O0 0 02-1)
2
Σ
0c 01-1)
= 1,
[=1
which establishes a lower bound for M. The equality is achieved when 0, - 0.-1 = l E [1, MJ. Thus, selecting
for all
M
d A2 6
M ~
satisfies the constraint given in Eq. (8) In this case, the step size he T/ कØz S 33- Combining this with the Ō(1) complexity for sampling from no, have completed the proof.
21

---

Published as a conference paper at ICLR 2025
D PROOF OF EX. 2
The smoothness of V comes from Lem.
Note that (2x) Ei Pj exp
(- -111 will?) and define
A |0:1
(x) X (T) exp
X
À B
3
2
pj exp
2(A + 3)
|
2
x
A +
B
M1
N
+ 8
B
exp
2
À + 3
1=1
3
P&N
A
X+
We use coupling method to upper bound (m xx+6). We first sample I following distribution
P(I = i) = Ps. E [V. and then independently sample n N (0, We have
B +
X =
A+
91
VA+
n~ TA.
3
1
Y A 3
+
V++0+B "
R246-
By the definition of the W2 distance, we have
(ax, & E 2
B
1
= E,
+
3
X
X
+3
y1 +
VA+B
VA+0=
- 3
11
3
B
1
1
2
E,
11
A+ 3
A+
V B
VA+0+B
3
1
1
d.
A B B
X+0+
VX+3
VA+
This implies
W #x+6)
82,2
d
lim
+
82
(X + B)4
4(A + B)3"
By time reparameterization To = (00; #10- = ( (\(0)). With X(0) = Ao - 8)', (²(0) =
7) 0)1-1 < 7 25 Ap- Therefore,
{-' 1 17
A =
| 12
(100)/000000000000 No //m
do
3 Ao
FRBdA
Aa
82,2
d
Ao
+
da
(A+
4(A + B)3
1
1
S Ao
8
g3
S dd 3 ++1)
1 +
2
d
3
d(r 3 + 1)
y2+
3
follows from the proof that as long as maX ((()) is bounded by a polynomial function of B, d and r, is the action A.
22

---

Published as a conference paper at ICLR 2025
E SUPPLEMENTARY LEMMAS
Lemma 6 Chewi 20044 Lemma 4.E.1)). Consider probability measure ps & e-U on R. If
V 3 31 for some B > 0, then E |V 3d.
Lemma 7 (Cheng al. (2023 Lemma 4)). For Gaussian mixture distribution
Σ, WiN (4i,0"I), we have
(
maxij
1= - log 3 0² T2.
02
20
Remark. This is a slightly improved version, as in the original lemma the authors omitted the factor 2 in the denominator on the l.h.s.
Lemma 8. Under Assump. 2 To defined in Eq. (5) has finite second-order moment when r7()) [0, 1].
Proof. When v)()) = 1, To x exp (-V - x(0) 1111)) & exp (-V), and the claim is straightfor-
ward. Otherwise, by convexity of u + c we have
exp (-n(0)v - X(0)
X(6)
2 11 -1-113) = exp
-n((OV - (1- (11-n(0) 2(1 ((0) |1 11.12)
S (0)) cxp (-V) + - ())) exp 2(1 (0)) || -1.1) -PP).
X(0)
Multiplying both sides by || 1| and taking integral over Rdd we see that Exp 11 < +00.
F FURTHER DETAILS OF EXPERIMENTS IN SEC. 6
Hyperparameter settings. For all the experiments, we use the annealing schedule A(0) 5(1 0)10 and (0)
The step size for ALMC designed to follow a quadratic sched- ule: the step size at the E-th iteration (out of M total iterations, l E [1, M]) is given by Smax -amin (e- M M2/4
2 )² + Smax. which increases on |0, and decreases on 2 .M). with a max-
M
imum of Smax and minimum of Smin- For
2, 5, 10, 15, 20, 25, 30, the M we choose are 200, 500, 2500, 10000, 20000, 40000, 60000, respectively, and we set 5max 0.05 and smin 0.01, which achieve the best performance across all settings after tuning.
KL divergence estimation. We use the Information Theoretical Estimators (ITE) toolbox (Szabó) 2014) to empirically estimate the KL divergence. In all cases, generate 1000 samples using ALMC, and an additional 1000 samples from the target distribution. The KL divergence is estimated using the i ite. cost BDKL. Knnk () function, which leverages k-nearest- neighbor techniques to compute the divergence from the target distribution to the sampled distribution.
Regression coefficients. We also compute the linear regression approximation of the curves in Fig. 2) via aallearn.iinee model. wwe.llLnnneaaeeessseeeeee 2.841 and an intercept of 1.257, while the orange one has slope of 2.890 and an intercept of wellearn.eetrico.mmmmm
The blue curve has a slope of
0.904. The R² scores, calculated using sklearn. met iss. r2 r2_score, are 0.995 and 0.997, respectively.
23


Reviews:
[{"review_id": "ycRrEQkPQG", "reviewer": "Reviewer_4z2B", "summary": "The paper studies the convergence of annealed Langevin algorithms for general, possibly non-log concave, target distributions. The authors propose using an argument based on Girsanov's theorem to bound the distance between a reference process and a Langevin SDE that is based on an annealing schedule of target distributions, bridging the target to a base distribution. The authors also consider a practical implementation of the continuous time SDE, based on the exponential integrator scheme.", "questions": "- Theorem 2 uses Lemma 1, that is a consequence of Girsanov's theorem. As far as I understand it uses it to bound the KL between the SDE in Equation (6) with the \"true\" SDE, that is Equation (4). However, the SDE (6) clearly does not fit into Lemma 1 of the paper, since a term in the drift depends on a past state. The authors should explain their reasoning and not just refer to Lemma 1, which is not general enough.\n\n- in Lemma 2, in what sense do the authors say the equality is \"reachable\"?\n\n- in lines 373-374 the authors state that the Euler scheme is \"non-optimal\", without a supporting reasoning. What are their reasons for writing that?\n\n- In Example 1, the authors say that \\rho_1 is \"readily sampleable\". Is it then the case that \\rho_0 is a simple distribution that can be sampled? Here the notation is not clear yet. Also, in point 2. of the example, are the LSI and PI constants exponentially dependent on d for the distribution \\rho_t for any t? In general, this example could be made clearer.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors consider an interesting problem, which is actively researched. Most of the research has focused on obtaining convergence bounds for standard Langevin algorithms imposing strong assumptions on the target distribution, such as log-concavity or log-Sobolev inequalities. The approach in this paper seems original, since it differs from strategies that are typically used in the literature as explained by the authors. Moreover, it gives convergence bounds in KL for an annealed Langevin algorithm, for which few results are available, and under \"weak\" conditions. Overall, the paper is clear enough to follow what the authors are doing and has a cohesive story.", "weaknesses": "- The authors consider a specific annealing schedule and it is not clear if their results give any kind of clarity on how the schedule affects the overall complexity of the algorithm. \n\n- In several occasions I would have appreciated clearer explanations. For instance, why considering the exponential integrator scheme instead of an Euler scheme? Why considering that specific annealing schedule? It is also not completely clear why one finds the topics in Section 2.4 at a first read. It would be beneficial to convince the reader that these mathematical concepts are needed, also giving an idea of how these are useful in what follows. \n\n- The sketch of the proof of Theorem 2 is not very clear to me and I find it should be heavily improved. It seems the authors compute the KL between two processes, neither of which is the discretisation scheme. Then the notation in the proof in the appendix seems inconsistent, denoting by \\nu^{ALMC} the measure of another process. As I motivate in the Questions section below, I struggle to see how the authors use Lemma 1 in the proof of this result. This should be clarified if the paper is to be considered for acceptance.\n\n- the contribution is in general interesting, but I would have liked to find analyses such as some (simple) numerical simulations showing that the convergence of the algorithm is for instance not exponential in the dimension.\n\n- Table 1 gives an overview of results available in the literature, but these are for various algorithms which are denoted by corresponding  acronyms.  This is not a very clear comparison in my opinion, and it would be nice to have a short explanation at the differences between these algorithms.\n\n- the intuitive explanations in lines 318-323 are rather obvious and are not really clarified by the results in the paper. This should be clear to the reader to avoid confusion.", "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": "jx9UP0G5Ii", "reviewer": "Reviewer_KRFS", "summary": "The paper proves new bounds on efficacy of Annealed Langevin MC by creating an SDE which approximates the target and then analyzing the discretization error introduced by simulating it on a finite machine", "questions": "What does $\\beta$-smoothness imply about the target distribution? Can we know this in general, especially where the density arises from a posterior? It seems like this quantity would be hard to calculate for even tractable likelihoods, let alone general posterior densities.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Computational bounds are generic- a smoothness constraint for target distribution, rather than isoperimetry assumptions.\n\nExplanations are clear and well-illustrated, suiting a broad generalist audience by mixing intuition-building and commentary.\n\nThe direct impact of this paper is unclear, but the methods it introduces are interesting contributions", "weaknesses": "The paper shares the weakness of most such oracle inequalities, which is that they reassure us of convergence of an algorithm under assumptions that are hard to verify on a particular problem\n\nNote that I am not expert in all the components of the authors' proof, and have taken some steps on faith.", "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": "r4LlBy2oiB", "reviewer": "Reviewer_WqFj", "summary": "The paper proposes a novel analysis of Annealed LMC which uses a specific scheduling system. The latter allows to benefit from another analysis scheme which uses the action on curves instead of isoperimetric inequalities.", "questions": "- Is the analysis using the action only available for annealing? Can we gain anything by applying this technique to LMC in the standard setting?\n- What are the estimates of the action parameter $\\mathcal{A}$ for a more general class of distributions than the mixture of Gaussians?\n- Is it possible to guarantee that for certain target distributions and schedules Assumption 1 is satisfied? This is important, as it is not easy to manually check for every setting. \n- Is there always a $v_t$ such that $X_t \\sim \\tilde{\\pi}_t$ for all $t$ in (4) and it generates $\\tilde{\\pi}_t$ i.e. satisfies the Fokker-Planck equation?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper provides a concise analysis with a clever mathematical trick of using the action of the curve instead of the isoperimetry constants. Assuming gradient Lipschitzness of the potential function allows to easily (rejection-acceptance) sample from an initial distribution, which then allows to sample from the target distribution (non-convex, gradient-Lipschitz) using an annealing schedule for LMC.", "weaknesses": "- Assumption 1 is not well discussed. One cannot verify beforehand whether the curve $\\pi_{\\theta}$ is AC. How should it be done? See the respective question in the section below. \n- Assumption 2 is not the classic smoothness assumption. Instead it is the gradient Lipschitz continuity, which is stronger. This should be explicitly mentioned in the paper. \n- The notation is slightly confusing. There are too many indices for $\\pi$ and the usage is incoherent. The reading would be rather simplified, if the notation was more developed.  \n- Simple experiments on sampling from a mixture of Gaussians using the proposed and existing methods would significantly boost the paper. \n- In the abstract of the paper, the authors claim that their analysis is non-asymptotic, however it is not true. Theorem 2 (main result) and related results are given with $\\tilde{O}(\\cdot)$. \n### Mathematical comments \n\n- *The equation after line 1077* in the proof of Example 2 is incorrect. The density of the sum of two independent random variables(vectors) is the convolution of their densities rather than their product. Thus, the variable $X$ is not distributed as $\\hat{\\pi}_{\\lambda}$. This serves as the cornerstone of the remainder of the proof, which means that the proof is incorrect. \n- *The third line in the proof of Example 2* is incorrect. After recentering the Gaussians, the authors erase the terms $\\exp(-\\frac{2\\lambda \\beta}{\\lambda + \\beta})\\|y_i\\|^2$ with the $\\propto$ sign. Since we have different $y_i$'s, the resulting mixture weights will be different from $p_i$. Nevertheless, this could be fixed by replacing $p_i$ by some $q_i$'s. \n- *Paragraph starting at line 364* The authors motivate the use of annealing as the schedules start at a distribution $\\pi_0$, which is easy to sample from. The reason for the easy sampling according to the authors is the strong-convexity of the negative log-density $-\\log\\pi_0(x) = \\eta(0)V(x) + \\lambda_0\\|x\\|^2/2$. The latter is true when $\\lambda_0$ is large enough.\n- *Continuation of the previous point. Line 831* The strong convexity constant $(\\lambda_0 - \\eta_0 \\beta)$ might be negative, unless $\\lambda_0$ is chosen to be large. \n- *Beginning of the proof of Theorem 1* $v_t$ is chosen to satisfy the Fokker-Planck equation on line 294. However, later on line 301 it is chosen to minimize the norm $\\|v_t\\|_{L_2(\\tilde{\\pi}_t)}$  using Lemma 2. This is possible if $v_t$ also generates $\\tilde{\\pi}_t$. Is it possible to find such $v_t$? See the relevant question.\n\n#### typos\n- *line 956:* cure -> curve", "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": "IBwtmvXv2q", "reviewer": "Reviewer_WbhJ", "summary": "The paper consider the problem of sampling from an unnormalized density that may be non-log-concave and multimodal using annealed MCMC.  The authors present a non-asymptotic analysis of Annealed Langevin Monte Carlo, bypassing the commonly assumed log-concavity constraint in literature. The quantitative bounds derived are widely applicable and either comparable to or better than previous analyses for isoperimetry-free sampling methods.", "questions": "Please see the weakness part.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides, as far as I know, the first thorough and non-asymptotic analysis of the annealed Langevin Monte Carlo algorithm.  The results obtained advance the understanding and analysis of annealed MCMC, potentially setting the stage for further research in this area. The intuition behind the algorithm and the proofs are well explained.", "weaknesses": "The discussion on the impact of the annealing schedule on the convergence rate is not sufficiently clear in the paper. How the choice of the annealing schedule influences the derived bounds? Specifically, in the example of mixture of Gaussians,  $\\lambda(\\theta) \\propto (1-\\theta)^\\gamma$ is used,   how varying $\\gamma$ affects the action $\\mathcal{A}$? whether there is an optimal value of $\\gamma$ that could minimize the convergence rate?", "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)