A Diffusion Theory For Deep Learning Dynamics: Stochastic Gradient Descent Exponentially Favors Flat Minima

Abstract

Stochastic Gradient Descent (SGD) and its variants are mainstream methods for training deep networks in practice. SGD is known to find a flat minimum that often generalizes well. However, it is mathematically unclear how deep learning can select a flat minimum among so many minima. To answer the question quantitatively, we develop a density diffusion theory (DDT) to reveal how minima selection quantitatively depends on the minima sharpness and the hyperparameters. To the best of our knowledge, we are the first to theoretically and empirically prove that, benefited from the Hessian-dependent covariance of stochastic gradient noise, SGD favors flat minima exponentially more than sharp minima, while Gradient Descent (GD) with injected white noise favors flat minima only polynomially more than sharp minima. We also reveal that either a small learning rate or large-batch training requires exponentially many iterations to escape from minima in terms of the ratio of the batch size and learning rate. Thus, large-batch training cannot search flat minima efficiently in a realistic computational time.

arXiv commentICLR 2021; 28 pages; 19 figures

References in corpus (19)

• One weird trick for parallelizing convolutional neural networks
• Don't Decay the Learning Rate, Increase the Batch Size
• A Closer Look at Memorization in Deep Networks
• Three Factors Influencing Minima in SGD
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Essentially No Barriers in Neural Network Energy Landscape
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• Sharp Minima Can Generalize For Deep Nets
• Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes
• Gradient Descent Happens in a Tiny Subspace
• Kramers' law: Validity, derivations and generalisations
• Hessian-based Analysis of Large Batch Training and Robustness to Adversaries
• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
• Where is the Information in a Deep Neural Network?
• Asymmetric Valleys: Beyond Sharp and Flat Local Minima
• A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
• Normalized Flat Minima: Exploring Scale Invariant Definition of Flat Minima for Neural Networks using PAC-Bayesian Analysis
• First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise
• Artificial Neural Variability for Deep Learning: On Overfitting, Noise Memorization, and Catastrophic Forgetting

Cited by in corpus (9)

• Understanding the Role of Training Regimes in Continual Learning
• The large learning rate phase of deep learning: the catapult mechanism
• On the different regimes of Stochastic Gradient Descent
• Wide-minima Density Hypothesis and the Explore-Exploit Learning Rate Schedule
• Dynamic of Stochastic Gradient Descent with State-Dependent Noise
• On generalization bounds for deep networks based on loss surface implicit regularization
• Optimal Potential Shaping on SE(3) via Neural ODEs on Lie Groups
• Generalization by design: Shortcuts to Generalization in Deep Learning
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD