# Gradient Projection onto Historical Descent Directions for Communication-Efficient Federated Learning

Arnaud Descours, Léonard Deroose, Jan Ramon

<figure><img src="image_1.png" /></figure>

## To cite this version:

Arnaud Descours, Léonard Deroose, Jan Ramon. Gradient Projection onto Historical Descent Directions for Communication-Efficient Federated Learning. 2025. hal-05347099

HAL Id: hal-05347099

https://hal.science/hal-05347099v1

Preprint submitted on 4 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Gradient Projection onto Historical Descent Directions for Communication-Efficient Federated Learning

Arnaud Descours¹*†, Léonard Deroose²† and Jan Ramon²

¹*ISFA, UCBL, Lyon, France.

²INRIA, Lille, France.

*Corresponding author(s). E-mail(s): arnaud descours@univ-lyon1.fr;

Contributing authors: leonard.deroose@inria.fr; jan.ramon@inria.fr;

†These authors contributed equally to this work.

## Abstract

Federated Learning (FL) enables decentralized model training across multiple clients while optionally preserving data privacy. However, communication efficiency remains a critical bottleneck, particularly for large-scale models. In this work, we introduce two complementary algorithms: ProjFL, designed for unbiased compressors, and ProjFL+EF, tailored for biased compressors through an Error Feedback mechanism. Both methods rely on projecting local gradients onto a shared client-server subspace spanned by historical descent directions, enabling efficient information exchange with minimal communication overhead. We establish convergence guarantees for both algorithms under strongly convex, convex, and non-convex settings. Empirical evaluations on standard FL classification benchmarks with deep neural networks show that ProjFL and ProjFL+EF achieve accuracy comparable to existing baselines while substantially reducing communication costs.

**Keywords:** Optimization, Neural Networks, Federated Learning, Communication cost

## 1 Introduction

In recent years, Federated Learning (FL) [1] has emerged as a promising paradigm for training Machine Learning (ML) models across distributed data owners, without
requiring direct access to the underlying data. This framework is particularly attractive in a landscape where organizations are increasingly concerned about data privacy, regulatory constraints (GDPR, AI Act), and the rising costs of centralized data infrastructure. FL is a setting where multiple entities, called clients, collaborate in solving a ML problem, under the coordination of a central server. Mathematically, various ML tasks can be formulated as the optimization problem:

$$ \text{Minimize } f(w) = \frac{1}{M} \sum_{i=1}^{M} f_i(w) \text{ over } \mathbb{R}^d, \qquad (1) $$

where the vector $w$ represents the parameters of a statistical model and $f_i: \mathbb{R}^d \to \mathbb{R}$ is the local objective function associated with client $i \in [M]$. Typically, in ML, the functions $f_i$ take the form

$$ f_i(w) = \mathbb{E}_{(x,y)\sim\pi_i} [L(y, h_w(x))], $$

where, in a supervised learning task, $h_w: \mathcal{X} \to \mathbb{R}$ is the prediction function (e.g., a neural network), and $L: \mathbb{R} \times \mathbb{R} \to \mathbb{R}_+$ a loss function. The data distribution $\pi_i$ is the underlying data distribution of client $i$, and is typically unknown. In practice, $\pi_i$ may be defined as a discrete distribution over the local dataset of client $i$, leading to empirical risk minimization. This motivates the use of either deterministic gradient descent (GD) or, more commonly, to stochastic gradient descent (SGD), which is preferred for its computational efficiency.

The communication cost is a major bottleneck in FL, especially for optimization of models with many parameters. Two main strategies have been explored to mitigate this issue:

1. **Local training**, which consists of reducing the communication frequency. Clients perform multiple local updates before sending their weights to the server for averaging.

2. **Gradient compression**, where compressed information is sent instead of full-dimensional gradients.

The first strategy involves performing multiple local updates (e.g., several SGD steps) before each communication round with the server, thereby reducing communication frequency. This classical approach, known as **FedAvg** [2], has inspired several extensions, such as **SCAFFOLD** [3] and **FedPAGE** [4]. The second strategy can be broadly divided into two subcategories. The first focuses on designing and analyzing various types of compression operators (see, e.g., [5, Table 1] and the analysis of [6]). The second aims to develop algorithms that remain effective under general compression schemes-or at least under broad classes of them. For example, several methods incorporate mechanisms to track and correct the compression error [7, 8]. In this work, we focus on the second strategy and propose a new algorithmic approach for gradient compression in FL.
## 1.1 Main Contributions

Our contributions are summarized as follows:

* **Algorithm Design:** We propose ProjFL (Algorithm 1), a novel federated learning method designed for unbiased compressors, and ProjFL+EF (Algorithm 2), an extension of the approach tailored for biased compressors that incorporates Error Feedback. Both methods project gradients onto a shared client-server subspace.

* **Theoretical Guarantees:** Under standard assumptions, we establish: (i) a linear convergence rate to a noise ball when optimizing strongly-convex objectives (item 1 of Theorems 1 and 2); (ii) a $O(1/T)$ convergence rate towards a noise ball around the minimum of convex objectives (item 2 of Theorems 1 and 2); and (iii) a $O(1/T)$ convergence rate towards near-stationary points for smooth non-convex objectives (item 3 of Theorems 1 and 2).

* **Empirical Validation:** We evaluate our methods on large-scale neural network models (LeNet-5, ResNet-20). Our methods exhibit accuracy and stability comparable to those of state-of-the-art baselines: it converges quickly without requiring careful hyperparameter tuning. Furthermore, it achieves up to a 8× reduction in communication cost compared to existing methods.

### *Outline.*

The rest of the paper is organized as follows. Section 2 introduces the formal problem setting and reviews related work. Section 3 presents our proposed methods, which are theoretically analyzed in Section 4. Numerical experiments are reported in Section 5. We conclude with future research directions in Section 6.

# 2 Setting and State of the Art

To solve the optimization problem (1) under communication constraints, a classical algorithm is FedAvg with compression (see Algorithm 3 in Appendix C), which can be written as:

$$w_{t+1} = w_t - \frac{\eta}{M} \sum_{i=1}^{M} C(g_t^i), \quad (2)$$

where $g_t^i$ is the stochastic gradient computed by client $i$ at iteration $t \in \mathbb{N}$, and $C: \mathbb{R}^d \to \mathbb{R}^d$ is a compression operator. Each $g_t^i$ is assumed to be an unbiased estimator of the true gradient, i.e., $\mathbb{E}[g_t^i | w_t] = \nabla f_i(w_t)$.

For ease of exposition and analysis, we treat $C$ as a mapping from $\mathbb{R}^d$ to $\mathbb{R}^d$, although in practical implementations: (i) the model parameters are typically updated layer-wise; (ii) several compression techniques require adaptations to the standard update rule (2). We now review commonly used classes of compressors.

## 2.1 Compressors

### Quantization-based Compressors.

These methods reduce communication by lowering the bit precision of the transmitted gradient values. Two common approaches are:
* **Precision reduction:** Directly reducing the bitwidth of floating-point values. For instance, 8-bit quantization [9] or even 1-bit representations [10] are commonly used.

* **Dictionary-based methods:** Gradients are quantized via a shared codebook. For example, QSGD [11] defines the compressed vector $\mathcal{C}(g)$ componentwise as:

$$ \mathcal{C}(g)_j = \|g\|_2 \cdot \operatorname{sgn}(g_j) \cdot \xi_j(g, s), \quad j \in [d], \qquad (3) $$

where $s$ is the number of quantization levels, and the random variable $\xi_j(g, s)$ satisfies

$$ \xi_j(g, s) = \begin{cases} \frac{\ell}{s} & \text{with probability } 1 + \ell - \frac{|g_j|}{\|g\|_2} s, \\ \frac{\ell+1}{s} & \text{otherwise,} \end{cases} $$

with $\ell \in \mathbb{N}$ chosen so that $\frac{|g_j|}{\|g\|_2} \in [\frac{\ell}{s}, \frac{\ell+1}{s}]$.

In this scheme, clients send the tuple $(\|g\|_2, \sigma, \zeta)$, where $\sigma$ contains the signs of $g$ and $\zeta$ the quantized coefficients.

For additional examples, including low-rank quantization methods, we refer the reader to [5, 6].

## Sparsification-based Compressors.

These methods reduce communication by enforcing sparsity, i.e., zeroing out a large fraction of the gradient coordinates:

* **Rand-k:** Uniformly selects $k$ coordinates to retain:

$$ \mathcal{C}(g) = \frac{d}{k} \sum_{j \in S} g_j e_j, $$

where $S$ is a random subset of $[d]$ with cardinality $k$, and $\{e_j\}_{j=1}^d$ is the canonical basis of $\mathbb{R}^d$. The scaling factor $d/k$ ensures unbiasedness.

In practice, sparsification is typically applied layer-wise, and $k$ may be set as a fixed proportion of non-zero coordinates.

* **Top-k:** Retains the $k$ largest-magnitude components:

$$ \mathcal{C}(g) = \sum_{i=d-k+1}^{d} g_{(i)} e_{(i)}, $$

where coordinates are sorted by absolute value: $|g_{(1)}| \le \dots \le |g_{(d)}|$. Variants such as Threshold-v [12] retain all components exceeding a fixed threshold.

At the implementation level, a sparse vector is typically represented using two components: one vector containing the values of the selected elements of $g$, and another containing the ordered indices of the nonzero elements of $\mathcal{C}(g)$. Quantization and
sparsification methods can be combined: for example, one can first apply a **Top-k** compressor and then quantize the *k* nonzero components to reduce their precision. In the context of analyzing the convergence of (2), it is useful to distinguish compressors based on their bias properties. A compressor $\mathcal{C}: \mathbb{R}^d \to \mathbb{R}^d$ is said to be unbiased if for all $g \in \mathbb{R}^d$, $\mathbb{E}[\mathcal{C}(g)] = g$ (see Assumption H1 for details); otherwise, it is biased (see Assumption H1'). Examples of unbiased compressors include the dictionary-based method defined in (3) and **Rand-k**, whereas **Top-k** is biased. We refer to [13, 14] for comprehensive discussions on unbiased compressors. Unbiased compressors enjoy appealing theoretical guarantees: for example, in gradient descent, one can establish convergence to a neighborhood of the optimum under unbiased compression when optimizing convex objectives [13]. In contrast, analyzing biased compressors is more challenging. In fact, it has been shown that no general convergence guarantees can be obtained for biased compression, even in the strongly convex setting [15, Section 5.2]. Nevertheless, in practice, biased compressors such as **Top-k** or its variants often outperform unbiased, randomized alternatives [16, 17]. To better understand and stabilize these biased methods, several new algorithmic frameworks have been proposed, which we now review.

## 2.2 Algorithm Design

A widely adopted mechanism in communication-efficient optimization is Error Feedback (EF), where each client stores the accumulated compression error and reinjects it in the next update [7, 10]. This approach enables convergence guarantees even when using biased compressors, see [15, 18–20]. Moreover, EF can also be applied on the server side, especially in cross-device FL scenarios [21].

To improve theoretical guarantees and stability, the EF21 method was proposed in [8]. Rather than applying compression directly to gradients, EF21 compresses the difference between the current stochastic gradient and the previous descent direction. This design has inspired a series of extensions [22–25].

Another influential approach is DIANA [26], which introduces a shared memory vector maintained by both clients and the server. Compression is applied to the deviation between this memory and the local stochastic gradient. While the original method includes a proximal step to address regularized problems, a simplified version without this step can be used in the absence of regularization. Further developments and analyses around DIANA can be found in [27–29].

# 3 Two New Algorithms

In this section, we introduce the algorithms evaluated in this work, specifically designed for FL under gradient compression.

## 3.1 Algorithm 1: ProjFL

Our first contribution is the ProjFL algorithm, which we now describe in detail. This algorithm leverages the fact that both the server and each client *i* have access to the local descent direction $D_i^t$ at iteration *t*. At the next iteration, instead of compressing
the full stochastic gradient $g_{t+1}^i$, client $i$ projects this gradient onto the one-dimensional subspace generated by $\bar{D}_t^i$, the average of the previous descent directions $D_t^i$. This yields the decomposition $g_{t+1}^i = \alpha_{t+1}^i \bar{D}_t^i + (g_{t+1}^i)^\perp$, where $(g_{t+1}^i)^\perp$ is orthogonal to $\bar{D}_t^i$, i.e., $\bar{D}_t^i \cdot (g_{t+1}^i)^\perp = 0$ (see line 6 of Algorithm 1). The scalar $\alpha_{t+1}^i$ thus captures the entire component of the gradient in the known direction, enabling a highly compact representation. Instead of compressing the full gradient, the client compresses only the orthogonal component $(g_{t+1}^i)^\perp$ and transmits the pair $(\alpha_{t+1}^i, M_{t+1}^i)$ to the server, where $M_{t+1}^i$ is the compressed version of $(g_{t+1}^i)^\perp$.

Two extreme cases help illustrate the benefits of this approach:

* If $g_{t+1}^i$ is nearly aligned with $\bar{D}_t^i$, then $\alpha_{t+1}^i$ captures nearly all the gradient information, and the compressed component is negligible.

* Conversely, if $g_{t+1}^i$ is orthogonal to $\bar{D}_t^i$, then $\alpha_{t+1}^i = 0$, and only the orthogonal part is transmitted, avoiding any misleading bias from projecting in the wrong direction.

Figure 1 illustrates the key differences between Algorithm 1 and EF21.

**Algorithm 1 ProjFL**

1: **Initialization:** $w_0 \in \mathbb{R}^d$, $D_0^i = 0$. Number of previous directions of descent to consider $K \in \mathbb{N}^*$.

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

3: **for** Each client $i$ **do**

4: Receive $w_t$.

5: Compute Stochastic Gradient $g_{t+1}^i$.

6: $\bar{D}_t^i = \frac{1}{K} \sum_{k=0}^{K-1} D_{t-k}^i$ ▷ with obvious adaptation<fnref n="1" /> when $t < K - 1$

7: $\alpha_{t+1}^i = \frac{g_{t+1}^i \cdot \bar{D}_t^i}{\|\bar{D}_t^i\|_2^2}$ such that $g_{t+1}^i = \alpha_{t+1}^i \bar{D}_t^i + (g_{t+1}^i)^\perp$ satisfying $\bar{D}_t^i \cdot (g_{t+1}^i)^\perp = 0$.

8: $M_{t+1}^i = C((g_{t+1}^i)^\perp)$

9: $D_{t+1}^i = \alpha_{t+1}^i \bar{D}_t^i + M_{t+1}^i$ ▷ Update the descent direction

10: Send $(\alpha_{t+1}^i, M_{t+1}^i)$ to the Central Server.

11: **end for**

12: **Central Server:**

13: $\bar{D}_t^i = \frac{1}{K} \sum_{k=0}^{K-1} D_{t-k}^i$ ▷ Same computation as line 6

14: $D_{t+1}^i = \alpha_{t+1}^i \bar{D}_t^i + M_{t+1}^i$ ▷ Update the descent direction

15: $w_{t+1} = w_t - \frac{\eta}{M} \sum_{i=1}^{M} D_{t+1}^i$.

16: **end for**

## 3.2 Algorithm 2: ProjFL+EF

We now present an extension of Algorithm 1 that incorporates the Error Feed-back mechanism. In Algorithm 2, we modify Algorithm 1 to explicitly account for

<footnote n="1">¹If $t < K - 1$, then $\bar{D}_t^i$ is defined as $\bar{D}_t^i = \frac{1}{t+1} \sum_{k=0}^{t} D_{t-k}^i$.</footnote>
**Definition 2** (L-smooth functions) A function $f: \mathbb{R}^d \to \mathbb{R}$ is called L-smooth if $\nabla f$ is L-Lipschitz continuous, i.e., for all $x, y \in \mathbb{R}^d$,

$$ \|\nabla f(x) - \nabla f(y)\| \le L \|x - y\|. \quad (4) $$

## 4.1 On Algorithm 1: ProjFL

We give below convergence results on ProjFL (Algorithm 1). Let us introduce the following assumptions:

H1 There exists an i.i.d. sequence of compressors $(C_t^i)_{i \in [M], t \ge 1}$ where for any $i \in [M]$ and $t \ge 0$, $C_{t+1}^i: \mathbb{R}^d \to \mathbb{R}$ is the compressor employed by client $i$ at iteration $t$. For convenience, we simply write $\mathcal{C}$. We assume that for all $w \in \mathbb{R}^d$, $\mathbb{E}[\mathcal{C}(w)] = w$ and $\mathbb{E}[\|\mathcal{C}(w)\|^2] \le \beta \|w\|^2$ for some $\beta \ge 1$.<fnref n="2" />

H2 There exist $a, b > 0$ such that for all $w \in \mathbb{R}^d$, $\frac{1}{M} \sum_{i=1}^M \|\nabla f_i(w)\|^2 \le a + b \|\nabla f(w)\|^2$.

H3 There exists an i.i.d. sequence of random vector fields $(\xi_t^i)_{i \in [M], t \ge 1}$ such that for any $i \in [M]$ and $t \ge 0$, $g_{t+1}^i = \nabla f_i(w_t) + \xi_{t+1}^i(w_t)$ and for any $w \in \mathbb{R}^d$, $\mathbb{E}[\xi_t^i(w)] = 0$ and $\mathbb{E}[\|\xi_t^i(w)\|^2] \le \sigma^2$ for some $\sigma > 0$. Moreover, the sequences $(\xi_t^i)_{i \in [M], t \ge 1}$ and $(C_t^i)_{i \in [M], t \ge 1}$ are independent.

We now discuss the role and implications of these assumptions.

* Assumption H1 restricts our analysis to *unbiased compression operators*. Crucially, since Algorithm 1 lacks an error feedback mechanism, convergence guarantees cannot be extended to biased compressors in this framework. For biased compressors, see Section 4.2.

* Assumption H2 formalizes the *bounded gradient dissimilarity* condition, which quantifies data heterogeneity across clients by controlling the deviation between local gradients $\nabla f_i(w)$ and their global average $\nabla f(w)$.

* Assumption H3 bounds the variance of stochastic gradient noise arising from mini-batch sampling. Notably, this noise intensity may vary both across clients (due to differences in local loss landscapes) and across parameter regions (e.g., near optima versus high-curvature regions).

In the following theorem—whose proof is given in Appendix A—we prove a linear convergence rate for Algorithm 1 towards a neighborhood of the optimal point.

**Theorem 1** Assume H1-H2-H3. Then the following holds:

1. if each $f_i$ is $\mu$-strongly convex and L-smooth (see Definitions 1 and 2), then, for any learning rate $0 \le \eta \le (1+b^{\frac{\beta-1}{M}})^{-1} \frac{2}{\mu+L}$, the sequence $(w_t)_{t \ge 0}$ generated by Algorithm 1 satisfies, for any $t \in \mathbb{N}$,

$$ \mathbb{E}[\|w_t - w^*\|^2] \le \left(1 - 2\eta \frac{\mu L}{\mu + L}\right)^t \mathbb{E}[\|w_0 - w^*\|^2] + \eta \frac{\mu + L}{2\mu LM} (a(\beta - 1) + \beta\sigma^2), \quad (5) $$

<footnote n="2">²Note that since $\mathbb{E}[\|X - \mathbb{E}[X]\|_2^2] = \mathbb{E}[\|X\|_2^2] - \|\mathbb{E}[X]\|_2^2$, Assumption H1 implies $\mathbb{E}[\|\mathcal{C}(w) - w\|_2^2] \le (\beta - 1)\|w\|_2^2$.</footnote>
where $w^* = \arg \min_{\mathbb{R}^d} f$ is the unique global minimizer.

2. if each $f_i$ is convex and L-smooth, and $f$ admits minimizers<fnref n="3" /> then, for any learning rate $0 < \eta \le \frac{1}{2L}(1 + b^{\frac{\beta-1}{M}})^{-1}$, the sequence $(w_t)_{t \ge 0}$ generated by Algorithm 1 satisfies, for any $T \ge 1$,

$$ \mathbb{E}[f(w^{\text{out}})] - f^* \le \frac{1}{(T+1)\eta} \mathbb{E}[\|w_0 - w^*\|^2] + \frac{\eta}{M}(a(\beta - 1) + \beta\sigma^2), $$

where the output $w^{\text{out}}$ is sampled uniformly at random in $\{w_t\}_{t=0}^T$, and $w^* \in \arg \min_{\mathbb{R}^d} f$ is any minimizer.

3. if each $f_i$ is L-smooth and bounded from below, then, for any learning rate $0 < \eta \le \frac{1}{L}(1 + b^{\frac{\beta-1}{M}})^{-1}$, the sequence $(w_t)_{t \ge 0}$ generated by Algorithm 1 satisfies, for any $T \ge 1$,

$$ \mathbb{E}[\|\nabla f(w^{\text{out}})\|^2] \le \frac{2}{(T+1)\eta} \mathbb{E}[|f(w_0) - f^*|] + \frac{L\eta}{M}(a(\beta - 1) + \beta\sigma^2), $$

where the output $w^{\text{out}}$ is sampled uniformly at random in $\{w_t\}_{t=0}^T$ and $f^* = \inf_{\mathbb{R}^d} f$.

Remark 1 Since $f(w_t) - f^* \le \frac{L}{2}\|w_t - w^*\|^2$ for any L-smooth function, item 1 yields

$$ \mathbb{E}[|f(w_t)|] - f^* \le \frac{L}{2} \left(1 - 2\eta \frac{\mu L}{\mu + L}\right)^t \mathbb{E}[\|w_0 - w^*\|^2] + \eta \frac{\mu + L}{4\mu M} (a(\beta - 1) + \beta\sigma^2). $$

The first term on the right-hand side of (5) reflects the initial distance to the optimum. The second term is a variance term corresponding to the (squared) radius of the neighborhood around the optimal point to which the algorithm converges.

This result also provides theoretical support for the common practice of decreasing the learning rate during training. A useful heuristic is as follows: at initialization, when the term $\mathbb{E}[\|w_0 - w^*\|^2]$ typically dominates, a relatively large learning rate should be used so that this term is quickly reduced thanks to the linear convergence rate. As training progresses and the second term on the right-hand side of (5) becomes dominant, the effective "starting point" is now closer to the optimum, and using a smaller step size becomes beneficial to reduce variance and improve stability.

Similar comments apply to items 2 and 3. Note also that when $\beta = 1$ (i.e., no compression), we recover the standard noise terms on the right-hand side of each inequality.

Finally, note that in many practical applications, these convergence rates may coexist in the following sense: even if $f$ is non-convex, it may still be (strongly) convex in a neighborhood of a local minimizer, meaning that locally, the linear convergence rate of item 1 may describe the final phase of training.

## 4.2 On Algorithm 2: ProjFL+EF

Since the Error Feedback mechanism is designed to mitigate the bias introduced by the compressor, we deal here with biased compressors and thus replace Assumption H1 by the following

<footnote n="3">³This holds, for instance, if $f$ is coercive, i.e., $|f(x)| \to +\infty$ as $\|x\| \to +\infty$.</footnote>
H1' There exists an i.i.d. sequence of compressors $(C_t^i)_{i \in [M], t \ge 1}$ where for any $i \in [M]$ and $t \ge 0$, $C_{t+1}^i: \mathbb{R}^d \to \mathbb{R}$ are the compressors employed by client $i$ at iteration $t$. For convenience, we simply write $\mathcal{C}$. We assume that there exists $0 < \delta \le 1$ such that for all $w \in \mathbb{R}^d$, $\mathbb{E}[\|\mathcal{C}(w) - w\|^2] \le (1 - \delta)\|w\|^2$.

Our result follows the same structure as Theorem 1, providing convergence rates for the strongly convex, convex, and non-convex settings.

**Theorem 2** Assume H1'-H2-H3. Then the following holds:

1. if each $f_i$ is $\mu$-strongly convex and L-smooth (see Definitions 1 and 2), then, for any learning rate $0 < \eta \le \min\left(\frac{\delta}{L(4+\delta)}, \frac{\delta}{\sqrt{40(2L+\mu)bL}}\right)$, the sequence $(w_t)_{t \ge 0}$ generated by Algorithm 2 satisfies, for any $T \ge 1$,
$$ \mathbb{E}[f(w^{\text{out}})] - f^* \le \frac{10}{\eta} \left(1 - \frac{\eta\mu}{2}\right)^{T+1} \mathbb{E}[\|w_0 - w^*\|^2] + 20(2L+\mu) \frac{(1-\delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right) + 10 \frac{\eta\sigma^2}{M}, $$
where the output $w^{\text{out}} \in \{w_t\}_{t=0}^T$ is chosen to be $w_t$ with probability proportional to $(1 - \frac{\eta\mu}{2})^{-t}$.

2. if each $f_i$ is convex and L-smooth, and assume also that $f$ admits minimizers$^4$, then, for any learning rate $0 < \eta \le \min\left(\frac{\delta}{L(4+\delta)}, \frac{\delta}{\sqrt{80bL}}\right)$, the sequence $(w_t)_{t \ge 0}$ generated by Algorithm 2 satisfies, for any $T \ge 1$,
$$ \mathbb{E}[|f(w^{\text{out}})|] - f^* \le \frac{10}{\eta(T+1)} \mathbb{E}[\|w_0 - w^*\|^2] + 40L \frac{2(1-\delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right) + 10 \frac{\eta\sigma^2}{M}, $$
where the output $w^{\text{out}}$ is sampled uniformly at random in $\{w_t\}_{t=0}^T$, and $w^* \in \arg\min_{\mathbb{R}^d} f$ is any minimizer.

3. if each $f_i$ is L-smooth and bounded from below, then, for any learning rate $0 < \eta \le \frac{\delta}{4\sqrt{2(b+1)L}}$, the sequence $(w_t)_{t \ge 0}$ generated by Algorithm 2 satisfies, for any $T \ge 1$,
$$ \mathbb{E}[\|\nabla f(w^{\text{out}})\|^2] \le \frac{8}{(T+1)\eta} \mathbb{E}[|f(w_0) - f^*|] + \frac{8(1-\delta)\eta^2 L^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right) + \frac{8\eta L \sigma^2}{2M}, $$
where $w^{\text{out}}$ is sampled uniformly at random in $\{w_t\}_{t=0}^T$ and $f^* = \inf_{\mathbb{R}^d} f$.

**Remark 2** Since $\|w^{\text{out}} - w^*\|^2 \le \frac{2}{\mu}(f(w^{\text{out}}) - f^*)$ for any $\mu$-strongly convex function, item 1 yields

$$ \mathbb{E}[\|w^{\text{out}} - w^*\|^2] \le \frac{20}{\eta\mu} \left(1 - \frac{\eta\mu}{2}\right)^{T+1} \mathbb{E}[\|w_0 - w^*\|^2] + 40(2L+\mu) \frac{(1-\delta)\eta^2}{\delta\mu} \left(\frac{2a}{\delta} + \sigma^2\right) + 20 \frac{\eta\sigma^2}{\mu M}. $$

The comments made after Theorem 1 remain relevant in this case. Again, when there is no compression ($\delta = 1$), we recover the usual rates toward a SGD neighborhood of the optimal point.

**On the proof of Theorem 2.** The proof relies on the analysis of the auxiliary sequence $\tilde{w}_t = w_t - e_t$, where $e_t = \frac{1}{M} \sum_i e_i^t$. (Note that $e_t$ is never computed

<footnote>$^4$This holds, for instance, if $f$ is coercive, i.e., $|f(x)| \to +\infty$ as $\|x\| \to +\infty$.</footnote>
in practice; it is introduced solely for mathematical analysis.) The sequence $(\tilde{w}_t)_{t \ge 0}$ enjoys the appealing property $\tilde{w}_{t+1} = \tilde{w}_t - \eta g_{t+1}$, where $g_{t+1} = \frac{1}{M} \sum_i g_{t+1}^i$. Since $E[g_{t+1} | \tilde{w}_t] = \nabla f(w_t)$, we almost recover the unbiased case. To conclude, it remains to bound the error term $e_t$, which is the purpose of Lemma 4. The detailed proof is provided in Appendix B.

# 5 Numerical experiments

In this section, we numerically evaluate the benefits of Algorithms 1 and 2 to reduce the communication cost in FL, for classification tasks using neural networks.

## 5.1 Datasets, models and preprocessing.

We conduct experiments on MNIST and CIFAR-10 datasets<fnref n="5" />. MNIST contains 70,000 grayscale images of handwritten digits (28×28, 1 channel), split into 60,000 training and 10,000 test samples. CIFAR-10 comprises 60,000 color images (32×32, 3 channels), with 50,000 for training and 10,000 for testing, across 10 classes. We use LeNet-5 [30] for MNIST: two convolutional blocks (with 5×5 kernels, ReLU activations, and 2×2 max pooling), followed by two fully connected layers with ReLU. For CIFAR-10, we adopt ResNet-20 [31] implemented in [32]. These models are standard architectures for their respective tasks. In all settings, 20% of the training set is used for validation. Images are normalized to [-1, 1], data is shuffled, and samples are evenly distributed across clients, with slight variation due to indivisibility.

## 5.2 Experimental methodology.

To assess the efficiency of our algorithms in solving learning tasks while maintaining reasonable communication costs, we monitor convergence-related metrics—specifically, the loss (cross-entropy in our case), accuracy, and the norm of the loss gradient—as functions of the total number of communicated bits. Unless otherwise specified, the results reported in this section are based on the total communication cost (including both uplink and downlink). An exception is Figure 5, which presents results for uplink communication only. Additional experiments, including uplink or downlink evaluations and further performance metrics, are provided in Appendix C. We focus on sparsification-based compressors (Top-k) and evaluate performance across M clients, where $M \in \{3, 10, 100, 1000\}$.

## 5.3 Parameters Selection

### 5.3.1 Hyperparameters

Our objective is not to surpass state-of-the-art performance, as such results often exhibit strong dependence on hyperparameter configurations and may inadvertently reflect tuning bias. To ensure a fair and transparent comparison, we adopt a consistent tuning strategy: all hyperparameters are optimized without compression (i.e., $C =$

<footnote n="5">⁵https://docs.pytorch.org/vision/main/datasets.html</footnote>
Id), and the resulting configurations are applied uniformly across all algorithms. The experimental settings is detailed in C.1.

### 5.3.2 Algorithm parameters

All algorithms are run using the same hyperparameter settings. Before comparing Algorithm 1 and Algorithm 2 with existing methods, we first need to select the parameters $k$ (used in the Top-$k$ compressor) and $K$ (as defined in Algorithms 1 and 2). We empirically set these parameters by balancing the trade-offs between convergence speed, communication cost, and stability across both datasets. In our experiments, we fix$^6 k = 0.01$ and $K = 3$. Detailed parameter-tuning results are provided in Figure C1 of Appendix C.1.

Furthermore, under our experimental setup, we found that, without further tuning, EF21 and DIANA underperformed. A similar behavior was already observed in [25, Section 2.2]. To address this, we introduced an additional parameter $\gamma$ into both methods, which significantly improved their performance (see Algorithms 5 and 7 for details). A thorough discussion is provided in Appendix C.

## 5.4 Evaluation of Algorithms 1 and 2

We compare our methods to the baselines FedAvg with compression, EF, EF21, and DIANA (see Algorithms 3, 4, 5, and 7 in Appendix C). Both training and test losses are reported. The results—with an increasing number of clients—are presented in Figure 2, 3, 4, 5 (with further comparisons using different metrics and parameters in Appendix C).

<footnote>$^6 k = 0.01$ means that, in each layer, only the fraction $k$ of components with the largest magnitudes are retained.</footnote>
<figure><img src="image_3.png" /><figcaption>**Fig. 3** Comparison of Algorithms 1 and 2 with FedAvg with compression, EF, EF21, and DIANA for $M = 10$ clients.</figcaption></figure>

<figure><img src="image_4.png" /></figure>
<figure><img src="image_5.png" /><figcaption>**Fig. 4** Comparison of Algorithms 1 and 2 with FedAvg with compression, EF, EF21, and DIANA for $M = 100$ clients.</figcaption></figure>

**General comments:**

Regardless of the algorithm, the first observation we can make is that as the number of clients increases, both communication costs and losses tend to rise. The first effect is straightforward: communication cost grows linearly with the number of clients $M$. This is why we report the uplink communication cost for $M = 1000$ clients in Figure 5, rather than the total communication cost. The increase in losses can be explained by the fact that, in datasets with a finite number of instances—such as MNIST or CIFAR-10—the effective batch size per client decreases as the number of clients increases, resulting in noisier stochastic gradients. This reduction amplifies the variance of the gradient estimates, an effect that is further exacerbated by compression. These observations are consistent with the noise terms appearing in the convergence rates of all the considered algorithms (including ours; see the right-hand side of the bounds in Theorems 1 and 2).

**On the MNIST dataset:**

Algorithm 1 outperforms both EF21 and DIANA when using 3 or 1000 clients. Its performance with 10 clients remains competitive, albeit slightly below the best-performing methods.

Across these experiments, EF21 and DIANA exhibit very similar behavior overall, although DIANA performs noticeably better in the 10-client configuration. When
<figure><img src="image_6.png" /><figcaption>**Fig. 5** Comparison of Algorithms 1 and 2 with FedAvg with compression, EF, EF21, and DIANA for $M = 1000$ clients. We consider here the uplink communication cost only.</figcaption></figure>

error feedback is incorporated, the EF algorithm demonstrates consistently competitive results regardless of the number of clients.

Importantly, Algorithm 2 achieves the best overall trade-off between accuracy and communication efficiency in both training and testing. For comparable test accuracy, it requires up to 8× less communication than EF in Figure 2 and 6× less in Figure 3 than DIANA.

On the CIFAR-10 dataset:

ProjFL delivers slightly better performance than Top-k across all experiments, except for the 100-client setting, where it attains the lowest accuracy among the compared methods—consistent with the trend observed in the MNIST analysis.

The observations made for EF21 and DIANA on the MNIST dataset also hold for CIFAR-10: both algorithms display very similar overall behavior, though DIANA performs noticeably better in the 10-client configuration.

The EF algorithm continues to offer competitive performance in terms of both accuracy and communication cost, except when $M = 10$. Once again, Algorithm 2 demonstrates a clear advantage, achieving strong results with significantly fewer training epochs, thereby reducing local computation time.

One might be surprised by the increase in test loss in Figure 2 and Figure 3 at the end of training for Algorithm 2. This rise is due to overfitting, as the training loss
continues to decrease monotonically (see Appendix C). The reason the algorithm was not stopped earlier lies in the early stopping criterion (specifically the patience), which was tuned based on the behavior of the baseline FedAvg, as previously discussed in 5.3.1. Naturally, if we had optimized early stopping specifically for Algorithm 2, more favorable stopping conditions would have been chosen.

# 6 Conclusion and Discussion

This work contributes to the growing body of research on communication-efficient FL by proposing two theoretically grounded and practically effective algorithms. Our algorithms provably improve convergence speed while requiring the transmission of only one additional scalar per iteration.

We established convergence guarantees for a variety of smooth objectives, ranging from strongly convex to non-convex settings. Furthermore, we conducted extensive experiments on large-scale neural networks to evaluate the empirical performance of our methods.

We conclude by outlining three promising directions for future work. First, our approach could be combined with acceleration techniques, such as those proposed in [33, 34], to further improve convergence. Second, instead of projecting onto the one-dimensional subspace spanned by the average of the last *K* descent directions, one could consider projections onto the full *K*-dimensional subspace generated by these directions. Third, for a large number of clients, one could apply bidirectional compression, as done in [21].

# Acknowledgements

This work has been partly supported by the FLUTE project, EC grant 101095382, and French State support under the France 2030 program with the reference ANR-23-PEIA-005 (REDEEM project). This work was partially carried out while A.D. was a postdoctoral researcher at Inria Lille - Nord Europe.
## References

[1] Kairouz, P., McMahan, H.B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A.N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., D’Oliveira, R.G.L., Eichner, H., El Rouayheb, S., Evans, D., Gardner, J., Garrett, Z., Gascón, A., Ghazi, B., Gibbons, P.B., Gruteser, M., Harchaoui, Z., He, C., He, L., Huo, Z., Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M., Konecný, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T., Liu, Y., Mittal, P., Mohri, M., Nock, R., Özgür, A., Pagh, R., Qi, H., Ramage, D., Raskar, R., Raykova, M., Song, D., Song, W., Stich, S.U., Sun, Z., Suresh, A.T., Tramèr, F., Vepakomma, P., Wang, J., Xiong, L., Xu, Z., Yang, Q., Yu, F.X., Yu, H., Zhao, S.: Advances and open problems in federated learning. Foundations and Trends® in Machine Learning **14**(1–2), 1–210 (2021) https://doi.org/10.1561/2200000083

[2] McMahan, B., Moore, E., Ramage, D., Hampson, S., Arcas, B.A.: Communication-Efficient Learning of Deep Networks from Decentralized Data. In: Singh, A., Zhu, J. (eds.) Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 54, pp. 1273–1282 (2017). PMLR. https://proceedings.mlr.press/v54/mcmahan17a.html

[3] Karimireddy, S.P., Kale, S., Mohri, M., Reddi, S., Stich, S., Suresh, A.T.: SCAF-FOLD: Stochastic controlled averaging for federated learning. In: III, H.D., Singh, A. (eds.) Proceedings of the 37th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 119, pp. 5132–5143 (2020). PMLR. https://proceedings.mlr.press/v119/karimireddy20a.html

[4] Zhao, H., Li, Z., Richtárik, P.: Fedpage: A fast local stochastic gradient method for communication-efficient federated learning. arXiv preprint arXiv:2108.04755 (2021)

[5] Xu, H., Ho, C.-Y., Abdelmoniem, A.M., Dutta, A., Bergou, E.H., Karatsenidis, K., Canini, M., Kalnis, P.: Grace: A compressed communication framework for distributed machine learning. In: 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS), pp. 561–572 (2021). IEEE

[6] Philippenko, C., Dieuleveut, A.: Compressed and distributed least-squares regression: convergence rates with applications to federated learning. Journal of Machine Learning Research **25**(288), 1–80 (2024)

[7] Karimireddy, S.P., Rebjock, Q., Stich, S., Jaggi, M.: Error feedback fixes SignSGD and other gradient compression schemes. In: Chaudhuri, K., Salakhutdinov, R. (eds.) Proceedings of the 36th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 97, pp. 3252–3261 (2019). PMLR. https://proceedings.mlr.press/v97/karimireddy19a.html

[8] Richtarik, P., Sokolov, I., Fatkhullin, I.: Ef21: A new, simpler, theoretically better,
and practically faster error feedback. In: Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P.S., Vaughan, J.W. (eds.) Advances in Neural Information Processing Systems, vol. 34, pp. 4384–4396 (2021). Curran Associates, Inc.

[9] Dettmers, T.: 8-bit approximations for parallelism in deep learning. In: International Conference on Learning Representations (ICLR) (2016)

[10] Seide, F., Fu, H., Droppo, J., Li, G., Yu, D.: 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnn s. In: Interspeech, vol. 2014, pp. 1058–1062 (2014). Singapore

[11] Alistarh, D., Grubic, D., Li, J., Tomioka, R., Vojnovic, M.: Qsgd: Communication-efficient sgd via gradient quantization and encoding. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 30 (2017). Curran Associates, Inc.

[12] Dutta, A., Bergou, E.H., Abdelmoniem, A.M., Ho, C., Sahu, A.N., Canini, M., Kalnis, P.: On the discrepancy between the theoretical analysis and practical implementations of compressed communication for distributed deep learning. Proceedings of the AAAI Conference on Artificial Intelligence 34(04), 3817–3824 (2020) https://doi.org/10.1609/aaai.v34i04.5793

[13] Khirirat, S., Feyzmahdavian, H.R., Johansson, M.: Distributed learning with compressed gradients. arXiv preprint arXiv:1806.06573 (2018)

[14] Safaryan, M., Shulgin, E., Richtárik, P.: Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor. Information and Inference: A Journal of the IMA 11(2), 557–580 (2021) https://doi.org/10.1093/imaiai/iaab006

[15] Beznosikov, A., Horváth, S., Richtárik, P., Safaryan, M.: On biased compression for distributed learning. Journal of Machine Learning Research 24(276), 1–50 (2023)

[16] Dryden, N., Moon, T., Jacobs, S.A., Van Essen, B.: Communication quantization for data-parallel training of deep neural networks. In: 2016 2nd Workshop on Machine Learning in HPC Environments (MLHPC), pp. 1–8 (2016). https://doi.org/10.1109/MLHPC.2016.004

[17] Aji, A.F., Heafield, K.: Sparse communication for distributed gradient descent. In: Palmer, M., Hwa, R., Riedel, S. (eds.) Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, Copenhagen, Denmark, pp. 440–445 (2017). https://doi.org/10.18653/v1/D17-1045 . Association for Computational Linguistics

[18] Stich, S.U., Karimireddy, S.P.: The error-feedback framework: Sgd with delayed
gradients. Journal of Machine Learning Research 21 (237), 1–36 (2020)

[19] Stich, S.U., Cordonnier, J.-B., Jaggi, M.: Sparsified sgd with memory. In: Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 31 (2018). Curran Associates, Inc.

[20] Alistarh, D., Hoefler, T., Johansson, M., Konstantinov, N., Khirirat, S., Renggli, C.: The convergence of sparsified gradient methods. In: Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 31 (2018). Curran Associates, Inc.

[21] Tang, H., Yu, C., Lian, X., Zhang, T., Liu, J.: DoubleSqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression. In: Chaudhuri, K., Salakhutdinov, R. (eds.) Proceedings of the 36th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 97, pp. 6155–6165 (2019). PMLR. https://proceedings.mlr.press/v97/tang19d.html

[22] Fatkhullin, I., Sokolov, I., Gorbunov, E., Li, Z., Richtárik, P.: Ef21 with bells & whistles: Six algorithmic extensions of modern error feedback. Journal of Machine Learning Research 26 (189), 1–50 (2025)

[23] Makarenko, M., Gasanov, E., Islamov, R., Sadiev, A., Richtárik, P.: Adaptive compression for communication-efficient distributed training. arXiv preprint arXiv:2211.00188 (2022)

[24] Gruntkowska, K., Tyurin, A., Richtárik, P.: EF21-p and friends: Improved theoretical communication complexity for distributed optimization with bidirectional compression. In: Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., Scarlett, J. (eds.) Proceedings of the 40th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 202, pp. 11761–11807 (2023). PMLR. https://proceedings.mlr.press/v202/gruntkowska23a.html

[25] Fatkhullin, I., Tyurin, A., Richtarik, P.: Momentum provably improves error feedback! In: Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., Levine, S. (eds.) Advances in Neural Information Processing Systems, vol. 36, pp. 76444–76495 (2023). Curran Associates, Inc.

[26] Mishchenko, K., Gorbunov, E., Takáč, M., and, P.R.: Distributed learning with compressed gradient differences*. Optimization Methods and Software 0(0), 1–16 (2024) https://doi.org/10.1080/10556788.2024.2358790 . Taylor & Francis

[27] Horváth, S., Kovalev, D., Mishchenko, K., Richtárik, P., Stich, S.: Stochastic distributed learning with gradient quantization and double-variance reduction. Optimization Methods and Software 38(1), 91–106 (2023). Taylor & Francis
[28] Condat, L., Richtarik, P.: Murana: A generic framework for stochastic variance-reduced optimization. In: Dong, B., Li, Q., Wang, L., Xu, Z.-Q.J. (eds.) Proceedings of Mathematical and Scientific Machine Learning. Proceedings of Machine Learning Research, vol. 190, pp. 81–96 (2022). PMLR

[29] Gorbunov, E., Hanzely, F., Richtarik, P.: A unified theory of sgd: Variance reduction, sampling, quantization and coordinate descent. In: Chiappa, S., Calandra, R. (eds.) Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 108, pp. 680–690 (2020). PMLR

[30] LeCun, Y., et al.: Lenet-5, convolutional neural networks. URL: http://yann.lecun.com/exdb/lenet 20(5), 14 (2015)

[31] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2016)

[32] Idelbayev, Y.: Proper ResNet Implementation for CIFAR10/CIFAR100 in PyTorch. https://github.com/akamaster/pytorch_resnet_cifar10. Accessed: 20xx-xx-xx

[33] Li, Z., Kovalev, D., Qian, X., Richtarik, P.: Acceleration for compressed gradient descent in distributed and federated optimization. In: III, H.D., Singh, A. (eds.) Proceedings of the 37th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 119, pp. 5895–5904 (2020). PMLR

[34] He, Y., Huang, X., Yuan, K.: Unbiased compression saves communication in distributed optimization: When and how much? In: Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., Levine, S. (eds.) Advances in Neural Information Processing Systems, vol. 36, pp. 47991–48020 (2023). Curran Associates, Inc.

[35] Nesterov, Y.: Lectures on Convex Optimization vol. 137, (2018). Springer
# Contents

<table><tr><td>1</td><td>Introduction</td><td>1</td></tr><tr><td>1.1</td><td>Main Contributions</td><td>3</td></tr><tr><td>2</td><td>Setting and State of the Art</td><td>3</td></tr><tr><td>2.1</td><td>Compressors</td><td>3</td></tr><tr><td>2.2</td><td>Algorithm Design</td><td>5</td></tr><tr><td>3</td><td>Two New Algorithms</td><td>5</td></tr><tr><td>3.1</td><td>Algorithm 1: ProjFL</td><td>5</td></tr><tr><td>3.2</td><td>Algorithm 2: ProjFL+EF</td><td>6</td></tr><tr><td>4</td><td>Theoretical convergence results</td><td>7</td></tr><tr><td>4.1</td><td>On Algorithm 1: ProjFL</td><td>8</td></tr><tr><td>4.2</td><td>On Algorithm 2: ProjFL+EF</td><td>9</td></tr><tr><td>5</td><td>Numerical experiments</td><td>11</td></tr><tr><td>5.1</td><td>Datasets, models and preprocessing.</td><td>11</td></tr><tr><td>5.2</td><td>Experimental methodology.</td><td>11</td></tr><tr><td>5.3</td><td>Parameters Selection</td><td>11</td></tr><tr><td>5.3.1</td><td>Hyperparameters</td><td>11</td></tr><tr><td>5.3.2</td><td>Algorithm parameters</td><td>12</td></tr><tr><td>5.4</td><td>Evaluation of Algorithms 1 and 2</td><td>12</td></tr><tr><td>6</td><td>Conclusion and Discussion</td><td>16</td></tr><tr><td>A</td><td>Proof of Theorem 1</td><td>22</td></tr><tr><td>A.1</td><td>Proof of Theorem 1: convex case</td><td>22</td></tr><tr><td>A.2</td><td>Proof of Theorem 1: non-convex case</td><td>24</td></tr><tr><td>B</td><td>Proof of Theorem 2</td><td>25</td></tr><tr><td>B.1</td><td>Proof of Theorem 2: convex case</td><td>27</td></tr><tr><td>B.2</td><td>Proof of Theorem 2: non-convex case</td><td>29</td></tr><tr><td>C</td><td>Experimental details and Additional experiments</td><td>30</td></tr><tr><td>C.1</td><td>Experimental details</td><td>30</td></tr><tr><td>C.1.1</td><td>Hardware and software.</td><td>30</td></tr><tr><td>C.1.2</td><td>Hyperparameters</td><td>30</td></tr><tr><td>C.1.3</td><td>Algorithms parameter</td><td>30</td></tr><tr><td>C.1.4</td><td>Algorithms evaluated in our experiments.</td><td>31</td></tr><tr><td>C.1.5</td><td>Variability across runs.</td><td>34</td></tr><tr><td>C.2</td><td>Overfitting on the Training Set for CIFAR-10</td><td>35</td></tr><tr><td>C.3</td><td>Additional Experiments with Uplink and Downlink Communication Costs</td><td>36</td></tr><tr><td>C.4</td><td>Accuracy</td><td>38</td></tr><tr><td>C.5</td><td>Evaluation of EF21 and DIANA under different hyperparameters</td><td>39</td></tr></table>
This appendix is organized as follows. In Section A, we present the proof of Theorem 1. In Section B, we prove Theorem 2. In Section C, we provide implementation details and additional numerical evaluations.

# Appendix A Proof of Theorem 1

This section is devoted to the proof of Theorem 1. We first recall the following property satisfied $\mu$-strongly convex and $L$-smooth functions.

**Proposition 3** ([35, Theorem 2.1.12]) For any $\mu$-strongly convex and $L$-smooth function $f: \mathbb{R}^d \to \mathbb{R}$ (see Definitions 1 and 2), it holds, for any $x, y \in \mathbb{R}^d$,

$$ \langle \nabla f(x) - \nabla f(y), x - y \rangle \geq \frac{\mu L}{\mu + L} \|x - y\|^2 + \frac{1}{\mu + L} \|\nabla f(x) - \nabla f(y)\|^2. $$

## A.1 Proof of Theorem 1: convex case

*Proof of item 1 of Theorem 1* Let $t \in \mathbb{N}$ and $w^* = \arg\min f$ be the unique minimizer (by strong convexity). We have

$$ \|w_{t+1} - w^*\|^2 = \|w_t - w^*\|^2 - 2\eta \langle w_t - w^*, \frac{1}{M} \sum_{i=1}^{M} D_{t+1}^i \rangle + \eta^2 \left\| \frac{1}{M} \sum_{i=1}^{M} D_{t+1}^i \right\|^2. $$

By Assumptions H1 and H3, we have

$$ \mathbb{E}[\mathcal{C}((g_{t+1}^i)^\perp)] = \mathbb{E}[(g_{t+1}^i)^\perp]. $$

Therefore, using Assumption H3 again, it follows that

$$ \mathbb{E}[D_{t+1}^i] = \mathbb{E}[g_{t+1}^i] = \mathbb{E}[\nabla f_i(w_t)]. $$

Conditioning on $w_t$, we obtain, using H3,

$$ \mathbb{E}[\|w_{t+1} - w^*\|^2] = \mathbb{E}[\|w_t - w^*\|^2] - 2\eta\mathbb{E}[\langle w_t - w^*, \nabla f(w_t) \rangle] + \eta^2\mathbb{E}\left[\left\|\frac{1}{M}\sum_{i=1}^{M} D_{t+1}^i\right\|^2\right]. $$

Using Proposition 3 (since $\nabla f(w^*) = 0$), it becomes

$$ \begin{aligned} \mathbb{E}[\|w_{t+1} - w^*\|^2] \leq & \left(1 - 2\eta \frac{\mu L}{\mu + L}\right) \mathbb{E}[\|w_t - w^*\|^2] - 2\frac{\eta}{\mu + L} \mathbb{E}[\|\nabla f(w_t)\|] \\ & + \eta^2 \mathbb{E}\left[\left\|\frac{1}{M}\sum_{i=1}^{M} D_{t+1}^i\right\|^2\right]. \end{aligned} \quad (A1) $$

Using again H3 and the fact that $\mathbb{E}[D_{t+1}^i] = \mathbb{E}[\nabla f_i(w_t)]$, we have

$$ \begin{aligned} \mathbb{E}\left[\left\|\frac{1}{M}\sum_{i=1}^{M} D_{t+1}^i\right\|^2\right] &= \mathbb{E}[\|\nabla f(w_t)\|^2] + \mathbb{E}\left[\left\|\frac{1}{M}\sum_{i=1}^{M} D_{t+1}^i - \nabla f_i(w_t)\right\|^2\right] \\ &= \mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{1}{M^2} \sum_{i=1}^{M} \mathbb{E}[\|D_{t+1}^i - \nabla f_i(w_t)\|^2]. \end{aligned} \quad (A2) $$

Using H1 and H3,

$$ \mathbb{E}[\|D_{t+1}^i - \nabla f_i(w_t)\|^2] = \mathbb{E}[\|D_{t+1}^i\|^2] - \mathbb{E}[\|\nabla f_i(w_t)\|^2] $$
$$
\begin{align*}
&= \mathbb{E}[\|\alpha_{t+1}^i \bar{D}_t^i + C((g_{t+1}^i)^\perp)\|^2] - \mathbb{E}[\|\nabla f_i(w_t)\|^2] \\
&= \mathbb{E}[\|\alpha_{t+1}^i \bar{D}_t^i\|^2] + \mathbb{E}[\|C((g_{t+1}^i)^\perp)\|^2] - \mathbb{E}[\|\nabla f_i(w_t)\|^2] \\
&\le \mathbb{E}[\|\alpha_{t+1}^i \bar{D}_t^i\|^2] + \beta \mathbb{E}[\|(g_{t+1}^i)^\perp\|^2] - \mathbb{E}[\|\nabla f_i(w_t)\|^2] \\
&\le \beta \mathbb{E}[\|\alpha_{t+1}^i \bar{D}_t^i\|^2] + \beta \mathbb{E}[\|(g_{t+1}^i)^\perp\|^2] - \mathbb{E}[\|\nabla f_i(w_t)\|^2] \quad (\beta \ge 1) \\
&= \beta \mathbb{E}[\|g_{t+1}^i\|^2] - \mathbb{E}[\|\nabla f_i(w_t)\|^2] \le (\beta - 1) \mathbb{E}[\|\nabla f_i(w_t)\|^2] + \beta \sigma^2.
\end{align*}
$$

Going back to (A2), we have

$$
\mathbb{E}\left[\left\|\frac{1}{M}\sum_{i=1}^{M} \mathbf{D}_{t+1}^{i}\right\|^{2}\right] \leq \mathbb{E}\left[\|\nabla f(w_{t})\|^{2}\right]+\frac{\beta-1}{M^{2}} \sum_{i=1}^{M} \mathbb{E}\left[\|\nabla f_{i}(w_{t})\|^{2}\right]+\frac{\beta \sigma^{2}}{M}.
$$

By H2,

$$
\mathbb{E}\left[\left\|\frac{1}{M}\sum_{i=1}^{M} \mathbf{D}_{t+1}^{i}\right\|^{2}\right] \leq\left(1+b \frac{\beta-1}{M}\right) \mathbb{E}\left[\|\nabla f(w_{t})\|^{2}\right]+a \frac{\beta-1}{M}+\frac{\beta \sigma^{2}}{M}.
\quad(\text{A3})
$$

Going back to (A1) we have

$$
\begin{align*}
\mathbb{E}[\|w_{t+1} - w^*\|^2] &\le \left(1 - 2\eta \frac{\mu L}{\mu + L}\right) \mathbb{E}[\|w_t - w^*\|^2] \\
&\quad + \eta \left(\eta \left(1 + b \frac{\beta - 1}{M}\right) - \frac{2}{\mu + L}\right) \mathbb{E}[\|\nabla f(w_t)\|^2] \\
&\quad + \eta^2 a \frac{\beta - 1}{M} + \eta^2 \frac{\beta \sigma^2}{M}.
\end{align*}
$$

Since $\eta(1 + b \frac{\beta - 1}{M}) \le \frac{2}{\mu + L}$, we obtain

$$
\mathbb{E}[\|w_{t+1} - w^*\|^2] \le \left(1 - 2\eta \frac{\mu L}{\mu + L}\right) \mathbb{E}[\|w_t - w^*\|^2] + \eta^2 a \frac{\beta - 1}{M} + \eta^2 \frac{\beta \sigma^2}{M}.
$$

Hence, noticing<fnref n="7" /> that $\eta < \frac{\mu+L}{2\mu L}$, we have

$$
\mathbb{E}[\|w_t - w^*\|^2] \le \left(1 - 2\eta \frac{\mu L}{\mu + L}\right)^t \mathbb{E}[\|w_0 - w^*\|^2] + \eta \frac{\mu + L}{2\mu L M} (a(\beta - 1) + \beta\sigma^2).
$$

The proof is complete.

<figure><img src="image_7.png" /></figure>

Proof of item 2 of Theorem 1 Let $t \in \mathbb{N}$. Denote by $w^*$ any optimal point of $f$. We have

$$
\|w_{t+1} - w^*\|^2 = \|w_t - w^*\|^2 - 2\eta \langle w_t - w^*, \frac{1}{M} \sum_{i=1}^{M} \mathbf{D}_{t+1}^i \rangle + \eta^2 \left\| \frac{1}{M} \sum_{i=1}^{M} \mathbf{D}_{t+1}^i \right\|^2.
$$

By (A3), H1 and H3, we have,

$$
\begin{align*}
\mathbb{E}[\|w_{t+1} - w^*\|^2] &\le \mathbb{E}[\|w_t - w^*\|^2] - 2\eta \mathbb{E}[\langle w_t - w^*, \nabla f(w_t) \rangle] \\
&\quad + \eta^2 (1 + b \frac{\beta-1}{M}) \mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{\eta^2}{M} (a(\beta-1) + \beta\sigma^2)
\end{align*}
$$

Since $f$ is convex, we have

$$
-2\langle w_t - w^*, \nabla f(w_t) \rangle \le -2(f(w_t) - f^*).
$$

<footnote n="7">⁷Note that our assumption $\eta \le (1 + b \frac{\beta-1}{M})^{-1} \frac{2}{\mu+L}$ implies $\eta < \frac{\mu+L}{2\mu L}$ as soon as $b(\beta-1) > 0$ or $L > \mu$.</footnote>
Hence, using also Proposition 5,

$$
\begin{align*}
\mathbb{E}[\|w_{t+1} - w^*\|^2] &\le \mathbb{E}[\|w_t - w^*\|^2] - 2\eta\mathbb{E}[f(w_t) - f^*] \\
&\quad + 2L\eta^2(1 + b\frac{\beta-1}{M})\mathbb{E}[f(w_t) - f^*] + \frac{\eta^2}{M}(a(\beta-1) + \beta\sigma^2) \\
&= \mathbb{E}[\|w_t - w^*\|^2] + 2\eta(L\eta(1 + b\frac{\beta-1}{M}) - 1)\mathbb{E}[f(w_t) - f^*] + \frac{\eta^2}{M}(a(\beta-1) + \beta\sigma^2).
\end{align*}
$$

Using that $L\eta(1 + b\frac{\beta-1}{M}) \le 1/2$, we obtain

$$
\mathbb{E}[\|w_{t+1} - w^*\|^2] \le \mathbb{E}[\|w_t - w^*\|^2] - \eta \mathbb{E}[f(w_t) - f^*] + 2 + \frac{\eta^2}{M}(a(\beta - 1) + \beta\sigma^2).
$$

Let $T \ge 1$. Summing over $t$, we have, by telescopic sum,

$$
\frac{\eta}{T+1} \sum_{t=0}^{T} \mathbb{E}[f(w_t) - f^*] \le \frac{1}{T+1} \mathbb{E}[\|w_0 - w^*\|^2] + \frac{\eta^2}{M} (a(\beta - 1) + \beta\sigma^2).
$$

The proof is complete since $\mathbb{E}[f(w^{\text{out}})] - f^* = \frac{1}{T+1} \sum_{t=0}^{T} \mathbb{E}[f(w_t) - f^*]$. $\square$

<figure><img src="image_8.png" /></figure>

A.2 Proof of Theorem 1: non-convex case

Proof of item 3 of Theorem 1 Let $t \in \mathbb{N}$. Since $f$ is $L$-smooth, we have, by (B10),

$$
f(w_{t+1}) \le f(w_t) + \langle \nabla f(w_t), w_{t+1} - w_t \rangle + \frac{L}{2} \|w_{t+1} - w_t\|^2.
$$

By H1 and H3, $\mathbb{E}[\mathbf{D}_{t+1}^i | w_t] = \nabla f_i(w_t)$ for all $i \in [M]$. Hence, taking the expectation we obtain

$$
\mathbb{E}[f(w_{t+1})] \le \mathbb{E}[f(w_t)] - \eta \mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{L\eta^2}{2} \mathbb{E}\left[\left\|\frac{1}{M} \sum_{i=1}^{M} \mathbf{D}_{t+1}^{i}\right\|^2\right]
$$

By (A3),

$$
\mathbb{E}[f(w_{t+1})] \le \mathbb{E}[f(w_t)] - \eta \mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{L\eta^2}{2} \left(1 + b\frac{\beta-1}{M}\right) \mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{L\eta^2}{2M} (a(\beta-1) + \beta\sigma^2)
$$

Since $L\eta(1 + b\frac{\beta-1}{M}) \le 1$, we obtain

$$
\frac{\eta}{2} \mathbb{E}[\|\nabla f(w_t)\|^2] \le \mathbb{E}[f(w_t) - f^*] - \mathbb{E}[f(w_{t+1}) - f^*] + \frac{L\eta^2}{2M}(a(\beta - 1) + \beta\sigma^2)
$$

Let $T \ge 1$. Summing over $t$,

$$
\frac{\eta}{2} \sum_{t=0}^{T} \mathbb{E}[\|\nabla f(w_t)\|^2] \le \mathbb{E}[f(w_0) - f^*] + (T+1) \frac{L\eta^2}{2M} (a(\beta-1) + \beta\sigma^2)
$$

Hence,

$$
\frac{1}{T+1} \sum_{t=0}^{T} \mathbb{E}[\|\nabla f(w_t)\|^2] \le \frac{2}{(T+1)\eta} \mathbb{E}[f(w_0) - f^*] + \frac{L\eta}{M}(a(\beta-1) + \beta\sigma^2),
$$

which concludes the proof since $\mathbb{E}[\|\nabla f(w^{\text{out}})\|^2] = \frac{1}{T+1} \sum_{t=0}^{T} \mathbb{E}[\|\nabla f(w_t)\|^2]$. $\square$

<figure><img src="image_9.png" /></figure>
Appendix B Proof of Theorem 2

We start this section with following lemma, which controls the second moment of the compression error.

**Lemma 4** Assume H1'-H2-H3 and that each $f_i$ is differentiable. Then, for all $t \in \mathbb{N}$ and $\eta > 0$,

$$ \mathbb{E}[\|e_{t+1}\|^2] \le \frac{2(1-\delta)b\eta^2}{\delta} \sum_{s=0}^{t} \left(1-\frac{\delta}{2}\right)^{t-s} \mathbb{E}[\|\nabla f(w_s)\|^2] + \frac{2(1-\delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right). \quad (B4) $$

Moreover, for any sequence $(\theta_t)_{t \ge 0}$ satisfying $0 < \theta_t \le \theta_{t+1} \le (1 + \delta/4)\theta_t$ for all $t \in \mathbb{N}$, it holds, for all $T \ge 1$,

$$ \sum_{t=0}^{T} \theta_t \mathbb{E}[\|e_t\|^2] \le \frac{8b\eta^2}{\delta^2} \sum_{t=0}^{T-1} \theta_t \mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{2(1-\delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right) \sum_{t=1}^{T} \theta_t. \quad (B5) $$

*Proof* Let $t \in \mathbb{N}$ and $i \in [M]$. By H1',

$$ \mathbb{E}_C[\|e_{t+1}^i\|^2] \le (1-\delta)\|\eta(g_{t+1}^i)^\perp + e_t^i\|^2. \quad (B6) $$

Defining $(\nabla f_i(w_t))^\perp$ and $(\xi_{t+1}^i(w_t))^\perp$ such that $(\nabla f_i(w_t))^\perp \cdot \bar{\mathbb{D}}_t^i = 0$ and $(\xi_{t+1}^i(w_t))^\perp \cdot \bar{\mathbb{D}}_t^i = 0$, we have

$$ \begin{aligned} \mathbb{E}[\|\eta(g_{t+1}^i)^\perp + e_t^i\|^2|w_t] &= \mathbb{E}[\|\eta(\nabla f_i(w_t))^\perp + \eta(\xi_{t+1}^i(w_t))^\perp + e_t^i\|^2|w_t] \\ &= \|\eta(\nabla f_i(w_t))^\perp + e_t^i\|^2 + \eta^2 \mathbb{E}[\|\xi_{t+1}^i(w_t)\|^2|w_t] \\ &\le (1+\beta)\|e_t^i\|^2 + \left(1+\frac{1}{\beta}\right)\eta^2 \|(\nabla f_i(w_t))^\perp\|^2 + \eta^2 \sigma^2, \quad \forall \beta > 0, \end{aligned} \quad (B7) $$

where, for the last inequality, we used H2 and the inequality $\|\mathbf{a} + \mathbf{b}\|^2 \le (1 + \beta)\|\mathbf{a}\|^2 + (1 + 1/\beta)\|\mathbf{b}\|^2$, $\mathbf{a}, \mathbf{b} \in \mathbb{R}^d, \beta > 0$. Since $\|(\nabla f_i(w_t))^\perp\| \le \|\nabla f_i(w_t)\|$, it follows from (B7) that

$$ \mathbb{E}[\|\eta(g_{t+1}^i)^\perp + e_t^i\|^2] \le (1 + \beta) \mathbb{E}[\|e_t^i\|^2] + \left(1 + \frac{1}{\beta}\right) \eta^2 \mathbb{E}[\|\nabla f_i(w_t)\|^2] + \eta^2 \sigma^2, \quad \forall \beta > 0. \quad (B8) $$

By (B6) and (B8), we have

$$ \mathbb{E}[\|e_{t+1}^i\|^2] \le (1-\delta)(1+\beta)\mathbb{E}[\|e_t^i\|^2] + (1-\delta)\left(1+\frac{1}{\beta}\right)\eta^2\mathbb{E}[\|\nabla f_i(w_t)\|^2] + (1-\delta)\eta^2\sigma^2, \quad \forall \beta > 0. \quad (B9) $$

Let us define the auxiliary sequence $U_t = \frac{1}{M} \sum_{i=1}^{M} \|e_t^i\|^2$. We have, by (B9), for any $\beta > 0$,

$$ \underbrace{\mathbb{E}[U_{t+1}]}_{b_{t+1}} \le \underbrace{(1-\delta)(1+\beta)}_{a} \underbrace{\mathbb{E}[U_t]}_{b_t} + \underbrace{(1-\delta)\left(1+\frac{1}{\beta}\right)}_{c_t} \frac{\eta^2}{M} \sum_{i=1}^{M} \underbrace{\mathbb{E}[\|\nabla f_i(w_t)\|^2]}_{d} + \underbrace{(1-\delta)\eta^2 \sigma^2}_{d}. $$

Since the recursion $b_{t+1} \le ab_t + c_t + d$ leads to $b_{t+1} \le a^{t+1}b_0 + \sum_{s=0}^t a^{t-s}c_s + d \sum_{s=0}^t a^s$, we obtain, using also that $U_0 = 0$,

$$ \mathbb{E}[U_{t+1}] \le (1 - \delta) \left(1 + \frac{1}{\beta}\right) \frac{\eta^2}{M} \sum_{s=0}^{t} \left[(1 - \delta)(1 + \beta)\right]^{t-s} \sum_{i=1}^{M} \mathbb{E}[\|\nabla f_i(w_s)\|^2] $$
$$+(1-\delta)\eta^2\sigma^2 \sum_{s=0}^{t} [(1-\delta)(1+\beta)]^s.$$

Consider now $\beta$ such that $1 + \frac{1}{\beta} \le \frac{2}{\delta}$ and $(1-\delta)(1+\beta) \le 1 - \frac{\delta}{2}$. Using also that $\sum_{s=0}^{t}(1-\delta/2)^s \le \sum_{s=0}^{\infty}(1-\delta/2)^s = \frac{2}{\delta}$, we have,

$$\mathbb{E}[U_{t+1}] \le \frac{2(1-\delta)\eta^2}{\delta M} \sum_{s=0}^{t} \left(1-\frac{\delta}{2}\right)^{t-s} \sum_{i=1}^{M} \mathbb{E}[\|\nabla f_i(w_s)\|^2] + \frac{2(1-\delta)\eta^2\sigma^2}{\delta}.$$

Using H2, we obtain

$$\mathbb{E}[U_{t+1}] \le \frac{2(1-\delta)b\eta^2}{\delta} \sum_{s=0}^{t} \left(1-\frac{\delta}{2}\right)^{t-s} \mathbb{E}[\|\nabla f(w_s)\|^2] + \frac{4(1-\delta)a\eta^2}{\delta^2} + \frac{2(1-\delta)\eta^2\sigma^2}{\delta}.$$

Hence, using Jensen's inequality,

$$\mathbb{E}[\|e_{t+1}\|^2] \le \mathbb{E}[U_{t+1}] \le \frac{2(1-\delta)b\eta^2}{\delta} \sum_{s=0}^{t} \left(1-\frac{\delta}{2}\right)^{t-s} \mathbb{E}[\|\nabla f(w_s)\|^2] + \frac{2(1-\delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right).$$

This proves (B4). Now, let $(\theta_t)_{t \ge 0}$ be as in the statement of the lemma. Let $t \in \mathbb{N}$. We have, since $\theta_{t+1} \le (1+\frac{\delta}{4})^{t+1-s}\theta_s$ for any $s \in \{0, \dots, t+1\}$,

$$\theta_{t+1} \mathbb{E}[\|e_{t+1}\|^2] \le \frac{2(1-\delta)b\eta^2}{\delta} \left(1+\frac{\delta}{4}\right) \sum_{s=0}^{t} \left[ \left(1+\frac{\delta}{4}\right) \left(1-\frac{\delta}{2}\right) \right]^{t-s} \theta_s \mathbb{E}[\|\nabla f(w_s)\|^2] + \frac{2(1-\delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right) \theta_{t+1}.$$

Since $(1-\delta)(1+\delta/4) \le 1$ and $(1+\delta/4)(1-\delta/2) \le 1-\delta/4$,

$$\theta_{t+1} \mathbb{E}[\|e_{t+1}\|^2] \le \frac{2b\eta^2}{\delta} \sum_{s=0}^{t} \left(1-\frac{\delta}{4}\right)^{t-s} \theta_s \mathbb{E}[\|\nabla f(w_s)\|^2] + \frac{2(1-\delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right) \theta_{t+1}.$$

Let $T \ge 1$. Summing over $t$ and using that $e_0 = 0$, we obtain

$$\sum_{t=0}^{T} \theta_t \mathbb{E}[\|e_t\|^2] \le \frac{2b\eta^2}{\delta} \sum_{s=0}^{T-1} \theta_s \mathbb{E}[\|\nabla f(w_s)\|^2] \sum_{t=s}^{T-1} \left(1-\frac{\delta}{4}\right)^{t-s} + \frac{2(1-\delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right) \sum_{t=1}^{T} \theta_t.$$

Since $\sum_{t=0}^{\infty}(1-\delta/4)^t = 4/\delta$, we obtain

$$\sum_{t=0}^{T} \theta_t \mathbb{E}[\|e_t\|^2] \le \frac{8b\eta^2}{\delta^2} \sum_{t=0}^{T-1} \theta_t \mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{2(1-\delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right) \sum_{t=1}^{T} \theta_t.$$

The proof is complete. $\square$

<figure><img src="image_10.png" /></figure>

We are now in position to prove Theorem 2. We first recall a useful result on L-smooth functions.

**Proposition 5** Let $f: \mathbb{R}^d \to \mathbb{R}_+$ be L-smooth. Then, it holds

$$\|\nabla f(x)\|^2 \le 2Lf(x), \quad \forall x \in \mathbb{R}^d.$$
Proof It holds$^8$, for all $x, y \in \mathbb{R}^d$,

$$0 \le f(y) \le f(x) + \langle \nabla f(x), y - x \rangle + \frac{L}{2} \|x - y\|^2 := \varphi_x(y) \quad (B10)$$

Fix $x \in \mathbb{R}^d$. The function $\varphi_x$ attains its minimum at $y = x - \nabla f(x)/L$. Evaluating (B10) with this values yields the desired result. □

## B.1 Proof of Theorem 2: convex case

Let us introduce $\tilde{w}_t = w_t - e_t$ where $e_t = \frac{1}{M} \sum_{i=1}^{M} e_t^i$, for any $t \in \mathbb{N}$.

*Proof of item 1 of Theorem 2.* The proof is divided into two steps. The first step consists in the derivation of (B18). On the second step, we apply the bound of Lemma 4 to conclude the proof.

**Step 1.** Let $t \in \mathbb{N}$. We have

$$\|\tilde{w}_{t+1} - w^*\|^2 = \|\tilde{w}_t - w^*\|^2 - 2\eta\langle g_{t+1}, w_t - w^* \rangle + \eta^2\|g_{t+1}\|^2 + 2\eta\langle g_{t+1}, w_t - \tilde{w}_t \rangle.$$

Hence,

$$\mathbb{E}[\|\tilde{w}_{t+1} - w^*\|^2] = \mathbb{E}[\|\tilde{w}_t - w^*\|^2] - 2\eta\mathbb{E}[\langle\nabla f(w_t), w_t - w^*\rangle] + \eta^2\mathbb{E}[\|g_{t+1}\|^2] + 2\eta\mathbb{E}[\langle\nabla f(w_t), w_t - \tilde{w}_t\rangle].$$

Using (B13) it holds

$$\mathbb{E}[\|g_{t+1}\|^2] \le \mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{\sigma^2}{M}. \quad (B11)$$

Thus,

$$\mathbb{E}[\|\tilde{w}_{t+1} - w^*\|^2] = \mathbb{E}[\|\tilde{w}_t - w^*\|^2] - 2\eta\mathbb{E}[\langle\nabla f(w_t), w_t - w^*\rangle] + \eta^2\mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{\eta^2\sigma^2}{M} \\ + 2\eta\mathbb{E}[\langle\nabla f(w_t), w_t - \tilde{w}_t\rangle]. \quad (B12)$$

By $\mu$-strong convexity of $f$,

$$-2\langle\nabla f(w_t), w_t - w^*\rangle \le -\mu\|w_t - w^*\|^2 - 2(f(w_t) - f^*). \quad (B13)$$

Moreover since $f$ is $L$-smooth, we have by Proposition 5,

$$\|\nabla f(w)\|^2 \le 2L(f(w) - f^*), \quad \forall w \in \mathbb{R}^d. \quad (B14)$$

Using $2\langle \mathbf{a}, \mathbf{b} \rangle \le 2L\|\mathbf{a}\|^2 + \|\mathbf{b}\|^2/(2L)$, we have

$$2\langle\nabla f(w_t), w_t - \tilde{w}_t\rangle \le \frac{1}{2L}\|\nabla f(w_t)\|^2 + 2L\|w_t - \tilde{w}_t\|^2 \le f(w_t) - f^* + 2L\|w_t - \tilde{w}_t\|^2. \quad (B15)$$

Plugging (B13) and (B15) into (B12),

$$\mathbb{E}[\|\tilde{w}_{t+1} - w^*\|^2] \le \mathbb{E}[\|\tilde{w}_t - w^*\|^2] - \eta\mu\mathbb{E}[\|w_t - w^*\|^2] - 2\eta\mathbb{E}[f(w_t) - f^*] \\ + \eta^2\mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{\eta^2\sigma^2}{M} + \eta\mathbb{E}[f(w_t) - f^*] + 2\eta L \mathbb{E}[\|w_t - \tilde{w}_t\|^2]. \quad (B16)$$

Using $\|\mathbf{a} + \mathbf{b}\|^2 \le 2\|\mathbf{a}\|^2 + 2\|\mathbf{b}\|^2$, we have $-\|w_t - w^*\|^2 \le -\frac{1}{2}\|\tilde{w}_t - w^*\|^2 + \|w_t - \tilde{w}_t\|^2$. Hence, (B16) becomes

$$\mathbb{E}[\|\tilde{w}_{t+1} - w^*\|^2] \le \left(1 - \frac{\eta\mu}{2}\right) \mathbb{E}[\|\tilde{w}_t - w^*\|^2] + \eta(2L + \mu)\mathbb{E}[\|w_t - \tilde{w}_t\|^2] \\ - \eta\mathbb{E}[f(w_t) - f^*] + \eta^2\mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{\eta^2\sigma^2}{M}. \quad (B17)$$

<footnote>$^8$See the proof of [35, Theorem 2.1.5].</footnote>
Using (B14) again, (B17) becomes

$$ \begin{aligned} \mathbb{E}[\|\tilde{w}_{t+1} - w^*\|^2] &\leq \left(1 - \frac{\eta\mu}{2}\right) \mathbb{E}[\|\tilde{w}_t - w^*\|^2] + \eta(2L + \mu)\mathbb{E}[\|w_t - \tilde{w}_t\|^2] \\ &\quad - \eta(1 - 2L\eta)\mathbb{E}[f(w_t) - f^*] + \frac{\eta^2\sigma^2}{M}. \end{aligned} $$

Since $\eta \le \frac{1}{4L}$, we obtain

$$ \begin{aligned} \mathbb{E}[\|\tilde{w}_{t+1} - w^*\|^2] &\leq \left(1 - \frac{\eta\mu}{2}\right) \mathbb{E}[\|\tilde{w}_t - w^*\|^2] + \eta(2L + \mu)\mathbb{E}[\|w_t - \tilde{w}_t\|^2] \\ &\quad - \frac{\eta}{2}\mathbb{E}[f(w_t) - f^*] + \frac{\eta^2\sigma^2}{M}. \end{aligned} \quad (B18) $$

**Step 2.** Let $s_t = \mathbb{E}[f(w_t)] - f^*$ and $r_t = \mathbb{E}[\|\tilde{w}_t - w^*\|^2]$. From (B18), we have, for any $\theta_t > 0$,

$$ \frac{\eta}{2}\theta_t s_t \leq (1 - \frac{\eta\mu}{2})\theta_t r_t - \theta_t r_{t+1} + \eta(2L + \mu)\theta_t \mathbb{E}[\|e_t\|^2] + \frac{\eta^2\sigma^2}{M}\theta_t. $$

Let $T \ge 1$. Summing over $t$, we obtain,

$$ \sum_{t=0}^{T} \frac{\eta}{2} \theta_t s_t \le \sum_{t=0}^{T} \left[ \left(1 - \frac{\eta\mu}{2}\right) \theta_t r_t - \theta_t r_{t+1} \right] + \eta(2L + \mu) \sum_{t=0}^{T} \theta_t \mathbb{E}[\|e_t\|^2] + \frac{\eta^2\sigma^2}{M} \sum_{t=0}^{T} \theta_t. $$

Let $\theta_t = (1 - \frac{\eta\mu}{2})^{-t}$. Since $\eta \le \frac{\delta}{L(4+\delta)} \le \frac{2\delta}{\mu(4+\delta)}$ (because $L \ge \mu$ for any $L$-smooth and $\mu$-strongly convex function), we have $\frac{\theta_{t+1}}{\theta_t} \le \frac{1}{1 - \frac{\eta\mu}{2}} \le 1 + \frac{\delta}{4}$. Hence, the sequence $(\theta_t)_{t \ge 0}$ satisfies the assumption of Lemma 4. By (B5),

$$ \begin{aligned} \sum_{t=0}^{T} \frac{\eta}{2} \theta_t s_t \le \sum_{t=0}^{T} \left[ \left(1 - \frac{\eta\mu}{2}\right) \theta_t r_t - \theta_t r_{t+1} \right] + \eta(2L + \mu) \frac{8b\eta^2}{\delta^2} \sum_{t=0}^{T-1} \theta_t \mathbb{E}[\|\nabla f(w_t)\|^2] \\ + \eta(2L + \mu) \frac{2(1-\delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right) \sum_{t=1}^{T} \theta_t + \frac{\eta^2\sigma^2}{M} \sum_{t=0}^{T} \theta_t. \end{aligned} $$

Since $\mathbb{E}[\|\nabla f(w_t)\|^2] \le 2L s_t$ (by (B14)) and since $\eta$ is such that $(2L + \mu) \frac{16bL\eta^2}{\delta^2} \le \frac{2}{5}$, we have

$$ \begin{aligned} \sum_{t=0}^{T} \frac{\eta}{2} \theta_t s_t \le \sum_{t=0}^{T} \left[ \left(1 - \frac{\eta\mu}{2}\right) \theta_t r_t - \theta_t r_{t+1} \right] + \frac{2}{5}\eta \sum_{t=0}^{T-1} \theta_t s_t \\ + \eta(2L + \mu) \frac{2(1-\delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right) \sum_{t=1}^{T} \theta_t + \frac{\eta^2\sigma^2}{M} \sum_{t=0}^{T} \theta_t. \end{aligned} $$

Denoting $\Theta_T = \sum_{t=0}^{T} \theta_t$, we obtain

$$ \frac{1}{\Theta_T} \sum_{t=0}^{T} \theta_t s_t \le \frac{10}{\eta \Theta_T} \sum_{t=0}^{T} \left[ \left(1 - \frac{\eta \mu}{2}\right) \theta_t r_t - \theta_t r_{t+1} \right] + 10(2L + \mu) \frac{2(1 - \delta)\eta^2}{\delta} \left( \frac{2a}{\delta} + \sigma^2 \right) + 10 \frac{\eta \sigma^2}{M}. $$

Since $(1 - \frac{\eta\mu}{2})\theta_t = \theta_{t-1}$ (which also holds for $t = 0$), we have, by telescopic sum,

$$ \begin{aligned} \frac{1}{\Theta_T} \sum_{t=0}^{T} \theta_t s_t &\le \frac{10}{\eta \Theta_T} \sum_{t=0}^{T} [\theta_{t-1} r_t - \theta_t r_{t+1}] + 10(2L + \mu) \frac{2(1 - \delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right) + 10 \frac{\eta \sigma^2}{M} \\ &\le \frac{10}{\eta \Theta_T} \theta_{-1} r_0 + 10(2L + \mu) \frac{2(1 - \delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right) + 10 \frac{\eta \sigma^2}{M}. \end{aligned} $$
Now, we use that $\Theta_T \ge \theta_T$ to obtain

$$ \frac{1}{\Theta_T} \sum_{t=0}^{T} \theta_t s t \le \frac{10}{\eta} \left(1 - \frac{\eta\mu}{2}\right)^{T+1} \mathbb{E}[\|w_0 - w^*\|^2] + 10(2L + \mu) \frac{2(1 - \delta)\eta^2}{\delta} \left(\frac{2a}{\delta} + \sigma^2\right) + 10 \frac{\eta\sigma^2}{M}. $$

This completes the proof since $\frac{1}{\Theta_T} \sum_{t=0}^{T} \theta_t s t = \mathbb{E}[f(w^{\text{out}})] - f^*$. $\square$

*Proof of item 2 of Theorem 2.* The proof follows the proof of item 1 of Theorem 2. In particular, the computations of Step 1 are still valid when $\mu = 0$. In Step 2, we apply Lemma 4 with $\theta_t = 1$. $\square$

## B.2 Proof of Theorem 2: non-convex case

*Proof of item 3 of Theorem 2.* The proof is divided into two steps. The first step consists in the derivation of (B19). On the second step, we apply the bound of Lemma 4 to conclude the proof.

**Step 1.** Let $t \in \mathbb{N}$. By (B10),

$$ \begin{aligned} f(\tilde{w}_{t+1}) &\le f(\tilde{w}_t) + \langle \nabla f(\tilde{w}_t), \tilde{w}_{t+1} - \tilde{w}_t \rangle + \frac{L}{2} \|\tilde{w}_{t+1} - \tilde{w}_t\|^2 \\ &= f(\tilde{w}_t) - \eta \langle \nabla f(\tilde{w}_t), g_{t+1} \rangle + \frac{L}{2} \eta^2 \|g_{t+1}\|^2 \end{aligned} $$

Taking the expectancy and using (B11),

$$ \begin{aligned} \mathbb{E}[f(\tilde{w}_{t+1})] &\le \mathbb{E}[f(\tilde{w}_t)] - \eta \mathbb{E}[\langle \nabla f(\tilde{w}_t), \nabla f(w_t) \rangle] + \frac{L}{2} \eta^2 \mathbb{E}[\|g_{t+1}\|^2] \\ &\le \mathbb{E}[f(\tilde{w}_t)] - \eta \mathbb{E}[\langle \nabla f(\tilde{w}_t), \nabla f(w_t) \rangle] + \frac{L}{2} \eta^2 \left( \mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{\sigma^2}{M} \right) \end{aligned} $$

Using $\langle \mathbf{a}, \mathbf{b} \rangle \le \|\mathbf{a}\|^2/2 + \|\mathbf{b}\|^2/2$,

$$ \begin{aligned} \mathbb{E}[f(\tilde{w}_{t+1})] &\le \mathbb{E}[f(\tilde{w}_t)] - \eta \mathbb{E}[\langle \nabla f(\tilde{w}_t) - \nabla f(w_t) + \nabla f(w_t), \nabla f(w_t) \rangle] + \frac{L}{2} \eta^2 \left( \mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{\sigma^2}{M} \right) \\ &\le \mathbb{E}[f(\tilde{w}_t)] + \frac{\eta}{2}(L\eta - 1)\mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{\eta}{2}\mathbb{E}[\|\nabla f(\tilde{w}_t) - \nabla f(w_t)\|^2] + \frac{\eta^2 L \sigma^2}{2M} \\ &\le \mathbb{E}[f(\tilde{w}_t)] + \frac{\eta}{2}(L\eta - 1)\mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{\eta L^2}{2}\mathbb{E}[\|e_t\|^2] + \frac{\eta^2 L \sigma^2}{2M} \end{aligned} $$

where we used (4) for the last inequality. Since $\eta \le \frac{1}{2L}$ we obtain

$$ \mathbb{E}[f(\tilde{w}_{t+1})] \le \mathbb{E}[f(\tilde{w}_t)] - \frac{\eta}{4} \mathbb{E}[\|\nabla f(w_t)\|^2] + \frac{\eta L^2}{2} \mathbb{E}[\|e_t\|^2] + \frac{\eta^2 L \sigma^2}{2M}. \quad (B19) $$

**Step 2.** Let $T \ge 1$. From (B19), we have

$$ \frac{\eta}{4} \sum_{t=0}^{T} \mathbb{E}[\|\nabla f(w_t)\|^2] \le \sum_{t=0}^{T} \left[ \mathbb{E}[f(\tilde{w}_t) - f^*] - \mathbb{E}[f(\tilde{w}_{t+1}) - f^*] \right] + \frac{\eta L^2}{2} \sum_{t=0}^{T} \mathbb{E}[\|e_t\|^2] + (T+1) \frac{\eta^2 L \sigma^2}{2M}. $$

Let us now apply Lemma 4 with weights $\theta_t = 1$:

$$ \frac{\eta}{4} \sum_{t=0}^{T} \mathbb{E}[\|\nabla f(w_t)\|^2] \le \mathbb{E}[f(\tilde{w}_0) - f^*] + \frac{4b\eta^3 L^2}{\delta^2} \sum_{t=0}^{T-1} \mathbb{E}[\|\nabla f(w_t)\|^2] $$
$$ + \frac{(1 - \delta)T\eta^3 L^2}{\delta} \left( \frac{2a}{\delta} + \sigma^2 \right) + (T + 1)\frac{\eta^2 L\sigma^2}{2M}. $$

Since $\frac{4b\eta^2L^2}{\delta^2} \le \frac{1}{8}$,

$$ \frac{\eta}{8} \sum_{t=0}^{T} \mathbb{E}[\|\nabla f(w_t)\|^2] \le \mathbb{E}[|f(\tilde{w}_0) - f^*|] + \frac{(1 - \delta)T\eta^3 L^2}{\delta} \left( \frac{2a}{\delta} + \sigma^2 \right) + (T + 1)\frac{\eta^2 L\sigma^2}{2M}. $$

Hence,

$$ \frac{1}{T+1} \sum_{t=0}^{T} \mathbb{E}[\|\nabla f(w_t)\|^2] \le \frac{8}{(T+1)\eta} \mathbb{E}[|f(\tilde{w}_0) - f^*|] + \frac{8(1 - \delta)\eta^2 L^2}{\delta} \left( \frac{2a}{\delta} + \sigma^2 \right) + \frac{8\eta L\sigma^2}{2M}. $$

□

# Appendix C Experimental details and Additional experiments

In this section we start by giving implementation details in Subsection C.1 and then in the following subsections provide further experiments.

## C.1 Experimental details

### C.1.1 Hardware and software.

All experiments were conducted on an internal cluster machine equipped with an Intel Xeon Gold 5320 CPU (104 cores, 2.20 GHz), 500 GB of RAM, and a single NVIDIA A30 GPU with 24 GB of memory (driver version 545.23.08, CUDA version 12.3). The software environment consisted of Python 3.9.19 and PyTorch 2.3, running on Debian GNU/Linux 12 (Bookworm). Experimental run took approximately 1 hour on average with 3 clients on 10 processes, with the most computationally intensive run requiring up to 48 hours. All experiments were performed on our institutional infrastructure on CPU; no cloud computing resources were used. Reproducing the CIFAR-10 experiments with 3 clients and a batch size of 128 requires 24 GB of RAM.

### C.1.2 Hyperparameters

* Early stopping: patience of 10 epochs and a minimum delta of 0.001.

* Batch size: 128 per client.

* Learning rate scheduler: PyTorch's ReduceLROnPlateau<fnref n="9" /> starting from 0.1, with a patience of 2 epochs, a decay factor of 0.5, and a minimum learning rate of 0.001.

### C.1.3 Algorithms parameter

Based on the observed trade-offs between convergence speed, communication cost, and stability across both datasets, the values $k = 0.01$ and $K = 3$ appear to offer a good compromise. These settings strike a strong balance between training efficiency and

<footnote n="9">⁹https://pytorch.org/docs/2.3/generated/torch.optim.lr_scheduler.ReduceLROnPlateau.html</footnote>
robustness. We note that although the algorithms differ in efficiency, they all converge to reasonable minima. Moreover, incorporating the Error Feedback mechanism consistently improves performance-an expected outcome given the use of biased compressors, as previously discussed. On the CIFAR-10 experiments for selecting *K* (see the two rightmost plots in Figure C1), one might be surprised by the increase in test loss at the end of training for Algorithm 2. This rise is due to overfitting, as the training loss continues to decrease monotonically (see Appendix C). The reason the algorithm was not stopped earlier lies in the early stopping criterion (specifically the patience). Naturally, had we optimized early stopping specifically for Algorithm 2, more favorable stopping conditions would have been chosen. Note that the curves start at different points, as the x-axis value of the first point corresponds to the communication cost after the first epoch.

<figure><img src="image_11.png" /><figcaption>Fig. C1 Selection of *k* (Top-*k*) and *K* for Algorithms 1 and 2, for *M* = 3 clients.</figcaption></figure>

### C.1.4 Algorithms evaluated in our experiments.

Algorithm 3 corresponds to the standard FedAvg algorithm with gradient compression. Algorithm 4 is a variant that incorporates the compression error using the well-known Error Feedback mechanism. All our experiments are done setting $\zeta = 0.75$. Algorithm 5
implement the EF21 algorithm from [8]. In our experiments, we observed that EF21
performs poorly on large models (see the analysis provided in Subsection C.5). To
address this limitation, we introduce a forgetting parameter $\gamma \in (0, 1)$, which improves
the robustness of the method (see Algorithm 6).

Table C2 shows the first descent directions for Algorithms 5 and 6. This illustrates that in classical EF21, the compressed version of the initial gradients—and their propagation—persist across all descent directions $D_k^i$, whereas in our modified version, their influence gradually vanishes at a rate governed by $\gamma$.

A similar effect is observed for DIANA (Algorithm 7) and its modified counterpart with forgetting (Algorithm 8). Our experiments are done with hyperparameters $\alpha = 0.9$ and $\beta = 0.1$ (see evaluation for different values of $\alpha$ and $\beta$ in Subsection C.5).

<caption>**Algorithm 3 FedAvg with compression**</caption>

1: **Initialization:** $w_0 \in \mathbb{R}^d$.
2: **for** $t = 0, \dots, T$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;**for** Each client $i$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Receive $w_t$.
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compute Stochastic Gradient $g_{t+1}^i$.
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Send $\mathcal{C}(g_{t+1}^i)$ to the Central Server.
7: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
8: **Central Server:**
9: &nbsp;&nbsp;&nbsp;&nbsp;$$w_{t+1} = w_t - \frac{\eta}{M} \sum_{i=1}^{M} \mathcal{C}(g_{t+1}^i).$$
10: **end for**

<caption>**Algorithm 4 FedAvg with Error Feedback**</caption>

1: **Initialization:** $w_0 \in \mathbb{R}^d$, $e_0^i = 0 \in \mathbb{R}^d$, $\forall i \in [M]$. $\zeta \in (0, 1]$.
2: **for** $t = 0, \dots, T$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;**for** each client $i$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Receive $w_t$.
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compute Stochastic Gradient $g_{t+1}^i$.
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\tilde{g}_{t+1}^i = g_{t+1}^i + \zeta e_t^i$. ▷ Add the previous compression error
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$e_{t+1}^i = \tilde{g}_{t+1}^i - \mathcal{C}(\tilde{g}_{t+1}^i)$. ▷ Update the compression error
8: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
9: **end for**
10: **Central Server:**
11: $$w_{t+1} = w_t - \frac{\eta}{M} \sum_{i=1}^{M} \mathcal{C}(\tilde{g}_{t+1}^i)$$
12: **end for**
**Algorithm 5 EF21 [8]**

1: Initialization: $D_0^i = 0 \in \mathbb{R}^d$

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

3: for Each client $i \in [M]$ do

4: Receive $w_t$

5: Compute Stochastic Gradient $g_{t+1}^i$

6: $M_{t+1}^i = C(g_{t+1}^i - D_t^i)$

7: $D_{t+1}^i = D_t^i + M_{t+1}^i$

▷ Update local direction of descent

8: Send $M_{t+1}^i$ to the Central Server

9: end for

10: Central Server:

11: $D_{t+1}^i = D_t^i + M_{t+1}^i$

12: $w_{t+1} = w_t - \frac{\eta}{M} \sum_{i=1}^{M} D_{t+1}^i$

13: end for

**Algorithm 6 EF21 with parameter $\gamma \in (0, 1)$**

1: Initialization: $D_0^i = 0 \in \mathbb{R}^d$

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

3: for Each client $i \in [M]$ do

4: Receive $w_t$

5: Compute Stochastic Gradient $g_{t+1}^i$

6: $M_{t+1}^i = C(g_{t+1}^i - \gamma D_t^i)$

7: $D_{t+1}^i = \gamma D_t^i + M_{t+1}^i$

▷ Update local direction of descent

8: Send $M_{t+1}^i$ to the Central Server

9: end for

10: Central Server:

11: $D_{t+1}^i = \gamma D_t^i + M_{t+1}^i$

12: $w_{t+1} = w_t - \frac{\eta}{M} \sum_{i=1}^{M} D_{t+1}^i$

13: end for
**Algorithm 7 DIANA [26]**

1: Initialization: $h_0^i = h_0 = D_0 = 0 \in \mathbb{R}^d$

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

3: for Each client $i \in [M]$ do

4: Receive $w_t$

5: Compute Stochastic Gradient $g_{t+1}^i$

6: $M_{t+1}^i = C(g_{t+1}^i - h_t^i)$

7: $h_{t+1}^i = h_t^i + \alpha M_{t+1}^i$ ▷ Update memory

8: Send $M_{t+1}^i$ to the Central Server

9: end for

10: Central Server:

11: $M_{t+1} = \frac{1}{M} \sum_{i=1}^{M} M_{t+1}^i$

12: $D_{t+1} = \beta D_t + h_t + M_{t+1}$ ▷ Compute the descent direction with momentum when $\beta > 0$

13: $h_{t+1} = h_t + \alpha M_{t+1}$ ▷ Update memory

14: $w_{t+1} = w_t - \eta D_{t+1}$

15: end for

**Algorithm 8 DIANA with parameter $\gamma \in (0, 1)$**

1: Initialization: $h_0^i = h_0 = D_0 = 0 \in \mathbb{R}^d$

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

3: for Each client $i \in [M]$ do

4: Receive $w_t$

5: Compute Stochastic Gradient $g_{t+1}^i$

6: $M_{t+1}^i = C(g_{t+1}^i - \gamma h_t^i)$

7: $h_{t+1}^i = \gamma h_t^i + \alpha M_{t+1}^i$ ▷ Update memory

8: Send $M_{t+1}^i$ to the Central Server

9: end for

10: Central Server:

11: $M_{t+1} = \frac{1}{M} \sum_{i=1}^{M} M_{t+1}^i$

12: $D_{t+1} = \beta D_t + \gamma h_t + M_{t+1}$ ▷ Compute the descent direction with momentum when $\beta > 0$

13: $h_{t+1} = \gamma h_t + \alpha M_{t+1}$ ▷ Update memory

14: $w_{t+1} = w_t - \eta D_{t+1}$

15: end for

### C.1.5 Variability across runs.

To assess the stability of our method, we report the test cross-entropy loss over 10 independent runs with different random seeds, measured at the end of training.

We observe that Algorithm 2 has a lower standard deviation compared to the other algorithms.
<table><caption>**Table C1** Standard deviation of the test loss where $C$=Top-0.01.</caption><thead><tr><th>Algorithm</th><th>MNIST</th><th>CIFAR-10</th></tr></thead><tbody><tr><td>no compression</td><td>0.0039</td><td>0.0423</td></tr><tr><td>Algorithm 1</td><td>0.0257</td><td>0.0284</td></tr><tr><td>Algorithm 2</td><td>0.0045</td><td>0.0149</td></tr><tr><td>Algorithm 3</td><td>0.0201</td><td>0.0211</td></tr><tr><td>Algorithm 4</td><td>0.0074</td><td>0.0143</td></tr><tr><td>Algorithm 6</td><td>0.0138</td><td>0.0221</td></tr><tr><td>Algorithm 8</td><td>0.0140</td><td>0.0358</td></tr></tbody></table>

<table><caption>**Table C2** Comparison of the first descent direction between Algorithms 5 and 6.</caption><thead><tr><th>Iteration k</th><th>D<sup>i</sup><sub>k</sub> (Alg. 5)</th><th>D<sup>i</sup><sub>k</sub> (Alg. 6)</th></tr></thead><tbody><tr><td>1</td><td>C(g<sup>i</sup><sub>1</sub>)</td><td>C(g<sup>i</sup><sub>1</sub>)</td></tr><tr><td>2</td><td>C(g<sup>i</sup><sub>1</sub>) + C(g<sup>i</sup><sub>2</sub> - C(g<sup>i</sup><sub>1</sub>))</td><td>γC(g<sup>i</sup><sub>1</sub>) + C(g<sup>i</sup><sub>2</sub> - γC(g<sup>i</sup><sub>1</sub>))</td></tr><tr><td>3</td><td>C(g<sup>i</sup><sub>1</sub>) + C(g<sup>i</sup><sub>2</sub> - C(g<sup>i</sup><sub>1</sub>)) + C(g<sup>i</sup><sub>3</sub> - C(g<sup>i</sup><sub>1</sub>) - C(g<sup>i</sup><sub>2</sub> - C(g<sup>i</sup><sub>1</sub>)))</td><td>γ<sup>2</sup>C(g<sup>i</sup><sub>1</sub>) + γC(g<sup>i</sup><sub>2</sub> - γC(g<sup>i</sup><sub>1</sub>)) + C(g<sup>i</sup><sub>3</sub> - γ<sup>2</sup>C(g<sup>i</sup><sub>1</sub>) - γC(g<sup>i</sup><sub>2</sub> - γC(g<sup>i</sup><sub>1</sub>)))</td></tr></tbody></table>

## C.2 Overfitting on the Training Set for CIFAR-10

As noticed in Figure C1, 2 and 3, we can see a rising loss on the test set. This behavior is a sign of overfitting. As can be seen, the training loss decreases monotonically, confirming that the model continues to fit the training data while generalization performance degrades.

<figure><img src="image_12.png" /><figcaption>**Fig. C2** Selection of $K$ for Algorithms 1 and 2, for $M = 3$ clients on train set.</figcaption></figure>
<figure><img src="image_13.png" /><figcaption>**Fig. C3** Comparison of Algorithms 1 and 2 with FedAvg with compression, EF, EF21, and DIANA for $M = 3$ clients on train set.</figcaption></figure>

## C.3 Additional Experiments with Uplink and Downlink Communication Costs

In this subsection, we present the same experiments as in Figure 2, but considering only the uplink communication cost (Figure C4) or only the downlink communication cost (Figure C5).

Regarding the downlink communication cost, note that the central server only sends the difference $w_{t+1} - w_t$ (that is, only the values and indices of $w_{t+1}$ that differ from $w_t$).
<figure><img src="image_14.png" /><figcaption>**Fig. C4** Uplink communication cost with $M = 3$ clients. The x-axis represents the total communication cost of the clients (i.e., 3 times the communication cost per client).</figcaption></figure>
<figure><img src="image_15.png" /><figcaption>Fig. C5 Downlink communication cost with $M = 3$ clients.</figcaption></figure>

## C.4 Accuracy

In Figure C6 (resp. Figure C7), we report both training and test accuracy for the MNIST (resp. CIFAR-10) dataset.
<figure><img src="image_16.png" /><figcaption>**Fig. C6** Accuracy on MNIST dataset with *M* = 3 clients. **First line:** Total communication cost. **Second line:** Uplink communication cost only. **Third line:** Donwlink communication cost only.</figcaption></figure>

## C.5 Evaluation of EF21 and DIANA under different hyperparameters

As already mentioned in Section 5, it was observed in [25] that Algorithm 5 is particularly sensitive to the batch size. However, on our models, none of the considered batch sizes yielded favorable results, as shown in Figure C8. For this reason, all comparisons involving the EF21 method in our experiments use Algorithm 6 instead of Algorithm 5.
<figure><img src="image_17.png" /><figcaption>**Fig. C7** Accuracy on CIFAR-10 dataset with $M = 3$ clients. **First line:** Total communication cost. **Second line:** Uplink communication cost only. **Third line:** Donwlink communication cost only.</figcaption></figure>

For DIANA, a similar observation holds. However, we also tuned the relevant hyperparameters of this algorithm, as shown in Figures C8 and C9.
<figure><img src="image_18.png" /><figcaption>Fig. C8 EF21 (Alg. 5) under different batch sizes *B* with *M* = 3 clients.</figcaption></figure>
<figure><img src="image_19.png" /><figcaption>Fig. C9 DIANA (Alg. 7) on MNIST under different batch sizes *B* and hyperparameters, with *M* = 3 clients.</figcaption></figure>
<figure><img src="image_20.png" /><figcaption>**Fig. C10 DIANA (Alg. 7) on MNIST** under different batch sizes *B* and hyperparameters, with *M* = 3 clients.</figcaption></figure>