In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies
This work addresses a fundamental computational geometry problem with applications in optimization and statistics, representing a significant advancement rather than an incremental improvement.
The paper tackles the problem of uniformly sampling high-dimensional convex bodies by introducing a new random walk algorithm that achieves state-of-the-art runtime complexity with stronger guarantees on output quality, such as in Rényi divergence, which implies improvements in total variation, Wasserstein distance, KL divergence, and chi-squared divergence.
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, $χ^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 target distribution.