Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo

We introduce Reflective Hamiltonian Monte Carlo (ReHMC), an HMC-based algorithm, to sample from a log-concave distribution restricted to a convex body. We prove that, starting from a warm start, the walk mixes to a log-concave target distribution π(x) propto e-f(x), where f is L-smooth and m-strongly-convex, within accuracy varepsilon after widetilde O(kappa d2 ℓ2 log (1 / varepsilon)) steps for a well-rounded convex body where kappa = L / m is the condition number of the negative log-density, d is the dimension, ℓ is an upper bound on the number of reflections, and varepsilon is the accuracy parameter. We also developed an efficient open source implementation of ReHMC and we performed an experimental study on various high-dimensional data-sets. The experiments suggest that ReHMC outperfroms Hit-and-Run and Coordinate-Hit-and-Run regarding the time it needs to produce an independent sample and introduces practical truncated sampling in thousands of dimensions.