mlsanityData to 14 Oct 2026

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

arXiv 2301.11500 ↗First posted 27 Jan 2023cs.LG math.OC stat.MLcited by 42

Not on the map. Why?

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.

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

41 of 64 references.

References · 41

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  2. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  3. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  4. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  5. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  6. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  7. 2017Implicit Regularization in Matrix Factorizationcited by 322
  8. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
  9. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  10. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  11. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
  12. 2019SGD on Neural Networks Learns Functions of Increasing Complexitycited by 204
29 more
  1. 2020Directional convergence and alignment in deep learningcited by 178
  2. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 150
  3. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 129
  4. 2016Matrix Completion has No Spurious Local Minimumcited by 125
  5. 2019Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networkscited by 124
  6. 2019Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like processcited by 123
  7. 2021Label Noise SGD Provably Prefers Flat Global Minimizerscited by 121
  8. 2020Implicit Regularization in Deep Learning May Not Be Explainable by Normscited by 119
  9. 2021What Happens after SGD Reaches Zero Loss? --A Mathematical Frameworkcited by 107
  10. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  11. 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
  12. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 83
  13. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 78
  14. 2022Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputscited by 76
  15. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 71
  16. 2019Optimization for deep learning: theory and algorithmscited by 70
  17. 2019The Implicit Bias of Depth: How Incremental Learning Drives Generalizationcited by 64
  18. 2020The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networkscited by 58
  19. 2019Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Modelscited by 53
  20. 2022Implicit Regularization Towards Rank Minimization in ReLU Networkscited by 53
  21. 2021Implicit Regularization in Tensor Factorizationcited by 44
  22. 2022Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descentcited by 39
  23. 2017Global Optimality in Low-rank Matrix Optimizationcited by 36
  24. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  25. 2022Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networkscited by 27
  26. 2017The Global Optimization Geometry of Low-Rank Matrix Optimizationcited by 25
  27. 2013Gradient methods for convex minimization: better rates under weaker conditionscited by 23
  28. 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
  29. 2020On implicit regularization: Morse functions and applications to matrix factorizationcited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 14; 2024: 13; 2025: 10; 2026: 5.

42 papers.

Sort:

By area:

  1. 2023Trained Transformers Learn Linear Models In-Contextcited by 337
  2. 2023Saddle-to-Saddle Dynamics in Diagonal Linear Networkscited by 57
  3. 2023Transformers learn through gradual rank increasecited by 52
  4. 2024LoRA Training in the NTK Regime has No Spurious Local Minimacited by 48
  5. 2025PoLAR: Polar-Decomposed Low-Rank Adapter Representationcited by 20
  6. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  7. 2024Mixed Dynamics In Linear Networks: Unifying the Lazy and Active Regimescited by 18
  8. 2023Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputscited by 16
  9. 2025Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Pointscited by 16
  10. 2024On the Crucial Role of Initialization for Matrix Factorizationcited by 15
  11. 2025Understanding the Learning Dynamics of LoRA: A Gradient Flow Perspective on Low-Rank Adaptation in Matrix Factorizationcited by 13
  12. 2024Directional Convergence Near Small Initializations and Saddles in Two-Homogeneous Neural Networkscited by 11
30 more
  1. 2025Towards Understanding Text Hallucination of Diffusion Models via Local Generation Biascited by 11
  2. 2024The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimizationcited by 8
  3. 2024Early Directional Convergence in Deep Homogeneous Neural Networks for Small Initializationscited by 7
  4. 2025On Learning Verifiers and Implications to Chain-of-Thought Reasoningcited by 6
  5. 2023Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descentcited by 5
  6. 2023A Quadratic Synchronization Rule for Distributed Deep Learningcited by 5
  7. 2024Task Diversity Shortens the ICL Plateaucited by 5
  8. 2024Swing-by Dynamics in Concept Learning and Compositional Generalizationcited by 5
  9. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  10. 2023Efficient Compression of Overparameterized Deep Models through Low-Dimensional Learning Dynamicscited by 3
  11. 2024Connectivity Shapes Implicit Regularization in Matrix Factorization Models for Matrix Completioncited by 3
  12. 2024Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexitycited by 3
  13. 2025One Rank at a Time: Cascading Error Dynamics in Sequential Learningcited by 3
  14. 2025On the Benefits of Weight Normalization for Overparameterized Matrix Sensingcited by 3
  15. 2023Gradient descent in matrix factorization: Understanding large initializationcited by 2
  16. 2023Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbationscited by 2
  17. 2024The Implicit Bias of Heterogeneity towards Invariance: A Study of Multi-Environment Matrix Sensingcited by 2
  18. 2025Neural Collapse under Gradient Flow on Shallow ReLU Networks for Orthogonally Separable Datacited by 2
  19. 2026Incremental Learning of Sparse Attention Patterns in Transformerscited by 2
  20. 2023Greedy Pruning with Group Lasso Provably Generalizes for Matrix Sensingcited by 1
  21. 2023Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensingcited by 1
  22. 2024Absence of spurious solutions far from ground truth: A low-rank analysis with high-order lossescited by 1
  23. 2024Lecture Notes on Linear Neural Networks: A Tale of Optimization and Generalization in Deep Learningcited by 1
  24. 2025Understanding Incremental Learning with Closed-form Solution to Gradient Flow on Overparamerterized Matrix Factorizationcited by 1
  25. 2023Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensingcited by 0
  26. 2023Sparse Mean Estimation in Adversarial Settings via Incremental Learningcited by 0
  27. 2026Near-optimal and Efficient First-Order Algorithm for Multi-Task Learning with Shared Linear Representationcited by 0
  28. 2026Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamicscited by 0
  29. 2026Ideal Paths for Approximating Logistic Gradient Descent Trajectories at Large Initializationcited by 0
  30. 2026Optimizer Geometry Sets the Pace: Spectral Learning Dynamics in Matrix Factorizationcited by 0