229 citations · 547 across the 23 of their papers we have counts for
4 papers · 1 filter
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
Chi Jin, Praneeth Netrapalli, Michael I. Jordan
Nesterov's accelerated gradient descent (AGD), an instance of the general family of "momentum methods", provably achieves faster convergence rate than gradient descent (GD) in the…
Leverage Score Sampling for Faster Accelerated Regression and ERM
Naman Agarwal, Sham Kakade, Rahul Kidambi +3
Given a matrix and a vector , we show how to compute an -approximate solution to the regression problem $ \min_{x\in\m…
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 $…