Shape Matters: Understanding the Implicit Bias of the Noise Covariance
arXiv:2006.08680
Abstract
The noise in stochastic gradient descent (SGD) provides a crucial implicit regularization effect for training overparameterized models. Prior theoretical work largely focuses on spherical Gaussian noise, whereas empirical studies demonstrate the phenomenon that parameter-dependent noise -- induced by mini-batches or label perturbation -- is far more effective than Gaussian noise. This paper theoretically characterizes this phenomenon on a quadratically-parameterized model introduced by Vaskevicius et el. and Woodworth et el. We show that in an over-parameterized setting, SGD with label noise recovers the sparse ground-truth with an arbitrary initialization, whereas SGD with Gaussian noise or gradient descent overfits to dense solutions with large norms. Our analysis reveals that parameter-dependent noise introduces a bias towards local minima with smaller noise variance, whereas spherical Gaussian noise does not. Code for our project is publicly available.
References in corpus (12)
- Very Deep Convolutional Networks for Large-Scale Image Recognition
- Understanding deep learning requires rethinking generalization
- On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
- Path-SGD: Path-Normalized Optimization in Deep Neural Networks
- Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
- Theory of Deep Learning III: explaining the non-overfitting puzzle
- Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates
- Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models
- How noise affects the Hessian spectrum in overparameterized neural networks
- On Dropout and Nuclear Norm Regularization
- Disentangling Adaptive Gradient Methods from Learning Rates