Efficient Sampling by Algorithmic Diffusion

We present a new random walk for uniformly sampling high-dimensional convex bodies and arbitrary logconcave distributions. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than previously known, namely in Rényi divergence. The proof departs from known approaches for polytime algorithms for the problem --- we utilize a stochastic diffusion perspective to show contraction to the target distribution with the rate of convergence determined by functional isoperimetric constants of the stationary density. The stronger guarantees lead to improvements in efficiency for rounding and integrating general logconcave functions. The talk will be self-contained and run in discrete time.

Based on joint work with Yunbum Kook.

About Santosh Vempala

Santosh Vempala is the Frederick Storey II Professor in the School of Computer Science at Georgia Tech, with courtesy appointments in Mathematics and Industrial and Systems Engineering (ISyE). He served as the founding director of the Algorithms and Randomness Center (2006-2011), initiated the Computing-for-Good program, and is currently the director of GT's interdisciplinary ACO PhD program. His research interests are broadly in the theory of algorithms, with emphasis on tools for high-dimensional sampling, learning and optimization.  He graduated from CMU in 1997 advised by Avrim Blum and was on the MIT Mathematics faculty until 2007. He gets rather excited when a phenomenon that appears complex from one perspective turns out to be simple from another. In recent years, he has been trying to understand the limits of sampling and optimization algorithms, robustness in learning, and building a computational theory of brain and cognition.