6 papers
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…
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}…
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…
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…
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…