# Markov chain Monte Carlo without evaluating the target: an auxiliary variable approach

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 51 references that are in the map.
- First posted on arXiv 7 Jun 2024.

## Builds on (most cited first, 17 of 17)

- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [Bayesian Coreset Construction via Greedy Iterative Geodesic Ascent](https://mlsanity.com/paper/1802.01737/) (2018)
- [Automated Scalable Bayesian Inference via Hilbert Coresets](https://mlsanity.com/paper/1710.05053/) (2017)
- [On Markov chain Monte Carlo methods for tall data](https://mlsanity.com/paper/1505.02827/) (2015)
- [The Bouncy Particle Sampler: A Non-Reversible Rejection-Free Markov Chain Monte Carlo Method](https://mlsanity.com/paper/1510.02451/) (2015)
- [Firefly Monte Carlo: Exact MCMC with Subsets of Data](https://mlsanity.com/paper/1403.5693/) (2014)
- [Auxiliary gradient-based sampling algorithms](https://mlsanity.com/paper/1610.09641/) (2016)
- [The Barker proposal: combining robustness and efficiency in gradient-based MCMC](https://mlsanity.com/paper/1908.11812/) (2019)
- [Involutive MCMC: a Unifying Framework](https://mlsanity.com/paper/2006.16653/) (2020)
- [Asymptotically Optimal Exact Minibatch Metropolis-Hastings](https://mlsanity.com/paper/2006.11677/) (2020)
- [An Efficient Minibatch Acceptance Test for Metropolis-Hastings](https://mlsanity.com/paper/1610.06848/) (2016)
- [Optimal design of the Barker proposal and other locally-balanced Metropolis-Hastings algorithms](https://mlsanity.com/paper/2201.01123/) (2022)
- [On nonnegative unbiased estimators](https://mlsanity.com/paper/1309.6473/) (2013)
- [Convergence of hybrid slice sampling via spectral gap](https://mlsanity.com/paper/1409.2709/) (2014)
- [Poisson-Minibatching for Gibbs Sampling with Convergence Rate Guarantees](https://mlsanity.com/paper/1911.09771/) (2019)
- [On the Theoretical Properties of the Exchange Algorithm](https://mlsanity.com/paper/2005.09235/) (2020)
- [Bayesian Goodness of Fit Tests: A Conversation for David Mumford](https://mlsanity.com/paper/1803.11251/) (2018)

## Abstract (arXiv)

In sampling tasks, it is common for target distributions to be known up to a normalizing constant. However, in many situations, even evaluating the unnormalized distribution can be costly or infeasible. This issue arises in scenarios such as sampling from the Bayesian posterior for tall datasets and the `doubly-intractable' distributions. In this paper, we begin by observing that seemingly different Markov chain Monte Carlo (MCMC) algorithms, such as the exchange algorithm, PoissonMH, and TunaMH, can be unified under a simple common procedure. We then extend this procedure into a novel framework that allows the use of auxiliary variables in both the proposal and the acceptance--rejection step. Several new MCMC algorithms emerge from this framework that uses estimated gradients to guide the proposal moves. They have demonstrated significantly better performance than existing methods on both synthetic and real datasets. We also develop theory for the new framework and use it to simplify and extend results for existing algorithms. The code to reproduce the experimental results can be found at https://github.com/ywwes26/Auxiliary-MCMC.