Asymptotically Exact, Embarrassingly Parallel MCMC

Willie Neiswanger Carnegie Mellon University, Eric Xing Carnegie Mellon University, Chong Wang
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:519-528, 2014.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-university14o, title = {Asymptotically Exact, Embarrassingly Parallel {MCMC}}, author = {University, Willie Neiswanger Carnegie Mellon and University, Eric Xing Carnegie Mellon and Wang, Chong}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {519--528}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/university14o/university14o.pdf}, url = {https://proceedings.mlr.press/r12/university14o.html}, abstract = {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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Asymptotically Exact, Embarrassingly Parallel MCMC %A Willie Neiswanger Carnegie Mellon University %A Eric Xing Carnegie Mellon University %A Chong Wang %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-university14o %I PMLR %P 519--528 %U https://proceedings.mlr.press/r12/university14o.html %V R12 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
University, W.N.C.M., University, E.X.C.M. & Wang, C.. (2014). Asymptotically Exact, Embarrassingly Parallel MCMC. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:519-528 Available from https://proceedings.mlr.press/r12/university14o.html. Reissued by PMLR on 04 October 2026.

Related Material