Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models
Authors: Xingyu Xie
Pan Zhou
Huan Li
Zhouchen Lin
Shuicheng YAN
Venue: Submitted to ICLR 2023 (2023)
Keywords: DNN optimizer
Deep Learning Optimization
AdamW
Large Batch Training
ViT
ResNet
Network Optimization

Abstract: Adaptive gradient algorithms combine the moving average idea with heavy ball acceleration to estimate accurate first- and second-order moments of the gradient for accelerating convergence.  However, Nesterov acceleration which converges faster than heavy ball acceleration in theory and also in many empirical cases, is much less investigated under the adaptive gradient setting.  In this work, we propose the ADAptive Nesterov momentum algorithm, Adan for short, to speed up the training of deep neural networks effectively.  Adan first reformulates the vanilla Nesterov acceleration to develop a new Nesterov momentum estimation (NME) method, which avoids the extra computation and memory overhead of computing gradient at the extrapolation point.  Then Adan adopts NME to estimate the first- and second-order moments of the gradient in adaptive gradient algorithms for convergence acceleration. Besides, we prove that Adan finds an $\epsilon$-approximate first-order stationary point within $O(\epsilon^{-3.5})$ stochastic gradient complexity on the non-convex stochastic problems (e.g., deep learning problems), matching the best-known lower bound. Extensive experimental results show that  Adan surpasses the corresponding SoTA optimizers on vision, language, and RL tasks and sets new SoTAs for many popular networks and frameworks, e.g., ResNet,  ConvNext, ViT, Swin, MAE, LSTM, Transformer-XL, and BERT.  More surprisingly, Adan can use half of the training cost (epochs) of SoTA optimizers to achieve higher or comparable performance on ViT, ResNet, MAE, etc., and also shows great tolerance to a large range of minibatch size, e.g., from 1k to 32k.  We hope Adan can contribute to developing deep learning by reducing training costs and relieving the engineering burden of trying different optimizers on various architectures.

Under review as a conference paper at ICLR 2023
ADAN: ADAPTIVE NESTEROV MOMENTUM ALGO- RITHM FOR FASTER OPTIMIZING DEEP MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
Adaptive gradient algorithms combine the moving average idea with heavy ball acceleration to estimate accurate first- and second-order moments of the gradient for accelerating convergence. However, Nesterov acceleration which converges faster than heavy ball acceleration in theory and also in many empirical cases, is much less investigated under the adaptive gradient setting. In this work, we propose the ADAptive Nesterov momentum algorithm. Adan for short, to speed up the training of deep neural networks effectively. Adan first reformulates the vanilla Nesterov acceleration to develop new Nesterov momentum estimation (NME) method, which avoids the extra computation and memory overhead of computing gradient at the extrapolation point. Then Adan adopts NME to estimate the first- and second-order moments of the gradient in adaptive gradient algorithms for convergence acceleration. Besides, we prove that Adan finds an e-approximate first-order stationary point within ( (3.5) stochastic gradient complexity on the non-convex stochastic problems (e.g. deep learning problems), matching the best- known lower bound. Extensive experimental results show that Adan surpasses the corresponding SoTA optimizers vision, language, and RI tasks and sets new So'TAs for many popular networks and frameworks, e.g. ResNet, ConvNext, ViT, Swin, MAE, LSTM, Transformer-XL. and BERT. More surprisingly. Adan can use half of the training cost (epochs) of SoTA optimizers to achieve higher or comparable performance on ViT, ResNet, MAE, etc, and also shows great tolerance to a large range of minibatch size, egg. from 1 to 32k. We hope Adan can contribute to developing deep learning by reducing training costs and relieving the engineering burden of trying different optimizers on various architectures.
INTRODUCTION
Deep neural networks (DNNs) have made remarkable success in many fields, e.g. computer vi- sion (Szegedy et al., 2015; He et al., 2016) and natural language processing (Sainath et al., 2013; Abdel-Hamid et al., 2014). A noticeable part of such success is contributed by the stochastic gradient-basee optimizers, which find satisfactory solutions with high efficiency. Among current deep optimizers, SGD (Robbins & Monro, 1951) is the earliest and also the most representative stochastic optimizer, with dominant popularity for its simplicity and effectiveness. It adopts a single common learning rate for all gradient coordinates but often suffers unsatisfactory convergence speed on sparse data or ill-conditioned problems. In recent years, adaptive gradient algorithms, e.g. Adam (Kingma & Ba, 2014) and Adam W (Loshchilov & Hutter, 2018), have been proposed, which adjust the learning rate for each gradient coordinate according to the current geometry curvature of the loss objective. These adaptive algorithms, e.g. Adam, often offer faster convergence speed than SGD in practice.
However, none of the above optimizers can always stay undefeated among all its competitors across different network architectures and application settings. For instance, for vanilla ResNet (He et al., 2016). SGD often achieves better generalization performance than adaptive gradient algorithms such as Adam, whereas on vision transformers (ViTs) (Touvron et al., 2021), SGD often fails, and AdamW is the dominant optimizer with higher and more stable performance. Moreover, these commonly used optimizers usually fail for large-batch training, which is default setting of the prevalent distributed training. Although there is some performance degradation, we still tend to choose the setting for large-scale deep learning training tasks due to the unaffordable training time. For example, training the ViT-B with the batch size of 512 usually takes several days, but when the batch size comes to 32K, we may finish the training within three hours (Liu al., 2022a). Although some

---

Under review as a conference paper at ICLR 2023
Table 1: Comparison of different adaptive gradient algorithms on nonconvex stochastic problems. "Separated Reg." refers to whether the &2 regularizer (weight decay) can be separated from the loss objective like AdamW. "Complexity" denotes stochastic gradient complexity to find an c- approximate first-order stationary point. Adam-type methods (Guo et al., 2021) includes Adam, and AdaGrad (Duchi et al., 2011), etc. A has no available convergence result. For SAM (Foret et al., 2020), A-NIGT (Cutkosky & Mehta, 2020) and Adam (Liu et al., 2020), we compare their adaptive versions. is the variable dimension. The lower bound is proven in (Arjevani et al., 2020).
Condition
Smooth
Optimizer
Separated Reg.
Batch Size Condition
Grad Bound
Complexity
Lower Bound
Adam-type
X
too Coo
O d)
A(E 2((
RMSProp
foo S Coo
O (vecoder
Lipschitz
AdamW
Adabelief
X
X
f2 02
((Ger-1)
a(c-
Gradient
Padam
X
X
8oo S Coo
(veoode
LAMB
X
( (E
8 S 02 600 Coo
Oledde
a
Adan (ours)
O
(((
Lipschitz
A-NIGT
X
X
4 S 02 81
Olc 3.5 log 2
Hessian
Adam
X
O L.26)
(c-33.22) ( -3.5) 33.5)
((c-3.))
Adan (ours)
X
860 S Coo
(15-3.5)
methods, e.g. LARS (You et al., 2017) and LAMB (You al., 2019), have been proposed to handle large batch sizes, their performance often varies significantly across batch sizes. This performance inconsistency increases the training cost and engineering burden, since one usually has to try various optimizers for different architectures or training settings.
When we rethink the current adaptive gradient algorithms, we find that they mainly combine the moving average idea with the heavy ball acceleration technique to estimate the first- and second-order moments of the gradient, e.g. Adam, AdamW and LAMB. However, previous studies (Nesterov, 1983; 1988; 2003) have revealed that Nesterov acceleration speed than heavy ball acceleration, as it uses gradient at an extrapolation point of the current solution and sees a slight "future". Moreover, recent work (Nado al., 2021; He al., 2021) have shown the potential of Nesterov acceleration for large-batch training. Thus we are inspired to consider efficiently integrating Nesterov acceleration with adaptive algorithmss
theoretically achieve a faster convergence
Contributions: 1) We propose an efficient DNN optimizer, named Adan. Adan develops Nesterov momentum estimation method estimate stable and accurate first- and second-order moments of the gradient in adaptive gradient algorithms for acceleration. 2) Moreover, Adan enjoys provably faster convergence speed than previous adaptive gradient algorithms such Adam. 3) Empirically, Adan shows superior performance over the SoTA deep optimizers across vision, language, and reinforcement learning (RL) tasks. Our detailed contributions are highlighted below.
Firstly, we propose an efficient Nesterov-acceleraiion--ddeee deep learning optimizer termed Adan. Given a function f and the current solution 0x. Nesterov acceleration (Nesterov, 1983; 1988; 2003) estimates the gradient ga f(() at the extrapolation point 0% 0₂ 7 81 )m;-1 with the learning rate and momentum coefficient 31 E 1), and updates the moving gradient average m (1 31 - + gx- Then it runs step by 0x+1 0r sym,- However, the inconsistency of the positions for parameter updating at 0₂ and gradient estimation at 0% leads to the additional cost of model parameter reloading during mrokppropngttion (BP), which is unaffordable especially for large DNNs. To avoid the model reloading during BP, we propose an alternative Nesterov momentum estimation (NME). We compute the gradient g& vf((x)) at the current solution 0g. and estimate the moving gradient average as m, = (1 $1 )ijmm + g where gl gk + (1 -g: 1) Our NME is provably equivalent to the vanilla one yet can avoid the extra model reloading. Then by regarding g/. as the current stochastic gradient in adaptive gradient algorithms, e.g. Adam, we accordingly estimate the first- and mecond-moments as m, = (1 (1- 31 m + Big and n; = (1 - 32)n + 32(g() respectively. Finally, we update o 0₁ nmm / ny + E. In this way, Adan enjoys the merit of Nesterov acceleration, namely faster convergence speed and tolerance to large mini-bate size (Lin et al., 2020), which is verified in experiments in Sec. 5.
2

---

Under review as a conference paper at ICLR 2023
Secondly, shown in Table I, we theoretically justify the advantages of Adan over previous SoTA adaptive gradient algorithms on nonconvex stochastic problems, e.g. deep learning problems.
1) Given Lipschitz gradient condition, to find e-approximate first-order stationary point, Adan has the stochastic gradient complexity O 220 which accords with the lower bound l?(e (up to a constant factor) (Arjevani et al., 2019). This complexity is lower than Oce of Adabelief (Zhuang et al., 2020) and O (c of LAMB, especially on over-parameterized networks. Specifically, for the d-dimensional gradient, compared with its &g norm 022 its &oo norm Coo is usually much smaller, and can be vdx smaller for the best case. Moreover, different from Adam-type optimizers (e.g. Adam), Adan can separate the &g regularizer with the loss objective like AdamW whose generalization benefits have been validated in many works (Touvron et al., 2021).
2) Given the Lipschitz Hessian condition, Adan has complexity O(c2225 which also matches the lower bound (2(--3.) in Arjevani al. (2020). This complexity is superior O log @) of A-NIGT (Cutkosky & Mehta, 2020) and also ( of Adam (Liu al., 2020). Indeed, Adam* + needs the minibatch size of order ( 1.625) (65)))25)) which is prohibitive in practice. For other optimizers, e.g. Adam, their convergence has not been provided yet under Lipschitz Hessian condition.
Finally, Adan simultaneously surpasses the corresponding SoTA optimizers across vision, lan- guage, and RL tasks, and establishes new SoTAS for many networks and settings, e.g. ResNet, ConvNext (Liu et al., 2022b), ViT (Touvron et al., 2021), Swin (Liu et al., 2021), MAE (He et al., 2022), LSTM (Schmidhuber al., 1997). Transformer-XL (Dai et al., 2019) and BERT (Devlin et al., 2018). More importantly, with half of the training cost (epochs) of SoTA optimizers. Adan can achieve higher or comparable performance. Besides, Adan works well in large range of minibatch size, e.g. from Ik to 32k on ViTs. The improvement of Adan for various architectures and settings can greatly relieve the engineering burden by avoiding trying different optimizers.
2 RELATED WORK
Current DNN optimizers can be grouped into two families: SGD and its accelerated variants, and adaptive gradient algorithms. SGD computes stochastic gradient and updates the variable along the gradient direction. Later, heavy-ball acceleration (Polyak, 1964) movingly averages stochastic gradient in SGD for faster convergence. Nesterov acceleration runs step along the moving gradient average and then computes gradient at the new point to look ahead for correction. Typically, Nesterov acceleration converges faster both empirically and theoretically least on convex problems, and also has superior generalization resutls on DNNs (Foret et al., 2020; Kwon et al., 2021).
Unlike SGD, adaptive gradient algorithms, egg. AdaGrad, RMSProp and Adam, view the second moment of gradient as preconditioner and also use moving gradient average to update the variable. Later, many variants have been proposed to estimate a more accurate and stable first moment of gradient or its second moment, e.g. AMSGrad, Adabound, and Adabelief. To improve generalization, AdamW splits the objective and trivial regularization, and its effectiveness is validated across many applications; SAM and its variants (Kwon et al., 2021) aim to find flat minima but need forward and backward twice per iteration. LARS and LAMB train DNNs with a large batch but suffer unsatisfactory performance
small batch. Xie et al. (2022) reveal the generalization and convergence gap between Adam and SGD from the perspective of diffusion theory and propose the optimizers, Adai, which accelerates the training and provably favors flat minima. Padam (Chen et al., 2021a) provides a simple but effective way to improve the generalization performance of Adam by adjusting the second-order moment Adam. The most related work to ours NAdam. It simplifies Nesterov acceleration to estimate the first moment of gradient in Adam. But its acceleration does not use any gradient from the extrapolation points and thus does not look ahead for correction. Moreover, there is no theoretical result to ensure its convergence. See more difference discussion in Sec. 3.2.
3 METHODOLOGY
In this work, study the following regularized nonconvex optimization problem:
ming F(O)= = EC-D [ ()] - 1011
+)
where loss .(,,-) is differentiable and possibly nonconvex, data is drawn from unknown distribution D. 0 is learnable parameters, and || is the classical E norm. At below, we first introduce the key motivation of Adan in Sec. 3. and then give detailed algorithmic steps in Sec. 3.2.
3

---

Under review as a conference paper at ICLR 2023
3.1 PRELIMINARIES
Adaptive gradient algorithms, Adam and AdamW, have become the default choice to train CNNs and ViTs. Unlike SGD which uses one learning rate for all gradient coordinates, adaptive algorithms adjust the learning rate for each gradient coordinate according to the current geometry curvature of the objective function, and thus converge faster. Take RMSProp and Adam as examples. Given stochastic gradient estimator gi == < V (Ok,, S)] + Ek, e.g. minibatch gradient, where & is the gradient noise, MSPrrop updates the variable as follows:
mk = (1- - 31 m -1 + Bggk
ng (1 1-8))n B) 11 8gi
RMSProp:
Adam:
ng = (1 -1 B/2 n + :3gg
0x+1 0₁ -n/(v n + E) gk:
0x+1 = 02 - 77/ ( n + my:
where my go. no gū: the scalar 7) is the base learning rate, and denotes the element- product. Based on RMSProp, Adam replaces the estimated gradient gk with a moving average m of all previous gradient ga- By inspection, one can easily observe that the moving average idea in Adam is similar to the classical (stochastic) heavy-ball acceleration (HBA) technique (Polyak, 1964):
HBA:
gk f(x)) + Ex.
m = (1 3 m + gk:
0x+1 = 0, - 17m3-
Both Adam and HBA share the spirit of moving gradient average, though HBA does not have the factor 31 on the gradient gt- That is, given one gradient coordinate, if its gradient directions are more consistent along the optimization trajectory, Adam/HBA accumulates larger gradient value in this direction and thus goes ahead for a bigger gradient step, which accelerates convergence.
In addition to HBA, Nesterov's accelerated (stochastic) gradient descent (AGD) (Nesterov, 1983; 1988; 2003) is another popular acceleration technique the optimization community:
AGD: g& = ff(0,- -1(1 -) + m = (1 -1- (1-33)) 31 m 0t+1 = 0 7m (2)
Unlike HBA, AGD uses the gradient at the extrapolation point 0z = O2 71(1 - 3 ) Hence when the adjacent iterates share consistent gradient directions, AGD sees slight future to converge faster. Indeed, AGD theoretically converges faster than HBA and achieves optimal convergence rate on the general smooth convex problems (Nesterov, 2003). Meanwhile, since the over-parameterizer DNNs have been observed/proved to have many convex-alike local basins (Hardt & Ma, 2016; Xie al., 2017; Li Yuan, 2017), AGD seems more suitable than HBA for DNNs. For large-batch training. Nado et al. (2021) showed that AGD has the potential to achieve comparable performance to some specifically designed optimizers, egg. LARS and LAMB. With its advantage in convergence and large-batch training, consider applying AGD to improve adaptive algorithms.
3.2
ADAPTIVE NESTEROV MOMENTUM ALGORITHM
Main Iteration. We temporarily set À 0 in Eqn. (1). As aforementioned, AGD computes gradient at an extrapolation point 8 instead of the current iterate 0j., which however brings extra computation and memory overhead for computing 0% and preserving both O₂ and 0% To solve the issue, Lemma I with proof in Appendix D reformulates AGD (2) into its equivalent but more DNN-efficient version.
Lemma 1. Assume E(Ex)
Cov EE,, E,) 0 for any k, i O, 0₂ and my be the iterate and momentum of the vanilla AGD in Eqn. (2), respectively. Let 0x+1 = 0 1/(1 B1 )m, and mm-1- m (1 - + (2 3: (V + Ex). The vamilla AGD in Eqn. (2) becomes AGD-II:
g: - -E +),+ m (1 31 - [g + (1-B1) (gx gk-1)), 0x+1 = 02 mmm..
Moreover, if vanilla AGD in Eqn. (2) converges, so does AGD-II, and Re0 = R0(02))
The main idea in Lemma is that we maintain (0,- 7 81 ) rather than 0₃ in vanilla AGD at each iteration, since there is no difference between them when the algorithm converges. Like other adaptive optimizers, by regarding g = gi (1 31 )gx gk-1) the current stochastic gradient and movingly averaging g to estimate the first- and second-moments of gradient, we obtain
m (1 8 ).)mm + $ [g: + (g) 8x-1)]
Vanilla Adan:
n₂ (1 33 n Bolge + (1 -1-33)) (:) g)-1) )
0x+1 0₂ 7 m. with 7)s = mg=///nn, +c).
For presentation convenience, we omit the de-bias term in adaptive gradient methods.
4

---

Under review as a conference paper at ICLR 2023
The main difference of Adan with Adam-type methods and Nadam (Dozat, 2016) is that as compared in Equ. (3), the momentum m, of Adan is the average of {gr + (1- 31)(g. gt-1)]=-1 while those of Adam-type and Nadam the average of {gr 1Bere- So is their second-order term ng.
Σ Cket g: + (1 - Bi)(g= g(-1)),
Adan,
(1 (k)()
t> 0,
Ck St
Adam,
(3)
t0= (t)
+
1e 2
gA:
Nadam,
(1 81)
0,
Pe+1
where (n4)r=1 is predefined exponentially decaying sequence, /ig I 14. So Nadam is more like Adam than Adan, as their m; movingly averages the historical gradients instead of gradient differences in Adan. For large &s (i.e. small pa),, my in Nadam and Adam are almost the same.
As shown in Eqn. (3), the moment my in Adan consists of two terms, i.e. gradient term ge and gradient difference term (g. gi-1), which actually have different physic meanings. So here we decouple them for greater flexibility and also better trade-off between them. Specifically, we estimate
(0u+1 - -0x) >
1=0 [Ck,igr gi+
+ (1 (1- 12,)) -g--1) = m + -2)
(4)
(k-t) for t > O, G,r = (1 -3)²* for = 0, and my and vy are defined as where de, = 0., (1))
m& = (1 31 m + Big gk:
V& = (1 32) + 32 - gi-
This change for a flexible estimation does not impair convergence speed. As we show in Theorem 1, the complexity of Adan under this change matches the lower complexity bound. We do not separate the gradients and their difference in the second-order moment ng. since B((x)) contains the correlation term Cov(gA, 1k-1) * 0 which may have statistical significance.
Decay Weight by Proximation. As observed in AdamW, W, decoupling the optimization objective and simple-type regularization (e.g. & regularizer) can largely improve the generalization performance. Here we follow this idea but from a rigorous optimization perspective. Intuitively, at each iteration, we minimize the first-order approximation of F()) at the point 0s:
0k+1 = 0% 77k m argming F(O+) (m.: Ok) +
1 21
0x
where / = (x, ng E) o x) and m == m + (1 V2 is the first-order derivative of F()) in some sense. Follow the idea of proximal gradient descent (Parikh & Boyd, 2014; Zhuang et al., 2022), we decouple the Ez regularizer from F(.) and only linearize the loss function f()):
AR 2
1 e 0% (m, O Ox)) + 2n
O2 Tkk m
0 argmin
0
(5)
T2y
+ A
where Ag is the weight decay at the k-th iteration. One can find that the optimization objective of at the k-th iteration is changed from the vanilla "static" function F(.) in Eqn. (1) to a "dynamic" function Fx(.) (.) in Eqn. (6), which adaptively regularizes the coordinates with larger gradient more:
A 2
(x) = Eç-D (f(0.))
101 V
We summarize our Adan in Algorithm 1. We reset the momentum term properly by the restart condition, a common trick to stabilize optimization and benefit convergence (Li & Lin, 2022; Jin al., 2018). But to make Adan simple, in all experiments except Table 8, we do not use this restart strategy although it can improve performance as shown in Table 8.
4 CONVERGENCE ANALYSIS
For analysis, we make several mild assumptions used in many works, e.g. (Guo et al., 2021). Assumption (L-smoothness). The function f(---) L-smooth w.r.. the parameter, if > 0,
V [ <)] (x,(())))) s L|[x [|l, Vx, y.
Assumption 2 (Unbiased and bounded gradient oracle). The stochastic gradient oracle gk =
V (0,, {)] &x is unbiased, and its magnitude and variance are bounded with probability 1:
E (Ex) = O, |gg lac S /3, E ((11511)) E EE 5)] 1 -Bul1²) S0², vk E [T].
5

---

Under review as a conference paper at ICLR 2023
Algorithm 1: Adan (Adaptive Nesterov Momentum Algorithm)
Input: initialization Og, step size 7,, weight decay X 0, restart condition.
Output: some average of {0
while k K do compute the stochastic gradient estimator gk at 4x:
ma (1 81) )m
+B gi
set my go */;
Vi = (1 V2 :2(
gk-1)
/ set Vi = gi */;
ng =(1- - + (1 3g)(EH 8k-1))?;
0x+1 =1 Ax17
7 o (m + (1 (0-3-))va v2) with T7 = /n/l// (v + e):
restart condition holds then get stochastic gradient estimator go at 0k+1;
m. go+ end if VD 10=0,
ng So+ update 0, by Line 6, k ==
end while
Assumption (p-Lipschitz continuous Hessian). The function f(--.) has p-continuous Hessian:
|| Bxlf(x {)) 4 Bels(x. <)]ll S p||x yll, Vx, Y,
where ||-|] is the spectral norm for matrix and the Eg norm for vector.
For general nonconvex problem, if Assumptions 1 and 2 hold, the lower bound of the stochastic gradient complexity to find an e-approximate first-order stationary point (e-ASP) is f?(--1 (Arjevani al., 2019; 2020). Moreover, if Assumption 3 further holds, the lower complexity bound becomes Q(E 3.5) for non-vatiance-reddutioo algorithm (Arjevani et al., 2019; 2020).
Lipsehitz Gradient. Theorem with proof in Appendix proves the convergence of Adan on problem (6) with lipschitz gradient condition.
Theorem 1. Suppose Assumptions I and 2 hold. Let max [31,82] = O : V23 < 1, " (c2), and d >(1 - 11)* Algorithm I runs at most = ((c25 iterations to achieve
K k D ((IFF((00) < 4c2.
1
K K+1
That is, to find an e-ASP, the stochastic gradient complexity of Adan on problem (6) is O (c225
2.5 (2))))
Theorem shows that under Assumptions and 2, Adan can converge to an e-ASP of a nonconvex stochastic problem with stochastic gradient complexity 0 which accords with the lower bound (2(==)) in Arjevani et al. (2019). For this convergence, Adan has no requirement on minibatch size and only assumes gradient estimation to be unbiased and bounded. Moreover, Table in Sec. 1, the complexity of Adan is superior to those of previous adaptive gradient algorithms. For Adabelief and LAMB, Adan always has lower complexity and respectively enjoys d x and d2x lower complexity for the worst case. Adam-type optimizers (e.g. Adam and AMSGrad) enjoy the same complexity as Adan. But they cannot separate the le regularizer with the objective like Adam and our Adan. The regularizer separation can boost generalization performance (Touvron et al., 2021; Liu et al., 2021) and already helps Adam dominate training of ViT-alike architectures. Besides, some previous analyses (Luo et al., 2018: Zaheer et al., 2018: 8; Liu et al., 201 9a; Shi et al., 2020) need the momentum coefficient (i.e. (s) to close or increased to one, which contradicts with the practice that Is are close to zero. In contrast, Theorem assumes that all 3s are very small, which is more consistent with the practice. Note that when μ = c/T, we have >ę/A E [(1 c), during training. Hence could choose the A as a fixed constant in the experiment for convenience.
shown in
Lipschitz Hessian. With Assumption 3, we further need a restart condition. Consider an extension point 1 == Oc+1 7 [m, (1 B2) [gg]]. and restart condition:
(I: + 1) Ily+t1 yr yell -, R².
where the constant R controls the restart frequency. Intuitively, when the parameters have accumulated enough updates, the iterate may reach new local basin. Resetting the momentum at this moment helps Adan to better use the local geometric information. Besides, we change mh from / (Vnz + E) to / (n/(vnn (nna- + ) to ensure 7) to be independent of noise Çk. See its proof in Appendix F.

---

Under review as a conference paper at ICLR 2023
Table 2: Top-1 accuracy (%) of ResNet and ConvNext on ImageNet under their official settings.
and o are respectively reported in (Wightman et al., 2021; Liu et al., 2022b).
ResNet-50
ResNet-101
ConvNext Tiny
Epoch
100
200
300
100
200
300
Epoch
150
300
SAM
77.3
78.7
79.4
79.5
81.1
81.6
AdamW
81.2
82.1
SGD-M
77.0
78.6
79.3
79.3
81.0
81.4
Adan (ours)
81.7
82.4
Adam
76.9
78.4
78.8
78.4 4
80.2
80.6
ConvNext Small
AdamW
77.0
78.9
79.3
78.9
79.9
80.4
Epoch
150
300
LAMB
77.0
79.2
79.8*
79.4
81.1
81.3*
Adam W
82.2
83.19
Adan (ours)
78.1
79.7
80.2
79.9
81.6
81.8
Adan (ours)
82.5
83.3
Theorem 2. Suppose Assumpiions 1-3 hold. Let R O max (31, 32) - ((2), 33 - =
((2.5), k= (( >= Then Algorithm with restart condition Eqn.(7) satisfies:
(( = (c..ee.
Kg = argmin K SMEK-1 llye+1 - Yell Moreover, to find an c- ASP, Algorithu restarts most (c-2s times in which each restarting cycle has at most K- = 0((E-)) iterations, and hence needs at most O Oc2225 (c352) stochastic gradient complexity.
where == 1 EK Ok:
Ko Ek=1
From Theorem 2, one can observe that with extra smooth Hessian condition in Assumption 3 and a restart condition (7), Adan improves its vanilla stochastic gradient complexity from O O (=2ee to (cc1225--5.) which also matches the corresponding lower bound fi 3.5). This complexity 3.5 log @a) of A-NIGT and (3.65) of Adam For other DNN optimizers,
is lower than O -3553.5 e.g. Adam, their convergence under Lipschitz Hessian condition has not been proved yet.
Moreover, Theorem 2 still holds for the large batch size. For example, by using minibatch size b O(E -155 ). our results still hold when R = (c max (31, = O(e B3 = Occ). 7 0(1), K (c-55) and À = 0. In this case, our is of the order (1). and is much larger than (ploy(e)) of other optimizers (e.g., LAMB and Adam+) for handling large minibatch. This large step size often boosts convergence speed in practice, which is actually desired.
5 EXPERIMENTAL RESULTS
We evaluate Adan vision, NLP and RL tasks. For vision tasks, we test Adan on several representa- tive SoTA backbones under the supervised settings, including 1) CNN-type architectures (ResNets and ConvNexts (Liu et al., 2022b)) and 2) ViT's vanilla ViT's and Swins (Liu et al., 2021)). Moreover, we also investigate Adan via the self-supervised pretraining by using it to train MAE ViT (He et al., 2022). For NLP tasks, we train LSTM, Transformer-XL (Dai et al., 2019), and BERT (Devlin et al., 2018) for sequence modeling. On RL tasks, we evaluate Adan on four games in MuJoCo (Todorov et al., 2012). In all experiments, we only replace the optimizer with Adan and tune the step size, warmup epochs, and weight decay, etc, while fixing the cedimizerindependeen egg. data augmentation and model architectures. Moreover, to make Adan simple, in all experiments except Table 8, we do not use the restart strategy in Algorithm 1. Due to space limitation, we defer the RL results and the ablation study into Appendix B.3 and B.5, respectively.
byper-parametert
5.1 EXPERIMENTS FOR VISION TASKS
Besides the vanilla supervised training setting used in ResNets (He et al., 2016), further consider two prevalent training settings on ImageNet, namely the following Training Setting I and II.
Training Setting The recently proposed "A2 training recipe" in (Wightman et al., 2021) has lifted the performance limits of many SoTA CNN-type architectures by stronger data augmenta- tion. Specifically, for data augmentation, this setting uses random crop, horizontal flipping, Mixup (0. 1)CCtMiix (1.0) with probability 0.5, and RandAugment with M = N = 2 and MSTD = 0.5.
sets stochastic depth (0.05), and adopts cosine learning rate decay and binary cross-entropy loss.
Training Setting II. For this setting, data augmentation includes random crop, horizontal flipping, Mixup (0.8), CutMix (1.0), Rundnng (M 9, MSTD 0.5) and Random Erasing (p 0.25). It uses cross- cross-entropy loss, cosine decay, and stochastic depth. For both settings, please refer to their details, e.g. data augmentation, in Appendix Sec. A.I.
7

---

Under review as a conference paper at ICLR 2023
Table 3: Top-1 accuracy (%) of ViT and Swin on ImageNet. We use their official Training Setting II
to train them. and o are respectively reported in (Touvron et al., 2021; Liu et al., 2021).
ViT Small
VIT Base
Swin Tiny
Swin small
Swin Base
Epoch
150
300
150
300
150
300
150
300
150
300
AdamW
78.3
79.9"
79.5
81.8*
79.9
81.2
82.1
83.2
82.6
83,5
Adan (ours)
79.6
80.9
81.7
82.3
81.3
81.6
82.9
83.7
83.3
83.8
Results on CNN-type Architectures. To train ResNet and Con- vNext, respectively use their official Training Setting I and II. For SoTA ResNe//ConvNext, its default official optimizer is LAMB/AdamW. From Table 2, one can observe that on ResNet, 1) in most cases, Adan only running 200 epochs can achieve higher or comparable top-1 accuracy on ImageNet compared with the of- ficial SoTA result trained by LAMB with 300 epochs; 2) Adan gets more improvements over other optimizers, when training insuf- ficient, e.g. 100 epochs. The possible reason for observation 1) is the regularizer separation, which can dynamically adjust the weight decay for each coordinate instead of sharing a common one. For observation 2), this can be explained by the faster convergence speed of Adan than other optimizers. As shown in Figure 1, Adan con- verges faster than many adaptive gradient optimizers. This faster speed partially comes from its large learning rate guaranteed by The- orem 2, almost 3x larger than that of LAMB. The same as Nesterov acceleration, Adan could look ahead for possible corrections. More comparison on convergence speed and loss curve is in Appendix B.2. On ConvNext, one can observe similar comparison results on ResNets. Additional results in Appendix Sec. B.1 provide more comparison on ResNet-18 under the vanilla setting in (He et al., 2016).
Adantours)
Adamm
Trairiing Loss
Nadam
SAM
SGD-M
20 40
100
Training
Epochs on ResNet-SS
Adan(ours)
Adam
Taaniin Loss
AdammV
LAMB
SGD M
Training Epochs on
Figure 1: Training curves of various optimizers.
Results on ViTs. 1) Supervised Training. We train VIT and Swin under their official training setting, i.e. Training Setting Table 3 shows that across different model sizes of ViT and Swin, Adan outperforms the official Adam W optimizer by large margin. For ViTs, their gradient per iteration differs much from the previous one due to the much sharper loss landscape than CNNs (Chen et al., 2021b) and the strong random augmentations for training. So it is hard to train ViTs to converge within a few epochs. Thanks to its faster convergence, as shown in Figure 1, Adan is very suitable for this situation. Moreover, the direction correction term from the gradient difference Vı of Adan can also better correct the first- and second-order moments. One piece of evidence is that the first-order moment decay coefficient 31 0.02 of Adan is much smaller than 0.1 used in other deep optimizers.
2) Self-supervised MAE Training (pretraining + finetuning). We follow the MAE training framework to pretrain and fine-tune ViT-B for 300/800 pretraining epochs and 100 fine-tuming epochs, and ViT-L for 800 pretraining epochs and 50 finettuning epochs, on Im- ageNet. Table 4 shows that 1) on ViT-B, Adan makes 0.5% improvement over AdamW under 300 pretrain- ing epochs, and Adan pretrained 800 epochs surpasses AdamW pretrained 1,600 epochs by nontrivial 0.2%;
Table 4: Top-1 Acc. (%) of ViT-B and ViT-L trained by MAE under the official Training Setting II. and in (Chen et al., 2022; Hc ct al., 2022).
respectively reported
MAE-VIT-B
MAE
ViT-L 1600
Epoch
300
800
1600
800
AdamW
82.9*
83.6
85.4
85.9
Adan
83,4
83,8
85.9
2) on ViT-L, Adan only uses 800 pretraining epochs to achieve the same performance of AdamW with 1,600 pretraining epochs. All these results show superior performance of Adan.
3) Large-Batch Training. Though large batch size can increase parallelism to reduce training time and is heavily desired, optimizers often suffer performance degradation, even fail. For instance, AdamW fails to train ViT' when batch size is beyond 4,096. How to solve the problem remains open (He et al., 2021). At present, LAMB is the most effective optimizer for large batch size. Table 5 reveals that Adan is robust batch sizes from 2k to 32k, and shows higher performance and robustness than LAMB.
Table 5: Top-1 Acc. (%) of ViT-S on Ima- geNet under Training Setting
Batch Size
1k
2k
4k
8k
16k
32k
LAMB Adan
78.9
79.2
79.8
79.7
79.5
78.4
80.9
81.1
81.1
80.8
80.5
80.2
8

---

Under review as a conference paper at ICLR 2023
Table 6: Results (the higher, the better) of BERT-base model on the development set of GLUE. The first line is from (Wolf et al., 2020) while the second line is reproduced by us.
BERT-hase
MNI.I
QNLI
QQP
RTF
SST-2
CoLAA
STS-B
Average
Adam (official)
83. 8
89.3
90.8
71.4
91.7
48.9
91.3
81.5
Adam (reproduced)
84.9/84.9
90.8
90.9
69.3
92.6
58.5
88.7
82.5
Adan (ours)
85.7/85.6
91.3
91.2
73.3
93.2
64.6
89.3
84.3 (+1.8)
5.2 EXPERIMENTS FOR NATURAL LANGUAGE PROCESSING TASKS
Results on BERT. Similar to the pretraining experiments of MAE which is also a self-supervised learning framework on vision tasks, we utilize Adan to train BERT (Devlin et al., 2018) from scratch, which is one of the most widely used pretraining models/frameworks for NLP tasks. We employ the exact BERT training setting in the widely used codebase-Fairsee (Ott et al., 2019). See more training details in Appendix A.3.
From Table 6, one can see that in the most commonly used BERT training experiment, Adan reveals much better advantage over Adam. Specifically, in all GLUE tasks, on BERT-base model, Adan achieves higher performance than Adam, and makes 1.8 average improvements on all tasks. In addition, some tasks of Adan, BERT-base trained by Adan can outperform some large models. e.g., BERT-large which achieves 70.4% on RTE, 93.2% on SST-2 and 60.6 correlation on CoLA, and laNee-large which has 63.6 correlation on CoLA. See (Liu et al., 2019b) for more results.
Results on Transformer-XL. We evaluate Adan on Transformer-XL. (Dai et al., 2019) which is often used to model long sequences. We follow the exact official set- ting 2 to train Transformer-XL-bass on the WikiText- dataset that is the largest available word-level language modeling benchmark with long-term dependency. We only replace the default Adam optimizer of Transformer-Xe XL- base by our Adan, and do not make other changes for the hyper-parameter For Adan, we set 31 = 0.1, 32 0.1, and B3- 0.001, and choose learning rate 0.001. We test Adan and Adam with several training steps, including 50k, 100k, and 200k (official).
Table 7: Test PPL (the lower, the better) for Transformer-XI--baal model on the WikiText- dataset.
Training Steps
Transformer-X
50k
100k
200k
Adam
28.5
25.5
24.2
Adan (ours)
26.2
24.2
23.5
Table 7 shows that Transformer-XL-Ae
Adan surpasses its default Adam optimizer in terms of test PPL (the lower, the better) under all training steps. Surprisingly, Adan using 100k training steps achieve comparable results Adam with 200k training steps. All these results demonstrate the superiority of Adan over the default SoTA Adam optimizer in Transformer-XL.
Results on LSTM. In Appendix B.4, the results on LSTM shows the superiority of our Adan over several representative optimizers, egg. SGD, Adam and AdamW, on the Penn TreeBank dataset.
5.3 DISCUSSION ON RESTART STRATEGY
Here we investigate the performance Adan with and with- out restart strategy ViT and ConvNext under 300 train- ing epochs. From the results in Table 8, one can observe that the restart strategy slightly improves test performance of Adan on both ViT and ConvNext. However, to make Adan simple and avoid hyper-parameter tuning of the restart strategy (e.g., restart frequency), in all experiments except Table 8, we do not use this restart strategy.
Table 8: Top-1 Acc. (%) of ViT-S and ConvNext-T on ImageNet under Train- ing Setting II trained with 300 epochs.
VIT Small
ConvNext Tiny
Adan w/o restart
80.71
81.38
Adan w/ restart
80.87
81.62
6 CONCLUSION
In this paper, we propose a new deep optimizer, Adan. We reformulate the vanilla AGD a more efficient version and use it to estimate the first- and second-order moments in adaptive optimization algorithms. We prove that the complexity of Adan matches the lower bounds and is superior to those of other adaptive optimizers. Finally, extensive experimental results demonstrate that Adan consistently surpasses other optimizers on many popular backbones and frameworks, including ResNet, ConvNext, ViT, Swin, MAE-ViT, LSTM, Transformer-XL and BERT.
hhttps://gi thub. combb.com/kee / hombb..oo//mmmmyoottttraaaa

---

Under review as a conference paper at ICLR 2023
REFERENCES
O. Abdel-Hamid, A. Mohamed, H. Jiang, L. Deng, G. Penn, and D. Yu. Convolutional neural networks for speech recognition. IEEE Trans. on audio, speech, and language processing. 22(10): 3533-1545, 2014.
Yossi Arjevani, Yair Carmon, John Duchi. Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv: 1912.0235, 2019.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridharan. Second-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pp. 242-299, PMLR, 2020.
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 Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pp. 3267-3275, 202la.
Xiangning Chen, Cho-Jui Hsieh, and Boqing Gong. When vision transformers outperform resnets without pre-training strong data augmentations. arXiv preprint arXiv:2106.01548, 2021b.
Xiaokang Chen, Mingyu Ding, Xiaodi Wang, Ying Xin, Shentong Mo, Yunhao Wang, Shumin Han, Ping Luo, Gang Zeng, and Jingdong Wang. Context autoencoder for self-supervised representation learning. arXiv preprint arXiv:2202.03022 2022.
Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with a reduced search space. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 702-703, 2020.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International Conference on Machine Learning, pp. 2260-2268. PMLR, 2020.
Zihang Dai, Zhilin Yang, Yiming Yang. Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 2978-2988, 2019.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 040000 2018.
Timothy Dozat. Incorporating nesterov momentum into adam. 2016
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International conference on machine learning, pp. 1329-1338. PMLR, 2016.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal Machine Learning Research, 12(7), 2011.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. arXiv preprint arXiv:2010.01412, 2020.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms of the adam family. arXiv preprint 1xXiv:21/2.0345 2021.
M. Hardt and T. Ma. Identity matters deep learning. arXiv preprint weXiv:1611.000 2016.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, 2022.
10

---

Under review as a conference paper at ICLR 2023
Xiaoxin He, Fuzhao Xue, Xiaozhe Ren, and Yang You. Lcage-scale deep learning optimizations: A comprehensive survey. arXiv preprint arXiv:2111.0086, 2021.
Gao Huang. Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian Q Weinberger. Deep networks with stochastic depth. In European Conference Computer Vision, pp. 646-661, 2016.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pp. 1042-1085. PMLR, 2018.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprini OrXiv:1412.6900 2014.
Jungmin Kwon, Jeongseop Kim, Hyunseo Park, and In Kwon Choi. Asam: Adaptive sharpness-aware minimization for scale-invariant learning of deep neural networks. In International Conference on Machine Learning pp. 5905-5914. PMLR, 2021.
Huan Li and Zhouchen Lin. Restarted nonconvex accelerated gradient descent: No more polyloga- rithmic factor in the ((--T/a) complexity. arXiv preprint arXiv:2201.14111, 2022.
Z. Li and Y. Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems, 2017.
Zhouchen Lin, Huan Li, and Cong Fang. Accelerated optimization for machine learning. Springer, 2020.
Liyun Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. In International Conference on Learning Representations, 2019a.
Mingrui Liu, Wei Zhang, Francesco Orabona, and Tianbao Yang. Adam +: A stochastic method with adaptive variance reduction. arXiv preprini arXiv:2011.11983 2020.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: 1907. 1692, 2019b.
Yong Liu, Siqi Mai, Xiangning Chen, Cho-Jui Hsieh, and Yang You. Towards efficient and scalable sharpness- aware minimization. arXiv preprint arXiv:2203.02714. 2022a.
Ze Liu, Yutong Lin, Yue Cao. Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEFF/CVF International Conference on Computer Vision pp. 10012-10022, 2021.
Zhuang Liu, Hanzi Mao, Chao- Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie.
convnet for the 2020s. arXiv preprint arXiv:2201.03545 2022b.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- ence on Learning Representations, 2018.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. In International Conference on Learning Representations, 2018
Mary Ann Marcinkiewicz. Building large annotated corpus english: The penn treebank. Using Large Corpora, 273, 1994.
Zachary Nado, Justin M Gilmer, Christopher J Shallue, Rohan Anil, and George E Dahl. A large batch optimizer reality check: Traditional, generic optimizers suffice across batch sizes. arXiv preprint 102.::200..06356. 2021.
Yurii Nesterov. On approach to the construction of optimal methods of minimization of smooth convex functions. Ekonomika Mateaticheskie Metody, 24(3):509-517, 1988.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
11

---

Under review as a conference paper at ICLR 2023
Yurii E Nesterov. A method for solving the convex programming problem with convergence rate (1/k2). Dokl. akad. nauk Sssr, volume 269, pp. 543-547, 1983.
Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: A fast, extensible toolkit for sequence modeling. Proceedings of NAACL-HLT 2019: Demonstrations, 2019.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in optimization, 1(3):
127-239, 2014.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa- tional mathematics and mathematical physics, 4(5):1-17, 1964.
H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pp. 400-407, 1951.
Tara N Sainath, Brian Kingsbury, Abdel-rahman Mohamed, George E Dahl, George Saon, Hagen Soltau, Tomas Beran, Aleksandr Y Aravkin, and Bhuvana Ramabhadran. Improvements to deep convolutional neural networks for LVCSR. In 2013 IEEE workshop on automatic speech recognition and understanding, pp. 315-320. IEEE, 2013.
Jürgen Schmidhuber, Sepp Hochreiter, et al. Long short-term memory. Neural Comput, 98)) 1735-1780, 1997.
Naichen Shi, Dawei Li, Mingyi Hong, and Ruoyu Sun. Rmsprop converges with proper hyper- parameter. In International Conference on Learning Representations, 2020.
C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-9, 2015.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033 IEEE, 2012.
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. In International Conference on Machine Learning, pp. 10347-10357. PMLR, 2021.
Hugo Touvron, Matthieu Cord, and Hervé Jégou. Deit ii:: Revenge of the vit. arXiv preprint arXiv:2204.071118 18, 2022.
Jiayi Weng, Huayu Chen, Dong Yan, Kaichao You, Alexis Duburcq, Minghao Zhang, Hang Su, and Jun Zhu. Tianshou: A highly modularized deep reinforcement learning library. arXiv preprint
arXiv:2107.1417,, 2021.
Ross Wightman, Hugo Touvron, and Hervé Jégou. Resnet strikes back: An improved training procedure in timm. arXiv preprint 10Xi0:21 2021.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma. Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger. Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the-ar natural language Empirical Methods in Natural Language Pro- cessing: System Demonstrations, pp. 38 38-45, Online, October 2020, Association for Computational Linguistics. URL https:://// www. ac wweb. org/ ant 2020 emnlp-denee 6.
processing. In Proceedings of the 2020 Conference
Tete Xiao, Mannat Singh, Eric Mintun, Trevor Darrell, Piotr Dollár, and Ross Girshick. Early convolutions help transformers see better. Advances in Neural Information Processing Systems, 34: 30392-30400, 2021.
Bo Xie, Yingyu Liang, and Le Song. Diverse neural network learns true target functions. In Artificial Intelligence and Statistics, pp. 1216-1224, PMLR, 2017.
12

---

Under review as a conference paper at ICLR 2023
Zeke Xie, Xinrui Wang, Huishuai Zhang, Issei Sato, and Masashi Sugiyama. Adaptive inertia: Disentangling the effects of adaptive learning rate and momentum. International Conference on Machine Learning, pp. 24430-2222 244599. PMLR, 2022.
Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. arXiv 03888, 2017.
preprint
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. In International Conference on Learning Representations, 2019.
Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. In Proceedings of the IEEE International Conference on Computer Vision, pp. 6023-6032, 2019.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. Advances neural information processing systems, 31, 2018.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2018.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 13:15383-15391 2020.
Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvoreek, Xenophon Pa- pademetris, and James Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. Advances in Neural Information Processing Systems, 33:18795-18806, 2020.
Zhenxun Zhuang, Mingrui Liu, Ashok Cutkosky, and Francesco Orabona. Understanding adamw through proximal methods and freenese arXiv preprint arXiv:2202.00089, 2022.
13

---

Under review as a conference paper at ICLR 2023
APPENDIX
The appendix contains some additional experimental results and the technical proofs of convergence results of the paper entitled "Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models". It is structured follows. Sec. A provides details of the training setting and Adan's implementation. also gives detailed steps to perform the experiment on BERT. Sec. B include the additional experimental results, which contains the results on ResNet- 18 in Sec. B.1, convergence curve in Sec. B.2, experiments on RI. tasks in Sec. B.3, results on LSTM in Sec. B.4, and the ablation study in Sec. B.5.
After Sec. C, which summarizes the notations throughout this document, we provide the technical proof's of convergence results. Then Sec. provides the proof of the equivalence between AGD and reformulated AGD, i.e., the proof of Lemma 1. And then, given Lipschitz gradient condition, Sec. E provides the convergence analysis in Theorem 1. Next, we show Adan's 's faster convergence speed with Lipschitz Hessian condition in Sec. F, by first reformulating our Algorithm I and introducing some auxiliary bounds. Finally, we present some auxiliary lemmas Sec. G.
A TRAINING SETTING AND IMPLEMENTATION DETAILS
A.1 TRAINING SETTING
Training Setting I. The recently proposed "A2 training recipe" in (Wightman et al., 2021) has pushed the performance limits of many SoTA CNN-type architectures by using stronger data augmentation and more training iterations. For example, on ResNet50. it sets new SoTA 80.4%, and improves the accuracy 76.1% under vanilla setting in (He et al., 2016). Specifically, for data augmentation. this setting uses random crop, horizontal flipping, Mixup (0.1) (Zhang ct al., 2018)/011/// //Ct/Mu (1.0) (Yun et al., 2019) with probability 0.5, and RandAugment (Cubuk et al., 2020) with M = 7, N = 2 and MSTD 0.5. It sets stochastic depth (0.05) (Huang al., 2016), and adopts cosine learning rate decay and binary cross-entropy (BCE) loss. For Adan, we use batch size 2048 for ResNet and ViT.
Training Setting II. We follow the same official training procedure of ViT/Swin/ConwNext. For this setting, data augmentation includes random crop, horizontal flipping, Mixup (0.8), CutMix (1.0), RandAugment (M 9, MSTD 0.5) and Random Erasing (p 0.25). We use CE loss, the cosine decay for base learning rate, the stochastic depth (with official parameters), and weight decay. For Adan, we set batch size 2048 for Swin/ViT/ConvNees and 4096 for MAE We follow MAE and tune B3 as 0.1.
A.2 IMPLEMENTATION DETAILS OF ADAN
For the large-batch training experiment, we use the sqrt rule scale the learning rate:
6.25e-3, and respectively set warmup epochs {20, 40, 60, 100, 160, 200} for batch size bs = {1k, 2k, 4k, 8k, 16k, 32k).. For other remaining experiments, we use the hyper-parameters. learning rate 1.5e-2 for ViTSSwnnnesNN//ConWNNY and MAE fine-tuning, and 2.0e-3 for MAE pre-training according to the official settings. We set 31 0.02, 32 0.08 and B3 0.01. and let weight decay be 0.02 unless noted otherwise. We clip the global gradient norm to for ResNet training and do not clip the gradient for ViT, Swin, ConvNext, and MAE. In the implementation, to keep consistent with Adam-type optimizers, we utilize the de-bias strategy for Adan.
hatch size
256
A.3 DETAILED STEPS FOR BERT
We replace the default Adam optimizer in BERT with our Adan for both pretraining and fune-tuning. Specifically, we first pretrain BERT-base on the Bookcorpus and Wikipedia datasets, and then finetune BERT-base separately for each GLUE task on the corresponding training data. Note, GLUE is collection of 9 tasks/datasets to evaluate natural language understanding systems, in which the tasks organized as either single-sentence classification or sentence- -air classification.
Here we simply replace the Adam optimizer in BERT with our Adan and do not make other changes, e.g. random seed, warmup steps and learning rate decay strategy, dropout probability, etc. For
14

---

Under review as a conference paper at ICLR 2023
Table 9: Top-1 accuracy (%) of ResNet18 under the official setting in (He et al., 2016). are reported in (Zhuang et al., 2020).
Adan
SGD
Nadam
AdaBound
Adam
Radam
Padam
L.MMB
AdamW
AdaBlief
Adai
70.60
70.23*
68.82
68.13"
63.79*
67.62*
70.07
68.46
67.93"
70.08
69.68
Table 10: Top-1 accuracy (%) of different optimizers when training ViT-S on ImageNet trained under training setting II. is reported (Touvron al., 2021).
Epoch
100
150
200
300
AdamW (default)
76.1
78.9
79.2
79.9*
Adam
62.0
64.0
64.5
66.7
Adai
66.4
72.6
75.3
77.4
SGD-M (AGD)
64.3
68.7
71.4
73.9
LAMB
69.4
77.7
Adan (ours)
77.5
79.6
80.0
80.9
pretraining, we use Adan with its default weight decay (0.02) and Bs (31 = 0.02, 33 = 0.08, and 83 0.01), and choose learning rate 0.001. For fine-tuning, we consider limited hyper-parameter sweep for each task, with a batch size of 16, and learning rates E f2c 5, 4e - 5) and use Adan with 31 0.02, 82 = 0.01, and B3 = 0.01 and weight decay 0.01. Following the conventional setting, we run each fine-tuning experiment three times and report the median performance in Table 6.
Same as the official setting, on MNLI, we report the mismatched and matched accuracy. And report Matthew's 's Correlation and Person Correlation on the task of CoLA and STS-B, respectively. The performance on the other tasks measured by classification accuracy.
The performance of our reproduced one (second row) is slightly better than the vanilla results of BERT reported in Huggingface-transfon NLP), since the vanilla Bookcorpus data in (Wolf et al., 2020) is not available and thus we train on the latest Bookcorpus data version.
(Wolf et al., 2020) (widely used codebase for transformers in
B ADDITIONAL EXPERIMENTAL RESULTS
B. RESUTLS ON R8SNET-18
Since some well-known deep optimizers also ResNet-18 for 90 epochs under the official vanilla training setting in (He et al., 2016), we also run Adan 90 epochs under this setting for more comparison. Table 9 shows that Adan consistently outperforms SGD and compared adaptive optimizers. Note for this setting. it is not easy for adaptive optimizers to surpass SGD due to the absence of heavy-tailed noise, which the crucial factor helping adaptive optimizers beat AGD (Zhang al., 2020).
B.2 DETAILED COMPARISON AND CONVERGENCE CURVE
Besides AdamW, we also compare Adan with several other popular optimizers, including Adam, SGD-M, and LAMB, on ViT-S. Table 10 shows that SGD, Adam, and LAMB perform poorly on ViT-S, which is also observed in the works (Xiao al., 2021; Nado al., 2021). These results demonstrate that the decoupled weight decay in Adan and AdamW is much more effective than 1) the vanilla weight decay, namely the commonly used l regularization in SGD, and the one without any weight decay, since as shown in Eqn. (6), the decoupled weight decay is dynamic regularization along the training trajectory and could better regularize the loss. Compared with A,amW, the advantages of Adan mainly come from its faster convergence shown in Figure 2 (b). We will discuss this below.
In Figure 2 (a), we plot the curve of training and test loss along with the training epochs ResNet50. One can observe that Adan converges faster than the compared baselines and enjoys the smallest training and test losses. This demonstrates its fast convergence property and good generalization ability. To sufficiently investigate the fast convergence of Adan, we further plot the curve training and test loss the ViT-Small in Figure 2 (b). From the results,
that Adan consistently
15

---

Under review as a conference paper at ICLR 2023
ResNet50
ResNet50
Aduns)
Adun(ours)
6
AdamW
AdamW
Training Loss
LAMB
LAMB
Test Loss
Nadam
Nadam
4
SAM
SAM
SGD-M
3
SGD-M
1
20
40
60
80
100
20
40
60
100
Epochs
Epochs
(a) Training and test curves ResNet-50 under Training Setting I.
VIT-S
VIT-S
Adan(ours)
Adan(ours)
Adam
Adam
Training Loss
AdamW
Test Loss
5
AdamW
LAMB
LAMB
SGD-M
4-
SGD-M
3
0
20
40
60
80
100
20
40
60
80
100
Epochs
Epochs
(b) Training and test curves on ViT-S under Training Setting II.
Figure 2: Training and test curves of various optimizers on ImageNet dataset. Training loss is larger due to its stronger data argumentation.
shows faster convergence behaviors than other baselines terms of both training loss and test loss. This also partly explains the good performance of Adan over other optimizers.
Discussion about convergence complexity Under the corresponding assumptions, most compared optimizers already achieve the optimal complexity in terms of the dependence on optimization c, and their complexities only differ from their constant factors, e.g. Coe and d. For instance, with Lipsehitz gradient but without Lipschitz Hessian, most optimizers have complexity ( (+)) which
matches the lower bound ((2) in Arjevani et al. (2019), where the constant factor x varies from different optimizers, e.g.z = e dl in Adam-type optimizer, : = e in Adabelief, x = cgd in LAMB, and 620 in Adan. So under the same conditions, cannot improve the complexity dependence on e but can improve the constant factors, which are significant, especially for the network.
Actually, we empirically find Coo (8.2),, C2 O430)), d 2.2 107 in the ViT-small across different optimizers, c.g., AdamW. W. Adam, Adan, LAMB. In the extreme case, under the widely used Lipschitz gradient assumption, the complexity bound of Adan is 7.6 x 10 smaller than the one of Adam, 3.3 x 10 smaller than the one of AdaBlief, 2.1 x 10 smaller than the one of LAMB, etc. For ResNet50, we also observe C.. = 0(78), = (970)) 2.5 107 which also means large big improvement of Adan over other optimizers
B.3 RESULTS ON REINFORCEMENT LEARNING TASKS
Here we evaluate Adan on reinforcement learning tasks. Specifically, we replace the default Adam optimizer in PPO (Duan et al., 2016) which one the most popular policy gradient method, and do not many any other change in PPO. For brevity, call this new PPO version "PPO-Adan". Then we test PPO and PPO-Adan on several games which are actually continuous control environments simulated by the standard and widely-used engine, MuJoCo (Todorov al., 2012). For these test games, their agents receive a reward at each step. Following standard evaluation, we run each game under 10 different and independent random seeds (i.e. 10), and test the performance
16

---

Under review as a conference paper at ICLR 2023
Ant
HalfCheetah
6000
10000
5000
8000
Episode Reward
Episode Reward
4000
6000
3000
4000
2000
2000
1000
ppo
ppo
ppo adan
ppo
adan
1
M
M
M
6 M
2
M Timesteps
4
M
6
Timesteps
Humanoid
Walker2d
5000
ppo
5000
adan
Episode Reward
4000
Episode Reward
4000
3000
3000
2000
2000
1000
1000
ppo ppo_adan
0
2M
6
Timesteps
Timesteps
Figure 3: Comparison of PPO and our PPO-Adan on several RL games simulated by MuloCo. Here PPO-Adan simply replaces the Adam optimizer in PPO with our Adan and does not change others.
Table 11:
Test perplexity (the lower, the better) on Penn Treebank for one-, two- and three-layered LSTMs. All results except Adan and Padam in the table are reported by AdaBelief.
LSTM
Adan
AdaBelief
SGD
AdaBound
Adam
AdamW
Padam
RAdam
Yogi
layer
83.6
84.2
85.0
84.3
85,9
84.7
84.2
86.5
86.5
2 layers
65.2
66.3
67.4
67.5
67.3
72.8
67.2
72.3
71.3
layers
59.8
61.2
63.7
63.6
64.3
69.9
63.2
70.0
67.5
for 10 episodes every 30,000 steps. All these experiments based the widely used codebase Tianshou (Weng et al., 2021). For fairness, we use the default hyper-parameters in Tianshou, egg. batch size, discount, and GAE parameter. We use Adan with its default As (8, 0.02, B2 0.08, and A3 = 0.01). Following the default setting, we do not adopt the weight decay and choose the learning rate as 3c-4.
We report the results on four test games in Figure 3, in which the solid line denotes the averaged episodes rewards in the evaluation and the shaded region is its 75% confidence intervals. From Figure 3, one can observe that on the four test games, PPO-Adan achieves much higher rewards than vanilla PPO which uses Adam as its optimizer. These results demonstrate the advantages of Adan over Adam, since PPO-Adan simply replaces the Adam optimizer in PPO with our Adan and does not make other changes.
B.4 RESULTS ON LSTM
To begin with, we test our Adan on LSTM (Schmidhuber al., 1997) by using the Penn TreeBank dataset (Marcinkiewicz, 1994), and report the perplexity (the lower, the better) on the test set in
https:://ii htt.ttttttbcccoommmtoooioo Itannssooo
anshou
17

---

Under review as a conference paper at ICLR 2023
1.0 - B1
1.0
1.0
0.98
0.97
0.95
0.98
0.94
0.92
0.98
0.97
0.95
0.96
83.68
83.52
83.45
0.96
83.65
83.67
83.68
0.98
83.69
83.64
83.57
83.7
0.94
83.70
83.58
83.50
1.0
0.94
83.73
83.72
83.70
1.0
0.94
83.59
83.54
83.51
83.6
83.5
0.90
83.75
83.72
83.60
0.90
83.69
83.59
83.75
0.92
83.75
83.72
83.60
1.0 B3 0.92
1.0 - B1
0.98
1.0 B3 0.9
83.4
Figure 4: Effects of momentum coefficients (31,82, (3) to top-1 accuracy (%) of Adan on ViT-B under MAE training framework (800 pretraining and 100 fine-tuning epochs on ImageNet).
Table 12: Top-1 accuracy (%) of ViT-S on ImageNet trained under Training Setting and II. is reported in (Touvron et al., 2021).
Training epochs
Training Setting
Training Setting II AdamW
AdamW
Adan
Adan
150
76.4
80.2
78.3
79.6
300
77.9
81.1
79.9
80.7
Table 11. We follow the exact experimental setting in Adablief (Zhuang et al., 2020). Indeed, all our implementations are also based on the code provided by Adablief (Zhuang et al., 2020)*. We use the default setting for all the syper-parametern provided by Adablief, since it provides more baselines for a fair comparison. For Adan, we utilize its default weight decay (0.02) and [3s (3 = 0.02, B2 = 0.08, and B3 0.01). We choose the learning rate 0.01 for Adan.
Table 11 shows that on the three LSTM models, Adan always achieves the lowest perplexity, making about 1.0 overall average perplexity improvement the runner-up. Moreover, when the LSTM depth increases, the advantage of Adan becomes more remarkable.
B.5 ABLATION STUDY
B.5.1 ROBUSTNESS TO IN MOMENTUM COEFFICIENTS
Here choose MAE to investigate the effects of the momentum coefficients (8s) to Adan, since as shown MAE, its pre-training is actually sensitive to momentum coefficients of AdamW. To this end, following MAE, we pretrain and fine tune ViT-B ImageNet for 800 pretraining and 100 fine-tuning epochs. We also fix one of (B1, B2, 33) and tune others. Figure 4 shows that by only pretraining 800 cases and outperforms the official accuracy 83. 83.6% obtained by AdamW with 1600 pretraining epochs, indicating the robustness of Adan to As. We also observe Adan is not sensitive to 32; 2) 31 has a certain impact on Adan, namely the smaller the (1.0 81). the worse the accuracy; 3) similar to findings of MAE, small second-orde coefficient (1.0 Bg) can improve the accuracy. The smaller the (1.0 - Ag), the more current landscape information the learning rate. Maybe the complex pre-training
epochs, Adan achieves 83. 73.7% + in
optimizer would utilize to adjust the coordinate-wu task of MAE is more preferred to the local geometric information.
B.5.2 ROBUSTNESS TO TRAINING SETTINGS
In convention, many works (Liu et al., 2021; 2022b; Touvron et al., 2022; Wightman et al., 2021; Touvron et al., 2021) often preferably chose LAMB/Adam/SS
for Training Setting I and AdamW for Training Setting II. Table 12 investigates Adan under both settings and shows consistent improvement also observe that Adan under Setting largely improves the accuracy of Adan under Setting II. It actually surpasses the best-known accuracy 80.4% on ViT-small in (Touvron al., 2022) trained by advanced layer scale strategy and stronger data augmentation.
of Adan. Moreover,
'htpp:: : //gittubb com/ junt ang- zhuang/ Adabe -wteeleeff-piiiiee Soff--ptmiizzz The reported results in (Zhuang et al., 2020) slightly differ from the those in (Chen et al., 2021a) because of their different settings for I. LTM and training hyper-parameters.
18

---

Under review as a conference paper at ICLR 2023
C NOTATION
We provide some notation that are frequently used throughout the paper. The scale is in normal font. And the vector is in bold lowercase. Give two vectors x and y, x 2 y means that (x - y) is non-negative vector. x/y or represents the element-wise vector division. x x y means the element-wise multiplication, and (x)² xxxx (.-)) is the inner product. Given non-negative vector 2 0, we let ||x| (x, vn + ex)). Unless otherwise specified, ||x|] is the vector &2 norm. Note that Exx) is the expectation of random random vector X.
D PROOF OF LEMMA I: EQUIVALENCE BETWEEN THE AGD AND AGD II
In this section, we show how to get AGD II from AGD. For convenience, we omit the noise term Sk- Note that, let a 1 31:
g: = ff 70mm;11)
AGD:
m am + 8k
0c+1 = 0₂ 17m3
We can get:
0t+1 gamN = 0₂ 17m - 1jam;
= 02 71 a) (o V (0, nomm=-1)
(8)
nam - n 2 17(1 + aa) -nmm--))
Let
0x+1 = 0x+1 - rjam,
mi == a² m + (1 + aa) - (jamm-)) mm +
Then, by (8), we have:
0,+1 0N - --mmg-
(9)
On the other hand, we have m = a m
and
m ama-a
a² - -m
(1 + [1+aa\//(+)+ (S( ami-1
= (1 + (0 -m
(10)
(1 (1+=) + aV ((,((( amp-1
+ (V vf(0x=1))
Finally, due (9) and 10. we have:
m. am + (V](O.) -V
0++1 02 mpi
E CONVERGENCE ANALYSIS WITH LIPSCHITZ GRADIENT
Before starting the proof, we first provide several notations. Let (x) Eclf(0, A 1011 and μ /29gcx/e.
|x| ynu (x, (VD +x) d = X(1 11)
Moreover, let
0 := :=
Or.
19

---

Under review as a conference paper at ICLR 2023
Lemma 2. Assume f(-) is L-smooth. For
A |0 vnv + f(0x) + (uz. -0x) +
1
0x+1 = argmin
1(0
0x)1 0x)1
0
2
21
1 With r) S min 31 TOX then we have:
un + SaOxll 1|(
17 us 11
FK+1 F(((s)
+
gg:
40
25
where gk = v)(()))
Proof. We denote Pk = un/( us/(VDn + EE). By the optimality condition of 0 we have
b, +
1 17 (0s- 02+1))
ds + P
(11)
Vn + "
Then for 17 S e 31. we have:
L
As+1
FR+1(0 - f(0x) (Vf(O)), 0k)
+
10 -Oxl1++
100+111 me+t
2
(4)
(f(0)) + (Vf(()). 0x+1 - 02) + -
L
10 - 02 +
Ak 10 1l
2
2
(
(OW( + (0 ON ApOx
Bk
L/e + dv
0x+1 Osill
Vnx +
/nc
=F((0k) + L/E+ AU: 100++1
Oall
(Out1
ORr Ag
Pk
8k Ug
/ +
/mz
12 (Ok) +
L/E+>/ dv
1 1+nde
|0
-Oxl1 VTTE +
8k Up
2
/nk E
(6)
(OW(O)) +
L/EE
1
|10x+1
-Oal1
+ 21
10k+1 - 00ll
+
17
|g: un
2
2s
1
(0.)
|0,+1 0x
0x112 /mn
2e llgk 1x
3r)
(O.(
"
Ub + 0x 1|²
+
1) |gg un 1?
4c
25
where (a) comes from the fact 1
p1) -1 d and Proposition 3:
/ iik +
2 21-H u.
/na+1 +
which implics:
A4+1 11 16
Act1
0++1 1/m >u 1mm
1 1
and (b) from:
10 11 yT
(10All + +(x0x+1 02.0k) .nn + +110 - -2x11 (
(c) is due Eqn. (11), and for (d), utilize:
Ou+1 Ok:
gi u
00+11
1 f/m + 2e
|gg u+l
21
VTg
the last inequality comes from the fact in Eqn. (11) and 1 S Tox such that:
1
(0
0w) 3(vnk + e) (1 + n)x))
"
uk uaōall
17 us Nr0a
3n
4000
20

---

Under review as a conference paper at ICLR 2023
Theorem 1. Suppose Assumptions 1 and 2 hold. Let cj == 1
and cu == : With Bycoe < 1,
Coo
1² s 9
Qr
242o 24c, mnaTe 32cqe2
max (31, B23 x H6
T max
8c 1.2
where Do = F(oo) - f and f = ming Eş V f(Oks () then we let un == my + (1 - $1) and
have:
T
uu + Anbal
sc:
T +
k=
and
1
T
E
m
g
fullll s
S
62
Σ
B (Ivz1
- 2
T+1
1
4
T
A=0
k=0
Hence, we have:
T
E
0z
Ak
2
| Vas
+
Ee
Vf <11 <1))l")
S 462.
k=
Proof. For convince, we let u2
== m + (1 - B1 v and gi: full F f(x. <)] We have:
full
fult
2(1 - 21)- v
g
m g
By Lemma 2, Lemma 5, and Lemma 6, we already have:
F < (0x)
17c
4 us + OxOal|" ||
+ mcu
8k
full
mm
+ nca (1 B11 111
(12)
2.? I.2
[Ixx+I-//91) -
-B $/ s (1 - 31) |ms g%
E (110k+1 - 0ull²)
+ 3300
B1
(13)
B (1Iv=+1l)) (1- 322 (Ivxll²) + 2,32B
| B6+1 gk
+ +3,3002
(14)
Then by adding (12) with seu (13) and nca(1-A11
x (14), we can get:
Ag
B(Px+1) SE
E
Φx 77
us 1x02 _|
1/Gu
(1-
11)
11 0c +e(o²
))
B1
Br
+ nCu(1 (1 - 31)²
E
23 12 - -0x11 + 33802)
82
(1 (1-31)²
<
uk + +N
+
+ 2(1 - -817 |10 - 0ull
4
B7
+
(8) + 3,2)m,,000
18
1 nc
11 + 'Aa0al"
+ ncuL2
11 - -Oal2)
+ 48m
4
BJ
(6)
(1)c)) 322
ne
| + 0x 12) + 4.8mmcyo
E
4 +
87
4
1/1
<
uk
where we let:
1/c, -312
$ = Fx(O2) - f" + 7/C,
m
g
full
+
|
31
B2
c,3
8m max (81, 12} <
S
3'
8c 1
21

---

Under review as a conference paper at ICLR 2023
and for (a), when 81 $ 2/ have:
(1 - B1)
1
+ 2(1 -,1²² <
87
37
and (b) is due to (11( from Lemma 2. And hence, we have:
B( S
B(
7
1e 1| +T +nn+))mmemnm0
ug
8
k=
k=
Hence, we can get:
uu + An0al()
8dp
32
8Au
8c,
32cusmo² S
TE
T+1
naT
net
BIGT
k=0
where
240o
24c,02 BiqtE S
Ao = F(Oo) f",
Bm S
T 2 max
06c
nae?
We finish the first part of the theorem. From Eq. (13), we can conclude that:
full
11)
0²
? 0I0²
E
m
8k
+
3T
3
R=
From E14() can conclude that:
s 22121 + +3320² 2
E (1v=2l)
T
k=0
Finally have:
Ak 11012 2m + +EcI((0x.(])) <]]
E
T
T
E
2|
uu
+ do 1| + 44|1m a||m=
g full 2 + +l]vall²)
))
s 462.
T+1
Now, we have finished the proof.
22

---

Under review as a conference paper at ICLR 2023
F FASTER CONVERGENCE WITH LIPSCHITZ HESSIAN
For convince, let - and A3 3 in the following proof. To consider the weight decay term in the proof, we refer to the previous section for more details. For the ease of notation, we denote x instead of 0 the variable needed to be optimized in the proof, and abbreviate Ecl [)] as f(0x).
F.1 REFORMULATION
Algorithm 2: Nesterov Adaptive Momentum Estimation Reformulation
Input: initial point og stepsize !/, average coefficients 8, and E. begin
while A < K do
get stochastic gradient estimator gk at X
m = (1 - 3 m + B(g+ + (1 - 8)(8k Bk-1));
ng (1 322 n - (g (1 ()k--1 gk-
7e = n/(VI + +)):
Vk+1 Xx: Bg:
X = Yk+1 + 3)) - yv) + (7 (m 1-g-181111
(k: +1> (voz + +) 1/2 (y++1 - -y))
2 R² then
get stochastic gradient estimator go at X
11
m. = go ny = go.
X = Yo = X++1, X1 y1 = X, 17 -nott 1;
end if end while
13
Ku argmin SkSK-1 ( (VTn + =) (yx+1 -w>)
15 end
Output: = Kg Eke X
We first prove the equivalent form between Algorithm and Algorithm The main iteration in Algorithm is:
my (1 - --)m -1 + Bgk.
V: = (1 - 3)v1-1 + 3((g: - g)-1)),
X6+1 Xx: 7h (mg + (1 - B)vk).
Let m == (mæ + (1 - v)),,, we can simplify the variable:
m (1 8)mm-)mm B(g + +11 () gg gg-1)),
xt+1 = Xx o m..
We let yk+1 = Xx+1 + m7 (mi (.gt), then we can get:
yk+1 Xk+1 + m.mk .m.ge Xx+1 + X X6+1 -8mgg Xx -Bnggk-
On one hand, we have:
X Xx
m Yk+1 nh mm -8gx)-
23

---

Under review as a conference paper at ICLR 2023
On the other hand:
mp [m (gg) (1 (m + 3(gs gk-1))
= (1 3) (m+=11 - B(gk Bk-1))
Xk-1 Xk
= (1 B)m
+ 3(g Bk-1)
7)-11
=(1
()
(xk-1 - Xx + +, 11 (8k Bk-1))
7k-1
77
=(1 B)
(yk Xk + 317k
7
The (yk Yk+1 3mm 7 )Bh)
=(1 8)
7K-
(ys - Yk+1) + 7/k M]--1
=(1- B)
(yk: -Yk+1 - (migg))
77-1
(y:: - -v++1) + 7k 77
(Yx: xx)
= -(1- 8)
7h
-(1 lyy yk+1) + (7 7
7k--1 (m
(3gh-1)].
Hence, can conclude that:
X Yk+1 + (1 11-3)](x++1111 yk) + (M7-1 mm) 1))-
The main iteration in Algorithm becomes:
yk+1 = X2 -877BK
X6+1 = YK+1 (1 3) (y++) yk) -x)+
7 77 (yx - xx)
(15)
Mh-1
F.2 AUXILIARY BOUNDS
first show some interesting property. Define to be the iteration number when the 'if condition triggers, that is,
k k-1
(vD: + E)1/2 o (ve+1 -ye11-vol"" soll" R& s
K= min
Proposition 1. Given hs S K. and B S (V2coo + t), we have:
|[/mn + =22 o (x+ yk) s S.R R.
Proof.
First of all, we let nt = (VI + +z) 1/2 Due to Proposition 3, we have:
m E V + )
2282
1+ V282c00 Coo
8
then, get:
-1/2
ng 5 1- V2380x cx0
n S (1 -3) 1/4 -1
where we use the fact B s e2/2/cc0 + E). For any 1 S k < K,, we have:
| (ys - yk-1)) S (1 (3) 1/2 -1/2 P (yx - 1111
k-1
R²
<(1 3)
|| o (ye+1 - y.)ll < k:1 - 3)
24

---

Under review as a conference paper at ICLR 2023
hence, conclude that:
R82
| o (Ya -yx-1))
(16)
k(1 - B)
On the other hand, by Eq.(1 have:
Yk+1 (1 (1- 31 (Fe+1 - -va) + 77 - 77--1 (xs -16
X
17--1
and hence,
lig (xx= yu)ll S (1- 33 (1-3))
llāe
(yx= yyk-1))
7
7
| (XX-1
yK-1)ll
1):-2
+ (1 - 3) c20 (1 1 C202c00
-1/2
(a)
R
V1
3
[ (xS-1 yk-1)ll
V
R
< V B
+ 3(1 - 3/ o (X - yk-1))l
Vi
B(1 -3)3111
+... (S(1 - -3)2//) k-1
$ V1 1 BR
Vk
Vk -1
1/4
3/4
k
(8(1-3) 3)8/2) 10/3)
3R
Σ
R,
12
where (a) comes from (16 and the proposition 3, (b) the application of Hölder's 's inequality and (c) comes from the facts when 3 S 1/2:
n²
k
(311- 3)2/2) 41/3
3/4
(1- (1-3)2/3
3/4
VI- 3
Σ
<
6
1 B4/3 (3)
F.3 DECREASE OF ONE RESTART CYCLE
Lemma 3. Suppose that Assumptions 1-2 hold. Let R 0(.5),, == =0(2), = O(2.5).
K. K =((-2)) Then we have:
Eff(yk) - f(xo)) ((26)).
(17)
Proof. Recall (15) and denote gk
full = (0x))) for convenience:
full + Ex)
YR+1 Xx -Bn
gk
(18)
Xk+1 -R+1 (1 (yk+1
ykk + 17 M/=1
17s-1 (xx= ve))]
In this proof, we let iu == (ViT + E) 1/2 and hence Th n//nß. By the L-smoothness condition. for S k K., we have:
I. B (f(y++11) f(xx)) SE (Bt. -xa) " "lYaAt xxxl1
yk+1 Ek,
+ $11xkt1 - xxll?
xx
AT
+ |ly++1 -xal1²) + n3o2
L
E
[ig o (yk+1 x+)11²
(19)
mB
2
1
| o (yk+1 xxx)12 + L
ji o (yx+1 - -xx))()
1902
E
n/3
2.
+ n780
n (yb+1 - -x+)1p)
E
2m
25

---

Under review as a conference paper at ICLR 2023
where (a) comes from the facts:
E ((EK. Yk+1 - xx)) = ((ER, X3= - -mm o (gi: + Ex))) = E ((E,, Omp o Ex)) S 11302
and the last inequality is due to Laj S 8. On the other hand, we have:
B(f(x*) ( f(yn) - B (Vf(y)), ya) + I.
2 |xxx - yyll?
(k yx) + (V)x)) fx(x)) y&c) + I. l1xe yull?
=E
8g Xk yb) + Vf(yx)= vf(x)]] + - -1xxe sull? + L ||xxs yull))
1
2L
8k Xx yt)) +
3L.
2 | ykll?)
yk+1 Xx
+ Xx yK
+
3L
| -xkll?
BTK
2
3I.
(n (yk+1
xx),yx yk xx)
||x; yxll²)
113
(n)
< E
[i o (YE+) - xx)11 + || 0 (yx xx))1
-lis o (yR+1 - -x))l()
+ 22 1|xs - yxll?
3L
2m/3
(6)
1 ++ 8/2
S.
E
| o (yk+1 - xx,)1 و - (yu+1 - -w))l²)
+ 2n/3
| o - (yx-xx)1²
2n/3
(20)
where (a) comes from the following facts, and in (b), we use 3Lm $ :.-
2 (nk (yx+1 x4), yv xs) = عاا (yk+1 -xx+1=x)]1++++ +1 (yx x+>11- -1m (yk+1 yu)ll?
By combing (19) and (2.( we have:
| o (yx+ -xx)1² + E ( - 1 E 2mB [ o (yx+1 - -1+)11++ + 1/2
17302
2n/33
(a)
1
lig (y++1- y=) + 1- 1-1/2- - 3 | (yx yx-1))
122 8oc
nn0²
< E
221B
2n133
where (a) comes from the following fact, and note that by Proposition we already have ns 5
(1- - 9) 1144 n
[ng (Xt= - yx)l1²
<(1 - 8)²
(1 + +a)lin a (y& - y1-1)1 + (1 + 1 ) | o 1 1211 -
5(1 - 3/2
- (1+a)lia--108 (ye-- yx- + (1 1 3 (xu-1 -
(21)
31 1 (11////32
<(1 - 8) (yx y
o - 211
1- (1 3/1/2
<(1 - 1 o (yx - -y--))1² + 2
[ 1 (XL-1 - Y
<(1 - 1) (yx- -y--1)1 4,33 3 R2 2
where we let 3 = 22 e, a (1 - -1/2 1, and the last inequality we use the results in Proposition 1. Summing over k = 2,..... K - 1, and note that y1 = X1, and hence we have
E E(f(y)) - f(xi)) E (fly)) f(y1)) n/00000/ V due to Eq. (19), then we get:
B(f(xx) - f(x1)) < E
1
Σ
[ù o (y+41 - +
H22
KnBo²
4n
26

---

Under review as a conference paper at ICLR 2023
On the other hand, similar to the results given in Eq.(19), we have:
(- 2n
1
lÍ (y1 -80)1() no²
E (f(y)) f(yo)) E (f(x)) f(x))) S IE
Therefore, using (KK = (1) and the restart condition
n -)112 (ye-1 18-1--ye)1 yi)l| 2 2R²
10
1=
we can get:
((f(yk) - -(yu)) SE
1
|ng (yt+1 - yxs)l
+ RKC
+
(K33 (K33+ 1)n(
4n
ne²
R
4K33²
R2
(GG 1)
-0
R²
BR²
-n) =0((cl1))
S
4Cn
ny²
E
Kn n
Now, we finish the proof of this claim.
F.4 GRADIENT IN THE LAST RESTART CYCLE
Before showing the main results, we first provide several definitions for the convenience of proof. Note that, for any ho < K. we already have:
( - yoll S 1/)
k ye - yell S R.
and we have:
2R
E (1|x xoll) S E (lly= xxx| + lly: - xoll) S
(22)
eI//''
where we utilize the results from Proposition 1. For each epoch, denote H == 42 (xx)) We then define:
full full . Xo) + 1
h(y) = (80
2 (y xo) "H(y xo).
Recall the Eq. (15):
Yk+1 = Xx= - -Bm ( full + Exs = Xx - -Bnk o (Vh(xx) + 5% + Ex)
17k 7h-1 a (x4 yzs) }
(23)
X4+1 - yx+1 = (1 (1- (yx+1 yk) +
77-1
where we let 8x = gk
full V)((x),, and we can get that:
E (115xll) = E (115%.0) full go
Full H(xx - xo)(
2/ 1(xx xo)) H
(xx xo)dd()
(24)
2pR2
< [1xx xo 13]
Iterations in (23) can be viewed as applying the proposed optimizer to the quadratic approximation h(x) with the gradient error ôg. which is in the order of O (pR2/E)
Lemma Suppose that Assumptions 1-3 hold. Let (c 8 =(e), 1 (
S K= =(E=²) Then we have: E =
where X Ro-T Eke XL-
27

---

Under review as a conference paper at ICLR 2023
Proof. Since h(-) is quadratic, then we have:
Ko Ko
(I) =
V h1 (1s
1=1
Kg
1
E
Σ
(3mx) oyx+1 xx: + Ex + 8%
Ko
Ko
Kg
Ko
1
(Ko - -118 E
(8mm))+ (yk+1 - xx)
+
IF
E1
+
E
8%
(Ko 1)
(Ko 1)
k=1
1==1
(4) 1
Ko
VKo 2pR
(Ko 1) E
(mx) (yk+1 -xx)
0
1
Kg
Yk+1 Yk (1 - -3) Yk-1)
77 72-2
(1 - (3
(xk-1 yk-1)
(Ko - 1)8
7
1=1
0
2p1t²
+ KK
Ko
Yk+1 Yk - - -3) - -I--1)
23c251 R
0
2pR22
(Ko- -118 E
76
11c
VKo
k=1
(c) 1
Ko Σ
(1 -1y)(y -K--1)
4B0225 R
RpR
Yk+1 Yk
+
(Ko - 1).8
7
Mh-1
NE
VKg
E
YKg -Ko-1
1
Kg -1
Yk+1 - Yk
4.c21 R
σ
2pR²
E
E
(Ko 1)B3
7Ko
(Ko- 1)
VKn
k=1
(4) 1
Ko
Yk+1 Yk
4,902 R /o
2pR
+
(Ko 1)
7
BnK²
nE
v K
E
/00
Kn
DE + +E) 2/2 0 (yk+1 yx)
+ 4R/Coo
4,c B
0
2pR²
E
3nK2
K 0
20 R
4R Coo
4,c1.R R
2pR2
+
K
Knk²
ne
VKo- -1
R
3R
=0
+
+ R?
Oce),
"
VK
where (a) is due to the independence of E 's and (24), (b) comes from Propositions 1 and 2:
M - -
(xk-1 - Y2-1) 5
V n4k +
97-1 7-
- 1 o (Xs-1 - yx-1)
7h-2776
( TD
+c)
1/2
77--2
(/ix +6) 1/2 C282
C2
-1/2
1
R
17
(coo + + 1/2
V2 coo
R
1
1/4
2,3
1.5
S
c
3)1/4
1 - B
nE
28

---

Under review as a conference paper at ICLR 2023
use the following bounds in (c):
V Yk-1)
(yk
Yk 1)
17 7 (yk yk-1)
7
7/
17/-
D 1 + +&)
1/2
7K 17-
(v [/ + +0)1/2 (yss - Yx-11
1
17
(v - + +5) 1/2
/288
R
(coo + 5)) 1/2 v288 R 202 R
"
8
"
8
nek
(d) is implied by Ko = argmin [
(vTT +0) (Yk+1 - yxx)
and restart condition:
YKo -Ko-1
Kk +
(VIKo +0) -yk. yko-1)
MKo
1/2
(Vuko + (YKo - yKo-1i1"
1
[V + 2) (yk+1 - vww)
- [K/2]
[K/2]
Σ +2) (yx+1 ya)l" K K/2]
1
R² 2R
K LK/2]
K K2
Finally, we have:
E ((V)) = E E - v)(*)1) = O(c) + 2pR O(t).
where we use the results from (2.). namely:
E ( - Vh(x)]l)
= E (1) T
go full
H(X xo)|| 1 P
o E |x - xoll?)
2
and we also note that, by (22):
Ko
1
2R
E x xoll 5
E | - xoll 5
Ko
81/2'
k=1
F.5 PROOF FOR MAIN THEOREM
Theorem 2. Suppose that Assumptions 1-3 hold. Let B=
( 3= 17 = -
S K = (). Then Algorithm find an e-approximate first-order stationary point within at most (355)) iterations. Namely, we have:
B(f(x)) f(xo)) = (E) E ([V][())I) = O(e).
Proof. Note that at the beginning of each restart eycle in Algorithm 2, set xo to be the last iterate XIC in the previous restart cycle. Due to Lemma 3, we already have:
(f((y) - fxx)) (cc
Summing this inequality over all cycles, say N total restart cycles, we have:
min fxx) f(mmi)) (NN...)
Hence, the Algorithm 2 terminates within at most O 1.5 Ar) restart cycles, where A, == fxxiitt) minx f (x). Note that each cycle contain most K O iteration step, therefore, the total iteration number must be less than OE 3.55 -3.5Ay).
On the other hand, by Lemma 4, in the last restart cycle, we have:
E ([V] Oe).
Now, we obtain the final conclusion for the theorem.
29

---

Under review as a conference paper at ICLR 2023
G
AUXILIARY LEMMAS
Proposition 2. Assumption holds. We have:
mm mollss so S Coo:
n 1xl S 2:00
Proof. By the definition of my, we can have that:
m
Ck.ggi 1=0
where
11 B1) (K-1)
when 0,
Ch,l =
(1 31)²a
when t 0.
Similar, we also have:
(ge + +11-82)gg 11-1))
n1
where
Ba(1 (k-1)
when 0,
(1 - (1-3g)
when t 0.
obvious that:
k
C = 1,
Σ t=0
cee 1,
t=
hence, get:
||
Ck.t 11:loo1
t=0
|
Σ
delll:: (1- 32)(B:
Bi-1)) S &2.
t=0
Proposition 3. If Assumpttio holds, have:
V23g0o0
7
E
Proof. Give any index i [d] and the definitions Th, we have:
T 77
- +
-1|=
/n v n
7
n +
m +
Note that, by the definition of ni. we have:
D Vik
V [ ma
Vnk
+e
/ng +
(ge + (1 (2) - -1)
n1-1
V 283000
3z
v Vik +
hence, we have:
7
V283co0
E 0,
7
We finish the proof.
30

---

Under review as a conference paper at ICLR 2023
Lemma 5. Consider moving average sequence: m, (1 --)mk-1 + 8gk:
where we note that:
g E C) EN.
and we denote g
fall
= Eg f ()r for convenience. Then we have:
(1 -3) E ((10k-1 1100
E m
gk
Full
$ 3)
| Bk-1
Full
0ull9) + +3002
B
Proof.
Note that, we have:
m
Sk
Fail
=(1 (8) m
8k-1
Fail
+ (1 - 8)8k-1
full full
gk + 8gg
=(1 B) m
8k-1
full
+ (1 3) 88-1 8k
full fall) + 3 g: gk
{ full)
Then, take expectation on both sides:
E
ma - Bx full
=(1 2)²E( (111|110 | Bk-1
+ (1 - 3)2 (1
full
/ull s(ull()) + 8202
g
Bk
2(1 8)²B( (ma-1-
full full - gk ) )) 8k-
8K-1
< <(1 8)² + +11 (1- /3)aa ))/a) E m
full f'ulll?? +
8k-1
(1 1 a
(1 -33) (1
||
fall
/all
12)
+ +/8202
8%
(a)
S (1 8)B
|ma-1
gk-1
full | (2)
B)²
E
8k
||
full
g (
full (2) + 8²00
B
<(1 - B)E
|
8k-1
full 22)
(1
B) 2
E 11 -Oa13) + 82000
where for (a), we set
1-3
Lemma 6. Consider moving average sequence:
Vk = (1- 3V + 3(gk gk-1),
where we note that:
gx E< 5) + Ek,
and we denote gi full = E () for convenience. Then we have:
(Ivall) s (1 3) (Iva-111)) + 2,3
2//u1/33 + +3302 (|sA
full full
Proof. Take expectation on both sides:
E ([vvll() (1 - 3)² [|va_ 11²) + 3² - -188--1--111))) +23(1-B))B (B0--BB)(VV-i-1 gk-1))
(4) [1 - --))² (Ive-
11²) + 338 [lge
BA 11=) + 2,3(1 - 3)T (V=- full -gk-1) BB-1))
(4)
1)) +22 -3)E (v g/ full 8h-1) 3.802 g
(1 2) (1 ( 112) + 2
full
full
g
(c)
S1 8)²B
([Va-1 11)
+ +282
full (2)
+ + -3) (ve-1.g/"
full -g s/ul1) + 3
gk-1
(d)
S1 (11))))(( (1Vv-11)
+ 23 (1
full
full
+ +33302
31

---

Under review as a conference paper at ICLR 2023
where for (a), utilize the independence between gA and Vk-1, while for (b):
E (IB Ba-1ll3) B
(1 Bi
2B
||
full 88-111
21E
full
Bk-1
Fuel )
for (c), we know:
full - 88-1)) = E (1- + E V 8k_1
B(gu-1 - Bk-2) (f BB)
8k - 8k-1)
(11 B) - 3gk-2, -k-1 B1-1)) + 3 (gi-1 - Bk- + Bk Bk-1 1 8k-1 Bi
full
full
full full
= =- 31
(1 g/-lll 3/-1111
and thus E
V
Bi
full BA-1)) (((V full - B/-11) 313 ( - - Fi-
nally, for (d),
2E (V=-1.
full
s1-11) s <6(1V=-11) E L s(=4)1))
32


Reviews:
[{"review_id": "uDPW5MIwmBL", "reviewer": "Reviewer_5SGt", "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 first reformulate the update expression of the Nesterov acceleration technique and then modify Adam accordingly to develop a new optimizer named Adan, which is different from NAdam. The main difference between Adan and Adam is that the gradient difference g_k-g_{k-1} is incorporated in computation of both the 1st and 2nd momentum. Both convergence analysis and experimental evaluation are conducted for Adan. ", "summary_of_the_review": "The authors develop a new method Adan by incorporating the gradient difference g_k-g_{k-1} in Adam based on a reformulation of the Nesterov acceleration technique. (1) Explanation of why Adan has lower theoretical complexity is needed for the readers to better understand the method. (2) Paper presentation needs further improvement (see my comments above). (3) I don't find anywhere that the hyper-parameters of the reference methods in the experiments are manually tuned while the hyper-parameters of Adan are tuned. Also it is suggested to evaluate AdaBelied, Adam+, Aida in the experiments. ", "strength_and_weaknesses": "Strengths: \n1. The new method Adan is developed by incorporating the gradient difference g_k-g_{k-1} in Adam based on a reformulation of the Nesterov acceleration technique.\n2.  Both convergence analysis and experimental evaluation are conducted for Adan, showing its advantage over other optimizers. \n\nWeaknesses:\n1.  The authors claim that  Adan has lower complexity than a number of existing optimizers including AdaBelief and LAMB without an explanation. Is it because of the separation of the l2 regularizer with the objective, or because of the introduction of g_k- g_{k-1} in Adan, or because of improved mathematical deviation. This is very important. It helps the readers to understand what is the reason of the the low complexity of the new method without reading all the proofs. If it is because of the separation of the l2 regularizer with the objective or  improved mathematical deviation, it suggests that the convergence of other optimizers can also be improved.  \n2. It seems that the authors are aware of AdaBelief and Adam+ but didn't evaluate them in the experiments. AdaBelief is empirically found to have better performance than quite a number of opimizers including AdamW and Adam for training different types of DNN models including Transformer. Recently, a new method named Aida in the paper \"On exploiting layerwise gradient statistics for effective training of deep neural networks\" is found to perform better than AdaBelief.  I highly suggest the authors to also evaluate AdamBelief, Adam+ and Aida in their experiments. Furthermore, the parameter epsilon needs to be searched for each method to achieve best performance. It seems from page 7 that the authors only tune the hyper-parameters of Adan. \n3. Compared to Adam, AdamW, AdaBelief, Adan needs to tune an additional parameter beta_2.", "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": "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": "rYhWA_jU7F", "reviewer": "Reviewer_SpFC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes another variant of Adam by combining the idea of Nesterov momentum with the adaptive algorithms. The authors prove that in the nonconvex optimization setting, the proposed algorithm converges faster than the other adaptive algorithms. Experimental results show that the proposed algorithm performs better than the other algorithms in multiple tasks and different settings.", "summary_of_the_review": "Overall, I find the idea of introducing Nesterov momentum to adaptive optimization algorithm not novel enough, but I am impressed by the theoretical results and the experiments the authors have provided. The performance of the proposed algorithm does look significantly better than the existing ones. Therefore, I vote for acceptance.", "strength_and_weaknesses": "Strength:\n  1. The paper is well-written and easy-to-follow\n  2. This is by far the first paper that have shown theoretical benefits over existing algorithms, as far as I am aware of, which is highly appreciated.\n  3. The experimental results are on both small-scale and large-scale datasets, which are quite strong and convincing.\n\nWeaknesses:\n  1. The idea of combining Nesterov momentum with Adam is, as far as I am concerned, a very straightforward idea. I am actually very surprised that this hasn't been put into practice in common deep learning tools such as PyTorch or Tensorflow. Therefore, I find the idea of the paper not novel enough.\n  2. The theoretical benefit looks marginal to me. Isn't the difference between all the optimizers only a multiplicative constant-level difference? When is the convergence of the algorithm better than the others (i.e., under what assumptions of $d$, $c_2$, $c_\\infty$? Can the authors elaborate more? ", "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": "eHheXwe1cJ", "reviewer": "Reviewer_wTd4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduce a new adaptive method that built upon ADAM and Nesterov momentum. First, it reformulate Nesterov momentum update and combine it with ADAM; Second, it provides $O(\\epsilon^{-4})$ complexity for Lipschitz-smooth case; Third, it provides $O(\\epsilon^{-3.5})$ complexity for Hessian Lipschitz case. ", "summary_of_the_review": "Overall, the algorithm looks promising, but does not match the lower bounds in theory and I am not fully convinced by the experiments. ", "strength_and_weaknesses": "### Strength\n1. The idea is clear and straightforward\n2. The experiments are conducted for multiple tasks\n\n### Weaknesses\n1. The claim that $O(\\epsilon^{-3.5})$ is the lower bound is not correct. In Assumption 1, it assumes the function is smooth with respect to each value of $\\zeta$, which will already lead to a lower bound of $O(\\epsilon^{-3})$ even without Lipschitz Hessian. I also found that Assumption 2 is stronger than usual, as it assume $\\mathbb{E}||\\xi|| \\leq \\sigma$ rather than $\\mathbb{E}||\\xi||^2 \\leq \\sigma^2$. So I think lower bound could be much better than $O(\\epsilon^{-4})$ and $O(\\epsilon^{-3.5})$ for each case. \n2. From the change in equation (4), the algorithm introduce a new hyperparameter $\\beta_2$. In the new algorithm, there are three momentum hyperparameters to pick: $\\beta_1, \\beta_2$ and $\\beta_3$. When $\\beta_2 = 0$, the algorithm basically reduces to the vanilla Adam. In the experiment, it performs much better than Adam, so I am not sure whether it is simply a result of tuning $\\beta_2$. However, the ablation study in B.5 indicate that Adan is not sensitive to the value of $\\beta_2$, which contradicts that it is much better than Adam. \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject