Shape Matters: Understanding the Implicit Bias of the Noise Covariance

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 (42)

• Adam: A Method for Stochastic Optimization
• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding deep learning requires rethinking generalization
• Don't Decay the Learning Rate, Increase the Batch Size
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Train faster, generalize better: Stability of stochastic gradient descent
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Adding Gradient Noise Improves Learning for Very Deep Networks
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Path-SGD: Path-Normalized Optimization in Deep Neural Networks
• Measuring the Effects of Data Parallelism on Neural Network Training
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Gradient descent aligns the layers of deep linear networks
• Norm matters: efficient and accurate normalization schemes in deep networks
• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
• Theoretical Analysis of Auto Rate-Tuning by Batch Normalization
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Risk and parameter convergence of logistic regression
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
• Kernel and Rich Regimes in Overparametrized Models
• Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Theory of Deep Learning III: explaining the non-overfitting puzzle
• Optimal Regularization Can Mitigate Double Descent
• Fluctuation-dissipation relations for stochastic gradient descent
• Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates
• Implicit Regularization for Optimal Sparse Recovery
• On the Implicit Bias of Dropout
• The Implicit and Explicit Regularization Effects of Dropout
• Convergence of Gradient Descent on Separable Data
• Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models
• Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
• The Implicit Bias of Depth: How Incremental Learning Drives Generalization
• Dropout: Explicit Forms and Capacity Control
• An Empirical Study of Large-Batch Stochastic Gradient Descent with Structured Covariance Noise
• How noise affects the Hessian spectrum in overparameterized neural networks
• On Dropout and Nuclear Norm Regularization
• Disentangling Adaptive Gradient Methods from Learning Rates

Cited by in corpus (14)

• On the Opportunities and Risks of Foundation Models
• Self-supervised Learning is More Robust to Dataset Imbalance
• Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem
• Strength of Minibatch Noise in SGD
• Dynamic of Stochastic Gradient Descent with State-Dependent Noise
• Label Noise SGD Provably Prefers Flat Global Minimizers
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• Stochastic Training is Not Necessary for Generalization
• Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation