Accelerating MCMC via Parallel Predictive Prefetching

2014/03/28 by Elaine Angelino, Angelino, Elaine, Eddie Kohler +7 · 1 citation
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Computation (stat.CO) #FOS: Computer and information sciences #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Statistical Methods and Inference #stat.CO #stat.ML

paper · pdf · doi:10.48550/arxiv.1403.7265

arxiv created 2014/03/28 · openalex publication_date 2014/03/28 · arxiv updated 2014/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a general framework for accelerating a large class of widely used Markov chain Monte Carlo (MCMC) algorithms. Our approach exploits fast, iterative approximations to the target density to speculatively evaluate many potential future steps of the chain in parallel. The approach can accelerate computation of the target distribution of a Bayesian inference problem, without compromising exactness, by exploiting subsets of data. It takes advantage of whatever parallel resources are available, but produces results exactly equivalent to standard serial execution. In the initial burn-in phase of chain evaluation, it achieves speedup over serial evaluation that is close to linear in the number of available cores.

Citations

• Exact sampling with coupled Markov chains and applications to statistical mechanics
• Equation of State Calculations by Fast Computing Machines
• Inference from Iterative Simulation Using Multiple Sequences
• How to view an MCMC simulation as a permutation, with applications to parallel simulation and improved importance sampling

Cited by

• Parallelizing MCMC Across the Sequence Length

Related

• Accelerating MCMC Algorithms
• Parallelizing MCMC Across the Sequence Length
• Scalable Inference for Markov Processes with Intractable Likelihoods
• Asymptotically Exact, Embarrassingly Parallel MCMC
• Running Markov Chain Monte Carlo on Modern Hardware and Software