Global Optimality of Local Search for Low Rank Matrix Recovery
This addresses the challenge of non-convex optimization in machine learning by ensuring global optimality for low-rank matrix recovery, which is incremental as it builds on prior work in matrix factorization.
The paper proves that for low-rank matrix recovery from incoherent linear measurements, there are no spurious local minima in the non-convex factorized parametrization, and with noisy measurements, all local minima are close to a global optimum, enabling polynomial-time global convergence for stochastic gradient descent from random initialization.
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}.