# Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regime

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 49 references that are in the map.
- First posted on arXiv 21 Apr 2021.

## Builds on (most cited first, 20 of 20)

- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [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)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems](https://mlsanity.com/paper/1505.05114/) (2015)
- [Dropping Convexity for Faster Semi-definite Optimization](https://mlsanity.com/paper/1509.03917/) (2015)
- [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016)
- [Global Optimality in Low-rank Matrix Optimization](https://mlsanity.com/paper/1702.07945/) (2017)
- [A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements](https://mlsanity.com/paper/1506.06081/) (2015)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery](https://mlsanity.com/paper/1901.01631/) (2019)
- [On the low-rank approach for semidefinite programs arising in synchronization and community detection](https://mlsanity.com/paper/1602.04426/) (2016)
- [Polynomial time guarantees for the Burer-Monteiro method](https://mlsanity.com/paper/1912.01745/) (2019)
- [Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form](https://mlsanity.com/paper/1803.00186/) (2018)
- [Solving Orthogonal Group Synchronization via Convex and Low-Rank Optimization: Tightness and Landscape Analysis](https://mlsanity.com/paper/2006.00902/) (2020)
- [How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?](https://mlsanity.com/paper/2006.06915/) (2020)
- [How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?](https://mlsanity.com/paper/1805.10251/) (2018)

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

- [Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization](https://mlsanity.com/paper/2202.08788/) (2022)
- [Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima](https://mlsanity.com/paper/2505.03717/) (2025)
- [Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO](https://mlsanity.com/paper/2608.29018/) (2026)
- [A Fine-Grained Analysis of the LoRA Fine-Tuning Landscape with Implications for Data Selection](https://mlsanity.com/paper/2610.06542/) (2026)
- [Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustness](https://mlsanity.com/paper/2610.18318/) (2026)

## Abstract (arXiv)

Recent work established that rank overparameterization eliminates spurious local minima in nonconvex low-rank matrix recovery under the restricted isometry property (RIP). But this does not fully explain the practical success of overparameterization, because real algorithms can still become trapped at nonstrict saddle points (approximate second-order points with arbitrarily small negative curvature) even when all local minima are global. Moreover, the result does not accommodate for noisy measurements, but it is unclear whether such an extension is even possible, in view of the many discontinuous and unintuitive behaviors already known for the overparameterized regime. In this paper, we introduce a novel proof technique that unifies, simplifies, and strengthens two previously competing approaches -- one based on escape directions and the other based on the inexistence of counterexample -- to provide sharp global guarantees in the noisy overparameterized regime. We show, once local minima have been converted into global minima through slight overparameterization, that near-second-order points achieve the same minimax-optimal recovery bounds (up to small constant factors) as significantly more expensive convex approaches. Our results are sharp with respect to the noise level and the solution accuracy, and hold for both the symmetric parameterization XXT, as well as the asymmetric parameterization UVT under a balancing regularizer; we demonstrate that the balancing regularizer is indeed necessary.