Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity
Authors: Jingzhao Zhang
Tianxing He
Suvrit Sra
Ali Jadbabaie
Venue:  (2020)
Keywords: Adaptive methods
optimization
deep learning

Abstract: 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, gradient clipping and 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.

Published as a conference paper at ICLR 2020
WHY GRADIENT CLIPPING ACCELERATES TRAINING: A THEORETICAL JUSTIFICATION FOR ADAPTIVITY
Jingzhao Zhang, Tianxing He, Suvrit Sra & Ali Jadbabaie Massachusetts Institute of Technology Cambridge, MA 02139, USA (jzhzhang, tianxing, suvrit, (adbabai)emin edu
ABSTRACT
We provide theoretical explanation for the effectiveness of gradient clipping in training deep neural networks. The key ingredient 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 constant, demonstrates significant variability along the training trajectory of deep neural networks. Further, this smoothness posi- tively correlates with the gradient norm, and contrary standard assumptions in the literature, it can grow with the norm of the gradient. These empirical observa- tions 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, gradiens clipping and 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.
INTRODUCTION
We study optimization algorithms for neural network training and aim to resolve the mystery of why adaptive methods converge fast. Specifically, we study gradient-based methods for minimizing a differentiable nonconvex function f IRd -> RR, where (xx can potentially be stochastic, i.e.,
f() = Fg [F(x,, {) Such choices of f cover wide range of problems in machine learning, and their study motivates a vast body of current optimization literature.
A widely used (and canonical) approach for minimizing f is the (stochastic) gradient descent (GD) algorithm. Despite its simple form, GD often achieves superior empirical (Wilson et al., 2017) performances and thcoretical (Carmon al., 2017) guarantees. However, in many tasks such as reinforcement learning and natural language processing (NLP), adaptive gradient methods (c.g., Adagrad (Duchi et al., 201 1), ADAM (Kingma and Ba, 2014), and RMSProp (Tieleman and Hinton, 2012)) outperform SGD. Despite their superior empirical performance, our understanding of the fast convergence of adaptive methods is limited. Previous analysis has shown that adaptive methods are more robust to variation in erper-parameters (Ward et al., 2018) and adapt to sparse gradients (Duchi al., 2011) 1) (a more detailed literature review is in Appendix A). However, in practice, the gradient updates are dense, and even after extensively tuning the SGD hyperparameters, it still converges much slower than adaptive methods NLP tasks.
We analyze the convergence of clipped gradient descent and provide an explanation for its fast con- vergence. Even though gradient clipping is standard practice tasks such as language models (e.g. Merity et al., 2018; Gehring et al., 2017; Peters et al., 2018), it lacks a firm theoretical grounding. Goodfellow et al. (2016); Pascanu et al. (2013; 2012) discuss the gradient explosion problem re- current models and consider clipping as an intuitive work around. We formalize this intuition and prove that clipped GD can converge arbitrarily faster than fixed-step gradient descent. This result is shown to hold under novel smoothness condition that is strictly weaker than the standard Lipschitz- gradient assumption pervasive in the literature. Hence our analysis captures many functions that are not globally Lipschitz. smooth. Importantly, the proposed smoothness condition derived the

---

Published as a conference paper at ICLR 2020
basis of extensive NLP training experiments, which precisely the same type of experiments for which adaptive gradient methods empirically perform superior to gradient methods.
By identifying new smoothness condition through experiments and then using it to analyze methods, we reduce the following gap between theory and
the convergence of adaptively-seaa practice. On one hand, powerful techniques such Nesterov's momentum and variance reduction theoretically accelerate convex and nonconvex optimization. But, at least for now, they seem to have limited applicability in deep learning (Defazio and Bottou, 2018). On the other hand, some widely used techniques (e.g., heavy-ball momentum, adaptivity) lack theoretical acceleration guar- antees. We suspect that a major reason here is the misalignment of the theoretical assumptions with practice. Our work demonstrates that the concept of acceleration critically relies on the problem assumptions and that the standard global Lipschitz-gradee some applications and thus must be relaxed to admit wider class of objective functions.
condition may not hold in the case of
1.1 CONTRIBUTIONS
In light of the above background, the main contributions of this paper the following:
Inspired and supported by neural network training experiments, we introduce a new smoothness condition that allows the local smoothness constant increase with the gradient norm. This condition is strictly weaker than the pervasive Lipschitz-gradient gradient assumption.
We provide convergence rate for clipped GD under our smoothness assumption (Theorem 3).
We prove an upper-bound (Theorem 6) and lower-bound (Theorem 4) the convergence rate of GD under our relaxed smoothness assumption. The lower- bound demonstrates that GD with fixed step size be arbitrarily slower than clipped GD.
We provide upper bounds for stochastic clipped GD (Theorem 7) and SGD (Theorem 8). Again, stochastic clipped GD can be arbitrarily faster than SGD with a fixed step size.
We support our proposed theory with realistic neural network experiments. First, in the state of art LSTM language modeling (LM) setting, we observe the function smoothness has strong correlation with gradient norm (see Figure 2). This aligns with the known fact that gradient clipping accelerates LM more effectively compared to computer vision (CV) tasks. Second, our experiments in CV and LM demonstrate that clipping accelerates training error convergence and allows the training trajectory to cross non-smooth regions of the loss landscape. Furthermore, gradient clipping can also achieve good generalization performance even in image classification (e.g., 95.2% test accuracy in 200 epochs for ResNet20 on Cifarl0) Please see Section 5 for more details.
2 A NEW RELAXED SMOOTHNESS CONDITION
In this section, motivate and develop a relaxed smoothness condition that is weaker (and thus, more general) than the usual global Lipschitz smoothness assumption. We start with the traditional definition of smoothness.
2.1 FUNCTION SMOOTHNESS (LIPSCHITZ GRADIENTS)
Recall that f denotes the objective function that we want to minimize. We say that f is L-smooth
[ ( s T.Ilx= vll. for all x, y Rd.
For twice differentiable functions, condition (1) equivalent to IIV2 < L. E Rd. This smoothness condition enables many important theoretical results. For example, Carmon et al. (2017) show that GD with h = 1/T. up to a constant optimal for optimizing smooth nonconvex functions.
But the usual L-smoothness assumption (1) also has its limitations. Assuming existence of a global constant that upper bounds the variation of the gradient is very restrictive. For example, simple polynomials such f(x) IZ break the assumption. One workaround is to assume that L exists in a compact region, and either prove that the iterates do not escape the region or run projection- based algorithms. However, such assumptions can make L very large and slow down the theoretical convergence rate. In Section 4, we will show that a slow rate is unavoidable for gradient descent with fixed step size, whereas clipped gradient descent can greatly improve the dependency on L..
2

---

Published as a conference paper at ICLR 2020
The above limitations force fixed-step gradient descent (which is tailored for Lipschitz smooth fune- tions) to converge slowly in many tasks. In Figure I, we plot the estimated function smoothness at different iterations during training neural networks. We find that function smoothness varies greatly at different iterations. From Figure 1, we further find that local smoothness positively correlates with the full gradient norm, especially in the language modeling experiment. A natural question is:
Can we find a fine-grann ane-grained smoothness condition under which we can design the- oretically and empirically fast algorithms at the same time?
To answer this question, introduce the relaxed smoothness condition in the next section, which developed on the basis of extensive experiments Figure provides an illustrative example.
log(smoothness
-0.5
-1.0
Iteration
-1.5
300
-2.0
2.55
200
100
-3.5
log(gradient norm)
Figure I: Gradient norm vs local gradient Lipschitz constant on log-scale along the training trajectory for AWD-LSTM (Merity et al., 2018) on PTB dataset. The colorbar indicates the number of iterations during training. More experiments can be found in Section 5. Experiment details are in Appendix H.
2.2 NEW RELAXED SMOOTHNESS CONDITION
We observe strong positive correlation between function smoothness and gradient in language modeling experiments (Figure (a)). This observation leads us to propose the following smoothness condition that allows local smoothness grow with function gradients.
Definition 1. A second order differentiable function f (Lo, L1)-smootee if
V f(x)l < Lo + f(z)]
Definition strictly relaxes the usual (and widely used) L-smoothness. There are two ways to interpret the relaxation: First, when we focus on a compact region, we can balance the constants Lo and L1 such that Lo < L while L1 < L. Second, there exist functions that are (Los L1) -smoshh globally, but not L-smooth. Hence the constant L for L-smoothness gets larger as the compact set increases but La and L, stay fixed. An example is given in Lemma 2.
Remark 1. It is worth noting that do not need the Hessian operator norm and gradient norm to necessarily satisfy the linear relation (2). As long as these norms are positively correlated, gradient clipping can be shown achieve faster rate than fixed step size gradient descent. We use the linear relationship (2) for simplicity of exposition.
Lemma 2. Let be the univariate polynomial f(x) = Σ agrh When d 2 3, then (Lo, In)- smooth for some To and I, but not L-smooth.
Proof. The first claim follows from lim
(() P())
lim
f(()) ["(a]
The second claim
follows by the unboundedness of (*()).
2.3 SMOOTHNESS IN NEURAL NETWORKS
We saw that smoothness condition relaxes the traditional smoothness assumption and is moti- vated empirically (Figure 1). Below we develop some intuition for this phenomenon. We conjecture that the proposed positive correlation results from the common components in expressions of the gradient and the Hessian. We illustrate the reasoning behind this conjecture by considering an l- layer linear network with quadratic loss-a similar computation also holds for nonlinear networks.
3

---

Published as a conference paper at ICLR 2020
The Le regression loss of deep linear network is L(Y, f(X) == || We... W2 where denotes labels, X denotes the imput data matrix, and W; denotes the weights the hhh layer. By (Lemma 4.3 Kawaguchi, 2016), we know that
V veo(wu)) C(Y,5(X) = .W..... W(+1) & "WWW (xo(f(X)-Y)
where v-c(.) flattens matrix R into a vector Rm";; denotes the Kronecker product. For constants j such that f 2 j > > 0, the second order derivative
V (vo((ng)) V voc((n;) f(Y f(X))
(WW ... W(+1) @ (W X -W5+) @ (W W2W1X)" (WW----..WW
@ (W,-1- ... W2W1 @ - ....................... W)+1)).
When = i, the second term equals O. Based on the above expressions. we notice that the gradient norm and Hessian norm may be positively correlated due to the following two ohservations. First, the gradient and the Hessian share many components such the matrix product of weights across layers. Second, if one naively upper bounds the norm using Cauchy-Schwand then both upper- bounds would be monotonically increasing with respect |Wil and [| Y|
PROBLEMS SETUP AND ALGORITHM
In this section, state the optimization problems and introduce gradient based algorithms for them that work under the new smoothness condition (2). Convergence analysis follows in Section 4.
Recall that wish solve the nonconvex optimization problem min f(z). Since in general this problem is intractable, following common practice we also seek an e-stationary point, i.c. a point such that || (x=)ll S Furthermore, make the following assumptions regularize the function class studied and subsequently provide nonasymptotic convergence rate analysis.
Assumption 1. The function f is lower bounded by Assumption 2. The function f is twice differentiable.
-00.
Assumption ( (Lo, I1 In)-smoothness) The function is (Lo, L1) smooohh, i.e., there exist positive constants Lo and L1 such that V fx)]] < Lo L1 L [[]][((]]]]/) see condition (2).
The first assumption is standard. Twice differentiability in Assumption can relaxed to first-order differentiability by modifying the definition of (Lo, Li)-smoothness
limsup sup (V(a))V(((r)) < L1 [ Lo.
The above inequality implies Vs(x) is locally Lipschitz, and hence almost everywhere differen- tiable. Therefore, all our results can go through by handling the integrations more carefully. But to avoid complications and simplify exposition, we assume that the function is twice differentiable.
To further relax the global assumptions, by showing that GD and clipped GD are monotonically decreasing in function value, require the above assumptions to hold just in neighborhood de- termined by the sublevel set S for a given initialization Fo. where
S = fx y such that f(y) I fzo), and || yll $ 1}.
(3)
3.1 GRADIENT DESCENT ALGORITHMS
In this section, review few well-known variants of gradient based algorithms that analyze. We start with the ordinary gradient descent with a fixed step size y).
Fk+1
1) V fxxx).
(4)
This algorithm (pedantically, its stochastic version) is widely used in neural network training. Many modifications it have been proposed to stabilize or accelerate training. One such technique of particular importance is clipped gradient descent, which performs the following updates:
Tk+1 z₁ h. (Fx)). where h. min [[V }
(5)
'The constant "1" in the expression (3) arbitrary and he replaced by any fixed positive constant.
4

---

Published as a conference paper at ICLR 2020
Another algorithm that is less common in practice but has attracted theoretical interest is normalized gradient descent. The updates for normalized GD method can be written as
1k+1 Fk h4 V (ark): where hy |V
The stochastic version of the above algorithms replace the gradient with stochastic estimator.
We note that Clipped GD and NGD are almost equivalent. Indeed, for any given 7in and 3, if we set Mc = 7/ and T/c = Tp/ B, then we have
hn S 2h.-
Therefore, clipped GD is equivalent to NGD up to constant factor in the step size choice. Conse- quently, the nonconvex convergence rates in Section 4 and Section 4.2 for clipped GD also apply to NGD. We omit repeating the theorem statements and the analysis for conciseness.
THEORETICAL ANALYSIS
In this section, we analyze the oracle complexities of GD and clipped GD under our relaxed smooth- ness condition. All the proofs are in the appendix. We highlight the key theoretical challenges that needed overcome in Appendix B (e.g.. due to absence Lipschitz-smoothness already the first- step of analysis, the so-called "descent lemma" fails).
Since we are analyzing the global iteration complexity, let us recall the formal definition being used. We follow the notation from Carmon et al. (2017). For deterministic sequence (KN) define complexity of (Itx JEN for a function f
Te (Ha (Hat)eNN, f) inf(t N|| c).
For random process {EE]KEN we define the complexity of {Ix JEN for function f
Tefaaeee f) == inf N[Prob([IVf(xx)] 2 for all k S }}
(8)
In particular, if the condition is never satisfied, then the complexity is co. Given an algorithm Aos where 0 denotes hyperparameters such step size and momentum coefficient, we denote Aslf, mop as the sequence (potentially stochastic) iterates generated by A when operating on f with ini- tialization zp. Finally, we define the iteration complexity of algorithm class parameterized by hyperparameters, A } on a function class as
N(A,F,c)
inf sup ZOER .FEF
Te(Aoff,
ADEA
The definition in the stochastic setting simply replaces the expression (7) with the expression (8). In the of the paper, "iteration complexity" refers the quantity defined above.
4.1 CONVERGENCE IN THE DETERMINISTIC SETTING
In this section, present the convergence rates for GD and clipped GD under deterministic setting. We start by analyzing the clipped GD algorithm with update defined in equation (5).
and 3 in set S defined Theorem 3. Let F denote the class of functions that satisfy Assumptions 1
in (3). Recall f is global lower bound for function value. With ne 107, 7 min n 101.gn
1
we can prove that the iteration complexity of clipped GD (Algorithm 5) is upper bounded by
20Lo( -8)) 20 maxxx(1 (1, (f))(( - -
2
La
The proof of Theorem 3 is included in Appendix C.
Now, we discuss the convergence of vanilla GD. The standard GD is known to converge to first order c-stationary points in ((((f(zz) f()) iterations for (I, 0) smooth nonconvex functions. By Theorem of Carmon et al. (2017), this rate is up to a constant optimal.
However, we will show below that gradient descent is suboptimal under our relaxed (Lo, L1)- smoothness condition. In particular, to prove the convergence rate for gradient descent with fixed step size, we need to permit it benefit from additional assumption gradient norms.
5

---

Published as a conference paper at ICLR 2020
Assumption 4. Given initialization zo, assume that
M = sup such that f(x) S ((o)) < oo.
This assumption is in fact necessary. as our next theorem reveals.
Theorem 4. Let be the class of objectives satisfying Assumptions 1. 2, 3, and with fixed con-
stants Lo 1, I1 Z 1, M > 1. The iteration complexity for the fixed-step gradient descent algorithms parameterized by step size h is at least
I M) -5c/8)
Sco NoggMr +
The proof can be found in Appendix D. Remark 5. Theorem of Carmon et al. (2017) and Theorem 4 together show that gra- dient descent with a fixed step size cannot converge to an e-stationary point faster than Q ML log//))g(MMMM (J(oo) (- Recall that clipped GD algorithm converges as O (Lo(f(z))-)) - f) than GD when L is large, or in other words, when the problem has poor initialization.
Therefore, clipped GD can be arbitrarily faster
Below, we provide iteration upper bound for the fixed-step gradient descent update (4).
Theorem 6. Suppose assumptions 2, and 4 hold in set S defined in (3). If we pick parameters such that h LZ]ML then can prove that the iteration complexity of GD with fixed step size defined Algorithm 4 is upper bounded by
4(ML, + (o)(f(z)) f
Please refer Appendix for the proof. Theorem shows that gradient descent with fixed step size converges in P(MLi + (zro) - /*²) iterations. This suggests that the lower bound in Remark is tight up log factor in M.
4.2 CONVERGENCE IN THE STOCHASTIC SETTING
In the stochastic setting, we assume GD and clipped GD have access to unbiased stochastic gradient V fz)) instead of the exact gradient ff(x). For simplicity, we denote 9& f((x)) below. To prove convergence, we need the following assumption.
Assumption 5. There exists f > 0, such that |/V fxx) V < almost surely.
Bounded noise be relaxed to sub- uub-gaussian noise if the noise is symmetric. Furthermore, up to our knowledge, this is the first stochastic nonconvex analysis of adaptive methods that does not require the gradient norm [[V[(=)]] to be bounded globally.
The main result of this section is the following convergence guarantee for stochastic clipped GD (based on the stochastic version of the update (5)).
Theorem 7. Let Assumptions 1-3 and 5 hold globally with Ia > O. Let h = 1
min 169Ln "7) where ni min{ 20L0' 128L,7' ) Then we show that iteration complexity for stochastic clipped GD after of update (5) upper bounded by
1
A max 128L1 4A 80La + 512LIT
2²
where A = (f((r) - (5L0 + 2L L/
In comparison, have the following upper bound for ordinary SGD.
Theorem 8. Let Assumptions 1-3, and hold globally with L, > 0. Let min v (((447) Then the iteration complexity for the stochastic version of GD (4) is upper bounded by
(f(xo) f r
(5Lg + ALL + +
We cannot provide a lower bound for this algorithm. In fact, lower bound is not known for SGD even the global smoothness setting. However, the deterministic lower bound in Theorem 4 is still valid, though probably loose. Therefore, the convergence of SGD still requires additional assumption and can again be arbitrarily slower compared clipped SGD when M is large.

---

Published as a conference paper at ICLR 2020
0.0
100
1.0
500
logismoothnent
-1.
-03
400
kogismoothness
0.50
0.22
402
500
legfsmoothnesse
400
-15
0.00
300
303
-20
-0:25
-25
200
-0.30
203
200
-30
-0.75
-35
-1.00
-10
Ing(gradient norm)
Ingigradient norm)
logigradient norm)
(a) Learning rate 30, with clipping. (b) Learning rate 2, without clipping. (c) Learning rate 2, with clipping.
Figure 2: Gradient norm vs smoothness on log scale for LM training. The dot color indicates the iteration
number Darker ones corresnond to earlier iterations. Note that the smans of v. and w axis are not fixed
350
350
350
toglsmecchess)
300
legfsmoothness
300
hegfsmoetheee
300
200
200
200
150
150
150
50
50
50
log(gredient norm)
logfgradient norm!
loglgradient norm)
(a) SGD with momentum.
(b) Learning rate 1, without clipping. (c) Learning rate 5, with clipping.
Figure 3: Gradient norm vs smoothness on log scale for ResNer20 training. The dot color indicates the
iteration number.
EXPERIMENTS
In this section, we summarize our empirical findings on the positive correlation between gradient norm and local smoothness. We then show that clipping accelerates convergence during neural network training. Our experiments are based on two tasks: language modeling and image classifi- cation. We language modeling the Penn Treebank (PTB) (Mikolov et al., 2010) dataset with AWD-LSTM models (Merity et al., 2018)2. We train ResNet20 (He et al., 2016) on the Cifarl0 dataset (Krizhevsky and Hinton, 2009). Details about the smoothness estimation and experimental setups are in Appendix H. An additional synthetic experiment is discussed in Appendix I.
First, our experiments test whether the local smoothness constant increases with the gradient norm, as suggested by the relaxed smoothness conditions defined in (2) (Section 2). To do so, we evaluate both quantities points generated by the optimization procedure. We then seatter the local smooth- ness constants against the gradient norms in Figure 2 and Figure 3. Note that the plots are on log-scale. A linear scale plot is shown Appendix Figure
We notice that the correlation exists in the default training procedure for language modeling (see Figure 2a) but not the default training for image classification (see Figure 3a). This difference aligns with the fact that gradient clipping is widely used in language modeling but is less popular in ResNet training, offering empirical support to our theoretical findings.
We further investigate the cause of correlation. The plots in Figures 2 and 3 show that correlation appears when the models are trained with clipped GD and large learning rates. We propose the fol- lowing explanation. Clipping enables the training trajectory to stably traverse non-smooth regions. Hence, we can observe that gradient norms and smoothness are positively correlated in Figures 2a and 3c. Without clipping, the optimizer has adopt small learning rate and stays in region where local smoothness does not vary much, otherwise the sequence diverges, and a different learning rate used. Therefore, other plots of Figures 2 and 3, the correlation is much weaker.
As positive correlations are present in both language modeling and image classification experiments with large step sizes, our next set of experiments checks whether clipping helps accelerate conver- gence as predicted by our theory. From Figure 4, we find that clipping indeed accelerates conver- gence. Because gradient clipping trained with clipping achieve the best validation performance and the fastest training loss conver-
standard practice language modeling, the LSTM models
Part of the code is available at http::///gghhhbbcco/////hhhahaa/ why-cl anpping-aceelleeee

---

Published as a conference paper at ICLR 2020
1:3clipp:25
1r10dip0.25
1r5clip0.25
Ir2undliped
Irlunclipped
Ir0 Sunclippe
5.5
5.5
4.5
Validation
5.0
3.5
2.5
4.0
0
100
150
200
100
150
20D
Epochs
Epochs
Training loss of LSTM with different op- timization parameters.
Validation loss of LSTM with different optimization parameters.
Irlunclipped
irsunclipped
n0.1mmmentum0.3
Iriclipped
r5clipped
2.00
100.0
1.75
1.50
59.0
1:25
4.00
50.0
0.50
0.25
0.20
1.25
150
175
Epocns
530.77
(c) Training loss of ResNet20 with different optimization parameters.
(d) Test accuracy of ResNet20 with differret optimization parameters.
Figure 4: Training and validation loss obtained with different training methods for LSTM and ResNet training. The validation loss plots the cross entropy. The training loss additionally includes the weight regularization term. the legend, 'Ir30clip0.25' denotes that clipped SGD uses step size 30 and that the La norm of stochastic gradient clipped by 0.25. ResNet training, we threshold the stochastic gradient norm at 0.25 when clipping is applied.
gence expected. For image classification, surprisingly, clipped GD also achieves the fastest con- vergence and matches the test performance SGD+momentum. These plots show that clipping can accelerate convergence and achieve good test performance the same time.
DISCUSSION
Much progress has been made to close the gap between upper and lower oracle complexities for first order smooth optimization. The works dedicated this goal provide important insights and tools for us to understand the optimization procedures. However, there is another gap that separates theoretically accelerated algorithms from empirically fast algorithms.
Our work aims to close this gap. Specifically, we propose relaxed smoothness assumption that supported by empirical evidence. We analyze simple but widely used optimization technique known as gradient clipping and provide theoretical guarantees that clipping can accelerate gradient descent. This phenomenon aligns remarkably well with empirical observations.
There is still much to be explored in this direction. First, though our smoothness condition relaxes the usual Lipschitz assumption, is unclear there an even better condition that also matches the experimental observations while also enabling clean thcoretical analysis. Second, we only study convergence of clipped gradient descent. Studying the convergence properties of other techniques such momentum, coordinate-wine learning rates (more generally, preconditioning), and variance reduction also interesting. Finally, the most important question is: "can we fast based relaxed conditions that achieve faster convergence in neural network training?"
fast algorithms
Our experiments also have noteworthy implications. First, though advocating clipped gradient de- scent in ResNet training is not main point of this work, it is interesting note that gradient
8

---

Published as a conference paper at ICLR 2020
descent and clipped gradient descent with large step sizes achieve similar test performance as momentum-SCO Second, we learned that the performance of the baseline algorithm can actually beat some recently proposed algorithms. Therefore, when design learn about new algorithms, we need to pay extra attention to check whether the baseline algorithms are properly tuned.
7 ACKNOWLEDGEMENT
SS acknowledges support from an NSF-CAREER Award (Number 1846088) and an Amazon Re- search Award. AJ acknowledges support from MTT-IBM-Explorttory project on adaptive, robust, and collaborative optimization.
REFERENCES
N. Agarwal, B. Bullins, X. Chen, E. Hazan, K. Singh, C. Zhang, and Y. Zhang. The case for full- matrix adaptive regularization. arXiv preprint arXiv: 02958, 2018.
Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Research, 18(1):8194-8244 2017.
L. Armijo. Minimization of functions having Lipschitz continuous first partial derivatives. Pacific Journal of mathematics, 16(1):1-3, 1966.
Bach and E. Moulines. Non- strongly-conve smooth stochastic approximation with convergence rate o(1 ((1/m) 1/nn). In Advances in Neural Information Processing Systems, pages 773-781, 2013.
A. Beck and M. Teboulle. A fast iterative
thresholding algorithm for linear inverse prob- lems. SIAM journal on imaging sciences, 2(1): 1011833-000 202, 2009.
Y. Carmon, C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points arXiv preprint arXiv: 1710. 1660,, 2017.
Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Accelerated methods for nonconvex optimiza- tion. SIAM Journal on Optimization, 28(2):1751-177) 2018.
X. Chen, S. Liu, R. Sun, and M. Hong. On the convergence a class of adam-type algorithms for non-convex optimization. arXiv preprint w:Xiv:188.0029411 2018.
K. Cho, B. van Merriënboer, Ç. Gülçehre, D. Bahdanau, Bougares, H. Schwenk, and Y. Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLL)), pages 1724-1734, Doha, Qatar, Oct. 2014. Association for Computational Linguistics. org/ httg://nthlooyy..o
URL http:
acwweb. wwt.w/wwwwww.cc.............oo.l
Z. Dai, Z. Yang. Y. Yang. J. G. Carbonell, Q. V. Le, and R. Salakhutdinov. Transformer-XIL At- tentive language models beyond fixed-length context. CoRR, abs/1901.022600 2019. URL
http: http//aaxivv... org/
wtwpgg/ab////e abs ttabs//911. /1001 02860.
A. Defazio and L. Bottou. On the ineffectiveness of variance reduced optimization for deep learning.
arXiv preprint arXiv: 1XX.:18822.0529 2018.
A. Defazio, F. Bach, and S. Lacoste-Julicn SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. NIPS, pages 1646-1654, 2014.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic
optimization. Journal of Machine Learning Research, 120ul))2121-2159, 2011.
C. Fang. C. Li, Z. Lin, and T. Zhang. Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator. arXiv preprint 1rXiv: 2018.
J. Gehring, M. Auli, D. Grangier, D. Yarats, and Y. N. Dauphin. Convolutional sequence to sequence learning. ArXiv e-prints, May 2017.
S. Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22 14):,, 2012.
S. Ghadimi and G. Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1-2):59-99) 2016.

---

Published as a conference paper at ICLR 2020
P. Gong and J. Ye. Linear convergence of veriaece-reduced stochastic gradient without strong con- vexity, arXiv preprint arXiv: 102, 2014.
I. Goodfellow, Y. Bengio, and A. Courville. Deep learning. MIT press, 2016.
E. Hazan, K. Levy, and S. Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex optimiza- tion. In Advances Neural Information Processing Systems, pages 1602, 2015.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation, 735-1778, 1997.
C. Jin, P. Netrapalli, and M. I. Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pages 1042-1085, 2018.
R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduc- tion. In Advances Neural Information Processing Systems, pages 315-323, 2013.
K. Kawaguchi. Deep learning without poor local minima. In Advances in neural information pro- cessing systems, pages 586-594, 2016.
D. P. Kingma and J. Ba. ADAM: A method for stochastic optimization. arXiv preprint arXiv: 14xv::4/2.6998) 2014.
J. Konečný and P. Richtárik. Semi-stochastic gradient descent methods. arXiv:1312. 1666, 2013.
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
K. Levy. The power of normalization: Faster evasion of saddle points. arXiv preprint arXiv:1611.04831, 2016.
X. Li and F. Orabona. On the convergence stochastic gradient descent with adaptive stepsizes. arXiv preprint 1105v 14, 2018
H. Lin, J. Mairal, and Z. Harchaoui. A universal catalyst for first-order optimization. In Advances in Neural Information Processing Systems, pages 3384-3392, 2015.
Merity, N. S. Keskar, and R. Socher. Regularizing and optimizing LSTM language models. In International Conference Learning Representations, 2018. https: /wtp////pppeeeeeeeeeeeee/eeee
net / forum? i ddSyyGPPOTT.
T. Mikolov, M. Karafiát, L. Burget, J. Cernocky, and S. Khudanpur. Recurrent neural network based language model. In INTERSPEECH 2010, 11th Anmual Conference of the International Speech Communicaation Association, AssomiiiiiiiooAAAAsiiiiaiiioo Makuhari, Chiba, Japan, September 26-30, 2010, pages 1045-1048, 2010/i10. 2010. URL http: / www. isca- speech wwtpp///accceeeeeeeeeeeeeeeeeeee 1045. html.
Y. Nesterov. A method of solving convex programming problem with convergence rate ((1/k²).
In Soviet Mathematics Doklady, volume 27, pages 372-376, 1983.
Y. Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimizution, 22(2):341-36) 2012.
R. Pascanu, T. Mikolov, and Y. Bengio. Understanding the exploding gradient problem. CoRR, abs/1211.5063, 2, 2012.
R. Pascanu, T. Mikolov, and Y. Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pages 1310-1318, 2013.
M. E. Peters, M. Neumann, M. Iyyer, M. Gardner, C. Clark. K. Lec, and L. Zettlemoyer. Deep contextualized word representations. arXiv preprint arXiv: 882.005365 2018.
B. T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computa- tional Mathematics and Mathematical Physics, 4(5) 1964.
B. T. Polyak. Introduction optimization. optimization software. Inc., Publications Division, New York, 1, 1987.
S. J. Reddi, S. Kale, and S. Kumar. On the convergence of ADAM and beyond. arXiv preprint 1rXiiv:904.09220
2019.
S. Santurkar, D. Tsipras, A. Ilyas, and A. Madry. How does batch normalization help optimization? In Advances in Neural Information Processing Systems, pages 2483-2493, 2018.
10

---

Published as a conference paper at ICLR 2020
M. Schmidt, N. Le Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming. 162, 2017.
S. Shalev-Shwarde and T. Zhang. Accelerated proximal stochastic dual coordinate ascent for regu- larized loss minimization. In International Conference on Machine Learning, pages 64-72, 2014.
N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting Journal of Machine Learning Research, 15: 1929-1958, 2014. URL http: jmlr org/ hwtp///ppss///eeeee /v15/
html. M. Staib, S. J. Reddi, S. Kale, S. Kumar, and S. Sra. Escaping saddle points with adaptive gradient methods. arXiv preprint arXiv: 09000, 2019.
M. Sundermeyer, R. Schlüter, and H. Ney. LSTM neural networks for language modeling. In INTERSPEECH 2012, 13th Annual Conference of the International Speech Communication As- sociation, Portland, Oregon, USA, September 9-13, 2012, pages 197,197, 2012. URL http: //www.isca= www.:iiscaspeeeeecee wwreech..rg/rrciiieeee. httpaaaaeeeeeeeeeeeeeeeeeeeeeeee
1t1/_112_00111 94 htmll
I. Sutskever, O. Vinyals, and Q. V. Le. Sequence to sequence learning with neural net- works. In Advances Neural Information Processing Systems 27: Annual Confer- ence Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 3104-3112, 2014. URL http:: nip. cia.p..cc/ppprr//
Ticleman and G. Hinton. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
L. Wan, M. Zeiler, S. Zhang, Y. L.. Cun, and R. Fergus. Regularization of neural networks us- ing DropConnect. In S. Dasgupta and D. McAllester, editors, Proceedings of the 30th Inter- national Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1058-1066, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL http: / //proceedings mlr pwessrppees//ee /v28 //anaaan/ 3. html.
R. Ward, X. Wu, and L. Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization. arXiv preprint arXiv: 01811, 2018.
A. C. Wilson, R. Roelofs, M. Stern, N. Srebro, and B. Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pages 4148 4158, 2017.
I. Xiao and T. Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4):2057-2075, 2014.
T. Young, D. Hazarika, S. Poria, and E. Cambria. Recent trends in deep learning based natural language processing. CoRR, tbs//100.002799 2017. httttt////aaiii org. abs/1708 02709.
D. Zhou, Tang, Z. Yang, Y. Cao, and Q. Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv:
2018a.
D. Zhou, P. Xu, and Q. Gu. Stochastic nested variance reduction for nonconvex optimization. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pages 3925-3936. Curran Associates Inc., 2018b.
Z. Zhou, Q. Zhang, G. Lu, H. Wang, W. Zhang, and Y. Yu. Adashift: Decorrelation and convergence of adaptive learning rate methods. arXiv preprint
2018c.
Zou and L. Shen. On the convergence of weighted adagrad with momentum for training deep 03408, neural networks. arXiv preprint arXiv:1806 180,00300, 2018.
Zou, L. Shen, Z. Jie, W. Zhang, and W. Liu. A sufficient condition for convergences of ADAM and RMSProp. arXiv preprint 1811v: 000558, 2018.
11

---

Published as a conference paper at ICLR 2020
A MORE RELATED WORK ON ACCELERATING GRADIENT METHODS
Variance reduction. Many efforts have been made to accelcrate gradient- based methods. One elegant approach is variance reduction (e.g. Schmidt et al., 2017: Johnson and Zhang, 2013; Defazio et al., 2014; Bach and Moulines, 2013; Konečný and Richtárik, 2013; Xiao and Zhang, 2014; Gong and Ye, 2014; Fang et al., 2018; Zhou al., 2018b). This technique aims to solve stochastic and finite sum problems by averaging the noise in the stochastic oracle via utilizing the smoothness of the objectives.
Momentum methods. Another line of work focuses on achieving acceleration with momentum. Polyak (1964) showed that momentum can accelerate optimization for quadratic problems; later, Nesterov (1983) designed variation that provably accelerate any smooth convex problems. Based on Nesterov's work, much theoretical progress was made accelerate different variations of the original smooth convex problems (e.g. Ghadimi and Lan, 2016; 2012; Beck and Teboulle, 2009; Shalev-Shwartz and Zhang, 2014; Jin et al., 2018; Carmon et al., 2018; Allen-Zhu, 2017; Lin al., 2015; Nesterov, 2012).
Adaptive step sizes. The idea of varying step size in each iteration has long been studied. Armijo (1966) proposed the famous backtracking line search algorithm to choose step size dynamically. Polyak (1987) proposed a strategy to choose step size based on function suboptimality and gradient norm. More recently, Duchi et al. (201 1) designed the Adagrad algorithm that can utilize the sparsity in stochastic gradients.
Since 2018, there has been surge in studying the theoretical properties of adaptive gradient meth- ods. One starting point is (Reddi et al., 2019). which pointed out that ADAM is not convergent and fix the problem. Ward al. (2018); Li and Orabona (2018)
proposed the A.SSGrd algorithm prove that Adagrad converges to stationary point for nonconvex stochastic problems. Zhou et al. (2018a) generalized the result to a class of algorithms named Padam. Zou al. (2018); Staib et al. (2019); Chen et al. (2018); Zhou et al. (2018c); Agarwal et al. (2018); Zhou et al. (2018b); Zou and Shen (2018) also studied different interesting aspects of convergence of adaptive methods. In addition, Levy (2016) showed that normalized gradient descent may have better convergence rate in presence of injected noise. However, the rate comparison is under dimension dependent set- ting. Hazan et al. (2015) studied the convergence of normalized gradient descent for quasi-convex functions.
B CHALLENGES IN THE PROOFS
In this section, we highlight few key challenges in proofs. First, the analysis convergence under the relaxed smoothness condition is more difficult than the traditional setup. In particular, classical analyses based Lipschitz-smooth gradients frequently exploit the descent condition:
f(v) < f(x) + (Vf(z), y - z) + f x||2.
(10)
However, under our relaxed smoothness condition, the last term will increase exponentially in lly - 20|2 To solve this challenge, we bound the distance moved by clipping and apply Grönwall's inequality.
Second, our algorithm specific lower bound proved in Theorem is novel and tight up log factor. To our knowledge, the worst case examples used have not been studied before.
Last, proving the convergence of adaptive methods in the nonconvex stochastic setting suffers from a fundamental challenge: the stochastic gradient is dependent on the update step size. This problem usually cireumvented by either assuming gradients have bounded norms by using a lagging-by- one step-size to decouple the correlation. The situation is even worse under the relaxed smoothness assumption. In our case, we overcome this challenge by novel analysis that divides the proof into the large gradient scenario and the small gradient scenario.
C PROOF OF THEOREM 3
We start by proving a lemma that is repeatedly used in later proofs. The lemma bounds the gradient in neighhorhood of the current point by Grönwall's inequality (integral form).
12

---

Published as a conference paper at ICLR 2020
Lemma 9. Given such that f(x) S f(xo), fo for any xt such that || x| min(11/1, 1}, have [Vf((t)] I L1 + [V)())) |
Remark Note that the constant "I" comes from definition (3). If Assumption holds globally, then we do not need to constrain | x|
S 1. This version will be used in Theorem 7.
Proof. Let (() be a curve defined below,
(t) t(x -x+= + + 1,,tt t 10, 1].
Then we have
vf(((t)) [ -
By Cauchy-Schwarz inequality, we get
|V s 11+ - xell / [++))
$ Li I (Lo + L [V](
The second inequality follows by Assumption Then we can apply the integral form of Grönwall's inequality and get
(V Lo + +IVf(a)]++ S.' (En +IV/(())) exp(t T)dT.
L
The Lemma follows by setting 1.
C.1 PROOF THE THEOREM
We parameterize the path between my and its updated iterate 26+ follows:
(t) = t( - I&) + 2b, Vt E [0, 1].
Since F4+1 = -a- - 11 V ((x)), using Taylor's theorem, the triangle inequality, and Cauchy-Schwarz, obtain
f(++11 S f(xx) - hx [f(xx)) | - =x
/
2
Since
77) < min [V] )
hg S
[
we know by Lemma 9
[V)((()) < 4 + [[V((=))).
Then by Assumption we obtain the "descent inequality":
f(Ix+1) f(x)) hu [[xx]) + 5Lo + 4L Vf(zx)]
[V
Therefore, as long as h2 < 1/(5 + 4L, Vf (which follows by our choice of m, 7), we can quantify the descent to be
bullV[((x)]]
((x+1) < f(xx)
When [xv](=))] 2 To/L1, LT, we have
hy Vall(((x))))
Lo
2
20 max (,axxx11,4 I.T
13

---

Published as a conference paper at ICLR 2020
When [ Lo/L,, we have
hy ff(x))?
Vf(xx)]1
e²
2
20Lo
20Lg
Therefore,
Lo
[(x+11) S (xxx) min
20 max
[2)
20T
Assume that e I [V for k < iterations. By doing telescopic sum, we get
Σ ((x+1) - f(xx)= S -T -i'in
Lo
e²
20 max (1, [.3) 20L
Rearranging we get
2fLo(f(zo) f²) fr)
20 max (1, (f f
T 2
Lo
D PROOF OF THEOREM
We will prove lower bound for the iteration complexity of GD with fixed step size. The high level idea is that GD converges for all functions satisfying the assumptions, then the step size needs to be small. However, this small step size will lead very slow convergence for another function.
Recall that the fixed step size GD algorithm is parameterized by the scaler: step size First, we show that when h 2 <log(M)+2
sup 2o(A = 0c
#BER
fEF
We start with a function that grows exponentially, Let L1 > 1, > 1 be fixed constants. Pick the initial point zo (log(M) + 1)/L, Let the objective be defined as follows,
1
for <
Lie
f(z)=
Lyx"
for E - Li 1 21
1/2
for x 1
Lie
We notice that the function satisfies the assumptions with constants
Lg 1, LA 1,
M>
(11)
When h > 2r//M, /,, we would have |<] > |oo] By symmetry of the function and the super-linear growth of the gradient norm, know that the iterates will diverge. Hence, in order for gradient descent with a fixed step size to converge, must be small enough. Formally,
2no 2 2log(M) +2
h <
M
ML1
Second, we show that when h <
2 2log( M+2
MLa
sup T. Tc(Afff, zu), 2 (L M 1))
FEF
Now, let's look at different objective that grows slowly.
-2 + 11 + 3
for < -1,
f(x)
(62 - x²t)
for E 1, 1], for 1.
2r(x 1) + 5c
4
14

---

Published as a conference paper at ICLR 2020
This function is also second order differentiable and satisfies the assumptions with constants in (1 (I).
we set 2o = 1+ A/c for some constant A >> O, we know that f(x)) f 22 + 5e/4. With the
step size choice h log M + 2)/(M11) ). know that in each step, 2x+1 2 2 (4e(log M + ()) Therefore, for & AT/M/(4e" (log M + 1)),
|[V](=)]] = 2e. After combining these two points, we proved the theorem by definition (9).
E
PROOF OF THEOREM 6
We start by parametrizing the function value along the update,
f(r(t)) := f(æ ( E [0, 1].
Note that with this parametrization, we have 7(0) -u. 71) - xx+1 Now we would like to argue that if f*x) & f(o)), then [V(()())) S M,, Vt 1. Assume by contradiction that this is not true. Then there exists 0,t E [0, such that [V((()())
M + Since can be made
arbitrarily small below a threshold, we assume e < M. Denote
t" = =infft [V 2 M c
The value 1* exists by continuity of (xx())] as function of t. Then we know by Assumption that f(x(tt)) f(xx). However, by Taylor expansion, we know that
['' (1V s((7)ll
[(x(1))) s f(xx) - 14 V (2x) +
S [(m)) (4)
+ +)+ Lo)
< f(xx).
The last inequality follows by h= 1 Lo)). Hence we get contradiction and conclude that for all S 1, (V]((() < M. Therefore, following the above inequality and Assumption 3, we get
L + Lo [/(+))1
f(x+11) S [[
2
2
f((x))
4(ML1 + Lo)
The conclusion follows by the same argument as in Theorem 3 via telescopic sum over k.
F PROOF OF THEOREM 7
Recall that we set the following parameters
h2 min
16 (I1gHll ll + +) m
1
min( 20 128L /T
(12)
Similar to proof of Theorem 3, we have
5L0 + 44, -44, Vf
E[f(*++1]] <x(xx) - El vf(xx)))
Eh |x
(13)
2
5 - 4h, [V]((())
<f(zx) Elhu vf(xx))]
[[h(()
2
+ 11gh (f(x)) 11 + 2 (xx). vf(xx)))]
<f(xx) + El 14 5Lo + 4L, fxxx(x))))
2
+ E (5L0 + 4L
V (1aaa v((x)))
5Lo + 44, V ff(xx)) E
(1 - v[(xx)]]
2
15

---

Published as a conference paper at ICLR 2020
First show (6Lu + 4L, (f(ee) I 2. This follows by 5Luhe S 2.ha4Llllf(aaa) hg4 4T, (I|gall +) Σ 4 Substitute in (15) and get
E[f(#++1)l (f(x)) + E|- 3hg |[(x)))
(14)
+ hl (V (2x)) 9h v((2a))]
El + 4L, | / (T (1 - ((xx)))
To
5Lo 441 [ (ara))
T
Then we bound T1, T2, T3 in Lemma 11,12,13 and get
E[f(**+1)l (x(x + + he [+
(15)
4
+ + (5Lv + L
Rearrange and do telescopic sum, we get
h IV s f(xo) f + ( + L1)
s 5((0)) - f + ((5L + 2L (
Furthermore, we know
h& [ min
16 (1 V. + V./kl1
1
m1n
H
32L
V
fill
32L
1
min
V/
32L Vi
Hence along with v) 5 T-1/2, we get
/ 32L,
E
HJ (x0)) 1" ((5 2217) +
AST
Let = (klll 1
full ). we know that 162,
nl fa | & f(x)) - f + ((5L 2[ 1 In);
keU
and
E
S f(20) - + ((5Lo + + Li).
32
kEUt
Therefore,
E K
[xxx)) < E [mmin
| Il.
Σ
|V
U
keu
kEU
< E(minf
1
M
U
kEU
kEUe
VT + 20Lg + 128L
S <max{ f( + ((5L
ff
2 + 9T L1)
T
64L
(f(zo) f" + +(50 2L1T) + 9T LT L1)
T
16

---

Published as a conference paper at ICLR 2020
The last inequality follow by the fact that either [4] 2 T/2 or R29 Emminger
T/2. This implies that
& 2e when
128L1
4A 80L. + 512L17
T A max
e
2²
where A = -f(xx) - + (5L0 2L1T) + L / L1). By Markov inequality,
(min [[+](=))] - c)
KST
2
The theorem follows by the definition in (9).
F.1 TECHNICAL LEMMAS
Lemma 11.
E[
- vf(xa))) - [l/hlll (((z)))
Proof. By unbiasedness of gl and the fact that 7 is constant, we have - Vf(x)))
[((n hx) (V/ (rrx), Ih V [((x)))]]
E[(n hx) (zz),, 9h {xxx))11(le 12
( f((x)) [ Illlall2 1age--7
v/ / 32, [[hx]T
The second last inequality follows by h2 S and follows by
inequality, The last inequality
[(+))l
|l
16 2T
(16)
16I,hg 32L
32L, h4
The equality above holds because hu 1672, (11))1++))* The lemma follows by LTT S 1/4. L
Lemma 12.
-77 + 1 [[nh]II[((E))
E[(LL +
Proof. When [V/(x>)] 2 Lo/Li, + 4L,
The last inequality follows by (12).
When [[](() )ll & Ta/ TT,
+ V (|
11/
Lemma 13.
5Lo + 4L, | [xx)]l
ElA V(((x))]3 < (5Lo + +2117)1²² + 8
V (V(
2
Proof. When [((x))] 2 Lo + we ger
5Lo + 4L, (+ (1gg VS(xx) (0 S 1 [)(<>)]
The first inequality follows by he 17 and ||g v <T [V)(2))) last inequality follows by (12).
When V (zx)) II $ La/ L1 + T, we get
5Lg /|
E
Ehh
- vf(xx)]131 < (5L. + 22
2
17

---

Published as a conference paper at ICLR 2020
G
PROOF OF THEOREM 8
Similar to proof of Theorem 3, we have
[[f(#++)) (f(x)) E(ha (gk, vf(xx))) 5To + 4T, (1<x))
El 11
[[((())) 5Lg + 4h, (MM + +)²
[((xk) VT
27
Sum across & E (O....,T- 1} and take expectations, then we can get
50 + 4I, + +)²
0 (xo) E(f(xT))
[V +
Rearrange and we get
T -ELINS((N)
1
1 S VT
(flo)) f 5Lo + M + T)
2
By Jensen's inequality,
[(zo)) - +++ 5Lo (M + +)2
Σ E=())
VT
By Markov inequality.
Σ [IT
2 (1(0)) 5Lg 4T, ( + t
2
$ 0.5
vT
2
The theorem follows by the definition in (9) and Jensen's inequality.
H EXPERIMENT DETAILS
In this section, we first briefly overview the tasks and models used in our experiment. Then we explain how we estimate smoothness the function. Lastly, we describe some details for generating the plots in Figure and Figure 3.
H.1 LANGUAGE MODELLING
Clipped gradient descent was introduced (vanilla) recurrent neural network (RNN) language model (LM) (Mikolov et al., 2010) training alleviate the exploding gradient problem, and has been used in more sophisticated RNN models (Hochreiter and Schmidhuber, 1997) or seq2seq mod- els for language modelling other NLP applications (Sutskever al., 2014; Cho et al., 2014). In this work we experiment with LSTM LM (Sundermeyer et al., 2012), which has been an important building block for many popular NLP models (Young al., 2017).
The task of language modelling is to model the probability of the next word w based on word history (or context). Given a document length T (words) training data, the training objective is to minimize negative log- ligliiilloood of the data = TT = log P(w, (1).
We LM experiments on the Penn Treebank (PTB) (Mikolov al., 2010) dataset, which has been a popular benchmark for language modelling. It has vocabulary of size 10k, and 887k/70k/78k words for aaaiinng/alidaatooneesnngggg
To train the LSTM LM, we follow the training recipe from 3 (Merity et al., 2018). The model is a 3-layer LSTM LM with hidden size of 1150 and embedding size of 400. Dropout (Srivastava et al., 2014) of rate 0.4 and DropConnect (Wan et al., 2013) of rate 0.5 is applied. For optimization, clipped SGD with clip value of 0.25 and a learning rate of 30 used, and the model is trained for 500 epochs. After training, the model reaches text-set perplexity of 56.5, which is very close to the current state-of-ar art result (Dai et al., 2019) on the PTB dataset.
18

---

Published as a conference paper at ICLR 2020
H.2 IMAGE CLASSIHICATION
As a comparison, we run the same set of experiments on image classification tasks. We train the ResNet20 (He et al., 2016) model Cifar10 (Krizhevsky and Hinton, 2009) classification dataset. The dataset contains 50k training images and 10k testing images in 10 classes
Unless explicitly state, use the standard hyper-parameters based on the Github repository". Our baseline algorithm runs SGD momentum with learning rate 0.1, momentum 0.9 for 200 epochs. We choose weight decay to be - The learning rate is reduced by 10 at epoch 100 and 150. Up to our knowledge, this baseline achieves the best known test accuracy (95.0%) for Resnet20 on Cifar 10. The baseline already beats some recently proposed algorithms which claim improve upon SGD momentum.
1.2
600
0.0
120000
1.0
-0.5
100000
0.8
log[smouthness)
-1.0
400
iteratioo
80000
Iteration
0.6
-1.5
300
60000
-2.0
0.4
200
-2.5
40000
0.2
-3.0
20000
0.0
-3.5
1.00
-2
Gradient norm
log(gradient norm)
(a) Figure 2a plotted on linear scale.
(b) Figure with epochs.
Figure 5: Auxiliary plots for Figure 2a. The left subfigure shows the values scattered on linear scale.
The right subfigure shows more data points from 200 epochs.
Gradient norm (10% data)
Smoothness (10% data)
Gradient
Smoothness
Gradient norm
0.6
0.5
0.4
0.3
0
50
100
150
200
250
300
0
50
100
150
200
250
300
Iterations
Iterationn
(a) Estimation for gradient norm.
(b) Estimation local smoothness.
Figure 6: Estimated gradient norm and smoothness using 10% data versus all data. The values are computed from checkpoints of the LSTM LM model in the first epoch. This shows that statistics evaluated from 10% of the entire dataset provides accurate estimation.
H.3 ESTIMATING SMOOTHNESS
Our smoothness estimator follows similar implementation as in (Santurkar et al., 2018). More pre- cisely, given sequence of iterates generated by training procedure {æx hes we estimate the smooth- ness ((Xx) as follows, For some small value 8 (0, Tx+1 Tk.
[v + yd) vf(x)]
i(xx)
max (6(6,28.....
|/d
(17)
19

---

Published as a conference paper at ICLR 2020
This suggests that we only care about the variation of gradient along 2k+1 zk- The motivation based on the function upper bound (10), which shows that the deviation of the objective from its linear approximation is determined by the variation of gradient between 21+1 and 2g.
H.4 ADDITIONAL PLOTS
The plots in Figure 2a show log- scale scattered data for iterates in the first epoch. To supplement this result, show in Figure 5a the linear scale plot of the same data in Figure 2a. In Figure 5b, we rum the same experiment as in Figure 2a for 200 epochs instead of epoch and plot the gradient norm and estimated smoothness along the trajectory.
In Figure 2, we plot the correlation between gradient norm and smoothness in LSTM LM training. We take snapshots of the model every 5 iterations in the first epoch, and use 10% of training data to estimate gradient norm and smoothness. As shown in Figure 6, using 10% of the data provides a very accurate estimate of the smoothness computed from the entire data.
I A SYNTHETIC EXPERIMENT
In this section, we demonstrate the different behaviors of gradient descent versus clipped gradient descent by optimizing simple polynomial f(x) = x². We initialize the point To 30 and run both algorithms. Within the sublevel set [-30, 30). the function satisfies
(x) - 12 30 1.08 x 10
('(x) S (0)
Therefore, we can either pick L, = 0, Lo 1.08* for gradient descent L1 10.Lo = 0.1 for clipped GD. Since the theoretical analysis is not tight with respect to constants, we scan the step sizes to pick the best parameter for both algorithms. For gradient descent, we scan step size by halving the current steps. For clipped gradient descent, we fix threshold to be 0.01 and pick the step size in the same way. The convergence results are shown in Figure 7, We can conclude that clipped gradient descent converges much faster than vanilla gradient descent, as the theory suggested.
307
10a
0,001000
10
step: 0.001000
10:
Step: 0,001000
0,000500
0.000500
step:
203
step: 0.000250
10
step: 0.000250
step: 0,000250
0.000125
step: 0.000125
102
0,000125
102
300
10a
10-
10
10"2
200
400
600
800
1000
1000
200
400
800
800
1000
iterations
Iterations
(a) Gradient descent |
(b) Gradient descent fx) = x²
(c) Gradient descent ('(x) = 4z
10a
10a
10a
step: 64 000000
step: 000000
20
stap: 64.000000
128, 000000
10a.
stop: 128,000000
stap: 0000000000
10a
step: 32. 0200000
105
step: 32.000000
102
step: 32, 020000000
step:
16,000000
16.000000
10:3
10:4_
10:3
10-2
10
10:4.
10a
200
400
600
800
1000
10:11
400
600
2000
10:4
200
400
600
800
1000
Iterations
Iterations
(d) Clipped GD |æc].
(e) Clipped GD f(z) =
(f) Clipped GD f'(z) = 4x
Figure/ 7: An synthetic experiment to optimize f() = x²_ (a) Gradient descent with different step size. (b) Clipped gradient descent with different step size and threshold 0.01.
J A QUANTITATIVE COMPARISON OF THEOREMS AND EXPERIMENTS
To quantify how much the result align with the theorem, we assume that the leading term in the iteration complexity is the dependent term. For GD, the term scales O M L, ML++ while for
/I
Clipped GD, the term scales as O Lo
20

---

Published as a conference paper at ICLR 2020
First, start with the synthetie experiment presented in From theory, infer that the im- le5. experiment, the best performing GD reaches f(sao) ((())) 0.36, while for clipped GD, the value is 1.3e - 8, and the ratio is [[scad] = 1c7. This suggests that in this very adversarial (against vanilla GD) synthetic experiment, the theorem is correct but conservative.
f(aoo) provement of ('cce))
La
MLi+Lo
Next, test how well the theory align with practice in neural network training. To do so, we rerun the PTB experiment in with smaller architecture (2-Layer LSTM with 200 embedding dimension and 512 inner dimension). We choose hyperparameters based Figure 4a. For clipped GD, we choose clipping threshold to be 0.25 and learning rate to be 10. For GD, we use a learning rate 2. One interesting observation is that, though GD makes steady progress in minimizing function value, its gradient norm is not decreasing.
To quantity the difference between theory and practice, we follow the procedure in the synthetic experiment. First, we estimate ML, + Lo 25 for GD from Figure 8(c). Second, we estimate L1 10, Lg for clipped GD's trajectory from subplot (d). Then the theory predicts that the ratio between gradients should be roughly 25/5 = 5. Empirically, we found the ratio to be = 3 by taking the average (as in Theorem and Theorem 6). This doesn't exactly align but of the same scale. From our view, the main reason for the difference could be the presence of noise in this experiment. As theorems suggested, noise impacts convergence rates but absent in our rough estimates Mi Lo Lo
Glpped Gotn
0.3
train
Gradient norm
cloped
0.2
Loss
0.1
50
100
150
200
0
50
100 Epoch
150
200
Epoch
Gradient descent.
(b) Clipped gradient descent.
40
Smoothness
Smoothness
20
10
0.0
0.2
0.4
0.6
0
2
Gradient Norm
Gradient Norm
(c)
(d)
Figure 8: (a) Gradient norm. (b) Loss curves. (e)The scatter points of smoothness gradient norm for the model trained with gradient (escent.(d))hhe scatter points of smoothness vs gradient norm for the model trained with clipped GD.
21


Reviews:
[{"review_id": "ryx_yx-HtS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors relax the generally used Lipschitz smoothness condition in optimization, to a more general smoothness condition that may depend on norm of the gradient. The authors proved that, with this relaxed condition, under such cases, both GD and clipped GD can converge within O(1/\\epsilon^2) time, but when their exists x where the gradient norm can be very large, the clipped GD will converge provably faster than GD with a proved GD convergence rate lower bound. The authors also generalize their results to SGD. Experiments show that in deep neural network local gradient Lipschitz constant is scale with gradient norm, and use clipped gradient can accelerate convergence while keep good generalization performance as expected, which is well observed by other researchers.\n\nDetailed comments:\n1. The f^* In theorem 3 is not defined. I think it’s not the f^* in Assumption 1? Should be more clear. Also, in non-convex optimization, can the deterministic GD find the global optimum? If f^* is the stationary point the algorithm find, then the Assumption 1 is a little weird. The authors should better clarify this.\n2. Feel the claim of the Assumption can be relaxed to only hold on \\mathcal{S} is a little confusing. Which Assumption can be relaxed? It seems that in the proof of Lemma 9, we need the Assumption 3 holds for the set \\|x^+-x\\| \\leq min{1/L_1, 1}. I think maybe the other Assumption will also be needed globally, unless the authors can prove that the optimization is only on a compact set in S.\n3. Maybe a discussion connected the existing Lipschitz constant based results to the new results in this paper can make the readers more aware of the contribution in this paper. For example, the Lipschitz constant of neural network can be of order O(L_1 M) due to the definition, so if L_1 M is large, for clipped GD we can still have expected decreasing of O(1/L_0) each turn while vanilla GD with the best O(1/L) step size can still only have O(1/L) where L = L_0 + L_1 M due to the traditional results based on Lipschitz smoothness.\n\nI don’t totally go through the whole proof, but I think the results are reasonable and the most of the techniques are standard to the whole community. So there may be no fatal error that violates the conclusion. I find the whole paper interesting and match the intuition from the practice. However, I think it can be polished to make the whole idea more clear and more easy to accept by the potential theorists and practitioner audience.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rylSdgmeqB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper applies new assumption on smoothness that assume the norm of Hessian is bounded by a scalar plus norm of gradient. The traditional smoothness is only bounded with a scalar, the proposed assumption is more relaxed because now the norm of Hessian can grow with the norm of gradient. Under this assumption, the authors show clipped gradient converges faster than gradient for general nonconvex problems. The authors provide insights on why the proposed assumption is good for describing neural networks, and empirically verify the assumption with ResNet on CIFAR and LSTM on PTB. \n\nI like the paper in general. It is well written and easy to follow. The contributions are clearly described and the techniques seem to be solid. \n\nI want a little bit more discussion to help me better understand the paper. \n\n1) Intuitively, try best in plain English, why does clipped gradient convergence does not have dependency on L_1 M? Could the authors provide more discussion on the learning rate (hyperparameters) used for clipped gradient and gradient?\n\n2) The convergence rates under the proposed assumption are slower than traditional smoothness assumption. Could you verify the slow convergence rate under proposed assumption aligns better with practical training? Could you provide a toy example, for example x^3, to show the advantage of the proposed assumption and the convergence under the assumption? What is the gap between clipped gradient and gradient, for experiments in figure 4, and possible toy problem? Could the authors elaborate the difference of clipped gradient and gradient with the details of theory, instead of simply claiming clipped gradient is faster?\n\nTypo, page 5, (0, L) -> (L, 0)\n\n\n============ after rebuttal ===================\nI am happy to see the paper in the conference. The paper is intuitive and well written. My remaining comments are still on the slower convergence rate comparing to previous assumption. Even before, researchers suggest overparameterized network can converge faster than expected. This paper suggests a generally slower convergence rate if the proposed assumption does fit practice better.   \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rkxmDNtEYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors provide the definition of a (L_0, L_1)-smooth function.\nThey motivate this class of function based on theoretical arguments and\nempirical observations in the context of neural network training loss.\nThe authors go on to show that for (L_0, L_1)-smooth loss constant\nstep-size gradient descent can perform arbitrarily bad with poor initialization.\nSpecifically, the largest constant step size that can be used without divergence\ndepends on the upper bound of the gradient norm.\nIf the function is steep (high gradient norm) at some point during the\noptimization process the steps need to become arbitrarily small\n(especially relevant in nonconvex loss, where gradient norm does not always decrease).\nThe small constant step size slows down convergence everywhere else.\nThe described phenomenon is an argument for step sizes adaptivity in general\nClipping the gradient based on the known (L_0, L_1)-smoothness is a form of\nadaptivity that makes steps small enough to avoid divergence only where the\nfunction is steep and can thus be more efficient.\n\nOverall, the authors give a theoretical justification for the use of clipped\ngradient descent in the context of training neural networks.\nThe analysis of clipped gradient descent is performed rigorously (proofs are\nprovided in the appendix) and extended to the stochastic gradient descent setting.\nThe motivation for using (L_0, L_1)-smoothness and gradient clipping is also\nshown to be relevant in practical experiments with language and image\nclassification models.\n\nI recommend to accept the paper.\n\nThe paper is a clearly stated contribution to optimization theory as motivated\nby machine learning applications.\nThe authors give a clean theoretical analysis of a previously empirically\nobserved phenomenon and an algorithm that is already used in practice.\n\nNotes:\n- Page 1, first paragraph:\nIf f(x) = E_xi [f(x, xi)] then f(x) the expectation is generally not stochastic,\nlike you write before. It is clear what you mean but Maybe use a different symbol.\n\n- Page 2, ...we observe the function smoothness has a strong correlation with gradient norm 2:\nPerhaps write something like \"(see Figure 2)\" instead of just \"2\" here.\n\n- Page 2, after definition of Lipschitz continuous:\nNitpick: Formal definition based on Hessian norm upper bound should also have, for all x \\in \\mathbb R^d\n\n- General: Some equations that are not referenced seem to be numbered, some are not.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Gradient clipping is increasingly popular and it's nice to see a paper theoretically exploring its nice performance. All reviewers appreciated the work and the results.

Please make sure to incorporate all of their comments for the final version.
Decision: Accept (Talk)