# Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 64 references that are in the map.
- First posted on arXiv 27 Jan 2023.

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [SGD on Neural Networks Learns Functions of Increasing Complexity](https://mlsanity.com/paper/1905.11604/) (2019)
- [Directional convergence and alignment in deep learning](https://mlsanity.com/paper/2006.06657/) (2020)
- [Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning](https://mlsanity.com/paper/2012.09839/) (2020)
- [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)
- [Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks](https://mlsanity.com/paper/1904.13262/) (2019)
- [Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process](https://mlsanity.com/paper/1904.09080/) (2019)
- [Label Noise SGD Provably Prefers Flat Global Minimizers](https://mlsanity.com/paper/2106.06530/) (2021)
- [Implicit Regularization in Deep Learning May Not Be Explainable by Norms](https://mlsanity.com/paper/2005.06398/) (2020)
- [What Happens after SGD Reaches Zero Loss? --A Mathematical Framework](https://mlsanity.com/paper/2110.06914/) (2021)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Understanding the Generalization Benefit of Normalization Layers: Sharpness Reduction](https://mlsanity.com/paper/2206.07085/) (2022)
- [Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias](https://mlsanity.com/paper/2110.13905/) (2021)
- [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)
- [Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs](https://mlsanity.com/paper/2206.00939/) (2022)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Optimization for deep learning: theory and algorithms](https://mlsanity.com/paper/1912.08957/) (2019)
- [The Implicit Bias of Depth: How Incremental Learning Drives Generalization](https://mlsanity.com/paper/1909.12051/) (2019)
- [The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks](https://mlsanity.com/paper/2006.14599/) (2020)

## Built on by (most cited first, 30 of 42)

- [Trained Transformers Learn Linear Models In-Context](https://mlsanity.com/paper/2306.09927/) (2023)
- [Saddle-to-Saddle Dynamics in Diagonal Linear Networks](https://mlsanity.com/paper/2304.00488/) (2023)
- [Transformers learn through gradual rank increase](https://mlsanity.com/paper/2306.07042/) (2023)
- [LoRA Training in the NTK Regime has No Spurious Local Minima](https://mlsanity.com/paper/2402.11867/) (2024)
- [PoLAR: Polar-Decomposed Low-Rank Adapter Representation](https://mlsanity.com/paper/2506.03133/) (2025)
- [How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization](https://mlsanity.com/paper/2310.01769/) (2023)
- [Mixed Dynamics In Linear Networks: Unifying the Lazy and Active Regimes](https://mlsanity.com/paper/2405.17580/) (2024)
- [Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs](https://mlsanity.com/paper/2306.06479/) (2023)
- [Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Points](https://mlsanity.com/paper/2508.12837/) (2025)
- [On the Crucial Role of Initialization for Matrix Factorization](https://mlsanity.com/paper/2410.18965/) (2024)
- [Understanding the Learning Dynamics of LoRA: A Gradient Flow Perspective on Low-Rank Adaptation in Matrix Factorization](https://mlsanity.com/paper/2503.06982/) (2025)
- [Directional Convergence Near Small Initializations and Saddles in Two-Homogeneous Neural Networks](https://mlsanity.com/paper/2402.09226/) (2024)
- [Towards Understanding Text Hallucination of Diffusion Models via Local Generation Bias](https://mlsanity.com/paper/2503.03595/) (2025)
- [The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimization](https://mlsanity.com/paper/2409.09745/) (2024)
- [Early Directional Convergence in Deep Homogeneous Neural Networks for Small Initializations](https://mlsanity.com/paper/2403.08121/) (2024)
- [On Learning Verifiers and Implications to Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.22650/) (2025)
- [Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent](https://mlsanity.com/paper/2305.17224/) (2023)
- [A Quadratic Synchronization Rule for Distributed Deep Learning](https://mlsanity.com/paper/2310.14423/) (2023)
- [Task Diversity Shortens the ICL Plateau](https://mlsanity.com/paper/2410.05448/) (2024)
- [Swing-by Dynamics in Concept Learning and Compositional Generalization](https://mlsanity.com/paper/2410.08309/) (2024)
- [Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2502.00463/) (2025)
- [Efficient Compression of Overparameterized Deep Models through Low-Dimensional Learning Dynamics](https://mlsanity.com/paper/2311.05061/) (2023)
- [Connectivity Shapes Implicit Regularization in Matrix Factorization Models for Matrix Completion](https://mlsanity.com/paper/2405.13721/) (2024)
- [Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity](https://mlsanity.com/paper/2408.13276/) (2024)
- [One Rank at a Time: Cascading Error Dynamics in Sequential Learning](https://mlsanity.com/paper/2505.22602/) (2025)
- [On the Benefits of Weight Normalization for Overparameterized Matrix Sensing](https://mlsanity.com/paper/2510.01175/) (2025)
- [Gradient descent in matrix factorization: Understanding large initialization](https://mlsanity.com/paper/2305.19206/) (2023)
- [Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbations](https://mlsanity.com/paper/2309.01796/) (2023)
- [The Implicit Bias of Heterogeneity towards Invariance: A Study of Multi-Environment Matrix Sensing](https://mlsanity.com/paper/2403.01420/) (2024)
- [Neural Collapse under Gradient Flow on Shallow ReLU Networks for Orthogonally Separable Data](https://mlsanity.com/paper/2510.21078/) (2025)

## Abstract (arXiv)

It is believed that Gradient Descent (GD) induces an implicit bias towards good generalization in training machine learning models. This paper provides a fine-grained analysis of the dynamics of GD for the matrix sensing problem, whose goal is to recover a low-rank ground-truth matrix from near-isotropic linear measurements. It is shown that GD with small initialization behaves similarly to the greedy low-rank learning heuristics (Li et al., 2020) and follows an incremental learning procedure (Gissin et al., 2019): GD sequentially learns solutions with increasing ranks until it recovers the ground truth matrix. Compared to existing works which only analyze the first learning phase for rank-1 solutions, our result provides characterizations for the whole learning process. Moreover, besides the over-parameterized regime that many prior works focused on, our analysis of the incremental learning procedure also applies to the under-parameterized regime. Finally, we conduct numerical experiments to confirm our theoretical findings.