Year: 2020

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.

heading: 1 INTRODUCTION
text: 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 a 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 to 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, FedAvg is hugely sensitive to its hyperparameters, and as a result, does not benefit from a favorable convergence guarantee (Li et al., 2020c). In Karimireddy et al. (2019), authors 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 diagnosis (Li & Wang, 2019), where poor performance on local clients could result in damaging consequences. This problem is exacerbated even further as the diversity among local data of different clients is growing. To better illustrate this fact, we ran a simple experiment on MNIST dataset where each client’s local training data is sampled from a 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
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 (Karimireddy 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 a poor generalization of local clients. To embrace statistical heterogeneity and mitigate the effect of negative transfer, it 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 et 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 disadvantage 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 a mixture of optimal local and global models. We theoretically analyze the generalization ability of the personalized model on local distributions, with dependency on mixing parameter, the divergence between local and global distributions, as 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 a better generalization compared to the global models learned by FedAvg and SCAFFOLD. We supplement our theoretical findings with extensive corroborating experimental results that demonstrate the superiority of the proposed personalization schema over the global and localized models of commonly used federated learning algorithms.

heading: 2 PERSONALIZED FEDERATED LEARNING
text: In this section, we propose a personalization approach for federated learning and analyze its statistical properties. Following the statistical learning theory, in a federated learning setting each client has access to its own data distributionDi on domain Ξ := X×Y , whereX ∈ Rd is the input domain and Y is the label domain. For any hypothesis h ∈ H the loss function is defined as ` : H×Ξ→ R+. The true risk at local distribution is denoted by LDi(h) = E(x,y)∼Di [` (h(x), y)]. We use L̂Di(h) to denote the empirical risk of h on distribution Di. We use D̄ = (1/n) ∑n i=1Di to denote the average distribution over all clients.

heading: 2.1 PERSONALIZED MODEL
text: In a standard federated learning scenario, where the goal is to learn a global model for all devices cooperatively, the learned global model obtained by minimizing the joint empirical distribution D̄, i.e., minh∈H L̂D̄(h) by proper weighting. However, as alluded to before, a single consensus predictor may not perfectly generalize on 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 to seek a reduction in the local generalization error 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 heterogeneity among distributions. This motivates us to mix the global model and local model with a controllable weight as a 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 a better client-specific model. In 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 minh∈H L̂D̄(h), while each user trains a local model while partially incorporating the global model, with some mixing weight αi, i.e., ĥ∗loc,i = arg minh∈H L̂Di(αih + (1 − αi)h̄∗). Finally, the personalized model for ith client is
a convex combination of h̄∗ and ĥ∗loc,i:
hαi = αiĥ ∗ loc,i + (1− αi)h̄∗, (1)
It is worth mentioning that, hαi is not necessarily the minimizer of empirical risk L̂Di(·), because we optimize ĥ∗loc,i 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 `2 unit ball: H = {h ∈ R2 : ‖h‖2 ≤ 1}. Assume the local empirical minimizer is known to be [1, 0]>, and h̄∗ = [−1, 0]>, and α is set to be 0.5. Now, if we wish to find a ĥ ∗ loc,i, such that hαi = α ∗ ĥ ∗ loc,i + (1 − α) ∗ h̄
∗ coincides with local empirical minimizer, we have to solve: 0.5∗h+0.5∗ [−1, 0]> = [1, 0]>, subject to ‖h‖2 ≤ 1. This equation has no feasible solution, implying that it is not necessarily true that hαi coincides with local empirical minimizer.
In fact, in most cases, as we will show in the convergence of the proposed algorithm, hαi will incur a residual risk if evaluated on the training set drawn from Di.

heading: 2.2 GENERALIZATION GUARANTEES
text: We now characterize the generalization of the mixed model. We present the learning bounds for classification and regression tasks. For classification, we consider a binary classification task, with squared hinge loss `(h(x), y) = (max{0, 1− yh(x)})2. In the regression task, we consider the MSE loss `(h(x), y) = (h(x)− y)2. 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 to measure the empirical complexity of a hypothesis classH over a training set S. Definition 1. Let S be a fixed set of samples and consider a hypothesis class H. The worst case disagreement between a pair of models measured by absolute loss is quantified by: λH(S) = suph,h′∈H 1 |S| ∑ (x,y)∈S |h(x)− h′(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 et 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 classH be compact closed set with finite VC dimension d. Assume loss function ` is Lipschitz continuous with constant G, and bounded in [0, B]. Then with probability at least 1−δ, there exists a constantC, such that the risk of the mixed model hαi = αiĥ∗loc,i+(1−αi)h̄∗ on the ith local distribution Di is bounded by:
LDi(hαi) ≤ 2α2i LDi(h∗i ) + 2C √ d+ log(1/δ)
mi +GλH(Si)  + 2(1− αi)2 ( L̂D̄(h̄∗) +B‖D̄ − Di‖1 + C √ d+ log(1/δ)
m
) ,
(2)
wheremi, i = 1, 2, . . . , n is the number of training data at ith user, m = m1 + . . .+mn is the total number of all data, Si to be the local training set drawn from Di, ‖D̄ − Di‖1 = ∫ Ξ |P(x,y)∼D̄ − P(x,y)∼Di |dxdy, is the difference between distributions D̄ and Di, and h∗i = arg minh∈H LDi(h). Remark 1. We note that a very analogous work to ours is Mansour et al. (2020), where a generalization bound is provided for mixing global and local models. However, their bound does not depend on αi, and hence we cannot see how it impacts the generalization ability. In Theorem 1, by omitting constant terms, we observe that the generalization risk of hαi on Di mainly depends on three key quantities: i) m: the number of global data drawn from D̄, ii) divergence between distributions D̄ andDi, and iii)mi: the amount of local data drawn fromDi. Usually,
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 mi is often small, the generalization performance of local model can be poor.
Optimal mixing parameter. We can also find the optimal mixing parameter α∗i that minimizes generalization bound in Theorem 1. Notice that the RHS of (2) is quadratic in αi, so it admits a minimum value at
α∗i =
( L̂D̄(h̄∗) +B‖D̄ − Di‖1 + C √ d+log(1/δ)
m ) ( L̂D̄(h̄∗) +B‖D̄ − Di‖1 + C √ d+log(1/δ)
m
) + ( LDi(h∗i ) + 2C √ d+log(1/δ) mi +GλH(Si) ) . The optimal mixture parameter is strictly bounded in [0, 1], which matches our intuition. If the divergence term is large, then the value becomes close to 1, which implies if local distribution drifts too much from average distribution, it is preferable to take more local models. If mi is small, this value will be negligible, indicating that we need to mix more of the global model into the personalized model. Conversely, if mi is large, then this term will be again roughly 1, which means taking the majority of local model will give the desired generalization performance.

heading: 3 OPTIMIZATION METHOD
text: To optimize the learning problem we cast in 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 h in the hypothesis space H to be parameterized by a vector w ∈ W ⊂ Rd where W is some convex closed set and denote the empirical risk at ith device by local objective function fi(w). Adaptive personalized federated learning can be formulated as a two-phase optimization problem: globally update the shared model, and locally update users’ local models. Similar to FedAvg algorithm, the server will solve the following optimization problem:
min w∈W
[ F (w) := 1
n n∑ i=1 {fi(w) := Eξi [fi (w, ξi)]}
] , (3)
where fi(.) is the local objective at ith client, ξi is a minibatch of data in data shard at ith client, and n is the total number of clients. Motivated by the trade-off between the global model and local model generalization errors in Theorem 1, we need to learn a personalized model as in (1) to optimize the local empirical risk. To this end, each client needs to solve this optimization over its local data:
min v∈W
fi (αiv + (1− αi)w∗) , (4)
where w∗ = arg minw F (w) is the optimal global model. The balance between these two models is governed by a parameter αi, which is associated with the diversity of the local model and the global model. We first state the algorithm for a pre-defined proper αi, and then propose an 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 to local ERM model, which means the personalization fails. Hence, to make sure the correctness of our algorithm, we need to require the parameter comes from some bounded domainW
Local Descent APFL. To efficiently optimize the problem we cast in (3) and (4), in this subsection we propose our bilevel optimization algorithm, Local Descent APFL. At each communication round, server uniformly random selects K clients as a set Ut. Each selected client will maintain three models at iteration t: local version of the global modelw(t)i , its own local model v (t) i , and the mixed personalized model v̄(t)i = αiv (t) i + (1−αi)w (t) i . Then, selected clients will perform the following updates locally on their own data for τ iterations:
w (t) i = ∏ W ( w (t−1) i − ηt∇fi ( w (t−1) i ; ξ t i )) ,v (t) i = ∏ W ( v (t−1) i − ηt∇vfi ( v̄ (t−1) i ; ξ t i )) , (5)
Algorithm 1: Local Descent APFL input: Mixture weights α1, · · · , αn, Synchronization gap τ . for t = 0, · · · , T do
parallel for i ∈ Ut do if t not divides τ then
w (t) i = ∏ W ( w (t−1) i − ηt∇fi ( w (t−1) i ; ξ t i )) ,
v (t) i = ∏ W ( v (t−1) i − ηt∇vfi ( v̄ (t−1) i ; ξ t i )) v̄
(t) i = αiv (t) i + (1− αi)w (t) i , Ut ←− Ut−1
else each selected client sends w(t)i to the server w(t) = 1|Ut| ∑ j∈Ut w (t) j
server uniformly samples a subset Ut of K clients. server broadcast w(t) to all chosen clients
end end
end
where ∇fi (.; ξ) 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 v̄(t)i as well. The clients that are not selected in this round will keep their previous step local modelv(t)i = v
(t−1) i . After these τ local updates, selected clients will send their local version of the global model w
(t) i to the server for aggregation by averaging: w (t) = 1|Ut| ∑ j∈Ut w (t) j . 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 α. 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 α is infeasible. However, we can infer it empirically during optimization. Based on the local objective defined in (4), the empirical optimum value of α for each client can be found by solving α∗i = arg minαi∈[0,1] fi (αiv + (1− αi)w), where we can use the gradient descent to optimize it at every communication round, using the following step:
α (t) i = α (t−1) i − ηt∇αfi
( v̄
(t−1) i ; ξ t i
) = α
(t−1) i − ηt
〈 v
(t−1) i −w (t−1) i ,∇fi
( v̄
(t−1) i ; ξ t i
)〉 , (6)
which shows that the mixing coefficient α is updated based on the correlation between the difference 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 of α changes to adjust the balance between local data and shared knowledge among all devices captured by the global model.

heading: 4 CONVERGENCE ANALYSIS
text: In this section we provide the convergence analysis of Local Descent APFL with fixed αi for strongly convex and nonconvex functions. To have a tight analysis, as well as putting the optimization results in the context of generalization bounds discussed above, we define the following parameterization-invariant 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 to measure the diversity among local gradients with respect to the gradient of the ith client: ζi = supw∈Rd ‖∇F (w) − ∇fi(w)‖22 (Woodworth et al., 2020a). We also define the sum of gradient diversities of n clients as: ζ = ∑n i=1 ζi. Definition 3. We define ∆i = ‖v∗i−w∗‖22, where v∗i = arg minv fi(v), andw∗ = arg minw 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 at local objectives.
Assumption 1 (Bounded Variance). The variance of stochastic gradients computed at each local data shard is bounded, i.e., ∀i ∈ [n]:E[‖∇fi(x; ξ)−∇fi(x)‖2] ≤ σ2.
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 in Appendix E.2.3. Theorem 2. Assume each client’s objective function is µ-strongly convex and L-smooth, and satisfies Assumption 1. Also let κ = L/µ, b = min { K n , 1 2 } . Using Algorithm 1, by choosing the mixing weight αi ≥ max{1− 14√6κ , 1− 1 4 √ 6κ √ µ }, learning rate: ηt = 16µ(t+a) , where a = max{128κ, τ},
and using average scheme v̂i = 1ST ∑T t=1 pt(αiv (t) i +(1−αi) 1K ∑ j∈Ut w (t) j ), where pt = (t+a) 2,
ST = ∑T t=1 pt, and letting f ∗ i to denote the local minimum of the ith client, then the following convergence rate holds for all clients i ∈ [n]:
E[fi(v̂i)]− f∗i ≤ α2iO ( σ2
µbT
) + (1− αi)2O ( κ2σ2
µbKT + κ2τ
( τζi + κ
2τ ζ K ) µbT 2 + ζi + ζ K µb + κL∆i b ) .
If we choose τ = √ T/K, then:
E[fi(v̂i)]− f∗i ≤ α2iO ( σ2
µT
) + (1− αi)2O ( κ2σ2+κ2ζi+κ 4 ζ K
µKT
) + (1− αi)2O ( ζi+ ζ K
µ + κL∆i
) .
A few remarks about the convergence of personalized local model are in place: (1) If we set αi = 1, then we recover O ( 1 T ) convergence rate of single machine SGD. If we only focus on the terms with (1−αi)2, which is contributed by the global model’s convergence, and omit the residual error, we achieve the convergence rate of O(1/KT ) using only √ KT 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 ζi and local-global optimality gap ∆i. It shows that taking any proportion of the global model will result in a sub-optimal ERM model. As we discussed in Section 2.1, hαi will not be the empirical risk minimizer in most cases. Also, we assume that αi needs to be larger than some value in order to get a tight rate. This condition can be alleviated, but the residual error 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 learned by APFL for nonconvex smooth loss functions. The proof is provided in Appendix G.3.
Theorem 3. Let v̂(t)i = αiv (t) i + (1 − αi) 1K ∑ j∈Ut w (t) j . If each client’s objective function is L-smooth and domain W be bounded by DW , that is, ∀w,w′ ∈ W, ‖w − w′‖2 ≤ DW . Using Algorithm 1 with full gradient, by choosing K = n and learning rate η = 1
2 √ 5L √ T , we have
1
T T∑ t=1 ∥∥∥∇fi(v̂(t)i )∥∥∥2 ≤ O( L√ T ) + (1− αi)2 ( L√ T ) + (1− α2i )2 ( ζi + L 2DW )
+ α4i (1− αi)2O ( τ4ζ
nT 2 + τ2ζi T
) + (1− αi)2O ( τ2ζ
nT
) .
By choosing τ = n−1/4T 1/4, it holds that:
1
T T∑ t=1 ∥∥∥∇fi(v̂(t)i )∥∥∥2 ≤ O( 1√ T ) + (1− αi)2O ( 1√ T + 1√ nT ) + (1− α2i )2 ( ζi + L 2DW ) .
Here we show that APFL will converge to stationary point on nonconvex function with sublinear rate plus some residual error, with n3/4T 3/4 communication rounds. The rate with factor (1 − αi)
2 is contributed from the global model convergence, and here we have some additive residual error reflected by ζi and DW . Compared to most related work by Haddadpour & Mahdavi (2019) regarding the convergence of local SGD on nonconvex functions, they obtain O(1/ √ nT ), while we only have speedup in n on 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 as a future work.

heading: 5 EXPERIMENTS
text: 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 run our experiments on Microsoft Azure systems, using Azure ML API. The code is developed on PyTorch (Paszke et al., 2019) using its “distributed” API with MPI. We deploy this code on Standard F64s family of VMs in Azure. We use four datasets for our experiments, MNIST, CIFAR10 (Krizhevsky et al., 2009), EMNIST (Cohen et al., 2017), and a synthetic dataset. For more information on datasets used in the following experiments refer to Appendix B.1. 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 is 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 performance over training data for optimization error and local validation data (from the same distribution as training data for each client) for the generalization accuracy. Throughout these experiments we 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 τ 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 τ = 10, unless otherwise stated.
• Personalized Model: This model is the personalized model produced by our proposed algorithm APFL. The reported results are 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 of experiments on the MNIST dataset, with different levels of non-IIDness 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 is involved is discussed in Appendix B.2. We compare the personalized model of APFLwith different rates of personalization as αwith global and localized models of FedAvg and SCAFFOLD, as well as their global models. The initial learning
rate is set to 0.1 and it is 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 models 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 α) will result in the lower training losses. For generalization ability, the best performance is given by personalized model with α = 0.25 in both (a) and (b) cases, which outperforms the global (FedAvg and SCAFFOLD) 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 a 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 α with both optimization and generalization losses. As it can be seen from the first row, α has a linear relationship with the optimization loss, that is, with smaller α, 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 α, and hence, the generalization performance does not simply increase or decrease monotonically with α.
Adaptive α update. In this part, we want to show how adaptively learning the value of α 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.1, with logistic regression as the loss function. We set the initial value of α(0)i = 0.01 for every i ∈ [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 a result of adaptively updating α 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 α values to guarantee the best generalization performance. We also have results on EMNIST dataset with adaptive tuning of α in Appendix B.2, wih a 2-layer MLP.
Nonconvex loss. To showcase the results for a nonconvex loss, we use CIFAR10 dataset that is distributed in a non-IID way with 2 classes per client. We apply it to a CNN model with 2 convolution 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 localized models of FedAvg and SCAFFOLD, as well as their global models, in both optimization and generalization. In this case adaptively tuning the α achieves the best training loss, while α = 0.25 case reaching the best generalization performance.
Comparison with other personalization methods. We now compare our proposed APFL with two recent approaches for personalization in federated learning. In addition to FedAvg, we compare with perFedAvg introduced in Fallah et al. (2020) using a meta-learning approach, and pFedMe
introduced in Dinh et al. (2020) using a regularization with Moreau envelope function. We run these algorithms to 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 α in our APFL) and β = 0.001. To have a fair comparison, we use the same validation for perFedAvg and we use 10% of training data as the test dataset that updates the meta-model. For pFedMe, following their setting, we use λ = 15, η = 0.01. We use τ = 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 α = 0.75 has the lowest training loss, and the one with adaptive α has the best validation accuracy. perFedAvg is slightly better than the localized FedAvg, however, it is 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.

heading: 6 CONCLUSIONS
text: In this paper, we proposed an adaptive federated learning algorithm that learns a mixture of local and global models as the personalized model. Motivated by learning theory in domain adaptation, we provided generalization guarantees for our algorithm that demonstrated the dependence on the diversity between each clients’ data distribution and the representative sample of the overall distribution of data, and the number of per-device samples as key factors in personalization. Moreover, we proposed a communication-reduced optimization algorithm to learn the personalized models and 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.

heading: SUPPLEMENTARY MATERIAL: ADAPTIVE PERSONALIZED FEDERATED LEARNING

heading: TABLE OF CONTENTS

heading: A Additional Related Work 13

heading: B Additional Experimental Results 15
text: B.1 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 B.2 Additional Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

heading: C Discussions and Extensions 17

heading: D Proof of Generalization Bound 20

heading: E Proof of Convergence Rate in Convex Setting 22
text: 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 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
E.2 Proof of Convergence of APFL with Sampling . . . . . . . . . . . . . . . . . . . . 31 E.2.1 Proof of Useful Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 E.2.2 Proof of Theorem 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 E.2.3 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

heading: F Convergence Rate without Assumption on αi 38

heading: G Proof of Convergence Rate in Nonconvex Setting 40
text: G.1 Proof of Technical Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 G.2 Proof of Theorem 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 G.3 Proof of Theorem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

heading: A ADDITIONAL RELATED WORK
text: The number of research in federated learning is proliferating during the past few years. In federated learning, the main objective is to learn a global model that is good enough for yet to be seen data and has fast convergence to a local optimum. This indicates that there are several uncanny resemblances between federated learning and meta-learning approaches (Finn et al., 2017; Nichol et al., 2018). However, despite this similarity, meta-learning approaches are mainly trying to learn multiple models, personalized for each new task, whereas in most federated learning approaches, the main focus is on the single global model. As discussed by Kairouz et al. (2019), the gap between the performance of global and personalized models shows the crucial importance of personalization in federated learning. Several different approaches are trying to personalize the global model, primarily focusing on optimization error, while the main challenge with personalization is during the inference time. Some of these works on the personalization of models in a decentralized setting can be found in Vanhaesebrouck et al. (2017); Almeida & Xavier (2018), where in addition to the optimization error, they have network constraints or peer-to-peer communication limitation (Bellet et al., 2017; Zantedeschi et al., 2019). In general, as discussed by Kairouz et al. (2019), there are three significant categories of 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 can obtain a 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.
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-learning approaches, notably the Reptile algorithm by Nichol et al. (2018) and FedAvg, and combine them to 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 to 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 to 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 on each client can be 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 et al. (2020).
Contextualization: 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 is 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 heterogeneity and ensures the fair learning.
Personalization via model regularization: Another significant trial for personalization is model regularization. There are several studies to introduce different personalization approaches for federated learning by regularize the difference between the global and local models. Hanzely & Richtárik (2020) try to introduce a new formulation for federated learning where they add the regularization 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 FedAvg (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 regularization 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 is 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 a 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
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 et al. (2019) ask an essential question of “when is a global FL-trained model better?”, or as we can ask, when is personalization better? The answer to 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 to the local SGD scenario (Stich, 2018; Haddadpour et al., 2019a;b; Woodworth et al., 2020b). However, when the data is non-IID 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 in Mohri et al. (2019) on how to appropriately mix the global and local model, we answer this question by adaptively tuning the degree of personalization for each client, as discussed in Section 3, so it can perfectly become agnostic to the local data distributions.

heading: B ADDITIONAL EXPERIMENTAL RESULTS
text: 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.

heading: B.1 DATASETS
text: For the experiments we use 4 different data sources as follows:
MNIST and CIFAR10 For the MNIST and CIFAR10 datasets to be similar to the setting in federated learning, we need to manually distribute them in a non-IID way, hence the data distribution is pathologically heterogeneous. 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 limited 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 a non-IID CIFAR10 dataset, where each client has access to only 2 classes of data.
EMNIST In addition to pathological heterogeneous data distributions, we 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 a 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, we follow the procedure used by Li et al. (2018), where they use two parameters, say synthetic(γ, β), 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 a weight matrixW i ∈ Rm×c and a bias b ∈ Rc, where the output for the ith client is yi = arg max ( σ ( W>i xi + b )) , where σ(.) is the softmax. In this setting, the input data xi ∈ Rm has m features and the output y can have c different values indicating number of classes. The model is generated based on a Gaussian distribution W i ∼ N (µi, 1) and bi ∼ N (µi, 1), where µi ∼ N (0, γ). The input is drown from a Gaussian distribution xi ∼ N (νi,Σ), where νi ∼ N (Vi, 1) and Vi ∼ N (0, β). Also the variance Σ is a diagonal matrix with value of Σk,k = k−1.2. Using this procedure, we generate three different datasets, namely synthetic(0.0, 0.0), synthetic(0.5, 0.5), and synthetic(1.0, 1.0), where we move from an IID dataset to a highly non-IID data.

heading: B.2 ADDITIONAL RESULTS
text: In this part, we 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 performance 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 experiment for different sampling rates of K ∈ {0.3, 0.5, 0.7}. Also, we run it with different values of α ∈ {0.25, 0.5, 0.75}. The results are reported for the personalized model of APFL and localized FedAvg. As it can be inferred, decreasing the sampling ratio has a negative impact on 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 α values are preferred. Increasing α can diminish the negative impacts of sampling on personalized models both in training and generalization.
Natural heterogeneous data In addition to the CIFAR10 and MNIST datasets with pathological heterogeneous data distributions, we apply our algorithm on a natural heterogeneous dataset, EMNIST (Caldas et al., 2018). We use the data from 1000 clients, and for each round of communication we randomly select 10% of clients to participate in the training. We use an MLP model with 2 hidden layers, each with 200 neurons and ReLU as the activation function, using cross entropy as the loss function. For APFL, we use 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 personalized model of APFL and the localized model of the FedAvg. APFL with adaptive α 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 a non-IID 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 to 1.0 and repeat the experiments
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 are summarized in Table 3. Again, it can be inferred that APFL can generalize well on the local test dataset of different clients.
distribution for splitting data across clients. The parameter of the Dirichlet distribution is set to 1.

heading: C DISCUSSIONS AND EXTENSIONS
text: Connection between learning guarantee and convergence. As Theorem 1 suggests, the generalization bound depends on the divergence of the local and global distributions. In the language of optimization, the counter-part 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 LDi(h∗i ), which are intrinsic to the distributions and hypothesis class. Meanwhile, in the convergence result, we have the term ‖v∗i −w∗‖2, which also only depends on the data distribution and hypothesis class we choose. In addition, ‖v∗i −w∗‖2 also reveals the divergence between local and global optimal solutions.
Why APFL is “Adaptive”. Both information-theoretically (Theorem 1) and computationally (Theorem 2), we prove that when the local distribution drifts far away from the average distribution, the global model does not contribute too much to improve the local generalization and we have to tune the mixing parameter α to a larger value. Thus it is necessary to make α updated adaptively during empirical risk minimization. In Section 3, (6) shows that the update of α depends on the correlation of local gradient and deviation between local and global models. Experimental results show that our method can adaptively tune α, and can outperform the training scheme using fixed α.
Comparison with local ERM model A crucial question about personalization is when it is preferable to employ a 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 be strictly worse than that of our personalized model. Corollary 1. Continuing with Theorem 1, there exist a distribution Di, constant C1 and C2, such that with probability at least 1 − δ, the following upper bound for the difference between risks of
personalized model hαi and local ERM model ĥ ∗ i on Di, holds :
LDi(hαi)− LDi(ĥ∗i ) ≤ (2α2i − 1)LDi(h∗i ) + (2α2iC1 − C2)
√ d+ log(1/δ)
mi + 2α2iGλH(Si)
+ 2(1− αi)2 ( L̂D̄(h̄∗) +B‖D̄ − Di‖1 + C1 √ d+ log(1/δ)
m
) .
By examining the above bound, the personalized model is preferable to local model if this value is less than 0. In this case, we require (2α2−1) and (2α2iC1−C2) to be negative, which is satisfied by choosing αi ≤ min{ √ 2 2 , √ C2 2C1 }. Then, the term √ d+log(1/δ) mi , should be sufficiently large, and the 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 1. Since in Theorem 1, we already obtained upper bound for LDi(hαi) as following,
LDi(hαi) ≤ 2α2i LDi(h∗i ) + 2C1 √ d+ log(1/δ)
mi +GλH(Si)  + 2(1− αi)2 ( L̂D̄(h̄∗) +B‖D̄ − Di‖1 + C1 √ d+ log(1/δ)
m
) ,
to find the upper bound of LDi(hαi) − LDi(ĥ∗i ), we just need the lower bound of LDi(ĥ∗i ). The fundamental theorem of statistical learning (Shalev-Shwartz & Ben-David, 2014; Mohri et 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 on m i.i.d. samples from D, there exists a constant C, with the probability at least 1− δ, we have:
LD(h)− min h′∈H
LD(h′) ≥ C √ d+ log(1/δ)
m .
Since ĥ∗i 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 Di, if ĥ∗i is learnt by ERM algorithm using mi samples, then there is a C2, such that with probability at least 1− δ, we have:
LDi(ĥ∗i ) ≥ LDi(h∗i ) + C2
√ d+ log(1/δ)
mi .
Thus we can bound LDi(hαi)− LDi(ĥ∗i ) as Corollary 1 claims.
Personalization for new participant nodes. Suppose we already have a trained global model ŵ, and now a new device k joins in the network, which is desired to personalize the global model to adapt its own domain. This can be done by performing a few local stochastic gradient descent updates from the given global model as an initial local model:
v (t+1) k = v (t) k − ηt∇vfk(αkv (t) k + (1− αk)ŵ; ξ (t) k ) (7)
to quickly learn a personalized model for the newly joined device. One thing worthy of investigation is the difference between APFL and meta-learning approaches, such as model-agnostic meta-learning (Finn et al., 2017). Our goal is to 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, it gets the global model and takes a few stochastic steps based on its own data to update the global model. In Figure 6, we show the results of applying
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 personalized model is the one resulting from APFL. Although the goal of APFL is to adaptively learn the personalized model during the training, it can be inferred that APFL can learn a better personalized model in a meta-learning scenario as well.
Agnostic global model. As pointed out by Mohri et al. (2019), the global model can be distributionally robust if we optimize the agnostic loss:
min w∈Rd max q∈∆n F (w) := n∑ i qifi(w), (8)
where ∆n = {q ∈ Rn+ | ∑ qi = 1} 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 a totally different domain, so the risk upper bound for hαi we derived does not hold anymore. Also, from a computational standpoint, since the resulted problem is a minimax optimization problem, the convergence analysis of agnostic APFL will be more involved, which we will leave as an interesting future work.

heading: D PROOF OF GENERALIZATION BOUND
text: In this section we present the proof of generalization bound for APFL algorithm. Recall that we define the following hypotheses on ith local true and empirical distributions:
ĥ∗i = arg min h∈H L̂Di(h) (LOCAL EMPIRICAL RISK MINIMIZER) h∗i = arg min h∈H LDi(h) (LOCAL TRUE RISK MINIMIZER) h̄∗ = arg min h∈H LD̄(h) (GLOBAL EMPIRICAL RISK MINIMIZER)
ĥ∗loc,i = arg min h∈H L̂Di(αih+ (1− αi)h̄∗) (MIXED EMPIRICAL RISK MINIMIZER) h∗loc,i = arg min h∈H LDi(αih+ (1− αi)h̄∗) (MIXED TRUE RISK MINIMIZER)
where L̂Di(h) and LDi(h) denote the empirical and true risks on Di, respectively. From a high-level technical view, since we wish to bound the risk of the mixed model on local distribution Di, first we need to utilize the convex property of the risk function, and decompose it into two parts: LDi ( ĥ∗loc,i ) and LDi ( h̄∗ ) . To bound LDi ( ĥ∗loc,i ) , a natural idea is to characterize
it by the risk of optimal model LDi (h∗i ), plus some excess risk. However, due to fact that ĥ∗loc,i is 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̂∗i . This drift can be depicted by the hypothesis capacity, so that is our motivation to define λH(S) to quantify the empirical loss discrepancy over S among pair of hypotheses in H. We have to admit that there should be a tighter theory to bound this drift, depending how global model is incorporated, which we leave it as a future work.
The following simple result will be useful in the proof of generalization.
Lemma 1. Let H be a hypothesis class and D and D′ denote two probability measures over space Ξ. Let LD(h) = E(x,y)∼D [` (h(x), y)] denote the risk of h over D . If the loss function `(·) is bounded by B, then for every h ∈ H:
LD(h) ≤ LD′(h) +B‖D − D′‖1, (9)
where ‖D − D′‖1 = ∫ Ξ |P(x,y)∼D − P(x,y)∼D′ |dxdy.

heading: Proof.
text: LD(h) ≤ LD′(h) + |LD(h)− LD′(h)| ≤ LD(h) + ∫
Ξ
|`(y, h(x))||P(x,y)∼D − P(x,y)∼D′ |dxdy
= LD(h) +B‖D − D′‖1.
Proof of Theorem 1 We now turn to proving the generalization bound for the proposed APFL algorithm. Recall that for the classification task we 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:
LDi(h∗αi) ≤ 2α 2 iLDi ( ĥ∗loc,i ) + 2(1− αi)2LDi ( h̄∗(x) ) . (10)
We start with the classification case first. Note that, hinge loss: max{0, 1 − z} is convex in z, so max{0, 1− y(αih+ (1−αi)h′)} ≤ αi max{0, 1− yh}+ (1−αi) max{0, 1− yh′}, according to
Jensen’s inequality. Hence, we have:
LDi(h∗αi) = LDi(αiĥ ∗ loc,i + (1− αi)h̄∗) = E(x,y)∼Di ( max{0, 1− y(αiĥ∗loc,i(x) + (1− αi)h̄∗(x))} )2
= E(x,y)∼Di ( αi max{0, 1− yĥ∗loc,i(x)}+ (1− αi) max{0, 1− yh̄∗(x)} )2 ≤ 2α2iE(x,y)∼Di ( max{0, 1− yĥ∗loc,i(x)}
)2 + 2(1− αi)2E(x,y)∼Di ( max{0, 1− yh̄∗(x)}
)2 ≤ 2α2iLDi ( ĥ∗loc,i ) + 2(1− αi)2LDi ( h̄∗ ) .
For regression case:
LDi(h∗αi) = LDi(αiĥ ∗ loc,i + (1− αi)h̄∗) = E(x,y)∼Di ∥∥∥y − (αiĥ∗loc,i(x) + (1− αi)h̄∗(x))∥∥∥2
= E(x,y)∼Di ∥∥∥αiy − αiĥ∗loc,i(x) + (1− αi)y − (1− αi)h̄∗(x)∥∥∥2
≤ 2α2iE(x,y)∼Di ∥∥∥y − ĥ∗loc,i(x)∥∥∥2 + 2(1− αi)2E(x,y)∼Di ∥∥y − h̄∗(x)∥∥2
≤ 2α2iLDi ( ĥ∗loc,i ) + 2(1− αi)2LDi ( h̄∗ )
Thus we can conclude:
LDi(h∗αi) ≤ 2α 2 i LDi ( ĥ∗loc,i ) ︸ ︷︷ ︸
T1
+2(1− αi)2 LDi ( h̄∗ )︸ ︷︷ ︸
T2
. (11)
We proceed to bound the terms T1 and T2 in RHS of above inequality. We first bound T1 as follows. The first step is to utilize uniform VC dimension error bound over H Mohri et al. (2018); ShalevShwartz & Ben-David (2014):
∀h ∈ H, |LDi(h)− L̂Di(h)| ≤ C
√ d+ log(1/δ)
mi ,
where C is constant factor. So we can bound T1 as:
T1 = LDi(ĥ∗loc,i) = LDi(h∗i ) + LDi(ĥ∗loc,i)− LDi(h∗i ) = LDi(h∗i )
+ LDi(ĥ∗loc,i)− L̂Di(ĥ∗loc,i)︸ ︷︷ ︸ ≤C √ d+log(1/δ)
mi
+L̂Di(ĥ∗loc,i)− L̂Di(h∗i ) + L̂Di(h∗i )− LDi(h∗i )︸ ︷︷ ︸ ≤C √ d+log(1/δ)
mi
≤ LDi(h∗i ) + 2C
√ d+ log(1/δ)
mi + L̂Di(ĥ∗loc,i)− L̂Di(ĥ∗i ).
Note that
L̂Di(ĥ∗loc,i)− L̂Di(ĥ∗i ) ≤ G 1 |Si| ∑
(x,y)∈Si
|ĥ∗loc,i(x)− ĥ∗i (x)| ≤ GλH(Si),
As a result we can bound T1 by:
T1 ≤ LDi(h∗i ) + 2C
√ d+ log(1/δ)
mi +GλH(Si).
We now turn to bounding T2. Plugging Lemma 1 in (11) and using uniform generalization risk bound will immediately give:
T2 ≤ L̂D̄(h̄∗) +B2‖D − D̄‖1 + C √ d+ log(1/δ)
m .
Plugging T1 and T2 back into (11) concludes the proof. Remark 3. One thing worth mentioning is that, we 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 a linear model w with the constraint ‖w‖ ≤ 1, and also the data tuples (x, y) are drawn from some bounded domain, then the loss is obviously bounded by some finite real value.
Remark 4. As LDi ( ĥ∗loc,i ) is the risk of the empirical risk minimizer on Di after incorporating a
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 our 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 target domains but measured in absolute distance, ‖ · ‖1. 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 tighter divergence measure on distributions as an open question.

heading: E PROOF OF CONVERGENCE RATE IN CONVEX SETTING
text: 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 as 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); 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, our goal is to find the convergence rate of the mixed model, 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 us consider the simple case for now where we set K = n (all device participate averaging). We define three virtual sequences: {w(t)}Tt=1, {v̄(t)}Tt=1 and {v̂ (t)}Tt=1 wherew(t) = 1n ∑n j=1w (t) i ,v̄ (t) i = αiv (t) i +(1−αi)w (t) i v̂ (t) i = αiv (t) i + (1−αi)w(t). Since the personalized model incorporates 1−αi 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 v̂
(t) i and global model w (t) differ from each other at each iteration. To be more specific, we study the distance between gradients ‖∇fi(v̂(t)i ) − ∇F (w(t))‖2. Surprisingly, we relate this distance to gradient diversity, personalized model convergence, global model convergence and local-global optimality gap:
E [ ‖∇fi(v̂(t)i )−∇F (w (t))‖2 ] ≤ 6ζi + 2L2E [ ‖v̂(t)i − v ∗‖2 ] + 6L2E [ ‖w(t) −w∗‖2 ] + 6L2∆i.
E [ ‖v̂(t)i − v∗‖2 ] and E [ ‖w(t) −w∗‖2 ] will converge very fast under smooth strongly convex
objective, and ζi and ∆i will serve as residual error that indicates the heterogeneity among local functions.
Algorithm 2: Local Descent APFL (without sampling)
input: Mixture weights α1, · · · , αn, Synchronization gap τ , Local models v(0)i for i ∈ [n] and local version of global model w(0)i for i ∈ [n]. for t = 0, · · · , T do if t not divides τ then
w (t) i = ∏ W ( w (t−1) i − ηt∇fi ( w (t−1) i ; ξ t i )) v
(t) i = ∏ W ( v (t−1) i − ηt∇vfi ( v̄ (t−1) i ; ξ t i )) v̄
(t) i = αiv (t) i + (1− αi)w (t) i
else each client sends w(t)j to the server
w(t) = 1n ∑n j=1w (t) j
server broadcast w(t) to all clients end
end for i = 1, · · · , n do
output: Personalized model: v̂i = 1ST ∑T t=1 pt(αiv (t) i + (1− αi) 1n ∑n j=1w (t) j );
Global model: ŵ = 1nST ∑T t=1 pt ∑n j=1w (t) j .
end

heading: E.1 PROOF WITHOUT SAMPLING
text: Before giving the proof of convergence analysis of the Algorithm 1 in the main paper, we first discuss a warm-up case: local descent APFL without client sampling. As Algorithm 2 shows, all clients will participate in the averaging stage every τ 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 without Sampling). If each client’s objective function is µ-strongly convex and L-smooth, and satisfies Assumption 1, using Algorithm 2, choosing the mixing weight αi ≥ max{1 − 14√6κ , 1 − 1 4 √ 6κ √ µ }, learning rate
ηt = 16 µ(t+a) , where a = max{128κ, τ}, and using average scheme ŵ = 1
nST
∑T t=1 pt ∑n j=1w (t) j ,
where pt = (t+ a)2, ST = ∑T t=1 pt, then the following convergence holds:
E [F (ŵ)]− F (w∗) ≤ O ( µ T 3 ) +O
( κ2τ ( σ2 + τ ζ
n ) µT 2 ) +O ( κ2τ ( σ2 + τ ζ n ) lnT µT 3 ) +O ( σ2 nT ) ,
where w∗ = arg minw F (w) 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 2. Theorem 5 (Personalized model convergence of Local Descent APFL without Sampling). If each client’s objective function is µ-strongly convex and L-smooth, and satisfies Assumption 1, using Algorithm 2, choosing the mixing weight αi ≥ max{1− 14√6κ , 1− 1 4 √ 6κ √ µ }, learning rate ηt = 16µ(t+a) , where a = max{128κ, τ}, and using average scheme v̂i =
1 ST ∑T t=1 pt(αiv (t) i + (1 − αi) 1n ∑n j=1w (t) j ), where pt = (t + a) 2, ST = ∑T t=1 pt,
and f∗i is the local minimum of the ith client, then the following convergence holds for all i ∈ [n]:
E[fi(v̂i)]− f∗i ≤ O ( µ T 3 ) + α2iO ( σ2 µT ) + (1− αi)2O ( ζi µ + κL∆i ) + (1− αi)2 ( O ( κL lnT
T 3
) +O ( κ2σ2
µnT
) +O ( κ2τ ( σ2 + τ(ζi + ζ n ) )
µT 2
) +O ( κ4τ ( σ2 + 2τ ζ n ) µT 2 )) .
Proof. Proof is deferred to Appendix E.1.3.

heading: E.1.1 PROOF OF USEFUL LEMMAS
text: Before giving the proof of Theorem 4 and 5, we first prove few useful lemmas. Recall that we define virtual sequences {w(t)}Tt=1,{v̄ (t) i }Tt=1,{v̂ (t) i }Tt=1 wherew(t) = 1n ∑n i=1w (t) i ,v̄ (t) i = αiv (t) i + (1− αi)w (t) i ,v̂ (t) i = αiv (t) i + (1− αi)w(t).
We start with the following lemma that bounds the difference between the gradients of local objective and global objective at local and global models. Lemma 2. For Algorithm 2, at each iteration, the gap between local gradient and global gradient is bounded by
E [ ‖∇fi(v̂(t)i )−∇F (w (t))‖2 ] ≤ 2L2E [ ‖v̂(t)i − v ∗‖2 ] + 6ζi + 6L 2E [ ‖w(t) −w∗‖2 ] + 6L2∆i.
Proof. From the smoothness assumption and by applying the Jensen’s inequality we have: E [ ‖∇fi(v̂(t)i )−∇F (w (t))‖2 ]
≤ 2E [ ‖∇fi(v̂(t)i )−∇fi(v ∗ i )‖2 ] + 2E [ ‖∇fi(v∗i )−∇F (w(t))‖2 ] ≤ 2L2E [ ‖v̂(t)i − v ∗‖2 ] + 6E [ ‖∇fi(v∗i )−∇fi(w∗)‖2
] + 6E [ ‖∇fi(w∗)−∇F (w∗)‖2 ] + 6E [ ‖∇F (w∗)−∇F (w(t))‖2
] ≤ 2L2E [ ‖v̂(t)i − v ∗‖2 ] + 6L2E [ ‖v∗i −w∗‖2 ] + 6ζi + 6L 2E [ ‖w(t) −w∗‖2
] ≤ 2L2E [ ‖v̂(t)i − v ∗‖2 ] + 6L2∆i + 6ζi + 6L 2E [ ‖w(t) −w∗‖2 ] .
Lemma 3 (Local model deviation without sampling). For Algorithm 2, at each iteration, the deviation between each local version of the global model w(t)i and the global model w
(t) is bounded by:
E [ ‖w(t) −w(t)i ‖ 2 ] ≤ 3τσ2η2t−1 + 3(ζi + ζ
n )τ2η2t−1,
1
n n∑ i=1 E [ ‖w(t) −w(t)i ‖ 2 ] ≤ 3τσ2η2t−1 + 6τ2 ζ n η2t−1,
where ζn = 1 n ∑n i=1 ζi.
Proof. According to Lemma 8 in Woodworth et al. (2020a):
E [ ‖w(t) −w(t)i ‖ 2 ] ≤ 1 n n∑ j=1 E [ ‖w(t)j −w (t) i ‖ 2 ]
≤ 3 ( σ2 + ζiτ + ζ
n τ ) t−1∑ p=tc η2p t−1∏ q=p+1 (1− µηq)
1
n n∑ i=1 E [ ‖w(t) −w(t)i ‖ 2 ] ≤ 1 n2 n∑ i=1 n∑ j=1 E [ ‖w(t)j −w (t) i ‖ 2 ]
≤ 3 ( σ2 + 2τ ζ
n ) t−1∑ p=tc η2p t−1∏ q=p+1 (1− µηq) .
Plugging in ηq = 16µ(a+q) yields:
E [ ‖w(t) −w(t)i ‖ 2 ] ≤ 3 ( σ2 + ζiτ + ζ
n τ ) t−1∑ p=tc η2p t−1∏ q=p+1 a+ q − 16 a+ q
≤ 3 ( σ2 + ζiτ + ζ
n τ ) t−1∑ p=tc η2p t−1∏ q=p+1 a+ q − 16 a+ q
≤ 3 ( σ2 + ζiτ + ζ
n τ ) t−1∑ p=tc η2p t−1∏ q=p+1 a+ q − 2 a+ q
≤ 3 ( σ2 + ζiτ + ζ
n τ ) t−1∑ p=tc η2p (a+ p− 1)(a+ p) (a+ t− 2)(a+ t− 1)
≤ 3 ( σ2 + ζiτ + ζ
n τ ) t−1∑ p=tc η2p η2t−1 η2p
≤ 3τ ( σ2 + ζiτ + ζ
n τ
) η2t−1.
Similarly,
1
n n∑ i=1 E [ ‖w(t) −w(t)i ‖ 2 ] ≤ 3τσ2η2t−1 + 6τ2 ζ n η2t−1.
Lemma 4. (Convergence of global model) Let w(t) = 1n ∑n i=1w (t) i . Under the setting of Theorem 5, we have:
E [ ‖w(T+1) −w∗‖2 ] ≤ a 3 (T + a)3 E [ ‖w(1) −w∗‖2 ] + ( T + 16 ( 1
a+ 1 + ln(T + a) )) 1536a2τ (σ2 + 2τ ζn)L2 (a− 1)2µ4(T + a)3 + 128σ2T (T + 2a) nµ2(T + a)3 .
Proof. Using the updating rule and non-expensive property of projection, as well as applying strong convexity and smoothness assumptions yields:
E [ ‖w(t+1) −w∗‖2 ] ≤ E
[∥∥∥∥∥w(t) −w(t) − ηt 1n n∑ j=1 ∇fj(w(t)j ; ξ t j)−w∗ ∥∥∥∥∥ 2]
≤ E [ ‖w(t) −w∗‖2 ] − 2ηtE
[〈 1
n n∑ j=1 ∇fj(w(t)j ),w (t) −w∗
〉]
+ η2t σ2
n + η2tE [∥∥∥∥∥ 1n n∑ j=1 ∇fj(w(t)j ) ∥∥∥∥∥ 2]
≤ E [ ‖w(t) −w∗‖2 ] − 2ηtE [〈 ∇F (w(t)),w(t) −w∗ 〉] + η2t σ2
n + η2t E [∥∥∥∥∥ 1n n∑ j=1 ∇fj(w(t)j ) ∥∥∥∥∥ 2]
︸ ︷︷ ︸ T1
−2ηtE
[〈 1
n n∑ j=1 ∇fj(w(t)j )−∇F (w (t)),w(t) −w∗ 〉] ︸ ︷︷ ︸
T2 ≤ (1− µηt)E [ ‖w(t) −w∗‖2 ] − 2ηt(E[F (w(t))]− F (w∗)) + η2t σ2
n + T1 + T2, (12)
where at the last step we used the strongly convex property.
Now we are going to bound T1. By the Jensen’s inequality and smoothness, we have:
T1 ≤ 2η2tE  ∥∥∥∥∥∥ 1n n∑ j=1 ∇fj(w(t)j )−∇F (w (t)) ∥∥∥∥∥∥ 2 + 2η2tE [∥∥∥∇F (w(t))∥∥∥2]
≤ 2η2tL2 1
n n∑ j=1 E [ ‖w(t)j −w (t)‖2 ] + 4η2tL ( E [ F (w(t)) ] − F (w∗) ) (13)
Then, we bound T2 as:
T2 ≤ ηt  2 µ E  ∥∥∥∥∥∥ 1n n∑ j=1 ∇fj(w(t)j )−∇F (w (t)) ∥∥∥∥∥∥ 2 + µ 2 E [ ‖w(t) −w∗‖2 ] ≤ 2ηtL 2
µ
1
n n∑ j=1 E [∥∥∥w(t)j −w(t)∥∥∥2]+ µηt2 E [‖w(t) −w∗‖2] . (14)
Now, by plugging back T1 and T2 from (13) and (14) in (12), we have: E [ ‖w(t+1) −w∗‖2 ] ≤ (
1− µηt 2
) E [ ‖w(t) −w∗‖2 ] −(2ηt − 4η2tL)︸ ︷︷ ︸
≤−ηt
( E [ F (w(t)) ] − F (w∗) ) + η2t σ2
n
+
( 2ηtL 2
µ + 2η2tL 2
) 1
n n∑ j=1 E [∥∥∥w(t)j −w(t)∥∥∥2] (15)
≤ (
1− µηt 2
) E [ ‖w(t) −w∗‖2 ] + η2t σ2
n +
( 2ηtL 2
µ + 2η2tL 2
) 1
n n∑ j=1 E [∥∥∥w(t)j −w(t)∥∥∥2] .
Now, by using Lemma 3 we have: E [ ‖w(t+1) −w∗‖2 ] ≤ (
1− µηt 2
) E [ ‖w(t) −w∗‖2 ] + ( 2ηtL 2
µ + 2η2tL 2
) 3τ ( σ2 + 2τ ζ
n
) η2t−1 + η 2 t σ2
n .
Note that (1− µηt2 ) pt ηt = µ(t+a) 2(t−8+a) 16 ≤ µ(t−1+a)3 16 = pt−1 ηt−1 , so we multiply ptηt on both sides and do the telescoping sum: pT ηT E [ ‖w(T+1) −w∗‖2
] ≤ p0 η0 E [ ‖w(1) −w∗‖2 ] + T∑ t=1 ( 2L2 µ + 2ηtL 2 ) 3τ ( σ2 + 2τ ζ n ) ptη 2 t−1 + T∑ t=1 ptηt σ2 n
≤ p0 η0
E [ ‖w(1) −w∗‖2 ] + T∑ t=1 ( 2L2 µ + 2ηtL 2 ) 3τ ( σ2 + 2τ ζ n ) 256a2 µ2(a− 1)2 + T∑ t=1 ptηt σ2 n .
(16) Then, by re-arranging the terms will conclude the proof:
E [ ‖w(T+1) −w∗‖2 ] ≤ a 3 (T + a)3 E [ ‖w(1) −w∗‖2
] + ( T + 16 ( 1
a+ 1 + ln(T + a) )) 1536a2τ (σ2 + 2τ ζn)L2 (a− 1)2µ4(T + a)3 + 128σ2T (T + 2a) nµ2(T + a)3 ,
where we use the inequality ∑T t=1 1 t+a ≤ 1 a+1 + ∫ T 1 1 t+a < 1 a+1 + ln(T + a).

heading: E.1.2 PROOF OF THEOREM 4
text: Proof. According to (15) and (16) in the proof of Lemma 4 we have:
pT ηT
E [ ‖w(T+1) −w∗‖2 ] ≤ p0 η0 E [ ‖w(1) −w∗‖2 ] − T∑ t=1 pt ( E [ F (w(t)) ] − F (w∗) ) +
T∑ t=1 ( 2L2 µ + 2ηtL 2 ) 3τ ( σ2 + 2τ ζ n ) 256a2 µ2(a− 1)2 + T∑ t=1 ptηt σ2 n ,
re-arranging term and dividing both sides by ST = ∑T t=1 pt > T 3 yields:
1
ST T∑ t=1 pt ( E [ F (w(t)) ] − F (w∗) ) ≤ p0 ST η0 E [ ‖w(1) −w∗‖2 ] + 1
ST T∑ t=1 ( 2L2 µ + 2ηtL 2 ) 3τ ( σ2 + 2τ ζ n ) 256a2 µ2(a− 1)2 + 1 ST T∑ t=1 ptηt σ2 n
≤ O ( µ T 3 ) +O
( κ2τ ( σ2 + 2τ ζ
n ) µT 2 ) +O ( κ2τ ( σ2 + 2τ ζ n ) lnT µT 3 ) +O ( σ2 nT ) .
Recall that ŵ = 1nST ∑T t=1 ∑n j=1w (t) j and convexity of F , we can conclude that:
E [F (ŵ)]− F (w∗) ≤ O ( µ T 3 ) +O
( κ2τ ( σ2 + 2τ ζ
n ) µT 2 ) +O ( κ2τ ( σ2 + 2τ ζ n ) lnT µT 3 ) +O ( σ2 nT ) .

heading: E.1.3 PROOF OF THEOREM 5
text: Proof. Recall that we defined virtual sequences {w(t)}Tt=1 where w(t) = 1n ∑n i=1w (t) i and v̂ (t) i = αiv (t) i + (1− αi)w(t), then by the updating rule and non-expensiveness of projection we have:
E [ ‖v̂(t+1)i − v ∗ i ‖2 ]
≤ E [∥∥∥∥∥v̂(t)i − α2i ηt∇fi(v̄(t)i )− (1− αi)ηt 1n n∑ j=1 ∇fj(w(t)j )− v ∗ i ∥∥∥∥∥ 2]
+ E [∥∥∥∥∥α2i ηt(∇fi(v̄(t)i )−∇fi(v̄(t)i ; ξti)) + (1− αi)ηt 1n ∑ j∈Ut ( ∇fj(w(t)j )−∇fj(w (t) j ; ξ t j) )∥∥∥∥∥ 2]
≤ E [ ‖v̂(t)i − v ∗ i ‖2 ] − 2E [〈 α2i ηt∇fi(v̄ (t) i ) + (1− αi)ηt 1
n n∑ j=1 ∇fj(w(t)j ), v̂ (t) i − v ∗ i
〉]
+ η2tE [∥∥∥∥∥α2i∇fi(v̄(t)i ) + (1− αi) 1n n∑ j=1 ∇fj(w(t)j ) ∥∥∥∥∥ 2] + α2i η 2 t σ 2 + (1− αi)2η2t σ2 n
= E [ ‖v̂(t)i − v ∗ i ‖2 ] −2(α2i + 1− αi)ηtE [〈 ∇fi(v̄(t)i ), v̂ (t) i − v ∗ i 〉] ︸ ︷︷ ︸
T1
−2ηt(1− αi)E
[〈 1
n n∑ j=1 ∇fj(w(t)j )−∇fi(v̄ (t) i ), v̂ (t) i − v ∗ i 〉] ︸ ︷︷ ︸
T2
+ η2t E [ ‖α2i∇fi(v̄ (t) i ) + (1− αi) 1
n n∑ j=1 ∇fj(w(t)j )‖ 2 ] ︸ ︷︷ ︸
T3
+α2i η 2 t σ 2 + (1− αi)2η2t σ2
n . (17)
Now, we bound the term T1 as follows: T1 = −2ηt(α2i + 1− αi)E [〈 ∇fi(v̂(t)i ), v̂ (t) i − v ∗ i 〉] − 2ηt(α2i + 1− αi)E [〈 ∇fi(v̄(t)i )−∇fi(v̂ (t) i ), v̂ (t) i − v ∗ i
〉] ≤ −2ηt(α2i + 1− αi) ( E [ fi(v̂ (t) i ) ] − fi(v∗i ) + µ 2 E [ ‖v̂(t)i − v ∗ i ‖2 ])
+ (α2i + 1− αi)ηt (
8L2 µ(1− 8(αi − α2i )) E [ ‖v̂(t)i − v̄ (t) i ‖ 2 ] + µ(1− 8(αi − α2i )) 8 E [ ‖v̂(t)i − v ∗ i ‖2 ])
≤ −2ηt(α2i + 1− αi) ( E [ fi(v̂ (t) i ) ] − fi(v∗i ) + µ 2 E [ ‖v̂(t)i − v ∗ i ‖2 ])
+ ηt
( 8L2(1− αi)2 µ(1− 8(αi − α2i )) E [ ‖w(t) −w(t)i ‖ 2 ] + µ(1− 8(αi − α2i )) 8 E [ ‖v̂(t)i − v ∗ i ‖2 ])
≤ −2ηt(α2i + 1− αi) ( E [ fi(v̂ (t) i ) ] − fi(v∗i ) ) − 7µηt 8 E [ ‖v̂(t)i − v ∗ i ‖2 ]
+ 8ηtL
2(1− αi)2 µ(1− 8(αi − α2i )) E [ ‖w(t) −w(t)i ‖ 2 ] , (18)
where we use the fact (α2i + 1 − αi) ≤ 1. Note that, because we set αi ≥ max{1 − 14√6κ , 1 − 1 4 √ 6κ √ µ }, and hence 1 − 8(αi − α2i ) ≥ 0, so in the second inequality we can use the arithmeticgeometry inequality.
Next, we turn to bounding the term T2 in (17):
T2 = −2ηt(1− αi)E
[〈 1
n n∑ j=1 ∇fj(w(t)j )−∇fi(v̄ (t) i ), v̂ (t) i − v ∗ i
〉]
≤ ηt(1− αi)
( 2(1− αi)
µ E [∥∥∥∥∥∇fi(v̄(t)i )− 1n n∑ j=1 ∇fj(w(t)j ) ∥∥∥∥∥ 2] + µ 2(1− αi) E [ ‖v̂(t)i − v ∗ i ‖2 ])
≤ 6(1− αi) 2ηt
µ
( E [∥∥∥∇fi(v̄(t)i )−∇fi(v̂(t)i )∥∥∥2]+ E [∥∥∥∇fi(v̂(t)i )−∇F (w(t))∥∥∥2]
+E [∥∥∥∥∥∇F (w(t))− 1n n∑ j=1 ∇fj(w(t)j ) ∥∥∥∥∥ 2]) + ηtµ 2 E [ ‖v̂(t)i − v ∗ i ‖2 ]
≤ 6(1− αi) 2ηt
µ
( L2E [∥∥∥w(t) −w(t)i ∥∥∥2]+ E [∥∥∥∇fi(v̂(t)i )−∇F (w(t))∥∥∥2]
+E [∥∥∥∥∥∇F (w(t))− 1n n∑ j=1 ∇fj(w(t)j ) ∥∥∥∥∥ 2]) + ηtµ 2 E [ ‖v̂(t)i − v ∗ i ‖2 ] . (19)
And finally, we bound the term T3 in (17) as follows:
T3 = E [∥∥∥∥∥α2i∇fi(v̄(t)i ) + (1− αi) 1n n∑ j=1 ∇fj(w(t)j ) ∥∥∥∥∥ 2]
≤ 2(α2i + 1− αi)2E [ ‖∇fi(v̄(t)i )‖ 2 ] + 2E [∥∥∥∥∥(1− αi) ( 1 n n∑ j=1 ∇fj(w(t)j )−∇fi(v̄ (t) i ) )∥∥∥∥∥ 2]
≤ 2 ( 2(α2i + 1− αi)2E [ ‖∇fi(v̂(t)i )−∇f ∗ i ‖2 ] + 2(α2i + 1− αi)2E [ ‖∇fi(v̄(t)i )−∇fi(v̂ (t) i )‖ 2 ])
+ 2(1− αi)2E [∥∥∥∥∥ 1n n∑ j=1 ∇fj(w(t)j )−∇fi(v̄ (t) i ) ∥∥∥∥∥ 2]
≤ 8L(α2i + 1− αi) ( E [ fi(v̂ (t) i ) ] − f∗i ) + 4(1− αi)2L2E [ ‖w(t) −w(t)i ‖ 2 ]
+ 6(1− αi)2 ( L2E [∥∥∥w(t) −w(t)i ∥∥∥2]+ E [∥∥∥∇fi(v̂(t)i )−∇F (w(t))∥∥∥2] + 1
n n∑ j=1 L2E [∥∥∥w(t) −w(t)j ∥∥∥2] ) . (20)
Now, using Lemma 3, (1 − αi)2 ≤ 1 and plugging back T1, T2, and T3 from (18), (19), and (20) into (17), yields:
E [ ‖v̂(t+1)i − v ∗ i ‖2 ]
≤ (
1− 3µηt 8
) E [ ‖v̂(t)i − v ∗ i ‖2 ] − 2(ηt − 4η2tL)(α2i + 1− αi) ( E [ fi(v̂ (t) i ) ] − fi(v∗i ) ) + ( 8ηtL 2(1− αi)2
µ(1− 8(αi − α2i )) +
6(1− αi)2ηtL2
µ + 10(1− αi)2η2tL2
) E [∥∥∥w(t) −w(t)i ∥∥∥2]
+
( 6(1− αi)2ηtL2
µ + 6(1− αi)2η2tL2
) 1
n n∑ j=1 E [∥∥∥w(t) −w(t)j ∥∥∥2]
+ ( 6ηt µ + 6η2t ) (1− αi)2E [∥∥∥∇F (w(t))−∇fi(v̂(t)i )∥∥∥2]+ α2i η2t σ2 + (1− αi)2η2t σ2n , ≤ (
1− 3µηt 8
) E [ ‖v̂(t)i − v ∗ i ‖2 ] − 2(ηt − 4η2tL)(α2i + 1− αi) ( E [ fi(v̂ (t) i ) ] − fi(v∗i ) ) + ( 8ηtL 2(1− αi)2
µ(1− 8(αi − α2i )) +
6(1− αi)2ηtL2
µ + 10(1− αi)2η2tL2
) 3τ ( σ2 + (ζi + ζ
n )τ
) η2t−1
+
( 6(1− αi)2ηtL2
µ + 6(1− αi)2η2tL2
) 3τ ( σ2 + 2 ζ
n τ
) η2t−1
+ ( 6ηt µ + 6η2t ) (1− αi)2E [∥∥∥∇F (w(t))−∇fi(v̂(t)i )∥∥∥2]︸ ︷︷ ︸ T4 +α2i η 2 t σ 2 + (1− αi)2η2t σ2 n , (21)
where using Lemma 2 we can bound T4 as:
T4 ≤ 6ηt µ
(1− αi)2 ( 2L2E [ ‖v̂(t)i − v ∗‖2 ] + 6ζi + 6L 2E [ ‖w(t) −w∗‖2 ] + 6L2∆i ) + 6η2t (1− αi)2 ( 2L2E [ ‖v̂(t)i − v ∗‖2 ] + 6ζi + 6L 2E [ ‖w(t) −w∗‖2 ] + 6L2∆i ) . (22)
Note that we choose αi ≥ max{1 − 14√6κ , 1 − 1 4 √ 6κ √ µ }, hence 12L 2(1−αi)2 µ ≤ µ 8 and 12L
2(1 − αi) 2 ≤ µ8 , thereby we have:
T4 ≤ µηt 4 ‖v̂(t)i − v
∗‖2 + 36ηt ( 1
µ + ηt
) (1− αi)2 ( ζi + L 2E [ ‖w(t) −w∗‖2 ] + L2∆i ) .
Now, using Lemma 4 we have:
T4 ≤ µηt 4
E [ ‖v̂(t)i − v ∗‖2 ] + 36ηt ( 1
µ + ηt ) (1− αi)2(
ζi + L 2
( a3 (t+ a− 1)3E [ ‖w(1) −w∗‖2 ] + ( t+ 16 ( 1
a+ 1 + ln(t+ a)
)) 1536τ ( σ2 + 2τ ζ
n
) L2
µ4(t+ a− 1)3 + 128σ2t(t+ 2a) nµ2(t+ a− 1)3
) + L2∆i ) . (23)
By plugging back T4 from (23) in (21) and using the fact−(ηt−4η2tL) ≤ − 12ηt, and (α 2 i+1−αi) ≥ 3 4 , we have:
E [ ‖v̂(t+1)i − v ∗ i ‖2 ]
≤ (1− µηt 8
)E [ ‖v̂(t)i − v ∗ i ‖2 ] − 3ηt
4
( E [ fi(v̂ (t) i ) ] − fi(v∗i ) ) + α2i η 2 t σ 2 + (1− αi)2η2t σ2
n
+
( 8ηtL 2(1− αi)2
µ(1− 8(αi − α2i )) +
6(1− αi)2ηtL2
µ + 10(1− αi)2η2tL2
) 3τ ( σ2 + (ζi + ζ
n )τ
) η2t−1
+
( 6(1− αi)2ηtL2
µ + 6(1− αi)2η2tL2
) 3τ ( σ2 + 2 ζ
n τ
) η2t−1
+ 36ηt
( 1
µ + ηt
) (1− αi)2 ζi + L2 a3E [ ‖w(1) −w∗‖2 ] (t− 1 + a)3
+ ( t+ 16 ( 1
a+ 1 + ln(t+ a)
)) 1536τ ( σ2 + 2τ ζ
n
) L2
µ4(t+ a− 1)3 + 128σ2t(t+ 2a) nµ2(t− 1 + a)3 + ∆i
)) .
Note that (1− µηt8 ) pt ηt ≤ pt−1ηt−1 where pt = (t+a) 2, so, we multiply ptηt on both sides, and re-arrange the terms:
3pt 4
( E [ fi(v̂ (t) i ) ] − fi(v∗i ) ) ≤ pt−1 ηt−1 E [ ‖v̂(t)i − v ∗ i ‖2 ] − pt ηt E [ ‖v̂(t+1)i − v ∗ i ‖2 ] + ptηt ( α2iσ 2 + (1− αi)2 σ2 n
) + ( 8L2(1− αi)2
µ(1− 8(αi − α2i )) +
6(1− αi)2L2
µ + 10(1− αi)2ηtL2
) 3τ ( σ2 + (ζi + ζ
n )τ
) ptη 2 t−1
+
( 6(1− αi)2L2
µ + 6(1− αi)2ηtL2
) 3τ ( σ2 + 2 ζ
n τ
) ptη 2 t−1 + 36pt ( 1
µ + ηt
) (1− αi)2 ( ζi + L 2∆i )
+ 36pt
( 1
µ + ηt
) (1− αi)2
L2 (
a3
(t− 1 + a)3 + (t+ 16Θ(ln t)) 1536τ
( σ2 + 2τ ζ
n
) L2
µ4(t+ a− 1)3 + 128σ2t(t+ 2a) nµ2(t− 1 + a)3
) .
By applying the telescoping sum and dividing both sides by ST = ∑T t=1 pt ≥ T 3 we have:
fi(v̂i)− fi(v∗i )
≤ 1 ST T∑ t=1 pt(fi(v̂ (t) i )− fi(v ∗ i ))
≤ 4p0E
[ ‖v̂(1)i − v ∗ i ‖2 ]
3η0ST +
1
ST
4
3 T∑ t=1 ptηt ( α2iσ 2 + (1− αi)2 σ2 n )
+ 1
ST
4
3 T∑ t=1 ( 8L2(1− αi)2 µ(1− 8(αi − α2i )) + 6(1− αi)2L2 µ + 10(1− αi)2ηtL2 ) 3τ ( σ2 + (ζi + ζ n )τ ) ptη 2 t−1
+ 1
ST
4
3 T∑ t=1 ( 6(1− αi)2L2 µ + 6(1− αi)2ηtL2 ) 3τ ( σ2 + 2 ζ n τ ) ptη 2 t−1
+ 48(1− αi)2
L2
ST T∑ t=1 pt ( 1 µ + ηt )( a3 (t− 1 + a)3 + (t+ 16Θ(ln t)) 1536τ ( σ2 + 2τ ζ n ) L2 µ4(t+ a− 1)3 + 128σ2t(t+ 2a) nµ2(t− 1 + a)3 ) + 48(1− αi)2 ( ζi + L 2∆i ) 1 ST T∑ t=1 pt ( 1 µ + ηt )
≤ 4p0E
[ ‖v̂(1)i − v ∗ i ‖2 ]
3η0ST +
32T (T + a)
3µST
( α2iσ 2 + (1− αi)2 σ2
n ) + 4(1− αi)2
3
( 8L2T
µ(1− 8(αi − α2i ))ST +
6L2T
µST +
10L2Θ(lnT )
µST
) 3τ ( σ2 + (ζi + ζ
n )τ
) 256a2
µ2(a− 1)2
+ 4
3
( 6(1− αi)2L2T
µST + 6(1− αi)2L2Θ(lnT ) µST
) 3τ ( σ2 + 2 ζ
n τ
) 256a2
µ2(a− 1)2
+ 48(1− αi)2L2 a2
(a− 1)2ST( a3Θ(lnT )
µ +
( T
a + Θ(lnT )
) 1536L2τ ( σ2 + 2τ ζ
n ) µ5 + 64(2a+ 1)σ2T (T + a) naµ3 )
+ 48(1− αi)2L2 a2
(a− 1)2ST
( 16a3π2
6µ + (Θ(lnT ))
1536L2τ ( σ2 + 2τ ζ
n ) µ5 + 2048(2a+ 1)σ2 naµ3 T )
+ 48(1− αi)2 ( ζi + L 2∆i ) 1 ST ( ST µ + 8T (T + 2a) µ ) = O ( µ T 3 ) + α2iO ( σ2 µT ) + (1− αi)2O ( ζi µ + κL∆i
) + (1− αi)2 ( O ( κL lnT
T 3
) +O ( κ2σ2
µnT
) +O ( κ2τ2(ζi + ζ n ) + κ2τσ2
µT 2
) +O ( κ4τ ( σ2 + 2τ ζ n ) µT 2 )) .
where we use the convergence of ∑∞ t=1 ln t t2 −→ O(1), and ∑∞ t=1 1 t2 −→ π2 6 .

heading: E.2 PROOF OF CONVERGENCE OF APFL WITH SAMPLING
text: In this section we 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 6 (Global model convergence of Local Descent APFL). If each client’s objective function is µ-strongly convex and L-smooth, and satisfies Assumption 1, using Algorithm 1, by choosing the learning rate ηt = 16µ(t+a) , where a = max{128κ, τ}, κ = L µ , and using average scheme
ŵ = 1KST ∑T t=1 pt ∑ j∈Ut w (t) j , where pt = (t+ a) 2, ST = ∑T t=1 pt, and letting F ∗ to denote the
minimum of the F , then the following convergence holds:
E [F (ŵ)]− F ∗ ≤ O ( µ T 3 ) +O
( κ2τ ( σ2 + 2τ ζ
K ) µT 2 ) +O ( κ2τ ( σ2 + 2τ ζ K ) lnT µT 3 ) +O ( σ2 KT ) ,
(24)
where τ is the number of local updates (i.e., synchronization gap) .
Proof. The proof is provided in Appendix E.2.2.
Remark 5. It is noticeable that the obtained rate matches the convergence rate of the FedAvg, and if we choose τ = √ T/K, we recover the rate O( √ 1/KT ), which is the convergence rate of well-known local SGD with periodic averaging (Woodworth et al., 2020a).
Now we switch to the proof of the Theorem 2. The proof pipeline is similar to what we did in Appendix E.1.3, non-sampling setting. The only difference is that we use sampling method here, hence, we will introduce the variance depending on sampling size K. Now we first begin with the proof of some technique lemmas.

heading: E.2.1 PROOF OF USEFUL LEMMAS
text: Lemma 5. For Algorithm 1, at each iteration, the gap between local gradient and global gradient is bounded by
E [∥∥∥∥∥∇fi(v̂(t)i )− 1K ∑ j∈Ut ∇fj(w(t)) ∥∥∥∥∥ 2]
≤ 2L2E [ ‖v̂(t)i − v ∗‖2 ] + 6 ( 2ζi + 2 ζ
K
) + 6L2E [ ‖w(t) −w∗‖2 ] + 6L2∆i.
Proof. From the smoothness assumption and by applying the Jensen’s inequality we have:
E [ ‖∇fi(v̂(t)i )− 1
K ∑ j∈Ut
∇fj(w(t))‖2 ]
≤ 2E [ ‖∇fi(v̂(t)i )−∇fi(v ∗ i )‖2 ] + 2E [ ‖∇fi(v∗i )− 1
K ∑ j∈Ut
∇fj(w(t))‖2 ]
≤ 2L2E [ ‖v̂(t)i − v ∗‖2 ] + 6E [ ‖∇fi(v∗i )−∇fi(w∗)‖2 ] + 6E [ ‖∇fi(w∗)− 1
K ∑ j∈Ut
∇fj(w∗)‖2 ] + 6E [ ‖∇ 1
K ∑ j∈Ut ∇fj(w∗)− 1 K ∑ j∈Ut
∇fj(w(t))‖2 ]
≤ 2L2E [ ‖v̂(t)i − v ∗‖2 ] + 6L2E [ ‖v∗i −w∗‖2 ] + 6 ( 2ζi + 2 1
K ∑ j∈Ut ζj
) + 6L2E [ ‖w(t) −w∗‖2 ] ≤ 2L2E [ ‖v̂(t)i − v ∗‖2 ] + 6L2∆i + 6 ( 2ζi + 2 ζ
K
) + 6L2E [ ‖w(t) −w∗‖2 ] .
Lemma 6 (Local model deviation with sampling). For Algorithm 1, at each iteration, the deviation between each local version of the global model w(t)i and the global model w (t) is bounded by:
E [ ‖w(t) −w(t)i ‖ 2 ] ≤ 3τσ2η2t−1 + 3(ζi + ζ
K )τ2η2t−1,
1
K ∑ i∈Ut E [ ‖w(t) −w(t)i ‖ 2 ] ≤ 3τσ2η2t−1 + 6τ2 ζ K η2t−1.
where ζK = 1 K ∑n i=1 ζi.
Proof. According to Lemma 8 in Woodworth et al. (2020a):
E [ ‖w(t) −w(t)i ‖ 2 ] ≤ 1 K ∑ j∈Ut E [ ‖w(t)j −w (t) i ‖ 2 ]
≤ 3 ( σ2 + ζiτ + ζ
K τ ) t−1∑ p=tc η2p t−1∏ q=p+1 (1− µηq)
1
n n∑ i=1 E [ ‖w(t) −w(t)i ‖ 2 ] ≤ 1 n2 n∑ i=1 n∑ j=1 E [ ‖w(t)j −w (t) i ‖ 2 ]
≤ 3 ( σ2 + 2τ ζ
K ) t−1∑ p=tc η2p t−1∏ q=p+1 (1− µηq) .
Then the rest of the proof follows Lemma 3.
Lemma 7. (Convergence of Global Model) Let w(t) = 1K ∑ j∈Ut w (t) j . In Theorem 2’s setting, using Algorithm 1 by choosing learning rate as ηt = 16µ(t+a) , we have:
E [ ‖w(T+1) −w∗‖2 ] ≤ a 3 (T + a)3 E [ ‖w(1) −w∗‖2 ] + ( T + 16 ( 1
a+ 1 + ln(T + a)
)) 1536a2τ ( σ2 + 2τ ζ
K
) L2
(a− 1)2µ4(T + a)3 + 128σ2T (T + 2a) Kµ2(T + a)3 .
Proof. According to the updating rule and non-expensiveness of projection, and the strong convexity we have:
E [ ‖w(t+1) −w∗‖2 ] ≤ E  ∥∥∥∥∥∥w(t) − ηt 1K ∑ j∈Ut ∇fj(w(t)j ; ξ t j)−w∗ ∥∥∥∥∥∥ 2 
≤ E [ ‖w(t) −w∗‖2 ] − 2ηtE 〈 1 K ∑ j∈Ut ∇fj(w(t)j ),w (t) −w∗ 〉 + η2tE  ∥∥∥∥∥∥ 1K ∑ j∈Ut ∇fj(w(t)j ) ∥∥∥∥∥∥ 2 + η2t σ2K
≤ (1− µηt)E [ ‖w(t) −w∗‖2 ] − (2ηt − 2Lη2t )E [ F (w(t))− F (w∗) ] + η2t σ2
K
+ η2t 1
K ∑ j∈Ut L2E [∥∥∥w(t)j −w(t)∥∥∥2]− 2ηtE 〈 1 K ∑ j∈Ut ∇fj(w(t)j )−∇fj(w (t)),w(t) −w∗ 〉 ≤ (1− µηt)E [ ‖w(t) −w∗‖2 ] −(2ηt − 4Lη2t )︸ ︷︷ ︸
≤−ηt
E [ F (w(t))− F (w∗) ] + η2t σ2
K
+ 2η2tL 2 1
K ∑ j∈Ut E [∥∥∥w(t)j −w(t)∥∥∥2]+ 2ηtL2µ 1K ∑ j∈Ut E [∥∥∥w(t)j −w(t)∥∥∥2]+ µηt2 E [‖w(t) −w∗‖2] .
(25)
Then, merging the term, multiplying both sides with ptηt , and do the telescoping sum yields:
pT ηT
E [ ‖w(T+1) −w∗‖2 ] ≤ p0 η0 E [ ‖w(1) −w∗‖2 ] − E[F (w(t))− F (w∗)]
+ T∑ t=1 ( 2L2 µ + 2ηtL 2 ) pt 1 K ∑ j∈Ut E [∥∥∥w(t)j −w(t)∥∥∥2]+ T∑ t=1 ptηt σ2 K .
(26)
Plugging Lemma 6 into (26) yields: pT ηT E [ ‖w(T+1) −w∗‖2 ] ≤ p0 η0 E [ ‖w(1) −w∗‖2 ] − E[F (w(t))− F (w∗)]
+ T∑ t=1 ( 2L2 µ + 2ηtL 2 ) 3ptη 2 t−1τ ( σ2 + 2τ ζ K ) + T∑ t=1 ptηt σ2 K .
(27)
Then, by re-arranging the terms will conclude the proof as
E [ ‖w(T+1) −w∗‖2 ] ≤ a 3 (T + a)3 E [ ‖w(1) −w∗‖2 ] + ( T + 16 ( 1
a+ 1 + ln(T + a) )) 1536a2L2τ (σ2 + 2τ ζK) (a− 1)2µ4(T + a)3
+ 128σ2T (T + 2a)
Kµ2(T + a)3 .

heading: E.2.2 PROOF OF THEOREM 6
text: Proof. According to (28) we have: pT ηT E [ ‖w(T+1) −w∗‖2 ] ≤ p0 η0 E [ ‖w(1) −w∗‖2 ] − E[F (w(t))− F (w∗)]
+ T∑ t=1 ( 2L2 µ + 2ηtL 2 ) 3ptη 2 t−1τ ( σ2 + 2τ ζ K ) + T∑ t=1 ptηt σ2 K .
(28) By re-arranging the terms and dividing both sides by ST = ∑T t=1 pt > T 3 yields:
1
ST T∑ t=1 pt ( E [ F (w(t)) ] − F (w∗) ) ≤ p0 ST η0 E [ ‖w(1) −w∗‖2 ] + 1 ST T∑ t=1 ( 2L2 µ + 2ηtL 2 ) 3ptη 2 t−1τ ( σ2 + 2τ ζ K ) + 1 ST T∑ t=1 ptηt σ2 K
≤ O
µE [ ‖w(1) −w∗‖2 ] T 3 +O(κ2τ (σ2 + 2τ ζK ) µT 2 ) +O ( κ2τ ( σ2 + 2τ ζ K ) lnT µT 3 ) +O ( σ2 KT ) .
Recalling that ŵ = 1nST ∑T t=1 pt ∑n j=1w (t) j , from the convexity of F (·), we can conclude that E [F (ŵ)]− F (w∗) ≤ O ( µ T 3 ) +O ( κ2τ ( σ2 + 2τ ζ K ) µT 2 ) +O ( κ2τ ( σ2 + 2τ ζ K ) lnT µT 3 ) +O ( σ2 KT ) .

heading: E.2.3 PROOF OF THEOREM 2
text: Now we provide the formal proof of Theorem 2. The main difference from without-sampling setting is that only a subset of local models get updated each period due to partial participation of devices, i.e., K out of all n 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 is unbiased, the variance is changed.
Proof. Recall that we defined virtual sequences of {w(t)}Tt=1 where w(t) = 1K ∑ j∈Ut w (t) i and v̂ (t) i = αiv (t) i + (1− αi)w(t). We also define an indicator variable to denote whether ith client was selected at iteration t:
Iti = { 1 if i ∈ Ut 0 else
obviously, E [Iti] = Kn . Then, according to updating rule and non-expensiveness of projection we have:
E [ ‖v̂(t+1)i − v ∗ i ‖2 ]
≤ E [∥∥∥∥∥v̂(t)i − α2i Itiηt∇fi(v̄(t)i )− (1− αi)ηt 1K ∑ j∈Ut ∇fj(w(t)j )− v ∗ i ∥∥∥∥∥ 2]
+ E [∥∥∥∥∥α2i Itiηt (∇fi(v̄(t)i )−∇fi(v̄(t)i ; ξti))+ (1− αi)ηt ( 1 K ∑ j∈Ut ∇fj(w(t)j )− 1 K ∑ j∈Ut ∇fj(w(t)j ; ξ t) )∥∥∥∥∥ 2]
= E [ ‖v̂(t)i − v ∗ i ‖2 ] − 2
〈 K
n α2i ηt∇fi(v̄ (t) i ) + (1− αi)ηt
1
K ∑ j∈Ut ∇fj(w(t)j ), v̂ (t) i − v ∗ i
〉
+ η2tE [∥∥∥∥∥α2i Iti∇fi(v̄(t)i ) + (1− αi) 1K ∑ j∈Ut ∇fj(w(t)j ) ∥∥∥∥∥ 2] + α2i η 2 t 2K2σ2 n2 + (1− αi)2η2t 2σ2 K .
= E [ ‖v̂(t)i − v ∗ i ‖2 ] −2ηt 〈( K
n α2i + 1− αi
) ∇fi(v̄(t)i ), v̂ (t) i − v ∗ i 〉 ︸ ︷︷ ︸
T1
−2ηt(1− αi)E
[〈 1
K ∑ j∈Ut ∇fj(w(t)j )−∇fi(v̄ (t) i ), v̂ (t) i − v ∗ i 〉] ︸ ︷︷ ︸
T2
+ η2t E [∥∥∥∥∥α2i Iti∇fi(v̄(t)i ) + (1− αi) 1K ∑ j∈Ut ∇fj(w(t)j ) ∥∥∥∥∥ 2]
︸ ︷︷ ︸ T3
+α2i η 2 t
2K2σ2
n2 + (1− αi)2η2t
2σ2
K .
Now we switch to bound T1:
T1 = −2ηt( K
n α2i + 1− αi)E
[〈 ∇fi(v̂(t)i ), v̂ (t) i − v ∗ i 〉] − 2ηt( K
n α2i + 1− αi)E
[〈 ∇fi(v̄(t)i )−∇fi(v̂ (t) i ), v̂ (t) i − v ∗ i 〉] ≤ −2ηt( K
n α2i + 1− αi)
( E [ fi(v̂ (t) i ) ] − fi(v∗i ) + µ 2 E [ ‖v̂(t)i − v ∗ i ‖2 ])
+ ( K
n α2i + 1− αi)ηt
( 8L2
µ(1− 8(αi − α2i Kn )) E [ ‖v̂(t)i − v̄ (t) i ‖ 2 ]
+ µ(1− 8(αi − α2i Kn )) 8 E [ ‖v̂(t)i − v ∗ i ‖2 ])
≤ −2ηt( K
n α2i + 1− αi)
( E [ fi(v̂ (t) i ) ] − fi(v∗i ) + µ 2 E [ ‖v̂(t)i − v ∗ i ‖2 ])
+ ηt
( 8L2(1− αi)2
µ(1− 8(αi − Kn α 2 i ))
E [ ‖w(t) −w(t)i ‖ 2 ] + µ(1− 8(αi − Kn α 2 i )) 8 E [ ‖v̂(t)i − v ∗ i ‖2 ])
≤ −2ηt( K
n α2i + 1− αi)
( E [ fi(v̂ (t) i ) ] − fi(v∗i ) ) − 7µηt 8 E [ ‖v̂(t)i − v ∗ i ‖2 ]
+ 8ηtL
2(1− αi)2 µ(1− 8(αi − α2i )) E [ ‖w(t) −w(t)i ‖ 2 ] , (29)
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  ∥∥∥∥∥∥α2i Iti∇fi(v̄(t)i ) + (1− αi) 1K ∑ j∈Ut ∇fj(w(t)j ) ∥∥∥∥∥∥ 2 
≤ 2(K n α2i + 1− αi)2E
[ ‖∇fi(v̄(t)i )‖ 2 ] + 2E  ∥∥∥∥∥∥(1− αi)  1 K ∑ j∈Ut ∇fj(w(t)j )−∇fi(v̄ (t) i ) ∥∥∥∥∥∥ 2 
≤ 2 ( 2( K
n α2i + 1− αi)2E
[ ‖∇fi(v̂(t)i )−∇f ∗ i ‖2 ]
+2( K
n α2i + 1− αi)2E
[ ‖∇fi(v̄(t)i )−∇fi(v̂ (t) i )‖ 2 ])
+ 2(1− αi)2E  ∥∥∥∥∥∥ 1K ∑ j∈Ut ∇fj(w(t)j )−∇fi(v̄ (t) i ) ∥∥∥∥∥∥ 2 
≤ 8L(K n α2i + 1− αi)
( E [ fi(v̂ (t) i ) ] − f∗i ) + 4(1− αi)2L2E [ ‖w(t) −w(t)i ‖ 2 ]
+ 6(1− αi)2 ( L2E [∥∥∥w(t) −w(t)i ∥∥∥2]+ E [∥∥∥∇fi(v̂(t)i )−∇F (w(t))∥∥∥2]
+ 1
K ∑ j∈Ut L2E [∥∥∥w(t) −w(t)j ∥∥∥2]  . (30)
Then plugging T1, T2, T3 back, we obtain the similar formulation as the without sampling case in (17). Thus:
E [ ‖v̂(t+1)i − v ∗ i ‖2 ]
≤ (
1− 3µηt 8
) E [ ‖v̂(t)i − v ∗ i ‖2 ] − 2(ηt − 4η2tL) ( α2i K
n + 1− αi
)( E [ fi(v̂ (t) i ) ] − fi(v∗i ) ) + α2i η 2 t 2Kσ2
n + (1− αi)2η2t
2σ2
K
+
( 8ηtL 2(1− αi)2
µ(1− 8(αi − α2i Kn )) +
6(1− αi)2ηtL2
µ + 10(1− αi)2η2tL2
) E [∥∥∥w(t) −w(t)i ∥∥∥2]
+
( 6(1− αi)2ηtL2
µ + 6(1− αi)2η2tL2
) 1
K ∑ j∈Ut E [∥∥∥w(t) −w(t)j ∥∥∥2]
+ ( 6ηt µ + 6η2t ) (1− αi)2E [∥∥∥∥∥ 1K ∑ j∈Ut ∇fj(w(t))−∇fi(v̂(t)i ) ∥∥∥∥∥ 2] . (31)
we then examine the lower bound of α2i K n +1−αi. Notice that: α 2 i K n +1−αi = K n ((αi− n 2K ) 2 + n K − n2 4K2 ).
Case 1: n2K ≥ 1 The lower bound is attained when αi = 1: α 2 i K n + 1− αi ≥ K n .
Case 2: n2K < 1 The lower bound is attained when αi = n 2K : α 2 i K n + 1− αi ≥ 1− n 4K > 1 2 .
So α2i K n + 1− αi ≥ b := min{ K n , 1 2} always holds.
Now we plug it and Lemma 6 back to (31):
E [ ‖v̂(t+1)i − v ∗ i ‖2 ]
≤ (
1− 3µηt 8
) E [ ‖v̂(t)i − v ∗ i ‖2 ] − bηt ( E [ fi(v̂ (t) i ) ] − fi(v∗i ) ) + α2i η 2 t 2Kσ2
n + (1− αi)2η2t
2σ2
K
+
( 8ηtL 2(1− αi)2
µ(1− 8(αi − α2i Kn )) +
6(1− αi)2ηtL2
µ + 10(1− αi)2η2tL2
) 3τη2t−1 ( σ2 + (ζi + ζ
K )τ ) + ( 6(1− αi)2ηtL2
µ + 6(1− αi)2η2tL2
) 3τη2t−1 ( σ2 + 2 ζ
K τ
)
+ ( 6ηt µ + 6η2t ) (1− αi)2E [∥∥∥∥∥ 1K ∑ j∈Ut ∇fj(w(t))−∇fi(v̂(t)i ) ∥∥∥∥∥ 2] . (32)
Plugging Lemma 5 yields: E [ ‖v̂(t+1)i − v ∗ i ‖2 ]
≤ (
1− 3µηt 8
) E [ ‖v̂(t)i − v ∗ i ‖2 ] − bηt ( E [ fi(v̂ (t) i ) ] − fi(v∗i ) ) + α2i η 2 t 2Kσ2
n + (1− αi)2η2t
2σ2
K
+
( 8ηtL 2(1− αi)2
µ(1− 8(αi − α2i Kn )) +
6(1− αi)2ηtL2
µ + 10(1− αi)2η2tL2
) 3τη2t−1 ( σ2 + (ζi + ζ
K )τ ) + ( 6(1− αi)2ηtL2
µ + 6(1− αi)2η2tL2
) 3τη2t−1 ( σ2 + 2 ζ
K τ ) + ( 6ηt µ + 6η2t ) (1− αi)2 [ 2L2E [ ‖v̂(t)i − v ∗‖2 ] + 6 ( 2ζi + 2 ζ K ) + 6L2E [ ‖w(t) −w∗‖2 ] + 6L2∆i ] .
Then following the same procedure in Appendix E.1.3, together with the application of Lemma 7 we can conclude that:
fi(v̂i)− fi(v∗i )
≤ 1 ST T∑ t=1 pt(fi(v̂ (t) i )− fi(v ∗ i ))
≤ p0E
[ ‖v̂(1)i − v ∗ i ‖2 ]
bη0ST +
1
bST T∑ t=1 ptηt ( α2i η 2 t 2Kσ2 n + (1− αi)2η2t 2σ2 K )
+ 1
bST T∑ t=1
(1− αi)2L2 (
8
µ(1− 8(αi − α2i Kn )) +
6 µ + 10ηt
) 3τptη 2 t−1 ( σ2 + (ζi + ζ
K )τ
)
+ 1
bST T∑ t=1 (1− αi)2L2 ( 6 µ + 10ηt ) 3τptη 2 t−1 ( σ2 + 2 ζ K τ )
+ 36(1− αi)2 L2
bST T∑ t=1 pt ( 1 µ + ηt )( a3 (t− 1 + a)3E [ ‖w(1) −w∗‖2 ] + ( t+ 16 ( 1
a+ 1 + ln(t+ a)
)) 1536a2τ ( σ2 + 2τ ζ
K
) L2
(a− 1)2µ4(t− 1 + a)3 + 128σ2t(t+ 2a) Kµ2(t− 1 + a)3
)
+ 36(1− αi)2 ( 2ζi + 2 ζ
K + L2∆i
) 1
bST T∑ t=1 pt ( 1 µ + ηt ) .
= O ( µ bT 3 ) + α2iO ( σ2 µbT ) + (1− αi)2O ( 2ζi + 2 ζ K µb + κL∆i b )
+ (1− αi)2 ( O ( κL lnT
bT 3
) +O ( κ2σ2
µbKT
) +O ( κ2τ2(ζi + ζ K ) + κ2τσ2
µbT 2
)
+O
( κ4τ ( σ2 + 2τ ζ
K ) µbT 2 )) .
F CONVERGENCE RATE WITHOUT ASSUMPTION ON αi
In this section, we provide the convergence results of Algorithm 1 without assumption on αi. The following Theorem establish the convergence rate:
Theorem 7 (Personalized model convergence of Local Descent APFL without assumption on αi). If each client’s objective function is µ-strongly-convex and L-smooth, and its gradient is bounded by G, using Algorithm 1, learning rate: ηt = 8µ(t+a) , where a = max{64κ, τ}, and using average scheme v̂i = 1ST ∑T t=1 pt(αiv (t) i + (1− αi) 1K ∑ j∈Ut w (t) j ), where pt = (t+ a) 2, ST = ∑T t=1 pt, and f∗i is the local minimum of the ith client, then the following convergence holds for all i ∈ [n]:
E[fi(v̂i)]− f∗i ≤ O ( µ bT 3 ) + α2iO ( σ2 µbT ) + (1− αi)2O ( G2 µb ) + (1− αi)2 ( O ( κL lnT
bT 3
) +O ( κ2σ2
µbKT
) +O ( κ2τ2(ζi + ζ K ) + κ 2τσ2
µbT 2
)
+O
κ4τ ( σ2 + 2τ ζK ) µbT 2  , (33) where b = min{Kn , 1 2}
Remark 6. Here we remove the assumption αi ≥ max{1− 14√6κ , 1− 1 4 √ 6κ √ µ }. The key difference is that we can only show the residual error with dependency on G, instead of more accurate quantities ζi and ∆i. Apparently, when the diversity among data shards is small, ζi and ∆i 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 domainW . Thus, we need to do projection during parameter update, which is inexpensive.
Proof. According to (32):
E [ ‖v̂(t+1)i − v ∗ i ‖2 ]
≤ (
1− 3µηt 8
) E [ ‖v̂(t)i − v ∗ i ‖2 ] − bηt ( E [ fi(v̂ (t) i ) ] − fi(v∗i ) ) + α2i η 2 t 2Kσ2
n + (1− αi)2η2t
2σ2
K
+
( 8ηtL 2(1− αi)2
µ(1− 8(αi − α2i Kn )) +
6(1− αi)2ηtL2
µ + 10(1− αi)2η2tL2
) 3τη2t−1 ( σ2 + (ζi + ζ
K )τ ) + ( 6(1− αi)2ηtL2
µ + 6(1− αi)2η2tL2
) 3τη2t−1 ( σ2 + 2 ζ
K τ
)
+ ( 6ηt µ + 6η2t ) (1− αi)2E  ∥∥∥∥∥∥ 1K ∑ j∈Ut ∇fj(w(t))−∇fi(v̂(t)i ) ∥∥∥∥∥∥ 2  .
Here, we directly use the bound E [∥∥∥ 1K ∑j∈Ut ∇fj(w(t))−∇fi(v̂(t)i )∥∥∥2] ≤ 2G2. Then we have:
E [ ‖v̂(t+1)i − v ∗ i ‖2 ]
≤ (
1− µηt 4
) E [ ‖v̂(t)i − v ∗ i ‖2 ] − bηt ( E [ fi(v̂ (t) i ) ] − fi(v∗i ) ) + α2i η 2 t 2Kσ2
n + (1− αi)2η2t
2σ2
K
+
( 8ηtL 2(1− αi)2
µ(1− 8(αi − α2i Kn )) +
6(1− αi)2ηtL2
µ + 10(1− αi)2η2tL2
) 3τη2t−1 ( σ2 + (ζi + ζ
K )τ ) + ( 6(1− αi)2ηtL2
µ + 6(1− αi)2η2tL2
) 3τη2t−1 ( σ2 + 2 ζ
K τ ) + ( 12ηt µ + 12η2t ) (1− αi)2G2.
Then following the same procedure in Appendix E.1.3, we can conclude that:
fi(v̂i)− fi(v∗i )
≤ 1 ST T∑ t=1 pt(fi(v̂ (t) i )− fi(v ∗ i ))
≤ p0E
[ ‖v̂(1)i − v ∗ i ‖2 ]
bη0ST +
1
bST T∑ t=1 ptηt ( α2i η 2 t 2Kσ2 n + (1− αi)2η2t 2σ2 K )
+ 1
bST T∑ t=1
(1− αi)2L2 (
8
µ(1− 8(αi − α2i Kn )) +
6 µ + 10ηt
) 3τptη 2 t−1 ( σ2 + (ζi + ζ
K )τ
)
+ 1
bST T∑ t=1 (1− αi)2L2 ( 6 µ + 10ηt ) 3τptη 2 t−1 ( σ2 + 2 ζ K τ )
+ 12(1− αi)2G2 1
bST T∑ t=1 pt ( 1 µ + ηt ) .
= O ( µ bT 3 ) + α2iO ( σ2 µbT ) + (1− αi)2O ( G2 µb ) + (1− αi)2 ( O ( κL lnT
bT 3
) +O ( κ2σ2
µbKT
) +O ( κ2τ2(ζi + ζ K ) + κ2τσ2
µbT 2
) +O ( κ4τ ( σ2 + 2τ ζ K ) µbT 2 )) .

heading: G PROOF OF CONVERGENCE RATE IN NONCONVEX SETTING
text: In this section we will provide the proof of convergence results on nonconvex functions. 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 objective function is L-smooth, using Algorithm 1 with full gradient, by choosing K = n and learning rate η =
1 2 √ 5L √ T , then the following convergence holds:
1
T T∑ t=1 ∥∥∥∇F (w(t))∥∥∥2 ≤ O( L√ T ) +O ( τ2ζ nT ) .
Proof. The proof is provided in Appendix G.2.
As usual, let us introduce several useful lemmas before the formal proof of Theorem 3 and 8.

heading: G.1 PROOF OF TECHNICAL LEMMAS
text: Lemma 8. Under Theorem 3’s assumptions, the following statement holds true:
fi(v̂ (t+1) i ) ≤ fi(v̂ (t) i )−
1 8 η‖∇fi(v̂i)‖2
+ 3
2 (1− αi)2η
1
n n∑ j=1 ∥∥∥w(t) −w(t)j ∥∥∥2 + 3α4i (1− α)2ηL2 ∥∥∥w(t) −w(t)i ∥∥∥2 + 6η(1− α2i )2ζi + 12η(1− α2i )2L2D2W + 12η(αi − α2i )2 ∥∥∥∇F (w(t))∥∥∥2 .
Proof. Define the following quantities:
g(t) = α2i∇fi(v̄ (t) i ) + (1− αi)
1
n n∑ j=1 ∇fj(w(t)j )
PW(v̂ (t) i , g
(t), η) = 1
η v̂(t)i −∏ W v̂(t)i − η α2i∇fi(v̄(t)i ) + (1− αi) 1n n∑ j=1 ∇fj(w(t)j ) 
According to Ghadimi et al. (2016) Lemma 1 :For all w ∈ W ⊂ Rd, g ∈ Rd and η > 0, we have:
〈g, PW(w, g, η)〉 ≥ ‖PW(w, g, η)‖2.
According to the updating rule and smoothness of fi, we have:
fi(v̂ (t+1) i ) ≤ fi(v̂ (t) i ) + 〈 ∇fi(v̂(t)i ), v̂ (t+1) i − v̂ (t) i 〉 + L
2 ∥∥∥v̂(t+1)i − v̂(t)i ∥∥∥2 . ≤ fi(v̂(t)i ) + 〈 ∇fi(v̂(t)i ), v̂ (t+1) i − v̂ (t) i 〉 + L
2 ∥∥∥v̂(t+1)i − v̂(t)i ∥∥∥2 ≤ fi(v̂(t)i )− η 〈 ∇fi(v̂(t)i ), PW(v̂ (t) i , g (t), η) 〉 + η2L
2 ∥∥∥PW(v̂(t)i , g(t), η)∥∥∥2 ≤ fi(v̂(t)i )− η 〈 g(t), PW(v̂ (t) i , g (t), η) 〉 − η 〈 ∇fi(v̂(t)i )− g (t), PW(v̂ (t) i , g (t), η) 〉
+ η2L
2 ∥∥∥PW(v̂(t)i , g(t), η)∥∥∥2 (34)
Using the identity:
〈 g(t), PW(v̂ (t) i , g (t), η) 〉 ≥ ‖g(t)‖2,
and Cauchy-Schwartz inequality that
〈 ∇fi(v̂(t)i )− g (t), PW(v̂ (t) i , g (t), η) 〉 ≤ 1
2 ‖∇fi(v̂(t)i )− g (t)‖2 + 1 2 ‖PW(v̂(t)i , g (t), η)‖2
we have:
fi(v̂ (t+1) i ) ≤ fi(v̂ (t) i )− ∥∥∥g(t)∥∥∥2 + η 2 ∥∥∥PW(v̂(t)i , g(t), η)∥∥∥2 + η2L2 ∥∥∥PW(v̂(t)i , g(t), η)∥∥∥2 + η
2 ∥∥∥∥∥∥∇fi(v̂(t)i )− α2i∇fi(v̄(t)i )− (1− αi) 1n n∑ j=1 ∇fj(w(t)j ) ∥∥∥∥∥∥ 2
≤ fi(v̂(t)i )− ( η
2 − η
2L
2 ) ︸ ︷︷ ︸
≤ 14η
∥∥∥g(t)∥∥∥2
+ η
2 ∥∥∥∥∥∥∇fi(v̂(t)i )− α2i∇fi(v̄(t)i )− (1− αi) 1n n∑ j=1 ∇fj(w(t)j ) ∥∥∥∥∥∥ 2
≤ fi(v̂(t)i )− 1 4 η ∥∥∥g(t)∥∥∥2 + (1− αi)2η ∥∥∥∥∥∥∇F (w(t))− 1n n∑ j=1 ∇fj(w(t)j ) ∥∥∥∥∥∥ 2
+ η ∥∥∥α2i (∇fi(v̂(t)i )−∇fi(v̄(t)i ))− (1− αi)∇F (w(t)) + (1− α2i )∇fi(v̂(t)i )∥∥∥2
≤ fi(v̂(t)i )− 1 4 η ∥∥∥g(t)∥∥∥2 + (1− αi)2η 1 n n∑ j=1 ∥∥∥w(t) −w(t)j ∥∥∥2 + 2η ∥∥∥α2i (∇fi(v̂(t)i )−∇fi(v̄(t)i ))∥∥∥2 + 2η
∥∥∥(1− α2i )∇fi(v̂(t)i )− (1− α2i )∇F (v̂(t)i ) + (1− α2i )∇F (v̂(t)i )− (1− αi)∇F (w(t))∥∥∥2 ≤ fi(v̂(t)i )− 1 4 η ∥∥∥g(t)∥∥∥2 + (1− αi)2η 1 n n∑ j=1
∥∥∥w(t) −w(t)j ∥∥∥2 + 2α4i ηL2 ∥∥∥v̂(t)i − v̄(t)i ∥∥∥2 + 4η
∥∥∥(1− α2i )∇fi(v̂(t)i )− (1− α2i )∇F (v̂(t)i )∥∥∥2 + 4η ∥∥∥(1− α2i )∇F (v̂(t)i )− (1− αi)∇F (w(t))∥∥∥2 ≤ fi(v̂(t)i )− 1 4 η ∥∥∥g(t)∥∥∥2 + (1− αi)2η 1 n n∑ j=1
∥∥∥w(t) −w(t)j ∥∥∥2 + 2α4i (1− α)2ηL2 ∥∥∥w(t) −w(t)i ∥∥∥2 + 4η(1− α2i )2ζi + 8η
∥∥∥(1− α2i )∇F (v̂(t)i )− (1− α2i )∇F (w(t))∥∥∥2 + 8η ∥∥∥(αi − α2i )∇F (w(t))∥∥∥2 ≤ fi(v̂(t)i )− 1 4 η ∥∥∥g(t)∥∥∥2 + (1− αi)2η 1 n n∑ j=1
∥∥∥w(t) −w(t)j ∥∥∥2 + 2α4i (1− α)2ηL2 ∥∥∥w(t) −w(t)i ∥∥∥2 + 4η(1− α2i )2ζi + 8η(1− α2i )2L2D2W + 8η(αi − α2i )2 ∥∥∥∇F (w(t))∥∥∥2
Using the following inequality to replace ‖g(t)‖2:
‖∇fi(v̂i)‖2 ≤ 2‖∇fi(v̂i)− g(t)‖2 + 2‖g(t)‖2
hence we can conclude the proof:
fi(v̂ (t+1) i ) ≤ fi(v̂ (t) i )−
1 4 η
[ 1
2 ‖∇fi(v̂i)‖2 − ‖∇fi(v̂i)− g(t)‖2 ] + (1− αi)2η 1
n n∑ j=1 ∥∥∥w(t) −w(t)j ∥∥∥2 + 2α4i (1− α)2ηL2 ∥∥∥w(t) −w(t)i ∥∥∥2 + 4η(1− α2i )2ζi + 8η(1− α2i )2L2D2W + 8η(αi − α2i )2
∥∥∥∇F (w(t))∥∥∥2 ≤ fi(v̂(t)i )− 1
8 η‖∇fi(v̂i)‖2 +
1 4 η ∥∥∥∥∥∥∇fi(v̂i)− α2i∇fi(v̄(t)i ) + (1− αi) 1n n∑ j=1 ∇fj(w(t)j ) ∥∥∥∥∥∥ 2
+ (1− αi)2η 1
n n∑ j=1 ∥∥∥w(t) −w(t)j ∥∥∥2 + 2α4i (1− α)2ηL2 ∥∥∥w(t) −w(t)i ∥∥∥2 + 4η(1− α2i )2ζi + 8η(1− α2i )2L2D2W + 8η(αi − α2i )2
∥∥∥∇F (w(t))∥∥∥2 ≤ fi(v̂(t)i )− 1
8 η‖∇fi(v̂i)‖2
+ 3
2 (1− αi)2η
1
n n∑ j=1 ∥∥∥w(t) −w(t)j ∥∥∥2 + 3α4i (1− α)2ηL2 ∥∥∥w(t) −w(t)i ∥∥∥2 + 6η(1− α2i )2ζi + 12η(1− α2i )2L2D2W + 12η(αi − α2i )2
∥∥∥∇F (w(t))∥∥∥2 . Lemma 9. Under Theorem 3’s assumptions, the following statement holds true:
1
T T∑ t=1 ∥∥∥∇F (w(t))∥∥∥2 ≤ 8 ηT F (w(1)) + 6L2 1 T T∑ t=1 1 n n∑ j=1 ∥∥∥ w(t)j −w(t)∥∥∥2 . Proof. Define the following quantities:
ḡ(t) = 1
n n∑ j=1 ∇fj(w(t)j )
R(t) = PW(w (t), ḡ(t), η) =
1
η w(t) −∏ W w(t) − η 1 n n∑ j=1 ∇fj(w(t)j )  According to the updating rule and smoothness of fi, we have:
F (w(t+1)) ≤ F (w(t)) + 〈 ∇F (w(t)),w(t+1) −w(t) 〉 + L
2 ∥∥∥w(t+1) −w(t)∥∥∥2 ≤ F (w(t))− η 〈 ∇F (w(t)), PW(w(t), ḡ(t), η) 〉 + η2L
2 ∥∥∥PW(w(t), ḡ(t), η)∥∥∥2 ≤ F (w(t))− η 〈 ḡ(t), PW(w (t), ḡ(t), η) 〉 − η 〈 ∇F (w(t))− ḡ(t), PW(w(t), ḡ(t), η)
〉 + η2L
2 ∥∥∥PW(w(t), ḡ(t), η)∥∥∥2 (35)
Using the identity: 〈 ḡ(t), PW(w (t), ḡ(t), η) 〉 ≥ ‖ḡ(t)‖2, and Cauchy-Schwartz inequality that〈
∇F (w(t))− ḡ(t), PW(w(t), ḡ(t), η) 〉 ≤ 12‖∇F (w (t))− ḡ(t)‖2 + 12‖PW(w (t), ḡ(t), η)‖2 we have:
F (w(t+1)) ≤ F (w(t))− η ∥∥∥ḡ(t)∥∥∥2 + (η
2 + η2L 2 )∥∥∥PW(w(t), ḡ(t), η)∥∥∥2 + η 2 ∥∥∥∇F (w(t))− ḡ(t)∥∥∥2 ≤ F (w(t))− η ∥∥∥ḡ(t)∥∥∥2 + (η 2 + η2L 2 )∥∥∥ḡ(t)∥∥∥2 + ηL2 2 1 n n∑ i=1
∥∥∥ w(t)j −w(t)∥∥∥2 . ≤ F (w(t))− 1 4 η ∥∥∥ḡ(t)∥∥∥2 + ηL2 2 1 n n∑ i=1
∥∥∥ w(t)j −w(t)∥∥∥2 . Using the following inequality to replace ‖g(t)‖2:
‖∇F (w(t))‖2 ≤ 2‖∇F (w(t))− ḡ(t)‖2 + 2‖ḡ(t)‖2
hence we obtain:
F (w(t+1)) ≤ F (w(t))− 1 4 η
( 1
2 ‖∇F (w(t))‖2 − ‖∇F (w(t))− ḡ(t)‖2
) + ηL2
2
1
n n∑ i=1 ∥∥∥ w(t)j −w(t)∥∥∥2 ≤ F (w(t))− 1
8 η‖∇F (w(t))‖2 + 3ηL
2
4
1
n n∑ i=1 ∥∥∥ w(t)j −w(t)∥∥∥2 . Re-arranging terms and doing the telescoping sum from t = 1 to T :
1
T T∑ t=1 ∥∥∥∇F (w(t))∥∥∥2 ≤ 8 ηT F (w(1)) + 6L2 1 T T∑ t=1 1 n n∑ j=1 ∥∥∥ w(t)j −w(t)∥∥∥2 .
Lemma 10. Under Theorem 3’s assumptions, the following statement holds true:
1
T T∑ t=1 1 n n∑ i=1 ∥∥∥w(t) −w(t)i ∥∥∥2 ≤ 10τ2η2 ζn , 1
T T∑ t=1 ∥∥∥w(t) −w(t)i ∥∥∥2 ≤ 200L2τ4η4 ζn + 20τ2η2ζi. Proof. For the first statement, we define γt = 1n ∑n i=1
∥∥∥w(t) −w(t)i ∥∥∥2, and let tc be the latest synchronization stage. Then we have:
γt = 1
n n∑ i=1 ∥∥∥∥∥∥wtc − t∑
j=tc
η
n n∑ k=1 ∇fk(w(j)k )− wtc − t∑ j=tc η∇fi(w(j)i ) ∥∥∥∥∥∥ 2
= τ t∑ j=tc η2 n n∑ i=1 ∥∥∥∥∥ 1n n∑ k=1 ∇fk(w(j)k )−∇fi(w (j) i ) ∥∥∥∥∥ 2
= τ t∑ j=tc η2 n n∑ i=1 ∥∥∥∥∥ 1n n∑ k=1 ∇fk(w(j)k )−∇fk(w (j)) +∇fk(w(j))−∇fi(w(j)) +∇fi(w(j))−∇fi(w(j)i ) ∥∥∥∥∥ 2
≤ τ t+τ∑ j=tc 5η2 ( 2L2γj + ζ n ) .
Summing over t from tc to tc + τ yields: tc+τ∑ t=tc γt ≤ tc+τ∑ t=tc tc+τ∑ j=tc 5τη2 ( 2L2γj + ζ n )
≤ 10L2τ2η2 (r+1)τ∑ j=rτ γj + 5τ3η2 ζ n .
Since η ≤ 1 2 √ 5τL , we have 10L2τ2η2 ≤ 12 , hence by re-arranging the terms we have:
tc+τ∑ t=tc γt ≤ 10τ3η2 ζ n .
Summing over all synchronization stages tc, and dividing both sides by T can conclude the proof of the first statement:
1
T T∑ t=1 γt ≤ 10τ2η2 ζ n . (36)
To prove the second statement, let δit = ∥∥∥w(t) −w(t)i ∥∥∥2. Notice that:
δit = ∥∥∥∥∥∥wtc − t∑
j=tc
η
n n∑ k=1 ∇fk(w(j)k )− wtc − t∑ j=tc η∇fi(w(j)i ) ∥∥∥∥∥∥ 2
= τ t∑ j=tc η2 ∥∥∥∥∥ 1n n∑ k=1 ∇fk(w(j)k )−∇fi(w (j) i ) ∥∥∥∥∥ 2
= τ t∑ j=tc η2 ∥∥∥∥∥ 1n n∑ k=1 ∇fk(w(j)k )−∇fk(w (j)) +∇fk(w(j))−∇fi(w(j)) +∇fi(w(j))−∇fi(w(j)i ) ∥∥∥∥∥ 2
≤ τ t+τ∑ j=tc 5η2 ( L2γj + L 2δij + ζi ) .
Summing over t from tc to tc + τ yields: tc+τ∑ t=tc γt ≤ tc+τ∑ t=tc tc+τ∑ j=tc 5τη2 ( L2γj + L 2δij + ζi )
≤ 5L2τ2η2 tc+τ∑ j=tc γj + 5L 2τ2η2 tc+τ∑ j=tc δij + 5τ 3η2ζi.
Since η ≤ 1 2 √ 5τL , we have 5L2τ2η2 ≤ 14 , hence by re-arranging the terms we have:
tc+τ∑ t=tc δit ≤ 20L2τ2η2 tc+τ∑ j=tc γj + 20τ 3η2ζi.
Summing over all synchronization stages tc, and dividing both sides by T can conclude the proof of the first statement:
1
T T∑ t=1 δit ≤ 20L2τ2η2 1 T T∑ t=1 γt + 20τ 2η2ζi.
Using the result from (36) to bound 2 1T ∑T t=1 γt we have:
1
T T∑ t=1 δit ≤ 200L2τ4η4 ζ n + 20τ2η2ζi.

heading: G.2 PROOF OF THEOREM 8
text: Proof. According to Lemma 9:
1
T T∑ t=1 ∥∥∥∇F (w(t))∥∥∥2 ≤ 8 ηT F (w(1)) + 6L2 1 T T∑ t=1 1 n n∑ j=1 ∥∥∥ w(t)j −w(t)∥∥∥2 . Then plugging in Lemma 10 will conclude the proof.

heading: G.3 PROOF OF THEOREM 3
text: Proof. According to Lemma 8:
fi(v̂ (t+1) i ) ≤ fi(v̂ (t) i )−
1 8 η‖∇fi(v̂i)‖2
+ 3
2 (1− αi)2η
1
n n∑ j=1 ∥∥∥w(t) −w(t)j ∥∥∥2 + 3α4i (1− α)2ηL2 ∥∥∥w(t) −w(t)i ∥∥∥2 + 6η(1− α2i )2ζi + 12η(1− α2i )2L2D2W + 12η(αi − α2i )2
∥∥∥∇F (w(t))∥∥∥2 . Re-arranging the terms, summing from t = 1 to T , and dividing both sides with T yields:
1
T T∑ t=1 ∥∥∥∇fi(v̂(t)i )∥∥∥2 ≤ 8fi(v̂ (1) i )
ηT
+ 24α4i (1− αi)2L2 1
T T∑ t=1 ∥∥∥w(t)i −w(t)∥∥∥2 + 12(1− αi)2L2 1n n∑ j=1 1 T T∑ t=1 ∥∥∥w(t)j −w(t)∥∥∥2 + 128(1− αi)2 1
T T∑ t=1 ∥∥∥∇F (w(t))∥∥∥2 + 48(1− α2i )2ζi + 128(1− α2i )2L2DW , Then, plug in Lemma 9 and 10 :
1
T T∑ t=1 ∥∥∥∇fi(v̂(t)i )∥∥∥2 ≤ 8fi(v̂ (1) i )
ηT + 48(1− α2i )2ζi + 128(1− α2i )2L2DW
+ 24α4i (1− αi)2L2 1
T T∑ t=1 ∥∥∥w(t)i −w(t)∥∥∥2 + 12(1− αi)2L2 1n n∑ j=1 1 T T∑ t=1 ∥∥∥w(t)j −w(t)∥∥∥2
+ 128(1− αi)2  8 ηT F (w(1)) + 6L2 1 T T∑ t=1 1 n n∑ j=1 ∥∥∥ w(t)j −w(t)∥∥∥2 
≤ 8fi(v̂ (1) i )
ηT + 48(1− α2i )2ζi + 128(1− α2i )2L2DW + 24α4i (1− αi)2L2 [ 200L2τ4η4 ζ
n + 20τ2η2ζi ] + 7800τ2η2(1− αi)2L2 ζ
n +
1024(1− αi)2
ηT F (w(1)).
Plugging in η = 1 2 √ 5 √ TL concludes the proof:
1
T T∑ t=1 ∥∥∥∇fi(v̂(t)i )∥∥∥2 ≤ O ( L√ T ) + (1− αi)2 ( L√ T ) + (1− α2i )2 ( ζi + L 2DW )
+ α4i (1− αi)2O ( τ4ζ
nT 2 + τ2ζi T
) + (1− αi)2O ( τ2ζ
nT
) .

Review summaries:
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.