# Communication-efficient Exact Diffusion for Decentralized Learning

Gustavo Faia, Stefan Vlaski, Roula Nassif

► To cite this version:

Gustavo Faia, Stefan Vlaski, Roula Nassif. Communication-efficient Exact Diffusion for Decentralized Learning. ICASSP 2025 - 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Apr 2025, Hyderabad, France. pp.1-5, 10.1109/ICASSP49660.2025.10888313. hal-05227750

HAL Id: hal-05227750

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

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>

Distributed under a Creative Commons Attribution 4.0 International License
# Communication-efficient Exact Diffusion for Decentralized Learning

Gustavo Faia

Escola Politécnica

Universidade de São Paulo, Brazil

Stefan Vlaski

Imperial College London, UK

Roula Nassif

Université Côte d'Azur

13S Laboratory, CNRS, France

**Abstract**—Communication-efficient approaches for decentralized learning rely on the exchange of quantized signals coupled with local updates. In this context, differential quantization is an effective technique to mitigate the negative impact of quantization by leveraging correlations between subsequent iterates. In addition, error-feedback, which consists of incorporating the quantization error into subsequent steps, is a powerful mechanism to compensate for the bias caused by the quantization. On the other hand, in recent years, several methods have been proposed for correcting inherent bias present in decentralized learning implementations. While the theoretical benefits of decentralized bias-correction methods are clear, their practical implementation in real-world networks with constrained communication resources may generally require further investigation. In this work, we propose and study a new decentralized communication-efficient learning approach that blends bias-correction with differential quantization and error-feedback. The results show that, under some general conditions on the quantization noise, and for sufficiently small step-sizes $\mu$, it is possible to keep the estimation errors small (on the order of $\mu$) in steady-state, while maintaining finite bit rates. Simulations are provided to illustrate the theoretical findings.

**Index Terms**—Error-feedback, differential quantization, bias-correction, communication-efficient learning, decentralized learning, exact diffusion.

## I. INTRODUCTION

Data is increasingly being collected in distributed and streaming manner, in environments where communication efficiency 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 [1]–[6]. In federated learning, multiple devices (also referred to as nodes or agents) hold local data, and collaboratively train a shared model under the orchestration of a central server that coordinates the process and aggregates the model updates (such as gradients) from each client. By keeping training data on local devices, federated learning reduces the risk of sharing sensitive data. On the other hand, decentralized learning is an alternative learning paradigm that enables collaborative model training without relying on a central server. The prevailing setting typically assumes a communication network topology where each agent can directly communicate with its neighboring agents. Such decentralized implementations reduce the communication burden since model updates are exchanged locally between agents without relying on a central coordinator [4]–[8].

In traditional decentralized implementations, agents need to exchange (possibly high-dimensional and dense) parameter vectors at every iteration of the learning algorithm, leading to prohibitively high communication costs, particularly in resource-constrained networks. Several strategies have been proposed to reduce the communication

This work was conducted during the research visit of G. Faia to Université Côte d'Azur. The work of G. Faia and R. Nassif was supported 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 and by the ANR JCJC grant ANR-22-CE23-0015-01 (CEDRO project). Emails: gustavofaiafagundes@gmail.com, s.vlaski@imperial.ac.uk, roula.nassif@unice.fr.

overhead, with quantization being a promising approach. Quantization involves compressing the information that needs to be communicated, thus reducing the size of the data being transmitted. While quantization offers a promising solution, its successful implementation requires designing the quantization operators and the learning algorithms jointly in order to prevent the quantization error from significantly deteriorating the learning performance [7], [8], [9]–[14]. Among the techniques employed to mitigate the impact of quantization, differential quantization and error-feedback are noteworthy. In differential quantization, agents communicate quantized versions of the differences between current estimates and their predictions based on previous iterations [8], [10]–[12], [15]. Error-feedback, on the other hand, consists of locally storing the quantization error (i.e., the difference between the input and output of the quantizer), and incorporating it back into the next iteration [16]–[18]. While it was common to apply these techniques separately, the work [14] shows how to blend them in order to obtain a communication-efficient decentralized learning technique.

On the other hand, while a fusion center has access to all data in centralized implementations, agents in decentralized implementations perform local computations and can only exchange data with their immediate neighbors [4]–[6], [19]. This localized communication can limit the amount of global information available to a single agent, potentially introducing a bias in the network's steady-state performance, and leading to severe performance degradation for sparsely connected networks [20]. Thus, it becomes important to employ decentralized approaches that do not compromise the performance levels typically achieved by centralized implementations. Several approaches have been studied for bias-correction in the context of consensus [21]–[23], and more recently, multitask [24] optimization, by leveraging arguments based on Lagrangian duality. These approaches often assume that the parameters exchanged between neighbors are represented with high precision. This assumption overlooks the communication constraints (such as limited bandwidth and energy resources) inherent in real-world decentralized systems. Thus, it becomes important to design schemes that integrate both quantization and bias-correction to address these challenges efficiently.

In this work, we show how to blend differential quantization and error-feedback to obtain a communication-efficient bias-corrected decentralized learning algorithm. First, we describe in Sec. II the decentralized learning framework and the class of quantization operators considered in the study. Then, we present and analyze the proposed learning strategy in Secs. III and IV, respectively. Particularly, we establish the mean-square-error stability of the proposed approach. The analysis shows that, under some general conditions on the quantization noise, and for sufficiently small step-sizes $\mu$, it is possible to keep the estimation errors small (on the order of $\mu$) in steady-state, while maintaining a finite bit rate. Finally, in Sec. V we illustrate the theoretical results through numerical simulations.
## II. PROBLEM SETUP

### A. Decentralized consensus optimization

In this work, we consider single-task or consensus-based optimization problems of the form:

$$w^* = \arg \min_{w \in \mathbb{R}^M} \frac{1}{N} \sum_{k=1}^{N} J_k(w), \quad (1)$$

where $N$ is the number of agents in the network, $w \in \mathbb{R}^M$ is an $M$ dimensional parameter vector, and $J_k(w): \mathbb{R}^M \to \mathbb{R}$ is a convex differentiable cost associated with agent $k$ and expressed as the expectation of some loss function $L_k(\cdot)$, i.e., $J_k(w) = \mathbb{E}L_k(w; y_k)$, where $y_k$ denotes the random data. The expectation is computed over the distribution of the data. In the stochastic setting, when the data distribution is unknown, the risks $J_k(\cdot)$ and their gradients $\nabla_w J_k(\cdot)$ are unknown. In this case, instead of using the true gradient vectors, it is common to use approximate gradient vectors of the form $\nabla_w J_k(w) = \nabla_w L_k(w; y_{k,i})$ where $y_{k,i}$ represents the data observed at iteration $i$ [5], [25].

In order to solve problem (1), agents are only allowed to perform local computations, and to exchange information with their neighbors over a prescribed network topology. Let $\mathcal{N}_k$ denote the set of nodes connected to agent $k$ by a communication link (including node $k$ itself). There are several techniques that can be used for solving problem (1). Diffusion strategies have been shown to be well-suited for learning from streaming data [4], [5], [26]. In its adapt-then-combine (ATC) form, the diffusion approach takes the following form:

$$\left\{ \begin{aligned} \psi_{k,i} &= w_{k,i-1} - \mu \widehat{\nabla_w J_k}(w_{k,i-1}), & (2a) \\ w_{k,i} &= \sum_{\ell \in \mathcal{N}_k} a_{k\ell} \psi_{\ell,i}. & (2b) \end{aligned} \right.$$

The first step (2a) is the adaptation step, in which agent $k$ performs a local stochastic gradient descent update on its own local cost. The second step (2b) is the combination step, in which agent $k$ combines the intermediate estimates $\{\psi_{\ell,i}\}_{\ell \in \mathcal{N}_k}$ (received from its neighborhood $\mathcal{N}_k$) through the combination coefficients $\{a_{k\ell}\}$. These coefficients are such that the $N \times N$ combination matrix $A = [a_{k\ell}]$ has a zero $(k, \ell)$-th entry 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 [19]:

$$A \mathbb{1}_N = \mathbb{1}_N, \quad \mathbb{1}_N^\top A = \mathbb{1}_N^\top, \quad \rho \left( A - \frac{1}{N} \mathbb{1}_N \mathbb{1}_N^\top \right) < 1, \quad (3)$$

where $\rho(\cdot)$ denotes the spectral radius of its matrix argument.

Although the approach in (2) is able to solve (1) in an efficient manner in the small step-size regime, it suffers from a steady-state bias [20]. That is, even in deterministic scenarios where the risks and the gradients are known, the steady-state squared error $\mathbb{E}\|w^* - w_{k,i}\|^2$ at agent $k$ approaches a small neighborhood around zero, preventing the iterates to reach the true minimizer. The work [20] shows that this non-exact convergence is a result of an inherent bias within the decentralized learning structure, and that the sparser the network is, the larger the bias will be. Previous works, such as [27] and [24], have shown that this induced bias can be corrected (i.e., removed) by $i$) adding the following correction step between the adaptation and combination steps:

$$\phi_{k,i} = \psi_{k,i} + w_{k,i-1} - \psi_{k,i-1}, \quad (4)$$

ii) replacing the intermediate estimates $\{\psi_{\ell,i}\}$ in the combination step (2b) by the corrected intermediate estimates $\{\phi_{\ell,i}\}$, and iii) replacing the combination matrix $A$ by $\bar{A}$ defined as:

$$\bar{A} = \frac{1}{2} (A + I_N). \quad (5)$$

The resulting approach is commonly referred to as the exact diffusion approach.

### B. Quantizers Design

In this work, we consider randomized quantizers $\mathcal{Q}(\cdot)$ satisfying the following property.

**Property 1.** (Unbiasedness and Variance bound).

$$\mathbb{E}[\mathbf{x} - \mathcal{Q}(\mathbf{x}) | \mathbf{x}] = 0, \quad (\text{Unbiasedness}) \quad (6)$$

$$\mathbb{E}[\|\mathbf{x} - \mathcal{Q}(\mathbf{x})\|^2 | \mathbf{x}] \le \beta_q^2 \|\mathbf{x}\|^2 + \sigma_q^2, \quad (\text{Variance bound}) \quad (7)$$

for some $\beta_q^2 \ge 0$ and $\sigma_q^2 \ge 0$, and where the expectations are evaluated w.r.t. the randomness of $\mathcal{Q}(\cdot)$.

As explained in [12, Section II], Property 1 is satisfied by many quantization operators of interest in decentralized learning such as QSGD [3], probabilistic ANQ [11], and probabilistic uniform quantizer [9], [28]. While many existing works focus on studying decentralized learning in the presence of quantizers that satisfy the variance bound conditions in Property 1 with a zero absolute noise term $\sigma_q^2 = 0$ [7]–[10], [13], [15], [18], the analysis in the current work is general and does not require $\sigma_q^2$ to be 0. As explained in [11], neglecting the effect of $\sigma_q^2$ requires that some quantities (e.g., the norm of the vector to be quantized) be represented with no quantization error. This limits the practical application of these performance bounds in communication constrained environments, since it would require some quantities to be communicated with near-infinite precision.

## III. ALGORITHM FRAMEWORK

In this work, we propose the DEF-ED (error-feedback - exact diffusion) approach for solving problem (1) in a decentralized and communication-efficient manner. At each iteration $i$, each agent $k$ performs four steps:

$$\left\{ \begin{aligned} \psi_{k,i} &= w_{k,i-1} - \mu \widehat{\nabla_w J_k}(w_{k,i-1}), & (8a) \\ \phi_{k,i} &= \psi_{k,i} + w_{k,i-1} - \psi_{k,i-1}, & (8b) \\ \kappa_{k,i} &= \kappa_{k,i-1} + \mathcal{Q}_k(\phi_{k,i} - \kappa_{k,i-1} + \mathbf{z}_{k,i-1}), & (8c) \\ w_{k,i} &= (1-\gamma)\kappa_{k,i} + \gamma \sum_{\ell \in \mathcal{N}_k} \bar{a}_{k\ell} \kappa_{\ell,i}, & (8d) \end{aligned} \right.$$

where $\gamma \in (0, 1]$ is a mixing parameter, $\mathcal{Q}_k(\cdot)$ is a randomized quantizer satisfying Property 1 (with parameters $\beta_q^2$ and $\sigma_q^2$ in (7) replaced by $\beta_{q,k}^2$ and $\sigma_{q,k}^2$ to highlight the dependency on agent $k$), $\bar{a}_{k\ell}$ is the $(k, \ell)$-th entry of the matrix $\bar{A}$ defined in (5), with $A$ satisfying the conditions in (3), and $\mathbf{z}_{k,i}$ is the quantization error at agent $k$ and iteration $i$, updated according to:

$$\mathbf{z}_{k,i} = \phi_{k,i} - \kappa_{k,i-1} + \mathbf{z}_{k,i-1} - \mathcal{Q}_k(\phi_{k,i} - \kappa_{k,i-1} + \mathbf{z}_{k,i-1}). \quad (9)$$

For the initialization, we set $\psi_{k,0} = w_{k,0}$ [27], $\kappa_{k,0} = 0$ [14] and $\mathbf{z}_{k,0} = 0$ [14]. In the first step (8a), which is referred to as the adaptation step, agent $k$ performs a local stochastic gradient descent step, as in (2a). In the second step (8b), which is referred to as the correction step, agent $k$ performs a self-correction step by simply adding and subtracting local quantities, as in [24], [27]. In the third step (8c), which is referred to as the quantization step,
agent $k$ performs differential quantization with error-feedback as in [14] by mapping real-valued vector $\psi_{k,i} - \phi_{k,i-1} + z_{k,i-1}$ into a quantized vector, i.e., $\delta_{k,i}$, and then computes the quantization noise $z_{k,i}$ according to (9). Then, agent $k$ sends $\delta_{k,i}$ to its neighbors through ideal communication links (i.e., it is assumed that node $k$ can transmit perfectly and reliably $\delta_{k,i}$ to its neighbors), receives $\{\delta_{\ell,i}\}$ from its neighbors $\ell \in \mathcal{N}_k$, and performs the reconstruction on each received vector $\delta_{\ell,i}$ by first decoding it and then computing $\kappa_{\ell,i}$ according to (8c). Note that implementing (8c) requires storing the vectors $\{\kappa_{\ell,i}\}_{\ell \in \mathcal{N}_k}$ and the quantization noise vector $z_{k,i}$ by agent $k$. In the fourth step (8d), which is referred to as the combination step, agent $k$ combines the reconstructed vectors $\{\kappa_{\ell,i}\}$ by using the combination coefficients $\{\bar{a}_{k,\ell}\}$. The mixing parameter $\gamma$ is used to tune the degree of cooperation between the agents in situations where quantization leads to network instability [12]. Observe that, in the absence of quantization (i.e., when the operator $\mathcal{Q}_k(\cdot)$ in (8c) and (9) is replaced by the identity operator and the parameter $\gamma$ is set to 1), we obtain the exact diffusion algorithm [27]. Therefore, (8) can be seen as a communication-efficient variant of the exact diffusion. To mitigate the negative impact of quantization, the approach in (8) uses differential quantization and error-feedback in step (8c).

IV. MEAN-SQUARE-ERROR ANALYSIS

We analyze strategy (8) by examining the average squared distance of the iterates $w_{k,i}$ with respect to the minimizer $w^*$, namely, $\mathbb{E}||\tilde{w}_{k,i}||^2$, where $\tilde{w}_{k,i} = w^* - w_{k,i}$, under the following assumptions on the risks $\{J_k(\cdot)\}$ and on the gradient noise processes $\{s_{k,i}(\cdot)\}$ defined as [5]:

$$s_{k,i}(w) = \nabla_w J_k(w) - \overline{\nabla_w J_k(w)}. \quad (10)$$

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

$$\nu_k I_M \le \nabla_w^2 J_k(w_k) \le \delta_k I_M, \quad (11)$$

for some positive parameters $\nu_k$ and $\delta_k$ for $k = 1, \dots, N$. For two matrices $X$ and $Y$, the notation $X \ge Y$ means that $X - Y$ is positive semi-definite.

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

$$\mathbb{E}[\|s_{k,i}(w_{k,i-1})\|^{\delta_{k,i-1}}] = 0, \quad (12)$$

$$\mathbb{E}[\|s_{k,i}(w_{k,i-1})\|^2 \mid \{\kappa_{\ell,i-1}\}_{\ell=1}^{\delta_{k,i-1}}] \le \beta_{s,k}^2 \|\tilde{w}_{k,i-1}\|^2 + \sigma_{s,k}^2, \quad (13)$$

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

In the following, we derive a useful recursion that allows us to examine the time-evolution across the network of the error dynamics relative to the reference vector $w^*$. Then, we present the mean-square-error stability theorem and highlight the main conclusions.

Let $\tilde{\psi}_{k,i} = w^* - \psi_{k,i}$, $\tilde{\phi}_{k,i} = w^* - \phi_{k,i}$ and $\tilde{\kappa}_{k,i} = w^* - \kappa_{k,i}$. Using similar arguments as in [20], [22], we can show that the vector $\tilde{\kappa}_i = \text{col}\{\tilde{\kappa}_{k,i}\}_{k=1}^N$ evolves according to:

$$\tilde{\kappa}_i = (2I_{MN} - \mu \mathcal{H}_{i-1}) \overline{\mathcal{A}'} \tilde{\kappa}_{i-1} - (I_{MN} - \mu \mathcal{H}_{i-2}) \overline{\mathcal{A}'} \tilde{\kappa}_{i-2} - \mu(s_i - s_{i-1}) + (z_i - z_{i-1}), \quad (14)$$

where $s_i = \text{col}\{s_{k,i}\}_{k=1}^N$, $z_i = \text{col}\{z_{k,i}\}_{k=1}^N$, $\mathcal{H}_{i-1} = \text{diag}\{\mathcal{H}_{1,i-1}, \dots, \mathcal{H}_{N,i-1}\}$ with $\mathcal{H}_{k,i-1} = \int_0^1 \nabla_w^2 J_k(w^* - t\tilde{w}_{k,i-1}) dt$ and $\overline{\mathcal{A}'} = (1 - \gamma)I_{MN} + \gamma\overline{\mathcal{A}}$, with $\overline{\mathcal{A}} = \overline{\mathcal{A}} \otimes I_M$, where the symbol $\otimes$ denotes the Kronecker product.

In order to facilitate the analysis, and as in [20], [22], we start by defining the matrix $\mathcal{V} \in \mathbb{R}^{MN \times MN}$ to be the symmetric square-root

matrix of $I_{MN} - \overline{\mathcal{A}}'$. That is, $\mathcal{V} = \mathbb{U} \Sigma^{1/2} \mathbb{U}^\top$, where $\Sigma \in \mathbb{R}^{MN \times MN}$ is a diagonal matrix consisting of the non-negative eigenvalues of $I_{MN} - \overline{\mathcal{A}}'$ and $\mathcal{U} \in \mathbb{R}^{MN \times MN}$ is an orthogonal matrix consisting of the eigenvectors of $I_{MN} - \overline{\mathcal{A}}'$. Next, we define the dual variable $\tilde{y}_i$ as $\tilde{y}_i = \tilde{y}_{i-1} + \mathcal{V}\tilde{\kappa}_i$, and rewrite (14) in the following primal-dual form:

$$\tilde{\kappa}_i = (I_{MN} - \mu \mathcal{H}_{i-1}) \overline{\mathcal{A}'} \tilde{\kappa}_{i-1} - \mathcal{V} \tilde{y}_{i-1} - \mu s_i + z_i, \quad (15)$$

$$\tilde{y}_i = \mathcal{V}(I_{MN} - \mu \mathcal{H}_{i-1}) \overline{\mathcal{A}'} \tilde{\kappa}_{i-1} + \overline{\mathcal{A}'} \tilde{y}_{i-1} - \mathcal{V}\mu s_i + \mathcal{V}z_i, \quad (16)$$

which can be written in a matrix form as:

$$\begin{bmatrix} \tilde{\kappa}_i \\ \tilde{y}_i \end{bmatrix} = \left( \begin{bmatrix} \overline{\mathcal{A}'} & -\mathcal{V} \\ \mathcal{V}\overline{\mathcal{A}'} & \overline{\mathcal{A}'} \end{bmatrix}_{\mathcal{B}} - \begin{bmatrix} \mu \mathcal{H}_{i-1} \overline{\mathcal{A}'} & 0 \\ \mathcal{V}\mu \mathcal{H}_{i-1} \overline{\mathcal{A}'} & 0 \end{bmatrix}_{\mathcal{R}_{i-1}} \right) \begin{bmatrix} \tilde{\kappa}_{i-1} \\ \tilde{y}_{i-1} \end{bmatrix} - \mu \underbrace{\begin{bmatrix} I_{MN} \\ \mathcal{V} \end{bmatrix}}_{\mathcal{B}_\ell} s_i + \underbrace{\begin{bmatrix} I_{MN} \\ \mathcal{V} \end{bmatrix}}_{\mathcal{B}_\ell} z_i. \quad (17)$$

Similarly to [20], [22], the mean-square-error analysis requires exploiting the eigenstructure of the matrix $\mathcal{B}$ appearing in (17). By following the same arguments as in [20, Lemma 3], we can show that $\mathcal{B}$ can be decomposed as:

$$\mathcal{B} = \underbrace{\left[ \begin{array}{ccc} \mathcal{R}_1 & \mathcal{R}_2 & c\mathcal{X}_R \end{array} \right]}_{\mathcal{X}} \underbrace{\left[ \begin{array}{ccc} I_M & 0 & 0 \\ 0 & I_M & 0 \\ 0 & 0 & \mathcal{D}_1 \end{array} \right]}_{\mathcal{D}} \underbrace{\left[ \begin{array}{c} \mathcal{L}_1^\top \\ \mathcal{L}_2^\top \\ \frac{1}{c} \mathcal{X}_L \end{array} \right]}_{\mathcal{X}^{-1}}, \quad (18)$$

where $c$ is some positive constant, $\mathcal{D}$ is a $2MN \times 2MN$ diagonal matrix, and:

$$\mathcal{R}_1 = \begin{bmatrix} \mathcal{I} \\ 0 \end{bmatrix} \in \mathbb{R}^{2MN \times M}, \quad \mathcal{R}_2 = \begin{bmatrix} 0 \\ \mathcal{I} \end{bmatrix} \in \mathbb{R}^{2MN \times M}, \quad (19)$$

$$\mathcal{L}_1 = \begin{bmatrix} \frac{1}{N} \mathcal{I} \\ 0 \end{bmatrix} \in \mathbb{R}^{2MN \times M}, \quad \mathcal{L}_2 = \begin{bmatrix} 0 \\ \frac{1}{N} \mathcal{I} \end{bmatrix} \in \mathbb{R}^{2MN \times M}, \quad (20)$$

$$\mathcal{X}_R \in \mathbb{C}^{2MN \times 2(N-1)M}, \quad \mathcal{X}_L \in \mathbb{C}^{2(N-1)M \times MN}, \quad (21)$$

where $\mathcal{I} = 1_N \otimes I_M$. The matrix $\mathcal{D}_1$ in (18) is diagonal with possibly complex entries of magnitude strictly less than 1.

**Theorem 1.** (Mean-square-error stability). Consider a network of $N$ agents running the quantized decentralized strategy (8) under Assumptions 1 and 2. Each agent $k$ is equipped with a quantizer satisfying Property 1 for some $\beta_{q,k}^2 \ge 0$ and $\sigma_{q,k}^2 \ge 0$. If the quantizers are such that $\beta_{q,k}^2 = 0$ for all $k$, let $\gamma = 1$. Otherwise, let $\gamma \in (0, 1]$ be such that:

$$\gamma \le \min\{1, \gamma^*\}, \quad (22)$$

where $\gamma^*$ satisfies the following condition:

$$\beta_{q,\max}^2 \alpha_1^2 \gamma^* (1 - \lambda_{\min}) \left( \frac{c^2}{N} + \alpha_2^2 + \gamma^* \alpha_2^2 \right) (1 + \gamma^* - \gamma^* \lambda_{\min}) + \sqrt{1 - \gamma^* + \gamma^* \lambda_2} < 1, \quad (23)$$

where $\beta_{q,\max}^2 = \max_{1 \le k \le N} \beta_{q,k}^2$, $\alpha_1^2 = \|\mathcal{X}_R\|^2$, $\alpha_2^2 = \|\mathcal{X}_L\|^2$, $\lambda_2 = \lambda_2(\overline{\mathcal{A}}) \le 1$ is the second largest eigenvalue of $\overline{\mathcal{A}}$ in magnitude and $\lambda_{\min}(\overline{\mathcal{A}})$ is the minimum eigenvalue of $\overline{\mathcal{A}}$ in magnitude. Then, the network is mean-square-error stable for sufficiently small step-size $\mu$, namely, it holds that:

$$\limsup_{i \to \infty} \mathbb{E} \|w^* - w_{k,i}\|^2 = \epsilon O(\mu) + \bar{\sigma}_q^2 O(\mu^{-1}), \quad (24)$$
<figure><img src="image_2.png" /><figcaption>Fig. 1. (Left) Evolution of the MSD learning curves for three different values of the step-size ($\mu_0 = 10^{-3}$). (Middle) Evolution of the average number of bits per node, per component. (Right) Comparison of the MSD learning performance with and without bias-correction for grid networks of different sizes.</figcaption></figure>

for $k = 1, \dots, N$, and where $\epsilon$ is a constant given by:

$$ \epsilon = 2 \|\overline{\mathcal{A}'}\|^2 \left(1 + \frac{N \alpha_2^2 \alpha_3^2}{c^2}\right) (1 + \beta_{q,\max}^2) \bar{\sigma}_s^2 + \frac{2 \|\overline{\mathcal{A}'}\|^2 c^2 \alpha_1^2}{N} \bar{\sigma}_q^2, \quad (25) $$

where $\alpha_3^2 = \|\mathcal{B}_\ell\|^2$, $\bar{\sigma}_s^2 = \sum_{k=1}^N \sigma_{s,k}^2$ and $\bar{\sigma}_q^2 = \sum_{k=1}^N \sigma_{q,k}^2$.

*Proof.* The proof is omitted due to space limitations. The arguments combine arguments from [12] for handling differential quantization and error feedback with those from [20], [27] for analyzing the dynamics of exact diffusion. □

While expression (24) reveals the influence of the step size $\mu$, the quantization noise (captured by $\{\bar{\sigma}_q^2, \beta_{q,\max}^2\}$), and the gradient noise (captured by $\sigma_s^2$) on the steady-state mean-square-error, expression (23) reveals the influence of the relative quantization noise term (captured by $\beta_{q,\max}^2$) on the network stability, and how this influence can be mitigated by properly choosing the mixing parameter $\gamma$. From Theorem 1, observe first that in the absence of quantization, i.e., when $\beta_{q,\max}^2 = \bar{\sigma}_q^2 = 0$, we obtain the classical result obtained in the uncompressed case [20]. If exact gradient vectors are used instead of stochastic approximations, i.e., $\bar{\sigma}_s^2 = 0$, and if the quantization operators are such that $\sigma_{q,k}^2 = 0 \forall k$, we obtain $\limsup_{i \to \infty} \mathbb{E}\|w^* - w_{k,i}\|^2 = 0$ due to the bias-correction mechanism in step (8b). Finally, and as in [12], the term $\bar{\sigma}_q^2 O(\mu^{-1})$ reduces to $O(\mu)$ by choosing quantization schemes with $\sigma_{q,k}^2 \propto \mu^2$.

By following similar arguments as those used in [12] to establish Theorem 2, we can establish that, despite requiring small quantization errors as $\mu \to 0$ (since $\sigma_{q,k}^2 \propto \mu^2$), the bit rate of strategy (8) stays bounded as $\mu \to 0$. In particular, we can show that, when the probabilistic ANQ quantizer equipped with the variable-rate encoding scheme described in [12, Section II] is used, strategy (8) achieves the classical small estimation error result $\limsup_{i \to \infty} \mathbb{E}\|w^* - w_{k,i}\|^2 = O(\mu)$ while guaranteeing that the average number of bits at agent $k$ stays bounded in steady-state, as $\mu \to 0$.

## V. SIMULATION RESULTS

We apply strategy (8) to a grid network consisting of $N = 36$ nodes. As explained in [20, Sec. IV-B], grid networks with a large number of nodes tend to be sparse, making them suitable to illustrate the effect and benefit of bias-correction techniques. Each agent is subjected to streaming data $\{\mathbf{d}_k(i), \mathbf{u}_{k,i}\}$ assumed to satisfy a linear regression model of the form $\mathbf{d}_k(i) = \mathbf{u}_{k,i}^\top w_k^o + \mathbf{v}_k(i)$, for some $M \times 1$ vector $w_k^o$ with $\mathbf{v}_k(i)$ denoting a zero-mean measurement noise and $M = 5$. A mean-square-error cost of the form $J_k(w) = \frac{1}{2}\mathbb{E}|\mathbf{d}_k(i) - \mathbf{u}_{k,i}^\top w|^2$ is associated with each agent $k$. The model parameters $\{w_k^o\}$ are generated from the Gaussian distribution

$\mathcal{N}(10 \times 1_{NM}, I_{NM})$. The processes $\{\mathbf{u}_{k,i}\}$ and $\{\mathbf{v}_k(i)\}$ are zero-mean, generated from the Gaussian distributions $\mathcal{N}(0, \sigma_{u,k}^2 I_M)$ and $\mathcal{N}(0, \sigma_{v,k}^2 I_M)$, respectively. The variances $\{\sigma_{u,k}^2\}$ and $\{\sigma_{v,k}^2\}$ are generated from the uniform distributions $\mathcal{U}(1.5, 2)$ and $\mathcal{U}(0.2, 0.8)$, respectively. We use a combination matrix $A$ satisfying the conditions in (3).

In Fig. 1 (left), we report the network mean-square-deviation (MSD) learning curves $\mathbb{E}\|w^* - w_{k,i}\|^2$ for 3 different values of the step-size $\mu$. The variable-rate encoding scheme from [11] is employed. The results were averaged over 200 Monte-Carlo runs. We used the probabilistic ANQ quantizer [12] with $\omega_k = 0.25$ and $\eta_k = \frac{\mu}{\sqrt{2M}}$. This choice ensures that $\sigma_{q,k}^2 \propto \mu^2$. We set $\gamma = 0.8$. We observe that, in steady-state, the network MSD decreases by approximately 3dB when $\mu$ goes from $2\mu_0$ to $\mu_0$ and from $\mu_0$ to $\mu_0/2$, for $\mu_0 = 10^{-3}$. This means that the performance is on the order of $\mu$. This is expected from the discussion in Sec. IV since the absolute noise component is such that $\sigma_{q,k}^2 \propto \mu^2$. In Fig. 1 (middle), we report the average number of bits per node, per component, computed according to $R(i) = \frac{1}{N} \sum_{k=1}^N \frac{1}{M} \mathbb{E}r_{k,i}$, where $r_{k,i}$ is the bit rate associated with the encoding of the difference vector $\phi_{k,i} - \kappa_{k,i-1} + z_{k,i-1}$ transmitted by agent $k$ at iteration $i$ according to (8c). As it can be observed, and thanks to the variable-rate quantization, a finite average number of bits is guaranteed (approximately 5.6 bits/component/iteration are required on average in steady-state).

In order to show the effect of bias-correction, we apply strategy (8) with and without the correction step (8b) for $\mu = 10^{-3}$. Note that strategy (8) without the correction step is the same as the one proposed and studied in [14]. In Fig. 1 (right), we report the network mean-square-deviation (MSD) learning curves for grid networks of 36 and 100 agents. For the grid of 36 agents, we observe that (8) outperforms the uncorrected bias approach by approximately 2.3dB in steady-state. For the larger grid network of 100 nodes, we observe that the bias-corrected algorithm outperforms the uncorrected version by approximately 6.4dB in steady-state. As discussed in [20], the less connected the network is (as in the case of the grid with size 100), the more prominent the effect of the bias correction step will be.

## VI. CONCLUSION

In this work, we proposed a communication-efficient variant of the exact diffusion approach, which addresses the bias inherent in decentralized architectures. We studied the mean-square error stability of this variant and demonstrated that, in the small step-size regime, it is possible to achieve small estimation errors (on the order of $\mu$) in steady-state, while maintaining finite bit rates. These theoretical findings were further illustrated through simulations.
REFERENCES

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

[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] 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.

[4] A. H. Sayed, "Adaptive networks," *Proc. IEEE*, vol. 102, no. 4, pp. 460-497, Apr. 2014.

[5] A. H. Sayed, "Adaptation, learning, and optimization over networks," *Foundations and Trends in Machine Learning*, vol. 7, no. 4-5, pp. 311-801, 2014.

[6] 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, May 2020.

[7] 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 Conference, 2021, pp. 4087-4095.

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

[9] 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.

[10] 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.

[11] 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, Nov. 2022.

[12] 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.

[13] 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, LA, USA, 2022, vol. 35, pp. 31653-31667.

[14] 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, 2024, pp. 1-5.

[15] 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.

[16] 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.

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

[18] 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.

[19] 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.

[20] K. Yuan, S. A. Alghunaim, B. Ying, and A. H. Sayed, "On the influence of bias-correction on distributed stochastic optimization," *IEEE Trans. Signal Process.*, vol. 68, pp. 4352-4367, 2020.

[21] W. Shi, Q. Ling, G. Wu, and W. Yin, "EXTRA: An exact first-order algorithm for decentralized consensus optimization," *SIAM J. Optim.*, vol. 25, no. 2, pp. 944-966, 2015.

[22] K. Yuan, B. Ying, X. Zhao, and A. H. Sayed, "Exact diffusion for distributed optimization and learning – Part II: Convergence analysis," *IEEE Trans. Signal Process.*, vol. 67, no. 3, pp. 724-739, Feb. 2019.

[23] P. Di Lorenzo and G. Scutari, "NEXT: In-network nonconvex optimization," *IEEE Trans. Signal and Inf. Process.*, vol. 2, no. 2, pp. 120-136, 2016.

[24] S. Wadehra, R. Nassif, and S. Vlaski, "Exact subspace diffusion for decentralized multitask learning," in *Proc. IEEE Conf. Decis. Control*, Singapore, 2023, pp. 6172-6179.

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

[26] 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.

[27] K. Yuan, B. Ying, X. Zhao, and A. H. Sayed, "Exact diffusion for distributed optimization and learning – Part I: Algorithm development," *IEEE Trans. Signal Process.*, vol. 67, no. 3, pp. 708-723, 2019.

[28] 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.