Accelerated Sampling on Discrete Spaces with Non-Reversible Markov Processes
arXiv:1912.04681
Abstract
We consider the task of MCMC sampling from a distribution defined on a discrete space. Building on recent insights provided in [Zan19], we devise a class of efficient continuous-time, non-reversible algorithms which make active use of the structure of the underlying space. Particular emphasis is placed on how symmetries and other group-theoretic notions can be used to improve exploration of the space. We test our algorithms on a range of examples from statistics, computational physics, machine learning, and cryptography, which show improvement on alternative algorithms. We provide practical recommendations on how to design and implement these algorithms, and close with remarks on the outlook for both discrete sampling and continuous-time Monte Carlo more broadly.
31 pages, 8 figures, code available at https://github.com/jvorstrupgoldman/tabu_dc_dzz
References in corpus (8)
- Determinantal point processes for machine learning
- Irreversible Monte Carlo Algorithms for Efficient Sampling
- Piecewise-Deterministic Markov Chain Monte Carlo
- Faster Monte Carlo Simulations at Low Temperatures. The Waiting Time Method
- Unbiased Markov chain Monte Carlo with couplings
- A discrete log-Sobolev inequality under a Bakry-Emery type condition
- The Coordinate Sampler: A Non-Reversible Gibbs-like MCMC Sampler
- A method to reduce the rejection rate in Monte Carlo Markov Chains
Cited by in corpus (6)
- Analysis of Stochastic Gradient Descent in Continuous Time
- The reproducing Stein kernel approach for post-hoc corrected sampling
- An asymptotic Peskun ordering and its application to lifted samplers
- Sampling algorithms in statistical physics: a guide for statistics and machine learning
- Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC
- Kinetic samplers for neural quantum states