# Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo

arXiv: https://arxiv.org/abs/2102.13068 · HTML: https://mlsanity.com/paper/2102.13068/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 34 of its 117 references that are in the map.
- First posted on arXiv 25 Feb 2021.

## Builds on (most cited first, 30 of 34)

- [Large Scale GAN Training for High Fidelity Natural Image Synthesis](https://mlsanity.com/paper/1809.11096/) (2018)
- [Pyro: Deep Universal Probabilistic Programming](https://mlsanity.com/paper/1810.09538/) (2018)
- [A Conceptual Introduction to Hamiltonian Monte Carlo](https://mlsanity.com/paper/1701.02434/) (2017)
- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [Sampling from a log-concave distribution with Projected Langevin Monte Carlo](https://mlsanity.com/paper/1507.02564/) (2015)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Proximal Markov chain Monte Carlo algorithms](https://mlsanity.com/paper/1306.0187/) (2013)
- [Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo](https://mlsanity.com/paper/1705.08964/) (2017)
- [Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond](https://mlsanity.com/paper/1906.07868/) (2019)
- [Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation](https://mlsanity.com/paper/1710.06261/) (2017)
- [Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions](https://mlsanity.com/paper/1905.02313/) (2019)
- [Megapixel Size Image Creation using Generative Adversarial Networks](https://mlsanity.com/paper/1706.00082/) (2017)
- [Geometric integrators and the Hamiltonian Monte Carlo method](https://mlsanity.com/paper/1711.05337/) (2017)
- [Computationally and Statistically Efficient Truncated Regression](https://mlsanity.com/paper/2010.12000/) (2020)
- [Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo](https://mlsanity.com/paper/2002.04121/) (2020)
- [An Efficient Sampling Algorithm for Non-smooth Composite Potentials](https://mlsanity.com/paper/1910.00551/) (2019)
- [Convex Relaxations for Permutation Problems](https://mlsanity.com/paper/1306.4805/) (2013)
- [Truncated Linear Regression in High Dimensions](https://mlsanity.com/paper/2007.14539/) (2020)
- [Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast](https://mlsanity.com/paper/2009.11338/) (2020)
- [Hamiltonian Monte Carlo with Energy Conserving Subsampling](https://mlsanity.com/paper/1708.00955/) (2017)
- [Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities](https://mlsanity.com/paper/1812.06243/) (2018)
- [Composite Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2006.05976/) (2020)
- [A Cubic Algorithm for Computing Gaussian Volume](https://mlsanity.com/paper/1306.5829/) (2013)
- [Gaussian Cooling and O*(n^3) Algorithms for Volume and Gaussian Volume](https://mlsanity.com/paper/1409.6011/) (2014)
- [On the mixing time of coordinate Hit-and-Run](https://mlsanity.com/paper/2009.14004/) (2020)
- [Sorting Network Relaxations for Vector Permutation Problems](https://mlsanity.com/paper/1407.6609/) (2014)
- [Optimal Approximate Polytope Membership](https://mlsanity.com/paper/1612.01696/) (2016)

## Abstract (arXiv)

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.