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

Abstract

We propose a general theory for studying the \xl{landscape} of nonconvex \xl{optimization} with underlying symmetric structures \tz{for a class of machine learning problems (e.g., low-rank matrix factorization, phase retrieval, and deep linear neural networks)}. In specific, we characterize the locations of stationary points and the null space of Hessian matrices \xl{of the objective function} via the lens of invariant groups\removed{for associated optimization problems, including low-rank matrix factorization, phase retrieval, and deep linear neural networks}. As a major motivating example, we apply the proposed general theory to characterize the global \xl{landscape} of the \xl{nonconvex optimization in} 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: ($\cR_1$) the region containing the neighborhoods of all strict saddle points, where the objective has negative curvatures; ($\cR_2$) the region containing neighborhoods of all global minima, where the objective enjoys strong convexity along certain directions; and ($\cR_3$) the complement of the above regions, where the gradient has sufficiently large magnitudes. We further extend our result to the matrix sensing problem. Such global landscape implies strong global convergence guarantees for popular iterative algorithms with arbitrary initial solutions.

References in corpus (11)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Global Optimality of Local Search for Low Rank Matrix Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Matrix Completion has No Spurious Local Minimum
• Fast Algorithms for Robust PCA via Gradient Descent
• Gradient Descent Converges to Minimizers
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
• Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• A Non-convex One-Pass Framework for Generalized Factorization Machine and Rank-One Matrix Sensing

Cited by in corpus (9)

• Global Optimality in Low-rank Matrix Optimization
• Deep Hyperspherical Learning
• Dimensionality Reduction for Stationary Time Series via Stochastic Nonconvex Optimization
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• The Global Optimization Geometry of Shallow Linear Neural Networks
• Simple and practical algorithms for ${\ell }_p$-norm low-rank approximation
• Online Convex Matrix Factorization with Representative Regions
• Towards Understanding Acceleration Tradeoff between Momentum and Asynchrony in Nonconvex Stochastic Optimization