📊 statistics

Accelerated Markov Chain Monte Carlo Algorithms on Discrete States

This paper proposes a class of accelerated discrete-state sampling algorithms that extend the Metropolis-Hastings method by interpreting its evolution as a gradient flow on a probability simplex under a discrete Wasserstein-2 metric, thereby utilizing Nesterov's momentum-based acceleration and an interacting particle system to efficiently sample from target distributions without requiring normalizing constants.

Original authors: Bohan Zhou, Shu Liu, Xinzhe Zuo, Wuchen Li

Published 2026-08-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Bohan Zhou, Shu Liu, Xinzhe Zuo, Wuchen Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the best spot to set up a campsite in a vast, foggy wilderness. You don't have a map, and you can't see the whole landscape at once. All you know is that some spots are "better" (maybe they're drier or have more firewood), but you can't measure the exact quality of every single spot because the math to do so is too complicated. This is the daily struggle of scientists and data detectives who need to sample from complex probability distributions. They use a tool called Markov Chain Monte Carlo (MCMC), which is like sending out a hiker who takes random steps. If the hiker stumbles into a better spot, they might stay; if they find a worse one, they might go back. Over time, if the hiker walks long enough, they will spend most of their time in the best spots, giving us a good idea of where the "gold" is hidden.

However, there's a catch: the hiker can get stuck in a local valley, thinking it's the best place, when a much better mountain peak is just over the next ridge. This is called "slow mixing," and it wastes a lot of time. To fix this, scientists often look to a technique called Nesterov acceleration, which is like giving the hiker a skateboard. Instead of just stepping carefully, the hiker builds up speed (momentum) and can coast over small bumps to reach better areas faster. While this "skateboard" trick has been used for smooth, continuous landscapes (like rolling hills), this paper asks a big question: Can we give a skateboard to a hiker who is walking on a jagged, discrete grid of stepping stones, where they can only jump from one stone to another?

The authors of this paper, Bohan Zhou, Shu Liu, Xinzhe Zuo, and Wuchen Li, say "Yes, but it's tricky." They propose a new family of algorithms called "Accelerated MCMC" (aMCMC) designed specifically for these discrete, stepping-stone worlds. Instead of just taking random steps like the classic Metropolis-Hastings algorithm, their method gives the probability distribution a "momentum." Imagine the hiker not just walking, but sliding on a sled that carries them forward even when the terrain tries to stop them. They use a clever mathematical framework involving "Hamiltonian flows" (think of it as the physics of swinging pendulums) to keep the hiker moving toward the best spots without getting stuck.

The paper suggests that this new method is a significant upgrade. In their simulations, they found that their "skateboard" approach converges to the correct answer much faster than the old "walking" method. Specifically, when they tested it on a grid of 25 by 25 stones (representing a complex image or a physical model), their method reached a higher level of accuracy with the same amount of computing time. They also showed that their method can estimate the "normalizing constant" (a hidden number that tells you how likely the whole picture is) with a specific advantage: when implemented as a "jump process" using a swarm of particles, the error shrinks much faster as you add more particles. While the classic method's error shrinks slowly, proportional to the inverse square root of the number of hikers (O(1/√M)), their new method's jump-process implementation achieves an error that shrinks linearly with the inverse of the number of hikers (O(1/M)). This is a massive improvement, though it relies on this specific particle-based implementation rather than being a universal property of the algorithm in every context.

However, the authors are careful to note that this isn't a magic wand that solves everything instantly. Their method requires a bit more setup, like a "warm start" where they let the hiker walk for a while before putting them on the skateboard. They also had to invent a safety mechanism called "restarts" to make sure the hiker doesn't accidentally step off the grid into a place where the math breaks down (where the probability becomes zero). In their tests on images and a famous physics model called the Ising model, the new method consistently outperformed the old one, but it required more computational power per step. The paper concludes that while the theory is solid and the simulations look promising, there is still work to be done to make the method even faster and more robust for the biggest, most complex problems.

Technical Summary: Accelerated Markov Chain Monte Carlo Algorithms on Discrete States

1. Problem Statement

Markov Chain Monte Carlo (MCMC) methods are fundamental for sampling from probability distributions, particularly when normalizing constants are intractable. While the Metropolis-Hastings (MH) algorithm is the standard for discrete state spaces, it often suffers from slow convergence and poor mixing, especially in multimodal distributions.

Recent advances in continuous-state sampling have successfully applied Nesterov's accelerated gradient (NAG) method by interpreting Langevin dynamics as a gradient flow of the Kullback–Leibler (KL) divergence under the Wasserstein-2 metric. However, a direct analog for discrete state spaces has been lacking. The core challenge addressed in this paper is: How can one formulate a Nesterov-type acceleration for sampling on discrete state spaces, and what are the resulting accelerated dynamics involving discrete score functions?

2. Methodology

2.1 Theoretical Framework: Wasserstein Gradient Flow

The authors interpret the reversible Markov chain governed by the forward master equation as a gradient flow of the KL divergence on the probability simplex $\mathcal{P}(V)$ , equipped with a discrete Wasserstein-2 metric.

Metric Structure: The metric is induced by a mobility function $\theta_{ij}(p)$ and a transition rate matrix $Q$ . The associated Onsager response matrix $K(p)$ acts as a preconditioner, defining the geometry of the probability manifold.
Gradient Flow: The standard MH dynamics correspond to a first-order gradient flow: $\dot{p} = -\nabla_p D_{KL}(p\|\pi) K(p)$ .

2.2 Accelerated Dynamics: Damped Hamiltonian Flow

To accelerate convergence, the authors propose a second-order dynamical system derived from Nesterov's acceleration, formulated as a damped Hamiltonian flow on the probability simplex. The system evolves a pair of state variables $(p(t), \psi(t))$ , where $p$ is the probability distribution and $\psi$ is a momentum variable.

The dynamics are governed by:
$\begin{cases} \frac{dp_i}{dt} + \sum_{j \neq i} \pi_i Q_{ij} \theta_{ij}(p) (\psi_j - \psi_i) = 0 \\ \frac{d\psi_i}{dt} + \gamma(t)\psi_i + \frac{1}{2} \sum_{j \neq i} \pi_i Q_{ij} \frac{\partial \theta_{ij}(p)}{\partial p_i} (\psi_i - \psi_j)^2 + \frac{\partial U(p)}{\partial p_i} = 0 \end{cases}$
Here, $U(p)$ is a potential function (e.g., KL divergence or Fisher information), and $\gamma(t)$ is a user-specified damping parameter.

2.3 Specific Algorithmic Variants

The paper explores different choices for the mobility function $\theta_{ij}$ and the potential $U(p)$ , summarized in Table 2 of the paper:

Chi-squared Method: Uses constant mobility ( $\theta_{ij}=1$ ) and $\chi^2$ divergence. This leads to a Telegrapher's equation but requires knowledge of the normalizing constant $Z$ and does not guarantee strict positivity of probabilities without careful handling.
KL Method: Uses the logarithmic mean mobility and KL divergence. While natural, it does not inherently preserve the strict positivity of $p(t)$ .
Log-Fisher Method (Proposed): Uses the logarithmic mean mobility and the relative Fisher information as the potential. This choice is critical as it guarantees the strict positivity of $p(t)$ along the flow and allows for implementation without knowing the normalizing constant $Z$ .
Con-Fisher Method: Uses constant mobility and relative Fisher information, simplifying the momentum equation.

2.4 Numerical Implementation

To implement these continuous dynamics on discrete states, the authors:

Discretization: Use a staggered (symplectic) Euler scheme to discretize the ODEs.
Jump Process: Reformulate the continuity equation into a forward master equation form $\dot{p} = p \bar{Q}^r_\psi$ , where $\bar{Q}^r_\psi$ is a time-inhomogeneous transition rate matrix derived from the momentum difference $(\psi_j - \psi_i)$ .
Interacting Particle System: The algorithm is realized as a system of $M$ interacting particles. The transition rates depend on the empirical distribution and momentum, requiring the simulation of multiple chains (swarm dynamics) rather than a single chain.
Stabilization: The paper introduces "warm starts" (initializing momentum based on a short MH run) and "restart mechanisms" (adding particles to empty states) to handle numerical degeneracies where $p_i(t)$ approaches zero.

3. Key Contributions

Formulation of Discrete Accelerated Dynamics: The paper establishes a rigorous framework for Nesterov acceleration on discrete state spaces by interpreting MH as a gradient flow in a discrete Wasserstein space and lifting it to a Hamiltonian system.
Log-Fisher Algorithm: The authors propose the "log-Fisher" method, which utilizes the relative Fisher information potential. This specific choice ensures the preservation of strict positivity of probabilities and enables sampling without the normalizing constant, addressing a key limitation of other discrete acceleration attempts.
Convergence Analysis:
- The paper proves that the Hamiltonian function is non-increasing.
- Under the assumption of a constant Onsager matrix and geodesic strong convexity of the potential, the authors derive an exponential convergence rate $O(e^{-\sqrt{\lambda}t})$ using Lyapunov analysis, analogous to Nesterov's acceleration in Euclidean space.
- Spectral analysis on the Chi-squared method demonstrates that the accelerated dynamics can achieve a larger spectral gap (faster convergence) than standard MH.
Score Function Approximation: The log-Fisher method specifically provides a novel way to estimate discrete score functions ( $\nabla \log p$ ) without requiring the normalizing constant, utilizing the logarithmic mean structure.

4. Numerical Results

The paper evaluates the proposed methods against standard MH baselines across several regimes:

Small Graphs (Fixed Iterations): On circular and two-loop graphs, the accelerated methods (Chi-squared and log-Fisher) demonstrate faster convergence in $\ell_2$ error compared to MH. Notably, the log-Fisher jump process achieves an error order of $O(1/M)$ due to the interacting particle system (swarm dynamics), whereas the standard MH algorithm in the same context achieves an accuracy of $O(1/\sqrt{M})$ .
Multimodal Sampling (Gaussian Mixture): On a $25 \times 25$ lattice, the log-Fisher method successfully samples from a bimodal distribution. The use of warm starts and adaptive step sizes allows the algorithm to navigate bottlenecks effectively, achieving smaller approximation errors for both the distribution and the normalizing constant.
Large-Scale Benchmarks (Fixed Wall-Clock):
- Image Targets: On $64 \times 64$ lattices derived from images ('rose', 'checkerboard', 'fractal tree'), the log-Fisher method (using multiple interacting chains) achieves lower $\ell_2$ errors and more accurate normalizing constant estimates than single-chain MH within the same computational time.
- Ising Model: On a 1D Ising model ( $L=13$ ), the log-Fisher method again outperforms MH in approximating the target distribution and partition function. The authors note that the multi-chain nature of aMCMC allows for better parallelization, though current implementations face bottlenecks in updating the time-inhomogeneous transition matrix for very large systems.

5. Significance and Claims

The paper claims that the proposed Accelerated MCMC (aMCMC) framework offers a principled extension of Nesterov acceleration to discrete domains. Its primary significance lies in:

Theoretical Unification: Bridging the gap between discrete MCMC, optimal transport (Wasserstein geometry), and accelerated optimization.
Practical Efficiency: Demonstrating that interacting particle systems driven by damped Hamiltonian flows can yield higher-quality samples (lower error) for a given computational budget compared to traditional single-chain MH, particularly in multimodal settings.
Robustness: The log-Fisher variant specifically addresses the challenge of maintaining probability positivity and handling unknown normalizing constants, which are critical for practical applications in statistical physics and graphical models.

The authors modestly note that while the current implementation uses multiple chains (swarm dynamics), future work is needed to derive efficient single-chain approximations and to optimize the choice of damping parameters and step sizes based on the specific geometry of the discrete Wasserstein manifold.