AdaDQH Optimizer: Evolving from Stochastic to Adaptive by Auto Switch of Precondition Matrix
Authors: Yun Yue
Zhiling Ye
Jiadi Jiang
Yongchao Liu
Ke Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: adaptive optimizer
Hessian approximation
auto switch
precondition matrix
AdaDQH

Abstract: Adaptive optimizers (e.g., Adam) have achieved tremendous success in deep learning. The key component of the optimizer is the precondition matrix, which provides more gradient information and adjusts the step size of each gradient direction. Intuitively, the closer the precondition matrix approximates the Hessian, the faster convergence and better generalization the optimizer can achieve in terms of iterations. However, this performance improvement is usually accompanied by a huge increase in the amount of computation. In this paper, we propose a new optimizer called AdaDQH to achieve better generalization with acceptable computational overhead. The intuitions are the trade-off of the precondition matrix between computation time and approximation of Hessian, and the auto switch of the precondition matrix from Stochastic Gradient Descent (SGD) to the adaptive optimizer. We evaluate AdaDQH on public datasets of Computer Vision (CV), Natural Language Processing (NLP) and Recommendation Systems (RecSys). The experimental results reveal that, compared to the State-Of-The-Art (SOTA) optimizers, AdaDQH can achieve significantly better or highly competitive performance. Furthermore, we analyze how AdaDQH is able to auto switch from stochastic to adaptive and the actual effects in different scenes. The code is available in the supplemental material.

Under review as a conference paper at ICLR 2023
ADADQH OPTIMIZER: EVOLVING FROM STOCHASTIC TO ADAPTIVE BY AUTO SWITCH OF PRECONDITION MATRIX
Anonymous authors Paper under double-blind review
ABSTRACT
Adaptive optimizers (e.g., Adam) have achieved tremendous success in deep learn- ing. The key component of the optimizer is the precondition matrix, which provides more gradient information and adjusts the step size of each gradient direction. In- tuitively, the closer the precondition matrix approximates the Hessian, the faster convergence and better generalization the optimizer can achieve in terms of itera- tions. However, this performance improvement usually accompanied by a huge increase in the amount of computation. In this paper, propose a new optimizer called AdaDQH to achieve better generalization with acceptable computational overhead. The intuitions are the trade-off of the precondition matrix between com- putation time and approximation of Hessian, and the auto switch of the precondition matrix from Stochastic Gradient Descent (SGD) the adaptive optimizer. We evaluate AdaDQH on public datasets of Computer Vision (CV), Natural Language Processing (NLP) and Recommendation Systems (RecSys). The experimental results reveal that, compared to the State-Of-Thee The--rrrrrr (SOTA) optimizers, AdaDQH can achieve significantly better or highly competitive performance. Furthermore, we analyze how AdaDQH is able to auto switch from stochastic to adaptive and the actual effects in different scenes. The code is available in the supplemental material.
INTRODUCTION
Consider the following empirical risk minimization problems:
M
min f(w) = M WER"
(wwx)))
(I)
where w R a vector of parameters to be optimized, {=1..... E&y } is training set, and E(w;; x) is loss function measuring the performance of the parameter the example Since it is ineffective to calculate the exact gradient in each optimization iteration when M is large, we usually adopt a mini-batched stochastic gradient, which is
g(w)
Σ Vl(w; xx), KEB
M) is the sample set of size [B] < M. Obviously, we have Ep(=)la(w) = V ((w) where p(æ) is the distribution of the training data. Equation | is usually solved iteratively.
where B C (L,...,
Assume w, is already known and let Aw We+1 w. then
arg min f(W(-1) = arg min s(Aw + +w,)
1 ER
AwER"
R arg min f(w)) + (Aw)" + A
(2)
arg min f(w)) + (Aw) Vf.:)) + - (A B,Aw, AweR"
k(Aw)

---

Under review as a conference paper at ICLR 2023
where the first approximation is from Taylor expansion. By solving Equation 2 and using m, to replace f( the general update formula is
Wx++1 w: -., a, m, 1 (.,
where is the step size for avoiding divergence, m. z Eptae) [e] is the first moment term which the weighted average of gradient 9t and B, is the so-called precondition matrix that incorporates additional information and adjusts updated velocity of variable wy in each direction. Most of
gradient descent algorithms can be summarized with Equation 3 such as SGD (Robbins & Monro
195I). MOMENTUM (Polyak) 1964), ADAGRAD (Duchi al. 2011), ADADELTA (Zeiler) 2012).
ADAM (Kingma & Bal [a][20 AMSGRAD (Reddi et al. 2018). ADABELIEF (Zhuang et al. (020)
and ADAHESSIAN (Yao al. 2020 Intuitively, the closer B, approximates the Hessian, the
closer (Aw) approximates [ ). Consequently, we can achieve a more accurate solution in
terms of iterations. However, it is usually untrue in terms of runtime. For instance, ADAHESSIAN
that approximates the diagonal Hessian consumes 2.91x more computation time than ADAM for
ResNet32 on Ci (Yao et al. 2020). Therefore, the key factor of designing the precondition matrix is how to trade off the approximation degree of the Hessian and the computation complexity.
In this paper, we propose AdaDQH (Adaptive optimizer with Diagonal Quasi-Hessiane whose precondition matrix is closely related to the Hessian but computationally efficient. Furthermore, AdaDQH can auto switch the precondition matrix from SGD to the adaptive optimizer through the hyperparameter threshold 5. Our contributions can be summarized as follows.
We propose AdaDQH, which originates the new design of the precondition matrix. We establish theoretically proven convergence guarantees in both convex and non-convex stochastic settings.
We validate AdaDQH on total of six public datasets: two from CV (Cifarl0 (Krizhevsky et al. 2009) and ImageNet (Russakovsky et al. 2013)), two from NLP (IWSLT14 (Cettolo et al. (014) and PTB (Mareus et | 1993)) and the rest from RecSys (Criteo (Criteo 2014) and Avazu (Avazu 2015)). The experimental results reveal that AdaDQH can outperform or be on a par with the SOTA optimizers.
We analyze how AdaDQH is able to auto switch from stochastic to adaptive, and assess the rigorous effect of the hyperparameter 8 which controls the auto-switch process in different scenes.
RELATED WORK
By choosing different B, and m, of Equation different optimizers are invented from the standard second order optimizer, i.e., Gauss-Newton method to the standard first order optimizer, i.e., SGD where m, is usually designed for noise reduction and B, for solving the ill-conditioned problems. See Table]] [ Kunstner et al. (2199) shows that the Fisher information matrix can be the reasonable approximation of the Hessian whereas the empirical Fisher can't. Furthermore, they propose the concept of variance adaption to explain the practical success of the empirical Fisher preconditioning.
The hybrid optimization methods of switching an adaptive optimizer to SGD have been proposed for improving the generalization performance, such as ADA (Luo et al., 2019) and SWATS (Keskar & Socher, 2017)) Luo al.) (2019) adopts clipping on the learning rate of ADAM, whose upper and lower bounds are a non-inceggi and non-decreasing functions, respectively, which would converge the learning rate of SGD. The clipping method is also mentioned in Keskar & Socher 2017). whose upper and lower bounds are constants.
NOTATION
We use lowercase letters to denote scalars, boldface lowercase to denote vectors, and uppercase letters denote matrices. We denote a sequence vectors by subscripts, that is, Ii,..., 2, where t E [T] := {1, 21. .T), and entries of each vector by an additional subscript, e.g., Tt,i- For any vectors σ, E IR", we write xT y or æ y for the standard inner product, zy for element-wise multiplication, x y for element- division, v for element-wise square root, x² for element-wise square. For the standard Euclidean norm, |>:| |||| = ||0||| = v (xx x) and max(x (z, y) for element-wise maximum. We also use || = max; [z to denote L.e norm, where x(()) is the i-th element of æ. Let e; denote the unit vector where the i-th element is one and V, denote the i-th element of V V.
2

---

Under review as a conference paper at ICLR 2023
Table I: Different optimizers with choosing different B,.
B₁
Optimizer
B R==H
B1 R
LBFGS (Byrd et 1995)
B, R diag(R
H
ADAHESSIAN Yao et al.
2020)
Br
NATURAL GRADIENT (Amani
1998
B. F Emp
SHAMPOO Gupta et al.
2018
ADAGRAD (Duchi et al.
2011
ADADELTA Zeiler 2012).
B. = diag(F Femp))
ADAM (Kingma & Baj
2015
ADAMW Loshchilov & Hutter 2019
AMSGRAD (Reddi al.)
20188)
Bi = diag(Vrr Var(g.)
ADABELIEF (Zhuang et al.
2020)
B₁
SGD (Robbins & Monro 1951), MOMENTUM (Polyak 1964)
the Hessian, the Fisher information matrix. Pemp the empirical Fisher information matrix.
Let fe(w) be the loss function of the model 1-step where w R". We consider m, as Exponential
Moving Averages (EMA) of g. throughout this paper, i.e.,
m. B m,m-111 + (1 31)g: = (1- B1) Σ 91-1418811, 121,
(4)
where 31 E (0,1) 1) is the exponential decay rate.
2
ALGORITHM
2.1 DETAILS AND INTUITIONS OF ADADQH OPTIMIZER
The algorithm is listed in Algorithm
The design of AdaDQH comes from two intuitions: Hessian
Algorithm 1 AdaDQH
I: Input: parameters 81, G2, 8, wi E IR", step size a₁, initialize mo = 0, bo 0
2: for 1 to 7 do
3: 9: (((w)
4: m, < 81m--1 + +(1 81)gt
mi/(1 [1 - -
= 1 / ((-1)
5:
me/( - (8)
t>!
6: b. 32b:-1 (1- 82)8
1--8
7: W w: 04 1-
m
max(
(v 1-
8: end for
approximation and auto switch for fast convergence and good generalization across tasks.
HESSIAN APPROXIMATION
Let Aur B, m: of Equation then we have
E Eigh, - 9c-1, = vef(w.)) - (20(
vV,f(w 0Aw) Aw, 0 E (0,
(5)
VV.((w,) Aw
Aw (...)
where the second equality above follows from the mean value theorem and in the second approxi- mation we assume that w. is not updated except for the i-th direction. Therefore, we can see that El Elg(w::) ()) is closely related to diag (H(w;)),, Similar to Kingma & Bal (0015),
3

---

Under review as a conference paper at ICLR 2023
mi/(1 B1) to approximate Elg(wi ([:ww) where the denominator is for bias correction. Denote
8: m. mi/( 31)
1 1=1 1, t> 1.
m./(1 31) m. 11-
Therefore, we choose the precondition matrix B, satisfying
B diag(EMA(s)$f; s2s" $si ))/(1 89),
where Bg is the parameter of EMA and the denominator is also for bias correction.
AUTO SWITCH Normally, small value is added to B, for numerical stability, becoming B; cI. However, we replace with max Br. 6I), where we use a different notation 5 to indicate its essential role in auto switch. When b, == / (35) is relatively larger than 6, AdaDQH takes confident step the adaptive way. Otherwise, the update is EMA, i.e. my, with constant scale az/(1 $1 similar to SGD with momentum. Moreover, AdaDQH can auto switch modes in per parameter manner as training progresses.
Compared to the additive method, AdaDQH can eliminate the noise caused by in adaptive updates. Another major benefit that AdaDQH has the ability to generalize in different tasks by tuning without choosing from candidates of obscure optimizers empirically. The effect of 8 is discussed in Sec experimentally.
2.2
CONVERGENCE ANALYSIS
Using the framework developed in Reddi al. (2018); Yang al. (2016); Chen al. (2019); Zhou et al. (2018), we have the following theorems that provide the convergence in convex and non-convex settings. Particularly, we use B1, to replace 31 where B1, is non-increasing.
Theorem 1. (Convergence in convex settings) Let {w,} } be the sequence obtained by AdaDQH
(Algorithm D. = a/ Vt, B1 I B1 E [0, 1), 82 [0, 1), b S b141, Vi E [n) and || lo S Goo Vt E [ Suppose f((w) is convex for all E [T], w" is an optimal solution of ET I f((w). i.e, w arg min Ei= fe(w) and there exists the constant Doo such that max 1
w'lles o00 5 Dxo Then we have the following bound on the regret
Σ (f((ws) fc(w"))
1
n22G + +8)D2
VT
$1.1
nD
1 31
20V1
32(1
B2
2ā;
naG²
VT
[1 (1-31) 3,)3
8v1 - 322
The proof of Theorem iis given in Appendix A Corollary 1. Suppose 31.t = ///6, then we have
T Σ (Je(mn)) - fc(1n))) <
n(2Gxc + +
nD 31
VT +
VT
B1
20 - 11/11-11111 -31)²
avl B2
naG 60
VT
1 8v1 B2
(1 (1-8)) 81)3
The proof of Corollary I
is given Appendix B Corollary Dimplies the regret O(VT) and can achieve the convergence rate ((IVVT) in convex settings.
Theorem 2. (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 optimal solution. f is also L-smooth, i.e., Vu, v E "R, we have
L 1|u w1 2
f(u) < f(v) (Vf((), u w)
4

---

Under review as a conference paper at ICLR 2023
2. Ar step t. the algorithm can access bounded noisy gradient and the true gradient is bounded, i.e.
|Igelloo I G.. (w:lV I Go. Vt E [T]. Without loss of generality, we assume Goc 2 6.
3. The noisy gradient is unbiased and the noise is independent, i.e, 9: = Vf(w))) + Se. E(gi = 0 and Çi is independent of Sj if j.
4. a== a/Vi,, $1, 1 E (0, B2 E 10, 1) and bi, S b vi [n].
Then Algorithm 7 yields
log
Σ 04 - 31,11)
min Blll < V2
V2 +
+Cs
LE[T]
V2
VT v2
where Ct, C2 and C3 are defined as follows:
Go
nG
aßinG²2
C ae1
[(w01) ((w") +
(0 8La)
B1)2(1 (2))
(1 3882
(1 - 3:)
15Inn33
C2 2(1 32)²(1 - 200
nG
C3 ae1 - 31)5(1 -2)
The proof of Theorem is given in Appendix Note that we can let b max(bi+1 b;). which is usually called AMSGrad condition (Reddi et al. 2018), to make sure the assumption br, S Vi E [n]] always true, though it could degenerate the effect in practice. The more detailed analysis is given in Appendix E.3 From Theorem 2
we have the following corollaries.
Corollary 2. Suppose SI, 31/Vt, then we have
log T
min ( C.
+
CB
EE[T]
VT /2
VT
V2
where C4 and Cs are defined as follows:
C a(1 (1) B2)2
Go
[((u1) f(ww)((+)) ) (1 8,
nG2
(26 + +La) + aBinG?
(1 3,)38)
n²G
15
La +6)
Cs (1 32) - 1882
The proof of Corollary 2 is given in Appendix D Corollary 3. Suppose S1.t B1, Vt E [T], then we have
log T VT
min E [ |1 < C1 VT v2
C2
E
V2¹
where C1 and C2 the same with Theorem 2
Corollaries 2 imply the convergence (to the stationary point) rate for AdaDQH is O(log T TTV in non-convex settings.
2.3 NUMERICAL ANALYSIS
In this section, we compare AdaDQH against several SOTA optimizers in three test funtions. We adopt the parameter settings from Zhuang et al. (2020). The learning rate is set to le-3 for adaptive optimizers, along with the same epsilon/delta (Ie-8), betas (3) 0.9, B2 0.999). For SGD, momentum is set to 0.9 and learning rate is le-6 for numerical stability. AdaDQH shows promising results as it reaches the optimal points across all of the experiments, shown in Figure [ Furthermore, we search the best learing rate for each optimizer with regard to Beale function. AdaDQH is still the strongest competitor. The details provided in
5

---

Under review as a conference paper at ICLR 2023
NECCE
RACCE
ARCOK
(a) fæ, v)
(b) Beale function
(c) Rosenbrock function
Figure 1: Trajectories of different optimizers in three test functions, where f(r, 3) (x: y)²
(xc //0/ We also provide animated versions in the supplemental material.
Table 2: Experiments overview
Task
Dataset
Model
Train
Val/Test
Params
Cifar10
ResNet20/ResNer32
50K
10K
0.27M/0.47M
CV
ImageNet
ResNet18
1.28M
50K
11,69M
NLP-NMT IWSLT14 De-En
Transformer small
153K
7K/7K
36.7M
I-layer LSTM
5.3M
NLP-LM
PTB
2-layer LSTM
0.93M
730K/82K
13.6M
l-yer LSTM
24.2M
Avazu
MLP
36.2M
4.2M
151M
RecSys
Criteo
DCN
39.4M
6.6M
270M
EXPERIMENTS
3.1 EXPERIMENT SETUP
We experimentally compare the performance of different optimizers on wide range of learning tasks, including CV, NLP and RecSys. The details of the tasks are as follows.
CV: We experiment with ResNet20 and ResNet32 Cifar10 (Krizhessky et al. 2009) dataset, and ResNet1 on ImageNet (Russakovsky et al. 2015) dataset. The details of the datasets are listed in Table 2 We train 160 epochs and decay the learning rate by a factor of 10 epoch 80 and 120 for Cifar 10, and train 90 epochs and decay the learning rate by a factor of 10 every 30 epochs for ImageNet. The batch size 256 for both datasets.
NLP: We experiment with Neural Machine Translation (NMT) on IWSLT14 German- to--tt-----o to-English (De-En) (Cettolo al.) 2014). and Language Modeling (LM) Penn TreeBank (Marcus al.) 1993). For NMT task, transformer small architecture is adopted. We use the same setting and pre-processing
method in Yao al. 22020), well the same length penalty (1.0), beam size (5) and tokens (4096). We train 55 epochs and average the last 5 checkpoints for inference. For LM task, we train 1,2,3-layer LSTM with batch size of 20 for 200 epochs. The details are listed in Table Additionally, we keep settings like learning rate scheduler and warm-up steps identical for the same task.
We experiment on common datasets including Avazu (Avazu 2015) and Criteo (Criteo) 2014) which are various display ads logs for the purpose of predicting the Click Through Rate (CTR). For Avazu, the samples from the first nine days are used for training, while the rest are for testing. We use the basic Multilayer Perceptron (MI.) structure of most deep CTR models. Specifically, the model maps each categorical feature as a 16-dimensional embedding vector, following up with 4 fully connected layer of dimension in 66, respectively. For Critco, we take the carly 6/7 part all samples as the train set. We adopt Deep & Cross Network (DCN) (Wang et al. 2017) with embedding size set 8. along with 2 deep layers of size 64 and cross layers. The details listed in Table We train epoch with a batch size of 512 for both datasets.
RecSys:
Optimizers to be compared include SGD (Robbins & Monro 1951), Adam (Kingma & Ba 2015).
AdamW (Loshchilov & Hutter 2019). AdaBelief (Zhuang et al. (020) and AdaHessian (Yao et al.
2020). The choices of the hyperparameters given in Appendix E. The experiments of CV and

---

Under review as a conference paper at ICLR 2023
Table Top-1 accuracy for different optimizers when trained on Cifar10 and ImageNet.
Dataset Model
Cifar10
ImageNet ResNet18
ResNet20
ResNet32
SGD
92.14 + .14
93.10 .07
69.85 = .04
Adam
90.46 + .20
91.54 + .12
63.81 266
AdamW
92.12 +
92.72 + .01
68.91 = .09
AdaBelief
92.19 +.19
92.90 .13
69.93 .09
AdaHessian
92.27 227
92.91 + .14
69.94 = .99
AdaDQH
92.35 + 24
93.12 = -18
70.19 = .05
Table 4: Relative training time for AdaDQH (baseline), SGD and AdaHessian. Additionally, minutes of training one epoch with AdaDQH are provided. f is measured on one Nvidia P100 GPU, 3/$ on one/four Nvidia VI00 GPU. Note that results from the limitations Py PyTorch running RNN model with second order optimizers.
Dataset Model
Cifarl0
ImageNet ResNet18
IWSLT14 Transformer
PTB 2-layer LSTM
ResNet20
ResNet32
SGD
0.85x
0.84x
0.62 2.98 x
0.67
0.93x
AdaHessian
1.86x
2.16x
2.17x
9.80x*
AdaDQH
1.00x
1.00x
1.00x
1.00x
1.00
AdaDQH 0.52
0.62
11.25
3.88
0.30
(min/epoch)
NLP are conducted with GPUs in the PyTorch framework (Paszke et al.) 2019). and the experiments of RecSys are conducted with 3 parameter servers and 5 workers in the TensorFlow framework (Abadi al. 2016). We run all the experiments times with random seeds and calculate the statistical results.
3.2
Table reports the top-1 accuracy for different optimizers when trained on Cifarl0 and ImageNet. It is remarkable that AdaDQH outperforms other optimizers on both Cifar10 and ImageNet. The testing accuracy (jи o)) curves of different optimizers for ResNet20/32 on Cifar10 and ResNet18 on ImageNet are plotted in Figure Note that the results of SGD, AdaBelief and AdaHessian on ImageNet are lower than the number reported in original papers (Chen al. 2020) Zhuang et
2020; Yao et al. 2020) which are single time. More discussions are given in Appendix E.4 We also report the accuracy of AdaDQH for ResNet18 on Cifar for comparing with the SOTA results which is listed in Appendix E.5 In addition, it is worth mentioning that although AdaDQH considered as quasi- Hessian, its runtime cost comparable with SGD and much lower than AdaHessian, which is shown in Table 4
3.3 NLP
We report case-insensitive BiLingual Evaluation Understudy (BLEU, higher is better) score and the perplexity (PPL, lower is better) on test set for NMT and LM tasks respectively. The results shown in Table For the NMT task on IWSLT14, AdaDQH achieves a similar result to AdaBelief, outperforming the other optimizers. For LM task PTB, AdaDQH obtains lowest PPL in all 1,2.3-layer LSTM experiments, as demonstrated in Figure Furthermore, we report the relative training time in Table which is similar to CV.
3.4 RECSYS
We adopt Area Under the receiver-operator Curve (AUC) as the evaluation criterion which is a good measurement in CTR estimation (Graepel et al. 2010). 6 that compared to other

---

Under review as a conference paper at ICLR 2023
03
Trotr aeruney
3.70
303
343
191
Epoch
Spech
(a) ResNet20 on Cifar10
(b) ResNet32 on Cifar10
(c) ResNett88 on ImageNet
Figure 2: Testing accuracy curves of different optimizers for ResNet20/32 on Cifarl0 and ResNet18 on ImageNet. The solid line represents the mean of the results and the shaded area represents the standard deviation.
70
Ezech
Erech
Srech
(a) I-layer
(b) 2-layer
(c) 3-layer
Figure Test PPL ([μ + o Penn Treebank for 1,2,3-layer LSTM.
622
I2.
Ratio (%)
1::41
11 1m:0
1e-34 2o-51
Be.. 16-0
11 1n-91
22,63
20
1.07 3.5
0.21
0.26
0.32
5:31
0.30
6.35
5.35
6:35
0.35
10
40
7.
10
20
30
40
Epoch
Epoch
(a) ResNet18 on ImageNct
(b) Transformer on IWSLT14
100
67.05
03.02
23
91.2
100
200
80
22.22
60
Ratio (9))
60
[6. 1e301
1e-81
(1.4,
11 4,
20
10000 20000 30000
40000 5 50000 6000e 70000
Epoch
Global Step
(c) 2-yeerr L.STM on PTB
(d) DCN on Criten
Figure 4: The distribution of b, on different epochs/steps. The colored area denotes the ratio of b, in the corresponding interval. The values of 5 of ResNet18 on ImageNet, Transformer on IWSLT14, 2-layer LSTM on PTB, and DCN on Criteo are le-5, le-14, 14, le-5 and 1e-8 respectively.
8

---

Under review as a conference paper at ICLR 2023
Table 5: Test BLEU score and PPL for NMT and LM tasks. f reported in Yao (2020).
Dataset
IWSLT14
PTB
Metric Model
BLEU, higher better Transformer
PPL., lower better
1-layer LSTM
2-layer LSTM
3-layer LSTM
SGD
28.57 15 f
85.36 + .34
67.26 + .17
63.68 + .17
Adam
29.61 - .17
84.50 + .16
67.01 + .11
64.45 + .26
A
35.75 .03
88.16 + .19
95.25 + 1.33
102.61 + 1.13
AdaBelief
35.93 .88
84.40 + .21
66.69 + .23
61.34 .11
AdaHessian
35.79 06
88.62 - .15
73.37 .22
69.51 + .19
AdaDQH
35.94 = .11
81.23 ..17
65.84 .18
60.89 .09
Table 6: Test AUC for different optimizers when trained on Avazu and Criteo.
Dataset Model
Avazu MI.P
Criteo DCN
SGD
0.7463 + .0005
0.7296 + .0067
Adam
0.7458 .000
0.8023 + 0002
AdaBelief
0.7467 = .0009
0.8022 + .0002
AdaHessian
0.7434 + .0006
0.7995 + .0018
AdaDQH
0.7480 + .0008
0.8023 + .0004
optimizers, AdaDQH achieve significantly better highly competitive performance the AUC metric.
3.5 THE EFFECT OF 8
In this section, we analyze the rigorous effect 5, i.e., what exact percentage of b, truncated by depicts the distribution of b during the training process on different tasks in the best configuration we found. The black dot gives the exact percentage of that is truncated by in the task. Lower percentage means more SGD-like updates than adaptive steps, which is controlled by the choice of 8.
in Algorithm Figure 4igurctdeppicss
Figure 4 reveals how auto switch in AdaDQH works in different tasks. As shown in Figure 4a AdaDQH behaves more like SGD in early stage of training (before the first learning rate decay at the 30th epoch) and switches the adaptive for fine-tuning, since SGD generally outperforms the adaptive optimizers in CNN tasks. (aaure/Abindicatee that the parameters taking adaptive updates are dominant, which is expected because the adaptive optimizers like AdamW are preferred in transformer. As indicated in Figure 4c most parameters are updating stochastically, which explains why AdaDQH
a similar eurve to SGD 3% to 5% afterwards, resulting in better PPI. in the fine-tuning stage. As for Figure 4d the model of the RecSys task is training for only one epoch, and AdaDQH gradually switch to the adaptive updates for better fit to the data.
(3) the 100th epoch. The ratio grows from
4 CONCLUSION
In this paper, we propose the AdaDQH optimizer, which can evolve from stochastic to adaptive by auto switch of the precondition matrix and has better generalization compared to the SOTA optimizers. We theoretically prove the convergence rate in both convex and non-convex stochastic settings and conduct empirical evaluation in real-world datasets of different scenes. The results clearly demonstrate the advantages of our optimizer in getting significantly better performance. Finally, we analyze how it is able to auto switch from stochastic to adaptive, and the rigorous effect of the hyperparameter 5 which controls the auto-switch process.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martín Abadi, Paul Barham, Jiammin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthicu Devin, Sanjay Ghemawar, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek Gordon Murray, Benoit Steiner, Paul A. 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 (eds.), 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016. pp. 265-283 USENIX Association, 2016.
Shun-ichi Amari. Natural gradient works efficiently in learning. Neural Comput., 10(2)251-276. 1998. doi: 10. 0,.1166/8899666980000077777 7746.
Avazu. Avazu throuut rate prediction. BttDs///ww..kcgllecoom///////2/ prediction/datt 2015.
Richard H. Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. A limited memory algorithm for bound constrained optimization. SIAM J. Sci. Comput., (6(5):119--12000 1995. doi: 10.1137/091006)
Mauro Cettolo, Jan Niehues, Sebastian Stüker, Luisa Bentivogli, and Marcello Federico. Report on the 11th IWSLT evaluation campaign. In Proceedings of the 11th International Workshop on Spoken Language Translation: Evaluation Campaign, pp- 2-17, Lake Tahoe, California, December 4-5 2014.
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, pp. 3239-3247, 07 2020. doi: http://///cca.222/444433
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 Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Criteo. Criteo display ad challenge. sttp::/labs.critee.co//// isgplaa--avverriiinng-e
leenge-dataee 2014.
John Duchi, Elad 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/1953048.22222 2028
Thore Graepel, Joaquin Quiñonero Candela, Thomas Borchert, and Ralf Herbrich. Web-scale bayesian thick-through rate prediction for sponsored search advertising in microsoft's bing search engine. In Johannes Fürnkranz and Thorsten Joachims (eds.), Proceedings of the 27th Interna- tional Conference Machine Learning (ICML-10), June 21-24, 2010, Haifa, Israel, pp. 13-20. Omnipress, 2010.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor opti- mization. In Jennifer G. Dy and Andreas Krause (eds.), 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, pp. 1837-1845. PMLR, 2018.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam SGD. CoRR, abs/1712.07661
2017.
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.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced research). httppp//www..cc.ooootttteeatt/ts
2009.
Frederik Kunstner, Philipp Hennig, and Lukas Balles. Limitations of the empirical fisher approxi- mation for natural gradient descent. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'lch-BBuc Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pp. 4158-4169 2019.
10

---

Under review as a conference paper at ICLR 2023
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dy- namic bound of learning rate. In 7th International Conference on Learning Representa- tions, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, OpenReview.net, 2019. URL
https:/ https://opentee http::/pppennevie.eeeeeeeeeeee fow.: BOC
Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large annotated corpus of English: The Penn treebank, June 1993.
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 T. Nguyen, Alain Rakotomamonjy, Zaccharie Ramzi, Joseph Salmon, and Samuel Vaiter. Benchopt: Reproducible, efficient and collaborative optimization benchmarks. 2022. URL
abs/ 220 6.1444
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 Z. Yang, Zachary Vitioo, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 8024-8035, 2019.
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: 10.1016/0041- 5553(64991137-5.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In Proceedings of the 6th International Conference Learning Representations, ICLR '18, Vancouver, BC, Canada, 2018. OpenReview.net.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
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 (IJCV), 115 (3):211 10:211-252,, 2015. doi: 10.1007/s1 1207///1263-00--001111
Ruoxi Wang, Bin Fu, Gang Fu, and Mingliang Wang. Deep & cross network for ad click predictions. In Proceedings of the ADKDD'I7, 17, Halifax, NS, Canada, August 13 17, 2017, pp. 12:1-12:7.
ACM, 2017. doi: 10. 1
Tianbao Yang. Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. CoRR, 604.0355..3,,. 2016.
Zhewei Yao, Amir Gholami, Sheng Shen, Kurt Keutzer, and Michael W. Mahoney, ADAHESSIAN: an adaptive second order optimizer for machine learning. CoRR, abs/2006.00719, 2020
Matthew D. Zeiler. Adadelta: An adaptive learning rate method. CoRR, ab//1212550110 2012.
Dongruo Zhou, Yigi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. CoRR, 0abs/180.,056771 2018.
Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C. Tatikonda, Nicha C. Dvorek, Xenophon Papademetris, and James S. Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
11


Reviews:
[{"review_id": "aTUH2x-e9s", "reviewer": "Reviewer_cyVQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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 research is on developing an adaptive optimization algorithm called AdaDQH, which proposes a new technique to approximate the Hessian matrix in the second-order gradient descent scheme in a computationally efficient manner. The authors demonstrate the optimizer’s performance on datasets from Natural Language Processing, Computer Vision, and Recommendation Systems to show faster convergence and better generalization. The paper also provides theoretical proofs on bounds on regret and time complexity to explain the trade-off between generalization, time and computational resources. Weights in a deep-network at iteration are updated as:\n   w_(t+1) = w_t − α_t B_t^(−1t) m_t\nwhere,α_t is the step-size, represents a linear combination of the gradients ∇_wL(w_t) , and B_t, called as the precondition matrix is an approximation of the Hessian H_t . Several previous second-order optimization algorithms like AdamW, AdaBelief, AdaHessian have developed methods to approximate . The current algorithm, AdaDQH, selects B_t as: B_t^2 = diag(EMA(s_1s_1^T, s_2s_2^T, s_ts_t^T ))/(1 − β_2^t))\nwhere, EMA represents an exponential moving average, and is given by a recurrent relation in terms of s_t.\nThe structure of is adopted for bias-correction is similar to Adam. In addition to approximating the Hessian, the research also proposes a way to switch between an adaptive version and EMA version for the gradients.\n\n", "summary_of_the_review": "Research paper is well-presented and produces a novel technique to approximate the Hessian for optimization. Overall, it’s an important paper to be considered in Machine Learning.\n\nAdditional Comments:\n\nWhat is s_t, b_t and beta_2?\nCould different notations be used for vector and scalar?\nThe paper updates B_t with max(B_t , delta*I). Why is this so?\nHow was equation 3 obtained from equation 2?\nIs it possible to give mathematical guarantees on autoswitch? Say when it switches and in which conditions does it occur.\n\n", "strength_and_weaknesses": "1. The paper provides mathematical details to support time-complexity and computational analysis, and bounds for establishing convergence.\n2. Results for the paper cover problems from different areas in Machine Learning and Optimization, adding to credibility and usefulness in the future.\n3. An essential point covered in the paper is: Trade-off of computations, time and generalization.\n4. It would be interesting to note the performance of AdaDQH on highly non-convex optimization problems  (i.e. functions with several local minima) like Ackley and Schwefel. This would help test the idea of whether AdaDQH is able to converge to global minima or not. Challenge problems from CEC 2019 would also help.\n5. An important question arises: Is AdaDQH able to converge to global minima of few functions wherein the current state-of-the-art algorithms are only able to make it to local minima? This would make it a significant improvement over the current state-of-the-art algorithms.", "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": "G8uLcKx2ck", "reviewer": "Reviewer_EHjo", "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 paper studies an Adam type optimizer, adaDQH, by designing a new rule to update $v$. The idea is i) using gradient difference to approximate (diagnalized) Hessian, and ii) using a max in the denominator of to switch AdaDQH to SGD when necessary. Theoretical results and numerical tests are carried out to support the convergence of proposed AdaDQH.", "summary_of_the_review": "The proposed AdaDQH is interesting in how the Hessian is estimated. However, this paper does not provide convincing explanation to their Hessian estimate, and does not compare with existing works with similar ideas. Some of experiments are not carried out on standard models making their numerical improvement less impressive.", "strength_and_weaknesses": "**Strength:**\n- S1. The idea to approximate Hessian is interesting.\n- S2. On tested tasks, AdaDQH exhibits improved performance. \n\n**Weakness:**\n\n- W1. (Novelty.) Two of key ideas, Hessian approximation, and auto switch have been used in the literatures but not well cited. For example, the idea of using gradient difference to estimate Hessian appeared in http://proceedings.mlr.press/v70/zheng17b.html, and the auto switch shares similar idea to https://arxiv.org/abs/1902.09843. In addition, although the idea of approximating Hessian is interesting, the motivating equation in two lines after Alg. 1 is less convincing. First, the value of $\\theta$ is taken as 1, however, the reason is unclear. If it is taken from mean value theorem, the choice of $\\theta$ can be different in different cases. Second, the reason to set $\\Delta w$ to $e_i$ is also unclear, and it looks like this is not the case when updating the model weights. It can be more reasonable if the authors can plot the difference between the proposed Hessian estimation and real Hessian. Another question is that how well does EMA approximates the true gradient. The lack of justification makes the claim \"better estimated Hessian\" less convincing. \n\n- W2. (Numerical experiments.) It looks like the models for evaluating the proposed algorithm are not well chosen. For example, it is standard to use ResNet50 rather than ResNet18 on ImageNet. And ResNet18 can easily achieve 93 - 94\\% test accuracy on CIFAR10, while the tested ResNet20 and ResNet32 struggle on the same task. The choice of testing models makes the numerical results less competitive.\nAnd why are some results in Table 4 are training on P100 and some on V100? \n\n\n(Minor 1) Does the experiment in Figure 1 take stochastic gradient into account?\n\n(Minor 2) The theory uses diminishing $\\beta_{1,t}$ while the main algorithm adopts fixed $\\beta_1$.\n", "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": "2mTZzZlSAMx", "reviewer": "Reviewer_FWdz", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper extends AdaBelief by making two modifications: (1) the 2nd momentum s_t is computed by taking the EMA of (m_t/(1-beta_1^t)-m_{t-1}/(1-beta_1^{t-1}) )^2 in comparison to the EMA of (m_t-g_t)^2 in AdaBelief; (2) the parameter delta (or epsilon  in AdaBelief) is introduced in a slightly different manner to avoid division by zero.  The new optimiser is referred to as ADADQH. Experiments on different DNN tasks indicates that ADADQH produce either better and competitive performance. ", "summary_of_the_review": "The paper proposes two new modifications to AdaBelief, and demonstrates performance gain on both synthetic and real-data experiments. 1. The connection between the proposed method  ADADQH and the two existing methods AdaBelief and Aida should be studied, or properly described in the introduction in the paper so that the readers better understand the reasoning behind it. 2. The parameter epsilon needs to be searched for each optimizer in order to make a fair comparison in all experiments. 3. The paper needs to conduct ablation study to find out which modification in ADADQH is more important to improve performance in AdaBelief. ", "strength_and_weaknesses": "Strength: \n1. The paper propose new types of modifications to AdaBelief, aiming to improve its performance, which I haven't seen from literature before. \n2. Theoretical analysis is provided for the new method. \n\nWeekness: \n(1) As I mentioned earlier, ADADQH made two modifications to AdaBelief. It is not clear which modification plays a crucial role for the performance gain. I am guessing the first modification for computing s_t makes a difference in performance improvement. The reason is that m_t/(1-beta_1^t)-m_{t-1}/(1-beta_1^{t-1}) = (1-beta_1)/(1-beta_1^t) * [g_t - m_{t-1}/(1-beta_1^{t-1})]. The scalar  (1-beta_1)/(1-beta_1^t) essentially reduce the variance of the adaptive stepsizes in comparison to AdaBelief which computes the EMA of (g_t-m_t)^2.  In a recent paper \"On Exploiting Layerwise Gradient Statistics for Effective Training of Deep Neural Networks\", another method named Aida was proposed to reduce the variance of the adaptive stepsizes of AdaBelief by performing vector projections between m_t and g_t before being used for the computing the 2nd momentum. I suggest the authors to conduct performance also in comparison to Aida. In the abstract, the authors state that ADADQH is compared to SOTA optimizers. Both Aida and ADADQH are closely related to AdaBelief and should be compared.  \n\n(2) In AdaBelief paper, the validation accuracy of AdaBelief for training ResNet34 over CIFAR10 is above 95%. In the current paper, the validation accuracy of AdaBelief for training ResNet32 over CIFAR10 is below 93%. Even though ResNet 34 is slightly complicated than ResNet32, I think the performance gap is too large for AdaBelief.  I suggest the authors take the opensource from AdaBelief to make a direct comparison. \n\n(3) My personal experience is the selection of parameter epsilon in Adam and AdaBelief plays a very important role in the performance. In order to make a fair comparison, the parameter epsilon needs to searched for each optimizer. In Figure 1, I don't see that the parameter epsilon  is being searched for Adam and AdaBelief. Inproper epsilon value in Adam and AdaBelief would slow down their convergence speed.  ", "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": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject