Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learning

Abstract

It is not clear yet why ADAM-alike adaptive gradient algorithms suffer from worse generalization performance than SGD despite their faster training speed. This work aims to provide understandings on this generalization gap by analyzing their local convergence behaviors. Specifically, we observe the heavy tails of gradient noise in these algorithms. This motivates us to analyze these algorithms through their Levy-driven stochastic differential equations (SDEs) because of the similar convergence behaviors of an algorithm and its SDE. Then we establish the escaping time of these SDEs from a local basin. The result shows that (1) the escaping time of both SGD and ADAM~depends on the Radon measure of the basin positively and the heaviness of gradient noise negatively; (2) for the same basin, SGD enjoys smaller escaping time than ADAM, mainly because (a) the geometry adaptation in ADAM~via adaptively scaling each gradient coordinate well diminishes the anisotropic structure in gradient noise and results in larger Radon measure of a basin; (b) the exponential gradient average in ADAM~smooths its gradient and leads to lighter gradient noise tails than SGD. So SGD is more locally unstable than ADAM~at sharp minima defined as the minima whose local basins have small Radon measure, and can better escape from them to flatter ones with larger Radon measure. As flat minima here which often refer to the minima at flat or asymmetric basins/valleys often generalize better than sharp ones , our result explains the better generalization performance of SGD over ADAM. Finally, experimental results confirm our heavy-tailed gradient noise assumption and theoretical affirmation.

arXiv commentNeurIPS 2020

References in corpus (16)

• Adam: A Method for Stochastic Optimization
• SGDR: Stochastic Gradient Descent with Warm Restarts
• The Marginal Value of Adaptive Gradient Methods in Machine Learning
• Regularizing and Optimizing LSTM Language Models
• Improving Generalization Performance by Switching from Adam to SGD
• Averaging Weights Leads to Wider Optima and Better Generalization
• Three Factors Influencing Minima in SGD
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• Efficient approaches for escaping higher order saddle points in non-convex optimization
• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• A Variational Analysis of Stochastic Gradient Algorithms
• An introduction to Lévy processes with applications in finance
• A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
• First exit times of solutions of stochastic differential equations driven by multiplicative Levy noise with heavy tails
• Theory-Inspired Path-Regularized Differential Network Architecture Search

Cited by in corpus (8)

• Theory-Inspired Path-Regularized Differential Network Architecture Search
• On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)
• SALR: Sharpness-aware Learning Rate Scheduler for Improved Generalization
• New Insights into Metric Optimization for Ranking-based Recommendation
• Exploiting Adam-like Optimization Algorithms to Improve the Performance of Convolutional Neural Networks
• Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect
• NucMM Dataset: 3D Neuronal Nuclei Instance Segmentation at Sub-Cubic Millimeter Scale
• GABO: Graph Augmentations with Bi-level Optimization