No spurious local minima in nonconvex low rank problems: A unified geometric analysis

Rong Ge, Chi Jin, Yi Zheng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

26 Scopus citations

Abstract

In this paper we develop a new framework that captures the common landscape underlying the common non-convex low-rank matrix problems including matrix sensing, matrix completion and robust PCA. In particular, we show for all above problems (including asymmetric cases): 1) ail local minima are also globally optimal; 2) no high-order saddle points exists. These results explain why simple algorithms such as stochastic gradient descent have global converge, and efficiently optimize these non-convex objective functions in practice. Our framework connects and simplifies the existing analyses on optimization landscapes for matrix sensing and symmetric matrix completion. The framework naturally leads to new results for asymmetric matrix completion and robust PCA.

Original languageEnglish (US)
Title of host publication34th International Conference on Machine Learning, ICML 2017
PublisherInternational Machine Learning Society (IMLS)
Pages1990-2028
Number of pages39
ISBN (Electronic)9781510855144
StatePublished - Jan 1 2017
Externally publishedYes
Event34th International Conference on Machine Learning, ICML 2017 - Sydney, Australia
Duration: Aug 6 2017Aug 11 2017

Publication series

Name34th International Conference on Machine Learning, ICML 2017
Volume3

Other

Other34th International Conference on Machine Learning, ICML 2017
CountryAustralia
CitySydney
Period8/6/178/11/17

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Human-Computer Interaction
  • Software

Cite this

Ge, R., Jin, C., & Zheng, Y. (2017). No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In 34th International Conference on Machine Learning, ICML 2017 (pp. 1990-2028). (34th International Conference on Machine Learning, ICML 2017; Vol. 3). International Machine Learning Society (IMLS).