Lottery Aware Sparsity Hunting: Enabling Federated Learning on Resource-Limited Edge
Authors: Sara Babakniya
Souvik Kundu
Saurav Prakash
Yue Niu
Salman Avestimehr
Venue: Submitted to ICLR 2023 (2023)
Keywords: Sparse federated learning (FL)
communication efficient FL
computation efficient FL

Abstract: Limited computation and communication capabilities of clients pose significant challenges in federated learning (FL) over resource-limited edge nodes. A potential solution to this problem is to deploy off-the-shelf sparse learning algorithms that train a binary sparse mask on each client with the expectation of training a consistent sparse server mask yielding sparse weight tensors. However, as we investigate in this paper, such naive deployments result in a significant drop in accuracy compared to FL with dense models, especially for clients with limited resource budgets. In particular, our investigations reveal a serious lack of consensus among the trained sparsity masks on clients, which prevents convergence for the server mask and potentially leads to a substantial drop in model performance. Based on such key observations, we propose federated lottery aware sparsity hunting (FLASH), a unified sparse learning framework to make the server win a lottery in terms of yielding a sparse sub-model, able to maintain classification performance under highly resource-limited client settings. Moreover, to support FL on different devices requiring different parameter density, we leverage our findings to present hetero-FLASH, where clients can have different target sparsity budgets based on their device resource limits. Experimental evaluations with multiple models on various datasets (both IID and non-IID) show superiority of our models in closing the gap with unpruned baseline while yielding up to ∼10.1% improved accuracy with ∼10.26x fewer communication costs, compared to existing alternatives, at similar hyperparameter settings.

Under review as a conference paper at ICLR 2023
LOTTERY AWARE SPARSITY HUNTING: ENABLING FED- ERATED LEARNING ON RESOURCE-LIMITED EDGE
Anonymous authors Paper under double-blind review
ABSTRACT
Limited computation and communication capabilities of clients pose significant challenges in federated learning (FL) over sssorree-lmmited edge nodes. A potential solution to this problem is to deploy off-the-shelf sparse learning algorithms that train binary sparse mask each client with the expectation of training consistent sparse server mask yielding sparse weight tensors. However, as we investigate this paper, such naive deployments result in significant drop in accuracy compared to FL with dense models, especially for clients with limited resource budgets. particular, our investigations reveal a serious lack of consensus among the trained sparsity masks on clients, which prevents convergence for the server mask and potentially leads to substantial drop in model performance. Based on such key observations, we propose federated lottery aware sparsity hunting (FLASH), a unified sparse learning framework to make the server win a lottery in terms of yielding sparse sub-model, able to maintain classification performance under highly resource-limites client settings. Moreover, to support FL on different devices requiring different parameter density, we leverage our findings to present hetero- FLASH, where clients can have different target sparsity budgets based on their device resource limits. Experimental evaluations with multiple models on various datasets (both IID and non-IlD) show superiority of our models in closing the gap with unpruned baseline while yielding up to 100. improved accuracy with ~10.26x fewer communication costs, compared to existing alternatives, at similar hyperparameter settings. Code is released as Supplement.ar.
INTRODUCTION
Federated learning (FL) McMahan al. (2017) is popular form of distributed training, which has gained significant traction due to its ability to allow multiple clients to learn shared global model without the requirement transfer their private data. However, clients' heterogeneity and resource limitations pose significant challenges for FL deployment over edge nodes, including mobile phones and IoT devices. To resolve these issues, various methods have been proposed
the past few
years including efficient learning for heterogeneous collaborative training Lin et al. (2020): Zhu et al. (202T), distillation He et al. (2020), federated dropout techniques Horvath (orvvthh et al. [202]; Caldas et al. (2018b), efficient aggregation for Taster convergence and reduced communication Reddi al. (2020); Li et al. (2020b). However, these methods do not necessarily address the growing concerns of highly computation and communication limited edge.
Meanwhile, reducing the memory, compute, and latency costs for deep neural networks (DNNs) in centralized training for their efficient edge deployment has also become active of research. In particular, recently proposed sparse learning (SL) strategies Evci et al. (2020); Kundu et al. al.] (20216); Raihan Mocanu et al. (2018); Dettmers & Zettlemoyer Raihann & Aamodt (202)) effectively train
weights and associated binary sparse masks allow only a fraction of model parameters to be updated during training, potentially enabling the lucrative reduction in both the training time and compute cost Qiu al. (202T); Raihan & Aamodt (2020), while creating model to meet a target parameter density denoted as d, and is able to yield accuracy close to that of the unpruned baseline.
However, the challenges and opportunities of sparse learning in FL is yet to be fully veiled. Only very recently, few works Bibikar et al. (202T); Huang et al.] (2022) have tried to leverage sparse learning in FL primarily to show their efficacy in non-lID set- tings. Nevertheless, these works primarily used sparsity for non-aggressive model compression,

---

Under review as a conference paper at ICLR 2023
limiting the actual benefits of sparse learn- ing, and required multiple local epochs, that may further increase the training time for stragglers making the overall FL pro-
Redletl1 on CIrA--10 te
Repler18 CIPAR-10
B7.3
15.0
cess inefficient Zhang et al. (2021). More- over, the server-side pruning used in these methods may not necessarily adhere to the layers' pruning sensitivity that often plays a crucial role in sparse model perfor- mance Kundu et al. (2021b); ZZhan et al. (0018) Another recent work, ZeroFl. Qiu et al. ( has explored deploying sparse learning FL settings. However, Qiu et al. (2021) could not leverage any advantage of model sparsity in the clients'
donuiresh
Gas25r057 Jet.3)
P5.0-
Zen't 6.31
12.3
Zeriit
10 17 In
16
25
70.0
0.0
0.7
6.
0.0
(a] Communccaion Cout (G
(0)
Daraity (c)
Figure 1: Comparison of (a) accuracy at different com-
munication budget with, ZeroFL Qiu et al. (202T) and FedAvg. (w/ d = 1.0) (b) Accuracy vs. parameter den- sity of each client. Proposed approaches can significantly outperform the existing alternative Qiu et al. (202T) at ultra-low target parameter density (d).
communication cost and had to keep significantly more parameters active compared to a target d to yield good accuracy. Moreover, as shown in Fig. [b)) for d = 0.05, ZeroFL still suffers from substantial accuracy drop of 144 compared to the baseline.
Our Contributions. Our contribution is fourfold. In view of the above limitations, we first identify crucial differences between centralized and the corresponding FL model, in learning the sparse masks for each layer. In particular, we observe that in FI., the server model fails to yield convergent sparse masks, primarily due to the lack of consensus among clients' later layers' masks. In contrast, the centralized model show significantly higher convergence trend in learning sparse masks for all layers. We then experimentally demonstrate the utility of pruning sensitivity and mask convergence in achieving good accuracy setting the platform to close the performance gap in sparse FI..
We then leverage our findings and present federated lottery aware sparsity hunting (FLASH), a sparse FL methodology addressing the aforementioned limitations in unified manner. At the core, FLASH leverages a two-stage FL., a robust and low-cost layer sensitivity evaluation stage and a FL training stage. In particular, the disentangling of the layer sensitivity evaluation from sparse weight training allows us to either choose to train a sparse mask or freeze a sensitivity driven pre-defined mask. This can further translate to a proportional communication saving.
To deal with the heterogeneity in clients' compute-bure budget, we further extend our methodologies to FLASH, where individual clients can support different density based on their resources. Here, to deal with the unique problem of the server selecting different sparse models for clients, we present server-side gradual mask sub-sampling, that identifies sparse masks via a form of layer sensitivity re-calibration, starting for models with highest to that with lowest density support.
We conduct experiments on MNIST, FEMNIST, and CIFAR-10 10 with different models for both IID and non-IID client data partitioning. Experimental results show that, compared to the existing alternative Qiu al. (2021), at iso-hyperparameter settings, FLASH can yield up to 8.99% and ~10.1% 1%, on IID and non-lID data settings, respectively, with reduced communication of up to 100.xx
RELATED WORKS
Model Pruning. Over the past few years, a plethora of research has been done to perform efficient
model compression via pruning, particularly in centralized training Ma et al. (2021); Frankle & Carbin (2018) Liu et al. (202T): You et al. (2019): He et al. (2018). Pruning essentially identifies
and removes the unimportant parameters to yield compute-ellicient inference models. More recently. sparse learning Evei al. (020)); Kundu al. (222Ib;; Dettmers & Zettlemoyer (2019); Raihann & AAamodt 20000; Kundu et al. 2010; a popular form of model pruning. has gained significant traction it can yield FLOPs advantage even during training. In particular, it ensures only d% of the model parameters remain non-zero during the training for a target parameter density d (d < 1.0 and sparsity is 100- d%), potentially enabling training compute and comm. cost if deployed for FL.
Dynamic network rewiring (DNR). We leverage DNR Kundu al. (2021b). to sparsely learn the sparsity mask of each client. In DNR, a model starts with randomly initiated mask following the
We measure layer importance via the proxy of sensitivity. A layer with higher sensitivity demands higher % of non-zero weights compared less sensitive layer.
2

---

Under review as a conference paper at ICLR 2023
target parameter density d. After an epoch, the client evenly prunes the lowest 9.% weights from each layer based on absolute magnitude, where p, is prune rate. Note, this p, % pruning happens on top of the sparse model with density d, allowing pr % weights to be regrown. DNR then ranks each layer based on the normalized contribution of the summed non-zero weight magnitudes. Finally, the client regrows total p, % weights in a non-uniform way, allowing more regrowth to the layers having higher rank. This process iteratively repeats over epochs to finally learn the mask.
Federated learning for resource and communication limited edge. To address device heterogeneity, existing works have explored the idea of heterogeneous training Horvath al. (202 1); Diao et al.
(2020): Yao et al. (202T) allowing different clients to train on different fractions full-model based on their compute-budget On parallel track, various optimizations are proposed in FL training
framework accelerate convergence. thus requiring fewer communication rounds Han al. (2020):
Gorbunov et al. (2021): ; Zhang et al. ): et al. (2019); Reddi et al. (2020); Islamov et al.
202
Albasyoni al. 20200.
To address the issue of client resource limitations, a few research have leveraged pruning in FL Li et al. (2020a): Jiang et al. 2022); Li et al. (202T). In particular, LotteryFL. [i et al. (2020a) trained each client to have their personalized mask with which they are able to perform well only on their own data. Moreover, the clients often need to send full model costing bandwidth. PruneFL, Jiang et al.
(2022) also asks for significant communication costs as it demands participating clients to send all the gradient values to the server while updating the masks.
Only few contemporary works Huang et al. (2022): Bibikar ct al. (2021) ): Qiu et al. (2021) tried to leverage the benefits of sparse learning in federated settings, In particular, Huang et al. (2022) relied on a randomly initialized sparse mask, and recommended keeping it frozen throughout the training, yet failed to provide any supporting intuition. FedDST Bibikar et a (202T), on the other hand, leveraged the idea of [xcc et al. (2020) to perform sparse learning of the clients, relied on a large number of local epochs avoid gradient noise, and focused primarily on only highly non-III data without targeting ultra-low density d. More importantly, neither of these works investigated the key differences between centralized and FL sparse learning. With similar philosophy as ours, ZeroFL Qiu et al. (202T) first identified a key aspect of sparse learning in FL in terms of all clients' masks to be within 30% of the total model weights to yield good accuracy at high compression. However, ZeroFL suffered significantly in exploiting a proportional advantage in communication saving as even for low parameter density d, all clients had to download the dense model and send back a 3x denser model. Furthermore, these algorithms sacrifice significant accuracy at ultra-low d.
3 REVISITING SPARSE LEARNING: WHY DOES IT MISS THE MARK IN FL?
Table I: FL training settings considered in this work.
Datzset
Model
#4 Params]
Data- partisning
RoundakKlientt Roants/RoundOpimmee
Aggregation type
Local spach (E)
Batch
(T) (Cx)
(cr.
MNNIST
LDD.
400
100
10,
CIFAR-10
RoNNeT
11:2M
600
SGD
FedAAas
FEMNIST Some to Caldis al 2018a
6.6M
RRddii en al.
2000
1000
3400
34,34
McMahun et al
2017
16
Note, centralized training has shown significant benefits with sparse learning in FLOPS reduction during forward operations Evci et al. (2020), and potential training speed-up of up to 3.3x QQu et al. (2021 while maintaining close to the baseline accuracy,
at d < 0.1. We now use sparse learning, namely Kundu et al. (202 in FL settings (refer to Table I for details) on CIFAR- 10, where each client separately performs Kundu et al. (202Th) to train a sparse server-side ResNet1 8 and meet a fixed parameter density d, starting from a random sparse mask. After sending the updates to server, it aggregates them using FedAvg. We term this as naive sparse training (NST). Note, due to lack of knowledge about the pruning sensitivity for each layer, the server fails sub-sample from the aggregated weights to meet target non-zero parameter density d. Thus, the down-link communication cost is higher as generally the aggregated non-zero parameter density is > d.
Observation 1. At high compression d S 0.1, the collaboratieely learned FL model significantly sacrifices performance, while the centralized sparse learning yields close to baseline performance.
As shown in Fig 2 a), naive deployment of sparse learning significantly sacrifices accuracy in FL. In particular, for d 0.1, , the trained server-side model suffers an accuracy drop of 3.67%. At even lower d 0.05, this drop significantly increases to 1 03%, hinting at serious limitations of sparse
3

---

Under review as a conference paper at ICLR 2023
:00
Most4:188
CIA8-10
100
Restlet1 CPA0-10
Reslecto on CIFA 15 to d-00000 Fode 200f
25-
22
15-
Controlleed 10+0:3 31
Contralied 10+0.05
Festraten -1 1-0.1
Fecoretotion (44.05
100 200
250 140
10
150
(6)
[el
Epech
Comrs
Round
Figure 2: (a-b) Accuracy vs. round plot on deployment of off-the-shelf sparse learning in FL for different d, (c-d) visualization of the Model's SM in terms of Jaccard distance while training with sparse learning for (c) centralized and (d) FL, respectively.
learning in FL. However, an off-the-shel centralized sparse learning can yield model having close to the baseline accuracy, even at d 0.05.
Observation 2. As the training progresses, the sparse masks in centralized training tend to agree across epochs, showing convergence, while the server mask in FL does lack agreement across rounds.
Definition 1. Sparse mask mismatch. For model at round I, we define the sparse mask mismatch (SM) am as the Jaccard distance that is measured as follows.
sm' = =1 Ei- (E
where Mi represents the sparse mask tensor for layer at the end of round I. Interestingly, as depicted in Fig. aaa, the SM for centralized learning tends to zero the training progresses. In contrast, with the same model, dataset and values, in FL, the SM remains > 0.4 indicating a substantial distinction in the sparse mask learning between centralized and federated learning.
Observation At low target density, in federated sparse learning, throughout the training rounds, the disagreement on the later layer's 's masks remains more severe than the earlier ones.
As the training progresses, in centralized learning, mask for each layer shows significant convergence trend as measured by SM for the layer (Fig. Baa).. However, Fig. ((b shows in FL, the later layers' masks differ significantly and continue to disagree over rounds with SM value as high as ~0.8. This may be attributed to many possible mask choices due to the later layers' significantly fewer non-zero param- eter allocation, compared to the initial layers, driven by their respective pruning sensitivities. For exam- ple, layer 1 requires 90% parameters to be present, compared to only 5% for layer 14, with the later costing an SM of ~0.73.
Table 2:
Performance based on the different levels of mask disagreement in centralized.
Training
Use sens- iivity
Masks change
Layer
Test
type
SM
detined mask frocen Pre-detmme mask Trozen
89.
$1.86
9.ye
0.8
88.
who mask frozen
Jyer 84..62"
F-6
0.S
To further investigate the impact of higher SM and layer sensitivity on a model's accuracy, we performed five different training in centralized as described in Table [ In particular, for the training in 1ow1 we randomly generate sparse masks with uniform density for all the layers. For all other training, we first randomly create each layer's 's mask by following its pruning sensitivity and then decide to keep the layer mask frozen for some or all the layers. For training described in rows 3-5, we allow fraction of the mentioned layers' masks to differ between consecutive epochs such that they meet the target SM value, creating the situation of non-convergent masks. As Table Table ellearly shows that large SM for the layers can degrade the accuracy by up to 9.34%, we can safely conclude that disagreement of masks across epochs can significantly affect the model's 's final performance. Moreover, the model trained via sparse learning with sensitivity-driver pre-defined masks yields better performance than the one trained with uniform density sparse mask.
FLASH: METHODOLOGY
To win lottery of having sparse network yielding high accuracy at reduced parameters, we identify two key characteristics of sparse learning, namely, the pruning sensitivity and mask learnability towards convergence. To explicitly adhere to these two important aspects, in FLASH, we present
2 For a sparse model it is evaluated as the ratio 1 of nen-zero Layer parancters
Ding et al. 2019). We use
# layer parametors
another pre-trained model of the same architecture and target d for this evaluation.
4

---

Under review as a conference paper at ICLR 2023
Sony
Figure 3: Layer-wise sparse mask mismatch (SM) vs. training epochs (rounds) plot for (a) centralized and (b) FL, respectively. In FL, the layer layers continue to have higher SM contrary to centralized, where every layer tend to reduce the SM as the training matures.
two-stage sparse FL method, stage 1: targeting sensitivity analysis to identify good initial sparse mask for each layer, stage 2: targeting training to learn masks and weights. In particular, to evaluate layer sensitivity in stage 1, the server randomly selects a small fraction of clients ([Cx). each locally sparse learning Kundu et al. (2021b) for few warm-up epochs (Ea) (I4-9 in Algo. D. Upon collection of layer-wise sensitivity from the clients, for each layer I, the server estimates average density d' as
Σ di where dt is the density at layer 1 in 8th client. As these averaged layer-wise cd
density values may not necessarily yield to the target density d, for model with K parameters follow the following density re re-calibration
de === =d'.ry .ry, where ry L 2i=1 &.
d X K
k' is dense model's parameter size for layer 1. For each layer I of the model, the server then creates binary sparse mask tensor that is randomly initialized, with a fraction of Is x d', (L10). In stage 2, the server begins the training rounds starting with sparse model initialization following the sparse mask computed in stage (I.1). Particularly, at each round, the clients perform sparse learning for E epochs (I,23-29) with the choice to either train the mask or keep training on the weights with the mask frozen (L26). The later allows the clients intermittently share masks saving up-link cost.
However, in FL settings, the masks often show poor convergence (section 3 Obs. 2). To address this. in stage 2, we present two sparse FL methods depending the mask learnability being disabled or enabled (L13). The disabled scenario (fifrree = 1) essentially translates to sparse learning with pre-defined layer masks at initialization, allowing to only learn the weights and forcing all the clients to use the same initialized masks. This guarantees no mask divergence issue (sn' = for all t). Moreover, as FLASH disentangles the sensitivity evaluation stage from the training, the pre-defined mask in this scenario benefits from the notion of layer sensitivity. We thus aptly name pre-defined sparse training (SPDST). Interestingly, earlier research
this scenario sensifivity-drivee Bibikar al. (2021) hinted at poor model performance with pre-defined masks, contrasting ours where we see significantly improved model performance, implying the importance of stage 1 (as will be elaborated in section 5).
In the enabled mask learning scenario (merrez = 0), model masks and weights are jointly learned during clients' local learning, thus termed as joint mask weight sparse training (JMWST), However, as highlighted earlier, clients' naive sparse mask selection at the beginning of each round costs considerable accuracy drop (section Bbbs. 1). JMWST allows the server to select a sparse model for the clients at round + 1. For clients' target density d, the aggregated server model (I20) at the end of round 6, generally has density ds > d. To enable efficient sampling of sparse model, we leverage the density re-calibration strategy (Eq, 2 by taking the 4 round's clients' sensitivity into consideration. We then perform magnitude pruning to retain the top-d" fraction of parameters for 7 layer at the server and send the pruned model to clients at round (L21). Intuitively, such sampling of non-zero weights by the server reduces chances of wasted updates, and allows the layer masks to converge faster due to alignment with the layers' pruning sensitivity. The clients then perform local sparse learning, yielding another set of sparse models and on. Note, the aggregation and sampling is simpler in SPDST, as the server model always remains at density d. In terms of yielding convergent masks, we indeed observed a lower SM for JMWST by 85% compared to that in NST, evaluated after 300 rounds on CIFAR- 10. Algorithm| [ details the FLASH training methods. is noteworthy that, the clients are only allowed to update mask after an interval of rints rounds, which for JMWST is set to by default, allowing the server to evaluate masks the end of every round.
Extension to support heterogeneous parameter density. To support different density budgets for different clients, now present hetero-FLASSH Let us assume total of N support densities
which is same as sensitivity for layer.
5

---

Under review as a conference paper at ICLR 2023
Algorithm 1: FLASH Training.
Data: Training rounds T. local opochs E, client set [Cy clients per rounds cr. target density d, sensitivity warm-up opochs Edt
density warm up count ca. initial value freeze masks mn frous O, training algorithm and Aggregation type Age.
Mini 4- -rraa=eandoommaa((
@inu <- instKaaskedWeiihhnMM
seEve=Ezecute:
N "Calculate the layer-wise semsitivity in stage
Randomiy sample elients [Ca] C [Cw]
for each client c [Ca] in parallel de
@. <- clientExeeut irss Eg: 0) m__reeee=
S. + computessenssiiiiityy..
9 end
10 # Initialize sensitivity-driven mask
11 MM +- initMask((Sel, d)
12 @ t- initKaskedwwiighh(MMM
13
+- freezeMask to and o for SPDST, and JMWST, respectively
# Stage
15 for each round / + to do
16
Randunly sample clients [C.] [Cxl
17
for each client c E [C-) in parallel do
18
6 t client.xecutss($
E, myrans)
19
end
29
Ø = Agr)
21
@¹ subsampleserverrtooe (9]] mirce))
22
end
23
Bentt
24
9_0 +- @
25
for local epock Eo
26
o -usppasseeeecnnnn0@0.... (rees)
27
freces + check(pdateMaskk)
28
end
return 6,5
doet= bedt=(11.... dars), where d; < d,41- Now, for hetero-SPDST, we perform sensitivity warm-up, to create the masks for the clients' with the highest density dy. For any other density di, we sample a sparse mask from that with density d;+1. Note, while creating the mask from d:+1 to d; we follow the layer-wise density re-calibration approach as mentioned earlier. For JMWSS, at the beginning of each round, the server performs magnitude pruning to yield N sub models meeting N different density levels, contrasting to the creation of one model in JMWST. Participating clients of different densities use the corresponding sub models to start their local sparse training. In hetero-FLASII server performs aggregation by following form of weighted fed averaging (WFA). In particular, with similar inspiration as Diao et al. (202)). to give equal importance to each parameter update in such heterogeneous settings, WFA averages the values by their number of non-zero occurrences among the participating clients. We have provided the algorithm for hetero-FLASH in the Appendix.
EXPERIMENTS
Datasets and Models. We evaluated the performance of FLASH on MNISTLeCun & Cortes 2010
Federated EMNIST (FEMNIST) Caldas et al. (2018a), and CIFAR-10 Krizhevsky et al. (2009
datasets with the CNN models described in McMahan et al. (017). Caldas et al. (2018a). and ResNet1 8, respectively. Further model details are provided in the Appendix. For data partitioning of MNIST and CIFAR-10, 10, we use Latent Dirichlet Allocation (LDAA Reddi et al. (0200) with three different a (a 1000 for IID and a = 1 and 0.1 for non-IID). For FEMNIST. we employ the same setting as in Han al. (2020), which partitions the data based on the writer into 3400 clients, making it inherently non-Ill).
Training Hyperparameters We use Clients' starting learning rate (Mmmi) as 0.1 that is exponentially decayed to 0.001 (Nena) at the end of training. Specifically, learning rate for participants at round t is T/. TTimii (xxiieexp(( (eppepxppxxeep log( Bimmt) ))). In all the sparse learning experiments, prune rate is set to
0 Summary of the rest of the training hyperparameters can be found in | Furthermore, all the experiments were performed with three different seeds. We report the final results as the averaged accuracy with corresponding std deviation in the tables.
*rruee rate controls the fraction of non-zero weights participating in the redistribution during sparse learning.

---

Under review as a conference paper at ICLR 2023
Table 3: Results with FLASH (SPDST, and JMWST) and its comparison with NST and PDST.
Data Didrilation Deniity
Baweline
POST Acc
SPIST Aec
JMWST
JMWST
170
09:70
0100
to 1000)
0.1
59.57
0.
08 97.40
12.45-1
USOW 0.23
0.05
d:
0.21
MNISST
1.00
0.1
96,82 0..55
07.06
0.33
97.72 0.32
98
0,00
0.77
57.3
0.31
97
0.07
1.0
98.45 = 0.17
200- H11 (o 0.13
0.1
96.11 22 0.222
14.44 4: 1:003
177 22 0.43
19.53 1: 0.10
1S.7 0.14
0.05
91.06 8: 1.74
91.00 8: 1.1
06.7 L: 0.87
95,83
a 0.54
95.91 = 0.64
88.00 0.00
I1D
10000)
0.1
56,72
11.00
888 0..2
57.82 0.35
87.86 0.13 87 = 0.00
0.05
77.65 0.555
$4.58 d: 0.12
86,00 0.314
86,87 0.08
170
811 1.15
CIFAR-10 10
502- IID (rx 1.00
0.1
68.46 0.10
55.07 0.24
86.42 0.40
86. 45 1:
86.36 a: 0.15
0.05
0.77
53.833 4:: 0.11
85.64 0.006
55.94 1: 0.27
65.0 =: 0.24
(a 0.1)
0.1
71.18 221
74.82 0.72
70.74
1.07
T5.47 1.15
2.51
1.0
85.68 0.00
FEMNIST
Z00 IID
0,1
76.32 0.42
76,01
1.20
82.70 d: 0.25
53,12 0.21
53.4 0.20 82 48 0.18
0.06
01.9
03.65
0.99
61.18
62.01
+ 0.53
Table 4: Comparison of ZeroFL on various performance metrics with existing alternative sparse
federated learning schemes. The italicized values are taken from the original manuscript.
Dutaset
Data Distribution
Method
Demsity
Acci
Down-link Savings
Up-link Savings
ZenoFi Qiaeet
2021
0.1
88.71 = 0.37
1x
1,6x
ID
FLASTESPOST
0.1
88 + 0.28
9.8x
9.8x
Zenof Quaet al
2021
0.05
78. 28.22-1
= 0.35
1x
1.9x
CIFAR-10
FLAST
0.05
86.99
0.14
19.5x
19.5x
ZenFF Qiaer
51.01
0.88
1x
1.6x
100-II (a = 1.0)
FLASPESPUST GBBST
0.1
86.42
0.49
9.8%
9.8x
Zenffl Quiel al
202
0.05
75.54
1-15
1x
1.9x
FLASTESPPEST (00s))
0.05
85.64
0.58
19.5x
19.5x
Quia et
77.15
2.07
1x
17.7x
FEMNIST
wo-IID
FLASSESPESTT (00N)
0.05
81.18
0.36
14.6x
14.6x
5.1 EXPERIMENTAL RESULTS WITH FLASH
To understand the importance of stage 1 in FLASH methodology. we identify a baseline training with uniform layer sensitivity driven pre-defined sparse training (PDST) in FL. 3 details the per- formance of FLASH at different levels of d, for various choices of sparse learning methods. In particu- lar, as we can see in Table Jcolumn 5 and 6, the performance of both NST and PDST produced models cost heavy accuracy drop ultra low parameter density d = 0.05. For example, on CIFAR-10 (a = 0.1), models from NST and PDST sacrifice an accuracy of 16.35% and 5.32%, respectively. However, at comparatively higher den- sity (d = 0.1), both can yield models with lower accuracy difference from the baseline by around 6.46% and 2.82%.
d=0.05
100
Test Accuracy (%6
80
60-
SPOST
JNIVST c.11
SPDST, on the other hand, can maintain close to the base- line accuracy at even ultra-low density for all data partitions.
SPOST (Q-1)
JNWVST (d-1)
20
SPOST
Interestingly, for majority of the cases, it even outperforms JMWST yielded models. These results clearly highlight the efficacy of both sensitivity driven sparse learning (as SPDST PDST) and early mask convergence (as SPDST z JMWST) in FL settings. Importantly, for increased Tint in JMWST, we observe a consistent improvement in accuracy. The inferior accuracy at Tine 1 can be attributed to the mask divergence caused by frequent noisy gradient dependent update. We thus believe efficient hyperparameter search including rint is essential for sparse FL model's 's improved performance, particularly for JMWST. Moreover, JMWST requires additional communication of non-zero weight indices, contrasting SPDST, where clients do not need to send the mask at all, allowing us to yield proportional communication saving as the model density. Fig. 4 shows the acc, vs. round comparison among the two proposed methods on different data distributions.
JNWVST (a-1000)
0
100
200
300
400
500
600
Comm. Round
Figure 4: Test accuracy vs. round for different approaches on CIFAR-10.
Comparison with ZeroFL. Despite leveraging a form of sparse learning Raihan & Aamodi (022)), ZeroFL required significantly higher up-link/down-lintt communication cost compared to the target density d. This enables FLASH to gain a significant advantage in communication saving over ZeroFL, particularly for SPDST, as it only asks for the reduced size parameters to be communicated between the server and clients. In particular, we evaluate the communication saving as the ratio of the dense model size and corresponding sparse model size with the tensors represented in compressed sparse
7

---

Under review as a conference paper at ICLR 2023
Table 5: Performance of hetero-FLASH on various datasets where each client can have density from the set dset E (0.1,0.15, 0.2).
Dataset
Data Distribution
Max Client Density (d.ct)
Hetero-SPDST Acc
Hetero.JMWSS
Hetero-JMWWS
Ae (Pintt
1000)
0.05
97.44
0.23
97.83
MNIST
1.00
0.2
98
29 1 0.09
97.47
0.22
97. .6 1 0.23
IID
96.11
96
1000)
87.10
86.37 0.2
87.39
0.15
CIARR 10 pcB lo
(a
1.00
0.
96.16
+ 0.04
84.07
= 0.06
86.19 = 0.24
75.23
2.75
Y4.34
FEMNIST
non- IID
82..8
1
0.24
62.2 4 0.42
82.5 1: 0.55
row (CSR) format Tinney& & Walker (1977). As depicted in Table
FLASH can yield an accuracy
improvement of up to 10. 1% at reduced communication cost of up to 10.26x (computed at up-link when both send sparse models).
5.2 EXPERIMENTAL. RESULTS WITH HETERO-FLASH
Table Jable5sshows shows the performance of hetero-FLASH where the clients can have three possible density budgets as defined by the dset- We assume the maximum capacity clients' density budget of 0.2. To train all the density values, we first create three sets, each having 40%, 30%, and 30% of total clients, and corresponds to density 0.2, 0,15, and 0.1, respectively. Now, during every round, we sample 10% from each set with corresponding target density. Similar to the trend in FLASH, hetero-SPDST outperforms the JMWST counter-parts by up to 3.93% evaluated on the three datasets. Also, following similar trend as with homogeneous density clients, with increased mask update interval (Fint), the performance of JMTS gets a significant boost in accuracy of up to 3 8.0%.
5.3 QUANTITATIVE ANALYSIS
Roshott8 d.0.55)
303
Roster18
lo=]
196)
Recurecy Chd
0.8
100 200 Comm.
300
500
505
100
420
Corv Layer 1rdec
Round 111
Comm.
Round
Figure 5: (a) Layer sensitivity evaluated at the end of sensitivity warm-up up stage for different client participation size and their local epochs, (b) Comparison of server side model performance with the initialized sparse mask based on different sensitivity evaluated from (a).
Dependence of initial sensitivity warm-up of participating clients. To understand the importance of the clients' participation in the warm-up. we experimented with six different scenarios. In particular, we used two different values of participating clients (110, 20)) each corresponding to three different local epoch choices ((10, 20, 40]). As shown in Fig. 5(a), the yielded pruning sensitivity follows a similar trend. Moreover, an SPDST training with mask chosen from any of these sensitivity lists finally yield FL models with similar performances (Fig. 5())), clearly demonstrating the robustness of our warm-up based sensitivity evaluation st stage 1.
Comparison with ERK+ initialization. We now compare SPDST mask initialization, with that of parameter density distribution evaluated via ERK+ Huang et al. (2022): Evei et al. (2020). Notably, contrary to uniform density. ERK+ scheme keeps more weights for the layers having fewer parameters. Note here, we use SPDST, ERK+, or uniform (PDST) as the initial mask for stage 2, and keep the mask frozen throughout the training of stage 2. As shown in Fig. ba-b), the mask evaluation stage 1 to initialize mask allows SPDST to consistently provide superior results over the other Iwo. We hypothesize this to the better layer sensitivity evaluation scheme of SPDST, particularly at the earlier layers, allowing it to retain more information at these layers.
Importance of parameters' weighted fed averaging at the server. Earlier literature Diao et al. (2000) suggested form of weighted fed averaging, for clients with different model sizes. Inspired by that, we now investigate the necessity of WFA in FLASH. In particular, we performed experiments
'ee understand for FEMNIST, ZeroFL reported significantly higher up-link saving, however, the best of understanding it should be similar their report on other datasets, i.e. 119x.
8

---

Under review as a conference paper at ICLR 2023
Fer Ve:3 on O24833 Hen 3X
Austeell on ORN LO (H0L))
Rordertti Cltle merto Wetett
7M0
Partiinndd
(b]
10:0
Figure 6: (b)-(b) Performance comparison of sparse models trained with SPDST, uniform (PDST) and ERK+ initialized layer-wise parameter density; (c-d)Performance comparison of fedavg with weighted fedavg for (c) different training algorithms and (d) different dataset partitioning (or).
on CIFAR-10 (a 1.0), both with and without WFA, during server aggregation.
shown in Fig. 6 (c), WFA model performs inferior to the fed averaged model in FLASH. On the contrary, Patero-FLASII enjoys consistent superior performance with WFABccd) The inferior performance of WFA in FLASH may hint at the fact that if a weight is non-zero only for fewer clients, as compared to other non-zero weights, giving it equal weight as the others nullifies its lower importance, that may be necessary to preserve for mask convergence. On the other hand, having WFA in hetero FLASH is necessary, as weight's 's less frequent non-zero occurrence can be due to fewer number of high-pane parammarreeer density clients in a round. Further investigations on the utility and use case of such weighted averaging is an interesting future research direction.
Time and communication overhead for stage round with Fg local epochs (for us F.e = 10) per client. A normal FL stage in our settings trains the clients for T rounds, epoch per client/round. Therefore, stage 1 increases the time by
Mask evaluation stage uses one
ResMect on OPAR te
factor of ( Ee the pre- pre-training time overhead negligible.
T. + 1). Usually, Ed << T, making
Ho1
Rer
The communication overhead of stage 1 is also negligible compared to that in each round for the stage 2 FL training. Each partici- pant only needs to send L values for an L-layer model. So, ca clients will have a total communication overhead of (T. x Cd X 32) bits, assuming 32-bit number representation.
Communicaton Cost 1G1)
Communicion Lost tu8)
Figure 7: performance comparison at different up- link limits for (a) 1.0 and (b) 0.1.
Computation saving for FLASH. The training FLOPs for layer (Fleyer) can be partitioned
into forward operation FL.PSs (F)wa). backward input (Fouokinn) in) and weight gradient (Pback_n) w compute FLOPs, With the assumption of no-compute cost associated to the zero-valued weights via zero-gating logic Kundu et al. 2021a), the Flayer for FLASH with parameter density d (d << 1.0) is
Flayer d x [Fulywd Fubackkin + Sa X F Fuback_wt
(3)
where s, is and for SPDST and JMWST, respectively. Fu', represents the corresponding FLOPs associated with an unpruned layer. Thus SPDST provides improved computation benefits along with the communication savings. Further details on FLOPs computation is provided in the Appendix.
Performance at limited communication budget. Fig. a and (b) show the performance of FL models when the clients are communication limited. In particular, we see both PDST and SPDST can significantly outperform other approaches in yielding a significantly well-trained model at low comm. budget. This can be attributed to their significantly smaller model sizes, helping them to run for higher number of rounds than others, on limited bandwidth scenario.
6 CONCLUSIONS
This paper presented federated lottery aware sparsity hunting methodologies to yield sparse server models with low parameter density while costing insignificant accuracy drop compared the un- pruned counterparts. In particular, we demonstrated two efficient sparse learning solutions specifically tailored for FL. enabling better computation and communication benefits over existing sparse learning alternatives. We experimentally demonstrated the superiority of our models in yielding up to 100. improved accuracy with 10.26x fewer communication costs, compared to the existing alternatives Qiu et al. (202I), at similar hy hyperparameter settings. Future research direction of this work includes the theoretical understanding of our observations, and further empirical demonstrations on newer class of models including transformers.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alyazeed Albasyoni, Mher Safaryan, Laurent Condat, and Peter Richtárik. Optimal gradient com- pression for distributed and federated learning. arXiv preprint arXiv:2010.03246. 2020.
Sameer Bibikar, Haris Vikalo, Zhangyang Wang, and Xiaohan Chen. Federated dynamic sparse train- ing: Computing less, communicating less, yet learning better. arXiv preprint 1rXiv:2112.09820 2021.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv:1812.0109) 2018a.
Sebastian Caldas, Jakub Konečny, H Brendan McMahan, and Ameet Talwalkar, Expanding the reach of federated learning by reducing client resource requirements. arXiv preprini arXiv: arXiv:181..0222 1812.07210, 2018b.
Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. arXiv preprint arXiv:1907.04866 2019.
Enmao Diao, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication efficient federated learning for heterogeneous clients. arXiv preprint arXiv:2010.0/26,, 2020.
Xiaohan Ding, Xiangxin Zhou, Yuchen Guo, Jungong Han, Liu, et al. Global sparse momentum sgd for pruning very deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pp. 2943-2952 PMLR, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprini arXiv: /803.0363, 2018.
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. Marina: Faster non- convex distributed learning with compression. In International Conference on Machine Learning, pp. 3788-3798. PMIR, 2021.
Pengchao Han, Shiqiang Wang, and Kin K Leung. Adaptive gradient sparsification for efficient federated learning: An online learning approach. In 2020 IEEE 40th International Conference Distributed Computing Systems (ICDCS), pp. 300-310. IEEE, 2020.
Chaoyang He, Murali Annavaram, and Salman Avestimehr. Group knowledge transfer: Federated learning of large cnns the edge. Advances in Neural Information Processing Systems, 33: 14068-14080, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Yihui He, Lin, Zhijian Liu, Hanrui Wang, Li-Jia Li, and Song Han. Ame: Automl for model compression and acceleration on mobile devices. In Proceedings of the European conference on computer vision (ECCV), pp. 784 784-800, 2018.
Samuel Horvath, Stefanos Laskaridis, Mario Almeida, Ilias Leontiadis, Stylianos Venieris, and Nicholas Lane. Fjord: Fair and accurate federated learning under heterogeneous targets with ordered dropout. Advances in Neural Information Processing Systems, 34, 2021.
Tiansheng Huang. Shiwei Liu, Li Shen, Fengxiang He, Weiwei Lin, and Dacheng Tao. Achieving personalized federated learning with sparse local models. arXiv preprint arXhv:2201.11380 2022.
Rustem Islamov, Xun Qian, and Peter Richtárik. Distributed second order methods with fast rates and compressed communication. In International Conference on Machine Learning, pp. 4617-4628. PMLR, 2021.
10

---

Under review as a conference paper at ICLR 2023
Yuang Jiang, Shiqiang Wang, Victor Valls, Bong Jun Ko, Wei-Han Lee, Kin K Leung, and Leandros Tassuuas. Model pruning enables efficient federated learning on edge devices. IEEE Transactions on Neural Networks and Learning Systems, 2022.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Souvik Kundu, Saurav Prakash, Haleh Akrami, Peter Beerel, and Keith M Chugg. psconv; A pre- defined sparse kernel based convolution for deep cnns. In 2019 57th Annual Allerton Conference on Communicationn Control, and Computing (Allerton), pp. 100-107. IEEE, 2019.
Souvik Kundu, Mahdi Nazemi, Massoud Pedram, Keith M Chugg, and Peter A Beerel. Pre-defined sparsity for complexity convolutional neural networks. IEEE Transactions on Computers, 69 (7):1045-1058, 2020.
Souvik Kundu, Gourav Datta, Massoud Pedram, and Peter A Beerel. Spike-thrift: Towards energy- efficient deep spiking neural networks by limiting spiking activity via attention-guidee compression. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 3953- 3962, 2021a.
Souvik Kundu, Mahdi Nazemi, Peter A Beerel, and Massoud Pedram. Dnr: A tunable robust pruning framework through dynamic network rewiring of dnns. In Proceedings of the 26th Asia and South Pacific Design Automation Conference, pp. 350, 2021
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http://yann
lecun. www.coom//e...... exdb /ombs//ns//////
Ang Li, Jingwei Sun, Binghui Wang, Lin Duan, Sicheng Li, Yiran Chen, and Hai Li. Lotteryfl: Personalized and communication efficiient federated learning with lottery ticket hypothesis on 2020a.
non-iid datasets. arXiv preprini arXiv:2008.0333
Ang Li, Jingwei Sun, Xiao Zeng, Mi Zhang, Hai Li, and Yiran Chen. Fedmask: Joint computation and communication-effiieee personalized federated learning via heterogeneous masking. In Proceedings of the 19th ACM Conference on Embedded Networked Sensor Systems, pp. 42-55, 2021.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429 450, 2020b.
Xiang Li. Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint #rXXiv:907.02166 2019.
Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. Advances in Neural Information Processing Systems, 33:2351-2363, 2020.
Shiwei Liu, Decebal Constantin Mocanu, Amarsagar Reddy Ramapuram Matavalam, Yulong Pei, and Mykola Pechenizkiy. Sparse evolutionary deep learning with over one million artificial neurons on commodity hardware. Neural Computing and Applications, 33(7):2589-2600 2021.
Xiaolong Ma, Sheng Lin, Shaokai Ye, Zhezhi He, Linfeng Zhang, Geng Yuan, Sia Huat Tan, Zhengang Li. Deliang Fan, Xuchai Qian, et al. Non-structured dnn weight pruning-is beneficial in any platform? IEEE Transactions on Neural Networks and Learning Systems, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas Communication-efficient learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, 9(1):1-12, 2018.
Eric Qin, Ananda Samajdar, Hyoukjun Kwon, Vineet Nadella, Sudarshan Srinivasan, Dipankar Das, Bharat Kaul, and Tushar Krishna. Sigma: A sparse and irregular gemm accelerator with flexible interconnects for dnn training. In 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA), pp. 58-70. IEEE, 2020.
11

---

Under review as a conference paper at ICLR 2023
Xinchi Qiu, Javier Srmaadez-MMaquuee Pedro PB Gusmao, Yan Gao, Titouan Parcollet, and Nicholas Donald Lane. Zerofl: Efficient on-device training for federated learning with local sparsity. In International Conference on Learning Representations, 2021.
Md Aamir Raihan and Tor Aamodt. Sparse weight activation training. Advances in Neural Information Processing Systems, 33:15625-15636 2020.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprini arXiv:2003.00295 2020.
William F Tinney and John W Walker. Direct solutions of sparse network equations by optimally ordered triangular factorization. Proceedings of the IEEE, (5(11):1801-180) 1967.
Giyoung Yang and Taewhan Kim. Design and algorithm for clock gating and flip-flop co-optimization. In 2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pp. 1-6. IEEE, 2018.
Dezhong Yao, Wanning Pan, Yao Wan, Hai Jin, and Lichao Sun. Fedhm: Efficient federated learning for heterogeneous models via low-rank factorization. arXiv preprint wrXiv:2/11.146555 2021.
Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing carly-bird tickets: Towards more efficient training of deep networks. arXiv preprint arXiv:/909. 1957, 2019.
Tianyun Zhang, Shaokai Ye, Kaiqi Zhang, Jian Tang, Wujie Wen, Makan Fardad, and Yanzhi Wang. systematic dnn weight pruning framework using alternating direction method of multipliers. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 184-199, 2018.
Tuo Zhang, Lei Gao, Chaoyang He, Mi Zhang, Bhaskar Krishnamachari, and Salman Avestimehr. Federated learning for internet of things: Applications, challenges, and opportunities. arXiv preprint arXiv:211 1.07494, 2021.
Yuchen Zhang, John Duchi, Michael I Jordan, and Martin Wainwright. Information- theoretic lower bounds for distributed statistical estimation with communication con- straints. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 26. Curran Asso- ciates, Inc., 2013. URL htt.a//oee//ppoocceueneeeeeeeeeo (eee5ffffallc13111555533532
Aojun Zhou, Yukun Ma, Junnan Zhu, Jianbo Liu, Zhijie Zhang, Kun Yuan, Wenxiu Sun, and Hongsheng Li. Learning n: m fine-graine ane-grained structured sparse neural networks from scratch. arXiv preprint arXiv:2 (02.04010. 2021.
Zhuangdi Zhu, Junyuan Hong, and Jiayu Zhou. Data-free knowledge distillation for heterogeneous federated learning. In International Conference Machine Learning, pp. 12878 12889. PMLR, 2021.
A APPENDIX
A.1 MODEL ARCHITECTURES
Table shows the model architectures used for MNIST and FEMNIST datasets. For CIFAR-I0 we used ResNet18 He al. 20166) with the first CONV layer kernel size 3 instead of original 7 x 7.
A.2 HETERO-FLASH ALGORITHM
Algorithm
details the training algorithm in hetero-FLASH. Note that and are the two functions that play key role in supoorting heterogeniety sparsity ratios for different clients. The details of these two functions are elaborated in Algortihm andd respectively. We plan to open-source our code upon acceptance of the paper.
aggrPa hawpraaaampddaataaaaaa
and SeroSampeeSereeteee
12

---

Under review as a conference paper at ICLR 2023
Table 6: Architecture used for MNIST and FEMNIST datasets
MNIST
FEMNIST
CONV5 X 5(Co 10)
CONV5 x 5(C. = 32)
pool
max max_pool
CONV5 x 5(C, 20)
CONV5 5(C. 64)
max poo_
max_pool FC(3136, 2048)
FC(5120, 50)
FC(50, 10)
FC 62)
Algorithm 2: Hetero-FLASH Training.
Data: Training rounds T, local epochs F,, client set [[CN, l.., [CN 11, clients per rounds cr, target density set daet [d1, ....., sensitivity warm-up epochs Es, density warm up client count cat, initial value freeze masks meees O, training algorithm and aggregation type Agr.
Minit +-
@reatteRandomMask)
θ gint
Ani.MMaseeeeieeeggtttttaaa (M
serverExecute:
Randomly sample clients [Cal C [CNxr]
for each client E [Ca] in parallel do
Oe +- Exeuute
Ed, 0)
S. + conpuseeensstiiiiiy((e))
end
M < (as.ttMass((S.)dd..)))
10 O LnittMaaeeeeeeeihht( (M²)
11 frees + FreezeMask(4)
12 for each round /
do
13
Randomly sample clients [C,] C [CN]
14
for euch client E [Cr] in parallel do
15
0 [xex E freez)
16
end
17
O f
asgrParamUjpdateNaask Agr)
18
O' subSampleSeerverMceee (0)s, [9'], duet, Te freaz)
19 end
20 cLientExecuteeS.. Myfaes)
21 O_0 t Oe
22 for local epoch i + to E do
23 Oe +- [ Metrecss)
m/eres checkupdateMaskk)
25
26
return 05
Algorithm 3: aggrPa
Data: Round 4, aggregation type Agr [fedAvg, wewghteddeddieeeee.e edAvg], clients updates [O']= = [ 1, client data size [dse] ds.,]
if Agr is fedAvg then
O E don
Es, - Ot
clse
//For heteH--FLASH
W' < iiiitWeightFactoor)
for each update O., e [
Wt +- dsc, x retrieveMask((__) w W W., end
10
/safeDivide(abb gives zero anywhere the b is queal to zero O <- Ee Lass w") 0,
11
12 end
13

---

Under review as a conference paper at ICLR 2023
Algorithm 4: wwwsampleeeereereeeeeo....
Data:
Current round id L, client set [C-], aggregated Weight O' of model with L layers, support density set
daet [di.-.., dar] where d; 1,+1, model layer-wise parameter count [k] [k], [K',.... 1
size(dget) is then
WJMWST subsampling in FLASH
M + initMaskwichzerros
(d'...., d'1 + arggayyar/ssseeestttv(.)).
dixk
ry Σt_, d'
for layer 1 to do
idx +-
n2 - int(r x d' k²) //number of non-zetos
M [ixx| nal]
10
end
else
12
/For hetero-FLASH for di E duat do
13
14
M. + (nitMaaaiitteerrss)))
15
end
D +- (ettttrrreeetteestt((((..
16
( ""....d 801 t gettlayerriiseeeessttyff...
17
18
for layer I
to J, do
idx + gettooteeleeegtttnteeettt Indeicee
for d, E dset de
21
rs. + Di
n= + int x d' k²)
23
M. Mi n=]]
24
end
end
26 end
A.3
ADDITIONAL COMPARISONS
We now compare the performance of FLASH with that of yielded via FedSpa Huang et al. (2022). and FedDST Bibikar et al. (202I). For FedSpa, we implemented their proposed algorithm in our settings and kept all the hyperparameters same for an apple-to-apple comparison. For FLASH, report the best of the accuracy yielded via models trained using SPDST and JMWST. As shown in Table FLASH generated models can outperform that generated via FedSpa with improved accuracy of up to 2.41 %. Similar trend observed when we compare with FedDST and as Table on MNIST dataset, FLASH can have accuracy improvement of up 1.41 44%.
Table 7: Comparison of FLASH with FedSpa Huang et al.
2022 on CIFAR-10 with ResNet18.
Data
Method
Density
Best Acc. (%)
Acc
distribution
α 1000
FedSpa
0.05
85.63
FLASH
0.05
87.
+1.55
0.1
FedSpa
0.05
73.08
FLASH
0.05
75.49
+2.41
A.4 MORE QUANTITATIVE ANALYSIS
Alation with the mask update interval rounds (Finc). As mentioned in the case of JMWST, to save communication energy we often can choose not to update the mask every round. We thus performed ablation with increased frequency of mask update interval round Tine from the default value (similar to Qiu et al.] (202T)). Table shows the results with different in the table, less frequent update intervals does not degrade the final
original manuscript,
Tint- In particular,
14

---

Under review as a conference paper at ICLR 2023
Table 8: Comparison of FLASH with FedDST Bibikar al. (2021) on pathologically non- non-IID MNIST.
For this comparison we used same hyperparameter settings and models as that in Bibikar et al. (021
Method
Density (d)
Communication Cost (GiB)
Best Acc. (%)
dAce
FedDST
0.2
1.0
96. 10
FLASH
97.51
+1.41
FedDST
0.2
2.0
97.35
FLASH
97.69
+-0.44
model performance. Moreover, less frequent update can provide additional savings in terms of up-link cost for the models as the masks do not change every round.
Table 9: Ablation with different mask update intervals for JMWST for a target density d = 0.1 on CIFAR-10.
Model
Data distribution
Mask update interval rounds (Timc)
Tint
Tina =
Yina =
Tint 10
IID (a 1000)
87.62
0.35
87.76
0.07
87.86
87.67
0.09
ResNet18
non- (a 1)
86.45
+ 0.31
86.26
0.07
86.36
20133
86.68 + 0.25
non-lID (a = 0.1)
74.74
1.07
73.73
1.18
75.47 1 1.08
77.1410.22
(a), shows that JMWST and SPDST follow the same pattern at the baseline model (d = 1.0) with FedAvg. In other words, similar to FedAvg, as the G- increases, the performance enhances. Also, for a specific Gr, JMWST and SPDST perform better than PDST and NST.
Impact of Number of participating clients per round. Fig. 8
Impact of Batci-toormalization layer statistics. Fig 8 (b), shows the performance comparison between batch bormalization (BN) and static batch normalization (static BN, as suggested in Diao al. 20200). In particular in setting, using BN layer statistics always outperform the static BN.
100
ResNat18 (a
1000
ResNet18 CIFAR-10
Test Accuracy (95)
97.13
82.48
82.33
80
70-
POST26-5
SPOOTI
tediiig (d+:)
30
Feddug [dm1]
JMWST
SPOST (dm0.05)
#Cliants per
(dm0 (.00005)
(a)
(b)
Method
Figure 8: (a) Performance of the final trained model for different participating clients per round, (b) Significance BN and Static BN in final model performance.
4a. Revisiting sparse mask mismatch for NST with VGG16. Fig. shows the comparison of SM between centralized and FL settings with NST on VGG16, another popular model variant. Similar to our observed trend with ResNer18, we see a significantly high SM for FL settings with target 0.05. This strengthens the generality of our observed limitations across different class DNN models.
10016 41 CHCNN 10--2222 CAnTral
W0 DRA--B 10-11-1------11 1.5.-11--..1111 (ROESONE)
66
0200
Figure 9: (a)-(b) Sparse mask mismatch (SM) for VGG16 in (a) centralized and (b) FL settings with NST. (c)-(d) Layer-wise SM vs. training epochs (rounds) for VGG16 in (c) centralized and (d) FL settings, respectively, with NST.
15

---

Under review as a conference paper at ICLR 2023
4b. Revisiting sparse mask mismatch for FLASH. As demonstrated in Figs 10 mismatch in the case of JMWST significantly reduces, helping the mask train in a convergent way, significantly faster than that in NST.
the sparse mask
Fig. IT shows the layer-wise SM, for centralized trained model (Fig. T and FL trained model with sparsity (Fig. b-c). In particular, the SM at later layer can significantly reduce in the case of JMWST compared to NST, further demonstrating the convergence ability even at the later layers.
ResNet19 CIFAR-10 1d-0.05, Centralized)
ResMett2 CIFAR.00
d-0.05, Federated
RedMat19 CIFAR 10
d-0.05, Feceroted!
25-
25-
E2oth
13-
325-
275
295-
(a) Epoch
[b] Comm. Round
(c)
Comm. Round
Figure 10: Sparse mask mismatch (SM) for (a) centralized sparse learning, (b) NST, and (c) JMWST in federated settings.
Core kpe
Peofiett an DHAR 2ow0 25 Centrolent
40 040.0 Faberitd
Peoteett on CIA 30 1 de0 Federttet Sgaliiurddy SM for INNKST
lewards mask aprenieent for alllaye
30
4pcch 150
375
[1) Corne
23
62)
2/5
100
Figure 11: Lase sparse mask mismatch (SM) vs. training epochs (rounds) plot for (a) centralized and (b) FL with NST, and (c) FL with JMWST.
4c. Sparse mask mismatch as a function of d. To understand the relation of SM with d we performed the baseline sparse training (NST) with ResNet18 on CIFAR- 10 for three different target densities, 0.05, 0.25, 0.5. As shown in Fig. [2 the S.M tends to reduce for higher density. In particular, Fig- 12 d) shows the SM for CONV layer T6 (a later layer), after round 200. The SM reduces by 1.53 x for d = 0.5 than that with d = 0.05, strengthening our general observation that SM becomes prominent as the density gets lower.
Rosket2 en CHO0.10 10 #1 de0.33 Peportog) Reafic:9 on CHAR 22 2. ded Podonseg RocMM33 on CPAN 3a- d+0.3 Pecerotd) Dollett on CRAN 10 Bayer Ice28, tourd-2000
275
3
6
630
6:55
05
Raard
Conre
Figure 12: (a-c) SM for FL settings for three different d of 0.05, 0.25, and 0.5, respectively. (d) Comparison of Jaccard distance values for the 16th CONV layer of ResNet18 after round 200 for different ds.
4d. Sparse mask mismatch as a function of number of clients. To understand the relation of SM with number of total clients, we performed the baseline sparse training (NST) with ResNet 8 on CIFAR-10 10 for 50 and 200 clients, respectively. As shown Fig. [3] the SM concern persists, irrespective of the number of clients. This strengthens the generality of our observations over total number of clients.
5. Convergence trend of proposed algorithms. Fig. 14 shows the test accuracy vs FL rounds for NST, PDST, SPDST, and JMWST algorithms CIFAR-10 dataset with non-lID data distribution (a = 1). As shown the plots, for d 0.05 and = 0.1, NST has slower convergence with lower final accuracy. Introducing consensus among the clients for the sparse mask accelerates the convergence and enhances the final performance.
6. Communication saving and FLOPS evaluations.Emmloyii sparse learning in FL helps par- ticipating clients reduce both the communication and compute costs (FL.Ps) for training. Without
16

---

Under review as a conference paper at ICLR 2023
PAIh 22 25 Rectacieod
Commn (80
Comes
Figure 13: (a-b) SM for FL settings for (a) 50 and (b) 200 clients. (c-d) Layer-wise SM vs. training rounds for (c) 50 and (d) 200 clients.
100
Seeveria or CEARLS a-1 4-0.25
100
Rectedti on CFWA 10.00000000000 2.5--
to Mcstoo
20
JWWST
SP061
SPOST
1000
200
2002
420
500
600
100
203
200
420
500
600
00
Locoin Poaurd 50
06
Lonin Houne
Figure 14: Performance of proposed algorithms vs. comm. rounds on CIFAR-10 dataset for (a) d = 0.05 (b) d = 0.1.
the loss of generality, we now evaluate the convolutional layer training FLOPs for FLASH, and demonstrate the relation of parameter density d with FLOPs and communication saving. Let us assume a layer has a weight tensor 0' E @CCxx, where h and w are the height and width of the convolutional kernel, and C, and C2 represent the number of filters and channels per filter, respectively. It takes an input tensor I E IR C xWW Let us also assume d to be the density of non-zero in the weight tensor for all the layers. During training, FLOPs associated to each weight tensor update can be partitioned in to three component, namely, forward pass FLOPs (F) (Fiud), backward input grad FLOPs (Fback jn). and backward weight grad FLOPs (Fback_wt). The weight sparsity helps both Fowd and Fback_in to reduce proportionally as given below.
to produce an output tensor O E C. x
(R S) C. Foack = d C. x (h X w) (H X W) C.
Fynd d C.
w)
(5)
Finally, if the zero weights' gradients flow is computed for the purpose of mask learning, then Fback can't leverage the advantage of low parameter density. Thus during mask training of JMWST, as the gradient needs to be dense, Fback_ we is same as that in dense computation. However, for SPDST, zero weights remain as zero, allowing us to safely skip the associated gradient computation. This essentially helps SPDST to extract benefits of sparsity during all the three stages of FL.PSs computation. Following Eq. shows the Fback we in FLASH.
Fbock_tt 5a C. X ( ( W)) C.
(6)
where,
84 1, for JMWST
d. for SPDST
For similar density, clients in ZeroFL also enjoys similar benefits in Fjwd and Fback_nn- However, Fback can be reduced only via introduction of activation sparsity, a. It is well surveyed in literature that having sparse activation density as low as parameter density may significantly impact model performance. Thus generally, d that allows SPDST enjoy a FLOPs benefit of a for Fbock_et-
ResNet1B on CIFAR-10 (d=0.05)
Test Accuracy (%))
89
80
0.0.1
These computations can be easily extended to linear layers. Also, can safely ignore the FLOPss associated to the BN layers due to their negligible contribution to the total FLOPs.
12
Faxt
Figure 15: Test accuracy vs.
7. Discussion on compute benefits at the edge. To extract FLOPs benefits for irregular pruning in FLASH, we assume that the com- pute energy for the sparse network can be avoided via the means of clock-gating Yang & Kim (0018) of the zero-valued weights. Moreover, there has been recent development of sparsity-friendly DNN
mask update interval round.
17

---

Under review as a conference paper at ICLR 2023
Repleell on CBRAA-16
ResMett on CIRRR-10
FecNer18 CIRAR-10
100%
FL00%
102.omm ca 1981
(31 derdetiityy 221
1C1 ic.denst ty 901
Figure 16: Computation and Communication relation with (a) each other (b, c) with different density levels for SPDST algorithm.
accelerators Qin et (2020) that can efficiently reduce the compute cost by significant margin. Such accelerators can leverage the yielded sparse FL models to deploy at compute constrained edges.
8. FLOPs communication cost for different density budget. To reach target accuracy value, we now plot the FLOPs to uplink communication cost for different density budget in Fig. T6
9. Impact of Tint. As depicted in Fig. 15 the test accuracy improves with the increase in JMWST mask update interval rent- particular, for both a 0.1 and 1.0, the accuracy with increased Tint can be up to ~1.6% and ~0.98% respectively. Interestingly, the improvement tend to saturate after certain Tint- Thus, consider important sparse learning hyperparameter search interesting future research direction.
A.5 DISCUSSION ON SUPPORT FOR HEIDWARE-FRIENDEE SPARSITY PATTERNS
Irregular sparsity often not well suited for hardware benefits without any dedicated architecture compiler support. Among the various hardware- feiere-frendlyyye sparsity patterns recently proposed N M sparsity (Zhou et al. (202T) has gained significant attention, due its less stricter constraints compared to other structured sparsity patterns. For SPDST, post stage sparse mask selection can easily extended to support the N M sparsity. In particular, for layer I, instead of random assignment of d' k non-zero mask locations, we can partition the total non-zero elements in G groups. where each group will contain d' x K//G' non-zero elements. Here G is evaluated as k/ /// M representing the total element size out which we need to have a certain fraction as non-zero, and k ensured
represents the total number of weights for that layer. As the masks remain frozen, such pattern is maintained throughout the training for each client to extract the benefit. For JMWST, we can adapt this principle in the prune and regrow policy that happens during local training of each client. We have added section in the appendix detailing on this important discussion.
18


Reviews:
[{"review_id": "ziKgGWlwmgN", "reviewer": "Reviewer_womR", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper tries to improve the sparse network training efficiency in a Federated learning framework in two folds: 1) bridging the gap between the sparse network and its dense counterpart (e.g., FedAvg) and 2) saving the communication cost between clients and the server.   To this end, the proposed method performs a two-stage sparse training, including the mask-sensitive evaluation (for mask initialization) and networking training, and investigates two different mask learning strategies -- 1) fixed masks and 2) jointly training over masks and weights. Experiments on three public datasets were provided in terms of both IID and non-IID settings.   ", "summary_of_the_review": "Overall, the paper provides a technically sound method to solve several practical challenges in incorporating sparse network training into a Federated learning framework. However, please refer to my concerns on methodology, experiment, and network depth in the above sections.  ", "strength_and_weaknesses": "Pros:\n- The proposed hetero-FLASH method is interesting and well adapted to the Federated learning setting over diverse edge resources. While the sampling and fusion strategy is straightforward, the proposed solution poses a good baseline for exploring dynamic budgets in a Federated learning framework. \n- It is technically sound to bridge the gap between sparse network training and its dense counterpart by developing a two-stage method to evaluate mask sensitivity in advance. \n- Two mask learning strategies, namely SPDST and JMWST, were designed and developed on three datasets under two different settings. \n\nCons:\n- While several observations were discussed and provided with empirical evidence, it somewhat lacks in-depth or theoretical analysis regarding the reasons behind these observations. Also, all the observations were provided on the same model architecture (ResNet18), which might lead to model bias in the conclusions. \n- The proposed stage 1 lies in the key contribution of this work. Thus, some ablated models like SPDST w/o state 1, and JMWST w/o state 1 are expected to be provided in the experiment. Plus, it is unclear to me how the proposed method encourages mask convergence -- by individually using SPDST or JMWST, or by dynamically switching between these two methods?\n- The experiment results are less convincing due to the lack of baselines (e.g., Huang et al. (2022) and Bibikar et al. (2021)) and ablated models. Although mask convergence has been well discussed, training convergence and parameter analysis on mask initialization are expected. It also remains unclear if the proposed method can be applied in a deeper model, such as ResNet34, ResNet50, and ResNet101", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": {}}, {"review_id": "nILSMC57Ju", "reviewer": "Reviewer_vopV", "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": "", "summary_of_the_paper": "The paper targets sparse training in the federated learning domain. The paper starts with multiple observations (on small models) about how disagreement of clients on the sparsity mask pattern could significantly reduce the model accuracy, compared to a centralized training. It also shows that this disagreement on the sparsity mask pattern diverges as the training progresses. Based on these observations, the authors propose a two-stage sparse federated learning method with two main purposes; (1) decoupling the identification of initial sparse mask from training and (2) collaboratively learning sparse mask and model weights. Finally, the paper extends the method for a heterogeneous environment (which I think may not be aligned with the main message of the paper) where each client has a different resource budget for which different sparsity mask is required.", "summary_of_the_review": "I think the paper is well-motivated with clear description of the observations. The authors went deep into a better understanding of the root cause of low model accuracy in a federated learning setting. While I agree with the authors that this disagreement between sparsity mask patterns *could* be one of the reasons for low accuracy, but I am not convinced that this is the sole reason for such performance degradation. In addition, as mentioned in the questions, it would be great if the authors could provide additional results for higher density ratio to better understand whether such problem exists in a more realistic setting.", "strength_and_weaknesses": "**Strength**\n\n- The paper starts off with multiple observations about the meager accuracy of models in a sparse federated learning setting and then proposes multiple solutions to mitigate the challenges.\n\n- The results across few models seem to be promising, both in terms of final model accuracy and reduced communication. \n\n**Weaknesses**\n\n- While I liked the structure of the paper, it is not clear how bringing the heterogeneity of a system is aligned with the message of the paper. \n\n- While sparsity is an interesting paradigm to reduce various bottlenecks in models, I am not sure if that low density rate (where the most benefit of the paper emerges) at the cost of accuracy degradation would be an acceptable solution even for federated learning. As such, this is not clear if the proposed solution is for a realistic problem setting.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LKUvZWoTBnu", "reviewer": "Reviewer_cFmd", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper studies sparse training in a federated learning setting. The authors show that a naïve implementation has significant accuracy degradation, and they proposed a method called federated lottery-aware sparsity hunting. Experiments on ResNet-18 on MNIST, EMNIST, and CIFAR-10 show that the proposed method improves accuracy and reduces communication costs.", "summary_of_the_review": "The setting of this work is unclear to me. The applicability of the proposed method also seems narrow. ", "strength_and_weaknesses": "## strength\nThe authors identify an interesting problem: the accuracy drops for sparse training in the federated learning setting.\n\n## weakness\n1. The paper is hard to follow. I don't understand why FL cannot achieve converged sparse masks. The only difference between centralized and federated learning is data distribution, but you can always have a consensus model on the server by averaging the gradients from workers, right? Or if you use local SGD and average the models, you can fix the sparse mask on each worker between synchronizations, right? \n\n2. The proposed algorithm is designed based on one particular pruning method (Kundu et al. 2021). Does it apply to other sparse training methods (e.g. RigL)? ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject