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

2025/11/01 by Zhou, Quan · 1 citation
#60J20 #65C05 #65C40 #68Q25 #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Probability (math.PR)

paper · doi:10.48550/arxiv.2511.00708

Abstract

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 β₁ = 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.

Citations

• Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions
• On spectral gap decomposition for Markov chains
• Quantifying the Speed-Up from Non-Reversibility in MCMC Tempering Algorithms
• Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition
• Improved Bound for Mixing Time of Parallel Tempering
• Improved analysis for a proximal algorithm for sampling
• Optimal dimension dependence of the Metropolis-Adjusted Langevin\n Algorithm
• Approximate spectral gaps for Markov chains mixing times in high dimensions
• Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo
• High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm
• Elementary Bounds On Mixing Times for Decomposable Markov Chains
• Log-concavity and strong log-concavity: a review
• Non-asymptotic mixing of the MALA algorithm

Cited by

• Convergence analysis of data augmentation algorithms in Bayesian lasso models with log-concave likelihoods

Related

• Improved Bound for Mixing Time of Parallel Tempering
• Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions
• Weight-Preserving Simulated Tempering
• Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
• Accelerating Parallel Tempering: Quantile Tempering Algorithm (QuanTA)