ZeroFL: Efficient On-Device Training for  Federated Learning with Local Sparsity
Authors: Xinchi Qiu
Javier Fernandez-Marques
Pedro PB Gusmao
Yan Gao
Titouan Parcollet
Nicholas Donald Lane
Venue: ICLR 2022 Poster (2022)
Keywords: Federated Learning
sparse training

Abstract: When the available hardware cannot meet the memory and compute requirements to efficiently train high performing machine learning models, a compromise in either the training quality or the model complexity is needed. In Federated Learning (FL), nodes are orders of magnitude more constrained than traditional server-grade hardware and are often battery powered, severely limiting the sophistication of models that can be trained under this paradigm. While most research has focused on designing better aggregation strategies to improve convergence rates and in alleviating the communication costs of FL, fewer efforts have been devoted to accelerating on-device training. Such stage, which repeats hundreds of times (i.e. every round) and can involve thousands of devices, accounts for the majority of the time required to train federated models and, the totality of the energy consumption at the client side. In this work, we present the first study on the unique aspects that arise when introducing sparsity at training time in FL workloads. We then propose ZeroFL, a framework that relies on highly sparse operations to accelerate on-device training. Models trained with ZeroFL and 95% sparsity achieve up to 2.3% higher accuracy compared to competitive baselines obtained from adapting a state-of-the-art sparse training framework to the FL setting.

Published as a conference paper at ICLR 2022
ZEROFL: EFFICIENT ON-DEVICE TRAINING FOR FEDERATED LEARNING WITH LOCAL SPARSITY
Xinchi Qiu"!", Javier Fernandez-Marques", Pedro P. B. Gusmao', Yan Gao', Titouan Parcollet and Nicholas D. Lane'
1 Department of Computer Science and Technology, University of Cambridge
2 Department of Computer Science, University of Oxford
3 Laboratoire Informatique d' Avignon, Avignon Université
ABSTRACT
When the available hardware cannot meet the memory and compute requirements to efficiently train high performing machine learning models, a compromise in either the training quality or the model complexity is needed. In Federated Learn- ing (FL.,, nodes are orders of magnitude more constrained than traditional server- grade hardware and are often battery powered, severely limiting the sophistication of models that can be trained under this paradigm. While most research has fo- cused on designing better aggregation strategies to improve convergence rates and in alleviating the communication costs of FL, fewer efforts have been devoted to accelerating on-device training. Such stage, which repeats hundreds of times (i.e. every round) and can involve thousands of devices, accounts for the majority of the time required to train federated models and, the totality of the energy consumption at the client side. In this work, we present the first study on the unique aspects that arise when introducing sparsity at training time in FL workloads. We then pro- pose ZeroFL, framework that relies on highly sparse operations accelerate on-device training. Models trained with ZeroFL and 95% sparsity achieve up to 2.3% higher accuracy compared to competitive baselines obtained from adapting a state-of-the-an sparse training framework to the FL setting.
INTRODUCTION
Despite it being a relatively new subfield of machine learning (ML), Federated Learning (FL) (McMahan et al. 2017 Reddi et al. 2021 Horvath al., 2021 has become an indispens- able tool to enable erivac-presseving collaboratively learning, as well as to deliver personalised models tailored to the end-user's s local data and context (Arivazhagan et al. 2019 Hilmkil et al.
2021 Cheng et al.) (021). For example: next-word prediction (Hard et al. 2018), physical activity detection (Doherty et al. 2017), keyword spotting (Hard et al. 2020). among others.
Unlike standard centralised training. which normally takes place on the Cloud and makes use of powerful hardware (Hazelwood et al.] 2018). FL. is envisioned to run on commodity devices such as smartphones or IoT devices often running of batteries, which are orders of magnitude more stricted in terms of compute, memory and power consumption (Qiu et al.] (021). This triplet of factors drastically limits the complexity of the ML models that can be trained on-device in fed- erated manner, ceiling their usefulness for the aforementioned applications as a result. In order to adjust the memory and compute footprints of complex MI. model to the FL setting, the research community has presented a number of approaches including: the use of distillation (Hinton et al., 2015) to enable the aggregation
the server side of heterogeneous model architectures (e.g. based on the compute capabilities of each device) that collaboratively train a single global model (Lin et al.) 2020 Zhu al.) 202T); group knowledge transfer algorithm (He al. 2020); federated dropout, by which clients perform local training on a sub-model of the global model (Caldas et al., 2019), trans- lates into lower overall communication costs and, enables better support for heterogeneous pools of clients regardless of their compute capabilities (Horvath et al., [021]; and, more generally, better aggregation strategies that enable faster convergence (Li et al. 2018 Reddi et al. 202T), reducing in
* Equul contribution. Correspondence to Xinchi Qiu (xq2270 cam.. ac. uk) or Javier Fernandez-Marques (javi fernandezma rques nacre. ox. uk).

---

Published as a conference paper at ICLR 2022
this way overall device utilization (e.g. fewer local epochs) and number of communication rounds. Other optimization techniques such as quantization and sparsity have been used in the context of FL but mostly as way to reduce communication costs (Liu et al. 2021 Amiri al. 2020 Shahid et al.
2021 but not to accelerate on-device training.
The use of sparse operations (e.g. convolutions) training time has recently been shown to be an effective technique to accelerate training in centralised settings (Sun et al.] [017 Goli & Aamodi 2020 Raihan & Aamodi 2020). The resulting models are as good or close their densely-trained counterparts despite reducing by up to 90% their FLOPs budget and, resulting in an overall up to 3.3x training speedup. Acceleration is achieved by performing sparse convolutions during the forward and/or backward pass, which requires at least one of the operands (i.e. inputs, weights, gra- dients) to be sufficiently sparse and, software and hardware support for such operations. However, it is unclear how the different -pe-spccfic challenges (i.e. data imbalance, stateless clients, periodic aggregation) will restrict the quality of the global model.
This work considers the challenges and opportunities of inducing high levels of sparsity to accelerate training on-device for FL workloads, and provides the following contributions:
The first framework for Federated Learning that leverages sparsity as a mechanism to ac- celerate on-device training by inducing up to 95% sparse weights and activations. This work considers three popular datasets: CIFAR-10 and FEMNIST for image classification and, SpeechCommands for audio classification.
A study on the unique aspects that arise when introducing sparsity at training time in FL: the degree of overlap between non-zero values decreases with layer-depth index and, the locations of zero-valued weights in the global model remain constant throughout most of the training rounds. Our discussion sets the foundations for future research in this area.
A technique that alleviates the accuracy degradation when applying a state-of oort-h--rt-rtttt off- the-shelf sparsification method to the FL domain. ZeroFL achieves +2.3% and +1.5% higher accuracy than baselines when inducing 90% and 95% sparsity respectively. In addi- tion, ZeroFL. also leverages sparsity when transferring the local models the central server reducing communication costs by 3.0x while still outperforming competitive baselines.
RELATED WORK
Pruning neural networks involves discarding parts of the model (e.g. individual weights or entire channels) that are irrelevant for solving the task at hand. This procedure generally produces a lightweight model representation more suitable for deployment on constrained devices with limited memory and compute budgets. In this section we detail how different forms of pruning sparsifi- cation have been used to accelerate inference and, to a lesser extent, training. We also discuss how these have been introduced to reduce communication costs in distributed and federated learning.
Unstructured pruming. Frameworks relying on unstructured pruning (Han et al.) 2015a b Guo let al. 2016 Molchanov et al., 2017) often achieve higher compression ratios the expense of inference stages being as compute intensive in practice as those of the original model. This is be- cause, assuming pruning has been homogeneously applied on the model, sparse operations can only be efficiently accelcrated on supported hardware, such as modern GPUs (Wang] 2020; Zachariadis al., 2020, Hong et al., 2018) or custom accelerators (Zhang et al. 2016 Lu et al. 2019; Srivas- tava et al.] 2020), for a sufficienlly high sparsity ratio. The lower the ratio, the less likely sparse operations would translate into measurable speedups. In the case of CPUs, speedups due to sparse operations where one operand is unstructurally sparse are often only feasible at 90% sparsity ratios or higher (Hong et al. 2019: Wang 2021).
Structured pruning. Methods that apply structured pruning (He et al., 2018 2017 Jion-Hao Luo & Lin 2017 Yu et al., 2018 Molchanov et al. 2019 Wang et al. 2017). 7) on the other hand, trade com- pression for acceleration potential. These approaches modify the underlying computational graph by discarding entire channels, resulting in smaller but still dense convolution operations, or by re- moving the nodes all together if an entire layer is set to be removed by the chosen pruning strategy. As a result, structured pruning frameworks are the preferred option when aiming to accelerate in- ference general purpose hardware. A body of work across structured and unstructured pruning
2

---

Published as a conference paper at ICLR 2022
methods, attempts induce structure in otherwise randomly sparse networks S. Gray & Kingma 2017); Ren et al. 2018); Wen et al. 2020);; Verelst & Tuytelaars (2020). This is often referred to as block sparsity and consists in subdividing the matrix representations of inputs or weights into tiles (e.g. 16x16 tiles), and restrict the training in such a way that some tiles contain only zeros while the rest remain dense and real-valued. Matrix-matrix multiplications following such a pattern be accelerated at lower global sparsity ratios compared to those following unstructured sparsity Hoefler ct al.] (2021). Other forms of constraining how sparsity occurs have been proposed, for example, aware reordering on the sparsity pattern of the weights Elsen et al. (200). This can be used to ensure high cache reuse on Cortex-A A mobile CPUs, resulting 2.4x acceleration of MobileNets.
Sparse training. The majority of works making use of sparsity are envisioned for either model compression or to accelerate inference. Only recently, sparse operations have been considered to accelerate training. The work of Sunn et (2017) presented mechanism to induce high levels of sparsity in the gradients during backpropagation and, demonstrated large speedups when training MLP-only models. More recently, Goli & Aamodt (2020) build upon the observation that gradients from consecutive batches are near identical. They present a framework to reuse a random sample of previously computed gradients and their thresholded difference w.r.t gradients from the current batch, resulting in a sparse tensor. Their framework accelerates training of CNNs by performing sparse convolutions during the backward pass at the cost of pre-computing partial gradients during forward pass. Closer to our work is SWAT (Raihan & Aamodi (020). a framework that relies on sparsified weights during inference and sparsified weights and activations for backward propagation.
Compression on communication. Konečný et al. (0016) proposed to restricts the updates of weight matrices to have a pre-specified structure in order reduce the total communication cost. The structure can either be random or low-rank structure. ATOMO (Wang et al.] 2018) introduced a generalised gradient decomposition and sparsification technique, aiming to reduce the gradient sizes communicated upstream. |Han et al. (2020) proposed different way of aggregation in the server, which instead of aggregating model weights, aggregates the sparsified gradients after every local update step. However, since the method requires to aggregate sparsified gradient after every step, it cannot benefit from multiple local updates. Hence it might require extra communication rounds to reach the target performance. PruneFL Jiang et al. (2019) reduced both computation and communi- cation overhead to minimize the overall training time by including an initial pruning at one selected client and further pruning part of FL process.
Nevertheless, none of the aforementioned works explored the challenges of extending state-of-the- art sparsification methods to federated learning a way accelerate on-device training. With ZeroFI,, a framework specifically tailored to the FL. setting, achieves better accuracy retention than with existing methods that remain exclusive to the centralised training paradigm.
BACKGROUND
This section describes the state-of-the-art sparse training method SWAT (Raihan & Aamodi 2020); the way we adapt it to the FL contexts; and the related challenges that would need be addressed.
3.1 SPARSE WEIGHTS AND ACTIVATIONS TRAINING
The SWAT framework embodies two strategies in the training process. During each forward pass, the weights are partitioned into active weights and non-active weights by a top-K (in magnitude) operator and only the active weights are used. For the 1th layer in the model, the layer maps the
input activations d:-1 1 onto feature maps or using function fi: or = fi(a)-1, uy). In this work we consider fi being the 3 x 3 convolution in the (-th layer. In the backward pass, the gradient of input activations (Va-1) and the gradient of weights (Vw) are calculated represented by functions G and H,, as shown below:
7a-1 = Gi(Vai, wi)
V Hi(va, a1-1)
(2)
Then in the backward pass, the retained layer inputs 0;-1 also partitioned into active and non- active by using the same top-K procedure. This results in full gradients and active weights being used in Eq. [ while full gradients and active activations are used in Eq. It is worth noticing
3

---

Published as a conference paper at ICLR 2022
that weights and activations and sparsified in the forward and backward pass, the gradients generated through the training process are dense. Therefore, the resulting model is a dense. The compute cost of updating weights wi given dense w tensor is negligible compare to the savings due to performing the underlying convolutions in Eq 2 as this is essentially a weighted sum.
3.2 FROM CENTRALISED TO FEDERATED SPARSE TRAINING
A direct adaptation of the SWAT framework to the FL setting could be done by framing each local training stage on client as an instance of centralised training. However, one major difference between centralized training and FL is the notion of client statefulness. In a centralised scenario, each example in the training set is seen multiple times, once epoch, allowing for the model to converge to a stable distribution of weights. This scenario more suitable for sparsification.
On the other hand, in a typical cross-device scenario, client's availability is low and new data points are continuously being presented to the system as new clients participate in training rounds. This means that clients are likely to participate only once. Such training behaviour inevitably leads to distributions of weights that change over time, making the application of sparsity inducing methods more difficult as a result.
4 SPARSE TRAINING FOR FEDERATED LEARNING
As a first step, we conduct preliminaries investigations and measure SWAT's performance when directly applied FL without any adaptation. This section describes the experimental protocol (Section (.1)). the obtained baseline results (Section 4.2 and sparsification effect analysis to high- light the weaknesses of this approach in Section 4.3
4.1 EXPERIMENTAL SETUP
While SWAT is used across the experiments as the standard sparsification methodology, results also depend on various FL.-specific pyper-parameters. Federated learning is simulated with the Virtual Client Engine (VCE) of the Flower toolkit (Beutel et al. (020) enabling us to scale a large number of clients within in a single machine. Datasets and hyper-parameter are detailed below.
Datasets. Experiments are conducted on two image classification tasks of different complexity both in terms of the number of samples and classes: FEMNIST (Caldas et al., 2018) and CI- FAR10 Krizhevsky et al. 2009). FEMNIST is constructed by partitioning the data of the Extended MNIST (Cohen et al. 201 7) based on the writers of the digit-character. We also include the Speech Commands dataset [Warden 2018), where the task is to classify 1-second long audio clips. Further details for these datasets can be found in the Appendix A.5
Data partitioning. We follow the latent Dirichlet allocation (LDA) partition method (Reddi al., 2021 Yurochkin et al. 2019 Hsu et al. 2019) ensuring that each client is allocated the same number of training samples. The level of heterogeneity is governed by the parameter a. As - cc, partitions become more uniform (IID), and as + O. partitions tend to be more heterogeneous. Our experimental evaluation considers a 1.0 and a 1000.
Model Architecture. Following the convention for CIFAR-IO, a ResNet-18 (He et al. 2016) archi-
tecture is instantiated the client side and aggregated on the server. We also make use ResNet- 18 for SpeechCommands, For FEMNIST, we employ the much smaller CNN first proposed in (Caldas) cet al. 2018). Further details for these architectures can found in Section A.6 in the Appendix. The models are trained with SGD, and all experiments imply one local epoch (i.e. client epoch). An exponential decay defined as = Jstart exp(; & (og((auer// Mend)) with 77start nend the starting and last learning rates respectively is applied at training time. T represents the total number of FL rounds.
Client partitioning. Following previous works, we propose to compose a pool 100 clients with 10 active clients training concurrently in given round (McMahan et al. 2017). We do this for all experiments except for FEMNIST, which comes pre- pre-partitioned into 3597 clients. For this dataset consider the setting of sampling 35 clients per round in Caldas et al. (2018).
Sparsity Ratios. This work considers accelerating the convolutions involved during forward and backward propagation following Top-K sparsity inducing mechanism at the weight level. As
4

---

Published as a conference paper at ICLR 2022
CIFAR-10, SWAT w/ sparsity=0.7
CIFAR-10, SWAT w/ s.s
OFAR-10, SWAT w/ Spersfly=
95
95
95
Or- eiphe- 1000
90
90
90
alphai1000
In alpha-
83
B5
88
Validation Accuracy
80
80
Validaaion Accuracy
80
centralized
75-
75
75-
70
Validation
70
70
65-
1--0.2 alpha-1000
65
1..0.2, aipha-00000
65
60
1--01, alpha-1
1--02, alpha-1000
60
In.0.1. alpha-1
1n-0.2 alpha-1000
55
1m-02, alpham]
55
1m-02, alpham]
contralzed
contralized
50
50
50
500
200
500
200
500 Round
Round
Round
Figure 1: Comparison of validation accuracies in percentage of both centralised learning and FL on the CI- FARIO dataset with different sparsity and non-IID ratios. While centralised training suffers from minimal degradation at very high sparsity ratios (95%). the opposite happens for FL; we observe 10% accuracy drop.
result, the expected sparse pattern would be unstructured, which can only be accelerated tensors are sufficiently sparse. While sufficient is mostly hardware-specific, for the target platforms often considered in FL (e.g. mobile CPUs and GPUs) we set a minimum sparsity ratio (sp) of 90%, above which acceleration can be achieved (Wang 2021p. We include in our study sp [0.7, 0.9, 0.95) in our initial evaluation. We expect minimal accuracy drop for both IID and non-IID at 0.7 sparsity.
4.2 BASELINES RESULTS
We begin by studying the effect of applying SWAT in both centralised learning and FL with the CIFAR10 dataset, and the results are given in Fig. [ Applying SWAT in centralised training does not impact the validation accuracy much despite the high level of sparsity level, which is equivalent to the results from the original paper (Raihan & Aamodi (2020) with a validation accuracy reaching 91.21% % with a sparsity level of 95% against 93.32% for 70%.
We found sparse FL to be particularly sensitive to the learning rate and its scheduler. In particular, exponential decay annealing is crucial to reach relatively good performance. It is also clear from the curves that higher learning rate of 0.2 reaches better accuracies in general than 0.1. As expected, however, FL offers lower levels of performance across all setups compared to centralised training.
In addition, and conversely to centralised training, plots show consistent drops in the validation accuracy with the increase of the sparsity level. It is worth noticing that the validation accuracy decreases by 4.60% and 2.78% while the sparsity level increases from 90% to 95% and 70% 90% respectively for IID settings. Then the validation accuracy drops by 8.3% and 1.84% when sparsity levels increase from 90% to 95% and 70% to 90% respectively for non-IlI settings. This highlights an important degradation of performance in non-lID settings with very high levels of sparsity.
4.3 SPARSIFICATION EFFECT ANALYSIS
As shown in Fig. high levels of sparsity with FL (e.g. 2 90%) induce an significant drop of accuracy that is more noticeable than for centralised training. We aim at understanding this phenomenon further reduce the gap between centralised and FL training by properly adapting sparsification. As first step, we propose to investigate the behaviour of the neural weights from clients to clients under SWAT and FL with a sparsity ratio equals to 90%.
Indeed, an undocumented effect of SWAT occurs at inference time and may motivate an extension of the technique to work properly with FL. During training. SWAT partitions the weights in two sets: active and non-active. The former set is used as sparsity map during any forward propagation (i.e. both at training and inference times). In fact, a part of the weights are simply dropped from the neural network. This implies that the neural network must remain sparsified when evaluating and inferring or the accuracy will drastically drops. For instance, a FL trained system on CIFAR 10 that reaches an accuracy of 82% on the validation set will drop to 10% if the inference is done without sparsification.
5

---

Published as a conference paper at ICLR 2022
Top 10%
Top 30%
0:22
0.40
0.20-
0.38
Sparaity Rablo
0.18
Sparsity Rabio
0.36
0.16
0.34
0.14
0.12
0.32
0.10
0.30
100
200
300
400
500
600
100
200
300 Round
400
500
600
Round
layer_o 0
layer_2
layer_4
layer_6 layor_7
layer_6 8
layer_10 _10
layer_12
layer_14 layer
layor_
layer_3
layer
layer 9
layer 11
layer_13
Figure Evolution of the zero weights ratio after server aggregation (i.e. number weights that are non-zero divided by the total number parameter that layer) of CNN layers ResNet-18 trained on CIFAR10 10 with FL. Each of the 100 clients either send the top- 1 10 or top-308 30% (i.e. weights with the highest norm) the server.
empirically validates that sparse training has an impact on the internal representation of a neural network making it dependent the sparsification strategy during inference.
In practice the latter behaviour is explained by the fact that, during centralised training, sparsified weights tend to be always the same i.e. some parameters are simply discarded. For FL, however, one may intuitively hypothesize that different clients will lead to different sparsification maps during the local training; preventing the creation of global federated sparsification strategy. To investigate this, we propose to analyse the variations observed on the most active weights after aggregation on the server over the communication rounds.
Let us define the top-K K weights as being the per-layer set of parameters with the highest norm. During each communication round, clients only send their top-K weights the server while the remaining ones are set to zero. After aggregation on the server side, the resulting weight matrix informs us on the level of overlapping non-zero parameters observed on the clients. Indeed, every non-zero value obtained at specific position will likely result in non-zero value at the correspond- ing position in the aggregated weight matrix. For instance, the number of non-sparse elements from the aggregated matrix is equivalent to the one of the clients (K %) it means that all clients have the exact same top-K KK weights. With that in mind, we can define a non- zero ratio that is the number of non-zero parameters after aggregation divided by the the total number of elements in this layer. Thus, the higher this ratio is, the more different are the top-K weights sent from the clients. Fig. 2 depicts this ratio for different CNN layers for non-IID CIFAR-I0 with K {10,30) 30)%.. %.
First, a significant overlap exists between clients across all CNN layers. Indeed, the non-zero ratio almost never exceeds 0.40, meaning that least 60% of the weights not comprised in the top-K weights of the clients. This advocates for the fact that the most important weights for the current task tend be the same across clients. Then, we can see that the non-zero ratio does not seem to be significantly impacted by changing K from 10% to 30% as it only slightly increases for most CNN layers. This explained by the fact that while clients may have different top-109 weights, they tend to have the same top-30% parameters: specific non-zero weight that is reported as a top-11 10 element from a single client out of the selected ones most likely to reported as non-zero as well by more of them when we increase c0p-30%. In short, top-30 30% will gather most of information about weights that are considered as being important for the task while keeping the same level of sparsity.
Second, we propose to examine the exact positions the top-10# weights for certain CNN layers across a pool of 100 selected clients better evaluate the overlap. Fig. shows the weight matrix recorded every 20 communication rounds after aggregation on the server. Observations validate our intuition that most of zero and non-zero weights remain the same during the whole training.
Based on this analysis, we hypothesis that the degradation of performance observed with high levels of sparsity for FL. is due to the dilution of important information during the aggregation process.

---

Published as a conference paper at ICLR 2022
615
0m
-606
-006
-015
-335
-015
200
200
200
0.55
035
015
0.55
845
605
606
225
606
035
223
035
Figure 3: Heatmaps of 6 CNN layers (layer 4-9) in ResNet-18 18 when trained on CIFAR with 100 clients by only keeping the top 10% of weights. The weights recorded every 20 communication rounds and flatten along the y-axis. The consistency across rounds (x-axis) indicates that, for the part, the locations of non-zero weights remains constant, larger version of this picture given the Appendix
For instance, weight that would be only sent by single client part of its top- 1 108 parameters would not be diluted with the noise of all the others clients. Conversely, this very same weight may be completely corrupted if we send the entire dense model for aggregation.
ZEROFL: LOCAL SPARSIFICATION OF UPLINK COMMUNICATION
Motivated by our previous analysis which suggests that not all weights are necessary to be trans- ferred the central server for aggregation, we propose ZeroFL: a method that applies local sparsi- fication before uplink communication. More precisely, we provide three strategies for local sparsifi- cation improve the performance of sparse training while reducing the communication cost the same time. By leveraging local sparsification, ZeroFL reduces the uplink communication footprint, hence reducing the noise aggregated on the central server observed in Section 4.3 In particular, if some updates are only sent by few clients, we force others clients to send zero in that particular positions of updates following our three strategies. After aggregation, the magnitude of these par- ticular updates will be averaged with the uploaded values instead of being completely corrupted by the entire set of clients. All three methods are summarized in Algorithm
Hop-K-Weights As shown in Sec. 4.3 only top-K K active weights are involved in the validation and inference stages, and an important part of these weights tend not to change during training. Therefore, the first local sparsification method is to sparsify the top-K weights the client-side before sending them back to the central server for aggregation. Then, and even though the positions of top-K weights largely overlap between each clients, only sending exactly number of weights corresponding to the sparsity level might be too restrictive and prevents natural variations in the weights. Hence, we introduce a parameter denoted as the mask ratio Tmask, indicating the additional amount of weights that the selected clients will choose to send to the server after the local training.
Let sp be the sparsity level of the local training. For instance, with sp 0.9, and after the local training process, each selected client sparsifies their model by only keeping the top (1 - (rask) weights w.r.t their magnitude, while setting the rest to zero. In particular, if sp 0.9 and Pmask 0.1, the selected clients will send the top-208 & to the central server for aggregation. The model produced after aggregation is not guaranteed to be sparse. If mask ratio equals to the sparsity level, the algorithm is degenerated to vanilla SWAT without local sparsification. However, and as shown in Fig 2 the resulting model is most likely to be sparse. Here, uplink communications are saved as only sp + mmmas) weights sent dense values.
Diff on Keeihtts. The idea behind this method is to send local weight-update for the top-K K weights, rather than sending the top-K weights themselves. Given sp and mmask. first identify the weights that are the largest in magnitude by selecting the top (1 - sp + Tmask). The selected clients now send only the difference d of these top (1 sp Timask) weights with respect to the

---

Published as a conference paper at ICLR 2022
Algorithm ZeroFL: Let us consider cluster of N total client with local data set and each with learning rate TIe round with T the total number of communication rounds. The client has the data ng. The number of local epoch and the number clients participating in each round is denoted K. wy represent the weights aggregated at round and de the difference of weights.
Central server does:
for & == O, ...;, -
Server randomly selects K devices. for all k in K do
Perform TrainLocally(A, wi)
Aggregation:
If
then We+1 <- Ex=o Te W1i1
If Diff' on Hop-K-Weighh then wh+1 6- wi + ER=o n
If Top-K Diff then We+1 < We + ΣR= ne 22
Trainl ocally(ks wz):
for 1,,., E
local model training via SWAT with spansity level sp.
We < Wc-1 T) F(we-1)
Determine which weights to send for aggregation:
-TTop---eeigh then return top 1 sp Tmask weights.
di+ Wg
If Diff on Top-K-Weight then return dit1 of top 1 - sp + Tmask weights. If Hop-K-Weight, Diff then return top 1 sp + Tmast of d/+1.
originally received model wy as de+1 = wg we with wg the weights obtained after local training. The remaining differences are set to zero. In this way, after the aggregation in the central server, the weights that are not the top (1 sp + Tmaak) part will remain the same as during the previous round, while only the top (1 sp + r mmmas) part of the weights will be updated.
Top-K-Weighte Diff. Conversely to Diff on Top-K-Weights. Weights, this strategy proposed first compute all the weights differences d and then only send the top (1 ssp + 7 maakk) of them to the server. With this method, only highly moving weights will considered.
All the aforementioned local sparsification methods lead to substantial reductions in uplink commu- nication costs. More precisely, total communications will be reduced by factor of (Tmask -sp) /2.
ZEROFL: EXPERIMENTAL RESULTS
We conducted extensive experiments on CIFARIO, Speech Commands (Warden 2018) and FEM- NIST (Caldas et al. 2018) datasets. The CIFARIO 10 experiments follow the same experimental proto- col as for baselines experiments. The three local sparsífication strategies are compared with various mask ratio mmask {0.0, 0.2, and vanilla SWAT without ZeroFL. Similarly results ob- tained in Section 4.2, sparse training performs better with exponential learning rate decay. Hence, all setups are investigated with this scheduler. reepots the test accuracies achieved as well as the gain in communication cost when applying ZeroFl..
First, it worth noticing that all three local sparsification methods with mask ratios higher than 0.1 perform better or similarly to vanilla SWAT. The biggest improvement for 90% sparsity is achieved with the Top-K- K-Weights method with a mask ratio of 0.2, which increases the test accuracy by 0.4%. The largest improvement for 95% sparsity is achieved with the ratio 0.2, and the increases the test accuracy by 1.5%.
method with a mask
reported the performance at communication round 200 to show that ZeroFL achieves faster convergences and higher accuracies with mask ratio higher than 0, especially for the non-IID setting. More results be found in appendix A.4 which demonstrates higher performance at round 300 when test accuracies are stabilized. With ZeroFL, the performance can be improved by 2.3% for 90% sparsity in the non-llI setting.
For SpeennCommands,
For FEMNIST we observe a similar trend when evaluating the different masking methods in ZeroFL: larger mask ratios result in better performing global models. However, sending the entire model from
8

---

Published as a conference paper at ICLR 2022
Table 1: Results with ZeroFL CIFARIO and SpeechCommands for both IID (a=1.0) and non-IlI (a==1000 1000) settings. We report the test accuracy at 700, 200 and IK communication rounds respectively for CIFARIO, Speech Commands and FEMNIST. We report the size (in MB) of the artifact to be transmitted to the server for aggregation, which has been compressed following the CSR sparse format representation. ZeroFI, improves the performance while reducing the uplink communication cost up to factor of 7.4x x compared to vanilla SWAT. For each sparsity level and dataset, we highlight in bold the best masking strategy. For clarity we do this on the non-IlI results only. More results can be found in Appendix.
Dataadt
Sp
Mask Ratio
Full Model
Top-K-W:
DiI K.W.
Tap-K-W. W. DHIT
File Size
Conams Savings
Level
ID
NIID
ITD
NID
IDD
NII
IID
NBD
62.8250.61
80.6230.22
43.7
90
0.0
N2.14a11.58
76 58
79.3421162
73.8740.50
82.6420.00
76 6266224
79.59&1.09
73.22a1.18 18
02.3220.75
76. 76.91:0.75
80.1720.48
72.71al.11 11
10.1
CIFAR-10 clients)
0.2
82.62+0.60
81.04490.28
82.67+0.26
79.74+1.35
82.71+0.37
79.1361191
74.0020.77
43.7
68 (666661..00
69.33+1.00
66.05=1.32 .3
69.21+0.09
76 15
73.65+1.54
76.72=0)46 46
78.03e0.82
76.44=1.12
73.06m3
0.2
76.96a1
15.54a1.15
78.2220.35
13.08a1.56
77.69s0078
72.57
85.9520.52
82.81a1.21
71.70s1 73.5422.50
76.4560.00
67,4622799
81.39H1.78
22.80
Speech
Commands
0.2
N6.30
86.11+1.11 84.90+1.77
23.70:2..5
85.4681..7
86.50+0.99
93.41a191
85.11.0.90
15.8120:11
86:21+0.74
83.81a1.48
84.85+0.75
18.7
27.3
(100 clienss)
13.10117772 81.1241.32
43.7
95%
0.1
0.0
84.71
68 130000000000
82.02:0.43
64.79+33013
81 01.5580..25
20.32+11.0 .08
81 $1.60011.2
67.95
83.6710.24
69.85-1.06
81.9921.33
66.96-2.44
14.4
5.9
7.4%
3.0x
0.2
84.0551.61
81.7946.33
82.4510.60
80.98.0.85
82 82.9620.88
81.79pl..4
23.0
1.9%
(3997
clients
PEMNIST
95%
0.1
0.2
0.3
83.3410.41
81.91
83.78.0.19
76.79541:90
83.01+0.27
82.100a3.39
77.36e2.007
81.71
82.54-0.65
77.02.0:95
23.0
4.4
2.9
1.3
17.7
52.
1x
client to server seems to be key to obtain good results. We hypothesise this is because FEMNIST is a much more challenging dataset (62 classes) and the architecture used is relatively simple and less sensible to sparsification a result.
Overall, performance improved with mask ratios between 0 and 0.2, indicating that there exist an optimal interval level. Indeed, mask ratio equal to the sparsity level degenerates the system to the vanilla SWAT, which obtains worse results. It also implies that there is a trade-off between communication cost and performance. By using mask ratio of 0.1, each selected client performs local sparsification with an effective sparsity level of 80%. hence sending more data that for lower mask ratios values. In Section A.I we densely evaluate the impact of mmask E [0.1, 0.9] and, we observe no clear benefit of choosing larger ratios over smaller ones (e.g. 0.1). We briefly elaborate on this in the Appendix.
ZeroFL enables us to reduce the performance degradation observed with high levels of sparsity with FL while not completely alleviating it. During communication, each weight matrix from the model is vectorised and transmitted using the Compressed Sparse Row (CSR) (Tinney & Walker 1967) format. Such representation requires exactly one integer index for each non-zero weight value in the model. Table [] shows the level of compression and reduction in communication for different level of mask ratios. Compared to the original 43MB dense model, uplink communications are reduced by factors of 7.5x, 3.0x and 1.9x for mask ratios of 0.0, 0.1 and 0.2 respectively, with sparsification ratio of 95%. Communication savings are calculated as the size ratio between original and compressed models; considering both weights and indices in the CSR file.
CONCLUSION
In this work, we consider the challenges of inducing high level of sparsity to accelerate on-device training for federated learning. We provide the first framework to leverage sparsity as a mechanism to accelerate on on-device training without the server imposing any restrictions. We study on the unique perspective that arise when introducing sparsity at training time, hence motivating us to propose in- novative state-of-the-ar off-the-shelve sparsification methods to the FL domain ZeroFL. The method achieves +1.5% accuracy while reducing 1.9x uplink communication costs compared with compet- itive baselines for CIFARIO at 95% sparsity, and +2.3% accuracy for non-III SpeechCommands at 90% sparsity. Our findings call for further investigations on the device-oriented optimisation of federated learning to motivate realistic deployments of this training methodology.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
This work was supported by the UK's Engineering and Physical Sciences Research Council (EP- SRC) with grants EP/M50659X/1 and EP/S001530/1 (the MOA project) and the European Research Council (ERC) via the REDIAL project (Grant Agreement ID: 805194). Part of this work was per- formed using HPC/AT resources from GENCI-IDRIS (Grant 2021-A01 10122911..
REFERENCES
Mohammad Mohammadi Amiri, Deniz Gunduz, Sanjeev R. Kulkamni, and H. Vincent Poor. Federated learning with quantized global model updates, 2020.
Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary. Federated learn- ing with personalization layers, 2019.
Daniel J. Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Titouan Parcollet, and Nicholas D. Lane. Flower: A friendly federated learning research framework, 2020.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint 11X1v:181..01097. 2018.
Sebastian Caldas, Jakub Konečny, H. Brendan McMahan, and Ameet Talwalkar. Expanding the reach of federated learning by reducing client resource requirements, 2019.
Gary Cheng, Karan Chadha, and John Duchi. Fine-tuning is fine in federated learning, 2021.
Gregory Cohen, Saced Afshar, Jonathan Tapson, and Andre Van Schaik, Emnist: Extending mnist to hand- written letters. In 2017 International Joint Conference on Neural Networks (IJCNN). pp. 2921-2926. IEEE, 2017.
Aiden Doherty, Dan Jackson, Nils Hammerla. Thomas Plötz, Patrick Olivier, Malcolm H Granat, Tom White, Vincent T Van Hees, Michael Trrenell, Christoper G Owen, et al. Large scale population assessment of physical activity using wrist worn accelerometers: The uk biobank study. PloS one, 12(2)=0016649, 2017.
Erich Elsen, Marat Dukhan, Trevor Gale, and Karen Simonyan. Fast sparse convnets. In Proceedings of the /EEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
Negar Goli and Tor M Aamodt. Resprop: Reuse sparsified backpropagation. Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 1548-1558, 2020.
Yiwen Guo. Anbang Yao, and Yurong Chen. Dynamic network surgery efficient dnns. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS'16, 16, pp. 1387-1395, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 978151083881
Pengehao Han, Shiqiang Wang, and Kin Leung- Adaptive gradient sparsification for efficient federated learning: An online learning approach. arXiv preprint 2xXiv:2001.07566 2020.
Song Han, Huizi Mao, and William Dally, Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding, 2015a.
Song Han, Jeff Pool, John Tran, and William J. Dally. Learning both weights and connections for efficient neural networks. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1, NIPS 15, pp. 1135 1143, Cambridge, MA, USA, 2015b. MIT Press
Andrew Hard, Chloé M Kiddon, Daniel Ramage, Francoise Beaufays, Hubert Fichner, Kanishka Rao, Rajiv Mathews, and Sean Augenstein. Federated learning for mobile keyboard prediction, 2018. URL https:
//arxiv.crg/ wtt../////abs/111........
Andrew Hard, Kurt Partridge, Cameron Nguyen, Niranjan Subrahmanya, Aishanee Shah, Pai Zhu, Igna- cio Lopez Moreno, and Rajiv Mathews. Training keyword spotting models on non-iid data with federated learning, 2020.
Kim Hazelwood, Sarah Bird, David Brooks, Soumith Chintala, Utku Diril, Dmytro Dzhulgakov, Mohamed Fawzy, Bill Jia, Yangqing Jia, Aditya Kalro, James Law, Kevin Lee, Jason Lu, Pieter Noordhuis, Misha Smelyanskiy, Liang Xiong, and Xiaodong Wang. Applied machine learning at facebook: A datacenter infrastructure perspective. In 2018 IEFF International Symposium on High Performance Computer Archi- tecture (HPCA), pp. 620-629, 2018. doi: 10. 10. 2010://AA..018.0000M
10

---

Published as a conference paper at ICLR 2022
Chaoyang He, Murali Annavaram, and Salman Avestimehr. Group knowledge transfer: Federated learning of large cnns at the edge. arXiv preprint arXiv:2007. 14513, 2020.
Kaiming He, Xiangyu Zhang, Shanqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IPFE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Yang He. Guoliang Kang. Xuanyi Dong. Yanwei Fu, and Yi Yang. Soft filter pruning accelerating deep convolutional neural networks. In Proceedings of the 27th International Joint Conference on Artificial Intel- ligence, LJCAI'18, pp.
AAAI Press, 2018. ISBN 9780999241127.
Yihui He, Xiangyu 7hang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In The IEEE International Conference on Computer Vision (ICCV), Oct 2017.
Agrin Hilmkil, Scbastian Callh, Matteo Barbieri, Leon René Sütfeld, Edvin Listo Zec, and Olof Mogren. Scaling federated learning for fine-tuning of large language models, 2021.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network, 2015.
Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks, 2021.
Changwan Hong, Aravind Sukumaran- Rajam, Bortik Bandyopadhyay, Jinsung Kim, Süreyya Emre Kurt, Is- rat Nisa, Shivani Sabhlok, Ümit V. Çatalyürek, Srinivasan Parthasarathy, and P. Sadayappan. Efficient sparse-matrix multi-vector product on gpus. In Proceedings of the 27th International Sympexitn on High-
Performance Parallel and Distributed Computing, HPDC '18, pp. 66-79. New York, NY, USA, 2018. URL
Association for Computing Machinery. ISBN 9781450357852.
doi: 10.1 00.1145/20800003228000
https: http://tcc...//////////// 10. 320334/223300..0 3208062
Changwan Hong, Aravind Sukumaran-Rann Rajam, Israt Nisa, Kunal Singh, and P. Sadayappan. Adaptive sparse tiling for sparse matrix multiplication. In Proceedings of the 24th Symposium on Principles and Practice of Purallel Programming, PPoPP 19. pp. 300-314, New York, NY, USA, 2.19. Association for Computing Machinery. ISBN 9781450362252.
doi: 00.1145/22938833229577 URL attpp:://di.ooe
1145/3293883 3295712
Samuel Horvath, Stefanos Laskaridis, Mario Almeida, Ilias Leontiadis, Stylianos Venieris, and Nicholas D Lane. Fjord: Fair and accurate federated learning under heterogeneous targets with ordered dropout. arXiv preprint arXiv:2102. 13451, 2021.
Tzu-Ming Harry Hsu, Hang Qi. and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.06333. 2019.
Jianxin Wu Jian-Hao Luo and Weiyao Lin. ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression. In International Conference on Computer Vision (ICCV), October 2017.
Yuang Jiang, Shiqiang Wang, Victor Valls, Bong Jun Ko, Wei-Han Lee, Kin K Leung, and Leandros Tassiulas. Model pruning enables efficient federated learning on edge devices. arXiv preprint arXiv:1909, 12326, 2019.
Jakuh Konečný, Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint 161.0:1610 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. arXiv preprint arXiv: /8/ 1..6622.77 2018.
Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances Neural Information Processing Systems, volume 33, pp. 2351 2363. Cur- ran Associates, Inc., 2020. URL httpps:/prroceeiings. 183f5
1288994804 Ffe.s49404433ccc77--8 -eccc87-Papee pdf
Lumin Liu, Jun Zhang, Shenghui Song, and Khaled B. Letaief. Hierarchical quantized federated learning: Convergence analysis and system design, 2021.
L. Lu, J. Xie, R. Huang. J. Zhang, W. Lin, and Y. Liang. An Efficient Hardware Accelerator for Sparse Convolu- tional Neural Networks on FPGAs. In IEFE 27th Annual International Symposium on Field- feeld-Prgganmabble Custom Computing Machines (FCCM), pp. 17-25, 2019.

---

Published as a conference paper at ICLR 2022
Brendan McMahan, Lider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication -efticcinnttt learning of deep networks from decentralized data, Artificial intelligence and statistics, pp. 1273- 1282. PMLR, 2017.
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 2498 2507. PMLR, 06- Aug 2017. http:t /ttp:::p//rcceeei ngs 1 www.pprsssvvv. 000/////00/mmmmom chanov html
Pavlo Molchanov, Arun Mallya, Stephen Tyree, luri Frosio, and Kautz. Importance Estimation for Neural Network Pruning. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Xinchi Qiu. Titouan Parcollet, Javier Fernandez- Berandez-Marquess, Pedro Porto Buarque de Gusmao, Daniel J Beutel, Taner Topal, Akhil Mathur, and Nicholas Lane. first look into the carbon footprint of federated learning. arXiv preprint arXiv:2102.07627, 2021.
Aamir Raihan and Tor M Aamodt. Sparse weight activation training. arXiv preprint arXiv:2001.0196 2020.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Ku- mar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference Learn- ing Representations, 2021.
Mengye Ren, Andrei Pokrovsky, Bin Yang, and Raquel Urtasun. Sbnet: Sparse blocks network for fast infer- ence, 2018
A. Radford S. Gray and D. P. Kingma. Block-sparse gpu kernels, 2017. URL httpa://bloo..perra com/b b1 oock sparse gpu kernel
Osama Shahid, Seyedamin Pouriyeh, Reza M. Parizi, Quan Z. Sheng, Gautam Srivastava, and Liang Zhao. Communication efficiency in federated learning: Achievements and challenges, 2021.
N. Srivastava, H. Jin, S. Smith, H. Rong, D. Albonesi, and Z. Zhang. Tensaurus: A Versatile Accelerator for Mixed Sparse- Dense Tensor Computations. In 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA), pp. 689-608972 2020.
Xu Sun, Xuancheng Ren, Shuming Ma, and Houfeng Wang- meProp: Sparsified back propagation for ac- celerated deep learning with reduced overfitting. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 3299-3308, International Convention Centre, Sydney, Australia, 2017.
W.F. Tinney and J.W. Walker. Direct solutions sparse network equations by optimally ordered triangular factorization. Proceedings of the IEEE, 55(11))1801-1809, 1967. doi: 10.1 10.1109/PRC..196 196..6011.
Thomas Verelst and Tinne Tuytelaars. Segblocks: segmentation, 2020.
Block-based dynamic resolution networks for real-time
Hongyi Wang, Scott Sievert, Zachary Charles, Shengehao Liu, Stephen Wright, and Dimitris Papailiopoulos. Atomo: Communication-eeficcenn learning via atomic sparsification. arXiv preprint arXiv: 1806.04090. 2018.
Yunhe Wang, Chang Xu, Chao and Dacheng Tao. Beyond Filters: Compact Feature Map Portable Deep Model. In Proceedings s of the 34th International Conference on Machine Learning (ICML), pp. 3703-3711, 2017.
Ziheng Wang. Sparsert: Accelerating unstructured sparsity gpus for deep learning inference. In Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques, PACT '20, pp. 31 42, New York, NY, USA. 2020, Association for Computing Machinery. ISBN 9781450380751. doi: 10.1145/3410463.344466 446544 URL
Ziheng Wang. Sparsednn: Fast sparse deep learning inference on cpus, 2021.
Pete Warden. Speech commands: A dataset for limited-vocabulary speech recognition. arXiv preprint
arXiv: 1.X3::8804.032000 2018
N. Wen, R. Guo, B. He. Yong Fan, and Ding Ma. Block-sparse cnn: towards fast and memory-effciient framework for convolutional neural networks. Applied Intelligence, 51:441-452, 2020.
12

---

Published as a conference paper at ICLR 2022
R. Yu, A. C. Chen, Lai. V. L. Morariu, X. Han, M. Gao. C. Lin, and L. S. Davis. Nisp: Pruning works using neuron importance score propagation. 2018 IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR). pp. 9194-990 994-9203, Los Alamitos, CA, USA, jun 2018. IEEE Computer Society. doi: 10. 201.C.....21.009555 URL https: http://www....poooooooooooooooo/
CVPR.2015 00958
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khaz- aeni. Bayesian nonparametric federated learning of neural networks. In International Conference on Ma- chine Learning, pp. 7252-7261. PMLR, 2019.
Orestis Zachariadis, Nitin Satpute, Juan Gómez-I.una and Joaquín Olivares. Accelerating sparse matrix-matrix multiplication with gpu tensor cores. Computers Electrical Engineering, 88: 88:106848, Dec 2020. ISSN 0045-7906. doi: cowp:l/o.ooelccnngg....m http//ceenn2220066464444444 106848. URL http::/dx.dooof org/10.. 1016// 1016/j- compeleceng 2020. 106848
Zhang, Du, Zhang, Lan, Liu, L. Li, Guo, Chen, Chen. Cambricon-X: Accelerator for Sparse Neural Networks. In 2016 49th Annual IEEE/ACM International Symposiun on Microarchitec- ture (MICRO), pp. 1-12, 2016.
Yundong Zhang, Naveen Suda, Liangzhen Lai, and Vikas Chandra. Hello edge: Keyword spotting on micro- controllers, 2018.
Zhuangdi Zhu, Junyuan Hong, and Jiayu Zhou. Data-free knowledge distillation for heterogeneous federated learning, 2021.
13

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.1 IMPACT OF Tmask IN GLOBAL PERFORMANCE
We hypothesised in Section 6 that increasing the masking ratio, Tmakk, which is used to limit the amount of non-zero weights that would be uploaded the central server after each client completes its local training, would yield better global model performance. However, as it can be observed in Figure 4 test accuracy does not monotonically increase with mmask and lower values (i.e. 0.1) that enable large savings in upload communication could perform good as with larger values (e.g. 0.6) after fine-tuning.
CIFAR-10, 100 clients, SWAT w/ sparsity=0.95
Test Accuracy
70
Validation Accuracy
60
mask_ratio=00:
50
mask ratio-0.8
mask_rate r0
0.6
mask_ratio=0011
mask_ratlo-0.2
60
mask_ratio=0.3
mask_ratio=0.4
10
rask-rrtio=0.5
50
0
100
200
300
400
500
600
700
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Round
Mask ratio
Figure 4: Larger masking ratios do not offer a clear advantage over smaller values (e.g. 0.1) despite them up- loading larger portion of the model parameters to the server after each round of local training. This experiment conducted using non-IID partitioning CIFAR-10.
A.2 CIFAR-10 WITH FEDADAM STRATEGY
Table 2 shows the performance of the proposed masking methods in ZeroFL when evaluating
CIFAR 10 on the non-lID setting using the FedAdam (Reddi et al. [222 aggregation strategy.
The results are inline with what was first observed in Table in Section 6 at large sparisty ratios (0.95) only ZeroFI. making use of
Table 2: CIFAR-10 with FedAdam for the non-IlD setting, 100 clients and using 10 clients per round.
Sparsity Level
Mask Ratio
Full Model NIID
Top-K-W. NIID
Diff. Top-K-W.
Top-K-W. Diff NIID
File Size
Comms. Savings
NIID
83.38
43.7
1
0.0
83.22
82.14
83.43
10.1
4.3x
90% %
0.1
84,01
81.58
83.60
18.7
2.3x
0.2
83.67
83.29
82.79
27.3
1.6x
80.69
43.7
1x
0.0
81.11
80.67
80.45
5.9
7.4x
95 %
0.1
81.02
80.29
80.09
14.4
3.0x
0.2
83.30
81.35
81.25
23.0
1.9x
A.3 HEATMAP VISUALIZATIONS
As mentioned in Fig. bigger version of heatmap for of the CNN layer (layer 4) is shown in Fig. [5 for better reference. Heatmap plots for SpeechCommands can be found Fig. 6 which shows the similar results.
14

---

Published as a conference paper at ICLR 2022
-013
Figure 5: Heatmap. in bigger scale, of CNN layers (layer 4) in ResNet-18 when trained CIFARIO with 100 clients by only keeping top of weights. The weights are recorded every 20 communication rounds and flatten along the y-axis. The consistency across rounds (x-axis) indicates that, for the most part, the locations of non-zero weights remains constant.
032
0.5
0.5
033
4.1
400
406
399
Figure 6: Heatmap. two CNN layers (layer 4 and 9) ResNet-18 trained on SpeechCommands with 100 clients by only keeping the top 10% of weights. The weights are recorded every 20 communication rounds and flatten along the y-axis. The consistency across rounds (x-axis) indicates that, for the most part, the locations of non-zero weights remains constant.
A.4 ADDITIONAL RESULTS FOR SPEECHCOMMANDS
Table reports the performance of ZeroFL. SpeechCommands after 300 communication rounds for both IID and non-lID settings. Combined with Table []] the results show consistent better perfor- mance for non-lID settings for mask ratio higher than O. The increase accuracy at rounds 200 in Table [ shows faster convergence of ZeroFL compared with baselines, while improvement in accuracies at rounds 300 in Table demonstrates the better performance of ZeroFL overall.
A.5 DATASETS
This work considers two image classification tasks of different complexity both terms of the number of samples and classes: CIFARIO (Krizhevsky al. 2009) and FEMNIST (Caldas et al.) 2018) with 10 classes and 62 classes respectively. The former is comprised of 60K 32 x32 RGB images for training and 10K images for test. The latter, results in over 652K images for training and over 165K for test. FEMNIST images are 28x28 and grayscale. In both scenarios we randomly extract 10% out from the training set for validation. This is done at the client level, i.e., the validation
15

---

Published as a conference paper at ICLR 2022
Table 3: Experimental results with ZeroFL SpeechCommands using 100 clients. We evaluate both IID
(a=1.00 1.0) and non-III -ID-IIID 1000) settings. The table reports highest test accuracy within 300 rounds.
Sp Level
Mask Ratio
Full Model
Top K.
DIE
Top-K-W.
Top-K-W. W. DeI NIT
File Sinee
Comms. Savings
ITD
NII
ITD
NID
ITD
NIID
ITD
$7,47a1.30
85. $5.36a1.22 1.1
43.7
1x
90%
0.1
0.
76.06+2.23
$7.6350042
74 1951.8
2..6111.446 166
76, 56.55+1 37
65.6060.31 31
85.97 $3.97a133
71 61.6022.88
87. $7.4069041
54.51+11 10
75,7742.02
R3.03a1
4.3x
2.3x
0.2
87.5250.44
56.20x2.31
87.3550 48
66.6911.00 1.0
87. 87.9750
85, 15.4611.45
1,5x
$5.1721.16
83,21a1.88
43.7
00
71.97s90770
73,85a0
71.39e1
73. 13.1l607:75
69.68881.13
84.52:1.37
K3.9120.77
N3.75et160
N4.40ts0
84.06a2.44
0.3
85.07+0
54. 44.31+1.56
84.29H0
82.86+188
85.29+0
63.39+1.50
set for each client is extracted from each client's 's training partition. This is done to ensure that the validation set representative of the underlying distribution.
In addition, we also perform analysis on the Speech Commands dataset (Warden, 2018) which con- sists of 65K 1-second long audio clips of 30 keywords, with each clip consisting of only one key- word. We train the model to classify the audio clips into one of the 10 keywords- "Yes", "No", "Up". "Down". "Left", "Right", "On", "Off", "Stopp" "Go", along with "silence" (i.e. no word spo- ken) and "unknown" word, representing the remaining 20 keywords from the dataset. The training set contains total of 56, 196 clips with 32, 550 (57%) samples from the "unknown" class and around 1800 samples (3.3%) from each of the remaining classes, hence the dataset is naturally unbalanced. Similarly to (Zhang et al. 2018), each audio clip preprocessed and 32x32 MFCC features are extracted and Ted to the CNN backbone, ResNet-16 18 as described in Section
A.6 MODELS AND HYPERPARAMETERS
For ResNet-18, all 3x3 convolutional layers implement sparse training as discussed in Sec. S.c.3.2 As it is common with other optimizations, leave the input layer unchanged (i.e. performing standard dense training). This architecture results in IM parameters.
For FEMNIST, we borrow the much smaller CNN first proposed by Caldas al. (2018). It is comprised of two 5x5 convolutional layers (each followed by 2 2 maxpool laye) and two linear layers. We sparsify both convolutional layers and the first linear layer but leave the final layer unchanged (i.e. dense). This architecture results in parameters 6.6M parameters, which the first linear layer accounting for 97% the memory footprint.
All our experiments make use of the following hyperparameters. The start and end learning rate are 0.1 and 0.01 respectively for CIFAR 10, 0.01 and 0.001 for Speech Commands, and 0.004 and 0.001 for FEMNIST.
16


Reviews:
[{"review_id": "_uipNYS6Crx", "reviewer": "Reviewer_1bwd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The authors introduce a new problem of adding sparse local training to federated learning. The problem appears well motivated (sparse training can lead to significant power savings at the edge) and challenging (directly adding sparse training to conventional aggregation methods like FedAvg leads to significant accuracy drops).\n\n2. The proposed solutions are good initial approaches backed by the empirical study and do appear to lead to some improvement in accuracy over the naive approach.\n\nWeaknesses:\n\n1. For a paper that relies entirely on empirical evidence for its claims, the empirical study appears a bit limited as it considers only a single dataset (CIFAR10) and a single model architecture (ResNet18). Without seeing results for some other image/text datasets and other model architectures (MLP/LSTM) it is difficult to completely believe the claims especially since the proposed solutions rely heavily on the claims that the positions of the top-K weights do not vary significantly across models and across rounds.\n\n2. The experimental results are also a bit limited. In particular:\n\na) It is misleading to highlight both max accuracy and max comms savings values since the two correspond to different settings and thus cannot be achieved simultaneously. I would suggest removing the bold font for the max comms savings model and just reporting the comms savings for the different mask ratios. An interesting future direction would be to think of a metric that can combine the two since it is currently unclear if the communication saving (and local computation cost reduction) is significant enough to compensate for the drop in accuracy w.r.t conventional FL (black line in Fig. 1)\n\nb) Since the authors acknowledge that accuracy is expected to first increase and then decrease on increasing mask ratio, it would be worth including results for all mask ratios in the appendix at least to see the trend clearly.\n\nc) The results with i.i.d data partitioning are not presented. Since from Fig 1 it seems like accuracy drops even for the i.i.d case, it is important to show if the proposed schemes alleviate the issue in that case as well.\n\nd) Lastly, following point 1, in my opinion all experiments should be performed with some other datasets and model architectures before the paper can be considered for acceptance.\n\n3. (Minor) There doesn't seem to be any real difference between Top-K-Weights and the Diff on Top-K-weights in that the weight updates will be exactly the same in both cases as far as I can tell. If that is so then there are essentially 2 (and not 3) new schemes being proposed. \n\n\n\n\n\n", "summary_of_the_paper": "The paper studies the problem of adding sparsity to local training in federated learning. Under the approach each node uses only the top-K weights for computations in the forward and backward pass of training (and only top-K activations for computations in the backward pass). The authors empirically show that adding sparsity in this way, while speeding up local training, significantly degrades the accuracy when directly used in federated learning. To mitigate this issue the authors propose to combine sparse training with sparse aggregation since their empirical study suggests that the accuracy drop may be due to dilution of weights that are active in only a few nodes. Experiments on CIFAR10 with non-IID splits using ResNet-18 as the model show some gain in accuracy along with a drop in communication cost when using the proposed schemes.", "summary_of_the_review": "The authors introduce an interesting and important problem but given that the paper relies purely on empirical evidence for its claims the current evaluation is quite limited and not enough for acceptance. I find the claims fairly intuitive, however, and so would be willing to increase my score if more empirical evidence (in line with my comments above) is presented to back them.\n\nComments after rebutal : I appreciate the added experiments which certainly demonstrate that the proposed schemes are able to improve performance across different datasets. I have increased my score to reflect the same. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_FlxM5ZbEll", "reviewer": "Reviewer_Fw5w", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This submission is reasonably well-written and easy to follow. The idea is simple to implement and seems to work, at least in this specific setting that the authors considered. This constitutes a nice advantage to ZeroFL. Nevertheless, I believe this submission needs quite a bit of work before I can recommend for acceptance:\n\n- There are comparisons with other relevant baselines missing; e.g., federated dropout (which can be done on the weight level as well) is missing.\n- The overall contribution seems incremental compared to the prior work of SWAT. Furthermore, the authors discuss how SWAT also employs activation sparsification but they seem to not use it at all in their experiments. \n- The overall state of the experimental evaluation is a bit weak; there is only one dataset considered where the number of clients is relatively small (100). What happens on datasets with more users for example on EMNIST / FEMNIST? Furthermore, it seems that the authors show results from single seeds and therefore it is hard to see what is the stability of their results.\n- The authors don’t talk about the extra cost of transmitting the indices of the non-zero values in the main text (although they do mention the CSC format in the table caption), which can be an important additional communication cost in the case of unstructured pruning. Furthermore, at section 5 at the end, the authors mention $0.5(r_{mask }- sp)$ savings and it is not clear to me how is that derived and whether it does take into account sending the indices of the non-zero values as well.\n\nAs for other general feedback:\n- At the first bullet before the related work, the authors argue that with the way their sparsity is realised  the privacy is better preserved. Could they perhaps elaborate more? To me it seems that this can actually be worse for privacy as each user can have its own sparsity pattern and thus reveal additional information compared to a server imposed sparsity pattern which is the same for all users.\n- This work seems to be geared towards upload compression, although to me it seems that download compression is also feasible. Have the authors experimented with such an idea? \n- The algorithm needs some improvements, e.g., add an if statement for the different choices, as it can be confusing as it is now. Furthermore, the details Figure 3 are quite hard to see, so I would encourage the authors to use a different colour palette and intensity for the lines. \n- At the caption of table 1 the authors mention a 7.4x improvement over vanilla SWAT but the 7.4x seems to be on the dense model, i.e., when SWAT is not employed. Could the authors elaborate on what they compare against?\n- Sometimes the authors refer to top-K and sometimes to top-K%. It would be better if they pick one for consistency. \n", "summary_of_the_paper": "This work proposes ZeroFL; a method that allows for sparse neural network training at the edge along with reduced upload communication, both of which being important aspects in federated learning.  ZeroFL essentially follows a prior work on sparse neural network training, namely SWAT, and adapts it appropriately for the federated setting. The SWAT method works by setting a target weight sparsity percentage (denoted by $sp$) which is enforced in both the forward and backward pass by a top-k operation on the weights. This allows for using sparse convolutions and thus offering training time speed-ups. The authors note that it is important to use the same set of sparse weights for inference as well, in order to not affect performance. \n\nZeroFL then applies this idea in the federated setting by letting each client perform SWAT type of training with a target sparsity of $sp$. Instead of the clients then communicating to the server the exact set of sparse weights obtained at the end of their local training procedure, ZeroFL proposes to add an extra “slack” $r_{mask}$ and communicate $1 - sp + r_{mask}$ percentage of weights (instead of $1 - sp$). The authors motivate this change via the results of an ablation study which showed significantly lower performance when directly applying SWAT to the federated setting. They argue that with the extra $r_{mask}$ weights, a “cleaner” training signal from the clients can be given as these weights are not “corrupted” by the weights of the other clients when averaging at the server. The authors further propose three separate weights of updating the server model, i.e., 1) using the client top-k weights, 2) using the difference between the server and client top-k weights and 3) using the top-k differences between the server and client weights.  \n\nThe authors experimentally validate the ZeroFL method on cifar 10 using 100 clients and both iid and non-iid splits.\n", "summary_of_the_review": "Overall, while ZeroFL is simple, it does seem to be a straightforward extension of SWAT to the federated setting with a very minor modification. The experimental evaluation is rather weak (experiments on a single dataset) and there is an absence of other critical baselines (such as federated dropout). These are the primary issues that lead me to recommending rejection. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XTvo-5axFW", "reviewer": "Reviewer_sb7x", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper has following strengths:\n1.\tIndeed, for more realistic deployment and to move federated learning towards practical systems, it is important to accelerate the on-device training (and not just the inference which is mainly the current practice). So, the problem the authors have considered is important.\n2.\tThe proposed strategies clearly indicate the improvements over existing centralized sparse training technique like SWAT.\n3.\tSome of the insights shared (like the non-sparse weights staying the same throughout FL) were interesting.\n\nThe paper has following weaknesses:\n1.\tThe main weakness of this paper is the experiments section. The results are presented only on CIFAR-10 dataset and do not consider many other datasets from Federated learning benchmarks (e.g., LEAF https://leaf.cmu.edu/). The authors should see relevant works like (FedProx https://arxiv.org/abs/1812.06127) and (FedMAX, https://arxiv.org/abs/2004.03657 (ECML 2020)) for details on different datasets and model types. If the experimental evaluation was comprehensive enough, this would be a very good paper (given the interesting and important problem it addresses).\n2.\tOne other thing (although this is not the main focus of this paper), the authors should provide comparisons between strategies that result in fast convergence (without sparsity) vs. sparse methods? For example, do non-sparse, fast convergence methods (like FedProx, FedMAX, and others) result in small enough number of epochs compared to sparse methods? Can the fast convergence methods be augmented with sparisity ideas successfully without resulting in significant loss of accuracy? Some discussion and possibly performance numbers are needed here.\n", "summary_of_the_paper": "The paper investigates sparse training to accelerate on-device federated learning. It begins by taking an off-the-shelf sparse training method (SWAT) and analyzes its limitations. Then, the method proposes three strategies to improve upon SWAT. Experiments are conducted on CIFAR-10 dataset and show some improvements compared to SWAT.", "summary_of_the_review": "Even though the reviewer is quite happy about the problem addressed in this paper, it lacks a solid experimental section. I would be willing to increase the score if the authors can present a more comprehensive results section.\n\nPost rebuttal:\nI have read the author response and other reviews. Thanks to the authors for a detailed rebuttal and new experiments. It addressed my concerns and so I have increased the rating from 5 to 6. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of on-device training for federated learning. This is an important problem since, in real-world settings, the clients have limited compute and memory, and local training needs to be efficient. The paper shows that the standard sparsity based speed-up techniques that consider top-K weights/activations during forward and/or backward pass do not work well in the federated setting and proposes several solutions to mitigate this issue. The proposed solutions are demonstrated to work well on several datasets.

In their initial assessment, given that this is largely an empirical insights driven paper, the reviewers mainly expressed concerns about the experimental evaluation (e.g., only one dataset CIFAR10 and one architecture ResNet18) and lack of more baselines (e.g., Federated Dropout). The authors responded in detail to the reviews and also conducted additional experiments and the reviewers and authors engaged in discussion. As the discussion converged, the reviewers agreed that the revised manuscript addresses their key concerns and their assessment, on an average, are now learning largely towards a borderline accept.

I also read the reviews, the discussion, and read the paper. I think the paper is a good initial attempt at providing a general approach to enable on-device federated learning when the clients are lightweight devices (e.g. edge devices). Even though the study is somewhat preliminary, the current manuscript, after the revision during the discussion phase, is significantly improved version of the original submission and does address the key concerns from the reviewers. Overall, I would rate the paper for a borderline acceptance.
Decision: Accept (Poster)