Convergence Speed and Approximation Accuracy of Numerical MCMC

Abstract

When implementing Markov Chain Monte Carlo (MCMC) algorithms, perturbation caused by numerical errors is sometimes inevitable. This paper studies how perturbation of MCMC affects the convergence speed and Monte Carlo estimation accuracy. Our results show that when the original Markov chain converges to stationarity fast enough and the perturbed transition kernel is a good approximation to the original transition kernel, the corresponding perturbed sampler has similar convergence speed and high approximation accuracy as well. We discuss two different analysis frameworks: ergodicity and spectral gap, both are widely used in the literature. Our results can be easily extended to obtain non-asymptotic error bounds for MCMC estimators. We also demonstrate how to apply our convergence and approximation results to the analysis of specific sampling algorithms, including Random walk Metropolis and Metropolis adjusted Langevin algorithm with perturbed target densities, and parallel tempering Monte Carlo with perturbed densities. Finally we present some simple numerical examples to verify our theoretical claims.

arXiv comment26 pages, 5 figures

References in corpus (14)

• Parallel Tempering: Theory, Applications, and New Perspectives
• Spectral gaps in Wasserstein distances and the 2D stochastic Navier--Stokes equations
• Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions
• Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Curvature, concentration and error estimates for Markov chain Monte Carlo
• Transport map accelerated Markov chain Monte Carlo
• Explicit error bounds for Markov chain Monte Carlo
• Convergence properties of pseudo-marginal Markov chain Monte Carlo algorithms
• Approximating Markov chains and V-geometric ergodicity via weak perturbation theory
• Perturbation Bounds for Monte Carlo within Metropolis via Restricted Approximations
• Approximations of Geometrically Ergodic Reversible Markov Chains
• Accelerating Parallel Tempering: Quantile Tempering Algorithm (QuanTA)
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics