Sampling from multimodal distributions with warm starts: Non-asymptotic bounds for the Reweighted Annealed Leap-Point Sampler

Holden Lee; Matheau Santana-Gijzen

stat.MLDec 19, 2025

Sampling from multimodal distributions with warm starts: Non-asymptotic bounds for the Reweighted Annealed Leap-Point Sampler

Authors: Holden Lee, Matheau Santana-Gijzen

Abstract

Sampling from multimodal distributions is a central challenge in Bayesian inference and machine learning. In light of hardness results for sampling -- classical MCMC methods, even with tempering, can suffer from exponential mixing times -- a natural question is how to leverage additional information, such as a warm start point for each mode, to enable faster mixing across modes. To address this, we introduce Reweighted ALPS (Re-ALPS), a modified version of the Annealed Leap-Point Sampler (ALPS) that dispenses with the Gaussian approximation assumption. We prove the first polynomial-time bound that works in a general setting, under a natural assumption that each component contains significant mass relative to the others when tilted towards the corresponding warm start point. Similarly to ALPS, we define distributions tilted towards a mixture centered at the warm start points, and at the coldest level, use teleportation between warm start points to enable efficient mixing across modes. In contrast to ALPS, our method does not require Hessian information at the modes, but instead estimates component partition functions via Monte Carlo. This additional estimation step is crucial in allowing the algorithm to handle target distributions with more complex geometries besides approximate Gaussian. For the proof, we show convergence results for Markov processes when only part of the stationary distribution is well-mixing and estimation for partition functions for individual components of a mixture.

Figures & tables

w_{l+1,k}=\frac{1}{\frac{1}{N}\sum_{j=1}^{N}\frac{\bar{\pi}_{l+1,k}(x_{j})}{\tilde{p}(x_{j},i_{j})}I\{i_{j}=l\}}

Algorithm 3 Reweighting via Partition Function Estimation

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: An illustration of good (solid) and bad (dashed) mixture components. The good components are sharply peaked around the warm-start locations, while the bad pseudo-modes from cross-terms have negligible mass.

Explore similar work

Jul 8, 2026

Gradient-free Riemannian Langevin Sampler

We address the problem of efficiently sampling multimodal probability distributions, where standard Markov Chain Monte Carlo methods often suffer from poor mixing and mode trapping. To mitigate these issues, we propose Gradient-free Riemannian Langevin Sampler (GRiLS), a novel proposal that improves exploration without requiring gradient evaluations of the target density. Our approach introduces a Riemannian metric which reshapes the local geometry in order to facilitate transitions across modes. The resulting gradient-free MCMC algorithm is particularly suitable for complex, computationally expensive targets where derivatives are unavailable or impractical. The GRiLS proposal requires knowing the mean and covariance of the target density, which we estimate using an ensemble of interacting particles. Empirical results on multimodal benchmarks demonstrate that GRiLS achieves improved mixing compared to existing gradient-based and gradient-free MCMC approaches.

Ricardo Baptista, Olivier Zahm

Department of Statistical Sciences, University of Toronto, Canada · UGA, Inria, CNRS, Grenoble INP*, LJK, 38000 Grenoble, France

Markov Chain Monte Carlo

Ask PDF

Sep 2, 2025

Bouncy particle sampler with infinite exchanging parallel tempering

Markov chain Monte Carlo is one of the most useful tools for obtaining samples from complex distributions, such as posterior distributions in Bayesian inference. Bouncy particle sampler (BPS) is a method that performs sampling using uniform linear motion and elastic collisions. Since BPS does not require time discretization, it is expected to be more advantageous than the widely used Hamiltonian Monte Carlo (HMC) and Langevin Monte Carlo (LMC) for distributions with large curvature changes. To sample more efficiently from multimodal distributions, we propose BPS with parallel tempering (BPS-PT) in the infinite exchange limit, based on LMC-PT with the infinite exchange rate proposed in a previous study. Using a distribution with large curvature changes, BPS-PT showed estimation accuracy comparable to HMC-PT and LMC-PT, and achieved higher ESS per computational time. Therefore, BPS-PT is considered to be effective for distributions with large curvature changes.

Yohei Saito, Shun Kimura, Koujin Takeda

Center for Mathematics and Data Science, Gunma University · Graduate School of Science and Engineering, Ibaraki University

Markov Chain Monte Carlo Parallel Tempering

Ask PDF

Mar 24, 2026

Algorithmic warm starts for Hamiltonian Monte Carlo

Generating samples from a continuous probability density is a central algorithmic problem across statistics, engineering, and the sciences. For high-dimensional settings, Hamiltonian Monte Carlo (HMC) is the default algorithm across mainstream software packages. However, despite the extensive line of work on HMC and its widespread empirical success, it remains unclear how many iterations of HMC are required as a function of the dimension

d

. On one hand, a variety of results show that Metropolized HMC converges in

O(d^{1/4})

iterations from a warm start close to stationarity. On the other hand, Metropolized HMC is significantly slower without a warm start, e.g., requiring

Ω(d^{1/2})

iterations even for simple target distributions such as isotropic Gaussians. Finding a warm start is therefore the computational bottleneck for HMC. We resolve this issue for the well-studied setting of sampling from a probability distribution satisfying strong log-concavity (or isoperimetry) and third-order derivative bounds. We prove that non-Metropolized HMC generates a warm start in

\tilde{O}(d^{1/4})

iterations, after which we can exploit the warm start using Metropolized HMC. Our final complexity of

\tilde{O}(d^{1/4})

is the fastest algorithm for high-accuracy sampling under these assumptions, improving over the prior best of

\tilde{O}(d^{1/2})

. This closes the long line of work on the dimensional complexity of MHMC for such settings, and also provides a simple warm-start prescription for practical implementations.

Matthew S. Zhang, Jason M. Altschuler, Sinho Chewi

UToronto · UPenn · Yale

Markov Chain Monte Carlo Sample Complexity Log-Concave Sampling

Ask PDF