Math Seminar: The Manifold Joys of Sampling
Dr. Santosh Vempala, Frederick G. Storey Chair of Computing and Professor – College of Computing, Georgia Tech
March 4th, 2022
11:00 AM
BSB 132
Abstract: Sampling high-dimensional sets and distributions is a fundamental problem with many applications. The state-of-the-art is that arbitrary logconcave densities can be sampled to arbitrarily small error in time polynomial in the dimension using simple Markov chains based on Euclidean geometry. In this talk, we describe algorithms that exploit varying local geometry and can be viewed as sampling Riemannian manifolds. This approach will let us derive more efficient algorithms for some cases of interest, as well as analyze affine-invariant versions of Euclidean algorithms, such as the Dikin walk, Hamiltonian Monte-Carlo and Riemannian Langevin.