Austerity in MCMC Land: Cutting the Metropolis-Hastings Budget

Abstract

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.

v4 - version accepted by ICML2014

References in corpus (2)

• The pseudo-marginal approach for efficient Monte Carlo computations
• Bayesian Posterior Sampling via Stochastic Gradient Fisher Scoring

Cited by in corpus (62)

• Stochastic Gradient Hamiltonian Monte Carlo
• A Complete Recipe for Stochastic Gradient MCMC
• Preconditioned Stochastic Gradient Langevin Dynamics for Deep Neural Networks
• Speeding Up MCMC by Efficient Data Subsampling
• On Markov chain Monte Carlo methods for tall data
• Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning
• Measuring Sample Quality with Stein's Method
• On Russian Roulette Estimates for Bayesian Inference with Doubly-Intractable Likelihoods
• GPS-ABC: Gaussian Process Surrogate Approximate Bayesian Computation
• A Kernel Test of Goodness of Fit
• Measuring Sample Quality with Kernels
• Expectation propagation as a way of life: A framework for Bayesian inference on partitioned data
• Firefly Monte Carlo: Exact MCMC with Subsets of Data
• Emulation of Higher-Order Tensors in Manifold Monte Carlo Methods for Bayesian Inverse Problems
• Speeding Up MCMC by Delayed Acceptance and Data Subsampling
• Scalable Bayes via Barycenter in Wasserstein Space
• Ergodicity of Approximate MCMC Chains with Applications to Large Data Sets
• A Survey of Bayesian Statistical Approaches for Big Data
• Online Bayesian Passive-Aggressive Learning
• Bayes Shrinkage at GWAS scale: Convergence and Approximation Theory of a Scalable MCMC Algorithm for the Horseshoe Prior
• Mean-Field Networks
• Accelerating MCMC via Parallel Predictive Prefetching
• Consistency and fluctuations for stochastic gradient Langevin dynamics
• Variational consensus Monte Carlo
• Unbiased Bayes for Big Data: Paths of Partial Posteriors
• Big Learning with Bayesian Methods
• Error bounds for Approximations of Markov chains used in Bayesian Sampling
• Hamiltonian Monte Carlo with Energy Conserving Subsampling
• Optimal approximating Markov chains for Bayesian inference
• PASS-GLM: polynomial approximate sufficient statistics for scalable Bayesian GLM inference
• Metropolis-Hastings view on variational inference and adversarial training
• Large-Scale Distributed Bayesian Matrix Factorization using Stochastic Gradient MCMC
• Distributed Bayesian Learning with Stochastic Natural-gradient Expectation Propagation and the Posterior Server
• Scaling Nonparametric Bayesian Inference via Subsample-Annealing
• Accelerating delayed-acceptance Markov chain Monte Carlo algorithms
• Langevin Markov Chain Monte Carlo with stochastic gradients
• Hypothesis testing for Markov chain Monte Carlo
• No Free Lunch for Approximate MCMC
• Quantifying the accuracy of approximate diffusions and Markov chains
• The block-Poisson estimator for optimally tuned exact subsampling MCMC
• Exploiting the Statistics of Learning and Inference
• Sparse Variational Inference: Bayesian Coresets from Scratch
• Asymptotically Optimal Exact Minibatch Metropolis-Hastings
• Implicit Langevin Algorithms for Sampling From Log-concave Densities
• Mini-batch Metropolis-Hastings MCMC with Reversible SGLD Proposal
• Scalable Metropolis-Hastings for Exact Bayesian Inference with Large Datasets
• Light and Widely Applicable MCMC: Approximate Bayesian Inference for Large Datasets
• How Can Subsampling Reduce Complexity in Sequential MCMC Methods and Deal with Big Data in Target Tracking?
• Sublinear-Time Approximate MCMC Transitions for Probabilistic Programs
• Subsampling MCMC - An introduction for the survey statistician
• Approximate Bayesian inference from noisy likelihoods with Gaussian process emulated MCMC
• Two-Stage Metropolis-Hastings for Tall Data
• Scalable Bayesian Nonparametric Clustering and Classification
• Approximate Cross-validated Mean Estimates for Bayesian Hierarchical Regression Models
• General Bayesian inference schemes in infinite mixture models
• Fast Sampling for Bayesian Max-Margin Models
• An Algorithm for Distributed Bayesian Inference in Generalized Linear Models
• Probabilistic Programs with Stochastic Conditioning
• Exploiting Multi-Core Architectures for Reduced-Variance Estimation with Intractable Likelihoods
• What is the best predictor that you can compute in five minutes using a given Bayesian hierarchical model?
• Perturbation Analysis of Markov Chain Monte Carlo for Graphical Models
• Data Subsampling for Bayesian Neural Networks