# Efficient-Adam: Communication-Efficient Distributed Adam

Congliang Chen  Li Shen  Wei Liu  Zhi-Quan Luo  Fellow, IEEE This work is
supported in part by the Major Science and Technology Innovation 2030 “Brain
Science and Brain-like Research” key project (No. 2021ZD0201405), the National
Natural Science Foundation of China (No. 61731018) and the Guangdong
Provincial Key Laboratory of Big Data Computing.Congliang Chen is with the
Chinese University of Hong Kong (Shenzhen), Shenzhen, Guangdong, China
(e-mail: congliangchen@link.cuhk.edu.cn). Li Shen is with JD Explore Academy,
Beijing, China (e-mail: mathshenli@gmail.com).Wei Liu is with Tencent,
Shenzhen, Guangdong, China (e-mail: wl2223@columbia.edu).Zhi-Quan Luo is with
the Chinese University of Hong Kong (Shenzhen), Shenzhen, Guangdong, China,
and Shenzhen Research Institute of Big Data, Shenzhen, Guangdong, China
(e-mail: luozq@cuhk.edu.cn).

###### Abstract

Distributed adaptive stochastic gradient methods have been widely used for
large-scale nonconvex optimization, such as training deep learning models.
However, their communication complexity on finding $\varepsilon$-stationary
points has rarely been analyzed in the nonconvex setting. In this work, we
present a novel communication-efficient distributed Adam in the parameter-
server model for stochastic nonconvex optimization, dubbed Efficient-Adam.
Specifically, we incorporate a two-way quantization scheme into Efficient-Adam
to reduce the communication cost between the workers and server.
Simultaneously, we adopt a two-way error feedback strategy to reduce the
biases caused by the two-way quantization on both the server and workers,
respectively. In addition, we establish the iteration complexity for the
proposed Efficient-Adam with a class of quantization operators, and further
characterize its communication complexity between the server and workers when
an $\varepsilon$-stationary point is achieved. Finally, we apply Efficient-
Adam to solve a toy stochastic convex optimization problem and train deep
learning models on real-world vision and language tasks. Extensive experiments
together with a theoretical guarantee justify the merits of Efficient Adam.

Communication Reduction, Distributed Optimization, Stochastic Adaptive
Gradient Descent

##  1 Introduction

Let $\mathbb{X}$ be a finite-dimensional linear vector space. We focus on a
stochastic optimization problem:

$\min_{x\in\mathbb{X}}\ F(x)=\mathbb{E}_{\xi\sim\mathbb{P}}[f(x,\xi)],$ (1)

where $F\\!:\mathbb{X}\\!\to\mathbb{R}$ is a proper, lower semi-continuous
smooth function that could be nonconvex, and $\xi$ is a random variable with
an unknown distribution $\mathbb{P}$. Stochastic optimizations commonly appear
in the fields of statistical machine learning [bishop2006pattern], deep
learning [goodfellow2016deep], and reinforcement learning
[sutton2018reinforcement], which include sparse learning
[hastie2015statistical], representation learning [bengio2013representation],
classification [deng2009imagenet], regression, etc.

Due to the existence of expectation over an unknown distribution, the
population risk $\mathbb{E}_{\xi\sim\mathbb{P}}[f(x,\xi)]$ with a complicated
function $F$ is approximated via an empirical risk function
$\frac{1}{n}\sum_{i=1}^{n}[f_{i}(x,\xi_{i})]$ via a large number of samples
$\\{\xi_{i}\\}$. For example, we may use the ImangeNet dataset for the image
classification task [deng2009imagenet], the COCO dataset for the object
detection task [lin2014microsoft], and the GLUE dataset for the natural
language understanding task [wang2018glue], respectively. As all of the above
datasets are large, we have to optimize problem (1) via a large number of
samples. Meanwhile, to learn appropriate distributions for different tasks, it
is hard to design the exact mathematical formulation of $f$. Thus, an
effective way is to set a complicated deep neural network as a surrogate
function with a large number of parameters/FLOPs, making problem (1) an ultra-
large-scale nonconvex stochastic optimization [shen2023efficient].

However, it could be impossible to train a deep neural network with a large
number of parameters over a large-scale dataset within a single machine.
Fortunately, we have some promising approaches to tackle this problem. One of
them is to extend the stochastic gradient descent (SGD) method to a
distributed version [li2014efficient]. Then using the distributed SGD method,
we train a deep learning model with multiple machines in a distributed mode
[goyal2017accurate, you2019large]. However, for the vanilla SGD method, how to
tune a suitable learning rate for different tasks remains challenging. This
dilemma is more serious for distributed SGD methods since there are multiple
learning rates needed to be tuned for multiple machines. Moreover, the
communication overhead is another issue in distributed methods. How to reduce
the communication cost among multiple machines is also challenging. Recently,
Hou et al.[hou2018analysis] proposed a distributed Adam [kingma2014adam] with
weights and gradients being quantized to reduce the communication cost between
the workers and the server. However, their theoretical analysis is merely
restricted to the convex setting, and they didn’t provide the bit-
communication complexity either, which hampers the potential applications. In
addition, both the weights and gradients quantization techniques will
introduce additional errors, which may degrade the performance of the vanilla
Adam optimizer. On the other hand, distributed Adam has already been built in
several deep learning platforms, such as PyTorch [paszke2019pytorch],
TensorFlow [abadi2016tensorflow], and MXNet [chen2015mxnet], and it has since
been broadly used for training deep learning models. However, its
communication complexity under the distributed mode has rarely been analyzed
in either convex or nonconvex settings.

Figure 1: The workflow of Efficient-Adam in the Parameter-Server model. For
each worker, parameters are updated via Adam. For the server, information is
gathered and averaged to update parameters. There exists a two-way
quantization scheme to reduce the communication cost between each worker and
the server. Moreover, a two-way error feedback strategy compensates for
quantization errors for both the workers and the server.

In this work, we propose a communication-efficient distributed adaptive
stochastic gradient descent method by incorporating a two-way quantization of
updates and a two-way error feedback strategy, dubbed Efficient-Adam, to solve
the nonconvex stochastic problem (1). As it is illustrated in Figure 1, the
architecture of Efficient-Adam belongs to a Parameter-Server
[smola2010architecture, li2014scaling] distributed system. For each worker, in
each iteration, we first sample a stochastic gradient of problem (1). Then, we
calculate the updates with the Adam optimizer. Next, we quantize the updates
based on a specifically designed quantization mapping and an error term and
send the quantized updates to the server. After that, we update the local
error terms using the updated quantization mapping and the new error terms. At
last, we receive the averaged updates from the server and update local
iterates. On the other hand, in the server, we first gather and average the
compressed updates from each worker. Then, we quantize the average updates and
broadcast them to each worker. Next, we update iterates and error feedback
terms. From the workflow of Efficient-Adam in Figure 1, it can be seen that
communicated bi-directional information is all quantized in advance. With the
proper quantization mapping, communication costs can be reduced largely. In
addition, error terms in the workers and server can compensate for errors that
are introduced by the two-way quantization steps between all the workers and
the server, which helps accelerate the convergence of Efficient-Adam for
problem (1).

Moreover, we explore the iteration complexity for Efficient-Adam with a class
of quantization operators when an $\varepsilon$-stationary point is achieved.
For a carefully designed quantization mapping, we further characterize its
overall communication complexity in terms of bits between the server and
workers. On the other hand, when the quantization mapping is generalized to a
compressor as [stich2019error, stich2018sparsified, zheng2019communication],
Efficient-Adam can enjoy the same convergence rate as the full-precision Adam
in Zou et al. [zou2019sufficient] and Chen et al. [chen2022towards].
Experimentally, we apply Efficient-Adam to train deep learning models on
computer vision and natural language processing tasks to demonstrate its
efficacy. To the end, we summarize our contribution in four-fold:

  * •

We propose a communication-efficient distributed Adam to solve stochastic
problem (1). We dub it Efficient-Adam which utilizes a two-way quantization
scheme to reduce the communication cost and a two-way error feedback strategy
to compensate for quantization errors.

  * •

We characterize the iteration complexity of Efficient-Adam in the non-convex
setting. Under proper assumptions, we further characterize its overall
communication complexity in terms of bits between the server and workers via a
specifically designed quantization mapping.

  * •

We show the convergence rate of Efficient-Adam can further be improved to the
same order of vanilla Adam, i.e., $\mathcal{O}(1/\sqrt{T})$, once we
generalize the quantization mapping in Efficient-Adam to a compressor mapping
as [stich2019error, stich2018sparsified].

  * •

We conduct experiments on computer vision and natural language processing
tasks to demonstrate the efficacy of the proposed Efficient-Adam, as well as
the related two-way quantization and two-way error feedback techniques.

##  2 Related Work

Table 1: Comparison among different methods. Note that Efficient-Adam can support both the compression and quantization mappings. Method | non-convex |  adaptive lr |  compression  |  quantization  |  error feedback | momentum
---|---|---|---|---|---|---
Distributed SGD | $\surd$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$
Alistarh et al. [alistarh2017qsgd] | $\surd$ | $\times$ | $\times$ | $\surd$ | $\times$ | $\times$
 Karimireddy et al. [karimireddy2019error] | $\surd$ | $\times$ | one side | $\times$ | $\surd$ | $\times$
Hou et al. [hou2018analysis] | $\times$ | $\surd$ | $\times$ | $\surd$ | $\times$ | $\times$
Zheng et al. [zheng2019communication] | $\surd$ | $\times$ | $\surd$ | $\times$ | $\surd$ | $\surd$
Chen et al. [chen2021quantized] |  $\surd$ |  $\surd$ |  one side + weights |  $\times$ |  $\surd$ |  $\surd$
Efficient-Adam | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$ | $\surd$

Optimizing a large-scale stochastic non-convex function has been studied for
many years, in which distributed SGD method has been widely explored. For
distributed SGD, its convergence rate has been established both in the
Parameter-Server model [agarwal2011distributed] and decentralized model
[lian2017can]. To reduce the communication cost, compression on the
communication has been added into the distributed stochastic methods, such as
QSGD [alistarh2017qsgd] and Sign SGD [bernstein2018signsgd]. However, due to
the error introduced by compression, most distributed methods will fail to
converge with compressed communication. Several works [jiang2018linear,
wangni2018gradient, wen2017terngrad] have tried to use unbiased compressors to
remove errors brought by compression and provide related convergence analyses.
However, with some biased compressors (e.g. SignSGD), SGD methods empirically
achieve good solutions, which cannot be explained by those works. To deal with
biased compression, Karimireddy et al. [karimireddy2019error] first introduced
error feedback into SignSGD method and established its convergence. However,
their analysis only focuses on the setting in a single machine. In addition,
there exist several decentralized SGDs that try to utilize error feedback to
reduce compression errors, such as ChocoSGD [koloskova2019decentralized] and
DeepSqueeze [tang2019texttt].

Further, for the parameter-server model, Zheng et al. [zheng2019communication]
introduced a two-way error feedback technique into SGD with momentum and
showed its convergence in the nonconvex setting. Moreover, they used a block-
wise compressor to meet the compressor assumption. However, even with the
block-wise compression, their assumption still does not hold when the gradient
goes to $0$. Besides, the learning rate for each worker may be hard to tune
when the number of workers is large. On the other hand, Hou et al.
[hou2018analysis] adapted the distributed Adam with quantized gradients and
weights to reduce the communication overhead and gave the convergence bound
for the convex case. However, in their work, they considered an unbiased
quantization function and did not consider error feedback terms, which may
limit the use of the analysis. Besides, Chen et al. [chen2021quantized]
proposed Quantized Adam, but they only consider error feedback in one
direction, and in the other direction, weight quantization is used. Wang et
al. [wang2022communication] compressed and communicated with gradients, then
they performed an AMSGrad algorithm. The update equation can be encapsulated
as $x_{t+1}=x_{t}-\alpha_{t}m_{t}/\sqrt{v_{t}+\epsilon}$. The theoretical
analysis conducted by Chen et al. [chen2021quantized] and Wang et al.
[wang2022communication] significantly depends on the constant $\epsilon$,
which must be sufficiently large. However, a larger value of $\epsilon$ can
lead to it dominating the denominator of the equation, thereby causing the
algorithm to regress to a simple stochastic gradient descent mechanism.
Further, Doostmohammadian M et al. [doostmohammadian2022distributed,
doostmohammadian2022fast] and Magnusson et al. [magnusson2018communication]
present algorithms that solve constrained optimization problems when the
communication network experiences heterogeneous time-delays. Moreover, when
considering transmitting bits among devices, the compression assumption used
in previous work does not hold (e.g. with finite bits arbitrary small values
can not be represented). Therefore, we will give a practical assumption on the
compression of the communication. To distinguish from the previous assumption,
we denote the function satisfying the new assumption as a quantizer, and the
function satisfying the previous assumption as a compressor. Among the
research we’ve looked at, the work by Chen et al. [chen2021quantized] is the
most similar to ours. However, they tried to reduce how much information the
server sends to the workers by using shorter representations for the model’s
weights which further introduces additional quantization bias. Since it’s
tough to represent these weights accurately with just a few bits, we took a
different path in our study. We try to send compressed updates for the weights
instead. This way, we’re able to lower the communication needed even more.

Different from these existing works, we propose an adaptive distributed
stochastic algorithm with a two-way quantization/compressor and a two-way
error feedback strategy, dubbed Efficient Adam. We also establish its
iteration complexity and communication complexity in terms of bits under some
specialized designed quantization mappings in the non-convex setting. In the
following Table 1, we summarize the differences between our proposed
Efficient-Adam and several existing communication-efficient distributed SGD
methods in the parameter-server model.

##  3 Preliminaries

For presenting and analyzing the proposed Efficient-Adam in the following
sections, we first give several basic definitions and assumptions. First, we
denote the stochastic estimation of $F(x)=\mathbb{E}_{\xi}[f(x,\xi)]$ as
$g=\nabla_{x}f(x,\xi)$ with a given sample $\xi$. In addition, we summarize a
few necessary assumptions on function $F$ and stochastic estimate $g$, and
define the $\varepsilon$-stationary point of problem (1).

###### Assumption 1

Function $F(x)$ is assumed to be lower bounded, i.e., $F(x)\geq F^{*}>-\infty$
for some give constant $F^{*}$. Gradient $\nabla F$ is assumed to be
L-Lipschitz continuous, i.e., $\|\nabla F(x)-\nabla F(y)\|\leq L\|x-y\|$.
Besides, we assume that for given $x$, $g$ is an unbiased estimator of the
gradient with bounded second moment, i.e.,
$\mathbb{E}_{\xi}(g)=\nabla{F}(x)=\nabla_{x}\mathbb{E}_{\xi}(f(x,\xi))$ and
$\|g\|\leq G$.

###### Definition 1

We denote $x^{*}\in\mathbb{X}$ as the $\varepsilon$-stationary point of
problem (1), if it satisfies $\mathbb{E}\|\nabla
F(x^{*})\|^{2}\leq\varepsilon$.

Assumption 1 is widely used for establishing convergence rates of adaptive SGD
methods towards $\varepsilon$-stationary points, such as Adam/RMSProp
[zou2019sufficient], AdaGrad [ward2018adagrad, zou2018weighted,
defossez2020convergence], AMSGrad [reddi2019convergence, chen2018convergence]
and AdaSAM [sun2023adasam]. Recently, Shi et al. [shi2021rmsprop] and Zhang et
al. [zhang2022adam] have eliminated the bounded gradient assumption in their
studies. However, their results are only applicable when $\mathbb{P}$ has
finite supports, and these cannot be extended to the general stochastic
setting.

Below, we define a class of quantization mappings which are used to quantize
the communicated information between the workers and server in Figure 1 to
reduce the communication.

###### Definition 2

We call $\mathcal{Q}:\mathbb{X}\to\mathbb{X}$ a quantization mapping, if there
exist constants $\delta>0$ and $\delta^{\prime}\geq 0$ such that the two
inequalities hold: $\|x-\mathcal{Q}(x)\|\leq(1-\delta)\|x\|+\delta^{\prime}$
and $\|\mathcal{Q}(x)\|\leq(2-\delta)\|x\|$.

We give a few quantization mappings that satisfy the above definition.

###### Example 1

Let $M_{1}$ be the set of 32-bits floating point number and
$M_{2}=\\{\frac{i}{2^{k}-1}|i=-2^{k}+1,-2^{k}+2,\cdots,2^{k}-1\\}$, for some
positive integer k. Then define $Q_{1}(x)=\arg\min_{y\in M_{1}}|x-y|$ which
maps $\mathbb{R}$ to $M_{1}$, and $Q_{2}(x)=\arg\min_{y\in
M_{2}^{d}}\|x-y\|_{2}$ which maps from $\mathbb{R}^{d}$ to $M_{2}^{d}$. The
quantization function $\mathcal{Q}$ is defined as
$\mathcal{Q}(x)=Q_{1}(\|x\|_{\infty})Q_{2}(x/Q_{1}(\|x\|_{\infty}))$, when
$Q_{1}(\|x\|_{\infty})>0$ and $\mathcal{Q}(x)=0$, when
$Q_{1}(\|x\|_{\infty})=0$.

###### Example 2

Let $M=\\{2^{k},2^{k+1},\cdots,2^{K}\\}$ for some integer numbers $k$ and
$K>k$. Define the quantization function $\mathcal{Q}$ as
$\mathcal{Q}(x)=sign(x)\arg\min_{y\in M^{d}}\||x|-y\|$.

There exist several works that utilize compressor mappings
[stich2018sparsified, stich2019error] to reduce the communication cost for
distributed SGD in the Parameter-Server model, in which compressor mapping is
formally defined as follows:

###### Definition 3

We call $\mathcal{Q}:\mathbb{X}\to\mathbb{X}$ as compressor mapping
[stich2018sparsified, stich2019error, zheng2019communication], if there exists
a positive value $\delta$ such that the inequality holds:
$\|x-\mathcal{Q}(x)\|\leq(1-\delta)\|x\|$. Based on the definition, it
directly holds that $\|\mathcal{Q}(x)\|\leq(2-\delta)\|x\|$.

###### Remark 1

Most quantization mappings do not belong to the above class of compressors,
since, with a finite set as range, quantization mapping cannot achieve the
condition of compressors for arbitrarily small parameters $x$. Therefore, we
cannot find any quantization function that satisfies the definition of the
compressor in Definition 3. Moreover, when $\delta^{\prime}$ is much smaller
than the precision which we want to achieve, we can ignore it and reduce the
condition to the compressor condition. Meanwhile, we have an additional
condition $\|Q(x)\|\leq(2-\delta)\|x\|$, which can be easily achieved by
replacing rounding to flooring. Therefore, we give a more practical condition
for analyzing the communication complexity. Moreover, the convergence of
Efficient-Adam with quantization can be easily extended to compressors.

##  4 Efficient-Adam

In this section, we describe the proposed Efficient-Adam, whose workflow has
already been displayed in Figure 1. To make the presentation clear, we split
Efficient-Adam into two parts: parameter server part (Algorithm 1) and
$N$-workers part (Algorithm 2). To reduce the communication overhead among the
server and workers, we introduce a two-way quantization mapping. We denote the
quantization function in the parameter server as $\mathcal{Q}_{s}(\cdot)$ and
the quantization function in the workers as $\mathcal{Q}_{w}(\cdot)$,
respectively. The detailed iterations of Efficient-Adam are described in
Algorithm 1 and Algorithm 2.

In the parameter server (see Algorithm 1), the initial value of $x$ will be
broadcast to each worker at the initialization phase. Then in each iteration,
the server gathers the update from each worker, calculates the average of
these updates, and then broadcasts this average after a quantization function.

Algorithm 1 Efficient-Adam: the server

1: Parameters: Choose quantization mapping $\mathcal{Q}_{s}(\cdot)$ via
Definition 2. Initialize $x_{1}\in\mathbb{X}$ and error term $e_{1}=0$.

2: Broadcasting $x_{1}$ to all workers;

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

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

5: Broadcasting $\tilde{\delta}_{t}=\mathcal{Q}_{s}(\hat{\delta}_{t}+e_{t})$;

6: $e_{t+1}=\hat{\delta}_{t}+e_{t}-\tilde{\delta}_{t}$;

7: $x_{t+1}=x_{t}-\tilde{\delta}_{t}$;

8: end for

Output: $x_{T+1}$.

Algorithm 2 Efficient-Adam: the $i$-th worker

1: Parameters: Choose hyperparameters
$\\{\alpha_{t}\\},\beta,\\{\theta_{t}\\}$, and quantization mapping
$\mathcal{Q}_{w}(\cdot)$ satisfying Definition 2. Set initial values
$m^{(i)}_{0}=0$ , $v^{(i)}_{0}=\epsilon$, and error term $e^{(i)}_{1}=0$,
respectively.

2: Receiving $x_{1}$ from the server;

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

4: Sample a stochastic gradient of $f(x_{t})$ as $g^{(i)}_{t}$;

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

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

7: Sending
$\delta_{t}^{(i)}=\mathcal{Q}_{w}\left(\alpha_{t}{m^{(i)}_{t}}/{\sqrt{v^{(i)}_{t}}}+e^{(i)}_{t}\right)$;

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

9: Receiving $\tilde{\delta}_{t}$ from the server;

10: $x_{t+1}=x_{t}-\tilde{\delta}_{t}$;

11: end for

In each worker (see Algorithm 2), at the initial phase, the initial value of
$x$ will be received. In each update iteration, a worker will sample a
stochastic gradient $g_{t}$ and calculate the update vector $\delta_{t}$. Then
it will send the update vector to the server with a quantization mapping and
receive the average update vector from the server. Finally, the worker will
update its local parameters.

For the above two algorithms, we use the error-feedback technique to reduce
the influence of errors introduced by quantization shown in line 6 of
Algorithm 1 and line 8 in Algorithm 2. The error-feedback technique can be
viewed as delaying updating values for $x$, while without error-feedback the
algorithm discards a few updating values on $x$ which losses information
during the optimization process. Therefore, the error-feedback technique can
help the algorithm by preserving information discarded by the quantizer.

###  4.1 Complexity Analysis

In this subsection, we give iteration complexity analysis and bit
communication complexity analysis in order to obtain an
$\varepsilon$-stationary solution of problem (1) in Definition 1, i.e.,

$\mathbb{E}\|\nabla F(x)\|^{2}\leq\varepsilon.$

We denote $\delta_{s}$ and $\delta_{s}^{\prime}$ as the constants defined in
Definition 2 for $\mathcal{Q}_{s}(\cdot)$, and $\delta_{w}$,
$\delta_{w}^{\prime}$ for $\mathcal{Q}_{w}(\cdot)$. In addition, we further
make another assumption on hyperparameters $\theta_{t}$ and $\alpha_{t}$.

###### Assumption 2

For a given maximum number of iterations $T$, we define the exponential moving
average parameter $\theta_{t}=1-\frac{\theta}{T}$, and base learning rate
$\alpha_{t}=\frac{\alpha}{\sqrt{T}}$. Besides, we define
$\gamma=\beta/(1-\frac{\theta}{T})$.

Below, we characterize the iteration complexity of Efficient-Adam to achieve
an $\varepsilon$-stationary solution of problem (1). In the corollary, we
characterize the overall bit communication complexity of Efficient-Adam with
the quantization mapping defined in Example 2.

###### Theorem 1

Let $\\{x_{t}\\}$ be the point generated by Algorithm 1 and Algorithm 2. In
addition, assume that all workers work identically and independently. Let
$x_{\tau}^{T}$ be the random variable $x_{\tau}$ with $\tau$ taking from
$\\{1,2,\cdots,T\\}$ with the same probability. For given $\varepsilon$, when
$T\geq\frac{4(G^{2}+\epsilon
d)}{(1-\beta)^{2}\alpha^{2}\varepsilon^{2}}\left(F(x_{1})-F^{*}+C_{2}\right)^{2}$,
it always holds that

$\displaystyle\mathbb{E}[\|\nabla F(x_{\tau}^{T})\|^{2}]\leq\varepsilon$
$\displaystyle\\!+\\!\left(\frac{(2\\!-\\!\delta_{s})\delta_{s}^{\prime}}{\delta_{s}}+\frac{(2\\!-\\!\delta_{s})(2\\!-\\!\delta_{w})\delta_{w}^{\prime}}{\delta_{s}\delta_{w}}\right)\frac{2L\sqrt{G^{2}\\!+\\!\epsilon
d}C_{3}}{(1-\beta)},$

where
$C_{1}=\left(\frac{\beta/(1-\beta)}{\sqrt{(1-\gamma)\theta_{1}}}+1\right)^{2}$,
$C_{2}\\!=\\!\frac{d}{1-\sqrt{\gamma}}\left(\frac{(2-\delta_{w})(2-\delta_{s})\alpha^{2}L}{\theta(1-\sqrt{\gamma})^{2}\delta_{w}\delta_{s}}\\!+\\!\frac{2C_{1}G\alpha}{\sqrt{\theta}}\right)\left[\log\left(1+\frac{G^{2}}{\epsilon
d}\right)\\!+\\!\frac{\theta}{1\\!-\\!\theta}\right]$, and
$C_{3}=\sqrt{\frac{d}{\theta(1-\sqrt{\gamma})^{4}}\left[\log\left(1+\frac{G^{2}}{\epsilon
d}\right)+\frac{\theta}{1-\theta}\right]}.$

###### Remark 2

In comparison to the work of Chen et al. [chen2021quantized] and Wang et al.
[wang2022communication], we have an order of
$\mathcal{O}(\log^{2}(1+\frac{1}{\epsilon d}))$ with respect to the constant
$\epsilon$, which pertains to numerical issues. Conversely, they demonstrate
an order of $\mathcal{O}(\frac{1}{\epsilon})$. In practical applications,
$\epsilon$ is typically configured to be a small value. Therefore, our
algorithm is capable of achieving significantly faster convergence compared to
theirs. Additionally, because Chen et al. [chen2021quantized] compress the
weights instead of the updates, when we let the value of $T$ go to infinity,
their method can’t reach the exact stationary point. Instead, it gets really
close to some stationary point, even when we use the compressor in Definition
3. On the other hand, our approach can reach the stationary point with $T$
going to infinity and compressors in Definition 3.

###### Corollary 1

With the quantization function in Example 2, when we want to get an
$\varepsilon$-stationary solution we need at most $C_{5}$ bits per iteration
on the workers and the server. Besides, to achieve an $\varepsilon$-stationary
point, we need $\frac{16(G^{2}+\epsilon
d)}{(1-\beta)^{2}\alpha^{2}\varepsilon^{2}}\left(F(x_{1})-F^{*}+C_{4}\right)^{2}$
iterations, where
$C_{4}=\frac{d}{1-\sqrt{\gamma}}\left(\frac{9\alpha^{2}L}{\theta(1-\sqrt{\gamma})^{2}}+\frac{2C_{1}G\alpha}{\sqrt{\theta}}\right)\left[\log\left(1\\!+\\!\frac{G^{2}}{\epsilon
d}\right)+\frac{\theta}{1-\theta}\right]$,
$C_{5}=d\left(1\\!+\\!\log\left(\log(\frac{\alpha}{(1\\!-\\!\gamma)\theta})\\!+\\!\log\left(\frac{24Ld\sqrt{G^{2}\\!+\\!\epsilon
d}C_{3}}{\varepsilon(1-\beta)}\right)\\!+\\!1\right)\right)$, and $C_{1},\
C_{3}$ are defined in Theorem 1.

From the above theorem and corollary, we can reduce the bits of communication
by two-way quantization and error feedback. In addition, the bit communication
complexity and iteration complexity are
$O(d\log\log\frac{d^{2}}{\varepsilon})$ and
$O(\frac{d^{3}}{\varepsilon^{2}})$, respectively. Moreover, it can be seen
that adding compression in both sides can converge to an arbitrary
$\varepsilon$-stationary point when we have large enough communication
bandwidth and sufficient iterations. There is a limited influence when we add
quantization into communication if we can have a small additional error
$\delta_{w}^{\prime}$. Below, we show that if we replace the quantization
mapping in Definition 2 as Compressor in Definition 3 in Algorithms 1-2,
Efficient-Adam can attain the same order of iteration complexity as original
Adam without introducing additional error terms.

###### Corollary 2

Let $\\{x_{t}\\}$ be the point generated by Algorithm 1 and Algorithm 2 with
the quantization mapping replaced by the compressor in Definition 3. In
addition, assume that all workers work identically and independently. Let
$x_{\tau}^{T}$ be the random variable $x_{\tau}$ with $\tau$ taking from
$\\{1,2,\cdots,T\\}$ with the same probability. For given $\varepsilon$, when
$T\geq\frac{4(G^{2}+\epsilon
d)}{(1-\beta)^{2}\alpha^{2}\varepsilon^{2}}\left(F(x_{1})-F^{*}+C_{2}\right)^{2}$,
it always holds: $\mathbb{E}[\|\nabla F(x_{\tau}^{T})\|^{2}]\leq\varepsilon,$
where
$C_{1}\\!=\\!\Big{(}\frac{\beta/(1-\beta)}{\sqrt{(1-\gamma)\theta_{1}}}+1\Big{)}^{2}$,
and
$C_{2}\\!=\\!\frac{d}{1-\sqrt{\gamma}}\left(\frac{(2-\delta_{w})(2-\delta_{s})\alpha^{2}L}{\theta(1-\sqrt{\gamma})^{2}\delta_{w}\delta_{s}}\\!+\\!\frac{2C_{1}G\alpha}{\sqrt{\theta}}\right)\left[\log\left(1+\frac{G^{2}}{\epsilon
d}\right)\\!+\\!\frac{\theta}{1\\!-\\!\theta}\right]$.

From the above corollary, it can be shown that the convergence rate of
Efficient-Adam matches the convergence rate of the vanilla Adam. Thanks to the
two-way error feedback techniques employed in Efficient-Adam, the convergence
rate will not be hurt by the introduced bi-direction compressor as defined in
Definition 3, which merely affects the speed of convergence at the constant
level. However, Chen et al. [chen2021quantized] adopt the compression on the
weights which merely converges to the neighborhood of the stationary point.

Table 2: Abbreviation of all compared algorithms Abbreviation | optimization algorithm |  communication algorithm  |  quantization function
---|---|---|---
Ours_full | Efficient-Adam | None | 32-bits floating-point number
Ours_com1 | Efficient-Adam | Error-feedback | Example 1
Ours_com1_err | Efficient-Adam | None | Example 1
Ours_com2 | Efficient-Adam | Error-feedback | Example 2
Ours_com2_err | Efficient-Adam | None | Example 2
Sgdm_full | Distributed SGD with Momentum | None | 32-bits floating-point number
Zheng et al. | Distributed SGD with Momentum | Error-feedback | Example 1
Sgdm_terngrad | Distributed SGD with Momentum | Terngrad | Example 1
Dadam_full | Distributed Adam | None | 32-bits floating-point number
Dadam_terngrad | Distributed Adam | Terngrad | Example 1
Chen et al. |  Distributed Adam |  Error-feedback |  Example 1

Figure 2: Experimental results for stochastic convex optimization (2). The
second subfigure shows the zoom-in version of the first subfigure, which
illustrates the norm of gradient vs. iterations on all compared algorithms.
The fourth subfigure shows the zoom-in version of the third subfigure, which
illustrates the norm of gradient vs. communication bit on all compared
algorithms.

##  5 Experiments

In this section, we apply our algorithms to handle several vision and language
tasks. First, to accurately test the theorem on $\mathbb{E}\|\nabla
f(x_{t})\|^{2}$, we apply Efficient-Adam to tackle a simple stochastic convex
case. Then we apply our algorithm for training neural networks on image
classification and binary sentiment classification tasks. All of the above
tasks we compare our method with including distributed SGD where the
quantization part is done by Terngrad [wen2017terngrad], distributed Adam
[nazari2019dadam] where the quantization part is done by Terngrad, Zheng et
al. [zheng2019communication] , and Chen et al. [chen2021quantized].

For simplicity, we use the abbreviation for all compared algorithms in the
figures in this section. The abbreviations are summarized in the following
Table 2.

###  5.1 Stochastic Convex Case

In this subsection, we first optimize the following toy stochastic convex
optimization problem:

$\displaystyle\min_{x}\mathbb{E}_{\xi}\big{\|}Ax-(x^{*}+\xi)\big{\|}^{2},$ (2)

where $A\in\mathbb{R}^{500\times 500}$, $x^{*}\in\mathbb{R}^{500}$ and $\xi$
follows a Gaussian distribution with mean 0 and covariance $0.1I$, i.e.
$\xi\sim\mathcal{N}(0,0.1I)$. We randomly generate 20 cases where
$A_{ij}\sim\mathcal{N}(0,1)$ independent with each other, and
$x^{*}\sim\mathcal{N}(0,0.1I)$. For hyper-parameters, we choose $\beta=0.9$
and $\theta=0.99$ for both distributed Adam method and our method. For
distributed SGD and Zheng et al. [zheng2019communication] we choose the
momentum coefficient as 0.9. As it refers to base learning rate $\alpha_{t}$,
it is chosen from $\\{1e-5,2e-5,\cdots,100e-5\\}$ via grid search approach. We
use Example 1 for all algorithms as a quantizer and we use Example 2 for
Efficient-Adam. For Example 1, we set $k=1$ for set $M_{2}$. Besides, for
Example 2, we use $k=-17$ and $K=-11$ for set $M$. 10 workers are involved in
the distributed optimization process.

The detailed comparisons are illustrated in Figure 2. It shows that when full-
precision algorithms achieve similar performance, the Terngrad quantizer and
Chen et al. [chen2021quantized] will give worse results than Zheng et al.
[zheng2019communication] and ours. We can achieve similar results as Zheng et
al. [zheng2019communication], or even better results when using Example 2.
Even when using Example 2, it can achieve a slighter better result than the
full precision version. In addition, as it is shown in the third subfigure and
the fourth subfigure in Figure 2 when we consider communication bits, the
quantizer introduced in Example 1 gives the smallest total number of bits. On
the other hand, even if Example 2 uses twice more bits than Example 1 does in
one communication iteration, with our algorithm it can still converge faster
than Terngrad.

Figure 3: Ablation study with/without error-feedback on the norm of gradient
vs. iterations for stochastic convex optimization (2). The right figure shows
the zoom-in version of the left one.

As it refers to the error-feedback technique, shown in Figure 3, with
quantizer in Example 1, error-feedback can help the algorithm get a better
result. It helps a little when using Example 2 as the quantization function
during communication. This may be because the Example 2 is accurate enough for
solving this problem.

Figure 4: Experimental results for image classification task on the CIFAR100
dataset. The left figure shows curves on training loss vs. communication bits.
The second figure shows zooming into the beginning iterations of training. The
third figure shows the curves on test accuracy vs. communication bits, and the
fourth figure shows the zoom-in version of the third figure.

###  5.2 Image Classification

In this subsection, we apply Efficient-Adam to train a ResNet-18[he2016deep]
on the dataset CIFAR100 [krizhevsky2009learning]. The CIFAR100 dataset
contains 60,000 $32\times 32$ images with RGB channels, and they are labeled
into 100 classes. In each class, there are 600 images, of which 500 images are
used for training and 100 images are used for the test. ResNet18 contains 17
convolutional layers and one fully-connected layer. Input images will be
downscaled into 1/8 size of their original size and then fed into a fully
connected layer for classification training and testing. For the convolutional
layers, we have 64 channels in the 1-5 convolutional layers, 128 channels in
the 6-9 layers, 256 channels in the 10-13 layers, and 512 channels in the
14-17 layers. With batch size 16 and 8 workers, we train ResNet-18 for 78200
iterations. We use cross-entropy loss with regularization to train the
network. The weight of $\ell_{2}$ regularization we used is $5e-4$. For the
other hyper-parameters, we use $\beta=0.9$, $\theta_{t}=0.999$ for adam-based
algorithms, and for sgd with momentum we use 0.9 as the momentum coefficient.
In addition, for each algorithm, based on the test accuracy, we select based
learning rate denoting as $\alpha$ from
$\\{1e-1,5e-2,1e-2,5e-3,1e-3,5e-4,1e-4\\}$ via grid search in the beginning
and reduce $\alpha$ into $0.2\alpha$ after every 19,550 iterations (50 epochs
for CIFAR100 training), which is often used in deep learning settings to get
better performance. The hyper-parameters for the quantization function are the
same as it in Section 5.1.

The detailed results are shown in Figure 4, 5, and 6, where training loss has
been smoothed for better presentation. Figure 5 shows the convergence speed
and test accuracy with respect to the optimization iterations. It shows that
even if we quantize the communication our algorithm and Zheng et al.
[zheng2019communication] can achieve similar performance as the full
communication version. Meanwhile, because Terngrad [wen2017terngrad]
introduces extra noise, it gives the worst results. And because Chen et al.
[chen2021quantized] quantized weights instead of the updates that introduce
the irreducible errors, they can not approach the optimal point as close as
the other methods. Thus it results in poor generalizations compared with our
proposed Efficient-Adam. When we consider the training loss and test accuracy
with respect to communication bits, which is shown in Figure 4, Zheng et al.
[zheng2019communication] achieves the best result. This may be because sgd-
based methods are much more suitable for image classification tasks compared
with adaptive stochastic gradient type methods [wilson2017marginal]. Moreover,
our results are similar to Zheng et al. [zheng2019communication]’s results.
Still, it can be shown in Figure 4 that with Example 2 as a quantizer, our
algorithm is still better than Terngrad [wen2017terngrad].

Figure 5: Experimental results for image classification on the CIFAR100
dataset. The left figure and right figure show curves on training loss vs.
iterations and the curves on test accuracy vs. iterations, respectively.

Figure 6: Ablation study with/without error-feedback on the training loss and
test accuracy vs. iterations for image classification task on CIFAR100
dataset, respectively. The left figure and right figure show curves on
training loss vs. iterations and the curves on test accuracy vs. iterations,
respectively.

Besides, we check whether the error-feedback technique is helpful to train the
image classification task. The results are shown in Figure 6. When
quantization functions introduce “large” error where Example 1 is used, the
error-feedback technique helps a lot. Similarly, when the quantizer is
accurate enough, where Example 2 is used as the quantization function, error-
feedback has limited effect for improving its accuracy.

Figure 7: Experimental results for binary sentiment classification task on the
IMDB dataset. The first subfigure shows curves on training loss vs.
communication bit. The second subfigure shows zooming into the beginning
iterations of training of the first subfigure. The third subfigure shows the
curves on test accuracy vs. communication bits, and the fourth figure shows
the zoom-in version of the third subfigure.

###  5.3 Binary Sentiment Classification

In addition, we apply our method to the sentiment classification task. We
train a GRU [cho2014properties] network on the dataset IMDB [maas-
EtAl:2011:ACL-HLT2011]. The dataset contains 50,000 movie reviews which are
labeled as positive or negative. Besides, the dataset has been split into two
sets: one is a training set that contains 25,000 reviews and the other is a
test set containing the rest 25,000 reviews. For the network part, we use a
bidirectional GRU with 2 layers. In each layer, we set the hidden unit
dimension as 256. Moreover, we use pertained Bert [devlin2018bert] encoding to
encode the text before it goes into GRU. During the training phase, we set
iterations as 2000, parameter $\beta=0.9$, and parameter $\theta_{t}=0.999$
for Adam-based algorithms, and the momentum coefficient for sgd-based
algorithm is 0.9. The learning rate for each algorithm is selected from
$\\{1e-1,5e-2,1e-2,5e-3,1e-3,5e-4,1e-4\\}$ via grid search approach. The batch
size is 16 and 8 workers are involved in the training phase. No regularization
terms or learning rate decay are used in the training phase. The hyper-
parameters for the quantization function are the same as it in Section 5.1.

The experimental results are shown in Figures 7, 8, and 9, where training loss
has been smoothed for better presentation. In Figure 8, sgd-based algorithms
perform worse than Adam-based algorithms. Still, the quantization of
communication affects a little on our algorithm. Besides, Efficient-Adam with
the quantizer in Example 2 even achieves the highest test accuracy among all
compared algorithms. When considering training loss and test accuracy vs.
communication, shown in Figure 7, Efficient-Adam with Example 1 can achieve
lower training loss and comparable high test-accuracy as Distributed Adam with
Terngrad, while Efficient-Adam with Example 2 can achieve the highest test
accuracy after 500MB communication.

Figure 8: Experimental results for binary sentiment classification on the IMDB
dataset. The first figure and the second figure show curves on training loss
vs. iterations and test accuracy vs. iterations, respectively.

Moreover, Figure 9 shows the influence of the error-feedback technique. Still,
without error-feedback, Efficient-Adam with quantizer in Example 1 achieves
much worse performance than the algorithm with error-feedback, and Efficient-
Adam with quantizer in Example 2 achieves a slightly bad test accuracy or
achieves even better training loss than the algorithm with error-feedback.
Results can be concluded similarly as it is in Section 5.1 and 5.2, where the
more error quantization function will introduce, the more helpful error
feedback is.

Figure 9: Ablation study with/without error-feedback on the training loss and
test accuracy vs. iterations for binary sentiment classification task on the
IMDB dataset, respectively. The left figure and right figure show curves on
training loss vs. iterations and the curves on test accuracy vs. iterations,
respectively.

##  6 Conclusion

We proposed a communication efficient adaptive stochastic gradient descent
algorithm for optimizing the non-convex stochastic problem, dubbed Efficient-
Adam. In the algorithm, we used a two-side quantization to reduce the
communication overhead and two error feedback terms to compensate for the
quantization error to encourage convergence. With the more practical
assumptions, we established a theoretical convergence result for the
algorithm. Besides, we established the communication complexity and iteration
complexity under certain quantization functions. On the other hand, when the
quantization operators are generalized to compressors, Efficient-Adam can
achieve the same convergence rate as full-precision Adam. Lastly, we applied
the algorithm to a toy task and real-world image and sentiment classification
tasks. The experimental results confirm the efficacy of the proposed
Efficient-Adam. However, we merely established the convergence of the
Efficient-Adam. To demonstrate the linear-speedup characteristic of Efficient-
Adam in a distributed environment, alternative assumptions, such as bounding
the variance of stochastic gradients, may be necessary. We identify this as a
potential area for future exploration. Additionally, the algorithm could
potentially be adapted into an asynchronous version, which would involve
assessing the impact of delays on the algorithm’s performance. We also earmark
this aspect for future investigation.

##  7 Proof of Efficient-Adam

To prove Theorem 1, more notations and lemmas are needed. Below, we introduce
several notations and lemmas.

###### Notation 1

Let
$\mathbb{E}_{t}\left(\cdot\right)=\mathbb{E}_{\xi}\left(\cdot|x_{t},v_{t-1},m_{t-1}\right)$.
Denote $\sigma_{t}^{2}=\mathbb{E}_{t}\left(g_{t}^{2}\right)$,
$\hat{v}^{\left(i\right)}_{t}=\theta_{t}v^{\left(i\right)}_{t}+\left(1-\theta_{t}\right){\sigma}^{2}_{t}$,
$\hat{\eta}^{\left(i\right)}_{t}=\alpha_{t}/\sqrt{\hat{v}^{\left(i\right)}_{t}}$,
$\Delta_{t}^{\left(i\right)}=-\alpha_{t}m_{t}^{\left(i\right)}/\sqrt{v_{t}^{\left(i\right)}}$,
$\Delta_{t}=\frac{1}{N}\sum_{i=1}^{N}\Delta_{t}^{\left(i\right)}$,
$E_{t}=\frac{1}{N}\sum_{i=1}^{N}e_{t}^{\left(i\right)}$,
$M_{t}=\mathbb{E}[\langle\nabla
f\left(x_{t}\right),\Delta_{t}\rangle+\frac{L\left(2-\delta_{s}\right)}{N}\sum_{i=1}^{N}\|e_{t}\|\|\Delta_{t}^{\left(i\right)}\|+\frac{L\left(2-\delta_{s}\right)\left(2-\delta_{w}\right)}{N}\sum_{i=1}^{N}\|\Delta_{t}^{\left(i\right)}\|^{2}$
$+\frac{L\left(2-\delta_{s}\right)\left(2-\delta_{w}\right)}{N^{2}}\sum_{i=1}^{N}\sum_{j=1}^{N}\|e_{t}^{\left(i\right)}\|\|\Delta_{t}^{\left(j\right)}\|]$,
and $\theta^{\prime}=1-\theta/T$. In addition, let $\tilde{x}_{t}=x_{t}-e_{t}$
and $\hat{x_{t}}=\tilde{x}_{t}-E_{t}$.

Using the above notations, it is not hard to check that the following two
equations hold:

$\displaystyle\tilde{x}_{t+1}=x_{t}-\mathcal{Q}_{s}\left(\hat{\delta}_{t}+e_{t}\right)-e_{t+1}=x_{t}+\hat{\delta}_{t}-e_{t}=\tilde{x}_{t}+\hat{\delta}_{t},$
(3)
$\displaystyle\hat{x}_{t+1}=\tilde{x_{t}}-\frac{1}{N}\sum_{t=1}^{N}\mathcal{Q}_{w}\left(-\Delta_{t}^{\left(i\right)}+e_{t}^{\left(i\right)}\right)-E_{t+1}=\hat{x}_{t}+\Delta_{t}.$
(4)

###### Lemma 1

By using Notation 1 and the iteration scheme of algorithm 2, $\forall\ t\geq
1$ and $i=1,2,\cdots,N$, the following inequality holds:

$\small\left(m_{t}^{\left(i\right)}\right)^{2}\leq\frac{1}{\left(1-\gamma\right)\left(1-\theta_{t}\right)}v_{t}^{\left(i\right)}.$

######  Proof 7.2.

By using the definitions of $m_{t}^{\left(i\right)}$ and
$v_{t}^{\left(i\right)}$ in Algorithm 2, it directly holds that

$\begin{split}m_{t}^{\left(i\right)}=\sum_{k=1}^{t}\beta^{t-k}\left(1-\beta\right)g_{k}^{\left(i\right)},v_{t}^{\left(i\right)}=\sum_{k=1}^{t}\left(\theta^{\prime}\right)^{t-k}\left(1-\theta_{k}\right)\left(g_{k}^{\left(i\right)}\right)^{2}.\end{split}$

With arithmetic inequality, it holds that

$\begin{split}\left(m_{t}^{\left(i\right)}\right)^{2}&=\left(\sum_{k=1}^{t}\frac{\beta^{t-k}\left(1-\beta\right)}{\sqrt{\theta^{\prime
t-k}\left(1-\theta_{k}\right)}}\sqrt{{\theta^{\prime}}^{t-k}\left(1-\theta_{k}\right)}g_{k}^{\left(i\right)}\right)^{2}\\\
&\leq\sum_{k=1}^{t}\frac{\beta^{2\left(t-k\right)}\left(1-\beta\right)^{2}}{\theta^{\prime
t-k}\left(1-\theta_{k}\right)}\sum_{k=1}^{t}\theta^{\prime
t-k}\left(1-\theta_{k}\right)\left(g_{k}^{\left(i\right)}\right)^{2}\\\
&=\sum_{k=1}^{t}\frac{\beta^{2\left(t-k\right)}\left(1-\beta\right)^{2}}{\theta^{\prime
t-k}\left(1-\theta_{k}\right)}v_{t}^{\left(i\right)}\leq\sum_{i=1}^{t}\frac{\beta^{2\left(t-i\right)}}{\left(\theta^{\prime}\right)^{t-k}\left(1-\theta_{k}\right)}v_{t}^{\left(i\right)}\\\
&\leq\frac{1}{\left(1-\gamma\right)\left(1-\theta_{t}\right)}v_{t}.\end{split}$

Then, we obtain the desired result.

######  Lemma 7.3.

Let $e^{\left(i\right)}_{t}$ be the noisy term defined in Algorithm 2 and
$\Delta^{\left(i\right)}_{t}$ be the term defined in Notation 1. Then it holds
that

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

######  Proof 7.4.

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

$\displaystyle\|e^{\left(j\right)}_{t}\|$
$\displaystyle=\|\Delta_{t-1}^{\left(j\right)}+e_{t-1}^{\left(j\right)}-\mathcal{Q}_{w}\left(\Delta_{t-1}^{\left(j\right)}+e_{t-1}^{\left(j\right)}\right)\|$
$\displaystyle\leq\left(1-\delta_{w}\right)\left(\|\Delta_{t-1}^{\left(j\right)}\|+\|e_{t-1}^{\left(j\right)}\|\right)+\delta_{w}^{\prime}$
$\displaystyle\leq\cdots\leq\sum_{k=1}^{t-1}\left(1-\delta_{w}\right)^{t-k}\|\Delta_{k}^{\left(j\right)}\|+\frac{\delta_{w}^{\prime}}{\delta_{w}}.$

In addition,

$\begin{split}&\frac{1}{N^{2}}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{j=1}^{N}\|e_{t}^{\left(i\right)}\|\|\Delta_{t}^{\left(j\right)}\|\\\
&\leq\frac{1}{N^{2}}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{j=1}^{N}\sum_{k=1}^{t-1}\frac{\left(1-\delta_{w}\right)^{t-k}}{2}\left(\|\Delta_{k}^{\left(i\right)}\|^{2}+\|\Delta_{t}^{\left(j\right)}\|^{2}\right)\\\
&\qquad+\frac{\delta_{w}^{\prime}}{\delta_{w}N}\sum_{t=1}^{T}\sum_{i=1}^{N}\|\Delta_{t}^{\left(i\right)}\|\\\
&\leq\frac{1-\delta_{w}}{\delta_{w}N}\sum_{t=1}^{T}\sum_{i=1}^{N}\|\Delta_{t}^{\left(i\right)}\|^{2}+\frac{\delta_{w}^{\prime}}{\delta_{w}N}\sum_{t=1}^{T}\sum_{i=1}^{N}\|\Delta_{t}^{\left(i\right)}\|.\end{split}$

Then, by taking expectations on both sides of the above inequality, we get the
desired result.

######  Lemma 7.5.

Let $e_{t}$ be the noisy term defined in Algorithm 1 and
$\Delta^{\left(i\right)}_{t}$ be the term defined in Notation 1. Then, it
holds that

$\begin{split}&\mathbb{E}\left[\frac{1}{N}\sum_{t=1}^{T}\sum_{i=1}^{N}\|e_{t}\|\|\Delta_{t}^{\left(i\right)}\|\right]\\\
&\leq\mathbb{E}\left[\frac{(2-\delta_{w})\left(1-\delta_{s}\right)}{N\delta_{s}\delta_{w}}\sum_{t=1}^{T}\sum_{i=1}^{N}\|\Delta_{t}^{\left(i\right)}\|^{2}\right.\\\
&\left.\qquad+\frac{1}{N}\left(\frac{\delta_{s}^{\prime}}{\delta_{s}}+\frac{(2-\delta_{w})\left(1-\delta_{s}\right)\delta_{w}^{\prime}}{\delta_{s}\delta_{w}}\right)\sum_{t=1}^{T}\sum_{i=1}^{N}\|\Delta_{t}^{\left(i\right)}\|\right].\end{split}$

######  Proof 7.6.

By the definition of $\hat{\delta_{t}}$ in Algorithm 1 and Algorithm 2, it
holds that

$\|\hat{\delta}_{t}\|\\!=\\!\frac{1}{N}\\!\sum_{i=1}^{N}\\!\left\|Q_{w}\left(\Delta_{t}^{(i)}\\!+\\!e_{t}^{(i)}\right)\right\|\\!\leq\\!\frac{2-\delta_{w}}{N}\\!\sum_{i=1}^{N}\\!\|\Delta_{t}^{(i)}\|+\|e_{t}^{(i)}\|.$

With the definition of $e_{t}$, we obtain that

$\begin{split}&\|e_{t}\|=\|\hat{\delta}_{t-1}+e_{t-1}-\mathcal{Q}_{s}\left(\hat{\delta}_{t-1}+e_{t-1}\right)\|\\\
&\leq\left(1-\delta_{s}\right)\left(\|\hat{\delta}_{t-1}\|+\|e_{t-1}\|\right)+\delta_{s}^{\prime}\\\
&\leq\left(1-\delta_{s}\right)\left(\frac{(2-\delta_{w})}{N}\sum_{j=1}^{N}\left(\|\Delta_{t-1}^{\left(j\right)}\|+\|e_{t-1}^{\left(j\right)}\|\right)+\|e_{t-1}\|\right)+\delta_{s}^{\prime}\\\
&\leq\frac{2-\delta_{w}}{N}\sum_{l=1}^{t-1}\left(1-\delta_{s}\right)^{t-l}\sum_{j=1}^{N}\|\Delta_{l}^{\left(j\right)}\|+\frac{\delta_{s}^{\prime}}{\delta_{s}}+\frac{(2-\delta_{w})\left(1-\delta_{s}\right)\delta_{w}^{\prime}}{\delta_{s}\delta_{w}}\\\
&\qquad+\frac{2-\delta_{w}}{N}\sum_{l=1}^{t-1}\left(1-\delta_{s}\right)^{t-l}\sum_{j=1}^{N}\sum_{k=1}^{l-1}\left(1-\delta_{w}\right)^{l-k}\|\Delta_{k}^{\left(j\right)}\|\end{split}$

Plugging $\|e_{t}\|$ into the left-hand-side and summing over $T$ and $N$, we
obtain that

$\begin{split}&\frac{1}{N}\sum_{t=1}^{T}\sum_{i=1}^{N}\|e_{t}\|\|\Delta_{t}^{\left(i\right)}\|\\\
&\leq\frac{2-\delta_{w}}{2N^{2}}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{l=1}^{t-1}\sum_{j=1}^{N}\left(1-\delta_{s}\right)^{t-l}\left(\|\Delta_{l}^{\left(j\right)}\|^{2}+\|\Delta_{t}^{\left(i\right)}\|^{2}\right)\\\
&+\frac{2-\delta_{w}}{2N^{2}}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{l=1}^{t-1}\sum_{j=1}^{N}\left(1-\delta_{s}\right)^{t-l}\sum_{k=1}^{l-1}\left(1-\delta_{w}\right)^{l-k}\|\Delta_{k}^{\left(j\right)}\|^{2}\\\
&+\frac{2-\delta_{w}}{2N^{2}}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{l=1}^{t-1}\sum_{j=1}^{N}\left(1-\delta_{s}\right)^{t-l}\sum_{k=1}^{l-1}\left(1-\delta_{w}\right)^{l-k}\|\Delta_{t}^{\left(i\right)}\|^{2}\\\
&+\frac{1}{N}\left(\frac{\delta_{s}^{\prime}}{\delta_{s}}+\frac{(2-\delta_{w})\left(1-\delta_{s}\right)\delta_{w}^{\prime}}{\delta_{s}\delta_{w}}\right)\sum_{t=1}^{T}\sum_{i=1}^{N}\|\Delta_{t}^{\left(i\right)}\|.\\\
\end{split}$ (5)

Then we simplify the above summation terms, for the first term, it holds that

$\begin{split}&\frac{2-\delta_{w}}{2N^{2}}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{l=1}^{t-1}\sum_{j=1}^{N}\left(1-\delta_{s}\right)^{t-l}\left(\|\Delta_{l}^{\left(j\right)}\|^{2}+\|\Delta_{t}^{\left(i\right)}\|^{2}\right)\\\
&\leq\frac{(2-\delta_{w})(1-\delta_{s})}{2N\delta_{s}}\sum_{l=1}^{T}\sum_{j=1}^{N}\|\Delta_{l}^{\left(j\right)}\|^{2}+\frac{(2-\delta_{w})(1-\delta_{s})}{2N\delta_{s}}\sum_{t=1}^{T}\sum_{i=1}^{N}\|\Delta_{t}^{\left(i\right)}\|^{2}\\\
&=\frac{(2-\delta_{w})(1-\delta_{s})}{N\delta_{s}}\sum_{t=1}^{T}\sum_{i=1}^{N}\|\Delta_{t}^{\left(i\right)}\|^{2}.\end{split}$
(6)

For the second summation term, we have

$\begin{split}&\frac{2-\delta_{w}}{2N^{2}}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{l=1}^{t-1}\sum_{j=1}^{N}\left(1-\delta_{s}\right)^{t-l}\sum_{k=1}^{l-1}\left(1-\delta_{w}\right)^{l-k}\|\Delta_{k}^{\left(j\right)}\|^{2}\\\
&\leq\frac{2-\delta_{w}(1-\delta_{w})(1-\delta_{s})}{2N\delta_{w}\delta_{s}}\sum_{k=1}^{T}\sum_{j=1}^{N}\|\Delta_{k}^{\left(j\right)}\|^{2}.\end{split}$
(7)

And for the third term, it holds that

$\begin{split}&\frac{2-\delta_{w}}{2N^{2}}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{l=1}^{t-1}\sum_{j=1}^{N}\left(1-\delta_{s}\right)^{t-l}\sum_{k=1}^{l-1}\left(1-\delta_{w}\right)^{l-k}\|\Delta_{t}^{\left(i\right)}\|^{2}\\\
&\leq\frac{(2-\delta_{w})(1-\delta_{w})(1-\delta_{s})}{2N\delta_{w}\delta_{s}}\sum_{t=1}^{T}\sum_{i=1}^{N}\|\Delta_{t}^{\left(i\right)}\|^{2}\end{split}$
(8)

Combining inequalities (5), (6), (7) and (8), it holds that

$\begin{split}&\frac{1}{N}\sum_{t=1}^{T}\sum_{i=1}^{N}\|e_{t}\|\|\Delta_{t}^{(i)}\|\\\
&\leq\frac{(2-\delta_{w})\left(1-\delta_{s}\right)}{N\delta_{s}\delta_{w}}\sum_{t=1}^{T}\sum_{i=1}^{N}\|\Delta_{t}^{\left(i\right)}\|^{2}\\\
&\qquad+\frac{1}{N}\left(\frac{\delta_{s}^{\prime}}{\delta_{s}}+\frac{(2-\delta_{w})\left(1-\delta_{s}\right)\delta_{w}^{\prime}}{\delta_{s}\delta_{w}}\right)\sum_{t=1}^{T}\sum_{i=1}^{N}\|\Delta_{t}^{\left(i\right)}\|.\end{split}$

Then, by taking expectations on both sides of the above inequality, we get the
desired result.

######  Lemma 7.7.

By using Notation1, for any $i=1,2,\cdots,N$, the following inequality holds:

$\sum_{t=1}^{T}\|\Delta_{t}^{\left(i\right)}\|^{2}\leq\frac{\alpha^{2}}{\theta\left(1-\sqrt{\gamma}\right)^{2}}\sum_{t=1}^{T}\left\|\frac{\sqrt{1-\theta_{t}}g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}\right\|^{2}.$

######  Proof 7.8.

By the definition of $m_{t}^{\left(i\right)}$, we can obtain

$|m_{t}^{\left(i\right)}|=\left|\sum_{i=1}^{t}\beta^{t-i}\left(1-\beta\right)g_{i}^{\left(i\right)}\right|\leq\sum_{i=1}^{t}\beta^{t-i}|g_{i}^{\left(i\right)}|.$

Because $v_{t}^{\left(i\right)}\geq\theta^{\prime}v_{t-1}^{\left(i\right)}$,
we can easily obtain that
$v_{t}^{\left(i\right)}\geq\left(\theta^{\prime}\right)^{t-k}v_{k}^{\left(i\right)}$.

By using the definition of $\Delta_{t}^{\left(i\right)}$, we can obtain

$\begin{split}\|\Delta_{t}^{\left(i\right)}\|^{2}&=\left\|\frac{\alpha_{t}m_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}\right\|^{2}\leq\alpha_{t}^{2}\sum_{k=1}^{t}\left\|\frac{\beta^{t-k}|g_{k}^{\left(i\right)}|}{\sqrt{v_{t}^{\left(i\right)}}}\right\|^{2}\\\
&\leq\frac{\alpha_{t}^{2}}{\left(1-\theta_{t}\right)}\sum_{k=1}^{t}\left\|\left(\frac{\beta}{\sqrt{\theta^{\prime}}}\right)^{t-i}\frac{\sqrt{1-\theta_{t}}|g_{k}^{\left(i\right)}|}{\sqrt{v_{t}^{\left(i\right)}}}\right\|^{2}\\\
&\leq\frac{\alpha^{2}}{\theta}\left(\sum_{k=1}^{t}\sqrt{\gamma}^{t-k}\right)\sum_{k=1}^{t}\sqrt{\gamma}^{t-k}\left\|\frac{\sqrt{1-\theta_{k}}g_{k}^{\left(i\right)}}{\sqrt{v_{k}^{\left(i\right)}}}\right\|^{2}\\\
&\leq\frac{\alpha^{2}}{\theta\left(1-\sqrt{\gamma}\right)}\sum_{k=1}^{t}\sqrt{\gamma}^{t-k}\left\|\frac{\sqrt{1-\theta_{k}}g_{k}^{\left(i\right)}}{\sqrt{v_{k}^{\left(i\right)}}}\right\|^{2}.\end{split}$

Hence, it follows that

$\begin{split}\sum_{t=1}^{T}\|\Delta_{t}^{\left(i\right)}\|^{2}&\leq\frac{\alpha^{2}}{\theta\left(1-\sqrt{\gamma}\right)}\sum_{t=1}^{T}\sum_{k=1}^{t}\sqrt{\gamma}^{t-k}\left\|\frac{\sqrt{1-\theta_{k}}g_{k}^{\left(i\right)}}{\sqrt{v_{k}^{\left(i\right)}}}\right\|^{2}\\\
&\leq\frac{\alpha^{2}}{\theta\left(1-\sqrt{\gamma}\right)^{2}}\sum_{t=1}^{T}\left\|\frac{\sqrt{1-\theta_{t}}g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}\right\|^{2}.\end{split}$

Thus, the desired result is obtained.

######  Lemma 7.9.

For all $i=1,2,\cdots,N$, the following estimate holds:

$\mathbb{E}\left[\sum_{t=1}^{T}\left\|\frac{\sqrt{1-\theta_{t}}g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}\right\|^{2}\right]\leq
d\left[\log\left(1+\frac{G^{2}}{\epsilon
d}\right)+\frac{\theta}{1-\theta}\right].$

######  Proof 7.10.

Let $W_{0}=1$ and $W_{t}=\prod_{i=1}^{t}\theta_{i}^{-1}$. Let
$w_{t}=W_{t}-W_{t-1}=\left(1-\theta_{t}\right)W_{t}$. Therefore, we have
$\frac{w_{t}}{W_{t}}=1-\theta_{t}$, and $\frac{W_{t-1}}{W_{t}}=\theta_{t}$. By
observing that $W_{0}v_{0}^{\left(i\right)}=\epsilon$ and
$W_{t}v_{t}^{\left(i\right)}=W_{t-1}v_{t-1}^{\left(i\right)}+w_{t}\left(g_{t}^{\left(i\right)}\right)^{2}$,
then we can obtain
$W_{t}v_{t}^{\left(i\right)}=\epsilon+\sum_{k=1}^{t}w_{k}\left(g_{k}^{\left(i\right)}\right)^{2}$.

By plugging the equality into the left-hand side, we obtain

$\begin{split}&\sum_{t=1}^{T}\left\|\frac{\sqrt{1-\theta_{t}}g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}\right\|^{2}=\sum_{t=1}^{T}\left\|\frac{\left(1-\theta_{t}\right)\left(g_{t}^{\left(i\right)}\right)^{2}}{v_{t}^{\left(i\right)}}\right\|_{1}\\\
&=\sum_{t=1}^{T}\left\|\frac{w_{t}\left(g_{t}^{\left(i\right)}\right)^{2}}{W_{t}v_{t}^{\left(i\right)}}\right\|_{1}=\sum_{t=1}^{T}\left\|\frac{w_{t}\left(g_{t}^{\left(i\right)}\right)^{2}}{\epsilon+\sum_{k=1}^{t}w_{k}\left(g_{k}^{\left(i\right)}\right)^{2}}\right\|_{1}\\\
&=\sum_{t=1}^{T}\sum_{j=1}^{d}\frac{w_{t}\left(g_{t,j}^{\left(i\right)}\right)^{2}}{\epsilon+\sum_{k=1}^{t}w_{i}\left(g_{k,j}^{\left(i\right)}\right)^{2}}=\sum_{j=1}^{d}\sum_{t=1}^{T}\frac{w_{t}g_{t,j}^{2}}{\epsilon+\sum_{k=1}^{t}w_{k}\left(g_{k,j}^{\left(i\right)}\right)^{2}}.\end{split}$

Considering each dimension respectively, for each $j=1,2,\cdots,d$, we obtain

$\begin{split}&\sum_{t=1}^{T}\frac{w_{t}\left(g_{t,j}^{\left(i\right)}\right)^{2}}{\epsilon+\sum_{k=1}^{t}w_{i}\left(g_{k,j}^{\left(i\right)}\right)^{2}}\leq\log\left(\epsilon+\sum_{k=1}^{t}w_{k}\left(g_{k,j}^{\left(i\right)}\right)^{2}\right)-\log\left(\epsilon\right)\\\
&=\log\left(1+\frac{1}{\epsilon}\sum_{k=1}^{t}w_{i}\left(g_{k,j}^{\left(i\right)}\right)^{2}\right).\end{split}$

Therefore,

$\begin{split}&\sum_{t=1}^{T}\left\|\frac{\sqrt{1-\theta_{t}}g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}\right\|^{2}\leq\sum_{j=1}^{d}\log\left(1+\frac{1}{\epsilon}\sum_{k=1}^{T}w_{k}\left(g_{k,j}^{\left(i\right)}\right)^{2}\right)\\\
&\leq
d\log\left(1+\frac{1}{d\epsilon}\sum_{k=1}^{T}w_{k}\|g_{k}^{\left(i\right)}\|^{2}\right)\\\
&\leq d\log\left(1+\frac{G^{2}}{d\epsilon}\left(W_{T}-W_{0}\right)\right)\\\
&\leq
d\left[\log\left(1+\frac{G^{2}}{d\epsilon}\right)+\frac{\theta}{1-\theta}\right].\end{split}$

Hence, we obtain the desired result.

######  Lemma 7.11.

By the definition of $\Delta_{t}^{\left(i\right)}$, the following inequality
always holds:

$\mathbb{E}\sum_{t=1}^{T}\|\Delta_{t}^{\left(i\right)}\|\leq\sqrt{T}\sqrt{\frac{\alpha^{2}d}{\theta\left(1-\sqrt{\gamma}\right)^{2}}\left[\log\left(1+\frac{G^{2}}{\epsilon
d}\right)+\frac{\theta}{1-\theta}\right]}.$

######  Proof 7.12.

Because of the concavity of function $\sqrt{x}$, we have
$\sum_{t=1}^{T}\|\Delta_{t}\|\leq\sqrt{T\sum_{t=1}^{T}\|\Delta_{t}\|^{2}}$.
Hence, using Lemma 7.7 and Lemma 7.9, we obtain the desired result.

######  Lemma 7.13.

With the definition of $M_{t}$, it holds that

$\begin{split}\sum_{t=1}^{T}M_{t}\leq
C_{2}-\frac{1-\beta}{2N}\sum_{t=1}^{T}\sum_{i=1}^{N}\mathbb{E}\|\nabla
f\left(x_{t}\right)\|_{\hat{\eta}_{t}^{\left(i\right)}}^{2}\\\
\qquad+LC_{3}\alpha\sqrt{T}\left(\frac{\delta_{s}^{\prime}}{\delta_{s}}+\frac{(2-\delta_{w})\delta_{w}^{\prime}}{\delta_{s}\delta_{w}}\right),\end{split}$

where

$\begin{split}C_{1}&=\left(\frac{\beta/\left(1-\beta\right)}{\sqrt{C_{1}\left(1-\gamma\right)\theta_{1}}}+1\right)^{2},\\\
C_{2}&=\frac{d}{1-\sqrt{\gamma}}\left(\frac{(2-\delta_{w})(2-\delta_{s})\alpha^{2}L}{\theta\left(1-\sqrt{\gamma}\right)^{2}\delta_{w}\delta_{s}}+\frac{2C_{2}G\alpha}{\sqrt{\theta}}\right)\\\
&\qquad\left[\log\left(1+\frac{G^{2}}{\epsilon
d}\right)+\frac{\theta}{1-\theta}\right],\\\
C_{3}&=\sqrt{\frac{d}{\theta\left(1-\sqrt{\gamma}\right)^{4}}\left[\log\left(1+\frac{G^{2}}{\epsilon
d}\right)+\frac{\theta}{1-\theta}\right]}.\end{split}$

######  Proof 7.14.

Using the definitions of $v_{t}^{\left(i\right)}$ and
$\hat{v}_{t}^{\left(i\right)}$, we obtain

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

In addition, we can obtain that

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

For convenience, we denote

$\begin{split}A_{t}^{\left(i\right)}&=\frac{\beta
m_{t-1}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}+\sqrt{\theta_{t}v_{t-1}^{\left(i\right)}}}-\frac{\left(1-\beta\right)g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}+\sqrt{\hat{v}_{t}^{\left(i\right)}}},\\\
B_{t}^{\left(i\right)}&=\left(\frac{\beta
m_{t-1}^{\left(i\right)}}{\sqrt{\theta_{t}v_{t-1}^{\left(i\right)}}}\frac{\sqrt{1-\theta_{t}}g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}+\sqrt{\theta_{t}v_{t-1}^{\left(i\right)}}}\frac{\left(1-\theta_{t}\right)\sigma_{t}}{\sqrt{\hat{v}_{t}^{\left(i\right)}}+\sqrt{\theta_{t}v_{t-1}^{\left(i\right)}}}\right)\\\
&+\frac{\left(1-\beta\right)\sigma_{t}}{\sqrt{v_{t}^{\left(i\right)}}+\sqrt{\hat{v}_{t}^{\left(i\right)}}}.\end{split}$

Then, for each $t>2$, we obtain

$\small\begin{split}&\Delta_{t}^{\left(i\right)}-\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}\Delta_{t-1}^{\left(i\right)}\\\
&=-\frac{\alpha_{t}m_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}+\frac{\beta\alpha_{t}m_{t-1}^{\left(i\right)}}{\sqrt{\theta_{t}v_{t-1}^{\left(i\right)}}}=-\alpha_{t}\left(\frac{m_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}-\frac{\beta
m_{t-1}^{\left(i\right)}}{\sqrt{\theta_{t}v_{t-1}^{\left(i\right)}}}\right)\\\
&=-\frac{\left(1-\beta\right)\alpha_{t}g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}-\beta\alpha_{t}m_{t-1}^{\left(i\right)}\left(\frac{1}{\sqrt{v_{t}^{\left(i\right)}}}-\frac{1}{\sqrt{\theta_{t}v_{t-1}^{\left(i\right)}}}\right)\\\
&=-\left(1-\beta\right)\hat{\eta}_{t}^{\left(i\right)}g_{t}^{\left(i\right)}-\hat{\eta}_{t}^{\left(i\right)}g_{t}^{\left(i\right)}\frac{\left(1-\theta_{t}\right)g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}A_{t}^{\left(i\right)}\\\
&-\hat{\eta}_{t}^{\left(i\right)}\sigma_{t}\frac{\left(1-\theta_{t}\right)g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}B_{t}^{\left(i\right)}.\end{split}$

By using the above equality, we can obtain an upper bound for
$\mathbb{E}\langle\nabla f\left(x_{t}\right),\Delta_{t}\rangle$ as follows:

$\begin{split}&\mathbb{E}\langle\nabla
f\left(x_{t}\right),\Delta_{t}\rangle=\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}\mathbb{E}\langle\nabla
f\left(x_{t}\right),\Delta_{t-1}\rangle\\\
&\qquad-\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\langle\nabla
f\left(x_{t}\right),\left(1-\beta\right)\hat{\eta}_{t}^{\left(i\right)}g_{t}^{\left(i\right)}\rangle\\\
&\qquad-\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\left\langle\nabla
f\left(x_{t}\right),\hat{\eta}_{t}^{\left(i\right)}g_{t}^{\left(i\right)}\frac{\left(1-\theta_{t}\right)g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}A_{t}^{\left(i\right)}\right\rangle\\\
&\qquad-\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\left\langle\nabla
f\left(x_{t}\right),\hat{\eta}_{t}^{\left(i\right)}\sigma_{t}\frac{\left(1-\theta_{t}\right)g_{i}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}B_{t}^{\left(i\right)}\right\rangle.\end{split}$

For the first term, we obtain

$\begin{split}&\mathbb{E}\langle\nabla
f\left(x_{t}\right),\Delta_{t-1}\rangle\\\ &=\mathbb{E}\langle\nabla
f\left(x_{t-1}\right),\Delta_{t-1}\rangle+\mathbb{E}\langle\nabla
f\left(x_{t}\right)-\nabla f\left(x_{t-1}\right),\Delta_{t-1}\rangle\\\
&\leq\mathbb{E}\langle\nabla f\left(x_{t-1}\right),\Delta_{t-1}\rangle\\\
&+L\mathbb{E}\left\|Q_{s}\left(\frac{1}{N}\sum_{i=1}^{N}\mathcal{Q}_{w}\left(\Delta_{t-1}^{\left(i\right)}+e_{t-1}^{\left(i\right)}\right)+e_{t-1}\right)\right\|\|\Delta_{t-1}\|\\\
\end{split}$

Meanwhile, with the definition of $\mathcal{Q}_{s}$ and $\mathcal{Q}_{w}$, it
holds that

$\begin{split}&\left\|Q_{s}\left(\frac{1}{N}\sum_{i=1}^{N}\mathcal{Q}_{w}\left(\Delta_{t-1}^{\left(i\right)}+e_{t-1}^{\left(i\right)}\right)+e_{t-1}\right)\right\|\\\
&\leq\frac{2-\delta_{s}}{N}\sum_{i=1}^{N}\left\|\mathcal{Q}_{w}\left(\Delta_{t-1}^{\left(i\right)}+e_{t-1}^{\left(i\right)}\right)\right\|+(2-\delta_{s})\left\|e_{t-1}\right\|\\\
&\leq\frac{(2-\delta_{s})(2-\delta_{w})}{N}\sum_{i=1}^{N}\left\|\Delta_{t-1}^{\left(i\right)}\right\|+\left\|e_{t-1}^{\left(i\right)}\right\|+(2-\delta_{s})\left\|e_{t-1}\right\|.\end{split}$

Combining with
$\|\Delta_{t-1}\|\leq\frac{1}{N}\sum_{i=1}^{N}\|\Delta_{t-1}^{(i)}\|$, it
holds that

$\mathbb{E}\langle\nabla f\left(x_{t}\right),\Delta_{t-1}\rangle\leq M_{t-1}.$

For the second term, we obtain

$\displaystyle-\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\langle\nabla
f\left(x_{t}\right),\left(1-\beta\right)\hat{\eta}_{t}^{\left(i\right)}g_{t}^{\left(i\right)}\rangle=-\frac{1-\beta}{N}\sum_{i=1}^{N}\|\nabla
f\left(x_{t}\right)\|_{\hat{\eta}_{t}^{\left(i\right)}}^{2}.$

For the third term, we have

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

where the inequality holds with the following equalities and inequalities:

$\begin{split}&\mathbb{E}\left\|\frac{\sqrt{\hat{\eta}_{t}^{\left(i\right)}}|\nabla
f\left(x_{t}\right)||g_{t}^{\left(i\right)}|}{\sigma_{t}}\right\|^{2}=\mathbb{E}\left\|\frac{\hat{\eta}_{t}^{\left(i\right)}\nabla
f\left(x_{t}\right)^{2}\left(g_{t}^{\left(i\right)}\right)^{2}}{\sigma_{t}^{2}}\right\|_{1}\\\
&=\mathbb{E}\|\hat{\eta}_{t}^{\left(i\right)}\nabla
f\left(x_{t}\right)^{2}\|_{1}=\mathbb{E}\|\nabla
f\left(x_{t}\right)\|^{2}_{\hat{\eta}_{t}^{\left(i\right)}},\end{split}$
$\sqrt{\hat{\eta}_{t}^{\left(i\right)}}\sigma_{t}\leq\sqrt{\frac{\alpha_{t}\sigma_{t}^{2}}{\sqrt{\left(1-\theta_{t}\right)\sigma_{t}^{2}}}}\leq\sqrt{\frac{\alpha
G}{\sqrt{\theta}}},$

and

$\begin{split}&|A_{t}^{\left(i\right)}|\leq\frac{1}{\sqrt{1-\theta_{t}}}\left(\frac{\beta}{\sqrt{\theta_{t}\left(1-\gamma\right)}}+1-\beta\right).\end{split}$

Let
$C_{1}\\!=\\!\left(\frac{\beta/\left(1-\beta\right)}{\sqrt{\left(1-\gamma\right)\theta_{1}}}+1\right)^{2}$,
we can obtain
$|A_{t}^{\left(i\right)}|\\!\leq\\!\frac{\sqrt{C_{1}}\left(1-\beta\right)}{\sqrt{1-\theta_{t}}}$.

Then we obtain the upper bound of the third term:

$\begin{split}&-\frac{1}{N}\mathbb{E}\sum_{i=1}^{N}\left\langle\nabla
f\left(x_{t}\right),\hat{\eta}_{t}^{\left(i\right)}g_{t}^{\left(i\right)}\frac{\left(1-\theta_{t}\right)g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}A_{t}^{\left(i\right)}\right\rangle\\\
&\leq\frac{1}{N}\sum_{i=1}^{N}\frac{1-\beta}{4}\mathbb{E}\|\nabla
f\left(x_{t}\right)\|_{\hat{\eta}_{t}^{\left(i\right)}}^{2}+\frac{C_{1}G\alpha}{\sqrt{\theta}}\mathbb{E}\left\|\frac{\sqrt{1-\theta_{t}}g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}\right\|^{2}.\end{split}$

For the fourth term, by using similar inequalities we have
$\small{|B_{t}^{\left(i\right)}|\leq\frac{\left(1-\beta\right)\sqrt{C_{1}}}{\sqrt{1-\theta_{t}}}.}$

Then, we have

$\begin{split}&-\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\left\langle\nabla
f\left(x_{t}\right),\hat{\eta}_{t}^{\left(i\right)}\sigma_{t}\frac{\left(1-\theta_{t}\right)g_{i}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}B_{t}^{\left(i\right)}\right\rangle\\\
&\leq\frac{1}{N}\sum_{i=1}^{N}\frac{1-\beta}{4}\mathbb{E}\|\nabla
f\left(x_{t}\right)\|_{\hat{\eta}_{t}^{\left(i\right)}}^{2}+\frac{C_{1}G\alpha}{\sqrt{\theta}}\mathbb{E}\left\|\frac{\sqrt{1-\theta_{t}}g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}\right\|^{2}.\end{split}$

By defining

$\begin{split}&N_{t}=\mathbb{E}\left[\frac{(2-\delta_{s})}{N}\left(\sum_{i=1}^{N}L\|e_{t}\|\|\Delta_{t}^{\left(i\right)}\|+(2-\delta_{s})\|\Delta_{t}^{(i)}\|^{2}\right)\right.\\\
&+\frac{(2-\delta_{w})(2-\delta_{s})L}{N^{2}}\sum_{i=1}^{N}\sum_{j=1}^{N}\|e_{t}^{\left(i\right)}\|\|\Delta_{t}^{\left(j\right)}\|\\\
&\left.+\frac{1}{N}\sum_{i=1}^{N}\frac{2C_{1}G\alpha}{\sqrt{\theta}}\left\|\frac{\sqrt{1-\theta_{t}}g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}\right\|^{2}\right],\end{split}$

then with induction, we can find the upper bound for $M_{t}$.

With the above bound, we have

$\begin{split}M_{t}&\leq\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}M_{t-1}+N_{t}-\frac{1-\beta}{2N}\mathbb{E}\sum_{i=1}^{N}\|\nabla
f\left(x_{t}\right)\|_{\hat{\eta}_{t}^{\left(i\right)}}^{2}\\\
&\leq\frac{\beta\alpha_{t}}{\sqrt{\theta_{t}}\alpha_{t-1}}M_{t-1}+N_{t}.\end{split}$

Besides, as for the bound of the first term $M_{1}$, we have

$\displaystyle\mathbb{E}\left\langle\nabla
f\left(x_{1}\right),-\frac{\alpha_{1}m_{1}^{\left(i\right)}}{\sqrt{v_{1}^{\left(i\right)}}}\right\rangle=\mathbb{E}\left\langle\nabla
f\left(x_{1}\right),\frac{\alpha_{1}\left(1-\beta\right)g_{1}^{\left(i\right)}}{\sqrt{v_{1}^{\left(i\right)}}}\right\rangle$
(9) $\displaystyle\leq\mathbb{E}\langle\nabla
f\left(x_{t}\right),\left(1-\beta\right)\hat{\eta}_{1}^{\left(i\right)}g_{1}^{\left(i\right)}\rangle$
$\displaystyle\qquad+\mathbb{E}\left\langle\nabla
f\left(x_{t}\right),\hat{\eta}_{1}^{\left(i\right)}\sigma_{1}^{\left(i\right)}\frac{\left(1-\theta_{1}\right)g_{1}^{\left(i\right)}}{\sqrt{v_{1}^{\left(i\right)}}}\frac{\left(1-\beta\right)\sigma_{1}^{\left(i\right)}}{\sqrt{v_{1}^{\left(i\right)}}+\sqrt{\hat{v}_{1}^{\left(i\right)}}}\right\rangle$
$\displaystyle\qquad-\mathbb{E}\left\langle\nabla
f\left(x_{t}\right),\hat{\eta}_{1}^{\left(i\right)}g_{1}^{\left(i\right)}\frac{\left(1-\theta_{1}\right)g_{1}^{\left(i\right)}}{\sqrt{v_{1}^{\left(i\right)}}}\frac{\left(1-\beta\right)g_{1}^{\left(i\right)}}{\sqrt{v_{1}^{\left(i\right)}}+\sqrt{\hat{v}_{1}^{\left(i\right)}}}\right\rangle$

Hence, with inequality (9), and definition of $M_{1}$, it holds that

$\begin{split}&M_{1}\leq\sum_{i=1}^{N}\frac{2C_{1}G\alpha}{\sqrt{\theta}}\mathbb{E}\left\|\frac{\sqrt{1-\theta_{1}}g_{1}^{\left(i\right)}}{\sqrt{v_{1}^{\left(i\right)}}}\right\|^{2}-\frac{1-\beta}{2}\mathbb{E}\|\nabla
f\left(x_{t}\right)\|_{\hat{\eta}_{t}^{\left(i\right)}}^{2}\\\
&\qquad+\frac{(2-\delta_{w})(2-\delta_{s})L}{N}\sum_{i=1}^{N}\mathbb{E}\|\Delta_{1}^{\left(i\right)}\|^{2}\leq
N_{1}.\end{split}$

Therefore, we can obtain

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

Then, by summing $M_{t}$ up, we obtain

$\begin{split}\sum_{t=1}^{T}M_{t}&\leq\sum_{t=1}^{T}\sum_{k=1}^{t}\sqrt{\gamma}^{t-k}N_{k}--\frac{1-\beta}{2N}\sum_{i=1}^{N}\mathbb{E}\|\nabla
f\left(x_{t}\right)\|_{\hat{\eta}_{t}^{\left(i\right)}}^{2}\\\
&\leq\frac{1}{\left(1-\sqrt{\gamma}\right)}\sum_{t=1}^{T}N_{t}-\frac{1-\beta}{2N}\sum_{i=1}^{N}\sum_{t=1}^{T}\mathbb{E}\|\nabla
f\left(x_{t}\right)\|_{\hat{\eta}_{t}^{\left(i\right)}}^{2}.\end{split}$ (10)

By combining lemma 7.3, 7.5, 7.7 and definition of $N_{t}$, we have

$\begin{split}&\sum_{t=1}^{T}N_{t}\leq\left(\frac{\delta_{s}^{\prime}}{\delta_{s}}+\frac{(2-\delta_{w})\delta_{w}^{\prime}}{\delta_{s}\delta_{w}}\right)\frac{L}{N}\sum_{t=1}^{T}\sum_{i=1}^{N}\|\Delta_{t}^{\left(i\right)}\|\\\
&+\left(\\!\frac{(2\\!-\\!\delta_{s})(2\\!-\\!\delta_{w})\alpha^{2}L}{\theta\left(1-\sqrt{\gamma}\right)^{2}\delta_{s}\delta_{w}}\\!+\\!\frac{2C_{1}G\alpha}{\sqrt{\theta}}\\!\right)\\!\frac{1}{N}\\!\sum_{i=1}^{N}\sum_{t=1}^{T}\mathbb{E}\left\|\frac{\sqrt{1-\theta_{t}}g_{t}^{\left(i\right)}}{\sqrt{v_{t}^{\left(i\right)}}}\right\|^{2}.\\\
\end{split}$

Then, using lemma 7.9 and 7.11 it holds that

$\begin{split}&\sum_{t=1}^{T}N_{t}\leq\left(\\!\frac{(2\\!-\\!\delta_{w})(2\\!-\\!\delta_{s})\alpha^{2}L}{\theta\left(1-\sqrt{\gamma}\right)^{2}\delta_{s}\delta_{w}}+\frac{2C_{1}G\alpha}{\sqrt{\theta}}\\!\right)\\!d\left[\log\\!\left(\\!1\\!+\\!\frac{G^{2}}{\epsilon
d}\\!\right)\\!+\\!\frac{\theta}{1\\!-\\!\theta}\right]\\\
&+\\!\left(\\!\frac{\delta_{s}^{\prime}}{\delta_{s}}\\!+\\!\frac{(2\\!-\\!\delta_{w})\delta_{w}^{\prime}}{\delta_{s}\delta_{w}}\\!\right)\\!L\sqrt{T}\\!\sqrt{\frac{\alpha^{2}d}{\theta\left(1\\!-\\!\\!\sqrt{\gamma}\right)^{2}}\left[\log\\!\left(\\!1\\!+\\!\frac{G^{2}}{\epsilon
d}\\!\right)\\!+\\!\frac{\theta}{1\\!-\\!\theta}\\!\right]}.\end{split}$ (11)

With the inequalities (10), (11), we obtain the desired result.

######  Lemma 7.15.

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

$\mathbb{E}[\|\nabla
f\left(x_{\tau}\right)\|^{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\left(\left(x_{t}\right)\right)\|_{\hat{\eta_{t}}^{\left(i\right)}}^{2}\right].$

######  Proof 7.16.

Note that for any $i=1,2,\cdots,N$,
$\|\hat{v}_{t}^{\left(i\right)}\|_{1}=\theta_{t}\|v_{t-1}^{\left(i\right)}\|_{1}+\left(1-\theta_{t}\right)\|\sigma_{t}\|^{2}$
and $\|g_{t}^{\left(i\right)}\|\leq G$.

Then, it is straightforward to prove $\|v_{t}^{\left(i\right)}\|_{1}\leq
G^{2}+\epsilon d$.

Utilizing this inequality, we have

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

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

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

Thus, the desired result is obtained.

######  Proof 7.17 (Proof of Theorem 1).

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

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

For fixed T, by summing up $t$ from $1$ to $T$, we can obtain

$\begin{split}f^{*}&\leq\mathbb{E}[f\left(\tilde{x}_{T+1}\right)]\leq
f\left(x_{1}\right)+\sum_{t=1}^{T}M_{t}\\\ &\leq
f\left(x_{1}\right)+C_{2}-\frac{1-\beta}{2N}\sum_{t=1}^{T}\sum_{i=1}^{N}\mathbb{E}\|\nabla
f\left(x_{t}\right)\|_{\hat{\eta}_{t}^{\left(i\right)}}^{2}\\\
&+LC_{3}\alpha\sqrt{T}\left(\frac{\delta_{s}^{\prime}}{\delta_{s}}+\frac{(2-\delta_{s})\delta_{w}^{\prime}}{\delta_{s}\delta_{w}}\right).\end{split}$

Then, using Lemma 7.15, we obtain

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

Therefore, by using the inequality that

$\mathbb{E}\|\nabla
f\left(x_{\tau}^{T}\right)\|^{2}\leq\varepsilon+\left(\frac{\delta_{s}^{\prime}}{\delta_{s}}+\frac{(2-\delta_{w})\delta_{w}^{\prime}}{\delta_{s}\delta_{w}}\right)\frac{2L\sqrt{G^{2}+\epsilon
d}C_{3}}{\left(1-\beta\right)},$

we obtain $\small{\frac{2\sqrt{G^{2}+\epsilon
d}}{\left(1-\beta\right)\alpha\sqrt{T}}\left(f\left(x_{1}\right)-f^{*}+C_{2}\right)\leq\varepsilon,}$
which gives that

$T\geq\frac{4\left(G^{2}+\epsilon
d\right)}{\left(1-\beta\right)^{2}\alpha^{2}\varepsilon^{2}}\left(f\left(x_{1}\right)-f^{*}+C_{2}\right)^{2}.$

Hence, the desired result is obtained.

######  Proof 7.18 (Proof of Corollary 1).

When using Example 2, we can calculate $\delta=1/2$ and
$\delta^{\prime}=2^{k}\sqrt{d}$, when $max_{x\in\mathbb{X}}\|x\|_{\infty}\leq
2^{K}+2^{K-1}$.

By solving
$\left(\frac{\delta_{s}^{\prime}}{\delta_{s}}+\frac{(2-\delta_{w})\delta_{w}^{\prime}}{\delta_{s}\delta_{w}}\right)\frac{2L\sqrt{G^{2}+\epsilon
d}C_{3}}{\left(1-\beta\right)}\leq\frac{\varepsilon}{2}$, and setting $K$ to
be the same in both directions, we obtain that when
$k\leq-\log\left(\frac{24L\sqrt{d}\sqrt{G^{2}\\!+\\!\epsilon
d}C_{3}}{\varepsilon(1-\beta)}\right)$, this equality always holds.

Besides, as it is shown in Lemma 1,
$\|\delta_{t}\|\leq\alpha/((1-\gamma)\theta)$. With assumption that
$\|Q(x)\|\leq 3/2\|x\|$, when
$K\geq\log\left(\alpha/((1-\gamma)\theta)\right)$ we can get a quantizer
satisfying Definition 1.

Besides, using Theorem 1, with inequality

$\mathbb{E}\|\nabla
f\left(x_{\tau}^{T}\right)\|^{2}\leq\varepsilon/2+\left(\frac{\delta_{s}^{\prime}}{\delta_{s}}+\frac{(2-\delta_{w})\delta_{w}^{\prime}}{\delta_{s}\delta_{w}}\right)\frac{2L\sqrt{G^{2}+\epsilon
d}C_{3}}{\left(1-\beta\right)},$

we have $T\geq\frac{16\left(G^{2}+\epsilon
d\right)}{\left(1-\beta\right)^{2}\alpha^{2}\varepsilon^{2}}\left(f\left(x_{1}\right)-f^{*}+C_{4}\right)^{2}$.

Meanwhile, we transmit $\small{d\log(K-k+1)}$ bits per iteration.

######  Proof 7.19.

Proof of Corollary 2

Because when compressor satisfies Definition 3, where
$\|Q(x)-x\|\leq(1-\delta)\|x\|$, it holds that $\|Q(x)\|\leq(2-\delta)\|x\|$.
Therefore, by setting $\delta^{\prime}=0$, we obtain the desired result.

[]Congliang Chen received the B.S degree in computer science and technology
from Peking University, China in 2018. He is working towards a Ph.D. degree of
the Computer Information and Engineering at the School of Science and
Engineering in the Chinese University of Hong Kong (Shenzhen). His research
interest includes distributed optimization, federated learning and machine
learning algorithms.

[]Li Shen received his Ph.D. in school of mathematics, South China University
of Technology in 2017. He is currently a research scientist at JD Explore
Academy, China. Previously, he was a research scientist at Tencent AI Lab,
China. His research interests include theory and algorithms for large scale
convex/nonconvex/minimax optimization problems, and their applications in
statistical machine learning, deep learning, reinforcement learning, and game
theory.

[]Wei Liu (M’14-SM’19) is currently a Distinguished Scientist of Tencent and
the Director of Ads Multimedia AI at Tencent Data Platform. Prior to that, he
has been a research staff member of IBM T. J. Watson Research Center, USA. Dr.
Liu has long been devoted to fundamental research and technology development
in core fields of AI, including deep learning, machine learning, reinforcement
learning, computer vision, information retrieval, big data analytics, etc. To
date, he has published extensively in these fields with more than 270 peer-
reviewed technical papers, and also issued 27 US patents. He currently serves
on the editorial boards of IEEE TPAMI, TNNLS, IEEE Intelligent Systems, and
Transactions on Machine Learning Research. He is an Area Chair of top-tier
computer science and AI conferences, e.g., NeurIPS, ICML, IEEE CVPR, IEEE
ICCV, IJCAI, and AAAI. Dr. Liu is a Fellow of the IAPR, IMA, BCS, RSA, and
AAIA, and an Elected Member of the ISI.

[]Zhi-Quan Luo received the B.S. degree in applied mathematics from Peking
University, China, and the Ph.D. degree in operations research from MIT in
1989. From 1989 to 2003, he held a faculty position with the ECE Department of
McMaster University, Canada. He held a tier-1 Canada Research Chair in
information processing from 2001 to 2003. After that, he has been a full
professor at the ECE Department, University of Minnesota and held an endowed
ADC Chair in digital technology. Currently, he is the Vice President
(Academic) of the Chinese University of Hong Kong (Shenzhen) and the director
of Shenzhen Research Institute of Big Data (SRIBD). Prof. Luo is a Fellow of
IEEE and SIAM. He was elected to Fellow of Royal Society of Canada in 2014 and
a Foreign Member of the Chinese Academy of Engineering (CAE) in 2021. He
received four best paper awards from the IEEE Signal Processing Society, one
best paper award from EUSIPCO, the Farkas Prize from INFORMS and the prize of
Paul Y. Tseng Memorial Lectureship in Continuous Optimization as well as some
best paper awards from international conferences. In 2021, he was awarded 2020
ICCM Best Paper Award by International Consortium of Chinese Mathematicians.
He has published over 350 refereed papers, books and special issues. Prof. Luo
has served as an Associate Editor for many internationally recognized journals
and the Editor in Chief for IEEE Transactions on Signal Processing. His
research mainly addresses mathematical issues in information sciences, with
particular focus on the design, analysis and applications of large-scale
optimization algorithms. (Email<EMAIL_ADDRESS>


######  Corollary 45 (Choffrut (2014)).

It is decidable whether a given automatic relation is prefix-recognizable.

##  5 Conclusion

We have considered uniformization and definability problems for subclasses of
rational relations that are defined in terms of synchronization languages. Our
results in combination with known results from the literature provide a
systematic overview of the decidability and undecidability for the different
variations of the problems. While this picture is almost complete, there are a
few problems left open, as shown in Tables 1 and 2.

Furthermore, since we consider synchronization languages over
$(\Sigma\cup\Gamma)^{*}$, our decidability results carry over to the more
restricted case of synchronization languages over $\\{1,2\\}$. However, the
undecidability results from the middle parts of the tables (where a
synchronization language $T$ is given as input to the problem) do not carry
over, in general. The undecidability results in Section 3 also hold in the
setting of synchronization languages over $\\{1,2\\}$ (in particular, Theorem
14 is formulated for such synchronization languages). For the undecidability
results in Table 2 that are derived from Proposition 18 it is open whether
they carry over to synchronization languages over $\\{1,2\\}$.

## References

  * Allauzen et al. (2011) C. Allauzen, M. Mohri, and A. Rastogi.  General algorithms for testing the ambiguity of finite automata and the double-tape ambiguity of finite-state transducers.  _International Journal of Foundations of Computer Science_ , 22(04):883–904, 2011.
  * Angluin and Hoover (1984) D. Angluin and D. N. Hoover.  Regular prefix relations.  _Mathematical Systems Theory_ , 17(3):167–191, 1984.  10.1007/BF01744439.  URL https://doi.org/10.1007/BF01744439.
  * Berstel (1979) J. Berstel.  _Transductions and context-free languages_ , volume 38 of _Teubner Studienbücher : Informatik_.  Teubner, 1979.  ISBN 3519023407.  URL http://www-igm.univ-mlv.fr/~berstel/.  Online version available via the homepage of the author http://www-igm.univ-mlv.fr/~berstel/.
  * Blumensath (2001) A. Blumensath.  Prefix-Recognisable Graphs and Monadic Second-Order Logic.  Technical Report AIB-06-2001, RWTH Aachen, May 2001.  URL http://www.logic.rwth-aachen.de/pub/blume/aib-2001-06.ps.gz.
  * Blumensath and Grädel (2000) A. Blumensath and E. Grädel.  Automatic structures.  In _15th Annual IEEE Symposium on Logic in Computer Science, Santa Barbara, California, USA, June 26-29, 2000_ , pages 51–62. IEEE Computer Society, 2000.  10.1109/LICS.2000.855755.  URL https://doi.org/10.1109/LICS.2000.855755.
  * Bojańczyk (2014) M. Bojańczyk.  Transducers with origin information.  In _Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II_ , volume 8573 of _Lecture Notes in Computer Science_ , pages 26–37. Springer, 2014.  10.1007/978-3-662-43951-7_3.  URL https://doi.org/10.1007/978-3-662-43951-7_3.
  * Bojańczyk et al. (2017) M. Bojańczyk, L. Daviaud, B. Guillon, and V. Penelle.  Which classes of origin graphs are generated by transducers.  In _ICALP_ , volume 80 of _LIPIcs_ , pages 114:1–114:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * Bose et al. (2018) S. Bose, A. Muscholl, V. Penelle, and G. Puppis.  Origin-equivalence of two-way word transducers is in PSPACE.  In _FSTTCS_ , volume 122 of _LIPIcs_ , pages 22:1–22:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * Bose et al. (2019) S. Bose, S. N. Krishna, A. Muscholl, V. Penelle, and G. Puppis.  On synthesis of resynchronizers for transducers.  In _MFCS_ , volume 138 of _LIPIcs_ , pages 69:1–69:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * Büchi and Landweber (1969) J. R. Büchi and L. H. Landweber.  Solving sequential conditions by finite-state strategies.  _Transactions of the American Mathematical Society_ , 138:295–311, 1969.  10.1090/S0002-9947-1969-0280205-0.
  * Carayol and Löding (2014) A. Carayol and C. Löding.  Uniformization in Automata Theory.  In _Proceedings of the 14th Congress of Logic, Methodology and Philosophy of Science Nancy, July 19-26, 2011_ , pages 153–178. London: College Publications, 2014.
  * Carton et al. (2006) O. Carton, C. Choffrut, and S. Grigorieff.  Decision problems among the main subfamilies of rational relations.  _ITA_ , 40(2):255–275, 2006.  10.1051/ita:2006005.  URL https://doi.org/10.1051/ita:2006005.
  * Caucal (2003) D. Caucal.  On infinite transition graphs having a decidable monadic theory.  _Theoretical Computer Science_ , 290(1):79 – 115, 2003.  ISSN 0304-3975.  https://doi.org/10.1016/S0304-3975(01)00089-5.  URL http://www.sciencedirect.com/science/article/pii/S0304397501000895.
  * Choffrut (2014) C. Choffrut.  Deciding whether or not a synchronous relation is regular prefix.  _Fundam. Inf._ , 132(4):439–459, Oct. 2014.  ISSN 0169-2968.  10.3233/FI-2014-1053.  URL http://dx.doi.org/10.3233/FI-2014-1053.
  * Descotte et al. (2018) M. E. Descotte, D. Figueira, and G. Puppis.  Resynchronizing classes of word relations.  In _45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic_ , volume 107 of _LIPIcs_ , pages 123:1–123:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  10.4230/LIPIcs.ICALP.2018.123.  URL https://doi.org/10.4230/LIPIcs.ICALP.2018.123.
  * Descotte et al. (2019) M. E. Descotte, D. Figueira, and S. Figueira.  Closure properties of synchronized relations.  In _STACS_ , volume 126 of _LIPIcs_ , pages 22:1–22:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * Figueira and Libkin (2015) D. Figueira and L. Libkin.  Synchronizing relations on words.  _Theory Comput. Syst._ , 57(2):287–318, 2015\.
  * Filiot et al. (2016) E. Filiot, I. Jecker, C. Löding, and S. Winter.  On equivalence and uniformisation problems for finite transducers.  In _Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy_ , pages 125:1–125:14, 2016.  10.4230/LIPIcs.ICALP.2016.125.  URL http://arxiv.org/abs/1602.08565.
  * Frougny and Sakarovitch (1993) C. Frougny and J. Sakarovitch.  Synchronized rational relations of finite and infinite words.  _Theor. Comput. Sci._ , 108(1):45–82, 1993.  10.1016/0304-3975(93)90230-Q.  URL https://doi.org/10.1016/0304-3975(93)90230-Q.
  * Hashiguchi (1982) K. Hashiguchi.  Limitedness theorem on finite automata with distance functions.  _J. Comput. Syst. Sci._ , 24(2):233–244, 1982\.  10.1016/0022-0000(82)90051-4.  URL https://doi.org/10.1016/0022-0000(82)90051-4.
  * Hashiguchi (1990) K. Hashiguchi.  Improved limitedness theorems on finite automata with distance functions.  _Theoretical Computer Science_ , 72(1):27–38, 1990.
  * Holtmann et al. (2010) M. Holtmann, Ł. Kaiser, and W. Thomas.  Degrees of lookahead in regular infinite games.  In _Foundations of Software Science and Computational Structures_ , volume 6014 of _Lecture Notes in Computer Science_ , pages 252–266. Springer, 2010.  /10.1007/978-3-642-12032-9_18.
  * Hosch and Landweber (1972) F. A. Hosch and L. H. Landweber.  Finite delay solutions for sequential conditions.  In _ICALP_ , pages 45–60, 1972.
  * Khoussainov and Nerode (1994) B. Khoussainov and A. Nerode.  Automatic presentations of structures.  In _Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, International Workshop LCC ’94, Indianapolis, Indiana, USA, 13-16 October 1994_ , volume 960 of _Lecture Notes in Computer Science_ , pages 367–392. Springer, 1994.  10.1007/3-540-60178-3_93.  URL https://doi.org/10.1007/3-540-60178-3_93.
  * Kirsten (2005) D. Kirsten.  Distance desert automata and the star height problem.  _RAIRO Theor. Informatics Appl._ , 39(3):455–509, 2005.  10.1051/ita:2005027.  URL https://doi.org/10.1051/ita:2005027.
  * Kopczynski (2016) E. Kopczynski.  Invisible pushdown languages.  In M. Grohe, E. Koskinen, and N. Shankar, editors, _Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’16, New York, NY, USA, July 5-8, 2016_ , pages 867–872. ACM, 2016.  10.1145/2933575.2933579.  URL http://doi.acm.org/10.1145/2933575.2933579.
  * Läuchli and Savioz (1987) H. Läuchli and C. Savioz.  Monadic second order definable relations on the binary tree.  _J. Symb. Log._ , 52(1):219–226, 1987.  10.2307/2273878.  URL https://doi.org/10.2307/2273878.
  * Sakarovitch (2009) J. Sakarovitch.  _Elements of Automata Theory_.  Cambridge University Press, 2009.  ISBN 978-0-521-84425-3.
  * Winter (2018) S. Winter.  Uniformization problems for synchronizations of automatic relations on words.  In _45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic_ , pages 142:1–142:13, 2018.  10.4230/LIPIcs.ICALP.2018.142.  URL https://doi.org/10.4230/LIPIcs.ICALP.2018.142.