# Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2018.

## Built on by (most cited first, 18 of 18)

- [Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling](https://mlsanity.com/paper/2407.16936/) (2024)
- [On the Edge of Memorization in Diffusion Models](https://mlsanity.com/paper/2508.17689/) (2025)
- [MDNS: Masked Diffusion Neural Sampler via Stochastic Optimal Control](https://mlsanity.com/paper/2508.10684/) (2025)
- [Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initialization](https://mlsanity.com/paper/2310.01762/) (2023)
- [Provable Convergence and Limitations of Geometric Tempering for Langevin Dynamics](https://mlsanity.com/paper/2410.09697/) (2024)
- [Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods](https://mlsanity.com/paper/2202.08907/) (2022)
- [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)
- [Markov Chain Monte Carlo with Diffusion Paths](https://mlsanity.com/paper/2607.11631/) (2026)
- [Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition](https://mlsanity.com/paper/2405.19553/) (2024)
- [Proposal of a Score Based Approach to Sampling Using Monte Carlo Estimation of Score and Oracle Access to Target Density](https://mlsanity.com/paper/2212.03325/) (2022)
- [Efficient Multimodal Sampling via Tempered Distribution Flow](https://mlsanity.com/paper/2304.03933/) (2023)
- [Reflection coupling for unadjusted generalized Hamiltonian Monte Carlo in the nonconvex stochastic gradient case](https://mlsanity.com/paper/2310.18774/) (2023)
- [Enhancing Gradient-based Discrete Sampling via Parallel Tempering](https://mlsanity.com/paper/2502.19240/) (2025)
- [Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions](https://mlsanity.com/paper/2505.15059/) (2025)
- [Slowly Annealed Langevin Dynamics: Theory and Applications to Training-Free Guided Generation](https://mlsanity.com/paper/2605.07950/) (2026)
- [Can We Do Better Than Random Start? The Power of Data Outsourcing](https://mlsanity.com/paper/2205.08098/) (2022)
- [Polynomial Mixing Times of Simulated Tempering for Mixture Targets by Conductance Decomposition](https://mlsanity.com/paper/2511.00708/) (2025)

## Abstract (arXiv)

A key task in Bayesian machine learning is sampling from distributions that are only specified up to a partition function (i.e., constant of proportionality). One prevalent example of this is sampling posteriors in parametric distributions, such as latent-variable generative models. However sampling (even very approximately) can be #P-hard. Classical results going back to Bakry and 'Emery (1985) on sampling focus on log-concave distributions, and show a natural Markov chain called Langevin diffusion mixes in polynomial time. However, all log-concave distributions are uni-modal, while in practice it is very common for the distribution of interest to have multiple modes. In this case, 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 a mixture of (strongly) log-concave distributions of the same shape. In particular, our technique applies to the canonical multi-modal distribution: a mixture of gaussians (of equal variance). Our algorithm efficiently samples from these distributions given only access to the gradient of the log-pdf. For the analysis, we introduce novel techniques for proving spectral gaps based on decomposing the action of the generator of the diffusion. Previous approaches rely on decomposing the state space as a partition of sets, while our approach can be thought of as decomposing the stationary measure as a mixture of distributions (a "soft partition"). Additional materials for the paper can be found at http://holdenlee.github.io/Simulated%20tempering%20Langevin%20Monte%20Carlo.html. The proof and results have been improved and generalized from the precursor at arXiv:1710.02736.