# Asynchronous and Distributed Data Augmentation for Massive Data Settings

arXiv: https://arxiv.org/abs/2109.08969 · HTML: https://mlsanity.com/paper/2109.08969/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 72 references that are in the map.
- First posted on arXiv 18 Sep 2021.

## Builds on (most cited first, 20 of 20)

- [Stochastic gradient Markov chain Monte Carlo](https://mlsanity.com/paper/1907.06986/) (2019)
- [On Markov chain Monte Carlo methods for tall data](https://mlsanity.com/paper/1505.02827/) (2015)
- [Scalable Bayes via Barycenter in Wasserstein Space](https://mlsanity.com/paper/1508.05880/) (2015)
- [The Bouncy Particle Sampler: A Non-Reversible Rejection-Free Markov Chain Monte Carlo Method](https://mlsanity.com/paper/1510.02451/) (2015)
- [Austerity in MCMC Land: Cutting the Metropolis-Hastings Budget](https://mlsanity.com/paper/1304.5299/) (2013)
- [Speeding Up MCMC by Efficient Data Subsampling](https://mlsanity.com/paper/1404.4178/) (2014)
- [Piecewise Deterministic Markov Processes for Continuous-Time Monte Carlo](https://mlsanity.com/paper/1611.07873/) (2016)
- [DG-LMC: A Turn-key and Scalable Synchronous Distributed MCMC Algorithm via Langevin Monte Carlo within Gibbs](https://mlsanity.com/paper/2106.06300/) (2021)
- [Distributed Generalized Cross-Validation for Divide-and-Conquer Kernel Ridge Regression and its Asymptotic Optimality](https://mlsanity.com/paper/1612.05907/) (2016)
- [Robust and Scalable Bayes via a Median of Subset Posterior Measures](https://mlsanity.com/paper/1403.2660/) (2014)
- [Minibatch Gibbs Sampling on Large Graphical Models](https://mlsanity.com/paper/1806.06086/) (2018)
- [Fast Moment-Based Estimation for Hierarchical Models](https://mlsanity.com/paper/1504.04941/) (2015)
- [Poisson-Minibatching for Gibbs Sampling with Convergence Rate Guarantees](https://mlsanity.com/paper/1911.09771/) (2019)
- [HOGWILD!-Gibbs can be PanAccurate](https://mlsanity.com/paper/1811.10581/) (2018)
- [Divide-and-Conquer Bayesian Inference in Hidden Markov Models](https://mlsanity.com/paper/2105.14395/) (2021)
- [Scalable Bayesian inference for time series via divide-and-conquer](https://mlsanity.com/paper/2106.11043/) (2021)
- [A fast asynchronous MCMC sampler for sparse Bayesian inference](https://mlsanity.com/paper/2108.06446/) (2021)
- [Scalable Bayesian shrinkage and uncertainty quantification for high-dimensional regression](https://mlsanity.com/paper/1509.03697/) (2015)
- [An Asynchronous Distributed Expectation Maximization Algorithm For Massive Data: The DEM Algorithm](https://mlsanity.com/paper/1806.07533/) (2018)
- [Parallelising MCMC via Random Forests](https://mlsanity.com/paper/1911.09698/) (2019)

## Built on by (most cited first, 2 of 2)

- [Machine Learning and the Future of Bayesian Computation](https://mlsanity.com/paper/2304.11251/) (2023)
- [The data augmentation algorithm](https://mlsanity.com/paper/2406.10464/) (2024)

## Abstract (arXiv)

Data augmentation (DA) algorithms are widely used for Bayesian inference due to their simplicity. In massive data settings, however, DA algorithms are prohibitively slow because they pass through the full data in any iteration, imposing serious restrictions on their usage despite the advantages. Addressing this problem, we develop a framework for extending any DA that exploits asynchronous and distributed computing. The extended DA algorithm is indexed by a parameter r ∈ (0, 1) and is called Asynchronous and Distributed (AD) DA with the original DA as its parent. Any ADDA starts by dividing the full data into k smaller disjoint subsets and storing them on k processes, which could be machines or processors. Every iteration of ADDA augments only an r-fraction of the k data subsets with some positive probability and leaves the remaining (1-r)-fraction of the augmented data unchanged. The parameter draws are obtained using the r-fraction of new and (1-r)-fraction of old augmented data. For many choices of k and r, the fractional updates of ADDA lead to a significant speed-up over the parent DA in massive data settings, and it reduces to the distributed version of its parent DA when r=1. We show that the ADDA Markov chain is Harris ergodic with the desired stationary distribution under mild conditions on the parent DA algorithm. We demonstrate the numerical advantages of the ADDA in three representative examples corresponding to different kinds of massive data settings encountered in applications. In all these examples, our DA generalization is significantly faster than its parent DA algorithm for all the choices of k and r. We also establish geometric ergodicity of the ADDA Markov chain for all three examples, which in turn yields asymptotically valid standard errors for estimates of desired posterior quantities.