# Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization

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

## Key facts

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

## Builds on (most cited first, 16 of 16)

- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [Big Transfer (BiT): General Visual Representation Learning](https://mlsanity.com/paper/1912.11370/) (2019)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [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)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [Early Stopping for Deep Image Prior](https://mlsanity.com/paper/2112.06074/) (2021)
- [Gradient Descent for Deep Matrix Factorization: Dynamics and Implicit Bias towards Low Rank](https://mlsanity.com/paper/2011.13772/) (2020)
- [Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent](https://mlsanity.com/paper/1605.07051/) (2016)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation](https://mlsanity.com/paper/1802.08397/) (2018)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery](https://mlsanity.com/paper/2102.02969/) (2021)

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

- [SD-LoRA: Scalable Decoupled Low-Rank Adaptation for Class Incremental Learning](https://mlsanity.com/paper/2501.13198/) (2025)
- [Saddle-to-Saddle Dynamics in Diagonal Linear Networks](https://mlsanity.com/paper/2304.00488/) (2023)
- [Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing](https://mlsanity.com/paper/2301.11500/) (2023)
- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization](https://mlsanity.com/paper/2310.01769/) (2023)
- [Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Points](https://mlsanity.com/paper/2508.12837/) (2025)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [On the Crucial Role of Initialization for Matrix Factorization](https://mlsanity.com/paper/2410.18965/) (2024)
- [Convergence of Alternating Gradient Descent for Matrix Factorization](https://mlsanity.com/paper/2305.06927/) (2023)
- [Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing](https://mlsanity.com/paper/2204.11516/) (2022)
- [Active Self-Supervised Learning: A Few Low-Cost Relationships Are All You Need](https://mlsanity.com/paper/2303.15256/) (2023)
- [A Validation Approach to Over-parameterized Matrix and Image Recovery](https://mlsanity.com/paper/2209.10675/) (2022)
- [Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery](https://mlsanity.com/paper/2401.02592/) (2024)
- [Closed-Form Training Dynamics Reveal Learned Features and Linear Structure in Word2Vec-like Models](https://mlsanity.com/paper/2502.09863/) (2025)
- [Federated Representation Learning in the Under-Parameterized Regime](https://mlsanity.com/paper/2406.04596/) (2024)
- [Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent](https://mlsanity.com/paper/2305.17224/) (2023)
- [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022)
- [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)
- [Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks](https://mlsanity.com/paper/2410.09640/) (2024)
- [Theoretical Guarantees for Low-Rank Compression of Deep Neural Networks](https://mlsanity.com/paper/2502.02766/) (2025)
- [Low-Rank Adaptation Redux for Large Models](https://mlsanity.com/paper/2604.21905/) (2026)
- [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)
- [In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting](https://mlsanity.com/paper/2409.08771/) (2024)
- [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024)
- [Neural Collapse under Gradient Flow on Shallow ReLU Networks for Orthogonally Separable Data](https://mlsanity.com/paper/2510.21078/) (2025)
- [Incremental Learning of Sparse Attention Patterns in Transformers](https://mlsanity.com/paper/2602.19143/) (2026)

## 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.