Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
- 27 March 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (6) , 3489-3514
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: (R 1 ) the region containing the neighborhoods of all strict saddle points where the objective has negative curvature; (R 2 ) the region containing neighborhoods of all global minima, where the objective enjoys strong convexity along certain directions; and (R 3 ) 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.Keywords
Funding Information
- DARPA Young Faculty Award (N66001-14-1-4047)
- National Science Foundation (DMS-1454377-CAREER, DMS-1841569-CAREER, BIGDATA-1546482, TRIPODS-1740735, BIGDATA-1840866, RI-1408910, IIS-1332109)
- NIH (R01MH102339, R01GM083084)
- Alfred P. Sloan Fellowship
This publication has 22 references indexed in Scilit:
- Sparse PCA: Optimal rates and adaptive estimationThe Annals of Statistics, 2013
- Minimax sparse principal subspace estimation in high dimensionsThe Annals of Statistics, 2013
- Minimax bounds for sparse PCA with noisy high-dimensional dataThe Annals of Statistics, 2013
- Templates for convex cone problems with applications to sparse signal recoveryMathematical Programming Computation, 2011
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm MinimizationSIAM Review, 2010
- A Singular Value Thresholding Algorithm for Matrix CompletionSIAM Journal on Optimization, 2010
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- Local Minima and Convergence in Low-Rank Semidefinite ProgrammingMathematical Programming, 2004
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorizationMathematical Programming, 2003
- Gradient methods for the minimisation of functionalsUSSR Computational Mathematics and Mathematical Physics, 1963