# Improved Bound for Mixing Time of Parallel Tempering

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 7 references that are in the map.
- First posted on arXiv 3 Apr 2023.

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

- [Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo](https://mlsanity.com/paper/1710.02736/) (2017)

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

- [Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling](https://mlsanity.com/paper/2407.16936/) (2024)
- [Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion](https://mlsanity.com/paper/2402.17886/) (2024)
- [Operator-Level Quantum Acceleration of Non-Logconcave Sampling](https://mlsanity.com/paper/2505.05301/) (2025)
- [Polynomial Mixing Times of Simulated Tempering for Mixture Targets by Conductance Decomposition](https://mlsanity.com/paper/2511.00708/) (2025)

## Abstract (arXiv)

In the field of sampling algorithms, MCMC (Markov Chain Monte Carlo) methods are widely used when direct sampling is not possible. However, multimodality of target distributions often leads to slow convergence and mixing. One common solution is parallel tempering. Though highly effective in practice, theoretical guarantees on its performance are limited. In this paper, we present a new lower bound for parallel tempering on the spectral gap that has a polynomial dependence on all parameters except log L, where (L + 1) is the number of levels. This improves the best existing bound which depends exponentially on the number of modes. Moreover, we complement our result with a hypothetical upper bound on spectral gap that has an exponential dependence on log L, which shows that, in some sense, our bound is tight.