End-to-End Total Variation Guarantees for Sequence-Parallel Markov Chain Monte Carlo


NAWAF BOU-RABEE – RUTGERS UNIVERSITY 

ABSTRACT

Graphics processing units (GPUs) and tensor processing units (TPUs) support parallel computation, yet standard Markov chain Monte Carlo (MCMC) is inherently sequential. In his Fall 2025 talk in this seminar, Scott Linderman presented an innovative approach to parallelizing MCMC: solve jointly for the entire sequence of chain states through a system of nonlinear equations. Building on this work, we ask: under what conditions can MCMC be efficiently parallelized along the sequence length?

We answer this question for the unadjusted Langevin algorithm and unadjusted Hamiltonian Monte Carlo applied to strongly log-concave target distributions, under suitable regularity and tuning assumptions. Our convergence bounds are quenched: they control the solver error over the entire sequence for every fixed realization of the sampler’s randomness. They establish global linear convergence for Jacobi iteration and local quadratic convergence for Newton iteration. A hybrid schedule uses Jacobi iteration to enter the region of quadratic convergence, then switches to Newton.

We obtain end-to-end upper bounds on the total variation distance to the target distribution by combining these quenched estimates with mixing and asymptotic-bias bounds. These guarantees retain the statistical convergence rates of the sequential implementations, with an explicitly controlled solver error. For a sequence of N chain states, with the initial-error bound and other parameters fixed and assuming sufficient parallel resources, the hybrid attains the required accuracy in O(log N) parallel time, compared with O(N) time for sequential evaluation.

 

RELATED PAPERS