Abstract
Understanding the implicit bias of training algorithms is of crucial importance in order to explain the success of overparametrised neural networks. In this paper, we study the dynamics of stochastic gradient descent over diagonal linear networks through its continuous time version, namely stochastic gradient flow. We explicitly characterise the solution chosen by the stochastic flow and prove that it always enjoys better generalisation properties than that of gradient flow. Quite surprisingly, we show that the convergence speed of the training loss controls the magnitude of the biasing effect: the slower the convergence, the better the bias. To fully complete our analysis, we provide convergence guarantees for the dynamics. We also give experimental results which support our theoretical claims. Our findings highlight the fact that structured noise can induce better generalisation and they help explain the greater performances observed in practice of stochastic gradient descent over gradient descent.
Introduction
In the world of deep learning, a persistent mystery remains: why does Stochastic Gradient Descent (SGD) consistently outperform full-batch Gradient Descent (GD) in generalization? Overparameterized models can fit training data in infinitely many ways, yet SGD reliably selects solutions that perform well on unseen data without explicit regularization.
A recent study by Pesme et al. (2021) provides a rigorous mathematical framework to explain this phenomenon in diagonal linear networks. These models, which parametrize a vector $\beta$ as the difference of two squared weight vectors ($w_+^2 - w_-^2$), serve as a proxy for the "rich regime" of deep learning where models learn sparse features rather than simple kernel solutions.
Methodology: Stochastic Gradient Flow
To analyze the discrete steps of SGD, the authors utilized Stochastic Gradient Flow (SGF), a continuous-time Stochastic Differential Equation (SDE). Crucially, they modeled the noise as state-dependent, meaning it vanishes as the model approaches a global optimum. This accurately mirrors the behavior of SGD in practice. By applying Itô calculus and viewing the trajectory through the lens of mirror descent, the researchers derived an exact characterization of the implicit bias inherent in the final solution.
The "Slow Training" Bonus
The most significant theoretical finding is the "Effective Initialization" effect. The study proves that SGD behaves like GD, but as if it had started with a much smaller initialization scale. In diagonal networks, smaller initializations are mathematically linked to sparser, better-generalizing solutions.
The magnitude of this "cooling" effect is determined by the cumulative training loss: $\int_0^\infty L(\beta_s) ds$. This leads to a counter-intuitive conclusion: the slower the training loss converges to zero, the more noise the algorithm accumulates, and the stronger the resulting bias toward sparsity.
Empirical Results and Generalization
The authors validated their theory using synthetic sparse regression datasets ($n=40, d=100$). As predicted, SGD achieved test losses orders of magnitude lower than GD for identical starting initializations.
Furthermore, the researchers experimented with "doping" the training process with label noise. While this slowed down convergence, it actually improved the final test performance by increasing the "slowness bonus" (the integral of the loss), confirming that structured stochasticity is a feature, not a bug.
Conclusion
This research demonstrates that the structured noise in SGD isn't just random interference; it is a mechanism that biases models toward simpler, sparser solutions. While the current proof is specific to diagonal linear networks and quadratic loss, it provides a foundational explanation for the superior performance of SGD. Future research will aim to extend these insights to more complex architectures like ReLU networks and Transformers.
Full Paper: Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity (Pesme et al., 2021)
Summary updated