Win: Weight-Decay-Integrated Nesterov Acceleration for Adaptive Gradient Algorithms
Authors: Pan Zhou
Xingyu Xie
Shuicheng YAN
Venue: ICLR 2023 notable top 5% (2023)
Keywords: Optimization acceleration in deep learning
network optimizers
deep learning optimizer
deep learning algorithm

Abstract: Training deep  networks on  large-scale datasets is computationally challenging.  In this work, we explore the problem of ``\textit{how to  accelerate  adaptive gradient algorithms in a general manner}", and aim to provide practical efficiency-boosting insights.   To this end, we   propose an effective and general   {Weight-decay-Integrated Nesterov acceleration} (Win) to accelerate adaptive  algorithms. Taking AdamW and Adam as examples,  we minimize a dynamical   loss per iteration which combines the vanilla training loss and a dynamic regularizer inspired by proximal point method (PPM) to improve the convexity of the problem. To introduce Nesterov-alike-acceleration into AdamW and Adam,  we respectively  use the  first- and second-order Taylor approximations of vanilla loss  to  update the variable  twice. In this way,  we arrive at  our Win acceleration  for AdamW and Adam that uses  a conservative step  and a  reckless step to update twice and then linearly combines these two updates for acceleration. Next,  we  extend  Win acceleration to LAMB and SGD. Our transparent acceleration derivation  could  provide insights for  other accelerated methods and their integration into  adaptive algorithms.  Besides, we prove the convergence of Win-accelerated adaptive  algorithms and  justify their convergence superiority over their non-accelerated counterparts by taking AdamW and Adam as examples.  Experimental results testify to the faster convergence speed and superior performance of our Win-accelerated AdamW, Adam, LAMB and SGD over their non-accelerated counterparts on vision classification tasks and  language modeling tasks with both CNN and Transformer backbones.  We hope Win  shall be a default acceleration option for  popular optimizers in deep learning community to improve the training efficiency. Code will be released at \url{https://github.com/sail-sg/win}.

Published as a conference paper at ICLR 2023
WIN: WEIGHT-DECAN-INTEGRAEEE NESTEROV AC- CELERATION FOR ADAPTIVE GRADIENT ALGORITHMS
Pan Zhou'
Xingyu Xie
Shuicheng Yan
'Sea AI Lab
Nattional Key Lab of General AI, School of Intelligence Science and Technology, Peking University { aaoouaa.xyxie.yynnce @ sea.com
ABSTRACT
Training deep networks on large-scale datasets is computationally challenging. In this work, we explore the problem of "how to accelerate adaptive grudient algo- rithms in general manner". and aim to provide practical efficiency-boosting in- sights. To this end, we propose an effective and general Weight-decay-Integraae Nesterov acceleration (Win) to accelerate adaptive algorithms. Taking Adam W and Adam as examples, we minimize a dynamical loss per iteration which com- bines the vanilla training loss and dynamic regularizer inspired by proximal point method (PPM) to improve the convexity of the problem. To introduce Resterov-alikc-acceleaatt into A and Adam, we respectively use the first- and second-order Taylor approximations of vanilla loss to update the variable twice. In this way, we arrive at our Win acceleration for AdamW and Adam that uses a conservative step and reckless step to update twice and then linearly combines these two updates for acceleration. Next, we extend Win acceleration LAMB and SGD. Our transparent acceleration derivation could provide insights for other accelerated methods and their integration into adaptive algorithms. Be- sides, we prove the convergence of Win-accelerated adaptive algorithms and jus- tify their convergence superiority over their non non-accelerated counterparts by tak- ing AdamW and Adam examples. Experimental results testify to the faster con- vergence speed and superior performance of our Vin-accelerated Adam W, Adam, LAMB and SGD over their non-accelerated counterparts tasks and language modeling tasks with both CNN and Transformer backbones. We hope Win shall be default acceleration option for popular optimizers in deep learning community to improve the training efficiency. Code will be released at https::/ thub. com/ sail- sg/win.
vision classification
INTRODUCTION
Deep neural networks (DNNs) are effective to model realistic data and have been successfully ap- plied to many applications. egg. image classification (He et al., 2016) and speech recognition (Sainath et al., 2013). Typically, their training models can be formulated as a nonconvex problem:
X
(1) where Rd is the model parameter; sample drawn from data distribution D; the loss is differentiable; À is a constant. Though many algorithms, e.g. gradient descent (Cauchy et al., 1847) and aaduuee--rduued algorithms (Rie Johnson, 2013), can solve problem (1), SGD (Robbins & Monro, 1951) uses the compositional structure in (1) to efficiently estimate gradient via minibatch data, and has become a dominant algorithm train DNNs in practice because of its higher efficiency and effectiveness. However, on sparse data or ill-conditioned problems, SGD suffers from slow con- vergence speed (Kingma & Ba, 201 2014), as scales the gradient uniformly in all parameter coordinate and ignores the problem properties on each coordinate. To resolve this issue, recent work has pro- posed a variety of adaptive methods, e.g. Adam (Kingma & Ba, 2014) and Adam (Loshchilov & Hutter, 2018), that scale each gradient coordinate according to the current geometry curvature of the loss Fz)) This coordinate- wise scaling greatly accelerates the optimization convergence and helps them, e.g. Adam and Adam W. become more popular in DNN training, especially for transformers.
min F(z) := EçwD C) + 2
|1=112-

---

Published as a conference paper at ICLR 2023
Unfortunately, along with the increasing scale of both datasets and models, efficient DNN training even with SGD or adaptive algorithms has become very challenging. In this work, we are particularly interested in the problem of "how accelerate the convergence of adaptive algorithms in a general manner" because of their dominant popularity across many DNNs. Heavy ball acceleration (Polyak, 1964) and Nesterov acceleration (Nesterov, 2003) are widely used in SGD but rarely studied in adaptive algorithms. Among the very few, NAdam (Dozat, 2016) simplifies Nesterov acceleration to estimate the first moment of gradient in Adam while totally ignoring the second-order moments, which is not exact Nesterov acceleration and may not inherit its full acceleration merit.
Contributions: In this work, based on a recent Nesterov-type acceleration formulation (Nesterov et al., 2018) and proximal point method (PPM) (Moreau, 1965), we propose a new Weight-decay Integrated Nesterov acceleration (Win for short) to accelerate adaptive algorithms, and also further analyze the convergence of Win-accelerated adaptive algorithms to justify their convergence superi- ority by taking Adam W and Adam as examples. Our main contributions are highlighted below.
Firstly, we use PPM to rigorously derive our Win acceleration for accelerating adaptive algorithms. By taking A and Adam as examples, at the k-iteration, we follow PPM spirit and minimize a dynamically regularized loss F=))+ + 27zu || srell orell/e,.H with the second-order gradient moment AdamW and Adam. Then to introduce Nesterov-alike accelera- tion and also make the problem solvable iteratively, we respectively approximate F((z) by its first- and second-order Taylor expansions to update the variable x twice while always fixing the above dynamic regularization and also an extra regularizer 2n12 = - induced by the weight decay in AdamW. As a result, arrive at our Win acceleration, a Nesterov-alike accelcration, for AdamW and Adam that uses a conservative step and a reckless step to update twice and then linearly com- bines these two updates for acceleration. Then we extend this Win acceleration to LAMB (You et al., 2019) and SGD, The above acceleration derivation is transparent and general which could motivate other accelerations and provide examples to introduce other accelerations into adaptive algorithms.
U2 and the stabilizing constant
Secondly, we prove the convergence of our Win-accelerated Adam and Adam. For both, to find an c-approximate first-order stationary point, their stochastic gradient complexity is (g1 and matches the lower bound 2 (x²)) in (Arjevani et al., 2019; 2020) (up to constant factors) un- der the same conditions, where Coc upper bounds the foo norm of stochastic gradient. Moreover, this d do of Adam-type optimizers in (Zhou et al., 2018; Guo et al., 2021), e.g. Adam, AdaGrad (Duchi et al., 201 I), AdaBound (Luo et al., 2018), since network parameter dimension dl is often much larger than .0.5 especially for over- weer-parameterized networks. Indeed, Win-accelerated Adam and Adam also enjoy superior com- of plexity than other Adam variants, e.g. Adabelief (Zhuang et al., 2020) with compelxity O (5A2)) ), es- pecially on over over-parameterizer networks, where C2 is the maximum Eg nn-norm of stochastic gradient.
d complexity improves a factor O 2015 over the complexity O
Finally, experimental results on both vision classification tasks and language modeling tasks show that our Win-accelerated algorithms, i.c. accelcrated AdamW, Adam, LAMB and SGD, can acceler- ate the convergence speed and also improve the performance of their corresponding non-accelerated counterparts by a remarkable margin on both CNN and transformer architectures. All these results show the strong compatibility, generalization and superiority of our acceleration technique.
RELATED WORK
In the context of deep learning, when considering efficiency and generalization, one often prefers to adopt SGD and adaptive gradient algorithms, e.g. Adam, instead of other algorithms, e.g. variance- reduced algorithms (Rie Johnson, 2013), to solve problem (1). But, in practice and theory, adaptive algorithms often suffer from inferior generalization performance than SGD (Zhou et al., 2020a;b). To solve this issue, AdamW (Loshchilov Hutter, 2018) proposes decoupled weight decay which introduces fa-alike regularization into Adam to decay network weight iteratively, and its effee- tiveness is widely validated on ViTs (Touvron et al., 2021) and CNNs (Touvron et al., 2021). Later, LAMB (You et al., 2019) scales the update in AdamW to the weight magnitude for avoiding too large or small update, but suffers from unsatisfactory performance on small batch. In this work, we aim to design general acceleration to accelerate these adaptive algorithms.
Hall acceleration (Polyak, 1964) and Nesterov acceleration (Nesterov, 2003) are two classi- cal acceleration techniques, and their effectiveness in SGD is well testified. Later, NAdam (Dozat,
2

---

Published as a conference paper at ICLR 2023
2016) integrates Nesterov acceleration into the first-order gradient moment estimation but ignores the second-order gradient moments which harms the acceleration effect. Some works (Anil et al,, 2022: 2020) also explore Nesterov acceleration for second-order algorithms. e.g. shampoo (Gupta et al., 2018). Recently, for full gradient decent algorithm, a new general Nesterov-type accelera- tion (Nesterov al., 2018) directly interpolates two variables look ahead for correction, and is more flexible than vanilla Nesterov acceleration (Nesterov, 2003) which interpolates the variable and gradient. See discussion in Sec. 3.2. Here we use proximal point method introduce this new acceleration into adaptive algorithms by rigorous and transparent derivation and necessary tailors.
3 WEEIGH--DECAV-INTEGRATTT NESTEROV ACCELERATION
To accelerate full gradient descent algorithm, given a full gradient (=(= of problem (1) at the k-th iteration, Nesterov-type acceleration (Nesterov et al., 2018) generally uses a conservative step T and a reckless step îī to update two sequences 2k+1 and yk+1 respectively, and then linearly combines them to update the variable #k+1 of the problem. Similar formulations are also observed and proved in recent works, e.g. (Allen-Zhu & Orecchia, 2014; Bansal & Gupta, 2019; Ahn & Sra, 2022). In general, their acceleration formulation can be formally formulated as
1 = 2x - M) V F(z)), yk++1 = TJ V F(z)), Zk+1 - P + (1 - pk px)yk+1 (2)
This acceleration enjoys provably faster convergence rate for full gradient descent method on convex problems (Nesterov et al., 2018), and is then empirically validated in many convex and nonconvex cases, e.g. (Wilson et al., 2017: Nado et al., 2021). Despite its effectiveness, such acceleration is rarely explored in adaptive gradient algorithms, especially for network training. In determinis- tic optimization setting, another widely used proximal point method (PPM) (Moreau, 1965; Rockafellar, 1976). At the k-th iteration, PPM op- timizes an fz-regularized loss F(z)+ + 2nc || 2x-1 instead of the vanilla loss F(z). This small change enhances the convexity of the problem, accelerating and also stabilizing optimization pro- cess (Kim et al., 2022; Zhou et al.. 2021c). To make the fe-regularized problem solvable iteratively, PPM approximates the loss F(z) by its first- or second-order Taylor expansion so that each iteration has close-form solution (see below). At below, we borrow the idea in PPM to induce a Weight- Nesterov acceleration (Win) for adaptive algorithms by using Adam W and Adam as examples in Sec. 3.1, and then extend this acceleration technique to LAMB and SGD in Sec. 3.2.
-ttabiiiioonstaaaiiizingg and acceleration approach is
3.1 WIN-ACCELERATED ADAMW AND ADAM
To begin with, following most adaptive gradient algorithms, egg. Adam and AdamW, we estimate the first- and second-order moments my and vy of gradient as follows:
b 9k E._ Vf(zi Ci), m = (1 3mm + Bigk: Uk =1 (1- 82) + 829 (3)
where 9k is the average gradient a minibatch data of size b, 31 E [0, 1] and B2 [0, 1]. For the initialization, we set my = gu. Vo = g6. For brevity, with a small scaler => O. we define
S / U2 + +
u m /ux +v.
(4)
Then following the spirit of PPM, the k-th iteration, we minimize regularized loss F(x)+ + 1 || 1 2 l where ||a.|l..- (x., +x*2) with an element-wise product operation *. Here we use 2nj. the regularizer - 11,., instead of the Ez-regularization || 1|2 since 1) this new regularization can induce adaptive algorithms as shown below Eqn. (5), and 2) increases the convexity of the problem and further considers different sharpness property of each coordinate because of different elements in 8g. accelerating convergence. To make the problem solvable iteratively, we approximate the vanilla loss F(z) by its first-order Taylor expansion at the point 24 and update #x+1 as
1 ||
d
1 (x* 1 mp UR), (5)
Fb+1 argmin ((zx) (zz) (m,, x 24)
2 11: +
|
112
2/1
1+
where m. is used to approximate the full gradient V F(z)). We add small regularization A ||
As
since 1) it can largely improve the generalization performance in practice (Loshchilov & Hutter, 2018; Touvron et al., 1021); 2) it allows to derive Adam (Aę- 0) and AdamW (Ax > 0). Here A can be fixed as a constant or evolved along iteration number k. But in practice, a evolving A often enjoys better performance than fixed one (Caron et al., 2021; Zhou et al., 2022). When A = 0, the updating (5) becomes the exact Adam. If X > O, the updating (5) can approximate the updating rule # (1 >4TIK Tj. Ug of AdamW. This is because consider A is small in
3

---

Published as a conference paper at ICLR 2023
practice, we can approximate (1 \bTTk (1ank))-= - A O and thus 14 (æt 7/ m7/2,s))
[] [1- ARTk + (A - 1m ( +AA which becomes AdamW by ignoring the ignorable terms ((n)) or O(m)). This is also reason that we adopt the regularizer ||æ x 11 in (5) instead of the Eg-regularization in PPM, since we can flexibly derive Adam and Adam
Similarly, we minimize a regularized loss F(z) +
1 | I1+1 ll again, and further approximate
2n
F(z) by its second-order approximation F(zx) + (ms; 2- - =x) + 20
|| xK+ 11 + A
Zk41 - aarmmin, F(zx)+ (m= -zz) + 21/k:
|z zx zxlla= + 27tk
1z (6)
- + Th (z T)
where T th + A m is used to approximate Vx(*)) as guaranteed by Theorem 1 in Sec. 4, 77 approximates the inverse of the local smoothness parameter of F(z) around zg. Here we use regularizer || Tx+1 2 with the latest update #1++1 instead of æy as an anchor point, since the latest update xx+1 could often provide better regularization for the concurrent optimization.
Now we have used PPM to rigorously derive our Win-accelerated Adam and Adam in Eqns. (3), (5) and (6). For more clarity, we summarize their algorithmic steps in Algorithm I in which we omit the bias-correction term for simplicity. When À = 0, it is Win-accelerated Adam; if X > 0, it gives Win-accelerated AdamW. Generally, AdamW can greatly improve the generalization performance of Adam by simply adding a weight decay (i.e. the regularizer ž |1=, into Adam observed in many works, e.g. (Loshchilov & Hutter, 2018; Touvron al., 2021). Our Win- acceleration is quit simple and efficient, since our accelerated AdamW/Adam only adds one extra simple algorithmic step, i.c. the seventh step in Algorithm 1, on vanilla Adam W/Adam, and brings negligible extra computational overhead into vanilla optimizer, e.g. about 2% ~ 5% extra training time per iteration on AdamW evaluated on ViT-small and ViT-base. Moreover, for the only extra hyper- byper-parameter, the reckless step Ti, in Algorithm over AdamW/Adam we always set it 2 larger than the conservative step Y]k: for all iterations, i.e. fiJ- = 21j,, working well in our all experiments.
Now we discuss the relations between Nesterov-type acceleration (2) and our Win acceleration (6). Uh in Win, and rewrite (6) as
For comparison, we introduce a virtual sequence yk++ = 2k
Fk+1 (1 + { (x mpp))), yk+1 = 2 Tip Ug #k+1 -
(7)
where 24 is defined in (4). By comparing Nesterov-type acceleration (2) with our Win accelera- tion (7), one can observe some similarity and also differences as well. For similarity, both methods use conservative step пд and a reckless step îe to update # and y respectively, and then linearly combine 1 and yk+1 to obtain Zk+1- For the differences, the first one is that Win has a weight-decay-alik factor I+ in (7) which slightly decays the variable 3y like AdamW W and also the update uy. while Nesterov acceleration does not have. Note, weight decay can greatly benefit generalization in practice as shown in many works, e.g. (Loshchilov & Hutter, 2018; Touvron et al., 2021; Liu et al., 2021). Another difference is that for almost all acceleration techniques, including Nesterov-type acceleration (2), the sum of their linear combination factors (e.g- Pl: and 1 Pk in (2)) Aie is always one. In contrast, in Eqn. (7), Win uses 7J + Tą:T = カe- fe 1 when A >0, 0, which further gives second weigh decay. Since these two differences caused by the weight decay, we call our acceleration
Nesterov acceleration" (Win for short).
3.2 EXTENSION TO LAMB AND SGD
Here we generalize Win acceleration to LAMB (You et al., 2019) and SGD (Robbins & Monro, 1951). For LAMB, scales the update uæ of AdamW in Eqn. (4) so that us is at the same magnitude of the network weight æg. That is, it changes the update rule xx+1 = (1 AkTlk) )x, m)
in AdamW to # I& ?i |rette aa2 (rk + >g.zK) where Tą m./ Rt- This modification is avoid too large or small update, improving optimization efficiency. To extend Win acceleration to LAMB, we inherit this scaling spirit, and scale the update uq in (4) to the following one:
||æu|||
UE <1 //a//l/////////// + Au 2|2) (rx + >x
(8)
We scale m instead of (mz/ sx + Aạæx)) in LAMB, as our scaling can be repeatedly used to update our two sequences 26 and zg. Next, the two sequences 2g and zg. See the detailed steps of Win-accelerated LAMB in Algorithm 1, and the detailed comparison between LAMB and Win-accelerated LAMB in Appendix A.
respectively follow Eqn. (5) and (6) to update
4

---

Published as a conference paper at ICLR 2023
Algorithm 1: Win-Accelerated Adam Adam and LAMB
Input: initialization 2o = O, step size {(Te Th) H moment parameters {31, B2}.
Output: (Ø, 2) uniformly seleted from { =k)
while do
gs = 1 E Vf(=xi Ç1)
v (1 1-31)m=- + Bigh
1 mg = 90 *
vs = (1- (1-82)00-- + $29
/ vo = 9 */
2k veuto for Adam W and Adam, UA [Imm//er wtt.//ttttttttttt tothe m. ll (op + +x2DD)) for LAMB
1
Ck+1 I+A2nE
2b41 = T16T) + The (Zx- - Th ux) with To The t- Ap.06.
end while
For SGD, applying Win acceleration to is quite direct. Specifically, the only algorithmic difference between SGD and A on the fz-regularized problems is that SGD has no second-order moment 2x while AdamW has. So we can borrow the acceleration framework of Adam Sec. 3.1 to accelerate SGD by setting
1 Rd in Eqn. (4), (5) and (6), and obtain Win-accelerated SGD:
my - 3 Bigh, 0k+1
(xx m)))) Zk+1 T (z): -fj.m)). (9)
where 8i E [0, 1] is dampening parameter. Here we slightly modify the moment my to accord with the one used Nesterov-acceelratee SGD (e.g. SGD-M in Pytorch) whose updating steps are
m& fim=-1 (gv \ιaR), T641 (1 (1-A7T)))a - 7/ (gx + +2mm)). (I0)
By comparing Win-accelerated SGD and SGD-M in (10), one can find their big differences mainly caused by their different acceleration strategies and ways to handle weight decay. Win-accelerated SGD is derived from PPM and recently proposed acceleration (2), while SGD-M modifies an- other previous Nesterov-type acceleration (Nesterov, 2003) (of formulation m. fim mi Di V TJ. m Çi) and #++11 Ig + m&) to better train networks. See more mecha- nisms of previous Nesterov acceleration and (10) in (Sutskever et al., 2013; Bengio et al., 2013).
4 CONVERGENCE ANALYSIS
Here investigate the convergence performance of Win-accelerated algorithms by taking acceler- ated A, Adam and SGD as examples, as these algorithms are more preferably used in deep learning field. Moreover, since we aim accelerate deep network training which is highly noncon- vex problems, we focus on analyzing nonconvex problems to accord with the practical setting.
For analysis, follow previous optimization works, e.g. (Kingma & Ba, 2014; Reddi al., 2019; Duchi et al., 2011: Zhou et al., 2020b; 2021a;b; Xie et al., 2022), to introduce necessary assumptions. Assumption (L-smoothness). We say a function f(z, -) be L-smooth w.r.t. 2, ifr Vz1, 22 and VÇ ~ D, we have ([V <) - (= C)ll2 < L L| z2ll2 with a universal constant L. Assumption 2 (Unbiased and bounded gradient estimation). The gradient estimation ge is unbi- ased, i.e. for vk, E[gn = (2xx) and its magnitude and variance are bounded, namely, for Vk, l1ghl1> S Coe and [||| F(z)) g 2l I with two universal constants C.o and a.
Next, we first define a dynamic function Fz( at the k-th iteration which is real loss minimized by algorithms. It combines the vanilla loss F(z) in (1) and dynamic regularization As. ||=||2,
Fx(x) = F(z) + A |== Eclf(=; +
d 2
|=
(1I)
2
where 8& is given in (4). To obtain (11), following PPM spirit and Eqn. (5), one can approximate F(z) by its first-order Taylor expansion, and obtain Eqn. (5) with æ replaced by z to update 21+1 1+ (z+- m st)). Since d is very small, one can follow the discussion below Eqn. (5) and
approximate 2k+1 2k+1 = (1 > Z4 / Sh which becomes the update rule of Adam W. This the reason that our analysis on Win-accelerated AdamW involves a dynamic loss F1(2)) in (11). Note, for Win-accelerated Adam (A+ =0), (x) degenerates to the vanilla loss F(z).
With these assumptions, we analyze the convergence behaviors our accelerated algorithms on gen- eral nonconvex problems, and summarize our main results in Theorem 1 with proof in Appendix E.
5

---

Published as a conference paper at ICLR 2023
Theorem 1. Suppose Assumptions I anddd 2 hold, and x, Eargming F(x:). Let iT
S O _2 ). 31 S ( (02))2) (2.62222002))
oZ2 S22 E (0,1), = (ca + +2 A = X(1 826
(k: 0)
v
and Ag with constant X > O. Then after T = 0 2125
1. iterations with minibatch size
b and A = F(xo) - F(x,). the sequence {( =x) =x)] generated by Win-accelerated Adam W and Adam in Algorithm I satisfies the following four properties.
a) The gradient (x(ss) of the sequence {Ixx 1 can be upper bounded by
1
[[IIFF(EE))1 k=0
1
[lmm + A * sk sx11 =²²
T
b) The gradient moment my can well estimate the full gradient (xxk) and Fz()))
T K= B [B| - VF(mx))1
R Bl|ma VF((>))(3 16 2c
0.5 T. )
max
c) The sequence {IR, } satisfies
- k= L
12.
y2.583422
0.5
Ellaa -
1 Bl
De 2x113 S Anpe
4c(1
4CT.
d) The total stochastic gradient complexity to achieve the above three properties is O
Theorem 1 guarantees the convergence of Win-accelerated AdamW and Adam in Algorithm on nonconvex problems. When A > 0 (Ap== - 0), Algorithm 1 corresponds to Win-accelerated Adam (Adam). For both cases, Theorem 1 holds. Theorem a) shows that by running at most
O 2.5 Ao Co 21,25 iterations, the average gradient +Σ B F (3+)) is upper bounded by e², guaranteeing the algorithmic convergence. Theorem b) indicates the gradient moment m, can well estimate the full gradient F2()) and also V Fa(ag)) because of their small distances, guaranteeing the good Taylor approximation used in Eqns. (5) and (6). Moreover, in Theorem 1 c), one can find that although Algorithm I uses a conservative step Tik and reckless step fΙk YTJk (Vy 1) to update, the two sequences I++11 and Zk+1 can converge to each other, which could be the key for the good convergence behavior of both win-accelerated AdamW and Adam.
Now we discuss the stochastic gradient complexity of Win-accelerated Adam and AdamW. The- orem 1 d) shows that to find an <-approximate first-order stationary point, both Win-accelerated
2. ".)"
Adam and AdamW have the complexity O jevani et al., 2019; 2020) (up to constant factors) under the same Assumptions and 2. Our ac- celerated Adam and AdamW enjoy superior complexity over Adam-type optimizers, e.g- Adam, AdaGrad (Duchi et al., 2011), AdaBound (Luo et al., 2018), whose previously best known com-
(x (x,2)((4) which matches the lower bound 2 in (Ar-
plexity under the same assumptions is O do in (Zhou et al., 2018; Chen et al., 2021: Guo et al., 2021). By comparison, both accelerated Adam and Adam improve their complexity by a factor O ( ), where the network parameter dimension
often much larger than .0.5 espe-
cially for over-parameterized modern networks. Since the convergence of Adam has not been proved yet in the literatures, here cannot directly compare with it. Moreover, the complexity of Win-accelerated Adam and AdamW is also lower than O cooa of Adabelief (Zhuang et al., 1-
gic 2020) and O 0.5 d'. of RMSProp (Tijmen & Geoffrey, 2012; Zhou et al., 2018), especially on oveo-vverrraaaooo wver-parameterized networks, since for a d-dimensional gradient, its εg-norm upper bound 0o is often much larger than the -nom Coo and can be vdx larger for worse case.
Now we discuss the convergence performance of Win-accelerated SGD in Theorem 2.
Theorem 2. Suppose Assumptions I and hold, and x, E Eargmin_ F(x)). Let îh Y 7> >,1, TJs- be"
n 7SO( be² ). 31 5 be2)) 81=1- 31, d => do 0. After T 0( 20"+) iterations with minibatch size b and A - F( -x..). the sequence ( 2x) ) generated by Win-accelerated SGD in (9) satisfies the four properties in Theorem with == Coo =c= and 8 LERd
See its proof in Appendix F. Theorem also guarantees the convergence of Win-accelerater SGD. By using the apprr-paraette settings in Theorem 2, the sequence { } generated by Win- accelerated SGD satisfies the four properties in Theorem with = Coo = c = 1 and 8; = 1. shows the complexity O La²) ) of Win-accelerated SGD which also matches the lower bound ((+)) in (Arjevani et al., 2019; 2020) (up constant factors) under Assumptions 1 and 2.

---

Published as a conference paper at ICLR 2023
Table ImageNet top-1 accuracy (%) of ResNet500 101 whose official optimizer is LAMB due to the stronger data augmentation for better performance. is reported in (Wightman et al., 2021).
ResNet50
ResNet101
Epoch
100
200
300
avg.
100
200
300
avg.
SAM
77.3
78.7
79.4
78.5
81.1
81.6
80.7
SGD-H
75.3
76.9
77.2
76.5
77.7
78.6
78.8
78.4
SGD-M
77.0
78.6
79.3
78.3
79.3
81.0
81.4
80.6
SGD-Win
78.0
79.2
79.7
79.0+0.7
80.1
81.2
81.6
81.0+0.4
Adam
78.4
78.8
78.1
78.4
80.2
80.6
79.7
Adam- Win
77.4
78.8
79.3
78.5 +8.5
79.2
80.6
81.0
80.3+0.6
Adam W
77.0
78.9
79.3
78.4
78.9
79.9
80.4
79.7
Adam W-Winn
78.0
79.3
79.9
70.1
80.2
81.1
81.3
80.9+1.2
LAMB LAMB-Win
77.0
79.2
79.8*
78.7
79.4
81.1
81.3"
80.6
78.4
79.7
80.1
79.4+0.7
80.6
81.5
81.7
81.2+0.6
EXPERIMENTS
Here we evaluate our accelerated algorithms on two representative tasks, including vision classifi- cation tasks and natural language modeling tasks. For vision tasks, we test accelerated algorithms on both CNNs, e.g. ResNet (He et al., 2016), and vision transformers (ViT'), e.g. ViT (Dosovit- skiy et al., 2020) and PoolFormer (Yu et al., 2021; 2022). For language modeling tasks, we use LSTM (Schmidhuber et al., 1997) and Transformer-XX (Dai et al., 2019) for evaluation.
For clarity, we call our accelerated algorithm "X-Win", where "X" denotes vanilla optimizers. e.g. Adam. In all experiments, we do not change model architectures and data augmentations, and only replace the default optimizer with ours. Moreover, for all experiments, our accelerated algo- rithms, e.g. AdamW- Win, always use the default optimizer-inheront optimizers, e.g. first- and second-order moment parameters 31 and B2 in Adam W; and their reckless step 77k always satisfies îiK = 27)x- These settings well reduce the parameter-tuning -tuning cost of our al- gorithms. In the experiments, same with other optimizers, we only slightly tune other widely tuned hyper-parameters around the vanilla ones, e.g. step size and warm-up epochs, etc, which is reason- able, as our accelerated algorithms have two step sizes and the vanilla ones are very suitable.
parameters of the vanilla
5.1 RESULTS ON VISION CLASSIFICATION TASKS
Results on ResNet18. Here we follow the conventional supervised training setting used in ResNets (He et al., 2016) and evaluate our accelerated algorithms on Ima- geNet (Fei-Fei, 2009). Due to limited space, we defer the hyper-parameee
Table Image top-1 accuracy (%)
of ResNet18, 8. *, and $ are respectively reported in (Chen et al., 2021), (Zhuang et al., 2020) and (Liu et al., 2019).
settings of the four accelerated algo- rithms in Table into Appendix B.
AdaBound
68.1"
Radam
67.7"
Nadam
68.8
Padam 70.1*
Yogi
68.2*
AdaBeliel
70.1
Table I shows that our accelerated algorithms can improve the corresponding non-accelerated versions by a remark- able margin. For instance, Adam W- Win, Adam-Win and
SGD-H
67.3
Adam-M
67.7
SGD-M
70.2*
Adam
66.54
SGD-W Win
70.7
Adam- Win
69.3
LAMB-Win Win respectively make 3. 1%, 2.8% and 2.6% im- provement over their corresponding non-accelerated coun- terparts, Adamw, W. Adam and LAMB. Moreover, SGD-Win improves SGD-H (i.c. SGD heavy ball) by 3.4%. and also surpasses SGD-M aesseerov-accelerateed SGD in Sec. 3.2) by 0.5%. also vali- dating the superiority of our Win accelcration. Besides, our accelerated algorithms, i.c. SGD-Win, AdamW-Win and LAMBB Win, beat several other optimizers, egg AdaBound, Radam (Liu et al., 2019), Nadam, Padam (Chen et al., 2021), AdaBelief, Yogi (Zaheer et al., 2018), in which Nadam uses Nesterov acceleration to estimate its first-order gradient moment. Actually, LAMB- MiB--Win sets a new SoTA top-1 accuracy on ResNet18. 8. All these results show the strong compatibility and superi- ority of our Win-acceleration in adaptive algorithms.
Adam
67.9"
LAMB 68.5
AdamW-Win 31.0
LAMB-Win
71.1
Results on 1esNet501101... Here adopt the training setting in (Wightman et al., 2021) to train ResNet50& 101, as this setting uses stronger data augmentation and largely improves CNNs' perfor- mance. See augmentation details and our algorithmic syper-parameet settings in Appendix B. Here LAMB is the default optimizer because of its higher performance than other optimizers caused by the stronger augmentations (Wightman et al., 2021). All optimizers in Table 2 are under this setting.
Table shows that our accelerated algorithms consistently outperform their corresponding non- accelerated version. For example, across the three training epoch settings on ResNet50/ ResNet101,
7

---

Published as a conference paper at ICLR 2023
Table 3: ImageNet top-1 accuracy (%) of ViT and PoolFormer whose default optimizers are both
Adam W. and are respectively reported in (Touvron et al., 2021) and (Yu et al., 2021).
ViT-S
ViT-B
PoolFoomer-S12
Epoch
150
300
avg.
150
300
avg.
150
300
avg.
SGD-M
77.4
79.4
78.4
79.6
80.0
79.8 80.640.8
69.7
74.3
72.0
SGD-Win
78.1
80.1
79.1
80.4
80.8
71.1
74.5
72.840.8
Adam
77.3
79.3
78.3
79.0
79.7
79.4
74.3
76.3
75.3
Adam- Win
78.6
80.2
79.4+1.1
80.0
80.5
80.3+0.9
75.6
77.1
76.4+111
Adam W
78.3
79.8*
79.1
79.5
81.8*
80.7
75.2
77.1*
76.2
Adam W-ii
79.3
81.0
80.2+1.1
81.0
82.3
81.7+1.0
76.7
77.6
77.2+1.0
LAMB LAMB-Win 79.3
78.0
79.6
78.8
80.3
80.8
80.6
75.4
77.4
76.4
80.6
80.0,1.2
81.0
81.4
81.2
76.7
78.0
77.44..
LAMB-Win always achieves remarkable improvement over the official optimizer LAMB for this training recipe. Specifically, LAMB-W Win makes 0.7% average improvement over LAMB on both ResNet50 / 11 For AdamW- W-n and Adam- Win, they also respectively improve their coun- terparts by 0.7% and 0.4% on ResNet50, 1. 1.2% and 0.6% on ResNet101. SGD- Win also makes 2.5% and 0.8% overall improvement over heavy-ball accelerated SGD (SGD-H) and Nesterov accelerated SGD (SGD-M) on ResNet50, and also has similar advantage on ResNet101. These improvements are not trivial because of the following two reasons. 1) Since the performance is already high and may approach the model limit, it is already very hard to make very large improvement. This is testified by the fact that in (Wightman et al., 2021), using LAMB to train ResNet50 for 600 epochs only gives 80.4% t accuracy. In contrast, our accelerated LAMB-W Min-WWn uses 300 epochs (half training cost) to achieve 80.2%. 2) By comparing the previous optimizers, including SAM, SGD-M, Adam, AdamW W and LAMB, one can observe smaller accuracy gap (S 0.2%) between the best op- timizer and the runner-up. For example, on 101, the SoTA optimizer, i.c. SAM, only makes 0.1% average improvement over the runner-up up LAMB. All these comparisons show the non-travail improvement of our accelerated algorithms over their counterparts.
Results on ViTs. We follow the widely used official training setting of ViTs (Touvron et al., 2021; Yu et al., 2021). To evaluate the performance of our accelerated algorithms, we select two popular and representative VIT architures, including ViT (Dosovitskiy et al., 2020) and PoolFormer (Yu et al., 2021). See the training setting and our hyper-parameter settings in Appendix B.
We test accelerated algorithms under different model sizes and different training epochs, and report the results in Table 3. One can find that since Adam W and LAMB use the decoupled weight decay, they enjoy better performance than SGD and Adam, which is also observed in other works, egg. (Xiao et al., 2021; Nado et al., 2021), Moreover, under different training settings, our accelerated algorithms consistently outperform the corresponding non non-accelerated counterparts. Specifically, compared the default Adam optimizer on both ViT and PoolFormer, our accelerated Adam W- Win respectively makes about 1.0%. 0.9%. 1.0% average improvement under the two training epoch set- tings on ViT-S, VIT-B and PoolFormer-S12 For Adam-Wip Win and LAMB-Win, one can also observe their remarkable improvements on the three ViT backbones. Moreover, our accelerated SGD- Win SGD denoted as "SGD-M" by non-trivial margins under
also outperforms the Resterov-accelerate all settings. All these results are consistent with the observations on ResNets, and they together demonstrate the advantage of our accelerated optimizers for deep network training.
Results Analysis. Here we investigate the convergence behaviors of accelerated algorithms, and aim to explain their better test per- formance over their non-accelerated counterparts. In Fig. 1, we plot the curves of training and test losses along with the training epochs on ResNet18 8 and ViT-B. One can find that our accelerated algorithms, e.g. AdamW- W-Win, show much faster convergence behaviors than their non-accelerated counterparts, e.g. AdamW: W. Moreover, SGD-Win also converges faster than Desterove-acceelerate SGD, i.e. SGD-M. We also plot the curves of test accuracy in Fig. 2, showing the superior convergence speed of AdamW-Win and LAMB-Win over their non- accelerated versions. Fig. 3 in Appendix B also reveals SGD-Win and Adam-Vo Win enjoy faster convergence than their non-accelerated counterparts in terms of test accu- racy. So these faster convergence behaviors could contribute to our accelerated algorithms for their higher performance over non non-accelerated counterparts under the same computational cost.
Accurass
20
65-
AdamiV-Win LLMB
LAMBB-Wi
30
40
Training Epochs
Figure 2: Test accuracy curves of Adam Win and LAMB-WiL on ResNet18.
8

---

Published as a conference paper at ICLR 2023
Toaniigg and lad Lon
SCD- on Resteetl8
Adam-Win on Resfittl
Ads JdemW-Win on ReaNet18
2a lo05
LAMD-Win on RenNetl8
sop trinn
Adamii train
coin
Adamii win train
train
sGp lest oos
Adam led
Adami lest losa
JANB tss! icsa
30p Win foxo
Adum W test 1o3
Adami Wiin sost los
JAMB Win soit loxu
Traning Epechs
Training
Training
Trenur and lea Low
SGD Win on VIT-B
Adam Win on VIT-B
Adami Wiin on VIT-B
LAMB-Win on VIT-B B
200-M crain lsa
Adam tran
Adintil stain losa
LAME tusn issa
SOD-Win bun
Alam-Win sain
tin zan
LANE los
Dun
lie
192
303
Truiting tpochs
Treining Epocts
Treining
Spects
Training Epochs
Figure 1: Visualization of training and test losses on ImageNet. In all figures, training loss is larger than test one, as training data use random augmentations, e.g. random crop and clip, while test data only adopt the centralization crop which eases the recognition difficulty and thus has small loss.
Robust Analysis. For the only extra hyper- parameter 7i in our accelerated algorithms over their non-accelerated counterparts, in experiments, we always set vik- Ykk. where 7 = 2. Here we investigate the effects of 7 to the accelerated algo- rithms on ResNet50 by taking Adam Winn and LAMB- -in as examples because of their superior performance. Table shows the stable performance of AdamW-Wa and LAMB-Win when tuning in a relatively large range, thus validating their robustness to the hyper-parameter 7.
Table 4: Effects of y to top-1 1 accuracy (%) of AdamW- and LAMB- Win on ResNet50.
1.5
2
3
6
8
AdamW-Win LAMB- Win
77.9
78.0
78.0
77.9
78.1
78.0
78.3
78.4
78.4
78.4
78.5
78.3
5.2 RESULTS ON NATURAL LANGUAGE MODELING TASKS
Results on LSTM. We follow AdaBelief to test our accelerated algorithms via training three-layered LSTM (Schmidhuber et al., 1997) on the Penn TreeBank dataset (Marcinkiewiczz, 1994) for 200 epochs. See optimization and training details in Appendix B.
Table 5: Test perplexity of LSTM on Penn Treebank. is reported by Ad- aBelief (Zhuang et al., 2020).
AdaBound
63.6*
Radam
70.0*
Yogi
67.5*
AdaBelief
61.2*
fromage
68.0-
MSVAG
65.3-
From Table 5, one can observe that our Win-accelerated algorithms consistently surpass the corresponding non- accelerated counterparts, and actually bring 1.2 over- all average perplexity improvement over the four non- accelerated counterparts.
SGD-H
67.4
Padam 63.2*
SGD-M SGD-Wir
63.8*
Adam
64.3*
61.6
Adam- Win
62.7
AdamW
67.0"
LAMB
66.8
Adam W-wwiwwiii Win 46.5
LAMB-WA
Min 66.2
Results on Transformer-X XL. We adopt a widely used lan- guage sequence model, i.c. Transformer-L (Dai et al., 2019), to further evaluate the performance of our accel- erated algorithms. Since 1) Adam is the most popular and used optimizer in NLP models, including Transformer-X XL, and 2) our limited resource cannot well tune the hyper- parameters of other optimizers in Sec. 5.1, we take Adam as an example to show the superiority of our accelerated algorithms. Follow the official setting of Meaesfoomer-----aase we use Adam-Wii with the default of Adam on the WikiText- 103 dataset. See more details in Appendix B.
Table 6: Test PPL of Transformer-X0 XL- base on WikiText- 103 where Adam is the official optimizer. * is reported in the official implementation.
Training Steps
Transformer-y XL
50k 100k 200k avg.
Adam
28.5 25.5 24.2" 26.7
Adam-Wis Win 26.7
25.0 24.0 25.2
Table 6 shows that under different training steps. our accelerated Adam- Win always achieves lower test PPL than the official Adam optimizer. Spefically, it improves 1.5 average test PPL over Adam on the three test cases. All these results are consistent with observations vision tasks, and they together demonstrate the advantages of our accelerated algorithms.
6 CONCLUSION
In this work, we adopt proximal point method to derive weight-decay-integrad Nesterov acceler- ation for Adam W and Adam, and extend it to LAMB and SGD. Moreover, we prove the convergence of our accelerated algorithms, i.e. accelerated AdamW, Adam and SGD, and observe the superior- ity of the accelerated Adam-type algorithm over the vanilla ones in terms of stochastic gradient complexity. Finally, experimental results validate the advantages of our accelerated algorithms.
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGE
Xingyu Xie was supported by National Key R&D Program of China (2022ZD0160302) and the National Natural Science Foundation of China (No. 62276004).
REFERENCES
Kwangjun Ahn and Suvrit Sra. Understanding nesterov's acceleration via proximal point method. In Symposium on Simplicity in Algorithms (SOSA), pp. 117-130. SIAM, 2022.
Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. arXiv preprint arXiv: 1407. 1537, 2014.
Rohan Anil, Vineet Gupta, Tomer Koren, Kevin Regan, and Yoram Singer. Scalable second order optimization for deep learning, arXiv preprint arXhv:2002.09018 2020.
Rohan Anil, Sandra Gadanho, Da Huang, Nijith Jacob, Zhuoshu Li, Dong Lin, Todd Phillips, Cristina Pop. Kevin Regan, Gil Shamir, et al. On the factory floor: MI engineering for industrial- scale ads recommendation models. arXiv preprint arXiv:2209.053/00 2022.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint 1r12:0:112.02.66 2019.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridha- ran. Second-order information non-convex stochastic optimization: Power and limitations. In Conference Learning Theory, pp. 242-299, PMLR, 2020.
Nikhil Bansal and Anupam Gupta. Potential-function proofs for gradient methods. Theory of Com- puting, 15(1):1-322 2019.
Yoshua Bengio, Nicolas Boulanger-owwaddowski, and Razvan Pascanu. Advances in optimizing recurrent networks. In 2013 IEEE international conference on acoustics, speech and signal pro- cessing, pp. 8624 8628. IEEE, 2013.
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. In Proc. IEFE Conf. Computer Vision and Pattern Recognition, pp. 9650-9660, 2021.
Augustin Cauchy et al. Méthode générale pour la résolution des systemes d' d'équations simultanées. Comp. Rend. Sci. Paris, 25(1847) (5(1847):536-538 1847.
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, 2021.
Ekin Cubuk, Barret Zoph, Jonathon Shlens, and Quoc Le. Randaugment: Practical automated data augmentation with reduced search space. In Proceedings of the IEEE Conference Com- puter Vision and Pattern Recognition Workshops, pp- 702-703, 2020.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G 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.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929 2020.
Timothy Dozat. Incorporating nesterov momentum into adam. 2016.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal Machine Learning Research, 12(7), 2011.
10

---

Published as a conference paper at ICLR 2023
Jia Deng; Wei Dong; Richard Socher; Li-Jia Li; Kai Li; Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp- 248-255 205, 2009.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms of the adam family and beyond. arXiv e-prints, pp. arXiv-2104, 2021.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor opti- mization. In Interattional Conference on Machine Learning, pp. 1842-1850. PMLR, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Junhyung Lyle Kim, Panos Toulis, and Anastasios Kyrillidis. Convergence and stability of the stochastic proximal point algorithm with momentum. In Learning for Dynamics and Control Conference, pp. 1034-1040 1047. PMLR, 2022.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization, arXiv preprint / 2014.
Liyuan Liu, Haoming Jiang, Pengeheng 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, 2019.
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 IEEE/CVF International Conference on Computer Vision, pp. 10012-10022, 2021.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. International Confer- ence on Learning Representations, 2018.
Liangehen 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 of english: The penn treebank. Using Large Corpora, 273, 1994.
Jean-Jacques Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société mathématique de France, 93:273-299, 1965.
Zachary Nado. Justin M Gilmer, Christopher Shallue, Rohan Anil, and George E Dahl. A large batch optimizer reality check: Traditional, generic optimizers suffice across batch sizes. arXiv preprint ar 102.063502 2021.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87, Springer Science & Business Media, 2003.
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
Boris T Polyak. Some methods of speeding the convergence of iteration methods. Ussr compu- tational mathematics and mathematical physics, 4(5):1-17, 1964.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv
preprint arXiv: 09237, 2019.
Tong Zhang Rie Johnson. Accelerating stochastic gradient descent using predictive variance reduc- tion. In Proc. Conf. Neural Information Processing Systems, pp. 315-323, 2013.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathemat- ical Statistics, 22(3):400-400 1951.
Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5):877-898, 1976.
11

---

Published as a conference paper at ICLR 2023
Tara N. Sainath, Abdel rahman Mohamed, Brian Kingsbury, and Bhuvana Ramabhadran. Deep convolutional neural networks for LVCSR. In ICASSP, pp. 8614-86111 8618. IEEE, 2013.
Jürgen Schmidhuber, Sepp Hochreiter, et al. Long short-term memory. Neural Comput, 988: 1780, 1997.
Ily Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. In International conference on machine learning, pp. 1139- 1147. PMLR, 2013.
Tieleman Tijmen and Hinton Geoffrey. Lecture 6.5-rmsprop: Divide the gradient by run- ning average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 4, 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 Machine Learning, pp. 10347-10357. PMLR, 2021.
Ross Wightman, Hugo Touvron, and Hervé Jégou. Resnet strikes back: An improved training procedure in timm. arXiv preprint arXiv22110.00476, 2021.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. Advances in neural information process- ing systems, 30, 2017.
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.
Xingyu Xie, Pan Zhou, Huan Li, Zhouchen Lin, and Shuicheng Yan. Adan: Adaptive nesterov momentum algorithm for faster optimizing both enns and vits. Axriv, 2022.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song. James Demmel, Kurt Keutzer, and Cho-Jui Hsich. Large batch optimization for deep learning: Training bert in 76 minutes. In International Conference on Learning Representations, 2019.
Weihao Yu, Mi Luo, Pan Zhou, Chenyang Si, Yichen Zhou Xinchao Wang, Jiashi Feng, and Shuicheng Yan. Metaformer is actually what you need for vision. arXiv preprint arXiv:2111.11418, 2021.
Weihao Yu, Chenyang Si, Pan Zhou, Mi Luo, Yichen Zhou, Jiashi Feng, Shuicheng Yan, and Xin- chao Wang. Metaformer baselines for vision. arXiv preprint 1rXiv:2210.13452, 2022.
Sangdoo Yun, Dongyoon Han, Scong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy train strong classifiers with localizable features. Proceed- ings of the IEEE International Conference on Computer Vision, pp. 6023-6032 2019.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive meth- ods for nonconvex optimization. Advances in neural information processing systems, 31, 2018.
ZhngyiZhang,
Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2018
Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint (rXXi:/808.006711 2018.
Pan Zhou, Jiashi Feng, Chao Ma, Caiming Xiong, Steven Chu Hong Hoi, et al. Towards theoreti- cally understanding why sgd generalizes better than adam in deep learning. Advances in Neural Information Processing Systems. 33:21285-21296, 2020a.
Pan Zhou, Caiming Xiong, Richard Socher, and Steven Hoi. theory-inspiree path- regularized dif- ferential network architecture search. In Neural Information Processing Systems, 2020b.
12

---

Published as a conference paper at ICLR 2023
Pan Zhou, Caiming Xiong, Xiaotong Yuan, and Steven Hoi. A sieory-driveen self- refinement method for contrastive representation learning. Neural Information Processing Systems, 202
Pan Zhou, Hanshu Yan, Xiaotong Yuan, Jiashi Feng, and Shuicheng Yan. Towards understand- ing why lookahead generalizes better than sgd and beyond. In Neural Information Processing Systems, 2021b.
Pan Zhou, Hanshu Yan, Xiaotong Yuan, Jiashi Feng, and Shuicheng Yan. Towards understanding why lookahead generalizes better than sgd and beyond. Advances Neural Information Process- ing Systems, 34:27290-27304, 2021c.
Pan Zhou, Yichen Zhou, Chenyang Si, Weihao Yu, Teck Khim Ng, and Shuicheng Yan. Mugs: A multi-granular self-supervised learning framework. arXiv preprint arXiv:2203. 14415,, 2022.
Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvornek, 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.
13

---

Published as a conference paper at ICLR 2023
APPENDIX
The appendix is structured as follows. In Appendix A, we provide more details of LAMB and Win- accelerated LAMB. Then, Appendix B provides more experimental details, such as hyper-parameter settings of the four accelerated algorithms and the official data augmentations. In Appendix C, we define some necessary notations for our analysis. Then Appendix D provides some auxiliary lemmas throughout this document. Then Appendix E presents the proof of the convergence results in Sec. 1, i.e, the proof of Theorems and 2. Finally, Appendix provides the proofs of some auxiliary lemmas in Appendix D.
A MORE DETAILS OF LAMB AND WIN-ACCELERATED LAMB
Here introduce more details of vanilla LAMB (You et al., 2019) and our Win-accelerated LAMB. Specifically, Algorithm and respectively summarize the algorithmic steps of LAMB and Win- accelerated LAMB.
B
MORE EXPERIMENTAL DETAILS
Due to space limitation, we defer the experimental details, such as hyper-parametts settings of the four accelerated algorithms, and their official augmentations in (He et al.. 2016) and (Wightman al., 2021), to this section.
For accelerated algorithms, including AdamW-Win, LAMB-Win Adam and SGD- Win, always share the default optimizer-inherent fh is always 2x larger than its conservative step T/e for all iterations, i.e. n 2mp. For AdamW- Win, LAMB-Win, Adam-Wing Win, their first- and second-order moment parameters 31 and 33 are set to the default values 31 0.9 and B2 0.999 used in Adam LAMB and Adam. For LAMB- Win, its other key parameters, such as "grad averaging" and "trust clip", also adopt the default ones in vanilla LAMB. For SGD-Win Win, it uses the default momentum parameter 0.9 and set dampening parameter as 0.0 used vanilla SGI).
parameersssstesss of the vanilla optimizers and its reckless step
Algorithm 2: LAMB in (You et al., 2019)
Input: initialization æt = 2o O, step size (Te, ii)) moment parameters (Bi, B2). Output: uniformly seleted from (axx {
while k < T do
gs 1 -i=1 Vz(zni (i)
Σ
m, (1 81 m + Bigk
my 90 +/ /* Uo 9 +/
Uk
32 1 -1 + 329
|| l2
Vortu + Xoxx)
ma// / w/ +u+ Amull2
Tk+1 Db
26
end while
Algorithm 3: Win-Accelerated LAMB
Input: initialization 2a 2o O, step size {(n,, 7h Th) moment parameters {B1, B2).
Output: (i. 2) uniformly seleted from { 21) 1T
while < do
gx = ; / Vf(zz; Gi)
m, (1 B1 m + Bigk
/ m. 90 *
U2 = (1 - 32 12- + 329
/ * vo = g *
uy my mm//vun uu
|2 122
ms
\L.Ftt)
Øk+1 I+Aam (x) 176 Ubx where d here
Zk+1 Tk+ + Th (Zk- 7) ux with m A
and A = 0 here
end while
14

---

Published as a conference paper at ICLR 2023
Settings ResNet18. Here we follow the conventional supervised training setting used in ResNets (He et al., 2016) and evaluate our accelerated algorithms on ImageNet (Fei-Fei, 2009). For data augmentation in (He et al., 2016), it uses random crop and horizontal flipping with prob- ability 0.5. For warm-up epochs, for all four accelerated algorithms, we set it as 5.0. For base learning rate, we respectively set it as 3 x 10-3, 5 10-3, 3 x 10-3, and 1.2 for AdamW-Win LAMB-Win, Adam-Win and SGD-Win. Moreover, we follow the default setting and use cosine learning rate decay. For weight decay, we respectively set it as 5 10 2 5 x 10-2, 10-6, and 10-3 for Odamm-Wing LAMB-WIL Win, Adam- Win and SGD-Win. On ResNet18, 8, all algorithms are trained for 90 epochs with minibatch size 512 by following the conventional setting.
Settings on Res For these two networks, we use "A2 training recipe" in (Wightman et al., 2021) to train them, since this training setting uses stronger data augmentation and largely improves CNNs' performance. Specifically, the data augmentation in (Wightman et al., 2021) uses random crop, horizontal flipping with probability, Mixup with parameter 0.1 (Zhang et al., 2018), CutMix with parameter 1.0 and probability 0.5 (Yun et al., 2019), and Randent (Cubuk al., 2020) with M- = N, = and MSTD = 0.5, Moreover, it often use binary cross-entropy (BCE) loss for training.
On both ResNet50 and ResNet101, for base learning rate, we respectively set it as 2 3 8 10 3 1 x 10 3, and 0.8 for Adam ShlumW-Wir Win, LAMB- Win, Adam- Win and SGD-Win. Moreover, we follow the default setting and use cosine learning rate decay. On both ResNet50 and ResNer101, for weight decay, we respectively set it as x 10-2 2 x 10-2, 10-5, and 5 x 10 for AdamW-Win, LAMB- Win, Adam-Win and SGD-Win. On both ResNet50 and 101, for warm-up epoch number, we respectively set it as 5, 10, 5 for AdamW-Win, LAMB-Win Adam-Win and SGD-Win.
Settings on ViT and PoolFormer. We follow the widely used official training setting of ViT's (Tou- vron et al., 2021; Yu et al., 2021). For this setting, data augmentation includes random crop. horizon- tal flipping with probability, Mixup with parameter 0.8 (Zhang et al., 2018), CutMix with parameter 1.0 and probability 0.5 (Yun et al., 2019). RandAugment (Cubuk al., 2020) with M = 9, N and MSTD = 0.5, and Random Erasing with parameter p 0.25. For training loss, we use cross entropy loss.
On both ViT-S and ViT-B, for base learning rate, we respectively set it as 2 x 10 3 5 x 10 1 x 10-4, and 0.8 for AdamW-Win LAMB-Win, Adam-Win and SGn-Win. Moreover, we follow the default setting and use cosine learning rate decay. On both ResNet50 and ResNer101, for weight decay, we respectively set it as x 10 22 2 x 10 3 10 and 5 x 10 4 for Adam Win, LAMB- Win, Adam--Win and SGD-Win. On both ResNet50 and ResNet101, for warm-up epoch number, we respectively set it as 5, 60, 30, 5 for Adam Haam--Win, LAMBB Win, Adam- Win and SGD-Win. For Adam Win, following the default setting in Adam W. its minibatch size is 1024 for VIT-S and 512 for ViT-B. For all other accelerated optimizer, their minibatch sizes are always 1024.
Settings on LSTM. On LSTM, for base learning rate, respectively set it as 1 x 10-3,1x 10 1 x 10-2, and 15.0 for Adam Win, LAMB-Win Win, Adam- Win and SGD-Win. Moreover, we follow the default setting and divide the learning rate by 10 at epoch 100 and 145. For weight decay, we respectively set it as 2 x 10 2, 5 x 10 1.8 x 10-6, and 2 x 10 for AdamW-Win, LAMB-Win, Adam-Win and SGD-Win. We do not utilize the warmup strategy in this experiment. Following the default setting, we set minibatch size as 20.
Settings on Transformer-XL. On Transformer-X XL. for base learning rate, we set it as 4 10 for Adam- Win. Moreover, we follow the default setting and use cosine learning rate decay. For weight 6 for Adam-Win. For warm-up steps, we set it as 2000. Following the default setting, we set minibatch size as 60 x 4.
decay, we set it as 10-6
Test accuracy curves of SGD-Win and Adam- Win on ResNet18. Here we investigate the con- vergence behaviors of our accelerated algorithms and hope to explain their better test performance over their non-accelerated counterparts. In each sub-figure pair of Fig. 1, we plot the curves of train- ing and test losses along with the training epochs on ResNet18 and ViT-B. One can find that our accelerated algorithms, e.g. AdamW. W-Win, show much faster convergence behaviors than their non- accelerated counterparts, e.g. AdamW. Moreover, SGD-W Win also converges faster than Nesterove- accelerated SGD, i.e. SGD-M. We also plot the curves of test accuracy in Fig. 2, showing the superior convergence speed of AdamW-Win and LAMB-Win over their corresponding non-accelerated ver- sions. Fig. 3 in Appendix B also reveals SGD-Win and Adam-Wii enjoy faster convergence than
15

---

Published as a conference paper at ICLR 2023
Test Top-1 Accuracy
70
SGD-M
SGD-Win
65
Adam
60
Adam-Win
55
50
45
30
60
90
Training Epochs
Figure 3: Test accuracy curve of SGD-Win and Adam-Win ResNet18. See the curves of AdamW- Win and LAMB- Win in manuscript.
their non-accelerated counterparts in terms of test accuracy. So these faster convergence behaviors could contribute to our accelerated algorithms for their higher performance over non-accelerated algorithms under the same computational cost.
C
NOTATIONS
Here first give some important notations used this document. For brevity, we let
8k v Uk + v.
Since have || Coo and brevity, let
100 + 11 S doe + in Lemma 3 (see Appendix D), for
= 0.5 < <11881000 S:2 = (c + 100.5
Also we define
my
A 8k
fJk
Wi
wi == my + AE 8k.
2x+1
3g
+ A
Sb.
1 + A Sy
Next, introduce virtual sequence {yR} into the algorithm. In this way, rewrite the update steps in Algorithm in the manuscript as its equivalent form (12):
gk 1o Σ Vf(zzi Ci);
my = (1 Bg m + Bighi
Uy = (1 - -2) + :2g
(12)
Øb+1 I+Aen Otx 17k mi
ys+1 2/- 7h
2k-1 T& 7/ Th9k+1
where mg = and Ug = gō- For analysis, we further define
A |00 [c([((:))] +
A 2
Fe(Ox) F(0)
1012
(13)
where 2₂ X(1 - = which μ proofs.
2 In the following, we mainly use these notations to finish
D AUXILIARY LEMMAS
Before giving analysis, we first provide important lemmas.
16

---

Published as a conference paper at ICLR 2023
Lemma 3. Suppose the sequence {Ek: yk, zk} are updated by Eqn. (12).
That is, 3k++1
1
Ii 1K ex yk+1 21 7) ma 2x+1 T4TT + Tb-1 = vux + V.
1+Aame
Then {m,,; 8x)} satisfies Assume C2 I 11 S Coo, then we have
mm S Coos |0 + viloo S c0x +v,
32c
S
8k
< 1 +
B2c
2(c2 + v)
8k+1
2(c + v)
See its proof in Appendix G.I.
Lemma 4. (Xie et al., 2022) Suppose the sequence {ær: yk 2b3 are updated by Eqn. (12). That T]
is, kk-1 I-denE Ikk
mak
yk++ 2xz
17 ox 1k+1 T1+ + Tktkkk+ Sk
ax
v U/ V. Then } satisfies
E mm [F(=))11]
(1 - 31
$902
<(1 B1)BB | (F(( 1)1
E || =x-11?]
31
b
Lemma 5. Suppose the sequence {ox: yk. 2x} are updated by Eqn. (12). That is, 0k+1 =
14 3g ?} # yk+1 2k `e at 2k+1
mi
me
7e T&+ + MeTKyK++. 8h = vok +
By setting Mi
17. πi f7. $1,k $1 and B2,8 B2, then we have
1 カ-1 11
uk+1 (1 Ab77) xx+1 = pk+1
P++1 1 Aum 8;
==
k
1
wi
1ye+1 - (1 x1 Sp
11
Pitz - 17T + der))
8;
1=0
|zx+1 - 22+111 - STMPh+11100 7)2
wi
Pit1 - 1)( + (mn)
1=0
||++11 - =xll2 5
27
Wk
(1 + )un))
8k
+ 1pk+1772 1jj-n)² 11) Aun)²
W
1=0 Pi+ 1): 1) + Am1)
where Pk+1 1PTk-1Pkk P1 = 1 and Po
See its proof in Appendix G.2.
Lemma 6. Suppose the sequence {Ik; yk Zx are updated by Eqn. (12). That is, 0c+1 =
I+Am Ø TJs 8x
más
Yk+1 2x πik Be
my Zu+1 = TTTTA + TETKyK+1 8% = /ux + V.
By setting Ii 1/, TJ "h B1,k 31 and B2 B2, then we have
21 - 2,
2090²
E mm VF(x+))1 =2(1-B1133 B1)E | [F(2
+ 2LII.
B1
where
T = (1 + da >
211²
Wk-1 1
+ (1) + d 17)
wi
8k-1
Pit1 (1 - 1) + Am))
1=
k-1
IT' :=7T--1P7((7 - 1)
wi
Pi+1 11 Xmn)a
8;
1=0
where Pk+1 = 1PTk-1Ph, P1 = 1 and Po =
its proof in Appendix G.3.
17

---

Published as a conference paper at ICLR 2023
E PROOF OF THEOREM 1
Proof. Recall our definition Fx((z)) F(z) + Av I [B(f(2;; + Ae I=
in the (13).
By using the smoothness of /(0: (), we obtain
(2+1(
L
Ac+1
<F(m)) + (VF( 2x+1 -0x)
|
axx11
11
2
2
{F(m)) + V F (rrs) Fk+1 xxn
L
|
x=x112+
Ax+1
| 11
2
2(1 - lr)
{F(())) + Ak | + (VF()))) + a 8k, 2k++
L
Ae
akk + 2
||08441
+
|
27
2
T7k
VF((x)) + A 8k: 8k
Ln
Wt
A
Wkk
I + Au
2(1 + >
8k
2(1 + >1TT)=
8k
(ark)
+
2 II (1+ )s
1
Uk
(VF(x)) AE * 8k wkk
2
1
T]
(V A * 8k.)
2
V (1
)sM))s
1
T/K
Lafe
Wkk
2
A
Wk
-2
2
(1 + Awmn)o
wk
2(1 + AuT)))2
8%.
2(1 + AuTTi)²
8%
<Fi (xx)) + 2c1(1 + ARTTS))
[VF(x)) m& 11
7
202 (1
77k
C2LTT
c27x.7k
||
202(1 )u.71))
c1(1 + \RTTN))
(xxn + (c1(1 + )aTTE)
17k
VF((xs) m. 11
7
|| Fu (xxa)l
7/
|
202 1 + ANTTK))
402(1 + A1.TK)
where holds since Lemma proves
ek #c+1
E [1 - 14, 1 p1
(vp E [0, 1]) which μ A203
Ac+1 and @ holds because ÀE= T-
[0 I
||ax 11, + |||0x1+11
=xl12 2(0241 Ik ax))a
3 holds, because
m. + AA.EE * 8kc
77
Wi
Wi = my + AEO 8k.
0k+1 2b
+ A
Sk.
1 + A Si
= 0.5 < 110 S : (c30 v)0.5
c((+))m)) such that ④ holds, since we set 77 I 20x(L+)ac1)
ea Lne (1++mmm))
+
e2 o2Ann e1(1-Amm))
S 1
From Lemma 6, by setting ?) 17, Tik and 31,t 31, we have
[[ Himi-VF(an V <2(1 31)E ( || -F
211 - B1)
28
+ 2LIT,
B1
(14)
where
11
217
Wk-1
+ - 2 + d x
w
(1 + du 1x)
8k-1
Pit1 (1 - 11Ti-1) (1 + den)
8:
k-1
11 :=77-1Ph7777 - 2)
Σ
wi
Pi+t
T/T, (1 + A.n)²
8;
1=0
(15)
18

---

Published as a conference paper at ICLR 2023
Here P&+1 1/7k-1Pks P1 and Pu 0. By considering C2 ||sk|1o 2 c1, have
217²
2p 2 + XB- xx-1
11. 11 := cf(1 + 17))
|w
Pi+i (1 177- 1) + Acn)a lw,l|
I S Mi Tk- PM- 11)
k-1
17T(-1)(1 + Xmn)² /w,11
1
ct
Pit1(1
(16)
Therefore, by plugging the results in Eqn. (14) into the upper bound of 12+1((044) we have
Fx+1(I
<Fb( 202(1 + AuTI
17
(xx))1
7
||/x112
4c2(1 + Aun)
+ 1/(1 - -31)
+ nlIx (1 - 331)2
n1900
+ nLLK
|| VF(* [
+
c1(1 + Xun)
c1 + XxT)
ci + Aum)
c1 + Aum)
S (xx) 202 1 + AuT)
r7
[xx()= 4c2(1 + Av7)
7
||wn|1
+ 111 - 31) E | - 1)
nIIx (1 31)
n3f0²
nLLi
+ a + AxT)
+
c1 + Aujjo
a. + (un)
(17)
where @ uses the fact that Ak S A. Then, from Lemma 4, we have
mm - VF(Ex)]]
(1 (1-3:)2
3902
<(1 - B1
|| - (F(=
|| 2k
1111
(18)
Bi
b
(1- L
+ B800
5(1 31 E
| VF(= +
B1
where we use the results in Lemma 5 that
1z 2 <IT S IT.-
Then we add Eqn. (17) and ax (18) as follows:
Fx+1(0041) + aE
|| - [=(x))11
<FA(#x)
17
[Vb((=>)11
27 4c2(1 + \un)
||
202 + Aun)
1yTTx(1 (1- 11)
1/3f02
(19)
+ (1 - (1))
11 +a a
[[ -F
+
c1 + >an)
c1
+ Am7)b
nLi
a(1 - LL
a5f0²
ci (1 + Axn)
Bi
19

---

Published as a conference paper at ICLR 2023
Then by setting a = -((-91) and (x+1(1x+1) =k++1(kk+1 (2++1)+ -لا
||m - VF(x))]1?
c
c
[x[f(2: 5) + dt || + v(1-81)
m - VF((x)) |2] E
we can obtain
GR+1(TR+1) <G((TE))
11
F (xx)))
71
||
202(1 + Ax7))
402 (1 + 2xT))
n114(1 32)
nLL1
+
01 + Ax.1)
c1 (1 + Aun)b
c1 + Aun)
+ 711 - L
7(1 B1)310²
+
c1
c₁b
<Gx(#a)) 202 + Ax:)
"1
[V (xx)
7
||20||1
402 (1 + XuT)
+ ( - L1
nLLi
+ 1310²
+
(1 + ART)
cib
where ① uses the fact that 0 A S A. Then summing the above inequality from k = Oto T-1 and using < As S À give
[[F + =11021??
E
20 + Xn)
2023102(14 Xn)
2028702
(G(z)) G((rT)]
1/l
bbT
c1b
2c 22 An))
T-11
20 T-1
II
+
I1I
c1,TT
eT k=
k=0
202 + An) A
202310² + An))
202 21 - 3.) +1+ Xn)
202 L
T-1
+
π +
nT
b
T
c T
k=0
k=0
where
G(æo) G(ær)
=Fo(zo) + 11(1 - -81)
Fr((r)) 1711 -31) E
E |lm (F(x
|
V VF(
31
31
1/(1 B1)
=F(xv) + Au |2ooll.. F(or) - dx ||
E
| - VF(xT-1)11)
<F(#p) F((T)
<A
20

---

Published as a conference paper at ICLR 2023
where A = F(xu)= F(x.): ): x-1 and m- two virtual points which satisfy m..1 VF(x=1).
Now we try bound Σx= 11g and Σ 1lg. Firstly, we have
T-1
21
2p R1) + 2k- X k-1
1
Σ
l20k111"
+
|20 |20
Gi + Ak- >x-17)2
of
Pit1 (1 11 + \nn)
k=
k=0
2
2772 1)
T-1
1
| 112)
PkTR- (1 + 1
2
1200 1
&
Pi+i -1 X1T))²
k=0
27
27 (n 11)
T-1
T--1
||20 1
Σ
PETi 1 (1 X
ot
Pk+1 (1 - 17Th 1TTk-1) + Axn))
n7 (π) - n)
T-1
T-1
1100
2
|
Σ P
G( - 177)
Pk++
i=k
2n²
2a 2 1))
|1:00-111 11
| 1|
cin(1 1/)2
8 217
2a - -
T-1
[ 13
| [1]
cip((1 - )7)
27
T-1
[1 a (1+7)(7 - 1)
Σ
|| ||ax ||00-
k=
27217 [1+a2g8]]
Σ
||
&
where @ holds since 0 S A S x; @ holds, since 1) for i 2 k we have 1+A:-17 1+
1-he-10
1-\xn < 1then 11 177 I I4(1-MA = - and 2) 1- t+ 1
+ イ+ト1ー1
11 S
カ+
1 1- whose minimum is at A 0 and n+
@ holds, since ET- Pst.-1
+ Pi-IT:-1 < 1 E P4t1 < _ (1-1 T+ -
+p @ holds by setting v = 77)-
1-
mrj
Similarly, we can bound
T-1
Σ m
1P
- 7)2
k-
Σ
Pi+1 11 + A27)2 ||m/|1?
k=
k=U
1=0
[ 7) 2
T-1
|w:11
21 T/T)
Pk
Pit1
Tn - 7)
T
|=
-T-1
c1(1 17T)
1= Pi
Pk+1
( - 1))
n7222 - 1)2
17
1)2 T-1 k=
|| |?
| <
|
G 1772
c2(1 + 7)2
o
k=
k=
(20)
where @ holds since 1) Pk+11 = 1fTk-1PP 1Pk 1T and P1 and 2) ET-1 Pi
1-77
Ch which together give pt-1
1
E Pi
<
Pk. < W7
I- S |
Therefore, we
ph+1
1-7
21

---

Published as a conference paper at ICLR 2023
have
E
[VF(( + /
T
K=0
[1 + A
2023102 Xn)
1/T
6/b
2
(1 B1) (22))22( + (1) + )2
117]
202n2 2 1)2
| 11²)
1/8T
G7
k=0
20 A
2023102 + Xn)
1
T-1
||
1/T
c/b
47
R=
where ① holds since choose proper 7) and 81 such that
402721/² 11) X1) + a279)
c
(21)
2021 2 1,7- - 1)2
S
69
where @ uses -04x)1)2+x>)
19-
< 1 $1 1 +
mm 1) and @ uses
< T. Now select
(1431
(1+7)4
7 and 31 such that (21) holds:
c1.531
ct.
S min
4V/c0-57711 L1) 10)00 (1 10.5 1)
So arrive
1 T ΣE
1
202(1 + +n)
202 + An)o²
E
//
?
(22)
T
n/
c
where we set T
1o2(1+Ani y1²
and 31 S
This result directly bounds
T-1
17
1
||
(xx
2x
| + Axx sxll?
T
T
XRT)²
k=0
[ux 1| 111262
A=0
Moreover, from Lemma 5, we have
k-1 Σ
1yk (1 As-1 x
2
1
(π n)
1
Wi
II
T
Pi+1 (1 1)7,-1)(11111 A,1)
8,
T
k=
1=0
R=
T-1
1 2nll²
Th- Pp-((1
11)2
w;
II
T
Piti - -)TT() (1+ + 2x17)2
8;
A==
Σ
| - 2xl1
T
2172
+ 2p - 72 + A
wk
T
(1 + Aun)2
Pi+1 (1 T/T (1 + 2
8y
k=
k=0
1=1
where Pk+1 = 7T P1 and Po = where ① holds by using Lemma 5; @ holds by using the definition in Eqn. (15); @ holds by defining:
IT :ū 7)
Σ
1
wi 8;
Pst1(1 (1 - 1)1--1)(11 + 2
O=0
22

---

Published as a conference paper at ICLR 2023
Now remaining task is to upper bound + E Ik E Ir and + Ei= m. Here we first
bound? T'
- my by using almost the same proof in Eqn. (20):
1
Pk(
n)
Pit1(1 - 1) + A17)2 1120:112
T
k=0
k=0
< (ī) 7)?
T-1
(17 - (1)
1 11
T
Σ
||wx:1?
Σ
1 cf(1 1T
c[(1 177 VT
1=0 Di+1
Pk+11
k=0
A=0
i=
2
1)=
||/,/ll [1]
1 7/ - 1)²
Σ
| 11
1)2
|| |
cp (1 - )7
cp(1 7
Tf
h=
k=
1 01 1e2 C176? 2
1602L Ac2L
(23)
where ① holds since
1
2-0+ 189 = 14 + 107 S 11+7 1) IIーパ 11 whose minimum
71
1 1-1/7--1
2) E 1 Pi S (=(1-1) 7tō. holds since 1) Pk+1 = 1TTk-1pk S 1/TPk and f = and
at A = and r
T-pr which together give p+t1
1 E Pi 1 2 v
n
Px+1 1-
1 1-1 S ) holds by using 1) E wpll S 4e in Eqn. (22); 2) we use the results in Eqn. (21) to obtain
n 17 1)2
ct S C17
o7
16c2L(7- 1)2
16c2L
From the bound in Eqn. (16) and the following bound on + IT ll and + E lig we have
+ ,
T i
2
[1
2
T-1
S
ci
GT
4cz LL) Xn)
K=
k==
T-1
1' - 1)2 7-11
| 2 4e2L
E
T
GT
K=
k=
k=
where @ holds, since 1) T Σ
T Ellux|11 < <4c2:2 2) we use the results in Eqn. (21) to obtain
27 2
27²
c1
[1 [1 ++
S 2
[1 + 117
32027 - 31) + (1) + 2273) S 16cz(1 - (,)2 (1+2(11+1)) +n)
of
1p(7 - 1)2 of
(7 11-1) 1)2
aî 16czL(7 112 S Ca
16
Therefore, we have
T-1 El (1 + Xx))xx11 < c1ne?
T K=
4crL'
E || -xx12 CIE2
40zT.
1 T-1
c1
Σ
E ||
- =zal2 -
T k=
4c (1 - (1)+
23

---

Published as a conference paper at ICLR 2023
Besides, we have
1
E
m2
AR.OR * sk VF(x)) AR. * sx sxl?]]
T
m + A = sxl12 + [V + AR. * Sx
T
2
|| + ARaEE * 8xll² (
E
T
k=U
3
2
e²
+
4e
8
4
where in we use 20 = mz + \I.
Sk. In this way, we have
2 T
I+ VF(2+)11
-
Σ
E
|
VF(xx))1
(IVF((m)))))) - V=(2)))
T
k=0
21, T-1
$16c²
Σ
E
||00 - 2x|l
T
k=0
LE
(c,L + 322222
<66c +
2
202
202
For all hyper-parameters, we put their constrains together:
be
be
B1 S 4c2(1 + An)o²
0
C202
where = 055 < 1/5//l00 S (c2 + +1) = =
For 17, it should satisfy
53.
c
(1 + xn))
v) S min
4v2c0.3 (1-))=((11B (2
10.67 1) 20 L + Xc1)
Considering Anj <<< 1, I+[1-A]A1
1+An
I-p f is constant, and C₁ = v0.5 <<< 1, then we have
cl..31
1
1 50 min
2..5,,255
c
0
0.5
L2L
bE2
)
=0 min
=
c
L0 L03
cJ
where v is often much smaller than one, and 31 is very small. For T, we have
T 40 An)
2
o
1122
2
2.5 2 25
LA
=0
2
y1.25
Now we compute the stochastic gradient complexity. For T iterations, the complexity is
[c2 2,5 y1 v1.25
O (Tb) =0
The proof is completed.
24

---

Published as a conference paper at ICLR 2023
F PROOFS OF THEOREM 2
Proof. Recall our definition Fi = 0()) +
Av = c)] + d 1 in the (13). By
2
setting 8 1 $1, then we have mm 0c I Coo by using Lemma 3 (see Appendix D). Also define
WR: = my Aark:
0k++1
(ms Xaxs) 1 ArR
T
wkk
+ ArI
Note in the following, we set all dE X. By using the smoothness of ((0:C), we can obtain
Fx+1(
A
<F((x) + (VF((x)) 02+1 - xat + | - æx 2
||
2
L
{F(x)) + 2 I (VF(xx)) + Awa, #k+1 x&) +
|
xxl
+ 2
| - xx.1
2
=F(((r))
Tjk
(VF( + A wE) + 2(1 + Ama))
LAf
|,/||1
+ 2(1 + XTI))2 |201|12
X
I + Ark
)2
1
2
-ax( +
(VF( + AaFE - wn)
(VF(xx) + )
V (1 + Amp)
2
(1 + AT1))
2
LafE
XvI
IV (1+ )
Wk
2(1 + \TT1)2
|///||
2(1 + \Tp))
||2x|||
(Fo()))) + 2(1 = )mT)))
VF(xx)) mx
7/
2(1 + Am1A)
17k
1
Lmpe
AMR
||002|1
2(1 + AmTi))
(1 + (Tp))
(1 + Amx)
(F() + 2(1 + )mpk)
7
VVF(2x) mmxll
7k
77 4(1 + Ank)
|
2(1 + Ampe)
where ① holds because
| 11 = | + |||2 - wa wxll 2(x 2kg a2)aa
holds, because
7
17k
Wy m& + AZEe
Øk++1 Tb
(m² xxxx)
1 ArR Wk-
+ Amp
holds, since we set Vik
c 2ex(L+xX11
such that co Lap
coAne (1++A))))
c[(+Am
Then in the following, we can directly follow the proof of Theorem 1. This is because the only difference between accelerated SGD and AdamW that SGD has no the second-order moment Vü while AdamW has. By let SGD, then they share the exact the same updating rules. So after setting 3 = 33, in accelerated SGD, to follow the proofs of Theorem 1, only need to verify whether the auxiliary lemmas and the proof process of Theorem 1 hold for 8% = 1. This is the true case. Please check our auxiliary lemmas, including Lemma 3 ~ 6, and the proof process of Theorem 1. Consider s
1 in accelerated AdamW and setting 8 = 1 B1 in accelerated
in accelerated SGD, we have 4 = 1 S | loo S 1
In this way, by setting 7h - 1, m== = 0 ( 81 5 le =1 d =x,
Ao 0, after T O bet iterations with minibatch size b and A F(x.) F F(x.), the sequence {(zg, = generated by accelerated SGD satisfies the following four properties. a) The gradient FF((,)) (#x) of the sequence {mx)²- can be upper bounded by
|| + Au se? b) The gradient moment my well estimate the full gradient (( and VF(zk):
1
k=o E
(zx
T
m+ - VF(x*)]l3,E El - VF(=))]2 (16 + 2
2 2))²
max
T
25

---

Published as a conference paper at ICLR 2023
c) The sequence (æk; 2x} satisfies
3
2
Ell us 2x113] S An
4(1-Bi
3322
4L
2.5
d) The total stochastic gradient complexity to achieve the above three properties is O The proof is completed.
G PROOFS OF AUXILIARY LEMMAS
G.1 PROOF OF LEMMA 3
Proof. To begin with, we assume that Vt S kt it holds
||melloo S Coo.
+ tlloo S Coc +
Then we consider the case where t= k + as follows
m = [I(1 m1) + Bigsle 2mx0 S (11- B1) || + 11 Coo
| = [[(1 - 82)0xx + B2g llo S - 32) |
+ 33 11 S cgo.
Then we derive the second results as follows:
I
1+ (2 g
Uk
Uk+1 uk+1 +
1
Uk+1
Uk+1
Therefore, have
B20
32cB v
Uk +v
By 2
32c
1
$1
1
2(c2.00 + v)
Uk-+1 +
8,00 +
( + +2)
100
We complete the proof.
G.2 PROOF OF LEMMA 5
Proof.
To begin with, we have
yk+1 (1 + Dxk+1
7 my 1 + A
mi
=2k
36k
T7s
8%
1 + APTT
m.
+ AETT
mi
-fi - Db + 77 1 13
T7.
7]
8k
1 + A6TT
+ Au-TE-1
m.
d (1TK
7Tk)
1 (yI - (1 + A1-7)-1)a2
17ke
ICK:
1 + AA-TI
Sk
1 + 7
7h TT (yss (1 + A 1)0k)
+ AuoTI
17ss
we
A 0k
+ Au Au( 176
x
+ A
1 1 Au
+ A
w0
-1] 17--1 (yK - (1 + Ato
T]k
+ AA-7IK-
8k
+ +(Xeo (AoTH
1 AuTIK- Au7
+ An( 7Kk
I+ A6T1-1
1 + Au
1) we
- (yk (1 >bT))aK))
1 X 8%
where ① holds since wy == m& + d sk; @ holds since we set all and î fj which gives Tr * Therefore, by defining Pa++1 = 1/Th- Pt = and Po 0. then we have
yk+t (1 + AUm
yk (1 + A
1 1 Wk (k 2 1)
P
Pk
Pk+1 1 1 AR 8k
26

---

Published as a conference paper at ICLR 2023
For O, we have
mg
+ A
m0
y1 - (1 +
A1
=20
20
+ A07)
w0
00 * 3D
+ Anñi
400
An
=20
f]
17
1 Ao
80
1) Wo
=20 20
+ A0 80
In this way, one can obtain
uk+1 (1 AuT))
1J
W0
1
71
w;
=20 20
Pk+1
1 Xo
S0
Pi+1
1
8;
k
1 7) wi
1=0 Pi+1 1 1 AM 8
where hold since zu = zn and p1 = 1. Then we can upper bound
yk+1 (1
Σ
Pk+1 77-11)
Pk+1
Pit1
Pk+1 -1 -1ppi=-))( + (177)
8;
Pk+1 (1
-1TT-1))
(1 - n1=
W:
Pi+1
Pk+1 (1 12 + A
2
1=0
(1)
11)
1
Pk+1
i=0
Pi+1(1 17[ An7)
8;
where ① holds since 1) Ei=o Therefore, have
1-
E
1
1)
and 2) Jensen' incquality.
Pi+1
Pi-1
Di
pa+1
1k++1 (1+ Ax S Pk+1 n)² Σ
W:
Pit1(1 - 1/T 1) A
8;
Moreover, we can also bound
|#4+1 - Fk+1 2 = =1 1TT2U:+1 #x11
=nyck 11 101 +1+ ) 1|
STEP&+11(T 7)² Σ
Pi+1 17 + 2,7)
On the other hand, we have
||z 1A
1 1/ zx|l
m72
7 + 77Tkyk+1
yk+1
1)
W)
A * 8k
T + 77T78441
yk+l
17
8j
Wi
77 + 77T3/K+1 4k+1 1)
+ A
8
(7T + M7.004111 - (1 T7T 17
7
Wk:
+ A4.77 8%
@
7rx (1 + (MO)) ((1 >x.7) 1k++)
17
W0k
1 + Au
8%
77
Wkk
S177a( + AwT) [1 + A17)) - Me+ill +
1
8%
27

---

Published as a conference paper at ICLR 2023
where ① we plug in yc++1 = 2/ - 77s mak in
we plug in ab+1 = 1+
2 - mi
=
1+Ax0 ats - wh - A5 = 3y 1+ as
wk and we have 17TH +r7A = 17Tx (1
and (1 - -77x ) = 17Th (1 n/11). Then we can upper bound
| zx|1 T2 )wn)² (1 + Aco))=++111 yk+ill + (1 + )xn))
2rj
Wk
8kc
272²
Wk
+ 12k+110 (1))-1))- -2) + )
Wi
(1 + )
8k
Pi+1 (1 - -)) + Xm))
8i
The proof is completed.
G.3 PROOF OF LEMMA 6
Proof. From Lemma we have
E | [1
5(1 - B1,A)L || [| VF (F + (1 32,
1866-xx-110 11 + 89,002
[1 -
B1,k
I1 =21,)) 18,,002
<(1 B1 ||
F []]
B1,
where in @ the results in Lemma 5 that
= Zソ-1 <11
with
11
27
Wk-1 1
+ 2px (1 =1) 11))
W
(1 + A7)1
8k-1
Pi (1 mT: ()- + (xn))²
8,
Then have
mz - VF(x))11
<2E
|m - VF(zx)11
+2 VF(zz) VF(x))11
<2E
|m=
VF(xx)1?
+ 2LE ||
xx1l?]
4 <2
211, (1 BI,
2B9
BI, VIik-I-V(((--
21IT 3
31,t
b
where in @. use the results in Lemma 4 that
E |lm VF(++)1?
(1-
22
82 02,02
<(1 - BI,))B ||==-1- 1F(2
EE
|| 2k 111 112]
31
and also the results in Lemma 5 that
k-1
|| zx 2 < IT : - 7)²
Σ
w0
P++1 (1= - 1) + A
1=0
The proof is completed.
28


Reviews:
[{"review_id": "fUNtPwhhAj-", "reviewer": "Reviewer_hKYG", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a weight decay integrated Nesterov acceleration algorithm for Adam, AdamW, LAMB and SGD by adopting the proximal point method. It shows the convergence analysis, and perform experiments to validate the results. ", "summary_of_the_review": "It is a very well written paper. ", "strength_and_weaknesses": "Strength: The paper is clear and well written. It presents an acceleration algorithm and apply to Adam, AdamW, LAMB and SGD. It has both theretical analysis and experiments to support the claims. The idea introduced is nice.\n\nWeaknesses: \n1. Better to include more comparisons with other methods, such as the line search methods.\n2. To consider the s_k norm seems not necessary. What if s_k is partial, like 1/2? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "eNzG_ONkVn", "reviewer": "Reviewer_FLq8", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 provides a new analysis of combining weight decay and Nesterov momentum and applying it to several standard first order optimizers (SGD, Adam, AdamW, LAMB). The authors prove convergence, and then show that the new acceleration provides significant improvements on a variety of training tasks.", "summary_of_the_review": "The paper presents an analysis of combining weight decay with nesterov momentum. The technique has been applied to several different optimizers, and is easy to implement in practice. The experimental results show significant gains across a variety of ML tasks. ", "strength_and_weaknesses": "The technique presented is well motivated theoretically, and is straightforward to implement. The experiments are quite diverse and show promising improvements across the board.\n\nThe organization of the paper could be a bit better --- right now the authors present the fully general technique and then specialize it to various algorithms, it might be better to present the technique for various algorithms one at a time, starting with SGD, which is the simplest algorithm. \n\nThe combination of weight decay and Nesterov momentum has been applied in other optimizers already (LARS, Shampoo, several others).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RLPcF5o-Ws", "reviewer": "Reviewer_kZaA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work focuses on adaptive gradient optimization algorithms and attempts to provide practical insights for speeding up convergence with such methods. In particular, the authors proposed the Win method to increase the speed of convergence for adaptive optimization techniques. In particular, this technique incorporates a dynamic regularizer into the loss that is inspired by proximal point methods, which improves the convexity of the optimization problem. In addition to providing a convergence proof of the Win technique, the authors first implement this technique for Adam/AdamW, then extend the implementation to LAMB (i.e., technique for optimization with larger step sizes) and SGD. The authors provides convergence guarantees for this acceleration technique within the non convex settings, which matches known lower bounds and slightly improves upon the bounds achieved for baseline algorithms like AdaBelief and RMSProp. In experiments, the Win acceleration is shown to provide a very tangible benefit across a suite of different deep learning architectures, including CNNs, LSTMs, and transformers for both vision and language.", "summary_of_the_review": "To begin, I want to emphasize that this review reflects my current opinion of the work. I am completely open to discussion with other reviewers/authors, and my final score will be mostly based upon this discussion.\n\nMy initial thoughts are as follows:\n* The idea in this paper is unique and (in my opinion) useful to the community.\n* The empirical (and seemingly theoretical, though I'm less familiar with Adam-style analysis) support for this technique is very strong.\n* The presentation quality of the work is quite poor (especially Sec. 1, 3).\n\nI believe that if the authors improve the clarity of their discussion/presentation of the technique, the impact of this work will significantly increase. I do not necessarily believe poor writing is a reason for rejection, especially given the strong empirical/theoretical support for Win. However, I truly believe that spending time with improving the writing of this paper (and fixing the other details I mention in the body of my review) will increase this work's potential significantly.\n\nI thank the authors for their interesting work, and I look forward to the subsequent discussion!", "strength_and_weaknesses": "Strength:\n* The incorporation of the PPM regularization term with a recently-proposed formulation of nesterov-type acceleration is novel and seems to be useful. \n* There proposed Win acceleration can be added to several different types of optimizers (e.g., Adam, SGD, AdamW, LAMB).\n* The authors provide convergence guarantees in the non convex setting for their acceleration technique using both Adam and AdamW. These guarantees improve upon prior work to the best of my knowledge. \n* Experiments are performed on a wide variety of architectures (CNNs, ViTs, LSTMs, transformers). X-Win improves upon baseline optimization techniques in nearly all cases. \n* The proposed acceleration technique seems to reduce the need for hyperparameter tuning. \n\nWeakness:\n* The discussion of adaptive optimization techniques is lacking. It is widely recognized that adaptive methods suffer poor generalization relative to SGDM in certain settings (see “The marginal value of adaptive gradient methods in machine learning” and “Towards theoretically understanding why sgd generalizes better than adam in deep learning.”). This has led to research in alternative optimizers like AMSGrad, Yogi, M-SVAG, etc. The authors mention AdamW, but do not mention the rest of this work or sufficiently address the generalization ailments of adaptive methods. I think because of these issues, claiming that optimizers like Adam/AdamW are “default optimizers to train DNNs” is somewhat problematic/incorrect. SGDM is still the default choice for most computer vision tasks, where event recent adaptive algorithms like AdamW achieve inferior performance. \n* The description of the proposed method (especially in the introduction) is lacking in clarity. I believe the paper could be greatly improved if the authors spend time to improve the clarity of these initial explanations of their technique. \n* No discussion of how the computational complexity of the proposed method compares to the other methods (maybe I missed it?). You need to state this comparison, do we incur extra cost by adding Win?\n\nSmall stuff:\n* Small writing errors: beginning of Section 3 (“accelerating and also stabilizing optimization”, “At below”), end of section 3.1 (shouldn’t “bias correlation” be “bias correction”?).\n* Putting AdamW, Adam, and LAMB variants all into Algorithm 1 is a bit confusing, though I’m not sure if there is a better way to present this. \n* It is not completely clear to me from your description how Win+LAMB compares to vanilla LAMB. Making this comparison a bit more directly would be helpful in my opinion. \n* It is a bit weird that Table 1 appears after Table 2 in the writing. \n* For the loss plots (Fig. 1), I’m not sure whether your method actually converges faster, or if it simply converges to a better loss. In some cases, the convergence does appear to be faster, but in others it converges at (seemingly) the same to a better loss. It would be helpful to provide a similar plot with some of the other baseline optimizers (e.g., PAdam, RAdam, Adabelief, etc.) if it is does not require too much extra effort. ", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%