# Noise Regularizes Over-parameterized Rank One Matrix Recovery, Provably

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 33 references that are in the map.
- First posted on arXiv 7 Feb 2022.

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

- [Fully Convolutional Networks for Semantic Segmentation](https://mlsanity.com/paper/1411.4038/) (2014)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Speech Recognition with Deep Recurrent Neural Networks](https://mlsanity.com/paper/1303.5778/) (2013)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Recent Trends in Deep Learning Based Natural Language Processing](https://mlsanity.com/paper/1708.02709/) (2017)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process](https://mlsanity.com/paper/1904.09080/) (2019)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [Shape Matters: Understanding the Implicit Bias of the Noise Covariance](https://mlsanity.com/paper/2006.08680/) (2020)
- [Towards Understanding Regularization in Batch Normalization](https://mlsanity.com/paper/1809.00846/) (2018)
- [A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics](https://mlsanity.com/paper/1904.04326/) (2019)
- [On the Implicit Bias of Dropout](https://mlsanity.com/paper/1806.09777/) (2018)
- [Adding One Neuron Can Eliminate All Bad Local Minima](https://mlsanity.com/paper/1805.08671/) (2018)
- [On the Inductive Bias of Dropout](https://mlsanity.com/paper/1412.4736/) (2014)
- [Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squareroot](https://mlsanity.com/paper/1507.05854/) (2015)
- [Towards Understanding the Importance of Noise in Training Neural Networks](https://mlsanity.com/paper/1909.03172/) (2019)
- [Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity](https://mlsanity.com/paper/1912.13472/) (2019)

## Abstract (arXiv)

We investigate the role of noise in optimization algorithms for learning over-parameterized models. Specifically, we consider the recovery of a rank one matrix Y^*∈ Rd× d from a noisy observation Y using an over-parameterization model. We parameterize the rank one matrix Y^* by XX^top, where X∈ Rd× d. We then show that under mild conditions, the estimator, obtained by the randomly perturbed gradient descent algorithm using the square loss function, attains a mean square error of O(σ2/d), where σ2 is the variance of the observational noise. In contrast, the estimator obtained by gradient descent without random perturbation only attains a mean square error of O(σ2). Our result partially justifies the implicit regularization effect of noise when learning over-parameterized models, and provides new understanding of training over-parameterized neural networks.