# Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?

arXiv: https://arxiv.org/abs/2302.10963 · HTML: https://mlsanity.com/paper/2302.10963/

## 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 (most cited first, 28 of 28)

- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [Optimization for deep learning: theory and algorithms](https://mlsanity.com/paper/1912.08957/) (2019)
- [Sharp Analysis for Nonconvex SGD Escaping from Saddle Points](https://mlsanity.com/paper/1902.00247/) (2019)
- [Global Optimality in Low-rank Matrix Optimization](https://mlsanity.com/paper/1702.07945/) (2017)
- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence](https://mlsanity.com/paper/1904.10020/) (2019)
- [From Symmetry to Geometry: Tractable Nonconvex Problems](https://mlsanity.com/paper/2007.06753/) (2020)
- [Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number](https://mlsanity.com/paper/2010.13364/) (2020)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [The Global Optimization Geometry of Low-Rank Matrix Optimization](https://mlsanity.com/paper/1703.01256/) (2017)
- [Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation](https://mlsanity.com/paper/1802.08397/) (2018)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization](https://mlsanity.com/paper/2202.08788/) (2022)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [Understanding Notions of Stationarity in Non-Smooth Optimization](https://mlsanity.com/paper/2006.14901/) (2020)
- [Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis](https://mlsanity.com/paper/1812.11466/) (2018)
- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (2022)
- [Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery](https://mlsanity.com/paper/2102.02969/) (2021)
- [Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functions](https://mlsanity.com/paper/2108.02072/) (2021)
- [Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurements](https://mlsanity.com/paper/2105.08232/) (2021)
- [Escaping strict saddle points of the Moreau envelope in nonsmooth optimization](https://mlsanity.com/paper/2106.09815/) (2021)
- [Nonsmooth rank-one matrix factorization landscape](https://mlsanity.com/paper/2211.14848/) (2022)

## Built on by (most cited first, 2 of 2)

- [Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion](https://mlsanity.com/paper/2402.06756/) (2024)
- [Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Lifting](https://mlsanity.com/paper/2602.05887/) (2026)

## 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.