Anthony Lee

How many steps are needed for random walk Metropolis? Explicit convergence bounds for Metropolis Markov chains.

One of the simplest and enduringly popular general-purpose Monte Carlo Markov chains evolving on R^d is the random walk Metropolis (RWM) Markov chain. Despite its relative simplicity, explicit convergence bounds that scale suitably with dimension have proved elusive for decades. In recent years, progress has been made to show that for distributions with strongly convex and gradient-Lipschitz potentials there exists a specific proposal variance giving an explicit bound on the L^2-mixing time. We refine these results and obtain explicit spectral gap and L^2-mixing time bounds for RWM with arbitrary proposal variances in any dimension, demonstrating the robustness of the algorithm. We obtain the correct scaling with dimension of the spectral gap for sufficiently regular target distributions, and the mixing time bounds are of reasonable (not astronomical) order. Our positive results are quite generally applicable in principle. Essentially the same analysis can be performed for the preconditioned Crank--Nicolson Markov chain, obtaining dimension-independent bounds under suitable assumptions.

This is joint work with C. Andrieu (Bristol), S. Power (Bristol) and A. Wang (Warwick).