Timezone: »

 
Poster
Global Optimality of Local Search for Low Rank Matrix Recovery
Srinadh Bhojanapalli · Behnam Neyshabur · Nati Srebro

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #20
in Tuesday Posters »

We show that there are no spurious local minima in the non-convex factorized parametrization of low-rank matrix recovery from incoherent linear measurements. With noisy measurements we show all local minima are very close to a global optimum. Together with a curvature bound at saddle points, this yields a polynomial time global convergence guarantee for stochastic gradient descent {\em from random initialization}.

Keywords: Matrix Factorization · Convex Optimization
[ PDF] 

Author Information

Srinadh Bhojanapalli (TTI Chicago)
Behnam Neyshabur (TTI-Chicago)
Nati Srebro (TTI-Chicago)

More from the Same Authors