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

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 stationary density.

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

Kook et al. "In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies." Neural Information Processing Systems, 2024. doi:10.52202/079017-3440

Markdown

[Kook et al. "In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies." Neural Information Processing Systems, 2024.](https://mlanthology.org/neurips/2024/kook2024neurips-inandout/) doi:10.52202/079017-3440

BibTeX

@inproceedings{kook2024neurips-inandout,
  title     = {{In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies}},
  author    = {Kook, Yunbum and Vempala, Santosh S. and Zhang, Matthew S.},
  booktitle = {Neural Information Processing Systems},
  year      = {2024},
  doi       = {10.52202/079017-3440},
  url       = {https://mlanthology.org/neurips/2024/kook2024neurips-inandout/}
}