Global Optimality of Local Search for Low Rank Matrix Recovery

2016/05/23 by Srinadh Bhojanapalli, Behnam Neyshabur, Bhojanapalli, Srinadh +3 · 1 voice · 23 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Microwave Imaging and Scattering Analysis #Numerical methods in inverse problems #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #cs.LG #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.1605.07221

21 pages, 3 figures

openalex publication_date 2016/05/23 · arxiv published 2016/05/23 · arxiv created 2016/05/27 · arxiv updated 2016/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Large-scale Multi-label Learning with Missing Labels
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Local Minima and Convergence in Low-Rank Semidefinite Programming
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Cited by

• On computing Goldstein approximate second-order stationary points of structured nonsmooth nonconvex programs
• Continuized Nesterov Acceleration for Non-Convex Optimization
• Smooth Quasar-Convex Optimization with Constraints
• Scalable Second-order Riemannian Optimization for K-means Clustering
• Convergence Analysis of the PAGE Stochastic Algorithm for Weakly Convex Finite-Sum Optimization
• Sensor network localization has a benign landscape after low-dimensional relaxation
• How to Escape Saddle Points Efficiently
• The Global Optimization Geometry of Shallow Linear Neural Networks
• The basins of attraction of the global minimizers of the non-convex sparse spike estimation problem
• Second-order methods for provably escaping strict saddle points in composite nonconvex and nonsmooth optimization
• A Complete Loss Landscape Analysis of Regularized Deep Matrix Factorization
• Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization
• Phase retrieval with rank d measurements -- descending algorithms phase transitions
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima
• Enhanced image approximation using shifted rank-1 reconstruction
• One Rank at a Time: Cascading Error Dynamics in Sequential Learning
• Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework
• A Deterministic Theory for Exact Non-Convex Phase Retrieval
• Nonconvex Demixing From Bilinear Measurements
• Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization

Discussions

• Global Optimality of Local Search for Low Rank Matrix Recovery [hn, 1 points, 0 comments]

Related

• Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?
• How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
• Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurements
• Local and Global Linear Convergence of General Low-rank Matrix Recovery Problems
• Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regime