# Accelerated Markov Chain Monte Carlo Algorithms on Discrete States

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 64 references that are in the map.
- First posted on arXiv 19 May 2025.

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

- [Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution](https://mlsanity.com/paper/2310.16834/) (2023)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem](https://mlsanity.com/paper/1802.08089/) (2018)
- [Accelerated Information Gradient flow](https://mlsanity.com/paper/1909.02102/) (2019)
- [Normalizing flow neural networks by JKO scheme](https://mlsanity.com/paper/2212.14424/) (2022)
- [A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization](https://mlsanity.com/paper/1910.10782/) (2019)
- [Accelerated Flow for Probability Distributions](https://mlsanity.com/paper/1901.03317/) (2019)
- [Towards Riemannian Accelerated Gradient Methods](https://mlsanity.com/paper/1806.02812/) (2018)
- [Accelerating optimization over the space of probability measures](https://mlsanity.com/paper/2310.04006/) (2023)
- [Hessian-Free High-Resolution Nesterov Acceleration for Sampling](https://mlsanity.com/paper/2006.09230/) (2020)
- [Irreversible Samplers from Jump and Continuous Markov Processes](https://mlsanity.com/paper/1608.05973/) (2016)
- [Gradient-adjusted underdamped Langevin dynamics for sampling](https://mlsanity.com/paper/2410.08987/) (2024)
- [Master equations for finite state mean field games with nonlinear activations](https://mlsanity.com/paper/2212.05675/) (2022)

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

- [Discrete Action Matching: Learning Stochastic Dynamics from Samples via State Graphs](https://mlsanity.com/paper/2610.05071/) (2026)
- [Nonlocal Hamiltonian Dynamics on Sparse L'evy Graphs: Spectral Analysis and Multimodal Sampling](https://mlsanity.com/paper/2610.06904/) (2026)

## Abstract (arXiv)

We propose a class of discrete state sampling algorithms based on Nesterov's accelerated gradient method, which extends the classical Metropolis-Hastings (MH) algorithm. The evolution of the discrete states probability distribution governed by MH can be interpreted as a gradient descent direction of the Kullback--Leibler (KL) divergence, via a mobility function and a score function. Specifically, this gradient is defined on a probability simplex equipped with a discrete Wasserstein-2 metric with a mobility function. This motivates us to study a momentum-based acceleration framework using damped Hamiltonian flows on the simplex set, whose stationary distribution matches the discrete target distribution. Furthermore, we design an interacting particle system to approximate the proposed accelerated sampling dynamics. The extension of the algorithm with a general choice of potentials and mobilities is also discussed. In particular, we choose the accelerated gradient flow of the relative Fisher information, demonstrating the advantages of the algorithm in estimating discrete score functions without requiring the normalizing constant and keeping positive probabilities. Numerical examples, including sampling on a Gaussian mixture supported on lattices or a distribution on a hypercube, demonstrate the effectiveness of the proposed discrete-state sampling algorithm.