The Global Optimization Geometry of Low-Rank Matrix Optimization

Abstract

This paper considers general rank-constrained optimization problems that minimize a general objective function $f(X)$ over the set of rectangular $n\times m$ matrices that have rank at most $r$. To tackle the rank constraint and also to reduce the computational burden, we factorize $X$ into $U{V}^T$ where $U$ and $V$ are $n\times r$ and $m\times r$ matrices, respectively, and then optimize over the small matrices $U$ and $V$. We characterize the global optimization geometry of the nonconvex factored problem and show that the corresponding objective function satisfies the robust strict saddle property as long as the original objective function $f$ satisfies restricted strong convexity and smoothness properties, ensuring global convergence of many local search algorithms (such as noisy gradient descent) in polynomial time for solving the factored problem. We also provide a comprehensive analysis for the optimization geometry of a matrix factorization problem where we aim to find $n\times r$ and $m\times r$ matrices $U$ and $V$ such that $U{V}^T$ approximates a given matrix $X^{\star }$. Aside from the robust strict saddle property, we show that the objective function of the matrix factorization problem has no spurious local minima and obeys the strict saddle property not only for the exact-parameterization case where $rank(X^{\star })=r$, but also for the over-parameterization case where $rank(X^{\star })<r$ and the under-parameterization case where $rank(X^{\star })>r$. These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) converge to a global solution with random initialization.

References in corpus (3)

• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Global Optimality in Low-rank Matrix Optimization
• Dynamic matrix recovery from incomplete observations under an exact low-rank constraint

Cited by in corpus (13)

• Global Optimality in Low-rank Matrix Optimization
• Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
• The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
• Nonconvex Robust Low-rank Matrix Recovery
• On Landscape of Lagrangian Functions and Stochastic Search for Constrained Nonconvex Optimization
• The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• The Global Optimization Geometry of Shallow Linear Neural Networks
• A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees
• Global Optimality in Distributed Low-rank Matrix Factorization
• An equivalence between critical points for rank constraints versus low-rank factorizations
• Error bound of critical points and KL property of exponent $1/2$ for squared F-norm regularized factorization
• Uncertainty Quantification For Low-Rank Matrix Completion With Heterogeneous and Sub-Exponential Noise