title: A general construction for parallelizing Metropolis-Hastings algorithms.
abstract: Markov chain Monte Carlo methods (MCMC) are essential tools for solving many modern-day statistical and computational problems; however, a major limitation is the inherently sequential nature of these algorithms. In this paper, we propose a natural generalization of the Metropolis-Hastings algorithm that allows for parallelizing a single chain using existing MCMC methods. We do so by proposing multiple points in parallel, then constructing and sampling from a finite-state Markov chain on the proposed points such that the overall procedure has the correct target density as its stationary distribution. Our approach is generally applicable and straightforward to implement. We demonstrate how this construction may be used to greatly increase the computational speed and statistical efficiency of a variety of existing MCMC methods, including Metropolis-Adjusted Langevin Algorithms and Adaptive MCMC. Furthermore, we show how it allows for a principled way of using every integration step within Hamiltonian Monte Carlo methods; our approach increases robustness to the choice of algorithmic parameters and results in increased accuracy of Monte Carlo estimates with little extra computational cost.
authors.affiliation: Department of Mathematics, Imperial College London, London SW7 2AZ, United Kingdom b.calderhead@imperial.ac.uk.
authors.forename: Ben
authors.initials: B
authors.lastname: Calderhead
keywords: Bayesian inference; Hamiltonian dynamics; Markov chain Monte Carlo; parallel computation