# Austerity in MCMC Land: Cutting the Metropolis-Hastings Budget

arXiv: https://arxiv.org/abs/1304.5299 · HTML: https://mlsanity.com/paper/1304.5299/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2013.

## Built on by (most cited first, 24 of 24)

- [Bayesian inference via sparse Hamiltonian flows](https://mlsanity.com/paper/2203.05723/) (2022)
- [Fast Bayesian Coresets via Subsampling and Quasi-Newton Refinement](https://mlsanity.com/paper/2203.09675/) (2022)
- [Non-reversible Parallel Tempering for Deep Posterior Approximation](https://mlsanity.com/paper/2211.10837/) (2022)
- [Variational Inference for Bayesian Neural Networks under Model and Parameter Uncertainty](https://mlsanity.com/paper/2305.00934/) (2023)
- [Coreset Markov Chain Monte Carlo](https://mlsanity.com/paper/2310.17063/) (2023)
- [Probabilistic Inference and Learning with Stein's Method](https://mlsanity.com/paper/2603.07467/) (2026)
- [Machine Learning and the Future of Bayesian Computation](https://mlsanity.com/paper/2304.11251/) (2023)
- [Structure Learning with Adaptive Random Neighborhood Informed MCMC](https://mlsanity.com/paper/2311.00599/) (2023)
- [Nystr"om Kernel Stein Discrepancy](https://mlsanity.com/paper/2406.08401/) (2024)
- [Approximate Bayesian inference from noisy likelihoods with Gaussian process emulated MCMC](https://mlsanity.com/paper/2104.03942/) (2021)
- [Interpolating between sampling and variational inference with infinite stochastic mixtures](https://mlsanity.com/paper/2110.09618/) (2021)
- [Asynchronous and Distributed Data Augmentation for Massive Data Settings](https://mlsanity.com/paper/2109.08969/) (2021)
- [AdamMCMC: Combining Metropolis Adjusted Langevin with Momentum-based Optimization](https://mlsanity.com/paper/2312.14027/) (2023)
- [ISR: Invertible Symbolic Regression](https://mlsanity.com/paper/2405.06848/) (2024)
- [Robust Approximate Sampling via Stochastic Gradient Barker Dynamics](https://mlsanity.com/paper/2405.08999/) (2024)
- [General bounds on the quality of Bayesian coresets](https://mlsanity.com/paper/2405.11780/) (2024)
- [Bayesian Data Sketching for Varying Coefficient Regression Models](https://mlsanity.com/paper/2506.00270/) (2025)
- [Quantifying the mini-batching error in Bayesian inference for Adaptive Langevin dynamics](https://mlsanity.com/paper/2105.10347/) (2021)
- [Data Subsampling for Bayesian Neural Networks](https://mlsanity.com/paper/2210.09141/) (2022)
- [Bayesian Computation in Deep Learning](https://mlsanity.com/paper/2502.18300/) (2025)
- [Robust Stochastic Gradient Posterior Sampling with Lattice Based Discretisation](https://mlsanity.com/paper/2602.15925/) (2026)
- [How To Train Your Program: a Probabilistic Programming Pattern for Bayesian Learning From Data](https://mlsanity.com/paper/2105.03650/) (2021)
- [Minibatch training of neural network ensembles via trajectory sampling](https://mlsanity.com/paper/2306.13442/) (2023)
- [Efficient MCMC Sampling with Expensive-to-Compute and Irregular Likelihoods](https://mlsanity.com/paper/2505.10448/) (2025)

## Abstract (arXiv)

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.