Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity
arXiv:2106.09524
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.
References in corpus (13)
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- On Lazy Training in Differentiable Programming
- Three Factors Influencing Minima in SGD
- Characterizing Implicit Bias in Terms of Optimization Geometry
- Bounds on the Lambert function and their application to the outage analysis of user cooperation
- Gradient descent aligns the layers of deep linear networks
- Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
- Time-uniform Chernoff bounds via nonnegative supermartingales
- The Implicit Regularization of Stochastic Gradient Flow for Least Squares
- Implicit Regularization for Optimal Sparse Recovery
- Shape Matters: Understanding the Implicit Bias of the Noise Covariance
- Stochastic Gradient and Langevin Processes
- The Statistical Complexity of Early-Stopped Mirror Descent