Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo

Abstract

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 $\pi (x)\propto e^{-f(x)}$, where $f$ is $L$-smooth and $m$-strongly-convex, within accuracy $\epsilon$ after $\tilde{O}(\kappa d^2{\ell }^2\log (1/\epsilon ))$ steps for a well-rounded convex body where $\kappa =L/m$ is the condition number of the negative log-density, $d$ is the dimension, $\ell$ is an upper bound on the number of reflections, and $\epsilon$ 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.

arXiv commentThere is an issue with the support of the distribution of Lemma 6 that affects the mixing time bound

References in corpus (17)

• Fairness of Exposure in Rankings
• A Conceptual Introduction to Hamiltonian Monte Carlo
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Statistical mechanics for metabolic networks during steady-state growth
• A General Metric for Riemannian Manifold Hamiltonian Monte Carlo
• Efficient Random-Walk Methods for Approximating Polytope Volume
• Megapixel Size Image Creation using Generative Adversarial Networks
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• An Efficient Sampling Algorithm for Non-smooth Composite Potentials
• On the mixing time of coordinate Hit-and-Run
• Geometrically Tempered Hamiltonian Monte Carlo
• Practical volume computation of structured convex bodies, and an application to modeling portfolio dependencies and financial crises
• Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
• Roll-back Hamiltonian Monte Carlo
• A simplicial polytope that maximizes the isotropic constant must be a simplex
• Truncated Linear Regression in High Dimensions