# Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 70 references that are in the map.
- First posted on arXiv 9 Oct 2023.

## Builds on (most cited first, 30 of 49)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [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)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [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)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [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)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (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)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [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)
- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Non-convex Robust PCA](https://mlsanity.com/paper/1410.7660/) (2014)
- [Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent](https://mlsanity.com/paper/1605.07051/) (2016)
- [Fast Algorithms for Robust PCA via Gradient Descent](https://mlsanity.com/paper/1605.07784/) (2016)
- [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020)
- [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)
- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [On Tensor Completion via Nuclear Norm Minimization](https://mlsanity.com/paper/1405.1773/) (2014)

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

- [Riemannian Preconditioned LoRA for Fine-Tuning Foundation Models](https://mlsanity.com/paper/2402.02347/) (2024)
- [EigenLoRAx: Recycling Adapters to Find Principal Subspaces for Resource-Efficient Adaptation and Inference](https://mlsanity.com/paper/2502.04700/) (2025)
- [A Stronger Mixture of Low-Rank Experts for Fine-Tuning Foundation Models](https://mlsanity.com/paper/2502.15828/) (2025)
- [Efficient Compression of Overparameterized Deep Models through Low-Dimensional Learning Dynamics](https://mlsanity.com/paper/2311.05061/) (2023)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [On the Benefits of Weight Normalization for Overparameterized Matrix Sensing](https://mlsanity.com/paper/2510.01175/) (2025)

## Abstract (arXiv)

Many problems encountered in science and engineering can be formulated as estimating a low-rank object (e.g., matrices and tensors) from incomplete, and possibly corrupted, linear measurements. Through the lens of matrix and tensor factorization, one of the most popular approaches is to employ simple iterative algorithms such as gradient descent (GD) to recover the low-rank factors directly, which allow for small memory and computation footprints. However, the convergence rate of GD depends linearly, and sometimes even quadratically, on the condition number of the low-rank object, and therefore, GD slows down painstakingly when the problem is ill-conditioned. This chapter introduces a new algorithmic approach, dubbed scaled gradient descent (ScaledGD), that provably converges linearly at a constant rate independent of the condition number of the low-rank object, while maintaining the low per-iteration cost of gradient descent for a variety of tasks including sensing, robust principal component analysis and completion. In addition, ScaledGD continues to admit fast global convergence to the minimax-optimal solution, again almost independent of the condition number, from a small random initialization when the rank is over-specified in the presence of Gaussian noise. In total, ScaledGD highlights the power of appropriate preconditioning in accelerating nonconvex statistical estimation, where the iteration-varying preconditioners promote desirable invariance properties of the trajectory with respect to the symmetry in low-rank factorization without hurting generalization.