Accelerated Markov Chain Monte Carlo Algorithms on Discrete States
This work addresses the bottleneck of computational speed in discrete-state MCMC sampling, which is incremental as it builds on existing methods like Metropolis-Hastings.
The authors tackled the problem of slow sampling in Markov Chain Monte Carlo (MCMC) for discrete states by proposing an accelerated algorithm based on Nesterov's method and damped Hamiltonian flows, resulting in improved efficiency demonstrated through numerical examples on Gaussian mixtures and hypercube distributions.
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.