Authors: Tianyi Liu (ByteDance), Yan Li, Enlu Zhou, Tuo Zhao (Georgia Tech)
Abstract
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^* \in \mathbb{R}^{d \times d}$ from a noisy observation $Y$ using an over-parameterization model. We parameterize the rank one matrix $Y^*$ by $XX^\top$, where $X \in \mathbb{R}^{d \times d}$. We show that under mild conditions, the estimator obtained by the randomly perturbed gradient descent (P-GD) algorithm using the square loss function attains a mean square error of $O(\sigma^2/d)$, where $\sigma^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(\sigma^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.
Introduction
In modern deep learning, models are typically over-parameterized, meaning they possess far more parameters than training data points. While classical statistics suggests such models should overfit observational noise, they often generalize remarkably well. This phenomenon has led researchers to investigate "implicit regularization"—the idea that the optimization algorithm itself biases the model toward simpler solutions.
This paper explores the role of noise in this process. While noise is often viewed as a nuisance, the authors prove that injecting random noise into the optimization process—specifically in Perturbed Gradient Descent (P-GD)—acts as a powerful regularizer that significantly improves recovery accuracy in over-parameterized settings.
The Rank-One Recovery Problem
The authors study a fundamental over-parameterized model: Rank One Matrix Recovery. The goal is to recover a simple rank-1 matrix $Y^*$ from a noisy observation $Y$. Instead of using a constrained model, they use an over-parameterized representation $XX^\top$, where $X$ is a full $d \times d$ matrix. This model has $d^2$ parameters to learn a structure that fundamentally only requires $d$ parameters. The challenge is ensuring the algorithm converges to the "simple" rank-1 solution rather than a complex one that fits the noise.
Methodology: Perturbed Gradient Descent
The primary algorithm analyzed is Perturbed Gradient Descent (P-GD). Unlike standard Gradient Descent (GD), P-GD injects independent random noise into the model parameters at every iteration before calculating the gradient.
To analyze its performance, the authors introduce a technical framework called Subspace Dissipativity. This condition demonstrates that injected noise helps the algorithm's trajectory point toward the true signal while suppressing components that would otherwise overfit the noise. Using a Super-martingale Theorem, they track the algorithm's convergence, showing it enters and remains within a region of minimal recovery error.
Key Theoretical Insights
- The $1/d$ Advantage: The most significant finding is the error bound. While standard GD attains a mean square error of $O(\sigma^2)$, P-GD achieves $O(\sigma^2/d)$. In high-dimensional spaces (large $d$), the noise effectively "dilutes" the error, leading to much higher precision.
- Noise as a Simplicity Bias: The injected noise creates an implicit bias, making the optimization landscape "dissipative" in the directions of over-parameterized components. This forces the model to prefer low-rank (simpler) solutions.
- Continuous Regularization: Unlike previous theories suggesting noise only helps escape saddle points, this work shows noise provides continuous benefits even after the algorithm reaches the correct neighborhood.
Experimental Validation
The authors verified their theoretical findings using synthetic datasets involving Rank-1 PSD, Rank-3 PSD, and Rank-3 Rectangular matrices subject to Gaussian noise.
As shown in the figure above, standard GD (even with small initialization or early stopping) eventually overfits the observational noise. In contrast, P-GD consistently converges to a solution with significantly lower error. Furthermore, P-GD demonstrates high robustness to initialization, reaching low-error solutions even when starting from "large" initial parameters where standard GD fails.
Conclusion
This work provides a rigorous mathematical justification for the beneficial role of noise in training over-parameterized models. By proving the $O(\sigma^2/d)$ error rate for P-GD, the authors offer a new perspective on why stochasticity in algorithms like SGD contributes to the success of deep learning. Future work aims to extend these proofs to multi-layer neural network architectures and more complex, data-dependent noise structures.
Summary updated