Communication Compression for Decentralized Learning with Operator Splitting Methods

Let $G=(\mathcal{V},\mathcal{E})$ be an undirected connected graph that represents the network topology where $\mathcal{V}$ denotes the set of nodes and $\mathcal{E}$ denotes the set of edges. For simplicity, we denote $\mathcal{V}$ as the set of integers $\{1,2,\ldots,|\mathcal{V}|\}$. We denote the set of neighbors of the node $i$ as $\mathcal{N}_{i}=\{j\in\mathcal{V}|(i,j)\in\mathcal{E}\}$. The goal of decentralized learning is formulated as follows:

where $\mathbf{w}\in\mathbb{R}^{d}$ is the model parameter, $F$ is the loss function, $\mathcal{D}_{i}$ represents the data held by the node $i$, $\zeta_{i}$ is the data sample from $\mathcal{D}_{i}$, and $f_{i}$ is the loss function of the node $i$.

A widely used approach for decentralized learning is the Gossip-based algorithm (e.g. D-PSGD [18]). In the Gossip-based algorithm, each node $i$ computes its own gradient $\nabla f_{i}$, exchanges parameters with its neighbors, and then takes their average. Although, the Gossip-based algorithm is a simple and effective approach, there are two main issues: high communication costs and sensitivity to the heterogeneity of the data distribution.

In the Gossip-based algorithm, the node needs to receive the model parameter from its neighbors. Because the number of parameters in a neural network is large, the exchanges of the model parameters incur huge communication costs. To reduce these communication costs of the Gossip-based algorithm, many methods that compress the exchanging parameters by using sparsification, quantization, and low-rank approximation have been proposed [29, 13, 21, 12, 33]. Then, it was shown that these compression methods can achieve almost the same accuracy as the uncompressed Gossip-based algorithm with fewer parameter exchanges.

The second issue is that the Gossip-based algorithm is sensitive to the heterogeneity of the data distribution. When the data distribution of each node is statistically heterogeneous, because the optimal solution of the loss function $\sum_{i}f_{i}$ and the optimal solution of the loss function of each node $f_{i}$ are far from each other, the Gossip-based algorithms do not perform well [22, 32]. To address heterogeneous data in the Gossip-based algorithm, Tang et al., 2018b [30] and Xin et al., [37] applied variance reduction methods [5, 10] to the Gossip-based algorithm. Lorenzo and Scutari, [20] proposed gradient tracking algorithms, and Vogels et al., [32] recently proposed the RelaySum.

In this section, we briefly introduce the Edge-Consensus Learning (ECL) [22]. By reformulating Eq. (1), the primal problem can be defined as follows:

where $\mathbf{A}_{i|j}=\mathbf{I}$ when $j\in\mathcal{N}_{i}$ and $i<j$, and $\mathbf{A}_{i|j}=-\mathbf{I}$ when $j\in\mathcal{N}_{i}$ and $i>j$. By contrast, the Gossip-based algorithm explicitly computes the average at each round, whereas the primal problem of Eq. (2) represents the consensus based on the linear constraints. Subsequently, by solving the the dual problem of Eq. (2) using the Douglas-Rachford splitting [8], the update formulas can be derived as follows [27]:

where $\theta\in(0,1]$ and $\alpha>0$ are hyperparameters, and $\mathbf{y}_{i|j},\mathbf{z}_{i|j}\in\mathbb{R}^{d}$ are dual variables. We present detailed derivation of these update formulas in Sec. B. When $\theta=1$, the Douglas-Rachford splitting is specifically called the Peaceman-Rachford splitting [24]. When $f_{i}$ is non-convex (e.g., a loss function of a neural network), Eq. (3) can not be generally solved. Then, Niwa et al., [22] proposed the Edge-Consensus Learning (ECL), which approximately solves Eq. (3) as follows:

where $\eta>0$ corresponds to the learning rate. Then, Niwa et al., [23] showed that the ECL can be interpreted as a stochastic variance reduction method and demonstrated that the ECL is more robust to heterogeneous data than the Gossip-based algorithms. However, as shown in Eq. (5), the node $i$ must receive dual variables $\mathbf{y}_{j|i}$ from its neighbor $j$ in the ECL. Therefore, in the ECL as well as in the Gossip-based algorithm, large communication costs occur during training.

In addition to the ECL, other methods using primal-dual formulations have been proposed [17], and recently, the compression methods for these primal-dual algorithms has been studied [14, 19]. However, the compression methods for the ECL have not been studied. In this work, we propose the compression method for the ECL, called the C-ECL, that can train a model with fewer parameter exchanges and is robust to heterogeneous data.

Before proposing the C-ECL, we first introduce the compression operator used in this work.

The assumption of Eq. (7) is commonly used for the compression methods for the Gossip-based algorithms [21, 33, 13]. In addition, we assume that the compression operator satisfies Eqs. (8-9), and the low-rank approximation [33] and the following sparsification used in the compression methods for the Gossip-based algorithm satisfy Eqs. (8-9).

In this section, we propose the the Communication Compressed ECL (C-ECL), the method for compressing the dual variables exchanged in the ECL using the compression operator introduced in the previous section.

In the ECL, to update $\mathbf{z}_{i|j}$ in Eq. (5), the node $i$ needs to receive $\mathbf{y}_{j|i}$ from the node $j$. Because the number of elements in $\mathbf{y}_{j|i}$ is the same as that of the model parameter $\mathbf{w}_{j}$, this exchange incurs significant communication costs. A straightforward approach to reduce this communication cost is compressing $\mathbf{y}_{j|i}$ in Eq. (5) as follows:

However, we found experimentally that compressing $\mathbf{y}_{j|i}$ does not work. In the compression methods for the Gossip-based algorithm, Lu and De Sa, [21] showed that the model parameters are not robust to the compression. This is because the optimal solution of the model parameter is generally not zero, and thus the error caused by the compression does not approach zero even if the model parameters are near the optimal solution. Therefore, the successful compression methods for the Gossip-based algorithms compress the gradient $\nabla f_{i}(\mathbf{w}_{i})$ or the model difference $(\mathbf{w}_{j}-\mathbf{w}_{i})$, which approach zero when the model parameters are near the optimal solution [13, 21, 33].

Inspired by these compression methods for the Gossip-based algorithms, we reformulate Eq. (5) into Eq. (12) so that we can compress the parameters which approach zero when the model parameters are near the optimal solution.

In the Douglas-Rachford splitting, $\mathbf{z}_{i|j}$ approaches the fixed point (i.e., $\mathbf{z}_{i|j}^{(r)}=\mathbf{z}_{i|j}^{(r+1)}$) when the model parameters approach the optimal solution. (See Sec. A for details of the Douglas-Rachford splitting and the definition of the fixed point). Then, from Eq. (12), when the model parameters approach to the optimal solution, $(\mathbf{y}_{j|i}-\mathbf{z}_{i|j})$ in Eq. (12) approaches zero. Then, instead of compressing $\mathbf{y}_{j|i}$ as in Eq. (11), we propose compressing $(\mathbf{y}_{j|i}-\mathbf{z}_{i|j})$ as follows:

where we use Assumption 1 in the last equation. When $\textbf{rand}_{k\%}$ is used as the compression operator, $\mathbf{y}_{j|i}$ and $\mathbf{z}_{i|j}$ must be compressed using the same sparse vector $\mathbf{s}$ in Eq. (10) to use Assumption 1. In Alg. 1, we provide the pseudo-code of the C-ECL. For simplicity, the node $i$ and the node $j$ exchange $\omega_{i|j}$ and $\omega_{j|i}$ at Lines 5-6 in Alg. 1. However, by sharing the same seed value to generate $\omega_{i|j}$ and $\omega_{j|i}$ before starting the training, the node $i$ and the node $j$ can obtain the same values $\omega_{i|j}$ and $\omega_{j|i}$ without any exchanges. Moreover, when $\textbf{rand}_{k\%}$ is used as the compression operator, the node $i$ can obtain $\omega_{i|j}$ from the received value $\textbf{comp}(\mathbf{y}_{j|i};\omega_{i|j})$ because $\textbf{comp}(\mathbf{y}_{j|i};\omega_{i|j})$ is stored in a sparse matrix format (e.g., COO format). Thus, these exchanges of $\omega_{i|j}$ and $\omega_{j|i}$ can be omitted in practice. Therefore, in the C-ECL, each node only needs to exchange the compressed value of $\mathbf{y}_{j|i}$, and the C-ECL can train a model with fewer parameter exchanges than the ECL.

In this section, we introduce additional notations and assumptions used in our convergence analysis. We define $N\coloneqq|\mathcal{V}|$, $N_{\text{min}}\coloneqq\text{min}_{i}\{|\mathcal{N}_{i}|\}$, $N_{\text{max}}\coloneqq\text{max}_{i}\{|\mathcal{N}_{i}|\}$ where $\mathcal{N}_{i}$ is the set of neighbors of the node $i$. Let $\mathcal{N}_{i}(j)$ be the $j$-th smallest index of the node in $\mathcal{N}_{i}$, we define $\mathbf{w}\in\mathbb{R}^{dN}$, $\mathbf{z}_{i}\in\mathbb{R}^{d|\mathcal{N}_{i}|}$, and $\mathbf{z}\in\mathbb{R}^{2d|\mathcal{E}|}$ as follows:

For simplicity, we drop the superscripts of the number of round $r$. Let $\{\mathbf{w}_{i}^{\ast}\}_{i}$ be the optimal solution of Eq. (2), we define $\mathbf{w}^{\star}\in\mathbb{R}^{dN}$ in the same manner as the definition of $\mathbf{w}$ in Eq. (14). We define the loss function as $f(\mathbf{w})\coloneqq\sum_{i\in\mathcal{V}}f_{i}(\mathbf{w}_{i})$. Next, we introduce the assumptions used in the convergence analysis.

Assumption 2, 3 are the standard assumptions used for the convergence analysis of the operator splitting methods [9, 26]. Assumption 3 is weaker than the assumptions of the smoothness and the strongly convexity of $f_{i}$ for all $i\in\mathcal{V}$, which are commonly used in decentralized learning. Assumption 4 holds in general because decentralized learning assumes that the graph $G$ is connected. In addition, we define $\delta\in\mathbb{R}$ as follows:

Suppose that Assumptions 2, 3, and 4 hold and $\alpha\in(0,\infty)$ holds, then $\delta\in[0,1)$ holds because $L\geq\mu>0$ and $N_{\text{max}}\geq N_{\text{min}}>0$.

Because $\tau=1$ implies that $\textbf{comp}(\mathbf{x})=\mathbf{x}$ in the C-ECL, Corollary 1 shows the convergence rate of the ECL under Assumptions 1, 2, 3, and 4, which is almost the same rate as that shown in the previous work [9]. Comparing the domain of $\theta$ for the ECL and the C-ECL to converge, as $\tau$ decreases, the domain in Eq. (15) becomes smaller. Subsequently, in order for the domain in Eq. (15) to be non-empty, $\tau$ must be greater than or equal to $(1-(1-\delta)^{2}/(1+\delta)^{2})$. Next, comparing the convergence rate of the ECL and the C-ECL, the compression in the C-ECL slows down the convergence rate of the ECL by the term $(\sqrt{1-\tau}(\theta+|1-\theta|\delta+\delta))$. Moreover, similar to the convergence analysis of the Douglas-Rachford splitting [9], Theorem 1 and Corollary 1 imply that the optimal parameter of $\theta$ can be determined as follows:

Dataset and Model: We evaluate the C-ECL using FashionMNIST [35] and CIFAR10 [15], which are datasets of 10-class image-classification tasks. As the models for both datasets, we use 5-layer convolutional neural networks [16] with group normalization [34]. Following the previous work [22], we distribute data to the nodes in two settings: the homogeneous and heterogeneous settings. In the homogeneous setting, the data are distributed such that each node has the data of all $10$ classes and has approximately the same number of data of each class. In the heterogeneous setting, the data are distributed such that each node has the data of randomly selected $8$ classes. In both settings, the data are distributed to the nodes such that each node has the same number of data.

Network: In Sec. 5.2, we evaluate all comparison methods on a network of a ring consisting of eight nodes. In addition, in Sec. 5.3, we evaluate all comparison methods in four settings of the network topology: chain, ring, multiplex ring, and fully connected graph, where each setting consists of eight nodes. In Sec. D, we show a visualization of the network topology. Each node exchanges parameters with its neighbors per five local updates. We implement with PyTorch using gloo²²2https://pytorch.org/docs/stable/distributed.html as the backend, and run all comparison methods on eight GPUs (NVIDIA RTX 3090).

Comparison Methods: (1) D-PSGD [18]: The uncompressed Gossip-based algorithm. (2) PowerGossip [33]: The Gossip-based algorithm that compresses the exchanging parameters by using a low-rank approximation. We use the PowerGossip as the compression method for the Gossip-based algorithm because the PowerGossip has been shown to achieve almost the same performance as other existing compression methods without additional hyperparameter tuning. (3) ECL [22, 23]: The primal-dual algorithm described in Sec. 2.3. Because Niwa et al., [22] showed that the ECL converges faster when $\theta=1$ than when $\theta=0.5$, we set $\theta=1$. (4) C-ECL: Our proposed method described in Sec. 3. We use $\textbf{rand}_{k\%}$ as the compression operator. Following Corollary 2, we set $\theta=1$. We initialize $\mathbf{z}_{i|j}$ and $\mathbf{y}_{i|j}$ to zeros. However, we found that when we compress the update values of $\mathbf{z}_{i|j}$ by using $\textbf{rand}_{k\%}$, the convergence becomes slower because $\mathbf{z}_{i|j}$ remains to be sparse in the early training stage. Then, we set $k\%$ of $\textbf{rand}_{k\%}$ to $100\%$ only during the first epoch.

In addition, for the reference, we show the results of the Stochastic Gradient Descent (SGD), in which the model is trained on a single node containing all training data. In our experiments, we set the learning rate, number of epochs, and batch size to the same values for all comparison methods. In Sec. D, we show the detailed hyperparameters used for all comparison methods.

In this section, we evaluate the accuracy and the communication costs when setting the network topology to be a ring.

Homogeneous Setting: First, we discuss the results on the homogeneous setting. Table 1 shows the accuracy and the communication costs on the homogeneous setting. The results show that the D-PSGD and the ECL achieve almost the same accuracy on both datasets. Then, the C-ECL and the PowerGossip are comparable and achieve almost the same accuracy as the ECL and the D-PSGD even when we set $k\%$ of $\textbf{rand}_{k\%}$ to $1\%$ and the number of the power iteration steps to $1$ respectively. Therefore, the C-ECL can achieve the comparable accuracy with approximately $50$-times fewer parameter exchanges than the ECL and the D-PSGD on the homogeneous setting.

Heterogeneous Setting: Next, we discuss the results on the heterogeneous setting. Table 2 shows the accuracy and the communication costs on the heterogeneous setting. In the D-PSGD, the accuracy on the heterogeneous setting decreases by approximately $3\%$ compared to that on the homogeneous setting. In the PowerGossip, even if the number of power iteration steps is increased, the accuracy does not approach that of the D-PSGD and the ECL. On the other hand, the accuracy of the ECL is almost the same on both the homogeneous and heterogeneous settings, and the results indicate that the ECL is more robust to heterogeneous data than the D-PSGD. In the C-ECL, when we set $k\%$ of $\textbf{rand}_{k\%}$ to $1\%$, the accuracy on the heterogeneous setting decreases by approximately $10\%$ compared to that of the ECL. However, when we increase $k\%$ of $\textbf{rand}_{k\%}$, the C-ECL is competitive with the ECL and outperforms the D-PSGD and the PowerGossip. Specifically, on FashionMNIST, when we set $k\%$ to $10\%$, the C-ECL is competitive to the ECL and outperforms the D-PSGD and the PowerGossip. On CIFAR10, when we set $k\%$ to $20\%$, the C-ECL is competitive with the ECL and outperforms the D-PSGD and the PowerGossip.

In summary, on the homogeneous setting, the C-ECL and the PowerGossip can achieve almost the same accuracy as the ECL and the D-PSGD with approximately $50$-times fewer parameter exchanges. On the heterogeneous setting, the C-ECL can achieve almost the same accuracy as the ECL with approximately $4$-times fewer parameter exchanges and can outperform the PowerGossip. Furthermore, the results show that the C-ECL can outperform the D-PSGD, the uncompressed Gossip-based algorithm, in terms of both the accuracy and the communication costs.

In this section, we show the accuracy and the communication costs when the network topology is varied. Table 3 and Fig. 1 show the communication costs and the accuracy on FashionMNIST when the network topology is varied as a chain, ring, multiplex ring, or fully connected graph.

On the homogeneous setting, Fig. 1 shows that the accuracy of all comparison methods are almost the same and reach that of the SGD on all network topologies. On the heterogeneous setting, Fig. 1 shows that the accuracy of the D-PSGD and the PowerGossip are decreased compared to that on the homogeneous setting. On the other hand, the accuracy of the ECL is almost the same as on the homogeneous setting on all network topologies. Then, on all network topologies, the C-ECL achieves almost the same accuracy as the ECL with fewer parameters exchanges and consistently outperforms the PowerGossip. Moreover, the results show that on the heterogeneous setting, the C-ECL can outperform the D-PSGD, the uncompressed Gossip-based algorithm, on all network topologies in terms of both the accuracy and the communication costs.