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 (6)

• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• 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

Cited by in corpus (43)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• 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
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• Loss Landscapes of Regularized Linear Autoencoders
• 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
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• 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
• Gradient descent with nonconvex constraints: local concavity determines convergence
• Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization
• Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery
• Nonconvex Robust Low-rank Matrix Recovery
• Convolutional Geometric Matrix Completion
• General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
• Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery
• Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
• The Global Optimization Geometry of Shallow Linear Neural Networks
• Alternating Iteratively Reweighted Minimization Algorithms for Low-Rank Matrix Factorization
• Spectrally Constrained Optimization
• How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?
• Global Optimality in Distributed Low-rank Matrix Factorization
• Optimized Structured Sparse Sensing Matrices for Compressive Sensing
• Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery
• Spherical Principal Component Analysis
• 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
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
• Collaborative Self-Attention for Recommender Systems
• Second-Order Convergence of Asynchronous Parallel Stochastic Gradient Descent: When Is the Linear Speedup Achieved?
• Learning Mixtures of Low-Rank Models
• On Application of Block Kaczmarz Methods in Matrix Factorization