mlsanityData to 7 Oct 2026

Connectivity Shapes Implicit Regularization in Matrix Factorization Models for Matrix Completion

arXiv 2405.13721 ↗First posted 22 May 2024cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

Matrix factorization models have been extensively studied as a valuable test-bed for understanding the implicit biases of overparameterized models. Although both low nuclear norm and low rank regularization have been studied for these models, a unified understanding of when, how, and why they achieve different implicit regularization effects remains elusive. In this work, we systematically investigate the implicit regularization of matrix factorization for solving matrix completion problems. We empirically discover that the connectivity of observed data plays a crucial role in the implicit bias, with a transition from low nuclear norm to low rank as data shifts from disconnected to connected with increased observations. We identify a hierarchy of intrinsic invariant manifolds in the loss landscape that guide the training trajectory to evolve from low-rank to higher-rank solutions. Based on this finding, we theoretically characterize the training trajectory as following the hierarchical invariant manifold traversal process, generalizing the characterization of Li et al. (2020) to include the disconnected case. Furthermore, we establish conditions that guarantee minimum nuclear norm, closely aligning with our experimental findings, and we provide a dynamics characterization condition for ensuring minimum rank. Our work reveals the intricate interplay between data connectivity, training dynamics, and implicit regularization in matrix factorization models.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 27 of its 32 references that are in the map. First posted on arXiv 22 May 2024.

Builds on

27 of 32 references.

References · 27

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  3. 2018On Lazy Training in Differentiable Programmingcited by 671
  4. 2019Fantastic Generalization Measures and Where to Find Themcited by 507
  5. 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
  6. 2017Implicit Regularization in Matrix Factorizationcited by 318
  7. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  8. 2018Gradient descent aligns the layers of deep linear networkscited by 182
  9. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 148
  10. 2021Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariancescited by 125
  11. 2019Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networkscited by 122
  12. 2020Implicit Regularization in Deep Learning May Not Be Explainable by Normscited by 118
15 more
  1. 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
  2. 2021Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsitycited by 83
  3. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  4. 2020Phase diagram for two-layer ReLU neural networks at infinite-width limitcited by 65
  5. 2019The Implicit Bias of Depth: How Incremental Learning Drives Generalizationcited by 64
  6. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 40
  7. 2021Embedding Principle of Loss Landscape of Deep Neural Networkscited by 36
  8. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  9. 2021Towards Understanding the Condensation of Neural Networks at Initial Trainingcited by 31
  10. 2019Semi-flat minima and saddle points by embedding neural networks to overparameterizationcited by 29
  11. 2021Embedding Principle: a hierarchical structure of loss landscape of deep neural networkscited by 21
  12. 2020On implicit regularization: Morse functions and applications to matrix factorizationcited by 11
  13. 2022Embedding Principle in Depth for the Loss Landscape Analysis of Deep Neural Networkscited by 7
  14. 2022Linear Stability Hypothesis and Rank Stratification for Nonlinear Modelscited by 7
  15. 2023Optimistic Estimate Uncovers the Potential of Nonlinear Modelscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 1.

3 papers.

  1. 2025From Condensation to Rank Collapse: A Two-Stage Analysis of Transformer Training Dynamicscited by 9
  2. 2025Deep Hierarchical Learning with Nested Subspace Networks for Large Language Modelscited by 5
  3. 2026Gradient Flow Dynamics and Implicit Bias of Diagonal Linear Networks under Infinitesimal Initializationcited by 0