Why gradient clipping accelerates training: A theoretical justification for adaptivity

Jingzhao Zhang; Tianxing He; Suvrit Sra; Ali Jadbabaie

Source-linked AI summary

Why gradient clipping accelerates training: A theoretical justification for adaptivity

Jingzhao Zhang, Tianxing He, Suvrit Sra, Ali Jadbabaie

arXiv:1905.11881v2May 28, 2019math.OCcs.LG

TL;DR

The paper asks why adaptive methods can converge faster than fixed-step gradient descent despite limited theoretical understanding and restrictive smoothness assumptions. It derives a relaxed, empirically supported smoothness condition and analyzes clipped and normalized gradient methods under it. The resulting theory establishes arbitrarily faster convergence than fixed-step methods in the stated deterministic and stochastic comparisons, alongside neural-network experiments supporting the mechanism.

Problem
Adaptive methods often outperform SGD in tasks such as reinforcement learning and NLP, but the fast convergence of adaptivity remains poorly understood, while fixed global smoothness assumptions may not match neural-network training.
Method
The paper derives a relaxed smoothness condition from neural-network experiments and analyzes clipped gradient descent and normalized gradient descent under that condition.
Results
The theory shows that clipped GD can be arbitrarily faster than fixed-step GD and stochastic clipped GD can be arbitrarily faster than fixed-step SGD; experiments support the proposed explanation and report comparable test performance with large-step GD variants and momentum-SGD.
Takeaways & Limitations
Gradient clipping and normalized gradient methods receive theoretical acceleration guarantees under a smoothness condition aligned with observed neural-network training behavior.
Takeaways & Limitations
The paper studies clipped gradient descent but leaves the convergence of momentum, preconditioning, and variance reduction, as well as faster algorithms for neural-network training, open.

Abstract

from arXiv · show

We provide a theoretical explanation for the effectiveness of gradient clipping in training deep neural networks. The key ingredient is a new smoothness condition derived from practical neural network training examples. We observe that gradient smoothness, a concept central to the analysis of first-order optimization algorithms that is often assumed to be a constant, demonstrates significant variability along the training trajectory of deep neural networks. Further, this smoothness positively correlates with the gradient norm, and contrary to standard assumptions in the literature, it can grow with the norm of the gradient. These empirical observations limit the applicability of existing theoretical analyses of algorithms that rely on a fixed bound on smoothness. These observations motivate us to introduce a novel relaxation of gradient smoothness that is weaker than the commonly used Lipschitz smoothness assumption. Under the new condition, we prove that two popular methods, namely, \emph{gradient clipping} and \emph{normalized gradient}, converge arbitrarily faster than gradient descent with fixed stepsize. We further explain why such adaptively scaled gradient methods can accelerate empirical convergence and verify our results empirically in popular neural network training settings.

1 INTRODUCTION

The paper addresses limited understanding of why adaptive methods outperform fixed-step gradient descent in some neural-network tasks. It introduces an empirically motivated relaxed smoothness condition and proves that clipped and stochastic clipped gradient methods can be arbitrarily faster than fixed-step counterparts.

Adaptive gradient methods often outperform SGD in reinforcement learning and NLP, but the reasons for their fast convergence remain limited.
Gradient clipping is analyzed as a standard neural-network training technique whose fast convergence previously lacked firm theoretical grounding.
The proposed smoothness condition is supported by neural-network experiments and is strictly weaker than the standard Lipschitz-gradient assumption.
Fixed-step GD can be arbitrarily slower than clipped GD, and stochastic clipped GD can be arbitrarily faster than fixed-step SGD.
Experiments in language modeling and computer vision show correlations between smoothness and gradient norm, faster training-error convergence with clipping, and trajectories crossing non-smooth regions.

2 A NEW RELAXED SMOOTHNESS CONDITION

The paper argues that global Lipschitz smoothness is restrictive because local smoothness varies during neural-network training and correlates positively with gradient norm. It therefore introduces a weaker condition allowing local smoothness to increase with gradient magnitude.

2.1 FUNCTION SMOOTHNESS (LIPSCHITZ GRADIENTS): Global Lipschitz smoothness can be restrictive: simple functions may violate it, while compact-region bounds can become large and slow fixed-step GD.
2.1 FUNCTION SMOOTHNESS (LIPSCHITZ GRADIENTS): During neural-network training, estimated function smoothness varies across iterations and positively correlates with the full gradient norm, especially in language modeling.
2.2 A NEW RELAXED SMOOTHNESS CONDITION: The paper introduces a relaxed smoothness condition motivated by experiments and designed to permit local smoothness to grow with function gradients.
2.2 A NEW RELAXED SMOOTHNESS CONDITION: The new condition is strictly weaker than ordinary L-smoothness and can describe functions that are globally relaxed-smooth but not globally L-smooth.
2.2 A NEW RELAXED SMOOTHNESS CONDITION: Positive correlation, rather than an exact linear relation, between Hessian and gradient norms is sufficient for the faster-rate argument.
2.2 A NEW RELAXED SMOOTHNESS CONDITION: In deep linear networks, shared weight products and residual terms can make gradient and Hessian norm upper bounds increase together.

3 PROBLEMS SETUP AND ALGORITHMS

The paper formulates nonconvex optimization under the relaxed smoothness condition and reviews fixed-step GD, clipped GD, normalized GD, and their stochastic variants. Clipped GD and normalized GD are equivalent up to a constant step-size factor.

The optimization target is an ϵ-stationary point of a lower-bounded, twice-differentiable nonconvex objective.
The smoothness and regularity assumptions need only hold in a neighborhood determined by the initialization's sublevel set.
The section introduces ordinary gradient descent with a fixed step size, clipped gradient descent, normalized gradient descent, and stochastic versions using gradient estimators.
Clipped GD and normalized GD are almost equivalent under a corresponding rescaling of their step-size parameters.

4 THEORETICAL ANALYSIS

The analysis develops convergence guarantees for clipped GD and fixed-step GD under relaxed smoothness, then extends the comparison to stochastic gradients. It shows fixed-step GD can be arbitrarily slower when gradient-dependent smoothness is large, while stochastic clipped GD also admits an upper bound under bounded noise.

Framework: The analysis addresses oracle and iteration complexity for GD and clipped GD under a relaxed smoothness condition, noting that standard descent-lemma arguments no longer directly apply.The paper highlights the absence of Lipschitz smoothness as a key theoretical challenge.
Deterministic setting: The fixed-step GD lower bound shows that faster convergence cannot generally be obtained under the relaxed smoothness condition without additional assumptions on gradient norms.The paper states that fixed-step GD is suboptimal under this condition and that an additional gradient-norm assumption is needed for its upper bound.
Deterministic setting: Clipped GD can be arbitrarily faster than GD when L1M is large, corresponding to problems with poor initialization.The comparison follows from the deterministic convergence bounds for the two methods.
Deterministic setting: Fixed-step GD converges in O((ML1 + L0)(f(x0) − f∗)/ϵ^2) iterations under the stated assumptions.This rate is described as tight up to a log factor in M.
Stochastic setting: SGD still requires an additional assumption and can be arbitrarily slower than clipped SGD when M is large, while a lower bound for SGD is not provided.The deterministic lower bound remains valid for SGD but is described as probably loose.

5 EXPERIMENTS

Experiments examine how local smoothness relates to gradient norms and whether clipping accelerates neural-network training. The results show stronger correlation in language modeling and faster convergence with clipping across both language modeling and image classification.

Experiments evaluate language modeling on Penn Treebank with AWD-LSTM models and image classification with ResNet20 on CIFAR10.
Local smoothness constants are evaluated against gradient norms at points generated by the optimization procedure, using log-scale scatter plots.
The gradient-norm/local-smoothness correlation appears in default language-model training but not in default image-classification training.
Clipping and large learning rates produce the observed correlations, while clipping enables trajectories to traverse non-smooth regions stably.
Clipping accelerates convergence; clipped LSTM training achieves the best validation performance and fastest training-loss convergence.
For image classification, clipped gradient descent converges fastest and matches the test performance of SGD+momentum.

6 DISCUSSION

The discussion positions relaxed smoothness and clipping as a way to narrow the gap between theoretically accelerated and empirically fast optimization. It also highlights tuning concerns and open questions about broader adaptive methods.

The paper targets the gap between theoretically accelerated algorithms and empirically fast algorithms.
A relaxed smoothness assumption supported by empirical evidence yields theoretical guarantees that clipping can accelerate gradient descent.
Open questions include finding better relaxed conditions, analyzing momentum, preconditioning, and variance reduction, and designing faster methods for neural-network training.
In ResNet training, gradient descent and clipped gradient descent with large step sizes can achieve test performance similar to momentum-SGD.
The authors caution that baseline algorithms may outperform newer methods, making proper baseline tuning important when evaluating algorithms.

A MORE RELATED WORK ON ACCELERATING GRADIENT METHODS

Related work covers variance reduction, momentum-based acceleration, and adaptive step-size methods. These lines of research provide established approaches for accelerating gradient-based optimization.

Variance reduction accelerates stochastic and finite-sum optimization by averaging stochastic-oracle noise using objective smoothness.
Momentum methods derive acceleration guarantees for quadratic and smooth convex optimization and extend them to related settings.
Adaptive step-size methods dynamically vary learning rates, including strategies based on line search, suboptimality, gradient norms, and gradient sparsity.
Recent theory studies convergence of adaptive methods such as AMSGrad, Adagrad, and Padam for nonconvex stochastic problems.

B CHALLENGES IN THE PROOFS

The proofs must handle relaxed smoothness, algorithm-specific lower bounds, and stochastic-gradient dependence on adaptive step sizes. The analysis uses distance bounds from clipping and Grönwall’s inequality to address these difficulties.

Relaxed smoothness makes convergence analysis harder because a key term can increase exponentially with ||y − x||2.
The proof controls the distance moved by clipping and applies Grönwall’s inequality to address the relaxed-smoothness challenge.
Theorem 4 gives a novel algorithm-specific lower bound that is tight up to a logarithmic factor.
In nonconvex stochastic analysis, stochastic gradients depend on update step sizes, creating a correlation challenge for adaptive methods.

C PROOF OF THEOREM 3

The proof bounds gradients near the current iterate, derives a descent inequality under adaptive step-size control, and telescopes the resulting decrease over iterations.

A Grönwall-based lemma bounds the neighboring gradient norm by 4(L0/L1 + ||∇f(x)||).
The proof parameterizes the update path and combines Taylor’s theorem, triangle inequality, Cauchy–Schwarz, and the lemma.
The descent inequality applies when hk ≤ 1/(5L0 + 4L1||∇f(xk)||).
Assuming ||∇f(xk)|| remains at least ϵ through T iterations, telescoping yields the convergence bound.

D PROOF OF THEOREM 4

The proof establishes a lower bound for fixed-step gradient descent by contrasting objectives that force either divergence or very slow progress under any universally convergent step size.

If fixed step size h exceeds a logarithmic threshold, an exponentially growing objective causes the iterates to diverge.
A second objective with slow growth makes the same sufficiently small step size reduce x by only a bounded amount per iteration.
The proof controls the gradient along the update path using continuity, the smoothness assumptions, Taylor expansion, and a contradiction argument.
The resulting iteration lower bound follows by summing the per-step progress and applying the theorem’s defining complexity relation.

I A SYNTHETIC EXPERIMENT

A synthetic optimization of f(x) = x^4 compares gradient descent with clipped gradient descent across step sizes, using a clipping threshold of 0.01.

The experiment initializes both algorithms at x0 = 30 while optimizing f(x) = x^4.
Within [−30, 30], the objective satisfies f′′(x) ≤ 10f′(x) + 0.1.
Gradient descent scans step sizes, whereas clipped gradient descent fixes threshold 0.01 and scans its step size.
The reported convergence results show clipped gradient descent converging much faster than vanilla gradient descent.

J A QUANTITATIVE COMPARISON OF THEOREMS AND EXPERIMENTS

The paper compares theorem-predicted and empirical convergence differences for a synthetic objective and a neural-network language-model experiment.

The synthetic theory predicts an approximately 1e5 gradient ratio favoring clipped GD, while the experiment reports approximately 1e7.
The synthetic clipped-GD result is f′(xT) = 1.3e−8 versus 0.36 for GD.
For the smaller PTB LSTM experiment, theory predicts a gradient ratio of roughly 5, while the empirical ratio is approximately 3.
The authors attribute the theory–practice discrepancy in the neural-network experiment partly to noise, which affects convergence rates but is omitted from rough estimates.