Global Optimality of Local Search for Low Rank Matrix Recovery

Abstract

We show that there are no spurious local minima in the non-convex factorized parametrization of low-rank matrix recovery from incoherent linear measurements. With noisy measurements we show all local minima are very close to a global optimum. Together with a curvature bound at saddle points, this yields a polynomial time global convergence guarantee for stochastic gradient descent {\em from random initialization}.

arXiv comment21 pages, 3 figures

References in corpus (11)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Quantum state tomography via compressed sensing
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Large-scale Multi-label Learning with Missing Labels
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Matrix Completion has No Spurious Local Minimum
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• Dropping Convexity for Faster Semi-definite Optimization
• Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
• Computational Limits for Matrix Completion

Cited by in corpus (93)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Global rates of convergence for nonconvex optimization on manifolds
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• How to Escape Saddle Points Efficiently
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Global Optimality in Low-rank Matrix Optimization
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Implicit Full Waveform Inversion with Deep Neural Representation
• The Non-convex Geometry of Low-rank Matrix Optimization
• Implicit Regularization in Deep Matrix Factorization
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• Knowledge Graph Completion via Complex Tensor Factorization
• Nonconvex Demixing From Bilinear Measurements
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
• Introduction to Nonnegative Matrix Factorization
• The non-convex Burer-Monteiro approach works on smooth semidefinite programs
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• The basins of attraction of the global minimizers of the non-convex sparse spike estimation problem
• From Symmetry to Geometry: Tractable Nonconvex Problems
• HePPCAT: Probabilistic PCA for Data with Heteroscedastic Noise
• Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
• A Deterministic Theory for Exact Non-Convex Phase Retrieval
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery
• Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
• A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm
• The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension
• Revealing the Structure of Deep Neural Networks via Convex Duality
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• Optimization Landscape of Tucker Decomposition
• Finding Local Minima via Stochastic Nested Variance Reduction
• Solving Complex Quadratic Systems with Full-Rank Random Matrices
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• On the computational and statistical complexity of over-parameterized matrix sensing
• Landscape Complexity for the Empirical Risk of Generalized Linear Models
• Replica Exchange for Non-Convex Optimization
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• A Unified Framework for Low-Rank plus Sparse Matrix Recovery
• Almost Sure Convergence of Dropout Algorithms for Neural Networks
• How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
• Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
• Nonconvex Robust Low-rank Matrix Recovery
• Fast Low-Rank Matrix Estimation without the Condition Number
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems
• On Landscape of Lagrangian Functions and Stochastic Search for Constrained Nonconvex Optimization
• Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy
• Avoiding Spurious Local Minima in Deep Quadratic Networks
• First-order methods almost always avoid saddle points: the case of vanishing step-sizes
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
• The Global Optimization Geometry of Shallow Linear Neural Networks
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• Spectral Compressed Sensing via Projected Gradient Descent
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• Escaping spurious local minimum trajectories in online time-varying nonconvex optimization
• On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examples
• On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA
• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations
• Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization
• On the Quadratic Convergence of the Cubic Regularization Method under a Local Error Bound Condition
• Global and Local Analyses of Nonlinear Low-Rank Matrix Recovery Problems
• An equivalence between critical points for rank constraints versus low-rank factorizations
• PCA by Optimisation of Symmetric Functions has no Spurious Local Optima
• A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• Who is Afraid of Big Bad Minima? Analysis of Gradient-Flow in a Spiked Matrix-Tensor Model
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
• PCA by Determinant Optimization has no Spurious Local Optima
• Enhanced image approximation using shifted rank-1 reconstruction
• Provably convergent acceleration in factored gradient descent with applications in matrix sensing
• Error bound of critical points and KL property of exponent $1/2$ for squared F-norm regularized factorization
• Learning Mixtures of Low-Rank Models
• Asynchronous Parallel Nonconvex Optimization Under the Polyak-Lojasiewicz Condition
• Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
• CNNs are Globally Optimal Given Multi-Layer Support
• Learning in Gated Neural Networks