A THEORETICAL JUSTIFICATION FOR ADAPTIVITY
Year: 2020

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.

heading: 1 INTRODUCTION
text: 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 : Rd → R, where f(x) can potentially be stochastic, i.e., f(x) = Eξ[F (x, ξ)]. Such choices of f cover a 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 theoretical (Carmon et al., 2017) guarantees. However, in many tasks such as reinforcement learning and natural language processing (NLP), adaptive gradient methods (e.g., Adagrad (Duchi et al., 2011), 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 hyper-parameters (Ward et al., 2018) and adapt to sparse gradients (Duchi et al., 2011) (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 in NLP tasks.
We analyze the convergence of clipped gradient descent and provide an explanation for its fast convergence. Even though gradient clipping is a standard practice in 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 in recurrent 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 a novel smoothness condition that is strictly weaker than the standard Lipschitzgradient assumption pervasive in the literature. Hence our analysis captures many functions that are not globally Lipschitz smooth. Importantly, the proposed smoothness condition is derived on the
basis of extensive NLP training experiments, which are precisely the same type of experiments for which adaptive gradient methods empirically perform superior to gradient methods.
By identifying a a new smoothness condition through experiments and then using it to analyze the convergence of adaptively-scaled methods, we reduce the following gap between theory and practice. On one hand, powerful techniques such as 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 guarantees. 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-gradient condition may not hold in the case of some applications and thus must be relaxed to admit a wider class of objective functions.

heading: 1.1 CONTRIBUTIONS
text: In light of the above background, the main contributions of this paper are the following:
Inspired and supported by neural network training experiments, we introduce a new smoothness condition that allows the local smoothness constant to increase with the gradient norm. This condition is strictly weaker than the pervasive Lipschitz-gradient assumption.
We provide a convergence rate for clipped GD under our smoothness assumption (Theorem 3). We prove an upper-bound (Theorem 6) and a lower-bound (Theorem 4) on the convergence rate of GD under our relaxed smoothness assumption. The lower-bound demonstrates that GD with fixed step size can 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 a 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 Cifar10). Please see Section 5 for more details.

heading: 2 A NEW RELAXED SMOOTHNESS CONDITION
text: In this section, we 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.

heading: 2.1 FUNCTION SMOOTHNESS (LIPSCHITZ GRADIENTS)
text: Recall that f denotes the objective function that we want to minimize. We say that f is L-smooth if
‖∇f(x)−∇f(y)‖ ≤ L‖x− y‖, for all x, y ∈ Rd. (1)
For twice differentiable functions, condition (1) is equivalent to ‖∇2f(x)‖ ≤ L,∀x ∈ Rd. This smoothness condition enables many important theoretical results. For example, Carmon et al. (2017) show that GD with h = 1/L is 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 L that upper bounds the variation of the gradient is very restrictive. For example, simple polynomials such as f(x) = x3 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 projectionbased 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.
The above limitations force fixed-step gradient descent (which is tailored for Lipschitz smooth functions) to converge slowly in many tasks. In Figure 1, 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-grained smoothness condition under which we can design theoretically and empirically fast algorithms at the same time?
To answer this question, we introduce the relaxed smoothness condition in the next section, which is developed on the basis of extensive experiments— Figure 1 provides an illustrative example.

heading: 2.2 A NEW RELAXED SMOOTHNESS CONDITION
text: We observe strong positive correlation between function smoothness and gradient norm in language modeling experiments (Figure 1(a)). This observation leads us to propose the following smoothness condition that allows local smoothness to grow with function gradients.
Definition 1. A second order differentiable function f is (L0, L1)-smooth if
‖∇2f(x)‖ ≤ L0 + L1‖∇f(x)‖. (2)
Definition 1 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 L0 and L1 such that L0 L while L1 L. Second, there exist functions that are (L0, L1)-smooth globally, but not L-smooth. Hence the constant L for L-smoothness gets larger as the compact set increases but L0 and L1 stay fixed. An example is given in Lemma 2.
Remark 1. It is worth noting that we 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 to achieve faster rate than fixed step size gradient descent. We use the linear relationship (2) for simplicity of exposition.
Lemma 2. Let f be the univariate polynomial f(x) = ∑d i=1 aix
i. When d ≥ 3, then f is (L0, L1)smooth for some L0 and L1 but not L-smooth. Proof. The first claim follows from limx→∞ ∣∣∣ f ′(x)f ′′(x) ∣∣∣ = limx→−∞ ∣∣∣ f ′(x)f ′′(x) ∣∣∣ =∞. The second claim follows by the unboundedness of f ′′(x).

heading: 2.3 SMOOTHNESS IN NEURAL NETWORKS
text: We saw that our smoothness condition relaxes the traditional smoothness assumption and is motivated 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 `- layer linear network with quadratic loss—a similar computation also holds for nonlinear networks.
The L2 regression loss of a deep linear network is L(Y, f(X)) := ‖Y − W` · · ·W1X‖2, where Y denotes labels, X denotes the input data matrix, and Wi denotes the weights in the ith layer. By (Lemma 4.3 Kawaguchi, 2016), we know that
∇vec(wi)L(Y, f(X)) = ((W` · · ·Wi+1)⊗ (Wi−1 · · ·W2W1X) T )T vec(f(X)− Y ),
where vec(·) flattens a matrix in Rm×n into a vector in Rmn; ⊗ denotes the Kronecker product. For constants i, j such that ` ≥ j > i > 0, the second order derivative ∇vec(wj)∇vec(wi)L(Y, f(X)) =
((W` · · ·Wi+1)⊗ (Wi−1 · · ·W2W1X)T )T ((W` · · ·Wj+1)⊗ (Wj−1 · · ·W2W1X)T )+ ((Wj−1 · · ·Wi+1)⊗ (Wi−1 · · ·W2W1X))(I ⊗ ((f(X)− Y )W` · · ·Wj+1)).
When j = i, the second term equals 0. Based on the above expressions, we notice that the gradient norm and Hessian norm may be positively correlated due to the following two observations. First, the gradient and the Hessian share many components such as the matrix product of weights across layers. Second, if one naively upper bounds the norm using Cauchy-Schwarz, then both upperbounds would be monotonically increasing with respect to ‖Wi‖ and ‖f(X)− Y ‖.

heading: 3 PROBLEMS SETUP AND ALGORITHMS
text: In this section, we 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 we wish to solve the nonconvex optimization problem minx∈Rd f(x). Since in general this problem is intractable, following common practice we also seek an -stationary point, i.e., a point x such that ‖∇f(x)‖ ≤ . Furthermore, we make the following assumptions to regularize the function class studied and subsequently provide nonasymptotic convergence rate analysis. Assumption 1. The function f is lower bounded by f∗ > −∞. Assumption 2. The function f is twice differentiable. Assumption 3 ((L0, L1)-smoothness). The function f is (L0, L1)-smooth, i.e., there exist positive constants L0 and L1 such that ‖∇2f(x)‖ ≤ L0 + L1‖∇f(x)‖—see condition (2).
The first assumption is standard. Twice differentiability in Assumption 2 can relaxed to first-order differentiability by modifying the definition of (L0, L1)-smoothness as
lim sup δ→~0
‖∇f(x)−∇f(x+δ)‖ ‖δ‖ ≤ L1‖∇f(x)‖+ L0.
The above inequality implies ∇f(x) is locally Lipschitz, and hence almost everywhere differentiable. 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, we require the above assumptions to hold just in a neighborhood determined by the sublevel set S1 for a given initialization x0, where
S := {x | ∃ y such that f(y) ≤ f(x0), and ‖x− y‖ ≤ 1}. (3)

heading: 3.1 GRADIENT DESCENT ALGORITHMS
text: In this section, we review a few well-known variants of gradient based algorithms that we analyze. We start with the ordinary gradient descent with a fixed step size η,
xk+1 = xk − η∇f(xk). (4) This algorithm (pedantically, its stochastic version) is widely used in neural network training. Many modifications of it have been proposed to stabilize or accelerate training. One such technique of particular importance is clipped gradient descent, which performs the following updates:
xk+1 = xk − hc∇f(xk), where hc := min{ηc, γηc‖∇f(x)‖}. (5)
1The constant “1” in the expression (3) is arbitrary and can be replaced by any fixed positive constant.
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
xk+1 = xk − hn∇f(xk), where hn := ηn‖∇f(x)‖+β . (6)
The stochastic version of the above algorithms replace the gradient with a stochastic estimator.
We note that Clipped GD and NGD are almost equivalent. Indeed, for any given ηn and β, if we set γηc = ηn and ηc = ηn/β, then we have
1 2hc ≤ hn ≤ 2hc.
Therefore, clipped GD is equivalent to NGD up to a constant factor in the step size choice. Consequently, 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.

heading: 4 THEORETICAL ANALYSIS
text: In this section, we analyze the oracle complexities of GD and clipped GD under our relaxed smoothness condition. All the proofs are in the appendix. We highlight the key theoretical challenges that needed to overcome in Appendix B (e.g., due to absence of Lipschitz-smoothness, already the firststep 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 a deterministic sequence {xk}k∈N, define the complexity of {xk}k∈N for a function f as
T ({xt}t∈N, f) := inf{t ∈ N|‖∇f(xt)‖ ≤ }. (7)
For a random process {xk}k∈N, we define the complexity of {xk}k∈N for function f as T ({xt}t∈N, f) := inf { t ∈ N|Prob(‖∇f(xk)‖ ≥ for all k ≤ t) ≤ 12 } . (8)
In particular, if the condition is never satisfied, then the complexity is∞. Given an algorithm Aθ, where θ denotes hyperparameters such as step size and momentum coefficient, we denote Aθ[f, x0] as the sequence of (potentially stochastic) iterates generated by A when operating on f with initialization x0. Finally, we define the iteration complexity of an algorithm class parameterized by p hyperparameters, A = {Aθ}θ∈Rp on a function class F as
N (A,F , ) := inf Aθ∈A sup x0∈Rd,f∈F T (Aθ[f, x0], f). (9)
The definition in the stochastic setting simply replaces the expression (7) with the expression (8). In the rest of the paper, “iteration complexity” refers to the quantity defined above.

heading: 4.1 CONVERGENCE IN THE DETERMINISTIC SETTING
text: In this section, we 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). Theorem 3. Let F denote the class of functions that satisfy Assumptions 1, 2, and 3 in set S defined in (3). Recall f∗ is a global lower bound for function value. With ηc = 110L0 , γ = min{ 1 ηc , 110L1ηc }, we can prove that the iteration complexity of clipped GD (Algorithm 5) is upper bounded by
20L0(f(x0)− f∗) 2 + 20 max{1, L21}(f(x0)− f∗)
L0 .
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 -stationary points in O((L(f(x0) − f∗)) −2) iterations for (L, 0)−smooth nonconvex functions. By Theorem 1 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 (L0, L1)smoothness condition. In particular, to prove the convergence rate for gradient descent with fixed step size, we need to permit it benefit from an additional assumption on gradient norms.
Assumption 4. Given an initialization x0, we assume that M := sup{‖∇f(x)‖ | x such that f(x) ≤ f(x0)} <∞.
This assumption is in fact necessary, as our next theorem reveals.
Theorem 4. Let F be the class of objectives satisfying Assumptions 1, 2, 3, and 4 with fixed constants L0 ≥ 1, L1 ≥ 1, M > 1. The iteration complexity for the fixed-step gradient descent algorithms parameterized by step size h is at least
L1M(f(x0)− f∗ − 5 /8) 8 2(logM + 1) .
The proof can be found in Appendix D. Remark 5. Theorem 1 of Carmon et al. (2017) and Theorem 4 together show that gradient descent with a fixed step size cannot converge to an -stationary point faster than Ω ( (L1M/ log(M) + L0)(f(x0)− f∗) −2 ) . Recall that clipped GD algorithm converges as
O ( L0(f(x0)− f∗) −2 + L21(f(x0)− f∗)L−10 ) . Therefore, clipped GD can be arbitrarily faster than GD when L1M is large, or in other words, when the problem has a poor initialization.
Below, we provide an iteration upper bound for the fixed-step gradient descent update (4). Theorem 6. Suppose assumptions 1, 2, 3 and 4 hold in set S defined in (3). If we pick parameters such that h = 1(2(ML1+L0)) , then we can prove that the iteration complexity of GD with a fixed step size defined in Algorithm 4 is upper bounded by
4(ML1 + L0)(f(x0)− f∗) −2.
Please refer to Appendix E for the proof. Theorem 6 shows that gradient descent with a fixed step size converges in O((ML1 + L0)(f(x0) − f∗)/ 2) iterations. This suggests that the lower bound in Remark 5 is tight up to a log factor in M .

heading: 4.2 CONVERGENCE IN THE STOCHASTIC SETTING
text: In the stochastic setting, we assume GD and clipped GD have access to an unbiased stochastic gradient ∇f̂(x) instead of the exact gradient ∇f(x). For simplicity, we denote gk = ∇f̂(xk) below. To prove convergence, we need the following assumption.
Assumption 5. There exists τ > 0, such that ‖∇f̂(x)−∇f(x)‖ ≤ τ almost surely.
Bounded noise can be relaxed to sub-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 ‖∇f(x)‖ 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 L1 > 0. Let h = min { 1 16ηL1(‖gk‖+τ) , η } where η = min { 1 20L0 , 1128L1τ , 1√ T } . Then we can show that iteration complexity for stochastic clipped GD after of update (5) is upper bounded by
∆ max{128L1 , 4∆
4 ,
80L0 + 512L1τ
2 },
where ∆ = (f(x0)− f∗ + (5L0 + 2L1τ)τ2 + 9τL20/L1).
In comparison, we have the following upper bound for ordinary SGD. Theorem 8. Let Assumptions 1–3, and 5 hold globally with L1 > 0. Let h = min { 1√ T , 1L1(M+τ) } .
Then the iteration complexity for the stochastic version of GD (4) is upper bounded by( f(x0)− f∗ + (5L0 + 4L1M)(M + τ)2 )2 −4.
We cannot provide a lower bound for this algorithm. In fact, lower bound is not known for SGD even in 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 to clipped SGD when M is large.

heading: 5 EXPERIMENTS
text: 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 classification. We run language modeling on 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 Cifar10 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 at points generated by the optimization procedure. We then scatter the local smoothness constants against the gradient norms in Figure 2 and Figure 3. Note that the plots are on a log-scale. A linear scale plot is shown in Appendix Figure 5.
We notice that the correlation exists in the default training procedure for language modeling (see Figure 2a) but not in 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 following 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 to adopt a small learning rate and stays in a region where local smoothness does not vary much, otherwise the sequence diverges, and a different learning rate is used. Therefore, in 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 convergence as predicted by our theory. From Figure 4, we find that clipping indeed accelerates convergence. Because gradient clipping is a standard practice in language modeling, the LSTM models trained with clipping achieve the best validation performance and the fastest training loss conver-
2Part of the code is available at https://github.com/JingzhaoZhang/ why-clipping-accelerates
gence as expected. For image classification, surprisingly, clipped GD also achieves the fastest convergence and matches the test performance of SGD+momentum. These plots show that clipping can accelerate convergence and achieve good test performance at the same time.

heading: 6 DISCUSSION
text: Much progress has been made to close the gap between upper and lower oracle complexities for first order smooth optimization. The works dedicated to 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 a relaxed smoothness assumption that is supported by empirical evidence. We analyze a 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, it is unclear if there is an even better condition that also matches the experimental observations while also enabling a clean theoretical analysis. Second, we only study convergence of clipped gradient descent. Studying the convergence properties of other techniques such as momentum, coordinate-wise learning rates (more generally, preconditioning), and variance reduction is also interesting. Finally, the most important question is: “can we design fast algorithms based on relaxed conditions that achieve faster convergence in neural network training?”
Our experiments also have noteworthy implications. First, though advocating clipped gradient descent in ResNet training is not a main point of this work, it is interesting to note that gradient
descent and clipped gradient descent with large step sizes can achieve a similar test performance as momentum-SGD. Second, we learned that the performance of the baseline algorithm can actually beat some recently proposed algorithms. Therefore, when we design or learn about new algorithms, we need to pay extra attention to check whether the baseline algorithms are properly tuned.

heading: 7 ACKNOWLEDGEMENT
text: SS acknowledges support from an NSF-CAREER Award (Number 1846088) and an Amazon Research Award. AJ acknowledges support from an MIT-IBM-Exploratory project on adaptive, robust, and collaborative optimization.

heading: A MORE RELATED WORK ON ACCELERATING GRADIENT METHODS
text: Variance reduction. Many efforts have been made to accelerate 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; Konečnỳ and Richtárik, 2013; Xiao and Zhang, 2014; Gong and Ye, 2014; Fang et al., 2018; Zhou et 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 a variation that provably accelerate any smooth convex problems. Based on Nesterov’s work, much theoretical progress was made to 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 et 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. (2011) designed the Adagrad algorithm that can utilize the sparsity in stochastic gradients.
Since 2018, there has been a surge in studying the theoretical properties of adaptive gradient methods. One starting point is (Reddi et al., 2019), which pointed out that ADAM is not convergent and proposed the AMSGrad algorithm to fix the problem. Ward et al. (2018); Li and Orabona (2018) 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 et 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 setting. Hazan et al. (2015) studied the convergence of normalized gradient descent for quasi-convex functions.

heading: B CHALLENGES IN THE PROOFS
text: In this section, we highlight a few key challenges in our proofs. First, the analysis convergence under the relaxed smoothness condition is more difficult than the traditional setup. In particular, classical analyses based on Lipschitz-smooth gradients frequently exploit the descent condition:
f(y) ≤ f(x) + 〈∇f(x), y − x〉+ L2 ‖y − x‖ 2. (10)
However, under our relaxed smoothness condition, the last term will increase exponentially in ‖y − x‖2. To solve this challenge, we bound the distance moved by clipping and apply Grönwall’s inequality.
Second, our algorithm specific lower bound proved in Theorem 4 is novel and tight up to a 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 is usually circumvented by either assuming gradients have bounded norms or by using a lagging-byone step-size to decouple the correlation. The situation is even worse under the relaxed smoothness assumption. In our case, we overcome this challenge by a novel analysis that divides the proof into the large gradient scenario and the small gradient scenario.

heading: C PROOF OF THEOREM 3
text: We start by proving a lemma that is repeatedly used in later proofs. The lemma bounds the gradient in a neighborhood of the current point by Grönwall’s inequality (integral form).
Lemma 9. Given x such that f(x) ≤ f(x0), for any x+ such that ‖x+ − x‖ ≤ min{1/L1, 1}, we have ‖∇f(x+)‖ ≤ 4(L0/L1 + ‖∇f(x)‖). Remark 10. Note that the constant “1” comes from the definition of S in (3). If Assumption 3 holds globally, then we do not need to constrain ‖x+ − x‖ ≤ 1. This version will be used in Theorem 7.
Proof. Let γ(t) be a curve defined below,
γ(t) = t(x+ − x) + x, t ∈ [0, 1].
Then we have
∇f(γ(t)) = ∫ t 0 ∇(2)f(γ(τ))(x+ − x)dτ +∇f(γ(0)).
By Cauchy-Schwarz’s inequality, we get ‖∇f(γ(t))‖ ≤ ‖x+ − x‖ ∫ t 0 ‖∇(2)f(γ(τ))‖dτ + ‖∇f(x)‖
≤ 1 L1 ∫ t 0 (L0 + L1‖∇f(γ(τ))‖)dτ + ‖∇f(x)‖.
The second inequality follows by Assumption 3. Then we can apply the integral form of Grönwall’s inequality and get
‖∇f(γ(t))‖ ≤ L0 L1 + ‖∇f(x)‖+ ∫ t 0 ( L0 L1 + ‖∇f(x)‖ ) exp(t− τ)dτ.
The Lemma follows by setting t = 1.
C.1 PROOF OF THE THEOREM
We parameterize the path between xk and its updated iterate xk+1 as follows:
γ(t) = t(xk+1 − xk) + xk,∀t ∈ [0, 1].
Since xk+1 = xk−hk∇f(xk), using Taylor’s theorem, the triangle inequality, and Cauchy-Schwarz, we obtain
f(xk+1) ≤ f(xk)− hk‖∇f(xk)‖2 + ‖xk+1 − xk‖2
2
∫ 1 0 ‖∇2f(γ(t))‖dt.
Since
hk ≤ γη
‖∇f(x)‖ ≤ min
{ 1
‖∇f(x)‖ ,
1
L1‖∇f(xk)‖
} ,
we know by Lemma 9
‖∇f(γ(t)‖ ≤ 4(L0L1 + ‖∇f(x)‖).
Then by Assumption 3, we obtain the “descent inequality”:
f(xk+1) ≤ f(xk)− hk‖∇f(xk)‖2 + 5L0 + 4L1‖∇f(xk)‖
2 ‖∇f(xk)‖2h2k.
Therefore, as long as hk ≤ 1/(5L0 + 4L1‖∇f(xk)‖) (which follows by our choice of η, γ), we can quantify the descent to be
f(xk+1) ≤ f(xk)− hk‖∇f(xk)‖2
2 .
When ‖∇f(xk)‖ ≥ L0/L1, we have
hk‖∇f(xk)‖2
2 ≥ L0 20 max{1, L21} .
When ≤ ‖∇f(xk)‖ ≤ L0/L1, we have hk‖∇f(xk)‖2
2 ≥ ‖∇f(xk)‖ 2 20L0 ≥ 2 20L0 .
Therefore,
f(xk+1) ≤ f(xk)−min {
L0 20 max{1, L21} , 2 20L0
} .
Assume that ≤ ‖∇f(xk)‖ for k ≤ T iterations. By doing a telescopic sum, we get T−1∑ k=0 f(xk+1)− f(xk) ≤ −T min { L0 20 max{1, L21} , 2 20L0 } .
Rearranging we get
T ≤ 20L0(f(x0)− f ∗)
2 + 20 max{1, L21}(f(x0)− f∗) L0 .

heading: D PROOF OF THEOREM 4
text: We will prove a lower bound for the iteration complexity of GD with fixed step size. The high level idea is that if GD converges for all functions satisfying the assumptions, then the step size needs to be small. However, this small step size will lead to very slow convergence for another function.
Recall that the fixed step size GD algorithm is parameterized by the scaler: step size h. First, we show that when h > 2 log(M)+2ML1 ,
sup x0∈Rd, f∈F
T (Ah[f, x0], f) =∞
We start with a function that grows exponentially. Let L1 > 1,M > 1 be fixed constants. Pick the initial point x0 = (log(M) + 1)/L1. Let the objective be defined as follows,
f(x) =  e−L1x L1e , for x < − 1L1 , L1x 2 2 + 1 2L1 , for x ∈ [− 1L1 , 1 L1 ],
eL1x L1e , for x > 1L1 .
We notice that the function satisfies the assumptions with constants
L0 = 1, L1 > 1, M > 1. (11)
When h > 2x0/M , we would have |x1| > |x0|. By symmetry of the function and the super-linear growth of the gradient norm, we know that the iterates will diverge. Hence, in order for gradient descent with a fixed step size h to converge, h must be small enough. Formally,
h ≤ 2x0 M = 2 log(M) + 2 ML1 .
Second, we show that when h ≤ 2 log(M)+2ML1 ,
sup x0∈Rd, f∈F
T (Ah[f, x0], f) ≥ ∆L1M/(4 2(logM + 1))
Now, let’s look at a different objective that grows slowly.
f(x) =  −2 (x+ 1) + 5 4 , for x < −1, 4 (6x
2 − x4), for x ∈ [−1, 1], 2 (x− 1) + 5 4 , for x > 1.
This function is also second order differentiable and satisfies the assumptions with constants in (11). If we set x0 = 1 + ∆/ for some constant ∆ > 0, we know that f(x0)− f∗ = 2∆ + 5 /4. With the step size choice h ≤ (2 logM + 2)/(ML1), we know that in each step, xk+1 ≥ xk − (4 (logM + 1))/(L1M). Therefore, for k ≤ ∆L1M/(4 2(logM + 1)),
‖∇f(xk)‖ = 2 . After combining these two points, we proved the theorem by definition (9).

heading: E PROOF OF THEOREM 6
text: We start by parametrizing the function value along the update,
f(γ(t)) := f(xk − th∇f(xk)), t ∈ [0, 1]. Note that with this parametrization, we have γ(0) = xk, γ(1) = xk+1. Now we would like to argue that if f(xk) ≤ f(x0), then ‖∇f(x(t))‖ ≤ M,∀t ≤ 1. Assume by contradiction that this is not true. Then there exists > 0, t ∈ [0, 1] such that ‖∇f(x(t))‖ ≥ M + . Since can be made arbitrarily small below a threshold, we assume < M . Denote
t∗ = inf{t | ‖∇f(x(t))‖ ≥M + }. The value t∗ exists by continuity of ‖∇f(x(t))‖ as a function of t. Then we know by Assumption 4 that f(x(t∗)) > f(xk). However, by Taylor expansion, we know that
f(x(t∗)) ≤ f(xk)− th‖∇f(xk)‖2 + (th)2‖∇f(xk)‖2 ∫ t 0 ‖∇(2)f(x(τ))‖dτ
≤ f(xk)− th‖∇f(xk)‖2 + (th)2‖∇f(xk)‖2(L1(M + ) + L0) ≤ f(xk).
The last inequality follows by h = 1/(2(ML1 + L0)). Hence we get a contradiction and conclude that for all t ≤ 1, ‖∇f(x(t))‖ ≤ M . Therefore, following the above inequality and Assumption 3, we get
f(xk+1) ≤ f(xk)− h‖∇f(xk)‖2 + h2 L1M + L0
2 ‖∇f(xk)‖2
≤ f(xk)− 2
4(ML1 + L0) .
The conclusion follows by the same argument as in Theorem 3 via a telescopic sum over k.

heading: F PROOF OF THEOREM 7
text: Recall that we set the following parameters
hk = min{ 1
16ηL1(‖gk‖+ τ) , η}
η = min{ 1 20L0 , 1 128L1τ , 1√ T } (12)
Similar to proof of Theorem 3, we have
E[f(xk+1)|] ≤f(xk)− E[hk〈gk,∇f(xk)〉] + 5L0 + 4L1‖∇f(xk)‖
2 E[h2k‖gk‖2] (13)
≤f(xk)− E[hk〈gk,∇f(xk)〉] + 5L0 + 4L1‖∇f(xk)‖
2 E[h2k(‖∇f(xk)‖2
+ ‖gk −∇f(xk)‖2 + 2〈∇f(xk), gk −∇f(xk)〉)]
≤f(xk) + E[−hk + 5L0 + 4L1‖∇f(xk)‖
2 h2k]‖∇f(xk)‖2
+ E[hk(−1 + (5L0 + 4L1‖∇f(xk)‖)hk)〈∇f(xk), gk −∇f(xk)〉]
+ 5L0 + 4L1‖∇f(xk)‖
2 E[h2k(‖gk −∇f(xk)‖2)]
First we show (5L0 + 4L1‖∇f(xk)‖)hk ≤ 12 . This follows by 5L0hk ≤ 1 4 , hk4L1‖∇f(xk)‖ ≤ hk4L1(‖gk‖+ τ) ≤ 14 . Substitute in (15) and we get
E[f(xk+1)|] ≤f(xk) + E[− 3hk 4 ]‖∇f(xk)‖2 (14)
+ E[−hk〈∇f(xk), gk −∇f(xk)〉]︸ ︷︷ ︸ T1 + E[(5L0 + 4L1‖∇f(xk)‖)h2k〈∇f(xk), gk −∇f(xk)〉]︸ ︷︷ ︸ T2
+ 5L0 + 4L1‖∇f(xk)‖
2 E[h2k(‖gk −∇f(xk)‖2)]︸ ︷︷ ︸ T3
Then we bound T1, T2, T3 in Lemma 11,12,13 and get
E[f(xk+1)|] ≤f(xk) + E[− hk 4 ]‖∇f(xk)‖2 (15)
+ (5L0 + 2L1τ)η 2τ2 + 9η2τL20/L1
Rearrange and do a telescopic sum, we get E[ ∑ k≤T hk 4 ‖∇f(xk)‖2] ≤ f(x0)− f∗ + η2T ((5L0 + 2L1τ)τ2 + 9τL20/L1)
≤ f(x0)− f∗ + ((5L0 + 2L1τ)τ2 + 9τL20/L1)
Furthermore, we know
hk‖∇fk‖2 = min{η, 1
16L1(‖∇fk‖+ τ) }‖∇fk‖2
≥ min{η, 1 32L1‖∇fk‖ , 1 32L1τ }‖∇fk‖2
≥ min{η, 1 32L1‖∇fk‖ }‖∇fk‖2
Hence along with η ≤ T−1/2, we get E[ ∑ k≤T min{η‖∇fk‖2, ‖∇fk‖ 32L1 }] ≤ f(x0)− f∗ + ((5L0 + 2L1τ)τ2 + 9τL20/L1)
Let U = {k|η‖∇fk‖2 ≤ ‖∇fk‖16L1 }, we know that E[ ∑ k∈U η‖∇fk‖2] ≤ f(x0)− f∗ + ((5L0 + 2L1τ)τ2 + 9τL20/L1),
and
E[ ∑ k∈Uc ‖∇fk‖ 32L1 ] ≤ f(x0)− f∗ + ((5L0 + 2L1τ)τ2 + 9τL20/L1).
Therefore,
E[min k ‖∇f(xk)‖] ≤ E[min{
1 |U| ∑ k∈U ‖∇fk‖], 1 |Uc| ∑ k∈Uc ‖∇fk‖}]
≤ E[min{ √ 1 |U| ∑ k∈U ‖∇fk‖2, 1 |Uc| ∑ k∈Uc ‖∇fk‖}]
≤ max{ √ f(x0)− f∗ + ((5L0 + 2L1τ)τ2 + 9τL20/L1) √ T + 20L0 + 128L1τ
T ,
(f(x0)− f∗ + (5L0 + 2L1τ)τ2 + 9τL20/L1) 64L1 T }.
The last inequality follow by the fact that either |U| ≥ T/2 or |Uc| ≥ T/2. This implies that E[mink≤T ‖∇f(xk)‖] ≤ 2 when
T ≥ ∆ max{128L1 , 4∆
4 ,
80L0 + 512L1τ
2 },
where ∆ = (f(x0)− f∗ + (5L0 + 2L1τ)τ2 + 9τL20/L1). By Markov inequality,
P{min k≤T ‖∇f(xk)‖ ≤ } ≥
1 2 .
The theorem follows by the definition in (9).
F.1 TECHNICAL LEMMAS
Lemma 11. E[−hk〈∇f(xk), gk −∇f(xk)〉] ≤ 1
4 E[hk]‖∇f(xk)‖2.
Proof. By unbiasedness of gk and the fact that η is a constant, we have E[−hk〈∇f(xk), gk −∇f(xk)〉] = E[(η − hk)〈∇f(xk), gk −∇f(xk)〉]
= E[(η − hk)〈∇f(xk), gk −∇f(xk)〉1{‖gk‖≥ 116L1η−τ}] ≤ η‖∇f(xk)‖E[‖gk −∇f(xk)‖1{‖gk‖≥ 116L1η−τ}]
≤ η‖∇f(xk)‖232L1E[hk]τ The second last inequality follows by hk ≤ η and Cauchy-Schwartz inequality. The last inequality follows by
‖∇f(xk)‖ ≥ ‖gk‖ − τ = 1 16L1hk − 2τ ≥ 1 16L1hk − 1 32L1η ≥ 1 32L1hk . (16)
The equality above holds because hk = 116ηL1(‖gk‖+τ) . The lemma follows by 32ηL1τ ≤ 1/4.
Lemma 12.
E[(5L0 + 4L1‖∇f(xk)‖)h2k〈∇f(xk), gk −∇f(xk)〉] ≤ 9η2τL20/L1 + 1
8 E[hk]‖∇f(xk)‖2.
Proof. When ‖∇f(xk)‖ ≥ L0/L1, E[(5L0 + 4L1‖∇f(xk)‖)h2k〈∇f(xk), gk −∇f(xk)〉] ≤9L1‖∇f(xk)‖E[h2k]‖∇f(xk)‖τ
≤1 8 E[hk]‖∇f(xk)‖2
The last inequality follows by (12).
When ‖∇f(xk)‖ ≤ L0/L1, E[(5L0 + 4L1‖∇f(xk)‖)h2k〈∇f(xk), gk −∇f(xk)〉] ≤9η2τL20/L1
Lemma 13. 5L0 + 4L1‖∇f(xk)‖
2 E[h2k(‖gk −∇f(xk)‖2)] ≤ (5L0 + 2L1τ)η2τ2 +
1 8 ‖∇f(xk)‖2E[hk].
Proof. When ‖∇f(xk)‖ ≥ L0/L1 + τ , we get 5L0 + 4L1‖∇f(xk)‖
2 E[h2k(‖gk −∇f(xk)‖2)] ≤ 5L1‖∇f(xk)‖2E[hk]ητ ≤
1 8 ‖∇f(xk)‖2E[hk].
The first inequality follows by hk ≤ η and ‖gk − ∇f(xk)‖ ≤ τ ≤ ‖∇f(xk)‖.The last inequality follows by (12).
When ‖∇f(xk)‖ ≤ L0/L1 + τ , we get 5L0 + 4L1‖∇f(xk)‖
2 E[h2k(‖gk −∇f(xk)‖2)] ≤ (5L0 + 2L1τ)η2τ2.

heading: G PROOF OF THEOREM 8
text: Similar to proof of Theorem 3, we have
E[f(xk+1)|] ≤f(xk)− E[hk〈gk,∇f(xk)〉] + 5L0 + 4L1‖∇f(xk)‖
2 E[h2k‖gk‖2]
≤f(xk)− 1√ T ‖∇f(xk)‖2 +
5L0 + 4L1M(M + τ) 2
2T
Sum across k ∈ {0, ..., T − 1} and take expectations, then we can get
0 ≤f(x0)− E[f(xT )]− 1√ T T∑ k=1 E [ ‖∇f(xk)‖2 ] + 5L0 + 4L1M(M + τ) 2 2
Rearrange and we get
1
T T∑ k=1 E [ ‖∇f(xk)‖2 ] ≤ 1√ T ( f(x0)− f∗ + 5L0 + 4L1M(M + τ) 2 2 ) By Jensen’s inequality,
1
T T∑ k=1 E[‖∇f(xk)‖] ≤ √ 1√ T ( f(x0)− f∗ + 5L0 + 4L1M(M + τ)2 2 ) By Markov inequality,
P
{ 1
T T∑ k=1 [ ‖∇f(xk)‖2 ] > 2√ T ( f(x0)− f∗ + 5L0 + 4L1M(M + τ) 2 2 )} ≤ 0.5
The theorem follows by the definition in (9) and Jensen’s inequality.

heading: H EXPERIMENT DETAILS
text: In this section, we first briefly overview the tasks and models used in our experiment. Then we explain how we estimate smoothness of the function. Lastly, we describe some details for generating the plots in Figure 2 and Figure 3.
H.1 LANGUAGE MODELLING
Clipped gradient descent was introduced in (vanilla) recurrent neural network (RNN) language model (LM) (Mikolov et al., 2010) training to alleviate the exploding gradient problem, and has been used in more sophisticated RNN models (Hochreiter and Schmidhuber, 1997) or seq2seq models for language modelling or other NLP applications (Sutskever et 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 et al., 2017).
The task of language modelling is to model the probability of the next word wt+1 based on word history (or context). Given a document of length T (words) as training data, the training objective is to minimize negative log-likelihood of the data −1T Σ T t=1 logP (wt|w1...wt−1).
We run LM experiments on the Penn Treebank (PTB) (Mikolov et al., 2010) dataset, which has been a popular benchmark for language modelling. It has a vocabulary of size 10k, and 887k/70k/78k words for training/validation/testing.
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 is used, and the model is trained for 500 epochs. After training, the model reaches a text-set perplexity of 56.5, which is very close to the current state-of-art result (Dai et al., 2019) on the PTB dataset.
3https://github.com/salesforce/awd-lstm-lm
H.2 IMAGE CLASSIFICATION
As a comparison, we run the same set of experiments on image classification tasks. We train the ResNet20 (He et al., 2016) model on Cifar10 (Krizhevsky and Hinton, 2009) classification dataset. The dataset contains 50k training images and 10k testing images in 10 classes.
Unless explicitly state, we use the standard hyper-parameters based on the Github repository4. Our baseline algorithm runs SGD momentum with learning rate 0.1, momentum 0.9 for 200 epochs. We choose weight decay to be 5e−4. 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 Cifar10. The baseline already beats some recently proposed algorithms which claim to improve upon SGD momentum.
H.3 ESTIMATING SMOOTHNESS
Our smoothness estimator follows a similar implementation as in (Santurkar et al., 2018). More precisely, given a sequence of iterates generated by training procedure {xk}k, we estimate the smoothness L̂(xk) as follows. For some small value δ ∈ (0, 1), d = xk+1 − xk,
L̂(xk) = max γ∈{δ,2δ,...,1} ‖∇f(x+ γd)−∇f(x)‖ ‖γd‖ . (17)
4https://github.com/kuangliu/pytorch-cifar
This suggests that we only care about the variation of gradient along xk+1 − xk. The motivation is 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 xk+1 and xk.
H.4 ADDITIONAL PLOTS
The plots in Figure 2a show log-scale scattered data for iterates in the first epoch. To supplement this result, we show in Figure 5a the linear scale plot of the same data as in Figure 2a. In Figure 5b, we run the same experiment as in Figure 2a for 200 epochs instead of 1 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.

heading: I A SYNTHETIC EXPERIMENT
text: In this section, we demonstrate the different behaviors of gradient descent versus clipped gradient descent by optimizing a simple polynomial f(x) = x4. We initialize the point at x0 = 30 and run both algorithms. Within the sublevel set [−30, 30], the function satisfies
f ′′(x) ≤ 12× 302 = 1.08× 104
f ′′(x) ≤ 10f ′(x) + 0.1. Therefore, we can either pick L1 = 0, L0 = 1.084 for gradient descent or L1 = 10.L0 = 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.

heading: J A QUANTITATIVE COMPARISON OF THEOREMS AND EXPERIMENTS
text: 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 as O(ML1+L0√
T ), while for
Clipped GD, the term scales as O( L0√ T ).
First, we start with the synthetic experiment presented in I. From theory, we infer that the improvement of f
′(xGD) f ′(xCGD)
≈ L0ML1+L0 ≈ 1e5. In experiment, the best performing GD reaches f ′(xT ) = 0.36, while for clipped GD, the value is 1.3e − 8, and the ratio is f ′(xGD) f ′(xCGD)
≈ 1e7. This suggests that in this very adversarial (against vanilla GD) synthetic experiment, the theorem is correct but conservative.
Next, we test how well the theory can align with practice in neural network training. To do so, we rerun the PTB experiment in 5 with a smaller architecture (2-Layer LSTM with 200 embedding dimension and 512 inner dimension). We choose hyperparameters based on 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 quantify the difference between theory and practice, we follow the procedure as in the synthetic experiment. First, we estimate ML1 + L0 = 25 for GD from Figure 8(c). Second, we estimate L1 = 10, L0 = 5 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 3 and Theorem 6). This doesn’t exactly align but is 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 is absent in our rough estimates ML1+L0L0 .

Review summaries:
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.

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.