A Langevin-like Sampler for Discrete Distributions
This provides a scalable solution for sampling in high-dimensional discrete spaces, impacting fields like machine learning and statistical physics, though it is incremental as it builds on gradient-based sampling ideas.
The authors tackled the problem of sampling from complex high-dimensional discrete distributions by proposing the discrete Langevin proposal (DLP), a gradient-based method that updates all coordinates in parallel, and demonstrated its efficiency with zero asymptotic bias for log-quadratic distributions and strong performance across various tasks.
We propose discrete Langevin proposal (DLP), a simple and scalable gradient-based proposal for sampling complex high-dimensional discrete distributions. In contrast to Gibbs sampling-based methods, DLP is able to update all coordinates in parallel in a single step and the magnitude of changes is controlled by a stepsize. This allows a cheap and efficient exploration in the space of high-dimensional and strongly correlated variables. We prove the efficiency of DLP by showing that the asymptotic bias of its stationary distribution is zero for log-quadratic distributions, and is small for distributions that are close to being log-quadratic. With DLP, we develop several variants of sampling algorithms, including unadjusted, Metropolis-adjusted, stochastic and preconditioned versions. DLP outperforms many popular alternatives on a wide variety of tasks, including Ising models, restricted Boltzmann machines, deep energy-based models, binary neural networks and language generation.