The Geometry of Efficient Nonconvex Sampling
This provides a substantial generalization of sampling methods for convex and star-shaped bodies, addressing a fundamental challenge in computational geometry and statistics.
The paper tackles the problem of uniformly sampling from arbitrary compact bodies in high dimensions, presenting an algorithm with polynomial complexity in dimension, Poincaré constant, and volume growth constant.
We present an efficient algorithm for uniformly sampling from an arbitrary compact body $\mathcal{X} \subset \mathbb{R}^n$ from a warm start under isoperimetry and a natural volume growth condition. Our result provides a substantial common generalization of known results for convex bodies and star-shaped bodies. The complexity of the algorithm is polynomial in the dimension, the Poincaré constant of the uniform distribution on $\mathcal{X}$ and the volume growth constant of the set $\mathcal{X}$.