Explicit error bounds for Markov chain Monte Carlo

DOI10.4064/DM485-0-1MaRDI QIDQ2896206zbMATH OpenOpenAlexFDO

Authors Daniel Rudolf

Publication date 13 July 2012

Published in Dissertationes Mathematicae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.3201

zbMATH Keywords

ball walkburn-inerror boundsgeometric ergodicityhit-and-run algorithmlog-concave densityMarkov chain Monte Carlomean square errormetropolis algorithmspectral gapuniform ergodicity

Mathematics Subject Classification ID

Ergodicity, mixing, rates of mixing (37A25) Discrete-time Markov processes on general state spaces (60J05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Computational methods in Markov chains (60J22)

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 {pi}. 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.

Recommendations

• Explicit error bounds for lazy reversible Markov chain Monte Carlo
• Error bounds for computing the expectation by Markov chain Monte Carlo
• Exponential inequalities for unbounded functions of geometrically ergodic Markov chains: applications to quantitative error bounds for regenerative Metropolis algorithms
• Error bounds of MCMC for functions with unbounded stationary variance
• Computation of expectations by Markov chain Monte Carlo methods

Cited in

(43)

• Perturbation theory for Markov chains via Wasserstein distance
• On a generalization of the preconditioned Crank-Nicolson metropolis algorithm
• Generalized parallel tempering on Bayesian inverse problems
• Adaptive Huber regression on Markov-dependent data
• On a Metropolis-Hastings importance sampling estimator
• Importance sampling correction versus standard averages of reversible MCMCs in terms of the asymptotic variance
• Quantitative spectral gap estimate and Wasserstein contraction of simple slice sampling
• Metropolis-Hastings reversiblizations of non-reversible Markov chains
• A weighted discrepancy bound of quasi-Monte Carlo importance sampling
• Error bounds of MCMC for functions with unbounded stationary variance
• Nonasymptotic bounds on the estimation error of MCMC algorithms
• Hit-and-run for numerical integration
• Dimension-Independent MCMC Sampling for Inverse Problems with Non-Gaussian Priors
• Some results on the complexity of numerical integration
• Error bounds for computing the expectation by Markov chain Monte Carlo
• scientific article; zbMATH DE number 1304829 (Why is no real title available?)
• Comparison of hit-and-run, slice sampler and random walk Metropolis
• Numerical integration using V-uniformly ergodic Markov chains
• Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions
• Log-concavity and strong log-concavity: a review
• Markov chain Monte Carlo estimation of quantiles
• Approximations of geometrically ergodic reversible Markov chains
• Hoeffding's inequality for general Markov chains and its applications to statistical learning
• Computation of expectations by Markov chain Monte Carlo methods
• On Stochastic Error and Computational Efficiency of the Markov Chain Monte Carlo Method
• Geometric Ergodicity for Hamiltonian Monte Carlo on Compact Manifolds
• Complexity results for MCMC derived from quantitative bounds
• Analysis of a Class of Multilevel Markov Chain Monte Carlo Algorithms Based on Independent Metropolis–Hastings
• Wasserstein contraction and spectral gap of slice sampling revisited
• Dimension‐independent Markov chain Monte Carlo on the sphere
• Rigorous confidence bounds for MCMC under a geometric drift condition
• Dimension-independent spectral gap of polar slice sampling
• Almost sure convergence rates of adaptive increasingly rare Markov chain Monte Carlo
• Optimal convergence rates of MCMC integration for functions with unbounded second moment
• Bayesian inversion for electrical impedance tomography by sparse interpolation
• Lower bounds on the rate of convergence for accept-reject-based Markov chains in Wasserstein and total variation distances
• Convergence speed and approximation accuracy of numerical MCMC
• Concentration inequalities for sums of Markov-dependent random matrices
• Optimal algorithms for numerical integration: recent results and open problems
• Convergence of hybrid slice sampling via spectral gap
• Reversibility of elliptical slice sampling revisited
• Mixing and concentration by Ricci curvature
• Explicit error bounds for lazy reversible Markov chain Monte Carlo

This page was built for publication: Explicit error bounds for Markov chain Monte Carlo

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2896206)