# LSB: Local Self-Balancing MCMC in Discrete Spaces

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 34 references that are in the map.
- First posted on arXiv 8 Sep 2021.

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

- [On the Anatomy of MCMC-Based Maximum Likelihood Learning of Energy-Based Models](https://mlsanity.com/paper/1903.12370/) (2019)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [Generalizing Hamiltonian Monte Carlo with Neural Networks](https://mlsanity.com/paper/1711.09268/) (2017)
- [A-NICE-MC: Adversarial Training for MCMC](https://mlsanity.com/paper/1706.07561/) (2017)
- [Learning Discrete Energy-based Models via Auxiliary-variable Local Exploration](https://mlsanity.com/paper/2011.05363/) (2020)
- [A Framework for Adaptive MCMC Targeting Multimodal Distributions](https://mlsanity.com/paper/1812.02609/) (2018)
- [The Hamming Ball Sampler](https://mlsanity.com/paper/1504.08133/) (2015)
- [Meta-Learning for Stochastic Gradient MCMC](https://mlsanity.com/paper/1806.04522/) (2018)
- [Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC](https://mlsanity.com/paper/2102.02374/) (2021)

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

- [A Langevin-like Sampler for Discrete Distributions](https://mlsanity.com/paper/2206.09914/) (2022)
- [Discrete Langevin Sampler via Wasserstein Gradient Flow](https://mlsanity.com/paper/2206.14897/) (2022)
- [Optimal Scaling for Locally Balanced Proposals in Discrete Spaces](https://mlsanity.com/paper/2209.08183/) (2022)
- [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)
- [EXPLAIN, AGREE, LEARN: Scaling Learning for Neural Probabilistic Logic](https://mlsanity.com/paper/2408.08133/) (2024)
- [Improving multiple-try Metropolis with local balancing](https://mlsanity.com/paper/2211.11613/) (2022)

## Abstract (arXiv)

We present the Local Self-Balancing sampler (LSB), a local Markov Chain Monte Carlo (MCMC) method for sampling in purely discrete domains, which is able to autonomously adapt to the target distribution and to reduce the number of target evaluations required to converge. LSB is based on (i) a parametrization of locally balanced proposals, (ii) a newly proposed objective function based on mutual information and (iii) a self-balancing learning procedure, which minimises the proposed objective to update the proposal parameters. Experiments on energy-based models and Markov networks show that LSB converges using a smaller number of queries to the oracle distribution compared to recent local MCMC samplers.