# ErrorCompensatedX: error compensation for variance reduced algorithms

Hanlin Tang<EMAIL_ADDRESS>University of Rochester  Yao Li  Michigan
State University  Ji Liu  Kuaishou Technology  Ming Yan  Michigan State
University

###### Abstract

Communication cost is one major bottleneck for the scalability for distributed
learning. One approach to reduce the communication cost is to compress the
gradient during communication. However, directly compressing the gradient
decelerates the convergence speed, and the resulting algorithm may diverge for
biased compression. Recent work addressed this problem for stochastic gradient
descent by adding back the compression error from the previous step. This idea
was further extended to one class of variance reduced algorithms, where the
variance of the stochastic gradient is reduced by taking a moving average over
all history gradients. However, our analysis shows that just adding the
previous step’s compression error, as done in existing work, does not fully
compensate the compression error. So, we propose ErrorCompensatedX, which uses
the compression error from the previous two steps. We show that
ErrorCompensatedX can achieve the same asymptotic convergence rate with the
training without compression. Moreover, we provide a unified theoretical
analysis framework for this class of variance reduced algorithms, with or
without error compensation.

##  1 Introduction

Data compression reduces the communication volume and alleviates the
communication overhead in distributed learning. E.g., Alistarh et al., (2017)
compress the gradient being communicated using quantization and find that
reducing half of the communication size does not degrade the convergence
speed. However, the convergence speed would be slower if we further reduce the
communication size, and it requires the compression to be unbiased (Alistarh
et al.,, 2017; Tang et al.,, 2019). Alternatively, recent work (Stich et al.,
2018a, ) shows that compression with error compensation, which adds back the
compression error to the next round of compression, using only $3\%$ of the
original communication volume does not degrade the convergence speed, and it
works for both biased and unbiased compression operators.

Despite the promising performance of error compensation on stochastic gradient
descent (SGD), SGD admits a slow convergence speed if the stochastic gradient
has a large variance. Variance reduction techniques, such as Momentum SGD
(Zhang et al.,, 2015), ROOT-SGD (Li et al.,, 2020), STORM (Cutkosky & Mehta,,
2020), and IGT (Arnold et al.,, 2019), are developed, and they admit increased
convergence speeds either theoretically or empirically. We found that directly
applying error compensation to those variance reduced algorithms is not
optimal, and their convergence speeds degrade. So a natural question arises:
what is the best compression method for variance reduced algorithms? In this
paper, we answer this question and propose ErrorCompensatedX, a general method
for error compensation, and show that it admits faster convergence speeds than
previous error compensation methods. The contributions of this paper can be
summarized as follows:

  * •

We propose a novel error compensation algorithm for variance reduced
algorithms and SGD. Our algorithm admits a faster convergence rate compared to
previous methods (Zheng et al., 2019a, ; Stich et al., 2018b, ) by fully
compensating all error history.

  * •

We provide a general theoretical analysis framework to analyze error
compensated algorithms. More specifically, we decompose the convergence rate
into the sum of two terms

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\|\nabla f(\bm{x}_{t})\|^{2}\leq$
$\displaystyle\mathcal{R}_{\text{uncompressed}}+\mathcal{R}_{\epsilon},$

where $\mathcal{R}_{\text{uncompressed}}$ depends only on the convergence rate
of the original algorithm without compression and $\mathcal{R}_{\epsilon}$ is
depends only on the magnitude of the compression error $\epsilon$. It means
that we can easily attain the convergence rate for any compressed algorithm in
the form of (2). To the best of our knowledge, this is the first general
result for error compensation.

##  2 Related Works

##### Variance Reduced Optimization.

When the variance of the stochastic gradient is large, training using SGD
becomes unstable, and it usually renders a slow convergence speed. Many
studies try to reduce the variance of the stochastic gradient. For example,
Momentum SGD (Zhang et al.,, 2015) takes a moving average over all previous
stochastic gradients. However, its expected momentum does not equal to the
full gradient. Recent studies take one step further by applying bias
correction to the momentum. One approach is to compute the gradient at
$\bm{x}_{t}$ and $\bm{x}_{t-1}$ using the same data sample $\xi_{t}$ (Huang et
al.,, 2020; Yuan et al.,, 2020; Li et al.,, 2020), while another direction is
to compute the gradient at the extrapolated point of $\bm{x}_{t}$ and
$\bm{x}_{t-1}$ (Arnold et al.,, 2019; Cutkosky & Mehta,, 2020). When the
number of data samples is finite, some approaches compute the full gradient
once in a while or memorize the latest stochastic gradient of each data sample
and use its average to approximate the full gradient; examples include SVRG
(Johnson & Zhang,, 2013), SAGA (Defazio et al.,, 2014), and SARAH (Nguyen et
al.,, 2017).

##### Communication Efficient Optimization.

One major bottleneck of distributed learning is the communication cost.
Methods, such as data compression, decentralized training, local SGD, and
federated learning, were proposed to reduce the communication cost. Data
compression is an important approach that can be combined with other
approaches, and it is critical for communication networks with limited
bandwidth. It was firstly proposed in Seide et al., (2014), where authors
proposed 1-bit SGD, which uses one bit to represent each element in the
gradient but still achieves almost the same convergence speed with the
uncompressed one. In Stich et al., 2018b , authors proposed a general
algorithm for error compensated compression—MEM-SGD with theoretical analysis.
They found that MEM-SGD has the same asymptotic convergence rate with
uncompressed SGD, and more importantly, is robust to both biased and unbiased
compression operators. This method can be combined with decentralized training
(Vogels et al.,, 2020), local SGD (Xie et al.,, 2020), and accelerated
algorithms (Gorbunov et al.,, 2020). Due to its promising efficiency, error
compensation has been applied into many related area (Zheng et al., 2019b, ;
Phuong & Phong,, 2020; Yu et al.,, 2019; Shi et al.,, 2019; Ivkin et al.,,
2019; Sun et al.,, 2019; Basu et al.,, 2019; Vogels et al.,, 2019) to reduce
the communication cost.

Another direction to minimize the side-effect of compression is to compress
the difference between the current gradient and momentum. Previous work
(Mishchenko et al.,, 2019; Liu et al.,, 2020) proved that this strategy
achieves linear convergence when the loss function is strongly convex.
However, the linear convergence requires either the full deterministic
gradient, or using SVRG (Horváth et al.,, 2019) to control the variance when
for finite sum the loss function. Therefore how they perform with general
variance reduced stochastic algorithms is still an open problem.

##  3 Algorithm Design

###  3.1 Background

The underlying problem we consider can be posed as the following distributed
optimization problem:

$\min_{\bm{x}}\quad
f(\bm{x})=\frac{1}{n}\sum_{i=1}^{n}\underbrace{\mathbb{E}_{\xi^{(i)}\sim\mathcal{D}_{i}}F\left(\bm{x};\xi^{(i)}\right)}_{:=f_{i}(\bm{x})},$
(1)

where $n$ is the number of workers, $\mathcal{D}_{i}$ is the local data
distribution for worker $i$ (in other words, we do not assume that all nodes
can access the same data set), and $F(\bm{x};\xi^{(i)})$ is the local loss
function of model $\bm{x}$ given data $\xi^{(i)}$ for worker $i$.

One widely used method for solving (1) is SGD, which updates the model using
$\bm{x}_{t+1}=\bm{x}_{t}-\gamma\bm{g}_{t},$ where $\bm{x}_{t}$ is the model at
the $t$-th iteration, $\gamma$ is the learning rate and $\bm{g}_{t}$ is the
averaged stochastic gradients. However, SGD suffers from the problem of large
stochastic gradient variance, and many variance reduced algorithms are
developed. In our paper, we focus on the following variance reduced
algorithms: Momentum SGD, STROM, ROOT-SGD111STORM (for non-convex loss
function) and ROOT-SGD (strongly-convex loss function) use the same updating
rule except $\alpha_{t}=1/{T^{\frac{2}{3}}}$ for STORM and $\alpha_{t}=1/T$
for ROOT-SGD., and IGT, because they all construct the estimator using a
moving average of previous stochastic gradients, which can be summarized as

$\displaystyle\bm{v}_{t}=$
$\displaystyle(1-\alpha_{t})\bm{v}_{t-1}+\alpha_{t}\mathscr{A}(\bm{x}_{t};\xi_{t}),\quad\bm{x}_{t+1}=\bm{x}_{t}-\gamma\bm{v}_{t},$
(2)

where $\bm{v}_{t}$ is the gradient estimator,
$\mathscr{A}(\bm{x}_{t};\xi_{t})$ is a variable that depends on the history
models $\bm{x}_{s}$ (for all $s\leq t$) and data sample $\xi_{t}$, and
$\alpha_{t}$ is a scalar. Notice that $\mathscr{A}(\bm{x}_{t};\xi_{t})$ and
$\alpha_{t}$ are designed differently for different algorithms. We list the
different choices of those parameters for each algorithm in Table 1.

| $\alpha_{t}$ | $\mathscr{A}(\bm{x}_{t};\xi_{t})$
---|---|---
SGD | $1$ | $\nabla F(\bm{x}_{t};\xi_{t})$
Momentum SGD | $\alpha$ | $\nabla F(\bm{x}_{t};\xi_{t})$
STORM | $\alpha$ | $\frac{1}{\alpha_{t}}\left(\nabla F(\bm{x}_{t};\xi_{t})-(1-\alpha_{t})\nabla F(\bm{x}_{t-1};\xi_{t})\right)$
ROOT-SGD | $1/t$ | $\frac{1}{\alpha_{t}}\left(\nabla F(\bm{x}_{t};\xi_{t})-(1-\alpha_{t})\nabla F(\bm{x}_{t-1};\xi_{t})\right)$
IGT | $\alpha$ | $\nabla F\left(\bm{x}_{t}+\frac{1-\alpha_{t}}{\alpha_{t}}(\bm{x}_{t}-\bm{x}_{t-1});\xi_{t}\right)$
Table 1: Different choices of $(\alpha_{t},\mathscr{A}(\bm{x}_{t};\xi_{t}))$
for each variance reduced algorithm.

Recent work suggests that instead of compressing the gradient directly
(Alistarh et al.,, 2017), using error compensation (Stich et al., 2018b, )
could potentially improve the convergence speed. The idea of error
compensation is quite straightforward: adding back the compression error from
the previous step to compensate the side-effect of compression. Denoting
$C_{\omega}[\cdot]$222Here $\omega$ denotes the randomness of the compression
operator. as the compressing operator, the updating rule of this method
follows

$\displaystyle\bm{x}_{t+1}=\bm{x}_{t}-\gamma
C_{\omega}[\bm{g}_{t}+\bm{\delta}_{t-1}],\quad\bm{\delta}_{t}=\bm{g}_{t}+\bm{\delta}_{t-1}-C_{\omega}[\bm{g}_{t}+\bm{\delta}_{t-1}],$

where $\bm{\delta}_{t}$ is the compression error at the $t$-th step. Moreover,
recent works (Chen et al.,, 2020; Wu et al.,, 2018) find that adding a low-
pass filter to the history compression error could be helpful for stabilizing
the training and further improving the training speed. Their updating rule can
be summarized as

$\displaystyle\bm{e}_{t}=$
$\displaystyle(1-\beta)\bm{e}_{t-1}+\beta\bm{\delta}_{t-1},\quad\bm{x}_{t+1}=\bm{x}_{t}-\gamma
C_{\omega}[\bm{g}_{t}+\bm{e}_{t}],\quad\bm{\delta}_{t}=\bm{g}_{t}+\bm{e}_{t}-C_{\omega}[\bm{g}_{t}+\bm{e}_{t}],$

where $\beta$ is a hyper-parameter of the low-pass filter.

Notice that even error compensated compression has been proved to be very
powerful for accelerating the compressed training, it was only studied for
SGD, which is a special case of (2) when $\alpha_{t}=1$. For the case where
$\alpha_{t}<1$, previous work (Zheng et al., 2019a, ; Zhao et al.,, 2019; Wang
et al.,, 2020) adapted the same idea from Stich et al., 2018b , which directly
compresses the gradient estimator $\bm{v}_{t}$ with the compression error from
the previous step being compensated (we refer this method as Single
Compensation). However, we find that when $\alpha_{t}$ is very small
($\mathcal{O}\left(1/T\right)$ for ROOT-SGD and
$\mathcal{O}\left(1/T^{\frac{2}{3}}\right)$ for STORM, where $T$ is the total
training iterations), Single Compensation would be much slower than the
uncompressed one, as shown in Figure 1.

(a)

(b)

Figure 1: Convergence speed comparison on linear regression for STORM and IGT
with different compression techniques. The $x$-axis is the training step
number, and the $y$-axis is the norm of the full gradient. The batch size
equals $1$, $\alpha_{t}=1/t$, and we use 1-bit compression as described in
Tang et al., (2019). Single Compensation means only compensate the compression
error from the last step, and we can see that it admits a much slower
convergence speed than the uncompressed one when $\alpha_{t}$ is very small.
However, our proposed ErrorCompensatedX has a similar convergence rate as the
uncompressed one.

###  3.2 Proposed ErrorCompensatedX

In this section, we provide the intuition behind our proposed method
ErrorCompensatedX. For simplicity, we consider the general update in (2) with
$\alpha_{t}=\alpha$. Let $\bm{v}_{-1}=0$, then the uncompressed algorithm has
the update

$\displaystyle\bm{x}_{T}=\bm{x}_{0}-\gamma\sum_{t=0}^{T-1}\sum_{s=0}^{t}\alpha(1-\alpha)^{t-s}\mathscr{A}(\bm{x}_{s};\xi_{s}).$

Note $\mathscr{A}(\bm{x}_{s};\xi_{s})$ is transferred from worker nodes to the
server (here we aggregate the data from all workers). If the compression is
applied on $\mathscr{A}(\bm{x}_{s};\xi_{s})$, then we have the update

$\displaystyle\bm{x}_{T}=$
$\displaystyle\bm{x}_{0}-\gamma\sum_{t=0}^{T-1}\sum_{s=0}^{t}\alpha(1-\alpha)^{t-s}(\mathscr{A}(\bm{x}_{s};\xi_{s})-\bm{\delta}_{s})$
$\displaystyle=$
$\displaystyle\bm{x}_{0}-\gamma\sum_{t=0}^{T-1}\sum_{s=0}^{t}\alpha(1-\alpha)^{t-s}\mathscr{A}(\bm{x}_{s};\xi_{s})+\gamma\sum_{s=0}^{T-1}(1-(1-\alpha)^{T-s})\bm{\delta}_{s}.$

Note that the sequence $\\{\bm{x}_{s}\\}_{s=0}^{T}$ is different from that of
the uncompressed one. Here $\bm{\delta}_{s}$ is the compression error, and the
compressed data $\mathscr{A}(\bm{x}_{s};\xi_{s})-\bm{\delta}_{s}$ is
transferred to the server. With error compensation and additional
$\bm{\delta}_{-1}=0$, we have

$\displaystyle\bm{x}_{T}=$
$\displaystyle\bm{x}_{0}-\gamma\sum_{t=0}^{T-1}\sum_{s=0}^{t}\alpha(1-\alpha)^{t-s}(\mathscr{A}(\bm{x}_{s};\xi_{s})+\bm{\delta}_{s-1}-\bm{\delta}_{s})$
$\displaystyle=$
$\displaystyle\bm{x}_{0}-\gamma\sum_{t=0}^{T-1}\sum_{s=0}^{t}\alpha(1-\alpha)^{t-s}\mathscr{A}(\bm{x}_{s};\xi_{s})+\gamma\sum_{s=0}^{T-1}\alpha(1-\alpha)^{T-1-s}\bm{\delta}_{s}.$

Here $\bm{\delta}_{s}$ is the compression error that occurs while compressing
$\mathscr{A}(\bm{x}_{s};\xi_{s})+\bm{\delta}_{s-1}$. When $\alpha=1$, the last
term disappears, and the standard SGD case has been analyzed in Tang et al.,
(2019); Stich et al., 2018a . In this paper, we focus on the case where the
last term does not disappear, i.e., $\alpha\in(0,1)$. Given
$\bm{\delta}_{-1}=\bm{\delta}_{-2}=0$, when using ErrorCompensatedX, we have

$\displaystyle\bm{x}_{T}=$
$\displaystyle\bm{x}_{0}-\gamma\sum_{t=0}^{T-1}\sum_{s=0}^{t}\alpha(1-\alpha)^{t-s}(\mathscr{A}(\bm{x}_{s};\xi_{s})+(1-\alpha)(\bm{\delta}_{s-1}-\bm{\delta}_{s-2})+\bm{\delta}_{s-1}-\bm{\delta}_{s})$
$\displaystyle=$
$\displaystyle\bm{x}_{0}-\gamma\sum_{t=0}^{T-1}\sum_{s=0}^{t}\alpha(1-\alpha)^{t-s}\mathscr{A}(\bm{x}_{s};\xi_{s})+\alpha\gamma\bm{\delta}_{T-1}.$

Notice that in the discussion above, we make an implicit assumption that there
is only one worker in the training. For the case of multiple workers, we adapt
the same strategy proposed by Tang et al., (2019), which uses a Parameter-
Server communication prototype and applies error compensation for both rounds
of worker-server communication.

For changing $\alpha_{t}$, the updating rule of ErrorCompensatedX with a low-
pass filter follows

$\displaystyle\bm{e}_{t}=$
$\displaystyle(1-\beta)\bm{e}_{t-1}+\beta\left(\frac{\alpha_{t-1}}{\alpha_{t}}(2-\alpha_{t})\bm{\delta}_{t-1}-\frac{\alpha_{t-2}}{\alpha_{t}}(1-\alpha_{t})\bm{\delta}_{t-2}\right),\quad\Delta_{t}=\mathscr{A}(\bm{x}_{t};\xi_{t})+\bm{e}_{t},$
(3) $\displaystyle\bm{v}_{t}=$
$\displaystyle(1-\alpha_{t})\bm{v}_{t-1}+\alpha_{t}C_{\omega}[\Delta_{t}],\quad\bm{\delta}_{t}=\Delta_{t}-C_{\omega}[\Delta_{t}],\quad\bm{x}_{t+1}=\bm{x}_{t}-\gamma\bm{v}_{t}.$

Here $\bm{e}_{t}$ is the compression error being passed after the low-pass
filter and $\beta$ is the hyper-parameter of the low-pass filter. Our analysis
indicates that for a general case with $0<\alpha_{t}\leq 1$, using just the
compression error from the last step is not good enough, especially when
$\alpha_{t}$ is very small. In this case, ErrorCompensatedX admits a much
faster convergence speed than Single Compensation and could achieve the same
asymptotic speed with the uncompressed one. We assume a Parameter-Server
communication prototype for the parallel implementation of ErrorCompensatedX,
and the detailed algorithm description can be find in Algorithm 1.

Algorithm 1 ErrorCompensatedX for general $\mathscr{A}(\bm{x};\xi)$

1: Input: Initialize $\bm{x}_{0}$, learning rate $\gamma$, loss-pass filter
parameter $\beta$, initial error on workers
$\bm{\delta}_{-1}^{(i)}=\bm{\delta}_{0}^{(i)}=\bm{0}$, initial error on the
server $\bm{\delta}_{-1}=\bm{\delta}_{0}=\bm{0}$, scheduler of
$\\{\alpha_{t}\\}_{t=-1}^{T}$, and number of total iterations $T$. The initial
gradient estimator $\bm{v}_{0}=\nabla F\left(\bm{x}_{0};\xi_{0}^{(i)}\right)$
with total batch-size $B_{0}$, initial compression error buffer
$\bm{e}_{0}^{(i)}=\bm{0}$ and $\bm{e}_{0}=\bm{0}$.

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

3: On worker $i$:

4: Pass the worker compression error into the low-pass filter:
$\bm{e}_{t}^{(i)}=(1-\beta)\bm{e}_{t-1}^{(i)}+\beta\left(\frac{\alpha_{t-1}}{\alpha_{t}}(2-\alpha_{t})\bm{\delta}_{t-1}^{(i)}-\frac{\alpha_{t-2}}{\alpha_{t}}(1-\alpha_{t})\bm{\delta}_{t-2}^{(i)}\right).$

5: Compute the error-compensated local gradient estimator:
$\Delta^{(i)}_{t}=\mathscr{A}\left(\bm{x}_{t};\xi_{t}^{(i)}\right)+\bm{e}_{t}^{(i)}.$

6: Compress $\Delta^{(i)}_{t}$ into $C_{\omega}\left[\Delta^{(i)}_{t}\right]$
and update the local worker error
$\bm{\delta}^{(i)}_{t}\leftarrow\Delta^{(i)}_{t}-C_{\omega}\left[\Delta_{t}^{(i)}\right]$.

7: Send $C_{\omega}\left[\Delta_{t}^{(i)}\right]$ to the parameter server.

8: On parameter server:

9: Pass the server compression error into the low-pass filter:
$\bm{e}_{t}=(1-\beta)\bm{e}_{t-1}+\beta\left(\frac{\alpha_{t-1}}{\alpha_{t}}(2-\alpha_{t})\bm{\delta}_{t-1}-\frac{\alpha_{t-2}}{\alpha_{t}}(1-\alpha_{t})\bm{\delta}_{t-2}\right).$

10: Average all gradient estimator received from workers:
$\Delta_{t}=\frac{1}{n}\sum_{i=1}^{n}C_{\omega}\left[\Delta_{t}^{(i)}\right]+\bm{e}_{t}.$

11: Compress $\Delta_{t}$ into $C_{\omega}\left[\Delta_{t}\right]$ and update
the server error
$\bm{\delta}_{t}=\Delta_{t}-C_{\omega}\left[\Delta_{t}\right]$

12: Send $C_{\omega}\left[\Delta_{t}\right]$ to workers

13: On worker $i$:

14: Update the gradient estimator
$\bm{v}_{t}=(1-\alpha_{t})\bm{v}_{t-1}+\alpha_{t}C_{\omega}\left[\Delta_{t}\right]$.

15: Update the model $\bm{x}_{t+1}=\bm{x}_{t}-\gamma\bm{v}_{t}$.

16: end for

17: Output: $\bm{x}_{T}$

Throughout this paper and its supplementary document, we let
$f^{*}=\min_{\bm{x}}f(\bm{x})$ be the optimal objective value. In addition, we
let $\|\cdot\|$ denote the $l_{2}$ norm of vectors, and $\lesssim$ means “less
than or equal to up to a constant factor”.

##  4 Theoretical Analysis

In this section, we first summarize the general updating rule for each
algorithm w/o error compensation. Then we will present a general theorem that
is essential for getting the convergence rate of each algorithm. At last, we
will see that by using ErrorCompensatedX, we could achieve the same asymptotic
convergence rate with training without communication compression using both
biased and unbiased compression.

All error compensation algorithms mentioned so far can be summarized into the
formulation of

$\displaystyle\bm{e}_{t}=$
$\displaystyle(1-\beta)\bm{e}_{t-1}+\beta\left(c_{1,t}\bm{\delta}_{t-1}-c_{2,t}\bm{\delta}_{t-2}\right),$
(4) $\displaystyle\bm{v}_{t}=$
$\displaystyle(1-\alpha_{t})\bm{v}_{t-1}+\alpha_{t}\mathscr{A}(\bm{x}_{t};\xi_{t})-\eta_{1,t}\bm{\delta}_{t}+\eta_{2,t}\bm{e}_{t},\quad\bm{x}_{t+1}=\bm{x}_{t}-\gamma\bm{v}_{t}.$
(5)

Here $(1-\alpha_{t})\bm{v}_{t-1}+\alpha_{t}\mathscr{A}(\bm{x}_{t};\xi_{t})$
originates from the original uncompressed algorithm. Other terms that depends
on the compression error $\bm{\delta}_{t}$ indicates the influence of
compression (see our supplementary material for more details about the
parameter setting for different compression algorithms.)

###  4.1 Convergence Rate of General Algorithms

In this section, we decompose the convergence rate of ErrorCompensatedX into
two parts: $\mathcal{R}_{\text{uncompressed}}(T)$ that only depends on the
original algorithm without compression, and $\mathcal{R}_{\epsilon}$ which
only depends on the way of error compensation.

Instead of investigating $\bm{x}_{t}$ directly, we introduce an auxiliary
sequence $\\{\hat{\bm{x}}_{t}\\}$, which is defined as

$\displaystyle\bm{u}_{t}=(1-\alpha_{t})\bm{u}_{t-1}+\alpha_{t}\mathscr{A}(\bm{x}_{t};\xi_{t}),\quad\hat{\bm{x}}_{t}=\hat{\bm{x}}_{t-1}-\gamma\bm{u}_{t},$
(6)

and set $\hat{\bm{x}}_{0}=\bm{x}_{0}$, $\bm{u}_{0}=\bm{v}_{0}$ for
initialization. Below we are going to see that $\\{\hat{\bm{x}}_{t}\\}$ admits
some nice properties and is very helpful for the analysis of the convergence
rate for $\\{\bm{x}_{t}\\}$.

For $\hat{\bm{x}}_{t}$, there seems to be no compression error, but we still
compute the gradient estimator using $\bm{x}_{t}$ instead $\hat{\bm{x}}_{t}$
directly. Therefore we also define

$\displaystyle\hat{\bm{u}}_{0}=\mathscr{A}(\bm{x}_{0};\xi_{0})=\mathscr{A}(\hat{\bm{x}}_{0};\xi_{0}),\quad\hat{\bm{u}}_{t}=(1-\alpha_{t})\hat{\bm{u}}_{t-1}+\alpha_{t}\mathscr{A}(\hat{\bm{x}}_{t};\xi_{t}).$
(7)

In this case, in the view of $\\{\hat{\bm{x}}_{t}\\}$, it basically updates
the model following

$\displaystyle\hat{\bm{u}}_{t}=(1-\alpha_{t})\hat{\bm{u}}_{t-1}+\alpha_{t}\mathscr{A}(\hat{\bm{x}}_{t};\xi_{t}),\quad\hat{\bm{x}}_{t}=\hat{\bm{x}}_{t-1}-\gamma\hat{\bm{u}}_{t}-\underbrace{\gamma(\bm{u}_{t}-\hat{\bm{u}}_{t})}_{\textbf{compression
bias}}.$

Therefore $\\{\hat{\bm{x}}_{t}\\}$ is essentially using the same uncompressed
gradient estimator $\mathscr{A}(\hat{\bm{x}}_{t};\xi_{t})$ for constructing
the gradient estimator $\hat{\bm{u}}_{t}$ except that when it updates the
model, it will use $\hat{\bm{u}}_{t}$ plus a compression bias term
$\gamma(\bm{u}_{t}-\hat{\bm{u}}_{t})$.

Now we present the key theorem that concludes the convergence rate of any
algorithm (for non-convex loss function) that updates the model according to
(4) and (5). Before we introduce the final theorem, we first make some
commonly used assumptions:

######  Assumption 1.

We assume $f^{*}>-\infty$ and make the following assumptions:

  1. 1.

Lipschitzian gradient: $f(\cdot)$ and $F(\cdot;\xi)$ are assumed to be with
$L$-smooth, which means

$\displaystyle\|\nabla F(\bm{x};\xi)-\nabla F(\bm{y};\xi)\|\leq$
$\displaystyle L_{F}\|\bm{x}-\bm{y}\|,\quad\forall\bm{x},\bm{y},\xi,$
$\displaystyle\|\nabla f_{i}(\bm{x})-\nabla f_{i}(\bm{y})\|\leq$
$\displaystyle L\|\bm{x}-\bm{y}\|,\quad\forall\bm{x},\bm{y},i;$

  2. 2.

Bounded variance: The variance of the stochastic gradient is bounded

$\displaystyle\mathbb{E}_{\xi^{(i)}\sim\mathcal{D}_{i}}\|\nabla
F(\bm{x};\xi^{(i)})-\nabla f(\bm{x})\|^{2}\leq$
$\displaystyle\sigma^{2},\quad\forall\bm{x},i.$

######  Theorem 1.

For algorithms that follow the updating rule (4) and (5), under Assumption 1,
we have

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f(\bm{x}_{t})\|^{2}\leq$
$\displaystyle\underbrace{\frac{16(f(\bm{x}_{0})-f^{*})}{\gamma
T}+\frac{8}{T}\sum_{t=0}^{T-1}A_{t}}_{\mathcal{R}_{\text{uncompressed}}(T)}+\underbrace{\frac{64L^{2}_{\mathscr{A}}+2L^{2}}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{x}_{t}-\hat{\bm{x}}_{t}\|^{2}}_{\mathcal{R}_{\epsilon}},$

where $A_{t}$ is defined as

$\displaystyle A_{t}:=$ $\displaystyle\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})-\hat{\bm{u}}_{t}\|^{2}-(1-2L\gamma)\mathbb{E}\|\hat{\bm{u}}_{t}\|^{2}-\frac{\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}}{4}$

with $\hat{\bm{u}}_{t}$ defined in (7), and $L_{\mathscr{A}}$ is the Lipschitz
constant of $\mathscr{A}(\cdot;\xi)$, i.e.,

$\displaystyle\|\mathscr{A}(\bm{x};\xi)-\mathscr{A}(\bm{y};\xi)\|\leq$
$\displaystyle
L_{\mathscr{A}}\|\bm{x}-\bm{y}\|,\quad\forall\bm{x},\bm{y},\xi.$

Here $A_{t}$, which depends only on the original uncompressed algorithm,
indicates the bias of constructing the gradient estimator using uncompressed
$\mathscr{A}(\hat{\bm{x}}_{t};\xi_{t})$, hence
$\frac{16(f(\bm{x}_{0})-f^{*})}{\gamma T}+\frac{8}{T}\sum_{t=0}^{T}A_{t}$ is
usually the convergence rate of the original algorithm without compression.

In order to get a clear vision about the influence of the compression error
under different error compensation methods, in the theorem below we are going
to give an upper bound of
$\sum_{t=0}^{T}\mathbb{E}\|\bm{x}_{t}-\hat{\bm{x}}_{t}\|^{2}$ for different
error compensation methods.

######  Assumption 2.

The magnitude of the compression error are assumed to be bounded by a constant
$\epsilon$:

$\displaystyle\mathbb{E}_{\omega}\left\|\bm{\delta}_{t}^{(i)}\right\|^{2}\leq\frac{\epsilon^{2}}{2},\quad\mathbb{E}_{\omega}\left\|\bm{\delta}_{t}^{(i)}\right\|^{2}\leq\frac{\epsilon^{2}}{2},\forall
t,i.$

######  Theorem 2.

For algorithms that follow the updating rule (4) and (5), under Assumption 2,
setting $\beta=1$, $\eta_{1,t}=\eta_{1}$, $\eta_{2,t}=\eta_{2}$,
$c_{1,t}=c_{1}$, and $c_{2,t}=c_{2}$, we have

$\displaystyle\bm{x}_{t}-\hat{\bm{x}}_{t}=$
$\displaystyle-\frac{\eta_{1}}{\alpha}\sum_{s=0}^{t}\left(1-(1-\alpha)^{t-s+1}\right)\bm{\delta}_{s}+\frac{\eta_{2}c_{1}}{\alpha}\sum_{s=0}^{t-1}\left(1-(1-\alpha)^{t-s}\right)\bm{\delta}_{s}$
$\displaystyle+\frac{\eta_{2}c_{2}}{\alpha}\sum_{s=0}^{t-2}\left(1-(1-\alpha)^{t-s-1}\right)\bm{\delta}_{s}.$

More specifically, we have

  * •

No Compensation:
$\sum_{t=0}^{T}\mathbb{E}\|\bm{x}_{t}-\hat{\bm{x}}_{t}\|^{2}\leq\frac{\gamma^{2}T^{2}\epsilon^{2}}{\alpha^{2}};$

  * •

Single Compensation:
$\sum_{t=0}^{T}\mathbb{E}\|\bm{x}_{t}-\hat{\bm{x}}_{t}\|^{2}\leq\frac{\gamma^{2}\epsilon^{2}}{\alpha^{2}};$

  * •

ErrorCompensatedX:
$\sum_{t=0}^{T}\mathbb{E}\|\bm{x}_{t}-\hat{\bm{x}}_{t}\|^{2}\leq\gamma^{2}\alpha^{2}\epsilon^{2}.$

###  4.2 Convergence Rate for Different Gradient Estimators

In this section, we apply Theorem 1 to get the specific convergence rate of
ErrorCompensatedX for Momentum SGD, STORM, and IGT.

####  4.2.1 SGD and Momentum SGD

Since SGD is a special case of Momentum SGD when setting $\alpha=1$, the
following theorem includes both SGD and Momentum SGD.

######  Theorem 3.

Setting $\mathscr{A}(\bm{x}_{t};\xi_{t})=\nabla F(\bm{x}_{t};\xi_{t})$, if
$L\gamma\leq\frac{\alpha}{12}$, under Assumptions 1 and 2, we have

$\displaystyle\sum_{t=0}^{T-1}A_{t}\leq\frac{17\gamma L\sigma^{2}T}{3n}.$

This leads us to the corollary below:

######  Corollary 4.

For ErrorCompensatedX, under Assumptions 1 and 2, setting
$\alpha_{t}=\alpha\in(0,1]$, $\mathscr{A}(\bm{x}_{t};\xi_{t})=\nabla
F(\bm{x}_{t};\xi_{t})$ and
$\gamma=\min\left\\{\frac{\alpha}{12L},\sqrt{\frac{n}{T\sigma^{2}}},\left(\frac{1}{\epsilon^{2}T}\right)^{1/3}\right\\}$,
we have

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f(\bm{x}_{t})\|^{2}\lesssim\frac{\sigma}{\sqrt{nT}}+\frac{\alpha^{2}}{(\epsilon
T)^{\frac{2}{3}}}+\frac{1}{\alpha T}.$

The leading term admits the order of $\mathcal{O}\left(1/\sqrt{nT}\right)$,
which is the same as uncompressed training.

####  4.2.2 STOchastic Recursive Momentum (STORM)

######  Theorem 5.

Setting $\mathscr{A}(\bm{x}_{t};\xi_{t})=\frac{1}{\alpha_{t}}\left(\nabla
F(\bm{x}_{t};\xi_{t})-(1-\alpha_{t})\nabla F(\bm{x}_{t-1};\xi_{t})\right)$, if
$\gamma\leq\frac{1}{4L}$ and
$\alpha\geq\frac{8(L^{2}+L_{F}^{2})\gamma^{2}}{n}$, under Assumptions 1 and 2,
we have

$\displaystyle\sum_{t=0}^{T-1}A_{t}\leq\frac{2\alpha\sigma^{2}T}{n}+\frac{\sigma^{2}}{n\alpha
B_{0}}.$

This leads us to the corollary below:

######  Corollary 6.

For ErrorCompensatedX, under Assumptions 1 and 2, setting
$\gamma=\min\left\\{\frac{1}{4L},\left(\frac{n^{2}}{\sigma^{2}T}\right)^{\frac{1}{3}},\left(\frac{n}{\epsilon^{2}T}\right)^{\frac{1}{7}}\right\\}$,
$\alpha_{t}=\frac{8L^{2}\gamma^{2}}{n}$,
$B_{0}=\frac{\sigma^{\frac{8}{3}}T^{\frac{1}{3}}}{n^{\frac{2}{3}}}$, and
$\mathscr{A}(\bm{x}_{t};\xi_{t})=\frac{1}{\alpha_{t}}\left(\nabla
F(\bm{x}_{t};\xi_{t})-(1-\alpha_{t})\nabla F(\bm{x}_{t-1};\xi_{t})\right)$, we
have

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f(\bm{x}_{t})\|^{2}\lesssim\left(\frac{\sigma}{nT}\right)^{\frac{2}{3}}+\left(\frac{\epsilon^{2}}{nT^{6}}\right)^{\frac{1}{7}}+\frac{1}{T}.$

The leading term admits the order of
$\mathcal{O}\left(1/{(nT)^{\frac{2}{3}}}\right)$, which is the same as
uncompressed training (Yuan et al.,, 2020).

####  4.2.3 Implicit Gradient Transport (IGT)

For IGT, we need to make some extra assumptions (as listed below) for
theoretical analysis.

######  Assumption 3.

The Hessian $\nabla^{2}f(\cdot)$ is $\rho$-Lipschitz continuous, i.e., for
every $\bm{x},~{}\bm{y}\in\mathbb{R}^{d}$,

$\displaystyle\left\|\nabla^{2}f(\bm{x})-\nabla^{2}f(\bm{y})\right\|\leq\rho\|\bm{x}-\bm{y}\|,\quad\forall\bm{x},\bm{y}.$

The magnitude of the stochastic gradient is upper bounded, i.e.,

$\displaystyle\mathbb{E}\|\nabla F(\bm{x};\xi)-\nabla
F(\bm{y};\xi)\|^{2}\leq\Delta^{2},\quad\forall\bm{x},\bm{y}.$

Now we are ready to present the result of IGT:

######  Theorem 7.

Setting $\mathscr{A}(\bm{x}_{t};\xi_{t})=\nabla
F\left(\bm{x}_{t}+\frac{1-\alpha_{t}}{\alpha_{t}}(\bm{x}_{t}-\bm{x}_{t-1});\xi_{t}\right)$,
if $\gamma\leq\frac{1}{2L}$, under Assumptions 1, 2 and 3, we have

$\displaystyle\sum_{t=0}^{T-1}A_{t}\leq\frac{\alpha\sigma^{2}T}{n}+\frac{\sigma^{2}}{\alpha
nB_{0}}+\frac{\rho^{2}\gamma^{4}\Delta^{4}T}{\alpha^{4}}.$

This leads us to the corollary below:

######  Corollary 8.

For ErrorCompensatedX, under Assumptions 1, 2 and 3, by setting
$\gamma=\min\left\\{\frac{1}{2L},\left(\frac{n^{4}}{\sigma^{8}T^{5}}\right)^{\frac{1}{9}},\left(\frac{n}{\epsilon^{2}T}\right)^{\frac{1}{7}}\right\\}$,
$\alpha=\left(\frac{n^{5}}{\sigma^{8}T^{4}}\right)^{\frac{1}{9}}$ and
$B_{0}=1$, we have

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f(\bm{x}_{t})\|^{2}\lesssim\left(\frac{\sigma^{8}}{n^{4}T^{4}}\right)^{\frac{1}{9}}+\left(\frac{\epsilon^{2}}{nT^{6}}\right)^{\frac{1}{7}}+\frac{1}{T}.$

The leading term admits the order of $\mathcal{O}(1/(nT)^{\frac{4}{9}})$,
which is even worse than that of Momentum SGD. A sharper rate of IGT for a
general non-convex loss function is still an open problem.

##  5 Numerical Experiments

In this section, we train ResNet-50 (He et al.,, 2016) on CIFAR10, which
consists of 50000 training images and 10000 testing images, each has 10
labels. We run the experiments on eight workers, each having a 1080Ti GPU. The
batch size on each worker is $16$ and the total batch size is $128$. For each
choice of $\mathscr{A}(\bm{x}_{t};\xi_{t})$, we evaluate four implementations:
1) Original algorithm without compression. 2) No compensation, which
compresses the data directly without the previous information. 3) Single
compensation, which compresses the gradient estimator with compression error
from the last step added. 4) ErrorCompensatedX.

We use the $1$-bit compression in Tang et al., (2019), which leads to an
overall $96\%$ of communication volume reduction. We find that for both STORM
and IGT, setting $\alpha_{t}=\frac{1}{1+c_{0}t}$, where $c_{0}$ is a constant
and $t$ is the training step count, would make the training faster. We grid
search the best learning rate from $\\{0.5,0.1,0.001\\}$ and $c_{0}$ from
$\\{0.1,0.05,0.001\\}$, and find that the best learning rate is $0.01$ with
$c_{0}=0.05$ for both original STORM and IGT. So we use this configuration for
the other three implementations. For Momentum, usually we will not set
$\alpha_{t}$ to be too small, therefore we only set $\alpha_{t}=0.1$, and the
best learning rate is $0.1$ after the same grid search. We set $\beta=0.3$ for
the low-pass filter in all cases.

(a) Training loss (Momentum SGD)

(b) Training loss (STORM)

(c) Training loss (IGT)

(d) Testing accuracy (Momentum SGD)

(e) Testing accuracy (STORM)

(f) Testing accuracy (IGT)

Figure 2: Epoch-wise convergence comparison on ResNet-50 for Momenum SGD (left
column), STORM (middle column), and IGT (right column) with different
communication implementations. We do not include the result of no compensation
because it diverges after a few steps of training.

As illustrated in Figure 2, for both STORM and IGT, ErrorCompensatedX achieves
almost the same convergence speed with the original algorithm, while Single
Compensation fails to achieve this. We find that with increasing magnitude of
$c_{0}$, this gap of convergence speed would increase, which further validate
our claim that ErrorCompensatedX is more essential when $\alpha_{t}$ gets
small. For Momentum SGD, all the three implementations (except compression
without error compensation) achieves similar convergence speed. This is
because $\alpha_{t}=0.1$ is comparably large.

##  6 Conclusion and Remarks

In this paper, we address an important problem for communication efficient
distributed training: how to fully compensate the compression error for
variance reduced optimization algorithms. In our paper, we consider a more
general class of optimization algorithms (including SGD and Momentum SGD), and
we propose a novel method: ErrorCompensatedX, which utilize the compression
error from the last two steps, in order to fully compensate the history
compression error while previous method fails to do. From the theoretical
perspective, we provide a unified theoretical analysis framework that gives an
intuitive evaluation for the side-effect of the compression, and shows that
ErrorCompensatedX admits the same asymptotic convergence rate with each of the
original algorithm. Numerical experiments are implemented to show
ErrorCompensatedX’s convergence and its better performance comparing to other
implementations.

## References

  * Alistarh et al., (2017) Alistarh, D., Grubic, D., Li, J., Tomioka, R., & Vojnovic, M. (2017).  Qsgd: Communication-efficient sgd via gradient quantization and encoding.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, & R. Garnett (Eds.), Advances in Neural Information Processing Systems, volume 30 (pp. 1709–1720).: Curran Associates, Inc.
  * Arnold et al., (2019) Arnold, S. M. R., Manzagol, P.-A., Babanezhad, R., Mitliagkas, I., & Roux, N. L. (2019).  Reducing the variance in online optimization by transporting past gradients.
  * Basu et al., (2019) Basu, D., Data, D., Karakus, C., & Diggavi, S. (2019).  Qsparse-local-sgd: Distributed sgd with quantization, sparsification and local computations.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 32 (pp. 14695–14706). Curran Associates, Inc.
  * Chen et al., (2020) Chen, C.-Y., Ni, J., Lu, S., Cui, X., Chen, P.-Y., Sun, X., Wang, N., Venkataramani, S., Srinivasan, V. V., Zhang, W., & Gopalakrishnan, K. (2020).  Scalecom: Scalable sparsified gradient compression for communication-efficient distributed training.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, & H. Lin (Eds.), Advances in Neural Information Processing Systems, volume 33 (pp. 13551–13563).: Curran Associates, Inc.
  * Cutkosky & Mehta, (2020) Cutkosky, A. & Mehta, H. (2020).  Momentum improves normalized SGD.  In H. D. III & A. Singh (Eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research (pp. 2260–2268).: PMLR.
  * Defazio et al., (2014) Defazio, A., Bach, F., & Lacoste-Julien, S. (2014).  Saga: A fast incremental gradient method with support for non-strongly convex composite objectives.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, & K. Q. Weinberger (Eds.), Advances in Neural Information Processing Systems, volume 27 (pp. 1646–1654).: Curran Associates, Inc.
  * Gorbunov et al., (2020) Gorbunov, E., Kovalev, D., Makarenko, D., & Richtárik, P. (2020).  Linearly converging error compensated sgd.
  * He et al., (2016) He, K., Zhang, X., Ren, S., & Sun, J. (2016).  Deep residual learning for image recognition.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (pp. 770–778).
  * Horváth et al., (2019) Horváth, S., Kovalev, D., Mishchenko, K., Stich, S., & Richtárik, P. (2019).  Stochastic distributed learning with gradient quantization and variance reduction.
  * Huang et al., (2020) Huang, F., Tao, L., & Chen, S. (2020).  Accelerated stochastic gradient-free and projection-free methods.  In H. D. III & A. Singh (Eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research (pp. 4519–4530).: PMLR.
  * Ivkin et al., (2019) Ivkin, N., Rothchild, D., Ullah, E., braverman, V., Stoica, I., & Arora, R. (2019).  Communication-efficient distributed sgd with sketching.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 32 (pp. 13144–13154). Curran Associates, Inc.
  * Johnson & Zhang, (2013) Johnson, R. & Zhang, T. (2013).  Accelerating stochastic gradient descent using predictive variance reduction.  In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, & K. Q. Weinberger (Eds.), Advances in Neural Information Processing Systems, volume 26 (pp. 315–323).: Curran Associates, Inc.
  * Li et al., (2020) Li, C. J., Mou, W., Wainwright, M. J., & Jordan, M. I. (2020).  Root-sgd: Sharp nonasymptotics and asymptotic efficiency in a single algorithm.
  * Liu et al., (2020) Liu, X., Li, Y., Tang, J., & Yan, M. (2020).  A double residual compression algorithm for efficient distributed learning.  In S. Chiappa & R. Calandra (Eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research (pp. 133–143).: PMLR.
  * Mishchenko et al., (2019) Mishchenko, K., Gorbunov, E., Takac, M., & Richtarik, P. (2019).  Distributed learning with compressed gradient differences.
  * Nguyen et al., (2017) Nguyen, L. M., Liu, J., Scheinberg, K., & Takac, M. (2017).  Sarah: A novel method for machine learning problems using stochastic recursive gradient.  In D. Precup & Y. W. Teh (Eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research (pp. 2613–2621). International Convention Centre, Sydney, Australia: PMLR.
  * Phuong & Phong, (2020) Phuong, T. T. & Phong, L. T. (2020).  Distributed sgd with flexible gradient compression.  IEEE Access, 8, 64707–64717.
  * Seide et al., (2014) Seide, F., Fu, H., Droppo, J., Li, G., & Yu, D. (2014).  1-bit stochastic gradient descent and application to data-parallel distributed training of speech dnns.  In Interspeech 2014.
  * Shi et al., (2019) Shi, S., Wang, Q., Zhao, K., Tang, Z., Wang, Y., Huang, X., & Chu, X. (2019).  A distributed synchronous sgd algorithm with global top-k sparsification for low bandwidth networks.  In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS) (pp. 2238–2247).
  * (20) Stich, S. U., Cordonnier, J.-B., & Jaggi, M. (2018a).  Sparsified sgd with memory.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 31 (pp. 4447–4458). Curran Associates, Inc.
  * (21) Stich, S. U., Cordonnier, J.-B., & Jaggi, M. (2018b).  Sparsified sgd with memory.  In Advances in Neural Information Processing Systems (pp. 4447–4458).
  * Sun et al., (2019) Sun, J., Chen, T., Giannakis, G., & Yang, Z. (2019).  Communication-efficient distributed learning via lazily aggregated quantized gradients.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 32 (pp. 3370–3380). Curran Associates, Inc.
  * Tang et al., (2019) Tang, H., Yu, C., Lian, X., Zhang, T., & Liu, J. (2019).  Doublesqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression.  In International Conference on Machine Learning (pp. 6155–6165).: PMLR.
  * Vogels et al., (2019) Vogels, T., Karimireddy, S. P., & Jaggi, M. (2019).  Powersgd: Practical low-rank gradient compression for distributed optimization.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 32 (pp. 14259–14268). Curran Associates, Inc.
  * Vogels et al., (2020) Vogels, T., Karimireddy, S. P., & Jaggi, M. (2020).  Powergossip: Practical low-rank communication compression in decentralized deep learning.
  * Wang et al., (2020) Wang, J., Tantia, V., Ballas, N., & Rabbat, M. (2020).  Slowmo: Improving communication-efficient distributed sgd with slow momentum.  In International Conference on Learning Representations.
  * Wu et al., (2018) Wu, J., Huang, W., Huang, J., & Zhang, T. (2018).  Error compensated quantized SGD and its applications to large-scale distributed optimization.  CoRR, abs/1806.08054.
  * Xie et al., (2020) Xie, C., Zheng, S., Koyejo, O., Gupta, I., Li, M., & Lin, H. (2020).  Cser: Communication-efficient sgd with error reset.
  * Yu et al., (2019) Yu, Y., Wu, J., & Huang, L. (2019).  Double quantization for communication-efficient distributed optimization.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 32 (pp. 4438–4449). Curran Associates, Inc.
  * Yuan et al., (2020) Yuan, H., Lian, X., Liu, J., & Zhou, Y. (2020).  Stochastic recursive momentum for policy gradient methods.
  * Zhang et al., (2015) Zhang, S., Choromanska, A., & LeCun, Y. (2015).  Deep learning with elastic averaging sgd.
  * Zhao et al., (2019) Zhao, S.-Y., Gao, H., & Li, W.-J. (2019).  On the convergence of memory-based distributed sgd.
  * (33) Zheng, S., Huang, Z., & Kwok, J. (2019a).  Communication-efficient distributed blockwise momentum sgd with error-feedback.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems, volume 32 (pp. 11450–11460).: Curran Associates, Inc.
  * (34) Zheng, S., Huang, Z., & Kwok, J. (2019b).  Communication-efficient distributed blockwise momentum sgd with error-feedback.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 32 (pp. 11450–11460). Curran Associates, Inc.

Supplementary

In the supplementary, we first prove the updating rule of ErrorCompensatedX.
Then we will present the detailed proof for Theorem 1 followed by the detailed
convergence rate result for each algorithm.

##  7 Updating rule of ErrorCompensatedX

The updating rule of Algorithm 1 admits the form

$\displaystyle\overline{\bm{e}}_{t}=$
$\displaystyle(1-\beta)\overline{\bm{e}}_{t-1}+\beta\left(\frac{\alpha_{t-1}}{\alpha_{t}}(2-\alpha_{t})\overline{\bm{\delta}}_{t-1}+\frac{\alpha_{t-2}}{\alpha_{t}}(1-\alpha_{t})\overline{\bm{\delta}}_{t-2}\right),$
$\displaystyle\bm{v}_{t}=$
$\displaystyle(1-\alpha_{t})\bm{v}_{t-1}+\alpha_{t}\overline{\bm{b}}_{t}(\bm{x}_{t})-\alpha_{t}\overline{\bm{\delta}}_{t}+\alpha_{t}\overline{\bm{e}}_{t},$
$\displaystyle\bm{x}_{t+1}=$ $\displaystyle\bm{x}_{t}-\gamma\bm{v}_{t}.$

where

$\displaystyle\overline{\bm{e}}_{t}:=$
$\displaystyle\frac{1}{n}\sum_{i}\bm{e}_{t}^{(i)}+\bm{e}_{t},$
$\displaystyle\overline{\bm{\delta}}_{t}:=$
$\displaystyle\bm{\delta}_{t}+\frac{1}{n}\sum_{i=1}^{n}\bm{\delta}_{t}^{(i)},$
$\displaystyle\overline{\bm{b}}_{t}(\bm{x}):=$
$\displaystyle\frac{1}{n}\sum_{i}\mathscr{A}\left(\bm{x}_{t};\xi_{t}^{(i)}\right).$

###### Proof.

From the algorithm description in Algorithm 1, we shall see that we are
essentially using $\bm{v}_{t}$ as the gradient estimator of the full gradient.
From the updating rule of $\bm{v}_{t}$, we have

$\displaystyle\bm{v}_{t}=$
$\displaystyle(1-\alpha_{t})\bm{v}_{t-1}+\alpha_{t}C_{\omega}\left[\Delta_{t}\right]$
$\displaystyle=$
$\displaystyle(1-\alpha_{t})\bm{v}_{t-1}+\alpha_{t}\left(\Delta_{t}-\bm{\delta}_{t}\right)$
$\displaystyle=$
$\displaystyle(1-\alpha_{t})\bm{v}_{t-1}+\frac{\alpha_{t}}{n}\sum_{i}C_{\omega}\left[\Delta_{t}^{(i)}\right]+\alpha_{t}\bm{e}_{t}-\alpha_{t}\bm{\delta}_{t}$
$\displaystyle=$
$\displaystyle(1-\alpha_{t})\bm{v}_{t-1}+\frac{\alpha_{t}}{n}\sum_{i}\left(\Delta_{t}^{{(i)}}-\bm{\delta}_{t}^{(i)}\right)+\alpha_{t}\bm{e}_{t}-\alpha_{t}\bm{\delta}_{t}$
$\displaystyle=$
$\displaystyle(1-\alpha_{t})\bm{v}_{t-1}+\frac{\alpha_{t}}{n}\sum_{i}\left(\mathscr{A}\left(\bm{x}_{t};\xi_{t}^{(i)}\right)+\bm{e}_{t}^{(i)}-\bm{\delta}_{t}^{(i)}\right)+\alpha_{t}\bm{e}_{t}-\alpha_{t}\bm{\delta}_{t}$
$\displaystyle=$
$\displaystyle(1-\alpha)\bm{v}_{t-1}+\alpha_{t}\overline{\bm{b}}_{t}(\bm{x}_{t})+\alpha_{t}\overline{\bm{e}}_{t}-\alpha_{t}\overline{\bm{\delta}}_{t}.$

Notice that in the deduction above we continuously using the fact that
$C_{\omega}[\bm{x}]=\bm{x}-\bm{\delta}$. For $\overline{\bm{e}}_{t}$, we have

$\displaystyle\overline{\bm{e}}_{t}=$
$\displaystyle\frac{1}{n}\sum_{i}\bm{e}_{t}^{(i)}+\bm{e}_{t}$ $\displaystyle=$
$\displaystyle\frac{1-\beta}{n}\sum_{i}\bm{e}_{t-1}^{(i)}+\frac{\beta}{n}\sum_{i}\left(\frac{\alpha_{t-1}}{\alpha_{t}}(2-\alpha_{t})\delta_{t-1}^{(i)}+\frac{\alpha_{t-2}}{\alpha_{t}}(1-\alpha_{t})\delta_{t-2}^{(i)}\right)$
$\displaystyle+(1-\beta)\bm{e}_{t-1}+\beta\left(\frac{\alpha_{t-1}}{\alpha_{t}}(2-\alpha_{t})\delta_{t-1}+\frac{\alpha_{t-2}}{\alpha_{t}}(1-\alpha_{t})\delta_{t-2}\right)$
$\displaystyle=$
$\displaystyle(1-\beta)\overline{\bm{e}}_{t-1}+\beta\left(\frac{\alpha_{t-1}}{\alpha_{t}}(2-\alpha_{t})\overline{\bm{\delta}}_{t-1}+\frac{\alpha_{t-2}}{\alpha_{t}}(1-\alpha_{t})\overline{\bm{\delta}}_{t-2}\right),$

which completes the proof. ∎

##  8 General Formulation of the Updating Rule

As mentioned in Section 4, all the error compensation mentioned so far admits
the updating rule of (4) and (5). Therefore in Table 2 we list the specific
choice of parameters for each algorithm.

| $\eta_{1,t}$ | $\eta_{2,t}$ | $c_{1,t}$ | $c_{2,t}$
---|---|---|---|---
Without Compensation | $1$ | $0$ | $0$ | $0$
Single Compensation | $1$ | $1$ | $1$ | $0$
ErrorCompensatedX | $\alpha_{t}$ | $\alpha_{t}$ | $2-\alpha_{t}$ | $1-\alpha_{t}$
Table 2: Different choices of $\eta_{1,t}$, $\eta_{2,t}$, $c_{1,t}$, and
$c_{2,t}$ for each algorithm.

##  9 Proof of Theorems

###  9.1 Proof of Theorem 1

###### Proof.

In the view of $\\{\hat{\bm{x}}_{t}\\}$, we have

$\displaystyle\mathbb{E}f(\hat{\bm{x}}_{t+1})-\mathbb{E}f(\hat{\bm{x}}_{t})$
$\displaystyle\leq$ $\displaystyle\mathbb{E}\langle\nabla
f(\hat{\bm{x}}_{t}),\hat{\bm{x}}_{t+1}-\hat{\bm{x}}_{t}\rangle+\frac{L}{2}\mathbb{E}\|\hat{\bm{x}}_{t+1}-\hat{\bm{x}}_{t}\|^{2}$
$\displaystyle=$ $\displaystyle-\gamma\mathbb{E}\langle\nabla
f(\hat{\bm{x}}_{t}),\bm{u}_{t}\rangle+\frac{L\gamma^{2}}{2}\mathbb{E}\|\bm{u}_{t}\|^{2}$
$\displaystyle=$ $\displaystyle-\gamma\mathbb{E}\langle\nabla
f(\hat{\bm{x}}_{t}),\hat{\bm{u}}_{t}+(\bm{u}_{t}-\hat{\bm{u}}_{t})\rangle+\frac{L\gamma^{2}}{2}\mathbb{E}\|\hat{\bm{u}}_{t}+(\bm{u}_{t}-\hat{\bm{u}}_{t})\|^{2}$
$\displaystyle\leq$ $\displaystyle-\gamma\mathbb{E}\langle\nabla
f(\hat{\bm{x}}_{t}),\hat{\bm{u}}_{t}\rangle-\gamma\mathbb{E}\langle\nabla
f(\hat{\bm{x}}_{t}),\bm{u}_{t}-\hat{\bm{u}}_{t}\rangle+L\gamma^{2}\mathbb{E}\|\hat{\bm{u}}_{t}\|^{2}+L\gamma^{2}\mathbb{E}\|\bm{u}_{t}-\hat{\bm{u}}_{t}\|^{2}$
$\displaystyle\leq$ $\displaystyle-\gamma\mathbb{E}\langle\nabla
f(\hat{\bm{x}}_{t}),\hat{\bm{u}}_{t}\rangle+\frac{\gamma}{4}\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}+\gamma\mathbb{E}\|\bm{u}_{t}-\hat{\bm{u}}_{t}\|^{2}+L\gamma^{2}\mathbb{E}\|\hat{\bm{u}}_{t}\|^{2}+L\gamma^{2}\mathbb{E}\|\bm{u}_{t}-\hat{\bm{u}}_{t}\|^{2}$
$\displaystyle\leq$ $\displaystyle-\frac{\gamma}{2}\left(\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}+\mathbb{E}\|\hat{\bm{u}}_{t}\|^{2}-\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})-\hat{\bm{u}}_{t}\|^{2}\right)+\frac{\gamma}{4}\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}$
$\displaystyle+\gamma\|\bm{u}_{t}-\hat{\bm{u}}_{t}\|^{2}+L\gamma^{2}\mathbb{E}\|\hat{\bm{u}}_{t}\|^{2}+L\gamma^{2}\mathbb{E}\|\bm{u}_{t}-\hat{\bm{u}}_{t}\|^{2}$
$\displaystyle\leq$ $\displaystyle-\frac{\gamma}{8}\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}-\frac{\gamma}{2}\left((1-2L\gamma)\mathbb{E}\|\hat{\bm{u}}_{t}\|^{2}-\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})-\hat{\bm{u}}_{t}\|^{2}+\frac{\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}}{4}\right)$
$\displaystyle+(1+L\gamma)\gamma\mathbb{E}\|\bm{u}_{t}-\hat{\bm{u}}_{t}\|^{2}.$

Summing up the inequality above from $t=0$ to $t=T$, with rearrangement we get

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}$ $\displaystyle\leq$
$\displaystyle\frac{8(f(\hat{\bm{x}}_{0})-f(\hat{\bm{x}}_{T}))}{\gamma
T}-\frac{4}{T}\sum_{t=0}^{T-1}\left((1-2L\gamma)\mathbb{E}\|\hat{\bm{u}}_{t}\|^{2}-\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})-\hat{\bm{u}}_{t}\|^{2}+\frac{\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}}{4}\right)$
$\displaystyle+\frac{8+8L\gamma}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{u}_{t}-\hat{\bm{u}}_{t}\|^{2}$
$\displaystyle\leq$ $\displaystyle\frac{8(f(\bm{x}_{0})-f^{*})}{\gamma
T}-\frac{4}{T}\sum_{t=0}^{T-1}\left((1-2L\gamma)\mathbb{E}\|\hat{\bm{u}}_{t}\|^{2}-\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})-\hat{\bm{u}}_{t}\|^{2}+\frac{\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}}{4}\right)$
$\displaystyle+\frac{8+8L\gamma}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{u}_{t}-\hat{\bm{u}}_{t}\|^{2}.$
(8)

In order to upper bound $\mathbb{E}\|\bm{u}_{t}-\hat{\bm{u}}_{t}\|^{2}$, we
have

$\displaystyle\mathbb{E}\|\bm{u}_{t}-\hat{\bm{u}}_{t}\|^{2}$ $\displaystyle=$
$\displaystyle\mathbb{E}\|(1-\alpha)(\bm{u}_{t-1}-\hat{\bm{u}}_{t-1})+\alpha(\mathscr{A}(\bm{x}_{t};\xi_{t})-\mathscr{A}(\hat{\bm{x}}_{t};\xi_{t}))\|^{2}$
$\displaystyle\leq$
$\displaystyle\left(1+\alpha\right)\mathbb{E}\|(1-\alpha)(\bm{u}_{t-1}-\hat{\bm{u}}_{t-1})\|^{2}+\left(1+\frac{1}{\alpha}\right)\mathbb{E}\|\alpha(\mathscr{A}(\bm{x}_{t};\xi_{t})-\mathscr{A}(\hat{\bm{x}}_{t};\xi_{t}))\|^{2}$
$\displaystyle=$
$\displaystyle\left(1-\alpha^{2}\right)(1-\alpha)\mathbb{E}\|\bm{u}_{t-1}-\hat{\bm{u}}_{t-1}\|^{2}+\left(\alpha^{2}+\alpha\right)\mathbb{E}\|\mathscr{A}(\bm{x}_{t};\xi_{t})-\mathscr{A}(\hat{\bm{x}}_{t};\xi_{t})\|^{2}$
$\displaystyle\leq$
$\displaystyle\left(1-\alpha\right)\mathbb{E}\|\bm{u}_{t-1}-\hat{\bm{u}}_{t-1}\|^{2}+2\alpha\mathbb{E}\|\mathscr{A}(\bm{x}_{t};\xi_{t})-\mathscr{A}(\hat{\bm{x}}_{t};\xi_{t})\|^{2}$
$\displaystyle=$
$\displaystyle(1-\alpha)^{t}\mathbb{E}\|\bm{u}_{0}-\bm{u}_{0}(\bm{y})\|^{2}+2\alpha\sum_{s=0}^{t}(1-\alpha)^{t-s}\mathbb{E}\|\mathscr{A}(\bm{x}_{s};\xi_{s})-\mathscr{A}(\hat{\bm{x}}_{s};\xi_{s})\|^{2}$
$\displaystyle=$ $\displaystyle
2\alpha\sum_{s=0}^{t}(1-\alpha)^{t-s}\mathbb{E}\|\mathscr{A}(\bm{x}_{s};\xi_{s})-\mathscr{A}(\hat{\bm{x}}_{s};\xi_{s})\|^{2}\quad\text{($\bm{u}_{0}-\bm{u}_{0}(\bm{y})=\bm{0}$)}$
$\displaystyle\leq$ $\displaystyle 2\alpha
L^{2}_{\mathscr{A}}\sum_{s=0}^{t}(1-\alpha)^{t-s}\mathbb{E}\|\bm{x}_{s}-\hat{\bm{x}}_{s}\|^{2}.$

Therefore we have

$\displaystyle\sum_{t=0}^{T-1}\mathbb{E}\|\bm{u}_{t}-\hat{\bm{u}}_{t}\|^{2}\leq$
$\displaystyle 2\alpha
L^{2}_{\mathscr{A}}\sum_{t=0}^{T-1}\sum_{s=0}^{t}(1-\alpha)^{t-s}\mathbb{E}\|\bm{x}_{s}-\hat{\bm{x}}_{s}\|^{2}$
$\displaystyle=$ $\displaystyle 2\alpha
L^{2}_{\mathscr{A}}\sum_{s=0}^{T-1}\sum_{t=s}^{T-1}(1-\alpha)^{t-s}\mathbb{E}\|\bm{x}_{s}-\hat{\bm{x}}_{s}\|^{2}$
$\displaystyle\leq$ $\displaystyle
2L^{2}_{\mathscr{A}}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{x}_{t}-\hat{\bm{x}}_{t}\|^{2}.$
(9)

Combining (8) and (9) together we get

$\displaystyle\frac{1}{T}\sum_{t=0}^{T}\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}$ $\displaystyle\leq$
$\displaystyle\frac{8(f(\bm{x}_{0})-f^{*})}{\gamma
T}-\frac{4}{T}\sum_{t=0}^{T}\left((1-2L\gamma)\mathbb{E}\|\hat{\bm{u}}_{t}\|^{2}-\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})-\hat{\bm{u}}_{t}\|^{2}+\frac{\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}}{4}\right)$
$\displaystyle+\frac{16(1+L\gamma)L^{2}_{\mathscr{A}}}{T}\sum_{t=0}^{T}\mathbb{E}\|\bm{x}_{t}-\hat{\bm{x}}_{t}\|^{2}.$

Hence $\|\nabla f(\bm{x}_{t})\|^{2}$ can be upper bounded by using

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f(\bm{x}_{t})\|^{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})+(\nabla f(\bm{x}_{t})-\nabla f(\hat{\bm{x}}_{t}))\|^{2}$
$\displaystyle\leq$
$\displaystyle\frac{2}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}+\frac{2}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f(\bm{x}_{t})-\nabla f(\hat{\bm{x}}_{t})\|^{2}$ $\displaystyle\leq$
$\displaystyle\frac{2}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}+\frac{2L^{2}}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{x}_{t}-\hat{\bm{x}}_{t}\|^{2}$
$\displaystyle\leq$ $\displaystyle\frac{16(f(\bm{x}_{0})-f^{*})}{\gamma
T}-\frac{8}{T}\sum_{t=0}^{T-1}\left((1-2L\gamma)\mathbb{E}\|\hat{\bm{u}}_{t}\|^{2}-\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})-\hat{\bm{u}}_{t}\|^{2}+\frac{\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}}{4}\right)$
$\displaystyle+\frac{32(1+L\gamma)L^{2}_{\mathscr{A}}+2L^{2}}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{u}_{t}-\hat{\bm{u}}_{t}\|^{2}.$

If $L\gamma\leq 1$, we have

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f(\bm{x}_{t})\|^{2}$ $\displaystyle\leq$
$\displaystyle\frac{16(f(\bm{x}_{0})-f^{*})}{\gamma
T}-\frac{8}{T}\sum_{t=0}^{T-1}\left((1-2L\gamma)\mathbb{E}\|\hat{\bm{u}}_{t}\|^{2}-\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})-\hat{\bm{u}}_{t}\|^{2}+\frac{\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}}{4}\right)$
$\displaystyle+\frac{64L^{2}_{\mathscr{A}}+2L^{2}}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{x}_{t}-\hat{\bm{x}}_{t}\|^{2},$

which completes the proof. ∎

###  9.2 Proof of Theorem 3, 5 and 7

In this section, we are going to present the proof of theorems for different
gradient estimators. We start with the key lemma for Momentum SGD.

######  Lemma 9.

For two nonnegative sequences $\\{a_{t}\\}$ and $\\{b_{t}\\}$ that satisfy

$\displaystyle a_{t}\leq\rho a_{t-1}+b_{t},$

where $\rho\in(0,1)$ is a constant, we have

$\displaystyle\sum_{t=0}^{T}a_{t}\leq\frac{\sum_{t=1}^{T}b_{t}+a_{0}}{1-\rho}.$

###### Proof.

Since

$\displaystyle a_{t}\leq\rho a_{t-1}+b_{t},$

adding the inequality above from $t=1$ to $t=T$ we get

$\displaystyle\sum_{t=1}^{T}a_{t}\leq$
$\displaystyle\rho\sum_{t=0}^{T-1}a_{t}+\sum_{t=1}^{T}b_{t}$
$\displaystyle\leq$
$\displaystyle\rho\sum_{t=0}^{T}a_{t}+\sum_{t=1}^{T}b_{t}.$

Adding $a_{0}$ to both side we get

$\displaystyle\sum_{t=0}^{T}a_{t}\leq$
$\displaystyle\rho\sum_{t=0}^{T}a_{t}+\sum_{t=1}^{T}b_{t}+a_{0}$

and the proof is complete by combining the sum of $a_{t}$ and dividing both
sides by $1-\rho$. ∎

###### Proof of Theorem 3.

For Momentum SGD, denote
$\bm{m}_{t}=\alpha\sum_{s=0}^{t}(1-\alpha)^{t-s}\nabla f(\bm{x}_{s})$, then we
have

$\displaystyle\mathbb{E}\|\nabla
f(\bm{x}_{t})-\bm{u}_{t}\|^{2}-\mathbb{E}\|\bm{u}_{t}\|^{2}$ $\displaystyle=$
$\displaystyle\mathbb{E}\|\nabla f(\bm{x}_{t})\|^{2}-2\mathbb{E}\langle\nabla
f(\bm{x}_{t}),\bm{u}_{t}\rangle$ $\displaystyle=$
$\displaystyle\mathbb{E}\|\nabla f(\bm{x}_{t})\|^{2}-2\mathbb{E}\langle\nabla
f(\bm{x}_{t}),\bm{m}_{t}\rangle-2\mathbb{E}\langle\nabla
f(\bm{x}_{t}),\bm{u}_{t}-\bm{m}_{t}\rangle$ $\displaystyle=$
$\displaystyle-\mathbb{E}\|\bm{m}_{t}\|^{2}+\mathbb{E}\|\nabla
f(\bm{x}_{t})-\bm{m}_{t}\|^{2}-2\mathbb{E}\langle\nabla
f(\bm{x}_{t}),\bm{u}_{t}-\bm{m}_{t}\rangle.$ (10)

For $\mathbb{E}\|\nabla f(\bm{x}_{t})-\bm{m}_{t}\|^{2}$ we have

$\displaystyle\mathbb{E}\|\nabla f(\bm{x}_{t})-\bm{m}_{t}\|^{2}$
$\displaystyle=$ $\displaystyle\mathbb{E}\|\nabla
f(\bm{x}_{t})-(1-\alpha)\bm{m}_{t-1}-\alpha f(\bm{x}_{t})\|^{2}$
$\displaystyle=$ $\displaystyle\mathbb{E}\|(1-\alpha)(\nabla
f(\bm{x}_{t-1})-\bm{m}_{t-1}+\nabla f(\bm{x}_{t})-\nabla
f(\bm{x}_{t-1}))\|^{2}$ $\displaystyle\leq$
$\displaystyle\left(1+\alpha\right)(1-\alpha)^{2}\mathbb{E}\|\nabla
f(\bm{x}_{t-1})-\bm{m}_{t-1}\|^{2}+\left(1+\frac{1}{\alpha}\right)(1-\alpha)^{2}\mathbb{E}\|\nabla
f(\bm{x}_{t})-\nabla f(\bm{x}_{t-1}))\|^{2}$ $\displaystyle\leq$
$\displaystyle(1-\alpha)\mathbb{E}\|\nabla
f(\bm{x}_{t-1})-\bm{m}_{t-1}\|^{2}+\frac{1}{\alpha}\mathbb{E}\|\nabla
f(\bm{x}_{t})-\nabla f(\bm{x}_{t-1}))\|^{2}$ $\displaystyle\leq$
$\displaystyle(1-\alpha)\mathbb{E}\|\nabla
f(\bm{x}_{t-1})-\bm{m}_{t-1}\|^{2}+\frac{L^{2}\gamma^{2}}{\alpha}\mathbb{E}\|\bm{u}_{t}\|^{2}.$

Therefore from Lemme 9,

$\displaystyle\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f(\bm{x}_{t})-\bm{m}_{t}\|^{2}\leq$
$\displaystyle\frac{L^{2}\gamma^{2}}{\alpha^{2}}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{u}_{t}\|^{2}.$
(11)

For $\mathbb{E}\langle\nabla f(\bm{x}_{t}),\bm{u}_{t}-\bm{m}_{t}\rangle$, we
have

$\displaystyle\mathbb{E}\left\langle\nabla
f(\bm{x}_{t}),\bm{u}_{t}-\bm{m}_{t}\right\rangle=$
$\displaystyle\mathbb{E}\left\langle\nabla
f(\bm{x}_{t}),(1-\alpha)(\bm{u}_{t-1}-\bm{m}_{t-1})+\alpha(\bm{g}_{t}-\nabla
f(\bm{x}_{t}))\right\rangle$ $\displaystyle=$
$\displaystyle\mathbb{E}\left\langle\nabla
f(\bm{x}_{t}),(1-\alpha)(\bm{u}_{t-1}-\bm{m}_{t-1})\right\rangle$
$\displaystyle=$ $\displaystyle(1-\alpha)\mathbb{E}\left\langle\nabla
f(\bm{x}_{t-1}),\bm{u}_{t-1}-\bm{m}_{t-1}\right\rangle$
$\displaystyle+(1-\alpha)\mathbb{E}\left\langle\nabla f(\bm{x}_{t})-\nabla
f(\bm{x}_{t-1}),\bm{u}_{t-1}-\bm{m}_{t-1}\right\rangle,$ (12)

where $\bm{g}_{t}=\nabla F(\bm{x}_{t};\xi_{t}).$

Notice that for $\nabla f(\bm{x}_{t})-\nabla f(\bm{x}_{t-1})$, we have

$\displaystyle\mathbb{E}\left\|\nabla f(\bm{x}_{t})-\nabla
f(\bm{x}_{t-1})\right\|^{2}$ $\displaystyle\leq$ $\displaystyle
L^{2}\gamma^{2}\mathbb{E}\|\bm{u}_{t-1}-\bm{m}_{t-1}+\bm{m}_{t-1}\|^{2}$
$\displaystyle\leq$ $\displaystyle
2L^{2}\gamma^{2}\mathbb{E}\|\bm{m}_{t-1}\|^{2}+2L^{2}\gamma^{2}\mathbb{E}\|\bm{u}_{t-1}-\bm{m}_{t-1}\|^{2}.$
(13)

Combining (12) and (13) together we get

$\displaystyle\mathbb{E}\left\langle\nabla
f(\bm{x}_{t}),\bm{u}_{t}-\bm{m}_{t}\right\rangle$ $\displaystyle\leq$
$\displaystyle(1-\alpha)\mathbb{E}\left\langle\nabla
f(\bm{x}_{t-1}),\bm{u}_{t-1}-\bm{m}_{t-1}\right\rangle+(1-\alpha)\mathbb{E}\left(\frac{1}{2\gamma
L}\left\|\nabla f(\bm{x}_{t})-\nabla f(\bm{x}_{t-1})\right\|^{2}+\frac{\gamma
L}{2}\mathbb{E}\left\|\bm{u}_{t-1}-\bm{m}_{t-1}\right\|^{2}\right)$
$\displaystyle\leq$ $\displaystyle(1-\alpha)\mathbb{E}\left\langle\nabla
f(\bm{x}_{t-1}),\bm{u}_{t-1}-\bm{m}_{t-1}\right\rangle+(1-\alpha)\mathbb{E}\left(\gamma
L\mathbb{E}\|\bm{m}_{t-1}\|^{2}+\frac{3\gamma
L}{2}\mathbb{E}\left\|\bm{u}_{t-1}-\bm{m}_{t-1}\right\|^{2}\right),$

Denote $c_{t}:=\gamma L\mathbb{E}\|\bm{m}_{t-1}\|^{2}+\frac{3\gamma
L}{2}\mathbb{E}\left\|\bm{u}_{t-1}-\bm{m}_{t-1}\right\|^{2}$, then we get

$\displaystyle\mathbb{E}\left\langle\nabla
f(\bm{x}_{t}),\bm{u}_{t}-\mathbb{E}\bm{u}_{t}\right\rangle=(1-\alpha)^{t}\mathbb{E}\left\langle\nabla
f(\bm{x}_{0}),\bm{u}_{0}-\bm{m}_{0}\right\rangle+\sum_{s=1}^{t}(1-\alpha)^{t-s}c_{s}.$

Since $\mathbb{E}\mathscr{A}(\bm{x}_{0};\xi_{0})=\mathbb{E}\nabla
F(\bm{x}_{0};\xi_{0})=\nabla F(\bm{x}_{0})$, which means
$\mathbb{E}\left\langle\nabla
f(\bm{x}_{0}),\bm{u}_{0}-\bm{m}_{0}\right\rangle=0$. So the equation above
becomes

$\displaystyle\mathbb{E}\left\langle\nabla
f(\bm{x}_{t}),\bm{u}_{t}-\bm{m}_{t}\right\rangle=\sum_{s=1}^{t}(1-\alpha)^{t-s}c_{s},$

and

$\displaystyle\sum_{t=0}^{T-1}\mathbb{E}\left\langle\nabla
f(\bm{x}_{t}),\bm{u}_{t}-\mathbb{E}\bm{u}_{t}\right\rangle\leq$
$\displaystyle\frac{\sum_{t=0}^{T-1}|c_{t}|}{1-(1-\alpha)}$ $\displaystyle=$
$\displaystyle\frac{\gamma
L}{\alpha}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{m}_{t}\|^{2}+\frac{3\gamma
L}{2\alpha}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{u}_{t}-\bm{m}_{t}\|^{2}.$ (14)

Combing (14), (11) and (10), we get

$\displaystyle\sum_{t=0}^{T-1}\left(\mathbb{E}\|\nabla
f(\bm{x}_{t})-\bm{u}_{t}\|^{2}-(1-2L\gamma)\mathbb{E}\|\bm{u}_{t}\|^{2}\right)$
$\displaystyle\leq$
$\displaystyle-\sum_{t=0}^{T-1}\mathbb{E}\|\bm{m}_{t}\|^{2}+\left(\frac{L^{2}\gamma^{2}}{\alpha^{2}}+2L\gamma\right)\sum_{t=0}^{T-1}\mathbb{E}\|\bm{u}_{t}\|^{2}+\frac{2\gamma
L}{\alpha}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{m}_{t}\|^{2}+\frac{3\gamma
L}{\alpha}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{u}_{t}-\bm{m}_{t}\|^{2}$
$\displaystyle=$
$\displaystyle-\left(1-\frac{2L^{2}\gamma^{2}}{\alpha^{2}}-4L\gamma-\frac{2\gamma
L}{\alpha}\right)\sum_{t=0}^{T-1}\mathbb{E}\|\bm{m}_{t}\|^{2}+\left(\frac{2L^{2}\gamma^{2}}{\alpha^{2}}+\frac{3\gamma
L}{\alpha}+4L\gamma\right)\sum_{t=0}^{T-1}\mathbb{E}\|\bm{u}_{t}-\bm{m}_{t}\|^{2},$
(15)

For $\mathbb{E}\left\|\bm{u}_{t}-\bm{m}_{t}\right\|^{2}$, we have

$\displaystyle\mathbb{E}\|\bm{u}_{t}-\bm{m}_{t}\|^{2}=$
$\displaystyle\mathbb{E}\|(1-\alpha)(\bm{u}_{t-1}-\bm{m}_{t-1})+\alpha(\bm{g}_{t}-\nabla
f(\bm{x}_{t}))\|^{2}$ $\displaystyle=$
$\displaystyle\mathbb{E}_{1:t-1}\mathbb{E}_{t}\|(1-\alpha)(\bm{u}_{t-1}-\bm{m}_{t-1})+\alpha(\bm{g}_{t}-\nabla
f(\bm{x}_{t}))\|^{2}$ $\displaystyle=$
$\displaystyle\mathbb{E}_{1:t-1}\mathbb{E}_{t}\|(1-\alpha)(\bm{u}_{t-1}-\bm{m}_{t-1})\|^{2}+\mathbb{E}_{1:t-1}\mathbb{E}_{t}\|\alpha(\bm{g}_{t}-\nabla
f(\bm{x}_{t}))\|^{2}$ $\displaystyle\leq$
$\displaystyle(1-\alpha)^{2}\mathbb{E}\|\bm{u}_{t-1}-\bm{m}_{t-1}\|^{2}+\alpha^{2}\sigma^{2}$
$\displaystyle\leq$
$\displaystyle(1-\alpha)\mathbb{E}\|\bm{u}_{t-1}-\bm{m}_{t-1}\|^{2}+\alpha^{2}\sigma^{2}$
$\displaystyle=$
$\displaystyle(1-\alpha)^{t}\mathbb{E}\|\bm{u}_{0}-\bm{m}_{0}\|^{2}+\alpha^{2}\sum_{s=1}^{t}(1-\alpha)^{t-s}\sigma^{2}.$

Therefore we have

$\displaystyle\mathbb{E}\|\bm{u}_{t}-\bm{m}_{t}\|^{2}\leq\alpha\sigma^{2}.$

So (15) becomes

$\displaystyle\sum_{t=0}^{T-1}\left(\mathbb{E}\|\nabla
f(\bm{x}_{t})-\bm{u}_{t}\|^{2}-(1-2L\gamma)\mathbb{E}\|\bm{u}_{t}\|^{2}\right)$
$\displaystyle\leq$
$\displaystyle-\left(1-\frac{2L^{2}\gamma^{2}}{\alpha^{2}}-\frac{4\gamma
L}{\alpha}-2L\gamma\right)\sum_{t=0}^{T-1}\mathbb{E}\|\bm{m}_{t}\|^{2}+\left(\frac{2L^{2}\gamma^{2}}{\alpha^{2}}+\frac{3\gamma
L}{2\alpha}+4L\gamma\right)\sum_{t=0}^{T-1}\alpha\sigma^{2}$

Therefore, for Momentum SGD

$\displaystyle\sum_{t=0}^{T-1}A_{t}=$
$\displaystyle\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
f({\bm{x}}_{t})-{\bm{u}}_{t}\|^{2}-(1-2L\gamma)\mathbb{E}\|{\bm{u}}_{t}\|^{2}-\frac{1}{4}\mathbb{E}\|\nabla
f(\bm{x}_{t})\|^{2}$ $\displaystyle\leq$
$\displaystyle-\left(1-\frac{2L^{2}\gamma^{2}}{\alpha^{2}}-\frac{4\gamma
L}{\alpha}-2L\gamma\right)\sum_{t=0}^{T-1}\mathbb{E}\|\bm{m}_{t}\|^{2}+\left(\frac{2L\gamma}{\alpha}+\frac{3}{2}+4\alpha\right)\gamma
LT\sigma^{2}.$

So if $\gamma L\leq\frac{\alpha}{12}$ and $\gamma L\leq\frac{1}{4}$, we have

$\displaystyle\sum_{t=0}^{T-1}A_{t}\leq\frac{17\gamma L\sigma^{2}T}{3}$

∎

###### Proof of Theorem 5.

For STROM, the most important part is to upper bound
$\sum_{t=0}^{T-1}\mathbb{E}\|\bm{u}_{t}-\nabla f(\bm{x}_{t})\|^{2}$. Therefore
we first focus on this term.

Denoting $\bm{e}_{t}:=\bm{u}_{t}-\nabla f(\bm{x}_{t})$ and
$\overline{\bm{g}}_{t}(\bm{x}):=\frac{1}{n}\sum_{i}\nabla
F(\bm{x};\xi_{t}^{(i)})$, we get

$\displaystyle\mathbb{E}\|\bm{e}_{t}\|^{2}$ $\displaystyle=$
$\displaystyle\mathbb{E}\|(1-\alpha)\bm{e}_{t-1}+(\overline{\bm{g}}_{t}(\bm{x}_{t})-\nabla
f(\bm{x}_{t}))-(1-\alpha)(\overline{\bm{g}}_{t}(\bm{x}_{t-1})-\nabla
f(\bm{x}_{t-1}))\|^{2}$ $\displaystyle=$
$\displaystyle\mathbb{E}\|(1-\alpha)\bm{e}_{t-1}\|^{2}+\mathbb{E}\|(\overline{\bm{g}}_{t}(\bm{x}_{t})-\nabla
f(\bm{x}_{t}))-(1-\alpha)(\overline{\bm{g}}_{t}(\bm{x}_{t-1})-\nabla
f(\bm{x}_{t-1}))\|^{2}$ $\displaystyle=$
$\displaystyle(1-\alpha)^{2}\mathbb{E}\|\bm{e}_{t-1}\|^{2}+\mathbb{E}\left\|\alpha(\overline{\bm{g}}_{t}(\bm{x}_{t})-\nabla
f(\bm{x}_{t}))+(1-\alpha)\left(\overline{\bm{g}}_{t}(\bm{x}_{t})-\overline{\bm{g}}_{t}(\bm{x}_{t-1})+\nabla
f(\bm{x}_{t-1})-\nabla f(\bm{x}_{t})\right)\right\|^{2}$ $\displaystyle\leq$
$\displaystyle(1-\alpha)^{2}\mathbb{E}\|\bm{e}_{t-1}\|^{2}+2\alpha^{2}\mathbb{E}\left\|\overline{\bm{g}}_{t}(\bm{x}_{t})-\nabla
f(\bm{x}_{t})\right\|^{2}+2(1-\alpha)^{2}\mathbb{E}\left\|\overline{\bm{g}}_{t}(\bm{x}_{t})-\overline{\bm{g}}_{t}(\bm{x}_{t-1})+\nabla
f(\bm{x}_{t-1})-\nabla f(\bm{x}_{t})\right\|^{2}$ $\displaystyle=$
$\displaystyle(1-\alpha)^{2}\mathbb{E}\|\bm{e}_{t-1}\|^{2}+2\alpha^{2}\mathbb{E}\left\|\overline{\bm{g}}_{t}(\bm{x}_{t})-\nabla
f(\bm{x}_{t})\right\|^{2}$
$\displaystyle+\frac{2(1-\alpha)^{2}}{n^{2}}\mathbb{E}\left\|\sum_{i=1}^{n}\left(\nabla
F(\bm{x}_{t};\xi_{t}^{(i)})-\nabla f_{i}(\bm{x}_{t})-\nabla
F(\bm{x}_{t-1};\xi_{t}^{(i)})+\nabla f_{i}(\bm{x}_{t-1})\right)\right\|^{2}$
$\displaystyle=$
$\displaystyle(1-\alpha)^{2}\mathbb{E}\|\bm{e}_{t-1}\|^{2}+2\alpha^{2}\mathbb{E}\left\|\overline{\bm{g}}_{t}(\bm{x}_{t})-\nabla
f(\bm{x}_{t})\right\|^{2}$
$\displaystyle+\frac{2(1-\alpha)^{2}}{n^{2}}\sum_{i=1}^{n}\mathbb{E}\left\|\nabla
F(\bm{x}_{t};\xi_{t}^{(i)})-\nabla f_{i}(\bm{x}_{t})-\nabla
F(\bm{x}_{t-1};\xi_{t}^{(i)})+\nabla f_{i}(\bm{x}_{t-1})\right\|^{2}$
$\displaystyle\leq$
$\displaystyle(1-\alpha)^{2}\mathbb{E}\|\bm{e}_{t-1}\|^{2}+2\alpha^{2}\mathbb{E}\left\|\overline{\bm{g}}_{t}(\bm{x}_{t})-\nabla
f(\bm{x}_{t})\right\|^{2}$
$\displaystyle+\frac{4(1-\alpha)^{2}}{n^{2}}\sum_{i=1}^{n}\mathbb{E}\left\|\nabla
F(\bm{x}_{t};\xi_{t}^{(i)})-\nabla
F(\bm{x}_{t-1};\xi_{t}^{(i)})\right\|^{2}+\frac{4(1-\alpha)^{2}}{n^{2}}\sum_{i=1}^{n}\mathbb{E}\left\|\nabla
f_{i}(\bm{x}_{t})-\nabla f_{i}(\bm{x}_{t-1})\right\|^{2}$ $\displaystyle\leq$
$\displaystyle(1-\alpha)^{2}\mathbb{E}\|\bm{e}_{t-1}\|^{2}+\frac{2\alpha^{2}\sigma^{2}}{n}+\frac{4(1-\alpha)^{2}(L^{2}+L_{F}^{2})}{n}\mathbb{E}\|\bm{x}_{t}-\bm{x}_{t-1}\|^{2}$
$\displaystyle\leq$
$\displaystyle(1-\alpha)^{2}\mathbb{E}\|\bm{e}_{t-1}\|^{2}+\frac{2\alpha^{2}\sigma^{2}}{n}+\frac{4(1-\alpha)^{2}(L^{2}+L_{F}^{2})\gamma^{2}}{n}\mathbb{E}\|\bm{u}_{t-1}\|^{2}.$
(16)

Using Lemma 9, we get

$\displaystyle\sum_{t=0}^{T-1}\mathbb{E}\|\bm{e}_{t}\|^{2}\leq$
$\displaystyle\frac{\sum_{t=0}^{T-1}\left(\frac{2\alpha^{2}\sigma^{2}}{n}+\frac{4(1-\alpha)^{2}(L^{2}+L_{F}^{2})\gamma^{2}}{n}\mathbb{E}\|\bm{u}_{t-1}\|^{2}\right)+\mathbb{E}\|\bm{u}_{0}-\nabla
f(\bm{x}_{0})\|^{2}}{1-(1-\alpha)^{2}}$ $\displaystyle\leq$
$\displaystyle\frac{1}{\alpha}\left(\frac{2\alpha^{2}\sigma^{2}T}{n}+\frac{4(1-\alpha)^{2}(L^{2}+L_{F}^{2})\gamma^{2}}{n}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{u}_{t-1}\|^{2}\right)+\frac{\mathbb{E}\|\bm{u}_{0}-\nabla
f(\bm{x}_{0})\|^{2}}{\alpha}$ $\displaystyle=$
$\displaystyle\frac{2\alpha\sigma^{2}T}{n}+\frac{4(1-\alpha)^{2}(L^{2}+L_{F}^{2})\gamma^{2}}{\alpha
n}\sum_{t=0}^{T-1}\mathbb{E}\|\bm{u}_{t-1}\|^{2}+\frac{\mathbb{E}\|\bm{u}_{0}-\nabla
f(\bm{x}_{0})\|^{2}}{\alpha}.$ (17)

Since $A_{t}=\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})-\hat{\bm{u}}_{t}\|^{2}-(1-2L\gamma)\mathbb{E}\|\hat{\bm{u}}_{t}\|^{2}-\frac{\mathbb{E}\|\nabla
f(\hat{\bm{x}}_{t})\|^{2}}{4}$, therefore if
$\frac{4(1-\alpha)^{2}(L^{2}+L_{F}^{2})\gamma^{2}}{\alpha n}\leq\frac{1}{2}$
and $1-2L\gamma\geq\frac{1}{2}$, then we have

$\displaystyle\sum_{t=0}^{T-1}A_{t}\leq$
$\displaystyle\frac{2\alpha\sigma^{2}T}{n}+\frac{\mathbb{E}\|\bm{u}_{0}-\nabla
f(\bm{x}_{0})\|^{2}}{\alpha}$ $\displaystyle\leq$
$\displaystyle\frac{2\alpha\sigma^{2}T}{n}+\frac{\sigma^{2}}{n\alpha B_{0}}.$

∎

###### Proof of Theorem 7.

Here we introduce an auxiliary variable that is defined as

$\displaystyle Z(\bm{x},\bm{y}):=\nabla f(\bm{x})-\nabla
f(\bm{y})-\langle\nabla^{2}f(\bm{y}),\bm{x}-\bm{y}\rangle.$

Then from the bounded Hessian in Assumption 3, we have

$\displaystyle\|Z(\bm{x},\bm{y})\|\leq\rho\|\bm{x}-\bm{y}\|^{2}.$

Moreover, since $\bm{u}_{t}$ is a weighted average over all history stochastic
gradients, under the bounded stochastic gradient of Assumption 3, we have

$\displaystyle\mathbb{E}\|\bm{x}_{t}-\bm{x}_{t-1}\|^{2}\leq\gamma^{2}\Delta^{2}.$

Denote $\bm{e}_{t}:=\bm{v}_{t}-\nabla f(\bm{x}_{t})$, we get

$\displaystyle\mathbb{E}\|\bm{e}_{t}\|^{2}$ $\displaystyle=$
$\displaystyle\mathbb{E}\left\|(1-\alpha)\bm{e}_{t-1}+\alpha\nabla
F\left(\bm{x}_{t}+\frac{1-\alpha}{\alpha}(\bm{x}_{t}-\bm{x}_{t-1});\xi_{t}^{(i)}\right)-\nabla
f(\bm{x}_{t})+(1-\alpha)\nabla f(\bm{x}_{t-1})\right\|^{2}$ $\displaystyle=$
$\displaystyle\mathbb{E}\left\|(1-\alpha)\bm{e}_{t-1}+\alpha\nabla
f\left(\bm{x}_{t}+\frac{1-\alpha}{\alpha}(\bm{x}_{t}-\bm{x}_{t-1})\right)-\nabla
f(\bm{x}_{t})+(1-\alpha)\nabla f(\bm{x}_{t-1})\right\|^{2}$
$\displaystyle+\mathbb{E}\left\|\alpha\nabla
F\left(\bm{x}_{t}+\frac{1-\alpha}{\alpha}(\bm{x}_{t}-\bm{x}_{t-1});\xi_{t}^{(i)}\right)-\alpha\nabla
f\left(\bm{x}_{t}+\frac{1-\alpha}{\alpha}(\bm{x}_{t}-\bm{x}_{t-1})\right)\right\|^{2}$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left\|(1-\alpha)\bm{e}_{t-1}+\alpha\nabla
f\left(\bm{x}_{t}+\frac{1-\alpha}{\alpha}(\bm{x}_{t}-\bm{x}_{t-1})\right)-\nabla
f(\bm{x}_{t})+(1-\alpha)\nabla
f(\bm{x}_{t-1})\right\|^{2}+\frac{\alpha^{2}\sigma^{2}}{n}$ $\displaystyle=$
$\displaystyle\mathbb{E}\left\|(1-\alpha)\bm{e}_{t-1}+(1-\alpha)Z(\bm{x}_{t-1},\bm{x}_{t})+\alpha
Z\left(\bm{x}_{t}+\frac{1-\alpha}{\alpha}(\bm{x}_{t}-\bm{x}_{t-1}),\bm{x}_{t}\right)\right\|^{2}+\frac{\alpha^{2}\sigma^{2}}{n}$
$\displaystyle\leq$
$\displaystyle\left(1+\alpha\right)\mathbb{E}\left\|(1-\alpha)\bm{e}_{t-1}\right\|^{2}+\left(1+\frac{1}{\alpha}\right)\mathbb{E}\left\|(1-\alpha)Z(\bm{x}_{t-1},\bm{x}_{t})+\alpha
Z\left(\bm{x}_{t}+\frac{1-\alpha}{\alpha}(\bm{x}_{t}-\bm{x}_{t-1}),\bm{x}_{t}\right)\right\|^{2}$
$\displaystyle+\frac{\alpha^{2}\sigma^{2}}{n}\qquad(\mbox{applying
}(x+y)^{2}\leq(1+\alpha)x^{2}+(1+{1\over\alpha})y^{2})$ $\displaystyle\leq$
$\displaystyle\left(1-\alpha\right)\mathbb{E}\left\|\bm{e}_{t-1}\right\|^{2}+\frac{(\alpha+1)}{\alpha^{2}}\mathbb{E}\left\|(1-\alpha)Z(\bm{x}_{t-1},\bm{x}_{t})\right\|^{2}$
$\displaystyle+\frac{(\alpha+1)}{\alpha(1-\alpha)}\mathbb{E}\left\|\alpha
Z\left(\bm{x}_{t}+\frac{1-\alpha}{\alpha}(\bm{x}_{t}-\bm{x}_{t-1}),\bm{x}_{t}\right)\right\|^{2}+\frac{\alpha^{2}\sigma^{2}}{n}$
$\displaystyle\leq$
$\displaystyle\left(1-\alpha\right)\mathbb{E}\left\|\bm{e}_{t-1}\right\|^{2}+\frac{(1-\alpha^{2})(1-\alpha)\rho^{2}}{\alpha^{3}}\mathbb{E}\left\|\bm{x}_{t-1}-\bm{x}_{t}\right\|^{4}+\frac{\alpha^{2}\sigma^{2}}{n}$
$\displaystyle\leq$
$\displaystyle\left(1-\alpha\right)\mathbb{E}\left\|\bm{e}_{t-1}\right\|^{2}+\frac{(1-\alpha)\rho^{2}}{\alpha^{3}}\mathbb{E}\left\|\bm{x}_{t-1}-\bm{x}_{t}\right\|^{4}+\frac{\alpha^{2}\sigma^{2}}{n}.$
(18)

In this case, we also have
$\mathbb{E}_{\xi_{t-1}}\|\bm{x}_{t}-\bm{x}_{t-1}\|^{2}\leq\gamma^{2}\Delta^{2}$,
and (18) becomes

$\displaystyle\mathbb{E}\|\bm{e}_{t}\|^{2}\leq\left(1-\alpha\right)\mathbb{E}\left\|\bm{e}_{t-1}\right\|^{2}+\frac{(1-\alpha)\rho^{2}\gamma^{4}\Delta^{4}}{\alpha^{3}}+\frac{\alpha^{2}\sigma^{2}}{n}.$
(19)

Using Lemma 9 and (19), we get

$\displaystyle\sum_{t=0}^{T}\mathbb{E}\|\nabla
f(\bm{x}_{t})-\bm{v}_{t}\|^{2}\leq$
$\displaystyle\frac{\sum_{t=1}^{T}\left(\frac{\alpha^{2}\sigma^{2}}{n}+\frac{\rho^{2}\gamma^{4}\Delta^{4}}{\alpha^{3}}\right)+\mathbb{E}\|\bm{e}_{0}\|^{2}}{1-(1-\alpha)}\leq\frac{\alpha\sigma^{2}T}{n}+\frac{\sigma^{2}}{\alpha
nB_{0}}+\frac{\rho^{2}\gamma^{4}\Delta^{4}T}{\alpha^{4}}.$

The lemma is proved. ∎

##  10 Proof of Corollary

###  10.1 Proof of Corollary 4

###### Proof.

Combining Theorem 1 and 3 together, we shall get

$\displaystyle\frac{1}{T}\sum_{t=0}^{T}\mathbb{E}\|\nabla
f(\bm{x}_{t})\|^{2}\leq$ $\displaystyle\frac{16(f(\bm{x}_{0})-f^{*})}{\gamma
T}+\frac{136\gamma
L\sigma^{2}}{3n}+(64L^{2}_{\mathscr{A}}+2L^{2})\gamma^{2}\alpha^{2}T\epsilon^{2}.$

Since $L_{\mathscr{A}}=L$, after setting
$\gamma=\min\left\\{\frac{\alpha}{12L},\frac{\sqrt{n}}{\sqrt{T}\sigma},\left(\frac{1}{\epsilon^{2}T}\right)^{\frac{1}{3}}\right\\}$,
it can be easily verified that we have

$\displaystyle\frac{1}{T}\sum_{t=0}^{T}\mathbb{E}\|\nabla
f(\bm{x}_{t})\|^{2}\leq\mathcal{O}\left(\frac{\sigma}{\sqrt{nT}}+\frac{\alpha^{2}}{(\epsilon
T)^{\frac{2}{3}}}+\frac{1}{\alpha T}\right),$

where we treat $f(\bm{x}_{0})-f^{*}$ and $L$ as constants. ∎

###  10.2 Proof of Corollary 6

###### Proof.

Combining Theorem 1 and 5 together, and setting
$\alpha=\frac{8L^{2}\gamma^{2}}{n}$ we shall get

$\displaystyle\frac{1}{T}\sum_{t=0}^{T}\mathbb{E}\|\nabla
f(\bm{x}_{t})\|^{2}\leq$ $\displaystyle\frac{16(f(\bm{x}_{0})-f^{*})}{\gamma
T}+\frac{128L^{2}\gamma^{2}\sigma^{2}}{n^{2}}+\frac{\sigma^{2}}{L^{2}\gamma^{2}B_{0}T}+\frac{64(64L^{2}_{\mathscr{A}}+2L^{2})L^{4}\gamma^{6}\epsilon^{2}}{n}.$

Since $L_{\mathscr{A}}=2L$, after setting
$\gamma=\min\left\\{\frac{1}{4L},\left(\frac{n^{2}}{\sigma^{2}T}\right)^{\frac{1}{3}},\left(\frac{n}{\epsilon^{2}T}\right)^{\frac{1}{7}}\right\\}$
and $B_{0}=\frac{\sigma^{\frac{8}{3}}T^{\frac{1}{3}}}{n^{\frac{2}{3}}}$, Can
we choose $B_{0}$ arbitrary? – Ming then it can be easily verified that we
have

$\displaystyle\frac{1}{T}\sum_{t=0}^{T}\mathbb{E}\|\nabla
f(\bm{x}_{t})\|^{2}\leq\mathcal{O}\left(\left(\frac{\sigma}{nT}\right)^{\frac{2}{3}}+\left(\frac{\epsilon^{2}}{nT^{6}}\right)^{\frac{1}{7}}+\frac{1}{T}\right),$

where we treat $f(\bm{x}_{0})-f^{*}$, $L$ as constants. ∎

###  10.3 Proof of Corollary 8

###### Proof.

Combining Theorem 1 and 7 together, we shall get

$\displaystyle\frac{1}{T}\sum_{t=0}^{T}\mathbb{E}\|\nabla
f(\bm{x}_{t})\|^{2}\leq$ $\displaystyle\frac{16(f(\bm{x}_{0})-f^{*})}{\gamma
T}+\frac{8\alpha\sigma^{2}}{n}+\frac{8\sigma^{2}}{\alpha
nB_{0}T}+\frac{8\rho^{2}\gamma^{4}\Delta^{4}}{\alpha^{4}}+\frac{8(64L^{2}_{\mathscr{A}}+2L^{2})L^{2}\gamma^{6}\epsilon^{2}}{n}.$

Since $L_{\mathscr{A}}=2L$, after setting
$\gamma=\min\left\\{\frac{1}{2L},\left(\frac{n^{4}}{\sigma^{8}T^{5}}\right)^{\frac{1}{9}},\left(\frac{n}{\epsilon^{2}T}\right)^{\frac{1}{7}}\right\\}$,
$\alpha=\left(\frac{n^{5}}{\sigma^{8}T^{4}}\right)^{\frac{1}{9}}$ and
$B_{0}=1$, then it can be easily verified that we have

$\displaystyle\frac{1}{T}\sum_{t=0}^{T}\mathbb{E}\|\nabla
f(\bm{x}_{t})\|^{2}\leq\mathcal{O}\left(\left(\frac{\sigma^{8}}{n^{4}T^{4}}\right)^{\frac{1}{9}}+\left(\frac{\epsilon^{2}}{nT^{6}}\right)^{\frac{1}{7}}+\frac{1}{T}\right),$

where we treat $f(\bm{x}_{0})-f^{*}$, $L$ and $\rho$ as constants. ∎