93 citations · 578 across the 83 of their papers we have counts for
8 papers · 1 filter
Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time
Xinyuan Cao, Santosh S. Vempala
We give a polynomial-time algorithm for learning high-dimensional halfspaces with margins in -dimensional space to within desired TV distance when the ambient distribution is an…
Calibrated Language Models Must Hallucinate
Adam Tauman Kalai, Santosh S. Vempala
Recent language models generate false but plausible-sounding text with surprising frequency. Such "hallucinations" are an obstacle to the usability of language-based AI systems and…
Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling
Yunbum Kook, Santosh S. Vempala
The connections between (convex) optimization and (logconcave) sampling have been considerably enriched in the past decade with many conceptual and mathematical analogies. For inst…
Computation with Sequences in a Model of the Brain
Max Dabagia, Christos H. Papadimitriou, Santosh S. Vempala
Even as machine learning exceeds human-level performance on many applications, the generality, robustness, and rapidity of the brain's learning capabilities remain unmatched. How c…
Sampling with Barriers: Faster Mixing via Lewis Weights
Khashayar Gatmiry, Jonathan Kelner, Santosh S. Vempala
We analyze Riemannian Hamiltonian Monte Carlo (RHMC) for sampling a polytope defined by inequalities in endowed with the metric defined by the Hessian of a convex barrie…
The Bit Complexity of Efficient Continuous Optimization
Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala
We analyze the bit complexity of efficient algorithms for fundamental optimization problems, such as linear regression, -norm regression, and linear programming (LP). State-of-t…