Asymptotically Exact, Embarrassingly Parallel MCMC

By Willie Neiswanger, Chong Wang, Eric P. Xing. 2013

341 citations recorded by the source corpus.

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

The Non-IID Data Quagmire of Decentralized Machine Learning (2019, methodology): “…algorithms to reduce the dependency on intensive parameter updates to enable more efﬁcient parallel training (e.g., (Jaggi et al., 2014; Zhang et al., 2013; Zinkevich et al., 2010; Takác et al., 2013; Neiswanger et al., 2014; Shamir et al., 2014; Zhang & Lin, 2015; Shalev-Shwartz & Zhang, 2013)).”
Toward Understanding the Impact of Staleness in Distributed Machine Learning (2018, methodology): “We focus on algorithms that are commonly used in large-scale optimization (Goyal et al., 2017; Chen et al., 2016; Dean et al., 2012), instead of methods speciﬁcally designed to minimize synchronization (Neiswanger et al., 2013; Scott et al., 2016; Jordan et al., 2013).”
Stochastic Gradient Markov Chain Monte Carlo (2019, background): “Alternative merging procedures, that aim to be more robust to non-Gaussianity, have also been proposed (Neiswanger et al., 2013; Rabinovich et al., 2015; Srivastava et al., 2018; Nemeth et al., 2018), but it is hard to quantify the level of approximation accuracy such merging procedures have in gene”
Communication-efficient distributed statistical learning (2016, methodology): “Another related work to DANE and ours is the iterated Hessian sketch (IHS) algorithm Pilanci and Wainwright [2014] that is specifically designed for constrained least-squares optimization. Although DANE applied to quadratic problems can be viewed as a special case of IHS by choosing the sketching ma”
Efficient task replication for fast response times in parallel computation (2014, background): “In addition, embarrassingly parallel computation is a feature that algorithm designers seek due to its ease of implementation, in optimization [3] and MCMC simulation [14].”
Expectation Propagation as a Way of Life (2020, background): “…proposed to combine inferences from partitioned data (see Ahn, Korattikara, and Welling, 2012, Gershman, Hoffman, and Blei, 2012, Korattikara, Chen, and Welling, 2013, Hoffman et al., 2013, Wang and Blei, 2013, Scott et al., 2013, Wang and Dunson, 2013, Neiswanger et al., 2013, and Wang, 2014).”
Stochastic variational inference for hidden Markov models (2014, methodology): “There is considerable interest in leveraging these methods for Bayesian inference since traditional algorithms such as Markov chain Monte Carlo (MCMC) scale poorly to large datasets, though subset-based MCMC methods have been recently proposed as well [5, 6, 7, 8].”
Using Straggler Replication to Reduce Latency in Large-scale Parallel Computing (2015, methodology): “Several algorithms used in optimization and machine learning, for example the Alter-nating Direction Method of Multipliers (ADMM) [4], and Markov Chain Monte-Carlo (MCMC) [14], fall into this class and can be parallelized easily.”
Communication-Efficient Distributed Statistical Inference (2016, background): “…Jordan 2015; Zhang and Lin 2015a; Lee et al. 2015a), and a Bayesian setting (Suchard et al. 2010; Cleveland and Hafen 2014; Maclau-rin and Adams 2014; Wang and Dunson 2015; Neiswanger, Wang, and Xing 2015; Rabinovich, Angelino, and Jordan 2016; Scott et al.2016; Terenin, Simpson, and Draper 2016).”
Bayesian computation: a summary of the current state, and samples backwards and forwards (2015, methodology): “Point 2 is less of a clearcut drawback: while the Tm terms corresponding to a product of m sums of T terms sounds self-defeating, Neiswanger et al. (2013) use a clever device to avoid the combinatorial explosion, namely operating on one component at a time.”
Expectation Propagation as a Way of Life: A Framework for Bayesian Inference on Partitioned Data (2014, background): “The top-down view deals with fitting statistical models to large data sets, for which many distributed (divide-and-conquer) algorithms have been proposed over the past few years (Ahn et al., 2012; Balan et al., 2014; Hoffman et al., 2013; Scott et al., 2016; Wang and Dunson, 2013; Neiswanger et al.,”
ProBO: a Framework for Using Probabilistic Programming in Bayesian Optimization (2019, methodology): “We can integrate these with combination algorithms from the embarassingly parallel MCMC literature (Neiswanger et al., 2014; Wang et al., 2015) to develop an algorithm that generates samples from the posterior predictive of the ensemble model M e and uses these in a black box acquisition function.”
Distributed Estimation, Information Loss and Exponential Families (2014, background): “There are also many works on distributed clustering (e.g., Merugu and Ghosh, 2003, Forero et al., 2011, Balcan et al., 2013) and distributed MCMC (e.g., Scott et al., 2013, Wang and Dunson, 2013, Neiswanger et al., 2013).”
Bayesian forecasting in economics and finance: A modern review (2022, methodology): “, 2023b) can be summarized as follows: the use of more geometric information about the target posterior, most notably the use of Hamiltonian updates (Neal, 2011b; Hoffman and Gelman, 2014); the use of better MH candidate, or proposal distributions, including those that ‘adapt’ to previous draws (Not”
Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms (2020, methodology): “Note that posterior inference via multiplicative averaging has been successfully used to scale Monte Carlo methods to large datasets, where the approach is embarrassingly parallel (Neiswanger et al., 2013; Scott et al., 2016).”