Research map / Learning theory and algorithms / Sample complexity
Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves a discrete-time decomposition bound on the restricted spectral gap of simulated tempering for Gaussian mixtures and derives a mixing-time bound for simulated tempering with random walk Metropolis-Hastings (STMH) that is logarithmic in 1/epsilon, polynomial in separation D, and exponential in dimension d.
Problem
Sampling from multimodal distributions (Gaussian mixtures) is slow for local MCMC; spectral gap bounds for discrete-time MH chains over unbounded spaces are hard to obtain, and existing analyses are continuous-time or lose factors.
Approach
A discrete-time decomposition theorem that bounds the restricted spectral gap of simulated tempering by separately bounding local chains on each mixture component and a projected chain over components and temperatures, with a new projected-chain construction that simplifies the proof and needs only restricted gaps for local chains.
Key results
- Theorem gives STMH mixing time poly(1/w_min, D, kappa) * log^3(1/epsilon) for fixed d, with exponential dependence on d.
- In simulation with D up to 30, steps for STMH grow approximately linearly in D^2, while baseline MH grows exponentially in D^2.
- For fixed D=30, STMH steps scale approximately linearly with log^2(1/||mu_hat||), versus near-logarithmic for MH.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use simulated tempering with random-walk Metropolis–Hastings instead of baseline MH | sampling the 2D symmetric Gaussian mixture as separation D increases · 2D symmetric Gaussian mixture, D varied | steps until empirical mean falls below 0.1 | Helped |
| Use STMH instead of baseline MH | sampling the 2D symmetric Gaussian mixture at D = 30 · 2D symmetric Gaussian mixture, D = 30 | dependence of mixing time on accuracy threshold | Helped |
| Use STMH instead of STLMC | sampling Gaussian mixture distributions · Gaussian mixture distributions | time complexity dependence on 1/ε | Mixed |
| Use STMH instead of the Proximal Sampler | sampling Gaussian mixture distributions · Gaussian mixture distributions | time complexity dependence on D | Helped |
| Use STMH instead of the Proximal Sampler | sampling Gaussian mixture distributions · Gaussian mixture distributions | time complexity dependence on 1/ε | Mixed |
Surprising findings
- Baseline MH steps grow exponentially with D^2 in the simulation, consistent with known MH limitations.
Limitations
- Complexity depends exponentially on dimension d due to RWMH local chains.
- Results restricted to Gaussian mixtures with shared covariance; extension to near-mixtures only sketched.
- Lower bounds on spectral gap only; tightness not established.
Experimental setup
Benchmarks: two-dimensional symmetric Gaussian mixture
Metrics: steps until empirical mean norm falls below 0.1 norm of empirical mean versus steps
Baselines: Metropolis-Hastings STLMC LMC annealed LMC proximal sampler data-initialized LMC
Builds on: simulated tempering Chen et al. continuous-time decomposition for simulated tempering Langevin canonical path method restricted spectral gap mixing bounds
Closest papers by meaning
- Continuously Tempered PDMP samplers (NeurIPS 2022 · similarity 0.89)
- Provable Convergence and Limitations of Geometric Tempering for Langevin Dynamics (ICLR 2025 · similarity 0.87)
- Multi-Marginal Couplings for Metropolis--Hastings (NeurIPS 2026 · similarity 0.85)
- Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion (NeurIPS 2025 · similarity 0.85)
- Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion (NeurIPS 2024 · similarity 0.84)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.