EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Yunbum Kook, Santosh S. Vempala, Matthew S. Zhang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →