# Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 44 references that are in the map.
- First posted on arXiv 4 Sep 2023.

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [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)
- [Implicit Gradient Regularization](https://mlsanity.com/paper/2009.11162/) (2020)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [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)
- [Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problem](https://mlsanity.com/paper/2101.08286/) (2021)
- [Transformers learn through gradual rank increase](https://mlsanity.com/paper/2306.07042/) (2023)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks](https://mlsanity.com/paper/1802.06093/) (2018)
- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [Gradient Descent for Deep Matrix Factorization: Dynamics and Implicit Bias towards Low Rank](https://mlsanity.com/paper/2011.13772/) (2020)
- [Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing](https://mlsanity.com/paper/2301.11500/) (2023)
- [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022)
- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [The Global Optimization Geometry of Low-Rank Matrix Optimization](https://mlsanity.com/paper/1703.01256/) (2017)
- [Convergence of gradient descent for learning linear neural networks](https://mlsanity.com/paper/2108.02040/) (2021)
- [Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squareroot](https://mlsanity.com/paper/1507.05854/) (2015)
- [Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent](https://mlsanity.com/paper/1605.08370/) (2016)
- [The extended Smale's 9th problem -- On computational barriers and paradoxes in estimation, regularisation, computer-assisted proofs and learning](https://mlsanity.com/paper/2110.15734/) (2021)
- [A Validation Approach to Over-parameterized Matrix and Image Recovery](https://mlsanity.com/paper/2209.10675/) (2022)
- [Implicit regularization in AI meets generalized hardness of approximation in optimization -- Sharp results for diagonal linear networks](https://mlsanity.com/paper/2307.07410/) (2023)
- [Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing](https://mlsanity.com/paper/2101.05113/) (2021)

## Built on by (most cited first, 2 of 2)

- [Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity](https://mlsanity.com/paper/2408.13276/) (2024)
- [HRP: High-Rank Preheating for Superior LoRA Initialization](https://mlsanity.com/paper/2502.07739/) (2025)

## Abstract (arXiv)

Several key questions remain unanswered regarding overparameterized learning models. It is unclear how (stochastic) gradient descent finds solutions that generalize well, and in particular the role of small random initializations. Matrix sensing, which is the problem of reconstructing a low-rank matrix from a few linear measurements, has become a standard prototypical setting to study these phenomena. Previous works have shown that matrix sensing can be solved by factorized gradient descent, provided the random initialization is extremely small. In this paper, we find that factorized gradient descent is highly robust to certain perturbations. This lets us use a perturbation term to capture both the effects of imperfect measurements, discretization by gradient descent, and other noise, resulting in a general formulation which we call textitperturbed gradient flow. We find that not only is this equivalent formulation easier to work with, but it leads to sharper sample and time complexities than previous work, handles moderately small initializations, and the results are naturally robust to perturbations such as noisy measurements or changing measurement matrices. Finally, we also analyze mini-batch stochastic gradient descent using the formulation, where we find improved sample complexity.