Skip to yearly menu bar Skip to main content


Poster

Global Optimality of Local Search for Low Rank Matrix Recovery

Srinadh Bhojanapalli · Behnam Neyshabur · Nati Srebro

Area 5+6+7+8 #20

Keywords: [ Matrix Factorization ] [ Convex Optimization ]


Abstract:

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}.

Live content is unavailable. Log in and register to view live content