9 papers
A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
Santosh S. Vempala
We prove nearly quadratic lower bounds for randomized algorithms for linear optimization and uniform sampling over convex bodies in the membership oracle model. For linear optimiza…
Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start
Yunbum Kook, Santosh S. Vempala
We show that logconcave probability measures along the Gaussian cooling path have thin-shell stability, generalizing the thin-shell theorem. This result leads to improved complexit…
Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run
Yunbum Kook, Santosh S. Vempala
For any convex body containing a unit ball, the spectral gap of Hit-and-Run is , where is the Poinc…
A unified complexity bound for logconcave sampling
Yunbum Kook, Santosh S. Vempala
We give a simple, unified, and nearly tight bound for sampling arbitrary logconcave distributions from a warm start using the In-and-Out algorithm along with exponential lifting. T…
Tight Bounds for Learning Polyhedra with a Margin
Shyamal Patel, Santosh Vempala
We give an algorithm for PAC learning intersections of halfspaces with a margin to within error that runs in time $\textsf{poly}(k, \varepsilon^{-1}, ρ^{-1})…
The Geometry of Efficient Nonconvex Sampling
Santosh S. Vempala, Andre Wibisono
We present an efficient algorithm for uniformly sampling from an arbitrary compact body from a warm start under isoperimetry and a natural volume…
Sampling Sphere Packings with Continuum Glauber Dynamics
Aiya Kuchukova, Santosh S. Vempala, Daniel J. Zhang
Continuum Glauber dynamics is a spatial birth-death process whose stationary distribution is a Gibbs distribution. We establish a spectral gap for Continuum Glauber dynamics applie…
Provable Long-Range Benefits of Next-Token Prediction
Xinyuan Cao, Santosh S. Vempala
Why do modern language models, trained to do well on next-word prediction, appear to generate coherent documents and capture long-range structure? Here we show that next-token pred…
Zeroth-order Logconcave Sampling
Yunbum Kook, Santosh S. Vempala
We study the zeroth-order query complexity of sampling from a general logconcave distribution: given access to an evaluation oracle for a convex function $V:\mathbb{R}^{d}\rightarr…