# Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Dec 2017.

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

- [Understanding Gradient Descent on Edge of Stability in Deep Learning](https://mlsanity.com/paper/2205.09745/) (2022)
- [How Does Adaptive Optimization Impact Local Neural Network Geometry?](https://mlsanity.com/paper/2211.02254/) (2022)
- [Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization](https://mlsanity.com/paper/2202.08788/) (2022)
- [Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion](https://mlsanity.com/paper/2402.06756/) (2024)
- [Achieving Small Test Error in Mildly Overparameterized Neural Networks](https://mlsanity.com/paper/2104.11895/) (2021)
- [Hallmarks of Optimization Trajectories in Neural Networks: Directional Exploration and Redundancy](https://mlsanity.com/paper/2403.07379/) (2024)
- [AILS-NTUA at SemEval-2024 Task 9: Cracking Brain Teasers: Transformer Models for Lateral Thinking Puzzles](https://mlsanity.com/paper/2404.01084/) (2024)
- [Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing](https://mlsanity.com/paper/2303.14244/) (2023)

## Abstract (arXiv)

We show that the gradient descent algorithm provides an implicit regularization effect in the learning of over-parameterized matrix factorization models and one-hidden-layer neural networks with quadratic activations. Concretely, we show that given tildeO(dr2) random linear measurements of a rank r positive semidefinite matrix Xstar, we can recover Xstar by parameterizing it by UU^top with U∈ mathbb Rd× d and minimizing the squared loss, even if r ll d. We prove that starting from a small initialization, gradient descent recovers Xstar in tildeO(√r) iterations approximately. The results solve the conjecture of Gunasekar et al.'17 under the restricted isometry property. The technique can be applied to analyzing neural networks with one-hidden-layer quadratic activations with some technical modifications.