skip to main content
Caltech

RSRG/DOLCIT Seminar Series

Thursday, June 1, 2017
12:00pm to 1:00pm
Add to Cal
Annenberg 213
Matrix Completion, Saddlepoints, and Gradient Descent
Jason Lee, Assistant Professor, Data Sciences and Operations, University of Southern California.,
 
Matrix completion is a fundamental machine learning problem with wide applications in collaborative filtering and recommender systems. Typically, matrix completion are solved by non-convex optimization procedures, which are empirically extremely successful. We prove that the symmetric matrix completion problem has no spurious local minima, meaning all local minima are also global. Thus the matrix completion objective has only saddlepoints an global minima.
 
Next, we show that saddlepoints are easy to avoid for even Gradient Descent -- arguably the simplest optimization procedure. We prove that with probability 1, randomly initialized Gradient Descent converges to a local minimizer. The same result holds for a large class of optimization algorithms including proximal point, mirror descent, and coordinate descent.

 

For more information, please contact Diane Goodfellow by email at diane@cms.caltech.edu.