SwISS: A Scalable Markov chain Monte Carlo Divide-and-Conquer Strategy

Callum Vyner, Christopher Nemeth, Chris Sherlock

TL;DR

This paper introduces SWISS, a novel divide-and-conquer strategy for Markov Chain Monte Carlo (MCMC) that scales Bayesian inference to massive datasets. SWISS efficiently merges results from parallel MCMC runs on data subsets by applying affine transformations to sub-posterior samples, offering accurate approximations even for complex, non-Gaussian posteriors.

What Problem Does This Paper Address?

Bayesian inference, a powerful statistical framework, often relies on MCMC methods to approximate complex probability distributions (posteriors). However, MCMC's computational cost typically scales linearly with the size of the dataset, making it prohibitively slow and memory-intensive for "big data" scenarios. Divide-and-conquer strategies aim to overcome this by partitioning the data across multiple computing cores, running MCMC in parallel on each subset to obtain "sub-posterior" samples. The main challenge then becomes how to effectively combine these sub-posterior samples to accurately represent the full posterior distribution. Existing methods like consensus MCMC, which average sub-posterior samples, can struggle with non-Gaussian posteriors, losing important features like skewness or multi-modality.

Methods

The core innovation of SWISS lies in its approach to merging sub-posterior samples. Instead of simply averaging, SWISS employs a two-step process:

  1. Inflation: Each sub-posterior is "inflated" by raising its density to a power. This stochastic approximation helps preserve the shape and scale of the full posterior, mitigating issues arising from imbalanced data partitions.
  2. Affine Transformation: Affine transformations (scaling and shifting) are then applied to the inflated sub-posterior samples. These transformations are specifically designed to correct for discrepancies in the variance and location of the sub-posteriors, aiming to produce samples that closely resemble those from the true full posterior.

The paper provides theoretical justification for the choice of these transformations, proving their asymptotic optimality in a natural sense and demonstrating that SWISS is exact for Gaussian posteriors.

Datasets

The paper evaluates SWISS on:

  • Synthetic datasets:
    • A rare Bernoulli density dataset designed to create skewed posteriors.
  • A warped bivariate Gaussian density dataset.
  • A mixture of bivariate Gaussian densities dataset.
  • A synthetic dataset for a linear mixed effects model with 200,000 observations and 10 parameters.
  • A synthetic dataset for a logistic regression model with 100,000 observations and 5 parameters.
  • Real-world dataset:
    • The Hepmass dataset from high-energy particle physics, with 10.5 million responses and 28 parameters.

The authors also mention using the parallelMCMCcombine R package for their experiments.

Key Insights and Ideas

  • Beyond Averaging: The key insight is that simply averaging sub-posterior samples (like in consensus MCMC) can smooth over important posterior features, especially for non-Gaussian distributions. SWISS's affine transformation approach offers a more sophisticated way to "reconstruct" the full posterior.
  • Inflation as a Preprocessing Step: Inflating the sub-posteriors is a crucial step that helps to bring them closer in scale and shape to the full posterior before the affine transformation is applied. This is particularly important when data partitions are imbalanced.
  • Affine Transformations for Correction: The use of affine transformations is not just a simple shift; it's a principled way to adjust the location and scale of sub-posterior samples to better match the target posterior, with theoretical backing for their optimality.
  • Scalability and Accuracy: SWISS demonstrates that it's possible to achieve both computational scalability (through parallelization) and high accuracy, even for complex posteriors, which is a significant advancement for Bayesian inference on large datasets.

Key Results

  • Accuracy on Complex Posteriors: SWISS consistently outperforms consensus MCMC and other methods (like Gaussian Barycenter and Average Re-centring) on non-Gaussian posterior geometries (rare Bernoulli, warped Gaussian, mixture of Gaussians), producing more reliable approximations.
  • Scalability with Dimension: SWISS and consensus MCMC remain robust and accurate as the dimensionality of the parameter space increases, outperforming methods like Semi-parametric KDE and Gaussian Barycenter in terms of Integrated Absolute Distance (IAD).
  • Computational Efficiency: SWISS is computationally efficient, comparable to the consensus algorithm, and significantly faster than methods like Semi-parametric KDE for merging posterior samples.
  • Robustness: SWISS performs well across various metrics (Mahalanobis distance, Skew, IAD) on both simulated and real-world datasets, including the Hepmass dataset.
  • Exactness for Gaussian: SWISS is proven to be exact when merging Gaussian sub-posteriors.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that while SWISS is generally robust, the Average Re-centring (AR) algorithm performs poorly when sub-posterior variances differ substantially, as it doesn't correct for this.
  • The Semi-parametric KDE approach is noted as being computationally more expensive.
  • Future Work:
    • The paper's conclusion suggests that SWISS is a promising method for scalable Bayesian inference. While not explicitly stated as future work, the success on complex posteriors and high dimensions implies potential for application to even larger and more complex real-world problems. The availability of code via a GitHub link also facilitates further research and application.

Summary updated

Abstract

Divide-and-conquer strategies for Monte Carlo algorithms are an increasingly popular approach to making Bayesian inference scalable to large data sets. In its simplest form, the data are partitioned across multiple computing cores and a separate Markov chain Monte Carlo algorithm on each core targets the associated partial posterior distribution, which we refer to as a sub-posterior, that is the posterior given only the data from the segment of the partition associated with that core. Divide-and-conquer techniques reduce computational, memory and disk bottle-necks, but make it difficult to recombine the sub-posterior samples. We propose SwISS: Sub-posteriors with Inflation, Scaling and Shifting; a new approach for recombining the sub-posterior samples which is simple to apply, scales to high-dimensional parameter spaces and accurately approximates the original posterior distribution through affine transformations of the sub-posterior samples. We prove that our transformation is asymptotically optimal across a natural set of affine transformations and illustrate the efficacy of SwISS against competing algorithms on synthetic and real-world data sets.
BibTeX
@inproceedings{vyner2022swiss,
  author = {Callum Vyner and Christopher Nemeth and Chris Sherlock},
  title = {{SwISS: A Scalable Markov chain Monte Carlo Divide-and-Conquer Strategy}},
  booktitle = {Stat},
  year = {2022},
  doi = {10.1002/sta4.523},
}
Figure