Austerity in MCMC Land: Cutting the Metropolis-Hastings Budget

By Anoop Korattikara, Yutian Chen, Max Welling. 2013

251 citations recorded by the source corpus.

Can we make Bayesian posterior MCMC sampling more efficient when faced with very large datasets? We argue that computing the likelihood for N datapoints in the Metropolis-Hastings (MH) test to reach a single binary decision is computationally inefficient. We introduce an approximate MH rule based on a sequential hypothesis test that allows us to accept or reject samples with high confidence using only a fraction of the data required for the exact MH rule. While this method introduces an asymptotic bias, we show that this bias can be controlled and is more than offset by a decrease in variance due to our ability to draw more samples per unit of time.

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

A Kernel Test of Goodness of Fit (2016, methodology): “We now illustrate how to quantify bias-variance trade-offs in an approximate MCMC algorithm – austerity MCMC (Korattikara et al., 2013).”
Stochastic Gradient Hamiltonian Monte Carlo (2014, background): “(13): for i = 1 to m do θi ← θi−1 + tM−1ri−1 ri ← ri−1 − t∇Ũ(θi)− tCM−1ri−1 +N (0, 2(C − B̂) t) end (θ(t+1), r(t+1)) = (θm, rm), no M-H step end”
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): “…2013; Broderick et al., 2013; Campbell 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;…”
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.”
A Complete Recipe for Stochastic Gradient MCMC (2015, methodology): “A similar bias-speed tradeoff was used in [11, 3] to construct MH samplers, in addition to being used in SGLD and SGHMC. 3 Applying the Theory to Construct Samplers”
GPS-ABC: Gaussian Process Surrogate Approximate Bayesian Computation (2014, methodology): “In [14], another approximate MCMC algorithm is presented and it provides a proof for an upper bound on the error in the stationary distribution.”
Exploiting Multi-Core Architectures for Reduced-Variance Estimation with Intractable Likelihoods (2014, methodology): “It is worth noting that several authors have used this type of approach to develop approximate algorithms for large datasets by using subsets of the data to approximate the likelihood, (Welling and Teh, 2011; Anh et al., 2012; Korattikara et al., 2014).”
Stochastic Gradient Markov Chain Monte Carlo (2019, methodology): “For example, in the Metropolis–Hastings algorithm, the accept-reject step can be approximated with a subset of the full data (Bardenet, Doucet, and Holmes 2014; Korattikara, Chen, and Welling 2014; Quiroz et al. 2019).”
Expectation Propagation as a Way of Life (2020, background): “…have been recently proposed to combine inferences from partitioned data (see Ahn, Korattikara, and Welling, 2012, Gershman, Hoffman, and Blei, 2012, Korattikara, Chen, and Welling, 2013, Hoffman et al., 2013, Wang and Blei, 2013, Scott et al., 2013, Wang and Dunson, 2013, Neiswanger et al., 2013,…”
Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning (2019, background): “To correct this error, it is possible to do stochastic Metropolis-Hastings (MH) (Korattikara et al., 2014; Bardenet et al., 2014; Chen et al., 2016b).”
On Markov chain Monte Carlo methods for tall data (2015, background): “However, as noted in (Korattikara et al., 2014; Bardenet et al., 2014), the results can be arbitrarily far from the original MH when the CLT approximations are not valid.”
Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach (2014, methodology): “Running the approximate MH algorithm of Korattikara et al. (2014) , using a level for the test = 0.05, and starting each iteration by looking at t = 2 points so as to be able to compute the variance of the log likelihood ratios, leads to the marginal of σ shown in Figure 4(a).”