# Optimal Scaling for Locally Balanced Proposals in Discrete Spaces

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 50 references that are in the map.
- First posted on arXiv 16 Sep 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks](https://mlsanity.com/paper/1503.00075/) (2015)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [Learning Discrete Energy-based Models via Auxiliary-variable Local Exploration](https://mlsanity.com/paper/2011.05363/) (2020)
- [The Barker proposal: combining robustness and efficiency in gradient-based MCMC](https://mlsanity.com/paper/1908.11812/) (2019)
- [The Hamming Ball Sampler](https://mlsanity.com/paper/1504.08133/) (2015)
- [Stein Variational Inference for Discrete Distributions](https://mlsanity.com/paper/2003.00605/) (2020)
- [Gradient-based Adaptive Markov Chain Monte Carlo](https://mlsanity.com/paper/1911.01373/) (2019)
- [LSB: Local Self-Balancing MCMC in Discrete Spaces](https://mlsanity.com/paper/2109.03867/) (2021)
- [Optimal design of the Barker proposal and other locally-balanced Metropolis-Hastings algorithms](https://mlsanity.com/paper/2201.01123/) (2022)
- [A fresh take on 'Barker dynamics' for MCMC](https://mlsanity.com/paper/2012.09731/) (2020)
- [Entropy-based adaptive Hamiltonian Monte Carlo](https://mlsanity.com/paper/2110.14625/) (2021)

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

- [Unlocking Guidance for Discrete State-Space Diffusion and Flow Models](https://mlsanity.com/paper/2406.01572/) (2024)
- [Gradient-based Discrete Sampling with Automatic Cyclical Scheduling](https://mlsanity.com/paper/2402.17699/) (2024)
- [Efficient Informed Proposals for Discrete Distributions via Newton's Series Approximation](https://mlsanity.com/paper/2302.13929/) (2023)
- [Reheated Gradient-based Discrete Sampling for Combinatorial Optimization](https://mlsanity.com/paper/2503.04047/) (2025)
- [Improving multiple-try Metropolis with local balancing](https://mlsanity.com/paper/2211.11613/) (2022)
- [Energy-Based Modelling for Discrete and Mixed Data via Heat Equations on Structured Spaces](https://mlsanity.com/paper/2412.01019/) (2024)
- [Gradient GA: Gradient Genetic Algorithm for Drug Molecular Design](https://mlsanity.com/paper/2502.09860/) (2025)
- [Enhancing Gradient-based Discrete Sampling via Parallel Tempering](https://mlsanity.com/paper/2502.19240/) (2025)
- [Training Discrete Energy-Based Models with Energy Discrepancy](https://mlsanity.com/paper/2307.07595/) (2023)

## Abstract (arXiv)

Optimal scaling has been well studied for Metropolis-Hastings (M-H) algorithms in continuous spaces, but a similar understanding has been lacking in discrete spaces. Recently, a family of locally balanced proposals (LBP) for discrete spaces has been proved to be asymptotically optimal, but the question of optimal scaling has remained open. In this paper, we establish, for the first time, that the efficiency of M-H in discrete spaces can also be characterized by an asymptotic acceptance rate that is independent of the target distribution. Moreover, we verify, both theoretically and empirically, that the optimal acceptance rates for LBP and random walk Metropolis (RWM) are 0.574 and 0.234 respectively. These results also help establish that LBP is asymptotically O(N^frac23) more efficient than RWM with respect to model dimension N. Knowledge of the optimal acceptance rate allows one to automatically tune the neighborhood size of a proposal distribution in a discrete space, directly analogous to step-size control in continuous spaces. We demonstrate empirically that such adaptive M-H sampling can robustly improve sampling in a variety of target distributions in discrete spaces, including training deep energy based models.