Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?
Not on the map. Why?
Abstract (arXiv)
We explore the local landscape of low-rank matrix recovery, focusing on reconstructing a d1× d2 matrix X^star with rank r from m linear measurements, some potentially noisy. When the noise is distributed according to an outlier model, minimizing a nonsmooth ℓ1-loss with a simple sub-gradient method can often perfectly recover the ground truth matrix X^star. Given this, a natural question is what optimization property (if any) enables such learning behavior. The most plausible answer is that the ground truth X^star manifests as a local optimum of the loss function. In this paper, we provide a strong negative answer to this question, showing that, under moderate assumptions, the true solutions corresponding to X^star do not emerge as local optima, but rather as strict saddle points -- critical points with strictly negative curvature in at least one direction. Our findings challenge the conventional belief that all strict saddle points are undesirable and should be avoided.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 28 of its 54 references that are in the map. First posted on arXiv 21 Feb 2023.
Builds on
28 of 54 references.
References · 28
- 2014Identifying and attacking the saddle point problem in high-dimensional non-convex optimizationcited by 289
- 2017How to Escape Saddle Points Efficientlycited by 285
- 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 160
- 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 129
- 2016Matrix Completion has No Spurious Local Minimumcited by 125
- 2016A Geometric Analysis of Phase Retrievalcited by 92
- 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 82
- 2019Optimization for deep learning: theory and algorithmscited by 70
- 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
- 2017Global Optimality in Low-rank Matrix Optimizationcited by 36
- 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 33
- 2019Low-rank matrix recovery with composite optimization: good conditioning and rapid convergencecited by 31
16 more
- 2020From Symmetry to Geometry: Tractable Nonconvex Problemscited by 29
- 2020Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Numbercited by 28
- 2013Incoherence-Optimal Matrix Completioncited by 27
- 2017The Global Optimization Geometry of Low-Rank Matrix Optimizationcited by 25
- 2018Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimationcited by 25
- 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 22
- 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
- 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
- 2020Understanding Notions of Stationarity in Non-Smooth Optimizationcited by 18
- 2018Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysiscited by 13
- 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
- 2021Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recoverycited by 10
- 2021Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functionscited by 9
- 2021Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurementscited by 7
- 2021Escaping strict saddle points of the Moreau envelope in nonsmooth optimizationcited by 7
- 2022Nonsmooth rank-one matrix factorization landscapecited by 1
Built on by
Citing papers per year: 2024: 1; 2025: 0; 2026: 1.
2 papers.