Year: 2019

Abstract:
While stochastic gradient descent (SGD) is still the de facto algorithm in deep learning, adaptive methods like Adam have been observed to outperform SGD across important tasks, such as attention models. The settings under which SGD performs poorly in comparison to Adam are not well understood yet. In this paper, we provide empirical and theoretical evidence that a heavy-tailed distribution of the noise in stochastic gradients is a root cause of SGD’s poor performance. Based on this observation, we study clipped variants of SGD that circumvent this issue; we then analyze their convergence under heavy-tailed noise. Furthermore, we develop a new adaptive coordinate-wise clipping algorithm (ACClip) tailored to such settings. Subsequently, we show how adaptive methods like Adam can be viewed through the lens of clipping, which helps us explain Adam’s strong performance under heavy-tail noise settings. Finally, we show that the proposed ACClip outperforms Adam for both BERT pretraining and finetuning tasks.

heading: 1 INTRODUCTION
text: Stochastic gradient descent (SGD) is the canonical algorithm for training neural networks (Robbins & Monro, 1951). SGD iteratively updates model parameters in the negative gradient direction and thus seamlessly scales to large-scale settings. Though a well-tuned SGD outperforms adaptive methods (Wilson et al., 2017) in many traditional tasks including ImageNet classification (see Figure 1b), certain tasks necessitate the use of adaptive variants of SGD (e.g., Adagrad (Duchi et al., 2011), Adam (Kingma & Ba, 2014), AMSGrad (Reddi et al., 2019)), which employ adaptive perparameter learning rates. For instance, consider the task of training an attention model (Vaswani et al., 2017) using BERT (Devlin et al., 2018). Figure 1a shows loss curves of BERT pretraining obtained from SGD with momentum as well as Adam. It can be seen that in spite of extensive hyperparameter tuning, SGD converges much slower than Adam during BERT training.
The first significant hint to the performance of Adam on BERT comes from the distribution of the stochastic gradients. For Imagenet, the norms of the mini-batch gradients are typically quite small and well concentrated around their mean. On the other hand, the mini-batch gradient norms for BERT take a wide range of values and are sometimes much larger than their mean value. More formally, while the distribution of the stochastic gradients in Imagenet is well approximated by a Gaussian, the distribution for BERT seems to be heavy-tailed.
In this work, we perform a rigorous theoretical and empirical study of the convergence of optimization methods under such heavy-tailed noise. In this setting, some of the stochastic gradients are much larger than the mean and can excessively influence the updates of SGD. This makes SGD unstable and leads to its poor performance. A natural strategy to stabilize the updates is to clip the magnitude of the stochastic gradients. We prove that indeed this is sufficient to ensure convergence even under heavy-tailed noise. Further, we show that adaptive methods in fact implicitly have such a clipping behavior, thereby providing a explanation for their superiority to SGD on BERT.
More specifically, we make the following main contributions:
• We empirically show that in tasks on which Adam outperforms SGD (BERT pretraining), the noise in stochastic gradients is heavy-tailed. On the other hand, on tasks where traditionally SGD outperforms Adam (ImageNet training), we show that the noise is well concentrated.
• We study the convergence of gradient methods under heavy-tailed noise condition where SGD’s performance degrades and previous convergence proofs fail. We then establish the convergence
of clipped gradient methods under the same condition and prove that they obtain theoretically optimal rates.
• We show that Adam implicitly performs coordinate-wise gradient clipping and can hence, unlike SGD, tackle heavy-tailed noise. We prove that using such coordinate-wise clipping thresholds can be significantly faster than using a single global one. This can explain the superior performance of Adam on BERT pretraining.
• Inspired by our theoretical analysis, we propose a novel adaptive-threshold coordinate-wise clipping algorithm and experimentally show that it outperforms Adam on BERT training tasks.

heading: 1.1 RELATED WORK
text: Adaptive step sizes. Adaptive step size during optimization has long been studied (Armijo, 1966; Polyak, 1987). More recently, Duchi et al. (2011) developed the Adagrad algorithm that benefits from the sparsity in stochastic gradients. Inspired by Adagrad, several adaptive methods have been proposed in the deep learning community (Tieleman & Hinton, 2012; Kingma & Ba, 2014). Recently, there has been a surge in interest to study the theoretical properties of these adaptive gradient methods due to (Reddi et al., 2019), which pointed out the non-convergence of Adam and proposed an alternative algorithm, AMSGrad. Since then, many works studied different interesting aspects of adaptive methods, see (Ward et al., 2018; Li & Orabona, 2018; Zhou et al., 2018a; Staib et al., 2019; Chen et al., 2018; Zou & Shen, 2018; Zhou et al., 2018b; Agarwal et al., 2018; Zou et al., 2019). Another direction of related work is normalized gradient descent, which has been studied for quasiconvex and non-convex settings (Levy, 2016; Hazan et al., 2015; Zhang et al., 2019). In contrast to our work, these prior works assume standard noise distributions that might not be applicable to key modern applications such as attention models, which exhibit heavy-tailed noise. Furthermore, mostly, the convergence rates of adaptive methods are worse than SGD.
Noise in neural network. There has been little study of the actual stochastic gradient noise distributions in neural network training. To our knowledge, Simsekli et al. (2019) is the first work to focus on this topic and observe heavy tailed noise in network training. Our work differs in two important ways: first, we treat the noise as a high dimensional vector, while (Simsekli et al., 2019) treat deviations in each coordinate as scaler noises to estimate tail index. Second, we focus on convergence of optimization algorithm, the original paper focus on Langevin dynamics and consistence of the index estimator. More experiment comparison is in Appendix H.

heading: 2 HEAVY-TAILED NOISE IN STOCHASTIC GRADIENTS
text: To gain intuition about the difference between SGD and Adam, we start our discussion with the study of noise distributions of stochastic gradient that arise during neural network training. In particular, we focus on noise distributions while training two popular deep learning models — BERT and ResNet. Note that BERT and ResNet are typically trained with Adam and SGD (with momentum) respectively and can thus, provide insights about difference between these optimizers.
We first investigate the distribution of the gradient noise norm ‖g −∇f(x)‖ in the aforementioned neural network models, where g is the stochastic gradient computed from a minibatch sample. Figure 7 (a) and (d) show these distributions for ResNet50 on ImageNet and BERT on the Wikipedia and books dataset at model initialization respectively. For comparison, we plot distributions of a normalized sum of squared Gaussians, a well-concentrated distribution, and a Levy-α-stable distribution, a heavy-tailed distribution, in Figure 7 (b) and (e) respectively. We observe that the noise distribution for BERT appears heavy-tailed, while that of ResNet50 is well-concentrated.
To support this observation, in Figure 7 (c) and (f) we further show the empirical variance of stochastic gradients with respect to the sample size used in the estimation. The results highlight that while the corresponding estimator converges for Imagenet, the empirical variance does not converge in BERT training even as the sample size approaches 107.
Figure 7 clearly shows that while the noise pattern is well-concentrated in some cases, it is also heavy tailed in other settings. We hypothesize that this is one major aspect that determines the performance of SGD and adaptive methods. More specifically, we argue and provide evidence that adaptive methods can be faster than SGD in scenarios where heavy-tailed noise distributions arise. More empirical details can be found in Section 5.

heading: 2.1 OPTIMIZATION PROBLEM SETUP
text: We now formalize the optimization setup with heavy-tailed noise. Neural network training can be seen as minimizing a differentiable stochastic function f(x) = Eξ[f(x, ξ)], where f : Rd → R can be potentially nonconvex. At each iteration, we assume access to an unbiased stochastic gradient g(x) = ∇f(x, ξ) corresponding to the parameters x, and also assume finite α moment.
Assumption 1 (Existence of α−moment). There exists positive real numbers α ∈ (1, 2] andG > 0 such that for all x, E[‖g(x)‖α] ≤ Gα.
Note that it is possible that the variance of g(x) is unbounded while simultaneously satisfying the above assumption for α < 2, e.g. the Pareto distribution. Hence Assumption 1 is much weaker than the standard bounded second moment assumption. The possibility that the variance could be unbounded has a profound impact on the optimization process. In particular, previous convergence proofs for SGD fail and the algorithm may diverge (see Appendix A). As we will illustrate over the next few sections, using a biased clipped stochastic gradient estimator allows us to circumvent the problem of unbounded variance, while ensuring convergence even under heavy-tailed noise.

heading: 3 CLIPPED GRADIENT DESCENT AND ACCLIP ALGORITHM
text: Our key idea is that by clipping the stochastic gradient, we can effectively control its variance. While this does introduce some additional bias, the clipping threshold can be (possibly adaptively) tuned to trade-off variance with the introduced bias.
Empirically, this is a prevalent practice e.g. Merity et al. (2018) use clipped SGD to train AWDLSTM whereas Devlin et al. (2018) use clipped Adam to pretrain BERT. The general form of clipped gradient descent is outlined in Algorithm 1.
Algorithm 1 A general framework for clipped gradient descent 1: x,mk ← x0, 0 2: for k = 1, ·, T do 3: mk ← β1mk−1 + (1− β1)gk 4: ĝk ← clip(τk,mk) 5: xk ← xk−1 − ηkĝk
return xK , where random variable K is supported on {1, · · · , T}.
Perhaps the two most natural candidates for clipping mechanisms are Global CLIPping where a single global threshold is used and Coordinate-wise CLIPping using d coordinate-wise thresholds
GClip(τk,mk) = min {
τk ‖mk‖ , 1
} mk , for τk ∈ R≥0 or, (GClip)
CClip(τk,mk) = min {
τk |mk| , 1 } mk , for τk ∈ Rd≥0 . (CClip)
where all operations for CClip are performed element-wise. Smaller threshold values of τk imply smaller variance, but also higher bias. If the noise distribution is very heavy-tailed (or has a large variance), one could compensate by picking a smaller threshold. See Theorems 1 and 2 for a theoretical treatment of this for GClip. While GClip preserves the update direction and only scales its magnitude, CClip scales each coordinate individually and may not preserve the direction. However, if the noise distribution varies significantly across coordinates, CClip can take advantage of this and only clip those which are more heavy-tailed and consequently converge faster (see Theorem 3).
However, to perform such a coordinate-wise variance-bias trade off optimally would require tuning all d thresholds, which could be extremely large in deep learning. Even if tuning were feasible, the noise distribution may be non-stationary and significantly vary as training progresses (see Fig. 5). To address this challenge, we propose Adaptive Coordinate-wise CLIPping, which adaptively sets the thresholds for each coordinate
ACClip(τk,mk) = min {
τk |mk|+ , 1
} mk, τ α k = β2τ α k−1 + (1− β2)|gk|α , (ACClip)
where operations are element-wise, is a small number for numerical stability, and we set α = 1 by default. The use of a coordinate-wise α-moment (as opposed to the traditional second moment) is motivated by our theory and estimates B = E[|gαk |]1/α in Assumption 2. Since E[|gαk |]1/α is increasing in α ≥ 1, using α = 1 is a conservative bound on B when the true α is unknown.

heading: 3.1 ADAM AS AN ADAPTIVE CLIPPING METHOD
text: We study Adam without momentum, i.e. RMSProp, and show that it resembles coordinate-wise clipping. When β1 = 0, we can rewrite the update for Adam and ACClip as SGD with effective step-sizes hAdam and hclip respectively
xk+1 = xk − α + √ β2vk+(1−β2)|gk|2 gk =: xk − hAdamgk , and xk+1 = xk − ηk min { τk |gk| , 1 } gk =: xk − hclipgk.
Given any set of parameters for RMSProp, if we set the parameters for ACClip as
ηk = 2α + √ β2vk
and τk = + √ β2vk√
1−β2 ,
then 12hclip ≤ hAdam ≤ 2hclip. Thus, the two differ by at most af factor of 2 and Adam can be seen as ACClip where τk is set using √ vk, which estimates E[|gk|2]1/2, and a correspondingly decreasing
step-size. This clipping effect can explain the faster convergence of Adam for training attention models in the presence of heavy-tailed noise (Fig. 1a). In contrast to Adam, ACClip (with α = 1) uses a simpler update scheme where τk is set using an estimate of E[|gk|] and a constant step-size. This allows ACClip to take larger steps than Adam and hence converge slightly faster (Section 5).

heading: 4 THEORETICAL ANALYSIS
text: In this section, we address the following three key points. First, we show how gradient clipping ensures convergence for both convex and non-convex functions under heavy-tailed noise. Then, we study when and why coordinate-wise clipping (CClip) outperforms global clipping (GClip). Finally, we show that (upto numerical constants) clipping is an optimal strategy under the strongly convex setting. Together, these provide a comprehensive analysis of the effect of clipping and a strong theoretical motivation for using it whenever one suspects the presence of noise with unbounded variance. Our results are summarized in Table 1, and all proofs are relegated to the Appendices.

heading: 4.1 CONVERGENCE OF GLOBALLY CLIPPED SGD
text: We state the rates for strongly-convex functions and for smooth non-convex functions. We focus on GClip with momentum β = 0, under the assumption 1. In the strongly convex case, we can prove the following rates of convergence to the optimum.
Theorem 1 (Strongly-convex convergence). Suppose that f is a µ-strongly convex function and the noise satisfies assumption 1. Then let {xk} be the iterates of Algorithm 1 using GClip, clipping parameter τk = Gkα−1 and steps-size ηk = 4µ(k+1) . Define the output to be a j-weighted
combination of the iterates: x̄k = ∑k j=1 jxj−1/( ∑k j=1 j) . Then the output x̄k satisfies:
E[f(x̄k)]− f(x?) ≤ 16G2
µ(k + 1)2(α−1)/α .
Observe that when α = 2 and with bounded second moment, we recover exactly the optimal SGD rate of O(G2/µk) of Lacoste-Julien et al. (2012). For any other α ∈ (1, 2), the performance of GClip gracefully degrades. As we will later show, this rate is in fact optimal for every α ∈ (1, 2]. In contrast, SGD can be arbitrarily bad when α < 2 (see Appendix A). We can also prove rates of convergence to a stationary point for smooth non-convex functions.
Theorem 2 (Non-convex convergence). Suppose that f is a possible non-convexL-smooth function and the noise satisfies assumption 1. Then let {xk} be the iterates of Algorithm 1 using GClip with momentum β = 0, constant step-size ηk = [( f(x0)−f? G2(K+1) ) α 3α−2 / L 2α−2 3α−2 ] and constant clipping parameter τk = G/(ηL) 1 α . Then, the sequence {xk} satisfies
1
K K∑ k=1 E[‖∇f(xk−1)‖2] ≤ 4G 2α 3α−2 ( f(x0)− f(x?) K ) 2α−2 3α−2 .
The rates of convergence for the non-convex case in Theorem 2 exactly match those of the usual SGD rates of O(1/ √ k) when α = 2 and gracefully degrades for α ∈ (1, 2]. Thus, GClip converges for both convex and non-convex functions under Assumption 1. However, Assumption 1 is quite crude and summarizes noise into a single number G. The noise present in the different gradient coordinates can be quite varied, and as we next show, CClip can take advantage of this and clip each coordinate independently. This allows CClip (when tuned properly) to have a significantly better convergence rate when compared to GClip.

heading: 4.2 BENEFITS OF COORDINATE-WISE CLIPPING
text: We had previously assumed a global bound on the α-moment of the norm of the stochastic gradient is bounded by G. However, G might be hiding some dimension dependence d. We next study a more fine-grained model of the noise in order to tease out this dependence. Assumption 2 (Coordinate-wise α moment). Denote {gi(x)} to be the coordinate-wise gradients for i ∈ [d]. We assume there exist constants {Bi} ≥ 0 and α ∈ (1, 2] such that E[|gi(x)|α] ≤ Bαi .
For the sake of convenience, we denote B = [B1;B2; · · · ;Bd] ∈ Rd, ‖B‖a = ( ∑ Bai )
1/a. Under this more refined assumption, we can show the following corollary: Corollary 1 (GClip under coordinate-wise noise). Suppose we run GClip under the Assumption of 2 to obtain the sequence {xk}. Then, if f is µ-strongly convex, with appropriate step-sizes and averaging, the output x̄k satisfies
E[f(x̄k)]− f(x?) ≤ 16d‖B‖2α
µ(k + 1)2(α−1)/α .
Thus, the convergence of GClip can have a pretty strong dependence on d, which for large-scale problems might be problematic. We show next that using coordinate-wise clipping avoids this issue. Theorem 3 (CClip under coordinate-wise noise). Suppose we run CClip under the Assumption of 2 with τk = Bkα−1 to obtain the sequence {xk}. Then, if f is µ-strongly convex, with appropriate step-sizes and averaging, the output x̄k satisfies
E[f(x̄k)]− f(x?) ≤ 16‖B‖22
µ(k + 1)2(α−1)/α .
Note that ‖B‖2 ≤ ‖B‖α. Hence CClip has a worst-case convergence independent of d under the coordinate-wise noise model. Similar comparison between GClip and CClip can be done for non-convex conditions too (see Thms 5 and 3 in Appendix F). This improvement has two sources: coordinate-wise clipping can adapt to different Bi in each coordinate; the global L2 clipping does not align with the geometry of coordinate-wise noise. Although we only compare upper-bounds here, when the noise across coordinates is independent the upper bounds here may be tight (see Lemma 4). Further, our experiments where d n (over-parameterized models) also empirically confirms superior performance of coordinate-wise clipping.
Given that CClip may be better than GClip, we next address the natural question of whether there exists some other strategy (which may perhaps not involve clipping at all) which is even better.

heading: 4.3 AN INFORMATION THEORETIC LOWER BOUND
text: We show a strong lower-bound for a simple class of one-dimensional quadratic functions with stochastic gradients satisfying E[|g(x)|α] ≤ 1. This matches the upper bounds of Theorems 1 and 3 for strongly-convex functions, showing that the simple clipping mechanism of Algorithm 1 is (up to constants) information theoretically optimal, providing a strong justification for its use. Theorem 4. For any α ∈ (1, 2] and any (possibly randomized) algorithm A, there exists a problem f which is 1-strongly convex and 1-smooth (µ = 1 and L = 1), and stochastic gradients which satisfy Assumptions 1 and 2 with G, ‖B‖ ≤ 1 such that the output xk of the algorithm A after processing k stochastic gradients has an error
E[f(xk)]− f(x?) ≥ Ω (
1
k2(α−1)/α
) .
0 50000 100000 150000 200000 iterations
1.5
2.0
2.5
3.0 3.5 Validation loss of BERT pretraining SGD momentum Clipped SGD momentum ADAM ACClip
Figure 3: Validation loss for BERTbase pretraining with the sequence length of 128. While there remains a large gap between non-adaptive methods and adaptive methods, clipped SGD momentum achieves faster convergence compared to standard SGD momentum. The proposed algorithm for adaptive coordinate-wise clipping (ACClip) achieves a lower loss than Adam.

heading: 5 EXPERIMENTS
text: We perform extensive evaluations of ACClip on BERT pre-training and fine-tuning tasks and demonstrate its advantage over Adam in Section 5.1. Since ACClip was explicitly designed to tackle heavytailed noise, this provides further evidence that Adam owes its efficacy to its gradient clipping effect. For completeness, an experiment on ImageNet is included in Appendix I. Then, in Section 5.2 we study the cause of the heavy-tailedness and show that both the architecture and the data play a role.

heading: 5.1 PERFORMANCE OF ACCLIP FOR BERT PRE-TRAINING AND FINE-TUNING
text: We evaluate the empirical performance of our proposed ACClip algorithm on BERT pre-training as well fine-tuning using the SQUAD v1.1 dataset. As a baseline, we use Adam optimizer and the same training setup as in the BERT paper (Devlin et al., 2018). For ACClip, we set lr = 1× 10−4, β1 = 0.9, β2 = 0.99, = 1× 10−5 and wd = 1× 10−5. We compare both setups on BERT models of three different sizes, BERTbase with 6 and 12 layers as well as BERTlarge with 24 layers.
Figure 3 shows the validation loss for pretraining BERTbase using SGD with momentum, GClip, Adam and ACClip. The learning rates and hyperparameters for each method have been extensively tuned to provide best performance on validation set. However, even after extensive tuning, there remains a large gap between (clipped) SGD momentum and adaptive methods. Furthermore, clipped SGD achieves faster convergence as well as lower final loss compared to standard SGD. Lastly, the proposed optimizer ACClip achieves a lower loss than the Adam. Table 2 further shows that ACClip achieves lower loss and higher masked-LM accuracy for all model sizes.
Next, we evaluate ACClip on the SQUAD v1.1 fine-tuning task. We again follow the procedure outlined in (Devlin et al., 2018) and present the results on the Dev set in Table 3. Both for F1 as well as for exact match, the proposed algorithm outperforms Adam on all model sizes.
The experimental results on BERT pretraining and fine-tuning indicate the effectiveness of the proposed algorithm. The increasing clipping threshold during the training is motivated by our theoretical analysis an indeed helps with empirical performance by reducing the bias in gradient estimators.

heading: 5.2 NOISE PATTERNS IN NEURAL NETWORK TRAINING
text: In the following experiment, we aim to understand the effect of model architecture and training data on the shape of gradient noise, and to understand how this shape evolves during training.
To address the first question, we measure the noise distribution in an Attention and a ResNet-like model on both Wikipedia and synthetic Gaussian data. We used BERTbase model as the Attention model, and the ResNet is constructed by removing the self-attention modules in the transformer blocks. Gaussian synthetic data is generated by replacing the token embedding layer with normalized Gaussian input. The resulting noise histograms are plotted in Figure 4. From the figure,
heavy-tailed noises are observed in the Attention model independently of the input data. For the ResNet model, we see Gaussian input leads to Gaussian noise while Wikipedia data makes the noise to be heavy-tailed. Therefore, the noise pattern results from both the model architecture as well as the data distribution.
Figure 5 shows how the distribution of gradient noise is evolving during training. The results highlight that the noise distribution is non-stationary during BERT training as the noise is becoming increasingly more concentrated. In contrast, for the ResNet model on ImageNet, the shape of the noise distribution remains almost unchanged. This result supports the use of exponential moving average as an estimator for the underlying non-stationary distribution to accelerate optimization.

heading: 6 CONCLUSION
text: Our work theoretically and empirically ties the advantage of adaptive methods over SGD to the heavy-tailed nature of gradient noise. A careful analysis of the noise and its impact yielded several insights: that adaptive methods implicitly perform gradient clipping, that clipping is an excellent strategy to deal with heavy-tailed noise, and that the adaptive coordinate-wise clipping yields state of the art performance for training attention models. Our results add to a growing body of work which demonstrate the importance of the structure of the noise in understanding neural network training. We believe additional such investigations into the source of the heavy tailed-ness, as well as a characterization of the noise in other scenarios where Adam is used (e.g. GAN training or reinforcement learning) can lead to further insights with significant impact on practice.

heading: A NECESSITY OF ADAPTIVITY AND NON-CONVERGENCE OF SGD
text: Consider a simple toy function f(x) = 12‖x − a‖ 2 with an optimum value of 0 achieved at x? = a. Suppose that we receive stochastic gradients g(x) with potentially unbounded variance i.e. E[‖g(x)−∇f(x)‖2] =∞. Then, starting from x0 = 0, let us run SGD (possibly with momentum) using with arbitrary but fixed step-sizes i.e. the step-sizes are predetermined and do not depend on the stochastic gradients. The output xk is then simply a linear combination of {g(xj)}j≤k with some (fixed) weights {ηj ∈ R}j≤k
xk = k∑ j=1 ηjg(xj) .
The the expected function suboptimality at xk can be lower bounded as follows E[f(xk)]− f(a) = E[‖xk − a‖2] ≥ E[‖xk − E[xk]‖2] = E [∥∥∥∥ k∑
j=1
ηj(g(xj)− E[g(xj))] ∥∥∥∥2] .
The last term in the above expression is the variance of sum of k independent random variables and ηj are fixed constants. We can then simplify as
E [∥∥∥∥ k∑ j=1 ηj(g(xj)− E[g(xj))] ∥∥∥∥2] = k∑ j=1 η2jE [∥∥(g(xj)− E[g(xj))]∥∥2]
≥ ( ∑k i=0 η 2 i ) maxj∈[k] E[‖g(xj)−∇f(xj)]‖2] .
This implies that if there is any i, j ≤ k such that η2i > 0 and E[‖g(xj) − ∇f(xj)]‖2 = ∞, we have E[f(xk)] = ∞! Thus, the solution provided by SGD can be arbitrarily bad when the domain is unbounded.
It was important in our proof above that the step-sizes are fixed before-hand and are independent of the stochastic gradients. Notably, both gradient clipping and adaptive methods do not satisfy this property, and can indeed tackle unbounded variance. In some sense, the above example establishes adaptivity as being necessary when dealing with heavy-tailed noise.

heading: B ADDITIONAL DEFINITIONS AND NOTATION
text: Here we describe some of the formal definitions which were previously skipped. Definition 3 (µ-strong-convexity). f is µ-strongly convex, if there exist positive constants µ such that ∀x, y,
f(y) ≥ f(x) + 〈∇f(x), y − x〉+ µ 2 ‖y − x‖2
The strong convexity assumption and the bounded gradient assumption implicitly implies that the domain is bounded. However, the domain diameter is not used explicitly in the proof. The projected clipped gradient descent follows exactly the same argument and the fact that orthogonal projections contract distances. Definition 4 (L-smoothness). f is L-smooth, if there exist positive constants L such that ∀x, y,
f(y) ≤ f(x) + 〈∇f(x), y − x〉+ L 2 ‖y − x‖2 .
Note that the above definitions together imply that µ ≤ L.

heading: C EFFECT OF GLOBAL CLIPPING ON VARIANCE AND BIAS
text: We focus on (GClip) under stochastic gradients which satisfy Assumption 1. Lemma 2. For any g(x) suppose that assumption 1 holds with α ∈ (1, 2]. Then the estimator ĝ from (GClip) with global clipping parameter τ ≥ 0 satisfies:
E [ ‖ĝ(x)‖2 ] ≤ Gατ2−α and ‖E[ĝ(x)]−∇f(x)‖2 ≤ G2ατ−2(α−1) .
Proof. First, we bound the variance. E[‖ĝ(x)‖2] = E[‖ĝ(x)‖α‖ĝ(x)‖2−α]
By the fact that ĝ(x) ≤ τ , we get E[‖ĝ(x)‖2] = E[‖ĝ(x)‖ατ2−α] ≤ Gατ2−α.
Next, we bound the bias, ‖E[ĝ(x)]−∇f(x)‖ = ‖E[ĝ(x)− g(x)]‖ ≤ E[‖ĝ(x)− g(x)‖] = E[‖ĝ(x)− g(x)‖1{|g(x)|≥τ}] ≤ E [ ‖g(x)‖1{|g(x)|≥τ} ] ≤ E[‖g(x)‖α]τ−(α−1).
The last inequality follows by Markov inequality.
As we increase the clipping parameter τ , note that the variance (the first term in Lemma 2) increases while the bias (which is the second term) decreases. This way, we can carefully trade-off the variance of our estimator against its bias, thereby ensuring convergence of the algorithm.

heading: D STRONGLY-CONVEX RATES (PROOF OF THEOREM 1)
text: For simplicity, we denote ĝk = ηkĝ(xk) and the bias bk = E[ĝk]−∇f(xk). ‖xk − x∗‖2 = ‖xk−1 − ηkĝk−1 − x∗‖2
= ‖xk−1 − x∗‖2 − 2ηk〈xk−1 − x∗,∇f(xk−1)〉 − 2ηk〈xk−1 − x∗, bk−1〉+ η2k‖ĝk−1‖2 ≤ (1− µηk)‖xk−1 − x∗‖2 − 2ηk(f(xk−1)− f∗))
+ 2ηk( µ
4 ‖xk−1 − x∗‖2 +
4 µ ‖bk‖2) + η2k‖ĝk−1‖2.
Rearrange and we get
f(xk−1)− f∗ ≤ η−1k − µ/2
2 ‖xk−1 − x∗‖2 − η−1k 2 ‖xk − x∗‖2 + 4 µ ‖bk‖2 + ηk 2 ‖ĝk−1‖2.
After taking expectation and apply the inequality from Lemma 2, we get E[f(xk−1)]− f∗ ≤ E [ η−1k − µ/2
2 ‖xk−1 − x∗‖2 − η−1k 2 ‖xk − x∗‖2 ] + 4G2ατ2−2αµ−1 + ηkG ατ2−α/2.
Then take ηk = 4µ(k+1) , τk = Gk 1 α and multiply both side by k, we get
kE[f(xk−1)]− f∗ ≤ µ 8 E [ k(k − 1)‖xk−1 − x∗‖2 − k(k + 1)‖xk − x∗‖2 ] + 8G2k 2−α α µ−1.
Notice that ∑K k=1 k 2−α α ≤ ∫K+1 0
k 2−α α dk ≤ (K + 1)2/α. Sum over k and we get∑K
k=1 kE[f(xk−1)]− f∗ ≤ µ 8 E [ −T (T + 1)‖xT − x∗‖2 ] + 8G2(K + 1) 2 αµ−1.
Devide both side by K(K+1)2 and we get
2
K(K + 1)
∑K k=1 kE[f(xk−1)]− f∗ ≤ 8G 2K−1(K + 1) 2−α α µ−1.
Notice that for K ≥ 1, K−1 ≤ 2(K + 1)−1. We have 2
K(K + 1)
∑K k=1 kE[f(xk−1)]− f∗ ≤ 16G 2(K + 1) 2−2α α µ−1.
The theorem then follows by Jensen’s inequality.

heading: E NON-CONVEX RATES (PROOF OF THEOREM 2)
text: For simplicity, we denote ĝk = ĝ(xk−1) and the bias bk = E[ĝk]−∇f(xk). By Assumption 4, we have
f(xk) ≤ f(xk−1) + 〈∇f(xk−1),−ηkĝk〉+ η2kL
2 ‖ĝk‖2
≤ f(xk−1)− ηk‖∇f(xk−1)‖2 − ηk〈∇f(xk−1), bk〉+ η2kL
2 ‖ĝk‖2
≤ f(xk−1)− ηk‖∇f(xk−1)‖2 − ηk〈∇f(xk−1), bk〉+ η2kL
2 ‖ĝk‖2
≤ f(xk−1)− ηk‖∇f(xk−1)‖2 + ηk 2 ‖∇f(xk−1)‖2 + ηk 2 ‖bk‖2 +
η2kL
2 ‖ĝk‖2 .
Here the last step used the AM-GM inequality. Then, taking expectation in both sides and using Lemma 2 gives
E[f(xk)|xk−1] ≤ f(xk−1)− ηk 2 ‖∇f(xk−1)‖2 +
η2kLG ατ2−α
2 + ηkG
2α
2τ2α−2 .
Rearrange and sum the terms above for some fixed step-size {ηk = η} and threshold {τk = τ} to get
1
K K∑ k=1 E [ ‖∇f(xk−1)‖2 ] ≤ 2 ηK (f(x0)− E[f(xK)]) + ηLGατ2−α + G2α τ2α−2
≤ 2 ηK
(f(x0)− f?)︸ ︷︷ ︸ T1
+ ηLGατ2−α + G2α
τ2α−2︸ ︷︷ ︸ T2 .
Since we use a threshold τ = G (ηL) 1 α , we can simplify T2 as
ηLGατ2−α + G2α
τ2α−2 =
2G2α τ2α−2 = 2G2(ηL) 2α−2 α .
Denote f0 = f(x0) − f? to ease notation. Then, adding T2 back to T1 and using a step-size η = [( f0 G2K ) α 3α−2 / L 2α−2 3α−2 ] we get
T1 + T2 = 2f0 ηK + 2G2(ηL) 2α−2 α = 4f0 ηK = 4G 2α 3α−2 ( Lf0 K ) 2α−2 3α−2 .
This proves the statement of the theorem.

heading: F EFFECT OF COORDINATE-WISE MOMENT BOUND
text: We now examine how the rates would change if we replace Assumption 1 with Assumption 2.
F.1 CONVERGENCE OF GCLIP (PROOF OF COROLLARY 1)
We now look at(GClip) under assumption 2. We can in fact also prove the following corollary for the non-convex case: Corollary 3 (Non-convex GClip under coordinate-wise noise). Suppose we run GClip under the Assumption of 1 to obtain the sequence {xk}. Then, if f is L-smooth and possibly non-convex, with appropriate step-sizes and averaging,
1
K K∑ k=1 E[‖∇f(xk−1)‖2] ≤ 4( √ d‖B‖α) 2α 3α−2 ( f(x0)− f(x?) K ) 2α−2 3α−2 .
The proof of both the convex and non-convex rates following directly from the following Lemma. Lemma 4. For any g(x) suppose that assumption 2 with α ∈ (1, 2]. Then suppose we have a constant upper-bound E[‖g(x)‖α] ≤ D . Then D satisfies
d α 2−1‖B‖αα ≤ D ≤ dα/2‖B‖αα.
Proof. Note that the function (·)α/2 is concave for α ∈ (1, 2]. Using Jensen’s inequality we can rewrite as:
D ≥ E[‖g(x)‖α] = dα/2E (1 d d∑ i=1 |g(x)(i)|2 )α/2 ≥ dα/2−1E[ d∑ i=1 |g(x)(i)|α ] .
Since the right hand-side can be as large as d α 2−1‖B‖αα, we have our first inequality. On the other hand, we also have an upper bound below:
E[‖g(x)‖α] = E ( d∑ i=1 |g(x)(i)|2 )α/2 ≤ E[(d( dmax i=1 g(x)(i))2 )α/2]
≤ E [ dα/2(
d max i=1
g(x)(i))α ] ≤ E [ dα/2
d∑ i=1 (g(x)(i))α
] ≤ dα/2
d∑ i=1 Bαi
where ‖B‖αα = ∑d i=1B α i . Thus, we have shown that
d α 2−1‖B‖αα ≤ E[‖g(x)‖ α ] ≤ dα/2‖B‖αα .
We know that Jensen’s inequality is tight when all the co-ordinates have equal values. This means that if the noise across the coordinates is linearly correlated the lower bound is tighter, whereas the upper bound is tighter if the coordinates depend upon each other in a more complicated manner or are independent of each other.
Substituting this bound on G in Theorems 1 and 2 gives us our corollaries.
F.2 CONVERGENCE OF CCLIP (PROOF OF THEOREM 3)
The proof relies on the key lemma which captures the bias-variance trade off under the new noiseassumption and coordinate-wise clipping. Lemma 5. For any g(x) suppose that assumption 2 with α ∈ (1, 2] holds. Denote gi to be ith component of g(x),∇f(x)i to be ith component of∇f(x). Then the estimator ĝ(x) = [ĝ1; · · · ; ĝd] from (CClip) with clipping parameter τ = [τ1; τ2; · · · ; τd] satisfies:
E [ ‖ĝi‖2 ] ≤ Bαi τ2−αi and ‖E[ĝi]−∇f(x)i‖ 2 ≤ B2αi τ −2(α−1) i .
Proof. Apply Lemma 2 to the one dimensional case in each coordinate.
Proof of Theorem 3. Theorem 1 For simplicity, we denote ĝk = ηkĝ(xk) and the bias bk = E[ĝk]− ∇f(xk).
‖xk − x∗‖2 = ‖xk−1 − ηkĝk−1 − x∗‖2
= ‖xk−1 − x∗‖2 − 2ηk〈xk−1 − x∗,∇f(xk−1)〉 − 2ηk〈xk−1 − x∗, bk−1〉+ η2k‖ĝk−1‖2 ≤ (1− µηk)‖xk−1 − x∗‖2 − 2ηk(f(xk−1)− f∗))
+ 2ηk( µ
4 ‖xk−1 − x∗‖2 +
4 µ ‖bk‖2) + η2k‖ĝk−1‖2.
Rearrange and we get
f(xk−1)− f∗ ≤ η−1k − µ/2
2 ‖xk−1 − x∗‖2 − η−1k 2 ‖xk − x∗‖2 + 4 µ ‖bk‖2 + ηk 2 ‖ĝk−1‖2.
After taking expectation and apply the inequality from Lemma 2, we get E[f(xk−1)]− f∗ ≤ E [ η−1k − µ/2
2 ‖xk−1 − x∗‖2 − η−1k 2 ‖xk − x∗‖2 ] + ∑d i=1 4B 2α i τ 2−2α i µ −1 + ηkG ατ2−αi /2.
Then take ηk = 4µ(k+1) , τi = Bik 1 α and multiply both side by k, we get
kE[f(xk−1)]− f∗ ≤ µ 8 E [ k(k − 1)‖xk−1 − x∗‖2 − k(k + 1)‖xk − x∗‖2 ] + 8 ∑d i=1B 2 i k 2−α α µ−1.
Notice that ∑K k=1 k 2−α α ≤ ∫K+1 0
k 2−α α dk ≤ (K + 1)2/α. Sum over k and we get∑K
k=1 kE[f(xk−1)]− f∗ ≤ µ 8 E [ −T (T + 1)‖xT − x∗‖2 ] + 8 ∑d i=1B 2 i k 2−α α µ−1.
Devide both side by K(K+1)2 and we get
2
K(K + 1)
∑K k=1 kE[f(xk−1)]− f∗ ≤ 8 ∑d i=1B 2 i k 2−α α µ−1.
Notice that for K ≥ 1, K−1 ≤ 2(K + 1)−1. We have 2
K(K + 1)
∑K k=1 kE[f(xk−1)]− f∗ ≤ 16 ∑d i=1B 2 i k 2−α α µ−1.
The theorem then follows by Jensen’s inequality.
We can in fact also show a non-convex convergence rate: Theorem 5 (Non-convex CClip under coordinate-wise noise). Suppose we run CClip under the Assumption of 1 to obtain the sequence {xk}. Then, if f is L-smooth and possibly non-convex, with appropriate step-sizes and averaging,
1
K K∑ k=1 E[‖∇f(xk−1)‖2] ≤ 4‖B‖ 2α 3α−2 2 ( f(x0)− f(x?) K ) 2α−2 3α−2 .
Proof. This is very similar to Theorem 2, except that we use the same trick as in the proof above for Theorem 3.

heading: G LOWER BOUND (PROOF OF THEOREM 4)
text: We consider the following simple one-dimensional function class parameterized by b:
min x∈[0,1/2]
{ fb(x) = 1 2 (x− b) 2 } , for b ∈ [0, 1/2] . (1)
Also suppose that for α ∈ (1, 2] and b ∈ [0, 1/2] the stochastic gradients are of the form: g(x) ∼ ∇fb(x) + χb ,E[g(x)] = ∇fb(x) , and E[|g(x)|α] ≤ 1 . (2)
Note that the function class (1) has µ = 1 and optimum value fb(b) = 0, and the α-moment of the noise in (2) satisfies G = B ≤ 1. Thus, we want to prove the following:
Theorem 6. For any α ∈ (1, 2] there exists a distribution χb such that the stochastic gradients satisfy (2). Further, for any (possibly randomized) algorithmA, defineAk(fb + χb) to be the output of the algorithm A after k queries to the stochastic gradient g(x). Then:
max b∈[0,1/2]
E[fb(Ak(fb + χb))] ≥ Ω (
1
k2(α−1)/α
) .
Our lower bound construction is inspired by Theorem 2 of Bubeck et al. (2013). Let Ak(fb + χb) denote the output of any possibly randomized algorithm A after processing k stochastic gradients of the function fb (with noise drawn i.i.d. from distribution χb). Similarly, let Dk(fb + χb) denote the output of a deterministic algorithm after processing the k stochastic gradients. Then from Yao’s minimax principle we know that for any fixed distribution B over [0, 1/2],
min A max b∈[0,1/2] EA[Eχbfb(Ak(fb + χb))] ≥ minD Eb∼B[Eχbfb(Dk(fb + χb))] .
Here we denote EA to be expectation over the randomness of the algorithm A and Eχb to be over the stochasticity of the the noise distribution χb. Hence, we only have to analyze deterministic algorithms to establish the lower-bound. Further, since Dk is deterministic, for any bijective transformation h which transforms the stochastic gradients, there exists a deterministic algorithm D̃ such that D̃k(h(fb + χb)) = Dk(fb + χb). This implies that for any bijective transformation h(·) of the gradients:
min D Eb∼B[Eχbfb(Dk(fb + χb))] = minD Eb∼B[Eχbfb(Dk(h(fb + χb)))] .
In this rest of the proof, we will try obtain a lower bound for the right hand side above.
We now describe our construction of the three quantities to be defined: the problem distribution B, the noise distribution χb, and the bijective mapping h(·). All of our definitions are parameterized by α ∈ (1, 2] (which is given as input) and by ∈ (0, 1/8] (which represents the desired target accuracy). We will pick to be a fixed constant which depends on the problem parameters (e.g. k) and should be thought of as being small.
• Problem distribution: B picks b0 = 2 or b1 = at random i.e. ν ∈ {0, 1} is chosen by an unbiased coin toss and then we pick
bν = (2− ν) . (3)
• Noise distribution: Define a constant γ = (4 )1/(α−1) and pν = (γα − 2νγ ). Simple computations verify that γ ∈ (0, 1/2] and that
pν = (4 ) α α−1 − 2ν(4 α) 1 α−1 = (4− 2ν)(4 α) 1 α−1 ∈ (0, 1) .
Then, for a given ν ∈ {0, 1} the stochastic gradient g(x) is defined as
g(x) = { x− 12γ with prob. pν , x with prob. 1− pν .
(4)
To see that we have the correct gradient in expectation verify that
E[g(x)] = x− pν 2γ
= x− γ α−1
2 + ν = x− (2− ν) = x− bν = ∇fbν (x) .
Next to bound the α moment of g(x) we see that E[|g(x)|α] ≤ γα ( x− 1
2γ
)α + xα ≤ 1
2 +
1 2 = 1 .
The above inequality used the bounds that α ≥ 1, x ∈ [0, 1/2], and γ ∈ (0, 1/2]. Thus g(x) defined in (4) satisfies condition (2).
• Bijective mapping: Note that here the only unknown variable is ν which only affects pν . Thus the mapping is bijective as long as the frequencies of the events are preserved. Hence given a stochastic gradient g(xi) the mapping we use is:
h(g(xi)) = { 1 if g(xi) = xi − 12γ , 0 otherwise.
(5)
Given the definitions above, the output of algorithm Dk is thus simply a function of k i.i.d. samples drawn from the Bernoulli distribution with parameter pν (which is denoted by Bern(pν)). We now show how achieving a small optimization error implies being able to guess the value of ν. Lemma 6. Suppose we are given problem and noise distributions defined as in (3) and (4), and an bijective mapping h(·) as in (5). Further suppose that there is a deterministic algorithm Dk whose output after processing k stochastic gradients satisfies
Eb∼B[Eχbfb(Dk(h(fb + χb)))] < 2/64 .
Then, there exists a deterministic function D̃k which given k independent samples of Bern(pν) outputs ν′ = D̃k(Bern(pν)) ∈ {0, 1} such that
Pr [ D̃k(Bern(pν)) = ν ] ≥ 3
4 .
Proof. Suppose that we are given access to k samples of Bern(pν). Use these k samples as the input h(fb + χb)) to the procedure Dk (this is valid as previously discussed), and let the output of Dk be x (ν) k . The assumption in the lemma states that
Eν [ Eχb |x (ν) k − bν | 2 ] < 2
32 , which implies that Eχb |x (ν) k − bν |
2 < 2
16 almost surely.
Then, using Markov’s inequality (and then taking square-roots on both sides) gives Pr [ |x(ν)k − bν | ≥
2
] ≤ 1
4 .
Consider a simple procedure D̃k which outputs ν′ = 0 if x(ν)k ≥ 3 2 , and ν ′ = 1 otherwise. Recall that |b0−b1| = with b0 = 2 and b1 = . With probability 34 , |x (ν) k −bν | < 2 and hence the output ν′ is correct.
Lemma 6 shows that if the optimization error of Dk is small, there exists a procedure D̃k which distinguishes between the Bernoulli distributions with parameters p0 and p1 using k samples. To argue that the optimization error is large, one simply has to argue that a large number of samples are required to distinguish between Bern(p0) and Bern(p1).
Lemma 7. For any deterministic procedure D̃k(Bern(pν)) which processes k samples of Bern(pν) and outputs ν′
Pr[ν′ = ν] ≤ 1 2 +
√ k(4 ) α α−1 .
Proof. Here it would be convenient to make the dependence on the samples explicit. Denote s(ν)k =( s (ν) 1 , . . . , s (ν) k ) ∈ {0, 1}k to be the k samples drawn from Bern(pν) and denote the output as
ν′ = D̃(s(ν)k ). With some slight abuse of notation where we use the same symbols to denote the realization and their distributions, we have:
Pr [ D̃(s(ν)k ) = ν ] = 1 2 Pr [ D̃(s(1)k ) = 1 ] + 1 2 Pr [ D̃(s(0)k ) = 0 ] = 1 2 + 1 2 E [ D̃(s(1)k )− D̃(s (0) k ) ] .
Next using Pinsker’s inequality we can upper bound the right hand side as:
E [ D̃(s(1)k )− D̃(s (0) k ) ] ≤ ∣∣∣D̃(s(1)k )− D̃(s(0)k )∣∣∣ TV ≤ √ 1 2 KL ( D̃ ( s (1) k ) , D̃ ( s (0) k )) ,
where |·|TV denotes the total-variation distance and KL(·, ·) denotes the KL-divergence. Recall two properties of KL-divergence: i) for a product measures defined over the same measurable space (p1, . . . , pk) and (q1, . . . , qk),
KL((p1, . . . , pk), (q1, . . . , qk)) = k∑ i=1 KL(pi, qi) ,
and ii) for any deterministic function D̃,
KL(p, q) ≥ KL(D̃(p), D̃(q)) .
Thus, we can simplify as
Pr [ D̃(s(ν)k ) = ν ] ≤ 1
2 +
√ k
8 KL(Bern(p1),Bern(p0))
≤ 1 2 +
√ k
8 (p0 − p1)2 p0(1− p0)
≤ 1 2 +
√ k(γ )2
4γα
= 1
2 +
√ k ( 4(2−1/α) ) α α−1 .
Recalling that α ∈ (1, 2] gives us the statement of the lemma.
If we pick to be
= 1
16k(α−1)/α ,
we have that 1
2 +
√ k(4 ) α α−1 < 3
4 .
Given Lemmas 6 and 7, this implies that for the above choice of ,
Eb∼B[Eχbfb(Dk(h(fb + χb)))] ≥ 2/64 = 1
214k2(α−1)/α .
This finishes the proof of the theorem. Note that the readability of the proof was prioritized over optimality and it is possible to obtain significantly better constants.

heading: H A COMPARISON WITH (SIMSEKLI ET AL., 2019)
text: We are not the first to study the heavy-tailed noise behavior in neural network training. The novel work by Simsekli et al. (2019) studies the noise behavior of AlexNet on Cifar 10 and observed that the noise does not seem to come from Gaussian distribution. However, in our AlexNet training with ImageNet data, we observe that the noise histogram looks Gaussian as in Figure 6(a, b). We believe the difference results from that in (Simsekli et al., 2019), the authors treat the noise in each coordinate as an independent scaler noise, as described in the original work on applying tail index estimator. We on the other hand, consider each the noise as a high dimensional random vector computed from a minibatch. We are also able to observe heavy tailed noise if we fix a single minibatch and plot the noise in each dimension, as shown in Figure 6(c). The fact that noise is well concentrated on Cifar is also observed by Panigrahi et al. (2019).
Furthermore, we used the tail index estimator presented in Simsekli et al. (2019) to estimate the tail index of noise norm distribution. Though some assumptions of the estimator are not satisfied (in our case, the symmetry assumption; in Simsekli et al. (2019), the symmetry assumption and independence assumption), we think it can be an indicator for measuring the “heaviness” of the tail distribution.

heading: I ACCLIP IN IMAGENET TRAINING
text: For completeness, we test ACClip on ImageNet training with ResNet50. After hyperparameter tuning for all algorithms, ACClip is able to achieve better performance compared to ADAM, but worse performance compared to SGD. This is as expected because the noise distribution in ImageNet + ResNet50 training is well concentrated. The validation accuracy for SGD, ADAM, ACClip are 0.754, 0.716, 0.730 respectively.

Review summaries:
This paper demonstrates empirically that the gradient noises of SGD with ResNet and Adam with Bert are different: one is well-concentrated, while the other one is heavy-tailed. The paper claims that this difference costs the failure of SGD on training Bert. Furthermore, the authors proposes gradient clipped SGD and its adaptive version ACClip. Experiments show that ACClip outperforms Adam on training Bert.