The Geometry of Efficient Nonconvex Sampling

2026/03/26 by Santosh S. Vempala, Andre Wibisono · 1 voice
Computer Science · Mathematics · #Constant (computer programming) #Convex body #Convex geometry #Generalization #Geometry and complex manifolds #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #Polynomial #Regular polygon #Sampling (signal processing) #Set (abstract data type) #Volume (thermodynamics) #cs.DS #cs.LG #math.ST #stat.ML

paper · pdf · open access · doi:10.48550/arxiv.2603.25622

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2026/03/26 · arxiv published 2026/03/26 · openalex created_date 2026/03/28 · arxiv updated 2026/06/30 · openalex updated_date 2026/07/28

Abstract

We present an efficient algorithm for uniformly sampling from an arbitrary compact body X ⊂ ℝⁿ 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 X and the volume growth constant of the set X.

Citations

• Oracle-based Uniform Sampling from Convex Bodies
• Faster logconcave sampling from a cold start in high dimension
• Sampling and Integration of Logconcave Functions by Algorithmic Diffusion
• In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies
• Logarithmic bounds for isoperimetry and slices of convex sets
• A Proximal Algorithm for Sampling
• Improved analysis for a proximal algorithm for sampling
• A Proximal Algorithm for Sampling from Non-smooth Potentials
• Structured Logconcave Sampling with a Restricted Gaussian Oracle
• Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms
• Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices
• Efficient Convex Optimization with Membership Oracles
• Hit-and-Run for Sampling and Planning in Non-Convex Spaces
• Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
• On the analogue of the concavity of entropy power in the Brunn-Minkowski theory

Discussions

• Does Poincare inequality suffice for polynomial-time sampling? arxiv.org/abs/2603.25622 [bsky, 1 points, 0 comments]

Related

• Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families
• The Limit of Convexity Based Isoperimetry: Sampling Harmonic-Concave Functions
• Gaussian Cooling and O*(n³) Algorithms for Volume and Gaussian Volume
• Hit-and-run mixing via localization schemes
• On theoretical guarantees and a blessing of dimensionality for nonconvex sampling