24 citations · 30 across the 3 of their papers we have counts for
10 papers
How to Escape Saddle Points Efficiently
Chi Jin, Rong Ge, Praneeth Netrapalli +2
This paper shows that a perturbed form of gradient descent converges to a second-order stationary point in a number iterations which depends only poly-logarithmically on dimension…
Thresholding based Efficient Outlier Robust PCA
Yeshwanth Cherapanamjeri, Prateek Jain, Praneeth Netrapalli
We consider the problem of outlier robust PCA (OR-PCA) where the goal is to recover principal directions despite the presence of outlier data points. That is, given a data matrix $…
Information-theoretic thresholds for community detection in sparse networks
Jess Banks, Cristopher Moore, Joe Neeman +1
We give upper and lower bounds on the information-theoretic threshold for community detection in the stochastic block model. Specifically, consider the symmetric stochastic block m…
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…