Complexity Results for MCMC derived from Quantitative Bounds

Abstract

This paper considers how to obtain MCMC quantitative convergence bounds which can be translated into tight complexity bounds in high-dimensional {settings}. We propose a modified drift-and-minorization approach, which establishes generalized drift conditions defined in subsets of the state space. The subsets are called the "large sets", and are chosen to rule out some "bad" states which have poor drift property when the dimension of the state space gets large. Using the "large sets" together with a "fitted family of drift functions", a quantitative bound can be obtained which can be translated into a tight complexity bound. As a demonstration, we analyze several Gibbs samplers and obtain complexity upper bounds for the mixing time. In particular, for one example of Gibbs sampler which is related to the James--Stein estimator, we show that the number of iterations required for the Gibbs sampler to converge is constant under certain conditions on the observed data and the initial state. It is our hope that this modified drift-and-minorization approach can be employed in many other specific examples to obtain complexity bounds for high-dimensional Markov chains.

to appear in Annals of Applied Probability

References in corpus (8)

• Renewal theory and computable convergence rates for geometrically ergodic Markov chains
• Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
• Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chains
• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
• On a generalization of the preconditioned Crank-Nicolson Metropolis algorithm
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• MCMC-Based Inference in the Era of Big Data: A Fundamental Analysis of the Convergence Complexity of High-Dimensional Chains
• Perturbation Bounds for Monte Carlo within Metropolis via Restricted Approximations

Cited by in corpus (6)

• Perturbation Bounds for Monte Carlo within Metropolis via Restricted Approximations
• No Free Lunch for Approximate MCMC
• Dimension-free Mixing for High-dimensional Bayesian Variable Selection
• On the limitations of single-step drift and minorization in Markov chain convergence analysis
• Optimal Scaling of Random-Walk Metropolis Algorithms on General Target Distributions
• Fast Markov chain Monte Carlo for high dimensional Bayesian regression models with shrinkage priors