# Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo

arXiv: https://arxiv.org/abs/1710.02736 · HTML: https://mlsanity.com/paper/1710.02736/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2017.

## Built on by (most cited first, 30 of 33)

- [Convergence for score-based generative modeling with polynomial complexity](https://mlsanity.com/paper/2206.06227/) (2022)
- [Statistical Efficiency of Score Matching: The View from Isoperimetry](https://mlsanity.com/paper/2210.00726/) (2022)
- [Critical windows: non-asymptotic theory for feature emergence in diffusion models](https://mlsanity.com/paper/2403.01633/) (2024)
- [Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling](https://mlsanity.com/paper/2407.16936/) (2024)
- [Fisher information lower bounds for sampling](https://mlsanity.com/paper/2210.02482/) (2022)
- [Polygonal Unadjusted Langevin Algorithms: Creating stable and efficient adaptive algorithms for neural networks](https://mlsanity.com/paper/2105.13937/) (2021)
- [Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond](https://mlsanity.com/paper/2502.04575/) (2025)
- [Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initialization](https://mlsanity.com/paper/2310.01762/) (2023)
- [Constrained Exploration via Reflected Replica Exchange Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2405.07839/) (2024)
- [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022)
- [Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions](https://mlsanity.com/paper/2306.09332/) (2023)
- [On the query complexity of sampling from non-log-concave distributions](https://mlsanity.com/paper/2502.06200/) (2025)
- [Improved Bound for Mixing Time of Parallel Tempering](https://mlsanity.com/paper/2304.01303/) (2023)
- [Persistently Trained, Diffusion-assisted Energy-based Models](https://mlsanity.com/paper/2304.10707/) (2023)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition](https://mlsanity.com/paper/2405.19553/) (2024)
- [Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion](https://mlsanity.com/paper/2501.00565/) (2024)
- [Finite Sample Complexity of Sequential Monte Carlo Estimators on Multimodal Target Distributions](https://mlsanity.com/paper/2208.06672/) (2022)
- [A noise-corrected Langevin algorithm and sampling by half-denoising](https://mlsanity.com/paper/2410.05837/) (2024)
- [Dimension-Free Multimodal Sampling via Preconditioned Annealed Langevin Dynamics](https://mlsanity.com/paper/2602.01449/) (2026)
- [Diffusion models recover accurate mixture weights despite score function insensitivity](https://mlsanity.com/paper/2607.15485/) (2026)
- [Fisher information dissipation for time inhomogeneous stochastic differential equations](https://mlsanity.com/paper/2402.01036/) (2024)
- [Query Lower Bounds for Diffusion Sampling](https://mlsanity.com/paper/2604.10857/) (2026)
- [Improved Langevin Monte Carlo for stochastic optimization via landscape modification](https://mlsanity.com/paper/2302.03973/) (2023)
- [Subsampling Error in Stochastic Gradient Langevin Diffusions](https://mlsanity.com/paper/2305.13882/) (2023)
- [Sampling with Adaptive Variance for Multimodal Distributions](https://mlsanity.com/paper/2411.15220/) (2024)
- [Can We Do Better Than Random Start? The Power of Data Outsourcing](https://mlsanity.com/paper/2205.08098/) (2022)
- [Exploring Non-Convex Discrete Energy Landscapes: An Efficient Langevin-Like Sampler with Replica Exchange](https://mlsanity.com/paper/2501.17323/) (2025)
- [Estimating Multi-chirp Parameters using Curvature-guided Langevin Monte Carlo](https://mlsanity.com/paper/2501.18178/) (2025)
- [Improved sampling algorithms and functional inequalities for non-log-concave distributions](https://mlsanity.com/paper/2507.11236/) (2025)

## Abstract (arXiv)

A key task in Bayesian statistics is sampling from distributions that are only specified up to a partition function (i.e., constant of proportionality). However, without any assumptions, sampling (even approximately) can be #P-hard, and few works have provided "beyond worst-case" guarantees for such settings. For log-concave distributions, classical results going back to Bakry and 'Emery (1985) show that natural continuous-time Markov chains called Langevin diffusions mix in polynomial time. The most salient feature of log-concavity violated in practice is uni-modality: commonly, the distributions we wish to sample from are multi-modal. In the presence of multiple deep and well-separated modes, Langevin diffusion suffers from torpid mixing. We address this problem by combining Langevin diffusion with simulated tempering. The result is a Markov chain that mixes more rapidly by transitioning between different temperatures of the distribution. We analyze this Markov chain for the canonical multi-modal distribution: a mixture of gaussians (of equal variance). The algorithm based on our Markov chain provably samples from distributions that are close to mixtures of gaussians, given access to the gradient of the log-pdf. For the analysis, we use a spectral decomposition theorem for graphs (Gharan and Trevisan, 2014) and a Markov chain decomposition technique (Madras and Randall, 2002).