Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling

## Abstract

Abstract We address 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 O ~ ⁢ ( d ⁢ β 2 ⁢ 𝒜 2 ε 6 ) ~ 𝑂 𝑑 superscript 𝛽 2 superscript 𝒜 2 superscript 𝜀 6 \widetilde{O}\left(\frac{d\beta^{2}{\cal A}^{2}}{\varepsilon^{6}}\right) over~ start_ARG italic_O end_ARG ( divide start_ARG italic_d italic_β start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT caligraphic_A start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG start_ARG italic_ε start_POSTSUPERSCRIPT 6 end_POSTSUPERSCRIPT end_ARG ) for simple annealed Langevin Monte Carlo algorithm to achieve ε 2 superscript 𝜀 2 \varepsilon^{2} italic_ε start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT accuracy in Kullback-Leibler divergence to the target distribution π ∝ e − V proportional-to 𝜋 superscript e 𝑉 \pi\propto{\rm e}^{-V} italic_π ∝ roman_e start_POSTSUPERSCRIPT - italic_V end_POSTSUPERSCRIPT on ℝ d superscript ℝ 𝑑 \mathbb{R}^{d} blackboard_R start_POSTSUPERSCRIPT italic_d end_POSTSUPERSCRIPT with β 𝛽 \beta italic_β -smooth potential V 𝑉 V italic_V . Here, 𝒜 𝒜 {\cal A} caligraphic_A represents the action of a curve of probability measures interpolating the target distribution π 𝜋 \pi italic_π and a readily sampleable distribution.

## 1 Introduction

We study the task of efficient sampling from a probability distribution $\pi\propto{\rm e}^{-V}$ on $\mathbb{R}^{d}$. This fundamental problem is pivotal across various fields including computational statistics [liu2004monte, robert2004monte, brooks2011handbook, owen2013monte], Bayesian inference [gelman2013bayesian], statistical physics [newman1999monte, landau2021a], and finance [dagpunar2007simulation], and has been extensively studied in the literature [chewi2022log]. The most common approach to this problem is Markov Chain Monte Carlo (MCMC), among which Langevin Monte Carlo (LMC) [durmus2019analysis, vempala2019rapid, chewi2022analysis, mousavi-hosseini2023towards] is a particularly popular choice. LMC can be understood as a time-discretization of a diffusion process, known as Langevin diffusion (LD), whose stationary distribution is the target distribution $\pi$, and has been attractive partly due to its robust performance despite conceptual simplicity.

Although LMC and its variants converge rapidly when the target distribution $\pi$ is strongly log-concave or satisfies isoperimetric inequalities such as the log-Sobolev inequality (LSI) [durmus2019analysis, vempala2019rapid, chewi2022analysis], its effectiveness diminishes when dealing with target distributions that are not strongly log-concave or are multimodal, such as mixtures of Gaussians. In such scenarios, the sampler often becomes confined to a single mode, severely limiting its ability to explore the entire distribution effectively. This results in significant challenges in transitioning between modes, which can dramatically increase the mixing time, making it exponential in dimension $d$. 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.

To address the challenges posed by multimodality, techniques around the notion of annealing have been widely employed [gelfand1990sampling, neal2001annealed]. The general philosophy involves constructing a sequence of intermediate distributions $\pi_{0},\pi_{1},...,\pi_{M}$ that bridge the gap between an easily samplable distribution $\pi_{0}$ (e.g., Gaussian or Dirac-like), and the target distribution $\pi_{M}=\pi$. The process starts with sampling from $\pi_{0}$ and progressively samples from each subsequent distribution until $\pi_{M}$ is reached. When $\pi_{i}$ and $\pi_{i+1}$ are close enough, approximate samples from $\pi_{i}$ can serve as a warm start for sampling from $\pi_{i+1}$, thereby facilitating this transition. Employing LMC within this framework gives rise to what is known as the annealed LMC algorithm, which is the focus of our study. Despite its empirical success [song2019generative, song2020improved, zilberstein2022annealed, zilberstein2024solving], a thorough theoretical understanding of annealed LMC, particularly its non-asymptotic complexity bounds, remains elusive.

In this work, we take a first step toward providing a non-asymptotic analysis of annealed MCMC. By leveraging the Girsanov theorem to quantify the differences between the sampling dynamics and a reference process, we establish an upper bound of the error of annealed MCMC by the summation of two terms. One term is equal to the ratio of an action integral in the Wasserstein geometry induced by optimal transport and the duration of the process and diminishes when the annealing is sufficiently slow. Another term quantifies the discretization error in implementation. Our approach challenges the traditional point of view that annealed MCMC is a cascade of warm start. Analysis based on this viewpoint still requires log-concavity or isoperimetry.
Instead, our theoretical analysis of the annealed Langevin-based MCMC advances the field by eliminating the reliance on assumptions related to log-concavity or isoperimetry. Our strategy represents a paradigm shift in analyzing annealed MCMC. Even though a fully polynomial complexity bound has not been achieved yet. We hope our strategy can inspire future work towards this ambitious goal.

Our key technical contributions are summarized as follows.

- 1.
We discover a novel strategy to analyze the non-asymptotic complexity bound of annealed MCMC algorithms that can circumvent the need for log-concavity or isoperimetry.
- 2.
In Section 4, we investigate the annealed LD, which involves running LD with a dynamically changing target distribution and derive a surprising bound on the time required to simulate the SDE for achieving $\varepsilon^{2}$-accuracy in KL divergence.
- 3.
Building on the insights from the analysis of the continuous dynamic and accounting for discretization errors, we establish a non-asymptotic oracle complexity bound for annealed LMC in Section 5, which is applicable to a broad range of annealing schemes.

The quantitative results are summarized and compared to other sampling algorithms in Table 1. Notably, our approach operates under the least stringent assumptions and exhibits the most favorable $\varepsilon$-dependence among all isoperimetry-free sampling methods.

**Table 1: Comparison of oracle complexities in terms of $d$, $\varepsilon$, and LSI constant for sampling from $\pi\propto{\rm e}^{-V}$. The notation “${\rm poly(\cdot)}$” denotes a polynomial function of the indicated parameters.**
| Algorithm | Isoperimetric<br>Assumptions | Other<br>Assumptions | Criterion | Complexity |
| --- | --- | --- | --- | --- |
| LMC<br>[vempala2019rapid] | $C$-LSI | Potential smooth | $\varepsilon^{2}$, $\operatorname{KL}\left(\cdot\middle\|\pi\right)$ | $\widetilde{O}\left(C^{2}d\varepsilon^{-2}\right)$ |
| PS<br>[fan2023improved] | $C$-LSI | Potential smooth | $\varepsilon$, TV | $\widetilde{O}\left(Cd^{1/2}\log\varepsilon^{-1}\right)$ |
| STLMC<br>[ge2018simulated] | / | Translated mixture of<br>a well-conditioned<br>distribution | $\varepsilon$, TV | $O\left(\operatorname{poly}\left(d,\varepsilon^{-1}\right)\right)$ |
| RDMC<br>[huang2024reverse] | / | Potential smooth,<br>nearly convex at $\infty$ | $\varepsilon$, TV | $O\left(\operatorname{poly}\left(d\right){\rm e}^{\operatorname{poly}\left(<br>\varepsilon^{-1}\right)}\right)$ |
| ZOD-MC<br>[he2024zeroth] | / | Potential growing<br>at most quadratically | $\varepsilon$, TV+W2 | ${\rm e}^{\widetilde{O}\left(d\right)O\left(\log\varepsilon^{-1}\right)}$ |
| ALMC<br>(ours) | / | Potential smooth | $\varepsilon^{2}$, $\operatorname{KL}\left(\pi\middle\|\cdot\right)$ | $\widetilde{O}\left(d{\cal A}(d)^{2}\varepsilon^{-6}\right)$ |

Related works and comparison. We provide a brief overview of the literature, mainly focusing on the algorithms for non-log-concave sampling and their theoretical analysis.

- •
Samplers based on tempering. The fundamental concept of tempering involves sampling the system at various temperatures simultaneously: at higher temparatures, the distribution flattens, allowing particles to easily transition between modes, while at lower temperatures, particles can more effectively explore local structures. In simulated tempering [marinari1992simulated, woodard2009conditions], the system’s temperature is randomly switched, while in parallel tempering (also known as replica exchange) [swendsen1986replica, lee2023improved], the temperatures of two particles are swapped according to a specific rule. However, quantitative theoretical results for tempering are limited, and the existing results (e.g., [ge2018beyond, ge2018simulated, dong2022spectral]) apply primarily to certain special classes of non-log-concave distributions.
- •
Samplers based on general diffusions. Inspired by score-based diffusion models [ho2020denoising, song2021denoising, song2021scorebased], recent advances have introduced sampling methods that reverse the Ornstein-Uhlenbeck process, as detailed in [huang2024reverse, huang2024faster, he2024zeroth]. These samplers exhibit reduced sensitivity to isoperimetric conditions, but rely on estimating score functions (gradients of log-density) via importance sampling, which poses significant challenges in high-dimensional settings. Concurrently, studies such as [zhang2022path, vargas2023denoising, vargas2024transport, richter2024improved] have employed neural networks to approximate unknown drift terms, enabling an SDE to transport a 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 interpolation of probability distributions, thus simplifying sampling by obviating the need for intensive score estimation or neural network training.
- •
Non-asymptotic analysis for non-log-concave sampling. Drawing upon the stationary-point analysis in non-convex optimization, the seminal work [balasubramanian2022towards] characterizes the convergence of non-log-concave sampling via Fisher divergence. Subsequently, [cheng2023fast] 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 as total-variational distance or Wasserstein distances. In contrast, our study provides a convergence guarantee in terms of KL divergence, which implies convergence in total-variation distance and offers a stronger result.

Notations and definitions. For $a,b\in\mathbb{R}$, we define $\left[\!\left[a,b\right]\!\right]:=[a,b]\cap\mathbb{Z}$, $a\wedge b:=\min(a,b)$, and $a\vee b:=\max(a,b)$. For $a,b>0$, the notations $a\lesssim b$, $a=O(b)$, and $b=\Omega(a)$ indicate that $a\leq Cb$ for some universal constant $C>0$, and the notations $a\asymp b$ and $a=\Theta(b)$ stand for both $a=O(b)$ and $b=O(a)$. $\widetilde{O}\left(\cdot\right)$ hides logarithmic dependence in $O(\cdot)$. A function $U\in C^{2}(\mathbb{R}^{d})$ is $\alpha(>0)$-strongly-convex if $\nabla^{2}U\succeq\alpha I$, and is $\beta(>0)$-smooth if $-\beta I\preceq\nabla^{2}U\preceq\beta I$. The total-variation (TV) distance is defined as $\operatorname{TV}\left(\mu,\nu\right)=\sup_{A\subset\mathbb{R}^{d}}\left|\mu(A
)-\nu(A)\right|$, and the Kullback-Leibler (KL) divergence is defined as $\operatorname{KL}\left(\mu\middle\|\nu\right)=\operatorname{\mathbb{E}}_{\mu}
\left[\log\frac{{\rm d}\mu}{{\rm d}\nu}\right]$. $\left\|\cdot\right\|$ represents the $\ell^{2}$ norm on $\mathbb{R}^{d}$. For $f:\mathbb{R}^{d}\to\mathbb{R}^{d^{\prime}}$ and a probability measure $\mu$ on $\mathbb{R}^{d}$, $\left\|f\right\|_{L^{2}(\mu)}:=\left(\int\left\|f\right\|^{2}{\rm d}\mu\right)
^{1/2}$, and the second-order moment of $\mu$ is defined as $\operatorname{\mathbb{E}}_{\mu}\left[\left\|\cdot\right\|^{2}\right]$.

## 2 Preliminaries

### 2.1 Stochastic Differential Equations and Girsanov Theorem

A stochastic differential equation (SDE) $X=(X_{t})_{t\in[0,T]}$ is a stochastic process on $\Omega=C([0,T];\mathbb{R}^{d})$, the space of continuous functions from $[0,T]$ to $\mathbb{R}^{d}$. The dynamics of $X$ are typically represented by the equation ${\rm d}X_{t}=b(X_{t},t){\rm d}t+\sigma(X_{t},t){\rm d}B_{t}$, $t\in[0,T]$, where $(B_{t})_{t\in[0,T]}$ is a standard Brownian motion in $\mathbb{R}^{d}$. The path measure of $X$, denoted $\mathbb{P}^{X}$, characterizes the distribution of $X$ over $\Omega$ and is defined by $\mathbb{P}^{X}(A)=\operatorname{\mathbb{P}}\left(X\in A\right)$ for all measurable subset $A$ of $\Omega$. The following lemma, as a corollary of the Girsanov theorem [karatzas1991brownian, ustunel2013transformation, liptser2013statistics], provides a methodology for computing the KL divergence between two path measures and serves as a crucial technical tool in our proof.

###### Lemma 1 .

Assume we have the following two SDEs on $\Omega$:

$$ $\displaystyle{\rm d}X_{t}=a_{t}(X_{t}){\rm d}t+\sqrt{2}{\rm d}B_{t},~{}X_{0} \sim\mu;\qquad{\rm d}Y_{t}=b_{t}(Y_{t}){\rm d}t+\sqrt{2}{\rm d}B_{t},~{}Y_{0} \sim\nu.$ $$

Let $\mathbb{P}^{X}$ and $\mathbb{P}^{Y}$ denote the path measures of $X$ and $Y$, respectively. Then

$$ $\operatorname{KL}\left(\mathbb{P}^{X}\middle\|\mathbb{P}^{Y}\right)= \operatorname{KL}\left(\mu\middle\|\nu\right)+\frac{1}{4}\operatorname{\mathbb {E}}_{X\sim\mathbb{P}^{X}}\left[\int_{0}^{T}\left\|a_{t}(X_{t})-b_{t}(X_{t}) \right\|^{2}{\rm d}t\right].$ $$

###### Lemma 1 .

### 2.2 Langevin Diffusion and Langevin Monte Carlo

The Langevin diffusion (LD) with target distribution $\pi\propto{\rm e}^{-V}$ is the solution to the SDE

$$ ${\rm d}X_{t}=-\nabla V(X_{t}){\rm d}t+\sqrt{2}{\rm d}B_{t},~{}t\in[0,\infty);~ {}X_{0}\sim\mu_{0}.$ (1) $$

It is well-known that under mild conditions, $\pi$ is the unique stationary distribution this SDE, and when $\pi$ has good regularity properties, the marginal distribution of $X_{t}$ converges to $\pi$ as $t\to{+\infty}$, so we can sample from $\pi$ by simulating Equation 1 for a long time. However, in most of the cases, LD is intractable to simulate exactly, and the Euler-Maruyama discretization of Equation 1 leads to the Langevin Monte Carlo (LMC) algorithm. LMC with step size $h>0$ and target distribution $\pi\propto{\rm e}^{-V}$ is a Markov chain $\{X_{kh}\}_{k=0,1,...}$ constructed by iterating the following update rule:

$$ $X_{(k+1)h}=X_{kh}-h\nabla V(X_{kh})+\sqrt{2}(B_{(k+1)h}-B_{kh}),~{}k=0,1,...;~ {}X_{0}\sim\mu_{0},$ (2) $$

where $\{B_{(k+1)h}-B_{kh}\}_{k=0,1,...}\stackrel{{\scriptstyle{\rm i.i.d.}}}{{\sim}}
\operatorname{{\cal N}}\left(0,hI\right)$.

### 2.3 Wasserstein Distance and Curves of Probability Measures

We briefly introduce several fundamental concepts in optimal transport, and direct readers to authoritative textbooks [villani2008optimal, villani2021topics, ambrosio2008gradient, ambrosio2021lectures] for an in-depth exploration.

For two probability measures $\mu,\nu$ on $\mathbb{R}^{d}$ with finite second-order moments, the Wasserstein-2 (W2) distance between $\mu$ and $\nu$ is defined as

$$ $W_{2}(\mu,\nu)=\inf_{\gamma\in\Pi(\mu,\nu)}\left(\int\left\|x-y\right\|^{2} \gamma({\rm d}x,{\rm d}y)\right)^{\frac{1}{2}},$ $$

where $\Pi(\mu,\nu)$ is the set of all couplings of $(\mu,\nu)$, i.e., probability measure $\gamma$ on $\mathbb{R}^{d}\times\mathbb{R}^{d}$ with $\gamma(A\times\mathbb{R}^{d})=\mu(A)$ and $\gamma(\mathbb{R}^{d}\times A)=\nu(A)$, for all measurable set $A\subset\mathbb{R}^{d}$.

Given a vector field $v=(v_{t}:\mathbb{R}^{d}\to\mathbb{R}^{d})_{t\in[a,b]}$ and a curve of probability measures $\rho=(\rho_{t})_{t\in[a,b]}$ on $\mathbb{R}^{d}$ with finite second-order moments, we say that $v$ generates $\rho$ if the continuity equation $\partial_{t}\rho_{t}+\nabla\cdot(\rho_{t}v_{t})=0$, $t\in[a,b]$ holds. The metric derivative of $\rho$ at $t\in[a,b]$ is defined as

$$ $\left|\dot{\rho}\right|_{t}:=\lim_{\delta\to 0}\frac{W_{2}(\rho_{t+\delta}, \rho_{t})}{\left|\delta\right|},$ $$

which can be interpreted as the “speed” of this curve. If $\left|\dot{\rho}\right|_{t}$ exists and is finite for all $t\in[a,b]$, we say that $\rho$ is absolutely continuous (AC). The metric derivative and the continuity equation are closely related by the following important fact (see [ambrosio2008gradient, Theorem 8.3.1]):

###### Lemma 2 .

For an AC curve of probability measures $(\rho_{t})_{t\in[a,b]}$, any vector field $(v_{t})_{t\in[a,b]}$ that generates $(\rho_{t})_{t\in[a,b]}$ satisfies $\left|\dot{\rho}\right|_{t}\leq\left\|v_{t}\right\|_{L^{2}(\rho_{t})}$ for all $t\in[a,b]$. Moreover, the equality is reachable.

Finally, define the action of an AC curve of probability measures $(\rho_{t})_{t\in[a,b]}$ as ${\cal A}(\rho):=\int_{a}^{b}\left|\dot{\rho}\right|_{t}^{2}{\rm d}t$.

###### Lemma 2 .

### 2.4 Isoperimetric Inequalities

A probability measure $\pi$ on $\mathbb{R}^{d}$ satisfies a log-Sobolev inequality (LSI) with constant $C$, or $C$-LSI, if for all $f\in C^{1}(\mathbb{R}^{d})$ with $\operatorname{\mathbb{E}}_{\pi}\left[f^{2}\right]>0$,

$$ $\operatorname{\mathbb{E}}_{\pi}\left[f^{2}\log\frac{f^{2}}{\operatorname{ \mathbb{E}}_{\pi}\left[f^{2}\right]}\right]\leq 2C\operatorname{\mathbb{E}}_{ \pi}\left[\left\|\nabla f\right\|^{2}\right].$ $$

It is worth noting that $\alpha$-strongly-log-concave distributions satisfy $\frac{1}{\alpha}$-LSI (Bakry-Émery theorem, [bakry2014analysis]). When $\pi\propto{\rm e}^{-V}$ satisfies $C$-LSI and the potential $V$ is $\beta$-smooth, it is established in [vempala2019rapid] that the LD converges exponentially fast in KL divergence, while the LMC also converges exponentially with a bias that vanishes when the step size approaches 0 0.

## 3 Problem Setup

In this paper, we consider the following mild assumption on the target distribution $\pi\propto{\rm e}^{-V}$ on $\mathbb{R}^{d}$, which is widely used in the field of sampling (see, e.g., [durmus2019analysis, vempala2019rapid, balasubramanian2022towards, chewi2022analysis]):

###### Assumption 1 .

The potential $V$ is $\beta$-smooth, and there exists a global minimizer $x_{*}$ of $V$ such that $\left\|x_{*}\right\|\leq R$. Moreover, $\pi$ has finite second-order moment.

Recall that the rationale behind annealing involves a gradual transition from a distribution that is easy to sample from to the more complex target distribution, which is crucial to our algorithm. Throughout this paper, we define the following curve of probability measures on $\mathbb{R}^{d}$:

$$ $\pi_{\theta}\propto\exp\left(-\eta(\theta)V-\frac{\lambda(\theta)}{2}\left\| \cdot\right\|^{2}\right),~{}\theta\in[0,1].$ (3) $$

We use the term annealing schedule to refer to the functions $\eta(\cdot)$ and $\lambda(\cdot)$. They need to be differentiable and monotone, satisfying the boundary conditions $\eta_{0}=\eta(0)\nearrow\eta(1)=1$ and $\lambda_{0}=\lambda(0)\searrow\lambda(1)=0$. The values of $\eta_{0}\in[0,1]$ and $\lambda_{0}\in(1,{+\infty})$ will be determined later. This flexible interpolation scheme includes many general cases. For example, [brosse2018normalizing] and [ge2020estimating] used the schedule $\eta(\cdot)\equiv 1$, while [neal2001annealed] used the schedule $\lambda(\theta)=c(1-\eta(\theta))$. The key motivation for this interpolation is that when $\theta=0$, the quadratic term predominates, making the potential of $\pi_{0}$ strongly-convex with a moderate condition number, thus $\pi_{0}$ is easy to sample from; on the other hand, when $\theta=1$, $\pi_{1}$ is just the target distribution $\pi$. As $\theta$ gradually increases from 0 0 to $1$, the readily sampleable distribution $\pi_{0}$ slowly transform into the target distribution $\pi_{1}$.

In Lemma 5, we prove that $\pi_{\theta}$ also has finite second-order moment, so the W2 distance between $\pi_{\theta}$’s makes sense. We further make a mild assumption on the absolute continuity of the curve:

###### Assumption 2 .

The curve $(\pi_{\theta})_{\theta\in[0,1]}$ is AC with finite action ${\cal A}_{\eta,\lambda}(\pi):=\int_{0}^{1}\left|\dot{\pi}\right|_{\theta}^{2}{
\rm d}\theta$.

To facilitate easy sampling from $\pi_{0}$, we consider two choices of the parameters $\eta_{0}$ and $\lambda_{0}$, which have the following complexity guarantees.

###### Lemma 3 .

When $\eta_{0}=0$, $\pi_{0}=\operatorname{{\cal N}}\left(0,\frac{1}{\lambda_{0}}I\right)$ can be sampled directly; when $\eta_{0}\in(0,1]$, we choose $\lambda_{0}=\eta_{0}d\beta$, so that under Assumption 1, it takes $O\left(1\vee\log\frac{\eta_{0}\beta R^{2}}{d^{2}}\right)=\widetilde{O}\left(1\right)$ queries to the oracle of $V$ and $\nabla V$ in expectation to precisely sample from $\pi_{0}$ via rejection sampling.

See Appendix A for the rejection sampling algorithm as well as the full proof of this lemma. The parameter $R$ reflects 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 $\widetilde{O}\left(1\right)$ complexity is negligible compared to the overall complexity of sampling. In particular, when the exact location of a global minimizer of $V$ is known, we can adjust the potential $V$ so that 0 0 becomes a global minimizer, thereby reducing the complexity to $O(1)$.

Equipped with this foundational setup, we now proceed to introduce the annealed LD and annealed LMC algorithms.

###### Assumption 1 .

###### Assumption 2 .

###### Lemma 3 .

## 4 Analysis of Annealed Langevin Diffusion

To elucidate the concept of annealing more clearly, we first consider the annealed Langevin diffusion (ALD) algorithm, which samples from the $\pi\propto{\rm e}^{-V}$ by running LD with a dynamically changing target distribution. For the purpose of this discussion, let us assume that we can exactly simulate *any* SDE with known drift and diffusion terms.

Fix an annealing schedule $\eta(\cdot),\lambda(\cdot)$ and choose a sufficiently long time $T$. We define a reparametrized curve of probability measures $\left(\widetilde{\pi}_{t}:=\pi_{t/T}\right)_{t\in[0,T]}$. Starting with an initial sample $X_{0}\sim\pi_{0}=\widetilde{\pi}_{0}$, we run the SDE

$$ ${\rm d}X_{t}=\nabla\log\widetilde{\pi}_{t}(X_{t}){\rm d}t+\sqrt{2}{\rm d}B_{t} ,~{}t\in[0,T],$ (4) $$

and ultimately output $X_{T}\sim\nu^{\rm ALD}$ as an approximate sample from the target distribution $\pi$. Intuitively, when $\widetilde{\pi}_{t}$ is changing slowly, the distribution of $X_{t}$ should closely resemble $\widetilde{\pi}_{t}$, leading to an output distribution $\nu^{\rm ALD}$ that approximates the target distribution. This turns out to be true, as is confirmed by the following theorem, which provides a convergence guarantee for the ALD process.

###### Theorem 1 .

When choosing $T=\frac{{\cal A}_{\eta,\lambda}(\pi)}{4\varepsilon^{2}}$, it follows that $\operatorname{KL}\left(\pi\middle\|\nu^{\rm ALD}\right)\leq\varepsilon^{2}$.

###### Proof.

Let $\mathbb{Q}$ be the path measure of ALD (Equation 4) initialized at $X_{0}\sim\widetilde{\pi}_{0}$, and define $\mathbb{P}$ as the path measure corresponding to the following reference SDE:

$$ ${\rm d}X_{t}=(\nabla\log\widetilde{\pi}_{t}+v_{t})(X_{t}){\rm d}t+\sqrt{2}{\rm d }B_{t},~{}X_{0}\sim\widetilde{\pi}_{0},~{}t\in[0,T].$ (5) $$

The vector field $v=(v_{t})_{t\in[0,T]}$ is designed such that $X_{t}\sim\widetilde{\pi}_{t}$ for all $t\in[0,T]$. According to the Fokker-Planck equation, $v$ must satisfy the PDE

$$ $\partial_{t}\widetilde{\pi}_{t}=-\nabla\cdot(\widetilde{\pi}_{t}\left(\nabla \log\widetilde{\pi}_{t}+v_{t}\right))+\Delta\widetilde{\pi}_{t}=-\nabla\cdot( \widetilde{\pi}_{t}v_{t}),~{}t\in[0,T],$ $$

which means that $v$ generates $\left(\widetilde{\pi}_{t}:=\pi_{t/T}\right)_{t\in[0,T]}$. We can compute $\operatorname{KL}\left(\mathbb{P}\middle\|\mathbb{Q}\right)$ using Lemma 1:

$$ $\operatorname{KL}\left(\mathbb{P}\middle\|\mathbb{Q}\right)=\frac{1}{4} \operatorname{\mathbb{E}}_{\mathbb{P}}\left[\int_{0}^{T}\left\|v_{t}(X_{t}) \right\|^{2}{\rm d}t\right]=\frac{1}{4}\int_{0}^{T}\left\|v_{t}\right\|_{L^{2} (\widetilde{\pi}_{t})}^{2}{\rm d}t.$ $$

Leveraging Lemma 2, among all vector fields $v$ that generate $\left(\widetilde{\pi}_{t}:=\pi_{t/T}\right)_{t\in[0,T]}$, we can choose the one that minimizes $\left\|v_{t}\right\|_{L^{2}(\widetilde{\pi}_{t})}$, thereby making $\left\|v_{t}\right\|_{L^{2}(\widetilde{\pi}_{t})}=\left|\dot{\widetilde{\pi}}
\right|_{t}$, the metric derivative. With the reparameterization $\widetilde{\pi}_{t}=\pi_{t/T}$, we have the following relation by chain rule:

$$ $\left|\dot{\widetilde{\pi}}\right|_{t}=\lim_{\delta\to 0}\frac{W_{2}( \widetilde{\pi}_{t+\delta},\widetilde{\pi}_{t})}{\left|\delta\right|}=\lim_{ \delta\to 0}\frac{W_{2}(\pi_{(t+\delta)/T},\pi_{t/T})}{T\left|\delta/T\right|} =\frac{1}{T}\left|\dot{\pi}\right|_{t/T}.$ $$

Employing the change-of-variable formula leads to

$$ $\operatorname{KL}\left(\mathbb{P}\middle\|\mathbb{Q}\right)=\frac{1}{4}\int_{0 }^{T}\left|\dot{\widetilde{\pi}}\right|_{t}^{2}{\rm d}t=\frac{1}{4T}\int_{0}^{ 1}\left|\dot{\pi}\right|_{\theta}^{2}{\rm d}\theta=\frac{{\cal A}_{\eta, \lambda}(\pi)}{4T}.$ $$

Finally, using the data-processing inequality ([chewi2022log, Theorem 1.5.3]), with $T=\frac{{\cal A}_{\eta,\lambda}(\pi)}{4\varepsilon^{2}}$,

$$ $\operatorname{KL}\left(\pi\middle\|\nu^{\rm ALD}\right)=\operatorname{KL}\left (\mathbb{P}_{T}\middle\|\mathbb{Q}_{T}\right)\leq\operatorname{KL}\left( \mathbb{P}\middle\|\mathbb{Q}\right)=\varepsilon^{2},$ $$

where $\mathbb{P}_{T}$ and $\mathbb{Q}_{T}$ stand for the marginal distributions of $\mathbb{P}$ and $\mathbb{Q}$ at time $T$, respectively.
∎

Although we adopt a specific parametrization of the interpolating distribution (Equation 3), which is widely used in practice, the results in Theorem 1 are applicable to any curve of probability measures $(\pi_{\theta})_{\theta\in[0,1]}$ that bridge $\pi_{0}$ and $\pi_{1}=\pi$. This applicability extends as long as the closed forms of the drift and diffusion terms in the SDE, which precisely follow the path $(\pi_{\theta})_{\theta\in[0,1]}$, are known.

Let us delve deeper into the mechanics of the ALD. Although at time $t$ the SDE (Equation 4) targets the distribution $\widetilde{\pi}_{t}$, the distribution of $X_{t}$ does not precisely match $\widetilde{\pi}_{t}$. Nevertheless, by choosing a sufficiently long time $T$, we actually move on the curve $(\pi_{\theta})_{\theta\in[0,1]}$ sufficiently slowly, thus minimizing the discrepancy between the path measure of $(X_{t})_{t\in[0,T]}$ and the reference curve $(\widetilde{\pi}_{t})_{t\in[0,T]}$. By applying data-processing inequality, we can upper bound the error between the marginal distributions at time $T$ by the joint distributions of the two paths. In essence, *moving more slowly, sampling more precisely*.

Our analysis predominantly 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 [dalalyan2012sparse] (see also [chewi2022log, Section 4.4]) and [chen2023sampling], and stands in contrast to the traditional isoperimetry-based analyses of LD (e.g., [vempala2019rapid, chewi2022analysis, balasubramanian2022towards]), which emphasize the decay of the KL divergence from the distribution of $X_{t}$ to the target distribution and require LSI to bound the time derivative of this quantity. Notably, the total time $T$ needed to run the SDE depends solely on the action of the curve $(\pi_{\theta})_{\theta\in[0,1]}$, obviating the need for assumptions related to log-concavity or isoperimetry.

We also remark that the ALD plays a significant role in another important subject known as non-equilibrium stochastic thermodynamics [seifert2012stochastic]. Recently, a refinement of the fluctuation theorem was discovered in [chen2020stochastic, fu2021maximal], stating that the irreversible entropy production in a stochastic thermodynamic system is equal to the ratio of a similar action integral as in Theorem 1 and the duration of the process $T$, resembling Theorem 1.

###### Theorem 1 .

###### Proof.

## 5 Analysis of Annealed Langevin Monte Carlo

It is crucial to recognize that the ALD (Equation 4) cannot be precisely simulated in practice. Transitioning from LD to LMC introduces additional errors due to discretization. This section will present a detailed convergence analysis for the annealed Langevin Monte Carlo (ALMC) algorithm, which is implementable in practical scenarios.

A straightforward yet non-optimal method to discretize Equation 4 involves employing the Euler-Maruyama scheme, i.e.,

$$ $X_{t+\Delta t}\approx X_{t}+\nabla\log\widetilde{\pi}_{t}(X_{t})\Delta t+\sqrt {2}(B_{t+\Delta t}-B_{t}),~{}0\leq t<t+\Delta t\leq T.$ $$

However, considering that $\nabla\log\widetilde{\pi}_{t}(x)=-\eta\left(\frac{t}{T}\right)\nabla V(x)-
\lambda\left(\frac{t}{T}\right)x$, the integral of the linear term can be computed in closed form, so we can use the exponential-integrator scheme [zhang2023fast, zhang2023gddim] to further reduce the discretization error.

Given the total time $T$, we define a sequence of points $0=\theta_{0}<\theta_{1}<...<\theta_{M}=1$, and set $T_{\ell}=T\theta_{\ell}$, $h_{\ell}=T(\theta_{\ell}-\theta_{\ell-1})$. The exponential-integrator scheme is then expressed as

$$ ${\rm d}X_{t}=\left(-\eta\left(\frac{t}{T}\right)\nabla V(X_{t_{-}})-\lambda \left(\frac{t}{T}\right)X_{t}\right){\rm d}t+\sqrt{2}{\rm d}B_{t},~{}t\in[0,T] ,~{}X_{0}\sim\pi_{0},$ (6) $$

where $t_{-}:=T_{\ell-1}$ when $t\in[T_{\ell-1},T_{\ell})$, $\ell\in\left[\!\left[1,M\right]\!\right]$. The explicit update rule is detailed in Algorithm 1, with $x_{\ell}$ denoting $X_{T_{\ell}}$, and the derivation of Equation 7 is presented in Section B.1. Notably, replacing $\nabla V(X_{t_{-}})$ with $\nabla V(X_{t})$ recovers the ALD (Equation 4), and setting $\eta\equiv 1$ and $\lambda\equiv 0$ reduces to the classical LMC iterations.

Figure: Algorithm 1 Annealed LMC Algorithm

We illustrate the ALMC algorithm in Figure 1. The underlying intuition behind this algorithm is that by setting a sufficiently long total time $T$, the trajectory of the continuous dynamic (i.e., annealed LD) approaches the reference trajectory closely, as established in Theorem 1. Additionally, by adopting sufficiently small step sizes $h_{1},...,h_{M}$, the discretization error can be substantially reduced. Unlike traditional annealed LMC methods, which require multiple LMC update steps for each intermediate distribution $\pi_{1},...,\pi_{M}$, our approach views the annealed LMC as a discretization of a continuous-time process. Consequently, it is adequate to perform *a single step* of LMC towards each intermediate distribution $\widetilde{\pi}_{T_{1}},...,\widetilde{\pi}_{T_{M}}$, provided that $T$ is sufficiently large and the step sizes are appropriately small.

Figure: Figure 1: Illustration of the ALMC algorithm. The $\ell$-th green arrow, proceeding from left to right, represents one step of LMC towards $\widetilde{\pi}_{T_{\ell}}$ with step size $h_{\ell}$, while each red arrow corresponds to the application of the same transition kernel, initialized at $\widetilde{\pi}_{T_{\ell-1}}$ on the reference trajectory $\mathbb{P}$, which is depicted in purple. To evaluate $\operatorname{KL}\left(\mathbb{P}\middle\|\mathbb{Q}\right)$, 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”).

The subsequent theorem provides a convergence guarantee for the annealed LMC algorithm, with the complete proof detailed in Section B.2.

###### Theorem 2 .

Under Assumptions 1 and 2, Algorithm 1 can generate a distribution $\nu^{\rm ALMC}$ satisfying $\operatorname{KL}\left(\pi\middle\|\nu^{\rm ALMC}\right)\leq\varepsilon^{2}$ within

$$ $\widetilde{O}\left(\frac{d\beta^{2}{\cal A}_{\eta,\lambda}(\pi)^{2}}{ \varepsilon^{6}}\right)$ $$

calls to the oracle of $V$ and $\nabla V$ in expectation.

###### Sketch of Proof.

Let $\mathbb{Q}$ be the path measure of ALMC (Equation 4), whose marginal distribution at time $T$ is the output distribution $\nu^{\rm ALMC}$. Again, let $\mathbb{P}$ denote the reference path measure of Equation 5 used in the proof of Theorem 1, in which the same vector field $(v_{t})_{t\in[0,T]}$ ensures that $X_{t}\sim\widetilde{\pi}_{t}$ under $\mathbb{P}$ for all $t\in[0,T]$.

Applying Girsanov theorem (Lemma 1) and carefully dealing with the discretization error, we can upper bound $\operatorname{KL}\left(\mathbb{P}\middle\|\mathbb{Q}\right)$ by

$$ $\operatorname{KL}\left(\mathbb{P}\middle\|\mathbb{Q}\right)\lesssim\sum_{\ell= 1}^{M}\left(\frac{1+\eta(\theta_{\ell})^{2}\beta^{2}h_{\ell}^{2}}{T}\int_{ \theta_{\ell-1}}^{\theta_{\ell}}\left|\dot{\pi}\right|^{2}_{\theta}{\rm d} \theta+\eta(\theta_{\ell})^{2}\beta^{2}dh_{\ell}^{2}\left(1+h_{\ell}\left( \beta\eta(\theta_{\ell})+\lambda(\theta_{\ell-1})\right)\right)\right).$ $$

The first summation is governed by the total time $T$, which pertains to the convergence of the continuous dynamic (i.e., ALD). Setting $T\asymp\frac{{\cal A}_{\eta,\lambda}(\pi)}{\varepsilon^{2}}$ ensures that the first summation remains $O(\varepsilon^{2})$, provided that the step size $h_{\ell}$ is sufficiently small. The second summation addresses the discretization error, and it suffices to determine the appropriate value of $\theta_{\ell}$ to minimize $M$, the total number of calls to the oracle of $\nabla V$ for discretizing the SDE. Combining $M$ with the complexity of sampling from $\pi_{0}$ 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 $\eta(\cdot)$ and $\lambda(\cdot)$ influence the complexity exclusively through the action ${\cal A}_{\eta,\lambda}(\pi)$. Identifying the optimal annealing schedule to minimize this action remains a significant challenge, and we propose this as an area for future research.

We also note that our Assumption 1 encompasses strongly-log-concave target distributions. For sampling from these well-conditioned distributions via LMC, the complexity required to achieve $\varepsilon$- in TV distance scales as $\widetilde{O}\left(\varepsilon^{-2}\right)$ [chewi2022log]. However, using Pinsker inequality ${\rm KL}\geq 2{\rm TV}^{2}$, our complexity to meet the same error criterion is $O\left(\varepsilon^{-6}\right)$, indicating a significantly higher computational demand. Refining the parameter dependence in our algorithm to reduce this complexity remains a key area for future work.

Finally, we present a conjecture concerning the action ${\cal A}_{\eta,\lambda}(\pi)$, leaving its proof or disproof as an open question for future research. Following this conjecture, we demonstrate its applicability to a specific class of non-log-concave distributions in the subsequent example, with the detailed proof provided in Appendix C.

###### Conjecture 1 .

Under Assumption 1, the action ${\cal A}_{\eta,\lambda}(\pi)$ is bounded above by a polynomial function of the problem parameters, including $d$, $\beta$, $R$, $\operatorname{\mathbb{E}}_{\pi}\left[\left\|\cdot\right\|^{2}\right]$ $\eta_{0}$, $\lambda_{0}$, etc.

###### Example 1 .

Consider a mixture of Gaussian distributions in $\mathbb{R}^{d}$ defined by $\pi=\sum_{i=1}^{N}p_{i}\operatorname{{\cal N}}\left(y_{i},\beta^{-1}I\right)$, where the weights $p_{i}>0$, $\sum_{i=1}^{N}p_{i}=1$, and $\left\|y_{i}\right\|=r$ for all $i\in\left[\!\left[1,N\right]\!\right]$. Consequently, the potential $V=-\log\pi$ is $B$-smooth, where $B=\beta(4r^{2}\beta+1)$. With an annealing schedule defined by $\eta(\cdot)\equiv 1$ and $\lambda(\theta)=dB(1-\theta)^{\gamma}$ for some $1\leq\gamma=O(1)$, it follows that ${\cal A}_{\eta,\lambda}(\pi)=O\left(d(r^{2}\beta+1)\left(r^{2}+\frac{d}{\beta}
\right)\right)$.

To demonstrate the superiority of our theoretical results, let us consider a simplified scenario where $N=2$, $y_{1}=-y_{2}$, and $r^{2}\gg\frac{1}{\beta}$. We derive from Example 1 and Pinsker inequality that the total complexity required to obtain a sample that is $\varepsilon$-accurate in TV is $\widetilde{O}\left(d^{3}\beta^{2}r^{4}(r^{4}\beta^{2}\vee d^{2})\varepsilon^{-
6}\right)$. In contrast, studies such as [schlichting2019poincare, chen2021dimensionfree, dong2022spectral] indicate that the LSI constant of $\pi$ is $\Omega\left({\rm e}^{\Theta(\beta r^{2})}\right)$, so existing bounds in Table 1 suggest that LMC, to achieve the same accuracy, can only provide an exponential complexity guarantee of $\widetilde{O}\left({\rm e}^{\Theta(\beta r^{2})}d\varepsilon^{-2}\right)$.

###### Theorem 2 .

###### Sketch of Proof.

###### Conjecture 1 .

###### Example 1 .

## 6 Conclusions and Future Work

In this paper, we have explored the complexity of annealed LMC for sampling from a non-log-concave probability measure without relying on log-concavity or isoperimetry. Central to our analysis are the Girsanov theorem and optimal transport techniques, thus circumventing the need for isoperimetric inequalities. While our proof primarily focuses on the annealing scheme as described in Equation 3, there is potential for adaptation to more general interpolations. Further exploration of these applications will be a focus of our future research. Technically, our proof methodology could be expanded to include a broader range of target distributions beyond those with smooth potentials, such as those with Hölder-continuous gradients [chatterji2020langevin, erdogdu2021on, liang2022a, nguyen2023unadjusted, fan2023nestrov, fan2023improved], or even heavy-tailed target distributions [mousavi-hosseini2023towards, ye2024an]. Furthermore, eliminating the necessity of assuming global minimizers of the potential function would enhance the practical utility of our algorithm. Theoretically, proving Conjecture 1 or obtaining a polynomial bound of ${\cal A}_{\eta,\lambda}(\pi)$ under less restrictive conditions would further validate that our complexity bounds are genuinely polynomial. Finally, while this work emphasizes the upper bounds for non-log-concave sampling, an intriguing future avenue would be to verify the tightness of these bounds and explore potential lower bounds for this problem [chewi2022the, chewi2023query, chewi2023fisher].

## Appendix A Proof of Lemma 3

Our proof is inspired by [liang2023a].

We only consider the nontrivial case $\eta_{0}\in(0,1]$. The potential of $\pi_{0}$ is $V_{0}:=\eta_{0}V+\frac{\lambda_{0}}{2}\left\|\cdot\right\|^{2}$, which is $(\lambda_{0}-\eta_{0}\beta)$-strongly-convex and $(\lambda_{0}+\eta_{0}\beta)$-smooth. Note that for any fixed point $x^{\prime}\in\mathbb{R}^{d}$,

$$ $\pi_{0}(x)\propto\exp\left(-V_{0}(x)\right)\leq\exp\left(-V_{0}(x^{\prime})- \left\langle\nabla V_{0}(x^{\prime}),x-x^{\prime}\right\rangle-\frac{\lambda_{ 0}-\eta_{0}\beta}{2}\left\|x-x^{\prime}\right\|^{2}\right).$ $$

The right-hand side is the unnormalized density of $\pi_{0}^{\prime}:=\operatorname{{\cal N}}\left(x^{\prime}-\frac{\nabla V_{0}(x
^{\prime})}{\lambda_{0}-\eta_{0}\beta},\frac{1}{\lambda_{0}-\eta_{0}\beta}I\right)$. The rejection sampling algorithm is as follows: sample $X\sim\pi_{0}^{\prime}$, and accept $X$ as a sample from $\pi_{0}$ with probability

$$ $\exp\left(-V_{0}(X)+V_{0}(x^{\prime})+\left\langle\nabla V_{0}(x^{\prime}),X-x ^{\prime}\right\rangle+\frac{\lambda_{0}-\eta_{0}\beta}{2}\left\|X-x^{\prime} \right\|^{2}\right)\in(0,1].$ $$

By [chewi2022log, Theorem 7.1.1], the number of queries to the oracle of $V$ until acceptance follows a geometric distribution with mean

$$ $\displaystyle\frac{\int\exp\left(-V_{0}(x^{\prime})-\left\langle\nabla V_{0}(x ^{\prime}),x-x^{\prime}\right\rangle-\frac{\lambda_{0}-\eta_{0}\beta}{2}\left \|x-x^{\prime}\right\|^{2}\right){\rm d}x}{\int\exp\left(-V_{0}(x)\right){\rm d }x}$ $\displaystyle\leq\frac{\int\exp\left(-V_{0}(x^{\prime})-\left\langle\nabla V_{ 0}(x^{\prime}),x-x^{\prime}\right\rangle-\frac{\lambda_{0}-\eta_{0}\beta}{2} \left\|x-x^{\prime}\right\|^{2}\right){\rm d}x}{\int\exp\left(-V_{0}(x^{\prime })-\left\langle\nabla V_{0}(x^{\prime}),x-x^{\prime}\right\rangle-\frac{ \lambda_{0}+\eta_{0}\beta}{2}\left\|x-x^{\prime}\right\|^{2}\right){\rm d}x}$ $\displaystyle=\frac{\int\exp\left(-\left\langle\nabla V_{0}(x^{\prime}),x \right\rangle-\frac{\lambda_{0}-\eta_{0}\beta}{2}\left\|x\right\|^{2}\right){ \rm d}x}{\int\exp\left(-\left\langle\nabla V_{0}(x^{\prime}),x\right\rangle- \frac{\lambda_{0}+\eta_{0}\beta}{2}\left\|x\right\|^{2}\right){\rm d}x}$ $\displaystyle=\frac{\int\exp\left(-\frac{\lambda_{0}-\eta_{0}\beta}{2}\left\|x +\frac{\nabla V_{0}(x^{\prime})}{\lambda_{0}-\eta_{0}\beta}\right\|^{2}+\frac{ \left\|\nabla V_{0}(x^{\prime})\right\|^{2}}{2(\lambda_{0}-\eta_{0}\beta)} \right){\rm d}x}{\int\exp\left(-\frac{\lambda_{0}+\eta_{0}\beta}{2}\left\|x+ \frac{\nabla V_{0}(x^{\prime})}{\lambda_{0}+\eta_{0}\beta}\right\|^{2}+\frac{ \left\|\nabla V_{0}(x^{\prime})\right\|^{2}}{2(\lambda_{0}+\eta_{0}\beta)} \right){\rm d}x}$ $\displaystyle=\left(\frac{\lambda_{0}+\eta_{0}\beta}{\lambda_{0}-\eta_{0}\beta }\right)^{\frac{d}{2}}\exp\left(\frac{\eta_{0}\beta}{\lambda_{0}^{2}-\eta_{0}^ {2}\beta^{2}}\left\|\nabla V_{0}(x^{\prime})\right\|^{2}\right)$ $\displaystyle\leq\exp\left(\frac{\eta_{0}\beta d}{\lambda_{0}-\eta_{0}\beta} \right)\exp\left(\frac{\eta_{0}\beta}{\lambda_{0}^{2}-\eta_{0}^{2}\beta^{2}} \left\|\nabla V_{0}(x^{\prime})\right\|^{2}\right)$ $$

We choose $\lambda_{0}=\eta_{0}\beta d$ such that $\exp\left(\frac{\eta_{0}\beta d}{\lambda_{0}-\eta_{0}\beta}\right)\lesssim 1$. With this $\lambda_{0}$, $\exp\left(\frac{\eta_{0}\beta}{\lambda_{0}^{2}-\eta_{0}^{2}\beta^{2}}\left\|
\nabla V_{0}(x^{\prime})\right\|^{2}\right)$ is also $O(1)$ as long as $\left\|\nabla V_{0}(x^{\prime})\right\|^{2}\lesssim\eta_{0}\beta d^{2}$.

Let $x^{\prime\prime}$ be the global minimizer of the strongly convex potential function $V_{0}$, which satisfies

$$ $0=\nabla V_{0}(x^{\prime\prime})=\eta_{0}\nabla V(x^{\prime\prime})+\lambda_{0 }x^{\prime\prime}=\eta_{0}\nabla V(x^{\prime\prime})+\eta_{0}\beta dx^{\prime \prime}.$ $$

Given the smoothness of $V_{0}$,

$$ $\left\|\nabla V_{0}(x^{\prime})\right\|^{2}=\left\|\nabla V_{0}(x^{\prime})- \nabla V_{0}(x^{\prime\prime})\right\|^{2}\leq(\eta_{0}\beta d+\eta_{0}\beta)^ {2}\left\|x^{\prime}-x^{\prime\prime}\right\|^{2}.$ $$

Therefore, to guarantee $\left\|\nabla V_{0}(x^{\prime})\right\|^{2}\lesssim\eta_{0}\beta d^{2}$, it suffices to find an $x^{\prime}$ such that $\left\|x^{\prime}-x^{\prime\prime}\right\|\lesssim\frac{1}{\sqrt{\eta_{0}\beta}}$.

We first derive an upper bound of $\left\|x^{\prime\prime}\right\|$ under Assumption 1. Since $x_{*}$ is a global minimizer of $V$,

$$ $\displaystyle\beta d\left\|x^{\prime\prime}\right\|$ $\displaystyle=\left\|\nabla V(x^{\prime\prime})\right\|=\left\|\nabla V(x^{ \prime\prime})-\nabla V(x_{*})\right\|$ $\displaystyle\leq\beta\left\|x^{\prime\prime}-x_{*}\right\|\leq\beta(\left\|x^ {\prime\prime}\right\|+R),$ $\displaystyle\implies\left\|x^{\prime\prime}\right\|$ $\displaystyle\leq\frac{R}{d-1}\lesssim\frac{R}{d}.$ $$

When $R=0$, i.e., 0 0 is a known global minimizer of both $V$ and $V_{0}$, we can directly set $x^{\prime}=0$; otherwise, we need to run optimization algorithms to find such an $x^{\prime}$. According to standard results in convex optimization (see, e.g., [garrigos2023handbook, Theorem 3.6]), running gradient descent on function $V_{0}$ with step size $\frac{1}{\lambda_{0}+\eta_{0}\beta}$ yields the following convergence rate: starting from $x_{0}=0$, the $t$-th iterate $x_{t}$ satisfies

$$ $\left\|x_{t}-x^{\prime\prime}\right\|^{2}\leq\left(1-\frac{\lambda_{0}-\eta_{0 }\beta}{\lambda_{0}+\eta_{0}\beta}\right)^{t}\left\|0-x^{\prime\prime}\right\| ^{2}\lesssim\left(\frac{2}{d}\right)^{t}\frac{R^{2}}{d^{2}}\leq\frac{R^{2}}{{ \rm e}^{t}d^{2}},$ $$

where the last inequality holds when $d\geq 6$. Thus, $\log\frac{\eta_{0}\beta R^{2}}{d^{2}}+O(1)$ iterations are sufficient to find a desired $x^{\prime}$. We summarize the rejection sampling algorithm in Algorithm 2. In conclusion, precisely sampling from $\pi_{0}$ requires

$$ $O\left(1\vee\log\frac{\eta_{0}\beta R^{2}}{d^{2}}\right)=\widetilde{O}\left(1\right)$ $$

calls to the oracle of $V$ and $\nabla V$ in expectation.

Figure: Algorithm 2 Rejection Sampling for $\pi_{0}$.

∎

## Appendix B Proofs for Annealed LMC

### B.1 Proof of Equation 7

Define $\varLambda(t):=\int_{0}^{t}\lambda\left(\frac{\tau}{T}\right){\rm d}\tau$, whose derivative is $\varLambda^{\prime}(t)=\lambda\left(\frac{t}{T}\right)$. By Itô’s formula, we have

$$ ${\rm d}\left({\rm e}^{\varLambda(t)}X_{t}\right)={\rm e}^{\varLambda(t)}\left( \lambda\left(\frac{t}{T}\right)X_{t}{\rm d}t+{\rm d}X_{t}\right)={\rm e}^{ \varLambda(t)}\left(-\eta\left(\frac{t}{T}\right)\nabla V(X_{t_{-}}){\rm d}t+ \sqrt{2}{\rm d}B_{t}\right).$ $$

Integrating over $t\in[T_{\ell-1},T_{\ell})$ (note that in this case $t_{-}=T_{\ell-1}$), we obtain

$$ $\displaystyle{\rm e}^{\varLambda(T_{\ell})}X_{T_{\ell}}-{\rm e}^{\varLambda(T_ {\ell-1})}X_{T_{\ell-1}}$ $\displaystyle=-\left(\int_{T_{\ell-1}}^{T_{\ell}}\eta\left(\frac{t}{T}\right){ \rm e}^{\varLambda(t)}{\rm d}t\right)\nabla V(X_{T_{\ell-1}})+\sqrt{2}\int_{T_ {\ell-1}}^{T_{\ell}}{\rm e}^{\varLambda(t)}{\rm d}B_{t},$ $$

i.e.,

$$ $\displaystyle X_{T_{\ell}}$ $\displaystyle={\rm e}^{-(\varLambda(T_{\ell})-\varLambda(T_{\ell-1}))}X_{T_{ \ell-1}}-\left(\int_{T_{\ell-1}}^{T_{\ell}}\eta\left(\frac{t}{T}\right){\rm e} ^{-(\varLambda(T_{\ell})-\varLambda(t))}{\rm d}t\right)\nabla V(X_{T_{\ell-1}})$ $\displaystyle+\sqrt{2}\int_{T_{\ell-1}}^{T_{\ell}}{\rm e}^{-(\varLambda(T_{ \ell})-\varLambda(t))}{\rm d}B_{t}.$ $$

Since

$$ $\varLambda(T_{\ell})-\varLambda(t)=\int_{t}^{T_{\ell}}\lambda\left(\frac{\tau} {T}\right){\rm d}\tau=T\int_{t/T}^{T_{\ell}/T}\lambda(u){\rm d}u,$ $$

by defining $\Lambda_{0}(\theta^{\prime},\theta)=\exp\left(-T\int_{\theta}^{\theta^{\prime}
}\lambda(u){\rm d}u\right)$, we have ${\rm e}^{-(\varLambda(T_{\ell})-\varLambda(T_{\ell-1}))}=\Lambda_{0}(\theta_{
\ell},\theta_{\ell-1})$. Similarly, we can show that

$$ $\int_{T_{\ell-1}}^{T_{\ell}}\eta\left(\frac{t}{T}\right){\rm e}^{-(\varLambda( T_{\ell})-\varLambda(t))}{\rm d}t=\int_{T_{\ell-1}}^{T_{\ell}}\eta\left(\frac{ t}{T}\right)\Lambda_{0}\left(\frac{T_{\ell}}{T},\frac{t}{T}\right){\rm d}t=T \int_{\theta_{\ell-1}}^{\theta_{\ell}}\eta(u)\Lambda_{0}(\theta_{\ell},u){\rm d }u,$ $$

and $\sqrt{2}\int_{T_{\ell-1}}^{T_{\ell}}{\rm e}^{-(\varLambda(T_{\ell})-\varLambda
(t))}{\rm d}B_{t}$ is a zero-mean Gaussian random vector with covariance

$$ $2\int_{T_{\ell-1}}^{T_{\ell}}{\rm e}^{-2(\varLambda(T_{\ell})-\varLambda(t))}{ \rm d}t\cdot I=2\int_{T_{\ell-1}}^{T_{\ell}}\Lambda_{0}^{2}\left(\frac{T_{\ell }}{T},\frac{t}{T}\right){\rm d}t\cdot I=2T\int_{\theta_{\ell-1}}^{\theta_{\ell }}\Lambda_{0}^{2}(\theta_{\ell},u){\rm d}u\cdot I.$ $$

### B.2 Proof of Theorem 2

We denote the path measure of ALMC (Equation 6) by $\mathbb{Q}$. Then, $\mathbb{Q}_{T}$, the marginal distribution of $X_{T}$, serves as the output distribution $\nu^{\rm ALMC}$. Similar to the methodology in the proof of Theorem 1, we use $\mathbb{P}$ to denote the reference path measure of Equation 5, in which the vector field $(v_{t})_{t\in[0,T]}$ generates the cure of probability distributions $(\widetilde{\pi}_{t})_{t\in[0,T]}$.

Using the data-processing inequality, it suffices to demonstrate that $\operatorname{KL}\left(\mathbb{P}\middle\|\mathbb{Q}\right)\leq\varepsilon^{2}$. By Girsanov theorem (Lemma 1) and triangle inequality, we have

$$ $\displaystyle\operatorname{KL}\left(\mathbb{P}\middle\|\mathbb{Q}\right)$ $\displaystyle=\frac{1}{4}\int_{0}^{T}\operatorname{\mathbb{E}}_{\mathbb{P}} \left[\left\|\eta\left(\frac{t}{T}\right)\left(\nabla V(X_{t})-\nabla V(X_{t_{ -}})\right)-v_{t}(X_{t})\right\|^{2}\right]{\rm d}t$ $\displaystyle\lesssim\int_{0}^{T}\operatorname{\mathbb{E}}_{\mathbb{P}}\left[ \eta\left(\frac{t}{T}\right)^{2}\left\|\nabla V(X_{t})-\nabla V(X_{t_{-}}) \right\|^{2}+\left\|v_{t}(X_{t})\right\|^{2}\right]{\rm d}t$ $\displaystyle\leq\sum_{\ell=1}^{M}\eta\left(\frac{T_{\ell}}{T}\right)^{2}\beta ^{2}\int_{T_{\ell-1}}^{T_{\ell}}\operatorname{\mathbb{E}}_{\mathbb{P}}\left[ \left\|X_{t}-X_{t_{-}}\right\|^{2}\right]{\rm d}t+\int_{0}^{T}\left\|v_{t} \right\|_{L^{2}(\widetilde{\pi}_{t})}^{2}{\rm d}t.$ $$

The last inequality arises from the smoothness of $V$ and the increasing property of $\eta(\cdot)$. To bound $\operatorname{\mathbb{E}}_{\mathbb{P}}\left[\left\|X_{t}-X_{t_{-}}\right\|^{2}\right]$, note that under $\mathbb{P}$, for $t\in[T_{\ell-1},T_{\ell})$, we have

$$ $X_{t}-X_{t_{-}}=\int_{T_{\ell-1}}^{t}\left(\nabla\log\widetilde{\pi}_{\tau}+v_ {\tau}\right)(X_{\tau}){\rm d}\tau+\sqrt{2}(B_{t}-B_{T_{\ell-1}}).$ $$

Thanks to the fact that $X_{t}\sim\widetilde{\pi}_{t}$ under $\mathbb{P}$,

$$ $\displaystyle\operatorname{\mathbb{E}}_{\mathbb{P}}\left[\left\|X_{t}-X_{t_{-} }\right\|^{2}\right]$ $\displaystyle\lesssim\operatorname{\mathbb{E}}_{\mathbb{P}}\left[\left\|\int_{ T_{\ell-1}}^{t}\left(\nabla\log\widetilde{\pi}_{\tau}+v_{\tau}\right)(X_{\tau} ){\rm d}\tau\right\|^{2}\right]+\operatorname{\mathbb{E}}\left[\left\|\sqrt{2} (B_{t}-B_{T_{\ell-1}})\right\|^{2}\right]$ $\displaystyle\lesssim(t-{T_{\ell-1}})\int_{T_{\ell-1}}^{t}\operatorname{ \mathbb{E}}_{\mathbb{P}}\left[\left\|(\nabla\log\widetilde{\pi}_{\tau}+v_{\tau })(X_{\tau})\right\|^{2}\right]{\rm d}\tau+d(t-{T_{\ell-1}})$ $\displaystyle\lesssim(t-T_{\ell-1})\int_{T_{\ell-1}}^{t}\left(\left\|\nabla \log\widetilde{\pi}_{\tau}\right\|^{2}_{L^{2}(\widetilde{\pi}_{\tau})}+\left\| v_{\tau}\right\|_{L^{2}(\widetilde{\pi}_{\tau})}^{2}\right){\rm d}\tau+d(t-T_{ \ell-1})$ $\displaystyle\lesssim h_{\ell}\int_{T_{\ell-1}}^{T_{\ell}}\left(\left\|\nabla \log\widetilde{\pi}_{\tau}\right\|^{2}_{L^{2}(\widetilde{\pi}_{\tau})}+\left\| v_{\tau}\right\|_{L^{2}(\widetilde{\pi}_{\tau})}^{2}\right){\rm d}\tau+dh_{ \ell}.$ $$

The second inequality arises from the application of the Cauchy-Schwarz inequality, and the last inequality is due to the definition $h_{\ell}=T_{\ell}-T_{\ell-1}$. Taking integral over $t\in[T_{\ell-1},T_{\ell}]$,

$$ $\int_{T_{\ell-1}}^{T_{\ell}}\operatorname{\mathbb{E}}\left[\left\|X_{t}-X_{t_{ -}}\right\|^{2}\right]{\rm d}t\lesssim h_{\ell}^{2}\int_{T_{\ell-1}}^{T_{\ell} }\left(\left\|\nabla\log\widetilde{\pi}_{t}\right\|^{2}_{L^{2}(\widetilde{\pi} _{t})}+\left\|v_{t}\right\|_{L^{2}(\widetilde{\pi}_{t})}^{2}\right){\rm d}t+dh _{\ell}^{2}.$ $$

Recall that the potential of $\widetilde{\pi}_{t}$ is $\left(\eta\left(\frac{t}{T}\right)\beta+\lambda\left(\frac{t}{T}\right)\right)$-smooth. By Lemma 4 and the monotonicity of $\eta(\cdot)$ and $\lambda(\cdot)$, we have

$$ $\displaystyle\int_{T_{\ell-1}}^{T_{\ell}}\left\|\nabla\log\widetilde{\pi}_{t} \right\|^{2}_{L^{2}(\widetilde{\pi}_{t})}{\rm d}t$ $\displaystyle\leq\int_{T_{\ell-1}}^{T_{\ell}}d\left(\eta\left(\frac{t}{T} \right)\beta+\lambda\left(\frac{t}{T}\right)\right){\rm d}t$ $\displaystyle\leq dh_{\ell}\left(\beta\eta\left(\frac{T_{\ell}}{T}\right)+ \lambda\left(\frac{T_{\ell-1}}{T}\right)\right)$ $\displaystyle=dh_{\ell}\left(\beta\eta\left(\theta_{\ell}\right)+\lambda\left( \theta_{\ell-1}\right)\right).$ $$

Therefore, $\operatorname{KL}\left(\mathbb{P}\middle\|\mathbb{Q}\right)$ is upper bounded by

$$ $\displaystyle\lesssim\sum_{\ell=1}^{M}\eta\left(\theta_{\ell}\right)^{2}\beta^ {2}\int_{T_{\ell-1}}^{T_{\ell}}\operatorname{\mathbb{E}}_{\mathbb{P}}\left[ \left\|X_{t}-X_{t_{-}}\right\|^{2}\right]{\rm d}t+\int_{0}^{T}\left\|v_{t} \right\|_{L^{2}(\widetilde{\pi}_{t})}^{2}{\rm d}t$ $\displaystyle\lesssim\sum_{\ell=1}^{M}\eta\left(\theta_{\ell}\right)^{2}\beta^ {2}\left(dh_{\ell}^{3}\left(\beta\eta\left(\theta_{\ell}\right)+\lambda\left( \theta_{\ell-1}\right)\right)+h_{\ell}^{2}\int_{T_{\ell-1}}^{T_{\ell}}\left\|v _{t}\right\|_{L^{2}(\widetilde{\pi}_{t})}^{2}{\rm d}t+dh_{\ell}^{2}\right)+ \int_{0}^{T}\left\|v_{t}\right\|_{L^{2}(\widetilde{\pi}_{t})}^{2}{\rm d}t$ $\displaystyle=\sum_{\ell=1}^{M}\left(\left(1+\eta(\theta_{\ell})^{2}\beta^{2}h _{\ell}^{2}\right)\int_{T_{\ell-1}}^{T_{\ell}}\left\|v_{t}\right\|_{L^{2}( \widetilde{\pi}_{t})}^{2}{\rm d}t+\eta(\theta_{\ell})^{2}\beta^{2}dh_{\ell}^{2 }\left(1+h_{\ell}\left(\beta\eta(\theta_{\ell})+\lambda(\theta_{\ell-1})\right )\right)\right).$ $$

For the remaining integral, given that $(v_{t})_{t\in[0,T]}$ generates $(\widetilde{\pi}_{t})_{t\in[0,T]}$, according to Lemma 2, we may choose $v_{t}$ such that $\left\|v_{t}\right\|_{L^{2}(\widetilde{\pi}_{t})}=\left|\dot{\widetilde{\pi}}
\right|_{t}$. Thus,

$$ $\displaystyle\int_{T_{\ell-1}}^{T_{\ell}}\left\|v_{t}\right\|_{L^{2}( \widetilde{\pi}_{t})}^{2}{\rm d}t$ $\displaystyle=\int_{T_{\ell-1}}^{T_{\ell}}\left|\dot{\widetilde{\pi}}\right|_{ t}^{2}{\rm d}t=\int_{T_{\ell-1}}^{T_{\ell}}\frac{1}{T^{2}}\left|\dot{\pi} \right|^{2}_{t/T}{\rm d}t=\frac{1}{T}\int_{\theta_{\ell-1}}^{\theta_{\ell}} \left|\dot{\pi}\right|^{2}_{\theta}{\rm d}\theta,$ $$

through a change-of-variable analogous to that used in the proof of Theorem 1. Therefore,

$$ $\displaystyle\operatorname{KL}\left(\mathbb{P}\middle\|\mathbb{Q}\right)$ $\displaystyle\lesssim\sum_{\ell=1}^{M}\left(\frac{1+\eta(\theta_{\ell})^{2} \beta^{2}h_{\ell}^{2}}{T}\int_{\theta_{\ell-1}}^{\theta_{\ell}}\left|\dot{\pi} \right|^{2}_{\theta}{\rm d}\theta+\eta(\theta_{\ell})^{2}\beta^{2}dh_{\ell}^{2 }\left(1+h_{\ell}\left(\beta\eta(\theta_{\ell})+\lambda(\theta_{\ell-1})\right )\right)\right).$ $$

Assume $h_{\ell}\lesssim\frac{1}{\beta d}$ (which will be verified later), so we can further simplify the above expression to

$$ $\displaystyle\operatorname{KL}\left(\mathbb{P}\middle\|\mathbb{Q}\right)$ $\displaystyle\lesssim\sum_{\ell=1}^{M}\left(\frac{1}{T}\int_{\theta_{\ell-1}}^ {\theta_{\ell}}\left|\dot{\pi}\right|^{2}_{\theta}{\rm d}\theta+\eta(\theta_{ \ell})^{2}\beta^{2}dh_{\ell}^{2}\right)$ $\displaystyle=\frac{{\cal A}_{\eta,\lambda}(\pi)}{T}+\beta^{2}d\sum_{\ell=1}^{ M}\eta(\theta_{\ell})^{2}h_{\ell}^{2}$ $\displaystyle=\frac{{\cal A}_{\eta,\lambda}(\pi)}{T}+\beta^{2}d\sum_{\ell=1}^{ M}\eta(\theta_{\ell})^{2}T^{2}(\theta_{\ell}-\theta_{\ell-1})^{2}.$ $$

To bound the above expression by $\varepsilon^{2}$, we first select $T\asymp\frac{{\cal A}_{\eta,\lambda}(\pi)}{\varepsilon^{2}}$, mirroring the total time $T$ required for running annealed LD as specified in Theorem 1. This guarantees that the continuous dynamics closely approximate the reference path measure. Given that $\eta(\cdot)\leq 1$, it remains only to ensure

$$ $\beta^{2}d\sum_{\ell=1}^{M}\eta(\theta_{\ell})^{2}T^{2}(\theta_{\ell}-\theta_{ \ell-1})^{2}\leq\beta^{2}d\frac{{\cal A}_{\eta,\lambda}(\pi)^{2}}{\varepsilon^ {4}}\sum_{\ell=1}^{M}(\theta_{\ell}-\theta_{\ell-1})^{2}\lesssim\varepsilon^{2},$ $$

which is equivalent to

$$ $\sum_{\ell=1}^{M}(\theta_{\ell}-\theta_{\ell-1})^{2}\lesssim\frac{\varepsilon^ {6}}{d\beta^{2}{\cal A}_{\eta,\lambda}(\pi)^{2}}.$ (8) $$

To minimize $M$, we apply Cauchy-Schwarz inequality:

$$ $\left(\sum_{\ell=1}^{M}1\right)\left(\sum_{\ell=1}^{M}(\theta_{\ell}-\theta_{ \ell-1})^{2}\right)\geq\left(\sum_{\ell=1}^{M}(\theta_{\ell}-\theta_{\ell-1}) \right)^{2}=1,$ $$

which establishes a lower bound for $M$. The equality is achieved when $\theta_{\ell}-\theta_{\ell-1}=\frac{1}{M}$ for all $\ell\in\left[\!\left[1,M\right]\!\right]$. Thus, selecting

$$ $M\asymp\frac{d\beta^{2}{\cal A}_{\eta,\lambda}(\pi)^{2}}{\varepsilon^{6}}$ $$

satisfies the constraint given in Equation 8. In this case, the step size $h_{\ell}=\frac{T}{M}\asymp\frac{\varepsilon^{4}}{d\beta^{2}}\lesssim\frac{1}{
\beta d}$. Combining this with the $\widetilde{O}\left(1\right)$ complexity for sampling from $\pi_{0}$, we have completed the proof.

## Appendix C Proof of Example 1

The smoothness of $V$ comes from [cheng2023fast, Lemma 4].

Note that $\pi(x)\propto\sum_{i=1}^{N}p_{i}\exp\left(-\frac{\beta}{2}\left\|x-y_{i}\right
\|^{2}\right)$, and define

$$ $\displaystyle\widehat{\pi}_{\lambda}(x)$ $\displaystyle\propto\pi(x)\exp\left(-\frac{\lambda}{2}\left\|x\right\|^{2}\right)$ $\displaystyle=\sum_{i=1}^{N}p_{i}\exp\left(-\frac{\lambda\beta}{2(\lambda+ \beta)}\left\|y_{i}\right\|^{2}-\frac{\lambda+\beta}{2}\left\|x-\frac{\beta}{ \lambda+\beta}y_{i}\right\|^{2}\right)$ $\displaystyle\propto\sum_{i=1}^{N}p_{i}\exp\left(-\frac{\lambda+\beta}{2}\left \|x-\frac{\beta}{\lambda+\beta}y_{i}\right\|^{2}\right)$ $\displaystyle=\sum_{i=1}^{N}p_{i}\operatorname{{\cal N}}\left(\frac{\beta}{ \lambda+\beta}y_{i},\frac{1}{\lambda+\beta}I\right).$ $$

We use coupling method to upper bound $W_{2}^{2}(\widehat{\pi}_{\lambda},\widehat{\pi}_{\lambda+\delta})$. We first sample $I$ with distribution $\operatorname{\mathbb{P}}\left(I=i\right)=p_{i}$, $i\in\left[\!\left[1,N\right]\!\right]$, and then independently sample $\eta\sim\operatorname{{\cal N}}\left(0,I\right)$. Then,

$$ $\displaystyle X$ $\displaystyle:=\frac{\beta}{\lambda+\beta}y_{I}+\frac{1}{\sqrt{\lambda+\beta}} \eta\sim\widehat{\pi}_{\lambda},$ $\displaystyle Y$ $\displaystyle:=\frac{\beta}{\lambda+\delta+\beta}y_{I}+\frac{1}{\sqrt{\lambda+ \delta+\beta}}\eta\sim\widehat{\pi}_{\lambda+\delta}.$ $$

By definition of W2 distance, we have

$$ $\displaystyle W_{2}^{2}(\widehat{\pi}_{\lambda},\widehat{\pi}_{\lambda+\delta})$ $\displaystyle\leq\operatorname{\mathbb{E}}\left[\left\|X-Y\right\|^{2}\right]$ $\displaystyle=\operatorname{\mathbb{E}}_{I}\left[\operatorname{\mathbb{E}}_{ \eta}\left[\left\|\left(\frac{\beta}{\lambda+\beta}-\frac{\beta}{\lambda+ \delta+\beta}\right)y_{I}+\left(\frac{1}{\sqrt{\lambda+\beta}}-\frac{1}{\sqrt{ \lambda+\delta+\beta}}\right)\eta\right\|^{2}\right]\right]$ $\displaystyle=\operatorname{\mathbb{E}}_{I}\left[{\left(\frac{\beta}{\lambda+ \beta}-\frac{\beta}{\lambda+\delta+\beta}\right)^{2}\left\|y_{I}\right\|^{2}+ \left(\frac{1}{\sqrt{\lambda+\beta}}-\frac{1}{\sqrt{\lambda+\delta+\beta}} \right)^{2}d}\right]$ $\displaystyle=\left(\frac{\beta}{\lambda+\beta}-\frac{\beta}{\lambda+\delta+ \beta}\right)^{2}r^{2}+\left(\frac{1}{\sqrt{\lambda+\beta}}-\frac{1}{\sqrt{ \lambda+\delta+\beta}}\right)^{2}d.$ $$

This implies

$$ $\left|\dot{\widehat{\pi}}\right|^{2}_{\lambda}=\lim_{\delta\to 0}\frac{W_{2}^{ 2}(\widehat{\pi}_{\lambda},\widehat{\pi}_{\lambda+\delta})}{\delta^{2}}\leq \frac{\beta^{2}r^{2}}{(\lambda+\beta)^{4}}+\frac{d}{4(\lambda+\beta)^{3}}.$ $$

By time reparameterization $\pi_{\theta}=\widehat{\pi}_{\lambda(\theta)}$, $\left|\dot{\pi}\right|_{\theta}=\left|\dot{\widehat{\pi}}\right|_{\lambda(
\theta)}\left|\dot{\lambda}(\theta)\right|$. With $\lambda(\theta)=\lambda_{0}(1-\theta)^{\gamma}$, $\left|\dot{\lambda}(\theta)\right|=\left|\gamma\lambda_{0}(1-\theta)^{\gamma-1
}\right|\leq\gamma\lambda_{0}\lesssim\lambda_{0}$. Therefore,

$$ $\displaystyle{\cal A}_{\eta,\lambda}(\pi)$ $\displaystyle=\int_{0}^{1}\left|\dot{\pi}\right|_{\theta}^{2}{\rm d}\theta= \int_{0}^{1}\left|\dot{\widehat{\pi}}\right|_{\lambda(\theta)}^{2}\left|\dot{ \lambda}(\theta)\right|^{2}{\rm d}\theta$ $\displaystyle\lesssim\lambda_{0}\int_{0}^{1}\left|\dot{\widehat{\pi}}\right|_{ \lambda(\theta)}^{2}\left|\dot{\lambda}(\theta)\right|{\rm d}\theta=\lambda_{0 }\int_{0}^{\lambda_{0}}\left|\dot{\widehat{\pi}}\right|_{\lambda}^{2}{\rm d}\lambda$ $\displaystyle=\lambda_{0}\int_{0}^{\lambda_{0}}\left(\frac{\beta^{2}r^{2}}{( \lambda+\beta)^{4}}+\frac{d}{4(\lambda+\beta)^{3}}\right){\rm d}\lambda$ $\displaystyle\lesssim\lambda_{0}\left(\beta^{2}r^{2}\frac{1}{\beta^{3}}+d\frac {1}{\beta^{2}}\right)$ $\displaystyle\lesssim d\beta(r^{2}\beta+1)\left(\frac{r^{2}}{\beta}+\frac{d}{ \beta^{2}}\right)$ $\displaystyle=d(r^{2}\beta+1)\left(r^{2}+\frac{d}{\beta}\right).$ $$

It follows from the proof that as long as $\max_{\theta\in[0,1]}\left|\dot{\lambda}(\theta)\right|$ is bounded by a polynomial function of $\beta$, $d$ and $r$, so is the action ${\cal A}_{\eta,\lambda}(\pi)$.

## Appendix D Supplementary Lemmas

###### Lemma 4 ( [ chewi2022log , Lemma 4.E.1] ) .

Consider a probability measure $\mu\propto{\rm e}^{-U}$ on $\mathbb{R}^{d}$. If $\nabla^{2}U\preceq\beta I$ for some $\beta>0$, then $\operatorname{\mathbb{E}}_{\mu}\left[\left\|\nabla U\right\|^{2}\right]\leq\beta
d$.

###### Lemma 5 .

Under Assumption 1, $\pi_{\theta}$ defined in Equation 3 has finite second-order moment when $\eta(\theta)\in[0,1]$.

###### Proof.

When $\eta(\theta)=1$, $\pi_{\theta}\propto\exp\left(-V-\frac{\lambda(\theta)}{2}\left\|\cdot\right\|^
{2}\right)\leq\exp\left(-V\right)$, and the claim is straightforward. Otherwise, by convexity of $u\mapsto{\rm e}^{-u}$, we have

$$ $\displaystyle\exp\left(-\eta(\theta)V-\frac{\lambda(\theta)}{2}\left\|\cdot \right\|^{2}\right)$ $\displaystyle=\exp\left(-\eta(\theta)V-(1-\eta(\theta))\frac{\lambda(\theta)}{ 2(1-\eta(\theta))}\left\|\cdot\right\|^{2}\right)$ $\displaystyle\leq\eta(\theta)\exp\left(-V\right)+(1-\eta(\theta))\exp\left(- \frac{\lambda(\theta)}{2(1-\eta(\theta))}\left\|\cdot\right\|^{2}\right).$ $$

Multiplying both sides by $\left\|\cdot\right\|^{2}$ and taking integral over $\mathbb{R}^{d}$, we see that $\operatorname{\mathbb{E}}_{\pi_{\theta}}\left[\left\|\cdot\right\|^{2}\right]<
{+\infty}$.
∎

###### Lemma 4 ( [ chewi2022log , Lemma 4.E.1] ) .

###### Lemma 5 .

###### Proof.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
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.

- in Lemma 2, in what sense do the authors say the equality is "reachable"?

- 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?

- 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.
soundness: 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.
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.
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. 

- 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. 

- 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.

- 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.

- 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.

- 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.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
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.
soundness: 4
strengths: Computational bounds are generic- a smoothness constraint for target distribution, rather than isoperimetry assumptions.

Explanations are clear and well-illustrated, suiting a broad generalist audience by mixing intuition-building and commentary.

The direct impact of this paper is unclear, but the methods it introduces are interesting contributions
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
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

Note that I am not expert in all the components of the authors' proof, and have taken some steps on faith.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
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?
- What are the estimates of the action parameter $\mathcal{A}$ for a more general class of distributions than the mixture of Gaussians?
- 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. 
- 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?
soundness: 2
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.
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.
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. 
- 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. 
- 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.  
- Simple experiments on sampling from a mixture of Gaussians using the proposed and existing methods would significantly boost the paper. 
- 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)$. 
### Mathematical comments 

- *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. 
- *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. 
- *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.
- *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. 
- *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.

#### typos
- *line 956:* cure -> curve

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: Please see the weakness part.
soundness: 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.
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.
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?

Meta-review: This paper provides a non-asymptotic analysis of annealed MCMC. Authors establish an oracle complexity of a simple variant of annealed Langevin Monte Carlo and provide convergence guarantees for this algorithm to the target in KL divergence. Target is assumed to have a , smooth potential and the rate is in terms of action of a curve of measures that interpolates the target, which is an intriguing parameter.


This paper was reviewed by four reviewers the following Scores/Confidence: 8/4, 8/3, 6/4, 6/4. I think the paper is studying an interesting topic and the results are relevant to ICLR community. The following concerns were brought up by the reviewers:

- It is not clear if the rate is tight (most likely it is not). As is, the result seems to be another upper bound on sampling from a class of targets.
  
- Assumptions are not discussed in detail and compared with standard ones in the literature. This should be improved.

- Even though this is a theoretical paper, a detailed experimentation section would make the paper much stronger.
  
- minor typos were pointed by the reviewers. These should be carefully addressed. One reviewer requested detailed explanation of the integrator.


Authors should carefully go over reviewers' suggestions and address any remaining concerns in their final revision. Based on the reviewers' suggestion, as well as my own assessment of the paper, I recommend including this paper to the ICLR 2025 program.

Decision: Accept (Poster)