# Quantized Adam with Error Feedback

Congliang Chen  Li Shen  Haozhi Huang  Qi Wu  Wei Liu

# Supplementary Material for “ Quantized Adam with Error Feedback ”

Congliang Chen  Li Shen  Haozhi Huang  Qi Wu  Wei Liu

###### Abstract

In this paper, we present a distributed variant of adaptive stochastic
gradient method for training deep neural networks in the parameter-server
model. To reduce the communication cost among the workers and server, we
incorporate two types of quantization schemes, i.e., gradient quantization and
weight quantization, into the proposed distributed Adam. Besides, to reduce
the bias introduced by quantization operations, we propose an error-feedback
technique to compensate for the quantized gradient. Theoretically, in the
stochastic nonconvex setting, we show that the distributed adaptive gradient
method with gradient quantization and error-feedback converges to the first-
order stationary point, and that the distributed adaptive gradient method with
weight quantization and error-feedback converges to the point related to the
quantized level under both the single-worker and multi-worker modes. At last,
we apply the proposed distributed adaptive gradient methods to train deep
neural networks. Experimental results demonstrate the efficacy of our methods.

Machine Learning, ICML

##  1 Introduction

Recently, deep neural networks (LeCun et al., 2015; Goodfellow et al., 2016)
achieve high performances in many applications, such as computer vision
(Krizhevsky et al., 2012; He et al., 2016), natural language processing
(Devlin et al., 2018), speech recognition (Amodei et al., 2016), reinforcement
learning (Mnih et al., 2015; Silver et al., 2016), etc. However, a huge deep
neural network contains millions of parameters, so its training procedure
requires a large amount of training data (Deng et al., 2009; Wu et al., 2019),
which may not be stored in a single machine. In addition, due to some privacy
issues (Kairouz et al., 2019; Yang et al., 2019), all the training data cannot
be sent to a single machine but can be stored in different devices. Therefore,
how to accelerate the training process by using multiple machines over large-
scale data or distributed data has already been a hot topic in both industrial
and academic communities (Kraska et al., 2013; Li et al., 2014; Xing et al.,
2015; Liu et al., 2017).

An efficient approach to tackle this problem is to develop distributed
training algorithms for the huge neural networks (Dean et al., 2012). Most of
the distributed algorithms can be summarized into two categories: one is the
parameter-server (Smola & Narayanamurthy, 2010) model (or called centralized
model) shown in Fig. 1, and the other is the decentralized model (Lian et al.,
2017) shown in Fig. 2. For the centralized model in Fig. 1, there are one
parameter server and multiple workers. In an update iteration, all workers
report the update vectors to the parameter server. After gathering all the
update vectors, the parameter server will update the parameters and send the
parameters to all workers. While for the decentralized model in Fig. 2, there
are $n$ nodes working simultaneously. In each update iteration, each worker
computes its update vector respectively and communicates with its neighbors,
and then updates its own parameters. When we use a distributed training
algorithm such as distributed stochastic gradient descent (Li et al., 2014) in
either the centralized model or the decentralized model, plenty of update
vectors have to be communicated among different devices. Then, there comes a
communication issue for huge networks.

To accelerate the distributed training process of huge deep learning models,
we propose a new distributed adaptive stochastic gradient algorithm with
gradient quantization, weight quantization, and error-feedback in the
parameter server model as in Fig. 1. In what follows, we describe each
component used in the proposed algorithm in details:

Figure 1: Centralized distributed model

Quantization. Note that both gradient quantization and weight quantization are
introduced in the proposed algorithm to reduce the communication cost among
the workers and parameter server. Specifically, weight quantization is
performed on the parameter server and the quantized weights are then broadcast
to all the workers. Meanwhile, gradient quantization is performed on each
worker and then the quantized gradients are reported to the server. Thanks to
the double quantization schemes, the communication cost can be largely
reduced. In addition, for some resource-limited devices, storage is another
issue. Weight quantization can also be used to reduce the deep neural network
model size efficiently (Han et al., 2015; Zhou et al., 2016; Rastegari et al.,
2016). Especially, in federated learning, a distributed device may be smart
phones or Internet of things devices, which may encounter both the storage
issue and the communication issue. Thus, the weight quantization and gradient
quantization can jointly solve these two issues.

Adaptive learning rate. To ease the labor of tuning learning rate, we also
adopt the adaptive learning rate as (Kingma & Ba, 2014; Hinton et al., 2012;
Duchi et al., 2011; Zou et al., 2018; Reddi et al., 2019; Chen et al., 2018)
in the proposed algorithm. Here, the adaptive learning rate is calculated by a
similar definition to those in RMSProp (Hinton et al., 2012) and Adam (Kingma
& Ba, 2014), except that the noisy gradients are estimated with quantized
weights. Moreover, to guarantee the convergence of the proposed algorithm, we
set the exponential moving average parameter in estimating the adaptive
learning rate the same as that used in (Zou et al., 2019).

Error-feedback. In the proposed algorithm, an error-feedback technique is
leveraged to reduce the bias introduced by gradient quantization. The error-
feedback technique is also performed on each worker. Actually, the error-
feedback technique is motivated from (Karimireddy et al., ) by introducing an
additional term as the compensation term for the quantized gradient. However,
due to the introduced adaptive learning rate and momentum, the compensation
term is slightly different from that in (Karimireddy et al., ). To the best of
our knowledge, this is the first work that simultaneously employs the adaptive
learning rate and the error-feedback technique.

Figure 2: Decentralized distributed model

Besides, we establish the convergence rate of the proposed algorithm. In the
stochastic nonconvex setting, we show that the distributed adaptive stochastic
gradient method with gradient quantization and error-feedback converges to the
first-order stationary point, and that the distributed adaptive stochastic
gradient method with weight quantization and error-feedback converges to the
point related to the quantized level under both the single-worker and multi-
worker modes. At last, we apply the proposed distributed adaptive algorithm to
train deep learning models, such as LeNet (LeCun et al., 1998) on the MNIST
dataset (LeCun et al., 1998) and ResNet-101 (He et al., 2016) on the CIFAR100
dataset (Krizhevsky et al., 2009), respectively. The experimental results
demonstrate the effectiveness of weight quantization, gradient quantization
and the error-feedback technique working in concert with distributed adaptive
stochastic gradient method. Here, we summarize our contribution as threefold:

  * •

We propose a distributed variant of adaptive stochastic gradient method to
train deep learning models. The proposed algorithm exploits gradient
quantization, weight quantization, and the error-feedback technique to
accelerate the training process.

  * •

We establish the convergence rate of the proposed distributed adaptive
stochastic gradient methods with weight quantization, gradient quantization,
and error-feedback in the nonconvex stochastic setting under the single-worker
and multi-worker environments.

  * •

We apply the proposed algorithm to train deep learning models including LeNet
and ResNet-101. The experiments demonstrate the efficacy of the proposed
algorithm.

##  2 Related Works

In this section, we enumerate several works that are most related to this
work. We split the related works into two categories: distributed quantized
algorithms and adaptive learning rate.

###  2.1 Distributed Quantized Algorithms

Based on the decentralized model in Fig. 2, (Tang et al., 2019) and (Koloskova
et al., 2019) showed that distributed stochastic gradient descent with
quantized communication and error-feedback can converge to the stationary
point in the nonconvex setting. Based on the centralized model in Fig. 1,
(Zhou et al., 2016) and (Wu et al., 2018) showed that few bits or integer
networks can be trained empirically. Besides, (Hou et al., 2018) showed that
in the stochastic convex setting, with gradient quantization solely, the
algorithm that they proposed will converge to the optimal solution, and with
weight quantization the algorithm will converge to the point near the optimal
solution which is related to the weight quantization level. Among the above
mentioned algorithms, this work (Hou et al., 2018) is the most related to our
proposed algorithm. However, their proposed methods do not adopt the error-
feedback technique (Karimireddy et al., ), which may thus suffer from the
issue of inefficiency due to the bias arising from quantized gradients and
weights. In addition, the convergence analysis in (Hou et al., 2018) is merely
restricted to stochastic convex setting. While the convergence rate of our
proposed algorithm is established in the more difficult nonconvex setting.

On the other hand, error-feedback is a common technique in previous works
(Stich & Karimireddy, 2019; Karimireddy et al., ) for distributed quantized
methods. Each worker stores the error of the quantization and adds the error
term to the next communication before quantization. (Tang et al., 2019),
(Karimireddy et al., ), and many other works showed that the error-feedback
technique can help the convergence with compressed communications. In this
work, we first extend the error-feedback technique to adaptive stochastic
gradient methods (Adam) and then establish its convergence in the nonconvex
setting.

###  2.2 Adaptive Learning Rate

Adaptive learning rate, as a popular optimization technique for training deep
learning models, has attracted much attention. Lots of papers have studied the
convergences of adaptive stochastic gradient methods, such as AdaGrad (Duchi
et al., 2011; McMahan & Streeter, 2010), RMSprop (Hinton et al., 2012), Adam
(Kingma & Ba, 2014), and AMSGrad (Reddi et al., 2019). Besides the
counterexample of divergence when using the Adam algorithm in the convex case
in (Reddi et al., 2019), various works have proposed different conditions to
make Adam-type methods converge to first-order stationary points. For example,
(Ward et al., 2018; Li & Orabona, 2018; Zou et al., 2018) established global
convergence of AdaGrad in the nonconvex setting; (Reddi et al., 2019) checked
the difference between learning rates of two adjacent iterations and proposed
a new variant called AMSGrad; (Chen et al., 2018) established the convergence
of AMSGrad in the nonconvex setting; (Basu et al., 2018) showed that Adam
converges when a full-batch gradient was used; (Zhou et al., 2018) checked the
independence between gradient square and learning rate to ensure the
convergence for the counterexamples in (Reddi et al., 2019), and (Zou et al.,
2019) checked the parameter setting to give a sufficient condition to
guarantee the convergences of both Adam and RMSProp. In this paper, we propose
distributed variant of Adam method based (Zou et al., 2019) by incorporating
quantization schemes and an error-feedback technique. We also show that it
will converge to a saddle point with quantized update vector, and will be
close to a saddle point when we quantize the weights of a certain network.

##  3 Main Results

In this paper, we consider the following stochastic nonconvex optimization:

$\min_{x\in\mathbb{R}^{n}}\
f(x)=\mathbb{E}_{\xi\sim\mathbb{P}}\,\big{[}f(x,\xi)\big{]},$ (1)

where $\xi$ is a random variable with an unknown distribution $\mathbb{P}$,
and $f:\mathbb{R}^{n}\to(-\infty,+\infty)$ is a lower bounded nonconvex smooth
function, i.e., $f^{*}=\min_{x\in R^{d}}f(x)>-\infty$.

Due to the absence of a probability distribution $\mathbb{P}$ of the random
variable $\xi$, the access of exact gradient $\nabla{f}(x)$ may be impossible,
which leads to constructing an unbiased noisy estimation
$\nabla{f}(x_{t},\xi_{t})$ for full gradient $\nabla{f}(x_{t})$ at the point
$x_{t}$ with the given sampled sequence $\\{\xi_{t}\\}$. For convenience, we
denote $g_{t}$ as the abbreviation, i.e., $g_{t}:=\nabla{f}(x_{t},\xi_{t})$.
Moreover, throughout this paper, we assume that objective function $f$ is a
gradient Lipschitz function. These two requirements on gradient estimation are
summarized as the following assumption:

######  Assumption 1.

Gradient $\nabla{f}$ is an $L$-Lipschitz mapping, i.e., $\|\nabla f(x)-\nabla
f(y)\|\leq L\|x-y\|$. In addition, the noisy gradient estimation $g_{t}$ is
upper bounded and unbiased, i.e., $E[g_{t}]=\nabla f(x_{t})$ and
$\|g_{t}\|\leq G$.

In addition, we define a general quantization mapping
$Q(\cdot):\mathbb{R}^{n}\to\mathbb{R}^{n}$ at point $x\in\mathbb{R}^{n}$
following (Tang et al., 2019):

######  Definition 1.

Let $M\subset\mathbb{R}^{n}$ be a finite set. For $x\in R^{n}$, the
quantization operation $Q(\cdot)$ on $x$ is defined as
$Q(x)=\alpha(x)\beta(x)$, where $\alpha(x)\in\mathbb{R}$ and $\beta(x)\in M$.

######  Example 1.

Let $M=\\{-1,0,1\\}$. We can define a quantization function that satisfies
above definition:

$Q(x)_{i}=\left\\{\begin{array}[]{ll}\|x\|_{\infty},&\text{ if
}x_{i}>\|x\|_{\infty}/2\\\ 0,&\text{ if }\|x\|_{\infty}/2\leq
x_{i}\leq-\|x\|_{\infty}/2\\\ -\|x\|_{\infty},&\text{ if
}-\|x\|_{\infty}/2>x_{i}\end{array}\right.,$

where $\alpha(x)=\|x\|_{\infty}$, and

$\beta(x)_{i}=\left\\{\begin{array}[]{ll}1,&\text{ if
}x_{i}>\|x\|_{\infty}/2\\\ 0,&\text{ if }\|x\|_{\infty}/2\leq
x_{i}\leq-\|x\|_{\infty}/2\\\ -1,&\text{ if
}-\|x\|_{\infty}/2>x_{i}\end{array}\right..$

Based on the above defined quantization operator, we introduce the gradient
quantization $Q_{g}(\cdot)$ and weight quantization $Q_{x}(\cdot)$ operators,
respectively. Below, we first introduce the gradient quantization operator
$Q_{g}(\cdot)$ and require it satisfy the following assumption:

######  Assumption 2.

Let $Q_{g}(\cdot)$ be the gradient quantization operator defined as in
Definition 1. We assume that there exists a constant $\delta_{g}>0$ such that
the inequality holds $\|g-Q_{g}(g)\|\leq(1-\delta_{g})\|g\|$.

Besides, we define the weight quantization operator $Q_{x}(\cdot)$ and require
it satisfy the following assumption:

######  Assumption 3.

Let $Q_{x}(\cdot)$ be the weight quantization operator defined as in
Definition 1. First, we assume that the noisy gradient estimation at point
$x_{t}$ is an unbiased estimation of $\nabla f(Q_{x}(x_{t}))$, i.e.,
$E[g_{t}]=\nabla f(Q_{x}(x_{t}))$. In addition, we assume that there exists
$\delta_{x}>0$ such that the inequality
$\|x-Q_{x}(x)\|\leq(1-\delta_{x})\|x\|$ holds.

Assumption 1 is commonly used in analyzing adaptive stochastic type methods
(Chen et al., 2018; Reddi et al., 2019; Duchi et al., 2011). Especially, for
the gradient quantization and weight quantization, the Lipschitz continuity
conditions are used for bounding the error term introduced by quantization.
For the weight quantization, the unbiased estimation condition
$E[g_{t}]=\nabla f(Q_{x}(x_{t}))$ is used. This condition has already been
used in (Hou et al., 2018).

###  3.1 Single-Machine Analysis

In this subsection, we first present the quantized Generic Adam with weight
quantization, gradient quantization, and the error-feedback technique with a
single machine. Then, we establish its convergence rate with either gradient
quantization or weight quantization.

Algorithm 1 Quantized Generic Adam

Parameters: Choose $\\{\alpha_{t}\\},\\{\beta_{t}\\},\\{\theta_{t}\\},x_{1}\in
R^{d}$, quantization function $Q_{x}(\cdot),Q_{g}(\cdot)$. Set initial values
$m_{0}=0$ , $v_{0}=0$, and $e_{1}=0$.

1: for $t=1,2,\cdots,T$ do

2: Sample a stochastic gradient of $f(Q_{x}(x_{t}))$ as $g_{t}$;

3: $v_{t}=\theta_{t}v_{t-1}+(1-\theta_{t})g_{t}^{2}$;

4: $m_{t}=\beta_{t}m_{t-1}+(1-\beta_{t})g_{t}$;

5:
$x_{t+1}=x_{t}-Q_{g}\left(\alpha_{t}\frac{m_{t}}{\sqrt{v_{t}+\epsilon}}+e_{t}\right)$;

6:
$e_{t+1}=\alpha_{t}\frac{m_{t}}{\sqrt{v_{t}+\epsilon}}+e_{t}-Q_{g}\left(\alpha_{t}\frac{m_{t}}{\sqrt{v_{t}+\epsilon}}+e_{t}\right)$;

7: end for

Algorithm 1 unifies weight quantization, gradient quantization, and the error-
feedback technique into Adam, in which $Q_{x}(\cdot)$ denotes the weight
quantization operator, $Q_{g}(\cdot)$ denotes the gradient quantization
operator, and $e_{t}$ denotes the error-feedback term, respectively. In
addition, to establish the convergence rate of Algorithm 1 in the nonconvex
setting, we make the following assumptions on momentum parameter $\beta_{t}$,
exponential moving average parameter $\theta_{t}$, and base learning rate
$\alpha_{t}$.

######  Assumption 4.

Assume that momentum parameter $\beta_{t}$, exponential moving average
parameter $\theta_{t}$, and base learning rate $\alpha_{t}$ satisfy
$\beta_{t}\in[0,\beta]$ with $0<\beta<1$, $\theta_{t}=1-\frac{\theta}{t}$, and
$\alpha_{t}=\frac{\alpha}{\sqrt{t}}$, respectively. Furthermore, we denote
$\gamma=\beta/\theta^{\prime}$ and
$C_{1}=\prod_{j=1}^{N}(\frac{\theta_{j}}{\theta^{\prime}})$, in which
$N=\max\\{j|\theta_{j}<\theta^{\prime}\\}$ and $\theta^{\prime}$ satisfies
$\beta^{2}<\theta^{\prime}<1$.

The above assumption on the hyperparameters is used to establish the
convergence of adaptive stochastic gradient type method as (Zou et al., 2019).
In this paper, we use a simplified setting for momentum parameter $\beta_{t}$,
exponential moving average parameter $\theta_{t}$, and the base learning rate
$\alpha_{t}$ to simplify the convergence analysis, compared with the
sufficient condition in (Zou et al., 2019).

####  3.1.1 Gradient Quantization

Let $Q_{x}(x)=x$. The quantized generic Adam reduces to be distributed Adam
with gradient quantization and error-feedback. Below, we first give an
estimation for the error compensation term $e_{t}$, and then we present the
convergence rate of Algorithm 1 in a single-machine setting.

######  Lemma 1.

Let $\\{e_{t}\\}$ be the error term generated by Algorithm 1 and $\Delta_{t}$
be $\alpha_{t}m_{t}/\sqrt{v_{t}+\epsilon}$, where $\alpha_{t}$,$m_{t}$,$v_{t}$
are defined in Algorithm 1. Then the following inequality holds:

$\sum_{t=1}^{T}\|e_{t}\|\|\Delta_{t}\|\leq\frac{1-\delta_{g}}{\delta_{g}}\sum_{t=1}^{T}\|\Delta_{t}\|^{2}.$

Proof: By the definition of the error compensation term $e_{t}$, it holds that

$\begin{split}\|e_{t}\|&=\|\Delta_{t}+e_{t-1}-Q_{g}(\Delta_{t}+e_{t-1})\|\\\
&\leq(1-\delta_{g})\|\Delta_{t}+e_{t-1}\|\\\
&\leq(1-\delta_{g})\|\Delta_{t}\|+(1-\delta_{g})\|e_{t-1}\|\\\
&\leq\sum_{i=1}^{t}(1-\delta_{g})^{t-i+1}\|\Delta_{i}\|.\end{split}$

Therefore, we have

$\displaystyle\sum_{t=1}^{T}\|e_{t}\|\|\Delta_{t}\|$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{i=1}^{t}(1-\delta_{g})^{t-i+1}\|\Delta_{i}\|\|\Delta_{t}\|$
$\displaystyle\leq\frac{1-\delta_{g}}{\delta_{g}}\sum_{t=1}^{T}\|\Delta_{t}\|^{2}.$

Then, the targeted result is obtained. $\Box$

######  Theorem 1.

Let $\\{x_{t}\\}$ be the point generated by Algorithm 1 with $Q_{x}(x)=x$. In
addition, let $x_{\tau}^{T}$ represent random variable $x_{\tau}$ with $\tau$
taking from $\\{1,2,\ldots,T\\}$ with the same probability. If Assumptions 1,
2, 4 further hold, the convergence result of Algorithm 1 holds as follows:

$(E[\|\nabla
f((x_{\tau}^{T}))\|^{2}])\leq\frac{C+C^{\prime}\sum_{t=1}^{T}\frac{1}{t}}{\sqrt{T}},$
(2)

where $C=\frac{2\sqrt{G^{2}+\epsilon d}}{(1-\beta)\alpha}(f(x_{1})-f^{*})$,
$C^{\prime}=\frac{2\sqrt{G^{2}+\epsilon d}C_{3}}{(1-\beta)\alpha}$, and
$C_{3}=\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta\right)$.

Proof Sketch.

Let $\tilde{x}_{t}=x_{t}-e_{t}$ and
$\Delta_{t}=\alpha_{t}m_{t}/\sqrt{v_{t}+\epsilon}$. Then, the iterates can be
written as follows:

$\displaystyle\tilde{x}_{t+1}$ $\displaystyle=x_{t+1}-e_{t+1}$
$\displaystyle=x_{t}-Q_{g}(\Delta_{t}+e_{t})-e_{t+1}$
$\displaystyle=x_{t}-\Delta_{t}-e_{t}=\tilde{x}_{t}-\Delta_{t}.$

In addition, by taking Assumption 1, we have

$\displaystyle f(\tilde{x}_{t+1})$ $\displaystyle\leq
f(\tilde{x}_{t})+\langle\nabla
f(\tilde{x}_{t}),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}\|^{2}$
$\displaystyle=f(\tilde{x}_{t})+\langle\nabla
f(x_{t}),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}\|^{2}$
$\displaystyle\qquad+\langle\nabla(f(\tilde{x}_{t})-\nabla
f(x_{t}),\Delta_{t}\rangle.$

Term $\langle\nabla f(x_{t}),\Delta_{t}\rangle+\frac{L}{2}\|\Delta\|^{2}$ can
use a similar proof to that of Adam (Zou et al., 2019) without quantization.
Moreover, note that $\langle\nabla(f(\tilde{x}_{t})-\nabla
f(x_{t}),\Delta_{t}\rangle\leq L\|e_{t}\|\|\Delta_{t}\|$. Besides, with Lemma
1, $\sum_{t=1}^{T}\|e_{t}\|\|\Delta_{t}\|$ is upper bounded by
$\frac{1-\delta_{g}}{\delta_{g}}\sum_{t=1}^{T}\|\Delta_{t}\|^{2}$. Combining
all the results above, the theorem can be proven. $\Box$

From this result, it is shown that with gradient quantization and error-
feedback the proposed algorithm can converge to the first-order stationary
point in the nonconvex setting. In addition, the convergence rate is of the
same order as original Adam in the nonconvex setting (Zou et al., 2019).
Besides, paying attention to constant $C_{3}$, it can be seen that the
constant factor in the convegrence rate is related to the quantized level.

####  3.1.2 Weight Quantization

In this subsection, we set $Q_{g}(g)=g$ in Algorithm 1. The proposed quantized
generic Adam reduces to distributed Adam with the weight quantization and
error-feedback techniques. In this situation, to establish convergence rate of
Algorithm 1, we further assume that all the iterates are bounded, i.e.,
$\|x_{t}\|\leq D$.

######  Theorem 2.

Let $\\{x_{t}\\}$ be the point generated by Algorithm 1 with $Q_{g}(g)=g$. In
addition, let $x_{\tau}^{T}$ represent random variable $x_{\tau}$ with $\tau$
taking from $\\{1,2,\ldots,T\\}$ with the same probability. If Assumptions 1,
3, 4 further hold, the convergence result of Algorithm 1 holds as follows:

$E\big{[}\|\nabla
f(Q_{x}(x_{\tau}^{T}))\|^{2}\big{]}\leq\frac{C_{5}+C_{6}\sum_{t=1}^{T}\frac{1}{t}}{\sqrt{T}}+C_{7},$

where $C_{5}=\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha}(f(x_{1})-f^{*})$, $C_{6}=\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{LG^{2}\alpha^{2}}{\epsilon}+C_{2}\theta\right)$,
$C_{7}=\frac{8(1-\delta_{x})\sqrt{G^{2}+\epsilon
d}LDG}{(1-\beta)\sqrt{\epsilon C_{1}}(1-\sqrt{\gamma})}$, and $C_{2}$ is
defined in Theorem 1.

Proof Sketch.

Let $\Delta_{t}=\alpha_{t}m_{t}/\sqrt{v_{t}+\epsilon}$. By using Assumption 1,
we have

$\displaystyle f(x_{t+1})$ $\displaystyle\leq f(x_{t})+\langle\nabla
f(x_{t}),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}\|^{2}$
$\displaystyle=f(x_{t})+\langle\nabla
f(Q_{x}(x_{t})),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}\|^{2}$
$\displaystyle\qquad+\langle\nabla f(x_{t})-\nabla
f(Q_{x}(x_{t})),\Delta_{t}\rangle.$

Still, term $\langle\nabla
f(Q_{x}(x_{t})),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}\|^{2}$ can use a
similar proof to Adam without quantization (Zou et al., 2019), because in this
case $g_{t}$ is an unbiased estimator of $\nabla f(Q_{x}(x_{t}))$. Moreover,
by applying the Cauchy-Schwartz inequality to the term $\langle\nabla
f(x_{t})-\nabla f(Q_{x}(x_{t})),\Delta_{t}\rangle$, we obtain

$\displaystyle\quad\langle\nabla f(x_{t})-\nabla
f(Q_{x}(x_{t})),\Delta_{t}\rangle$ $\displaystyle\leq
L(1-\delta_{x})D\|\Delta_{t}\|.$

Besides, $\sum_{t=1}^{T}\|\Delta_{t}\|\leq\zeta\sqrt{T}$ holds, in which
$\zeta$ is a constant related to $\alpha,\ G$ and $\epsilon$. By combining
those results, the above theorem can be proven. $\Box$

From this result, it can be shown that with weight quantization the algorithm
will converge to the point related to the quantized level, and when we don’t
use quantization the algorithm will converge to the first-order stationary
point by setting $\delta_{x}=0$ directly. In addition, weight quantization on
stochastic gradient type methods has already been considered in (Khaled &
Richtárik, 2019), in which the authors also showed that weight quantized SGD
convergences to a point near the global optimum. However, the analysis of
weight quantized SGD in (Khaled & Richtárik, 2019) is merely restricted to the
strongly convex setting.

###  3.2 Multi-Worker Analysis

In this subsection, we extend Algorithm 1 to the multi-worker setting with the
parameter server model. Below, we use Algorithm 2 to represent the iteration
schemes of the distributed quantized generic Adam algorithm in the parameter
server, and Algorithm 3 to represent the iteration schemes in all workers,
respectively. Here, we assume that all workers work independently.

Algorithm 2 The Parameter Server

Parameters: Choose $x_{1}\in R^{d}$, and quantization function $Q_{x}(\cdot)$.

1: for $t=1,2,\cdots,T$ do

2: Broadcasting $Q_{x}(x_{t})$;

3: Gathering all updates from workers
$\hat{\delta}_{t}=\frac{1}{N}\sum_{i=1}^{N}\delta_{t}^{(i)}$;

4: $x_{t+1}=x_{t}+\hat{\delta}_{t}$;

5: end for

Output: $Q_{x}(x_{t})$.

Algorithm 3 The $i$-th Worker

Parameters: Choose $\\{\alpha_{t}\\},\\{\beta\\},\\{\theta_{t}\\}$, and
quantization function $Q_{g}()$. Set initial values $m^{(i)}_{0}=0$ ,
$v^{(i)}_{0}=0$, $e^{(i)}_{1}=0$, and $hat{x}_{0}=0$.

1: for $t=1,2,\cdots,T$ do

2: Receiving $\hat{x}_{t}$ from the server;

3: Sample a stochastic gradient of $f(\hat{x}_{t})$ as $g^{(i)}_{t}$;

4:
$v^{(i)}_{t}=\theta_{t}v^{(i)}_{t-1}+(1-\theta_{t})\big{[}g^{(i)}_{t}\big{]}^{2}$;

5: $m^{(i)}_{t}=\beta m^{(i)}_{t-1}+(1-\beta)g^{(i)}_{t}$;

6: Sending
$\delta_{t}^{(i)}=Q_{g}\left(\alpha_{t}\frac{m^{(i)}_{t}}{\sqrt{v^{(i)}_{t}+\epsilon}}+e^{(i)}_{t}\right)$;

7:
$e^{(i)}_{t+1}=\alpha_{t}\frac{m^{(i)}_{t}}{\sqrt{v^{(i)}_{t}+\epsilon}}+e^{(i)}_{t}-\delta^{(i)}_{t}$;

8: end for

Note that communicated information $\hat{x}_{t}$ and $\delta_{t}^{i}$ between
the server and works is all quantized in order to improve the communication
efficiency. The weight quantization procedure is performed on the server, and
the gradient quantization and error-feedback procedures are performed on the
workers. Below, we establish the convergence rate of distributed Adam with
weight quantization, gradient quantization, and error-feedback in Algorithms
2-3 in the parameter server model.

|  |
---|---|---
|  |
Figure 3: Results for Gradient Quantization: FP represents no quantization, and EF represents error-feedback. |  |
---|---|---
|  |
Figure 4: Results for Gradient Quantization and Weight Quantization: FP
represents no quantization, and the line without $k_{g}$ value means using
full precision for gradient communication.

######  Theorem 3.

Let $\\{x_{t}\\}$ be the point generated by Algorithms 2-3. In addition, let
$\hat{x}^{T}_{\tau}$ be the random variable $\hat{x}_{\tau}$ with $\tau$
taking from $\\{1,2,\ldots,T\\}$ with the same probability. If Assumptions 1-4
further hold and the iterates $\|x_{t}\|\leq D$ are upper bounded, the
convergence result of Algorithms 2-3 holds as follows:

$E\big{[}\|\nabla
f(\hat{x}_{\tau}^{T})\|^{2}\big{]}\leq\frac{C_{8}+C_{9}\sum_{t=1}^{T}\frac{1}{t}}{\sqrt{T}}+C_{10},$

where $C_{8}=\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha}(f(x_{1})-f^{*})$, $C_{9}=\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta\right)$,
$C_{10}=\frac{4\sqrt{G^{2}+\epsilon
d}(1-\delta_{x})LDG}{\sqrt{C_{1}}(1-\sqrt{\gamma})\sqrt{\epsilon}(1-\beta)}$,
and $C_{2}$ is defined in Theorem 1.

Proof Sketch. Let $\tilde{x}_{t}=x_{t}-\frac{1}{N}\sum_{i=1}^{N}e_{t}^{(i)}$,
$\Delta_{t}^{(i)}=\alpha_{t}m_{t}^{(i)}/\sqrt{v_{t}^{(I)}+\epsilon}$, and
$\Delta_{t}=\frac{1}{N}\sum_{i=1}^{N}\Delta_{t}^{(i)}$. Then
$\tilde{x}_{t+1}=\tilde{x}_{t}-\Delta_{t}$.

By using Assumption 1, we have

$\displaystyle f(\tilde{x}_{t+1})$
$\displaystyle\leq(f(\tilde{x}_{t})+\langle\nabla
f(\tilde{x}_{t}),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}\|^{2})$
$\displaystyle=f(\tilde{x}_{t})+\langle\nabla
f(\hat{x}_{t}),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}\|^{2}$
$\displaystyle\qquad+\langle\nabla f(x_{t})-\nabla
f(\hat{x}_{t})),\Delta_{t}\rangle$ $\displaystyle\qquad+\langle\nabla
f(\tilde{x}_{t})-\nabla f(x_{t}),\Delta_{t}\rangle$ $\displaystyle\leq
f(\tilde{x}_{t})+\langle\nabla
f(\hat{x}_{t}),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}\|^{2}$
$\displaystyle\qquad+\langle\nabla f(x_{t})-\nabla
f(\hat{x}_{t})),\Delta_{t}\rangle$
$\displaystyle\qquad+L\sum_{i=1}^{N}\sum_{j=1}^{N}\|e_{t}^{(i)}\|\|\Delta_{t}^{(j)}\|.$

With Lemma 1, the estimation of
$L\sum_{i=1}^{N}\sum_{j=1}^{N}\|e_{t}^{(i)}\|\|\Delta_{t}^{(j)}\|$ will
involve the estimation of $E(\Delta_{t_{1}}^{(i)}\Delta_{t_{2}}^{(j)})$.
Without loss of generality, let $t_{1}\leq t_{2}$. When $t_{1}<t_{2}$, it
holds that:

$\displaystyle E(\Delta_{t_{1}}^{(i)}\Delta_{t_{2}}^{(j)})$
$\displaystyle=E(E(\Delta_{t_{1}}^{(i)}\Delta_{t_{2}}^{(j)}|x_{t_{2}}))$
$\displaystyle=E(E(\Delta_{t_{1}}^{(i)}|x_{t_{2}})E(\Delta_{t_{2}}^{(j)}|x_{t_{2}}))$
$\displaystyle=E(E(\Delta_{t_{1}}^{(i)}|x_{t_{2}})E(\Delta_{t_{2}}^{(i)}|x_{t_{2}}))$
$\displaystyle=E(E(\Delta_{t_{1}}^{(i)}\Delta_{t_{2}}^{(i)})|x_{t_{2}})$
$\displaystyle=E(\Delta_{t_{1}}^{(i)}\Delta_{t_{2}}^{(i)}),$

where the equalities hold since worker i and worker j work in the same setting
and independently.

On the other hand, when $t_{1}=t_{2},i\neq j$, since workers $i$ and $j$ work
independently, it holds that

$\displaystyle E(\Delta_{t_{1}}^{(i)}\Delta_{t_{2}}^{(j)})$
$\displaystyle=E(\Delta_{t_{1}}^{(i)})E(\Delta_{t_{2}}^{(j)})$
$\displaystyle=E(\Delta_{t_{1}}^{(i)})^{2}\leq E([\Delta_{t_{1}}^{(i)}]^{2}).$

So when $t_{1}=t_{2}$, the term $E(\Delta_{t_{1}}^{(i)}\Delta_{t_{2}}^{(j)})$
can be bounded by $E([\Delta_{t_{1}}^{(i)}]^{2})$. Then, we obtain
$E(\Delta_{t_{1}}^{(i)}\Delta_{t_{2}}^{(j)})\leq
E(\Delta_{t_{1}}^{(i)}\Delta_{t_{2}}^{(i)})$. With this inequality, we can
reduce all terms involving different machines to a single machine, and the
rest of the proof will be the same as Theorems 1 and 2. $\Box$

In Algorithms 2-3, both the gradient quantization and weight quantization
schemes are applied. We also show that the proposed algorithms converge to a
point near the saddle point of problem (1) up to a constant. While the
constant is effected by both the gradient quantized level $\delta_{g}$ and the
weight quantized level $\delta_{x}$. In addition, the limit point of the
generate iterates will be effected only by the weight quantized level. Once
gradient quantization and weight quantization reduce to identity mappings,
Algorithms 2-3 reduce to the distributed Adam in the parameter server model
and Theorem 3 provides its convergence rate.

##  4 Experiments

In this section, we apply the proposed algorithm to train deep neural networks
including LeNet (LeCun et al., 1998) and ResNet-101 (He et al., 2016) on MNIST
(LeCun et al., 1998) and CIFAR100 (Krizhevsky et al., 2009) datasets,
respectively. Below, we first describe the implementation details and then
show the experimental results.

###  4.1 Implementation Details

Let
$M_{k}=\left\\{-1,-\frac{2^{k-1}-2}{2^{k-1}-1},\cdots,-\frac{1}{2^{k-1}-1},0,\frac{1}{2^{k-1}-1},\cdots,\right.$
$\left.\frac{2^{k-1}-2}{2^{k-1}-1},1\right\\}$ in Definition 1 and
$Q_{k}(x)=\arg\min_{y\in M_{k}^{d}}\|y-x\|_{2}$, in which $Q_{k}(x)$ can be
represented by a $k$ bits quantization mapping. Then according to Definition
1, we set the gradient quantization
$Q_{g}(g)=\|g\|_{\infty}Q_{k_{g}}(g/\|g\|_{\infty})$ and
$Q_{x}(x)=\|x\|_{\infty}Q_{k_{x}}(x/\|x\|_{\infty})$, respectively. Moreover,
it is not hard to verify that Assumption 2 and Assumption 3 hold, as $x$ and
$g$ are bounded.

We evaluate the effectiveness of the proposed algorithm via training
ResNet-101 (He et al., 2016) on the CIFAR100 dataset. The CIFAR100 dataset
contains 100 classes. In each class, there are $600$ color images with the
size of $32\times 32$ among which 500 images serve as training images and the
rest are testing images. We train ResNet-101 with the batch size 128 and set
the total number of training epochs as $200$. In addition, we add $\ell_{2}$
regularization with a scalar $5e-4$ as the weight decay term. Input images are
all down-scaled to 1/8 of their original sizes after 18 convolutional layers,
and then fed into a fully-connected layer for the 100-class classifications.
The output channel numbers of 1-11 conv layers, 12-23 conv layers, 24-92 conv
layers, and 93-101 conv layers are 64, 128, 256, and 512, respectively. Also,
we train LeNet (LeCun et al., 1998) on the MNIST dataset. MNIST contains 10
classes of $28\times 28$ images of digits, including $60,000$ training images
and $10,000$ testing images. We train LeNet with the batch size of 128 for
$10,000$ iterations without $l_{2}$ regularization. The LeNet contains 5
layers with 2 convolutional layers with channel numbers 6 and 16,
respectively, and 3 fully connected layers with width 120, 84, 10,
respectively.

Besides, in all experiments we choose $\beta$ as 0.99, $\theta$ as 0.999, and
$\epsilon$ as $1e-5$. Since it is natural to choose the exponential decay
strategy on learning rate, we choose to reduce $\alpha$ by half every 50
epochs instead of using $\frac{\alpha}{\sqrt{t}}$ as (Reddi et al., 2019). We
choose the starting learning rate as 0.001. The value is chosen based on grid
search on the set $\\{0.01,0.001,0.005,0.0005,0.0001\\}$ based on the accuracy
of full precision setting. For simplicity, in the experiment we use $1$
parameter server and 2 workers, with each worker sampling the data from the
same dataset independently. Moreover, the communication part is implemented
based on NVIDIA NCCL for gathering and broadcasting.

###  4.2 Results Illustration

Fig. 3 shows the results when only gradient quantization is used in Algorithm
3. The upper row in Fig. 3 shows the results of training ResNet-101 on the
CIFAR100 dataset, and the bottom row shows the results of training LeNet on
the MNIST dataset. For results on training ResNet-101, the left figure shows
the training loss curve during the whole training process. As it is shown in
the left figure, without the error-feedback technique, $k_{g}=2$ and $k_{g}=3$
perform worse than those with the error-feedback technique. And the algorithm
with the error-feedback technique performs similarly to the full precision
version. When we test the models on the testing data, the middle figure shows
that the error-feedback technique helps the model obtain better performance on
test dataset. The right figure shows when zooming in the accuracy curve, with
a higher quantization level the model performs better. This is because a
higher quantization level has a smaller constant. With the same number of
iterations, the model can get closer to the stationary point. And for the
results on training LeNet, except the setting of $k_{g}=2$ without error-
feedback, all the settings have similar performance. This may be because the
classification task on MNIST is too simple.

Fig. 4 shows the results of Algorithms 2-3 with both weight quantization and
gradient quantization schemes. Also, the upper row in Fig. 4 shows the results
of training ResNet-101 on the CIFAR100 dataset, and the bottom row shows the
results of training LeNet on the MNIST dataset. In the upper row, the left
figure is the result of the training loss during the training process. It
shows that even if we quantize parameters in the network with 7 bits, it can
still perform similarly to the full precision version. And when we add
gradient quantization with error-feedback, the algorithm can get close to the
stationary point. Moreover, when testing the model they can achieve similar
accuracy on each step of training, which is shown in the middle figure of Fig.
4. When zooming in the accuracy curve we can find that for a large
quantization level of weights, we can get better performance shown in the
right figure, which is consistent with our theoretical results. Besides, in
the bottom row, the figures show that all the settings perform well and
similarly. Still, this may be due to the easiness of the MNIST dataset.

##  5 Conclusions

To accelerate the training process of deep learning models, we proposed
distributed Adam with weight quantization, gradient quantization, and the
error-feedback technique in the parameter-server model. Thanks to the
introduction of two schemes of weight quantization and gradient quantization,
the communication cost between the server and works can be significantly
reduced. In addition, the proposed error-feedback technique can suppress the
bias caused by the gradient quantization step, thereby making the proposed
algorithm more efficiently. We further established the convergence rate of the
proposed algorithm in the nonconvex stochastic setting, which shows that
quantized Adam with the error-feedback technique converges to the neighborhood
of a stationary point under both the single-worker and multi-worker modes.
Moreover, we applied the proposed algorithm to train LetNet on the MNIST
dataset and ResNet-101 on the CIFAR100 dataset, respectively. The experiments
demonstrate the efficacy of the proposed algorithm.

## References

  * Amodei et al. (2016) Amodei, D., Ananthanarayanan, S., Anubhai, R., Bai, J., Battenberg, E., Case, C., Casper, J., Catanzaro, B., Cheng, Q., Chen, G., et al.  Deep speech 2: End-to-end speech recognition in english and mandarin.  In _International conference on machine learning_ , pp. 173–182, 2016.
  * Basu et al. (2018) Basu, A., De, S., Mukherjee, A., and Ullah, E.  Convergence guarantees for rmsprop and adam in non-convex optimization and their comparison to nesterov acceleration on autoencoders.  _arXiv preprint arXiv:1807.06766_ , 2018.
  * Chen et al. (2018) Chen, X., Liu, S., Sun, R., and Hong, M.  On the convergence of a class of adam-type algorithms for non-convex optimization.  _arXiv preprint arXiv:1808.02941_ , 2018.
  * Dean et al. (2012) Dean, J., Corrado, G., Monga, R., Chen, K., Devin, M., Mao, M., Ranzato, M., Senior, A., Tucker, P., Yang, K., et al.  Large scale distributed deep networks.  In _Advances in neural information processing systems_ , pp. 1223–1231, 2012.
  * Deng et al. (2009) Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pp. 248–255. Ieee, 2009.
  * Devlin et al. (2018) Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Duchi et al. (2011) Duchi, J., Hazan, E., and Singer, Y.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of machine learning research_ , 12(Jul):2121–2159, 2011.
  * Goodfellow et al. (2016) Goodfellow, I., Bengio, Y., and Courville, A.  _Deep learning_.  MIT press, 2016.
  * Han et al. (2015) Han, S., Mao, H., and Dally, W. J.  Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.  _arXiv preprint arXiv:1510.00149_ , 2015.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Hinton et al. (2012) Hinton, G., Srivastava, N., and Swersky, K.  Neural networks for machine learning lecture 6a overview of mini-batch gradient descent.  _Cited on_ , 14(8), 2012.
  * Hou et al. (2018) Hou, L., Zhang, R., and Kwok, J. T.  Analysis of quantized models.  2018\.
  * Kairouz et al. (2019) Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al.  Advances and open problems in federated learning.  _arXiv preprint arXiv:1912.04977_ , 2019.
  * (14) Karimireddy, S. P., Rebjock, Q., Stich, S. U., and Jaggi, M.  Error feedback fixes signsgd and other gradient compression schemes.
  * Khaled & Richtárik (2019) Khaled, A. and Richtárik, P.  Gradient descent with compressed iterates.  _arXiv preprint arXiv:1909.04716_ , 2019.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Koloskova et al. (2019) Koloskova, A., Lin, T., Stich, S. U., and Jaggi, M.  Decentralized deep learning with arbitrary communication compression.  _arXiv preprint arXiv:1907.09356_ , 2019.
  * Kraska et al. (2013) Kraska, T., Talwalkar, A., Duchi, J. C., Griffith, R., Franklin, M. J., and Jordan, M. I.  Mlbase: A distributed machine-learning system.  In _Cidr_ , volume 1, pp. 2–1, 2013.
  * Krizhevsky et al. (2009) Krizhevsky, A., Hinton, G., et al.  Learning multiple layers of features from tiny images.  2009\.
  * Krizhevsky et al. (2012) Krizhevsky, A., Sutskever, I., and Hinton, G. E.  Imagenet classification with deep convolutional neural networks.  In _Advances in neural information processing systems_ , pp. 1097–1105, 2012.
  * LeCun et al. (1998) LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * LeCun et al. (2015) LeCun, Y., Bengio, Y., and Hinton, G.  Deep learning.  _nature_ , 521(7553):436–444, 2015.
  * Li et al. (2014) Li, M., Andersen, D. G., Park, J. W., Smola, A. J., Ahmed, A., Josifovski, V., Long, J., Shekita, E. J., and Su, B.-Y.  Scaling distributed machine learning with the parameter server.  In _11th $\\{$USENIX$\\}$ Symposium on Operating Systems Design and Implementation ($\\{$OSDI$\\}$ 14)_, pp. 583–598, 2014.
  * Li & Orabona (2018) Li, X. and Orabona, F.  On the convergence of stochastic gradient descent with adaptive stepsizes.  _arXiv preprint arXiv:1805.08114_ , 2018.
  * Lian et al. (2017) Lian, X., Zhang, C., Zhang, H., Hsieh, C.-J., Zhang, W., and Liu, J.  Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent.  In _Advances in Neural Information Processing Systems_ , pp. 5330–5340, 2017.
  * Liu et al. (2017) Liu, T.-Y., Chen, W., and Wang, T.  Distributed machine learning: Foundations, trends, and practices.  In _Proceedings of the 26th International Conference on World Wide Web Companion_ , pp. 913–915, 2017.
  * McMahan & Streeter (2010) McMahan, H. B. and Streeter, M.  Adaptive bound optimization for online convex optimization.  _arXiv preprint arXiv:1002.4908_ , 2010.
  * Mnih et al. (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, 2015.
  * Rastegari et al. (2016) Rastegari, M., Ordonez, V., Redmon, J., and Farhadi, A.  Xnor-net: Imagenet classification using binary convolutional neural networks.  In _European conference on computer vision_ , pp. 525–542. Springer, 2016.
  * Reddi et al. (2019) Reddi, S. J., Kale, S., and Kumar, S.  On the convergence of adam and beyond.  _arXiv preprint arXiv:1904.09237_ , 2019.
  * Silver et al. (2016) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484, 2016.
  * Simonyan & Zisserman (2014) Simonyan, K. and Zisserman, A.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Smola & Narayanamurthy (2010) Smola, A. and Narayanamurthy, S.  An architecture for parallel topic models.  _Proceedings of the VLDB Endowment_ , 3(1-2):703–710, 2010.
  * Stich & Karimireddy (2019) Stich, S. U. and Karimireddy, S. P.  The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication.  _arXiv preprint arXiv:1909.05350_ , 2019.
  * Tang et al. (2019) Tang, H., Lian, X., Qiu, S., Yuan, L., Zhang, C., Zhang, T., and Liu, J.  Deepsqueeze: Decentralized meets error-compensated compression.  _arXiv preprint arXiv:1907.07346_ , 2019.
  * Ward et al. (2018) Ward, R., Wu, X., and Bottou, L.  Adagrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization.  _arXiv preprint arXiv:1806.01811_ , 2018.
  * Wu et al. (2019) Wu, B., Chen, W., Fan, Y., Zhang, Y., Hou, J., Liu, J., and Zhang, T.  Tencent ml-images: A large-scale multi-label image database for visual representation learning.  _IEEE Access_ , 7:172683–172693, 2019.
  * Wu et al. (2018) Wu, S., Li, G., Chen, F., and Shi, L.  Training and inference with integers in deep neural networks.  _arXiv preprint arXiv:1802.04680_ , 2018.
  * Xing et al. (2015) Xing, E. P., Ho, Q., Dai, W., Kim, J. K., Wei, J., Lee, S., Zheng, X., Xie, P., Kumar, A., and Yu, Y.  Petuum: A new platform for distributed machine learning on big data.  _IEEE Transactions on Big Data_ , 1(2):49–67, 2015.
  * Yang et al. (2019) Yang, Q., Liu, Y., Chen, T., and Tong, Y.  Federated machine learning: Concept and applications.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ , 10(2):1–19, 2019.
  * Zhou et al. (2016) Zhou, S., Ni, Z., Zhou, X., Wen, H., Wu, Y., and Zou, Y.  Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients.  _CoRR_ , abs/1606.06160, 2016.  URL http://arxiv.org/abs/1606.06160.
  * Zhou et al. (2018) Zhou, Z., Zhang, Q., Lu, G., Wang, H., Zhang, W., and Yu, Y.  Adashift: Decorrelation and convergence of adaptive learning rate methods.  _arXiv preprint arXiv:1810.00143_ , 2018.
  * Zou et al. (2018) Zou, F., Shen, L., Jie, Z., Sun, J., and Liu, W.  Weighted adagrad with unified momentum.  _arXiv preprint arXiv:1808.03408_ , 2018.
  * Zou et al. (2019) Zou, F., Shen, L., Jie, Z., Zhang, W., and Liu, W.  A sufficient condition for convergences of adam and rmsprop.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 11127–11135, 2019.

In this supplementary material, we provide the detailed proof procedures of
Theorem 1, Theorem 2 and Theorem 3 in Section A, Section B and Section C,
respectively. Moreover, the related corollaries of the main theorems are also
provided. Besides, we provide additional experiments to demonstrate the
effectiveness of the proposed algorithms.

##  Appendix A Proof of Theorem 1

Before providing the detailed proof of Theorem 1, we first denote several
useful notations. Then, we provide several lemmas that are used to split the
main proof of Theorem 1 for better readability.

######  Notation 1.

Denote $\sigma_{t}^{2}=\mathbb{E}_{t}[g_{t}^{2}]$ where
$\mathbb{E}_{t}[\cdot]$ is the conditional expectation on the random variables
$\\{x_{t},x_{t-1},\cdots,x_{1}\\}$. Denote
$\hat{v}_{t}=\theta_{t}v_{t-1}+(1-\theta_{t})\sigma_{t}^{2}$,
$\hat{\eta}_{t}=\alpha_{t}/\sqrt{\hat{v}_{t}}$,
$\Delta_{t}=-\alpha_{t}m_{t}/\sqrt{v_{t}}$, $M_{t}=\mathbb{E}[\langle\nabla
f(x_{t}),\Delta_{t}\rangle+L(2-\delta_{g})\|\Delta_{t}\|^{2}+L(2-\delta_{g})\|e_{t}\|\|\Delta_{t}\|]$
and
$\|x\|_{\hat{\eta}_{t}}^{2}=\sum_{i=1}^{d}\hat{\eta}_{t}^{(i)}{x^{(i)}}^{2}$.
In addition, let $\tilde{x}_{t}=x_{t}-e_{t}$. Then, it holds that
$\tilde{x}_{t+1}=x_{t}-Q_{g}(-\Delta_{t}+e_{t})-e_{t+1}=x_{t}+\Delta_{t}-e_{t}=\tilde{x}_{t}+\Delta_{t}$.

######  Lemma 2.

By using Notation 1 and the iteration scheme of Theorem 1, for all $t\geq 1$
the following inequality holds:

$m_{t}^{2}\leq\frac{1}{C_{1}(1-\gamma)(1-\theta_{t})}v_{t}.$

###### Proof.

By using the definition of $m_{t}$ in Theorem 1, it directly holds that

$\displaystyle m_{t}=\sum_{i=1}^{t}\beta^{t-i}(1-\beta)g_{i}.$ (3)

Let $\Theta(t,i)=\prod_{j=i+1}^{t}\theta_{j}$ for $i<t$, and $\Theta(i,i)=1$.
According to the definition of $v_{t}$, it holds that

$v_{t}=\sum_{i=1}^{t}\left(\prod_{j=i+1}^{t}\theta_{j}\right)(1-\theta_{i})g_{i}^{2}=\sum_{i=1}^{t}\Theta(t,i)(1-\theta_{i})g_{i}^{2}.$

With arithmetic inequality and Eq. (3), it holds that

$\begin{split}m_{t}^{2}&=\left(\sum_{i=1}^{t}\frac{\beta^{t-i}(1-\beta)}{\sqrt{\Theta(t,i)(1-\theta_{i})}}\sqrt{\Theta(t,i)(1-\theta_{i})}g_{i}\right)^{2}\leq\sum_{i=1}^{t}\frac{\beta^{2(t-i)}(1-\beta)^{2}}{\Theta(t,i)(1-\theta_{i})}\sum_{i=1}^{t}\Theta(t,i)(1-\theta_{i})g_{i}^{2}\\\
&=\sum_{i=1}^{t}\frac{\beta^{2(t-i)}(1-\beta)^{2}}{\Theta(t,i)(1-\theta_{i})}v_{t}\leq\sum_{i=1}^{t}\frac{\beta^{2(t-i)}}{(\prod_{j=i+1}^{N}\theta_{j}){\theta^{\prime}}^{t-N}(1-\theta_{i})}v_{t}=\sum_{i=1}^{t}\frac{\beta^{2(t-i)}}{(\prod_{j=i+1}^{N}\theta_{j}/\theta^{\prime})(\theta^{\prime})^{t-i}(1-\theta_{i})}v_{t}\\\
&\leq\sum_{i=1}^{t}\frac{\beta^{2(t-i)}}{(\prod_{j=1}^{N}\theta_{j}/\theta^{\prime})(\theta^{\prime})^{t-i}(1-\theta_{i})}v_{t}=\sum_{i=1}^{t}\frac{\beta^{2(t-i)}}{C_{1}(\theta^{\prime})^{t-i}(1-\theta_{i})}v_{t}\leq\frac{1}{C_{1}(1-\theta_{t})}\sum_{i=1}^{t}\left(\frac{\beta^{2}}{\theta^{\prime}}\right)^{t-i}v_{t}\\\
&\leq\frac{1}{C_{1}(1-\gamma)(1-\theta_{t})}v_{t}.\end{split}$

Then, we obtain the targeted result. ∎

######  Lemma 3.

Let $\tau$ be randomly chosen from $\\{1,2,\cdots,T\\}$ with equal
probabilities $p_{\tau}=\frac{1}{T}$. We have the following estimate:

$\mathbb{E}[\|\nabla f((x_{\tau}))\|^{2}]\leq\frac{\sqrt{G^{2}+\epsilon
d}}{\alpha\sqrt{T}}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f((x_{t}))\|_{\hat{\eta_{t}}}^{2}\right].$

###### Proof.

Note that
$\|\hat{v}_{t}\|_{1}=\theta_{t}\|v_{t-1}\|_{1}+(1-\theta_{t})\|\sigma_{t}\|^{2}$
and $\|g_{t}\|\leq G$. It is straightforward to prove $\|v_{t}\|_{1}\leq
G^{2}$. Hence, we have $\|\hat{v}_{t}+\epsilon\|_{1}\leq G^{2}+\epsilon d$.
Utilizing this inequality, we have

$\begin{split}\|\nabla f(x_{t})\|^{2}&=\frac{\|\nabla
f(x_{t})\|^{2}}{\sqrt{\|\hat{v}_{t}+\epsilon\|_{1}}}\sqrt{\|\hat{v}_{t}+\epsilon\|_{1}}=\sqrt{\|\hat{v}_{t}+\epsilon\|_{1}}\sum_{k=1}^{d}\frac{|\nabla_{k}f(x_{t})|^{2}}{\sqrt{\sum_{l=1}^{d}\hat{v}_{t,l}+\epsilon}}\\\
&\leq\sqrt{\|\hat{v}_{t}+\epsilon\|_{1}}\alpha_{t}^{-1}\sum_{k=1}^{d}\frac{\alpha_{t}}{\sqrt{\hat{v}_{t,k}+\epsilon}}|\nabla_{k}f(x_{t})|^{2}\\\
&=\sqrt{\|\hat{v}_{t}+\epsilon\|_{1}}\alpha_{t}^{-1}\|\nabla
f(x_{t})\|_{\hat{\eta}_{t}}^{2}\leq\sqrt{G^{2}+\epsilon
d}\alpha_{t}^{-1}\|\nabla f(x_{t})\|_{\hat{\eta}_{t}}^{2}\\\
&\leq\frac{\sqrt{G^{2}+\epsilon d}}{\alpha_{T}}\|\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}.\end{split}$

Then, by using the definition of $x_{\tau}$, we obtain

$\mathbb{E}\left[\|\nabla
f(x_{\tau})\|^{2}\right]=\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[\|\nabla
f(x_{t})\|^{2}\right]\leq\frac{\sqrt{G^{2}+\epsilon
d}}{\alpha\sqrt{T}}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}\right].$

Thus, the desired result is obtained. ∎

######  Lemma 4.

By using Notation (1), the following inequality holds:

$\sum_{t=1}^{T}\|\Delta_{t}\|^{2}\leq\frac{G^{2}}{\epsilon}\sum_{t=1}^{T}\frac{\alpha^{2}}{t}.$

###### Proof.

By using the definition of $m_{t}$, it holds $\|m_{t}\|^{2}\leq G^{2}$. Then,
$\|\Delta_{t}\|^{2}=\|\frac{\alpha_{t}m_{t}}{\sqrt{v_{t}+\epsilon}}\|^{2}\leq\frac{G^{2}}{\epsilon}\alpha_{t}^{2}$
by using the definition of $\Delta_{t}$. Therefore,

$\sum_{t=1}^{T}\|\Delta_{t}\|\leq\frac{G^{2}}{\epsilon}\sum_{t=1}^{T}\frac{\alpha^{2}}{t}.$

Hence, the desired result holds. ∎

######  Lemma 5.

By the iteration scheme of Algorithm 1, it holds that

$\sum_{t=1}^{T}\|e_{t}\|\|\Delta_{t}\|\leq\sum_{t=1}^{T}\frac{1-\delta_{g}}{\delta_{g}}\|\Delta_{t}\|^{2}.$

###### Proof.

By the definition of noisy term $e_{t}$ and $\Delta_{t}$, it holds

$\begin{split}\|e_{t}\|&=\|\Delta_{t}+e_{t-1}-Q_{g}(\Delta_{t}+e_{t-1})\|\leq(1-\delta_{g})\|\Delta_{t}+e_{t-1}\|\leq(1-\delta_{g})\|\Delta_{t}\|+(1-\delta_{g})\|e_{t-1}\|\\\
&\leq\sum_{i=1}^{t}(1-\delta_{g})^{t-i+1}\|\Delta_{i}\|.\end{split}$

Therefore, we have

$\displaystyle\sum_{t=1}^{T}\|e_{t}\|\|\Delta_{t}\|\leq\sum_{t=1}^{T}\sum_{i=1}^{t}(1-\delta_{g})^{t-i+1}\|\Delta_{i}\|\|\Delta_{t}\|.$
(4)

In addition, let
$\Delta=\left[\begin{array}[]{cccc}\|\Delta_{1}\|&\|\Delta_{2}\|&\cdots&\|\Delta_{T}\|\end{array}\right]^{\top}$
and $U$ be the following $T\times T$ matrix:

$U=\left[\begin{array}[]{ccccc}(1-\delta_{g})&(1-\delta_{g})^{2}/2&(1-\delta_{g})^{3}/2&\cdots&(1-\delta_{g})^{T}/2\\\
(1-\delta_{g})^{2}/2&(1-\delta_{g})&(1-\delta_{g})^{2}/2&\cdots&(1-\delta_{g})^{T-1}/2\\\
(1-\delta_{g})^{3}/2&(1-\delta_{g})^{2}/2&(1-\delta_{g})&\cdots&(1-\delta_{g})^{T-2}/2\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
(1-\delta_{g})^{T}/2&(1-\delta_{g})^{T-1}/2&(1-\delta_{g})^{T-2}/2&\cdots&(1-\delta_{g})\end{array}\right].$

Let $\rho(U)$ be the spectral radius of $U$ and $\|U\|_{\infty}$ be
$\infty$-norm which is defined to be the maximal row sum of $U$. Then, it
holds that

$\rho(U)\leq\|U\|_{\infty}\leq
2\sum_{t=1}^{T/2+1}(1-\delta_{g})^{t}/2\leq\frac{1-\delta_{g}}{\delta_{g}}.$

Utilizing the above inequality, we obtain

$\sum_{t=1}^{T}\sum_{i=1}^{t}(1-\delta_{g})^{t-i+1}\|\Delta_{i}\|\|\Delta_{t}\|=\Delta^{T}U\Delta\leq\rho(U)\Delta^{T}\Delta\leq\frac{1-\delta_{g}}{\delta_{g}}\sum_{t=1}^{T}\|\Delta_{t}\|^{2}.$

Substituting the above inequality into Eq. (4), we obtain the desired result.
∎

######  Lemma 6.

By the definition of $M_{k}$, it holds that

$\sum_{t=1}^{T}M_{t}\leq\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta)\sum_{t=1}^{T}\frac{1}{t}-\frac{1-\beta}{2}\mathbb{E}\left[\|\sum_{t=1}^{T}\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}\right],$

where

$\begin{split}C_{2}&=\frac{5\alpha
G^{3}(1-\beta)}{2\epsilon\sqrt{\theta}}\left(\frac{\beta}{(1-\beta)\sqrt{\theta_{1}C_{1}(1-\gamma)}}+1\right)^{2}+\frac{5\alpha
G^{3}}{2\epsilon\sqrt{\theta}}+\frac{5\beta^{2}\alpha
d\sqrt{\epsilon}}{2\sqrt{\theta}(1-\beta)\theta_{1}C_{1}(1-\gamma)}\\\
&+\frac{5\alpha\sqrt{G^{2}+\epsilon}G^{2}\beta^{2}}{2(1-\beta)\sqrt{\theta}\theta_{1}C_{1}(1-\gamma)\epsilon}+\frac{5\alpha\sqrt{G^{2}+\epsilon}\beta^{2}d}{2(1-\beta)\sqrt{\theta}\theta_{1}C_{1}(1-\gamma)}.\end{split}$

###### Proof.

Using the definitions of $v_{t}$ and $\hat{v}_{t}$, we obtain

$\begin{split}\frac{(1-\beta)\alpha_{t}g_{t}}{\sqrt{v_{t}+\epsilon}}&=\frac{(1-\beta)\alpha_{t}g_{t}}{\sqrt{\hat{v}_{t}+\epsilon}}+(1-\beta)\alpha_{t}g_{t}\left(\frac{1}{\sqrt{v_{t}+\epsilon}}-\frac{1}{\sqrt{\hat{v}_{t}+\epsilon}}\right)\\\
&=(1-\beta)\hat{\eta}_{t}g_{t}+(1-\beta)\alpha_{t}g_{t}\frac{(1-\theta_{t})(\sigma_{t}^{2}-g_{t}^{2})}{\sqrt{v_{t}+\epsilon}\sqrt{\hat{v}_{t}+\epsilon}(\sqrt{v_{t}+\epsilon}+\sqrt{\hat{v}_{t}+\epsilon})}\\\
&=(1-\beta)\hat{\eta}_{t}g_{t}+\hat{\eta}_{t}\sigma_{t}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{(1-\beta)\sigma_{t}}{\sqrt{v_{t}+\epsilon}+\sqrt{\hat{v}_{t}+\epsilon}}-\hat{\eta}_{t}g_{t}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{(1-\beta)g_{t}}{\sqrt{v_{t}+\epsilon}+\sqrt{\hat{v}_{t}+\epsilon}}.\end{split}$

In addition, it is not hard to check that the following equalities hold:

$\begin{split}&\qquad\beta\alpha_{t}m_{t-1}\left(\frac{1}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}-\frac{1}{\sqrt{v_{t}}+\epsilon}\right)\\\
&=\beta\alpha_{t}m_{t-1}\frac{(1-\theta_{t})(g_{t}^{2}+\epsilon)}{\sqrt{v_{t}+\epsilon}\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}(\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon})}\\\
&=\beta\alpha_{t}m_{t-1}\frac{(1-\theta_{t})(g_{t}^{2}+\epsilon)}{\sqrt{v_{t}+\epsilon}\sqrt{\hat{v}_{t}+\epsilon}(\sqrt{v_{t}+\epsilon}+{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}})}\\\
&\qquad+\beta\alpha_{t}m_{t-1}\frac{(1-\theta_{t})(g_{t}^{2}+\epsilon)}{\sqrt{v_{t}+\epsilon}(\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon})}\left(\frac{1}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}-\frac{1}{\sqrt{\hat{v}_{t}+\epsilon}}\right)\\\
&=\hat{\eta}_{t}g_{t}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}+\hat{\eta}_{t}\epsilon\frac{(1-\theta_{t})}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\\\
&\qquad+\frac{\beta\alpha_{t}m_{t-1}(1-\theta_{t})^{2}(g_{t}^{2}+\epsilon)(\sigma_{t}^{2}+\epsilon)}{\sqrt{v_{t}+\epsilon}\sqrt{\hat{v}_{t}+\epsilon}\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon})\sqrt{\hat{v}_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon})}\\\
&=\hat{\eta}_{t}g_{t}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}+\hat{\eta}_{t}\epsilon\frac{(1-\theta_{t})}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\\\
&\qquad+\hat{\eta}_{t}\sqrt{\sigma_{t}^{2}+\epsilon}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}g_{t}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\sigma_{t}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\\\
&\qquad+\hat{\eta}_{t}\sqrt{\sigma_{t}^{2}+\epsilon}\frac{(1-\theta_{t})\sqrt{\epsilon}}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\epsilon}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\sigma_{t}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}.\end{split}$

For convenience, we denote

$\displaystyle A^{1}_{t}$
$\displaystyle=\hat{\eta}_{t}g_{t}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\left(\frac{\beta
m_{t-1}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}+\frac{(1-\beta)g_{t}}{\sqrt{v_{t}+\epsilon}+\sqrt{\hat{v}_{t}}+\epsilon}\right),$
(5) $\displaystyle A^{2}_{t}$
$\displaystyle=-\hat{\eta}_{t}\sigma_{t}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{(1-\beta)\sigma_{t}}{\sqrt{v_{t}+\epsilon}+\sqrt{\hat{v}_{t}+\epsilon}},$
(6) $\displaystyle A^{3}_{t}$
$\displaystyle=\hat{\eta}_{t}\epsilon\frac{(1-\theta_{t})}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}},$
(7) $\displaystyle A^{4}_{t}$
$\displaystyle=\hat{\eta}_{t}\sqrt{\sigma_{t}^{2}+\epsilon}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}g_{t}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\sigma_{t}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}},$
(8) $\displaystyle A^{5}_{t}$
$\displaystyle=\hat{\eta}_{t}\sqrt{\sigma_{t}^{2}+\epsilon}\frac{(1-\theta_{t})\sqrt{\epsilon}}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\epsilon}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\sigma_{t}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}.$
(9)

Then, we obtain

$\begin{split}\Delta_{t}-\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}\Delta_{t-1}&=-\frac{\alpha_{t}m_{t}}{\sqrt{v_{t}+\epsilon}}+\frac{\beta\alpha_{t}m_{t-1}}{\sqrt{\theta_{t}(v_{t-1}+\epsilon)}}\\\
&=-\frac{(1-\beta)\alpha_{t}g_{t}}{\sqrt{v_{t}+\epsilon}}+\beta\alpha_{t}m_{t-1}\left(\frac{1}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}-\frac{1}{\sqrt{v_{t}+\epsilon}}\right)\\\
&=-(1-\beta)\hat{\eta}_{t}g_{t}-\hat{\eta}_{t}\sigma_{t}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{(1-\beta)\sigma_{t}}{\sqrt{v_{t}+\epsilon}\sqrt{\hat{v}_{t}+\epsilon}}+\hat{\eta}_{t}g_{t}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{(1-\beta)g_{t}}{\sqrt{v_{t}+\epsilon}\sqrt{\hat{v}_{t}+\epsilon}}\\\
&+\hat{\eta}_{t}g_{t}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}+\hat{\eta}_{t}\epsilon\frac{(1-\theta_{t})}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\\\
&+\hat{\eta}_{t}\sqrt{\sigma_{t}^{2}+\epsilon}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}g_{t}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\sigma_{t}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\\\
&+\hat{\eta}_{t}\sqrt{\sigma_{t}^{2}+\epsilon}\frac{(1-\theta_{t})\sqrt{\epsilon}}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\epsilon}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\sigma_{t}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\\\
&=-(1-\beta)\hat{\eta}_{t}g_{t}+A^{1}_{t}+A^{2}_{t}+A^{3}_{t}+A^{4}_{t}+A^{5}_{t}.\end{split}$

By using the above inequality, we derive the upper bound for the term
$\mathbb{E}\langle\nabla f(x_{t}),\Delta_{t}\rangle$:

$\begin{split}\mathbb{E}\langle\nabla
f(x_{t}),\Delta_{t}\rangle&=\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}\mathbb{E}\langle\nabla
f(x_{t}),\Delta_{t-1}\rangle+\mathbb{E}\langle\nabla
f(x_{t}),\Delta_{t}-\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t}}\Delta_{t-1}\rangle\\\
&=\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(x_{t-1}),\Delta_{t-1}\rangle+\mathbb{E}\langle\nabla f(x_{t})-\nabla
f(x_{t-1}),\Delta_{t-1}\rangle)\\\ &\qquad+\mathbb{E}\langle\nabla
f(x_{t}),-(1-\beta)\hat{\eta}_{t}g_{t}\rangle+\mathbb{E}\langle\nabla
f(x_{t}),A^{1}_{t}\rangle+\mathbb{E}\langle\nabla f(x_{t}),A^{2}_{t}\rangle\\\
&\qquad+\mathbb{E}\langle\nabla
f(x_{t}),A^{3}_{t}\rangle+\mathbb{E}\langle\nabla
f(x_{t}),A^{4}_{t}\rangle+\mathbb{E}\langle\nabla
f(x_{t}),A^{5}_{t}\rangle.\end{split}$ (10)

For the first term in Eq (10), we have

$\begin{split}&\qquad\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(x_{t-1}),\Delta_{t-1}\rangle+\mathbb{E}\langle\nabla f(x_{t})-\nabla
f(x_{t-1}),\Delta_{t-1}\rangle)\\\
&\leq\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(x_{t-1}),\Delta_{t-1}\rangle+\mathbb{E}[L\|x_{t}-x_{t-1}\|\|\Delta_{t-1}\|)]\\\
&=\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(x_{t-1}),\Delta_{t-1}\rangle+L\mathbb{E}[\|\Delta_{t-1}\|\|Q_{g}(\Delta_{t-1}+e_{t-1})\|]\\\
&\leq\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(x_{t-1}),\Delta_{t-1}\rangle+L\mathbb{E}[\|\Delta_{t-1}\|(\|Q_{g}(\Delta_{t-1}+e_{t-1})-(\Delta_{t-1}+e_{t-1})\|+\|\Delta_{t-1}+e_{t-1}\|)]\\\
&\leq\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(x_{t-1}),\Delta_{t-1}\rangle+L(2-\delta_{g})\mathbb{E}[\|\Delta_{t-1}\|^{2}]+L(2-\delta_{g})\mathbb{E}[\|e_{t-1}\|\|\Delta_{t-1}\|])\\\
&=\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}M_{t-1}.\end{split}$

For the second term in Eq. (10), we have

$\begin{split}-(1-\beta)\mathbb{E}\langle\nabla
f(x_{t}),\hat{\eta}_{t}g_{t}\rangle&=-(1-\beta)\mathbb{E}\langle\nabla
f(x_{t}),\hat{\eta}_{t}\mathbb{E}_{t}[g_{t}]\rangle=-(1-\beta)\mathbb{E}\|\nabla
f(x_{t})\|_{\hat{\eta}_{t}}^{2}.\end{split}$

For the third term in Eq. (10), we have

$\begin{split}\mathbb{E}\langle\nabla
f(x_{t}),A^{1}_{t}\rangle&\leq\mathbb{E}\langle\frac{\sqrt{\hat{\eta}_{t}}|\nabla
f(x_{t})||g_{t}|}{\sigma_{t}},\frac{\sqrt{\hat{\eta}_{t}}\sigma_{t}(1-\theta_{t})|g_{t}|\left|\frac{\beta
m_{t-1}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}+\frac{(1-\beta)g_{t}}{\sqrt{v_{t}+\epsilon}}\right|}{\sqrt{v_{t}+\epsilon}}\rangle\\\
&\leq\mathbb{E}\langle\frac{\sqrt{\hat{\eta}_{t}}|\nabla
f(x_{t})||g_{t}|}{\sigma_{t}},\sqrt{\frac{\alpha
G}{\sqrt{\theta}}}\frac{(1-\theta_{t})|g_{t}|\left(\left|\frac{\beta
m_{t-1}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\right|+\left|\frac{(1-\beta)g_{t}}{\sqrt{v_{t}+\epsilon}}\right|\right)}{\sqrt{v_{t}+\epsilon}}\rangle\\\
&\leq\mathbb{E}\langle\frac{\sqrt{\hat{\eta}_{t}}|\nabla
f(x_{t})||g_{t}|}{\sigma_{t}},\sqrt{\frac{\alpha
G}{\sqrt{\theta}}}\left(\frac{\beta}{\sqrt{\theta_{1}C_{1}(1-\gamma)}}+(1-\beta)\right)\frac{\sqrt{1-\theta_{t}}|g_{t}|}{\sqrt{v_{t}+\epsilon}}\rangle\\\
&\leq\frac{1-\beta}{10}\mathbb{E}\left\|\frac{\sqrt{\hat{\eta}_{t}}|\nabla
f(x_{t})|\mathbb{E}_{t}|g_{t}|}{\sigma_{t}}\right\|^{2}+\frac{2\alpha
G}{5\sqrt{\theta}}\left(\frac{\beta}{(1-\beta)\sqrt{\theta_{1}C_{1}(1-\gamma)}}+1\right)^{2}\mathbb{E}\left\|\frac{\sqrt{1-\theta_{t}}g_{t}}{\sqrt{v_{t}+\epsilon}}\right\|^{2}\\\
&\leq\frac{1-\beta}{10}\mathbb{E}\|\nabla
f(x_{t})\|_{\hat{\eta}_{t}}^{2}+\frac{5\alpha
G^{3}(1-\beta)(1-\theta_{t})}{2\epsilon\sqrt{\theta}}\left(\frac{\beta}{(1-\beta)\sqrt{\theta_{1}C_{1}(1-\gamma)}}+1\right)^{2},\end{split}$

where the equalities hold according to the following inequities, respectively,

$\displaystyle\sqrt{\hat{\eta}_{t}}\sigma_{t}=\sqrt{\frac{\alpha_{t}\sigma_{t}^{2}}{\sqrt{\hat{v}_{t}+\epsilon}}}\leq\sqrt{\frac{\alpha_{t}\sigma_{t}^{2}}{\sqrt{(1-\theta_{t})\sigma_{t}^{2}}}}\leq\sqrt{\frac{G\alpha_{t}}{\sqrt{1-\theta_{t}}}}=\sqrt{\frac{\alpha
G}{\sqrt{\theta}}},$ $\displaystyle\left|\frac{\beta
m_{t-1}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\right|\leq\left|\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}}}\right|\leq\frac{\beta}{\sqrt{\theta_{t}(1-\theta_{t})C_{1}(1-\gamma)}}\leq\frac{\beta}{\sqrt{\theta_{1}(1-\theta_{t})C_{1}(1-\gamma)}},$
$\displaystyle\left|\frac{(1-\beta)g_{t}}{\sqrt{v_{t}+\epsilon}}\right|\leq\left|\frac{(1-\beta)g_{t}}{\sqrt{(1-\theta_{t})g_{t}^{2}}}\right|=\frac{1-\beta}{\sqrt{1-\theta_{t}}}.$

For the fourth term in Eq. (10), we have

$\begin{split}\mathbb{E}\langle\nabla
f(x_{t}),A^{2}_{t}\rangle&\leq\mathbb{E}\langle|\nabla
f(x_{t})|,\left|\hat{\eta}_{t}\sigma_{t}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{(1-\beta)\sigma_{t}}{\sqrt{v_{t}+\epsilon}+\sqrt{\hat{v}_{t}+\epsilon}}\right|\rangle\\\
&\leq\mathbb{E}\langle\sqrt{\hat{\eta}_{t}}|\nabla
f(x_{t})|,\sqrt{\hat{\eta}_{t}}\sigma_{t}\left|\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\right|\left|\frac{(1-\beta)\sigma_{t}}{\sqrt{v_{t}+\epsilon}+\sqrt{\hat{v}_{t}+\epsilon}}\right|\rangle\\\
&\leq\frac{1-\beta}{10}\mathbb{E}\|\nabla
f(x_{t})\|_{\hat{\eta}_{t}}^{2}+\frac{2\alpha
G}{5\theta}\mathbb{E}\left\|\frac{\sqrt{1-\theta_{t}}g_{t}}{\sqrt{v_{t}+\epsilon}}\right\|^{2}\\\
&\leq\frac{1-\beta}{10}\mathbb{E}\|\nabla
f(x_{t})\|_{\hat{\eta}_{t}}^{2}+\frac{5\alpha
G^{3}(1-\theta_{t})}{2\sqrt{\theta}\epsilon},\\\ \end{split}$

where the equality holds according to

$\left|\frac{(1-\beta)\sigma_{t}}{\sqrt{v_{t}+\epsilon}+\sqrt{\hat{v}_{t}+\epsilon}}\right|\leq\left|\frac{(1-\beta)\sigma_{t}}{\sqrt{\hat{v}_{t}+\epsilon}}\right|\leq\left|\frac{(1-\beta)\sigma_{t}}{\sqrt{(1-\theta_{t})\sigma_{t}^{2}}}\right|=\frac{1-\beta}{\sqrt{1-\theta_{t}}}.$

For the fifth term in Eq. (10), we have

$\begin{split}\mathbb{E}\langle\nabla
f(x_{t}),A^{3}_{t}\rangle&\leq\mathbb{E}\langle|\nabla
f(x_{t})|,\left|\hat{\eta}_{t}\epsilon\frac{(1-\theta_{t})}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\right|\rangle\\\
&\leq\mathbb{E}\langle\sqrt{\hat{\eta}_{t}}|\nabla
f(x_{t})|,\sqrt{\hat{\eta}_{t}}\epsilon\frac{(1-\theta_{t})\beta|m_{t-1}|}{\sqrt{\epsilon}\sqrt{\theta_{t}v_{t-1}}}\rangle\\\
&\leq\frac{1-\beta}{10}\mathbb{E}\|\nabla
f(x_{t})\|_{\hat{\eta}_{t}}^{2}+\frac{5(1-\theta_{t})\beta^{2}\alpha
d\sqrt{\epsilon}}{2\sqrt{\theta}(1-\beta)\theta_{1}C_{1}(1-\gamma)},\end{split}$

where the inequality holds according to

$\sqrt{\hat{\eta}_{t}}\epsilon\leq\sqrt{\frac{\alpha_{t}\epsilon^{2}}{\sqrt{\hat{v}_{t}+\epsilon}}}\leq\sqrt{\frac{\alpha_{t}\epsilon^{2}}{\sqrt{(1-\theta_{t})\epsilon}}}\leq\sqrt{\frac{\alpha\epsilon^{3/2}}{\sqrt{\theta}}}.$

For the sixth term in Eq. (10), we have

$\begin{split}&\mathbb{E}\langle\nabla f(x_{t}),A^{4}_{t}\rangle\\\
&\leq\mathbb{E}\langle|\nabla
f(x_{t})|,\left|\hat{\eta}_{t}\sqrt{\sigma_{t}^{2}+\epsilon}\frac{(1-\theta_{t})g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}g_{t}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\sigma_{t}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\right|\rangle\\\
&\leq\mathbb{E}\langle\sqrt{\hat{\eta}_{t}}|\nabla
f(x_{t})|,\sqrt{\frac{\alpha\sqrt{G^{2}+\epsilon}}{\sqrt{\theta}}}\frac{\beta}{\sqrt{\theta_{1}C_{1}(1-\gamma)}}\frac{\sqrt{1-\theta_{t}}|g_{t}|}{\sqrt{v_{t}+\epsilon}}\rangle\\\
&\leq\frac{1-\beta}{10}\mathbb{E}\|\nabla
f(x_{t})\|_{\hat{\eta}_{t}}^{2}+\frac{5\alpha\sqrt{G^{2}+\epsilon}G^{2}\beta^{2}(1-\theta_{t})}{2(1-\beta)\sqrt{\theta}\theta_{1}C_{1}(1-\gamma)\epsilon},\end{split}$

where the equalities hold according to

$\sqrt{\hat{\eta}_{t}}\sqrt{\sigma_{t}^{2}+\epsilon}=\sqrt{\frac{\alpha_{t}(\sigma_{t}^{2}+\epsilon)}{\sqrt{\hat{v}_{t}+\epsilon}}}\leq\sqrt{\frac{\alpha_{t}(\sigma_{t}^{2}+\epsilon)}{\sqrt{(1-\theta_{t})(\sigma_{t}^{2}+\epsilon)}}}\leq\sqrt{\frac{\alpha\sqrt{G^{2}+\epsilon}}{\sqrt{\theta}}},$
$\begin{split}&\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}g_{t}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\sigma_{t}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\\\
&\leq\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}g_{t}}{\sqrt{v_{t}+\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\sigma_{t}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}+\epsilon}}\leq\frac{\beta}{\sqrt{\theta_{1}(1-\theta_{t})C_{1}(1-\gamma)}}.\end{split}$

For the seventh term in Eq. (10), we have

$\begin{split}&\mathbb{E}\langle\nabla f(x_{t}),A^{5}_{t}\rangle\\\
&\leq\mathbb{E}\langle|\nabla
f(x_{t})|,\left|\hat{\eta}_{t}\sqrt{\sigma_{t}^{2}+\epsilon}\frac{(1-\theta_{t})\sqrt{\epsilon}}{\sqrt{v_{t}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\epsilon}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\sigma_{t}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\right|\rangle\\\
&\leq\mathbb{E}\langle\sqrt{\hat{\eta}_{t}}|\nabla
f(x_{t})|,\sqrt{\frac{\alpha\sqrt{G^{2}+\epsilon}}{\sqrt{\theta}}}\frac{\beta}{\sqrt{\theta_{1}C_{1}(1-\gamma)}}\frac{\sqrt{1-\theta_{t}}\sqrt{\epsilon}}{\sqrt{v_{t}+\epsilon}}\rangle\\\
&\leq\frac{1-\beta}{10}\|\nabla
f(x_{t})\|_{\hat{\eta}_{t}}^{2}+\frac{5\alpha\sqrt{G^{2}+\epsilon}\beta^{2}(1-\theta_{t})d}{2(1-\beta)\sqrt{\theta}\theta_{1}C_{1}(1-\gamma)},\end{split}$

where the inequality holds according to

$\begin{split}&\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\epsilon}}{\sqrt{v_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\sigma_{t}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}+\epsilon}+\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\\\
&\leq\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\epsilon}}{\sqrt{(1-\theta_{t})\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\sigma_{t}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}+\epsilon}}\leq\frac{\beta}{\sqrt{\theta_{1}(1-\theta_{t})C_{1}(1-\gamma)}}.\end{split}$

Therefore, by combining the above upper estimations for the seven terms in Eq.
(10), we obtain

$\begin{split}\mathbb{E}\langle\nabla
f(x_{t}),\Delta_{t}\rangle\leq\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}M_{t-1}+C_{2}(1-\theta_{t})-\frac{1-\beta}{2}\mathbb{E}[\|\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}],\end{split}$

where $C_{2}=\frac{5\alpha
G^{3}(1-\beta)}{2\epsilon\sqrt{\theta}}\left(\frac{\beta}{(1-\beta)\sqrt{\theta_{1}C_{1}(1-\gamma)}}+1\right)^{2}+\frac{5\alpha
G^{3}}{2\epsilon\sqrt{\theta}}+\frac{5\beta^{2}\alpha
d\sqrt{\epsilon}}{2\sqrt{\theta}(1-\beta)\theta_{1}C_{1}(1-\gamma)}+\frac{5\alpha\sqrt{G^{2}+\epsilon}G^{2}\beta^{2}}{2(1-\beta)\sqrt{\theta}\theta_{1}C_{1}(1-\gamma)\epsilon}+\frac{5\alpha\sqrt{G^{2}+\epsilon}\beta^{2}d}{2(1-\beta)\sqrt{\theta}\theta_{1}C_{1}(1-\gamma)}$.

On the other hand, let
$N_{t}=L(2-\delta_{g})\mathbb{E}[\|\Delta_{t}\|^{2}]+L(2-\delta_{g})\mathbb{E}[\|e_{t}\|\|\Delta_{t}\|]+C_{2}(1-\theta_{t})$.
Recalling the definition of $M_{t}$. For $M_{1}$, we have

$\begin{split}M_{1}&=\mathbb{E}\left[-\langle\nabla
f(x_{1}),\frac{\alpha_{1}m_{1}}{\sqrt{v_{1}+\epsilon}}\rangle+L(2-\delta_{g})\|\Delta_{1}\|^{2}+L(2-\delta_{g})\|e_{1}\|\|\Delta_{1}\|\right]\\\
&=\mathbb{E}\left[-\langle\nabla
f(x_{1}),\frac{\alpha_{1}(1-\beta)g_{1}}{\sqrt{v_{1}+\epsilon}}\rangle+L(2-\delta_{g})\|\Delta_{1}\|^{2}\right]+L(2-\delta_{g})\mathbb{E}[\|e_{1}\|\|\Delta_{1}\|]\\\
&=\mathbb{E}\left[-\langle\nabla
f(x_{1}),(1-\beta_{1})\hat{\eta}_{1}g_{1}+\hat{\eta}_{1}\sigma_{1}\frac{(1-\theta_{1})g_{1}}{\sqrt{v_{1}+\epsilon}}\frac{(1-\beta)\sigma_{1}}{\sqrt{v_{1}+\epsilon}+\sqrt{\hat{v}_{1}+\epsilon}}-\hat{\eta}_{1}g_{1}\frac{(1-\theta_{1})g_{1}}{\sqrt{v_{1}+\epsilon}}\frac{(1-\beta)g_{1}}{\sqrt{v_{1}+\epsilon}+\sqrt{\hat{v}_{1}+\epsilon}}\rangle\right]\\\
&+\mathbb{E}\left[L(2-\delta_{g})\|\Delta_{1}\|^{2}\right]+L(2-\delta_{g})\mathbb{E}[\|e_{1}\|\|\Delta_{1}\|]\\\
&\leq N_{1},\end{split}$

where the last inequality holds by using $A^{1}_{t}$ and $A^{2}_{t}$.

Let $M_{0}=0$. Then we have
$M_{t}\leq\frac{{\beta\alpha_{t}}}{\sqrt{\theta_{t}}\alpha_{t-1}}M_{t-1}+N_{t}-\frac{1-\beta}{2}\mathbb{E}[\|\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}]\leq\frac{{\beta\alpha_{t}}}{\sqrt{\theta_{t}}\alpha_{t-1}}M_{t-1}+N_{t}$.
By induction we have

$\begin{split}M_{t}&\leq\sum_{i=1}^{t}\frac{\alpha_{t}\beta^{t-i}}{\alpha_{i}\sqrt{\Theta(t,i)}}N_{i}-\frac{1-\beta}{2}\mathbb{E}\left[\|\nabla
f(x_{t})\|_{\hat{\eta}_{t}}^{2}\right]\leq\frac{1}{\sqrt{C_{1}}}\sum_{i=1}^{t}\left(\frac{\beta}{\sqrt{\theta^{\prime}}}\right)^{t-i}N_{i}-\frac{1-\beta}{2}\mathbb{E}\left[\|\nabla
f(x_{t})\|_{\hat{\eta}_{t}}^{2}\right]\\\
&\leq\frac{1}{\sqrt{C_{1}}}\sum_{i=1}^{t}\sqrt{\gamma}^{t-i}N_{i}-\frac{1-\beta}{2}\mathbb{E}\left[\|\nabla
f(x_{t})\|_{\hat{\eta}_{t}}^{2}\right].\end{split}$

Therefore,

$\begin{split}\sum_{t=1}^{T}M_{t}&\leq\frac{1}{\sqrt{C_{1}}}\sum_{t=1}^{T}\sum_{i=1}^{t}\sqrt{\gamma}^{t-i}N_{i}-\frac{1-\beta}{2}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}\right]\\\
&\leq\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\sum_{t=1}^{T}N_{t}-\frac{1-\beta}{2}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}\right]\\\
&=\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\sum_{t=1}^{T}[L(2-\delta_{g})\mathbb{E}\|\Delta_{t}\|^{2}+L(2-\delta_{g})\mathbb{E}\|e_{t}\|\|\Delta_{t}\|+\frac{C_{2}\theta}{t}]-\frac{1-\beta}{2}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}\right]\\\
&\leq\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta)\sum_{t=1}^{T}\frac{1}{t}-\frac{1-\beta}{2}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}\right].\end{split}$

Hence, the targeted result holds. ∎

###### Proof of Theorem 1.

Based on Notation (1) and the above lemmas, then we can prove Theorem 1.
First, according to the gradient Lipschitz condition of $f$, it holds

$\begin{split}f(\tilde{x}_{t+1})&\leq f(\tilde{x}_{t})+\langle\nabla
f(\tilde{x}_{t}),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}^{2}\|\\\
&=f(\tilde{x}_{t})+\langle\nabla
f(x_{t}),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}\|^{2}+\langle\nabla
f(\tilde{x}_{t})-\nabla f(x_{t}),\Delta_{t}\rangle\\\ &\leq
f(\tilde{x}_{t})+\langle\nabla
f(x_{t}),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}\|^{2}+\|\nabla
f(\tilde{x}_{t})-\nabla f(x_{t})\|\|\Delta_{t}\|\\\ &\leq
f(\tilde{x}_{t})+\langle\nabla
f(x_{t}),\Delta_{t}\rangle+L(2-\delta_{g})\|\Delta_{t}\|^{2}+L(2-\delta_{g})\|e_{t}\|\|\Delta_{t}\|.\end{split}$

Recall that $M_{t}=\mathbb{E}[\langle\nabla
f(x_{t}),\Delta_{t}\rangle+L(2-\delta_{g})\|\Delta_{t}\|^{2}+L(2-\delta_{g})\|e_{t}\|\|\Delta_{t}\|]$.
Then we have

$\begin{split}f^{*}&\leq\mathbb{E}[f(\tilde{x}_{T+1})]\leq
f(x_{1})+\sum_{t=1}^{T}M_{t}\\\ &\leq f(x_{1})+\sum_{t=1}^{T}M_{t}\leq
f(x_{1})+\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta\right)\sum_{t=1}^{T}\frac{1}{t}-\frac{1-\beta}{2}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}\right].\\\ \end{split}$

Using the above lemmas and arranging the corresponding terms, we have

$\begin{split}(\mathbb{E}[\|\nabla
f((x_{\tau}^{T}))\|^{2}])&\leq\frac{\sqrt{G^{2}+\epsilon
d}}{\alpha\sqrt{T}}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(x_{t})\|_{\hat{\eta}_{t}}^{2}\right]\leq\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha\sqrt{T}}\left(f(x_{1})-f^{*}+C_{3}\sum_{t=1}^{T}\frac{1}{t}\right)\\\
&\leq\frac{C+C^{\prime}\sum_{t=1}^{T}\frac{1}{t}}{\sqrt{T}},\end{split}$

where $C_{3}$, $C^{\prime}=$ and $C^{\prime}$ are defined as follows,

$\begin{split}C_{3}=\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta\right),C=\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha}(f(x_{1})-f^{*}),C^{\prime}=\frac{2\sqrt{G^{2}+\epsilon
d}C_{3}}{(1-\beta)\alpha},\end{split}$

respectively. Hence, the proof is completed. ∎

######  Corollary 1.

For given precision $\xi$, to achieve $\mathbb{E}[\|\nabla
f(x_{\tau}^{T})\|^{2}]\leq\xi$, we have $T=O\left(\frac{1}{\xi^{2}}\right)$.

###### Proof.

For a fixed iteration $T$, let $\alpha_{t}=\frac{\alpha}{\sqrt{T}}$ and
$\theta=1-\frac{\theta}{T}$.

When $\alpha_{t}=\frac{\alpha}{\sqrt{T}}$, Lemma 4 will update to
$\sum_{t=1}^{T}\|\Delta_{t}\|^{2}\leq\frac{G^{2}\alpha^{2}}{\epsilon}$. By the
same proof in Lemma 6, we have

$\begin{split}\sum_{t=1}^{T}M_{t}&\leq\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\sum_{t=1}^{T}[L(2-\delta_{g})\mathbb{E}\|\Delta_{t}\|^{2}+L(2-\delta_{g})\mathbb{E}\|e_{t}\|\|\Delta_{t}\|+\frac{C_{2}\theta}{T}]-\frac{1-\beta}{2}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}\right]\\\
&\leq\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\sqrt{C_{1}}(1-\sqrt{\gamma})\epsilon\delta_{g}}+\frac{C_{2}\theta}{\sqrt{C_{1}}(1-\sqrt{\gamma})}-\frac{1-\beta}{2}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}\right].\end{split}$

Based on the proof of Theorem 1, we have

$\begin{split}f^{*}&\leq\mathbb{E}[f(\tilde{x}_{T+1})]\leq
f(x_{1})+\sum_{t=1}^{T}M_{t}\\\ &\leq
f(x_{1})+\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\sqrt{C_{1}}(1-\sqrt{\gamma})\epsilon\delta_{g}}+\frac{C_{2}\theta}{\sqrt{C_{1}}(1-\sqrt{\gamma})}-\frac{1-\beta}{2}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}\right].\end{split}$

Therefore,

$\begin{split}(\mathbb{E}[\|\nabla
f((x_{\tau}^{T}))\|^{2}])&\leq\frac{\sqrt{G^{2}+\epsilon
d}}{\alpha\sqrt{T}}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(x_{t})\|_{\hat{\eta}_{t}}^{2}\right]\\\ &\leq\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha\sqrt{T}}\left(f(x_{1})-f^{*}+\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\sqrt{C_{1}}(1-\sqrt{\gamma})\epsilon\delta_{g}}+\frac{C_{2}\theta}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\right).\end{split}$

By bounding $\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha\sqrt{T}}\left(f(x_{1})-f^{*}+\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\sqrt{C_{1}}(1-\sqrt{\gamma})\epsilon\delta_{g}}+\frac{C_{2}\theta}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\right)$
by $\xi$, we obtain $T=O\left(\frac{1}{\xi^{2}}\right)$.

Hence, the proof is completed. ∎

##  Appendix B Proof of Theorem 2

To prove Theorem 2, we first define some notations and provide several useful
lemmas.

######  Notation 2.

Let $\mathbb{E}_{t}[\cdot]$ be the conditional expectation with respect to
$x_{t}$ conditioned on $\\{x_{t-1},x_{t-2},\cdots,x_{1}\\}$. Denote
$\sigma_{t}^{2}=\mathbb{E}_{t}[g_{t}^{2}]$,
$\hat{v}_{t}=\theta_{t}v_{t-1}+(1-\theta_{t})\sigma_{t}^{2}$,
$\hat{\eta}_{t}=\alpha_{t}/\sqrt{\hat{v}_{t}+\epsilon}$,
$\Delta_{t}=-\alpha_{t}m_{t}/\sqrt{v_{t}+\epsilon}$, and
$M_{t}=\mathbb{E}[\langle\nabla
f(Q_{x}(x_{t})),\Delta_{t}\rangle+L\|\Delta_{t}\|^{2}+2LD\|\Delta_{t}\|]$.

######  Lemma 7.

By using Notation 2, the following inequality holds:

$\sum_{t=1}^{T}\|\Delta_{t}\|\leq\frac{2G\alpha\sqrt{T}}{\sqrt{\epsilon}}.$

###### Proof.

$\begin{split}\sum_{t=1}^{T}\|\Delta_{t}\|&=\sum_{t=1}^{T}\alpha_{t}\|\frac{m_{t}}{\sqrt{v_{t}+\epsilon}}\|\\\
&\leq\sum_{t=1}^{T}\frac{G\alpha}{\sqrt{t\epsilon}}\leq\frac{2G\alpha\sqrt{T}}{\sqrt{\epsilon}}.\end{split}$

∎

######  Lemma 8.

Based on Notation 2, we have the following upper estimation for $M_{t}$,

$\sum_{t=1}^{T}M_{t}\leq\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{LG^{2}\alpha^{2}}{\epsilon}+C_{2}\theta\right)\sum_{t=1}^{T}\frac{1}{t}+\frac{4L(1-\delta_{x})DG\alpha\sqrt{T}}{\sqrt{\epsilon
C_{1}}(1-\sqrt{\gamma})}-\frac{1-\beta}{2}\mathbb{E}[\sum_{t=1}^{T}\|\nabla
f(Q_{x}(x_{t}))\|_{\hat{\eta}_{t}}^{2}],$

where

$\begin{split}C_{2}&=\frac{5\alpha
G^{3}(1-\beta)}{2\epsilon\sqrt{\theta}}\left(\frac{\beta}{(1-\beta)\sqrt{\theta_{1}C_{1}(1-\gamma)}}+1\right)^{2}+\frac{5\alpha
G^{3}}{2\epsilon\sqrt{\theta}}+\frac{5\beta^{2}\alpha
d\sqrt{\epsilon}}{2\sqrt{\theta}(1-\beta)\theta_{1}C_{1}(1-\gamma)}\\\
&+\frac{5\alpha\sqrt{G^{2}+\epsilon}G^{2}\beta^{2}}{2(1-\beta)\sqrt{\theta}\theta_{1}C_{1}(1-\gamma)\epsilon}+\frac{5\alpha\sqrt{G^{2}+\epsilon}\beta^{2}d}{2(1-\beta)\sqrt{\theta}\theta_{1}C_{1}(1-\gamma)}.\end{split}$

###### Proof.

Denoting the same notations
$A^{1}_{t},A^{2}_{t},A^{3}_{t},A^{4}_{t},A^{5}_{t}$ in Lemma 6, we have

$\begin{split}\mathbb{E}\langle\nabla
f(x_{t}),\Delta_{t}\rangle&=\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}\mathbb{E}\langle\nabla
f(x_{t}),\Delta_{t-1}\rangle+\mathbb{E}\langle\nabla
f(x_{t}),\Delta_{t}-\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t}}\Delta_{t-1}\rangle\\\
&=\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(x_{t-1}),\Delta_{t-1}\rangle+\mathbb{E}\langle\nabla f(x_{t})-\nabla
f(x_{t-1}),\Delta_{t-1}\rangle)\\\ &+\mathbb{E}\langle\nabla
f(x_{t}),-(1-\beta)\hat{\eta}_{t}g_{t}\rangle+\mathbb{E}\langle\nabla
f(x_{t}),A^{1}_{t}\rangle+\mathbb{E}\langle\nabla f(x_{t}),A^{2}_{t}\rangle\\\
&+\mathbb{E}\langle\nabla f(x_{t}),A^{3}_{t}\rangle+\mathbb{E}\langle\nabla
f(x_{t}),A^{4}_{t}\rangle+\mathbb{E}\langle\nabla
f(x_{t}),A^{5}_{t}\rangle.\end{split}$ (11)

For the first term in Eq. (11), we have

$\begin{split}&\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(Q_{x}(x_{t-1})),\Delta_{t-1}\rangle+\mathbb{E}\langle\nabla
f(Q_{x}(x_{t}))-\nabla f(Q_{x}(x_{t-1})),\Delta_{t-1}\rangle)\\\
&\leq\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(Q_{x}(x_{t-1})),\Delta_{t-1}\rangle+\mathbb{E}[L\|Q_{x}(x_{t})-Q_{x}(x_{t-1})\|\|\Delta_{t-1}\|])\\\
&\leq\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(Q_{x}(x_{t-1})),\Delta_{t-1}\rangle+\mathbb{E}[L(\|Q_{x}(x_{t})-x_{t}\|+\|x_{t}-x_{t-1}\|+\|Q_{x}(x_{t-1})-x_{t-1}\|)\|\Delta_{t-1}\|])\\\
&\leq\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(Q_{x}(x_{t-1})),\Delta_{t-1}\rangle+L\mathbb{E}[\|\Delta_{t-1}\|^{2}]+2L(1-\delta_{x})D\mathbb{E}[\|\Delta_{t-1}\|]\\\
&=\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}M_{t-1}.\end{split}$

The rest six parts remain the same as Lemma 6. Then we have

$\begin{split}\mathbb{E}\langle\nabla
f(x_{t}),\Delta_{t}\rangle\leq\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}M_{t-1}+C_{2}(1-\theta_{t})-\frac{1-\beta}{2}\mathbb{E}[\|\nabla
f(x_{t})\|^{2}_{\hat{\eta}_{t}}],\end{split}$

where $C_{2}=\frac{5\alpha
G^{3}(1-\beta)}{2\epsilon\sqrt{\theta}}\left(\frac{\beta}{(1-\beta)\sqrt{\theta_{1}C_{1}(1-\gamma)}}+1\right)^{2}+\frac{5\alpha
G^{3}}{2\epsilon\sqrt{\theta}}+\frac{5\beta^{2}\alpha
d\sqrt{\epsilon}}{2\sqrt{\theta}(1-\beta)\theta_{1}C_{1}(1-\gamma)}+\frac{5\alpha\sqrt{G^{2}+\epsilon}G^{2}\beta^{2}}{2(1-\beta)\sqrt{\theta}\theta_{1}C_{1}(1-\gamma)\epsilon}+\frac{5\alpha\sqrt{G^{2}+\epsilon}\beta^{2}d}{2(1-\beta)\sqrt{\theta}\theta_{1}C_{1}(1-\gamma)}$.

Define
$N_{t}=L\mathbb{E}[\|\Delta_{t-1}\|^{2}]+2L(1-\delta_{x})D\mathbb{E}[\|\Delta_{t-1}\|]+C_{2}(1-\theta_{t})$.
By applying the same induction in Lemma 6, we have

$\begin{split}\sum_{t=1}^{T}M_{t}&\leq\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\sum_{t=1}^{T}N_{t}-\frac{1-\beta}{2}\mathbb{E}[\sum_{t=1}^{T}\|\nabla
f(Q_{x}(x_{t}))\|_{\hat{\eta}_{t}}^{2}]\\\
&=\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{LG^{2}\alpha^{2}}{\epsilon}+C_{2}\theta\right)\sum_{t=1}^{T}\frac{1}{t}+\frac{4L(1-\delta_{x})DG\alpha\sqrt{T}}{\sqrt{\epsilon
C_{1}}(1-\sqrt{\gamma})}-\frac{1-\beta}{2}\mathbb{E}[\sum_{t=1}^{T}\|\nabla
f(Q_{x}(x_{t}))\|_{\hat{\eta}_{t}}^{2}].\end{split}$

Hence, we obtain the desired result. ∎

###### Proof of Theorem 2.

By the Lipschitz continuity of the gradient, we have

$\begin{split}f(x_{t+1})&\leq f(x_{t})+\langle\nabla
f(x_{t}),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}\|^{2}\\\
&=f(x_{t})+\langle\nabla
f(Q_{x}(x_{t})),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}\|^{2}+\langle\nabla
f(x_{t})-\nabla f(Q_{x}(x_{t})),\Delta_{t}\rangle\\\ &\leq
f(x_{t})+\langle\nabla
f(Q_{x}(x_{t})),\Delta_{t}\rangle+\frac{L}{2}\|\Delta_{t}\|^{2}+L(1-\delta_{x})D\|\Delta_{t}\|.\end{split}$

Let $M_{t}=\mathbb{E}[\langle\nabla
f(Q_{t}(x_{t})),\Delta_{t}\rangle+L\|\Delta_{t}\|^{2}+2L(1-\delta_{x})D\|\Delta_{t}\|]$.
Then we have

$\begin{split}f^{*}&\leq E[f(x_{T+1})]\leq f(x_{1})+\sum_{t=1}^{T}M_{t}\\\
&\leq
f(x_{1})+.\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{LG^{2}\alpha^{2}}{\epsilon}+C_{2}\theta\right)\sum_{t=1}^{T}\frac{1}{t}+\frac{4L(1-\delta_{x})DG\alpha\sqrt{T}}{\sqrt{\epsilon
C_{1}}(1-\sqrt{\gamma})}-\frac{1-\beta}{2}\mathbb{E}[\sum_{t=1}^{T}\|\nabla
f(Q_{x}(x_{t}))\|_{\hat{\eta}_{t}}^{2}].\end{split}$

Arranging the corresponding terms suitably, we obtain

$\begin{split}(\mathbb{E}[\|\nabla
f(Q_{x}(x_{\tau}^{T}))\|^{2}])&\leq\frac{\sqrt{G^{2}+\epsilon
d}}{\alpha\sqrt{T}}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(Q(x_{t}))\|_{\hat{\eta}_{t}}^{2}\right]\\\ &\leq\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha\sqrt{T}}\left(f(x_{1})-f^{*}+\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{LG^{2}\alpha^{2}}{\epsilon}+C_{2}\theta\right)\sum_{t=1}^{T}\frac{1}{t}+\frac{4L(1-\delta_{x})DG\alpha\sqrt{T}}{\sqrt{\epsilon
C_{1}}(1-\sqrt{\gamma})}\right)\\\
&=\frac{C_{5}+C_{6}\sum_{t=1}^{T}\frac{1}{t}}{\sqrt{T}}+C_{7},\end{split}$

where $C_{5}$, $C_{6}$, and $C_{7}$ are defined as
$C_{5}=\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha}(f(x_{1})-f^{*}),C_{6}=\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{LG^{2}\alpha^{2}}{\epsilon}+C_{2}\theta\right),\text{
and }C_{7}=\frac{8(1-\delta_{x})\sqrt{G^{2}+\epsilon
d}LDG}{(1-\beta)\sqrt{\epsilon C_{1}}(1-\sqrt{\gamma})}$, respectively. Hence,
the proof is completed. ∎

######  Corollary 2.

For given precision $\xi$, to achieve $\mathbb{E}[\|\nabla
f(Q_{x}(x_{\tau}^{T}))\|^{2}]\leq C_{7}^{\prime}+\xi$, we have
$T=O\left(\frac{1}{\xi^{2}}\right)$, where
$C_{7}^{\prime}=\frac{4(1-\delta_{x})\sqrt{G^{2}+\epsilon
d}LDG}{(1-\beta)\sqrt{\epsilon C_{1}}(1-\sqrt{\gamma})}$.

###### Proof.

For a fixed iteration $T$, let $\alpha_{t}=\frac{\alpha}{\sqrt{T}}$ and
$\theta_{t}=1-\frac{\theta}{T}$.

It is not hard to check that Lemma 7 updates to
$\sum_{t=1}^{T}\|\Delta_{t}\|\leq\frac{\alpha G\sqrt{T}}{\sqrt{\epsilon}}$,
and Lemma 8 updates to

$\sum_{t=1}^{T}M_{t}\leq\frac{LG^{2}\alpha^{2}}{\sqrt{C_{1}}(1-\sqrt{\gamma})\epsilon}+\frac{C_{2}\theta}{\sqrt{C_{1}}(1-\sqrt{\gamma})}+\frac{2L(1-\delta_{x})DG\alpha\sqrt{T}}{\sqrt{\epsilon
C_{1}}(1-\sqrt{\gamma})}-\frac{1-\beta}{2}\mathbb{E}[\sum_{t=1}^{T}\|\nabla
f(Q_{x}(x_{t}))\|_{\hat{\eta}_{t}}^{2}].$

Then, we have

$\begin{split}(\mathbb{E}[\|\nabla
f(Q_{x}(x_{\tau}^{T}))\|^{2}])&\leq\frac{\sqrt{G^{2}+\epsilon
d}}{\alpha\sqrt{T}}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(Q(x_{t}))\|_{\hat{\eta}_{t}}^{2}\right]\\\ &\leq\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha\sqrt{T}}\left(f(x_{1})-f^{*}+\frac{LG^{2}\alpha^{2}}{\sqrt{C_{1}}(1-\sqrt{\gamma})\epsilon}+\frac{C_{2}\theta}{\sqrt{C_{1}}(1-\sqrt{\gamma})}+\frac{2L(1-\delta_{x})DG\alpha\sqrt{T}}{\sqrt{\epsilon
C_{1}}(1-\sqrt{\gamma})}\right)\\\
&=\frac{C_{5}^{\prime}}{\sqrt{T}}+C_{7}^{\prime},\end{split}$

where

$\begin{split}C_{5}^{\prime}&=\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha}\left(f(x_{1})-f^{*}+\frac{LG^{2}\alpha^{2}}{\sqrt{C_{1}}(1-\sqrt{\gamma})\epsilon}+\frac{C_{2}\theta}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\right),\\\
C_{7}^{\prime}&=\frac{4(1-\delta_{x})\sqrt{G^{2}+\epsilon
d}LDG}{(1-\beta)\sqrt{\epsilon C_{1}}(1-\sqrt{\gamma})}.\end{split}$

Hence, by bounding $\frac{C_{5}^{\prime}}{\sqrt{T}}+C_{7}^{\prime}\leq
C_{7}^{\prime}+\xi$, we obtain the desired result. ∎

##  Appendix C Proof of Theorem 3

To prove Theorem 3, we first denote a few notations and provide several useful
lemmas.

######  Notation 3.

Let $\mathbb{E}_{t}[\cdot]$ be the conditional expectation with respect to
$x_{t}$ conditioned on $\\{x_{t-1},x_{t-2},\cdots,x_{1}\\}$. Denote
${\sigma_{t}^{(i)}}^{2}=\mathbb{E}_{t}[{g_{t}^{(i)}}^{2}]$,
$\hat{v}^{(i)}_{t}=\theta_{t}v^{(i)}_{t-1}+(1-\theta_{t}){\sigma^{(i)}_{t}}^{2}$,
$\hat{\eta}^{(i)}_{t}=\alpha_{t}/\sqrt{\hat{v}^{(i)}_{t}+\epsilon}$,
$\Delta_{t}^{(i)}=-\alpha_{t}m_{t}^{(i)}/\sqrt{v_{t}^{(i)}+\epsilon}$,
$\hat{\Delta}_{i}=\frac{1}{N}\sum_{i=1}^{N}\Delta_{t}^{(i)}$, and
$M_{t}=\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\langle\nabla
f(\hat{x}_{t}),\Delta_{t}^{(i)}\rangle+\frac{1}{N^{2}}L(2-\delta_{g})\sum_{i=1}^{N}\sum_{j=1}^{N}\mathbb{E}\|\Delta_{t}^{(i)}\|\|\Delta_{t}^{(j)}\|+\frac{1}{N^{2}}L(2-\delta_{g})\sum_{i=1}^{N}\sum_{j=1}^{N}\mathbb{E}\|\Delta_{t}^{(i)}\|\|e_{t}^{(j)}\|+\frac{1}{N}2LD\sum_{i=1}^{N}\mathbb{E}\|\Delta_{t}^{(i)}\|$.
In addition, let $\tilde{x}_{t}=x_{t}-\frac{1}{N}\sum_{i=1}^{N}e_{t}^{(i)}$.
Then

$\displaystyle\tilde{x}_{t+1}$
$\displaystyle=x_{t}-\frac{1}{N}\sum_{i=1}^{N}Q_{g}(-\Delta_{t}^{(i)}+e_{t}^{(i)})-\frac{1}{N}\sum_{i=1}^{N}e_{t+1}^{(i)}=x_{t}+\frac{1}{N}\sum_{i=1}^{N}\Delta_{t}^{(i)}-\frac{1}{N}\sum_{i=1}^{N}e_{t}=\tilde{x}_{t}+\frac{1}{N}\sum_{i=1}^{N}\Delta_{t}^{(i)}.$

######  Lemma 9.

By using Notation 3, we derive an upper estimation for $\hat{\Delta}_{t}$ as
follows:

$\sum_{t=1}^{T}\|\hat{\Delta}_{t}\|^{2}\leq\frac{G^{2}}{\epsilon}\sum_{t=1}^{T}\frac{\alpha^{2}}{t}.$

###### Proof.

By using the definition of $\hat{\Delta}_{t}$, it is not hard to check that
the following equations hold:

$\sum_{t=1}^{T}\|\hat{\Delta}_{t}\|^{2}=\sum_{t=1}^{T}\|\frac{1}{N}\sum_{i=1}^{N}\Delta_{t}^{(i)}\|^{2}\leq\sum_{t=1}^{T}\frac{1}{N}\sum_{i=1}^{N}\|\Delta_{t}^{(i)}\|^{2}=\frac{1}{N}\sum_{i=1}^{N}\sum_{t=1}^{T}\|\Delta_{t}^{(i)}\|^{2}\leq\frac{G^{2}}{\epsilon}\sum_{t=1}^{T}\frac{\alpha^{2}}{t}.$

∎

######  Lemma 10.

Let $e_{i}$ be the noisy term defined in Algorithm2 and $\hat{\Delta}_{t}$ be
the term defined in Notation (3). Then it holds that

$\mathbb{E}\left[\frac{1}{N^{2}}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{j=1}^{N}\|e_{t}^{(i)}\|\|\Delta_{t}^{(j)}\|\right]\leq\frac{1-\delta_{g}}{\delta_{g}N}\sum_{i=1}^{N}\mathbb{E}\left[\sum_{t=1}^{T}\|\Delta_{t}^{(i)}\|^{2}\right].$

###### Proof.

Using the definition of the noisy term $e_{t}$, the following holds:

$\|e^{(j)}_{t}\|=\|\Delta_{t}^{(j)}+e_{t-1}^{(j)}-Q_{g}(\Delta_{t}^{(j)}+e_{t-1}^{(j)})\|\leq(1-\delta_{g})(\|\Delta_{t}^{(j)}\|+\|e_{t-1}^{(j)}\|)\leq\sum_{k=1}^{t}(1-\delta_{g})^{t-k+1}\|\Delta_{k}^{(j)}\|.$

Because each worker works independently, we have
$\frac{1}{N}\mathbb{E}\left[\sum_{j=1}^{N}\|\Delta_{t_{1}}^{(i)}\|\|\Delta_{t_{2}}^{(j)}\|\right]=\mathbb{E}[\|\Delta_{t_{1}}^{(i)}\|\|\Delta_{t_{2}}^{(i)}\|]$
for $t_{1}\neq t_{2}$. In addition, because
$\mathbb{E}[X^{2}]\geq\mathbb{E}[X]^{2}$, we have
$\frac{1}{N}\mathbb{E}\left[\sum_{j=1}^{N}\|\Delta_{t_{1}}^{(i)}\|\|\Delta_{t_{1}}^{(j)}\|\right]\leq\mathbb{E}[\|\Delta_{t_{1}}^{(i)}\|^{2}]$.
Then, we have

$\begin{split}\mathbb{E}\left[\frac{1}{N^{2}}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{j=1}^{N}\|e_{t}^{(i)}\|\|\Delta_{t}^{(j)}\|\right]&\leq\mathbb{E}\left[\frac{1}{N^{2}}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{j=1}^{N}\sum_{k=1}^{t}(1-\delta_{g})^{t-k+1}\|\Delta_{k}^{(i)}\|\|\Delta_{t}^{(j)}\|\right]\\\
&\leq\mathbb{E}\left[\frac{1}{N}\sum_{t=1}^{T}\sum_{k=1}^{t}\sum_{i=1}^{N}(1-\delta_{g})^{t-k+1}\|\Delta_{k}^{(i)}\|\|\Delta_{t}^{(i)}\|\right]\\\
&\leq\frac{1-\delta_{g}}{\delta_{g}N}\sum_{t=1}^{T}\sum_{i=1}^{N}\|\Delta_{t}^{(i)}\|^{2},\end{split}$

where the last inequality can be proven by Lemma 5. Hence, the proof is
completed. ∎

######  Lemma 11.

Let $\tau$ be randomly chosen from $\\{1,2,\cdots,T\\}$ with equal
probabilities $p_{\tau}=\frac{1}{T}$. We have the following estimate:

$\mathbb{E}[\|\nabla f(\hat{x}_{\tau})\|^{2}]\leq\frac{\sqrt{G^{2}+\epsilon
d}}{\alpha\sqrt{T}N}\sum_{i=1}^{N}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f((\hat{x}_{t}))\|_{\hat{\eta_{t}}^{(i)}}^{2}\right].$

###### Proof.

By Lemma 3, $\mathbb{E}[\|\nabla
f(\hat{x}_{\tau})\|^{2}]\leq\frac{\sqrt{G^{2}+\epsilon
d}}{\alpha\sqrt{T}}\mathbb{E}[\sum_{t=1}^{T}\|\nabla
f(\hat{x}_{t})\|_{\hat{\eta_{t}}^{(i)}}^{2}$ holds for any $i$. Hence, the
proof is finished. ∎

######  Lemma 12.

By the definition of $M_{t}$, we obtain its upper-estimation as follows:

$\sum_{t=1}^{T}M_{t}\leq\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\left(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta\right)\sum_{t=1}^{T}\frac{1}{t}+\frac{4(1-\delta_{x})LDG\alpha\sqrt{T}}{\sqrt{\epsilon}}\right)-\frac{1-\beta}{2N}\sum_{i=1}^{N}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(\hat{x}_{t})\|^{2}_{\hat{\eta}_{t}^{(i)}}\right].$

###### Proof.

Based on the similar proof of
$\Delta_{t}-\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t}}\Delta_{t-1}$
in Lemma 6, we define

$\displaystyle(A^{1}_{t})^{(i)}=\hat{\eta}_{t}^{(i)}g_{t}^{(i)}\frac{(1-\theta_{t})g_{t}^{(i)}}{\sqrt{v_{t}^{(i)}+\epsilon}}\left(\frac{\beta
m_{t-1}^{(i)}}{\sqrt{v_{t}^{(i)}+\epsilon}+\sqrt{\theta_{t}v_{t-1}^{(i)}+\theta_{t}\epsilon}}+\frac{(1-\beta)g_{t}^{(i)}}{\sqrt{v_{t}^{(i)}+\epsilon}+\sqrt{\hat{v}_{t}^{(i)}}+\epsilon}\right),$
$\displaystyle(A^{2}_{t})^{(i)}=-\hat{\eta}_{t}^{(i)}\sigma_{t}^{(i)}\frac{(1-\theta_{t})g_{t}^{(i)}}{\sqrt{v_{t}^{(i)}+\epsilon}}\frac{(1-\beta)\sigma_{t}^{(i)}}{\sqrt{v_{t}^{(i)}+\epsilon}+\sqrt{\hat{v}^{(i)}_{t}+\epsilon}},$
$\displaystyle(A^{3}_{t})^{(i)}=\hat{\eta}_{t}^{(i)}\epsilon\frac{(1-\theta_{t})}{\sqrt{v_{t}^{(i)}+\epsilon}}\frac{\beta
m_{t-1}^{(i)}}{\sqrt{v_{t}^{(i)}+\epsilon}+\sqrt{\theta_{t}v_{t-1}^{(i)}+\theta_{t}\epsilon}},$
$\displaystyle(A^{4}_{t})^{(i)}=\hat{\eta}_{t}^{(i)}\sqrt{{\sigma_{t}^{(i)}}^{2}+\epsilon}\frac{(1-\theta_{t})g_{t}^{(i)}}{\sqrt{v_{t}^{(i)}+\epsilon}}\frac{\beta
m_{t-1}^{(i)}}{\sqrt{\theta_{t}v_{t-1}^{(i)}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}g_{t}^{(i)}}{\sqrt{v_{t}^{(i)}+\epsilon}+\sqrt{\theta_{t}v_{t-1}^{(i)}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{{\sigma_{t}^{(i)}}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}^{(i)}+\epsilon}+\sqrt{\theta_{t}v_{t-1}^{(i)}+\theta_{t}\epsilon}},$
$\displaystyle(A^{5}_{t})^{(i)}=\hat{\eta}_{t}^{(i)}\sqrt{{\sigma_{t}^{(i)}}^{2}+\epsilon}\frac{(1-\theta_{t})\sqrt{\epsilon}}{\sqrt{v_{t}^{(i)}+\epsilon}}\frac{\beta
m_{t-1}}{\sqrt{\theta_{t}v_{t-1}^{(i)}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{\epsilon}}{\sqrt{v_{t}^{(i)}+\epsilon}+\sqrt{\theta_{t}v_{t-1}^{(i)}+\theta_{t}\epsilon}}\frac{\sqrt{1-\theta_{t}}\sqrt{{\sigma_{t}^{(i)}}^{2}+\epsilon}}{\sqrt{\hat{v}_{t}^{(i)}+\epsilon}+\sqrt{\theta_{t}v_{t-1}^{(i)}+\theta_{t}\epsilon}}.$

Then, via the same proof as Lemma 6, the following equation holds

$\begin{split}\mathbb{E}\langle\nabla
f(\hat{x}_{t}),\hat{\Delta}_{t}\rangle&=\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\langle\nabla
f(\hat{x}_{t}),\Delta_{t}^{(i)}\rangle\\\
&=\frac{1}{N}\sum_{i=1}^{N}\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}\mathbb{E}\langle\nabla
f(\hat{x}_{t}),\Delta_{t-1}^{(i)}\rangle+\mathbb{E}\langle\nabla
f(\hat{x}_{t}),\Delta_{t}^{(i)}-\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t}}\Delta_{t-1}^{(i)}\rangle\\\
&=\frac{1}{N}\sum_{i=1}^{N}\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(\hat{x}_{t-1}),\Delta_{t-1}^{(i)}\rangle+\mathbb{E}\langle\nabla
f(\hat{x}_{t})-\nabla f(\hat{x}_{t-1}),\Delta_{t-1}^{(i)}\rangle)\\\
&\qquad+\mathbb{E}\langle\nabla
f(\hat{x}_{t}),-(1-\beta)\hat{\eta}_{t}^{(i)}g_{t}^{(i)}\rangle+\mathbb{E}\langle\nabla
f(\hat{x}_{t}^{(i)}),(A^{1}_{t})^{(i)}\rangle+\mathbb{E}\langle\nabla
f(\hat{x}_{t}^{(i)}),(A^{2}_{t})^{(i)}\rangle\\\
&\qquad+\mathbb{E}\langle\nabla
f(\hat{x}_{t}^{(i)}),(A^{3}_{t})^{(i)}\rangle+\mathbb{E}\langle\nabla
f(\hat{x}_{t}^{(i)}),(A^{4}_{t})^{(i)}\rangle+\mathbb{E}\langle\nabla
f(\hat{x}_{t}^{(i)}),(A^{5}_{t})^{(i)}\rangle.\end{split}$ (12)

For the first term in Eq. (12), it holds that

$\displaystyle\frac{1}{N}\sum_{i=1}^{N}\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(\hat{x}_{t-1}),\Delta_{t-1}^{(i)}\rangle+\mathbb{E}\langle\nabla
f(\hat{x}_{t})-\nabla f(\hat{x}_{t-1}),\Delta_{t-1}^{(i)}\rangle)$ (13)
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(\hat{x}_{t-1}),\Delta_{t-1}^{(i)}\rangle+L\mathbb{E}\|\hat{x}_{t}-\hat{x}_{t-1}\|\|\Delta_{t-1}^{(i)}\|)$
(14)
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(\hat{x}_{t-1}),\Delta_{t-1}^{(i)}\rangle+L\mathbb{E}\|x_{t}-x_{t-1}\|\|\Delta_{t-1}^{(i)}\|+2(1-\delta_{x})LD\mathbb{E}\|\Delta_{t-1}^{(i)}\|)$
(15)
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\mathbb{E}\langle\nabla
f(\hat{x}_{t-1}),\Delta_{t-1}^{(i)}\rangle+L\mathbb{E}\|\frac{1}{N}\sum_{j=1}^{N}Q_{g}(\Delta_{t}^{(j)}+e_{t}^{(j)})\|\|\Delta_{t-1}^{(i)}\|+2(1-\delta_{x})LD\mathbb{E}\|\Delta_{t-1}^{(i)}\|)$
(16)
$\displaystyle\leq\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}(\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\langle\nabla
f(\hat{x}_{t-1}),\Delta_{t-1}^{(i)}\rangle+\frac{1}{N^{2}}L(2-\delta_{g})\sum_{i=1}^{N}\sum_{j=1}^{N}\mathbb{E}\|\Delta_{t-1}^{(i)}\|\|\Delta_{t-1}^{(j)}\|$
(17)
$\displaystyle\qquad+\frac{1}{N^{2}}L(2-\delta_{g})\sum_{i=1}^{N}\sum_{j=1}^{N}\mathbb{E}\|\Delta_{t-1}^{(i)}\|\|e_{t-1}^{(j)}\|+\frac{1}{N}2(1-\delta_{x})LD\sum_{i=1}^{N}\mathbb{E}\|\Delta_{t-1}^{(i)}\|)$
(18)
$\displaystyle=\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}M_{t-1}.$
(19)

The remain 6 terms are the same as Lemma 6. Thus, we have

$\begin{split}\mathbb{E}\langle\nabla
f(\hat{x}_{t}),\hat{\Delta_{t}}\rangle\leq\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}M_{t-1}+C_{2}(1-\theta_{t})-\frac{1}{N}\sum_{i=1}^{N}\frac{1-\beta}{2}\mathbb{E}[\|\nabla
f(\hat{x}_{t})\|^{2}_{\hat{\eta}_{t}^{i)}}].\end{split}$

Let
$N_{t}=\frac{1}{N^{2}}L(2-\delta_{g})\sum_{i=1}^{N}\sum_{j=1}^{N}\mathbb{E}\|\Delta_{t}^{(i)}\|\|\Delta_{t}^{(j)}\|+\frac{1}{N^{2}}L(2-\delta_{g})\sum_{i=1}^{N}\sum_{j=1}^{N}\mathbb{E}\|\Delta_{t}^{(i)}\|\|e_{t}^{(j)}\|+\frac{1}{N}2LD\sum_{i=1}^{N}\mathbb{E}\|\Delta_{t}^{(i)}\|+C_{2}(1-\theta_{t})$.
Similarly, we can acquire

$\begin{split}\sum_{t=1}^{T}M_{t}&\leq\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\sum_{t=1}^{T}N_{t}-\frac{1-\beta}{2N}\mathbb{E}[\sum_{t=1}^{T}\sum_{i=1}^{N}\|\nabla
f(\hat{x}_{t})\|^{2}_{\hat{\eta}_{t}^{(i)}}]\\\
&=\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left\\{\frac{1}{N^{2}}L(2-\delta_{g})\sum_{i=1}^{N}\sum_{j=1}^{N}\mathbb{E}\|\Delta_{t}^{(i)}\|\|\Delta_{t}^{(j)}\|+\frac{1}{N^{2}}L(2-\delta_{g})\sum_{i=1}^{N}\sum_{j=1}^{N}\mathbb{E}\|\Delta_{t}^{(i)}\|\|e_{t}^{(j)}\|\right.\\\
&\qquad\left.+\frac{1}{N}2(1-\delta_{x})LD\sum_{i=1}^{N}\mathbb{E}\|\Delta_{t}^{(i)}\|+C_{2}(1-\theta_{t})\right\\}-\frac{1-\beta}{2N}\sum_{i=1}^{N}\mathbb{E}[\sum_{t=1}^{T}\|\nabla
f(\hat{x}_{t})\|^{2}_{\hat{\eta}_{t}^{(i)}}]\\\
&\leq\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left\\{\sum_{t=1}^{T}\frac{1}{N}L(2-\delta_{g})\sum_{i=1}^{N}\mathbb{E}\|\Delta_{t}^{(i)}\|^{2}+\frac{1-\delta_{g}}{\delta_{g}N}L(2-\delta_{g})\sum_{i=1}^{N}\mathbb{E}\|\Delta_{t}^{(i)}\|^{2}\right.\\\
&\qquad\left.\frac{2(1-\delta_{x})LD}{N}\sum_{i=1}^{N}\|\Delta_{t}^{(i)}\|+C_{2}(1-\theta_{t})\right\\}-\frac{1-\beta}{2N}\sum_{i=1}^{N}\mathbb{E}[\sum_{t=1}^{T}\|\nabla
f(\hat{x}_{t})\|^{2}_{\hat{\eta}_{t}^{(i)}}]\\\
&\leq\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\left(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta\right)\sum_{t=1}^{T}\frac{1}{t}+\frac{4(1-\delta_{x})LDG\alpha\sqrt{T}}{\sqrt{\epsilon}}\right)-\frac{1-\beta}{2N}\sum_{i=1}^{N}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(\hat{x}_{t})\|^{2}_{\hat{\eta}_{t}^{(i)}}\right].\end{split}$

Hence, the proof is completed. ∎

###### Proof of Theorem 3.

By using the gradient Lipschitz continuity of $f$, it holds that

$\begin{split}\mathbb{E}f(\tilde{x}_{t+1})&\leq\mathbb{E}(f(\tilde{x}_{t})+\langle\nabla
f(\tilde{x}_{t}),\hat{\Delta}_{t}\rangle+\frac{L}{2}\|\hat{\Delta}_{t}\|^{2})\\\
&=\mathbb{E}\left[f(\tilde{x}_{t})+\langle\nabla
f(\hat{x}_{t}),\hat{\Delta}_{t}\rangle+\frac{L}{2}\|\hat{\Delta}_{t}\|^{2}+\langle\nabla
f(x_{t})-\nabla f(\hat{x}_{t})),\hat{\Delta}_{t}\rangle+\langle\nabla
f(\tilde{x}_{t})-\nabla f(x_{t}),\hat{\Delta}_{t}\rangle\right]\\\
&\leq\mathbb{E}\left[f(\tilde{x}_{t})+\frac{1}{N}\sum_{i=1}^{N}\langle\nabla
f(\hat{x}_{t}),\Delta_{t}^{(i)}\rangle+\frac{L}{2N^{2}}\sum_{i=1}^{N}\sum_{j=1}^{N}\|\Delta_{t}^{(i)}\|\|\Delta_{t}^{(j)}\|\right]\\\
&\qquad+\mathbb{E}\left[\frac{1}{N}(1-\delta_{x})LD\sum_{i=1}^{N}\|\Delta_{t}^{(i)}\|+\frac{L}{N^{2}}\sum_{i=1}^{N}\|e_{t}^{(i)}\|\|\Delta_{t}^{(j)}\|\right]\\\
&\leq\mathbb{E}f(\tilde{x}_{t})+M_{t}.\end{split}$

Taking summation over both sides of the above inequality, it holds that

$\begin{split}f^{*}&\leq\mathbb{E}f(\tilde{x}_{T+1})\leq
f(x_{1})+\sum_{t=1}^{T}M_{t}\\\ &\leq
f(x_{1})+\leq\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\left(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta\right)\sum_{t=1}^{T}\frac{1}{t}+\frac{4(1-\delta_{x})LDG\alpha\sqrt{T}}{\sqrt{\epsilon}}\right)-\frac{1-\beta}{2N}\sum_{i=1}^{N}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(\hat{x}_{t})\|^{2}_{\hat{\eta}_{t}^{(i)}}\right].\end{split}$

Arranging the terms, it holds that

$\begin{split}\mathbb{E}[\|\nabla
f(\hat{x}_{\tau})\|^{2}]&\leq\frac{\sqrt{G^{2}+\epsilon
d}}{\alpha\sqrt{T}N}\sum_{i=1}^{N}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f((\hat{x}_{t}))\|_{\hat{\eta_{t}}^{(i)}}^{2}\right],\\\
&\leq\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha\sqrt{T}}\left\\{f(x_{1})-f^{*}+\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\left(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta\right)\sum_{t=1}^{T}\frac{1}{t}+\frac{4(1-\delta_{x})LDG\alpha\sqrt{T}}{\sqrt{\epsilon}}\right)\right\\},\\\
&=\frac{C_{8}+C_{9}\sum_{t=1}^{T}\frac{1}{t}}{\sqrt{T}}+C_{10},\end{split}$

where $C_{8}$, $C_{9}$, and $C_{10}$ are defined as follows

$\begin{split}C_{8}&=\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha}(f(x_{1})-f^{*})\\\ C_{9}&=\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta\right)\\\
C_{10}&=\frac{8\sqrt{G^{2}+\epsilon
d}(1-\delta_{x})LDG}{\sqrt{C_{1}}(1-\sqrt{\gamma})\sqrt{\epsilon}(1-\beta)},\end{split}$

respectively. Hence, the proof is completed. ∎

######  Corollary 3.

For given precision $\xi$, to achieve $\mathbb{E}[\|\nabla
f(\hat{x}_{\tau}^{T}))\|^{2}]\leq C_{10}^{\prime}+\xi$, we have
$T=O\left(\frac{1}{\xi^{2}}\right)$, where
$C_{10}^{\prime}=\frac{4\sqrt{G^{2}+\epsilon
d}(1-\delta_{x})LDG}{\sqrt{C_{1}}(1-\sqrt{\gamma})\sqrt{\epsilon}(1-\beta)}$.

###### Proof.

For a fixed iteration $T$, let $\alpha_{t}=\frac{\alpha}{\sqrt{T}}$ and
$\theta_{t}=1-\frac{\theta}{T}$.

Lemma 12 updates to

$\sum_{t=1}^{T}M_{t}\leq\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta+\frac{2(1-\delta_{x})LDG\alpha\sqrt{T}}{\sqrt{\epsilon}}\right)-\frac{1-\beta}{2N}\sum_{i=1}^{N}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f(\hat{x}_{t})\|^{2}_{\hat{\eta}_{t}^{(i)}}\right].$

Then, we have

$\begin{split}\mathbb{E}[\|\nabla
f(\hat{x}_{\tau})\|^{2}]&\leq\frac{\sqrt{G^{2}+\epsilon
d}}{\alpha\sqrt{T}N}\sum_{i=1}^{N}\mathbb{E}\left[\sum_{t=1}^{T}\|\nabla
f((\hat{x}_{t}))\|_{\hat{\eta_{t}}^{(i)}}^{2}\right]\\\
&\leq\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha\sqrt{T}}\left\\{f(x_{1})-f^{*}+\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta+\frac{2(1-\delta_{x})LDG\alpha\sqrt{T}}{\sqrt{\epsilon}}\right)\right\\}\\\
&=\frac{C_{8}^{\prime}}{\sqrt{T}}+C_{10}^{\prime},\end{split}$

where

$\begin{split}C_{8}^{\prime}&=\frac{2\sqrt{G^{2}+\epsilon
d}}{(1-\beta)\alpha}\left(f(x_{1})-f^{*}+\frac{1}{\sqrt{C_{1}}(1-\sqrt{\gamma})}\left(\frac{L(2-\delta_{g})G^{2}\alpha^{2}}{\epsilon\delta_{g}}+C_{2}\theta\right)\right),\\\
C_{10}^{\prime}&=\frac{4\sqrt{G^{2}+\epsilon
d}(1-\delta_{x})LDG}{\sqrt{C_{1}}(1-\sqrt{\gamma})\sqrt{\epsilon}(1-\beta)},\end{split}$

Hence, by bounding $\frac{C_{8}^{\prime}}{\sqrt{T}}+C_{10}^{\prime}\leq
C_{10}^{\prime}+\xi$, we obtain the desired result.

∎

##  Appendix D Additional Experimental Results

We follow the same implementation details in Section 4 in the main paper. We
test the proposed algorithm on the dataset CIFAR10 (Krizhevsky et al., 2009)
and the VGG19 network (Simonyan & Zisserman, 2014). The results are plotted in
Fig 5. From the results, it can be shown that the error-feedback technique
helps accelerate the convergence of our algorithm with gradient quantization.
However, in this experiment the networks with weight quantization perform
better than those without weight quantization. This may be because we overcome
the over-fitting issue by considering weight quantization as a regularization
term.

|  |
---|---|---
|  |
Figure 5: Additional Experimental Results: FP represents training without
quantization, and EF represents error-feedback. $k_{x}$ and $k_{g}$ are
defined in Section 4 in the main paper. The left column shows the values of
the loss function during the training process. The middle column shows the
classification accuracy on the test dataset at each training epoch. The right
column shows the zooming-in-version of the accuracy curve.