989 citations · 6.1k across the 184 of their papers we have counts for
5 papers · 2 filters
Prediction with a Short Memory
Vatsal Sharan, Sham Kakade, Percy Liang +1
We consider the problem of predicting the next observation given a sequence of past observations, and consider the extent to which accurate prediction requires complex algorithms t…
Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
Rong Ge, Chi Jin, Sham M. Kakade +2
This paper considers the problem of canonical-correlation analysis (CCA) (Hotelling, 1936) and, more broadly, the generalized eigenvector problem for a pair of symmetric matrices.…
Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
Chi Jin, Sham M. Kakade, Praneeth Netrapalli
Matrix completion, where we wish to recover a low rank matrix by observing a few entries from it, is a widely studied problem in both theory and practice with wide applications. Mo…
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm
Prateek Jain, Chi Jin, Sham M. Kakade +2
This work provides improved guarantees for streaming principle component analysis (PCA). Given sampled independently from distributions…
Recovering Structured Probability Matrices
Qingqing Huang, Sham M. Kakade, Weihao Kong +1
We consider the problem of accurately recovering a matrix B of size M by M , which represents a probability distribution over M2 outcomes, given access to an observed matrix of "co…