# Efficient Informed Proposals for Discrete Distributions via Newton's Series Approximation

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 42 references that are in the map.
- First posted on arXiv 27 Feb 2023.

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

- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Non-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1711.02281/) (2017)
- [BERT has a Mouth, and It Must Speak: BERT as a Markov Random Field Language Model](https://mlsanity.com/paper/1902.04094/) (2019)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Generative Flow Networks for Discrete Probabilistic Modeling](https://mlsanity.com/paper/2202.01361/) (2022)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [A Langevin-like Sampler for Discrete Distributions](https://mlsanity.com/paper/2206.09914/) (2022)
- [Probabilistic Binary Neural Networks](https://mlsanity.com/paper/1809.03368/) (2018)
- [Stein Variational Inference for Discrete Distributions](https://mlsanity.com/paper/2003.00605/) (2020)
- [Optimal Scaling for Locally Balanced Proposals in Discrete Spaces](https://mlsanity.com/paper/2209.08183/) (2022)
- [Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC](https://mlsanity.com/paper/2102.02374/) (2021)
- [LSB: Local Self-Balancing MCMC in Discrete Spaces](https://mlsanity.com/paper/2109.03867/) (2021)
- [From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models](https://mlsanity.com/paper/2006.01293/) (2020)
- [Improving multiple-try Metropolis with local balancing](https://mlsanity.com/paper/2211.11613/) (2022)
- [Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order](https://mlsanity.com/paper/1712.05450/) (2017)

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

- [Gradient-based Discrete Sampling with Automatic Cyclical Scheduling](https://mlsanity.com/paper/2402.17699/) (2024)
- [Reheated Gradient-based Discrete Sampling for Combinatorial Optimization](https://mlsanity.com/paper/2503.04047/) (2025)
- [Divide-and-Conquer Predictive Coding: a structured Bayesian inference algorithm](https://mlsanity.com/paper/2408.05834/) (2024)
- [Enhancing Gradient-based Discrete Sampling via Parallel Tempering](https://mlsanity.com/paper/2502.19240/) (2025)
- [Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs](https://mlsanity.com/paper/2505.18300/) (2025)
- [Slithering Through Gaps: Capturing Discrete Isolated Modes via Logistic Bridging](https://mlsanity.com/paper/2604.10821/) (2026)
- [Fine-Tuning Low-Bit Models with Gradient in Quantized Code Space](https://mlsanity.com/paper/2608.30908/) (2026)

## Abstract (arXiv)

Gradients have been exploited in proposal distributions to accelerate the convergence of Markov chain Monte Carlo algorithms on discrete distributions. However, these methods require a natural differentiable extension of the target discrete distribution, which often does not exist or does not provide effective gradient guidance. In this paper, we develop a gradient-like proposal for any discrete distribution without this strong requirement. Built upon a locally-balanced proposal, our method efficiently approximates the discrete likelihood ratio via Newton's series expansion to enable a large and efficient exploration in discrete spaces. We show that our method can also be viewed as a multilinear extension, thus inheriting its desired properties. We prove that our method has a guaranteed convergence rate with or without the Metropolis-Hastings step. Furthermore, our method outperforms a number of popular alternatives in several different experiments, including the facility location problem, extractive text summarization, and image retrieval.