Efficient Personalized Federated Learning via Sparse Model-Adaptation
Authors: Daoyuan Chen
Liuyi Yao
Dawei Gao
Bolin Ding
Yaliang Li
Venue: Submitted to ICLR 2023 (2023)
Keywords: Efficient Federated Learning
Personalization
Sparse Model-Adaptation

Abstract: Federated Learning (FL) aims to train machine learning models for multiple clients without sharing their own private data. Due to the heterogeneity of clients' local data distribution, recent studies explore the personalized FL that learns and deploys distinct local models with the help of auxiliary global models. However, the clients can be heterogeneous in terms of not only local data distribution, but also their computation and communication resources. The capacity and efficiency of personalized models are restricted by the lowest-resource clients, leading to sub-optimal performance and limited practicality of personalized FL. To overcome these challenges, we propose a novel approach named pFedGate for efficient personalized FL by adaptively and efficiently learning sparse local models. With a lightweight trainable gating layer, pFedGate enables clients to reach their full potential in model capacity by generating different sparse models accounting for both the heterogeneous data distributions and resource constraints. Meanwhile, the computation and communication efficiency are both improved thanks to the adaptability between the model sparsity and clients' resources. Further, we theoretically show that the proposed pFedGate has superior complexity with guaranteed convergence and generalization error. Extensive experiments show that pFedGate achieves superior global accuracy, individual accuracy and efficiency simultaneously over state-of-the-art methods, by up to 4.53\% accuracy improvement and 12x smaller model size. We also demonstrate that pFedGate performs better than competitors in the novel clients participation and partial clients participation scenarios, and can learn meaningful sparse local models adapted to different data distributions.

EFFICIENT PERSONALIZED FEDERATED LEARNING VIA SPARSE MODEL-ADAPTATICN
Anonymous authors
Paper under double-blind review
ABSTRACT
Federated Learning (FL) aims to train machine learning models for multiple clients without sharing their own private data. Due to the heterogeneity of clients' local data distribution, recent studies explore the personalized FL that learns and de- ploys distinct local models with the help of auxiliary global models. However, the clients can be heterogeneous in terms of not only local data distribution, but also their computation and communication resources. The capacity and efficiency of personalized models are restricted by the lowest-resource clients, leading to sub-optimal performance and limited practicality of personalized FL. To overcome these challenges, we propose a communication and computation efficient approach named pFedGate by adaptively and efficiently learning sparse local models. With a lightweight trainable gating layer, pFedGate enables clients to reach their full potential in model capacity by generating different sparse models accounting for both the heterogeneous data distributions and resource constraints. Meanwhile, the computation and communication efficiency are both improved thanks to the adaptability between the model sparsity and clients' resources. Further, theoret- ically show that the proposed pFedGate has superior complexity with guaranteed convergence and generalization error. Extensive experiments show that pFedGate achieves superior global accuracy, individual accuracy and efficiency simultane- ously over state-of- of-te-of-the-att -hrt methods. We also demonstrate that pFedGate performs better than competitors in the novel clients participation and partial clients partici- pation scenarios, and learn meaningful sparse local models adapted to different data distributions.
INTRODUCTION
Federated Learning (FL) gains increasing popularity in machine learning scenarios where the data are distributed in different places and can not be transmitted due to privacy concerns (Muhammad et al. 20200 Meng et al., 2021 Yu et al. 202T Hong et al., 2021 Yang et al., 2021). Typical FI. trains a unique global model from multiple data owners (clients) by transmitting and aggregating intermediate information with the help of centralized server (McMahan et al. 2017 Kairouz et al.
2021). Although using shared global model for all clients shows promising average performance, the inherent statistical heterogeneity among clients challenges the existence and convergence of the global model (Sattler et al.) 2020 Li et al., 2020). Recently, there are emerging efforts that introduce personalization into FL by learning and deploying distinct local models (Yang et al. 2019 Karimireddy et al.] 2020) Tan et al. (02T). The distinct models are designed particularly to fit the heterogencous local data distribution via techniques taking care of relationships between the global model and personalized local models, such as multi-task learning (Collins et al., 2022I) meta-lcarning (Dinh et al. 2020a), model mixture (Li et al., 2021c), knowledge distillation (Zhu et al. 2021 and
clustering (Ghosh et al.) 2020).
However, the heterogeneity among clients exists not only in local data distribution, but also in their computation and communication resources (Chai et al., 2019 2020). The lowest-resource clients restrict the capacity and efficiency of the personalized models due to the following reasons: (1) The adopted model architecture of all clients is usually assumed to be the same for aggregation compatibility and (2) The communication bandwidth and participation frequency of clients usually determine how much can they contribute to the model training of other clients and how fast can they agree to meet converged "central point" w.r.t their local models. This resource heterogeneity is

---

under-explored in most existing personalized FL (pFL) works, and instead, they gain the accuracy improvement with a large amount of additional computation or communication costs. Without special design taking the efficiency and resource heterogeneity into account, we can only gain sub-optimal performance and limited practicality of pFL..
To overcome these challenges, in this paper, we propose a novel method named pFedGate for efficient PFI., which learns to generate personalized sparse models based adaptive gated weights and different clients' resource constraints. Specifically, we introduce a lightweight trainable gating layer for each client, which predicts sparse, continues and block-wise gated weights and transforms the global model shared across all clients into personalized sparse one. The gated weights prediction conditioned on specific samples for better estimation of the heterogeneous data distributions. Thanks to the adaptability between the model sparsity and clients" resource, the personalized models and FL training process gain better computation and communication efficiency. As result, the model-adaption via sparse gated weights delivers the double benefit of personalization and efficiency: (1) The sparse model- paneel-adattion enables each client to reach its full potential in model capacity with no need for compatibility across other low-resouree clients, and to deal with a small and focused hypothesis space that restricted by the personalized sparsity and the local data distribution. (2) Different resource restrictions can be easily imposed the predicted weights block-wise masking under a flexible combinatorial optimization setting. We further provide space- time complexity analysis to show pFedGate' superiority over state-of-the-an (SOTA) methods, and provide theoretical guarantees for pFedGate in terms of its generalization and convergence.
consider the
We evaluate the proposed PFedGate on four FL benchmarks compared to several SOTA methods. We show that PFedGate achieves superior global accuracy, individual accuracy and efficiency simulta- neously (up to 4.53% average accuracy improvement with 12x smaller sparsity than the compared strongest pFL. method). We demonstrate the effectiveness and robustness of pFedGate the par- tial clients participation and novel clients participation scenarios. We also find that pFedGate can learn meaningful sparse local models adapted to different data distributions, and conduct various experiments to verify the necessity and effectiveness of pFedGatee components.
Our main contributions can be summarized as follows:
We exploit the potential of co-design of model compression and personalization in FL, and propose novel computation and communication efficient pFL. approach that learns to generate sparse local models with a fine-grind sample-level adaptation.
We provide a new formulation for the efficient pFL. considering the clients' heterogeneity in both local data distribution and hardware resources, and provide theoretical results about the generalization, convergence and complexity of the proposed method.
We achieve SOTA results on several FL benchmarks and illustrate the feasibility of gaining better efficiency and accuracy for pFL simultaneously. To facilitate further studies, we release our code at
2 RELATED WORKS
Personalized FL.
Personalized FL draws increasing attention as it is a natural way to improve
FL performance for heterogencous clients. Many efforts have been devoted via multi-task learning
Smmth et al. 2017 Corinzia & Buhmann, 2019: Huang et al., 2021: Marfoq et al. 2021). model
mixture (Zhang al. 2020 Li et al. 2021c), clustering (Briggs et al. 2020 /Sttler et al. 2020
Chai et al. 2020). knowledge distillation (Lin et al., 2020 Zhu et al. 2021:
2021aOzkara Ozkara et al. 2021
meta-learning (Khodak al., 2019 Jiang et al.] 2019 9 Khodak al.
2019
Fallah et al. 2020
Singhal et al. 2021), and transfer learning (Yang et al. 2020 He et al. 2020 Zhang et al.
2021a).
Although effective in accuracy improvements, most works pay the cost additional computation or
communication compared to non persoonnnd methods. For example, [Sattee et al. (2020) consider group-wise client relationships, requiring client-wise distance calculation that is computationally intensive in cross-device scenarios. Fallah et al.) (2020) leverage model agnostic meta learning to
enable fast local personalized training that requires computationally expensive second-order gradients. Zhang et al. (2021a) learn pair-wise client relationships and need to store and compute similarity matrix with square complexity w.r.. the number of clients. Marroq et al. (2021) learn mixture of multiple global models which multiplies the storing and communicating costs. Our work differs from these works by considering a practical setting that clients are heterogeneous in both the data distribution and hardware resources. Under this setting, we achieve personalization from novel
2

---

perspective, personalized sparse model-adaptation, and show the feasibility of gaining better accuracy, and computation and communication efficiency at the same time.
Efficient FI.. Fruitful FL. literatures have explored the improvement of communication efficiency
such as methods based on gradient compression (Rothchild et al.) 2020 Alistarh et al., 2017
Reisizadeh et al. [2200] Haddadpour et al., 2021 Zhang et al. [20 lb), model ensemble (Hamer et al.
2020h, model sub-parane sub-parameter sharing (Liang et al. 2020) sub-model selection Tianchun et al. 20022 :
Minh & Carl [021], and Bayesian neural network (Yurochkin et al. 2019b a). Few works improve
computation and communication efficiency with personalized local models via quantization (Ozkara
iet al. [021]] Li al. 2021a Hong et al.] (2022) and model parameter decoupling (Diao al.) 202 I
Collins et al. 2021 Huang et al., 2022). The most important difference is that our method differs from these works by adaptively generating the sparse model weights at fine-grained sample level, which achieves a good estimation for the conditional probability of heterogeneous local data and high accuracy as shown our experiments. Due the space limit, we present more detailed description and comparison with some of these works in Appendix
3 PROBLEM FORMULATION
The goal of traditional federated learning (FL) is to fit a single global model by collaboratively training models from a set C of clients without sharing their local data. In this paper, we focus on the personalized federated learning problem in terms of not only client-distinet models, but also client-distinet resource limitations. Specifically, consider each client i has its own private dataset S, that is drawn from a local distribution D, over X' x y. In general, the local data distributions (ee are heterogeneous and thus it is promising to learn personalized model hag E H. X' + y parameterized by 0, for each local distribution D;, where H is the set of hypotheses with d dimensions. Besides, clients may have heterogeneous computation and communication resources especially on cross-device FL scenarios. To better account for the data heterogeneity and system heterogeneity, we aim to optimize the following objective:
min Ep. Ep.EEse (, v)). (he, seC
(I)
s.t. size(0,) S d,, Ei
where f00,; wr y) A E(ho, (x), y) and L y + R+ is the loss function, py is non-negative aggregation weight for client i and Σiec P: = 1. In typical FL. setting (McMahan et al. 2017 Kairouz et al., (02T), pj indicates the participation degree of client and set to be proportional to the size of local dataset [S.]. The size(O.) indicates the number of parameters of 0, and d, indicates the model size limitation for client i. Without special designs to handle the system heterogeneity (here the size restriction), most pFL methods simply adopt another hypothesis space H with min( {de hee)) dimensions that are constraints by the lowest-resource clients, and the problem is degraded to the typical one that minimizes the objective without constraints. We consider the resource constraints in terms of model size limitation in this paper as it fairly reflect the computation and communication cost. Later we will see that our approach can be extended to other configurations such as FLOPs (Floating-poins operations per second), latency and communication bandwidth.
4 LEARNING TO GENERATE SPARSE MODEL
In practice, one can solve the problem in Equation 4 with two-step manner: ① find optimal local models via existing personalized federated learning methods without sparsity constraints, and then ② compress the trained models into required local model size via compression techniques such as pruning, quantization and knowledge distillation (Deng et al., 2020). However, the final local models from step ② usually gain worse performance to models found in step ① (Tiang et al. 2022). Besides, the post-compression process still requires computational and communication costs corresponding to the un-coppeeseed models during the FL process. To alleviate the performance degradation and further improve the efficiency of FL process, we propose to jointly learn and compress the federated models. Specifically, we can directly learn sparse local models whose number of non-zero parameters satisfy the size requirements:
min Dp: E(n.)) (((or (x). (hoz hic SEC
where he: E Hd: and Ha, indicates the subset of 7L with hypotheses whose number of non-zero parameters is not larger than d; However, the sparse models he can be arbitrarily different across clients due to the various dimension requirements di and local data distributions D,. Directly optimizing heg and aggregating them may lead to sub-optimal performance and make the federated
3

---

learning process un-convergent. As Marfog et al. (2021) discussed, clients can not benefit from each other without any additional assumption to the local distributions. Here we consider the case of bounded diversity following assumption shows:
Assumption 1. (Bounded Diversity) Let Dg be global data distribution that is a mixture of all local data distribution D; E C. Denote hog and ho; as the optimal estimator for the conditional probability of Dg and Dj respectively. There exist Dg such that the variance between local and global gradients bounded
[of((() Vof(0)1I S oo. ViEC
(3)
where l(0) is compact notation as f(0) 2 5(0; x,, v) for all data points (z, v) E X x y
Proposition 1. Denote (f))" be the parameter of any sparse optimal estimator for Di, i E C. If p-strongly convex, under Assumption [ there exist continuous weights M; E Rd such that (0)) = 0g @ M² where @ indicates element-wise production over model parameters of 8, and {M; hiee can be bounded as
of
Ro, Ro Vi ViEC
IIM 1)11
(4)
12110T17 ro, where va, and r9, are the infimum 0; and 0g respectively, Rs, and Ro, are the supremum of 0, and 8g respectively.
The proofs of all propositions and theorems of our work are in Appendix. Proposition suggests that we can deal with Problem ( via indirectly generating personalized sparse models hg: parameterized by 0' = 0g O M; with personalized weights M, and shared global model 0g. which helps to transfer information cross clients and leads to controllable optimization. Specifically, denote s; be the model sparsity constraint of client i, Problem (2) can be transformed into following form:
min Σpt Pt B(ay)= [f0g @ v)),
( lice: IEC
(5)
s.t. count(M; + 0)/d 8s 8,, E.
With this re-formulation, Mj can be regarded as sparsity-enforeet gated weights that absorb the diversity of different local data distribution into the global model, via scaling and blocking the information flow through the shared model 8g-
5
PERSONALIZED FL WITH CONDITIONAL GATED WEIGHTS
5.1 OVERALL FRAMEWORK
Note that for discriminative models (e.g., neural networks), the personalized models are estimators for conditional distribution Pp, (y]xx) associated to clients' local data D, To achieve efficient pFL and optimize the objective described in Equation (5), instead of learning client-level element- wise weights M, Rd, propose learn predict sample-level block-wise weights Mi, = 86, (xig), where di indicates the parameters a trainable personalized gating layer, and 8s, is the predictive function conditioned on specific data sample zi.j and sparsity limitation s;. The gating layer Φ; brings up benefits in both efficiency and effectiveness: (I) predicting block-wise weights M', E R enables us use lightweight o; for L N+ sub-blocks of 0 with < d, and thus gain much smaller computational costs than the element- wise manner; (2) predicting sample-wise weights can estimate the conditional probability better than the client-level manner since each client may have complex local data distribution mixed by different classes, e.g., using different sparse models to classify dog and bird can achieve better performance than using the same one. We empirically verify the effectiveness of these choices in Section 7.4
Based on the introduced gating layer, we establish an efficient pFL framework in server-client setting as shown in Figure [ To enable benefits from each other, all clients share the same global model fy that downloaded from server. Each client i E C has private, lightweight and learnable gating layer ds, which is trained from local data with a differentiable manner, and learns to achieve fine-grained personalized model-adaptation 0', = 0, @ M = 0, @ &8. (zi.) given different data samples, where @ indicates block-wise production of 0. To handle diverse resource-limited scenarios, 6i ensures that the personalized adapted model e/_, has required sparsity not larger than 8;, Moreover, the sparsity speeds up the training and inference of local models, as well as the communication via uploading the sparse model updates (we give detailed discussion Sec 6.3 and Appx.
4

---

Sparss model model-udapioan udaption
8
% % & MY
10.
① Uplaadd sparne
Mij
Lose
F+.
Updatt f
3 Optimbre 62.9. with backprngation
sppregating [M
( Send %
Clett (ppanity consraint
Spanse model-adapiion
x Uptoad
Xi
0 O Mij
Mi
Cuting Layer d:
Optimiar 9, with backprapttion
The pFedGate framework that learns to generate sparse personalized models conditioned on clients' different data samples and resource limitations. The serial numbers indicate the FL processes each communication round.
Figure 1:
5.2
ADAPTIVE GATING LAYER
5.2.1 LAYER ARCHITECTURE
We adopt a simple two-path sandwich ar- chitecture for the gating layer as shown in the left part of Figure 2 One path predicts the block-wise gated weights M that may violate the hard sparsity constrains, and the other path predicts the block-wise impor- tance scores that used to adjust M into a sparse one M' such that the final sparse model satisfies the hard limitation (we intro- duce the adjustment later). Let the number of sub-blocks of 0g be L and the dimension of flatten input feature be dx, i.e., x E dx The middle two fully connected layers have the same size and each of them has (dx L) parameters. Here the switchable normal- ization (Luo al. 2019) used handle batched data samples and different input
Feature
Sparse gated wright
Inference
Cony-1
WRgTL
Gwitstable Norm
Switrbable Norm
Bis au50
Fully Connected
Fully
Prediction
Batch
Salch
Block Wisc Scaling Masiinng
Sgmois
Sgrostt
Conv-3
weight Jub0
weight Rubo
Krapsuch protiem
Adsptive gating layer
Original weighht
Figure The sparse adaptaain via gating layer.
types via learning mixture of batch norm, instance norm and layer norm with negligible additional number of trainable parameters. Furthermore, the personalized normalization parameters within client-distinct gating layers enable our aadel-adaptttion to absorb different feature distributions (similar empirical evidence is shown by Li et al. (2021d)) The final batch normalization and sigmoid activation are used to stabilize the optimization of 6, and { by bounding M' and thus the scaling degrees 0, 's parameters (recall that the upper bound in Proposition i dependent the infimum and supremum of parameters after scaling). In total, the gating fayerTearm and predicts the sparse gated weights M (x) g(ó; æ)) given specific data sample where g Rdx R-,, with lightweight parameter size dg = 2d L that is usually much smaller than the size of model f,. We show the effectiveness and necessity of these adopted components of gating layer in Section 7.4
5.2.2 OPERATOR-TYPE-TREE BLOCK SPLITTING
There are many alternatives to split a model into certain sub-blocks, e.g., a convolutional operator can be split in channel-wis or filter-wise and an attention operator can be split in head-wise. Our gating layer is decoupled with specific block splitting manners and thus can easily support users" various splitting preferences. Besides, to enhance the usability of our approach as illustrated in the right part of Figure 2 Denote given block split factor, and denote di the dimension of flatten vector that parameterizes the given learnable operator. We group the vector's 's first [d, smin. elements as the first bub-block, and equally split the remaining elements into (B - 1) sub-blocks (the last sub-block may has fewer
propose a general sperator-type-free splitting manner by default N
5

---

log size than [(d:- (1- Sminn/B -
1).). Here B provides flexible splitting granularity, Smán (0, indicates a pre-defined minimal sparsity factor and the predicted gated weights for the first sub-block is enforced to be non-zero to avoid cutting information flow through this operator. The proposed splitting is simple to implement but effective for pFL. as shown in our empirical evaluations.
5.2.3 SPARSE GATED WFIGHTS
To ensure an equal or smaller sparsity of adapted model than the limitation 8;. we propose to leverage the predicted block importance G' to adjust the predicted gated weights M into a sparse one M'. Specifically, denote W E z be the parameter size look-up table of L sub-blocks, we transform M' .M I" where I E {0, 13 is binary index and a solution of the following knapsack problem that maximizes total block importance values while satisfy the sparsity constraint:
max I I. S.l. II Wl/d s,.
(6)
In practical, to enable gradient- based optimization of gating layer, we leverage the straight-through trick (Hubara al., 2016) via differentiable G in backward pass. In Appendix [ we summarize the overall algorithm and give detailed descriptions about the gradients flows through the gating layer.
ALGORITHM ANALYSIS
6.1 GENERALIZATION
Following the parameter-sharing analysis from Baxter (2000) and the generalization analysis from Shamsian et al. 2021), here we give the generalization guarantee of our sparse model.
Based on the notations used in previous sections, let L(0 di) denote the empirical loss of the sparse model in client and L(0g. Φ.)) A 1 Ei= Elew)ss f(00 B0, Bo, (x)):..))) The expected loss is denoted as C(Og, 0b) - + ((..)) ((,, @ 80. (x)) x,
Assumption 2. The parameters of global model and the gating layer can be bounded in ball with radius R. The following Lipschitz conditions hold: [f v) f(0'; x0, 22, Ly 0 ||. []h(0;;;)) 1000;; x)ll S Tn|l0;-- - 6'11 and ()):;) g(02 x)]l S Tylloh - --'l where h(00;;)) is the sparse model parameterized by 0g and g(0;;)) indicates the gating layer parameterized by th.
Let the parameter spaces of the sparse model and gating layer be of size d and dę, separately, With the above assumption, we have the following theorem regarding the generalization error bound.
Theorem 1. Under Assumption 2 there exist Ñ =
o d C (
log RL, RL5LA(RL,
+ do RL LLLLLaRL, + +1) log 6 Cle2
2
6
such that for all Og. Or with probability least 6, |C(0 di) -(0g, di)l S when the number of client i's local data samples is greater than N.
Thcorem I indicates the generalization depends on the size of the global model (i.e., d) reduced by the number of clients |C] (the first term), as the global model is shared by all clients. It also depends on the size of the gating layers (the second term), and it is not reduced by |C] since each client has its own personalized parameters. Besides, the generalization is also affected by the Lipschitz constants of the global model, sparse model, and the gating layer, as they together constrain the parameter space that our method can search.
6.2 CONVERGENCE
Under the following a few mild assumptions that commonly used in convergence analysis of many FL works (Kairouz et al., (021] Li al.) (2020) (more discussion about these assumptions are in Appendix (D), we can see that the learnable parameters of pFedGate (0,, and (é:)iec) converge to stationary points, meanwhile the global model updates (A Jicce become arbitrarily small.
Assumption 3. (Smoothness) For all clients i C. (x,y) E D, and all possible fg. the function f(0 x. y) & E(ho, (x), y) is twice continuously differentiable and L-smooth: [[ x4,) v (0 12 T.110, 0gll-

---

Assumption 4. (Bounded Output) The function f is bounded below by f E B.
Assumption S. (Bounded variance) For client i E C and all possibile Og. given data sample (x, v) drawn from local data S,, the local gradient estimator Vol(ho, (z),y) unbiased and has bounded variance o².
Theorem 2. Under Assumptions D
if clients use SGD as local optimizer with learning rale tn there exist a large enough number of communication rounds T', such that pFedGate converges with VT
1
T' T
(1;()); = =0)
(TT)
ViEC,
T
where the expectation is over the random samples and (1)) hides polylogarithmic factors.
6.3 SPACE-TIME TIME COMPLEXITY
We briefly summarize the efficiency of the proposed pFedGate method in terms of space-time costs. The training and inference cost of pFedGate is O (d((s++8))) for client i at each round, where the model sparsity 8; and relative sparsity of gating layer s6; cound( (b; * 0)/d are usually small and lead to (8,+ 1. By contrast, the computation cost of FedAvg and several SOTA pFL. methods is at least (d). The introduced sparsity provides great potential for boosting computation efficiency. As for the communication, the upload parameter number of pFedGate is ((g:)) that can be also smaller than the one of baselines, (d). Here the non-zero model updates, which depends on s; and local samples trained the round. In Appendix E we provide detailed discussions to show superiority of pFedGate over several SOTA competitors.
count A0; # o) indicates the ratio of
EXPERIMENTS
7.1 EXPERIMENTAL SETTINGS
We adopt four widely used FL datasets in experiments: EMNIST (Cohen al. 2017). FEMNIST (Caldas et al, 2018), CIFAR10 and CIFAR100 (Krizhevsky) 2009). They are partitioned into several sub-datasets to simulate the local dataset for client, and each of them is randomly split into train/val/test datasets with ratio 6:2:2. In the experiments, the data partition follows the heterogeneous settings adopted by Marroq et al. (2021): Dinh al. (2020b). We evaluate pFedGate terms of both personalization and FL efficiency. For personalization, we use standard FedAvg (McMahan et al. 2017) and FedAvg with fine-tuning (FedAvg-F7) as the baselines, and also choose several SOTA pFL methods, including PFedMe (Dinh et al., 2020b). LG-FedAvg (Liang et al.] (020). Ditro (Li et al. 2021c) and FedEM (Marfoq et al. | (021). As for efficiency, we compare several SOTA pFL methods that improve efficiency via shared model representations (FedRep (Collins et al.) (02T)), binary quantization (FedMask) Li et al. (2021a)), and sparse sub-models (HeteroFL (Diao et al. (021)). Due to limited space, please refer Appendix G for more details about the datasets, models and baselines.
7.2 OVERALL PERFORMANCE
Clients' Average Performance. We first examine the overall performance by evaluating the accuracy on local test set of each client, and averaging the results of all clients with weights proportional to their local dataset sizes. The detailed overall performance shown in Table 1 where s' indicates the average of finally achieved sparsity across all clients (our block-wise operation may lead to 5 < 8). We can see that PFedGate achieves better accuracy (averaged 3.1% to 4.53% accuracy improvements) and smaller sparsity even with ==0.3 at the same time. Compared with FedEM, the baseline with best accuracy, pFedGate doesn't have the heavy storage burden, since FedEM needs to store multiple (3) global models in the client. These observation demonstrate the effectiveness and efficiency of the proposed method. Note that compared to the SOTA efficient method HeteroFL, our method achieves better accuracy while with smaller sparsity (0.25 v.s. 0.55). When s=1, we achieve the best performance without sparsity constraints, verifying that the sample-level block-wise adaptation has a strong ability achieve personalization. When s<1, still gain comparable performance with s=1, providing evidence that there exist werf-performed sparse models and they can be effectively learned by our approach.
7

---

Table 1: Accuracy comparison on widely-adopted FL datasets. Acc (%) and Ace (%) indicates the average accuracy of all clients and accuracy of the bottom decile clients respectively. s' indicates the average of finally achieved sparsity across all clients. Bold and underlined numbers indicate the best and recond-best results respectively.
EMNIST
FEMNIST
CIFARIO
CIFARI00
Average
Ace
Acc
Acc
Ace
Acc
Ace
Acc
Acc
Ace
Acc
Local
71.91
64.28
71.12
57.93
61.91
53.71
26.95
21.13
$7.97
49.26
FedAvg
82.54
75.07
76.51
60.82
68.33
60.22
35.21
29.82
65.65
56.48
FodAvg-FT
83.19
76.83
78.43
64.22
69.91
61.55
37.15
30.91
67.17
58.38
PFedMe
83.29
76.48
75.29
57.63
70.29
62.13
36.14
30.13
66.25
56.59
LG-FedAvg
83.25
76.14
75.13
57.62
69.54
61.86
36.72
30.51
66.16
56.53
Ditto
82.75
78.12
79.29
63.24
73.14
62.59
37.32
30.11
68.13
58.52
FedEM
83.41
76.59
80.12
64.81
72.43
62.88
38.28
31.04
68.56
58.83
FedRep FedMask, s'=0.5
82.42
77.71
79.17
62.89
72.77
63.44
36.68
30,51
67.76
58.66 64
81.95
77.26
78.69
62.18
72.43
62,88
36.21
30.13
67.32
58.11
HeteroFL,, 3'=0.55
85.64
77.76
77.22
59.13
70.97
63.64
37.01
31.27
67.71
57.95
PFedGate, s=1
87.11
81.43
87.32
77.14
75.18
66.67
42.01
35.03
72.91
65.07
s=0.5 5'=0.43
81.15
86.31
75.68
74.07
64.21
40.07
32.38
71.93
63.36
0=3.3 5'20.25
87.09
82.52
86.75
76.47
73.65
64.39
39.53
31.63
71.76
63.75
0.2
W.D.A. 7.90
12:31
0.9
VI
Clent3
Clant
Chenk
Glast
Dlerd
ChaRT
Dhamc
Chao2
Dhmm 6K6
Clest
V.D.A
K3.00
Figure 3: The client-wise accu-
racy difference between PFedGate and FedEM on CIFARIO dataset.
Figure 4: The hierarchical clustering result for parameters of clients' gating layers on CIFAR-10 with 10-clients partition.
Individual Client Performance. We then examine whether pFedGate improved the average perfor- mance by sacrificing the performance of some clients. In Table we mark the accuracy of bottom decile local models Aec the [CI//10)-th worst accuracy (following Marfoq al. (2021) neglect the particularly noisy results from clients with worse accuracy due to their very small local data sizes). We find that pFedGate also gains significant Ace improvement (averaged 4.92% 6.24% than FedEM). We plot the client-wise accuracy difference between our method with = 0.5 and the strongest baseline, FedEM in Figure 3 in which pFedGate significantly improves most clients compared to the strongest baseline. The results in Table | and Figure 3 show that pFedGate not only improves the average accuracy and efficiency, but also fairly improves the individual client performance by learning to generate personalized models with adaptive gating layers.
7.3 PERSONALIZATION STUDY
We propose to learn personalized gating layers [oy] that estimate the heterogeneous data distribution with sparse model-adaption. To investigate the level of personalization achieved by PFedGate, we conduct experiments on another CIFARIO non-i.i.d. partition with 10 clients and pathological splitting
(MeMahan al. 2017) that sorts the data by labels and assigns to clients with equal-sized shards.
We do hierarchical clustering for the parameters of learned gating layers [db]] with Ward's method (Ward Jr. 1963) and euclidean distance. We illustrate the results in Figure when the models of clients converge with ==0.3 and achieve good performance (Acc=89.2) 89.2%% 1)), where we mark the local label categories of clients and common label categories after merging in red numbers. Interestingly, we can see that clients learn gating layers with smaller parameter distances along with they share more similarities in label categories. This indicates that pFedGate not only can achieve good client- distinct personalization, but also implicitly learn the group-wiss wise personalization with a strong sparsity constraint, which could be beneficial applications where there are inherent partitions among clients.
8

---

Table 2: Average accuracy and round to achieve Acc
accuracy (Th.s) normalized by standard pFedGate.
85.0
EMNIST
CIFAR100
82.5-
Acc
Toss
Acc
To.s
80.0-
pFedGate, s=0.5
87.28
39.72
Accurscy Type Ang SOC
75.0
w/o pre-norm
86.25
1.13
38.32
1.24
72.
w/o post-norm
87.14
1.10
39.67
1.43
0.5
10.5 2a
w/o sigmoid
83.55
1.85
31.29
1.93
Figure The accuracy on EMNIST when varying
client-wise adaptation
84.83
0.74
33.52
0.86
7.4 ABLATION STUDY
Choices of Gating Layer. To gain further insight into method. we ablate the gating layer w.r.t. its switchable norm layer (pre-norm) and batch norm layer (post-norm) within the sandwich structure and the sigmoid activation that bounds the gated weights. We also change the sample-wise adaption into client-wise manner by feeding the input feature mean-pooled over all local training data samples of each client. We show the results in Table 2 with s=0.5.
We find that the two normalization layers improve the convergence speed. Beside, pre-norm has a larger impact on performance than post-norm since it helps to handle the heterogeneous feature distribution. The sigmoid significantly impacts both the convergence and accuracy, showing effec- tiveness of gated weights bounding operation, which restricts the dissimilarity level between the personalized model and global model, and turn helps to learn a global model suitable for different clients. Compared to sample-level manner, although client-wise adaption achieves a faster training, it pays cost of significant accuracy drop due to the coarser-graing modeling of conditional distribution of local data and smaller parameter space could be explored under sparsity constraints. In nutshell, the ablation results verify effectiveness and necessity of our choices in gating layer.
Effect of s. We further study the effect of the sparsity factor by varying from to 0.1 EMNIST dataset and illustrate the results in Figure 5 in which "00.5, 0.1]" indicates that we randomly divide all clients into two equal-sized parts and set can see that our method is robust to keep a good performance when adopting not very small sparsity degrees. Another observation is that the performance variance increases as decreases. Besides, our method still performs well in a sparsity-mixed setting, verifying the robustness of our method again.
be 0.5 and 0.1 for these two parts respectively. We
7.5 OVERVIEW OF MORE EXPERIMENTS IN APPENDIX
Due to the space limitation, provide further experiments and analysis in Appendix in terms of
Generalization: In Appx H.I we present additional results of pFedGate for the un-seen clients that haven't 't participated in the Fl. training stage (Diao et al., 2021 Marfoq et al.) 2021: Yuan et al.
2022 in which case pFedGate achieves better performance than baselines since only needs to train the personalized lightweight gating layers with a small number of parameters.
Robustness: In Appx H.2 we conduct experiments in partial clients participation case with sampling technique to further verify the effectiveness and robustness of pFedGate in practical FL scenarios.
Convergence and model compression manner: In Appx H.3 we show that pFedGate can achieve effective optimization, which supports the Theorem In Appx H.4] we vary the block splitting factor B of pFedGate and make more detailed comparison to FedMask (Li et al. 202
8 CONCLUSION
Existing personalized Federated Learning (pFL) methods usually focus on the heterogeneity of local data distribution only and pay additional computation and communication costs. In this paper, we explore the organic combination of model compression and pFL by adaptively generating different sparse local models at fine-grained sample level, which gains double benefit of personalization performance and efficiency. Theoretical analysis are provided w.r.t. generalization, convergence and space-time simee-timed complexity. Extensive experiments are conducted to verify the effectiveness, efficiency and robustness of the proposed method in various benchmarks and scenarios. We demonstrate the feasibility of obtaining superior accuracy and efficiency simultancously for pFL, and believe this work can enlighten more studies efficient and practical pFL..

---

REPRODUCIBILITY STATEMENT
For the proposed proposition and theorems, we give the complete proof in Appendix (for propo- sition T Appendix C (for theorem I and Appendix D (for theorem 2 More introduction and implementation details experimental setups are also presented in Appendix G including configura- tions for the datasets, models and baselines and our method. To facilitate the reproducibitlity. summarize the algorithm of the proposed method in Appendix and provide the source codes in the anonymous link, http::/giihub..om//mng
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. NewrlPS, 30:1709-1722 2017.
Jonathan Baxter. A model inductive bias learning. JAIR, 12:149-198, 2000.
Christopher Briggs, Zhong Fan, and Peter Andras. Federated learning with hierarchical clustering of local updates to improve training non-iid data. In IJCNN, pp. 1-9. IEEE, 2020.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: benchmark for federated settings. arXiv preprint arXiv:1812.0109) 2018
Zheng Chai, Hannan Fayyaz, Zeshan Fayyaz, Ali Anwar, Yi Zhou, Nathalic Baracaldo, Heiko Ludwig, and Yue Cheng. Towards taming the resource and data heterogeneity in federated learning. In 2019 USENIX Conference on Operational Machine Learning (OpML 19), pp. 19-21, 2019.
Zheng Chai, Ahsan Ali, Syed Zawad, Stacey Truex, Ali Anwar, Nathalie Baracaldo, Yi Zhou, Heiko Ludwig, Feng Yan, and Yue Cheng. Tifl: tier-based federated learning system. In Proceedings of the 29th International Symposium on Frigh-Pefformncce Parallel and Distributed Computing, pp. 12--136 2020.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist handwritten letters. In IJCNN, pp. 2921-2926. IEEE, 2017.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared repre- sentations for personalized federated learning. In /CML, volume 139, pp. 2089-2099, 18-24 Jul 2021.
Luca Corinzia and Joachim M. Buhmann. Variational federated multi-task learning, 2019.
Lei Deng, Guoqi Li, Song Han, Luping Shi, and Yuan Xie. Model compression and hardware acceleration for neural networks: A comprehensive survey. Proceedings of the IEEE, 108(4): 485-532, 2020.
Enmao Diao, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication efficient federated learning for heterogeneous clients. In ICLR, 2021.
Canh T. Dinh, N. H. Tran, and T. D. Nguyen. Personalized federated learning with moreau envelopes. ArXiv, abs/2006.08820 008448 2020a.
Canh T Dinh, Nguyen Tran, and Tuan Dung Nguyen. Personalized federated learning with moreau envelopes. In NeurlPS, 2020b.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning with theoretical guarantees: A model-agnostic meta-leariing approach. In NeurIPS, volume 33, pp. 3557-3568, 2020.
Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. In NeurlPS, volume 33, 2020.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In AISTATS, pp. 2350-2358. PMLR, 2021.
10

---

Jenny Hamer, Mehryar Mohri, and Ananda Theertha Suresh. Fedboost: A fommunication-effice algorithm for federated learning. In ICML, pp. 1973-3983, PMLR, 2020.
Godfrey Harold Hardy, John Edensor Littlewood, George Pólya, György Pólya, et al. Inqqualities. Cambridge university press, 1952.
Chaoyang He, Murali Annavaram, and Salman Avestimehr. Group knowledge transfer: Federated learning of large cnns at the edge. NeurlPS, 33, 2020.
Junyuan Hong, Zhuangdi Zhu, Shuyang Yu, Zhangyang Wang, Hiroko Dodge, and Jiayu Zhou. Federated adversarial debiasing for fair and transferable representations. In KDD, 2021.
Junyuan Hong, Haotao Wang, Zhangyang Wang, and Jiayu Zhou. Efficient split-mix federated learning for on-demand and in-situ customization. In ICLR, 2022.
Tiansheng Huang. Shiwei Liu, Shen Li, Fengxiang He, Weiwei Lin, and Dacheng Tao. Achieving personalized federated learning with sparse local models. ArXiv, abs/2201. 1380, 2022.
Yutao Huang. Lingyang Chu, Zirui Zhou, Lanjun Wang, Jiangchuan Liu, Jian Pei, and Yong Zhang. Personalized cross-silo federated learning non-iid data. In AAAI, volume 35, pp. 7865-7873, 2021.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran EI- Eany,,, and Yoshua Bengio. Binarized neural networks. NeurlPS, 29, 2016.
Yihan Jiang, Jakub Konečný, Keith Rush, and Sreeram Kannan. Improving Federated Learning Personalization via Model Agnostic Meta Learning. 1rXiv:190..12440
2019.
Yuang Jiang, Shiqiang Wang, Victor Valls, Bong Jun Ko, Wei-Han Lee, Kin Leung, and Leandros Tassiulas. Model pruning enables efficient federated learning on edge devices. IEEE Transactions on Neural Networks and Learning Systems, 2022.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He. Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song. Weikang Song, Scbastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Pranceth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2): 1-210, 2021. ISSN 1935-8237. doi: 10.1561/2200000833 URL hattp://da www.doi..oooooo oog/11 1561/22000000
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In ICML, pp. 5132-51444 5143. PMLR, 2020.
Mikhail Khodak, Maria-Florina F Balcan, and Ameet $ Talwalkar. Adaptive gradient- meta- learning methods. In NeurlPS, pp. 5917-5928, 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Msc thesis, 2009.
Ang Li, Jingwei Sun, Xiao Zeng, Mi Zhang, Hai Li, and Yiran Chen. Fedmask: Joint computation and communication-efiiccn personalized federated learning via heterogeneous masking, In SenSys, pp. 42-55, 202 la.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges,
methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In ICML, pp. 6368. PMLR, 2021b.
11

---

Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In ICML, pp. 6357-6368, 2021c
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang, On the convergence of fedavg on non-iid data. In ICLR, 2019.
Xiaoxiao Li, Meirui Jiang, Xiaofei Zhang, Michael Kamp, and Qi Dou. Fed(bn]: Federated learning on non- (iid) features via local batch normalization. In ICLR, 2021d.
Paul Pu Liang, Terrance Liu, Liu Ziyin, Ruslan Salakhutdinov, and Louis- Louis-Phllippe Morency. Think locally, act globally: Federated learning with local and global representations. arXiv preprint arXiv:2001.01523, 2020.
Tao Lin, Lingjing Kong. Sebastian U Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. NeurlPS, 33, 2020.
Ping Luo, Jiamin Ren, Zhanglin Peng. Ruimao Zhang, and Jingyu Li. Differentiable learning-to- normalize via switchable normalization. ICLR, 2019.
Jie Ma, Guodong Long, Tianyi Zhou, Jing Jiang, and Chengqi Zhang. On the convergence of clustered federated learning. arXiv preprini arXiv:2202.06// 2022.
Othmane Marfoq, Giovanni Neglia, Aurélien Bellet, Laetitia Kameni, and Richard Vidal. Federated multi-task learning under mixture of distributions. NeurlPS, 34, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication efficcient learning of deep networks from decentralized data. In AISTATS, pp. 1273-1282. PMLR, 2017.
Chuizheng Meng, Sirisha Rambhatla, and Yan Liu. Cross-node federated graph neural network for spatio-temporal data modeling. In KDD, pp. 1202-1211, 2021.
Hoang Minh and Kingsford Carl. In neurips 2021 workshop on new frontiers in federated learning 2021. Personalized neural architecture search for federated learning.. 2021.
Khalil Muhammad, Qinqin Wang, Diarmuid O (Reilly-Morgal Elias Tragos, Barry Smyth, Neil Hurley, James Geraci, and Aonghus Lawlor: Fedfast: Going beyond average for faster training of federated recommender systems. In KDD, pp. 1244-1242, 2020.
Kaan Ozkara, Navjot Singh, Deepesh Data, and Suhas Diggavi. Quped: Quantized personalization via distillation with applications federated learning. A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In ICLR, 2021.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-etffcienn federated learning method with periodic averaging and quanti- zation. In AISTATS, pp. 2021-2031. PMLR, 2020.
Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. Fetchsgd: Communication-fftiicen federated learning with sketching, In ICML, pp. 8253-8265. PMLR, 2020.
Felix Sattler, Klaus-Robert Müller, and Wojciech Samek. Clustered federated learning: Model- agnostic distributed multitask optimization under privacy constraints. TNNLS, 2020.
Aviv Shamsian, Aviv Navon, Ethan Fetaya, and Gal Chechik. Personalized federated learning using hypernetworks. Marina Meila and Tong Zhang (eds.), ICML., volume 139, pp. 9489-9502, 2021.
Karan Singhal, Hakim Sidahmed, Zachary Garrett, Shanshan Wu, John Rush, and Sushant Prakash. Federated reconstruction: Partially local federated learning. Advances in Neural Information Processing Systems, 34, 2021.
12

---

Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar. Federated Multi-Tass Learning. NewrIPS, volume 30, pp. 4427 1227-4437,22 2017.
Alysa Ziying Tan, Han Yu, Lizhen Cui, and Qiang Yang. Towards personalized federated learning. arXiv preprint arXiv:2103.000 2021.
Wan Tianchun, Cheng Wei, Luo Dongsheng. Yu Wenchao, Ni Jingehao, Tong Liang, Chen Haifeng, and Xiang Zhang. ledm. In Personalized Federated Learning via Heterogeneous Modular Networks, 2022.
Joe H Ward Jr. Hicrarchical grouping to optimize an objective function. JASA, 58(301);236-244, 1963.
Hongwei Yang, Hui He, Weizhe Zhang, and Xiaochun Cao. FedSteg: A Federated Transfer Learning Framework for Secure Image Steganalysis. IEEE TNSE, 2020.
Qian Yang, Jianyi Zhang, Weituo Hao, Gregory P Spell, and Lawrence Carin. Flop: Federated learning on medical datasets using partial networks. In KDD, pp. 3845-3853, 2021.
Qiang Yang. Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. arXiv: Artificial Intelligence, 2019.
Fuxun Yu, Weishan Zhang, Zhuwei Qin, Zirui Xu, Di Wang, Chenchen Liu, Zhi Tian, and Xiang Chen. Fed2: Feature-aligned federated learning. In KDD, pp. 2066-2074, 2021.
Honglin Yuan, Warren Richard Morningstar, Lin Ning, and Karan Singhal. What do we mean by generalization in federated learning? In International Conference on Learning Representations, 2022.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, and Nghia Hoang. Sta- tistical model aggregation via parameter matching. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, 2019a.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. In International Conference on Machine Learning, 7252-7261. PMLR, 2019b.
Jie Zhang, Song Guo, Xiaosong Ma, Haozhao Wang, Wenchao Xu, and Feijie Wu. Parameterized knowledge transfer for personalized federated learning. NewrIPS, volume 34, 2021a.
Michael Zhang, Karan Sapra, Sanja Fidler, Serena Yeung, and Jose M Alvarez. Personalized federated learning with first order model optimization. In ICLR, 2020.
Qingsong Zhang, Bin Gu, Cheng Deng, Songxiang Gu, Liefeng Bo, Jian Pei, and Heng Huang. Asysqn: Faster vertical federated learning algorithms with better computation resource utilization. In KDD, pp. 3917-3921 2021b.
Zhuangdi Zhu, Junyuan Hong, and Jiayu Zhou. Data-free knowledge distillation for heterogencous federated learning. In ICML, 2021.
13

---

APPENDICES FOR THE SUBMISSION: EFFICIENT PERSONALIZED FEDERATED LEARNING VIA SPARSE ADDATATAATTTIOON
We provide more details and further experiments about our work in appendices:
Sec A
the summarized algorithm of the proposed method.
Sec the full proof of Proposition
Sec the full proof of Theorem
See D the full proof of Theorem
See the detailed discussion about the space-time complexity comparing with other FL. methods.
Sec the detailed discussion about more related works.
Sec G the implementation details of experiments such datasets, baselines, models, hyper-parameten and sparse model aggregation procedure pFedGate.
Sec H further experimental results including: Sec H.1 the performance in novel client participation case; Sec the performance in partial clients participation case; S..3 the convergence study; and Sec|H.4, the model compression manner study, in which we compare pFedGate the SOTA binary quantization method FedMask (Li et al. 2021a).
A THE ALGORITHM OF THE PROPOSED PFEDGATE METHOD
Algorithm 1: Efficient Personalized FL with pFedGate
Input: T, fg. 1), 80 hee 8min, (sihee for ( = 1, .T' do
Server sends 0--1 to clients C, sampled from C for client i E C. in parallel do for data sample (z, v) E do
Get sparse gated weight: M/ g(0)- (2)
Do personalized model-adaption: 02 = 06-1 @ M
Update global model and local gating layer: 0f = -t- 0t-1- mg (Vof
&i = の 1-1 7/( 50 [o Upload sparse Aet 9. = q g--1
Server updates global model: 0r AGGREGATE (0) (ABt (EE.))Ec.) return fg. {dh hiec
We summarize the overall algorithm in Algorithm Besides, we present more details about the gradients flow through the gating layer, which contains knapsack solver.
We leverage the straight- through trick (Hubara et al. 2016) to make the combination of the two flows predicted by the gating layer (red G and blue MM in Figure 2) still differentiable. Recall that the combination is M' M Is where 1* is binary index and a solution to the knapsack problem (Section 5.2 The "straight-through" (ST) here means that build such a computation graph, in which we only use binary variable I" in the forward pass stage, while replace I" into the differentiable variable G in backward gradient propagation. Specifically, this can be implemented by the following demonstrative PyTorch code: Tšr = 1* G. C.detach() + G. In this way, the tensor TST and M are both differentiable and can used to pass the gradient flow via their combination tensor M Tšx M and the following adapted tensor of the sparse model 8 ge- @ M'. And thus we can train the personalized model and the gating layer as Algorithm
lines 6 and 7 shown.
14

---

B PROOF OF PROPOSITION 1
Since f is p-strongly convex, by definition we have
S(0') ( V05(0) 0) -0)+ 21000 012,. v0, 0'.
(8)
We have (' = f(0) - " ||i| 2 also convex due to the first order condition of f with Equation Considering the monotone gradient condition for convexity of f', get
(Va](0) (O') (0 0') 2 pl10 0'I,, v0, 0'.
Applying Cauchy-Schwartz inequality on Equation ( we get
Vo.(()-Vof((()lll 0'll
(V) V (af( 0')
(10)
/-|0 811
Dividing ||0 0 on both sides of Equation 10) get
||0 0'1| - ( Vof 11/,, V0, Under Assumption for all (0), 07)) pairs with Equation (1). we have
(11)
[M 1)0
2 Vi C.
(12)
Using the reversed Cauchy- Schwarz incquality (Hardy et al. 1952), we have A (M, - 1) z |1 (M; - 1))11
(13)
where A, 1 [Ro, tro, is positive constant, re, and re, the infimum of 0, and 0g Ko, Ro, ro, respectively, Ro, and Ra, are the supremum of 0; and 0g respectively, Since Ro, 2 To, we N.RRo,R,,,
Ra, Combining Equation (12 and Equation (13). we get the upper have A; S 1 Ra, Re, 79, T8 bound in Propostion and finish the proof.
C PROOF OF THEOREM
Let THT" denote the function space with its elements parametrized by 0g. Φ1. .., on and the distance metric is defined as:
(((0g) Φ1, Fn) - (0 $1.... ,(,,),
(14)
EnwDD. Σ (f(0, di x, 8) 5(0 61
With the Lipshitz conditions in Assumption 2 we have:
d((0g, g, Φ1, On) (0 0i )'n)
n Eg En.YDD. (s)) (x). ehh ( (z).
< Lyllbb, - :10
(L,llb.(0.) - (0')l
Ln 10,, M. - 0,
(Lipshitz condition)
SL,4, 10,M 0,M, + +0, - 0,,''l
(15)
L [1001 1IM, - M/1l+ +|M111 110, - 6,11
RIIM - Mil1 +110, - [511]
SLy4,
(Assumption
LL
R((g(o.) - s( + +110, - e
Ln
RL4 10: -2'1 + 110,- - d/1l]
(Lipshitz condition)
15

---

where R is radius of the ball that can bound the parameters of global model and the gating layer (men-
tioned in Assumption We can get an e-covering in metric d((0g. 01, @.a) - (0y 91. ........... .n))
we select a covering of in the parameter space with both || Aill and 110 0 equal to b +RI Therefore, the covering number of IH[C), denoted as ((c, H is: log (B(c, H O (IClds + d) log RL, (R,,,()
According to Baxter 2000 Shamsian et al. 2021, , there exit N and Ñ = 0 nc log Ble, 1 |c|c2 log
O
RL., In (
de log
RL, La (1)
log 6 |c|c
D PROOF OF THEOREM 2
We note that Marfoq et al. (202I) extends the surrogate optimization into FL setting and provide convergence results for the algorithms which approximates the target objective functions using first- order surrogate or partial first-order surrogate functions. For simplicity, we use two more compact notations for all the learnable parameters introduced our formulation as UM - {M,) hiec and "M''o {M, = 8(0;: z) ie).,ex.. Here we prove that our method described in Algorithm | can be regarded as optimize the objective function F(Og, Tar") ) in Equation (5) with another partial first-order surrogate function, and the convergence results from Marfoq et al. (2021) can be applied into our method. We first recap the formal definition of partial first-order surrogate:
Definition 1 (Partial first-order surrogate Marfoq et al. (2021)) ). A functio F' 8) Rdd x x - -R R partial-fire first- order surrogate of F(ui, ū) wrt near (ug. Vo) Rd V when the following conditions are satisfied:
1. (( 17 2 F(ū, ū) for all i E TRd and T E V;
2. c(ū, iT & (ū, 17) F(ū. iř) is differentiable and L-smooth with respect to i. Moreover, we have e( To. Un) = 0 and V zE( 2e(2o, 06) = O.
3. [" 0o) (ū, ū) dy (Tn U) for all ī E Rd and T E arg mittaey F' U'), where dy is non-negative and dy (ū, V) = = T=
Definition indicates that in partial parameter set V. F' is majorant F and the smoothness is satisfied in the neighborhood of given point.
Denote (0,, uMr. .)) as the transformed local objective function depicted by the gating layer di i.e. the sparse gated weight M, generated by the process described Section 5.2 and intermediate objective in Equation (6) We then restrict attention from the function F u over all clients into (C] local functions (l,. Unr' .o) for each client i, since the weighted sum operation is convex and holds the partial majorization and smoothness properties. Consider the iterative version of F; and F. corresponding to the produce in Algorithim 1
We have the partial set of gated weights V/ = [fM, = g( x( rxxx, I mar (O) _ot for all t [T]. For UM' .6 Ve. due to the optimality of of and equality between E.M and UM .ot using block-to-element scatter operation on the gated weights, have (0 ) = F. T' .o)) and Condition satisfied.
Note that the difference between Ff ) and F. UMr is differentiable w.r.t 0, since both of them is differentiable by adopting either element-wise or block-wise production on 6 and the sparse gated weights. With the smoothness Assumption 3 we have the Condition 2 sat- isfied. For the Condition 3, it is clear that if the right statement holds, i.e., Uns o = ox. " .e'
then
dy (T Vy .aa Ff U F. Ty "xr 0 and we have the sufficiency between the two statements of Condition satisfied. For the necessity between the two statements of Con- dition 3, we can consider such set Vo \ (V/ V.), where V. indicates the subset of V in which t E [T if F converges at step T < T, and Vo indicates the subset of V& in which =1 "" vt, E [T], t' + f). The new partial subset ensures the optimal i Ey a is unique by discarding the redundant u. o that have the same (0 of As a)) For
E (1'1F
16

---

such new partial subset V \ (V& Ub), we have the necessity between the two statements of Con- dition satisfied due to the uniqueness of the solutions of arg min. sr (VA(D,
(f 'M' p
and the Condition I and Condition still hold since V \ (V& U V is a subset of Va-
We finally show that the assumptions required by the convergence proof in Marlog et al. 2022 hold when using our approach.
Proposition 2. Under the assumptions 1 when taking the parameter from 0g to 0g. 0g o. (x) over all i E C, E X,, the gradient variance of f and diversity across clients are also bounded, and the smoothness of f holds.
Proof. Note that using the chain rule, the gradients on oi can be written as Vo(f(Os,iz.)) Volg. (0, x, 1) for (z, y) E D, For simplicity, we denote Vo( x),)) 2 f(0s)). S..). we generate sparse model as 0s. = 0g @ Mt. we have Vole. = M, V,M,M The block-wise production operation @ is differentiable and over 0g is differentiable according to Assumption 3 thus f over d; is also differentiable. Then recall that the optimal gated weights are bounded as shown in Proposition| [] Further, we explicitly bound the sparse gated weight during FL training process in [0, 1] using sigmoid function as introduced in Section 5.2 We thus can assume that
V Volle - V 10 < 10 - 12.11
(16)
where Lo is a Lipshitz constant corresponding to our bounded gated weights. We get
(ol((s; (0
V Volo; Vof( V Vo (of()
(Chain Rule)
=| V Vola; Vof((x) V&G (of( Vol - Vob Vof(O,)) 1l
V V. (05())) - Vals;
(11 + V Vol(O - Volo. Vol
<1 0 06 19 0 2 + L Vo (0 1 12.
(Assumption 3 & Eqn. (6)
$ S2LL 1 0..1 113
(17)
where the last two lines because of that Lipschitz implies bounded gradient. Thus we get that is (2LL,))-moot using our method. Similar to the proof of smoothness that leverages the chain rule and bounded Mf. we can generalize Assumption I and Assumption [or our method such that the gradients dissimilarity is bounded and f has bounded variance characterized by another constant factor.
Now we see that each client can optimize a partial first-order surrogate function and the necessary Applying the Theorem 3.2' in Marfoq al. (021). we
assumptions satisfy with Proposition 2
conclude the proof of our Theorem
Remark on the assumptions. We note that the adopted theoretical assumptions are widely used by numerous related FL works. Specifically, the assumptions [ (bounded data diversity). (smoothness of f...P (bounded output of (),5 (bounded gradients variance) are used in works such as Li al.
2019
Ma et al.) (202)); Dinh et al. (2020b); Liang et al. (2020); Marloq et al. (202T) These scenarios:
assumptions are reasonable and fairly mild
The assumptions 3 and 4 are easily satisfied for most discriminative models such as neural networks
(Tan et al. 2021 Kairouz et al. 2021
al. 2019).
The assumptions and are necessary to a feasible and effective FL course, in which there is knowledge that can be shared and mutually beneficial between the FI. participants (Ma et al. 2022
Dinh al. 2020bb Liang al. 2020 Marfoq et al. (021).
As for the assumption 2 (bounded parameters of the global model and the gating layer), it is
dependent the hypothesis space of the adopted global model and gating layer, which are controllable by users. For example, we can hard clip their model parameters, and introduce bounded activation functions such sigmoid into the gating layer structure as the proposed method does. A
17

---

specific example of this is our implementation, where zero initialization, kaiming- uniform initialization and (0, -nnuffrrm initialization for the parameters adopted global model and gating layer, which leads to all these init parameters are bounded by one of O, 1, constants calculated by the bounded fam_in (usually determined by the data shape). Then during the FL. courses, we clip the gradients each backpropagation step (via wrrch.n.utils.com _eapeeppppppd___ee grad_norm_()) resulting in the bounded parameters and thus the assumption holds.
Besides, assumption similar to our assumption 2 can be found in the related pFL work, PFedHN (Shamsian et al.] 2021), in which the authors assume that their introduced weights of the hyper-network and the embeddings bounded and follow several Lipschitz conditions with constants different from ours.
E SPACE-TIME COMPLEXITY
Table 3: The proposed PFedGate achieves better computation, communication and storage complexity over tfate-of-the-at personalized FL methods. The underlined results indicate the examples when taking default hyper-pann pameters: the embedding and hypernetwork size d, = 0.25 C d₁, 100 for DFedHN (Shamsian et al. (202)) the component model number k for FedEM Marfoq al. (2021), the client sparsity 0.5, and relative sparsity of gating layer sø, d/2dx L = 0.05 for pFedGate. Besides, for pFedGate, we report the average non-zero parameter ratio = 0.67, which dependent datasets and local training steps. Here report the average value of qi when run FL experiments 3 times on FEMNIST and CIFARIO with s; = 0.5, local update step as 1 epoch, and batch size 128.
FedAvg
pFedHN
FedEM
pFedGate
O(2d)
O(2d)
(2kd)
(2d(ss: + (6.) (
Train (Client)
(6d)
Computation
((d)
O(d)
O(d)
Old(s: + $6:)) O(0.55d)
Infer (Client)
0(1)
O(d,+
O(1)
0(1)
Train (Server)
O(6d)
(((025)(C++100) c.I)
((d)
(dd)
(kd)
O(qd)
Client
(3d)
(
Communication
O(d(c.))
Oddc..
Okd]C,,)
Odd(a))
Server
O(3d
O(d)
((d)
(kd)
0(1++ sa.)d)
Client
(3d)
O(100dd)
Storage
O(d)
O(d.d, + dclC))
(kkd)
O(d)
Server
(3d)
We examine the efficiency of pFedGate described in Algorithm T in terms of computation, communication, and storage costs. We will see that pFedGate gains improvements on computation and communication costs with tolerable storage cost. 3 summarizes the costs for pFedGate and competitors including FedAvg and two SOTA personalized FL methods, where the training and inference costs on client considered for each training batch (or each sample when the batch size is 1), and the communication cost is considered for each FL round. We also mark some specific example values when taking the default pyper-parameters of different methods in Table For comparison simplicity, here we assume that for the computation costs, the inference and back- propagation times are proportional to the model size. We hide both constants and polylogarithmic factors dependent with the same model architectures and the same trained data samples. As for communication and storage, O(-) hides constants and lower-order factors dependent specific implementations such as platforms, storage, and communication protocols. The PFedGate uploads parameters (q.d). where d count A0; * 0)/d indicates the ratio of non-zero model updates. Specifically, qi be
the specific model architectures in O(.), since we compare these methods
18

---

regarded as the probability that a parameter is finally not masked in the local training process. We can consider qi (1-11, p;)). where pj indicates the probability that a parameter is not within the sub-blocks the gating layer predicts to mask when taking the j-th data batch as input, and |S] indicates the number of data batches trained in each local FL round. Note that p1 is equal to the sparsity factor 8; at client i, and pj becomes smaller as j increases, due to the fact that the local data samples usually share some similarities, and the newly predicted sub-blocks are more likely to be the same as the sub-blocks have been selected.
From Table 3 we can see that PFedGate achieves better efficiency than FedAvg in training, inference, and uploading with negligible additional storage cost on clients (as marked in red). By contrast, to achieve good personalization. FedEM introduces more than global model and pays larger costs in training. communication, and storage (as marked in blue). And pFedHN learns client-wise embedding in the server, which may lead to single-point bottleneck for cross-device setting and potentially disclose personal information.
F MORE RELATED WORK COMPARISON
Here we present more details about the works related to our method. QuPeD (Ozkara et al. 2021 combines quantization and knowledge distillation for personalized federated learning. FedMask (Li et al. (02 freezes the local models during the whole FL. process, learns distinct binary masks for the last several layers of the models, and only transmits and aggregates the learned masks. Different from the quantization based methods, we adopts continuous gated weights all sub-blocks of the local model and transmits the sparse model updates, enabling flexible model size reduction and high capability to capture the client relationships via the shared global model.
FedRep (Collins et al. 202T) proposes to upload partial sub-parameters as shared representation and leave the others locally trained. HereroFL (Diao et al. 2021) selects different subsets of global model parameters for clients based on their computational capabilities. Different from these model-decoupling based works that use the same parameter subset for those clients having the same computation capability, our method generates different sub-models from the whole global model with larger learnable parameter space handle heterogeneous data distribution. More importantly, our method differs from these works by adaptively generating the sparse model weights at fine-grained sample level, which achieves good estimation for the conditional probability of heterogeneous local data and high accuracy as shown in our experiments.
FedPNAS Minh & Carl (2021) leverages neural architecture search (NAS) to search suitable sub- networks for clients, and FedMN Tianchun et al. (2022) proposes to use nouting-hypernetie select personalized sub-blocks. For the FedPNAS, we differ from it in the target and studied problem. FedPNAS mainly focuses on improving the personalization performance with sufficient hardware resources. For example, they adopt clients in their experiments that usually correspond to the cross-silo case. While pFedGate focuses the cross-device setting, where the clients' resources are usually very limited. Compared with FedMN, the performance of pFedGate is theoretically guaranteed for both generalization and convergence. While FedMN doesn't provide any theoretical analyses for generalization or convergence. Besides, the proposed pFedGate method adopts a much larger hypotheses space than FedMN. In FedMN, each modular is either connected dropped. While pFedGate doesn't 't only decide the connections of network (connected or dropped), but also scales weights of the remained blocks simultancously to improve the personalized performance.
to
G IMPLEMENTATION DETAILS
Datasets. We conduct experiments on several widely used FI. datasets including EMNIST Cohen
ct al. (017) and FEMNIST Caldas et al. 2018)) for 62-class hadnwritten character recognition, and CIFAR IO/CIFAR 100 Krizhevsky (2009) for 10-class/100-e
image classification. We follow the
heterogeneous partition manners used in Marfoq et al. (202I): Caldas et al. (2018): Diao et al. (202
Fallah et al. (2020): FEMNIST was partitioned by writer and generate the other three FL datasets using Dirichlet allocation of parameter =0044. We adopt 10% sub-samples of EMNIST (81,425
samples) and 15% sub-samples of FEMNIST (98,671 samples), and allocate the sub datasets 100
19

---

and 539 clients for EMNIST and FEMNIST respectively. For CIFARIO/CIFARE (60,000 samples), we allocate them to 100/50 clients. All datasets are randomly split into train/valid/test sets with ratio 6:2:2.
Baselines and models. We consider the following competitive baselines including SOTA personal- ized and efficient FL methods in this work:
FedAvg McMahan et al. (2017): the classical FL method that simply aggregates model updates in a weighted averaging manner;
FedAvg-FT: a basic personalised baseline that fine-tunes the global model with local data before model local evaluation;
Local: naive personalized method that trains models on local datasets without FL commu- nication;
pFedMe Dinh et al. (2020b) decouples the personalized model and global model with Moreau envelops based regularization;
LG-FedAvg Liang et al. (2200) achieves personalization with improved communication efficiency;
Ditto Li et al. (2021b) SOTA pFL method that introduces a local personalized model for each client, which is trained with model parameter regularization according to global model;
202T)) deals with data heterogeneity via the mixture of multiple global models. We use 3 models according to the authors' default choice;
FedEM Marfoq et al.
(2021) proposes to improve the FL performance and communication efficiency via sharing partial model parameters among FL participants. Only the low-layers of models for feature extraction are uploaded to server and aggregated, and the remaining head parameters are locally trained for personalization. Following the authors' sharing manner, we adopt the last classification layers as local personalized model parameter;
FedRep Marfoq et al.
FedMask Li et al. (202 learns distinct binary masks for the last several layers of the local models, and aggregates the masks with an intersection operation. Following the mask layer choice manner similar to the authors, in our experiments, the one-shot mask is applied in the last layer for the adopted 2-layer CNN and the last 2 layers for the adopted 3-layer CNN respectively;
HeteroFL Diao Diao et al. (0021) uses heterogeneous model architectures for different clients to achieve personalization and improvements in both computational and communication efficiency. Recall that we can vary each client's sparse ratio s to reflect the clients' resource heterogeneity, since the affordable sparse ratio can fairly reflect the client's computation and communication capabilities. Clients with very limited computation and communication resources have to set close to O; On the contrary, clients with sufficient resources can set close to 1. Here we use the full model parameters for 10% clients and 50% parameters for the other 90% clients following the authors' computation complexity setting, which leads to an average sparsity 0.55.
To align with previous works, EMNIST/FEMNIST. and two LeNet-based CNNs Dinh et al. (2020b): Liang et al. (2020): Shamsian al. (221)) with different capabilities for CIFARIO and CIFAR 100. Specifically, the model used two convolutional layers with 5 x 5 kernels, max pooling and two dense layers with total of 2.171,786 parameters. The models used for CIFAR1O and CIFAR 100 have a LeNet-based structure with an additional linear classification layer, and total of 256,830 and 3,537,444 parameters respectively.
2-layer CNN Reddi al. (2021 Marfog et al. (02 for
for
Platform and Syper-parametert We implement all models with PyTorch, and run experiments on Tesla V 100 and NVIDIA GeForce GTX 1080 Ti GPUs. For fair comparisons, we adopt the same com- munication rounds for all methods and search for the optimal configuration of haper-parameters using
20

---

Table 4: The adopted learning rates for pFedGate all datasets.
EMNIST
FEMNIST
CIFARIO
CIFARI00
11
1lg
flg
0.1
0.1
0.1
0.1
0.03
0.05
0.1
1.5
0.5
0.1
0.1
0.1
0.05
0.03
1.5
0.03
1.5
0.3
0.03
0.5
0.3
0.05
0.03
1.5
0.05
0.5
the validation sets. We run each experiment 3 times with the optimal configurations and different ran- dom seeds, and report the average results. For each method each dataset, and grid search the learning rate M2 from [0.005, 0.01, 0.03, 0.05, 0.1, 0.3, 0.5). set the communica- tion round 7 400, the batch size as 128 and the local update step epoch. For pFedGate, the learning rate of gating layer is searched from [0.01, 0.05, 0.1, 0.5, 1, 1.5]. and we set the block size splitting factor as epoch. For PFedMe, we search its penalization parameter from [0.0001, 0.001, 0.01, 0.1, 1. 10]. For Ditto, we search its regularization factor from [0.05, 0.1, 0.5, 0.8). For FedRep, we search its learning rate for personalized model from [0.05, 0.005, 0.5, 0.01, 0.1]. For FedEM, we set its number of global models as We summarize the adopted learning rates in Table
the SGD optimizer
5 for all evaluated models. For FedAvg-FT, we use the local fine- fine-tuning step
Global Model Aggregation Detail. We present more details about the global model aggregation of pFedGate. After local training, the client only uploads the updates of the parameters in the global model that are selected to form the client's local model. In other words, the client uploads the non-zero parameters updates with their corresponding index the global model. The server then aggregates the received model updates according their index.
Considering the following toy example: there are four clients, and the global model has a total of three parameter blocks. Each client uploads dictionary whose key denotes the index and the value denotes the corresponding parameter updates.
Client 1: 0: dg. 2: 82;
Client 2: dg. 2: 82:
Client 3: 0: 8o, 52;
Client 4: 0: 6o, 1: 60. 2: 82.
After receiving the above updates, the server aggregates the parameter updates with index 0 by weighted averaging the 6os from clients 1, 3, and 4. The other parameters are aggregated similarly.
H ADDITIONAL EXPERIMENTS
H.1 NOVEL CLIENTS GENERALIZATION
To evaluate the generalization of PFedGate for the novel clients that haven't participated in the previous FI. training stage, we conduct experiments with similar simulation settings to Diao et al. (202T): Marfoq et al. (202T): Yuan et al. (2022), where the novel clients only fine tune the global model their local dataset. Specifically, evaluate the selected and remaining clients separately. The results are summarized Table 5
randomly select 20% clients novel clients, and
where Acc and Ace indicate the results of FL-participated clients and novel clients respectively, and A = Ace Ace indicates the accuracy generalization gap. The results show that the proposed method PFedGate can generalize to novel clients well and gain smaller accuracy gaps than compared methods. For the novel clients, instead of re- training the over- parameterized global model (possibly small amounts of) local data, PFedGate only needs to train the personalized lightweight gating layers with small number of parameters, and thus achieves efficient and effective local adaptation.
21

---

Table 5: Averaged accuracy when testing on novel clients that are not participated in the training stage of FL. The Acc indicates the results of novel clients, and indicates the generalization gap Acc Acc.
FEMNIST
CIFARIO
Ace
Acc
Acc
Ace
FedAvg FedEM
76.39
74.93
1.46
67.78
66.15
1.63
79.21
78.26
0.95
71.92
70.75
1.17
PFedGate, s=1
87.79
87.18
0.61
73.97
73.18
0.79
PFedGate, s=0.5
86.64
86.19
0.45
74.12
73.19
0.93
pFedGate. s=0.3
85.69
85.12
0.57
73.64
72.78
0.86
H.2 PARTIAL CLIENTS PARTICIPATION
We have seen method can consistently and simultaneously improve the efficiency and model accuracy as Table [ shows. One can arise such a natural question: when combined with other efficiency improvement techniques such as client sampling. is pFedGate still effective? Here experiments by uniformly sampling 20% clients without replacement at each round, and summarize the results in Table [ It is observed that compared with baselines having about 1.45% 3.56% performance drop, our method still achieves strong and comparable performance to the non-sampled case, verifying the effectiveness and robustness our proposed method again.
H.3 CONVERGENCE STUDY
We demonstrate the convergence curves of FedAvg, HeteroFL with average sparsity rate as 0.55, the strongest baseline, FedEM, and the proposed pFedGate with different sparsity rates on EMNIST dataset in Figure We with the baselines, which provides empirical evidence for the Theorem 2 In addition, to gain further insights into the proposed method, plot the histogram of averaged gating weights of all clients on the CIFAR10 dataset in Figure 7 We can see that the sparse pattern becomes stable as we train the gating layer with more local datasets, showing that the proposed method can achieve effective optimization and converge to certain global points under distinct personalized local models.
that the proposed method achieves comparable convergence speeds
H.4 MODEL. COMPRESSTON MANNER STUDY
We gain sparse local models in the proposed framework via learning personalized gating layers and predicting sparse gated weights for model sub-blocks. As introduced in Section 5.2 we propose simple and general split manner that chunks the model parameters into B equal-sized sub-blocks, where the split factor B provides flexible splitting granularity. Here we study the sparsification technique proposed in our method by varying the split factor B and comparing it with SOTA PFL method FedMask Li et al. (2021a), that adopts binary masks compress the parameters of models' last layers. The results are shown in Table 7 where we examine the FL accuracy by setting B [2, 5, 10) and [0.3, 0.5).
Table 6: Averaged accuracy when randomly sampling 20% clients at each round. The last two columns indicate the average drop compared to non-sampled case.
FEMNIST (1)
CIFARIO (t)
Drop (J)
Acc.
Acc
Acc
Acc
Acc
Acc
FedAvg FedEM
77.45
57.98
66.31
57.96
3.56
2.55
78.54
63.37
71.12
60.76
1.45
1.78
pFedGate, s=1
87.86
77.43
74.29
64.11
0.82
1.13
pFedGate, s=0.5
86.72
75.12
74.25
64.36
0.79
0.21
PFedGate, s=0.3
85.78
74.89
73.91
64.38
0.36
0.80
22

---

Convergence Curves
0.8
0.8
0.4
0.2
Round
0
100
150
200
PFodGate
pFedGate, s=0.5
pFedGate,
FedAug
FedEM
HeteroFL
Figure The convergence curves of FedAvg, HereroFL, pFedGate and the strongest baseline, FedEM on EMNIST. The pFedGate achieves comparable even better (s=l) convergence speeds than baselines.
Gating Weights Histogram
Gating Weights Histogram
68
0.6
0.
02
50
100
150
100
190
203
Round
Gating Weights Histogram
Gating Weights Histogram
2.8
0.5
0.4
Roundi
Round
Figure 7: The convergence curves of PFedGate in terms of the histogram of averaged gating weights over all clients on the CIFARIO dataset.
From Table we have the following observations: Our method achieves better performance than FedMask in various sparsity settings. Besides, when increasing the sparsity (s 0.5 to 0.3), our method with = 5 still achieves good performance while FedMask gains larger performance drops. These results verify the effectiveness of the proposed adaptive sparse weights prediction again. As gains relatively worse results
for the impact of B, on the one hand, we can see that too small than B 5 there may be insufficient sub-bo blocks to model the clients' diversity. On the other hand, the larger B = 10 achieves similar results to B = 5 while larger performance drop when increasing sparsity. We empirically found that B 5 has good robustness and adopt it the default value in our experiments.
23

---

Table 7: Averaged accuracy comparison for pFL methods with and without model compression. The numbers in the parentheses indicate the accuracy difference between sparsity s 0.5 and 0.3 for FedMask and pFedGate.
FEMNIST
CIFARIO
Acc
Acc
Aoc
Acc
FedAvg FedEM
76.51
60.82
68.33
60.22
80.12
64.81
72.43
62.88
8=0.5
78.69
62.16
70.54
61.37
FedMask
8=0.3
77.41 (-1.28)
60.69 (- (-1.49)
68.46 (-2008)
59.05 (-1.32)
s=5.5
86.31
75.68
74.07
64.21
B=5
8=0.3
86.75 (+0.44)
76.47 (+0.779)
73.65 (-0.42)
64.39 (+0.18)
s=0.5
81.10
71.28
70.81
61.03
pFedGate
B=2
$=0.3
80.03 (-1.07)
70.72 (-0.56)
70.65 (-0.16)
60.66 (-0337)
$=0.5
85,38
74.91
72.94
63.59
B=10
s=0.3
84.67
(-0.71)
75.10 (4-0.19)
72.48 (-0.46)
63.58 (-0.11)
24


Reviews:
[{"review_id": "snzwPGx_BYd", "reviewer": "Reviewer_PyZd", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper proposes a personalized federated learning framework that selects a subset of model parameters (thus sparse) for each training example via personalized gating units for each client (Fig.1). The proposed method, pFedGate, has a gating unit/layer for each client, consisting of a rescaling factor M, an importance factor G and learns the binary mask by solving a knapsack problem per training example (Fig.2). Theoretical analysis on generalization, convergence and complexities are provided. Experiments on common personalized FL benchmark datasets show that pFedGate can outperform existing methods.", "summary_of_the_review": "The paper proposes a framework for personalized FL and it can work well in the experiments. However, it does not provide sufficient justification for the main claim/contribution of solving the resource heterogeneity issue as all clients still need to store the global model locally for training and inference.", "strength_and_weaknesses": "Strengths\n- Writing is clear and easy to understand\n- Thorough theoretical analysis\n\nWeaknesses\n- The framework fails to solve the resource heterogeneity issue since the clients still need to store the whole (global) model.\n- Some implementation and experiment details remain unclear.\n\nDetail comments:\n\n1. Sec.4 first paragraph: the two-step process “still requires computational and communication costs corresponding to the un-compressed models during the FL process”. However, according to Fig.1, pFedGate also needs to store the un-compressed model locally in order to compute the compressed model using M’, which is also mentioned in Sec.5.1 “all clients share the same global model \\theta_g that downloaded from server”. In addition, since every example uses different blocks of the model, each client has to store the whole model for inference. Therefore, both training and inference are dense, making the main contribution unsubstantiated. (Appendix E is also misleading.)\n\n2. The gradient computation requires further discussion. The forward pass of every example requires solving a knapsack problem as shown in Sec.5.2.3. Combing with the fact that we are training multiple networks (\\theta and \\phi), it would be helpful to elaborate on how the gradient of each network is computed using the knapsack solution. \n\n3. What is the relative sparsity of gating layer s_{\\phi_i} in Sec.6.3?\n\n4. For the experiments\n- How many clients are used for the experiments in Sec.7.2?\n- Sec.5.2.2 discusses that different DNN layers can have different block structures. Then how are the layers being partitioned in the experiments?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "f9dJkvusjWF", "reviewer": "Reviewer_sfrQ", "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": "", "summary_of_the_paper": "The paper proposes a new framework called pFedGate for training personalized models at client devices, such that each model can have different sparsity level depending on the devices computational and memory capacities. The idea is to generate personalized masks with different sparsity levels for each device, using a small gating layer per device. The gating layer itself is small in size and hence the paper claims that it does not add much overhead. The empirical results show that this technique indeed achieves better personalization than existing methods.", "summary_of_the_review": "While the proposed idea of generating personalized masks (gating weights) is novel and has potential, I have some concerns regarding the theory and experimental results that I have mentioned above.", "strength_and_weaknesses": "Strengths:\n1. The proposed framework seems to achieve better personalization accuracy than existing models.\n2. The idea of generating personalized masks (gating weights) using a computationally cheap network is novel.\n\n\nConcerns / Questions:\n1. I think Assumption 1 might be a strong assumption, since it assumes bounded diversity between the globally optimal model, and the optimal sparse local model. In particular, I think $\\sigma_i$ might itself depend on the level of sparsity for the device.\n\n2. In the proof of proposition 1, I do not follow how the Reverse Cauchy-Schwarz inequality is applied, since the left hand side of Eq. (13) has the l2 norm squared of element-wise multiplication of vectors instead of inner product. To be precise, the left hand side will look like $(\\sum_j (M^*_{i,j}\\theta^*_{g,j})^2 )$ instead of $(\\sum_j (M^*_{i,j}\\theta^*_{g,j}) )$. Also, I think the denominator of Eq. (4) should not have the square in norm of $\\theta^*_{g}$.\n\n3. The experimental results do not provide the time (in seconds) and memory requirements (in GB / MB) for the training of the models. Further, the convergence vs communication round curve is only provided for EMNIST dataset. This data is important since one of the motivations for this paper is to perform Federated Learning efficiently on computationally slow devices.\n\n4. In Eq. (7), is the gradient w.r.t $\\phi$ as well? In other words, does Theorem 2 prove convergence for the gating layer as well?\n\n5. On page 6, section 6.1, I think the definition of $L(\\theta_g, \\phi_i)$ and $\\hat{L}(\\theta_g, \\phi_i)$ should not have the $i$ in subscript on the left hand side since it also appears in the summation on the right.", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "X30uHMeAlD0", "reviewer": "Reviewer_gH8r", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "\n\nThe draft proposed an approach for efficient personalized FL by adaptively and efficiently learning sparse local models(a subset of the global one) with a shared global model. With a lightweight trainable gating layer, the proposed algorithm enables clients to reach their full potential in model capacity by generating different sparse models accounting for both the heterogeneous data distributions and resource constraints. ", "summary_of_the_review": "Basically,  The paper is of good quality. Although the novelty is not very high since there are two existing papers that adopt similar ideas for Personalized FL, this paper provides a good theoretical analysis and the results are very promising. If the authors can add a good discussion on the novelty compared with the two papers mentioned below, I would champion the acceptance.", "strength_and_weaknesses": "Strength:\n\nS1). The authors provided a theoretical analysis of the proposed algorithm.\n\nS2). The method is validated with sufficient experiments.\n\nS3). The results are very promising.\n\nWeakness:\n\nW1). The novelty of the paper is not very high since there are already some papers with similar ideas in FL. As claimed in Related work “our method generates different sub-models from the whole global model with a larger learnable parameter space to handle heterogeneous data distribution”, actually the following work is using a similar idea. It also adopts the block-wise selection from the global model and generates personal and sparse architecture for different clients. \na). Personalized Federated Learning via Heterogeneous Modular Networks. IEEE ICDM 2022. \nhttps://arxiv.org/pdf/2210.14830.pdf\n\nb). Personalized Neural Architecture Search for Federated Learning, Minh Hang et al. Neurips Workshop 2021.\nhttps://neurips2021workshopfl.github.io/NFFL-2021/papers/2021/Hoang2021.pdf\n\nActually, these two papers are using more elegant solutions for PFL. The proposed solution adopts the mixture method of ideas of NAS and FL. \n\n\nW2). It is strongly suggested to include the two papers above in the revised version for discussion of novelty of the proposed approach. B) is discussing the fine-grained subnetwork selection and A) is discussing block-wise subset network selection for communication efficiency that is similar as this paper.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "9iK1ugcpwUa", "reviewer": "Reviewer_eJXn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "### Summary\n\nThis paper addresses data and resource heterogeneity of each client in Federated Learning. This paper proposes a gating function $g_{\\phi}(x, s_i)$ that allows easily adaptation to each client while taking sparsity into account like computation resources. As gating function generates masking parameters for local models, it can response to various model-size, heterogeneous dataset and computation resources. Especially, the authors suggest that sample-wise model is better effective than a client-wise local model in personalized FL. \n\nTechnically, the authors demonstrate that the proposed method does not hurt the previous theoretical convergence bound and generalization gap in FL. This empirically achieves the state-of-art average performance in personalized FL, ensuring bottom decile performance in a variety of experimental results like EMNIST, FEMNIST, CIFAR10 and CIFAR100. ", "summary_of_the_review": "In summary, I believe the paper holds an interesting research direction worth exploring in personalized FL. However, in my opinion, the current manuscript does not meet the standards for acceptance at ICLR 2023. The authors are strongly encouraged to present the limitations of the method by empirical manners, and improve technical aspects as I do believe this is a promising idea.\n\n-------------------\n\n**After rebuttal** : I'm satisfied with the authors feedback related to experimental results. They provide several experimental evidences to support the efficiency of their model and performance improvement via this rebuttal phase. However, I believe that theoretical aspects must be revised and re-organized in the camera-ready version. Furthermore, since the authors have responded my comments after the end of discuss period, so they were not able to revise the manuscript. Under the condition that author assure all comments will be included in the camera ready version, I score this paper as 6.", "strength_and_weaknesses": "### Strength\n\n- This paper consistently presents empirical performance improvement in various experimental results. \n- It also suggests sample-wise local models by using gating function $g_{\\phi}$, so that we do not practically need to design sophisticated manipulation for it, since this gating function can be learnt during training. It obviously leads to work in FL that disregard data and resource heterogeneity.\n- This paper offers many ablation studies of learned FL models, including ones that distinguish each client without additional training. This empirical studies appears relevant for deriving performance improvement of all cases, and supports author's claims.  \n\n### Weakness\n\n- This paper should clarify a limit of data and resource heterogeneity of FL framework. In the manuscript, their voices are likely to be misunderstood, so that the proposed method may be used to totally different devices like edge devices and high-performance cloud computation. According to my understanding, this method supposes that all devices have sufficient memory to simultaneously load global and gating function, but each device's computation capability varies.\n\n- Along with the above comment, the authors should reveal the how extents of sparsity this model can support. Particularly, they should investigate when a gating function rapidly deteriorates. Also, they need to show characteristic of representation capability between global and local models. Lastly, they should clearly reveal a limitation and boundary of this method by changing communication frequency and data distribution of each client.\n\n- In technical aspects,  theoretical reasonings in this paper somewhat mismatch their claim that emphasizes sparsity of each client. Especially, in theorem 1 and 2, they do not consider the sparsity of each client, as well as not provide any high-level understanding of this sparsity based on those theorems. Instead, through very strong assumption like strong convexity of all losses and independence with respect to global, gating functions and these parameters $\\phi_i$, it simply reveals that the proposed method does not violate the previous FL framework from point of the number of effective samples and convergence analysis.\n\n- This paper must compare of FedMask[1] in terms of masking characteristics by varying sparsity. The FedMask also employs masking parameters for each client, so it is completely compatible with the proposed method excluding sample-wise models. If the authors want to highlight practical usage of heterogeneity of data and resources, this comparison must be presented for better understanding of this paper. However, in experimental results on the manuscript and appendix, they simply describe the proposed method outperform those algorithms. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2lXzXgqkdm", "reviewer": "Reviewer_wTvc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a new approach to personalized federated learning via sparse model adaptation. The key idea is to configure local models as subnets of a master net representing the global model. \n\nThe subnets are generated via a block-wise binary mask that (1) zeroes out less important components; and (2) enforce a certain sparsity level such that the no. of non-zero parameters of resulting subnets fits with local hardware constraints. \n\nLocal models are therefore heterogeneous compression of the same global model. This importantly allows local models to have heterogeneous architectures, which is, to my understanding, a less studied aspect of personalized FL. Most existing personalized FL approaches only consider data heterogeneity (but not model heterogeneity).   \n\nThe generative mechanism of the subset is parameterized by a two-flow model: (1) one flow generates crude masks (that might violate local sparsity constraints); (2) the other flow generates an importance score for each parameter blocks. The output of two flows are combined via solving a knapsack problem, resulting in a binary mask that meets the hard sparsity constraint.\n\nComparing to existing model compression or gradient quantization techniques, which are often post-training editing approaches, the proposed approach allows learning both the compression mechanism & the updates to the global model. ", "summary_of_the_review": "The paper presents an interesting formulation of personalized FL & a new solution addressing a less studied issue of model heterogeneity. The novelty of this work is strong but its execution needs more polishing, particularly regarding missing experiments with both related work & vanilla baseline (to make sure such proposed mechanism is needed & cannot be bypassed by simpler, trivial engineering solution). The presentation of proving techniques can also be improved. Please refer to my specific comments above. Overall, I believe this will be an acceptable paper if the above are addressed sufficiently. ", "strength_and_weaknesses": "Strengths:\n\n+ Both problem formulation & proposed solution are novel to me. I have not seen similar approaches to this before.\n+ The technical presentation is very well-organized, particularly the well-structured appendix that makes it easy to zoom into each component of the proposed work\n+ The empirical results are reasonably extensive with comparison to multiple baselines in the same direction\n+ There are interesting theoretical results showing both convergence of the proposed algorithm and the existence of optimal local solution: among optimal local solution that meets local sparse constraints, there exists one that can be acquired via masking the global model\n\nWeaknesses:\n\n- Lacking comparison with a known baseline -- Fallah et al., 2020\n- Lacking discussion with other related works on FL with heterogeneous models\n- Theoretical results are established under strong convexity of the loss function, which is likely not the case unless the model is linear\n- Lacking experiments showing advantages over simpler knowledge distillation technique for FL with heterogeneous model\n\nI will elaborate on those weaknesses with specific comments & suggestions below.", "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": {}}]

Author rebuttal:

Decision: Reject