Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.15059 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912624714711040 |
|---|---|
| author | Garg, Jhanvi Balasubramanian, Krishna Zhou, Quan |
| author_facet | Garg, Jhanvi Balasubramanian, Krishna Zhou, Quan |
| contents | Simulated tempering is a widely used strategy for sampling from multimodal distributions. In this paper, we consider simulated tempering combined with an arbitrary local Markov chain Monte Carlo sampler and present a new decomposition theorem that provides a lower bound on the restricted spectral gap of the algorithm for sampling from mixture distributions. By working with the restricted spectral gap, the applicability of our results is extended to broader settings such as when the usual spectral gap is difficult to bound or becomes degenerate. We demonstrate the application of our theoretical results by analyzing simulated tempering combined with random walk Metropolis--Hastings for sampling from mixtures of Gaussian distributions. Our complexity bound scales polynomially with the separation between modes, logarithmically with $1/\varepsilon$, where $\varepsilon$ denotes the target accuracy in total variation distance, and exponentially with the dimension $d$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_15059 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions Garg, Jhanvi Balasubramanian, Krishna Zhou, Quan Statistics Theory Probability Computation Machine Learning Simulated tempering is a widely used strategy for sampling from multimodal distributions. In this paper, we consider simulated tempering combined with an arbitrary local Markov chain Monte Carlo sampler and present a new decomposition theorem that provides a lower bound on the restricted spectral gap of the algorithm for sampling from mixture distributions. By working with the restricted spectral gap, the applicability of our results is extended to broader settings such as when the usual spectral gap is difficult to bound or becomes degenerate. We demonstrate the application of our theoretical results by analyzing simulated tempering combined with random walk Metropolis--Hastings for sampling from mixtures of Gaussian distributions. Our complexity bound scales polynomially with the separation between modes, logarithmically with $1/\varepsilon$, where $\varepsilon$ denotes the target accuracy in total variation distance, and exponentially with the dimension $d$. |
| title | Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions |
| topic | Statistics Theory Probability Computation Machine Learning |
| url | https://arxiv.org/abs/2505.15059 |