Skip to yearly menu bar Skip to main content


Spotlight Poster

In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies

Yunbum Kook · Santosh Vempala · Matthew Zhang

[ ]
Fri 13 Dec 11 a.m. PST — 2 p.m. PST

Abstract: We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than previously known, namely in Rényi divergence (which implies TV, $\mathcal{W}_2$, KL, $\chi^2$). 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.

Live content is unavailable. Log in and register to view live content