Parallelizing MCMC with Random Partition Trees
The modern scale of data has brought new challenges to Bayesian inference. In particular, conventional MCMC algorithms are computationally very expensive for large data sets. A promising approach to solve this problem is embarrassingly parallel MCMC (EP-MCMC), which first partitions the data into multiple subsets and runs independent sampling algorithms on each subset. The subset posterior draws are then aggregated via some combining rules to obtain the final approximation. Existing EP-MCMC algorithms are limited by approximation accuracy and difficulty in resampling. In this article, we propose a new EP-MCMC algorithm PART that solves these problems. The new algorithm applies random partition trees to combine the subset posterior draws, which is distribution-free, easy to resample from and can adapt to multiple scales. We provide theoretical justification and extensive experiments illustrating empirical performance.
Acknowledge the author's rebuttal.I overall maintain my general sentiment about the paper.--In this paper the authors describe and evaluate a method to aggregate posterior samples from an MCMC algorithm run over partitions of a dataset, where the observations are conditionally independent given the model parameters being estimated.One of the primary limitations of existing work that the authors intend to address is that existing aggregation methods poorly handle distributions which are multimodal or have skew (i.e., those which are not Gaussian).Their method to do this is by generating histograms of the parameter space (where the histograms are shared by partitions/samplers), then counting samples within the blocks of these histograms and aggregating across partitions by simply summing observations.The authors then illustrate their method with several experiments - some toy problems, Bayesian logistic regression on a synthetic dataset, and some larger data sets - and illustrate that their method leads to consistently better estimates of the posterior.What I concerns me about this paper is that I feel that the complexity of their method should be justified with more demonstration that their posterior estimate is actually better in practice than with alternative methods, especially on large datasets, for which the posterior very possibly is near-normal (more on this below).What I like about it is that, at least as a first cut, it uses a method which is simple in theory (basically, histograms and counting) to aggregate posterior samples from disjoint partitions into a full posterior estimate.What I think can be improved is that the complexity of the method should be better justified, and the explanation of it should be cleaned up (because while it is simple in theory, it appears complicated in practice to the extent that it is not clear that it is worth the added complexity).More concretely, my primary suggestion for this paper to the authors is to devote more effort to describing the partition algorithms that they propose.I believe they could do this by discussing related work a bit less (focusing mainly on the PDE equation) and by moving the remaining proofs to the appendix (but still stating the consistency results).By doing this, the authors could make it easier for readers to implement and tune their own implementations of this algorithm.As it is, I wouldn't want to be the grad student tasked with implementing their algorithm.It would be worth seeing some discussion about when the assumption of skewness in a posterior with many observations (and moderate dimensionality) actually is a problem when aggregating posteriors.Particularly, the "Bayesian central limit theorem" indicates that the posterior approaches normality when there are many samples and moderate dimensionality: http://www.stat.cmu.edu/~larry/=stat705/Lecture14.pdf.This large-observation scenario is the exact scenario this paper is aimed to address.When each subset has many observations, the resulting first and seconds moments may actually capture the distribution quite well, so the complexity of this method may not be justified.In addition, I have several more comments: - It would be good to see more discussion about previous methods for creating partition trees and how the authors' methods relate to these. - More motivation should be given in the introduction to the motivating problems; the algorithm is jumped into without enough of a clear idea for the specific problem class. - The "parametric" method is not described in any detail, so I am confused by what it represents.Are these based on a parametric estimate of the distribution, where the parameter samples are aggregated with an average?My overall takeaway from the toy examples (which exhibit skewness and/or multiple modes) is that, with averaging techniques such as mean, the resulting aggregated posterior is a poor representation of the true posterior.However, I have questions about whether such comparisons are fair, since (at least in the case of a known bimodal distribution) averaging techniques are clearly a poor choice.Therefore it feels that the comparison is a bit unfair. - It might be nice to see some discussion about whether taking higher-order moments would suffice with unimodal examples. One of the columns in table 1, logistic regression, should show the likelihood of held-out observations under the posterior (e.g. averaged over posterior examples or based on the posterior mean), as optimal performance on holdout data is the most common performance metric in fitting any logistic regression.While I don't expect the proposed method to perform worse than "average", if it doesn't then this method's complexity may not be justified for such applications. - I'd like to see more discussion of the final examples the "Real datasets" section, as the only real discussion of it is contained in the tiny plots.My takeaway from these is that the proposed method is able to find the best approximation to the posterior (as measured by KL divergence) while performing well - as well as the "average" method (while the average method doesn't approximate the posterior well) - on a test set. - The authors should discuss how they selected delta_p and delta_a; was this done by fitting the model over a grid of values?Is there a general rule of thumb for this? How poorly does their algorithm perform for poorly selected values?Tuning these would add a significant barrier in adoption of this method.The description of the partitioning algorithms could be cleaned up.Further, I had no idea what sentences like "Our PART algorithm consists of space partitioning followed by density aggregation" meant on first reading them, because the terms "space partitioning" and "density aggregation" didn't yet have meeting for me (I realize that there are subsections devoted to this later in section 2).A simple cartoon diagram would probably help significantly. - Feel free to drop sentences like "such partitions are multi scale and related to wavelets [8]" since they are useless to people who don't already know the relation to wavelets and already known by people who do. - The author should put much more effort into making Algorithms 1 and 2 more clear.While I am usually pedantic about careful notation, I think pseudocode (and, as noted above, illustrations) with less emphasis on precise notation might improve the discussion here.A highly-marked up version (with full notation) could go into the appendix.