Asymptotically Optimal Exact Minibatch Metropolis-Hastings

Abstract

Metropolis-Hastings (MH) is a commonly-used MCMC algorithm, but it can be intractable on large datasets due to requiring computations over the whole dataset. In this paper, we study minibatch MH methods, which instead use subsamples to enable scaling. We observe that most existing minibatch MH methods are inexact (i.e. they may change the target distribution), and show that this inexactness can cause arbitrarily large errors in inference. We propose a new exact minibatch MH method, TunaMH, which exposes a tunable trade-off between its batch size and its theoretically guaranteed convergence rate. We prove a lower bound on the batch size that any minibatch MH method must use to retain exactness while guaranteeing fast convergence-the first such bound for minibatch MH-and show TunaMH is asymptotically optimal in terms of the batch size. Empirically, we show TunaMH outperforms other exact minibatch MH methods on robust linear regression, truncated Gaussian mixtures, and logistic regression.

References in corpus (8)

• MCMC using Hamiltonian dynamics
• The pseudo-marginal approach for efficient Monte Carlo computations
• Austerity in MCMC Land: Cutting the Metropolis-Hastings Budget
• Speeding Up MCMC by Efficient Data Subsampling
• Explicit error bounds for Markov chain Monte Carlo
• Firefly Monte Carlo: Exact MCMC with Subsets of Data
• Poisson-Minibatching for Gibbs Sampling with Convergence Rate Guarantees
• The block-Poisson estimator for optimally tuned exact subsampling MCMC

Cited by in corpus (2)

• Accountability in an Algorithmic Society: Relationality, Responsibility, and Robustness in Machine Learning
• Accuracy-Efficiency Trade-Offs and Accountability in Distributed ML Systems