# Asymptotically Optimal Exact Minibatch Metropolis-Hastings

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2020.

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

- [Accountability in an Algorithmic Society: Relationality, Responsibility, and Robustness in Machine Learning](https://mlsanity.com/paper/2202.05338/) (2022)
- [Surrogate Likelihoods for Variational Annealed Importance Sampling](https://mlsanity.com/paper/2112.12194/) (2021)
- [Masked Bayesian Neural Networks : Theoretical Guarantee and its Posterior Inference](https://mlsanity.com/paper/2305.14765/) (2023)
- [Training Bayesian Neural Networks with Sparse Subspace Variational Inference](https://mlsanity.com/paper/2402.11025/) (2024)
- [Entropy-MCMC: Sampling from Flat Basins with Ease](https://mlsanity.com/paper/2310.05401/) (2023)
- [Approximate Bayesian inference from noisy likelihoods with Gaussian process emulated MCMC](https://mlsanity.com/paper/2104.03942/) (2021)
- [DP-Fast MH: Private, Fast, and Accurate Metropolis-Hastings for Large-Scale Bayesian Inference](https://mlsanity.com/paper/2303.06171/) (2023)
- [A Langevin sampling algorithm inspired by the Adam optimizer](https://mlsanity.com/paper/2504.18911/) (2025)
- [AdamMCMC: Combining Metropolis Adjusted Langevin with Momentum-based Optimization](https://mlsanity.com/paper/2312.14027/) (2023)
- [High-accuracy log-concave sampling with stochastic queries](https://mlsanity.com/paper/2602.14342/) (2026)
- [Bayesian Computation in Deep Learning](https://mlsanity.com/paper/2502.18300/) (2025)
- [Cyclical Kernel Adaptive Metropolis](https://mlsanity.com/paper/2206.14421/) (2022)
- [Markov chain Monte Carlo without evaluating the target: an auxiliary variable approach](https://mlsanity.com/paper/2406.05242/) (2024)
- [Efficient MCMC Sampling with Expensive-to-Compute and Irregular Likelihoods](https://mlsanity.com/paper/2505.10448/) (2025)

## Abstract (arXiv)

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.