# Momentum Centering and Asynchronous Update for Adaptive Gradient Methods

Juntang Zhuang1; Yifan Ding2; Tommy Tang3; Nicha Dvornek1;
Sekhar Tatikonda1; James S. Duncan1
1 Yale University; 2 University of Central Florida; 3 University of Illinois
at Urbana-Champaign
<EMAIL_ADDRESS>
yf.ding<EMAIL_ADDRESS>
###### Abstract

We propose ACProp (Asynchronous-centering-Prop), an adaptive optimizer which
combines centering of second momentum and asynchronous update (e.g. for $t$-th
update, denominator uses information up to step $t-1$, while numerator uses
gradient at $t$-th step). ACProp has both strong theoretical properties and
empirical performance. With the example by Reddi et al. (2018), we show that
asynchronous optimizers (e.g. AdaShift, ACProp) have weaker convergence
condition than synchronous optimizers (e.g. Adam, RMSProp, AdaBelief); within
asynchronous optimizers, we show that centering of second momentum further
weakens the convergence condition. We demonstrate that ACProp has a
convergence rate of $O(\frac{1}{\sqrt{T}})$ for the stochastic non-convex
case, which matches the oracle rate and outperforms the
$O(\frac{logT}{\sqrt{T}})$ rate of RMSProp and Adam. We validate ACProp in
extensive empirical studies: ACProp outperforms both SGD and other adaptive
optimizers in image classification with CNN, and outperforms well-tuned
adaptive optimizers in the training of various GAN models, reinforcement
learning and transformers. To sum up, ACProp has good theoretical properties
including weak convergence condition and optimal convergence rate, and strong
empirical performance including good generalization like SGD and training
stability like Adam. We provide the implementation at
https://github.com/juntang-zhuang/ACProp-Optimizer.

##  1 Introduction

Deep neural networks are typically trained with first-order gradient
optimizers due to their computational efficiency and good empirical
performance [1]. Current first-order gradient optimizers can be broadly
categorized into the stochastic gradient descent (SGD) [2] family and the
adaptive family. The SGD family uses a global learning rate for all
parameters, and includes variants such as Nesterov-accelerated SGD [3], SGD
with momentum [4] and the heavy-ball method [5]. Compared with the adaptive
family, SGD optimizers typically generalize better but converge slower, and
are the default for vision tasks such as image classification [6], object
detection [7] and segmentation [8].

The adaptive family uses element-wise learning rate, and the representatives
include AdaGrad [9], AdaDelta [10], RMSProp [11], Adam [12] and its variants
such as AdamW [13], AMSGrad [14] AdaBound [15], AdaShift [16], Padam [30],
RAdam [17] and AdaBelief [18]. Compared with the SGD family, the adaptive
optimizers typically converge faster and are more stable, hence are the
default for generative adversarial networks (GANs) [19], transformers [20],
and deep reinforcement learning [21].

We broadly categorize adaptive optimizers according to different criteria, as
in Table. 1. (a) Centered v.s. uncentered Most optimizers such as Adam and
AdaDelta uses uncentered second momentum in the denominator; RMSProp-center
[11], SDProp [22] and AdaBelief [18] use square root of centered second
momentum in the denominator. AdaBelief [18] is shown to achieve good
generalization like the SGD family, fast convergence like the adaptive family,
and training stability in complex settings such as GANs. (b) Sync vs async The
synchronous optimizers typically use gradient $g_{t}$ in both numerator and
denominator, which leads to correlation between numerator and denominator;
most existing optimizers belong to this category. The asynchronous optimizers
decorrelate numerator and denominator (e.g. by using $g_{t}$ as numerator and
use $\\{g_{0},...g_{t-1}\\}$ in denominator for the $t$-th update), and is
shown to have weaker convergence conditions than synchronous optimizers[16].

Table 1: Categories of adaptive optimizers

| Uncentered second momentum | Centered second momentum
---|---|---
Synchronous | Adam , RAdam, AdaDelta, RMSProp, Padam | RMSProp-center, SDProp, AdaBelief
Asynchronous | AdaShift | ACProp (ours)

We propose Asynchronous Centering Prop (ACProp), which combines centering of
second momentum with the asynchronous update. We show that ACProp has both
good theoretical properties and strong empirical performance. Our
contributions are summarized as below:

  * •

Convergence condition  (a) Async vs Sync We show that for the example by Reddi
et al. (2018), asynchronous optimizers (AdaShift, ACProp) converge for any
valid hyper-parameters, while synchronous optimizers (Adam, RMSProp et al.)
could diverge if the hyper-paramaters are not carefully chosen. (b) Async-
Center vs Async-Uncenter Within the asynchronous optimizers family, by example
of an online convex problem with sparse gradients, we show that Async-Center
(ACProp) has weaker conditions for convergence than Async-Uncenter (AdaShift).

  * •

Convergence rate  We demonstrate that ACProp achieves a convergence rate of
$O(\frac{1}{\sqrt{T}})$ for stochastic non-convex problems, matching the
oracle of first-order optimizers [23], and outperforms the
$O(\frac{logT}{\sqrt{T}})$ rate of Adam and RMSProp.

  * •

Empirical performance  We validate performance of ACProp in experiments: on
image classification tasks, ACProp outperforms SGD and AdaBelief, and
demonstrates good generalization performance; in experiments with transformer,
reinforcement learning and various GAN models, ACProp outperforms well-tuned
Adam, demonstrating high stability. ACProp often outperforms AdaBelief, and
achieves good generalization like SGD and training stability like Adam.

##  2 Overview of algorithms

###  2.1 Notations

  * $x,x_{t}\in\mathbb{R}^{d}$:

$x$ is a $d-$dimensional parameter to be optimized, and $x_{t}$ is the value
at step $t$.

  * $f(x),f^{*}\in\mathbb{R}$:

$f(x)$ is the scalar-valued function to be minimized, with optimal (minimal)
$f^{*}$.

  * $\alpha_{t},\epsilon\in\mathbb{R}$:

$\alpha_{t}$ is the learning rate at step $t$. $\epsilon$ is a small number to
avoid division by 0.

  * $g_{t}\in\mathbb{R}^{d}$:

The noisy observation of gradient $\nabla f(x_{t})$ at step $t$.

  * $\beta_{1},\beta_{2}\in\mathbb{R}$:

Constants for exponential moving average, $0\leq\beta_{1},\beta_{2}<1$.

  * $m_{t}\in\mathbb{R}^{d}$:

$m_{t}=\beta_{1}m_{t-1}+(1-\beta_{1})g_{t}$. The Exponential Moving Average
(EMA) of observed gradient at step $t$.

  * $\Delta g_{t}\in\mathbb{R}^{d}$:

$\Delta g_{t}=g_{t}-m_{t}$. The difference between observed gradient $g_{t}$
and EMA of $g_{t}$.

  * $v_{t}\in\mathbb{R}^{d}$:

$v_{t}=\beta_{2}v_{t-1}+(1-\beta_{2})g_{t}^{2}$. The EMA of $g_{t}^{2}$.

  * $s_{t}\in\mathbb{R}^{d}$:

$s_{t}=\beta_{2}s_{t-1}+(1-\beta_{2})(\Delta g_{t})^{2}$. The EMA of $(\Delta
g_{t})^{2}$.

Initialize $x_{0}$, $m_{0}\leftarrow 0$ , $s_{0}\leftarrow 0$, $t\leftarrow 0$

While $x_{t}$ not converged

$t\leftarrow t+1$

$g_{t}\leftarrow\nabla_{x}f_{t}(x_{t-1})$

$m_{t}\leftarrow\beta_{1}m_{t-1}+(1-\beta_{1})g_{t}$

$s_{t}\leftarrow\beta_{2}s_{t-1}{+}(1{-}\beta_{2}){\color[rgb]{0,0,0}(g_{t}{-}m_{t})^{2}}$

${\color[rgb]{0,0,1}x_{t}\leftarrow\prod_{\mathcal{F},\sqrt{s_{t}}}\Big{(}x_{t-1}-\frac{\alpha}{\sqrt{{\color[rgb]{0,0,1}s_{t}}+{\color[rgb]{0,0,1}\epsilon}}}m_{t}\Big{)}}$

Algorithm 1 AdaBelief

Initialize $x_{0}$, $m_{0}\leftarrow 0$ , $s_{0}\leftarrow 0$, $t\leftarrow 0$

While $x_{t}$ not converged

$t\leftarrow t+1$

$g_{t}\leftarrow\nabla_{x}f_{t}(x_{t-1})$

$m_{t}\leftarrow\beta_{1}m_{t-1}+(1-\beta_{1})g_{t}$

${\color[rgb]{0,0,1}x_{t}\leftarrow\prod_{\mathcal{F},\sqrt{s_{t-1}}}\Big{(}x_{t-1}-\frac{\alpha}{\sqrt{{\color[rgb]{0,0,1}s_{t-1}}+{\color[rgb]{0,0,1}\epsilon}}}g_{t}\Big{)}}$

$s_{t}\leftarrow\beta_{2}s_{t-1}{+}(1{-}\beta_{2}){\color[rgb]{0,0,0}(g_{t}{-}m_{t})^{2}}$

Algorithm 2 ACProp

###  2.2 Algorithms

In this section, we summarize the AdaBelief [18] method in Algo. 1 and ACProp
in Algo. 2. For the ease of notations, all operations in Algo. 1 and Algo. 2
are element-wise, and we omit the bias-correction step of $m_{t}$ and $s_{t}$
for simplicity. $\Pi_{\mathcal{F}}$ represents the projection onto feasible
set $\mathcal{F}$.

We first introduce the notion of “sync (async)” and “center (uncenter)”. (a)
Sync vs Async The update on parameter $x_{t}$ can be generally split into a
numerator (e.g. $m_{t},g_{t}$) and a denominator (e.g.
$\sqrt{s_{t}},\sqrt{v_{t}}$). We call it “sync” if the denominator depends on
$g_{t}$, such as in Adam and RMSProp; and call it “async” if the denominator
is independent of $g_{t}$, for example, denominator uses information up to
step $t-1$ for the $t$-th step. (b) Center vs Uncenter The “uncentered” update
uses $v_{t}$, the exponential moving average (EMA) of $g_{t}^{2}$; while the
“centered” update uses $s_{t}$, the EMA of $(g_{t}-m_{t})^{2}$.

Adam (Sync-Uncenter) The Adam optimizer [12] stores the EMA of the gradient in
$m_{t}$, and stores the EMA of $g_{t}^{2}$ in $v_{t}$. For each step of the
update, Adam performs element-wise division between $m_{t}$ and
$\sqrt{v_{t}}$. Therefore, the term $\alpha_{t}\frac{1}{\sqrt{v_{t}}}$ can be
viewed as the element-wise learning rate. Note that $\beta_{1}$ and
$\beta_{2}$ are two scalars controlling the smoothness of the EMA for the
first and second moment, respectively. When $\beta_{1}=0$, Adam reduces to
RMSProp [24].

AdaBelief (Sync-Center) AdaBelief optimizer [18] is summarized in Algo. 1.
Compared with Adam, the key difference is that it replaces the uncentered
second moment $v_{t}$ (EMA of $g_{t}^{2}$) by an estimate of the centered
second moment $s_{t}$ (EMA of $(g_{t}-m_{t})^{2}$). The intuition is to view
$m_{t}$ as an estimate of the expected gradient: if the observation $g_{t}$
deviates much from the prediction $m_{t}$, then it takes a small step; if the
observation $g_{t}$ is close to the prediction $m_{t}$, then it takes a large
step.

AdaShift (Async-Uncenter) AdaShift [16] performs temporal decorrelation
between numerator and denominator. It uses information of
$\\{g_{t-n},...g_{t}\\}$ for the numerator, and uses
$\\{g_{0},...g_{t-n-1}\\}$ for the denominator, where $n$ is the “delay step”
controlling where to split sequence $\\{g_{i}\\}_{i=0}^{t}$. The numerator is
independent of denominator because each $g_{i}$ is only used in either
numerator or denominator.

ACProp (Async-Center) Our proposed ACProp is the asynchronous version of
AdaBelief and is summarized in Algo. 2. Compared to AdaBelief, the key
difference is that ACProp uses $s_{t-1}$ in the denominator for step $t$,
while AdaBelief uses $s_{t}$. Note that $s_{t}$ depends on $g_{t}$, while
$s_{t-1}$ uses history up to step $t-1$. This modification is important to
ensure that
$\mathbb{E}(g_{t}/\sqrt{s_{t-1}}|g_{0},...g_{t-1})=(\mathbb{E}g_{t})/\sqrt{s_{t-1}}$.
It’s also possible to use a delay step larger than 1 similar to AdaShift, for
example, use $EMA(\\{g_{i}\\}_{i=t-n}^{t})$ as numerator, and
$EMA(\\{(g_{i}-m_{i})^{2}\\}_{i=0}^{t-n-1})$ for denominator.

Figure 1: Numerical results for the example defined by Eq. (1). We set the
initial value as $x_{0}=0$, and run each optimizer for $10^{4}$ steps trying
different initial learning rates in
$\\{10^{-5},10^{-4},10^{-3},10^{-2},10^{-1},1.0\\}$, and set the learning rate
decays with $1/\sqrt{t}$. If there’s a proper initial learning rate, such that
the average distance between the parameter and its optimal value $x^{*}=-1$
for the last 1000 steps is below 0.01, then it’s marked as “converge" (orange
plus symbol), otherwise as “diverge” (blue circle). For each optimizer, we
sweep through different $\beta_{2}$ values in a log grid ($x$-axis), and sweep
through different values of $P$ in the definition of problem ($y$-axis). We
plot the result for $\beta_{1}=0.9$ here; for results with different
$\beta_{1}$ values, please refer to appendix. Our results indicate that in the
$(P,\beta_{2})$ plane, there’s a threshold curve beyond which sync-optimizers
(Adam, RMSProp, AdaBelief) will diverge; however, async-optimizers (ACProp,
AdaShift) always converge for any point in the $(P,\beta_{2})$ plane. Note
that for AdaShift, a larger delay step $n$ is possible to cause divergence
(see example in Fig. 2 with $n=10$). To validate that the “divergence” is not
due to numerical issues and sync-optimizers are drifting away from optimal, we
plot trajectories in Fig. 2

##  3 Analyze the conditions for convergence

We analyze the convergence conditions for different methods in this section.
We first analyze the counter example by Reddi et al. (2018) and show that
async-optimizers (AdaShift, ACProp) always converge
$\forall\beta_{1},\beta_{2}\in(0,1)$, while sync-optimizers (Adam, AdaBelief,
RMSProp et al.) would diverge if $(\beta_{1},\beta_{2})$ are not carefully
chosen; hence, async-optimizers have weaker convergence conditions than sync-
optimizers. Next, we compare async-uncenter (AdaShift) with async-center
(ACProp) and show that momentum centering further weakens the convergence
condition for sparse-gradient problems. Therefore, ACProp has weaker
convergence conditions than AdaShift and other sync-optimizers.

###  3.1 Sync vs Async

We show that for the example in [14], async-optimizers (ACProp, AdaShift) have
weaker convergence conditions than sync-optimizers (Adam, RMSProp, AdaBelief).

######  Lemma 3.1 (Thm.1 in [14]).

There exists an online convex optimization problem where sync-optimizers (e.g.
Adam, RMSProp) have non-zero average regret, and one example is

$f_{t}(x)=\begin{cases}Px,&\ \textit{if \ \ }t\%P=1\\\ -x,&\
\textit{Otherwise}\\\ \end{cases}x\in[-1,1],P\in\mathbb{N},P\geq 3$ (1)

######  Lemma 3.2 ([25]).

For problem (1) with any fixed $P$, there’s a threshold of $\beta_{2}$ above
which RMSProp converges.

Figure 2: Trajectories of $x$ for different optimizers in Problem by Eq. 1.
Initial point is $x_{0}=0$, the optimal is $x^{*}=-1$, the trajectories show
that sync-optimizers (Adam, AdaBelief, RMSProp) diverge from the optimal,
validating the divergent area in Fig. 1 is correct rather than artifacts of
numerical issues. Async-optimizers (ACProp, AdaShift) converge to optimal
value, but large delay step $n$ in AdaShift could cause non-convergence.

In order to better explain the two lemmas above, we conduct numerical
experiments on the problem by Eq. (1), and show results in Fig. 1. Note that
$\sum_{t=k}^{k+P}f_{t}(x)=x$, hence the optimal point is $x^{*}=-1$ since
$x\in[-1,1]$. Starting from initial value $x_{0}=0$, we sweep through the
plane of $(P,\beta_{2})$ and plot results of convergence in Fig. 1, and plot
example trajectories in Fig. 2.

Lemma. 3.1 tells half of the story: looking at each vertical line in the
subfigure of Fig. 1, that is, for each fixed hyper-parameter $\beta_{2}$,
there exists sufficiently large $P$ such that Adam (and RMSProp) would
diverge. Lemma. 3.2 tells the other half of the story: looking at each
horizontal line in the subfigure of Fig. 1, for each problem with a fixed
period $P$, there exists sufficiently large $\beta_{2}$s beyond which Adam can
converge.

The complete story is to look at the $(P,\beta_{2})$ plane in Fig. 1. There is
a boundary between convergence and divergence area for sync-optimizers (Adam,
RMSProp, AdaBelief), while async-optimizers (ACProp, AdaShift) always
converge.

######  Lemma 3.3.

For the problem defined by Eq. (1), using learning rate schedule of
$\alpha_{t}=\frac{\alpha_{0}}{\sqrt{t}}$, async-optimizers (ACProp and
AdaShift with $n=1$) always converge
$\forall\beta_{1},\beta_{2}\in(0,1),\forall P\in\mathbb{N},P\geq 3$.

The proof is in the appendix. Note that for AdaShift, proof for the always-
convergence property only holds when $n=1$; larger $n$ could cause divergence
(e.g. $n=10$ causes divergence as in Fig. 2). The always-convergence property
of ACProp and AdaShift comes from the un-biased stepsize, while the stepsize
for sync-optimizers are biased due to correlation between numerator and
denominator. Taking RMSProp as example of sync-optimizer, the update is
$-\alpha_{t}\frac{g_{t}}{\sqrt{v_{t}}}=-\alpha_{t}\frac{g_{t}}{\sqrt{\beta_{2}^{t}g_{0}^{2}+...+\beta_{2}g_{t-1}^{2}+g_{t}^{2}}}$.
Note that $g_{t}$ is used both in the numerator and denominator, hence a large
$g_{t}$ does not necessarily generate a large stepsize. For the example in Eq.
(1), the optimizer observes a gradient of $-1$ for $P-1$ times and a gradient
of $P$ once; due to the biased stepsize in sync-optimizers, the gradient of
$P$ does not generate a sufficiently large stepsize to compensate for the
effect of wrong gradients $-1$, hence cause non-convergence. For async-
optimizers, $g_{t}$ is not used in the denominator, therefore, the stepsize is
not biased and async-optimizers has the always-convergence property.

Remark Reddi et al. (2018) proposed AMSGrad to track the element-wise maximum
of $v_{t}$ in order to achieve the always-convergence property. However,
tracking the maximum in the denominator will in general generate a small
stepsize, which often harms empirical performance. We demonstrate this through
experiments in later sections in Fig. 6.

Figure 3: Area of convergence for the problem in Eq. (2). The numerical
experiment is performed under the same setting as in Fig. 1.Our results
experimentally validated the claim that compared with async-uncenter
(AdaShift), async-center (ACProp) has a larger convergence area in the hyper-
parameter space.

###  3.2 Async-Uncenter vs Async-Center

In the last section, we demonstrated that async-optimizers have weaker
convergence conditions than sync-optimizers. In this section, within the
async-optimizer family, we analyze the effect of centering second momentum. We
show that compared with async-uncenter (AdaShift), async-center (ACProp) has
weaker convergence conditions. We consider the following online convex
problem:

$f_{t}(x)=\begin{cases}P/2\times x,\ \ \ t\%P==1\\\ -x,\ \ \ \ \ \ \ \ \ \ \
t\%P==P-2\\\ 0,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{otherwise}\\\
\end{cases}P>3,P\in\mathbb{N},x\in[0,1].$

(2)

Initial point is $x_{0}=0.5$. Optimal point is $x^{*}=0$. We have the
following results:

######  Lemma 3.4.

For the problem defined by Eq. (2), consider the hyper-parameter tuple
$(\beta_{1},\beta_{2},P)$, there exists cases where ACProp converges but
AdaShift with $n=1$ diverges, but not vice versa.

We provide the proof in the appendix. Lemma. 3.4 implies that ACProp has a
larger area of convergence than AdaShift, hence the centering of second
momentum further weakens the convergence conditions. We first validate this
claim with numerical experiments in Fig. 3; for sanity check, we plot the
trajectories of different optimizers in Fig. 4. We observe that the
convergence of AdaShift is influenced by delay step $n$, and there’s no good
criterion to select a good value of $n$, since Fig. 2 requires a small $n$ for
convergence in problem (1), while Fig. 4 requires a large $n$ for convergence
in problem (2). ACProp has a larger area of convergence, indicating that both
async update and second momentum centering helps weaken the convergence
conditions.

We provide an intuitive explanation on why momentum centering helps
convergence. Due to the periodicity of the problem, the optimizer behaves
almost periodically as $t\to\infty$. Within each period, the optimizer
observes one positive gradient $P/2$ and one negative gradient -1. As in Fig.
5, between observing non-zero gradients, the gradient is always 0. Within each
period, ACprop will perform a positive update $P/(2\sqrt{s^{+}})$ and a
negative update $-1/\sqrt{s^{-}}$, where $s^{+}$ ($s^{-}$) is the value of
denominator before observing positive (negative) gradient. Similar notations
for $v^{+}$ and $v^{-}$ in AdaShift. A net update in the correct direction
requires $\frac{P}{2\sqrt{s^{+}}}>\frac{1}{\sqrt{s^{-}}}$, (or
$s^{+}/s^{-}<P^{2}/4$).

When observing 0 gradient, for AdaShift,
$v_{t}=\beta_{2}v_{t-1}+(1-\beta_{2})0^{2}$; for ACProp,
$s_{t}=\beta_{2}s_{t-1}+(1-\beta_{2})(0-m_{t})^{2}$ where $m_{t}\neq 0$.
Therefore, $v^{-}$ decays exponentially to 0, but $s^{-}$ decays to a non-zero
constant, hence $\frac{s^{+}}{s^{-}}<\frac{v^{+}}{v^{-}}$, hence ACProp is
easier to satisfy $s^{+}/s^{-}<P^{2}/4$ and converge.

Figure 4: Trajectories for problem defined by Eq. (2). Note that the optimal
point is $x^{*}=0$.

Figure 5: Value of uncentered second momentum $v_{t}$ and centered momentum
$s_{t}$ for problem (2).

##  4 Analysis on convergence rate

In this section, we show that ACProp converges at a rate of $O(1/\sqrt{T})$ in
the stochastic nonconvex case, which matches the oracle [23] for first-order
optimizers and outperforms the $O(logT/\sqrt{T})$ rate for sync-optimizers
(Adam, RMSProp and AdaBelief) [26, 25, 18]. We further show that the upper
bound on regret of async-center (ACProp) outperforms async-uncenter (AdaShift)
by a constant.

For the ease of analysis, we denote the update as:
$x_{t}=x_{t-1}-\alpha_{t}A_{t}g_{t}$, where $A_{t}$ is the diagonal
preconditioner. For SGD, $A_{t}=I$; for sync-optimizers (RMSProp),
$A_{t}=\frac{1}{\sqrt{v_{t}}+\epsilon}$; for AdaShift with $n=1$,
$A_{t}=\frac{1}{\sqrt{v_{t-1}}+\epsilon}$; for ACProp,
$A_{t}=\frac{1}{\sqrt{s_{t-1}}+\epsilon}$. For async optimizers,
$\mathbb{E}[A_{t}g_{t}|g_{0},...g_{t-1}]=A_{t}\mathbb{E}g_{t}$; for sync-
optimizers, this does not hold because $g_{t}$ is used in $A_{t}$

######  Theorem 4.1 (convergence for stochastic non-convex case).

Under the following assumptions:

  * •

$f$ is continuously differentiable, $f$ is lower-bounded by $f^{*}$ and upper
bounded by $M_{f}$. $\nabla f(x)$ is globally Lipschitz continuous with
constant $L$:

$||\nabla f(x)-\nabla f(y)||\leq L||x-y||$ (3)

  * •

For any iteration $t$, $g_{t}$ is an unbiased estimator of $\nabla f(x_{t})$
with variance bounded by $\sigma^{2}$. Assume norm of $g_{t}$ is bounded by
$M_{g}$.

$\mathbb{E}\big{[}g_{t}\big{]}=\nabla f(x_{t})\ \ \ \
\mathbb{E}\big{[}||g_{t}-\nabla f(x_{t})||^{2}\big{]}\leq\sigma^{2}$ (4)

then for $\beta_{1},\beta_{2}\in[0,1)$, with learning rate schedule as:
$\alpha_{t}=\alpha_{0}t^{-\eta},\ \ \alpha_{0}\leq\frac{C_{l}}{LC_{u}^{2}},\ \
\eta\in[0.5,1)$
for the sequence $\\{x_{t}\\}$ generated by ACProp, we have

$\frac{1}{T}\sum_{t=1}^{T}\Big{|}\Big{|}\nabla
f(x_{t})\Big{|}\Big{|}^{2}\leq\frac{2}{C_{l}}\Big{[}(M_{f}-f^{*})\alpha_{0}T^{\eta-1}+\frac{LC_{u}^{2}\sigma^{2}\alpha_{0}}{2(1-\eta)}T^{-\eta}\Big{]}$
(5)

where $C_{l}$ and $C_{u}$ are scalars representing the lower and upper bound
for $A_{t}$, e.g. $C_{l}I\preceq A_{t}\preceq C_{u}I$, where $A\preceq B$
represents $B-A$ is semi-positive-definite.

Note that there’s a natural bound for $C_{l}$ and $C_{u}$:
$C_{u}\leq\frac{1}{\epsilon}$ and $C_{l}\geq\frac{1}{2M_{g}}$ because
$\epsilon$ is added to denominator to avoid division by 0, and $g_{t}$ is
bounded by $M_{g}$. Thm. 4.1 implies that ACProp has a convergence rate of
$O(1/\sqrt{T})$ when $\eta=0.5$; equivalently, in order to have $||\nabla
f(x)||^{2}\leq\delta^{2}$, ACProp requires at most $O(\delta^{-4})$ steps.

######  Theorem 4.2 (Oracle complexity [23]).

For a stochastic non-convex problem satisfying assumptions in Theorem. 4.1,
using only up to first-order gradient information, in the worst case any
algorithm requires at least $O(\delta^{-4})$ queries to find a
$\delta$-stationary point $x$ such that $||\nabla f(x)||^{2}\leq\delta^{2}$.

Optimal rate in big O Thm. 4.1 and Thm. 4.2 imply that async-optimizers
achieves a convergence rate of $O(1/\sqrt{T})$ for the stochastic non-convex
problem, which matches the oracle complexity and outperforms the
$O(logT/\sqrt{T})$ rate of sync-optimizers (Adam [14], RMSProp[25], AdaBelief
[18]). Adam and RMSProp are shown to achieve $O(1/\sqrt{T})$ rate under the
stricter condition that $\beta_{2,t}\to 1$ [27]. A similar rate has been
achieved in AVAGrad [28], and AdaGrad is shown to achieve a similar rate [29].
Despite the same convergence rate, we show that ACProp has better empirical
performance.

Constants in the upper bound of regret Though both async-center and async-
uncenter optimizers have the same convergence rate with matching upper and
lower bound in big O notion, the constants of the upper bound on regret is
different. Thm. 4.1 implies that the upper bound on regret is an increasing
function of $1/C_{l}$ and $C_{u}$, and

$1/C_{l}=\sqrt{K_{u}}+\epsilon,\ \ C_{u}=1/(\sqrt{K_{l}}+\epsilon)$

where $K_{l}$ and $K_{u}$ are the lower and upper bound of second momentum,
respectively.

We analyze the constants in regret by analyzing $K_{l}$ and $K_{u}$. If we
assume the observed gradient $g_{t}$ follows some independent stationary
distribution, with mean $\mu$ and variance $\sigma^{2}$, then approximately

$\displaystyle\textit{Uncentered second momentum:
}1/C_{l}^{v}=\sqrt{K_{u}^{v}}+\epsilon\approx\sqrt{\mu^{2}+\sigma^{2}}+\epsilon$
(6) $\displaystyle\textit{Centered second momentum:
}1/C_{l}^{s}=\sqrt{K_{u}^{s}}+\epsilon\approx\sqrt{\sigma^{2}}+\epsilon$ (7)

During early phase of training, in general $|\mu|\gg\sigma$, hence
$1/C_{l}^{s}\ll 1/C_{l}^{v}$, and the centered version (ACProp) can converge
faster than uncentered type (AdaShift) by a constant factor of around
$\frac{\sqrt{\mu^{2}+\sigma^{2}}+\epsilon}{\sqrt{\sigma^{2}}+\epsilon}$.
During the late phase, $g_{t}$ is centered around 0, and $|\mu|\ll\sigma$,
hence $K_{l}^{v}$ (for uncentered version) and $K_{l}^{s}$ (for centered
version) are both close to 0, hence $C_{u}$ term is close for both types.

Remark We emphasize that ACProp rarely encounters numerical issues caused by a
small $s_{t}$ as denominator, even though Eq. (7) implies a lower bound for
$s_{t}$ around $\sigma^{2}$ which could be small in extreme cases. Note that
$s_{t}$ is an estimate of mixture of two aspects: the change in true gradient
$||\nabla f_{t}(x)-\nabla f_{t-1}(x)||^{2}$, and the noise in $g_{t}$ as an
observation of $\nabla f(x)$. Therefore, two conditions are essential to
achieve $s_{t}=0$: the true gradient $\nabla f_{t}(x)$ remains constant, and
$g_{t}$ is a noise-free observation of $\nabla f_{t}(x)$. Eq. (7) is based on
assumption that $||\nabla f_{t}(x)-\nabla f_{t-1}(x)||^{2}=0$, if we further
assume $\sigma=0$, then the problem reduces to a trivial ideal case: a linear
loss surface with clean observations of gradient, which is rarely satisfied in
practice. More discussions are in appendix.

Figure 6: From left to right: (a) Mean value of denominator for a 2-layer MLP
on MNIST dataset. (b) Training loss of different optimizers for the 2-layer
MLP model. (c) Performance of AdaShift for VGG-11 on CIFAR10 varying with
learning rate ranging from 1e-1 to 1e-5, we plot the performance of ACProp
with learning rate 1e-3 as reference. Missing lines are because their accuracy
are below display threshold. All methods decay learning rate by a factor of 10
at 150th epoch. (d) Performance of AMSGrad for VGG-11 on CIFAR10 varying with
learning rate under the same setting in (c).

Empirical validations We conducted experiments on the MNIST dataset using a
2-layer MLP. We plot the average value of $v_{t}$ for uncentered-type and
$s_{t}$ for centered-type optimizers; as Fig. 6(a,b) shows, we observe
$s_{t}\leq v_{t}$ and the centered-type (ACProp, AdaBelief) converges faster,
validating our analysis for early phases. For epochs $>10$, we observe that
$\operatorname{min}s_{t}\approx\operatorname{min}v_{t}$, validating our
analysis for late phases.

As in Fig. 6(a,b), the ratio $v_{t}/s_{t}$ decays with training, and in fact
it depends on model structure and dataset noise. Therefore, empirically it’s
hard to compensate for the constants in regret by applying a larger learning
rate for async-uncenter optimizers. As shown in Fig. 6(c,d), for VGG network
on CIFAR10 classification task, we tried different initial learning rates for
AdaShift (async-uncenter) and AMSGrad ranging from 1e-1 to 1e-5, and their
performances are all inferior to ACProp with a learning rate 1e-3. Please see
Fig.9 for a complete table varying with hyper-parameters.

##  5 Experiments

We validate the performance of ACProp in various experiments, including image
classification with convolutional neural networks (CNN), reinforcement
learning with deep Q-network (DQN), machine translation with transformer and
generative adversarial networks (GANs). We aim to test both the generalization
performance and training stability: SGD family optimizers typically are the
default for CNN models such as in image recognition [6] and object detection
[7] due to their better generalization performance than Adam; and Adam is
typically the default for GANs [19], reinforcement learning [21] and
transformers [20], mainly due to its better numerical stability and faster
convergence than SGD. We aim to validate that ACProp can perform well for both
cases.

Figure 7: Test accuracy ($mean\pm std$) on CIFAR10 datset. Left to right:
VGG-11, ResNet-34, DenseNet-121.

Figure 8: Test accuracy (%) of VGG network on CIFAR10 under different hyper-
parameters. We tested learning rate in $\\{10^{-1},10^{-2},10^{-3},10^{-4}\\}$
and $\epsilon\in\\{10^{-5},...,10^{-9}\\}$.

Figure 9: The reward (higher is better) curve of a DQN-network on the four-
rooms problem. We report the mean and standard deviation across 10 independent
runs.

Table 2: Top-1 accuracy of ResNet18 on ImageNet. ⋄ is reported in PyTorch
Documentation, ${\dagger}$ is reported in [chen2020closing], $\ast$ is
reported in [17], ‡ is reported in [18]

SGD | Padam | Adam | AdamW | RAdam | AdaShift | AdaBelief | ACProp
---|---|---|---|---|---|---|---
69.76⋄ (70.23†) | 70.07† | 66.54∗ | 67.93† | 67.62∗ | 65.28 | 70.08${\ddagger}$ | 70.46

Image classification with CNN We first conducted experiments on CIFAR10 image
classification task with a VGG-11 [31], ResNet34 [6] and DenseNet-121 [32]. We
performed extensive hyper-parameter tuning in order to better compare the
performance of different optimizers: for SGD we set the momentum as 0.9 which
is the default for many cases [6, 32], and search the learning rate between
0.1 and $10^{-5}$ in the log-grid; for other adaptive optimizers, including
AdaBelief, Adam, RAdam, AdamW and AdaShift, we search the learning rate
between 0.01 and $10^{-5}$ in the log-grid, and search $\epsilon$ between
$10^{-5}$ and $10^{-10}$ in the log-grid. We use a weight decay of 5e-2 for
AdamW, and use 5e-4 for other optimizers. We report the $mean\pm std$ for the
best of each optimizer in Fig. 7: for VGG and ResNet, ACProp achieves
comparable results with AdaBelief and outperforms other optimizers; for
DenseNet, ACProp achieves the highest accuracy and even outperforms AdaBelief
by 0.5%. As in Table 2, for ResNet18 on ImageNet, ACProp outperforms other
methods and achieves comparable accuracy to the best of SGD in the literature,
validating its generalization performance.

To evaluate the robustness to hyper-parameters, we test the performance of
various optimizers under different hyper-parameters with VGG network. We plot
the results for ACProp and AdaShift as an example in Fig. 9 and find that
ACProp is more robust to hyper-parameters and typically achieves higher
accuracy than AdaShift.

Table 3:  BLEU score (higher is better) on machine translation with
Transformer

| Adam | RAdam | AdaShift | AdaBelief | ACProp
---|---|---|---|---|---
DE-EN | 34.66$\pm$0.014 | 34.76$\pm$0.003 | 30.18$\pm$0.020 | 35.17$\pm$0.015 | 35.35$\pm$0.012
EN-VI | 21.83$\pm$0.015 | 22.54$\pm$0.005 | 20.18$\pm$0.231 | 22.45$\pm$0.003 | 22.62$\pm$0.008
JA-EN | 33.33$\pm$0.008 | 32.23$\pm$0.015 | 25.24$\pm$0.151 | 34.38$\pm$0.009 | 33.70$\pm$0.021
RO-EN | 29.78$\pm$ 0.003 | 30.26 $\pm$ 0.011 | 27.86$\pm$0.024 | 30.03$\pm$0.012 | 30.27$\pm$0.007

Table 4: FID (lower is better) for GANs

| Adam | RAdam | AdaShift | AdaBelief | ACProp
---|---|---|---|---|---
DCGAN | 49.29$\pm$0.25 | 48.24$\pm$1.38 | 99.32$\pm$3.82 | 47.25$\pm$0.79 | 43.43$\pm$4.38
RLGAN | 38.18$\pm$0.01 | 40.61$\pm$0.01 | 56.18 $\pm$0.23 | 36.58$\pm$0.12 | 37.15$\pm$0.13
SNGAN | 13.14$\pm$0.10 | 13.00$\pm$0.04 | 26.62$\pm$0.21 | 12.70$\pm$0.17 | 12.44$\pm$0.02
SAGAN | 13.98$\pm$0.02 | 14.25$\pm$0.01 | 22.11$\pm$0.25 | 14.17$\pm$0.14 | 13.54$\pm$0.15

Table 5: Performance comparison between AVAGrad and ACProp. $\uparrow$
($\downarrow$) represents metrics that upper (lower) is better. ⋆ are reported
in the AVAGrad paper [28]

| WideResNet Test Error ($\downarrow$) | Transformer BLEU ($\uparrow$) | GAN FID ($\downarrow$)
---|---|---|---
| CIFAR10 | CIFAR100 | DE-EN | RO-EN | DCGAN | SNGAN
AVAGrad | 3.80⋆$\pm$0.02 | 18.76⋆$\pm$0.20 | 30.23$\pm$0.024 | 27.73$\pm$0.134 | 59.32$\pm$3.28 | 21.02$\pm$0.14
ACProp | 3.67$\pm$0.04 | 18.72$\pm$0.01 | 35.35$\pm$0.012 | 30.27$\pm$0.007 | 43.34$\pm$4.38 | 12.44$\pm$0.02

Reinforcement learning with DQN We evaluated different optimizers on
reinforcement learning with a deep Q-network (DQN) [21] on the four-rooms task
[33]. We tune the hyper-parameters in the same setting as previous section. We
report the mean and standard deviation of reward (higher is better) across 10
runs in Fig. 9. ACProp achieves the highest mean reward, validating its
numerical stability and good generalization.

Neural machine translation with Transformer We evaluated the performance of
ACProp on neural machine translation tasks with a transformer model [20]. For
all optimizers, we set learning rate as 0.0002, and search for
$\beta_{1}\in\\{0.9,0.99,0.999\\}$, $\beta_{2}\in\\{0.98,0.99,0.999\\}$ and
$\epsilon\in\\{10^{-5},10^{-6},...10^{-16}\\}$. As shown in Table. 3, ACProp
achieves the highest BLEU score in 3 out 4 tasks, and consistently outperforms
a well-tuned Adam.

Generative Adversarial Networks (GAN) The training of GANs easily suffers from
mode collapse and numerical instability [34], hence is a good test for the
stability of optimizers. We conducted experiments with Deep Convolutional GAN
(DCGAN) [35], Spectral-Norm GAN (SNGAN) [36], Self-Attention GAN (SAGAN) [37]
and Relativistic-GAN (RLGAN) [38]. We set $\beta_{1}=0.5$, and search for
$\beta_{2}$ and $\epsilon$ with the same schedule as previous section. We
report the FID [39] on CIFAR10 dataset in Table. 4, where a lower FID
represents better quality of generated images. ACProp achieves the best
overall FID score and outperforms well-tuned Adam.

Remark Besides AdaShift, we found another async-optimizer named AVAGrad in
[28]. Unlike other adaptive optimizers, AVAGrad is not scale-invariant hence
the default hyper-parameters are very different from Adam-type
($lr=0.1,\epsilon=0.1$). We searched for hyper-parameters for AVAGrad for a
much larger range, with $\epsilon$ between 1e-8 and 100 in the log-grid, and
$lr$ between 1e-6 and 100 in the log-grid. For experiments with a WideResNet,
we replace the optimizer in the official implementation for AVAGrad by ACProp,
and cite results in the AVAGrad paper. As in Table 5, ACProp consistently
outperforms AVAGrad in CNN, Transformer, and GAN training.

##  6 Related Works

Besides the aforementioned, other variants of Adam include NosAdam [40], Sadam
[41], Adax [42]), AdaBound [15] and Yogi [43]. ACProp could be combined with
other techniques such as SWATS [44], LookAhead [45] and norm regularization
similar to AdamP [46]. Regarding the theoretical analysis, recent research has
provided more fine-grained frameworks [47, 48]. Besides first-order methods,
recent research approximate second-order methods in deep learning [49, 50,
51].

##  7 Conclusion

We propose ACProp, a novel first-order gradient optimizer which combines the
asynchronous update and centering of second momentum. We demonstrate that
ACProp has good theoretical properties: ACProp has a “always-convergence"
property for the counter example by Reddi et al. (2018), while sync-optimizers
(Adam, RMSProp) could diverge with uncarefully chosen hyper-parameter; for
problems with sparse gradient, async-centering (ACProp) has a weaker
convergence condition than async-uncentering (AdaShift); ACProp achieves the
optimal convergence rate $O(1/\sqrt{T})$, outperforming the $O(logT/\sqrt{T})$
rate of RMSProp (Adam), and achieves a tighter upper bound on risk than
AdaShift. In experiments, we validate that ACProp has good empirical
performance: it achieves good generalization like SGD, fast convergence and
training stability like Adam, and often outperforms Adam and AdaBelief.

## Acknowledgments and Disclosure of Funding

This research is supported by NIH grant R01NS035193.

## References

  * [1] Ruoyu Sun,  “Optimization for deep learning: theory and algorithms,”  arXiv preprint arXiv:1912.08957, 2019.
  * [2] Herbert Robbins and Sutton Monro,  “A stochastic approximation method,”  The annals of mathematical statistics, pp. 400–407, 1951.
  * [3] Yu Nesterov,  “A method of solving a convex programming problem with convergence rate o(1/k2̂),”  in Sov. Math. Dokl, 1983.
  * [4] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton,  “On the importance of initialization and momentum in deep learning,”  in International conference on machine learning, 2013, pp. 1139–1147.
  * [5] Boris T Polyak,  “Some methods of speeding up the convergence of iteration methods,”  USSR Computational Mathematics and Mathematical Physics, vol. 4, no. 5, pp. 1–17, 1964.
  * [6] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep residual learning for image recognition,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.
  * [7] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun,  “Faster r-cnn: Towards real-time object detection with region proposal networks,”  arXiv preprint arXiv:1506.01497, 2015.
  * [8] Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla,  “Segnet: A deep convolutional encoder-decoder architecture for image segmentation,”  IEEE transactions on pattern analysis and machine intelligence, vol. 39, no. 12, pp. 2481–2495, 2017.
  * [9] John Duchi, Elad Hazan, and Yoram Singer,  “Adaptive subgradient methods for online learning and stochastic optimization,”  Journal of machine learning research, vol. 12, no. Jul, pp. 2121–2159, 2011.
  * [10] Matthew D Zeiler,  “Adadelta: an adaptive learning rate method,”  arXiv preprint arXiv:1212.5701, 2012.
  * [11] Alex Graves,  “Generating sequences with recurrent neural networks,”  arXiv preprint arXiv:1308.0850, 2013.
  * [12] Diederik P Kingma and Jimmy Ba,  “Adam: A method for stochastic optimization,”  arXiv preprint arXiv:1412.6980, 2014.
  * [13] Ilya Loshchilov and Frank Hutter,  “Decoupled weight decay regularization,”  arXiv preprint arXiv:1711.05101, 2017.
  * [14] Sashank J Reddi, Satyen Kale, and Sanjiv Kumar,  “On the convergence of adam and beyond,”  International Conference on Learning Representations, 2018.
  * [15] Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun,  “Adaptive gradient methods with dynamic bound of learning rate,”  arXiv preprint arXiv:1902.09843, 2019.
  * [16] Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, and Yong Yu,  “Adashift: Decorrelation and convergence of adaptive learning rate methods,”  in International Conference on Learning Representations, 2019.
  * [17] Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han,  “On the variance of the adaptive learning rate and beyond,”  arXiv preprint arXiv:1908.03265, 2019.
  * [18] Juntang Zhuang, Tommy Tang, Sekhar Tatikonda, Nicha Dvornek, Yifan Ding, Xenophon Papademetris, and James S Duncan,  “Adabelief optimizer: Adapting stepsizes by the belief in observed gradients,”  arXiv preprint arXiv:2010.07468, 2020.
  * [19] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio,  “Generative adversarial nets,”  in Advances in neural information processing systems, 2014, pp. 2672–2680.
  * [20] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin,  “Attention is all you need,”  Advances in neural information processing systems, vol. 30, pp. 5998–6008, 2017.
  * [21] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller,  “Playing atari with deep reinforcement learning,”  arXiv preprint arXiv:1312.5602, 2013.
  * [22] Yasutoshi Ida, Yasuhiro Fujiwara, and Sotetsu Iwamura,  “Adaptive learning rate via covariance matrix based preconditioning for deep neural networks,”  arXiv preprint arXiv:1605.09593, 2016.
  * [23] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth,  “Lower bounds for non-convex stochastic optimization,”  arXiv preprint arXiv:1912.02365, 2019.
  * [24] Geoffrey Hinton,  “Rmsprop: Divide the gradient by a running average of its recent magnitude,”  Coursera, 2012.
  * [25] Naichen Shi, Dawei Li, Mingyi Hong, and Ruoyu Sun,  “{RMS}prop can converge with proper hyper-parameter,”  in International Conference on Learning Representations, 2021.
  * [26] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong,  “On the convergence of a class of adam-type algorithms for non-convex optimization,”  arXiv preprint arXiv:1808.02941, 2018.
  * [27] Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu,  “A sufficient condition for convergences of adam and rmsprop,”  in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019, pp. 11127–11135.
  * [28] Pedro Savarese, David McAllester, Sudarshan Babu, and Michael Maire,  “Domain-independent dominance of adaptive methods,”  arXiv preprint arXiv:1912.01823, 2019.
  * [29] Xiaoyu Li and Francesco Orabona,  “On the convergence of stochastic gradient descent with adaptive stepsizes,”  in The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019, pp. 983–992.
  * [30] Jinghui Chen and Quanquan Gu,  “Closing the generalization gap of adaptive gradient methods in training deep neural networks,”  arXiv preprint arXiv:1806.06763, 2018.
  * [31] Karen Simonyan and Andrew Zisserman,  “Very deep convolutional networks for large-scale image recognition,”  arXiv preprint arXiv:1409.1556, 2014.
  * [32] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger,  “Densely connected convolutional networks,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 4700–4708.
  * [33] Richard S Sutton, Doina Precup, and Satinder Singh,  “Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning,”  Artificial intelligence, vol. 112, no. 1-2, pp. 181–211, 1999.
  * [34] Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen,  “Improved techniques for training gans,”  in Advances in neural information processing systems, 2016, pp. 2234–2242.
  * [35] Alec Radford, Luke Metz, and Soumith Chintala,  “Unsupervised representation learning with deep convolutional generative adversarial networks,”  arXiv preprint arXiv:1511.06434, 2015.
  * [36] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida,  “Spectral normalization for generative adversarial networks,”  arXiv preprint arXiv:1802.05957, 2018.
  * [37] Han Zhang, Ian Goodfellow, Dimitris Metaxas, and Augustus Odena,  “Self-attention generative adversarial networks,”  in International conference on machine learning. PMLR, 2019, pp. 7354–7363.
  * [38] Alexia Jolicoeur-Martineau,  “The relativistic discriminator: a key element missing from standard gan,”  arXiv preprint arXiv:1807.00734, 2018.
  * [39] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter,  “Gans trained by a two time-scale update rule converge to a local nash equilibrium,”  in Advances in neural information processing systems, 2017, pp. 6626–6637.
  * [40] Haiwen Huang, Chang Wang, and Bin Dong,  “Nostalgic adam: Weighting more of the past gradients when designing the adaptive learning rate,”  arXiv preprint arXiv:1805.07557, 2018.
  * [41] Guanghui Wang, Shiyin Lu, Weiwei Tu, and Lijun Zhang,  “Sadam: A variant of adam for strongly convex functions,”  arXiv preprint arXiv:1905.02957, 2019.
  * [42] Wenjie Li, Zhaoyang Zhang, Xinjiang Wang, and Ping Luo,  “Adax: Adaptive gradient descent with exponential long term memory,”  arXiv preprint arXiv:2004.09740, 2020.
  * [43] Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar,  “Adaptive methods for nonconvex optimization,”  in Advances in neural information processing systems, 2018, pp. 9793–9803.
  * [44] Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson,  “Averaging weights leads to wider optima and better generalization,”  arXiv preprint arXiv:1803.05407, 2018.
  * [45] Michael Zhang, James Lucas, Jimmy Ba, and Geoffrey E Hinton,  “Lookahead optimizer: k steps forward, 1 step back,”  in Advances in Neural Information Processing Systems, 2019, pp. 9593–9604.
  * [46] Byeongho Heo, Sanghyuk Chun, Seong Joon Oh, Dongyoon Han, Sangdoo Yun, Gyuwan Kim, Youngjung Uh, and Jung-Woo Ha,  “Adamp: Slowing down the slowdown for momentum optimizers on scale-invariant weights,”  in Proceedings of the International Conference on Learning Representations (ICLR), Online, 2021, pp. 3–7.
  * [47] Ahmet Alacaoglu, Yura Malitsky, Panayotis Mertikopoulos, and Volkan Cevher,  “A new regret analysis for adam-type algorithms,”  in International Conference on Machine Learning. PMLR, 2020, pp. 202–210.
  * [48] Xiaoyu Li, Zhenxun Zhuang, and Francesco Orabona,  “Exponential step sizes for non-convex optimization,”  arXiv preprint arXiv:2002.05273, 2020.
  * [49] James Martens,  “Deep learning via hessian-free optimization.,”  in ICML, 2010, vol. 27, pp. 735–742.
  * [50] Zhewei Yao, Amir Gholami, Sheng Shen, Kurt Keutzer, and Michael W Mahoney,  “Adahessian: An adaptive second order optimizer for machine learning,”  arXiv preprint arXiv:2006.00719, 2020.
  * [51] Xuezhe Ma,  “Apollo: An adaptive parameter-wise diagonal quasi-newton method for nonconvex stochastic optimization,”  arXiv preprint arXiv:2009.13586, 2020.
  * [52] Shi Naichen, Li Dawei, Hong Mingyi, and Sun Ruoyu,  “Rmsprop can converge with proper hyper-parameter,”  ICLR, 2021.

###### Contents

  1. 1 Introduction
  2. 2 Overview of algorithms
    1. 2.1 Notations
    2. 2.2 Algorithms
  3. 3 Analyze the conditions for convergence
    1. 3.1 Sync vs Async
    2. 3.2 Async-Uncenter vs Async-Center
  4. 4 Analysis on convergence rate
  5. 5 Experiments
  6. 6 Related Works
  7. 7 Conclusion
  8. A Analysis on convergence conditions
    1. A.1 Convergence analysis for Problem 1 in the main paper
      1. A.1.1 Numerical validations
    2. A.2 Convergence analysis for Problem 2 in the main paper
    3. A.3 Numerical experiments
  9. B Convergence Analysis for stochastic non-convex optimization
    1. B.1 Problem definition and assumptions
    2. B.2 Convergence analysis of Async-optimizers in stochastic non-convex optimization
      1. B.2.1 Validation on numerical accuracy of sum of generalized harmonic series
    3. B.3 Convergence analysis of Async-moment-optimizers in stochastic non-convex optimization
  10. C Experiments
    1. C.1 Centering of second momentum does not suffer from numerical issues
    2. C.2 Image classification with CNN
    3. C.3 Neural Machine Translation with Transformers
    4. C.4 Generative adversarial networks

##  Appendix A Analysis on convergence conditions

###  A.1 Convergence analysis for Problem 1 in the main paper

######  Lemma A.1.

There exists an online convex optimization problem where Adam (and RMSprop)
has non-zero average regret, and one of the problem is in the form

$f_{t}(x)=\begin{cases}Px,&\ \ \textit{if }t\mathrm{\ mod\ }P=1\\\ -x,&\ \
\textit{Otherwise}\\\ \end{cases}\ \ x\in[-1,1],\exists P\in\mathbb{N},P\geq
3$ (8)

###### Proof.

See [14] Thm.1 for proof. ∎

######  Lemma A.2.

For the problem defined above, there’s a threshold of $\beta_{2}$ above which
RMSprop converge.

###### Proof.

See [52] for details. ∎

######  Lemma A.3 (Lemma.3.3 in the main paper).

For the problem defined by Eq. (8), ACProp algorithm converges
$\forall\beta_{1},\beta_{2}\in(0,1),\forall P\in\mathbb{N},P\geq 3$.

###### Proof.

We analyze the limit behavior of ACProp algorithm. Since the observed gradient
is periodic with an integer period $P$, we analyze one period from with
indices from $kP$ to $kP+P$, where $k$ is an integer going to $+\infty$.

From the update of ACProp, we observe that:

$\displaystyle m_{kP}$
$\displaystyle=(1-\beta_{1})\sum_{i=1}^{kP}\beta_{1}^{kP-i}\times(-1)+(1-\beta_{1})\sum_{j=0}^{k-1}\beta_{1}^{kP-(jP+1)}(P+1)$
(9) $\displaystyle\Big{(}\textit{For each observation with gradient
}P,\textit{we break it into }P=-1+(P+1)\Big{)}$
$\displaystyle=-(1-\beta_{1})\sum_{i=1}^{kP}\beta_{1}^{kP-i}+(1-\beta_{1})(P+1)\beta_{1}^{-1}\sum_{j=0}^{k-1}\beta_{1}^{P(k-j)}$
(10)
$\displaystyle=-(1-\beta_{1}^{kP})+(1-\beta_{1})(P+1)\beta_{1}^{P-1}\frac{1-\beta_{1}^{(k-1)P}}{1-\beta_{1}^{P}}$
(11) $\displaystyle\lim_{k\to\infty}m_{kP}$
$\displaystyle=-1+(P+1)(1-\beta_{1})\beta_{1}^{P-1}\frac{1}{1-\beta_{1}^{P}}=\frac{(P+1)\beta_{1}^{P-1}-P\beta_{1}^{P}-1}{1-\beta_{1}^{P}}$
(12) $\displaystyle\Big{(}\textit{Since }\beta_{1}\in[0,1)\Big{)}$

Next, we derive $\lim_{k\to\infty}S_{kP}$. Note that the observed gradient is
periodic, and $\lim_{k\to\infty}m_{kP}=\lim_{k\to\infty}m_{kP+P}$, hence
$\lim_{k\to\infty}S_{kP}=\lim_{k\to\infty}S_{kP+P}$. Start from index $kP$, we
derive variables up to $kP+P$ with ACProp algorithm.

$\displaystyle index=kP,$ $\displaystyle m_{kP}$ $\displaystyle,S_{kP}$ (13)
$\displaystyle index=kP+1,$ $\displaystyle m_{kP+1}$
$\displaystyle=\beta_{1}m_{0}+(1-\beta_{1})P$ (14) $\displaystyle S_{kP+1}$
$\displaystyle=\beta_{2}S_{kP}+(1-\beta_{2})(P-m_{kP})^{2}$ (15)
$\displaystyle index=kP+2,$ $\displaystyle m_{kP+2}$
$\displaystyle=\beta_{1}m_{kP+1}+(1-\beta_{1})\times(-1)$ (16)
$\displaystyle=\beta_{1}^{2}m_{kP}+(1-\beta_{1})\beta_{1}P+(1-\beta_{1})\times(-1)$
(17) $\displaystyle S_{kP+2}$
$\displaystyle=\beta_{2}S_{kP+1}+(1-\beta_{2})(-1-m_{kP+1})^{2}$ (18)
$\displaystyle=\beta_{2}^{2}S_{kP}+(1-\beta_{2})\beta_{2}(P-m_{kP})^{2}+(1-\beta_{2})\big{[}\beta_{1}(P-m_{kP})-(P+1)\big{]}^{2}$
(19) $\displaystyle index=kP+3,$ $\displaystyle m_{kP+3}$
$\displaystyle=\beta_{1}m_{kP+2}+(1-\beta_{1})\times(-1)$ (20)
$\displaystyle=\beta_{1}^{3}m_{kP}+(1-\beta_{1})\beta_{1}^{2}P+(1-\beta_{1})\beta_{1}\times(-1)+(1-\beta_{1})\times(-1)$
(21) $\displaystyle S_{kP+3}$
$\displaystyle=\beta_{2}S_{2}+(1-\beta_{2})(-1-m_{kP+2})^{2}$ (22)
$\displaystyle=\beta_{2}^{3}S_{kP}+(1-\beta_{2})\beta_{2}^{2}(P-m_{kP})^{2}$
$\displaystyle+(1-\beta_{2})\beta_{2}\big{[}\beta_{1}(P-m_{kP})-(P+1)\big{]}^{2}(\beta_{2}+\beta_{1}^{2})$
(23) $\displaystyle index=kP+4,$ $\displaystyle m_{kP+4}$
$\displaystyle=\beta_{1}^{4}m_{kP}+(1-\beta_{1})\beta_{1}^{3}P+(-1)(1-\beta_{1})(\beta_{1}^{2}+\beta_{1}+1)$
(24) $\displaystyle S_{kP+4}$
$\displaystyle=\beta_{2}S_{kP+3}+(1-\beta_{2})(-1-m_{kP+3})^{2}$ (25)
$\displaystyle=\beta_{2}^{4}S_{kP}+(1-\beta_{2})\beta_{2}^{3}(P-m_{kP})^{2}$
$\displaystyle+(1-\beta_{2})\beta_{2}\big{[}\beta_{1}(P-m_{kP})-(P+1)\big{]}^{2}(\beta_{2}^{2}+\beta_{2}\beta_{1}^{2}+\beta_{1}^{4})$
(26) $\displaystyle\cdot\cdot\cdot$ $\displaystyle index=kP+P,$ $\displaystyle
m_{kP+P}$
$\displaystyle=\beta_{1}^{P}m_{kP}+(1-\beta_{1})\beta_{1}^{P-1}P+(-1)(1-\beta_{1})\big{[}\beta_{1}^{P-2}+\beta_{1}^{P-3}+...+1\big{]}$
(27)
$\displaystyle=\beta_{1}^{P}m_{kP}+(1-\beta_{1})\beta_{1}^{P-1}P+(\beta_{1}-1)\frac{1-\beta_{1}^{P-1}}{1-\beta
1}$ (28) $\displaystyle S_{kP+P}$
$\displaystyle=\beta_{2}^{P}S_{kP}+(1-\beta_{2})\beta_{2}^{P-1}(P-m_{kP})^{2}$
$\displaystyle+(1-\beta_{2})\big{[}\beta_{1}(P-m_{kP})-(P+1)\big{]}^{2}\big{(}\beta_{2}^{P-2}+\beta_{2}^{P-3}\beta_{1}^{2}+...+\beta_{2}^{0}\beta_{1}^{2P-4}\big{)}$
(29)
$\displaystyle=\beta_{2}^{P}S_{kP}+(1-\beta_{2})\beta_{2}^{P-1}(P-m_{kP})^{2}$
$\displaystyle+(1-\beta_{2})\big{[}\beta_{1}(P-m_{kP})-(P+1)\big{]}^{2}\beta_{2}^{P-2}\frac{1-(\beta_{1}^{2}/\beta_{2})^{P-1}}{1-(\beta_{1}^{2}/\beta_{2})}$
(30)

As $k$ goes to $+\infty$, we have

$\displaystyle\lim_{k\to\infty}m_{kP+P}$
$\displaystyle=\lim_{k\to\infty}m_{kP}$ (31)
$\displaystyle\lim_{k\to\infty}S_{kP+P}$
$\displaystyle=\lim_{k\to\infty}S_{kP}$ (32)

From Eq. (28) we have:

$m_{kP+P}=\frac{(P+1)\beta_{1}^{P-1}-P\beta_{1}^{P}-1}{1-\beta_{1}^{P}}$ (33)

which matches our result in Eq. (A.1). Similarly, from Eq. (30), take limit of
$k\to\infty$, and combine with Eq. (32), we have

$\displaystyle\lim_{k\to\infty}S_{kP}=\frac{1-\beta_{2}}{1-\beta_{2}^{P}}\Bigg{[}\beta_{2}^{P-1}(P-\lim_{k\to\infty}m_{kP})^{2}+\big{[}\beta_{1}(P-\lim_{k\to\infty}m_{kP})-(P+1)\big{]}^{2}\beta_{2}^{P-2}\frac{1-(\beta_{1}^{2}/\beta_{2})^{P-1}}{1-(\beta_{1}^{2}/\beta_{2})}\Bigg{]}$
(34)

Since we have the exact expression for the limit, it’s trivial to check that

$S_{i}\geq S_{kP},\ \ \forall i\in[kP+1,kP+P],i\in\mathbb{N},k\to\infty$ (35)

Intuitively, suppose for some time period, we only observe a constant gradient
-1 without observing the outlier gradient ($P$); the longer the length of this
period, the smaller is the corresponding $S$ value, because $S$ records the
difference between observations. Note that since last time that outlier
gradient ($P$) is observed (at index $kP+1-P$), index $kP$ has the longest
distance from index $kP+1-P$ without observing the outlier gradient ($P$).
Therefore, $S_{kP}$ has the smallest value within a period of $P$ as $k$ goes
to infinity.

For step $kP+1$ to $kP+P$, the update on parameter is:

$\displaystyle index=kP+1,-\Delta_{x}^{kP+1}$
$\displaystyle=\frac{\alpha_{0}}{\sqrt{kP+1}}\frac{P}{\sqrt{S_{kP}}+\epsilon}$
(36) $\displaystyle index=kP+2,-\Delta_{x}^{kP+2}$
$\displaystyle=\frac{\alpha_{0}}{\sqrt{kP+2}}\frac{-1}{\sqrt{S_{kP+1}}+\epsilon}$
(37) $\displaystyle...$ $\displaystyle index=kP+P,-\Delta_{x}^{kP+P}$
$\displaystyle=\frac{\alpha_{0}}{\sqrt{kP+P}}\frac{-1}{\sqrt{S_{kP+P-1}}+\epsilon}$
(38)

So the negative total update within this period is:

$\displaystyle\frac{\alpha_{0}}{\sqrt{kP+1}}\frac{P}{\sqrt{S_{kP}}+\epsilon}$
$\displaystyle-\underbrace{\Bigg{[}\frac{\alpha_{0}}{\sqrt{kP+2}}\frac{1}{\sqrt{S_{kP+1}}+\epsilon}+...+\frac{\alpha_{0}}{\sqrt{kP+P}}\frac{1}{\sqrt{S_{kP+P}}+\epsilon}\Bigg{]}}_{P-1\textit{
terms}}$ (39)
$\displaystyle\geq\frac{\alpha_{0}}{\sqrt{kP+1}}\frac{P}{\sqrt{S_{kP}}+\epsilon}-\underbrace{\Bigg{[}\frac{\alpha_{0}}{\sqrt{kP+1}}\frac{1}{\sqrt{S_{kP}}+\epsilon}+...+\frac{\alpha_{0}}{\sqrt{kP+1}}\frac{1}{\sqrt{S_{kP}}+\epsilon}\Bigg{]}}_{P-1\textit{
terms}}$ (40) $\displaystyle\Big{(}\textit{Since }S_{kP}\textit{ is the
minimum within the period}\Big{)}$
$\displaystyle=\frac{\alpha_{0}}{\sqrt{S_{kP}}+\epsilon}\frac{1}{\sqrt{kP+1}}$
(41)

where $\alpha_{0}$ is the initial learning rate. Note that the above result
hold for every period of length $P$ as $k$ gets larger. Therefore, for some
$K$ such that for every $k>K$, $m_{kP}$ and $S_{kP}$ are close enough to their
limits, the total update after $K$ is:

$\sum_{k=K}^{\infty}\frac{\alpha_{0}}{\sqrt{S_{kP}}+\epsilon}\frac{1}{\sqrt{kP+1}}\approx\frac{\alpha_{0}}{\sqrt{\lim_{k\to\infty}S_{kP}}+\epsilon}\frac{1}{\sqrt{P}}\sum_{k=K}^{\infty}\frac{1}{\sqrt{k}}\textit{\
\ If $K$ is sufficiently large}$ (42)

where $\lim_{k\to\infty}S_{kP}$ is a constant determined by Eq. (34). Note
that this is the negative update; hence ACProp goes to the negative direction,
which is what we expected for this problem. Also considering that
$\sum_{k=K}^{\infty}\frac{1}{\sqrt{k}}\to\infty$, hence ACProp can go
arbitrarily far in the correct direction if the algorithm runs for infinitely
long, therefore the bias caused by first $K$ steps will vanish with running
time. Furthermore, since $x$ lies in the bounded region of $[-1,1]$, if the
updated result falls out of this region, it can always be clipped. Therefore,
for this problem, ACProp always converge to
$x=-1,\forall\beta_{1},\beta_{2}\in(0,1)$. When $\beta_{2}=1$, the denominator
won’t update, and ACProp reduces to SGD (with momentum), and it’s shown to
converge. ∎

######  Lemma A.4.

For any constant $\beta_{1},\beta_{2}\in[0,1)$ such that
$\beta_{1}<\sqrt{\beta_{2}}$, there is a stochastic convex optimization
problem for which Adam does not converge to the optimal solution. One example
of such stochastic problem is:

$f_{t}(x)=\begin{cases}Px&\ \ \textit{with probability
}\frac{1+\delta}{P+1}\\\ -x&\ \ \textit{with probability
}\frac{P-\delta}{P+1}\end{cases}\ \ x\in[-1,1]$ (43)

###### Proof.

See Thm.3 in [14]. ∎

######  Lemma A.5.

For the stochastic problem defined by Eq. (43), ACProp converge to the optimal
solution, $\forall\beta_{1},\beta_{2}\in(0,1)$.

###### Proof.

The update at step $t$ is:

$\displaystyle\Delta_{x}^{t}=-\frac{\alpha_{0}}{\sqrt{t}}\frac{g_{t}}{\sqrt{S_{t-1}}+\epsilon}$
(44)

Take expectation conditioned on observations up to step $t-1$, we have:

$\displaystyle\mathbb{E}\Delta_{x}^{t}$
$\displaystyle=-\frac{\alpha_{0}}{\sqrt{t}}\frac{\mathbb{E}_{t}g_{t}}{\sqrt{S_{t-1}}+\epsilon}$
(45)
$\displaystyle=-\frac{\alpha_{0}}{\sqrt{t}\Big{(}\sqrt{S_{t-1}}+\epsilon\Big{)}}\mathbb{E}_{t}g_{t}$
(46)
$\displaystyle=-\frac{\alpha_{0}}{\sqrt{t}\Big{(}\sqrt{S_{t-1}}+\epsilon\Big{)}}\Big{[}P\frac{1+\delta}{P+1}-\frac{P-\delta}{P+1}\Big{]}$
(47)
$\displaystyle=-\frac{\alpha_{0}\delta}{\sqrt{t}\Big{(}\sqrt{S_{t-1}}+\epsilon\Big{)}}$
(48)
$\displaystyle\leq-\frac{\alpha_{0}\delta}{\sqrt{t}\Big{(}P+1+\epsilon\Big{)}}$
(49)

where the last inequality is due to $S_{t}\leq(P+1)^{2}$, because $S_{t}$ is a
smoothed version of squared difference between gradients, and the maximum
difference in gradient is $P+1$. Therefore, for every step, ACProp is expected
to move in the negative direction, also considering that
$\sum_{t=1}^{\infty}\frac{1}{\sqrt{t}}\to\infty$, and whenever $x<-1$ we can
always clip it to -1, hence ACProp will drift $x$ to -1, which is the optimal
value. ∎

####  A.1.1 Numerical validations

We validate our analysis above in numerical experiments, and plot the curve of
$S_{t}$ and $g_{t}$ for multiple periods (as $k\to\infty$) in Fig. 10 and zoom
in to a single period in Fig. 11. Note that the largest gradient $P$
(normalized as 1) appears at step $kP+1$, and $S$ takes it minimal at step
$kP$ (e.g. $S_{kP}$ is the smallest number within a period). Note the update
for step $kP+1$ is $g_{kP+1}/\sqrt{S_{kP}}$, it’s the largest gradient divided
the smallest denominator, hence the net update within a period pushes $x$
towards the optimal point.

Figure 10: Behavior of $S_{t}$ and $g_{t}$ in ACProp of multiple periods for
problem (1). Note that as $k\to\infty$, the behavior of ACProp is periodic.
Figure 11: Behavior of $S_{t}$ and $g_{t}$ in ACProp of one period for problem
(1).

###  A.2 Convergence analysis for Problem 2 in the main paper

######  Lemma A.6 (Lemma 3.4 in the main paper).

For the problem defined by Eq. (50), consider the hyper-parameter tuple
$(\beta_{1},\beta_{2},P)$, there exists cases where ACProp converges but
AdaShift with $n=1$ diverges, but not vice versa.

$f_{t}(x)=\begin{cases}P/2\times x,\ \ \ \ \ t\%P==1\\\ -x,\ \ \ \ \ \ \ \ \ \
\ t\%P==P-2\\\ 0,\ \ \ \ \ \ \ \ \ \ \ \ \ \textit{otherwise}\\\
\end{cases}P>3,P\in\mathbb{N},x\in[0,1].$

(50)

###### Proof.

The proof is similar to Lemma. A.3,we derive the limit behavior of different
methods.

$\displaystyle index=kP,$ $\displaystyle m_{kP}$ $\displaystyle,v_{kP},s_{kP}$
$\displaystyle index=kP+1,$ $\displaystyle m_{kP+1}$
$\displaystyle=m_{kP}\beta_{1}+(1-\beta_{1})P/2$ (51) $\displaystyle v_{kP+1}$
$\displaystyle=v_{kP}\beta_{2}+(1-\beta_{2})P^{2}/4$ (52) $\displaystyle
s_{kP+1}$ $\displaystyle=s_{kP}\beta_{2}+(1-\beta_{2})(P/2-m_{kP})^{2}$ (53)
$\displaystyle...$ $\displaystyle index=kP+P-2,$ $\displaystyle m_{kP+P-2}$
$\displaystyle=m_{kP}\beta_{1}^{P-2}+(1-\beta_{1})\frac{P}{2}\beta_{1}^{P-3}+(1-\beta_{1})\times(-1)$
(54) $\displaystyle v_{kP+P-2}$
$\displaystyle=v_{kP}\beta_{2}^{P-2}+(1-\beta_{2})\frac{P^{2}}{4}\beta_{2}^{P-3}+(1-\beta_{2})$
(55) $\displaystyle s_{kP+P-2}$
$\displaystyle=s_{kP}\beta_{2}^{P-2}+(1-\beta_{2})\beta_{2}^{P-3}(\frac{P}{2}-m_{kP})^{2}+(1-\beta_{2})\beta_{2}^{P-4}m_{kP+1}^{2}+...$
$\displaystyle+(1-\beta_{2})\beta_{2}m_{kP+P-4}^{2}+(1-\beta_{2})(m_{kP+P-3}+1)^{2}$
(56) $\displaystyle index=kP+P-1,$ $\displaystyle m_{kP+P-1}$
$\displaystyle=m_{kP+P-1}\beta_{1}$ (57) $\displaystyle v_{kP+P-1}$
$\displaystyle=v_{kP+P-2}\beta_{2}$ (58) $\displaystyle s_{kP+P-1}$
$\displaystyle=s_{kP}\beta_{2}^{P-1}+(1-\beta_{2})\beta_{2}^{P-1}(\frac{P}{2}-m_{kP})^{2}+(1-\beta_{2})\beta_{2}^{P-3}m_{kP+1}^{2}+...$
$\displaystyle+(1-\beta_{2})\beta_{2}^{2}m_{kP+P-4}^{2}+(1-\beta_{2})\beta_{2}(m_{kP+P-3}+1)^{2}+(1-\beta_{2})m_{kP+P-2}^{2}$
(59) $\displaystyle index=kP+P,$ $\displaystyle m_{kP+P}$
$\displaystyle=m_{kP}\beta_{1}^{P}+(1-\beta_{1})\frac{P}{2}\beta_{1}^{P-1}+(1-\beta_{1})(-1)\beta_{1}^{2}$
(60) $\displaystyle v_{kP+P}$
$\displaystyle=v_{kP}\beta_{2}^{P}+(1-\beta_{2})\frac{P^{2}}{4}\beta_{2}^{P-1}+(1-\beta_{2})\beta_{2}^{2}$
(61) $\displaystyle s_{kP+p}$
$\displaystyle=s_{kP}\beta_{2}^{P}+(1-\beta_{2})\beta_{2}^{P-1}(\frac{P}{2}-m_{kP})^{2}+(1-\beta_{2})\beta_{2}^{P-2}m_{kP+1}^{2}+...$
$\displaystyle+(1-\beta_{2})\beta_{2}^{3}m_{kP+P-4}^{2}+(1-\beta_{2})\beta_{2}^{2}(m_{kP+P-3}+1)^{2}$
$\displaystyle+(1-\beta_{2})m_{kP+P-2}^{2}\beta_{2}+(1-\beta_{2})m_{kP+P-1}^{2}$
(62)

Next, we derive the exact expression using the fact that the problem is
periodic, hence
$\lim_{k\to\infty}m_{kP}=\lim_{k\to\infty}m_{kP+P},\lim_{k\to\infty}s_{kP}=\lim_{k\to\infty}s_{kP+P},\lim_{k\to\infty}v_{kP}=\lim_{k\to\infty}v_{kP+P}$,
hence we have:

$\displaystyle\lim_{k\to\infty}m_{kP}$
$\displaystyle=\lim_{k\to\infty}m_{kP}\beta_{1}^{P}+(1-\beta_{1})\frac{P}{2}\beta_{1}^{P-1}+(1-\beta_{1})(-1)\beta_{1}^{2}$
(63) $\displaystyle\lim_{k\to\infty}m_{kP}$
$\displaystyle=\frac{1-\beta_{1}}{1-\beta_{1}^{P}}\Big{[}\frac{P}{2}\beta_{1}^{P-1}-\beta_{1}^{2}\Big{]}$
(64) $\displaystyle\lim_{k\to\infty}m_{kP-1}$
$\displaystyle=\frac{1}{\beta_{1}}\lim_{k\to\infty}m_{kP}$ (65)
$\displaystyle\lim_{k\to\infty}m_{kP-2}$
$\displaystyle=\frac{1}{\beta_{1}}\Big{[}\lim_{k\to\infty}m_{kP-1}-(1-\beta_{1})0\Big{]}$
(66) $\displaystyle\lim_{k\to\infty}m_{kP-3}$
$\displaystyle=\frac{1}{\beta_{1}}\Big{[}\lim_{k\to\infty}m_{kP-2}-(1-\beta_{1})(-1)\Big{]}$
(67)

Similarly, we can get

$\displaystyle\lim_{k\to\infty}v_{kP}$
$\displaystyle=\frac{1-\beta_{2}}{1-\beta_{2}^{P}}\Big{[}\frac{P^{2}}{4}\beta_{2}^{P-1}+\beta_{2}^{2}\Big{]}$
(68) $\displaystyle\lim_{k\to\infty}v_{kP-1}$
$\displaystyle=\frac{1}{\beta_{2}}\lim_{k\to\infty}v_{kP}$ (69)
$\displaystyle\lim_{k\to\infty}v_{kP-2}$
$\displaystyle=\frac{1}{\beta_{2}}\lim_{k\to\infty}v_{kP-1}$ (70)
$\displaystyle\lim_{k\to\infty}v_{kP-3}$
$\displaystyle=\frac{1}{\beta_{2}}\Big{[}\lim_{k\to\infty}v_{kP-2}-(1-\beta_{2})\times
1^{2}\Big{]}$ (71)

For ACProp, we have the following results:

$\displaystyle\lim_{k\to\infty}s_{kP}$
$\displaystyle=\lim_{k\to\infty}\frac{1-\beta_{2}}{1-\beta_{2}^{P}}\Big{[}\beta_{2}^{P-4}(\frac{P}{2}-m_{kP})^{2}+\beta_{2}^{3}\frac{\beta_{2}^{P-5}-\beta_{1}^{2(P-4)}\beta_{2}}{1-\beta_{1}^{2}\beta_{2}}+\beta_{2}^{2}(m_{kP+P-3}+1)^{2}$
$\displaystyle+\beta_{2}m_{kP+P-2}^{2}+m_{kP+P-1}^{2}\Big{]}$ (72)
$\displaystyle\lim_{k\to\infty}s_{kP-1}$
$\displaystyle=\lim_{k\to\infty}\frac{1}{\beta_{2}}\Big{[}s_{kP}-(1-\beta_{2})m_{kP}^{2}\Big{]}$
(73) $\displaystyle\lim_{k\to\infty}s_{kP-2}$
$\displaystyle=\lim_{k\to\infty}\frac{1}{\beta_{2}}\Big{[}s_{kP-1}-(1-\beta_{2})m_{kP-1}^{2}\Big{]}$
(74) $\displaystyle\lim_{k\to\infty}s_{kP-3}$
$\displaystyle=\lim_{k\to\infty}\frac{1}{\beta_{2}}\Big{[}s_{kP-2}-(1-\beta_{2})(m_{kP-2}+1)^{2}\Big{]}$
(75)

Within each period, ACprop will perform a positive update $P/(2\sqrt{s^{+}})$
and a negative update $-1/\sqrt{s^{-}}$, where $s^{+}$ ($s^{-}$) is the value
of denominator before observing positive (negative) gradient. Similar
notations for $v^{+}$ and $v^{-}$ in AdaShift, where
$s^{+}=s_{kP},s^{-}=s_{kP-3},v^{+}=v_{kP},v^{-}=v_{kP-3}$. A net update in the
correct direction requires $\frac{P}{2\sqrt{s^{+}}}>\frac{1}{\sqrt{s^{-}}}$,
(or $s^{+}/s^{-}<P^{2}/4$). Since we have the exact expression for these terms
in the limit sense, it’s trivial to verify that $s^{+}/s^{-}\leq v^{+}/v^{-}$
(e.g. the value $\frac{s^{+}}{s^{-}}-\frac{v^{+}}{v^{-}}$ is negative as in
Fig. 13 and 13), hence ACProp is easier to satisfy the convergence condition.
∎

Figure 12: Value of $\frac{s^{+}}{s^{-}}-\frac{v^{+}}{v^{-}}$ when
$\beta_{1}=0.2$

Figure 13: Value of $\frac{s^{+}}{s^{-}}-\frac{v^{+}}{v^{-}}$ when
$\beta_{1}=0.9$

###  A.3 Numerical experiments

We conducted more experiments to validate previous claims. We plot the area of
convergence for different $\beta_{1}$ values for problem (1) in Fig. 14 to
Fig. 16, and validate the always-convergence property of ACProp with different
values of $\beta_{1}$. We also plot the area of convergence for problem (2)
defined by Eq. (50), results are shown in Fig. 17 to Fig. 19. Note that for
this problem the always-convergence does not hold, but ACProp has a much
larger area of convergence than AdaShift.

Figure 14: Numerical experiments on problem (1) with $\beta_{1}=0.5$ Figure
15: Numerical experiments on problem (1) with $\beta_{1}=0.5$ Figure 16:
Numerical experiments on problem (1) with $\beta_{1}=0.9$ Figure 17: Numerical
experiments on problem (43) with $\beta_{1}=0.85$ Figure 18: Numerical
experiments on problem (43) with $\beta_{1}=0.9$ Figure 19: Numerical
experiments on problem (43) with $\beta_{1}=0.95$

(a) Trajectories of AdaShift with various $n$ for problem (1). Note that
optimal is $x^{*}=-1$. Note that convergence of problem (1) requires a small
delay step $n$, but convergence of problem (2) requires a large $n$, hence
there’s no good criterion to select an optimal $n$.

(b) Trajectories of AdaShift with various $n$ for problem (43). Note that
optimal is $x^{*}=0.0$, and the trajectories are oscillating at a high
frequency hence appears to be spanning an area.

##  Appendix B Convergence Analysis for stochastic non-convex optimization

###  B.1 Problem definition and assumptions

The problem is defined as:

$\operatorname{min}_{x\in\mathbb{R}^{d}}f(x)=\mathbb{E}[F(x,\xi)]$ (77)

where $x$ typically represents parameters of the model, and $\xi$ represents
data which typically follows some distribution.

We mainly consider the stochastic non-convex case, with assumptions below.

  1. A.1

$f$ is continuously differentiable, $f$ is lower-bounde by $f^{*}$. $\nabla
f(f)$ is globalluy Lipschitz continuous with constant $L$:

$||\nabla f(x)-\nabla f(y)||\leq L||x-y||$ (78)

  2. A.2

For any iteration $t$, $g_{t}$ is an unbiased estimator of $\nabla f(x_{t})$
with variance bounded by $\sigma^{2}$. The norm of $g_{t}$ is upper-bounded by
$M_{g}$.

$\displaystyle(a)\ \ \ \ \mathbb{E}g_{t}=\nabla f(x_{t})$ (79)
$\displaystyle(b)\ \ \ \ \mathbb{E}\big{[}||g_{t}-\nabla
f(x_{t})||^{2}\big{]}\leq\sigma^{2}$ (80)

###  B.2 Convergence analysis of Async-optimizers in stochastic non-convex
optimization

######  Theorem B.1 (Thm.4.1 in the main paper).

Under assumptions A.1-2, assume $f$ is upper bounded by $M_{f}$, with learning
rate schedule as

$\alpha_{t}=\alpha_{0}t^{-\eta},\ \ \alpha_{0}\leq\frac{C_{l}}{LC_{u}^{2}},\ \
\eta\in[0.5,1)$ (81)

the sequence generated by

$x_{t+1}=x_{t}-\alpha_{t}A_{t}g_{t}$ (82)

satisfies

$\frac{1}{T}\sum_{t=1}^{T}\Big{|}\Big{|}\nabla
f(x_{t})\Big{|}\Big{|}^{2}\leq\frac{2}{C_{l}}\Big{[}(M_{f}-f^{*})\alpha_{0}T^{\eta-1}+\frac{LC_{u}^{2}\sigma^{2}\alpha_{0}}{2(1-\eta)}T^{-\eta}\Big{]}$
(83)

where $C_{l}$ and $C_{u}$ are scalars representing the lower and upper bound
for $A_{t}$, e.g. $C_{l}I\preceq A_{t}\preceq C_{u}I$, where $A\preceq B$
represents $B-A$ is semi-positive-definite.

###### Proof.

Let

$\delta_{t}=g_{t}-\nabla f(x_{t})$ (84)

then by A.2, $\mathbb{E}\delta_{t}=0$.

$\displaystyle f(x_{t+1})$ $\displaystyle\leq f(x_{t})+\Big{\langle}\nabla
f(x_{t}),x_{t+1}-x_{t}\Big{\rangle}+\frac{L}{2}\Big{|}\Big{|}x_{t+1}-x_{t}\Big{|}\Big{|}^{2}$
(85) $\displaystyle\Big{(}\textit{by L-smoothness of }f(x)\Big{)}$
$\displaystyle=f(x_{t})-\alpha_{t}\Big{\langle}\nabla
f(x_{t}),A_{t}g_{t}\Big{\rangle}+\frac{L}{2}\alpha_{t}^{2}\Big{|}\Big{|}A_{t}g_{t}\Big{|}\Big{|}^{2}$
(86) $\displaystyle=f(x_{t})-\alpha_{t}\Big{\langle}\nabla
f(x_{t}),A_{t}\big{(}\delta_{t}+\nabla
f(x_{t})\big{)}\Big{\rangle}+\frac{L}{2}\alpha_{t}^{2}\Big{|}\Big{|}A_{t}g_{t}\Big{|}\Big{|}^{2}$
(87) $\displaystyle\leq f(x_{t})-\alpha_{t}\Big{\langle}\nabla
f(x_{t}),A_{t}\nabla f(x_{t})\Big{\rangle}-\alpha_{t}\Big{\langle}\nabla
f(x_{t}),A_{t}\delta_{t}\Big{\rangle}+\frac{L}{2}\alpha_{t}^{2}C_{u}^{2}\Big{|}\Big{|}g_{t}\Big{|}\Big{|}^{2}$
(88)

Take expectation on both sides of Eq. (88), conditioned on
$\xi_{[t-1]}=\\{x_{1},x_{2},...x_{t-1}\\}$, also notice that $A_{t}$ is a
constant given $\xi_{[t-1]}$, we have

$\displaystyle\mathbb{E}\big{[}f(x_{t+1})|x_{1},...x_{t}\big{]}$
$\displaystyle\leq f(x_{t})-\alpha_{t}\Big{\langle}\nabla f(x_{t}),A_{t}\nabla
f(x_{t})\Big{\rangle}+\frac{L}{2}\alpha_{t}^{2}C_{u}^{2}\mathbb{E}\Big{|}\Big{|}g_{t}\Big{|}\Big{|}^{2}$
(89) $\displaystyle\Big{(}A_{t}\textit{ is independent of }g_{t}\textit{ given
}\\{x_{1},...x_{t-1}\\},\textit{ and }\mathbb{E}\delta_{t}=0\Big{)}$

In order to bound RHS of Eq. (89), we first bound
$\mathbb{E}\big{[}||g_{t}||^{2}\big{]}$.

$\displaystyle\mathbb{E}\Big{[}\Big{|}\Big{|}g_{t}\Big{|}\Big{|}^{2}\Big{|}x_{1},...x_{t}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\Big{|}\Big{|}\nabla
f(x_{t})+\delta_{t}\Big{|}\Big{|}^{2}\Big{|}x_{1},...x_{t}\Big{]}$ (90)
$\displaystyle=\mathbb{E}\Big{[}\Big{|}\Big{|}\nabla
f(x_{t})\Big{|}\Big{|}^{2}\Big{|}x_{1},...x_{t}\Big{]}+\mathbb{E}\Big{[}\Big{|}\Big{|}\nabla\delta_{t}\Big{|}\Big{|}^{2}\Big{|}x_{1},...x_{t}\Big{]}+2\mathbb{E}\Big{[}\Big{\langle}\delta_{t},\nabla
f(x_{t})\Big{\rangle}\Big{|}x_{1},...x_{t}\Big{]}$ (91)
$\displaystyle\leq\Big{|}\Big{|}\nabla f(x_{t})\Big{|}\Big{|}^{2}+\sigma^{2}$
(92) $\displaystyle\Big{(}\textit{By {A.2}, and }\nabla f(x_{t})\textit{ is a
constant given }x_{t}\Big{)}$

Plug Eq. (92) into Eq. (89), we have

$\displaystyle\mathbb{E}\Big{[}f(x_{t+1})\Big{|}x_{1},...x_{t}\Big{]}$
$\displaystyle\leq f(x_{t})-\alpha_{t}\Big{\langle}\nabla f(x_{t}),A_{t}\nabla
f(x_{t})\Big{\rangle}+\frac{L}{2}C_{u}^{2}\alpha_{t}^{2}\Big{[}\Big{|}\Big{|}\nabla
f(x_{t})\Big{|}\Big{|}^{2}+\sigma^{2}\Big{]}$ (93)
$\displaystyle=f(x_{t})-\Big{(}\alpha_{t}C_{l}-\frac{LC_{u}^{2}}{2}\alpha_{t}^{2}\Big{)}\Big{|}\Big{|}\nabla
f(x_{t})\Big{|}\Big{|}^{2}+\frac{LC_{u}^{2}\sigma^{2}}{2}\alpha_{t}^{2}$ (94)

By A.5 that $0<\alpha_{t}\leq\frac{C_{l}}{LC_{u}^{2}}$, we have

$\displaystyle\alpha_{t}C_{l}-\frac{LC_{u}^{2}\alpha_{t}^{2}}{2}=\alpha_{t}\Big{(}C_{l}-\frac{LC_{u}^{2}\alpha_{t}}{2}\Big{)}\geq\alpha_{t}\frac{C_{l}}{2}$
(95)

Combine Eq. (94) and Eq. (95), we have

$\displaystyle\frac{\alpha_{t}C_{l}}{2}\Big{|}\Big{|}\nabla
f(x_{t})\Big{|}\Big{|}^{2}$
$\displaystyle\leq\Big{(}\alpha_{t}C_{l}-\frac{LC_{u}^{2}\alpha_{t}^{2}}{2}\Big{)}\Big{|}\Big{|}\nabla
f(x_{t})||^{2}$ (96) $\displaystyle\leq
f(x_{t})-\mathbb{E}\Big{[}f(x_{t+1})\Big{|}x_{1},...x_{t}\Big{]}+\frac{LC_{u}^{2}\sigma^{2}}{2}\alpha_{t}^{2}$
(97)

Then we have

$\displaystyle\frac{C_{l}}{2}\Big{|}\Big{|}\nabla
f(x_{t})\Big{|}\Big{|}^{2}\leq\frac{1}{\alpha_{t}}f(x_{t})-\frac{1}{\alpha_{t}}\mathbb{E}\Big{[}f(x_{t+1})\Big{|}x_{1},...x_{t}\Big{]}+\frac{LC_{u}^{2}\sigma^{2}}{2}\alpha_{t}$
(98)

Perform telescope sum on Eq. (98), and recursively taking conditional
expectations on the history of $\\{x_{i}\\}_{i=1}^{T}$, we have

$\displaystyle\frac{C_{l}}{2}\sum_{t=1}^{T}||\nabla
f(x_{t})\Big{|}\Big{|}^{2}$
$\displaystyle\leq\sum_{t=1}^{T}\frac{1}{\alpha_{t}}\Big{(}\mathbb{E}f(x_{t})-\mathbb{E}f(x_{t+1})\Big{)}+\frac{LC_{u}^{2}\sigma^{2}}{2}\sum_{t=1}^{T}\alpha_{t}$
(99)
$\displaystyle=\frac{\mathbb{E}f(x_{1})}{\alpha_{1}}-\frac{\mathbb{E}f(x_{T+1})}{\alpha_{T}}+\sum_{t=2}^{T}\Big{(}\frac{1}{\alpha_{t}}-\frac{1}{\alpha_{t-1}}\Big{)}\mathbb{E}f(x_{t})+\frac{LC_{u}^{2}\sigma^{2}}{2}\sum_{t=1}^{T}\alpha_{t}$
(100)
$\displaystyle\leq\frac{M_{f}}{\alpha_{1}}-\frac{f^{*}}{\alpha_{T}}+M_{f}\sum_{t=1}^{T}\Big{(}\frac{1}{\alpha_{t}}-\frac{1}{\alpha_{t-1}}\Big{)}+\frac{LC_{u}^{2}\sigma^{2}}{2}\sum_{t=1}^{T}\alpha_{t}$
(101)
$\displaystyle\leq\frac{M_{f}-f^{*}}{\alpha_{T}}+\frac{LC_{u}^{2}\sigma^{2}}{2}\sum_{t=1}^{T}\alpha_{t}$
(102)
$\displaystyle\leq(M_{f}-f^{*})\alpha_{0}T^{\eta}+\frac{LC_{u}^{2}\sigma^{2}\alpha_{0}}{2}\Big{(}\zeta(\eta)+\frac{T^{1-\eta}}{1-\eta}+\frac{1}{2}T^{-\eta}\Big{)}$
(103) $\displaystyle\Big{(}\textit{By sum of generalized harmonic series},$
$\displaystyle\sum_{k=1}^{n}\frac{1}{k^{s}}\sim\zeta(s)+\frac{n^{1-s}}{1-s}+\frac{1}{2n^{s}}+O(n^{-s-1}),$
(104) $\displaystyle\zeta(s)\textit{ is Riemann zeta function}.\Big{)}$

Then we have

$\frac{1}{T}\sum_{t=1}^{T}\Big{|}\Big{|}\nabla
f(x_{t})\Big{|}\Big{|}^{2}\leq\frac{2}{C_{l}}\Big{[}(M_{f}-f^{*})\alpha_{0}T^{\eta-1}+\frac{LC_{u}^{2}\sigma^{2}\alpha_{0}}{2(1-\eta)}T^{-\eta}\Big{]}$
(105)

∎

####  B.2.1 Validation on numerical accuracy of sum of generalized harmonic
series

We performed experiments to test the accuracy of the analytical expression of
sum of harmonic series. We numerically calculate
$\sum_{i=1}^{N}\frac{1}{i^{\eta}}$ for $\eta$ varying from 0.5 to 0.999, and
for $N$ ranging from $10^{3}$ to $10^{7}$ in the log-grid. We calculate the
error of the analytical expression by Eq. (104), and plot the error in Fig.
21. Note that the $y$-axis has a unit of $10^{-7}$, while the sum is typically
on the order of $10^{3}$, this implies that expression Eq. (104) is very
accurate and the relative error is on the order of $10^{-10}$. Furthermore,
note that this expression is accurate even when $\eta=0.5$.

Figure 21: The error between numerical sum for
$\sum_{i=1}^{N}\frac{1}{i^{\eta}}$ and the analytical form.

###  B.3 Convergence analysis of Async-moment-optimizers in stochastic non-
convex optimization

######  Lemma B.2.

Let $m_{t}=\beta_{1}m_{t-1}+(1-\beta_{1})g_{t}$, let $A_{t}\in\mathbb{R}^{d}$,
then

$\Big{\langle}A_{t},g_{t}\Big{\rangle}=\frac{1}{1-\beta_{1}}\Big{(}\Big{\langle}A_{t},m_{t}\Big{\rangle}-\Big{\langle}A_{t-1},m_{t-1}\Big{\rangle}\Big{)}+\Big{\langle}A_{t-1},m_{t-1}\Big{\rangle}+\frac{\beta_{1}}{1-\beta_{1}}\Big{\langle}A_{t-1}-A_{t},m_{t-1}\Big{\rangle}$
(106)

######  Theorem B.3.

Under assumptions 1-4, $\beta_{1}<1,\beta_{2}<1$, also assume $A_{t+1}\leq
A_{t}$ element-wise which can be achieved by tracking maximum of $s_{t}$ as in
AMSGrad, $f$ is upper bounded by $M_{f}$, $||g_{t}||_{\infty}\leq M_{g}$, with
learning rate schedule as

$\alpha_{t}=\alpha_{0}t^{-\eta},\ \ \alpha_{0}\leq\frac{C_{l}}{LC_{u}^{2}},\ \
\eta\in(0.5,1]$ (107)

the sequence is generated by

$x_{t+1}=x_{t}-\alpha_{t}A_{t}m_{t}$ (108)

then we have

$\frac{1}{T}\sum_{t=1}^{T}\Big{|}\Big{|}\nabla
f(x_{t})\Big{|}\Big{|}^{2}\leq\frac{1}{\alpha_{0}C_{l}}T^{\eta-1}\Big{[}M_{f}-f^{*}+EM_{g}^{2}\Big{]}$
(109)

where

$E=\frac{\beta_{1}^{2}}{4L(1-\beta_{1})^{2}}+\frac{1}{1-\beta_{1}}\alpha_{0}M_{g}+\Big{(}\frac{\beta_{1}}{1-\beta_{1}}+\frac{1}{2}\Big{)}L\alpha_{0}^{2}C_{u}^{2}\frac{1}{1-2\eta}$
(110)

###### Proof.

Let $A_{t}=\alpha_{t}A_{t}\nabla f(x_{t})$ and let $A_{0}=A_{1}$, we have

$\displaystyle\sum_{t=1}^{T}\Big{\langle}A_{t},g_{t}\Big{\rangle}$
$\displaystyle=\frac{1}{1-\beta_{1}}\Big{\langle}A_{T},m_{T}\Big{\rangle}+\sum_{t=1}^{T}\Big{\langle}A_{t-1},m_{t-1}\Big{\rangle}+\frac{\beta_{1}}{1-\beta_{1}}\sum_{t=1}^{T}\Big{\langle}A_{t-1}-A_{t},m_{t-1}\Big{\rangle}$
(111)
$\displaystyle=\frac{\beta_{1}}{1-\beta_{1}}\Big{\langle}A_{T},m_{T}\Big{\rangle}+\sum_{t=1}^{T}\Big{\langle}A_{t},m_{t}\Big{\rangle}+\frac{\beta_{1}}{1-\beta_{1}}\sum_{t=0}^{T-1}\Big{\langle}A_{t}-A_{t+1},m_{t}\Big{\rangle}$
(112)

First we derive a lower bound for Eq. (112).

$\displaystyle\Big{\langle}A_{t},g_{t}\Big{\rangle}$
$\displaystyle=\Big{\langle}\alpha_{t}A_{t}\nabla f(x_{t}),g_{t}\Big{\rangle}$
(113) $\displaystyle=\Big{\langle}\alpha_{t}A_{t}\nabla
f(x_{t})-\alpha_{t-1}A_{t-1}\nabla
f(x_{t}),g_{t}\Big{\rangle}+\Big{\langle}\alpha_{t-1}A_{t-1}\nabla
f(x_{t}),g_{t}\Big{\rangle}$ (114)
$\displaystyle=\Big{\langle}\alpha_{t-1}A_{t-1}\nabla
f(x_{t}),g_{t}\Big{\rangle}-\Big{\langle}(\alpha_{t-1}A_{t-1}-\alpha_{t}A_{t})\nabla
f(x_{t}),g_{t}\Big{\rangle}$ (115)
$\displaystyle\geq\Big{\langle}\alpha_{t-1}A_{t-1}\nabla
f(x_{t}),g_{t}\Big{\rangle}-\Big{|}\Big{|}\nabla
f(x_{t})\Big{|}\Big{|}_{\infty}\Big{|}\Big{|}\alpha_{t-1}A_{t-1}-\alpha_{t}A_{t}\Big{|}\Big{|}_{1}\Big{|}\Big{|}g_{t}\Big{|}\Big{|}_{\infty}$
(116) $\displaystyle\Big{(}\textit{By H\"{o}lder's inequality}\Big{)}$
$\displaystyle\geq\Big{\langle}\alpha_{t-1}A_{t-1}\nabla
f(x_{t}),g_{t}\Big{\rangle}-M_{g}^{2}\Big{(}\Big{|}\Big{|}\alpha_{t-1}A_{t-1}\Big{|}\Big{|}_{1}-\Big{|}\Big{|}\alpha_{t}A_{t}\Big{|}\Big{|}_{1}\Big{)}$
(117) $\displaystyle\Big{(}\textit{Since
}\Big{|}\Big{|}g_{t}\Big{|}\Big{|}_{\infty}\leq
M_{g},\alpha_{t-1}\geq\alpha_{t}>0,A_{t-1}\geq A_{t}>0\textit{ element-
wise}\Big{)}$ (118)

Perform telescope sum, we have

$\sum_{t=1}^{T}\Big{\langle}A_{t},g_{t}\Big{\rangle}\geq\sum_{t=1}^{T}\Big{\langle}\alpha_{t-1}A_{t-1}\nabla
f(x_{t}),g_{t}\Big{\rangle}-M_{g}^{2}\Big{(}\Big{|}\Big{|}\alpha_{0}H_{0}\Big{|}\Big{|}_{1}-\Big{|}\Big{|}\alpha_{T}A_{t}\Big{|}\Big{|}_{1}\Big{)}$
(119)

Next, we derive an upper bound for
$\sum_{t=1}^{T}\Big{\langle}A_{t},g_{t}\Big{\rangle}$ by deriving an upper-
bound for the RHS of Eq. (112). We derive an upper bound for each part.

$\displaystyle\langle A_{t},m_{t}\Big{\rangle}$
$\displaystyle=\Big{\langle}\alpha_{t}A_{t}\nabla
f(x_{t}),m_{t}\Big{\rangle}=\Big{\langle}\nabla
f(x_{t}),\alpha_{t}A_{t}m_{t}\Big{\rangle}$ (120)
$\displaystyle=\Big{\langle}\nabla f(x_{t}),x_{t}-x_{t+1}\Big{\rangle}$ (121)
$\displaystyle\leq
f(x_{t})-f(x_{t+1})+\frac{L}{2}\Big{|}\Big{|}x_{t+1}-x_{t}\Big{|}\Big{|}^{2}\Big{(}\textit{By
L-smoothness of }f\Big{)}$ (122)

Perform telescope sum, we have

$\displaystyle\sum_{t=1}^{T}\Big{\langle}A_{t},m_{t}\Big{\rangle}\leq
f(x_{1})-f(x_{T+1})+\frac{L}{2}\sum_{t=1}^{T}\Big{|}\Big{|}\alpha_{t}A_{t}m_{t}\Big{|}\Big{|}^{2}$
(123) $\displaystyle\langle A_{t}-A_{t+1},m_{t}\Big{\rangle}$
$\displaystyle=\Big{\langle}\alpha_{t}A_{t}\nabla
f(x_{t})-\alpha_{t+1}A_{t+1}\nabla f(x_{t+1}),m_{t}\Big{\rangle}$ (124)
$\displaystyle=\Big{\langle}\alpha_{t}A_{t}\nabla
f(x_{t})-\alpha_{t}A_{t}\nabla f(x_{t+1}),m_{t}\rangle$
$\displaystyle+\Big{\langle}\alpha_{t}A_{t}\nabla
f(x_{t+1})-\alpha_{t+1}A_{t+1}\nabla f(x_{t+1}),m_{t}\rangle$ (125)
$\displaystyle=\Big{\langle}\nabla f(x_{t})-\nabla
f(x_{t+1}),\alpha_{t}A_{t}m_{t}\Big{\rangle}+\Big{\langle}(\alpha_{t}A_{t}-\alpha_{t+1}A_{t+1})\nabla
f(x_{t}),m_{t}\Big{\rangle}$ (126) $\displaystyle=\Big{\langle}\nabla
f(x_{t})-\nabla f(x_{t+1}),x_{t}-x_{t+1}\Big{\rangle}+\Big{\langle}\nabla
f(x_{t}),(\alpha_{t}A_{t}-\alpha_{t+1}A_{t+1})m_{t}\Big{\rangle}$ (127)
$\displaystyle\leq
L\Big{|}\Big{|}x_{t+1}-x_{t}\Big{|}\Big{|}^{2}+\Big{\langle}\nabla
f(x_{t}),(\alpha_{t}A_{t}-\alpha_{t+1}A_{t+1})m_{t}\Big{\rangle}$ (128)
$\displaystyle\Big{(}\textit{By smoothness of }f\Big{)}$ $\displaystyle\leq
L\Big{|}\Big{|}x_{t+1}-x_{t}\Big{|}\Big{|}^{2}+\Big{|}\Big{|}\nabla
f(x_{t})\Big{|}\Big{|}_{\infty}\Big{|}\Big{|}\alpha_{t}A_{t}-\alpha_{t+1}A_{t+1}\Big{|}\Big{|}_{1}\Big{|}\Big{|}m_{t}\Big{|}\Big{|}_{\infty}$
(129) $\displaystyle\Big{(}\textit{By H\"{o}lder's inequality}\Big{)}$
$\displaystyle\leq
L\Big{|}\Big{|}x_{t+1}-x_{t}\Big{|}\Big{|}^{2}+M_{g}^{2}\Big{(}\Big{|}\Big{|}\alpha_{t}A_{t}\Big{|}\Big{|}_{1}-\Big{|}\Big{|}\alpha_{t+1}A_{t+1}\Big{|}\Big{|}_{1}\Big{)}$
(130) $\displaystyle\Big{(}\textit{Since }\alpha_{t}\geq\alpha_{t+1}\geq
0,A_{t}\geq A_{t+1}\geq 0,\textit{element-wise}\Big{)}$ (131)

Perform telescope sum, we have

$\displaystyle\sum_{t=1}^{T-1}\Big{\langle}A_{t}-A_{t+1},m_{t}\rangle\leq
L\sum_{t=1}^{T-1}\Big{|}\Big{|}\alpha_{t}A_{t}m_{t}\Big{|}\Big{|}^{2}+M_{g}^{2}\Big{(}\Big{|}\Big{|}\alpha_{1}H_{1}\Big{|}\Big{|}_{1}-\Big{|}\Big{|}\alpha_{T}A_{t}\Big{|}\Big{|}_{1}\Big{)}$
(132)

We also have

$\displaystyle\Big{\langle}A_{T},m_{T}\Big{\rangle}$
$\displaystyle=\Big{\langle}\alpha_{T}A_{t}\nabla
f(x_{T}),m_{T}\Big{\rangle}=\Big{\langle}\nabla
f(x_{T}),\alpha_{T}A_{t}m_{T}\Big{\rangle}$ (133) $\displaystyle\leq
L\frac{1-\beta_{1}}{\beta_{1}}\Big{|}\Big{|}\alpha_{T}A_{t}m_{T}\Big{|}\Big{|}^{2}+\frac{\beta_{1}}{4L(1-\beta_{1})}\Big{|}\Big{|}\nabla
f(x_{T})\Big{|}\Big{|}^{2}$ (134) $\displaystyle\Big{(}\textit{By Young's
inequality}\Big{)}$
$\displaystyle=L\frac{1-\beta_{1}}{\beta_{1}}\Big{|}\Big{|}\alpha_{T}A_{t}m_{T}\Big{|}\Big{|}^{2}+\frac{\beta_{1}}{4L(1-\beta_{1})}M_{g}^{2}$
(135)

Combine Eq. (123), Eq. (132) and Eq. (135) into Eq. (112), we have

$\displaystyle\sum_{t=1}^{T}\Big{\langle}A_{t},g_{t}\Big{\rangle}$
$\displaystyle\leq\frac{\beta_{1}}{1-\beta_{1}}\Big{\langle}A_{T},m_{T}\Big{\rangle}+f(x_{1})-f(x_{T+1})+\frac{L}{2}\sum_{t=1}^{T}\Big{|}\Big{|}\alpha_{t}A_{t}m_{t}\Big{|}\Big{|}^{2}$
$\displaystyle+\frac{\beta_{1}}{1-\beta_{1}}L\sum_{t=1}^{T-1}\Big{|}\Big{|}\alpha_{t}A_{t}m_{t}\Big{|}\Big{|}^{2}+\frac{\beta_{1}}{1-\beta_{1}}M_{g}^{2}\Big{(}\Big{|}\Big{|}\alpha_{1}H_{1}\Big{|}\Big{|}_{1}-\Big{|}\Big{|}\alpha_{T}A_{t}\Big{|}\Big{|}_{1}\Big{)}$
(136) $\displaystyle\leq
f(x_{1})-f(x_{T+1})+\Big{(}\frac{\beta_{1}}{1-\beta_{1}}+\frac{1}{2}\Big{)}L\sum_{t=1}^{T}\Big{|}\Big{|}\alpha_{t}A_{t}m_{t}\Big{|}\Big{|}^{2}$
$\displaystyle+\Big{(}\frac{\beta_{1}^{2}}{4L(1-\beta_{1})^{2}}+\frac{\beta_{1}}{1-\beta_{1}}\Big{|}\Big{|}\alpha_{1}H_{1}\Big{|}\Big{|}_{1}\Big{)}M_{g}^{2}$
(137)

Combine Eq. (119) and Eq. (137), we have

$\displaystyle\sum_{t=1}^{T}\Big{\langle}\alpha_{t-1}A_{t-1}\nabla
f(x_{t}),g_{t}\Big{\rangle}$ $\displaystyle-
M_{g}^{2}\Big{(}\Big{|}\Big{|}\alpha_{0}H_{0}\Big{|}\Big{|}_{1}-\Big{|}\Big{|}\alpha_{T}A_{t}\Big{|}\Big{|}_{1}\Big{)}\leq\sum_{t=1}^{T}\Big{\langle}A_{t},g_{t}\Big{\rangle}$
$\displaystyle\leq
f(x_{1})-f(x_{T+1})+\Big{(}\frac{\beta_{1}}{1-\beta_{1}}+\frac{1}{2}\Big{)}L\sum_{t=1}^{T}\Big{|}\Big{|}\alpha_{t}A_{t}m_{t}\Big{|}\Big{|}^{2}$
$\displaystyle+\Big{(}\frac{\beta_{1}^{2}}{4L(1-\beta_{1})^{2}}+\frac{\beta_{1}}{1-\beta_{1}}\Big{|}\Big{|}\alpha_{1}H_{1}\Big{|}\Big{|}_{1}\Big{)}M_{g}^{2}$
(138)

Hence we have

$\displaystyle\sum_{t=1}^{T}\Big{\langle}\alpha_{t-1}A_{t-1}\nabla
f(x_{t}),g_{t}\Big{\rangle}\leq
f(x_{1})-f(x_{T+1})+\Big{(}\frac{\beta_{1}}{1-\beta_{1}}+\frac{1}{2}\Big{)}L\sum_{t=1}^{T}\Big{|}\Big{|}\alpha_{t}A_{t}m_{t}\Big{|}\Big{|}^{2}$
$\displaystyle+\Big{(}\frac{\beta_{1}^{2}}{4L(1-\beta_{1})^{2}}+\Big{|}\Big{|}\alpha_{0}H_{0}\Big{|}\Big{|}_{1}+\frac{\beta_{1}}{1-\beta_{1}}\Big{|}\Big{|}\alpha_{1}H_{1}\Big{|}\Big{|}_{1}\Big{)}M_{g}^{2}$
(139) $\displaystyle\leq
f(x_{1})-f^{*}+\Big{(}\frac{\beta_{1}}{1-\beta_{1}}+\frac{1}{2}\Big{)}L\alpha_{0}^{2}M_{g}^{2}C_{u}^{2}\sum_{t=1}^{T}t^{-2\eta}$
$\displaystyle+\Big{(}\frac{\beta_{1}^{2}}{4L(1-\beta_{1})^{2}}+\Big{|}\Big{|}\alpha_{0}H_{0}\Big{|}\Big{|}_{1}+\frac{\beta_{1}}{1-\beta_{1}}\Big{|}\Big{|}\alpha_{1}H_{1}\Big{|}\Big{|}_{1}\Big{)}M_{g}^{2}$
(140) $\displaystyle\leq f(x_{1})-f^{*}$
$\displaystyle+M_{g}^{2}\Big{[}\frac{\beta_{1}^{2}}{4L(1-\beta_{1})^{2}}+\Big{|}\Big{|}\alpha_{0}H_{0}\Big{|}\Big{|}_{1}+\frac{\beta_{1}}{1-\beta_{1}}\Big{|}\Big{|}\alpha_{1}H_{1}\Big{|}\Big{|}_{1}+\Big{(}\frac{\beta_{1}}{1-\beta_{1}}+\frac{1}{2}\Big{)}L\alpha_{0}^{2}C_{u}^{2}\frac{T^{1-2\eta}}{1-2\eta}\Big{]}$
(141) $\displaystyle\leq
f(x_{1})-f^{*}+M_{g}^{2}\underbrace{\Big{[}\frac{\beta_{1}^{2}}{4L(1-\beta_{1})^{2}}+\frac{1}{1-\beta_{1}}\alpha_{0}M_{g}+\Big{(}\frac{\beta_{1}}{1-\beta_{1}}+\frac{1}{2}\Big{)}L\alpha_{0}^{2}C_{u}^{2}\frac{1}{1-2\eta}\Big{]}}_{E}$
(142)

Take expectations on both sides, we have

$\displaystyle\sum_{t=1}^{T}\Big{\langle}\alpha_{t-1}A_{t-1}\nabla
f(x_{t}),\nabla
f(x_{t})\Big{\rangle}\leq\mathbb{E}f(x_{1})-f^{*}+EM_{g}^{2}\leq
M_{f}-f^{*}+EM_{g}^{2}$ (143)

Note that we have $\alpha_{t}$ decays monotonically with $t$, hence

$\displaystyle\sum_{t=1}^{T}\Big{\langle}\alpha_{t-1}A_{t-1}\nabla
f(x_{t}),\nabla f(x_{t})\Big{\rangle}$
$\displaystyle\geq\alpha_{0}T^{-\eta}\sum_{t=1}^{T}\Big{\langle}A_{t-1}\nabla
f(x_{t}),\nabla f(x_{t})\Big{\rangle}$ (144)
$\displaystyle\geq\alpha_{0}T^{1-\eta}C_{l}\Big{[}\frac{1}{T}\sum_{t=1}^{T}\Big{|}\Big{|}\nabla
f(x_{t})\Big{|}\Big{|}^{2}\Big{]}$ (145)

Combine Eq. (143) and Eq. (145), assume $f$ is upper bounded by $M_{f}$, we
have

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\Big{|}\Big{|}\nabla
f(x_{t})\Big{|}\Big{|}^{2}\leq\frac{1}{\alpha_{0}C_{l}}T^{\eta-1}\Big{[}M_{f}-f^{*}+EM_{g}^{2}\Big{]}$
(146)

∎

##  Appendix C Experiments

Figure 22: Behavior of ACProp for optimization of the function $f(x)=|x|$ with
$lr=0.00001$.

Figure 23: Behavior of ACProp for optimization of the function $f(x)=|x|$ with
$lr=0.01$.

###  C.1 Centering of second momentum does not suffer from numerical issues

Note that the centered second momentum $s_{t}$ does not suffer from numerical
issues in practice. The intuition that “$s_{t}$ is an estimate of variance in
gradient” is based on a strong assumption that the gradient follows a
stationary distribution, which indicates that the true gradient $\nabla
f_{t}(x)$ remains a constant function of $t$. In fact, $s_{t}$ tracks
$EMA((g_{t}-m_{t})^{2})$, and it includes two aspects: the change in true
gradient $||\nabla f_{t+1}(x)-\nabla f_{t}(x)||^{2}$, and the noise in
gradient observation $||g_{t}-\nabla f_{t}(x)||^{2}$. In practice, especially
in deep learning, the gradient suffers from large noise, hence $s_{t}$ does
not take extremely small values.

Next, we consider an ideal case that the observation $g_{t}$ is noiseless, and
conduct experiments to show that centering of second-momentum does not suffer
from numerical issues. Consider the function $f(x)=|x|$ with initial value
$x_{0}=100$, we plot the trajectories and stepsizes of various optimizers in
Fig. 22 and Fig. 23 with initial learning rate $lr=0.00001$ and $lr=0.01$
respectively. Note that ACProp and AdaBelief take a large step at the initial
phase, because a constant gradient is observed without noise. But note that
the gradient remains constant only within half of the plane; when it cross the
boundary $x=0$, the gradient is reversed, hence $||\nabla f_{t+1}(x)-\nabla
f_{t}(x)||^{2}\neq 0$, and $s_{t}$ becomes a non-zero value when it hits a
valley in the loss surface. Therefore, the stepsize of ACProp and AdaBelief
automatically decreases when they reach the local minimum. As shown in Fig. 22
and Fig. 23, ACProp and AdaBelief does not take any extremely large stepsizes
for both a very large (0.01) and very small (0.00001) learning rates, and they
automatically decrease stepsizes near the optimal. We do not observe any
numerical issues even for noise-free piecewise-linear functions. If the
function is not piecewise linear, or the gradient does not remain constant
within any connected set, then $||\nabla f_{t+1}(x)-\nabla f_{t}(x)||^{2}\neq
0$ almost everywhere, and the numerical issue will never happen.

The only possible case where centering second momentum causes numerical issue
has to satisfy two conditions simultaneously: (1) $||\nabla f_{t+1}(x)-\nabla
f_{t}(x)||^{2}=0,\forall t$ and (2) $g_{t}$ is a noise-free observation of
$\nabla f(x)$. This is a trivial case where the loss surface is linear, and
gradient is noise-free. This is case is almost never encountered in practice.
Furthermore, in this case, $s_{t}=0$ and ACProp reduces to SGD with stepsize
$1/\epsilon$. But note that the optimal is $-\infty$ and achieved at $\infty$
or $-\infty$, taking a large stepsize $1/\epsilon$ is still acceptable for
this trivial case.

Table 6: Hyper-parameters for ACProp in various experiments | lr | beta1 | beta2 | eps
---|---|---|---|---
ImageNet | 1e-3 | 0.9 | 0.999 | 1e-12
GAN | 2e-4 | 0.5 | 0.999 | 1e-16
Transformer | 5e-4 | 0.9 | 0.999 | 1e-16

###  C.2 Image classification with CNN

We performed extensive hyper-parameter tuning in order to better compare the
performance of different optimizers: for SGD we set the momentum as 0.9 which
is the default for many cases, and search the learning rate between 0.1 and
$10^{-5}$ in the log-grid; for other adaptive optimizers, including AdaBelief,
Adam, RAdam, AdamW and AdaShift, we search the learning rate between 0.01 and
$10^{-5}$ in the log-grid, and search $\epsilon$ between $10^{-5}$ and
$10^{-10}$ in the log-grid. We use a weight decay of 5e-2 for AdamW, and use
5e-4 for other optimizers. We conducted experiments based on the official code
for AdaBound and AdaBelief 111https://github.com/juntang-zhuang/Adabelief-
Optimizer.

(a) VGG11 on Cifar10

(b) ResNet34 on Cifar10

(c) DenseNet121 on Cifar10

(d) VGG11 on Cifar10

(e) ResNet34 on Cifar10

(f) DenseNet121 on Cifar10

Figure 24: Training (top row) and test (bottom row) accuracy of CNNs on
Cifar10 dataset.

Figure 25: The training and test accuracy curve of VGG11 on CIFAR10 with
different $\beta_{1}$ values.

Figure 26: The training and test accuracy curve of VGG11 on CIFAR10 with
different $\beta_{2}$ values.

Figure 27: Test accuracy of VGG-11 on CIFAR10 trained under various hyper-
parameter settings with different optimizers

We further test the robustness of ACProp to values of hyper-parameters
$\beta_{1}$ and $\beta_{2}$. Results are shown in Fig. 25 and Fig. 26
respectively. ACProp is robust to different values of $\beta_{1}$, and is more
sensitive to values of $\beta_{2}$.

Figure 28: BLEU score on validation set of a Transformer-base trained with
ACProp and Adam

###  C.3 Neural Machine Translation with Transformers

We conducted experiments on Neural Machine Translation (NMT) with transformer
models. Our experiments on the IWSLT14 DE-EN task is based on the 6-layer
transformer-base model in fairseq implementation
222https://github.com/pytorch/fairseq. For all methods, we use a learning rate
of 0.0002, and standard invser sqrt learning rate schedule with 4,000 steps of
warmup. For other tasks, our experiments are based on an open-source
implementation333https://github.com/DevSinghSachan/multilingual_nmt using a
1-layer Transformer model. We plot the BLEU score on validation set varying
with training epoch in Fig. 28, and ACProp consistently outperforms Adam
throughout the training.

###  C.4 Generative adversarial networks

The training of GANs easily suffers from mode collapse and numerical
instability [34], hence is a good test for the stability of optimizers. We
conducted experiments with Deep Convolutional GAN (DCGAN) [35], Spectral-Norm
GAN (SNGAN) [36], Self-Attention GAN (SAGAN) [37] and Relativistic-GAN (RLGAN)
[38]. We set $\beta_{1}=0.5$, and search for $\beta_{2}$ and $\epsilon$ with
the same schedule as previous section. Our experiments are based on an open-
source implementation 444https://github.com/POSTECH-CVLab/PyTorch-StudioGAN.

Figure 29: Generated figures by the SN-GAN trained with ACProp. Figure 30:
Generated figures by the SA-GAN trained with ACProp. Figure 31: Generated
figures by the DC-GAN trained with ACProp. Figure 32: Generated figures by the
RL-GAN trained with ACProp.