The Non-convex Geometry of Low-rank Matrix Optimization

Abstract

This work considers two popular minimization problems: (i) the minimization of a general convex function $f(\mathbf{X})$ with the domain being positive semi-definite matrices; (ii) the minimization of a general convex function $f(\mathbf{X})$ regularized by the matrix nuclear norm $\Vert \mathbf{X}{\Vert }_{\ast }$ with the domain being general matrices. Despite their optimal statistical performance in the literature, these two optimization problems have a high computational complexity even when solved using tailored fast convex solvers. To develop faster and more scalable algorithms, we follow the proposal of Burer and Monteiro to factor the low-rank variable $\mathbf{X}=\mathbf{U}{\mathbf{U}}^{\top }$ (for semi-definite matrices) or $\mathbf{X}=\mathbf{U}{\mathbf{V}}^{\top }$ (for general matrices) and also replace the nuclear norm $\Vert \mathbf{X}{\Vert }_{\ast }$ with $(\Vert \mathbf{U}{\Vert }_F^2+\Vert \mathbf{V}{\Vert }_F^2)/2$. In spite of the non-convexity of the resulting factored formulations, we prove that each critical point either corresponds to the global optimum of the original convex problems or is a strict saddle where the Hessian matrix has a strictly negative eigenvalue. Such a nice geometric structure of the factored formulations allows many local search algorithms to find a global optimizer even with random initializations.

References in corpus (11)

• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Global Optimality of Local Search for Low Rank Matrix Recovery
• How to Escape Saddle Points Efficiently
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Global Optimality in Low-rank Matrix Optimization
• First-order Methods Almost Always Avoid Saddle Points
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems
• Provable quantum state tomography via non-convex methods

Cited by in corpus (32)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Global Optimality in Low-rank Matrix Optimization
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• Introduction to Nonnegative Matrix Factorization
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
• The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
• The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension
• Solving Complex Quadratic Systems with Full-Rank Random Matrices
• Fair Principal Component Analysis and Filter Design
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
• How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
• Nonconvex Robust Low-rank Matrix Recovery
• Low-Rank Univariate Sum of Squares Has No Spurious Local Minima
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
• The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
• Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• Global and Local Analyses of Nonlinear Low-Rank Matrix Recovery Problems
• PCA by Optimisation of Symmetric Functions has no Spurious Local Optima
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms
• Spherical Principal Component Analysis
• PCA by Determinant Optimization has no Spurious Local Optima
• A three-operator splitting algorithm for nonconvex sparsity regularization
• Learning Mixtures of Low-Rank Models
• Error bound of critical points and KL property of exponent $1/2$ for squared F-norm regularized factorization
• A parameterized Douglas-Rachford Splitting algorithm for nonconvex optimization