mlsanityData to 7 Oct 2026

Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization

arXiv 2203.02839 ↗First posted 6 Mar 2022cs.LG math.OC stat.MLcited by 34

Not on the map. Why?

Abstract (arXiv)

We study the asymmetric matrix factorization problem under a natural nonconvex formulation with arbitrary overparametrization. The model-free setting is considered, with minimal assumption on the rank or singular values of the observed matrix, where the global optima provably overfit. We show that vanilla gradient descent with small random initialization sequentially recovers the principal components of the observed matrix. Consequently, when equipped with proper early stopping, gradient descent produces the best low-rank approximation of the observed matrix without explicit regularization. We provide a sharp characterization of the relationship between the approximation error, iteration complexity, initialization size and stepsize. Our complexity bound is almost dimension-free and depends logarithmically on the approximation error, with significantly more lenient requirements on the stepsize and initialization compared to prior work. Our theoretical results provide accurate prediction for the behavior gradient descent, showing good agreement with numerical experiments.

Key facts. Cited by 34 papers in the map (data through 7 Oct 2026). Builds on 16 of its 29 references that are in the map. First posted on arXiv 6 Mar 2022.

Builds on

16 of 29 references.

References · 16

  1. 2019EfficientNet: Rethinking Model Scaling for Convolutional Neural Networkscited by 6,415
  2. 2019Big Transfer (BiT): General Visual Representation Learningcited by 766
  3. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 302
  4. 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 172
  5. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  6. 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
  7. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  8. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  9. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
  10. 2021Early Stopping for Deep Image Priorcited by 44
  11. 2020Gradient Descent for Deep Matrix Factorization: Dynamics and Implicit Bias towards Low Rankcited by 42
  12. 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 37
4 more
  1. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  2. 2018Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimationcited by 25
  3. 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 21
  4. 2021Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recoverycited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 11; 2024: 8; 2025: 8; 2026: 3.

34 papers.

Sort:

  1. 2025SD-LoRA: Scalable Decoupled Low-Rank Adaptation for Class Incremental Learningcited by 60
  2. 2023Saddle-to-Saddle Dynamics in Diagonal Linear Networkscited by 54
  3. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 40
  4. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  5. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  6. 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
  7. 2024On the Crucial Role of Initialization for Matrix Factorizationcited by 15
  8. 2025Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Pointscited by 15
  9. 2023Convergence of Alternating Gradient Descent for Matrix Factorizationcited by 12
  10. 2022Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensingcited by 11
  11. 2023Active Self-Supervised Learning: A Few Low-Cost Relationships Are All You Needcited by 9
  12. 2022A Validation Approach to Over-parameterized Matrix and Image Recoverycited by 8
22 more
  1. 2024Guaranteed Nonconvex Factorization Approach for Tensor Train Recoverycited by 8
  2. 2024Federated Representation Learning in the Under-Parameterized Regimecited by 7
  3. 2025Closed-Form Training Dynamics Reveal Learned Features and Linear Structure in Word2Vec-like Modelscited by 7
  4. 2023Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descentcited by 5
  5. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  6. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 3
  7. 2023Efficient Compression of Overparameterized Deep Models through Low-Dimensional Learning Dynamicscited by 3
  8. 2024Connectivity Shapes Implicit Regularization in Matrix Factorization Models for Matrix Completioncited by 3
  9. 2024Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networkscited by 3
  10. 2025Theoretical Guarantees for Low-Rank Compression of Deep Neural Networkscited by 3
  11. 2023Gradient descent in matrix factorization: Understanding large initializationcited by 2
  12. 2023Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbationscited by 2
  13. 2024In-depth Analysis of Low-rank Matrix Factorisation in a Federated Settingcited by 2
  14. 2024Robust Low-rank Tensor Train Recoverycited by 2
  15. 2025Neural Collapse under Gradient Flow on Shallow ReLU Networks for Orthogonally Separable Datacited by 2
  16. 2026Low-Rank Adaptation Redux for Large Modelscited by 2
  17. 2024The Implicit Bias of Heterogeneity towards Invariance: A Study of Multi-Environment Matrix Sensingcited by 1
  18. 2025Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descentcited by 1
  19. 2026Incremental Learning of Sparse Attention Patterns in Transformerscited by 1
  20. 2023Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensingcited by 0
  21. 2025k-SVD with Gradient Descentcited by 0
  22. 2026Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamicscited by 0