Dimension-free Relaxation Times of Informed MCMC Samplers on Discrete Spaces
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916865444413440 |
|---|---|
| author | Chang, Hyunwoong Zhou, Quan |
| author_facet | Chang, Hyunwoong Zhou, Quan |
| contents | Convergence analysis of Markov chain Monte Carlo methods in high-dimensional statistical applications is increasingly recognized. In this paper, we develop general mixing time bounds for Metropolis-Hastings algorithms on discrete spaces by building upon and refining some recent theoretical advancements in Bayesian model selection problems. We establish sufficient conditions for a class of informed Metropolis-Hastings algorithms to attain relaxation times that are independent of the problem dimension. These conditions are grounded in the high-dimensional statistical theory and allow for possibly multimodal posterior distributions. We obtain our results through two independent techniques: the multicommodity flow method and single-element drift condition analysis; we find that the latter yields a slightly tighter mixing time bound. Our results are readily applicable to a broad spectrum of statistical problems with discrete parameter spaces, as we demonstrate using both theoretical and numerical examples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_03867 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dimension-free Relaxation Times of Informed MCMC Samplers on Discrete Spaces Chang, Hyunwoong Zhou, Quan Computation Probability Machine Learning 60J10, 60J20, 82M31, 62F15 Convergence analysis of Markov chain Monte Carlo methods in high-dimensional statistical applications is increasingly recognized. In this paper, we develop general mixing time bounds for Metropolis-Hastings algorithms on discrete spaces by building upon and refining some recent theoretical advancements in Bayesian model selection problems. We establish sufficient conditions for a class of informed Metropolis-Hastings algorithms to attain relaxation times that are independent of the problem dimension. These conditions are grounded in the high-dimensional statistical theory and allow for possibly multimodal posterior distributions. We obtain our results through two independent techniques: the multicommodity flow method and single-element drift condition analysis; we find that the latter yields a slightly tighter mixing time bound. Our results are readily applicable to a broad spectrum of statistical problems with discrete parameter spaces, as we demonstrate using both theoretical and numerical examples. |
| title | Dimension-free Relaxation Times of Informed MCMC Samplers on Discrete Spaces |
| topic | Computation Probability Machine Learning 60J10, 60J20, 82M31, 62F15 |
| url | https://arxiv.org/abs/2404.03867 |