Firefly Monte Carlo: Exact MCMC with Subsets of Data

By Dougal Maclaurin, Ryan P. Adams. 2014

186 citations recorded by the source corpus.

Markov chain Monte Carlo (MCMC) is a popular tool for Bayesian inference. However, MCMC cannot be practically applied to large data sets because of the prohibitive cost of evaluating every likelihood term at every iteration. Here we present Firefly Monte Carlo (FlyMC) MCMC algorithm with auxiliary variables that only queries the likelihoods of a subset of the data at each iteration yet simulates from the exact posterior distribution. FlyMC is compatible with modern MCMC algorithms, and only requires a lower bound on the per-datum likelihood factors. In experiments, we find that FlyMC generates samples from the posterior more than an order of magnitude faster than regular MCMC, allowing MCMC methods to tackle larger datasets than were previously considered feasible.

Subfields: Artificial Intelligence, Statistics and Probability, Probabilistic & Bayesian Methods

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

In Probabilistic & Bayesian Methods

Citations in the corpus

Large Language Models Are Human-Level Prompt Engineers (2022, methodology): “We note that a similar score estimation scheme has been used in previous works (Li et al., 2022; Maclaurin & Adams, 2015).”
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): “…et al., 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., 2016; Srivastava et al., 2015; Rabinovich et al.,…”
Posterior Computation with the Gibbs Zig-Zag Sampler (2020, methodology): “Data sub-sampling has been explored as a way to speed up MCMC for large datasets (Welling and Teh, 2011; Maclaurin and Adams, 2015; Quiroz et al., 2018).”
The Bouncy Particle Sampler: A Nonreversible Rejection-Free Markov Chain Monte Carlo Method (2015, methodology): “This version of Fireﬂy outperforms experimentally signiﬁcantly the standard MH in terms of ESS per-datum likelihood [21].”
Bayesian computation: a summary of the current state, and samples backwards and forwards (2015, methodology): “Several Big Data MCMC approaches have been already considered in Welling and Teh (2011), Korattikara et al. (2013), Teh et al. (2014), Bardenet et al. (2014), Maclaurin and Adams (2014), Minsker et al. (2014), Quiroz et al. (2014) and Strathmann et al. (2015).”
Variational Boosting: Iteratively Refining Posterior Approximations (2016, background): “With a few exceptions [24, 36], most MCMC algorithms require evaluating a log-likelihood that touches all data at each step in the chain (sometimes many times per step).”
Bayesian computation: a perspective on the current state, and sampling backwards and forwards (2015, background): “…complex models with intractable like-lihoods, but also by the need of MCMC algorithms for Big Data in contexts where the likelihood function can not be evaluated for the whole dataset (Ko-rattikara et al. 2013; Bardenet et al. 2014; Teh et al. 2014; Maclaurin and Adams 2014; Minsker et al. 2014).”
Provable Bayesian Inference via Particle Mirror Descent (2015, methodology): “To address this issue, approximate sampling algorithms have been proposed which use only a small batch of data points at each iteration (e.g. Chopin, 2002; Balakrishnan and Madigan, 2006; Welling and Teh, 2011; Maclaurin and Adams, 2014).”
Bayesian Coresets: Revisiting the Nonconvex Optimization Perspective (2021, methodology): “…for variational Bayes (Hoﬀman et al., 2013; Broderick et al., 2013), subsampling methods for MCMC (Welling & Teh, 2011; Ahn et al., 2012; Korattikara et al., 2014; Maclaurin & Adams, 2015), and consensus methods for MCMC (Srivastava et al., 2015; Rabinovich et al., 2015; Scott et al., 2016).”
On nonnegative unbiased estimators (2013, background): “…(2014); Korattikara, Chen and Welling(2014) describe ways of approximating the Metropolis-Hastings ratio in the generic context of large datasets;Maclaurin and Adams (2014) uses a lower bound on the local likelihood to simulate from the exact posterior distribution while evaluating only a…”
Stochastic variational inference for hidden Markov models (2014, methodology): “There is considerable interest in leveraging these methods for Bayesian inference since traditional algorithms such as Markov chain Monte Carlo (MCMC) scale poorly to large datasets, though subset-based MCMC methods have been recently proposed as well [5, 6, 7, 8].”
Exploiting Multi-Core Architectures for Reduced-Variance Estimation with Intractable Likelihoods (2014, methodology): “…et al., 2010) in a straightforward manner that directly complements (and is compatible with) related research eﬀorts for parallelisation of MCMC methodology (Alquier et al., 2014; Angelino et al., 2014; Bardenet et al., 2014; Calderhead, 2014; Korattikara et al., 2014; Maclaurin and Adams, 2014).”
Communication-Efficient Distributed Statistical Inference (2016, background): “A statistical literature on parallel and distributed inference has begun to emerge, both in a frequentist setting (Duchi, Agar-wal, and Wainwright 2012; Zhang, Duchi, and Wainwright 2013; Kannan, Vempala, and Woodruff 2014; Kleiner et al. 2014; Shamir, Srebro, and Zhang 2014; Mackey, Talwalkar, and…”
Bayesian Sampling Using Stochastic Gradient Thermostats (2014, background): “There is some recent work [2, 3, 14] which attempts to estimate the Metropolis step using partial data.”
On Markov chain Monte Carlo methods for tall data (2015, methodology): “3 Building γ̂(θ) with auxiliary variables In (MacLaurin and Adams, 2014), the authors propose an alternative MCMC to sample from π which, similarly to the method described previously, only requires evaluating the likelihood of a subset of the data at each iteration.”
Modeling, Inference and Optimization With Composable Differentiable Procedures (2016, background): “It appeared at UAI 2014 [64] where it won best paper.”