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 non-convergence 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 $g_t$ and the second moment term $v_t$ 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 $v_t$ and $g_t$ 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 $v_t$ and $g_t$ by temporal shifting, i.e., using temporally shifted gradient $g_{t-n}$ to calculate $v_t$. 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. 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 g t ∈ R n as the gradient of loss function f with respect to its parameters θ ∈ R n at timestep t, then the general updating rule of these algorithms can be written as follows (Reddi et al., 2018) : DISPLAYFORM0 In the above equation, m t φ(g 1 , . . . , g t ) ∈ R n is a function of the historical gradients; v t ψ(g 1 , . . . , g t ) ∈ R n + is an n-dimension vector with non-negative elements, which adapts the learning rate for the n elements in g t respectively; α t is the base learning rate; and αt √ vt is the adaptive step size for m t .One common choice of φ(g 1 , . . . , g t ) 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 ψ(g 1 , . . . , g t ) 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 DISPLAYFORM1 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 definesv t as the historical maximum of v t , i.e.,v t = max {v i } t i=1 , and replaces v t withv t to keep v t non-decreasing and therefore forces Γ t to be positive; while AdamNC forces v t to have "long-term memory" of past gradients and calculates v t 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 v t once a large gradient appears, and a large v t 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 g t . 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 v t and g t , and we argue that this is the fundamental cause of the non-convergence issue of Adam.In Section 4, we further prove that decorrelating v t and g t 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 v t and g t by calculating v t 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. 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 v t and g t , 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 v t and g t 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 v t and g t via calculating v t using temporally shifted gradient g t−n .In addition, based on our new perspective on adaptive learning rate methods, v t is no longer necessarily the second moment of g t , but a random variable that is independent of g t and reflects the overall gradient scale. Thus , it is valid to calculate v t 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. FIG7 . It suggests that for a fixed sequential online optimization problem, both of β 1 and β 2 determine the direction and speed of Adam optimization process. Furthermore , we also study the threshold point of C and d, under which Adam will change to the incorrect direction, for each fixed β 1 and β 2 that vary among [0, 1). To simplify the experiments, we keep d = C such that the overall gradient of each epoch being +1. The result is shown in FIG7 , which suggests, at the condition of larger β 1 or larger β 2 , it needs a larger C to make Adam stride on the opposite direction. In other words , large β 1 and β 2 will make the non-convergence rare to happen.
We analysis and solve the non-convergence issue of Adam.
{"src": "scitldr-AIC_train", "paper_id": "HkgTkhRcKQ"}