The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
arXiv:2003.10981 · doi:10.1109/LSP.2020.3008876
Abstract
Low-rank matrix recovery is a fundamental problem in signal processing and machine learning. A recent very popular approach to recovering a low-rank matrix X is to factorize it as a product of two smaller matrices, i.e., X = UV^T, and then optimize over U, V instead of X. Despite the resulting non-convexity, recent results have shown that many factorized objective functions actually have benign global geometry---with no spurious local minima and satisfying the so-called strict saddle property---ensuring convergence to a global minimum for many local-search algorithms. Such results hold whenever the original objective function is restricted strongly convex and smooth. However, most of these results actually consider a modified cost function that includes a balancing regularizer. While useful for deriving theory, this balancing regularizer does not appear to be necessary in practice. In this work, we close this theory-practice gap by proving that the unaltered factorized non-convex problem, without the balancing regularizer, also has similar benign global geometry. Moreover, we also extend our theoretical results to the field of distributed optimization.
References in corpus (13)
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Guaranteed Matrix Completion via Non-convex Factorization
- How to Escape Saddle Points Efficiently
- Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
- Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
- Global Optimality in Low-rank Matrix Optimization
- Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
- Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
- The Non-convex Geometry of Low-rank Matrix Optimization
- The Global Optimization Geometry of Low-Rank Matrix Optimization
- Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
- The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
Cited by in corpus (4)
- Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
- Global convergence of the gradient method for functions definable in o-minimal structures
- Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
- Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem