mlsanityData to 7 Oct 2026

Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction

arXiv 2106.15013 ↗First posted 28 Jun 2021cs.LG cs.IT math.ITcited by 77

Not on the map. Why?

Abstract (arXiv)

Recently there has been significant theoretical progress on understanding the convergence and generalization of gradient-based methods on nonconvex losses with overparameterized models. Nevertheless, many aspects of optimization and generalization and in particular the critical role of small random initialization are not fully understood. In this paper, we take a step towards demystifying this role by proving that small random initialization followed by a few iterations of gradient descent behaves akin to popular spectral methods. We also show that this implicit spectral bias from small random initialization, which is provably more prominent for overparameterized models, also puts the gradient descent iterations on a particular trajectory towards solutions that are not only globally optimal but also generalize well. Concretely, we focus on the problem of reconstructing a low-rank matrix from a few measurements via a natural nonconvex formulation. In this setting, we show that the trajectory of the gradient descent iterations from small random initialization can be approximately decomposed into three phases: (I) a spectral or alignment phase where we show that that the iterates have an implicit spectral bias akin to spectral initialization allowing us to show that at the end of this phase the column space of the iterates and the underlying low-rank matrix are sufficiently aligned, (II) a saddle avoidance/refinement phase where we show that the trajectory of the gradient iterates moves away from certain degenerate saddle points, and (III) a local refinement phase where we show that after avoiding the saddles the iterates converge quickly to the underlying low-rank matrix. Underlying our analysis are insights for the analysis of overparameterized nonconvex optimization schemes that may have implications for computational problems beyond low-rank reconstruction.

Key facts. Cited by 77 papers in the map (data through 7 Oct 2026). Builds on 47 of its 66 references that are in the map. First posted on arXiv 28 Jun 2021.

Builds on

47 of 66 references.

References · 47

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2018On Lazy Training in Differentiable Programmingcited by 671
  3. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  4. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  5. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
  6. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 422
  7. 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
  8. 2017Implicit Regularization in Matrix Factorizationcited by 318
  9. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 302
  10. 2017How to Escape Saddle Points Efficientlycited by 284
  11. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
  12. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
35 more
  1. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  2. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  3. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  4. 2018A Convergence Analysis of Gradient Descent for Deep Linear Neural Networkscited by 180
  5. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  6. 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
  7. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 148
  8. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  9. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 123
  10. 2020Implicit Regularization in Deep Learning May Not Be Explainable by Normscited by 118
  11. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 111
  12. 2018Mean Field Analysis of Neural Networks: A Central Limit Theoremcited by 107
  13. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  14. 2016A Geometric Analysis of Phase Retrievalcited by 92
  15. 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 87
  16. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  17. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 81
  18. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 79
  19. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  20. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  21. 2017A Hitting Time Analysis of Stochastic Gradient Langevin Dynamicscited by 70
  22. 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
  23. 2019Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizerscited by 61
  24. 2013Phase Retrieval using Alternating Minimizationcited by 58
  25. 2015Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systemscited by 50
  26. 2018Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networkscited by 44
  27. 2020Gradient Descent for Deep Matrix Factorization: Dynamics and Implicit Bias towards Low Rankcited by 42
  28. 2020Deep Networks and the Multiple Manifold Problemcited by 35
  29. 2015When Are Nonconvex Problems Not Scary?cited by 27
  30. 2019Analysis of a Two-Layer Neural Network via Displacement Convexitycited by 27
  31. 2019Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recoverycited by 26
  32. 2020Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTKcited by 18
  33. 2016Phase retrieval with random Gaussian sensing vectors by alternating projectionscited by 15
  34. 2020Beyond Lazy Training for Over-parameterized Tensor Decompositioncited by 15
  35. 2015Regularization-free estimation in trace regression with symmetric positive semidefinite matricescited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 14; 2023: 19; 2024: 21; 2025: 10; 2026: 11.

77 papers.

Sort:

By area:

  1. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  2. 2021Neural Networks as Kernel Learners: The Silent Alignment Effectcited by 106
  3. 2022Robust Training under Label Noise by Over-parameterizationcited by 93
  4. 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
  5. 2023Transformers as Support Vector Machinescited by 67
  6. 2023Transformers learn through gradual rank increasecited by 52
  7. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 40
  8. 2022Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descentcited by 38
  9. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  10. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  11. 2023Early Neuron Alignment in Two-layer ReLU Networks with Small Initializationcited by 28
  12. 2026Preconditioning Benefits of Spectral Orthogonalization in Muoncited by 28
38 more
  1. 2024Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptationcited by 26
  2. 2024Bayes-optimal learning of an extensive-width neural network from quadratically many samplescited by 23
  3. 2021More is Less: Inducing Sparsity via Overparameterizationcited by 22
  4. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  5. 2025PoLAR: Polar-Decomposed Low-Rank Adapter Representationcited by 19
  6. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  7. 2024Implicit Regularization of Gradient Flow on One-Layer Softmax Attentioncited by 16
  8. 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
  9. 2024On the Crucial Role of Initialization for Matrix Factorizationcited by 15
  10. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  11. 2023Provable Guarantees for Neural Networks via Gradient Feature Learningcited by 13
  12. 2025Understanding the Learning Dynamics of LoRA: A Gradient Flow Perspective on Low-Rank Adaptation in Matrix Factorizationcited by 13
  13. 2022Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensingcited by 11
  14. 2025Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networkscited by 11
  15. 2023Robust Implicit Regularization via Weight Normalizationcited by 10
  16. 2025Generalization or Hallucination? Understanding Out-of-Context Reasoning in Transformerscited by 10
  17. 2025From Condensation to Rank Collapse: A Two-Stage Analysis of Transformer Training Dynamicscited by 9
  18. 2022A Validation Approach to Over-parameterized Matrix and Image Recoverycited by 8
  19. 2023Canonical Factors for Hybrid Neural Fieldscited by 8
  20. 2024Guaranteed Nonconvex Factorization Approach for Tensor Train Recoverycited by 8
  21. 2024Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descentcited by 7
  22. 2023The Inductive Bias of Flatness Regularization for Deep Matrix Factorizationcited by 6
  23. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  24. 2024Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completioncited by 6
  25. 2024Early Directional Convergence in Deep Homogeneous Neural Networks for Small Initializationscited by 6
  26. 2023Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descentcited by 5
  27. 2023A Quadratic Synchronization Rule for Distributed Deep Learningcited by 5
  28. 2024Can Implicit Bias Imply Adversarial Robustness?cited by 5
  29. 2024Swing-by Dynamics in Concept Learning and Compositional Generalizationcited by 5
  30. 2022Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decompositioncited by 4
  31. 2022Rank-1 Matrix Completion with Gradient Descent and Small Random Initializationcited by 4
  32. 2023Implicit regularization in AI meets generalized hardness of approximation in optimization -- Sharp results for diagonal linear networkscited by 4
  33. 2024Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recoverycited by 4
  34. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  35. 2023Efficient Compression of Overparameterized Deep Models through Low-Dimensional Learning Dynamicscited by 3
  36. 2024Connectivity Shapes Implicit Regularization in Matrix Factorization Models for Matrix Completioncited by 3
  37. 2024Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexitycited by 3
  38. 2024Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networkscited by 3

50 most cited of 77 All 77 (JSON)