No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
arXiv:1704.00708
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 (12)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
- An overview of low-rank matrix recovery from incomplete observations
- Guaranteed Matrix Completion via Non-convex Factorization
- Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Matrix Completion has No Spurious Local Minimum
- Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
- Fast matrix completion without the condition number
- Accelerated Methods for Non-Convex Optimization
- Dropping Convexity for Faster Semi-definite Optimization
- Recovery guarantee of weighted low-rank approximation via alternating minimization
Cited by in corpus (101)
- 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
- Global Optimality in Low-rank Matrix Optimization
- The Non-convex Geometry of Low-rank Matrix Optimization
- 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
- HePPCAT: Probabilistic PCA for Data with Heteroscedastic Noise
- Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
- The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
- Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
- Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
- Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
- Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
- 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
- Solving Complex Quadratic Systems with Full-Rank Random Matrices
- Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
- Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
- Limitations of Lazy Training of Two-layers Neural Networks
- How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
- Nonconvex Rectangular Matrix Completion via Gradient Descent without Regularization
- On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
- Provable quantum state tomography via non-convex methods
- 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
- General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
- On Landscape of Lagrangian Functions and Stochastic Search for Constrained Nonconvex Optimization
- Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery
- Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
- Implicit Regularization and Convergence for Weight Normalization
- Landscape Connectivity and Dropout Stability of SGD Solutions for Over-parameterized Neural Networks
- The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
- Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect
- First-order methods almost always avoid saddle points: the case of vanishing step-sizes
- Fast Convergence for Langevin Diffusion with Manifold Structure
- Riemannian Perspective on Matrix Factorization
- Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices
- Avoiding Spurious Local Minima in Deep Quadratic Networks
- The nonsmooth landscape of blind deconvolution
- Sparse GCA and Thresholded Gradient Descent
- Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
- Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
- Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery
- Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery
- On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
- Low-Rank Matrix Completion: A Contemporary Survey
- Rank-one matrix estimation: analytic time evolution of gradient descent dynamics
- Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization
- A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees
- Global and Local Analyses of Nonlinear Low-Rank Matrix Recovery Problems
- Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
- Who is Afraid of Big Bad Minima? Analysis of Gradient-Flow in a Spiked Matrix-Tensor Model
- Global Convergence of Triangularized Orthogonalization-free Method
- Lecture notes on non-convex algorithms for low-rank matrix recovery
- 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
- Proximal algorithms for constrained composite optimization, with applications to solving low-rank SDPs
- Nonconvex Matrix Completion with Linearly Parameterized Factors
- NeuSE: A Neural Snapshot Ensemble Method for Collaborative Filtering
- Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
- Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models: Extension
- Tensor Ring Decomposition: Optimization Landscape and One-loop Convergence of Alternating Least Squares
- Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
- Conditions for Exact Convex Relaxation and No Spurious Local Optima
- Provably convergent acceleration in factored gradient descent with applications in matrix sensing
- Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers
- On the Second-order Convergence Properties of Random Search Methods
- Collaborative Self-Attention for Recommender Systems
- Learning Mixtures of Low-Rank Models
- Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
- On The Convergence of First Order Methods for Quasar-Convex Optimization
- A Deterministic Gradient-Based Approach to Avoid Saddle Points
- Error bound of critical points and KL property of exponent for squared F-norm regularized factorization
- On Recovering the Best Rank-r Approximation from Few Entries
- Provable Exactness for Asymmetric Low-Rank SDP Learning
- Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling
- Stochastic Approximation for Online Tensorial Independent Component Analysis
- Towards Understanding Generalization via Decomposing Excess Risk Dynamics
- Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics
- Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience