Constrained high-dimensional models are a mainstay of modern data science. In this talk, we demonstrate for the first time that convex sets and non-smooth log-concave distributions in very high dimension, upwards of 100,000 and up to a million, can be sampled efficiently. Our main tool is a variant of Hamiltonian Monte Carlo, a Markov Chain method whose steps are curves that preserve the Hamiltonian of the corresponding system. Combining this with interior point methods, we find that on a benchmark of data sets, the method outperforms existing techniques by multiple orders of magnitude.

Joint work with Ruoqi Shen, and Santosh Vemapala.