93 citations · 578 across the 83 of their papers we have counts for
6 papers · 1 filter
Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
Yin Tat Lee, Zhao Song, Santosh S. Vempala
Sampling logconcave functions arising in statistics and machine learning has been a subject of intensive study. Recent developments include analyses for Langevin dynamics and Hamil…
The Price of Fair PCA: One Extra Dimension
Samira Samadi, Uthaipon Tantipongpipat, Jamie Morgenstern +2
We investigate whether the standard dimensionality reduction technique of PCA inadvertently produces data representations with different fidelity for two different populations. We…
Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons
Nima Anari, Constantinos Daskalakis, Wolfgang Maass +3
We analyze linear independence of rank one tensors produced by tensor powers of randomly perturbed vectors. This enables efficient decomposition of sums of high-order tensors. Our…
The Kannan-Lovász-Simonovits Conjecture
Yin Tat Lee, Santosh S. Vempala
The Kannan-Lovász-Simonovits conjecture says that the Cheeger constant of any logconcave density is achieved to within a universal, dimension-independent constant factor by a hyper…
Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds
Santosh Vempala, John Wilmes
We study the complexity of training neural network models with one hidden nonlinear activation layer and an output weighted sum layer. We analyze Gradient Descent applied to learni…
Approximating Sparse Graphs: The Random Overlapping Communities Model
Samantha Petti, Santosh S. Vempala
How can we approximate sparse graphs and sequences of sparse graphs (with unbounded average degree)? We consider convergence in the first moments of the graph spectrum (equival…