LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression

## Abstract

Abstract In D istributed optimization and L earning, and even more in the modern framework of federated learning,
communication, which is slow and costly, is critical. We introduce LoCoDL , a communication-efficient algorithm that leverages the two popular and effective techniques of Lo cal training, which reduces the communication frequency, and Co mpression, in which short bitstreams are sent instead of full-dimensional vectors of floats. LoCoDL works with a large class of unbiased compressors that includes widely-used sparsification and quantization methods. LoCoDL provably benefits from local training and compression and enjoys a doubly-accelerated communication complexity, with respect to the condition number of the functions and the model dimension, in the general heterogenous regime with strongly convex functions. This is confirmed in practice, with LoCoDL outperforming existing algorithms.

## 1 Introduction

Performing distributed computations is now pervasive in all areas of science. Notably, Federated Learning (FL) consists in training machine learning models in a distributed and collaborative way (Konečný et al., , ; McMahan et al., ; Bonawitz et al., ). The key idea in this rapidly growing field is to exploit the wealth of information stored on distant devices, such as mobile phones or hospital workstations. The many challenges to face in FL include data privacy and robustness to adversarial attacks, but communication-efficiency is likely to be the most critical (Kairouz et al., ; Li et al., ; Wang et al., ). Indeed, in contrast to the centralized setting in a datacenter, in FL the clients perform parallel computations
but also communicate back and forth with a distant orchestrating server. Communication typically takes place over the internet or
cell phone network, and can be slow, costly, and unreliable. It is the main bottleneck that currently prevents large-scale deployment of FL in mass-market applications.

Two strategies to reduce the communication burden have been popularized by the pressing needs of FL: 1) Local Training (LT), which consists in reducing the communication frequency. That is, instead of communicating the output of every computation step involving a (stochastic) gradient call, several such steps are performed between successive communication rounds. 2) Communication Compression (CC), in which compressed information is sent instead of full-dimensional vectors.
We review the literature of LT and CC
in Section 1.2.

We propose a new randomized algorithm named LoCoDL, which features LT and unbiased CC
for communication-efficient FL and distributed optimization. It is variance-reduced (Hanzely & Richtárik, ; Gorbunov et al., ; Gower et al., ), so that it converges to an exact solution. It provably benefits from the two mechanisms of LT and CC:
the communication complexity is doubly accelerated, with a better dependency on the condition number of the functions and on the dimension of the model.

### 1.1 Problem and Motivation

We study distributed optimization problems of the form

$$ $\min_{x\in\mathbb{R}^{d}}\ \frac{1}{n}\sum_{i=1}^{n}f_{i}(x)+g(x),$ (1) $$

where $d\geq 1$ is the model dimension and the functions $f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ and $g:\mathbb{R}^{d}\rightarrow\mathbb{R}$ are *smooth*, so their gradients will be called. We consider the server-client model in which $n\geq 1$ clients do computations in parallel and communicate back and forth with a server. The private function $f_{i}$ is owned by and stored on client $i\in[n]\coloneqq\{1,\ldots,n\}$.
Problem (1) models empirical risk minimization,
of utmost importance
in machine learning (Sra et al., ; Shalev-Shwartz & Ben-David, ). More generally, minimizing a sum of functions appears in virtually all areas of science and engineering. Our goal is to solve Problem (1) in a communication-efficient way, in the general heterogeneous setting in which the functions $f_{i}$, as well as $g$, can be *arbitrarily different*: we do not make any assumption on their similarity whatsoever.

We consider in this work the strongly convex setting — an analysis with nonconvex functions would certainly require very different proof techniques, which we currently do not know how to derive. That is, the following holds:

###### Assumption 1.1 (strongly convex functions) .

The functions $f_{i}$ and $g$ are all $L$-smooth and $\mu$-strongly convex, for some $0<\mu\leq L$.(^1^11A differentiable function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is said to be $L$-smooth if $\nabla f$ is $L$-Lipschitz continuous; that is, for every $x\in\mathbb{R}^{d}$ and $y\in\mathbb{R}^{d}$, $\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$ (the norm is the Euclidean norm throughout the paper). $f$ is said to be $\mu$-strongly convex if $f-\frac{\mu}{2}\|\cdot\|^{2}$ is convex.)
Then we denote by $x^{\star}$ the solution of the strongly convex problem (1), which exists and is unique. We define the condition number $\kappa\coloneqq\frac{L}{\mu}$.

Problem (1) can be viewed as the minimization of the average of the $n$ functions $(f_{i}+g)$, which can be performed using calls to $\nabla(f_{i}+g)=\nabla f_{i}+\nabla g$. We do not use this straightforward interpretation. Instead,
let us illustrate the interest of having the additional function $g$ in (1), using 4 different viewpoints. We stress that we can handle the case $g=0$, as discussed in Section 3.1.

- •
Viewpoint 1: *regularization*. The function $g$ can be a regularizer. For instance, if the functions $f_{i}$ are convex, adding $g=\frac{\mu}{2}\|\cdot\|^{2}$ for a small $\mu>0$ makes the problem $\mu$-strongly convex.
- •
Viewpoint 2: *shared dataset*. The function $g$ can model the cost of a common dataset, or a piece thereof, that is known to all clients.
- •
Viewpoint 3: *server-aided training*. The function $g$ can model the cost of a core dataset, known only to the server, which makes calls to $\nabla g$.
This setting has been investigated in several works,
with the idea that using a small auxiliary dataset representative of the global data distribution, the server can correct for the deviation induced by partial participation (Zhao et al., ; Yang et al., , ). We do not focus on this setting, because we deal with the general heterogeneous setting in which $g$ and the $f_{i}$ are not meant to be similar in any sense, and in our work $g$ is handled by the clients, not by the server.
- •
Viewpoint 4: *a new mathematical and algorithmic principle*. This is the
idea that led to
the construction of LoCoDL, and we detail it in Section 2.1.

In LoCoDL, the clients make all gradient calls; that is, Client $i$ makes calls to $\nabla f_{i}$ and $\nabla g$.

###### Assumption 1.1 (strongly convex functions) .

### 1.2 State of the Art

We review the latest developments on communication-efficient algorithms for distributed learning, making use of LT, CC, or both. Before that, we note that we should distinguish
uplink, or clients-to-server, from downlink, or server-to-clients, communication. Uplink is usually slower than downlink communication, since uploading different messages in parallel to the server is slower than broadcasting the same message to an arbitrary number of clients. This can be due to cache memory and aggregation speed constraints of the server, as well as
asymmetry of the service provider’s systems or protocols used on the internet or cell phone network. In this work, we focus on the uplink communication complexity, which is the bottleneck in practice. Indeed, the goal is to exploit parallelism to obtain better performance when $n$ increases. Precisely, with LoCoDL, the uplink communication complexity decreases from $\mathcal{O}\left(d\sqrt{\kappa}\log\epsilon^{-1}\right)$ when $n$ is small to $\mathcal{O}\big{(}\sqrt{d}\sqrt{\kappa}\log\epsilon^{-1}\big{)}$ when $n$ is large, where the condition number $\kappa$ is defined in Assumption 1.1, see Corollary 3.2. Many works have considered bidirectional compression, which consists in compressing the messages sent both ways (Gorbunov et al., ; Philippenko & Dieuleveut, ; Liu et al., ; Philippenko & Dieuleveut, ; Condat & Richtárik, ; Gruntkowska et al., ; Tyurin & Richtárik, ) but to the best of our knowledge, this has no impact on the downlink complexity, which cannot be reduced further than $\mathcal{O}\left(d\sqrt{\kappa}\log\epsilon^{-1}\right)$, just because there is no parallelism to exploit in this direction. Thus, we focus our analysis on theoretical and algorithmic techniques to reduce the uplink communication complexity, which we call communication complexity in short, and we ignore downlink communication.

Communication Compression (CC) consists in applying some lossy scheme that compresses vectors into messages of small bit size, which are communicated. For instance, the well-known rand-$k$ compressor selects $k$ coordinates of the vector uniformly at random, for some $k\in[d]\coloneqq\{1,\ldots,d\}$. $k$ can be as small as $1$, in which case the compression factor is $d$, which can be huge. Some compressors, such as rand-$k$, are unbiased, whereas others are biased; we refer to Beznosikov et al. (); Albasyoni et al. (); Horváth et al. (); Condat et al. () for several examples and a discussion of their properties.
The introduction of DIANA by Mishchenko et al. () was a major milestone, as this algorithm converges linearly with the large class of unbiased compressors defined in Section 1.3 and also considered in LoCoDL. The communication complexity $\mathcal{O}\big{(}d\kappa\log\epsilon^{-1}\big{)}$ of the basic Gradient Descent (GD) algorithm is reduced with DIANA to $\mathcal{O}\big{(}(\kappa+d)\log\epsilon^{-1}\big{)}$ when $n$ is large, see Table 2.
DIANA was later extended in several ways (Horváth et al., ; Gorbunov et al., ; Condat & Richtárik, ). An accelerated version of DIANA called ADIANA based on Nesterov Accelerated GD has been proposed (Li et al., ) and further analyzed in He et al. (); it has the state-of-the-art theoretical complexity.

Algorithms converging linearly with biased compressors have also been proposed, such as EF21 (Richtárik et al., ; Fatkhullin et al., ; Condat et al., ), but the acceleration potential is less understood than with unbiased compressors.
Algorithms with CC such as MARINA (Gorbunov et al., ) and DASHA (Tyurin & Richtárik, ) have been proposed for nonconvex optimization, but their analysis requires a different approach and there is a gap in the achievable performance: their complexity depends on $\frac{\omega\kappa}{\sqrt{n}}$ instead of $\frac{\omega\kappa}{n}$ with DIANA, where $\omega$ characterizes the compression error variance, see (2). Therefore, we focus on the convex setting and leave the nonconvex study for future work.

Local Training (LT) is a simple but remarkably efficient idea: the clients perform multiple Gradient Descent (GD) steps, instead of only one, between successive communication rounds. The intuition behind is that this leads to the communication of richer information, so that the number of communication rounds to reach a given accuracy is reduced. We refer to Mishchenko et al. () for a comprehensive review of LT-based algorithms, which include the popular FedAvg and Scaffold algorithms of McMahan et al. () and Karimireddy et al. (), respectively. Mishchenko et al. () made a breakthrough by proposing Scaffnew, the first LT-based variance-reduced algorithm that not only converges linearly to the exact solution in the strongly convex setting, but does so with accelerated communication complexity $\mathcal{O}(d\sqrt{\kappa}\log\epsilon^{-1})$.
In Scaffnew, communication can occur randomly after every iteration, but occurs only with a small probability $p$. Thus, there are in average $p^{-1}$ local steps between successive communication rounds. The optimal dependency on $\sqrt{\kappa}$ (Scaman et al., ) is obtained with $p=1/\sqrt{\kappa}$. LoCoDL has the same probabilistic LT mechanism as Scaffnew but does not revert to it
when compression is disabled, because of the additional function $g$ and tracking variables $y$ and $v$.
A different approach to LT was developed by Sadiev et al. () with the APDA-Inexact algorithm, and generalized to handle partial participation by Grudzień et al. () with the 5GCS algorithm: in both algorithms, the local GD steps form an inner loop in order to compute a proximity operator inexactly.

Combining LT and CC while retaining their benefits is very challenging.
In our strongly convex and heterogeneous setting, the methods Qsparse-local-SGD (Basu et al., ) and FedPAQ (Reisizadeh et al., ) do not converge linearly. FedCOMGATE features LT + CC and converges linearly (Haddadpour et al., ), but its complexity $\mathcal{O}(d\kappa\log\epsilon^{-1})$ does not show any acceleration.
We can mention that random reshuffling, a technique that can be seen as a type of LT, has been combined with CC in Sadiev et al. (); Malinovsky & Richtárik (). Recently, Condat et al. () managed to design a specific compression technique compatible with the LT mechanism of
Scaffnew, leading to CompressedScaffnew, the first LT + CC algorithm exhibiting a doubly-accelerated complexity, namely
$\mathcal{O}\big{(}\big{(}\sqrt{d}\sqrt{\kappa}+\frac{d\sqrt{\kappa}}{\sqrt{n}}
+d\big{)}\log\epsilon^{-1}\big{)}$, as reported in Table 2. However,
CompressedScaffnew uses a specific linear compression scheme that requires shared randomness; that is, all clients have to agree on a random permutation of the columns of the global compression pattern. No other compressor can be used, which notably rules out any type of quantization.

### 1.3 A General Class of Unbiased Random Compressors

For every $\omega\geq 0$, we define the $\mathbb{U}(\omega)$ as the set of random compression operators $\mathcal{C}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ that are unbiased, i.e. $\mathbb{E}\!\left[\mathcal{C}(x)\right]=x$, and satisfy, for every $x\in\mathbb{R}^{d}$,

$$ $\mathbb{E}\!\left[\left\|\mathcal{C}(x)-x\right\|^{2}\right]\leq\omega\left\|x \right\|^{2}.$ (2) $$

In addition, given a collection $(\mathcal{C}_{i})_{i=1}^{n}$ of compression operators in $\mathbb{U}(\omega)$ for some $\omega\geq 0$, in order to characterize their joint variance, we introduce
the constant $\omega_{\mathrm{av}}\geq 0$
such that, for every $x_{i}\in\mathbb{R}^{d}$, $i\in[n]$, we have

$$ $\mathbb{E}\!\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}\mathcal{C}_{i}(x_{i} )-x_{i}\big{)}\right\|^{2}\right]\leq\frac{\omega_{\mathrm{av}}}{n}\sum_{i=1}^ {n}\left\|x_{i}\right\|^{2}.$ (3) $$

The inequality (3) is not an additional assumption: it is satisfied with $\omega_{\mathrm{av}}=\omega$
by convexity of the squared norm.
But the convergence rate will depend on $\omega_{\mathrm{av}}$, which is typically much smaller than $\omega$. In particular, if the compressors $\mathcal{C}_{i}$ are mutually independent, the variance of their sum is the sum of their variances, and (3) is satisfied with $\omega_{\mathrm{av}}=\frac{\omega}{n}$.

### 1.4 Challenge and Contributions

This work addresses the following question:

*Can we combine LT and CC with any compressors in the generic class $\mathbb{U}(\omega)$ defined in the previous section, and fully benefit from both techniques by obtaining a doubly-accelerated communication complexity?*

We answer this question in the affirmative. LoCoDL has the same probabilistic LT mechanism as Scaffnew and features CC with compressors in $\mathbb{U}(\omega)$ with arbitrarily large $\omega\geq 0$, with proved linear convergence under Assumption 1.1, without further requirements. By choosing the communication probability and the variance $\omega$ appropriately, double acceleration is obtained. Thus, LoCoDL achieves the same theoretical complexity as CompressedScaffnew, but allows for a large class of compressors instead of the cumbersome permutation-based compressor of the latter. In particular, with compressors performing sparsification and quantization, LoCoDL outperforms existing algorithms, as we show by experiments in Section 4.
This is remarkable, since ADIANA, based on Nesterov acceleration and not LT, has an even better theoretical complexity when $n$ is larger than $d$, see Table 2, but this is not reflected in practice: ADIANA is clearly behind LoCoDL in our experiments. Thus, LoCoDL sets new standards in terms of communication efficiency.

**Table 1: Communication complexity in number of communication rounds to reach $\epsilon$-accuracy for linearly-converging algorithms allowing for CC with independent compressors in $\mathbb{U}(\omega)$ for any $\omega\geq 0$. Since the compressors are independent, $\omega_{\mathrm{av}}=\frac{\omega}{n}$. We provide the leading asymptotic factor and ignore log factors such as $\log\epsilon^{-1}$. The state of the art is highlighted in green.**
| Algorithm | Com. complexity in # rounds | case $\omega=\mathcal{O}(n)$ | case $\omega=\Theta(n)$ |
| --- | --- | --- | --- |
| DIANA | $(1+\frac{\omega}{n})\kappa+\omega$ | $\kappa+\omega$ | $\kappa+\omega$ |
| EF21 | $(1+\omega)\kappa$ | $(1+\omega)\kappa$ | $(1+\omega)\kappa$ |
| 5GCS-CC | $\left(1\!+\!\sqrt{\omega}\!+\!\frac{\omega}{\sqrt{n}}\right)\!\sqrt{\kappa}+\omega$ | $\left(1\!+\!\sqrt{\omega}\right)\!\sqrt{\kappa}+\omega$ | $\left(1\!+\!\sqrt{\omega}\right)\!\sqrt{\kappa}+\omega$ |
| ADIANA $\!{}^{1}$ | $\left(1\!+\!\frac{\omega^{3/4}}{n^{1/4}}\!+\!\frac{\omega}{\sqrt{n}}\right)\!<br>\sqrt{\kappa}+\omega$ | $\left(1\!+\!\frac{\omega^{3/4}}{n^{1/4}}\right)\!\sqrt{\kappa}+\omega$ | $\left(1\!+\!\sqrt{\omega}\right)\!\sqrt{\kappa}+\omega$ |
| ADIANA $\!{}^{2}$ | $\left(1+\frac{\omega}{\sqrt{n}}\right)\!\sqrt{\kappa}+\omega$ | $\left(1+\frac{\omega}{\sqrt{n}}\right)\!\sqrt{\kappa}+\omega$ | $\left(1\!+\!\sqrt{\omega}\right)\!\sqrt{\kappa}+\omega$ |
| lower bound${}^{2}$ | $\left(1+\frac{\omega}{\sqrt{n}}\right)\!\sqrt{\kappa}+\omega$ | $\left(1+\frac{\omega}{\sqrt{n}}\right)\!\sqrt{\kappa}+\omega$ | $\left(1\!+\!\sqrt{\omega}\right)\!\sqrt{\kappa}+\omega$ |
| LoCoDL | $\left(1\!+\!\sqrt{\omega}\!+\!\frac{\omega}{\sqrt{n}}\right)\!\sqrt{\kappa}+<br>\omega(1\!+\!\frac{\omega}{n})$ | $\left(1\!+\!\sqrt{\omega}\right)\!\sqrt{\kappa}+\omega$ | $\left(1\!+\!\sqrt{\omega}\right)\!\sqrt{\kappa}+\omega$ |

**Table 2: (Uplink) communication complexity in number of reals to reach $\epsilon$-accuracy for linearly-converging algorithms allowing for CC, with an optimal choice of unbiased compressors. We provide the leading asymptotic factor and ignore log factors such as $\log\epsilon^{-1}$. The state of the art is highlighted in green.**
| Algorithm | complexity in # reals | case $n\!=\!\mathcal{O}(d)$ |
| --- | --- | --- |
| DIANA | $(1+\frac{d}{n})\kappa+d$ | $\frac{d}{n}\kappa+d$ |
| EF21 | $d\kappa$ | $d\kappa$ |
| 5GCS-CC | $\left(\sqrt{d}\!+\!\frac{d}{\sqrt{n}}\right)\!\sqrt{\kappa}+d$ | $\frac{d}{\sqrt{n}}\sqrt{\kappa}+d$ |
| ADIANA | $\left(1+\frac{d}{\sqrt{n}}\right)\!\sqrt{\kappa}+d$ | $\frac{d}{\sqrt{n}}\sqrt{\kappa}+d$ |
| CompressedScaffnew | $\left(\sqrt{d}\!+\!\frac{d}{\sqrt{n}}\right)\!\sqrt{\kappa}+d$ | $\frac{d}{\sqrt{n}}\sqrt{\kappa}+d$ |
| FedCOMGATE | $d\kappa$ | $d\kappa$ |
| LoCoDL | $\left(\sqrt{d}\!+\!\frac{d}{\sqrt{n}}\right)\!\sqrt{\kappa}+d$ | $\frac{d}{\sqrt{n}}\sqrt{\kappa}+d$ |

## 2 Proposed Algorithm LoCoDL

### 2.1 Principle: Double Lifting of the Problem to a Consensus Problem

In LoCoDL, every client stores and updates *two* local model estimates. They will all converge to the same solution $x^{\star}$ of (1). This construction comes from two ideas.

#### Local steps with local models.

In algorithms making use of LT, such as FedAvg, Scaffold and Scaffnew, the clients store and update local model estimates $x_{i}$.
When communication occurs, an estimate of their average is formed by the server and broadcast to all clients. They all resume their computations with this new model estimate.

#### Compressing the difference between two estimates.

To implement CC, a powerful idea is to compress not the vectors themselves, but *difference vectors* that converge to zero. This way, the algorithm is variance-reduced; that is, the compression error vanishes at convergence. The technique of compressing the difference between a gradient vector and a control variate is at the core of algorithms such as DIANA and EF21. Here, we want to compress differences between model estimates, not gradient estimates. That is, we want Client $i$ to compress the difference between $x_{i}$ and another model estimate that converges to the solution $x^{\star}$ as well. We see the need of an additional model estimate that plays the role of an anchor for compression. This is the variable $y$ common to all clients in LoCoDL, which compress $x_{i}-y$ and send these compressed differences to the server.

#### Combining the two ideas.

Accordingly, an equivalent reformulation of (1) is
the consensus problem with $n+1$ variables

$$ $\min_{x_{1},\ldots,x_{n},y}\ \frac{1}{n}\sum_{i=1}^{n}f_{i}(x_{i})+g(y)\ \mbox {\ s.t.\ }\ x_{1}=\cdots=x_{n}=y.$ $$

The primal–dual optimality conditions are

$$ $\displaystyle x_{1}=\cdots=x_{n}=y,$ $\displaystyle 0=\nabla f_{i}(x_{i})-u_{i},\ \forall i\in[n],$ $\displaystyle 0=\nabla g(y)-v,$ $\displaystyle 0=u_{1}+\cdots+u_{n}+nv,$ (4) $$

for some dual variables $u_{1},\ldots,u_{n},v$ introduced in LoCoDL, that always satisfy the condition (4) of dual feasibility.

Figure: Algorithm 1 LoCoDL

### 2.2 Description of LoCoDL

LoCoDL is a randomized primal–dual algorithm, shown as Algorithm 1. At every iteration, for every $i\in[n]$ in parallel, Client $i$ first constructs a prediction $\hat{x}_{i}^{t}$ of its updated local model estimate, using a GD step with respect to $f_{i}$ corrected by the dual variable $u_{i}^{t}$. It also constructs a prediction $\hat{y}^{t}$ of the updated model estimate, using a GD step with respect to $g$ corrected by the dual variable $v^{t}$. Since $g$ is known by all clients, they all maintain and update identical copies of the variables $y$ and $v$. If there is no communication, which is the case with probability $1-p$, $x_{i}$ and $y$ are updated with these predicted estimates, and the dual variables $u_{i}$ and $v$ are unchanged. If communication occurs, which is the case with probability $p$, the clients compress the differences $\hat{x}_{i}^{t}-\hat{y}^{t}$ and send these compressed vectors to the server, which forms $\bar{d}^{t}$ equal to one half of their average. Then the variables $x_{i}$ are updated using a convex combination of the local predicted estimates $\hat{x}_{i}^{t}$ and the global but noisy estimate $\hat{y}^{t}+\bar{d}^{t}$. $y$ is updated similarly. Finally, the dual variables are updated using the compressed differences minus their weighted average, so that the dual feasibility (4) remains satisfied. The model estimates $x_{i}^{t}$, $\hat{x}_{i}^{t}$, $y^{t}$, $\hat{y}^{t}$ all converge to $x^{\star}$, so that their differences, as well as the compressed differences as a consequence of (2), converge to zero. This is the key property that makes the algorithm variance-reduced.
We consider the following assumption.

###### Assumption 2.1 (class of compressors) .

In LoCoDL the compressors $\mathcal{C}_{i}^{t}$ are all in $\mathbb{U}(\omega)$ for some $\omega\geq 0$. Moreover, for every $i\in[n]$, $i^{\prime}\in[n]$, $t\geq 0$, $t^{\prime}\geq 0$, $\mathcal{C}_{i}^{t}$ and $\mathcal{C}_{i^{\prime}}^{t^{\prime}}$ are independent if $t\neq t^{\prime}$ ($\mathcal{C}_{i}^{t}$ and $\mathcal{C}_{i^{\prime}}^{t}$ at the same iteration $t$ need not be independent). We define $\omega_{\mathrm{av}}\geq 0$ such that for every $t\geq 0$,
the collection $(\mathcal{C}_{i}^{t})_{i=1}^{n}$ satisfies (3).

###### Remark 2.2 (partial participation) .

LoCoDL allows for a form of partial participation if we set $\rho=1$.
Indeed, in that case, at steps 11 and 13 of the algorithm, all local variables $x_{i}$ as well as the common variable $y$ are overwritten by the same up-to-date model $\hat{y}^{t}+\bar{d}^{t}$. So, it does not matter that for a non-participating client $i$ with $d_{i}^{t}=0$, the $\hat{x}_{i}^{t^{\prime}}$ were not computed for the $t^{\prime}\leq t$ since its last participation, as they are not used in the process. However, a non-participating client should still update its local copy of $y$ at every iteration. This can be done when $\nabla g$ is much cheaper to compute that $\nabla f_{i}$, as is the case with $g=\frac{\mu}{2}\|\cdot\|^{2}$.
A non-participating client can be completely idle for a certain period of time, but when it resumes participating, it should receive
the last estimates of $x$, $y$ and $v$ from the server as it lost synchronization.

###### Assumption 2.1 (class of compressors) .

###### Remark 2.2 (partial participation) .

## 3 Convergence and Complexity of LoCoDL

###### Theorem 3.1 (linear convergence of LoCoDL ) .

Suppose that Assumptions 1.1 and 2.1 hold.
In LoCoDL,
suppose that $0<\gamma<\frac{2}{L}$, $2\rho-\rho^{2}(1+\omega_{\mathrm{av}})-\chi\geq 0$.
For every $t\geq 0$, define the Lyapunov function

$$ $\displaystyle\Psi^{t}$ $\displaystyle\coloneqq\frac{1}{\gamma}\left(\sum_{i=1}^{n}\left\|x_{i}^{t}-x^{ \star}\right\|^{2}+n\left\|y^{t}-x^{\star}\right\|^{2}\right)$ (5) $\displaystyle\quad+\frac{\gamma(1+2\omega)}{p^{2}\chi}\left(\sum_{i=1}^{n} \left\|u_{i}^{t}-u_{i}^{\star}\right\|^{2}+n\left\|v^{t}-v^{\star}\right\|^{2} \right),$ $$

where
$v^{\star}\coloneqq\nabla g(x^{\star})$ and $u_{i}^{\star}\coloneqq\nabla f_{i}(x^{\star})$. Then
LoCoDL converges linearly: for every $t\geq 0$,

$$ $\mathbb{E}\!\left[\Psi^{t}\right]\leq\tau^{t}\Psi^{0},$ (6) $$

where

$$ $\tau\coloneqq\max\left((1-\gamma\mu)^{2},(1-\gamma L)^{2},1-\frac{p^{2}\chi}{1 +2\omega}\right)<1.$ (7) $$

In addition, for every $i\in[n]$, $(x_{i}^{t})_{t\in\mathbb{N}}$ and $(y^{t})_{t\in\mathbb{N}}$ converge to $x^{\star}$, $(u_{i}^{t})_{t\in\mathbb{N}}$ converges to $u_{i}^{\star}$, and $(v^{t})_{t\in\mathbb{N}}$ converges to $v^{\star}$,
almost surely.

The proof is derived in Appendix A.

We place ourselves in the conditions of Theorem 3.1. We observe that in (7), the larger $\chi$, the better, so given $\rho$ we should set

$$ $\chi=2\rho-\rho^{2}(1+\omega_{\mathrm{av}}).$ (8) $$

Then, choosing $\rho$ to maximize $\chi$ yields

$$ $\chi=\rho=\frac{1}{1+\omega_{\mathrm{av}}}.$ (9) $$

We now study the complexity of LoCoDL with
$\chi$ and $\rho$ chosen as in (9) and $\gamma=\Theta(\frac{1}{L})$.

We can remark that
LoCoDL has the same rate $\tau^{\sharp}\coloneqq\max(1-\gamma\mu,\gamma L-1)^{2}$ as mere distributed gradient descent, as long as $p^{-1}$, $\omega$ and $\omega_{\mathrm{av}}$ are small enough to have
$1-\frac{p^{2}\chi}{1+2\omega}\leq\tau^{\sharp}$.
This is remarkable: communicating with a low frequency and compressed vectors does not harm convergence at all, until some threshold.

The iteration complexity of LoCoDL to reach $\epsilon$-accuracy, i.e. $\mathbb{E}\!\left[\Psi^{t}\right]\leq\epsilon\Psi^{0}$, is

$$ $\mathcal{O}\left(\left(\kappa+\frac{(1+\omega_{\mathrm{av}})(1+\omega)}{p^{2}} \right)\log\epsilon^{-1}\right).$ (10) $$

By choosing

$$ $p=\min\left(\sqrt{\frac{(1+\omega_{\mathrm{av}})(1+\omega)}{\kappa}},1\right),$ (11) $$

the iteration complexity becomes

$$ $\mathcal{O}\Big{(}\big{(}\kappa+\omega(1+\omega_{\mathrm{av}})\big{)}\log \epsilon^{-1}\Big{)}$ $$

and the communication complexity in number of communication rounds is $p$ times the iteration complexity, that is

$$ $\mathcal{O}\left(\left(\sqrt{\kappa(1+\omega_{\mathrm{av}})(1+\omega)}+\omega( 1+\omega_{\mathrm{av}})\right)\log\epsilon^{-1}\right).$ $$

If the compressors are mutually independent, $\omega_{\mathrm{av}}=\frac{\omega}{n}$ and the communication complexity can be equivalently written as

$$ $\mathcal{O}\left(\left(\left(1+\sqrt{\omega}+\frac{\omega}{\sqrt{n}}\right) \sqrt{\kappa}+\omega\left(1+\frac{\omega}{n}\right)\right)\log\epsilon^{-1} \right),$ $$

as shown in Table 1.

Let us consider the example of independent rand-$k$ compressors, for some $k\in[d]$. We have $\omega=\frac{d}{k}-1$. Therefore, the communication complexity in numbers of reals is $k$ times the complexity in number of rounds; that is,

$$ $\mathcal{O}\left(\left(\left(\sqrt{kd}+\frac{d}{\sqrt{n}}\right)\sqrt{\kappa}+ d\left(1+\frac{d}{kn}\right)\right)\log\epsilon^{-1}\right).$ $$

We can now choose $k$ to minimize this complexity: with $k=\lceil\frac{d}{n}\rceil$,
it becomes

$$ $\mathcal{O}\left(\left(\left(\sqrt{d}+\frac{d}{\sqrt{n}}\right)\sqrt{\kappa}+d \right)\log\epsilon^{-1}\right),$ $$

as shown in Table 2. Let us state this result:

###### Corollary 3.2 .

In the conditions of Theorem 3.1, suppose in addition that the compressors $\mathcal{C}_{i}^{t}$ are independent rand-$k$ compressors with $k=\lceil\frac{d}{n}\rceil$. Suppose that $\gamma=\Theta(\frac{1}{L})$, $\chi=\rho=\frac{n}{n-1+d/k}$, and

$$ $p=\min\left(\sqrt{\frac{dk(n-1)+d^{2}}{nk^{2}\kappa}},1\right).$ (12) $$

Then the uplink communication complexity in number of reals of LoCoDL is

$$ $\mathcal{O}\left(\left(\sqrt{d}\sqrt{\kappa}+\frac{d\sqrt{\kappa}}{\sqrt{n}}+d \right)\log\epsilon^{-1}\right).$ (13) $$

This is the same complexity as CompressedScaffnew (Condat et al., ). However, it is obtained with simple independent compressors, which is much more practical than the permutation-based compressors with shared randomness of CompressedScaffnew. Moreover, this complexity can be obtained with other types of compressors, and further reduced, when reasoning in number of bits and not only reals, by making use of quantization (Albasyoni et al., ), as we illustrate by experiments in the next section.

We can distinguish 2 regimes:

- 1.
In the “large $d$ small $n$” regime, i.e. $n=\mathcal{O}(d)$, the communication complexity of LoCoDL in (13) becomes
$\mathcal{O}\left(\left(\frac{d\sqrt{\kappa}}{\sqrt{n}}+d\right)\log\epsilon^{-
1}\right).$
This is the state of the art, as reported in Table 2.
- 2.
In the “large $n$ small $d$” regime, i.e. $n=\Omega(d)$, the communication complexity of LoCoDL in (13) becomes
$\mathcal{O}\left(\left(\sqrt{d}\sqrt{\kappa}+d\right)\log\epsilon^{-1}\right).$
If $n$ is even larger with $n=\Omega(d^{2})$, ADIANA achieves the even better complexity
$\mathcal{O}\left(\left(\sqrt{\kappa}+d\right)\log\epsilon^{-1}\right).$

Yet, in the experiments we ran with different datasets and values of $d$, $n$, $\kappa$, LoCoDL outperforms the other algorithms, including ADIANA, in all cases.

Figure: Figure 1: Comparison of several algorithms with several compressors on logistic regression with the ‘diabetes’ dataset from the LibSVM, which has $d=8$ and 768 data points. We chose different values of $n$ to illustrate the three regimes $n<d$, $n>d$, $n>d^{2}$, as discussed at the end of Section 3.
Refer to caption: x1.png

Figure: Figure 2: Comparison of several algorithms with several compressors on logistic regression with the ‘a5a’ dataset from the LibSVM, which has $d=122$ and 6,414 data points. We chose different values of $n$ to illustrate the two regimes $n<d$ and $n>d$, as discussed at the end of Section 3.
Refer to caption: x4.png

###### Theorem 3.1 (linear convergence of LoCoDL ) .

###### Corollary 3.2 .

### 3.1 The Case g = 0 𝑔 0 g=0 italic_g = 0

We have assumed the presence of a function $g$ in Problem (1), whose gradient is called by all clients. In this section, we show that we can handle the case where such a function is not available. So, let us assume that we want to minimize $\frac{1}{n}\sum_{i=1}^{n}f_{i}$, with the functions $f_{i}$ satisfying Assumption 1.1. We now define the functions $\tilde{f}_{i}\coloneqq f_{i}-\frac{\mu}{4}\left\|\cdot\right\|^{2}$ and $\tilde{g}\coloneqq\frac{\mu}{4}\left\|\cdot\right\|^{2}$. They are all $\tilde{L}$-smooth and $\tilde{\mu}$-strongly convex, with $\tilde{L}\coloneqq L-\frac{\mu}{2}$ and $\tilde{\mu}\coloneqq\frac{\mu}{2}$. Moreover, it is equivalent to minimize $\frac{1}{n}\sum_{i=1}^{n}f_{i}$ or $\frac{1}{n}\sum_{i=1}^{n}\tilde{f}_{i}+\tilde{g}$. We can then apply LoCoDL to the latter problem. At Step 5, we simply have $y^{t}-\gamma\nabla\tilde{g}(y^{t})=(1-\frac{\gamma\mu}{2})y^{t}$.
The rate in (7) applies with $L$ and $\mu$ replaced by $\tilde{L}$ and $\tilde{\mu}$, respectively. Since $\kappa\leq\tilde{\kappa}\coloneqq\frac{\tilde{L}}{\tilde{\mu}}\leq 2\kappa$, the asymptotic complexities derived above also apply to this setting. Thus, the presence of $g$ in Problem (1) is not restrictive at all, as the only property of $g$ that matters is that it has the same amount of strong convexity as the $f_{i}$s.

## 4 Experiments

We evaluate the performance of our proposed method LoCoDL and compare it with several other methods that also allow for CC and
converge linearly to $x^{\star}$.
We also include GradSkip (Maranjyan et al., ) and Scaffold (McMahan et al., ) in our comparisons for benchmarking purposes.
We focus on a regularized logistic regression problem, which has the form (1) with

$$ $\displaystyle f_{i}(x)=\frac{1}{m}\sum\limits_{s=1}^{m}\log\!\Big{(}1\!+\!\exp \left(-b_{i,s}a_{i,s}^{\top}x\right)\!\Big{)}\!+\frac{\mu}{2}\|x\|^{2}$ (14) $$

and $g=\frac{\mu}{2}\|x\|^{2}$,
where $n$ is the number of clients, $m$ is the number of data points per client,
$a_{i,s}\in\mathbb{R}^{d}$ and $b_{i,s}\in\{-1,+1\}$ are the data samples,
and $\mu$ is the regularization parameter, set so that $\kappa=10^{4}$. For all algorithms other than LoCoDL, for which there is no function $g$, the functions $f_{i}$ in (14) have a twice higher $\mu$, so that the problem remains the same.

We considered several datasets and show here the results
with the ‘diabetes’ and ‘a5a’ datasets from the LibSVM library (Chang & Lin, ).
Additional experiments are shown in the Appendix.
We prepared each dataset by first shuffling it, then distributing it equally among the $n$ clients (since $m$ in (14) is an integer, the remaining datapoints were discarded).

We used four different compression operators in the class $\mathbb{U}(\omega)$, for some $\omega\geq 0$:

- 1.
rand-$k$ for some $k\in[d]$, which communicates $32k+k\lceil\log_{2}(d)\rceil$ bits.
Indeed, the $k$ randomly chosen values are sent in the standard 32-bits IEEE floating-point format, and their locations are encoded with $k\lceil\log_{2}(d)\rceil$ additional bits. We have $\omega=\frac{d}{k}-1$.
- 2.
Natural Compression (Horváth et al., ), a form of quantization in which floats are encoded into 9 bits instead of 32 bits. We have $\omega=\frac{1}{8}$.
- 3.
A combination of rand-$k$ and Natural Compression, in which the $k$ chosen values are encoded into 9 bits, which yields a total of
$9k+k\lceil\log_{2}(d)\rceil$ bits. We have $\omega=\frac{9d}{8k}-1$.
- 4.
The $l_{1}$-selection compressor, defined as
$C(x)=\text{sign}(x_{j})\|x\|_{1}e_{j}$,
where $j$ is chosen randomly in $[d]$, with the probability of choosing $j^{\prime}\in[d]$ equal to
$|x_{j^{\prime}}|/\|x\|_{1}$, and $e_{j}$ is the $j$-th standard unit basis vector in $\mathbb{R}^{d}$.
$\text{sign}(x_{j})\|x\|_{1}$ is sent as a 32-bits float and the location of $j$ is indicated with $\lceil\log_{2}(d)\rceil$, so that this compressor communicates $32+\lceil\log_{2}(d)\rceil$ bits. Like with rand-$1$, we have $\omega=d-1$.

The compressors at different clients are independent, so that $\omega_{\mathrm{av}}=\frac{\omega}{n}$ in (3).

The results are shown in Figures 1 and 2. We can see that LoCoDL, when combined with rand-$k$ and Natural Compression, converges faster than all other algorithms, with respect to the total number of communicated bits per client.
We chose two different numbers $n$ of clients, one with $n<d$ and another one with $n>2d$, since the compressor of CompressedScaffnew is different in the two cases $n<2d$ and $n>2d$ (Condat et al., ). LoCoDL outperforms CompressedScaffnew in both cases. As expected, all methods exhibit faster convergence with larger $n$. Remarkably, ADIANA, which has the best theoretical complexity for large $n$, improves upon DIANA but is not competitive with the LT-based methods CompressedScaffnew, 5GCS-CC, and LoCoDL. This illustrates the power of doubly-accelerated methods based on a successful combination of LT and CC. In this class, our new proposed LoCoDL algorithm shines.
For all algorithms, we used the theoretical parameter values given in their available convergence results (Corollary 3.2 for LoCoDL). We tried to tune the parameter values, such as $k$ in rand-$k$ and the (average) number of local steps per round, but this only gave minor improvements. For instance, ADIANA in Figure 2 was a bit faster with the best value of $k=20$ than with $k=30$. Increasing the learning rate $\gamma$ led to inconsistent results, with sometimes divergence.

The results of additional experiments on the ‘w1a’ and ‘australian’ datasets from the LibSVM library (Chang & Lin, ), in the same setting, are shown in Figures 3 and 4. Consistent with our previous findings,
LoCoDL outperforms the other algorithms in terms of communication efficiency.

Figure: Figure 3: Comparison of several algorithms with various compressors on logistic regression with the ‘australian’ dataset from the LibSVM, which has $d=14$ and 690 data points. We chose different values of $n$ to illustrate the three regimes: $n<d$, $n>d$, $n>d^{2}$, as discussed at the end of Section 3.
Refer to caption: x6.png

Figure: Figure 4: Comparison of several algorithms with various compressors on logistic regression with the ‘w1a’ dataset from the LibSVM, which has $d=300$ and 2,477 data points. We chose different values of $n$ to illustrate the two regimes, $n<d$ and $n>d$, as discussed at the end of Section 3.
Refer to caption: x9.png

## 5 Conclusion

We have proposed LoCoDL, which combines a probabilistic Local Training mechanism similar to the one of Scaffnew and Communication Compression with a large class of unbiased compressors. This successful combination makes LoCoDL highly communication-efficient, with a doubly accelerated complexity with respect to the model dimension $d$ and the condition number of the functions. In practice, LoCoDL outperforms other algorithms, including ADIANA, which has an even better complexity in theory obtained from Nesterov acceleration and not Local Training. This again shows the relevance of the popular mechanism of Local Training, which has been widely adopted in Federated Learning. A venue for future work is to implement bidirectional compression (Liu et al., ; Philippenko & Dieuleveut, ). We will also investigate extensions of our method with calls to stochastic gradient estimates, with or without variance reduction, as well as partial participation. These two features have been proposed for Scaffnew in Malinovsky et al. () and Condat et al. (),
but they are challenging to combine with generic compression.

## Acknowledgement

This work was supported by the SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence (SDAIA-KAUST AI).

## Appendix A Proof of Theorem 3.1

We define the Euclidean space $\mathcal{X}\coloneqq\mathbb{R}^{d}$ and the product space $\boldsymbol{\mathcal{X}}\coloneqq\mathcal{X}^{n+1}$ endowed with the weighted inner product

$$ $\langle\mathbf{x},\mathbf{x}^{\prime}\rangle_{\boldsymbol{\mathcal{X}}} \coloneqq\sum_{i=1}^{n}\langle x_{i},x_{i}^{\prime}\rangle+n\langle y,y^{ \prime}\rangle,\quad\forall\mathbf{x}=(x_{1},\ldots,x_{n},y),\mathbf{x}^{ \prime}=(x_{1}^{\prime},\ldots,x_{n}^{\prime},y^{\prime}).$ (15) $$

We define the copy operator $\mathbf{1}:x\in\mathcal{X}\mapsto(x,\ldots,x,x)\in\boldsymbol{\mathcal{X}}$ and
the linear operator

$$ $S:\mathbf{x}\in\boldsymbol{\mathcal{X}}\mapsto\mathbf{1}\bar{x},\ \ \mbox{with }\ \bar{x}=\frac{1}{2n}\!\left(\sum_{i=1}^{n}x_{i}+ny\right).$ (16) $$

$S$ is the orthogonal projector in $\boldsymbol{\mathcal{X}}$ onto the consensus line $\{\mathbf{x}\in\boldsymbol{\mathcal{X}}\ :\ x_{1}=\cdots=x_{n}=y\}$.
We also define the linear operator

$$ $W\coloneqq\mathrm{Id}-S:\mathbf{x}=(x_{1},\ldots,x_{n},y)\in\boldsymbol{ \mathcal{X}}\mapsto(x_{1}-\bar{x},\ldots,x_{n}-\bar{x},y-\bar{x}),\ \mbox{with }\ \bar{x}=\frac{1}{2n}\!\left(\sum_{i=1}^{n}x_{i}+ny\right)\!,$ (17) $$

where $\mathrm{Id}$ denotes the identity.
$W$ is the orthogonal projector in $\boldsymbol{\mathcal{X}}$ onto the hyperplane $\{\mathbf{x}\in\boldsymbol{\mathcal{X}}\ :\ x_{1}+\cdots+x_{n}+ny=0\}$, which is orthogonal to the consensus line. As such, it is self-adjoint, positive semidefinite, its eigenvalues are $(1,\ldots,1,0)$, its kernel is the consensus line, and its spectral norm is 1. Also, $W^{2}=W$. Note that we can write $W$ in terms of the differences $d_{i}=x_{i}-y$ and $\bar{d}=\frac{1}{2n}\sum_{i=1}^{n}d_{i}$:

$$ $W:\mathbf{x}=(x_{1},\ldots,x_{n},y)\mapsto\big{(}d_{1}-\bar{d},\ldots,d_{n}- \bar{d},-\bar{d}\big{)}.$ (18) $$

Since for every $\mathbf{x}=(x_{1},\ldots,x_{n},y)$, $W\mathbf{x}=\mathbf{0}\coloneqq(0,\ldots,0,0)$ if and only if $x_{1}=\cdots=x_{n}=y$,
we can reformulate the problem (1) as

$$ $\min_{\mathbf{x}=(x_{1},\ldots,x_{n},y)\in\boldsymbol{\mathcal{X}}}\ \mathbf{f }(\mathbf{x})\quad\mbox{s.t.}\quad W\mathbf{x}=\mathbf{0},$ (19) $$

where $\mathbf{f}(\mathbf{x})\coloneqq\sum_{i=1}^{n}f_{i}(x_{i})+ng(y)$. Note that in $\boldsymbol{\mathcal{X}}$, $\mathbf{f}$ is $L$-smooth and $\mu$-strongly convex, and
$\nabla\mathbf{f}(\mathbf{x})=\big{(}\nabla f_{1}(x_{1}),\ldots\nabla f_{n}(x_{
n}),\nabla g(y)\big{)}$.

Let $t\geq 0$.
We also introduce vector notations for the variables of the algorithm:
$\mathbf{x}^{t}\coloneqq(x_{1}^{t},\ldots,x_{n}^{t},y^{t})$, $\mathbf{\hat{x}}^{t}\coloneqq(\hat{x}_{1}^{t},\ldots,\hat{x}_{n}^{t},\hat{y}^{
t})$, $\mathbf{u}^{t}\coloneqq(u_{1}^{t},\ldots,u_{n}^{t},v^{t})$, $\mathbf{u}^{\star}\coloneqq(u_{1}^{\star},\ldots,u_{n}^{\star},v^{\star})$, $\mathbf{w}^{t}\coloneqq\mathbf{x}^{t}-\gamma\nabla\mathbf{f}(\mathbf{x}^{t})$, $\mathbf{w}^{\star}\coloneqq\mathbf{x}^{\star}-\gamma\nabla\mathbf{f}(\mathbf{x
}^{\star})$, where $\mathbf{x}^{\star}\coloneqq\mathbf{1}x^{\star}$ is the unique solution to (19).
We also define $\bar{x}^{t}\coloneqq\frac{1}{2n}\!\left(\sum_{i=1}^{n}\hat{x}_{i}^{t}+n\hat{y}
^{t}\right)$ and $\lambda\coloneqq\frac{p\chi}{\gamma(1+2\omega)}$.

Then we can write the iteration of LoCoDL as

$$ $\left\lfloor\begin{array}[]{l}\mathbf{\hat{x}}^{t}\coloneqq\mathbf{x}^{t}- \gamma\nabla\mathbf{f}(\mathbf{x}^{t})+\gamma\mathbf{u}^{t}=\mathbf{w}^{t}+ \gamma\mathbf{u}^{t}\\ \mbox{flip a coin $\theta^{t}\in\{0,1\}$ with $\mathrm{Prob}(\theta^{t}=1)=p$} \\ \mbox{{if} }\theta^{t}=1\\ \ \ \ \mathbf{d}^{t}\coloneqq\big{(}\mathcal{C}_{1}^{t}(\hat{x}_{1}^{t}-\hat{y }^{t}),\ldots,\mathcal{C}_{n}^{t}(\hat{x}_{n}^{t}-\hat{y}^{t}),0\big{)}\\ \ \ \ \bar{d}^{t}\coloneqq\frac{1}{2n}\sum_{j=1}^{n}d_{j}^{t}\\ \ \ \ \mathbf{x}^{t+1}\coloneqq(1-\rho)\mathbf{\hat{x}}^{t}+\rho\mathbf{1}( \hat{y}^{t}+\bar{d}^{t})\\ \ \ \ \mathbf{u}^{t+1}\coloneqq\mathbf{u}^{t}+\lambda\big{(}\mathbf{1}\bar{d}^ {t}-\mathbf{d}^{t}\big{)}=\mathbf{u}^{t}-\lambda W\mathbf{d}^{t}\\ \mbox{{else}}\\ \ \ \ \mathbf{x}^{t+1}\coloneqq\mathbf{\hat{x}}^{t}\\ \ \ \ \mathbf{u}^{t+1}\coloneqq\mathbf{u}^{t}\\ \mbox{{end if}}\end{array}\right.$ (20) $$

We denote by $\mathcal{F}^{t}$ the $\sigma$-algebra generated by the collection of $\mathcal{X}$-valued random variables $\mathbf{x}^{0},\mathbf{u}^{0},\ldots,\mathbf{x}^{t},\mathbf{u}^{t}$.

Since we suppose that $S\mathbf{u}^{0}=\mathbf{0}$ and we have $SW\mathbf{d}^{t^{\prime}}=\mathbf{0}$ in the update of $\mathbf{u}$, we have $S\mathbf{u}^{t^{\prime}}=\mathbf{0}$ for every $t^{\prime}\geq 0$.

If $\theta^{t}=1$, we have

$$ $\displaystyle\left\|\mathbf{u}^{t+1}-\mathbf{u}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}$ $\displaystyle=\left\|\mathbf{u}^{t}-\mathbf{u}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}+\lambda^{2}\left\|W\mathbf{d}^{t}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}-2\lambda\langle\mathbf{u}^{t}-\mathbf{u}^{\star},W \mathbf{d}^{t}\rangle_{\boldsymbol{\mathcal{X}}}$ $\displaystyle=\left\|\mathbf{u}^{t}-\mathbf{u}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}+\lambda^{2}\left\|\mathbf{d}^{t}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}-\lambda^{2}\left\|S\mathbf{d}^{t}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}-2\lambda\langle\mathbf{u}^{t}-\mathbf{u}^{\star}, \mathbf{d}^{t}\rangle_{\boldsymbol{\mathcal{X}}},$ $$

because $S\mathbf{u}^{t}=S\mathbf{u}^{\star}=\mathbf{0}$, so that $\langle\mathbf{u}^{t}-\mathbf{u}^{\star},S\mathbf{d}^{t}\rangle_{\boldsymbol{
\mathcal{X}}}=0$.

The variance inequality (2) satisfied by the compressors $\mathcal{C}_{i}^{t}$ is equivalent to
$\mathbb{E}\!\left[\left\|\mathcal{C}_{i}^{t}(x)\right\|^{2}\right]\leq(1+
\omega)\left\|x\right\|^{2}$,
so that

$$ $\mathbb{E}\!\left[\left\|\mathbf{d}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}} \;|\;\mathcal{F}^{t},\theta^{t}=1\right]\leq(1+\omega)\left\|\mathbf{\hat{x}}^ {t}-\mathbf{1}\hat{y}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}}.$ $$

Also,

$$ $\mathbb{E}\!\left[\mathbf{d}^{t}\;|\;\mathcal{F}^{t},\theta^{t}=1\right]= \mathbf{\hat{x}}^{t}-\mathbf{1}\hat{y}^{t}.$ $$

Thus,

$$ $\displaystyle\mathbb{E}\!\left[\left\|\mathbf{u}^{t+1}-\mathbf{u}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}\;|\;\mathcal{F}^{t}\right]$ $\displaystyle=(1-p)\left\|\mathbf{u}^{t}-\mathbf{u}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}+p\mathbb{E}\!\left[\left\|\mathbf{u}^{t+1}-\mathbf{u }^{\star}\right\|^{2}_{\boldsymbol{\mathcal{X}}}\;|\;\mathcal{F}^{t},\theta^{t }=1\right]$ $\displaystyle\leq\left\|\mathbf{u}^{t}-\mathbf{u}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}+p\lambda^{2}(1+\omega)\left\|\mathbf{\hat{x}}^{t}- \mathbf{1}\hat{y}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}}-p\lambda^{2} \mathbb{E}\!\left[\left\|S\mathbf{d}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}} }\;|\;\mathcal{F}^{t},\theta^{t}=1\right]$ $\displaystyle\quad-2p\lambda\langle\mathbf{u}^{t}-\mathbf{u}^{\star},\mathbf{ \hat{x}}^{t}-\mathbf{1}\hat{y}^{t}\rangle_{\boldsymbol{\mathcal{X}}}$ $\displaystyle=\left\|\mathbf{u}^{t}-\mathbf{u}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}+p\lambda^{2}(1+\omega)\left\|\mathbf{\hat{x}}^{t}- \mathbf{1}\hat{y}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}}-p\lambda^{2} \mathbb{E}\!\left[\left\|S\mathbf{d}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}} }\;|\;\mathcal{F}^{t},\theta^{t}=1\right]$ $\displaystyle\quad-2p\lambda\langle\mathbf{u}^{t}-\mathbf{u}^{\star},\mathbf{ \hat{x}}^{t}\rangle_{\boldsymbol{\mathcal{X}}}.$ $$

Moreover,
$\mathbb{E}\!\left[\left\|S\mathbf{d}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}
}\;|\;\mathcal{F}^{t},\theta^{t}=1\right]\geq\left\|\mathbb{E}\!\left[S\mathbf
{d}^{t}\;|\;\mathcal{F}^{t},\theta^{t}=1\right]\right\|^{2}_{\boldsymbol{
\mathcal{X}}}=\left\|S\mathbf{\hat{x}}^{t}-\mathbf{1}\hat{y}^{t}\right\|^{2}_{
\boldsymbol{\mathcal{X}}}$ and
$\left\|\mathbf{\hat{x}}^{t}-\mathbf{1}\hat{y}^{t}\right\|^{2}_{\boldsymbol{
\mathcal{X}}}=\left\|S\mathbf{\hat{x}}^{t}-\mathbf{1}\hat{y}^{t}\right\|^{2}_{
\boldsymbol{\mathcal{X}}}+\left\|W\mathbf{\hat{x}}^{t}\right\|^{2}_{
\boldsymbol{\mathcal{X}}}$, so that

$$ $\displaystyle\mathbb{E}\!\left[\left\|\mathbf{u}^{t+1}-\mathbf{u}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}\;|\;\mathcal{F}^{t}\right]$ $\displaystyle\leq\left\|\mathbf{u}^{t}-\mathbf{u}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}+p\lambda^{2}(1+\omega)\left\|\mathbf{\hat{x}}^{t}- \mathbf{1}\hat{y}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}}-p\lambda^{2}\left \|S\mathbf{\hat{x}}^{t}-\mathbf{1}\hat{y}^{t}\right\|^{2}$ $\displaystyle\quad-2p\lambda\langle\mathbf{u}^{t}-\mathbf{u}^{\star},\mathbf{ \hat{x}}^{t}\rangle_{\boldsymbol{\mathcal{X}}}$ $\displaystyle=\left\|\mathbf{u}^{t}-\mathbf{u}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}+p\lambda^{2}\omega\left\|\mathbf{\hat{x}}^{t}- \mathbf{1}\hat{y}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}}+p\lambda^{2}\left \|W\mathbf{\hat{x}}^{t}\right\|^{2}-2p\lambda\langle\mathbf{u}^{t}-\mathbf{u}^ {\star},\mathbf{\hat{x}}^{t}\rangle_{\boldsymbol{\mathcal{X}}}.$ $$

From the Peter–Paul inequality $\|a+b\|^{2}\leq 2\|a\|^{2}+2\|b\|^{2}$ for any $a$ and $b$, we have

$$ $\displaystyle\left\|\mathbf{\hat{x}}^{t}-\mathbf{1}\hat{y}^{t}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}$ $\displaystyle=\sum_{i=1}^{n}\left\|\hat{x}_{i}^{t}-\hat{y}^{t}\right\|^{2}= \sum_{i=1}^{n}\left\|(\hat{x}_{i}^{t}-\bar{x}^{t})-(\hat{y}^{t}-\bar{x}^{t}) \right\|^{2}$ $\displaystyle\leq\sum_{i=1}^{n}\left(2\left\|\hat{x}_{i}^{t}-\bar{x}^{t}) \right\|^{2}+2\left\|\hat{y}^{t}-\bar{x}^{t}\right\|^{2}\right)$ $\displaystyle=2\left(\sum_{i=1}^{n}\left\|\hat{x}_{i}^{t}-\bar{x}^{t})\right\| ^{2}+n\left\|\hat{y}^{t}-\bar{x}^{t}\right\|^{2}\right)$ $\displaystyle=2\left\|\mathbf{\hat{x}}^{t}-\mathbf{1}\bar{x}^{t}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}=2\left\|W\mathbf{\hat{x}}^{t}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}.$ (21) $$

Hence,

$$ $\displaystyle\mathbb{E}\!\left[\left\|\mathbf{u}^{t+1}-\mathbf{u}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}\;|\;\mathcal{F}^{t}\right]$ $\displaystyle\leq\left\|\mathbf{u}^{t}-\mathbf{u}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}+p\lambda^{2}(1+2\omega)\left\|W\mathbf{\hat{x}}^{t} \right\|^{2}_{\boldsymbol{\mathcal{X}}}-2p\lambda\langle\mathbf{u}^{t}-\mathbf {u}^{\star},\mathbf{\hat{x}}^{t}\rangle_{\boldsymbol{\mathcal{X}}}.$ $$

On the other hand,

$$ $\displaystyle\mathbb{E}\!\left[\left\|\mathbf{x}^{t+1}-\mathbf{x}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}\;|\;\mathcal{F}^{t},\theta=1\right]$ $\displaystyle=(1-\rho)^{2}\left\|\mathbf{\hat{x}}^{t}-\mathbf{x}^{\star}\right \|^{2}_{\boldsymbol{\mathcal{X}}}+\rho^{2}\mathbb{E}\!\left[\left\|\mathbf{1}( \hat{y}^{t}+\bar{d}^{t})-\mathbf{x}^{\star}\right\|^{2}_{\boldsymbol{\mathcal{ X}}}\;|\;\mathcal{F}^{t},\theta=1\right]$ $\displaystyle\quad+2\rho(1-\rho)\left\langle\mathbf{\hat{x}}^{t}-\mathbf{x}^{ \star},\mathbf{1}\big{(}\hat{y}^{t}+\mathbb{E}\!\left[\bar{d}^{t}\;|\;\mathcal {F}^{t},\theta=1\right]\big{)}-\mathbf{x}^{\star}\right\rangle_{\boldsymbol{ \mathcal{X}}}.$ $$

We have $\mathbb{E}\!\left[\bar{d}^{t}\;|\;\mathcal{F}^{t},\theta=1\right]=\frac{1}{2n}
\sum_{i=1}^{n}\hat{x}_{i}^{t}-\frac{1}{2}\hat{y}^{t}=\bar{x}^{t}-\hat{y}^{t}$, so that

$$ $\mathbf{1}\big{(}\hat{y}^{t}+\mathbb{E}\!\left[\bar{d}^{t}\;|\;\mathcal{F}^{t} ,\theta=1\right]\!\big{)}=\mathbf{1}\bar{x}^{t}=S\mathbf{\hat{x}}^{t}.$ $$

In addition,

$$ $\left\langle\mathbf{\hat{x}}^{t}-\mathbf{x}^{\star},S\mathbf{\hat{x}}^{t}- \mathbf{x}^{\star}\right\rangle_{\boldsymbol{\mathcal{X}}}=\left\langle\mathbf {\hat{x}}^{t}-\mathbf{x}^{\star},S(\mathbf{\hat{x}}^{t}-\mathbf{x}^{\star}) \right\rangle_{\boldsymbol{\mathcal{X}}}=\left\|S(\mathbf{\hat{x}}^{t}-\mathbf {x}^{\star})\right\|^{2}_{\boldsymbol{\mathcal{X}}}.$ $$

Moreover,

$$ $\displaystyle\mathbb{E}\!\left[\left\|\mathbf{1}(\hat{y}^{t}+\bar{d}^{t})- \mathbf{x}^{\star}\right\|^{2}_{\boldsymbol{\mathcal{X}}}\;|\;\mathcal{F}^{t}, \theta=1\right]$ $\displaystyle=\left\|\mathbf{1}\!\left(\hat{y}^{t}+\mathbb{E}\!\left[\bar{d}^{ t}\;|\;\mathcal{F}^{t},\theta=1\right]\right)-\mathbf{x}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}$ $\displaystyle\quad+\mathbb{E}\!\left[\left\|\mathbf{1}\!\left(\bar{d}^{t}- \mathbb{E}\!\left[\bar{d}^{t}\;|\;\mathcal{F}^{t},\theta=1\right]\right)\right \|^{2}_{\boldsymbol{\mathcal{X}}}\;|\;\mathcal{F}^{t},\theta=1\right]$ $\displaystyle=\left\|S\mathbf{\hat{x}}^{t}-\mathbf{x}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}+2n\mathbb{E}\!\left[\left\|\bar{d}^{t}-\mathbb{E}\! \left[\bar{d}^{t}\;|\;\mathcal{F}^{t},\theta=1\right]\right\|^{2}\;|\;\mathcal {F}^{t},\theta=1\right]$ $$

and, using (3),

$$ $\displaystyle\mathbb{E}\!\left[\left\|\bar{d}^{t}-\mathbb{E}\!\left[\bar{d}^{t }\;|\;\mathcal{F}^{t},\theta=1\right]\right\|^{2}\;|\;\mathcal{F}^{t},\theta=1\right]$ $\displaystyle\leq\frac{\omega_{\mathrm{av}}}{4n}\sum_{i=1}^{n}\left\|\hat{x}_{ i}^{t}-\hat{y}^{t}\right\|^{2}$ $\displaystyle\leq\frac{\omega_{\mathrm{av}}}{2n}\left\|W\mathbf{\hat{x}}^{t} \right\|^{2}_{\boldsymbol{\mathcal{X}}},$ $$

where the second inequality follows from (21). Hence,

$$ $\displaystyle\mathbb{E}\!\left[\left\|\mathbf{x}^{t+1}-\mathbf{x}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}\;|\;\mathcal{F}^{t},\theta=1\right]$ $\displaystyle\leq(1-\rho)^{2}\left\|\mathbf{\hat{x}}^{t}-\mathbf{x}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}+\rho^{2}\left\|S\mathbf{\hat{x}}^{t}- \mathbf{x}^{\star}\right\|^{2}_{\boldsymbol{\mathcal{X}}}+\rho^{2}\omega_{ \mathrm{av}}\left\|W\mathbf{\hat{x}}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}}$ $\displaystyle\quad+2\rho(1-\rho)\left\|S(\mathbf{\hat{x}}^{t}-\mathbf{x}^{ \star})\right\|^{2}_{\boldsymbol{\mathcal{X}}}$ $\displaystyle=(1-\rho)^{2}\left\|\mathbf{\hat{x}}^{t}-\mathbf{x}^{\star}\right \|^{2}_{\boldsymbol{\mathcal{X}}}+\rho^{2}\omega_{\mathrm{av}}\left\|W\mathbf{ \hat{x}}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}}$ $\displaystyle\quad+(2\rho-\rho^{2})\left\|S(\mathbf{\hat{x}}^{t}-\mathbf{x}^{ \star})\right\|^{2}_{\boldsymbol{\mathcal{X}}}$ $\displaystyle=(1-\rho)^{2}\left\|\mathbf{\hat{x}}^{t}-\mathbf{x}^{\star}\right \|^{2}_{\boldsymbol{\mathcal{X}}}+\rho^{2}\omega_{\mathrm{av}}\left\|W\mathbf{ \hat{x}}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}}$ $\displaystyle\quad+(2\rho-\rho^{2})\left(\left\|\mathbf{\hat{x}}^{t}-\mathbf{x }^{\star}\right\|^{2}_{\boldsymbol{\mathcal{X}}}-\left\|W\mathbf{\hat{x}}^{t} \right\|^{2}_{\boldsymbol{\mathcal{X}}}\right)$ $\displaystyle=\left\|\mathbf{\hat{x}}^{t}-\mathbf{x}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}-\left(2\rho-\rho^{2}-\rho^{2}\omega_{\mathrm{av}} \right)\left\|W\mathbf{\hat{x}}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}}$ $$

and

$$ $\displaystyle\mathbb{E}\!\left[\left\|\mathbf{x}^{t+1}-\mathbf{x}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}\;|\;\mathcal{F}^{t}\right]$ $\displaystyle=(1-p)\left\|\mathbf{\hat{x}}^{t}-\mathbf{x}^{\star}\right\|^{2}_ {\boldsymbol{\mathcal{X}}}+p\mathbb{E}\!\left[\left\|\mathbf{x}^{t+1}-\mathbf{ x}^{\star}\right\|^{2}_{\boldsymbol{\mathcal{X}}}\;|\;\mathcal{F}^{t},\theta^{ t}=1\right]$ $\displaystyle\leq\left\|\mathbf{\hat{x}}^{t}-\mathbf{x}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}-p\big{(}2\rho-\rho^{2}(1+\omega_{\mathrm{av}})\big{) }\left\|W\mathbf{\hat{x}}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}}.$ $$

Furthermore,

$$ $\displaystyle\left\|\mathbf{\hat{x}}^{t}-\mathbf{x}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}$ $\displaystyle=\left\|\mathbf{w}^{t}-\mathbf{w}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}+\gamma^{2}\left\|\mathbf{u}^{t}-\mathbf{u}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}+2\gamma\langle\mathbf{w}^{t}-\mathbf{w }^{\star},\mathbf{u}^{t}-\mathbf{u}^{\star}\rangle_{\boldsymbol{\mathcal{X}}}$ $\displaystyle=\left\|\mathbf{w}^{t}-\mathbf{w}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}-\gamma^{2}\left\|\mathbf{u}^{t}-\mathbf{u}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}+2\gamma\langle\mathbf{\hat{x}}^{t}- \mathbf{x}^{\star},\mathbf{u}^{t}-\mathbf{u}^{\star}\rangle_{\boldsymbol{ \mathcal{X}}}$ $\displaystyle=\left\|\mathbf{w}^{t}-\mathbf{w}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}-\gamma^{2}\left\|\mathbf{u}^{t}-\mathbf{u}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}+2\gamma\langle\mathbf{\hat{x}}^{t}, \mathbf{u}^{t}-\mathbf{u}^{\star}\rangle_{\boldsymbol{\mathcal{X}}},$ $$

which yields

$$ $\displaystyle\mathbb{E}\!\left[\left\|\mathbf{x}^{t+1}-\mathbf{x}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}\;|\;\mathcal{F}^{t}\right]$ $\displaystyle\leq\left\|\mathbf{w}^{t}-\mathbf{w}^{\star}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}-\gamma^{2}\left\|\mathbf{u}^{t}-\mathbf{u}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}+2\gamma\langle\mathbf{\hat{x}}^{t}, \mathbf{u}^{t}-\mathbf{u}^{\star}\rangle_{\boldsymbol{\mathcal{X}}}$ $\displaystyle\quad-p\big{(}2\rho-\rho^{2}(1+\omega_{\mathrm{av}})\big{)}\left \|W\mathbf{\hat{x}}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}}.$ $$

Hence, with $\lambda=\frac{p\chi}{\gamma(1+2\omega)}$,

$$ $\displaystyle\frac{1}{\gamma}$ $\displaystyle\mathbb{E}\!\left[\left\|\mathbf{x}^{t+1}-\mathbf{x}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}\;|\;\mathcal{F}^{t}\right]+\frac{ \gamma(1+2\omega)}{p^{2}\chi}\mathbb{E}\!\left[\left\|\mathbf{u}^{t+1}-\mathbf {u}^{\star}\right\|^{2}_{\boldsymbol{\mathcal{X}}}\;|\;\mathcal{F}^{t}\right]$ $\displaystyle\leq\frac{1}{\gamma}\left\|\mathbf{w}^{t}-\mathbf{w}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}-\gamma\left\|\mathbf{u}^{t}-\mathbf{u} ^{\star}\right\|^{2}_{\boldsymbol{\mathcal{X}}}+2\langle\mathbf{\hat{x}}^{t}, \mathbf{u}^{t}-\mathbf{u}^{\star}\rangle_{\boldsymbol{\mathcal{X}}}-\frac{p}{ \gamma}\big{(}2\rho-\rho^{2}(1+\omega_{\mathrm{av}})\big{)}\left\|W\mathbf{ \hat{x}}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}}$ $\displaystyle+\frac{\gamma(1+2\omega)}{p^{2}\chi}\left\|\mathbf{u}^{t}-\mathbf {u}^{\star}\right\|^{2}_{\boldsymbol{\mathcal{X}}}+\frac{p\chi}{\gamma}\left\| W\mathbf{\hat{x}}^{t}\right\|^{2}_{\boldsymbol{\mathcal{X}}}-2\langle\mathbf{u }^{t}-\mathbf{u}^{\star},\mathbf{\hat{x}}^{t}\rangle_{\boldsymbol{\mathcal{X}}}$ $\displaystyle=\frac{1}{\gamma}\left\|\mathbf{w}^{t}-\mathbf{w}^{\star}\right\| ^{2}_{\boldsymbol{\mathcal{X}}}+\frac{\gamma(1+2\omega)}{p^{2}\chi}\left(1- \frac{p^{2}\chi}{1+2\omega}\right)\left\|\mathbf{u}^{t}-\mathbf{u}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}-\frac{p}{\gamma}\big{(}2\rho-\rho^{2}( 1+\omega_{\mathrm{av}})-\chi\big{)}\left\|W\mathbf{\hat{x}}^{t}\right\|^{2}_{ \boldsymbol{\mathcal{X}}}.$ $$

Therefore, assuming that $2\rho-\rho^{2}(1+\omega_{\mathrm{av}})-\chi\geq 0$,

$$ $\displaystyle\mathbb{E}\!\left[\Psi^{t+1}\;|\;\mathcal{F}^{t}\right]$ $\displaystyle\leq\frac{1}{\gamma}\left\|\mathbf{w}^{t}-\mathbf{w}^{\star} \right\|^{2}_{\boldsymbol{\mathcal{X}}}+\left(1-\frac{p^{2}\chi}{1+2\omega} \right)\frac{\gamma(1+2\omega)}{p^{2}\chi}\left\|\mathbf{u}^{t}-\mathbf{u}^{ \star}\right\|^{2}_{\boldsymbol{\mathcal{X}}}.$ $$

According to Condat & Richtárik (, Lemma 1),

$$ $\displaystyle\left\|\mathbf{w}^{t}-\mathbf{w}^{\star}\right\|^{2}_{\boldsymbol {\mathcal{X}}}$ $\displaystyle=\left\|(\mathrm{Id}-\gamma\nabla\mathbf{f})\mathbf{x}^{t}-( \mathrm{Id}-\gamma\nabla\mathbf{f})\mathbf{x}^{\star}\right\|^{2}_{\boldsymbol {\mathcal{X}}}$ $\displaystyle\leq\max(1-\gamma\mu,\gamma L-1)^{2}\left\|\mathbf{x}^{t}-\mathbf {x}^{\star}\right\|^{2}_{\boldsymbol{\mathcal{X}}}.$ $$

Hence,

$$ $\displaystyle\mathbb{E}\!\left[\Psi^{t+1}\;|\;\mathcal{F}^{t}\right]$ $\displaystyle\leq\max\left((1-\gamma\mu)^{2},(1-\gamma L)^{2},1-\frac{p^{2} \chi}{1+2\omega}\right)\Psi^{t}.$ (22) $$

Using the tower rule, we can unroll the recursion in (22) to obtain the unconditional expectation of $\Psi^{t+1}$.

Using classical results on supermartingale convergence (Bertsekas, , Proposition A.4.5), it follows from (22) that $\Psi^{t}\rightarrow 0$ almost surely. Almost sure convergence of $\mathbf{x}^{t}$ and $\mathbf{u}^{t}$ follows.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Can the authors please explain in more details and provide some intuitions on why does LoCoDL "require" a regularisation $g$ to work? I put "require" in quotes because, as explained in section 3.1, one can reduce the case with $g=0$ to some strongly convex $\tilde g$. But such reduction highlights the fact that the algorithm, on its own, does need a strongly convex $g$, which seems quite mysterious to me. I think it would significantly improve my understanding of the technique if the authors can point out why/if LoCoDL, as is and without the reduction, would fail when $g=0$.

2. Based on the choice of the Lyapunov function, it seems to me that the convergence of LoCoDL is characterised in terms of $\frac{1}{n}\sum\lVert x_i^t-x^\star\rVert^2$. While ProxSkip's analysis also uses this convergence criteria, there the situation is slightly different since if the composite part can attain infinity then there is just no way to prove convergence in terms of the optimality gap when the prox step is skipped. But here the situation seems different, I wonder if it's possible to prove the convergence of LoCoDL in terms of the optimality gap, say, $f(\bar x) + g(\bar x)-f(x^\star)-g(x^\star)$ where $\bar x$ is the average of the primal variable (or perhaps the average optimality gap of each clients)? If not, what's the difficulty here? I think some of the algorithms that the authors compare LoCoDL against do use optimality gap as the convergence criteria, so there might be some mismatch.

3. The paper focuses on the strongly convex case. While the authors mentioned that non convex case might require significantly different techniques, I wonder what about the general convex case? It seems that LoCoDL would fail in that case (see also my question regarding $g$), but can the authors provide some insights in what would fail in the general convex case?

4. I wonder if LoCoDL can handle stochastic gradients? It seems to me that the idea of compressing the difference between two estimates works well with full gradient computations, but might not work so well when there is noise (e.g. EF21 fail to converge beyond the variance of the noise and ProxSkip's original analysis cannot achieve linear speedup with the noise). Is it also the case here? Have the authors tried the stochastic case?
soundness: 3
strengths: The proposed method, LoCoDL manages to combine both local updates and communication compression, and show that in the strongly convex regime, the method enjoys the communication-saving benefits of both techniques. LoCoDL combines ideas from ProxSkip and EF21 (and the likes) with primal-dual updates to achieve this impressive result.
summary: This paper proposed the LoCoDL algorithm, which applies both communication compression and local updates in distributed training, and analyzed its complexity, showing that with suitable compression scheme the total communication complexity matches that of the accelerated compressed methods
weaknesses: see questions.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: 1. It is a little bit strange that ADIANA performs worse than other baseline algorithms. Are the hyperparameters not sufficiently tuned?
2. Since with communication compression only we can achieve the optimal theoretical convergence rate, how to illustrate the theoretical benefit of using "local steps with local models"?
soundness: 3
strengths: 1. Though the area of local training and communication compression has been explored by previous works, it may still be challenging to develop algorithms combining these ideas to achieve the theoretically optimal convergence rate. LoCoDL is shown to be optimal in cases where $n$ is smaller than the problem dimension $d$, which is often the case in real settings. Considering the assumptions used are standard, this result is believed to be strong enough.
2. It is impressive that LoCoDL performs much better than ADIANA, which has been the SOTA algorithm in distributed deterministic convex optimization with communication compression, and enjoys an optimal convergence rate matching the convergence lower bound.
summary: This paper studies how to develop communication-efficient algorithms for centralized optimization problem by combining the idea of local training and communication compression, and proposes an algorithm called LoCoDL. LoCoDL is both validated theoretically through a nearly optimal convergence rate and via empirically by comparing with previous SOTA algorithms.
weaknesses: 1. The theoretical results are not perfect. Since LoCoDL has a sub-optimal rate in the case where $n$ is larger than $d$, its unclear whether it is the algorithm or the analysis is sub-optimal. As ADIANA has already achieves the optimal rate, it should be better if the author discuss the challenges to achieve a same rate.
2. It's not clear how LoCoDL is derived by combining the two ideas "local steps with local models" and "compressing the difference of two estimates". It is recommended that the authors discuss the motivation behind each algorithm line.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: * Please consider a more comprehensive experimental evaluation.
  * Since nonconvex landscape is not covered by theory, experiments on deep neural networks can be done to show its performance in handling nonconvex problems.
  * The theory claims heterogeneous setting but experiments are done on a homogeneous distribution of dataset. Experiments with data heterogeneity can be conducted, as in previous related works like [1,2].
* I suggest the authors provide more discussions on the primal-dual design. How does this help with your proof? What challenges will you encounter without this primal-dual approach?

[1] Huang, X., Chen, Y., Yin, W., and Yuan, K. (2022). Lower bounds and nearly optimal algorithms in distributed learning with communication compression. Advances in Neural Information Processing Systems, 35, 18955-18969.

[2] Chen, S., Li, Z., and Chi, Y. (2024). Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compression. In International Conference on Artificial Intelligence and Statistics (pp. 2701-2709). PMLR.
soundness: 3
strengths: * The design of LoCoDL shows novelty such as the introduction of primal-dual updates.
* The convergence of LoCoDL with unbiased compression under strongly convex landscape is supported by rigorous theoretical analysis, provably showing a reduced communication overhead.
* LoCoDL achieves empirical advantages in experiments on regularized logistic regression.
* The presentation of the paper is well-organized and clear to follow.
summary: This paper proposes LoCoDL, an algorithm for distributed optimization that incorporates both local training and communication compression. The design of LoCoDL uses a primal-dual approach and randomization, provably achieving double acceleration in strongly convex landscape with unbiased compression. Empirical advantages of LoCoDL are demonstrated from experiments.
weaknesses: * The theory of this paper has some limitation. For example, it assumes the usage of unbiased compression, which does not encompass some popular biased schemes such as Top-k compression. The proof also exploits strong convexity and nonconvex landscape poses a challenge.
* Empirical evaluations are conducted only on regularized logistic regression with homogeneous distribution of local dataset. The experiments are not able to demonstrate the performance in heterogeneous settings (which is claimed by the theory) and nonconvex problems; also see Questions.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. What is the intuition that make the proposed algorithm work compared to existing works that combines LT and CC?
2. Is the rate obtained optimal?
soundness: 3
strengths: Proves the proposed algorithm the accelerate communication complexity due to both components used.
summary: The paper combines local update with compression to improve communication efficiency in distributed estimation.
weaknesses: Only demonstrate strongly convex case. Assuming g is smooth (exclude non-smooth penalty such as lasso, for example)

Meta-review: This paper studies communication efficient training methods in federated learning. Local training, and compression of gradients are two different methods for reducing communication in federated learning. This paper provides an algorithm that combines both and achieves convergence for strongly convex objective functions. As such, it is interesting to know that this works. 

As far as weaknesses are concerned, this is not a very rigorous paper as far as compression parts are concerned (terms such as "communication complexity in reals" shows the lack of understanding of issues in communication, which is a pretty big engineering field by itself). However, from optimization perspective (federated learning) this paper has some values, and the reviewers do recognize that. From the tables of the papers, there is no theoretical advantage this paper provides over existing ones, but in simulation it is better.

Overall, I recommend acceptance.

Decision: Accept (Spotlight)