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

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, , KL, ). 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.