# Improving the Worst-Case Bidirectional Communication Complexity
for Nonconvex Distributed Optimization under Function Similarity

Kaja Gruntkowska  Alexander Tyurin  Peter Richtárik

###### Abstract

Effective communication between the server and workers plays a key role in
distributed optimization. In this paper, we focus on optimizing the server-to-
worker communication, uncovering inefficiencies in prevalent downlink
compression approaches. Considering first the pure setup where the uplink
communication costs are negligible, we introduce MARINA-P, a novel method for
downlink compression, employing a collection of correlated compressors.
Theoretical analyses demonstrates that MARINA-P with permutation compressors
can achieve a server-to-worker communication complexity improving with the
number of workers, thus being provably superior to existing algorithms. We
further show that MARINA-P can serve as a starting point for extensions such
as methods supporting bidirectional compression. We introduce M3, a method
combining MARINA-P with uplink compression and a momentum step, achieving
bidirectional compression with provable improvements in total communication
complexity as the number of workers increases. Theoretical findings align
closely with empirical experiments, underscoring the efficiency of the
proposed algorithms.

###  1 Introduction

In federated learning (McMahan et al., 2017; Konečný et al., 2016) and large-
scale machine learning (Ramesh et al., 2021; OpenAI, 2023), a typical
environment consists of multiple devices working together to train a model.
Facilitating this collaborative process requires the transmission of
substantial information (e.g., gradients, current model) between these
devices. In the centralized framework, communication takes place via a server.
As a result, practical challenges arise due to the large size of machine
learning models and network speed limitations, potentially creating a
communication bottleneck (Kairouz et al., 2021; Wang et al., 2023a).

One possible strategy to reduce this communication burden is to use _lossy
compression_ (Seide et al., 2014; Alistarh et al., 2017). Our paper focuses on
this research direction.

We consider the nonconvex distributed optimization task

$\displaystyle\min\limits_{x\in\mathbb{R}^{d}}\left\\{f(x):=\frac{1}{n}\sum\limits_{i=1}^{n}f_{i}(x)\right\\},$
(1)

where $x\in\mathbb{R}^{d}$ is the vector of parameters of the model, $n$ is
the number of workers and $f_{i}\,:\,\mathbb{R}^{d}\rightarrow\mathbb{R}$,
$i\in[n]:=\\{1,\dots,n\\}$ are smooth nonconvex functions.

We investigate the scenario where the functions $f_{i}$ are stored on $n$
distinct workers, each directly connected to the server via some communication
port (Kairouz et al., 2021). At present, we operate under the following
generic assumptions:

######  Assumption 1.1.

The function $f$ is $L$–smooth, i.e., $\left\|\nabla f(x)-\nabla
f(y)\right\|\leq L\left\|x-y\right\|,\quad\forall x,y\in\mathbb{R}^{d}.$

######  Assumption 1.2.

There exists $f^{*}\in\mathbb{R}$ such that $f(x)\geq f^{*}$ $\forall
x\in\mathbb{R}^{d}.$

In the nonconvex world, our goal is to find a (possibly) random point
$\bar{x}$ such that

${\rm\mathbb{E}}\left[\left\|\nabla
f(\bar{x})\right\|^{2}\right]\leq\varepsilon.$

We refer to such a point an $\varepsilon$–stationary point.

####  1.1 Related Work

Before we discuss more advanced optimization methods, let us consider the
simplest baseline: the gradient descent (GD) (Lan, 2020), which iteratively
performs updates

$x^{t+1}=x^{t}-\gamma\nabla
f(x^{t})=x^{t}-\frac{\gamma}{n}\sum_{i=1}^{n}\nabla f_{i}(x^{t}).$

In the distributed setting, the method can be implemented as follows: each
worker calculates $\nabla f_{i}(x^{t})$ and sends it to the server, where the
gradients are aggregated. The server takes the step and broadcasts $x^{t+1}$
back to the workers. With step size $\gamma=\nicefrac{{1}}{{L}},$ GD finds an
$\varepsilon$–stationary point after

$\mathcal{O}\left(\frac{\delta^{0}L}{\varepsilon}\right)$

steps, where $\delta^{0}:=f(x^{0})-f^{*}$ for a starting point $x^{0}$. Since
at each step the workers and the server send $\Theta(d)$ coordinates/bits, the
worker-to-server (w2s, uplink) and server-to-worker (s2w, downlink)
communication costs are

$\displaystyle\mathcal{O}\left(\frac{d\delta^{0}L}{\varepsilon}\right).$ (2)

######  Definition 1.3.

The _worker-to-server (w2s)_ and _server-to-worker (s2w)_ communication
complexities of a method are the expected number of coordinates/floats that a
worker sends to the server and that the server sends to a worker,
respectively, to find an $\varepsilon$–solution. The _total communication
complexity_ is the sum of these complexities.

Unbiased compressors. In this work, to perform lossy compression, we employ
mappings from the following family:

######  Definition 1.4.

A stochastic mapping $\mathcal{C}\,:\,\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$
is an unbiased compressor if there exists $\omega\geq 0$ such that

$\displaystyle{\rm\mathbb{E}}\left[\mathcal{C}(x)\right]=x,\,{\rm\mathbb{E}}\left[\left\|\mathcal{C}(x)-x\right\|^{2}\right]\leq\omega\left\|x\right\|^{2}\,\forall
x\in\mathbb{R}^{d}.$ (3)

We denote the family of such mappings by $\mathbb{U}(\omega)$. A canonical
example is the Rand$K\in\mathbb{U}(\nicefrac{{d}}{{K}}-1)$ sparsifier, which
preserves $K$ random coordinates of a vector scaled by $\nicefrac{{d}}{{K}}$
(Beznosikov et al., 2020). More examples can be found in Wangni et al. (2018);
Beznosikov et al. (2020); Szlendak et al. (2021); Horváth et al. (2022). A
larger family of compressors, called _biased compressors_ , also exists (see
Section B). In this paper, we implicitly assume that compressors are mutually
independent _across iterations_ of algorithms.

Worker-to-server compression scales with $n$. Many previous works ignore the
s2w communication costs and focus solely on w2s compression, assuming that
_broadcasting is free_. For nonconvex objective functions, the current state-
of-the-art w2s communication complexities are achieved by the MARINA and DASHA
methods (Gorbunov et al., 2021a; Szlendak et al., 2021; Tyurin & Richtárik,
2023a). Here, two additional assumptions are needed:

######  Assumption 1.5.

The function $f_{i}$ is $L_{i}$–smooth. We define
$\widehat{L}^{2}:=\frac{1}{n}\sum_{i=1}^{n}L_{i}^{2}$ and
$L_{\max}:=\max_{i\in[n]}L_{i}.$

######  Assumption 1.6.

For all $\mathcal{C}\in\mathbb{U}(\omega),$ all calls of $\mathcal{C}$ are
mutually independent.111This assumptions means that if an algorithm calls a
compressor $\mathcal{C}$ at some points $x_{1},\dots,x_{m},$ then
$\mathcal{C}(x_{1}),\dots,\mathcal{C}(x_{m})$ are _i.i.d._

Under Assumptions 1.1, 1.2, 1.5, 1.6, and considering the Rand$K$ compressor
with $K\leq\nicefrac{{d}}{{\sqrt{n}}}$ as an example, the w2s communication
complexity of both methods is

$\displaystyle\underbrace{K}_{\textnormal{\\# of sent
coord.}}\times\underbrace{\mathcal{O}\left(\frac{\delta^{0}}{\varepsilon}(L+\frac{\omega}{\sqrt{n}}\widehat{L})\right)}_{\textnormal{\\#
of
iterations}}=\mathcal{O}\left(\frac{d\delta^{0}\widehat{L}}{\sqrt{n}\varepsilon}\right),$
(4)

where we use the facts that $L\leq\widehat{L}$ and
$\omega=\nicefrac{{d}}{{K}}-1$ for Rand$K$. The key observation is that when
comparing (2) and (4), one sees that (4) can be $\sqrt{n}$ times smaller if
$\widehat{L}\approx L.$ Consequently, the communication complexity of
MARINA/DASHA scales with the number of workers $n,$ and can _provably_ improve
the _worker-to-server_ communication complexity
$\mathcal{O}\left(\nicefrac{{d\delta^{0}L}}{{\varepsilon}}\right)$ achieved by
GD.

Server-to-worker compression does not scale with $n$. In certain applications,
the significance of s2w communication cannot be ignored. In 4G LTE and 5G
networks, w2s and s2w communication speeds can be almost the same (Huang et
al., 2012) or differ by at most a factor of $10$ (Narayanan et al., 2021).
Although important, this issue is often overlooked and that is why it is the
s2w communication that this work places a central emphasis on.

There is an abundance of works which study the use of compression techniques
as tools to reduce the s2w communication (Zheng et al., 2019; Liu et al.,
2020; Philippenko & Dieuleveut, 2021; Fatkhullin et al., 2021; Gruntkowska et
al., 2023; Tyurin & Richtárik, 2023b). However, to the best of our knowledge,
under Assumptions 1.1, 1.2, 1.5, and 1.6, in the worst case, all previous
theoretical s2w communications guarantees _are greater or equal_ to (2). As an
example, let us consider the result from Gruntkowska et al. (2023)[Theorem
E.3]. If the server employs operators from $\mathbb{U}(\omega)$ and we ignore
w2s compression, the method from Gruntkowska et al. (2023) converges in
$\mathcal{O}\left(\nicefrac{{(\omega+1)\delta^{0}L}}{{\varepsilon}}\right)$
iterations. Thus, with Rand$K$, the s2w communication complexity is

$\mathcal{O}\left(K\times\frac{(\omega+1)L}{\varepsilon}\right)=\mathcal{O}\left(\frac{d\delta^{0}L}{\varepsilon}\right).$

Another method, called CORE, proposed by Yue et al. (2023), achieves s2w and
w2s communication complexities equal to

$\mathcal{O}\left(\frac{r_{1}(f)\delta^{0}L}{\varepsilon}\right),$

where $r_{1}(f)$ is a uniform upper bound of the trace of the Hessian. When
$r_{1}(f)\leq dL,$ CORE can improve on GD. However, this complexity does not
scale with $n$ and requires an additional assumption about the Hessian of $f$.

###  2 Contributions

In our work, we aim to investigate whether the _server-to-worker and total
communication complexities_ (2) of the vanilla GD method can be improved. We
make the following contributions:

  1. 1.

We start by proving the impossibility of devising a method where the server
communicates with the workers using unbiased compressors $\mathbb{U}(\omega)$
(or biased compressors from Section B) and achieves an _iteration rate_ faster
than

$\Omega\left(\frac{(\omega+1)L\delta^{0}}{\varepsilon}\right)$

(Theorem 3.1) under Assumptions 1.1, 1.2, and 1.6. This result gives no hope
for improving the communication complexity (2) in the worst case.

  2. 2.

In view of this result, it is clear that an extra assumption is needed to
break the lower bound
$\Omega\left(\nicefrac{{(\omega+1)L\delta^{0}}}{{\varepsilon}}\right).$ In
response, we introduce a novel assumption termed “Functional $(L_{A},L_{B})$
Inequality” (see Assumption 4.2). We prove that this assumption is relatively
weak and holds, for instance, under the local smoothness of the functions
$f_{i}$ (see Assumption 1.5).

  3. 3.

We develop a new method for downlink compression, MARINA-P, and show that,
under our new assumption, it can achieve the _s2w communication complexity_ of

$\displaystyle\mathcal{O}\left(\frac{d\delta^{0}L}{n\varepsilon}+\frac{d\delta^{0}L_{A}}{\varepsilon}\right).$

Notably, when $L_{A}$ is small and $n>1,$ this complexity is _provably_
superior to (2) and the complexities of the previous compressed methods. In
this context, $L_{A}$ serves as a measure of the similarity between the
functions $f_{i}$, and can be bounded by the “variance” of the Hessians of the
functions $f_{i}$ (see Theorem 4.8). Thus, MARINA-P is _the first method whose
s2w communication complexity can provably improve with the number of workers
$n$_.

  4. 4.

Our theoretical improvements can be combined with techniques enhancing the
_w2s communication complexities_. In particular, by combining MARINA-P with
MARINA (Gorbunov et al., 2021b) and adding the crucial momentum step, we
develop a new method, M3, that guarantees a _total communication complexity_
(s2w + w2s) of

$\displaystyle\mathcal{O}\left(\frac{d\delta^{0}L_{\max}}{n^{1/3}\varepsilon}+\frac{d\delta^{0}L_{A}}{\varepsilon}\right).$

When $n>1$ and in the close-to-homogeneous regime, i.e., when $L_{A}$ is
small, this complexity is better than (2) and the complexities of the previous
bidirectionally compressed methods.

###  3 Lower Bound under Smoothness

Let us first investigate the possibility of improving the s2w communication
complexity $\mathcal{O}\left(\nicefrac{{d\delta^{0}L}}{{\varepsilon}}\right)$
of GD under Assumptions 1.1,1.2, and 1.6.

In Section G, we consider a family of methods that include those proposed in
Zheng et al. (2019); Liu et al. (2020); Philippenko & Dieuleveut (2021);
Fatkhullin et al. (2021); Gruntkowska et al. (2023), where the server
communicates with workers using unbiased/biased compressors, and establish the
following result.

######  Theorem 3.1 (Slightly Less Formal Reformulation of Theorem G.5).

Under Assumptions 1.1, 1.2, and 1.6, all methods, where the server
communicates with clients using different and independent unbiased compressors
from $\mathbb{U}\left(\omega\right),$ and sends one compressed vector to each
worker, cannot converge before

$\Omega\left(\frac{(\omega+1)L\delta^{0}}{\varepsilon}\right)$

iterations.

######  Remark 3.2.

The theorem remains applicable to biased compressors
$\mathbb{B}\left(\alpha\right)$ (see Section B) with a lower bound of
$\Theta\left(\nicefrac{{L\delta^{0}}}{{\alpha\varepsilon}}\right)$. This is
because if $\mathcal{C}\in\mathbb{U}(\omega),$ then
$(\omega+1)^{-1}\mathcal{C}\in\mathbb{B}\left((\omega+1)^{-1}\right).$ We also
establish a more general result (Theorem G.4): “all methods in which the
server zeroes out a coordinate with probability $\leq p$ independently _across
iterations_ cannot converge before
$\Omega\left(\nicefrac{{L\delta^{0}}}{{p\varepsilon}}\right)$ iterations.”

This lower bound is tight up to a constant factor. For instance, under exactly
the same assumptions, the EF21-P mechanism from Gruntkowska et al. (2023)
converges after
$\Theta\left(\nicefrac{{(\omega+1)L\delta^{0}}}{{\varepsilon}}\right)$
iterations. Unlike (4), this convergence rate does not scale with $n,$ and
Theorem 3.1 leaves no room for improvement. Consequently, breaking the lower
bound requires an additional assumption about the structure of the problem.
Before presenting our candidate assumption, we first introduce the ingredients
needed to leverage it to the fullest extent: our novel downlink compression
method and the type of compressors we shall employ.

###  4 The MARINA-P Method

Let us first recall the MARINA method (Gorbunov et al., 2021a; Szlendak et
al., 2021):

$\displaystyle x^{t+1}$ $\displaystyle=x^{t}-\gamma g^{t},\quad
c^{t}\sim\textnormal{Bernoulli}(p),$ (5) $\displaystyle g_{i}^{t+1}$
$\displaystyle=\begin{cases}\nabla f_{i}(x^{t+1})&c^{t}=1,\\\
g^{t}+\mathcal{C}_{i}^{t}(\nabla f_{i}(x^{t+1})-\nabla
f_{i}(x^{t}))&c^{t}=0\end{cases}$ for a $\displaystyle\textnormal{ll
}i\in[n],\quad g^{t+1}=\frac{1}{n}\sum_{i=1}^{n}g_{i}^{t+1},$

where $g^{0}=\nabla f(x^{0})$. Motivated by MARINA, we design its primal
counterpart, MARINA-P (Algorithm 1), operating in the primal space of the
model parameters, as outlined in (6).

The MARINA-P Method: Initialize vectors
$x_{0},w_{1}^{0},\dots,w_{n}^{0}\in\mathbb{R}^{d}$, step size $\gamma>0$,
probability $0<p\leq 1$ and compressors
$\mathcal{C}_{1}^{t},\ldots,\mathcal{C}_{n}^{t}\in\mathbb{U}(\omega_{P})$ for
all $t\geq 0.$ The method iterates $\displaystyle g^{t}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\nabla f_{i}(w_{i}^{t}),$ (6)
$\displaystyle x^{t+1}$ $\displaystyle=x^{t}-\gamma g^{t},$ $\displaystyle
c^{t}$ $\displaystyle\sim\textnormal{Bernoulli}(p),$ $\displaystyle
w^{t+1}_{i}$ $\displaystyle=\begin{cases}x^{t+1}&\text{if }c^{t}=1,\\\
w_{i}^{t}+\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})&\text{if }c^{t}=0\end{cases}$ for
al $\displaystyle\textnormal{l }i\in[n].$ We denote
$w^{t}:=\nicefrac{{1}}{{n}}\sum_{i=1}^{n}w_{i}^{t}.$ See the implementation in
Algorithm 1.

At each iteration of MARINA-P, the workers calculate $\nabla f_{i}(w_{i}^{t})$
and transmit it to the server. The server then averages the gradients and
updates the global model $x^{t}$. Subsequently, with some (typically small)
probability $p$, the master sends the non-compressed vector $x^{t+1}$ to all
workers. Otherwise, the $i$th worker receives a compressed vector
$\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})$. Each worker then uses the received
message to compute $w^{t+1}_{i}$ locally. Importantly,
$\mathcal{C}_{1}^{t}(x^{t+1}-x^{t}),\dots,\mathcal{C}_{n}^{t}(x^{t+1}-x^{t})$
_can differ_ , and this distinction will form the basis of our forthcoming
advancements.

Comparing (5) and (6), MARINA-P and MARINA are dual methods: both learn
control variables ($w^{t}_{i}$ and $g_{i}^{t}$), compress the differences
($x^{t+1}-x^{t}$ and $\nabla f_{i}(x^{t+1})-\nabla f_{i}(x^{t})$), and with
some probability $p$ send non-compressed vectors ($x^{t+1}$ and $\nabla
f_{i}(x^{t+1})$). However, unlike MARINA, which compresses vectors sent _from
workers to server_ and operates in the _dual_ space of gradients, MARINA-P
compresses messages sent _from server to workers_ and operates in the _primal_
space of arguments.

Let us take Rand$K\in\mathbb{U}(\nicefrac{{d}}{{K}}-1)$ as an example. If we
set $p=\left(\omega+1\right)^{-1}=\nicefrac{{K}}{{d}}$ to balance heavy
communications of $x^{t+1}$ and light communications of $\mathcal{C}^{t}_{i}$
in (6), MARINA-P averages sending $pd+(1-p)K\leq 2K$ coordinates per
iteration. Then, the lower bound from Theorem G.4 implies that at least

$\Omega\left(\frac{(\omega+1)\delta^{0}L}{\varepsilon}\right)$

iterations of the algorithm are needed.

At first glance, it may seem that MARINA-P does not offer any extra benefits
compared to previous methods; that is true – we could not expect to break the
lower bound. However, as we shall soon see, under an extra assumption,
MARINA-P achieves communication complexity that improves with $n$.

####  4.1 Three ways to compress

Existing algorithms performing s2w compression share a common characteristic:
at each iteration, the server broadcasts _the same_ message to all workers
(Zheng et al., 2019; Liu et al., 2020; Fatkhullin et al., 2021; Gruntkowska et
al., 2023; Tyurin & Richtárik, 2023b)222A notable exception form this rule is
the MCM method (Philippenko & Dieuleveut, 2021) \- see Appendix A.. In
contrast, in w2s compression methods, each worker sends to the server a
_different_ message, specific to the data stored on that particular device. An
analogous approach can be taken in the s2w communication: intuitively, sending
$n$ distinct messages would convey more information, potentially leading to
theoretical improvements. This indeed proves to be the case. While the usual
approach of the server broadcasting the same vector to all clients does not
lead to an improvement over (2), allowing these vectors to differ enables a
well-crafted method to achieve communication complexity that improves with $n$
(see Corollary D.4).

In Appendix A we provide a detailed discussion of the topic and compare the
theoretical complexities of MARINA-P when the server employs three different
compression techniques: a) uses _one compressor_ and sends the same vector to
all clients, b) uses a _collection of independent compressors_ , or c) uses a
_collection of correlated compressors_. We now turn to presenting the
technique that gives the best theoretical s2w communication complexity out of
these, namely the use of a set of _correlated compressors_.

####  4.2 Recap: permutation compressors Perm$K$

Szlendak et al. (2021) propose compressors that will play a key role in our
new theory. For clarity of presentation, we shall assume that $d\geq n$ and
$n|d$.333The general definition of Perm$K$ for $d\bmod n\neq 0$ is presented
in (Szlendak et al., 2021)[App. I].

######  Definition 4.1 (Perm$K$ (for $d\geq n$ and $n|d$)).

Assume that $d\geq n$ and $d=qn$, where $q\in\mathbb{N}_{>0}$. Let
$\pi=(\pi_{1},\dots,\pi_{d})$ be a random permutation of $\\{1,\dots,d\\}$.
Then for all $x\in\mathbb{R}^{d}$ and each $i\in\\{1,2,\dots,n\\}$ we define

$\mathcal{C}_{i}(x):=n\times\sum\limits_{j=q(i-1)+1}^{qi}x_{\pi_{j}}e_{\pi_{j}}.$

Unpacking this definition: when the server compresses a vector using a Perm$K$
compressor, it randomly partitions its coordinates across the workers, so that
each client receives a sparse vector containing a random subset of entries of
the input vector. Like Rand$K$, Perm$K$ is also a sparsifier. However, unlike
Rand$K$, it does not allow flexibility in choosing $K$, as it is fixed to
$\nicefrac{{d}}{{n}}$. Furthermore, it can be shown (Lemma A.6) that
$\mathcal{C}_{i}\in\mathbb{U}(n-1)$ for all $i\in[n]$.

An appealing property of Perm$K$ is the fact that

$\displaystyle\frac{1}{n}\sum\limits_{i=1}^{n}\mathcal{C}_{i}(x)=x$ (7)

for all $x\in\mathbb{R}^{d}$ deterministically. Here, it is important to note
that by design, compressors $\mathcal{C}_{i}$ from Definition 4.1 are
_correlated_ , and do not satisfy Assumption 1.6. This correlation proves
advantageous - Szlendak et al. (2021) show that MARINA with Perm$K$
compressors performs provably better than with i.i.d. Rand$K$ compressors.

####  4.3 Warmup: homogeneous quadratics

We are finally ready to present our first result showing that the s2w
communication complexity can scale with the number of workers $n$. To explain
the intuition behind our approach, let us consider the simplest (and somewhat
impractical) choice of functions $f_{i}$ – the homogeneous quadratics:

$\displaystyle f_{i}(x)=\frac{1}{2}x^{\top}\mathbf{A}x+b^{\top}x+c,\quad
i\in[n],$ (8)

where $\mathbf{A}\in\mathbb{R}^{d\times d}$ is a symmetric but not necessarily
positive semidefinite matrix, $b\in\mathbb{R}^{d}$ and $c\in\mathbb{R}$. We
now investigate the operation of MARINA-P with Perm$K$ compressors. With
probability $p$, we have $w^{t+1}=x^{t+1}$. Otherwise
$w^{t+1}=w^{t}+\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})\overset{\eqref{eq:restore}}{=}x^{t+1}+(w^{t}-x^{t}).$
Hence, if we initialize $w_{i}^{0}=x^{0}$ for all $i\in[n],$ an inductive
argument shows that $w^{t}=x^{t}$ deterministically for all $t\geq 0$. Then,
substituting the gradients of $f_{i}$ to (6), one gets

$\displaystyle
g^{t}=\frac{1}{n}\sum\limits_{i=1}^{n}(\mathbf{A}w_{i}^{t}+b)=\mathbf{A}w^{t}+b=\mathbf{A}x^{t}+b=\nabla
f(x^{t})$

for all $t\geq 0.$ Therefore, MARINA-P with Perm$K$ compressor in this setting
is essentially a smart implementation of vanilla GD! Indeed, for
$p\leq\nicefrac{{1}}{{n}}$, MARINA-P with Perm$K$ sends on average
$\leq\nicefrac{{2d}}{{n}}$ coordinates to each worker, so the s2w
communication complexity is

$\displaystyle\frac{2d}{n}\times\underbrace{\mathcal{O}\left(\frac{\delta^{0}L}{\varepsilon}\right)}_{\textnormal{{\scriptsize\sf
GD} rate}}=\mathcal{O}\left(\frac{d\delta^{0}L}{n\varepsilon}\right),$

which is $n$ times smaller than in (2)!

Table 1: The worst case _server-to-workers communication complexities_ to find
an $\varepsilon$–stationary point. For simplicity, we compare the complexities
with non-homogeneous quadratics:
$f_{i}(x)=\frac{1}{2}x^{\top}\mathbf{A}_{i}x+b_{i}^{\top}x+c_{i},$ where
$\mathbf{A}_{i}\in\mathbb{R}^{d\times d}$ is symmetric but not necessarily
positive semidefinite, $b_{i}\in\mathbb{R}^{d}$ and $c_{i}\in\mathbb{R}$ for
$i\in[n].$ We denote $\mathbf{A}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{A}_{i}.$

Method Complexity GD and other compressed methods(a)
$\geq\frac{d\delta^{0}\left\|\mathbf{A}\right\|}{\varepsilon}$ CORE (Yue et
al., 2023) $\frac{\delta^{0}\textnormal{tr}\mathbf{A}}{\varepsilon}$ MARINA-P
with independent Rand$K$(b) (Corollary D.4)
$\frac{d\delta^{0}\frac{1}{n}\sum_{i=1}^{n}\left\|\mathbf{A}_{i}\right\|}{\sqrt{n}\varepsilon}+\frac{d\delta^{0}\max_{i\in[n]}\left\|\mathbf{A}_{i}-\mathbf{A}\right\|}{\varepsilon}$
MARINA-P with Perm$K$(b) (Corollary 4.7)
$\frac{d\delta^{0}\left\|\mathbf{A}\right\|}{n\varepsilon}+\frac{d\delta^{0}\max_{i\in[n]}\left\|\mathbf{A}_{i}-\mathbf{A}\right\|}{\varepsilon}$
• The complexity of MARINA-P with Perm$K$ is better when $n>1$ and in close-
to-homogeneous regimes, i.e., when
$\max_{i\in[n]}\left\|\mathbf{A}_{i}-\mathbf{A}\right\|$ is small. (a)
including EF21-P (Gruntkowska et al., 2023), dist-EF-SGD (Zheng et al., 2019),
DORE (Liu et al., 2020), MCM (Philippenko & Dieuleveut, 2021), and EF21-BC
(Fatkhullin et al., 2021). (b) This table only showcases the results for
Rand$K$ and Perm$K.$ A more general result for all compressors is provided in
Section D. One can see that the correlated Perm$K$ compressors provide better
guarantees than independent Rand$K$.

####  4.4 Functional $(L_{A},L_{B})$ Inequality

From the discussion in Section 3, we know that to improve (2), an extra
assumption about the structure of the problem is needed. Building on the
example from Section 4.3, we introduce the _Functional $(L_{A},L_{B})$
Inequality_.

######  Assumption 4.2 (Functional $(L_{A},L_{B})$ Inequality).

There exist constants $L_{A},L_{B}\geq 0$ such that

$\displaystyle\left\|\frac{1}{n}\sum\limits_{i=1}^{n}(\nabla
f_{i}(x+u_{i})-\nabla f_{i}(x))\right\|^{2}$ $\displaystyle\leq
L_{A}^{2}\left(\frac{1}{n}\sum\limits_{i=1}^{n}\left\|u_{i}\right\|^{2}\right)+L_{B}^{2}\left\|\frac{1}{n}\sum\limits_{i=1}^{n}u_{i}\right\|^{2}$
(9)

for all $x,u_{1},\dots,u_{n}\in\mathbb{R}^{d}.$

######  Remark 4.3.

A similar assumption termed “Heterogeneity-driven Lipschitz Condition on
Averaged Gradients” is proposed in Wang et al. (2023b). Our assumption aligns
with theirs when $L_{B}=0$. However, our formulation proves to be more
powerful. The possibility that $L_{B}>0$ becomes instrumental in driving the
enhancements we introduce.

Assumption 4.2 is defined for all functions together, and intuitively, it
tries to capture the similarities between the functions $f_{i}$. For $n=1$,
inequality (4.2) reduces to

$\displaystyle\left\|\nabla f(x)-\nabla
f(y)\right\|^{2}\leq\left(L_{A}^{2}+L_{B}^{2}\right)\left\|x-y\right\|^{2}\forall
x,y\in\mathbb{R}^{d},$

equivalent to standard $L$-smoothness (Assumption 1.1) with
$L^{2}=L_{A}^{2}+L_{B}^{2}$. The Functional $(L_{A},L_{B})$ Inequality is
reasonably weak also for $n>1$, as the next theorem shows.

######  Theorem 4.4.

For all $i\in[n],$ assume that the functions $f_{i}$ are $L_{i}$–smooth
(Assumption 1.5). Then, Assumption 4.2 holds with $L_{A}=L_{\max}$ and
$L_{B}=0$.

Therefore, Assumption 4.2 holds whenever the functions $f_{i}$ are smooth,
which is a standard assumption in the literature. Now, returning to the
example from Section 4.3,

######  Theorem 4.5.

For all $i\in[n],$ assume that the functions $f_{i}$ are homogeneous
quadratics defined in (8). Then, Assumption 4.2 holds with $L_{A}=0$ and
$L_{B}=\left\|\mathbf{A}\right\|.$

Under Assumption 1.5, no information about the similarity of the functions
$f_{i}$ is available, yielding $L_{B}=0$ and $L_{A}>0$ in Theorem 4.4.
However, once we have some information limiting heterogeneity, $L_{A}$ can
decrease. Notably, $L_{A}=0$ for homogeneous quadratics. As we shall see in
Section 4.5, the values $L_{A}$ and $L_{B}$ significantly influence the s2w
communication complexity of MARINA-P, with lower $L_{A}$ values leading to
greatly improved performance.

####  4.5 The Convergence Theory of MARINA-P with Perm$K$

We are ready to present our main convergence result. For simplicity, we
consider the Perm$K$ compressor from Section 4.2. The general theory covering
all unbiased compressors can be found in Appendix D.

######  Theorem 4.6.

Let Assumptions 1.1, 1.2 and 4.2 be satisfied. Set $w_{i}^{0}=x^{0}$ for all
$i\in[n].$ Take Perm$K$ as $\mathcal{C}_{i}^{t}$ and

$\gamma=\left(L+L_{A}\sqrt{\omega_{P}\left(\frac{1}{p}-1\right)}\right)^{-1},$

where $\omega_{P}=n-1$ (Lemma A.6). Then, MARINA-P finds an
$\varepsilon$–stationary point after

$\displaystyle\mathcal{O}\left(\frac{\delta^{0}}{\varepsilon}\left(L+L_{A}\sqrt{\frac{\omega_{P}}{p}}\right)\right)$

iterations.

######  Corollary 4.7.

Let $p=\nicefrac{{K}}{{d}}\equiv\nicefrac{{1}}{{n}}$. Then, in the view of
Theorem 4.6, the average s2w communication complexity of MARINA-P with Perm$K$
compressor is

$\displaystyle\mathcal{O}\left(\frac{d\delta^{0}L}{n\varepsilon}+\frac{d\delta^{0}L_{A}}{\varepsilon}\right).$
(10)

The key observation is that (10) is independent of $L_{B},$ and only depends
on $L_{A}$. This particular property is specific to _correlated compressors_
with parameter $\theta=0$ (defined in Appendix A), such as Perm$K$. A similar
result holds for _independent_ Rand$K$ compressors (see Corollary D.4), but
the convergence rate is worse and depends on $L_{B}$. Nevertheless, this
dependence improves with $n$.

When $L_{A}=0,$ which is the case for homogeneous quadratics, the step size
bound from Theorem 4.6 simplifies to $\gamma\leq\nicefrac{{1}}{{L}}$, the
standard GD stepsize (recall that in this case our method reduces to GD). Most
importantly, (10) scales with the number of workers $n$! Even when $L_{A}>0,$
for sufficiently big $n,$ (10) can improve (2) to
$\mathcal{O}\left(\nicefrac{{d\delta^{0}L_{A}}}{{\varepsilon}}\right).$

Let us now investigate how the constants $L_{A}$ and $L_{B}$ change in the
general case.

####  4.6 Estimating $L_{A}$ and $L_{B}$ in the General Case

It is clear from Corollary 4.7, that MARINA-P with Perm$K$ shines when $L_{A}$
is small. To gain further insights into what values $L_{A}$ may take, we now
provide an analysis based on the Hessians of the functions $f_{i}$.

######  Theorem 4.8.

Assume that the functions $f_{i}$ are twice continuously differentiable,
$L_{i}$–smooth (Assumption 1.5), and that there exist $D_{i}\geq 0$ such that

$\displaystyle\sup\limits_{z_{1},\ldots,z_{n}\in\mathbb{R}^{d}}\left\|\nabla^{2}f_{i}(z_{i})-\frac{1}{n}\sum_{j=1}^{n}\nabla^{2}f_{j}(z_{j})\right\|\leq
D_{i}$ (11)

for all $i\in[n]$. Then, Assumption 4.2 holds with

$L_{A}=\sqrt{2}\max\limits_{i\in[n]}D_{i}\leq
2\sqrt{2}\max\limits_{i\in[n]}L_{i}$

and

$L_{B}=\sqrt{2}\left(\frac{1}{n}\sum\limits_{i=1}^{n}L_{i}\right).$

Intuitively, (11) measures the similarity between the functions $f_{i}$. The
above theorem yields a more refined result than Theorem 4.4: it is always true
that $\max_{i\in[n]}D_{i}\leq 2\max_{i\in[n]}L_{i}$, and, in fact,
$\max_{i\in[n]}D_{i}$ can be much smaller, as the next result shows.

######  Theorem 4.9.

Assume that $f_{i}(x)=\frac{1}{2}x^{\top}\mathbf{A}_{i}x+b_{i}^{\top}x+c_{i},$
where $\mathbf{A}_{i}\in\mathbb{R}^{d\times d}$ is symmetric but not
necessarily positive semidefinite, $b_{i}\in\mathbb{R}^{d}$ and
$c_{i}\in\mathbb{R}$ for $i\in[n].$ Define
$\mathbf{A}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{A}_{i}.$ Then, Assumption 4.2
holds with

$L_{A}=\sqrt{2}\max\limits_{i\in[n]}\left\|\mathbf{A}_{i}-\mathbf{A}\right\|$

and

$L_{B}=\sqrt{2}\left(\frac{1}{n}\sum\limits_{i=1}^{n}\left\|\mathbf{A}_{i}\right\|\right).$

Thus, $L_{A}$ is less than or equal to
$\sqrt{2}\max_{i\in[n]}\left\|\mathbf{A}_{i}-\mathbf{A}\right\|,$ which serves
as a measure of similarity between the matrices. The smaller the values of
$\left\|\mathbf{A}_{i}-\mathbf{A}\right\|$ (indicating greater similarity
among the functions $f_{i}$), the smaller the $L_{A}$ value.

In the view of this theorem, the s2w communication complexity of MARINA-P with
Perm$K$ on non-homogeneous quadratics is

$\displaystyle\mathcal{O}\left(\frac{d\delta^{0}\left\|\mathbf{A}\right\|}{n\varepsilon}+\frac{d\delta^{0}\max_{i\in[n]}\left\|\mathbf{A}_{i}-\mathbf{A}\right\|}{\varepsilon}\right).$
(12)

Since the corresponding complexity of GD is

$\displaystyle\mathcal{O}\left(\frac{d\delta^{0}\left\|\mathbf{A}\right\|}{\varepsilon}\right),$
(13)

in the close-to-homogeneous regimes (i.e., when
$\max_{i\in[n]}\left\|\mathbf{A}_{i}-\mathbf{A}\right\|$ is small), the
complexity (12) can be _provably_ much smaller than (13). The same reasoning
applies to the general case when the functions $f_{i}$ are not quadratics:
MARINA-P improves with the number of workers $n$ in the regimes when $D_{i}$
are small (see Theorem 4.8).

Let us note that there is another method, CORE, by Yue et al. (2023), that can
also provably outperform GD, achieving the s2w communication complexity of
$\Omega\left(\frac{\delta^{0}\textnormal{tr}{\mathbf{A}}}{\varepsilon}\right)$
on non-homogeneous quadratics. Neither their method nor ours universally
provides the best possible communication guarantees. Our method excels in the
close-to-homogeneous regimes: for example, if we take
$\mathbf{A}_{i}=L_{i}\mathbf{I}$ for all $i\in[n],$ and define
$L=\frac{1}{n}\sum_{i=1}^{n}L_{i}$, then the complexity of CORE is

$\Omega\left(\frac{d\delta^{0}L}{\varepsilon}\right),$

while ours is

$\mathcal{O}\left(\frac{d\delta^{0}L}{n\varepsilon}+\frac{d\delta^{0}\max_{i\in[n]}\lvert
L_{i}-L\rvert}{\varepsilon}\right).$

Hence, our guarantees are superior in regimes where $\max_{i\in[n]}\lvert
L_{i}-L\rvert\ll L$. One interesting research direction is to develop a
universally better method combining the benefits of both approaches.

###  5 M3: A New Bidirectional Method

In the previous sections, we introduce a new method that provably improves the
_server-to-worker_ communication, but ignores the _worker-to-server_
communication overhead. Our aim now is to treat MARINA-P as a starting point
for developing methods applicable to more practical scenarios, by combining it
with techniques that compress in the opposite direction. Since the theoretical
state-of-the-art w2s communication complexity is obtained by MARINA (see
Section 1.1), our next research step was to combine the two and analyze
”MARINA \+ MARINA-P”, but this naive approach did not yield communication
complexity guarantees surpassing (2) in any regime. It became apparent that
some “buffer” step between these two techniques is needed, and this step
turned out to be the momentum. Our new method, M3 (Algorithm 2), is described
in (LABEL:eq:mthree).

The M3 Method (M3 = MARINA-P + Momentum + MARINA): Initialize vectors
$x_{0},w_{i}^{0},g_{i}^{0},z_{i}^{0}\in\mathbb{R}^{d}$ for all $i\in[n]$, step
size $\gamma>0$, probabilities $0<p_{P},p_{D}\leq 1$ and compressors
$\mathcal{C}_{1}^{t},\ldots,\mathcal{C}_{n}^{t}\in\mathbb{U}(\omega_{P})\cap\mathbb{P}(\theta)$444By
$\mathbb{P}(\theta)$ we denote a family of _correlated compressors_ (defined
in Appendix A). It includes, among others, Perm$K$ compressors.,
$\mathcal{Q}_{1}^{t},\ldots,\mathcal{Q}_{n}^{t}\in\mathbb{U}(\omega_{D})$ for
all $t\geq 0.$ The method iterates $\displaystyle x^{t+1}=x^{t}-\gamma g^{t},$
(14) $\displaystyle w^{t+1}_{i}=\begin{cases}x^{t+1}&\textnormal{w.p.
}p_{P},\\\ w_{i}^{t}+\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})&\textnormal{w.p.
}1-p_{P},\end{cases}$ $\displaystyle z_{i}^{t+1}=\beta
w_{i}^{t+1}+(1-\beta)z_{i}^{t}\qquad\textnormal{{\small\sf(Momentum)}}$
$\displaystyle g^{t+1}_{i}=\begin{cases}\nabla
f_{i}(z_{i}^{t+1})&\textnormal{w.p. }p_{D},\\\
g^{t}_{i}+\mathcal{Q}_{i}^{t}(\nabla f_{i}(z_{i}^{t+1})-\nabla
f_{i}(z_{i}^{t}))&\textnormal{w.p. }1-p_{D}\end{cases}$ for al
$\displaystyle\textnormal{l }i\in[n],$ where the probabilistic decisions are
the same for all $i\in[n],$ i.e., one coin is tossed for all workers (as in
(5) and (6)), and the coins for the first and second probabilistic decisions
with $p_{P}$ and $p_{D}$ are independent. We denote
$w^{t}:=\nicefrac{{1}}{{n}}\sum_{i=1}^{n}w_{i}^{t},$
$g^{t}:=\nicefrac{{1}}{{n}}\sum_{i=1}^{n}g_{i}^{t},$
$z^{t}:=\nicefrac{{1}}{{n}}\sum_{i=1}^{n}z_{i}^{t}.$ See the implementation in
Algorithm 2.

M3 combines (5), (6), and the momentum step

$z_{i}^{t+1}=\beta w_{i}^{t+1}+(1-\beta)z_{i}^{t},$

which is the key to our improvements. A similar technique is used to reduce
the variance in Fatkhullin et al. (2023). Let us explain how M3 works in
practice. First, the server calculates $x^{t+1}.$ Depending on the first
probabilistic decision, it sends either $x^{t+1}$ or
$\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})$ to the workers, who then calculate
$w^{t+1}_{i}$ locally. Next, the workers compute $z^{t+1}_{i},$ and depending
on the second probabilistic decision, they send either $\nabla
f_{i}(z_{i}^{t+1})$ or $\mathcal{Q}_{i}^{t}(\nabla f_{i}(z_{i}^{t+1})-\nabla
f_{i}(z_{i}^{t}))$ back to the server. The server aggregates the received
vectors and calculates $g^{t+1}.$ As in MARINA, $p_{P}$ and $p_{D}$ are chosen
in such a way that the non-compressed communication does not negatively affect
the communication complexity. Therefore, the method predominantly transmits
compressed information, with only a marginal probability of sending
uncompressed vectors.

Table 2: The worst case _total communication complexities_ to find an
$\varepsilon$–stationary point. For simplicity, we compare the complexities
with non-homogeneous quadratics:
$f_{i}(x)=\frac{1}{2}x^{\top}\mathbf{A}_{i}x+b_{i}^{\top}x+c_{i},$ where
$\mathbf{A}_{i}\in\mathbb{R}^{d\times d}$ is symmetric but not necessarily
positive semidefinite, $b_{i}\in\mathbb{R}^{d}$ and $c_{i}\in\mathbb{R}$ for
$i\in[n].$ We denote $\mathbf{A}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{A}_{i}.$

Method Complexity GD and other compressed methods(a)
$\geq\frac{d\delta^{0}\left\|\mathbf{A}\right\|}{\varepsilon}$ CORE (Yue et
al., 2023) $\frac{\delta^{0}\textnormal{tr}\mathbf{A}}{\varepsilon}$ M3 with
Perm$K$ and Rand$K$(b) (Theorem 5.1)
$\frac{d\delta^{0}\max\limits_{i\in[n]}\left\|\mathbf{A}_{i}\right\|}{n^{1/3}\varepsilon}+\frac{d\delta^{0}\max\limits_{i\in[n]}\left\|\mathbf{A}_{i}-\mathbf{A}\right\|}{\varepsilon}$
• The complexity of M3 with Perm$K$ and Rand$K$ is better when $n>1$ and in
close-to-homogeneous regimes, i.e., when
$\max_{i\in[n]}\left\|\mathbf{A}_{i}-\mathbf{A}\right\|$ is small. (a)
including EF21-P (Gruntkowska et al., 2023), dist-EF-SGD (Zheng et al., 2019),
DORE (Liu et al., 2020), MCM (Philippenko & Dieuleveut, 2021), and EF21-BC
(Fatkhullin et al., 2021). (b) This table only showcases the results for
Perm$K$ and Rand$K.$ A more general result for all compressors is provided in
Section E.

####  5.1 The Convergence Theory of M3

For simplicity, we consider Perm$K$ in the role of $\mathcal{C}_{i}^{t}$ and
Rand$K$ in the role of $\mathcal{Q}_{i}^{t}$. The general theory for all
unbiased compressors is presented in Section E.

######  Theorem 5.1.

Let Assumptions 1.1, 1.2, 1.5 and 4.2 be satisfied. Take

$\gamma=\left(L+34\left(nL_{A}+n^{2/3}L_{B}+n^{2/3}L_{\max}\right)\right)^{-1},$

$p_{D}=p_{P}=\nicefrac{{1}}{{n}}$, $\beta=n^{-2/3}$,
$w_{i}^{0}=z_{i}^{0}=x^{0}$ and $g_{i}^{0}=\nabla f_{i}(x^{0})$ for all
$i\in[n]$. Then MARINA-P with $\mathcal{C}_{i}^{t}=$ Perm$K$ and
$\mathcal{Q}_{i}^{t}=$ Rand$K$ with $K=\nicefrac{{d}}{{n}}$ finds an
$\varepsilon$–stationary point after

$\mathcal{O}\left(\frac{\delta^{0}}{\varepsilon}\left(n^{2/3}L_{\max}+nL_{A}\right)\right)$

iterations. The total communication complexity is

$\displaystyle\mathcal{O}\left(\frac{d\delta^{0}L_{\max}}{n^{1/3}\varepsilon}+\frac{d\delta^{0}L_{A}}{\varepsilon}\right).$
(15)

Once again, we observe improvement with the number of workers $n$, and the
obtained complexity (15) can be provably smaller than (2). Indeed, in
scenarios like federated learning, where the number of workers (e.g., mobile
phones) is typically large (Kairouz et al., 2021; Chowdhery et al., 2023), the
first term can be significantly smaller than
$\nicefrac{{d\delta^{0}L}}{{\varepsilon}}$. The second term can also be small
in close-to-homogeneous regimes (see Section 4).

###  6 Experiments

This section provides some insights from the experiments. Further details and
additional experiments can be found in Appendix F.

####  6.1 Experiments with MARINA-P on quadratic optimization tasks

The aim of this experiment is to empirically test the theoretical results from
Section 4. We consider a quadratic optimization problem, where the functions
$f_{i}$ are as defined in Theorem 4.9 and
$\mathbf{A}_{i}\in\mathbb{R}^{300\times 300}$. We compare the following
algorithms: GD, MARINA-P sending the same message compressed using a single
Rand$K$ compressor to all workers (“SameRand$K$” from Section A), MARINA-P
with independent Rand$K$ compressors, MARINA-P with Perm$K$ compressors, and
EF21-P with Top$K$ compressor. We consider $n\in\\{10,100,1000\\}$ and fine-
tune the step size for each algorithm.

The results, presented in Figure 1, align closely with the theory. MARINA-P
with Perm$K$ compressor performs best in all experiments. Moreover, the
convergence rate of both MARINA-P with Perm$K$ compressors and MARINA-P with
independent Rand$K$ compressors improves with $n$. Since this is not the case
for EF21-P, even though it outperforms MARINA-P with independent Rand$K$
compressors for $n=10$, it becomes worse for $n\in\\{100,1000\\}$.

Figure 1: Experiments on the quadratic optimization problem from Section 6.1.
We plot the norm of the gradient w.r.t. # of coordinates sent from the server
to the workers.

####  6.2 Experiments with M3 on quadratic optimization tasks

We consider close-to-homogeneous quadratic optimization problem with
$\mathbf{A}_{i}=(1+\xi_{i})\mathbf{I}_{d},$ where
$\xi_{i}\sim\mathcal{N}(0,0.01)$ for all $i\in[n],$ and $d=1000.$ We run two
algorithms from Table 2, M3 and CORE, and check whether theory matches
practice. In M3, we use Perm$K$ followed by the natural compressor
$\mathcal{C}_{\textnormal{nat}}$ (Horváth et al., 2022) (composition of two
unbiased compressors) on the server’s side, and Rand$K$ followed by
$\mathcal{C}_{\textnormal{nat}}$ on the workers’ side. We use $K=\left\lfloor
d/n\right\rfloor\in\\{1,10,100\\}$ for $n\in\\{1000,100,10\\}$. In CORE, the
number of communicated coordinates is set to $10.$ We run each experiment $5$
times with different seeds and plot the average to reduce the noise factor.
Only the step size is fine-tuned for each algorithm.

The results are presented in Figure 2. As expected, CORE does not change its
behavior as the number of workers increases from $10$ to $100;$ this is
expected since CORE does not depend on $n.$ At the same time, M3 does improve
with $n$, which supports our findings from Theorem 5.1.

Figure 2: Experiments on the quadratic optimization problem from Section 6.2.
We plot the norm of the gradient w.r.t. # of coordinates sent from the server
(s2w) and from the workers (w2s).

Figure 3: Experiments on the autoencoder task from Section 6.3. We plot the
norm of the gradient w.r.t. # of coordinates sent from the server (s2w) and
from the workers (w2s).

####  6.3 Experiments with an autoencoder and MNIST

We now compare MARINA-P, M3, CORE, EF21-P + DCGD, and GD on a non-convex
autoencoder problem. We train it on the MNIST dataset (LeCun et al., 2010)
with objective function

$f(\mathbf{D},\mathbf{E}):=\frac{1}{m}\sum_{i=1}^{m}\left\|\mathbf{D}\mathbf{E}b_{i}-b_{i}\right\|^{2}+\frac{\lambda}{2}\left\|\mathbf{D}\mathbf{E}-\mathbf{I}\right\|_{F}^{2},$

where $\mathbf{D}\in\mathbb{R}^{d_{1}\times d_{2}}$,
$\mathbf{E}\in\mathbb{R}^{d_{2}\times d_{1}}$, $b_{i}\in\mathbb{R}^{d_{1}}$
are samples, $d_{1}=784$ is the number of features, $d_{2}=16$ is the size of
the encoding space, $\lambda=0.001$ is a regularizer, and $m=60\,000$ is the
number of samples. The dimension of the problem is $d=25\,088.$ We randomly
split the dataset among $n=100$ workers. For MARINA-P and M3, we take Perm$K$
followed by the natural compressor $\mathcal{C}_{\textnormal{nat}}$ on the
server’s side. On the workers’ side, M3 uses Rand$K$ and
$\mathcal{C}_{\textnormal{nat}}$. For EF21-P + DCGD, we take Rand$K$ with
$\mathcal{C}_{\textnormal{nat}}$ on both the workers’ and server’s sides. In
each case, $K=\left\lfloor d/n\right\rfloor=250.$ For CORE, we set the number
of communicated coordinates to $100.$ As in previous experiments, we only
fine-tune the step size, repeat each experiment $5$ times, and plot the
average results.

In Figure 3, the results are presented. All methods with bidirectional
compression: M3, CORE, and EF21-P + DCGD, converge much faster than GD.
MARINA-P converges fastest only in the first plot. This is expected since it
compresses only from the server to the workers. M3, CORE, and EF21-P + DCGD
have similar convergence rates in both metrics, with M3 performing better in
the low accuracy regime.

### Impact Statement

This paper presents work whose goal is to advance the field of Machine
Learning. There are many potential societal consequences of our work, none
which we feel must be specifically highlighted here.

#### Acknowledgements

The work of P. Richtárik was partially supported by the KAUST Baseline
Research Fund Scheme and by the SDAIA-KAUST Center of Excellence in Data
Science and Artificial Intelligence. The work of K. Gruntkowska and A. Tyurin
was supported by the Extreme Computing Research Center (ECRC) at KAUST.

### References

  * Alistarh et al. (2017) Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M.  QSGD: Communication-efficient SGD via gradient quantization and encoding.  In _Advances in Neural Information Processing Systems (NIPS)_ , pp. 1709–1720, 2017.
  * Arjevani et al. (2022) Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B.  Lower bounds for non-convex stochastic optimization.  _Mathematical Programming_ , pp. 1–50, 2022.
  * Beznosikov et al. (2020) Beznosikov, A., Horváth, S., Richtárik, P., and Safaryan, M.  On biased compression for distributed learning.  _arXiv preprint arXiv:2002.12410_ , 2020.
  * Carmon et al. (2020) Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A.  Lower bounds for finding stationary points i.  _Mathematical Programming_ , 184(1):71–120, 2020.
  * Chowdhery et al. (2023) Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al.  Palm: Scaling language modeling with pathways.  _Journal of Machine Learning Research_ , 24(240):1–113, 2023.
  * Fang et al. (2018) Fang, C., Li, C. J., Lin, Z., and Zhang, T.  SPIDER: Near-optimal non-convex optimization via stochastic path integrated differential estimator.  In _NeurIPS Information Processing Systems_ , 2018.
  * Fatkhullin et al. (2021) Fatkhullin, I., Sokolov, I., Gorbunov, E., Li, Z., and Richtárik, P.  EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback.  _arXiv preprint arXiv:2110.03294_ , 2021.
  * Fatkhullin et al. (2023) Fatkhullin, I., Tyurin, A., and Richtárik, P.  Momentum provably improves error feedback!  _Advances in Neural Information Processing Systems (NeurIPS)_ , 2023.
  * Gorbunov et al. (2021a) Gorbunov, E., Burlachenko, K., Li, Z., and Richtárik, P.  MARINA: Faster non-convex distributed learning with compression.  In _38th International Conference on Machine Learning_ , 2021a.
  * Gorbunov et al. (2021b) Gorbunov, E., Burlachenko, K., Li, Z., and Richtárik, P.  Marina: Faster non-convex distributed learning with compression.  _arXiv preprint arXiv:2102.07845_ , 2021b.
  * Gruntkowska et al. (2023) Gruntkowska, K., Tyurin, A., and Richtárik, P.  EF21-P and friends: Improved theoretical communication complexity for distributed optimization with bidirectional compression.  In _International Conference on Machine Learning_ , pp. 11761–11807. PMLR, 2023.
  * Horváth et al. (2022) Horváth, S., Ho, C.-Y., Horvath, L., Sahu, A. N., Canini, M., and Richtárik, P.  Natural compression for distributed deep learning.  In _Mathematical and Scientific Machine Learning_ , pp. 129–141. PMLR, 2022.
  * Huang et al. (2012) Huang, J., Qian, F., Gerber, A., Mao, Z. M., Sen, S., and Spatscheck, O.  A close examination of performance and power characteristics of 4g lte networks.  In _Proceedings of the 10th international conference on Mobile systems, applications, and services_ , pp. 225–238, 2012.
  * Huang et al. (2022) Huang, X., Chen, Y., Yin, W., and Yuan, K.  Lower bounds and nearly optimal algorithms in distributed learning with communication compression.  _arXiv preprint arXiv:2206.03665_ , 2022.
  * Kairouz et al. (2021) Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al.  Advances and open problems in federated learning.  _Foundations and Trends® in Machine Learning_ , 14(1–2):1–210, 2021.
  * Konečný et al. (2016) Konečný, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., and Bacon, D.  Federated learning: Strategies for improving communication efficiency.  _arXiv preprint arXiv:1610.05492_ , 2016.
  * Lan (2020) Lan, G.  _First-order and stochastic optimization methods for machine learning_.  Springer, 2020.
  * LeCun et al. (2010) LeCun, Y., Cortes, C., and Burges, C.  Mnist handwritten digit database.  _ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist_ , 2, 2010.
  * Li et al. (2021) Li, Z., Bao, H., Zhang, X., and Richtárik, P.  PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization.  In _International Conference on Machine Learning_ , pp. 6286–6295. PMLR, 2021.
  * Liu et al. (2020) Liu, X., Li, Y., Tang, J., and Yan, M.  A double residual compression algorithm for efficient distributed learning.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 133–143. PMLR, 2020.
  * Lu & De Sa (2021) Lu, Y. and De Sa, C.  Optimal complexity in decentralized training.  In _International Conference on Machine Learning_ , pp. 7111–7123. PMLR, 2021.
  * McMahan et al. (2017) McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , pp. 1273–1282. PMLR, 2017.
  * Narayanan et al. (2021) Narayanan, A., Zhang, X., Zhu, R., Hassan, A., Jin, S., Zhu, X., Zhang, X., Rybkin, D., Yang, Z., Mao, Z. M., et al.  A variegated look at 5g in the wild: performance, power, and qoe implications.  In _Proceedings of the 2021 ACM SIGCOMM 2021 Conference_ , pp. 610–625, 2021.
  * OpenAI (2023) OpenAI.  Gpt-4 technical report.  _ArXiv_ , abs/2303.08774, 2023.  URL https://arxiv.org/abs/2303.08774.
  * Philippenko & Dieuleveut (2021) Philippenko, C. and Dieuleveut, A.  Preserved central model for faster bidirectional compression in distributed settings.  _Advances in Neural Information Processing Systems_ , 34:2387–2399, 2021.
  * Ramesh et al. (2021) Ramesh, A., Pavlov, M., Goh, G., Gray, S., Voss, C., Radford, A., Chen, M., and Sutskever, I.  Zero-shot text-to-image generation.  In _International Conference on Machine Learning_ , pp. 8821–8831. PMLR, 2021.
  * Richtárik et al. (2021) Richtárik, P., Sokolov, I., and Fatkhullin, I.  EF21: A new, simpler, theoretically better, and practically faster error feedback.  _In Neural Information Processing Systems, 2021._ , 2021.
  * Seide et al. (2014) Seide, F., Fu, H., Droppo, J., Li, G., and Yu, D.  1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs.  In _Fifteenth Annual Conference of the International Speech Communication Association_ , 2014.
  * Szlendak et al. (2021) Szlendak, R., Tyurin, A., and Richtárik, P.  Permutation compressors for provably faster distributed nonconvex optimization.  In _International Conference on Learning Representations_ , 2021.
  * Tyurin & Richtárik (2023a) Tyurin, A. and Richtárik, P.  DASHA: Distributed nonconvex optimization with communication compression, optimal oracle complexity, and no client synchronization.  _11th International Conference on Learning Representations (ICLR)_ , 2023a.
  * Tyurin & Richtárik (2023b) Tyurin, A. and Richtárik, P.  2Direction: Theoretically faster distributed training with bidirectional communication compression.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 2023b.
  * Tyurin & Richtárik (2023c) Tyurin, A. and Richtárik, P.  Optimal time complexities of parallel stochastic optimization methods under a fixed computation model.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 2023c.
  * Wang et al. (2023a) Wang, J., Lu, Y., Yuan, B., Chen, B., Liang, P., De Sa, C., Re, C., and Zhang, C.  Cocktailsgd: Fine-tuning foundation models over 500mbps networks.  In _International Conference on Machine Learning_ , pp. 36058–36076. PMLR, 2023a.
  * Wang et al. (2023b) Wang, J., Wang, S., Chen, R.-R., and Ji, M.  A new theoretical perspective on data heterogeneity in federated optimization.  In _Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities_ , 2023b.
  * Wangni et al. (2018) Wangni, J., Wang, J., Liu, J., and Zhang, T.  Gradient sparsification for communication-efficient distributed optimization.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Yue et al. (2023) Yue, P., Zhao, H., Fang, C., He, D., Wang, L., Lin, Z., and Zhu, S.-c.  Core: Common random reconstruction for distributed optimization with provable low communication complexity.  _arXiv preprint arXiv:2309.13307_ , 2023.
  * Zheng et al. (2019) Zheng, S., Huang, Z., and Kwok, J.  Communication-efficient distributed blockwise momentum sgd with error-feedback.  _Advances in Neural Information Processing Systems_ , 32, 2019.

## Appendix

###  Appendix A Three unbiased ways to compress

The main focus of this paper is handling the server-to-worker communication
costs. To explain better where the improvements outlined in the main part of
this paper come from, let us first consider the scenario where uplink
communication cost is negligible but downilnk communication cost is not. While
we do no necessarily say that this is a realistic setup, examining it first
enables us to understand how downlink compression should be performed,
capturing all the intricacies.

Existing algorithms with lossy s2w and w2s communication have a certain common
feature. The compression mechanism employed on the clients is very different
from the one used on the server: while each client transmits to the server a
different message, specific to the data stored on each device, the server
broadcasts the same update to all clients. We want to question this
algorithmic step and suggest to the reader that if compression is applied
multiple times and each worker receives its individual update, then
intuitively more information can be transmitted. A well-designed algorithm
should be able to take advantage of this.

One can depart from the usual approach of sending the same update to all
workers in two ways: a) compress the update $n$ times independently, or b)
produce $n$ such updates in a correlated way. Either way, the server
broadcasts $n$ different compressed messages rather than one, and sends a
_different_ update to each worker. The key discovery here is that both a) and
b) are mathematically _provably better_ than the prevalent approach of sending
the same update to all clients.

This is a crucial improvement in a system where the above setup is a good
approximation of reality. And even if it is not, and the current model is not
perfectly capturing the reality, we can accept it for now, as it allows us to
focus on the novel aspects of the approach. With that said, these
considerations can serve as a starting point for thinking about _bidirectional
compression_ : having focused on the simplified setup and equipped with
knowledge on how the compression on the master should be performed, we employ
this mechanism in more complex scenarios (see Section 5).

Let us now describe the three possible ways to perform compression on the
server.

###### “Same” compressors.

The prevalent approach in downlink compression is to transmit the same update
to all workers. To illustrate this, let us call a collection
$\mathcal{C}_{1},\ldots,\mathcal{C}_{n}$ of compressors “SameRand$K$” if for
all $i\in[n]$ we have $\mathcal{C}_{i}=\mathcal{C}$ for some Rand$K$
compressor $\mathcal{C}$. Now, consider one iteration $t$ of MARINA-P with
SameRand$K$ compressor. The server calculates
$\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})$ for $i\in[n]$, but in this case,

$\mathcal{C}_{1}^{t}(x^{t+1}-x^{t})=\dots=\mathcal{C}_{n}^{t}(x^{t+1}-x^{t})=\mathcal{C}^{t}(x^{t+1}-x^{t}).$

Thus, applying a collection of SameRand$K$ compressors to some vector
$x\in\mathbb{R}^{d}$ is equivalent to using a single Rand$K$ compression
operator and transmitting the same message $\mathcal{C}(x)$ to all workers.

###### Independent Compressors.

Rather than setting $\mathcal{C}_{i}(x)=\mathcal{C}(x)$ for all $i\in[n]$, one
can break the dependency between the messages and allow the compressors to
differ. For illustrational purposes, suppose that $\mathcal{C}_{i},i\in[n]$
are independent Rand$K$ compressors (Assumption 1.6). Then, applying such a
collection of mappings to the vector of interest $x\in\mathbb{R}^{d}$, one
obtains $n$ distinct and independent sparse vectors
$\mathcal{C}_{1}(x),\ldots,\mathcal{C}_{n}(x)$.

######  Remark A.1.

We are aware of only one method that uses $n$ distinct compressors in downlink
compression, Rand-MCM by Philippenko & Dieuleveut (2021). Given the absence of
results in the non-convex case, let us compare the communication complexities
of Rand-MCM and M3 under the Polyak-Łojasiewicz condition (Assumption D.9),
which holds under strong convexity. In the strongly convex case, the proved
iteration complexity of Rand-MCM is

$\displaystyle\Omega\left(\frac{L_{\max}}{\mu}\left(\omega_{P}^{3/2}+\frac{\omega_{P}\omega_{D}^{1/2}}{\sqrt{n}}+\frac{\omega_{D}}{n}\right)\log\frac{\delta^{0}}{\varepsilon}\right).$

Assuming for simplicity that the server and the workers use Rand$K$
compressors with $K=\nicefrac{{d}}{{n}}$, this gives the total communication
complexity of

$\displaystyle\Omega\left(\frac{d}{n}\times\frac{L_{\max}}{\mu}\left(\omega_{P}^{3/2}+\frac{\omega_{P}\omega_{D}^{1/2}}{\sqrt{n}}+\frac{\omega_{D}}{n}\right)\log\frac{\delta^{0}}{\varepsilon}\right)$
$\displaystyle=\Omega\left(\frac{d\sqrt{n}L_{\max}}{\mu}\log\frac{\delta^{0}}{\varepsilon}\right),$

which is getting _worse_ as the number of workers $n$ increases. Meanwhile, by
Corollary E.10, the total communication complexity of M3 (where
$\mathcal{C}_{i}^{t}$ are the Perm$K$ compressors and $\mathcal{Q}_{i}^{t}$
are independent Rand$K$ compressors, both with $K=d/n$) under the Polyak-
Łojasiewicz condition is

$\displaystyle\mathcal{O}\left(\left(\frac{dL_{\max}}{n^{1/3}\mu}+\frac{dL_{A}}{\mu}+d\right)\log\frac{\delta^{0}}{\varepsilon}\right).$

Since $n$ is typically large, the total communication complexity of M3 can be
much better than that of Rand-MCM.

###### Correlated Compressors.

In their work, Szlendak et al. (2021) introduce an alternative class of
compressors, which satisfy the following condition:

######  Definition A.2 (AB-inequality (Szlendak et al., 2021)).

There exist constants $A,B\geq 0$ such that the random operators
$\mathcal{C}_{1},\ldots\mathcal{C}_{n}$ satisfy

$\displaystyle{\rm\mathbb{E}}\left[\mathcal{C}_{i}(x)\right]$
$\displaystyle=x,$
$\displaystyle{\rm\mathbb{E}}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}(x_{i})-\frac{1}{n}\sum_{i=1}^{n}x_{i}\right\|^{2}\right]$
$\displaystyle\leq
A\frac{1}{n}\sum_{i=1}^{n}\left\|x_{i}\right\|^{2}-B\left\|\frac{1}{n}\sum_{i=1}^{n}x_{i}\right\|^{2}$
(16)

for all $x,x_{1},\ldots,x_{n}\in\mathbb{R}^{d}$. If these conditions hold, we
write $\left\\{\mathcal{C}_{i}\right\\}_{i=1}^{n}\in\mathbb{U}(A,B)$.

Following on this idea, we introduce the concept of a collection of correlated
compressors.

######  Definition A.3 (Collection of Correlated Compressors).

There exists a constant $\theta\geq 0$ such that the random operators
$\mathcal{C}_{1},\ldots\mathcal{C}_{n}$ satisfy:

$\displaystyle{\rm\mathbb{E}}\left[\mathcal{C}_{i}(x)\right]$
$\displaystyle=x$
$\displaystyle{\rm\mathbb{E}}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}(x)-x\right\|^{2}\right]$
$\displaystyle\leq\theta\left\|x\right\|^{2}$ (17)

for all $x\in\mathbb{R}^{d}$. If these conditions hold, we write
$\left\\{\mathcal{C}_{i}\right\\}_{i=1}^{n}\in\mathbb{P}(\theta)$.

Definition A.3 will play a key role in our upcoming advancements. But what
makes this assumption reasonable?

First, it is easy to note that condition (A.3) is weaker than (A.2). Indeed,
if $\left\\{\mathcal{C}_{i}\right\\}_{i=1}^{n}\in\mathbb{U}(A,B)$, then
inequality (A.3) holds with $\theta:=A-B$. It turns out that it is in fact
strictly weaker, as the following example shows.

######  Example A.4.

Let $n=2$, $d=1$. Let $\left\\{\zeta_{x}:x\in\mathbb{R}\right\\}$ be the
collection of independent Cauchy variables indexed by real numbers. Define
$\mathcal{C}_{1}(u)=u+\zeta_{u}$, and $\mathcal{C}_{2}(u)=u-\zeta_{u}$. Then

$\displaystyle\frac{1}{2}\left(\mathcal{C}_{1}(u)+\mathcal{C}_{2}(u)\right)=u,$

so $\mathcal{C}_{1}(u)$ and $\mathcal{C}_{2}(u)$ satisfy Definition A.3 with
$\theta=0$. However, for $u_{1}\neq u_{2}$, by the properties of Cauchy
distribution we have

$\displaystyle{\rm\mathbb{E}}\left[\left(\frac{1}{2}\left(\mathcal{C}_{1}(u)+\mathcal{C}_{2}(u)\right)-\frac{1}{2}\left(u_{1}+u_{2}\right)\right)^{2}\right]={\rm\mathbb{E}}\left[\left(\frac{1}{2}\left(\zeta_{1}+\zeta_{2}\right)\right)^{2}\right]=\frac{1}{4}{\rm\mathbb{E}}\left[\zeta_{1}^{2}+\zeta_{2}^{2}+2\zeta_{1}\zeta_{2}\right]=\infty.$

Thus, $\mathcal{C}_{1}(u)$ and $\mathcal{C}_{2}(u)$ do not satisfy Definition
A.2.

In fact, the condition specified in Definition A.3 does not impose any
restrictions on the compressor class when working with unbiased compressors.
This is because, for any set of compressors
$\mathcal{C}_{1},\ldots,\mathcal{C}_{n}\in\mathbb{U}(\omega)$, there exists
$\theta\geq 0$ such that
$\left\\{\mathcal{C}_{i}\right\\}_{i=1}^{n}\in\mathbb{P}(\theta)$, as shown in
the following lemma.

######  Lemma A.5.

  1. 1.

Let $\mathcal{C}_{1},\ldots,\mathcal{C}_{n}$ be a collection of compressors
such that $\mathcal{C}_{i}\in\mathbb{U}(\omega)$ for all $i\in[n]$. Then
$\left\\{\mathcal{C}_{i}\right\\}_{i=1}^{n}\in\mathbb{P}(\omega)$.

  2. 2.

Let us further assume that $\mathcal{C}_{1},\ldots,\mathcal{C}_{n}$ are
independent (Assumption 1.6). Then
$\left\\{\mathcal{C}_{i}\right\\}_{i=1}^{n}\in\mathbb{P}(\nicefrac{{\omega}}{{n}})$.

###### Proof.

  1. 1.

Jensen’s inequality gives

$\displaystyle{\rm\mathbb{E}}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}(u)-u\right\|^{2}\right]$
$\displaystyle\overset{\eqref{eq:jensen}}{\leq}\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|\mathcal{C}_{i}(u)-u\right\|^{2}\right]\overset{\textnormal{Def.}\ref{def:unbiased_compression}}{\leq}\frac{1}{n}\sum_{i=1}^{n}\omega\left\|u\right\|^{2}=\omega\left\|u\right\|^{2},$

so $\theta=\omega$.

  2. 2.

Using independence of compressors, we have

$\displaystyle{\rm\mathbb{E}}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}(u)-u\right\|^{2}\right]$
$\displaystyle=\frac{1}{n^{2}}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|\mathcal{C}_{i}(u)-u\right\|^{2}\right]\overset{\textnormal{Def.}\ref{def:unbiased_compression}}{\leq}\frac{1}{n^{2}}\sum_{i=1}^{n}\omega\left\|u\right\|^{2}=\frac{\omega}{n}\left\|u\right\|^{2}.$

Thus $\theta=\nicefrac{{\omega}}{{n}}$.

∎

However, the true advantages of employing correlated compressors become
apparent when the definition holds with $\theta=0$, as in the case of Perm$K$
compressors.

######  Lemma A.6.

Let $\mathcal{C}_{1},\ldots,\mathcal{C}_{n}$ be a collection of a)
SameRand$K$, b) independent Rand$K$, c) Perm$K$ compressors. Then

  1. a)

$\left\\{\mathcal{C}_{i}\right\\}_{i=1}^{n}\in\mathbb{P}(\omega)$ and
$\mathcal{C}_{i}\in\mathbb{U}(\omega)$ where $\omega=\nicefrac{{d}}{{K}}-1$
for all $i\in[n]$,

  2. b)

$\left\\{\mathcal{C}_{i}\right\\}_{i=1}^{n}\in\mathbb{P}(\nicefrac{{\omega}}{{n}})$
and $\mathcal{C}_{i}\in\mathbb{U}(\omega)$ where
$\omega=\nicefrac{{d}}{{K}}-1$ for all $i\in[n]$,

  3. c)

$\left\\{\mathcal{C}_{i}\right\\}_{i=1}^{n}\in\mathbb{P}(0)$ and
$\mathcal{C}_{i}\in\mathbb{U}(\omega)$ where $\omega=n-1$ for all $i\in[n]$.

###### Proof.

Unbiasedness follows easily from definitions of compressors (the proof for
Perm$K$ compressors can be found in Szlendak et al. (2021)). That
Rand$K\in\mathbb{U}(\nicefrac{{d}}{{K}}-1)$ (and hence trivially
SameRand$K\in\mathbb{U}(\nicefrac{{d}}{{K}}-1)$) is a well-known fact. Next,
the fact that a)
$\left\\{\mathcal{C}_{i}\right\\}_{i=1}^{n}\in\mathbb{P}(\omega)$ for
SameRand$K$ compressors and b)
$\left\\{\mathcal{C}_{i}\right\\}_{i=1}^{n}\in\mathbb{P}(\nicefrac{{\omega}}{{n}})$
for independent Rand$K$ compressors follows directly from Lemma A.5.

To compute $\omega$ for Perm$K$ compressor, first assume that $d\geq n$. Then
${\rm\mathbb{E}}\left[\left\|\mathcal{C}_{i}(x)\right\|^{2}\right]=n\left\|x\right\|^{2}$
(Szlendak et al., 2021), so

$\displaystyle{\rm\mathbb{E}}\left[\left\|\mathcal{C}_{i}(x)-x\right\|^{2}\right]\overset{\eqref{eq:vardecomp}}{=}{\rm\mathbb{E}}\left[\left\|\mathcal{C}_{i}(x)\right\|^{2}\right]-\left\|x\right\|^{2}=(n-1)\left\|x\right\|^{2}.$

Similarly, suppose that $d\leq n$, and write $n$ as $n=qd+r$, where
$q\in\mathbb{N}_{>0}$ and $0\leq r<d$. Then
${\rm\mathbb{E}}\left[\left\|\mathcal{C}_{i}(x)\right\|^{2}\right]=\nicefrac{{n}}{{q}}\left\|x\right\|^{2}$
(Szlendak et al., 2021), and hence

$\displaystyle{\rm\mathbb{E}}\left[\left\|\mathcal{C}_{i}(x)-x\right\|^{2}\right]\overset{\eqref{eq:vardecomp}}{=}{\rm\mathbb{E}}\left[\left\|\mathcal{C}_{i}(x)\right\|^{2}\right]-\left\|x\right\|^{2}=\left(\frac{n}{q}-1\right)\left\|x\right\|^{2}\leq\left(n-1\right)\left\|x\right\|^{2}.$

In both cases $\omega=n-1$.

Finally, by construction of Perm$K$, we have
$\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}(x)=x$, implying $\theta=0$. ∎

In what follows, when considering the Perm$K$ compressor, we shall assume for
simplicity that $d\geq n$. The results for $d<n$ are analogous.

###  Appendix B Biased Compressors

In addition to unbiased compressors (Definition 1.4), the literature of
compressed methods distinguishes another class of mappings:

######  Definition B.1.

A stochastic mapping $\mathcal{C}\,:\,\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$
is a biased compressor if there exists $\alpha\in(0,1]$ such that

$\displaystyle\qquad{\rm\mathbb{E}}\left[\left\|\mathcal{C}(x)-x\right\|^{2}\right]\leq(1-\alpha)\left\|x\right\|^{2}\quad\forall
x\in\mathbb{R}^{d}.$ (18)

The family of such compressors is denoted by $\mathbb{B}(\alpha)$. It is well-
known that if $\mathcal{C}\in\mathbb{U}(\omega),$ then
$(\omega+1)^{-1}\mathcal{C}\in\mathbb{B}\left((\omega+1)^{-1}\right)$, meaning
that the family of biased compressors is broader. A canonical example is the
Top$K\in\mathbb{B}(\nicefrac{{K}}{{d}})$ compressor, which preserves the $K$
largest in magnitude coordinates of the input vector (Beznosikov et al.,
2020).

###  Appendix C Properties of $L_{A}$ and $L_{B}$

We first prove the results from Section 4, starting with calculating the
constants $L_{A}$ and $L_{B}$ from Assumption 4.2 in some special cases.

Algorithm 1 MARINA-P

1: Input: initial model $x_{0}\in\mathbb{R}^{d}$ (stored on the server),
initial model shifts $w_{1}^{0}=\ldots=w_{n}^{0}=x^{0}$ (stored on the
workers), step size $\gamma>0$, probability $0<p\leq 1$, compressors
$\mathcal{C}_{1}^{t},\dots,\mathcal{C}_{n}^{t}\in\mathbb{U}(\omega_{P})$

2: for $t=0,\dots,T$ do

3: for $i=1,\dots,n$ in parallel do

4: Calculate $\nabla f_{i}(w_{i}^{t})$ and send it to the server  Workers
evaluate the gradients at the current model estimate

5: end forOn the server:

6: $g^{t}=\frac{1}{n}\sum_{i=1}^{n}\nabla f_{i}(w_{i}^{t})$ Server averages
the messages received from the workers

7: $x^{t+1}=x^{t}-\gamma g^{t}$ Server takes a gradient-type step to update
the global model

8: Sample $c^{t}\sim\textnormal{Bernoulli}(p)$

9: if $c^{t}=0$ then

10: Send $\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})$ to worker $i$ for $i\in[n]$
Server sends compressed messages to all workers with probability $1-p$

11: else

12: Send $x^{t+1}$ to worker $i$ for $i\in[n]$ Server sends the same
uncompressed message to all workers with probability $p$

13: end ifOn the workers:

14: for $i=1,\dots,n$ in parallel do

15: $w^{t+1}_{i}=\begin{cases}x^{t+1}&\text{if }c^{t}=1,\\\
w_{i}^{t}+\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})&\text{if }c^{t}=0\end{cases}$
Worker $i$ updates its local model shift

16: end for

17: end for

See 4.4

###### Proof.

From Assumption 1.5 it follows that

$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}(\nabla f_{i}(x+u_{i})-\nabla
f_{i}(x))\right\|^{2}$ $\displaystyle\overset{\eqref{eq:jensen}}{\leq}$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla f_{i}(x+u_{i})-\nabla
f_{i}(x)\right\|^{2}$
$\displaystyle\overset{\textnormal{Ass.}\ref{ass:local_lipschitz_constant}}{\leq}$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}L_{i}^{2}\left\|u_{i}\right\|^{2}$
$\displaystyle\leq$ $\displaystyle
L_{\max}^{2}\left(\frac{1}{n}\sum_{i=1}^{n}\left\|u_{i}\right\|^{2}\right),$

so Assumption 4.2 holds with $L_{A}=L_{\max}$ and $L_{B}=0$. ∎

See 4.5

###### Proof.

It is easy to verify that

$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}(\nabla f_{i}(x+u_{i})-\nabla
f_{i}(x))\right\|^{2}$ $\displaystyle=$
$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}\left(\mathbf{A}(x+u_{i})+b-\left(\mathbf{A}x+b\right)\right)\right\|^{2}$
$\displaystyle=$
$\displaystyle\left\|\mathbf{A}\left(\frac{1}{n}\sum_{i=1}^{n}u_{i}\right)\right\|^{2}$
$\displaystyle\leq$
$\displaystyle\left\|\mathbf{A}\right\|^{2}\left\|\frac{1}{n}\sum_{i=1}^{n}u_{i}\right\|^{2},$

meaning that Assumption 4.2 holds with $L_{A}=0$ and
$L_{B}=\left\|\mathbf{A}\right\|$. ∎

######  Lemma C.1.

Let Assumption 1.5 hold. Then, there exist constants $L_{A},L_{B}\geq 0$ such
that Assumption 4.2 holds and $L_{A}^{2}+L_{B}^{2}\leq L_{\max}^{2}$.

###### Proof.

Assumption 1.5 gives

$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}(\nabla f_{i}(x+u_{i})-\nabla
f_{i}(x))\right\|^{2}$ $\displaystyle\overset{\eqref{eq:jensen}}{\leq}$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla f_{i}(x+u_{i})-\nabla
f_{i}(x)\right\|^{2}$
$\displaystyle\overset{\textnormal{Ass.}\ref{ass:local_lipschitz_constant}}{\leq}$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}L_{i}^{2}\left\|u_{i}\right\|^{2}$
$\displaystyle\leq$ $\displaystyle
L_{\max}^{2}\left(\frac{1}{n}\sum_{i=1}^{n}\left\|u_{i}\right\|^{2}\right),$

and hence Assumption 4.2 holds with $L_{A}^{2}=L_{\max}^{2}$ and
$L_{B}^{2}=0$. ∎

######  Remark C.2.

Under Assumption 4.2 we have

$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}(\nabla f_{i}(x+u_{i})-\nabla
f_{i}(x))\right\|^{2}$
$\displaystyle\overset{\textnormal{Ass.}\ref{ass:functional}}{\leq}$
$\displaystyle
L_{A}^{2}\left(\frac{1}{n}\sum_{i=1}^{n}\left\|u_{i}\right\|^{2}\right)+L_{B}^{2}\left\|\frac{1}{n}\sum_{i=1}^{n}u_{i}\right\|^{2}$
$\displaystyle\overset{\textnormal{Ass.}\ref{ass:local_lipschitz_constant}}{\leq}$
$\displaystyle\left(L_{A}^{2}+L_{B}^{2}\right)\left(\frac{1}{n}\sum_{i=1}^{n}\left\|u_{i}\right\|^{2}\right),$

so, in principle, one could always set $L_{B}^{2}=0$. However, the bound could
be tightened by decreasing $L_{A}$ and increasing $L_{B}$. The smaller
$L_{A}$, the better the performance of our algorithms (see Corollaries D.4 and
E.3).

Now, we proceed to prove the result that relates the values of $L_{A}$ and
$L_{B}$ to the Hessians of the functions $f_{i}$.

See 4.8

###### Proof.

By the fundamental theorem of calculus,

$\displaystyle\nabla f_{i}(x+u_{i})-\nabla
f_{i}(x)=\int_{0}^{1}\nabla^{2}f_{i}(x+tu_{i})u_{i}dt=\left(\int_{0}^{1}\nabla^{2}f_{i}(x+tu_{i})dt\right)u_{i}=\mathbf{Q}_{i}u_{i},$

where $\mathbf{Q}_{i}=\int_{0}^{1}\nabla^{2}f_{i}(x+tu_{i})dt$. Letting
$\mathbf{Q}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{Q}_{i}$, we can write

$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}\left(\nabla
f_{i}(x+u_{i})-\nabla f_{i}(x)\right)\right\|^{2}$ $\displaystyle=$
$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}\mathbf{Q}_{i}u_{i}\right\|^{2}$
$\displaystyle=$
$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}\left(\mathbf{Q}_{i}-\mathbf{Q}\right)u_{i}+\mathbf{Q}\left(\frac{1}{n}\sum_{i=1}^{n}u_{i}\right)\right\|^{2}$
$\displaystyle\overset{\eqref{eq:young}}{\leq}$ $\displaystyle
2\left\|\frac{1}{n}\sum_{i=1}^{n}\left(\mathbf{Q}_{i}-\mathbf{Q}\right)u_{i}\right\|^{2}+2\left\|\mathbf{Q}\left(\frac{1}{n}\sum_{i=1}^{n}u_{i}\right)\right\|^{2}$
$\displaystyle\overset{\eqref{eq:jensen}}{\leq}$ $\displaystyle
2\frac{1}{n}\sum_{i=1}^{n}\left\|\left(\mathbf{Q}_{i}-\mathbf{Q}\right)u_{i}\right\|^{2}+2\left\|\mathbf{Q}\right\|^{2}\left\|\frac{1}{n}\sum_{i=1}^{n}u_{i}\right\|^{2}$
$\displaystyle\leq$ $\displaystyle
2\frac{1}{n}\sum_{i=1}^{n}\left\|\mathbf{Q}_{i}-\mathbf{Q}\right\|^{2}\left\|u_{i}\right\|^{2}+2\left\|\mathbf{Q}\right\|^{2}\left\|\frac{1}{n}\sum_{i=1}^{n}u_{i}\right\|^{2}.$

Further,

$\displaystyle\left\|\mathbf{Q}_{i}-\mathbf{Q}\right\|$ $\displaystyle=$
$\displaystyle\left\|\int_{0}^{1}\nabla^{2}f_{i}(x+tu_{i})dt-\frac{1}{n}\sum_{j=1}^{n}\int_{0}^{1}\nabla^{2}f_{j}(x+tu_{j})dt\right\|$
$\displaystyle=$
$\displaystyle\left\|\int_{0}^{1}\nabla^{2}f_{i}(x+tu_{i})dt-\int_{0}^{1}\frac{1}{n}\sum_{j=1}^{n}\nabla^{2}f_{j}(x+tu_{j})dt\right\|$
$\displaystyle=$
$\displaystyle\left\|\int_{0}^{1}\frac{1}{n}\sum_{j=1}^{n}\left(\nabla^{2}f_{i}(x+tu_{i})-\nabla^{2}f_{j}(x+tu_{j})\right)dt\right\|$
$\displaystyle\leq$
$\displaystyle\int_{0}^{1}\left\|\nabla^{2}f_{i}(x+tu_{i})-\frac{1}{n}\sum_{j=1}^{n}\nabla^{2}f_{j}(x+tu_{j})\right\|dt$
$\displaystyle\leq$ $\displaystyle\int_{0}^{1}D_{i}dt=D_{i},$

and

$\displaystyle\left\|\mathbf{Q}\right\|$ $\displaystyle=$
$\displaystyle\left\|\frac{1}{n}\sum_{j=1}^{n}\int_{0}^{1}\nabla^{2}f_{j}(x+tu_{j})dt\right\|=\left\|\int_{0}^{1}\frac{1}{n}\sum_{j=1}^{n}\nabla^{2}f_{j}(x+tu_{j})dt\right\|$
$\displaystyle\leq$
$\displaystyle\int_{0}^{1}\left\|\frac{1}{n}\sum_{j=1}^{n}\nabla^{2}f_{j}(x+tu_{j})\right\|dt\overset{\eqref{eq:jensen}}{\leq}\int_{0}^{1}\frac{1}{n}\sum_{j=1}^{n}\left\|\nabla^{2}f_{j}(x+tu_{j})\right\|dt$
$\displaystyle\leq$
$\displaystyle\int_{0}^{1}\frac{1}{n}\sum_{j=1}^{n}L_{j}dt=\frac{1}{n}\sum_{j=1}^{n}L_{j}.$

By combining the above, we get

$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}\left(\nabla
f_{i}(x+u_{i})-\nabla f_{i}(x)\right)\right\|^{2}$ $\displaystyle\leq$
$\displaystyle
2\frac{1}{n}\sum_{i=1}^{n}D_{i}^{2}\left\|u_{i}\right\|^{2}+2\left(\frac{1}{n}\sum_{j=1}^{n}L_{j}\right)^{2}\left\|\frac{1}{n}\sum_{i=1}^{n}u_{i}\right\|^{2}$
$\displaystyle\leq$ $\displaystyle
2\left(\max_{i}D_{i}^{2}\right)\left\|u_{i}\right\|^{2}+2\left(\frac{1}{n}\sum_{j=1}^{n}L_{j}\right)^{2}\left\|\frac{1}{n}\sum_{i=1}^{n}u_{i}\right\|^{2},$

which means that Assumption 4.2 holds with $L_{A}^{2}=2(\max_{i}D_{i}^{2})$
and $L_{B}^{2}=2\left(\frac{1}{n}\sum_{i=1}^{n}L_{i}\right)^{2}$. ∎

######  Remark C.3.

Clearly, if Assumption 1.5 holds, i.e., if there exists $L_{i}\geq 0$ such
that $\sup_{z_{i}\in\mathbb{R}^{d}}\left\|\nabla^{2}f_{i}(z_{i})\right\|\leq
L_{i}$ for all $i\in[n]$, then there exists $D_{i}$ such that
$\sup_{z_{1},\ldots,z_{n}\in\mathbb{R}^{d}}\left\|\nabla^{2}f_{i}(z_{i})-\frac{1}{n}\sum_{j=1}^{n}\nabla^{2}f_{j}(z_{j})\right\|\leq
D_{i}$, which means that this latter condition is not restrictive. Indeed,

$\displaystyle\left\|\nabla^{2}f_{i}(z_{i})-\frac{1}{n}\sum_{j=1}^{n}\nabla^{2}f_{j}(z_{j})\right\|$
$\displaystyle\leq\left\|\nabla^{2}f_{i}(z_{i})\right\|+\left\|\frac{1}{n}\sum_{j=1}^{n}\nabla^{2}f_{j}(z_{j})\right\|$
$\displaystyle\leq\left\|\nabla^{2}f_{i}(z_{i})\right\|+\frac{1}{n}\sum_{j=1}^{n}\left\|\nabla^{2}f_{j}(z_{j})\right\|$
$\displaystyle\leq L_{i}+\frac{1}{n}\sum_{j=1}^{n}L_{j}.$

However, $D_{i}$ can be small even if the constants $\\{L_{i}\\}$ are large,
as the next theorem shows.

See 4.9

###### Proof.

In this case $\nabla^{2}f_{i}(z_{i})\equiv\mathbf{A}_{i}$, and the result
easily follows from Theorem 4.8. ∎

###  Appendix D Convergence of MARINA-P in the General Case

####  D.1 Main Results

As promised, we now present a result generalizing Theorem 4.6 to all unbiased
compressors.

######  Theorem D.1.

Let Assumptions 1.1, 1.2 and 4.2 be satisfied and suppose that
$\left\\{\mathcal{C}_{i}^{t}\right\\}_{i=1}^{n}\in\mathbb{P}(\theta)$ (Def.
A.3) and $\mathcal{C}_{i}^{t}\in\mathbb{U}(\omega_{P})$ (Def. 1.4) for all
$i\in[n]$. Let

$\displaystyle
0<\gamma\leq\frac{1}{L+\sqrt{\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\theta\right)\left(\frac{1}{p}-1\right)}}.$

Letting

$\displaystyle\Psi^{t}=f(x^{t})-f^{*}+\frac{\gamma
L_{A}^{2}}{2p}\frac{1}{n}\sum_{i=1}^{n}\left\|w_{i}^{t}-x^{t}\right\|^{2}+\frac{\gamma
L_{B}^{2}}{2p}\left\|w^{t}-x^{t}\right\|^{2},$

for each $T\geq 1$ we have

$\displaystyle\sum_{t=0}^{T-1}\frac{1}{T}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]\leq\frac{2\Psi^{0}}{\gamma T}.$

Let us provide some important examples:

######  Theorem D.2.

Let Assumptions 1.1, 1.2 and 4.2 be satisfied. Choose

$\displaystyle\gamma=\begin{cases}\left(L+\sqrt{\left(L_{A}^{2}+L_{B}^{2}\right)\nicefrac{{\omega_{P}}}{{p}}}\right)^{-1}&\text{for
{\small\sf SameRandK} compressors}\\\
\left(L+\sqrt{\left(L_{A}^{2}+\nicefrac{{L_{B}^{2}}}{{n}}\right)\nicefrac{{\omega_{P}}}{{p}}}\right)^{-1}&\text{for
independent {\small\sf RandK} compressors}\\\
\left(L+L_{A}\sqrt{\nicefrac{{\omega_{P}}}{{p}}}\right)^{-1}&\text{for
{\small\sf PermK} compressors}\end{cases}$

and set $w_{i}^{0}=x^{0}$ for all $i\in[n]$. Then MARINA-P finds an
$\varepsilon$–stationary point after

$\displaystyle\bar{T}=\begin{cases}\mathcal{O}\left(\frac{\delta^{0}\left(L+\sqrt{\left(L_{A}^{2}+L_{B}^{2}\right)\nicefrac{{\omega_{P}}}{{p}}}\right)}{\varepsilon}\right)&\text{for
{\small\sf SameRandK} compressors}\\\
\mathcal{O}\left(\frac{\delta^{0}\left(L+\sqrt{\left(L_{A}^{2}+\nicefrac{{L_{B}^{2}}}{{n}}\right)\nicefrac{{\omega_{P}}}{{p}}}\right)}{\varepsilon}\right)&\text{for
independent {\small\sf RandK} compressors}\\\
\mathcal{O}\left(\frac{\delta^{0}\left(L+L_{A}\sqrt{\nicefrac{{\omega_{P}}}{{p}}}\right)}{\varepsilon}\right)&\text{for
{\small\sf PermK} compressors}\end{cases}$

iterations.

######  Remark D.3.

  * •

The result for Perm$K$ compressors proves Theorem 4.6.

  * •

The above theorem demonstrates the complexities for a) SameRand$K$, b)
independent Rand$K$ and c) Perm$K$ compressors. However, the result applies to
any families of compressors such that for all $t\geq 0$ we have a)
$\mathcal{C}_{1}^{t}=\ldots=\mathcal{C}_{n}^{t}=\mathcal{C}^{t}\in\mathbb{U}(\omega_{P})$,
b) $\mathcal{C}_{1}^{t},\ldots,\mathcal{C}_{n}^{t}\in\mathbb{U}(\omega_{P})$
are independent, and c)
$\mathcal{C}_{1}^{t},\ldots,\mathcal{C}_{n}^{t}\in\mathbb{U}(\omega_{P})\cap\mathbb{P}(\theta)$,
respectively.

We now derive the communication complexities:

######  Corollary D.4.

Let us take $p=\nicefrac{{1}}{{n}}$ and set $K=\nicefrac{{d}}{{n}}$
(corresponding to the sparsification level of a Perm$K$ compressor). Then, in
the view of Theorem D.2, the average s2w communication complexity of MARINA-P
is

$\displaystyle\begin{cases}\mathcal{O}\left(\frac{d\delta^{0}L}{n\varepsilon}+\frac{d\delta^{0}}{\varepsilon}\sqrt{L_{A}^{2}+L_{B}^{2}}\right)&\text{for
{\small\sf SameRandK} compressors}\\\
\mathcal{O}\left(\frac{d\delta^{0}L}{n\varepsilon}+\frac{d\delta^{0}}{\varepsilon}\sqrt{L_{A}^{2}+\frac{L_{B}^{2}}{n}}\right)&\text{for
independent {\small\sf RandK} compressors}\\\
\mathcal{O}\left(\frac{d\delta^{0}L}{n\varepsilon}+\frac{d\delta^{0}}{\varepsilon}L_{A}\right)&\text{for
{\small\sf PermK} compressors}\end{cases}$ (19)

######  Remark D.5.

  * •

The result for Perm$K$ compressors proves Corollary 4.7.

  * •

The key observation from (19) is the dependence on $L_{A}$ and $L_{B}$. In
particular, if $L_{A}\approx 0$ (which is the case, e.g., for homogeneous
quadratics), the above communication complexities are

$\displaystyle\begin{cases}\mathcal{O}\left(\frac{\delta^{0}}{\varepsilon}d\left(\frac{L}{n}+L_{B}\right)\right)&\text{for
{\small\sf SameRandK} compressors},\\\
\mathcal{O}\left(\frac{\delta^{0}}{\varepsilon}d\left(\frac{L}{n}+\frac{L_{B}}{\sqrt{n}}\right)\right)&\text{for
independent {\small\sf RandK} compressors},\\\
\mathcal{O}\left(\frac{\delta^{0}}{\varepsilon}d\frac{L}{n}\right)&\text{for
{\small\sf PermK} compressors}.\end{cases}$

Hence, only by sending different messages to different clients, one obtains
complexities improving with $n$. In particular, for Perm$K$, the complexity
scales linearly with the number of workers.

####  D.2 Proofs

To prove the results from the previous section, we first establish several
identities and inequalities satisfied by the sequences
$\\{w_{1}^{t},\ldots,w_{n}^{t}\\}_{t\geq 0}$. We start by studying the
evolution of the quantity $\left\|w_{i}^{t}-x^{t}\right\|^{2}$. In what
follows, ${\rm\mathbb{E}}_{t}\left[\cdot\right]$ denotes the expectation
conditioned on the first $t$ iterations.

######  Lemma D.6.

Let $\mathcal{C}_{i}^{t}\in\mathbb{U}(\omega_{P})$ for all $i\in[n]$. Then

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t+1}-x^{t+1}\right\|^{2}\right]\leq(1-p)\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+(1-p)\omega_{P}{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right].$

###### Proof.

In the view of definition of $w^{t+1}$, we get

$\displaystyle{\rm\mathbb{E}}_{t}\left[\left\|w_{i}^{t+1}-x^{t+1}\right\|^{2}\right]$
$\displaystyle=(1-p){\rm\mathbb{E}}_{t}\left[\left\|w_{i}^{t}+\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})-x^{t+1}\right\|^{2}\right]$
$\displaystyle\overset{\eqref{eq:vardecomp}}{=}(1-p){\rm\mathbb{E}}_{t}\left[\left\|\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})-(x^{t+1}-x^{t})\right\|^{2}\right]+(1-p){\rm\mathbb{E}}_{t}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]$
$\displaystyle\overset{\textnormal{Def.}\ref{def:unbiased_compression}}{\leq}(1-p)\omega_{P}\left\|x^{t+1}-x^{t}\right\|^{2}+(1-p)\left\|w_{i}^{t}-x^{t}\right\|^{2}.$

Averaging, taking expectation and using the tower property, we get the result.
∎

This lemma is less powerful: it is not an identity, and hence some information
is lost. Moreover, it focuses on a single client $i$, and is therefore not
able to take advantage of the correlation among the compressors. On the other
hand, it can be used in the convergence analysis without any need to restrict
the function class.

Next, we study the evolution of the quantity $\left\|w^{t}-x^{t}\right\|^{2}$.

######  Lemma D.7.

Let $\left\\{\mathcal{C}_{i}^{t}\right\\}_{i=1}^{n}\in\mathbb{P}(\theta)$.
Then

$\displaystyle{\rm\mathbb{E}}\left[\left\|w^{t+1}-x^{t+1}\right\|^{2}\right]$
$\displaystyle\leq(1-p){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]+(1-p)\theta{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right].$

###### Proof.

In the view of definition of $w^{t+1}$, we get

$\displaystyle{\rm\mathbb{E}}_{t}\left[\left\|w^{t+1}-x^{t+1}\right\|^{2}\right]$
$\displaystyle=$
$\displaystyle{\rm\mathbb{E}}_{t}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}w_{i}^{t+1}-x^{t+1}\right\|^{2}\right]$
$\displaystyle=$
$\displaystyle(1-p){\rm\mathbb{E}}_{t}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}(w_{i}^{t}+\mathcal{C}_{i}^{t}(x^{t+1}-x^{t}))-x^{t+1}\right\|^{2}\right]$
$\displaystyle=$
$\displaystyle(1-p){\rm\mathbb{E}}_{t}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})-(x^{t+1}-x^{t})-x^{t}+w^{t}\right\|^{2}\right]$
$\displaystyle\overset{\eqref{eq:vardecomp}}{=}$
$\displaystyle(1-p){\rm\mathbb{E}}_{t}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})-(x^{t+1}-x^{t})\right\|^{2}\right]+(1-p){\rm\mathbb{E}}_{t}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]$
$\displaystyle\overset{\textnormal{Def.}\ref{def:corr_compr}}{\leq}$
$\displaystyle(1-p)\theta\left\|x^{t+1}-x^{t}\right\|^{2}+(1-p)\left\|w^{t}-x^{t}\right\|^{2}.$

Taking expectation and using the tower property, we get the result. ∎

This lemma is more powerful since it is able to take advantage of the
correlation among the compressors. Indeed, if $\theta=0$ (as in the case of
Perm$K$ compressors), then it becomes an identity:

$\displaystyle{\rm\mathbb{E}}\left[\left\|w^{t+1}-x^{t+1}\right\|^{2}\right]=(1-p){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right].$

We now prove convergence of MARINA-P in the general case. See D.1

###### Proof.

First, combining the inequalities in Lemmas D.6 and D.7, we get

$\displaystyle\frac{\gamma
L_{A}^{2}}{2p}\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t+1}-x^{t+1}\right\|^{2}\right]+\frac{\gamma
L_{B}^{2}}{2p}{\rm\mathbb{E}}\left[\left\|w^{t+1}-x^{t+1}\right\|^{2}\right]$
$\displaystyle\leq\frac{\gamma
L_{A}^{2}}{2p}(1-p)\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+\frac{\gamma
L_{A}^{2}}{2p}(1-p)\omega_{P}{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle\quad+\frac{\gamma
L_{B}^{2}}{2p}(1-p){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]+\frac{\gamma
L_{B}^{2}}{2p}(1-p)\theta{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle=\frac{\gamma
L_{A}^{2}}{2p}(1-p)\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+\frac{\gamma
L_{B}^{2}}{2p}(1-p){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]$
$\displaystyle\quad+\frac{\gamma}{2p}\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\theta\right)(1-p){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right].$
(20)

Next, using Assumption 4.2, we have

$\displaystyle{\rm\mathbb{E}}\left[\left\|g^{t}-\nabla
f(x^{t})\right\|^{2}\right]$ $\displaystyle=$
$\displaystyle{\rm\mathbb{E}}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\left(\nabla
f_{i}(w_{i}^{t})-\nabla f_{i}(x^{t})\right)\right\|^{2}\right]$
$\displaystyle\overset{\textnormal{Ass.}\ref{ass:functional}}{\leq}$
$\displaystyle
L_{A}^{2}\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+L_{B}^{2}{\rm\mathbb{E}}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}w_{i}^{t}-x^{t}\right\|^{2}\right].$

Combining the above inequality with Lemma H.1 gives

$\displaystyle{\rm\mathbb{E}}\left[\delta^{t+1}\right]$ $\displaystyle\leq$
$\displaystyle{\rm\mathbb{E}}\left[\delta^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]-\left(\frac{1}{2\gamma}-\frac{L}{2}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|g^{t}-\nabla
f(x^{t})\right\|^{2}\right]$ (21) $\displaystyle\leq$
$\displaystyle{\rm\mathbb{E}}\left[\delta^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]-\left(\frac{1}{2\gamma}-\frac{L}{2}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle+\frac{\gamma}{2}\left(L_{A}^{2}\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+L_{B}^{2}{\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]\right).$

By adding inequalities (D.2) and (21), we get

$\displaystyle{\rm\mathbb{E}}\left[\Psi^{t+1}\right]$ $\displaystyle=$
$\displaystyle{\rm\mathbb{E}}\left[\delta^{t+1}\right]+\frac{\gamma
L_{A}^{2}}{2p}\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t+1}-x^{t+1}\right\|^{2}\right]+\frac{\gamma
L_{B}^{2}}{2p}{\rm\mathbb{E}}\left[\left\|w^{t+1}-x^{t+1}\right\|^{2}\right]$
$\displaystyle\leq$
$\displaystyle{\rm\mathbb{E}}\left[\delta^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]-\left(\frac{1}{2\gamma}-\frac{L}{2}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle+\frac{\gamma}{2}\left(L_{A}^{2}\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+L_{B}^{2}{\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]\right)$
$\displaystyle+\frac{\gamma
L_{A}^{2}}{2p}(1-p)\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+\frac{\gamma
L_{B}^{2}}{2p}(1-p){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]$
$\displaystyle+\frac{\gamma}{2p}\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\theta\right)(1-p){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle=$
$\displaystyle{\rm\mathbb{E}}\left[\Psi^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]-\left(\frac{1}{2\gamma}-\frac{L}{2}-\frac{\gamma}{2p}\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\theta\right)(1-p)\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle\leq$
$\displaystyle{\rm\mathbb{E}}\left[\Psi^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right],$

where in the last line we use the assumption on the step size and Lemma H.2.
Summing up the above inequality for $t=0,1,\ldots,T-1$ and rearranging the
terms, we get

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]\leq\frac{2}{\gamma
T}\left({\rm\mathbb{E}}\left[\Psi^{0}\right]-{\rm\mathbb{E}}\left[\Psi^{T}\right]\right)\leq\frac{2\Psi^{0}}{\gamma
T}.$

∎

With the above result, we can establish the iteration and communication
complexities of MARINA-P for three different compression schemes described in
Appendix A. First, let us prove a result when independent compressors are
used.

######  Theorem D.8.

Let Assumptions 1.1, 1.2 and 4.2 be satisfied and suppose that
$\mathcal{C}_{1}^{t},\ldots,\mathcal{C}_{n}^{t}$ is a collection of
independent compressors (Assumption 1.6) such that
$\mathcal{C}_{i}^{t}\in\mathbb{U}(\omega)$ for all $i\in[n]$,
$t\in\mathbb{N}$. Choose

$\displaystyle\gamma=\left(L+\sqrt{\left(L_{A}^{2}+\nicefrac{{L_{B}^{2}}}{{n}}\right)\nicefrac{{\omega_{P}}}{{p}}}\right)^{-1}$

and set $w_{i}^{0}=x^{0}$ for all $i\in[n]$. Then MARINA-P finds an
$\varepsilon$–stationary point after

$\displaystyle\bar{T}=\mathcal{O}\left(\frac{\delta^{0}\left(L+\sqrt{\left(L_{A}^{2}+\nicefrac{{L_{B}^{2}}}{{n}}\right)\nicefrac{{\omega_{P}}}{{p}}}\right)}{\varepsilon}\right)$

iterations.

###### Proof.

In view of Theorem D.1, the step size satisfies the inequality

$\displaystyle\gamma\leq\frac{1}{L+\sqrt{\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\theta\right)\left(\frac{1}{p}-1\right)}}.$

Since by Lemma A.5, when the compressors are independent we have
$\theta=\nicefrac{{\omega_{P}}}{{n}}$, the algorithm converges in

$\displaystyle\bar{T}=\frac{\Psi^{0}}{\varepsilon}\left(L+\sqrt{\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\frac{\omega_{P}}{n}\right)\left(\frac{1}{p}-1\right)}\right)=\mathcal{O}\left(\frac{\Psi^{0}}{\varepsilon}\left(L+\sqrt{\frac{\omega_{P}}{p}\left(L_{A}^{2}+\frac{L_{B}^{2}}{n}\right)}\right)\right)$
(22)

iterations. ∎

See D.2

###### Proof.

In view of Theorem D.1, the step size is such that

$\displaystyle\gamma\leq\frac{1}{L+\sqrt{\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\theta\right)\left(\frac{1}{p}-1\right)}}.$

We now use Lemma A.6 and substitute the vales of $\theta$ specific to each
compression type.

For SameRand$K$, we have $\theta=\omega_{P}$, so the algorithm converges after

$\displaystyle\bar{T}=\frac{\Psi^{0}}{\varepsilon}\left(L+\sqrt{\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\omega_{P}\right)\left(\frac{1}{p}-1\right)}\right)=\mathcal{O}\left(\frac{\Psi^{0}}{\varepsilon}\left(L+\sqrt{\frac{\omega_{P}}{p}\left(L_{A}^{2}+L_{B}^{2}\right)}\right)\right)$
(23)

iterations. Following the same reasoning as in the proof of Theorem D.8, for
Rand$K$ we have

$\displaystyle\bar{T}=\frac{\Psi^{0}}{\varepsilon}\left(L+\sqrt{\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\frac{\omega_{P}}{n}\right)\left(\frac{1}{p}-1\right)}\right)=\mathcal{O}\left(\frac{\Psi^{0}}{\varepsilon}\left(L+\sqrt{\frac{\omega_{P}}{p}\left(L_{A}^{2}+\frac{L_{B}^{2}}{n}\right)}\right)\right).$
(24)

Finally, for Perm$K$ we have $\theta=0$, so

$\displaystyle\bar{T}=\frac{\Psi^{0}}{\varepsilon}\left(L+\sqrt{L_{A}^{2}\omega_{P}\left(\frac{1}{p}-1\right)}\right)=\mathcal{O}\left(\frac{\Psi^{0}}{\varepsilon}\left(L+L_{A}\sqrt{\frac{\omega_{P}}{p}}\right)\right).$
(25)

The result follows from the fact that $w_{i}^{0}=x^{0}$ for all $i\in[n]$. ∎

See D.4

###### Proof.

The expected number of floats a server is relaying to each client at each
iteration of MARINA-P is

$\displaystyle pd+(1-p)k=\frac{d}{n}+\frac{n-1}{n}k\leq\frac{2d}{n}.$

Next, using the results from Lemma A.6, our choice of compressors and
parameters gives $\omega_{P}=\nicefrac{{d}}{{K}}-1=n-1$ in each of the three
cases. Hence, substituting $p=\nicefrac{{1}}{{n}}$ in (23), (24) and (25), we
obtain the following server-to-worker communication complexities:

  1. 1.

for SameRand$K$ compressors:

$\displaystyle\frac{d}{n}\times\frac{\delta^{0}}{\varepsilon}\left(L+\sqrt{\omega_{P}\left(L_{A}^{2}+L_{B}^{2}\right)\left(\frac{1}{p}-1\right)}\right)$
$\displaystyle=\frac{\delta^{0}}{\varepsilon}\left(\frac{d}{n}L+\frac{d}{n}\sqrt{\left(L_{A}^{2}+L_{B}^{2}\right)(n-1)^{2}}\right)$
$\displaystyle=\mathcal{O}\left(\frac{\delta^{0}}{\varepsilon}\left(\frac{d}{n}L+d\sqrt{L_{A}^{2}+L_{B}^{2}}\right)\right),$

  2. 2.

for Rand$K$ compressors:

$\displaystyle\frac{d}{n}\times\frac{\delta^{0}}{\varepsilon}\left(L+\sqrt{\omega_{P}\left(L_{A}^{2}+\frac{L_{B}^{2}}{n}\right)\left(\frac{1}{p}-1\right)}\right)$
$\displaystyle=\frac{\delta^{0}}{\varepsilon}\left(\frac{d}{n}L+\frac{d}{n}\sqrt{\left(L_{A}^{2}+\frac{L_{B}^{2}}{n}\right)(n-1)^{2}}\right)$
$\displaystyle=\mathcal{O}\left(\frac{\delta^{0}}{\varepsilon}\left(\frac{d}{n}L+d\sqrt{L_{A}^{2}+\frac{L_{B}^{2}}{n}}\right)\right),$

  3. 3.

for Perm$K$ compressors:

$\displaystyle\frac{d}{n}\times\frac{\delta^{0}}{\varepsilon}\left(L+\sqrt{L_{A}^{2}\omega_{P}\left(\frac{1}{p}-1\right)}\right)$
$\displaystyle=\frac{\delta^{0}}{\varepsilon}\left(\frac{d}{n}L+\frac{d}{n}L_{A}\sqrt{(n-1)^{2}}\right)$
$\displaystyle=\mathcal{O}\left(\frac{\delta^{0}}{\varepsilon}\left(\frac{d}{n}L+dL_{A}\right)\right).$

∎

####  D.3 Polyak-Łojasiewicz condition

#####  D.3.1 Main Results

To complete the theory, we now establish a convergence result for MARINA-P
under the Polyak-Łojasiewicz assumption.

######  Assumption D.9 (Polyak-Łojasiewicz condition).

The function $f$ satisfies Polyak-Łojasiewicz (PŁ) condition with parameter
$\mu$, i.e., for all $x\in\mathbb{R}^{d}$ there exists
$x^{*}\in\arg\min_{x\in\mathbb{R}^{d}}f(x)$ such that

$\displaystyle 2\mu\left(f(x)-f(x^{*})\right)\leq\left\|\nabla
f(x)\right\|^{2}.$ (26)

######  Theorem D.10.

Let Assumptions 1.1, 1.2, 4.2 and D.9 be satisfied and suppose that
$\left\\{\mathcal{C}_{i}^{t}\right\\}_{i=1}^{n}\in\mathbb{P}(\theta)$ and
$\mathcal{C}_{i}^{t}\in\mathbb{U}(\omega_{P})$ for all $i\in[n]$. Take

$\displaystyle
0<\gamma\leq\min\left\\{\frac{1}{L+\sqrt{2\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\theta\right)\left(\frac{1}{p}-1\right)}},\frac{p}{2\mu}\right\\}.$
(27)

Letting

$\displaystyle\Psi^{t}=f(x^{t})-f^{*}+\frac{\gamma
L_{A}^{2}}{p}\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+\frac{\gamma
L_{B}^{2}}{p}{\rm\mathbb{E}}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}w_{i}^{t}-x^{t}\right\|^{2}\right],$
(28)

for each $T\geq 1$ we have

$\displaystyle{\rm\mathbb{E}}\left[\Psi^{T}\right]\leq\left(1-\gamma\mu\right)^{T}\Psi^{0}.$

######  Corollary D.11.

Let $\mathcal{C}_{i}^{t}\in\mathbb{P}(0)$ for all $i\in[n]$ (e.g. Perm$K$),
choose $p=1/(\omega_{P}+1).$ Then, in the view of Theorem D.10, Algorithm 1
ensures that ${\rm\mathbb{E}}\left[f(x^{T})-f^{*}\right]\leq\varepsilon$ after

$\displaystyle\mathcal{O}\left(\max\left\\{\frac{L+L_{A}\omega_{P}}{\mu},\omega_{P}+1\right\\}\log\frac{\Psi^{0}}{\varepsilon}\right)$

iterations.

######  Corollary D.12.

Let $\mathcal{C}_{i}^{t}$ be the Perm$K$ compressors
($K=\nicefrac{{d}}{{n}}$). Then, in the view of Corollary D.11, the s2w
communication complexity of MARINA-P with Perm$K$ is

$\displaystyle\mathcal{O}\left(\left(\frac{dL}{n\mu}+\frac{dL_{A}}{\mu}+d\right)\log\frac{\Psi^{0}}{\varepsilon}\right).$

#####  D.3.2 Proofs

See D.10

###### Proof.

We proceed similarly as in the proof of Theorem D.1. Combining the
inequalities in Lemmas D.6 and D.7 gives

$\displaystyle\frac{\gamma
L_{A}^{2}}{p}\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t+1}-x^{t+1}\right\|^{2}\right]+\frac{\gamma
L_{B}^{2}}{p}{\rm\mathbb{E}}\left[\left\|w^{t+1}-x^{t+1}\right\|^{2}\right]$
$\displaystyle\leq\frac{\gamma
L_{A}^{2}}{p}(1-p)\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+\frac{\gamma
L_{A}^{2}}{p}(1-p)\omega_{P}{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle\quad+\frac{\gamma
L_{B}^{2}}{p}(1-p){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]+\frac{\gamma
L_{B}^{2}}{p}(1-p)\theta{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle=\frac{\gamma
L_{A}^{2}}{p}(1-p)\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+\frac{\gamma
L_{B}^{2}}{p}(1-p){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]$
$\displaystyle\quad+\frac{\gamma}{p}\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\theta\right)(1-p){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right].$
(29)

By adding inequalities (21) and (D.3.2), we get

$\displaystyle{\rm\mathbb{E}}\left[\Psi^{t+1}\right]$ $\displaystyle=$
$\displaystyle{\rm\mathbb{E}}\left[\delta^{t+1}\right]+\frac{\gamma
L_{A}^{2}}{p}\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t+1}-x^{t+1}\right\|^{2}\right]+\frac{\gamma
L_{B}^{2}}{p}{\rm\mathbb{E}}\left[\left\|w^{t+1}-x^{t+1}\right\|^{2}\right]$
$\displaystyle\leq$
$\displaystyle{\rm\mathbb{E}}\left[\delta^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]-\left(\frac{1}{2\gamma}-\frac{L}{2}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle+\frac{\gamma}{2}\left(L_{A}^{2}\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+L_{B}^{2}{\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]\right)$
$\displaystyle+\frac{\gamma
L_{A}^{2}}{p}(1-p)\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+\frac{\gamma
L_{B}^{2}}{p}(1-p){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]$
$\displaystyle+\frac{\gamma}{p}\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\theta\right)(1-p){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle=$
$\displaystyle{\rm\mathbb{E}}\left[\delta^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]-\left(\frac{1}{2\gamma}-\frac{L}{2}-\frac{\gamma}{p}\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\theta\right)(1-p)\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle+\gamma
L_{A}^{2}\left(\frac{1}{p}-\frac{1}{2}\right)\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+\gamma
L_{B}^{2}\left(\frac{1}{p}-\frac{1}{2}\right){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]$
$\displaystyle\overset{\textnormal{Ass.}\ref{ass:pl},\eqref{eq:marinap_pl_gen_step}}{\leq}$
$\displaystyle\left(1-\gamma\mu\right){\rm\mathbb{E}}\left[\delta^{t}\right]+\frac{\gamma
L_{A}^{2}}{p}\left(1-\gamma\mu\right)\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+\frac{\gamma
L_{B}^{2}}{p}\left(1-\gamma\mu\right){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]$
$\displaystyle=$
$\displaystyle\left(1-\gamma\mu\right){\rm\mathbb{E}}\left[\Psi^{t}\right],$

where the last inequality follows from the Polyak-Łojasiewicz condition, Lemma
H.2 and our choice of $\gamma$. Applying the above inequality iteratively, we
finish the proof. ∎

See D.11

###### Proof.

In view of Theorem D.10, the step size satisfies

$\displaystyle\gamma\leq\min\left\\{\frac{1}{L+\sqrt{2\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\theta\right)\left(\frac{1}{p}-1\right)}},\frac{p}{2\mu}\right\\}.$

Therefore, since $\theta=0$ and $p=1/(\omega_{P}+1),$ the algorithm converges
after

$\displaystyle\bar{T}=\max\left\\{\frac{L+\sqrt{2\left(L_{A}^{2}\omega_{P}+L_{B}^{2}\theta\right)\left(\frac{1}{p}-1\right)}}{\mu},\frac{2}{p}\right\\}\log\frac{\Psi^{0}}{\varepsilon}=\mathcal{O}\left(\max\left\\{\frac{L+L_{A}\omega_{P}}{\mu},\omega_{P}+1\right\\}\log\frac{\Psi^{0}}{\varepsilon}\right)$

iterations. ∎

See D.12

###### Proof.

For Perm$K$, $\omega_{P}=n-1.$ Therefore, the iteration complexity is

$\displaystyle\mathcal{O}\left(\max\left\\{\frac{L+L_{A}n}{\mu},n\right\\}\log\frac{\Psi^{0}}{\varepsilon}\right).$

Since the expected number of floats the server is relaying to each client is

$\displaystyle pd+(1-p)k=\frac{d}{n}+\frac{n-1}{n}k\leq\frac{2d}{n},$

the server-to-worker communication complexity is

$\displaystyle\mathcal{O}\left(\max\left\\{\frac{\frac{d}{n}L+dL_{A}}{\mu},d\right\\}\log\frac{\Psi^{0}}{\varepsilon}\right).$

∎

###  Appendix E Convergence of M3 in the General Case

We now move on to the bidirectionally compressed method. Below is a
generalization of Theorem 5.1 to all unbiased compressors.

####  E.1 Main Results

######  Theorem E.1.

Let Assumptions 1.1, 1.2, 1.5 and 4.2 hold and suppose that the compressors
$\mathcal{Q}_{i}^{t}\in\mathbb{U}(\omega_{D})$ satisfy Assumption 1.6,
$\left\\{\mathcal{C}_{i}^{t}\right\\}_{i=1}^{n}\in\mathbb{P}(\theta)$ and
$\mathcal{C}_{i}^{t}\in\mathbb{U}(\omega_{P})$ for all $i\in[n]$. Let
$\gamma>0$ be such that

$\displaystyle\gamma\leq\left(L+\sqrt{288\left(\left(\frac{\theta}{p_{P}}+\frac{1+\theta
p_{P}}{\beta^{2}}\right)L_{B}^{2}+\left(\frac{\omega_{P}}{p_{P}}+\frac{1+\omega_{P}p_{P}}{\beta^{2}}\right)L_{A}^{2}+\left(\frac{\omega_{D}\omega_{P}\beta}{np_{D}}+\frac{\omega_{D}(1+\omega_{P}p_{P})}{np_{D}}\right)L_{\max}^{2}\right)}\right)^{-1}.$

Letting

$\displaystyle\Psi^{t}=\delta^{t}+\kappa\left\|g^{t}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t})\right\|^{2}+\eta\left\|z^{t}-w^{t}\right\|^{2}+\nu\frac{1}{n}\sum_{i=1}^{n}\left\|z^{t}_{i}-w^{t}_{i}\right\|^{2}+\rho\left\|w^{t}-x^{t}\right\|^{2}+\mu\frac{1}{n}\sum_{i=1}^{n}\left\|w_{i}^{t}-x^{t}\right\|^{2},$

where $\kappa=\frac{\gamma}{p_{D}}$, $\eta=\frac{4\gamma L_{B}^{2}}{\beta}$,
$\nu=\frac{4\gamma L_{A}^{2}}{\beta}+\frac{6\gamma\omega_{D}\beta
L_{\max}^{2}}{np_{D}}$, $\rho=32\gamma
L_{B}^{2}\left(\frac{1}{p_{P}}+\frac{p_{P}}{\beta^{2}}\right)$ and
$\mu=32\gamma
L_{A}^{2}\left(\frac{1}{p_{P}}+\frac{p_{P}}{\beta^{2}}\right)+\frac{48\gamma\omega_{D}L_{\max}^{2}}{np_{D}}\left(\beta+p_{P}\right)$,
M3 ensures that

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]=\mathcal{O}\left(\frac{\Psi^{0}}{\gamma
T}\right).$

We now simplify the above result by considering that $\theta=0.$

######  Corollary E.2.

Let $\mathcal{C}_{i}^{t}\in\mathbb{P}(0)$ for all $i\in[n]$ (e.g. Perm$K$),
choose $p_{P}=1/(\omega_{P}+1),$ $p_{D}=1/(\omega_{D}+1)$ and

$\displaystyle\beta=\min\left\\{\left(\frac{n}{\omega_{D}\omega_{P}(\omega_{D}+1)}\right)^{1/3},1\right\\}.$

Then, in the view of Theorem E.1, the iteration complexity is

$\displaystyle\mathcal{O}\left(\frac{\Psi^{0}}{\varepsilon}\left(L_{\max}+\left(\frac{\omega_{D}\omega_{P}(\omega_{D}+1)}{n}\right)^{1/3}L_{\max}+\sqrt{\frac{\omega_{D}(\omega_{D}+1)}{n}}L_{\max}+\sqrt{\omega_{P}(\omega_{P}+1)}L_{A}\right)\right).$

We now give the bound for the total communication complexity of M3.

######  Corollary E.3.

Let $\mathcal{C}_{i}^{t}$ be the Perm$K$ compressors and $\mathcal{Q}_{i}^{t}$
be the independent (Assumption 1.6) Rand$K$ compressors, both with
$K=\nicefrac{{d}}{{n}}$. Then, in the view of Corollary E.2, the iteration
complexity is

$\displaystyle\mathcal{O}\left(\frac{\Psi^{0}}{\varepsilon}\left(n^{2/3}L_{\max}+nL_{A}\right)\right),$

and the total communication complexity is

$\displaystyle\mathcal{O}\left(\frac{\Psi^{0}}{\varepsilon}\left(\frac{dL_{\max}}{n^{1/3}}+dL_{A}\right)\right).$

######  Remark E.4.

The above result proves the complexities from Theorem 5.1.

####  E.2 Proofs

Similar to our approach from the previous section, we start by establishing
several inequalities satisfied by the sequences
$\\{w_{1}^{t},\ldots,w_{n}^{t}\\}_{t\geq 0}$,
$\\{z_{1}^{t},\ldots,z_{n}^{t}\\}_{t\geq 0}$ and
$\\{g_{1}^{t},\ldots,g_{n}^{t}\\}_{t\geq 0}$.

Algorithm 2 M3

1: Input: initial model $x_{0}\in\mathbb{R}^{d}$ (stored on the server),
initial model shifts $w_{i}^{0}=z_{i}^{0}=x^{0}$ (stored on the workers),
initial gradient estimators $g^{0}=\nabla f(x^{0})$ (stored on the sever),
$i\in[n]$, step size $\gamma>0$, probabilities $0<p_{P},p_{D}\leq 1$,
compressors
$\mathcal{C}_{1}^{t},\ldots,\mathcal{C}_{n}^{t}\in\mathbb{U}(\omega_{P})\cap\mathbb{P}(\theta)$,
$\mathcal{Q}_{1}^{t},\ldots,\mathcal{Q}_{n}^{t}\in\mathbb{U}(\omega_{D})$ for
all $t\geq 0.$

2: for $t=0,\dots,T$ do

3: $x^{t+1}=x^{t}-\gamma g^{t}$ Server takes a gradient-type step to update
the global model

4: Sample $c_{P}^{t}\sim\textnormal{Bernoulli}(p_{P})$,
$c_{D}^{t}\sim\textnormal{Bernoulli}(p_{D})$

5: For $i\in[n]$, send $\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})$ to worker $i$ if
$c_{P}^{t}=0$ and $x^{t+1}$ otherwise

6: for $i=1,\dots,n$ in parallel do

7: $w^{t+1}_{i}=\begin{cases}x^{t+1}&\textnormal{if }c_{P}^{t}=1,\\\
w_{i}^{t}+\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})&\textnormal{if
}c_{P}^{t}=0,\end{cases}$ Worker $i$ updates its local model shift

8: $z_{i}^{t+1}=\beta w_{i}^{t+1}+(1-\beta)z_{i}^{t}$ Worker $i$ takes the
momentum step

9: Send $\mathcal{Q}_{i}^{t}(\nabla f_{i}(z_{i}^{t+1})-\nabla
f_{i}(z_{i}^{t}))$ to the server if $c_{D}^{t}=0$ and $\nabla
f_{i}(z_{i}^{t+1})$ otherwise

10: end for

11: if $c_{D}^{t}=1$ then

12: $g^{t+1}=\frac{1}{n}\sum_{i=1}^{n}f_{i}(z_{i}^{t+1})$

13: else

14: $g^{t+1}=g^{t}+\frac{1}{n}\sum_{i=1}^{n}\mathcal{Q}_{i}^{t}(\nabla
f_{i}(z_{i}^{t+1})-\nabla f_{i}(z_{i}^{t}))$

15: end if

16: end for

(maintaining only the sequence $g^{t}$ in the implementation is sufficient;
the sequences $g^{t}_{i}$ from (LABEL:eq:mthree) are _virtual_)

######  Lemma E.5.

Let $\mathcal{C}_{i}^{t}\in\mathbb{U}(\omega_{P})$ for all $i\in[n]$ and
$\left\\{\mathcal{C}_{i}^{t}\right\\}_{i=1}^{n}\in\mathbb{P}(\theta)$. Then

$\displaystyle{\rm\mathbb{E}}_{t}\left[\left\|w^{t+1}_{i}-z^{t}_{i}\right\|^{2}\right]\leq\left\|(x^{t+1}-x^{t})-p_{P}(w_{i}^{t}-x^{t})+(w_{i}^{t}-z^{t}_{i})\right\|^{2}+p_{P}\left\|w_{i}^{t}-x^{t}\right\|^{2}+\omega_{P}\left\|x^{t+1}-x^{t}\right\|^{2}$

for all $i\in[n],$ and

$\displaystyle{\rm\mathbb{E}}_{t}\left[\left\|w^{t+1}-z^{t}\right\|^{2}\right]\leq\left\|(x^{t+1}-x^{t})-p_{P}(w^{t}-x^{t})+(w^{t}-z^{t})\right\|^{2}+p_{P}\left\|w^{t}-x^{t}\right\|^{2}+\theta\left\|x^{t+1}-x^{t}\right\|^{2}.$

###### Proof.

Using the definition of $w_{i}^{t+1}$, we have

$\displaystyle{\rm\mathbb{E}}_{t}\left[w^{t+1}_{i}\right]=x^{t+1}+(1-p_{P})(w_{i}^{t}-x^{t})$

and hence

$\displaystyle{\rm\mathbb{E}}_{t}\left[\left\|w^{t+1}_{i}-z^{t}_{i}\right\|^{2}\right]$
$\displaystyle\overset{\eqref{eq:vardecomp}}{=}$
$\displaystyle\left\|x^{t+1}+(1-p_{P})(w_{i}^{t}-x^{t})-z^{t}_{i}\right\|^{2}+{\rm\mathbb{E}}_{t}\left[\left\|w^{t+1}_{i}-(x^{t+1}+(1-p_{P})(w_{i}^{t}-x^{t}))\right\|^{2}\right]$
$\displaystyle=$
$\displaystyle\left\|(x^{t+1}-x^{t})-p_{P}(w_{i}^{t}-x^{t})+(w_{i}^{t}-z^{t}_{i})\right\|^{2}+{\rm\mathbb{E}}_{t}\left[\left\|w^{t+1}_{i}-(x^{t+1}+(1-p_{P})(w_{i}^{t}-x^{t}))\right\|^{2}\right].$

Using the definition of $w_{i}^{t+1}$ again, we get

$\displaystyle{\rm\mathbb{E}}_{t}\left[\left\|w^{t+1}_{i}-z^{t}_{i}\right\|^{2}\right]$
$\displaystyle=$
$\displaystyle\left\|(x^{t+1}-x^{t})-p_{P}(w_{i}^{t}-x^{t})+(w_{i}^{t}-z^{t}_{i})\right\|^{2}+p_{P}\left\|x^{t+1}-(x^{t+1}+(1-p_{P})(w_{i}^{t}-x^{t}))\right\|^{2}$
$\displaystyle+(1-p_{P}){\rm\mathbb{E}}_{t}\left[\left\|w_{i}^{t}+\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})-(x^{t+1}+(1-p_{P})(w_{i}^{t}-x^{t}))\right\|^{2}\right]$
$\displaystyle=$
$\displaystyle\left\|(x^{t+1}-x^{t})-p_{P}(w_{i}^{t}-x^{t})+(w_{i}^{t}-z^{t}_{i})\right\|^{2}+p_{P}(1-p_{P})^{2}\left\|w_{i}^{t}-x^{t}\right\|^{2}$
$\displaystyle+(1-p_{P}){\rm\mathbb{E}}_{t}\left[\left\|\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})-(x^{t+1}-x^{t})+p_{P}(w_{i}^{t}-x^{t})\right\|^{2}\right]$
$\displaystyle\overset{\eqref{eq:vardecomp}}{=}$
$\displaystyle\left\|(x^{t+1}-x^{t})-p_{P}(w_{i}^{t}-x^{t})+(w_{i}^{t}-z^{t}_{i})\right\|^{2}+p_{P}(1-p_{P})^{2}\left\|w_{i}^{t}-x^{t}\right\|^{2}$
$\displaystyle+(1-p_{P})p_{P}^{2}\left\|w_{i}^{t}-x^{t}\right\|^{2}+(1-p_{P}){\rm\mathbb{E}}_{t}\left[\left\|\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})-(x^{t+1}-x^{t})\right\|^{2}\right]$
$\displaystyle\overset{\textnormal{Def.}\ref{def:unbiased_compression}}{\leq}$
$\displaystyle\left\|(x^{t+1}-x^{t})-p_{P}(w_{i}^{t}-x^{t})+(w_{i}^{t}-z^{t}_{i})\right\|^{2}+p_{P}\left\|w_{i}^{t}-x^{t}\right\|^{2}+\omega_{P}\left\|x^{t+1}-x^{t}\right\|^{2}.$

Using the same reasoning, we now prove the second inequality:

$\displaystyle{\rm\mathbb{E}}_{t}\left[\left\|w^{t+1}-z^{t}\right\|^{2}\right]$
$\displaystyle\overset{\eqref{eq:vardecomp}}{=}$
$\displaystyle\left\|x^{t+1}+(1-p_{P})(w^{t}-x^{t})-z^{t}\right\|^{2}+{\rm\mathbb{E}}_{t}\left[\left\|w^{t+1}-(x^{t+1}+(1-p_{P})(w^{t}-x^{t}))\right\|^{2}\right]$
$\displaystyle=$
$\displaystyle\left\|(x^{t+1}-x^{t})-p_{P}(w^{t}-x^{t})+(w^{t}-z^{t})\right\|^{2}$
$\displaystyle+{\rm\mathbb{E}}_{t}\left[\left\|w^{t+1}-(x^{t+1}+(1-p_{P})(w^{t}-x^{t}))\right\|^{2}\right]$
$\displaystyle=$
$\displaystyle\left\|(x^{t+1}-x^{t})-p_{P}(w^{t}-x^{t})+(w^{t}-z^{t})\right\|^{2}+p_{P}(1-p_{P})^{2}\left\|w^{t}-x^{t}\right\|^{2}$
$\displaystyle+(1-p_{P}){\rm\mathbb{E}}_{t}\left[\left\|w^{t}+\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})-(x^{t+1}+(1-p_{P})(w^{t}-x^{t}))\right\|^{2}\right]$
$\displaystyle=$
$\displaystyle\left\|(x^{t+1}-x^{t})-p_{P}(w^{t}-x^{t})+(w^{t}-z^{t})\right\|^{2}+p_{P}(1-p_{P})^{2}\left\|w^{t}-x^{t}\right\|^{2}$
$\displaystyle+(1-p_{P}){\rm\mathbb{E}}_{t}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})-(x^{t+1}-x^{t})+p_{P}(w^{t}-x^{t})\right\|^{2}\right]$
$\displaystyle\overset{\eqref{eq:vardecomp}}{=}$
$\displaystyle\left\|(x^{t+1}-x^{t})-p_{P}(w^{t}-x^{t})+(w^{t}-z^{t})\right\|^{2}+p_{P}(1-p_{P})^{2}\left\|w^{t}-x^{t}\right\|^{2}$
$\displaystyle+(1-p_{P}){\rm\mathbb{E}}_{t}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}^{t}(x^{t+1}-x^{t})-(x^{t+1}-x^{t})\right\|^{2}\right]+p_{P}^{2}(1-p_{P})\left\|w^{t}-x^{t}\right\|^{2}$
$\displaystyle\overset{\textnormal{Def.}\ref{def:corr_compr}}{\leq}$
$\displaystyle\left\|(x^{t+1}-x^{t})-p_{P}(w^{t}-x^{t})+(w^{t}-z^{t})\right\|^{2}+p_{P}\left\|w^{t}-x^{t}\right\|^{2}+\theta\left\|x^{t+1}-x^{t}\right\|^{2}.$

∎

######  Lemma E.6.

Let Assumption 1.5 hold. Furthermore, suppose that the compressors
$\mathcal{Q}_{i}^{t}\in\mathbb{U}(\omega_{D})$ satisfy Assumption 1.6 and that
$\mathcal{C}_{i}^{t}\in\mathbb{U}(\omega_{P})$ for $i\in[n]$. Then

$\displaystyle{\rm\mathbb{E}}\left[\left\|g^{t+1}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t+1})\right\|^{2}\right]$
$\displaystyle\leq\frac{\omega_{D}L_{\max}^{2}}{n}\left(4p_{P}\beta^{2}{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|w^{t}_{i}-x^{t}\right\|^{2}\right]+3\beta^{2}{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|z^{t}_{i}-w_{i}^{t}\right\|^{2}\right]+3(\omega_{P}+1)\beta^{2}{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]\right)$
$\displaystyle\quad+(1-p_{D}){\rm\mathbb{E}}\left[\left\|g^{t}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t})\right\|^{2}\right].$

###### Proof.

First, from the definition of $g_{i}^{t+1},$ we get

$\displaystyle{\rm\mathbb{E}}\left[\left\|g^{t+1}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t+1})\right\|^{2}\right]=(1-p_{D}){\rm\mathbb{E}}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\left(g_{i}^{t}+\mathcal{Q}_{i}^{t}(\nabla
f_{i}(z_{i}^{t+1})-\nabla f_{i}(z_{i}^{t}))-\nabla
f_{i}(z_{i}^{t+1})\right)\right\|^{2}\right]$

and hence

$\displaystyle{\rm\mathbb{E}}\left[\left\|g^{t+1}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t+1})\right\|^{2}\right]$ (30)
$\displaystyle\overset{\eqref{eq:vardecomp}}{=}$
$\displaystyle(1-p_{D}){\rm\mathbb{E}}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathcal{Q}_{i}^{t}\left(\nabla
f_{i}(z_{i}^{t+1})-\nabla
f_{i}(z_{i}^{t})\right)-\frac{1}{n}\sum_{i=1}^{n}\left(\nabla
f_{i}(z_{i}^{t+1})-\nabla f_{i}(z_{i}^{t})\right)\right\|^{2}\right]$
$\displaystyle+(1-p_{D}){\rm\mathbb{E}}\left[\left\|g^{t}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t})\right\|^{2}\right]$
$\displaystyle\overset{\textnormal{Def.}\ref{def:unbiased_compression},\eqref{ass:independent}}{\leq}$
$\displaystyle\frac{\omega_{D}}{n}{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}(z_{i}^{t+1})-\nabla
f_{i}(z_{i}^{t})\right\|^{2}\right]+(1-p_{D}){\rm\mathbb{E}}\left[\left\|g^{t}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t})\right\|^{2}\right]$
$\displaystyle\overset{\textnormal{Ass.}\ref{ass:local_lipschitz_constant}}{\leq}$
$\displaystyle\frac{\omega_{D}L_{\max}^{2}}{n}{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|z_{i}^{t+1}-z_{i}^{t}\right\|^{2}\right]+(1-p_{D}){\rm\mathbb{E}}\left[\left\|g^{t}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t})\right\|^{2}\right].$

Let us consider the first term separately:

$\displaystyle{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|z_{i}^{t+1}-z_{i}^{t}\right\|^{2}\right]={\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|\beta
w^{t+1}_{i}+(1-\beta)z^{t}_{i}-z_{i}^{t}\right\|^{2}\right]=\beta^{2}{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|w^{t+1}_{i}-z^{t}_{i}\right\|^{2}\right].$

Using the result from Lemma E.5, we have

$\displaystyle{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|z_{i}^{t+1}-z_{i}^{t}\right\|^{2}\right]$
$\displaystyle\leq$
$\displaystyle\beta^{2}{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|(x^{t+1}-x^{t})-p_{P}(w_{i}^{t}-x^{t})+(w_{i}^{t}-z^{t}_{i})\right\|^{2}+p_{P}\frac{1}{n}\sum_{i=1}^{n}\left\|w_{i}^{t}-x^{t}\right\|^{2}+\omega_{P}\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle\overset{\eqref{eq:young_2}}{\leq}$
$\displaystyle\beta^{2}{\rm\mathbb{E}}\left[\frac{3}{n}\sum_{i=1}^{n}\left\|w_{i}^{t}-z^{t}_{i}\right\|^{2}+4p_{P}\frac{1}{n}\sum_{i=1}^{n}\left\|w_{i}^{t}-x^{t}\right\|^{2}+(\omega_{P}+3)\left\|x^{t+1}-x^{t}\right\|^{2}\right],$

where in the last line we use the fact that $p_{P}\leq 1$. It remains to
substitute the above inequality in (30). ∎

######  Lemma E.7.

Let $\mathcal{C}_{i}^{t}\in\mathbb{U}(\omega_{P})$ for all $i\in[n]$ and
$\left\\{\mathcal{C}_{i}^{t}\right\\}_{i=1}^{n}\in\mathbb{P}(\theta)$. Then

$\displaystyle{\rm\mathbb{E}}\left[\left\|z^{t+1}_{i}-w^{t+1}_{i}\right\|^{2}\right]\leq\left(1-\frac{\beta}{2}\right){\rm\mathbb{E}}\left[\left\|z^{t}_{i}-w_{i}^{t}\right\|^{2}\right]+4\left(\frac{1}{\beta}+\omega_{P}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+4p_{P}\left(1+\frac{p_{P}}{\beta}\right){\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]$

for all $i\in[n],$ and

$\displaystyle{\rm\mathbb{E}}\left[\left\|z^{t+1}-w^{t+1}\right\|^{2}\right]\leq\left(1-\frac{\beta}{2}\right){\rm\mathbb{E}}\left[\left\|z^{t}-w^{t}\right\|^{2}\right]+4\left(\frac{1}{\beta}+\theta\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+4p_{P}\left(1+\frac{p_{P}}{\beta}\right){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right].$

###### Proof.

From the definition of $z^{t+1}_{i},$ we get

$\displaystyle{\rm\mathbb{E}}\left[\left\|z^{t+1}_{i}-w^{t+1}_{i}\right\|^{2}\right]={\rm\mathbb{E}}\left[\left\|\beta
w^{t+1}_{i}+(1-\beta)z^{t}_{i}-w^{t+1}_{i}\right\|^{2}\right]=(1-\beta)^{2}{\rm\mathbb{E}}\left[\left\|w^{t+1}_{i}-z^{t}_{i}\right\|^{2}\right].$

Then, Lemma E.5 gives

$\displaystyle{\rm\mathbb{E}}\left[\left\|z^{t+1}_{i}-w^{t+1}_{i}\right\|^{2}\right]$
$\displaystyle\leq$
$\displaystyle(1-\beta)^{2}{\rm\mathbb{E}}\left[\left\|(x^{t+1}-x^{t})-p_{P}(w_{i}^{t}-x^{t})+(w_{i}^{t}-z^{t}_{i})\right\|^{2}+p_{P}\left\|w_{i}^{t}-x^{t}\right\|^{2}+\omega_{P}\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle\overset{{\eqref{eq:young},\eqref{eq:ineq1},\eqref{eq:ineq2}}}{\leq}$
$\displaystyle\left(1-\frac{\beta}{2}\right){\rm\mathbb{E}}\left[\left\|w_{i}^{t}-z^{t}_{i}\right\|^{2}\right]+\frac{2}{\beta}{\rm\mathbb{E}}\left[\left\|(x^{t+1}-x^{t})-p_{P}(w_{i}^{t}-x^{t})\right\|^{2}\right]$
$\displaystyle+{\rm\mathbb{E}}\left[p_{P}\left\|w_{i}^{t}-x^{t}\right\|^{2}+\omega_{P}\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle\overset{\eqref{eq:young_2}}{\leq}$
$\displaystyle\left(1-\frac{\beta}{2}\right){\rm\mathbb{E}}\left[\left\|w_{i}^{t}-z^{t}_{i}\right\|^{2}\right]+\frac{4}{\beta}{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+\frac{4p_{P}^{2}}{\beta}{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]$
$\displaystyle+{\rm\mathbb{E}}\left[p_{P}\left\|w_{i}^{t}-x^{t}\right\|^{2}+\omega_{P}\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle\leq$
$\displaystyle\left(1-\frac{\beta}{2}\right){\rm\mathbb{E}}\left[\left\|w_{i}^{t}-z^{t}_{i}\right\|^{2}\right]+4\left(\frac{1}{\beta}+\omega_{P}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+4p_{P}\left(1+\frac{p_{P}}{\beta}\right){\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right].$

The second inequality is proved almost in the same way. First,

$\displaystyle{\rm\mathbb{E}}\left[\left\|z^{t+1}-w^{t+1}\right\|^{2}\right]=(1-\beta)^{2}{\rm\mathbb{E}}\left[\left\|w^{t+1}-z^{t}\right\|^{2}\right],$

and using Lemma E.5, we obtain

$\displaystyle{\rm\mathbb{E}}\left[\left\|z^{t+1}-w^{t+1}\right\|^{2}\right]$
$\displaystyle\leq$
$\displaystyle(1-\beta)^{2}{\rm\mathbb{E}}\left[\left\|(x^{t+1}-x^{t})-p_{P}(w^{t}-x^{t})+(w^{t}-z^{t})\right\|^{2}+p_{P}\left\|w^{t}-x^{t}\right\|^{2}+\theta\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle\overset{\eqref{eq:young}}{\leq}$
$\displaystyle\left(1-\frac{\beta}{2}\right){\rm\mathbb{E}}\left[\left\|w^{t}-z^{t}\right\|^{2}\right]+\frac{2}{\beta}{\rm\mathbb{E}}\left[\left\|(x^{t+1}-x^{t})-p_{P}(w^{t}-x^{t})\right\|^{2}\right]+{\rm\mathbb{E}}\left[p_{P}\left\|w^{t}-x^{t}\right\|^{2}+\theta\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle\overset{\eqref{eq:young_2}}{\leq}$
$\displaystyle\left(1-\frac{\beta}{2}\right){\rm\mathbb{E}}\left[\left\|w^{t}-z^{t}\right\|^{2}\right]+4\left(\frac{1}{\beta}+\theta\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+\frac{4p_{P}^{2}}{\beta}{\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]+{\rm\mathbb{E}}\left[p_{P}\left\|w^{t}-x^{t}\right\|^{2}\right]$
$\displaystyle\leq$
$\displaystyle\left(1-\frac{\beta}{2}\right){\rm\mathbb{E}}\left[\left\|w^{t}-z^{t}\right\|^{2}\right]+4\left(\frac{1}{\beta}+\theta\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+4p_{P}\left(1+\frac{p_{P}}{\beta}\right){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right].$

∎

See E.1

###### Proof.

Lemma H.1 gives

$\displaystyle{\rm\mathbb{E}}\left[\delta^{t+1}\right]$ $\displaystyle\leq$
$\displaystyle{\rm\mathbb{E}}\left[\delta^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]-\left(\frac{1}{2\gamma}-\frac{L}{2}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|g^{t}-\nabla
f(x^{t})\right\|^{2}\right]$ $\displaystyle\overset{\eqref{eq:young}}{\leq}$
$\displaystyle{\rm\mathbb{E}}\left[\delta^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]-\left(\frac{1}{2\gamma}-\frac{L}{2}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle+\gamma{\rm\mathbb{E}}\left[\left\|g^{t}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t})\right\|^{2}\right]+\gamma{\rm\mathbb{E}}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\left(\nabla
f_{i}(z_{i}^{t})-\nabla f_{i}(x^{t})\right)\right\|^{2}\right]$
$\displaystyle\overset{\eqref{as:AB_assumption}}{\leq}$
$\displaystyle{\rm\mathbb{E}}\left[\delta^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]-\left(\frac{1}{2\gamma}-\frac{L}{2}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle+\gamma{\rm\mathbb{E}}\left[\left\|g^{t}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t})\right\|^{2}\right]+\gamma
L_{A}^{2}\frac{1}{n}\sum_{i=1}^{n}{\rm\mathbb{E}}\left[\left\|z_{i}^{t}-x^{t}\right\|^{2}\right]+\gamma
L_{B}^{2}{\rm\mathbb{E}}\left[\left\|z^{t}-x^{t}\right\|^{2}\right]$
$\displaystyle\overset{\eqref{eq:young}}{\leq}$
$\displaystyle{\rm\mathbb{E}}\left[\delta^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]-\left(\frac{1}{2\gamma}-\frac{L}{2}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+\gamma{\rm\mathbb{E}}\left[\left\|g^{t}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t})\right\|^{2}\right]$ $\displaystyle+2\gamma
L_{A}^{2}\frac{1}{n}\sum_{i=1}^{n}\left({\rm\mathbb{E}}\left[\left\|z_{i}^{t}-w_{i}^{t}\right\|^{2}\right]+{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]\right)+2\gamma
L_{B}^{2}\left({\rm\mathbb{E}}\left[\left\|z^{t}-w^{t}\right\|^{2}\right]+{\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]\right).$

Let $\kappa,\eta,\nu,\rho,\mu\geq 0$ be some non-negative numbers that we
define later. Using Lemmas D.6, D.7, E.6 and E.7, we get

$\displaystyle{\rm\mathbb{E}}\left[\delta^{t+1}\right]+\kappa{\rm\mathbb{E}}\left[\left\|g^{t+1}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t+1})\right\|^{2}\right]+\eta{\rm\mathbb{E}}\left[\left\|z^{t+1}-w^{t+1}\right\|^{2}\right]$
$\displaystyle\quad+\nu{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|z^{t+1}_{i}-w^{t+1}_{i}\right\|^{2}\right]+\rho{\rm\mathbb{E}}\left[\left\|w^{t+1}-x^{t+1}\right\|^{2}\right]+\mu{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|w_{i}^{t+1}-x^{t+1}\right\|^{2}\right]$
$\displaystyle\leq{\rm\mathbb{E}}\left[\delta^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]-\left(\frac{1}{2\gamma}-\frac{L}{2}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+\gamma{\rm\mathbb{E}}\left[\left\|g^{t}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t})\right\|^{2}\right]$ $\displaystyle\quad+2\gamma
L_{A}^{2}\frac{1}{n}\sum_{i=1}^{n}\left({\rm\mathbb{E}}\left[\left\|z_{i}^{t}-w_{i}^{t}\right\|^{2}\right]+{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]\right)+2\gamma
L_{B}^{2}\left({\rm\mathbb{E}}\left[\left\|z^{t}-w^{t}\right\|^{2}\right]+{\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]\right)$
$\displaystyle\quad+\kappa\left(\frac{\omega_{D}L_{\max}^{2}}{n}\left(4p_{P}\beta^{2}{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|w^{t}_{i}-x^{t}\right\|^{2}\right]+3\beta^{2}{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|z^{t}_{i}-w_{i}^{t}\right\|^{2}\right]+3(\omega_{P}+1)\beta^{2}{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]\right)\right)$
$\displaystyle\quad+\kappa(1-p_{D}){\rm\mathbb{E}}\left[\left\|g^{t}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t})\right\|^{2}\right]$
$\displaystyle\quad+\eta\left(\left(1-\frac{\beta}{2}\right){\rm\mathbb{E}}\left[\left\|z^{t}-w^{t}\right\|^{2}\right]+4\left(\frac{1}{\beta}+\theta\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+4p_{P}\left(1+\frac{p_{P}}{\beta}\right){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]\right)$
$\displaystyle\quad+\nu\left(\left(1-\frac{\beta}{2}\right){\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|z^{t}_{i}-w_{i}^{t}\right\|^{2}\right]+4\left(\frac{1}{\beta}+\omega_{P}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+4p_{P}\left(1+\frac{p_{P}}{\beta}\right){\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]\right)$
$\displaystyle\quad+\rho(1-p_{P})\left({\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]+\theta{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]\right)$
$\displaystyle\quad+\mu(1-p_{P})\left({\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+\omega_{P}{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]\right).$

Taking $\kappa=\frac{\gamma}{p_{D}}$ and $\eta=\frac{4\gamma
L_{B}^{2}}{\beta}$, we get $\gamma+\kappa(1-p_{D})=\kappa$ and $2\gamma
L_{B}^{2}+\eta(1-\nicefrac{{\beta}}{{2}})=\eta$, which gives

$\displaystyle{\rm\mathbb{E}}\left[\delta^{t+1}\right]+\kappa{\rm\mathbb{E}}\left[\left\|g^{t+1}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t+1})\right\|^{2}\right]+\eta{\rm\mathbb{E}}\left[\left\|z^{t+1}-w^{t+1}\right\|^{2}\right]$
$\displaystyle\quad+\nu{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|z^{t+1}_{i}-w^{t+1}_{i}\right\|^{2}\right]+\rho{\rm\mathbb{E}}\left[\left\|w^{t+1}-x^{t+1}\right\|^{2}\right]+\mu{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|w_{i}^{t+1}-x^{t+1}\right\|^{2}\right]$
$\displaystyle\leq{\rm\mathbb{E}}\left[\delta^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]-\left(\frac{1}{2\gamma}-\frac{L}{2}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+\kappa{\rm\mathbb{E}}\left[\left\|g^{t}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t})\right\|^{2}\right]$
$\displaystyle\quad+\eta{\rm\mathbb{E}}\left[\left\|z^{t}-w^{t}\right\|^{2}\right]+2\gamma
L_{A}^{2}\frac{1}{n}\sum_{i=1}^{n}\left({\rm\mathbb{E}}\left[\left\|z_{i}^{t}-w_{i}^{t}\right\|^{2}\right]+{\rm\mathbb{E}}\left[\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]\right)+2\gamma
L_{B}^{2}{\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]$
$\displaystyle\quad+\frac{\gamma}{p_{D}}\left(\frac{\omega_{D}L_{\max}^{2}}{n}\left(4p_{P}\beta^{2}{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|w^{t}_{i}-x^{t}\right\|^{2}\right]+3\beta^{2}{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|z^{t}_{i}-w_{i}^{t}\right\|^{2}\right]+3(\omega_{P}+1)\beta^{2}{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]\right)\right)$
$\displaystyle\quad+\frac{4\gamma
L_{B}^{2}}{\beta}\left(4\left(\frac{1}{\beta}+\theta\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+4p_{P}\left(1+\frac{p_{P}}{\beta}\right){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]\right)$
$\displaystyle\quad+\nu\left(\left(1-\frac{\beta}{2}\right){\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|z^{t}_{i}-w_{i}^{t}\right\|^{2}\right]+4\left(\frac{1}{\beta}+\omega_{P}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+4p_{P}\left(1+\frac{p_{P}}{\beta}\right){\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]\right)$
$\displaystyle\quad+\rho\left((1-p_{P}){\rm\mathbb{E}}\left[\left\|w^{t}-x^{t}\right\|^{2}\right]+\theta{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]\right)$
$\displaystyle\quad+\mu\left((1-p_{P}){\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|w_{i}^{t}-x^{t}\right\|^{2}\right]+\omega_{P}{\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]\right).$

We rearrange the terms to obtain

$\displaystyle{\rm\mathbb{E}}\left[\delta^{t+1}\right]+\kappa{\rm\mathbb{E}}\left[\left\|g^{t+1}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t+1})\right\|^{2}\right]+\eta{\rm\mathbb{E}}\left[\left\|z^{t+1}-w^{t+1}\right\|^{2}\right]$
$\displaystyle\quad+\nu{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|z^{t+1}_{i}-w^{t+1}_{i}\right\|^{2}\right]+\rho{\rm\mathbb{E}}\left[\left\|w^{t+1}-x^{t+1}\right\|^{2}\right]+\mu{\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|w_{i}^{t+1}-x^{t+1}\right\|^{2}\right]$
$\displaystyle\leq{\rm\mathbb{E}}\left[\delta^{t}\right]-\frac{\gamma}{2}{\rm\mathbb{E}}\left[\left\|\nabla
f(x^{t})\right\|^{2}\right]-\left(\frac{1}{2\gamma}-\frac{L}{2}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]+\kappa{\rm\mathbb{E}}\left[\left\|g^{t}-\frac{1}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}^{t})\right\|^{2}\right]$
$\displaystyle\quad+\eta{\rm\mathbb{E}}\left[\left\|z^{t}-w^{t}\right\|^{2}\right]+\left(\nu\left(1-\frac{\beta}{2}\right)+2\gamma
L_{A}^{2}+\frac{3\gamma\omega_{D}\beta^{2}L_{\max}^{2}}{np_{D}}\right){\rm\mathbb{E}}\left[\frac{1}{n}\sum_{i=1}^{n}\left\|z^{t}_{i}-w_{i}^{t}\right\|^{2}\right]$
$\displaystyle\quad+\left(\frac{3\gamma\omega_{D}(\omega_{P}+1)\beta^{2}L_{\max}^{2}}{np_{D}}+\rho\theta+\frac{16\gamma
L_{B}^{2}}{\beta}\left(\frac{1}{\beta}+\theta\right)+4\nu\left(\frac{1}{\beta}+\omega_{P}\right)+\mu\omega_{P}\right){\rm\mathbb{E}}\left[\left\|x^{t+1}-x^{t}\right\|^{2}\right]$
$\displaystyle\quad+\left(\rho(1-p_{P})+2\gamma L_{B}^{2}+\frac{16\gamma