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

DOI10.1109/TIT.2019.2898663zbMATH Open1432.90123arXiv1612.09296OpenAlexW2931810883WikidataQ128135569 ScholiaQ128135569MaRDI QIDQ5224010FDOQ5224010

Authors: Xing Guo Li, Junwei Lu, Raman Arora, Jarvis D. Haupt, Han Liu, Zhaoran Wang, Tuo Zhao 

Publication date: 19 July 2019

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We propose a general theory for studying the xl{landscape} of nonconvex xl{optimization} with underlying symmetric structures z{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 emoved{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: ($c{R}_1$) the region containing the neighborhoods of all strict saddle points, where the objective has negative curvatures; ($c{R}_2$) the region containing neighborhoods of all global minima, where the objective enjoys strong convexity along certain directions; and ($c{R}_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.

Full work available at URL: https://arxiv.org/abs/1612.09296

zbMATH Keywords

phase retrievallow-rank matrix factorizationdeep linear neural networksclass of machine learning problemslandscape of nonconvex optimization with underlying symmetric structureslocations of stationary pointsmatrix sensing problemnull space of Hessian matrices of objective function

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Cited In (16)

• The global optimization geometry of shallow linear neural networks
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
• Title not available (Why is that?)
• Role of sparsity and structure in the optimization landscape of non-convex matrix sensing
• Column \(\ell_{2,0}\)-norm regularized factorization model of low-rank matrix recovery and its computation
• Symmetry-based matrix factorization
• GNMR: a provable one-line algorithm for low rank matrix recovery
• Provable accelerated gradient method for nonconvex low rank optimization
• \(L^p\) continuity and microlocal properties for pseudodifferential operators
• Title not available (Why is that?)
• Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization
• Model-free nonconvex matrix completion: local minima analysis and applications in memory-efficient kernel PCA
• Analysis of the optimization landscape of Linear Quadratic Gaussian (LQG) control
• Nonconvex Robust Low-Rank Matrix Recovery
• Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation

This page was built for publication: Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224010)