Discontinuous Hamiltonian Monte Carlo for discrete parameters and discontinuous likelihoods

Abstract: “Hamiltonian Monte Carlo has emerged as a standard tool for posterior computation. In this article we present an extension that can efficiently explore target distributions with discontinuous densities. Our extension in particular enables efficient sampling from ordinal parameters through the embedding of probability mass functions into continuous spaces. We motivate our approach through a theory of discontinuous Hamiltonian dynamics and develop a corresponding numerical solver. The proposed solver is the first of its kind, with a remarkable ability to exactly preserve the Hamiltonian. We apply our algorithm to challenging posterior inference problems to demonstrate its wide applicability and competitive performance.”

Maybe this discussion would be helpful.

Maybe also @betanalpha could be asked to provide an up-to-date account on the state of the art when it comes to HMC for discrete spaces (or point to something he’s written).

This was a particularly bad paper with fatal methodological flaws that had been shopped around journals for a long time. I’m not sure the current state of the paper but I also can’t review it behind a paywall.

Discontinuities in the target density function cause problems for the numerical integration in Hamiltonian Monte Carlo. In order to properly account for them the integrator needs to “jump” whenever it passes over any discontinuity, which requires some method for identifying when an integrator has passed a discontinuity. Numerical integrators, however, work with discrete steps and so don’t have the resolution to probe for discontinuities that might be passed with each step.

Fully discrete spaces are another matter. Discrete spaces simply don’t have the differential structure needed to guide Hamiltonian Monte Carlo, no matter how you manipulate them. A common strategy is to try to embed or “relax” a discrete distribution into a continuous one, but the differential structure of that continuous output is determined not by the original discrete space but rather the embedding/relaxation method. In other words any resulting Hamiltonian Monte Carlo implementation is just following the structure of the transformation, not the actual distribution one is trying to explore.


I realize this is a somewhat old thread. Since I happened to come across this thread for the first time, though, I wanted to respond to @betanalpha’s unfair critique of our work.

with fatal methodological flaws

Besides the theory developed in our paper, the correctness of our method is empirically verified in this Jupyter notebook. Also available in the github repo is the code to reproduce the rest of the results in our paper. Our method has further been independently validated by other research groups, for example in Zhou et. al. (2019).

I also can’t review it behind a paywall.

The latest version is publicly available on arXiv:
[1705.08510] Discontinuous Hamiltonian Monte Carlo for discrete parameters and discontinuous likelihoods.