Estimating Convergence of Markov chains with L-Lag Couplings

Abstract

Markov chain Monte Carlo (MCMC) methods generate samples that are asymptotically distributed from a target distribution of interest as the number of iterations goes to infinity. Various theoretical results provide upper bounds on the distance between the target and marginal distribution after a fixed number of iterations. These upper bounds are on a case by case basis and typically involve intractable quantities, which limits their use for practitioners. We introduce L-lag couplings to generate computable, non-asymptotic upper bound estimates for the total variation or the Wasserstein distance of general Markov chains. We apply L-lag couplings to the tasks of (i) determining MCMC burn-in, (ii) comparing different MCMC algorithms with the same target, and (iii) comparing exact and approximate MCMC. Lastly, we (iv) assess the bias of sequential Monte Carlo and self-normalized importance samplers.

References in corpus (11)

• General state space Markov chains and MCMC algorithms
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Measuring Sample Quality with Stein's Method
• Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• A Kernel Test of Goodness of Fit
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• Unbiased Markov chain Monte Carlo with couplings
• Bayes Shrinkage at GWAS scale: Convergence and Approximation Theory of a Scalable MCMC Algorithm for the Horseshoe Prior
• Unbiased Smoothing using Particle Independent Metropolis-Hastings
• On the coupling time of the heat-bath process for the Fortuin-Kasteleyn random-cluster model

Cited by in corpus (3)

• The shifted ODE method for underdamped Langevin MCMC
• Couplings for Multinomial Hamiltonian Monte Carlo
• A fast asynchronous MCMC sampler for sparse Bayesian inference