NeurIPS 2016poster475 citations
Global Optimality of Local Search for Low Rank Matrix Recovery
Srinadh Bhojanapalli, Behnam Neyshabur, Nati Srebro
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}.
BibTeX
@inproceedings{NIPS2016_b139e104,
author = {Bhojanapalli, Srinadh and Neyshabur, Behnam and Srebro, Nati},
booktitle = {Advances in Neural Information Processing Systems},
editor = {D. Lee and M. Sugiyama and U. Luxburg and I. Guyon and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Global Optimality of Local Search for Low Rank Matrix Recovery},
url = {https://proceedings.neurips.cc/paper_files/paper/2016/file/b139e104214a08ae3f2ebcce149cdf6e-Paper.pdf},
volume = {29},
year = {2016}
}