@inproceedings{
kook2024inandout,
title={In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies},
author={Yunbum Kook and Santosh Vempala and Matthew Shunshi Zhang},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=aNQWRHyh15}
}
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.
In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies
Yunbum Kook Santosh Vempala Matthew Shunshi Zhang