Momentum Centering and Asynchronous Update for Adaptive Gradient Methods
Authors: Juntang Zhuang
Yifan Ding
Tommy Ming Tang
Nicha C Dvornek
sekhar tatikonda
James s Duncan
Venue: NeurIPS 2021 Poster (2021)
Keywords: momentum centering
asynchronous update
adaptive optimizer

Abstract: We propose ACProp (Asynchronous-centering-Prop), an adaptive optimizer which combines centering of second momentum and asynchronous update (e.g. for $t$-th update, denominator uses information up to step $t-1$, while numerator uses gradient at $t$-th step).  ACProp has both strong theoretical properties and empirical performance. With the example by Reddi et al. (2018), we show that asynchronous optimizers (e.g. AdaShift, ACProp) have weaker convergence condition than synchronous optimizers (e.g. Adam, RMSProp, AdaBelief); within asynchronous optimizers, we show that centering of second momentum further weakens the convergence condition. We demonstrate that ACProp has a convergence rate of $O(\frac{1}{\sqrt{T}})$ for the stochastic non-convex case, which matches the oracle rate and outperforms the $O(\frac{logT}{\sqrt{T}})$ rate of RMSProp and Adam. We validate ACProp in extensive empirical studies: ACProp outperforms both SGD and other adaptive optimizers in image classification with CNN, and outperforms well-tuned adaptive optimizers in the training of various GAN models, reinforcement learning and transformers. To sum up, ACProp has good theoretical properties including weak convergence condition and optimal convergence rate, and strong empirical performance including good generalization like SGD and training stability like Adam. We provide the implementation at \url{ https://github.com/juntang-zhuang/ACProp-Optimizer}.

Momentum Centering and Asynchronous Update for Adaptive Gradient Methods
Juntang Zhuang's Yifan Ding"; Tommy Tang"; Nicha Dvornek
Sekhar Tatikonda' James S. Duncan'
1 Yale University; 2 University of Central Florida; University of Illinois at Urbann-Champaign {j zzuangg n cha. dvornek; sekhar tatikonda; jamess yf. ding@kni ghts ucf edu; towmytt28illinoiii.... edu
james ) @eaala..ell....eeaaeeeeeeaaaee edu;
Abstract
We propose ACProp ceneehrrnnous-cetrrinngg-g combines centering second momentum and asynchronous update (e.g. for t-th update, denominator uses information up to step t 1. while numerator uses gradient t-th step). ACProp has both strong theoretical properties and empirical performance. With the example by Reddi et al. (2018), we show that asynchronous optimizers (e.g. AdaShift, ACProp) have weaker convergence condition than syn- chronous optimizers (e.g. Adam, RMSProp, AdaBelief); within asynchronous optimizers, we show that centering of second momentum further weakens the con- vergence condition. We demonstrate that ACProp has convergence rate of O VT
an adaptive optimizer which
for the stochastic non-convex case, which matches the oracle rate and outperforms the O( LesTT) ) rate of RMSProp and Adam. We validate ACProp extensive empiri- cal studies: ACProp outperforms both SGD and other adaptive optimizers in image classification with CNN, and outperforms well-tuned adaptive optimizers in the training of various GAN models, reinforcement learning and transformers. To sum up. ACProp has good theoretical properties including weak convergence condition and optimal convergence rate, and strong empirical performance including good generalization like SGD and training stability like Adam. We provide the imple- mentation at https: /ttt::////ttbb com/ juntang-zhuang ACPrrppOptiimin
/T
Introduction
Deep neural networks are typically trained with first-order gradient optimizers due to their com- putational efficiency and good empirical performance [[] Current first-order gradient optimizers can be broadly categorized into the stochastic gradient descent (SGD) [2 family and the adaptive family. The SGD family uses global learning rate for all parameters, and includes variants such as
SGD (3] SGD with momentum 4 and the heavy-ball method [5) Compared
with the adaptive family, SGD optimizers typically generalize better but converge slower, and are the default for vision tasks such as image classification (6), object detection and segmentation
The adaptive family uses element-wise learning rate, and the representatives include AdaGrad [ AdaDelta 10), RMSProp [T Adam [22 and its variants such AdamW 13. AMSGrad [4]
AdaBound 15). AdaShift [16), RAdam 17 and AdaBelief [18). Compared with the SGD family, the
adaptive optimizers typically converge faster and are more stable, hence are the default for generative adversarial networks (GANs) [19], transformers (20). and deep reinforcement learning [21].
We broadly categorize adaptive optimizers according different criteria, in Table. T (a) Centered v.S. uncentered Most optimizers such as Adam and AdaDelta uses uncentered second momentum in the denominator; RMSProp--enter [11) SDProp 22 and AdaBelief [18] use square root of centered
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table Categories of adaptive optimizers
Uncentered second momentum
Centered second momentum
Synchronous Asynchronous
Adam RAdam, AdaDelta, RMSProp RMSProp-center. SDProp, AdaBelief ACProp (ours)
AdaShift
second momentum in the denominator. AdaBelief [18] is shown to achieve good generalization like the SGD family, fast convergence like the adaptive family, and training stability in complex settings such GANs. (b) Sync vs async' The synchronous optimizers typically use gradient ÿt in both numerator and denominator, which leads to correlation between numerator and denominator; most existing optimizers belong to this category. The asynchronous optimizers decorrelate numerator and denominator (e.g. by using 9r as numerator and use (9o...9t- } in denominator for the f-th update), and is shown have weaker convergence conditions than synchronous optimizers [6].
We propose Asynchronous Centering Prop (ACProp), which combines centering of second momentum with the asynchronous update. We show that ACProp has both good theoretical properties and strong empirical performance. Our contributions are summarized as below:
Convergence condition (a) Asyne Sync We show that for the example by Reddi et al. (2018), asynchronous optimizers (AdaShift, ACProp) converge for any valid hyper ayper-parameters while synchronous optimizers (Adam, RMSProp et al.) could diverge if the hyper-paramane not carefully chosen. (b) Async-Center vs Async-Uncenter Within the asynchronous optimizers family, by example of an online convex problem with sparse gradients, show that AeynerCenter (ACProp) has weaker conditions for convergence than
(AdaShift).
Convergence rate We demonstrate that ACProp achieves convergence rate of ( for
stochastic non-convex problems, matching the oracle of first-order optimizers 23 and outper- forms the O log2") rate Adam and R.MSProp.
Empirical performance We validate performance of ACProp in experiments: on image classi- fication tasks, ACProp outperforms SGD and AdaBelief, and demonstrates good generalization performance; experiments with transformer, reinforcement learning and various GAN models, ACProp outperforms well-tuner tull-tund Adam, demonstrating high stability. ACProp often outperforms AdaBelief, and achieves good generalization like SGD and training stability like Adam.
2
Overview of algorithms
2.1 Notations
24 RR:: is didmensiooa parameter to be optimized, and xy is the value step l.
[(x), 1 ER: f(x) is the scalar-valued function to be minimized, with optimal (minimal) f*
01 E R: a is the learning rate at step t. e is small number to avoid division by 0.
91 E Rd: The noisy observation of gradient (x at step t.
B1 82 E R: Constants for exponential moving average, S B1, B2 <
m4 Rd: me -1m4-1 (1 (1) The Exponential Moving Average (EMA) of observed gradient at step t.
Age E Rd: Ag: = 9t my- The difference between observed gradient Jr and EMA of gt-
U. Rd: it 82 + (1 32)g/ The EMA of 9²-
St Rd: S; f25 + (1 (A))) The EMA of (Ag.)².
2.2 Algorithms
In this section, summarize the AdaBelief [18] method in Algo. and ACProp in Algo. 2 For the ease of notations, all operations in Algo. and Algo. [ are element-wise, and we omit the bias-correction step of m, and 8 for simplicity. TI represents the projection onto feasible set F.
We first introduce the notion of "syne (asyne)" and "center (uncenter)". (a) Sync vs Async The update parameter I; can be generally split into numerator (e.g. m4, 9t) and denominator (e.g.

---

Algorithm 1: AdaBelief
Algorithm 2: ACProp
Initialize zo, mo t 00 t 0,
Initialize Ho. ma
0,80 80 0,
While 24 not converged
While 2₁ not converged
t 1+1
+ 1 9: f V Vafe(rz-1)
9t < vafe((t-11)
m t 31m4-1 + (1 52)9t
m Bim=-1 1
+ +1--31)
St t 1 (9t m
21 II var-
Dt-1
v ite 9t
2x - 1F xt-1
Voete
1 114
8t 8281-1 ++ (9c mam²
ysi, (r), We call it "sync" if the denominator depends on 9t. such as in Adam and RMSProp; and call it "asyne" if the denominator is independent of 9t, for example, denominator uses information up to step t t- for the t-th step. (b) Center vs Uncenter The "uncentered" update uses 2t2 the exponential moving average (EMA) of g while the "centered" update
8,, the EMA of (g: 3
stores the EMA of the gradient in m,, and stores the EMA of oe in uz. For each step of the update, Adam performs element-wise division between my and Ve,- Therefore, the term 0t ".. can be viewed as the element-we learning rate. Note that 31 and B2 are two scalars controlling the smoothness of the EMA for the first and second moment, respectively. When 31 0, Adam reduces RMSProp
Adam (Sync-Uncenter)
The Adam optimizer
AdaBelief (Sync-Center) AdaBelief optimizer 18 is summarized in Algo. Compared with Adam, the key difference is that it replaces the uncentered second moment t (EMA of g?) by an estimate of the centered second moment &, (EMA of (gt - ) The intuition is to view m, as an estimate of the expected gradient: if the observation gi deviates much from the prediction my then takes a small step; if the observation Ir is close to the prediction my, then it takes a large step.
AdaShift AAyyc-Unnenter
AdaShift [16] performs temporal decorrelation between numerator and }} for the
denominator. It uses information (g. } for the numerator, and uses {g0. -.-t-n-1> denominator, where is the "delay step" controlling where to split sequence {g 1 The numerator is independent of denominator because each Ji is only used in either numerator or denominator.
ACProp (Async-Center) Our proposed ACProp is the asynchronous version of AdaBelief and is summarized in Algo. 2 Compared to AdaBelief, the key difference is that ACProp uses 8 in the denominator for step t. while AdaBelief uses 8,, Note that s; depends on 9t. while 8,-1 uses history up to step / - 1. This modification is important to ensure that (gt,/ / 18t-1 ..-t----))) = (Ego)/ /3,-1. It's also possible use a delay step larger than I similar AdaShift, for example, use EMA(19 . as numerator, and EMA(1 m=))))==111 for denominator.
3 Analyze the conditions for convergence
We analyze the convergence conditions for different methods in this section. We first analyze the counter example by Reddi et al. (2018) and show that async-optimizers (AdaShift, ACProp) always converge vB1,, 32 (0, 1), while sync-optimizers (Adam, AdaBelief, RMSProp al.) would diverge if (81, B2) are not carefully chosen; hence, async-optimizers have weaker convergence conditions than sync-optimizers. Next, we compare async-uncenter (AdaShift) with async-center (ACProp) and show that momentum centering further weakens the convergence condition for sparse-gradient problems. Therefore, ACProp has weaker convergence conditions than AdaShift and other sync-optimizers.
3.1 Syne vs Asyne
We show that for the example in [1,, async-optimizers (ACProp, AdaShift) have weaker convergence conditions than sync-optimizers (Adam, RMSProp. AdaBelief).
Lemma 3.1 1 in [14. There exists an online convex optimization problem where sync- optimizers (e.g. Adam, RMSProp) have non-zero average regret, and one example is
Pz,
if tPp Otherwise x E 111,12
[x(x)
(1)
-x,
3

---

AdaBelief
RMSProp
Adam
30
Converge
Converge
Converge
Diverge
Diverge
Diverge
20
ACProp (Ours)
AdaShift, n=1
AdaShift, n=3
Converge
Converge
Converge
20
10
0.5
1.5 -log(1 (1-B2)
2.0
0.5
1.5
0.0
1.5 2.5
-log(1 -B2)
log(1-Ba)
Figure 1: Numerical results for example defined by Eq. (I). We set the initial value as zo = 0. and run each optimizer for 10* steps trying different initial learning rates in {10 1.10 10
10 3 10 , 10--1111 ,10), and set the learning rate decays with 1/vF. If there's 's a proper initial lcarning rate, such that the average distance between the parameter and its optimal value x = -1 for the last 1000 steps below 0.01, then it's marked as "converge" (orange plus symbol), otherwise as "diverge" (blue circle). For each optimizer. we sweep through different S2 values in a log grid (æ-axis), and sweep through different values of P in the defimition of problem (y-axis). We plot the result for 81 = 0.9 here; for results with different 31 values, please refer to appendix. Our results indicate that in the (P, (2) plane, there's threshold curve beyond which sync-optimizers (Adam, RMSProp. AdaBelief) will diverge; however, async-optinee asymec-otimiiers (ACProp. AdaShift) always converge for any point in the (P, 82) plane. Note that for AdaShift, a larger delay step n is possible to cause divergence (see example in Fig. 2 with n = 10). To validate that the "divergence" is not due to numerical issues and sync-optimizers are drifting away from optimal, we plot trajectories in Fig.
Lemma 3.2( ( (2 D. For problem (1) with any fixed P. there's 's a threshold of 32 above which RMSProp converges.
In order to better explain the two lemmas above, we conduct numerical experiments on the prob- lem by Eq. [.. and show results in Fig, T Note that >*++P fx) = x. hence the optimal point is x -1 since x E [-1,1]] 1]. Starting from ini- tial value xgg = 0, we sweep through the plane of (P, 52) and plot results of convergence Fig.
Trajectories for problem 1
ACProp
AdaBelief
Value of
0.0
RMSProp
Adam
AdaSrifft n=1
005
AdaShiff, n-3
and plot example trajectories in Fig. [
AdaShift, n=10
-1.0
Lemma. 3.1 tells half of the story: looking at
1000
2000
3000 Steps
4000 5000
each vertical line in the subfigure of Fig. [ that is, for each fixed hyper-parameter 32, there ex- ists sufficiently large P such that Adam (and RMSProp) would diverge. Lemma. 3.2 tells the other half of the story: looking at each horizontal line in the subfigure of Fig. D for each problem with a fixed period P. there exists sufficiently large Bys beyond which Adam can converge.
Figure 2: Trajectories of æ for different optimizers in Problem by Eq. Initial point is 2o = 0, the optimal x = -1, the trajectories show that sync-optimizers (Adam, AdaBelief, RMSProp) diverge from the optimal, validating the divergent area in Fig. D correct rather than artifacts of numerical issues. Async-optimizers (ACProp, AdaShift) converge to optimal value, hut large delay step n AdaShift could cause non-convergence.
The complete story is to look at the (P, 32) plane in Fig. [1. There is boundary between conver- gence and divergence area for sync-optimizers (Adam, RMSProp, AdaBelief), while async-optimizers (ACProp, AdaShift) always converge.
Lemma 3.3. For the problem defined by Eq. (T. using learning rate schedule of a VP' async- optimizers (ACProp and AdaShift with n 1) always converge V3,, 32 E (0,1), VP E N, 3.
The proof is in the appendix. Note that for AdaShift, proof for the always- convergece property only holds when = larger n could cause divergence (e.g. n 10 causes divergence in Fig. 2 The always-convergence property of ACProp and AdaShift comes from the un-biased stepsize, while the stepsize for syne-optimizers are biased due correlation between numerator and denominator.
Taking R.MPPopp as example of sync-optimizer, the update is -0² 2t
Ott
Ve.
Re + 8007 +97
Note that ge is used both in the numerator and denominator, hence large It does not necessarily

---

ACProp, A 0.9
AdaShift, B = 0.9, n=
AdaShift, B1 - 0.9, n
Converge
Converge Diverge
Converge
30
30-
Diverge
20
20
10
10
10
0.0 0.5
1.0
1.5
2.0
2.5
0.0
0.5
1.0
1.5
2.0
2.5
0.0
0.5
1.0
1.5
2.0
2.5
-log(1-B2)
(1-g(1-82)
-log(1-B2)
Figure 3: Area of convergence for the problem in Eq. ( The numerical experiment is performed under the setting in Fig. Our results experimentally validated the claim that compared with async-uncenter (AdaShift), asyne-cens center (ACProp) larger convergence area the syper-parameter space.
generate large stepsize. For the example in Eq. (.. the optimizer observes gradient of -1 for 1 times and a gradient P once; due to the biased stepsize sync-optimizers, the gradient of P does not generate sufficiently large stepsize to compensate for the effect of wrong gradients -1, hence cause non-convergence. For async-optimizers, 9t is not used in the denominator, therefore, the stepsize is not biased and async-optimizers has the always-convergenee property.
Remark Reddi al. (2018) proposed AMSGrad track the element-wise maximum of e, order to achieve the always-convergenec property. However, tracking the maximum in the denominator will in general generate small stepsize, which often harms empirical performance. We demonstrate this through experiments in later sections in Fig.
3.2 Async-Uncenter vs Async-Center
In the last section, we demonstrated that async-optimizers have weaker convergence conditions than sync-optimizers. this section, within the async-optimizer family, we analyze the effect of centering second momentum. We show that compared with async-uncenter (AdaShift), async-center (ACProp) has weaker convergence conditions. We consider the following online convex problem:
P/2 x x, f((x)
1%P =-1
2,
hP=== E> 0.1
(2)
0,
otherwise
Initial point Ty 0.5. Optimal point x= We have the following results:
Lemma 3.4. For the problem defined by Eq. 2 consider the hyper-parameter tuple (Bi, B2, P), there exists cases where ACProp converges but AdaShift with n = 1 diverges, but not vice versa.
We provide the proof in the appendix. Lemma. 3.4 implies that ACProp has larger area of conver- gence than AdaShift, hence the centering of second momentum further weakens the convergence conditions. We first validate this claim with numerical experiments in Fig. for sanity check, we plot the trajectories of different optimizers in Fig. We observe that the convergence AdaShift influenced by delay step n, and there's 's good criterion to select good value of n, since Fig. requires a small n for convergence problem (T). while Fig. Irequirs a large n for convergence in problem 2 ACProp has larger area of convergence, indicating that both async update and second momentum centering helps weaken the convergence conditions.
We provide an intuitive explanation on why momentum centering helps convergence. Due to the periodicity of the problem, the optimizer behaves almost periodically as + co. Within each period, the optimizer observes one positive gradient P/2 and one negative gradient -1. As in Fig. 5 between observing non-zero gradients, the gradient is always O. Within each period, ACprop will perform a positive update (/(2/=+) and negative update- -1/V where s+ (s ) is the value of denominator before observing positive (negative) gradient. Similar notations for vt and v in AdaShift, A net update in the correct direction requires 2/5T
(or s < p2/4)
When observing 0 gradient, for AdaShift, e, B2v (1 00 for ACProp, st 323 (1 - (0 m2 where m, + Therefore, e decays exponentially to 0, but 8 decays to non-zero constant, hence -- t hence ACProp is casier to satisfy st /s- - < p2 and converge.
5

---

Trajectories for problem 2
Denominator
0.8
ACProp
Gredient(resscaled
AdsShift,
ACProp
Value of
AdaShift,
AdeShift
AdldShift, n-10
05
0.2
0.0
500
1000
1500
2000
-05
20
30
Steps
Steps
Figure 4: Trajectories for problem defined by Eq.
Figure 5: Value of uncentered second momentum tV
Note that the optimal point x² O.
and centered momentum 8, for problem 2
Analysis on convergence rate
In this section, we show that ACProp converges at a rate of (1/V/T) in the stochastic nonconvex case, which matches the oracle [23] for first-order optimizers and outperforms the OloggT/ VT) rate for sync-optimizers (Adam, RMSProp and AdaBelict) [26 25 18 We further show that the upper bound on regret of async-center (ACProp) outperforms usync-uncenter (AdaShift) by constant.
For the of analysis, denote the update as: 22 24-1 A, where A is the diagonal preconditioner. For SGD, A = I; for sync-optimizers (RMSProp), A vor+e for AdaShift with n = A, . for ACProp, A -ou For asyne optimizers, I[[Agh (9o ... A,Eg; for sync-optimizers, this does not hold because I: is used in A,
Theorem 4.1 (convergence for stochastic non-convex case). Under the following assumptions:
is continuously differentiable, J is lower-bounded by I and upper bounded by My. [(x))) is globally Lipschitz continuous with constant T.:
[V ff(y))l S L vll
(3)
For any iteration t, is an unbiased estimator of V f(z) with variance bounded by o². Assume norm of gt is bounded by Mg-
B3 [
V
B[llg -)(x)))111 0²
(4)
C then for B1,B2 [0, 1), with learning rate schedule a4 aut au I LOg n (0.5.1) for the sequence {xt} generated by ACProp, we have
Σ
s 2 G
2 [M,, [(M,- fan
IC200a0 T-
(5)
2(1 1 11)
where C1 and Cu are scalars representing the lower and upper bound for As, egg. Ci 1 A. - Cal. where A < B represents A is semi-posiiive-deiiiic
Note that there's 's a natural bound for Ct and Cu: C. S and Ci 2 2M, because c is added to denominator to avoid division by 0, and 9: is bounded by Mg. Thm. T implies that ACProp has convergence rate of (1/vTT) when 17 0.5; equivalently, in order have [V < 8?.
ACProp requires at most 0(6-4) steps.
Theorem 4.2 (Oracle complexity 23)). For stochastic non-convex problem satisfying assumptions in Theorem. 4.1 using only to first-order gradient information, in the worst case any algorithm requires at least O6 queries to find a 8-stationary point x such that ||V fz))l 82.
Optimal rate in big O Thm. 4.1 and Thm. imply that async-optimizers achieves a convergence rate of O(1/VT) for the stochastic non-convex problem, which matches the oracle complexity and outperforms the O(logT/VT) rate of sync-optimizers (Adam [4], RMSProp 25 AdaBelief (18).
Adam and RMSProp are shown to achieve O(1/VT) rate under the stricter condition that 32, 27]. similar rate has been achieved AVAGrad (8), and AdaGrad shown to achieve a similar
rate 229 Despite the same convergence rate, we show that ACProp has better empirical performance.

---

Mean of denominator
Training loss
accuracy
Epoch
accuracy
Epach
Second momentum
S in ACProp
ACProp
ACProp-i-1o-3
AcProp
Adatbelie
AdaBelif
AdfaShif-ir-ee-1
AMSGrad-n-101
AdeShift
Ada5
Ade3hiit-i-1e-2
AMSGrad-n1e1
Adam
Atam
AdaShift-i-le-3
AMSGrac-i-e-3
AdaShitt Ir 1o
AMSGrac 10 4
AduShittir-1e55
AMSGrad-I-1es
20
23
15
20
25
Epoch
Epoch
Figure 6: From left to right: (a) Mean value of denominator for a 2-layer MLP on MNIST dataset. (b) Training loss of different optimizers for the 2-layer MLP model. (c) Performance of AdaShift for VGG-11 1 on CIFARIO varying with learning rate ranging from Ie-1 to le-5, we plot the performance of ACProp with learning rate 1e-3 as reference. Missing lines are because their accuracy are below display threshold. All methods decay learning rate by a factor of 10 at 150th epoch. (d) Performance of AMSGrad for VGG- 11 on CIFARIO varying with learning rate under the same setting in (c).
Constants in the upper bound of regret Though both async-center and asyne-uncenter optimizers have the same convergence rate with matching upper and lower bound in big O notion, the constants of the upper bound regret is different. Thm. 4.1 implies that the upper bound on regret is an increasing function of 1/C; and C.. and
1/C1- = VK, 6, C. = 1/(KKi+ +c)
where K₁ and K2, are the lower and upper bound of second momentum, respectively.
We analyze the constants in regret by analyzing K₁ and Ku. If we assume the observed gradient ge follows some independent stationary distribution, with mean μ and variance o², then approximately
Uncentered second momentum: 1/C = v kg + t vpP + o +c
(6)
Centered second momentum: 1/C; Vk: + Vo +e
During early phase of training, in general |μ| >>>>>>> o, hence 1/C; < 1/Cf, and the centered version (ACProp) can converge faster than uncentered type (AdaShift) by a constant factor of around
Va2+o2+e
Volte During the late phase, 9. is centered around 0, and ||| < hence KỤ (for uncentered version) and KJ (for centered version) are both close to O, hence C. term is close for both types.
Remark We emphasize that ACProp rarely encounters numerical issues caused by a small as denominator, even though Eq. 77) implies lower bound for 8 around 0² which could be small in extreme cases. Note that is an estimate of mixture of two aspects: the change in true gradient [z) - f (z)) [2 f, and the noise in 9r as an observation of V (z). Therefore, two conditions are essential to achieve 8, = 0: the true gradient (ar( remains constant, and gr is nrise-free (=)(
O, if we further assume Ø = 0, then the problem reduces to a trivial ideal case: linear loss surface with clean observations of gradient, which is rarely satisfied in practice. More discussions are in appendix.
observation of (x)). Eq. ( is based on assumption that [xx)
Empirical validations We conducted experiments on the MNIST dataset using a 2-layer MLP, We plot the average value of o, for uncentered-type and s for centered-type optimizers; as Fig. a. shows, we observe St S Ut and the centered-type (ACProp, AdaBelief) converges faster, validating our analysis for early phases. For epochs > 10, we observe that min st zs min v2 validating our analysis for late phases.
As in Fig. a,,,)), the ratio st/8, decays with training, and in fact it depends model structure and dataset noise. T'herefore, empirically it's hard to compensate for the constants in regret by applying larger learning rate for async-uncenter optimizers. As shown in Fig. Fig.Bc.dd c.d)) for VGG network on CIFAR 10 classification task, we tried different initial learning rates for AdaShift (async-uncenter) and AMSGrad ranging from le-1 to le-5, and their performances are all inferior to ACProp with learning rate le-3. Please see Fig 8 for a complete table varying with hyper-parameters.
5 Experiments
We validate the performance of ACProp in various experiments, including image classification with convolutional neural networks (CNN), reinforcement learning with deep Q-network (DQN), machine translation with transformer and generative adversarial networks (GANs). We aim to test
7

---

Test accuracy
Epoch
Test accuracy
Epoch
Test accuracy Epoch
ACProp
ACProp
ACProp
AdaBelier
AdaBelief
AdaBelier
SGD
SGD
SGD
Adam
10
Adam
Adam
RAdam
RAdam
RAdam
AdamW
AdamW
AdamW
AdaShift
Adashift
AdaShift
152
17
Figure 7: Test accuracy (mean + std) on CIFARIO datset. Left to right: VGG-I1, ResNet-34, DenseNet-121.
ACProp
AdaShift
Reward Reinforcement Learning
90.56
88.73
81.53
61.1
10.0
10.0
87.47
79.45
Reward (2:tt)
eg5.on
10.0
00
10.0
10.0
06.73
ACProp
AdaBellef
1609
10.0 10.0
91.24 79.7 Le00
10.0 10.0
87.39 79.25
AdaSn
Adam
16:00
10.0
10.0
87.63 78.3 1ei9
10.0
10.0 87.65 79.64
RAda m
learning rate
leaming rate
Epoch
Figure 8: Test accuracy (%) of VGG network CIFARIO under different hyper- seper-parameters. We tested learning rate in {10 ,110 - ,,10 ,,10",10' 4)
Figure 9: The reward (higher is better) curve of a DQN-network on the four-rooms problem. We report the mean and standard deviation across 10 independent runs.
and c E {10 .... 10-9)
Table 2: Top-1 accuracy of 8 on ImageNet. 9 is reported in PyTorch Documentation, is reported in [30], * is reported in [7. $ is reported in [18]
SGD
Adam
AdamW
RAdam AdaShifi
AdaBelicf
ACProp
69.76 (70.23f)
66.54
67.93
67.62"
65.28
70.08t
70.46
both the generalization performance and training stability: SGD family optimizers typically are the default for CNN models such as in image recognition (6] and object detection 7 due their better generalization performance than Adam; and Adam is typically the default for GANs [19], reinforcement learning [2 and transformers [20], mainly due to its better numerical stability and faster convergence than SGD. We aim to validate that ACProp can perform well for both cases.
Image classification with CNN We first conducted experiments CIFARIO image classification task with a VGG-11 [1I, ResNet34 6 and DenseNet- 121 [32]. We performed extensive hyper- parameter tuning in order to better compare the performance of different optimizers: for SGD set the momentum as 0.9 which is the default for many cases 66 [2] and search the learning rate between 0.1 and 10-5 in the log-grid; for other adaptive optimizers, including AdaBelief, Adam, RAdam, Adam W and AdaShift, we search the learning rate between 0.01 and 10-5 in the goidg and search e between 10-5 and 10 in the log-grid. We use weight decay of 5c-2 for AdamW, and use 5e-4 for other optimizers. We report the mean + std for the best of each optimizer in Fig. 7 for VGG and ResNet, ACProp achieves comparable results with AdaBelief and outperforms other optimizers; for DenseNet, ACProp achieves the highest accuracy and even outperforms AdaBelief by 0.5%. As in Table 2 for ResNet18 on ImageNet, ACProp outperforms other methods and achieves comparable accuracy to the best of SGD in the literature, validating its generalization performance.
To evaluate the robustness to hyper-parameters, we test the performance of various optimizers under different hyper-parameters with VGG network. We plot the results for ACProp and AdaShift as an example in Fig. and find that ACProp is more robust hyper-parameter and typically achieves higher accuracy than AdaShift.
Reinforcement learning with DQN We evaluated different optimizers reinforcement learning with a deep Qenewwork (DQN) 21 on the four-rooms task [33]. We tune the hyper- hyper- parameters in the same setting as previous section. We report the mean and standard deviation of reward (higher is better) across 10 runs in Fig. | ACProp achieves the highest mean reward, validating its numerical stability and good generalization.
Neural machine translation with Transformer We evaluated the performance of ACProp on neural machine translation tasks with transformer model [20]. For all optimizers, set
8

---

Table 3: BLEU score (higher is better) on machine translation with Transformer
Adam
RAdam
AdaShift
AdaBelief
ACProp
DE-EN
34.661.0014
34.76.10.003
30.18110.020
35.17:0.015
35.35-10.012
EN-VI
21.83=0.015
22.54=00.005
20.18+0.231
22.45=+0.003
22.62=+0.008
JA-EN
33.03-100008
3..23::0.015
25.24:10.151
34.38:10.009
33.70=10.021
RO-EN
29.78 0.003
30.26 = 0.011
27.86::0.024
30.03=0.0012
30.27:100077
Table 4: FID (lower is better) for GANs
Adam
RAdam
AdaShift
AdaBelief
ACProp
DCGAN
49.29-10.25
1..2411138
99.32:1..82
47.25:1.79
43.43.14.38
RLGAN
18.00+0.00
40.61+0001
56.18 +0.23
36.58-+0.12
37.15++0113
SNGAN
13.14+0.10
13.00+0.04
26.62++0.2
12.70++0.17
12.44++.002
SAGAN
13.98:10.02
14.2510.011
22.111:0.25
14.17-10.14
13.54.10.15
Table Performance comparison between AVAGrad and ACProp. 1 (4) represents metrics that upper
(lower) is better.
are reported in the AVAGrad paper (28)
WideResNet Test Eiror (L)
Transformer (IEU
GAN FID (L)
CIFARTO
CIFARTOO
DE-EN
RO-EN
DCGAN
SNGAN
AVAGrad
1..02 3.67
28.76"20.20
30.23:00.024
27.73+0.134
59.3243.28
21.02:0.14 12.44+0..2
ACProp
18.724+0.01
35.35+0.0012
30.27-0.007
43.34:44.8
10.9, 0.99, 0.999). 82 E {0.98, 0.99, 0.999) and e E {10-5, 10-6- 10.-,,...10-111 ,...100111] 16.. As shown in Table. 3 ACProp achieves the highest BLEU score out 4 tasks, and consistently outperforms well-tuned Adam.
learning rate as 0.0002, and search for 31
Generative Adversarial Networks (GAN) The training of GANs easily suffers from mode collapse and numerical instability [34] hence is a good test for the stability of optimizers. We conducted experiments with Deep Convolutional GAN (DCGAN) 35), Spectral-Norm GAN (SNGAN) 36
3 and Delativistic-GAr (RLGAN) 38 We set 31 0.5, and Self-Attention GAN (SAGAN)
search for 83 and with the same schedule as previous section. We report the FID 33 on CIFARIO dataset in Table. 4 where a lower FID represents better quality of generated images. ACProp achieves the best overall FID score and outperforms well-tuned Adam.
Remark Besides AdaShift, we found another async-optimizer named AVAGrad in 28 Unlike other adaptive optimizers, AVAGrad is not scale-invarian hence the default typer-parameter: are very different from Adam-type (Ir = 0.1, = 0.1). We searched for hyper-parameters for AVAGrad for much larger range, with between 1e-8 and 100 the log-grid, and Ir between 1e-6 and 100 in the log-grid. For experiments with WideResNet, we replace the optimizer in the official implementation for AVAGrad by ACProp, and cite results in the AVAGrad paper. As in Table 5 ACProp consistently outperforms AVAGrad in CNN, Transformer, and GAN training.
6 Related Works
Besides the aforementioned, other variants Adam include NosAdam 44) Sadam
Adax 42
AdaBound [13 and Yogi (4)) ACProp could be combined with other techniques such SWATS [4], Lhok 455 and norm regularization similar to AdamP [46] Regarding the theoretical
analysis, recent research has provided more fine-grained frameworks 47 48 Besides first-order
methods, recent research approximate second-order methods in deep learning
49 50 51
7 Conclusion
We propose ACProp, novel first-order gradient optimizer which combines the asynchronous update and centering of second momentum. We demonstrate that ACProp has good theoretical properties: ACProp has "always-convergence" property for the counter example by Reddi et al. (2018), while sync-optimizers (Adam, RMSProp) could diverge with uncarefully chosen problems with sparse gradient, async-cemtering (ACProp) has weaker convergence condition than esyne-uncentering (AdaShift); ACProp achieves the optimal convergence rate O(1/VT), outper- forming the [[logT/VT] rate of RMSProp (Adam), and achieves a tighter upper bound on risk than AdaShift. In experiments, we validate that ACProp has good empirical performance: it achieves good generalization like SGD, fast convergence and training stability like Adam, and often outperforms Adam and AdaBelief.
for

---

Acknowledgments and Disclosure of Funding
This research supported by NIH grant RO1N5035193.
References
[1] Ruoyu Sun, "Optimization for deep learning: theory and algorithms," arXiv preprint urXiv:1912.089577 2019.
[2] Herbert Robbins and Sutton Monro, "A stochastic approximation method," The annals of mathematical statistics, pp. 400-407 1951.
[3] Yu Nesterov, "A method of solving a convex programming problem with convergence rate o(1/k2)," in Sov. Math. Dokl, 1983.
[4] Ila Sutskever, James Martens, George Dahl, and Geoffrey Hinton, "On the importance of initialization and momentum in deep learning." in International conference machine learning,
2013, pp. 1139-1147.
[5] Boris T Polyak, "Some methods of speeding up the convergence of iteration methods," USSR Computational Mathematics and Mathematical Physics, vol. 4, no. 5, pp. 1-17, 1964.
[6] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun, "Deep residual learning for image recognition." " in Proceedings of the IEEE conference on computer vision and pattern recognition. 2016, pp. 770-778.
[7] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun, "Faster r-cmn: Towards real-time object detection with region proposal networks," arXiv preprint arXiv:1506.00 002110566919997 01497, 2015.
[8] Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla, "Segnet: A deep convolutional encoder-decoder architecture for image segmentation," IEEE transactions on pattern analysis and machine intelligence, vol. 39, no. 12, pp. 2481-2495, 2017.
[9] John Duchi, Elad Hazan, and Yoram Singer, "Adaptive subgradient methods for online learning and stochastic optimization," Journal of machine learning research, vol. 12, no. Jul, pp. 2121-2159, 2011.
[10] Matthew D Zeiler, "Adadelta: an adaptive learning rate method," arXiv preprint 122.5:12 2012.
[11] Alex Graves, "Generating sequences with recurrent neural networks," arXiv preprint 1308.0300 2013.
[12] Diederik P Kingma and Jimmy Ba, "Adam: A method for stochastic optimization," arXiv preprint arXiv: 1412 22880,06...00 2014.
[13] Ilya Loshchilov and Frank Hutter, "Decoupled weight decay regularization," arXiv preprint 10000 2017.
[14] Sashank Reddi, Satyen Kale, and Sanjiv Kumar, "On the convergence of adam and beyond," International Conference Learning Representations, 2018.
[15] Liangchen Luo, Yuanhao Xiong. Yan Liu, and Xu Sun, "Adaptive gradient methods with dynamic bound of learning rate," arXiv preprint arXiv: 09843, 2019.
[16] Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, and Yong Yu, "Adashift: Decorrelation and convergence of adaptive learning rate methods," " in International Conference Leurning Representations, 2019.
[17] Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han, "On the variance of the adaptive learning rate and beyond," arXiv preprint
2019.
[18] Juntang Zhuang, Tommy Tang, Sekhar Tatikonda, Nicha Dvomek, Yifan Ding, Xenophon Papademetris, and James Duncan, "Adabelicf optimizer: Adapting stepsizes by the belief in observed gradients," arXiv preprint arXhv:2010.07468 2020.
[19] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio, "Generative adversarial nets," in Advances in neural information processing systems, 2014, pp. 2672-2680.
10

---

[20] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin, "Attention is all you need," Advances in neural information processing systems, vol. 30, pp. 5998-6008, 2017.
[21] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller, "Playing atari with deep reinforcement learning," arXiv preprint arXiv: 132.5602, 2013.
[22] Yasutoshi Ida, Yasuhiro Fujiwara, and Sotetsu Iwamura, "Adaptive learning rate via covariance matrix based preconditioning for deep neural networks," arXiv preprint arXiv:100.005593 2016.
[23] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth, "Lower bounds for non-convex stochastic optimization," arXiv preprint arXiv:1912.02365. 2019.
[24] Geoffrey Hinton, "Rmsprop: Divide the gradient by a running average of its recent magnitude,"
Coursera, 2012.
[25] Naichen Shi, Dawei Li, Mingyi Hong. and Ruoyu Sun, "[RMS) can converge with proper hyper-parameter." in International Conference on Learning Representations, 2021.
[26] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. "On the convergence of class of adam-type algorithms for non-convex optimization." arXiv preprint arXiv: 1808:0994) 2018.
[27] Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu, "A sufficient condition for convergences of adam and rmsprop," in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019, pp. 11127-11135.
[28] Pedro Savarese, David McAllester, Sudarshan Babu, and Michael Maire, "Domain-inndependen dominance of adaptive methods," arXiv preprint 19120091200123 2019.
[29] Xiaoyu Li and Francesco Orabona, "On the convergence of stochastic gradient descent with adaptive stepsizes," in The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019, pp. 983-992.
[30] Jinghui Chen and Quanquan Gu, "Closing the generalization gap of adaptive gradient methods in training deep neural networks," arXiv preprint arXiv: 1806: 1806.06763, 2018.
[31] Karen Simonyan and Andrew Zisserman, "Very deep convolutional networks for large-scale image recognition," " arXiv preprint arXiv: 140991556, 2014.
[32] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger, "Densely connected convolutional networks," in Proceedings of the IEEE conference on computer vision and pattern recognition, 2017. pp. 4700-4708.
[33] Richard S Sutton, Doina Precup, and Satinder Singh, "Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning," Artificial intelligence, vol. 1 112, 1-2, pp. 181-211, 1999.
[34] Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen, "Improved techniques for training gans," in Advances in neural information processing systems, 2016, pp. 2234-2242.
[35] Alec Radford, Luke Metz, and Soumith Chintala, "Unsupervised representation learning with deep convolutional generative adversarial networks," arXiv preprint arXiv: 2015,
[36] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida, "Spectral normaliza- tion for generative adversarial networks," arXiv preprint arXiv: 0188800.59977 2018.
[37] Han Zhang, Ian Goodfellow, Dimitris Metaxas, and Augustus Odena, "Self-attention generative adversarial networks." in International conference on machine learning. PMLR, 2019, pp- 7354-7363.
[38] Alexia Sdicoeur-Martinean standard gan," arXiv preprint 1rXivv1807.0073: 2018
"The relativistic discriminator: a key element missing from
[39] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter, "Gans trained by a two time-scale update rule converge to local nash equilibrium," in Advances in neural information processing systems, 2017, pp. 6626-6637.
[40] Haiwen Huang, Chang Wang, and Bin Dong, "Nostalgic adam: Weighting more of the past gradients when designing the adaptive learning rate," arXiv preprint arXiv:1805.077 2018.
11

---

[41] Guanghui Wang, Shiyin Lu, Weiwei Tu, and Lijun Zhang, "Sadam: A variant of adam for strongly convex functions," arXiv preprint arXiv:1905.022 09990.09997... 2019.
[42] Wenjie Li, Zhaoyang Zhang, Xinjiang Wang, and Ping Luo, "Adax: Adaptive gradient descent with exponential long term memory," arXiv preprint 40X4v:2004009740, 2020.
[43] Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar, "Adaptive methods for nonconvex optimization." in Advances in neural information processing systems, 2018, pp. 9793-9803.
[44] Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson, "Averaging weights leads to wider optima and better generalization," arXiv preprint 1803. 2018.
[45] Michael Zhang, James Lucas, Jimmy Ba, and Geoffrey E Hinton, "Lookahead optimizer: k steps forward, step back," in Advances in Neural Information Processing Systems, 2019, pp. 9593-9604.
[46] Byeongho Heo, Sanghyuk Chun, Scong Joon Oh, Dongyoon Han, Sangdoo Yun, Gyuwan Kim, Youngjung Uh, and Jung- Woo Ha, "Adamp: Slowing down the slowdown for momentum optimizers scale-invariant weights," in Proceedings of the International Conference Learning Representations (ICLR), Online, 2021, pp. 3-7.
[47] Ahmet Alacaoglu, Yura Malitsky, Panayotis Mertikopoulos, and Volkan Cevher, "A new regret analysis for adam-type algorithms," in International Conference Machine Learning. PMLR, 2020, pp. 202-210.
[48] Xiaoyu Li, Zhenxun Zhuang, and Francesco Orabona, "Exponential step sizes for non-convex optimization." arXiv preprint arXiv:2002.05273, 2020.
[49] James Martens, "Deep learning via hessian-free optimization."" in ICML, 2010, vol. 27, pp. 735-742.
[50] Zhewei Yao, Amir Gholami, Sheng Shen, Kurt Keutzer, and Michael W Mahoney, "Adahessian: An adaptive second order optimizer for machine learning." arXiv preprint 0rXiv:2006.007199 2020.
[51] Xuezhe Ma, "Apollo: An adaptive parameter- diagonal quasi-newton method for nonconvex stochastic optimization." arXiv preprint arXiv:2009. 2020.
12


Reviews:
[{"review_id": "zIjqE24G2Kt", "reviewer": "Reviewer_Argb", "summary": "This work studies the problem of adaptive gradient methods and it is relevant to the conference. The paper provides momentum centering and asynchronous update for adaptive gradient methods that combines several existing works. The paper prove its algorithm the standard $1/\\sqrt{T}$ convergence rate for stochastic nonconvex case. There are some experiments on VGG + CIFAR10 associated with the paper, thus the practical performance of the approach is also validated.\n\n\n", "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": "The main contribution of the paper is the offering of momentum centering and asynchronous update for adaptive gradient methods. The problem is well-motivated and the writing is clear. There are some simulation results associated with the paper thus the proposed algorithm seems work from both the theory and simulations.\n \nIn short, the paper is technically sound and the developments are clear. The derived algorithm and rates seems to be correct and may be a useful contribution to the literature on adaptive gradient methods, showing a modest improvement over the state of the art. ​ ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no discussion on the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "gFDxGTl-s_A", "reviewer": "Reviewer_yEdV", "summary": "This paper proposes to combine centering of second momentum with asynchronous update for adaptive learning rate optimizer, showing that the proposed optimizer has: (1) a weaker convergence condition on sequence online convex optimization problem than its counterparts; (2) a convergence rate that matches the oracle; (3)  strong empirical performance in terms of generalization and training stability.", "questions": "", "limitations": "", "rating": 7, "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": "This paper is overall well written and has a moderate theoretical contribution. However, the experiments can be conducted and/or explained better to help understand the results. Besides, some points need to be clarified.\n\nIssues:\n\n- It should be mentioned that ACProp in the experiments does not use momentum, i.e., mt is only used for the estimation of st. \n\n- Given the previous point, the comparison between ACProp and other optimizers can be done better, e.g., disable momentum for other optimizers. Otherwise, it is hard to conclude whether centering is the key to better empirical performance.\n\n\n- The learning rate used In Figure 6 (a) and (b) should be given. Given that centered version generally has a large effective learning rate at the beginning, using a same learning rate for centered and uncentered would be inappropriate. If it is using a same learning rate, it might be better to tune the learning rate such that the curves in the initial stage basically overlap.\n\n\n- It is unclear why the proposed optimizer leads to better generalization. It is better to have some investigations and/or explanations in the paper.\n\n- It is interesting to show how rectification (RAdam) and/or decoupled weight decay (AdamW) work when combined with ACProp and other optimizers. It might help to understand the experiments, e.g., what are the fundamental issues in these optimizers and how the issues are solved.\n\n\nDetails:\n\n- Figure 8, there are typos for the range of eps. It is also not inconsistent with the correlated figure in the Appendix.\n\n\n- It is better to mention that AdaShift assumed the independence of gradients, which holds if minibatches are randomly sampled and is violated in the sequence online convex optimization problem.\n\n**Score increased from 6 to 7, after rebuttal.**", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "VguaTnPZuvQ", "reviewer": "Reviewer_5voH", "summary": "This paper proposed a new adaptive optimizer, ACProp, which combines centering of second momentum and asynchronous update. In essence, ACProp modifies an existing method AdaBelief by using s_{t-1} instead of s_{t} as the update denominator. It has been shown that ACProp has a weaker convergence condition in the example by Reddi et al. (2018). They also proved that ACProp has the same convergence rate of O(1\\\\sqrt{T}), which matches the oracle rate for the stochastic nonconvex case.", "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": "The proposed method is very similar to AdaBelief. The only difference is that ACProp uses s_{t-1} instead of s_{t} as the update denominator. It’s not clear how much difference there is between s_{t-1} and s_{t} during most period of the training procedure (i.e., when training loss curve starts to enter the flat part and only slowly decreases), especially given that \\beta_2 is normally set to a value that is very close to 1 (e.g., 0.99 or 0.999). \n\nWhat’s more, although the theoretical analysis of the proposed method ACProp looks interesting, I am concerned with how significant the change from AdaBelief to ACProp is in terms of the practical performance. The theoretical analysis has shown that ACProp is better than AdaBelief in some cases (e.g., weaker convergence condition in the example by Reddi et al. (2018)). However, in practice these cases might not be common enough to set ACProp clearly apart from AdaBelief. Actually, from the experiments in this paper, I tend to have the impression that ACProp has very close performance to AdaBelief in many cases (sometimes even worse than AdaBelief: see the row JA-EN in Table 3 and the row RLGAN in Table 4). For example, in Figure 7 (left and middle), blue curve (ACProp) and orange curve (AdaBelief) reach identical final test accuracy. In Table 2, the difference between AdaBelief and ACProp is only 0.38% (not sure how much of it might come from random noise), while the difference between AdaBelief and Adam is much larger, i.e., around 3.5%. Results from Table 3 and Table 4 also seem to suggest that ACProp has very similar performance with AdaBelief in most cases. \n\nGiven the above reasons, I am concerned that ACProp is just an incremental improvement over AdaBelief in practice.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations have been discussed in Section 3 and 4. \nNo negative societal impact is applicable.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "KoY3oHyXyJ3", "reviewer": "Reviewer_Vu9t", "summary": "This paper proposes an adaptive optimizer, ACProp, which combines centering of second momentum and asynchronous update. The authors show that ACProp has a convergence rate of $O(\\frac{1}{\\sqrt{T}})$ in a stochastic non-convex setting, outperforming the  $O(\\frac{\\log T}{\\sqrt{T}})$ of RMSProp and Adam in the same setting. Experiments on a range of tasks, including image classification, training GANs, reinforcement learning and machine translation, show the effectiveness of ACProp.", "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": "This is good paper with both theoretical results and comprehensive experiments. However, I still wonder how much ACProp could help in practice. To be detailed below.\n\nStrengths:\n1. ACProp converges under a wide range of hyperparameter settings on the toy problem in Eq. 1 and Eq. 2. The convergence rate is better than Adam and RMSProp in the same stochastic non-convex setting.\n\n2. Empirical results are verified on a range of different tasks.\n\nWeaknesses:\n1. Lack of comparisons with AMSGrad. AMSGrad already stabilizes Adam for Eq. 1. I wonder if it also solves Eq. 2. It would be even better if AMSGrad is also considered in other experiments.\n\n2. The main improvement of convergence rate in the stochastic non-convex setting seems to be from the asynchronous update scheme proposed in AdaShift, rather than a combination of the asynchronous update scheme and centering second momentum. The rate of ACProp is only better than AdaSfhit by a constant.\n\n3. I feel it is quite difficult to provide a 100% fair comparison for optimizers (finding the best hyperparameter for each optimizer), but this is important unless the proposed optimizer already shows a significant improvement over the best result of a well-established, challenging benchmark. Therefore, I have doubts about many experimental results. For example, in Figure 7, the learning rate schedule does not seem to be optimal for every optimizer. What if a cosine annealing schedule is used? Is SGD still not as good as adaptive methods? In Table 4, why is AdaShift much worse than ACProp? The only difference seems to be the second-momentum centering. However, with this technique, AdaBelief did not make such a huge improvement over Adam (e.g., ACProp's 99.32 to 43.43 vs. AdaBelief's 49.29 to 47.25).\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: I recommend acceptance. The work build on top of existing work and clearly (even if moderately) improves some theoretical and empirical aspects.

I applaud the authors for their great communication with the reviewers that were responsive during the discussion period. Their responses have been extensive and convincing. They have gone to great lengths to respond to all timely requests for extra experiments and hyper parameter tuning.

I acknowledge that last-minute requests for heavy experiments cannot be reasonably accommodated and I accept the provided experimental evidence as sufficient for the paper’s main claims.
Decision: Accept (Poster)