Noise Is Not the Main Factor Behind the Gap Between Sgd and Adam on Transformers, But Sign Descent Might Be
Authors: Frederik Kunstner
Jacques Chen
Jonathan Wilder Lavington
Mark Schmidt
Venue: ICLR 2023 poster (2023)
Keywords: optimization for deep learning
adaptive methods
adam
rmsprop
sgd
sign descent
noise
stochasticity
full batch

Abstract: The success of the Adam optimizer on a wide array of architectures has made it the default in settings where stochastic gradient descent (SGD) performs poorly. However, our theoretical understanding of this discrepancy is lagging, preventing the development of significant improvements on either algorithm. Recent work advances the hypothesis that Adam and other heuristics like gradient clipping outperform SGD on language tasks because the distribution of the error induced by sampling has heavy tails. This suggests that Adam outperform SGD because it uses a more robust gradient estimate. We evaluate this hypothesis by varying the batch size, up to the entire dataset, to control for stochasticity. We present evidence that stochasticity and heavy-tailed noise  are not major factors in the performance gap between SGD and Adam. Rather, Adam performs better as the batch size increases,  while SGD is less effective at taking advantage of the reduction in noise. This raises the question as to why Adam outperforms SGD in the full-batch setting. Through further investigation of simpler variants of SGD, we find that  the behavior of Adam with large batches is similar to sign descent with momentum.

Published as a conference paper at ICLR 2023
NOISE IS NOT THE MAIN FACTOR BEHIND THE GAP BETWEEN SGD AND ADAM ON TRANSFORMERS, BUT SIGN DESCENT MIGHT BE
Frederik Kunstner, Jacques Chen, J. Wilder Lavington & Mark Schmidt University of British Columbia, Canada CIFAR AI Chair (Amii)* [kunstner, jola2372, schmidtm, ) (ecs wbc. ca ja bacquesc@students as. ubc.ca
ABSTRACT
The success of the Adam optimizer on a wide array of architectures has made it the default in settings where stochastic gradient descent (SGD) performs poorly. However, our theoretical understanding of this discrepancy is lagging, preventing the development of significant improvements on either algorithm. Recent work advances the hypothesis that Adam and other heuristics like gradient clipping outperform SGD on language tasks because the distribution of the error induced by sampling has heavy tails. This suggests that Adam outperform SGD because it uses a more robust gradient estimate. We evaluate this hypothesis by varying the batch size, up to the entire dataset, to control for stochasticity. We present evidence that stochasticity and heavy-tailed noise are not major factors in the performance gap between SGD and Adam. Rather, Adam performs better as the batch size increases, while SGD is less effective at taking advantage of the reduction in noise. This raises the question why Adam outperforms SGD in the full-batch setting. Through further investigation of simpler variants of SGD, we find that the behavior of Adam with large batches is similar to sign descent with momentum.
INTRODUCTION
Adam (Kingma and Ba, 2015) and its derivatives have been successful in training deep learning models that they have become the default optimizer for some architectures. Adam often outperforms stochastic gradient descent (SGD) by such a margin that SGD is considered incapable of training certain models, to the point of being omitted from performance comparisons (e.g. Liu et al., 2020; Anil et al., 2019). Despite this success, we still do not understand why Adam works, much less why it can outperform SGD by such a wide margin. We have made progress understanding why it should not, as the work of Reddi et al. (2018) who pointed out that Adam does not converge even on convex problems, but this does not answer why Adam outperforms SGD.
The limited effectiveness of standard theory. We usually analyse optimization algorithms under assumptions like Lipschitz continuous camction/gradieen and convexity (e.g. Nesterov, 2018, Chapters 2-3). Many works have focused on improving the analysis of Adam and its variants under those same assumptions. But these assumptions are only models of how losses behave. They do not convey the complexity of the optimization process in complex architectures, and are limited to showing that Adam does not do much worse than gradient descent (Défosscz et al., 2022; Alacaoglu et al., 2020). Analyses in online learning also struggle to illuminate the gap. The assumption that the gradients come from adversary requires decreasing step-sizes (e.g. Hazan, 2022, Thm 3.1), which decrease too quickly to perform well in practice. Our theoretical understanding is thus still limited in that we cannot describe the empirical behavior we observe-thar that Adam outperforms SGD in many settings.
As a result, there is a sentiment in the community that the success of these heuristics need not be due to robust theoretical underpinnings, but rather to social dynamics and co-evolution of deep learning architectures and optimization heuristics (see for example Orabona, 2020). These "adaptive" algorithms might actually be adapted to type of problems where they outperform SGD. But this suggests that they are leveraging some problem structure that our current theory and theory-derived algorithms missing. Understanding this structure may be key to develop better practical algorithms.

---

Published as a conference paper at ICLR 2023
MNIST
CIFAR-10
PTB
Wik
SQuAD
200
100-
500
Counts
10-
40-
100
50
250
10
5
0.1
0.2
25
30
0.7 0.8 0.9
1.0
1.2
2.5
5.0
Gradient error
Gradient error
Gradient error
Gradient error
Gradient error
10'
Training loss
10
6
10
10
10
2
4
100
10
10
10-s 100
2
10
10
0
Epoch
Epoch
100
Epoch
100
Epoch
40
Epoch
5
(m)
Adam(+m)
SGD(-m) m)
Adam( m)
Figure 1: The Heavy-TTall hypothesis: the gap between SGD and Adam is caused by a heavier tail in the distribution of the stochastic gradient error. The performance gap between SGD and Adam larger and more consistent on transformers on text data (right: PTB, Wikitext2, SQuAD) than on CNNs on image data (left: MNIST, CI), which coincides with a heavier tail in the distribution of the stochastic gradient error. J. Zhang et al. (2020b) hypothesize that heavier tails might be the cause of this gap. Top: Distribution of errors in stochastic gradients at initialization (lgg ğll where 9 is stochastic and g is a full gradient) compared against a Gaussian (QQ-plot). Bottom: SGD and Adam with and without momentum (+m//m) with small batch sizes.
The heavy-tailed assumption. Recent works have proposed alternative assumptions to model the behavior of optimizers neural networks. One such assumption comes from J. Zhang et al. (2020b), who hypothesize that the gap in performance might arise from a heavy-tailed distribution of the error induced by stochasticity. They notice larger and more consistent gap in the performance of SGD and Adam on language models than on image models, which coincides with heavier tail in the distribution of the stochastic gradient error.' We reproduce their observation in Figure 1. The proposed mechanism is that heavy-tailed errors have a larger impact on SGD than on Adam or gradient clipping. as the introduction of bias in the estimation of the gradient reduces its variance. This hypothesis suggests that a path to designing better algorithms is to improve robustness to heavy-tailed noise. For example, Gorbunov et al. (2020) combine acceleration and gradient clipping, while Srinivasan et al. (2021) leverage estimators tailored to heavy-tailed noise.
Inconsistency with large batch results. tailedness and cases where Adam outperforms SGD, and give mechanism to link heavy-tailed errors to this gap. However, the type of noise is not the only difference between image and language tasks. There is limited empirical evidence that stochasticity is the root cause of this gap. In fact, there are reasons to believe noise might not be a major contributor. For example, the lack of variance in the behavior of the optimizers on language tasks in Figure I suggests they are less sensitive to noise than image tasks. Moreover, we would expect the gap to diminish as the noise is reduced by increasing the batch size. However, methods such LAMB (You et al., 2020) or plain Adam find success in large batch settings (Nado et al., 2021), suggesting a competitive advantage even with reduced noise. Studies of batch size scaling also find that Adam scales better with batch size (G. Zhang et al., 2019).
Zhang et al. (2020b) note a correlation between heavy-
Alternative explanations. These empirical results cast doubt on the idea that robustness to heavy- tailed noise is the primary factor behind the performance improvement of Adam over SGD. Hypothe- ses based on deterministic properties might provide better descriptions of the cause of this gap we discuss them in more details Sections and One such interpretation is the view of Adam as a variant of sign descent, which was motivation of RMSprop (Tieleman and Hinton, 2012), as studied by Balles and Hennig (2018) and Bernstein et al. (2018). However, it remains unclear whether the performance of Adam can be explained by its similaritics to simpler algorithm, or if the additional changes needed to obtain Adam are necessary to obtain good performance.
'The distribution of errors hetween stochastic gradients and full gradients g. llğ øll, is well approximated by Gaussian for image models but closer an a-stable distribution for language models.
2

---

Published as a conference paper at ICLR 2023
MNIST
CIFAR-10
PTB
WikiText-2
SQuAD
10'
Training loss
100
10
10-3
10-2-
10
100
10-5
10-5
10-1
10-1
Epoch
800
Epoch
800
0
Epoch
3200
Epoch
320
Epoch
80
SGD(+m)
Adam(+m)
SGD(-m) m))
Adam(-m)
Figure 2: The gap does not disappear when training in full batch. Repeating the training procedure of Figure I in full batch reveals similar-or larger-gap between SGD and Adam.
1.1 CONTRIBUTIONS
The key question we wish to address is whether the gap between SGD and Adam on transformer models, studied by J. Zhang et al. (2020b), is really caused by noise, whether there already is large difference in the deterministic setting. Our key observations are
Noise is not the key contributor to the performance gap between SGD and Adam on trans- formers. Removing noise by running in full batch does not reduce the gap (Figure 2).
SGD benefits less from the reduction in noise than Adam. Increasing the batch size actually increases the gap between the methods when controlling for the step-size and number of iterations ($3, Figure 3). The performance SGD does not seem dominated by noise, as its progress per iteration does not improve with batch size much as it does for Adam ($3.1, Figure 4).
That the performance gap between SGD and Adam grows when noise is removed suggests that robustness to noise. This raises the
the benefit of Adam over SGD can not primarily be due question as to which component of Adam enables its good performance in the deterministic setting and whether a simpler algorithm can display similar behavior. We show that
3. Sign descent can close most of the gap between SGD and Adam in full batch. While sign descent performs poorly with small batch sizes, it improves drastically with larger batch sizes and can bridge most of the gap between gradient descent and Adam ($4, Figure 5-7).
We also present results using normalized gradient updates, which improves on the performance of SGD and scales better large batch sizes. However, full batch, sign descent outperforms plain normalization and approaches the performance of Adam. Momentum improves the performance of both Adam and sign descent, and they are similar when both run with- or without momentum.
Despite sign descent being one of the key motivations behind RMSprop, and Adam by extension, the similarity to sign descent in full batch had not been shown empirically. Although this does not give an explanation for why Adam outperforms SGD, it might give indication of how. As sign descent is a simpler algorithm, understanding its behavior in the deterministic setting might prove a useful tool understand the success of Adam and the properties of the problem classes where it works well.
2 EXPERIMENTAL DESIGN
Our first experiments focus on the performance of SGD and Adam as the batch size increases, and the noise induced by subsampling decreases. Our goal is check whether the gap between SGD and Adam persists as noise is removed. We touch on the experimental design decisions necessary to interpret the results here. Note that there are practical limitations when comparing optimizers with large batch sizes due to computational challenges, which we discuss in Section 5.1 and Appendix A.
Problems. We consider two image and three language tasks.
Image classification on MNIST and CIFAR-10 10 using a small CNN and ResNet18.
Language modeling on PTB and WikiText-2 using a small transformer and Transformer-XX
Question answering on SQuAD by fine-tuning pre-trained DistillBERT model.
Focusing on the heavy-tail hypothesis of Zhang et al. (2020b), our attention is on the behavior of the optimizers on language tasks. Image tasks are included for comparison.
Training performance. Our goal is to study optimization dynamics cases where SGD fails to make sufficient progress. Our results focus the training loss, and we use it to select hyperparameters.
3

---

Published as a conference paper at ICLR 2023
MNIST
CIFAR-10
PTB
WikiText-2
SQuAD
10'
Training loss at comparablee
10-1
10
4-
10"
10-9-
10-3
10
2
10-1
10-5
10-6
10-1
10a
Batch size
10
Batch size
10
10
Batch size
10
10
Batch size
10*
10
Batch size
10
SGD(+m)
Adam(+m)
SGD(-m)
Adam(-m)
Figure 3: The gap between SGD and Adam increases with batch size. Performance after a similar number of iterations across batch sizes. The gap between Adam and SGD grows with batch size on language models, confirming the trend observed in Figures and 2. Due to practical implementation issues, smaller batch sizes still run for more iterations on the larger datasets (WikiText-2, SQuAD) despite being stopped after one epoch (see Appendix A). The degradation in performance as the batch size increases is explained by this decrease number of iterations. We still observe that the gap grows with batch size despite this bias favoring small batches. To show the effect of batch size beyond the first epoch, we show the full runs in Figure 4.
Results on hold-out data are given in Appendix C, but generalization at large batch sizes is known to require additional tuning and regularization (Shallue et al., 2019; Geiping et al., 2022).
Batch sizes and reducing noise. To check if less noisy gradient estimates reduce the gap between SGD and Adam, we measure progress per iteration as we increase the batch size. The batch sizes used, labelled S, M, L. and XI., correspond to a #44 x relative increase. Larger batch sizes are run for more epochs, but the increase in batch size leads to fewer iterations (detailed in Tables I and 2, Appendix A). For the full batch runs, we remove small percentage of the data (50.5%) to ensure the dataset is divided evenly in batches. We check that the observed trends also hold when disabling dropout, the other source of randomness on transformers, in Appendix B.4.
Simple training procedure. We use a constant step-size tuned by grid search. While better per- formance can be obtained with step-size schedules, our primary objective is to gain insight on the behavior of simple updates rather than reproduce sfte-of-the-ane performance.
Hyperparameter tuning. Increasing the batch size can allow for larger step-sizes to be stable, and previous work has reported that the best step-size across batch size settings need not be monotonic (Shallue et al., 2019). To account for these effects, we tune the step-size for each batch size individually by grid search. We start with a sparse grid and increase the density around the best step-size. We repeat each run for 3 random seeds. Grid-search validation results are given in Appendix C. We use each method with and without momentum, indicated by (+m) and (-m). When using momentum, we fix it to 0.9 (8 for SGD, B1 for Adam). Other parameters are set to defaults (32 = 0.999, 6 10-8).
BEHAVIOR OF SGD AND ADAM IN LARGE BATCH
Comparing SGD and Adam in small and full batch in Figures and we observe the following.
3.a Adam outperforms SGD by large margin on language tasks, as expected from previous observations (J. Zhang et al., 2020b).
3.b Despite removing stochasticity, the gap between SGD and Adam is not reduced. It even increases on some problems, especially on the language tasks. On CIFAR-10 10 and PTB, the performance of Adam improves while the performance of SGD worsens PTB and WikiText-2.
The importance of momentum is also increased in full batch, as the gap between the same optimizer with and without momentum is larger in Figure 2. But Adam without momentum still outperforms SGD with momentum in large batch on the language tasks.
However, it is not clear that this comparison of the small and full batch settings a good indicator of the performance per iteration. Although run for more epochs, the optimizers take far fewer steps in the full batch setting. To account for this confounding factor, in Figure 3 we introduce intermediate batch sizes and show the loss in each setting when stopped at comparable number of iterations. The observations from Figures 1 and 2 carry over to Figure 3, which shows the trend across batch sizes more clearly; the gap between Adam and SGD grows with batch size, especially language models.
4

---

Published as a conference paper at ICLR 2023
PTB
WikiText-2
SQuAD
10
Training loss
10
10
109
10
10-1
10
10"
10
10
10
10
10
10
10
10"
10a
10
10
10*
10*
10
101
Training loss
8-
10
4-
100
100
10
10
10
lteration
10
10
Iteration
10
10'
Ieeraiio
10
SGD(+m)
Adam(+m)
SGD( m)
Adam(-m)
Full
XL
M
Figure 4: Adam better takes advantage of the reduced noise with larger batch sizes. For each problem, each optimizer shown with five different batch sizes, interpolating between the small batch setting of Figure and the full batch setting of Figure 2. Larger batch sizes run for fewer iterations and terminate earlier, indicated by the markers (7), with smaller sizes for smaller batches. SGD follow similar trajectory across most batch sizes, indicating that increasing the batch size past some threshold does not improve the performance; similar results would expected from running with the same batch size but terminating earlier. Adam, the other hand, achieves similar error in fewer iterations when the batch size increased. Top/bottom: results without/with momentum.
3.1 LIMITATIONS AND ALTERNATIVE VISUALIZATIONS
The view provided by Figure 3 highlights the gap in performance per iteration between Adam and SGD, but does not provide a full picture of their behavior with increasing batch-size. To stop each method at a comparable number of iterations across batch sizes, we have to stop the smallest batch sizes after one epoch. The results thus need not be representative of standard training, as neither SGD nor Adam can achieve reasonable training error after only one epoch.
To verify that the observed behavior holds beyond the first epoch in small batches, we show the full trajectory of the loss for each batch size in Figure 4, focusing on the transformer problems. For each problem, each optimizer is shown running with fives batch sizes, giving a more detailed view of how the gap between the two optimizers increases with batch size, and is greatest at full batch;
3.c The performance of plain SGD does not significantly improve improves with batch-size. The trajectory of the loss for SGD is similar across batch sizes, indicating that the reduction in noise from increasing the batch size does not improve its performance; we might expected similar results from running with the same batch size, but terminating earlier.
3.d Adam improves with batch size and achieves similar or lower error in fewer iterations.
We also observe that, for both optimizers, momentum improves the convergence speed more with larger batch size. These results are consistent with previous studies the batch size scaling of momentum (Shallue et al., 2019; Smith et al., 2020) and Adam (G. Zhang et al., 2019).
Our experiments provide additional evidence on language tasks that SGD does not benefit from reduction in noise in the gradient estimate once beyond a certain batch-size. This suggests that stochasticity is not the limiting factor the performance of SGD for these problems. That the gap between Adam and SGD grows with batch size is also inconsistent with the idea that the improvement of Adam over SGD results from a more robust estimation of the gradient. Those observations do not rule out the possibility that optimization dynamics for small batch sizes are better explained by heavy-tailed rather than sub-Gaussian noise. However, results with large batch sizes suggest that the benefits of Adam over SGD are deterministic in nature.
ALTERNATIVE INTERPRETATIONS
As noise cannot explain the gap between (S)GD and Adam in the full batch setting, this raises the question the improved performance of Adam in full batch be attributed to a simpler algorithm? Are the algorithmic differences between Adam and SGD, such as moving averages or bias-correction. improving the performance in the stochastic setting, or are they necessary in the deterministic
5

---

Published as a conference paper at ICLR 2023
MNIST
CIFAR-10
PTB
WikiText-2
SQuAD
10'
Training loss at compparbbl
10-1
10
4-
10"
10-9
10-3
10
2-
10-1
10-5
10-6
10-1
102
10*
10
10
10
10
10
10*
10
10
Batch size
Batch size
Batch size
Batch size
Batch size
(i)
Norm.(+m)
Sign(-
Norm.(mm
Figure 5: Sign descent and normalized GD improve with batch size. Performance after a similar number of iterations across batch sizes. Sign descent performs poorly in small batch sizes and is outperformed by normalized GD. In full batch, sign descent outperforms normalized GD and approaches the performance of Adam. We show the full runs for each batch size in Figure 6.
setting? Our goal is to isolate small algorithmic changes from gradient descent that would exhibit behavior similar to Adam, while being easier to interpret and analyse. Alternative hypotheses on the performance of Adam might provide insight on its performance, such its similarity to sign descent or gradient clipping.
4.1 SIGN DESCENT AND NORMALIZED UPDATES
common view of Adam is that it performs a form of smoothed sign descent (Balles and Hennig, 2018; Bernstein et al., 2018), Indeed, the motivation for RMSprop (Tieleman and Hinton, 2012) was make sign descent more stable in the stochastic setting. The update of R.Sprop (with parameters recond-moment buffer 2/ 0, and parameters a, B2,c),
1
Mt++ = B2 + (1 32)
1++1 It
St:
Vet+i
reduces to sign descent when setting the hyperparameters 32 and c to 0, as
gt
Ut+1 Dt
T++1 = T2.
It or siggn))))).
The same applies to Adam when taking its momentum parameter 31 to 0 (ignoring bias- coas-correction. Consistent with the sign descent interpretation, the success of Adam often attributed to its normal- ization effect, that changes across coordinate are uniform despite large differences in their gradients (e.g., Liu al., 2020. $3.2/Fig. 5). However, why sign descent should work in the deterministic setting and whether RMSprop succeeds in "stabilizing" sign descent have not been explored.
An alternative approach to improve the performance of SGD on language models is to use gradient clipping (Pascanu et al., 2013), Clipping and normalized updates were discussed recently in the context of Adam (J. Zhang et al., 2020a) and bgnnbbaedd methods (Crawshaw et al., 2022), as element-wise clipping is equivalent to the sign if all elements are larger than the clipping threshold.
To gain insights on whether the success of Adam in the deterministic setting can be attributed those simpler heuristics, we repeat the prior experiments with the following updates. We use the normalized gradient, which changes the magnitude of the step, and sign descent, which also change its direction. We implement the updates with heavy-ball momentum by accumulating the transformed gradient:
m 3m,m + h(g)),
where
h(g) g/ 9/119112 for normalized GD,
It-1 = Iz am4+1
h(g) = sign(g) for sign descent.
As before, do not tune momentum and present results with (8 0.9) and without (B 0) it. We reproduce the visualizations of Figure 3-4 for the new updates in Figure 5-6 and observe that:
4.a Sign descent performs poorly at small batch sizes but gets closer to Adam in full batch. At small batch sizes, sign descent can be worse than plain SGD. However, the improvement from increasing batch sizes is greater than for other optimizers, and sign descent goes from being the worst option with small batches being competitive with Adam in full batch.
4.b Normalized GD scales better but plateaus. While normalizaton improves performances and helps scale with batch size, the scaling plateaus earlier than for sign descent.

---

Published as a conference paper at ICLR 2023
PTB
WikiText-2
SQuAD
10
Training loss
10
10
109
10
10-1
10
10
10
10
10
10
10
10
10
10
10
101
10
10*
10
10a
10
Training loss
8-
10
4-
100
100
10-1
10
10
lteration
10
10
Iteration
10
10'
Iteration
10
Sign(+m)
Nom.(+m)
Sign(-m)
Nomm.-mm
Full
XL
M
Figure 6: Sign descent improves with batch size. While normalized GD outperforms sign descent in small batch sizes, the relationship switches in full batch and sign descent outperforms normalized GD. Normalized gradient descent also scales better with batch size than plain gradient descent (compare Figure 4), but the method that scales best with batch size is sign descent. Larger batch sizes run for fewer iterations and terminate earlier, indicated by the markers (7), with smaller sizes for smaller batches. Top/bottom: results without/with momentum.
As with other optimizers, momentum helps both sign descent and normalized GD scale larger batch sizes. The improvement in performance with batch size observed for Adam is closer to that of sign descent than normalized GD. In full batch, sign descent with momentum closes most of the gap between SGD and Adam, and it can even outperform Adam on some problems.
To better illustrate that the performance of sign descent poor in small batch, but that it closes most of the gap between GD and Adam in full batch, we compare all optimizers with momentum in traditional loss per epoch format in Figure (without momentum in Figure 10, Appendix B).
While a gap still exists between Adam and sign descent, the improvement in performance over gradient descent supports the hypothesis that the performance gap between Adam and gradient descent has its roots in a difference in the deterministic case. Parts of the benefit of the second- moment estimation in Adam or R.Sprop can be attributed the difference between gradient descent and sign descent. The good scaling properties of Adam to large batch sizes are also shared with sign descent. This connection might provide a new avenue for analysis, by studying simpler algorithm, to understand the behavior of Adam and the impact of noise.
DISCUSSION
We present experimental evidence that runs counter to the idea that Adam outperforms SGD on transformers due more robust estimate of the descent direction. Rather, experimental results show that Adam outperforms gradient descent in the full batch setting, where gradient descent already performs poorly. Those results validate the intuitive motivations for RMSProp and by extension, Adam-ttie that the sign of the gradient might be more reliable direction than the gradient. In addition, the results show that the improvement performance with large batch sizes exhibited by Adam, also observed by previous work (G. Zhang et al., 2019), is shared by sign descent. As Adam outperforms sign descent in small batch sizes, this suggests that the benefits of the algorithmic differences between sign descent and Adam indeed improves its behavior in small batch sizes.
Despite the reported similarities between sign descent and Adam, that sign descent outperforms gradient descent by such margin in full batch on transformers is surprising. The sign descent perspective does not fit the common view Adam as an "adaptive" algorithm, and there is limited theory explaining the benefits of sign descent in deep learning. But that sign descent performs well on deep learning tasks is corroborated by the recent work of Chen et al. (2023). Using evolutionary search to discover optimization algorithms, they obtain variant of sign descent with momentum that outperforms Adam variants on a range of deep learning models and exhibits better relative performance with large batch sizes. Understanding how to capture the benefits of sign descent
7

---

Published as a conference paper at ICLR 2023
Medium batch
Training Loss
PTB
10
WikiText-2
10'
SQuAD
Sign
Sign
SGD
109
Nor..
10
SGD Norm.
Nom
Adam
10
Adam
10
Sin
50
100
20
40
Training Loss
10
Full batch
8-
101
SGD
Nom.
4-
SGD
100
Sign
100
SGD
Norm.
Nom.
Sign
Adam
10
Adam
10-1
Adam
Sign..
Epoch
3000
Epoch
300
Epoch
60
Figure 7: Sign descent can close most of the gap between GD and Adam in full batch. At small batch sizes, the performance of sign descent can be worse than SGD. However, the improvement when increasing the batch size is greater than for other optimizers, and sign descent goes from being the worst option to being competitive with Adam full batch. All optimizers are shown with momentum. A similar trend holds when looking at all optimizers without momentum, shown in Figure 10. Top/Bottom:
performance with a medium batch size/in full batch.
those models might give us a better understanding of the loss landscape in deep learning. We end by discussing potential open questions, related work, and limitations of the results presented here.
Improvement of sign descent with batch size. Larger improvements with batch size often asso- ciated with methods that are faster than gradient descent, such as second-order methods, momentum or Nesterov acceleration. This improved performance typically comes at the cost of increased sensitivity to noise, requiring larger batch sizes to achieve better performance. This has been shown empirically for momentum on deep learning models (Shallue al., 2019; Smith al., 2020), and can be established formally, e.g. on quadratics (Flammarion and Bach, 2015). Quadratic models have also been used to justify the improved performance of Adam with large batches (G. Zhang et al., 2019). This justification relies on the interpretation of Adam as approximate second-order method, similar to the KFAC approximation to natural gradients (Martens and Grosse, 2015). However, this form of sign descent, and the
interpretation of Adam seems incompatible with its interpretation quadratic model alone seems insufficient to explain the performance of sign descent.
Limitations of typical assumptions. Typical analyses in optimization assume the objective function L) to ensure the accuracy of its Taylor approximation. This
smooth (has bounded Hessian, | assumption implies the following, sometimes called the descent lemma (Bertsekas, 1999, Prop. A.24)
L +
(w) < f(x)
2T. [+(+)))++
(x (+L))
Without further assumptions, this bound the only guarantee of performance. As the bound is optimized at the gradient descent step y improve on GD. is of course possible to provably improve on GD with further assumptions. e.g. with acceleration on convex functions (Nesterov, 1983), but this highlights the strong relationship between the typical smoothness assumption and GD. Moreover, recent works have called into question the adequacy of this assumption, showing that it does not hold even in "simple" deep learning problems (Cohen et al., 2021). We discuss next recent works that explore relaxations of smoothness to better characterize the loss landscape and capture the benefit of clipping and sign-based algorithms.
(1/x)V((xx) one would expect any corollary to not
Justifications for normalization approaches. J. Zhang et al. (2020a) provides empirical evidence that, on deep learning models, the Hessian and gradient norm can share similar scale. This observa- tion motivates a relaxation of the uniform smoothness bound ([|v2 fll < L) to allow the Hessian to grow with the gradient (|) [ < Lo + Li I|I. This suggests f behaves like smooth function when the gradient is small, and gradient descent step can be expected to make progress. But the gradient is large, the Hessian might be large. Dividing by the upper bound on the Hessian, the gradient norm, normalizes the step and leads to clipping. This view of clipping has been further explored by B. Zhang et al. (2020) and Qian et al. (2021). However, our experiments suggest that
8

---

Published as a conference paper at ICLR 2023
normalization alone might be not be sufficient to bridge the gap between SGD and Adam, and that dlement-wist clipping or sign-baud based methods exploit additional structure about the problem.
Justifications for sign- and element-wise clipping approaches. Bernstein et al. (2018) and Balles et al. (2020) provide conditions under which sign-based approaches can outperform SGD in the deterministic stochastic setting, assuming glement-wiss, smoothness measuring smoothness in the 20 norm. As with the standard smoothness assumption, it is unclear whether they provide an accurate description of the optimization dynamics in deep learning. Following the relaxed smoothness assumption of J. Zhang et al. (2020a), Crawshaw et al. (2022) propose a coordinate analyse a variant of sign-descent inspired by Adam, using exponential moving averages estimate the sign. While providing a justification for sign descent-like algorithms, it is not clear whether the coordinate-we -isee relaxation is practical. Having 2d parameters, one for each of the weights in the network, checking this variant requires checking each weight and convergence results depend on the 2d problem specific-constant. Identying a verifiable assumption that captures the advantage of sign-based methods in the deterministic setting and understanding when it holds remains open.
relaxation to
What architecture choices lead to the increased gap between SGD and Adam? We do not observe such a large gap between SGD and Adam on CNNs image tasks compared to transformers on language tasks. What properties of the problem or architecture leads to a much better performance of Adam, sign descent or other normalization schemes, beyond the difference in the tails of the stochastic gradients noted by J. Zhang et al. (2020b)? The prediction over a large vocabulary in language tasks-much larger than the number of classes in image tasks-could suggest similarity with overparametrized logistic regression, which is known to exhibit faster convergence of normalized gradient descent (Nacson et al., 2019). The architectures also differ in their choice of normalization layers, skip connections and initializations, choices which were crucial for the training of deep networks on image tasks (He et al., 2016) but might not yet be as mature for transformer models. Reducing the complexity of such model to minimal example that still exhibits a large gap between SGD and Adam but without the computational hurdles of large deep learning models would be helpful to serve as mental model and henchmark to test hypotheses or optimizers.
Designing versions of sign descent that are robust to small batch sizes? The exponential moving average used by RMSProp and Adam works well in practice, but capturing this benefit in theory is challenging. Existing guarantees show a negative dependence on 32 (Défossez et al., 2022; Alacaoglu et al., 2020; Crawshaw et al., 2022). In contrast, alternative mechanisms such majority voting, popular in the distributed setting due to the low communication cost of sign descent, have provable guarantees (Bernstein al., 2018; Safaryan and Richtárik, 2021). )). How to obtain similar guarantees for exponential moving averages, which are known to work for deep learning, remains open.
5.1 LIMITATIONS
major limitation whenever probing the full batch setting is computational costs. As we measure progress per iteration, keeping the number of iterations constant across batch sizes would be ideal, but it is computationally infeasible given our budget. We mitigate this limitation by introducing intermediate batch sizes that interpolate between the small and full batch setting. However, due to those limitations, our results might only probe the "beginning" of the training procedure compared to state-of-the-an workloads. We also use constant step-size, and some of the difficulties encountered by SGD on transformers might be mitigated by a warm-up or decaying step-size schedule if the initialization has strikingly different landscape from the remainder of the optimization path.
Focus on training performance. We do not attempt to optimize hyperparameters for validation error, and instead focus on understanding the optimization performance on the training loss. The results might be of limited applicability in practical settings focused on generalization. However, the validation metries (available alongside our grid-search results Appendix C) suggests that optimizers which perform better on training error achieve lower testing loss faster (before over-fitting)
Qualitative differences across architectures. The striking difference in performance between SGD and Adam on transformers need not hold for other architectures. On the two image tasks included to serve as comparison points, the distinction between SGD and Adam and the observed trends are less clear. For example, on ResNetl 8/CIFAR10 10, SGD behaves differently than on the language tasks in Figure (Appendix B), and improves with batch size as much as Adam. We hypothesize this is due to the network using Batch Normalization. We might need different assumptions, analysis tools and possibly optimizers for different families of architectures that have qualitatively different behaviors.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS We thank Si Yi (Cathy) Meng, Aaron Mishkin, and Victor Sanches Portella for providing comments on the manuscript and earlier versions of this work. This research was partially supported by the Canada CIFAR AI Chair Program, the Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grants RGPIN-2022-06669, and enabled in part by support provided by the Digital Research Alliance of Canada (alliancecas) ca).
REFERENCES
Ahmet Alacaoglu, Yura Malitsky, Panayotis Mertikopoulos, Volkan Cevher (2020). "A new regret analysis for Adam-type algorithms".. In: International Conference on Machine Learning.
Rohan Anil, Vincet Gupta, Tomer Koren, and Yoram Singer (2019). "Memory Efficient Adaptive Optimization". In: Advances in Neural Information Processing Systems.
Jimmy Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton (2016). "Layer Normalization". In: Advances in Neural Information Processing Systems, Deep Learning Symposium.
Lukas Balles and Philipp Hennig (2018). "Dissecting Adam: The Sign, Magnitude and Variance Stochastic Gradients". In: International Conference on Machine Learning-
Lukas Balles, Fabian Pedregosa, and Nicolas Le Roux (2020). The Geometry of Sign Gradient Descent. arXiv/2002.08056.
Jeremy Bersstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar (2018). "SIGNSGD: Compressed Optimisation for Non-Convex Problems". In: International Conference on Machine Learning.
Dimitri P. Bertsekas (1999). Nonlinear Programming.. Athena Scientific.
Xiangning Chen, Chen Liang. Da Huang, Esteban Real, Kaiyuan Wang, Yao Liu, Hieu Pham, Xuanyi Dong, Thang Luong, Cho-Jui Hsich, Yifeng Lu, and Quoc V. Le (2023). Symbolic Discovery of Optinization Algorithms. arXiv/2302.0666
Jeremy M. Cohen, Simran Kaur, Yuanzhi Zico Kolter, and Ameet Talwalkar (2021). "Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability". In: International Conference on Learning Representations.
Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang. and Zhenxun Zhuang (2022). "Robustness to Unbounded Smoothness of Generalized SignSGD". In: Advances in Neural Information Processing Systems.
Zihang Dai, Zhilin Yang, Yiming Yang. Jaime Carbonell, Quoe Viet Le, and Ruslan Salakhutdinov (2019). "Transformer-Xi. Attentive Language Models beyond ength Context". In: Annual Meeting of the Association for Computational Linguistics.
Alexandre Défossez, Leon Bottou, Francis Bach, and Nicolas Usunier (2022). "A Simple Convergence Proof of Adam and Adagrad". In: Transactions on Machine Learning Research.
Nicolas Flammarion and Francis R. Bach (2015). "From Averaging to Acceleration, There is Only a Step-size". In: Conference on Learning Theory.
Jonas Geiping, Micah Goldblum, Phil Pope, Michael Moeller, and Tom Goldstein (2022). "Stochastic Training is Not Necessary for Generalization.. In: International Conference on Learning Representations.
Eduard Gorbunov, Marina Danilova, and Alexander V. Gasnikov (2020). "Stochastic Optimization with Heavy-
Tailed Noise via Accelerated Gradient Clipping". In: Advances Neural Information Processing Systems.
Elad Hazan (2022). Introduction to Online Convex Optimization. MIT Press.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun (2016). "Deep Residual Learning for Image Recogni- tion". In: IEEE Conference on Computer Vision and Pattern Recognition.
Sergey loffe and Christian Szegedy (2015). "Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift". In: International Conference Machine Learning.
Diederik Kingma and Jimmy Ba (2015). "Adam: A Method for Stochastic Optimization". In: International Conference on Learning Representations.
Alex Krizhevsky (2012). Learning Multiple Layers of Features from Tiny Images. Tech, rep. University of Toronto.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner (1998). "Gradient- Basee Learning Applied to Document Recognition". In: Proceedings the IEEE
10

---

Published as a conference paper at ICLR 2023
Liyuan Liu, Xiaodong Liu, Jianfeng Gao, Weizhu Chen, and Jiawei Han (2020). "Understanding the Difficulty of Training Transformers". In: Conference on Empirical Methods Natural Language Processing.
Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz (1993). "Building a Large Annotated
Corpus of English: The Penn Treebank". In: Computational Linguistics 19.2. pp. 313-330.
James Martens and Roger B. Grosse (2015). "Optimizing Neural Networks with Kronecker-factored Approximate Curvature". In: International Conference on Machine Learning.
Stephen Merity, Caiming Xiong, James Bradbury. and Richard Socher (2017). "Pointer Sentinel Mixture Models". In: International Conference on Learning Representations.
Mor Shpigel Nacson, Jason D. Lec, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry (2019). "Convergence of Gradient Descent on Separable Data", In: International Conference on Artificial Intelligence and Statistics.
Zachary Nado, Justin Gilmer, Christopher Shallue, Rohan Anil, and George E. Dahl (2021). A Large Batch Optimizer Reality Check: Traditional, Generic Optimizers Suffice Across Batch Sizes. #tXiv/2102.06356
Yurii E. Nesterov (1983). "A method of solving a convex programming problem with convergence rate O(k²)". In: Soviet Mathematics Doklady. English translation of Russian, in Doklady Adademii Nauk SSSR 269, 543-547 (1983).
Yurii E. Nesterov (2018). Lectures Convex Optimization. Springer.
Francesco Orabona (2020), Neural Networks (maybe) Evolved Make Adam the Best Optimizer. Blog post. http::/:///aaammeeeeeeemmm free com/ 2too/2220/12/000 ke se--ada-ther best pesst-optimie imptiiir./.....
Razvan Pascanu, Tomás Mikolov, and Yoshua Bengio (2013). "On the difficulty of training recurrent neural networks", In: International Conference Machine Learning.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala (2019). "PyTorch: An Imperative Style, High- Perfforrrfo Deep Learning Library". In: Advonces Neural Information Processing Systems.
Jiang Qian, Yuren Wu, Bojin Zhuang, Shaojun Wang, and Jing Xiao (2021). "Understanding Gradient Clipping In Incremental Gradient Methods". In: International Conference on Artificial Intelligence and Statistics.
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang (2016). "SQuAD: 100,000+ Questions for Machine Comprehension of Text". In: Conference on Empirical Methods in Natural Language Processing.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar (2018). "On the Convergence of Adam and Beyond". In: International Conference on Learning Reprexentations.
Mher Safaryan and Peter Richtárik (2021). "Stochastic Sign Descent Methods: New Algorithms and Better Theory". In: International Conference on Machine Learning.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf (2019). "DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter". In; Advances in Neural Information Processing Systems, EMC² workshop.
Christopher
Shallue, Jachoon Lee, Joseph M. Antognini, Jascha Sohl- Dicksteein Roy Frostig, and George Dahl (2019). "Measuring the Effects of Data Parallelism on Neural Network Training". In: Journal of Machine Learning Research 20, 112:1-1 12:49.
Samuel L. Smith, Erich Elsen, and Soham De (2020). "On the Generalization Benefit of Noise in Stochastic Gradient Descent". In: International Conference on Machine Learning.
Vishwak Srinivasan, Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Kumar Ravikumar (2021). Efficient Estimators for Heavy-Taile Machine Learning. Openneeview:5K377CWWWYY
Tijmen Tieleman and Geoffrey Hinton (2012). RMSPROP: Divide the gradient by a ruaning average of its recent magnitude. Lecture notes http:/ / www. toronto. www.entt...deeeeeeeeeeeeeee -t
pdf.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin (2017). "Attention is All you Need". In: Advances in Neural Information Processing Systems.
11

---

Published as a conference paper at ICLR 2023
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jemiit, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush (2020). "Transformers: State-of-the- Art Natural Language Processing". In: Conference on Empirical Methods in Natural Language Processing.
Yang You, Jing Li, Sashank J. Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh (2020). "Large Batch Optimization for Deep Learning: Training BERT in 76 minutes". In: International Conference on Learning Representations.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang (2020). "Improved Analysis of Clipping Algorithms for Non-convex Optimization". In: Advances in Neural Information Processing Systems.
Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George E. Dahl, Christopher J. Shallue, and Roger B. Grosse (2019). "Which Algorithmic Choices Matter at Which Batch Sizes? Insights From Noisy Quadratic Model". Advances Neural Information Processing Systems.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie (2020a). "Why Gradient Clipping Accelerates Train- ing: A Theoretical Justification for Adaptivity". In: International Conference on Learning Representations.
Jingzhao Zhang, Sai Pranceth Karimireddy, Andreas Veit, Seungyeon Kim. Sashank Reddi, Sanjiv Kumar, and Suvrit Sra (2020b). "Why Adaptive Methods Good for Attention Models?" In: Adyances Neural Information Processing Systems.
12

---

Published as a conference paper at ICLR 2023
Supplementary material
Appendix A Experimental details
Appendix B Additional plots
Appendix C Grid-searcher and performance of selected runs
A EXPERIMENTAL DETAILS
Appendix A.1
Datasets and models Appendix A.2 Batch sizes and epoch counts
Appendix A.3 Algorithms pseudocode
Appendix A.4 Histograms in Figure I
Appendix A.5 Grid search
The code to reproduce our experiments and data generated by each run is available at https: /githbb.tttuugggg
addaa-----ad
A.1 DATASETS AND MODELS
Problems in the main For all problems, we use the default train/test split and report the performance on the test split as validation error.
referred to by the dataset and corresponds to the following problems.
MNIST, Modified LeNet5
(LeCun et al., 1998)
Image classification task using a modified LeNet5 architecture; 3-convolution, 2-linear layer average pooling and tanh activations, using linear rather than Gaussian output.
Dataset
Lanun.ecur.com excb/xnmaiae /mnist/
CIFAR10, ResNet18
(Krizhevsky, 2012; He et al., 2016)
PyTorch (Paszke et al., 2019) implementation of the 18-layer CNN with residual connections.
Dataset
www.cs
html
Model
10/modd s. html #torchvi a ionoon.oo mo.eodell 1 s. resnet
PTB, Transformer
(Marcus al., 1993; Vaswani et al., 2017)
Word-level language modeling with sequences of 35 tokens using simple Transformer model used as a tutorial example in Py PyTorch. The architecture consists of an 200-dimensional embed- ding layer, transformer layers (2-head self attention, layer normalization, 200ear(200x200)- ReLUU-linear(200x200) layer normalization) followed by linear layer. Data processing uses the implementation of Dai al. (2019).
Dataset
catal 1 1db.uppem..ebbuuccc991...
Processing github. cowp///iiiyyuuu//aaaeeeee--2222 Model pytorch.
html
Wi Transformer-Xi
(Merity al., 2017: Dai et al., 2019)
Word-level language modeling with sequences of length 128 with Transformer-XL, using implementation of Dai et al. (2019) for the model and data preprocessing. Hyperparameters follow the ENWIK8 base experiment Dai et al. (2019), except with the modifications of J. Zhang et al. (2020b), using layers and target length of 128.
Dataset
Lugeaddoor-Langgggg--ooodo--aaaa github. http://o/////occceeeeeeee
Model
SQuAD v1.1, DistillBERT finetuning
(Rajpurkar et al., 2016; Sanh et al., 2019) Question-answering by fine-tuning pretrained DistillBERT model using the HuggingFacc (Wolf et al., 2020) implementation of the model and data processing.
Dataset
moturrar.githhin Model huggingface. wtt.://e.ttttttrereesossooo 9. /ttp hhtml
1/dev/ html
13

---

Published as a conference paper at ICLR 2023
Table Batch sizes used in experiments. The batch size corresponds to the number of input-output samples. For image data, a sample corresponds to an image-label pair. For language models on PTB/WikiText-2, a sample corresponds to pairs of sequences of 35/135 tokens. For DistillBERT on SQuAD, a sample corresponds to question/answer pair. The full batch runs that use 2 99.5% of the entire dataset, drop 0.5% of the data and run full batch on the remaining data every epoch.
Dataset/Model
Batch size
% data
Epochs
Iter:/Epoch
Total Iter.
MNIST M
256
0.43%
100
234
23 400
Modified LeNet5
024
1.71%
100
58
5 800
069
6.78%
200
14
200
XL
16 384
27.31%
400
3
200
Full
60 000
100.00%
800
800
CIFAR-10 ResNet18
64
0.13%
100
781
100
M
256
0.51%
100
195
19,50
I. 024
2.05%
100
48
800
XI. 4.096
8.19%
200
12
2,000
Full
50.000
100.00%
800
800
PTB
16
0.06%
100
I 6.59
165 900
Transformer
M
64
0.24%
100
414
41 400
L
256
0.96%
200
103
600
XL
1224
3.86%
400
25
10000
Full
26 520
99.85%
3 200
3 200
WikiText-2
20
0.12%
40
815
600
Transformer-XI.
M
80
0.49%
40
203
8 1200
320
1.96%
40
2 000
XL
280
7.84%
80
12
960
Full
16240
99.53%
320
320
SQUAD
32
0.04%
5
2 241
13
DistilIBET
M
128
0.15%
5
685
3 3425
L
512
0.58%
5
171
855
XL
2048
2.33%
10
42
420
Full
87 680
99.96%
60
60
A.2 BATCH SIZES AND EPOCH COUNTS
Our goal to compare the optimization performance while controlling for the number of iterations. But keeping the iteration count constant across batch sizes is computationally infeasible. For example, running Transformer-X on WikiText-2 with a batch size of 20 for epoch (32600 iterations) takes 1-2 hours. Running 320 epochs in full batch (320 iterations) takes 8-10 hours. Running 100x more iterations would take over month, making hyperparameter tuning infeasible. As increasing the batch size leads to better performance in fewer iterations, we run larger batch sizes for fewer iterations. We control how the number of iterations changes from setting to setting to have comparable results. The batch sizes indicated by S. M, and XL correspond to relative increase of 4x in batch size, and tune the number of epochs for each setting so that the number of iterations from one batch size to the next stays within factor of =2-8. The settings used in our experiments are described in Table
To highlight the improvement in performance per iteration and account for the confounding factor that larger batch sizes run for fewer iterations (Appendices B. and B.2), we introduce intermediate batch sizes and show the loss in each setting when stopped comparable number of iterations. The stopping times for these experiments (given in Appendix A.2) were selected to make the number of iterations similar. They could not be made equal as we not record the loss on the entire dataset at each iteration. For example, on WikiText-2, the full-batch run is stopped after 320 epochs (320 iterations). while the small batch-size run is stopped at one epoch (815 iterations). On the larger language datasets (WikiText-2, SQuAD), the degradation in performance the batch size increases in Figure is attributable to this decrease in number iterations. However, we still observe that the gap between SGD and Adam grows with batch size, despite this bias favoring small batch sizes.
14

---

Published as a conference paper at ICLR 2023
Table Stopping times used in Figures 3 and 5 obtain comparable number of iterations across batch sizes. The number of iterations can not always s be made made equal as we did not record the loss on the entire dataset at each iteration, and can only stop the small batch sizes one epoch, but the number of steps taken by the optimizer are much closer than in Table 1.
Batch size
Epoch
Iter.
Batch size
Epoch
Iter.
Batch size
Epoch
Iter.
MNIST
PTB
SQuAD
S
256
4
936
S
16
2
3.320
S
32
1
2 741
M
1 0224
812
64
3320
M
128
2
370
L
4.096
58
812
L
256
32
3.96
L
512
3
513
XL
16384
267
801
XL
124
128
30000
XL
2
4
168
Full
60000
800
800
Full
26 520
3 200
200
Full
87 680
60
60
CIFAR-10
WikiText-2
781
S
20
815
M
256
4
780
M
80
3
609
L
1 1024
16
768
L
320
10
500
XL
096
64
768
XL
280
34
408
Full
50000
768
768
Full
140
320
320
For settings where computing the gradient would not fit into memory, we use gradient accumulation to reduce peak memory consumption (computing the gradients of smaller batches and averaging them). We use accumulation for Full batch runs, WikiTeext22 (2 L) and SQuAD (2 M). Due to the batch normalization layers (loffe and Szegedy, 2015) in ResNet18, computing the full-batch gradient would require to pass the entire dataset through the network at once (the normalization makes so that the average of the gradients of the minibatches different from the full gradient). We use the average over the minibatch gradients with a batch size of 10000. Transformer models use layer normalization (Ba et al., 2016) and are unaffected.
The transformer models on PTB and WikiText-2 use dropout by default, meaning that the increase to Full batch reduces noise to floor but does not remove it entirely. In Appendix B.4, we verify that the observation that sign descent bridges the gap between (SJGD and Adam in the deterministic setting on those two datasets in full batch after removing dropout.
A.3 ALGORITIMMS PSEUDOCODE
We the PyTorch (Paszke et al., 2019) implementation of SGD and Adam, and implement the normalized variants (sign descent, normalized GD) with heavy-ball momentum following the pseudo- code in Algorithm 1, The pseudo-code of Adam is given in Algorithm
For every algorithm, we tune the main siep-size by grid search. The momentum parameters / in gradient descent variants and in Adam is set either to 0 or 0.9. This indicated in the main text and figure legends by the suffix (+m) (with momentum) or (-m) (without). We leave the remaining hyperparameters of Adam to their default (82 0.999, 10-5)
Algorithm 1 Gradient Descent and variants
Algorithm 2 Adam
Parameters: step-size a, momentum B. Initialization: momentum buffer mo 0.
Parameters: step-size a, momentum B1, B2.
Initialization: moments buffers mo, Mo = 0. At iteration i: given stochastic gradient gt.
At iteration (: given stochastic gradient 9t.
my 8m4-1 1 + de
m. = 31m-- + (1 -B
Fe-1 It
M, = 32 + (1 - B2)
g for Gradient Descent ge/1lgellz
m//(1 B8)
with d,
for Normalized GD
Tt+1 = - /M, 335) +
(ōt) for Sign Descent
Using the c
15

---

Published as a conference paper at ICLR 2023
A.4 HISTOGRAMS IN FIGURE
The histograms in Figure show the distribution of the stochastic gradient errors at initialization to confirm the observation of J. Zhang al. (2020b). J. Zhang et al. also show the pattern is preserved through training. We use the batch sizes
MNIST
CIFAR-I0
PTB
WikiText-2
SQuAD
256
64
16
16
16
As ResNet18 uses batch normalization, it does not have well-defined "full" gradient (the average of minibatch gradients is not the gradient obtained by passing the entire dataset through the network). We use the average over the minibatch gradients. Other models are unaffected.
A.5 GRID SEARCH
We start with a sparse grid of integer powers of 10 (eg. [10-5, 10 +........ ..... 10"). After ini- tial run to identify a reasonable region, we increase the density to include half-powers (eg. [10-3 10-2.5 10-2 10-1.5 10- The density of the grid is the same for all problems. We run those step-sizes for 3 random seeds determining the data ordering and initialization (except for DistilIBERT on SQuAD, which is pretrained).
To select the step-size, we minimize the (maximum over seeds of the) training loss at the end of training. End-of-training the epoch reported Table 1 for most figures. The exceptions are Figures 3 and 5 which use the stopping times in Table 2.
The final performance as a function of the step-size for the training loss and accuracy/PPL/FI-scor (including on holdout data) are given in Appendix C
B ADDITIONAL PLOTS
Appendix B.1 Gap vs. Batch size (Figure 4 including image tasks)
Appendix B.2 Gap vs. Batch size (Version of Figure 6 including image tasks)
Appendix B.3 Relative performance of sign descent in medium vs. full batch (Version of Figure 7 without momentum)
Appendix B.4 Verifying the results hold without Dropout
B.1
GAP vs. BATCH SIZE (FIGURE 4 INCLUDING IMAGE TASKS)
MNIST
CIFAR-10
PTB
WikiText-2
SQuAD
Training loss
10
10
10
10'
10-3
100
10
2
10-4
10-7
10
10-1
10
10
10a
10
10
10
10
10a
10
10
10
10'10010
10
10
10
10a
10a
10
10
10
10
10
10
10
Training loss
10
10
8
10¹
10'
10-9
10
100
10-
10-7
2
10
10-1
10'
lteration 10a
10'
lteration
10
10'
lteration 10
10'
lteration
10
10'
Iteration
10a
SG)(+m)
Adam(+m)
SGD( m)
Adam(-m)
Full
XL
L
M
Figure 8: Adam better takes advantage of the reduced noise with larger batch sizes. For each problem, each optimizer is shown with five different batch sizes, interpolating between the small batch setting of Figure and the full batch setting of Figure 2. Larger batch sizes run for fewer iterations and terminate earlier, indicated by the markers ),), with smaller sizes for smaller batches. SGD follow a similar trajectory across most batch sizes, indicating that increasing the batch size past some threshold does not improve the performance; similar results would be expected from running with the same batch size but terminating earlier. Adam, on the other hand, achieves similar error in fewer iterations when the batch size is increased. However, the trends are not as clear on MNIST and CIFAR- 10. SGD performs better on CIFAR- 10 than on other problems, which might be attributable the presence of Batch Normalization layers. Top/bottom: results without/win momentum.
16

---

Published as a conference paper at ICLR 2023
B.2
GAP vs. BATCH SIZE (VERSION OF FIGURE 6 INCLUDING IMAGE TASKS)
MNIST
CIFAR-10
PTB
WikiText-2
SQuAD
Training loss
10
10'
10'
10
10
108
109
10
10
10a
10
10
10
10a
10a
10
10
10 10"0
10
10
10a
10
10
10
10
10
10"
10
Training loss
109
10
10
10
10
10
100
10
10
2
10-1
-0-1
10
lteration
10
10'
lteration
10
10
Iteration
10
10
Iteration
10
10
Iteration
10
Sign(+m)
Norm.(+m)
Sign(-m)
Norm.(-m)
v Full
XL
M
Figure 9: Sign descent improves with batch size. While normalized GD outperforms sign descent in small batch sizes, the relationship switches in full batch and sign descent outperforms normalized GD. Normalized gradient descent also scales better with batch size than plain gradient descent (compare Figure 4), but the method that scales best with batch size is sign descent. Larger batch sizes run for fewer iterations and terminate earlier, indicated by the markers (V), with smaller sizes for smaller batches. Top/bottom: results without/withh momentum.
B.3 RELATIVE PERFORMANCE OF SIGN DESCENT IN MEDIUM vs. FULL BATCH (VERSION OF FIGURE 7 WITHOUT MOMENTUM)
Medium batch
Training Loss
PTB
10
WikiText-2
10
SQuAD
Sign
Sign
SGD
10
10
SGD
Nom.
Adam
Adam
Sign
10
10
100
Full batch
Training Loss
8
101
SGD
10"
Sign
8CD
4-
SGD
Norm.
10
10
S
Adam
Sign Adam
10
10-1
Epoch
3000
Epoch
300
Epoch
60
Figure 10: Sign descent can close most of the gap between GD and Adam in full batch. At small batch sizes, the performance of sign descent be worse than SGD. However, the improvement when increasing the batch size is greater than for other optimizers, and sign descent goes from being the worst option to being competitive with Adam full batch. All optimizers are shown without momentum. Although all optimizers suffer from the lack of momentum, especially on WikiText-2, sign descent closes most of the gap between SGD and Adam. A similar trend holds when looking at all optimizers with momentum, shown in Figure 7. Top/Bottom: performance with medium batch size/in full batch.
17

---

Published as a conference paper at ICLR 2023
B.4 VERIFYING THE RESULTS HOLD WITHOUT DROPOUT
The increase of batch size to "Full batch" drives noise to a floor, but does not remove it entirely due to the use of Dropout in the transformer models. Figure 11 shows those models after disabling dropout to verify that the same trends holds, showing the performance of the optimizer in full batch, as in the bottom row of Figure 7 (momentum) and Figure 10 (without momentum). The settings use are the same as for the Full batch in those figures (See Full in Table for batch size and epoch counts) and uses step-sizes tuned by search, with the only modification of disabling dropout. We note that the models achieve lower training error, but the overall trend of Sign Descent closing most of the gap between SGD and Adam full batch is preserved.
PTB
WikiText-2
10
10
Training loss
10
10%
10
10
500
1000
1500
2000
2500
3000
100
150
200
250
300
101
101
Training loss
10"
100
10-1
10-1_
500
1000
1500
2000
2500
3000
50
100
150 Epoch
200
250
300
Epoch
SGD(+m)
Adam(+m)
SGD(-m)
Adam(-m)
Sign(+m)
Norm.(-m)
Sign( m)
Norm. m)
Figure 11: Checking that sign descent still bridges the gap between GD and Adam when dropout removed. The increase of batch size to "Full batch" drives noise to a floor, but does not remove entirely due to the use of dropout in the transformer models. We rerun those models after disabling dropout to verify that the same trends observed Figure 6-7 holds. We note that the models achieve lower training error, but the overall trend of Sign Descent closing most of the gap between SGD and Adam in full batch is preserved.
18

---

Published as a conference paper at ICLR 2023
C
GRID- AND PERFORMANCE OF SELECTED RUNS
C.I SGD AND ADAM
C.I.1
MODIFIED LENETÉ ON MNIST
(GD(+m)
Adam(+m)
SGD(-m)
Adam(-m)
S
M
XL
Full
10
10
10
Train Loss
10"
10
100
10a
10P
10
R
10"2-
10"2.
10
10
10
10
10-2
10
10
10
10
10P
10-4
10-2
10
10
10
10P
10
10-4
10
16
100-
100
100
100
100
Train Acc.
50
0
0
0-
0-
10
10
10
8
10-2
10
10
10
100
100
Valid Acc.
50
50
50
50
50-
0
0
0-
0
10-5
10-2
10-5
10-2
10-6
10-2
10-6
10-2
10
10
Stepsize
Stepsize
Stepsize
Stepsize
Stepsize
S
M
XL
Full
10
10
10
10
10"
Train Loss
10
10
10 R_
10:2_
10-1_
10
10
10-1-
10
10-1
80
100
50
100
10
100
200
200
400
10-9
0
560
100
100
100
100
100
Train Acc.
50
0
0
100
50
100
100
200
200
400
500
100
100
100
Valid Acc.
50
50
50-
50
50-
0
0
0
0
50 Epoch
100
0
50 Epoch
100
0
100
200
200
400
0
500
Epoch
Epoch
Epoch
Figure 12: Grid search and selected runs for each batch size modified LeNetS on MNIST. Top: Loss and evaluation metrics at the end of training (see Table 1) for step-sizes evaluated. Grey line corresponds to value at initialization. Bottom: Performance of the selected step-size on training loss and evaluation metrics during training.
19

---

Published as a conference paper at ICLR 2023
C.1.2
RESNET18 ON CIFAR10
(GD(+m)
Adam(+m)
SGD(-m)
Adam( (m))
S
M
XL
Full
10
10
10
Train Loss
10-1
10-1
10-1-
10-1-
-0-1-
10
10.2
10'
10
10-2
1
10-3
10'
10-2
100-
100 -
100
100 -
100
Train Acc.
50
0
0
0-
0-1
10
10-2
10
10
10
10:2
10
10
10
100
100
100
100
Valid Acc.
50
50
50
50
50-
0
0-T
0
10
10-2
10
10-2
10
10-2
10-7
10-2
10
10
Stepsize
Stepsize
Stepsize
Stepsize
Stepsize
S
M
XL
Full
10
10
10
Train Loss
10:1-
10-4_
10-1
6b
100
50
100
10-
5b
100
100
200
10-7
56o
100
100
100
100
100
Train Acc.
50
0
0
100
50
100
100
100
200
500
100
100
100
Valid Acc.
50
50
50
50
50
0
0
0
50 Epoch
100
50
100
50
100
100
200
0
500
Epoch
Epoch
Epoch
Epoch
Figure 13: Grid search and selected runs for each batch size ResNet18 on Cifar10. Top: Loss and evaluation metries the end of training (see Table 1) for step-sizes evaluated. Grey line corresponds to value at initialization. Bottom: Performance of the selected step-size on training loss and evaluation metries during training.
20

---

Published as a conference paper at ICLR 2023
C.1.3
SMALL TRANSFORMER ON PTB
(GD(+m)
Adam(+m)
SGD(-m)
Adam(-m)
S
M
XL
Full
10
10'
Train Loss
10
10
10
10P
10-4
10-2
10
10
10
10-4
10
10
10"
101
10
10*
10*
Train PPL
10²-
10
10"-
10²
10¹
10"
10
10
10
10"
10
10
109
10
10
109
10
10
10
10
10-1
10
10
10
10
10
10
10
10
10
Valid PPL
10a
10
10a
10a
10º
105_
10a
10
101
10'
10
10
100
10
a
100
10
1
10%
10
10P
10
10
10
Stepsize
Stepsize
Stepsize
Stepsize
Stepsize
S
M
XL
Full
101
10
101
10'
10'
Train Loss
8b
100
50
100
100
200
200
400
2000
10
10
10"
10a
10*
Train PPL
10
10a
105
10a-
10"-
10
10
100
10
10"
50
100
50
100
100
200
200
400
2000
10
10
10
10*
10*
Valid PPL
10a
10a
102
10a
102-
102_
102
5b Epoch
1do
sb Epoch
1d0
10
1do Epoch
200
Z00 Epoch
400
10'
2000
Epoch
Figure 14: Grid search and selected runs for each batch size Small Transformer on PTB. Top:
Loss and evaluation metrics at the end of training (see Table for step-sizes evaluated. Grey line corresponds to value at initialization. Bottom: Performance of the selected step-size on training loss and evaluation metrics during training.
21

---

Published as a conference paper at ICLR 2023
C.1.4 TRANSFORMER-XL ON WIKITEXT-2
(GD(+m)
Adam(+m)
SGD(-m)
Adam(-m)
S
M
XL
Full
Train Loss
10
10
10
10'
10
10
10
10
10t
10-9
10
10
10
10
10P
10-4
10-2
10
10
10
10
10
10-4
10
10
10a
10
100
10
10"
Train PPL
107-
10
10?
102-
10²-
10!-
10
10
10
10'
10"1
10-1
10-1_
10-
10-1_
10
10-3
10
10
10
109
10
10
10"
10
10-1
10
10-2
10
10
10
Valid PPL
10
10
10*
10
101
10'
10
10
10
a
100
10
1
10
10
10
10P
10
10
10
Stepsize
Stepsize
Stepsize
Stepsize
Stepsize
S
M
XL
Full
Train Loss
10
10
10
10'
10¹
10
10
10
10
10"
10
20
20
40
10-1
20
40
10
60
10-1-
200
105
10
100
105
105
Train PPL
10a
10
10a
10a
10a
101
10
10
10'
10'
10"1
10
10
10
10"1
20
40
20
40
20
40
50
200
10
10a
10
10
Valid PPL
103
10a
10a
20 Epoch
40
2b Epoch
10
2b Epoch
40
5b
10'
200
Epoch
Epoch
Figure 15: Grid search and selected runs for each batch size Transformer-XL on WikiText-2.
Top:
Loss and evaluation metrics the end of training (see Table 1) for step-sizes evaluated. Grey line corresponds to value at initialization. Bottom: Performance of the selected step-size on training loss and evaluation metrics during training.
22

---

Published as a conference paper at ICLR 2023
C.1.5
DISTILLBERT PINETUNING ON SQUAD
SGD(+m)
Adam(+m)
SGD(-m)
Adam(- (-m)
S
M
XL
Full
107
10"
Train Loss
10
10
10"
10"1
10-1-
10-1
10
10-1-
10
10
10P
10-4
10-2
10
10
10P
10-4
10
16
100
100
100
100 -
100
Train F1
0
0
0-
10
10
10
8
10
10
10
100
100
100
Valid F1
50
50
50
50
50-
0
0-
0
10-5
10-2
10-5
10
10-6
10-2
10-2
10
10-4
10
Stepsize
Stepsize
Stepsize
Stepsize
Stepsize Full
S
M
XL
10'
Train Loss
10
10
10a
10a
10
10 1-
10
10
10
20
60
100
100
100
100
100
Train F1
0
0-
2.5
5.0
0.0
2.5
0.0
5.0
100
Valid F1
50
50
50
50
50-
0
0
0
0.0
2.5 Epoch
5.0
0.0
2.5 Epach
5.0
0.0
2.5 Epoch
5.0
0
50
Epoch
Epoch
Figure 16: Grid search and selected runs for each batch size DistilIBERT finetuning on SQuAD. Top:
Loss and evaluation metrics at the end of training (see Table 1) for step-sizes evaluated. Grey line corresponds to value at initialization. Bottom: Performance of the selected step-size on training loss and evaluation metrics during training.
23

---

Published as a conference paper at ICLR 2023
C.2
SIGN DESCENT AND NORMALIZED GD MODIFIED LENETS ON MNIST
C.2.1
Sign(+m)
Nomm.++m)
Sign(-m)
Norm.(-n (-m
S
M
XL
Full
10
10
10
Train Loss
10"
10
100
10
10P
10
R
R
10
10
10
10
10-9
10
10
10
10
10P
10-4
10-2
10"
10
10
10"
10
10-9
10
10
100
100
100
100
100
Train Acc.
50
0
0
0-
0-
10-2
10
10
8
10-2
2
10
10
100
100
100
Valid Acc.
50
50
50
50
50-
0
0
0-
0-
10-5
10-2
10-5
10-2
10-6
10-2
10-6
10-2
10
10-2
Stepsize
Stepsize
Stepsize
Stepsize
Stepsize
S
M
XL
Full
10
10
10
10
10
Train Loss
10
10
10 2_
10 10
10-1-
10
10
10-1-
10-1-
10-1
80
10
50
100
10
100
200
200
400
10-9
500
100
100
100
100 -
100
Train Acc.
50
0
0
100
50
100
100
200
200
400
500
100
100
100
Valid Acc.
50
50
50-
50
50-
0
0
0
0
50 Epoch
100
0
50 Epoch
100
0
100
200
200
400
0
500
Epoch
Epoch
Epoch
Figure 17: Grid search and selected runs for each batch size modified LeNetS on MNIST. Top: Loss and evaluation metrics at the end of training (see Table for step-sizes evaluated. Grey line corresponds to value at initialization. Bottom: Performance of the selected step-size on training loss and evaluation metrics during training.
24

---

Published as a conference paper at ICLR 2023
C.2.2
RESNET18 ON CIFAR10
Sign(+m)
Norm.(+m)
Sign(-m)
Norm.(-n) (-m)
S
M
XL
Full
10
10
10
Train Loss
10-1
10-1-
10-1
10
10
1
10
10
10
10-1
10
10-4
10-1
10"
10
10
10-9
10-1
10"
100
100 -
100
100 -
100
Train Acc.
0
0
0-
0-
10
10
10
10%
10"
10
10
10
100
100
100
Valid Acc.
50
50
50
50
50-
0
0
0-
0-
10-2
10-2
10-8
10-2
10-8
10-2
10-
10-2
10
10
Stepsize
Stepsize
Stepsize
Stepsize
Stepsize
S
M
XL
Full
10
10a
10a
Train Loss
10:1-
1
10-1_
10-1_
10--
10
8b
100
50
100
10
50
100
100
200
10-7
500
100
100
100
100 -
100
Train Acc.
50-
0
0
100
50
100
100
100
200
500
100
100
Valid Acc.
50
50
50
50
50-
0
0
0
0
50 Epoch
100
0
50 Epoch
100
0
50 Epoch
100
100
200
0
500 Epoch
Epoch
Figure 18: Grid search and selected runs for each batch size ResNet18 on Cifar10. Top: Loss and evaluation metries the end of training (see Table 1) for step-sizes evaluated. Grey line corresponds to value at initialization. Bottom: Performance of the selected step-size on training loss and evaluation metries during training.
25

---

Published as a conference paper at ICLR 2023
C.2.3
SMALL TRANSFORMER ON PTB
Sign(+m)
Norm.(+m)
Sign(-m)
Norm.(-m)
S
M
XL
Full
10
10'
Train Loss
10
10
10
10
10P
10-4
10-2
10
10
10
10"
10-4
10
10
10"
101
101
10*
10*
Train PPL
107-
10
10²-
10²
10²-
10
10
10
10
10"
10
10
10
10
1
109
10
10
10P
10
10
10
10
10
10
10"
10
10
10
10
Valid PPL
10
10
10a
10
10º
105
10a
10a
10
100
10
a
100
101
10
1
10
10
10
10'
10
10
10
Stepsize
Stepsize
Stepsize
Stepsize
Stepsize
S
M
XL
Full
101
10
101
10'
10'
Train Loss
8b
100
10
50
100
100
200
200
400
2000
10
104
10"
10
10
Train PPL
10"
10a-
105
10a
10"-
10
10
100
10
10"
50
100
50
100
100
200
200
400
2000
10"
10
10
10*
10*
Valid PPL
102
10a
102
10a-
102-
102
102
sb Epoch
1do
sb Epoch
100
10
1do Epoch
200
200 Epoch
400
10'
2000
Epoch
Figure 19: Grid search and selected runs for each batch size Small Transformer on PTB. Top:
Loss and evaluation metrics at the end of training (see Table 1) for step-sizes evaluated. Grey line corresponds to value at initialization. Bottom: Performance of the selected step-size on training loss and evaluation metrics during training.
26

---

Published as a conference paper at ICLR 2023
C.2.4
TRANSFORMER-XL XL ON WIKITEXT-2
Sign(+m)
Nomm.++m)
Sign(-m)
Norm.(-m)
S
M
XL
Full
Train Loss
10
10
10
10
10'
10
10
10
10
108
10
10-
10
10
10
10
10P
10-4
10-2
10
10
10
10
10
10-4
10
10
10a
10
100
10
10
Train PPL
107
10
10?
10²
10*
10!
10
10
10"
10'
10"1
10-1
10-1_
10-
10-1_
10
10
10
10
10
109
10
10
10P
10
10
10
10
10
10
10
105
Vaïd PPL
10
10*
101
10'
10
10
10
a
100
10
1
10"
10%
10
10P
10
10
10
Stepsize
Stepsize
Stepsize
Stepsize
Stepsize
S
M
XL
Full
Train Loss
10
10
101
10'
10¹
10"
10
10
10
10"
10
20
20
40
10
20
40
60
10-1
200
105
10
10a
105
105
Train PPL
10a
10
10a
10a
10a
10
10
10
10'
10"1
10a1
10-
10
10-1_
20
40
20
40
20
40
50
200
10
10
10*
10
Valid PPL
10a
102
102-
10a-
20 Epoch
40
2b Epoch
10
20 Epoch
20
5b
10'
200
Epoch
Epoch
Figure 20: Grid search and selected runs for each batch size Transformer-XL on WikiText-2.
Top: Loss and evaluation metrics the end of training (see Table 1) for step-sizes evaluated. Grey line corresponds to value at initialization. Bottom: Performance of the selected step-size on training loss and evaluation metrics during training.
27

---

Published as a conference paper at ICLR 2023
C.2.5
DISTILLBERT PINETUNING ON SQUAD
Sign(+m))
Norm.++m)
Sign(-m)
Norm.(-n (-m)
S
M
XL
Full
107
10"
Train Loss
10
10
10-1
10-1
10-1-
10
10-1-
10-2
10
10
10P
10
10-2
10
10
10P
10-9
10
16
100
100
100
100
100
Train F1
50
0
0
0-
0-1
10
10
10
8
10-2
10
10
100
100
100
Valid F1
50
50
50
50
50-
0
0--
0
10-5
10-2
10-6
10-2
10-6
10-2
10-8
10-2
10
10-2
Stepsize
Stepsize
Stepsize
Stepsize
Stepsize
S
M
XL
Full
10'
Train Loss
10
10
10a
10a
10a
10
10
10
10
10 1
2
2
20
60
100
100
100
100 -1
100
Train F1
50
0
0
2.5
5.0
0.0
2.5
0.0
5.0
100
Valid F1
50
50
50
50
50-
0
0
0.0
2.5 Epoch
5.0
0.0
2.5 Epach
5.0
0.0
2.5 Epoch
5.0
0
50
Epoch
Epoch
Figure 21: Grid search and selected runs for each batch size DistilIBERT finetuning on SQuAD. Loss and evaluation metrics at the end of training (see Table 1) for step-sizes evaluated. Grey line corresponds to value at initialization. Bottom: Performance of the selected step-size on training loss and evaluation metrics during training.
Top:
28


Reviews:
[{"review_id": "k13LQBTyov-", "reviewer": "Reviewer_J7tc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "**Overview of this paper**\n\nThis paper studies why adaptive methods perform better than SGD in terms of convergence. Specifically, this paper aims to explore the hypothesis proposed by (Zhang et al., 2019): Adaptive methods including Adam converge faster than SGD due to the more robust gradient estimate of adaptive methods (abbreviated as the adaptivity-to-noise hypothesis latter). Through extensive experiments, it is observed that the convergence gap between Adam and SGD even gets larger when the batch size increases (and thus the noise decreases), and thus the adaptivity to the noise of adaptive optimizers can not fully explain the gap.\n\n**Summary of the experiment observations**\n\n(1). Over language tasks, the training loss gap between SGD and Adam (both best tuned) gets larger when the batch size increases.\n\n(2). Adding momentum improves the performance of optimizers, mainly in the case when the batch size is large.\n\n(3). The performance of SignGD in the small-batch regime, but improves significantly with respect to batch. Over some tasks (e.g., PTB), the performance of full-batch SignGD is comparable to that of full-batch Adam.\n\n(4). Normalized gradient descent also scales better with batch size than plain gradient descent, but less so than sign descent. Full-batch normalized gradient descent performs worse than full-batch SignGD.\n\n\n\n**References**\n\nZhang et al.,  Why are adaptive methods good for attention models?, 2019", "summary_of_the_review": "This work is the first to investigate the correctness of the adaptivity-to-noise hypothesis, which is an impactful hypothesis for why Adam converges faster than SGD. While this paper does not provide a new hypothesis, it disproves the adaptivity-to-noise hypothesis through extensive and sound experiments. I believe this result is of interest to the optimization-in-deep-learning community, and lean on acceptance of this work.", "strength_and_weaknesses": "**Strength**\n\n1. The question that the paper aims to study may be of interest to the optimization community. The adaptivity-to-noise hypothesis is impactful and its correctness is worth studying. Ruling out this hypothesis also indicates that new hypotheses need to be considered.\n\n2. The experiments are extensive and solid, thus convincing.\n\n**Weakness**\n\n1. While disproving the adaptivity-to-noise hypothesis, this paper does not provide a new hypothesis/conjecture. It is unclear why signGD works well in the large batch regime and why signGD works badly in the small batch regime.\n\n**Questions**\n\nIn (Zhang et al. 2019), it is hypothesized that adaptive methods perform better than SGD since the smoothness is not uniformly bounded but can be controlled by the gradient norm. It also proves that normalized GD can adapt to such a landscape and converge arbitrarily faster than SGD. If this was the key mechanism of the acceleration effect of adaptive methods, then clipped SGD should perform as well as Adam in the full-batch case. However, this paper shows that normalized GD performs much worse than Adam in the full-batch case. Does this mean this hypothesis is also wrong?\n\n**References**\n\nZhang et al. Why gradient clipping accelerates training: A theoretical justification for adaptivity, 2019\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WIUzNr9ypPr", "reviewer": "Reviewer_emm1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "This paper studies the performance gap between Adam and SGD at different batch sizes. It is found that the gap still exists with large batches or even full batches, which suggests the distribution of random noise may not explain this gap. By contrast, it is shown that Adam with large batches is similar to sign descent.", "summary_of_the_review": "This paper provides interesting results, that the performance gap between Adam and SGD still exists with full batches, and that Adam is similar to sign descent. On the other hand, I think more experiments can be tried to make the story more complete. Therefore currently I put this paper marginally above the acceptance threshold.", "strength_and_weaknesses": "This paper studies the important problem of why Adam performs better than SGD (especially on language tasks), and provides interesting results. Prior work argues that the performance gap might be due to heavy tail of the noise distribution; however, this paper shows that heavy-tailed-ness  may not be enough to explain the performance gap, as it still exists even with full batches. Moreover, as the batch size increases, the SGD performance almost always degrades, while Adam can sometimes do better. Finally, with full batches, it is shown that sign descent can sometimes match the Adam performance. These findings can help us understand Adam better and design more efficient algorithms.\n\nOn the other hand, I have the following suggestions:\n1. I think more hyperparameter tweaking is needed (e.g., some simple learning rate schedule). The reason is to make sure the results still hold when we have satisfactory test accuracies. For example, in Figure 11, the best test accuracy obtained for ResNet18 on CIFAR10 is below 80%, but I believe it should be easy to get 90%.\n2. In Figure 5, to support the claim that Adam is similar to sign descent, it is also nice to compare the test error for Adam and sign descent.\n2. For sign descent, in addition to moving averages of signs, it might also be interesting to consider signs of moving averages.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KTlHlRRvP9c", "reviewer": "Reviewer_AS9c", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The authors show that across a range of tasks, the performance of Adam improves more as the batch size rises than the performance of SGD. In the full batch limit, Adam continues to significantly outperform SGD on language tasks. Based on this observation, they argue that the benefits of Adam are best studied in the full-batch/deterministic limit, and that key benefit of Adam is therefore not better robustness in the presence of heavy tailed gradient noise.\n\nAdditionally, they observe that sign descent also improves considerably as the batch size rises, and that while it performs poorly for small batch sizes it achieves comparable performance to Adam on some tasks in the full batch limit. They therefore propose that studying sign descent in the full batch limit may be a useful toy model for understanding the benefits of Adam.", "summary_of_the_review": "I think this paper makes a valuable contribution to the field. However I think it could be significantly improved by improving/extending the experiments and discussion of sign descent. I therefore will score it weak accept for now.", "strength_and_weaknesses": "Strengths:\n1) The paper tells a clear story, and makes a convincing case that the key differences between Adam and SGD are best studied in the large batch/low noise regime.\n2) The observation that sign descent outperforms gradient descent in the full batch limit is quite interesting, and provides a plausible intuition for the success of Adam.\n\nWeaknesses:\n1) The sign descent experiments are not very convincing. There is still quite a significant gap between sign descent and Adam in the large batch regime on some datasets (eg Figure 5 wikitext/Squad).\n2) The authors note that the gap between SGD and Adam primarily arises on language/transformer tasks, however this observation is not explored/discussed.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3waWCrrLi9", "reviewer": "Reviewer_nxBD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "This work studies whether the heavy-tailed nature of gradient is the true cause of Adam outperforming SGD, as suggested by prior work (J. Zhang et. al., 20). The paper conducts an extensive set of experiments involving decreasing noise level of SGD/Adam via increasing the batchsize from small batch all the way to fullbatch GD. The paper makes three main observations: 1. Noise does not explain the gap between SGD and Adam since Adam still has lower training loss with full batch gradient, 2. SGD’s performance does not improve as the batchsize increases, which is a more granular version of claim 1, and 3. Adam’s success might be attributed to its behavioral similarities with signed gradient descent.", "summary_of_the_review": "The paper makes interesting findings but makes some overclaims. I would increase my score to 6 or 8 if the authors can correct these overclaims and fix other issues that I mentioned above.\n", "strength_and_weaknesses": "### Strength\n- The paper’s motivation to establish the correct assumptions for theoretical work on optimization is refreshing and extremely important.\n- The experimental procedure is carefully designed\n\n### Weakness\nIn my opinion, the major weakness of the paper is overclaiming, especially with regard to the claim about refuting “long-tailed gradient error is why Adam does better than SGD”. I will comment on each of the claims made individually.\n\n**Claim 1**: comparing figure 1 and figure 2, it does seem Adam benefits from the full batch more than SGD. This claim seems well supported.\n\n**Claim 2**: This claim only seems to hold for a subset of the experiments and does not say anything about the long-tailed nature of SGD. Further, even in Figure 3, I am not sure how I should reach the conclusion “SGD does not take advantage of the reduction in noise while Adam does”. On Squad, it seems that SGD is able to take advantage of the increased batchsize. Similarly, on PTB, SGD seems to do better when the batch size increases. The argument seems strenuous at best. Finally, in Figure B.2, it seems that Mnist and Cifar10 exhibit very different behavior even though both are supposed to not have long-tailed gradient noise according to figure 1. This casts further doubt on the claim about long-tailed gradient error.\n\n**Claim 3**: This claim does not seem supported by the figures. In figure 4, I am not sure how to get “signed GD scales better than normalized GD” from the plots. In particular, it seems to me that signed GD since the larger batch sizes have higher training loss. If I am misinterpreting the plots, please correct me and add appropriate instructions about how to read the plots.\n\nOverall, I find the plots to be difficult to read even with the help of the text. The addition of two sets of experiments for w/ and w/o momentum makes the matter worse. The momentum and no momentum plots (e.g., figure 3) should ideally be separate from each other. The dashed lines look really bad presumably because of the fact that the lines are sometimes not smooth. I would rather see a plot of the final performance against the number of each batch size rather than seeing their progress which doesn’t add anything. I think it would be more helpful to quantify how much the batchsize is correlated with training loss rather than commenting on it qualitatively.\n\nMore importantly, I believe that the paper did not fully disprove the hypothesis about heavy-tailed gradient error. In particular, I believe that what the paper showed is that “gradient noise does not explain the gap between Adam and SGD '' by showing that there is still a gap between the two even using fullbatch GD. This is somewhat a subtle point, because the paper didn’t convincingly address the issue of heavy-tailedness noise but instead removed it altogether. There exist alternative hypotheses. “Full-batch improving adam” and “heavy tail worsening sgd” can coexist. For example, noise helps gradient descent in general but SGD performs worse when the noise is heavy-tailed, or gradient noise worsens Adam, but when there is noise, Adam performs better if the noise is heavy tail. If I am wrong about this, I would be more than happy to learn how the current set of experiments do not support these possibilities.\n\nGiven how much the paper focuses on the heavy-tailed gradient noise, I believe the experimental results do not fully support the claim. The findings are still interesting and it supports the claim that the difference between Adam and SGD is deterministic, but I don’t think they fully preclude the heavy-tailed hypothesis. I would like to emphasize that I do not believe in the hypothesis myself but I believe that it is important to be careful and rigorous in scientific claims. As such, I would suggest the authors rephrase the introduction and title accordingly to reflect subtleties.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster