# Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization arXiv: https://arxiv.org/abs/2504.09708 · HTML: https://mlsanity.com/paper/2504.09708/ ## Key facts - Cited by 12 papers in the map (data through 7 Oct 2026). - Builds on 23 of its 55 references that are in the map. - First posted on arXiv 13 Apr 2025. ## Builds on (most cited first, 23 of 23) - [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015) - [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017) - [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015) - [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) - [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014) - [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015) - [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016) - [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) - [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020) - [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015) - [Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture](https://mlsanity.com/paper/1511.03607/) (2015) - [Non-convex Robust PCA](https://mlsanity.com/paper/1410.7660/) (2014) - [Dropping Convexity for Faster Semi-definite Optimization](https://mlsanity.com/paper/1509.03917/) (2015) - [Fast Algorithms for Robust PCA via Gradient Descent](https://mlsanity.com/paper/1605.07784/) (2016) - [A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements](https://mlsanity.com/paper/1506.06081/) (2015) - [Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number](https://mlsanity.com/paper/2010.13364/) (2020) - [Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery](https://mlsanity.com/paper/1901.01631/) (2019) - [Fast matrix completion without the condition number](https://mlsanity.com/paper/1407.4070/) (2014) - [Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization](https://mlsanity.com/paper/1702.06175/) (2017) - [How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?](https://mlsanity.com/paper/1805.10251/) (2018) - [Chordal decomposition in operator-splitting methods for sparse semidefinite programs](https://mlsanity.com/paper/1707.05058/) (2017) ## Built on by (most cited first, 12 of 12) - [Preconditioning Benefits of Spectral Orthogonalization in Muon](https://mlsanity.com/paper/2601.13474/) (2026) - [PoLAR: Polar-Decomposed Low-Rank Adapter Representation](https://mlsanity.com/paper/2506.03133/) (2025) - [AltLoRA: Towards Better Gradient Approximation in Low-Rank Adaptation with Alternating Projections](https://mlsanity.com/paper/2505.12455/) (2025) - [On the Benefits of Weight Normalization for Overparameterized Matrix Sensing](https://mlsanity.com/paper/2510.01175/) (2025) - [Convergence Dynamics of Over-Parameterized Score Matching for a Single Gaussian](https://mlsanity.com/paper/2511.22069/) (2025) - [Low-Rank Adaptation Redux for Large Models](https://mlsanity.com/paper/2604.21905/) (2026) - [Faster Than SVD, Smarter Than SGD: The OPLoRA Alternating Update](https://mlsanity.com/paper/2509.19977/) (2025) - [Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2512.07490/) (2025) - [RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees](https://mlsanity.com/paper/2505.12919/) (2025) - [Beyond SGD, Without SVD: Proximal Subspace Iteration LoRA with Diagonal Fractional K-FAC](https://mlsanity.com/paper/2602.16456/) (2026) - [Scaled Gradient Descent for Ill-Conditioned Low-Rank Matrix Recovery with Optimal Sampling Complexity](https://mlsanity.com/paper/2604.00060/) (2026) - [Reassessing Muon for Matrix Factorization](https://mlsanity.com/paper/2607.13246/) (2026) ## Abstract (arXiv) In practical instances of nonconvex matrix factorization, the rank of the true solution rstar is often unknown, so the rank r of the model can be overspecified as r>rstar. This over-parameterized regime of matrix factorization significantly slows down the convergence of local search algorithms, from a linear rate with r=rstar to a sublinear rate when r>rstar. We propose an inexpensive preconditioner for the matrix sensing variant of nonconvex matrix factorization that restores the convergence rate of gradient descent back to linear, even in the over-parameterized case, while also making it agnostic to possible ill-conditioning in the ground truth. Classical gradient descent in a neighborhood of the solution slows down due to the need for the model matrix factor to become singular. Our key result is that this singularity can be corrected by ℓ2 regularization with a specific range of values for the damping parameter. In fact, a good damping parameter can be inexpensively estimated from the current iterate. The resulting algorithm, which we call preconditioned gradient descent or PrecGD, is stable under noise, and converges linearly to an information theoretically optimal error bound. Our numerical experiments find that PrecGD works equally well in restoring the linear convergence of other variants of nonconvex matrix factorization in the over-parameterized regime.