Flow: Per-instance Personalized Federated Learning
Authors: Kunjal Panchal
Sunav Choudhary
Nisarg Parikh
Lijun Zhang
Hui Guan
Venue: NeurIPS 2023 poster (2023)
Keywords: federated learning
personalization
statistical heterogeneity
dynamic routing
TL;DR: Flow addresses the challenge of statistical heterogeneity in federated learning through creating a dynamic personalized model for each input instance through a routing mechanism.

Abstract: Federated learning (FL) suffers from data heterogeneity, where the diverse data distributions across clients make it challenging to train a single global model effectively. Existing personalization approaches aim to address the data heterogeneity issue by creating a personalized model for each client from the global model that fits their local data distribution. However, these personalized models may achieve lower accuracy than the global model in some clients, resulting in limited performance improvement compared to that without personalization. To overcome this limitation, we propose a per-instance personalization FL algorithm Flow. Flow creates dynamic personalized models that are adaptive not only to each client’s data distributions but also to each client’s data instances. The personalized model allows each instance to dynamically determine whether it prefers the local parameters or its global counterpart to make correct predictions, thereby improving clients’
accuracy. We provide theoretical analysis on the convergence of Flow and empirically demonstrate the superiority of Flow in improving clients’ accuracy compared to state-of-the-art personalization approaches on both vision and language-based tasks.

Flow: Per-instance Personalized Federated Learning
Kunjal Panchal
Sunav Choudhary Adobe Research Bangalore, India schoudha@adobe. com
College of Information and Computer Sciences University of Massachusetts, Amherst
Amherst, MA 01003 kpanchal @umass edu
Nisarg Parikh
Lijun Zhang, Hui Guan
Khoury College of Computer Sciences Northeastern University
College Information and Computer Sciences University of Massachusetts, Amherst
Boston, MA 02115
Amherst, MA 01003 {li flijunzhang, hui Bagguannnuuassssss edu
parikh. htw.:hhhniiitttthhatttere...ee edu
Abstract
Federated learning (FL) suffers from data heterogeneity, where the diverse data distributions across clients make it challenging train single global model effec- tively. Existing personalization approaches aim to address the data heterogeneity issue by creating personalized model for each client from the global model that fits their local data distribution. However, these personalized models may achieve lower accuracy than the global model in some clients, resulting in limited perfor- mance improvement compared to that without personalization. To overcome this limitation, we propose per-instance personalization FL algorithm Flow. Flow creates dynamic personalized models that are adaptive not only to each client's 's data distributions but also to each client's 's data instances. The personalized model allows each instance to dynamically determine whether it prefers the local parameters its global counterpart to make correct predictions, thereby improving clients' accuracy. We provide theoretical analysis on the convergence of Flow and empiri- cally demonstrate the superiority of Flow in improving clients' accuracy compared to state-of-the-ans art personalization approaches both vision and language-based tasks. The source code is available on GitHub!
Introduction
Federated Learning (FL) is a distributed machine learning paradigm that enables edge devices, known "clients", which collaboratively train machine learning model called "global model" (T]. However, because the server, which is the FL training orchestrator, does not have access to or knowledge of client data distributions, poses challenge of statistical heterogeneity 2 This heterogeneity hinders the server's ability to train an ML model on a large quantity and variety of data and also impacts the client's ability benefit from generalizable model without sharing any information about its data. To address this challenge, personalization has been studied 4 5
improve prediction performance. Recent literature consistently demonstrates that personalized models achieve higher prediction performance than the global model aggregated over clients [SHTO] These approaches typically create personalized model specific each elient's 's data distribution, and thus we refer to them as "per-client personalization".
https:/ggthnb..co///ttuaarr//o
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

However, we have identified two factors that limit the performance improvement of existing per-client personalization approaches in terms of clients' accuracy. First, as reported in the evaluation in Sec. [5] we found that personalized models can achieve lower accuracy than the global model on up to 31% clients, causing limited improvement accuracy averaged across all clients. Second, even if personalized models achieve higher accuracy on client compared to the global model, they can still produce incorrect predictions on up to 11% 1% of data instances on clients that could be correctly handled by the global model, causing limited accuracy improvement from personalization on that client. These observations reveal a significant drawback of existing per-client personalization approaches: each client's 's personalized model is a static network that cannot accommodate the heterogeneity of the local client's data instances. As a result, every data instance on a client is constrained use its personalized model for prediction, even though some instances could benefit from the better generalizability of the global model.
To overcome the above limitation, this paper proposes per-instance and per-client personalized FL algorithm Flow via dynamic routing to improve clients' accuracy. Flow creates dynamic personalized models that are adaptive to each client's 's individual data instances (per-instance) distribution (per-client). In a FL round of Flow, each client has both the global model parameters that are shared across clients and the local model parameters that are adapted to the local data distribution of the client by fine-tuning the global model parameters. Flow creates dynamic personalized model per client that consists of local and global model components and dynamic routing module. The dynamic routing module allows each data instance on a client to determine whether prefers the local model parameters their global model counterparts make correct predictions, thereby improving the personalized model's accuracy on the client compared to that of a local model or a global model. At the same time, through dynamic routing, Flow could identify instances in each client that agree with the global data distribution to further improve the performance of the global model, offering a good starting point for any new client to personalize from. Since Flow is a client-side personalization approach, it can work with server-side optimization methods like FEDYOGI
well as their data
We theoretically analyze how dynamic routing affects the convergence of the global model and person alized model in Flow and also empirically demonstrate the effectiveness of Flow in improving clients' accuracy compared to state-of-the of-the-art personalization approaches cross-device language and vision tasks. For the newly joined clients, the global model from Flow achieves 2.81 2.81% (Stackoverflow), 3.46% (Shakespeare), and 0.95% % (CIFARIO) better accuracy the global model against its best performing baselines respectively. After personalization, the dynamic personalized model from Flow sees improvements of 3.79% (Stackoverflow), 2.25% (Shakespeare), and 3.28%-4.58%% (CIFARIO) against the best performing baselines. Our in-depth analysis shows that Flow achieves the highest percentage of clients who benefit from personalization compared to all baselines and reduces the number of instances that are misclassified by the personalized model but correctly classified by the global model, contributing the better personalized accuracy from Flow.
We summarize the contributions as follows:
We propose per-instance and per-elient personalization approach Flow that creates person- alized models via dynamic routing, which improves both the performance of the personalized model and the generalizability of the global model.
We derive convergence analysis for both global and personalized models, showing how the routing policy influences convergence rates based on the across- and within- client heterogeneity.
We empirically evaluate the superiority of Flow in both generalization and personalized accuracy on various vision and language tasks in cross-device FL settings.
2 Related Work
interpolation method and Personalized Federated Learning. Personalization in FL has been explored primarily on client-level granularity. APFL (6) interpolates client-specific local model weights with the global model weights which are sent by the server. Meanwhile, Flow is an intermediate- also includes a dynamic policy to interpolate at instance-level granularity. We note that DAPPER 12 interpolates the client dataset with global dataset, which is impractical for the cross-device use cases FL. focused on in this paper. Regularization is another popular way of creating personalized model. It encourages a personalized model of each client to be close to the global model as explored

---

in DITTO [3] and PFEDME 14). Finetuning partial or entire global model to get the personalized model has been studied in LGFEDAVG 77. which finetunes and personalizes the feature extractor and globally shares the classifier head, FEDBARI BAU and aggregates the feature extractor, and FEDREP which finetunes and personalizes the classifier head and globally shares the feature extractor. Learning personalized representations of the global model has been explored in FEDHN [16] where a central hypernetwork model is trained to generate a personalized model for each client. PARTIALFED [77 makes layer-wise choice between global and local models to create a personalized model, but it sends the personalized models back to the server in lieu of separate global model. This method has limitations in terms of training the base global model (on which the personalized model would be based) with FEDAVG, which has been observed to be insufficient against non-iid data [8.. Besides, the strategy does not create dynamic personalized model during inference. None of the above work has explored instance-level personalization.
15 which freezes the classifier head and only updates
Personalized models from previous work KNNPER 19] exhibits per-instance personalization behavior. The personalized model of a client makes a prediction based on features extracted from the global model from instance well as features from the instance's 's nearest neighbors. However, KNNPER trains the global model parameters in the same way as FEDAVG, which has been shown to perform poorly in heterogeneous data settings [8] In contrast, Flow's dynamic routing mechanism results in a global model with better- seater-genrralzzed performance amidst heterogeneous instances, which ultimately leads to higher boost in the performance of personalized models well.
Dynamic Routing. Motivated by saving compute effort for "easy to predict" instances. instance-level dynamic routing has been matter of discussion in works related to early exiting [20-22], layer skipping (23, and multi-branchin
(4 25]. SKIMRNN 266 explored temporal dynamic routing where depending on the input instance, trained policy can determine whether to skim through the instance with a smaller RNN layer (which just updates the hidden states partially), or read the instance with standard (bigger) RNN layer (updating the entire hidden state). Our work is motivated by the question of Depending on the models' utility and instances' heterogeneity, which route to pick?. This can be achieved by using routing policy to dynamically pick from two versions of model, which are equivalent in terms of computational cost but different in terms of the data they are trained on.
3 Our Approach
We introduce Flow, a per-instance and per-client personalization method that dynamically determines when use a client's local parameters and when use the global parameters based on the input instance. Table summarizes the notation used in this paper.
Algorithm describes the workflow of Flow. During each FL round, the server samples M participating
Table 1: Notations
clients with sampling rate of p. Upon receiving the
global model Wy and policy parameters v9 (Line 3 each participating client personalizes and trains wg in
K
#Eppcch for training
Total number of sampled clients M
five major stages: (1) Split the training dataset into two
m
Client index E [M]
halves: (m. and Sm.g (Line G Sm,t will be used to
M
Set of available clients
update the parameters in the Tocal model parameters while Sm.g will be used train the parameters in the global model and a routing module. (2) Derive the local parameters we by finetuning the global parameters wy
P
Client sampling rate
Local learning rate
W/
Global model
V/g
Policy module
for K2 epochs with Sm.e (Line 7 (3) Construct a
Wg.m
Local version of the global model
Wi,m
Local model of mn client
dynamic personalized model Wp.m by integrating the
Wp.m Personalized model of th client
local versions of the global parameters Wg. and policy parameters y..m. and the local parameters we. Here, the routing policy Vi determines whether the execution path of an instance should use We or Wg. (4) Train the routing policy b... and the local version of
Dm Data distribution of mhh client
the global parameters Wg.m alternatively for K₂ epochs (Lines TOp with Cm.g- Although K₃ and K₂ can be different, we later use K to denote both Ki and K2 for ease of theoretical analysis. (5) Send the local version of the global model parameters W'g.m and the policy parameters 2... back to the server for aggregation (Line 14). Aggregation strategies are orthogonal to this work and we adopt FEDAVG M.
3

---

Next, we discuss the design of the dynamic personalized model up in detail. Figure T design of wp. Flow, wp is made of three components, the local model wy and global model wy and the routing module Ve that selects the execution of local or global model layers for each data instance.
Tillustrates the
Local Parameters. We use finetuning to get the local parameters wt.m the r-th round since finetuning has proven be less complex yet very effective method of personalization [27]
(r) Given a global model of the previous round, Wg.m. we finetune it for K epochs to get wi.m This local model would be reflective of the client's 's data distribution Dm Note that we use one half of the dataset to get "2.m and reserve the other half of the training dataset for updating the global model and the policy (i.c., the routing module) parameters. This is to make sure that the policy parameters, which would decide between local and global layers based on each input instance, not overfitted in favor of the local parameters. In Figure 1 the local parameters are shaded green, denoted by we. The update rule for t. is:
K
(r,K) W2 2,m
V Im (w
(rr))) Sm,e), where (r.0) = (r)
me
Algorithm 1: Pscudocode of Flow
Server randomly initializes the global model Wg and the policy module 2
personalized
global modsl
X Inputs
for each round do
oupputs
policy model
Send wg. 1/g to sampled M clients
for m E [M] in parallel do
model
Mg.mn < Wy. Wg.. 6- digi MF.m 6- W...
Creating two mutually exclusive datasets
towerdss next policy lnyer
Sm.e, Sm.g + Dn,
Ubase
Train We.on for Ki epochs
from previous
for E [K2] epochs do
W
ayer
Update aa according Equation
oxt
next. layer
10
Update 10.m according to Equation
probabillty of pickingg a roune
W:
end
12
Send back Wgm.s Va.m: nm = 16m.9l
13
end
Update W2 and vh with weighted average of each client's Wg and Plym
Figure 1: Illustration of the dynamic personalized model design proposed by Flow.
is end
Routing Module. The routing module is a model with fully connected layers, shown 4hass in
Figure After each layer vlasse model has early exits denoted as vexi which outputs a probability of choosing the layer in the global model wy the local model we. This probability at layer [L] computed as,
f a x Fm if = 0:
( = =190) q:
( softmax (ammmax((55))
(v (1) (i))) E 10 where
á v ((-1)))) otherwise,
where go and qi (1) (1)
(
(i) are the probability of picking the global parameter wg.m and the local parameter
Wrm respectively.
In order to train the routing parameters, we compute the training loss based on the output of the (r) personalized model wp.m. which averages the global model's output and local model's output weighted by q()), for each layer j E [L]:
() p.m (i) +- 4n ().
() g.m. (2) + qi () L (+) where
④ t- Im if f t- Wp.m
(-11 ()())) otherwise.
(3)

---

Let [m(-) denote the loss function on client m. Using the above personalized model (r) Wp.m Flow
updates the policy parameters as follows,
(ir 9mm
el(TT) 9.m
The V
fm Im(uggh wof Sm.a) - 2
Σ log qu )
(4)
_E[L]]
where - -jjr (og( is a regularization term that encourages the global model to learn on heterogeneous instances to improve the global model's generalizability.
Global Parameters. Global parameters Wi are trained alternatively with the routing parameters V.g. Flow updates the global parameters as follows,
1 (((+1) + w 9.
V w g.m.
fm (r(
(((+1) g.m. Smm.)
(5)
g.m
The goal of the alternative training is for the instances that are characterized better by the global data distribution to get diverted to the global model and the rest of the instances that are captured better by the local data distribution routed the local model. This improves the stability of the global model compared to approaches like APFL or KNNPER which still use the global model trained on all the instances, regardless of the level of heterogeneity. The effectiveness of the alternative training is validated empirically and discussed in Appendix D.2
Soft versus Hard Policy. During training, we use soft policy where the probability in Equation ranges over [0, 1] to update the parameters in the global model and the routing module. But during inference, we use a discrete version of the policy (Q))d E {0, 1}2 for q in Eq. The rationale behind this twofold: (a) Using hard policy saves compute resources during interence by executing either the global or the local layer for an instance instead of both. (b) Our empirical
evaluation shows negligible difference in performance of personalized models with soft and hard policies during the inference.
The dynamic nature of the personalized model in Flow introduces additional storage and computa- tional overhead compared to the canonical method FEDAVG with Fine Tuning (called FEDAvGFT). However, compared other oftte-of-thheart personalization methods such DITTO and APFL,, Flow requires similar or even less storage and computational overhead. Detailed analysis and comparison with baselines is in Appendix [
4 Theoretical Analysis
In this section, we give convergence bounds for the global model wa and the personalized model up of an arbitrary client in smooth non-convex cases. The bounds for strong and general convex cases are available in Appendix E Sections E.3 and E.5 To derive the bounds, we adopt two commonly
used assumptions in FL convergence analysis from AFO (Assumption 2, [TI) and SCAFFOLD (Assumption 1, 18) (1) We assume local variance between a client's 's expected and true gradient is bo-bounded. (2) We also assume that the dissimilarity between aggregated gradients of local expected risk and the true global gradient is (G. B) -ouuddde where both G and are constants capturing the extent of gradient dissimilarities. A detailed description is in Appendix Section F.2
Now we present the bounds on the norm of expected global (and local) risks on global (and per- sonalized) models respectively, at R-th (last) round. The proofs are in Appendix Sections E.3 E.3and
E.5
Theorem 4.1 (Convergence of the Global Model), If each client's 's objective function fm (and hence the global objective function F) satisfies 3 B-smoothness, a oo-bounded local gradient variance, (G, B) (B)dddsssmilarii assumptions, using the learning rate 23 I me S 2V53BK3 [for non non-convex case] in Flow, then the following convergence holds:
R
E
2 mh R
E
[(w
E [1]
R
of
G
oî
2 2v5B
K /R
B²R
B
5

---

Discussion. Here, q (and qî) are the probability of picking the global (and local) weights averaged over all instances sampled from the global data distribution. Given a fixed o and qi larger G increases the bound, indicating slower convergence of the global model due to higher heterogeneity. We made two additional observations on the convergence of Flow depending on q the bound.
One the one hand, when q + 1. Flow matches the linear (strong convex) and sub-linear (general convex and non-convex) convergence rates of FEDAVG [18) Specifically, q 1 results in conver- gence rate of ( Rte) (strong convex), (11/ R2/$) (general convex), and (1/RR) (non-convex). When q = 1, which also indicates qf = O, the local parameters do not influence global model updates since all instances on a client will be routed the global model and their gradients solely depend on the global model parameters. Flow degrades to FEDAVG in this case in terms of the convergence of the global model.
On the other hand, when - - 0 indicating all instances are likely to be routed to the local model, the bound goes to infinity. It is because the global model parameters won't get updated and thus won't 't be able to converge. This observation validates the necessity of the regularization term in Eq. encourage instances pick global model parameters.
Now we present the convergence bounds of the personalized model for the m-th client. The bound uses definition of gradient diversity (noted as 6m) to quantify the diversity of client's gradient with respect to the global aggregated gradient, following the prior work [29]. Higher diversity implics higher heterogeneity of the client.
Theorem 4.2 (Convergence of the Personalized Model). If each client's objective function Jmm satisfies 3-smoothness, Ot-bounded local gradient variance, (G, By B)-dissimilard assumptions, and using the learning rate πι S KV123R [for non-convex case] in Flow, then the following convergence holds:
R J (um )1
B
V
2 (B
(mm((()))))) - fmn(uu (um
( ())
R
g2
8%
qi. G2
O
of +
K
R2 K2
M
Gi R
Discussion. The theorem implies two main properties of the personalized models in Flow, First, for all convex and non-conved cases, the convergence rate of the personalized model in Flow is affected by the routing policy through the ratio qी mm G2 / We know that a higher value of the gradient dissimilarity constant G, indicates higher heterogeneity between the aggregated and expected global model. The ratio of / /q.... would be higher for heterogeneous client, since the client would get a higher probability of picking the local route (qî... + 1). The higher G and qi.,. results in slower convergence, On the contrary, a homogeneous client would benefit from a low value of qi /q3.... which would offset the high value of G. Hence homogeneous client's personalized model would converge faster than the one of a heterogeneous client. Second, we observe that gradient diversity of the policy model, 5% linearly affects the personalized model's convergence. Since the policy model also globally aggregated, a heterogeneous client would have high 5% and need more epochs per round to converge.
5 Experiments and Results
We empirically evaluate the performance of Flow against various personalization approaches for five non-iid vision and language tasks in terms of clients' accuracy.
Datasets, Tasks, and Models. We have experiments on two language and three vision tasks. The first three datasets which are described below represent real-world heterogeneous data where each author or user is one client. (a) Stackoverflow (30) dataset is used for the next word prediction task, using a model with 1 LSTM and 2 subsequent fully connected layers. (b) Shakespeare [I dataset is for the next character prediction task, using a 2 layer LSTM + layer fully connected model. (c) EMNIST 32 dataset is for 62-class image classification, which uses 2 CNN layers followed by 2 fully-connected layers. The models for the above three datasets have been described in
m The next two datasets are federated and artificially heterogencous versions of CIFAR10/100

---

datasets. (d-e) CIFARI0/100 33 datasets are for 10- and 100-class image classification tasks with ResNet18 B4 model. Both CIFARIO/100 have two heterogeneous versions each: 0.1-Dirichlet is more heterogeneous, and 0.6-Dirichlet is less heterogeneous. Details about the datasets and the hyperparameters are in Appendix
Baselines and Metrics. We compare Flow with the following baselines: the classic FL algorithms FEDAVG (35), state-of-the-art personalized FL approaches including FEDAVGFT (FedAvg Finetun- PARTIALFED 17,, APFL [6, FEDREP [8, LGFEDAVG 77. DITTO [3]. HYPCLUSTER
ing) 36
12 and KNNPER 19 and the LOCAL baseline which trains local model on each client's 's dataset
without any collaboration. We use the adaptive version of PARTIALFED as it shows better per- formance compared to the alternatives in [7]. We evaluate Flow and these baselines in terms of generalized accuracy and personalized accuracy, which correspond to the accuracy of the global model and the personalized model on clients' test data split.
We use Flower [37 library to implement Flow and all its baselines. We use an NVidia 2080ti GPU to run all the experiments with 3 runs for each. The random seeds used are O, 44, and 56. We do not observe significant difference in results using other random seeds (see results in Appendix D.4)
5.1 Performance Comparison
Generalized and Personalized Accuracy. The performance of Flow and its baselines are reported in Table for four datasets. Note that the LOCAL baseline has only personalized accuracy as it doesn't 't create a global model collaboratively. The FEDAVG has only generalized accuracy as it doesn't t personalize the global model for each client. Since PARTIALFED is stateful approach, we are unable to run it on the cross-device datasets (Stackoverflow, Shakespeare, EMNIST). Results for the rest of the datasets and their variance across different runs reported in Appendix
Overall, Flow achieves 1.11- 3.46% higher generalized accu- racy and 1.33-4.58% higher per- sonalized accuracy over the best performing baseline. In par- ticular, Flow outperforms KN- NPER, another per-instance per- client personalization approach,
Generalized (Ace,) and Personalized (Acc,) accuracy Table 2:
(the higher, the better) for Flow and baselines.
Datasets
Stackwverfow
Shakespeare
CIFARIO
CIFARIO (0.6)
Baselines
Ace,
Acc.
Acco
Ace,
Acc,
Accp
Ace,
Accp.
LOCAL
15.93%
18.70%
49.78%
62.74%
FEDAYG
23.15%
52.00%
60.98%
67.50%
FEDAYGFT
23.83%
24.41%
52.12%
53.68%
61.23%
73.03%
68. 19%
72.21%
KNNPER
23.16%
24.49%
51.87%
53.10%
59.62%:
75.14%
69.22%
10%
PARTIALFED
62.57%
73.20%
66.93%%
70.38%
by 1.66-6.64% and 1.33-6.97% in generalized and personalized ac-
22.96%
25.70%
52.38%
53.64%
62.87%.
69.53%
72.53%
DITTO
22.59%
24.36%
52.44%
53.95%
62.06%
72.06%
68. 12%
70.31%
FEDROP
18.92%
21.04%
46.71%
50.09%
64.85%
68 62%
69.77%
63.61%
curacy metrics respectively. KN-
NPER allows each instance to personalize the prediction of the global model based on its k- nearest neighbors at inference time. However, the global model is trained through the classic FL method FEDAVG, which is agnostic to the heterogeneity of data instances. In contrast, Flow trains the global model differently via parameterized dynamic routing module, which learns to put emphasis on data instances that are more aligned with the global data distribution improve the performance of the global model.
LGFEDAYG
22.61%
24.03%
51 10.0
51.43%
56.63%
73.19%
67.48%
68.94%
HYPCCLUSTER
23.75%
22.43%
51 92..
$2. 74%
63.64%
71.55%
65.44%
72.40%
Flow (Ours)
26.64%
29.49%
55.90%
56.20
66.26%
76.47%
70.88 %
77.11%
Flow also outperforms the per-client personalization approaches including APFL, DITTO, HYPCLUS- TER, and FEDAVGFT by 1.35-3.46 % (generalized accuracy) and 2.25-4.58% (personalized accuracy). Table 3: % of clients for which Accp > Accy (the higher, the better).
We improvements in generalized accu- racy of Flow because of the fact that the global model in Flow is trained based on the instances which align more with the
Stackoverllow Shakespeare CIFARTO (0. CIFARIO (0.6)
FEDAVGFT
79.26%
79.00%
97.18%
99.33%
global distribution. We see improvements
KNNPER
82.73%
68.87%
90.00%
90.00%
PARTIALFED
88.30%
84.80%
in personalized accuracy due to the limita- tion of the per-client approaches where some instances being correctly classified by the
APEL
69.66%
79.22%
87.48%
90.63%
DITTO
74.59%
73.74%
90.52%
89.61%
FEDREP
91.53%
79.78%
92.30%
84.64%
LGFEDAVG
83.47%
88. 43%
88.41%
89.59%
global model are incorrect on the personal-
HYPCLUSTER
80.46%
74.84%
95.11%
98.18%
ized model. We next give insights on why
Flow (Ours)
92.74%
89.77 %
98.33%
99.62%
Flow achieves better performance person-
alized and generalized accuracy compared to these personalized baselines.
7

---

pisbsk-orty
persona ony
globalony
panooalaadienly
(Probviiitt prking the ginbal mute)
1.0
0.30
0.25
0.20
0.15
0.30
0.4
0.05
0.00
relbby PT
Dee
Frosder
Festup
Lonedang
PmpClater
Piao
11 13
Baselines
indirce
Figure Wy and wp accuracies Figure Behavior of the routing policy from v for all instances at each layer for Stackoverflow.
for Stackoverflow.
Percentage of Clients Benefiting from Personalization. The goal of personalization is achieve higher prediction accuracy in each client by creating a per-client personalized model from the global model. We can thus measure the effectiveness of personalization by computing the percentage of clients for which the personalized model achieves higher task accuracy than the global model. The higher the percentage is, the better (or more effective) the personalization approach is.
Table 3 reports the results. We observed that Flow achieves the highest percentage of clients who benefit from personalization compared to all personalization baselines, echoing the better personalized accuracy from Flow. The percentage of clients who prefer personalized models can be as low as 68.87% (KNNPER on Shakespeare), which means personalization hurts up 31% % of clients' accuracy, as mentioned in the introduction. As contrast, Flow improves the percentage of clients benefiting from personalization to 89.77%-99. .66%% because each instance, the global model parameters and the local model parameters and can choose the one that better fits it. Note that the comparison in favor of the baselines since Flow also achieves better generalized accuracy, which makes it even harder for personalized models to further improve prediction accuracy.
client, has choice between
Breakdown of Correctly Classified Instances. Figure 2 further shows the breakdown of the percentage instances that are (a) correctly classified by the global model but not the personalized model (noted global-only, colored in yellow O), (b) correctly classified by the personalized model but not the local model (noted as personalized-onfe colored in blue O) and (c) correctly classified by both models (noted both-correct, colored in green in Flow and baselines Stackoverflow. The percentage of instances in y-axis is averaged over the test splits of all clients.
Overall, Flow increases the both-correct bars compared to all the baselines, which are the instances that contribute to the generalized performance of the global model. This explains the better generalized accuracy of Flow. Flow also increases the personalized-only bars and decreases the global-only bars, which correspond to the heterogeneous instances that prefer personalized models instead of the global model. This further explains the better personalized accuracy of Flow. Notably, for Stackoverflow dataset, existing personalization approaches still result in up to 4. 7.99-% of instances incorrectly classified by the personalized model but correctly by the global model. Flow reduces it 1.12-2.42% Similarly for the CIFARIO (0.6) dataset, as mentioned in the introduction, we notice up to 1 11.4% of instances falling under the global-only category, which Flow reduces 2.55%. echoes the aforementioned effectiveness of personalization Flow. The instance-wise accuracy breakdown for the rest of the datasets is detailed in Appendix D Figure 10
nalysis of Routing Decisions. We further analyze the behavior routing decisions for instances of client that fall in the above three cases, global-only, personalized-only and both-correct. Figure shows the par-layer routing policies of the dynamic personalized model from Flow on Stackoverflow. For instances that fall into each category, average the policy value from Eq. [ and report the statistics on the probability of picking the global parameters for each layer. The statistics for the rest of the datasets detailed in Appendix D
For instances that are correctly classified by Wy but not by wp (global-only), we see a clear trend of the routing parameters getting more confident about picking the global parameters, As a contrast,
8

---

Valdatton Accuraccy tharsccyhhaaaattttaaaa altzed
Valdation Aotton/cccuaaccc (Plassnnalii
0.28
0.28
of verheete
of unituctt
0.29
0.25
Accuraee
0.28
0.24
Dynani Aautnn
valdalon
sp Ried 5.5
0.20
Plix iirentioonn Olox Requlatmat
Instinnc Elert Fo
0.22
Flend 5.50
250
1i 1250 yoar 1750 2000 Number Hourds
6.18
250
500 Ni 1003 1250 1688 2010
0.21
250
760 1000 1250 1502 1750 2000 Numbar Rounds
Ficed 223
Number of Rounds
(a) Ablation on the regularization
(b) Ablation on per-instance personalization design
(c) Ablation on dynamic routing
term
component
Figure 4: Ablation studies on Stackoverflow dataset.
for instances that are correctly classified by wp but not by Wy (personalized-only)) we see the trend of routing policy being more confident in picking the local parameters. For instances that can be correctly classified by both models (both-correct), the routing policy still prefers the global parameters over local parameters. This due to the regularization term Eq. which encourages instances to pick the global model over the local model in order to improve the generalizability of the global model. Our ablation study in the next section demonstrates the importance of regularization.
5.2
Ablation Studies
Here we highlight some results of three ablation studies on regularization, per-instance personalization, dynamic routing, and hard policies during inference. More results are in Appendix D
Regularization. The regularization term Eq. promotes the global model layers whenever possible. It helps boost the generalized performance of the global model, which in turn also produces better personalized models. We use the results on the Stackoverflow dataset in Figure Aegure/ajur 4a to illustrate the get 26.64% + 0.23% % generalized accuracy
importance of regularization. At the end of the training, with regularization, compared to 24.16% + 0.34% without regularization, and 29. 29.49% + 0.28% personalized accuracy with regularization, compared to 27.59% + 0.36% without regularization. The importance of regularization in the policy update rule is also highlighted in Theorem 4. which states that only picking local route does not lead global model convergence; the regularization term encourage the global model to converge faster.
Per-instance Personalization. The dynamic personalized model in Flow allows each instance to choose between the local model and global model layers. To verify this per-instance personaliza- tion design, create two variants of Flow, named "Per-Instance" Flow (PI-FLOW) where both paths of a dynamic model are global models, and "Per-Client" Flow (PC-FLoW) which is simply FEDAvGFT. Compared to the personalized accuracy of per instance and per client Flow (29.49% + 0.28%) PI- PI-FLOW and PC- FC-FLOW achieve 26.31% + 0.19% and 24.41% % + 0.26% respectively on Stackoverflow dataset, shown in Figure 4b The results demonstrate the effectiveness of the per-instance personalization design in Flow.
Dynamic Routing. This ablation study aims to learn whether dynamically interpolating global and local routes has any advantages over fixing the routing policy throughout the training. Figure 4c we compare the validation accuracy curves of dynamic routing in Flow and dynamic routing with instance-agnostic static routing during the training phase. We observe that (a) For the case of fixed policy of qo 0.25, the validation accuracy has bad performance due to the fixed policy only choosing the local route. This due to using hard policy during inference, and (b) The cases of fixed policy qo E [0.50, 0.75, 1.00] will only pick the global route during inference, which are also outperformed by the dynamic routing variant. With dynamic routing, the choice between local and global parameters depends on each instance during inference.
Soft versus Hard Decisions during Inference. We did not use soft decisions during inference since it only negligibly improves the accuracy of Flow. The test accuracies after personalization for Flow on Stackoverflow with hard decisions are 29.49% 0.28%, while with soft decisions, we observed 29.57% + 0.22%. The rest of the datasets show similar trend (see Appendix D Table 8).

---

6
Conclusion
This paper proposed Flow, a per-instance and per-client personalization method to address the statistical heterogeneity issue in Federated Learning. Flow is motivated by the observation that the personalized models from existing personalized approaches achieve lower accuracy a significant portion of clients compared to the global model. To overcome this limitation, Flow creates dynamic personalized models with a routing policy that allow instances on each client to choose between global and local parameters to improve clients' accuracy. We derived error bounds for global and personalized models of Flow, showing how the routing policy affects the rate of convergence. The theoretical analysis validates a local route based on the heterogeneity of individual instances. Extensive evaluation on both vision and language-basee based prediction tasks demonstrates the effectiveness of Flow in improving both the generalized and personalized accuracy.
empirical observations related to clients preferring either global or
Acknowledgments and Disclosure of Funding
This material is based upon work supported by the National Science Foundation under Grant No. 2312396, 2220211, and 2224054. Any opinions, findings, and conclusions recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. The work is also generously supported by Adobe Gift Fund.
References
[1] H. Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas. Federated learning of deep networks using model averaging. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2016.
[2] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 2020.
[3] Bing Luo, Wenli Xiao, Shiqiang Wang, Jianwei Huang, and Leandros Tassiulas. Tackling system and statistical heterogeneity for federated learning with adaptive client sampling. IEEE INFOCOM 2022 IEEE Conference on Computer Communications, 2022.
[4] Alysa Ziying Tan, Han Yu, Lizhen Cui, and Qiang Yang. Towards personalized federated lcarning. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[5] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized foderated learning with thcoretical guarantees: model-agnostic meta-learning approach. Advances Neural Information Processing Systems, 2020.
[6] Yuyang Deng. Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning. arXiv preprint 2003. 13461, 2020.
[7] Paul Pu Liang, Terrance Liu, Liu Ziyin, Ruslan Salakhutdinov, and Louis-Philippe Morency. Think locally, act globally: Federated learning with local and global representations. Advances Neural Information Processing Systems Workshop on Federated Learning, 2019.
[8] Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized federated learning. arXiv preprint 2102.07078, 2021.
[9] Krishna Pillutla, Kshitiz Malik, Abdelrahman Mohamed, Michael Rabbat, Maziar Sanjabi, and Lin Xiao. Federated learning with partial model personalization. arXiv preprint 2204.03809, 2022.
[10] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogencous networks. In Proceedings of Machine Learning and Systems, 2020.
[11] Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2021.
[12] Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personaliza- tion with applications to federated learning. arxiv preprint 2002.10619, 2020.
10

---

[13] Tian Li. Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. International Conference Machine Learning, 2021.
[14] Canh T. Dinh, Nguyen H. Tran, and Tuan Dung Nguyen. Personalized federated learning with moreau envelopes. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
[15] Jachoon Oh, SangMook Kim, and Se- YouYoung Yun. FedBABU: Toward enhanced representation for federated image classification. In International Conference on Learning Representations, 2022.
[16] Aviv Shamsian, Aviv Navon, Ethan Fetaya, and Gal Chechik. Personalized federated learning using hypernetworks. In Proceedings of the 38th International Conference on Machine Learning. 2021.
[17] Benyuan Sun, Hongxing Huo, Yi Yang, and Bo Bai. Partialfed: Cross-domate personalized federated learning via partial initialization. In Advances in Neural Information Processing Systems, 2021.
[18] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In Pruceed- ings of the 37th International Conference on Machine Learning, 2020.
[19] Othmane Marfoq, Giovanni Neglia, Laetitia Kameni, and Richard Vidal. Personalized federated learning through local memorization. International Conference on Machine Learning, 2022.
[20] Surat Teerapittayanon, Bradley McDanel, and H. T. Kung. Branchynet: Fast inference via early exiting from deep neural networks. arXiv preprint 7799016866 2017.
[21] Tolga Bolukbasi, Joseph Wang, Ofer Dekel, and Venkatesh Saligrama. Adaptive neural networks for efficient inference. In Proceedings of the 34th International Conference Machine Learning, 2017.
[22] Gao Huang, Danlu Chen, Tianhong Li, Felix Wu, Laurens van der Maaten, and Kilian Weinberger. Multi- scale dense networks for resource efficient image classification. In International Conference on Learning Representattinss, 2018
[23] Xin Wang, Fisher Yu, Yi-Yi Dou, Trevor Darrell, and Joseph E. Gonzalez. Skipnet: Learning dynamic routing in convolutional networks. In The European Conference on Computer Vision, 2018.
[24] Xin Dai, Xiangnan Kong, and Tian Guo. Epnet: Learning to exit with flexible multi branch network. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management. Association for Computing Machinery, 2020.
[25] Lanlan Liu and Jia Deng. Dynamic deep neural networks: Optimizing accuracy-efficieny trade-offs by selective execution. In Association for the Advancement of Artificial Intelligence, 2018.
[26] Minjoon Seo, Sewon Min, Ali Farhadi, and Hannaneh Hajishirzi. Neural speed reading via kiim-NNN. In International Conference on Learning Representations, 2018.
[27] Jian Xu, Xinyi Tong, and Shao-Lun Huang. Personalized federated learning with feature alignment and classifier collaboration. In The Eleventh International Conference on Learning Representations, 2023. URI
[28] Shanshan Wu, Tian Li, Zachary Charles, Yu Xiao, Ziyu Liu, Zheng Xu, and Virginia Smith. Motley: Benehmarking heterogeneity and personalization in federated learning, arXiv preprint 2206.09262. 2022.
[29] Blake E Woodworth, Kumar Kshitij Patel, and Nati Srehro. Minibatch vs local sgd for heterogencous distributed learning. In Advances in Neural Information Processing Systems, 2020.
[30] Stackoverflow. TensorFlow Federated Datasets, http://yyhoon//tt////mmaaat/////
tttp:/ofow..oooooroooooooooo.o.. http://wwwwomoooooooooo/o///ddee arggfeedratee//p.. 2023. [Online; accessed J9 2023].
[31] Shakespeare. TensorFlow Federated Datasets, https://www/ wwwp://wwwwwa//o. tensorflos ttrg/federated/app
docs/ sicss//ytthoo/tt////immaama http://aaaaainaaattt/tteeeeeeeee wawpaasstttsssaassserrreee 2023. [Online; accessed Jan
[32] Gregory Cohen, Saeed Afshar, Jonathan Tapson, and André van Schaik. Emnist: Extending mnist to handwritten letters. In 20/7 International Joint Conference on Neural Networks (ICNN), 2017.
[33] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images, 2009.
[34] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2016.
11

---

[35] Brendan McMahan. Eider Moore. Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--Efiiee Learning of Deep Networks from Decentralized Data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.
[36] Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Fedavg with fine tuning: Local updates lead to representation learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho. editors, Advances in Neural Information Processing Systems, 2022. URL htttttttt/pppereeeeeee
net/forum? Siciorrmmmii---a G3f sww.
[37] Daniel Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Titouan Parcollet, and Nicholas D Lane. Flower: 2020.
A friendly federated learning research framework. arXiv preprint
[38] Wenqi Wei, Ling Liu, Margaret Loper, Ka Ho Chow, Mehmet Emre Gursoy, Stacey Truex, and Yanzhao Wu. A framework for evaluating gradient leakage attacks in federated learning. arxiv preprint 2004.10397 2020.
[39] Xiao Jin, Pin- Yu Chen, Chia-Y Yi Hsu, Chia-Ma Mu Yu, and Tianyi Chen. Catastrophic data leakage in vertical federated learning. Advances in Neural Information Processing Systems, 2021.
[40] Wenqi Wei, Ling Liu, Yanzhao Wut, Gong Su, and Arun Iyengar. maddient-lcakage resilient federated learning. In IEEE 41 International Conference Distributed Computing Systems, 2021.
[41] Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In IEEE symposium on security and privacy, 2019.
[42] Hongsheng Hu, Zoran Salcie, Lichao Sun, Gillian Dobbie, and Xuyun Zhang. Source inference attacks in federated learning. In IEEE International Conference on Data Mining, 2021.
[43] Mohammad Naseri, Jamie Hayes, and Emiliano De Cristofaro. Toward robustness and privacy in federated learning: Experimenting with local and central differential privacy. Proceedings of the 29th Network and Distributed System Security Symposium, 2022.
[44] Kang Wei, Jun Li. Ming Ding, Chuan Ma. Howard Yang. Farhad Farokhi, Shi Jin, Tony Q S. Quek, and
H. Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security, 2020.
[45] Stackoverflow Dataset FedML. FedML Federated Stackovertlow Heterogenity 2ee.e222200222 wwwa:a/0000000eaaaaaaaaaaeeeeea.
https
//github.com/Fedd........... Attp:///eeaMAAA//ee////aaaaaa/ en/ en/s wwt.al/attoor//bbnocccma///////a
doc/
md. 2022. [Online; accessed 14 14-S22-
[46] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective incon- sistency problem in heterogencous federated optimization. Advances in neural information processing systems, 2020.
[47] Ellango Jothimurugesan, Kevin Hsich, Jianyu Wang. Gauri Joshi, and Phillip Gibbons. Federated learning under distributed concept drift. In NeurlPS 2022 Workshop on Distribution Shifts: Connecting Methods and Applications, 2022.
[48]
CIFAR100. TensorFlow Federated Datasets, httph: http:pp::/www.ttnooott www.oo/wwwo..ggggeeerateeeeaaaaa docs/ python/ httpm///tiitoeaaattatttt//////ee
2023. [Online; accessed 18-Jan-2023].
[49] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations, 2019.
[50] Xuanyi Dong and Yi Yang. Searching for robust neural architecture in four gpu hours. In Proceedings of the JEEF/CVF Conference on Computer Vision and Pattern Recognition, 2019.
12

---

A Limitations, Future Work, and Broader Impact
Learning on naturally heterogencous datasets can be challenging, as the true data distributions of individual clients are unknown, making it difficult to correlate the divergence between client data distribution and the global data distribution with routing policy decisions. In approach, we estimate the distribution divergence by measuring the difference between inference losses on global and local models, which helps us reason about routing probabilities for global and local routes. To further improve our understanding of the model performance, we plan to propose a metric that quantifies the difference in performance when particular dataset is included versus excluded.
Flow has shown the promise of per-instance personalization in improving clients' accuracy. This approach also holds the potential of preserving privacy by protecting against gradient leakage 38 and membership infer- ence 41 42 attacks that are easier to carry out vanilla FL. Studying the relationship hetween personalization and privacy, and comparing our approach to traditional methods like Differential Privacy (DP)
43 can
reveal properties of personalization that go beyond improved accuracy.
B Datasets and Hyperparameters
Stackoverflow The Stackoverflow dataset 30 is comprised of separate clients designated for training. validation, and testing. The dataset contains a total of 342,477 train clients, whose combined sample count equals 135,818,730. Similarly, the dataset contains 38,758 validation and 204,088 test clients, whose combined sample counts equal 16,491,230 and 16,586,035, respectively. This dataset naturally heterogeneous [ since each user of Stackoverflow represents client, with their posts forming the dataset for that client. The heterogeneity of the dataset arises from the fact that users have different writing styles, meaning the clients' datasets are not i.i.d., and the total number of posts from each user varies, leading to diffcrent dataset sizes per client.
We have trained Flow and its baselines on the Stackoverflow dataset for 2000 rounds. The one layer LSTM we have used has 96 as embedding dimension, 670 as hidden state size, and 20 as the maximum sequence length M. The batch size used for each client on each baseline is 16. The vocabulary of this language task limited 10K most frequent tokens. The default learning rate used 0.1. The number clients per round set to 10, as is the common practice in algorithms.
47
For client-side training, the default epoch count is 3 for all the
For KNNPER, we used 5 nearby neighbors, and the mixture parameter is À = 0.5. For APFL, mixture hyperparameter a is set to 0.25, DITTO has regularization hyperparameter À = 0.1. There are clusters by default for HYPCLUSTER. Flow and its variants were tested on the following choices of regularizing hyperparameters 7 E (1e-1, le-2, 1e-3, le-4), where 1e-3 gave the best personalized accuracy.
The Shakespeare dataset [1] consists of 715 distinct clients, each of which has its own training, validation, and test datasets. The combined training datasets of all clients contain a total of 12,854 instances, while the combined validation and test datasets contain 3,214 and 2,356 instances, respectively. The Shakespeare dataset is considered heterogeneous due to the fact that each client is play written by William Shakespeare, and these plays have varying settings and characters.
Shakespeare
All the baselines and Flow variants have heen run for 1500 rounds, with 10 clients per round. The 2 layer LSTM used [T] has as embedding size, vocabulary size 90 most frequently used characters. and 256 as hidden size. The default epoch count is 5 for each client, for each algorithm. The batch size is 4 since bigger batch sizes resulted in the divergence of the global model across all the different runs. The default learning rate is 0.1.
Since each client has sample count under 20, we have used 3 as the nearest neighbor sample count for KNNPER. À and o, the mixture parameters, for KNNPER and APFL respectively, are set to 0).45 and 0.3. The regularization parameter for DITTO set 0. For Flow, the learning rate set to 0.1 11 and the regularization parameter picked from y E 11c-1, 1c-2, 1e-3, le-4) similar to Stackoverflow.
The EMNIST datasct + comprises 3400 distinct elients, each which has its own training, validation, and test datascts. The combined total number of instances in the train datasets of all clients is 671, 1,555, whereas the validation and test datasets of all clients combined contain 77,483 instances cach. The heterogeneity of EMNIST clients is due to the individual writing styles of each client, with each client representing a single person. This is discussed in Appendix C.2 of [TT]
EMNIST
The default round count for all the baselines and Flow variants is 1500, with 10 clients participating per round. Similar to AFO [.]. we have used a shallow convolution neural network with convolution layers. Each client uses 3 local epochs for on devie training. The default batch size is 20, and the default learning rate is 0.01.
For LOCAL only training, we have used 10 epochs per client with a learning rate of 0.05. The nearest sample count for KNNPER is 10 and the mixture parameter is À = 0.4. For APFL, we have the default mixture parameter = 0.25. DITTO has regularization hyperparameter À O.L. There are clusters for the clustering
13

---

algorithm HYPCLUSTER. And for Flow, along with its variants, we have picked é (le-1, 1e-2, 1e-3, le-4) as the regularizing hyperparameter.
CIFARIO The CIFARIO dataset is derived from the centralized version of the CIFARIO dataset [33. which comprises 50,000 images. The federated CIFARIO 10 dataset consists of 500 unique clients, each of which has 100 training samples and 20 testing samples. The training and testing samples for each client determined according to the Dirichlet distribution
[1] The heterogeneity of a client is determined by the Dirichlet distribution parameter a E [0, 1), where a client is more heterogeneous than o + 0. In this context, heterogeneity refers to the dissimilarity of the dataset instances sampled from distribution. We conducted experiments clients with a values of 0.1 and 0.6.
We all the experiments for 4000 rounds for the CIFARIO dataset. ResNet18 [4 is used for all the algorithms. The default batch size is 20 and the default learning rate is 0.05. Each client individually trains their local versions of the global model for 3 epochs.
For LOCAL only training, 20 epochs per client were used. The learning rate was 0.1 for the same. The nearest sample count and the mixture hyperparameter for KNNPER are set to 5 and 0.5, PARTIALFED learning rate is set to 0. I, with the local epoch count is 5. APFL has mixture hyperparameter set 0.2. And DITTO has a regularization hyperparameter set À 0.01. Flow and its variants have their regularization hyperparameter y E (le-1, le-2, 1e-3, le-4).
CIFAR100 Like CIFARIO, the CIFARIO0 dataset [48] is derived from the CIFARI00 dataset 33 consisting of 50,000 images. The number of clients and the count of training and testing images are identical to those of CIFAR10. Similarly, we also conducted experiments with the Dirichlet parameter set to a = 0.1 and a = 0.6.
Similar to CI we have a 4000 round count for all the algorithms ran on the CIFAR100 dataset. We have again used ResNet18 8 (34] The default local epoch count is 3, and the default lcarning rate is 0.05. We have used 20 batch size for all the algorithms. For each round, 10 clients participate as is the norm stated in the Stackoverflow dataset description.
LOCAL only training has 20 epochs per client, and 0.1 learning rate. 5 nearest samples used for KNNPER, while the mixture parameter is set to 0.4. PARTIALFED, just like in CIFARIO, has 0.11 learning rate and local epochs per elient. APFL has 0.25 as mixture parameter a. DITTO has le-2 as regularization parameter A. For both CIFARIO and CIFAR 100, we have 2 as the default cluster count for HYPCLUSTER. Flow and its variants get (1e-1, 1e-2, 1e-3, le-4) as the regularization hyperparameter
C Computation, Communication, and Storage
While Flow introduces additional storage and computational overhead compared to the canonical method FEDAYG with Fine Tuning (called FEDAvGFT), compared other state-of-the-art personalization methods such as DITTO and APFI., Flow requires similar or even less storage and computational overhead.
To illustrate, Table compares
compares the storage, computational overhead, and communication cost for personalized models from Flow and baselines using the CNN for EMNIST, and RNN for Stackoverflow.
Referring to Table 4 for Flow. thy is the policy module. For our experiments on Flow, the policy module has 1.23% for Stackoverflow RNN, 8.39% for Shakespeare RNN, 27.86% for EMNIST CNN, 35.51% for CIFAR10/100 parameters of w,. For EMNIST CNN. for one epoch, the dynamic routing takes 0.3M FLOPs, while the rest of the model computations take 2.9M FLOPs. Hence the overhcad 10.34%. For Stackoverflow RNN one epoch, the dynamic routing takes 0.89M FLOPs, while the rest of the model computations take 12.34M FLOPs, making the overhead 7.21%.
Below, we highlight the computational and storage analysis on Stackoverflow dataset for the best performing methods. APFL, and HYPCLUSTER. The computational overhead is calculated for one epoch of training, which is then multiplied with however many epochs the baseline needs for convergence. APFL needs train two separate local models for more numbers of epochs than Flow, hence the higher computational overhead. In comparison with HYPCLUSTER, Flow introduces 7.23% % overhead. With respect to both APFL and HYPCLUSTER, Flow introduces only 1.23% storage overhead.
Moreover, from T we can see that compared to some other state of the personalization techniques (e.g.. FEDREP, APFL), Flow requires similar or even less computations, even with the dynamic routing operations.
14

---

Table 4: Computational and Communication costs, and Storage of Flow and its baselines.
A Local Storage of Personalized Model (unit: parameter count) for general case,
B Local Storage of Personalized Model (unit: parameter count) for Stackoverflow RNN case,
C' = Computational Overhead of Personalized Model of the RNN used for Stackoverflow (unit:
FLOPs for training),
D = Communication Cost (unit: parameter count) for general case, and
E Communication Cost (unit: parameter count) for Stackoverflow RNN case.
Baselines
FEDAYGFT
Wig
72.38M
Not Applicable
72.38
[ig
(Hinstances
M
72.38.M
Jintermediate representation
PARTIALFED
[wy] + 2+# layers of wy
72.38.M
36.9.M
72. 72.38.M
217.14M
73.8M
72.38.M
DITTO
2/10,
144.76M
36.9M
72.38.M
[gg
72.38.
00 (base)
70.98.M
LGPEDAYG
We
72.38.M
10.5M
(head)]
1.39M
HYPCLUSTER
Wgg
144.76M
36 36.9M
72.38M
FLOW (ours)
2/10g 14g1
145.651M
39.57M
73.271M
D Additional Results
D.1 Generalized and Personalized Accuracy
Generalized (Personalized) accuracy is calculated based on the global (personalized) model, where each participating client's test dataset is used to compute accuracy of the global (personalized) model.
Generalized accuracy is formulated
Σ Liaye 1yy wy (x)
Accg
1 M
Σ
(6)
Stest
mE(M]
Personalized accuracy is formulated as
Elaaeesw By wp. (2))
Accp
Σ
(7)
M
Stest
mE[M
We have reported Generalized (Personalized), Accuracy Ace, (Acc,) of Flow, averaged across 1000 clients in Table for all the datasets. Similarly, variance of accuracies across 3 different runs (based seeds 0, 44. 56) reported in Table The learning curves for both Generalized and Personalized accuracies for all datasets for Flow and its baselines are in Figures and
Table 5: Generalized (Accy) and Personalized (Acc,) accuracy (the higher, the better) for Flow and baselines. Variance across different runs is reported in Appendix D Table
Datasets
Stackoverllow
Shakespeare
EMNIST
(I.A
CIFARTON (0.1)
CIFARIO
CIFAR (O0 (0.6)
Baselines
Acc,, Acep
Apeg
Accp
Accy
Acep
Ace
Ace,
Acc
Acc,
Ace
Ane,
Aee
Ace
LOCAL
15.93%
18.70%
28.18%
62.74%
21.31%
FEDAVG
23.15%
52.00%
85. 10%
60.98%
28.11
67.50%
30.33%
FEDAYGFT
23.83%
24.41%
52.12%
53.68%
89.57%,
90.14%
19%.
31.15%
37.24%
KNNPER
23.16%
24.49%
51 3..87%
53, 10%
85.20%
88.28%
59.62%
75. 14%
28.08%
33.62%
69.22%
14%
30.66%
34.39%
PARTIALFED
62.57%
73.20%
34.79%
40.64%
66.93%
70.38%
37.72%
40.18%
APFL.
22.96%
25.70%
52.38%
53.64%
88.40%
89.44%
62.87%
72.86%
31.05%
32.56%
69.53%
72.53%
36.37%
36.74%
DITTO
22.59%
34%
52.44%
53.95%
89.08%
01 30%
62.00 62.06%
72.00 06%
28, 14%
35.45%
68. 12% 70.31%
35.11%
36.07%
FEDREP
21.04%
33.72%
LGFEDAvG
22.61%
24.03%
51 081%
51 43%.
87.43%
91.70%
56.63%
19%
31.65%
39.63%
67.48%
68. 94%
35.01%
33.90%
HYPCLUSTER
23.75%
22.43%
52.74 72.7
89.
90.49%
33.04%
34.76%
36.22%
Flow (Ours)
26.64 29.49%
55.90%
56.20%
90.88% % 94.18%
66.26 %
76.47% %
34.00%
42.42%
70.88%
77.11 1
39.70% 40.08%
Flow sees an improvement of 1.11-3.46% in Acc, and 1.33-4.58% in Accp over the best performing baseline. Besides the main observations listed in Section [5] we discuss results the CIFAR 100 dataset here. For CIFAR (0.6), Flow (40.08% 0.27%) matches the personalized accuracy of the highest performing baseline, PARTIALFED (40.18% 0.19%), while achieving 1.98% point increase generalized accuracy. And for CIFARIO0 (0.1), Flow improves personalized accuracy by 1.78% points. For generalized accuracy, Flow (34.00% = 0.32%) reaches close to the best performing baseline, PARTIALFED (34.79% + 0.29%). The reason attributed the statefulness of PARTIALFED.
behind the on- par performance of Flow with PARTIALFED
15

---

Table 6: Variance of generalized and personalized accuracies across 3 different runs (seeds 0, 44. 56) for Flow and its baselines.
Datasets
SOWWP
Shakespeare
EMNIST
CIFARIO (0.1)
CIFARIOO (0.1)
CIFARIO (0.6)
CIFARIOU (0.6)
Baselines
Accg
Accp
Accg
Acty
Aoca
Aocp
Aoeg
Accp
Acca
Actp
Accg
Accp
Acca
Actp
LOCAL
0.25%
0.46%
1.14%
1.56%
0.43%
0.89%
0,25%
FEDAVO
0.07%
0.39%
1.12%
0.31%
0.15%
PEDAYGFT
0.09%
0.26%
0.51%
0.59%
1.16%
1.21%
0.99%
0.89%
0.46%
0.62%
1.10%
1.26%
0.33%
0.42%
KNNPER
0.16%
0.24%
0.36%
0.41%
0.95%
1.02%
1.41%
1.57%
0.34%
0.57%
0.91%
1.06%
0.24%
0.29%
PARTIALFED
1.36%
1.39%
0.29%
0.46%
0.966%
1.97%
0.09%
0.19%
APEL
0.19%
0.20%
0.41%
0.53%
1.41%
1.50%
1.24%
1.31%
0.36%
0.72%
0.70%
0.97%
0.42%
0.59%
DITTO
0.12%
1.1%%
0.49%
0.56%
1.12%
1.22%%
1.35%
1.41%
0.43%
0.69%
0.84%
0.87%
0.28%
0.34%
FEDREP
0.15%
0.29%
0.50%
0.65%
0.89%
0.94%
0.95%
1.02%
0.59%
0.79%
0.964
1.14%
0.14%
0.10%
LGFEDAYO
0.08%
0.16%
0.56%
1.10%
1.17%
1.21%%
1.24%
0.47%
0,51%
0.82%
0.96%
0.23%
0.21%
HYPCLUSTER
0,20%
0.19%
0.56%
0.73%
0.90%
1.13%
1.43%
1.49%
0.39%
0.47%
0.98%
0.76%
0.35%
0,46%
Flow
0.23%
0.28%
0.40%
0.49%
1.16%
1.21%
1.23%
1.25%
0.32%
0.36%
0.78%
0.86%
0.21%
0.27%
Validation Accuracy (Generatadd)
Valldationn Accuracy (Generaiized)
Vwirdetion Accumery (Camerlizee)
0.55
0.80
0.6-
0.83
0.5
0.8-
0.40
0.75
Fechup
Partialeed
0.70
LGFodlogg
Feshig
Festive
0.35
Hyocluser
Hyschuserr
AFTL
LSSeekog
Ditto
HysCluater
0.30
kerPer
0.1
1400
203
2000 1500 3030 Number Rounds
Number Rounds
Number Rounds
(a) Shakespeare
(b) EMNIST
(c) CIFARIO (0.1)
VAlidation Accunary (Caneralizee)
0.7
Callsttonn Acorasy (Scherltedd)
0.35
Validattin Accuracc (Sendralizd))
0.6
0:30
0.25
8.25
0.30
5,20
Fedlig APPL 0.3
2.4
Fodlug
0.15
Fedfag
Fedifeg
Fediep
Partaafee
Fedfup
FedRep
Parta
LGFadAug
APPL 2.00
LoHcokog
APPL 0:15
LoPezAkg
Data
Hypplusde
DiZU
HypChaster
Ditt:
Hypclustrr
500
1000 1500 2009 2500 3000 3500 4000 Number of Rounds
knnhwe
flww
5.05
505
1000 2500 2020 2000 3000 3500 4000
knnter
Flom
0.10
550 1000 1500 2000 2550 a0to 3503 1000 Number or of Rounds
Flom
Number of Rounds
(d) CIFAR 10 (0.6)
(e) CIFARI00 (0.1)
(1 CIFARIOO (0.6)
Validation Accuraay (Gencallted)
2.29
0.35
HypCllster
InnPer
250
Number Rounds
(g) Stackoverflow
Figure 5: Learning curves on Generalized Accuracy Metric of Flow and its baselines.
With the assumption of full device participation, PARTIALFED makes use of each client's previous state of the personalized model to further train its layer-wise model building policy. With Flow, both the assumptions of full device participation and statefulness of the personalized model not necessarily have to earry their personalized model states to upcoming rounds, the personalized model recreated by Flow might be unable to compete against stateful approaches like PARTIALFED. Although because of the per- per-instance routing, Flow still manages to outperform PARTIALFED for the CIFARIO (0.1/0.6) datasets, and gives comparable performance for the CIFARI00 (/.16 datasets.
necessary. Since the clients do
16

---

Valdadton (Poreenattoo
0.9-
6.775
0.50-
8.725
0,703
0.40
RoSANg FT
Feciees (GFediig HycClueer
FedAng
FodRop LoFe HypClunter
APRL
GGFedkug CynCuder
0.35
APR.
Dihn
APRL Dito 28D
Validatten
0.690
DETe knnter Portiited
Fixx
knnneer
Flow
0.823
200
430
600
502
1005
1200 1400
400
60n nbn
1000
1230 1400
502 2000 1300 2010 2002 5000 4000
Number of Rounds
Number of Rounds
No mber of Rounds
(a) Shakespeare
(b) EMNIST
(c) CIFARIO (0.1)
Velidton Accurayy (heronaleee)
Validaation (Pursonalizd))
0.425
0.70
0.65
0.30
0.60
0.325
0.55
Fediug FT
APPL
Dio
FodRep
HypCluster
LGFed/wg
0.300
0.255
Fechug
APP:
LGGedius
MypChsstrr
0.5
krnForr
Flow
0.200
Part aFod
500 1500 2000 2500 2000 3500 4000
2520 2010 Number Rounds
Number of Rounds
Number Rounds
(d) CIFAR 10 (0.6)
(e) CIFARI00 (0.1)
(1 CIFARIOO (0.6)
Valdaciion Accuracy Rocuracy//Cnrraaiiaccoo (Generaltzdd
0.25
0.00
0.25
500
(g) Stackoverflow
Figure 6: Learning curves on Personalized Accuracy Metric of Flow and its baselines.
D.2 Effeeciveness of the Alternative Training of the Global Model
experimented three modes training for global model: (a) Global model trained first, then policy module, (b) Policy module trained first, then the global model, (c) Global model and Policy module trained alternatively. The results are shown in Figure 7 We see that the alternate training results in more stable training compared to the other modes of training. These results are in conformance with other works which have also used alternative training for policy and model weights training.
49
50
D.3 Dataset Split
We experimented with the Stackoverflow Next Word Prediction task initial rounds for the local and global training dataset splits. The plot is shown in Figure We observe that for the dataset split size of 0.75:0.25 for local and global datasets respectively, the global model does not get sufficient samples converge, resulting in worse personalized model performance since the personalized model based on the global model. While a split of 0.25:0.75 75 for local and global datasets has closer performance to that of a 0.50:0.50 split, lesser data (and hence fewer iterations) to the local model leads to local model weights heing similar to that of global model, diminishing the impact of personalization.
D.4 More Seeds
We have re-run Stackoverflow experiment with seeds in 6, 6, 8, 9), the results show material difference. See Figure
17

---

Vallodtion Accuaccy (Senoralzoo
0.50
0.32
Ke.d 10.d-3100
0.32
0.30
6:65
K..d-jaal
0.28
Ke.d - Plaal
6,80
Vallcation Arc m3
0.24
0.75
0.72
0.72
0.70
0.20
0.20
Gobal Mode fint
0.38
0.05
Policy Mazute first
Atammane
#60
1450
0.14
Number of Rounds
Number of Rounds
Number Rounds
Figure 7: Results for different modes of training for EMNIST
Figure Earlier stages of Stackoverflow NWP training with different local:global dataset splits
Figure Stackoverflow NWP training with seed choices of
[1.9]
D.5 Percentage of Clients Benefiting from Personalization
In this section discuss the effect of personalization. comparing each client's performance their individual personalized models with their performance on global model. The evaluation, just as in section [.] done on the test datasets of all the clients. The goal with any personalization method is to make each client's personalized model more beneficial (for us, in terms of accuracy) compared to the global model. Hence we want Accp > Accg, to incentivize personalization for cach client, As shown in Table compared the best performing baseline, Flow improves the utility of personalization by up to 3.31% points.
Table 7: % of clients for which Accp > Accg (the higher, the better).
Stackoverllow
EMNIST
Slakespeare
CIFARIO (0.1)
CIFARIOD (0.1)
CIFARIO (0.6)
CIFARTOO (0.6)
PEDAYGIT
79.26% 82.73%
81.48%
79.00% 68.87%
97.18%
91. 74%
99.33%
88.54%
KNNPER
94.71%
PARTIALFED
88.30%
90.32%
84. 64.80%
98.64%
APEL
69.66%
93.34%
79.22%
37.48%
86.18%
90.63'5
92.03%
DITTO
74.59%
79.26%
73.74%
90.52%
91.45%
89.61%
97.45%
FEDREP
91.53%
82.20%
79.78%
92.30%
78.81
84.64%
99.54%
LGFEDAVG
83.47%
HYPCLUSTER
80.46%
80.70%
74.84%
95.1 11%
93.70%
98. 18%
99.73%
Flow (Ours)
92.74%
96.70%
%
98.33%
97.29 %
99.62%
99.75%
D.6
Breakdown of Correctly Classified Instances
Here we show detailed view how instances (across clients) get classified correctly between global and personalized models for each the baselines. For the plots in Figures y-axis represent of instances correctly classified by (a) Both the global and the personalized models (both-correct), model (global-only), and (c) Only the personalized model (personalized-only)) This % of instances metric is averaged across all clients, and is based on their test datasets. The goal here is increase the % of instances for both-correct and personalized-onn
(b) Only the global
reduce the of instances for global-only. We make following observations for each of the datasets: Since Flow improves both the generalized and personalized accuracies, we see higher both-correct for Stackoverflow (by 2.75% points), Shakespeare (by 4.34% points), EMNIST (by 3.17% points), CIFARIO (0.1) (by 5.24% points), CIFARIO (0.6) (by 0.03% points), CIFAR100 (0.1) (by 0.63% points) and CIFARIOO (0.6) (by 2.78% points).
Due per ver-instace personalization, we see improvements personalized accuracy, those improvements are also included the both-correct bars, so solely comparing personalized-onle har lengths not right comparison. Similarly, we see fewer instances in global-only bars due to the increase in instances which fall under both-correct.
D.7
A nalysss of Routing Decisions
Now show probability value analysis of the routing policy for CIFAR10/100 datasets. Here we have fixed the client the client which had the highest loss difference between its global and personalized models for Flow. This analysis was done during the inference stage, on test dataset of above-mentiones client. The box plots show statistics on the probability of picking the global route for all the instances. Echoing the observations made in Section 5 in Figure I] we see trend in increasing probability for the global parameters for the instances which correctly classified by only the global model. In the contrary, for the instances which
18

---

gazsi-onyy
goosl-ony
0.6
0.5
0.
0.7
04
0.6
0.6
05
0.3
0.4
Dato
Feut
Hpprhuuter Flom
Tedtwg FT
APP
Datt
Fedtfop
Hypthatte
Flow
Resber AiY
Deta
Aoxe
Partasiid
PicPf ap
Laredtug
loycluree
Flas
Baseines
Shakespeare
EMNIST
CIFARIO (0.1)
af Iestunces
0.3
0.5
0.4
% of
02
0.3
0.2
0.2
0.1
Portattel
restup
Lanesoop
Hypclaster
Feddop FT
4rP
Dita
hartelred
Festae
Lateslog
flow
APP
knothe
Partior
reotfer
Lafestog
rediig
reddop
Baseines
Basefnes
Baseines
(d) CIFAR 10 (0.6)
CIFARIOO (0.1)
(1) CIFARI00 (0.6)
Figure 10: Different combinations of Wy and up accuracies.
only be classified by the personalized model, the probahility for taking the global route lower the input passes through more layers.
D.8 Ablation Study: Regularization
Figures 12 and 13 show the validation curves for generalized and personalized accuracy with and without the regularization term used in the policy learning objective shown in Equation 4 With regularization, an improvement
(Stackoverflow). 1.86% (Shakespeare), 3.98% (EMNIST), 2.55% (CIFARIO 0.1), 4.36% (CIFAR10 0.6), 0.91 % (CIFARION 100 0. 3.46% (CIFAR 100 0.6) for the generalized accuracy. And for the personalized accuracy, we see an improvement of 1.92% (Stackoverflow)) 2.02% (Shakespeare), 3.01% % (EMNIST), 0.65% (CIFARIO 0.1), 3.98% (CIFARIO 0.6), 2.42% (CIFARIO0 0.1), 2.19% (CIFARI00 0.6).
D.9 Ablation Study: Per-instance Personalization
Figure 14 show the validation curves for 3 Flow variants: (a) Per-instance Per-client Flow, which the primary design proposed in this work, (b) Per-instance Flow, which makes choices between two global routes solely based each client's instances, (c) Per-client Flow, which is simply FEDAvGFT where the personalization only depends on a client, and not on any specific instances.
With the datasets, we see trend of Per-instance Flow outperforming Per-client Flow by 1.88% (Stack- overflow), 0.82% (Shakespeare), 5.07% (EMNIST), 2.90% (CIFAR10 0.1), 2.41% % (CIFARI0 0.6), 7.52% (CIFAR100 0.1), 1.09% (CIFAR 100 0.6). We also see the trend of Per-instance Flow outperforming Per- Per-Client Flow by 3. 3.19% (Stackoverflow)) 1. 1.24% (Shakespeare), 0,94% (EMNIST), 0.55% (CIFARIO 0.1), 4.49% (CIFAR 0.6), 3.88% (CIFAR100 0.1), 1.37% (CIFAR100 0.6).
D.10
Ablation Study: Soft versus Hard Policy
Table X shows the personalized accuracy of the test clients while using soft and hard policies during inference. We that the accuracy difference between the two designs statistically insignificant. Hence, using hard
19

---

both-currect
global-only
personaliced--nnly
both-careet
global-enly
persondlized-only
(Probabll Iky of picking the global route)
1.0
0.8-
(Probabilitt of picking global
0.8
0.6
0.4-
0.4-
0.2
0.0
2
Layer indices
Layer indices
CIFARIO (0.1)
(b) CIFAR (0.6)
both-correct
global-anly
personallzadd.on) only
both-corract
global-only
personalized-oe only
(Probability of picking the global route)
1.0
(Probability of picking the global route)
0.9
0.0
0.6
0.6
0.4
0.5-
0.4
0.2
0.3
Layer indices
Layer indices
(c) CIFAR100 (0.1)
(d) CIFAR100 (0.6)
Figure 11: Behavior of th for all instances with respect to each layer of a client with highest loss difference between personalized and global models.
policy for inference not only saves half the compute resources, but also doesn't 't affect the personalized model's performance.
D.11 Ablation Study: Dynamic Routing
The accuracy curves are given in Figure 15 The curves show that the phenomena of "dynamic probabilities based each instance works consistently better than the fixed probabilities for all the clients throughout the training" is indeed observable across datasets. intuition hehind discussed in Section 5.2 under "Dynamic Routing".
Table 8: Test (personalized) accuracy of two of the Flow variants: (a) Soft Policy variant where the probability q is continuous in the range of [0, during inference. (b) Hard Policy variant where the probability q is discrete over the set [0,1) during inference.
Datasets
Stackoverflow
Shakespeare
EMNIST
Soft Policy
29.57%
0.22% 57.01% 0.53% 94.97% 1.06%
Hard Policy
29.49% = 0.28% 56.20% + 0.49% 94.18% + 1.21%
Datasets
CIFAR 10 (0.1) CIFAR 100 (0.1) CIFAR 10 (0.6) CIFAR 100 (0.6)
Soft Policy
77.24% 1.30% 42.75% + 0.30% 77.02% + 0.90% 39.74% 0.13%
Hard Policy
76.47% + 1.25%
42.42% + 0.36%
77.11% + 0.86% 40.08% + 0.27%
20

---

Valtaatten AccurFScy (Sanarsiite))
0.56
M Mamaimo
0.61
Valisattnn Accaracc
0.2
of
Vallsatten Accurary
0.422
0.70
0.60
0.00
0.59
0.8
0.00
0.55
whheot Reguaromtion
0.54
Olin withor Requlartmaion
460
cóo sóo 186o 1252 1n50
260
600
cón
séo
ta5o
1292 1660
1002 1550 200e 2000 1500 endo Number Roards
Number Rounds
Namber of Rounds
(a) Shakespeare
(b) EMNIST
(c) CIFARIO (0.1)
Valdasion (Senoratzod)
0.70
Veltterto Aecuraccy (Greeraazzed)
2:34
Valdation Accuracy/Gaaarraaaaoooa
0.50
0.090
0.55
0:30
et
6.25
1:28
0.20
Thon with Regulemaaiion Tlow whncot Reguanization
Sugu Row WITHAUE Regutarann tortationn
Plan Regubrttation Flin withou Regutarizat
0.45
+
560
1003 1500 2010 2503 3000 2510 4003 Number Rounds
500 1000 1500 2005 2503 5920 3500 4200
2002 1500 abto 2000 1500 4950 Number Rounds
Number of Rounds
(d) CIFAR 10 (0.6)
(c) CIFARI00 (0.1)
(f) CIFARTO0 (0.6)
validation ACCU/DSY (Guneralizad)
0.27
0.26
0.23
0.70
withor Regularmmto
250
560
1000 1250 1500 1750 2000 Namber of Rounds
150
(g) Stackoverflow
Figure 12: Generalized accuracy of the ablation study the regularization term used in the policy learning objective.
21

---

Vallbotonn Acouraco (Personliizee
Valddrdon Accurayy (PcurcyyPaersrsaaa (Personalaad
0.3
0.79
0.76
Valdatton ACCUROO
0.52
0.54
PPow
0.8
fitee.
6.77
0.71
0.7
0.70
0.69
0.8
Fex with Regularical
Reguistcttoon
0.65
Thxx with Eug Segulartsttonn Hii without Regubvizzt or
Fiew wlthout hoguiar calkn
wthnut Segularteation
0.61
200
400
500
1920 1200 1400
200
400
eúc
soo
1000
1200 1400
500
1002
1500 2010 2300 2003 2500 4000
(a) Shakespeare
(b) EMNIST
(c) CIFARIO (0.1)
Valdaton Accuracy (Prnsonaza)))
0300
W
Velinastor Accuracy (Pwnamelzznt)
2.42
Valcudion (Pansuaal
6,42
0.725
0.42
0815
0.42
0.20
Reguearizaiion
0.35
Reguiartent
2500
1002
1560 2010
e050
Number of Rounds
Number of Rounds
Number Rounds
(d) CIFAR 10 (0.6)
(c) CIFARIOO (0.1)
(1 CIFARIO0 (0.6)
PaldaionAccaaa (PNrsorrtttdd
Number Rounds
(g) Stackoverflow
Figure 13: Personalized accuracy of the ablation study on the regularization term used the policy
learning objective.
22

---

Valcazion (P
0.5
validatton (Parsonstood)
Anm
0.56
0.0
0.54
0.76
0.52
0.72
0.70
Pastslanke harckert FoM
Petirstanee horckert
0.05
Fee Instonce Panci Panciient Flox
0.48
Pand end Flo
Posirslakee How
Metirstanke Him
0.60
For insiumne Flow
1600
200
1860
1500
(a) Shakespeare
(b) EMNIST
(c) CIFARIO (0.1)
Voldarknn AcCUrazy (ww.ss/ooaaaaaaaao
0.90
Valitadon WolidutannAcccuuu Accuraszyy (Pertona
0.48
instance Perdd ann Man Fer Inctinee Fiex
Valduddk Valddutkn.Acccumm Accurazy (Persoraaaaaa
0.40
0.75
TTow Metiine
horickort
0.35
0.70
0.65
For indiance Perdior How
For insiamma Perid lnn How Fee Peetenetnce Flok
Fee tretennnce Flox clert Fo
0.32
0.35
corrt FOo
500 1002 1500 2020 2300 2002 2500 4000
500
1002
1910
2000
2000
2007
2500 4000
500 1002
1500 2020 2300 2003 2500 4000
(d) CIFAR 10 (0.6)
CIFARIOO (0.1)
(1 CIFARIO0 (0.6)
Validation Accurssy (Puugonallbod)
0.29
0.29
0.20
instance Frow
flox
0.18
Per chent Few 250
500
150 2003 1250 1592 1750 2010 Namber Rourds
(g) Stackoverflow
Figure 14: Ablation of the dynamic routing component (Per-client Flow), and the local component (Per-instance Flow).
23

---

Vallaatton AccuISSC (Papsonatzee)
Valtdation Accuraay (Pursenalized)
Valisation AccuRSI (1a.ura
0.80
0.50
0.49
0.75
0.75
0.40
1.00
0.70
faad
Floed 2.50
Fand du 0.76
0.6
Fand 0u 0.75
Flced 2:73
0.5
Fand 0.50
Tand 6.5
0.00
Tand 0.25
Fand
0.45
Fleed to 3.50
Flled ty 325
200
660
660
1020
1202 1650
260
460
sén
1960
1902 1920
550
1002 1500 2020 7100 3003 1500 <000
Numbe Bounds
Numbbrr Rounds
Number Rourds
(a) Shakespeare
(b) EMNIST
(c) CIFARIO
Accuracy (Pazonalizd)
VMldeeter Acconett www.ry/hheeeleeee
0:42
0.40
0.75
5:35
Dynutri: had cy
Dynanis Rastin
0.70
Dynam r Routin
0:23
cy
Valcaston Accurary
0.25
0.30
Fliedd ty 2:50 Flced qp 3.75
Foot op = 1.00
Fleci o 075
Foled da 055
5.15
0.15
Faeed au 025
0.22
500 1003 1500 2000 2503 3000 3500 4003
500
1900
2005 2503 3020 3500 5000 Number Rounds
1500
1002 15t0 201o 2500 3003 3500 4006 550
Number Rounds
Number Rounds
(d) CIFAR 10 (0.6)
(c) CIFAR100 (0.1)
(f) CIFARTOO (0.6)
Vallaatinn Accuracy (Nersialiiza
TToe varherte
0.26
0.25
Dynanii
0.22
0.21
H50 1000 1250 1995 1750 201o Number of Rounds
(g) Stackoverflow
Figure 15: Personalized Accuracy of the Ablation Study the Dynamic Routing Component.
24

---

E
Proofs
E.1
Flow: Detailed
Here give detailed version of Flow (Algorithm 2 for proving its convergence properties. Here assuming that the global and local model output interpolation model-wise (after the final layer), not layer-wise.
Algorithm 2:
Flow
Input: R: Total number of rounds, r E [Ad]: Round index, M: Total number of clients, m [M Client index, M: Set of available clients, p: Client sampling rate, K: Total local epoch count, E [K]: Epoch index, T) Local learning rate, (r); Global model at th round, wgmm: m client's local update of the global model for th round and k epoch, w m th client's local model for A round and k epoch, wpthh) mhth client's personalized model for th round and 4 epoch, wi!") Global policy model at th round, va.m m client's routing policy for 7hhh round and kth epoch, Dm: Data distribution of th client, Sm: Dataset of m th client, Sm.e? Dataset used to train wy,
<m.g: Dataset used to train Wy and Wig
(R+1), Global model at the end of the training Output: Wy
Server randomly initializes wig (1)
for E [R] round do
Sample M clients from .M with the rate of p
Send u 3/6+)) to all the clients
for m E [M]] in parallel do
(r.0) -wyy (r) (7.0) +- w(rr; (r.0) + wg..
(r.0)
L.m
Sm.ei Sm.g Sm Creating two mutually exclusive datasets for E [K1] epochs do
(r.8) + wimm
(r,k-1) ne fm (ntrtt" (m.e))
end
I1
for
E [K2] epocks
12
V (am,8m)) ~ Sm.g. define
(rok- (rrkk-)) (o.nk-((ara)) (I:m) &- tg.
(r.k--1) (xm)) (r.k-1) (am) + (1
(r.k-1) (Imm) )) wo (Im)
Wpmm
(rih) +- (1) neV f.a.
fm (1iptih (nk-1)) (mm))
13
14
V (Emi Hmm) ~ Sm.g. define
(rik-1) (Im) (2 t- g. (Im) wg..
(r.k-)) (3em) ) + (1 (itthh) (20m) (r( (2m) (20m)
(r.8) (r,k-1)
V (r--1) fm (now (rrk-),, Sm..)
ug.m +- u.g.m
16
end
(r,K) Send back wg.m vorm nm = 1mm.p
17
18
end
19
nsI Emejar Nen w.mm Eme(M)) Nom g.m.
(T,K)
(++1)
end
E.2 Basics
We perform thcoretic analysis of Flow based on the following sctup: There are total M clients, A client is denoted by a unique integer m associated with where m E [M]. Each client mn has a dataset Sm {(=m ym ); e
[mm]]] where (# (t) has been sampled from D., distribution of the m th client. vt = S.m. is the total sample count of the th client. Total sample count across all the participating client
Emejaj Tom. The
ratio of th client's sample count to total sample count a
The global distribution is defined as D EmE[M] 4m D.n where qm is the weight associated with mht client and Emejy MM 9m
25

---

Note that My.m is combination of outputs of g. (Global parameters) and w (Local parameters) on each layer. For tractability of analysis, will assume that the combination is only after the last layer. Hence.
Wp (Fm) &- Vo (Wm)WWg, (Fmm) + (1 Vgg. m (2m) ue
The local model update rule is.
(nik) (rk-1) t.m
TE V ( (2000-1((m)) ymm)
wmm
where wm.. wg.n The policy update rule is,
(r,0) w
Indices r E [Tc] and is E [K] are the global round and the local epoch indices.
(m.)) tg.m 9.m
(brck-1) 176 fm fm( (w (Irm) ymm)
The global model update rule is,
w (rik)
w
(rik-1) g,m
T) V Fm Fm (2 ymn.
g.mn
We out all the optimization problems relevant Flow:
Local true risk of the personalized model
F' (Wy.m) := E( tim ~ DDn) [Imm (pp.((mm) vm)]
where fm is loss function associated with the m client.
Local empirical risk of the personalized model
Fm (wp.p)
Σ
fm (arli)) ) v
1h vE(Am]
Local true risk global model
Fm (Wg..) == Ex Nm Lm (Mig.m (1m), Mm]]
Local empirical risk of the global model
F (10.m))
Σ
fm (Ir v
Thm vE(Am)
Local minimizer of local empirical risk of the personalized model
Wpmm such that For (wp...) 2 Fin (wp.m); Wup.o E H. Be O, 1ppm 2pmm <E
Global true risk of the global model
F(w,) n.M
Σ
Tbm E (m S-S 1m (weg) (Iim), Mm where n1 |S| =1=11 U Smi
mE[M
mE(M]]
Global empirical risk the global model
F(w,) n.M ME[M]
1
Σ Fm (W. (Tm). Mm) nM
Σ
Σ
fm (W (5r y,
ME[M] xE(mm)
Local minimizer global empirical risk
Wy E H such that F(w,) 2 P(w)): Ve, E H. 3e > 0, 1| will <
We also use following assumptions similar to 18 Assumption E.1 (Strong Convexity). fr is p-convex for μ 2 0. Hence,
V (w), w) S (m) (w) w m11 Vm E [M] and w. E H.
We also generalize convergence analysis for general convex cases.
Assumption E.2 (Smoothness). The gradient of fm is g-Lipschitz
[/ (mm(v)] & l w/l. Vm [M] and w, v H.
26

---

Assumption E.3 (Bounded Local Variance), (m)(w) == Vfn (1)() Mm)) is unbiased stochastic gradient of Jm with variance bounded oz.
(zmm Dim (w)) (m bmlll I oř, Vm [M] and w H.
Assumption E.4 ((G, B)- B3-Bounded Gradient Dissimilarity.. There exists constants G 0 and B 2 such that
(w). S G 2x0) mE|M]
Σ
M
for a convex fm. And for a non-convex fms
Σ [V5m(m)) s B1IIVF(w)1)
M
MEIM
The derivation is given in Section D.I of Scaffold [8]
We also use a definition to quantify the diversity of a client's gradient with respect to the global gradient as defined in 29]]:
Definition E.5 (Gradient Diversity). The difference between gradients of the m client's true risk and the global true risk based on the global model w is,
8m sup [m VF(w))
WER
E,3
Convergence Proof for the Global Model: Convex (Strong and General) Cases
client's 's local update for one local epoch on the global model, starting with wg.m +- wg
g.m
frr +++1
w
a.m
(r.K) nehm (
(1 (r.k) ).
(8)
And client's local update for epochs on the global model, would be
W..
(r.K)
(miD)
Nmm (w(kk-1)))
(9)
(r.D)
g:me
me
hmm tm
(1blos)) (I juy. (r,k-1) (m)) + +11
(g(n))) sime (cm) Deo (m. (Im) Mm))
(10)
In both the above cases, the gradient is with respect to my parameters. The global model update is,
Tbm W g.m
(II)
n
ME(M)
(r.K) We first start with a lemma which binds deviation between the local model w and the global model starting point w/") for at round
Lemma E.6 (Local model progress). Im client's objective function f'm satisfies Assumptions E.2
E.3 and
condition ne S 1²2 Algorithm the following satisfied:
E
(nJ)
(r:0) Wi,
1|? < 6K2 / (11 3Kn2ot
Proof.
[w0 2.m
(r.K)
(r,K-1)
V fu (1)( (r:0)
(12)
K
El
2.m.
20 112 Knj (m (w
+
12
(13)
27

---

Here we have used triangle inequality and variance separation.
+ K- E|| El
(ook 1]
( Kn B fm (10/ 10 + no:0?
(14)
+
Bllugmm
w (r.00) 11 + or
K
+ Knt
E
fm (w) C.
1))
Vm fm + fm (w (mm ||2
(15)
+
1
El| Em
(nk-1)
w
(100) 1 2K 17 B V (wff (1) V fm ) )1
K K-1
+ 2k E.|
V fi (1))))
n/a
(16)
1 K -
1
El
1 (r.K-1) - wp 1? + 2K 22 (l
(r,K-1)
+ +2Km V (w (1 ||( + n²o
(17)
Assuming N1 122X(K-1) get
Bllwg, wi,
(r.k)
(n:0) S 1 2 Em 10lo//.---1
2K +2 V ( A11 + =z07
(18)
Unrolling the above recursion.
K Σ
B Wim
wimm
(0-1))
112
2K Fm (w0 )1² nēoo2)
1 K --11
(19)
1=1
S 33
( )1 12002)
(20)
V fm V
(w (r0
3Km20?
(21)
Now we move forward to a lemma which binds the deviation between the local version the global model (rA)
Wg.m and the global model starting point w!?' for round r.
Lemma E.7 (Local version of the global model progress), If mhth client's objective function fm satisfies
Assumptions
E.1
E.2
E.3
and condition me S 3/2x in Algorithmm
2
the following is satisfied:
E
(+:00) 8 El
|| Fm (w,) \1 + 4kTi o
Prouf. We start by expanding wg.m in terms of its previous epoch iterate.
Ellw, i f0 112 El f
(n,k-1) ne V (n 13 fm (7th (onkk-11)) - (r.0) 1|a
(22)
wa.m
Using triangle inequality and separation of variance, get.
(1) - Ell (r.--1) Elluo wir000 + kntllly (1.4-1) fm (w 1112 + 7z007
(23)
Using the convex property of fm, we get
+
El Elluffth-))
(r.00) 11 knj Ellyy (1.0)) V Im (w 2)) )12 ni
(24)
k
El Bllogtth
(1000) 1|a + niē oz
+
k
+ knfe Ellbtta (V I. (witt (woft v. (m (m)))
V (w (r.00 1)
(25)
El Ellwotih (r.k-1) - w (1 ||a + n + 2km E | (r.k)
+ k -
+ 2km EI (r.
||" 1|
(w (r,
fm ||(
(26)
2k 8 1 (6.
E3| with (r (7,00 1|2 + n2:0
--
Fm + 2km7 (1 || V (w(f)
(27)
28

---

Unrolling the recursion.
B| W g.m
(ruk)
- (r.1)
11² $
2kmz El I || (m ( )1 nooo
1 + 1
2k
B |
(28)
Assuming that T/e -
we get knj
< 1,
PV2t
B
(r.k) W 9.m
w 1|2
2kn
B||
[ V (m )12 noo?
Σ
1+
+2
(29)
h
4k
2 17k
V (1 nioo?)
(30)
8k "a
El
g.m
|| (m. 1k7j of
(31)
Lemma E.8 (Deviation of the personalized model from the global model). If client's objective function
Jm satisfiex Assumptions E.1 3. and condition Tir S min 6V2X(K-1j BVIR in Algurithm
following is satisfied:
E|| w (r.k)
& 16A nf Vg.m
B (² 2 11
p.m.
+ 12 wif | (1:"T)) o2
Proof.
B p
(2.0))
1|
= [3] (md) (r.k)
wy gi
+ (1 - (rik) yan yum
(xx))
u ||
(32)
13] ( (wogt))
wm.m (r,)))) + (rrkk))) w )1
(33)
[3] (o (woftn) (ri))
- (n10) + w (r:0)
(w (r.K)
(m-00
(34)
< 2| wit (10
w0(r0) )1 2E| // (w (r,k)
(r.0)
)|
(35)
Using lemmas
E.6 and E.7
(r.A)
(r.0)
2
< 2E|| 2
(8h" E
V fm (w 6 |f
(10 )²)))
M p.m
w
p.m
+ 2E||1 - 2
1|
+
(36)
< 16A , E
||
o E 1 |?
12K"
p.m
(w )² 6K 6K (ra))
(37)
Theorem E.9 (Convergence of the Global Model Convex Cases), If each client's objective function f 1
satisfies Assumptions E.1
E.2
E.3 E.4
using the learning rate uR I S min 4vI0BBK2 8B2 in
Algorithm 2 then the following convergence holds: (Strong Convex Case)
R. (( F(w()
K
Fllw (0)
wIll
exp
MHKKR
2M
RRUR
20
40K?
132
+
qi
G
28K 3
2,8²
+ +1) o²
2² H2
9
4
(General Convex Case)
22
B [(w]R))] - F(w)) S
Blll (0) - w + me
ne (RR +
+ r
q 40K2g
1/3
+
0p) (10K33
+ ni (28KBot) 1/3 + ri (56K 3 33x)) 1/5
q
q
where 2 are the probabilities of picking global/local routes averaged over all the instances sampled from the global distribution.
29

---

Prouf. From the update rules stated in Equations 10
and 11
K (
W1g
(r+1)
W.
Σ
7m
W g.m
Nle
hmm
w
(38)
n.M
mejM
km
T.M
Wig
nM
Tje
Tam
Nim (wpion (/rkk-1))) 11)
w/
(39)
mE((M]
K
10g
7m
Σ
hm
(1))11))
(40)
n.M
MEI
1=1
Taking squared norm and expectation on both sides with respect the choice of hmm.
E [1
will"
E
[|
wgll"]
2n
Σ
El ( 1), w/g w/
nM
ME(M)
+
n
1
Σ
Am
(20 ()) par
(41)
nM
me
M]
Am
Separating mean and variance according Lemma of Scaffold 18]
< IB
[|wb")
- w.]1
2m
V
11 fm (u
Krik 11,, w/6 w.
n.M
Wiin
mE
[M]]
nio? K
+
n. Σ
nm
Jm (20 (rik-1) pum
(42)
2.m
M
T2
Bounding Ti
-27e
Σ
7mm
V
(r.k-1) mim
(rikk))))) (1 1], (r) wg
(43)
n.
m
km
K
Smn (rsk -1)) w/ wo!+)
2Tj
Y4m
(rik-1)
(44)
n.M
ME[M]
A=
Using perturbed strong convexity lemma (Lemma 5) from
we get,
2T Ti S
[
- V (m) 11 (uf")) -w + BB| pumm
(rk-1)
w (r)
112
n.M
mE(M]
Lemma
E.
(45)
$ 2n (B[F(w(())) F(wi))
TiHK
Ellwe()) will
2M
2
Σ Tmm
K
166 16 E
(
|E]
nM
mE[M]
12K 2 1
/E|IV fm
(46)
2 (B(F(u)())) F())))
Ellwb} will
2M
2
Σ
[,6 f. (|
(mx SK 3 11
T1m
nM
ME(M)
12
6K*
(47)
30

---

Next, using Assumption E.4
Ti - K (BIF(w)")) ] F(w))) KopkKK
B (u) - -w wrll
2M
32n K |B|| - 1p (c² + 2/3B² E p( - F(wi)) )) + 16n K BI?
+ 24m K 1 - 1 (c + 2/B3 (R. [(())))) - F(w3)) + 12n2 K² B0 Po?
(48)
< 2nc (BIF(u)")) ((wg))
Yea
Bl Bl ) - -
2M
(4K 3) 11 (B(F(u)))) - F(w3))
+ 3(4K 3]B||1 11 28m 22 10
(49)
Bounding T2
K
T2 = E
n.
1
7mm
(20 (1) p.m
f
(50)
= E
n.
1
7mm
(V "y
(r---1) fm (1) (r.k- 1)) - V. fm(1o)²)) + V. (un(r))))
(51)
ME(M]
< 2npEE
V (r)--1) fmr fm (1ppth-1)) V fm (m(()))))))
n.M
mE(M]
K Σ
+ 27/BBB
1
Σ
7mm
V fm (+))))
(52)
nM
mE[M]
k=
K
$ 22nE0'K K
nM
Σ
Nmm
I
pm
(r.k-1) 13
(7) 2
mE[Mr]
#=1
Lommell P.
+ 22/KK K
Σ
E
Fo (oo)")))
(53)
nM
Mc[M]
1=1
< 16 K 8tt (4K + 3)Bl|1 1/ (E(F(w) 1 F(w3))
+ 8t1 K 8 (4K + - 1
+ 56m x2 8d )? 112 + 2n K (c² + +28BBE[F(u6")) F(wi))
(54)
Plugging in Ti and T3 bounds.
E
Im0 (10 (r+1) - w²(12] s E [luggr wi]l?]] 2mp K
- -Fxx)) 16n K2 8² B² (4K 3) + 1)E [1 11² (E(F(W) F(w)))
E ((ag - -w
2M
12 3(4 BB
8 + E) 15 0² + 28 K² Bo
+ +567 x 8² 0 ( 10 2n K (G + B|
F(w3))
(55)
Rearranging the terms, and replacing E |= 1| and B|| 112 with ف (probability of picking global route averaged over the instances sampled from the global distribution) and qी respectively,
| (r+1) w -
1
neak
E
| w111²]
2M
B2 (n: l)ql - Kn/K²B²) (L [[w]b))] - -((()) + 40m 3(ne33 + 1)qic²
(2nrK s0ne K* B²
+ kn2 + +28/ K² 3(2 B K + 1)qio?
(56)
31

---

Assuming
W 3
3BB² B (1xB +)
S WI0SBK2 and By 2 Anj KBB²
2
wc get
(r+1) - [1 B
nouk 2M
E [1lveg] - wi]l"] -k q1)² (B F(u! FF(w))
400e K" 3(ne3* + +)qĪG² + 2n² + 28n K B(2 8² K l)q
(57)
Moving E F(ws F(wz)) to the left-hand side, and rest of the terms on right-hand side,
Tje K qu
(E [((ug")] F(w3)) - (1- "ejk
[[lu5]]
wāll"] E [1l00 will?]
2M
40m "=3((=83 + +1)qfG² + 2n KG + 28n K2 322n 32 K + 1)9ãož
(58)
:. [(w)")] - F(wg) - me
(1
JHN
[1lug] =6]l
IB
[11u
w
2
2M
T/e K
1) q
2ne
+ 40n K2 B
a²
+ 28 K B2 8² K 1)o?
(59)
e
Unrolling the recursion convex case from Scaffold [8].
rounds and then using the linear convergence lemma (Lemma for strong
T3 (( (
F(w()= S Bllws (0) -
TOKK H
20 LBuR
exp
9
2M
4
18a
qi
28K 3
2 K
+ oi
(60)
2
R²
uR
R²
4
H² K2
Unrolling the recursion over R rounds then using the sublinear convergence lemma (Lemma 2) general convex case from Scaffold [8].
E Fww ] - F(wi)) S
Bl Bll
-wzl?
+m
2G
1/2
+
( +
+ nl
40K
qi (²)
1/2
+n
G²)
1/3
+ ni (28K (88) 1/3 + nn (56K3) 1/3
9o
(61)
E.4
Convergence Proof for the Global Model: Non-convex Case
We start with a non-convex version of Lemmas and E.8
Lemma E. (Local version of the global model progress), mh client's objective function I' satisfies in Algorithm
Assumptions E.2 E.3
2
the following is satisfied:
E 1 w
1| < 4k Vf 11 2kn
mE
pomm w/ 11
(nd-1)
Proof. We start by expanding (r.k) in terms of its previous epoch iterate.
Ellw (r.k) (r.0))
g.m
w g.m
1| Elluo (r.k=1)
g.m
me V (n fm (w0 (20 u..m
(r.k-1)) (r.D)
g.mn
(62)
Using triangle inequality and separation of variance, we get,
Ell Ellae (r.k-1) - (n.0)
(m (w (nr + n200
(63)
Elluefrah-1) - (1.00
nz
1o
+ kn Ell fin(wu (wf((ttkk)) V fm (w((.))) + V V.n
(w
g.
(r.00))p
(64)
(65)
32

---

1+ k -
El| f
w a.m 11 n
+ 2k E fm (ws) (umpmmm-))) - Vfm(ub"))
(66)
El 10 ( -
k
2kne 3² B (10
w! 11
(67)
(68)
Unrolling the recursion,
h Σ
R| (5A)
5
(2km)
Fm + noo? 2km7 B (1 w.!
1
(69)
k --1
I3 (ung
(ri)) 9.m
(r.00)
11a S 2k
2k 1B] V fm (w= || + n2022
2km22
El| Ell (ni-1) -w
(70)
-k2 VT 2k + +4k 22222
B 1
(ri-1) pm
- -w(-111
(71)
Lemma E.11 (Deviation of the nersonalized model from the glohal model),
If mhh client's 's objective fanction the following is satisfied:
fm satisfies Assumptions E.2
E.3 and condition T) S 2V28K in Algorithum
E 1l
(r.k)
w g.m
(n.U)
20K of E
(r.Ak) 1 a.mm F (w) )1 + 10k" of (
Prouf.
B (mf w05: 1|
B3 ( wotth
+ (1 you (r,K)
Wggm (1.00 11
(72)
T3| pi (r.b)
- 10 mmm + (v.K)
w wr ) |12
(73)
B| gam (w
- w g.m
(n00)
+ g.m
(r.0)
(r.k) + (w (m) w w0.00
(r.K)
||
(74)
2B| wig (w
(2
|| 2E| (( (r.
(r,K) wm
(r,0))
(75)
Using lemmas
E.6 and E.10
Eljuefnn -wff"111 < 2B
4K B B (w. 66* 6 " (mn )}1
c
2E 1
2K + +3K +K< g²
B Bl m 1
(76)
Assuming B3
(r,-1) I zvス0k and unrolling the recursion over wp.m
20K² n/
(m.
FE
V (w. (r)) |1
10K 2 w
(77)
20
2
((
PE
(w
I 10K 2
(78)
Theorem E,12 (Convergence of the Global Model for Non-convex Case). Ifeach client's 's objective function
f. satisfiex Assumptions E.2 E.3
E.4 using the learning rate 28 S t/
min 2V53DK22 Vank<
Algorithm then the following convergence holds:
2
Be T [F(ug))] -E [[[ [E((( [[]]
R
M
qi 10
Kt B
(2.97² - n1 + 20 132 gon? (sni
17
9
2
2
33

---

Proef. From the update rule stated in Equation 11 and B-smoothness of fmx we have
F(ug F(wg") (VF(u)").us w0 w 3 (r+1)
2 mng
(79)
Taking expectation hoth sides,
F( < [(w]())] + ( (VF(u)""), w -w0" - > |10g (10
B
11
(80)
Using Equation 10 for second and third terms, and using the fact that the expectation is with respect to the choice of hym-
[(u
(F(())")
Σ
Iim (w (
Cm
ME(M]
ink
E
Σ ME(M]
Clym
Am (w
(rik-11)
(81)
M
where Oky
which are the weights for weighted aggregation according to the sample count, as shown in
Equation 11
Separating mean and variance according Assumption E.3
K
I F(w(+t)) E
[((w)())
VFF(o("))
Σ mE(M
Σ
R
V
(rik (r.-1) fmr (105toh
M
" 2..
+
Bnk E
(r.k-1) f' (woth (r 0.
n B03k K
(82)
M
2M
mEIM
Using (a, b) l/a - b112 + //1a/ + 11611
E ((w((tt)))
E [F(Wf+)]
1
VF(W!))
(3)
1
Σ
1) (w
(r,k-1) 1)
M
us 9,30
mE|M [M
n1
E
V F (wo("))) (r)))
E
M
Σ
V (r.k-1)
2g.m
fm (u (r.k-
(1p
ME(M]
km
+
Cm
K
(rck- 1) smm (wo
(rrk-11))
n2 K 2M
(83)
M
u
me M
1=
?i E
V
F ||?
2
K
1) fon Cork (oak-1))) 12
E
(rik s.m
ME(M]
2
1h 30
+
VF(W
Σ
(ni 1) fm (wo (rik-2)) p.m.
+
(84)
2M
M
34

---

S F(w)T)
)]
F
-2
K
7
E
(F(ug")
Σ am
trik
1)5mm (m (off
v (F(w(()))
2
2
M
melad!
K
n n2
+ !1 E.
VF(m))")
M
Σ
Om
"
(r Fm (1mbp (nofimh-11)
2M
(85)
mE [M]]
33
S F(w(())
ByQ
2
2M
-(% 11 - -mmt)
E
VF(W!)))
1
Oum
V
A 12
fm
(rik-11 1))
(86)
M
mE M
k=1
< I. [(w({r)]
311e
Bid
E
V
(w)))))) ||
+
2
2M
K
Σ
Qm Σ
mng
up
w
11)
(87)
M
me M
Using Lemma
E.IT
E (((w)+)))) < E [(w])))]
-
3qp
3nk
E
||
Bo K 2M
2
K
T/e
9n2
3²k
Σ
n2 20
20
w
|B] V sm (mo (wo)
?
2
M
am
+ 10K
2 (1
(88)
Using Assumption E.4 for non-convex case, we get,
E F(uf
S E [(w(())
3ne
- 3n2 E (F( (/ +
n2
2
2M
T/r
Bnt)
20 K ( G2 BBBI/FF(w 111 10
(Th
Bnk
(1/33 Ka o
(89)
V VF(W)))) }|² )|
Rearranging the terms to put E
on left-hand side,
3Tp - अ 20K 32 rp B² (/4 - BTē 1e |e((vF(ud))] S (((
2
- E
F(
- 20q k 8 n² (Th - Bn²
10 noo?
n
2 - + nh B0 K
(90)
2M
Assuming 10K- B² < 2 my S
マлHमA and 20K 1 1/ B²² S 2
ne S
T/8
V
||
I F. [( - E F(mn(()))
+ B0 K
2
2M
+ 20q k* n²
22 71
+ 10 K3 1 oo (snz 2 (91)
nt
2
E [(
- R (((m(++))))
+ 3 K
E
MqH
40 9
K n"
(2 - mp :1 + 20K no (3
7t
(92)
2
2
35

---

Taking average over all the R rounds.
Σ E
R
E F(
E [(m
noBoiK 1 Ma
S n n
R
+ 40 qं 4o
K Gn
(281k
+ 20 B'n (Bri "/(
(93)
E.5
Convergence Proof for the Personalized Model: Convex (Strong and General) Cases
Lemma E.13 (Local progress of the personalized model). If m th client's 's objective function fm satisfies
Assumptions E./
E.2
3.3 and E.4 and conditioning on S /V6K in Algorithm 2 the following are satisfied:
B| 5
(r.8)
< 18K 18 V fm (10 p.m. II2 + 108 ne fm (wl (1) + 126 1
(7.0)
+ 9K | 13 KO 11 141 ne El E |B ('m )01
Prouf.
< Bl| (i withh + (1
wor + yo jwmm
(n)0)) (m-0) (1 - wion yre no (
(94)
E/| (wonnk) oe agrn ao fm (1op)rhh))
M V
(1 w/r + me tnv Jmn (nmmmmpppp (or
wim
(n.))
(i (m))) - (1 (( 2
(r.
12
(95)
E Ellwstih " ugm
wgm work ne V (n fmn (uppink
neV V (rr fmm fmm (2afmr
wgm
+ ve V ao fm (1nbern y 2a.m
n (wfttn (w(tx
+ (1 vilca))) w(thk
(n,)) " V son sm (1a(n)))) + iim
(m)) (r.0)
g.m g.m
- (1 p.m (oo 112
(r.D)
(96)
Using the convexity of fm.
(r.k) fm (wffttt))
(r.))
f' (wbrkk
+1) (na) + (1 wiicht Ju (r.))
(97)
wa.m
S
(1 Wigm
fi (w)(()))
(98)
and
(1r)) f'm ( (1afornti)
(onne f' Sm g. (wofrrh)) (rrkk)) (r.KK)
wm,
(99)
(witth) w ( J (m (2)))11))
(100)
we get,
0 1|2
< Bl (r.K-1) + (1 (1- vgi wam -W worr00 (1 E.m
(1-w
(1-
(r,K)
Wgm
ne ne( ( fm fm (. + (r(
(101)
(1+
K B whik (r) - -6(r00 11² 3K V (1)
1
+ 3K
BlBBll (rxK)
(n.K 1311 3k 1|
(102)
El
(r.K-1)
((.00)
3
fm Sm (11 V fi ( + V fm (1
||²
K
+ 6K
(r.
w w 112 + 6K 6 || (: wo 111 +3k w/
(103)
Using Lemma
F.6 and
H.7 and smoothness property,
K-1 + 6K 8²
B (o (xX-1)
6K
V fm fm ا|
+ 6KT/
1/ (w) (w >12 + + 3K 3K
+ 6KT
(8K",
4Knão?)
(104)
36

---

R. 11 (7.K)
11.00011
6Kr fm (m0)t))) + fmm
-42k2 42k22n00
1=1
+ 3K
9,m
48 /.
11 K-1 + 6K 12
(105)
Assuming 6 < = f)t S DVER
El| (
- 11 Σ 3K 6K V Vin 36** V/n (1)" 42K no
3k k +
(106)
18K2
10sK
|| 126K 1/
9A 1
144K"
144K
(107)
Lemma E.14 (Deviation of local parameters from the aggregated global parameters). If m' client's objective the following is satisfied:
function Im satisfies Assumptions
E.3 E.4
in Algorithm 2
(,+10) p.
(r.K)
s 18
Koint +
6%
8%
K2n2
Kožni
+
6mm
8th
K2n2
M
M
+ 6(1 + 7p K² k² )n²
Kaini
+
6th
8"
K2
(c²
+ B²B VF
Prouf. Stating the aggregate rule from Algorithm
Lines and 20
El| (1+110)
112
R.
1 M
(r,K)
1
Σ
(r+1KK)
M
M
(M(M)
cE[M]
cE|Mr
V w mmm
(r. (r.K)
- (1
(108)
s 2
Σ
(n.K) 1
Σ
(r.K)
(o. w
(r.k)
M
CE(M]
CE(M
+ 2B
1
1
Σ
wemm
(++1,K)
- (1 - woo ) ye k
(109)
M
CE|M
s 2B
M
Σ
(r.K)
Pic
(m)
M
1
(r.KK)
w0
(v,KK
||
M
CE
+ 2B
w (
(r+1,K)
(T, 1|
(110)
cE(M
Using Lemma 8 from (29 and Lemma E.17
EE
(r+1100 p.m.
-w(=tkk 12 18
Koini +
5thh
8"
(Koinž +
((mm0
6mm +
8
k2n2
M
M
+ 6(1 + ni x² 3 22 x2
Koink
(6%)
+
K2nZ
M
(G + B² (
(1I1)
Lemma E.15 (One epoch progress of the personalized model). m/ client's objective function f... satisfies
Assumptions E.7
E.2 and and(E.4]i Algorithm [ the following are satisfied:
El| f (r.k41)
w (r.k)
|| < 3nf fm (w (w (r.)) A|| + 3n Bll
(r.K) -(rrkk)) 3n v.
Bl (1
37

---

and hence.
K
s 6,91 (01fm(wph)) (w(r))) -- f(1))mm) 3r/ K
Σ
ink
+ 36KK E V fm 311 40KK n/
+ 48K m/ Bl (w 1|
Ell (
9.m
Proof.
(1)+1)
11 E1llighth
u pmm
+ (1
(x.K)
u.g.m
(1
wighthh )uok 1 11?
(112)
TE
(p n1e (r fm (1n(tra)))
(witth) me V
wo f'm (1 pooh))
+ 1
Wiich V
a Jm (1obir)))
W..
(r.K)
Vam wog - (1
(rik)
wh (rikk)
s.m
(
(113)
(rik)
m.
trw fmn (wppp))
mamm
+ ne sto fm (woftck) (rrkk) V
Sm (w)tth) (rak))
+ +(1 - (i(kk)) (r.K)
womm
+ new i.
(1,4)
wonn fm
(on((1 (r(()) - (rrn) wemnenggn
(r.) - (1 (rik)) (x) 12 ) j
(114)
TE me (m
( fm (1iffchh))
Tie (1(0442))
fm fm (1opsm)))) (1000 sim
(115)
Using,
(r. fmr (wutth)
= V fm (V () waggn + (1 (r) uamm
Ju Kr)
Ju k
(116)
I w/ (nn+1) fm (w (rek))
(117)
p.m
and,
f'r (vofrin))
V worch Sm ( (rrkk) (r.6) (0 w (r.K))
g. (uogin)
(118)
9.m
I (wf
w 2 (in fi (1(
(119)
we get,
v/² IE
(r.
(((ritt)
V (w ||
(120)
< v/ TE
V Fm (withh) (rik))
+ (10 (m,K)
- mofrrh))
+ wi 1+1))
(121)
< 3np B
V mm (wofrrt)) 111 + 31/2 1E|
2
(r)))
(r.Ae) 11
33/ H
B (r. 111111111
(122)
From Lemmas E.6 and E.7
Summing over = k: to K.
K
E upm
(r.k)) 1
Bl
p.m
(nk+1)
w 112
(123)
i=k
< 3nf
E| m (1 + 3n/ K
Σ
Blllghh (m))
||
p.m
+ 6n
+ 3K
K
6m
[8
3 Elll
"1IV )112 |
mp
(1
4K KK
(124)
38

---

S 639g [llf (10ftn))) f(162mm))
3rp K
TB] 1e 11
+ 366 n2 B V (2m5
+ 188K no52
+8K
m/ B V Fm
(w ||(
18] pugg 11 + 24K 22022
(125)
E (e (r,K) p.m
1| 1 6,377
[Biʃm (1n) - f(wp.)) + 33/ K
B 1 ||?
36K fm (2ng )1 + 40KKK 2 neo?
48K " Fm (ucg I
B g.m 11
(126)
Theorem E.16 (Convergence of the Personalized Model for Convex (Strong and General) Cases), If each client's objective function fm satisfies Assumptions E.2 Algorithm 2 then the following convergence holds: (Strong CoRvex Case)
E.3
E.4 using the learning rate aR I my K3² in
E
[mm(u (w((ne))
[m( -
36 RK3
Bl
w
(1.K) p.
wjmml 11 Fexp
exp
1
MOKR
K -1
R
+1K o 12K
2/6
1/2
+ 1K o
16A T/
R
16K 10 Ti
1
Σ
E
VI (++1)) ||
Kt
o7 K
8 +
8th
)
8
M
K
M
+ B²
8thh + [Koime +
5th
K21H 11
2
B
V
F
(w²y (r) )1 26
M
(General Convex Case)
B fm fmm(w (w0 }] - fm (wrg.))) S
1 +
1
Ellwe (1.K) - up.ml
3617 K2R
K
R
+ (12K2
B
BIVF
|
no
(12K"
TH (4
R
+ n/ (16K*
BII
+
(16K 13
R
K
8th
o K
)))
1/3
+ mi
6m
+
2
K
M
M
+ 1/
K2
of
8
8
2
Σ
R
B
(
25
1/3
M
R
where 1
ER_ EE FV (r) )1 is bounded as shown in Theorem E.12
R
Prouf. We restate the update rules of the personalized model in Algorithm 2
For all samples Zm. define wp.m (am) 4- 1.g. (mm (r.6) (sm) + (1 (. (x (2m) Dao K) (Im)
2. Train policy parameters tgg.n gggm Me wir fov fmmmmmnn (186t162) (xm), vmm)
(r,++1)
3. For all samples Fm. define (r.k)
upp. (Im) ) <- 2..m
(r.k=1)
(xm Jon (am) + (1
Bo (Imm 1
(r.k+1)
(r.K) (mm)
4. Train global parameters wa.00 <- Wg.m
(n.))
(r.-1)
T/e
V
(r.k
1) son (wii (a ), Hon)
39

---

B |1
p.o
(+)1,8)
Wp 11 E]
p.m
())
pm
((++ 00
+ pm
10(++1100
(r,K)
+
(r,K)
(127)
2
[B] |
pm.m
pm
10
11 +2K El 11100 (opp..m.0))
Lammo
Lemmo BERE)
1+ K
Bll (r.k)
(128)
And using Assumption E.4
S 36K* n8 [no (w((pp))))
[m (m(((tttttt00
+ 2 11 + 126K
+ 18K 1/ 1
+ 288K
( y1²
p.m
+ 18
Kooēt
8
8
K²nt)
Kožnk
8
K kt
M
M
8t
+ +6(1 + n/ k n²
Koint +
6 +
Ell
V fm (zn²"))
M
+ K-1 uole Blleeft
(129)
Rearranging the terms,
36K 1oK-n² m [ fm (mm [1)] - fm (wjj)))
S 1+
K K-1 pime E| (r.K)
1
+ 216K " V (2of
11 + 126K nho7 + 18K2 n/ E |1
"p.mll 1? El lupp
(1,+1))
upmml? 11?
+ +288K* 1/e Ell 1,) [
18 Kožnž 8 + M
8th
1²
(Koinz + 6m
8
M
8%
+ 6(1 + n x2 x m k²
[Koine +
5mhh
K n2
El| (w
(130)
M
mm (u)..) S 3612 K2
1+ K mome)
Elleetiin) w 11
R 11 (r.
upm.ml + 6K22
77 F.l
V fm
11111
AKnEot +
361 k2
+ 8K n 1
(1) | (1)(+))))1
k²n
o²
+
tth
8th ))
(
o
+
6mmh +
8
2
K
K
M
1 K2
8
Koin
k2m
E
V fm (m6
(131)
6
M
For strong convex (fx > 0) case, using the linear convergence rate lemma from [8] (Lemma 1) and Definition
E Im (o. (wpphho)) - fm (wpp.) )
36,²
Bl|
(. p.m.
(1,K)
exp -mpm
1
noKR
RK3
K-1
12K2 2 200 + 12
R Σ
1
E
44K
q
16K 21
2
16K W/. 40
2
1
R
E V|
(1 211
K2n2
o K
8t
8th
oo
8
R
M
K
M
+
ne K2
(Koine +
8th +
5th
K2 1/6
2 R
Σ
E
V
Fw
(r) 111
+ 26th2
(132)
M
R
40

---

For general convex (1 = 0) case, using the sublinear convergence rate lemma from [8 conditioning on of K2 < TJe
(Lemma 2), and
KJ2
E fm (1offt
)]
fm (m)
1 + K
Bl
(1.K) up.m!l?
36 K2R
p.m
(12K2
B BIVFF(u
+ nr (12K
+
n 2
90
R
(16K
goom
+ (16 qó
B||
BIIVF(w 1133)
R
n1
K2
o0
+
6m
8th
M/
K
+
60
MM
1/3
too
K²
6
R
Y/
8 +
B
VF(W
25%
(133)
K
M
E.6
Convergence Proof for the Personalized Model: Non-convex Case
Lemma E.17
(One round progress of the local model). mm client's objective function fm satisfies Assump- the following is satisfied:
tions
E
E.4
in Algorithm 2
(++1
11
S (1 K + x2 8 mek (o² - VB'
Proof.
K
K
TR| 1 -m
(++1,K)
11 = Fl1le0 (r+1)
-7 Σ
V fm (wfrtt)))))
-10g + m Σ V fm (m)
(134)
k=1
Elllofr (1+))))) - m/g m
V (mm(un (un(r+)))) - V (mn)) 112
(135)
nk 82 (w((41) - -wk")) 112
(136)
El|(1 - mK 33)
(u) (r+1)
w!() 11?
(137)
$ (1 - )
1
wh
(m,K) w/ |
(138)
M
CE|M
(1 3
1 M
(m) (r)
me
(m(((())) - m |
(139)
(1 MK3988|
T
V Vun
(140)
M
M]
k=1
< (1 qe K8
K
Σ Ffm(w!)) {
(141)
M
cE[M]
< (1 qe 8 R2 (G² + B'RIVFF( ( M13)
(142)
27. K3
n K2 B² 2 K2 (a' + BB )'EI|=((w(>>)1))
(143)
The last inequality follows from Assumption E.4
We proceed with a lemma which binds the deviation the personalized model wy of an arbitrary client m over one round, i.e. wp.m and w for non-convex case.
41

---

Lemma E,18 (Local progress of personalized model), If client's 's fbjnctiiv,uunctin fm. satisfies Assumptions
E.3
E.4 and Ti I kv122(K-1)" Algorithm the following is satisfied:
18] p.m
(r)+1)
w/ I 18K"
(w ( 21( 9K oo + 36K +36K"10o - y.
(
1|
24K 2 V fm (m " "
Proof. We start with using the update rule stated for the personalized model at the beginning of Theorem E.16
(nk+t) El gm
(110000 1|? = [B] (m w 9.m.
( (r.k-1)
1) (1 (ffrst-1
yur E.m
(r,K)
11?
(144)
Expanding by one iterate.
Ell (1(t Tee of (r(
(wigth)
(MA)) fm
me
+ [1
Pa.m
V
(nee Smn Smm(mmuuuu (wptrit)
Wam
(r.K)
wftm 1?
(145)
El (istthh (rik)
(ri))
V
(ndy fm (m(
(o(mr)) V
(ri)) fmr (wfph)))
+ ne waa fir (
(rtt) fm fm(up (w(ttt) + (1 wornt) ju
(r.K)
"
+ wem no woth fm mn(uun (wbtrn)) - (ni)) 1?
(146)
Ellwgt p.m
(r.k)
(r,k) me - w (nu) + (wof w
fm (1o (n.))
V
(r- Sm (w )) T/
(n.))
(we (m1)) )11
(147)
S 3E p1
(r.k)
w
(m:0)
1|
3E
(r.))
w
(rk))
g.m
+ 3r E
(rik) mm.
Fm (w )
(148)
The inequality was derived from the fact that B|| V
(r. fm
||
E| 1
(r,k+1)
(r,))
1|?
< 1.
Unrolling the recursion across r [R], then using Lemmas F.6 and E.10 and Assumption E.4
(r.K)
11 S Σ
((+
1+
1 K -
E|| Elluo
(r, c.
w with 112
KI
)1
p.
(149)
6K* ,/ fm (n(
12K22202E) 3 12 12K o2 vo.
+4
1+ K K-1
K ka N/ (m "1
K
+ 12K2
(150)
K
Assuming x 2 12
m1
K /v122K-1)3 1133
El Elloo/1/00
2
6 6K V. ( 3K m202 + 12k n/ 1666219112
+1 +1(1 K -
T (mobT)) 1160011000000111 3K
(151)
18K E mm
9 ト/ + 36K y1 -
+ 24 77 E. V
(152)
42

---

Lemma E.19 (One round progress of personalized model). If mhth client's objective function fo. satisfies Assumptions
E.3
Algorithm the following is satisfied:
E 10
(r-1KK)
p.m
1 pm
(1
72 + T²)K [ BB
(F (F(m )11)) + 1202
8th
8
+ Koēne +
Om
K2 n2
Koêni
8th +
K²
M
5
+ 12(1 + ni K2 222g" mn²
Koēnk +
6
K K²
M
(c² + B²B ( {
Proof.
E
= E w/
(r+1,K)
upm
(.+1.0)
+ up.
(r+1.0)
11
(153)
2 II w/
wpm
1.0
2E 2||
(
wp p.
(154)
Using the Lemmas E.18 and
E.14 14
we proceed as
72(1 + 1
(G2 + B²
BB )13) + 120
+ 36 Košnh
8t Tthh +
kzn²)
(Konn++ + 5th
8
Kzni
M
M
8t + 5th
+ 12(1 nē K 3"
(Koint +
kzn (6* + B'BIIFF(({>)))+
(155)
M)
Theorem E.20 (Convergence of the Personalized Model for Non-convex Cases). If each client's s objective function I'm satisfies Assumptions E.2
E.3
E.4 Ausing the learning rate I kV128 in Algorithm 2 then the
following convergence holds:
R
B
fm fm(mmpuu (wb
Fro (un(100) (10((111)))
R
R
6(1 + n 5K(G² + B²
Σ
BlIVF(wg )11)) +120
R
5v
5
-3Knž
07 +
6m +
K
o7 +
6 +
K
M
M
8
R
(1 + k2 3* m K
0
8
K
G²
B²
BIVF
M
R
Proof. According to the update rule of Equation 10 and 8-smoothness of fn, we have,
I'm I' (m/ (r)1)))))) 1 [m (wo(rkk)) + V fm (r,K)) w w p.m
(r+1,K)
(r.K)
+
I p.m
(++1K)
wr (156)
Taking expectation on both sides.
Jm (w SB B [im (omprnn
+ E1 10llmmmm (m-1,
8
2
E (m k)), u wpt (14,1, (K) (r,KC)
(w(r)
(157)
43

---

Using (a, b) =|lall² + 1 1612 la - b11
F ffm(wj (mn(w/ttttt..1))
F.
fm fmn (m }}
} 2 FF (mo (o )1
+
13+1
E|| p.
(T+
-p..m
2
1
Bl| V fm (w (1
Wpm wopmh))) )1(²
(158)
S fm fmmmuyh (w) }
+ 2 V fm (wm ( )11 +
3 1+1
El 1 pm
(r+1,K)
1p2
EmI (u ( >1( Bl| ( (wpp k. ( )1
(159)
x E
fm (wsiin)
Ell V fm (win (usiim +
3
El
(v41,K)
'12 p.
(r.1C)
2
p.m
(160)
Rearranging the terms to put | V fm ( 2 LHS.
1 B V fm (w/h:)))))))
1
) 12 < 1B fm (ung, ((rrk)))) }]
fm (w (.)))
+ + ($-1
3 1
E]
1upm upm
(r.K))
LemmalT ET
(161)
B| V fmm(fff
s 2 [ fm ( (of
E Im (u
+ 728 + K² (5K + B'EIIFF(U (1n)))) () + +120?)
5th
6 M
+ 368
Kainj 2 +
-thh +
Kooini +
6
K² 2
m/2
M
(0% + 8th
+ 128 + n2 k2 3 m K²
Koink
K
K²nl ne
M
(c B' (w))( )1())
(162)
Taking average over all the rounds [R].
R
B V (m
211 S [B [m [mm(wpp) (1 }
Fm fmm(up (wp (
+ +7,8(1 + T2) TE
5K(G² + +B²
Σ
Bl| v F (w) )())) + 1202
R
+ 363K21n 1/ 0ī +
8:mh +
5th
K
+
+
8
K
M
M
8th
R
12
ne K² 8th m R2
0
K
G²
B²
FVF )1
M
R
(163)
Assuming 12K <151
m) x /V
E V
1 (w
(r.kk) )112
E
fm (1
- E fm fm (1.( )
R
R
R
+6(1 T²)K
5K(G2 B²
BlIFF( ()) 1207
R
(02 + nn
6%
8v
K)
+
+
5 M
M
8
R
(1 + n1 2"
B*) K
oo
8% +
K
G²
B²
B BIFF(
(164)
M
R
Plugging in Theorem
E2 )
to get bounds on Σ (2I (1) )1²
would get us bounds on
(x.1) V fm (w
44


Reviews:
[{"review_id": "fAb0tPw123", "reviewer": "Reviewer_iGNe", "summary": "This paper proposed the Flow, which achieves per-instance and per-client personalized federated learning by dynamic routing between a global model and a personalized model. Flow creates a personalized model that adapts to each client's data instances and distribution. In each federated learning round, clients have both global and local model parameters, which are fine-tuned to fit the local data distribution. The dynamic routing module predicts for each instance using either local or global model parameters based on the instance preference, thereby improving the accuracy of the personalized model. The authors also improve the accuracy of the global model by identifying the instances on the clients that are in agreement with the global data distribution. The extensive experiments have been conducted to evaluate the advantage of the proposed Flow. ", "questions": "1) Is there any experimental results to support the heuristic step in line 124? What does the proportion of data used for fine-tuning impact the final experimental performance?\n2) How does it compare to the existing flexible personalized FL algorithms, such as some algorithms based on NAS?\n3) What is the additional training time overhead for fine-tuning the local models?\n4) What is the additional time overhead for dynamic routing decisions during inference?\n5) Does the current reuslts can be extended to the more general dynamic routing framework, such as MoE?\n", "limitations": "Please refer to the weakness discussed above. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The authors proposed a new personalized FL algorithm that utilizes the dynamic routing strategy to generate dynamic inference models that best fit the local data, which is a new aspect of personalized FL.\n2) The experiments are comprehensive, and the code is included.\n3) The writing is clear.\n", "weaknesses": "1）The Flow proposed in this paper takes a different approach compared to general local model personalization methods in FL literature. In some typical personalized FL algorithms, a large global model is generated on the server. When the global model is deployed for the personalized requirements of clients, NAS or dynamic routing are adopted to get a smaller model which can better fits the local data distribution (e.g., OFA and AdaptiveNet[1-2]). In contrast, the authors suggest storing both the personalized local models and global models on the client, and dynamically selecting the inference path based on routing decisions, which can adapt to local data distribution and instances. However, this approach introduces additional local storage and computational overhead. Especially when the global model has a large parameter size, the proposed algorithm is limited.\n2) Some metrics proposed in the paper are heuristic. For example, in line 124, the authors divide the local dataset into two parts because they considered that fine-tuning the local model with the entire local data may lead to overfitting.\n3) The selection of baselines lacks some personalized FL algorithms based on NAS or NAS-inspired methods. Flow and these baselines are both algorithms based on path-searching, and it would be interesting to supplement the related comparative experimental results.\n\n4) Some claims are unclear. For example, in the abstract, it is a little confused that the personalized models could achieve lower accuracy than the global model. \nIt seems that the per-instance personalization FL is more fine-grainded than the current personalization FL. However, this would also introduce additional overhead. The authors need to discuss the overhead of this operation. \n\n5) The authors only consider two types of models for the clients to select: i.e., the persoanlized model and the global model. However, in conditional computing paradigm, such as mixture of expert (MoE) framework, each instance can be routed to different kinds of experts.  \n\nReferences:\n1) Once-for-All: Train One Network and Specialize it for Efficient Deployment\n2) AdaptiveNet: Post-deployment Neural Architecture Adaptation for Diverse Edge Environments\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1/Q3: Additional local storage and computational overhead of a personalized model (Especially with larger models)**\n\nA: Please refer to the answer to W2/Q2 of reviewer QKWb \n\n**W2/Q1: Heuristics to divide the local dataset**\n\nA: We experimented with the Stackoverflow Next Word Prediction task on initial rounds for the local and global training dataset splits. The plot is attached as Figure 1, in the PDF attached to the global response titled “Author Rebuttal by Authors”. We observe that for the dataset split size ratio of 0.75:0.25 for local and global datasets respectively, the global model does not get sufficient samples to converge, resulting in worse personalized model performance since the personalized model is based on the global model. While a split of 0.25:0.75 for local and global datasets has closer performance to that of a 0.50:0.50 split, lesser data (and hence fewer iterations) to the local model leads to local model weights being similar to that of global model, diminishing the impact of personalization.\n\n**W3/Q2: NAS-based methods as baselines**\n\nA: Our literature search yielded two papers on NAS under federated setup for personalization:\n\n[1] Personalized Neural Architecture Search for Federated Learning (FL Workshop @ NeurIPS ‘21)\n\nIn FedPNAS, the personalization happens similar to FedRep, as only the head of the model is getting personalized. For personalization, they need to compute hessian of the personalized parameters, which is computationally expensive, hence they restrict personalization to a smaller subset of the parameters. Moreover their search space is computationally expensive, on the scale of $10^6$. Further, this paper’s experimental depth with respect to tasks and datasets is quite small, and code implementing the algorithm is not available to reproduce the results or adapt to a broader array of tasks and datasets.\n\n[2] SPIDER: Searching Personalized Neural Architecture for Federated Learning (FL Workshop @ AAAI ‘22)\n\nThe setting of SPIDER demands an over-parameterized global model, and finding a suitable personalized model path in that over-parameterized network. Besides the communication and computation overhead of the bigger global model, and storage of a separate local model, the goal of this work is to find a personalized architecture per-client to fit a computational budget. It still doesn’t address the issue of personalization harming the client’s accuracy due to a few instances which fall under the global distribution. Besides, SPIDER requires all the clients to participate throughout the federated training process as the personalized models would be progressively updated with a new path, which is not a practical scenario for cross-device FL, which Flow is targeting. \n\nSince the reviewer mentioned the following works, we also comment on them below:\n\n[3] Once-for-All: Train One Network and Specialize it for Efficient Deployment\n\n[4] AdaptiveNet: Post-deployment Neural Architecture Adaptation for Diverse Edge Environments\n\nDue to the heterogeneous nature of FL clients, OFA and AdaptiveNet face the same challenges as FedAvg (i.e., slow or poor convergence). This is because they require fully training a super-network first (which will be based on FedAvg), and then progressively shrinking it or doing the post-deployment adaptation to make the inference faster and more accurate. Note that one of our baselines KnnPer also personalizes the global model after training the global model to converge using FedAvg. The results of KnnPer show that “personalization after training a global model to converge” performs worse than “personalization during training”.\n\nWe also want to draw the reviewer’s attention to another baseline we use, PartialFed, which makes a layer-wise choice between global and local models to create a personalized model, but sends the personalized models back to the server in lieu of a separate global model. This method faces the same issues as FedAvg in the heterogeneous FL setup.\n\n**W4/Q4: Overhead of the dynamic routing operation**\n\nA: We have discussed the dynamic routing operation overheads in answer to W2/Q2 of reviewer QKWb, under the table. \n\nMoreover, from Table 1, we can see that compared to some other state-of-the-art personalization techniques (e.g., FedRep, APFL), Flow requires similar or even less computations.\n\n**W5/Q5: Extension to a general dynamic routing framework**\n\nA: With this work, under the context of federated learning, we have only considered two models because for each client, there can only be one global model and one local model. Only using two models for dynamic routing is not a limitation of this work, but a requirement for our setting of personalized federated learning. \n\nStill, we can extend this framework to more than 2 “experts” by having softmax of Equation 2 accommodate as many routing path probabilities as there are experts. And then taking the linear combination of all the weighted model outputs in Equation 3.\n\n\n\n"}, {"review_id": "onRmOi2VlI", "reviewer": "Reviewer_QKWb", "summary": "This paper presents a novel approach to address the data heterogeneity issue in Federated Learning, resulting in improved accuracy for clients. The proposed approach, called Flow, is a per-instance and per-client personalized Federated Learning algorithm that uses dynamic routing to create adaptive personalized models for each client's individual data instances. The paper provides theoretical analysis on the convergence of Flow and empirically demonstrates its superiority in improving clients' accuracy compared to state-of-the-art personalization approaches on both vision and language-based tasks. ", "questions": "see above", "limitations": "see above", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents a novel approach to address the data heterogeneity issue in Federated Learning, which is a significant challenge in real-world applications.\nThe proposed approach, called Flow, is a per-instance and per-client personalized Federated Learning algorithm that uses dynamic routing to create adaptive personalized models for each client's individual data instances.\nThe paper provides theoretical analysis on the convergence of Flow, which adds to the credibility of the proposed approach.\nThe paper empirically demonstrates the superiority of Flow in improving clients' accuracy compared to state-of-the-art personalization approaches on both vision and language-based tasks.\nThe paper is well-structured and easy to follow, with clear explanations of the proposed approach and experimental results.", "weaknesses": "The motivation of this paper is not convincing enough for me, how can per-instance FL solve the challenges is not clear. \nThe paper does not provide a detailed analysis of the computational and communication costs of Flow, which could be important factors in practical applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1/Q1: Motivation behind Flow. How does per-instance FL solve the stated challenges?**\n\nA: The challenge we are addressing with Flow is the limited performance improvement from personalization in federated learning. Our empirical results indicate that the above challenge comes from two reasons: (a) Some clients’ personalized models are not able to outperform the global model (and therefore defeating the purpose of personalization), and (b) For the clients’ personalized models which do have better accuracy compared to the global model, some instances of those clients are still incorrectly classified by the personalized models but correctly classified by the global model. \n\nMotivated by the above empirical results, we develop Flow to allow each instance on a client to choose the best module (the local model layers or the global model layers) to execute. Flow  creates a dynamic personalized model that combines the local and the global model using a policy module. For each layer, the policy module decides whether to use a local layer or a global layer depending on each instance of the client. The policy module makes Flow adaptive to each client’s individual data instances (per-instance) as well as their data distribution (per-client). The dynamic personalized model improves the performance of personalization because (1) It increases the number of clients that favor the personalized model by 1.15-1.34%  (2) It decreases the number of misclassified instances of a client’s personalized model from 4.74-7.93% of best performing baselines to 1.12-2.42%. \n\n**W2/Q2: Computational and communication costs of Flow**\n\nA: We agree with reviewers that Flow introduces additional storage and computational overhead compared to the canonical method FedAvg with Fine Tuning (noted as FedAvgFT). \n\nHowever, compared to other state-of-the-art personalization methods such as Ditto and APFL, Flow requires similar or even less storage and computational overhead. To illustrate, the table below compares the storage, computational overhead, and communication cost for personalized models from Flow and baselines using the CNN for EMNIST, and RNN for Stackoverflow. We will add the table and similar analysis for all the models used in the paper in the appendix of the final version. \n\n|  | Local Storage of Personalized Model (unit: parameter count) for general case | Local Storage of Personalized Model (unit: parameter count) for Stackoverflow RNN case | Computational Overhead of Personalized Model of the RNN used for Stackoverflow (unit: FLOPs for training) | Communication Cost (unit: parameter count) for general case | Communication Cost (unit: parameter count) for Stackoverflow RNN case |\n|---|---|---|---|---|---|\n| FedAvgFT | \\|$w_g$\\|  | 72.38M | Not Applicable | \\|$w_g$\\| | 72.38M |\n| knnPer | \\|$w_g$\\| + #instances * \\|intermediate representation\\| | 72.42M | 12.46M | \\|$w_g$\\| | 72.38M |\n| PartialFed | \\|$w_g$\\| + 2 * #layers of $w_g$ | 72.38M | 36.9M | \\|$w_g$\\| | 72.38M |\n| APFL | 3 * \\|$w_g$\\| | 217.14M | 73.8M | \\|$w_g$\\| | 72.38M |\n| Ditto | 2 * \\|$w_g$\\| | 144.76M | 36.9M | \\|$w_g$\\| | 72.38M |\n| FedRep | \\|$w_g$\\| | 72.38M | 51M | \\|$w_g$ base\\| | 70.98M |\n| LGFedAvg | \\|$w_g$\\| | 72.38M | 10.5M | \\|$w_g$ head\\| | 1.39M |\n| HypCluster | 2 * \\|$w_g$\\| | 144.76M | 36.9M | \\|$w_g$\\| | 72.38M |\n| Flow (ours) | 2 * \\|$w_g$\\| + \\|$\\psi_g$\\| | 145.651M | 39.57M  | \\|$w_g$\\| + \\|$\\psi_g$\\| | 73.271M |\n\nIn the above table, $w_g$ is the global model\n\nFor Flow, $\\psi_g$ is the policy module. For our experiments on Flow, the policy module has 1.23% for Stackoverflow RNN, 8.39% for Shakespeare RNN, 27.86% for EMNIST CNN, 35.51% for CIFAR10/100 parameters of $w_g$.\n\nFor EMNIST CNN, for one epoch, the dynamic routing takes 0.3M FLOPs, while the rest of the model computations take 2.9M FLOPs. Hence the overhead is 10.34%. For Stackoverflow RNN one epoch, the dynamic routing takes 0.89M FLOPs, while the rest of the model computations take 12.34M FLOPs, making the overhead 7.21%. We believe the additional computation overhead from the routing module is relatively small.\n\nBelow, we will highlight the computational and storage analysis on Stackoverflow dataset for the best performing methods, APFL and Hypcluster. The computational overhead is calculated for one epoch of training, which is then multiplied with however many epochs the baseline needs for convergence. APFL needs to train two separate local models for more numbers of epochs than Flow, hence the higher computational overhead. In comparison with HypCluster, Flow introduces 7.23% overhead. With respect to both APFL and HypCluster, Flow only introduces 1.23% storage overhead.\n"}, {"review_id": "1g1eRPE6Xb", "reviewer": "Reviewer_cLqQ", "summary": "The paper proposes a per-instance personalized federated learning algorithm called Flow. The algorithm creates dynamic personalized models that adapt to each client's individual data instances. The personalized models allow each instance to determine whether it prefers the local parameters or the global counterpart for making predictions, resulting in improved accuracy. The paper provides theoretical analysis and empirical results demonstrating the superiority of Flow compared to state-of-the-art personalization approaches.", "questions": "- What is split data used for?\n- Why is there no \"Ablation on Dynamic Routing Component\" like Figure 4(c)  about other datasets except for stackoverflow. I am very interested in the results, but I cannot find them in the appendix.\n- In Table 2, why did LGFedAvg's Acc_g achieve a relatively high score and even surpass FedAvg at the CIFAR10(0.6) setting? Didn't LGFedAvg only aggregate classification layers? In terms of my own experiments, it is reasonable that it should be worse than the fully aggregated FedAvg.\n- the seed selection \"0, 44, and 56\" seems deliberate to me. \n- Dynamic routing is done by layer-wise to select the layer of the local model or the layer of the global model. My concern is how to ensure that the input space and output space of the local or global model are matched.\n", "limitations": "Instead of using a real-world federal learning dataset, the division is performed on a general NLP/CV dataset. Routing module may cause the risk of leaking client privacy distribution.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The paper proposes a novel approach for per-instance personalized federated learning, which is not explored in previous work. \n\n2) The proposed problem “each clients’ data instance is limited to using its personalized model for prediction, while some instances could benefit from better generalization of the global model” is a real PFL problem need to be solved. \n\n3) Both CV and NLP datasets were used for the experiment evaluation. The logic of the paper is clear and easy to understand.\n", "weaknesses": "1) There are additional computational and communication overheads that are not analyzed inside the paper.\n\n2) some hyperparameters are not introudced: for example, the values of K1 and K2. \n\n3) There are no converge curves compared to other baseline algorithms.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1:  Computational and communication overheads**\n\nA: Please refer to the answer to W2/Q2 of reviewer QKWb\n\n**W2: Hyperparameters**\n\nA: For Stackoverflow and Shakespeare, $K = K_1 = K_2$  is set to 3 and 5 respectively. For EMNIST, CIFAR10/100 variations, $K = K_1 = K_2$  is set to 3. These hyperparameters, along with the rest of the model and training hyperparameters are mentioned in Appendix B.\n\n**W3: Convergence curves**\n\nA:  Please refer to Figure 5, in the PDF attached to the global response titled “Author Rebuttal by Authors”, to see the conference curves for the global model (generalized accuracy). We will add curves for both the generalized and personalized accuracies in the final version of the paper.\n\n**Q1: Utility of the split data**\n\nA: We experimented with the Stackoverflow Next Word Prediction task on initial rounds for the local and global training dataset splits. The plot is attached as Figure 1, in the PDF attached to the global response titled “Author Rebuttal by Authors”. We observe that for the dataset split size ratio of 0.75:0.25 for local and global datasets respectively, the global model does not get sufficient samples to converge, resulting in worse personalized model performance since the personalized model is based on the global model. While a split of 0.25:0.75 for local and global datasets has closer performance to that of a 0.50:0.50 split, lesser data (and hence fewer iterations) to the local model leads to local model weights being similar to that of global model, diminishing the impact of personalization.\n\n**Q2: Ablation on Dynamic Routing Component (for rest of the datasets)**\n\nA: You can find the results on other datasets in the PDF attached to the global response titled “Author Rebuttal by Authors” as Figure 4. We will add the results in the appendix. Thank you for pointing it out.  \n\n**Q3: Global accuracy of LGFedAvg**\n\nA: The global accuracy of LGFedAvg for CIFAR10 (0.6) is indeed lower than FedAvg, as it is for the following other datasets too: Stackoverflow, Shakespeare, EMNIST, CIFAR10 (0.1). We do see LGFedAvg surpassing FedAvg CIFAR100 (0.1 and 0.6) setups [Table 4, Appendix C.1], which can be attributed to poor performance of FedAvg due to higher class count across clients, which is also displayed by a decrease in CIFAR100 performance as compared to CIFAR10 for all baselines.\n\n**Q4: Seed selection**\n\nA: The seeds were randomly chosen. Choosing different seeds doesn’t impact the results. We have re-run Stackoverflow experiment with seeds in {1, 2, 3, 4, 5 , 6, 7, 8, 9}, the results show no significant difference. See Figure 2, in the PDF attached to the global response titled “Author Rebuttal by Authors”: \n\n**Q5: Enforcing that the input and output spaces of the local and global models are the same**\n\nA: Like many other personalization works [5, 6, 7] in federated learning, the assumption is that the personalized or local models have the same architecture as the global model. To ensure that the input space has been matched, during training, we have used a soft policy. This means that the input to an intermediate layer is a linear combination of outputs from both the local and the global layers. During inference, even with the hard policy, the outputs from a layer can be fed to the next layer of both the global and the local model because of the same model architecture. The similar logic applies for the output space.\n\n[5] Adaptive Personalized Federated Learning (Deng et al., arxiv 2003.13461)\n\n[6] Ditto: Fair and Robust Federated Learning Through Personalization (Li et al., ICML 2021)\n\n[7] Three Approaches for Personalization with Applications to Federated Learning (Mansour et al., 2002.10619)\n\n**L1: Real-world datasets**\n\nA: We have picked both artificial (CIFAR10/100) and real-world heterogeneous datasets (EMNIST, Stackoverflow, Shakespeare) especially suited for the federated setting (more details in Appendix B). These datasets have been used in many federated learning literatures [8, 9, 10] to address the heterogeneity issue. \n\n[8] Adaptive Federated Optimization (Reddi et al., ICLR 2021)\n\n[9] Motley: Benchmarking Heterogeneity and Personalization in Federated Learning (Wu et al., arxiv 2206.09262)\n\n[10] Communication-Efficient Learning of Deep Networks from Decentralized Data (McMahan et al., AISTATS 2017)\n\n**L2: Routing module may cause the risk of leaking client privacy distribution**\n\nA: With Flow, we aim to improve the performance of personalization in federated settings, by introducing a per-instance and dynamically personalized model. The interplay between personalization for higher accuracy and other techniques for better privacy guarantees is another interesting topic to explore which we leave to future work.\n"}, {"review_id": "cddaBvTIQG", "reviewer": "Reviewer_MbeB", "summary": "The paper proposes a per-instance and per-client personalization approach Flow that creates personalized models via dynamic routing to improve both the performance of the personalized model and the generalizability of the global model. Convergence analysis for both global and personalized models are provided. Empirical evaluation shows that Flow can achieve better performance in terms of generalization and personalized accuracy on several vision and language tasks in cross-device FL setting. ", "questions": "Q1: Why the routing model is designed as a fully connected network rather than a sequential model such as RNN? See W1.\n\nQ2: Whether the alternative training of the global parameters is effective? See W2.\n\nQ3: Theorem 4.1 and 4.2 are not the standard form of convergence because they do not show the global optima. \n", "limitations": "See W1-W2.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1: The paper provides two essential observations that limits the performance of existing personalized FL methods, which well motivates the proposal of training dynamic network to benefit from both the global model and the personalized model.\n\nS2: The basic idea behind Flow that improving the performance of the personalized model via dynamic routing is very intuitive. Theoretical analysis and experimental evaluation also show the effectiveness.\n\nS3: The experiments are well designed which not only show the superior performance of the proposed Flow against existing state-of-the-art personalized FL methods, but also give in-depth analysis of how the proposed dynamic routing strategy works.\n\nS4: The paper is well-written and very easy-to-follow.\n", "weaknesses": "W1: The routing module is not very intuitive to me. Why the model is designed as a fully connected network rather than a sequential model such as RNN? The authors should elaborate more on this issue.\n\nW2: The effectiveness of the alternative training for the global parameters (Equation 5) is not validated. More evaluations are needed.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1/Q1: Routing module being fully-connected network**\n\nA: Our first choice was a fully-connected network for the policy module because that would take the least amount of computation resources and time. Besides, we did not have any reasons to justify the use of RNNs to generate probabilities of using local or global layers given an input representation. It is because we are already using hidden states as intermediate representations for the policy modules for global models based on RNNs.\n\n**W2/Q2: Effectiveness of the alternative training of the global model**\n\nA: We experimented with three modes of training for the global model: (a) Global model trained first, then the policy module, (b) Policy module trained first, then the global model, (c) Global model and Policy module trained alternatively. The results are shown in Figure 3, in the PDF attached to the global response titled “Author Rebuttal by Authors”. We see that the alternate training results in a more stable training compared to the other two modes of training. These results are in conformance with other works [11, 12] which have also used alternative training for policy and model weights training. \n\n[11] DARTS: Differentiable Architecture Search (Liu et al., ICLR 2019)\n\n[12] Searching for A Robust Neural Architecture in Four GPU Hours (Dong et al., CVPR 2019)\n\n**Q3: Global optima in theorems**\n\nA: The theorems 4.1 and 4.2 are for non-convex cases, where the standard form does not have the global optima [13]. The strong-convex and general-convex cases are covered in Appendix D, where Theorem D.9 (for the global model) and Theorem D.16 (for the personalized model) have the global optima. \n\n[13] SCAFFOLD: Stochastic Controlled Averaging for Federated Learning (Appendix D.2, Theorem V) (Karimireddy et al., ICML 2020)\n"}]

Author rebuttal:
We are attaching a one-page PDF containing more experiment results on 

Figure 1: Different dataset splits for trainings of local and global parameters

Figure 2: More runs on Stackoverflow dataset for Flow, on seeds {1, 2, 3, 4, 5, 6, 7, 8, 9}

Figure 3: Different training modes on EMNIST to showcase how alternate training of global and policy parameters result in more stable training

Figure 4: Ablation on Dynamic Routing Component for rest of the datasets

Figure 5: Convergence curves for all the datasets

Meta-review: In this paper, the authors proposes a new personalized federated learning method named Flow, which allows the output of each instance is dynamically determined by global or local model, which is new for pFL research. Some analysis and experiments demonstrate its advantage. To this end, I recommend accepting this submission.

However, I still have the concern about the additional cost, which may limit its application scope. This is also pointed by reviewers; although the authors discuss this one in the rebuttal, this concern is still there.

Please further improve this submission according to all the discussions between reviewers and the authors. Hope they find the discussion useful and make this submission a better one.
Decision: Accept (poster)