Convergence of Langevin AIS for multimodal distributions

Akshat Agarwal, Gautam Iyer, Aidan Jameson, Seungjae Son, Wyatt Wimmer · 2026

Read Convergence of Langevin AIS for multimodal distributions by Akshat Agarwal, Gautam Iyer, Aidan Jameson, Seungjae Son, Wyatt Wimmer (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-17526.txt.

Introduction

Agarwal and four colleagues study rates for annealed importance sampling combined with Langevin Monte Carlo on multimodal Gibbs measures. Their main result fixes an error threshold and shows time complexity growing as the square of inverse temperature. They find a simple number that controls sampling error for AIS in general, then bound it in their setting with spectral tools. An autonormalized version gets bounds of the same form, also in terms of inverse temperature.

Catalog record

CREATORAkshat Agarwal, Gautam Iyer, Aidan Jameson, Seungjae Son, Wyatt Wimmer
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE103537
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.17526

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Convergence of Langevin AIS for multimodal distributions Thanks: This work has been partially supported by the National Science Foundation under grants DMS-2406853, DMS-2342349 and the Center for Nonlinear Analysis. Akshat Agarwal, Gautam Iyer, Aidan Jameson, Seungjae Son, Wyatt Wimmer Abstract . We study convergence rates of the annealed importance sampling algorithm (Neal ’01) combined with Langevin Monte Carlo when the target is a multimodal Gibbs measure. The main result shows that for a fixed error threshold, the time complexity is quadratic in the inverse temperature . We identify a simple and useful quantity that controls the sampling error for AIS in a general setting, and then bound this quantity in our setting using spectral estimates. We also study an autonormalized version and obtain bounds for the time complexity in terms of the inverse temperature. 1991 Mathematics Subject Classification Primary: 60J22, Secondary: 65C05, 65C40. 1. Introduction 1.1. Main Results We begin by stating our main results, following which we survey the literature and place our results in the context of the current literature. Let \mathcal{X} be a configuration space and U\colon\mathcal{X}\to\mathbb{R} be an energy function. Given \varepsilon>0 , the Gibbs measure with temperature \varepsilon is defined by (1.1) \pi_{\varepsilon}\stackrel{{\scriptstyle\scriptscriptstyle\textup{def}}}{{=}}\frac{\tilde{\pi}_{\varepsilon}}{Z_{\varepsilon}}\quad\text{where}\quad\tilde{\pi}_{\varepsilon}=e^{-U/\varepsilon}\,,\quad\text{and}\quad Z_{\varepsilon}=\int_{\mathcal{X}}\tilde{\pi}_{\varepsilon}\,dx\,, where the last integral is carried out with respect to some reference measure on \mathcal{X} . We typically only consider the case where \mathcal{X} is the d -dimensional Euclidean space \mathbb{R}^{d} , or the d -dimensional torus \mathbb{T}^{d} . In these cases the reference measure in ( 1.1 ) is the Lebesgue measure. Consider the overdamped Langevin equation (1.2) dX^{\varepsilon}_{t}=-\nabla U(X^{\varepsilon}_{t})+\sqrt{2\varepsilon}\,dB_{t}\,, where B is a standard d -dimensional Brownian motion. It is well known (see for instance [ 38 ] ) that the stationary distribution of the Langevin equation is \pi_{\varepsilon} , and the Langevin Monte Carlo (LMC) algorithm obtains samples from \pi_{\varepsilon} by simulating ( 1.2 ) for long time. The disadvantage of LMC is that when U is not convex, the rate at which solutions to ( 1.2 ) converge to the stationary distribution is exponentially small in 1/\varepsilon . This is the Arrhenius law [ 2 ] , and is described in more detail below. We show that this slow rate of convergence can be overcome if one uses annealed importance sampling (AIS) [ 34 ] , or an autonormalized version of AIS. 1.1.1. Langevin Annealed Importance Sampling For convenience, we first state the Langevin AIS algorithm. Algorithm 1 Langevin Annealed Importance Sampling (Langevin AIS) 1: 2: (1) Target temperature \varepsilon>0 . (2) Annealing schedule K\in\mathbb{N} and \varepsilon_{1}>\cdots>\varepsilon_{K+1}=\varepsilon (3) LMC simulation time T . 3: Start with X_{0}\in\mathbb{T}^{d} arbitrary, and weight \tilde{w}_{0}=1 . 4: for k=1,\dots,K do 5: Simulate ( 1.2 ) with temperature \varepsilon_{k} , starting from X_{k-1} , and let X_{k} be the state after time T . 6: \tilde{w}_{k}\leftarrow\tilde{w}_{k-1}\frac{\tilde{\pi}_{\varepsilon_{k+1}}(X_{k})}{\tilde{\pi}_{\varepsilon_{k}}(X_{k})} . 7: end for 8: return X_{K} and the unnormalized weight \tilde{w}_{K} . Our main result shows that if we obtain N independent samples using Algorithm 1 , and empirically normalize the weights, then we obtain good samples from \pi_{\varepsilon} with time complexity that is quadratic in 1/\varepsilon . Theorem 1.1 . Suppose the configuration space \mathcal{X}=\mathbb{T}^{d} , and U is a regular double-well potential with non-degenerate wells of equal depth. Given \nu>0 , and \varepsilon_{1}>0 there exist constants C_{T}=C_{T}(\nu,U,\varepsilon_{1}) , \bar{C}_{w}(\nu,U,\varepsilon_{1}) such that the following holds. For every \delta>0 , \varepsilon\in(0,\varepsilon_{1}) , choose (1.3) \displaystyle K \displaystyle=\bigg\lceil\frac{1}{\varepsilon\nu}\bigg\rceil\,, (1.4) \displaystyle T \displaystyle>\max\Big\{C_{T}\Big(\frac{1}{\varepsilon}+\log K\Big),(4+\lvert\log_{2}\delta\rvert)t_{\mathrm{mix},\varepsilon_{1}}^{\infty}\Big\}\,, (1.5) \displaystyle N \displaystyle=\bigg\lceil\frac{64\bar{C}_{w}}{\delta^{2}}\bigg\rceil\,. Choose \varepsilon_{2} , …, \varepsilon_{K+1}=\varepsilon so that \{1/\varepsilon_{k}\}_{1\leqslant k\leqslant K+1} are linearly spaced. Let (X^{1}_{K},\tilde{w}^{1}_{K}) , …, (X^{N}_{K},\tilde{w}^{N}_{K}) be the points and unnormalized weights obtained from N independent runs of Algorithm 1 with these parameters. Define the empirical measure \mu_{N} by (1.6) \mu_{N}\stackrel{{\scriptstyle\scriptscriptstyle\textup{def}}}{{=}}\sum_{i=1}^{N}w_{i}\delta_{X^{i}_{K}}\quad\text{where}\quad w_{i}=\frac{\tilde{w}^{i}_{K}}{\tilde{W}_{K,N}}\quad\text{and}\quad\tilde{W}_{K,N}\stackrel{{\scriptstyle\scriptscriptstyle\textup{def}}}{{=}}\sum_{i=1}^{N}\tilde{w}^{i}_{K}\,. Then for every bounded test function f (1.7) \bm{E}\big\lvert\langle f,\mu_{N}\rangle-\langle f,\pi_{\varepsilon}\rangle\big\rvert^{2}<\lVert f\rVert_{\mathrm{osc}}^{2}\delta^{2}\,. Moreover, for every s>d/2 there exists an explicit dimensional constant C_{s} (independent of \varepsilon_{1},\varepsilon,\nu,\delta ) such that (1.8) \bm{E}\lVert\mu_{N}-\pi_{\varepsilon}\rVert_{\dot{H}^{-s}}^{2}\leqslant C_{s}\delta^{2}\,. Here t_{\mathrm{mix},\varepsilon_{1}}^{\infty} is the uniform mixing time of ( 1.2 ) on \mathbb{T}^{d} with \varepsilon=\varepsilon_{1} (see [ 25 ] , or ( 2.2 ), below). The notation \langle f,\mu\rangle used in ( 1.7 ) is (1.9) \langle f,\mu\rangle=\int_{\mathbb{T}^{d}}f\,d\mu\,, and \lVert\cdot\rVert_{\dot{H}^{-s}} denotes the norm in the homogeneous Sobolev space with index -s (for instance see [ 1 ] , or ( 4.33 ), below). Remark 1.2 (Effective sample size) . When working with weighted points as above, it is important to ensure that the weights don’t concentrate on a few particles reducing the overall efficiency. This is often measured by the effective sample size (see for instance Section 8.6 in [ 6 ] ) defined by (1.10) \ESS(w_{1},\dots,w_{N})\stackrel{{\scriptstyle\scriptscriptstyle\textup{def}}}{{=}}\frac{1}{\sum_{i=1}^{N}w_{i}^{2}}\,. We will show (see Proposition 2.7 and Remark 3.8 , below) that Theorem 1.1 implies that the effective sample size is bounded by (1.11) \bm{E}\ESS(w_{1},\dots,w_{N})=\bm{E}\left(\frac{1}{\sum_{i=1}^{N}w_{i}^{2}}\right)\geqslant\frac{N}{8\left(4\bar{C}_{w}+1\right)}\,. Remark 1.3 (Computational complexity) . We now discuss the asymptotic behavior of the computational complexity as the temperature \varepsilon\to 0 , and as the allowed error \delta\to 0 . Assuming the computational cost of simulating ( 1.2 ) for time T is O(T) , and neglecting the discretization error, the computational cost of Algorithm 1 to achieve the error bounds ( 1.7 ) or ( 1.8 ) is O(KTN) . Unravelling the \varepsilon and \delta dependence in ( 1.3 )–( 1.5 ) this implies (1.12) \operatorname{complexity}(\operatorname{Algorithm}\ref{a:aisLMC})=O(KTN)\leqslant\frac{C_{d}}{\delta^{2}}\Big(\frac{1}{\varepsilon^{2}}+\lvert\ln\delta\rvert\Big)\,, for some constant C_{d}=C_{d}(U) . For reference we mention that the computational complexity of Langevin Monte Carlo under these conditions is e^{O(1/\varepsilon)} , and the complexity of rejection sampling is O(1/\varepsilon^{d}) . A more comprehensive discussion and comparison is at the end of Section 1.2 , below. Remark 1.4 (Multiple wells, and wells of unequal depth.) . The assumption that U is a double well potential with wells of equal depth can be relaxed. If the wells have “nearly equal depth” so that the distribution remains truly multimodal in a temperature range, then Theorem 1.1 will still hold. The required assumptions and generalized theorem is Theorem 3.7 in Section 3 , below. If there are more than two wells, then Theorem 1.1 will still hold provided we make the same non-degeneracy assumptions as in Section 10 in [ 15 ] . Remark 1.5 . The constants C_{T} and \bar{C}_{w} in Theorem 1.1 involve dimensional factors that arise in spectral estimates and Sobolev embedding theorems. As a result, their dimensional dependence is not explicit (see ( 5.20 ) and ( 5.30 ), below). In special cases where U has a low dimensional structure, the dimensional dependence of these constants can be controlled for an idealized model problem (similar to Proposition 3.1 in [ 15 ] ), but their dimensional dependence is not explicit for the full Langevin system. Remark 1.6 . In practice, one often has a target distribution of the form \pi\propto e^{-V} which is hard to sample from. By the Arrhenius law, the complexity of using LMC to directly sample from \pi\propto e^{-V} is e^{O(H)} where H is the energy barrier. If instead if we choose \varepsilon=1/H and U=\varepsilon V , and use Langevin AIS to sample from \pi=\pi_{\varepsilon}\propto e^{-U/\varepsilon} , then by Remark 1.3 the time complexity is now only O(1/\varepsilon^{2})=O(H^{2}) . The proof of Theorem 1.1 consists of two steps: The first step is a general result concerning AIS. Given a family

Read the complete text