Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles

Abstract

We derive the first explicit bounds for the spectral gap of a random walk Metropolis algorithm on $R^d$ for any value of the proposal variance, which when scaled appropriately recovers the correct $d^{-1}$ dependence on dimension for suitably regular invariant distributions. We also obtain explicit bounds on the ${\mathrm{L}}^2$-mixing time for a broad class of models. In obtaining these results, we refine the use of isoperimetric profile inequalities to obtain conductance profile bounds, which also enable the derivation of explicit bounds in a much broader class of models. We also obtain similar results for the preconditioned Crank--Nicolson Markov chain, obtaining dimension-independent bounds under suitable assumptions.

References in corpus (11)

• Renewal theory and computable convergence rates for geometrically ergodic Markov chains
• Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Between Sobolev and Poincaré
• On the Computational Complexity of MCMC-based Estimators in Large Samples
• Explicit error bounds for lazy reversible Markov Chain Monte Carlo
• On the role of Convexity in Functional and Isoperimetric Inequalities
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling
• An Efficient Sampling Algorithm for Non-smooth Composite Potentials
• Poincaré inequalities for Markov chains: a meeting with Cheeger, Lyapunov and Metropolis

Cited by in corpus (3)

• Optimal convergence rates of MCMC integration for functions with unbounded second moment
• Sharp detection of low-dimensional structure in probability measures via dimensional logarithmic Sobolev inequalities
• Scalable couplings for the random walk Metropolis algorithm