Santosh S. Vempala

research

∙ 07/24/2023

Efficiently Sampling the PSD Cone with the Metric Dikin Walk

Semi-definite programs represent a frontier of efficient computation. Wh...

0 Yunbum Kook, et al. ∙

research

∙ 06/06/2023

Computation with Sequences in the Brain

Even as machine learning exceeds human-level performance on many applica...

0 Max Dabagia, et al. ∙

research

∙ 04/04/2023

The Bit Complexity of Efficient Continuous Optimization

We analyze the bit complexity of efficient algorithms for fundamental op...

0 Mehrdad Ghadiri, et al. ∙

research

∙ 03/01/2023

Sampling with Barriers: Faster Mixing via Lewis Weights

We analyze Riemannian Hamiltonian Monte Carlo (RHMC) for sampling a poly...

0 Khashayar Gatmiry, et al. ∙

research

∙ 03/01/2023

Is Planted Coloring Easier than Planted Clique?

We study the computational complexity of two related problems: recoverin...

0 Pravesh K. Kothari, et al. ∙

research

∙ 02/23/2023

Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error

We present a polynomial-time algorithm for robustly learning an unknown ...

0 He Jia, et al. ∙

research

∙ 10/13/2022

Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators

We study the convergence rate of discretized Riemannian Hamiltonian Mont...

0 Yunbum Kook, et al. ∙

research

∙ 08/24/2022

A Slightly Improved Bound for the KLS Constant

We refine the recent breakthrough technique of Klartag and Lehec to obta...

0 Arun Jambulapati, et al. ∙

research

∙ 06/22/2022

Constant-Factor Approximation Algorithms for Socially Fair k-Clustering

We study approximation algorithms for the socially fair (ℓ_p, k)-cluster...

10 Mehrdad Ghadiri, et al. ∙

research

∙ 05/02/2022

A Unified Approach to Discrepancy Minimization

We study a unified approach and algorithm for constructive discrepancy m...

0 Nikhil Bansal, et al. ∙

research

∙ 04/22/2022

Convergence of the Riemannian Langevin Algorithm

We study the Riemannian Langevin Algorithm for the problem of sampling f...

0 Khashayar Gatmiry, et al. ∙

research

∙ 03/23/2022

The k-Cap Process on Geometric Random Graphs

The k-cap (or k-winners-take-all) process on a graph works as follows: i...

0 Mirabel Reid, et al. ∙

research

∙ 02/03/2022

Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space

We demonstrate for the first time that ill-conditioned, non-smooth, cons...

0 Yunbum Kook, et al. ∙

research

∙ 11/17/2021

How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization

The success of gradient descent in ML and especially for learning neural...

0 Shivam Garg, et al. ∙

research

∙ 10/27/2021

Provable Lifelong Learning of Representations

In lifelong learning, the tasks (or classes) to be learned arrive sequen...

0 Xinyuan Cao, et al. ∙

research

∙ 10/07/2021

Assemblies of neurons can learn to classify well-separated distributions

Assemblies are patterns of coordinated firing across large populations o...

7 Max Dabagia, et al. ∙

research

∙ 09/24/2021

The Mirror Langevin Algorithm Converges with Vanishing Bias

The technique of modifying the geometry of a problem from Euclidean to H...

0 Ruilin Li, et al. ∙

research

∙ 09/23/2021

Sparse Regression Faster than d^ω

The current complexity of regression is nearly linear in the complexity ...

0 Mehrdad Ghadiri, et al. ∙

research

∙ 08/10/2021

Tutorial on the Robust Interior Point Method

We give a short, self-contained proof of the interior point method and i...

0 Yin Tat Lee, et al. ∙

research

∙ 12/03/2020

Robustly Learning Mixtures of k Arbitrary Gaussians

We give a polynomial-time algorithm for the problem of robustly estimati...

3 Ainesh Bakshi, et al. ∙

research

∙ 08/05/2020

Reducing Isotropy and Volume to KLS: An O(n^3ψ^2) Volume Algorithm

We show that the the volume of a convex body in ℝ^n in the general membe...

0 He Jia, et al. ∙

research

∙ 06/13/2019

The Communication Complexity of Optimization

We consider the communication complexity of a number of distributed opti...

0 Santosh S. Vempala, et al. ∙

research

∙ 05/07/2019

Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions

We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logc...

0 Zongchen Chen, et al. ∙

research

∙ 03/20/2019

Rapid Convergence of the Unadjusted Langevin Algorithm: Log-Sobolev Suffices

We prove a convergence guarantee on the unadjusted Langevin algorithm fo...

0 Santosh S. Vempala, et al. ∙

research

∙ 12/15/2018

Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities

Sampling logconcave functions arising in statistics and machine learning...

0 Yin Tat Lee, et al. ∙

research

∙ 07/10/2018

The Kannan-Lovász-Simonovits Conjecture

The Kannan-Lovász-Simonovits conjecture says that the Cheeger constant o...

0 Yin Tat Lee, et al. ∙

research

∙ 02/10/2018

Approximating Sparse Graphs: The Random Overlapping Communities Model

How can we approximate sparse graphs and sequences of sparse graphs (wit...

0 Samantha Petti, et al. ∙

research

∙ 10/17/2017

Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation

We give the first rigorous proof of the convergence of Riemannian Hamilt...

0 Yin Tat Lee, et al. ∙

research

∙ 06/22/2017

Efficient Convex Optimization with Membership Oracles

We consider the problem of minimizing a convex function over a convex se...

0 Yin Tat Lee, et al. ∙

research

∙ 12/26/2014

Unsupervised Learning through Prediction in a Model of Cortex

We propose a primitive called PJOIN, for "predictive join," which combin...

0 Christos H. Papadimitriou, et al. ∙

research

∙ 12/09/2014

Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity

We present a simple, general technique for reducing the sample complexit...

0 Santosh S. Vempala, et al. ∙

Santosh S. Vempala

Featured Co-authors