# Polynomial Mixing Times of Simulated Tempering for Mixture Targets by Conductance Decomposition

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

## Key facts

- No citing papers in the map yet (data through 7 Oct 2026).
- Builds on 10 of its 35 references that are in the map.
- First posted on arXiv 1 Nov 2025.

## Builds on (most cited first, 10 of 10)

- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo](https://mlsanity.com/paper/1710.02736/) (2017)
- [Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition](https://mlsanity.com/paper/1812.00793/) (2018)
- [Improved Bound for Mixing Time of Parallel Tempering](https://mlsanity.com/paper/2304.01303/) (2023)
- [Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition](https://mlsanity.com/paper/2405.19553/) (2024)
- [Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions](https://mlsanity.com/paper/2505.15059/) (2025)

## Abstract (arXiv)

We study the theoretical complexity of simulated tempering for sampling from mixtures of log-concave components differing only by location shifts. The main result establishes the first polynomial-time guarantee for simulated tempering combined with the Metropolis-adjusted Langevin algorithm (MALA) with respect to the problem dimension d, maximum mode displacement D, and logarithmic accuracy log ε-1. The proof builds on a general state decomposition theorem for s-conductance, applied to an auxiliary Markov chain constructed on an augmented space. We also obtain an improved complexity estimate for simulated tempering combined with random-walk Metropolis. Our bounds assume an inverse-temperature ladder with smallest value β1 = O(D-2) and spacing βi+1/βi = 1 + O( d-1/2 ), both of which are shown to be asymptotically optimal up to logarithmic factors.