# Dimension-free Relaxation Times of Informed MCMC Samplers on Discrete Spaces

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 79 references that are in the map.
- First posted on arXiv 5 Apr 2024.

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

- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [A Langevin-like Sampler for Discrete Distributions](https://mlsanity.com/paper/2206.09914/) (2022)
- [On the Computational Complexity of High-Dimensional Bayesian Variable Selection](https://mlsanity.com/paper/1505.07925/) (2015)
- [The Hamming Ball Sampler](https://mlsanity.com/paper/1504.08133/) (2015)
- [Scalable Importance Tempering and Bayesian Variable Selection](https://mlsanity.com/paper/1805.00541/) (2018)
- [Dimension-free Mixing for High-dimensional Bayesian Variable Selection](https://mlsanity.com/paper/2105.05719/) (2021)
- [Extended Stochastic Block Models with Application to Criminal Networks](https://mlsanity.com/paper/2007.08569/) (2020)
- [Improving multiple-try Metropolis with local balancing](https://mlsanity.com/paper/2211.11613/) (2022)
- [Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)](https://mlsanity.com/paper/1603.01512/) (2016)
- [Order-based Structure Learning without Score Equivalence](https://mlsanity.com/paper/2202.05150/) (2022)
- [Rapidly Mixing Multiple-try Metropolis Algorithms for Model Selection Problems](https://mlsanity.com/paper/2207.00689/) (2022)
- [Dimension-free mixing times of Gibbs samplers for Bayesian hierarchical models](https://mlsanity.com/paper/2304.06993/) (2023)
- [On Mixing Rates for Bayesian CART](https://mlsanity.com/paper/2306.00126/) (2023)
- [Scalability of Metropolis-within-Gibbs schemes for high-dimensional Bayesian models](https://mlsanity.com/paper/2403.09416/) (2024)

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

- [A phase transition in sampling from Restricted Boltzmann Machines](https://mlsanity.com/paper/2410.08423/) (2024)
- [Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions](https://mlsanity.com/paper/2505.15059/) (2025)
- [Leveraging heterogeneity for identifiability: Bayesian order-based learning of multiple DAGs](https://mlsanity.com/paper/2605.15639/) (2026)

## Abstract (arXiv)

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.