[2405.01425] In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies

Computer Science > Data Structures and Algorithms arXiv:2405.01425 (cs) [Submitted on 2 May 2024 (v1), last revised 20 Mar 2026 (this version, v4)] Title:In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies Authors:Yunbum Kook, Santosh S. Vempala, Matthew S. Zhang 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 target distribution. Comments: Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML) Cite as: arXiv:2405.01425 [cs.DS]   (or arXiv:2405.01425v4 [cs.DS] for this version)   https://doi.org/10.48550/arXiv.2405.01425 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Yunbum Kook [view email] [v1] Thu, 2 May 2024 16:15:46 UTC (148 KB) [v2] Wed, 20 Nov 2024 19:01:42 UTC (139 KB) [v3] Fri, 7 Nov 2025 17:18:06 UTC (137 KB) [v4...