989 citations · 6.1k across the 184 of their papers we have counts for
7 papers · 1 filter
Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation
Chi Jin, Sham M. Kakade, Cameron Musco +2
We provide faster algorithms and improved sample complexities for approximating the top eigenvector of a matrix. Offline Setting: Given an matrix , we show how to c…
Super-Resolution Off the Grid
Qingqing Huang, Sham M. Kakade
Super-resolution is the problem of recovering a superposition of point sources using bandlimited measurements, which may be corrupted with noise. This signal processing problem ari…
Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squareroot
Prateek Jain, Chi Jin, Sham M. Kakade +1
While there has been a significant amount of work studying gradient descent techniques for non-convex optimization problems over the last few years, all existing results establish…
Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
Roy Frostig, Rong Ge, Sham M. Kakade +1
We develop a family of accelerated stochastic algorithms that minimize sums of convex functions. Our algorithms improve upon the fastest running time for empirical risk minimizatio…
Convergence Rates of Active Learning for Maximum Likelihood Estimation
Kamalika Chaudhuri, Sham Kakade, Praneeth Netrapalli +1
An active learner is given a class of models, a large set of unlabeled examples, and the ability to interactively query labels of a subset of these examples; the goal of the learne…
Learning Mixtures of Gaussians in High Dimensions
Rong Ge, Qingqing Huang, Sham M. Kakade
Efficiently learning mixture of Gaussians is a fundamental problem in statistics and learning theory. Given samples coming from a random one out of k Gaussian distributions in Rn,…