On Heterogeneously Distributed Data, Sparsity Matters
Authors: Tiansheng Huang
Shiwei Liu
Li Shen
Fengxiang He
Weiwei Lin
Dacheng Tao
Venue: ICLR 2022 Submitted (2022)
Keywords: Federated Learning
Dynamic Sparse Training
Communication-efficient Personalized Federated Learning

Abstract: Federated learning (FL) is particularly vulnerable to heterogeneously distributed data, since a common global model in FL may not adapt to the heterogeneous data distribution of each user. To counter this issue, personalized FL (PFL) was proposed to produce dedicated local models for each individual user. However, PFL is far from its maturity, because existing PFL solutions either demonstrate unsatisfactory generalization towards different model architectures or cost enormous extra computation and memory.  In this work, we propose federated learning with personalized sparse mask (FedSpa), a novel personalized federated learning scheme that employs personalized sparse masks to customize sparse local models on the edge. Instead of training fully dense PFL models, FedSpa only maintains a fixed number of active parameters throughout training (aka sparse-to-sparse training), which enables users' models to achieve personalization with consistently cheap communication, computation, and memory cost. We theoretically show that with the rise of data heterogeneity, setting a higher sparsity of FedSpa may potentially result in a smaller error bound on its personalized models, which also coincides with our empirical observations. Comprehensive experiments demonstrate that FedSpa significantly saves communication and computation costs, while simultaneously achieves higher model accuracy and faster convergence speed against several state-of-the-art PFL methods.

Under review as a conference paper at ICLR 2022
ACHIEVING PERSONALIZED FEDERATED LEARNING WITH SPARSE LOCAL MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning (FL) is vulnerable heterogeneously distributed data, since a common global model in FL may not adapt to the heterogeneous data distri- bution of each user. To counter this issue, personalized FL (PFL) was proposed to produce dedicated local models for each individual user. However, PFL is far from its maturity, because existing PFL solutions either demonstrate unsatisfac- tory generalization towards different model architectures or cost enormous extra computation and memory. In this work, we propose federated learning with per- sonalized sparse mask (FedSpa), novel PFL. scheme that employs personalized sparse masks to customize sparse local models on the edge. Instead of training an intact (or dense) PFL model, FedSpa only maintains fixed number of active pa- rameters throughout training (aka sparse-t-sppane training), which enables users' models to achieve personalization with cheap communication, computation, and memory cost. We theoretically show that with the rise of data heterogeneity, set- ting a higher sparsity of FedSpa may potentially result in better convergence on its personalized models, which also coincides with our empirical observations. Comprehensive experiments demonstrate that FedSpa significantly saves commu- nication and computation costs, while simultancously achieves higher model ac- curacy and faster convergence speed against several fate-offthee-ae PFL methods
INTRODUCTION
Data privacy raises increasingly intensive concerns, and governments have enacted legislation to regulate the privacy intrusion behavior of mobile users, c.g., the General Data Protection Regulation (Voigt & Von dem Bussche, 2017). Traditional distributed learning approaches, requiring mas- sive users' data to be collected and transmitted to a central server for training model, soon may no longer be realistic under the increasingly stringent regulations on users' private data. On this ground, federated learning (FL), a distributed training paradigm emerges successful solution to cope with privacy concerns, which allows multiple clients to per- form model training within the local device without the ne- cessity to exchange the data to other entities. this way, the data privacy leakage problem could be potentially relieved. Despite the promising prospect, several notorious issues are afflicting practical performance of FL: The global model produced by weight average (or FedAvg and its non-personalized variants) exhibits unsatisfactory performance in a Non-IID data distribution setting. To alleviate this prob- lem, the most popular idea is to integrate personalized features into the global model, and produce dedicated model for each local distribution. However, how to make this integration is an open problem that remains unresolved. Prior works on personalized FL (PFL) zero in this issue, but the existing methods either demonstrate weak generalization towards different model architectures (Arivazhagan al., 2019), or require extra computation and storage (Li et al., 2021).
80 54
nigher Gie Buftle
0
Accuueenyy
PedRww
Smaller the
180
201
Communicatinn Ovathoad
Figure 1: Performance of FedSpa and several baselines w.r.t. communication cost in Non-IID setting. Numbers above FedSpa and Sub-FedAvg are sparsity.
The communication and training overhead is prohibitively high for both the FL and PFL. Clients in FL/PFL responsible for model training are mostly edge-devices with limited computation ca- pacity and low bandwidth, and may not be powerful enough to fulfill modern machine learning

---

Under review as a conference paper at ICLR 2022
task with large deep neural networks. Existing studies (Li al., 2020; Vahidian al., 2021) inte- grate model compression into FL/PFL to save communication and computation overhead. How- ever. both methods embrace the technique of dense-to-sparys training, which still requires large amount of communication at the beginning of training. In addition, how to effectively aggregate the dynamic sparse models is another challenging problem that remains unresolved.
In this work, we propose FedSpa (see Figure 2). which has two key features to counter the above two chal- lenges: (i) FedSpa does deploy single global model, but allows each client to own its unique sparse model masked by a personalized mask, which success- fully alleviates the Non-IID challenge. (ii) FedSpa al- lows each client to train over an evolutionary sparse model with constant sparsity' throughout the whole fed- erated training process, which consistently alleviates the computation overhead of clients. Besides, all the local models in FedSpa are sparse models, which re- quires smaller amount of communication cost in each communication round. Theoretically, we conclude that with the rise of Non-IID extent, setting higher spar- sity may result in better convergence on the personal- ized models of FedSpa. Empirically, in the Non-IID set- ting, we demonstrate that FedSpa accelerates the con- vergence (respectively 76.2% and 38.1% less commu- nication rounds to reach the best accuracy of FedAvg (McMahan et al., 2016) and Ditto (Li et al., 2021)), in- creases the final accuracy (up to 21.9% and 4.4% higher accuracy than FedAvg and Ditto, respec- tively), reduces the communication overhead (50% less parameters communicated than the dense solutions), and lowers the computation (15.3% lower floating-pont point operations (FLOPs) than algo- rithms trained with fully dense model). To the end, we summarize our contribution as:
Parameter Server
global
Spanse local updates
uplost
Local Trakingg
not mak
Figure 2: Overview of FedSpa. Firstly, the server masks and distributes the sparse weights. Secondly, clients do lo- cal training on constantly sparse model. Thirdly, clients upload the sparse updates and being aggregated by the server.
We present a novel formulation of the sparse personalized FL (SPFL) problem, which can be applied various network architectures by enforcing personalized sparse masks to global model.
We propose solution dubbed FedSpa to solve the SPFL problem. By novel design, FedSpa reduces the communication and computation overhead of the general FL solution.
Two pparse-to-sparce mask searching techniques are integrated as plugins of our solution. To adapt PFL training context, modify the DST-based mask searching technique enable warm-start of the searching process, which achieves superior performance.
We theoretically present the convergence analysis of the personalized models. Experimental re- sults demonstrate the superiority of FedSpa and also coincides with the theoretical conclusion with the rise of data heterogeneity, setting a higher sparsity of FedSpa may potentially result in better convergence on its personalized models.
RELATED WORKS
Federated learning (FL) (McMahan et al., 2016) is seriously afflicted by the issue of heterogeneously distributed (or Non-IID) data. Personalized FL (PFL), initiated by recent literature (Li et al., 2021; Arivazhagan et al., 2019), is shown to be effective to counter this issue of FL. In this work, we propose an alternative yet effective way enhance PFL with personalized sparse models.
2.1 PERSONALIZED FEDERATED LEARNING
We categorize PFL into five genres. Firstly, PFL via layer partition, e.g., FedPer (Arivazhagan et al., 2019), LG-FedAvg (Liang et al., 2020), FedRep (Collins et al., 2021), is to divide the global model layers into shared layers and personalized layers. For the shared layers, weights average as in FedAvg is adopted, while for personalized layers, models are trained only locally and will not
Sparsity specifies the ratio of parameters that (or inactive) in model.
2

---

Under review as a conference paper at ICLR 2022
be exchanged with others. Secondly, PFL via regularization, e.g., Ditto (Li et al., 2021), L2GD (Hanzely & Richtárik, 2020) is to add a proximal term on the local model to force the local model and global model closely in the local model fine-tuning stage. Similarly, Sarcheshmehpour et al. (2021); SarcheshmehPour et al. (2021) propose a total variation (TV) regularization to form the network lasso (nl asso) problem, and primal-dual methods adapted from (Jung, 2020) are proposed to solve the nLasso problems, Thirdly, PFL via model interpolation, e.g. MAPPER (Mansour et al., 2020), APFL (Deng et al., 2020) achieves personalization by linearly interpolating the weights of the cluster (global) model and local model as the personalized model. Fourthly, PFL via transfer learning e-g., FedMD (Li & Wang. 2019), FedSteg (Yang al., 2020), and Fedhealth (Chen al., 2020), is to either use model and domain-specific local fine-tuning or knowledge distillation adapt the global model into the personalized model. Finally, PFL via model compression, egg., LotteryFl. (Li et al., 2020) and Sub-FedAvg (Vahidian et al., 2021), achieves personalization via employing principle model compression techniques, such as weight pruning and channel pruning, over the shared global model.
2.2 SPARSE DEEP NEURAL NETWORKS
Methods to Sparsify neural networks can be classified into two genres: dense-to-sparse methods and pparse-to-spary, methods. Dense-to-sparse methods train from dense model, and compress the model along the training process. Iterative pruning, first proposed by Frankle & Carbin (2018), shows promising performance in dynamically searching for a sparse yet accurate network. Recently, sparse-to-spars, methods have been proposed to pursue training efficiency. Among them, dynamic sparse training (DST) (Bellec et al., 2018; Evei et al., 2020; Liu et al., 2021) the most success- ful technique that allows sparse networks, trained from scratch, to match the performance of their dense equivalents. Stemming from the first work sparse evolutionary training (Mocanu et al., 2018; Liu et al., 2020), DST has evolved as class of sparse training methods absorbing many ad- vanced techniques, e.g., weight redistribution (Mostafa & Wang, 2019; Dettmers Zettlemoyer, 2019), gradient-based regrowth (Dettmers & Zettlemoyer, 2019; Evei al., 2020), and extra weight exploration (Jayakumar et al., 2020; Liu et al., 2021).
Our work also achieves personalization via model compression. We emphasize that three main progresses are made towards SOTA compression-basse PFL:: (i) We rigorously formulate the sparse personalized FL problem, filling the gap left by the prior works. (ii) While prior works either vaguely describe their model aggregation as "aggregating the Lottery Ticket Network via FedAvg" (Li et al., 2020), or "taking the average on the intersection of unpruned parameters in the network" (Vahidian et al., 2021), we explicitly formulate the aggregation as averaging the sparse update from clients. (iii) Both the two prominent prior works use the idea of iterative pruning to prune the network from dense to sparse. We instead provide two sparse-to-sparse training alternatives to plug in our solution, which largely reduces the costs of communication at the beginning of the training process, and exhibits remarkable performance.
3 PROBLEM FORMULATION
We assume total number of K clients within our FL system, and we consistently use k to index specific client. First, we give a preliminary introduction on the general FL and PFL problem.
General FL problem. Let E IRd be the global weight. General FL takes the formulation below
K
(P1) min f(w)
Σ (P((w)) = E[A( (wx; (a., s))} k=1
K
where D - 1..0....2 is the joint distribution of k: local heterogeneous distributions, data (æt, y) uniformly sampled according distribution DA wrt. client k and L(::-) the loss function.
Ultimate PFL Problem. Let }wr} be the personalized models. The ultimate PFL is defined as:
K
(P2)
min f(wi,"... wK) = K
Σ k=
Fr (wxx = E[L((r))) (wxs (x, y))}
(w)y }x
3

---

Under review as a conference paper at ICLR 2022
according to (Zhang et al., 2020; Hanzely et al., 2021). The problem could be separately solved by individual client with no communication. However, if the local data is insufficient, poor performance could be observed by this direct solution, since the local models cannot be boosted by other clients.
Regularized PFL problem. Regularized PFL can case the heterogeneous challenges encountered by general FL, while escaping the curse of insufficient samples encountered by the ultimate PFL problem. Inspired by (Chen & Chao, 2021), we formulate the Regularized PFL problem as follows:
(P3)
min f(w1,.". WK)
F& (w)) ElC(ayy)- (wxi (z, v))1 R-),
[wi (K)
where We denote the personalized models and R(-) is the regularizer that enables information ex- change between clients, making the problem tractable even the local samples are insufficient. How- ever, it remains controversial about how to define the regularizer. Also, the gap between regularized PFL problem (P3) and the ultimate PFL problem (P2) still remains unspecified in existing PFL study.
In this work, our ultimate goal to solve problem (P2), which requires information exchange be- tween clients to ensure effective solution. Below, instead of utilizing regularizer in (P3), alternatively propose a novel Sparse PFL (SPFL) problem to reach the same goal.
Sparse PFL problem. By introducing personalized masks into FL, we derive the SPFL problem as
1 K
(P4)
min f(w)
[Fim] 3 w) = E[C(=,)) (m) o w: (x, B))
where m E (0, 13d is personalized sparse binary mask for k-th client. @ denotes the Hadamard product for two given vectors. Our ultimate goal is to find global model w, such that the per- sonalized model for k-th client can be extracted from the global model by personalized mask m ie., m @ w. The element of m being means that the weight in the global model is active for k-th personalized model, otherwise, remains dormant. Thus, the information exchange between all personalized models is enforced by shared global model w.
Compared with existing PFL algorithms, solving tional computation and storage overhead of clients, since we do not maintain both personalized local models and global model in clients in (Li et al., 2021; Mansour al., 2020). On contrary, the solution to our problem could potentially lower the communication and computation overhead. Moreover, SPFL problem (P4) can be applied to most of the model architectures without model- specific hyper-paramenn parameter tuning, since we do not make model-specific separation of the public and personalized layer in (Arivazhagan al., 2019; Liang et al., 2020; Collins et al., 2021). or domain- specific fine-tuning in (Chen et al., 2020; Yang et al., 2020).
SPFL. problem (P4) does not sacrifice addi-
FEDSPA: SOLUTION FOR SPFL
In this section, we first introduce our proposed FedSpa in Algorithm 1. Then, specify the update rule of global model, and two sparse-to-spary mask searching methods that can be plug in the update process. At last, we give a theoretical analysis on evaluating the quality of the iterates of FedSpa with respect to the ultimate PFL problem (P2).
4.1 GLOBAL MODEL UPDATE RULE FOR FEDSPA
Data Parallel-based Update. We first propose the following iterative update to solve problem (P4)
17 m C
W++1 we
K
where Ex,t is a batch of data that is uniformly sampled from the k-th client's local distribution Dz. n is the learning rate, and uū = m. ( w. the sparse weights sparsified by mask m However,
4

---

Under review as a conference paper at ICLR 2022
the optimal personalized masks {mī} generally not accessible to in the solution process. Let m,, be an intermediate surrogate personalized mask of m we rewrite Eq. (1) as:
K mkkt ① Vw... C( Ex.e).
" K
Wi+1 = wt
(2)
For our proposed update rule, it is worth mentioned that: (i) Some coordinates of the model weights have been made zero before doing the forward process, i.c., not all the parameters have to be involved when calculating ((wiet Ex.r). This means that the computation overhead the forward process could be potentially saved. (ii) In the backward process, the stochastic gradient Vwv.. _. C( CR,e) masked again by my.t. which means that we do not need backward the gradient for those sparse coordinates. Thus, the computation cost can be largely saved.
FL-adapted Update. To save the communication overhead, we integrate the idea from local SGD (Stich, 2018) and partial participation to our solution. Let tūk,,,7 denote the weights before doing (r+ (r+1)-th 1) step of local SGD and set tūk,t.0 ma, 3w (i.e., the local weights will be synchronized every N steps with the global weights). Then, each client & E S, updates its model below:
WR,1,7+1 = Ük,1,7 T @ Van,... L(tik,r (A. 1, 1
(3)
where SR.e.r is a batch of sampled data in r-th step at round t. After the local training is finished, the models of participated clients updated and aggregated the global model in server follows:
w++1 w.
WE.L0 WK.NN),
S
RES.
where S; is the set of clients selected to be participant in round According to Eq. (3), the update synchronized to the server (i.e., Wk,1,0 W,,,,N), and the model distributed to clients (i.e., w..0.) are all sparse with a constant sparsity. Therefore, the communication overhead over synchronization could be largely saved. At last, we summarize our proposed FedSpa in Algorithm 1.
Algorithm FedSpa
Input Training iteration T; Learning rate v): Local Steps N; Random seed seed;
1: procedure SERVER'S S MAIN Loop
2: Randomly initialize global model w0
3: m& Initialization(seee) for k = 1, I...., K
Initialize masks via mask-searching
solution
4:
for == 0, 1......, T do Uniformly sample fraction of client into St for each client à & S. do
5:
6:
7:
mg.++1 = -mat
Inherit masks for round f + 1 if not chosen
8:
for k E S. do
9: Send Wk.1.0 = ma,t @ we to client
Call Client k's main loop and receive Uk and mg.++1
11:
Wr++1 = W0 3 Σ,es, U procedure CLIENT'S MAIN LOOP for T
> Average and apply the update
12:
13:
do Sample a batch data Êx,e.r from local dataset 9k.t.r (W0k,,, V Wu.... L( Ex.,,) Wk.1771 WRS17 7pm2,, r 3 gk.t, (Wx...)
14:
15:
16:
Local update with fixed mask myg
17:
UK, Wk..0 KKC,N
18:
m NasksM
Plug in mask-searching solution to produce next masks
19:
Send back UR. and mg.c+1
4.2 SPARSE-TO-SPARSY MASK SEARCHING TECHNIQUE
The framework of FedSpa is extensible. Specifically, we use the mask surrogate my, in Eq. (3) perform the update, which allows plug in arbitrary mask searching techniques determine
5

---

Under review as a conference paper at ICLR 2022
the iterating process of ma.e- In this work, we nominate two kinds of techniques: modified dynamic sparse training (DST) (Liu et al., 2021) and Random Static Masks (RSM), into FedSpa reduce the computation and communication cost.
training
Modified DST for FedSpa. Our modified DST solution (see Algorithm 2) for FL follows these procedures. Firstly, randomly initialize the same mask for each client based Erdós-Rény' Kernel (ERK) (Evci al., 2020). Secondly, after local training, each client prunes out a number of unpruned weights with the smallest magnitude, and the number of weights being pruned is determined by decayed pruned rate. Thirdly, recover the same amount of weights pruned in the last step. We follow the recovery process as in (Evci et al., 2020) by utilizing the gradient information to do the recovery. By our DST method, the number of sparse weights (aka. sparse volume) remains a constant (i.e.. B) throughout the whole training process.
Algorithm 2 Modified DST for FedSpa
Input Initial pruning rate og; Set of Model layers J: 1: procedure INTTIAIZZATIO((see)]
2: Randomly initialize mk.0 using the same random seed seed.
3: procedure NEXT MASKS(
4: Decay a using cosine annealing with initial pruning rate og
5: Sample a batch of data and backward the dense gradient g(Wk,,,,N)
6: for layer j E I do
7: Update mask m ())
k.t+] by zeroing out ae-proportion of weights with magnitude pruning
8: Update mask m k,t++ via recovering weights with gradient information g( ((Wk.N,)
(i)
9: Return mg.++1
Remark. We highlight our main modification over traditional DST techniques like Rigl (Evci al., 2020) and Set (Mocanu et al. (2018)) to an FL context exist two main aspects: (i) The pruning is performed individually by each client based on their local models, and the gradient used for weights recovery is derived using the client's local training data. (ii) Once the next masks are generated, existing DST solutions immediately apply them to the local model weight. Indicated by Liu et al. (2021), by doing so, the recovered coordinate may need extra training steps to grow from to a dense value. Our solution relieves this problem by applying the new mask on the global weights (which are dense), such that the recovered coordinates could have a dense initial value to warm-start.
RSM for FedSpa. RSM (shown in Algorithm 3) is basi- cally fixing my.t for all & E [K] to the same randomly ini- tialized mask, which remains unchanged during the whole training session. This solution also ensures the same sparse volume for all the clients throughout the training process, and could also reduce the computation and com- munication overhead DST. Interestingly, within the set- ting of the homogeneous data distribution, we empirically show that RSM is more effective than DST in FedSpa.
Algorithm 3 RSM for FedSpa
procedure INITIALIZATION(Seed)
2: Randomly initialize mæ,0 us- ing the same random seed seed
3: procedure MASKS
mg,++1 mggt
5: Return mg,1+1
4.3 THEORETICAL ANALYSIS
In this section, we shall introduce the convergence property of personalized models produced by FedSpa. We first give the following assumptions.
Assumption 1 (Coordinate- wise bounded gradient dissimilarity). For any w Rd. there ex- ists a constant G > O bounding the coordinate-wise gradient dissimilarity over all clients, i.e., ( 1 EK=n F (w)) S.
( Eu,s.r ) is an unbiased estima- Assumption 2 (Bounded variance). Assume that g (w)) VL(w;;
tor V (w) with bounded variance, i.e., IE Ilgh,, V (w)) Sa² 2o2,kk,t, t, v E Rd. Assumption 3 (L-smoothness). We assume L-smoothness over the client's 's loss function, i.e., F (w)) - (i2)il)) & T. ubz| holds for arbitrary w u2 E Rdd

---

Under review as a conference paper at ICLR 2022
Assumption 4 (Coordinate-wind bounded gradient). Suppose the coordinate-wis gradient of each client is upper-bounded. i.e., VV ( (w) S B.
Assumptions 2 and 3 are commonly used for characterizing the convergence of FL algorithms. We modify the other two assumptions slightly from their counterparts in existing FL literature (Xu al., 2021, see Assumptions 3 and 5) by replacing the Lg norm with Loe norm. These modifications are made reveal the coordinate-wor wise gradient information in our analysis.
Theorem 1 (Convergence of personalized models), Given the above assumptions, suppose the learning rate satisfies 7) 16 the optimal personalized masks m {0, and the evolu- tionary masks m, E {0, 1] maintain the same sparse volume constraint, i.e. ||1- millo
||1 - mı = B. the personalized sparse models {WE,t} generated via FedSpa exhibits the fol- lowing convergence property towards the optimal solution of ultimate PFL problem (P2):
1
Σ
K
E [
(10x,)) [13] S
3(f (wo)= (((w))
3
(S)
TK
TnNN
1=0 k=
1=U
where
K
2
150N
15
5N and Pt. (25 +
GN GN","''" 2²
1a² + 1) +
AN , No
Σx
m2) + 9N L +
Nn
2
2K
d1
Ex ((d B)
+ K Ex B² (ddss((mmr. m..)) + dist(m m m
T
200 =0p8-a
200 ao mm Σx Ex dist(m), m B² dist(m1, m2) is the hamming distance" K2
20 s0ffm., Cmmaa
oid-3)C²+ 33B²
3
a083-d
=0 8-0
1f -m
between masks my and m2.
Below, we give several comments on the above theorem. We focus analysis on the the second and third residuals, which do not vanish as communication round T -> 0o
Impact of sparse volume. The result in Eq. (5) is highly related to setting of sparse volume, i.e., B. The term 3B² would vanish as 3 - O, while the term (d - 3)G² would disappear as 3 - d. When the data is highly heterogencous, i.c., gradient dissimilarity is drastic, G could be prohibitively large to dominate the error. Then setting the sparsity level to a relatively large value, which results in a lower (d (d² would potentially give smaller non-vanished error. On contrary. when the data heterogeneity is mild, the error could be dominated by BB². Then setting an excessively high sparsity might even hurt the performance, This conclusion is also evidenced by our experimental results (see Figure I in Section 1, where the optimal sparsity setting of FedSpa that achieves the highest accuracy is 0.5).
Error by evolutionary mask searching. Recall that FedSpa uses evolutionary masks as a surro- gate of optimal masks to perform update on the global model w, (see Eq. (3)). This replacement may bring additional errors to the convergence bound, as the hamming distance between the evo- lutionary masks and optimal masks (i.e., the term dist(ma.; mz)) exists our bound.
Error by dissimilar evolutionary masks. The theoretical result on the term dist(m.e. my in i, indicates that the dissimilarity among the evolutionary masks may also play a role in optimizing the ultimate PFL problem (P2). This term could be minimized if the evolutionary masks remain the same throughout the training process, and would dominate the error if the masks are too distinct. This observation exactly motivates us to present the naive mask searching technique RSM in Algorithm 3, which forces all the clients to share the same random masks.
EXPERIMENTS
In this section, we conduct extensive experiments verifying the efficacy of the proposed FedSpa. Our implementation of FedSpa is based on an open-source FL. simulator FedMI. (He et al., 2020).
5.1 EXPERIMENTAL SETUP
Dataset. We evaluate the efficacy of FedSpa on EMNIST-Letter heMefsStt CIFARIO, and CIFAR100 datasets. We simulate the client's data distribution on Non-IID and IID setting. We
Hamming distance measures the number of positions at which the two masks different.

---

Under review as a conference paper at ICLR 2022
IID
Non-IID (setting
Non-IID (setting
EMNNIST-L
Accuracy
0.-
3.0
0.9
0.8
0.7
0.7
0.7
Accuracy
CIFAR10
0.0
0.0
0.6
0.5
0.6
CIFARIOO
Accuracy
0.6
0.2
0.0
0.0
0.0
200
Communication
Rounds
Communication Rounds
Communication Rounds
Fed5pa (DST)
FedSpa (RSM)
Dito
FecAug
Sub-FeddAug
Local
Subsampliing
Figure 3: Test Accuracy vs. Communication Rounds
simulate two groups of NoD-III settings via y-Dirichlet distribution, named setting A and setting B. Setting and setting B respectively specify y 0.2, 0.1 for both EMNIST-L and CIFARI00, while specify 0.5, 0.3 for CIFAR10. Details of our simulation setting are available in Appendix B.1.
Baselines. We compare our proposed FedSpa with four baselines, including FedAvg (MeMahan et al. (2016)), Sub-FedAvg (Vahidian et al. (2021)), Ditto (Li et al. (2021)) and Local. We tune the hyper-parameters of the baselines to their best states. Specifically, the regularization factor Ditto set to 0.5. The prune rate each round, distance threshold, and accuracy threshold of Fed-Subavg are fixed to 0.05, 0.0001, 0.5, respectively. We ran 3 random seeds in our comparison.
Models and dyper-paramees ResNet18 for CIFARIO 100 our experiment. We use a SGD optimizer with weight decayed parame- ter 0.0005. The learning rate is initialized with 0.1 and decayed with 0.998 after each communication round. We simulate 100 clients in total, and in each round 10 of them are picked to perform local training (the setting follows McMahan et al. (2016)). For all the methods except Ditto, local epochs are fixed to 5. For Ditto, in order to ensure a fair comparison, each client uses 3 epochs for training of the local model, and 2 epochs for global model training. The batch size of all the experiments is fixed to 128. For FedSpa, the pruning rate (i.e., a₂) is decayed using cosine annealing with an initial pruned rate 0.5. The initial sparsity of layers initialized by ERK with scale parameter 1.
We use LeNet5 for EMNIST-L, VGGI1 for CIFARIO, and
5.2 MAIN PERFORMANCE EVALUATION
We fix the dense ratio of FedSpa (DST), FedSpa (RSM), and the final dense ratio of Fed-SubAvg both to 0.5 (i.e., 50% of parameters are pruned) our main evaluation. Other typer-parametert are fixed as default. Figure 3 and Table illustrate the training performance of different algorithms three datasets. We evaluate the performance based on the following metrics:
Final Accuracy. In the Non-IID setting, show that FedSpa (DST) achieves remarkable per- formance. Specifically, in Non-lID setting B of CIFAR100, FedSpa (DST) achieves respectively 4.4%, 11.9% and 21.9% higher final model accuracy, compared with Ditto, Sub-FedAvg and Fe- dAvg. FedSpa (DST) seems to achieve better performance as the FL tasks becoming difficult (since better performance observed in a higher Non-IID extent, and in datasets that are intrinsically more difficult). Interestingly, in the IID setting, we show that all the personalized solutions exhibit some extents of performance degradation, which become more significant as the dataset becomes challenging. The compression-bant based methods seem to be especially vulnerable in this setting. Our interpretation for this phenomenon is that: since the information exchange between clients would be limited by employing different sub-networks for training, the clients could not efficiently make an effective fusion on their models through parameter averaging. This hypothesis substantiated FedSpa (RSM), alternative implementation of FedSpa, which forces all
by our experiment the masks to maintain the same sub-network. FedSpa (RSM) achieves commensurate performance with FedAvg in the IID setting, outperforming the personalized solutions. The reason FedSpa (DST)
8

---

Under review as a conference paper at ICLR 2022
Table
Table illustrating performance of different methods.
Non-IID
IID
Setting A
Setting B
Task
Method
Acc
Aoc
Cost (GB)
Acc
Comm (GB)
FLOP
(GB)
(Ie14)
(1c16)
(1c14)
FodSpa (DST)
92.2=0.1
7.0
2.0
95.3+0.1
7,0
96.5+0.2
7.0
2.0
FedSpa (RSM)
92.9+0011
7.0
2.0
91.9+002
7.0
2,0
90.6++0.99
7.0
2.0
EMNIST-L (LeNet)
Ditto
92.9=0.1
14.1
3.5
95.9=0.1
14.1
3.5
97,0+0.2
14,1
3.5
FedAvg
93.5-002
14.1
92.3+0.3
90.9+0.8
14.1
3.5
Sub-redAvg
90.7:10.2
9.5
1.9
94.910.2
9.4
1,9
96.410.2
9.4
1.9
Local
77.6+00.3
3.5
87.8+0.11
3.5
91.6+0.5
3.5
Suhsampling
93.3-10.2
10.5
3.5
92.0::0.4
10.5
3.5
91.3-100.6
10.5
3.5
FedSpa (DST)
83,4:00.1
369.2
172.9
86.6.10.5
369.2
173.3
88.2:0.
369.2
173.5
FodSpa (RSM)
84.5=00.1
369.2
172.9
82.1++022
369.2
173.5
80.9+0.22
369.2
173.5
CIFAR-10 (VGG11)
Dino
83.5+-0.2
738.5
229.3
86.4+00.6
738.5
229.8
87.8+0.33
738.5
230.0
FedAvg
84.810.3
81.400.4
738.5
Suh-FedAvg
71.8+0.3
410.2
121.4
78.3++1.0
424.7
120.6
79.6++0.6
416.9
119.8
Local
42.5.10.2
229.3
63.6.10.6
229.8
69.4.10.2
230.0
Suhsampling
83.0=0.4
553.9
78.9+0055
76.7+-1.0
553.9
230.0
FedSpa (DST)
41.5+0.5
448.8
705.1
59,0++10
448.8
704.9
66.9+012
448.8
704.8
FedSpa (RSM)
448.8
44.610..
448.8
704.8
CIFAR-100 (8esNet18)
Ditto
$1.91111
897.6
833.2
56.8:10.6
897.6
831.0
62.5100.2
897.6
832.9
FedAvg
1..7:11.3
897.6
833.2
49.3:104
897.5
833.0
45.0::0.
897.6
832.9
Sub-FedAvg
38.3:10.8
616.5
494.1
49.2.10.7
624.4
5U8.4
55.0.10.7
612.8
496.1
I Local
10.3+-0.3
833.2
28.8+00.1
833.0
40.5+004
832.9
Subsampling
49.8.11.3
833.2
42.310.88
673.2
832.9
performing better in Non-IID setting can also be explained by Theorem 1, which concludes that in a Non-IIID setting, setting proper sparsity for personalized models may promise hetter convergence.
Convergence. As shown Table 2, FedSpa achieves significantly faster convergence, which poten- tially saves the communication rounds to train model from scratch to specific accuracy.
Table 2: Communication rounds fixed accuracy.
Non-IID
CIFARIO
II
Setting A
Setting B
Acc@ 70
Acc@75
6cc080
Acc@77
Asc
Acc@80
Acc@70
Acc@:75
Acc
FedSpa (DST)
134.0.22.9
183.3168
312.3116.2
167.3.1.00
206.31-4.1
270.0.1.11
FedSps (RSM)
1013311.
14131162
237.011.4
195.3
271.3116.2
471.7119.8
252.0112.7
339.01120.6
611.0112.88
Didio
284.7:88.1
570.319.3
549 31:22.6
242.5212.7
334.0:166.5
366.3:.3.3
190.3:261
278 378.01222.0
417.7:10.22
HodAvg
105.0=2.2
140.3+47
2287+23.5
198 19115
7-..8810.8
474,7+31.4
241.0-3.7
327. 348.3
583.7-65.5
Sub-FedArg
197.7.222
1000
15171100.
235.0.177.1
1000
1917166.6
Subsampling
198.0 198.224.5
268.31455
13..0:13..5
365.3123.8
523.0243.4
1000
466.3:1500
722.71105
1000
CIFARI00
4008:00
Acc8500
Acc
Axc0-10
Asc8 50
Acc
Acc040
Acc
Asc855
FedSpu (DST)
536.3=3559
1000
1000
236.3:12.3
442.0:16.9
595,01:113
181,3:788
314.7117.4
407.7116.77
FealSpa (RSM)
239.3-24.1
435.7+258
1000
460.
1000
594,0=101
1000
1000
Didoo
515.7119.4
868.71.56.1
1080
116.
721.0.20.22
891.0125.0
301.3110.8
531.111.3
678.717.9
FodAvg
245.025.11
436.31:25.3
1000
470.7125.4
> 1000
1000
589.7246.7
1000
> 1000
Sub--odAAyC
1000
1000
1000
280.5
> 1000
1000
246,3=10.1
131,3+14,1
511.0+85,9
Suhsampling
460.7=16.6
1000
845.34599.2
1000
1000
Training FLOPs and Communication. From Table 1, FedSpa (DST) achieves 15.4%
lower FLOPs than the dense solutions (e.g.. Ditto, FedAvg), 13.0%~28.22%% lower communication overhead than another model compression solution Sub-FedAvg, and 50% lower communication than the dense solution. The edge of FedSpa (DST) stems from its training pattern - it is trained from sparse model, with constant sparsity throughout the training process. However, it interesting to see that the training FLOPS of Fed-SubAve is considerably lower than FedSpa, even under the same sparsity setting. This phenomenon stems from our ERK initialization, which is essential for the high performance of our solution, for which we will have further discussion in Appendix B.4.
6 CONCLUSIONS
In this paper, we propose FedSpa, personalized FL solution that enables sparse-to-sparse train- ing and efficient sub-model aggregation. As demonstrated by our experiments, FedSpa exhibits outstanding performance in the Non-IID setting, outperforming other existing solutions in terms of accuracy, convergence speed as well as communication overhead. Additionally, we present theo- retical analysis to evaluate the error bound of FedSpa towards the ultimate PFL problem. Future direction includes designing new model aggregation solutions for the sparse sub-network, and new mask searching techniques specifically targeting on federated learning process.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
For sake of reproducibility of our solution, we make the following efforts: (i) In Appendix B.1, we clearly state the data splitting method for IID and Non-IID data distribution. (ii) In Appendix B.2, the network models we used in our experiment are clearly described. (iii) In Appendix B.4, the proposed FedSpa with various
during the implementation are also systemically tested to demonstrate its stability and superiority. (iv) In Appendix C, we give the self-contained proof of Theorem 1. (v) last, the source-code FedSpa is enclosed in the supplementary material.
REFERENCES
Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary, Fed- erated learning with personalization layers. arXiv preprint arXiv: 19/2.009/2000888 2019.
Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert Legenstein. Deep rewiring: Training very sparse deep networks. In International Conference on Learning Representations, 2018.
Hong- You Chen and Wei Chao. On bridging generic and personalized federated learning. arXiv preprint arXiv:2107.0071 00778, 2021.
Yiqiang Chen, Xin Qin, Jindong Wang, Chaohui Yu, and Wen Gao. Fedhealth: A federated transfer learning framework for wearable healthcare. IEEE Intelligent Systems, 35(4):83-95 2020.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared repre- sentations for personalized federated learning. arXiv preprint arXiv:2102.07078, 2021.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning, 2020.
Tim Dettmers and Luke Zettlmoyer. Sparse networks from scratch: Faster training without losing performance. arXiv preprint arXiv:1907.cm 00440004444 2019.
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pp. 2943-2952. PMLR, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv: 2018.
Filip Hanzely and Peter Richtárik. Federated learning of a mixture of global and local models. arXiv preprint 2xXx:20002.055// /6, 2020.
Filip Hanzely, Boxin Zhao, and Mladen Kolar. Personalized federated learning: A unified frame- work and universal optimization techniques. arXiv preprint arXiv:2102.09743, 2021.
Chaoyang He, Songze Li, Jinhyun So, Xiao Zeng, Mi Zhang, Hongyi Wang, Xiaoyang Wang, Pra- neeth Vepakomma, Abhishek Singh, Hang Qiu, et al. Fedml: research library and benchmark for federated machine learning, arXiv preprint arXiv: 20X::2007.1355 13518, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Kevin Hsich, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-iid data quagmire of decentralized machine learning. In International Conference on Machine Learning, pp. 4387- 4398. PMLR, 2020.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.06333. 2019.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456 PMLR, 2015.
10

---

Under review as a conference paper at ICLR 2022
Siddhant Jayakumar, Razvan Pascanu, Jack Rae, Simon Osindero, and Erich Elsen. Top-kast: Top-k always sparse training. Advances in Neural Information Processing Systems, 33, 2020.
Alexander Jung. Networked exponential families for big data over networks. IEEE Access, 8: 202897-202909, 2020.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143. PMLR, 2020.
Jakub Konečný, Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint urXiv:161000549) 2016.
Yann LeCun et al. Lenet-5, convolutional neural networks. URL: http://yann. lecun. com/exdb/lenet, 20, 2015.
Ang Li. Jingwei Sun, Binghui Wang. Lin Duan, Sicheng Li, Yiran Chen, and Hai Li. Lotteryfl: Personalized and communication-ed -effrccennt federated learning with lottery ticket hypothesis non-iid datasets. arXiv preprint 0rXiv:2008.03371, 2020.
Daliang Li and Junpu Wang. Fedmd: Heterogenous federated learning via model distillation, 2019.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization, 2021.
Paul Pu Liang, Terrance Liu, Liu Ziyin, Nicholas Allen, Randy P Auerbach, David Brent, Ruslan Salakhutdinov, and Louis- Dhiis-Phllippe Moreney. Think locally, act globally: Federated learning with local and global representations. arXiv preprins arXiv:2001.01523, 2020.
Shiwei Liu, Decebal Constantin Mocanu, Amarsagar Reddy Ramapuram Matavalam, Yulong Pei, and Mykola Pechenizkiy. Sparse evolutionary deep learning with over one million artificial neu- rons on commodity hardware. Neural Computing and Applications, pp. 1-16, 2020.
Shiwei Liu, Lu Yin. Decebal Constantin Mocanu, and Mykola Pechenizkiy. Do actually need dense over poce-paraatttiizaioon? in-time over- poee-aaaatterization in sparse training. In Proceedings of the 39th International Conference Machine Learning, pp. 6989-7000. PMLR, 2021.
Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications to federated learning. arXiv preprint arXiv:2002.10619, 2020.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communicaiion-eficieent learning deep networks from decentralized data. arXiv preprint arXiv: 2016.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connec- tivity inspired by network science. Nature Communications, 9(1 91):3333, 2018.
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. International Conference on Machine Learning, 2019.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295. 2020.
Yasmin Sarcheshmehpour, M Leinonen, and Alexander Jung. Federated learning from big data over networks. ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3055-3059, IEEE, 2021.
Yasmin SarcheshmehPour, Yu Tian, Linli Zhang, and Alexander Jung. Networked federated multi- task learning. arXiv preprint wrXiv22105.12660 2021.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.

---

Under review as a conference paper at ICLR 2022
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv:1805.09767, 2018.
arXiv preprint
Saeed Vahidian, Mahdi Morafah, and Bill Lin. Personalized federated learning by structured and unstructured pruning under data heterogeneity, arXiv preprint arXiv:2105.00566,, 2021.
Paul Voigt and Axel Von dem Bussche. The eu general data protection regulation (gdpr). Practical
Guide, 1st Ed., Cham: Springer International Publishing, 10:3152676, 2017.
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference computer vision (ECCV), pp. 3-19, 2018.
Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedem: Federated learning with client-level momentum. arXiv preprint arXiv:2106. 10874, 2021.
Hongwei Yang, Hui He, Weizhe Zhang, and Xiaochun Cao. Fedsteg: federated transfer learning framework for secure image steganalysis. IEEE Transactions on Network Science and Engineer- ing, 2020.
Michael Zhang, Karan Sapra, Sanja Fidler, Serena Yeung, and Jose M Alvarez, Personalized feder- ated learning with first order model optimization, arXiv preprint arXiv:2012.08566 2020.
12

---

Under review as a conference paper at ICLR 2022
A CRITICAL COMPONENTS OF FEDSPA (DST)
ERK initialization. In Algorithm 2, we use Erdós-Rényí Kernel (ERK) originally proposed by Evci al. (2020) initialize the sparsity of each layer. Specifically, the active parameters of the convolutional layer initialized by ERK is proportional to 1 1="=1 n--1=m! +art h respectively specify number of input channels, output channels and kernel's width and height in +n' the 1-th layer. For the linear layer, the number of active parameters scale with - where n/-1 and n' are the number of neurons in the - 1-th and I-th layer. This initialization basically allows the layer with less parameters have more proportion of active parameters.
+h' where n² ny w and
Cosine annealing. Recall that we set the initial pruning rate as og and gradually decay it to with cosine annealing Liu et al. (2021). The update of pruning rate with cosine annealing can be formalized as: 0₁ = 0.5 x oo x 11 +os cos (--))) We perform this decay in order to ensure that the network (specifically, its active coordinates) would not experience drastic change on the later stage of training while ensuring that the mask searching is effective the early stage of training.
B DETAILED SETTING AND ADDITIONAL EXPERIMENTS
B. DATA SPLITTING SETTING
In our implementation, we first split the training data (60k pieces of data for CIFAR10 and CI- FAR100, and 145.6k for EMNIST-L, respectively) to clients for III) setting and Non-III setting. For the IID setting, data are uniformly sampled for each client. For the Non-IID setting, we use 7-- Dirichlet distribution on the label ratios ensure uneven label distributions among devices as (Hsu et al., 2019). The lower the distribution parameter is, the more uneven the label distribution will be, and would be more challenging for FL. After the initial splitting of training data, we sample 100 pieces of testing data from the testing set to each client. To simulate the personalized setting, each client's testing data has the same proportion of labels as its training data. Testing of the personalized model is performed by each client based on their personalized data, and the overall testing accuracy is calculated as the average of all the client's 's testing accuracy. In our experiment, we simulate dif- ferent -ID-IID settings. For CIFARIO, Non-IID setting A and B respectively specify y 0.5 and = 0.3. For EMNIST-L and CIFAR100 since the number of the total labels are bigger?, we use smaller y, wherein setting A and B respectively specify 7 0.2 and y 0.1.
B.2 NETWORK ARCHITECTURES
We follow the Caffe's implementation of LeNet5 4 (LeCun et al., 2015), VGG11 (Simonyan & Zisserman, 2014) and ResNet18 (He et al., 2016) to do the evaluation. Suggested by Hsieh et al. (2020), DNNs with batch normalization layers (loffe & Szegedy, 2015) are particularly vulnerable to the Non-IID setting, suffering significant model quality loss the FL process. Following the recommendation from Hsieh et al. (2020), we use group normalization (Wu & He, 2018) to substitute the original batch normalization layer in both ResNet18 and VGGI1.
B.3 BASELINE DESCRIPTION
Below, we give brief introduction of the baselines compared in our evaluations:
FedAvg (McMahan et al., 2016) is the vanilla solution of FL. It utilizes weights average to enable all the clients to collaboratively train a global model, which efficiently absorbs knowledge from personal data resided in clients.
Ditto (Li et al., 2021) is a personalized FL solution aiming to smooth the tension brought by the data heterogeneity problem of FL.. Ditto achieves personalization via maintaining both the local models and global model. Specifically, within each round of iteration, each client first trains the global model based on its local empirical loss (which shares the same procedure as FedAvg).
226 and 100 labels respectively in EMNIST-L and CIFAR 100, while only 10 labels in CIFAR10 10.
"Available
13

---

Under review as a conference paper at ICLR 2022
After the global model is updated, each client additionally trains its local model based loss function involving its local empirical loss and the proximal term towards the global model. This local training phase is used to extract the global knowledge into each client's 's local model. Since each client has to maintain and train both local model and global model, Ditto might need extra computation and storage overhead achieve its personalization.
Local is the direct solution to the ultimate PFL problem (P2). Each client performs SGD based on its local data, and there is no communication between clients. To mimic the FL setting, we sample 10 out of 100 clients to do the local update on its local model after every epochs of training (same with the number of local epochs in communication round that is performed by other solutions). For sake of consistency, we still use I communication round to represent local epochs of Local in our evaluation.
Sub-FedAvg (Vahidian al., 2021) is prominent model compression- based PFL. Sub-FedAvg maintains personalized sub-networks for each client. Training of Sub-FedAvg starts from a fully dense model, and this solution iteratively prunes out the parameters and channels as the training progresses. Finally, the commonly shared parameters of each layer are removed, and only the personalized parameters that can represent the features of local data are kept.
Subsampling (Konečný et al., 2016) is gradient- compeesiooo solution aiming to reduce the com- munication overhead of FL. The local training procedure is the same with FedAvg. The difference is that Subsampling does not communicate the intact model for aggregation, but only commu- nicates the sparse gradient update to the server for aggregation. Explicitly, in each round, the sparse gradient update is produced through element-wisely multiplying a random mask. Different from FedSpa, the randomized mask is independently generated in each round, and would only be used to compress the gradient when uploading the gradient update (which means in the model distribution phase, the model distributed would not be sparsified, and therefore would not save the downlink communication cost).
B.4 ABLATION STUDY
In this sub-section, we focus on the ablation study of FedSpa. Specifically, we study the impacts of dense ratio, different mask initialization methods, and the gradient-involved weight recovery proce- dure. Additionally, we present an interesting observation on the performance of the global model trained by our personalized solution. Our ablation study done with ResNet- 18 on CIFAR100.
Impact of sparsity (aka. sparse ratio). Fixing other components and hyper- parametesssserrs to the default value our setup, we change the sparsity of FedSpa to 0.2, 0.4, 0.5, 0.6 and 0.8, to show its impact on the algorithm performance. Experimental results are available in Figure 4 and Table 3. By our report, we observe that sparsity may impact learning performance under different data distribution settings. For the IID setting, higher sparsity seems to seriously degrade the training performance, while for the Non-IID setting, properly sparsifying the model may even enhance the final accuracy, and with higher Non-IID extent, the benefit of sparsification reinforces. This ob- servation surprisingly coincides with our theoretical conclusion given in Theorem 1, that setting the sparse volume proper value when gradient dissimilarity is large (i.e., under a high extent of Non-IID) could foster better performance of personalized models. But too much sparsity, even in the highly non-iid setting (c.g. 7 0.1) leads to performance degradation. On the contrary, while it is rid, the convergence could be dominated by the errors brought by sparsification, and setting the mask to a higher sparsity could possibly enlarge these existing errors.
Another more intuitive interpretation for the impact of sparse ratio is from the perspective of infor- mation exchange. Too much sparsification may limit the information exchange between the local sparse models. If all the clients maintain an extremely high sparsity, the intersected coordinates between clients' local sparse models (or identically, their masks) would be small. Then the local update averaging process (see Eq. (4)), the only way to extract global knowledge into the local models, would not be effective. On contrary, while the sparsity is set to an extremely low value, the personalized features of local models could be eliminated, since only limited coordinates in their models are different.
ERK vs. Uniform sparsity initialization. Recall our mask initialization procedure in Algorithm 3 that the layer-wise sparsity is initialized by ERK. This in essence ensures that the layer-wise sparsity of model is scaled with the number of parameters in layer. Liu et al. (2021) confirms the out-
14

---

Under review as a conference paper at ICLR 2022
(y-
0.2
16
Acouracy
CIPARIDO
403
3000
360
380
480
100
Communicttion Rounds
Communication Rounds
Communictiion Roundss
(DST)
Fed5pa (DST)
Fed5pa (DST)
Figure 4: FedSpa (DST) under different sparsity. Numbers in the labels are sparsity.
Table 3: Performance of FedSpa (DST) under different sparsity settings.
Non-iid
iid
Sparsity
0=022
7=0.1
Acc
Comm Cost
FLOPs
Acc
Comm Cost
FLOPs
Acc
Comm Cost
FLOPs
(Ic16)
(GB)
(1c16)
(GB)
(Ic16)
0.2
01.5+
718.1
8.2
62.9+0.4
718.1
65.5+00.5
718.1
8.2
0.4
45.5+009
538.6
7.6
61.4+066
$38.6
7.5
67.2+0.4
538.6
7.5
0.5
41.5
448.8
7.1
59.0+..0
448.8
7.0
66.91.0.2
448.8
7.0
0.6
38.4+0.6
359.0
6.5
57.3+1.5
359.0
6.5
65.2+00.2
359.0
6.5
0.8
32.0++077
179.5
49.2+
179.5
4.6
56.7+-0.8
179.5
4.6
standing effect of ERK initialization in improving overall training performance over the centralized training primitive, but it remains unexplored how it performs in proposed distributed training framework. Below, we show in Figure how accuracy evolves with communication rounds under ERK and Uniform initialization. As shown, drastic drop of accuracy observed by replacing ERK with Uniform, by which we conclude that ERK an essential component for FedSpa (DST).
Non-llD (y- 0.2)
Non-113 ty 0.3)
Accuracy
3.4
CITAR100
Communication Rounds
Communicaton Rounds
Communication Roundss
Fod5ps
Figure 5: Layer-wise sparsity initialized by ERK Uniform. Sparsity of FedSpa is fixed 0.5.
However, though a significant accuracy enhancement is observed, we note that integrating ERK may sacrifice potentially more FLOPS reduction. This observation can be found Table 6, wherein our results show that initialization with Uniform can save 34.3% FLOPs of that with ERK.
Table 4: Performance of FedSpa under ERK and Uniform initialization.
Non-iid
iid
Methods
7=0.2
7=
Acc
Comm Cost
FLOPS
Acc
Comm Cost (GB)
FLOPS
Acc
Comm Cost
FLOPs
(GB)
(1c16)
(1c16)
(GB)
(1e16)
ERK
41.5-10.5
448.8
7.1
59.0 1.0
448.8
7.0
66.9-0,2
448.8
7,0
Uniform
13.0+ 1.4
448.8
4.6
49.3++0.9
448.8
4.6
1..3+1.1
448.8
4.6
Different or same mask initialization. Recall that based on the layer-wise sparsity calculated by ERK, FedSpa uses the same random seed to initialize the mask, as make the mask exploration
Uniformm enforces the sparsity for all the layers in model.
15

---

Under review as a conference paper at ICLR 2022
of all clients started from the same mask. In the following, give another implementation that allows each client to share different masks in the beginning.
As shown in Figure 6, suprisingly find that for FedSpa (DST), maintaining different masks in initialization may slightly enhance its training performance in IID and Non-IID (7 = 0.2) setting. We hypothesize that by different mask initialization, each client could more efficiently search for their optimal masks that better represents the features and labels of the personal data.
IID
Non-lID
Non 0.33
ALcuracy
3.5
0.5
CIFAR100
0.7
0.1
80
30
203
409
300
200
400
80
380
803
800
10X
Fed5pa (DST, same intialiatioon)
RedSpa (PSN same intialiation))
FedSpa (DST, different intializzaion)
FedSpa (RSM, differant intialzation)
Figure 6: Initialization based on same or different masks. Sparsity of FedSpa is fixed to O.5.
For FedSpa (RSM), compared with initialization using the same mask, different mask initialization may result drastic performance loss in the IID setting, and significant improvement in the Non- III) setting. With the same mask initialization of RSM, each client consistently trains based on the same sub-network, which completely eliminates personalization. So this setting shares similar per- formance with FedAvg with satisfactory performance in IID setting and rather weak performance in Non-IID setting. On contrary, by initializing different masks the beginning, FedSpa (RSM) re- serves some degrees of personalization, since only the intersected coordinates in their local models are shared and updated by the information exchange (i.e., average) process. Consequently. FedSpa (RSM) with different mask initializations has similar performance pattern with FedSpa (DST).
Another interesting observation is that FedSpa (RSM) with different mask initialization cannot out- perform FedSpa (DST) in both the two groups of Non-IID settings. This indicates that the DST mask searching process effective to achieve superior performance FedSpa in Non-IID setting.
Weight recovery w/ or w/o gradient information. Recall that in FedSpa (DST), proposed to use gradient information to recover the pruned weights, which is empirically proven in (Evci et al., 2020) outperform its random recovery counterpart in Set (Mocanu al., 2018). Specifically, recovery, the weight coordinates with the top-a, magnitude of the
for gradient information-bas gradient would be recovered, while for random recovery, the coordinates are recovered randomly. To demonstrate the impact of the weight recovery method over FedSpa (DST), in Figure 7, we compare the gradient information-bas based recovery with random recovery. Our experimental result demonstrates that recovery with gradient information could slightly accelerate the convergence and enhance the final accuracy our FedSpa framework.
0.20
1.5
3.5
Accuracy
2.4
0.5
Communication
Communication Rounds
Communication Rounds
Fedipp (US) with gradient invormation)
Fed5pa (US) with random recovery)
Figure 7: Recovery with gradient information or random recovery. Sparsity is fixed to 0.5.
Global model vs. Personalized model. In our main experimental result, all the testings are con- ducted by clients based on their own personalized models. But it is interesting evaluate whether
16

---

Under review as a conference paper at ICLR 2022
Table Wall time of FedSpa (DST) for local training and mask searching.
Wall Time (Train)
Wall Time
Ratio
Task
(Mask Search)
(Mask Search/Train)
EMNIST-LeNet (CPU)
1.03++0.04s
0.09:10.0s
8.92%+006
CIFAR 10- VGGG (CPU)
11.4+0.25s
2.19=0011s
19.19%=11.0
CIFAR 100-Resnete (CPU)
28.61:10.38s
3.7::0.28s
12.93%:+1.08
EMNIST-LeNetS (GPU)
0.39:L0.01s
0.02:10.0s
5.66%.11025
CIFARIO- LGGGI (GPU)
1.56:+0.03s
0.22+0001s
14.3%=10.48
CIFARI00 100-Resnet11188 (GPU)
2.71+0001s
0.33#0.01s
12.06%40.2
the global model trained by FedSpa itself could converge, or even could achieve commensurate per- formance with the global model trained by general FL solution (e.g. FedAvg). As demonstrated by Figure 8, we empirically find that in the IID setting, the global model trained by FedSpa cannot recover the performance of that trained by FedAvg, and a considerable performance drop also ob- served in the Non-IID setting. Another observation is that the global model of FedSpa surprisingly maintains roughly the same performance as its personalized models in the IID setting, but conceiv- ably suffers significant performance loss in the Non-IID setting. This corroborates our conclusion that net-nesworks extracted from a global model may potentially outperform the full model, under the condition that the data distributions of clients are skewed (or heterogeneous).
Non-llD (y- 0.2)
Non-112 by 0.33
Accuracy
3.4
CIFAR100
Communication Rounds
Communication Rounds
Communication Rounds
Fedduy Iglobal
Figure 8: Global model Personalized models. Sparsity of FedSpa is fixed 0.5.
Wall time. Recall that do additional mask searching procedure in FedSpa (DST), which might possibly induce extra wall time on the local devices. We show in Table 5 the wall time used for training and mask searching one single local round. The sparsity used for this experiment is fixed to 0.5, while other parameters remain the default setting (see Section 5.1). We use one single 1080Ti to perform training for the GPU-based experiment, while the CPU-based experiment conducted on an Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz with 8 cores. Our experimental results confirm that the mask searching process only accounts for small portion of wall time (approximately 5% 20%) for the entire computation time on the local devices.
C PROOF OF THEOREM
In this section, for sake of readability, we first clarify the notations and reiterate several facts that we use in our proof. Then present several lemmas that are commonly used in the FL literature (see (Karimireddy et al., 2020; Xu et al., 2021)). Later, several key lemmas are listed with exhaustive proof, and finally, the proof of our main theorem is given by exploiting the listed lemmas and facts.
C.I NOTATIONS AND FACTS
Throughout the proof, we assume Σ, equivalent to EN-1 Σe equivalent to Σ and Σn.r equivalent to Σ EN-1 unless otherwise specified. In proof, we reuse most of the notations
17

---

Under review as a conference paper at ICLR 2022
from problem formulation part. We use Jk.t.r (w.,,,)) V V, S to denote the stochastic gradient of client in round and at step т.
Then as per formulation in Section 4.1, reiterate the following facts, which would be heavily used in our proof.
Fact 1 (Local step). As per Eq. (3), one local step client's update can be formalized follows:
Wk,t Wk,t,r - 1, @ 9k,t, (10k,,))
(6)
where 9k.t.r (W0,,,,) is the stochastic gradient over the sparse model weights W..t. and WR,00 ma, @ w, is the synchronized local weights at the beginning of communication round.
Fact 2 (Local update from client k). The local update of clients can be formalized as follows:
U 20,,1.0 WK,,I =
Σ ma,t C (1
Fact (Server's update). The server aggregates the sparse update by averaging, which can be formalized as follows:
W++1 =w:
EU. = wi
Σ
ma, O -h.a,-
(8)
S
KESt
RESUT
Fact 4 (Global and local loss). The local loss of a client is denoted by Fu (ip)), and is formulated
Fa((0)) = (LC(a,))) (wxx (x, a))]
(9)
where wy mig u, and the global loss be formalized as follows:
1 K
f(w)
Σ
FR (w
K Σ Fa(m @ w)
(10)
K
k=1
and {m,) in the function are viewed as optimal personalized masks which satisfies the sparse volume constraint ||1 mi = 3 for all k.
C.2 AUXILIARY LEMMAS
In the following. we shall present several common lemmas that are heavily used in the FL literature. Lemma (Cauchy-Schwarz)) Assume arbitrary vector sequences {a Cauchy-Schwarz inequality implies:
I....KK k= and (bs) kkm I==......f I.....K.. K
Σ
Σanbi
anbb
|aull?
Σ |bbal?
(11)
by taking by 1, we also have:
K
K Σ k=1
K
|ar11
(12)
A=1
Lemma 2 (Separating mean and variance, Lemma B.3 (Xu et al., 2021)). Let (ai...., a be random vectors in Rgd Suppose that {a, - {.} form martingale difference sequence, i.e. E [a: & a....., = 0, and suppose that their variance is bounded by E |la; 1 s 0². Then, the following inequality holds:
E
a
<
Σ
2TO²
Lemma 3 (Relaxed triangle inequality, Lemma 3 (Karimireddy et al., 2020)), Let v; and v, be vectors in Rd, Then the following inequality holds true for any 0:
|1 + 11,1 2 $ (1 a) 12 + (1 a 10,1112
(13)
18

---

Under review as a conference paper at ICLR 2022
Lemma 4. For random vector v satisfying [[vi]] =
and assume another random vector
U2 is independent with U1, we have:
11 + =21l = v1 1 + 0
(14)
Proof.
1l + u2|l = B( + 02 1 + U2)
E||e 2 + 1 1| 21 v2)
(15)
Bl|eil! 2| + 2 + 2(EU1 Ev2)
Bll +| B|
This completes the proof.
C.3 KEY LEMMAS
In this section, we present several important lemmas that would be used in our formal proof. All the presented claims rigorously proved.
Lemma 5 (Smoothness of f(w)). Assume we m @ w for any m {0, we have L--
smoothness for f(w) = 1
K Σx (w))), ie., for any wr, w2 Rdd we have:
[V/((w)) ( S L.[w:: - w2ll-
(16)
Proof.
[V](w)) -V(w))
m O V. @ w1) m C (F. c w2))
K
k
K mm @ (VFa(m) ① w/) (m 1 w2))
Σ | @ w1) (m @ w2)l
(17)
(a)
Σ
m O (w) w2)ll
K
< L wi
w2ll
where the first equality holds by the Fact and inequality (a) is due Assumption 3, This completes the proof.
Lemma 6 (Separating mean and variance of stochastic gradient). For mk, E {0, 1)a We have the following bounding for the expected average gradient:
2No²
E,
Σ
mi.t @ Ikster (WER
2
Σ
ma.
S
kES..T
KES..T
(18)
where [.]] denotes the expectation all the randomness of round t.
19

---

Under review as a conference paper at ICLR 2022
Proof. We view m,,t C Ir.t.r (WK,1,7) for all & and as stochastic vectors. By the unbiasedness of stochastic gradient, we know their variance satisfies:
5 m o (u E 5 mas guar ( 1
a ④ (0R,,,,(0üK,..7 (FE(WRR)))))
5
(19)
gh..t (100,,,)) VFr
52
o²
52
where the first inequality holds since my,t E (0, 1] and the last inequality is due Assumption 2. As per the variance given above, and directly apply Lemma 2, the claim immediately shows.
Lemma 7. We have the the following error bound by introducing personalized masks:
m - < VV (
(woH,)) + dist(mxx. m
(20)
and,
3(d- K
Σ
B² (dist(mu. disst m):)
l
(21)
where dist(m:, m2) is the hamming distance between masks.
Proof. Let V (t0k.,).)) and Fi (10k))) be the derivative over the j-th weight coordinates. Define the support of vector v E Rd as supp(v) {i u(i) * 0}. The left hand side of the first claim can be rewritten and bounded as follows:
| Fi m (
Σ
F( (a
jEsupp( ( ( (mp
Σ
F
|| Fe (uba,.)))
Esuppl ma Jundy (Tra)
desupp(mr (maup jundd
Σ
|ل
F
Σ
B²
jEsupp m. (sspp((;)))
jEsupp(ma,
Σ
(( Fi (( + dist(mmre. m B²
jEsupp! me. (2)
| F(
( Fi( dist(ma,, m2
V Fa((E,,..) - (Fg( däst m
(22)
where inequality (a) is true since have () Fg (w.x...))l B² and ( Fg (1) < Ba by coordinate-we wise bounded gradient Assumption Inequality (b) is due to the definition of hamming distance, dist( U1, 02) Ejesupp(o (wa)). This shows first claim.
20

---

Under review as a conference paper at ICLR 2022
Following the same technique, expand the left hand side of the second claim using Cauchy Schwarz inequality in Lemma 1, as follows:
|m (Fe(W)))) [[(w))]
1
= -| FFL(Wk,))
Σ
m O V. (ww .)l
K
R
O (
Σ mk,t O (
K
3|1
m,g
(EK(( my (F 11)
+ 3
m it O (ww m V (ww,
K
m3 @ (20x,))
ma.t @ VFW Σ
(23)
K
&
+
Σ
mkx @ ( my o (
K
3
+
(mwr O (Fw my o FF
K
<3(d-8)0
+
3
dist(ma.t. my ,)² +
3
Σ
dist(m m )B²
K
K
3) + K B² (dist(mpp. mw,)) + dist(mmysr mj.))
Σ
For the last inequality, we use the same technique as in the first claim bound the second term and the third term, and the first term is bounded by Lemma 8.
Lemma 8. Let ||1 - mllo = 3 be the sparse volume of a mask m. and suppose m E {0, 134, by assumption 4, we have the following relation:
|l (VFa(Wns))
Σ
sd- B)
(24)
K
K
and,
Σ m
(
+ BB²
(25)
K
where d is the dimension of the models (or identically, the dimension of the mask m.).
Proof. The proof of this lemma follows similar technique in Lemma 7. Let ((5 Fa (20x.)) be the derivative over the j-th weight coordinate. Define the support of vector IRd supp( v) (j v(5) # 0}. The left hand side (L.H.S) of our first claim can be bounded by:
1 Σ Fy (wx
m @ (VFg(W)..)
-
K
Σ (.
(26)
K
(Esupp(m))
<(d - G
where the last inequality is obtained from the sparsity constraint and the coordinate- wise gradient dissimilarity Assumption 1. This shows first claim.
21

---

Under review as a conference paper at ICLR 2022
For our second claim, expand its L.H.S follows:
1 Σ m
[[VF((t
VP.((ww..))
K
| FA(u..))
v (w Σ
Σ spsupp(m)
(27)
K
jEsupp(m) <(d-8)G* + 3B²
where the last inequality is due to Assumption and Assumption 4. It completes the proof.
Lemma 9 (Drift towards Synchronized Point). For any E .T.....TT.... T E {o...., N}. and learning rate satisfies 1) S I6LN. we have the following claim:
Σ E, [1 w S5NT) + 18N4)) + V K
(28)
where & 1 En((d - 3)G² + & Ex (distt me + dist(mg mi))) and E+H]] denotes the expectation over all the randomness of round t.
Proof. We follow the basic techniques from (Reddi et al., 2020) to prove this lemma.
We first assume that:
m -h.tr 1 ma,t Vi (WN,,.TT
m,k O (F(((W,,,)7111) - -ma ④ ((i(t)))))
Q m&,t O F& (((r))
We can expand Uk,,, as follows:
E. [1 - -
K
A
Fast
Be [1 1. 17mi,t ② - (10.r.--00 =1]1]
K
w. - P P ((w))))1
K
(29)
k
+
6N K
2N
Ex 1.llr -20=112 +
E111012 +
K
K
2 K
Σ
EIQ +
Σ
V f(w)1)
K
where the last inequality follows from Lemma and Lemma 4. Explicitly, we use Lemma 4 to treat the stochastic term with EE, | and then we use Lemma 3 with a = 2N to separate the other four terms.
Then we proceed by separately bounding the components the above inequality.
Bounding the second term:
B111012 =
E2 m @ 1.B..--((DDE..---- m ④ V (
K
K
Er m (9 V (1)x,,,-1)))
K
(30)
<
Ex, E - -aiioirrrr---ii(iaa.... -VE(((
K
< 17 2)²
22

---

Under review as a conference paper at ICLR 2022
where the last inequality holds by Assumption 2. Bounding the third term:
6
Eel
Eg mag 3 VFi((RAr-1) Mxk, O Vi (1l
K
K
2
E, (
(31)
K
&
2 L2
Er - wx,e|l -0k,e1 Σ
K
Bounding the fourth term:
6
6N
Eell m C VFp((0x,)) - Vs(w;))1
(32)
K
18N 2
Σ
Bd + Σ B² (dist(ma,, my)) + dist(mp mmm)))
K
where we use the second claim in Lemma 7 in the last inequality.
Let t = x (dd R Ev B² ([dist(mm.. mw.+) + dist((me;s m..)). The bound can be simplified as follows:
Σ
E. Q11 < 18.
(33)
K
Putting together: Plugging all the components into (2,, the following result immediately follows:
E. [100et 2
K
1
1
<(1 +
+ L2)
E, Wh - -00,1l +17002 + 18N7 + +NN7
2N -1
K
1
<(1 + N - 1 K
Eg Bel12xk,1.7-
wp + 702 18 (
(34)
where the last inequlity holds by our assumption 16LN Unrolling the recursion, we obtain the following results:
Eg [laik.err - [22
K
(1 N [12(0² +
+ 18N+)
(35)
7=0
1 ~ -1) 112 + (6N
<(N - 1) (1
S5N1 + 18N4.) 30.2 1² [V
The last inequality holds since (1 (1+ - < 5 for N 2 1. This completes the proof.
23

---

Under review as a conference paper at ICLR 2022
C.4 FORMAL PROOF
We start our proof by expanding s(w(+1) under its smoothness condition (see Lemma 5), which indicates that:
E4 [J (we+1) wi]
L
Sf(w))- - (V (Ww())) (ro0)),BB(eure Be(we(1 wil) Ezl
11/111411 will
2
1 Σ Un,tt )
Faet ff (ww) T
V (w.))
+ E
En
1 Σ
Uk!t
3
kES.
kE
2
Fact 2 ((we))
17
NV f (we) 1EF,
ma,t 2 ViFk(Uk,
+
Σ
Unit
N
K
2
S
R,T
kES
<((w))
N
|V (w:) 112
E2
Σ
ma.t 2 (FL((Ok
NV (wx) 112
2
2N
K
Ti
L
+
R4
U
2
kE
T2
(36)
where the last inequality holds since -a S ((b a)² -a²), and R&[-] is the expectation over all the randomness in round t.
In the following, we shall separately bound Tj and T2.
Bounding Ti:
7 T
Eell Σ
m
O V.g(WLLLT)) - (w,)
2N
R,T
Fact
7
Ezll
Σ
mk.t C ( - N K Σ mi @ (wx,
2N
K
k,T
17 2N
E.ll
(mg O V.L( m O FF.(w..)))
K
K.T
(37)
(0)
1
E2
m O V.h(Wke.)) - mi c (Fr(Wu)))
2K
K.T
(6)
1
[(IVFr - Vi (xin.))) disl(ma.t. m))BB
2K
112
w. +
Σ dist m B²
2K
2K
where inequality (a) is due to Seuchy-Schward inequality (i.c., Lemma 1), (b) follows from the first claim in Lemma 7, and the last incquality holds by Assumption 3.
Plugging the results of Lemma 9, we obtain that:
n
N
Ti <
(5 11NN 30. |
(11)
dist( m2)
2K
(38)
5 3T2
nN Σ dist m B²
<
(02 + +1N4,, - 15,33
2
2K
24

---

Under review as a conference paper at ICLR 2022
Bounding T3:
T2 2 Ee
Ukit
S
RESt
Fact 2 LIf
Bt
Σ kES..7
ma,t gk,t. (10k,57)
S
(39)
(0)
N L
< Tny
Σ
ma,t @ (
+
S
S
kES
1
N
N
Σ E,
mkkt O (.E(
S
S
RES,
T3
where (a) obtained as per Lemma
Bounding Tz:
T3
E, g2
1
IiEss) mis @ (F(W...)))
Σ
[sES, mj m (2)(2))..))
Vi(KK
jE[K]
1 E, 52
Σ
Es. (ssssssssjs) (mi, O VF((W..)) m2s C VF
+ Σ
Es, (iess)ls)) C (F(
1 E,
Σ
-(S-1)
(mi. & VF(( m2 O (F + Σ S
mm, O (.
5
K(K 1)
K
S(S -(8-1) 1)
E,
(m; O (w) m2a O (
5
K(K 11)
(JE(K]
Σ S(K-S)
m, O (w),,,))))
K(K 1)
(K S)
E
Σ may & (Fg(
Σ
K2
SK(K 1)
T4
Ts
(40)
where the last inequality holds since
S-1
S-1
S
SK -1]
SK=
SK3
R
25

---

Under review as a conference paper at ICLR 2022
Bounding Tı:
T4
m V.r(We..) v[(w:)) V f(ww))
K
k
Lemma
S 2
- K mRi 3 VFr((u,,.)) - vs(w)))
+ + ((w))]
Faet 2
m VFF(WR..))) m3 o (wx,,))))))
+ +2|lVf(wo))l
(41)
Lemmal
-
| O VFe(Ws..)) m F Wp
[[
K
Lemma
S
(II Fi (WWN,,)))
F mis. + 2
K
21
2 " +
Σ
+2
K
K
where the last inequality is obtained by the L-smoothness Assumption 3.
Bounding Ts:
TB = (K -S 5)
mmg. O (
SK(K 1) k
3(K- - -)
SK(K 1) 1) Σ
E(|mm C (Fe((E,, - ma,t O Fi )|
| ((b( [[(w))]] + [[(((1)))
(a) 3L2 -S)
Σ | 2 2 3(K 5)
S(K - 1)K Σ - -
(42)
SK(K - 1)
3(K S)
Σ (dist(mm.. (w..mm...m).))) + dist(mw,,,
|| ((w)))
S(K 1)
3L2 K
T.KL. wx,ell + --, + fllVf(
K-S S under the condition S > 1. Inequality (a) is where the last inequality holds since S(K
obtained by Assumption and the second claim in Lemma 7
Summing T4 and Tú, we have the following bounding for Ty:
5122 Ts S K
Σ
11 We + K
Σ
dist(ma,s, mi) B² -Db + {[m)))
(43)
Plugging Lemma 9 into the above inequality, we have:
T3
2 K
<5L² (5 18N4,) + 30N' (V
+
Σ dist(mx... m + 9 + +5\W)(
N 18N4,) + (150N2, + 5) V 11
+
Σ K
dist (emtm. + 94,
(44)
Plugging T3 into Inequality (39), we bound T2 follows:
To S(150N4 5La/ N2) [ 25, 1 N3 18N
N2 T, dist m B² + 97² N2 L
NT
(45)
+
K
S
26

---

Under review as a conference paper at ICLR 2022
Plugging T2 and 7i into R.H.S of Inequality (36), we obtain that:
B[f w.)) - f (wi) - n,11 1 1500211 5L - 15N2 I (an:) 11
+ +255m 1
(o² + 18N + 4n n
Σ dist(ma,t,mG) m
2K
2
+ 91 L +
s
(46)
Taking expectation over the randomness before round / towards both sides of the inequality, it yields:
E [f (wx+1)) - Elf (w:)) Ny (wx) + PL-
(47)
where 3/2 150 15 5N and Pt (25 SN 18 + 1N Σx dist m B + 9) Lbb NoP
2K
By rearanging, and summing from t = , T 1, the following result immediately shows:
E [f (wo) E (wT))
1
Σ
Vf (w:) 113
Σ
Pe
T
TyNN
T
t=u
(48)
I (wo) f (wn)
T-1
Σ
Pt
TyNK
Now we bound the local gradient over the personalized sparse model:
T-1
1
FlIV (1
TK
1= k=1
1 TK
F (mxr.) vf(w.)++ V
t=0 k=1
T-1
K
Lemmu
3
Σ K
m c VFw
TK
K
1=0 k=1
1
+||
(mi O ((r( m O V Fi .)) + (w:))1
K
(a) 3
T-1 K
1
3
T-1
(dd ((d-3)) BBG- -BG+++BB +33
dist(m), meimmm,,i..BB" +
E
V
1(w)))
TK
K
TK
T-1 K
1old-3100 03 + +33B2 + K2 ΣΣ
dist dist(mi, B² +
TK E
Σ
(fw,))]
(49)
In inequality (a), we use the second claim in Lemma 8 to treat the first term, and the second term is bounded using a similar technique as in the first claim in Lemma 8.
Let Y = 3(d - G2 + 3 + K² Ex Ex dist(m;,, my mm B² and plugging inequality (48) into the above inequality, it further implies that:
3
T-1 K
3( (wo) - f (w=))
3 T-1
ΣΣ
E V (
Pt
+
Y
(50)
TK
TnNN
T
k=
1=0
This shows the claim.
27

---

Under review as a conference paper at ICLR 2022
D DISCUSSION ON VARIOUS BOUNDS IN EXISTING STUDY
Under the non-convex setting, Theorem 1 bounds the squared gradient norm of the personalized iterates over the local loss. Existing studies on PFL zero in various different kinds of convergence bound, and under different assumptions. Below are some concrete examples:
Li et al. (2021) study the upper bound of IE | w=ll? for any device & (see their Corollary 1), where Wx,T is the personalized weights iteration T and wi the optimal weights under the client k's local loss. Under the assumption of strongly convex, smoothness, bounded gradient, and gradient dissimilarity, as well as an additional assumption on the distance between personalized models and the optimal global model, it is theoretically proved that the proposed solution, named Ditto, achieves O(1/T) convergence rate, Their derived convergence rate is on the same scale the convergence rate of the global model produced by FedAvg, However, it is important to note that an extra assumption on the distance between personalized models and the optimal global model is required to achieve this rate.
Hanzely et al. (2021) study the convergence of the proposed regularization problem (see their Theorem 4.5). Specifically, they propose to bound Σ ( (())) where
-
WKTT the personalized model, and (A) is the optimal model for their defined regular- ization problem under the regularized hyper-parameter A. Under the strongly convex and smoothness assumption, the authors derive the bound as E E - (A)I S
| (A)] 2neo" Further, by applying the variance reduction tech- nique on their proposed L2GD solution, they eliminate the constant term (i.e., the second term) in the above bound. However, their convergence analysis regularized problem. remains unspecified about how and whether the personalized iteration produced by L2GD can achieve convergence towards the optimum for each client's 's local loss (i.e., the optimum of the ultimate PFL problem (P2)). In other words, the gap between W and we min., Fi(ww)) remains unknown.
(1-%)
2. ( E
made towards a special case of the
Under the non non-convex setting, Deng et al. (2020) study the upper bound of squared gradient norm, or formally, T E E V (wr,,)) (see their Theorem 6) where tZ is the personalized
() is the gradient a model over the local loss. Under the smoothness and bounded variance conditions, they derive bound with rate O( (T))) convergence. Similar our results, non-vanished residual presents in their bound. This non-vanished residual is related to: i) the gradient dissimilarity between clients' local loss function; and (ii) the gradient discrepancy, The form of this non-van vanished term highly similar to our derived residual term (i.e., T in our Theorem 5), since both the gradient dissimilarity factor (i.e., G in Assumption 1) and gradient bound (i.c., B in Assumption 4) would present in the non-vanished residual. Additionally, when the personalized factor is completely climinated i.c.. og - 0 in their formulation or 8 - d our formulation, the non-venished residual (i.e., I in their formulation and Y ours) would both become significant to dominate the bound.
model for client & and (.)
28


Reviews:
[{"review_id": "Rx1aMF36e8A", "reviewer": "Reviewer_Zg2F", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**1.** The idea of using sparse masks to model personalization for federated learning is not novel in this work. Prior works utilize this idea with other techniques (Li et al., 2020) (Vahidian et al., 2021). Moreover, several side-benefits such as low communication cost, cheaper computation, and fewer memory requirements should also be attributed to those original works where sparse masks are used, and the same side-benefits of sparsity were mentioned.\n\n**2.** As far as I can see, the idea of current work that differs from the above two mentioned papers is how the sparse masks are handled throughout the training process. However, there does not seem to be done much progress in this direction neither. The authors nominate two heuristics on how to evolve sparse masks over the iterates, one of which is simply fixing the same mask for all clients and iterations. However, isn’t it the same as initially training the smaller model for all clients?\n\n**3.** It was mentioned in the contributions that the problem of sparse PFL is rigorously formulated (I guess this refers to the last part of section 3, Sparse PFL problem (P4)). However, you do not provide a deeper understating of this formulation, e.g., How well it models personalization compared to other formulations? Why it makes sense to use a small subset of the global model (i.e., sparse masks) as the local, personalized model beyond what was heuristically proposed by (Li et al., 2020) (Vahidian et al., 2021)? Can the formulation (P4) be regarded as a particular case of regularized PFL (P3), say with $l_1$ norm?\n\n**4.** The algorithm FedSpa seems to directly apply FedAvg (LocalSGD with partial participation) to the problem (P4). What is the novelty in the algorithm itself?\n\n**5.** Theoretical analysis is very weak. Let us ignore the first two terms in the rate (5) and consider the third non-vanishing term $\\Upsilon$. Using only Assumption 4 and running any method, one can upper bound the left-hand side of (5) by $d B^2$.\n\n**6.** The title is somehow vague and does not describe the work well. The paper is on personalized federated learning, which is not reflected in the title.\n", "summary_of_the_paper": "This work studies personalized federated learning through sparse local masks. For each client, the local model is subset of the global model. The paper proposes and analysis a new method, named FedSpa, which trains sparse local models for all clients reducing communication size, the amount of computation and memory cost.", "summary_of_the_review": "The level of originality is low given the prior works. A new formulation lacks deeper understanding and theoretical analysis is weak.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Alp5lsDuJfC", "reviewer": "Reviewer_PGV4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: Addressing the data heterogeneity and reducing communication cost are an important problems in federated learning. Using one architecture for all local models and different sparse masks seems a new idea in the field.\n\nWeaknesses: 1) At every iteration, the Algorithm 1 FedSpa requires new masks to be computed, which highly increases the computational time on local machines. The experiments results only report the communication time without the total running time. It is not clear whether the wall clock time can be reduced or the contrary. Also the FedSpa requires communication every iteration which causes more communication cost.\n \n2) One merit of using sparse masking is that it reduces the communication memory size and the Table 1 measures the communication cost in terms of GB, so a natural baseline would be FedAvg with compression techniques. A lack of such comparison makes the true effect of sparse masking questionable. ", "summary_of_the_paper": "This submission proposes federated learning with personalized sparse mask (FedSpa) to apply sparse masks to the local models in training and communication, hence to make the model adaptive to its local data and also to reduce communication cost.\n", "summary_of_the_review": "This paper has proposed a new method to address the heterogeneously distributed data problem in federated learning. However, the algorithms has some impractical components and the effects over state-of-the-art is not convincing enough due to lack of some baselines. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8kv_uKyAQqu", "reviewer": "Reviewer_mQ15", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1: This paper proposes a novel personalized federated learning scheme by incorporating sparse-to-sparse searching techniques.\n\n2: Extensive experiments are conducted to verify the superiority of the proposed algorithm.\n\n3: This paper is well-written and easy to follow. The background knowledge is presented well. The readers can easily understand the paper.\n\nWeaknesses:\n\n1: The theoretical analysis in Theorem 1 is unclear and weak. It is unclear that what the error bound in Theorem 1 means. The authors need to analyze and compare the theoretical results to other comparable methods. \n\n2: The title is ambiguous and may lead to inappropriate reviewers.\n\n3: I see no code attached to this submission, which makes me a bit concerned about reproducibility.\n\n", "summary_of_the_paper": "This paper studies personalized sparse training for federated learning. The proposed method FedSpa is a novel personalized federated learning scheme that employs personalized sparse masks to customize sparse local models on the edge.  The authors provide the theoretical result with regard to the error bound and empirical results with several personalized federated learning methods.", "summary_of_the_review": "I marginally accept this paper mainly due to its novelty and better experimental results. \n\nAfter reading the response, I keep my score at 6.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0Gdbi5-h8XB", "reviewer": "Reviewer_ECdR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My main comments are : \n\n* The level or rigour needs to be improved. As a case in point, already the title suggests that the notion of \"sparsity\" \nis crucial for the proposed approach. However, i was not able to find a rigorous definition of the quantity \"sparsity\". \n\n* In my opinion the novelty of the proposed approach is limited. First of all, the sparse FPL problem is a special \ncase of the regularized FPL problem (3) using a specific choice for the regulariser (requiring the non-zero entries \nof the i-th weight to agree for all clients. The regularised FPL has been studied in a sparse model context recently e.g. in \n\n* M.Yamada, T. Koh, T. Iwata, J. Shawe-Taylor and S. Kaski, \"Localized Lasso for High-Dimensional Regression\", Proc. AISTATS 2017 \n* A. Jung, “Networked Exponential Families For Big Data over Networks,” in IEEE Access, Oct. 2020. doi: 10.1109/ACCESS.2020.3033817.\n* Y. Sarcheshmehpour, M. Leinonen, A. Jung, “Federated Learning from Big Data over Networks,” to be presented at IEEE Int. Conf. on Acoustics, Speech and Sig. Proc., 2021.\n\nit might be useful to compare your approach with the (generalised linear model based) methods proposed in above papers. \n\n* The FedSpa algorithm seems to be a straightforward combination of existing techniques (stochastic gradient descent and masking search techniques \nfor sparse deep net training). \n\n* The relevance and usefulness of Theorem 1 is unclear. How did you use Theorem 1 for applying FedSpa (e.g., choice of hyper-parameters) \nin the numerical experiments of Section 5? Im also not sure if (5) can be referred to as \"error bound\" as it actually \nbounds the gradient of the objective function along the trajectory of the algorithm. However, the numerical experiments do not \nuse this gradient as the figure of merit but the resulting accuracy. How is (5) relevant for bounding the accuracy of FedSpa? \n\n* The clarity or presentation and use of language needs significant improvement: \n\n- what are \"fully dense PFL models\" ? \n- what is \"consistently cheap communication\"? \n- \"The Non-IID data distribution makes the training process prohibitively difficult, and the obtained global model may not fit all the local data.\" \ntry to be more specific \n- \".. is another challenging problem that remains mysterious.\" \n- \"FedSpa does not deploy a single global model, but allows each client to own its unique sparse model...\" this is a bit confusing as FedSpa actually tightly couples \nthe sparse model parameters of each client. as i understood, they must have the same non-zero weight value for each individual feature. \n- what is a \"evolutionary sparse model\" ?\n- \"... which is agnostic to all kinds of network architectures ...\" with is meant by \"being agnostic\" here ? i believe that at least the assumptions on the loss \nfunction somehow interact with the particular network architecture. \n\n- \"Experimental results ... also coincides with the theoretical conclusion.\" Pls explain more precisely what you mean by \"theoretical conclusion\".  \n\n- \"We emphasize that three main progresses are made towards the interpretable and SOTA compression-based PFL...\" interpretability is a hot topic in machine learning. \nHowever, it is not clear how your approach ensures interpretability. Why is FedSpa interpretable?\n\n- The masks appearing in (P4) need more discussion. Are these fixed but unknown (ground truth), or just some estimate. \n\n- \"Mimicking the data-parallel solution ...\" which solution are you referring here exactly? \n\n- \"The framework of FedSpa is extensible ...\"\n\n- would it be possible to avoid \"dist(m1,m2)\" by using the ell0 norm (which is already used elsewhere). \n\n- what is \"cosine annealing \" ? \n\n- pls explicitly state any input/hyperparamter used in Algorithm 1,2 3 E.g. Algorithm 3 might have a random seed as its input. \n\n- \"Our main focus of analysis is on the second and third non-vanished terms while communication round...\"\n\n- \" The result in Eq. (5) is highly related to setting of sparse volume,...\" ?\n\n- \" ... to perform update.\" which update ? \n", "summary_of_the_paper": "This paper proposes an interesting approach to FL with heterogeneous client data. The main idea is \nto learn a common weight vector for all clients but allow them to individually mask this global weight vector. \n\n****\nI appreciate the effort that authors put into adressing my concerns which have been partially covered. Thus, i have slighltly raised the grade of my recommendation. However, i would ask the area chair to verify if the authors have addressed all my concerns satisfactorily. In particular, im still not sure about the relation between (P4) and regularized PFL (P3) which is quite generic and also allows for reguarlizers that are indicator functions of sets. \n\n", "summary_of_the_review": "My main comments are : \n\n* The level or rigour needs to be improved. As a case in point, already the title suggests that the notion of \"sparsity\" \nis crucial for the proposed approach. However, i was not able to find a rigorous definition of the quantity \"sparsity\". \n\n* In my opinion the novelty of the proposed approach is limited. First of all, the sparse FPL problem is a special \ncase of the regularized FPL problem (3) using a specific choice for the regulariser (requiring the non-zero entries \nof the i-th weight to agree for all clients. The regularised FPL has been studied in a sparse model context recently e.g. in \n\n* M.Yamada, T. Koh, T. Iwata, J. Shawe-Taylor and S. Kaski, \"Localized Lasso for High-Dimensional Regression\", Proc. AISTATS 2017 \n* A. Jung, “Networked Exponential Families For Big Data over Networks,” in IEEE Access, Oct. 2020. doi: 10.1109/ACCESS.2020.3033817.\n* Y. Sarcheshmehpour, M. Leinonen, A. Jung, “Federated Learning from Big Data over Networks,” to be presented at IEEE Int. Conf. on Acoustics, Speech and Sig. Proc., 2021.\n\n\nit might be useful to compare your approach with the (generalised linear model based) methods proposed in above papers. \n\n* The FedSpa algorithm seems to be a straightforward combination of existing techniques (stochastic gradient descent and masking search techniques \nfor sparse deep net training). \n\n* The relevance and usefulness of Theorem 1 is unclear. How did you use Theorem 1 for applying FedSpa (e.g., choice of hyper-parameters) \nin the numerical experiments of Section 5? Im also not sure if (5) can be referred to as \"error bound\" as it actually \nbounds the gradient of the objective function along the trajectory of the algorithm. However, the numerical experiments do not \nuse this gradient as the figure of merit but the resulting accuracy. How is (5) relevant for bounding the accuracy of FedSpa? \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear authors,

I have carefully read the reviews, rebuttals and the subsequent discussion. The review scores are mixed (5, 5, 6, 6). Let me comment on some of the key issues raised by the reviewers. I will elaborate on some of them with my own insights.

1) You insist that (P4) cannot be regarded as a particular case of (P3). But this is trivially incorrect. The hard constraint in the reformulation (P6) you mention in the discussion can be written as a regularizer: *indicator function* of the constraint set. Indeed, let  $\cal C$ be the set of points $W=(w_1,\dots,w_K)$ for which there exists $w$ such that $w_k = m_k^* \circ w$ for all $k$. Then the regularizer defined by ${\cal R}(W) = 0$ if $W\in {\cal C}$ and ${\cal R}(W) = +\infty$ if otherwise does the job. This is a well defined regularizer. Such regularizers are routinely used in optimization to model hard constraints. So, the formulation you consider is a special case of (P3).  Moreover, as pointed out by Reviewer Zg2F, and acknowledged by the authors, "The idea of using sparse masks to model personalization for federated learning is not novel in this work. Prior works utilize this idea with other techniques (Li et al., 2020) (Vahidian et al., 2021). Moreover, several side-benefits such as low communication cost, cheaper computation, and fewer memory requirements should also be attributed to those original works where sparse masks are used, and the same side-benefits of sparsity were mentioned." The claim that one of the novel contributions of FedSpa is "we formulate a clear optimization problem for FedSpa" is weak, especially in the light of the above comment, and the "moral" existence of the formulation in prior work, albeit not expressed in a mathematical notation. The fact that previous works did not formulate this properly is a major issue with those works, and not a major contribution of this work. A clear mathematical formulation of what one wants to achieve should be a standard requirement. In any case, I appreciate the clarity nevertheless. 

2) The same reviewer states that the key idea of the paper that differs from the above two mentioned papers is how the sparse masks are handled. One of the two ideas proposed is trivial and is equivalent to standard non-personalized FL (if all masks are the same, the submodes they defined can be considered a global model). The second idea does not seem to have any interesting/distinctive theoretical support. 

3) Sparse-to-sparse training in FedSpa may be novel, but the claim that "the masks continue to evolve (towards the optimal masks) in the training process" is not supported by theory nor experiments. If indeed you can show that the local masks evolve to some meaningful notion of an optimal mask, this would be interesting. 

4) I also agree with the other points raised by this reviewer. I have read the author response to these comments. (BTW: Language such as "you bet" is inappropriate). While some of them make sense, they do not reduce the severity of the concerns by a large enough margin. 

5) The comment about the weakness of the main theorem is particularly concerning. Indeed, the main theorem may be vacuous, and the authors need to do a thorough explanation of the result and its importance (on its own and in comparison with existing literature and rates). I do not believe such a comparison could be advantageous to the proposed method though. The expressions are complicated. It seems that for any meaningful mask size, the non-vanishing term will be too large. The theorem is not a valid convergence result as the authors do not show that the right hand side can indeed be provably made arbitrarily small by some choice of the parameters of the method. For instance, it is not guaranteed that $dist(m_{k,t}, m_k^*)$ will converge to zero. In this sense, calling this theorem "Convergence of personalized models" is incorrect and misleading. This is a fatal issue, unfortunately. The authors should make it absolutely clear that the result does not prove convergence. 

6) Assumptions 1, 2, and 4 are very strong. For example, Assumption 2 is not provably satisfied for lower bounded nonconvex smooth functions when subsampling (=minibatching) is used to produce the stochastic gradient. Assumption 3 is also quite strong: it is not satisfied by convex quadratics. Assumption 1 is also strong - most recent works on FL do not require any similarity assumptions. 

In summary, while this direction of research is interesting, the level of contributions in this work is marginal at best. The key theoretical result is misleading in that it does not imply convergence while it is marketed as such. Moreover, strong assumptions (relative to what is achieved in the latest papers) are used to obtain it. Because of these concerns, and other concerns raised by the reviewers, I do not have any other choice but to reject the paper.

Area Chair
Decision: Reject