Why ADAM Beats SGD for Attention Models	
Authors: Jingzhao Zhang
Sai Praneeth Karimireddy
Andreas Veit
Seungyeon Kim
Sashank J Reddi
Sanjiv Kumar
Suvrit Sra
Venue:  (2020)
Keywords: Optimization
ADAM
Deep learning

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.

Under review as a conference paper at ICLR 2020
WHY ADAM BEATS SGD FOR ATTENTION MODELS
Anonymous authors
Paper under double-blind review
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 pa- per, we provide empirical and theoretical evidence that a heavy-tailed distribution 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 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 's strong perfor- mance under heavy-tail noise settings. Finally, we show that the proposed ACClip outperforms Adam for both BERT pretraining and finetuning tasks.
INTRODUCTION
Stochastic gradient descent (SGD) is the canonical algorithm for training neural networks (Rob- bins & 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 al., 2017) in many traditional tasks including ImageNet classification (see Fig- ure 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 per- parameter learning rates. For instance, consider the task of training an attention model (Vaswani al., 2017) using BERT (Devlin 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- 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 Gaussian, the distribution for BERT seems be heavy-tailed.
In this work, we perform a rigorous theoretical and empirical study of the convergence of optimiza- tion 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 fact implicitly have such clipping behavior, thereby providing explanation for their superiority to SGD 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

---

Under review as a conference paper at ICLR 2020
BERT pretraining
ImageNet with ResNet50
3.5
SGD momentumn
3.5
SGD momentum
ADAM
ADAM
Validation loss
3.0
3.0-
Validation
2.5
2.5-
2.0
1.-
1.5
0.5
2.0
0.25
1.00
Iterations
1c2
Iterationn
1e5
(a)
(b)
Figure 1: (a) Validation loss for BERT base pretraining. Although hyperparameters for SGD momen- tum are finetuned, a large performance gap is still observed between SGD and Adam. (b) Validation loss for ResNet50 trained on ImageNet. SGD momentum outperforms Adam
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- -iite clipping thresholds can be significantly faster than using a single global one. This can explain the superior perfor- mance of Adam BERT pretraining.
Inspired by our theoretical analysis, propose novel adaptive-theeshold coordinate- wise clipping algorithm and experimentally show that it outperforms Adam on BERT training tasks.
1.1 RELATED WORK
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). Re- cently, there has been surge in interest to study the theoretical properties of these adaptive gradient methods due to (Reddi et al., 2019), which pointed out the converggeeee of Adam and proposed an alternative algorithm, AMSGrad. Since then, many works studied different interesting aspects of adaptive methods,
(Ward et al., 2018: 8; Li & Orabona, 2018; Zhou et al., 201 Sa; Staib al., 2019; Chen et al., 2018; Zou & Shen, 2018; Zhou et al., 201 8b; Agarwal et al., 2018; 8; Zou et al., 2019). Another direction of related work normalized gradient descent, which has been studied for quasi- convex and non-convex settings (Levy, 2016; Hazan et al., 2015; Zhang et al., 2019). In contrast 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 distribu- tions in neural network training. To our knowledge, Simsekli 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 devia- tions in each coordinate scaler noises to estimate tail index. Second, we focus convergence of optimization algorithm, the original paper focus on Langevin dynamics and consistence of the index estimator. More experiment comparison is in Appendix H.
HEAVY-TAILED NOISE IN STOCHASTIC GRADIENTS
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, focus 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.
2

---

Under review as a conference paper at ICLR 2020
Estiateed varsnce
0.03
0.02
0.112
0.00
0.32
0.34
1.4
1.6
No norm
Goussian
Sample
107
(a) ImageNet training
Synthetic Gaussian
(c) ImageNet emp, variance
0.04
0.075
Extirated variance
0.03
Denats
1500
0.02
0.01
0.000
10 Lecy-stable
Sample
le/
(d) Bert pretraining
(e) Synthetic Levy-stable
(f) Bert empirical variance
Figure 2: (a) Histogram of sampled gradient noise for ResNer50 using Imagenet dataset. (b) His- togram of samples from sum of squared Gaussians.
(c) Estimated variance the stochastie gra- dient for Resnet50. (d) Histogram of sampled gradient nosie for BERT using Wikipedia+Bookke Books dataset. (c) Histogram of samples from a sum of squared a-stable random variables. (l) Estimated variance of the stochastic gradient for BERT model.
We first investigate the distribution of the gradient noise norm 11g Vf(x)) in the aforementioned neural network models, where g is the stochastic gradient computed from minibatch sample. Fig- ure 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, normalized sum of squared Gaussians, a well-concentrated distribution, and a Levy-a-stable distri- bution, 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.
plot distributions of
To support this observation, in Figure (c) and (f) we further show the empirical variance of stochas- tic 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 10".
Figure 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.
2.1 OPTIMIZATION PROBLEM SETUP
We now formalize the optimization setup with heavy-tailed noise. Neural network training can be seen as minimizing a differentiable stochastic function fax (z, E)], where f Rd - R can be potentially nonconvex. At each iteration, we assume access to an unbiased stochastic gradient ((x) (z [ corresponding to the parameters æ, and also assume finite moment.
Assumption (Existence of a moment). There exists positive real numbers a E (1, and G >> O such that for all x, [[] < Go.
Note that it is possible that the variance of g(z) is unbounded while simultancously satisfying the above assumption for a < 2, c.g. the Pareto distribution. Hence Assumption much weaker than the standard bounded second moment assumption. The possibility that the variance could be unbounded has profound impact on the optimization process. In particular, previous convergence proofs for SGD fail and the algorithm may diverge (see Appendix A). As 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 taived noise.
3

---

Under review as a conference paper at ICLR 2020
3 CLIPPED GRADIENT DESCENT AND ACCLIP ALGORITHM
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 AWD- LSTM whereas Devlin et al. (2018) use clipped Adam to pretrain BERT. The general form of clipped gradient descent outlined in Algorithm
Algorithm A general framework for clipped gradient descent
1: z, mg f- 0
2: for = 1. do
3: my 31m=-1 + (1 91)9
4: Gh + clip( mz)
5: 3h f- Ik-1 Ij:0k
return иk, where random variable K is supported on (1..... T).
Perhaps the two most natural candidates for clipping mechanisms are Global CLiPping where single global threshold used and Coordinate-wiss CLIPping using d coordinate-wis thresholds
GClip(TTe, m&) = min 7k
||a|| 1 m for тк E Rg0 or,
(GClip)
CClip(TTe, mp) = min |m 1 Jms for ты. E R
(CClip)
where all operations for CClip are performed element-wise. Smaller threshold values of т imply smaller variance, but also higher bias. If the noise distribution is very heavy-tailed (or has large variance), one could compensate by picking a smaller threshold. See Theorems and 2 for a theo- retical 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-tailes and consequently converge faster (see Theorem 3).
However, to perform such coordinate-ve -wite variance-bias trade off optimally would require tuning all thresholds, which could be extremely large in deep learning. Even if tuning were feasible, the noise distribution may be non-stationary and significantly vary training progresses (see Fig. 5). To address this challenge, we propose Adaptive Coordinate-wise CLIPping, which adaptively sets the thresholds for each coordinate
ACClip(TT: m²) = min |mmelte 1)mp
= -2TE + (1- 32)lgx1
(ACClip)
where operations are element-wise, is a small number for numerical stability, and we set a by default. The of coordinate-wist a-moment (as opposed to the traditional second moment) is motivated by our theory and estimates B = Fllg || 1/aa in Assumption 2. Since [[]96]] is increasing in a 2 1, using a 1 is conservative bound on B when the true a unknown.
ADAM AS AN ADAPTIVE CLIPPING METHOD
We study Adam without momentum, i.e. R.MPProp, and show that it resembles coordinate-wind clipping. When 31 = O, we can rewrite the update for Adam and ACClip as SGD with effective step-sizes hAdum and hetip respectively
Tk+1 3kk
et (2
=: Th h Adamm and
Tk+1 Given any of parameters for RMSProp, if we the parameters for ACClip as
Fk 7i8 min(
Th gel
13 g
=: 2g heipg
c and Tk
ctv -T-
then hetip 5 h.daam < 2heip. Thus, the two differ by at most af factor of 2 and Adam can be seen as ACClip where Th is set using lik. which estimates IF [[g 12 and correspondingly decreasing
4

---

Under review as a conference paper at ICLR 2020
Table 1: Error bounds after iterations: Define a-moment [[lg(=)]11 G (Assump 1) and coordinate-wise moments [ & B (Assump 2), which satisfy G I d d|| In the stan- dard setting (a = 2), GClip recovers the optimal rates of SGD. For heavy-tailed noise (a (1, GClip converges both for convex (Thm 1) and non-convex functions (Thm 2), whereas the proof for SGD fails, denoted as N/A. Under a more fine-grained noise model, CClip has better convergence rates (Thm 3). We also show matching lower-bounds for all E (1, proving the optimality of clipping methods (Thm 4).
Strongly Convex Function
Non-Convex Function
Heavy-tailed noise (a (1,
Standard noise
Heavy-tailed noise (a (1,2))
Standard noise (a 2 2)
(a 2 2)
SGD
N/A
O
N/A
O +
GClip
O O h -
0(G2k-1)
O G
20 -2ta-1) 3a
Ba-2
O(G-
CClip
O B 2
2(a-11
011111kk-1
{
O (11BBl22+
Lower-bound
(K
((K-1)
step-size. This clipping effect can explain the faster convergence of Adam for training attention models in the presence of heavy-tailed noise (Fig. la). In contrast to Adam, ACClip (with 1) uses a simpler update scheme where т is set using an estimate of Ellgk] | and a constant step-size. This allows ACClip to take larger steps than Adam and hence converge slightly faster (Section 5).
THEORETICAL ANALYSIS
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, study when and why coordinate-wis wise clipping (CClip) outperforms global clipping (GClip). Finally, show that (upto numerical constants) clipping is optimal strategy under the strongly convex setting. Together, these provide a comprehensive analysis of the effect of clipping and strong theoretical motivation for using it whenever one suspects the presence of noise with unbounded variance. Our results are summarized in Table I, and all proofs are relegated to the Appendices.
4.1 CONVERGENCE OF GLOBALLY CLIPPED SGD
We state the rates for strongly-convex functions and for smooth non-convex functions. We focus on GClip with momentum = 0, under the assumption In the strongly convex case, we can prove the following rates of convergence to the optimum.
Theorem (Strongly-convex convergence). Suppose that f is a μ-strongly convex function and the noise satisfies assumption 1. Then let {ox} be the iterates of Algorithm I using GClip, clip- ping parameter Tk Gka-1 and steps-size T]k p(k+I] Define the output to be a j-weighted
combination of the iterates: 3g = Ej jzz () Then the output I& satisfies:
16G2
- plk + 1)2/a-1)//-
Observe that when = 2 and with bounded second moment, we recover exactly the optimal SGD rate of (G2
(G22/uk) /uk) of Lacoste-Julien al. (2012). For any other a E (1, 2), the performance of GClip gracefully degrades. As we will later show, this rate is in fact optimal for every E (1, 2]. In contrast, SGD can be arbitrarily bad when a < (see Appendix A). We can also prove rates of convergence stationary point for smooth non-convex functions.
Theorem 2 (Non-convex convergence). Suppose that f is possible non-convex L-smooth function and the noise satisfies assumption 1. Then let } be the iterates of Algorithm using GClip with momentum 3 O. constant step-size The [[ ((((K+1)) 3
and constant clipping
parameter Th G. Then, the sequence {xx} satisfies
5

---

Under review as a conference paper at ICLR 2020
20-2
2a
(fxo)
f(x*)
3x
4G 3G-o-2 30-2 Σ [[[
K
The rates of convergence for the non-convex case in Theorem 2 exactly match those of the usual SGD rates of ((1/V)) when a = and gracefully degrades for a E (1,2). Thus, GClip converges for both convex and non-convex functions under Assumption 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 significantly better convergence rate when compared to GClip.
4.2 BENEFITS OF COORDINATE- WISE CLIPPING
We had previously assumed a global bound on the a-moment of the norm of the stochastic gradient 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 (Coordinate-wise moment). Denote (g((x)) to be the coordinate-wist gradients for i E [d. We assume there exist constants [B:) 2 0 and a E (1,2) such that Ellg: B;
For the sake of convenience, we denote B = [B B2; Bal E R |B]I. C B/ Under this more refined assumption, we can show the following corollary:
Corollary (GClip under coordinate-wise noise). Suppose we run GClip under the Assumption of 2 to obtain the sequence {. Then, if is p-strongly convex, with appropriate step-sizes and averaging, the output Σy satisfies
16d B -[(=)) p + 1)2 1)/a
Thus, the convergence of GClip can have a pretty strong dependence 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-wist noise). Suppose we CClip under the Assumption 2 with Tą = Bka to obtain the sequence {ax} }- Then, if is p-strongly corvex, with appropriate step-sizes and averaging, the output Ty satisfies
16||
E[S(#x) f(=")))-((>>>> M + 2aa-a/
Note that ||B||2 S [|a. Hence CClip has a worst-case convergence independent of d under the coordinate-win 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-we wise clipping can adapt to different B; in each coordinate; the global L2 clipping does not align with the geometry of coordinate-wist noise. Although we only compare upper-bounds here, when the noise across coordinates independent the upper bounds here may be tight (see Lemma 4). Further, our experiments where d >> n lover-parameterizee models) also empirically confirms superior performance of coordinate-
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.
4.3 AN INFORMATION THEORETIC LOWER ROUND
We show a strong bound for simple class of one-dimensional quadratic functions with stochastic gradients satisfying [l < 1. This matches the upper bounds of Theorems and 3 for strongly-convex functions, showing that the simple clipping mechanism of Algorithm is (up to constants) information theoretically optimal, providing a strong justification for its use.
Theorem 4. For any E (1,2] and any (possibly randomized) algorithm A, there exists problem which is I-strongly convex and I-smooth (μ and I, 1), and stochastic gradients which satisfy Assumptions I and 2 with G, B|] < 1 such that the output as of the algorithm A after processing k stochastic gradients has an error
Elf(xx)] - f(x*) 2 1
1
(12la-11/a)

---

Under review as a conference paper at ICLR 2020
Validation loss BERT pretraining
Figure 3: Validation loss for BERT hase pre- training with the sequence length of 128. While there remains a large gap between non-adaptive methods and adaptive meth- ods, 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.
3.5
SGD momentum
Clipped SGD momentum
ADAM
ACClip
2.5
1.5
50000
100000
150000
200000
Iterations
Table 2: BERT pretraining: Adam vs ACClip. Compared to Adam, the proposed ACClip algo- rithm achieves better evaluation loss and Masked LM accuracy for all model sizes.
BERT Base layers
BERT Base 12 layers
BERT Large 24 layers
Val. loss
Accuracy
Val. loss
Accuracy
Val. loss
Accuracy
Adam
1.907 1.877
63.45
1.718 1.615
66.44
1.432 1.413
70.56
ACClip
63.85
67.16
70.97
5 EXPERIMENTS
We perform extensive evaluations of ACClip BERT pre-training and fine-tuning tasks and demon- strate its advantage over Adam in Section 5.1. Since ACClip was explicitly designed to tackle heavy- tailed 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.
5.1 PERFORMANCE OF ACCLIP FOR BERT PRE- TREAIIIN AND FINE-TUNING
We evaluate the empirical performance of our proposed ACClip algorithm BERT pre- pre-training as well fine-tuning using the SQUAD v1.1 dataset. As a baseline, we use Adam optimizer and the same training setup in the BERT paper (Devlin et al., 2018). For ACClip, we set lr 1 10 81 0.9, B2 = 0.99, e = 1 x 10-5 and wd = 1 x 10 We compare both setups on BERT models of three different sizes, BERT base with 6 and 12 layers well BERT with 24 layers.
Figure 3 shows the validation loss for pretraining BERT 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 further shows that ACClip achieves lower loss and higher masked-LM accuracy for all model sizes.
Next, we evaluate ACClip on the SQUAD vI.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 Fl as well as for exact match, the proposed algorithm outperforms Adam on all model sizes.
The experimental results BERT pretraining and fine-tuning indicate the effectiveness of the pro- posed algorithm. The increasing clipping threshold during the training is motivated by our theoreti- cal analysis indeed helps with empirical performance by reducing the bias in gradient estimators.
5.2 NOISE PATTERNS IN NEURAL NETWORK TRAINING
In the following experiment, 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 ResNet-like model on both Wikipedia and synthetic Gaussian data. We used BERT Base 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 nor- malized Gaussian input. The resulting noise histograms are plotted in Figure 4. From the figure,
7

---

Under review as a conference paper at ICLR 2020
SQUAD v1.1 dev set: Adam ACClip. The mean and standard deviation of Fl and exact match score for 5 runs. The first row contains results reported from the original BERT paper, which are obtained by picking the best ones out of 10 repeated experiments.
Table 3:
BERT Base layers Fi
BERT Base layers
BERT Large layers
EM
EM
F1
EM
F1
Adam (Devlin al.,
80.8
88.5
84.1
90.9
Adam
76.85 0.34
84.79 + 0.33
81.42 = 0.16
88.61 + 0.11
83.94 + 0.19
90.87 0.12
ACClip
78.07 0.24
85.87 1 0.13
81.62 1 0.18
88.82 1 0.10
84.93 1 0.29
91.40 0.15
0.03
Deyaie
8.03
Denzre
0.04
Densre
0.04
Denuty
0.02
0.02
0.02
0.0L
0.00
20
40
60
80
0.00
0.00
60
0.27
0.28 0.25 0.30 033
(a) Attention Wikipedia
(b) Attention Gaussian
(c) Resnet Wikipedia
(d) Resnet + Gaussian.
Figure 4: Noise distribution Attention and ResNet on two data sources: Wikipedia and synthetic Gaussian. The noise pattern is from the interaction of both architecture and data distribution.
heavy-tailed noises 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 be heavy-tailed. Therefore, the noise pattern results from both the model architecture as well as the data distribution.
Figure shows how the distribution of gradient noise is evolving during training. The results high- light 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 accelerate optimization.
20.000
0.050
0.050
0.08
0.022
0.025
0.025
0.00
0.000
50
0.000
100
309
0.000
0.000
g Noise norm
Noise norm
Noise
Notse norm
(a) Development of noise distribution during BERT training.
Iteration
10k
60k
0.04
0.04
0.
0.04
Denetty
0.7
SA
e,575
0,500
Noise 0.575
0.500
0,525
0,500
1.99
10
Noise norm
Noise
Neise nom
(b) Development of noise distribution during ResNet50 training ImageNet.
Figure 5: The distribution of gradient noise is non-stationary during BERT training, while it remains almost unchanged for ResNet training on ImageNet.
CONCLUSION
Our work theoretically and empirically ties the advantage of adaptive methods over SGD to the heavy-tailed nature of gradient noise. A careful analysis 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 training. We believe additional such investigations into the source of the heavy tailed-ness, well as a characterization of the noise in other scenarios where Adam is used (e.g. GAN training or reinforcement learning) can lead further insights with significant impact practice.
the structure of the noise in understanding neural network
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, and Yi Zhang. The case for full-matrin adaptive regularization. arXiv preprint net::18860099958 2018.
Larry Armijo. Minimization of functions having Lipschitz continuous first partial derivatives. Pacific Journal of mathematics, 1--1 1966.
Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEEE Trans- actions on Information Theory, 59(1 1)77711-7777, 2013.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. arXiv preprint arXiv: 18080091,,.0291,, 02941, 2018.
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep
bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 2018.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120ul):2121-2159, 2011.
Elad Hazan, Kfir Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex opti- mization. In Advances in Neural Information Processing Systems, pp. 1594-1602, 2015.
Diederik P Kingma and Jimmy Ba. ADAM: A method for stochastic optimization. arXiv preprint arXiv:14/2.6990, 2014.
Simon Lacoste-Julien, Mark Schmidt, and Francis Bach. A simpler approach to obtaining an o (I/t) convergence rate for the projected stochastic subgradient method. arXiv preprint 102iv:1212.2002, 2012.
Kfir Y Levy. The power of normalization: Faster evasion of saddle points. arXiv preprint arXiv: 1.04831, 2016.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. arXiv preprint arXiv:/805.008 1805.08/ 14, 2018.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM language models. In International Conference on Learning Representations, 2018. URL https: / //openzeview. wwwppereeiww.et/eoooroeooeeeeeee dya.rrmmmdddyyyyyoo2...
Abhishek Panigrahi, Raghav Somani, Navin Goyal, and Praneeth Netrapalli. Non-gaussianity of stochastic gradient noise. arXiv preprint 1rXiv:1910.09626, 2019.
Boris T Polyak. Introduction to optimization. optimization software. Inc., Publications Division, New York, 1, 1987.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of ADAM and beyond. arXiv preprint 1tXiv:1904.092.37 2019.
H. Robbins and S. Monro. A stochastic approximation method. Annals of Mathematical Statisties, 22:400-407, 1951.
Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. arXiv preprint arXiv:1901.0600 2019.
Matthew Staib, Sashank Reddi, Satyen Kale, Sanjiv Kumar, and Suvrit Sra. Escaping saddle points with adaptive gradient methods. arXiv preprint 1rXiv:1901.09145 2019.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26 31, 2012.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 1998-6008. 2017.

---

Under review as a conference paper at ICLR 2020
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence landscapes, from any initialization. arXiv preprint arXiv:1806.0181,, 2018.
Ashia C Wilson, Rebecca Roelofs, Mitchell Ster,, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4148-4158, 2017.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Analysis of gradient clipping and adaptive scaling with relaxed smoothness condition. arXiv preprint arXiv: 1881, 2019.
Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv: arXiv: 2018a.
Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, and Yong Yu. Adashift: Decorrelation and convergence of adaptive learning rate methods. arXiv preprint arXiv:1810.00143, 2018b.
Fangyu Zou and Shen. On the convergence of weighted adagrad with momentum for training deep neural networks. arXiv preprint arXiv: 1808 03400, 2018.
Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for conver- gences of adam and rmsprop. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 11127-11135, 2019.
10

---

Under review as a conference paper at ICLR 2020
A NECESSITY OF ADAPTIVITY AND NON-CONVERGENCE OF SGD
Consider a simple toy function f(x) = د all with an optimum value of 0 achieved at x² Suppose that receive stochastic gradients g(x) with potentially unbounded variance ie.. [[]]g())) V f=)) = co. Then, starting from Zo = 0, let us run SGD (possibly with momen- tum) using with arbitrary but fixed step-sizes i.e. the step-sizes are predetermined and do not depend on the stochastic gradients. The output Zy is then simply a linear combination of {9(T)))isR with
some (fixed) weights (1) E R)jsk
PK bg((z))
The the expected function suboptimality at 2g can be lower bounded as follows
|
E[f(xx)] - f(a) E|||= all2
Elll a4 E[xx]]
Σ no (o(()))) -()())
The last term in the above expression is the variance of sum of A: independent random variables and My are fixed constants. We can then simplify
Elg(z,))) |
E Σ (o(a))
Σ 7 [l)(())) E[g(z;)))
E n maxje(4] ([)o(()))) [[
This implies that if there is any i.j < & such that v > 0 and (l)))()))) - V f((z)]] = we have [xxx] = oo! Thus, the solution provided by SGD can be arbitrarily bad when the domain
is unbounded.
was important 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 being necessary when dealing with heavy-tailed noise.
B ADDITIONAL DEFINITIONS AND NOTATION
Here we describe some of the formal definitions which were previously skipped. Definition 3 peestrong-convexity f is u-strongly convex, if there exist positive constants p. such that's Vx.
11 f(v) 2 f(x) + (VI(x) x) 5 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 Vx, y.
L
(w) < f(x) (VS(z), x) Ily 2
Note that the above definitions together imply that μ < L.
C EFFECT OF GLOBAL CLIPPING ON VARIANCE AND BIAS
We focus on (GClip) under stochastic gradients which satisfy Assumption 1.
Lemma 2. For any g(x) suppose that assumption holds with (1,2). Then the estimator from (GClip) with global clipping parameter т 2 satisfies:
E [1 & -- and [F]]())) - 2 < 2 2(aa)11
11

---

Under review as a conference paper at ICLR 2020
Proof. First, bound the variance.
[] E[16(=)1
By the fact that ((x) I T, we get
=
500 2072-a.
Next, we bound the bias,
[[[](=)] - ([((]) 2(x)]]
s { - - -
(()))
< <[[]o((>)]]<<0d)))=>) - [1 (a-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, can carefully trade-off the variance of our estimator against its bias, thereby ensuring convergence of the algorithm.
D STRONGLY-CONVEN RATES (PROOF OF THEOREM 1)
For simplicity, we denote ÿR (2rk( and the bias by Elgn] (((x)).
|| x x²1 = || - m69k-1 x²11
|| x²11 - 21/1 21 xx, v[(xk-1))
2mp (DX-1 xx, 1x + n 9 1|
S (1 wi7k) 11:8) x=1 2 21F (s [(*k-1) ))
4 |b> 2 + n 19k- 11
2M 4 11 x2 +
1121-1--
Rearrange and we get
1(xx-))- S 1h 112 2
| -
x²11
Th 2
- x² x²1 122 + =|bbal 1|2
+
Th
-100=-11
2
After taking expectation and apply the inequality from Lemma 2, we get
Elf( 1/p
u12
| - x=" x=112= 7k
|| - x =²1
2
2
+ _ 20 1 + m/ 20022a11
Then take #(6+1] = G and multiply both side by k. we get
kE[f(z)11] - ft < 4 E [k((k
1) x² k(k 1))l x=1 [²]
+ 8 2-0 1
Notice that Σk 2- S So kK k 2ي dk S (K + 1)2/0 Sum over i and we get
Σ kE[s ) f"
K
E[- + 1)[l=T [13]
8
8 + 1
Devide both side by K(K-1) and we get
2
2
ΣK kE(f( - - 1) 20 n-1
K(K +
Notice that for K > 1, K
< 2(K + 1 We have
2
ΣK ME f* +1) 2-20
K(K +
The theorem then follows by Jensen's inequality.
12

---

Under review as a conference paper at ICLR 2020
E NON-CONVEX RATES (PROOF OF THEOREM 2)
For simplicity, we denote IR 0()x-1) and the bias by = [[ - Vf(xx). By Assumption 4, we have
f(xx) S f(2x-1) (((r--))(((((x-/))) TA9A)) + TEL
11
2
[(x-1)) 7/6 / (3x 7h ( (V/ (I 1),b))))) bx)) + v [ ||
2
L
$ (1)=-1) 7/6 / |)| 7 V (2 1), bx) +
| 11
2
< {(x=-1) 1/6 V 11]
V (x ))|
7k
||xx||
+
T
11 11
2
2
Here the last step used the AM-GM inequality. Then, taking expectation in both sides and using Lemma 2 gives
1 T 2-a
G2
E[f(x)))==-1) f(x=-1)
AK 2
[V
2
272a-2
Rearrange and sum the terms above for some fixed step-size {M- = 7) and threshold fTh = r} get
to
K
2 (f(z)) - =[]((x))) + 1LG 2-a
G
[[V
K
n
720-2
G2a
(f(zo) - f) + tLLGa 2- -2a
nk
Th
12
Since threshold
G
can simplify T2 as
(gL)a
G
2G2x
20 (n)))
22--2
72a-2
Denote fo = f(x) - f* to ease notation. Then, adding T/ back to Ti and using a step-size
1
(//x 30-2
30-2
we get
Ti + T2
2fo n
+ (nL(
20-2
4fo n₁K
4G 30-3
Lfo K
This proves the statement of the theorem.
F EFFECT OF COORDINATE- WISE MOMENT BOUND
We now examine how the rates would change if replace Assumption with Assumption 2.
F.1 CONVERGENCE OF GCLIP (PROOF OF COROLLARY 1)
We now look atCClip under assumption 2. We can in fact also prove the following corollary for the non-convex case:
Corollary (Non-convex GClip under coordinate- wise noise). Suppose we run GClip under the Assumption of to obtain the sequence {xx) Then, if is L-smooth and possibly non-convex, with appropriate step-sizes and averaging.
2n 2
2a
(f(z) - -((x))
3a-2
30-2 ( = 30-2
K
K
13

---

Under review as a conference paper at ICLR 2020
The proof of both the convex and non-convex rates following directly from the following Lemma.
Lemma 4. For any g(z) suppose that assumption with a E (1,2). Then suppose we have a constant upper-bound
Ellg(()]| D.
Then D satisfies
d BB I D - d² Bla
Proof. Note that the function (.)a/2 is concave for E (1, Using Jensen's inequality we rewrite as:
a/27
2 E[]l(())) da/2E
l0(o))00p
da/2-1E
Σ 1010))
Since the right hand-side can be large d | we have our first inequality, On the other hand, we also have an upper bound below:
[l[g(()) =F ( 10(p))pp)))
a/27
(d(máx i=1
8/2)
S
d Σ (o(a))
d I dd/2
S E 22 (max (z) (1)g
< da/2
Σ
B
1=1
2=
where |B||a
Σ 1i=1 B Thus, have shown that d B S Elllg())](*) 11
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 more complicated manner or are independent of each other.
Substituting this bound on G in Theorems and 2 gives our corollaries.
F.2 CONVERGENCE OF CCLIP (PROOF THEOREM
The proof relies on the key lemma which captures the bias-variance trade off under the new noise- assumption and coordinate- wise clipping.
Lemma 5. For any g(x)) suppose that assumption 2 with (1, 2] holds. Denote gi to be ish component of g(z). fz)x to be in component of f(x). Then the estimator g(x) = [91: - Gal from (CClip) with clipping parameter [1i: TTa] satisfies:
E [119,117] < 7 and [| - [()))] < T 1 2(a-1)
Proof. Apply Lemma to the one dimensional case each coordinate.
Proof of Theorem 3. Theorem
For simplicity, we denote 9& nar(vx) and the bias by [[gh]
V (Ir.).
| x x=
|| 1 1)9 2²1
||ak-1 - 2111 21 ( - x", vf(Ik-1))
21/6 (D0--1 - x² bx-1) + n/ 11 112
< (1 (1T 11 - x²1 /²= 2n (f - f*))
27/6 (1) || - x²
4
| 11 + n 11 -
4
14

---

Under review as a conference paper at ICLR 2020
Rearrange and get
f(x-1)- 1h -1/2
|
x²1
Th +
||
x²12
-
=11bal12
112
Th
11 111?
2
2
1
2
After taking expectation and apply the inequality from Lemma 2, we get
E[[(xx-))
1/2 11/2
x=1 1/
20
x²
$12
2
+ Di= i=1 4B,a, T, 2-20 p- + G :i 2-a /2.
Then take p(k+13, To B, and multiply both side by k; we get
k- [[[[((*=1)] - 8 < M E [M<(k: 1)1 x²1 k(k + 1))laxx - x []]
+ +8 B²kk= :س
Notice that Ek= 2- S
KK-1 k 2 dk S (K + 1)2/a. Sum over it and we get
Σ kE] - <
# El [ + 1) | x [|*]
8
8 Σ
Devide both side by K(K-1) and we get
2
kk=1 kE[ -
K(K + 11)
Notice that for K 2 1, K
< 2(K + +1)-1
We have
K(K + Æ= kF
2
B
The theorem then follows by Jensen's inequality.
We can in fact also show non-convex convergence rate:
Theorem 5 (Non-convex CClip under coordinate-wise noise). Suppose we run CClip under the Assumption of to obtain the sequence {œx}. Then, f f L-smooth and possibly non-convex, with appropriate step-sizes and averaging.
1
K
(f(x0) 3n-2
3a-2
2a
f((x))
3a
20-2
K
Proof. This is very similar to Theorem 2, except that the same trick in the proof above for Theorem 3.
G LOWER BOUND (PROOF OF THEOREM 4)
We consider the following simple one- oieedimmnsi function class parameterized by
min {f((z) { -b))). for b E 1/2 zE[0.1/2]
(1)
Also suppose that for E 2] and E [0, 1/2] the stochastic gradients are of the form:
g(x) f((( X E[g(=)) (=x(),, and [[]g(=) 1.
Note that the function class (1) has = 1 and optimum value (b) = O, and the a-moment of the noise in (2) satisfies G B 1. Thus, we want to prove the following:
15

---

Under review as a conference paper at ICLR 2020
Theorem 6. For any (1,2) there exists distribution X such that the stochastic gradients
satisfy (2). Further, for any (possibly randomized) algorithu A, define As(fo + Xb) to be the outuu of the algorithm A after & queries the stochastic gradient g(z). Then:
max (lf + xx)) 2 12(n-1)/0 1)/o (0,0///2]
Our lower bound construction is inspired by Theorem 2 of Bubeck et al. (2013). Let A& + xt) denote the output of any possibly randomized algorithm A after processing k stochastic gradients of the function fa (with noise drawn i.i.d. from distribution X+). Similarly, let D2 (ʃo + X6) denote the output of deterministic algorithm after processing the & stochastic gradients. Then from Yao's minimax principle we know that for any fixed distribution B over [0, 1/2],
min max fole (fo + xx)I 2 min Eo..ss xx))]] (0
Here we denote EA to be expectation over the randomness of the algorithm A and Ex. to be over the stochasticity of the the noise distribution Xa- Hence, we only have to analyze deterministic algorithms to establish the lower-bound. Further, since D; is deterministic, for any bijective trans- formation h which transforms the stochastic gradients, there exists a deterministic algorithm DD such that D&(h(fa + xb)) (fo + Xt). This implies that for any bijective transformation h(-) of the gradients:
min Ei E + xx))] mijn (x..iss(EE...Meeeeiiaa
+ xx))).
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 be defined: the problem distribution B, the noise distribution Xb. and the bijective mapping h(-). All of our definitions are parameterized by a (1, (which is given input) and by E (0, 1/8] (which represents the desired target accuracy). We will pick to be fixed constant which depends on the problem parameters (e.g. k) and should be thought of being small.
Problem distribution: B picks bo unbiased coin toss and then we pick
2x or bi = at random i.e. v (0. is chosen by an
by = (2 v)c.
Noise distribution: Define a constant 7 = (4e) 246)2/(a-11 and pv (7 - 2u77e). Simple compu- tations verify that y E (0, 1/2) and that
Py (4c) नं (x(( = (4
(4c) (4-22v)44c)
E (0,1).
Then, for given E (0, 1} the stochastic gradient ((x) is defined
with prob. Pa with prob. Pa.
g(x)
2
x
To see that we have the correct gradient expectation verify that
[[g())] = x
Pv
x
-0-1
+ ve = (2 - u)e = x- - b, (x).
27
2
Next to bound the a moment of g(x)) we see that
1
1 1
E[[g(z))9)
+
x
S - 1.
27
The above inequality used the bounds that a 1, [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 v which only affects p.. Thus
the mapping is bijective as long the frequencies of the events are preserved. Hence given stochastic gradient g(x;) the mapping we use is:
{
if g(x))) =x 27
h(g(z=))
(5)
otherwise.
16

---

Under review as a conference paper at ICLR 2020
Given the definitions above, the output of algorithm Di: is thus simply a function of i..d. samples drawn from the Bernoulli distribution with parameter Pv (which is denoted by Bern(pu)). We now show how achieving small optimization error implies being able to guess the value of
Lemma 6. Suppose are given problem and noise distributions defined as in (3) and (4), and an bijective mapping h((.) as (5). Further suppose that there is deterministic algorithm Dy whose output after processing k stochastic gradients satisfies
fo-:BlEx..6(DD(hhC + X6IM < /64
Then, there exists a deterministic function Di which given independent samples of Bern(p,) outputs o' =D((eer((p))) E {0, 1} such that
Pr Du (Bern(p)))) =v 3
Proof. Suppose that given access to l samples of Bern(px). Use these i samples as the input h + Xb)) to the procedure Dj (this is valid as previously discussed), and let the output of Dr be
(v) The assumption in the lemma states that
2
Eg Ex.. - b117]
which implies that Ex, |z
byl <
almost surely.
32"
16
Then, using Markov's 's inequality (and then taking square-roots on both sides) gives
Pr Pr[1ot - bvl 2 2.
-
Consider simple procedure Dr which outputs v/ = 0 x/
and v/ 1 otherwise. Recall 2 3:
2
that 160 b1l with bo 2x and b1 With probability 4. v' is correct.
(v) bul < 1 and hence the output
Lemma 6 shows that if the optimization error of Dj is small, there exists procedure Dj which distinguishes between the Bernoulli distributions with parameters po and pi using k samples. To argue that the optimization error large, one simply has to argue that large number of samples are required to distinguish between Bern(po) and Bern(pi).
Lemma 7. For any deterministic procedure (Be(nn(()))) which processes k samples of Bern and outputs v
1 + k(46)==
Pr(y' = = S =
Proof. Here it would be convenient to make the dependence on the samples explicit. Denote s 89 (1)) E 13 to be the samples drawn from Bern(p,) and denote the output as v/ (()) With some slight abuse of notation where we use the same symbols denote the realization and their distributions, we have:
Pr Pr[p(ok (2) )
1 Pr (r( ()) = Pr (0) -
- D(s
= -
Next using Pinsker's inequality upper bound the right hand side as:
E where blrv 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 (Pi....,Pt) and (g......gH). )
< -
TV S V KL (
V
( )))))
k
KL((PI..... (pI....,pp). (q.,... ..)))
(.....).......)) = Σ KL(p,, 4))
17

---

Under review as a conference paper at ICLR 2020
and ii) for any deterministic function D,
KL (KL(D()),D()))
Thus, simplify
k
Pr D(s 10) =
+
KL (Ber(((())) Bern(po))
8
k (po - p1)²
- 2
8 P Po)
k(())2
$
+
2
47
k(4(2-1//))) =
Recalling that a E (1, gives us the statement of the lemma.
If we pick e be
c= 16k(a-1)/a
we have that
+ 1= 4
Given Lemmas and 7, this implies that for the above choice of
Lo-BlEx, + xx))) 2//44 214p2(a-1)/a
This finishes the proof the theorem. Note that the readability of the proof was prioritized over optimality and it is possible to obtain significantly better constants.
H A COMPARISON WITH (SIMSEKLI ET AL., 2019)
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 AlexNet on Cifar 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 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 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).
0.03
0.20
0.02
0.02
0.01
0.01
0.05
0.00
1.50
1.55
1.35
1.35
0.00
1.3
1.25
1.30
1.35
0.00055.00c0 0000000010 0 2.00200 8.000.0030
Norm notee
Nam mohe
(a)
(b)
(c)
Figure 6: (a) Noise histogram of AlexNet ImageNet data at initialization. (b)Noise histogram of AlexNet on ImageNet data at 5k iterations. minibatch initialization.
(c) The per dimension noise distribution within a single
18

---

Under review as a conference paper at ICLR 2020
0.04
0.03
Density
Density
0..3
0.02
0.01
0.01
0.00
0.00
0.32
0.34 Noise norm
40
Noise norm
(a) ImageNet training, & 1.99
(b) Bert pretraining, à = 1.08
Figure 7: Tail index estimation gradient noise in ImageNet training and BERT training.
Furthermore, used the tail index estimator presented in Simsekli al. (2019) estimate the tail index of noise norm distribution. Though some assumptions the estimator are not satisfied (in our case, the symmetry assumption; Simsekli al. (2019), the symmetry assumption and independence assumption), we think it can be an indicator for measuring the "heaviness" of the tail distribution.
I ACCLIP IN IMAGENET TRAINING
For completeness, 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 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. 0.754, 0.716, 0.730 respectively.
ImageNet with ResNet50
3.5
SGD momentum
3.0
ADAM
Validation loss
ACClip
2.5
2.0
1.5
0.00
0.25
0.50
0.75
1.00
Iterations
1e5
(a)
Figure 8: Validation loss for ResNet50 trained on ImageNet. SGD outperforms Adam and ACClip.
19


Reviews:
[{"review_id": "HyeyJmwRFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposed a very interesting claim: When training a neural network, if the (stochastic) gradient noise is Gaussian-like, then SGD performs better than Adam; On the other hand if the gradient noise is Heavy tailed, then Adam perform better than SGD.\n\nThe paper supported this argument with experiments showing that ResNet50 on ImageNet, the noise is more like Gaussian while BERT on language learning tasks the noise is more heavy-tailed. The paper also gave a theoretical result showing that Adam converges in the regime of heavy-tailed noise. \n\n\nThe experiment finding is quite surprising to me, since many papers (see e.g. \nA Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks\n)  claim that the SGD noise is heavy-tailed for image recognization tasks such as CIFAR-10, CIFAR-100. The referred paper used rigorous statistical testing for the tail-index of the SGD noise, while this paper simply drew some image. \n\n\nMoreover, the theoretical result in this paper also worries me quite a bit, since from the bounds it seems that Adam is the dominating algorithm (both in the heavy-tail case and in Gaussian tail case). Moreover, SGD also converges in the heavy-tail noise case (by showing that the norm of x_t is not too large during the training process using martingale-based argument). Hence, the upper bound of the theoretical result is convincing enough to claim that Adam is better than SGD in certain regime. \n\n\nAfter Rebuttal: I have read the authors' responses and acknowledge the sensibility of the statement. I have higher my score: In particular, if the noise is indeed Gaussian as opposite to the \"known results\", this paper should be accepted. \n\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJgmwxsiKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper gives theoretical and empirical results for a gradient clipping variant of Adam they call ACClip.  While the theoretical analysis is rather  sophisticated and nontrivial, I personally do not believe that analyses of this form are of any value in guiding practice.  But that is a long discussion that is not specific to this paper.  The bottom line is that for me it is mainly the experimental results that matter.\n\nThe experimental results are not compelling.  It is now clear that careful hyperparameter search is critical to drawing experimental conclusions about optimizers.  This paper simply states the hyperparameters used with no discussion of hyperparameter search. I strongly believe that any claim about optimizers needs to be backed up by experiments with very careful hyper-parameter optimization.\n\nPostscript:  I have modified this review in response to the authors.  I remain unconvinced that the theory is providing anything more than an intuitive hypothesis that Adam is importance when the variance is large.  Since Adam and RMSprop are explicitly damping variance in the gradients, this intuition is reasonable even before we prove any theorems.  I still believe the theorems do not add really add anything to the intuition and it is the experiments that matter.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1llHZtRYB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper 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.\n\nIn general, the paper is well-written and has addressed an important practical and theoretical problem of why SGD fails to train Bert and how to fix this problem. The theory appears to be solid. My only concern is how generalizable ACClip is. Experiments show that it outperforms Adam on training Bert. How about the other architectures where Adam is usually applied? Is ACClip competitive to Adam in those applications? What’s the performance of ACClip on DL applications where SGD + momentum works well, such as ResNet on the ImageNet dataset?\n\nWhat is exactly \\delta f(x)? Is this the full batch gradient over all training examples? \n\nSome typos: \n1.\tPage 1: thereby providing a explanation\n2.\tPage 4: at most af factor of 2 and Adam\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tries to explain why Adam is better than sgd for training attention model. In specific, it first provides some empirical and theoretical evidence that a heavy-tailed distribution of the noise in stochastic gradients is the cause of SGD's worse performance. Then the authors studied a clipped variant of SGD that circumvents this issue, and revisited Adam through the lens of clipping. Overall, this paper conveys some interesting ideas. On the other hand, the theorems proved in this paper do not provide additional insight besides the intuition and the experiments are weak (hyperparameters are not carefully tuned). So even after author response, it still does not gather sufficient support from the reviewers. This is a borderline paper, and due to a rather limited number of papers the conference can accept, I encourage the authors to improve this paper and resubmit it to future conference.

Decision: Reject