Title: 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 our understanding. 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 algorithm, we receive a clear map of the functionality of each term in Adam. In addition, this new angle brings us a new insight on identifying the non-convergence issue of Adam and explaining the superior convergence speed of Adam than other first-order methods. Moreover, we provide a 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.

1. INTRODUCTION:

In recent years, first-order optimization algorithms with adaptive learning rate have become the dominant method to train deep neural networks because these methods show extraordinary power in solving large-scale machine learning optimization problems. By cooperating with first-order information, 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 regularization functions for bounding objective function parameters based on the loss functions observed at each iteration. Then, in Streeter & McMahan (2010) , they demonstrate that the convergence rates can often be dramatically improved through the use 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 et al., 2011) carefully chooses the preconditioner and provides the first practical adaptive algorithm with a 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 accumulating all the past gradients as its learning rate. And this unbounded learning rate becomes extremely small when one has a large number of training iterations. To address this, several variants of AdaGrad, such as AdaDelta (Zeiler, 2012) and RMSProp (Hinton et al., 2012) have been proposed to mitigate the rapid decay of the learning rate. Based on these, Adma (Kingma & Ba, 2014) incorporating with first momentum correction accelerates the convergence speed of first-order optimization algorithms to a new height. The use of exponential moving average (EMA) in Adam becomes a key to Adam's success. Up to this point, we can summarize the adaptive or non-adaptive first-order optimization algorithms as follows.

Denote g t ∈ R d as the gradient of generic optimization problem f with respect to its parameters x ∈ R d at iteration t, then the generic updating rule of adaptive methods can be expressed as (Reddi et al., 2019) :

x t+1 = x t - η t √ v t m t (1)

where denotes the entry-wise or Hadamard product and the α t is the base learning rate. In the equation above, m t = ϑ(g 1 , • • • , g t ) is a function related to the historical gradients up to t; and v t = υ(g 1 , • • • , g t ) is a function that produces a d-dimensional vector with non-negative entry; The design of v t is simple of non-adaptive methods, such as vanilla stochastic gradient descent (Vanilla SGD), where we have v t = I, however, it is crucial for Adam-Type algorithms. For Adam, in particular, the m t and v t are computed by EMA of gradient, with coefficient β 1 and β 2 where

m t = (1 -β 1 ) i=t i=1 β t-i 1 g i and v t = (1 -β 2 ) i=t i=1 β t-i 2 g 2 i (2)

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 optimization problems remains an open question (Chen et al., 2018) . In addition, the generalization ability and out-of-sample behavior of Adam-Type methods are even worse than traditional non-adaptive counterparts such as Vanilla SGD (Wilson et al., 2017) .

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., 2018b; 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 correction methods to improve Adam, we think the mechanism of Adam-Type algorithms is still unclear. For example, one common thinking about about m t and v t in Adam is first and second moments of unbiased estimator g t , however, why this second moment can be used as adaptive learning rate? Does the v t really behave as the second moment of the gradient g t ? Also, another commonly asked question is where the Adam adopts such a faster convergence speed than other first-order methods?

These mysterious questions on adaptive methods finally leads us to rethink the Adam-Type algorithms in a neutral way. In this paper, we provide a new insight into Adam-Type algorithms, which brings a new perspective of comprehension on 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 (2014) framework, which limits our understanding. In fact, when we look back to the origin of adaptive learning rate methods mentioned in Streeter & McMahan (2010) , we notice that the design of Adam is highly related to adaptive regularization of follow-the-proximally-regularized-leader (FTPRL) method and it can also be regarded as a variant of traditional mirror descent method (Xiao, 2010) . The more detail and our motivation can be found in the next section. For simplicity, we use standard Adam as our touchstone through the paper to convey our main idea, and their variants follow the same thoughts. Now, we summarize our contribution in three folds:

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-Type algorithms and we provide a new 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 x ∈ R d we denote its i-th entry by x i ; We use ||x|| to denote its l 2 norm; for a vector x t in the t-th iteration, the i-th coordinate of x t is denoted as x t,i . We also define x 1:t = t i=1 x i . Given two vectors x, y ∈ R, we use x, y to denote their inner product, x y to denote element-wise product, x y to denote entry-wise division, the max(x, y) to denote entry-wise 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 1 2 to denote √ M .

2.1. PRELIMINARIES:

Nonlinear projected subgradient methods and mirror descent algorithm Iterative gradient descent (GD) scheme, which can be traced back to (Cauchy, 1847) , is the simplest strategy to 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 descent (PGD) algorithm with following updating rules:

x t+1 = P X (x t -ηf (x t )) (standard PGD) x t+1 = P A X (x t -η t g t ) (Zinkevich OGSP) (3)

where P A X is a distance-based projector denoting the projection of a point y onto X by P A X (y) = arg min x∈X ||x -y|| A , and || • || A = x, Ax , and g t ∈ ∂f t (x t ) = f (x t ) is the subgradient of the objective function f t (•). 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:

x t+1 = arg min x∈X { f (x t ), x + 1 η t D ψ (•)} (4)

the nonlinear projection therefore encoded in the term D ψ . By replacing the Euclidean quadratic norms in Equation. 3 with more general distance-liked settings such as Bregman distance function D ψ (•) define on ψ(•), the equivalence of PGD algorithm and MDA has been proved by Beck & Teboulle (2003) . For example, the simplest version of MDA is that: taking ψ(x) = 1 2 ||x|| 2 2 , and

D ψ (x, x t ) = 1 2 ||x -x t || 2

2 then plugging into Equation. 4, we have:

x t+1 = arg min x∈X { g t , x + 1 2η t ||x -x t || 2 2 } (5)

Update scheme in the above equation. 5 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 x, and rearranging the formula:

EQUATION

Now, we see the last two expressions in Equation. 6 are well-known subgradient descent update. We restate the proposition 3.2 in Beck & Teboulle (2003) as: Proposition 1. Assume X is a closed convex subset in R with non-empty interior, and objective function f : X → R is a convex and Lipschitz function. Suppose the optimal set of x denoted by X * is non-empty, we can compute the subgradient of f at x as g ∈ ∂f (x). For a convex mirror mapping function ψ : X → R with conjugate function ψ * defined by ψ * (y) = max x∈X { x, y -ψ(x)}.

Then the sequence {x t } ⊆ X generated by MDA is equivalent to the sequence generated by PGD.

We state the equivalence of PGD algorithm and MDA, particularly, the general gradient descent (or SGD) can be directly derived from the Equation. 6.

Follow the proximally-reqularized leader (FTPRL) FTPRL is introduced by McMahan & Streeter (2010) belongs to the family of follow-the-regularized-leader (FTRL) algorithms such as Regularized Dual Averaging (Xiao, 2010) . In general, FTRL-Type has following update rule:

EQUATION

where the subgradient of objective function f τ (x τ ) is approximated by the gradient at x τ and R 1:t (x) is defined as regularization. Particularly, the formal FTPRL is:

x t+1 = arg min x∈X {g 1:t • x + φ 1:t • x + Ψ(x) + 1 2 t τ =1 ||Q 1 2 τ (x -x τ )|| 2 2 } (8)

with φ 1:t • x + Ψ(x) can be considered as non-smooth composite term which is orthogonal to our Table 1 : An overview of first-order optimization methods using the generic framework

SGD SGDM AdaGrad RMSProp Adam m t g t t i=1 β t-i g i g t g t (1 -β 1 ) t i=1 β t-i 1 g i v t I I t i=1 g 2 i (1 -β) t i=1 β t-i g 2 i (1 -β 2 ) t i=1 β t-i 2 g 2 i lr η t η t η 0 1 √ vt η 0 1 √ vt η 0 1 √ vt

paper, more details can be found in McMahan (2010b) . The last term in the above equation is stabilizing regularization to ensure low regret. We mention that the Q τ can 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. 4 regularizing the parameter to be close to the origin, on contrast, FTPRL is regularizing the parameter at current feasible point. No surprising, McMahan (2010a) propose the equivalence proof of FTPRL and a variation algorithm of the MDA as follow.

Proposition 2. (McMahan, 2010a ) Let R t be a sequence of differentiable convex functions (∇R t (0) = 0), and let Ψ be an arbitrary convex function. Define the proximal-MDA with updating rule:

x t+1 = arg min x∈X { g t (x t ), x + Ψ(x) + D R1:t (•)} (9)

where the Bregman distance function D Rt with respect to R t where R t (x) = R t (x -x t ). And applying FTPRL to the same objective function, with:

EQUATION

when φ t ∈ ∂Ψ, such that g 1:t + φ 1:t + ∇R 1:t (x t ) = 0. Then the two above update scheme are equivalent.

At this moment, we state a series of equivalence proposition from FTPRL to proximal-MDA (variation 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 unofficially 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) Non-Adam-type online gradient descent algorithms including SGD, SGD with momentum, Polyak's HB and Nesterov's accelerated gradient method can be easily understood as first order optimization with different momentum function. And, interestingly, most of them have physical interpretations. However, as shown in Table 1 , Adam-Type algorithms do not rely on the non-increasing learning rate when iteratively updating their parameters. Instead, they perform adaptively learning rate element-wise on parameters according to the first order information. However, this leads to the most mysterious part in the Adam-Type algorithm where the adaptive update is represented as -η0

√ vt m t . One common interpretation of this updating representation is regarding -η0 √ vt as adaptive learning rate, and regarding m t as general first order gradient. However, we can not treat Adam-Type algorithm in this way because the first order information g t resides in both m t and v t and we are unable to simply decorrelate them as common gradient with step-size scheme. Another possible interpretation of such updating is 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: can we interpret Adam-Type algorithm as a variant of mirror descent method? Before answering the question, let us explain why we present Adam-Type algorithm as MDA is beneficial. We summary below: Table 2 : An overview of first-order optimization methods using Mirror Descent expression

SGD SGDM AdaGrad Adam A g1:t • x (g1:t - i=t,j=t i=1 β j+1-i ) • x gt • x (g1:t - i=t,j=t i=1 β j+1-i ) • x C 1 2 ||x -xτ || 2 2 1 2 ||x -xτ || 2 2 1 2 t τ =1 στ ||x -xτ || 2 2 1 2 t τ =1 στ ||x -xτ || 2 2 ρ 1 1 1-β 1 1

* Term A, C, ρ are defined in Equation 11. 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 to efficiently compute the parameters. The mirror descent algorithms, in fact, adopt implicit update rules very well, therefore, the explicit update will roll into some regularizedliked terms which can elaborate more insights. In contrast, like Adam, the learning rate is explicitly defined as η0 √ vt 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 to the construction function with respect to the first-order gradient g. The underlying relation between two functions m t and v t can not be decorrelated. However, as shown in Table 2 , we represent Adam-Type algorithms in MDA way so that we can separate the numerator and denominator as simple additive scheme where the hard-understanding division disappears and meanwhile, the alignment of m t and v t 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 equivalence guarantee so that we can transform safely. As we discuss in previous (Proposition 1& 2), we successfully build such a bridge in between two types of algorithm.

In general, these first-order algorithms can be written in FTPRL style (also see Table 2 ):

EQUATION

The understanding of above representation is highly related to our analysis on Adam-Type algorithms. Term A has two parts, the first part g 1:t • x is an approximation to f 1:t based on the gradient; the second part C 1:t • x 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 as l 2 -regularization. In addition, term C stabilizing regularization plays a crucial role in this transformation because (1) the implicit updates from x t to x t+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 ρ is a balancing coefficient, aims at controlling the tendency of minimization between term A and C. Smaller ρ 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. 8 (for the sake of simplicity, we do not consider the Ψ):

EQUATION

)

where the ρ = 1, C 1:t is zero, and Q τ sets to be

Q τ = σ 2 τ I. If Vanilla SGD with learning rate η t = 1 t , the t τ =1 σ τ = t. If it with fixed learning rate η t = 1 k , then t τ =1 σ τ = k.

To be mentioned here, fixed learning rate SGD is kind of special, it can be easily explained as Equation. 5, however, in FTPRL format (Equation. 12), we need to be more careful.

Mirror descent like Vanilla SGD with non-increasing learning rates shows the great insight of understanding current algorithms. First, we are always looking for the next step x t+1 in the opposite direction of the current gradient because cos(π) = -1 minimize Equation. 12. Second, x t+1 is being bound in a region centered at previous step x t . This is 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 (2010b) confirm this view. Third, t τ =1 σ τ should be non-decreasing alone time. Similar, when σ τ gets smaller, the bounding region expands, reducing the convergence speed.

3. NEW PERSPECTIVE ON ADAM:

In this section, we deliver a 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.

EQUATION

where both β 1 ≤ 1 (commonly chose β 1 = 0.9), the

t τ =1 σ τ,i = (1 -β 2 ) τ =t τ =1 β t-τ 2 g 2 τ,i

in Adam settings with β 2 = 0.999. In SGDM, t τ =1 σ * τ performs differently, (1) SGDM is nonadaptive method, the τ * applies to all entry on the x; (2)

t τ =1 σ * σ = t if we have learning rate η t = 1

t , it also means σ * = 1 for all τ ∈ 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 ρ = 1 while SGDM has ρ = 1 1-β1 = 10 (a common setting of β = 0.9). Recall the previous section, by definition of ρ, we have following corollary: Corollary 2. Compare to Vanilla SGD or Adam, SGDM has larger ρ 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. 13.Adam, Proximal Searching Region refers to D = ||x -x τ || 2 2 , this Euclidean quadratic norm reflects the geometry of given constraints feasible set X . We can also treat it as a regularization process. This region is inversely proportional (D ∝ 1 B ) to the Regularization Budget defined below.

Regularization Budget refer to B = t τ =1 σ τ,i , it indicates total "weight" we can 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 x τ .

In Hoffer et al. (2017) , they define an ultra slow diffusion phenomenon when they evaluate the distance from current weight to initial weight point with ||x t -x 0 || 2 2 ∼ log t. Interestingly, this result is entirely consistent with our Proximal Searching Region analysis, because for any t ∈ T , we have ||x t+1 -x t || ∼ (log t) = 1 t . Now, we summarise our results as follows:

1. Hyper-parameter β 1 : β 1 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 t 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-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

1 2 τ ||x -x τ || 2 2

). 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, we successfully disassemble the Adam updating mt √ vt into two additive terms and identify their functionality separately. We mainly focus on the m t part in this section, we will move our eye on 1 √ vt in the next section.

3.2. ADAM V t AND THE NON-CONVERGENCE OF ADAM:

A common thinking of Adam's adaptive learning rate 1 √ vt will treat v t as second moment approximation. However, in our 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:

EQUATION

By guiding with this intuition and our regularization budget definition, we now can conclude that 1. Strictly speaking, non-Adam-Type algorithm such as SGD(M) has only proximal searching region center at x t , however, Adam-Type algorithms achieve globally stabilizing regulations via proximal searching region through {x 1 , x 2 , • • • , x t-1 , x t }. Therefore, in our settings, SGD has σ function with a constant value where {σ τ = k|τ = t}. A special case is when η t = 1 t where the SDG has a descending step size 1 t , we notice that t τ =1 σ τ = t and σ t = 1. In fact, in our 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 ||x -x τ || 2 2 . With the training iterations increasing, in order to retain the similar regularization strength, the natural way is increasing the regularization budget t τ =1 σ τ such that B t ≥ B t-1 . We have the following comments for Adam: 2.1 Pro: Non-decreasing regularization budget B t 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, exponential moving average (EMA) performs as a 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 satisfy the primary requirement that regularization budget B t should be a 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 to access.

122 86 17 134 96 77 31 213 17 The non-convergence of Adam This issue was first identified by Reddi et al. (2019) , which points out that the key issue in the convergence of Adam lies in the quantity 

EQUATION

EQUATION

Although this setting solves the decreasing regularization budget issue, it still remains the problem so called nonalignment projection, we state this problem in the next section.

3.3. NON-ALIGNMENT PROJECTION AND ADAMAL:

AMSGrad (Reddi et al., 2019) uses Equation. 16 to ensure the Γ t ≥ 0 for all t ∈ 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 as non-alignment projection. To illustrate the non-alignment projection problem, we trace a series of entries generated by AMSGrad and sample them from vector v t,i:j , our goal is counting the total number of times of that entry being swap with v t,i:j and meanwhile, we record the interval between two swaps. We employ a heat map to visualize this result. As shown in Figure 1 , we can find that (1) the different entry has very different swapping counts; (2) the swapping intervals are nonuniform. Note here sampling v t,i 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.

Suppose in iteration t, we receive a corresponding v t,i at i th element. Then in the next step, we would like to perform the update of v t,i to v t+1,i via v t+1,i = β 2 v t,i + (1 -β 2 )g 2 t+1,i based on the original design of the Adam. However, if we choose AMSGrad to evaluate v t+2,i , we first make the comparison between new v t+1,i and old v t,i to ensure Γ t+1 to be non-negative and choose vt+1,i = max{v t+1,i , v t,i }. If this swap happens, we will have vt+1,i = v t,i and AMSGrad uses it for t + 2 update, and results in

EQUATION

However, the true step for updating v t+2,i should be

EQUATION

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 β 2 value as 0.999 which makes the v ams t+2,i ≈ v t+2,i . However, iterative method will accumulate this small error into each step and as a consequence, the non-alignment of v t will lead the model to find a suspicious local optimal. Another non-alignment refers to m t and v k , AMSGrad updates its i th parameter by

x t+1,i = x t,i - m t,i √ v k,i

where k = t

Recall in the Zinkevich's greedy projection, we minimize the objective loss function relies on current gradient approximation g t then we perform the projection by projector P

- √ v k X

to resolve the x t+1 . We see the v k is not the actual projection matrix for x t approximate by m t .

To address above issue, recall the define of non-decreasing regularization budget, in Adam setting,

B t ≥ B t-1 equivalent to v t ≥ v t-1 that is v t -v t-1 = (1 -β 2 )(g 2 t -v t-1 ) ≥ 0 ⇒ g 2 t -v t-1

≥ 0 Now, the solution for resolving Adam's non-convergence and non-alignment of AMSGrad is clear. That is before we evaluate v t , we modify g t to guarantee the non-decreasing condition of v t-1 to v t . We illustrate the update detail of AdamAL in Algorithm.1. Using a similar one-step example to

Algorithm 1 AdamAL 1: Input x ∈ F, initial step size α, β 1 , β 2 , 2: set m t = 0, v t = 0 3: for t = 1 to T do 4: g t = ∇f t (x t ) 5: m t = β 1 m t-1 + (1 -β 1 )g t 6: ĝt = max{g 2 t , v t-1 } 7: v t = β 1 v t-1 + (1 -β 1 ) ĝt 8: x t+1 = P - √ vt X (x t -ηt √ vt

m t ) 9: end for illustrate how AdamAL can mitigate non-alignment issue when update v t+2 :

EQUATION

)

which reconstruct the v t+2 in correct expression. The major difference of AdamAL and AMSGrad is we do not skip the gradient update for v t so that we guarantee the alignment of g t and v t so as m t . We have the following bound for AdamAL. Theorem 3.1. Let {x t } and {v t } be the sequences obtained from AdamAl (Algorithm 1). η t = η/t 1/2 , β 1,t = β 1 , β 1,t non-decreasing for all t ∈ [T ]. Assume that feasible convex set F such for all x t ∈ F with bounded diameter D 2 and ||∇f t (x t )|| ≤ G. For x t generated using the AdamAL, we have the following bound on the regret:

T t=1 f t (x t ) -f t (x * ) ≤ D 2 2 2η 1 (1 -β 1 ) d i=1 v 1/2 1,i + D 2 2 2(1 -β 1 ) T t=1 d i=1 v 1/2 t,i η t + D 2 2 2(1 -β 1 ) T t=2 d i=1 { v 1/2 t,i η t - v 1/2 t-1,i η t-1 } + η √ 1 + log T (1 + β 1 )(1 -γ) (1 -β 2 ) d i=1 ||g 1:T,i || 2 (20)

4. EXPERIMENTS:

In this section, we turn to an empirical study of different models to compare new variants with popular optimization methods including SGD(M), Adam, and AMSGrad. We focus on image classification tasks on CIFAR10 and CIFAR100 with different state-of-the-art 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 we fix the 

5. DISCUSS AND CONCLUSION:

The Newton second-order method and v t The mystery of v t in Adam is fascinating. As we discussed in the section 2.2, using second moment to describe v t 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 to v t as v 1/p t and Adam still performs well. Another evidence from AdaShift (Zhou et al., 2018b) , in their settings, v t is no longer acting as second moment, instead they treat it as a learning rate scalar. In our point of view, recall the α-exp-concavity (Hazan et al., 2007) , it structures the relation from first-order to second-order Hessian with α ≤ H/G 2 where gradient upper bound is G and H > 0 is the lower bound of Hessian. This relaxed condition results of g 2 t to be an possible approximation of Hessian with scaling factor α at iteration t. Beyond the Adam-Type method Assume the above assumption on g 2 t is true, the fast convergence speed of Adam-Type 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 11. 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 of Hessian.

In this paper, we present a new angle to look at the first-order method with adaptive learning rate. We decouple the Adam updating rule as an addition of two regularized terms. In this way, we can identify the intuition behind Adam-Type algorithm. Additionally, we naturally figure out the nonconvergence issue resides in AMSGrad and Adam, we propose another variant of Adam algorithm to mitigate such problem.

A AUXILIARY LEMMAS:

Lemma A.1. (McMahan & Streeter, 2010) 

EQUATION

Proof. Define:

EQUATION

we can write as:

EQUATION

Then, note that ∇ x B(x, u 1 ) = Qx -Qu 1 , and so we must have (Qx 1 -Qu 1 ) (x 2 -x 1 ) ≥ 0; otherwise for δ sufficiently small the point x 1 + δ(x 2 -x 1 ) would belong to F (by convexity) and would be closer to u 1 than x 1 . Similarly, we must have

EQUATION

and so

EQUATION

B PROOF OF THEOREM 3.1

Proof. Let x * = arg min x∈F T t=1 f t (x), exist and F is feasible convex set. We have

EQUATION

Applying Lemma A.1 we have:

||v 1/4 t (x t+1 -x * )|| 2 ≤ ||v 1/4 t (x t -η t v -1 2 t m t -x * )|| 2 = ||v 1/4 t (x t -x * )|| 2 + η 2 t ||v -1 4 t m t || 2 -2η t m t , x t -x * = ||v 1/4 t (x t -x * )|| 2 + η 2 t ||v -1 4 t m t || 2 -2η t β 1 m t-1 + (1 -β 1 )g t , x t -x * (27) That is gt,xt -x * ≤ 1 2ηt(1 -β1) [||v 1/4 t (xt+1 -x * )|| 2 -||v 1/4 t (xt -x * )|| 2 ] + ηt 2(1 -β1) ||v -1/4 t mt|| 2 + β1 1 -β1 mt-1, xt -x * ≤ 1 2ηt(1 -β1) [||v 1/4 t (xt+1 -x * )|| 2 -||v 1/4 t (xt -x * )|| 2 ] + ηt 2(1 -β1) ||v -1/4 t mt|| 2 + β1 2(1 -β1) ηt||v -1/4 t mt-1|| 2 + β1 2ηt(1 -β1) ||v 1/4 t (xt -x * )|| 2

We rearrange the Equation 27 to have first inequality. And the second inequality follows the Cauchy-Schwarz and Yong's inequality. Next, we have

T t=1 ft(xt) -ft(x * ) ≤ T t=1 gt, xt -x * ≤ T t=1 { 1 2ηt(1 -β1) [||v 1/4 t (xt+1 -x * )|| 2 -||v 1/4 t (xt -x * )|| 2 ] + ηt 2(1 -β1) ||v -1/4 t mt|| 2 + β1 2(1 -β1) ηt||v -1/4 t mt-1|| 2 + β1 2ηt(1 -β1) ||v 1/4 t (xt -x * )|| 2 } (28)

The first inequality is due to convexity of function f . To bound the above regret, we need the following intermediate result.

Lemma B.1. For the parameter settings and conditions assumed in Theorem 3.1, we have:

EQUATION

Proof. To prove, we need

T t=1 η t ||v -1/4 t m t || 2 = T -1 t=1 η t ||v -1/4 t m t || 2 + η T d i=1 m 2 T,i v 1/2 T,i = T -1 t=1 η t ||v -1/4 t m t || 2 + η d i=1 ((1 -β 1 ) T j=1 β T -j 1 g j,i ) 2 T (β 2 v t-1,i + (1 -β 2 )ĝ t,i ) = T -1 t=1 η t ||v -1/4 t m t || 2 + η(1 -β 1 ) 2 d i=1 ( T j=1 β T -j 1 g j,i ) 2 T (β 2 v t-1,i + (1 -β 2 )ĝ t,i ) ≤ T -1 t=1 η t ||v -1/4 t m t || 2 + η(1 -β 1 ) 2 d i=1 T j=1 β 2(T -j) 1 T j=1 g 2 j,i T (β 2 v t-1,i + (1 -β 2 )ĝ t,i ) = T -1 t=1 η t ||v -1/4 t m t || 2 + η(1 -β 1 )(1 -β 2T 1 ) 1 + β 1 d i=1 T j=1 g 2 j,i T (β 2 v t-1,i + (1 -β 2 )ĝ t,i ) = T -1 t=1 η t ||v -1/4 t m t || 2 + η(1 -β 1 )(1 -β 2T 1 ) 1 + β 1 d i=1 T j=1 g 2 j,i T (1 -β 2 ) T j=1 β T -j 2 ĝj,i = T -1 t=1 η t ||v -1/4 t m t || 2 + η(1 -β 1 )(1 -β 2T 1 ) (1 + β 1 ) T (1 -β 2 ) d i=1 T j=1 g 2 j,i T j=1 β T -j 2 ĝj,i ≤ T -1 t=1 η t ||v -1/4 t m t || 2 + η(1 -β 1 )(1 -β 2T 1 ) (1 + β 1 ) T (1 -β 2 ) d i=1 T j=1 g 2 j,i β T -j 2 ĝj,i = T -1 t=1 η t ||v -1/4 t m t || 2 + η(1 -β 1 )(1 -β 2T 1 ) (1 + β 1 ) T (1 -β 2 ) d i=1 T j=1 γ T -j g 2 j,i ĝj,i ≤ T -1 t=1 η t ||v -1/4 t m t || 2 + η(1 -β 1 )(1 -β 2T 1 ) (1 + β 1 ) T (1 -β 2 ) d i=1 T j=1 γ T -j |g j,i |

The first inequality follows from Cauchy-Schwarz inequality. We let γ = 1/ √ β 2 . The last inequality due to the Algorithm 1 that ĝj,i = max{g j,i , v j-1,i }. By using similar upper bounds for all time steps, the quantity in above can further be bounded as follows: (1 -β 2j 1 )γ j-t √ j = η(1 -β 1 )

(1 + β 1 ) (1 -β 2 ) d i=1 T t=1 |g t,i | t j=1 (1 -β 2j 1 )γ j-t √ t ≤ η(1 -β 1 ) (1 + β 1 )(1 -γ) (1 -β 2 ) d i=1 T t=1 |g t,i | t j=1 1 √ t ≤ η(1 -β 1 ) (1 + β 1 )(1 -γ) (1 -β 2 ) d i=1 ||g 1:T,i || 2 t j=1 1 t ≤ η(1 -β 1 ) √ 1 + log T (1 + β 1 )(1 -γ) (1 -β 2 ) d i=1 ||g 1:T,i || 2

The first inequality due to the fact that 1 -β 2j 1 < 1 and T j=1 γ j-t ≤ 1/(1 -γ). The second inequality is due to simple application of Cauchy-Schwarz inequality. The final inequality is due to the following harmonic sum bound with T t=1 1/t ≤ (1 + log T ). Now we return to the proof of Theorem 3.1, by using above lemma, we have:

T t=1 f t (x t ) -f t (x * ) ≤ T t=1 g t , x t -x * ≤ T t=1 { 1 2η t (1 -β 1 ) [||v 1/4 t (x t+1 -x * )|| 2 -||v 1/4 t (x t -x * )|| 2 ] + β 1 2η t (1 -β 1 ) ||v 1/4 t (x t -x * )|| 2 } + η √ 1 + log T (1 + β 1 )(1 -γ) (1 -β 2 ) d i=1 ||g 1:T,i || 2 = 1 2η 1 (1 -β 1 ) ||v 1/4 t (x 1 -x * )|| 2 + 1 1 -β 1 T t=1 1 2η t ||v 1/4 t (x t -x * )|| 2 + 1 2(1 -β 1 ) T t=2 { ||v 1/4 t (x t -x * )|| 2 η t - ||v 1/4 t-1 (x t -x * )|| 2 η t-1 } + η √ 1 + log T (1 + β 1 )(1 -γ) (1 -β 2 ) d i=1 ||g 1:T,i || 2 = 1 2η 1 (1 -β 1 ) d i=1 v 1/2 1,i (x 1,i -x * ,i ) 2 + 1 2(1 -β 1 ) T t=1 d i=1 v 1/2 t,i (x t,i -x * ,i ) 2 η t + 1 2(1 -β 1 ) T t=2 d i=1 (x t,i -x * ,i ) 2 { v 1/2 t,i η t - ||v 1/2 t-1,i η t-1 } + η √ 1 + log T (1 + β 1 )(1 -γ) (1 -β 2 ) d i=1 ||g 1:T,i || 2 (30)

For the sake of clarity, we further suppose that the feasible region of parameter x with bound D 2 , the Equation 30 becomes to:

T t=1 f t (x t ) -f t (x * ) ≤ D 2 2 2η 1 (1 -β 1 ) d i=1 v 1/2 1,i + D 2 2 2(1 -β 1 ) T t=1 d i=1 v 1/2 t,i η t + D 2 2 2(1 -β 1 ) T t=2 d i=1 { v 1/2 t,i η t - ||v 1/2 t-1,i η t-1 } + η √ 1 + log T (1 + β 1 )(1 -γ) (1 -β 2 ) d i=1 ||g 1:T,i || 2 (31)

Therefore, we finish the proof of Theorem 3.1 as desired.

:



Figures and Tables:

Figure 1: The number indicates the total swapping by AMSGrad at v t,i . The darker heat map colors reveal the lower average swapping interval.

Figure 2: Top: Accuracy of Cifar10 on ResNet18 and VGG16; Cifar100 on ResNet50 and VGG16; Top: Loss of Cifar10 on ResNet18 and VGG16; Cifar100 on ResNet50 and VGG16;(Best see in color)

15)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. AndLuo et al. (2019) using a similar way but conduct a heuristic experiment shows that Adam will generate extreme learning rates (also extreme v t value) that can affect the convergence. Fundamentally, they are identifying the same problem in different expressions. In Reddi et al. (2019) non-convergence Theorem.1 the repeated occurrence gradient -C is, in fact, the extreme learning rate. In our analysis, the emergence of extreme learning rates is due to decreasing regularization budget B t -B t-1 < 0 which is equivalent to Γ < 0, the negative regularization coefficient σ τ < 0 makes the corresponding proximal searching region ||x -x τ || 2 2 to be arbitrarily large when minimizing the Equation. 13.Adam. Again, the parameters behavior in out of the control manner for example ||x -x τ || 2 2 → +∞. To this end, Reddi et al. (2019) proposes a very intuitive modification on Adam where

Table content: <table/>

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 to that fact that we observe there is no further accuracy improvement without performing any hyperparameter tuning. If we perform hyperparameter tuning, the results show in Table.1. AdamAL can finally reach to 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 to non-alignment. We also compare the result of AdamAL using different mini-batch settings, the result shows that AdamAL is also not sensitive to min-batch size.

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="3">on ResNet18 and VGG16; Cifar100 on ResNet50 and VGG16;</td></tr><tr><td colspan="10">Top: Loss of Cifar10 on ResNet18 and VGG16; Cifar100 on ResNet50 and VGG16;(Best see in</td></tr><tr><td>color)</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>40 50 60 70 80 90 non-alignment 0 Acc</td><td>10</td><td>20</td><td>30</td><td>40 epoch</td><td>50</td><td>60</td><td>70</td><td>128 256 512 1024 80</td><td>Algorithm Adam AMSGrad 75, 125, 175 94.60 lr decay Acc. 75, 125, 175 94.98 AdamAL 75, 125, 175 95.13 VSGD 75, 125, 175 94.73 Table 3: hyperparameter tuning, learn-</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>ing rate halve at iteration 75, 125, 175.</td></tr><tr><td colspan="9">Figure 3: AdamAL in different min-batch</td><td/></tr></table>

Peer review (iclr2020):
Summary: This 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. Pros: The 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. Cons: - 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. - 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. - The authors should complete the proof of Theorem 3.1. - 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. Minor comments: - Below equation 8, detail -> details. - The authors should add the definition of 1:t in subscript for g_{1:t} or phi_{1:t}. - Page 6, the first paragraph, logt-> log t - This paper lacks some references in this area. J. Chen and Q. Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. arXiv preprint arXiv:1806.06763, 2018. Ward, R., Wu, X. and Bottou, L. (2018). Adagrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization. arXiv preprint arXiv:1806.01811 . Li, X. and Orabona, F. (2018). On the convergence of stochastic gradient descent with adaptive stepsizes. arXiv preprint arXiv:1805.08114 .