Accelerated Markov Chain Monte Carlo Algorithms on Discrete States

arXiv:2505.12599 · math.OC, cs.LG, stat.CO · Submitted 2026-08-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Accelerated Markov Chain Monte Carlo Algorithms on Discrete States".

Jane: The paper was written by Bohan Zhou, Shu Liu, Xinzhe Zuo and Wuchen Li from University of California, Santa Barbara and Florida State University and University of California, Los Angeles and University of South Carolina.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the show, everybody. Today we’re digging into a brand new paper on arXiv called “Accelerated Markov Chain Monte Carlo Algorithms on Discrete States.” Jane, I have to say, the title alone got me excited, because MCMC is one of those workhorse tools that everyone uses but rarely thinks about improving.

Jane: Absolutely, Tom. And the authors here — Bohan Zhou, Shu Liu, Xinzhe Zuo, and Wuchen Li — they’ve taken something really classical and asked a bold question. Can we make the Metropolis-Hastings algorithm, which is the backbone of so much statistical sampling, run faster using ideas from accelerated optimization?

Tom: Right, and that’s the part that grabbed me. Normally when you think about speeding up MCMC, you think about better proposals or smarter mixing. But these folks went back to the math and realized that Metropolis-Hastings is actually a gradient descent method in disguise, on a space of probability distributions.

Jane: Exactly. And once you see it that way, you can borrow a trick from optimization called Nesterov acceleration. That’s the same trick that makes accelerated gradient methods converge faster than plain gradient descent. So they built a new class of algorithms that applies that momentum idea to discrete state spaces.

Tom: And that’s huge, because a lot of the recent acceleration work has been for continuous spaces — like Langevin dynamics on manifolds. But so many real problems live on discrete structures: spin systems in physics, graphical models in machine learning, combinatorial counting problems. Those all need discrete sampling.

Jane: Right, and the paper doesn’t just stop at theory. They actually implement these accelerated dynamics and test them on things like Gaussian mixtures on lattices and Ising models. So we’re talking about real numerical evidence that the acceleration works in practice.

Tom: And the results are pretty striking. In some of their fixed-iteration experiments, the accelerated method gets to the target distribution much faster than the classical Metropolis-Hastings, and it even achieves higher accuracy with the same number of particles.

Jane: That’s the part I find most exciting, Tom. Because it means this isn’t just a theoretical curiosity. It’s a practical upgrade to a tool that’s used in physics, chemistry, finance, and machine learning. If you can sample faster and more accurately, you can solve bigger problems.

Tom: And that’s exactly what we’re going to dig into over the next few segments. We’ll talk about the core ideas, the improvements they propose, and what this could mean for the field.

Jane: So stay with us, because this paper has some real depth to it.

Summary: Tom: So we’re back with “Accelerated Markov Chain Monte Carlo Algorithms on Discrete States.” Jane, let’s get into the actual summary of what these authors did. Because the title is one thing, but the machinery underneath is pretty clever.

Jane: It really is, Tom. So the starting point is the Metropolis-Hastings algorithm, which is the classic way to sample from a distribution when you only know it up to a constant. The paper shows that the evolution of the probability distribution under Metropolis-Hastings can be viewed as a gradient flow of something called the Kullback-Leibler divergence, on a discrete Wasserstein space.

Tom: And that’s the key insight, right? Once you have that gradient flow structure, you can apply Nesterov acceleration, which is the momentum-based trick from optimization. The result is a damped Hamiltonian flow on the probability simplex.

Jane: Exactly. And the paper gives a whole family of these accelerated algorithms, depending on how you choose the potential function and the mobility. They list several examples in a table — chi-squared, KL divergence, log-Fisher, and con-Fisher. Each one has different properties.

Tom: And the log-Fisher one seems to be the star of the show. It uses the relative Fisher information as the potential, and it has this nice property that the probability distribution stays strictly positive throughout the dynamics. That’s not guaranteed for the KL divergence version.

Jane: Right, and that positivity matters a lot when you want to interpret the dynamics as a jump process for particles. If a probability hits zero, you can’t define the transition rates anymore. So the log-Fisher method is the one they focus on for the numerical experiments.

Tom: And those experiments are pretty convincing. On small graphs, they show the accelerated method converges faster than Metropolis-Hastings in terms of iterations. On a two-loop graph with a bottleneck, the log-Fisher method gets to the target distribution much faster.

Jane: And then they scale up. They test on a twenty-five by twenty-five lattice with a Gaussian mixture target, which is a classic multimodal problem. That’s where Metropolis-Hastings often gets stuck in one mode. The accelerated method handles it better.

Tom: And they even test on image-derived targets and the Ising model. In the wall-clock comparisons, the log-Fisher method achieves smaller errors in the empirical distribution and the normalizing constant than a single-chain Metropolis-Hastings benchmark.

Jane: And that’s the part that really matters for practitioners, Tom. Because MCMC is used everywhere, and if you can get better accuracy in the same amount of time, that’s a direct win.

Tom: So the summary is: they took a classical algorithm, found its hidden gradient structure, applied acceleration, and showed it works in practice. That’s a solid contribution.

Jane: And it opens the door for more work on discrete-state sampling, which has been a bit of a blind spot compared to continuous-state methods.

Improvements: Tom: We’re back with “Accelerated Markov Chain Monte Carlo Algorithms on Discrete States.” And now we need to talk about the improvements this paper suggests. Because it’s not just about making one algorithm faster — it’s about changing how we think about discrete sampling.

Jane: Right, Tom. And one of the biggest improvements is the way they handle the score function on discrete spaces. In continuous spaces, you have gradients and you can use Langevin dynamics. On discrete spaces, that’s much trickier. This paper uses a logarithmic mean and a discrete score function that doesn’t require knowing the normalizing constant.

Tom: And that’s a big deal. The normalizing constant is often the whole reason you’re using MCMC in the first place. If your accelerated method needs it, that defeats the purpose. So the fact that the log-Fisher method works without it is a major practical advantage.

Jane: Exactly. And there’s another improvement I really like: the positivity guarantee. The paper proves that under certain conditions on the potential function, the probability distribution stays strictly positive along the dynamics. That’s not just a nice mathematical property — it makes the numerical implementation much more stable.

Tom: And they back that up with a restart mechanism. If a particle count hits zero during the jump process, they add a particle and reinitialize the momentum. It’s a practical safeguard that keeps the algorithm running smoothly.

Jane: And then there’s the damping parameter. The paper shows that for the chi-squared method, you can choose the damping based on the spectral gap of the transition rate matrix. That gives you an explicit convergence rate improvement — the accelerated method converges faster than the classical one.

Tom: And for the log-Fisher method, they use a Rayleigh quotient to estimate the damping parameter. It’s a bit more involved, but it works in practice. And they show that the Hamiltonian — the energy of the system — decreases along the dynamics, which is a nice sanity check.

Jane: So the improvements here are really about robustness and practicality. They’re not just saying “here’s a faster algorithm.” They’re saying “here’s a faster algorithm that you can actually implement without knowing the normalizing constant, that keeps probabilities positive, and that has a principled way to choose the damping.”

Tom: And the numerical results back that up. In the wall-clock benchmarks, the log-Fisher method achieves smaller errors than Metropolis-Hastings, even when you account for the fact that the accelerated method has more overhead per iteration.

Jane: Right. And that’s the kind of improvement that could actually change how people do sampling in practice. Not just in academia, but in industry applications like Bayesian inference, computational physics, and even machine learning.

Tom: So the improvements here are real, and they’re meaningful. And I think the next step is to see how this scales to even bigger problems.

Conclusion: Tom: And that brings us to the end of our discussion on “Accelerated Markov Chain Monte Carlo Algorithms on Discrete States.” Jane, let’s wrap this up for our listeners.

Jane: Let’s do it, Tom. So this paper takes the classical Metropolis-Hastings algorithm and gives it a serious upgrade. By recognizing that MCMC is a gradient flow on the space of probability distributions, the authors were able to apply Nesterov acceleration and build a family of accelerated sampling algorithms.

Tom: And the star of the show is the log-Fisher method, which uses the relative Fisher information and works without knowing the normalizing constant. It keeps probabilities positive, it converges faster, and it achieves higher accuracy in practice.

Jane: And the numerical experiments back that up — from small graphs to image-derived targets to the Ising model. The accelerated method consistently outperforms the classical benchmark.

Tom: So what does this mean for the world? Well, MCMC is used in so many fields — physics, chemistry, finance, machine learning. If you can sample faster and more accurately, you can solve bigger problems. That’s a real impact.

Jane: And it also opens the door for more research. The authors mention future work on better damping parameters, GPU implementations, and single-chain approximations. So this is just the beginning.

Tom: Absolutely. And with that, we’re going to say goodbye to this paper and get ready for the next one. Thanks for joining us, and we’ll see you next time.

Bohan Zhou, Shu Liu, Xinzhe Zuo, Wuchen Li

University of California, Santa Barbara · Florida State University · University of California, Los Angeles · University of South Carolina

math.OC, cs.LG, stat.CO

Submitted: 2026-08-12

Code: https://github.com/silentmovie/AMCMC

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 79/100

Terminology

Summary

Summary

This paper proposes a class of discrete-state sampling algorithms based on Nesterov’s accelerated gradient method, extending the classical Metropolis-Hastings (MH) algorithm. The authors establish that the evolution of the probability distribution over discrete states 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, defined on a probability simplex equipped with a mobility-dependent discrete Wasserstein-2 metric. This motivates the study of a momentum-based acceleration framework using damped Hamiltonian flows on the simplex, whose stationary distribution matches the discrete target distribution.

The paper begins by reviewing the classical MCMC with the MH update, the gradient flow formulation of the forward master equation, and gradient and accelerated flows in Euclidean space. The authors then introduce a class of accelerated MCMC (aMCMC) sampling algorithms on discrete-state spaces, with particular instances listed in Table 2. The proposed dynamics evolve according to a damped Hamiltonian system:


dpi(t)/dt + Σ j≠i πi Qij θij(p(t))(ψj(t) − ψi(t)) = 0,

dψi(t)/dt + γ(t)ψi(t) + (1/2)Σ j≠i πi Qij (∂θij(p(t))/∂pi)(ψi(t) − ψj(t))2 + ∂I(p(t)∥π)/∂pi = 0.

The first equation is a discrete-state continuity equation describing the evolution of the probability function p. The second is a discrete Hamilton–Jacobi equation governing the dynamics of the momentum variable ψ, incorporating dissipative effects through γ(t)ψi and information-theoretic feedback via ∂I(p∥π)/∂pi. Here, γ(t) is a user-specified damping parameter, and (θij(p(t))) is a mobility weight matrix that may depend on p(t). A particularly important choice is the logarithmic mean or KL divergence mean, given by:


θij(p) = (pi/πi − pj/πj) / (log(pi/πi) − log(pj/πj)) = (πj pi − πi pj) / (πi pj log(πj pi / πi pj)).

The proposed aMCMC dynamics guarantee the non-increasing behavior of its associated Hamiltonian function on a simplex set, defined as H(p, ψ) = (1/2)ψK(p)ψT + I(p∥π), and the strict positivity of p(t). For numerical implementation, a staggered scheme is employed to discretize the dynamics in time, and an interacting particle system on discrete states is introduced with transition rates derived from a positive/negative-part decomposition of the gradient term ψj − ψi.

The paper presents several specific methods, summarized in Table 2: Chi-squared, KL, log-Fisher, and con-Fisher. The Chi-squared method uses uniform activation (θij = 1) and the χ2 divergence as potential. The KL method uses the logarithmic mean and KL divergence. The log-Fisher method uses the logarithmic mean and the relative Fisher information I(p∥π) = (1/4)Σ i,j=1 n ωij (log(pi/πi) − log(pj/πj))(pi/πi − pj/πj). The con-Fisher method uses constant activation and the relative Fisher information with squared log-ratios.

Key properties of the methods are discussed. Regarding the normalizing constant, the KL and log-Fisher methods have Onsager response matrices independent of Z, while Chi-squared and con-Fisher methods depend on Z. Regarding positivity, Theorem 5 provides a general condition on the potential function U(p) to ensure pi(t) remains away from zero, satisfied by log-Fisher and con-Fisher methods. Theorem 6 establishes exponential convergence of the state variables with a constant damping parameter γ(t) = 2√λ for geodesically λ-strongly convex potentials under a flat metric. Theorem 8 shows that with an appropriate damping parameter, the largest negative eigenvalue of the accelerated system matrix L is smaller than the spectral gap of the original Q-matrix, demonstrating accelerated convergence.

Numerical experiments evaluate the proposed methods in several regimes. Fixed-iteration experiments on small graphs (circular graph C3 and two-loop graph) validate the accelerated transient behavior predicted by the continuous dynamics, showing faster convergence in l2 error than MH. A multimodal lattice example (25×25 lattice sampling a Gaussian mixture) illustrates the practical use of warm starts, adaptive time stepping, and restarts. Notably, the incorporation of score functions in the aMCMC algorithm yields a higher empirical accuracy with respect to target distributions, with error of order O(1/M), where M denotes the number of swarm particles, a substantial improvement over the O(1/√M) accuracy of the MH algorithm.

Under fixed wall-clock budgets, experiments on image-derived lattice targets ('rose', 'checkerboard', 'fractal tree') and on a one-dimensional Ising model show that the multi-chain log-Fisher achieves smaller l2 error for empirical distributional and more accurate estimation for the partition function than the single-chain MH benchmark, using aggregated-sample and effective-sample protocols. The paper concludes that the log-Fisher method is able to produce the same amount of samples with higher quality for Monte-Carlo estimation within the same computational time.

Improvements for AI systems

Based on the scientific paper, here are the specific improvements that can be made to AI systems and what the improved system can do:

Improvement: Implement the log-Fisher method (Section 3.3) as a drop-in replacement for Metropolis-Hastings in discrete-state MCMC pipelines. This uses damped Hamiltonian dynamics with relative Fisher information as potential, ensuring strict positivity of probabilities without requiring the normalizing constant.

What the improved system can do:

  • Sample from discrete distributions (e.g., Ising models, graphical models, lattice-based targets) with O(1/M) empirical accuracy instead of O(1/√M) for MH

  • Maintain strict positivity of probability estimates even when target distributions have near-zero mass regions

  • Operate without knowledge of the normalizing constant Z, making it suitable for Bayesian posteriors and energy-based models

Improvement: Integrate the momentum-based acceleration framework (Equation 19) with adaptive damping parameter selection based on the Rayleigh quotient of the con-Fisher approximation (Section 4.4.2).

Improvement: Implement the interacting particle system (Algorithm 3) with warm-start initialization from MH and restart mechanisms for particle depletion.

Improvement: Use the logarithmic mean activation function (Equation 2) to estimate discrete score functions ∇log p = [log(p j/p i)] without computing Z.

Improvement: Implement the local backtracking scheme (lines 19-23 of Algorithm 3) that reduces step size by factor 10 whenever the transition matrix becomes invalid.

Improvement: Use the aggregated-sample and effective-sample protocols (Section 6.3) to fairly compare and deploy the accelerated sampler under real-time constraints.

  1. Bayesian Inference Acceleration: Sample from posterior distributions over discrete parameter spaces (e.g., model selection, change-point detection) with 10-100× fewer iterations to reach the same accuracy.

  2. Statistical Physics Simulation: Simulate Ising models and spin systems with critical temperature behavior captured more accurately, enabling better estimation of phase transitions.

  3. Discrete Diffusion Models: Train and sample from discrete diffusion models (e.g., for text, graphs, protein sequences) with improved score estimation and faster mixing.

  4. Combinatorial Optimization: Solve maximum likelihood estimation on graphical models with faster convergence to stationary distribution, reducing pseudo-convergence issues in multimodal landscapes.

  5. Real-Time Monte Carlo Estimation: Deploy in applications requiring rapid estimation (e.g., risk assessment, option pricing) where wall-clock time is critical, achieving better accuracy per second than standard MCMC.

Abstract

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.

Sources

Related papers