Discontinuous Hamiltonian Monte Carlo for sampling discrete parameters

Hamiltonian Monte Carlo (HMC) is a powerful sampling algorithm employed by several probabilistic programming languages. Its fully automatic implementations have made HMC a standard tool for applied Bayesian modeling. While its performance is often superior to alternatives under a wide range of models, one weakness of HMC is its inability to handle discrete parameters. In this article, we present discontinuous HMC, an extension that can efficiently explore discrete parameter spaces as well as continuous ones. The proposed algorithm is based on two key ideas: embedding of discrete parameters into a continuous space and simulation of Hamiltonian dynamics on a piecewise smooth density function. The latter idea has been explored under special cases in the literature, but the extensions introduced here are critical in turning the idea into a general and practical sampling algorithm. Discontinuous HMC is guaranteed to outperform a Metropolis-within-Gibbs algorithm as the two algorithms coincide under a specific (and sub-optimal) implementation of discontinuous HMC. It is additionally shown that the dynamics underlying discontinuous HMC have a remarkable similarity to a zig-zag process, a continuous-time Markov process behind a state-of-the-art non-reversible rejection-free sampler. We apply our algorithm to challenging posterior inference problems to demonstrate its wide applicability and superior performance.