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, 𝒲2 , KL, χ2${\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 target distribution.