# The Implicit Regularization of Stochastic Gradient Flow for Least Squares

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

## Key facts

- Cited by 59 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2020.

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

- [Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity](https://mlsanity.com/paper/2106.09524/) (2021)
- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [Noisy Recurrent Neural Networks](https://mlsanity.com/paper/2102.04877/) (2021)
- [Stochastic Collapse: How Gradient Noise Attracts SGD Dynamics Towards Simpler Subnetworks](https://mlsanity.com/paper/2306.04251/) (2023)
- [The Implicit Bias of Adam on Separable Data](https://mlsanity.com/paper/2406.10650/) (2024)
- [The Benefits of Implicit Regularization from SGD in Least Squares Problems](https://mlsanity.com/paper/2108.04552/) (2021)
- [On Implicit Bias in Overparameterized Bilevel Optimization](https://mlsanity.com/paper/2212.14032/) (2022)
- [Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrisation](https://mlsanity.com/paper/2206.09841/) (2022)
- [Multi-scale Feature Learning Dynamics: Insights for Double Descent](https://mlsanity.com/paper/2112.03215/) (2021)
- [Does Momentum Change the Implicit Regularization on Separable Data?](https://mlsanity.com/paper/2110.03891/) (2021)
- [RATT: Leveraging Unlabeled Data to Guarantee Generalization](https://mlsanity.com/paper/2105.00303/) (2021)
- [The Limiting Dynamics of SGD: Modified Loss, Phase Space Oscillations, and Anomalous Diffusion](https://mlsanity.com/paper/2107.09133/) (2021)
- [NoisyMix: Boosting Model Robustness to Common Corruptions](https://mlsanity.com/paper/2202.01263/) (2022)
- [Interpolation can hurt robust generalization even when there is no noise](https://mlsanity.com/paper/2108.02883/) (2021)
- [Toward Equation of Motion for Deep Neural Networks: Continuous-time Gradient Descent and Discretization Error Analysis](https://mlsanity.com/paper/2210.15898/) (2022)
- [Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squares](https://mlsanity.com/paper/2206.01274/) (2022)
- [Neuro-symbolic Learning Yielding Logical Constraints](https://mlsanity.com/paper/2410.20957/) (2024)
- [On the (Non-)Robustness of Two-Layer Neural Networks in Different Learning Regimes](https://mlsanity.com/paper/2203.11864/) (2022)
- [Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent](https://mlsanity.com/paper/2205.07331/) (2022)
- [On Regularization via Early Stopping for Least Squares Regression](https://mlsanity.com/paper/2406.04425/) (2024)
- [Generalized equivalences between subsampling and ridge regularization](https://mlsanity.com/paper/2305.18496/) (2023)
- [Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning](https://mlsanity.com/paper/2306.08590/) (2023)
- [A Continuous-time Stochastic Gradient Descent Method for Continuous Data](https://mlsanity.com/paper/2112.03754/) (2021)
- [Group-Sparse Matrix Factorization for Transfer Learning of Word Embeddings](https://mlsanity.com/paper/2104.08928/) (2021)
- [Comparing Classes of Estimators: When does Gradient Descent Beat Ridge Regression in Linear Models?](https://mlsanity.com/paper/2108.11872/) (2021)
- [Robust Generalization of Quadratic Neural Networks via Function Identification](https://mlsanity.com/paper/2109.10935/) (2021)
- [How You Start Matters for Generalization](https://mlsanity.com/paper/2206.08558/) (2022)
- [On Optimal Early Stopping: Over-informative versus Under-informative Parametrization](https://mlsanity.com/paper/2202.09885/) (2022)
- [Robust Linear Regression: Gradient-descent, Early-stopping, and Beyond](https://mlsanity.com/paper/2301.13486/) (2023)
- [Failures and Successes of Cross-Validation for Early-Stopped Gradient Descent](https://mlsanity.com/paper/2402.16793/) (2024)

## Abstract (arXiv)

We study the implicit regularization of mini-batch stochastic gradient descent, when applied to the fundamental problem of least squares regression. We leverage a continuous-time stochastic differential equation having the same moments as stochastic gradient descent, which we call stochastic gradient flow. We give a bound on the excess risk of stochastic gradient flow at time t, over ridge regression with tuning parameter λ = 1/t. The bound may be computed from explicit constants (e.g., the mini-batch size, step size, number of iterations), revealing precisely how these quantities drive the excess risk. Numerical examples show the bound can be small, indicating a tight relationship between the two estimators. We give a similar result relating the coefficients of stochastic gradient flow and ridge. These results hold under no conditions on the data matrix X, and across the entire optimization path (not just at convergence).