Year: 2021

Abstract:
Federated Learning (FL) is an emerging learning paradigm that preserves privacy by ensuring client data locality on edge devices. The optimization of FL is challenging in practice due to the diversity and heterogeneity of the learning system. Despite recent research efforts on improving the optimization of heterogeneous data, the impact of time-varying heterogeneous data in real-world scenarios, such as changing client data or intermittent clients joining or leaving during training, has not been well studied. In this work, we propose Continual Federated Learning (CFL), a flexible framework, to capture the time-varying heterogeneity of FL. CFL covers complex and realistic scenarios—which are challenging to evaluate in previous FL formulations—by extracting the information of past local datasets and approximating the local objective functions. Theoretically, we demonstrate that CFL methods achieve a faster convergence rate than FedAvg in time-varying scenarios, with the benefit being dependent on approximation quality. In a series of experiments, we show that the numerical findings match the convergence analysis, and CFL methods significantly outperform the other SOTA FL baselines.

heading: 1 INTRODUCTION
text: Federated Learning (FL) has recently emerged as a critical distributed machine learning paradigm to preserve user/client privacy. Clients engaged in the training process of FL only communicate their local model parameters, rather than their private local data, with the central server. As the workhorse algorithm in FL, FedAvg (McMahan et al., 2017) performs multiple local stochastic gradient descent (SGD) updates on the available clients before communicating with the server. Despite its success, FedAvg suffers from the large heterogeneity (non-iid-ness) in the data presented on the different clients, causing drift in each client’s updates and resulting in slow and unstable convergence (Karimireddy et al., 2020b). To address this issue, a new line of study has been suggested lately that either simulates the distribution of the whole dataset using preassigned weights of clients (Wang et al., 2020; Reisizadeh et al., 2020; Mohri et al., 2019; Li et al., 2020a) or adopts variance reduction methods (Karimireddy et al., 2020b;a; Das et al., 2020; Haddadpour et al., 2021). However, the FL formulation in these approaches always assumes a fixed data distribution among clients throughout all training rounds, while in practice this assumption does not always hold because of the complex, uncontrolled, and unpredictable client behaviors. Local datasets, for example, often vary over time, and intermittent clients can join or depart during training without prior notice. The difficulty in addressing the time-varying heterogeneity of FL lies in the stateless nature of the local datasets, which includes the unpredictable future datasets and the impossibility of retaining all prior local datasets. To this end, we first provide a novel Continual Federated Learning (CFL) formulation and then propose a unified CFL framework as our solution. This framework encompasses a variety of design choices for approximating the local objective functions in the previous training rounds, with the difference between actual and estimated local object functions described as information loss for further analysis. To capture the time-varying data heterogeneity in the CFL framework, we expand the theoretical assumption on the client drift—which has been extensively utilized recently in Karimireddy et al. (2020b); Khaled et al. (2020); Li et al. (2020b)—to include both client drift and time drift. This allows us to quantify the difference between local client objective function and global objective function for the considered time-varying heterogeneous clients. We provide convergence rates for our unified CFL framework in conjunction with information loss and new models of both client and time drifts. Our analysis reveals a faster convergence of CFL framework than FedAvg, with the benefit dependent on approximation quality. The rate of FedAvg obtained from
our framework is consistent with previous work, while a similarly simplified rate on Continual Learning (CL) (French, 1999; Kirkpatrick et al., 2017) for the convex and strongly convex cases is novel. Finally, in extensive empirical results, we demonstrate that CFL methods—stemmed from the CFL framework with different approximation techniques—significantly outperform the SOTA FL competitors on various realistic datasets. These numerical observations corroborate our theoretical findings.
Contribution. We summarize our key contributions below. • We present a unified framework, termed Continual Federated Learning (CFL), together with a
novel client and time drift modeling approach, to capture complex FL scenarios involving timevarying heterogeneous data. This is the first theoretical study, to our knowledge, that describes the time-varying nature of FL. • We provide rigorous convergence analysis for the CFL methods. Our theoretical analysis explains the faster and more stabilized optimization of the CFL methods over that of FedAvg, and conjecture their variance reduction effect. In addition, we provide tight convergence rates for standalone CL methods on convex and strongly-convex problems: to the best of our knowledge, we are the first to provide such guarantees for CL on SGD. • We examine several approximation techniques for CFL framework: the insights therein offer a valuable practical guideline. We demonstrate the efficacy and necessity of CFL methods over the SOTA FL baselines across a range of time-varying heterogeneous data scenarios and datasets.

heading: 2 RELATED WORK
text: Federated Learning. FedAvg (McMahan et al., 2017; Lin et al., 2020b) is the de facto standard FL algorithm, in which multiple local SGD steps are executed on the available clients to alleviate the communication bottleneck. While communication efficient, heterogeneity, such as system heterogeneity (Li et al., 2018; Wang et al., 2020; Mitra et al., 2021; Diao et al., 2021) and statistical/objective heterogeneity (Li et al., 2018; Wang et al., 2020; Mitra et al., 2021; Lin et al., 2020a; Karimireddy et al., 2020b;a), results in inconsistent optimization objectives and drifted clients models, impeding federated optimization considerably. A line of work has been proposed to address the heterogeneity in FL. FedProx (Li et al., 2018) adds the regularization term on the distance of local and global models when performing local training—similar formulations can be found in other recent FL works (Hanzely & Richtárik, 2020; Dinh et al., 2020; Li et al., 2021) for various purposes. To address the issue of objective heterogeneity e.g. caused by heterogeneous data, works like SCAFFOLD (Karimireddy et al., 2020b; Mitra et al., 2021) introduce the idea of variance reduction on the client local update steps. FedNova (Wang et al., 2020) further proposes a general framework for unifying FedAvg and FedProx, and argues that while averaging, local updates should be normalized to minimize heterogeneity induced by different number of local update steps. However, most of these prior works focus on the fixed heterogeneity across clients and throughout the entire optimization procedure; we instead consider the novel scenario with time-varying data heterogeneity. The theoretical study on the convergence of FedAvg can date back to the parallel SGD analysis on the identical functions Zinkevich et al. (2010) and recently is improved by Stich (2019); Stich & Karimireddy (2020); Patel & Dieuleveut (2019); Khaled et al. (2020); Woodworth et al. (2020b). For the analysis of heterogeneous data, Li et al. (2020b) first give the convergence rate of FedAvg on non-iid datasets with random selection, assuming that the client optimum are -close. Woodworth et al. (2020a); Khaled et al. (2020) give tighter convergence rates under the assumption of bounded gradient drift. All above works give a O (1/T ) convergence rate for convex local objective functions. More recently, Karimireddy et al. (2020b); Koloskova et al. (2020) give the convergence analysis of local SGD for non-convex objective functions under bounded gradient noise assumptions, and obtain a O(1/ √ T ) convergence rate. Our theoretical analysis framework covers more challenging timevarying data heterogeneity in FL, which has not been considered in the community yet—our rate can be simplified to the standard FL scenario, matching the tight analysis in Karimireddy et al. (2020b).
Continual Learning. Continual learning, also known as incremental learning or lifelong learning, aims to learn from (time-varying) sequential data while avoiding the problem of catastrophic forgetting (French, 1999; Kirkpatrick et al., 2017). There exists a large amount of works, from the perspectives of regularization (Kirkpatrick et al., 2017; Li & Hoiem, 2017; Zenke et al., 2017), experience replay (Castro et al., 2018; Rebuffi et al., 2017), and dynamic architectures (Maltoni & Lomonaco, 2019; Rusu et al., 2016). In this paper, we examine both regularization and experience replay based methods, and compare their empirical performance in depth.
Despite the empirical success, the theoretical analysis of CL is limited: only a very recent preprint (Yin et al., 2020b) provides a viewpoint of regularization-based continual learning, and only for the single worker scenario. In this work, we provide tight convergence analysis for both CL and CFL on SGD.
Continual Federated Learning. To our knowledge, the scenario of CFL was originally described in Bui et al. (2018) in order to federated train Bayesian Neural Network and continually learn for Gaussian Process models—it is orthogonal to our optimization aspect in this paper. FedCurv (Shoham et al., 2019) blends EWC (Kirkpatrick et al., 2017) regularization with FedAvg, and empirically shows a faster convergence. FedWeIT (Yoon et al., 2021) extends the regularization idea, with a focus on selective inter-client knowledge transfer for task-adaptive parameters. In a very recent parallel (and empirical) work, CDA-FedAvg (Casado et al., 2021) uses a locally maintained long-term data samples, with asynchronous communication; however, this design choice lacks sufficient numerical results to justify the performance gain (even over FedAvg) and it cannot be applied to more general scenarios. Our theoretically sound CFL framework covers the regularization component of FedCurv and the core set part of CDA-FedAvg, and is orthogonal to the neural architecture manipulation idea in FedWeIT.

heading: 3 CONTINUAL FEDERATED LEARNING FRAMEWORK

heading: 3.1 FORMULATION
text: Conventional FL Formulation. The standard FL typically considers a sum-structured distributed optimization problem as below:
f? = minω∈Rd [ f(ω) := ∑N i=1 pifi(ω) ] , (1)
where the objective function f(ω) : Rd → R is the weighted sum of the local objective functions fi(ω) := EDi [Fi(ω)] of N nodes/clients, and pi is the weight of client i. In practice, it may be infeasible to select all clients each round, especially for cross-device setup (McMahan et al., 2017; Kairouz et al., 2019). The standard FedAvg then randomly selects S clients to receive the model parameters from the server (S ≤ N ) in each communication round and performs K local SGD update steps in the form of ωt,i,k = ωt,i,k−1 − ηl(∇fi(ωt,i,k−1) + νt,i,k−1), with local step-size ηl and gradient noise νt,i,k−1. The selected clients then communicate the updates ∆ωt,i = ωt,i,K − ωt with the server for the model aggregation: ωt+1 = ωt − ηgS ∑S i=1 ∆ωt,i.
Continual FL Formulation. Despite its wide usage, the standard FL formulation given in Equation (1) cannot properly reflect actual time-varying scenarios, such as local datasets changing over time or intermittent clients joining or leaving during training. To address this problem, we propose the Continual Federated Learning (CFL) formulation:
f? = minω∈Rd [ f(ω) := ∑T t=1 ∑ i∈St pt,ift,i(ω) ] , (CFL)
where ft,i(ω) represents the local objective function of client i at time t. St is a subset of clients sampled from all clients set Ω, where |St| = S. For the time-varying scenarios, client i could have different local objective functions ft,i(ω) due to the changing local datasets on different t.

heading: 3.2 APPROXIMATION OF CFL
text: The challenge of addressing (CFL) formulation stems from the stateless nature of the local datasets, which include unpredictable future datasets, as well as the difficulty of keeping all the previous local datasets. The original definition of (CFL) is theoretically and empirically infeasible. To handle the second case (while ignoring the intractable former), a straightforward approach is to approximate the prior local objective functions (Kirkpatrick et al., 2017; Zenke et al., 2017; Li & Hoiem, 2017), which may be accomplished by retraining information from earlier rounds in accordance with privacy protection standards. Thus, we can express the approximated CFL formulation as:
f̃t ? = minω∈Rd [ f̃t(ω) := ∑ i∈St pt,ift,i(ω) + ∑t−1 τ=1 ∑ i∈St pτ,if̃τ,i(ω) ] , (2)
where f̃t,i(ω) denotes the approximated local objective function of client i at time t. In practice, different approximation methods can be used to calculate f̃τ,i(ω), and we refer the detailed illustration and discussions of these approximation algorithms in Section 5.1, Section 5.2, and Appendix C.2.2 We give the formal definition of CFL framework in Algorithm 1. CFL methods are a collection of methods that make use of different approximation techniques and are based on Algorithm 1. We retrieve the objective function of conventional Continual Learning (CL), by setting S = 1 in (2). Take note that in most cases, the previous local object functions cannot be properly approximated. Due to the fact that such approximation impairs optimization, we define the information loss below.
Algorithm 1 Approximated CFL Framework Require: initial weights ω0, global learning rate ηg , local learning rate ηl, number of training rounds T Ensure: trained weights ωT 1: for round t = 1, . . . , T do 2: communicate ωt to the chosen clients. 3: for client i ∈ St in parallel do 4: initialize local model ωt,i,0 = ωt. 5: for k = 1, . . . ,K do
6: g̃t,i,k(ωt,i,k−1) = ( pt,i∇ft,i(ωt,i,k−1) + ∑t−1 τ=1 pτ,i∇f̃τ,i(ωt,i,k−1) ) + νt,i,k.
7: ωt,i,k ← ωt,i,k−1 − ηlg̃t,i,k(ωt,i,k−1). 8: communicate ∆ωt,i ← ωt,i,K − ωt. 9: ∆ωt ← ηgS ∑ i∈St ∆ωt,i.
10: ωt+1 ← ωt + ∆ωt.
Definition 3.1 (Information Loss). We define the information loss as the difference between the approximated local objective function f̃t,i(ω) and the real local objective function ft,i(ω), i.e.
∆t,i(ω) = ∇ft,i(ω)−∇f̃t,i(ω) . (3)
In practice, we use ‖∆t,i(ω)‖2 to measure the information loss of different approximation methods. We show large information loss can impede the convergence theoretically (c.f. Theorem 4.1) and empirically (e.g. Figure 1 in Section 5.2).

heading: 3.3 GRADIENT NOISE MODEL
text: To analyze Equation (2) and Algorithm 1 in-depth, we propose the Gradient Noise Model (Equation (5)) to capture the dynamics of performing SGD with data heterogeneity. We first recap the standard definition of gradient noise in Sammut & Webb (2010); Gower et al. (2019).
Gradient noise in SGD. For objective function f(ω), the gradient with stochastic noise can be defined as ∇f(ω) = g(ω) + ν, where g(ω) is the stochastic gradient, and ν is a zero-mean noise. Client drift in FL. To analyze the impact of data heterogeneity, recent works (Karimireddy et al., 2020b; Khaled et al., 2020; Li et al., 2020b) similarly use the gradient noise to capture the distribution drift between local objective function and global objective function:
∇f(ω) = ∇fi(ω) + δi , (4)
where δi is a zero-mean random variable which measures the gradient noise of client i.
Client drift and time drift in CFL framework. In (CFL), we use {t, i} pair instead of i to represent client i at time t. Considering the distribution drift in the dimension of client and time, we further modify the gradient noise model in FL as,
∇f(ω) = ∇ft,i(ω) + δt,i + ξt,i . (5)
Note that we extend the gradient noise to two terms: δt,i and ξt,i. δt,i is a time independent (of t), zero-mean random variable that measures the drift of client i. The zero-mean ξt,i measures the drift of client i at time t: this value of client i may change over time t, due to the time-varying local datasets. Remark 3.2. We assume different ξt,i are independent to simplify the analysis. We also empirically examine the performance of CFL methods under overlapped time-varying local data in Section 5.2.

heading: 3.4 ASSUMPTIONS
text: To ease the theoretical analysis of (CFL) framework, we use the following widely used assumptions. Assumption 1 (Smoothness and convexity). Assume local objective functions ft,i(ω) are L-smooth and µ-convex, i.e. µ2 ‖ω1 − ω2‖ 2 ≤ ft,i(ω1)− ft,i(ω2)− 〈∇ft,i(ω2),ω1 −ω2〉 ≤ L2 ‖ω1 − ω2‖ 2. A widely used corollary is that if a function ft,i is both L-smooth and µ-convex, then it satisfies 1 2L ‖∇ft,i(x)−∇ft,i(y)‖
2 ≤ ft,i(x)− ft,i(y)−∇ft,i(x)T (x− y), and L ≥ µ. Assumption 2 (Bounded noise in stochastic gradient). Let gt,i,k(ω) = ∇ft,i,k(ω) + νt,i,k, where νt,i,k is the stochastic noise of client i on round t at k-th local update step. We assume that
E [ν|ω] = 0, and E [ ‖ν‖2 |ω ] ≤ σ2.
Assumption 1 and 2 are common assumptions in FL (Karimireddy et al., 2020b; Li et al., 2020b). Considering a relaxed assumption like the bounded noise at optimum in Khaled et al. (2020) will be an interesting future research direction. Besides, we introduce the following assumptions to better characterize the client and time drifts in CFL framework (i.e. (5)). Assumption 3 (Bounded gradient drift of CFL framework). Let f(ω) = ∇ft,i(ω)+δt,i+ξt,i, where δt,i measures client drift and ξt,i indicates the time drift of {t, i}. We assume E [δ|ω] = 0, E [ξ|ω] = 0, and thus E [ ‖δ‖2 |ω ] ≤ G2 +B2E‖∇f(ω)‖2 and E [ ‖ξ‖2 |ω ] ≤ D̂2 + Â2E‖∇fi(ω)‖2.
We can derive the corollary from Assumption 3 that E [ ‖ξ‖2 |ω ] ≤D̂2+Â2G2+Â2B2E‖∇f(ω)‖2,
which can simplified to E [ ‖ξ‖2 |ω ] ≤ D2 +A2E‖∇f(ω)‖2, by assuming A2 = Â2B2, D2 =
D̂2+Â2G2. Assumption 3 assumes the bounded E [ ‖δ‖2 |ω ] and E [ ‖ξ‖2 |ω ] in CFL framework, which is
equivalent to the widely used (G,B) gradient drift assumption1 (Gower et al., 2019; Karimireddy et al., 2020b) on the bounded E [ ‖∇fi(ω)‖2 ] . We prove this claim in Appendix B.1.
Assumption 4 (Bounded information loss). We assume the information loss ∆t,i(ω) can be bounded by an arbitrary non-negative value R, i.e. ‖∆t,i(ω)‖ ≤ R. Remark 3.3. The exact information loss in Assumption 4 may be intractable for some approximation methods. In Lemma B.3 of Appendix B.3, we showcase a tight analysis of information loss for Taylor extension based regularization methods.

heading: 4 THEORETICAL RESULTS
text: In this section, we analyze the theoretical performance of Algorithm 1 under Assumption 1–4. We prove that CFL methods converges faster than FedAvg, despite that the term (refer to ϕt in Theorem 4.1) induced by information loss concurrently trades off the optimization. Additionally, our results include the FedAvg rate (and match the prior work) and a novel convergence rate for SGD on CL. In Table 1, we summarize the convergence rate of different algorithms2. The proof details refer to Appendix B.4 and Appendix B.5.

heading: 4.1 CONVERGENCE RATE OF CFL METHODS
text: We start our analysis of Algorithm 1 from the one round progress of CFL methods in the Theorem stated below.
1The (G,B) gradient drift: E [ ‖∇fi(ω)‖2 ] ≤ G2E [ ‖∇f(ω)‖2 ] +B2, where G2 ≥ 1 and B2 ≥ 0.
2To match the notations of prior works that include all clients in all training rounds, we use the abbreviation N to denote the number of selected clients in each round in this section.
Theorem 4.1 (One round Progress of CFL methods). When {ft,i(ω)} satisfy Assumption 1–4, and let η = Kηgηl, we have the one round progress of CFL methods as,
f(ωt)− f(ω∗) ≤ 1 η (1− µη 2 )E‖ωt − ω∗‖2 − 1 η E‖ωt+1 − ω∗‖2︸ ︷︷ ︸
A1
+ c1η + c2η 2︸ ︷︷ ︸
A2
+ϕt , (6)
where c1 = 2cpG+ σ2 NK+2cR, c2 = LcpG 3η2g + Lσ 2 6η2gK +LcR3η2g , cpG = 1 N ∑N i=1G 2+D2( ∑t τ=1 p 2 τ,i), cR =
1 N ∑N i=1( ∑t−1 τ=1 pτ,i) 2R2. ϕt is a constant satisfying ϕt = O ( 1 N ∑N i=1 ∑t−1 τ=1 pt,iR ‖ω0 − ω∗‖ ) .

heading: N is the number of chosen clients in each round, and K is the number of local iterations.
text: Theorem 4.1 shows the one round progress of CFL methods. The A1 part of (6) indicates the linear convergence rate, while the A2 part illustrates the worsened convergence induced by gradient noise and information loss. ϕt is a constant related to the information loss that causes the drift of the optimum. When the upper limit on information loss R exceeds 0, we cannot reach the exact optimum due to the approximation error: the iterates instead reach the neighborhood of + ϕ, where ϕ =
∑T t=1 qtϕt∑T t=1 qt
for some sequence qt. We show in Section 5 that in practice, the approximation methods with small information loss converge much better than methods with larger information loss.
Theorem 4.2 (Convergence rate of CFL methods). Assume {ft,i(ω)} satisfy Assumption 1– 4, the output of Algorithm 1 has expected error smaller than + ϕ, for ηg = 1, ηl ≤√
3+4(1+B2+A2)− √ 4(1+B2+A2)
6KL √ 1+B2+A2
, pτ,i = D 2 tD2+(t−1)R2 (τ < t), and pt,i = (t−1)R2+D2 tD2+(t−1)R2 on round t.
When {ft,i(ω)} are µ-strongly convex functions, we have, T = O ( LcO µ + σ 2 µNK + cA µ + √ cB µ + √ cC µ2 + 3 √ cD µ2 ) , (7)
and when {ft,i(ω)} are general convex functions (µ = 0), we have T = O ( cOF+ √ cBF+ 3 √ cDF 2 + σ
2F NK 2 + cAF 2
+ √ cCF 2
3
) , (8)
and when {ft,i(ω)} are non-convex, setting η=Kηgηl= √ KN√ TL , and when 1T ∑T t=1 E [ ‖∇f(ωt)‖2 ] converge to , we have
T = O L2(f0 − f∗)2 NKc2m 2 + 1 2 (√ KNc2R1 L + σ2√ NK )2 + √ KNcR2 cm L + (KN) 1 3 c 4 3 R2 ( L) 2 3  , (9) where cO = 1 + A2 + B2, cA = G2 + D 2R2 R2+D2 , cB = D6 (R2+D2)2 , cC = Lσ2 η2gK + LcAη2g , cD = LcBη2g ,
cR1 = R2 R2+D2 , cR2 = D4 (R2+D2)2 , cm is a constant related to A, B and R, and F = ‖ω0 − ω ∗‖2. N is the number of chosen clients in each round, and K is the number of local iterations. We elaborate the choice of pt,i in Appendix B.4.3.
Remark 4.3. When setting N = 1 in Theorem 4.2, we recover the convergence rate of standalone CL methods. To the best of our knowledge, we are the first to provide such theoretical guarantees for SGD: the recent work (Yin et al., 2020a) only gives the convergence rate of GD for regularization based CL methods on general convex case, under the constraint of R = 0.
Remark 4.4. For stateless FL scenarios (clients only appear once during training), we can derive tighter bounds than that of Theorem 4.2. Applying Lemma B.2 to the considered stateless scenario, cA and cB in Theorem 4.2 become cA′ = (G2+D2)R2 G2+D2+R2 and cB′ = (D2+G2)3 (R2+D2+G2)2 , where cA µ + √ cB µ ≥
cA′ µ + √ cB′ µ and cA µ + √ cB µ corresponds to the rate of strongly convex setting in Theorem 4.2.

heading: 4.2 CONVERGENCE RATE OF FEDAVG UNDER TIME-VARYING SCENARIOS
text: To show the faster convergence of CFL methods than FedAvg, we provide the convergence rate of FedAvg under time-varying scenarios. Results are derived from Theorem 4.1, by setting pt,i = 1. Note that when pt,i = 1, we can set ϕt to 0.
Theorem 4.5 (Convergence rate of FedAvg under time-varying scenarios). Assume {ft,i(ω)} satisfy Assumption 1–4, the output of FedAvg has expected error smaller than , for ηg = 1 and ηl ≤√
3+4(1+B2+A2)− √ 4(1+B2+A2)
6KL √ 1+B2+A2
. When {ft,i(ω)} are µ-strongly convex functions, we have,
T = O ( LcO µ + σ 2 µNK + cA µ + √ cC µ2 ) , (10)
and when {ft,i(ω)} are general convex functions (µ = 0), we have T = O ( cOF + σ 2F
NK 2 + cAF 2 + √ cCF 2 3 ) , (11)
where cO = 1 + A2 + B2, cA = G2 + D2, cC = Lσ 2 η2gK + LcAη2g , and F = ‖ω0 − ω∗‖2. N is the number of chosen clients in each round, and K is the number of local iterations. Remark 4.6. CFL methods accelerates the convergence by reducing the variance term. As stated in Theorem 4.2 and Theorem 4.5, FedAvg (under time-varying scenarios) is a special case of CFL methods by setting pt,i = 1, and we can show by proof (in Appendix B.4) that it is equivalent to setting the upper bound of information loss R → ∞ (we can also observe this result by setting R → ∞ in pt,i = (t−1)R 2+D2
tD2+(t−1)R2 in Theorem 4.2). The upper bound R is linearly correlated to
gradient noise, where cA = G2 + D 2R2 R2+D2 in Theorem 4.2 increases to cA = G 2 +D2 in Theorem 4.5.

heading: 5 EXPERIMENTS
text: In our numerical investigation, we first use the Noisy Quadratic Model—a simple convex model—to verify our theoretical results stated in Section 4. The results (in Appendix C.1) demonstrate that CFL methods converge much faster than baselines like FedAvg and FedProx, with a smoother convergence curve. These findings are corroborate Remark 4.6 about the variance reduction effect of CFL methods. We further provide extensive empirical evaluations below by comparing CFL methods with various strong FL competitors on different realistic datasets. We explore several approximation techniques in CFL methods and shed light on achieving practical efficient federated learning with time-varying data heterogeneity.

heading: 5.1 SETUP
text: Time-varying heterogeneous local datasets. We consider federated learn an image classifier using ResNet18 on split-CIFAR10 and split-CIFAR100 datasets, as well as a two layer MLP on the split-Fashion-MNIST dataset. The “split” follows the idea introduced in Yurochkin et al. (2019); Hsu et al. (2019); Reddi et al. (2021), where we leverage the Latent Dirichlet Allocation (LDA) to control the distribution drift with parameter α (See Algorithm 4). Larger α indicates smaller drifts. Unless specifically mentioned otherwise our studies use the following protocol. All datasets are partitioned to 210 subsets for 7 distinct clients: all clients are selected and trained for 500 communication rounds, and each client randomly samples one of the corresponding 30 subsets for the local training— this challenging time-varying scenario mimics the realistic client data sampling scheme (from some underlying distributions). Notably, the training strategy used in this section is applicable to all FL baselines and CFL methods, and we assess the model performance using a global test dataset3. We carefully tune the hyper-parameters in all algorithms (details refer to Appendix C.2.1), and report the optimal results (i.e. mean test accuracy across the past 5 best epochs) after repeated trials.
Approximation techniques in CFL methods. Below, we review three representative types of information approximation techniques in CL, and use them to investigate the effect of various types of information loss under the (CFL) formulation. We refer to Appendix C.2.2 for a more comprehensive introduction and discussion. • Regularization methods. Instead of keeping datasets from previous rounds, we keep track
the gradients and Hessian matrices of local objective functions, and use Taylor Extension to approximate the local objective functions in previous rounds. Note that the trade-off between Hessian estimation and computational overhead constrains the practical feasible of such approach. • Core set methods. Another simple yet effective treatment in CL lines in the category of Exemplar Replay (Rebuffi et al., 2017; Castro et al., 2018). This method selects and regularly saves previous core-set samples (a.k.a. exemplars), and replays them with the current local datasets. 3The training loss/accuracy on (CFL) formulation are closely aligned with that of global test data, as shown in Figure 5 of Appendix C.2.3. We here only present the global test results for the common interests in practice.
• Generative methods. Maintaining a core set for each client may become impractical when learning scales to millions of clients. To ensure a privacy-preserved federated learning, the generative models (Goodfellow et al., 2014) could be used locally to capture the local data distribution: fresh data samples will be generated on the fly and combined with the current local dataset. For the sake of simplicity, we use Markov Chain Monte Carlo (Nori et al., 2014) in our assessment.

heading: 5.2 RESULTS
text: Comments on different CFL approximation techniques. In Table 2, we examine the performance of several approximation techniques using the split-CIFAR10 dataset. We can conclude that (1) Core set methods outperform other methods by a significant margin. The simple choice of “naive core set”, i.e. randomly and uniformly sample data from the local dataset, surpasses the sampling technique described in iCaRL (Rebuffi et al., 2017)4 for CL, despite their faster convergence in the initial training phase. (2) The quality of Hessian estimation matters for regularization based methods. PyHessian (Yao et al., 2020), as a method to approximate diagonal Hessian matrix, is slightly preferable than Fisher Information Matrix, though the latter one involves less computation. (3) The performance of generative methods is restricted, and we hypothesize that the poor quality of generated samples contributes to the constraint. In the subsequent evaluation, we consider naive core set sampling for CFL-Core-Set method, and use PyHessian for CFL-Regularization. We exclude the results of generative methods, due to the trivial performance gain and significant computational overhead.
Understanding various approximated CFL implementations on different datasets. Table 3 experimentally studies the impacts of various information approximation techniques in CFL methods— as discussed in Section 5.1—and compares them with the backbone algorithm of CFL methods, i.e. FedAvg. We have the following consistent findings on different datasets. 1. The improvement of CFL methods over FedAvg becomes larger for more challenging tasks, as
shown in the bottom of the Table 3 for regularization based methods. This might reflect the fact that the precision of the information approximation is more crucial for complicated tasks. Similarly, we demonstrate in Figure 6 (in Appendix C.2.3) that CFL methods offer better resistance to time-varying non-iid data and the significance of such finding is depending on the task difficulty. 2. For CFL-Regularization method, applying regularization terms on top layers works better than that on all layers. This observation matches the recent work on decoupling feature extractor and classifier (Collins et al., 2021; Chen & Chao, 2021; Luo et al., 2021): the bottom layers are more generic across tasks and can serve as a global feature extractor, while the top layers are subject to task-specific information. 3. The core-set method consistently outperforms FedAvg and other CFL approximation techniques by a large margin. We further investigate the connection between the information loss and the learning performance. We examine CFL methods with naive core sets, where the degree of information loss5 can be changed
4The algorithmic details of the sampling method in iCaRL refer to Algorithm 3 in Appendix C.2.2. 5We estimate the information loss by using 1
tS ∑S i=1 ∑t τ=1 ‖∆τ,i(ω)‖, where ∆τ,i(ω) is defined in
Equation (3), S is the number of clients chosen in each round, and t is the number of communication rounds.
by altering the core set size from 20 to 150, with the same random seed and optimizers. Figure 1 depicts that the performance of models is highly linked to the value of information loss: the lesser the information loss, the higher the performance.
Superior performance of CFL methods over other strong FL baselines. Alongside the comparison between CFL methods and FedAvg on various datasets (Table 3), in Table 4 we verify the efficacy of CFL methods over other strong FL baselines, on split-CIFAR10 dataset. We also examine MimeLite (Karimireddy et al., 2020a), a method suggested for stateless FL scenarios. Note that we exclude the results illustration for methods like SCAFFOLD (Karimireddy et al., 2020b) and Ditto (Li et al., 2021), due to their infeasibility to be applied in our continual scenarios6.
We further relax the difficulty of federated continual learning, from challenging nonoverlapping time-varying heterogeneous data (e.g. in Table 2 and Table 3) to a moderate time-varying case (i.e. the local data evolves with the overlapping, while the size of local datasets stay unchanged). Table 5 illustrates the performance of FL baselines and CFL methods, under different degrees of overlapping (the construction details refers to Appendix C.2.1): the improvement of CFL methods is consistent to our previous results, while the overlap
parameter has no obvious connection with the final global test performance. We believe that both the overlap degree and the new arriving data influence final performance, and we leave future work on realistic time-varying FL datasets to gain a better understanding.
Investigating other time-varying scenarios. In previous numerical investigations, we examine the stateful clients and assume that these clients would learn and retain their client states throughout the training process. The remainder of this section will discuss how to learn with stateless clients (i.e. each client only appear once). To do this, we change the data partition strategy such that fresh data partitions are sampled on the fly for each client and communication round. Table 6 evaluates the above-mentioned scenario. We find that CFL-Regularization methods consistently outperform alternative FL baselines, similar to the observations in Table 4. However, due to the nature of stateless under the privacy concern, the advancements of core set method in CFL algorithm cannot be seen in this scenario. Additionally, we discuss the applicability of different algorithms in a variety of time-varying scenarios in Table 8 of Appendix C.2.3.

heading: CONTENTS OF APPENDIX

heading: A Techniques 14

heading: B Convergence rate of CFL 15
text: B.1 Bound of Gradient Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 B.2 Bounded Gradient Noise of CFL . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 B.3 Bounded Approximation Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 B.4 Proof of Theorem 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
B.4.1 Start up. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 B.4.2 One Step Progress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 B.4.3 Weights of rounds. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 B.4.4 Convergence results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
B.5 Proof of convergence rate for non-convex setting . . . . . . . . . . . . . . . . . . 21

heading: C Experiment details 25
text: C.1 Noisy quadratic model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 C.2 Realistic datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
C.2.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 C.2.2 Approximation Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 C.2.3 Additional Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
C.3 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

heading: A TECHNIQUES
text: Here we show some technical lemmas which are helpful in the theoretical proof. Lemma A.1 (Linear convergence rate (Karimireddy et al., 2020b, Lemma 1)). For every nonnegative sequence {dr−1}r≥1, and any parameter µ > 0, T ≥ 12ηmaxµ , there exists a constant step-size η ≤ ηmax and weights ωt = (1− µη)1−t such that for WT = ∑T+1 t=1 ωt
ΦT = 1
WT T+1∑ t=1 ( ωt−1 η (1− µη)dt−1 − ωt η dt ) = Õ (µd0exp(−µηmaxT )) . (12)
Lemma A.2 (Sub-linear convergence rate (Karimireddy et al., 2020b, Lemma 2)). For every nonnegative sequence {dr−1}r≥1 and any parameters ηmax > 0, c1 ≥ 0, c2 ≥ 0, T ≥ 0, there exists a constant step-size η ≤ ηmax such that
ΦT = 1
T + 1 T+1∑ t=1 ( dt−1 η − dt η + c1η + c2η 2 ) ≤ d0 ηmax(T + 1) + 2 √ c1d0√ T + 1 + 2 ( d0 T + 1 ) 2 3 c 1 3 2 .
(13) Lemma A.3 (Relaxed triangle inequality (Karimireddy et al., 2020b, Lemma 3)). Let {v1, ...,vτ} be τ vectors inRd. Then the following is true:
‖1 τ τ∑ i=1 vi‖2 ≤ 1 τ τ∑ i=1 ‖vi‖2 . (14)
Lemma A.4 (Separating mean and variance (Stich & Karimireddy, 2020, Lemma 14)). Let Ξ1,Ξ2, ...,Ξτ be τ random variables in Rd which are not necessarily independent. First suppose that their mean is E[Ξi] = ξi, and variance is bounded as E‖Ξi − ξi‖2 ≤M‖ξi‖2 + σ2, then the following holds
E ∥∥∥∥∥ τ∑ i=1 Ξi ∥∥∥∥∥ 2 ≤ (τ +M) τ∑ i=1 ‖ξi‖2 + τσ2 . (15)
Lemma A.5 (Perturbed strongly convexity (Karimireddy et al., 2020b, Lemma 5)). The following holds for any L-smooth and µ-strongly convex function h, and any x, y, z in the domain of h:
〈∇h(x), z− y〉 ≥ h(z)− h(y) + µ 4 ‖y − z‖2 − L‖z− x‖2 . (16)
Lemma A.6. Define S = ∑T t=1 pt t where ∑T t=1 pt = 1, and pt ≤ pt+1 then S ≤ 1 T ∑T t=1 1 t =
Õ ( lnT T ) .

heading: B CONVERGENCE RATE OF CFL

heading: B.1 BOUND OF GRADIENT NOISE
text: Lemma B.1 (Bound of Gradient Noise). Suppose fi(ω) is the local objective function, and f(ω) = E [fi(ω)] is the global objective function. Define ∇f(ω) = ∇fi(ω) + ςi, E[ςi] = 0, and assume E [ ‖ς‖2 |ω ] ≤ A2E [ ‖∇f(ω)‖2 ] +B2, we have
E [ ‖∇fi(ω)‖2 ] ≤ (A2 + 1)E [ ‖∇f(ω)‖2 ] +B2 . (17)
Proof.
E [ ‖∇fi(ω)‖2 ] = E [ ‖∇f(ω) + ςi‖2 ] (18)
= E [ ‖∇f(ω)‖2 ] + E [ ‖ςi‖2 ] (19)
≤ (A+ 1)E [ ‖∇f(ω)‖2 ] +B . (20)

heading: B.2 BOUNDED GRADIENT NOISE OF CFL
text: Lemma B.2 (Bounded Gradient Noise of CFL). For Formulation (CFL), consider CFL and FedAvg, we can bound the gradient drift as (1) FedAvg only optimize current local objective functions, thus,
E‖∇ft,i(ω)‖2 ≤ (1 +A2 +B2)E‖∇f(ω)‖2 +G2 +D2 .
(2) For CFL, in general (same clients can appear in different rounds), we have
E ∥∥∥∥∥ t∑
τ=1
pτ,i∇fτ,i(ω) ∥∥∥∥∥ 2 ≤ ( 1 +B2 +A2 t∑ τ=1 p2τ,i ) E‖∇f(ω)‖2
+G2 +D2 t∑
τ=1
p2τ,i .
(3) For CFL, when clients only participate in training once(δt,i are independent for all t and i), we have
E ∥∥∥∥∥ t∑
τ=1
pτ,i∇fτ,i(ω) ∥∥∥∥∥ 2 ≤ ( 1 + (B2 +A2) t∑ τ=1 p2τ,i ) E‖∇f(ω)‖2
+ (G2 +D2) t∑ τ=1 p2τ,i .
Proof. Using Assumption 3, together with the fact that∇ft,i(ω) = ∇f(ω) + δt,i + ξt,i, we have
E‖∇ft,i(ω)‖2 = E‖∇f(ω) + δt,i + ξt,i‖2 (21) = E‖∇f(ω)‖2 + E‖δt,i‖2 + E‖ξt,i‖2 (22) ≤ (1 +A2 +B2)E‖∇f(ω)‖2 +G2 +D2 . (23)
The second inequality is based on the independence of noise, and directly use Assumption 3 we get the last inequality. Similarly, we have
E ∥∥∥∥∥ t∑
τ=1
pτ,i∇fτ,i(ω) ∥∥∥∥∥ 2 = E ∥∥∥∥∥ t∑
τ=1
pτ,i(∇fτ,i(ω) + δi + ξτ,i) ∥∥∥∥∥ 2
(24)
= E‖∇f(ω)‖2 + E‖δi‖2 + E ∥∥∥∥∥ t∑
τ=1
pτ,iξτ,i ∥∥∥∥∥ 2
(25)
≤ ( 1 +B2 +A2
t∑ τ=1 p2τ,i
) E‖∇f(ω)‖2 +G2 +D2
t∑ τ=1 p2τ,i . (26)
For the last inequality, when δt1,i and δt2,i are independent for all t1, t2,
E ∥∥∥∥∥ t∑
τ=1
pτ,i∇fτ,i(ω) ∥∥∥∥∥ 2 = E ∥∥∥∥∥ t∑
τ=1
pτ,i(∇fτ,i(ω) + δt,i + ξτ,i) ∥∥∥∥∥ 2
(27)
= E‖∇f(ω)‖2 + E ∥∥∥∥∥ t∑
τ=1
pτ,iδt,i ∥∥∥∥∥ 2 + E ∥∥∥∥∥ t∑
τ=1
pτ,iξτ,i ∥∥∥∥∥ 2
(28)
≤ ( 1 + (A2 +B2)
t∑ τ=1 p2τ,i
) E‖∇f(ω)‖2 + (G2 +D2)
t∑ τ=1 p2τ,i . (29)

heading: B.3 BOUNDED APPROXIMATION ERROR
text: Lemma B.3 (Bounded Approximation Error). For ∆t,i(ω) = ∇ft,i(ω)−∇f̃t,i(ω) (c.f. Definition 3), when use Taylor Extension,
∇f̃t,i(ω) = ∇ft,i(ωt) +∇2ft,i(ωt)(ω − ωt) ,
we have
‖∆t,i(ω)‖ ≤ ‖ω − ω̂t,i‖ .
Proof.
‖∆t,i(ω)‖ = ∥∥∥∇ft,i(ω)−∇f̃t,i(ω)∥∥∥ (30)
= ‖∇ft,i(ω)−∇ft,i(ωt,i,K)−HtjK(ω − ωt,i,K)‖ (31) = ∥∥∇2ft,i(ωξ,t)(ω − ωt,i,K)−HtjK(ω − ωt,i,K)∥∥ (32)
= ∥∥(∇2ft,i(ωξ,t)−HtjK)(ω − ωt,i,K)∥∥ (33)
≤ ‖ω − ωt,i,K‖ . (34)
The first two equations come from the mean value theorem which says for continuous function f in closed intervals [a, b] and differentiable on open interval (a, b), there exists a point c ⊆ (a, b) such that
f ′(c) = f(b)− f(a)
b− a . (35)
The last inequality is based on Assumption 4.

heading: B.4 PROOF OF THEOREM 4.2
text: In this section we will give the complete proof of convergence rate of algorithm 2 when the local objective functions are convex.
Algorithm 2 CFL Framework Require: initial weights ω0, global learning rate ηg , local learning rate ηl
1: for round t = 1, . . . , T do 2: communicate ωt to the chosen clients. 3: for client i ∈ St in parallel do 4: initialize local model ωt,i,0 = ωt. 5: for k = 1, . . . ,K do 6: g̃t,i,k(ωt,i,k−1) = ( pt,i∇ft,i(ωt,i,k−1) + ∑t−1 τ=1 pτ,i∇f̃t,i(ωt,i,k−1) ) + νt,i,k.
7: ωt,i,k ← ωt,i,k−1 − ηlg̃t,i,k(ωt,i,k−1). 8: communicate ∆ωt,i ← ωt,i,K − ωt. 9: ∆ωt ← ηgS ∑ i∈St ∆ωt,i.
10: ωt+1 ← ωt + ∆ωt.

heading: B.4.1 START UP.
text: The local objective function of round t on client i is
f̄t,i(ω) = (pt,ift,i(ω) + t−1∑ τ=1 pτ,if̃τ,i(ω) . (36)
Without loss of generality, assume ∑t τ=1 pτ,i = 1. Then follow the steps in algorithm 2, we have
∇f̄t,i(ω) = pt,i∇ft,i(ω) + t−1∑ τ=1 pτ,i∇f̃τ,i(ω) . (37)
Then the noisy gradient in mini-batch SGD can be described as
ḡt,i,k(ωt,i,k−1) = ∇f̄t,i(ωt,i,k−1) + νt,i,k (38) Then follow the steps in algorithm 2, we have
∆ωt = −ηlηg N N∑ i=1 K∑ k=1 ḡt,i(ωt,i,k−1) , (39)
E[∆ωt] = −ηlηg N N∑ i=1 K∑ k=1 ∇f̄t,i(ωt,i,k−1) . (40)
Then let η = Kηlηg , we have
∆ωt = −η NK N∑ i=1 K∑ k=1 ḡt,i(ωt,i,k−1) , (41)
E[∆ωt] = −η NK N∑ i=1 K∑ k=1 ∇f̄t,i(ωt,i,k−1) . (42)

heading: B.4.2 ONE STEP PROGRESS
text: Consider the one-step progress we have
E‖ωt + ∆ωt − ω∗‖2 = ‖ωt − ω∗‖2 − 2E〈ωt − ω∗,∆ωt〉︸ ︷︷ ︸ A1 +E‖∆ωt‖2︸ ︷︷ ︸ A2 . (43)
Firstly we consider A1 part in equation (43),
− 2E〈ωt − ω∗,∆ωt〉
= 2η
NK N∑ i=1 K∑ k=1 〈∇f̄t,i(ωt,i,k−1),ω∗ − ωt〉 (44)
= 2η
NK N∑ i=1 K∑ k=1 〈pt,i∇ft,i(ωt,i,k) + t−1∑ τ=1 pτ,i∇f̃τ,i(ωt,i,k),ω∗ − ωt〉 (45)
= 2η
NK N∑ i=1 K∑ k=1 t∑ τ=1 〈pτ,i∇fτ,i(ωt,i,k),ω∗ − ωt〉 − 2η NK N∑ i=1 K∑ k=1 t−1∑ τ=1 pτ,i〈∆τ,i(ωt,i,k),ω∗ − ωt〉
(46)
≤ 2η NK N∑ i=1 K∑ k=1 t∑ τ=1 pτ,i〈∇fτ,i(ωt,i,k),ω∗ − ωt〉+ 2η N N∑ i=1 t−1∑ τ=1 pτ,iR ‖ω∗ − ωt‖ . (47)
We use equality (42) for first inequality, and directly use Assumption 4 and Cauchy–Schwarz inequality for last inequality. Then we can consider the first term of inequality (47). Firstly, by Lemma A.5 we see that
〈∇fτ,i(ωt,i,k−1),ω∗ − ωt〉 ≤ fτ,i(ω∗)− fτ,i(ωt)− µ
4 ‖ωt − ω∗‖2 + L‖ωt,i,k−1 − ωt‖2 . (48)
That is, based on (47) and (48), we have,
− 2E〈ωt − ω∗,∆ωt〉
≤ −2η(ft(ωt)− ft(ω∗) + µ
4 ‖ωt − ω∗‖2) +
2ηL
NK N∑ i=1 K∑ k=1 ‖ωt,i,k−1 − ωt‖2
+ 2η t−1∑ τ=1 pτ,iR ‖ω∗ − ωt‖ . (49)
Then considerA2 in (43), and define cpB ,i = 1+B 2+A2( ∑t τ=1 p 2 τ,i), cpG,i = G 2+D2( ∑t τ=1 p 2 τ,i), cpB = 1 N ∑N i=1 cpB ,i, and cpG = 1 N ∑N i=1 cpG,i we have
E‖∆ωt‖2
= η2
N2K2 E ∥∥∥∥∥ N∑ i=1 K∑ k=1 ( pt,i∇ft,i(ωt,i,k−1) + t−1∑ τ=1 pτ,i∇f̃τ,i(ωt,i,k−1) + νt,i,k )∥∥∥∥∥ 2
(50)
= η2
N2K2 E ∥∥∥∥∥ N∑ i=1 K∑ k=1 ( t∑ τ=1 pτ,i∇fτ,i(ωt,i,k−1)− t−1∑ τ=1 pτ,i∆τ,i(ωt,i,k−1) + νt,i,k )∥∥∥∥∥ 2
(51)
Lem A.4 ≤ η 2
NK N∑ i=1 K∑ k=1 E ∥∥∥∥∥ t∑ τ=1 pτ,i∇fτ,i(ωt,i,k−1)− t−1∑ τ=1 pτ,i∆τ,i(ωt,i,k−1) ∥∥∥∥∥ 2 + η2σ2 NK (52)
Lem A.3 ≤ 2η 2
NK N∑ i=1 K∑ k=1 E∥∥∥∥∥ t∑ τ=1 pτ,i∇fτ,i(ωt,i,k−1) ∥∥∥∥∥ 2 + E ∥∥∥∥∥ t−1∑ τ=1 pτ,i∆τ,i(ωt,i,k−1) ∥∥∥∥∥ 2 + η2σ2 NK (53)
Lem ?? ≤ 2η
2
NK N∑ i=1 K∑ k=1
(( 1 +B2 +A2(
t∑ τ=1 p2τ,i)
) E‖∇f(ωt,i,k−1)‖2 + ( G2 +D2(
t∑ τ=1 p2τ,i)
)) + 2η2
N N∑ i=1 ( t−1∑ τ=1 pτ,i) 2R2 + η2σ2 NK
(54)
Lem A.3 ≤ 4η 2
NK N∑ i=1 K∑ k=1 cpB ,i ( E‖∇f(ωt,i,k−1)−∇f(ωt)‖2 + E‖∇f(ωt)‖2 ) + 2η2cpG + 2η2 N N∑ i=1 ( t−1∑ τ=1 pτ,i) 2R2 + η2σ2 NK
(55)
Ass 1
≤ 16η2LcpB (f(ωt)− f(ω ∗)) +
8η2L2
NK N∑ i=1 K∑ k=1 cpB ,iE‖ωt,i,k−1 − ωt‖ 2 + 2η2cpG + 2η2 N N∑ i=1 ( t−1∑ τ=1 pτ,i) 2R2 + η2σ2 NK .
(56)
Then consider equation (49) and (56), to solve E‖ωt,i,k−1 − ωt‖2, we have
E‖ωt,i,k − ωt‖2 = η2l E ∥∥∥∥∥ k∑ τ=1 ḡt,i(ωt,i,τ−1) ∥∥∥∥∥ 2
(57)
Lem A.4 ≤ kη2l k∑ τ=1 E ∥∥∇f̄t,i(ωt,i,τ−1)∥∥2 + kη2l σ2 . (58)
Here we directly use Lemma A.4 to get inequality (58).
Then for E ∥∥∇f̄t,i(ω)∥∥2, we have
E ∥∥∇f̄t,i(ω)∥∥2
= E ∥∥∥∥∥pt,i∇ft,i(ω) + t−1∑ τ=1 pτ,i∇f̃τ,i(ω) ∥∥∥∥∥ 2
(59)
= E ∥∥∥∥∥ t∑
τ=1 pτ,i∇fτ,i(ω)− t−1∑ τ=1 pτ,i∆τ,i(ω) ∥∥∥∥∥ 2
(60)
Lem A.3 ≤ 2E ∥∥∥∥∥ t∑
τ=1
pτ,i∇fτ,i(ω) ∥∥∥∥∥ 2 + 2E ∥∥∥∥∥ t−1∑ τ=1 pτ,i∆τ,i(ω) ∥∥∥∥∥ 2
(61)
Lem ?? ≤ 2cpB ,iE‖∇f(ω)‖ 2 + 2cpG,i + 2( t−1∑ τ=1 pτ,i) 2R2 (62)
Ass 1 ≤ 4L2cpB ,iE‖ω − ωt‖ 2 + 8LcpB ,i (f(ωt)− f(ω∗)) + 2cpG,i + 2( t−1∑ τ=1 pτ,i) 2R2 . (63)
Combine equation (58) and (63) we get,
E‖ωt,i,k − ωt‖2
≤ 4k2η2l L2cpB ,iE‖ωt,i,k−1 − ωt‖ 2 + 8k2η2l LcpB ,i(f(ωt)− f(ω∗)) + 2k2η2l cpG,i + 2k2η2l ( t−1∑ τ=1 pτ,i) 2R2 + kη2l σ 2 .
(64)
That is,
E‖ωt,i,k − ωt‖2
≤ k−1∑ τ=0 (8K2η2l LcpB ,i(f(ωt)− f(ω∗)) + 2K2η2l cpG,i + 2K2η2l ( t−1∑ τ=1 pτ,i) 2R2 +Kη2l σ 2)(4K2η2l L 2cpB ,i) τ
(65)
≤ 8K2η2l LcpB ,i(f(ωt)− f(ω∗)) + 2K2η2l cpG,i + 2K2η2l (
∑t−1 τ=1 pτ,i) 2R2 +Kη2l σ 2
1− 4K2η2l L2cpB ,i . (66)
Combine the equation (43), (49), (56), and (66), we get
E‖ωt + ∆ωt − ω∗‖2
≤ (1− µη 2 )E‖ωt − ω∗‖2 + (−2η + 16η2LcpB + 1 N N∑ i=1 16K2ηη2l LcpB ,i(1 + 4ηLcpB ,i) 1− 4K2η2l L2cpB ,i )(f(ωt)− f∗) + 2η2cpG
+ η2σ2
NK +
1
N N∑ i=1
( 2η2(
t−1∑ τ=1 pτ,i) 2 + 4K2ηη2l L( ∑t−1 τ=1 pτ,i) 2(1 + 4ηLcpB ,i) 1− 4K2η2l L2cpB ,i ) R2
+ 1
N N∑ i=1 2Kηη2l L(2KcpG,i + σ 2)(1 + 4ηLcpB ,i) 1− 4K2η2l L2cpB ,i + 2η N N∑ i=1 t−1∑ τ=1 pτ,iR ‖ωt − ω∗‖ . (67)
Then we notice that
−2η + 16η2LcpB + 1
N N∑ i=1 16K2ηη2l L 2cpB ,i(1 + 4ηLcpB ,i) 1− 4K2η2l L2cpB ,i ≤ 0 . (68)
Use the fact that η = Kηlηg , and solve above inequality, we notice that if η satisfy
η ≤
√ 3η2g + 4cpB ,iη 4 g − √ 4cpB ,iη 4 g
6L √ cpB ,i
, (69)
for any cpB ,i, convergence can be promised. Define ĉpB as the largest cpB ,i, let η ≤√ 3η2g+4ĉpBη 4 g− √ 4ĉpBη 4 g
12L √ ĉpB
, we have 1 − 4K2η2l L2cpB ,i ≥ 33−8η2g ĉpB+4
√ 3η2g ĉpB+4η 4 g ĉ 2 pB
36 , and then 1+4ηLcpB,i
1−4K2η2l L2cpB,i ≤ 112 − 7 33+ √ 3η2g ĉpB+4η 4 g ĉ 2 pB −2η2g ĉpB ≤ 112 . Define cR,i = ( ∑t−1 τ=1 pτ,i) 2R2, and cR = 1N ∑N i=1 cR,i. Assume c1 = 2cpG + σ2
NK + 2cR, c2 =
LcpG 3η2g + Lσ 2 6η2gK + LcR3η2g , and c3 = 2N ∑N i=1 ∑t−1 τ=1 pτ,iR, inequality (67) become
E‖ωt + ∆ωt − ω∗‖2 ≤ (1− µη
2 )E‖ωt − ω∗‖2 − η(f(ωt)− f∗) + c1η2 + c2η3 + c3η ‖ωt − ω∗‖ .
(70)
Move f(ωt)− f∗ to the left side, we get
f(ωt)− f(ω∗) ≤ 1 η (1− µη 2 )E‖ωt − ω∗‖2 − 1 η E‖ωt+1 − ω∗‖2 + c1η + c2η2 + ϕt . (71)
Here ϕt is a constant bounded by c3 ‖ω0 − ω∗‖. Because of ϕt, the model cannot converge to an arbitrary ; instead, it can only converge to the neighborhood of + ϕ, where ϕ is the weighted sum of the sequence ϕt. The following parts give the convergence rates when models converge to + ϕ for convenience.

heading: B.4.3 WEIGHTS OF ROUNDS.
text: We can carefully tune the pτ,i to minimize the noise while speeding up the convergence. Here we give the lemma of the best choice of pτ,i.
Lemma B.4. On round t, when setting pτ,i = D 2 tD2+(t−1)R2 for any τ < t, and pt,i = (t−1)R2+D2 tD2+(t−1)R2 , we can minimize c1 and c2 to get best convergence.
Proof. Minimizing c1 and c2 is equal to minimize cpG + cR, that is,
min p
1
N N∑ i=1 (1− pt,i)2R2 +G2 +D2( t∑ τ=1 p2τ,i) ,
s.t. t∑ τ=1 pτ,i = 1,∀i = 1, . . . , N . (72)
Solving above optimization problem, we get the results. Using lemma B.4, we have min{cpG + cR} = G2 +D2 ( D2+(t−1)R2 tD2+(t−1)R2 ) . Notice that the value of c1, c2, and c3 are changing over t. We use ct1, c t 2, and c t 3 to represent c1, c2, and c3 on round t.

heading: B.4.4 CONVERGENCE RESULTS
text: Strongly convex functions. By equation (80), when ft,i(ω) are strongly convex functions, using Lemma A.1, and define qt = (1− µη2 ) 1−t, we have
f(ωF )− f(ω∗) ≤ O ( µ ‖ω0 − ω∗‖2 exp(− µηT
2 )
) +
1∑T t=1 qt
qt ( c1η + c2η 2 + ϕt ) . (73)
By Lemma A.6, we have,
1∑T t=1 qt T∑ t=1 qt(cR + cpG) = 1∑T t=1 qt T∑ t=1 qt ( G2 +D2 ( D2 + (t− 1)R2 tD2 + (t− 1)R2 ))
= 1∑T t=1 qt T∑ t=1 qt
( G2 +D2 ( R2
R2 +D2 +
D4
(R2 +D2)2 1
t− R2R2+D2
))
= O ( G2 +D2 ( R2
R2 +D2 +
D4
(R2 +D2)2 lnT T
)) . (74)
For ϕt, by Lemma B.4, we have,
ϕ = 1∑T t=1 qt T∑ t=1 qtϕt ≤ O ( R ( D2 D2 +R2 − D 4 (D2 +R2)2 lnT T ) ‖ω0 − ω∗‖ ) . (75)
Then define co1 = 1∑T t=1 qt ∑T t=1 qtc t 1, c o 2 = 1∑T t=1 qt ∑T t=1 qtc t 2, we have,
f(ωF )− f(ω∗)− ϕ ≤ O ( µ ‖ω0 − ω∗‖2 exp(− µηT
2 ) + co1η + c o 2η 2
) (76)
= O ( µ ‖ω0 − ω∗‖2 exp(− µT
LcO ) +
σ2
µNKT + cA µT + cB µT 2 + cC µ2T 2 + cD µ2T 3
) ,
(77)
where cO = 1 +A2 +B2, cA = G2 + D 2R2 R2+D2 , cB = D6 (R2+D2)2 , cC = Lσ2 η2gK + LcAη2g , cD = LcBη2g .
General convex functions. When ft,i(ω) are general convex functions (µ = 0), directly use Lemma A.2 we get,
f(ωF )− f(ω∗)− ϕ ≤ O
( cOF
T +
√ σ2F
NKT + √ FcA T + √ cBF T + 3 √ cCF 2 T 2 + 3 √ cDF 2 T ) ,
(78)
where cO = 1 +A2 +B2, cA = G2 + D 2R2 R2+D2 , cB = D6 (R2+D2)2 , cC = Lσ2 η2gK + LcAη2g , cD = LcBη2g , and F = ‖ω0 − ω∗‖2.
The drift of optimal point. Because of information loss, we can’t get the true optimal point when considering previous rounds’ information. Instead, the drift can be described as
ϕ = co3 ‖ω0 − ω∗‖ = O ( R ( D2
D2 +R2 − D
4
(D2 +R2)2 lnT T
) ‖ω0 − ω∗‖ ) . (79)
Convergence of FedAvg. Notice that FedAvg is a special case of CFL by setting pt,i = 1 on round t. Having this, we derive the one round convergence of FedAvg under our formulation as,
f(ωt)− f(ω∗) ≤ 1 η (1− µη 2 )E‖ωt − ω∗‖2 − 1 η E‖ωt+1 − ω∗‖2 + c1η + c2η2 , (80)
where c1 = 2(G2 + D2) + σ 2 NK , c2 = L(G2+D2) 3η2g + Lσ 2 6η2gK . Then using Lemma A.1, we get the convergence rate when ft,i(ω) are µ strongly convex.
f(ωt)− f(ω∗) ≤ O ( µ ‖ω0 − ω∗‖2 exp( µT
LcO ) + ĉA µT + ĉC µ2T 2
) , (81)
where cO = 1 + A2 + B2, cA = G2 + D2, cC = Lσ 2 η2gK + LcAη2g
. Besides, when ft,i(ω) are general convex, we have,
f(ωF )− f(ω∗) ≤ O
( cOF
T +
√ σ2F
NKT + √ FcA T + 3 √ cCF 2 T 2 ) , (82)
where cO = 1 +A2 +B2, cA = G2 +D2, cC = Lσ 2 η2gK + LcAη2g , and F = ‖ω0 − ω∗‖2.

heading: B.5 PROOF OF CONVERGENCE RATE FOR NON-CONVEX SETTING
text: E [f(ωt+1)] ≤ E [f(ωt)] + E [〈∇f(ωt),∆ωt〉]︸ ︷︷ ︸ A1 + L
2 E [ ‖∆ωt‖2 ] ︸ ︷︷ ︸
A2
(83)
For A1 part, we have,
E [〈∇f(ωt),∆ωt〉]
= −η NK N∑ i=1 K∑ k=1 E [ 〈∇f(ωt),∇f̄t,i(ωt,i,k)〉 ] (84)
= −η NK N∑ i=1 K∑ k=1 E
[ 〈∇f(ωt),
t∑ τ=1 pτ,i∇fτ,i(ωt,i,k)− t−1∑ τ=1 pτ,i∆τ,i(ωt,i,k)〉
] (85)
≤ −η NK N∑ i=1 K∑ k=1 E
[ 〈∇f(ωt),
t∑ τ=1 pτ,i∇fτ,i(ωt,i,k)〉
] + η
2N N∑ i=1 (1− pt,i) ( E [ ‖∇f(ωt)‖2 ] +R2 ) (86)
= η
2NK N∑ i=1 K∑ k=1 E ∥∥∥∥∥∇f(ωt)− t∑ τ=1 pτ,i∇fτ,i(ωt,i,k) ∥∥∥∥∥ 2 − E [‖∇f(ωt)‖2]− E ∥∥∥∥∥ t∑ τ=1 pτ,i∇fτ,i(ωt,i,k) ∥∥∥∥∥ 2 
+ η
2N N∑ i=1 (1− pt,i) ( E [ ‖∇f(ωt)‖2 ] +R2 ) (87)
From equation (53) we have
E [ ‖∆ωt‖2 ] ≤ 2η 2
NK N∑ i=1 K∑ k=1 E∥∥∥∥∥ t∑ τ=1 pτ,i∇fτ,i(ωt,i,k) ∥∥∥∥∥ 2 + E ∥∥∥∥∥ t−1∑ τ=1 pτ,i∆τ,i(ωt,i,k) ∥∥∥∥∥ 2 + η2σ2 NK
(88)
Then when η ≤ 12L , the E ∥∥∥∑tτ=1 pτ,i∇fτ,i(ωt,i,k)∥∥∥2 term can be ignored, since the coefficient
number will less than 0. Then the remaining term in A2 is 2η 2
N ∑N i=1(1− pt,i)2R2 + η2σ2 NK .
Then we are willing to consider the ∥∥∥∇f(ωt)−∑tτ=1 pτ,i∇fτ,i(ωt,i,k)∥∥∥2. Then we have
E ∥∥∥∥∥∇f(ωt)− t∑
τ=1
pτ,i∇fτ,i(ωt,i,k) ∥∥∥∥∥ 2 
= E ∥∥∥∥∥∇f(ωt)−∇f(ωt,i,k) +∇f(ωt,i,k)− t∑
τ=1
pτ,i∇fτ,i(ωt,i,k) ∥∥∥∥∥ 2  (89)
≤ 2E [ ‖∇f(ωt)−∇f(ωt,i,k)‖2 ] + 2E ∥∥∥∥∥∇f(ωt,i,k)− t∑
τ=1
pτ,i∇fτ,i(ωt,i,k) ∥∥∥∥∥ 2  (90)
≤ 2L2E [ ‖ωt − ωt,i,k‖2 ] + ( B2 +A2
t∑ τ=1 p2τ,i
) E [ ‖∇f(ωt,i,k)‖2 ] + ( G2 +D2
t∑ τ=1 p2τ,i ) (91)
≤ 2L2E [ ‖ωt − ωt,i,k‖2 ] + 2L2 ( B2 +A2
t∑ τ=1 p2τ,i
) E [ ‖ωt,i,k − ωt‖2 ] + 2 ( B2 +A2
t∑ τ=1 p2τ,i
) E [ ‖∇f(ωt)‖2 ] + ( G2 +D2
t∑ τ=1 p2τ,i
) (92)
Combine equation (87) and (92) we have
E [〈∇f(ωt),∆ωt〉]
≤ ηL 2
NK N∑ i=1 K∑ k=1 cpB ,iE [ ‖ωt,i,k − ωt‖2 ] + η(cpB − 1− ∑N i=1 pt,i 2N )E [ ‖∇f(ωt)‖2 ] + η
2
( cpG + 1
N N∑ i=1
(1− pt,i)R2 )
(93)
Then we have
E [f(ωt+1)] ≤ E [f(ωt)] + ηL2
NK N∑ i=1 K∑ k=1 cpB ,iE [ ‖ωt,i,k − ωt‖2 ] + η(cpB − 1− ∑N i=1 pt,i 2N )E [ ‖∇f(ωt)‖2 ] + η
2
( cpG + 1
N N∑ i=1
(1− pt,i)R2 ) + Lη2
N N∑ i=1 (1− pt,i)2R2 + Lη2σ2 2NK (94)
Because we know
E‖ωt,i,k − ωt‖2
≤ 4k2η2l L2cpB ,iE‖ωt,i,k−1 − ωt‖ 2 + 4k2η2l cpB ,i(E [ ‖∇f(ωt)‖2 ] ) + 2k2η2l cpG,i + 2k 2η2l ( t−1∑ τ=1 pτ,i) 2R2 + kη2l σ 2 .
(95)
That is,
E‖ωt,i,k − ωt‖2
≤ k−1∑ r=0 ( 4k2η2l cpB ,i(E [ ‖∇f(ωt)‖2 ] ) + 2k2η2l cpG,i + 2k 2η2l ( t−1∑ τ=1 pτ,i) 2R2 + kη2l σ 2 )( 4k2η2l L 2cpB ,i )r
(96)
≤
( 4k2η2l cpB ,i(E [ ‖∇f(ωt)‖2 ] ) + 2k2η2l cpG,i + 2k 2η2l ( ∑t−1 τ=1 pτ,i) 2R2 + kη2l σ 2 )
1− 4k2η2l L2cpB ,i (97)
Let 8K2η2l cpB ,i ≤ 1, we have,
1
NK N∑ i=1 K∑ k=1 cpB ,iE‖ωt,i,k−1 − ωt‖ 2
≤ 1 N N∑ i=1 cpB ,i
( 4K2η2l cpB ,i(E [ ‖∇f(ωt)‖2 ] ) + 2K2η2l cpG,i + 2K 2η2l ( ∑t−1 τ=1 pτ,i) 2R2 +Kη2l σ 2 )
1− 4K2η2l L2cpB ,i (98)
≤ 1 N N∑ i=1 cpB ,iE [ ‖∇f(ωt)‖2 ] + 1 2 cpG,i + 1 2 ( t−1∑ τ=1 pτ,i) 2R2 + σ2 4K (99)
= cpBE [ ‖∇f(ωt)‖2 ] + 1
2 cpG +
1
2N N∑ i=1 ( t−1∑ τ=1 pτ,i) 2R2 + σ2 4K (100)
Then we have
E [f(ωt+1)] ≤ E [f(ωt)] + η ( (L2 + 1)cpB − 1− ∑N i=1 pt,i 2N ) E [ ‖∇f(ωt)‖2 ] + η
2
( cpG + 1
N N∑ i=1
(1− pt,i)R2 ) + Lη2
N N∑ i=1 (1− pt,i)2R2 + Lη2σ2 2NK
+ ηL2
( 1
2 cpG +
1
2N N∑ i=1 ( t−1∑ τ=1 pτ,i) 2R2 + σ2 4K
) (101)
Then we must to choose the value of pt,i for better convergence. Follow the idea that we want to train a better model when convergent, we choose pt,i that can minimize the constant term, which is by solving
min p
G2 +D2 t∑
τ=1
p2τ,i + ( t−1∑ τ=1 pτ,1) 2R2
s.t. t∑ τ=1 pτ,1 = 1 (102)
We get same results as when the objective function is convex, that is, pτ,i = D 2
tD2+(t−1)R2 for
any τ < t, and pt,i = (t−1)R2+D2 tD2+(t−1)R2 , and min{G 2 + D2 ∑t τ=1 p 2 τ,i + ( ∑t−1 τ=1 pτ,1) 2R2} = G2 +
D2 ( D2+(t−1)R2 tD2+(t−1)R2 ) . Then we simplify the equation by using c0(t), c1(t), and c2(t) to denote the constant terms, we have
E [f(ωt+1)] ≤ E [f(ωt)]− ηc0(t)E [ ‖∇f(ωt)‖2 ] + ηc1(t) + η 2c2(t) (103)
Then we have
1
T T∑ t=1 c0(t)E [ ‖∇f(ωt)‖2 ] ≤ E [f(ω0)]− E [f(ω ∗)] η + η 1 T T∑ t=1 c2(t) + ϕ (104)
Consider c0, because the value of B2 and A can’t be constrained, the algorithm can’t converge for very large A and B. Here we first consider when c0 < 0, and use cm to denote the min c0. Then let η =
√ KN√ TL , we derive the convergence rate as
1
T T∑ t=1 E [ ‖∇f(ωt)‖2 ] = O( L(f0 − f∗)√ TNKcm + 1√ T
(√ KN
L
( R2
R2 +D2
)2 +
σ2√ NK
)
+
√ KN
TL
D4
cm(R2 +D2)2 +
√ KN T √ TL
( D4
(R2 +D2)2
)2 ) (105)
Then we want to analyse when the algorithm won’t converge. When the algorithm won’t converge, that means c0 ≥ 0. Because c0 = (L2 + 1)cpB − 1 − ∑N i=1 pt,i 2N = 1 N ∑N i=1(L 2 + 1)(1 + A2 +
B2 ∑t τ=1 p 2 τ,i)− 1− pt,i 2 . Then the value of A
2, B2, L, p decide if c0 ≥ 0. Notice that in FedAvg, pt,i = 1, and c0,avg = (L2 + 1)(1 + A2 + B2) − 32 , and in CFL, we can setting different p to get better convergence. For example, when B is large, setting pτ,i = 1t , we have c0, = (L 2 + 1)(1 +A2 + B 2 t )− 1− 1 2t . Thus, we draw the conclusion as Then we have following observations: • CFL converge faster than FedAvg by reducing the variance terms. For c0 = 1N ∑N i=1(L 2 +
1)(1 + A2 + B2 ∑t τ=1 p 2 τ,i) − 1 − pt,i 2 , in FedAvg, we have pt,i = 1, then c0,avg = (L2 + 1)(1 + A2 + B2) − 32 . However, in CFL, we can adjust p, such as when setting pτ,i = 1 t , we have c0 = (L 2 + 1)(1 + A2 + B 2 t )− 1− 1 2t , then the variance term reduce from B2 to B 2
t .
• The convergence rate of CFL become better for larger t, since cpB in c0 become smaller for larger t.
• Improve N,K will speed up the convergence by reducing the terms about f0 − f∗ and σ2. However, larger N and K will cause larger information loss and round drift (terms with R and D), thus, it should be a trade off in practice.

heading: C EXPERIMENT DETAILS

heading: C.1 NOISY QUADRATIC MODEL
text: We use the noisy quadratic model introduced in Zhang et al. (2019) to simulate the assumptions we used in the proof. We use the model f(ω) = ωTAω + BTω + C, where ω ∈ Rn is the parameter we want to optimize, and A ∈ Rn×n, A 0, B ∈ Rn, and C ∈ R. We construct A by firstly constructing a diagonal matrix Λ and then constructing A by let A = UTΛU, where U is a unitary matrix. Here we control the eigenvalues of A to control the convexity of model, that is,
µ ≤ λmin(A) ≤ λmax(A) ≤ L. Because Λ and A have same eigenvalues, it’s simple to control the eigenvalues of A by control the eigenvalues of Λ. To simulate Assumption 2, 3, we formulate the gradient noise model by
gt,i(ω) = Aω + B + δi + ξt,i + νt,i,k , (106)
where δi denotes the client drift of client j, ξt,i denotes the round drift of client j on round i, and νt,i,k denotes the noise of gradient of client j on round i, iteration k. All of above drifts and noise are generated from Normal distribution with zero mean and different variance. In practice, to show if the numerical results match our theoretical results, we tried eight settings: large and small L, large and small round drift, and general and strongly convex conditions. For different types of L, we set L = 20 for large L, and L = 5 for small L. For convexity, we set µ = 1 for strongly convex, and µ = 0 for general convex. For different round drift, we set E‖ξt,i‖2 = 100 for big round drift, and E‖ξt,i‖2 = 0.01 for small round drift. Besides, we set fixed variance of δi and νt,i,k for E‖δi‖2 = 0.01, and E‖νt,i,k‖2 = 0.00001. We do the gradient descent by let ωt,i,k+1 = ωt,i,k − ηlgt,i(ωt,i,k), and we use ‖Aω +B‖ as loss because for convex functions, when it reaches the global optimal point, we should have ‖Aω +B‖ = 0, and if it is far away from global optimal, ‖Aω +B‖ will be large. Besides, we show that CFL algorithms can tolerate a larger learning rate here. Table 7 shows the best learning rates for different FL algorithms on noisy quadratic model. In Table 7, we denote small round drift as SRD, big round drift as BRD, small L as SL, large L as LL, strongly convex as SC, and general convex as GC. We show that the best learning rate of CFL is the largest. The difference between CFL methods and other FL baselines becomes large when models are strongly convex or with big round drift. Figure 2 shows the performance of different algorithms, and CFL outperforms other FL baselines significantly in all settings. Besides, the loss curves of CFL are smoother than FL methods, which implies that CFL can reduce the variance of gradients.

heading: C.2 REALISTIC DATASETS

heading: C.2.1 SETUP
text: We consider federated learning an image classifier on split-CIFAR10 and split-CIFAR100 datasets with ResNet18, and split-Fashion-MNIST dataset with a two-layer MLP. The “split” follows the idea introduced in Yurochkin et al. (2019); Hsu et al. (2019); Reddi et al. (2021), where we leverage the Latent Dirichlet Allocation (LDA) to control the distribution drift with parameter α (See Algorithm 4). Larger α denotes smaller drifts here. In our experiments, unless specifically mentioned otherwise all datasets are partitioned to 210 subsets for 7 different clients: all clients are selected and trained for 500 communication rounds, and each client samples one of the corresponding 30 subsets randomly for the local training. Note that unless mentioned otherwise the training strategy here applies to all FL baselines and CFL methods, and we evaluate the performance of models on global test datasets. We carefully tuned the hyper-parameters in all algorithms, and we report the results under the optimal settings after many trials. For CFLRegularization, we set the weight of regularization term for β = 1 on fc layer, and β = 0.1 for last block (layer). For FedProx, we set the weight of proximal term µ = 0.1, and for MimeLite, we set the global momentum weight for γ = 0.01. Besides, for all experiments, we set fixed learning rate lr = 0.01. We also naively examined warm-up tuning strategies but can not observe significant improvement on final results.
Construct local datasets with overlap. Follow the partition methods of disjoint local datasets; we first split the whole dataset to
M × S subsets for S different clients: each client has M disjoint local subsets, and we put these M subsets in sequence. For each client, we use a pointer to point to the start position of the current local dataset. Figure 3 show the case when M = 5: D1−D5 are 5 disjoint local subsets of client i. The pointer point to the start point of a local dataset of the current round and the blue lines bound current subsets. At the beginning of training, pointers belong to each client will point to the beginning of the sequence. At the end of each round, the pointer moves s steps, and if it moves to the end of all the sequence, it will come back to the start point. In practice, the Cifar10 dataset is partitioned to 210 subsets for 7 clients, and set the size of local dataset Sl = 285. Then when we set s = 285, the local datasets are disjoint, which means the overlap is 0%. Otherwise, when set s = 213, the overlap is 25%, and when set s = 142, the overlap is 50%.

heading: C.2.2 APPROXIMATION METHODS
text: Regularization Methods. We use Taylor Extension to approximate the objective functions of previous rounds, that is,
f̃(ω) = f(ω̂) +∇f(ω̂)T (ω − ω̂) + 1 2 (ω − ω̂)T∇2f(ω̂)(ω − ω̂) , (107)
where ω̂ are the parameters of previous rounds. Then the gradient of f̃(ω) is,
∇f̃(ω) = ∇f(ω̂) +∇2f(ω̂)(ω − ω̂) . (108)
Having this, we can approximate the gradients of objective functions of previous rounds. The problem is how to approximate ∇2f(ω̂). Here we use two kinds of methods to calculate the Hessian matrices. The first is to use the Fisher Information Matrix as introduced in EWC (Kirkpatrick et al., 2017). The Fisher Information Matrix is equal to the diagonal Hessian matrix when using cross entropy loss functions. The Fisher Information Matrix can be calculated by,
Fij = [∇f(ω̂)]2ij , (109)
where Fij are the entries of Fisher Information Matrix. Another method is to calculate the diagonal Hessian matrix. We use the PyHessian package (Yao et al., 2020) in this experiment. In addition, if the parameters or the Hessian matrix changes too much, the performance of this method is constrained. To formulate this problem, assume
∥∥∇2f(ω)∥∥ ≤ for some arbitrary , we have ‖∆t,i(ω)‖ ≤ ‖ω − ω̂‖2 .
The corresponding proof refers to B.3. In each round, the server will collect Hessian matrices from clients, and store them in a buffer. Then at the beginning of next round, server combine send latest 40 Hessian matrices, gradients, and parameters, and send them to chosen clients. Each clients use these to calculate regularization terms. In practice, we only add regularization terms to the top layers (last block and fc layer of ResNet18). This is based on the assumption that top layers contain more personal information while bottom layers contain more general information. We verified that this strategy perform better than adding regularization terms to all layers in experiments.
Generation Methods. We use MCMC to generate samples in each round. In practice, we initialize x from uniform distribution, and update x by,
xk = xk−1 − η∇xE(xk−1) + ω , (110)
where E(xk − 1) is the function that can measure the distance between xk−1 and the real local distribution. ω ∼ N (0, σ). In practice, we generate 50-100 samples of each local dataset and add them to the current local datasets for training. However, because of the low quality of the generated data, the improvement is limited. Besides, the generated data will pollute the batch normalization(BN) layer, and we should use real data to refresh BN layer at the end of each round.
Algorithm 3 iCaRL Construct Core Set Require: Image set X = {x1,x2,x3, ...,xn} of class y,m: target number of samples, φ : X → Rd:
current feature function 1: µ← 1n ∑ x∈X φ(x) 2: for k = 1, ...,m do 3: pk ← arg minx∈X
∥∥∥µ− 1k (φ(x) +∑k−1j=1 φ(pi))∥∥∥ 4: P ← (p1, p2, ..., pm)
Core Set Methods. Another simple yet effective treatment in CL lines in the category of Exemplar Replay (Rebuffi et al., 2017; Castro et al., 2018). This approach stores past core-set samples (a.k.a. exemplars) selectively and periodically, and replays them together with the current local datasets. We tried two sample methods. First is so-called Naive method, in which the samples are uniformly chosen from local datasets. Except of naive select core sets, we also tried another core set sampling method introduced in iCaRL (Rebuffi et al., 2017). See Algorithm 3 for details. In practice, we save 100 figures of each local dataset and combine them with the current local datasets. Saving core sets perform best compared with these three approximation methods; however, only valid when the number of clients is limited.

heading: C.2.3 ADDITIONAL EXPERIMENTS
text: Applicability of different algorithms. We list the applicability of different algorithms under various time-varying scenarios in Table 8.
Convergence curves for different settings. Figure 4 show convergence curves of CFL and FedAvg on different datasets. The settings are the same as results in Table 3. Models are trained on partitioned datasets with α = 0.1, and all datasets are partitioned to 210 subsets for 7 clients. To show the difference between different algorithms more clearly, all curves are smoothed by a 1D-Mean-Filter. Results show CFL can converge to a better optimum compare with FedAvg.
Investigating resistance of CFL to time-evolving scenarios. Figure 6 shows the loss curve of CFL-Regularization and FedAvg on different datasets. Models are trained on partitioned datasets with α = 0.1, and all datasets are partitioned to 210 subsets for 7 clients. The first column shows the loss curve of the first 300 rounds, and the second column shows the loss of some chosen details. Because of the non-iidness of local datasets, the loss will suddenly rise. Notice that CFL-Regularization has an apparent mitigation effect on this situation.
Difference between training and test loss. Figure 5 show the loss on global test data and past appeared training data. We evaluate the model with stateful clients, set α = 0.2, and use FedAvg algorithm. We show that there is no significant difference between loss value on global test data and past appeared training data.
C.3 ALGORITHMS
Algorithm 4 Data splitting Require: S: a list of datasets split by labels, M : the number of clients, N : the size of local datasets,
α: the Dirichlet distribution parameter Ensure: D: split datasets
1: D ← [] 2: G← [0, 1, 2, ..., len(S)] 3: for m = 1, 2, ...,M do 4: p = [p1, p2, ..., plen(S)], where pt,i denotes the fraction of class i in total dataset. 5: θ ← Dirichlet(α, p) 6: Dm ← ∅ 7: while len(Dm) < N do 8: i← multinomial(θ, 1) 9: y ← G[i]
10: data← uniform(S[y]) 11: Dm ← Dm ∪ {data} 12: S[y]← S[y]/data 13: if len(S[y]) == 0 then 14: G← G/y 15: θ ← renormalize(θ, i) 16: D.append(Dm)
Algorithm 5 renormalize Require: θ: weights for different classes, i: the class that should be deleted Ensure: θ: renormalized weights
1: for j = 1, 2, ..., len(θ), j 6= i do 2: θ[j]← θ[j]/sum(theta/theta[i])
Algorithm 6 SplitdataMain Require: S: total dataset split by class, T : rounds, K, N , α, β Ensure: Dfinal: split dataset
1: D ← splitData(S,K,N, α) 2: Dfinal ← [] 3: for i = 1, 2, ...,K do 4: Si ← splitByClass(D[i]) 5: Nlocal ← len(Dm)/T 6: Di ← splitData(Si, cluster_num,Nlocal, β) 7: Dfinal ← Dfinal ∪Di

Review summaries:
This paper introduces the Continual Federated Learning framework that allows capturing time-evolving heterogeneity of FL. The authors introduce a new formulation of the problem and propose a carefully chosen approximation to work with the new problem. Also, the authors provide theoretical analysis for strongly convex and general convex settings. At the end of the paper, they provide experimental results for deep learning models.

This paper proposes to study time evolving heterogeneous data, and proposes Continual Federated Learning (CFL) to address this problem. Their analysis achieves this by introducing time-drift to capture data heterogeneity across time. Convergence results are presented followed by numerical results on time-varying and heterogeneous settings.  

The paper presents continual federated learning (CFL) to address the issue that data at clients in FL may vary over time. The main objective of CFL is to optimize the time-aggregated objective across multiple clients. While historical objective functions are usually not available, the paper considers a surrogate objective that approximates the original historical objective. A theoretical analysis is presented that takes into account the approximation error (referred to as information loss in the paper) and the time drift in local objective functions. Experiments were also conducted that show core set methods to perform well.

The authors study Federated Learning for time-evolving data. In particular, they study gradient based methods for learning parameter vectors and characterize their performance in terms of the approximation quality of a noisy gradient oracle. Numerical experiments compare the performance of the proposed method with existing FL methods.