Global Optimality in Low-rank Matrix Optimization

Abstract

This paper considers the minimization of a general objective function $f(X)$ over the set of rectangular $n\times m$ matrices that have rank at most $r$. To reduce the computational burden, we factorize the variable $X$ into a product of two smaller matrices and optimize over these two matrices instead of $X$. Despite the resulting nonconvexity, recent studies in matrix completion and sensing have shown that the factored problem has no spurious local minima and obeys the so-called strict saddle property (the function has a directional negative curvature at all critical points but local minima). We analyze the global geometry for a general and yet well-conditioned objective function $f(X)$ whose restricted strong convexity and restricted strong smoothness constants are comparable. In particular, we show that the reformulated objective function has no spurious local minima and obeys the strict saddle property. These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) can provably solve the factored problem with global convergence.

References in corpus (21)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• An overview of low-rank matrix recovery from incomplete observations
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Low-Rank Matrix Approximation with Weights or Missing Data is NP-hard
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Gradient Descent Converges to Minimizers
• When Are Nonconvex Problems Not Scary?
• The Non-convex Geometry of Low-rank Matrix Optimization
• Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
• Dropping Convexity for Faster Semi-definite Optimization
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• The Learnability of Quantum States
• Dynamic matrix recovery from incomplete observations under an exact low-rank constraint
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization

Cited by in corpus (44)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• The Non-convex Geometry of Low-rank Matrix Optimization
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• 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
• Scalable Spectral Clustering with Nystrom Approximation: Practical and Theoretical Aspects
• Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy
• Loss Landscapes of Regularized Linear Autoencoders
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
• Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
• A Deterministic Theory for Exact Non-Convex Phase Retrieval
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Fair Principal Component Analysis and Filter Design
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Nonconvex Robust Low-rank Matrix Recovery
• Convolutional Geometric Matrix Completion
• Gradient descent with nonconvex constraints: local concavity determines convergence
• Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery
• Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization
• Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery
• General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
• The Global Optimization Geometry of Shallow Linear Neural Networks
• Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
• Alternating Iteratively Reweighted Minimization Algorithms for Low-Rank Matrix Factorization
• Spectrally Constrained Optimization
• Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery
• Global Optimality in Distributed Low-rank Matrix Factorization
• How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?
• Optimized Structured Sparse Sensing Matrices for Compressive Sensing
• Spherical Principal Component Analysis
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms
• Multi-Head Encoding for Extreme Label Classification
• Zeroth-order optimisation on subsets of symmetric matrices with application to MPC tuning
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• Collaborative Self-Attention for Recommender Systems
• Second-Order Convergence of Asynchronous Parallel Stochastic Gradient Descent: When Is the Linear Speedup Achieved?
• On Application of Block Kaczmarz Methods in Matrix Factorization
• Learning Mixtures of Low-Rank Models