In‐and‐Out: Algorithmic Diffusion for Sampling Convex Bodies
Random Structures & Algorithms · 2026-05 · 68 (3)
DOI: 10.1002/rsa.70061 ↗Kurz gefasst
Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 29.03.2026. Verfasst von Yunbum Kook und 2 weiteren Autor:innen. Die Arbeit nennt 73 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Simons Foundation, National Science Foundation, Natural Sciences and Engineering Research Council of Canada.
Abstract (Originalsprache)
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.
Förderung
- Simons Foundation
- National Science Foundation
- Natural Sciences and Engineering Research Council of Canada
Zitieren
APA
Kook, Y., Vempala, S. S., & Zhang, M. S. (2026). In‐and‐Out: Algorithmic Diffusion for Sampling Convex Bodies. Random Structures & Algorithms, 68(3). https://doi.org/10.1002/rsa.70061
Vancouver
Kook Y, Vempala SS, Zhang MS. In‐and‐Out: Algorithmic Diffusion for Sampling Convex Bodies. Random Structures & Algorithms. 2026;68(3). doi:10.1002/rsa.70061
BibTeX
@article{Kook2026,
author = {Kook, Yunbum and Vempala, Santosh S. and Zhang, Matthew S.},
title = {In‐and‐Out: Algorithmic Diffusion for Sampling Convex Bodies},
journal = {Random Structures & Algorithms},
year = {2026},
volume = {68},
number = {3},
doi = {10.1002/rsa.70061}
}
EUVIMED