Nostalgic Adam: Weighting More of the Past Gradients When Designing the Adaptive Learning Rate

1 Introduction

Along with the rise of deep learning, various first-order stochastic optimization methods emerged. Among them, the most fundamental one is the stochastic gradient descent, and the Nesterov's Accelerated Gradient method [Nesterov, 1983] is also a well-known acceleration algorithm. Recently, many adaptive stochastic optimization methods have been proposed, such as AdaGrad [Duchi et al., 2010], RMSProp [Tieleman and Hinton, 2012], AdaDelta [Zeiler, 2012] and Adam [Kingma and Ba, 2014]. These algorithms can be written in the following general form:

where gi is the gradient obtained in the i-th time step, αt/ψ(g1, ..., gt) the adaptive learning rate, and ϕ(g1, ..., gt) the gradient estimation. There have been extensive studies on the design of gradient estimations which can be traced back to classical momentummethods [Polyak, 1964] andNAG [Nesterov, 1983]. In this paper, however, we focus more on how to understand and improve the adaptive learning rate.

1 https://github.com/andrehuang/NostalgicAdam-NosAdam

Adam [Kingma and Ba, 2014] is perhaps the most widely used adaptive stochastic optimization method which uses an exponential moving average (EMA) to estimate the square of the gradient scale, so that the learning rate can be adjusted adaptively. More specifically, Adam takes the form of (1) with

Here in g2 t , and other multiplication operations in this paper, coordinate-wise multiplication is performed. We shall call vt the re-scaling term of the Adam and its variants, since it serves as a coordinate-wise re-scaling of the gradients. Despite its fast convergence and easiness in implementation, Adam is also known for its non-convergence and poor generalization in some cases [Reddi et al., 2018][Wilson et al., 2017]. More recently, [Balles and Hennig, 2018] both theoretically and empirically pointed out that generalization is mainly determined by the sign effect rather than the adaptive learning rate, and the sign effect is problem-dependent. In this paper, we are mainly dealing with the non-convergence issue and will only empirically compare generalization ability among different Adam variants.

As for the non-convergence issue, [Reddi et al., 2018] suggested that the EMA of vt of Adam is the cause. The main problem lies in the following quantity:

which essentially measures the change in the inverse of learning rate with respect to time. Algorithms that use EMA to estimate the scale of the gradients cannot guarantee the positive semi-definiteness of Γt, and that causes the non-convergence of Adam. To fix this issue, [Reddi et al., 2018] proposed AMSGrad, which added one more step ̂ vt = max{̂ vt-1, vt} in (2). AMSGrad is claimed by its authors to have a "longterm memory" of past gradients.

Another explanation on the cause of non-convergence was recently proposed by [Zhou et al., 2018]. The authors observed that Adam may diverge because a small gradient may have a large step size which leads to a large update. Therefore, if the small gt with large step size is often in the wrong direction, it could lead to divergence. Thus, they proposed a modification to Adam called AdaShift by replacing g2 t with g2 t-n for some manually chosen n when calculating vt.

Both AdaShift and AMSGrad suggest that we should not fully trust the gradient information we acquire at current step, and the past gradients are useful when gt is not reliable. In this paper, we take this idea one step further by suggesting that we may weight more of the past gradients than the present ones. We call our algorithm Nostalgic Adam (NosAdam). We will show that the design of the algorithm is inspired by our mathematical analysis on the convergence, and NosAdam has the fastest known convergence rate. Furthermore, we will discuss why "nostalgia" is important, and empirically investigate how different designs of vt can lead to different performances from a loss landscape perspective. Finally, we examine the empirical performance of NosAdam on some common machine learning tasks. The experiments show us that NosAdam is a promising alternative to Adam and its variants.

2 RelatedWork

Adam is widely used in both academia and industry. However, it is also one of the least well-understood algorithms. In recent years, some remarkable works provided us with better understanding of the algorithm, and proposed different variants of it. Most of works focused on how to interpret or modify the re-scaling term vt of (2).

As mentioned above, [Reddi et al., 2018], [Zhou et al., 2018] focused on the non-convergence issue of Adam, and proposed their own modified algorithms. More recently, [Luo et al., 2019] proposed another modification. [Wilson et al., 2017] pointed out the generalization issue of adaptive optimization algorithms. Based on the assumption that vt is the estimate of the second moment estimate of gt, [Balles and Hennig, 2018] dissected Adam into sign-based direction and variance adaption magnitude. They also pointed out that the sign-based direction part is the decisive factor of generalization performance, and that is problem-dependent. This in a way addressed the generalization issue raised in [Wilson et al., 2017].

However, the interpretation of vt as an estimate of the second moment assumption may not be correct, since [Chen and Gu, 2019] showed that v1/2 t in the Adam update (2) can be replaced by vp t for any p ∈ (0, 1 2 ]. The modified algorithm is called Padam. In our supplementary material, we also proved that a convergence theorem of a "p-norm" form of NosAdam, where the re-scaling term vt can be essentially viewed as a "p-moment" of gt. These discoveries cast doubts on the second moment assumption, since both the convergence analysis and empirical performance seemed not so dependent on this assumption.

The true role of vt, however, remains a mystery. In AdaGrad [Duchi et al., 2010], which is a special case of NosAdam, the authors mentioned an metaphor that "the adaptation allows us to find needles in haystacks in the form of very predictive but rarely seen features." They were suggesting that vt is to some extent balancing the update speeds of different features according to their abundance in the data set. This understanding might be supported by a previous work called SWATS (Switching from Adam to SGD) [Keskar and Socher, 2017], which uses Adam for earlier epochs and then fix the re-scaling term vt for later epochs. This suggests that there may be some sort of optimal re-scaling term, and we can keep using it after we obtain a good enough estimate.

Despite all the previous efforts, our understanding of the re-scaling term vt is still very limited. In this paper, we investigate the issue from a loss landscape approach, and this provides us with some deeper understanding of when and how different Adam-like algorithms can perform well or poorly.

3 Nostalgic AdamAlgorithm

In this section, we introduce the Nostalgic Adam (NosAdam) algorithm, followed by a discussion on its convergence. Let us first consider a general situation where we allow the parameter β2 in Equation (2) change in time t. Without loss of generality, we may let β2,t = Bt-1 Bt and B0 = 0. Considering the constraint that 0 ≤ β2,t ≤ 1, {Bt} is assumed to be a non-decreasing positive sequence. We then define bt := Bt - Bt-1, then Bt = ∑tk=1 bk and {bk} is a nonnegative sequence.

Like Adam and its variants, the condition Γt ⪰ 0 is crucial in ensuring convergence. We will now see that to ensure positive semi-definiteness of Γt, the algorithm naturally requires to weight more of the past gradients than the more recent ones when calculating vt. To see this, we first present the following lemma.

Lemma 3.1. The positive semi-definiteness of Vt α2t - Vt-1 α2t-1 is satisfied if and only if Bt t is non-increasing.

Proof.

Here the "if and only if" in the lemma is due to that if Bt t is non-increasing, then because ∑tj=1 bjg2 j ≥ ∑t-1 j=1 bjg2 j , we can derive the positive semi-definiteness of Vt α2t - Vt-1 α2t-1 ; and if Vt α2t - Vt-1 α2t-1 ⪰ 0 for every {gj}, then for {gj} whose limit is 0, we can derive that Bt t is non-increasing from the above inequality.

Then, if we assume that {bk} is an monotonous sequence (note in Adam, {bk} is a decreasing sequence), it is not hard

Algorithm 1 Nostalgic Adam Algorithm

Input: x ∈ F , m0 = 0, V0 = 0

• 1: for t = 1 to T do
• 2: gt =∇ft(xt)
• 3: β2,t = Bt-1/Bt, where Bt = ∑tk=1 bk for t ≥ 1, bk ≥ 0 and B0 = 0
• 4: mt = β1mt-1 + (1 -β1)gt
• 5: Vt = β2,tVt-1 + (1 -β2,t)g2 t
• 6: ˆxt+1 = xt -αtmt/√Vt
• 7: xt+1 = PF,√Vt (ˆxt+1)
• 8: end for

to see that Bt t is non-increasing if and only if bj is nonincreasing. Noting that vt = ∑tk=1 g2 k bk Bt , we can see that the sufficient condition for positive semi-definiteness of Γt is that in the weighted average vt, the weights of gradients should be non-increasing w.r.t. t. In other words, we should weight more of the past gradients than the more recent ones.

The NosAdam algorithm reads as in Algorithm 1. We now introduce the necessary notations and definitions in our presentation of the algorithm and convergence theorem. We have adopted the notation of online optimization introduced in [Zinkevich, 2003]. At each time step t, the optimization algorithm picks a point xt in its feasible set F ∈ Rd . Let ft be the loss function corresponding to the underlying minibatch, and the algorithm incurs loss ft(xt). We evaluate our algorithm using the regret that is defined as the sum of all the previous differences between the online prediction ft(xt) and loss incurred by the fixed parameter point in F for all the previous steps, i.e.

Denote S + d the set of all positive definite d × d matrices. The projection operator PF,A(y) for A ∈ S + d is defined as argminx∈F ||A1/2 (x-y)|| for y ∈ Rd . Finally, we say F has bounded diameter D∞ if ||x - y||∞ ≤ D∞ for all x, y ∈ F.

From Algorithm 1, we can see that vt can either decrease or increase based on the relationship between vt-1 and g2 t , which is the reason why NosAdam circumvents the flaw of AMSGrad (Figure 4). Convergence of NosAdam is also guaranteed as stated by the following theorem.

Theorem 3.2 (Convergence of NosAdam). Let Bt and bk be the sequences defined in Algorithm 1, αt = α/√t, β1,1 = β1, β1,t ≤ β1 for all t. Assume that F has bounded diameter D∞ and ||∇ft(x)||∞ ≤ G∞ for all t and x ∈ F. Furthermore, let β2,t be such that the following conditions are satisfied:

Then for {xt} generated using NosAdam, we have the following bound on the regret

One notable characteristic of NosAdam, which makes it rather different from the analysis by [Reddi et al., 2018], is that the conditions on Bt and bt are data-independent and are very easy to check. In particular, if we choose Bt as a hyperharmonic series, i.e. Bt = ∑tk=1 k-γ , then the convergence criteria are automatically satisfied. We shall call this special case NosAdam-HH (HyperHarmonic), and its convergence result is summarized in the following corollary.

Corollary 3.2.1. Supposeβ1,t = β1λt-1 , bk = k-γ , γ ≥ 0 , thus Bt = ∑tk=1 k-γ , and β2,t = Bt-1/Bt < 1 in Algorithm 1. Then Bt and bt satisfy the constraints in Therorem 3.2, and we have

To see this, we simply need to see that Bt = O(t1-γ ). More detailed explanation is put in our supplement. Our theory shows that the proposed NosAdam achieves convergence rate of O(1/√T ), which is so far the best known convergence rate.

4 Why Nostalgic?

In this section, we investigate more about the mechanism behind Adam and AMSGrad, and analyze the pros and cons of being "nostalgic".

As mentioned in Section 1, [Reddi et al., 2018] proved that if Γt is positive semi-definite, Adam converges. Otherwise, it may diverge. An example of divergence made by [Reddi et al., 2018] is

where C is slightly larger than 2. The correct optimization direction should be -1, while Adam would go towards 1. To fix this, they proposed AMSGrad, which ensures Γt ⪰ 0 by updating vt as follows

where ˆ vt is used in the update step.

However, this example is not representative of real situations. Also, the explanation of "long-term memory" by [Reddi et al., 2018] is not very illustrative. In the remaining part of this section, we aim to discuss some more realistic senarios and try to understand the pros and cons of different algorithms.

We start from analyzing the different weighting strategies when calculating vt. For Adam,

and the weight (1 - β2)βt-k 2 increases exponentially. For NosAdam,

and for NosAdam-HH, bk = k-γ is the k-th term of a hyperharmonic series. For AMSGrad, v(AMSGrad) t is data-dependent and therefore cannot be explicitly expressed. However, v(AMSGrad) t is chosen to be the largest in {v(Adam) s : 0 ≤ s ≤ t}. Therefore, it can be seen as a shifted version of v(Adam) t , i.e. v(Adam) s = v(Adam) t-n , where n depends on the data. This is similar as AdaShift, where n is instead a hyperparameter. Figure 1 plots the first 100 weights of Adam, NosAdam and AMSGrad, where β2, γ, n, is chosen as 0.9, 0.1 and 20, respectively.

From the above analysis, we can see that vt of Adam is mainly determined by its most current gradients. Therefore, when gt keeps being small, the adaptive learning rate could be large, which may lead to oscillation of the sequence, and increasing chance of being trapped in local minimum. On the other hand, NosAdam adopts a more stable calculation of vt, since it relies on all the past gradients.

We support the above discussion with an example of an objective function with a bowl-shaped landscape where the global minima is at the bottom of the bowl with lots of local minimum surrounding it. The explicit formula of the objective function is

Figure 2: Example of an objective function with a bowl-shaped landscape. It has a wide global minima and some sharp local minimum surrounding it. In 2b, the red trajectory is the sequence generated by NosAdam and yellow trajectory by Adam. The trajectory of Adam ends up in valley A and NosAdam in valley B. This shows that Adam would easily diverge due to unstable calculations of vt.

Figure 2a shows one slice of the function for z = 2.34. In the function, a and b determine the depth and width of the global minima, and c, r, β determine depth, location and width of the local minimums. In this example, a, b, c, r, β are set to 30, 0.007, 0.25, 1, 20, respectively. Figure 2b shows different trajectories of Adam and NosAdam when they are initiated at the same point on the side of the bowl. As expected, the trajectory of Adam (yellow) passes the global minima and ends up trapped in valley A, while NosAdam (red) gradually converges to the global minima, i.e. valley B.

With the operation of taking max, AMSGrad does not have the same non-convergence issue as discussed above. However, taking max may be problematic as well since ˆ vt can never decrease. If a very large gradient appears at an iteration, then the adaptive learning rate for all later steps will keep being small. For example, if a large gradient (e.g. 100 times of the original gradient) appears at the 106 step in the example Equation (4), we can see that AMSGrad will converge very slowly. This, however, will not be a problem for NosAdam which has the ability of both increasing and decreasing its vt. See Figure 3 for a demonstration. Another example with sharper local minima by setting b = 2, c = 4, r = 1.3 is given in Figure 4; and the algorithms are initialized at location A. One can see that the sequence generated by AMSGrad is trapped in a sharp local minima, whereas NosAdam still converges to the global minimum. From these examples we can see that the operation of taking max of AMSGrad has some intrinsic flaws though it promises convergence. The way of computing vt in NosAdam seems superior.

There are also situations in which NosAdam can work poorly. Just because NosAdam is nostalgic, it requires a relatively good initial point to achieve good performances though this is commonly required by most optimization algorithms. However, Adam can be less affected by bad initializations sometime due to its specific way of calculating vt. This gives it a chance of jumping out of the local minimum (and a chance of jumping out of the global minima as well as shown in Figure 2). To demonstrate this, we let both Adam and NosAdma initialize in the valley A (see Figure 5). We can see that the trajectory of Adam manages to jump out of the valley, while it is more difficult for NosAdam to do so.

We note that although NosAdam requires good initialization, it does not necessarily mean initializing near the global minima. Since the algorithm is nostalgic, as long as the initial gradients are pointing towards the right direction, the algorithm may still converge to the global minima even though the initialization is far away from the global minima. As we can see from Figure 4 that NosAdam converges because all of the gradients are good ones at the beginning of the algorithm, which generates enough momentum to help the sequence dashes through the region with sharp local minimum.

Like any Adam-like algorithm, the convergence of NosAdam depends on the loss landscape and initialization. However, if the landscape is as shown in the above figures, then NosAdam has a better chance to converge than Adam and AMSGrad. In practice, it is therefore helpful to first ex-

• (b) Trajectories of AMSGrad (blue) and NosAdam (red)
• (b) Trajectories of Adam (blue) and NosAdam (red)

Figure 5: Figure 5a shows the landscape of the objective function. Figure 5b shows the different behaviours of Adam and NosAdam, with the sequence generated by Adam colored in blue and NosAdam in red, and they are initiated in the valley A.

amine the loss landscape before selecting an algorithm. However, it is time consuming to do in general. Nonetheless, earlier studies showed that neural networks with skip connections like ResNet and DenseNet lead to coercive loss functions similar to the one shown in the above figures [Li et al., 2018].

5 Experiments

In this section, we conduct some experiments to compare NosAdam with Adam and its variant AMSGrad. We consider the task of multi-class classification using logistic regression, multi-layer fully connected neural networks and deep convolutional neural networks on MNIST [Lecun, ] and CIFAR-10 [Krizhevsky et al., ]. The results generally indicate that NosAdam is a promising algorithm that works well in practice. Throughout our experiments, we fixed β1 to be 0.9, β2 to be 0.999 for Adam and AMSGrad, and search γ in {1e-1, 1e-2, 1e-3, 1e-4} for NosAdam. The initial learning rate is chosen from {1e-3, 2e-3, ..., 9e-3, 1e-2, 2e-2, ..., 9e-2, 1e-1, 2e-1, ..., 9e-1} and the results are reported using the best set of hyperparameters. All the experiments are done using Pytorch0.4.

Logistic Regression

To investigate the performance of the algorithms on convex problems, we evaluate Adam, AMSGrad and NosAdam on multi-class logistic regression problem using the MNIST dataset. To be consistent with the theory, we set the step size αt = α/√t. We set the minibatch size to be 128. According to Figure 6a, the three algorithms have very similar performance.

Multilayer Fully Connected Neural Networks

We first train a simple fully connected neural network with 1 hidden layer (with 100 neurons and ReLU as the activation function) for the multi-class classification problem on MNIST. We use constant step size αt = α and minibatch=128 throughout the experiments for this set of experiments. The results are shown in Figure 6b. We can see that NosAdam slightly outperforms AMSGrad, while Adam is much worse than both NosAdam and AMSGrad and oscillates a lot. This is due to the difference of the definition of vt for each algorithm: vt in AMSGrad and NosAdam gradually becomes stationary and stays at a good re-scaling value; while vt in Adam does not have such property.

Deep Convolutional Neural Networks

Finally, we train a deep convolutional neural network on CIFAR-10. Wide Residual Network [Zagoruyko and Komodakis, 2016] is known to be able to achieve high accuracy with much less layers than ResNet [He et al., 2015]. In our experiment, we choose Wide ResNet28. The model is trained on 4 GPUs with the minibatch size 100. The initial learning rate is decayed at epoch 50 and epoch 100 by multiplying 0.1. In our experiments, the optimal performances are usually achieved when the learning rate is around 0.02 for all the three algorithms. For reproducibility, an anonymous link of code will be provided in the supplementary material.

Our results are shown in Figure 7. We observe that NosAdam works slightly better than AMSGrad and Adam in terms of both convergence speed and generalization. This indicates that NosAdam is a promising alternative to Adam and its variants.

6 Conlusion

In this paper, we suggested that we should weight more of the past gradients when designing the adaptive learning rate. Our original intuition came from the convergence analysis of Adam-like algorithms. Based on such observation, we then proposed Nostalgic Adam (NosAdam), and provided convergence analysis. We also discussed the pros and cons of NosAdam comparing to Adam and AMSGrad, which gave us a better idea when NosAdam could be effective.

Acknowledgments

This work would not have existed without the support of BICMR and School of Mathematical Sciences, Peking University. Bin Dong is supported in part by Beijing Natural Science Foundation (Z180001).