Dynamic of Stochastic Gradient Descent with State-Dependent Noise
arXiv:2006.13719
Abstract
Stochastic gradient descent (SGD) and its variants are mainstream methods to train deep neural networks. Since neural networks are non-convex, more and more works study the dynamic behavior of SGD and the impact to its generalization, especially the escaping efficiency from local minima. However, these works take the over-simplified assumption that the covariance of the noise in SGD is (or can be upper bounded by) constant, although it is actually state-dependent. In this work, we conduct a formal study on the dynamic behavior of SGD with state-dependent noise. Specifically, we show that the covariance of the noise of SGD in the local region of the local minima is a quadratic function of the state. Thus, we propose a novel power-law dynamic with state-dependent diffusion to approximate the dynamic of SGD. We prove that, power-law dynamic can escape from sharp minima exponentially faster than flat minima, while the previous dynamics can only escape sharp minima polynomially faster than flat minima. Our experiments well verified our theoretical results. Inspired by our theory, we propose to add additional state-dependent noise into (large-batch) SGD to further improve its generalization ability. Experiments verify that our method is effective.
References in corpus (26)
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- The Loss Surfaces of Multilayer Networks
- Anomalous diffusion in the presence of external forces: exact time-dependent solutions and entropy
- Dual Learning for Machine Translation
- On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- No More Pesky Learning Rates
- Essentially No Barriers in Neural Network Energy Landscape
- The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
- Energy-entropy competition and the effectiveness of stochastic gradient descent in machine learning
- Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
- Understanding Short-Horizon Bias in Stochastic Meta-Optimization
- The Heavy-Tail Phenomenon in SGD
- Asymmetric Valleys: Beyond Sharp and Flat Local Minima
- Multiplicative noise and heavy tails in stochastic optimization
- On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
- A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
- A Diffusion Theory For Deep Learning Dynamics: Stochastic Gradient Descent Exponentially Favors Flat Minima
- Power-law distributions and fluctuation-dissipation relation in the stochastic dynamics of two-variable Langevin equations
- On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks
- Kramers escape rate in overdamped systems with the power-law distribution
- Shape Matters: Understanding the Implicit Bias of the Noise Covariance
- Towards Understanding the Importance of Noise in Training Neural Networks
- Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model
- Are power-law distributions an equilibrium distribution or a stationary nonequilibrium distribution?
- A Diffusion Approximation Theory of Momentum SGD in Nonconvex Optimization