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

View a PDF of the paper titled In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies, by Yunbum Kook and 2 other authors

View PDF
HTML (experimental)

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.