TL;DR
This paper introduces Sampling via Moment Sharing (SMS), a distributed MCMC algorithm that uses Expectation Propagation (EP) to keep parallel samplers in sync. By sharing simple moment statistics (like mean and covariance) during the sampling process, the method ensures that local nodes agree on the global posterior, outperforming traditional "embarrassingly parallel" methods that only combine results at the very end.
What Problem Does This Paper Address?
Bayesian inference is powerful but notoriously difficult to scale. Standard Markov chain Monte Carlo (MCMC) methods require a full pass over the dataset at every iteration—an impossible task for "big data" ($N \gg 1$).
To solve this, researchers often use "embarrassingly parallel" architectures: split the data across $m$ nodes, run MCMC independently on each, and then merge the results. However, this approach has a major flaw: if the data isn't partitioned perfectly or if the local distributions aren't Gaussian, the final combined posterior can be highly inaccurate. The samplers "drift" apart because they have no awareness of the data held by other nodes.
Methods
The authors propose SMS (Sampling via Moment Sharing). Instead of running samplers in total isolation, they use Expectation Propagation (EP) as a communication framework.
- Local Priors: Each node runs an MCMC sampler on its local data partition. However, instead of a standard global prior, it uses a "context-aware" local prior.
- Moment Sharing: Periodically, nodes share their local moment statistics (e.g., mean and covariance for Gaussian cases).
- EP Message Passing: These moments are used to update the local priors at every other node. This effectively "nudges" each local sampler toward the global consensus.
- Convergence: Because EP typically converges in just a few rounds, communication costs remain low. Once converged, the samples from any individual node can be treated as valid samples from the global posterior, eliminating the need for a complex final combination step.
The authors demonstrate this using both Multivariate Gaussian families (for logistic regression) and Spike-and-Slab distributions (for sparse regression).
Datasets
The paper evaluates the algorithm on two main fronts:
- Simulated Logistic Regression: A synthetic dataset with $N=4000$ points and $d=20$ dimensions, used to test convergence and accuracy against ground truth.
- Boston Housing Dataset: A real-world dataset ($N=455, d=13$) used to test the method's performance on sparse linear regression using a non-Gaussian "spike-and-slab" prior.
Key Insights and Ideas
- Context-Awareness is Key: By using EP to inform local nodes about the "rest of the data," the samplers are much less likely to get stuck in local modes that don't represent the global truth.
- Beyond Gaussianity: While many distributed methods assume the posterior is Gaussian to simplify merging, SMS can be extended to any exponential family (like the spike-and-slab prior), making it more flexible for complex models.
- Reduced Approximation Bias: Unlike standard EP, which approximates every single likelihood term, SMS approximates a product of many likelihood terms at each node. This actually reduces the overall approximation bias.
- Stability through Damping: The authors found that "damping" updates (only moving a fraction of the way toward the new moment) is essential to keep the distributed system stable, especially since MCMC introduces stochastic noise into the EP updates.
Key Results
- Higher Accuracy: In logistic regression tests, SMS consistently achieved lower Mean Squared Error (MSE) and KL-divergence compared to popular baselines like Consensus Monte Carlo (SCOT) and the Weierstrass sampler (WANG).
- Fast Convergence: The "moment sharing" allows the local means to snap toward the ground truth much faster than independent samplers.
- Scalability: The method showed a favorable accuracy-computation trade-off. While increasing the number of nodes ($m$) slightly increases approximation error (a known trait of EP), it significantly reduces the time per iteration.
- Robustness: SMS handled non-random data partitioning much better than "embarrassingly parallel" methods, which often fail when local data slices are biased.
Limitations and Future Work
- Stochasticity in EP: Standard EP theory assumes exact moments. In SMS, moments are estimated via MCMC, which adds noise. While damping helps, a more rigorous theoretical analysis of EP under these stochastic perturbations is still needed.
- Hyperparameter Tuning: The current version doesn't automatically tune hyperparameters; the authors suggest that future versions could use the shared moments to perform empirical Bayesian learning of these parameters.
- Decentralization: While the paper discusses a decentralized version (node-to-node broadcasting), most experiments were conducted with a master-worker architecture. Further testing on fully peer-to-peer networks would be valuable for massive-scale deployments.
Summary updated