# Asymptotically Exact, Embarrassingly Parallel MCMC

arXiv: https://arxiv.org/abs/1311.4780 · HTML: https://mlsanity.com/paper/1311.4780/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2013.

## Built on by (most cited first, 30 of 30)

- [A Primer on Bayesian Neural Networks: Review and Debates](https://mlsanity.com/paper/2309.16314/) (2023)
- [QLSD: Quantised Langevin stochastic dynamics for Bayesian federated learning](https://mlsanity.com/paper/2106.00797/) (2021)
- [A Survey of Monte Carlo Methods for Parameter Estimation](https://mlsanity.com/paper/2107.11820/) (2021)
- [On Convergence of Federated Averaging Langevin Dynamics](https://mlsanity.com/paper/2112.05120/) (2021)
- [DG-LMC: A Turn-key and Scalable Synchronous Distributed MCMC Algorithm via Langevin Monte Carlo within Gibbs](https://mlsanity.com/paper/2106.06300/) (2021)
- [Parallel MCMC Without Embarrassing Failures](https://mlsanity.com/paper/2202.11154/) (2022)
- [Calibrated One Round Federated Learning with Bayesian Inference in the Predictive Space](https://mlsanity.com/paper/2312.09817/) (2023)
- [Parallelized Midpoint Randomization for Langevin Monte Carlo](https://mlsanity.com/paper/2402.14434/) (2024)
- [SwISS: A Scalable Markov chain Monte Carlo Divide-and-Conquer Strategy](https://mlsanity.com/paper/2208.04080/) (2022)
- [Capture Global Feature Statistics for One-Shot Federated Learning](https://mlsanity.com/paper/2503.06962/) (2025)
- [Enhancing Transfer Learning with Flexible Nonparametric Posterior Sampling](https://mlsanity.com/paper/2403.07282/) (2024)
- [Federated Variational Inference Methods for Structured Latent Variable Models](https://mlsanity.com/paper/2302.03314/) (2023)
- [Machine Learning and the Future of Bayesian Computation](https://mlsanity.com/paper/2304.11251/) (2023)
- [MCMC-driven importance samplers](https://mlsanity.com/paper/2105.02579/) (2021)
- [Divide-and-Conquer Fusion](https://mlsanity.com/paper/2110.07265/) (2021)
- [Embarrassingly Parallel GFlowNets](https://mlsanity.com/paper/2406.03288/) (2024)
- [Federated Averaging Langevin Dynamics: Toward a unified theory and new algorithms](https://mlsanity.com/paper/2211.00100/) (2022)
- [One-Shot Federated Learning with Bayesian Pseudocoresets](https://mlsanity.com/paper/2406.02177/) (2024)
- [Data value estimation on private gradients](https://mlsanity.com/paper/2412.17008/) (2024)
- [Adaptive posterior distributions for uncertainty analysis of covariance matrices in Bayesian inversion problems for multioutput signals](https://mlsanity.com/paper/2501.01148/) (2025)
- [Federated Learning via Meta-Variational Dropout](https://mlsanity.com/paper/2510.20225/) (2025)
- [Vertical Consensus Inference for High-Dimensional Random Partition](https://mlsanity.com/paper/2603.27864/) (2026)
- [Distributed data analytics](https://mlsanity.com/paper/2203.14088/) (2022)
- [Robust One Round Federated Learning with Predictive Space Bayesian Inference](https://mlsanity.com/paper/2206.09526/) (2022)
- [Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers](https://mlsanity.com/paper/2401.15838/) (2024)
- [Diffusion Generative Modelling for Divide-and-Conquer MCMC](https://mlsanity.com/paper/2406.11664/) (2024)
- [Measuring the right thing: justifying metrics in AI impact assessments](https://mlsanity.com/paper/2504.05007/) (2025)
- [Differential Privacy of Gaussian Process Posterior Sampling](https://mlsanity.com/paper/2606.17995/) (2026)
- [Divide-and-Conquer: Towards Generalizable Amortized Bayesian Inference for the Drift Diffusion Model](https://mlsanity.com/paper/2608.03566/) (2026)
- [Every pooling rule has its world: matching probability combination rules to situations and stakes](https://mlsanity.com/paper/2608.11275/) (2026)

## Abstract (arXiv)

Communication costs, resulting from synchronization requirements during learning, can greatly slow down many parallel machine learning algorithms. In this paper, we present a parallel Markov chain Monte Carlo (MCMC) algorithm in which subsets of data are processed independently, with very little communication. First, we arbitrarily partition data onto multiple machines. Then, on each machine, any classical MCMC method (e.g., Gibbs sampling) may be used to draw samples from a posterior distribution given the data subset. Finally, the samples from each machine are combined to form samples from the full posterior. This embarrassingly parallel algorithm allows each machine to act independently on a subset of the data (without communication) until the final combination stage. We prove that our algorithm generates asymptotically exact samples and empirically demonstrate its ability to parallelize burn-in and sampling in several models.