Explicit error bounds for Markov chain Monte Carlo

Abstract

We prove explicit, i.e. non-asymptotic, error bounds for Markov chain Monte Carlo methods. The problem is to compute the expectation of a function f with respect to a measure π. Different convergence properties of Markov chains imply different error bounds. For uniformly ergodic and reversible Markov chains we prove a lower and an upper error bound with respect to the L2 -norm of f . If there exists an L2 -spectral gap, which is a weaker convergence property than uniform ergodicity, then we show an upper error bound with respect to the Lp -norm of f for p > 2. Usually a burn-in period is an efficient way to tune the algorithm. We provide and justify a recipe how to choose the burn-in period. The error bounds are applied to the problem of the integration with respect to a possibly unnormalized density. More precise, we consider the integration with respect to log-concave densities and the integration over convex bodies. By the use of the Metropolis algorithm based on a ball walk and the hit-and-run algorithm it is shown that both problems are polynomial tractable.

References in corpus (3)

• MCMC using Hamiltonian dynamics
• Renewal theory and computable convergence rates for geometrically ergodic Markov chains
• Nonasymptotic bounds on the estimation error for regenerative MCMC algorithms

Cited by in corpus (34)

• Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions
• On a generalization of the preconditioned Crank-Nicolson Metropolis algorithm
• Markov Chain Monte Carlo Estimation of Quantiles
• Positivity of hit-and-run and related algorithms
• Hoeffding's lemma for Markov Chains and its applications to statistical learning
• Complexity Results for MCMC derived from Quantitative Bounds
• On the Lq(Lp)-regularity and Besov smoothness of stochastic parabolic equations on bounded Lipschitz domains
• Hit-and-run for numerical integration
• Approximations of Geometrically Ergodic Reversible Markov Chains
• Generalized Parallel Tempering on Bayesian Inverse Problems
• Convergence of hybrid slice sampling via spectral gap
• Metropolis-Hastings reversiblizations of non-reversible Markov chains
• Importance sampling correction versus standard averages of reversible MCMCs in terms of the asymptotic variance
• A Hierarchical Multilevel Markov Chain Monte Carlo Algorithm with Applications to Uncertainty Quantification in Subsurface Flow
• Error bounds of MCMC for functions with unbounded stationary variance
• Discrepancy estimates for variance bounding Markov chain quasi-Monte Carlo
• Computation of expectations by Markov chain Monte Carlo methods
• Establishing some order amongst exact approximations of MCMCs
• On a Metropolis-Hastings importance sampling estimator
• Comparison of hit-and-run, slice sampling and random walk Metropolis
• AMAGOLD: Amortized Metropolis Adjustment for Efficient Stochastic Gradient MCMC
• Non-asymptotic confidence intervals for MCMC in practice
• Geometric convergence of elliptical slice sampling
• Dimension-independent Markov chain Monte Carlo on the sphere
• Concentration Inequalities for Sums of Markov Dependent Random Matrices
• Asymptotically Optimal Exact Minibatch Metropolis-Hastings
• Almost sure convergence rates of adaptive increasingly rare Markov chain Monte Carlo
• Convergence Speed and Approximation Accuracy of Numerical MCMC
• Convergence of Contrastive Divergence Algorithm in Exponential Family
• Optimal convergence rates of MCMC integration for functions with unbounded second moment
• Wasserstein contraction and spectral gap of slice sampling revisited
• Adaptive Huber Regression on Markov-dependent Data
• Some Results on the Complexity of Numerical Integration
• Convergence of Contrastive Divergence with Annealed Learning Rate in Exponential Family