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

Pan Zhou; Jiashi Feng; Chao Ma; Caiming Xiong; Steven Hoi; Weinan E

Source-linked AI summary

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

Pan Zhou, Jiashi Feng, Chao Ma, Caiming Xiong, Steven Hoi, Weinan E

arXiv:2010.05627v2Oct 12, 2020cs.LGcs.AImath.OCstat.ML

TL;DR

Adaptive gradient methods can train faster yet generalize worse than SGD, and existing curvature-based explanations do not fully account for this gap. The paper models SGD and ADAM with Lévy-driven SDEs and analyzes their escape times from local basins. It finds that SGD escapes more quickly from sharp basins and more often reaches flatter or asymmetric minima, offering an explanation for its better generalization.

Problem
It remains unclear why ADAM-like adaptive methods often generalize worse than SGD despite faster training, especially because curvature-based sharpness does not explain all observed minima.
Method
The paper models SGD and ADAM as Lévy-driven SDEs motivated by empirically observed heavy-tailed gradient noise, then analyzes their escaping times from local basins.
Results
For the same basin, SGD has smaller escaping time than ADAM; the escaping time scales as O(ε^-α/m(W)), with SGD benefiting from heavier-tailed noise and preserved anisotropy.
Takeaways & Limitations
SGD is more locally unstable at sharp minima and tends to reach flatter or asymmetric basins with larger Radon measure, which often generalize better.
Takeaways & Limitations
The analysis applies to moderately ill-conditioned local basins and assumes trajectories follow the eigenvector direction associated with the smallest curvature for one theorem result.

Abstract

from arXiv · show

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.

1 Introduction

The paper argues that SGD generalizes better than ADAM because their local escaping behaviors differ under heavy-tailed gradient noise, with SGD more likely to leave sharp basins and reach flatter or asymmetric ones.

Motivation: Adaptive methods train faster but often generalize worse than SGD, and curvature-based sharpness does not fully explain this gap.Deep networks can generalize well from asymmetric basins containing both steep and flat directions.
Gradient noise: Figure 1 indicates that α-stable noise better characterizes real gradient noise and that SGD has heavier tails than ADAM.The comparison uses AlexNet trained on CIFAR10.
Approach: The paper models SGD and ADAM as Lévy-driven SDEs to analyze how their local escaping behaviors affect the basins they eventually reach.The approach is motivated by heavy-tailed gradient noise and the similar convergence behavior of an algorithm and its SDE.
Escaping analysis: The escaping time Γ is O(ε^-α/m(W)), so both algorithms escape sharp minima whose basins have small Radon measure.Here α is the SαS tail index, ε depends on learning rate, and m(W) is the Radon measure of the escaping set.
Comparison: For the same basin, ADAM has smaller escaping-set measure because coordinate-wise geometry adaptation diminishes anisotropic gradient-noise structure.SGD therefore has smaller escaping time and is more locally unstable, favoring flatter or asymmetric basins with larger measure.
Comparison: SGD also has a smaller gradient-noise tail index than ADAM at some iterations, further reducing its escaping-time factor ε^-α.Together, the measure and tail differences explain why SGD more often reaches minima associated with better generalization.

2 Related Work

Prior work largely explains optimization and generalization through SGD or special problem settings, while theoretical treatment of adaptive algorithms remains limited.

Adaptive optimization: Adaptive gradient methods are widely used for fast convergence but often generalize worse than SGD, motivating analyses based on flat and sharp minima.Earlier empirical studies observed that SGD often converges to flatter minima than adaptive methods.
SGD theory: Most theoretical generalization analyses focus on SGD and model its gradient noise with Brownian-motion SDEs under a Gaussian assumption.One example links a larger learning-rate-to-mini-batch-size ratio with flatter minima and better generalization.
Research gap: Theoretical work on adaptive-gradient generalization is limited because these algorithms are more complex, with existing analyses including special problems such as spurious-feature influence in ADAGRAD.The paper positions its analysis as broader than work restricted to SGD or specially constructed settings.

3 Lévy-driven SDEs of Algorithms in Deep Learning

This section formulates SGD and ADAM as discretizations of Lévy-driven SDEs, using heavy-tailed gradient noise to analyze their convergence behavior.

Algorithm formulation: The objective is expressed as an empirical average of n component losses, and SGD updates parameters using mini-batch gradients.The mini-batch gradient averages the gradients of sampled examples, with η controlling the learning rate.
Algorithm formulation: ADAM estimates gradients with an exponential moving average and adapts each coordinate’s learning rate using a diagonal Fisher-matrix preconditioner.Its second-moment estimate uses β2, while the first-moment estimate uses β1.
Noise modeling: Gradient noise is defined as the difference between the full gradient and the mini-batch gradient, denoted u_t.This noise term appears explicitly in the SGD update and motivates the stochastic-process formulation.
Noise modeling: Empirical observations indicate that gradient noise has heavy tails and is better characterized by an SαS distribution than by Gaussian noise.The SαS model has tail index α; α = 2 recovers the Gaussian case.
SDE formulation: The analysis therefore models SGD and ADAM with Lévy-driven SDEs, including time-dependent covariance structure and exponential averaging for ADAM’s noise.The resulting SDEs are then used to analyze the algorithms’ escaping behavior from local basins.

4 Analysis for Escaping Local Minima

The analysis models SGD and ADAM with Lévy-driven SDEs and studies their first escaping time from local basins. It shows how basin Radon measure, geometry adaptation, and gradient-noise tails shape local stability and the resulting preference for flatter minima.

The first escaping time Γ is defined as the least time for the SDE trajectory to leave the inner portion of a local basin.
For both SGD and ADAM, expected escaping time scales as O(ε^−α/m(W)), increasing with basin-related Radon measure and decreasing with heavier noise tails.Here α is the SαS tail index, ε depends on the learning rate, and m(W) is the Radon measure of the escaping set.
4.2 Analysis of Generalization Gap between ADAM and SGD: These mechanisms make SGD more locally unstable and more likely to move from small-measure sharp basins toward flat or asymmetric basins associated with better generalization.The comparison is framed as an explanation for SGD’s better test performance than ADAM’s.
4.1 Preference to Flat Minima: Because m(W) negatively depends on basin volume, both algorithms escape sharp minima more readily and are more stable in larger, flatter basins.The analysis links larger basin measure with longer escaping time.
4.2 Analysis of Generalization Gap between ADAM and SGD: SGD’s heavier gradient-noise tails further reduce escaping time, while ADAM’s exponential gradient averaging smooths noise and yields lighter tails.The paper also notes that ADAM typically uses a smaller learning rate, which contributes to its escaping-time factor.
4.2 Analysis of Generalization Gap between ADAM and SGD: The gradient-noise-free processes exponentially converge to the local minimizer, and the noisy trajectories remain near it between large Lévy jumps before escape.This behavior is established under the theorem’s assumptions.
4.2 Analysis of Generalization Gap between ADAM and SGD: Theorem 2 applies to moderately ill-conditioned local basins; its analysis does not hold for extremely ill-conditioned basins with µ approaching or equal to zero.The paper notes that such extreme basins are asymmetric and often generalize well, so they are not required to be escaped.
4.2 Analysis of Generalization Gap between ADAM and SGD: SGD has a smaller escaping time than ADAM in the same basin because its escaping set has larger volume and Radon measure without geometry adaptation.For SGD, anisotropic gradient noise increases m(W), whereas ADAM’s coordinate scaling diminishes this structure.

5 Experiments

Experiments support the paper’s heavy-tailed gradient-noise assumption and show convergence differences consistent with the theory: SGD generally generalizes better than ADAM and exhibits basin-transition behavior absent in ADAM.

Heavy Tails of Gradient Noise: SGD and ADAM gradient noise is heavy-tailed and is well characterized by an SαS distribution.This supports the heavy-tail assumption used in the theoretical analysis.
Escaping Behaviors: SGD usually achieves better generalization performance than ADAM-alike adaptive algorithms in the reported MNIST and CIFAR10 experiments.
Escaping Behaviors: SGD’s tail index α decreases rapidly during an initial phase before accuracy improves more quickly on MNIST and CIFAR10.The reported initial phase lasts 1000 iterations on MNIST and 150 iterations on CIFAR10.
Escaping Behaviors: SGD sometimes makes sudden basin transitions accompanied by accuracy drops and subsequent rapid improvement, whereas ADAM shows no similar phenomenon.The paper attributes this contrast to SGD’s greater local instability and ADAM’s geometry adaptation, exponential gradient averaging, and smaller learning rate.

6 Conclusion

The paper explains SGD’s better generalization by comparing the local escaping behavior of Lévy-driven SDEs for SGD and ADAM-alike algorithms. For the same basin, SGD escapes faster and tends toward flatter minima with larger Radon measure.

The analysis uses escaping times of Lévy-driven SDEs to study local convergence and generalization differences between SGD and ADAM-alike algorithms.
For the same basin, SGD has smaller escaping time than ADAM and tends to converge to flatter minima with larger Radon measure.
The experiments support the heavy-gradient-noise assumption and the implications of the escaping-time theory.

Broader Impacts

The supplementary and broader-impact discussion documents additional SDE construction details, numerical validation, and evidence that SαS distributions characterize gradient noise. It also notes that practical algorithm design remains open.

Further work is needed to translate the theoretical understanding into practical algorithms with both fast convergence and good generalization.
The supplementary material adds ADAM SDE construction details, convergence-behavior experiments, related-work comparisons, and numerical results.
The supplementary analysis examines ADAM gradient-noise moments, introduces two randomness sources, and tests the constructed SDEs for ADAM and SGD.
Both the gradient noise and its second-order moment exhibit heavy tails, with SαS distributions characterizing them better than Gaussian distributions.
The ADAM SDE approximates gradient noise through the full gradient and Lévy motion but does not approximate v_t, leaving randomness from Lévy motion and minibatch sampling.

B.3 Convergence Behavior Comparison between Algorithm and Its SDE

The experiments compare ADAM and SGD with their Lévy-driven SDEs, while the analysis decomposes Lévy noise into small and large jumps and establishes local convergence behavior.

Algorithm–SDE comparison: ADAM and SGD show convergence trajectories very similar to those of their respective SDEs.This supports the validity of constructing SDE counterparts for both algorithms.
Lévy-noise decomposition: The Lévy process is decomposed into bounded small jumps and larger jumps represented by a compound Poisson process.The small-jump component has infinitely many bounded jumps, whereas the large-jump component has finite intensity Θ(ε−δ).
Lévy-noise decomposition: Small jumps are unlikely to escape the current basin, so the main escape mechanism is attributed to large jumps.The analysis explicitly treats large jumps as the principal force for leaving a local basin.
Local convergence: The deterministic dynamics associated with SGD and ADAM exponentially converge to the minimum of the current local basin.The Lyapunov-function analysis is used to characterize these local convergence behaviors before studying escape.

E.1 Proof of Theorem 1

The proof bounds basin-escape times by separating small-jump and large-jump effects, using local neighborhoods, jump probabilities, and Laplace-transform estimates.

Escape-probability bounds: Upper and lower escape-time bounds are obtained from the probability that large jumps carry the process outside the local basin.The lower-bound argument ignores small jumps, whereas the upper-bound analysis also controls their contribution.
Proof strategy: The proof estimates escape times by first analyzing escape from an inner basin and then relating it to escape from the full basin.The inner region is defined by a distance margin from the basin boundary, with the margin later taken toward zero.
Assumptions: The analysis assumes initialization inside a sufficiently shrunken basin, such as θ0 ∈ Ω−2εγ for the upper-bound argument.A stronger interior initialization, θ0 ∈ Ω−εγ, is used in the lower-bound analysis.
Proof strategy: The deterministic trajectory reaches a small neighborhood of the local optimum before the first large jump with exponentially high probability.The required convergence time is vε = O(ln(1/ε)), while the first large-jump waiting time is much larger for sufficiently small ε.
Escape-probability bounds: The proof uses exponential waiting times for large jumps and Laplace transforms to control the accumulated escape probabilities.The first large-jump waiting time has intensity Θ(ε−δ), and its transform is used in the bounds.

E.2 Proof of Theorem 2

The proof of Theorem 2 uses local strong convexity and auxiliary lemmas to show exponential convergence of the deterministic dynamics within a local basin.

Convergence proof: Local strong convexity, together with the auxiliary lemmas, yields exponential convergence to the current basin minimum.The result applies to the sequences generated by the SGD and ADAM deterministic systems.
Algorithm-specific bounds: The convergence bounds distinguish algorithm-specific constants for ADAM and SGD.The proof identifies separate constants involving Δ and μ for the two algorithms.
Lyapunov analysis: The proof bounds the Lyapunov function L(t) = F(bθt) − F(θ∗) and then applies Grönwall’s lemma to obtain linear convergence.The initial Lyapunov gap is Δ = F(bθ0) − F(θ∗).
Lyapunov analysis: Strong convexity converts Lyapunov-function convergence into convergence of the distance between the iterate and the basin minimum.The final step directly controls ∥bθt − θ∗∥2.

F.2 Proof of Theorem 4 for the Linear Convergence of Lévy-driven ADAM SDE (12)

Theorem 4 is proved by bounding ADAM’s Lyapunov derivative under parameter assumptions, then applying local strong convexity and Grönwall’s lemma to establish linear convergence.

Lyapunov derivative: The proof defines ADAM’s Lyapunov function and bounds its derivative using the first- and second-moment variables.The variables c_mt,i, bvt,i, and bst,i denote coordinate-wise moment-related quantities.
Assumptions: The analysis assumes β1 ≤ β2 ≤ 2β1, consistent with the practical setting β1 = 0.9 and β2 = 0.999.This parameter relation is used when bounding the two derivative terms.
Lyapunov derivative: The ADAM derivative bound uses the condition ∥c mt∥2 ≥ τ∥∇F(bθt)∥2 and the upper bound bvt,i ≤ vmax.These assumptions connect the moment estimates to the gradient and control the adaptive denominator.
Convergence result: The resulting inequality contains the convergence factor 2μτβ1/(ε + vmax) multiplying the Lyapunov gap.This bound is then integrated to establish linear convergence of the Lyapunov function.
Convergence result: Local strong convexity converts Lyapunov convergence into convergence of ∥bθt − θ∗∥2.The proof concludes after applying the strong-convexity relation to the distance from the basin minimum.

F.4 Proof of Lemma 2

The proof establishes local control of the SGD- and ADAM-driven sequences by combining exponential convergence, martingale deviation bounds, and estimates that exclude large jumps over successive time intervals.

Deviation control: Martingale exponential inequalities bound deviations of the Lévy martingale, yielding probabilities of order exp(−ε^−p) for sufficiently small ε.The proof decomposes the driving process into a bounded-jump martingale and linear drift before applying the bounds.
Step 1: Under local strong convexity, the auxiliary sequence bθt converges exponentially to the basin minimum θ∗.The argument applies to the sequences generated by the SGD or ADAM dynamics.
Step 2: For times before vε, θt remains close to bθt when the driving process has no large jumps.This couples the original sequence to the exponentially convergent auxiliary sequence over the initial interval.
Algorithm-specific estimates: The SGD and ADAM estimates differ through their respective dynamic-system constants, including κ1=ℓ for SGD and an adaptive expression for ADAM.The ADAM bound additionally uses boundedness of its moment and variance-related quantities.
Step 3: The proof controls h(θ)=ln(1+F(θ)) using quadratic bounds near the local basin minimum and Itô estimates for the process h(θt).Smoothness and boundedness assumptions on F support the derivative and quadratic-variation estimates.
Steps 4–5: The argument extends the local control from [0,Tε∧σ1) to [0,σ1) and then to all initializations θ0∈Ω by combining the preceding estimates.The extension relies on the absence of large jumps before σ1 and the earlier convergence and deviation bounds.