AdaShift: Decorrelation and Convergence of Adaptive Learning Rate Methods

By Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, Yong Yu. 2018

73 citations recorded by the source corpus.

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 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 biased 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.

Subfields: Artificial Intelligence, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Optimization & Training

Citations in the corpus

On Empirical Comparisons of Optimizers for Deep Learning (2019, background): “Others do not even report the value of (cid:15) used (Balles and Hennig, 2017; Zhang and Mitliagkas, 2017; Keskar and Socher, 2017; Chen et al., 2018; Zhou et al., 2018; Aitchison, 2018; Reddi et al., 2019; Luo et al., 2019).”
A Sufficient Condition for Convergences of Adam and RMSProp (2018, methodology): “However, convergence of AdaShift in [25] was merely restricted to RMSProp for solving the convex counterexample in [20].”
A Theory on Adam Instability in Large-Scale Machine Learning (2023, unknown): “Zhou et al. [2018] argue that the fundamental reason behind Adam divergence is the negative correlation between the scale of gradient estimation and the vector of learning rates, which results in a small step size for a large gradient, and a large step size for a small gradient.”
Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization (2019, background): “For instance, AdaShift (Zhou et al., 2019) argues that the convergence issue of Adam is due to its unbalanced step sizes.”
Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity (2019, background): “One elegant approach is variance reduction (e.g. Schmidt et al., 2017; Johnson and Zhang, 2013; Defazio et al., 2014; Bach and Moulines, 2013; Koneˇcn`y and Richt´arik, 2013; Xiao and Zhang, 2014; Gong and Ye, 2014; Fang et al., 2018; Zhou et al., 2018b).”
Why ADAM Beats SGD for Attention Models (2019, background): “Since then, many works studied different interesting aspects of adaptive methods, see (Ward et al., 2018; Li & Orabona, 2018; Zhou et al., 2018a; Staib et al., 2019; Chen et al., 2018; Zou & Shen, 2018; Zhou et al., 2018b; Agarwal et al., 2018; Zou et al., 2019).”