AGD: an Auto-switchable Optimizer using Stepwise Gradient Difference for Preconditioning Matrix
Authors: Yun Yue
Zhiling Ye
Jiadi Jiang
Yongchao Liu
Ke Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: adaptive optimizer
gradient difference
auto switch
AGD
TL;DR: We propose a novel optimizer, AGD, which incorporates the Hessian information into the precondition matrix and allows seamless switching between SGD and the adaptive optimizer.

Abstract: Adaptive optimizers, such as Adam, have achieved remarkable success in deep learning. A key component of these optimizers is the so-called preconditioning matrix, providing enhanced gradient information and regulating the step size of each gradient direction. In this paper, we propose a novel approach to designing the preconditioning matrix by utilizing the gradient difference between two successive steps as the diagonal elements. These diagonal elements are closely related to the Hessian and can be perceived as an approximation of the inner product between the Hessian row vectors and difference of the adjacent parameter vectors. Additionally, we introduce an auto-switching function that enables the preconditioning matrix to switch dynamically between Stochastic Gradient Descent (SGD) and the adaptive optimizer. Based on these two techniques, we develop a new optimizer named AGD that enhances the generalization performance. We evaluate AGD on public datasets of Natural Language Processing (NLP), Computer Vision (CV), and Recommendation Systems (RecSys). Our experimental results demonstrate that AGD outperforms the state-of-the-art (SOTA) optimizers, achieving highly competitive or significantly better predictive performance. Furthermore, we analyze how AGD is able to switch automatically between SGD and the adaptive optimizer and its actual effects on various scenarios. The code is available at https://github.com/intelligent-machine-learning/dlrover/tree/master/atorch/atorch/optimizers.

AGD: an Auto-switchable Optimizer using Stepwise Gradient Difference for Preconditioning Matrix
Yun Yue
Zhiling Ye"
Ant Group
Ant Group Hangzhou, Zhejiang, China grrhiling.yzldanteee wwt.yylllanttuu.oom com
Hangzhou, Zhejiang, China yueyun. www.yyyyyatttuu.c.omm
Jiadi Jiang
Yongchao Liu Ant Group
Ke Zhang Ant Group Beijing, China
Ant Group Hangzhou, Zhejiang, China jiadi.jjddandl jjddantgroupp.. com
Hangzhou, Zhejiang, China
.onacha..1y@ant 1w@layggroup.....mmmmm.mmmm com
yingzi zk@antgroup.coo com
Abstract
Adaptive optimizers, such as Adam, have achieved remarkable success in deep learning. A key component of these optimizers is the so-called preconditioning matrix, providing enhanced gradient information and regulating the step size of each gradient direction. In this paper, we propose novel approach to designing the preconditioning matrix by utilizing the gradient difference between steps as the diagonal elements. These diagonal elements are closely related to the Hessian and can be perceived as an approximation the inner product between the Hessian row vectors and difference of the adjacent parameter vectors. Additionally, we introduce an auto-switching function that enables the preconditioning matrix switch dynamically between Stochastic Gradient Descent (SGD) and the adaptive optimizer. Based on these two techniques, we develop new optimizer named AGD that enhances the generalization performance. We evaluate AGD on public datasets Natural Language Processing (NLP), Computer Vision (CV), and Rec- ommendation Systems (RecSys). Our experimental results demonstrate that AGD outperforms the state-of-the-art (SOTA) optimizers, achieving highly competitive significantly better predictive performance. Furthermore, is able to switch automatically between SGD and the adaptive optimizer and its actual effects various scenarios. The code is available at this link'
successive
analyze how AGD
Introduction
Consider the following empirical risk minimization problems:
min f(w) == WES
f(w; Φx),
(I)
M
where w E R" the parameter vector to optimize, {#1,.... 2 MM) is the training set, and E(w; x) is the loss function measuring the predictive performance of the parameter w the example Since is expensive to calculate the full batch gradient each optimization iteration when M is large, the
"Co-first authors with equal contributions.
hattpa://github.co ietiininlllii atorch/ optimizera
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

standard approach is to adopt mini-batched stochastic gradient, i.e.,
g(w)
Vl(ue; wx),
B
BEB
where B C {I...., } is the sample set of size |B] < M. Obviously, we have Ex())(())) = V ((w)) where p(æ)) is the distribution the training data. Equation ( is usually solved iteratively.
Assume wz is already known and let Aw W+++1 We, have
arg min f(W(+1) arg min f(Aw +wi)
AWER"
arg min f(w:) + (Aw) V(.,)) + 3 (Aww)" (w,, AWER"
1
1 (Aw)" B,Aw,
2 arg min f(w:) + (Aw) m. + 20x
AWER"
where the first approximation is from Taylor expansion, and the second approximation are from
(Aw)) B.
m, z V fww) (m, denotes the weighted average of gradient g.) and a₂ = (Aw) ( (at
denotes the step size). By solving Equation Q the general update formula is
W++11 = ut: ar B, m., t (1,
(3)
where B3 is the so-called preconditioning matrix that adjusts updated velocity of variable w, in each direction. The majority of gradient descent algorithms can be succinetly encapsulated by Equation (3. ranging from the conventional second order optimizer, Gauss-Newton method, to the standard first-order optimizer, SGD, via different combinations of B, and m. Table summarizes different implementations of popular optimizers.
Intuitively, the closer B, approxi- mates the Hessian, the faster conver- achieve
Table 1: Different optimizers by choosing different B,.
gence rate the optimizer in terms of numher of iterations, since the Hesssan method enjoys quadratic rate, whereas the gradient descent converges linearly under cer- tain conditions (Theorems 1.2.4, 1.2.5 in Nesterov (25). However, comput- ing the Hessian is computationally ex- pensive for large models. Thus, is essential to strike a balance between the degree of Hessian approximation and computational efficiency when de- signing the preconditioning matrix.
B.
Optimizer
H
GAUSS- HESSIAN
B, = H
BEGS 13
LBFGS
5
Br = diag(H)
ADAHESSIAN
NATURAL GRADIENT
B7 F Pemp
SHAMPOO 16
ADAGRAD 12
ADADELTA 35
B (Fegp)emp))
ADAM 18] ADAMW (1), AMSGRAD 28
B7 diag( Var(g.)
ADABELIEF
B,
SGD MOMENTUM
29
M
Hessian.
information matris. F Famp empirical
Fisher information matrix.
In this paper, we propose the AGD (Auto-switchable optimizer with Gradient Difference of adjacent steps) optimizer based on the idea of efficiently and effectively acquiring the information of the Hessian. The diagonal entries of AGD's ' preconditioning matrix are computed as the difference of gradients between two successive iterations, serving as an approximation of the inner product between the Hessian row vectors and difference of parameter vectors. In addition, AGD is equipped with an adaptive switching mechanism that automatically toggles its preconditioning matrix between SGD and the adaptive optimizer, governed by threshold hyperparameter 5 which enables AGD adaptive to various scenarios. Our contributions can be summarized as follows.
We present a novel optimizer called AGD, which efficiently and effectively integrates the infor- mation of the Hessian into the preconditioning matrix and switches dynamically between SGD and the adaptive optimizer. We establish theoretical results convergence guarantees for both non-convex and convex stochastic settings.
We validate AGD on six public datasets: two from NLP (IWSLT14 6 and PTB 23 ), two from CV (Cifarl0 [9 and ImageNet (30]), and the rest two from RecSys (Criteo [ and Avazu (3). The experimental results suggest that AGD is on par with or outperforms the SOTA optimizers.
We analyze how AGD able to switch automatically between SGD and the adaptive optimizer, and assess the effect of hyperparameter 8 which controls the auto-switch process in different scenarios.

---

Notation
We use lowercase letters to denote scalars, boldface lowercase to denote vectors, and upperease letters to denote matrices. We employ subscripts to denote a sequence of vectors. e.g., 2i..... Ry where and one additional subscript used for specific entry of vector, e.g., F2,s denotes i-th element of xt. For any vectors æ; y E IK",, we write x" y or æ y for the standard inner product, zy for element wise multiplication, z/ y for element- division, v for element- square root, x² for element-wise square, and max(æ, y) for element- maximum. Similarly, any operator performed between a vector z E IR" and a scalar с E R, such as max( c), is also element-wise We denote ||ж||| ||>||| v (xx, æ) for the standard Euclidean norm, ||>||| E, | for the & norm, and || | = max; |z:|] for the norm, where 2; is the i-th element æ.
t [T] := (1,2...., ].
Let f(w) be the loss function of the model at t-step where ur R We consider m, as Exponential Moving Averages (EMA) of gi throughout this paper, i.e.,
m, = 81m--1 + +1 B1)g: (1 B1) Σ 90-1-199
(4)
where 31 E (0,1) 1) is the exponential decay rate.
Related work
ASGD (36] leverages Taylor expansion to estimate the gradient at the global step in situations where the local worker's gradient delayed, by analyzing the relationship between the gradient difference and Hessian. To approximate the Hessian, the authors utilize the diagonal elements of empirical Fisher information due to the high computational and spatial overhead of Hessian. ADABELIER [39] employs the EMA of the gradient as the predicted gradient and adapts the step size by scaling it with the difference between predicted and observed gradients, which can be considered as the variance of the gradient.
Hybrid optimization methods, including ADABOUNT 22 and SWATS 17], have been proposed to enhance generalization performance by switching adaptive optimizer to SGD. ADABOUND utilizes learning rate clipping on ADAM, with upper and lower bounds that are non non-increasing and non-decreasing functions, respectively. One can show that it ultimately converges to the learning rate of SGD. Similarly, S SWATS also employs the clipping method, but with constant upper and lower bounds.
3 Algorithm
3.1 Details of AGD optimizer
Algorithm AGD
Optimal Adam
1: Input: parameters 31, 32, 8, wi IR",, step size
3
or, initialize mg 0, bo
2
2: for 1 to T do
3: 9: f((:))
4: m, + 31m;1
+ (1 31)g:
0
mi
= 1
-1
5: 8:
m
1>1 1 1-8 -tT
m
1-
6:
32b:-1
(1
32 )
7: Wr+11 W: 04 T-
11
m
44
2
max v b. bb 1-
8: end for
Figure 1: Trajectories of AGD and Adam in the Beale function.
Algorithm I summarizes our AGD algorithm. The design of AGD comes from two parts: gradient difference and auto switch for faster convergence and better generalization performance across tasks.
3

---

Gradient difference Our motivation stems from how to efficiently and effectively integrate the information of the Hessian into the preconditioning matrix. Let Aw w w,-1 and ; denote the i-th element of Vs. From Taylor expansion or the mean value theorem, when ||Aw]] is small, we have the following approximation.
v.f(w,) Vvf(w))-Vi((w--))) & VV.f(w)) Aw.
means the difference of gradients between adjacent steps can be an approximation the inner product between the Hessian row vectors and the difference of two successive parameter vectors. To illustrate the effectiveness of gradient difference in utilizing Hessian information, we compare the convergence trajectories of AGD and Adam the Beale function. As shown in Figure I see that AGD converges much faster than Adam; when AGD reaches the optimal point, Adam has only covered about half of the distance. We select the two most representative points on the AGD trajectory in the figure, the maximum and minimum points of [[V flll diag H)) HIll Il. to illustrate how AGD accelerates convergence by utilizing Hessian information. At the maximum point (A), where the gradient is relatively large and the curvature is relatively small ['V = 22.3, [|diag(H]li
25.3), the step size of AGD is 1.89 times that of Adam. At the minimum point (B), where the gradient is flli 0.2, [diag(())]
relatively small and the curvature is relatively large ()
34.8), the step size decreases prevent it from missing the optimal point during the final convergence phase.
To approximate V (ww)), we utilize m - {1) instead of gr. as the former provides an unbiased estimation of ((r,) with lower variance. According Kingma and Ba [8] we have 1-31
Elgr], where the equality is satisfied if {g:} is stationary. Additionally, assuming {g:} is strictly stationary and Cov 9,) = Of i + for simplicity and B1 E (0, 1), we observe that
Var
my 8
1
Var (1 (1-
Σ i=1
9:
(1+ (1) B1) Varlgd < &Vallg)- (1 (1 B1)
(1
3
Now, we denote
m1/(1-1) (1-B1) 32)
t=1,
$: =
m./(1 (1) m. 1 -1-1) 1>
and design the preconditioning matrix B, satisfying
B = (iiA((EMM(sss]] s25 8 ()/(1)8)) 82).
where 32 represents the parameter of EMA and bias correction is achieved via the denominator.
Note that previous research, such as the one discussed in Section 2 by Zheng et al. [36), has acknowledged the correlation between the difference of two adjacent gradients and the Hessian. However, the key difference is that they did not employ this relationship to construct an optimizer. In contrast, our approach presented this paper leverages this relationship to develop an optimizer, and its effectiveness has been validated in the experiments detailed in Section
Auto switch Typically a small value is added to B, for numerical stability, resulting in B, + cI. However, in this work we propose to replace this with max (B,, öII), where we use a different notation ó to emphasize its crucial role in auto-switch mechanism. In contrast to e, can be a relatively large (such as le-2). If the element of 6, := / b./ (1- .35 exceeds 6, AGD (Line of Algorithm takes confident adaptive step. Otherwise, the update is performed using EMA, i.e., my with constant scale of a2 / }.). similar to SGD with momentum. It's it's worth noting that, AGD can automatically per-parameter basis the training progresses.
switch modes
Compared to the commonly used additive method, AGD effectively eliminates the noise generated by during adaptive updates. In addition, AGD offers an inherent advantage of being able to generalize across different tasks by tuning the value of 8, obviating the need for empirical choices among a plethora of optimizers.

---

3.2 Comparison with other optimizers
Comparison with AdaBound As noted in Section 2 the auto-switch bears similarities to AdaBound [22] in its objective to enhance the generalization performance by switching to SGD using the clipping method. Nonetheless, the auto-switch's 's design differs significantly from AdaBound. Rather than relying solely on adaptive optimization in the early stages, AGD has the flexibility to switch seamlessly between stochastic and adaptive methods, as we will demonstrate in Section 4.5 In addition, AGI) outperforms AdaBound's is across various tasks, as we will show in Appendix A.2
100
Comparison with AdaBelief While in princi- ple our design is fundamentally different from that of AdaBelief [39], which approximates gra- dient variance with its preconditioning matrix, do see some similarities in our final forms. Compared with the denominator of AGD, the denominator of AdaBelief 8, = gr m, 1-9 (m, - 1 lacks bias correction for the subtracted terms and includes multiplication factor of - In addition, we observe that AGD exhibits superior stability compared to Ad- aBelief. As shown in Figure 2 when the value of e deviates from 1e-8 by orders of magnitude, the performance of AdaBelief degrades signif- icantly; in contrast, AGD maintains good stabil- ity wide range of 5 variations.
Tost accuraoy (59
85
AGD, k=0.001
AGD. k=0 000
AGD, 1=0.01
70
AdaBelief, I==00001
AdaBelief, lm0.005
AdaBelief, Ir-0.01
10
10
10
10"
10"
10
Figure 2: Comparison of stability between AGD and AdaBelief relative to the parameter 5 (or for ResNet32 on Cifar10. 10. AGD shows better stability over wide range of (or e) variations than Ad- aBelief.
3.3 Numerical analysis
In this section, we present a comparison between AGD and several SOTA optimiz- ers on three test functions. We use the parameter set- tings from Zhuang et al. [9]. where the learning rate is set to le-3 for all adaptive optimizers, along with the same default val- ues of (or 8) (le-8) and be- tas (8, 0.9, B2 0.999). For SGD, we set the mo- mentum to 0.9 and the leam- ing rate to le-6 to ensure numerical stability. As shown in Figure 3 AGD exhibits promising results by firstly reaching the optimal points in all experiments before other competitors. In addition, conduct a search of the largest learning rate for each optimizer with respect to the Beale function, and AGD once again stands out as the strongest method. More details the search process can be found in Appendix A.3
Drinsd
Oypnd
Daaad Fanesta
502 NoWAELL
(a) f(x v)
(b) Beale
(c) Rosenbrack
Figure 3: Trajectories of different optimizers three test functions,
where f(z, y) = (ar 4) + (r y) /10. We also provide animated
versions at
Experiments
4.1 Experiment setup
We extensively compared the performance of various optimizers on diverse learning tasks in NLP, CV, and RecSys; only vary the settings for the optimizers and keep the other settings consistent in this evaluation. To offer a comprehensive analysis, we provide a detailed description of each task and the optimizers' efficacy in different application domains.
NLP:: We conduct experiments using Language Modeling (LMM) on Penn TreeBank 23 and Neural Machine Translation (NMT) on IWSLT14 German-to-Engee Eng-nss (De-En) [6] datasets. For the LM task,
5

---

we train 1, 2, and 3-layer LSTM models with batch size of 20 for 200 epochs. For the NMT task, we implement the Transformer small architecture, and employ the same pre-processing method and settings as AdaHessian [4, including length penalty of 1.0, beam size of 5, and max tokens of 4096. We train the model for 55 epochs and average the last 5 checkpoints for inference. We maintain consistency in our learning rate scheduler and warm-up steps. Table 2 provides complete details of the experimental setup.
CV: We conduct experiments ing ResNet20 and ResNet32 on the
Table 2: Experiments setup.
us-
Task
Dataset
Model
Train
Val/Test
Params
I-layer L.TTM
5.3M
Cifar10 [9] dataset, and R on the ImageNet 330 dataset, as detailed in Table 2 It is worth noting that the number of param- eters of ResNet18 is significantly larger
NLP-LM PTB
2-layer LSTM
0.93M
730K/82K
13.6M
3-layer LSTM
24.2M
NLP-NMT IWSLT14 De-En Transformer small
153K
7K/7K
36.7M
Cifarl0
ResNec20/ResNee32
50K
10K
0,27M/0.47M
CV
ImageNet
ResNet18
1.28M
50K
11.6MM
Avazu
MLP
36 36.2M
4.2M
151M
RecSys
Criteo
DCN
39.4M 6.6M
270M
than that of ResNet20/32,, stemming from inconsistencies in ResNet's naming conventions. Within the ResNet architecture, the consistency in filter sizes, feature maps, and blocks maintained only within specific datasets. Originally proposed for ImageNet, ResNet18 is more complex compared to ResNer20 and ResNet32, which were tailored for the less demanding Cifar 10 dataset. Our training process involves 160 epochs with a learning rate decay epochs 80 and 120 by a factor of 10 for Cifar10, and 90 epochs with a learning rate decay every 30 epochs by a factor of 10 for ImageNet. The batch size for both datasets is set 256.
We conduct experiments on two widely used datasets, Avazu 3 and Criteo [. which contain logs of display ads. The goal is to predict the Click Through Rate (CTR). We use the samples from the first nine days of Avazu for training and the remaining samples for testing. We employ the Multilayer Perceptron (MLP) structure (a fundamental architecture used in most deep CTR models). The model maps each categorical feature into a 16-dimensional embedding vector, followed by four fully connected layers of dimensions 64, 32, 16, and 1, respectively. For Criteo, we use the first 6/7 of all samples as the training set and last 1/7 as the test set. We adopt the Deep & Cross Network (DCN) 332 with an embedding size of 8, along with two deep layers of size 64 and two cross layers. Detailed summary of the specifications can be found in Table For both datasets, we train them for one epoch using a batch size of 512.
RecSys:
Optimizers to compare include SGD (2),, Adam 18] Adam 21), AdaBelief [39] and AdaHessian 34]. To determine each optimizer's 's hyperparameters,
adopt the parameters suggested in the literature of AdaHessian and AdaBelief when the experimental settings are identical. Otherwise, we perform hyperparameter searches for optimal settings. A detailed description of this process can be found in Appendix A. For our NL.P and CV experiments, we utilize GPUs with the Py PyTorch framework (26), while RecSys experiments are conducted with three parameter servers and five workers in the TensorFlow framework [ To ensure the reliability of our results, we execute each experiment five times with different random seeds and calculate statistical results.
4.2 NLP
We report the perplexity (PPL, lower is better) and case- inss-insensitive BiLingual Evaluation Understudy (BLEU, higher is better) score on test set for LM and NMT tasks, respectively. The results are shown in Table For the LM task on PTB, AGD achieves the lowest PPL in all 1,2.3-layer LSTM experiments, as demonstrated in Figure For the NMT task on IWSLT14, AGD is on par with AdaBelief, but outperforms the other optimizers.
4.3 CV
Table 4 rreports the top-1 accuracy for different optimizers when trained on Cifar and ImageNet. remarkable that AGD outperforms other optimizers on both C0 and ImageNet. The test accuracy ([p + o)) curves of different optimizers for ResNet20/32 on C0 and ResNet18 on

---

Table 3: Test PPL and BLEU score for LM and NMT tasks. + is reported in AdaHessian 34
Dataset
PTB
IWSIT14
Metric
PPL. lower is better
BLEU, higher better Transformer
Model
I-layer LSTM
2-layer LSTM
3-layer LSTM
SGD
85.36 :: (3:433(45 (-4.13)
67.26 .17 1-42)
63.68 + .17 (-79)
28.37 + (57((47.37))
Adam
84.50 : (-3.27)
67.01 1.11 1
64.45 26 (-3.56)
32.93 f 26 (+3.01)
AdamW
88.16 = (-6.98)
95.25 (-29.41)
102.61 + 1.13 (-41.72)
35.82 .06 (+0.12)
AdaBelief
84.40 1:
3.17)
66.69 1 0.85)
61.34 .11 0.45)
35.93 .08 (10.01)
AdaHessian
88.62 = .15 (-7.39)
73.37 + (-7.53)
69.51 .19 (-8.62)
35.79 06+((+015))
AGD
81.23 .17
65.84 1 .18
60.89 .09
35.94 1.11
105
100
105
S0D
Ada
Adam AdamiM
100
AdarrW
AdamT
45
50
151
85
70-
60-
Epoch
Eaach
Epoch
(a) I-layer
(b) 2-layer
(c) 3-layer
Figure 4: Test PPL ((1 + o on Penn Treebank for 1,2,3-layer LSTM.
0.9
0.9
0.81
0.7
0.7
0.5
111
146
3k
LEC
8.4
0.6
5:D
Ada
Ass
0.5
AdamtW
Adart/
0.2
AG2
A00
ADD
20
40
60
50 Epoch
100
120
140
160
20
40
60
80 Epoch
100
120
140
160
0.1
40
Epoch
(a) RosNet20 on Cifar10
(b) ResNer32 on Cifar10
(c) ResNet18 on ImageNet
Figure 5: Test accuracy (lμ+ + o)) of different optimizers for ResNet20/32 on Cifar10 and ResNet18 on ImageNet.
ImageNet are illustrated in Figure Notice that the numbers of SGD and AdaHessian on ImageNet are lower than the numbers reported in original papers 77 34), which were run only once (we average multiple trials here). AdaHessian can achieve 70.08% top-1 accuracy in Yao et al. [34] while we
report 69.57 + 0.12%. Due to the limited training details provided in Yao et al. (34] it is difficult for us to explain the discrepancy. However, regardless of which result of AdaHessian is taken, AGD outperforms AdaHessian significantly. Our reported top-1 accuracy of SGD is 69.94 + 0.10%, slightly lower than 70.23% reported in Chen al. [7]. We find that the differences training epochs, learning rate scheduler and weight decay rate are the main reasons. We also run the experiment using the same configuration as in Chen et al. 77, and AGD can achieve 70.45% accuracy at Ir 4e-4 and 8= = le-5, which is still better than the 70.23% result reported in Chen et al. (7]
We also report the accuracy of AGD for R8 on Cifar for comparing with the SOTA results Fl which is listed in Appendix A.5 Here we clarify again the ResNet naming confusion. The test accuracy of ResNet18 8 on Cifar TO training with AGD above 95%, while ResNet32 about 93% since ResNet18 is much more complex than ResNet32.
4.4 RecSys
To evaluate the accuracy of CTR estimation, we have adopted the Area Under the receiver-operator Curve (AUC) as our evaluation criterion, which is widely recognized as a reliable measure (15). As stated in Cheng et al. [00, Wang et al. [2] Ling et al. [20] Zhu et al. [38] even an absolute
http://ppeessiiiiooommmtceeeeeee 18-

---

Table 4: Top-1 I accuracy for different optimizers when trained on Cifar 10 and ImageNet.
Table Test AUC for different optimizers
when trained on Avazu and Criteo.
Ciaa10
ImageNet ResNet88
Model
ResNer20
RosNes32
Model
SGD
92.14 + 14 (4-0211 93. = 07 (4-0.02) 69.94 = 10 (4004111 SGD
0.7463 + .000 (4-1-94)) 0.7296 = .0067 (+72.75))
Adam
90.46 + 20 (4-889) 91.54
(4..8) 64.03 + 3604--882
Adam
0.7458 + .0010 (4-2250 0. 8023 + 0002 (4-0.0%)
AdamW
92.12 1: (4.0)) 92.72 1 0 (40.40)
69.11 = .17 6++1 24) Adalielief
0.7467 1: .009 (+133)) 0.8022 1 .0002 (-0.15)
AdaRellef
92.19 + (4-0.)))) 92:90
(4-0.2)
70.20 = (400.5)
AdaHossion
D.7434 + .0006 (4-4.68) 0.8004 = .0005 (-1.06)))))
Addttesiann
92.27 (H0.08) 92.91 01221))221
89.57 (12(40079))
AGD
0.7480 .00088
0.8023 + .0004
AGD
92.86
244
98.12 +
70.35 + .17
improvement of 1% in AUC can be considered practically significant given the difficulty of improving CTR prediction. Our experimental results in Table that AGD can achieve highly competitive or significantly better performance when compared to other optimizers. In particular, on the Avazu task, AGD outperforms all other optimizers by more than 1%o. On the Criteo task, AGD performs better than SGD and AdaHessian, and achieves comparable performance to Adam and AdaBelief.
4.5
The effect of
Looc
(a) ResNeti8 on ImageNet
(b) Transformer IWSLT14
(c) 2-layer LSTM PTB
(d) DCN Critco
Figure 6: The distribution of b, on different epochs/steps. The colored area denotes the ratio of b, in the corresponding interval. The values of & for R on ImageNet, Transformer on IWSLT14, 2-layer LSTM on PTB, and DCN on Critco are 1e-5, 1e-14, le-5 and 1e-8, respectively.
In this section, we aim to provide a comprehensive analysis of the impact of on the training process by precisely determining the percentage of b, that Algorithm truncates. To this end, Figure shows the distribution of b, across various tasks under the optimal configuration that we have identified. The black dot on the figure provides the precise percentage of b, that truncates during the training process. Notably, a lower percentage indicates higher degree of SGD-like updates compared to adaptive steps, which can be adjusted through 8.
As SGD with momentum generally outperforms adaptive optimizers on CNN tasks 34
39
confirm this observation as illustrated in Figure 6a AGD behaves more like SGD during the initial stages of training (before the first learning rate decay the 30th epoch) and switches to adaptive optimization for sine-tuning. Figure 6b indicates that the parameters taking adaptive updates are dominant, expected because adaptive optimizers such AdamW preferred in transformers. Figure [oc| demonstrates that most parameters update stochastically, which explains why AGD has similar curve to SGD in Figure 4b before the 100th epoch. The proportion of parameters taking adaptive updates grows from 3% to % afterward, resulting in a better PPL in the fine-tuning stage. Concerning Figure 6d the model of the RecSys task trains for only one epoch, and AGD gradually switches to adaptive updates for a better fit to the data.
4.6
Computational cost
We train a Transformer small model for IWSLT14 on a single NVIDIA P100 GPU. AGD is comparable to the widely used Adam optimizer, while significantly outperforms AdaHessian in terms of memory footprint and training speed, As result, AGD can drop-in replacement for AdamW with similar computation cost and better generalization performance.

---

Table Computational cost for Transformer small.
Optimizer
Memory
Time per Epoch
Relative time to Adam
SGD
5119 MB
230
0.88x
AdamW W
5413 MB
260
1.00x
AdaHessian
8943 MB
750s
2.88x
AGD
5409 MB
278
1.07x
5 Theoretical analysis
Using the framework developed in Reddi et al. (28), Yang et al. [33] Chen et al. [9], Zhou et al. 337, we have the following theorems that provide the convergence in non-convex and convex settings. Particularly, we use S1. to replace 31, where 31, is non-increasing with respect to
Theorem 1. (Convergence in non-convex settings) Suppose that the following assumptions are satisfied:
1. f is differential and lower bounded, i.e. f(w") > -00 where w" is an optimal solution. f is also L-smooth, ie., Yu, v E IR.", we have f(u)) S f(v) (Vf(v), u) + 11122
2. At step I, the algorithm can access a bounded noisy gradient and the true gradient is bounded, i.e..
|19ul1so S f f loo I Go Vt E [T]. Without loss of generality, we assume Goc 2 5.
3. The noisy gradient is unbiased and the noise is independent, i.e, 9: Vf(w)) + Se. E(G(] = and Çi is independent of Sj if j.
4. at = a/vi, BI. is non-increasing satisfying BLE S B1 E (0,1), 32 E [0,1) and b S 1 Vi E [m].
Then Algorithm 7 vields
log T VT /2 VT v2
Σr
01(31,: - (1,411 (5)
min E LETT]
+ Cs
+ +C₂
VT v2
where Cs, Ca and Cs are defined as follows:
Go
nG
(6 8La) + aBin
C3 a(1 31)2(1 B2)
[((w)) - f(w=)
(1 B1 )582
(1 8,)
15LnG3
nG3
C 2(1 -
((1-B2)2((1. (2) - -31)20822 Cg a01-1111 -31)s(1 - (0:1(1)))66
The proof of Theorem is presented in Appendix B There are two important points that should be noted: Firstly, in assumption 2, we can employ the gradient norm clipping technique to ensure the upper bound of the gradients. Secondly, in assumption 4, by,5 S b2+1,s Vi E [n], which is necessary for the validity of Theorems Tand[] may not always hold. To address this issue, we can implement the AMSGrad condition (28 by setting be+1 = max(b,+1- b.). However, this may lead to potential decrease in the algorithm's 's performance in practice. The more detailed analysis is provided in Appendix A.4. From Theorem [
we have the following corollaries.
Corollary 1. Suppose 31,e = ///VI, we have
log T
Cra log T
[[]]V/(w::]]]) < Co EE(T]
min
VT V2 +C4
+
VT
V2
B vT /2
where Cs. Ca and Cs are the same with Theorem
The proof of Corollary caan be found in Appendix C
Corollary 2. Suppose S1, = 31, Vt E [T]. we have
1
log T VT
min E ( C3 VT 2 E
C
2
where C3s and C2 are the same with Theorem 7

---

Corollaries D and 2 imply the convergence (to the stationary point) rate for AGD is O T/ VT)
in
non-convex settings.
Theorem 2. (Convergence in convex settings) Let {we) ) be the sequence obtained by AGD (Algorithm
P.. ar = -a/ Lt, B1.t is non-increasing satisfying B1 S 31 E [0. 1), B2 E [0, 1), bt. S b Vi E ( and [ S Go, Vi E [T]. Suppose fe(2r) convex for all E [T), u² an optimal solution
of Ei=1 fe(w), i.e., w0 = arg wirl Lt= Se(w) and there exists the constant Doo such that m l|w, w"l loc I Doo. Then we have the following bound on the regret
(f((w)) f((w")) B-
1
CIVT+
B11 nD + +C2VT)
201
where C₁ and C2 are defined as follows:
n n22G + D)
naG2
(
1
C1 = 20 1 32 3,
C2 (1 (1-33 -1)3
1+
8v1 B2
The proof of Theorem given in Appendix D To ensure that the condition max ||w w" moo S Doo holds, we can assume that the domain W C R is bounded and project the sequence
--
{wi} onto W by setting w++1 11w wi
From Theorem 2
maxl max(vb.. 6
have the following corollary.
Corollary 3. Suppose B1,t B1/t, we have
[(((u)) - f((ww))w)) - 1- 3 31
(GVT+ nD2 avl 32
VT CaVT).
where C1 and C2 are the same with Theorem
2
The proof of Corollary 3 given in Appendix Corollary implies the regret O(VT) and can achieve the convergence rate O(I/VT) in convex settings.
Conclusion
In this paper, introduce novel optimizer, AGD, which incorporates the Hessian information into the preconditioning matrix and allows seamless switching between SGD and the adaptive optimizer. We provide theoretical convergence rate proofs for both non-convex and convex stochastic settings and conduct extensive empirical evaluations on various real-world datasets. The results demonstrate that AGD outperforms other optimizers in most cases, resulting in significant performance improvements. Additionally, we analyze the mechanism that enables AGD to automatically switch between stochastic and adaptive optimization and investigate the impact of the hyperparameter & for this process.
Acknowledgement
We thank Yin Lou for his meticulous review of our manuscript and for offering numerous valuable suggestions.
References
[1] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek Gordon Murray, Benoit Steiner. Paul Tucker. Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: A system for large-scale machine learning. In Kimberly Keeton and Timothy Roscoe, editors. 12th USENIX Symposiun on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016, pages 265-283. USENIX Association, 2016.
[2] Shun-ichi Amari. Natural gradient works efficiently in learning. Neural Comput., 10(2):251-22 276, 1998. doi: 10.116//0999777990000077774
10

---

[3] Avazu, Avazu click-through rate httpp//////wwe.agge.cc.cc/////// pte.ecccciirreio/
data 2015.
[4] Charles G. Broyden. The convergence of a class of double-rank minimization algorithms. Journal of the Institute of Mathematics and Its Applications. 6:6-90. 1970. doi: 10. (0.1093//mmaa/6... 1.76.
[5] Richard Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. A limited memory algorithm for bound constrained optimization. SIAM J. Sci. Comput., 16(5): 190-1208, 1208, 1995. doi: 10.1 10.1137/0916069
[6] Mauro Cettolo, Jan Nichues, Sebastian Stüker, Luisa Bentivogli, and Marcello Federico. Report the 11th IWSLT evaluation campaign. In Proceedings of the 11th International Workshop on Spoken Language Translation:
Evaluation Campaign, pages 2-17, Lake Tahoe, California, December 4-5 2014.
[7] Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang. Yuan Cao, and Quanquan Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. pages 3239-3247, 07 2020. doi: 10. 10.24963/jccai. 2...63//aai22220/444... 2020/448.
[8] Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang. Yuan Cao, and Quanquan Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI ijcai.org, 2020. doi: 10. 20.22466/ieai.2222000 2020/452.
2020, pages
[9] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of A class of adam-type algorithms for non-convex optimization. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, OpenReview.net, 2019.
[10] Hen Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, Rohan Anil, Zakaria Haque, Lichan Hong, Vihan Jain, Xiaobing Liu, and Hemal Shah. Wide & deep learning for recommender systems. In Alexandros Karatzoglou, Balázs Hidasi, Domonkos Tikk, Oren Sar Shalom, Haggai Roitman, Bracha Shapira, and Lior Rokach, editors, Proceedingy of the Ist Workshop on Deep Learning for Recommender Syxtems, DLRS @ RecSys 2016, Boston, MA, USA, September 15, 2016, pages 7-10. ACM, 2016. doi: 10. 2988450. 2988454.
[11] Criteo. Criteo display ad challenge. advertising- challenge-dataset) 2014.
http://laab..rrboooom//////////2
[12] John Duchi, Flad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 2011. doi: 10.5555/ 2022048.
[13] R. Fletcher. A new approach to variable metric algorithms. Comput. J., 13(3)311-322, 1970. doi: 10. 1093/comjj//11.33.317
[14] Donald Goldfarb. family of variable metric updates derived by variational means. Mathematics of Computation, 24(109);23-26, 1970. doi: 10. 1090/50025-5718. 1970-0258249-6.
[15] Thore Graepel, Joaquin Quiñonero Candela, Thomas Borchert, and Ralf Herbrich. Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft's bing search engine. In Johannes Fürnkranz and Thorsten Joachims, editors, Proceedings of 27th International Conference on Machine Learning (ICML-10), 10), June 21-24, 2010, Haifa, Israel, pages 13 20. Omnipress, 2010.
[16] Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimization. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan. Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 1837-1845. PMLR, 2018
[17] Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam to SGD. CoRR, 0tbs//711.0771 2017.
[18] Diederik P. Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations, ICLR 15, San Diego CA. USA, 2015.
[19] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton, Cifar- 10 (canadian institute for advanced research). http:://www.c..toooneeeee wdw. wwteekrii//////////e/aa/aadaai cifar htmll 2009.
[20] Xiaoliang Ling, Weiwei Deng, Chen Gu, Hucheng Zhou, Cui Li, and Feng Sun. Model ensemble for click prediction in bing search ads. In Rick Barrett, Rick Cummings, Eugene Agichtein, and Evgeniy Gabrilovich, editors. Proceedings of the 26th International Conference on World Wide Web Companion. Perth, Australia, April 3-7, 2017, pages 689-698. ACM, 2017. doi: 10.1145/3041021.1 3054419..
11

---

[21] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In 7th International Conference Learning Representations, ICLR 2019, New Orleans. LA. USA. May 6-9, 2019. OpenReview.net, 2019.
[22] Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. In 7th International Conference on Learning Representations. ICLR 2019, New Orleans, LA. USA, May 6-9, 2019. OpenReview.net, 2019.
[23] Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large annotated corpus of English: The Penn treebank. June 1993.
[24] Thomas Moreau, Mathurin Massias, Alexandre Gramfort, Pierre Ablin, Pierre-Antoine Bannier, Benjamin Charlier, Mathieu Dagréou, Tom Dupré la Tour, Ghislain Durif, Cassio F. Dantas, Quentin Klopfenstein. Johan Larsson, En Lai, Tanguy Lefort, Benoit Malézieux, Badr Moufad, Binh Nguyen, Alain Rako- tomamonjy. Zaccharie Ramzi, Joseph Salmon, and Samuel Vaiter. Benchopt: Reproducible, efficient and collahorative optimization henchmarks. 2022.
[25] Yurii E. Nesterov. Introductory Lectures on Convex Optimization A Basic Course, volume 87 of Applied doi: 10. 1-97778---419-885555 URL
Optimization. Springer, 2004, ISBN 978- 978-1-4613-44 1-466--466911..
https://dol.org/// http:///...oo/111110/////////// 1007/978-7179900 1-419 1144119-880 8853-
[26] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer. James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, pigh-performance deep learning library. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neurul Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 8024-8035, 2019.
[27] Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964. doi: 1016//144 11.10060041--55556444000000 5553(6699111335555
[28] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In Proceedings of 6th International Conference on Learning Representations, ICLR '18 Vancouver, BC, Canada, 2018. OpenRoview.net.
[29] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[30] Olga Russakovsky. Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (ICCV), 115(3):211-52) 2015. doi: 10. 10.7//
[31] David F. Shanno. Conditioning of quasi-newton methods for function minimization. Mathematics of Computation,
1970. doi: 10. 10.1000/50025- -71---7777--9111-1-11111 0770-0274229-X X.
[32] Ruoxi Wang, Bin Fu, Gang Fu, and Mingliang Wang. Deep & cross network for ad click predictions. In Proceedings of the ADKDD 17, Halifax, NS, Canada, August 13 17, 20/7, pages 12:1-12:7. ACM, 2017. doi:
3124754.
[33] Tianbao Yang. Qihang Lin, Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. CoRR, abs//164.03257V2. 2016.
[34] Zhewei Yao, Amir Gholami, Sheng Shen, Kurt Keutzer, and Michael W. Mahoney, ADAHESSIAN: an adaptive second order optimizer for machine learning. CoRR, abs/2006.007 000119 2020.
[35] Matthew D. Zeiler. Adadelta: An adaptive learning rate method, CoRR, abs/1212.5701, 2012.
[36] Shuxin Zheng, Qi Meng, Taifeng Wang, Wei Chen, Nenghai Yu. Zhiming Ma, and Tie- Yan Liu. Asyn- chronous stochastic gradient descent with delay compensation. In Doina Precup and Yee Whye Teh, editors. Proceedings of 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW Australia, 6-11 August 2017, volume 70 Proceedings of Machine Learning Research, pages 4120-4129. PMLR, 2017.
[37] Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. CoRR, abs/1808.0566 2018.
12

---

[38] Jieming Zhu, Jinyang Liu, Shuai Yang. Qi Zhang, and Xiuqiang He. Open benchmarking for click-through rate prediction. In Gianluca Demartini, Guido Zuccon, Shane Culpepper, Zi Huang, and Hanghang Tong, editors, CIKM '21: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 1 5, 2021, pages 7759-7769. ACM, 2021. doi: 10.1145/3459637.38 3482486, URL httphhttp:///o....o org/ 10.1///011115111 045444/33555377.8 3482486
[39] Juntang Zhuang. Tommy Tang. Yifan Ding. Sekhar C. Tatikonda, Nicha C. Dvornek, Xenophon Pa- pademetris, and James S. Duncan. Adabelicf optimizer: Adapting stepsizes by the helief in observed gradients. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lim, editors, Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Procexsing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020.
13

---

Appendix
A Details of experiments
A.1 Configuration of optimizers
In this section, provide thorough description of the hyperparamettess used for different optimizers across ious tasks. For optimizers other than AGD, we adopt the recommended parameters for the identical experimental setup as indicated in the literature of AdaHessian (34) and AdaBelief [39] In cases where these recommendations are not accessible, we perform a hyperparameter search to determine the optimal hyperparameters.
NLP
SGD/Adam/ daadddd//mmmmmm W: For the NMT task, we report the results of SGD from AdaHessian 24 and search learning rate among (Se-5, le-4, 5e-4, 1e-3] and epsilon in Il-11, 10-10, 1e-8, 1e-6, le-4] for Adam/Adam and for both optimizers the optimal learning rate/epsilon is Se-4/le-12. For the LM task, we follow the settings from AdaBelief [39], setting learning rate to 30 for SGD and 0.001 for Adam/AdamW while epsilon to lc- 12 for Adam/Adam when training I-layer LSTM. For 2-layer LSTM, we conduct similar search with learning rate among (1c-4, 5e-4, 1c-3, 2c-2] and epsilon within { (1c-12, 1c-10, 1c-8, 1c-6, 1c-4), and = 1c-8/le-4 for Adam/AdamW, For 3-layer LSTM,
the best parameters are learning rate 1e-2 and epsilon learning rate = 1e-2 and epsilon = 1e-8 are used for Adam/AdamW.
AdaBelicf: For the NMT task we use the recommended configuration from the latest implementation for transformer. We search learning rate in (5e-5, Ic-4, 5c-4, lc-3) and epsilon in (1c-16, le-14, 1c-12, 1c-10, 1c-8), and the best configuration is to set learning rate as 5c-4 and epsilon as lc-16. We adopt the same LSTM experimental setup for the LM task and reusc the optimal settings provided by AdaBclicf (39), except for 2-layer LSTM, where search for the optimial learning in Ie-4, Se-4, 1e-3, 1e-2] and epsilon in (1e-16, le-14, 1e-12, le-10, 1e-8). However, the best configuration identical to the recommended.
AdaHessian: For the NMT task, we adopt the same experimental setup as in the official implementation For LM task, search the learning rate among (le-3, 1c-2, 0.1, 1) and hessian power among (0.5, 1, 2). We finally select 0.1 for learning rate and 0.5 for hessian power for l-layer LSTM, and 1.0 for learning rate and 0.5 for for hessian power for 2.3-layer LSTM. Note that AdaHessian appears to overfit when using learning rate 1.0. Accordingly, we also try to decay its learning rate at the 50th/90th epoch, but it achieves a similar PPL.
AGD: For the NMT task, we search learning rate among (5e-5, le-4, 5e-4, 1e-3) ) and ō among (le-16 16, le- 14, le- 12, le-10, 10, Ie-8). We report the best result with learning rate 5e-5 and ó Ie- 1e-14 for AGD, For the LM task, we search learning rate among (le-4, 5e-4, 1e-3, 5e-3, 1e-2] and 6 from le- 16 to le-4, and the best settings for learning rate (6) is 5e-4 (Ic-10) and 1e-3 (1c-5) for 1-layer I.STM (2,3-layer LSTM).
The weight decay is set to le-4 (1.2e-6) for all optimizers in the NMT (LM) task. For adaptive optimizers, we set (81, 82) to (0.9, 0.98) in the NMT task and (0.9, 0.999) in the LM task. For the LM task, the general dropout rate set to 0.4.
CV
SGD/Adan//damwy We adopt the same experimental setup in AdaHessian 34 For SGD, the initial learning rate is 0.1 and the momentum is set to 0.9. For Adam, the initial learning rate is set to 0.001 and the epsilon is 1e-8. For AdamW, the initial learning rate is to 0.005 and the epsilon is to 1c-8.
AdaBelicf: We explore the best lcarning rate for ResNet20/32 on Cifarl0 and ResNet18 on ImageNet, respectively. Finally, the initial learning rate is set to be 0,01 for ResNet20 on Cifar10 and 0.005 for ResNec12/RRsNee188 on Cifar 10/lmageNet. The epsilon is set to 1e-8.
AdaHessian: We use the recommended configuration as much as possible from AdaHessian (44 The Hessian power is set to 1. The initial learning rate is 0. when training on both Cifarl0 and ImageNet, as recommended in Yao et al.
34 The epsilon is set to Ic-4.
AGD: We conduct grid search of ō and the learning rate. The choice of ă is among (le-8, 1c-7, 1e-6, 1e-5, 1e-4, 1e-3, 1e-2) and the search range for the learning rate from Ic-4 to le-2. Finally, we choose the learning rate to 0.007 and 5 1e-2 for C task, and learning rate to 0.0004 and to le-5 for ImageNet task.
The weight decay for all optimizers is set to 0.0005 on Cifar10 and 0.0001 on ImageNet. B = 0.9 and 82 0.999 are for all adaptive optimizers.
'hanps//gituuh.com//uttaaag http:///ggtta..como/mnnnngggh/ho oppiiinn hunps//ghhhbbooom/mmmggooommaaas
14

---

RecSys
Note that we implement the optimizers for training our internal distributed environment.
SGD: We search for the learning rate among (le-4, le-3, le-2, 0.1, 1) and choose the best results (0.1 for the Avazu task and le-3 for the Criteo task).
Adam/AdaBelief: We search the learning rate among (le-5, Ie-4, Ie-3, 1e-2] and the epsilon among (Ie-16, Ic- lc-14, Ic-12, 1c-10, Ic-8, Ic-6). For the Avazu task, the best learning ratc/epsilon is lc-4/1c-8 for Adam and lc-4/1e-16 for AdaBelicf. For the Critco task, the best learning ratc/epsilon 1e-3/1c-8 for Adam and 1e-3/le-16 for AdaBelief.
AdaHessian: We search the learning rate among (1c-5, lc-4, 1e-3, 1c-2] and the epsilon among (1e-16 16, le-14, 1e-12, le-10, 1e-8, 1e-6). The best learning rate/epsilon lc-4/1e-8 for the Avazu task and 1e-3/1c-6 Criteo task. The block size and Hessian power are set to
AGD: We search the learning rate among ( (1e-5, le-4, le-3) and 8 among [1e-12, le-10, 1e-8, 1e-6, le4, 1e-2). The best learning rate/ó is le-4/le-4 for the Avazu task and le-4/le-8 for the Criteo task.
81 = 0.9 and 32 = 0.999 are for all adaptive optimizers.
A.2 AGD vs. AdaBound
Table 7: The performance of AGD and AdaBound across different tasks.
Optimizer
3-Layer LSTM, test PPL (lower is better)
ResNet18 on ImageNet, Top-1 accuracy
AdaBound
63.60 39
68.13 (100 epochs) [8]
AGD
60.89 (better)
70.19 (90 epochs, still better)
A.3
Numerical Experiments
our numerical experiments, we employ the same learning rate across optimizers. While larger learning rate could accelerate convergenee, as shown Figures an we also note that it could lead to unstable training. To investigate the largest learning rate that cach optimizer could handle for the Beale function, we perform a scarch across the range of (le-5, Ic-4, ... 10). The optimization trajectories are displayed in Figure 7c and AGD demonstrates slightly superior performance. Nonetheless, we argue that the learning rate selection outlined Section presents a more appropriate representation.
Maen brokec
(a) Adam
(b) AGD
(c) Comparison
Figure 7: Optimization trajectories on Beale function using various learning rates.
A.4 AGD with AMSGrad condition
Algorithm summarizes the AGD optimizer with AMSGrad condition. The AMSGrad condition is usually used ensure the convergence. We empirically show that adding AMSGrad condition AGD will slightly degenerate AGD's performance, as listed in Table [8] For AGD with AMSGrad condition, we search for the best learning rate among (0.001, 0.003, 0,005, 0.007, 0.01] J and best within ( [le-2, le-4, le-6, 1e-8), We find the best learning rate is 0.007 and best ó is le-2, which are the same as AGD without AMSGrad condition.
AGD for ResNet18 Cifar10 A.5
Since the SOTA accuracy | for ResNet18 Cifar10 is 95.55% using SGD optimizer with a cosine learning rate schedule, we also test the performance of AGD for ResNet18 on Cifar10. We find AGD can achieve 95. 79%
10-reeet--1
15

---

Algorithm 2 AGD with AMSGrad condition
1: Input: parameters 31, 32, wi E IR", step size Oe, initialize mo - 0, bo
2: for 1 to 7 do
3: 9: V V(((w)
4: m, - 81m=-1 +11 31)
mi/ (1)
t == 1
5:
m (1 (1) m,
1/(11(1111 111-11-11
11-1)
t>
6: b: -2b1-1 + (1- {2)s}
7: b t max b,, b
AMSGrad condtion
VI-
8: Wi+1 wi 04 1-81
maxt Vo. 1-
9: end for
Table 8: Top-1 accuracy for AGD with and without AMSGrad condition when trained with ResNet20 on Cifar10.
Optimizer
AGD
AGD AMSGrad
Accuracy
92.35 + .24
92.25 + 0.11
accuracy 0.001 and 6 le-2 when using the same training configuration as experiment SGD Moreau et al. [24), which exceeds the current SOTA result.
A.6 Robustness to pyperparameters
We test the performance of AGD and Adam with respect ô (or c) and learning rate. The experiments performed with ResNer20 on Cifarl0 and results are shown Figure Compared Adam, AGD shows better robustness to the change of hyperparameters.
0.9
0.8
0.8
Test accuracy
0.7
I--0.000
In-0 0001
00000
0.5
0 0000
In-0 00000
0.5
001
005
0.3
0= 007
Ir=0 007
120
140
Epoch
Epoch
(a) AGD
(b) Adam
0.9
accuracy
Teat accuracy
0.7
0.7
1m1e-3
cmle:3
0.5
1=1e
cle5
1e-6
0.3
1648
c=1e8
20
60
80 Epoch
100
120
140
160
20
40
60
100
120
140
160
(c) AGD
(d) Adam
Figure 8: Test accuracy of ResNer20 on Cifar10, trained with AGD and Adam using different 5 (or c) and learning rate. For (a) and (b), we choose learning rate as 0.007 and 0.001, respectively. For (c) and (d), we set 5 (or e) to be le-2 and le-8, respectively.
16

---

B Proof of Theorem 1
11 and b2 max( 8/ 35), we have the following lemmas.
Proof. Denote d; at 1-
Lemma 1. For the parameter settings and assumptions in Theorem 1 or Theorem 2 have
âs 0e++1, t t [1],
11-8
where ōn = 1-91.
Proof. Since 91, is non non-inonnnnn non-increasing with respect to have Pi,t41 S f1,411 S Bi,1. Hence, Pi, non- increasing and 1- non-increasing. Thus, we only need prove @(t) or 55 decreasing. Since the proof is trivial when $2 = O, only need to consider the case where B3 E (0, 1). Taking the derivative of ((t), have
(1()) 0 1 (1-1)))))))
-1)
a 11 B2) 3 loge 32
a
32) (1 B1 1 loge 82).
2
(()
Since
3 (t) = - B log. 32 + /8 log, B2 + t,og, 32) = (loge .2)2
we have (1) 0 when & 0 and (1) when = O. Combining (0) 0, we get eb(t) 0 when / 0. Thus, have of (t) 0, which completes the proof.
Lemma 2. For the parameter settings and assumptions in Theorem 7 or Theorem 2 have
|v n(2G +
t [T].
(1 (1-
where max(m/b, B.)
Proof.
Gx
|m m0
(1 - -1,---1 ) -41
B
B $ Σ
g-
g
1f 1-
11x S
|m lcc <
Gx
20
t=
||01|100 5
| 2
1-3h
mm
11
[1
11
[1-
20.0
1> 1,
1-
1-
1-1
(1
4G2
10elo0 =1[(1 - B2) Σ
8 0
1000 <
(1- (1-31)4-
1|vx,11 = Σ Ve, < nnllvball
+8)
n12G + +
(1 31)²
By assumptions 2, 4, Lemma and Lemma
Vt E [T), we have
G
2G
&4t1
| ooo S
E [n].
(6)
3
1-3,)²
Vetii
Following Yang et
Chen et al. 99 Zhou et 37
define an auxiliary sequence (ur]: 1L
2,
BI (w:
Br,1
31,5
B
31,5
17

---

Hence, we have
1
$1,041
$1,1
U++1
-1,111
11,1
1 31,5
16+1
1 B1,e+1
1 -1,1
B1
+
(we+1
(we u(-11
1
BI,1
1 - 1I,
1
mi
B1,a-1
Bi.
$1,1+1
1 $1,t
(wr
1 11,1+
1 31,t
we
de
mh:
B1, Vi
1 -
31,1
1
de mc
B1,
Mc-1
+ (1
31,0)
gt
, m
BI.t
1
91,1+1
w:
1 31.1
V:
1 B1.t
Dt-1
1
mc
11,
ât-1
āe
gt
BI, 1 31,441
31.1
Ut-1
mh
de
11
(8)
By assumption and Equation we have
L
f(u=-1) Sf(u) + (V (u+). we+1 ue) + 2 -1/22c+ cec+1 wel
=f(u) + (Ww:)) u4+1 - ui) + (V V.(w))) ue+1 - ue) + -
u1+1
zel1
2
=s(u)) + V[(w)) 1 1-Br, Bi,e 1 31,141
m:
BI.
(Vs(u)))
á
I 31,1
11-1
m
âu (we() g:
+ (V.[(us) V/(w)), u141 ut)
L
|| - usll
uell?
2
(9)
Rearranging Equation 9 and taking expectation both sides, by assumption 3 and Equation 6
we get
(1 3.)
V((ws) Vf(w)))
[[I[ <à.E
2Goc
<E(f(ue) f[ue+1]] + (Vllw)), (1 11 B1.1
mh
ōx
B2.e11
Vt.
A
B1,t E Vs(w),
á:-1 âe
+
mi-1
1 - $1,
I. E
E (VV((u)
Vi(w)),
u ui)
|11411
well?
P4
(10)
To further bound Equation 10 we need the following lemma.
Lemma 3. For the sequence {wi} defined as Equation
7 Vi 2 2, have
ā,,1,
+ à: 11, + âz
|uu41 - uell 5
(1 (1- 32
(1 - 81)²
3nG2 82
67
|1++1
wil1? v
(1- 3:)4 8i
31)6
Proof. Since Vt E [T]. E [m]] 1/(1 B1,e) 2 1/(1 - 3 -1,--1;; vi 2 8VI 32, â > 6e/21.1.
By Equation (8) we have
VTG
B1.1 B1,441
B1.1 â
VTG
+ àr VTG
|1e+1 well < â, (1
81)0v1 B2
(1- 31,e B1,411)
1 B1,t (1- (1-8,)6v1-
5.1 3r
11-131.
ài
8 3r
(1-31)) 81)3
(1- 81)2
3n
|ue - uill <
+ a
(1 - B2)
(1 - 36
(1 B1)a
where the last inequality follows from
inequality. This completes the proof.
18

---

Now we bound Pt. P2, P33 and Pa of Equation 10
separately. By assumptions 1, 2. Equation 6 and Lemma 3
we have
P S d
1
E
| [V(
mi
31,1 1 B1,041
B Br,e41
S de
8vT - 31 - -11 -
Ce(B1. B1,,+1),
(1 - (1,00(1 - -1.++1)
(1 - B1) 31)88v1 13
a
âi
ā di
P2 E
V. V.f(we))me 1s(
1 1
)
11
2/,3""
B1
11-1, Uz
1=1
Pa E f(us)
-ill
S LE
|||e, we dell|/
U1+1 U4
31, E
|||4411 well
3 (1 - (1-1,))884 81)282(1 - (2)
LnC
àr- ai-18f,
+ 1
1- B1.
1/-1
(1 - 31)3
(1- 31)²
LnCZ
01-1
07-1
+ oi-1
< (1 81)582(1 - (8)) 0i-1;
3LnC3
(1 31)30221 - 82)
(1 - (1-8)3 (1 - B1)2
3nO
ai-18i,
+ 2 3n
à²
2ع-1 + 6
Pa 5 (1 32)
+ (1 (1)
(1 81)6
(1 - 31
(-
(1 B1)8
OnG2
(1 B,)802(1 B2) 1
(11)
Replacing Pi Pr, I's and Pa of Equation 10 with Equation [I and telescoping Equation wc have
10
for = to T.
T
8
nG
T
E
[[I
[s( [(uT+1)]
a. - 31,0+1)
2G
(1
32
1=2
1=2
G.G²
3Ln
T
9
T
+ (1- 81)582(1- - B2)
Σ
a;
a
(1 B1)2
U1
VT,
2(1-31
31 3,)002211 :2)
t=
1=2
nG
aßinGa
<E [f(ua)] - ~[(w") +
ar(31 - B1,411 +
(1 - B1) 85 1 13
(1 3:8
15LmG.
+ 2(1- - --))8-1)102 B2)
22
(12)
Since
T
T
0 VI 31
T
Σ
Σ
2 2av1- 1- 32
Σ
Vl
Bi,
2 Vi
1-2
1
1
T 1
=a 1 - 82
ds + +..
da
>
1 -
82
ds
2 V2
T-1 VT
V8
-2a7 1 31
(VT v2)
2
1- 81
< (1 B1)
t (1 - )1
t
a²
1
a²
/ 1
1+
da
T-1 T ds
1
do
(1 8.)2
2 2
(1
3:)3
2
(13)
a²
a²
(log(T - +1) <
(log T + +1),
(1- 31
(1 - 31
L
E [[s(wz)] <[(i) + E [[((S[(w)) ) u2 wi\1 +
E
[||u2 - wi [1
2
=f(w])
ân I- B1,2 E
mi
2(1 3) E
La?
mi
11
<f(w)) + avT - 32
(1 (32
+ 2(1 - 31
E
(1 - 31
01
01
anG²
LannGe
nG a
<f(w)) + (1- 3, 28
S f(w)) + 2(1 8,
(26 La),
2(1 - B, 888
19

---

substituting Equation
13
into Equation
12
we finish the proof.
C Proof of Corollary 1
Proof. Since $1,t = Pa/vt, we have
T
VI $1
T
Σ de( -1, Br
B1,
(log T 1).
Vi
Bi.
81 t=1
1
1
B1
(14)
Substituting Equation 14
into Equation (). we have
Go
no
min cE[T]
[IV]()))
< a(1 - -11)a(1 82)² [((01) - -f((0)
(25 + 8L.)
(1 31)882
aBinn
nG
15
La +8)
log T
(1- 8,)38
VT /2
(1 (1-32)3(1 308 (
VT V2
This completes the proof.
D Proof of Theorem
Proof. Denote à, = at T-
V1-02
and v, max(vb,, 8/11/11/ (35). then
[Vei(w4r w² w²)11 11 Vollw. à v.
m. w") )l² = ll w)1 2âc (w. w. ,m,))) + ail
mi
/v:
|| Vollww - w )12 + aill
me 112 2ā.31,1 (w01 - w., mo"m)_ -6xz 31,1) (w: w ,9))
/v:
(15)
Rearranging Equation 15
we have
(w: w''g))
(llver(
w²)1l - B1, (w. w", m.
m,
||
31,t
2ā,
2
/0:
( =²)) B1,t 26.
5 31
(1lv
==)
uw - w0 w²11
+ 2 |
1|
1
m:
||3
2
VuL
where the first inequality follows from
inequality and < 1 (a" + 6²). Hence, regret
(fe(me)) fe(w"
un w
gt))
T
1
B1.1
(Il (1lvv,(w: w²)ll ( ==')l²²)
w. un
20re
20
t=1
31 31
dee
mc
|m--1
/ue
(16)
where the first inequality follows from the convexity of f:(w), For further bounding Equation following Jemma.
16 we need the
Lemma 4. For the parameter settings and conditions assumed in Theorem
we have
2naG2
VT.
[1 31
20

---

Proef. From Equation 4
we have
de de|lmall
azl
B1 -1.1-14199 19 -11
II
B
S <
Σ 01-1111111
fm1
-t-
2
S 0t
gl o
E
==1
==1
n
Go
1
Vi
B
B1
(1 - 31 Vi
where the second inequality follows from Cauchy- Schwartz inequality. Therefore.
naG (1 - )1
2naG T (1-B))
Σ 6e.lm..11 <
Vt
(1-
where the last inequality follows from
8 1
T 1 ds
1+
ds +
V
V2
T-1 VT
3
1 da
1 +
da
2
V
T-1 V
1
= 1
ds = 2 1 2VT.
V8
This completes the proof.
Now return to the proof of Theorem 2 Let âo â1. By Lemma] the third incquality Equation o we have
Lemma
Lemma
Equation T6 and
T
E (Ji(w))) Se(w )) S
1
(volww
w') w')ll +
Σ
w.(w: ww w')l 2ā.
|l (/ (w: w '1]
20
20,
t=2
+
B1,t
ww
w 11
Σ
át-1
|m:
_1
+
mi
11))
26x
2
Vot
1=
1
D2
|vvil
+
Σ
D
||vi
|
/
Σ
3r.t
nD
81
26
2d,-1
26,
Σ
|m, ||
2
28
82
1=1
D2
2
Σ
T
$1.1
nD²
T
1
||mm|??
31
2④T
20,
2
28 - B22
1=1
1=1
1
n(2G + +
T Σ
31,1
nD²
naG2
(1+
(1+
vT
31
20
32(1 - B1)²
26
(1 31)3
5v1 - Bz
t=1
This completes proof.
E Proof of Corollary 3
Proof. Since 31,t = B1/t, we have
B Σ
T
Σ
T (1 (L.)
T
V181.
31
T
1
B1
VT.
1=1 2a 83
20<1
32
20
B2
Vt
avl - B2
t=l
This completes proof.
21


Reviews:
[{"review_id": "LLuQJDIzRz", "reviewer": "Reviewer_xqym", "summary": "This paper proposed AGD, a novel optimiser that can dynamically switch between an adaptive optimiser and SGD. To achieve this, an auto-switching function is introduced to change the diagonal elements of the preconditioning matrix based on the gradients of adjacent steps. Both theoretical analysis on the convergence of the optimiser, and experimental results on six public CV, NLP and RecSys setups are provided, demonstrating AGD is a promising method both in theory and practice. \n", "questions": "What's the trajectory of Adam at the minimum point B in Figure 1?", "limitations": "Discussions of regularisation methods (at least with SGD) and large-scale experiments with complex model structures (e.g. a Transformer with both encoder and decoder) are missing. \nThe analysis of the convergence speed in the numerical analysis session may not be completely fair. \nWould be useful to include the analysis of computation and storage costs. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "It is often noticed in practice that SGD with proper hyperparameters (learning rate, momentum, and weight decay) can outperform the adaptive optimisers with better local optimum found, while the adaptive optimisers require less effort in hyperparameter tuning and sometimes faster convergence. The auto-switching strategy may help combine the advantages of them, and experimental results and analysis demonstrate the soundness and robustness of the chosen auto-switching function.\n", "weaknesses": "1. Optimisers can perform differently on large-scale and small-scale experiments. Although good PTB results are given in the paper, a larger-scale language modelling experiment may still be useful.\n2. Some hyperparameter settings, such as those for PTB, are missing in the paper and the supplementary materials. The effect of regularisation methods, in particular L2 and dropout, are not given. This often makes a key difference to the generalisation ability of the test set and the performance of SGD and could be at least considered in the numerical analysis session. \n3. The proof of the faster convergence speed of AGD using the case studies in Sec. 3.2 may have resulted in some questions, as the comparisons of optimisers with different learning rates and other hyperparameters may not be fair enough. \n4. Extra memory cost, computational cost and possible limitations of the method are not discussed. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive review.\n\n**Q1: Optimisers can perform differently on large-scale and small-scale experiments. Although good PTB results are given in the paper, a larger-scale language modelling experiment may still be useful.**\n\nPlease refer to [Global Response 1](https://openreview.net/forum?id=A954O4tDmU&noteId=wLS9DFtY0I).\n\n**Q2: Some hyperparameter settings, such as those for PTB, are missing in the paper and the supplementary materials. The effect of regularisation methods, in particular L2 and dropout, are not given. This often makes a key difference to the generalisation ability of the test set and the performance of SGD and could be at least considered in the numerical analysis session.**\n\nThe training settings are consistent across all optimizers, including regularization methods. The specific training details for PTB are provided in the file nlp-task/lstm/run_all_layer{1,2,3}.py, where the general dropout rate is set to 0.4 and the weight decay is set to 1.2e-6 (as mentioned in Appendix A.1). We will provide more details in the revised version.\n\n**Q3: The proof of the faster convergence speed of AGD using the case studies in Sec. 3.2 may have resulted in some questions, as the comparisons of optimisers with different learning rates and other hyperparameters may not be fair enough.**\n\nAs mentioned in Sec. 3.2, all hyperparameters are kept identical, including the learning rate of 1e-3 and betas of (0.9, 0.999). One exception is SGDM, which does not converge under such a large learning rate.\n\n**Q4: Extra memory cost, computational cost and possible limitations of the method are not discussed.**\n\nAGD and AdamW both store two optimizer states, so their memory footprints should be similar. AGD incurs a slight additional computational cost, which we validate on the transformer model and find to be negligible, especially when compared to optimizers like AdaHessian. The results are shown in [Global Response 2](https://openreview.net/forum?id=A954O4tDmU&noteId=wLS9DFtY0I).\n\n**Q5: What's the trajectory of Adam at the minimum point B in Figure 1?**\n\nThe whole trajectory until convergence is shown in Figure 3 in the [provided PDF](https://openreview.net/attachment?id=wLS9DFtY0I&name=pdf).\n\nWe hope our responses have addressed your concerns."}, {"review_id": "B0YSJnkfYw", "reviewer": "Reviewer_Ag5C", "summary": "The paper proposes a new optimizer called AGD that integrates the information of the Hessian into the preconditioning matrix and switches dynamically between SGD and the adaptive optimizer. The authors establish theoretically proven convergence guarantees in both non-convex and convex stochastic settings. The authors validate AGD on a total of six public datasets: two from NLP (IWSLT14 and PTB), two from CV (Cifar10 and ImageNet), and the rest from RecSys (Criteo and Avazu). The experimental results reveal that AGD can outperform or be on a par with the SOTA optimizers. Overall, the paper makes a significant contribution to the field of deep learning optimization. AGD is a promising new optimizer that has the potential to improve the performance of deep learning models on a variety of tasks.", "questions": "•\tPlease see weaknesses.", "limitations": "There is no limitation discussed in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "• AGD can achieve a faster convergence rate over SGD\n\n• AGD can automatically switch between stochastic and adaptive optimization, depending on the progress of the optimization. This allows AGD to achieve the best of both worlds, i.e., the fast convergence of adaptive optimizers and the robustness of SGD.\n\n• AGD has a few flexible hyperparameters, making tuning for different tasks and datasets easy.\n\n• AGD was evaluated on various datasets across different domains, and it outperformed other optimizers in most cases.\n", "weaknesses": "• The convergence rate of AGD depends on the hyperparameters δ and β1. If these hyperparameters are not chosen carefully, AGD may not converge to the optimal solution. Looking forward to seeing more comprehensive robustness evaluation using different network structures and larger datasets.\n\n• AGD requires more computation than SGD. How is its efficiency for large-scale problems, e.g., large language models? I think performance on large-scale generative model optimization is a very interesting direction. Does the author have plans to try on such a task?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful review.\n\n**Q1: The convergence rate of AGD depends on the hyperparameters δ and β1. If these hyperparameters are not chosen carefully, AGD may not converge to the optimal solution. Looking forward to seeing more comprehensive robustness evaluation using different network structures and larger datasets.**\n\nWe also conducted robustness tests on $\\delta$ for the ResNet18 model using the ImageNet dataset, and the results are shown in Figure 2 in the [provided PDF](https://openreview.net/attachment?id=wLS9DFtY0I&name=pdf). As can be seen, the model performance did not show significant changes within a large range of $\\delta$ values. As a common parameter for adaptive optimizers, $\\beta_1$ was not adjusted in this work in order to maintain consistency with other optimizers.\n\n**Q2: AGD requires more computation than SGD. How is its efficiency for large-scale problems, e.g., large language models? I think performance on large-scale generative model optimization is a very interesting direction. Does the author have plans to try on such a task?**\n\nPlease refer to [Global Response 1](https://openreview.net/forum?id=A954O4tDmU&noteId=wLS9DFtY0I).\n\nWe hope our responses have addressed your concerns."}, {"review_id": "YA2gAw2IoW", "reviewer": "Reviewer_1Tit", "summary": "The paper proposes a new optimizer based on finite difference approximation to obtain the inner product between the Hessian row vector and the parameter vector difference from gradients of succeeding steps and an auto-switching function to switch between SGD and the adaptive optimizer. It uses an exponential moving average of gradient instead of gradient for lower variance. Experimental results show that the proposed method performs better than existing methods in most cases.", "questions": "What is the reason for the performance improvement? Is it due to its ability to find better local optima or the faster convergence in a limited computation budget?", "limitations": "There is no numerical explanation for the computational cost.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The proposed algorithm can efficiently acquire the information of the Hessian.\n\nExperimental results show performance improvements.", "weaknesses": "The explanation of related works is minimum. It needs to be more concretely clarified what problem of existing second-order methods it addresses. \n\nThe experiments in section 4 only report model performance and do not report computational costs. \n\nI need help finding Figures 5 and 6 in the paper. Are they missing?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your thoughtful review.\n\n**Q1: The explanation of related works is minimum. It needs to be more concretely clarified what problem of existing second-order methods it addresses.**\n\nSecond-order methods entail the computation or approximation of the Hessian, which can be computationally demanding. Despite efforts to reduce overhead, such as the Hessian diagonal approximation employed by AdaHessian, these methods are still less efficient compared to first-order methods. In response to Q2, we will present experimental results regarding the computational costs involved.\n\nThe major problem of the existing second-order methods, like AdaHessian, is that they require extra memory footprints and heavy computation compared to first-order methods, which makes they unusable in practice. Please refer to [Global Response 2](https://openreview.net/forum?id=A954O4tDmU&noteId=wLS9DFtY0I), where we compare the resource usage experimentally.\n\n**Q2: The experiments in section 4 only report model performance and do not report computational costs.**\n\nIn theory, AGD requires approximately the same amount of memory as AdamW, as they both store two optimizer states, with slightly higher computational requirements. In order to demonstrate this, we provide experimental results in [Global Response 2](https://openreview.net/forum?id=A954O4tDmU&noteId=wLS9DFtY0I).\n\n**Q3: I need help finding Figures 5 and 6 in the paper. Are they missing?**\n\nThanks for pointing out this issue. Figures 5 and 6 are in Appendix A.2 due to space limitations. We will provide further clarification in the next revised version, as well as fix a typo in Figure 5.\n\n**Q4: What is the reason for the performance improvement? Is it due to its ability to find better local optima or the faster convergence in a limited computation budget?**\n\nOur findings suggest that the observed improvement in performance can be attributed to both fast convergence and good generalization. The fast convergence is primarily thanks to the gradient difference between the previous and current steps, which effectively incorporates Hessian information into the preconditioning matrix. Furthermore, the auto-switch mechanism we implemented can prevent abnormal updates and and, compared to the traditional method of adding a small amount, can avoid introducing additional bias during updates, thereby leading to more stable training and improved generalization.\n\nWe hope our responses have addressed your concerns."}, {"review_id": "SjQH5pCCq6", "reviewer": "Reviewer_ns5n", "summary": "This paper introduces a novel optimizer, namely, Auto-switchable optimizer with Gradient Difference of adjacent steps. The authors propose a different way of approximating information from the Hessian for faster and better convergence in a way that a preconditioning matrix is computed using successive optimization steps in the parameter steps. The authors evaluate their optimization algorithm across different tasks and including some widely used architectures such as Transformers and RNNs. Moreover, the authors provide a theoretical analysis of the convergence of their algorithm and some bounds.\n", "questions": "Would you consider including experiments with some harder tasks such as estimation tasks, e.g. audio source separation instead of detection and retrieval tasks?\n", "limitations": "The authors should include my first point under the weaknesses of the paper and include a small paragraph to address this potential limitation of their algorithm.\n", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is well written in terms of giving the appropriate context of the most commonly used optimization algorithms, nice figures for toy experiments to understand how the algorithm works.\n- The experimental framework idea is well designed in the sense that a good range of optimization tasks is considered to show the importance of the algorithm.\n- The idea of using the successive steps seems novel to me to approximate Hessian information for faster convergence.\n", "weaknesses": "- In my humble opinion, the issue with the current idea lies in terms of the number/width of the optimization steps and how far the solution lies compared to the initialization point in the parameter space. The information that one can obtain by gradient differentials in the optimization space is only getting less and less useful while we increase the dimensionality of the optimization space. That means that for smaller optimization problems where the optimal solution would lie close to the initialization point, then I can really see the benefit of AGD compared to less Hessian well-informed optimizers like Adam. One can also see this emergent problem even from the theoretical analysis of the authors. For instance, in Theorem 2, the authors bound the approximation of the function using $D_\\infty$ which effectively is the upper bound in terms of successive optimization steps in the parameter space and also an upper bound of each weight vector compared to its distance from the optimal solution. That means that for real-world multi-dimensional optimization problems (e.g. billions of parameters) those bounds and probably the algorithm itself could be called into question. Having said that, there are other works like NTK that have shown that neural networks stay pretty close in general near the initialization regime, so, I would not consider it appropriate to ask the authors to prove these things but they could put more effort into making their experiments more convincing to ameliorate this huge concern.\n- Building upon my previous argument, my belief about the problem of scaling of the algorithm to bigger optimization problems is also displayed in the experiments where AGD scores significantly higher than all the other optimizers in smaller parameter spaces (e.g. 1-2 layers of LSTM) but becomes almost negligible with slightly bigger networks (e.g. compare Adam vs Proposed in Table 4, ResNEt 20, 32, Table 5 MLP, DCN, compare AdamW vs AGD in Table 1 Transformer). Having said that, the authors can include experiments with larger and state-of-the-art networks (e.g. ResNet 100+ layers on ImageNet, include some experiments with some networks with 500+ million parameters transformers) to prove me wrong and compare against state-of-the-art performance reported numbers with SGD and/or Adam. \n\nI am willing to increase my score if most of the most important above concerns are addressed by the authors since I truly believe that the paper has a great potential to offer a more robust general optimization strategy to replace Adam.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive review.\n\n**Q1: In my humble opinion, the issue with the current idea lies in terms of the number/width of the optimization steps and how far the solution lies compared to the initialization point in the parameter space ... That means that for real-world multi-dimensional optimization problems (e.g. billions of parameters) those bounds and probably the algorithm itself could be called into question ... I would not consider it appropriate to ask the authors to prove these things but they could put more effort into making their experiments more convincing to ameliorate this huge concern.**\n\nTo our knowledge, the issue exists for all optimizers. The generalization bound of Adam-like optimizers also includes $D_\\infty$, as shown in Theorem 5 of [1]. The generalization bound of SGD includes $\\\\| x_0 - x^* \\\\|^2$, where $x_0$ is the starting point and $x^*$ is the optimal point, as shown in Theorem 2.1.14 of [2]. Therefore, the statement `the issue with the current idea lies in ... how far the solution lies compared to the initialization point in the parameter space` is inappropriate.\n\nIn addition, we have experimentally demonstrated the effectiveness of AGD for models with a large number of parameters, as shown in the Figure 1 of the [PDF provided](https://openreview.net/attachment?id=wLS9DFtY0I&name=pdf) in the [Global Response](https://openreview.net/forum?id=A954O4tDmU&noteId=wLS9DFtY0I). We conducted optimizer experiments on the GPT2 (124 M) and GPT2-Large (774 M) models using the OpenWebText dataset. The results indicate that AGD outperformed the AdamW optimizer in terms of convergence. We hope our results address your concern.\n\n**Q2: My belief about the problem of scaling of the algorithm to bigger optimization problems is also displayed in the experiments where AGD scores significantly higher than all the other optimizers in smaller parameter spaces (e.g. 1-2 layers of LSTM) but becomes almost negligible with slightly bigger networks (e.g. compare Adam vs Proposed in Table 4, ResNEt 20, 32, Table 5 MLP, DCN, compare AdamW vs AGD in Table 1 Transformer).**\n\nFirstly, LSTMs tend to have far more parameters than ResNets, as convolutional kernels typically have fewer parameters. This difference can be observed in Table 2 of the paper.\n\nAdditionally, the improvement in metrics can vary depending on the model’s capacity and the specific dataset being used. For instance, enhancing the AUC of ReSys tasks is known to be challenging, and certain networks are often over-parameterized for smaller datasets (e.g., ResNets on Cifar10). Consequently, achieving improvement from the optimizer’s perspective can be challenging but valuable as well.\n\nLastly, we have conducted extensive experiments of AGD on GPTs since the rise of LLMs, and the results have been highly promising, as indicated in the response to Q1. The pretraining stage of LLMs can typically be time-consuming, often spanning several months. However, we are confident that AGD has the potential to considerably expedite the training of LLMs.\n\n**Q3: Having said that, the authors can include experiments with larger and state-of-the-art networks (e.g. ResNet 100+ layers on ImageNet, include some experiments with some networks with 500+ million parameters transformers) to prove me wrong and compare against state-of-the-art performance reported numbers with SGD and/or Adam.**\n\nPlease refer to the [Global Response 1](https://openreview.net/forum?id=A954O4tDmU&noteId=wLS9DFtY0I). Also see Q1.\n\n**Q4: Would you consider including experiments with some harder tasks such as estimation tasks, e.g. audio source separation instead of detection and retrieval tasks?**\n\nFollowing [3, 4], we test optimizers against common CV and NLP tasks. We will leave the harder tasks you mentioned for future work.\n\nWe hope our responses have addressed your concerns.\n\n---\nReferences:\n\n[1] Reddi, S. J. et al., On the Convergence of Adam and Beyond. ICLR 2019.\n\n[2] Yurii E. Nesterov. Introductory Lectures on Convex Optimization - A Basic Course, volume 87 of Applied Optimization. Springer, 2004.\n\n[3] Zhuang, J. et al., AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients. NeurIPS 2020.\n\n[4] Yao, Z. et al., ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning. AAAI 2021.\n"}, {"review_id": "5o12nMMFrv", "reviewer": "Reviewer_BE2A", "summary": "The paper proposes a new gradient based optimization called AGD. The idea is to utilize gradient difference between the current and previous steps in the preconditioning matrix which is related to Hessian. Also, an autoswitching function is proposed to switch between SGD and the adaptive optimizer. As mentioned in the paper, both ideas were previously brought up but the attempt to make an explicit optimizer is first done in the paper.", "questions": "- Figure 3 suggests AGD is faster to converge, and Table 3 suggests AGD results in better performance. Could we make such a conclusion that it should be always used instead of SOTA optimization methods?\n\n- What is the stop criteria of different optimization techniques in Table 3? I am wondering if the improvement obtained by AGD is accurately examined or for example all methods go for the same number of iterations and AGD converges faster? You argued this issue in section 4.3 for CV task.\n\n- The performance of AGD in CV task is quite marginal. How about the convergence time? does AGD maybe converges faster? \n\n- I would have also liked to see more about autoswitching and why and how it happens in a simple toy example.", "limitations": "-", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Well written and motivated\n- Conducting number of downstream experiments\n- Presenting extra studies to examine the method", "weaknesses": "-The idea is not fully new\n- The details of experiments could be more explained", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable review.\n\n**Q1: Figure 3 suggests AGD is faster to converge, and Table 3 suggests AGD results in better performance. Could we make such a conclusion that it should be always used instead of SOTA optimization methods?**\n\nAGD is at least the optimal method in the datasets and models we have tested. We believe it will also have promising performance in other scenarios.\n\n**Q2: What is the stop criteria of different optimization techniques in Table 3? I am wondering if the improvement obtained by AGD is accurately examined or for example all methods go for the same number of iterations and AGD converges faster? You argued this issue in section 4.3 for CV task.**\n\nIn regards to the experiments detailed in Table 3, both the LSTM and transformer models were trained for a consistent number of epochs until convergence (200 epochs for LSTM and 55 epochs for transformers). With the exception of the optimizer hyperparameters mentioned in Appendix A.1, such as learning rate, epsilon, and delta, all other training settings remained identical across optimizers. These settings were inherited from previously published works to ensure a fair and credible comparison.\n\n**Q3: The performance of AGD in CV task is quite marginal. How about the convergence time? does AGD maybe converges faster?**\n\nThe convergence speed of different optimizers can be found in Fig. 6 of Appendix A.2. For ResNet18 on ImageNet, AGD has a faster convergence speed compared to other optimizers. For ResNet20 and ResNet32 on Cifar10, after the learning rate decay, AGD demonstrates better convergence compared to other optimizers except for AdaHessian.\n\n**Q4: I would have also liked to see more about autoswitching and why and how it happens in a simple toy example.**\n\nConsider using AGD to optimize the function $f(x, y) = |x| + |y|$ from the starting point $(-4, 0.5)$, see Figure 4 in the [provided PDF](https://openreview.net/attachment?id=wLS9DFtY0I&name=pdf). Choose hyperparameters of $lr = 1.0$, $\\delta = 1.0$, and $(\\beta_1, \\beta_2) = (0.0, 0.0)$. In the X-axis direction, the gradient difference is 0, so taking the maximum allows the parameters to be updated in an SGD-like manner. In the Y-axis direction, the gradient difference is 2, which is greater than 1, so the parameters are updated in an adaptive manner. Auto switch allows the model to use different update methods in different directions, and switches adaptively between SGD and adaptive methods as training progresses.\n\nWe hope our responses have addressed your concerns."}]

Author rebuttal:
#### Global Response

1. **AGD performance on large models**

    We conduct optimizer experiments on the GPT2 (124M) and GPT2-Large (774M) models using the OpenWebText dataset. Our code is based on https://github.com/karpathy/nanoGPT. We compare AGD with the default AdamW optimizer. The results are shown in Figure 1 of the PDF provided. As can be seen, AGD outperforms AdamW even after both were run for 50,000 steps. We hope our results effectively address the concerns of the reviewers.

2. **AGD's computational cost**

    We train a transformer small model for IWSLT14 on a single Nvidia P100. AGD is comparable to the most commonly used optimizer AdamW, while significantly better than AdaHessian in terms of memory footprint and training speed. We will add these results to the next revision.

    | Optimier | Memory/Mb | Time per Epoch/s | Relative time to AdamW |
    | - | - | - | - |
    | SGDM | 5119 | 230 | 0.96× |
    | AdamW | 5413 | 260 | 1.00× |
    | AdaHessian | 8943 | 750 | 2.88× |
    | AGD | 5409 | 278 | 1.07× |


In addition, we have included some images in attachment PDF to address specific questions raised by the reviewers.



Meta-review: This paper proposes an optimizer that can switch dynamically between SGD and being adaptive.  The authors design a diagonal preconditioning matrix where the diagonal elements are approximating the inner product between the Hessian row vector and the parameter vector difference of adjacent steps.  On top of that , depending on a threshold hyperparameter, the preconditioning matrix can switch between SGD and an adaptive one.   The proposed optimizer is evaluated on three tasks on a variety of datasets and models.   Superior convergence and generalization performance is reported and computation/memory cost is analyzed.  The authors also give a proof for its convergence and its rate.   The idea of auto-switching is interesting and extensive experiments are carried out to show its effectiveness in the original submission and rebuttal.  That being said, there are also issues with the papers. For instance, the authors assume bounded gradients in Theorem 1 and bounded set of W in Theorem 2, which are strong assumptions in optimization literature.  Furthermore, it is helpful to move some of the convergence curves to the main body rather than put all of them in supplementary as they are helpful to show the convergence behavior of an optimizer.   Overall,  given its strong empirical performance, this paper can be accepted.
Decision: Accept (poster)