Symmetry. saddle points, and global optimization landscape of nonconvex matrix factorization

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

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

1 Scopus citations

Abstract

We propose a general theory for studying the geometry of nonconvex objective functions with underlying symmetric structures. In specific, we characterize the locations of stationary points and the null space of the associated Hessian matrices via the lens of invariant groups. As a major motivating example, we apply the proposed general theory to characterize the global geometry of the low-rank matrix factorization problem. In particular, 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 curvatures; (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 magnitudes. We further extend our result to the matrix sensing problem. This allows us to establish strong global convergence guarantees for popular iterative algorithms with arbitrary initialization.

Original languageEnglish (US)
Title of host publication2018 Information Theory and Applications Workshop, ITA 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728101248
DOIs
StatePublished - Oct 23 2018
Event2018 Information Theory and Applications Workshop, ITA 2018 - San Diego, United States
Duration: Feb 11 2018Feb 16 2018

Publication series

Name2018 Information Theory and Applications Workshop, ITA 2018

Other

Other2018 Information Theory and Applications Workshop, ITA 2018
CountryUnited States
CitySan Diego
Period2/11/182/16/18

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Software
  • Information Systems and Management
  • Theoretical Computer Science

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