A new perspective in understanding of Adam-Type algorithms and beyond
Authors: Zeyi Tao
Qi Xia
Qun Li
Venue:  (2020)
Keywords: Machine Learning
Algorithm
Adam
First-Order Method

Abstract: First-order adaptive optimization algorithms such as Adam play an important role in modern deep learning due to their super fast convergence speed in solving large scale optimization problems. However, Adam's non-convergence behavior and regrettable generalization ability make it fall into a love-hate relationship to deep learning community. Previous studies on Adam and its variants (refer as Adam-Type algorithms) mainly rely on theoretical regret bound analysis, which overlook the natural characteristic reside in such algorithms and limit our thinking. In this paper, we aim at seeking a different interpretation of Adam-Type algorithms so that we can intuitively comprehend and improve them. The way we chose is based on a traditional online convex optimization algorithm scheme known as mirror descent method. By bridging Adam and mirror descent, we receive a clear map of the functionality of each part in Adam. In addition, this new angle brings us a new insight on identifying the non-convergence issue of Adam. Moreover, we provide new variant of Adam-Type algorithm, namely AdamAL which can naturally mitigate the non-convergence issue of Adam and improve its performance. We further conduct experiments on various popular deep learning tasks and models, and the results are quite promising.

Under review as a conference paper at ICLR 2020
A NEW PERSPECTIVE IN UNDERSTANDING OF ADAM- TYPE ALGORITHMS AND BEYOND
Anonymous authors Paper under double-blind review
ABSTRACT
First-order adaptive optimization algorithms such as Adam play an important role in modern deep learning due to their super fast convergence speed in solving large scale optimization problems. However, Adam's ' non-convergence behavior and disturbing generalization ability make it fall into a love-hate relationship to the deep learning community. Previous studies on Adam and its variants (refer as Adam-Type algorithms) mainly rely on theoretical regret bound analysis, which overlooks the natural characteristics residing in Adam-Type algorithms and limits understanding. In this paper, we aim at seeking a different interpretation of Adam-Typp algorithms so that we can intuitively comprehend and improve them. The way we chose is based scheme known as mirror descent method. By bridging Adam and mirror descent algorithm, we receive a clear map of the functionality of each term in Adam. In ad- dition, this new angle brings us a new insight on identifying the non-convereence issue of Adam and explaining the superior convergence speed of Adam than other first-order methods. Moreover, we provide new variant of Adam-Type algo- rithm, namely AdamAL which can naturally mitigate the con-conveeeence issue of Adam and improve its performance. We further conduct experiments on various popular deep learning tasks and models, and the results are quite promising.
traditional online convex optimization algorithm
INTRODUCTION
In recent years, first-order optimization algorithms with adaptive learning rate have become the dominant method train deep neural networks because these methods show extraordinary power in solving large-scale machine learning optimization problems. By cooperating with first-order in- formation, adaptive methods iteratively update parameters by moving them to the direction of the negative gradient of the cost function with non-fixed learning rate. The first algorithm in this line of research can be dated back to McMahan Streeter (2010), where they adaptively choose regular- ization functions for bounding objective function parameters based the loss functions observed at each iteration. Then, in SStrecter& & McMahan (2010), they demonstrate that the convergence rates often be dramatically improved through the of preconditioning. The insight of these two methods is parallel but effective, that is, they try to modify the gradients* magnitude with adaptive pre-coordinate learning rates. Later, AdaGrad (Duchi al., 2011)) carefully chooses the precon- ditioner and provides the first practical adaptive algorithm with tight theoretical guarantee based on Zinkevich (2003) regret analysis. Although AdaGrad achieves a great success in the sparse settings, the rapid decay of the adaptive learning rate limits its usage. This is due to AdaGrad ac- cumulating all the past gradients as its learning rate. And this unbounded learning rate becomes extremely small when one has large number of training iterations. To address this, several variants of AdaGrad, such as AdaDelta [Zeiler] 2012) and RMSProp (Hinton et al.) (012) have been pro- posed to mitigate the rapid decay of the learning rate. Based these, Adma (Kingma & Bal 2014) incorporating with first momentum correction accelerates the convergence speed of first-order op- timization algorithms to new height. The use of exponential moving average (EMA) in Adam becomes a key to Adam's 's success. Up to this point, we can summarize the adaptive or non-adaptive first-order optimization algorithms as follows.
Denote 9: E Rd as the gradient of generic optimization problem f with respect to its parameters Rd iteration I, then the generic updating rule of adaptive methods can be expressed as (Reddi

---

Under review as a conference paper at ICLR 2020
et al. 2019)
Th
F++1 Dt
m2
Ut
where @ denotes the entry-wise or Hadamard product and the a is the base learning rate. In the equation above, my i9g1.... ... : function related to the historical gradients up to and v(11.'.. 9t) is function that produces d-dimensional vector with non-negative entry: The design of 0f is simple of non-adaptive methods, such as vanilla stochastic gradient descent (Vanilla I, however, it is crucial for Adam-Type algorithms. For Adam, in particular, the my and 2i are computed by EMA of gradient, with coefficient B1 and 32 where
SGD), where we have
imt
m = (1 - 31)
3 9t and 12 = (1- 32)
9
Adam, the most popular adaptive method, has been widely adopted by the deep learning community. The root cause of the fast convergence of Adam and its variants in convex or non-convex optimiza- tion problems remains an open question (Chen al. 2018). In addition, the generalization ability and out-of-sample sample behavior of Adam- methods are even worse than traditional non-adaptive counterparts such as Vanilla SGD (Wilson et al. (017))
In order to understand the insight behind those adaptive algorithms and close the generalization gap, several Adam- Type algorithms have been proposed including (Reddi et al. 2019 Luo et al. 2019, Zhou et al.) 201 8b Balles& & Hennig 2017 Liu et al., 2019). Although they propose many different kinds of viewpoints in understanding the performance of Adam and demonstrate a series of correc- tion methods to improve Adam, think the mechanism of Adam-Type algorithms is still unclear. For example, one common thinking about about my and U Adam is first and second moments of unbiased estimator Jt, however, why this second moment
be used as adaptive learning rate? Does the 2, really behave as the second moment of the gradient g.? Also, another commonly asked question is where the Adam adopts such faster convergence speed than other first-order methods?
These mysterious questions on adaptive methods finally leads us to rethink the Adam-Type algo- rithms in neutral way. In this paper, we provide new insight into Adam-Type algorithms, which brings new perspective of comprehension on Adam- Adam-Type algorithms and it allows us to easily identify the misbehavior of Adam such as non-convergence issues. In the aforementioned works, the analysis of Adam- Type methods is based on Kingma & Ba (004)) framework, which limits our understanding. In fact, when we look back the origin of adaptive learning rate methods mentioned in Streeter & McMahan (2010), we notice that the design of Adam is highly related to adaptive regu- proximally-rggullrrieedd
larization of as a variant of traditional mirror descent method (Xiao) 2010). The more detail and our motivation can be found the next section. For simplicity, we use standard Adam as our touchstone through the paper to convey main idea, and their variants follow the same thoughts. Now, summarize our contribution in three folds:
(FTPRL) method and can also be regarded
1. We provide a new perspective in understanding the non-convergence behavior of Adam- Type algorithms based on mirror descent approach. Our analysis agrees well with the previous works but much more intuitive and effective.
2. Based on our observation, we identify potential faults in Adam -lam-Type algorithms and we provide
Adam variant algorithm, named AdamAL.
3. We conduct a series of experiments on different machine learning tasks and models by using our AdamAL algorithm, and the results are promising and the performance of AdamAL is never worse than Adam.
2 PRELIMINARIES AND MOTIVATIONS
Notations Given a vector & E Rd we denote its i-th entry by r;; We use ||>||| to denote its norm; for a vector in the t-th iteration, the i-th coordinate of za is denoted as 2t,i. We also define -
Fiit= Ei= Zz. Given two vectors v. y R, we use (x, to denote their inner product, denote element-wise product, _ to denote entry-wise division, the max y) to denote entry-wise y
y to
maximum and min(x, y) to denote entry-wise minimum. We use S, to denote the set of all positive definite matrices M. We use M denote VM.
2

---

Under review as a conference paper at ICLR 2020
2.1 PRELIMINARIES
Nonlinear projected subgradient methods and mirror descent algorithm Iterative gradient de- scent (GD) scheme, which can be traced back to (Cauchy 1847), the simplest strategy minimize convex optimization problems. It was further developed as Zinkevich Online Greedy Subgradient Project (OGSP) Zinkevich 2003), which can be considered as a variation of project gradient de- scent (PGD) algorithm with following updating rules:
J++1 = Px(x nf (xt) (standard PGD) I++1 = Px m.h) (Zinkevich OGSP)
(3)
where P is a distance-based projector denoting the projection of a point y onto X' by (A(v)
arg m || Al and || ||a = (a, Ar), and E (z+) I (axe) is the subgradient of the objective function ft(.) The well-known bottleneck of using PGD is that it can only work in Hilbert space H. and it cannot be extended to more general cases (in modern machine learning) of optimization plays in some Banach space B where the Euclidean norms cannot be computed. To this end, the mirror descent algorithm (MDA) introduced by (Nemirovsky & Yudin 1983) overcomes such infeasibility by using the linearity on dual vector space B and a carefully designed mirror map (Bubeck 2014). Hence, MDA has following updating schemes:
1 ()) + T}t
Tt+1 arg min((( (1x), ZEX
the nonlinear projection therefore encoded in the term D&s By replacing the Euclidean quadratic norms Equation. 3 with more general distance-liked settings such as Bregman distance function
(- define on (³(). the equivalence of PGD algorithm and MDA has been proved by BBek &
Teboulle (2003). For example, the simplest version of MDA is that: taking (xxx) 2 | 22 and
D (1 24
a x2l12 then plugging into Equation.
have:
T++1 = arg min ((gt,
+
||0
xx 12
(5)
zEX
27).
Update scheme in the above equation. is also known as proximal point algorithm (Rockafellar 1976). The equivalence of Equation. 5 and PGD can be achieved by taking the derivative of our target function on æ, and rearranging the formula:
Tt+1
Ne: PA negrt)
(6)
Now, we see the last two expressions in Equation. are well-known subgradient descent update. We restate the proposition 3.2 in Beck & Teboulle (2003) as:
Proposition 1. Assume X is closed convex subset in R with non-empty interior, and objective function.
function f X + R is a convex and finccint Suppose the optimal set of x denoted by X" is non-empty, we can compute the subgradient of as g E 0f(z). For a convex mirror mapping function db : X + R with conjugate function x/² defined by v/* (y) = max { ((x, y) <((x)}
Then the sequence { C X generated by MDA is equivalent the sequence generated by PGD.
We state the equivalence of PGD algorithm and MDA, particularly, the general gradient descent (or SGD) can directly derived from the Equation.
Follow the proximall--reqularizee leader (FTPRL) FTPRL is introduced by McMahan & Streeter (010)) belongs to the family of the-regularized-leadee (FTRL) algorithms such as Regular- ized Dual Averaging (Xiao 2010). In general, FTRL-Type has following update rule:
( (((x)) x Ria(F) T=1
Ft+1 arg min
xEX
where the subgradient of objective function (((x) is approximated by the gradient x, and R1a(x) is defined as regularization. Particularly, the formal FTPRL is:
Tt+1 arg ( a x dia - + (xx) Σ
(8)
zEx
with &ia x (x:) can be considered as non-smooth composite term which is orthogonal to
3

---

Under review as a conference paper at ICLR 2020
Table 1: An overview of first-order optimization methods using the generic framework
SGD
SGDM
AdaGrad
RMSProp
Adam
Ei=1
(1 (1) Σ i=1 31
m4
9t
91
V/
I
I
Σ
of
(1 - B) Ei=1 8 gr 9.
(1- B2) E 1= 32 92
Ir
1/2 % 1/0 V
1J V
1)0 V/
paper, more details can be found in McMahan (0110)). The last term in the above equation is stabilizing regularization to ensure low regret. We mention that the Q- be either regarded as scale of regularization or generalized learning rate which plays crucial role in our paper. As we can see, FTPRL appears quite different from MDA stated in Equation. [5] however, in McMahan (2010a b) they show that in the case of selecting quadratic stabilizing regularization, the FTPRL and generalized MDA only has differences in parameter centering. In fact, MDA is illustrated in the Equation. regularizing the parameter to be close to the origin, on contrast, FTPRL is regularizing the parameter current feasible point. No surprising. McMahan (2010a) propose the equivalence proof of FTPRL and variation algorithm of the MDA as follow.
Proposition 2. (McMahan 2010a) Let Re be a sequence of differentiable convex functions (VR, 0), and let be an arbitrary convex function.. Define the proximal MDDA with updating rule:
T++1 = arg (ge()))))))) + V(x)) + DR.. (-)
=ēX
where the Bregman distance function DR, with respect to Re where R₂(x) Re( - xt). And applying FTPRL to the same objective function, with:
Lt+1 = arg minagra: +ia + (xx) R1a}
(10)
xEX
when de E 00, such that Iud + Φ1 + VRI((a)) = 0. Then the two above update scheme are equivalent.
At this moment, we state series of equivalence proposition from FTPRL to proximal-MDA (vari- ation of MDA) and MDA to PGD. Now, we can construct the equivalence proof of FTPRL and PGD properly. Although the direct proof of equivalence between FTPRL and PGD is provided un- officially in McMahan (2010a), we would like to elaborate the intuition behind each algorithm and deduce our perspective in understanding the Adam-Type algorithms.
2.2 MOTIVATION
Non-Adam-type and Adam-type algorithms to mirror descent (FTPRL) Mon-Adam-tyy online gradient descent algorithms including SGD, SGD with momentum, Polyak's 's HB and Nesterov's 's ac- celerated gradient method can be easily understood first order optimization with different momen- tum function. And, interestingly, most of them have physical interpretations. However, as shown in Table [ Adam-Type algorithms do not rely on the non-increasing learning rate when iteratively parame-
updating their parameters. Instead, they perform adaptively learning rate element-wist ters according to the first order information. However, this leads to the most mysterious part in the Adam-Tyre algorithm where the adaptive update is represented
yey m, One common inter- noo as adaptive learning rate, and regarding pretation of this updating representation is regarding /or
general first order gradient. However, we can not treat Adam-Type algorithm in this way be- cause the first order information gi resides in both m, and i and we are unable to simply decorrelate them as common gradient with step-size scheme. Another possible interpretation of such updating related to the Newton's second order method, but there is no free lunch for expressing in this way. We will discuss it later.
In order to dissect Adam-Type algorithm, we recall the FTPRL algorithm mentioned in the previous section. A natural question arises: scent method? Before answering the question, let us explain why we present Adam- Type algorithm MDA is beneficial. We summary below:
interpret Adam-Type algorithm variant of mirror de-
4

---

Under review as a conference paper at ICLR 2020
Table 2: An overview of first-order optimization methods using Mirror Descent expression
SGD
SGDM
AdaGrad
Adam
imfjjt
i (ijj
A
(g
(g1
Σ
gitl-1). .x
2 |
21 1+13
Σ a+
||= x4
1
Σ 0+||0 x-112
2
p
Term A, C, p are defined in Equation
See below.
1. Implicit updates:
This concept was first derived by Kivinen & Warmuth 1997 and later pointed by Kulis & Bartlett (2010). It refers to without using explicit first-order update rules efficiently compute the parameters. The mirror descent algorithms, in fact, adopt implicit update rules very well, therefore, the explicit update will roll into some regularized- liked terms which can elaborate more insights. In contrast, like Adam, the learning rate is explicitly defined as no which is hard to identify from intuition unless relying on the theoretical proofs.
2. First-order information dissection The entire adaptive update involves in Hadamard product and division. Both numerator and denominator are highly related the construc- tion function with respect to the first-order gradient g. The underlying relation between two functions m, and d can not be decorrelated. However, as shown in Table 2 we rep- resent Adam-Type algorithms in MDA way that can separate the numerator and denominator as simple additive scheme where the hard-understanding division disappears and meanwhile, the alignment of m, and i2 gone.
3. Equivalence guarantee The original adaptive method AdaGrad is build upon non-linear subgradient projection, and Adam actually inherit such design indicate by their regret proof. To re-represent Adam-Type algorithm as FTPRL style, we do require the theoretical equiv- alence guarantee so that we can transform safely. As we discuss in previous (Proposition 1& 2), successfully build such bridge in between two types of algorithm.
In general, these first-order algorithms can be written in FTPRL style (also see Table 2):
T++1 arg min(p (gi. + CIa) x ((x)
11 (x 12)
(11)
2
xEX
The understanding of above representation is highly related to our analysis on Adam-Type algo- rithms. Term A has parts, the first part 91:t is approximation fi:t based on the gradient; the second part Cla & refers to first-order momentum correction or fault tolerant in this literature. Term B is similar to the setting of FTPRL, but we usually consider it 1 Iz-reuularization. In ad- dition, term C stabilizing regularization plays a crucial role in this transformation because (1) the implicit updates from 24 to x4+1 happen in this term; (2) the Q, residing in norms can be regarded as generalized learning rate or even more complicated format; (3) the rule of parameter centering to the current feasible solution is figured. Finally, the leading p balancing coefficient, aims at controlling the tendency of minimization between term A and C. Smaller p value will guide the minimization process and relies more on term C, otherwise term A will dominate the minimization.
The simplest format transformation from Vanilla SGD to MD is illustrated in Equation. 5 Now, we rewrite it as FTPRL style according to Equation. g (for the sake of simplicity, we do not consider the V)):
Fz+1 = arg min x + 0r11o 111
Σ
(12)
ZEx
2
r=1
where the p = 1, C1at is zero, and Q, sets to be Q, IRI. If Vanilla SGD with learning rate M 1. the Σ dr L. If it with fixed learning rate n E. then Σt= or ht To be
5

---

Under review as a conference paper at ICLR 2020
mentioned here, fixed learning rate SGD is kind of special, it can be easily explained as Equation. however, in FTPRL format (Equation. 12 we need to be more careful.
Mirror descent like Vanilla SGD with non- intrrasicranngg learning rates shows the great insight of un- derstanding current algorithms. First, we are always looking for the next step Z++1 in the opposite direction of the current gradient because cos(a)) -1 minimize Equation. 12 Second, Jz-1 is be- ing bound in a region centered at previous step z₁. This due to the fact that we do not want the new solution to be far away from the current feasible solution, otherwise, may cause slow convergence, and McMahan (2010)) confirm this view. Third, Σ o, should be non-decreasing alone time. Similar, when T, gets smaller, the bounding region expands, reducing the convergence speed.
3 NEW PERSPECTIVE ON ADAM
In this section, we deliver new perspective on Adam-Type algorithm from the Mirror Descent point of view. In this lecture. we mainly focus on Adam to demonstrate our analysis, for the other variants, they have similar results.
3.1 ADAM ON MIRROR DESCENT
According to the Table 2 the subgradient projected Adam can be written as follows (entry-wise). In order to make a clear comparison, we also show SGDM alongside.
Adam: F++1,i arg min (
Σ
- gr.))
I + 2 Σ
1aal=,,--00 - xr,11133
=Ex
(13)
r=tj==t
SGDM: 2141,4 arg min( aEx
1 - B1 (9r..1
1
8f41-1 gr.)) 2.,
2 Σ of -
where both 81 S 1 (commonly chose Bi 0.9), the Σt= Tr
((1 B2) Σ 83
in Adam settings with 83 0.999. In SGDM, Σ of performs differently, (1) SGDM is adaptive method, the -* applies to all entry on the x; (2) Σt=1 of = if we have learning rate t 1. it also means a² = for all T E T. First, let us recall Vanilla SGD and compare it with SGDM:
Corollary 1. Compare to Vanilla SGD, SGDM employs first-order momentum correction defined in Section. 2.2 to correct the possible wrong direction prediction, making a smooth optimization
trajectory. (This is a well known truth. We verify it by experiments show in Appendix.)
Besides, we also notice that Adam has p = 1 while SGDM has p --1h. = 10 (a common setting of 3 = 0.9). Recall the previous section, by definition of we have following corollary:
Corollary 2. Compare to Vanilla SGD Adam, SGDM has larger p value indicates that the SGDM is more sensitive on the value change of loss function.
To explain this, we know one of the drawbacks of SGDM is that SGDM is prone to oscillation around the optimal point, because SGDM has relatively weak bound in proximal terms, and is very sensitive to small change of loss, that is, factor amplifies this loss change up to tenfold. We notice that Adam avoids such imbalance between objective function and its parameter regularization by using EMA wisely.
Now, back to Adam, before we move forward, we define some terms in the Equation. Adam,
Proximal Searching Region refers to D = || - xr 1|2 this Euclidean quadratic norm reflects the geometry of given constraints feasible set X. We can also treat a regu- larization process. This region is inversely proportional (D x 1 to the Regularization Budget defined below.
Regularization Budget refer to B Σ Tr it indicates total "weight"
distribute
to the Proximal Searching Region. More weight it has been given will lead to a stronger regularization in bounding, and a small search space centering at Zy.

---

Under review as a conference paper at ICLR 2020
In Hoffer et al. (0177), they define an ultra slow diffusion phenomenon when they evaluate the distance from current weight to initial weight point with || - mull ~ logt. Interestingly. this result is entirely consistent with our Proximal Searching Region analysis, because for any t T, have ||2+11
zell (log t)
Now, summarise results follows:
1. Hyper-parameter 31: 31 exponential smooth eliminates the presence of imbalance in between the goal of minimizing loss of function and the constraints of searching in proximal region. In other words, Adam treats both conditions fairly.
2. First-order momentum:
the usage of m, leads to a smooth optimization trajectory which avoids the sharp twist such as SGD. It can benefit Adam if searching in the wrong direction, the momentum correction C, can compensate the party of penalty directly from the loss function.
3. Adam-Type algorithm: Adam- adam-Type algorithms such as AdamAL (this paper), AMSGrad AdaBound, AdaShift, NosAda, etc. can be regarded as making a correction on one of
regularization term (most on ||Q || 11)))
4. Learning rate: mirror descent corporate with implicit update makes learning rate (step size) act as a scalar factor of regularization.
By transferring the Adam to MDA-liked method, successfully disassemble the Adam updating my into two additive terms and identify their functionality separately. We mainly focus on the m part this section, we will move our eye on
the next section.
3.2 ADAM VE AND THE NON-CONVERGENCE OF ADAM
A common thinking of Adam's adaptive learning rate vor will treat U, as second moment approx- imation. However, in perspective, we regard it as adaptive regularize scalar and it performs implicit updates by replacing the explicit learning rate. Two adaptive regularize from AdaGrad and Adam show in below:
T=t
T=t
Adam: Σ OT
V (1
32)
AdaGrad:
T
(14)
By guiding with this intuition and our regularization budget definition, we can conclude that
1. Strictly speaking, non-Adam- algorithm such as SGD(M) has only proximal search- ing region center at 2,, however, Adam-Type algorithms achieve globally stabilizing reg- ulations via proximal searching region through {2,, ... II-1,<Te). Therefore, in our settings, SGD has a function with constant value where {a, = k/T = t). special case is when 7/2 = 1 where the SDG has a descending step size 7. we notice that E'=1 o = and o, 1. In fact, in theory, we can regard SGD with decreasing learning rate as an adaptive regularization with respect to training iterations.
2. Adam- Type algorithms, in contrast, have stronger bonding constraints with each proximal term || 11.. With the training iterations increasing, in order to retain the similar regularization strength, the natural way is increasing the regularization budget Df= such that B, 2 B.- We have the following comments for Adam:
2.1 Pro:
Non-decreasing regularization budget B, can benefit for Adam, however, unbounded budget causes the infinitely small proximal searching region. On the surface, training will stop without parameters updates. Adam overcomes this problem wisely, expo- nential moving average (EMA) performs as sliding window. In other words, the regularization budget is bounded.
2.2 Con:
EMA, on the one hand, controls the regularization budget in a range, but it fails to sat- isfy the primary requirement that regularization budget B, should be non-decreasing manner. Lots of previous works point out this issue such as (Reddi et al. 2019 Luo et al. 2019 Chen et al. 2018). However, the way they identify such problems is not natural, for example, the objective function with periodicity gradient rarely seen in real scenarios. Our way seems more easy access.
7

---

Under review as a conference paper at ICLR 2020
17
122
86
17
134
96
77
31
213
The number indicates the total swapping by AMSGrad at 0r,i- The darker heat map colors reveal the lower average swapping interval.
Figure I:
The non-convergence of Adam This issue was first identified by Reddi et al. al.a) (2019). which points out that the key issue in the convergence of Adam lies in the quantity
T
(15)
1/2
7--1
which assumes to be a non-negative value, but in training, this assumption does not always hold in Adam. Reddi et al. (2019) construct an objective function with periodicity gradient to illustrate the non-convergence of Adam which is hard to follow. Luo et al. (2019) using similar way but conduct a heuristic experiment shows that Adam will generate extreme learning rates (also extreme Ve value) that can affect the convergence. Fundamentally, they are identifying the same problem in different expressions. In Reedi et al. (2019) non non-convergence Theorem. the repeated occurrence gradient CC' is, in fact, the extreme learning rate. In analysis, the emergence of extreme learning rates is due to decreasing regularization budget B, B < O which is equivalent to < 0, the negative regularization coefficient o, O makes the corresponding proximal searching region ||=- - -rrl2 11 to be arbitrarily large when minimizing the Equation. 13 Adam. Again, the parameters behavior in out of the control manner for example | - 1r-112 400. To this end, Reddi et al.
2019) proposes very intuitive modification on Adam where
= max U2 1t-13
(16)
Although this setting solves the decreasing regularization budget issue, it still remains the problem so called nonalignment projection, state this problem in the next section.
3.3 NON-ALIGNMENT PROJECTION AND ADAMAL
AMSGrad (Reddi al. 2019) uses Equation. 16 to ensure the r, 0 for all t E T. They derive it mainly from an unrealistic objective function which has extreme gradient appearance in periodical manner. Does AMSGrad really outperform Adam or does AMSGrad's design follow the general sketch of Adam-Type algorithm? We conduct an experiment to illustrate the fundamental problem of AMSGrad (or its variant AdaShift). We call this problem illustrate the non-alignment projection problem, we trace a series of entries generated by AMSGrad and sample them from vector Ur,ajj our goal is counting the total number of times of that entry being swap with Ut and meanwhile, we record the interval between two swaps. We employ heat map to visualize this result. As shown in Figure [ we can find that (1) the different entry has very different swapping counts; (2) the swapping intervals are nonuniform. Note here sampling vr, from different neuron network layers and different batch size have different results, but we demonstrate the presence of such problems. To be more specific, we present a simple one-step AMSGrad swapping at iteration t and figure out the ill-condition problem.
non-alignment projection. To
Suppose in iteration f, we receive corresponding Ur at 7th element. Then in the next step, would like to perform the update of Uz,, to U141, via Ut+1. 32ur, + (1 32)92 based on the original design of the Adam. However, if we choose AMSGrad to evaluate 04+2,1, we first make the comparison between new 1t+1, and old Uz to ensure T++1 to be non-negative and choose i1+1, max("*+1 ). this swap happens, we will have 6 = U2,4 and AMSGrad uses for + update, and results in
2 = 320 + (1 B2 32)0 = B20i, + (1 1-22)00+22
(17)
However, the true step for updating 2442, should be
2 924441, + 32)9 B3u0, + B2 B2 + B2)
(18)
The difference is quite obvious show in Equation 17 and Equation 18 But another question is Why AMSGrad still working? AMSGrad can still work is because we choose very big 3n value as 0.999
which makes the 222 1242, However, iterative method will accumulate this small error into
8

---

Under review as a conference paper at ICLR 2020
each step and consequence, the non-alignment of v will lead the model to find suspicious local optimal. Another non-alignment refers to my and Uk. AMSGrad updates its 7t parameter by
Ma,
where k +
Recall the Zinkevich's greedy projection, we minimize the objective loss function relies on current T gradient approximation Ir then perform the projection by projector Pxx Px resolve the 2++11- We see the Ug is not the actual projection matrix for I₁ approximate by my.
To address above issue, recall the define of non-decreasing regularization budget, in Adam setting, B, 2 B equivalent to 2 U that is
0/ リ = 32) o. 0 -
Now, the solution for resolving Adam's 's non-convergence and non-alignment of AMSGrad clear. That is before we evaluate th, we modify di to guarantee the non-decreasing condition of 0--1 to et- We illustrate the update detail of AdamAL in Algorithm. Using a similar one-step example to
Algorithm AdamAL
1: Input F, initial step size a, B1,
2: set my 0, 14 =
3: for to T do
4: Jt = (((())
5: m, 8ime-1 1 + 31)gt
6: ft = max U1-1) B1)
7: Tt Bi0111 v
8: Ft+1 Px vi (zt
@ m+)
9: end for
illustrate how AdamAL can mitigate non-alignment issue when update P:422 32 + (1 - 32) = 33 + (1 32) + (1 -2)
adamaal U22
(19)
which reconstruct the 0142 in correct expression. The major difference of AdamAL and AMSGrad do not skip the gradient update for that guarantee the alignment of ge and as my We have the following bound for AdamAL.
Theorem 3.1. Let {x,} and {ve} be the sequences obtained from AdamAl (Algorithm 7. Tt n//22, Br.t = 31, 313 non-decreasing for all E [T]. Assume that feasible convex set F such for all xı. E F with bounded diameter D2 and [[V S G. For generated using the AdamAL,
we have the following bound on the regret:
Σ f((z)) - fe(x")
T
D3
d
1/2
D3
T
d
Ut
1/2
2m
(1
B1)
U1
2(1
31)
T1t
1=1
1=1
1=1
D
U
1/2
1/2
+
(20)
2(1 B1)
71
Mh-1
t=2
n + log T
+
(1 81)
7) 32)
4 EXPERIMENTS
In this section, we turn to an empirical study of different models to compare variants with popular optimization methods including SGD(M), Adam, and AMSGrad. We focus on image clas- sification tasks CIFARIO and CIFAR100 with different state-of-the-an deep models including ResNet18, ResNet50, VGG16 and VGG19. From the experiment results shown in Figure. 2 we notice that AdamAL outperforms Adam and AMSGrad! This result is desirable because fix the

---

Under review as a conference paper at ICLR 2020
Figure 2: Top: Accuracy of Cifarl0 on R8sNet18 and VGGI6: C0far100 on ResNet50 and VGG16; Top: Loss of Cifarl0 on ResNet18 and VGGI6; Ci on ResNet50 and VGG16:(Best see in color)
non-alignment projection issue residing in AMSGrad. In general, from the experiments, AdamAL constantly achieve 1% more accuracy gain than Adam. Notice that we only conduct our experiments with 80 epochs, this is due that fact that observe there is further accuracy improvement without performing any hyperparameter tuning. If we perform hyperparameter tuning, the results show in 1. AdamAL can finally reach 95% accuracy on average on test data, however, the best run of Adam is still lower than AdamAL. It is also worth mentioning that AMSGrad have even worse performance than Adam due alignmet.mnt. We also compare the result of AdamAL using different mini-batch settings, the result shows that Ad is also not sensitive min-batch size.
Algorithm
decay
Acc.
Adam
75, 125, 175
94.98
AMSGrad
75, 125, 175
94.60
AdamAL
75, 125, 175
95.13
VSGD
75, 125, 175
94.73
100
Table 3: hyperparameter tuning, learn- ing rate halve at iteration 75, 125, 175.
Figure 3: AdamAL in different min-batch
5 DISCUSS AND CONCLUSION
The Newton second-order method and The mystery of in Adam is fascinating. As we discussed in the section 2.2] using second moment describe i runs counter to its primary purpose. Because AdaMax (Kingma & Ba 2014), p-NosAdam (Huang et al. 2018) and Padam (Zhou et al.) 2018a), they apply the p-norm vt vi and Adam still performs well. Another evidence from AdaShift (Zhou et al.) 2018b), in their settings, Ut is no longer acting second moment, instead they treat 2007), it structures the relation from first-order to second-order Hessian with s H/G where gradient upper bound is G and H is the lower bound of Hessian. This relaxed condition results of ot to be possible approximation of Hessian with scaling factor a at iteration t.
learning rate scalar. our point of view, recall the a-exp-concavity (Hazan al.,
Beyond the Adam-Type method Assume the above assumption on of true, the fast convergence speed of Adam-Typp algorithms seems easy to be explained. We also notice that most of the previous works improve the Adam by modifying (or correcting) the term C in Equation [T Therefore, such corrections cannot speed up the Adam, instead, they define different regularization budget. To make one step furthers to Adam may rely on close approximations Hessian.
angle look the first-order method with adaptive learning rate. We decouple the Adam updating rule as an addition two regularized terms. this way, we can identify the intuition behind Adam-Type algorithm. Additionally, naturally figure out the non- convergence issue resides in AMSGrad and Adam, we propose another variant of Adam algorithm to mitigate such problem.
In this paper, present
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Lukas Balles and Philipp Hennig. Dissecting adam: The sign, magnitude and variance of stochastic gradients. arXiv preprint arXiv: 1oXiv:170.007770 2017.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
Sébastien Bubeck. Theory of convex optimization machine learning. arXiv preprint 15, 2014.
Augustin Cauchy. Méthode générale pour la résolution des systemes d' l'équutionn simultanées. Comp. Rend. Sci. Paris, 1847.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. arXiv preprint arXiv:/808.029411 2018.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120ul):2121-2159, 2011.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, (9(2-3):169-192) 2007.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. lecture, 2012.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. Advances in Neural Information Processing Systems, pp. 1731-1741, 2017.
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.07557, 2018.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: /4/2.6980, 2014.
Jyrki Kivinen and Manfred K Warmuth. Exponentiated gradient versus gradient descent for linear predictors. information and computation, 132(1):1-63, 1997.
Brian Kulis and Peter L Bartlett. Implicit online learning. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pp. 575-582, 2010.
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.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint
2019.
H. McMahan. follow-theereguulaiiee--eeee leader and mirror descent: Equivalence theorems and implicit updates. CORR, abs/1009.3244) 2010a.
H. Brendan McMahan. Follow-therrgguarizzaellddee and mirror descent: Equivalence theorems and implicit updates. CoRR, abs/1009.32400 2010b. URL htt.:tttp..//arrr..or//aa///////
3240
H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex opti- mization. arXiv preprint 1r02 2010.
Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley, New York, 1983.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv: /904 09999099477......000... 2019.

---

Under review as a conference paper at ICLR 2020
R Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal control and optimization, 14(5):877-88) 89,888 1976.
Matthew Streeter and H Brendan McMahan. Less regret via online conditioning. arXiv preprint arXiv:1002.4862, 2010.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4148 4158, 2017.
Lin Xiao, Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11(0ct):2543-255) 2010.
Matthew D Zeiler. Adadelta: adaptive learning method. arXiv preprint arXiv: urXiv:1212.570.. 2012.
Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv: 1808.888711 2018a.
Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, and Yong Yu. Adashift: Decorrelation and convergence of adaptive learning rate methods. arXiv preprint arXiv:1810.00143, 2018b.
Martin Zinkevich. Online convex programming and generalized intinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 928-936. 2003.
12

---

Under review as a conference paper at ICLR 2020
A AUXILIARY LEMMAS
Lemma A.I. McMMahan & Streeter 2010 Let Q E S++ with A Q². Let FF be convex set, and let u1, U2 E R with 21 (u] and x2 PA (2g)
||A(12 - z1)1l - ||A(uz u1)ll
(21)
Proof. Define:
1
1
B(r, = 2
- -)112 2(1 >11A(x-w)ll =
u) T)x((= - u)
(22)
we can write as:
I1 = arg min Bir, un)
(23)
#EF
Then, note that V ,, u1) Qr Qui, and so we must have (Qz1 Qu)) x1) 2 0:
otherwise for 8 sufficiently small the point 21 5(1, - xT) would belong F (by convexity) and
would be closer to than 21. Similarly, we must have (Qx2 - Qu2) (01 - 22) 2 0. Thus
(Qz1 Qui) (x2 - x1) - (Qr2 Qu2) (x1 - x2) 2 0
(x2 =11 [=((x= 21) + (u2 w1) T 'Q(12 x1) 2 0
(u2 u1) TTi)TQQp)) Q z1) 2 (x2 x1) T 'Q(12= x1)
Letting à u22 U1. and å D2 I1. have a =Q < à T Q². Since Q is
we have
(u 2) Q( 2 2 0, equivalently à Qu + à Q2- 2 Qu 2 0. Thus
a aTQu 2 - Qi 28 Qu 2 - a T Q2 + 2$ T Q2 = & Q0
(24)
and so
[AA(22-u)))) ú TQ@u 8 -Q= || - x1)11
(25)
B PROOF OF THEOREM 3.1
Proof. Let x= = arg min Et= fe(x), exist and F is feasible convex set. We have
J+41 py (xt - n 1 o m+)
min #EF ||0 1/1 @ (x (xx ne o m.))ll
(26)
Applying Lemma A. we have:
|| 1/4 o (It-1 x²]1 = 1| 1/4 @ (xt - 1/
3 m. x²'ll"
|| 1/4 ② (xt x² x²)11 + n 1/, + mzl12
2m (m - x²)
(27)
1//2/4 @ (xt x² x²"11² + n 10 @ m2,1
(8 + (1 (1-31111 31) Tt- - x
That is
(g - -x') 27/ - 31)
|1 1/4
o @xet1 - -1))1 = 1112// o (x. x² x'
+ 2(1 - 81)
m
10,
1/4
3 mell + 1-Bi (mi-1, - -x")
31
< 2m, (1
1110
1/4
@
(x++1
- >10) -10 1/4 @ (xx x² x11
81)
1/
|0,
1/4
m=|l3
31
1/4 mm
B1
o @z 11///
(x--="))²
2(1 81)
2(1
3,)
2 3:)
13

---

Under review as a conference paper at ICLR 2020
We rearrange the Equation 27 to have first inequality. And the second inequality follows the Cauchy- Schwarz and Yong's s inequality. Next, we have
fa(m))) - fa(x))
Σ ge, tt x²)
T
111o2" 1/4 (#1+1 x²) =1)1!=-110?" o (or x² x²)1 +
2(1 ?
B.) 11v
1/4 1/, melp? (28)
2nd (1 (:)
1m
31
mollo 1/4
mm-1ll
2tp.(1 B1) 10! @ (x. x >1
B1
2(1 B1)
The first inequality is due convexity of function f. To bound the above regret, we need the following intermediate result.
Lemma B.1. For the parameter seltings and conditions assumed in Theorem 3.1 we have:
T
17(1 11)- log T
d
nelly
1/4
@ mmllis
(29)
(1+ 3:) - 7) 32)
t=1
Proof. To prove, we need
m
1/4
m.
mellv 1/4
C @mell + TM
1/2
1=1
i=1
UT
d
((1 - B1) E} -T' gg,}²
mello, 1/4
C +mell++)
Σ
( (1 (1332)94 (32)
i=1
EE gg,0))
g5,a)²
nell%
- 1/1
@ mrll + +n((1 - -1
/T 1, + (1 32)g..)
ΣS11 87 2(T Σx 93
melloz
1/4
@ mill + 11(1 - 31 Σ
(B2ur--1 1,1 +(1 32)91..)
@ mell? + 711 - -
Σ/= 93.3
vellyz
1/4
1 B1
T(22 1, +(1- (2)
@ mmlll + 711 - -1)(11 - -197)
nelly;
1/4
1 B1
T(1 - 32) Eラ=1 1355 9
2 @mll? + 1711 - (1) - )37T)
Σ Li.
nelly
1/4
(1 33 T(1 (3)
3
jm1
melly;
1/4
o mmll
+ 171 - (1)(1111111 )
-
d
T
93.
(1 31) (22
1/
-
1=1 1=1
17(1 - -B:)(1 -8TT)
93.
melliz
1/4
c mmll2
T-
(1 + T 82)
Von.
j=1
+ 17(1 - B1)(1 -87T)
d T
W
mellyz
1/4
m2ll
199.al
(1 + (++33//T T(1 32
j=1
The first inequality follows from Pauchy-Schwarr inequality. We let 7 = 1/VB.. The last inequal- ity due to the Algorithm that وイ.4 max (gja, 1. By using similar upper bounds for all time
14

---

Under review as a conference paper at ICLR 2020
steps, the quantity in above can further be bounded as follows:
T
n B1)(L )
1/4
C mill=
19
(1+ B1) - B2)
j=l
n(1 - -31)
1 B7
d
1 ga
(1 + 31) /11 - (2) tm1
- ((1-)1)
T
(1
B 0
9t,1
(1+ + 31.v(1 (1 - -32)
vi
im1 t=l
j=l
711 (1-131))
d T
(1
(1+ 31) (1 -32)
Vt
1m1 1=1
j=1
71 - 31)
$ (1+ 8:)(1 7)((11 -B2)
Vi
jm1
111 - 31)
(1 + 81((1 7) (2)
j=1
n11 - -1) log'T T
191.,,ll2
(1 + 3,)(1 7), (1 32)
The first inequality due the fact that 1- 88 < and Σj= 7-1 1/(1 7)) The second
inequality is due to simple application of Sauchy-Schwan inequality. The final inequality is due to the following harmonic sum bound with Σ 1/t S (1 (1+ logT).
Now we return to the proof of Theorem 3.1 by using above lemma, we have:
f(())) - ff((=)(()) S
ggt Tz - x²)
T
11|e 1/4 2 (I1+1 - x0)11 - -1ee @ (zy - =1)
271e(1 (1 - 31)
1=1
31
n + logT T
d
+
||///
@ (xt 12--x" x²)1 +
21p
(1 31)
(1 (1 - 7) v1 B2)
T
1
1//!/4
1/4
3 (x1 xx x²)|12 +
1
1
1/4 3 0 -x*)11
21
81)
1 B1
277
[=1
1
11
1/4
(xt x²2
11/2/
1/4
(It
x=')) )|
+
}
(30)
2(1 - 31)
17
M--1
1/ log
+
(1 31)(1 7) V) (2) 1=1
1
114 (m1 -x,)²+
1/2
1
T
1,3
1/2
(14 x2
21
B1)
2(1
B1)
i=1
t=1 1=1
1/2
1
1
+
(Di - (²
}
2(1 - 31)
171
7/-1
1 logT
+
192:2,112
(1
-32)
1=1
15

---

Under review as a conference paper at ICLR 2020
For the sake of clarity, further suppose that the feasible region of parameter with bound D2, the Equation 30 becomes to:
D3
d
D2
T
d
1/2
f((a)) ff(x)) -
271
(1
B1)
1,
1/2
+
2(1
B1)
1/
1=1
1=1
==1 1=1
D2
1/2
10--
1, 1,4
1/2
(31)
2(1 81)
7
7/--1
t=2
M/1 log T
Σ
+
+ 31) 7) / B2)
==1
Therefore, we finish the proof of Theorem 3.1 as desired.
16


Reviews:
[{"review_id": "rJlnmSE-qH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzed a few issues of Adam, and proposed a new variant of Adam called AdamAL.  \n\nThere are quite a few issues: \n--It is not clear whether the heuristic observations are useful. \n--Theorem 3.1 does not even lead to the convergence of the algorithm. \n--The simulation does not show the advantage. \n--There are too many typos and grammar errors.\n\n1) Heuristic observations.\nOne main observation is that v_{t+1} = beta_2 v_t + (1 - beta_2) g_{t+1}^2 in the original Adam will be different from \\hat{v}_t defined in AMSGrad. The paper states \"...will accumulate this small error into each step\" ...\"will lead this model to find a suspicious local optimal\".  This claim makes little sense. Even if AMSGrad uses a different v from the original Adam, it is not necessarily bad. In addition, why is this related to \"suspicious local optimal\" (I suppose this paper intends to say \"spurious local optima\")? I do not have any intuition why this is related to spurious local minima. \n\n\n\n2) Too many typos and grammar errors. \n\nJust give one example. In the first paragraph of Sec. 3.3, there are at least 15 typos, and a few sentences are hard to read: \n   \"They derive it mainly from an unrealistic objective function\" --what does \"objective function\" mean? \n   \"Does it really solve the problem or dose this design violate the intuition of Adam-Type algorithm\"?  --what is the \"intuition\" to be violated? I roughly get the point of this sentence, but \"intuition\" is not a good word here.\n   \"To be more specifically, we present a simple one-step AMSGrad swapping at iteration t and figure out the ill-condition problem\". --What is \"ill-condition problem\"? It is not mentioned in this paragraph, and I don't know where it comes from.\n   In the whole paper, there are too many problematic sentences to enumerate (a very rough estimate: at least 30?)  It makes the paper very difficult to read.\n\n  \n\n   ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJg7hHphtH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis work proposed a framework to analyze both Adam-type algorithms and SGD-type algorithms. The authors considered both of them as specialized cases of mirror descent algorithms and provided a new algorithm AdamAL. The authors showed experiments to backup their theoretical results. \n\nPros:\n\nThe authors provided a novel framework to analyze Adam-type algorithms by using standard FTRL framework. It provides a unified viewpoint to consider a broad class of algorithms. The authors also provided a new algorithm AdamAL to overcome some shortcomings in previous algorithms. \n\nCons:\n\n- The novelty of this paper is limited. The authors provided a framework to analyze Adam-type algorithms. However, it seems that contribution is more conceptual rather than practical. I suggest the authors add more examples or theorems to show the superiority of their mirror descent framework. \n- Some of the explanations in this paper may be wrong. For instance, around equation 17, the authors suggested that if the swap happens, then v_{t+1} = v_t. That is not correct since the swap happens for each coordinate. Meanwhile, the explanation about why AdamAL is better than AMSgrad is quite poor since the update rule of AMSgrad can also guarantee the coordinate decreasing of v_t. I suggest the authors explain more on the algorithm design. \n- The authors should complete the proof of Theorem 3.1. \n- The settings of experiments are limited. The authors should at least compare AdamAL with other baseline algorithms on some modern deep learning tasks including Imagenet.  \n\nMinor comments:\n\n- Below equation 8, detail -> details.\n- The authors should add the definition of 1:t in subscript for g_{1:t} or \\phi_{1:t}.\n- Page 6, the first paragraph, logt-> \\log t\n- This paper lacks some references in this area. \n\nJ. Chen and Q. Gu. Closing the generalization gap of adaptive gradient methods in training\ndeep neural networks. arXiv preprint arXiv:1806.06763, 2018.\nWard, R., Wu, X. and Bottou, L. (2018). Adagrad stepsizes: Sharp convergence over nonconvex\nlandscapes, from any initialization. arXiv preprint arXiv:1806.01811 .\nLi, X. and Orabona, F. (2018). On the convergence of stochastic gradient descent with adaptive\nstepsizes. arXiv preprint arXiv:1805.08114 .", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1gj6JT7qr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to study some weaknesses of Adam and AMSGrad and propose a new method called AdamAL that is evaluated on CIFAR10.\n\nI am not from this area, but unfortunately I find this paper to not be rigorously written or organized. Section 3.3 for instance which discusses the non-alignment projection issue with AMSGrad is not rigorously written. There are no proofs to any theorems and even some of the theorems/corollaries are not written rigorously. \n\nOrganization-wise I feel it is difficult to see where the paper is going and some sort of outline / notation box would help. \n\nEmpirically, there are results on one dataset CIFAR10 that shows the author's proposed variant AdamAL works better. However, it is not the detailed types of experiments I was expecting of a paper that points out specific issues in AMSGrad. Shouldn't the experiments be showing these weaknesses in some sort of controlled setting? \n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors draw upon online convex optimization in order to derive a different interpretation of Adam-Type algorithms, allowing them to identify the functionality of each part of Adam. Based on these  observations, the authors derive a new Adam-Type algorithm,  AdamAL and test it in 2 computer vision datasets using 3 CNN architectures. The main concern shared by all reviewers is the lack of novelty but also rigor both on the experimental and theoretical justification provided by the authors. After having read carefully the reviews and main points of the paper, I will side with the reviewers, thus not recommending acceptance of this paper. 
Decision: Reject