In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914410365190144 |
|---|---|
| author | Kook, Yunbum Vempala, Santosh S. Zhang, Matthew S. |
| author_facet | Kook, Yunbum Vempala, Santosh S. Zhang, Matthew S. |
| contents | 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, $χ^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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_01425 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies Kook, Yunbum Vempala, Santosh S. Zhang, Matthew S. Data Structures and Algorithms Machine Learning Statistics Theory 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, $χ^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. |
| title | In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies |
| topic | Data Structures and Algorithms Machine Learning Statistics Theory |
| url | https://arxiv.org/abs/2405.01425 |