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

Holden Lee, Matheau Santana-GijzenarXiv 2025 · DOI · arXiv

Introduction

In Bayesian inference and machine learning, sampling from complex probability distributions is a fundamental task. A significant challenge arises when these distributions are multimodal, characterized by multiple high-probability regions separated by low-probability "valleys." Standard Markov Chain Monte Carlo (MCMC) methods, such as Langevin dynamics, often suffer from metastability, where the sampler becomes trapped in a single mode for an exponential amount of time.

While techniques like simulated tempering attempt to bridge these modes by flattening the distribution, they often encounter "bottlenecks" where mode weights collapse at intermediate temperatures. The Annealed Leap-Point Sampler (ALPS) was proposed to address this using "warm starts" (approximate mode locations) and Hessian-based weight estimation. However, ALPS relies on restrictive Gaussian assumptions that fail when modes have complex geometries or heavy tails.

The Reweighted ALPS (Re-ALPS) Algorithm

To overcome these limitations, we introduce Reweighted ALPS (Re-ALPS). This algorithm integrates three core components to ensure robust sampling across diverse modal structures:

  1. Simulated Tempering: A ladder of distributions is constructed, transitioning from the target distribution to "colder" versions localized around the warm start points.
  2. Leap-Point Process: At the coldest levels, the sampler can "teleport" between modes. The localization around warm starts ensures these jumps maintain high acceptance probabilities.
  3. Dynamic Reweighting: Unlike the original ALPS, which uses analytical Hessian approximations, Re-ALPS iteratively estimates the partition function (weight) of each mode at every temperature level using Monte Carlo simulation.
Figure 1: Illustration of unbalanced mode weights ($Z_{i,j}$) in a standard tempering scheme, where varying mode sizes can impede transitions.

By dynamically re-balancing these weights, Re-ALPS ensures that no mode becomes under-represented during the annealing process, creating a smooth path for the sampler to travel between peaks.

Figure 2: The reweighted state ($W_{i,j}$) in Re-ALPS, where modes are balanced to facilitate efficient leap-point transitions.

Theoretical and Empirical Results

The primary contribution of this work is the first non-asymptotic, polynomial-time convergence bound for sampling from multimodal distributions with warm starts. The mixing time is shown to scale polynomially with the dimension ($d$), the number of modes ($M$), and the target accuracy ($\epsilon$). A key technical innovation involves using $\chi^2$ bounds to prove that the sampler spends negligible time in "cross-term" regions where tilted distributions overlap.

Empirically, Re-ALPS was tested on a 5D synthetic mixture containing a quartic exponential, a Cauchy distribution, and a Gaussian. While the original ALPS failed (0% leap acceptance) due to inaccurate Hessian-based weight estimation for the non-Gaussian modes, Re-ALPS achieved a 43.5% leap acceptance rate and accurately recovered the true mode weights.

Conclusion and Future Work

Re-ALPS demonstrates that "weak advice" in the form of warm starts can transform an exponentially hard sampling problem into a polynomial-time one. Future research will focus on removing the requirement for pre-defined warm starts by discovering modes online and implementing adaptive tilting functions to better match local mode geometries.

Summary updated

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. We numerically evaluate our algorithm's mixing performance compared to ALPS on a mixture of heavy-tailed distributions.
BibTeX
@misc{lee2025sampling,
  author = {Holden Lee and Matheau Santana-Gijzen},
  title = {{Sampling from multimodal distributions with warm starts: Non-asymptotic bounds for the Reweighted Annealed Leap-Point Sampler}},
  year = {2025},
  eprint = {2512.17977},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.17977},
}
Figure