Distributed Bayesian Posterior Sampling via Moment Sharing
We propose a distributed Markov chain Monte Carlo (MCMC) inference algorithm for large scale Bayesian posterior simulation. We assume that the dataset is partitioned and stored across nodes of a cluster. Our procedure involves an independent MCMC posterior sampler at each node based on its local partition of the data. Moment statistics of the local posteriors are collected from each sampler and propagated across the cluster using expectation propagation message passing with low communication costs. The moment sharing scheme improves posterior estimation quality by enforcing agreement among the samplers. We demonstrate the speed and inference quality of our method with empirical studies on Bayesian logistic regression and sparse linear regression with a spike-and-slab prior.
Summary:  The authors propose a new Bayesian inference algorithm that operates on subsets of data in a distributed environment.  This work is in the spirit of an active area of recent work on parallel MCMC for Bayesian inference using subsets of data.  The authors focus on comparisons to parallel methods; a complementary line of work uses data subsets as mini-batches. (I think these are not discussed, though they could be.) The new method, eventually called Distributed Context-Aware Sampling (DCAS), combines MCMC and expectation propagation.  All these methods must eventually share information between parallel cores, each of which "owns" a data subset.  The strategy here is to share some information between nodes, encoded in a "context prior."  In the experimental evaluation, the proposed method looks better than some other recent methods, but the experiments are very limited.      Quality:  The proposed method is interesting and well-motivated.  Theoretical results would have been nice, but not necessarily required -- in which case I would expect thorough and impressive experiments.  The algorithm relies on Normal models, fitted at each node, to share information between nodes.  A major question I have is, in the case where everything is actually Gaussian, does the algorithm converge to the exact target?      The writing is mostly good, except in the Intro, which appears to have been slapped together -- after a short but clear Abstract, the Intro begins immediately with a series of grammatically incoherent sentences containing embarrassing errors.  The citations, especially in the first paragraph, are dropped in and lack context (ironically).  Please explain the differences between these citations, and point out which concern Bayesian posterior sampling and which do not.      The Experiments are designed thoughtfully, and effort has been made to present a fair comparison of different sampling procedures, where it isn't obvious how to compare them directly.  The synthetic problem is nice (Bayesian logistic regression, 4,000 and 10,000 data points, 20 dimensions), but the evaluation could have benefitted from studying several problems along several axes -- synthetic and real data, larger datasets (which are free for synthetic models).  I would have liked to have seen standard MCMC convergence tests.         Clarity:  Since you are introducing the notion of the context prior, please italicize it in the Abstract.  It would also be useful to give some intuition there for what it means and why it is useful. Also in your Abstract, you could elaborate on your results. "We demonstrate the advantages of our algorithm" -- With respect to what?  Measured how?  Using how many cores?  What would be a summary of your quantitative results?  Your Abstract and Intro should introduce the name of your algorithm (DCAS), especially since it is not in your title.      Please define acronyms such as KDE and RKHS in the Intro.      The context prior is a nice idea and I appreciated its motivation with respect to the SVB paper.  In lines 068-069 where you say, "We believe ... it appears intuitive to suggest ... " -- Can you make stronger statements?  Or just explain that you are taking a reasonable Bayesian approach.        There is a lot of notation -- p's and q's with various superscripts and subscripts.  I wonder if it can be made clearer or more intuitive.  Perhaps there could be a little table, even as an appendix, summarizing all notation.  The superscripts (I think they are chi and iota) are not terribly intuitive -- or is there an explanation?  chi because it looks like an "x" for conteXt?  It took me a while to internalize that the subscript notation refers to a data subset and is also used to suppress this explicit dependence in the usual probabilistic notation -- e.g., p_i(theta) replaces p(theta | D_i).  I found this confusing on my initial reading because this led me to interpret the notation for subset posteriors as priors.        Footnote 2 appears at the end of a mathematical expression and looks like an exponent.      Thank you for the sentence around line 087, "To recap ..."      Please define "proj" in Eq. (7).      Section 2.4 could use some high-level sentences at the beginning, explaining the layout of the section.        In 2.4.1, line 132, I think you are defining p_i(theta) here, so please make this clear, as I was searching for it in the previous notation.  Also, calling this the "target distribution" may be confusing, since it isn't the true target.      Question about Algorithm 1:  should the 1/(T_i - 1) terms be 1/T_i?      Line 161, "As the underlying message passing progresses" -- this is confusing, as you haven't yet described the message passing component of your algorithm, which comes in the next section, 2.4.2.  This would be addressed by giving a high-level overview at the beginning of Section 2.4.        Some of the text in Figure 1 is way too small.      The descriptions of the synchronous, asynchronous and decentralized algorithms are very concise but could be expanded somewhat for clarity.  What explicit parallel architecture do you have in mind?  Who is receiving the messages?  Is there a master node?  It seemed that the implementation uses shared memory, available to all nodes, to share/update global information.  The description of the asynchronous scheme should make explicit how the latest historical copy of q_i^iota is used, using the notation introduced in line 185.      2.4.4, line 226 -- Where did tilde{f} come from?        Line 230, "Several possible remedies have been proposed" -- by whom?  You?      Experiments section -- please give explicit details about the cluster architecture -- you mention 8 nodes, is it 1 core per node?  It sounds like there is shared memory?  I assume then there is no need for MPI?  There are 8 nodes, but you study m = 8, 16, 24, 36, 48 partitions -- this suggests to me you have multiple cores per node.  The compute architecture needs to be clarified.      Make explicit that you do not evaluate the decentralized scheme.        It would be useful to explicitly describe the combining rules you use for SCOT, NEIS and WANG; this could go in Supplemental.  For WANG, you use their sequential sampler -- the corresponding paper proposes at least 3 sampling procedures, why did you choose this one?  What might you have expected to be different if you had used one of their other procedures?        Line 261, "Upon convergence" -- according to what criteria?      Please label the axes of Figures 3 and 5 (# samples).       Please make explicit how the ground truth samples are used, and precisely what KL-divergence is measuring (presumably between distributions fit to the ground truth samples and to the various MCMC samples.      If you feel you would benefit from more room, I would suggest moving (parts of) section 3.4 to Supplemental.       Originality:  To the best of my knowledge, the proposed method is novel.  This work has the same motivations as recent parallel, approximate MCMC schemes that operate on subsets (partitions) of data.  These other schemes either sample in an embarrassingly parallel manner, and then need to "fix up" the samples by combining them somehow, or have each parallel core sample from an approximate target (Weierstrass sampling). In all these methods, information must eventually be shared between nodes.  This work uses the novel idea of the context prior, which is continuously updated during execution.       Significance:  There is much recent interest in the area of scaling MCMC sampling by subsampling (partitioning) the data, and having separate parallel cores process each subsample.  Therefore the proposed algorithm is of interest and timely.  However, the paper presents no theoretical analysis or guarantees and therefore relies on empirical studies.  The empirical evaluation presented here compares with several other recent techniques, but is limited.  I really wanted to see a more enlightened discussion of this method compared to other (recent) work -- several other of these methods rely on Normal models, and a discussion/comparison would be very useful.       Other:  At least 4 of your references cite arxiv versions when (sometimes recent) journal or conference versions are now available [2, 4, 8, 15].      Line 067, "prompts our core" (delete "us to")       Line 081, commas around "e.g."      Typo around line 090, ", And ..."      Line 095 "two" not "2"      Line 103, "progress"      Line 104, "rules (4) naturally reduce"      Line 110, "first" not "firstly"      Line 215, explicitly define your notation for the zero matrix      Line 226, "not much of"      Line 266, "draw" not "draws"