Fall 2020

Work in Progress: a Structured Sampling Package

Nov. 3, 2020 11:00 am12:00 pm

Add to Calendar


Yin Tat Lee (University of Washington)


Zoom link will be sent out to program participants.

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.