Parallelizing MCMC Across the Sequence Length: T samples in O(log2 T) time
SCOTT LINDERMAN – STANFORD UNIVERSITY
ABSTRACT
Markov chain Monte Carlo (MCMC) algorithms are foundational methods for Bayesian statistics. However, most MCMC algorithms are inherently sequential, and their time complexity scales linearly with the number of samples generated. Previous work on adapting MCMC to modern hardware has therefore focused on running many independent chains in parallel. Here, we take an alternative approach: we propose algorithms to evaluate MCMC samplers in parallel across the chain length. To do this, we build on recent methods for parallel evaluation of nonlinear recursions that formulate the state sequence as a solution to a fixed-point problem, which can be obtained via a parallel form of Newton’s method. We show how this approach can be used to parallelize Gibbs, Metropolis-adjusted Langevin, and Hamiltonian Monte Carlo sampling across the sequence length. Moreover, we prove theoretical results that link the convergence rate of the fixed-point algorithm to the stability of the recursion, yielding sublinear time complexity for certain problems. Finally, to lower memory costs and reduce runtime in practice, we develop quasi-Newton methods that are generally applicable for parallel evaluation of nonlinear recursions. Across several examples, we demonstrate the simulation of up to hundreds of thousands of MCMC samples with only tens of parallel Newton iterations. We find that the proposed parallel algorithms accelerate MCMC, in some cases by more than an order of magnitude compared to sequential evaluation.