ADAPTIVE LEARNING RATE METHODS
Year: 2019

Abstract:
Adam is shown not being able to converge to the optimal solution in certain cases. Researchers recently propose several algorithms to avoid the issue of nonconvergence of Adam, but their efficiency turns out to be unsatisfactory in practice. In this paper, we provide a new insight into the non-convergence issue of Adam as well as other adaptive learning rate methods. We argue that there exists an inappropriate correlation between gradient gt and the second moment term vt in Adam (t is the timestep), which results in that a large gradient is likely to have small step size while a small gradient may have a large step size. We demonstrate that such unbalanced step sizes are the fundamental cause of non-convergence of Adam, and we further prove that decorrelating vt and gt will lead to unbiased step size for each gradient, thus solving the non-convergence problem of Adam. Finally, we propose AdaShift, a novel adaptive learning rate method that decorrelates vt and gt by temporal shifting, i.e., using temporally shifted gradient gt−n to calculate vt. The experiment results demonstrate that AdaShift is able to address the non-convergence issue of Adam, while still maintaining a competitive performance with Adam in terms of both training speed and generalization.

heading: 1 INTRODUCTION
text: First-order optimization algorithms with adaptive learning rate play an important role in deep learning due to their efficiency in solving large-scale optimization problems. Denote gt ∈ Rn as the gradient of loss function f with respect to its parameters θ ∈ Rn at timestep t, then the general updating rule of these algorithms can be written as follows (Reddi et al., 2018):
θt+1 = θt − αt√ vt mt. (1)
In the above equation, mt , φ(g1, . . . , gt) ∈ Rn is a function of the historical gradients; vt , ψ(g1, . . . , gt) ∈ Rn+ is an n-dimension vector with non-negative elements, which adapts the learning rate for the n elements in gt respectively; αt is the base learning rate; and αt√vt is the adaptive step size for mt.
One common choice of φ(g1, . . . , gt) is the exponential moving average of the gradients used in Momentum (Qian, 1999) and Adam (Kingma & Ba, 2014), which helps alleviate gradient oscillations. The commonly-used ψ(g1, . . . , gt) in deep learning community is the exponential moving average of squared gradients, such as Adadelta (Zeiler, 2012), RMSProp (Tieleman & Hinton, 2012), Adam (Kingma & Ba, 2014) and Nadam (Dozat, 2016).
Adam (Kingma & Ba, 2014) is a typical adaptive learning rate method, which assembles the idea of using exponential moving average of first and second moments and bias correction. In general, Adam is robust and efficient in both dense and sparse gradient cases, and is popular in deep learning research. However, Adam is shown not being able to converge to optimal solution in certain cases. Reddi et al. (2018) point out that the key issue in the convergence proof of Adam lies in the quantity
Γt , (√vt αt − √ vt−1 αt−1 ) , (2)
∗Equally contributed.
which is assumed to be positive, but unfortunately, such an assumption does not always hold in Adam. They provide a set of counterexamples and demonstrate that the violation of positiveness of Γt will lead to undesirable convergence behavior in Adam.
Reddi et al. (2018) then propose two variants, AMSGrad and AdamNC, to address the issue by keeping Γt positive. Specifically, AMSGrad defines v̂t as the historical maximum of vt, i.e., v̂t = max {vi}ti=1, and replaces vt with v̂t to keep vt non-decreasing and therefore forces Γt to be positive; while AdamNC forces vt to have “long-term memory” of past gradients and calculates vt as their average to make it stable. Though these two algorithms solve the non-convergence problem of Adam to a certain extent, they turn out to be inefficient in practice: they have to maintain a very large vt once a large gradient appears, and a large vt decreases the adaptive learning rate αt√vt and slows down the training process.
In this paper, we provide a new insight into adaptive learning rate methods, which brings a new perspective on solving the non-convergence issue of Adam. Specifically, in Section 3, we study the counterexamples provided by Reddi et al. (2018) via analyzing the accumulated step size of each gradient gt. We observe that in the common adaptive learning rate methods, a large gradient tends to have a relatively small step size, while a small gradient is likely to have a relatively large step size. We show that the unbalanced step sizes stem from the inappropriate positive correlation between vt and gt, and we argue that this is the fundamental cause of the non-convergence issue of Adam.
In Section 4, we further prove that decorrelating vt and gt leads to equal and unbiased expected step size for each gradient, thus solving the non-convergence issue of Adam. We subsequently propose AdaShift, a decorrelated variant of adaptive learning rate methods, which achieves decorrelation between vt and gt by calculating vt using temporally shifted gradients. Finally, in Section 5, we study the performance of our proposed AdaShift, and demonstrate that it solves the non-convergence issue of Adam, while still maintaining a decent performance compared with Adam in terms of both training speed and generalization.

heading: 2 PRELIMINARIES
text: Adam. In Adam, mt and vt are defined as the exponential moving average of gt and g2t :
mt = β1mt−1 + (1− β1)gt and vt = β2vt−1 + (1− β2)g2t , (3)
where β1 ∈ [0, 1) and β2 ∈ [0, 1) are the exponential decay rates for mt and vt, respectively, with m0 = 0 and v0 = 0. They can also be written as:
mt = (1− β1) t∑ i=1 βt−i1 gi and vt = (1− β2) t∑ i=1 βt−i2 g 2 i . (4)
To avoid the bias in the estimation of the expected value at the initial timesteps, Kingma & Ba (2014) propose to apply bias correction to mt and vt. Using mt as instance, it works as follows:
mt = (1− β1)
∑t i=1 β t−i 1 gi
(1− β1) ∑t i=1 β t−i 1 =
∑t i=1 β
t−i 1 gi∑t
i=1 β t−i 1
= (1− β1)
∑t i=1 β t−i 1 gi
1− βt1 . (5)
Online optimization problem. An online optimization problem consists of a sequence of cost functions f1(θ), . . . , ft(θ), . . . , fT (θ), where the optimizer predicts the parameter θt at each timestep t and evaluate it on an unknown cost function ft(θ). The performance of the optimizer is usually evaluated by regret R(T ) , ∑T t=1[ft(θt)− ft(θ∗)], which is the sum of the difference between the online prediction ft(θt) and the best fixed-point parameter prediction ft(θ∗) for all the previous steps, where θ∗ = arg minθ∈ϑ ∑T t=1 ft(θ) is the best fixed-point parameter from a feasible set ϑ.
Counterexamples. Reddi et al. (2018) highlight that for any fixed β1 and β2, there exists an online optimization problem where Adam has non-zero average regret, i.e., Adam does not converge to optimal solution . The counterexamples in the sequential version are given as follows:
ft(θ) = { Cθ, if t mod d = 1; −θ, otherwise, (6)
where C is a relatively large constant and d is the length of an epoch. In Equation 6, most gradients of ft(θ) with respect to θ are −1, but the large positive gradient C at the beginning of each epoch makes the overall gradient of each epoch positive, which means that one should decrease θt to minimize the loss. However, according to (Reddi et al., 2018), the accumulated update of θ in Adam under some circumstance is opposite (i.e., θt is increased), thus Adam cannot converge in such case. Reddi et al. (2018) argue that the reason of the non-convergence of Adam lies in that the positive assumption of Γt , ( √ vt/αt − √ vt−1/αt−1) does not always hold in Adam.
The counterexamples are also extended to stochastic cases in (Reddi et al., 2018), where a finite set of cost functions appear in a stochastic order. Compared with sequential online optimization counterexample, the stochastic version is more general and closer to the practical situation. For the simplest one dimensional case, at each timestep t, the function ft(θ) is chosen as i.i.d.:
ft(θ) =
{ Cθ, with probability p = 1+δC+1 ;
−θ, with probability 1− p = C−δC+1 , (7)
where δ is a small positive constant that is smaller than C. The expected cost function of the above problem is F (θ) = 1+δC+1Cθ − C−δ C+1θ = δθ, therefore, one should decrease θ to minimize the loss. Reddi et al. (2018) prove that when C is large enough, the expectation of accumulated parameter update in Adam is positive and results in increasing θ.
Basic Solutions Reddi et al. (2018) propose maintaining the strict positiveness of Γt as solution, for example, keeping vt non-decreasing or using increasing β2. In fact, keeping Γt positive is not the only way to guarantee the convergence of Adam. Another important observation is that for any fixed sequential online optimization problem with infinitely repeating epochs (e.g., Equation 6), Adam will converge as long as β1 is large enough. Formally, we have the following theorem:
Theorem 1 (The influence of β1). For any fixed sequential online convex optimization problem with infinitely repeating of finite length epochs (d is the length of an epoch), if ∃G ∈ R such that ‖∇ft(θ)‖∞ ≤ G and ∃T ∈ N,∃ 2 > 1 > 0 such that 1 < αt√vtG
2 < 2 holds for all t > T , then, for any fixed β2 ∈ [0, 1), there exists a β1 ∈ [0, 1) such that Adam has average regret ≤ 2;
The intuition behind Theorem 1 is that, if β1 → 1, then mt → ∑d i=1 gi/d, i.e., mt approaches the average gradient of an epoch, according to Equation 5. Therefore, no matter what the adaptive learning rate αt/ √ vt is, Adam will always converge along the correct direction.

heading: 3 THE CAUSE OF NON-CONVERGENCE: UNBALANCED STEP SIZE
text: In this section, we study the non-convergence issue by analyzing the counterexamples provided by Reddi et al. (2018). We show that the fundamental problem of common adaptive learning rate methods is that: vt is positively correlated to the scale of gradient gt, which results in a small step size αt/ √ vt for a large gradient, and a large step size for a small gradient. We argue that such an unbalanced step size is the cause of non-convergence.
We will first define net update factor for the analysis of the accumulated influence of each gradient gt, then apply the net update factor to study the behaviors of Adam using Equation 6 as an example. The argument will be extended to the stochastic online optimization problem and general cases.

heading: 3.1 NET UPDATE FACTOR
text: When β1 6= 0, due to the exponential moving effect of mt, the influence of gt exists in all of its following timesteps. For timestep i (i ≥ t), the weight of gt is (1− β1)βi−t1 . We accordingly define a new tool for our analysis: the net update net(gt) of each gradient gt, which is its accumulated influence on the entire optimization process:
net(gt) , ∞∑ i=t αi√ vi [(1− β1)βi−t1 gt] = k(gt) · gt, where k(gt) = ∞∑ i=t αi√ vi (1− β1)βi−t1 , (8)
and we call k(gt) the net update factor of gt, which is the equivalent accumulated step size for gradient gt. Note that k(gt) depends on {vi}∞i=t, and in Adam, if β1 6= 0, then all elements in {vi}∞i=t are related to gt. Therefore, k(gt) is a function of gt.
It is worth noticing that in Momentum method, vt is equivalently set as 1. Therefore, we have k(gt) = αt and net(gt) = αtgt, which means that the accumulated influence of each gradient gt in Momentum is the same as vanilla SGD (Stochastic Gradient Decent). Hence, the convergence of Momentum is similar to vanilla SGD. However, in adaptive learning rate methods, vt is function over the past gradients, which makes its convergence nontrivial.

heading: 3.2 ANALYSIS ON ONLINE OPTIMIZATION COUNTEREXAMPLES
text: Note that vt exists in the definition of net update factor (Equation 8). Before further analyzing the convergence of Adam using the net update factor, we first study the pattern of vt in the sequential online optimization problem in Equation 6. Since Equation 6 is deterministic, we can derive the formula of vt as follows:
Lemma 2. In the sequential online optimization problem in Equation 6, denote β1, β2 ∈ [0, 1) as the decay rates, d ∈ N as the length of an epoch, n ∈ N as the index of epoch, and i ∈ {1, 2, ..., d} as the index of timestep in one epoch. Then the limit of vnd+i when n→∞ is:
lim n→∞ vnd+i = 1− β2 1− βd2 (C2 − 1)βi−12 + 1 . (9)
Given the formula of vt in Equation 9, we now study the net update factor of each gradient. We start with a simple case where β1 = 0. In this case we have
lim n→∞ k(gnd+i) = lim n→∞ αt√ vnd+i . (10)
Since the limit of vnd+i in each epoch monotonically decreases with the increase of index i according to Equation 9, the limit of k(gnd+i) monotonically increases in each epoch. Specifically, the first gradient gnd+1 = C in epoch n represents the correct updating direction, but its influence is the smallest in this epoch. In contrast, the net update factor of the subsequent gradients−1 are relatively larger, though they indicate a wrong updating direction.
We further consider the general case where β1 6= 0. The result is presented in the following lemma: Lemma 3. In the sequential online optimization problem in Equation 6, when n→∞, the limit of net update factor k(gnd+i) of epoch n satisfies: ∃ 1 ≤ j ≤ d such that
lim n→∞ k(C) = lim n→∞ k(gnd+1) < lim n→∞ k(gnd+2) < · · · < lim n→∞ k(gnd+j), (11)
and lim n→∞ k(gnd+j) > lim n→∞ k(gnd+j+1) > · · · > lim n→∞ k(gnd+d+1) = lim n→∞ k(C), (12)
where k(C) denotes the net update factor for gradient gi = C.
Lemma 3 tells us that, in sequential online optimization problem in Equation 6, the net update factors are unbalanced. Specifically, the net update factor for the large gradient C is the smallest in the entire epoch, while all gradients −1 have larger net update factors. Such unbalanced net update factors will possibly lead Adam to a wrong accumulated update direction.
Similar conclusion also holds in the stochastic online optimization problem in Equation 7. We derive the expectation of the net update factor for each gradient in the following lemma:
Lemma 4. In the stochastic online optimization problem in Equation 7, assuming αt = 1, it holds that k(C) < k(−1), where k(C) denote the expectation net update factor for gi = C and k(−1) denote the expectation net update factor for gi = −1.
Though the formulas of net update factors in the stochastic case are more complicated than those in deterministic case, the analysis is actually more easier: the gradients with the same scale share the same expected net update factor, so we only need to analyze k(C) and k(−1). From Lemma 4, we can see that in terms of the expectation net update factor, k(C) is smaller than k(−1), which means the accumulated influence of gradient C is smaller than gradient −1.

heading: 3.3 ANALYSIS ON NON-CONVERGENCE OF ADAM
text: As we have observed in the previous section, a common characteristic of these counterexamples is that the net update factor for the gradient with large magnitude is smaller than these with small magnitude. The above observation can also be interpreted as a direct consequence of inappropriate correlation between vt and gt. Recall that vt = β2vt−1 +(1−β2)g2t . Assuming vt−1 is independent of gt, then: when a new gradient gt arrives, if gt is large, vt is likely to be larger; and if gt is small, vt is also likely to be smaller. If β1 = 0, then k(gt) = αt/ √ vt. As a result, a large gradient is likely to have a small net update factor, while a small gradient is likely to have a large net update factor in Adam.
When it comes to the scenario where β1 > 0, the arguments are actually quite similar. Given vt = β2vt−1 +(1−β2)g2t . Assuming vt−1 and {gt+i}∞i=1 are independent from gt, then: not only does vt positively correlate with the magnitude of gt, but also the entire infinite sequence {vi}∞i=t positively correlates with the magnitude of gt. Since the net update factor k(gt) = ∑∞ i=t αi/ √ vi(1−β1)βi−t1 negatively correlates with each vi in {vi}∞i=t, it is thus negatively correlated with the magnitude of gt. That is, k(gt) for a large gradient is likely to be smaller, while k(gt) for a small gradient is likely to be larger.
The unbalanced net update factors cause the non-convergence problem of Adam as well as all other adaptive learning rate methods where vt correlates with gt. To construct a counterexample, the same pattern is that: the large gradient is along the “correct” direction, while the small gradient is along the opposite direction. Due to the fact that the accumulated influence of a large gradient is small while the accumulated influence of a small gradient is large, Adam may update parameters along the wrong direction.
Finally, we would like to emphasize that even if Adam updates parameters along the right direction in general, the unbalanced net update factors are still unfavorable since they slow down the convergence.

heading: 4 THE PROPOSED METHOD: DECORRELATION VIA TEMPORAL SHIFTING
text: According to the previous discussion, we conclude that the main cause of the non-convergence of Adam is the inappropriate correlation between vt and gt. Currently we have two possible solutions: (1) making vt act like a constant, which declines the correlation, e.g., using a large β2 or keep vt nondecreasing (Reddi et al., 2018); (2) using a large β1 (Theorem 1), where the aggressive momentum term helps to mitigate the impact of unbalanced net update factors. However, neither of them solves the problem fundamentally.
The dilemma caused by vt enforces us to rethink its role. In adaptive learning rate methods, vt plays the role of estimating the second moments of gradients, which reflects the scale of gradient on average. With the adaptive learning rate αt/ √ vt, the update step of gt is scaled down by √ vt and achieves rescaling invariance with respect to the scale of gt, which is practically useful to make the training process easy to control and the training system robust. However, the current scheme of vt, i.e., vt = β2vt−1 + (1 − β2)g2t , brings a positive correlation between vt and gt, which results in reducing the effect of large gradients and increasing the effect of small gradients, and finally causes the non-convergence problem. Therefore, the key is to let vt be a quantity that reflects the scale of the gradients, while at the same time, be decorrelated with current gradient gt. Formally, we have the following theorem:
Theorem 5 (Decorrelation leads to convergence). For any fixed online optimization problem with infinitely repeating of a finite set of cost functions {f1(θ), . . . , ft(θ), . . . fn(θ)}, assuming β1 = 0 and αt is fixed, we have, if vt follows a fixed distribution and is independent of the current gradient gt, then the expected net update factor for each gradient is identical.
Let Pv denote the distribution of vt. In the infinitely repeating online optimization scheme, the expectation of net update factor for each gradient gt is
E[k(gt)] = ∞∑ i=t Evi∼Pv [ αi√ vi (1− β1)βi−t1 ]. (13)
Given Pv is independent of gt, the expectation of the net update factor E[k(gt)] is independent of gt and remains the same for different gradients. With the expected net update factor being a fixed constant, the convergence of the adaptive learning rate method reduces to vanilla SGD.
Momentum (Qian, 1999) can be viewed as setting vt as a constant, which makes vt and gt independent. Furthermore, in our view, using an increasing β2 (AdamNC) or keeping v̂t as the largest vt (AMSGrad) is also to make vt almost fixed. However, fixing vt is not a desirable solution, because it damages the adaptability of Adam with respect to the adapting of step size.
We next introduce the proposed solution to make vt independent of gt, which is based on temporal independent assumption among gradients. We first introduce the idea of temporal decorrelation, then extend our solution to make use of the spatial information of gradients. Finally, we incorporate first moment estimation. The pseudo code of the proposed algorithm is presented as follows.
Algorithm 1 AdaShift: Temporal Shifting with Block-wise Spatial Operation
Input: n, β1, β2, φ, θ0, {ft(θ)}Tt=1, {αt}Tt=1, {g−t}n−1t=0 , 1: set v0 = 0 2: for t = 1 to T do 3: gt = ∇ft(θt) 4: mt = ∑n−1 i=0 β i 1gt−i/ ∑n−1 i=0 β i 1
5: for i = 1 to M do 6: vt[i] = β2vt−1[i] + (1− β2)φ(g2t−n[i]) 7: θt[i] = θt−1[i]− αt/ √ vt[i] ·mt[i] 8: end for 9: end for
10: // We ignore the bias-correction, epsilon and other misc for the sake of clarity

heading: 4.1 TEMPORAL DECORRELATION
text: In practical setting, ft(θ) usually involves different mini-batches xt, i.e., ft(θ) = f(θ;xt). Given the randomness of mini-batch, we assume that the mini-batch xt is independent of each other and further assume that f(θ;x) keeps unchanged over time, then the gradient gt = ∇f(θ;xt) of each mini-batch is independent of each other.
Therefore, we could change the update rule for vt to involve gt−n instead of gt, which makes vt and gt temporally shifted and hence decorrelated:
vt = β2vt−1 + (1− β2)g2t−n. (14) Note that in the sequential online optimization problem, the assumption “gt is independent of each other” does not hold. However, in the stochastic online optimization problem and practical neural network settings, our assumption generally holds.

heading: 4.2 MAKING USE OF THE SPATIAL ELEMENTS OF PREVIOUS TIMESTEPS
text: Most optimization schemes involve a great many parameters. The dimension of θ is high, thus gt and vt are also of high dimension. However, vt is element-wisely computed in Equation 14. Specifically, we only use the i-th dimension of gt−n to calculate the i-th dimension of vt. In other words, it only makes use of the independence between gt−n[i] and gt[i], where gt[i] denotes the i-th element of gt. Actually, in the case of high-dimensional gt and vt, we can further assume that all elements of gradient gt−n at previous timesteps are independent with the i-th dimension of gt. Therefore, all elements in gt−n can be used to compute vt without introducing correlation. To this end, we propose introducing a function φ over all elements of g2t−n, i.e.,
vt = β2vt−1 + (1− β2)φ(g2t−n). (15) For easy reference, we name the elements of gt−n other than gt−n[i] as the spatial elements of gt−n and name φ the spatial function or spatial operation. There is no restriction on the choice of φ, and we use φ(x) = maxi x[i] for most of our experiments, which is shown to be a good choice. The maxi x[i] operation has a side effect that turns the adaptive learning rate vt into a shared scalar.
An important thing here is that, we no longer interpret vt as the second moment of gt. It is merely a random variable that is independent of gt, while at the same time, reflects the overall gradient scale. We leave further investigations on φ as future work.

heading: 4.3 BLOCK-WISE ADAPTIVE LEARNING RATE SGD
text: In practical setting, e.g., deep neural network, θ usually consists of many parameter blocks, e.g., the weight and bias for each layer. In deep neural network, the gradient scales (i.e., the variance) for different layers tend to be different (Glorot & Bengio, 2010; He et al., 2015). Different gradient scales make it hard to find a learning rate that is suitable for all layers, when using SGD and Momentum methods. In traditional adaptive learning rate methods, they apply element-wise rescaling for each gradient dimension, which achieves rescaling-invariance and somehow solves the above problem. However, Adam sometimes does not generalize better than SGD (Wilson et al., 2017; Keskar & Socher, 2017), which might relate to the excessive learning rate adaptation in Adam.
In our temporal decorrelation with spatial operation scheme, we can solve the “different gradient scales” issue more naturally, by applying φ block-wisely and outputs a shared adaptive learning rate scalar vt[i] for each block:
vt[i] = β2vt−1[i] + (1− β2)φ(g2t−n[i]). (16)
It makes the algorithm work like an adaptive learning rate SGD, where each block has an adaptive learning rate αt/ √ vt[i] while the relative gradient scale among in-block elements keep unchanged. As illustrated in Algorithm 1, the parameters θt including the related gt and vt are divided into M blocks. Every block contains the parameters of the same type or same layer in neural network.

heading: 4.4 INCORPORATING FIRST MOMENT ESTIMATION: MOVING AVERAGING WINDOWS
text: First moment estimation, i.e., defining mt as a moving average of gt, is an important technique of modern first order optimization algorithms, which alleviates mini-batch oscillations. In this section, we extend our algorithm to incorporate first moment estimation.
We have argued that vt needs to be decorrelated with gt. Analogously, when introducing the first moment estimation, we need to make vt and mt independent to make the expected net update factor unbiased. Based on our assumption of temporal independence, we further keep out the latest n gradients {gt−i}n−1i=0 , and update vt and mt via
vt = β2vt−1 + (1− β2)φ(g2t−n) and mt = ∑n−1 i=0 β i 1gt−i∑n−1
i=0 β i 1
. (17)
In Equation 17, β1 ∈ [0, 1] plays the role of decay rate for temporal elements. It can be viewed as a truncated version of exponential moving average that only applied to the latest few elements. Since we use truncating, it is feasible to use large β1 without taking the risk of using too old gradients. In the extreme case where β1 = 1, it becomes vanilla averaging.
The pseudo code of the algorithm that unifies all proposed techniques is presented in Algorithm 1 and a more detailed version can be found in the Appendix. It has the following parameters: spatial operation φ, n ∈ N+, β1 ∈ [0, 1], β2 ∈ [0, 1) and αt.
Summary The key difference between Adam and the proposed method is that the latter temporally shifts the gradient gt for n-step, i.e., using gt−n for calculating vt and using the kept-out n gradients to evaluatemt (Equation 17), which makes vt andmt decorrelated and consequently solves the nonconvergence issue. In addition, based on our new perspective on adaptive learning rate methods, vt is not necessarily the second moment and it is valid to further involve the calculation of vt with the spatial elements of previous gradients. We thus proposed to introduce the spatial operation φ that outputs a shared scalar for each block. The resulting algorithm turns out to be closely related to SGD, where each block has an overall adaptive learning rate and the relative gradient scale in each block is maintained. We name the proposed method that makes use of temporal-shifting to decorrelated vt and mt AdaShift, which means “ADAptive learning rate method with temporal SHIFTing”.

heading: 5 EXPERIMENTS
text: In this section, we empirically study the proposed method and compare them with Adam, AMSGrad and SGD, on various tasks in terms of training performance and generalization. Without additional declaration, the reported result for each algorithm is the best we have found via parameter grid search. The anonymous code is provided at http://bit.ly/2NDXX6x.

heading: 5.1 ONLINE OPTIMIZATION COUNTEREXAMPLES
text: Firstly, we verify our analysis on the stochastic online optimization problem in Equation 7, where we set C = 101 and δ = 0.02. We compare Adam, AMSGrad and AdaShift in this experiment. For fair comparison, we set α = 0.001, β1 = 0 and β2 = 0.999 for all these methods. The results are shown in Figure 1a. We can see that Adam tends to increase θ, that is, the accumulate update of θ in Adam is along the wrong direction, while AMSGrad and AdaShift update θ in the correct direction. Furthermore, given the same learning rate, AdaShift decreases θ faster than AMSGrad, which validates our argument that AMSGrad has a relatively higher vt that slows down the training.
In this experiment, we also verify Theorem 1. As shown in Figure 1b, Adam is also able to converge to the correct direction with a sufficiently large β1 and β2. Note that (1) AdaShift still converges with the fastest speed; (2) a small β1 (e.g., β1 = 0.9, the light-blue line in Figure 1b) does not make Adam converge to the correct direction. We do not conduct the experiments on the sequential online optimization problem in Equation 6, because it does not fit our temporal independence assumption. To make it converge, one can use a large β1 or β2, or set vt as a constant.

heading: 5.2 LOGISTIC REGRESSION AND MULTILAYER PERCEPTRON ON MNIST
text: We further compare the proposed method with Adam, AMSGrad and SGD by using Logistic Regression and Multilayer Perceptron on MNIST, where the Multilayer Perceptron has two hidden layers and each has 256 hidden units with no internal activation. The results are shown in Figure 2 and Figure 3, respectively. We find that in Logistic Regression, these learning algorithms achieve very similar final results in terms of both training speed and generalization. In Multilayer Perceptron, we compare Adam, AMSGrad and AdaShift with reduce-max spatial operation (max-AdaShift) and without spatial operation (non-AdaShift). We observe that max-AdaShift achieves the lowest training loss, while non-AdaShift has mild training loss oscillation and at the same time achieves better generalization. The worse generalization of max-AdaShift may be due to overfitting in this task, and the better generalization of non-AdaShift may stem from the regularization effect of its relatively unstable step size.

heading: 5.3 DENSENET AND RESNET ON CIFAR-10
text: ResNet (He et al., 2016) and DenseNet (Huang et al., 2017) are two typical modern neural networks, which are efficient and widely-used. We test our algorithm with ResNet and DenseNet on CIFAR10 datasets. We use a 18-layer ResNet and 100-layer DenseNet in our experiments. We plot the best results of Adam, AMSGrad and AdaShift in Figure 4 and Figure 5 for ResNet and DenseNet, respectively. We can see that AMSGrad is relatively worse in terms of both training speed and generalization. Adam and AdaShift share competitive results, while AdaShift is generally slightly better, especially the test accuracy of ResNet and the training loss of DenseNet.

heading: 5.4 DENSENET WITH TINY-IMAGENET
text: We further increase the complexity of dataset, switching from CIFAR-10 to Tiny-ImageNet, and compare the performance of Adam, AMSGrad and AdaShift with DenseNet. The results are shown in Figure 6, from which we can see that the training curves of Adam and AdaShift are basically overlapped, but AdaShift achieves higher test accuracy than Adam. AMSGrad has relatively higher training loss, and its test accuracy is relatively lower at the initial stage.

heading: 5.5 GENERATIVE MODEL AND RECURRENT MODEL
text: We also test our algorithm on the training of generative model and recurrent model. We choose WGAN-GP (Gulrajani et al., 2017) that involves Lipschitz continuity condition (which is hard to optimize), and Neural Machine Translation (NMT) (Luong et al., 2017) that involves typical recurrent unit LSTM, respectively. In Figure 7a, we compare the performance of Adam, AMSGrad
and AdaShift in the training of WGAN-GP discriminator, given a fixed generator. We notice that AdaShift is significantly better than Adam, while the performance of AMSGrad is relatively unsatisfactory. The test performance in terms of BLEU of NMT is shown in Figure 7b, where AdaShift achieves a higher BLEU than Adam and AMSGrad.

heading: 6 CONCLUSION
text: In this paper, we study the non-convergence issue of adaptive learning rate methods from the perspective of the equivalent accumulated step size of each gradient, i.e., the net update factor defined in this paper. We show that there exists an inappropriate correlation between vt and gt, which leads to unbalanced net update factor for each gradient. We demonstrate that such unbalanced step sizes are the fundamental cause of non-convergence of Adam, and we further prove that decorrelating vt and gt will lead to unbiased expected step size for each gradient, thus solving the non-convergence problem of Adam. Finally, we propose AdaShift, a novel adaptive learning rate method that decorrelates vt and gt via calculating vt using temporally shifted gradient gt−n.
In addition, based on our new perspective on adaptive learning rate methods, vt is no longer necessarily the second moment of gt, but a random variable that is independent of gt and reflects the overall gradient scale. Thus, it is valid to calculate vt with the spatial elements of previous gradients. We further found that when the spatial operation φ outputs a shared scalar for each block, the resulting algorithm turns out to be closely related to SGD, where each block has an overall adaptive learning rate and the relative gradient scale in each block is maintained. The experiment results demonstrate that AdaShift is able to solve the non-convergence issue of Adam. In the meantime, AdaShift achieves competitive and even better training and testing performance when compared with Adam.

heading: B THE ADASHIFT PSEUDO CODE
text: Algorithm 2 AdaShift: We use a first-in-first-out queue Q to denote the averaging window with the length of n. Push(Q, gt) denotes pushing vector gt to the tail of Q, while Pop(Q) pops and returns the head vector of Q. And W is the weight vector calculated via β1.
Input: n, β1, β2, φ, , θ0, {ft(θ)}Tt=1, {αt}Tt=1 1: set v0 = 0, p0 = 1 2: W = [βn−11 , β n−2 1 , . . . , β1, 1]/ ∑n−1 i=0 β n 1
3: for t = 1 to T do 4: gt = ∇ft(θt) 5: if t ≤ n then 6: Push(Q, gt) 7: else 8: gt−n = Pop(Q) 9: Push(Q, gt)
10: mt = W ·Q 11: pt = pt−1β2 12: for i = 1 to M do 13: vt[i] = β2vt−1[i] + (1− β2)φ(g2t−n[i]) 14: θt[i] = θt−1[i]− αt/( √ vt[i]/(1− pt) + ) ·mt[i] 15: end for 16: end if 17: end for
We provided the anonymous code where a Tensorflow implementation of this algorithm is available.
C CORRELATION BETWEEN gt AND vt
In order to verify the correlation between gt and vt in Adam and AdaShift, we conduct experiments to calculate the correlation coefficient between gt and vt. We train the Multilayer Perceptron on MNIST until converge and gather the gradient of the second hidden layer of each step. Based on these data, we calculate vt and the correlation coefficient between gt[i] and gt−n[i], between gt[i] and gt−n[j] and between gt[i] and vt[i] of the last 10 epochs using the Pearson correlation coefficient, which is formulated as follows:
ρ = ∑n i=1(Xi − X̄)(Yi − Ȳ )√∑n
i=1(Xi − X̄)2 √∑n i=1(Yi − Ȳ )2 .
To verify the temporal correlation between gt[i] and gt−n[i], we range n from 1 to 10 and calculate the average temporal correlation coefficient of all variables i. Results are shown in Table 1.
To verify the spatial correlation between gt[i] and gt−n[j], we again range n from 1 to 10 and randomly sample some pairs of i and j and calculate the average spatial correlation coefficient of all the selected pairs. Results are shown in Table 2.
To verify the correlation between gt[i] and vt[i] within Adam, we calculate vt and the average correlation coefficient between g2t and vt of all variables i. The result is 0.435885276.
To verify the correlation between gt−n[i] and vt[i] within non-AdaShift and between gt−n[i] and vt within max-AdaShift, we range the keep number n from 1 to 10 to calculate vt and the average correlation coefficient of all variables i. The result is shown in Table 3 and Table 4.
Table 2: Spatial correlation coefficient between gt[i] and gt−n[j].
n 1 2 3 4 5 ρ -0.000609471 -0.001948853 -0.001426661 0.000904615 0.000329359 n 6 7 8 9 10 ρ 0.000971337 -0.000644563 -0.00137805 -0.001147973 -0.000592037
Table 3: Correlation coefficient between g2t−n[i] and vt[i] in non-AdaShift.
n 1 2 3 4 5 ρ -0.000706289 -0.000794959 -0.00076306 -0.000712474 -0.000668459 n 6 7 8 9 10 ρ -0.000623162 -0.000566573 -0.000542046 -0.000598015 -0.000592707

heading: D PROOF OF THEOREM 1
text: Proof.
With bias correction, the formulation of mt is written as follows
mt = (1− β1)
∑t i=1 β t−i 1 gi
(1− β1) ∑t i=1 β t−i 1 =
∑t i=1 β
t−i 1 gi∑t
i=1 β t−i 1
. (20)
According to L’Hospitals rule, we can draw the following:
lim β1→1 t∑ i=1 βt−i1 = lim β1→1 1− βt1 1− β1 = t.
Thus,
lim β1→1 mt = ∑t i=1 gi t .
According to the definition of limitation, let g∗ = ∑t
i=1 gi t , we have, ∀ > 0, ∃β1 ∈ (0, 1), such that
‖mt − g∗‖∞ < .
We set to be | g ∗
2 |, then for each dimension of mt, i.e. mt[i], g∗[i]
2 ≤ mt[i] ≤
3g∗[i]
2 So, mt shares the same sign with g∗ in every dimension.
Given it is a convex optimization problem, let the optimal parameter be θ∗, and the maximum step size is αt√vtG that holds 1/G < αt√ vt G < 2/G, we have,
lim t→∞ ‖θt − θ∗‖∞ < 2/G. (21)
Given ‖∇ft(θ)‖∞ ≤ G, we have ft(θ)− ft(θ∗) < 2, which implies the average regret
R(T )/T = T∑ t=1 [ft(θt)− ft(θ∗)]/T < 2. (22)

heading: E PROOF OF LEMMA 2
text: Proof. Let β1, β2 ∈ [0, 1) , d ∈ N , 1 ≤ i ≤ d and i ∈ N.
mnd+i =(1− β1) nd+i∑ j=1 βnd+i−j1 gj
=(1− β1) (C + 1) n∑ j=0 βjd+i−11 − nd+i−1∑ j=0 βj1  =(1− β1) [ 1− β(n+1)d1
1− βd1 βi−11 (C + 1)− 1− βnd+i1 1− β1
]
= 1− β(n+1)d1
1− βd1 (1− β1)βi−11 (C + 1)− (1− β nd+i 1 )
For a fixed d, as n approach infinity, we get the limit of mnd+i as:
lim nd→∞ mnd+i = 1− β1 1− βd1 (C + 1)βi−11 − 1
Similarly, for vnd+i:
vnd+i =(1− β2) nd+i∑ j=1 βnd+i−j2 g 2 j
=(1− β2) (C2 − 1) n∑ j=0 βjd+i−12 + nd+i−1∑ j=0 βj2  =(1− β2) [ 1− β(n+1)d2
1− βd2 βi−12 (C
2 − 1) + 1− β nd+i 2
1− β2
]
= 1− β(n+1)d2
1− βd2 (1− β2)βi−12 (C + 1)− (1− β nd+i 2 )
For a fixed d, as n approach infinity, we get the limit of vnd+i as:
lim nd→∞ vnd+i = 1− β2 1− βd2 (C2 − 1)βi−12 + 1 .

heading: F PROOF OF LEMMA 3
text: Proof. First, we define Ṽi as:
Ṽi = lim nd→∞ 1 √ vnd+i
= 1√
1−β2 1−βd2 (C2 − 1)β(i−1)2 + 1
where 1 ≤ i ≤ d and i ∈ N. And Ṽi has a period of d. Let t ′ = t− nd, then we can draw:
lim nd→∞ k(gnd+i) = ∞∑ t=nd+i (1− β1)βt−nd−i1√ 1−β2 1−βd2 (C2 − 1)β(t−1)% d2 + 1
= ∞∑ t′=i
(1− β1)βt ′ −i 1√ 1−β2 1−βd2 (C2 − 1)β(t ′−1)% d 2 + 1
= ∞∑ l=1 ld+i−1∑ j′′=(l−1)d+i (1− β1)βj ′′ −i 1 · Ṽj′′
= ∞∑ l=1 β (l−1)d 1 i+d−1∑ j′=i (1− β1)βj ′ −i 1 · Ṽj′
= ∞∑ l=1 β (l−1)d 1 d−1∑ j=0 (1− β1)βj1 · Ṽj+i
= ∞∑ l=1 β (l−1)d 1 β1 d−1∑ j=0 (1− β1)βj1 · Ṽj+i+1 + (1− β1)(1− βd1 ) · Ṽi  =β1 · lim
nd→∞ k(gnd+i+1) + ∞∑ l=1 β (l−1)d 1 (1− β1)(1− βd1 ) · Ṽi
Thus, we can get the forward difference of k(gnd+i) as:
lim nd→∞ k(gnd+i+1)− lim nd→∞ k(gnd+i) = ∞∑ l=1 β (l−1)d 1 (1− β1)2 ∞∑ j=0 βj1 · Ṽj+i+1 + (1− β1)2 ∞∑ j=0 βj1 · Ṽi  =(1− β1)2
∞∑ l=1 β (l−1)d 1 d−1∑ j=0 βj1 · [ Ṽj+i+1 − Ṽi ] Ṽnd+1i monotonically increases within one period, when 1 ≤ i ≤ d and i ∈ N. And the weigh βj1 for every difference term [ Ṽj+i+1 − Ṽi ] is fixed when i varies. Thus, the weighted summa-
tion ∑d−1 j=0 β j 1 · [ Ṽj+i+1 − Ṽi ] is monotonically decreasing from positive to negative. In other words, the forward difference is monotonically decreasing, such that there exists j, 1 ≤ j ≤ d and lim
nd→∞ k(gnd+1) is the maximum among all net updates. Moreover, it is obvious that lim nd→∞ k(gnd+1) is the minimum.
Hence, we can draw the conclusion: ∃1 ≤ j ≤ d, such that lim
nd→∞ k(C) = lim nd→∞ k(gnd+1) < lim nd→∞ k(gnd+2) < · · · < lim nd→∞ k(gnd+j)
and lim
nd→∞ k(gnd+j) > lim nd→∞ k(gnd+j+1) > · · · > lim nd→∞ k(gnd+d+1) = lim nd→∞ k(C),
where K(C) is the net update factor for gradient gi = C.

heading: G PROOF OF LEMMA 4
text: Lemma 7. 1 For a bounded random variable X and a differentiable function f(x), the expectation of f(X) is as follows:
E[f(X)] = f(E[X]) + f ′′ (E[X])
2 D(X) +R3 (23)
1See detial in: https://stats.stackexchange.com/questions/5782/variance-of-a-function-of-one-randomvariable
where D(X) is variance of X , and R3 is as follows:
R3 = f [3](α)
3 E(X − E[X])3+ (24)
+ ∫ |x−E[X]|>c ( f(E[X]) + f ′ (E[X])(x− E[X])2 + f(X) ) dF (x) (25)
F (x) is the distribution function of X . R3 is a small quantity under some condition. And c is large enough, such that: for any > 0,
P (X ∈ [E[X]− c,E[X] + c]) = P (|X − E[X]| ≤ c) ≤ 1− (26)
Proof. (Proof of Lemma 4 ) In the stochastic online optimization problem equation 7, the gradient subjects the distribution as:
gi =
{ C, with probability p := 1+δC+1 ;
−1, with probability 1− p := C−δC+1 . , (27)
Then we can get the expectation of gi : E[gi] = δ (28)
E[g2i ] = C2 · 1 + δ C + 1 + C − δ C + 1 = C + δ(C + 1) (29)
D[gi] = C + δ(C + 1)− δ2 (30) E[g4i ] = C(C2 − C + 1) + δ(C − 1)(C2 + 1) (31)
D[g2i ] = C 3 − 2C2 + C + δ(C3 − 3C2 − C − 1)− δ2(C + 1)2 (32)
Meanwhile, under the assumption that gradients are i.i.d., the expectation and variance of vi are as following when nd→∞:
E[vi] = lim i→∞
(1− β2) i∑
j=1
βi−j2 E[g 2 j ] = lim i→∞ (1− βi2)E[g2j ] = C + δ(C + 1) (33)
D[vi] = lim i→∞
(1− β2) i∑
j=1
βi−j2 D[g 2 j ] = lim i→∞ (1− βi2)D[g2j ] = D[g2j ] (34)
Then, for the gradient gi, the net update factor is as follows:
k(gi) = ∞∑ t=0 (1− β1)βt1√ βt+12 vi−1 + (1− β2)βt2 · g2i + (1− β2) ∑t j=1 β t−j 2 g 2 i+j
It should to be clarified that we define ∑t j=1 β t−j 2 g 2 i+j equal to zero when t = 0. Then we define Xt as:
Xt = β t+1 2 vi−1 + (1− β2)βt2 · g2i + (1− β2) t∑ j=1 βt−j2 g 2 i+j
E[Xt] =βt+12 E[vi−1] + (1− β2)βt2 · g2i + (1− β2) t∑
j=1
βt−j2 E[g 2 i+j ] (35)
=βt+12 E[g 2] + (1− β2)βt2 · g2i + (1− βt2)E[g2] (36)
=(1 + βt+12 − βt2)E[g2] + (1− β2)βt2 · g2i (37)
D[Xt] =β 2(t+1) 2 D[vi−1] + (1− β2)2(1− β2t2 ) 1− β22 D[g2i+j ] (38)
= [ β 2(t+1) 2 +
(1− β2)2(1− β2t2 ) 1− β22
] D[g2] (39)
For the function f(x) = 1√ x :
f ′′ (x) =
3 · x−5/2
8 According to lemma 7, we can the expectation of f(Xt) as follows:
E[f(Xt)] = (E[Xt])−1/2 + 3
8 (E[Xt])−5/2 ·D[Xt] (40)
E[Xt] andD[Xt] are expressed by equation 35 and equation 38. Then we can obtain the expectation expression of net update factor as follows:
k(gi) = ∑∞ t=0(1− β1)βt1 [ 1√
(1−β2)βt2g2i+(1+β t+1 2 −βk2 )E[g2i ] + 3Dt 8[(1−β2)βt2g2i+(1+β t+1 2 −βt2)E[g2i ]] 5 2
] (41)
where Dt = D[Xk]. Then for gradient C and −1, the net update factor is as follows:
k(C) = ∑∞ t=0(1− β1)βt1 [ 1√
(1−β2)βt2C2+(1+β t+1 2 −βk2 )E[g2i ] + 3Dt 8[(1−β2)βt2C2+(1+β t+1 2 −βt2)E[g2i ]] 5 2
] (42)
and
k(−1) = ∑∞ t=0(1− β1)βt1 [ 1√
(1−β2)βt2+(1+β t+1 2 −βk2 )E[g2i ] + 3Dt 8[(1−β2)βt2+(1+β t+1 2 −βt2)E[g2i ]] 5 2
] (43)
We can see that each term in the infinite series of k(C) is smaller than the corresponding one in k(−1). Thus, k(C) < k(−1).

heading: H PROOF OF LEMMA 6
text: Proof. From Lemma 2, we can get:
lim nd→∞ mnd+i√ vnd+i =
1−β1 1−βd1 (C + 1)βi−11 − 1√ 1−β2 1−βd2 (C2 − 1)βi−12 + 1
We sum up all updates in an epoch, and define the summation as S(β1, β2, C).
S(β1, β2, C) = d∑ i=1 lim nd→∞ mnd+i√ vnd+i
Assume β2 and C are large enough such that vt 1, we get the approximation of limit of vnd+i as:
lim nd→∞ vnd+i ≈ 1− β2 1− βd2 (C2 − 1)βi−12
Then we can draw the expression of S(β1, β2, C) as: S(β1, β2, C) = d∑ i=1 1−β1 1−βd2 (C + 1)βi−11 − 1√ 1−β2 1−βd2 (C2 − 1)βi−12
= d∑ i=1 1−β1 1−βd1 (C + 1)βi−11√ 1−β2 1−βd2 (C2 − 1)βi−12 − d∑ i=1 1√ 1−β2 1−βd2 (C2 − 1)βi−12
=
√ 1− βd2
(1− β2)βd−12
√ C + 1
C − 1 · 1− β1 1− βd1 · √ βd2 − βd1√ β2 − β1 − √ 1− βd2 (1− β2)βd−12 · 1√ C2 − 1 √ βd2 − 1√ β2 − 1
=
√ 1− βd2
(1− β2)βd−12 (C − 1)
[ (1− β1)(βd2 − βd1 ) √ C + 1
(1− βd1 )( √ β2 − β1)
− √ βd2 − 1√
C + 1( √ β2 − 1)
]
Let S(β1, β2, C) = 0, we get the equation about critical condition:
C + 1 = (1− βd1 )(
√ βd2 − βd1 )(1− √ β2)
(1− β1)( √ β2 − β1)(1− √ βd2 )

heading: I HYPER-PARAMETERS INVESTIGATION
text: I.1 HYPER-PARAMETERS SETTING
Here, we list all hyper-parameter setting of all above experiments.
I.2 LEARNING RATE αt SENSITIVITY
In this section, we discuss the learning rate αt sensitivity of AdaShift. We set αt ∈ {0.1, 0.01, 0.001} and let n = 10, β1 = 0.9 and β2 = 0.999. The results are shown in Figure 9 and Figure 10. Empirically, we found that when using the max spatial operation, the best learning rate for AdaShift is around ten times of Adam.
I.3 β1 AND β2 SENSITIVITY
In this section, we discuss the β1 and β2 sensitivity of AdaShift. We set α = 0.01, n = 10 and let β1 ∈ {0, 0.9} and β2 ∈ {0.9, 0.99, 0.999}. The results are shown in Figure 11 and Figure 12. According to the results, AdaShift holds a low sensitivity to β1 and β2. In some tasks, using the first moment estimation (with β1 = 0.9 and n = 10) or using a large β2, e.g., 0.999 can attain better performance. The suggested parameters setting is n = 10, β1 = 0.9, β2 = 0.999.
I.4 n AND m SENSITIVITY
In this section, we discuss the n sensitivity of AdaShift. Here we also test a extended version of first moment estimation where it only uses the latest m gradients (m ≤ n):
vt = β2vt−1 + (1− β2)φ(g2t−n) and mt = ∑m−1 i=0 β i 1gt−i∑m−1
i=0 β i 1
. (44)
We set β1 = 0.9, β2 = 0.999. The results are shown in Figure 13, Figure 14 and Figure 15. In these experiments, AdaShift is fairly stable when changing n and m. We have not find a clear pattern on the performance change with respect to n and m.

heading: J TEMPORAL-ONLY AND SPATIAL-ONLY
text: In our proposed algorithm, we apply a spatial operation on the temporally shifted gradient gt−n to update vt: vt[i] = β2vt−1[i] + (1 − β2)φ(g2t−n[i]). It is based on the temporal independent assumption, i.e., gt−n is independent of gt. And according to our argument in Section 4.2, one can further assume every element in gt−n is independent of the i-th dimension of gt.
We purposely avoid involving the spatial elements of the current gradient gt, where the independence might not holds: when a sample which is rare and has a large gradient appear in the mini-batch xt, the overall scale of gradient gt might increase. However, for the temporally already decorrelation gt−i, further taking the advantage of the spatial irrelevance will not suffer from this problem.
We here provide extended experiments on two variants of AdaShift: (i) AdaShift (temporal-only), which only uses the vanilla temporal independent assumption and evaluate vt with: vt = β2vt−1 + (1−β2)g2t−n; (ii) AdaShift (spatial-only), which directly uses the spatial elements without temporal shifting.
According to our experiments, AdaShift (temporal-only), i.e., without the spatial operation, is less stable than AdaShift. In some tasks, AdaShift (temporal-only) works just fine; while in some other cases, AdaShift (temporal-only) suffers from explosive gradient and requires a relatively small learning rate. The performance of AdaShift (spatial-only) is close to Adam. More experiments for AdaShift (spatial-only) are included in the next section.

heading: K EXTENDED EXPERIMENTS: NADAM AND ADASHIFT(SPACE ONLY)
text: In this section, we extend the experiments and add the comparisons with Nadam and AdaShift (spatial-only). The results are shown in Figure 18, Figure19 and Figure20. According to these experiments, Nadam and AdaShift (spatial-only) share similar performence as Adam.

heading: L EXTENSION EXPERIMENTS: ILL-CONDITIONED QUADRATIC PROBLEM
text: Rahimi & Recht raise the point, at test of time talk at NIPS 2017, that it is suspicious that gradient descent (aka back-propagation) is ultimate solution for optimization. A ill-conditioned quadratic problem with Two Layer Linear Net is showed to be challenging for gradient descent based methods, while alternative solutions, e.g., Levenberg-Marquardt, may converge faster and better. The problem is defined as follows: L(W1,W2;A) = Ex∈N(0,1)‖W1W2x−Ax‖2 (45) where A is some known badly conditioned matrix (k = 1020 or 105), and W1 and W2 are the trainable parameters.
We test SGD, Adam and AdaShift with this problem, the results are shown in Figure 21, Figure 24. It turns out as long as the training goes enough long, SGD, Adam, AdaShift all basically converge in this problem. Though SGD is significantly better than Adam and AdaShift.
We would tend to believe this is a general issue of adaptive learning rate method when comparing with vanilla SGD. Because these adaptive learning rate methods generally are scale-invariance, i.e., the step-size in terms of gt/sqrt(vt) is basically around one, which makes it hard to converge very well in such a ill-conditioning quadratic problem. SGD, in contrast, has a step-size gt; as the training converges SGD would have a decreasing step-size, makes it much easier to converge better. The above analysis is confirmed with Figure 22 and Figure 23, with a decreasing learning rate, Adam and AdaShfit both converge very good.

Review summaries:
Based on an extensive argument acoordig to which Adam potential failures are due to the positive correlation between gradient and moment estimation, the authors propose Adashift, a method in which temporal shift (and more surprisingly 'spatial' shift, ie mixing of parameters) is used to ensure that moment estimation is less correlated with gradient, ensuring convergence of Adashift in pathological cases, without the efficiency cost of simpler method such as AMSGrad. An extensive analysis of a pathological counter example, introduced in Reddi et al. 2018 is analysed, before the algorithm presentation and experimental validation. Experiments shows that the algorithm has equivalent speed as Adam and sometimes false local minima, resulting in better training error, and potentially better test error.