# An Efficient Minibatch Acceptance Test for Metropolis-Hastings

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

## Key facts

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

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

- [Textual Bayes: Quantifying Prompt Uncertainty in LLM-Based Systems](https://mlsanity.com/paper/2506.10060/) (2025)
- [Non-reversible Parallel Tempering for Deep Posterior Approximation](https://mlsanity.com/paper/2211.10837/) (2022)
- [AdamMCMC: Combining Metropolis Adjusted Langevin with Momentum-based Optimization](https://mlsanity.com/paper/2312.14027/) (2023)
- [Bayesian Data Sketching for Varying Coefficient Regression Models](https://mlsanity.com/paper/2506.00270/) (2025)
- [High-accuracy log-concave sampling with stochastic queries](https://mlsanity.com/paper/2602.14342/) (2026)
- [Data Subsampling for Bayesian Neural Networks](https://mlsanity.com/paper/2210.09141/) (2022)
- [Differentially Private Statistical Inference through β-Divergence One Posterior Sampling](https://mlsanity.com/paper/2307.05194/) (2023)
- [Enhancing Gradient-based Discrete Sampling via Parallel Tempering](https://mlsanity.com/paper/2502.19240/) (2025)
- [Centroid Approximation for Bootstrap: Improving Particle Quality at Inference](https://mlsanity.com/paper/2110.08720/) (2021)
- [Minibatch training of neural network ensembles via trajectory sampling](https://mlsanity.com/paper/2306.13442/) (2023)
- [Markov chain Monte Carlo without evaluating the target: an auxiliary variable approach](https://mlsanity.com/paper/2406.05242/) (2024)

## Abstract (arXiv)

We present a novel Metropolis-Hastings method for large datasets that uses small expected-size minibatches of data. Previous work on reducing the cost of Metropolis-Hastings tests yield variable data consumed per sample, with only constant factor reductions versus using the full dataset for each sample. Here we present a method that can be tuned to provide arbitrarily small batch sizes, by adjusting either proposal step size or temperature. Our test uses the noise-tolerant Barker acceptance test with a novel additive correction variable. The resulting test has similar cost to a normal SGD update. Our experiments demonstrate several order-of-magnitude speedups over previous work.