# Differential error feedback for communication-efficient decentralized learning

Roula Nassif, Stefan Vlaski, Marco Carpentiero, Vincenzo Matta, Ali Sayed

► To cite this version:

Roula Nassif, Stefan Vlaski, Marco Carpentiero, Vincenzo Matta, Ali Sayed. Differential error feedback for communication-efficient decentralized learning. IEEE Transactions on Signal Processing, 2025, 73, pp.1905-1921. 10.1109/TSP.2025.3564416. hal-05227572

HAL Id: hal-05227572

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

Submitted on 28 Aug 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_1.png" /></figure>
# Differential error feedback for communication-efficient decentralized learning

Roula Nassif, Stefan Vlaski, Marco Carpentiero, Vincenzo Matta, Ali H. Sayed

**Abstract**—Communication-constrained algorithms for decentralized learning and optimization rely on local updates coupled with the exchange of compressed signals. In this context, *differential quantization* is an effective technique to mitigate the negative impact of compression by leveraging correlations between successive iterates. In addition, the use of *error feedback*, which consists of incorporating the compression error into subsequent steps, is a powerful mechanism to compensate for the bias caused by the compression. Under error feedback, performance guarantees in the literature have so far focused on algorithms employing a fusion center or a special class of contractive compressors that cannot be implemented with a finite number of bits. In this work, we propose a new *decentralized communication-efficient learning approach* that blends differential quantization with error feedback. The approach is specifically tailored for decentralized learning problems where agents have individual risk functions to minimize subject to subspace constraints that require the minimizers across the network to lie in low-dimensional subspaces. This constrained formulation includes consensus or single-task optimization as special cases, and allows for more general task relatedness models such as multitask smoothness and coupled optimization. We show that, under some general conditions on the compression noise, and for sufficiently small step-sizes $\mu$, the resulting communication-efficient strategy is stable both in terms of mean-square error and average bit rate: by reducing $\mu$, it is possible to keep the *estimation errors small (on the order of $\mu$) without increasing indefinitely the bit rate as $\mu \to 0$*. The results establish that, in the *small step-size regime* and with a *finite number of bits*, it is possible to attain the performance achievable in the absence of compression.

**Index Terms**—Error feedback, differential quantization, compression operator, decentralized subspace projection, single-task learning, multitask learning, mean-square-error analysis, bit rate analysis.

## I. INTRODUCTION

Data is increasingly being collected in a distributed and streaming manner, in an environment where communication and data privacy are becoming major concerns. In this context, centralized learning schemes with fusion centers tend to be replaced by new paradigms, such as federated and decentralized learning [2]–[8]. In these approaches, each participating device

The work of R. Nassif was supported in part by ANR JCJC grant ANR-22-CE23-0015-01 (CEDRO project) and by the French government through the France 2030 investment plan managed by the ANR, as part of the initiative of Excellence Université Côte d'Azur under reference number ANR-15-IDEX-01 (ODER project).

A short conference version of this work appears in [1]. This extended version includes proofs, derivations, and new results.

R. Nassif is with Université Côte d'Azur, I3S Laboratory, CNRS, France (email: roula.nassif@unice.fr). S. Vlaski is with Imperial College London, UK (e-mail: s.vlaski@imperial.ac.uk). M. Carpentiero and V. Matta are with University of Salerno, Italy (e-mail: {mcarpentiero,vmatta}@unisa.it). A. H. Sayed is with the Institute of Electrical and Micro Engineering, EPFL, Switzerland (e-mail: ali.sayed@epfl.ch).

This paper has supplementary downloadable material available at http://ieeexplore.ieee.org, provided by the authors. The material primarily consists of detailed extended proofs of the Lemmas and Theorems presented in the paper.

(which is referred to as *agent* or *node*) has a local training dataset, which is never uploaded to the server. The training data is kept locally on users' devices, and the devices act as agents performing local computations to learn global models of interest. In applications where communication with a server becomes a bottleneck, *decentralized topologies* (where agents only communicate with their neighbors) become attractive alternatives to federated topologies (where a server connects with all remote devices). These decentralized implementations reduce the communication burden since model updates are exchanged locally between agents without relying on a central coordinator [6]–[10]. Studies have shown that decentralized approaches can be as efficient as the centralized schemes when considering, for instance, steady-state mean-square-error performance [6], [11].

In traditional decentralized implementations, agents need to exchange (possibly *high-dimensional* and *dense*) parameter vectors at every iteration of the learning algorithm, leading to high communication costs. In modern distributed networks comprising a massive number of devices (e.g., thousands of participating smartphones), communication can be slower than local computation by many orders of magnitude (due to limited resources such as energy and bandwidth). Designers are typically limited by an upload bandwidth of 1MB/s or less [2]. Therefore, in practice, if not addressed adequately, the scarcity of the communication resources may limit the application of decentralized learning [12]. A variety of methods have been proposed to reduce the communication overhead of decentralized learning. These methods can be divided into two main categories. In the first one, communication is reduced by skipping communication rounds while performing a certain number of local updates in between [2], [13], [14], thus trading-off communication overhead, computation, and learning performance. In the second one, information is compressed by employing either quantization (e.g., employing dithered quantization [15]), sparsification (e.g., employing top-k or rand-k sparsifiers [9]), or both (e.g., employing top-k combined with dithering [16]), before being exchanged. Compression operators and learning algorithms are then jointly designed to prevent the compression error from accumulating during the learning process and from significantly deteriorating the performance of the decentralized approach [9], [10], [17]–[28]. Other works propose to combine the aforementioned two categories to further reduce the communication cost [29], [30].

In this work, we introduce a new communication-efficient approach for decentralized learning. The approach exploits *differential quantization* and *error feedback* to mitigate the negative impact of compressed communications on the learning performance. *Differential quantization* is a common technique for mitigating the impact of compression by leveraging
correlations between successive iterates. In this case, instead of communicating compressed versions of the iterates, agents communicate compressed versions of the differences between current estimates and their predictions based on previous iterations. Several recent works have focused on studying the benefits of differential quantization in the context of decentralized learning. For instance, the work [10] shows that, in a diminishing step-size regime, differential quantization can reduce communication overhead without degrading much the learning rate. In [31], it is shown that decentralized learning can achieve the same convergence rate as centralized learning in non-convex settings, under very high accuracy constraints on the compression operators. The constraints are relaxed in the study [26], which also assumes decentralized non-convex optimization. The work [29] studies the benefits of differential quantization and event-triggered communications. The analysis shows that compression affects slightly the convergence rate when gradients are bounded. Similar results are established in [30] under a weaker bounded gradient dissimilarity assumption, and in [23] in the context of decentralized learning over directed graphs. The works [20], [21], [25] study the benefits of differential quantization without imposing any assumptions on the gradients, and by allowing for the use of combination matrices<fnref n="1" /> that are not symmetric [20], [21] or that have matrix valued entries [25]. While the works [10], [20], [21], [23], [25], [26], [29]–[31] focus on studying primal stochastic optimization decentralized techniques (that are based on propagating and estimating primal variables), the works [9], [27], [28] consider primal-dual decentralized techniques and the work [24] considers deterministic optimization.

Error feedback, on the other hand, consists of locally storing the compression error (i.e., the difference between the input and output of the compression operator), and incorporating it into the next iteration. This technique has been previously employed for stochastic gradient descent (SGD) algorithms. Specifically, it has been applied to the SignSGD algorithm in the single-agent context under 1-bit quantization [32], and to the distributed SGD to handle biased compression operators [16]. In the context of decentralized learning, the DeepSqueeze approach in [33] uses error feedback without differential quantization.

In the current work, we show how to blend differential quantization and error feedback in order to obtain a communication-efficient decentralized learning algorithm. First, we describe in Sec. II the decentralized learning framework and the class of compression operators considered in the study. While most existing works on decentralized learning with compressed communications are focused on single-task or consensus algorithm design, the design in the current work goes beyond this traditional focus by allowing for both single-task and multitask implementations. In single-task learning, nodes collaborate to reach an agreement on a single parameter vector (also referred to as task or objective) despite having different local data distributions. Multitask learning, on the other hand, involves training multiple tasks simultaneously

and exploiting their intrinsic relationship. This approach offers several advantages, including improved network performance, especially when the tasks share commonalities in their underlying features [8]. Compared with previous works, another contribution in the current study is the consideration of a general class of compression operators. Specifically, rather than being confined to the set of probabilistic unbiased operators as in [9], [20], [21], [25], [28], [31], we allow for the use of biased (possibly deterministic) compression operators. Moreover, while most existing works assume that some quantities (e.g., the norm or some components of the vector to be quantized) are represented with very high precision (e.g., machine precision) and neglect the associated quantization error [9], [10], [20], [21], [23], [26]–[31], [33], the current work incorporates realistic quantization models into the compression process and shows how to effectively manage the errors and minimize their impact on the learning performance. In Secs. III and IV, we present and analyze the proposed learning strategy. While there exist several theoretical works investigating communication-efficient learning, the analysis in the current work is more general in the following sense. First, it considers a general class of compression schemes. Moreover, unlike the studies in [9], [10], [24], [26]–[31], [33], it does not require the combination matrices to be symmetric. We further allow the entries of the combination matrix to be matrix-valued (as opposed to scalar valued as in traditional implementations) in order to solve general multitask optimization problems. Finally, we do not assume bounded gradients as in [10], [23], [27], [29], [33]. We establish in Sec. IV the mean-square-error stability of the proposed decentralized communication-efficient approach. In addition to investigating the mean-square-error stability, we characterize the steady-state average bit rate of the proposed approach when variable-rate quantizers are used. The analysis shows that, by properly designing the quantization operators, the iterates generated by the proposed approach lead to small estimation errors on the order of the step-size $\mu$ (as it happens in the ideal case without compression), while concurrently guaranteeing a bounded average bit rate as $\mu \to 0$. Our theoretical findings show that, in the small step-size regime, the proposed strategy attains the performance achievable in the absence of compression, despite the use of a finite number of bits. This demonstrates the effectiveness of the approach in maintaining performance while reducing communication overhead. Finally, we present in Sec. V experimental results illustrating the theoretical findings and showing that blending differential compression and error feedback can achieve superior performance compared to state-of-the-art baselines.

**Notation:** All vectors are column vectors. Random quantities are denoted in boldface. Matrices are denoted in uppercase letters while vectors and scalars are denoted in lowercase letters. The symbol $(\cdot)^\top$ denotes matrix transposition. The operator $\text{col}\{\cdot\}$ stacks the column vector entries on top of each other. The operator $\text{diag}\{\cdot\}$ forms a matrix from block arguments by placing each block immediately below and to the right of its predecessor. The symbol $\otimes$ denotes the Kronecker product. The ceiling and floor functions are denoted by $\lceil \cdot \rceil$ and $\lfloor \cdot \rceil$, respectively. The $M \times M$ identity matrix is denoted

<footnote n="1">¹As we will see, combination matrices in decentralized learning are used to control the exchange of information between neighboring agents.</footnote>
by $I_M$. The abbreviation “w.p.” is used for “with probability”. The notation $\alpha = O(\mu)$ signifies that there exist two positive constants $c$ and $\mu_0$ such that $|\alpha| \le c\mu$ for all $\mu \le \mu_0$. Vectors or matrices of all zeros are denoted by 0.

## II. PROBLEM SETUP

### A. Decentralized optimization under subspace constraints

We consider a connected graph (or network) $\mathcal{G}(\mathcal{V}, \mathcal{E})$, where $\mathcal{V}$ and $\mathcal{E}$ denote the set of $K$ agents or nodes (labeled $k=1, \dots, K$) and the set of possible communication links or edges, respectively. Let $w_k \in \mathbb{R}^{M_k}$ denote some parameter vector at agent $k$ and let $w = \text{col}\{w_1, \dots, w_K\}$ denote the $M$-dimensional vector (where $M = \sum_{k=1}^K M_k$) collecting the parameter vectors from across the network. We associate with each agent $k$ a differentiable convex risk $J_k(w_k) : \mathbb{R}^{M_k} \to \mathbb{R}$, expressed as the expectation of some loss function $L_k(\cdot)$ and written as $J_k(w_k) = \mathbb{E}L_k(w_k; \mathbf{y}_k)$, where $\mathbf{y}_k$ denotes the random data at agent $k$. The expectation is computed relative to the distribution of the local data. In the stochastic setting, when the data distribution is unknown, the risks $J_k(\cdot)$ and their gradients $\nabla_{w_k} J_k(\cdot)$ are unknown. In this case, instead of using the true gradient, it is common to use approximate gradient vectors based on the loss functions such as $\nabla_{w_k} J_k(w_k) = \nabla_{w_k} L_k(w_k; \mathbf{y}_{k,i})$ where $\mathbf{y}_{k,i}$ represents the data observed at iteration $i$ [6], [34].

In traditional single-task or consensus problems, agents need to agree on a common parameter vector (also called model or task) corresponding to the minimizer of the following weighted sum of individual risks:

$$w^o = \arg \min_{w \in \mathbb{R}^{M_c}} \frac{1}{K} \sum_{k=1}^{K} J_k(w), \quad (1)$$

where $M_c$ represents a common vector length, i.e., in this case, the dimensions $M_k$ for all agents are identical and equal to $M_c$. Moreover, $w$ is the global parameter vector, which all agents need to agree upon. Each agent seeks to estimate $w^o$ through local computations and communications among neighboring agents without the need to know any of the risks or losses besides its own. Among many useful strategies that have been proposed in the literature [6], [7], [35]–[37], diffusion strategies [6], [7] are particularly attractive since they are scalable, robust, and enable continuous learning and adaptation in response to drifts in the location of the minimizer.

In this work, instead of considering the single-task formulation (1), we consider a generalization that allows the network to solve multitask optimization problems. Multitask learning is suitable for network applications where differences in the data distributions require more complex models and flexible algorithms than single-task implementations. In multitask networks, agents generally need to estimate and track multiple distinct, though related, models or objectives. For instance, in distributed power system state estimation, the local state vectors to be estimated at neighboring control centers may overlap partially since the areas in a power system are interconnected [38]. Likewise, in weather forecasting applications, regional differences in the collected data distributions require agents to exploit the correlation profile in the data for enhanced decision rules [39]. Existing strategies to address multitask

problems generally exploit prior knowledge on how the tasks across the network relate to each other [8]. For example, one way to model relationships among tasks is to formulate convex optimization problems with appropriate co-regularizers between neighboring agents [8]. Another way to leverage the relationships is to constrain the model parameters to lie within certain subspaces that can represent for instance shared latent patterns that are common across tasks [8], [40], [41]. The choice between these techniques depends in general on the specific characteristics of the tasks and the desired trade-offs between model complexity and performance [8], [41].

In this work, we study decentralized learning under subspace constraints in the presence of compressed communications. Specifically, we consider inference problems of the form:

$$w^o = \arg \min_{w} \sum_{k=1}^{K} J_k(w_k), \quad (2) \\ \text{subject to } w \in \text{Range}(\mathcal{U})$$

where the matrix $\mathcal{U}$ is an $M \times P$ full-column rank matrix (with $P \ll M$) assumed to be semi-unitary, i.e., its columns are orthonormal ($\mathcal{U}^\top \mathcal{U} = I_P$). By using the stochastic gradient of the individual risk $J_k(w_k)$, agent $k$ seeks to estimate the $k$-th $M_k \times 1$ subvector $w_k^o$ of the network vector $w^o = \text{col}\{w_1^o, \dots, w_K^o\}$, which is required to lie in a low-dimensional subspace. While the objective in (2) is additively separable, the subspace constraint couples the models across the agents. Constrained formulations of the form (2) have been studied previously in decentralized settings where communication constraints are absent [40], [42]. As explained in [8], [42], [40, Sec. II], by properly selecting the matrix $\mathcal{U}$, formulation (2) can be tailored to address a wide range of optimization problems encountered in network applications. Examples include i) consensus or single-task optimization (where the agents' objective is to reach consensus on the minimizer $w^o$ in (1)), ii) decentralized coupled optimization (where the parameter vectors to be estimated at neighboring agents are partially overlapping) [38], [41], [43], [44], and iii) multitask inference under smoothness (where the network parameter vector $w$ to be estimated is required to be smooth w.r.t. the underlying network topology) [39], [40]. For instance, setting in (2) $\mathcal{U} = \frac{1}{\sqrt{K}}(\mathbb{1}_K \otimes I_{M_c})$ where $\mathbb{1}_K$ is the $K \times 1$ vector of all ones, we obtain an optimization problem equivalent to the consensus problem (1). While projecting onto the space spanned by the vector of all ones allows to enforce consensus across the network, graph smoothness can in general be promoted by projecting onto the space spanned by the eigenvectors of the graph Laplacian corresponding to small eigenvalues [8], [40], [42].

### B. Decentralized diffusion-based approach

To solve problem (2) in a decentralized manner, we consider the primal approach proposed and studied in [11], [40], namely,

$$\left\{ \begin{array}{l} \psi_{k,i} = w_{k,i-1} - \mu \widehat{\nabla}_{w_k} J_k(w_{k,i-1}) \quad (3a) \\ w_{k,i} = \sum_{\ell \in \mathcal{N}_k} A_{k,\ell} \psi_{\ell,i} \quad (3b) \end{array} \right.$$
where $\mathcal{N}_k$ denotes the set of nodes connected to agent $k$ by a communication link (including node $k$ itself) and $\mu > 0$ is a small step-size parameter. Note that the information sharing across agents in (3) is implemented by means of a $K \times K$ block combination matrix $\mathcal{A} = [A_{k\ell}]$ that has a zero $M_k \times M_\ell$ block element $(k, \ell)$ if nodes $k$ and $\ell$ are not neighbors, i.e., $A_{k\ell} = 0$ if $\ell \notin \mathcal{N}_k$, and satisfies the following conditions [40]:

$$ \mathcal{A}U = U, \quad U^\top \mathcal{A} = U^\top, \quad \text{and} \quad \rho(\mathcal{A} - \mathcal{P}_U) < 1, \quad (4) $$

where $\rho(\cdot)$ denotes the spectral radius of its matrix argument, and $\mathcal{P}_U = UU^\top$ is the orthogonal projection matrix onto Range($U$). It is shown [11], [42] how combination matrices $\mathcal{A}$ satisfying (4) can be constructed. If strategy (3) is employed to solve the single-task problem (1), we can select the combination matrix $\mathcal{A}$ in the form $A \otimes I_{M_c}$, where $A = [a_{k\ell}]$ is a $K \times K$ doubly-stochastic matrix satisfying:

$$ a_{k\ell} \ge 0, \quad A1_K = 1_K, \quad 1_K^\top A = 1_K^\top, \quad a_{k\ell} = 0 \text{ if } \ell \notin \mathcal{N}_k, \quad (5) $$

In this case, conditions (4) are satisfied for $\mathcal{U} = \frac{1}{\sqrt{K}}(1_K \otimes I_{M_c})$ [40] and strategy (3) reduces to the standard diffusion Adapt-Then-Combine (ATC) approach [6], [7]:

$$ \left\{ \begin{array}{l} \psi_{k,i} = w_{k,i-1} - \mu \widehat{\nabla}_{w_k} J_k(w_{k,i-1}) \quad (6a) \\ w_{k,i} = \sum_{\ell \in \mathcal{N}_k} a_{k\ell} \psi_{\ell,i} \quad (6b) \end{array} \right. $$

This fact motivates the use of the terminology “diffusion Adapt-Then-Combine (ATC) approach” in the sequel when referring to the decentralized strategy (3) for solving general constrained optimization problems of the form (2).

The first step (3a) in the ATC approach (3) is the self-learning step corresponding to the stochastic gradient descent step on the individual risk $J_k(\cdot)$. This step is followed by the social learning step (3b) where agent $k$ receives the intermediate estimates $\{\psi_{\ell,i}\}$ from its neighbors $\ell \in \mathcal{N}_k$ and combines them through $\{A_{k\ell}\}$ to form $w_{k,i}$, which corresponds to the estimate of $w_k^o$ at agent $k$ and iteration $i$. To alleviate the communication bottleneck resulting from the exchange of the intermediate estimates among agents over many iterations, compressed communication must be considered. Before presenting the communication-efficient variant of the ATC approach (3), we describe in the following the class of compression operators considered in this study.

### C. Compression operator

For the sake of clarity, we first introduce the following formal definitions for key concepts relating to data compression.

**Definition 1. (Compression operator).** Let $L$ represent a generic vector length. A compression operator $\mathcal{C}: \mathbb{R}^L \to \mathbb{R}^L$ associates to every input $x \in \mathbb{R}^L$ a random quantity $\mathcal{C}(x) \in \mathbb{R}^L$ that is governed by the conditional probability measure $\mathbb{P}(\cdot|x)$.

Note that the above family of compression operators includes deterministic mappings as a particular case.

**Definition 2. (Bounded-distortion compression operator).** It is a compression operator that fulfills the property:

$$ \mathbb{E}\|x - \mathcal{C}(x)\|^2 \le \beta_c^2 \|x\|^2 + \sigma_c^2, \quad (7) $$

for some $\beta_c^2 \ge 0$ and $\sigma_c^2 \ge 0$, and where the expectation is taken over the conditional probability measure $\mathbb{P}(\cdot|x)$.

**Definition 3. (Unbiased compression operator).** It is a compression operator that fulfills the property:

$$ \mathbb{E}[\mathcal{C}(x)] = x. \quad (8) $$

In this study, we consider bounded-distortion compression operators. Table I provides a list of bounded-distortion operators commonly used in decentralized learning, with the corresponding compression noise parameters $\beta_c^2$ and $\sigma_c^2$, and the bit-budget required to encode an input vector $x \in \mathbb{R}^L$. By comparing the reported schemes, we observe that the “rand-c”, “randomized Gossip”, and “top-c” can be considered as sparsifiers that map a full vector into a sparse version thereof. For instance, the rand-c scheme selects randomly $c$ components of the input vector and encodes them with very high precision (32 or 64 bits are typical values for encoding a scalar). These bits are then communicated over the links in addition to the bits encoding the locations of the selected entries. On the other hand, the QSGD scheme encodes the norm of the input vector with very high precision. In addition to encoding the norm, L-bits are used to encode the signs of the input vector components and $L[\log_2(s)]$ to encode the levels. In comparison, the probabilistic uniform and probabilistic ANQ quantizers do not make any assumptions on the high-precision representation of specific variables. In the following, we highlight the key facts regarding the compression operators considered in this study.

1) **Allowing for an absolute compression noise term:** Many existing works focus on studying decentralized learning in the presence of bounded-distortion compression operators that satisfy condition (7) with the absolute noise term $\sigma_c^2 = 0$ [9], [10], [20], [21], [23], [26]–[31], [33]. In contrast, the analysis in the current work is conducted in the presence of both the relative (captured through $\beta_c^2$) and the absolute compression noise terms. As explained in [24], neglecting the effect of $\sigma_c^2$ requires that some quantities (e.g., the norm of the vector in QSGD) are represented with no quantization error, in practice at the machine precision. We refer the reader to [25] for a description of a framework for designing randomized compression operators that do not require high-precision quantization of specific variables. Particularly, Sec. II in [25] describes the design of the probabilistic uniform and ANQ quantizers endowed with a variable-rate coding scheme from [24] to adapt the bit rate based on the quantizer input. When these rules, which are listed in Table I (rows 2–3), are applied entrywise to a vector $x \in \mathbb{R}^L$, the overall (random) bit budget will be equal to [25]:

$$ r(x) = \log_2(3) \sum_{j=1}^{L} (1 + \lceil \log_2(|\mathbf{n}(x_j)| + 1) \rceil). \quad (9) $$

2) **Allowing for the use of biased compression operators:** Although the communication-efficient approach developed in [25] can be used for solving decentralized learning under subspace constraints and makes no assumptions about encoding quantities with high precision, it is not designed to handle biased compression operators, i.e., operators that do not satisfy the unbiasedness condition (8). As we will see,
* In terms of steady-state performance: We show that, in the small step-size regime, i.e., when $\mu \to 0$ (so that higher order terms of the step-size can be neglected), the iterates $w_{k,i}$ generated by the communication-efficient approach resulting from incorporating differential quantization and error feedback into the ATC diffusion approach (3) satisfy:

$$ \limsup_{i \to \infty} \mathbb{E} \|w_k^o - w_{k,i}\|^2 \le \kappa \mu, \quad (13) $$

where $\kappa$ is a constant that depends mainly on the gradient noise (i.e., the difference between the true gradient and its approximation) variance, and does not depend on the compression noise terms $\{\beta_c^2, \sigma_c^2\}$. The same result holds when studying the ATC diffusion approach (3) in the absence of compression [40, Theorem 1]. As we will show later, this asymptotic equivalence is achievable because the compression error is contained in higher-order terms that vanish faster than $\mu$ as $\mu \to 0$.

* In terms of bit rate: While result (13) provides important reassurance about the accuracy of the compressed approach, it does not address the communication efficiency directly, which is often quantified in terms of bit-rate. In the absence of the absolute quantization noise term ($\sigma_c^2 = 0$), result (13) is achieved at the expense of communicating some quantities with high precision (as previously explained). In the presence of the absolute noise term, the analysis reveals that, to guarantee (13), the parameters of the compression schemes (which are chosen by the designer) should be set so that the absolute noise term converges to zero as $\mu \to 0$. We prove that this result can be achieved with a bit rate that remains bounded as $\mu \to 0$, despite the fact that we are requiring an increasing precision as the step-size decreases.

Thus, our theoretical findings reveal that, in the small step-size regime, the proposed strategy attains the performance achievable in the absence of compression, despite the use of a finite number of bits. This demonstrates the effectiveness of the approach in maintaining performance while reducing communication overheads. While the theoretical findings show the optimality of the strategy in the small step-size regime, the experimental results in Sec. V illustrate its practical effectiveness in terms of achieving superior or competitive performance against state-of-the-art baselines in various scenarios, including those beyond the small step-size regime.

Compared to the previous work [25], which also considers compressed variants of the diffusion ATC algorithm (3), the current work introduces three key improvements. First, it extends the framework to allow for both deterministic and randomized biased compression operators, whereas [25] only considered unbiased probabilistic compression. Second, while [25] also employed differential quantization, the current work incorporates error feedback, which plays an important role in filtering the compression noise. This addition makes the subsequent mean-square-error analysis more demanding, as it requires studying not only the evolution of the iterates but also the evolution of the compression errors that are fed back into the algorithm. Finally, the main theoretical result of this work represents a notable advancement over that of [25], as it

demonstrates that the combination of differential quantization and error feedback enables the algorithm to achieve performance comparable to the uncompressed ATC algorithm (3), while maintaining a stable bit budget. In particular, in [25], we established that the method guarantees the traditional small estimation error result, i.e., $\limsup_{i \to \infty} \mathbb{E} \|w_k^o - w_{k,i}\|^2 = O(\mu)$, meaning that reducing $\mu$ keeps the estimation errors small (on the order of $\mu$). However, in [25], the constant multiplying $\mu$ depends on the compression noise parameters, whereas in the current work, this constant matches the one obtained in the analysis of the uncompressed ATC variant (3), effectively eliminating the adverse impact of compression in the small step-size regime. A similar discussion applies when comparing the current work with the previous compressed ATC diffusion-based work [20], which focuses on decentralized communication-efficient consensus optimization and assumes that the absolute compression noise term $\sigma_c^2 = 0$.

### III. DECENTRALIZED ALGORITHMIC FRAMEWORK: COMPRESSED COMMUNICATIONS

In this work, we propose the DEF-ATC (differential error feedback - adapt then combine) diffusion strategy listed in Algorithm 1 and in (18a)-(18c) for solving problem (2) in a decentralized and communication-efficient manner. At each iteration $i$, each agent $k$ in the network performs three steps. The first step, which corresponds to the adaptation step, is identical to the adaptation step (3a), except that the step-size $\mu$ in (3a) is replaced by $\mu/\zeta$ in (14), where $\zeta \in (0, 1]$ is a damping parameter appearing in the compression step (15). This parameter is used to counteract the instability induced by the compression errors. The second step is the compression step. To update $\{\phi_{\ell,i}\}_{\ell \in \mathcal{N}_k}$, each agent $k$ first encodes the error compensated difference $\psi_{k,i} - \phi_{k,i-1} + z_{k,i-1}$ (using a bounded-distortion compression operator$^3 C_k(\cdot)$), and broadcasts the result to its neighbors. Then, agent $k$ updates the local compression error vector $z_{k,i}$ according to (16) and performs the reconstruction on each received vector by first decoding it to obtain $\delta_{\ell,i}$, and then computing the predictor $\phi_{\ell,i}$ according to (15) where $\delta_{\ell,i}$ is scaled by the aforementioned damping parameter $\zeta$. Observe that implementing the compression step in Algorithm 1 requires storing the previous compression error $z_{k,i-1}$ and the previous predictors $\{\phi_{\ell,i-1}\}_{\ell \in \mathcal{N}_k}$ by agent $k$. The compression step is followed by the combination step (17) where agent $k$ combines the reconstructed vectors $\{\phi_{\ell,i}\}$ using the combination coefficients $\{A_{k,l}\}$ and a mixing parameter $\gamma \in (0, 1]$. The resulting vector $w_{k,i}$ is the estimate of $w_k^o$, the $k$-th subvector of $w^o$ in (2), at agent $k$ and iteration $i$. As we will see in Sec. IV, and as for the damping coefficient $\zeta$, the mixing parameter $\gamma$ in the combination step (17) can also be used to control the algorithm stability. In terms of memory requirements, agent $k$ at iteration $i$ needs to store: i) the local update vector $w_{k,i}$, which represents the agent's current estimate; ii) the local compression error vector $z_{k,i}$, which is required for implementing error feedback; and iii) the reconstructed vectors $\{\phi_{\ell,i}\}_{\ell \in \mathcal{N}_k}$, which correspond to

<footnote>$^3$Since the compression characteristics can vary across agents, the compression operator becomes $C_k$ instead of $C$ with a subscript $k$ added to $C$.</footnote>
**Algorithm 1:** DEF-ATC (differential error feedback - adapt then combine) diffusion strategy for solving (2)

**Input:** initializations $\mathbf{w}_{k,0} = 0$, $\phi_{k,0} = 0$, and $z_{k,0} = 0$, small step-size $\mu$, damping coefficient $\zeta \in (0, 1]$, mixing parameter $\gamma \in (0, 1]$, combination matrix $\mathcal{A}$ satisfying (4). **for** $i = 1, 2, \dots, \text{on the } k\text{-th node do}$

**Adapt:** update $\mathbf{w}_{k,i-1}$ according to:

$$ \psi_{k,i} = \mathbf{w}_{k,i-1} - \frac{\mu}{\zeta} \widehat{\nabla_{w_k} J_k}(\mathbf{w}_{k,i-1}) \quad (14) $$

**Compress and broadcast:**

* encode the error compensated difference $\psi_{k,i} - \phi_{k,i-1} + z_{k,i-1}$ using a bounded-distortion compression operator $\mathcal{C}_k(\cdot)$ and broadcast the result $\mathbf{p}_{k,i}$ to the neighbors $\mathcal{N}_k$

* upon receiving the compressed messages $\{\mathbf{p}_{\ell,i}\}$ from neighbors $\ell \in \mathcal{N}_k$, first decode them to obtain $\{\delta_{\ell,i} = \mathcal{C}_{\ell}(\psi_{\ell,i} - \phi_{\ell,i-1} + z_{\ell,i-1})\}_{\ell \in \mathcal{N}_k}$, and then compute $\{\phi_{\ell,i}\}_{\ell \in \mathcal{N}_k}$ according to:

$$ \phi_{\ell,i} = \phi_{\ell,i-1} + \zeta \delta_{\ell,i}, \quad \ell \in \mathcal{N}_k \quad (15) $$

* update the local compression error:

$$ z_{k,i} = (\psi_{k,i} - \phi_{k,i-1} + z_{k,i-1}) - \delta_{k,i} \quad (16) $$

**Combine:** Update local model according to:

$$ \mathbf{w}_{k,i} = (1 - \gamma)\phi_{k,i} + \gamma \sum_{\ell \in \mathcal{N}_k} A_{k\ell}\phi_{\ell,i} \quad (17) $$

the information received from neighboring agents, and are required for implementing differential quantization.

For the sake of convenience, we rewrite Algorithm 1 in the following compact form:

$$ \psi_{k,i} = \mathbf{w}_{k,i-1} - \frac{\mu}{\zeta} \widehat{\nabla_{w_k} J_k}(\mathbf{w}_{k,i-1}) \quad (18a) $$

$$ \phi_{k,i} = \phi_{k,i-1} + \zeta \mathcal{C}_k(\psi_{k,i} - \phi_{k,i-1} + z_{k,i-1}) \quad (18b) $$

$$ \mathbf{w}_{k,i} = (1 - \gamma)\phi_{k,i} + \gamma \sum_{\ell \in \mathcal{N}_k} A_{k\ell}\phi_{\ell,i} \quad (18c) $$

where the compression error $z_{k,i}$ is updated according to:

$$ z_{k,i} = (\psi_{k,i} - \phi_{k,i-1} + z_{k,i-1}) - \mathcal{C}_k(\psi_{k,i} - \phi_{k,i-1} + z_{k,i-1}). \quad (19) $$

Observe that, in the absence of compression (i.e., when the operator $\mathcal{C}_k(\cdot)$ in (18b) and (19) is replaced by the identity operator and the parameters $\zeta$ and $\gamma$ in (18b) and (18c), respectively, are set to 1) we recover the diffusion ATC approach (3). Therefore, Algorithm 1 can be seen as a communication-efficient variant of the Adapt-Then-Combine (ATC) approach. To mitigate the negative impact of compression, the DEF-ATC approach uses differential quantization and error-feedback in step (18b). Differential quantization consists of compressing differences of the form $\psi_{k,i} - \phi_{k,i-1}$ and transmitting them, instead of communicating compressed versions of the estimates $\psi_{k,i}$. Error feedback, on the other hand, consists of locally storing the compression error $z_{k,i}$ (i.e., the difference between the input and output of the compression operator), and incorporating it back into the next iteration. In Remark 1 further ahead, we explain the role of the compression error $z_{k,i}$ and how its introduction helps mitigate the accumulation of errors over time.

# IV. MEAN-SQUARE-ERROR AND BIT RATE STABILITY ANALYSIS

## A. Modeling assumptions

In this section, we analyze strategy (18) with a matrix $\mathcal{A}$ satisfying (4) by examining the average squared distance between $\mathbf{w}_{k,i}$ and $w_k^o$ (defined in (2)), namely, $\mathbb{E}\|w_k^o - \mathbf{w}_{k,i}\|^2$, under the following assumptions on the risks $\{J_k(\cdot)\}$, the compression operators $\{\mathcal{C}_k(\cdot)\}$, and the gradient noise processes $\{s_{k,i}(\cdot)\}$ defined by [6]:

$$ s_{k,i}(w) \triangleq \nabla_{w_k} J_k(w) - \widehat{\nabla_{w_k} J_k}(w). \quad (20) $$

**Assumption 1. (Conditions on individual and aggregate risks).** The individual risks $J_k(w_k)$ are assumed to be differentiable and convex such that:

$$ \|\nabla_{w_k} J_k(x_k) - \nabla_{w_k} J_k(y_k)\| \le \delta_k \|x_k - y_k\|, \quad \forall x_k, y_k \in \mathbb{R}^{M_k} \quad (21) $$

where $\delta_k \ge 0$ for $k = 1, \dots, K$. It is further assumed that the aggregate risk defined as $J^{\text{glob}}(w) \triangleq \sum_{k=1}^K J_k(w_k)$ satisfies:

$$ \langle x - y, \nabla_{w_k} J^{\text{glob}}(x) - \nabla_{w_k} J^{\text{glob}}(y) \rangle \ge \nu \|x - y\|^2, \quad (22) $$

for any two vectors $x, y \in \text{Range}(\mathcal{U})$, and for some positive parameter $\nu > 0$. $\square$

While the analyses in [25] and [40] assume that the risk functions $J_k(w_k)$ are twice-differentiable, the analysis in this work requires only first-order differentiability. As explained in [6, Appendix E], if the risks are twice-differentiable and convex, then requiring the Hessian to be uniformly bounded from above, i.e., $\nabla_{w_k}^2 J_k(w_k) \le \delta_k I_{M_k}$, $\forall w_k$, as in [25], [40], is equivalent to the Lipschitz continuity of the gradient for first-order differentiable convex functions (condition (21)). On the other hand, by rewriting problem (2) in the following alternative form:

$$ w^o = \mathcal{U}s^o, \text{ with } s^o = \arg \min_s \{f(s) \triangleq J^{\text{glob}}(\mathcal{U}s)\}, \quad (23) $$

we can show that if $f(s)$ is $\nu$-strongly convex (implying that problem (2) has a unique minimizer $w^o$), then condition (22) is satisfied. While the smoothness condition (21) is standard in decentralized learning, condition (22) can be interpreted as a network global strong convexity condition, which is generally weaker than the local strong convexity typically imposed on each individual cost function $J_k(w_k)$ (as commonly adopted in various studies on decentralized learning under communication constraints [10], [22], [24], [28], [29]).

**Assumption 2. (Conditions on gradient noise).** The gradient noise process defined in (20) satisfies for $k = 1, \dots, K$:

$$ \mathbb{E}[s_{k,i}(\mathbf{w}_{k,i-1}) | \{\phi_{\ell,i-1}, z_{\ell,i-1}\}_{\ell=1}^K] = 0, \quad (24) $$

$$ \mathbb{E}[\|s_{k,i}(\mathbf{w}_{k,i-1})\|^2 | \{\phi_{\ell,i-1}, z_{\ell,i-1}\}_{\ell=1}^K] \le \beta_{s,k}^2 \|w_k^o - \mathbf{w}_{k,i-1}\|^2 + \sigma_{s,k}^2, \quad (25) $$

for some $\beta_{s,k}^2 \ge 0$ and $\sigma_{s,k}^2 \ge 0$. $\square$

**Assumption 3. (Conditions on compression operators).** In step (18b) of the DEF-ATC strategy, each agent $k$ at time $i$ applies to the error compensated difference $\chi_{k,i} = \psi_{k,i} - \phi_{k,i-1} + z_{k,i-1}$ a bounded-distortion compression
operator $\mathcal{C}_k(\cdot)$ (see Definition 2) with compression noise parameters $\beta_{c,k}^2$ and $\sigma_{c,k}^2$. It is assumed that given the past history, the randomized compression mechanism depends only on the quantizer input $\chi_{k,i}$. Consequently, from (7), we get:

$$ \mathbb{E}[\|\chi_{k,i} - \mathcal{C}_k(\chi_{k,i})\|^2 | \mathbf{h}_i] = \mathbb{E}[\|\chi_{k,i} - \mathcal{C}_k(\chi_{k,i})\|^2 | \chi_{k,i}] \\ \leq \beta_{c,k}^2 \|\chi_{k,i}\|^2 + \sigma_{c,k}^2, \quad (26) $$

where $\mathbf{h}_i$ is the vector collecting all iterates generated by (18) before the quantizer is applied to $\chi_{k,i}$, namely, $\{\{\phi_{\ell,j}\}_{j=1}^{i-1}, \{\psi_{\ell,j}\}_{j=1}^{i}, \{z_{\ell,j}\}_{j=1}^{i-1}\}_{\ell=1}^K$. $\square$

## B. Network error vector recursion

Let $\tilde{w}_{k,i} = w_k^o - w_{k,i}$, $\tilde{\psi}_{k,i} = w_k^o - \psi_{k,i}$, and $\tilde{\phi}_{k,i} = w_k^o - \phi_{k,i}$. By subtracting $w_k^o$ from both sides of (18a), by using (20), and by introducing the following network quantities:

$$ s_i \triangleq \operatorname{col}\{s_{1,i}(w_{1,i-1}), \dots, s_{K,i}(w_{K,i-1})\}, \quad (27) $$

$$ \begin{aligned} g_{i-1} &\triangleq \operatorname{col}\{\nabla_{w_1} J_1(w_{1,i-1}), \dots, \nabla_{w_K} J_K(w_{K,i-1})\} \\ &= \nabla_w J^{\text{glob}}(w_{i-1}), \end{aligned} \quad (28) $$

$$ w_{i-1} \triangleq \operatorname{col}\{w_{1,i-1}, \dots, w_{K,i-1}\}, \quad (29) $$

$$ \tilde{w}_{i-1} \triangleq \operatorname{col}\{\tilde{w}_{1,i-1}, \dots, \tilde{w}_{K,i-1}\}, \quad (30) $$

we can show that the network error vector $\tilde{\psi}_i = \operatorname{col}\{\tilde{\psi}_{k,i}\}_{k=1}^K$ evolves according to:

$$ \tilde{\psi}_i = \tilde{w}_{i-1} + \frac{\mu}{\zeta} g_{i-1} - \frac{\mu}{\zeta} s_i. \quad (31) $$

By subtracting $w_k^o$ from both sides of (18c), by replacing $w_k^o$ by $(1-\gamma)w_k^o + \gamma w_k^o$, and by using $w_k^o = \sum_{\ell \in \mathcal{N}_k} A_{k\ell} w_\ell^o$ [40, Sec. III-B], we obtain:

$$ \tilde{w}_{k,i} = (1 - \gamma)\tilde{\phi}_{k,i} + \gamma \sum_{\ell \in \mathcal{N}_k} A_{k\ell} \tilde{\phi}_{\ell,i}. \quad (32) $$

From (32), we find that the network error vector $\tilde{w}_{i-1}$ in (30) evolves according to:

$$ \tilde{w}_{i-1} = (1 - \gamma)\tilde{\phi}_{i-1} + \gamma \mathcal{A}\tilde{\phi}_{i-1} = \mathcal{A}'\tilde{\phi}_{i-1}, \quad (33) $$

where

$$ \tilde{\phi}_i \triangleq \operatorname{col}\{\tilde{\phi}_{1,i}, \dots, \tilde{\phi}_{K,i}\}, \quad (34) $$

$$ \mathcal{A}' \triangleq (1 - \gamma) I_M + \gamma \mathcal{A}. \quad (35) $$

By subtracting $w_k^o$ from both sides of (18b) and by adding and subtracting $w_k^o$ to the difference $\psi_{k,i} - \phi_{k,i-1}$, we can write:

$$ \tilde{\phi}_{k,i} = \tilde{\phi}_{k,i-1} - \zeta \mathcal{C}_k (\tilde{\phi}_{k,i-1} - \tilde{\psi}_{k,i} + z_{k,i-1}). \quad (36) $$

Now, by adding and subtracting $\zeta(\tilde{\phi}_{k,i-1} - \tilde{\psi}_{k,i} + z_{k,i-1})$ to the RHS of the above equation, we obtain:

$$ \tilde{\phi}_{k,i} = (1 - \zeta)\tilde{\phi}_{k,i-1} + \zeta\tilde{\psi}_{k,i} + \zeta(z_{k,i} - z_{k,i-1}), \quad (37) $$

in terms of the compression error vector $z_{k,i}$ defined in (19). By combining (31), (33), and (37), we conclude that the network error vector $\tilde{\phi}_i$ in (34) evolves according to the following dynamics:

$$ \tilde{\phi}_i = \mathcal{A}'' \tilde{\phi}_{i-1} + \mu g_{i-1} - \mu s_i + (z_i - z_{i-1}), \quad (38) $$

where

$$ \mathcal{A}'' \triangleq (1 - \zeta) I_M + \zeta \mathcal{A}' \stackrel{(35)}{=} (1 - \zeta \gamma) I_M + \zeta \gamma \mathcal{A}, \quad (39) $$

$$ z_i \triangleq \zeta \operatorname{col}\{z_{k,i}\}_{k=1}^K. \quad (40) $$

**Remark 1 (Temporal filtering of the compression error):** A direct consequence of feeding back the error in the compression step (18b) is to subtract the compression error from previous instants in recursion (38), thereby allowing for a correction mechanism⁴. This correction helps mitigate the accumulation of errors over time, leading to improved network performance. ■

## C. Mean-square-error stability

The mean-square-error analysis will be carried out by first establishing the boundedness of $\limsup_{i \to \infty} \mathbb{E}\|\tilde{\phi}_i - z_i\|^2$, and then using relation (33) and Holder's and Jensen's inequalities to deduce boundedness of $\limsup_{i \to \infty} \mathbb{E}\|\tilde{w}_i\|^2$. Therefore, in the following, we first study the stability of the network error vector $\tilde{\phi}_i^z$ defined as:

$$ \tilde{\phi}_i^z \triangleq w^o - \phi_i^z = \tilde{\phi}_i - z_i, \quad (\text{where } \phi_i^z \triangleq \phi_i + z_i) \quad (42) $$

and evolving according to:

$$ \tilde{\phi}_i^z = \mathcal{A}'' \tilde{\phi}_{i-1}^z + \mu g_{i-1} - \mu s_i - (I_M - \mathcal{A}'') z_{i-1} \quad (43) $$

The above identity can be found by adding and subtracting the term $\mathcal{A}''z_{i-1}$ to the RHS of (38). We analyze the stability of recursion (43) by first transforming it into a more convenient form (shown later in (51) and (52)) using the Jordan canonical decomposition [47] of the matrix $\mathcal{A}''$ defined in (39). To exploit the eigen-structure of $\mathcal{A}'$, we first recall that a matrix $\mathcal{A}$ satisfying the conditions in (4) (for a full-column rank semi-unitary matrix $\mathcal{U}$) has a Jordan decomposition of the form $\mathcal{A} = \mathcal{V}_\epsilon \Lambda_\epsilon \mathcal{V}_\epsilon^{-1}$ with [40, Lemma 2]:

$$ \mathcal{V}_\epsilon = [\mathcal{U} | \mathcal{V}_{R,\epsilon}], \quad \Lambda_\epsilon = \begin{bmatrix} I_P & 0 \\ 0 & \mathcal{J}_\epsilon \end{bmatrix}, \quad \mathcal{V}_\epsilon^{-1} = \begin{bmatrix} \mathcal{U}^\top \\ \mathcal{V}_{L,\epsilon}^\top \end{bmatrix}, \quad (44) $$

where $\mathcal{J}_\epsilon$ is a Jordan matrix with eigenvalues (which may be complex but have magnitude less than one) on the diagonal and $\epsilon > 0$ on the super-diagonal [40, Lemma 2], [6, pp. 510]. The parameter $\epsilon$ is chosen small enough to ensure $\rho(\mathcal{J}_\epsilon) + \epsilon \in (0, 1)$ [40]. Consequently, the matrices $\mathcal{A}'$ and $\mathcal{A}''$ in (35) and (39) have a Jordan decomposition of the form $\mathcal{A}' = \mathcal{V}_\epsilon \Lambda'_\epsilon \mathcal{V}_\epsilon^{-1}$ and $\mathcal{A}'' = \mathcal{V}_\epsilon \Lambda''_\epsilon \mathcal{V}_\epsilon^{-1}$, respectively, where:

$$ \Lambda'_\epsilon = \begin{bmatrix} I_P & 0 \\ 0 & \mathcal{J}'_\epsilon \end{bmatrix}, \quad \text{with } \mathcal{J}'_\epsilon \triangleq (1 - \gamma) I_{M-P} + \gamma \mathcal{J}_\epsilon, \quad (45) $$

$$ \Lambda''_\epsilon = \begin{bmatrix} I_P & 0 \\ 0 & \mathcal{J}''_\epsilon \end{bmatrix}, \quad \text{with } \mathcal{J}''_\epsilon \triangleq (1 - \zeta\gamma) I_{M-P} + \zeta\gamma \mathcal{J}_\epsilon. \quad (46) $$

By multiplying both sides of (43) from the left by $\mathcal{V}_\epsilon^{-1}$ in (44), we obtain the transformed iterates and variables:

$$ \mathcal{V}_\epsilon^{-1} \tilde{\phi}_i^z = \begin{bmatrix} \mathcal{U}^\top \tilde{\phi}_i^z \\ \mathcal{V}_{L,\epsilon}^\top \tilde{\phi}_i^z \end{bmatrix} \triangleq \begin{bmatrix} \bar{\phi}_i^z \\ \tilde{\phi}_i^z \end{bmatrix}, \quad (47) $$

$$ \mathcal{V}_\epsilon^{-1} s_i = \begin{bmatrix} \mathcal{U}^\top s_i \\ \mathcal{V}_{L,\epsilon}^\top s_i \end{bmatrix} \triangleq \begin{bmatrix} \bar{s}_i \\ \tilde{s}_i \end{bmatrix}, \quad (48) $$

⁴To see this, we can simply remove the error feedback mechanism from the approach (18) by replacing the compression step (18b) by $\phi_{k,i} = \phi_{k,i-1} + \zeta \mathcal{C}_k(\psi_{k,i} - \phi_{k,i-1})$ and derive the network error vector $\tilde{\phi}_i$ in (34) by following similar arguments as in (27)–(40). Instead of (38), we would arrive at the following dynamics:

$$ \tilde{\phi}_i = \mathcal{A}'' \tilde{\phi}_{i-1} + \mu g_{i-1} - \mu s_i + z_i, \quad (41) $$

where we obtain in (41) the instantaneous noise vector $z_i$ instead of the difference vector $z_i - z_{i-1}$ as in (38).
$$ \mathcal{V}_{\epsilon}^{-1} \mathbf{g}_{i-1} = \begin{bmatrix} \mathcal{U}^{\top} \mathbf{g}_{i-1} \\ \mathcal{V}_{L, \epsilon}^{\top} \mathbf{g}_{i-1} \end{bmatrix} \triangleq \begin{bmatrix} \bar{\mathbf{g}}_{i-1} \\ \check{\mathbf{g}}_{i-1} \end{bmatrix}, \quad (49) $$

$$ \mathcal{V}_{\epsilon}^{-1} \mathbf{z}_{i-1} = \begin{bmatrix} \mathcal{U}^{\top} \mathbf{z}_{i-1} \\ \mathcal{V}_{L, \epsilon}^{\top} \mathbf{z}_{i-1} \end{bmatrix} \triangleq \begin{bmatrix} \bar{\mathbf{z}}_{i-1} \\ \check{\mathbf{z}}_{i-1} \end{bmatrix}. \quad (50) $$

In particular, the transformed components $\bar{\phi}_i^z$ and $\check{\phi}_i^z$ evolve according to:

$$ \bar{\phi}_i^z = \bar{\phi}_{i-1}^z + \mu \bar{\mathbf{g}}_{i-1} - \mu \bar{\mathbf{s}}_i, \quad (51) $$

$$ \check{\phi}_i^z = \mathcal{J}_{\epsilon}'' \check{\phi}_{i-1}^z + \mu \check{\mathbf{g}}_{i-1} - \mu \check{\mathbf{s}}_i - \zeta \gamma (I_{M-P} - \mathcal{J}_{\epsilon}) \check{\mathbf{z}}_{i-1}, \quad (52) $$

where we used the fact that $I_{M-P} - \mathcal{J}_{\epsilon}'' = \zeta\gamma(I_{M-P} - \mathcal{J}_{\epsilon})$.

**Theorem 1. (Mean-square-error stability).** Consider a network of K agents running the DEF-ATC diffusion approach (listed in Algorithm 1) to solve problem (2) under Assumptions 1, 2, and 3, with a matrix A satisfying (4). In the absence of the relative compression noise term (i.e., $\beta_{c,k}^2 = 0, \forall k$), let the damping and mixing parameters be such that $\zeta = \gamma = 1$. In the presence of the relative compression noise (i.e., at least one $\beta_{c,k}^2$ is positive for some agent k), let $\zeta \in (0, 1], \gamma \in (0, 1],$ and $\beta_{c,max}^2 = \max_{1 \le k \le K} \{\beta_{c,k}^2\}$, be such that the two following conditions are satisfied:

$$ 0 < \gamma\zeta < \frac{1 - (\rho(\mathcal{J}_{\epsilon}) + \epsilon)}{4v_1^2 v_2^2 \beta_{c,max}^2 (\rho(I - \mathcal{J}_{\epsilon}) + \epsilon)^2}, \quad (53) $$

and

$$ \gamma\zeta \frac{(\rho(I - \mathcal{J}_{\epsilon}) + \epsilon)^2}{1 - (\rho(\mathcal{J}_{\epsilon}) + \epsilon) + \beta_{c,max}^2 v_1^2 v_2^2 \left(1 + ((1 + \gamma\zeta) - \gamma\zeta(\rho(\mathcal{J}_{\epsilon}) + \epsilon))^2\right)} < \frac{1}{2}, \quad (54) $$

where $v_1 = \|\mathcal{V}_{\epsilon}^{-1}\|$, and $v_2 = \|\mathcal{V}_{\epsilon}\|$. Then, for sufficiently small step-size $\mu$, the network is mean-square-error stable, and it holds that:

$$ \limsup_{i \to \infty} \mathbb{E} \|\tilde{\phi}_i^z\|^2 \le \kappa\mu + \bar{\sigma}_c^2 O(1), \quad (55) $$

where $\bar{\sigma}_c^2 = \sum_{k=1}^K \sigma_{c,k}^2$. The constant $\kappa$ is positive, independent of $\mu$ and the compression noise terms $\{\beta_{c,k}^2, \sigma_{c,k}^2\}$, and is given by $\kappa = v_1^2 v_2^2 \frac{\bar{\sigma}_c^2}{\nu}$ with $\bar{\sigma}_c^2 = \sum_{k=1}^K \sigma_{c,k}^2$, and $\nu$ is the positive constant that appears in condition (22) of Assumption 1. Moreover, by choosing compression schemes with $\sigma_{c,k}^2 \propto \mu^{1+\epsilon}$ (where the symbol $\propto$ hides a proportionality constant independent of $\mu$) and $\epsilon \in (0, 1]$, we obtain:

$$ \limsup_{i \to \infty} \mathbb{E} \|\tilde{\phi}_i^z\|^2 \le \kappa\mu + O(\mu^{1+\epsilon}). \quad (56) $$

It then holds that:

$$ \limsup_{i \to \infty} \mathbb{E} \|\tilde{\mathcal{W}}_i\|^2 \le \kappa\mu + O(\mu^{1+\frac{\epsilon}{2}}), \quad (57) $$

from which we conclude that:

$$ \lim_{\mu \to 0} \limsup_{i \to \infty} \frac{1}{\mu} \mathbb{E} \|w_k^o - w_{k,i}\|^2 \le \kappa, \quad \text{for } k = 1, \dots, K. \quad (58) $$

Proof. See Appendix A. □

While expressions (55)–(58) in Theorem 1 reveal the influence of the step-size $\mu$, the compression noise (captured by $\{\bar{\sigma}_c^2, \beta_{c,max}^2\}$), and the gradient noise (captured by $\bar{\sigma}_s^2$) on the steady-state mean-square error, expressions (53)

and (54) reveal the influence of the relative compression noise term (captured by $\beta_{c,max}^2$) on the network stability. Expressions (53) and (54) show that when $\{\beta_{c,k}^2\}$ are such that $\beta_{c,max}^2 v_1^2 v_2^2 < 1/2$, the negative impact of compression can be mitigated by properly selecting the damping coefficient $\zeta$ and the mixing parameter $\gamma$. They also indicate that, as the compression strength increases (i.e., as $\beta_{c,max}^2$ grows larger), the feasible parameter range shrinks, and for a given graph connectivity (captured by $\rho(\mathcal{J}_{\epsilon})$ and $\rho(I - \mathcal{J}_{\epsilon})$), excessive compression can ultimately lead to instability and make the parameter range unfeasible. In such cases, one can employ a probabilistic uniform quantizer, which satisfies $\beta_{c,k}^2 = 0$, thereby eliminating the negative impact of compression on stability altogether. Returning to expression (55), the main conclusion stemming from Theorem 1 is that the mean-square-error contains two terms. The first term is $\kappa\mu$ where $\kappa$ is a constant independent of the compression noise $\{\beta_{c,k}^2, \sigma_{c,k}^2\}$, but depends on the gradient noise $\{\sigma_{s,k}^2\}$. This term, which we refer to as the gradient noise term, is classically encountered in the uncompressed case [40]. The second factor is an $O(1)$ term that is proportional to the quantizers’ absolute noise components $\{\sigma_{c,k}^2\}$. Interestingly, by choosing compression schemes with $\sigma_{c,k}^2 \propto \mu^{1+\epsilon}$ and $\epsilon \in (0, 1]$, for sufficiently small step-sizes $\mu$ we obtain $\limsup_{i \to \infty} \mathbb{E}\|w_k^o - w_{k,i}\|^2 \le \kappa\mu$. This result is reassuring since it implies that the impact of the compression noise can be minimized to the point where it only affects higher-order terms of the step-size. Consequently, the primary noise influencing the learning process will be the gradient noise, which is consistent with the classical results observed in the uncompressed case studied in [40].

In addition to characterizing the steady-state error, we can analyze the convergence rate of the DEF-ATC approach by building on the arguments presented in Theorem 1. In particular, we can establish the following lemma.

**Lemma 2. (DEF-ATC convergence rate).** Consider the same setting of Theorem 1, and let $\sigma_{c,k}^2 \propto \mu^{1+\epsilon}$ with $\epsilon \in (0, 1]$. Assume that conditions (53) and (54) are satisfied. Then, for sufficiently small step-size $\mu$, the mean-square-error of the DEF-ATC approach, namely, $\mathbb{E}\|\tilde{\mathcal{W}}_i\|^2$, converges to the steady-state error (57) at a geometric rate of $(1 - \mu\nu)^i$. Moreover, given a desired error value mse, the number of iterations required to reach this error is $O(\text{mse}^{-1} \log(\text{mse}^{-1}))$.

*Proof.* The arguments can be found in Sec. D of the supplementary material. □

While result (58) is appealing, it is not sufficient to characterize the DEF-ATC approach. To fully characterize a decentralized strategy endowed with a compression mechanism, it is essential to consider the learning-communication tradeoff. In other words, we need to assess how the design choice $\sigma_{c,k}^2 \propto \mu^{1+\epsilon}$ impacts the amount of communication resources (e.g., quantization bits). For instance, consider the probabilistic uniform quantizer from Table I. For this scheme, setting $\sigma_{c,k}^2 \propto \mu^{1+\epsilon}$ is equivalent to requiring the quantization step $\Delta$ to be proportional to $\mu^{1+\frac{\epsilon}{2}}$. Thus, while small values of $\sigma_{c,k}^2$ imply small compression errors in view of (7), they might in principle require large bit rates. Moreover, as $\mu \to 0$, the
quantization step $\Delta$ becomes very small, potentially leading to an unbounded bit rate increase. It becomes important to find a quantization scheme that achieves the same performance as the uncompressed case, i.e., $\limsup_{i \to \infty} \mathbb{E}\|w_k^o - w_{k,i}\|^2 \le \kappa\mu$, while guaranteeing a finite bit rate as $\mu \to 0$. In the next theorem, we show that DEF-ATC equipped with the variable-rate coding scheme from [24], [25, Sec. II] achieves both objectives.

### D. Bit rate stability

We first assume that the top-$c_k$ quantizer in Definition 4 (with a subscript $k$ added to $c$ to highlight the fact that the compression characteristics can vary across agents) is used at each iteration $i$ and agent $k$. We then recall that the quantizer input is given by the error compensated difference $\chi_{k,i} = \psi_{k,i} - \phi_{k,i-1} + z_{k,i-1}$, and assume that the probabilistic ANQ scheme$^5$ (Table I, row 3) is employed at the output of the top-$c_k$ sparsifier. Consequently, from (9), the bit rate at agent $k$ and iteration $i$ is given by:

$$r_{k,i} = \log_2(3) \sum_{j \in \mathcal{I}_{c_k,i}} \left( 1 + \mathbb{E} \left[ \left[ \log_2(|\mathbf{n}([\chi_{k,i}]_j)| + 1) \right] \right] \right) + (M_k - c_k) \log_2(3), \quad (59)$$

where $[\chi_{k,i}]_j$ denotes the $j$-th entry of $\chi_{k,i}$, $\mathcal{I}_{c_k,i}$ is the set containing the indices of the $c_k$ largest-magnitude components of $\chi_{k,i}$, and $(M_k - c_k) \log_2(3)$ is the number of bits required to encode the $M_k - c_k$ zero components at the output of the top-$c_k$ sparsifier$^6$.

**Theorem 2. (Bit rate stability).** Assume that each agent $k$ employs the top-$c_k$ quantizer (see Definition 4) with the probabilistic ANQ scheme. Assume further that the design parameters of the compression operators are chosen such that:

$$\omega_k = t, \quad \eta_k \propto \mu^{\frac{1+\epsilon}{2}}, \quad (60)$$

where $t$ is a constant independent of $\mu$ and $0 < \epsilon \le 1$. First, under conditions (60), we have:

$$\sigma_{c,k}^2 \propto \mu^{1+\epsilon}. \quad (61)$$

Second, in the steady state, the average number of bits at agent $k$ stays bounded as $\mu \to 0$, namely,

$$\limsup_{i \to \infty} r_{k,i} = O(1). \quad (62)$$

*Proof.* See Appendix B. □

The bit rate stability result (62) can be explained by considering again the uniform quantization rule (Table I, row 2) which, as explained previously, requires setting $\Delta \propto \mu^{1+\epsilon/2}$ in order to guarantee that $\sigma_{c,k}^2 \propto \mu^{1+\epsilon}$. The result (93) reveals that the input to the compression operators of the DEF-ATC strategy in (18b), namely, the error compensated difference $\chi_{k,i} = \psi_{k,i} - \phi_{k,i-1} + z_{k,i-1}$, under (61) is on the order of

<figure><img src="image_2.png" /><figcaption>Fig. 1. Experimental setup. (Left) Communication link matrix. (Right) Regression and noise variances.</figcaption></figure>

$\mu^{1+\epsilon/2}$ at steady-state. This means that as $\mu \to 0$, the quantizer resolution $\Delta \propto \mu^{1+\epsilon/2}$ decreases, but in proportion to the effective range of the quantizers' inputs. Theorem 2 reveals the adaptability of the variable-rate scheme, ensuring that even as the quantization becomes increasingly precise (as $\mu \to 0$), the DEF-ATC strategy can still maintain a finite expected bit rate$^7$, which is crucial for efficient data transmission.

In comparison, consider the approach studied in [25], which is obtained from DEF-ATC by removing error feedback. By calling upon the main result from Theorem 1 in [25], we find that by selecting $\sigma_{c,k}^2 \propto \mu^2$ (e.g., $\sigma_{c,k}^2 = \lambda_c \mu^2$) to ensure bit rate stability, we obtain:

$$\lim_{\mu \to 0} \limsup_{i \to \infty} \frac{1}{\mu} \mathbb{E} \| w_k^o - w_{k,i} \|^2 \le \kappa + c_1 \|\tilde{b}\|^2 + c_2 \beta_{c,\max}^2 + c_3 \lambda_c, \quad (63)$$

where $c_1$, $c_2$, and $c_3$ are some positive constants independent of $\mu$. Comparing results (58) and (63), both methods achieve the traditional small estimation error result, i.e., $\limsup_{i \to \infty} \mathbb{E}\|w_k^o - w_{k,i}\|^2 = O(\mu)$. However, result (58) is stronger, as it shows that DEF-ATC can achieve the same constant as the uncompressed variant, not just the $O(\mu)$ small estimation error result. Thus, for small $\mu$, DEF-ATC attains a performance level comparable to the uncompressed ATC, while significantly reducing the number of exchanged bits. This is not the case for the approach studied in [25] where, as it can be seen from (63), the compression parameters $\beta_{c,\max}^2$ and $\lambda_c$ impact the performance to the first order in $\mu$.

## V. SIMULATION RESULTS

We consider a network of $K=30$ nodes with the communication link matrix shown in Fig. 1 (left), where the $(k, \ell)$-th entry is equal to 1 if there is a link between $k$ and $\ell$ and is 0 otherwise. Each agent is subjected to streaming data $\{d_k(i), u_{k,i}\}$ assumed to satisfy a linear regression model of the form $d_k(i) = u_{k,i}^\top w_k^* + v_k(i)$ for some $M_c \times 1$ vector $w_k^*$ with $v_k(i)$ denoting a zero-mean measurement noise and $M_c = 10$. A mean-square-error risk of the form $J_k(w_k) = \mathbb{E}|d_k(i) - u_{k,i}^\top w_k|^2$ is associated with agent $k$. The processes $\{u_{k,i}, v_k(i)\}$ are assumed to be zero-mean Gaussian with: i) $\mathbb{E}u_{k,i}u_{k,i}^\top = R_{u,k} = \sigma_{u,k}^2 I_{M_c}$ if $k = \ell$ and 0 otherwise; ii) $\mathbb{E}v_k(i)v_k(i) = \sigma_{v,k}^2$ if $k = \ell$ and 0 otherwise.

<footnote>$^5$The probabilistic uniform rule (Table I, row 2) can be obtained from the ANQ rule by letting $\omega \to 0$ [25].</footnote>

<footnote>$^6$Encoding the 0 input using the variable-rate coding scheme from [24], [25, Sec. II] requires only a parsing symbol, i.e., $\log_2(3)$ bits. Instead of encoding the 0 entries, agent $k$ can send the location of the $c_k$ largest-magnitude components. In this case, the term $(M_k - c_k) \log_2(3)$ is replaced by $c_k[\log_2(M_k)]$. This alternative solution does not affect the main conclusions of Sec. IV-D.</footnote>

<footnote>$^7$This key property does not hold in the absence of differential quantization. In that case, the inputs to the compression operators are $\psi_{k,i} + z_{k,i-1}$, which remain $O(1)$ in steady-state. If we choose the quantizer resolution $\Delta \propto \mu^{(1+\epsilon)/2}$ to reduce the compression impact on steady-state performance as $\mu \to 0$, we can no longer ensure that the quantizer resolution decreases in proportion to the effective range of the quantizer inputs. Consequently, maintaining a finite expected bit rate is no longer guaranteed. This phenomenon is illustrated in the simulation section (Sec. V-C).</footnote>
otherwise; and iii) $\mathbf{u}_{k,i}$ and $\mathbf{v}_k(i)$ are independent of each other. The variances $\sigma_{u,k}^2$ and $\sigma_{v,k}^2$ are shown in Fig. 1 (right). Throughout Sec. V, we assume that all agents employ the same compression rule, i.e., $\mathcal{C}_k = \mathcal{C} \ \forall k$. We use the terminology “top-$c$ quantizer-name” to refer to the top-$c$ quantizer of Definition 4 where, as compression scheme $\mathcal{Q}$, we use quantizer-name. For instance, “top-4 probabilistic ANQ” is the quantizer obtained by applying the probabilistic ANQ scheme at the output of the top-4 sparsifier.

### A. Illustrating the theoretical findings

In this section and the following Secs. V-B and V-C, we assume that agents have a common model parameter $w_k^* = w^o \ \forall k$. The model $w^o$ is generated by normalizing to unit norm a randomly generated Gaussian vector, with zero mean and unit variance. To promote consensus (i.e., to solve problem (1) or, equivalently, (2) with $\mathcal{U} = \frac{1}{\sqrt{K}}(\mathbb{1}_K \otimes I_{M_c})$), we run Alg. 1 using a combination matrix of the form $\mathcal{A} = A \otimes I_{M_c}$, where $\mathcal{A}$ is generated according to the Metropolis rule [6, Chap. 8].

In Fig. 2 (left), we report the network mean-square-deviation (MSD) learning curves:

$$ \text{MSD}(i) = \frac{1}{K} \sum_{k=1}^{K} \mathbb{E} \| w_k^o - w_{k,i} \|^2, \quad (64) $$

for 3 different values of the step-size $\mu$. The results are averaged over 100 Monte-Carlo runs. For each value of the step-size, we run Alg. 1 for 4 different choices of the compression operator $\mathcal{C}$: i) top-4 sparsifier, ii) top-4 QSGD (Table I, row 6, $s = 2$), iii) top-4 probabilistic uniform (Table I, row 2, $\Delta = \mu$), and iv) top-4 probabilistic ANQ (Table I, row 3, $\omega = 0.5$, $\eta = \mu$). We set $\gamma = \zeta = 0.9$. As it can be observed, despite compression, the DEF-ATC approach achieves a performance that is almost identical to the uncompressed ATC approach (which can be obtained from Alg. 1 by setting $\gamma = \zeta = 1$ and replacing the compression operator by identity). We further observe that, in steady-state, the network MSD increases by approximately 3 dB when $\mu$ goes from $\mu_0$ to $2\mu_0$. This means that the performance is on the order of $\mu$, as expected from Theorem 1 since in the simulations the absolute noise component is such that $\sigma_{c,k}^2 \propto \mu^2$. For the top-4 probabilistic uniform and ANQ quantizers, we report in Fig. 2 (right) the average number of bits per node, per component, computed according to:

$$ R(i) = \frac{1}{K} \sum_{k=1}^{K} \frac{1}{M_k} r_{k,i}, \quad (65) $$

where $r_{k,i}$ is the bit rate given by (59), which is associated with the encoding of the error compensated difference vector $\chi_{k,i} = \psi_{k,i} - \phi_{k,i-1} + z_{k,i-1}$ transmitted by agent $k$ at iteration $i$. As it can be observed, for the three different values of the step-size, we approximately obtain the same finite average number of bits in steady-state (approximately 2.4 bits/component/iteration are required on average in steady-state when the top-4 probabilistic ANQ quantizer is used). From Table I (row 7), the top-4 sparsifier would require an average of $\frac{4(32+4)}{10} = 14.4$ bits/node/component/iteration$^8$,

<figure><img src="image_3.png" /><figcaption>Fig. 2. Network performance for three different values of the step-size ($\mu_0 = 0.001$). (Left) Evolution of the MSD learning curves. (Right) Evolution of the average number of bits per node, per component, when the variable-rate probabilistic uniform and ANQ schemes are used at the output of the top-4 sparsifier to encode the error compensated difference $\psi_{k,i} - \phi_{k,i-1} + z_{k,i-1}$ in (18b).</figcaption></figure>

which is almost six times higher than the one obtained in steady-state when the probabilistic ANQ is used. This is expected since the top-4 sparsifier requires encoding the 4 largest magnitude components of the input with very high precision. On the other hand, the top-4 QSGD (Table I, row 6, $s = 2$), which requires encoding the norm of the input with high precision, would need an average of $\frac{32+10+10}{10} = 5.2$ bits/node/component/iteration, which is almost two times higher than the one obtained for probabilistic ANQ.

Evaluating the performance of a learning approach requires considering both the *attained learning error* (MSD) and the associated *bit expense*. Therefore, in the following, we focus on reporting rate-distortion (RD) curves, where the bit budget quantifies the rate and the MSD quantifies the distortion.

### B. Top-c quantization outperforms other compression rules

We report in Fig. 3 the RD curves of DEF-ATC with probabilistic uniform and top-4 uniform quantization. We set $\mu = 0.001$ and $\gamma = \zeta = 0.9$. Each point of the rate-distortion curve corresponds to one value of the parameter $\varepsilon$, which determines the quantization step $\Delta = \mu^{\frac{1+\varepsilon}{2}}$. In the example, we selected 25 values of $\varepsilon$ linearly spaced in the interval $[10^{-3}, 1]$. For each value of $\Delta$ (i.e., each point of the curve), the resulting MSD (distortion) and average number of bits/node/component (rate) were obtained by averaging the instantaneous mean-square-deviation MSD($i$) in (64) and averaging the number of bits $R(i)$ in (65) over 100 samples after convergence of the algorithm (the expectations in (64) and (65) are estimated empirically over 100 Monte Carlo runs). The trade-off between rate and distortion can be observed from Fig. 3, namely, as the rate decreases, the distortion increases, and vice versa. For comparison purposes, we illustrate in Fig. 3 the distortion (horizontal dashed line) of the uncompressed ATC approach obtained by averaging MSD($i$) in (64) over 100 samples after convergence. We also illustrate the specific $\log_2(3)$ bit rate (vertical dashed line) corresponding to minimum number of bits possible for the considered scheme, namely, the variable-rate coding scheme from [24], [25, Sec. II]. Under this scheme, each component is appended with a parsing symbol, and the 0 value is encoded as an empty element. Thus, the minimum number of bits/component would correspond to sending only one symbol per component. As it can be observed, top-4 probabilistic uniform is more efficient than probabilistic uniform, namely, it approaches the uncompressed performance

<footnote>$^8$Note that we replaced $B_{HP}$ by 32 since we are performing the experiments on MATLAB 2022a which uses 32 bits to represent a floating number in single-precision.</footnote>
<figure><img src="image_4.png" /><figcaption>Fig. 3. Rate-distortion curves of the DEF-ATC approach with probabilistic uniform and top-4 probabilistic uniform quantization.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4. DEF-ATC performance w.r.t. to state-of-the-art baselines. Evolution of the MSD and average number of bits/node/component (when top-4 probabilistic uniform with variable-rate encoding scheme is used) for different values of the step-size. (Left) $\mu = 0.01$. (Right) $\mu = 0.001$.</figcaption></figure>

(low distortion) at a lower bit rate compared to probabilistic uniform quantization.

### C. Performance w.r.t. state-of-the-art baselines

In this part, we compare the DEF-ATC diffusion to the following approaches: i) ChocoSGD [10], ii) DeepSqueeze [33], iii) diffusion ACTC [20], and iv) compressed diffusion ATC approach (which we refer to as the “compressed ATC 2”) [25]. We assume that all agents employ the top-4 probabilistic uniform quantizer with the variable rate encoding scheme from [24], [25, Sec. II]. In Fig. 4, we report the network MSD learning curves with the corresponding bit rates, for 2 different values of the step-size $\mu = 0.01$ (left) and $\mu = 0.001$ (right). The results are averaged over 100 Monte-Carlo runs. We set the quantization parameter $\Delta = \mu$. For the ACTC [20] and compressed ATC 2 [25] approaches (which were originally designed to handle unbiased probabilistic compression), we used a step-size $\mu = 0.0125$ and $\mu = 0.00125$, in place of $\mu = 0.01$ and $\mu = 0.001$, respectively, in order to ensure that they have the same learning rate as the uncompressed ATC approach. This configuration ensures that all approaches are compared at the same learning rate. The other parameters of the baselines approaches are set as follows: i) ChocoSGD: $\gamma = 0.9$, ii) DeepSqueeze: (consensus parameter) $\eta = 0.05$ when $\mu = 0.01$ and $\eta = 0.2$ when $\mu = 0.001$, iii) ACTC: $\zeta = 0.9$, iv) compressed ATC 2: $\gamma = 0.9$, and v) DEF-ATC:

<figure><img src="image_6.png" /><figcaption>Fig. 5. RD curves of DEF-ATC and state-of-the-art baselines approaches for different values of $\mu$. The top-4 probabilistic uniform quantizer with variable-rate encoding scheme is used. (Left) $\mu = 0.01$. (Right) $\mu = 0.001$.</figcaption></figure>

$\gamma = \zeta = 0.9$. While the space of algorithms' hyperparameters ($\gamma, \zeta$, etc.) is explored in the next experiment, it is worth noting that the values chosen in the current experiment ensure a stable compressed strategy with the lowest MSD level. As it can be observed from the MSD learning curves, the DEF-ATC approach tends to outperform state-of-the-art baselines in various step-size regimes. Specifically, in the small step-size regime ($\mu = 0.001$), DEF-ATC closely approaches the performance of the uncompressed ATC, whereas ACTC and compressed ATC 2 [25] performance is affected by compression. This outcome is expected, as explained previously at the end of Sec. II-D, since the constant multiplying the step-size $\mu$ in the steady-state performance $\limsup_{i \to \infty} \mathbb{E}\|w_k^o - w_{k,i}\|^2 = O(\mu)$ for both approaches depends on the compression noise parameters. In order to identify which method provides better compression efficiency for a given level of distortion, we report in Fig. 5 the RD curves of the different approaches. Before analyzing the results, it is noteworthy that the bit rate curves reported in Fig. 4 indicate that the DeepSqueeze approach tends to require a larger number of bits as the step-size decreases. Thus, for very fine quantization (i.e., small step-sizes since $\Delta = \mu$), the number of bits required tends to grow. By noting that DeepSqueeze does not employ differential quantization, the increase in bit rate with decreasing quantization step is expected. In fact, in this case, the input values at the compressor remain large (in particular, their effective range does not scale with the step-size $\mu$), leading to an increase in the bit rate with decreasing quantization step.

For each approach, the process for generating the rate-distortion curves in Fig. 5 consists of three main steps. First, we select a set of algorithm's hyperparameters ($\gamma, \zeta$, etc.). In particular, for ACTC [20], we select 10 values of the damping coefficient $\zeta$ uniformly spaced in the interval $[0.1, 0.9]$. For compressed ATC 2 [25] (and ChocoSGD [10]), we select 10 values of the mixing parameter $\gamma$ uniformly spaced in the interval $[0.1, 0.9]$. For the DEF-ATC approach, we create two sets of 5 uniformly spaced values in the interval $[0.1, 0.9]$ for the coefficients $\zeta$ and $\gamma$, and then consider all possible pairs from these sets. In the second step, and for each hyperparameter setting (i.e., each element in the sets of step 1), we generate the RD curve by following the same method as in Sec. V-B, namely, we vary the quantization step according to $\Delta = \mu^{\frac{1+\epsilon}{2}}$, where 25 values of $\epsilon$ linearly spaced in the interval $[10^{-3}, 1]$ are chosen. For each value of $\Delta$, distortion and rate are evaluated by averaging over 100 samples after convergence (expectations are computed empirically over 50 Monte Carlo
runs). Each RD curve then represents the performance of
the algorithm under a specific choice of hyperparameters. In
the last step, we generate and report in Fig. 5 the optimal
RD curve given by the convex hull of the empirical curves
collected in step 2. This process allows us to identify the best
possible performance trade-offs by varying the algorithms'
hyperparameters (γ, ζ, etc.) and the compression parameters,
namely, ε. Two learning step-size regimes are considered,
namely, μ = 0.01 (**left plot**) and μ = 0.001 (**right plot**).
By exploring the hyperparameter space and by considering
different step-size regimes, the results show that the DEF-
ATC approach can still achieve the closest performance to
the uncompressed approach with a relatively small number
of bits (approximately 2.2–2.4 bits/component/iteration are
required on average in steady-state), outperforming state-of-
the-art baselines.

D. *Beyond single-task estimation*

To illustrate the effectiveness of the DEF-ATC in solving
general optimization problems of the form (2), we conduct
an experiment in which agents seek consensus on certain
components of their estimates while seeking partial con-
sensus on others. In particular, we assume that we have
5 connected groups of agents, namely, $G_1 = \{1, \dots, 15\}$,
$G_2 = \{16, \dots, 30\}$, $G_3 = \{1, \dots, 10\}$, $G_4 = \{11, \dots, 20\}$,
and $G_5 = \{21, \dots, 30\}$, and that the model parameter vector
$w_k^*$ at agent $k$ is of the form $w_k^* = w_k^\bullet + \Delta_{k,i}$, where $\Delta_{k,i}$ is a
$10 \times 1$ vector with each component randomly generated from
the Gaussian distribution, with zero mean and variance 0.1.
The vectors $\{w_k^\bullet\}$ are generated in such a way that the first 5
components are common across the network, the components
6, 7, 8 are separately common for agents in $G_1$ and $G_2$, and
the last two components are separately common for agents in
groups $G_3, G_4$, and $G_5$. Then, we choose the constraints in (2)
(i.e., the matrix $U$) in order to enforce global consensus on
the first 5 components of the estimates and partial consensus
on the remaining components. The partial consensus is as
follows. Agents in $G_1$ should converge to a consensus on
components 6–8, and agents in $G_2$ should also converge to
a consensus on components 6–8, independently from the first
group. For the remaining two components 9 and 10, consensus
is enforced within each of the groups $G_3, G_4$, and $G_5$. The
matrix $A$ satisfying the conditions in (4) and having the same
sparsity structure as the link matrix in Fig. 1 (**left**) is found
by following the same approach as in [40]. We assume that
all agents employ the top-4 probabilistic uniform quantizer. In
Fig. 6, we report the network MSD (64) and average number
of bits/node/component (65) for 3 different values of the step-
size $\mu$. The results are averaged over 100 Monte-Carlo runs.
We set $\gamma = \zeta = 0.9$ and the quantizer parameter $\Delta = \mu$.
As in Sec. V-A, we observe, in the small step-size regime,
that the DEF-ATC achieves the same performance (which is
on the order of $\mu$) as the uncompressed ATC, and is able to
maintain a finite bit rate when the step-size approaches zero.
This illustrates the effectiveness of DEF-ATC in handling dif-
ferent problems, beyond single-task estimation. For illustration
purposes, we report in Sec. B of the supplementary material
the RD curves of DEF-ATC with probabilistic uniform and

<figure><img src="image_7.png" /><figcaption>Fig. 6. Beyond single-task estimation. (Left) Network MSD learning curves w.r.t. $w_k^\bullet$ in (2) for three different values of the step-size ($\mu_0 = 0.001$). (Right) Evolution of the average number of bits/node/component when the variable-rate scheme is used.</figcaption></figure>

top-4 probabilistic uniform quantization.

VI. CONCLUSION

In this work, we presented an approach for solving de-
centralized learning problems where agents have individual
risks to minimize subject to subspace constraints that require
the minimizers across the network to lie in low-dimensional
subspaces. This constrained formulation includes consensus or
single-task optimization as a special case, and allows for more
general task relatedness models such as multitask smoothness
and coupled optimization. To reduce the communication cost
among agents, we incorporated compression into the decen-
tralized approach by employing differential quantization at
the agent level to compress the iterates before communicating
them to neighbors. In addition, we implemented in the learning
approach an error-feedback mechanism, which consists of
incorporating the compression error into subsequent steps.
We then showed that, under some general conditions on the
compression noise, and for sufficiently small step-sizes $\mu$, the
resulting communication-efficient strategy is stable both in
terms of mean-square error and average bit rate. The results
showed that, in the small step-size regime, the iterates gen-
erated by the decentralized communication-efficient approach
achieve the same performance as the decentralized baseline
full-precision approach where no communication compression
is performed. Simulations illustrated the theoretical findings
and the effectiveness of the approach. Future research work
includes extending the optimal capacity problem (i.e., deter-
mining the minimum average bit-rate required to transmit
information while guaranteeing performance comparable to
the uncompressed variant) to our setting by incorporating
techniques from [48], [49], adapting their analysis to account
for stochastic gradients, unbounded initial states/gradients, and
fully-decentralized architectures.

# APPENDIX A

MEAN-SQUARE-ERROR ANALYSIS

Due to space limitations, we provide in this appendix a
sketch of the proof by outlining the logical progression, and by
providing a clear path from the assumptions to the conclusions.
For the detailed steps and intermediate calculations, we refer
the reader to Sec. C of the supplemental material. It is
worth mentioning that our proofs mirror those in [25] in
the sense that we also study the transformed iterates. The
key difference, however, is that we need to account for the
additional complexity introduced by error feedback and the
fact that we work under first-order differentiability conditions, rather than second-order as in [25].

By computing the second-order moments of both sides of (51) and (52), by using Assumption 1 on the individual and global costs, and Assumption 2 on the gradient noise processes, we can show that:

$$
\begin{align}
\mathbb{E} \| \tilde{\phi}_i^z \|^2 &\le \left( 1 - \mu\nu + \frac{\mu^2}{2} \delta_{\max}^2 \right) \mathbb{E} \left\| \tilde{\phi}_{i-1}^z \right\|^2 + \nonumber \\
&\quad \frac{2\mu v_2^2 \delta_{\max}^2 \| \mathcal{J}'_\epsilon \|^2}{\nu - \mu \delta_{\max}^2 / 2} \mathbb{E} \left\| \tilde{\phi}_{i-1}^z \right\|^2 + \nonumber \\
&\quad \frac{2\mu v_2^2 \delta_{\max}^2}{\nu - \mu \delta_{\max}^2 / 2} \mathbb{E} \| \mathcal{V}_\epsilon^{-1} z_{i-1} \|^2 + \mu^2 \mathbb{E} \| \bar{s}_i \|^2, \tag{66}
\end{align}
$$

and

$$
\begin{align}
\mathbb{E} \| \tilde{\phi}_i^z \|^2 &\le \left( \| \mathcal{J}_\epsilon'' \| + \frac{8\mu^2 v_2^2 v_L^2 \delta_{\max}^2 \| \mathcal{J}_\epsilon' \|^2}{1 - \| \mathcal{J}_\epsilon'' \|} \right) \mathbb{E} \| \tilde{\phi}_{i-1}^z \|^2 + \nonumber \\
&\quad \left( \frac{8\mu^2 \delta_{\max}^2 v_L^2}{1 - \| \mathcal{J}_\epsilon'' \|} \right) \mathbb{E} \| \tilde{\phi}_{i-1}^z \|^2 + \nonumber \\
&\quad \left( \frac{2\zeta^2 \gamma^2 \| I - \mathcal{J}_\epsilon \|^2}{1 - \| \mathcal{J}_\epsilon'' \|} + \frac{8\mu^2 \delta_{\max}^2 v_2^2 v_L^2}{1 - \| \mathcal{J}_\epsilon'' \|} \right) \mathbb{E} \| \mathcal{V}_\epsilon^{-1} z_{i-1} \|^2 \nonumber \\
&\quad + \frac{8\mu^2 \| \tilde{b} \|^2}{1 - \| \mathcal{J}_\epsilon'' \|} + \mu^2 \mathbb{E} \| \tilde{s}_i \|^2, \tag{67}
\end{align}
$$

$$
\begin{align}
&\text{where } \delta_{\max}^2 \triangleq \max_{1 \le k \le K} \delta_k^2, \quad v_L^2 \triangleq \|\mathcal{V}_{L,\epsilon}^{\top}\|^2, \quad v_1 = \|\mathcal{V}_{\epsilon}^{-1}\|, \nonumber \\
&\phantom{\text{where }} v_2 = \|\mathcal{V}_{\epsilon}\|, \nonumber \\
&\phantom{\text{where }} \tilde{b} \triangleq \mathcal{V}_{L,\epsilon}^{\top} \nabla_W J^{\text{glob}}(w^o), \tag{68}
\end{align}
$$

and where we used the fact that the 2-induced matrix norm of the block diagonal matrix $\mathcal{J}_\epsilon''$ in (46) satisfies $\|\mathcal{J}_\epsilon''\| \in (0, 1)$. In fact, by following similar arguments as in [6, pp. 516–517], we can first show that $\|\mathcal{J}_\epsilon''\|^2 \le (\rho(\mathcal{J}_\epsilon'') + \gamma\zeta\epsilon)^2$. We can also show that $\rho(\mathcal{J}_\epsilon'') \le (1 - \gamma\zeta) + \gamma\zeta\rho(\mathcal{J}_\epsilon)$. Using the fact that $\rho(\mathcal{J}_\epsilon) \in (0, 1)$ from [40, Lemma 2] and the fact that $\gamma\zeta \in (0, 1]$, we obtain $\rho(\mathcal{J}_\epsilon'') \in (0, 1)$. Moreover, since $\rho(\mathcal{J}_\epsilon'') + \gamma\zeta\epsilon$ is non-negative, we can show that:

$$
\| \mathcal{J}_{\epsilon}'' \| \le (1 - \gamma \zeta) + \gamma \zeta \rho(\mathcal{J}_{\epsilon}) + \gamma \zeta \epsilon = 1 - \gamma \zeta (1 - \rho(\mathcal{J}_{\epsilon}) - \epsilon). \quad (69)
$$

This identity will be used in the subsequent analysis. Returning to the result (67), and under Assumption 1, the norm of gradient at the optimal solution $w^o$, namely, $\|\nabla_W J^{\text{glob}}(w^o)\|^2$, is bounded and we can write $\|\tilde{b}\|^2 = O(1)$.

For the gradient noise, by following similar arguments as in [6, Chap. 9] and by using Assumption 2, we can show that:

$$
\mathbb{E}\|\bar{s}_i\|^2 + \mathbb{E}\|\tilde{s}_i\|^2 = \mathbb{E}\|\mathcal{V}_\epsilon^{-1}s_i\|^2 \le v_1^2 \beta_{s,\max}^2 \mathbb{E}\|\tilde{\mathcal{W}}_{i-1}\|^2 + v_2^2 \sigma_s^2, \quad (70)
$$

where $\beta_{s,\max}^2 = \max_{1 \le k \le K} \beta_{s,k}^2$, and $\bar{\sigma}_s^2 = \sum_{k=1}^K \sigma_{s,k}^2$. Using expression (33), the fact that $\tilde{\phi}_{i-1} = \tilde{\phi}_{i-1}^z + z_{i-1}$, the Jordan decomposition of $\mathcal{A}'$ in (45), and the sub-multiplicative property of norms, we can show that:

$$
\begin{align}
\mathbb{E}\|\bar{s}_i\|^2 + \mathbb{E}\|\tilde{s}_i\|^2 &\le 2v_1^2\beta_{s,\max}^2 v_2^2 (\mathbb{E}\|\tilde{\phi}_{i-1}^z\|^2 + \mathbb{E}\|\tilde{\phi}_{i-1}^z\|^2) + \nonumber \\
&\quad 2v_1^2\beta_{s,\max}^2 v_2^2 \mathbb{E}\|\mathcal{V}_\epsilon^{-1}z_{i-1}\|^2 + v_1^2\sigma_s^2. \tag{71}
\end{align}
$$

Now, for the compression noise vector $z_i$ in (40), we have:

$$
\mathbb{E} \| \mathcal{V}_{\epsilon}^{-1} z_i \|^2 \le \zeta^2 v_1^2 \left( \sum_{k=1}^{K} \mathbb{E} \| z_{k,i} \|^2 \right). \quad (72)
$$

From (19) and Assumption 3, and since $\psi_{k,i} - \phi_{k,i-1} = \tilde{\phi}_{k,i-1} - \tilde{\psi}_{k,i}$, we can write $\mathbb{E}\|z_{k,i}\|^2 \le \beta_{c,k}^2 \mathbb{E}\|\tilde{\phi}_{k,i-1} - \tilde{\psi}_{k,i} + z_{k,i-1}\|^2 + \sigma_{c,k}^2$ and, therefore,

$$
\sum_{k=1}^{K} \mathbb{E} \| z_{k,i} \|^2 \le \beta_{c,\max}^2 \mathbb{E} \| \tilde{\phi}_{i-1} - \tilde{\psi}_i + \frac{1}{\zeta} z_{i-1} \|^2 + \bar{\sigma}_c^2, \quad (73)
$$

where $\beta_{c,\max}^2 = \max_{1 \le k \le K} \{\beta_{c,k}^2\}$ and $\bar{\sigma}_c^2 = \sum_{k=1}^K \sigma_{c,k}^2$. Since the analysis is facilitated by transforming the network vectors into the Jordan decomposition basis of $\mathcal{A}'$, we show that:

$$
\sum_{k=1}^{K} \mathbb{E} \| z_{k,i} \|^2 \stackrel{(73)}{\le} v_2^2 \beta_{c,\max}^2 \left( \mathbb{E} \| \bar{\chi}_i \|^2 + \mathbb{E} \| \tilde{\chi}_i \|^2 \right) + \bar{\sigma}_c^2, \quad (74)
$$

where $\bar{\chi}_i \triangleq \mathcal{U}^\top(\tilde{\phi}_{i-1} - \tilde{\psi}_i + \zeta^{-1}z_{i-1})$ and $\tilde{\chi}_i \triangleq \mathcal{V}_{L,\epsilon}^\top(\tilde{\phi}_{i-1} - \tilde{\psi}_i + \zeta^{-1}z_{i-1})$. By combining (72) and (74), we obtain:

$$
\mathbb{E} \| \mathcal{V}_\epsilon^{-1} z_i \|^2 \le \zeta^2 v_1^2 v_2^2 \beta_{c,\max}^2 [\mathbb{E} \| \bar{\chi}_i \|^2 + \mathbb{E} \| \tilde{\chi}_i \|^2] + \zeta^2 v_1^2 \bar{\sigma}_c^2. \quad (75)
$$

We focus now on deriving the recursions that allow to examine the time-evolution of the transformed vectors $\bar{\chi}_i$ and $\tilde{\chi}_i$. Subtracting $\tilde{\phi}_{i-1}$ from both sides of (31), adding $z_{i-1}$, and using (33), we can write:

$$
\begin{align}
\tilde{\phi}_{i-1} - \tilde{\psi}_i + \zeta^{-1} z_{i-1} &\stackrel{(a)}{=} (I_M - \mathcal{A}') \tilde{\phi}_{i-1}^z - \frac{\mu}{\zeta} g_{i-1} + \frac{\mu}{\zeta} s_i + \nonumber \\
&\quad ((1 + \zeta^{-1}) I_M - \mathcal{A}') z_{i-1}, \tag{76}
\end{align}
$$

where in (a) we used the fact that $\tilde{\phi}_{i-1} = \tilde{\phi}_{i-1}^z + z_{i-1}$. By multiplying both sides of (76) by $\mathcal{V}_\epsilon^{-1}$ and by using (47)–(50), and the Jordan decomposition of the matrix $\mathcal{A}'$, we obtain:

$$
\begin{bmatrix} \bar{\chi}_i \\ \tilde{\chi}_i \end{bmatrix} = \begin{bmatrix} 0 & 0 \\ 0 & I_{M-P} - \mathcal{J}_\epsilon' \end{bmatrix} \begin{bmatrix} \tilde{\phi}_{i-1}^z \\ \tilde{\phi}_{i-1}^{\tilde{z}} \end{bmatrix} - \frac{\mu}{\zeta} \begin{bmatrix} \bar{g}_{i-1} \\ \tilde{g}_{i-1} \end{bmatrix} + \\
+ \frac{\mu}{\zeta} \begin{bmatrix} \bar{s}_i \\ \tilde{s}_i \end{bmatrix} + \begin{bmatrix} \zeta^{-1} I_P & 0 \\ 0 & (1 + \zeta^{-1}) I_{M-P} - \mathcal{J}_\epsilon' \end{bmatrix} \begin{bmatrix} \bar{z}_{i-1} \\ \tilde{z}_{i-1} \end{bmatrix}.
$$

Now, by using similar arguments as those used to establish inequalities (66) and (67), we can verify that:

$$
\begin{align}
\mathbb{E} \| \bar{\chi}_i \|^2 &\le \left( \frac{2}{\zeta^2} + \frac{8\mu^2 v_2^2 \delta_{\max}^2}{\zeta^2} \right) \mathbb{E} \| \mathcal{V}_\epsilon^{-1} z_{i-1} \|^2 + \nonumber \\
&\quad \frac{4\mu^2 \delta_{\max}^2}{\zeta^2} \mathbb{E} \| \tilde{\phi}_{i-1}^z \|^2 + \frac{8\mu^2 v_2^2 \delta_{\max}^2 \| \mathcal{J}_\epsilon' \|^2}{\zeta^2} \mathbb{E} \| \tilde{\phi}_{i-1}^z \|^2 + \frac{\mu^2}{\zeta^2} \mathbb{E} \| \bar{s}_i \|^2 \tag{77}
\end{align}
$$

and

$$
\begin{align}
\mathbb{E} \| \tilde{\chi}_i \|^2 & \le \left( 2 \|(1 + \zeta^{-1}) I - \mathcal{J}_\epsilon' \|^2 + \frac{16\mu^2 v_2^2 v_L^2 \delta_{\max}^2}{\zeta^2} \right) \mathbb{E} \| \mathcal{V}_\epsilon^{-1} z_{i-1} \|^2 \nonumber \\
& \quad + \left( 4 \| I - \mathcal{J}_\epsilon' \|^2 + \frac{16\mu^2 v_2^2 v_L^2 \delta_{\max}^2 \| \mathcal{J}_\epsilon' \|^2}{\zeta^2} \right) \mathbb{E} \| \tilde{\phi}_{i-1}^z \|^2 \nonumber \\
& \quad + \frac{16\mu^2 \delta_{\max}^2 v_L^2}{\zeta^2} \mathbb{E} \| \tilde{\phi}_{i-1}^z \|^2 + \frac{16\mu^2}{\zeta^2} \| \tilde{b} \|^2 + \frac{\mu^2}{\zeta^2} \mathbb{E} \| \tilde{s}_i \|^2. \tag{78}
\end{align}
$$

By combining expressions (77) and (78), by using the result of the combination and the bound (71) in (75), and by using (71) in (66) and (67), we finally find that $\mathbb{E}\|\tilde{\phi}_i^z\|^2$, $\mathbb{E}\|\tilde{\phi}_i^z\|^2$, and $\mathbb{E}\|\mathcal{V}_\epsilon^{-1}z_i\|^2$ are coupled and recursively bounded as:
$$ \begin{bmatrix} \mathbb{E}\|\tilde{\phi}_i^z\|^2 \\ \mathbb{E}\|\tilde{\phi}_i^z\|^2 \\ \mathbb{E}\|\mathcal{V}_\epsilon^{-1}z_i\|^2 \end{bmatrix} \preceq \Gamma \begin{bmatrix} \mathbb{E}\|\tilde{\phi}_{i-1}^z\|^2 \\ \mathbb{E}\|\tilde{\phi}_{i-1}^z\|^2 \\ \mathbb{E}\|\mathcal{V}_\epsilon^{-1}z_{i-1}\|^2 \end{bmatrix} + \begin{bmatrix} l \\ m \\ n \end{bmatrix}, \quad (79) $$

where $\Gamma$ is the $3 \times 3$ matrix given by:

$$ \Gamma = \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & j \end{bmatrix}, \quad (80) $$

with $a = 1 - \mu\nu + O(\mu^2)$, $b = O(\mu)$, $c = O(\mu)$, $d = O(\mu^2)$, $e = \|\mathcal{J}_\epsilon''\| + O(\mu^2)$, $f = \frac{2\zeta^2\gamma^2\|I - \mathcal{J}_\epsilon\|}{1 - \|\mathcal{J}_\epsilon''\|} + O(\mu^2)$, $g = O(\mu^2)$, $h = 4\zeta^2\beta_{c,\max}^2 v_1^2 v_2^2 \|I - \mathcal{J}_\epsilon'\|^2 + O(\mu^2)$, $j = 2\beta_{c,\max}^2 v_1^2 v_2^2 (1 + \zeta^2\|(1 + \zeta^{-1})I - \mathcal{J}_\epsilon'\|^2) + O(\mu^2)$, $l = \mu^2 v_1^2 \bar{\sigma}_s^2 = O(\mu^2)$, $m = O(\mu^2)$, $n = \zeta^2 v_1^2 \bar{\sigma}_c^2 + O(\mu^2)$. If the matrix $\Gamma$ is stable, i.e., $\rho(\Gamma) < 1$, then by iterating (79), we arrive at:

$$ \limsup_{i \to \infty} \begin{bmatrix} \mathbb{E}\|\tilde{\phi}_i^z\|^2 \\ \mathbb{E}\|\tilde{\phi}_i^z\|^2 \\ \mathbb{E}\|\mathcal{V}_\epsilon^{-1}z_i\|^2 \end{bmatrix} \preceq (I_3 - \Gamma)^{-1} \begin{bmatrix} l \\ m \\ n \end{bmatrix}. \quad (81) $$

Generally speaking, and since the spectral radius of a matrix is upper bounded by its 1-norm, the matrix $\Gamma$ is stable if:

$$ \rho(\Gamma) \le \max\{|a| + |d| + |g|, |b| + |e| + |h|, |c| + |f| + |j|\} < 1. \quad (82) $$

Since $\nu > 0$, a sufficiently small $\mu$ can make $|a| + |d| + |g| < 1$. For $|b| + |e| + |h|$, observe that if $\zeta$ and $\gamma$ are chosen such that:

$$ \|\mathcal{J}_\epsilon''\| + 4\zeta^2 v_1^2 v_2^2 \beta_{c,\max}^2 \|I - \mathcal{J}_\epsilon'\|^2 < 1, \quad (83) $$

then $|b| + |e| + |h| < 1$ for sufficiently small $\mu$. Finally, for $|c| + |f| + |j|$, observe that if $\beta_{c,\max}^2$, $\gamma$, and $\zeta$ are such that:

$$ \frac{2\gamma^2\zeta^2\|I - \mathcal{J}_\epsilon\|^2}{1 - \|\mathcal{J}_\epsilon''\|} + 2\beta_{c,\max}^2 v_1^2 v_2^2 (1 + \zeta^2\|(1 + \zeta^{-1})I - \mathcal{J}_\epsilon'\|^2) < 1, \quad (84) $$

then $|c| + |f| + |j| < 1$ for sufficiently small $\mu$. It is therefore clear that $\rho(\Gamma) < 1$ for sufficiently small $\mu$ and for $\zeta \in (0, 1]$, $\gamma \in (0, 1]$, and $\beta_{c,\max}^2$ satisfying (83) and (84). In the following, we analyze conditions (83) and (84). By following similar arguments as in [6, pp. 516–517], we can establish the following identities:

$$ \|I - \mathcal{J}_\epsilon'\|^2 \stackrel{(45)}{=} \|\gamma(I - \mathcal{J}_\epsilon)\|^2 \le \gamma^2(\rho(I - \mathcal{J}_\epsilon) + \epsilon)^2, \quad (85) $$

$$ \begin{aligned} \|(1 + \zeta^{-1})I - \mathcal{J}_\epsilon'\|^2 \stackrel{(45)}{=} & \|(\zeta^{-1} + \gamma)I - \gamma\mathcal{J}_\epsilon\| \\ & \le (\zeta^{-1} + \gamma) - \gamma(\rho(\mathcal{J}_\epsilon) + \epsilon), \end{aligned} \quad (86) $$

where $\rho(I - \mathcal{J}_\epsilon) \in (0, 2)$ since $\rho(\mathcal{J}_\epsilon) \in (0, 1)$. By using the bounds (69) and (85) into (83), and by using the fact that $\gamma\zeta$ must be in $(0, 1]$, we obtain condition (53) on $\gamma\zeta$. For the second condition (84), by using (69), (85), and (86), we find that (84) is guaranteed to be satisfied under condition (54).

Under conditions (53) and (54), $\rho(\Gamma) < 1$, and consequently, the matrix $\Gamma$ is stable. Moreover, it holds that:

$$ (I - \Gamma)^{-1} = \begin{bmatrix} \frac{1}{\mu\nu} & O(1) & O(1) \\ O(\mu) & O(1) & O(1) \\ O(\mu) & O(1) & O(1) \end{bmatrix}. \quad (87) $$

Now, using (87) into (81), we arrive at:

$$ \limsup_{i \to \infty} \begin{bmatrix} \mathbb{E}\|\tilde{\phi}_i^z\|^2 \\ \mathbb{E}\|\tilde{\phi}_i^z\|^2 \\ \mathbb{E}\|\mathcal{V}_\epsilon^{-1}z_i\|^2 \end{bmatrix} \preceq \begin{bmatrix} \mu v_1^2 \frac{\bar{\sigma}_s^2}{\nu} + O(\mu^2) + \bar{\sigma}_c^2 O(1) \\ O(\mu^2) + \bar{\sigma}_c^2 O(1) \\ O(\mu^2) + \bar{\sigma}_c^2 O(1) \end{bmatrix}. \quad (88) $$

By using (88) and by noting that $\limsup_{i \to \infty} \mathbb{E}\|\tilde{\phi}_i^z\|^2 \le \limsup_{i \to \infty} \|\mathcal{V}_\epsilon\|^2[\mathbb{E}\|\tilde{\phi}_i^z\|^2 + \mathbb{E}\|\tilde{\phi}_i^z\|^2]$, we can finally conclude that (55) holds. Result (56) follows from (55) by replacing $\bar{\sigma}_c^2 O(1)$ by $O(\mu^{1+\epsilon})$.

To establish (57), we first show that:

$$ \limsup_{i \to \infty} \mathbb{E}\|\tilde{\mathcal{W}}_i - \tilde{\phi}_i^z\|^2 = O(\mu^{1+\epsilon}). \quad (89) $$

By subtracting $\tilde{\mathcal{W}}_i$ and $\tilde{\phi}_i^z$ and by using (33), (44), and (45), we can show that:

$$ \begin{aligned} & \limsup_{i \to \infty} \mathbb{E}\|\tilde{\mathcal{W}}_i - \tilde{\phi}_i^z\|^2 \\ & \le \limsup_{i \to \infty} \left[ 2\|\mathcal{V}_{R,\epsilon}(\mathcal{J}_\epsilon' - I)\|^2 \mathbb{E}\|\tilde{\phi}_i^z\|^2 + 2\|\mathcal{V}_\epsilon\Lambda_\epsilon'\|^2 \mathbb{E}\|\mathcal{V}_\epsilon^{-1}z_i\|^2 \right]. \end{aligned} \quad (90) $$

Now, using (88) with $\bar{\sigma}_c^2 O(1)$ replaced by $O(\mu^{1+\epsilon})$, we conclude that (89) holds. To establish (57), note that, by adding and subtracting $\tilde{\phi}_i^z$ to $\tilde{\mathcal{W}}_i$, by using Jensen's ($|\mathcal{E}x| \le \mathcal{E}|x|$) and Holder's ($|\mathcal{E}|x^\top y| \le (|\mathcal{E}|x|^p)^{\frac{1}{p}} (|\mathcal{E}|y|^q)^{\frac{1}{q}}$ when $1/p + 1/q = 1$) inequalities, we can write:

$$ \mathbb{E}\|\tilde{\mathcal{W}}_i\|^2 \le \mathbb{E}\|\tilde{\mathcal{W}}_i - \tilde{\phi}_i^z\|^2 + \mathbb{E}\|\tilde{\phi}_i^z\|^2 + 2\sqrt{\mathbb{E}\|\tilde{\mathcal{W}}_i - \tilde{\phi}_i^z\|^2 \mathbb{E}\|\tilde{\phi}_i^z\|^2} \quad (91) $$

and, hence, from (56) and (89), we get $\limsup_{i \to \infty} \mathbb{E}\|\tilde{\mathcal{W}}_i\|^2 \le \limsup_{i \to \infty} \mathbb{E}\|\tilde{\phi}_i^z\|^2 + O(\mu^{1+\epsilon})$.

The analysis can be simplified in settings where the compression operators $\{C_k\}$ are such that $\beta_{c,k}^2 = 0$, $\forall k$ (we refer the reader to the detailed proof in the supplementary material).

## APPENDIX B
### BIT RATE STABILITY

Equation (61) follows from Lemma 1 and Table I (row 3, col. 3–4). Invoking similar arguments to the ones used to establish Theorem 2 in [25], the individual summands in (59) can be upper bounded by:

$$ 2 + \log_2 \left( \frac{\ln \left( 1 + \frac{\omega}{\eta} \sqrt{\mathbb{E}\|\chi_{k,i}\|^2} \right)}{2 \ln \left( \omega + \sqrt{1 + \omega^2} \right)} + 2 \right). \quad (92) $$

By combining expressions (77) and (78), by using the bound (71), and by using (88) and (61), we can show that:

$$ \limsup_{i \to \infty} \mathbb{E}\|\chi_{k,i}\|^2 \le \kappa_1 \mu^{1+\epsilon} + \kappa_2 \mu^2, \quad (93) $$

for sufficiently small $\mu$, and where $\kappa_1$ and $\kappa_2$ are some positive constants independent of $\mu$. Applying the limit superior to (92), using the fact that (92) is a continuous and increasing function in the argument $\mathbb{E}\|\chi_{k,i}\|^2$, and using (93), in view of (61), we find that each summand in (59) is $O(1)$, which in turn implies (62).
REFERENCES

[1] R. Nassif, S. Vlaski, M. Carpentiero, V. Matta, and A. H. Sayed, "Differential error feedback for communication-efficient decentralized optimization," in *Proc. IEEE Sens. Array Multichannel Signal Process. Workshop*, Corvallis, OR, USA, Jul. 2024.

[2] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. Y. Arcas, "Communication-efficient learning of deep networks from decentralized data," in *Proc. Int. Conf. Artif. Intell. Stat.*, Ft. Lauderdale, FL, USA, 2017, vol. 54, pp. 1273-1282.

[3] T. Li, A. K. Sahu, A. S. Talwalkar, and V. Smith, "Federated learning: Challenges, methods, and future directions," *IEEE Signal Process. Mag.*, vol. 37, pp. 50-60, May 2020.

[4] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic, "QSGD: Communication-efficient SGD via gradient quantization and encoding," in *Proc. Adv. Neural Inf. Process. Syst.*, Long Beach, CA, USA, 2017, pp. 1709-1720.

[5] V. Smith, C.-K. Chiang, M. Sanjabi, and A. S. Talwalkar, "Federated multi-task learning," in *Proc. Adv. Neural Inf. Process. Syst.*, Long Beach, CA, USA, Dec. 2017, vol. 30.

[6] A. H. Sayed, "Adaptation, learning, and optimization over networks," *Found. Trends Mach. Learn.*, vol. 7, no. 4-5, pp. 311-801, 2014.

[7] A. H. Sayed, S.-Y. Tu, J. Chen, X. Zhao, and Z. Towfic, "Diffusion strategies for adaptation and learning over networks," *IEEE Signal Process. Mag.*, vol. 30, no. 3, pp. 155-171, May 2013.

[8] R. Nassif, S. Vlaski, C. Richard, J. Chen, and A. H. Sayed, "Multitask learning over graphs: An approach for distributed, streaming machine learning," *IEEE Signal Process. Mag.*, vol. 37, no. 3, pp. 14-25, 2020.

[9] D. Kovalev, A. Koloskova, M. Jaggi, P. Richtarik, and S. Stich, "A linearly convergent algorithm for decentralized optimization: Sending less bits for free!", in *Proc. Int. Conf. Artif. Intell. Stat.*, Virtual, 2021, pp. 4087-4095.

[10] A. Koloskova, S. Stich, and M. Jaggi, "Decentralized stochastic optimization and gossip algorithms with compressed communication," in *Proc. Int. Conf. Mach. Learn.*, 2019, vol. 97, pp. 3478-3487.

[11] R. Nassif, S. Vlaski, and A. H. Sayed, "Adaptation and learning over networks under subspace constraints-Part II: Performance analysis," *IEEE Trans. Signal Process.*, vol. 68, pp. 2948-2962, 2020.

[12] X. Cao, T. Başar, S. Diggavi, Y. C. Eldar, K. B. Letaief, H. V. Poor, and J. Zhang, "Communication-efficient distributed learning: An overview," *IEEE J. Sel. Areas Commun.*, vol. 41, no. 4, pp. 851-873, 2023.

[13] A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich, "A unified theory of decentralized SGD with changing topology and local updates," in *Proc. Int. Conf. Mach. Learn.*, Virtual, Jul. 2020, vol. 119, pp. 5381-5393.

[14] Y. Liu, T. Lin, A. Koloskova, and S. U. Stich, "Decentralized gradient tracking with local steps," Available as arXiv:2301.01313v1, 2023.

[15] T. C. Aysal, M. J. Coates, and M. G. Rabbat, "Distributed average consensus with dithered quantization," *IEEE Trans. Signal Process.*, vol. 56, no. 10, pp. 4905-4918, 2008.

[16] A. Beznosikov, S. Horvath, P. Richtárik, and M. H. Safaryan, "On biased compression for distributed learning," *J. Mach. Learn. Res.*, vol. 24, no. 276, pp. 1-50, 2023.

[17] A. Nedic, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis, "Distributed subgradient methods and quantization effects," in *Proc. IEEE Conf. Decis. Control*, Cancun, Mexico, Dec. 2008, pp. 4177-4184.

[18] X. Zhao, S.-Y. Tu, and A. H. Sayed, "Diffusion adaptation over networks under imperfect information exchange and non-stationary data," *IEEE Trans. Signal Process.*, vol. 60, no. 7, pp. 3460-3475, 2012.

[19] D. Thanou, E. Kokiopoulou, Y. Pu, and P. Frossard, "Distributed average consensus with quantization refinement," *IEEE Trans. Signal Process.*, vol. 61, no. 1, pp. 194-205, 2013.

[20] M. Carpentiero, V. Matta, and A. H. Sayed, "Distributed adaptive learning under communication constraints," *IEEE Open J. Signal Process.*, vol. 5, pp. 321-358, 2024.

[21] M. Carpentiero, V. Matta, and A. H. Sayed, "Compressed regression over adaptive networks," To appear in *IEEE Trans. Signal Inf. Process. Netw.* Available as arXiv:2304.03638v1, 2024.

[22] A. Reisizadeh, A. Mokhtari, H. Hassani, and R. Pedarsani, "An exact quantized decentralized gradient descent algorithm," *IEEE Trans. Signal Process.*, vol. 67, no. 19, pp. 4934-4947, 2019.

[23] H. Taheri, A. Mokhtari, H. Hassani, and R. Pedarsani, "Quantized decentralized stochastic learning over directed graphs," in *Proc. Int. Conf. Mach. Learn.*, Jul. 2020, vol. 119, pp. 9324-9333.

[24] N. Michelusi, G. Scutari, and C.-S. Lee, "Finite-bit quantization for distributed algorithms with linear convergence," *IEEE Trans. Inf. Theory.*, vol. 68, no. 11, pp. 7254-7280, 2022.

[25] R. Nassif, S. Vlaski, M. Carpentiero, V. Matta, M. Antonini, and A. H. Sayed, "Quantization for decentralized learning under subspace constraints," *IEEE Trans. Signal Process.*, vol. 71, pp. 2320-2335, 2023.

[26] H. Zhao, B. Li, Z. Li, P. Richtarik, and Y. Chi, "BEER: Fast O(1/T) rate for decentralized nonconvex optimization with communication compression," in *Proc. Adv. Neural Inf. Process. Syst.*, New Orleans, Louisiana, USA, 2022, vol. 35, pp. 31653-31667.

[27] N. Singh, X. Cao, S. Diggavi, and T. Başar, "Decentralized multi-task stochastic optimization with compressed communications," *Automatica*, vol. 159, pp. 111363, 2024.

[28] X. Liu, Y. Li, R. Wang, J. Tang, and M. Yan, "Linear convergent decentralized optimization with compression," in *Proc. Int. Conf. Learn. Represent.*, Virtual, May 2021.

[29] N. Singh, D. Data, J. George, and S. Diggavi, "SPARQ-SGD: Event-triggered and compressed communication in decentralized optimization," *IEEE Trans. Automat. Contr.*, vol. 68, no. 2, pp. 721-736, 2023.

[30] N. Singh, D. Data, J. George, and S. Diggavi, "SQuARM-SGD: Communication-efficient momentum SGD for decentralized optimization," in *Proc. IEEE Int. Symp. Inf. Theory*, Melbourne, Victoria, Australia, 2021, pp. 1212-1217.

[31] H. Tang, S. Gan, C. Zhang, T. Zhang, and J. Liu, "Communication compression for decentralized training," in *Proc. Adv. Neural Inf. Process. Syst.*, Montreal, Canada, Dec. 2018, vol. 31, pp. 7663-7673.

[32] S. P. Karimireddy, Q. Rebjock, S. Stich, and M. Jaggi, "Error feedback fixes SignSGD and other gradient compression schemes," in *Proc. Int. Conf. Mach. Learn.*, Long Beach, CA, USA, Jun. 2019, vol. 97, pp. 3252-3261.

[33] H. Tang, X. Lian, S. Qiu, L. Yuan, C. Zhang, T. Zhang, and J. Liu, "DeepSqueeze: Decentralization meets error-compensated compression," Available as arXiv:1907.07346, 2019.

[34] A. H. Sayed, *Inference and Learning from Data*, 3 vols., Cambridge University Press, 2022.

[35] A. Nedic and A. Ozdaglar, "Distributed subgradient methods for multi-agent optimization," *IEEE Trans. Automat. Contr.*, vol. 54, no. 1, pp. 48-61, Jan. 2009.

[36] D. P. Bertsekas, "A new class of incremental gradient methods for least squares problems," *SIAM J. Optim*, vol. 7, no. 4, pp. 913-926, 1997.

[37] A. G. Dimakis, S. Kar, J. M. F. Moura, M. G. Rabbat, and A. Scaglione, "Gossip algorithms for distributed signal processing," *Proc. IEEE*, vol. 98, no. 11, pp. 1847-1864, 2010.

[38] V. Kekatos and G. B. Giannakis, "Distributed robust power system state estimation," *IEEE Trans. Power Syst.*, vol. 28, no. 2, pp. 1617-1626, 2013.

[39] R. Nassif, S. Vlaski, C. Richard, and A. H. Sayed, "Learning over multitask graphs-Part I: Stability analysis," *IEEE Open Journal of Signal Processing*, vol. 1, pp. 28-45, 2020.

[40] R. Nassif, S. Vlaski, and A. H. Sayed, "Adaptation and learning over networks under subspace constraints-Part I: Stability analysis," *IEEE Trans. Signal Process.*, vol. 68, pp. 1346-1360, 2020.

[41] J. Plata-Chaves, A. Bertrand, M. Moonen, S. Theodoridis, and A. M. Zoubir, "Heterogeneous and multitask wireless sensor networks – Algorithms, applications, and challenges," *IEEE J. Sel. Top. Signal Process.*, vol. 11, no. 3, pp. 450-465, 2017.

[42] P. Di Lorenzo, S. Barbarossa, and S. Sardellitti, "Distributed signal processing and optimization based on in-network subspace projections," *IEEE Trans. Signal Process.*, vol. 68, pp. 2061-2076, 2020.

[43] J. F. C. Mota, J. M. F. Xavier, P. M. Q. Aguiar, and M. Püschel, "Distributed optimization with local domains: Applications in MPC and network flows," *IEEE Trans. Automat. Contr.*, vol. 60, no. 7, pp. 2004-2009, 2015.

[44] S. A. Alghunaim and A. H. Sayed, "Distributed coupled multiagent stochastic optimization," *IEEE Trans. Automat. Contr.*, vol. 65, no. 1, pp. 175-190, 2020.

[45] S. U. Stich, J.-B. Cordonnier, and M. Jaggi, "Sparsified SGD with memory," in *Proc. Adv. Neural Inf. Process. Syst.*, Montréal, Canada, 2018, pp. 4452-4463.

[46] D. Basu, D. Data, C. Karakus, and S. Diggavi, "Qsparse-local-SGD: Distributed SGD with quantization, sparsification, and local computations," in *Proc. Adv. Neural Inf. Process. Syst.*, Vancouver, Canada, 2019, pp. 14695-14706.

[47] R. A. Horn and C. R. Johnson, *Matrix Analysis*, Cambridge University Press, 2012.

[48] C.-Y. Lin, V. Kostina, and B. Hassibi, "Differentially quantized gradient methods," *IEEE Trans. Inf. Theory.*, vol. 68, no. 9, pp. 6078-6097, 2022.

[49] A. Mitra, L. Ye, and V. Gupta, "Towards model-free LQR control over rate-limited channels," in *Proc. Ann. Learn. Dyn. Control Conf.*, Oxford, UK, Jul. 2024, vol. 242, pp. 1253-1265.