On Markov chain Monte Carlo methods for tall data

By Rémi Bardenet, Arnaud Doucet, Christopher C. Holmes. 2015

303 citations recorded by the source corpus.

Markov chain Monte Carlo methods are often deemed too computationally intensive to be of any practical use for big data applications, and in particular for inference on datasets containing a large number $n$ of individual data points, also known as tall datasets. In scenarios where data are assumed independent, various approaches to scale up the Metropolis-Hastings algorithm in a Bayesian inference context have been recently proposed in machine learning and computational statistics. These approaches can be grouped into two categories: divide-and-conquer approaches and, subsampling-based algorithms. The aims of this article are as follows. First, we present a comprehensive review of the existing literature, commenting on the underlying assumptions and theoretical guarantees of each method. Second, by leveraging our understanding of these limitations, we propose an original subsampling-based approach which samples from a distribution provably close to the posterior distribution of interest, yet can require less than $O(n)$ data point likelihood evaluations at each iteration for certain statistical models in favourable scenarios. Finally, we have only been able so far to propose subsampling-based methods which display good performance in scenarios where the Bernstein-von Mises approximation of the target posterior distribution is excellent. It remains an open challenge to develop such methods in scenarios where the Bernstein-von Mises approximation is poor.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Coresets for Scalable Bayesian Logistic Regression (2016, methodology): “Examples include subsampling and streaming methods for variational Bayes [11, 12, 20], subsampling methods for MCMC [2, 7, 8, 22, 25, 33], and distributed “consensus” methods for MCMC [28, 30, 31].”
Automated Scalable Bayesian Inference via Hilbert Coresets (2017, methodology): “, 2015), subsampling methods for MCMC (Welling and Teh, 2011; Ahn et al., 2012; Bardenet et al., 2014; Korattikara et al., 2014; Maclaurin and Adams, 2014; Bardenet et al., 2015), and distributed “consensus” methods for MCMC (Scott et al.”
Sparse Variational Inference: Bayesian Coresets from Scratch (2019, methodology): “Designing correct MCMC schemes in the large-scale data setting is a challenging, problem-speciﬁc task [10–12]; and despite recent results in asymptotic theory [13–16], it is difﬁcult to assess the effect of the variational family on VI approximations for ﬁnite data, where a poor choice can result…”
ProBO: Versatile Bayesian Optimization Using Any Probabilistic Programming Language (2019, methodology): “For example, most MCMC methods have complexity O ( n ) per iteration [4].”
Stochastic Gradient Markov Chain Monte Carlo (2019, methodology): “Recent works, for example Baker et al. (2019a) and Huggins and Zou (2016) (see Bardenet et al. , 2017b; Pollock et al. , 2016; Bierkens et al. , 2019, for similar ideas used in different Monte Carlo procedures), have implemented this control variate technique with each u i ( θ ) set as a constant.”
Bayesian forecasting in economics and finance: A modern review (2022, methodology): “7 Such schemes can thus struggle when confronted with ‘big data’ (Bardenet et al., 2017).”
The Bouncy Particle Sampler: A Nonreversible Rejection-Free Markov Chain Monte Carlo Method (2015, methodology): “To improve this rate, one can adapt the control variate ideas introduced in [3] for the MH algorithm to these schemes.”
Expectation Propagation as a Way of Life: A Framework for Bayesian Inference on Partitioned Data (2014, background): “Data partitioning is an extremely active research area with several black box algorithms being proposed by various research groups (e.g. Kucukelbir et al., 2016; Hasenclever et al., 2017; Bardenet et al., 2015).”
Hands-On Bayesian Neural Networks—A Tutorial for Deep Learning Users (2020, methodology): “Despite their inherent drawbacks, MCMC methods can be considered among the best available and the most popular solutions for sampling from exact posterior distributions in Bayesian statistics [78].”