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 synchro- nization 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 pro- cessed independently, with very little com- munication. 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 ma- chine are combined to form samples from the full posterior. This embarrassingly parallel algorithm allows each machine to act inde- pendently 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 synchro- nization 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 pro- cessed independently, with very little com- munication. 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 ma- chine are combined to form samples from the full posterior. This embarrassingly parallel algorithm allows each machine to act inde- pendently 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 synchro- nization 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 pro- cessed independently, with very little com- munication. 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 ma- chine are combined to form samples from the full posterior. This embarrassingly parallel algorithm allows each machine to act inde- pendently 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