The Geometry of Efficient Nonconvex Sampling

Santosh S. Vempala, Andre Wibisono
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6496-6532, 2026.

Abstract

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}$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-vempala26a, title = {The Geometry of Efficient Nonconvex Sampling}, author = {Vempala, Santosh S. and Wibisono, Andre}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {6496--6532}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/vempala26a/vempala26a.pdf}, url = {https://proceedings.mlr.press/v336/vempala26a.html}, abstract = {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}$.} }
Endnote
%0 Conference Paper %T The Geometry of Efficient Nonconvex Sampling %A Santosh S. Vempala %A Andre Wibisono %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-vempala26a %I PMLR %P 6496--6532 %U https://proceedings.mlr.press/v336/vempala26a.html %V 336 %X 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}$.
APA
Vempala, S.S. & Wibisono, A.. (2026). The Geometry of Efficient Nonconvex Sampling. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:6496-6532 Available from https://proceedings.mlr.press/v336/vempala26a.html.

Related Material