Auxiliary-variable Exact Hamiltonian Monte Carlo Samplers for Binary Distributions
We present a new approach to sample from generic binary distributions, based on an exact Hamiltonian Monte Carlo algorithm applied to a piecewise continuous augmentation of the binary distribution of interest. An extension of this idea to distributions over mixtures of binary and possibly-truncated Gaussian or exponential variables allows us to sample from posteriors of linear and probit regression models with spike-and-slab priors and truncated parameters. We illustrate the advantages of these algorithms in several examples in which they outperform the Metropolis or Gibbs samplers.
This paper describes a method for relaxing discrete 
      sampling problems into continuous ones that are suitable for Hamiltonian 
      Monte Carlo. The idea is to divide the continuous space into orthants, 
      creating a one-to-one correspondence between the possible values of the 
      discrete space and orthants in the continuous space. The complication that 
      arises is that the relaxation has noncontinuous jumps at the boundaries 
      between orthants, which the authors address by augmenting Hamiltonian 
      dynamics to allow the sample to either reflect off or jump on top of 
      cliffs, depending on its energy. A nice effect of this construction is 
      within the orthant, the problem is a constrained quadratic, for which 
      recent work has pointed out that the dynamics can be computed exactly, 
      eliminating the need for numerical integration. This is a creative 
      and nice application of recent work on exact Hamiltonian samplers for 
      log-quadratic densities. Spike-and-slab models are a great application of 
      this technique, and an important model, and the results show that this 
      method has promise as an effective sampling algorithm for this model. 
      I have a question about the validity of the method. It's clear to 
      me that with energy barriers added, the dynamics is reversible and 
      preserves the value of the Hamiltonian. I cannot immediately see why the 
      dynamics conserves volume. Obviously it does so away from the boundaries, 
      but it is less clear to me why the dynamics conserves volume at the energy 
      barriers. Could the authors please expand on this? Assuming that 
      the method is valid, it's an interesting paper that merits publication. 
      Minor comments: * lines 108ff: A possible comment that 
      might help the reader's intuition: The equation (9) has a solution iff the 
      right hand side is positive. So if Delta is positive, meaning that the new 
      discrete state would have higher probability than the current one, then 
      the coordinate always crosses the boundary, i.e., we always move to the 
      new discrete state. In the physical analogy of HMC, the dynamics reaches 
      the top of a cliff, so it always falls downward. On the other hand, if 
      Delta is negative, then the new discrete state has lower probability, so 
      we only switch to it if the sampler has enough energy, i.e., if q^2_j 
      (t_j^-)/2 > -Delta. ========== AFTER REBUTTAL 1. 
      Thanks for your explanation about the boundary effects. 2. Perhaps 
      a bit self-indulgent, re-reading my review, I thought of a perhaps better 
      way to express my intuition at the end. "On the other hand, if 
      Delta is negative, then the new discrete state has lower probability. 
      Because the sampler has to be reversible, we're only allowed to roll up 
      the cliff if there exists a reverse trajectory that could have been 
      generated by the dynamics. In the reverse trajectory, the particle gains 
      energy when it falls down the cliff, so this creates a lower bound on the 
      energy of particles that jump up the cliff." Feel free to not use 
      this if you feel it doesn't help.