Adaptive Personalized Federated Learning
Authors: Yuyang Deng
Mohammad Mahdi Kamani
Mehrdad Mahdavi
Venue:  (2021)
Keywords: Federated learning
Personalization
Optimization

Abstract: Investigation of the degree of personalization in federated learning algorithms has shown that only maximizing the performance of the global model will confine the capacity of the local models to personalize. In this paper, we advocate an adaptive personalized federated learning (APFL) algorithm, where each client will train their local models while contributing to the global model.  We derive the generalization bound of mixture of local and global models, and find the optimal mixing parameter. We also  propose a  communication-efficient  optimization method to collaboratively learn the personalized models and analyze its convergence in both smooth strongly convex and nonconvex settings.  The extensive experiments demonstrate the effectiveness of our personalization schema, as well as the correctness of established generalization theories.


Under review as a conference paper at ICLR 2021
ADAPTIVE PERSONALIZED FEDERATED LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Investigation of the degree of personalization in federated learning algorithms has shown that only maximizing the performance of the global model will confine the capacity of the local models to personalize. In this paper, we advocate an adaptive personalized federated learning (APFL) algorithm, where each client will train their local models while contributing to the global model. We derive the gener- alization bound of mixture of local and global models, and find the optimal mix- ing parameter. We also propose communication-efficee to collaboratively learn the personalized models and analyze its convergence both smooth strongly convex and noncomvex settings. The extensive experiments demonstrate the effectiveness of our personalization schema, as well as the cor- rectness of established generalization theories.
optimization method
1 INTRODUCTION
With the massive amount of data generated by the proliferation of mobile devices and the internet of things (IoT), coupled with concerns over sharing private information, collaborative machine learning and the use of federated optimization (FO) is often crucial for the deployment of large-scale machine learning (McMahan et al., 2017; Kairouz et al., 2019; Li et al., 2020b). In FO, the ultimate goal is to learn global model that achieves uniformly good performance over almost all participating clients without sharing raw data. To achieve this goal, most of the existing methods pursue the following procedure learn a global model: (i) a subset of clients participating in the training is chosen at each round and receive the current copy of the global model; (ii) each chosen client updates the local version of the global model using its own local data, (iii the server aggregates over the obtained local models to update the global model, and this process continues until convergence (McMahan et al., 2017: Mohri et al., 2019; Karimireddy et al., 2019; Pillutla et al., 2019). Most notably, FedAvg by McMahan et al. (2017) uses averaging as its aggregation method over local models.
Due to inherent diversity among local data shards and highly non-IID distribution of the data across clients, Fe- dAvg hugely sensitive to its hyperparameters, and as a result, does not benefit from a favorable convergence guar- antee (Li et al., 2020c). In Karimireddy et al. (2019), au- thors argue that if these hyperparameters are not carefully tuned, it will result in the divergence of FedAvg, as local models may drift significantly from each other. Therefore, in the presence of statistical data heterogeneity, the global model might not generalize well on the local data of each client individually (Jiang et al., 2019). This is even more crucial in fairness-critical systems such as medical diagno- sis (Li & Wang, 2019). where poor performance on local clients could result in damaging consequences. This prob- lem is exacerbated even further as the diversity among lo- cal data of different clients is growing. To better illustrate MNIST dataset
Incrnaving Statisiical Hearogernity
Loos
Number of Classes Per Client
Modi SCATFOLD Seneaitatar)
aloul Hudld (Traki
Figure 1: Comparing the generaliza- tion and training losses of our proposed personalized model with the global models of FedAvg and SCAFFOLD by increasing the diversity among the data of clients on MNIST dataset with a lo- gistic regression model.
this fact, we ran a simple experiment where each client's local training data is sampled from subset of classes to simulate heterogeneity. Obviously, when each client has samples from less number of classes of training data, the heterogeneity among them will be high and if each of them has samples from all

---

Under review as a conference paper at ICLR 2021
classes, the distribution of their local training data becomes almost identical, and thus heterogeneity will be low. The results of this experiment are depicted in Figure 1, where the generalization and training losses of the global models of the FedAvg (McMahan et al., 2017) and SCAFFOLD (Karim- ireddy et al., 2019) on local data diverge when the diversity among different clients' data increases. This observation illustrates that solely optimizing for the global model's accuracy leads to poor generalization of local clients. To embrace statistical heterogeneity and mitigate the effect of nega- tive transfer, is necessary to integrate the personalization into learning instead of finding a single consensus predictor. This pluralistic solution for FO has recently resulted in significant research in personalized learning schemes (Eichner et al.. 2019; Smith al., 2017; Dinh et al., 2020; Mansour et al., 2020; Fallah et al., 2020; Li et al., 2020a).
To balance the trade-off between the benefit from collaboration with other users and the disadvan- tage from the statistical heterogeneity among different users' domains, in this paper, we propose an adaptive personalized federated learning (APFL. algorithm which aims to learn a personalized model for each device that is mixture of optimal local and global models. We theoretically analyze the generalization ability of the personalized model on local distributions, with dependency on mix- ing parameter, the divergence between local and global distributions, well as the number of local and global training data. To learn the personalized model, we propose a communication efficient optimization algorithm that adaptively learns the model by leveraging the relatedness between local and global models as learning proceeds. As it is shown in Figure 1, by progressively increasing the diversity, the personalized model found by the proposed algorithm demonstrates better gener- alization compared to the global models learned by FedAvg and SCAFFOLD. We supplement our theoretical findings with extensive corroborating experimental results that demonstrate the superior- ity of the proposed personalization schema over the global and localized models of commonly used federated learning algorithms.
PERSONALIZED FEDERATED LEARNING
In this section, we propose a personalization approach for federated learning and analyze its statis- tical properties. Following the statistical learning theory, in a federated learning setting each client has access to its own data distribution D; on domain =\t == X' x>,, where X' E IR is the input domain and y is the label domain. For any hypothesis h E H the loss function is defined as E HxE - R+ The true risk at local distribution is denoted by LD, (h) = E( g) [E (x)),, y)] We use L. (h) to denote the empirical risk of h on distribution D. We use D = (1/n) E 1 De to denote the average distribution over all clients.
2.1 PERSONALIZED MODEL
In a standard federated learning scenario, where the goal is to learn global model for all devices cooperatively. the learned global model obtained by minimizing the joint empirical distribution D, ie., min (h) by proper weighting. However, as alluded to before, a single consensus pre- dictor may not perfectly generalize local distributions when the heterogeneity among local data shards is high (i.e., the global and local optimal models drift significantly). Meanwhile, from the local user perspective, the key incentive to participate in "federated" learning is the desire seek reduction in the local generalization еттоr with the help of other users' data. In this case, the ideal situation would be that the user can utilize the information from the global model to compensate for the small number of local training data while minimizing the negative transfer induced by het- erogeneity among distributions. This motivates us to mix the global model and local model with a controllable weight as joint prediction model, namely, the personalized model.
Here we formally introduce our proposed adaptive personalized learning schema, where the goal is to find the optimal combination of the global and the local models, in order to achieve better client-specific model. this setting, global server still tries to train the global model by minimizing the empirical risk on the aggregated domain D, i.e., h = arg min (h),, while each user trains local model while partially incorporating the global model, with some mixing weight ag i.e., hipee arg mingeH (ash + (1 oz)āt). Finally, the personalized model for ith client is
2

---

Under review as a conference paper at ICLR 2021
convex combination of h" and Miness
ha, aghio + (1 a;)h",
is worth mentioning that, has is not necessarily the minimizer of empirical risk Ép, (-), because we optimize Moc, with partially incorporating the global model.
Example 1. Let us illustrate a simple situation where mixed model does not necessarily coincide with local ERM model. To this end, consider a setting where the hypothesis class H is the set of all vectors in R2, lying in &g unit ball: H. = { E R², : ||A||2 I 1}. Assume the local empirical minimizer is known to be [1,0]", and h = [1- 0]T, and a is set to be 0.5. Now, if we wish to find hioc. such that ha. a loc.i + (1- (1) h coincides with local empirical minimizer, we have to solve: 0.5 + 0.5 [-1,0] = [1,0]", subject to l|hll2 S 1. This equation has no feasible solution, implying that it is not necessarily true that h,, coincides with local empirical minimizen
In fact, in most cases, as we will show in the convergence of the proposed algorithm, ha, will incur residual risk if evaluated the training drawn from Dj.
2.2 GENERALIZATION GUARANTEES
We now characterize the generalization of the mixed model. We present the learning bounds for classification and regression tasks. For classification, we consider binary classification task, with squared hinge loss (((())) y) = (max (0, yh())))² In the regression task, we consider the MSE loss ((h(a)) y) (h(x:) - y)². Even though we present learning bounds under these two loss functions, our analysis can be generalized to any convex smooth loss. Before formally presenting the generalization bound, we introduce the following quantity measure the empirical complexity of a hypothesis class H over a training set S.
Definition 1. Let S be fixed set of samples and consider hypothesis class H. The worst case disagreement between a pair of models measured by absolute loss is quantified by: Az = SU (an)ees [h(x)) [x)).)
The empirical discrepancy characterizes the complexity of hypothesis class over some finite set. The similar concepts are also employed in the related multiple source PAC learning or domain adaption (Kifer et al., 2004; Mansour et al., 2009; Ben-David et al., 2010; Konstantinov al., 2020; Zhang et al., 2020).
We now state the main result on the generalization of the proposed personalization schema. The proof of the theorem is provided in Appendix D.
Theorem 1. Let hypothesis class H. be compact closed set with finite VC dimension Assume loss function E is Lipschitz continuous with constant G, and bounded in [0, B). Then with probability at least 1 there exists a constant C. such that the risk of the mixed model ha, ashioc. + +1 (1-a;)ir at)h" on the ith local distribution D, is bounded by:
d log(1/8)
LD, (hau) S 2at
(D.(h))+ +20
+ G)x(SS)
m,
(2)
[2D("')+ D,ll2 + +CV + 2(1 oz,
d log(1/5)
m
where mi 1.2..... is the number of training data at ith user, m = m, +... my is the total number of all data, S: to be the local training set drawn from D; I Dilli P P(a.y)>D, Idwdy, is the difference between distributions D and D., and hū = arg minsER CD,(h), Remark 1. We note that very analogous work to ours is Mansour et al. (2020), where a gen- eralization bound provided for mixing global and local models. However. their bound does not depend on a, and hence we cannot see how it impacts the generalization ability.
.,.
In Theorem 1, by omitting constant terms, mainly depends on three key quantities: i) m: the number of global data drawn from D. ii) diver- gence between distributions D and D;, and iii) my: the amount of local data drawn from D.. Usually,
observe that the generalization risk of has on D
3

---

Under review as a conference paper at ICLR 2021
the first quantity m, the amount of global data is fairly large compared to individual users, so global model usually has a better generalization. The second quantity characterizes the data heterogeneity between the average distribution and ith local distribution. If this divergence is too high, then the global model may hurt the local generalization. For the third quantity, as amount of local data m, is often small, the generalization performance of local model can be poor.
Optimal mixing parameter. We can also find the optimal mixing parameter of that minimizes generalization bound in Theorem 1. Notice that the RHS of (2) is quadratic in so it admits a minimum value at
(Ep(1t)+ + BII - Dilli + +OV
af (co(h+) BID Dill1 + C..
d+log(1/8) m
+ CD. (h;) 2C
(4-log(1/0) + GA
mi
The optimal mixture parameter is strictly bounded in [0, 11, which matches our intuition. If the divergence term is large, then the value becomes close to I, which implies if local distribution drifts too much from average distribution, it is preferable to take more local models. If my is small, this value will be negligible, indicating that we need to mix more of the global model into the personalized model. Conversely, if m; large, then this term will be again roughly which means taking the majority of local model will give the desired generalization performance.
3 OPTIMIZATION METHOD
To optimize the learning problem we cast the previous section, here we propose a communication efficient adaptive algorithm to learn the personalized local models and the global model. To do so, we let every hypothesis
the hypothesis space H to be parameterized by a vector w E W C Rd where W is some convex closed set and denote the empirical risk at ith device by local objective function f:(w). Adaptive personalized federated learning can be formulated as a two-phase opti- mization problem: globally update the shared model, and locally update users' local models. Similar to FedAvg algorithm, the server will solve the following optimization problem:
F(w) = 1 n Σ (f((w) := E Eg, [fr (ux, 6.11
min WEW
where ft(.) is the local objective at ith client, & a minibatch of data in data shard at ith client, and is the total number of clients. Motivated by the trade-off between the global model and local model generalization errors in Theorem I, we need to learn a personalized model as in (I) to optimize the local empirical risk. To this end, each client needs to solve this optimization over its local data:
min (a. + (1 -o))w", vEW
44)
where wt* arg min F(w) is the optimal global model. The balance between these two models is governed by a parameter Og, which is associated with the diversity of the local model and the global model. We first state the algorithm for a pre-defined proper ag, and then propose adaptive schema to learn this parameter as learning proceeds.
Remark 2. As mentioned in Section 2.1, when the hypothesis class is bounded, the mixed model will not coincide with local ERM model. However, if the class is unbounded, the mixed model will eventually converge local ERM model, which means the personalization fails. Hence, make sure the correctness of our algorithm, we need to require the parameter comes from some bounded domain W
Local Descent APFL. To efficiently optimize the problem we cast in (3) and (4), in this subsection propose our bilevel optimization algorithm, Local Descent APFL. At each communication round, server uniformly random selects K clients as a set U.. Each selected client will maintain three
models at iteration t: local version of the global model wh! its own local model o ( and the mixed personalized model b(.) = v + (1 - a, ww (") Then, selected clients will perform the following updates locally on their own data for iterations:
w (8)
II W
nh f. (w:" ( :4)
II W
v (t-1)
no Vofi (o.-"); (5)
w
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Local Descent APFL,
input: Mixture weights 01, ,nn Synchronization gap 7.
for t = 0,-.. ....... . do
parallel for E U2 do
if not divides then
w IIw
w (1((-1) 1/1 V/: u0,-0
1),
IIw
V [t-1] -7 V.fi
! (1(11),
(t)
+ - ar)w (t) Ut + UL-1
else
each selected client sends w; to the server
w (+)
1 Ejeu, w.
[U.]
server uniformly samples subset U, of K clients. server broadcast w(() to all chosen clients
end end end
where fi (.:E) denotes the stochastic gradient of f(.) evaluated at mini-batch ç. Then, using the updated version of the global model and the local model, we update the personalized model a as well. The clients that are not selected in this round will keep their previous step local modeln
o (t-1) After these local updates, selected clients will send their local version of the global model w to the server for aggregation by averaging: (t = Th Σjeu, w0)" Then the server will choose another set of K clients for the next round of training and broadcast this new model to them.
Adaptively updating a. Even though in Section 2.2, we give the information theoretically optimal mixing parameter, in practice we usually do not know the distance between user's distribution and the average distribution. Thus, finding the optimal a is infeasible. However, we can infer it empiri- cally during optimization. Based on the local objective defined in (4), the empirical optimum value of a for each client can be found by solving of arg min, [o fa (a.v + (1 - a; a)),,, where we can use the gradient descent to optimize it at every communication round, using the following step:
(0) a -((11)1 V.Ji
:t) = a ((-1) T). (o (1 (1-1)
w
V (1- (00-")=5) (6)
which shows that the mixing coefficient a is updated based on the correlation between the differ- ence of the personalized and the local version of global models, and the gradient at the in-device personalized model. Meaning, when the global model is drifting from the personalized model, the value changes to adjust the balance between local data and shared knowledge among all devices captured by the global model.
CONVERGENCE ANALYSIS
In this section provide the convergence analysis of Local Descent APFL with fixed o; for strongly convex and nonconvex functions. To have a tight analysis, as well as putting the opti- mization results in the context of generalization bounds discussed above, we define the following parameterization-nnve -nvvariannn quantities that only depend on the distributions of local data across clients and the geometry of loss functions.
Definition 2. We define the following quantity measure the diversity among local gradients with respect to the gradient of the ith client: G = supwERs [V V (:()]] (Woodworth et al., 2020a). We also define the sum of gradient diversities of n clients as: Ç Emss.
Definition 3.
We define A = =|2 -|o:-=" wwwww" [|2 where o = arg min f((v), and wv = arg min F(w)
to measure the gap between optimal local model and optimal global model.
We also need the following standard assumption on the stochastic gradients local objectives.
5

---

Under review as a conference paper at ICLR 2021
Assumption 1 (Bounded Variance), The variance of stochastic gradients computed at each local data shard is bounded, i... Vi E f V(())) s
Strongly Convex Loss. We now turn to establishing the convergence of local descent APFL on smooth strongly convex functions. Specifically, the following theorem characterizes the convergence of the personalized local model to the optimal local model. The proof is provided Appendix E.2.3.
Theorem 2. Assume each client's 's objective function is p-strongly convex and L-smooth, and satis- fies Assumption 1. Also let K. = L/ b = min { K
n 2.) Using Algorithm 1, by choosing the mixing 4v6K, / ). learning rate: T)
weight a; 2 max 4vo6'
16 where a = mmax (128k,, T }
"((4aj''
and using average scheme Ú; = 1 Ei= Po(aro) a1)-ait K ESEU, wf)) where Ps = (t+a)? ST
ST = - Pt, and letting Jí to denote the local minimum of the ith client, then the following con- vergence rate holds for all clients i E [m]]
[[f(((]] - f S a20
( pubT)
+ - (1-az)²0
R²002
+
1²T (TG (T(
S S pb
+ kLdi
HubKT
JuTT
If we choose T= /T/K, then: B[f((0.)] - ff S a70
o² uT + (1 (1=0))30
""""trrrett &
+ )
+11 a;)²0
(itt P
+ RLA.).
KKT
A few remarks about the convergence of personalized local model are in place: (1) If we set a; = 1, then we recover O (2) convergence rate of single machine SGD. If we only focus on the terms with (1 - oz)², which contributed by the global model's convergence, and omit the residual error, we achieve the convergence rate of ((1/KT) using only VKT communication, which matches with the convergence rate of vanilla local SGD (Stich, 2018; Woodworth et al., 2020a), and (2) The residual error is related to the gradient diversity S and local-global optimality gap A, It shows that taking any proportion of the global model will result in sub-optimal ERM model. As we diseussed in Section 2.1, ha, will not be the empirical risk minimizer in most cases. Also, we assume that o; needs to be larger than some value in order get a tight rate. This condition can be alleviated, but the residual еπтоr will be looser. The analysis of this relaxation is presented in Appendix F.
Nonconvex Loss. The following theorem establish the convergence rate of personalized model leamed by APFL for nonconvex smooth loss functions. The proof is provided in Appendix G.3.
(11-a;) as) EjEU, w If each client's 's objective function is L-smooth and domain W be bounded by Dw that is, Yw, w' E W, ||w - w'll² < Dw. Using Algorithm I with full gradient, by choosing K n and learning rate 1] 2VELVT' we have
Theorem 3. Let o!!) a,o + (1-
V)((o/9) 50
L
+ (1
aai)?
L VT)
+ +11
11-aah at)² (Gi L2
74S
T2G
(-26)
+ of - a;)²0
nT2
+
+T
+ (1 - a;)²0
(1-a;)²0
nT
By choosing T = 11/4T1/ it holds that:
1 T
VA.C || 0
1 VT
+ (1 - ai)3
-1-aa))00
1
VnT + (1 (1- +1-a3)² (c+ + L2'w))
+
VT
Here we show that APFL will converge to stationary point on nonconvex function with sublinear rate plus some residual error, with n/3/133/1 communication rounds. The rate with factor (1
a.)² is contributed from the global model convergence, and here we have some additive residual eиror reflected by & and Dw. Compared to most related work by Haddadpour & Mahdavi (2019) regarding the convergence of local SGD on nonconvex functions, they obtain O(1/VnT), while we only have speedup in n partial terms. This could be solved by using different learning rate for local and global update. Additionally, we assume K = n to derive the convergence in nonconvex setting, and leave the analysis for partial participation future work.

---

Under review as a conference paper at ICLR 2021
19.2
(a) Non HDD classes per client)
(b) Nos (4 classes clicat)
(c) IID distribution clients
APFL (a - 0.26]
APFL (a 0.75)
Localized FedAAg
Localized SCAFFOLD
APRL 0.5)
APFL (a 1.0)
Global FadAug
Global SCAFFOLD
Figure 2: Comparing the the performance of APFL with FedAvg (APFL with a = 0) and SCAF- FOLD on the MNIST dataset. Top is the training loss and the bottom row is the generalization accuracy on training and validation data, respectively. In (a), the accuracy lines of SCAFFOLD and FedAvg global models removed since their low values degrade the readability of the plot.
EXPERIMENTS
In this section, we empirically show the effectiveness of the proposed algorithm in personalized federated learning. Due to lack of space, some experimental results are deferred to Appendix B.
Experimental setup. We our experiments on Microsoft Azure systems, using Azure MIL API. The code is developed on Py Torch (Paszke et al., 2019) using its "distributed" API with MPI. We de- ploy this code on Standard F64s family of VMs Azure. We use four datasets for our experiments, MNIST, CIFAR1O (Krizhevsky et al., 2009), EMNIST (Cohen et al., 2017), and synthetic dataset. For more information on datasets used the following experiments refer Appendix B. For all the experiments, we have 100 users (except for EMNIST dataset), each of which has access to its own data only. The local dataset randomly divided into 80% for training and 20% for validation, which is the standard way to examine the local models for personalized use cases. For the learning rate, we use the linear decay structure with respect to local steps, suggested by Bottou (2012). At each iteration the learning rate is decreased by 1%, unless otherwise stated. We report the perfor- mance over training data for optimization error and local validation data (from the same distribution training data for each client) for the generalization accuracy. Throughout these experiments report the results for the following three models:
Global Model: Referring to the global model of FedAvg or SCAFFOLD.
Localized Global Model: Referring to the fine-tuned version of the global model at each round of communication after 5 steps of local SGD. Here, we have either the localized FedAvg or the localized SCAFFOLD. The reported results are for the average of the performance over all the local models on each online client. In all the experiments T 10, unless otherwise stated.
Personalized Model: This model is the personalized model produced by our proposed algorithm APFL. The reported results the average of the respective performance of personalized models over all online clients at each round of communication.
Strongly convex loss. First, we run a set experiments on the MNIST dataset, with different levels of non-lIDness by assigning certain number of classes to each client. We use logistic regression with parameter regularization as our strongly convex loss function. In this part, all clients are online for each round, however, the results when client sampling involved is diseussed in Appendix B.2. We compare the personalized model of APFL with different rates of personalization as a with global and localized models of FedAvg and SCAFFOLD, well their global models. The initial learning

---

Under review as a conference paper at ICLR 2021
18
Sy 541
bystoee Prereder
SythectLE LX) Duee abbe
Voscotion Nouureee
20
40
60
80
100
Manter
Number Communiation Iooudd
Figure 3: Comparing the APFL, with adaptive a and the localized FedAvg. The left figure is the
training performance, and the right one is the accuracy of these models on local validation data.
rate is set to 0.1 and it decaying as mentioned before. The results of running this experiment on 100 clients and after 100 rounds of communication are depicted in Figure 2, where we move from highly non-IID data distribution (left) to IID data distribution (right). As it can be seen, global mod- els learned by FedAvg and SCAFFOLD have high local training losses. On the other hand, taking more proportion of the local model in the personalized model (namely, increasing a) will result in the lower training losses. For generalization ability, the best performance is given by personalized model with a = 0.25 in both (a) and (b) cases, which outperforms the global (FedAvg and SCAF- FOLD) and their localized versions. However, as we move toward IID distribution, the advantage of personalization vanishes as expected. Hence, as expected by the theoretical findings, we can benefit from personalization the most when there is statistical heterogeneity between the data of different clients. When the data are distributed IID, local models of FedAvg or SCAFFOLD are preferable.
An interesting observation from the results in Figure 2, which is inline with our theoretical findings is the relationship of a with both optimization and generalization losses. As it can be seen from the first row, a has linear relationship with the optimization loss, that is, with smaller a, training loss is getting closer to the global model of FedAvg in terms of optimization loss, which matches with our convergence theory. However, from the second row, it can be inferred that there is no linear relationship between and generalization. In fact, according to (2), we know that generalization bound is quadratic in a, and hence, the generalization performance does not simply increase or decrease monotonically with
Adaptive a update. In this part, we want to show how adaptively learning the value of a across different clients, based on (6), will affect the training and generalization performance of APFL's personalized models. We use the three synthetic datasets as described in Appendix B. with logistic regression as the loss function. We set the initial value of ai 0.01 for every i E [n]. The results of this training are depicted in Figure 3, where both optimization and generalization of the learned models are compared. As it can be inferred, in training. APFL outperforms FedAvg in the same datasets. More interestingly, in generalization of learned APFL personalized models, all datasets achieve almost the same performance as result of adaptively updating a values, while the FedAvg algorithm has a huge gap with them. This shows that, when we do not know the degree of diversity among data of different clients, we should adaptively update a values to guarantee the best generalization performance. We also have results on EMNIST dataset with adaptive tuning of a in Appendix B.2, wih 2-layer MLP.
Nonconvex loss. To showcase the results for nonconvex loss, we use CIFARIO dataset that is dis- tributed in a non-IID way with classes per client. We apply layers, followed by 2 fully connected layers, using cross entropy as the loss function. The initial learning rates of APFL and FedAvg algorithms are set to 0.1 with the mentioned decay structure, while for SCAFFOLD this value is 0.05 with 5% decay per iteration to avoid divergence. As it can be inferred from the results in Table 1, the personalized model learned by APFL outperforms the lo- calized models of FedAvg and SCAFFOLD, as well as their global models, in both optimization and generalization. In this case adaptively tuning the a achieves the best training loss, while a = 0.25 case reaching the best generalization performance.
CNN model with convolution
Comparison with other personalization methods. We now compare our proposed APFL with two recent approaches for personalization in federated learning. In addition to FedAvg, compare with perFedAvg introduced in Fallah et al. (2020) using a meta-learning approach, and pFedMe
8

---

Under review as a conference paper at ICLR 2021
XPPL
FedAvg
SCAFFOLD
0:25
0.5
= 0.75
Adaptive
Global Model
Localized Model
Global Model
Localized Model
0.154
0.113+
0.103
0.101=
1,789
0.3894
1.70+
0.583
Training Loss
0.003
0.008
0.007
0.013
0.001
0.005
0.001
0.012
89 33%
68.74%
89.00%
88.67%
32.51%
83.16%
37.16%
85, 25%
Validation Accuracy
0.26%
0.14%
0.22%
0.51%
0.47%
0.37%
0.3%
0.2%
Table 1: The results of training CNN model on CIFARIO dataset using different algorithms.
introduced in Dinh et al. (2020) using a regularization with Moreau envelope function. We run these algorithms train an MLP with 2 hidden layers, each with 200 neurons, on a non-IID MNIST dataset with 2 classes per client. For perFedAvg, similar to their setting, we use learning rates of = 0.01 (different from the a in our APFL) and 0.001. To have fair comparison, we use the same validation for perFedAvg and we use 10% of training data the test dataset that updates the meta-model. For pFedMe, following their setting, we use À 15, = 0.01. We use T = 20 with total number of communications to 100 and the batch size is 20. The results of these experiments are presented in Table 2, where APFL clearly outperforms all other models in both training and generalization. The APFL model with adaptive o has the best validation accuracy. perfedAvg is slightly better than the localized FedAvg, however, it worse than APFL models. pFedMe performs better than the global model of FedAvg. but it cannot surpass neither the localized model of FedAvg nor APFL models.
0.75 has the lowest training loss, and the one with
FodAvy
perFedAvg Personalized Model
pFodMe Personalized Model
0:25
0.5
0.75
Adaptive
Global Model
Localized Model
Training Loss
0.011
0.0012
0.002
0.00L2
0,240
0.011
0.0000
0.182
0.0007
0.0001
0.0001
0.0008
0.006
0.002
0,002
0,004
Validation Accurncy
+8.07%
98.04%
97.96%
98. 10%%
98.8155
97.76%5
97.8 07.83%
95.92%
0,10%
0.08%
0.09%
0.10%
0.29%
0.13%
0.12%
0.1%
Table 2: The results of training an MLP on MNIST dataset with different personalization methods.
6 CONCLUSIONS
In this paper, we proposed an adaptive federated learning algorithm that learns mixture of local and global models as the personalized model. Motivated by learning theory in domain adaptation, provided generalization guarantees for our algorithm that demonstrated the dependence the diversity between each clients' data distribution and the representative sample of the overall distri- bution of data, and the number of per-device samples key factors in personalization. Moreover, we proposed a communication-reduee analyzed its convergence rate for both smooth strongly convex and nonconvex functions. Finally, we empirically backed up our theoretical results by conducting experiments in a federated setting.
optimization algorithm to learn the personalized models and
REFERENCES
Inés Almeida and Joao Xavier. Djam: distributed jacobi asynchronous method for learning personal models. IEEE Signal Processing Letters, 25(9): 2018. 13
Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary. Fed- crated learning with personalization layers. arXiv preprint arXiv: 191::1012.0088 2019. 14
Aurélien Bellet, Rachid Guerraoui, Mahsa Taziki, and Mare Tommasi, Personalized and private peer-to-peer machine learning. arXiv preprint arXiv: 2017. 13
Shai David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine learning, 151--2) 2010. 3, 14, 22
Léon Bottou. Stochastic gradient descent tricks. In Neural networks: Tricks of the trade, pp. 421- 436. Springer, 2012.7 7
Sebastian Caldas, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv: 1rXi::8122.0199) 2018. 15, 16

---

Under review as a conference paper at ICLR 2021
Gregory Cohen, Saced Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 International Joint Conference on Neural Networks (LJCNN), pp- 2921-2926 IEEE, 2017.
Canh T Dinh, Nguyen H Tran, and Tuan Dung Nguyen. Personalized federated learning with moreau envelopes. arXiv preprint (rXiv:2006.08845, 2020. 2, 9, 14
Hubert Eichner, Tomer Koren, Brendan Memahan, Nathan Srebro, and Kunal Talwar. Semi-cyclic stochastic gradient descent. In International Conference Machine Learning, pp. 1764 1773, 2019. 2
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta- learning approach. arXiv preprint arXiv:2002.0794h 2020. 2, 8, 14
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta- veta-learning for fast adaptation of deep networks. In ICML, pp. 1126-1135. JMLR. org, 2017. 13, 14, 18
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation meth- ods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2): 267-305, 2016. 41
Farzin Haddadpour and Mchrdad Mahdavi. On the convergence of local descent methods feder- ated learning. arXiv preprint arXiv: 14425, 2019. 6
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Lo- cal sgd with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, pp. 11080-1 1092, 2019a. 15
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Trading redundancy for communication: Speeding up distributed sgd for non-convex optimization. In International Conference Machine Learning, pp. 2545-2554, 2019b. 15
Filip Hanzely and Peter Richtárik. Federated learning of mixture of global and local models. arXiv preprint arXiv:2002.055 2020. 14
Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint 18X /0/1://////30000 1.03604, 2018. 14
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint 1909::/909.0000 9099006335, 2019. 16
Yutao Huang, Lingyang Chu, Zirui Zhou, Lanjun Wang, Jiangchuan Liu, Jian Pei, and Yong Zhang. Personalized federated learning: An attentive collaboration approach. arXiv preprint arXiv:2007.03799. 2020. 14
Yihan Jiang, Jakub Konečný, Keith Rush, and Sreeram Kannan. Improving federated learning per- sonalization via model agnostic meta learning. arXiv preprint arXiv:/909, 10999999.2444.. /2488, 2019. 1, 14
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, 7achary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. arXiv preprint
2019. 1, 13, 14, 15
Sai Praneeth Karimireddy. Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for on-device federated learn- ing. arXiv preprint 1910.66 2019. 1,2
Mikhail Khodak, Maria-Florine Balcan, and Ameet S Talwalkar. Adaptive gradient-basee based meta- learning methods. In Advances in Neural Information Processing Systems, pp. 5915-5926, 2019.
14
Daniel Kifer, Shai Ben-David, and Johannes Gehrke. Detecting change in data streams. 2004.
Nikola Konstantinov, Elias Frantar, Dan Alistarh, and Christoph H Lampert. On the sample com- plexity of adversarial multi-source pac learning. arXiv preprint arXiv:2002. 10384, 2020. 3
10

---

Under review as a conference paper at ICLR 2021
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009. 7
Ang Li, Jingwei Sun, Binghui Wang, Lin Duan, Sicheng Li, Yiran Chen, and Hai Li. Lotteryfl: federated learning with lottery ticket hypothesis on
Personalized and communication-efice non-iid datasets. arXiv preprint arXiv:2008. 00:::000880337,,, 2020a. 2
Daliang Li and Jumpu Wang. Fedmd: Heterogenous federated learning via model distillation. arXiv preprint drXiv:1910.03581, 2019.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith.
Federated optimization in heterogeneous networks. arXiv preprint arXiv:1812.06122 2018. 15
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50 60, 2020b. 1
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Feddane: A federated newton-type method. arXiv preprint arXiv:2001.01900 2020c.
Paul Pu Liang, Terrance Liu, Liu Ziyin, Ruslan Salakhutdinov, and Louis- Louis-Philippe Morency. Think locally, act globally: Federated learning with local and global representations. arXiv preprint arXiv:2001.01523, 2020. 14
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. arXiv preprint arXiv:0902.3430, 2009. 3, 14, 22
Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications to federated learning. arXiv preprint arXiv:2002. 2020.
2, 3, 14
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-fficiennt learning of deep networks from decentralized data. In AISTAT, pp. 1273-1282, 2017.
14, 15
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018. 18, 21
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. arXiv preprint arXiv:1902.00146, 2019. 1, 15, 19
Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv preprint
2018. 13, 14
Sinno Jialin Pan and Qiang Yang. A survey on transfer learning. IEEE Transactions on knowledge and data engineering, 22(10):1345-1355 2009. 14
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. In NeurIPS, pp. 8024-8035, 2019.
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. arXiv preprini arXiv: 1912::1912..44./ 2019.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory algo-
rithms. Cambridge university press, 2014. 18, 21
Tao Shen, Jie Zhang, Xinkang Jia, Fengda Zhang, Gang Huang, Pan Zhou, Fei Wu, and Chao Wu. Federated mutual learning. arXiv preprint 160.:2000..6755, 2020. 14
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi-task learning. Advances in Neural Information Processing Systems, pp. 4424 4434, 2017. 2, 14
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint
arXiv: met.. 2018. 6, 15,

---

Under review as a conference paper at ICLR 2021
Paul Vanhaesebrouck, Aurélien Bellet, and Mare Tommasi. Decentralized collaborative learning of personalized models over networks. 2017. 13
Kangkang Wang, Rajiv Mathews, Chloé Kiddon, Hubert Eichner, Françoise Beaufays, and Daniel Ramage. Federated evaluation of on-device personalization. arXiv preprint arXiv:1910.1023 2019. 14
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch local sgd for heteroge- neous distributed learning. arXiv preprint arXiv:2006.047: 04735, 2020a. 5, 22, 24, 32, 33
Blake Woodworth, Kumar Kshitij Patel. Sebastian U Stich, Zhen Dai, Brian Bullins, H Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? arXiv preprint arXiv:2002.078.3, 2020b. 15
Tao Yu, Eugene Bagdasaryan, and Vitaly Shmatikov. Salvaging federated learning by local adapta- tion. arXiv preprint arXiv:2002.04758. 2020. 13
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Trong Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. arXiv preprint arXiv: /2022, 2019. 16
Valentina Zantedeschi, Aurélien Bellet, and Mare Tommasi. Fully decentralized joint learning of personalized models and collaboration graphs. 2019. 13
Yuchen Zhang, Mingsheng Long, Jianmin Wang, and Michael I Jordan. On localized discrepancy for domain adaptation. arXiv preprint arXiv:2008.0624 2020. 3, 22
12

---

Under review as a conference paper at ICLR 2021
SUPPLEMENTARY MATERIAL: ADAPTIVE PERSONALIZED FEDERATED LEARNING
TABLE OF CONTENTS
Additional Related Work
13
Additional Experimental Results
15
B.1 Datasets
15
B.2
Additional Results
16
Discussions and Extensions
17
Proof of Generalization Bound
20
Proof of Convergence Rate in Convex Setting
22
E.1
Proof without Sampling
23
E.1.1
Proof of Useful Lemmas
24
E.1.2
Proof of Theorem 4
27
E.1.3
Proof of Theorem
27
E.2
Proof of Convergence of APFL with Sampling
San._in.........................
31
E.2.1
Proof of Useful Lemmas
32
E.2.2
Proof of Theorem
................................
E.2.3
Proof of Theorem 2
35
F Convergence Rate without Assumption on
38
G Proof of Convergence Rate in Nonconvex Setting
40
G.1 Proof of Technical Lemmas
40
G.2 Proof of Theorem 8
46
G.3 Proof of Theorem
46
A ADDITIONAL RELATED WORK
The number of research in federated learning is proliferating during the past few years. In federated learning, the main objective is to learn global model that is good enough for yet to be seen data and has fast convergence to local optimum. This indicates that there are several uncanny resem- blances between federated learning and meta-learnig approaches (Finn et al., 2017; Nichol et al., 2018). However, despite this similarity, meta-learning approaches mainly trying learn mul- tiple models, personalized for each new task, whereas in most federated learning approaches, the main foeus is the single global model. As discussed by Kairouz al. (2019), the gap between the performance of global and personalized models shows the crucial importance of personalization in federated learning. Several different approaches marily focusing on optimization eтror, while the main challenge with personalization is during the inference time. Some of these works on the personalization of models a decentralized setting can be found in Vanhaesebrouck et al. (2017); Almeida & Xavier (2018), where in addition to the opti- mization error, they have network constraints or peer-to-peer communication limitation (Bellet al., 2017; Zantedeschi et al., 2019). In general, as discussed by Kairouz et al. (2019), there are three significant categories personalization methods in federated learning, namely, local fine-tuning, multi-task learning, and contextualization. Yu et al. (2020) argue that the global model learned by federated learning, especially with having differential privacy and robust learning objectives, can hurt the performance of many clients. They indicate that those clients obtain better model by using only their own data. Hence, they empirically show that using these three approaches can boost the performance of those clients. In addition to these three, there is also another category that fits the most to our proposed approach, which is mixing the global and local models.
trying to personalize the global model, pri-
13

---

Under review as a conference paper at ICLR 2021
Local fine-tuning: The dominant approach for personalization is local fine-tuning, where each client receives a global model and tune it using its own local data and several gradient descent steps. This approach is predominantly used in meta-learning methods such as MAML by Finn et al. (2017) or domain adaptation and transfer learning (Ben-David et al., 2010; Mansour et al., 2009; Pan & Yang, 2009). Jiang et al. (2019) discuss the similarity between federated learning and meta-lcarning approaches, notably the Reptile algorithm by Nichol et al. (2018) and FedAvg, and combine them personalize local models. They observed that federated learning with a single objective of performance of the global model could limit the capacity of the learned model for personalization. In Khodak et al. (2019), authors using online convex optimization introduce a meta-learning approach that can be used in federated learning for better personalization. Fallah et al. (2020) borrow ideas from MAML to learn personalized models for each client with convergence guarantees. Similar to fine-tuning, they update the local models with several gradient steps, but they use second-order information to update the global model, like MAML. Another approach adopted for deep neural networks is introduced by Arivazhagan et al. (2019), where they freeze the base layers and only change the last "personalized" layer for each client locally. The main drawback of local fine-tuning is that it minimizes the optimization error, whereas the more important part is the generalization performance of the personalized model. In this setting, the personalized model is pruned overfit.
Multi-task learning: Another view of the personalization problem is to see it as a multi-task learning problem similar to Smith et al. (2017). In this setting, optimization considered as a new task; hence, the approaches of multi-task learning can be applied. One other approach, discussed as an open problem in Kairouz et al. (2019), is to cluster groups of clients based on some features such as region, as similar tasks, similar to one approach proposed by Mansour al. (2020).
each client can be
An important application of personalization in federated learning is using the model under different contexts. For instance, in the next character recognition task in Hard et al. (2018), based on the context of the use case, the results should be different. Hence, we need a personalized model on one client under different contexts. This requires access to more features about the context during the training. Evaluation of the personalized model in such a setting has been investigated by Wang et al. (2019), which in line with our approach in experimental results in Section 5. Liang et al. (2020) propose to directly learn the feature representation locally, and train the discriminator globally, which reduces the effect of data beterogeneity and ensures the fair learning.
Contextualization:
Personalization via model regularization: Another significant trial for personalization is model regularization. There are several studies to introduce different personalization approaches for feder- ated learning by regularize the difference between the global and local models. Hanzely & Richtárik (2020) try to introduce a new formulation for federated learning where they add the regulariza- tion term on the distance of local and global models. In their effort, they use a mixing parameter, which controls the degree of optimization for both local models and the global model. The Fe- dAvg (McMahan et al., 2017) can be considered a special case of this approach. They show that the learned model is in the convex haul of both local and global models, and at each iteration, depend on the local models' optimization parameters, the global model is getting closer to the global model learned by FedAvg. Similarly, Huang et al. (2020) and Dinh et al. (2020) also propose to use the reg- ularization between local and global model, to realize the personalized learning. Shen et al. (2020) propose a knowledge distillation way to achieve personalization, where they apply the regularization on the predictions between local model and global model.
Personalization via model interpolation: Parallel to our work, there are other studies to introduce different personalization approaches for federated learning by mixing the global and local models. The closest approach for personalization to our proposal introduced by Mansour et al. (2020). In fact, they propose three different approaches for personalization with generalization guarantees, namely, client clustering, data interpolation, and model interpolation. Out of these three, the first two approaches need some meta-features from all clients that makes them not a feasible approach for federated learning, due to privacy concerns. The third schema, which is the most promising one in practice as well, has close formulation to ours in the interpolation of the local and global models. However, in their theory, the generalization bound does not demonstrate the advantage of mixing models, but in our analysis, we show how the model mixing can impact the generalization
14

---

Under review as a conference paper at ICLR 2021
bound, by presenting its dependency on the mixture parameter, data diversity and optimal models on local and global distributions.
Beyond different techniques for personalization in federated learning, Kairouz al. (2019) ask an essential question of "when a global FL-trained model better?", or as we can ask, when is per- sonalization better? The answer these questions mostly depends on the distribution of data across clients. As we theoretically prove and empirically verify in this paper, when the data is distributed IID, we cannot benefit from personalization, and it is similar the local SGD scenario (Stich, 2018; Haddadpour et al., 2019a;b; Woodworth et al., 2020b). However, when the data is non-llD across clients, which is mostly the case in federated learning, personalization can help to balance between shared and local knowledge. Then, the question becomes, what degree of personalization is best for each client? While this was an open problem Mohri et al. (2019) on how to appropriately mix the global and local model, we answer this question by adaptively tuning the degree of personaliza- tion for each client, as discussed in Section 3, so can perfectly become agnostic to the local data distributions.
B ADDITIONAL EXPERIMENTAN RESULTS
In this section, we present additional experimental results to demonstrate the efficacy of the proposed APFL algorithm. First, we describe different datasets we have used in this paper, and then, present additional results.
B. DATASETS
For the experiments we use 4 different data sources as follows:
MNIST and CIFARIO For the MNIST and CIFAR1O datasets to be similar to the setting in fed- crated learning, we need manually distribute them in a non-IID way, hence the data distribution is pathologically heterogencous. To this end, we follow the steps used by McMahan et al. (2017), where they partitioned the dataset based on labels and for each client draw samples from some lim- ited number of classes. We use the same way to create 3 datasets for the MNIST, that are, MNIST non-IID with 2 classes per client, MNIST non-IID with 4 classes per client, and MNIST IID, where the data is distributed uniformly random across different clients. Also, we create non-lID CIFARIO dataset, where each client has access to only 2 classes of data.
EMNIST In addition pathological heterogeneous data distributions, applied our algorithm on a real-world heterogeneous dataset, which is an extension to MNIST dataset. The EMNIST dataset includes images of characters divided by authors, where each author has different style, make their distributions different Caldas et al. (2018). We use only digit characters and 1000 authors' data to train our models on.
Synthetic For generating the synthetic dataset, follow the procedure used by Li et al. (2018), where they use two parameters, say synthet (nt,,,))))) 8). that control how much the local model and the local dataset of each client differ from that of other clients, respectively. Using these parameters, we want to control the diversity between data and model of different clients. The procedure is that for each client we generate weight matrix W; E mm and bias b RR where the output for the ith client is yı arg max (a (W. x; + +)). where o()) is the softmax. In this setting, the input data T; E T has m features and the output can have e different values indicating number classes. Gaussian distribution W; N' (H,, 1) and b ./ (14, 1), where μ. ~ N (0, 7). The input is drown from a Gaussian distribution x; ~ N (v., Σ), where v; N (V, 1) and Vi ~ V (0, Also the variance Σ is a diagonal matrix with value of Σx. generate three different datasets, namely s wentteetc(O.... 0.0),
The model is generated based
1.2, Using this procedure, synthet t i < (0.5, 0.5), and synthetic 1.0), where we move from an IID dataset to a highly non-IIID data.
15

---

Under review as a conference paper at ICLR 2021
Lodda
Busten Ranih
Ht
17.0
Dorm ald
500
160
604
Nomber Conmantorden
Marber Commurozion foands
Commaniozin
(a) 0.25
(b) 0.5
(c) a 0.75
Figure 4: Evaluating the effect of sampling on APFL and FedAvg algorithm using the MNIST dataset that is non-IID with only 2 classes per client with logistic regression the loss. The first row is training performance on the local model of FedAvg and personalized model of APFL with different sampling rates from {0.3, 0.5, 0.7). The second row is the generalization performance of models on local validation data, aggregated over all clients. It can be inferred that despite the sampling ratio, APFL can superbly outperform FedAvg.
B.2 ADDITIONAL. RESULTS
In this part, present more experimental results that can further illustrate the effectiveness of APFL on other datasets and models.
Effect of sampling. To understand how the sampling of different clients will affect the perfor- mance of the APFL. algorithm, we run the same experiment with different sampling rates for the MNIST dataset. The results of this experiment are depicted in Figure 4, where we run the experi- ment for different sampling rates of K E {0.3, 0.5, 0.7}. Also, run it with different values of a E {0.25, 0.5, 0.75). The results are reported for the personalized model of APFL and localized FedAvg. As it be inferred, decreasing the sampling ratio has negative impact both the training and generalization performance of FedAvg. However, we can see that despite the sampling ratio, APFL is outperforming local model of the FedAvg in both training and generalization. Also, from the results of Figure 2, we know that for this dataset that is highly non-IID, larger a values are preferred. Increasing a diminish the negative impacts of sampling on personalized models both in training and generalization.
Natural heterogencous data In addition to the CIFARIO and MNIST datasets with pathological heterogencous data distributions, we apply our algorithm NIST (Caldas et al., 2018). We use the data from 1000 clients, and for each round of communication randomly select 10% of clients to participate in the training. We use MLP model with hid- den layers, each with 200 neurons and ReLU as the activation function, using cross entropy as the loss function. For APFL,
natural heterogeneous dataset, EM-
the adaptive scheme with initial value of 0.5 for each client. We run both algorithms for 250 rounds of communication. In each round, each online client performs the local updates for 1 epoch on its data. Figure 5 shows the results of this experiment for person- alized model of APFL and the localized model of the FedAvg. APFL L with adaptive a can reach to the same training loss of the local FedAvg, while greatly outperforms the local FedAvg model in generalization on local validation data.
Data distribution using Dirichlet distribution Another approach to distribute data in non-III way is to use the Dirichlet distribution as discussed in Hsu et al. (2019); Yurochkin et al. (2019). We use this approach and set the parameter of the Dirichlet distribution 1.0 and repeat the experiments
16

---

Under review as a conference paper at ICLR 2021
10
FadAug
1000
Personalized (Acaptive
56.5
01.5
on
00.0
67.5
0.3
Localized FedAug
Personalizod APFL (Adaptive o)
0.1
00.0
12)
Number Commurication Rounds
Namber Communication Founds
Figure 5: The results of applying FedAvg and APFL (with adaptive a) on an MLP model using EM- NIST dataset, which is naturally heterogeneous, APFL achieves the same training loss of localized FedAVG, while outperforms validation accuracy.
for MNIST dataset with MLP model in the main body. Here, again we have 100 clients and run the experiments for 100 rounds of communication each with 1 epoch of training. The results summarized in Table 3. Again, it can be inferred that APFL can generalize well on the local test dataset of different clients.
APFL
FedAVG
0.25
a = 0.5
a 0.75
Global Model
Localized Model
0.004
0.001
0.1946
0.0224
Training Loss
0.001
0.0009
0.0003
0.003
0.0023
98.4 4
98.52%%
98.34%
93.71%
98.04%
Validation Accuracy
0.07%
0.09%
0.06%
0.07%
0.19%
Table The results of training an MLP on MNIST dataset with APFL and FedAvg using Dirichlet distribution for splitting data across clients. The parameter of the Dirichlet distribution is set to 1.
C DISCUSSIONS AND EXTENSIONS
Connection between learning guarantee and convergence. As Theorem 1 suggests, the gener- alization bound depends on the divergence of the local and global distributions. In the language of optimization, the counter-pan partt of divergence of distribution is the gradient diversity; hence, the gradient diversity appears in our empirical loss convergence rate (Theorem 2). The other interesting discovery is in the generalization bound, we have the term λh and LD, (hī), which are intrinsic to the distributions and hypothesis class. Meanwhile, in the convergence result, we have the term i|l = I|2, which also only depends on the data distribution and hypothesis class we choose. In addition, |0 w= also reveals the divergence between local and global optimal solutions.
Why APFL is "Adaptive". Both information-theorrtiiall (Theorem 1) and computationally (Theorem 2), we prove that when the local distribution drifts far away from the average distribu- tion, the global model does not contribute too much to improve the local generalization and we have to tune the mixing parameter to larger value. Thus it is necessary make updated adaptively during empirical risk minimization. In Section 3, (6) shows that the update of a depends on the correlation of local gradient and deviation between local and global models. Experimental results show that our method can adaptively tune a. and can outperform the training scheme using fixed a.
Comparison with local ERM model A erucial question about personalization is when is prefer- able to employ mixed model?, ? and how bad a local ERM model will be? In the following corollary, we answer this by showing that the risk of local ERM model can strictly worse than that of our personalized model.
Corollary 1. Continuing with Theorem 1, there exist a distribution D., constant C₁ and Cz. such that with probability least 8, the following upper bound for the difference between risks of
17

---

Under review as a conference paper at ICLR 2021
personalized model ha; and local ERM model hū Di, holds
1og(1/0))
LD. - CD, (hz) s (2o 1)LD, (h;) (2a,C1 (20
-Ca) -20
+ G2z(
mi
+ +(111 - 2 (D(h+) + -Dili CiV
+ log(1/0)
By examining the above bound, the personalized model is preferable to local model if this value is less than O. In this case, we require (2n² 1) and (20 C2) to be negative, which is satisfied by choosing 0g min
J. Then, the term V d+Hog(118)) should be sufficiently large, and the 19;
divergence term, as well as the global model generalization error has to be small. In this case, from the local model perspective, it can benefit from incorporate some global model. Using the similar technique, we can prove the supremacy of mixed model over global model as well.
Proof of Corollary Since Theorem 1, we already obtained upper bound for LD, (ber.) as fol- lowing,
d+ (og((1//)) + G)u(S.)
(b) + +C11 Chai)) S 20²
mi
log(1
+ 2(11 - az) [c(hh)+ + - + C.y
m
to find the upper bound of LD. (ha,) (hī), just need the lower bound of LD. (ha). The fundamental theorem of statistical learning (Shalev-Shwartz & Ben-David, 2014; Mohri al., 2018) states a lower risk bound for agnostic PAC learning: for a hypothesis class with finite VC dimension d, then there exists a distribution D, such that for any learning algorithm, which learns a hypothesis h H i..dd samples from D, there exists constant C, with the probability at least 6, have:
d log(1/8)
(h) min CD 2 CV N'EH
m
Since hę is learnt by ERM algorithm, the agnostic PAC learning lower risk bound also holds for it, so in worst case it might hold that under distribution D,. if he is learnt by ERM algorithm using samples, then there is C2, such that with probability least 1 5, we have:
d log(1/5)
Lo. Co, 2 LD. (h,) + Cap
m,
Thus we can bound Lo, (har) - CD, (h;) as Corollary claims.
Personalization for new participant nodes. Suppose we already have a trained global model rù and now new device h joins in the network, which is desired to personalize the global model to adapt its own domain. This can be done by performing few local stochastic gradient descent updates from the given global model as initial local model:
(++1) o nh V..eaao (4) (1 - oz )ui:
to quickly lear personalized model for the newly joined device. One thing worthy of inves- tigation the difference between APFL and meta-learning approaches, such as model-agnostic meta-learning (Finn et al., 2017). Our goal is share the knowledge among the different users, in order to reduce the generalization error; while meta-learning cares more about how to build a meta-learner, to help training models faster and with fewer samples. In this scenario, similar to FedAvg, when a new node joins the network, gets the global model and takes a few stochastic steps based its own data to update the global model. In Figure 6, show the results of applying
18

---

Under review as a conference paper at ICLR 2021
90
Sptwiish5533
Syereseto002221 2)- Loce Feilhng
Syetwrogh150 5).
fara Frilog
Viiccatre Acauery
Teaning 90
Sycleti/8888) Peeseu ATT
Syrtheee) (1385 Pesseveed APR
Systore Lera bnd
Number of Epochs
Namber of Epodss
Figure 6: Comparing the effect of fine-tuning with the local model of FedAvg and with the personal- ized model of APFL on the synthetic datasets. The model is trained for 100 rounds of communication with 97 clients, and then 3 clients will join in fine-tuning the global model based on their own data. It can be seen that the model from APFL can better personalize the global model with respect to the FedAvg method both in training loss and validation accuracy. Increasing diversity makes harder to personalize, however, APFL surpasses FedAvg again.
FedAvg and APFL on synthetic data with two different rates of diversity, synthetic(0.0 0.0) and Synthetic(0.5, 0.5). In this experiment, we keep 3 nodes with their data off in the entire training for 100 rounds of communication between 97 nodes. In each round, each client updates its local and personalized models for one epoch. After the training is done, those 3 clients will join the network and get the latest global model and start training local and personalized models of their own Figure 6 shows the training loss and validation accuracy of these 3 nodes during the 5 epochs of updates. The local model represents the model that will be trained in FedAvg, while the person- alized model is the one resulting from AL. Although the goal of APFL is to adaptively learn the personalized model during the training, it can be inferred that APF APFL can learn better personalized model in meta-learning scenario as well.
Agnostic global model. As pointed out by Mohri et al. (2019), the global model can be distribu- tionally robust if we optimize the agnostic loss:
min max F(w) = Σ af((w), weRd qEAn.
(8)
where A,, f - is the n-dimensional simplex. We call this scenario "Adaptive Personalized Agnostic Federated Learning". In this case, the analysis will be more challenging since the global empirical risk minimization is performed at totally different domain, so the risk upper bound for ha, we derived does not hold anymore. Also, from a computational standpoint, since the resulted problem is minimax optimization problem, the convergence analysis of agnostic APFL will be more involved, which we will leave as an interesting future work.
19

---

Under review as a conference paper at ICLR 2021
D PROOF OF GENERALIZATION BOUND
In this section we present the proof of generalization bound for APFL algorithm. Recall that define the following hypotheses on ith local true and empirical distributions:
h arg min LD. (h)
(LOCaL EMPIRICAL RISK MINIMIZER)
kEH
4 = arg min Cp, (h)
(LoCaL TRUE RISK MINIMIZER)
hEH
h" arg min (b)
(GLORAL EMPIRICAL RISK MINIMIZER)
kER
Moc.i arg min LD. (ogh -1-o;) h,))")
(MIXED EMPIRICAL RISK MINIMIZER)
kEH
Moc, arg min LD, (0sh + (1 (1-0;)he h²) (MIXED TRUE RISK MINIMIZER
kE#t
where Lx, (h) and LD. (h) denote the empirical and true risks on D., respectively.
From a high-level technical view, since we wish bound the risk of the mixed model on local distribution D., first we need to utilize the convex property of the risk function, and decompose it into two parts: CD. (hioc..) and CD. (h*). To bound CD. (hioc..) a natural idea is to characterize it by the risk of optimal model CD. (kt), plus some excess risk. However, due to fact that hoo.. not the sole local empirical risk minimizer, rather it partially incorporates the global model, we need to characterize to what extent it drifts from the local empirical risk minimizer h This drift can depicted by the hypothesis capacity, so that is our motivation to define >x to quantify the empirical loss discrepancy over S among pair of hypotheses in H. We have admit that there should be a tighter theory to bound this drift, depending how global model incorporated, which leave future work.
The following simple result will be useful in the proof of generalization.
Lemma 1. Let H be hypothesis class and D and D' denote probability measures space E. Let LD (h) = E( [E (h(æ), y)1 denote the risk of over If the loss function ((-) is bounded by B, then every h E H::
(D(h) S LDD + BIID D'
(9)
where | - D'Il1 =
[ (Paa)) - P. PlaayinD' ddrdy-
Proof.
CD(h) (b) + (Co(h) CDr(h))
- LD(h) + / ((y.h(z))lP((n))>>)) P( ddddy
LD(h) + BID - D'l11- -
Proof of Theorem We now turn to proving the generalization bound for the proposed APFL al- gorithm. Recall that for the classification task consider squared hinge loss, and for the regression case we consider MSE loss. We will first prove that in both cases we can decompose the risk as follows:
CD, (ha,) & 20 CD. (Bioc:)) +((11 - 2 (I*(x)).
(10)
We start with the classification case first. Note that, hinge loss: max (0, 1 22} is convex in 2, so max (0, y(ash + (1 as)h()) & ar max(0, 1 yh) (1 ax) max (0, yh') according
20

---

Under review as a conference paper at ICLR 2021
Jensen's inequality. Hence, we have:
CD.(hai LD, (ashioes + (1 - -a;)h")
ylashion (z) + (1 a:) az))) 2
(a max
-B(a,))DD max - yh ( (z)) + (1 as) max 1 - yy² (2:)) )²
S (a) max(0, (0, yhioo, (x)} 2
2(1 - -a;) a;)" (max (0, yh (x)))²
S 202 LD: (Mioc:s) + 2(1 - ) LD. (h*)
For regression case:
CD. (ha.) = LD, (ashioc, + (1 - -a;)h")
Bla,y)D, (ashioc, (x) + (1-11100 (1-x)h"(<x)) (x))
|ayy ashioc, (x) + (1 a:ly (1 a,)h (2)) ax)h<(>>)
B(a,y)D,,
S 2a 2a
|10 (10)
2 + + 2 E( 11 h (x)]l²
2a LD. (itoc.)) + 2(1 LDD (h*)
Thus we can conclude:
CD. (har)) S 20 LD. (Mioc.) +2(1 - -0x)² LD. (h*)
(II)
T2
We proceed bound the terms Ti and T2 in RHS of above inequality. We first bound Ti as follows.
The first step is to utilize uniform VC dimension error bound over H Mohri et al. (2018); Shalev- Shwartz & Ben-David (2014):
Vh E H. - -D (h)) =c) d log(1/))
where C' constant factor. So we can bound Ti as:
Ti = Lo, (o.(hio,.)) = LDD (47)) + LD. (bioc.)) LDD(hh))
= (1)(1))
+ LD, (hioea))) - LD, (hiocs)) +LD (hioc,)) Lo. (hī) + (h/) - CD, (ht)
50
d4 1773
d log(11))
< LD. + +20
+ (n.(hinn.)) Lo, (h,))
m,
Note that
Lo, (1ioc.) - Lo, (ht) S G S
-
Σ (m.))S;
(x)) - -h((x0) s G)x(S.),
As result we can bound Ti by:
d + log(1/8)
Ti S Lo, (ht) (k2)) V
+ GD).
mi
21

---

Under review as a conference paper at ICLR 2021
We now turn to bounding T2. Plugging Lemma in (11) and using uniform generalization risk bound will immediately give:
Te S Cp(h")+ + B - + CV d d log(1/6)
Plugging Ti and T2 back into (11) concludes the proof.
Remark 3. One thing worth mentioning is that, assume the customary boundedness of loss functions. Actually it can be satisfied if the data and the parameters of hypothesis are bounded. For example, considering the scenario where we are learning linear model w with the constraint ||w|| I 1, and also the data tuples (æt, y) are drawn from some bounded domain, then the loss is obviously bounded by some finite real value.
Remark 4. As LD. (Mioes) is the risk of the empirical risk minimizer on Dj after incorporating model learned on a different domain (i.e.. global distribution), one might argue that generalization techniques established in multi-domain learning theory (Ben-David et al., 2010; Mansour et al., 2009; Zhang et al., 2020) can be utilized to serve our purpose. However, we note that the techniques developed in Ben-David et al. (2010); Mansour et al. (2009); Zhang et al. (2020) are only applicable to a settings where we aim at directly learning a model in some combination of source and target domain, while in setting, we partially incorporate the model learned from source domain and then perform ERM on joint model over target domain. Moreover, their results only apply to very simple loss functions, e.g., absolute loss or MSE loss, while we consider squared hinge loss in the classification case. Analogous to multiple domain theory, we derive the multi domain learning bound based on the divergence of source and larget domains but measured in absolute distance, 1-11 11.. As Mansour et al. (2009) points out, divergence measured by absolute loss can be large, and as a result we leave the development of a more general multiple domain learning theory that can deal with most popular loss functions like hinge loss, cross entropy loss and optimal transport, with righter divergence measure on distributions as an open question.
E PROOF OF CONVERGENCE RATE IN CONVEX SETTING
In this section, we present the proof of convergence raters. For ease of mathematical derivations, we first consider the case without sampling clients at each communication step and then generalize the proof to the setting where K devices are sampled uniformly at random by the server employed in the proposed algorithm.
Technical challenges. The analysis of convergence rates in our setting is more involved compared to analysis of local SGD with periodic averaging by Stich (2018), 8); Woodworth et al. (2020a). The key difficulty arises from the fact that unlike local SGD where local solutions are evolved by employing mini-batch SGD, in our setting we also partially incorporate the global model to compute stochastic gradients over local data. In addition, rather than merely the local model or global model. To better illustrate this, let us first clarify the notations of models that will be used in analysis. Let consider the simple case for now where set K (all device participate averaging). We define three virtual sequences: (w(()) 1T ]1=1 !") 6 = a.u; (2)
goal is to find the convergence rate of the mixed model,
(oO)) and (ū )T where (t) = 1 Σ/= w!! ,u; = a + (1 aal-aja a.)w!
(1 (1-a:)w((), Since the personalized model incorporates 1 a percentage of global model, then the key challenge in the convergence analysis is to find out how much the global model benefits/hurts the local convergence. To this end, we analyze how much the dynamics of personalized model
(t) and global model (t) differ from each other at each iteration. To be more specific, we study the distance between gradients (() (( Surprisingly, relate this distance to gradient diversity, personalized model convergence, global model convergence and local-global optimality gap:
E
| (o(")) - (1 < 6G, 21,2 [1o 11]]] + +6..2 |10000
w01 + +672
10] and E [[ - w w1]] will converge very fast under smooth strongly convex objective, and çi and A, will serve as residual error that indicates the heterogeneity among local functions.
E | (1)
22

---

Under review as a conference paper at ICLR 2021
Algorithm 2: Local Descent APFL (without sampling)
input: Mixture weights 01, On, Synchronization gap 7, Local models v; local version of global model w (0) for i E [n]]
(0) for E [xx] and
for t = 0,... ,T do
if not divides then
w (1) IIw i
(t-1)
1/1 V
u (1-1);
0 (0) Ilw (1-1) 7i V
v (t-1),
( a.u,
+ (1 all-;;yu w:
else
each client sends w (1
to the server
22 w j=
server broadcast (t) to all clients
end end
for
i 1, ,. n do output: Personalized model: 6; 37 Et- pr(a,
(1) (11 0z) A w0,")
1 ΣT Pt Σド= w (t)
Global model: i nSr
end
E.1 PROOF WITHOUT SAMPLING
Before giving the proof of convergence analysis of the Algorithm in the main paper, we first discuss warm-up case: local descent APFL without client sampling. As Algorithm 2 shows, all clients will participate in the averaging stage every T iterations. The convergence of global and local models in Algorithm 2 are given in the following theorems. We start by stating the convergence of global model.
Theorem 4 (Global model convergence of Local Descent APFL wi without Sampling) If each client's objective function is p-strongly convex and L-smooth, and satisfies Assumption I, using Algorithm 2, choosing the mixing weight a; max
1/6x IVen/K }. learning rate
16 m(t+a where +max{128k, T) and using average scheme i nST Σt Σド=1" " (1)
where Pt (t + a)?, ST -IT Pt, then the following convergence holds:
(o
x2 x²= + I luT
+
o²
[[ F(w") s o To)
+0
+ +0
1TZ
113
mT
where w. arg min F F(un) is the optimal global solution.
Proof. Proof is deferred to Appendix E.1.2.
The following theorem obtains the convergence of personalized model in Algorithm
Theorem 5 (Personalized model convergence of Local Descent APFL without Sampling). If each client's 's objective function is p-strongly convex and L-smooth, and satisfies Assumption I, using Algorithm 2, choosing the mixing weight 0; 2 max(1 (1 Avox Avonyaa max m12811 T}. and using average scheme
learning rate T)t
16 u(ttaj'
where
() and J is the local minimum of the ith client, then the following convergence holds for all E [n]:
6;
1 E. Pi= +1-aa)++ E3=1 (0), where Pt (t (t+a)² ST ΣT= ST
Elf(( f: 5 (1))
11
+ o
(0²)
a.)0 +11
+
( +KLA)) "
1T
(nL.InT)
K=022
13' (0² + + 5.))
(n'T 2T 5.) ))
(1 az)²
+
+0
+0
73
unn
1
2T2
23

---

11-11 Under review as a conference paper at ICLR 2021
Proof.
Proof is deferred to Appendix E.1.3.
E.1.1 PROOF OF USEFUL. LEMMAS
Before giving the proof of Theorem and 5, first prove few useful lemmas. Recall that we define
virtual sequences (w (6) T (o
[t= (-
(T (0 Ti=1 where w(()) Ei= w (t) (t))) a,v; + (1
( (T
(t)
a
(t) _b = a (0)
+ - a.
We start with the following lemma that bounds the difference between the gradients of local objective and global objective local and global models.
Lemma 2. For Algorithm 2, at each iteration, the gap berween local gradient and global gradient bounded by
B - s 2 -010 + .6. + +LLAB [10e00 w0'1]] + =662
Proof. From the smoothness assumption and by applying the Jensen's 's inequality we have:
E [IVI((!!))
( ||
s 2E
[VF((0/9)) vf((0)) + 2E -
|10.00
u'[]] + 6E [.,) V11
+ 6I
[IV
VF w || + 6E
|V - FF 11
< 2E
|1650
'
+ E || w 111 + 66, + 6
11 wn w1
< 21,
[1050
1²
+ +L.2 - .0 + 61. [1 w w0113
Lemma 3 (Local model deviation without sampling). For Algorithm 2, at each iteration, the devi- ation between each local version of the global model w!") and the global model w(() is bounded by:
s 3 + +3(G, + E)r2p 1w( (1) - [0]'|p]
E
11
E (un(t) m 10(0pp] < 5 2 + 67 n
n
where S
1 n
Em Gr.
Proof. According Lemma 8 in Woodworth et al. (2020a):
1 12
E (1 11]
E
(t)
(01
71
j=1
S 5
3
0²
Gi
+
(1 pmg)
p=to
g=p+1
1
E w (1) - 11
E 1100 (1)
w 11
i=1 j=1
0² 25 5
1-1
<3
II (1 - pmg)
p=to
$=p+1
24

---

Under review as a conference paper at ICLR 2021
Plugging in fg p(ata) yields:
16
E
(0000 u0!"0
33 0² GTT + -
Σ
1-1
11
[-]
a a+
a+1-- 16
n
a+9
p=te
g-p+1
6 1iT + S
Σ
1-1
[-1
a+9 16
a
<3
a+4
p=le
(=P+1
0 GT + ST
a+q-22
53
n
a+q
p=l.
g-p+1
0 - GT + E
2 p - ()
33
1/p
(a (a+t-2) - 2)
p=te
0 - GiT + 5
1-1
2 カ
33
-
Up
pole
0² + Gi + ST
S 3r
nh-1
Similarly,
n
E
(w))) (t)
w 101 s 3
11-1
67 25 17-71-1 (1)
n2 a Σn - w,
Lemma 4. (Convergence of global model) Let un!!)
Under the setting of Theorem
5, we have:
a
E [1o)+ - w0'18] - S (T + a)3
[1w0 -w0')]]
1 (+t++1n( In(T (M(T++a)) +))) 1536a²t (02 27 2 1.2
+ +
(+ 16
1280 + 2a)
(a
() ta)
nT + a)
Proof. Using the updating rule and non-expensive property of projection, as well as applying strong convexity and smoothness assumptions yields:
B ((+1)
(1+1)
w11
w- |7
<
E
(0 17 Σ (1)
V (w
j=1
f5 wi(h) w") }
< E
(1))))
w w0|1'|
27/
11
+ 1 0²
+ TB
ni Σ
EVSS(W (1)() (
n
5
|1000 (0)
wi|p?
( (0)) (.) w/)) + 1/ Te
22
Σ
Sq (m 11
71
B
(w) () (0 w0
[1 20 11-] 27 (B] F(w F(w"") + n 00
< (1 1o
Ti + T2,
(12)
25

---

Under review as a conference paper at ICLR 2021
where at the last step we used the strongly convex property.
Now we are going to bound Ti. By the Jensen's 's incquality and smoothness, we have:
Ti S E E
1 Σ
- )
+ 2 /|(00)))))))
S 2 1,? 1
n
|| 1 ( 10( + 4n T. (R [((no())]] - F((n*)
R
(13)
==1
Then, we bound T2 as:
Ta
S T)t
2 E
n
V T (1)) -F
+
M 2
1 (t) w0
- |1
11 j=1
27, L 1
E
w
w
(1)
119
Mul
E
w w0113]
(14)
1
n
Now, by plugging back Ti and T2 from (13) and (14) in (12), we have: w
E
((+1)
10
0²
(1
E
- -22 - 4n L)
E
F(w](0)] F(ww))
+
n
2
S-m
12
1
(1) |
+
+ 2.²
(15)
1
j=1
(1
pTl
E
2 (1)
w
1|3]
n
202
22
2n,
1
Σ
E
(t)
w (t) 11] 27
1
n2 j=1
Now, by using Lemma 3 we have:
E
[1
w=1l2
$ (1 1071)) [1 w1]
- +
22
+
27
3r 02 + 2 2/e + m
5
0²
2
n
Note that (1 MT p (((+a))(-8ta)) m
<
p((-1+a)²
Pt on both sides and so we multiply 9
Pt-1
16
16
do the telescoping sum
PT 11
E
w (T+1)
w" [13]
Po E
(1(0(1) w0 1|2]
+ Σ
T
222
+
3T
0² + +225)
11
pe
Σ
PiTle
o²
7o
1
n
1=1
t=1
po E
[120(1)
20 10
+
Σ
T
222
+ 20012)
37 02 (2+55
256a²
+
Pi o²
770
μ
12
1r2
1)2
n
(16)
Then, by re-arranging the terms will conclude the proof:
E (T+))
w01 -w"
[1]]
3
E [1100))- - w11
s (T + 0)3
( a+11 + +In[T + a1) m)) 1536a²7 (0" + 27 5 1
n1
1280"T + 2a)
+ T 16
+
(a 1) + a)3
nT + a)3
where we use the inequality Er ita .
+ 1 Ho < + (T
26

---

Under review as a conference paper at ICLR 2021
E.1.2
PROOF OF THEOREM
Proof.
According to (15) and (16) in the proof of Lemma 4 we have:
T Σ pr (E [F(co! F(ww))
PT E
1 (T+)))) w' [1]
|
w' w'1l]]
71
110
1=1
Σ
T
(2L
222
3r 211
0² +
256a²
Σ
o² pep
1
2 2a 1)3
n
re-arranging term and dividing both sides by ST Et= Pr T yields:
Σ Pc
F
[(
F(ww))
Po STTO
[|u(())
2 11
ST
1
2L
+ +.21112 37 (o² 222
256a²
o²
ST
12 - 1)3
+
ST
Pelle
1e²r (o² + 5)
R (o² + +) In
0² nT
0
s
T
+0
pT²
+0
HTB
+
Recall that á
/=|
]
and convexity of F, we can conclude that:
N²T (a² + 2T 5)
T (a +
R
27 S) lnT
0²
[[F(())] F(w") 0
#
+
+
+0
78
NT²
NT
nT
E.1.3 PROOF OF THEOREM
Proof. Recall that we defined virtual sequences (w(1) 17=1 where w(() = Σ. w. and 6!0)
0 + (1 (.) then by the updating rule and non exnexxeensiveess of projection we have:
E
|10f( - =1]
s E
(()) nm vS(oo00 - -(1 (1- -m1-as)m
n2 Σ
v) (1) - Di
+E
ann (VS(o(") vS(o!"
-as)mi = Σ (vis(w)f)) - ((((w))
yEU,
[1650
0:]]"] 2E (ainv/iio))) + (1 -a-mm
(lu(w!")) ), ),((") vi
E <
1=1
+ n''E
| (i(!' + (1 - as. Σ ( (t)
+ tam + (1 - as) nm n
=
[10o50
wi [|3]
2(aa 1 a
(V(((o!"). ) 6000
n (l(w(()) - v)(ol(), 0500 0i vi) I
-2
a1)
1=1
72
2 E
(a(()i(o!"") + (1 ax)
1
tam 2 + (1 ox)
2 0
1/
(17)
T's
27

---

Under review as a conference paper at ICLR 2021
Now, we bound the term T1 as follows:
Ti (a) + 1 as) )E (VI:(6,)))) - -i)l
2m((a + 1 - 1B (V]i(b!") - V/1(6,0). ). 0.00 vi)
x (a] + as)
(8) [ - fi(of)
2 LE [16!] 05]())
+ +(a} +1 1 - -a
8L2
P.
[11050
a [|] + rall - 8(cu= a.31 T [1o05] - m3 x311²)
M11 - 8(a; - o,))
8
- 5-2m (a? + 1 aa)
(B [
- -s((o))
ME [16(5) -bo1(])
2
8L a:)²
F. [110000 - -wo + all 8(ar; -afi) F [110/0 - [1)
+m (11 - 18(4--004--00 - a.))
8
S 2m + +1 1-aaj) ai) (B [1((699]]
- f(((i))
[10000 7um
- vt 1|
8q, (1 - a,)²
p(l ((1-8(a:- a+)) E |10(0 1=]
(18)
where we use the fact (a, + 1 - -a;) < 1. Note that, because we set a; 2 max [1
1/66"
(Vbnyzh J. and hence 8(a; - at) 2 0, so in the second incquality we can use the arithmetic-
geometry inequality.
Next, we turn to bounding the term T2 in (17):
T2 = 21: - a.)BB
(w0) )
), - -ms
S nc(11 ai)
2(1 - as)
[(((o(") 1 Σ
(w) (11)
+ 2(11 - oa)
/4
E ('all] - 0]]1]]
1
3-1
6(1 a.)² Im
E [ - v,( [|"
+ [..(6())) vF( 20) ||²]
(ro (71)
+E
VF(
1 Σ
+ Mhl
E (ioa5] c. 11
n
2
6(1
Im mp
1.2R
(0) -nn(")
| F - )
+E
VF (0) Σ
+ nhl E [1o - wf]13]
(19)
And finally, we bound the term T3 in (17) as follows:
T3 E of v. + (1 a.)
+ 2F [1 (1-oz) V - - )17
< 2( +1 - 2B || (1 19 >>
52 22(2 +1- =2 3B (((")
].l + 2(a + 1 a.)² [V -V(C0)))))
- +2(1-a.)²B
(w (A(
< <aL(a +1 - as) (B [:(6(00]] - (.:) + 4(1 - ax)² [| [
+ 69 - ai)² (377)
1o w ||] E [\/66(0 v
- ト L2E
(20)
28

---

Under review as a conference paper at ICLR 2021
Now, using Lemma 3, (1 - as)² into (17), yields:
I (a=ss)²=
and plugging back Ti, T2, and T3 from (18), (19), and (20)
| [1((tt1)
3
|16! - v/] - 2(m - Ln + aa)) (E [((((0)) -f((v))
8n. a:)
+ 6(1 - m
10(1 ass) 212 L2 E 1 - (000
1(1 8(as )}
6(1 a.) Pm.
+ 6(1 - as) 1 L²
Σ E
w -
-20 101
6m
'F VF(w //(o//////
+ ainoo + (1 - 2ve 20
+ 6rg
(1
1
3pm
|1000)
wilp] - 2(1 - an [)? + +1-a,) (I [^(o[T)]] -s((v)))
E
8
8tp
oz)²
6(1 mm
+ +00 aa:1-=))?n? 3r (o+ (C: + 511) ni-1
MM 8(a:
a.))
6(1 a, m
+ 6(1
as) 121 L? ) 37
2
1/-1
n1
6/ + on²
(1 BB
- ||²
+a 0² + (1 0m 2
(21)
where using Lemma 2 we can bound T4 as:
T4 S 6T% (1 - as)) (2L'R [10 - 0011]] + 6C, + 6L 11=00) w01 + 66L2A.)
+ +6n a;)² (2L'B [1o65) ||?]
+ 6c, + 667 -1010--011p w²] +6L'4.). (22)
4vox 4v/6r, }. hence 121.2110;)3 < and 12T
Note that we choose a; 2 max P g
a:)²
therehy we have:
1T] T4 <
110 1012
12 + 36q/
I + mz) (1 -a;)² (Gt L,E [1000 - w0'l2] (,00)=w"11""
122..).
4
11
Now, using Lemma we have:
T4 < 1976 B [1050) - -0113] + 36n (1 +m (1 az)²
G 1
(Ita 135 [120 - w1
| 1+16 16 a+1 + lu(t aa(l+aa))) 15367 (o² 27 L?
128 ft(t + 2a) a + - 1)3 + 1'D.) (23)
+
4l( + 1)3
29

---

Under review as a conference paper at ICLR 2021
By plugging back TĄ from (23) in (21) and using the fact -nn (n--4n L) I - -2n, and (a?+1-a;)) 2 we have:
E (16(et1)-0f -.12
$ (1 - p97 LB 110 - 0:]
3m
(E [r(([']]] - -i((:)) + aamoo² + (1 - ai) 22
4
n2
L1 a.)²
6(1 a.) a,))nnn mzL²
+0(11 a1)3 37 0² + (c: + 51 n
m(1 8(a; a}))
+
6(1 a;) 1.
+ +61 - a.) ) [
3r
0² + + 7 nZ-1
n1
a (ww()) w='l 11?
[ ( (1 (++m)(1- a1) G 1,
360%
11.
(t- 1-1+a)
+ ++ 16 ( 1
+ In(t++ an((+a)))
15367 (o² + 2) T?
1280 + 2a)
n + ++.))
aa+1
x1 - 1)3
Note that (1
Pt MM
<
Pt-1 T-
where Pt (1+a)2, so, we multiply Pt on both sides, and re-arrange de
8 n
the terms:
3pt
(B [((699)] - -((()))
4
s pt- R. [1 - -v21²]
PT R.
|10 (1+1)
- - 12] + pam 02?0 + (1 - ax) 22
n-1
71
n
81,(11 - -2:)
6(1 212
+ 10(1 - as) an)=m 37 (0² (Ge + E/r p
+
m(1 - 8(as a)))
#
6(1 2=)²
6(1 2 )
0z + 25 pen + 36p. ( + (1 az)) (Gi + 1.2
1
36pt
+ 91 (1 2
1536r (o² 2 L
12802((t+22))
17
(t (1-1+a)3 + (t+ + 160(lnt))
1 + a 1)3
nyp((t - 1
30

---

Under review as a conference paper at ICLR 2021
By applying the telescoping sum and dividing both sides by Sr Et= Pi T we have:
f(().) f((1))
p: (f((((!)) Ji(w?))
Ap
10
1
1 4
Petp 0,00 (1 - 2i)² (1-as)²
ST
ST 3
n
1
81 0:
6(1 - a.)= 10(1 - m;)? ml) 3r (o² + (Ci (o+
n $)7) puni
ST
a(l 8(cs:
a)))
6(1 L²²²
6(1 a.) 2 )nl))) 37 0² + 2 ponii
ST
48(1 - az)²
1 T
15367 (o² + 2T () 1²²
1280*1(1 + 2a) np²(t-1+a))
Pt
11
mh
(t- a}s
+ (t 160(lnt))
(+ 1-13
1-1
48(1 a.)² + +2A,)
ST Σ
1
+
Pt
j
4
11)00) m]]1
(T + a)
a²0²² + (1 az) 02)200 j20
STp
3UST
4(1 -a,)²
S
6L 10L=0(mnT)
37 0² (S: -11))
236a² 112 1)2
3
1a(1-
8(a: 8T
STT
UST
4
6(1
2
6(1 a:)² L2 T)
0² +
25 n
256a²
3r
3
PST
pSt
1²(a - 1)²
a²
48(1 -o,)²1 21²²
(a 1)2ST
a d'O(1T))
T
1536L (0² + +27
64(2a + 1)o²I((T + a)
0(li2)
11
41
mapa
a²
16
1536L (o² + +22 {)
+ 2048(2u + 1)o² T nap
2T? 48(1
+9((In T))
(a 1)2ST
6/
110
ST
8T + 2a)
48(1 ax) (G+ (Gi+)
ST
11
P
-0 + a
0²
- 00
Ge
+nLas
+
(1T
/
+ (1 az)² (0
In
n² N²O²?
12 N²
+ (.) + R²T0"
(x' + 2T
+
+0
+0
73
unll'
nll
4l2
where we use the convergence of Eee
lnf 7
0(1,, and
E D1=1 7
2²
E.2 PROOF OF CONVERGENCE OF APFL WITH SAMPLING
In this section will provide the formal proof of the Theorem 2. Before proceed to the proof, we would like to give the convergence of global model here first. The following theorem establishes the convergence of global model in APFL.
Theorem (Global model convergence of Local Descent APFL). If each client's 's functionn function is u-strrongly convex and L-smooth, and satisfies Assumption 1, using Algorithm I, by choosing the learning rate Tp
p(t+aa. where a = max T}, K = L and using average scheme
16
#.
i KST Σt Pt Ejeu, w/ where Pt = (1 a)2, ST Σt= Pt. and letting F* to denote the
(1)
31

---

Under review as a conference paper at ICLR 2021
minimum of the F, then the following convergence holds:
K²T + 2T
n²T
N²' (o"
25 {) lnT
+0(xT)
0² KT
E [[F(#))] F" 00 +0
+0
+
pT
1TB
(24)
where T the number of local updates (i.e., synchronization gap)
Proof. The proof is provided in Appendix E.2.2.
Remark 5. It noticeable that the obtained rale matches the convergence rate the FedAvg, and if choose T VT/K, recover the rate O(y1/TT), which is the convergence rate of well-known local SGD with periodic averaging (Woodworth et al., 2020a).
Now we switch to the proof the Theorem 2. Appendix E.1.3, non-sampling setting. The only difference is that hence, we will introduce the variance depending on sampling size K. Now we first begin with the proof of some technique lemmas.
The proof pipeline is similar to what we did in
sampling method here,
E.2.1 PROOF OF USEFUL LEMMAS
Lemma 5. For Algorithm I, at each iteration, the gup between local gradient and global grudient bounded by
|T]
| E (1)(
E
K
JEL,
s 21 [10 - - x0] + (22 + xxx
+ 61,7T [1 - w w011]] + AI.2A,
Proof. From the smoothness assumption and by applying the Jensen's inequality we have:
R
[V
J/ K
Σ
(w
JEU,
2
[V))( v)((=))]? 2E
[V)((o))
Σ (10())0))
JeC.
x 2
[1050
0'127] GE [[(o)(
V.i(w"))] [1[
6E
[V
1 Σ (w
+G I Σ
vb(ww))
1 Σ (
K
jEú,
jEU,
jEU,
< <2LBB [10(0) -011²] 66 -a||
w 113] + 2Ç, +
1
Σ So
GL [11o0 20
K
jEUi
s 21 [16|0 00 1|2
6LL2, +
2G + 2 + 6L
[1l00
w w0112]
Lemma (Local model deviation with sampling), For Algorithm 1, at each iteration, the deviation between each local version the global model w and the global model (!!) is bounded by:
(0) - -0 [0(" s 2 +3(5 +
2
E
K
E [110(()) - -n,"0 [2] < 3ro 23 + Gr
2 1
K
K
VEU:
where &
R m Gr.
32

---

Under review as a conference paper at ICLR 2021
Proof. According to Lemma 8 in Woodworth et al. (2020a):
E 2000 -w 10!"
-
1
E
|10 (1)
w
11]
K
JEU
)
Σ
3
2 +
CIT +
K
Up
(1 (1-w7g)
p=to
4=p+1
E
w (1)
w [0]
S
1
E 1100
(1)
w
(8)
|2]
n
im
jml
5
33
2
+
2T
II (1 - pm1)) q=p+1
K
p=te
Then the rest of the proof follows Lemma
Lemma 7. (Convergence of Global Model) Let w(()) = K
Ejer wj (0) In Theorem 2's setting,
using Algorithm I by choosing learning rate as 1pe = pittay we have:
E (Tt)) - w0|p S (T' + a)3 1000 w' 11²]
a²
1 lmf + =1)) 1536a 2 (0² +2 LT
128a 2a) (T²(T+a))
+ T' 16
a+1
(a - 1T +T' +a}s
Proof. According to the updating rule and non-expensiveness of projection, and the strong convexity we have:
E
((+1))) 113
E
(t) Tle K
1
V (0 w²
jEU,
< E
1100 (1) 10
- 2
1 Σ
V fj fz (,) w( - w²) )
-wo)
)
K
jEU,
1
Σ V (t))
+ 111 0
+ 1/
K
K
JEU,
+ nz 002
$ (1 - [120((0
- w011 - (2m 22 LE -(xw(0)-F(())) -F(w-)
-
K
||00) - 1010 21
+ 1/1 K
2
Σ 1,2B
Σ (lz(10()) - VVi (1) 20 w²
K
JEU,
jEU,
+ 112 0²
< (1 wm)) )E
-2011]] [200(())==01]]]] -(2)
4LTR) E ((wo(()) F(wo))
K
S-m
+ +n/ L2 1
Σ E
100 (0())
(t) ||]
+ 21 L2 1
Σ
E
w
(t)
(0)
11]
27
E
[w (1)
w w=1
K
K
2
JEU,
DEU,
(25)
33

---

Under review as a conference paper at ICLR 2021
Then, merging the term, multiplying both sides with Pt. and do the telescoping sum yields: 1/."
E hr
|100 - w [1|]
E
[1
20 1|]
([F(w(()) F(w")]
70
T
2T2
+
21
Pt K Σ
E
10 (1)
w0
100
+ Σ
Pttpt
o²
K"
JEU,
1=1
(26)
Plugging Lemma 6 into (26) yields:
Pr
E
1 (T+1))
w
11]
Pe
E
[1
w 113
E[(((w(!))
F(w")]
9f
170
Σ>
21. +
2nd23
3poth-17
(o2 (o²+27
5
T
o²
Pidt
K
t=1
(27)
Then, by re-arranging the terms will conclude the proof as
a
E
(T+1)) - w=11]] s
E
|
w w²]
(T
+ aa)
1536a² 1,27 (02 + 2T K
In(T + +0)))
+
a+1
(a -0-11 1) (T + ta)
T2Ta2T(T 2a)
Kμ²(T + a)3
F.2.2
PROOF OF THEOREM
Proof.
According to (28) we have:
PT
E
|| (T+
w0 [12]
Po
E
(1
2
20(13]
E[F((ww (w(() F(w")]
Tf
170
Σ
222
21.1.3
3pmth-17 (0² (o 27
Σ
T
o²
+
Pttte
(28)
By re-arranging the terms and dividing both sides by ST = Σt Pe > T yields:
[ [()]
F(w"))
<
Sr
Pu
F
ST
1 T
Σ
2
2m.11 1. 3ppri-17 0²2 27 5
K
+
ST
1
P47p
o²
K
1=1
(wwl))
w01
(o²
27 2))
1x2 27 x In
0²
50
+0
78
1022
4T's
KT
Recalling that á
T Pr Σソ
from the convexity of F(-), we can conclude that w
(t)
nST
E [[F(@)] - F(w") 2 (3) +0
<²T 10" + +T 2x
+0
1KT (o²
27 R
lnT
+
o²
4
pl
KT
34

---

Under review as a conference paper at ICLR 2021
E.2.3 PROOF OF THEOREM
Now we provide the formal proof of Theorem 2. The main difference from wathout-sampling setting is that only subset of local models get updated each period due to partial participation of devices, iee, K out of all devices that are sampled uniformly at random. To generalize the proof, we will use an indicator function to model this stochastic update, and show that while the stochastic gradient unbiased, the variance is changed.
Proof. Recall that we defined virtual sequences of {w where un())
1 Ejev, w and
K ((0) = a.v + (1 - (t))w()) We also define an indicator variable to denote whether ith client was
selected at iteration t:
- -{(
1 if U²
else
obviously, E [1:]] have:
K.
Then, according to updating rule and non-expensiveness of projection we
| [(()+ - w.113]
(10) Th (. - (1-00 1 Σ () - vi
s
JEU,
17
a 1/ (V/i(b!0) vi((o! + (1:mm
1 Σ Vs (w)
1 Σ (ls(Wu))
E
K
K
jEti
jet,
0]]]]] -2 a v (5( +(1 ax)m K
(l (,) ),000
JEU
of (
+ ass
1 Σ
2k
+ (1 ) 20
ai
n2
K
JEL/
-
[1o!!
-211
- + ai
K
vs((o (,000
-21 (1 aB)
Σ
- 6: - -0;)
K
SEU
T2
+ 2K²
+ (1 az) 2 20
+ + (1- aa) K
Σ (w)()
+a 1
n²
K
jet
35

---

Under review as a conference paper at ICLR 2021
Now we switch to bound Ti:
T = -2mi
K
- + 1 - a;
[ii(o ) -/0 -;)]
n
217e(
K
0;
2 + a:)
< (V)i(o(") Vf((6("), ) 0/9) -oil
n1
K
(R) [1(][9]] [((1)) + T [10/5] - -05 [1*]
< -21
of + - as)
n
+ (
K
a + 1 - ai)me
8L2
E
|100 -
u1( 8(a: a? ))
11
1(l 8(a;
at az
[10.00 2 [1²]
8
< -mp
K
ai + 11 -1a)) (B [ - -f((o)) + E (1060) 2t (11]
2
n
8L2 (1 a,
EF [110(00 - 10!0 + 1111 8((:
K kat))
E [1o - 1000-011' [[]]]]
+ 1t
111 - 8(a; a?))
< 2m 04 + 1 - axi)
K 2
(B [[]00o]]] -i(())))
7pme E [1005] - [13]
n
8q. (1 a,)² ?
E (1001)) w. 10]"
+
(29)
111 - 8(a; - am))
For T2, we use the same approach as we did in (19); To deal with T3, we also employ the similar technique in (20):
T3 = E
(T0)) a;)
Σ
(
K
JEU
< 2 - a + 1 -
K
+1-
| 5: (1) |ル}
+ 2E
(1 (1-ax) az)
DIvI(110) - -V/(o())
jEU,
K
2 2(
? +1 +1- (0))) [
n
K 2 + 1 - 2E
[V/)(o!") - -V(((()1P))
+2(
1
n
+ +2(1- -
Σ
K
jEU,
< 8T( K 2
E [[(]((]]] - -.:) + 4((1 T.22 [1le((0 -mo""
a 1 - -as)
n
+ 6(1 a2)² (L33)
(o(()) - mo! ! ||] + | -
Σ L -000) 11)
(30)
K
JEU,
36

---

Under review as a conference paper at ICLR 2021
Then plugging Tı, T2, Ty back, we obtain the similar formulation as the without sampling case in (17). Thus:
I
1]
3pm7
E [166!0 v?1l²]
2(n L) at n
+1 oz) (B [[<[)']]] - f((1))
8
2Ko²
20
+ a, 1t
+ (1 - -as)= a 1/2
n
K
8n, 54:L'11 (1 0²
6(1 0z) meL
+ +10 - -0:)-a))3(
E
w - 20!"
M(1 8(a:
a7 k ])
6(1 a.)3
+ 6(1 T/
1
Σ
n
10
m0 10011
/
K
yEU,
17
6n + 6T²² (1 a
-
(31)
P
K
JEU:
we then examine the lower bound of o K +1 1 0x. Notice that: 0, K
n
+1 -0
K
n
[((o=
n )²+ + 2K
n K
TK
Case 1: 2K
21
1
The lower bound is attained when a; = 1: o
K
+ 1 a; 2 K
Case 2:
n
< 1
The lower bound is attained when a; = n
2k a n
K
+ 0; 2 1
π > 1
2K
4K 2'
So 2 K
a + 1 a; 2 b min 1 } always holds.
Now we plug and Lemma 6 back to (31):
E [1o(ett)
]]]]"]
3/m7;)
(10000
0711²] by: (B[rA(o(O) - -i(0))) + a +aini 2Ko²
+ (1 - a1)²m1 20
8
n
K
L1
6(1 an ned? 0x
+ 10(1 - aa)) 1.2 अ (o+ (c: + {T)
+
n11 8(o=
at 1)
1
6(1 ((1-aa))mm 661 -a-
3-m2-1 (0² + 2 (0²+25)
xx²
1
6m + 6n²) (1 (1-as) =T)
Σ
V -
(32)
p
K
JEUL
Plugging Lemma yields:
E b
((41)
3pmp
E 2[166(0 -0;11]] - bby (R [A(][()] (00())))s((())))) -i(o))) + i?? 2Ko²
+ 19--a) as)² 20²
8
n
K
o;)²
+ 6(1 - 1. + +10(1 1all-a))21 +
21 37TH (0² + (G. - )r)
m(1 - 8(a,
of K)
6(1 as) as) 1.2
+ 6(1 -ri) ni)????? 3-12
02 22+25
#
K
6tp
+ 67?) (1 o2)² 22,²8 [1090) 0''1]] + (2g + 2xx
)
+ +6127 (lw0") - w0] + 666 A
K
37

---

Under review as a conference paper at ICLR 2021
Then following the same procedure in Appendix E.1.3, together with the application of Lemma can conclude that:
f((6.)- f((w))
<
1
Σ (((()((()))) - f((oT))
ST
pul 110.0) vi11"]
T
2Ko²
+(1 (1-ai)²ri mm 20
Σ
SI
UST
pit
ai%
K
1=1
+ bST
Σ (1-aa)²12 a=)
u(1 - 8(a: - a 22
10m
3mpeoh-2 (o² + (Gi (Si+
S K )T)
1
1m1
T
6 +10m
3TPere-1 (0"
x2+2
SST
K
1m1
+ +66(11 - a²)²
L
Σ
L (
(t- (0-1 aa33 E [100 -w0'l
bSt
1
1+ Inft bn(t++)))
1536a -0" + 2T L²
11-11a111t - + ta3 + 12802U(L+24
+ 16 16
+
a+1
(a-
(1²(t-1+a))
T
+ +33611 a;,²²
25i + 2 K
+ 112.))
GSt
Σ
Pt
1/t
1=1
=0 p
+ 0
0²
+ (1 - a
2C + 2
KLAi
8T
jubT
jib
b
kLIuT 67
x²O²²
12: + & + TO²
+ (1 (1-0))²
+ 0
+
HbKT
nbT
" (o² + 27
+0
1bT2
F CONVERGENCE RATE WITHOUT ASSUMPTION ON Oi
In this section, we provide the convergence results of Algorithm 1 without assumption og. The following Theorem establish the convergence rate:
Theorem 7 (Personalized model convergence of Local Descent APFL without assumption on a.).
If each client's 's objective function is p-strongly-convex and I--mooth, and its gradient is bounded by G, using Algorithm I, learning rate: T):- = pit+ay' where a = max (64K, T}, and using average scheme v; = ST Et= (1) + a;)
(1-a;) 2 EyEU, ())), where pt (t + a)², S. Σt= Po. and Si is the local minimum of the ith client, then the following convergence holds for all E [m]:
B[fi(6,)] 13 S
1
+ +a70
0²
+ +(1
G²
bT
PubT
Hbb
KLInT
n20²
Tx2 + { + K2TT?
+ (1
az)
0
+ 0
+ +
6T
HbKT
(0² + 2T T
+0
(33)
ubT²
where b- min K )
38

---

Under review as a conference paper at ICLR 2021
Av AvGn./u1: ). The key difference is that we can only show the residual error with dependency on G, instead of more accurate quantities Sa and D, Apparently, when the diversity among data shards is small, S, and Ds terms become small which leads to a tighter convergence rate. Also notice that, to realize the bounded gradient assumption, we need to require the parameters come from a bounded domain W. Thus, we need to do projection during parameter update, which is inexpensive.
Remark 6. Here remove the assumption oq 2 max -
Proof. According (32):
E
||0|(t]]
11
3pm
E
[16 -0]13]
bm (B [[ f((o?))
8
2 2 2Ko² + 0 11
2 20²
(1 3112
n
K
8m, L (1 a:)²
6(1
3 (2+ (S: $
+
10(1 ai))
1(1 - 8(a;- - a 1)
6(1 3 1,2
5
+ 6(1
az)) 1;)) 112
3712-11
02 +
1
K
+
6n p
+ 6rž
(1 (1- 2z) (1-0;)²T
-
JEU,
Here, we directly use the bound E k EsEu (f)(w(0) \/:6o/))/
22G Then we have:
|10| ||0 (()())))
of 112
$ (1 p
E -
- -b7 (B [[]]([] - -((0)))
4
2 2Ko²
+1 o..) 20²
+ a
1/1
K
8m, 2 - );
6(1 - m2)
3TTh (²2 (Gi {
+
10(1 az:
111 8(0; - a K
P
6(1 a,) 2, I?2
0² + 02+25, 5 K
+
+ 6(1 an 122
3
r
121
+1212)
(1-as) G2
39

---

Under review as a conference paper at ICLR 2021
Then following the same procedure in Appendix E.1.3, we can conclude that:
f((8)) - f((1))
pi(S((6)0) fi(wi))
ST
[10(4) 11?
PolE
2Ko²
20²² + (1 ai)) Th K
ST
UST
petp
n
(1 - 2=
8
+
6
+ 10m
3pp:ti-11 0² (o* (G {1
SST
M(1 - 8(a;
a,
(1 2=2
6
10ml)
3rperi-1
(0²
+ oo*
$
S
bST
K'
12(11
0²2
T
1
17:
GST
11 =0
+ a,0
+ (1 0=)²0
G²
1T
ubT
μb
(1 - ai)²
In
0²²02
+0
2 + k)) + x² 20=
+ 0
x xa'T(0p (02 + 25 2
DT3
pbKTT
JuT
G PROOF OF CONVERGENCE RATE IN NONCONVEX SETTING
In this section we will provide the proof of convergence results nonconvex functtions. Let us first present the convergence rate of the global model of APFL, on nonconvex function:
Theorem 8 (Global model convergence of Local Descent APFL). If each client's 's objective function L-smooth, using Algorithm I with full gradient, by choosing = n. and learning rate 1 2/5LVT' then the following convergence holds:
V w
/1
())
50
L VT
+0
T26 nT
Proof.
The proof is provided in Appendix G.2.
As usual, let introduce several useful lemmas before the formal proof of Theorem and 8.
G.1 PROOF OF TECHNICAL LEMMAS
Lemma 8. Under Theorem 3's assumptions, the following statement holds true:
f((0!)) ((
1
+ 2 (1 an)²n w w /0/0 + 3aa - n (2 10(0) -mm w000|?
+ 6n -a,) + 12n(1 2?? + 12n(a: - at}² VF (F
40

---

Under review as a conference paper at ICLR 2021
Proof. Define the following quantities:
+ -
az)
V (1)
j=1
0 77 ( (oV + +1- a.) - V (w) ())
Bw(t/"g90))
1
0
II
77
W
According to Ghadimi al. (2016) Lemma Forr all W c R4, g Rd and 17 >> we have:
(g, Pw(w,g.)) gw(w,ggn)ll
According to the updating rule and smoothness of f., we have:
f((0(tt)) S f.(60 + ), (((t1)) ((0))
+ L
(e+1)
(.00
2
S f1(60) (. 0((+1) 0/0) + L
0/
(((+1))
0500
</(00) (VV(6()) (w(6l) (0000)0000000))))
+ 7
Pw( .g ,g0),,)
2
<A(0()) 7 (9 (w (1) g0 (m)) (V/((o(0) "') , .1)
L |Aw(oS) " gg.n))
2
(34)
Using the identity:
(0(()")g)))))))))) () Pw( . 2 113
and Cauchy-Schwartz inequality that
V)((o!) - "), (o (w. s [[
601 + 1 (wo(o"".g)..))) (0)01))
1
have:
41

---

Under review as a conference paper at ICLR 2021
1((0!-11 s )i(((()) - ||000²+ +
R ( .g/0 .n|²=
, /wllff ,g mml
2
+ 7
Vf((o!0 a.V - (1 az) _ n
Σ V ( )
2
(1) I
9
2
2
1in
1 n2
+ 7
- - - (a=a;)
Σ
( (0))
2
n ==1
$ (.((//0) 1" | + - as)?7 (1-=a))77 VF( Σ V f, m (1)
+olln (V%(6//) - V)((o!9) - (( (1 - a² (1-a))// \
s ((0 / 0| + +(1 +(1-a:) 1/
_ Σ 10100 - + 23
(vri(o/)- v.(oo!)) )|²
+ +2n (1
a VF(B
(1 -(1a)())--aa))((((""
S (,((000) 1" g0)
+ (1 a;) )2, 1 Σ
(0 - /0/00 2 + 22 |0,00 -0(0-5(()) -/oo|²
+4n [1- at ((
(1 -1- at //
4n (1 - a. (F(O! - - -(1-a.)VF((u (1)
$T/(,(0) 1" g 2
+ (1 - ) 1 Σ
(1)) w (1) 2
+ 2a -a)'nL² | -w: 10
(1 a.) (0) (1-aa))V(( { 2 + +8n |(0s - ((ss-
[() (t) 18
+ +1n(1 - - 2z)&g + 8n
S <)((0[0) 1 g + (1 - az)3 Σ (0()) w 10 + +2a - Rnt2 (t) 2 !0)
+ +44(1 an(1-17)95 + 87(1 - ???2I.222y + +8n(a; - - (F ?
Using the following inequality to replace [|?
|V 22 - 11 22
hence we can conclude the proof:
42

---

Under review as a conference paper at ICLR 2021
(O! s M(
V [V](()) - g/ -
- 2
+ +(1-ai) az)²"1 1
Σ
/010) w0/0 + 2a, n 20 - -w0 "0
+ +4n(1 - ag)p<, + +1n(1 - 23)R122 +
- -n(a,
V (F(
1 4" V..((.)) - (,م + +(1 as) Σ
S <'/1010 1 [((:)\1 +
V (o((
+ +(1 +1--ai) +11-a))31) 1 Σ
-0:0-w00) =0/0|² + 2a - a)2 |2010) (1:0~ww' -wo !
==1
+ +47(1 - 0z) + 8n(1 - 0z)3I2233 + 8n(a, - a373 1
S ))10/00 (1))6
+ 21 ai)21 1 (0( - -w, 00/ + +3a - -a)?nt? (t) - -u0 (0
3
+ 6nn(1 - (0011-13)3. 12 2?) + 12n(a; - ag?
( //((0(1))
Lemma 9. Under Theorem 3's assumptions, the the following statement holds true:
I
( ||
8 T
((w + 6L2
w (1) w (t) 2
Proof. Define the following quantities:
g0 () (0)
n
(0 Pw(w (1) g00)
((
w (t)
- Σ v (((
According to the updating rule and smoothness of fi, we have:
F(w((+1)) < (() + (F(w()), w((+ - w()) -w())) + L | - w0
2
< (0) 11 (V)(w) (w "0000,00001)009111 _00,,,)) + 2
1226
PP g(0 m))
< (0) 17 (g)) Pwl(u g0) n)) n (VF(col)) -g pw 00))
+ L
( (() m)]
(35)
Using the identity: (g()) (w( ((()))))g()) > |2 and Cauchy-Schwart inequality that
(VF(uo()) -))), Pw (0) m)) < 1 (t) - ( 12 + 2 (P ,(0) gg"),) 12) we have:
43

---

Under review as a conference paper at ICLR 2021
F(wltt1)) s F(w!!))
-1 |0)
+ + rfT.)
( g(d) m|
+ "
VF VF(w
- |
2
2
S {F(w(0) -
g (0
2
+
2 +
L2L
1/00|2
+
7 1
w
w/ - w
2
2
S F(w
""
1 (t)
nT.22
1
n
2
(t)
w
n
Using the following inequality to replace 1
(0) < ()) -0 11
hence we obtain:
1 4" (3 (1IFF(w(0)) - -((00) F(wl((1)) S F(w)!0))
11T.2
-
+
Σ
w
w (1)
2
1 n VF( + 3nI $ =(w"1))
w00
w
4 n
Re-arranging terms and doing the telescoping sum from t = to
T
F( s nT )(w
8
+ 6L2
w (t)
w (1)
T
Lemma 10. Under Theorem 3's assumptions, the following statement holds true:
w
1072211 11 n
T T
w
10/
S 2000L
17 n
+ 2072,1 222
Proof. For the first statement, define "t Σ (t)) w w000 10]2 and let to be the latest synchronization stage. Then we have:
2
a
7
(3)
w Σ (VSSinn
7
w
n1
n
==
1=1
j=to
V
(a -
Σ
Σ
(T) - v(a(wo())) Vf((w()) - v.f((o(0)) + Vfilw00)) Vfi(w((1))
Σ 5y²² (21272 + +5)
< T
1=t
44

---

Under review as a conference paper at ICLR 2021
Summing over t from te to te + 7 yields:
21 + S
5Tm
18
t ==te
(r+1)T
$ 10
Σ
+ 15 5
Since 17 S 2v3rL' we have 10
S 2 hence by re-arranging the terms we have:
Σ Y S 10 10 25
1f
1=fe
Summing over all synchronization stages te, and dividing both sides by T can conclude the proof of the first statement:
107 3 25
7e
(36)
To prove the second statement, let 6
w(())
w
(8)
Notice that:
w
fa(wF - 30' Σ V Si
k=
(w (3) - )
j=te
(k V)((w(()) + fe(lw())
Vf((w(1) + V.((w()) V)(lw(1))
T
j=tt
Σ 5yj² (L²3g + 120 + Gt)
jute
Summing over t from to to + 7 yields:
lot
1. te
Σ
5T72 (L'rg + LZoj + ti)
t= f=te
lot
bett
s 2 1
Yi 5L2
Σ
83 5-8
j=te
j=t.
Since S
1 we have 5L273,72 < 3. hence by re-arranging the terms we have:
2/5rL'
++t
tuto
Σ
8 < 20
Σ
71 + 20+
j=t.
Summing over all synchronization stages ter and dividing both sides by T can conclude the proof of the first statement:
1
5
<
20L 20
Yo + 20'
T
T
t=1
Using the result from (36) to bound
2 T
7/ we have:
T
Σ
8 < , 2072212
45

---

Under review as a conference paper at ICLR 2021
G.2
PROOF OF THEOREM 8
Proof. According to Lemma 9:
VF
)
|| 2
8 n/
F(w 6I.
w (8) w
T
Then plugging in Lemma 10 will conclude the proof.
G.3 PROOF OF THEOREM 3
Proof. According to Lemma 8:
f,(0, S f((())) (1) 1
8 - V
+ 2 (1 an) Σ
w
w0/ w0/0 + (1 - (1) /u0(0 10/
+ 67 at)² + 12m(1 L2 + 12m(a: - az}² /))(
Re-arranging the terms, summing from t = 1 to T, and dividing both sides with T yields:
V
())
nT
+ 24a (1 - 2 2
1
(1)
wo
+1211 - aa))
Σ
1
1
w
w00'
T
T
T
+ +128(1 - =²
Σ
+ + a33 128(1 0? Dw
T
Then, plug in Lemma 9 and 10:
(
()) np
48(1
az)
128(1 - -a2) Dw
+4aa TT2
1
10
(0()) 12 12(
2T2
Σ
n
1
m (1)
w (0)
T
T
T
+ +128(1 - 0z)2 -0z))
(1) + +692
(1)
2
w
1/T
T
j=1
81)()(1) nTT
L'2 Dw + 48(1 af)²c + 128(1 az)² L
+ 24aa
212 200 2 + 2072 2G
n
778007 a; 2225 +
1024(1 a; (1)
n
nT
46

---

Under review as a conference paper at ICLR 2021
Plugging in 1
concludes the proof:
2/5vTL
1
T
L
L
+ a1-1
+ (1- a1-oz)) (c: L2Ww)
vT
vT
TtS
S
T2C
+ + (1 - -a)30
+
+ (1 a:)30
nTT22
T
nT
47


Reviews:
[{"review_id": "hkOSESKEYnu", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "==================== Post rebuttal ====================\n\nI thank the authors for their response and additional experiments. Please see my comments below.\n\n**Relation to [1]** The first version of [1] appeared on arxiv in February. I am not sure if it has been published since then or not, but regardless it is sufficiently ahead of the ICLR submission deadline to consider it a prior work. [1] provides a Mapper optimization algorithm in Figure 4. There are some minor differences with your algorithm, but I don't see how they make your algorithm more communication efficient. Generalization analysis in [1] is for the mixing parameter learned from data (i.e. adaptive), that is why there is no dependency on it. Your analysis is for a fixed mixing parameter, but since it is not possible to know it in advance, learning it from data seems to be more reasonable. So I am not sure what is the advantage of a theorem with explicit dependence on it. I agree that the convergence analysis is new, but [1] also has two more algorithms.\n\n**Experiments** Despite that your paper has more experiments, EMNIST experiment in [1] is better suited for studying personalization in my opinion. EMNIST results in Appendix B in the submission are for **digits only** (and also use fewer clients, but that is less important). One of the reasons that a centrally trained model on EMNIST performs worse than personalized models is the shift in the distribution of characters and digits across clients. This is not the case for MNIST/CIFAR10: if I train a neural net using all of MNIST train data it will easily achieve 99+ average test accuracy (without any personalization). How the test data is split across clients does not matter because accuracy on each digit is roughly the same. That is what I meant by a \"single global model with good performance (i.e. trained on the full dataset)\".\n\nHaving worked on FL with personalization myself, I've noticed that it is quite hard to achieve a meaningful improvement over the vanilla FedAvg + fine-tuning. This is also evident from Table 2 of [1], where none of their algorithms offer a convincing improvement. This paper claims that an algorithm very similar to Mapper [1] indeed outperforms FedAvg + fine-tuning. I'd be happy if it is so, but I do not find the provided experimental evidence sufficient. I recommend reproducing the EMNIST experiment of [1] (please don't discard characters, use the same number of clients per communication, etc.). If your algorithm can achieve 91+ accuracy, I'd consider it an improvement. In that case, a more detailed discussion of the differences with Mapper [1] that enabled the improvement would also be great.\n\nRegarding the number of parameters, based on eq. (1), personalized model is a convex combination of **two** models. So if I understood correctly, the number of parameters is increased both during training and testing.\n\n====================================================\n\n\nThis paper considers the problem of personalization in federated learning. The proposed approach consists of allowing each client to have a local model for personalization and taking a convex combination of global and local models as personalized preditors. Authors also provide a theoretical analysis of the generalization and convergence guarantees and empirical evaluation.\n\nThe proposed method is equivalent to the Mapper algorithm from [1]. Generalization analysis is also very similar.\n\nThe empirical study is not conducted carefully:\n- Allowing for a separate local model for personalization increases the number of parameters which is not accounted for\n- Reported performance of the global model trained with FedAvg on MNIST and CIFAR10 is overly pessimistic. Prior works (e.g. [2]) report much better performance for the non-personalized model in similar heterogeneous data splitting scenarios.\n- Splitting MNIST and CIFAR10 datasets by classes is not a realistic way of simulating heterogeneous distributions in my opinion (see [3,4] for more recent strategies). It also does not seem appropriate for studying personalization as we know that there is a single global model with good performance (i.e. trained on the full dataset) and the key challenge is the optimization over heterogeneous datasets rather than the need for personalization. I recommend datasets such as FEMNIST [5] for studying personalization.\n\n[1] Three Approaches for Personalization with Applications to Federated Learning\n[2] Communication-Efficient Learning of Deep Networks from Decentralized Data\n[3] Bayesian Nonparametric Federated Learning of Neural Networks\n[4] Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification\n[5] https://leaf.cmu.edu/", "extra_scores": {}, "extra_text": {}}, {"review_id": "cI4YfIVdaeA", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## 1. Summary\n\nI do apologize for delaying the review process. I do spend lots of time and carefully read the paper. All comments listed below intend to help authors improve the quality of the manuscript. They are based on my understanding which might contain misunderstanding points if any. I hope comments are helpful and even the critiques are not discouraging your endeavor in the following.\n\nFirst of all, the manuscript proposed an adaptive personalized federated learning algorithm, where each client will train their local models while contributing to the global model. The convergence analysis and generalization bound for the algorithm are conducted.\n\n## 2. Major Comments:\n\n- Could please emphasize the motivation in figure 1, I cannot follow your statement.\n\n- The authors defined the average distribution $\\bar{\\mathcal{D}}=1/n\\sum_{i=1}^n\\mathcal{D}_i$. Why the global model can be obtained by minimizing the joint empirical distribution $\\bar{\\mathcal{D}}$ in the federated learning?\n\n- Why you only consider the smooth loss? \n\n- The optimal mixing parameter is the theoretical one. It seems cannot be used in practices. How do you think?\n\n## 3. Minor Comments:\n\n- Page 5, the first line, it should be ``model $v_i^{(t)}$''.\n\n- Definition 2 you should cite ``Li, Xiang, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. \"On the convergence of fedavg on non-iid data.\" arXiv preprint arXiv:1907.02189 (2019).''\n\n\t", "extra_scores": {}, "extra_text": {}}, {"review_id": "PrpPm79xaQ", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the personalization aspect of the federated learning problem. The authors propose a new framework in which they replace the common global model in the original federated learning formulation with a convex combination of the global model and a local model. They later introduce an adaptive optimization algorithm for their formulation and provide generalization bounds as well as convergence guarantees for both strongly-convex and nonconvex settings.  Finally, numerical experiments and comparison with other methods in the literature are provided to support the theoretical results.\n\nThe paper has a complete story. It provides generalization bounds, optimization results for both strongly convex and nonconvex functions, as well as experiments and comparison with other works.  \n\nHowever, I am slightly confused regarding the proposed formulation. In Section 2.1, for any agent $i$, and for a mixing weight $\\alpha_i$, $h_{loc,i}^*$ is defined as (I suppressed the hat notation over $h_{loc,i}^*$ and calligraphic font due to some compilation error here).\n\n$h_{loc,i}^* = argmin_{h \\in H} \\hat{L}_{D_i}(\\alpha_i h + (1-\\alpha_i) \\bar{h}^*).$\n\nThe authors then take $h_{\\alpha_i} := \\alpha_i h_{loc,i}^* + (1-\\alpha_i) \\bar{h}^*$ as the output, and claim that this is not the minimizer of $\\hat{L}_{D_i}$, since \"we optimize $h_{loc,i}^*$ with partially incorporating $\\bar{h}^*$.\" \n\nHowever, I am not sure if I follow the argument here, and it is not clear to me why $h_{\\alpha_i}$ is not the minimizer of $\\hat{L}_{D_i}$. Let's take $H = \\mathbb{R}^d$, as stated in Section 4. Also, let's denote the minimizer of $\\hat{L}_{D_i}$ as $h_{opt,i}$. Then, the solution to the minimization problem above would be\n\n$h_{loc,i}^* = (h_{opt,i} - (1-\\alpha_i) \\bar{h}^*) / \\alpha_i$\n\nwhich leads to having $h_{\\alpha_i} = h_{opt,i}$, the minimizer of $\\hat{L}_{D_i}$. \n\nI have the same confusion regarding Section 3 as well. There, the goal is to solve two minimization problems \n\n$ w^* = argmin_{w \\in \\mathbb{R}^d} \\frac{1}{n} \\sum_{i=1}^n f_i(w), \\quad v_i^* =  argmin_{v \\in \\mathbb{R}^d} f_i(\\alpha_i v+ (1-\\alpha_i)w^*),$\n\nand the output of the algorithm, for instance in Theorem 2, is $\\alpha_i v_i+ (1-\\alpha_i)w^*$ which is the minimizer of $f_i$. If this is the case, why we need to find $w^*$, and why not solving $argmin_{v \\in \\mathbb{R}^d} f_i(v)$ directly? \n\nIt is completely possible that I am missing something here. But I would appreciate it if authors provide a clarification on this.\n\nAs a second question, I am wondering if there is any connection between the sequence $\\alpha_i^{(t)}$ and the optimal $\\alpha_i^*$ derived in Section 2. In other words, for instance for the strongly convex case, does the sequence $\\alpha_i^{(t)}$ converge to any particular value close to $\\alpha_i^*$?", "extra_scores": {}, "extra_text": {}}, {"review_id": "7MXDd3dEsk", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose a variant of FedAvg that not only produce the global training, but also a mixture of the local model and the global model, which is called personalized model. As a result, the personalized models show better validation accuracy. The theoretical and empirical analysis are provided.\nIn overall, I think the paper is technically sound, making reasonable contributions.\n\nHowever, some parts of the paper is unclear to me, which may affect the final score:\n\n1. In the exerpiments in Figure 2, it is still unclear to me how the \"local validation\" dataset is sampled, even after I read the appendix. The most important thing is, on each worker, does the validation dataset shares the same subsets of labels as the local training data? If not, then why call it \"local\"? Also, for the results in Table 1 and 2, are the validation dataset also \"local\"? My concern is that, if the local validation data is close to the local training data, and is not sampling from the global distribution, then this criterion is too beneficial to APFL, and not fair for the global models.\n\n2. Theoretically, when $\\alpha$ gets smaller, the personalized models also gets closer to the global model. Especially, when $\\alpha=0$, the presonalized model is equivalent to the global model, which is equivalent to the result of FedAvg. However, the empirical results indicate the opposite. In all the experiments (Figure 2, Table 1 and 2), when $\\alpha$ gets smaller, the validation accuracy gets farther away from FedAvg. Even with a pretty small $\\alpha$ (=0.25), the gap between APFL and FedAvg is still huge. However, the $\\alpha=0$ case seems not discussed in the theoretical analysis. Furthermore, the mismatch between the theoretical and empirical results when $\\alpha$ gets smaller is not explained.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies personalized federated learning, mixing a global model with locally trained models.  Reviewers agreed on the relevance of the problem and that the work contains valuable contributions, such as the generalization bounds.
After discussion, unfortunately consensus remained that the paper remains narrowly below the bar in the current form. 
Concerns remained on novelty over the Mapper optimization algorithm which also has adaptivity to the local/global combination of models, the dependence of the generalization bound on the mixing parameter as it converges to the global model, 
as well as on the strength of the experimental findings compared to well-known FedAvg and related method in a realistic benchmark environment (such as e.g. Leaf), since the dataset choice (and even more its partition among clients) is a crucial aspect for measuring personalization in a fair way. We hope the feedback helps to strengthen the paper for a future occasion.
Decision: Reject