93 citations · 578 across the 83 of their papers we have counts for
13 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…
Convergence of the Riemannian Langevin Algorithm
Khashayar Gatmiry, Santosh S. Vempala
We study the Riemannian Langevin Algorithm for the problem of sampling from a distribution with density with respect to the natural measure on a manifold with metric . We as…
Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space
Yunbum Kook, Yin Tat Lee, Ruoqi Shen +1
We demonstrate for the first time that ill-conditioned, non-smooth, constrained distributions in very high dimension, upwards of 100,000, can be sampled efficiently $\textit{in pra…
Provable Lifelong Learning of Representations
Xinyuan Cao, Weiyang Liu, Santosh S. Vempala
In lifelong learning, tasks (or classes) to be learned arrive sequentially over time in arbitrary order. During training, knowledge from previous tasks can be captured and transfer…
Socially Fair k-Means Clustering
Mehrdad Ghadiri, Samira Samadi, Santosh Vempala
We show that the popular k-means clustering algorithm (Lloyd's heuristic), used for a variety of scientific data, can result in outcomes that are unfavorable to subgroups of data (…
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…
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…
On the Complexity of Learning Neural Networks
Le Song, Santosh Vempala, John Wilmes +1
The stunning empirical successes of neural networks currently lack rigorous theoretical explanation. What form would such an explanation take, in the face of existing complexity-th…
Chi-squared Amplification: Identifying Hidden Hubs
Ravi Kannan, Santosh Vempala
We consider the following general hidden hubs model: an random matrix with a subset of special rows (hubs): entries in rows outside are generated from…
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization
Vitaly Feldman, Cristobal Guzman, Santosh Vempala
Stochastic convex optimization, where the objective is the expectation of a random convex function, is an important and widely used method with numerous applications in machine lea…
Efficient Representations for Life-Long Learning and Autoencoding
Maria-Florina Balcan, Avrim Blum, Santosh Vempala
It has been a long-standing goal in machine learning, as well as in AI more generally, to develop life-long learning systems that learn many different tasks over time, and reuse in…
Fourier PCA and Robust Tensor Decomposition
Navin Goyal, Santosh Vempala, Ying Xiao
Fourier PCA is Principal Component Analysis of a matrix obtained from higher order derivatives of the logarithm of the Fourier transform of a distribution.We make this method algor…
Isotropic PCA and Affine-Invariant Clustering
S. Charles Brubaker, Santosh S. Vempala
We present a new algorithm for clustering points in R^n. The key property of the algorithm is that it is affine-invariant, i.e., it produces the same partition for any affine trans…