Date: September 22, 2025
Time: 3:45-5 p.m.
Location: Computing and Information Science Building, Room 450 or via Zoom
Speaker: Santosh Vempala
Title: Efficient Sampling by Algorithmic Diffusion
Abstract: We present a new random walk for sampling high-dimensional convex bodies and arbitrary logconcave distributions, specified only by evaluation oracles. It achieves state-of-the-art runtime complexity with stronger guarantees on the output distribution than previously known (KL and Rényi divergences). The proof departs from known approaches for polytime algorithms for the problem --- we utilize a continuous-time stochastic diffusion perspective to show convergence to the target distribution with the rate bounded by functional isoperimetric constants of the target density. The stronger output guarantees lead to faster algorithms for rounding and integrating general logconcave functions as well as streamlined error analysis. The talk will be self-contained and run in discrete time.
Based on joint work with Yunbum Kook.