Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization

Xingguo Li, Junwei Lu, Raman Arora, Jarvis Haupt, Han Liu, Zhaoran Wang, Tuo Zhao

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

We propose a general theory for studying the landscape of nonconvex optimization with underlying symmetric structures for a class of machine learning problems (e.g., low-rank matrix factorization, phase retrieval, and deep linear neural networks). In particular, we characterize the locations of stationary points and the null space of Hessian matrices of the objective function via the lens of invariant groups. As a major motivating example, we apply the proposed general theory to characterize the global landscape of the nonconvex optimization in low-rank matrix factorization problem. We illustrate how the rotational symmetry group gives rise to infinitely many nonisolated strict saddle points and equivalent global minima of the objective function. By explicitly identifying all stationary points, we divide the entire parameter space into three regions: (R1) the region containing the neighborhoods of all strict saddle points where the objective has negative curvature; (R2) the region containing neighborhoods of all global minima, where the objective enjoys strong convexity along certain directions; and (R3) the complement of the above regions, where the gradient has sufficiently large magnitude. We further extend our result to the matrix sensing problem. Such global landscape implies that strong global convergence guarantees for popular iterative algorithms with arbitrary initial solutions.

Original languageEnglish (US)
Article number8675509
Pages (from-to)3489-3514
Number of pages26
JournalIEEE Transactions on Information Theory
Volume65
Issue number6
DOIs
StatePublished - Jun 2019

Bibliographical note

Funding Information:
This work was supported in part by the DARPA Young Faculty Award under Grant N66001-14-1-4047, in part by the NSF under Grant DMS-1454377-CAREER, Grant DMS-1841569-CAREER, Grant BIGDATA-1546482, Grant TRIPODS-1740735, Grant BIGDATA-1840866, Grant RI-1408910, and Grant IIS-1332109, in part by the NIH under Grant R01MH102339 and Grant R01GM083084, and in part by the Alfred P. Sloan Fellowship.

Funding Information:
Manuscript received March 19, 2017; revised January 14, 2018; accepted October 15, 2018. Date of publication March 27, 2019; date of current version May 20, 2019. This work was supported in part by the DARPA Young Faculty Award under Grant N66001-14-1-4047, in part by the NSF under Grant DMS-1454377-CAREER, Grant DMS-1841569-CAREER, Grant BIGDATA-1546482, Grant TRIPODS-1740735, Grant BIGDATA-1840866, Grant RI-1408910, and Grant IIS-1332109, in part by the NIH under Grant R01MH102339 and Grant R01GM083084, and in part by the Alfred P. Sloan Fellowship.

Keywords

  • Strict saddle problem
  • global landscape
  • invariant group
  • matrix sensing
  • nonconvex matrix factorization

Fingerprint Dive into the research topics of 'Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization'. Together they form a unique fingerprint.

Cite this