SpaFL: Communication-Efficient Federated Learning With Sparse Models And Low Computational Overhead
Authors: Minsu Kim
Walid Saad
Merouane Abdelkader DEBBAH
Choong Seon Hong
Venue: NeurIPS 2024 poster (2024)
Keywords: Federated Learning
Communication and Computation Efficiency
Pruning
Primary area: other
TL;DR: We find optimal structured sparse models by communicating trainable thresholds

Abstract: The large communication and computation overhead of federated learning (FL) is one of the main challenges facing its practical deployment over resource-constrained clients and systems. In this work, SpaFL: a communication-efficient FL framework is proposed to optimize sparse model structures  with low computational overhead. In SpaFL, a trainable threshold is defined for each filter/neuron to prune its all connected 
parameters, thereby leading to structured sparsity. To optimize the pruning process itself,  only thresholds are communicated between a server and clients instead of parameters, thereby learning how to prune. Further, global thresholds are used to update model parameters by extracting aggregated parameter importance. The generalization bound of SpaFL is also derived, thereby proving key insights on the relation between sparsity and performance. Experimental results show that SpaFL improves accuracy while requiring much less communication and computing resources compared to sparse baselines. The code is available at https://github.com/news-vt/SpaFL_NeruIPS_2024

SpaFL: Communication-Effiiinn Federated Learning with Sparse Models and Low Computational Overhead
Minsu Kim Virginia Tech
Walid Saad Virginia Tech
Merouane Debbah
Choong Seon Hong Kyung Hee University
Khalifa University
Abstract
The large communication and computation overhead of federated learning (FL) is one of the main challenges facing its practical deployment over resource- constrained clients and systems. this work, SpaFL:: a communication-eficceen FL. framework is proposed to optimize sparse model structures with low computational overhead. In SpaFl., a trainable threshold is defined for each filter/neuron to prune its all connected parameters, thereby leading to structured sparsity. To optimize the pruning process itself, only thresholds are communicated between a server and clients instead of parameters, thereby learning how to prune. Further, global thresholds are used to update model parameters by extracting aggregated parameter importance. The generalization bound of SpaFL is also derived, thereby proving key insights on the relation between sparsity and performance. Experimental results show that SpaFL improves accuracy while requiring much less communication and computing resources compared to sparse baselines. The code is available at https://gthub..om/nwwwwwww
NerulPS_2020
Introduction
Federated learning (FL) is distributed machine learning framework in which clients collaborate to train machine learning (ML) model without sharing private data [ In FL, clients perform multiple epochs of local training using their own datasets and communicate model updates with server. Different from classical, centralized ML, FL systems typically deployed edge devices such as mobile or Internet of Things (IoT) devices, which have limited computing and communication resources. However, current ML models typically too large and complex to be trained and deployed for inference by edge devices. Moreover, large model sizes can induce significant FL communication costs on both devices and communication networks. Hence, the devices and systems requires optimized
practical deployment of FL over resource-construiig computation and communication costs for both edge devices and communication networks. This has motivated lines of research focused on reducing communication overhead in FL 2 training sparse models in FL for inference [10 gradient compression, and transmitting the subset of models in order reduce the communication costs of FL. However, the associated computational overhead of these existing algorithms remains high since devices have to train dense model. train and communicate sparse models are proposed. However, the works in 4 5 used unstructured pruning, which difficult gain the computation efficiency in practice. Moreover, the computation
9 and optimizing model architectures to find a compact model 12 The works in 2 3] proposed training algorithms such as quantization,
6
9 FL algorithms in which devices
"This work was supported in part by grant from the Amazon- Amazon-Virginia Virginia Tech Initiative for Efficient and in part by the Robust Machine Learning and U.S. National Science Foundation under Grant CNS-21 2114267.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

and communication overhead can still be large if model sparsity is not high. In 66 7 8 91. the authors investigated the structured sparsity, however, the solutions therein either fixed the channel sparsity patterns for clients or did not optimize the pruning process. Furthermore, the FI. approaches of [T] 12 can significantly increase computation resource usage by training multiple models for resource- resource-constrained devices. Clearly, despite a surge of literature on sparsity in FI., there is still a need to develop new FL algorithms that can find sparse model structures with optimized communication efficiency and low computational overhead to operate on resource-constrained devices.
The main contribution of this paper is SpaFL: cotammmiicatio-effciiiee FL framework for optimizing sparse models with low computational overhead achieved by performing structured pruning through trainable thresholds. Here, a trainable threshold is defined for each filter/neuron to prune all of its connected parameters. To optimize the pruning process, only thresholds are communicated between clients and the FL server. Hence, clients can learn how to prune their model from global thresholds and can significantly reduce communication costs. Since parameters are not communicated, the clients' parameters and sparse model structures will remain personalized while only global thresholds are shared. We show that global thresholds can capture the aggregated parameter importance of clients. We further update the clients' model parameters by extracting aggregated parameter importance from global thresholds to improve performance. We analyze the generalization ability of SpaFL and provide insights the relation between sparsity and performance. We summarize contributions as follows:
We propose new communicationn-effiieeen FL framework called SpaFI., in which clients optimize their sparse model structures with low computing costs through trainable thresholds.
We show how SpaFl. can significantly reduce communication overhead for both clients and the server by only exchanging thresholds, the number of which is less than two orders of magnitude smaller than the number of model parameters.
We provide the generalization performance of SpaFL. Moreover, the impact of sharing thresholds the model performance is theoretically and experimentally analyzed.
Experimental results demonstrate the performance, computation costs, and communication efficiency of SpaFL compared with both dense and sparse baselines. For instance, the results show that SpaFL uses only O. 0.17% of communication and 12.0% of computation resources compared to a dense baseline FedAvg while improving accuracy. Additionally, SpaFL improves accuracy by 2.92% compared to sparse baseline while consuming only 0.35% of this baseline's communication resources, and only 24% of its computing resources.
2 Background and Related Work
2.1 Federated Learning
Distributed machine learning has consistently progressed and achieved success. However, it mostly focuses on training with independent and identically distributed (i.i.d) data [33 14]. The FL frameworks along with the FedAvg [1] enables clients to collaboratively train while preserving data privacy without data sharing. Due to privacy constraints and individual preferences. FL clients often collect non-iid data. As such, data can exhibit differences and imbalances in distribution across clients. This variability poses significant challenges in achieving efficient convergence. For a more detailed literature review, we refer to [5] 16). Although most of state-of-the-ar FL methods are effective in mitigating data heterogeneity, they often neglect the computational and communication costs involved in the training process.
2.2 Training and Finding Sparse Models in FL
To reduce the computation and communication overhead of complex ML models during training. the idea of embedding FL algorithms with pruning has recently attracted attention. In [4]
6 7
8, 9 I7 18 19
23 24| 25], the clients train sparse models and communicate sparse model parameters to reduce computation and communication overhead. To improve the aggregation phase with sparse models, the works in 17 20 21 perform averaging only between overlapping parameters to avoid information dilution by excluding zero value parameters. The authors in [18] obtained sparse model by selecting particular client to prune initial dense model and then
20,
21
22

---

Global thresholds
र(t 1) R (x(()
Thresholds (t(t)
Thresholds Tx(t)
Server
Structured sparse model
Data Client
Client
Data
Structured sparse model
Wi (t)
(c)))
Figure 1: Illustration of SpaFL framework that performs model pruning through thresholds. Only the thresholds are communicated between the server and clients.
performed training in a similar way to FedAvg. In 4 24, the authors presented binary masks adjustment strategy to improve the performance of sparse models and communication efficiency. The work in [25] progressively pruned dense model for sparsification and analyzed its convergence. In 19 22 the clients optimized personalized sparse models by exchanging lottery tickets [26] every communication round. The work in [5] obtained personalized sparse models by / norms constraints and the correlation between local and global models. In B the authors proposed dual pruning scheme for both local and global models to reduce the communication costs. The FL framework of 23 allows clients to train personalized sparse models in a decentralized setting without a central 19
server. Although these works [17] 8 4 [24 25
[2] 5 23 adopted sparse models during training, they used unstructured pruning. which is difficult to improve the computation efficiency in practice. Meanwhile, with structured sparsity, the authors 7 proposed a training scheme that allows clients to
train smaller submodels of global model. In 9 clients train set of submodels with fixed channel sparsity patterns depending on their computing capabilities. The work in [ studied structured sparsity by adjusting clients' channel activation probabilities. However, the works sparsity patterns and did not optimize sparse model structures. Although (6) optimized channel activation probabilities, the communication cost downlink still remains high as a server broadeasts whole parameters. Similar to our work, in 27 28). only binary masks are communicated and optimized by training auxiliary variables to learn sparse model structures. However, the work in (27] approximated binarization step using sigmoid function during forward propagation. In (28), the downlink communication costs remained the same as that of FedAvg. In [TO] [T] [29], clients perform
g fixed
by training multiple models find optimized and sparse models to improve computational and memory efficiency at inference phase. However, in practice, clients often have limited resources to support the computationally intensive architecture search process [30. Therefore, most prior works either adopted unstructured pruning or they still required extensive computing and communication costs for finding optimal sparse models. In contrast the prior art, in the proposed SpaFL framework, we find sparse model structures with structured sparsity by optimizing and communicating trainable thresholds for filter/neurons.
3 SpaFL Algorithm
In this section, first present the proposed pruning scheme for structured sparsity and formulate FL problem to find optimal sparse models. Then, we present SpaFL to solve the proposed problem with low computation and communication overhead.
3.1 Structured Pruning with Trainable Thresholds
We define a trainable threshold for each neuron in linear layers or for each filter in convolutional layers. The neural network of client & will consist of L layers as (Wi..... W For parameters W! k e a x in a linear layer I, we define trainable thresholds T' ih for output neurons. If it
3

---

is a convolutional layer W E Re xk''x xh! where c/n is the number of input channels and k' x hi' are the kernel sizes, we can change W as W R with n = ch k h'. Similarly, we can define the corresponding thresholds T' R for filters in that layer. Then, for each client k, we define a set of total thresholds T T= (T) (T',..... ...., .... Note that the number of these additional thresholds will be at most I 1% of the number of model parameters d.
For threshold 7 of filter/neuron i in layer 1, compare the average magnitude of its connected pa-
rameters u 1/ Σラ= [ its value T/. If p.k. T., we prune all connected parameters to this filter/neuron. Hence, our pruning can induce structured sparsity unlike [31]. Thus, we do not need to compute the gradients of parameters in a pruned filter/neuron 32 during backpropagation.
We can obtain a binary mask p for W as follows
Pl.y = S(pRa - :))), isis nour: 1 j S Tin.
(1)
[ by performing where S(-) is a unit step function. Hence, we can obtain the binary masks {pr..... Pk
(T) at each layer. To facilitate the pruning, we constrain the parameters and thresholds to be within [-1,1] and [0, 1). respectively (1). For simplicity,
unroll (W)..... W and (pl..... pF)
to we Rdd and Pk. Rd respectively done in [33] Thresholds represent the importance of their connected parameters (see more details in Section (.3.I). Hence, clients can know which filter/neuron is important by training thresholds, thereby optimizing sparse model structures. Then, the key question becomes: Can clients benefit by collaborating to optimize shared thresholds in order to find optimal sparse models? We partially answer this question in Table D
Following the same configurations in Section [ clients with non-iid datasets only train and communicate thresholds т while freezing model parameters.
Algorithm Trained + Initialization
FMNIST 5..52
CIFAR-I0 60.94+3.4
CIFAR-I00 24.80+1.11
10.22 + 0.25
10.38 = 0.42
1.43 = 0.53
Table 1: Only thresholds are trained and communicated while parameters are kept frozen.
We can see that learning sparse structures can improve the performance even without training parameters. This also corroborates the result of (28). Motivated by this observation, we aim to find optimal sparse models of clients in an FL setting by communicating only thresholds in order to reduce the communication costs in both clients and server sides while keeping parameters locally. The communication cost will decrease drastically because the number of thresholds will be at most 1 % of the number of model parameters d. Essentially, we optimize the sparse models of clients with small computing and communication resources by communicating thresholds.
3.2 Problem Formulation
We aim to optimize each client's model parameters and sparse model structures jointly in a per- sonalized FL setting by only communicating thresholds. This can be formulated as the following optimization problem:
min 7,00
Fx Fu T),
N
De
Fa T) = DR Σ C(w; 3 P:(T): (æ,, 9:h),
S.L.
(2)
where ú; Wy @ (T) is a pruned model, Fx(-) is empirical risk associated with local data of client k, L is a loss function, D; is the number of data samples, {x, y} is an input-label pair, wy captures the model parameters, and then the corresponding parameter of wi will be pruned. Our goal is to obtain the optimal wy and T for each client in order to reduce the computation and communication overhead during training. However, solving 2 is not trivial because and t are highly correlated. Moreover, structured sparsity can induce large performance drop due to coarse-graine grained sparsity patterns compared to unstructured pruning [34].
the Hadamard product. If element of P& (T) zero,

---

3.3 Algorithm Overview
We now describe the proposed algorithm, SpaFL, that can solve (2 while maintaining communication- efficiency with low computational cost. In SpaFL, every client jointly optimizes its personalized sparse model structure and model parameters with trainable thresholds, which can used to prune filters/neurons. To save communication resources, only thresholds will be aggregated at server to generate global thresholds for the next round. Here, global thresholds can represent the aggregated parameter importance of clients. Hence, at the beginning of each round, every client extracts the aggregated parameter importance from the global thresholds so as to update its model parameters. The overall algorithm is illustrated in Fig T and summarized in Algorithm [
3.3.1 Local Training for Parameters and Thresholds
At each round, server samples a set of clients S, such that |S, K for local training. For given global thresholds T() at round 6, client k E S, generates binary mask (T)))) using (I)
Subsequently, obtains the sparse model wx (() = wr (P) To improve the communication efficiency, each sampled client performs E epochs using mini-batch stochastic gradient to update parameters and thresholds as follows:
w w (t) t (f(() - ((tt), (t( = (t) E
(3)
(t) + (t()) - -nnnnn((thh(@)))) ((t) rh(t) = (t), 0 E
(4)
where 9& (t)) = Ft
with mini-batch and (t)) is learning rate. Parameters of unpruned filter/neurons and thresholds will be jointly updated via backpropagation. To enforce sparsity, add regularization term Ri(t) to 4 in order to penalize small threshold values. To this end, client & first calculates the following sparsity
(w)(())
T (t): V,F((Ei(t,
regularization term R(t) Σt Ee cxp(- (T)). Then, the loss function can be rewritten as:
(L( + (L(
(5)
where 0 < < is the coefficient that controls R(t). From we can give thresholds r(t)
performance feedback on the current sparse model while also progressively increasing T(t) through the sparsity regularization term R(t) [3I]. From (5). client &o then updates the received global
thresholds r(t) via backpropagation as follows
T ++ - ((() ( (tth
+
(6)
After local training, each client & E S,, transmits the updated thresholds (x( to the server. Here, the communication overhead will be less than one percent of that of transmitting the entire parameters. Subsequently, the server performs aggregation and broadcasts new global thresholds, i.c..
+(++1)
Σ Tn()). KES,
K
Here, in SpaFL, clients communicate only thresholds. Then, what will clients learn from sharing trained thresholds? Next, we show that thresholds represent the importance their associated filter/neurons.
5

---

3.3.2 Learning Parameter Importance From Thresholds
Clients can know which filter/neurons are important by sharing trained thresholds. For the threshold of filter/neuron at layer of client its gradient can be written as below
Tie Dug (t) aF T (t))
"
1/, ((f (t(
(g)(
(T
Bu k,yy (4)
Tt (1)
pin kay (1) (0
(,)(())))
(Q (t)
auf (t) o PRaj (t) as(QE) 0)
(g (,((0)
(8)
as(Q (t)
(1)(() (t)
g ( (1))
(9)
where (1)(1) - (1)
cll in is from the definition of pruned parameters in 2 and T
the unit step fiunction S(-), and ( is from the identity straight-through estimator 35 to approximate the gradient of the step functions in
From p
see that threshold
ed corresponds the importance of its connected parameters TR
S m/g. in its filter/neuron. This is because the importance of parameter w/y can be estimated by (36
"k,y
F(w, 7) - F(w, r; u; = 0) vs g(w)),
(10)
where F(w, wi = 0) is the loss function when w/y is masked and the approximation is obtained from the first Taylor expansion w/ 0. Therefore, if connected parameters were important, the sign of (TO) of those parameters will be negative, and the corresponding threshold will decrease as in (9). Otherwise, the threshold will be increased enforce sparsity. Hence, prematurely pruned parameters will be automatically recovered via a joint optimization of r and w.
3.3.3 Extracting Parameter Importance from Global Thresholds
Since thresholds represent the importance of the connected parameters at each filter/neuron, clients can learn how to prune their parameters from the global thresholds. Moreover, the difference between two consecutive global thresholds (t T(t + 1) rtt) captures the history of aggregated parameter importance, which can be further used to improve model performance. For instance, from (10), if (t < 0, then the parameters connected threshold in layer / were globally important. If (t) 0, then the connected parameters were globally less important. Hence, from At(t), clients can deduce which parameter is globally important or not and further update their model parameters. After generating new global thresholds 7 + 1), the server broadcasts T(t + 1) to client k S and then clients calculate AT(t) = r(t + 1) - (t)).
We then present how clients can update their model parameters from (r(.). For given Ar(t), we need to decide on the: 1) update direction and 2) update amount. Clients can know the update direction of parameters by considering (r(!) and the dominant sign of parameters connected to each threshold. For simplicity, assume that each parameter has a threshold. Then, the gradient the thresholds in can be rewritten as follows:
by (x)x((t)) g ( wxx())
(11)
The gradient of the loss F (t), T (t)) with respect to the whole parameters wy is given by
OF (wx T()) g. (
(12)
Ow
From 111 and 12 the gradient direction of parameter w is opposite of that of its connected threshold if w 0. Otherwise, both the threshold and the parameter have the same gradient direction.

---

Algorithm 1: SpaFL
Input:
Total number of clients N; Total communication rounds T; Local number of epochs E Output: Global thresholds T and personalized models zög
The server initializes (0) and (0)) and broadcasts them every client; do Server randomly samples St:
2 for t = 0 to
for Client & E S do
Receive 7(t + from the server and calculate (r(t); Update the current local model using (T with (I3
for
E 1 do
Update w 4 (t) < (f( (t) ((f)) w wx
Update Tx (t) + (t) hy (w (t)), (t) (t)
10
Transmit the updated threshold (t) the server
Generate global threshold 7 using 7
Hence, we can deduce the following: If w > O, the gradient direction of w and the sign of Ar will have the same sign; otherwise, the gradient direction of and the sign of At opposite. In SpaFL, each threshold has multiple connected parameters to its filter/neuron. As such, we decide the update direction of connected parameters by finding the dominant sign among them. To this end, simply add the connected parameters of each threshold. For instance, consider threshold in layer of client
k. if E/= wh Wy (t) > 0, then the gradient direction of the connected parameters will be the same as the sign of (t). Otherwise, it is the opposite of the sign of A (t). Thus, the update direction can be simply expressed with XOR operation between the sign of A (t) and the sign of connected parameters sum. Next, we decide how much a parameter should be updated. From (TT) and (I2). we can see that threshold and parameter have the same magnitude for their gradients. Hence, we simply divide (1) by the number of connected parameters n We finally provide the update equation using (t( as follows
+ (k T T
1 (1) XOR
sign
Σ Ewheesl whes(()) .sign(Ar((0))
(13)
where sign(-) is sign function. This parameter update corresponds line in Algorithm Note that this additional parameter update is not computationally intensive because it happens only once before local training. We also provide the number of used FLOPSs during training with inclusion of this operation in Section 5
4 Theoretical Analysis of SpaFL
We now present our generalization analysis of SpaFL. For the empirical risk R. 1 E> DDr Di=1 L(wxx 2;2;), we consider the expected risk R = E EL,,D, L(wū, 2 N k==
where C is loss function and 2 is an input-output pair. Suppose P is the ratio of remaining model parameters of client and f the average model density across clients. Then, for the hypothesis A(D) with global thresholds from Algorithm| on the joint training dataset DD = UN Dr. with we have the following generalization bound as follows:
Theorem 1. For the loss function || < 1, the training data size D > 2 In expl-c'oj and
the total number of communication rounds T, we have
P [((A()) - R(A(D)) < 96] > 1 expl
exp(-c')8'
2 In e
(14)
è'
7

---

where d' 27 log 2 +e
exp(t)+1I
c' [C)Te)
2TS 7
Té + c
- -(1
T
8' = exp
2
1 exp(E)
TE Tē-é- crā-e')
Tē -
- exp(E)
1 +
1&1
T-141
-1 11- (1-exp(() exp(((
+2
(1-1 1+ exp(e)
(15)
exp((()
0 v log 1/2 + p² M²
D D-
ē= log
+ exp
(16)
20
where & is the size of mini-batch, is the variance of Gaussian noise, and Mg is the maximum diameter of thresholds' gradients (TT). The proof and the definition of are provided in the Appendix 1.2 and (12), respectively.
From Theorem we can see that, as the average model density p decreases, the generalization bounds becomes smaller, thereby achieving better generalization performance. This is because e' and ? decrease as the average model density decreases. Hence, SpaFL can improve the generalization performance with sparse models by optimizing and sharing global thresholds.
Experiments
We now present experimental results to demonstrate the performance, computation costs and commu- nication efficiency of SpaFl.. Implementation details are provided in the Supplementary document.
5.1 Experiments Configuration
We conduct experiments on three image classification datasets: FMNIST (37 CIFAR-10, and CIFAR- 100 [38] datasets with NVIDA A100 GPUs To distribute datasets in a non-iid fashion,
we use Dirichlet (0.2) for FMNIST and Dirichlet (0.1) for CIFAR-I0 and CIFAR-100 datasets as done in 39 with N 100 clients. We set the total communication round T 500 and 1500 for FMNIST/CIFAR10 10 and CIFAR 100, respectively. At each round, we randomly sample K = 10 clients. Unless stated otherwise, we average all the results over at least 10 different random seeds. We also calculate the best accuracy by averaging each client's performance on its test dataset. For FMNIST dataset, we use the Lenet-5-Caffe For Lenet model, we set v7(1) 0.001, E a = 0.002, and batch size to be 64. For CIFAR-10 dataset, we use convolutional neural network (CNN) model with seven layers used in [40] with ry(t) = 0.01, E = 5, a = 0.00015, and a batch size of 16. We adopt the ResNet-18 18 model for CIFAR- 100 dataset with (t) 0.01, E 7, 0.0007, and batch size of 64. The learning rate of CIFAR- 100 is decayed by 0.993 at each communication round.
5.2 Baselines
We compare SpaFL with multiple state of the art baselines that studied sparse model structures in FL. In FedAvg [1. every client trains global dense model and communicates whole model parameters. FedPM (28) trains and communicates a binary mask while freezing model parameters. In HeteroFL 77. each client trains and communicates p-reduced models, which remove the last p output channels in each layer. In Fjord [9), each client randomly samples a model from a set of p-reduced models, which drops out p% of filter/neurons in each layer. FedP3 [T] communicates a subset of sparse layers that are pruned by the server for downlink and personalize the remaining layers. Clients only upload the updated remaining layers to the server. FedSpa trains personalized sparse models for clients while maintaining fixed model density during training. Local only performs local training with the introduced pruning method without any communications. For the sparse FL baselines, the average target sparsity is set to 0.5 following the configurations in [28
5.3 Main Results
In Table 2 and Fig. 2 we present the averaged accuracy, communication costs, number of FL.OPs during training, and convergence rate for each algorithm. We consider all uplink and downlink communications to calculate the communication cost of each algorithm. We also provide the details
8

---

FMNIST
CIFARIO
CIFAR100
Algorithms
Acc
Comm
FLOPs
Acc
Comm
FLOPs
Comm
FLOPs
(Gbit)
(e+11)
(Gbit)
(e+13)
(Gbit)
(e+14)
SpaFL
89.21
0.1856
2.3779
69.75.12.81
0,4537
1,4974
10.5010.54
4,6080
1.2894
FedAvg
88.73110.21
133.8
10.345
61.33110.15
258.36
12.382
35.51
10712
8.7289
FedPM
63.27.1. 1.65
66.554
5.8901
$2.05.1
133.19
7,0013
28.56 0.15
5506.1
5.423
HeteroFI.
85.97=00.00
68.88
5.1621
66.83-11115
129.178
6.1908
37.82-+0.15
5356.4
4,3634
Fjord
89.08+00.17
64.21
5.1311
66,38+2.01
128.638
6.1428
39.13+0.222
5251.4
4.1274
FedSpa
89.30:10.20
55.256
5.2510
67.03-00.63
129.31
4,2978
36.32+t0.35
5342.2
9.275
FedP3
89.12:10.14
41.327
5.8923
67.5410.55
67.345
6.8625
37.73+10.42
2682.6
4,9384
Local
84.31=00200
3.7982
57,06
0
1.9373
33.77=1.87
1.5384
Table 2: Performance SpaFL and other baselines along with their used communication costs (Comm) and computation (FLOPs) resources during whole training.
60-
70-
Accuracy [%)
SpaFt
550
SpaFL
SpaRL
Accuracy
00-
FedPM
FedAvg
Accuracy
FedPM
FedAug
Fed/vg
FcdPM
80
HeteroFl
HeteroFL
HateraFl
-0
Fjord
Fjord
Fjord
FedP3
FedP3
Fedp3
10
Fed5pa
10
FesSpa
Fed5pa
100
200
300
400
200
300
0
200
400
600
800
1000
1200 1400
Communicaton rounds
Communicaton rounds
Communicaton rounds
(a) Learning curve on FMNIST
(b) Learning curve on CIFAR-10
(c) Learning curve on CIFAR-100
Figure 2: Learning curves on FMNIST, CIFAR-10, 10, and CIFAR-100
Algorithm
FMNIST
CIFAR-
CIFAR- 100
SpaFL
89.21 0.25
69.75-2..81 38.9610.80 68.63
40.50
w.o. [3
88.20=1.10
Table Impact of extracting parameter importance from global thresholds
of the FLOPs measure in the Supplementary document. We average the model densities of SpaFL when model achieved the best accuracy during training. From these results, observe that SpaFL. outperforms all baselines while using the least amount of communication costs and number of FLOPs. The achieved model densities are 35, 35.36%, 30.57%. and 35.38%, for FMNIST, CIFAR- 10, and CIFAR-100, respectivcly. We also observe that SpaFL uses less resources and performs better than FedP3, HetroFL and Fjord, which deployed structured sparse models across clients. For FedP3, clients only upload subset of layers, but the server still needs to send the remaining layers. Although FedPM reduced uplink communication costs by communicating only binary masks, its downlink cost is the same as FedAvg. In SpaFL, since the clients and the server only exchange thresholds, we can significantly reduce the communication costs compared baselines that exchange the subset of model parameters such as HeteroFL and Fjord. Moreover, SpaFL significantly achieved better performance than Local, which did not communicate trained thresholds. Local achieved 51 31.2%, 50.1%. and 53.6% model densities for each dataset, respectively. We can see that communicating trained thresholds can make models sparser and achieve better performance. This also corroborates the analysis of Theorem I Hence, SpaFL can efficiently improve model performance with small computation and communication costs. In Fig. 2 we show the convergence rate cach algorithm. We can that the accuracy of SpaFL decreases and then keeps increasing. The initial accuracy drop from pruning while global thresholds are not trained enough. As thresholds keep being trained and communicated, clients learn how prune their model, thereby gradually improving the performance with less active filter/neurons.
We provide an empirical comparison between SpaFL, and the baseline that does not use the update in Section 3.3.3 in Table. We can see that the update (13) can provide a clear improvement compared to the baseline by extracting parameter importance from global thresholds.

---

Round 40
Round 150
Round 500
Conv Filter
Conv litter
Cliant
Client
Client
(a) Sparsity pattern at round 40
(b) Sparsity pattern at round 150
(c) Sparsity pattern at round 500
Figure Sparsity pattern of conv1 layer on CIFAR-10
Algorithm
Accuracy [%]
Density [%]
SpaFL. 69.78+22.62
42.2:t4.88
FedAvg
59.20=0.4
100
Table 4: Performance of SpaFL with the ViT architecture on CIFAR-10
In Fig- 3 we show the change of structured sparsity of the first convolutional layer with 64 filters with three input channels CIFAR-10. We color active filters black and pruned filters white. We can see that clients learn common sparse structures across training round. For instance, the 31th and 40th filters are all pruned round 40, Meanwhile, the 20th filter recovered rounds 150 and 500. We can know that SpaFL enables clients to learn optimized sparse model structures by optimizing thresholds. In SpaFL, pruned filter/neurons can be recovered by sharing thresholds. At round 40, filters are pruned with high sparsity. Since premature pruning damages the performance, most filters are recovered round 150. Then, clients gradually enforce more sparsity to filters along with training rounds as shown in Fig. 3c
In Tab. we show the performance of SpaFl. vision transformer using the VIT 42
CIFAR-10 dataset. We used the same data distribution as done in Tab. _ We apply our pruning scheme to multiheads attention layers. Since multiheads attention layer essentially consists of stacked linear layers, we can simply use ([). thereby making sparse attention. We can see that SpaFL can be applied transformer architectures by achieving the density of around 42% while outperforming FedAvg.
Conclusion
In this paper, we have developed a communication--fficieee FL. framework SpaFL that allows clients to optimize sparse model structures with low computing costs. We have reduced computational overhead by performing structured pruning through trainable thresholds. To optimize the pruning process, we have communicated only thresholds between clients and a server. We have also presented the parameter update method that can extract parameter importance from global thresholds. Furthermore, we have provided thcoretical insights on the generalization performance of SpaFL.
Limitations and Broader Impact One limitation of SpaFL is that it cannot explicitly control the sparsity of clients. Since we enforce sparsity through the regularizer term, we need to run multiple experiments to find values for desired sparsity. Another limitation is that our analysis requires bounded loss function. Meanwhile, in practice, most loss functions may admit bounds that have a large value. For broader impact, SpaFL can reduce not only the computation and communication costs of FL training, but also those of inference phase due to sparsity. Hence, in general, SpaFL can improve the sustainability of Fl. deployments, and more broadly, of AI.
10

---

References
[1] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. communication-efficcnee learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282, PMLR, 2017.
[2] Sunwoo Lee, Anit Kumar Sahu, Chaoyang He, and Salman Avestimehr. Partial model averaging in federated learning: Performance guarantees and benefits. arXiv e-prints, pages arXiv-2201, 2023.
[3] Pretom Roy Ovi, Emon Dey, Nirmalya Roy, and Aryya Gangopadhyay, Mixed quantization enabled federated learning to tackle gradient inversion attacks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages
2023.
[4] Tiansheng Huang, Shiwei Liu, Li Shen, Fengxiang He, Weiwei Lin, and Dacheng Tao. Achiev- ing personalized federated learning with sparse local models. arXiv preprint arXiv:2201.11380, 2022.
[5] Xiaofeng Liu, Yinchuan Li, Qing Wang. Xu Zhang, Yunfeng Shao, and Yanhui Geng. Sparse personalized federated learning. IEEE Transactions on Neural Networks and Learning Systems, 2023.
[6] Dongping Liao, Xitong Gao, Yiren Zhao, and Cheng-Zhong Xu. Adaptive channel sparsity for federated learning under system heterogeneity. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 20432-20441, 2023.
[7] Enmao Diao, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication ef- ficient federated learning for heterogencous clients. International Conference on Learning Representations, 2021.
[8] Kai Yi, Nidham Gazagnadou, Peter Richtárik, and Lingjuan Lyu. Fedp3: Federated per- sonalized and privacy-frienee network pruning under model heterogeneity. arXiv preprint arXiv:2404.0 09816, 2024.
[9] Samuel Horvath, Stefanos Laskaridis, Mario Almeida, Ilias Lcontiadis, Stylianos Venieris, and Nicholas Lane. Fjord: Fair and accurate federated learning under heterogeneous targets with ordered dropout. Advances in Neural Information Processing Systems, 34: 1887--128,,,, 2021.
[10] Tachyeon Kim and Se- Young Yun. Supernet training for federated image classification under system heterogeneity. arXiv preprint arXiv:2206.00 01666 2022.
[11] Mi Luo, Fei Chen, Zhenguo Li, and Jiashi Feng. Architecture personalization in resource- constrained federated learning. In NeurlPS Workshop on New Frontiers in Federated Learning, 2021.
[12] Won Joon Yun, Yunscok Kwak, Hankyul Back, Soyi Jung, Mingyue Ji, Mehdi Bennis, Jihong Park, and Joongheon Kim. Slimff: Federated learning with superposition coding over slimmable neural networks. IEEE/ACM Transactions Networking, 2023.
[13] Zhenheng Tang, Shaohuai Shi, Wei Wang, Bo Li, and Xiaowen Chu. Communicaaion-effiiienn distributed deep learning: A comprehensive survey. arXiv preprint arXiv:2003.06300 2020.
[14] Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg. Tim Verbelen, and Jan S Rellermeyer. A survey on distributed machine learning. Acm computing surveys, 53(2): 1-33, 2020.
[15] Wenke Huang, Mang Ye, Zekun Shi, Guancheng Wan, He Li, Bo Du, and Qiang Yang. Federated learning for generalization, robustness, fairness: A survey and benchmark. arXiv preprint D:Xiv:23/1.0675: 2023.
[16] Qinbin Li, Zeyi Wen, Zhaomin Wu, Sixu Hu, Naibo Wang, Yuan Li, Xu Liu, and Bingsheng He. survey on federated learning systems: Vision, hype and reality for data privacy and protection. IEEE Transactions on Knowledge and Data Engineering, 35(4):3347-336 2021.
11

---

[17] Sameer Bibikar. Haris Vikalo, Zhangyang Wang. and Xiaohan Chen. Federated dynamic sparse training: Computing less, communicating less, yet learning better. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6080-6088, 2022.
[18] 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. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[19] Ang Li, Jingwei Sun, Binghui Wang. Lin Duan, Sicheng Li, Yiran Chen, and Hai Li. fotteryfl: empower edge intelligence with personalized and communication-effiice federated learning. In 2021 IEEE/ACM Symposium on Edge Computing (SEC), pages 68-79. IEEE, 2021.
[20] Xinchi Qiu, Javier Brmmandez-Marquee Pedro PB Gusmao, Yan Gao, Titouan Parcollet, and Nicholas Donald Lane. Zerofl: Efficient on-device training for federated learning with local sparsity, arXiv preprint arXiv:2208. 02507, 2022.
[21] Ang Li. Jingwei Sun, Pengcheng Li, Yu Pu, Hai Li, and Yiran Chen. Hermes: an efficient federated learning framework for heterogeneous mobile clients. In Proceedings of the 27th Annual International Conference on Mobile Computing and Networking, pages 420-437, 2021.
[22] Vaikkunth Mugunthan, Eric Lin, Vignesh Gokul, Christian Lau, Lalana Kagal, and Steve Pieper. Fedltn: Federated learning for sparse and personalized lottery ticket networks. In Computer Vision-ECCV 2022: 17th European Conference. pages 69 80- Springer, 2022.
[23] Rong Dai, Li Shen, Fengxiang He, Xinmei Tian, and Dacheng Tao. Dispft: Towards communication-effiieee personalized federated learning via decentralized sparse training. In International Conference on Machine Learning, pages 4587-4604. PMLR, 2022.
[24] Sara Babakniya, Souvik Kundu, Sauray Prakash, Yue Niu, and Salman Avestimehr. Revisiting sparsity hunting in federated learning: Why does sparsity consensus matter? Transactions on Machine Learning Research, 2023.
[25] Dimitris Stripelis, Umang Gupta, Greg Ver Steeg, and Jose Luis Ambite. Federated progressive sparsification (purge-merge-tuney) In Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurIPS, 2022.
[26] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv:1803.0363: 2018.
[27] Ang Li, Jingwei Sun, Xiao Zeng, Mi Zhang, Hai Li, and Yiran Chen. Fedmask: Joint computa- tion and commanicationn-efiiiee personalized federated learning via heterogeneous masking. In Proceedings of the 19th ACM Conference on Embedded Networked Sensor Systems, pages 42-55, 2021
[28] Berivan Isik, Francesco Pase, Deniz Gunduz, Tsachy Weissman, and Michele Zorzi. Sparse ran- dom networks for communication--ffciientttt federated learning. arXiv preprint a5X35 2022.
[29] Erum Mushtaq, Chaoyang He, Jie Ding, and Salman Avestimehr. Spider: Searching personalized neural architecture for federated learning. arXiv preprint vrXiv:2112.13993 2021.
[30] Minh Tri Lé, Pierre Wolinski. and Julyan Arbel. Efficient neural networks for tiny machine learning: A comprehensive review. arXiv preprint arXiv:2311.11883, 2023.
[31] Junjie Liu, Zhe Xu, Runbin Shi, Ray CC Cheung, and Hayden KH So. Dynamic sparse training: Find efficient sparse network from scratch with trainable masked layers. arXiv preprint arXiv:2005.0633 066700 2020.
[32] Xiao Zhou, Weizhong Zhang, Zonghao Chen, Shizhe Diao, and Tong Zhang. Efficient neural network training via forward and backward propagation sparsification. Advances in neural information processing systems, 34:15216-1522 2021.
[33] Amirkeivan Mohtashami, Martin Jaggi, and Sebastian Stich. Masked training of neural networks with partial gradients. In International Conference on Artificial Intelligence and Statistics, pages 5876-5890. PMLR, 2022.
12

---

[34] Lu Yin. Gen Li, Meng Fang, Li Shen, Tianjin Huang, Zhangyang Wang, Vlado Menkovski, Xiaolong Ma. Mykola Pechenizkiy, Shiwei Liu, et al. Dynamic sparsity is channel-level sparsity learner. Advances in Neural Information Processing Systems, 36, 2023.
[35] Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley Osher, Yingyong Qi, and Jack Xin. Understanding straight-through estimator in training activation quantized neural nets. arXiv preprint arXiv:1903.0566 2019.
[36] Pavlo Molchanov, Arun Mallya, Stephen Tyree, luri Frosio, and Jan Kautz. Importance estimation for neural network pruning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11264-11272, 2019.
[37] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint axXiv:108.007455 2017.
(38) Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[39] Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint
2019.
[40] Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. Advances in neural information processing systems, 32, 2019.
[41] Kai Yi, Nidham Gazagnadou, Peter Richtárik, and Lingjuan Lyu. Fedp3: Federated personalized and privacy-friendy network pruning under model heterogeneity. The Twelfth International Conference on Learning Representations.
[42] Alexey Dosovitskiy. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 11929, 2020.
[43] Fengxiang He, Bohan Wang, and Dacheng Tao. Tighter generalization bounds for iterative differentially private learning algorithms. In Uncertainty in Artificial Intelligence, pages 802- 812. PMLR, 2021.
[44] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint 18X1v:1907.02119, 2019.
[45] Atilim Gunes Baydin, Barak A Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in machine learning; survey. Journal of machine learning research, 18(153):1 2018.
13

---

A Experiments
A.1 Implementation Detail
We run all experiments on NVIDIA A10 GPUs with PyTorch. In Table 6 we provide detailed information of model architectures for each dataset. For the FMNIST dataset, we use the Lenet-5- Caffe model, which is Caffe variant of Lenet-5. The Lenet model has 430500 of model parameters and 580 of trainable thresholds. For the CIFAR- 10 dataset, we use CNN model of seven layers used in [40]. It has 807366 of model parameters and 1418 of trainable thresholds. The ResNet- 18 model is adopted for the CIFAR-100 dataset with 11 11159232 of model parameters and 4800 of thresholds. We use a stochastic gradient optimizer with momentum 0.9. For FMNIST with the Lenet model, we use 7)(() 0.001. E 5. batch size of 64, and 0.002. For CIFAR-10, we use 17(1) = 0.01, E = 5, a batch size of 16, and a = 0.00015. For CIFAR-100, we use r7()) = 0.01, E = decayed by 0.993 at each communication round, batch size of 64, and 0.0007. All trainable thresholds are initialized to zero. We noticed that too large sparsity coefficient a can dominate the training loss, resulting in masking whole parameters in a certain layer. Following the implementation of [31,, if certain layer's s density becomes less than 1%, the corresponding trainable thresholds will be reset to zero to avoid masking whole parameters.
For the ViT, we use the patch size 4, embedding dimension of 128, depth of 6, heads, and set the dimension of linear layers as 256. We use the same setting with the above CIFAR-10 experiments except a = 0.0001 and
FMNIST
CIFAR-10
CIFAR-100
(3,3, out 32, stride 1)
(5. 5, out 64, stride = 1)
(3,3, out = stride x)
(5, 5, out = 20, stride = 1) Maxpool2d
(5, 5, out 64, stride = I)
(3,3, out 32, stride x2
Maxpool2d
Conv
(3,3, out = 64, stride =)
(5, 5, out = 50, stride = I)
(5, 5, out = 128 stride I)
(3,3, out 64, stride 1)
Maxpool2d
5, out 128, stride 1)
(3, 3, out 128, stride =
Maxpool2d
(3, out 128, stride 1) x3
(512. 128)
(800, 500) (500, 10)
FC
(128, 128)
(256, 100)
(128, 100)
Table 6: Model architectures used in our experiments
A.1.1 More details about baselines
We compare SpaFL with sparse baselines that investigated structured sparsity. In FedAvg [1. every client trains global dense model and communicates whole model parameters. We used the equal weighted average for the model aggregation. FedPM (28) optimizes a binary mask while freezing model parameters. Clients only transmit their arithmetically coded binary masks the server, and the server broadcasts real-valued probability masks to the clients. We use Adam optimizer with learning rate of 0.1 as done in 22 HeteroFL. 7 selects [pC] channels of each layer, where <<> 1 and C is the number of channels, to make p reduced submodels. Clients train and communicate reduced submodels during training. We set p 0.5 following 7 Fjord
samples p from a uniform distribution U (Pmin Pmax). After sampling p. clients train p reduced submodel by selecting the first [pC1] channels of each layer. We set Pain 0.4 and Pmax 0.6 D We provide the learning rates of the baselines in the following table. FedP3 [1] communicates subset of sparse layers that are pruned by the server for downlink and personalize the remaining layers. Clients only upload the updated remaining layers to the server. We choose 'OPU2' method, which uniformly selects two layers for clients from the entire network. Hence, clients only upload these chosen layers to the server. For the pruning methods, we adopted the ordered dropout for structured sparsity. FedSpa 4 trains personalized sparse models for clients while maintaining fixed model density during training. The initial pruning rate is set to be 0.5 and decayed using cosine annealing.
14

---

Algorithm
FMNIST
CIFAR-10
CIFAR-100
FedAvg
m(t) = 0.001
n(t] 0.01
7(t) = 0.1
FedPM
T1(1) = 0.15
7(()) 0.1
7(1) 0.1
HeteroFL
v(t) = 0.001
v]() = 0.005
7(() = 0.01
Fjord
T7(1) = 0.01
7(1) 0.01
7(() 0.01
FedP3
TT(() = 0.01
7(() 0.01
7(() 0.01
FedSpa
7( = 0.001
7()) 0.01
7(t) 0.1
Local
nlt) = 0.001
ntt 0.01
7(t) 0.01
Table 7: learning rates used by the baselines
A.2 Proof of Theorem
We next present the detailed proof of Theorem 1. The proof inspired by (23 and 43 To facilitate the proof, we first provide the definition of differential privacy and key lemmas from 43
Definition 1. (Differential privacy). A hypothesis A is (e, 6)- differentially private for any hypothesis subset Ao and adjacent datasets S and S' which differ by only one example such that
P PA(S) (A(S) E Ao) Ab)
log
(A(S)) E Ao) { S.
(17)
Lemma 1. (Theorem 4 in (43)) For an iterative algorithm A; at round i, define the update rule as follows:
Mr (Ai-1(8),))- Ai(S)-
(18)
If for any fixed Ai-1, M; is (G,, 8) private, then {Ai) is (c,8') differntially private such that exp(e;)-1
d= 2 Et log Σ 4 exp(re)+1
- Te +
Te
+ (1+ exp(c)
2Te
- 1
8' = exp (--2
1
Tc c
Te
1$1
T-
+ (1-
(1-
(19)
Txex)(e)
( exp(e)
Lemma (Theorem (431) For an (c,8) private hypothesis A, the training dataset size exp(-e]o' and the loss function ||[|| < 1, we have
s
2 In
16
27
P P[[R(ACD)) -
R(A(D)) < 96 >1 exp(-e))
In 2 C
(20)
Proof. The overall proof follows 23
by showing that SpaFL is iterative machine learning
algorithm that satisfies differential privacy at each round. Then, we can use lemmas from [43] that provide generalization bound differential private algorithm. One major difference from 23 is that
we have global thresholds not global parameters.
We first define notations for the proof. The diameter of the gradient space is defined as Mg max I|VFFWw T; - T; ll) where z an input-output pair. We also denote G [ E.es hy (ū =) as the average h2 (mñx)) over B3 We use probability distribution and TP as the probability distribution conditioned on A.
From Algorithm 1, it is clear that SpaFL is iteratively optimizing global thresholds in each client at every round. We now derive the differential privacy of (9) in Algorithm 1. Here, each client calculates h4 using its subset of local data. As done in (23). we assume that additive Gaussian noise sample added in (9) Algorithm for the analysis. Since we always have global thresholds at round I,
(9) can be seen sampling mini-batch [(t) from D Up with mini-batch size & and we let
15

---

(tt) ST(() Then, for fixed (t 1) and two adjacent sample sets S and S", we have
pezzc0 (r(t) = [| 1)) psam (17(t 1)Gsz " +N(0, - + ( 1))
(21)
psz (T(t)= = (( 1)) 1 (n1( 1 1)0s 2(e-1) + N((, = - + 7(1 1))
where =(1) - T(l - 1) - n1(1 (G + (O o)1)) and Gzzge-)) = N E GR. (t,
We define 1)(t - 1)T' = T(t 1t (() (t 1)G Sz then we can rewrite (1 as below
P (N)
= =+)
(A) = p 1 (G 1) - Gs +
(22)
o²1l +2(0 +')
+ (0, o²l)) due to added Gaussian noise samples, T' ~ 22). Then, following the definition of differential privacy, define
Since T T(t 1) nl( () 1)
S (pSI)) (W(0,021) =')
Dy(T') = log
I (Gs) 2(1-1) - -Srran) +.N(0,021) = T')
1
|| -GS2(11 G 1
(23)
20
20²
2(T', Gsza- Gz + +1[Gs1(e-1)
G Gz
(24)
20
where 23 is from the definition of Gaussian distribution. We now denote Gsza-1) - G 21 in
24 as v. We derive the bound of ||aa| as follows
N Σ
||a|| = [|Gszu-n
G. Zu 1y
|| = 11 N
GK,Sqq(-1
-Gk,st
k=1
1
Gk Ck.st (-1)
N
1
Σ
he(wx(t 1);2)
1
hx 1): 2|1l
N
Sz(e-1)l
( xES
=ES2(1-1)
(25)
N
1
<
N ph Mg MM
(26)
where 25 is from the definition of G and (26) is from the definition of the diameter of gradient Mg. Note that some elements of (wx; 2) will be zero since we do not calculate gradients of pruned filter/neurons due to structured sparsity. Hence, multiply the current model density to derive (26).
We next bound (T', in (4 Since (T', v) -N ||u|||2)), using Chernoff Bound as
we have the following inequality
P (T',)) u) 2 /2l0oo o log 1/5 S minexp 2ar///////// log 1/0E(exp(x((' ,i))). (27)
We define 5 as follows
min exp (-V2a log L/ u))l)
(28)
Then, with the probability of 1 - 8 with respect to T', we can derive the bound of 24 as follows
V2pM. log 1/5 M²
Dp(T's 5
(29)
202
16

---

Following Lemma 1 and (13) in [23]. we can derive that each round in Algorithm 1 is (2, 56) differntially private, where is given as
v2pM,0 / log 3/4 + p2
D E D
+ 5 exp D
ē= log
(30)
20²
where Ç is the size of Sz(r-1-- Subsequently, we apply Lemma 1 to have (c', 8*) differential privacy for T communication rounds. Lastly, we finish the proof by using Lemma 2
A.3 Convergence Rate Analysis
We derive the convergence rate of SpaFL. Since we only communicate thresholds т, we derive the convergence rate of the global thresholds. In SpaFL, we simultancously update T and w, and is analytically challenging to track the update of T for multiple local epochs E. As such, we analyze the convergence of SpaFL under the special case with E = 1. We leave more general convergence analysis with multiple local epochs for future works. We now make two assumptions 44 as follows
Assumption 1. (smoothness) Fi(.) M-smooth for and client k; Wk
M 1| - VT. 2
Fu T') (u( + (V,Fe(w, -)) -'
(31)
Assumption 2. (Unbiased stochastic gradient) The stochastic gradient h2 is unbiased estimator of the gradient Fkk,, respectively, for client k. Yk, such that
Ehg(ww) F (wk: T).
(32)
Then, we have the following convergence rate
Theorem For (t) (ft a(1 (1I-M((t)))))) and the largest number of parameters connected to neuron or filter mmax > 0 in given model, we have
2
Fl (()
Σ E Σ
(()))
NT
MNTr(t)
1=
1= km
T
2am(t)
(1 (1n) (xxppp--))()
Ty(t)
T-1
Men(())mmm max
(t))
NTy(t)
E B - (x))]
(33)
NT
From (9) thresholds (t) are updated using parameter gradients (t), & E S. We can expect that the thresholds will converge when parameters Ws, Vk, converge. We can see that the sparsity regularizer coefficient impacts convergence. As increases, we can quickly enforce more sparsity to the model. However, a very large will damage the performance as 7(1) decreases in ( We can also observed that the convergence depends on the difference between the received global thresholds Ttt) and the updated thresholds T (t). Hence, a very large change to the global thresholds will lead to significantly different binary mask in the next round. Then, local training be unstable as parameters have to adapt to the new mask. Therefore, from Theorem we can capture the tradeoff between the computing cost and the learning performance in terms a.
Proof. We first consider the case in which global thresholds converge. We have the following update rule for global thresholds as
(t +
Σ (t))) = (t)) K" (tt)
Σ hx (t) + an(t) exp(-T(())) (()).
(34)
K
KES
kes
17

---

We take the expectation over the randomness in client scheduling and stochastic gradients as follows
ET(++1)= =(() - n((),
E
he (t) + an(t) exp((r(())
K
RES
70t) N
=t)
E
(z ( + ann(t) exp(-((()) V
(35)
Hence, clearly will eventually converge if N show that this conditional statement holds in our SpaFL framework.
k=1 (l) (9, converges. We next
From the M-smoothness of the loss function in Assumption
we have
M [T) (t)]
(36)
To facilitate the analysis, we first derive (t( - (t) below
Tx (1) (()) (1))(((((()(()))))))))) + (x0)x))))))
(37)
Then, we can change (36) as follows
Fi( (t) S (
+ (())))(((
Mn(()²
|| (1xx an)()) exp(-r
(38)
2
We next take the expectation to the above inequality and use Assumption 2 as below
E& (F 7001://000000000000/////00000000
< IE
+
Mn(t)² (
2
EF -(t) (000))1))))--011177-000000000000
+ am(t)(1 (ttt)///---kkku..t/rt//e)e------
A
Mn(()²
Ma²n(1)²
B (1x (1))1
|exp(- |exp(-=(())))_
(39)
2
2
||a|1++1011 as below
We first bound A using (a, b) <
AS (n))) Mm)(t)
(40)
We now further bound B as
n
Mn(()²
B
E
gn (o (1))),
2
Mn
(t)) lg (t)) E-1 (0)
2
1=1
1=1
Mn
( max
n
Pin
MM. (1h (0)
2
1=1
2
E
ΣΣΣ
(
2
Mn(t))n
m max in
E g (Tx (t)iI
M (t))tt)2n))) max Fx (())), F
(41)
2
18

---

where mi is the largest number of parameters connected to a neuron or filter in a given model, (a) is from |w < 1 in Section 3.2.1, and the last inequality is from the Mssmoothness of Fg. By combining A and B with taking expectation, we have
(t)) < EF, ( (tt) 1 a(1 161--MN
a(1-MMn(t)) Mn(())
2
an(t) (MM()))-nn()((1-00 /eeppp eex((=T(t))l= +M² (tt) EFF T (t))
(42)
By arranging the above inequality, we have
1
(1. <
(F((((n(t), - (t) (())
7(1)
(A)
(n)(t)
M (t) max
+
{1 Mm(()(1 ||pp
EF (()),
7t)
7t))
(43)
where (() = (1)((1
a(1 Mo(t))
2
We now further bound (A) in 43 From Assumption 1
we
have the following
(A) (1),
+x(())
2M V [ V (1),
(t)
V Fl
26
(t))) 27(() [IT (1
V Fv 1x (t)) V (t))
(44)
2M
Based on 44 we can bound (43 below
||V (())
( (+))11
My(t)
2am((t) (1 -
2M (t)) max
+ 7(t)
EF&
T())
7()
|T - (t)l
(45)
7(1)2
From 45
we can bound the averaged aggregated gradients with respect to thresholds as below
v (()))
<
E ()V
N
B (V (10
NM
20z7(t)
{1 Mn(() (1 (|xp(pT())]
7(t)
max
E El( - (t)11
EF +(1) +
N
7(t)
N
7t)2
(46)
By summing the above inequality from / = 0 to T - 1, we can obtain the result of Theorem 2
Based on Theorem 2 we can derive the convergence rate with the Big-O notation by following the
steps in 8 We first assume 11/ 1/VT and ( S < 1. Then, we can bound 70
w0[1-o)
2
By
19

---

replacing rt() and yt)) with their assumed value and bound into the above convergence rate, we have the following bound
0
A
0
-
B
-
-
C VT
+
D
(47)
VT(1 a)
T(1 -
VT
where A = ET-11 Ek=1 k=1
E| V.FFA(00(())((0)-- (1E
B = Et= dail exp(-r(())11
MN
C = M2 maz /²/2, and D = Ei= k=
(011
N
A.4
Communication Costs Measure
We calculate the communication cost of SpaFL, considering both uplink and downlink communica- tions. At each round t, sampled clients transmit their updated thresholds the server. Hence, the uplink communication costs can be given by
Commup = K x 7rum X 32 [bits],
(48)
where Trum is the number of thresholds of given model. In downlink, the server broadcasts the updated global threshold to sampled clients, Hence, the downlink communication costs can be given below
Commaown K Tumm 32 [bits].
(49)
Therefore, total communication costs can be given by (Commup + Commoowa).
A.5 FLOPs Measure
We calculate the number of FLOPs during training using the framework introduced in [32]. We consider convolutional layer with input tensor X E XxCXXXX parameter tensor W e RxCxxxx5 and output tensor O E Nx Here, the input tensor X consists of number of samples, each of which has X x Y dimension. The parameter tensor W has F filters of C channels with kernel size R x S. The output tensor O will have output channels with dimension x W for N samples. During forward propagation, a filter in W performs convolution operation with the input tensor X to produce a single value in the output tensor O. Hence, we can approximate the sparse model during forward
number of FLOPs N x (C R S) x F x H W. Since propagation, the number of FLOPs can be reduced to x N x (C x R x S) x F x H X W, where is the density of the parameter matrix W. For the backpropagation, times of that of forward propagation following 455
p |[Wllo
|Pllo
calculate
For fully connected layer with input tensor X E NxX and parameter tensor W E XxY the input tensor X is multiplied with W during the forward propagation. Hence, with the density of W. we can calculate the number of FLOPs for the forward propagation as x N x x In backpropagation,
follow the same process for convolutional layers.
We also consider the number of FLOPs to perform line 6 Algorithm 1 for updating the local models from global thresholds. Sampled clients first have to decide update directions by doing summation of connected parameters at each neuron/filter (sum operation). Then, they update their local models using the received global thresholds (sum and multiply operations). This corresponds to 1.5 x d FLOPs, where d is the number of model parameters. Then, the total number of FLOPs during one local epoch at round t can be approximately given by
FLOP(() = Σ 3N x (Cr x R x St) x Fr x H1 x W x 1 (layer == conv)
E=
X3xNxX x Y x flaaerr = fc} + 1.5d
(50)
B Change of sparsity patterns CIFAR-10
Here, present the change of sparsity patterns of different layers CIFAR-10.
20

---

Round
Figure 4: Sparsity patterns of conv2 layer CIAFR-10
Centae Filter
50
63
220-
Client
Figure 5: Sparsity patterns of densel layer on CIAFR-10
0ir=011
D.5
Dir: 1.0
Fiteer
Conv Fiteer
Fitee
Client
Client
Client
Figure 6: Sparsity patterns of conv1 layer on CIAFR-10
B.1
Change of Model Sparsity patterns in conv2
B.2
Change of Model Sparsity patterns densel
From Figs. and 5 we can observe that clients learn common sparsity patterns across layers by communicating thresholds.
B.3
Change of Model Sparsity patterns with different data heterogeneity
From Fig. we can see that as the data heterogenity decreases, clients share more similar sparsity patterns across their filters.
21

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA] is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, so please just use your best judgment and write a justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
22

---

The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specing well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tes system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess..
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
23

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
public/guides//odeeeee ion.ooiccy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines tht
/niis.cccppbliic gww.://guiis.se..u CodeeSmmeiiiaeccc SinSSuuubiiiiie ssi on Policyy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
24

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma eгrоr bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
25

---

Question: Does the research conducted in the paper conform, in every respect. with the NeurIPS Code of Ethics ht otinai/hths/////arrrr.ccooo//p/a
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [Yes] NA
Justification: We do not include pretraiend language models or image generators.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
26

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. www. con/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
we do not have crowdsourcing experiments.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
27

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
We do not have human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "S8KKN9XqDu", "reviewer": "Reviewer_28Jj", "summary": "This paper suggests communicating the threshold instead of the model parameters in federated learning. Through empirical validations on popular benchmarks, the proposed method, SpaFL, is shown to have lower computational overhead and achieve relatively good results.", "questions": "I would expect a README file to better understand your code efficiently.", "limitations": "The major limitations include the unclear presentation of the proposed method, lack of analysis of the generalization bound, absence of convergence and communication efficiency analysis, and the use of outdated empirical baselines.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "Communicating the threshold instead of the model weights seems to be interesting. Preliminary empirical results on popular benchmarks seem to have shown that this idea works with lower communication overhead and relatively good performance.", "weaknesses": "1. The main figure, Figure 1, is not informative and very confusing. I would expect to see a high-level explanation of how the threshold for each client is selected, whether they are the same for each layer, and how the selected thresholds are combined. At this moment, I can only see that all local models have the same threshold and they are directly combined at the server. Due to the misalignment between the main figure and the illustration in section 3.1, the necessary details to fully understand the main idea of this paper are not easy to follow. The writing in this section could also be improved.\n\n2. In Theorem 1, the authors provided a generalization bound. However, the intuition and analysis for this bound are missing. At this moment, I do not have a good sense of, in a practical or special case, how large the right-hand side probability of Equation 14 is? How large must the minimal training data size $D$ be? Is it practical? Also, this bound only measures the distance between the empirical risk and the expected risk; how can this be regarded as a generalization bound? To my understanding, a generalization bound should be between the training set and the testing set. Furthermore, could you please provide the convergence rate and communication complexity of the proposed method? These are very important for the theoretical analysis of FL.\n\n3. The baselines are outdated, such as Fjord (NeurIPS21) and HeteroFL (ICLR21). Can you please compare more recent methods, which can be easily found, such as [FedPAC](https://arxiv.org/abs/2306.11867) and [FedCR](https://proceedings.mlr.press/v202/zhang23w.html)? I would expect to see more comparisons with newer methods. They do not need to be the ones mentioned above, but I believe it is critical to determine whether the proposed method is still interesting to explore at this moment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive comments. We provide our response to each comment below.\n>Q1: I would expect to see a high-level explanation of how the threshold for each client is selected, whether they are the same for each layer, and how the selected thresholds are combined.\n\n**A1:**  In SpaFL, all thresholds are initialized to zero. Each threshold will be updated by (6) during the training. As such, each threshold will have different value. We averaged selected thresholds to generate global thresholds for the next round as shown in (7). We will clarify Figure. 1 and Section 3.1. \n\n>Q2: This bound only measures the distance between the empirical risk and the expected risk; how can this be regarded as a generalization bound? To my understanding, a generalization bound should be between the training set and the testing set.\n\n**A2:** It is our understanding that the generalization bound is the difference between empirical and expected risks as shown in [1, 2]. \n\n>Q3:  Is it practical?  how large the right-hand side probability of Equation 14 is? How large must the minimal training data size D be?\n\n**A3**: Theorem 1 can provide a probabilistic guarantee with a certain amounts of data and communication rounds under the assumption of the bounded loss function, As shown in the result and the proof, the result depends on theoretical values such as $(\\epsilon, \\delta)$ differential privacy, gaussian noise $\\sigma$ and the maximum diameter of gradient space $M_g$, To calculate the right-hand side probability of (14), we first assume $\\epsilon =4, \\delta = 1/10^6$, $\\sigma = 2$, and $M\\_g =1$ from [1, 2]. We also assume mini-batch size $\\xi=64$ and do $T=500$ communication rounds with $\\rho = 0.5$ average model density. Then, we can obtain the right-hand side probability as 0.61 for bound the generalization error around as 0.25, and the minimum required training sample $D$ is around 10000. \n\n>Q4: Furthermore, could you please provide the convergence rate and communication complexity of the proposed method?\n\n**A4**: We provided the training curve in Figure 2. We can see that the proposed approach shows relatively faster convergence rate compared to the baselines, \n\n>Q5: The baselines are outdated, such as Fjord (NeurIPS21) and HeteroFL (ICLR21). Can you please compare more recent methods, which can be easily found, such as FedPAC and FedCR? I would expect to see more comparisons with newer methods. They do not need to be the ones mentioned above, but I believe it is critical to determine whether the proposed method is still interesting to explore at this moment.\n\n**A5**: We compare SpaFL with two more baselines: FedP3 [5] and FedSpa [6]. Specifically, FedP3 communicates a subset of sparse layers that are pruned by the server and personalize the remaining layers. FedSpa trains a personalized sparse models while fixing the model density during the training, For FedP3, we set global pruning ratio as 0.5 and use OPU2 method (overlaps two layers) as done in [5]. We use the same data distribution and model architecture as done in our experiment, For CIFAR-10, we set the learning rate as 0.01. For CIFAR-100, we set the learning rate as 0.1 and decayed it by 0.997 for each communication round, We set the initial pruning ratio of FedSpa as 0.5 with cosine annealing as done in [6]. We set the learning rate as 0.01 and 0.1 for CIFAR-10 and CIFAR-100, respectively. \n\n|Algorithm | Accuracy (CIFAR-10) | Accuracy (CIFAR-100)|\n| --- | --- | ---|\n| SpaFL  | $\\mathbf{69.75 \\pm 2.81}$ |$\\mathbf{40.80 \\pm 0.54}$|\n|FedP3 | $67.54 \\pm 0.52$ | $37.73 \\pm 0.42$|\n| FedSpa   | $67.03 \\pm 0.63$ | $36.32 \\pm 0.35$|\n\n\n\n**References**\n\n[1] Dupuis, Benjamin, George Deligiannidis, and Umut Simsekli. \"Generalization bounds using data-dependent fractal dimensions.\" International Conference on Machine Learning, 2023.\n\n[2] Chu, Yifeng, and Maxim Raginsky. \"A unified framework for information-theoretic generalization bounds.\" Advances in Neural Information Processing Systems 36 (2023): 79260-79278.\n\n[3] Abadi, Martin, et al. \"Deep learning with differential privacy.\" Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 2016.\n\n[4] Balle, Borja, Gilles Barthe, and Marco Gaboardi. \"Privacy amplification by subsampling: Tight analyses via couplings and divergences.\" Advances in neural information processing systems 31 (2018).\n\n[5] Yi, Kai, et al. \"FedP3: Federated Personalized and Privacy-friendly Network Pruning under Model Heterogeneity.\" The Twelfth International Conference on Learning Representations, 2024\n\n[6] Huang, Tiansheng, et al. \"Achieving personalized federated learning with sparse local models.\" arXiv preprint arXiv:2201.11380 (2022).", "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": "", "extra_scores": {}}, {"review_id": "uuJWsEPFhv", "reviewer": "Reviewer_qu5D", "summary": "This paper introduces SpaFL, a federated learning framework that enhances communication efficiency and minimizes computational overhead by optimizing sparse model structures. They achieve this goal by defining a trainable threshold which leads to structured sparsity. Since the server and clients only exchange thresholds, SpaFL is able to reduce communication overhead. Furthermore, these trainable thresholds also lead to low computing costs.", "questions": "1. If you apply this method to the transformer based models, how can you define trainable thresholds? To be specific, you gave an explanation for a convolutional layer in section 3.1, and can we just similarly define for self attention modules?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is generally well-written and easy to follow\n\n2. The idea of using trainable thresholds is new and effective for achieving both communication efficiency and low computational overhead.\n\n3. They perform valid experiments with the baseline methods and some image datasets. The accuracy performance of their method is better than others.", "weaknesses": "1. I recommend the authors to do additional experiments with NLP tasks.\n\n2. In Figure 8 of the FedPM paper, the accuracy achieved by FedPM is higher than what is reported in this paper. Could you clarify the reason for this discrepancy? Is it due to differences in experimental setup and hyperparameters? If so, could you ensure that all conditions are consistent for the CIFAR-100 experiments and compare your method to the original accuracy reported in the FedPM paper?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive comments.  We provide our response to each comment below.\n\n>Q1: In Figure 8 of the FedPM paper, the accuracy achieved by FedPM is higher than what is reported in this paper. Could you clarify the reason for this discrepancy? Is it due to differences in experimental setup and hyperparameters? If so, could you ensure that all conditions are consistent for the CIFAR-100 experiments and compare your method to the original accuracy reported in the FedPM paper?\n\n**A1**: In Figure 8 of the FedPM paper, the authors distributed IID CIFAR-100 dataset over 10 clients, and every clients are sampled at each communication round, Meanwhile, in our setting, we distributed non-iid CIFAR-100 dataset with Dirichlet distribution of 0.1 over 100 clients and only sampled 10 clients at each communication round. We would like to note that every algorithm has different well working configurations. In the implementation of the FedPM, the authors used Adam optimizer. Since we were not able to reproduce their results with SGD optimizer, we used the Adam optimizer for the FedPM in Table 2. Next, we compare the result of SpaFL over IID CIFAR-100 dataset over 10 clients with the reported accuracy in the FedPM paper. We sampled every client at each communication round and set the learning rate as 0.05 and decayed it by 0.993 at each round. We set local epoch as 7 and averaged over 3 runs. \n\n| Algorithm |Accuracy |\n| --- | --- |\n| SpaFL | $\\mathbf{45.32 \\pm 0.3}$ |\n| FedPM | 42 |\n\n>Q2:I recommend the authors to do additional experiments with NLP tasks.\n\n**A2:** Due to the limited time frame, we will update the result with a transformer model shortly. \n\n>Q3: If you apply this method to the transformer based models, how can you define trainable thresholds? To be specific, you gave an explanation for a convolutional layer in section 3.1, and can we just similarly define for self attention modules?\n\n**A3:** A transformer model mostly consists of multi-head attention modules and feed-forward network modules. In SpaFL, we already provided pruning methods for feed-forward networks such as Linear and Convolutional layers. We can use a similar pruning method for multi-head attention modules as we did for Linear layers. Specifically, we defined a trainable threshold for each column of a matrix in a linear layer, We pruned a whole column if the average magnitude is smaller than its threshold, thereby achieving structured sparsity. Since multi-head attention modules also consist of multiple matrices, we can use the same pruning method. For each column of query, key, value and projection matrices, we can define a trainable threshold, If the average magnitude of parameters in a column is smaller than its threshold, we can prune the entire column. Due to the limited time frame, we will update the result with NLP tasks shortly,", "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": "", "extra_scores": {}}, {"review_id": "3Too74H0M7", "reviewer": "Reviewer_Ju3Y", "summary": "The authors consider distributed training of sparse models, by optimizing over the thresholds used to prune the models.", "questions": "No question", "limitations": "The technical limitations are discussed at the end of the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I am not an expert of deep learning but the results look convincing enough.", "weaknesses": "I would be interested in a discussion and comparison with other approaches that train sparse models, such as\n* Meinhardt et al. \"Prune at the Clients, Not the Server: Accelerated Sparse Training in Federated Learning,\" preprint arXiv:2405.20623, 2024.  \n* Yi et al. \"FedComLoc: Communication-Efficient Distributed Training of Sparse and Quantized Models,\" preprint arXiv:2403.09904, 2024. \n\nand references therein.\n\nThe experiments should investigate more the influence of the level of heterogeneity, because this is what makes it difficult to identify the sparsity pattern.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive comments. We provide our response for each question below.\n\n>Q1:I would be interested in a discussion and comparison with other approaches that train sparse models, such as\n\nMeinhardt et al. \"Prune at the Clients, Not the Server: Accelerated Sparse Training in Federated Learning,\" preprint arXiv:2405.20623, 2024.  \nYi et al. \"FedComLoc: Communication-Efficient Distributed Training of Sparse and Quantized Models,\" preprint arXiv:2403.09904, 2024.\nand references therein.\n\n**A1:** We compare SpaFL with two more baselines: FedP3 [1] and FedSpa [2]. Specifically, FedP3 communicates a subset of sparse layers that are pruned by the server and personalize the remaining layers. FedSpa trains a personalized sparse models while fixing the model density during the training, For FedP3, we set global pruning ratio as 0.5 and use OPU2 method (overlaps two layers) as done in [5]. We use the same data distribution and model architecture as done in our experiment, For CIFAR-10, we set the learning rate as 0.01. For CIFAR-100, we set the learning rate as 0.1 and decayed it by 0.997 for each communication round, We set the initial pruning ratio of FedSpa as 0.5 with cosine annealing as done in [6]. We set the learning rate as 0.01 and 0.1 for CIFAR-10 and CIFAR-100, respectively. \n\n|Algorithm | Accuracy (CIFAR-10) | Accuracy (CIFAR-100)|\n| --- | --- | ---|\n| SpaFL  | $\\mathbf{69.75 \\pm 2.81}$ |$\\mathbf{40.80 \\pm 0.54}$|\n|FedP3 | $67.54 \\pm 0.52$ | $37.73 \\pm 0.42$|\n| FedSpa   | $67.03 \\pm 0.63$ | $36.32 \\pm 0.35$|\n\n>Q2: The experiments should investigate more the influence of the level of heterogeneity, because this is what makes it difficult to identify the sparsity pattern.\n\n**A2:** As the data distribution becomes iid, the sparsity pattern will be more similar. Due to the limited time frame, we will update the result shortly. \n\n**References**\n\n[1] Yi, Kai, et al. \"FedP3: Federated Personalized and Privacy-friendly Network Pruning under Model Heterogeneity.\" The Twelfth International Conference on Learning Representations, 2024\n\n[2] Huang, Tiansheng, et al. \"Achieving personalized federated learning with sparse local models.\" arXiv preprint arXiv:2201.11380 (2022).", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces SpaFL: a federated learning framework for enhancing communication efficiency and minimizing computational overhead by optimizing sparse model structures. This goal is achieved by defining a trainable threshold which leads to structured sparsity. Since the server and clients exchange thresholds only, SpaFL is able to reduce communication overhead. Furthermore, these trainable thresholds lead to lower computation overhead, too.

All reviewers see the paper favorably. In particular, all give acceptance-level scores, and list several compelling strengths, including:

- Communicating the threshold instead of the model weights is an interesting idea
- Preliminary empirical results on popular benchmarks seem to have shown that this idea indeed lowers communication overhead
- The paper is well-written and easy to follow

The several weaknesses that were pointed out by the reviewers were mostly addressed in the rebuttal and ensuing discussion. I fully expect these developments, clarifications and explanations to be included in the camera-ready version of the paper.
Decision: Accept (poster)