Santosh Vempala - Gibbs Sampling for Convex Bodies and an L_0 Isoperimetric Inequality
Presenter
February 10, 2022
Abstract
Recorded 10 February 2022. Santosh Vempala of Georgia Institute of Technology, Computer Science, presents "Gibbs Sampling for Convex Bodies and an L_0 Isoperimetric Inequality" at IPAM's Calculus of Variations in Probability and Geometry Workshop.
Abstract: Gibbs sampling, also known as Coordinate Hit-and-Run (CHAR), is a Markov chain for sampling from high-dimensional distributions. In each step, the algorithm selects a random coordinate and resamples that coordinate from the distribution induced by fixing all the other coordinates. While this algorithm has become widely used over the past half-century, guarantees of efficient convergence have been elusive. We show that CHAR for sampling from a convex body K in R^n mixes in poly(n, R/r) steps where K contains a ball of radius r and R is the average distance of a point of K from its centroid. We also give a lower bound on the conductance of CHAR, showing that it is strictly worse than Hit-and-Run or the Ball Walk in the worst case.
This is joint work with Aditi Laddha.