FedComLoc: Communication-Efficient Distributed Training of Sparse and Quantized Models

## Abstract

Abstract Federated Learning (FL) has garnered increasing attention due to its unique characteristic of allowing heterogeneous clients to process their private data locally and interact with a central server, while being respectful of privacy.
A critical bottleneck in FL is the communication cost.
A pivotal strategy to mitigate this burden is Local Training , which involves running multiple local stochastic gradient descent iterations between communication phases.
Our work is inspired by the innovative Scaffnew algorithm of Mishchenko et al. ( 2022 ) , which has considerably advanced the reduction of communication complexity in FL.
We introduce FedComLoc (Federated Compressed and Local Training),
integrating practical and effective compression into Scaffnew to further enhance communication efficiency.
Extensive experiments, using the popular TopK compressor and quantization, demonstrate its prowess in substantially reducing communication overheads in heterogeneous settings.

## 1 Introduction

Privacy concerns and limited computing resources on edge devices often make centralized training impractical, where all data is gathered in a data center for processing. In response to these challenges, Federated Learning (FL) has emerged as an increasingly popular framework (McMahan et al., ; Kairouz et al., ). In FL, multiple clients perform computations locally on their private data and exchange information with a central server. This process is typically framed as an empirical risk minimization problem (Shalev-Shwartz & Ben-David, ):

$$ $\min_{x\in\mathbb{R}^{d}}\left[f(x)\coloneqq\frac{1}{n}\sum_{i=1}^{n}f_{i}(x) \right],$ (ERM) $$

where $f_{i}$ represents the local objective for client $i$, $n$ is the total number of clients, and $x$ is the model to be optimized. Our primary objective is to solve the problem (ERM) and deploy the optimized global model to all clients. For instance, $x$ might be a neural network trained in an FL setting.
However, a considerable bottleneck in FL are communication cost, particularly with large models.

To mitigate these costs, FL often employs *Local Training* (LT), a strategy where local parameters are updated multiple times before aggregation (Povey et al., ; Moritz et al., ; McMahan et al., ; Li et al., ; Haddadpour & Mahdavi, ; Khaled et al., , ; Karimireddy et al., ; Gorbunov et al., ; Mitra et al., ). However, there is a lack of theoretical understanding regarding the effectiveness of LT methods. The recent introduction of
Scaffnew by Mishchenko et al. () marked a substantial advancement, as this algorithm
converges to the exact solution with accelerated complexity, in convex settings.

Another approach to reducing communication costs is through compression (Haddadpour et al., ; Condat et al., ; Yi et al., ).
In centralized training, one often aims to learn a sparsified model for faster training and communication efficiency (Dettmers & Zettlemoyer, ; Kuznedelev et al., ).
Dynamic pruning strategies like gradual magnitude pruning (Gale et al., ) and RigL (Evci et al., ) are common. But in FL, the effectiveness of these model sparsification methods based on thresholds remains unclear.
The work by Babakniya et al. () considers FL sparsity mask concepts, showing promising results.

Quantization is another efficient model compression technique (Han et al., ; Bhalgat et al., ; Shin et al., ),
though its application in heterogeneous settings is limited.
Gupta et al. () introduced FedAvg with Kurtosis regularization (Chmiel et al., ) in FL.

Furthermore, studies such as Haddadpour et al. (); Condat et al. () have theoretical convergence guarantees for unbiased estimators with restrictive assumptions.
As this work employs the biased TopK compressor these are unsuitable in this case.

Thus, we tackle the following question:

Is it possible to design an efficient algorithm combining accelerated local training with compression techniques,
such as quantization and Top-K, and validate its efficiency empirically on popular FL datasets?

Our method for investigating this question consists of two steps.
Firstly, we design an algorithm, termed FedComLoc, which integrates general compression into ScaffNew, an accelerated local training algorithm.
Secondly, we empirically validate FedComLoc for popular compression techniques (${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Top}K}$ and quantization)
on popular FL datasets (FedMNIST and FedCIFAR10).

We were able to answer this question affirmatively with the following contributions:

- •
We have developed a communication-efficient method FedComLoc for distributed training, specifically designed for heterogeneous environments.
This method integrates general compression techniques and is motivated by previous theoretical insights.
- •
We proposed three variants of our algorithm addressing several key bottlenecks in FL:
FedComLoc-Com addresses communication costs from client to server,
FedComLoc-Global addresses communication costs from server to client and
FedComLoc-Local addresses limited computational resources on edge devices.
- •
We conducted detailed comparisons and ablation studies, validating the effectiveness of our approach.
These reveal a considerable reduction in communication and, in certain cases, an enhancement in training speed in number of communication rounds.
Furthermore, we demonstrated that our method outperforms well-established baselines in terms of training speed and communication costs.

## 2 Related Work

### 2.1 Local Training

The evolution of LT in FL has been profound and continuous, transitioning through five distinct generations, each marked by considerable advancements from empirical discoveries to reductions in communication complexity. The pioneering FedAvg algorithm (McMahan et al., )
represents the
first generation of LT techniques, primarily focusing on empirical evidence and practical applications (Povey et al., ; Moritz et al., ; McMahan et al., ).
The second generation of LT methods consists in solving (ERM) based on homogeneity assumptions such as bounded gradients(^1^11 There exists $c\in\mathbb{R}$ s.t. ${\left\|\nabla f_{i}(x)\right\|}\leq c$ for $1\leq i\leq d$.)
(Li et al., ) or limited gradient diversity(^2^22 There exists $c\in\mathbb{R}$ s.t. $\frac{1}{n}\sum_{i=1}^{n}{\left\lVert\nabla f_{i}(x)\right\rVert}^{2}\leq c{ \left\lVert\nabla f(x)\right\rVert}^{2}$.)
(Haddadpour & Mahdavi, ). However, the practicality of such assumptions in real-world FL scenarios is debatable and often not viable (Kairouz et al., ; Wang et al., ).

Third-generation methods made fewer assumptions, demonstrating sublinear (Khaled et al., , ) or linear convergence up to a neighborhood (Malinovsky et al., ) with convex and smooth functions.
More recently, fourth-generation
algorithms like Scaffold (Karimireddy et al., ), S-Local-GD (Gorbunov et al., ), and FedLin (Mitra et al., )
have gained popularity.
These algorithms effectively counteract client drift and achieve linear convergence to the exact solution under standard assumptions.
Despite these advances, their communication complexity mirrors that of GD, i.e. $\mathcal{O}(\kappa\log\epsilon^{-1})$,
where $\kappa\coloneqq L/\mu$ denotes the condition number.

The most recent Scaffnew algorithm, proposed by Mishchenko et al. (), revolutionizes the field with its accelerated communication complexity $\mathcal{O}(\sqrt{\kappa}\log\epsilon^{-1})$. This seminal development establishes LT as a communication acceleration mechanism for the first time, positioning Scaffnew at the forefront of the fifth generation of LT methods with accelerated convergence.
Further enhancements to Scaffnew have been introduced,
incorporating aspects like variance-reduced stochastic gradients (Malinovsky et al., ),
personalization (Yi et al., ), partial client participation (Condat et al., ), asynchronous communication (Maranjyan et al., ),
and an expansion into a broader primal–dual framework (Condat & Richtárik, ).
This latest generation also includes the 5GCS algorithm (Grudzień et al., ),
with a different strategy where the local steps are part of an inner loop to approximate a proximity operator.
Our proposed FedComLoc algorithm extends Scaffnew by incorporating pragmatic compression techniques,
such as sparsity and quantization, resulting in even faster training measured by the number of bits communicated.

### 2.2 Model Compression in Federated Learning

Model compression in the context of FL is a burgeoning field with diverse research avenues,
particularly focusing on the balance between model efficiency and performance.
Jiang et al. () innovated in global pruning by engaging a single, powerful client to initiate the pruning process. This strategy transitions into a collaborative local pruning phase, where all clients contribute to an adaptive pruning mechanism. This involves not just parameter elimination, but also their reintroduction, integrated with the standard FedAvg framework (McMahan et al., ).
However, this approach demands substantial local memory for tracking the relevance of each parameter, a constraint not always feasible in FL settings.

Addressing some of these challenges, Huang et al. () introduced an adaptive batch normalization coupled with progressive pruning modules, enhancing sparse local computations. These advancements, however, often do not fully address the constraints related to computational resources and communication bandwidth on the client side. Our research primarily focuses on magnitude-based sparsity pruning. Techniques like gradual magnitude pruning (Gale et al., ) and RigL (Evci et al., ) have been instrumental in dynamic pruning strategies. However, their application in FL contexts remains relatively unexplored. The pioneering work of Babakniya et al. () extends the concept of sparsity masks in FL, demonstrating noteworthy outcomes.

Figure: Algorithm 1 FedComLoc

Quantization is another vital avenue in model compression.
Seminal works in this area include Han et al. (), Bhalgat et al. (), and Shin et al. ().
A major advance has been made by Gupta et al. (), who combined FedAvg with Kurtosis regularization (Chmiel et al., ).
We are looking to go even further by integrating accelerated LT with quantization techniques.

However, a gap exists in the theoretical underpinnings of these compression methods.
Research by Haddadpour et al. () and Condat et al. () offers theoretical convergence guarantees for unbiased estimators,
but these frameworks are not readily applicable to common compressors like Top-K sparsifiers.
In particular, CompressedScaffnew (Condat et al., ) integrates an unbiased compression mechanism in Scaffnew,
that is based on random permutations.
But due to requiring shared randomness it is not practical.
Linear convergence has been proved when all functions $f_{i}$ are strongly convex.

To the best of our knowledge, no other compression mechanism has been studied in Scaffnew,
either theoretically or empirically, and even the mere convergence of Scaffnew in nonconvex settings has not been investigated either.
Our goal is to go beyond the convex setting and simplistic logistic regression experiments and to study compression in Scaffnew in realistic nonconvex settings with large datasets such as Federated CIFAR and MNIST.
Our integration of compression in Scaffnew is heuristic but backed by the findings and theoretical guarantees of CompressedScaffnew in the convex setting,
which shows a twofold acceleration with respect to the conditioning $\kappa$ and the dimension $d$, thanks to LT and compression, respectively.

## 3 Proposed Algorithm FedComLoc

### 3.1 Sparsity and Quantization

Let us define the sparsifying ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Top}K}(\cdot)$ and quantization ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Q_{r}}}(\cdot)$ operators.

###### Definition 3.1 .

Let $x\in\mathbb{R}^{d}$ and $K\in\{1,2,\dots,d\}$. We define the sparsifying compressor ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Top}K}:
\mathbb{R}^{d}\to\mathbb{R}^{d}$ as:

$$ ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Top}K}(x) \coloneqq\arg\min_{y\in\mathbb{R}^{d}}\left\{\left\|y-x\right\|\;|\;\left\|y \right\|_{0}\leq K\right\},$ $$

where $\left\|y\right\|_{0}\coloneqq|\{i:y_{i}\neq 0\}|$ denotes the number of nonzero elements in the vector $y=(y_{1},\cdots,y_{d})^{\intercal}\in\mathbb{R}^{d}$.
In case of multiple minimizers, ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Top}K}$ is chosen arbitrarily.

###### Definition 3.2 .

For any vector $x\in\mathbb{R}^{d}$, with $x\neq\mathbf{0}$ and a number of bits $r>0$, its binary quantization ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Q_{r}}}(x)$ is defined componentwise as

$$ ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Q_{r}}} \left(x\right)=\begin{pmatrix}\|x\|_{2}\cdot\operatorname{sgn}\left(x_{i} \right)\cdot\xi_{i}(x,2^{r})\end{pmatrix}_{1\leq i\leq d},$ $$

where $\xi_{i}(x,2^{r})$ are independent random variables.
Let $y_{i}:=\frac{|x_{i}|}{\|x\|_{2}}$.
Then their probability distribution is given by

$$ $\xi_{i}(x,2^{r})=\begin{cases}\left\lceil 2^{r}y_{i}\right\rceil/2^{r}&\text{ with proba.\ }2^{r}y_{i}-\left\lfloor 2^{r}y_{i}\right\rfloor;\[6.0pt] \left\lfloor 2^{r}y_{i}\right\rfloor/{2^{r}}&\text{otherwise.}\end{cases}$ $$

If $x=\mathbf{0}$, we define ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Q_{r}}}(x
)=\mathbf{0}$.

The distributions of the $\xi_{i}(x,r)$ minimize variance over distributions with support $\{0,1/r,\ldots,1\}$,
ensuring unbiasedness, i.e. $\mathbb{E}\left[\xi_{i}(x,r)\right]=\left|x_{i}\right|/\|x\|_{2}$.
This definition is based on an equivalent one in Alistarh et al. ().

###### Definition 3.1 .

###### Definition 3.2 .

### 3.2 Introduction of the Algorithms

FedComLoc (Algorithm 1) is an adaptation of Scaffnew,
with modifications for compression. ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Top}K}(\cdot)$ is used as the default compression technique for simplicity, although quantization is equally applicable.
We examine three distinct variants in our ablations:

- •
FedComLoc-Com: This variant addresses the communication bottleneck.
It focuses on compressing the uplink network weights transmitted from each client to the server.
This setup is adopted as our default setting.
- •
FedComLoc-Local: Here, the local model is compressed during each training step.
This addresses limited computational power and resources available to each client.
- •
FedComLoc-Global: Here, the server model is compressed before sending it to the clients.
This variant is tailored for FL situations where downloading the model from the server is costly e.g. due to network bandwidth constraints.

Figure: Figure 1: Performance outcomes for various Top-K ratios. In the table, the row Accuracy shows the maximal test accuracy achieved after hyperparameter tuning. The row Decrease highlights the decline in test accuracy when comparing a sparsified model to its unsparsified counterpart ($K=100\%$). The plots show training loss and test accuracy over the number of communication rounds and communicated bits.
Refer to caption: x1.png

Figure: Figure 2: Training loss and test accuracy with respect to communication rounds and communication bits for a density ratio of $K=10\%$.
Refer to caption: x3.png

## 4 Experiments

##### Baselines.

Our evaluation comprises three distinct aspects.
Firstly, we conduct experiments to assess the impact of compression on communication costs.
FedComLoc is assessed for varying sparsity and quantization ratios.
Secondly, we compare FedComLoc-Com with FedComLoc-Local and FedComLoc-Global.
Thirdly, we explore the efficacy of FedComLoc against non-accelerated local training methods,
including FedAvg (McMahan et al., ), its Top-K sparsified counterpart sparseFedAvg,
and Scaffold (Karimireddy et al., ).

##### Datasets.

Our experiments are conducted on FedMNIST (LeCun, ) and FedCIFAR10 (Krizhevsky, ) with the data processing framework FedLab (Zeng et al., ).
For FedMNIST, we employ MLPs with three fully-connected layers, each coupled with a ReLU activation function.
For FedCIFAR10, we utilize CNNs with two convolutional layers and three fully-connected layers.
Comprehensive statistics for each dataset, details on network architecture and training specifics can be found in
Appendix A.

Figure: Tuned Stepsize.
Refer to caption: x5.png

##### Heterogeneous Setting.

We explore different heterogeneous settings.
Similar to  (Zhang et al., ; Yi et al., ), we create heterogeneity in data by using a Dirichlet distribution, which assigns each client a vector indicating class preferences.
This vector guides the unique selection of labels and images for each client until all data is distributed.
The Dirichlet parameter $\alpha$ indicates the level of non-identical distribution.
We also include a visualization of this distribution for the CIFAR10 dataset in Appendix B.1.1.

##### Default Configuration.

In the absence of specific clarifications, we adopt the Dirichlet factor $\alpha=0.7$. To balance both communication and local computation costs, we use $p=0.1$, resulting in an average of 10 local iterations per communication round.
The learning rate is chosen by conducting a grid search over the set $\{0.005,0.01,0.05,0.1,0.5\}$.
With communication costs being of most interest, our study employs FedComLoc-Com as the default strategy.
The experiments are run for $2500$ communication rounds for the CNN on FedCIFAR10 and $500$ rounds for the MLP on FedMNIST.
Furthermore, the dataset is distributed across $100$ clients from which $10$ are uniformly chosen to participate in each global round.

Furthermore, in our Definition 3.1 of ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Top}K}$, $K$ is the number of nonzero parameters.
However, we will rather specify the enforced density ratio, i.e. the ratio of nonzero parameters. For instance, specifying $K=30\%$ means retaining $30\%$ of parameters.

### 4.1 Top-K Sparsity Ratios

This section investigates the effects of different sparsity rations by investigating ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Top}K}$ ratios on FedMNIST.
The outcomes can be found in Table 1.
Notably, $K=10\%$ in ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Top}K}$ yields an accuracy of $0.9374$, merely 3.94% lower than the $0.9758$ unsparsified baseline.
Remarkably, a 70% sparsity level ($K=30\%$) attains commendable performance, with only a 1.07% accuracy reduction, alongside a 70% reduction in communication costs.
Furthermore, from the communication bits depicted in Figure 1 it is evident that sparsity yields faster convergence, the more so with increased sparsity (smaller $K$).

### 4.2 Data Heterogeneity/Dirichlet Factors

This subsection aims to assess the impact of varying degrees of data heterogeneity on FedMNIST.
Hence, an analysis of the Dirichlet distribution factor $\alpha$ is presented, exploring the range of values $\alpha\in\{0.1,0.3,0.5,0.7,0.9,1.0\}$.
Remember that a lower $\alpha$ means increased heterogeneity.
Alongside, we examine the influence of different ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Top}K}$ factors, specifically $10\%,50\%$ and $100\%$.
The results are shown in Table 2.
Figure 2 reports training loss and test accuracy for a sparsity ratio of 90% ($K=10\%$).
Additionally, round-wise visualizations for $K=50\%$ and $K=100\%$ (non-sparse) are presented in Figure 10 in the Appendix.

Key observations from our study include:

a) When examining the effects of the heterogeneity degree $\alpha$ (as seen in each column of Table 2),
we observe that sparsity performance is influenced by heterogeneity degrees.
For instance, $\alpha=0.1$ results in a relative performance drop of 9.79% from an unsparsified to a sparsified model with $K=10\%$.
In contrast, for $\alpha=0.3$, this drop is 5.80%, and for $\alpha=1.0$, it is 3.63%.
Interestingly, for commonly used heterogeneity ratios in literature ($\alpha=0.3,0.5,0.7$), the performance drop does not decrease substantially when moving from $\alpha=0.3$ to $\alpha=0.5$, or from $\alpha=0.5$ to $\alpha=0.7$, unlike the shift from $\alpha=0.1$ to $\alpha=0.3$.

b) Focusing on the rows of Table 2, we find that lower sparsity ratios are more sensitive to heterogeneous distributions.
In particular, observe that with $K=10\%$, the absolute performance improvement from $\alpha=0.1$ to $\alpha=1$ is $7.01\%$. However, for $K=50\%$, this improvement is only $1.22\%$.

c) It should be noted that each method was run with a fixed learning rate without scheduling, and the maximum communication round was set to 1000.
Previous studies suggest that higher sparsity ratios require more communication rounds in centralized settings (Kuznedelev et al., ).
This phenomenon was also observed in our FL experiments.
Therefore, there is the potential for performance enhancement through sufficient model rounds and adaptive learning rate adjustments, especially for methods with higher sparsity.

Figure: Figure 4: FedComLoc employing ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Q_{r}}}(\cdot)$. The number of quantization bits $r$ is set to $r\in\{4,8,16,32\}$.
Refer to caption: x9.png

Figure: Figure 5: Data heterogeneity ablations for FedComLoc utilizing ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Q_{r}}}(\cdot)$ with number of bits $r$ either $8$ or $16$. The same results plotted over the number of communication rounds can be found in Figure 11 in the Appendix.
Refer to caption: x11.png

### 4.3 CNNs on FedCIFAR10

This section repeats the experiments for CIFAR10 and a Convolutional Neural Network (CNN).
We explored a range of stepsizes ($\gamma\in\{0.005,0.01,0.05,0.1|\}$).
Further information is provided in Appendix A.
The CIFAR10 results, which involve optimizing a Convolutional Neural Network (CNN), are presented in Figure 3
for both tuned and a fixed step size.
Observe the accelerated convergence of sparsified models in terms of communicated bits when the step size is tuned.
Interestingly, a sparsity of $90\%$ ($K=10\%$) shows faster convergence in terms of communication rounds (as shown in the first column),
suggesting the potential for enhanced training efficiency in sparsified models.
For a fixed step size (the two rightmost columns of Figure 3) and $K=10\%$, one can observe slower convergence compared to other configurations.
This indicates that sparsity training requires more data and benefits from either increased communication rounds or a larger initial stepsize.
This aligns with recent similar findings in the centralized setting (Kuznedelev et al., ).

### 4.4 Quantization

This section explores using quantization ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Q_{r}}}$ for compression with the number of bits, $r$, set to $r\in\{4,8,16,32\}$ on FedMNIST.
This approach aligns with the methodologies outlined in Alistarh et al. ().
The results after 1000 communication rounds are illustrated in Figure 4.
Our analysis reveals that quantization offers superior performance compared to ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Top}K}$-style sparsity.
For instance, with 16-bit quantization corresponding to a 50% reduction in communication cost, the performance decrease is a mere $0.14\%$,
Furthermore, Figure 5 shows outcomes for different degrees of data heterogeneity.
These findings demonstrate that quantization reduces communication at minor performance tradeoff while also exhibiting only minor sensitivity to data heterogeneity.
The Appendix gives further results for both FedMNIST (section B.2.1) and FedCIFAR10 (section B.2.2).

### 4.5 Number of Local Iterations

This section explores the performance impact of varying the expected number of local iterations on FedMNIST.
The expected number of local iterations is $1/p$ where $p$ is the communication probability.
Hence, we investigate the influence of $p$ ranging from $p\in\{0.05,0.1,0.2,0.3,0.5\}$.
Furthermore, $K=30\%$ is used.
The results are presented in Figure 6.
A key finding is that more local training rounds (i.e. smaller $p$) not only accelerate convergence but can also improve the final performance.

Figure: Figure 6: Loss and test accuracy over communication rounds and total costs. Total costs are a combined measurement of both communication costs and local computation cost. A communication round has unit cost while a local training round has cost $\tau$. In a realistic FL system, $\tau$ is typically much less than 1, as the primary bottleneck is often communication and hence we set $\tau=0.01$.
Refer to caption: x13.png

Figure: (a) $K=50\%$
Refer to caption: x15.png

Figure: (a) $K=10\%$
Refer to caption: x17.png

### 4.6 FedComLoc Variants

In this section, we compare FedComLoc-Local, FedComLoc-Com, and FedComLoc-Global on FedCIFAR10.
The findings are illustrated in Figure 8.
Observe that at high levels of sparsity (indicated by a small $K$ in ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Top}K}$), FedComLoc-Com underperforms the other algorithms.
This could be attributed to the heterogeneous setting of our experiment: each client’s model output is inherently skewed towards its local dataset.
When this is coupled with extreme ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Top}K}$ sparsification, more bias is introduced, which adversely affects performance.
Conversely, at low sparsity (e.g. $K=90\%$), FedComLoc-Com surpasses FedComLoc-Global.
In addition, we observe that sparsity during local training (i.e. FedComLoc-Local) tends to yield better results.
One possible explanation is that due to the local data bias the communication bandwidth between client and server might be crucial.
Remember that FedComLoc-Local had no communication compression while both FedComLoc-Com and FedComLoc-Global do.
Further FedMNIST results are shown in the Appendix.

### 4.7 FedAvg and Scaffold

In this section, the performance of FedComLoc is compared with baselines in form of FedAvg (McMahan et al., ) and Scaffold (Karimireddy et al., ) on FedCIFAR10.
Furthermore, a sparsified version of FedAvg is employed, termed as sparseFedAvg.
For sparseFedAvg a learning rate of $0.1$ is used, whereas for FedComLoc, a lower rate of $0.05$ is utilized.
The outcomes of this analysis are depicted in Figure 7.
The left part illustrates the performance of compressed models.
We observe notably faster convergence for FedComLoc-type methods in comparison with sparseFedAvg despite the lower learning rate.
The right part of the figure compares FedAvg with Scaffold, devoid of sparsity, using an identical learning rate of $0.005$.
This uniform rate ensures that each method achieves satisfactory convergence over a sufficient number of epochs.
Here again, faster convergence is demonstrated with FedComLoc.

## 5 Conclusion and Future Work

This paper advances the field of FL by tackling one of its main challenges, namely its high communication cost.
Building on the accelerated Scaffnew algorithm (Mishchenko et al., ), we introduced FedComLoc.
This novel approach blends the practical compression techniques of model sparsity and quantization into the efficient local training framework.
Our extensive experimental validation shows that FedComLoc preserves computational integrity while notably cutting communication costs.

Future research could explore the reduction of internal variance in stochastic gradient estimation, akin to the approach described in Malinovsky et al. (). The FedComLoc-Global algorithm we propose offers potential for obtaining a sparsified model suitable for deployment. Additionally, investigating the development of an efficiently sparsified deployed model extensively presents an intriguing avenue for further study.

## Acknowledgement

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

## Appendix A Experimental Details

### A.1 Datasets and Models

Our research primarily focuses on evaluating the effectiveness of our proposed methods and various baselines on widely recognized FL datasets. These include Federated MNIST (FedMNIST) and Federated CIFAR10 (FedCIFAR10), which are benchmarks in the field. The use of the terms FedMNIST and FedCIFAR10 is intentional to distinguish our federated training approach from the centralized training methods typically used with MNIST and CIFAR10.
The MNIST dataset consists of 60,000 samples distributed across 100 clients using a Dirichlet distribution.
For this dataset, we employ a three-layer Multi-Layer Perceptron (MLP) as our default model. CIFAR10, also comprising 60,000 samples, is utilized in our experiments to conduct various ablation studies.
The default setting for our FedCIFAR10 experiments is set with 10 clients. The model chosen for CIFAR10 is a Convolutional Neural Network (CNN) consisting of 2 convolutional layers and 3 fully connected layers (FCs).
The network architecture is chosen in alignment with (Zeng et al., ).

### A.2 Training Details

Our experimental setup involved the use of NVIDIA A100 or V100 GPUs, allocated based on their availability within our computing cluster. We developed our framework using PyTorch version 1.4.0 and torchvision version 0.5.0, operating within a Python 3.8 environment. The FedLab framework (Zeng et al., ) was employed for the implementation of our code.
For the FedMNIST dataset, we established the default number of global iterations at 500, whereas for the FedCIFAR10 dataset, this number was set at 2500. We conducted a comprehensive grid search for the optimal learning rate, exploring values within the range of $[0.005,0.01,0.05,0.1]$. Our intention is to make the code publicly available upon the acceptance of our work.

Figure: (a) $\alpha=0.1$
Refer to caption: x22.png

## Appendix B Complementary Experiments

### B.1 Exploring Heterogeneity

#### B.1.1 Visualization of Heterogeneity

The Dirichlet non-iid model serves as our primary means to simulate realistic FL scenarios. Throughout this paper, we extensively explore the effects of varying the Dirichlet factor $\alpha$ and examine how our algorithms perform under different degrees of data heterogeneity.
In Figure 9, we present a visualization of the class distribution in the FedCIFAR10 dataset. We visualize the first 10 clients. This illustration clearly demonstrates that a smaller $\alpha$ results in greater data heterogeneity, with $\alpha=1000$ approaching near-homogeneity. To further our investigation, we conduct thorough ablation studies using values of $\alpha$ in the range of $[0.1,0.3,0.5,0.7,0.9,1.0]$.
It is important to note that an $\alpha$ value of 1.0, while on the higher end of our test spectrum, still represents a heterogeneous data distribution.

#### B.1.2 Influence of Heterogeneity with Non-Compressed Models

In our previous analyses, the impact of sparsified models with a sparsity factor $K=10\%$ was illustrated in Figure 2, and the effects of quantized models were depicted in Figure 5. Extending this line of inquiry, we now present additional experimental results that explore the influence of data heterogeneity on models with $K=50\%$ and those without compression, as shown in Figure 10.
Our findings indicate that while model compression can result in slower convergence rates, it also potentially reduces the total communication cost, thereby enhancing overall efficiency.
Notably, a Dirichlet factor of $\alpha=0.1$ creates a highly heterogeneous setting, impacting both the speed of convergence and the final accuracy, with results being considerably inferior compared to other degrees of heterogeneity.

Figure: Figure 10: Exploration of variations in loss and accuracy across diverse sparsity ratios, communication rounds, and communicated bits is depicted through our figures. The first set of four figures on the left showcases results obtained with a sparsity ratio of $K=50\%$. In contrast, the corresponding set on the right, consisting of another four figures, represents scenarios where $K=100\%$, indicative of scenarios without model compression.
Refer to caption: x28.png

### B.2 Complementary Quantization Results

#### B.2.1 Additional Quantization Results on FedMNIST

In Figure 5, we presented the quantization results in terms of communicated bits. For completeness, we also display the results with respect to communication rounds in Figure 11.

Figure: Figure 11: FedComLoc utilizing ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Q_{r}}}(\cdot)$ with a fixed $r$ value of $8$ (as shown in the left figure) and $16$ (in the right figure) with respected to communication rounds. We conduct ablations across various $\alpha$.
Refer to caption: x32.png

#### B.2.2 Quantization on FedCIFAR10

Previously, in Figure 4, we detailed the outcomes of applying quantization to the FedMNIST dataset.
This section includes an additional series of experiments conducted on the FedCIFAR10 dataset.
The results of these experiments are depicted in Figure 12.
Consistent with our earlier findings, we observe that quantization considerably reduces communication costs
with only a marginal decline in performance.

Figure: Figure 12: FedComLoc with ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@color@rgb@fill{0}{0}{0}{\rm Q_{r}}}(\cdot)$ on CIFAR10.
Refer to caption: x36.png

### B.3 Double Compression by Sparsity and Quantization

In Sections 4.1 and 4.4, we individually investigated the effectiveness of sparsified training and quantization. Building on these findings, this section delves into the combined application of both techniques, aiming to harness their synergistic potential for enhanced results. Specifically, we first conduct Top-K sparsity and then quantize the selected Top-K weights. The outcomes of this exploration are depicted in Figure 13.
The left pair of figures illustrates that applying double compression with a higher degree of compression consistently surpasses the performance of lower compression degrees in terms of communication bits. However, the rightmost figure presents an intriguing observation: considering the communicated bits and convergence speed, there is no distinct advantage discernible between double compression and single compression when they are set to achieve the same level of compression.

Figure: Figure 13: Comparison with double compression by sparsity and quantization.
Refer to caption: x38.png

## Peer Reviews

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
questions: 1. Why was Scaffnew chosen specifically for this study? What unique characteristics of Scaffnew make it suitable for the proposed compression techniques compared to other algorithms?
1. Do the authors expect the empirical observations to generalize to other algorithms using the same compression schemes? If so, could the paper include a discussion on the expected performance of these compression schemes when applied to other popular algorithms?
1. If the goal is to develop a communication-efficient algorithm that outperforms the state-of-the-art (SOTA), what are the current SOTA methods in communication efficiency? The proposed method integrates compression schemes with one particular algorithm. Are there other approaches that might achieve comparable communication efficiency in federated learning? A review and comparison with SOTA methods could strengthen the context of this work.
1. Are the sub-captions in Figure 1 accurate, or could there be some typos that need correction? Please confirm and revise if necessary to ensure clarity.
soundness: 1
strengths: - The paper reports and discusses the empirical performances of FedComLoc in different configurations and hyperparameter settings, including heterogeneity, quantization bits, and TopK sparsities.
- The paper presents some interesting observations based on the numerical results.
summary: This paper presents an empirical study on a new algorithm, FedComLoc, which extends Scaffnew by integrating compression techniques: TopK and quantization. Three settings of the proposed algorithm are evaluated: (i) compressing the communication from client to the server; (ii) compressing the local model itself; and (iii) compressing the communication from the server to each client. The paper reports the empirical performances for these configurations by using FedMNIST and FedCIFAR10 with varying degrees of heterogeneity.
weaknesses: - The scope of the paper is narrow, focusing solely on one algorithm, Scaffnew, with a basic integration of existing compression schemes. The paper lacks justification for why Scaffnew was chosen over other potential algorithms.
- The paper provides an insufficient review of existing communication-efficient FL approaches (e.g., FedEF [1]). These existing approaches were also missing in the numerical experiment.
- The experimental setup is not extensive, relying only on image datasets and simple models: MLPs and CNNs. Given the paper's empirical focus without theoretical analysis or in-depth discussion, it is challenging to generalize the findings. Moreover, the numerical comparison is limited and lacks breadth.
- The paper offers no new insights or findings beyond empirical results and observations. The main conclusion appears to be: "we can apply compression schemes to Scaffnew."

**Reference**
1. Li and Li. Analysis of error feedback in federated non-convex optimization with biased compression: Fast convergence and partial participation. ICML, 2023.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: Please refer to the weaknesses section for details.
soundness: 2
strengths: 1. The paper is clearly well-written, concise, and easy to follow.
summary: This paper explores communication reduction techniques for a federated optimization method called Scaffnew. The proposed approach demonstrates that Scaffnew can be combined with various communication reduction techniques on both the local and global sides. Empirical results illustrate the effectiveness of FedComLoc in reducing communication overhead while maintaining comparable performance.
weaknesses: 1. My major concern is the novelty and technical contribution of this paper. Model compression techniques, such as top-k and quantization, are already widely used and well-established. Integrating these compression methods with an FL algorithm appears to be an incremental contribution. While this approach does address the communication cost challenges in Scaffnew, it is not immediately clear to me how applying model compression introduces new challenges or is non-trivial. Therefore, the technical contribution seems relatively weak to me.

2. It appears that the proposed algorithm and experiments are conducted under a partial participation setting in FL. This could lead to potential “asynchronous” issues in FedComLoc-Global: since there is no model initialization step in FedComLoc, a client that has not participated in the previous $t-1$ steps would begin local training in the $t$-th step with an outdated model. This lack of updated model initialization may result in poorer convergence, particularly when only a small fraction of clients participate in the training.

3. There are several issues with the presentation of the experimental results:

a. The caption of the subfigures in Figure 1 mentions sparsity, but the curves also represent sparsity.

b. The results in the table in Figure 6 conflict with those in the subfigure within the same figure.

c. The caption of Figure 8 states that there is a comparison with FedDyn, but the subfigures do not include this baseline.

d. What is the purpose of K=100% (no sparsity) in Figure 8? It seems this is intended to compare Scaffnew with FedAvg and Scaffold.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
questions: 1. In line 14 and in line 24 when you write 'heterogeneous clients' and 'heterogeneous settings', respectively,  it is unclear if you mean to heterogeneity in data or local hardware or both. 
2. In lines 28-29: "Privacy concerns and limited computing resources on edge devices often make centralized training impractical, where all data is gathered in a data center for processing." Maybe you mean "Privacy concerns and limited computing resources on  a data center often make..."?
3. In lines 38-39: "Our primary objective is to solve the problem (ERM) and deploy the optimized global model to all clients.". Actually, in FL, it is often the server who wishes to obtain the optimal model rather than the local users.  The users are contributing their local private datasets to the process of learning, "serving" the centralizing server.
4. In line 40 there is a typo, it should be 'is' instead of 'are'.
5. In lines 54-55: "Quantization is another efficient model compression technique..., though its application in heterogeneous settings is limited". Quite a harsh statement. Do you have any references supporting it?
6. In lines 71-74 you claim that FedComLoc is specially designed for heterogenous environments. My question is why do you claim that, as your adopted compression methods, encompassing TopK and quantization, are generic tools in compression; and furthermore, your numerical evolutions involve the non-iid local datasets scenario, as in standard FL experimental studies.
7. In lines 75-78 you mentioned that the integration of compression communication into Scaffnew is studied in either of client-to-server, server-to-client, and client-storage possibilities. Actually, as also covered by the majority of compressed FL works, it is the client-to-server communication bottleneck that is the most crucial one to be relaxed. 
8. Algorithm 1 is almost unreadable without being closely familiar with Scaffnew. For the paper to be a stand-alone one, you should specify in the accompanied text the not-intuitive-usages therein; e.g., control variates, the role probability, etc.
9. In theoretical studies of compressed FL, it is typically revealed that the integration of compression slows downs the convergence rate obtained without it. Can you explain how in the rightmost column of Fig. 3 the reversed is evidenced?
10. In lines 365-366: "Observe the accelerated convergence of sparsified models in terms of communicated bits...". It is not clear how this is being calculated. That is, to translate K into bits one can do, e.g., if K=10% set  R=0.1*b when b it the used-bits in full-precision, mostly 32 or 64. What the x-axis of 'Communication Bits' measures in your case? 
11. It would be interesting to compare the performance of quantization and sparsification for the same bit rate...
12. In lines 370-371: "This indicates that sparsity training requires more data and benefits from either increased communication rounds...". Benefits? according to my understanding more communication rounds imply slower overall convergence (that takes longer time); which is not wanted. Can you explain that?
soundness: 2
strengths: Clarity:
- The paper is overall well written and organized.
- The experiments' accompanied details and explanations are overall well presented. 
- The ablation study is quite comprehensive.
summary: In this work the authors suggest to incorporate compression, via sparsification (TopK) and (random) quantization, into the established Scaffnew algorithm of Mishchenko et al. (2022); where the latter considerably advanced the reduction of communication complexity in federated learning. The integration of compressed communication into Scaffnew is studied in either of client-to-server, server-to-client, and client-storage possibilities; and experimentally verified using MNIST and CIFAR10 datasets in the non-iid local datasets scenario.
weaknesses: Significance & Quality:
- Compression in FL has been extensively studied. It is  of lessen motivation to incorporate it into multiple SGD local iterations, what already by itself relaxes the communication overhead compared to single SGD local iteration, as communicating the local gradients to the server occurs less often. 
- As stated by the authors in lines 177-179, this work's integration of compression in Scaffnew is merely heuristic and solely provides numerical evaluations for CompressedScaffnew (Condat et al., 2022); where the latter studies the theoretical aspects of general lossy compression integrated into Scaffnew in convex settings. 
- The majority of FL papers with provable convergence guarantees employ convex settings in their theoretical evolutions and non-convex ones in their experimental studies; having deep neural networks fit into that regime. 
- The CompressedScaffnew presents the idea of compressed Scaffnew, provides analytical study under the convex setting, and presents simulations that, unusually to their respective related works, covers only simplistic logistic regression model rather than diverse deep learning architectures. The significance of this paper is thus equivalent to the importance of a full-length comprehensive experiments section of the work CompressedScaffnew; i.e., one that includes simulations on general neural networks beyond the simplified logistic regression model. As a result, the merit of this paper to a conference such as ICLR is of minor contribution.

Originality:
- The idea learned in this paper is not new and was already presented, and also analytically analyzed, in CompressedScaffnew (Condat et al., 2022). The numerical simulations of this idea are claimed to be the novelty of the presented work, and by themselves are insufficient.
- The authors further claim in lines 169-171 that the studies of CompressedScaffnew (Condat et al., 2022) are not practical as they require
shared randomness. Yet, a bulk of works studying compressed FL utilize pseudo-random methods upon which sharing a common seed can overcome the necessity of shared randomness.