Sam Power

Accelerated Sampling on Discrete Spaces with Non-Reversible Markov Jump Processes

In Bayesian inference problems and elsewhere, Markov Chain Monte Carlo (MCMC) algorithms are an indispensable tool for sampling from complex probability distributions. On continuous state-spaces, there has been a great deal of successful work on how to construct efficient MCMC dynamics which can converge quickly, under very general circumstances. Much of this success has stemmed from identifying continuous-time dynamical processes (ODEs, SDEs, PDMPs) which admit the desired invariant measure, and then discretising those processes to form tractable discrete-time chains. This approach has apparently seen less use in the setting of discrete spaces.

In this work, we aim to bridge this gap by identifying `canonical’ Markov processes (both reversible and non-reversible) on structured discrete spaces which admit a given invariant measure, and then use them to derive new algorithms for efficient sampling on discrete spaces. The algorithms are parameter-free (no tuning is required) and can be simulated directly in continuous time, easily and without discretisation error. We provide theoretical results supporting the use of non-reversible dynamics, and a range of numerical experiments demonstrate the practial benefits of our algorithms.

This is joint work with Jacob Vorstrup Goldman (Cambridge).