No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis

Abstract

In this paper we develop a new framework that captures the common landscape underlying the common non-convex low-rank matrix problems including matrix sensing, matrix completion and robust PCA. In particular, we show for all above problems (including asymmetric cases): 1) all local minima are also globally optimal; 2) no high-order saddle points exists. These results explain why simple algorithms such as stochastic gradient descent have global converge, and efficiently optimize these non-convex objective functions in practice. Our framework connects and simplifies the existing analyses on optimization landscapes for matrix sensing and symmetric matrix completion. The framework naturally leads to new results for asymmetric matrix completion and robust PCA.

References in corpus (2)

• Fast matrix completion without the condition number
• Accelerated Methods for Non-Convex Optimization

Cited by in corpus (97)

• Deep Learning is Robust to Massive Label Noise
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• An Analysis of the t-SNE Algorithm for Data Visualization
• First-order Methods Almost Always Avoid Saddle Points
• Implicit Regularization in Deep Matrix Factorization
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• How to Start Training: The Effect of Initialization and Architecture
• Stochastic Cubic Regularization for Fast Nonconvex Optimization
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• Convergence guarantees for a class of non-convex and non-smooth optimization problems
• Nonconvex Demixing From Bilinear Measurements
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Provable Subspace Tracking from Missing Data and Matrix Completion
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
• HePPCAT: Probabilistic PCA for Data with Heteroscedastic Noise
• Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Optimization Landscape of Tucker Decomposition
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• Limitations of Lazy Training of Two-layers Neural Networks
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Solving Complex Quadratic Systems with Full-Rank Random Matrices
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Provable quantum state tomography via non-convex methods
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
• Landscape Complexity for the Empirical Risk of Generalized Linear Models
• Thresholds of descending algorithms in inference problems
• Replica Exchange for Non-Convex Optimization
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Fast Low-Rank Matrix Estimation without the Condition Number
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
• Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery
• Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
• Landscape Connectivity and Dropout Stability of SGD Solutions for Over-parameterized Neural Networks
• Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery
• On Landscape of Lagrangian Functions and Stochastic Search for Constrained Nonconvex Optimization
• The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
• Implicit Regularization and Convergence for Weight Normalization
• General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
• Fast Convergence for Langevin Diffusion with Manifold Structure
• Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices
• Riemannian Perspective on Matrix Factorization
• The nonsmooth landscape of blind deconvolution
• Avoiding Spurious Local Minima in Deep Quadratic Networks
• Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect
• First-order methods almost always avoid saddle points: the case of vanishing step-sizes
• Sparse GCA and Thresholded Gradient Descent
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery
• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
• Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery
• Rank-one matrix estimation: analytic time evolution of gradient descent dynamics
• Low-Rank Matrix Completion: A Contemporary Survey
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization
• Global and Local Analyses of Nonlinear Low-Rank Matrix Recovery Problems
• A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
• Proximal algorithms for constrained composite optimization, with applications to solving low-rank SDPs
• Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
• NeuSE: A Neural Snapshot Ensemble Method for Collaborative Filtering
• Tensor Ring Decomposition: Optimization Landscape and One-loop Convergence of Alternating Least Squares
• Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models: Extension
• Global Convergence of Triangularized Orthogonalization-free Method
• Who is Afraid of Big Bad Minima? Analysis of Gradient-Flow in a Spiked Matrix-Tensor Model
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• Nonconvex Matrix Completion with Linearly Parameterized Factors
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Provable Exactness for Asymmetric Low-Rank SDP Learning
• Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics
• Collaborative Self-Attention for Recommender Systems
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
• On Recovering the Best Rank-r Approximation from Few Entries
• A Deterministic Gradient-Based Approach to Avoid Saddle Points
• Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience
• Error bound of critical points and KL property of exponent $1/2$ for squared F-norm regularized factorization
• Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics
• Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers
• On the Second-order Convergence Properties of Random Search Methods
• Provably convergent acceleration in factored gradient descent with applications in matrix sensing
• On The Convergence of First Order Methods for Quasar-Convex Optimization
• Learning Mixtures of Low-Rank Models
• Conditions for Exact Convex Relaxation and No Spurious Local Optima
• Stochastic Approximation for Online Tensorial Independent Component Analysis