Towards Federated Learning on Time-Evolving Heterogeneous Data
Authors: Yongxin Guo
Tao Lin
Xiaoying Tang
Venue: ICLR 2022 Submitted (2022)
Keywords: Federated Learning
Continual Learning
Convergence Analysis

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-evolving 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-evolving 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-evolving 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.

Under review as a conference paper at ICLR 2022
TOWARDS FEDERATED LEARNING ON TIME- EVOLVING HETEROGENEOUS DATA
Anonymous authors Paper under double-blind review
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 chal- lenging in practice due to the diversity and heterogeneity of the learning system. Despite recent research efforts improving the optimization of heterogeneous data, the impact of time-varying heterogencous data in real-worke scenarios, such changing client data intermittent clients joining or leaving during training, has not been well studied. In this work, we propose Continual Federated Learning (CFL), flexible framework, to capture the varying heterogeneity of FL.. CFL covers complex and realistic scenarios in previous FL formulations- extracting the information of past local datasets and approximating the local objective functions. Theoretically, we demonstrate that CFL methods achieve faster convergence rate than FedAvg in time-vare varring 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 CFI. methods significantly outperform the other SOTA FL baselines.
are challenging to evaluate
INTRODUCTION
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 ss updates and resulting in slow and unstable convergence (Karimireddy
al. 2020b). To address this issue, 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 al. (0200) or adopts variance reduction methods (Karimireddy et al. 2020b al Das et al. 2020 Haddadpour et al. (021). However, the FL. formulation in these approaches a always assumes 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 marying 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 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-whidh has been extensively utilized recently in Karimireddy et al.) (2020b); Khaled et al. (2020);[] Li et al. (2020b) include both client drift and time drift. This allows us quantify the difference between local client objective function and global objective function for the considered time-var 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 approximation quality. The rate of FedAvg obtained from

---

Under review as a conference paper at ICLR 2022
our framework is consistent with previous work, while a similarly simplified rate on Continual Learn- ing (CL) (French) 1999 Kirkpatrick et al. (217)) for the convex and strongly convex cases is novel. Finally, in extensive empirical results, demonstrate that CFL methods-stemmeed from the CFL framework with different approximation cchniques-Significanee outperform the SOTA FL. competi- tors 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 time- varying 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-conve 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.
2 RELATED WORK
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 system
heterogeneity (Li et al, 2018: Wang et al. 2020 Mitra et al.) 202T; Diao et al.] [021) and
statistical/objeetivee heterogeneity (Li et 2018)) Wang et al. [2020] Mitra et al. 202 Lin et al.
2020a Karimireddy et al. (2020bla 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
-iimilar
Dinh et al. 2020 Li et al. [02T] 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.
202T) 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 (2000): Patel & Dieuleveut 2019); Khaled et al. (2020): Woodworth et al. (202bb) For the analysis of heterogeneous data, Li al. (202bb) first give the convergence rate of FedAvg on non-iid datasets with random selection, assuming that the client optimum are e-close. Woodworth al. (2020a): Khaled al. (220) give tighter convergence rates under the assumption of bounded gradient drift. All above works give O (1/T) convergence rate for convex local objective functions. More recently, Karimireddy et al. (2020b); Koloskova et al. (200)) give the convergence analysis of local SGD for non-convex objective functions under bounded gradient noise assumptions, and obtain (1/VT)) convergence rate. Our theoretical analysis framework covers more challenging time- varying data heterogeneity in FL, which has not been considered the community out-our rate can be simplified to the standard FL scenario, matching the tight analysis in Karimireddy et al. (020bb..
Continual Learning. Continual learning, also known as incremental learning or lifelong learn- ing, 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 Rebufii 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.
2

---

Under review as a conference paper at ICLR 2022
Despite the empirical success, the theoretical analysis of is limited: only very recent preprint (in 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. (007)) regularization with FedAvg, and empirically shows faster convergence. FedWeIT (Yoon et al. [222]) extends the regularization idea, with focus on selective inter-client knowledge transfer for task-adaptive parameters. a very recent parallel (and empirical) work, CDA-FedAvg (Casado et al., 202T uses locally maintained long-term data samples, with asynchronous communication; however, this design choice lacks sufficient numerical results 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 orthogonal the neural architecture manipulation idea in FedWeIT.
CONTINUAL FEDERATED LEARNING FRAMEWORK
3.1 FORMULATION
Conventional FL Formulation. optimization problem as below:
The standard FL typically considers a sum-structured distributed
f" = wiR [[w) = E
(1)
where the objective function f(w): : Rd - R is the weighted sum of the local objective functions fi(w)) := ED, [W)] of N nodes/clients, and p; the weight of client i.
In practice, may be infeasible to select all clients each round, especially for cross-device setup (McMahan et al. 2017 Kairouz et al. 2019b. 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 Wt,i, wr,ik-1 m ( ( + (t,,, with local step-size 7) and gradient noise 1- The selected clients then communicate the updates
AWi, = Wt,iK W, with the server for the model aggregation: W Wi 22 Σ Awi.
Continual FL Formulation. Despite its wide usage. the standard FL formulation given in Equation ① 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" = minwErd [M()) = E Eies, Pr.Jes(w)].
(CFL)
where (w) represents the local objective function of client i at time t. S, is subset of clients sampled from all clients set Ω where |S.] = S. For the tire-narying scenarios, client i could have different local objective functions [e,s(w) due to the changing local datasets on different L.
3.2 APPROXIMATION OF CFL
The challenge of addressing (CLL) formulation stems from the stateless nature of the local datasets, which include unpredictable future datasets, 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. 20177) 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:
minwers [f(w = Eiss, (w)) + Σラ Eies, Pr..f..((w)
where f.,(w) denotes the approximated local objective function of client i at time t. In practice. different approximation methods can be used to calculate (w,)(w), 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 CFL methods are 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 Take note that in most cases, the previous local object functions cannot be properly approximated. Due to the fact that such approximation impairs optimization, define the information loss below.
3

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Approximated CFL Framework
Require: initial weights wo. global learning rate T/g, local learning rate yj, number of training rounds T Ensure: trained weights Wr
I: for round = ,....; do
2:
communicate to the chosen clients.
3: for client à E St in parallel do
4:
initialize local model Wt.c. = WL.
5:
for k 1,..., do
6:
(ral(Waak-1) Pe, (w.. Eis Pr, Pr..Vrralaran Vrallardd)) Menk We.ck + Wiick- ( communicate Awi. < WoiiK Wr.
7:
8:
9:
Awo <- 1i Dies, Awe..
10:
WH41 Wi + Awr.
Definition 3.1 (Information Loss). We define the information loss as the difference between the approximated local objective function fe, and the real local objective function fe,(w), i.e.
(w)( (i,((w) [i,((w))
(3)
In practice, we use || || (w)]l, 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 TaareeTii in Section p.2
3.3 GRADIENT NOISE MODEL
To analyze Equation (2) and Algorithm inn-eepth, we propose the Gradient Noise Model (Equation (5) to capture the dynamics 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(w), the gradient with stochastic noise can be defined as f(w = g(w) + v,, where g(w) is the stochastic gradient, and v is 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 capture the distribution drift between local objective function and global objective function:
f((w) = f((w) 6,
where 8, 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 at time t. Considering the distribution drift in the dimension of client and time, further modify the gradient noise model in FL as,
v V((w) V(,((w) + Sr, E..i.
(5)
Note that we extend the gradient noise to two terms: 6,,5 and Et,,. òτ, is a time independent (of t), zero-mean random variable that measures the drift of client i. The zero-mean E,,, measures the drift of client i at time t: this value of client may change over time f, due to the time-varying local datasets. Remark 3.2. We assume different &.,, 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
3.4 ASSUMPTIONS
To ease the theoretical analysis of (CFL) framework, the following widely used assumptions. Assumption (Smoothness and convexity). Assume local objective functions fe,i(w) are L-smooth and j-convex, i.e. & ||w] w2 < (w.)(w) (e.i(wz) (V fe,a (W2), w2) S 4/2 ||W| we 1| widely used corollary that a function ft, is both L-smooth and μ-convex, then it satisfies ZI Jr, - V1 S fe,,(x)
fy) [x,,
y). and I.
Assumption (Bounded noise in stochastic gradient). Let gt, (w) V.Lin(w) + Vtiik, where Vtiik is the stochastic noise of client on round at k-th local update step. We assume that
[[|[w] 0. and |||| [ <002
4

---

Under review as a conference paper at ICLR 2022
Table 1: Number of communication rounds required to reach + yp accuracy for μ strongly convex and general convex functions under vineingyyngg FL scenarios (Assumption D We can recover the rates in conventional FL setups by setting D = 0 and A = O. Note that yp = 0 in FedAvg. Our convergence rate of FodAvg matches the results in Karimrreddy et al. 2020b). Our SGD rate of CL on strongly-convex case is novel.
Algorithm
Strongly Convex
General Conves
SGD
FedAve
Li ct
2020b
2
DD uif PEGAD
Khaled
mn 129108409)
Karimireddy at
20200
G&D
Woodworlh al.
2020a
10+ Diren
Ours
GR
GLD
PC
NIVE
CL
Yin et ol. 20206
(GD)
Ours
1=.4
Ours
uNKe
Cpp + B2 + A3. CA
D2 R2
CB
D2y+
D
N is the number of chosen clients in each round, and
K is the number of local iterations.
Assumption
D and 2 are common assumptions in FL (Krrimiredy et al. 2020b; Li ct al., 2020b).
Considering 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(w) = ((,(())+ 6,, Er. where
o,,, measures client drift and Ét, indicates the time drift of (t, i}. We assume E 18 w/ = 0, B B(EW]
O, and thus E || | GG + B I(W)] and E
||E1|
W
I D2 V
We can derive the corollary from Assumption 3 that IE
[|E|] w
< GC + A2 V (w))
which can simplified to E |||||2 [
< D2 A
V [(w)], by assuming A² = B2 D
A²
Assumption assumes the bounded E
||.) [w)]
and E [|E|] | in CFL framework, which is
equivalent to the widely used (G, B) gradient drift assumption! Gower al. 2019 Karimireddy
et al. 2020b on the bounded E [f(w)))]] We prove this claim in Appendix B.1
Assumption (Bounded information loss). We assume the information loss (,,((w)
(w) can be bounded
by an arbitrary non-negative value R, i.e. ||wr,(W)]|| < R.
Remark 3.3. The exact information loss in Assumption Campptiioommmaa May be intractable for some appreximation
methods. In Lemma B.3 of Appendix B.3
we showcase tight analysis of information loss for Taylor
extension based regularization methods.
4 THEORETICAL RESULTS
In this section, we analyze the theoretical performance of Algorithm Iunder Assumption 4 We prove that CFL. methods converges faster than FedAvg, despite that the term (refer to yP 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 I we summarize the convergence rate of different algorithms? The proof details refer to Appendix B. 3. and Appendix B.5
4.1
CONVERGENCE RATE OF CFL METHODS
We start our analysis of Algorithm I from the one round progress of CFL methods in the Theorem stated below.
'The (G, B) gradient drift: E. [[ < G [[T]( + B², where G² 2 and B² 2 0. TT 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.
5

---

Under review as a conference paper at ICLR 2022
Theorem 4.1 (One round Progress of CFL methods). When (w)) satisfy Assumption 7 let v K Ng we have the one round progress of CFL methods as,
and
s(wi) - -[(w- - -
107 DE - w w01
1 BBllwL - w 11 + cir + eall tpL,
(6)
"
A2
A1
where C1 = 20p +
NK +eR C2 =
n²
Lepc 3ng
kog
Lo²
+
Leg 3m, Cpc - # En G + eR =
N Ei (Et=1 Pr,a) RRP. (pt is a constant satisfying (pt = ( E Pt, R Wo - w'll)
N is the number of chosen clients in each round, and K is the number of local ierations.
Theorem shows the round progress of CFL methods. The A1 part of (6) indicates the linear convergence rate, while the A part illustrates the worsened convergence induced by gradient noise and information loss. (e constant related to the information loss that causes the drift of the optimum. When the upper limit on information loss R exceeds O, we cannot reach the exact optimum due to the approximation error: the iterates instead reach the neighborhood of + 4o, where
>T qeift for some sequence q:- We show in Section S that in practice, the approximation Σi= qe methods with small information loss converge much better than methods with larger information loss.
Theorem 4.2 (Convergence rate of CFL methods). Assume (Sta(w)} satisfy Assumption the output of Algorithm [ has expected error smaller than e + 9, for Bl = 1, 1
33+4(1+ 422) /40+ BB+ PT.i (12+(t- (T < t), and Pt, = ( on round t.
D²
(t-1)R²+D²
6KL When (f(r(w)) are p-strongly convex functions, we have,
T = O Len +
2 BNKE
and when (fr((W)} are general convex functions (μ 0), we have
T 0
coF+/eeF++
VEDEE
2F NK2
+
+
c0
(8)
and when {fe,(w)} are non-convex, setting 17 Kngn converge to 6, we have
VKN TTL
and when 1 T El E [[VF(W)))
(Jo f.)²
1
v
KKeC
VKNeR CmeT.
(KN)+cH
T=0
+
(9)
NKe2
L
VNK
(cL)
where co = =1+
B², CA G2
D²R R4
CB
D
CC
La Lea CD og
Leg
og
R² H + CR2 [R Dayz Cm is a constant related to A, B and R, and F = I|wo - w011 N is the number of chosen clients in each round, and K is the number of local iterations. We elaborate the choice of pt. in Appendix B.4.3.
D
CRI
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. (020a) only gives the convergence rate of GD for regularization based CL methods on general convex case, under the constraint of R O.
Remark 4.4. For stateless FL scenarios (clients only appear once during training). we can derive fighter bounds than that of Theorem 4.2 Applying Lemmal B.2 to the considered stateless scenario, CA and en in Theorem 4.2 become cN
(G* GD and ca D where pe
(D2+
DE
eat
Cg' and CA +
cB pe
corresponds to the rate of strongly convex setting in Theorem 4.2
4.2 CONVERGENCE RATE OF FEDAVG UNDER TIME- VARYING SCENARIOS
To show the faster convergence of CFL methods than FedAvg, provide the convergence rate of FedAvg under time-varying scenarios. Results are derived from Theorem 4.1 by setting Pt, = 1. Note that when Pt. 1, we yo O.

---

Under review as a conference paper at ICLR 2022
Theorem 4.5 (Convergence rate of FedAvg under time- varying scenarios). Assume {fr,((w)} satisfy the ouiput of FedAvg has expected error smaller than e, for fg 1 and mn S
Assumption 7H
3344(14 + ACL 42)
When {fr,(w)} are p-strongly convex functions. we have,
T= T= (La
o² pNKe
+
EA
(10)
and when [Jts(wi] are general convex functions (11 = 0), we have
T 0 ( co +
o'r NKe.
+ saf + P2
(11)
where co = =1 A2 B², CA = + D2, cc
La² + LCA, and F F= 1w0 - wnIl N the 1
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.; = 1, and we can show by proof (in Appendix B.4 that it is equivalent to setting the upper bound of information loss R + oc (we can also observe this result by setting (t-1)R=+D* R - DO in Pt,s = +D2 1) in Theorem 4.2 The upper bound R is linearly correlated to D²R2²
gradient noise, where Cλ = G2 + R++D2 in Theorem 4.2 increases to CA = G2 +D² in Theorem 4.5
5 EXPERIMENTS
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 [..I) demonstrate that CFL methods converge much faster than baselines like FedAvg and FedProx, with a smoother convergence curve. These findings are corroborate Remark[4.6Jabben 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.
5.1 SETUP
Time-varying heterogeneous local datasets. We consider federated learn image classifier us- ing ResNet18 on Split-CIFAR10 and split-CIFARI 100 datasets, as well as a two layer MLP on the Spiit-aahhonnMNNIST dataset. The "split" follows the idea introduced in Yurochkin al. (2019): Hsu et al. (2019): Reddi et al. (202T), where we leverage the Latent Dirichlet Allocation (LDA) ) to control the distribution drift with parameter a (See Algorithm 4). Larger a indicates smaller drifts.
Unless specifically mentioned otherwise our studies use the following protocol. All datasets are parti- tioned 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 datasef" We carefully tune the pprerpparmettrs 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. [0117] Castro et al., 20188). This method selects and regularly saves previous core-set samples (a.k.a. exemplars), and replays them with the current local datasets.
"The training loss/accuracy on CFF.) formulation are closely aligned with that of global test data, as shown in Figure of Appendix C.2.3 We here only present the global test results for the common interests in practice.
7

---

Under review as a conference paper at ICLR 2022
Table 2: Top-1 accuracy for different choices of approximation techniques in CFL. We train 8 on splitCCIARRIO dataset (w/ a = 0.2) for 300 communication rounds, and the dataset is partitioned to 300 subsets for 10 different clients. All examined algorithms use FedAvg as the backbone.
Algorithon
Regulatizaion Methods
Methods
Generative Methods
PyHlesian
Fisher Information Matris
Noive (Small Set)
Naive (1 (large Set)
ICaRI. (Small Set)
iCaRI. (1 aege Set)
MCMC
Accuracy 74 a 0.66
76.70 & 0.39
77.84 = 1.06 78.90 # 0.09 70.97 & 0.36
77.00 a 0.00 70.18 = ILD8
Table 3: Top-1 accuracy of various CFL methods on diverse datasets for training ResNet18 with 500 communication rounds. In order to observe a noticeable performance difference on Fashion-MNIST, we use a 0.1 instead. All examined algorithms use FedAvg as the backhone. Both CFL-Regularization and CeL-Regularization- Full are regularization based method, and the difference lies on where the regularization is applied: the full version applies regularization to all layers while the other only considers the top layers. R, indicates the accuracy of CFL- LEL--egularizztton, while Ry denotes the accuracy of FedAvg.
Algorihm
Accuncy on Fishion-NNIST(S (36)
Accumcy on CIFARIO (%0
Accuracy on (IP)
FedArg
86, 75 0.14
70.51 0.19
49:97 0.19
Regulatization
09 53.17 0.08 14.84 1 0.12
CR CFI-CCoreSSt
WX.32 0.12
N1.48
CFL CFL Repulauruttiinonn Full
77.37 0.63
33.09
1.45
Metric
Inprovementt on Fashion-MNIST (%) Improvenenn on CIFARIO (%)
Improvement on (IPAR100(5)
Absulute (R. - R2)
0.27
0.35
0.72
(
Ry)/
0.31
0.50
1,44
Generative methods. Maintaining core set for each client may become impractical when learn- ing 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.
5.2 RESULTS
Comments on different CFL approximation techniques. In Table 2 examine the perfor- mance of several approximation techniques using the split-CIFARII 10 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 f 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 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 sampling for CFL-Core-Set method, and use PyHessian for CFL FFL-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 experimentally studies the impacts of various information approximation techniques in CFL methods as discussed in Section 35.--and and compares them with the backbone algorithm of CFL methods, i.c. 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 (in Appendix (C2.3) that CFL methods offer better resistance 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. [02T]:: 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 approximatio 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 loss can be changed
'The algorithmic details the sampling method iCaRL refer to Algorithm in Appendix C.2.2
5 We estimate the information loss by using 18 E. Ei= [|Ar,(w)]] where Ar,((w) is defined in Equation B. S is the number of clients chosen in each round, and is the number of communication rounds.
8

---

Under review as a conference paper at ICLR 2022
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 com- parison between CFL methods and FedAvg on various datasets (Table 3). in Table verify the efficacy of methods over other strong FL baselines, on split-CIFAR 10 dataset. We also examine MimeLite (Karimireddy et al. 2020a), method suggested for stateless FL scenarios. Note that we exclude the results illustration for methods like SCAFFOLD (Karimiredyy et al. 2020b) and Ditto (Li et al. 2021], due to their infeasibility to be applied in our continual scenarios We further relax the difficulty of federated continual learning, from challenging non- overlapping 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 illustratee the performance of FL baselines and CFL methods, under different degrees of overlapping (the construction details refers to Appendix C.2.Tp: 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 lime-vayying FL datasets to gain a better understanding.
8
300
126 149
185
Figure 1: Information loss (left y-axis) and accuracy (right y-axis) for training ResNet18 on split-CIFARIO with different core set sizes (x-axis) and a = 0.2.
Table 4: Comparing the SOTA FL baselines with several CFL methods, for training ResNet18 on split-
CIFARIO dataset with different degrees of con-iid-ness a (and with total 500 communication rounds).
FL baselines
CFL methods
Accuracy
FedAvg
FedProx
MimeLite
CFL-Cure Set
CFL CFL-Regulatzzttion
CFL ReL-lagularization + FedProx
a
0.1
70.51 0.19
71.57 + 0.17
60.55 + 0.36
81.48 0.224
70.86 + 0.31
71.50 + 0.07
0.2
77.98
= 0.36
78.
0.22
78.65 0.26
0.11
78.76 0.26
79.01 = 0.01
Table 5: Benchmarking FL. baselines and CFL. methods different degrees of local dataset overlapping. for training ResNet18 split- split-CIFARIO dataset. The overlap reduces the degree of non-id-ness. In order observe noticeable performance difference, we use a larger data distribution gap between rounds (i.e. a = 0.1).
FL basclines
CFL methods
Overlap
FedAvg
Mimel
Core-Core-Set
CFI Cel-Regulaiizztion
0%
80.66 + 0.40
80.78 = 0.07
84.87 + 0.11
81.27 0.38
25%
80.16 0.01
0.11
84.66 0.11
80.67 0.27
50%
79.97 + 0.23
80.35 0
84.59
0.07
80.91 + 0.25
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.c. 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/6evaluater the bhove-mentiones scenario. We find that EFL-Regulaiizztion methods consis- tently outprforrm alternative FL baselines, similar to the observations in Table However, due to the nature of stateless under the privacy concern, the advancements of core set method CFL algorithm cannot be seen in this scenario. Additionally, we discuss the applicability of different algorithms in variety of time-varying scenarios in Table g of Appendix C.2.3
Table 6: Learning with stateless clients, regarding training ResNet18 on SpliI-CIFARIO with a = 0.2, All examined algorithms use FedAvg as the backbone. The details w.r.t. Reu-laeuuaiizatioon refer to Appendix C.2.2
FL baselines
CFL methods
Algorithm
FedAvg
MimeLite
FedProx
CFL Regulazaaii
CFL- ReL-lagulaiization + FedPrrx
Accuracy
78.07 + 0.06
78.47 + 0.19
78. 48 1 0.05
79.07 1: 0.25
79.32 + 0.07
We also naively adapted and examined these methods, hut we cannot observe significant performance gains.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Thang D Bui, Cuong V Nguyen, Siddharth Swaroop, and Richard E Turner. Partitioned variational inference: A unified framework encompassing federated and continual learning. arXiv preprint arXiv:1811.11206 2018.
Fernando E. Casado, Dylan Lema, Marcos F. Criado, Roberto Iglesias, Carlos V. Regueiro, and Senén Barro. Concept drift detection and adaptation for federated and continual learning. CoRR, abs/2105. 13309, 2021. URL
Francisco M Castro, Manuel Marin-Jiménez, Nicolás Guil, Cordelia Schmid, and Karteek Alahari. End-to-end incremental learning. In Proceedings of the European conference on computer vision (ECCV), pp. 233-248, 2018.
Hong-You You Chen and Wei-Lun Chao. On bridging generic and personalized federated learning. arXiv preprint 1XXv:2207.000775 2021.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared represen- tations for personalized federated learning. In arXiv preprint 172i022002.07078, 2021.
Rudrajit Das, Anish Acharya, Abolfazl Hashemi, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topcu. Faster non-convex federated learning via global and local momentum. arXiv preprint 20XI::2012.04061, 2020.
Enmao Diao, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication efficient feder- ated learning for heterogeneouss clients. In International Conference Learning Representations, 2021. URL httppss://ppperreeeeeee nwt w d=TNkPBSYFKKG
Canh T Dinh, Nguyen H Tran, and Tuan Dung Nguyen. Personalized federated learning with moreau envelopes. In Advances in Neural Information Processing Systems, 2020.
Robert M French. Catastrophic forgetting in connectionist networks. Trends in cognitive sciences, (4):128-135, 1999.
lan Goodfellow, Jean Pouget-Abadie. Mchdi Mirza, Bing Xu. David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks, 2014.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International Conference Machine Learning, pp. 5200-5209, PMLR, 2019.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In International Conference on Artificial Intelligence and Statistics, pp. 2350-2355 PMLR, 2021.
Filip Hanzely and Peter Richtárik. Federated learning of a mixture of global and local models. arXiv preprint arXiv:2002.055/6 2020.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint
2019.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. arXiv preprint arXiv: 1911v:9112.04977 2019.
Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.03600 2020a.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-5143. PMLR, 2020b.
10

---

Under review as a conference paper at ICLR 2022
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519-4523 PMLR, 2020.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei Rusu, Kieran Milan, John Quan, Tiago Ramalho. Agnieszka Grabska- Barwinska, et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114 (13):3521-3526, 2017.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pp. 5381-5393. PMLR, 2020.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. arXiv preprinl arXiv: arXiv:/812.066 18/2.6/ 2018.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resouree allocation in federated learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020a. URL https::
net/
Forum?1d-Byexxll.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pp. 6357-6368. PMLR, 2021.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2020b. URL
https: /sttp:://openreveew hwtp:eetttoooteeeee HUd-HUXA
Zhizhong Li and Derek Hoiem. Learning without forgetting. IEEE transactions on pattern analysis
and machine intelligence, 40(12):2935-2947, 2017.
Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. In Advances in Neural Information Processing Systems, 2020a.
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local sgd. In International Conference on Learning Representations, 2020b. URI. https
//openreview
Mi Luo, Fei Chen, Dapeng Hu, Yifan Zhang, Jian Liang, and Jiashi Feng. No fear of heterogeneity: Classifier calibration for federated learning with non-iid data. arXiv preprint arXiv:2106. 05001, 2021.
Davide Maltoni and Vincenzo Lomonaco. Continuous learning single-ineremmenal-tskk scenarios. Neural Networks, 116:56-73, 73, 2019.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communicaionn-fftiienn learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR. 2017.
Aritra Mitra, Rayana Jaafar, George Pappas, and Hamed Hassani. Achieving linear convergence in federated learning under objective and systems heterogeneity. arXiv preprint 2rXiv:2102.0700 2021.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 4615 PMLR, 2019. URL http l/proceedimg ngs. ml press////// / v97 10977/ooh mohr 9a html
Aditya Nori, Chung Kil Hur, Sriram Rajamani, and Selva Samuel. R2: An efficient meme sampler for probabilistic programs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
11

---

Under review as a conference paper at ICLR 2022
Kumar Kshitij Patel and Aymeric Dieuleveut. Communication trade-offs for synchronized distributed sgd with large step size. In Advances Neural Information Processing Systems, 2019.
Sylvestre-Alvis Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert. icarl: Incremental classifier and representation learning. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 2001-2010, 2017.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný. Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2021. TtI..ttts:: http:///////.e.eee.e///o ne. forrm?
1d-LkFG31B1305
Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaie. Robust federated learning: The case of affine distribution shifts. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiae Lin (eds.), Advances in Neural Information Pro- cessing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020. URL
neurnnng.....euseeee neurips. CC/ httmmtml
Andrei Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprint arXiv: (oop::6066.47777 2016.
Claude Sammut and Geoffrey I. Webb (eds.). Neuro-Dynamte Programming, pp. 716-716. Springer US, Boston, MA, 2010. ISBN -78-0-387-30164-8 doi: 10. fittss://dof org. 1007
5888. URL
Neta Shoham, Tomer Avidor, Aviv Keren, Nadav Israel, Daniel Benditkis, Liron Mor- Yosef, and Itai Zeitak. Overcoming forgetting federated learning on non-iid data. CoRR, abs/1910.07796, 2019.
URL httt:://axxiv.oo httpg///ab//11.0000011
Sebastian Stich. Local SGD converges fast and communicates little. In International Confer- ence on Learning Representations, 2019. URL http::::///oeeeee..www hwtp://wwwwweettnnnn/eee
S1c2JnRcFX
Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed updates. Journal of Machine Learning Research, 21:1-36, 2020.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. arXiv preprint arXiv:2007.00 07481, 2020.
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local sgd for heterogeneous distributed learning. In NeurlPS 2020 T0e00-TTiityyfoooe Thirty-fourth Conference on Neural Information Processing Systems, 2020a.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference Machine Learning, pp. 10334-10343. PMLR, 2020b.
Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W. Mahoney. Pyhessian: Neural networks through the lens of the hessian. Xintao Wu, Chris Jermaine, Li Xiong, Xiaohua Hu, Olivera Kotevska, Siyuan Lu, Weija Xu, Srinivas Aluru, Chengxiang Zhai, Eyhab Al-Masri,, Zhiyuan Chen, and Jeff Saltz (eds.), ), IEEE International Conference on Big Data, Big Data 2020, Atlanta, GA, USA, December 10-13, 2020, pp. 581-5901 IEEE, 2020. doi: 10. 2020. 9378171
URL wttpthttt///t. / httpd/oi..oggg///oo wttp://///...../.ppppo.o.....o/.
Dong Yin, Mehrdad Farajtabar, and Ang Li. SOLA: continual learning with second-order loss approximation. CoRR, abs/2006. 10974, 2020a. URL http::ttt///tt ://ariiv// wwt.oor//aooo. abs 2abb/200 abs/2006 2006 10974
12

---

Under review as a conference paper at ICLR 2022
Dong Yin, Mehrdad Farajtabar, Ang Li, Nir Levine, and Alex Mott. Optimization and generaliza- tion of regularization based continual learning: a loss approximation viewpoint. arXiv preprint arXiv:2006. 10974, 2020b.
Jachong Yoon, Wonyong Jeong, Giwoong Lee, Eunho Yang, and Sung Ju Hwang. Federated continual learning with weighted inter-client transfer. In International Conference on Machine Learning, pp.
12073-12086. PMLR, 2021.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. In International Conference on Machine Learning, pp. 7252-7261. PMLR, 2019.
Friedemann Zenke, Ben Poole, and Surya Ganguli. Continual learning through synaptic intelligence. In International Conference Machine Learning, pp. 3987-3995 PMLR, 2017.
Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George E Dahl, Christo- pher Shallue, and Roger Grosse. Which algorithmic choices matter at which batch sizes? insights from noisy quadratic model. In Advances Neural Information Processing Systems, 2019.
Martin Zinkevich, Markus Weimer, Alexander Smola, and Lihong Li. Parallelized stochastic gradient descent. In NIPS, volume 4, pp. 4. Citeseer, 2010.
13

---

Under review as a conference paper at ICLR 2022
CONTENTS OF APPENDIX
Techniques
14
Convergence rate CFL
15
B.
Bound of Gradient Noise
15
B.2
Bounded Gradient Noise of CFL
15
B.3
Bounded Approximation Error
16
B.4
Proof of Theorem
16
B.4.1
Start up.
17
B.4.2
One Step Progress
17
B.4.3
Weights rounds.
20
B.4.4
Convergence results
20
B.5
Proof of convergence rate non-convex setting
Experiment details
25
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
Algorithms
28
A TECHNIQUES
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 non- negative sequence (d--1)r21. and any parameter > 0, T Z 2imazti' there exists constant step-size 1j S Mmas and weights We -um)-- such that for Wy. = EE We
1 T+1
- pn)d-11- - Σ
W--
_:d Ô (uddexpl (-mmpaa)
ΦT
(12)
WT
Lemma A.2 (Sub-linear convergence rate (Karimireddy et al. negative sequence {dy-13r21 and any parameters Mmaz 0, c1 constant step-size 1) S 1maa such that
2020b Lemma 2)). For every non-
2 0.
02
2 T there exists
T+1
de-1 de +an+ + can") xan++ < Mmaa (T 11 T +1
do
2vcido
do
T
+2
C2
T
17
7
T T+1 1
(13)
Lemma A.3 (Relaxed triangle inequality (Karimireddy et al. be vectors in Rdd Then the following is true:
2020b Lemma 3)), Ler [VI...., V7}
Σ vill Σ lv.l..
(14)
1=1
Lemma A.4 (Separating mean and variance (Stich & Karimireddy, 2020 Lemma 14)), Ler
E,, E, be rundom variables in Rd which are not necessarily independent. First sup- pose that their mean is E[E,] = ε., and variance is bounded as EE|E - & < M||&|| + oo?, then
the following holds
E
Σ
(T 12 + TTO2
(15)
Lemma A.5 (Perturbed strongly convexity (Karimireddy et al. 2020b holds for any S-moohhh and j-strroggyy convex function h. and any x, y. z in the domain of he
Lemma 5)). The following
1 lly z112 L||z - x|1
(Vh(x), - 2 h(z) h(y) 4
(16)
Lemma A.6. Define S = ΣT= Pt where DTT = 1, and Pt S pc+ then S < F ET
In
14

---

Under review as a conference paper at ICLR 2022
B CONVERGENCE RATE OF CFL
B.1 BOUND OF GRADIENT NOISE
Lemma B.1 (Bound of Gradient Noise), Suppose fi(w) is the local objective function, and f(w)
E
[[(w]] is the global objective function. Define V[(w) = V[i(w) + So. E|si] O, and assume
||||| w
A
|| [(w)
+ =B, we have
V [
- (A² + 1)B |V] + +B²
(17)
Proof.
E [((
= E | + si19
(18)
E ||> || +E ||::
(19)
$ (A+ 1 B |V)(W| + B.
(20)
B.2 BOUNDED GRADIENT NOISE OF CFL
Lemma B.2 (Bounded Gradient Noise of CFL). For Formulation (CFL. we can bound the gradient drift as
consider CFL and FedAvg,
(1) FedAvg only optimize current local objective functions, thus,
fra S (1 + A² + / G² + D2
(2) For CFI, in general (same clients can appear in different rounds), we have
E
Σ Pr. V.r((W))
$ 1+ + A² Σ phs B[V](W))
G² D2 Σ p
(3) For CFL, when clients only participate in training once(ōi, are independent for all t and i), we have
Σ Pra vor. 5 (I+ + +A9I pr
B(V
+ + D2) Σ pr.
Proof. Using Assumption 3
together with the fact that Vi,,(w)) = V + d2,5 + Er,i we have
E V(. = E (()) S., + E.,il
(21)
= -EI E E E
(22)
(1+ + (f) + GD + D2
(23)
The second inequality based on the independence noise, and directly use Assumption the last inequality. Similarly, we have
3 we get
E
Σ
p ((ra(w))
=
Σ Pr. (.T,((w) + + + Er:i)
(24)
= + +
+ E
Σ
Pr. Er.
(25)
7=1
11+ + 12 Σ 2
E ( + +D²
Σ
2
(26)
15

---

Under review as a conference paper at ICLR 2022
For the last inequality, when i1, and d12,1 are independent for all 81, t2.
E
Pro Virl(W)
= E
Pr. V [rri(w)) + dr, + ET,i)
(27)
= [[]) + E
Σ
Or.
+ Σ Dr, STi
(28)
T=1
(++ + +B²
Pr..
BIV (G² + D2)
Σ
2 Pr.
(29)
B.3 BOUNDED APPROXIMATION ERROR
Lemma B.3 (Bounded Approximation Error), For A,,(w) Vfi((w) (V.,((w) (cf.. Definition 3 when use Taylor Extension,
Vii((w = V.al(w)) + v (() wi).
we have
||r,)(W]|| <e wreel
Proof.
| (w)]
Vee((w) v
(30)
[Vla(w) V.r Hejk(w wrikk)
(31)
(e.(w,,)) wi,Kk) Hejk (w (wik(w-wo) w.,,kK)
(32)
f(.Wee))) - HijK)(w wwiik))
(33)
S <||w - w
(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 point S (a, b) such that
(c(c) f(b) f(a)
(35)
a
The last inequality is based on Assumption
B.4 PROOF OF THEOREM
In this section we will give the complete proof of convergence rate of algorithm when the local
objective functions are convex.
Algorithm 2 CFL Framework
Require: initial weights wo. global learning rate ng. local learning rate 17
T do 2: communicate w. the chosen clients.
1: for round t =
3: for client E S₁ in parallel do initialize local model w1,100 = wi.
4:
5:
for k: = 1 K do
6:
Vi,
Ei=l Pr, (isl(arrs))) + Veskk
7:
Wriik & Wiiik-1 - TĀhiiA (W),ik--))
8:
communicate Awo, + Wt.LK We.
9:
Aw, Eies. AwAi
10:
Wi+1 & wi + Awi.
16

---

Under review as a conference paper at ICLR 2022
B.4.1 START UP.
The local objective function of round client is
2-1 Prafra(w).
fi,(w) = (Pr,sfe,(w)) + Σ
(36)
T=1
Without loss of generality, assume Exm 1 Prii = Then follow the steps in algorithm we have
1-1
(+((w) - Pr, V(,,(w) + Σ PrraVir
(37)
Then the noisy gradient in mini Mini-batch SGD can be described
(.,.,( = V
+ Verkk
(38)
Then follow the steps in algorithm 2 we have
N
K
Aw:
- T77
Te, (wo.
(39)
N
K
A(Aw
fex (w))))))
(40)
Then let = Knngg we have
N
K
AWl
T
Th. (wr
(41)
NK
1=1
K
E[Aw]]
-1
v fe..(W
(42)
NK
1=1
B.4.2 ONE STEP PROGRESS
Consider the one-step progress we have
E wi + Aw; w0 11 = ||:, - w01
-2E(w: w., Awi) + EllAw, 1|?
(43)
A
A2
Firstly we consider A1 part in equation 45
2F: w", Aws)
2n
(1 10 wi)
(44)
NK
2m
N
11 (p (WrL)) + Σ Pr.s V (r.(WIs))) wi wi)
(45)
NK
K
2n
2n
Prs (T. w* -w))
Pro P.s(Ar.laaa)).e -w,)
NK
NK
k=1r=
i=
k=1
(46)
2n NK
ΣΣΣ
Pr.s V..VVr. (f.lwWe))) w- wi) 2n
Pr. will
(47)
We use equality (42) for first inequality, and directly use Assumption and Cauchy-Schware Schwarz inequality for last inequality. Then we can consider the first term of inequality 477. Firstly, by Lemma A.5 we see that
(V VWrrsweri w wi) S fr.((w") sT,( # [| w w01l² + L| w. (48)
17

---

Under review as a conference paper at ICLR 2022
That is, based (47 and 48
have,
2E(wi w², Awi)
s <-2n(felwr) fi(w") + 1
1 Ill, w²113)
2
Wriik-1 - well
NK
1-1
+ 21) Prii 1|0"" - will
Σ r=1
(49)
Cpo.s Then consider A2 in (43) and define Cpa = ppo N
P..).
Cpp N Opa,ó and Cpa N Ei=1 Cpa,s we have
El|
Aur?
112
E
Pt. V. V. Σ Pr, Virl + tusk
(50)
N2K?
12
1/2
pr. A (wr..k11) + Ve.sk Prss V.r.e Σ
(51)
N2K2
Lem
K
2
1122
Pr. VT.
Pr. Pr.i (,,,r,(wo..a-)))
+
(52)
NK
NK
i=1 k=
Tem AB3 2n²
N
K
1100²
E Σ Pra V V. (T.((w)
E
pr. Predm.(Wisssi))
(53)
NK
NK
1=1 km1
Lem t 2x/²
N K
1+ A
17:))
62 D2 Σ p ))
21 2
N
t-1
P+,) ) RR²
120²
NK 1=1 k=
N
NK
1=1 1=1
(54)
Lem A3
N K
Cpp. +
+2 cxo +
21²²
Σ
N 1-1
Pra)
R T202
NK
N
NK
mm k=1
i=1
(55)
Aua
161/ Lepp (s(wi) - -[ww)) +
8n 2n² L2
K
Spn Emn,E - well + 21 Upa
2n 2
Σ
N
P+,)
2R²
2²0²
NK
N
NK
(56)
Then consider equation (49 and (6). to solve Bl - will. we have
2
Bllwe,i. - will2 ni E
Σ ge. (wr, (w.
(57)
Lem A.4
kmf
E
[ knfo²
V
(58)
Here directly use Lemma A.4 get inequality
58
18

---

Under review as a conference paper at ICLR 2022
Then for
||| V fw,((w)]
we have
E
[-1 Pt, Ve,((e))) + Σ Pr. (isl(s
E
(59)
1-1 Σ
2
E
Σ Pr V fw,(w))
Pr. - n, (w)
(60)
7=1
Lem A.3
[-1
2E
Pr V (w)
+ 21E
Σ
Pr, A (w))
(61)
Lem ??
t-1
20p R [ [1] + 20pa.t + 2(
pr,)) ) RR2
(62)
Ass 4L Cpn E w will? + 8Lppmi (f(ws) - -((w))) + 2Cp + 2( [-1
Pr,i)
(63)
Combine equation 58 and 66 we get,
Bl will
S 4k211 21 L2 cpp. :llls,s-- - w.1l² + 8h2n1 (J - f(w")) + -222m cpa. + 2k? m/ [
pr.)
r2 + knj 0²
r=1
(64)
That is,
Bllweii, will
k-1
t-1
Σ (8K2 uh (f(we) - f(w=)) + +2K2 12 + 2K2
m/
Pr. pr,)) R2
1? cppp))))
r=0
T=1
(65)
(f
+ +2 2
p + 2k (2 7- Pr. 22 + Kio0²²
(66)
4K f T.2 Cpa.i
Combine the equation
43
49
556 and (66), we get
Bllwe + Aw; ~ 112
16K mm, Lcps, ,(1 + 4nLCpea) [f(ww: -8") + 2 cpa
5 Wl
w011 (-21) 16n2Lcpp Lcpp
1k21, 122
1202
N
1-1
pr,)) + 4K<2 L( pT.) (1 + AnLcpnns)
2n²
R²
NK
1 4K2 L2
1
N
2km L(2K Cpoid + 01 + Ampc)pe))
+
21
Σ
N t-1
Σ
Pr. R llwe - w*ll
(67)
N
1- --K2 T/ L2ppp
N 1=1
Then notice that
16K fok"mii'' L'c (1 + AnLcpa
2n 16n Lcps +
$ 0.
(68)
N
4K4 np T2 122
Use the fact that 77 = Knmn. and solve above inequality, we notice that if n satisfy
3ng + 4cpa.
/ ACpp.ingg
<
(69)
61. 6I./Cpun
19

---

Under review as a conference paper at ICLR 2022
for any Cpn.ds convergence be promised.
Define
Gyn the largest Cpn.b let 1j S
33n + 40p v.
A Ni
33 33-81 + / + +4gg PB and then
we have 1 1f 1.2 cppp. 2
/
30
144nb0p 1- o- Lpndd
S
1 33+ y fnggrg ung ve -2 12.
12
Define CR.
P Pr,)) RR² and eR # Σ CR Assume ei 20pa
(Σ
d² NR
2cR.
Lepg 02 302
La²
Leg and C2 N Σ Σt=l Pr, R, inequality (6 become 3ng
Bmg
Bllwr + Awi - w0 s (1
B 2²11 n(f(wi)) -f) + eun + con + +cn w0ll I
(70)
Move f(w:) f to the left side, we get
f(Wi)- - -ww") = (1 1m Bl wi - w01 - - w01 -
on + c2n + 9t-
(71)
Here Pi is constant bounded by es ||wb w0 Because of pt, the model cannot converge to arbitrary e; instead, it can only converge to the neighborhood of + yp where yp is the weighted sum of the sequence 1 The following parts give the convergence rates when models converge to + ip for convenience.
B.4.3 WEIGHTS ROUNDS.
We can carefully tune the Pr,; minimize the noise while speeding up the convergence. Here give the lemma of the best choice of Pr,i-
Lemma B.4, On round 1, when setting Pr,i = (t- for any T < t, and pt, = (t-1)R*+D* we can minimize C1 and 02 to get best convergence.
D2
(t=-)(-1))2
Proof. Minimizing 61 and 0g is equal to minimize Cpc
CR. that is,
min F
Pr.;) R² + G + D2
pr.))
s.t. Σ Pr. = 1,
(72)
Solving above optimization problem, we get the results.
Using lemma B.4 we have min(Cpo + +cn] = G2 + D2 ('+((-1)8*) [))+(--)))) Notice that the value of Ci.
C2. and Cy are changing over t. We use ci, cg and ca to represent C₁, 62 and 03 on round t.
B.4.4 CONVERGENCE RESULTS Strongly convex functions. By equation 80), when (e,i(w) are strongly convex functions, using Lemma A.l and define gi (1 -- we have
f(WF) - f(ww) 0 (ulleo w01l expppp -mm)))
ge (on + c2n + vr) (73)
Em1 9t
By Lemma A.6 we have,
Σ qt t=1
I Σ
co(eR + cpa) =
1
Σ
T
91
G2 + 22
f12 + (t - 1)
D2 + (t- (1-)
1== 91 t=1
1
Σ 41
G² + D2
Re + D +
R²
D
Σ 91 t=1
(R' + 12
R D2
R22
(R2 + D232 In7)
D
=0 G2 + D
(74)
RR + D2
20

---

Under review as a conference paper at ICLR 2022
For yet, by Lemma B.4 we have,
8
9:9t S0 11=1 ==1
R
D2 R
D
-12 - R2122 T
D
In
1100 w²ll
(75)
Then define 69
Et=1
U:
C22
E U: we have,
21-1
21-1
f(wr)- - f(w") - - 000
11w0 w01]2xxp(
) + En + E27
(76)
2
=0 1 11W0 w011 expp
UT
-) +
o²
+
CA
CB
CC
+
CD
Tco
UNKT
11272
112733
(77)
where co 1 1 A3 B², CA= G2 R+D CB
D²
D D++
L R
Leg 1
Les rig
cC
CD
General convex functions. When ((,((w are general convex functions (μ 0), directly use Lemma A.2 we get,
CoF T
o2F
FCA
VCBF
C
VeD
+
NKT
T
T
T
(78)
where = 1 A2 B², CΛ = G² + R24D2 (n++Day
D²
D
cC
m
Lo²
+
Leg
1/
CD
Leg
ng
and
F Wo w'1
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 described as
4 = E3 1w0 -660-u0 - --1l= -
D R2 ("TERR
D
InT) T
||w
w01l
(79)
Convergence of FedAvg. Notice that FedAvg is special case of CFL by setting pt,i 1 on round Having this, we derive the one round convergence of FedAvg under our formulation as,
f(wi) - f(w²) < - pm B||l w011 - -E - w01l + tin +212
(80)
2
where = 2(2 + D2)= + x²
NK C2 = LIGa D2)
+
Lo² kogK
Then using Lemma A.1
we get the
3
convergence rate when (w) are strongly convex.
f(wi) - f(ww' 2 0 μ1 |W|WW - w0|l exp
exp(
HT Leo
+
CA u& +
èc 1212
(81)
where co- 11 12 + B2 CΛ G2 D22 cc
Lod Ti
Les vig
Besides, when fe,i(w) are general
convex, we have,
f(wF) - [(w))( COF
O²F
FCA T
CCF2 T
(82)
NKT
where co- 1 A B G2 D2,
cg
R.K
La²
Lag and F
llwo w" w012
B.5 PROOF OF CONVERGENCE RATE FOR NON-CONVEX SETTING
L E
+EKVf(w)), Awi)l E [[f(w[+1) $ B[f((.))
(83)
A
A2
21

---

Under review as a conference paper at ICLR 2022
For A1 part, we have,
BKV [wws), Awi)]
[[V](w)) V [(slaw))))))
(84)
NK
N
K
7
(Vf(w))) Σ Pra V.r.(Wank)
Σ Pr. PrasmalurrN))
(85)
NK
N
E
(V)())) Σ Pr. V (.T.(w)s))))
+
"
Σ
(1 pt.))
[ [
- R²²
NK
2N
==1 k=1
d=1
(86)
N
K
12 (w.(()
1)
7
E
V((w)) - Σ
Pr. V...((es)))
E
[VF(
-E
Σ
Pr. V f.
2NK
2m
Rm
==1
7
pt,))
IE
|
+ +1²)
(87)
2N
From equation (53
we have
2T NK
N
K
1702
E
||Aw/]
Σ Pr. V (ralWain))
+E
Σ Pr. A (.
+
NK
(88)
Then when 7) S 27. the 18
- Pr, V fr.((,r,.)) term can be ignored, since the coefficient
number will less than 0. Then the remaining term in A2 is 2n² N E (1 12 + NK Then we are willing to consider the
Vf(w)) - Et Pr. (..,)
Then we have
E
v ((w)) - Σ Pr, (T.(( 1=1
= E
vf(w)) - Vf(we())) + V.(weakk) - Σ Pr.s V (ra(War)
(89)
2E [V/)) - v {((W)))) + 2E
V [[(We))) Epro Pro V...aar.
(90)
< 21 || - - + B2 12+ Σ pro
E
[IV + G² ( D2
Dr.
(91)
< 2 ||w, - -a,a
+ +2,2
B² B²= -A= >2>r?, pr: E [[|WAiA- - will
+2
1² + A2
pr.
E [+))())
+
6² + D² Σ Pr.
(92)
Combine equation
87 and
92 have
22

---

Under review as a conference paper at ICLR 2022
E
(V f(wr), Awi)l
N
Cp ||wre well? #n(ppn -1 -1- Σ Pt.i
}E
[
NK
2.V
i=1 kml
N Pt,;) R2
+
17
Cpc
(93)
Then we have
nL2
E [[((+))
[[[[(w)]]
Cpaat B ||waa - -
+ +n(cpp
1
Li=1
Pt.
}E
[V((w)))
V
NK
2N
+
7
Cpc
+
1
Σ
NV.
11 - pr. p22 n2?
+ Lip
Σ (1 - pc,))
N
Lyi²0²
(94)
2
N
N
2NK
Because we know
Bl|w,,,, well
4k 4 L cpp. :lll: wil1 + 4k2n cps. EE
[[T(())))) 2k2n?
+2k2m cpe.t
Cpa. +
2r.s)
RRR kni
1=1
(95)
That is,
Bll - will?
4k2 of cpe [[V(()))) + 222n2 epont
Spait 22 m
Pra) 2 R² knto²
(4h2 L Lppr)))
(96)
(Ah pp. ( [IVS(w))]
2k Cpa.t +
(2+=) Pr. 22, R2 knj
(97)
1 2 L2 L2
Let 8K2 Cp 5 1, we have,
N
Σ
Cpn C W w2ll
NK
N
4K22 CIE
[V((w))) +2K2 Spani + +2K22 (2 2 + Knjo"
Cpa.i
4k2 AK2nnLLe L2epm.
(98)
a²
Cpa. E
[V](w)))l?
Spart
+
Pr. pr. R2
(99)
2
1K
r=1
1
0²
E
[V((w)]]
2500
)
R2
(100)
2N
4K
Then have
23

---

Pt.L Under review as a conference paper at ICLR 2022
E
E
[[[ S R. [[(w)]]] +1
(1.2 (1.2 +1)pp
-1
i= Pr.
IE
||V
2N
+ 7
2
Cpa +
N
1
N Σ
-
+ N
Lai
N
(1-Pt,) 1=,)
-
L1i²²²
2NK
N
t-1
O²
+ tnb²
PC
2N
R
4K
(101)
1=1
Then must choose the value of Pt.s for better convergence. Follow the idea that we want train a better model when convergent, we choose Pt, that can minimize the constant term, which is by solving
min G² + D2 Σ
+
② 7=1
Pr. pr.)) 2
s.t.
Pr. =1
(102)
We get same results as when the objective function is convex, that is, Prái iD24(t-1338 17 for
D2
(t-1)=²+D² and min + D2 Σ Ph. + (Ei=1 22 = G² any 7 < t, and Pt. (D*+(1-1)82 Da D'+(-11H Then we simplify the equation by using co (t), ci (t), and (t to denote the (D=+(1-)))))
constant terms, have
E [[f(w(+]) S E [f(wi)] - (t) [V+(W)]] + +t)
(103)
Then we have
T Σ co( [IVS()))]]] - [[[(w])] E [[][")
T
17
(2( +
(104)
1
Consider co. because the value of B² and can't be constrained, the algorithm can't converge for very large A and B. Here we first consider when co < 0, and use Cm to denote the min co. Then let
7
VKN
we derive the convergence rate as VTL
T
= 0 L(fo f.) VTNKcm
L
1.
VKN L
R²
Σ ||)(E)
E
+
VT
R2
D2
VNK
t=1
VKN
D4
VKN
D4
TL Cm (R2 + Daya + Then want to analyse when the algorithm won't converge. When the algorithm won't converge,
TVTL (R + D2j2
(105)
- Pimi N/4 Em (L2 1)( AA that means co 2 0. Because co (L2 + 1)cps
Ba Et - 2 Then the value of A2, B2, L. decide co 20. 0.
Notice that in FedAvg, Pt.i 1, and C0.ang = (I.2 + 1)(1 + 12 + B²) 3. and in CFL., we can
setting different p to get better convergence. For example, when large, setting Pr. 1 we have
Co. (L2 + 1)(1+ + - म Thus, we draw the conclusion as
Then we have following observations:"
CFL converge faster than FedAvg by reducing the variance terms. For cp N EN (1
1)(1 + A2 + Ba Et (2
Pt. 2- FedAvg, we have Pt, = 1, then Co.ang + B2) 2. However, in CFL, we can adjust such as when setting z then the variance term reduce
Pr, = t. we have co (I?2 1)(1 + A2 + Bº
from B² to B²
24

---

Under review as a conference paper at ICLR 2022
The convergence rate of CFL become better for larger t, since Cpn in co become smaller for larger
Improve N, will speed up the convergence by reducing the terms about fo - f. and o². However, larger N and K will cause larger information loss and round drift (terms with R and D), thus, it should be trade off in practice.
C EXPERIMENT DETAILS
C.I NOISY QUADRATIC MODEL
GR
C% Fediug
loss
1.0
50
rounds
Small L, strongly convex, small round drift (b) Large L, strongly convex, small round drift
4.50
425
Festrox
100
4.00
3.2
335
3.6
rounds
(c) Small general convex, small round drift
Large L, general convex, small round drift
Restmox
loss
10
50
rounds
(e) Small L, strongly convex, big round drift
(f) Large L, strongly convex, big round drift
C"
Fediog
Restrox
4.6
335
3.8
3.50
3.00
rounds
(g) Small L, general convex, big round drift
(h) Large general convex, big round drift
Figure 2: Performance of different algorithms on noisy quadratic model. The curves all evaluate the loss on global test datasets.
We use the noisy quadratic model introduced in Zhang al. (2019) to simulate the assumptions
we used in the proof. We use the model f(w) W Aw B w + C, where w E R" is the parameter want optimize, and A E R A O. Ra and C E R. We construct A by firstly constructing a diagonal matrix A and then constructing A by let A = U AU, where U is unitary matrix. Here control the eigenvalues of A control the convexity of model, that is,
25

---

Under review as a conference paper at ICLR 2022
SRD
BRD
Method
SL-SC
LL-SC
SL-GC
LL-GC
SL-SC
LL-SC
SL-GC
LL-GC
FAVG
0.03
0.08
0.33
0.09
0.02
0.01
0.09
0.02
FPROX
0.04
0.07
0.35
0.09
0.02
0.01
0.26
0.02
CFL
0.2
0.09
0.35
0.09
0.25
0.08
0.3
0.08
Table 7: Best learning rate of different algorithms on noisy quadratic model
L. Because A and A have same cigenvalues, it's simple control the eigenvalues of A by control the eigenvalues of A. To simulate Assumption we formulate the gradient noise model by
1 S Amin (A) < Ama <
(t.a(w) Aw + B 8; + Ex,i + Mt,ik
(106)
where 6; denotes the client drift of client j. Ét.i denotes the round drift of client j on round i, and Vt,ik denotes the noise of gradient of client j round i, iteration k. All of above drifts and noise are generated from Normal distribution with zero mean and different variance.
In practice, show if the numerical results match our theoretical results, 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 strongly convex, and μ = 0 for general convex. For different round drift, we set RII = 100 for big round drift, and [.,ll = 0.01 for small round drift. Besides, we set fixed variance of 6; and Mt,i for | 0.01, and |EI|1,,,. We do the gradient descent by let Wr.,k+1 = wr,i, ( and we use ||Aw + B| as loss because for convex functions, when it reaches the global optimal point, we should have ||.Aw B| 0, and if it far away from global optimal, || + B| will be large.
20 for large L, and L for small L. For convexity, we set μ for
0.00001.
Besides, show that CFL algorithms learning rates for different FL algorithms on noisy quadratic model. In Table 7 we denote small round drift SRD, big round drift BRD, small 7. as SI., large T. as LI.,, strongly convex 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.
tolerate larger learning rate here. Table 7 shows the best
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.
C.2 REALISTIC DATASETS
C.2.1 SETUP
We consider federated learning an image classifier on split-CIFAR10 and split-CIFARIO datasets with ResNet18, 18, and split-Fassee Fashion -NNIST dataset with a two-layer MLP. The "split" follows the idea introduced Yurochkin et al. (2019); Hsu et al. (2019); Reddi et al. (202T), where we leverage the Latent Dirichiet Allocation (LDA) to control the distribution drift with parameter (See Algorithm Larger a denotes smaller drifts here.
In our experiments, unless specifically mentioned otherwise all datasets partitioned to 210 subsets for 7 different clients: 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 CFL- on layer, and B 0.1 for last
Regularization, we set the weight of regularization term for block (layer). For FedProx, we set the weight of proximal term μ = 0.1. and for MimeLite, we set the global momentum weight for 7 = 0.01. Besides, for all experiments, we set fixed learning rate Ir = 0.01. We also naively examined warm-up tuning strategies but can not observe significant improvement on final results.
cummen
cataset
Construct local datasets with overlap. Fol- low the partition methods of disjoint local datasets; first split the whole dataset to
current pointer
noxt pointar
26
Figure 3: Process of constructing local datasets with overlap. Blue lines bound the current local datasets. Red

---

Under review as a conference paper at ICLR 2022
M X 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 pointer to point to the start position of the current local dataset. Figure show the case when M = 5: D1 D; 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 8 steps, and if it moves to the end of all the sequence, it will come back to the start point.
In practice, the Cifarl0 dataset is partitioned to 210 subsets for 7 clients, and set the size of local dataset S = 285. Then when we set 8 = 285, the local datasets are disjoint, which means the overlap is 0%. Otherwise, when set 213, the overlap is 25%, and when set 142, the overlap is 50%.
C.2.2 APPROXIMATION METHODS
Regularization Methods. We use Taylor Extension to approximate the objective functions of previous rounds, that is,
w) + 1 j/w w) w)
-
(107)
where s are the parameters of previous rounds. Then the gradient of f(w) is,
V((w) = ff( - f(O) - -w.
(108)
Having this, we can approximate the gradients of objective functions of previous rounds. The problem how to approximate V² f()). 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,
Fg V (()))
(109)
where Fiy are the entries of Fisher Information Matrix. Another method is to calculate the diagonal Hessian matrix. We use the PyHessian package (Yao al. 2020 this experiment.
In addition, if the parameters or the Hessian matrix changes too much, the performance of this method constrained. To formulate this problem, assume
[ for some arbitrary e, have
[w))]())] S selw -
The corresponding proof refers B.3
In each round, the server will collect Hessian matrices from clients, and store them in buffer. Then at the beginning of next round, server combine send latest 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 layer of ResNet18) 8). This is based 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 by,
V FX w,
(110)
where E(x² - 1) is the function that can measure the distance between A-1 and the real local distribution. w ~ ~N( r).
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 refresh BN layer at the end of each round.
27

---

Under review as a conference paper at ICLR 2022
Algorithm 3 iCaRL Construct Core Set
Require: Image set X = {x1, X2, X3: Xn of class m: target number of samples, Φ X' Rd.
current feature function
1: μ 4 1 Exex (xx)
2: for L.... m do
I - + (o(x)+ ((:))
3: Pk: arg minl XEX
4: P f (P1,P2. P2, ... Pm)
Core Set Methods. Another simple yet effective treatment in CL lines in the category of Exemplar Replay (Rebuffi et al. 2017; Castro 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 sample methods. First 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. (Rebufh et al., 2017). See Algorithm 33 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.
C.2.3 ADDITIONAL EXPERIMENTS
Applicability of different algorithms. various vary-ng scenarios in Table
We list the applicability of different algorithms under
Table 8: The applicability of various algorithms under different time-varying scenarios.
Scenarios
Fl. buselines
CFI. methood
FedAvy
FedProx
SCAFFOLD
Mimelite
Reg-laggliiooition
CFL-Core
Stateful clients
Stateless clicuts
Convergence curves for different settings. Siow convergence curves of CFL and FedAvg on different datasets. The settings are the same as results Table 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 ID-Mcan-Fiile Results show CFL can converge to better optimum compare with FedAvg.
Investigating resistance of CFL to time-evolving scenarios. Figure 6 shows the loss curve of Regulaguliiiottion and FedAvg on different datasets. Models are trained on partitioned datasets with = 0.1, and all datasets are partitioned to 210 subsets for 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-Regularizatinn has an apparent mitigation effect on this situation.
Difference between training and test loss. Figure show the loss global test data and past appeared training data. We evaluate the model with stateful clients, set a = 0.2, and use FedAvg algorithm. We show that there is no significant difference berween loss value on global test data and past appeared training data.
C.3 ALGORITIMMS
28

---

Under review as a conference paper at ICLR 2022
0.8
0.7
0.7
Accuracy
Accuracy
0.0
0.4
Feddug
0.3
Fedkig
0.3
ei thour Core
CFI Without Care Set
CP. W Core Set
CFI Wit Care Set
0.1
100
200
300
400
500
100
300 Communication Round
200
400
500
Communication A Round
(a) Performance on Fashion-MNIST
(h) Performance on Cifar10
0.6
0.5
0.4
Accuracy
0.2
0.1
CFL Witoou ore Se:
100
200
300
400
500
Communication
(c) Performance on Cifar100
Figure Models are trained on various datasets with CFL Without Core method use regularization methods, and CFL With Core Set methods use core set methods. All these two CFL algorithms use FedAvg as backbone.
3.5
de Past PascArpeaed
25
05
Accurety
02
Tust
ATTAINT 0R.P Appesedd 1005
0.5
10
50
70
80
30
20
30
40
50
60
70
60
90
Communication Round
Communication Round
(a) Loss global test data and past appeared (b) Accuracy global test data and past ap- train
peared train data
Figure 5: Evaluation global test data and past appeared training data. We trained ResNet18 split-Cifar10 datasct with 0.2 for 85 rounds.
29

---

Under review as a conference paper at ICLR 2022
Fedlig wip.erbrtttnnn
1.5
1.8
1.2
0.4
300
Communicatin
Communication Round
(a) Loss on Fashion-MNIST
MNIST
(b) Loss on Mushion-MMNSS (Local)
2.4
Fectus
Fadiuy
2.2
1.5
1.8
1.4
0.5
0.5
100
Communication R Round
Communcalion Round
(c)
Cifarl0
(d)
Cifarl0 (Local)
Figure 6: Models are trained on split-Fashion evaluated global test datasets. Left column is the full curve of 300 rounds, and figures in right column partially enlarged curves.
Fashion-MNIST MNIST and split- Cift-CiiarrlO datasets with 0.1. The loss is
Algorithm 4 Data splitting
Require: S: a list of datasets split by labels, M: the number of clients, N: the size of local datasets, a: the Dirichlet distribution parameter
Ensure: D: split datasets
1: +-+
2: G + [0, 1,2, ..., len(S))
3: for m = =1,2,..... M do
4:
[p1.22 .... (s)l where pt, denotes the fraction of class in total dataset. 0 + Dirichlet(a.
5:
6:
Dm 0
7:
while (en(Dm)) < N do
8:
i + mallinomiial(.1 1) - Gli)
9:
10:
data + uniform(Slin
11:
Dm + Dm U {data}
S(y) < /Syy)/data
13:
len(Sly)) 0 then
G G/y
<- renormalize(( D (Dop
16:
Algorithm 5 renormalize
Require: 0: weights for different classes, i: the class that should be deleted
Ensure: 0: renormalized weights
I: for 1,2, (e) j + do
2: [ + 80m (tettam/tttttttttteeee
30

---

Under review as a conference paper at ICLR 2022
Algorithm 6 SplitdataMain
Require: S: total dataset split by class, T: rounds, K, N, a. 8
Ensure: Dfimet: split dataset
t spliitDataaS,, K, o)
2: Djimal +
3: for = 1,2, 2...... K do
4: S - splitByClass (D(t)
5:
Niocal t- len (D Dm)
6:
Di Split.Datal Si, cdusterrnuun Niocat, 3)
7:
Diimat + Diinat Dj
31


Reviews:
[{"review_id": "McEBkutezVU", "reviewer": "Reviewer_2NMQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "STRENGTHS:\n\n- The paper introduces clearly the problem and contribution, while clearly stating differences with state of the art in FL and CL. \n- The paper bridges between these two frameworks, and proposes a clear algorithm to learn from time evolving data. \n- Analyses and guarantees are provided under full knowledge of $f_t$\n\nIMPROVEMENTS:\n- I would suggest discussing how to extend CFL for the setting when clients participate at most once during training. I saw the comment in the experimental section but it would be nice to have a remark on the theoretical section describing it. \n- Time evolving patterns could have a common component across clients. It would be interesting to see experiments involving data partitions across time capturing this king of realistic trends. For example on Twitter data each user tends to have a drift (their own posting behavior) but there is also a time component (trending news, etc. )\n- There is no analyses on the real algorithm. How does CFL with specific function approximation behave? what is $R$ for the considered estimation methods? Perhaps it is not tractable but at least a connection, or a remark on this aspect, could make the transition between theory and experiments more smooth. \n-  Given the time evolving nature of data, it would be good to see different metrics (not only final accuracy) that represent how the algorithm is able to maintain accuracy as time-shifts occur. \n\nMinor comments: \n- I would suggest adding a subscript t in equation (2) to indicate that it is a time-evolving objective. \n", "summary_of_the_paper": "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. \n", "summary_of_the_review": "This is a paper that clearly defines a problem in Federated Learning and proposes to extend existing tools from continual learning to this setting. The problem is well motivated, and clearly formulated. Convergence guarantees are interesting but it would be better to have the real bounds for the practical algorithms used, bounds that account for the error estimation of $f_t$. This would allow to see how practical the algorithm is in real settings. Experiments are consistent with claims and show the potential of this framework.\n\nMy score is based on above comments, but I think several of these can be addressed during the rebuttal. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "E52aKb_JEkS", "reviewer": "Reviewer_s89S", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-written. It is easy to follow the narration, all assumptions are clearly described. The motivation of the problem is explained in detail. The notation might be confusing, for example $\\Delta \\boldsymbol{\\omega}_{t, i}=\\boldsymbol{\\omega}_{t, i, K}-\\boldsymbol{\\omega}_{t}$ has three subscript indexes, which is not comfortable to read. It might be useful to use superscript. \n\nTable 1 is illustrative, but it can be useful to add more paper with analysis of FedAvg, such as https://arxiv.org/pdf/2006.04735.pdf. It is not clear what is the CL rate of Yin et al. (2020b). Assumption 1 is not well-described. \nAssumption 1 (Smoothness and convexity). Assume local objective functions $f_{t, i}(\\boldsymbol{\\omega})$ are $L$-smooth, and in some conditions, $\\mu$-convex. If a function $f_{t, i}$ is both $L$-smooth and $\\mu$-convex, then it satisfies $\\frac{1}{2 L}\\left\\|\\nabla f_{t, i}(\\mathbf{x})-\\nabla f_{t, i}(\\mathbf{y})\\right\\|^{2} \\leq f_{t, i}(\\mathbf{x})-f_{t, i}(\\mathbf{y})-\\nabla f_{t, i}(\\mathbf{x})^{T}(\\mathbf{x}-\\mathbf{y})$, and $L \\geq \\mu$\n\nIn the formula, there is no any $\\mu$. It can be useful to have definitions of $L$-smooth function and $\\mu$ strong convexity. \n\nAssumption 2 is limited. \n\nAssumption $\\mathbf{2}$ (Bounded noise in stochastic gradient). Let $g_{t, i, k}(\\boldsymbol{\\omega})=\\nabla f_{t, i, k}(\\boldsymbol{\\omega})+\\boldsymbol{\\nu}_{t, i, k}$, where $\\boldsymbol{\\nu}_{t, i, k}$ is the stochastic noise of client $i$ on round $t$ at $k$-th local update step. We assume that $\\mathbb{E}[\\boldsymbol{\\nu} \\mid \\boldsymbol{\\omega}]=0$, and $\\mathbb{E}\\left[\\|\\boldsymbol{\\nu}\\|^{2} \\mid \\boldsymbol{\\omega}\\right] \\leq \\sigma^{2}$ \n\nIn the paper https://arxiv.org/pdf/1901.09401.pdf, it is shown that bounded variance assumption cannot capture all settings. In the paper https://arxiv.org/pdf/1909.04746.pdf, all results do not require a bounded variance assumption. \n\nAssumption 4 is questionable.\n\nAssumption 4 (Bounded information loss). We assume the information loss $\\Delta_{t, i}(\\boldsymbol{\\omega})$ can be bounded by an arbitrary non-negative value $R$, i.e. $\\left\\|\\Delta_{t, i}(\\boldsymbol{\\omega})\\right\\| \\leq R$.\n\nIt seems not realistic to have a constant bound for information loss, can you please show when this assumption holds in practice? \n\nTheoretical results seem to be sound. Unfortunately, this paper does not propose any non-convex analysis. This part is needed since experiments are done only for deep learning models, which are non-convex. \n\nThis paper has a wide set of different experiments. A broad comparison of different approximation approaches is done. Moreover, the authors compare a new method with other methods and results show that the new method outperforms other methods. It might be interesting to compare with a large number of federated learning algorithms. \n\nThe main issue of the experimental part is the lack of convex and strongly convex models. The theory is done only for convex and strongly convex settings, but experiments are done for deep learning models, so experiments cannot support the theory. \n", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper proposes a novel framework and considers the important problem. The theoretical results are obtained only for convex and strongly convex cases. Some assumptions are questionable and analysis can be generalized. Experiments are done only for deep learning models and cannot support the theory. \n\nI think that novelty of the paper is significant, but the paper has some issues. Overall, the paper is marginally above the acceptance threshold. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ColNfppJ3dH", "reviewer": "Reviewer_87pq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My main concern is about the novelty brought by the paper: \n\n* As the first main contribution, authors list a novel CFL framework. I assume that authors refer to Eq. CFL as t\nhe \"CFL framework\". However, it seems that (CFL) is just a special case of the general FL objective (1). \nMaybe authors mean by CFL framework the data access model, i.e., online gathering of Local datasets over time? \nIf (CFL) framework does not target an online data access model, I don't see the fundamental difference \nbetween (CFL) and total variation type models that have already been proposed, e.g., in \n\nA. Jung, \"Networked Exponential Families for Big Data Over Networks,\" in IEEE Access, vol. 8, pp. 202897-202909, 2020, doi: 10.1109/ACCESS.2020.3033817.\n\nSarcheshmehPour, Y., Tian, Y., Zhang, L., and Jung, A., “Networked Federated Multi-Task Learning”, <i>arXiv e-prints</i>, 2021. https://arxiv.org/abs/2105.12769\n\n\nD. Hallac, J. Leskovec, and S. Boyd, Network Lasso: Clustering and Optimization in Large Graphs, Proceedings SIGKDD, pages 387-396, 2015.\n\n\nThese papers consider local models assigned to nodes of a graph or networks. These nodes could represent different time periods of the time-evolving datasets.\n\n* As the second main contribution authors list a convergence analysis of a gradient method for (CFL). However, it is not clear how the resulting convergence rates are better than what can be obtained from existing analysis techniques for (online) SGD of strongly convex functions, see e.g., \n\n[1]Rakhlin, A., Shamir, O., and Sridharan, K., “Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization”, <i>arXiv e-prints</i>, 2011. https://arxiv.org/abs/1109.5647\n\nThe convergence rates depicted in Table I need more discussion. It is not clear to me how Table I shows that the proposed convergence rates are substantially \nbetter than rates of known FL methods. \n\n\n* As the third main contribution authors mention approximation techniques. However, it is unclear what precise approximation \ntechniques are proposed for solving (CFL). The relevant Section 3.2 only introduces a measure (information loss) for the approximation quality but \ndoes not discuss how precisely these approximations will be constructed for (CFL). \n\n* The main theoretical results of the paper are bounds on the number of iterations/rounds required to achieve prescribed accuracy. These bounds involve several parameters used by Assumption 1 - 4. However, i do not see how the current numerical experiments verify these bounds on the required rounds for achieving prescribed accuracy. \n\nThe clarity of presentation and quality of language needs improvement: \n\n* what is the output of Algorithm 1 ? Is Algorithm 1 meant to be run in an online fashion ? Otherwise the time horizon T should be listed as input parameter. How precisely is S_{t} constructed? The summation in step 6 seems to have flipped a \\tau for a t in the subscript of \\omega \n\n* \"...St is a subset of clients sampled from all clients set...\" How precisely is this set sampled ? \n\n* what is a \"cross-device setup\"?\n\n* \"We give the formal definition of CFL framework in Algorithm 1.\"  pls avoid the term \"framework\" when you actually mean a specific algorithm (your new algorithm 1) \n\n* \"...the previous local object functions cannot be properly approximated.\" ps provide more justification for this \"non-approximhatability\" \n\n* Definition 3.1 talks about approximating loss functions but Eq. (3) is about gradients \n\n* \"To analyze Equation (2) and Algorithm 1 in-depth, we propose the Gradient Noise Model...\" It seems a bit unusual to use a gradient noise model for analysing an  algorithm. The gradient noise model might be prescribed by the application setup (data access model) \n\n* should the LHS of (4) and (5) involve the gradient of local loss functions instead of the global loss function ? \n\n* \"...and in some conditions, μ-convex.\" \n\n* Assumption 2 and 3 involve conditional expectations given parameter vector \\omega. Pls provide more details about the proability distribution of the random variable \\omega. \n\n* There should be more separation between the cells of the last row in Table I. \n\n* \"We prove this comment...\" I would rather say to prove a theorem/lemma or claim. \n\n* \"..can be bounded by an arbitrary non-negative value...\" So we can choose this value arbitrarily small ? \n\n* \"... we analyze the theoretical performance of Algorithm 1 ...\" \n\n* \"..., despite that the term induced by information loss concurrently trades off the optimization....\"  Pls refer to the term using \\eqref{}\n\n* what is a \"...regular linear convergence term...\"?\n\n* \"...the model instead reaches the neighborhood of...\" Do you mean \"iterates\" by \"model\"?\n\n* what is a \"...smoother optimization phase.\"?\n\n* \"We consider to federated learn ...\"\n\n* \"...this (most) challenging time-varying scenario mimics the realistic client data sampling scheme (from some underlying distributions). \" in what precise sense is this the most challenging scenario ? \n\n* \"Note that the trade-off between Hessian estimation and computational overhead constrains the practical feasible of such approach.\" Unclear \n\n* \"... as a method to approximate diagonal Hessian matrix, is slightly preferable than Fisher Information Matrix, though the latter one involves less computation.\"\n\n* what is \"...challenging non-overlapping time-varying heterogeneous data\" ? \n\n* \"...we are the first to provide such theoretical guarantees ...\" what precisely do you mean by \"such guarantees\"?", "summary_of_the_paper": "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. \n", "summary_of_the_review": "My main concern is about the novelty brought by the paper: \n\n* As the first main contribution, authors list a novel CFL framework. I assume that authors refer to Eq. CFL as t\nhe \"CFL framework\". However, it seems that (CFL) is just a special case of the general FL objective (1). \nMaybe authors mean by CFL framework the data access model, i.e., online gathering of Local datasets over time? \nIf (CFL) framework does not target an online data access model, I don't see the fundamental difference \nbetween (CFL) and total variation type models that have already been proposed, e.g., in \n\nA. Jung, \"Networked Exponential Families for Big Data Over Networks,\" in IEEE Access, vol. 8, pp. 202897-202909, 2020, doi: 10.1109/ACCESS.2020.3033817.\n\nSarcheshmehPour, Y., Tian, Y., Zhang, L., and Jung, A., “Networked Federated Multi-Task Learning”, <i>arXiv e-prints</i>, 2021. https://arxiv.org/abs/2105.12769\n\n\nD. Hallac, J. Leskovec, and S. Boyd, Network Lasso: Clustering and Optimization in Large Graphs, Proceedings SIGKDD, pages 387-396, 2015.\n\n\nThese papers consider local models assigned to nodes of a graph or networks. These nodes could represent different time periods of the time-evolving datasets.\n\n* As the second main contribution authors list a convergence analysis of a gradient method for (CFL). However, it is not clear how the resulting convergence rates are better than what can be obtained from existing analysis techniques for (online) SGD of strongly convex functions, see e.g., \n\n[1]Rakhlin, A., Shamir, O., and Sridharan, K., “Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization”, <i>arXiv e-prints</i>, 2011. https://arxiv.org/abs/1109.5647\n\nThe convergence rates depicted in Table I need more discussion. It is not clear to me how Table I shows that the proposed convergence rates are substantially \nbetter than rates of known FL methods. \n\n\n* As the third main contribution authors mention approximation techniques. However, it is unclear what precise approximation \ntechniques are proposed for solving (CFL). The relevant Section 3.2 only introduces a measure (information loss) for the approximation quality but \ndoes not discuss how precisely these approximations will be constructed for (CFL). \n\n* The main theoretical results of the paper are bounds on the number of iterations/rounds required to achieve prescribed accuracy. These bounds involve several parameters used by Assumption 1 - 4. However, i do not see how the current numerical experiments verify these bounds on the required rounds for achieving prescribed accuracy. \n\nThe clarity of presentation and quality of language needs improvement: \n\n* what is the output of Algorithm 1 ? Is Algorithm 1 meant to be run in an online fashion ? Otherwise the time horizon T should be listed as input parameter. How precisely is S_{t} constructed? The summation in step 6 seems to have flipped a \\tau for a t in the subscript of \\omega \n\n* \"...St is a subset of clients sampled from all clients set...\" How precisely is this set sampled ? \n\n* what is a \"cross-device setup\"?\n\n* \"We give the formal definition of CFL framework in Algorithm 1.\"  pls avoid the term \"framework\" when you actually mean a specific algorithm (your new algorithm 1) \n\n* \"...the previous local object functions cannot be properly approximated.\" ps provide more justification for this \"non-approximhatability\" \n\n* Definition 3.1 talks about approximating loss functions but Eq. (3) is about gradients \n\n* \"To analyze Equation (2) and Algorithm 1 in-depth, we propose the Gradient Noise Model...\" It seems a bit unusual to use a gradient noise model for analysing an  algorithm. The gradient noise model might be prescribed by the application setup (data access model) \n\n* should the LHS of (4) and (5) involve the gradient of local loss functions instead of the global loss function ? \n\n* \"...and in some conditions, μ-convex.\" \n\n* Assumption 2 and 3 involve conditional expectations given parameter vector \\omega. Pls provide more details about the proability distribution of the random variable \\omega. \n\n* There should be more separation between the cells of the last row in Table I. \n\n* \"We prove this comment...\" I would rather say to prove a theorem/lemma or claim. \n\n* \"..can be bounded by an arbitrary non-negative value...\" So we can choose this value arbitrarily small ? \n\n* \"... we analyze the theoretical performance of Algorithm 1 ...\" \n\n* \"..., despite that the term induced by information loss concurrently trades off the optimization....\"  Pls refer to the term using \\eqref{}\n\n* what is a \"...regular linear convergence term...\"?\n\n* \"...the model instead reaches the neighborhood of...\" Do you mean \"iterates\" by \"model\"?\n\n* what is a \"...smoother optimization phase.\"?\n\n* \"We consider to federated learn ...\"\n\n* \"...this (most) challenging time-varying scenario mimics the realistic client data sampling scheme (from some underlying distributions). \" in what precise sense is this the most challenging scenario ? \n\n* \"Note that the trade-off between Hessian estimation and computational overhead constrains the practical feasible of such approach.\" Unclear \n\n* \"... as a method to approximate diagonal Hessian matrix, is slightly preferable than Fisher Information Matrix, though the latter one involves less computation.\"\n\n* what is \"...challenging non-overlapping time-varying heterogeneous data\" ? \n\n* \"...we are the first to provide such theoretical guarantees ...\" what precisely do you mean by \"such guarantees\"?", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ChS4Nb39tCZ", "reviewer": "Reviewer_XVxz", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Limited novelty:** The technical novelty of this paper is relatively limited. Using a replay buffer to approximate historical objectives is a well-known approach in continual learning. Extending it to FL seems to be straightforward as long as the replay buffer remains local to each client. The theoretical analysis is somewhat interesting but it relies on strong assumptions such as convexity (more details below), which does not hold for deep neural networks. Furthermore, the result is a bit cumbersome and difficult to interpret, and the analysis technique and result appear to be quite similar to Yin et al. (2020b).\n\n**Unrealistic assumptions:** It is evident that objectives related to deep learning models are not convex, so it would be good to analyze the convergence of non-convex objectives as well. Moreover, I feel that the assumption that the time drift is independent across both $t$ and $i$ (Remark 3.2) is a fairly strong assumption. Usually, the data varies gradually over time, so the time drift should also change gradually over time $t$, instead of being independent for each $t$. I further do not understand why $\\delta_i$ needs to be zero-mean. Usually an upper bound of the gradient drift across clients is sufficient for the analysis. In general, considering gradient drifts as random variables is problematic, since you are talking about the full (i.e., non-stochastic) gradients in the definition of drifts. These gradients only depend on the model parameter $\\omega$ and there should be no other random source (unless you consider the time evolution of data to be random, but even then it should be at least Markovian instead of fully independent).\n\n**Interpretation of results:** The results are generally cumbersome. It would be worthwhile to see whether some of the terms can be simplified in the $\\\\mathcal{O}(\\\\cdot)$ notation. I do not understand how Section 4.2 is related to time-varying scenarios. In particular, it is not clear why setting $p_{t,i}=1$ would eliminate $R$. Intuitively it does not seem to make sense, since the information loss (upper bounded by $R$) should affect the convergence even if $p_{t,i}=1$. I also do not understand what \"CFL methods accelerates the convergence by reducing the variance term\" means in Remark 4.5. While I see that the result in Theorem 4.4 has less terms compared to the result in Theorem 4.2, it is unclear how those terms are related to the variance.\n\n**Experiments:** When talking about generative methods, the paper mentions \"Maintaining a core set for each client may become impractical when\nlearning scales to millions of clients\". I'm not sure why the core set needs to be maintained collectively across different clients, and if this is the case in the core set method evaluated in the experiments, it may cause privacy issues. It seems sufficient for each client to separately select and manage its own core set. In other words, assuming that each client has a fixed amount of storage, whenever new data arrives, it has to delete some old data. The client can choose to delete the data samples that are less representative, and increase the weights of the remaining representative data samples. In this way, a core set would be constructed on each client alone, without involvement of other clients, so there will not be a scalability issue. In general, the use of replay buffer (e.g., in the core set method) for continual learning is quite standard.\n\nMinor: The paper should have a conclusion section highlighting the main results and findings.", "summary_of_the_paper": "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.", "summary_of_the_review": "While the topic is interesting, the paper has limited novelty, unrealistic assumptions, and hardly interpretable results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes “Continual Federated Learning (CFL)” to study time evolving heterogeneous data. To do this the authors introduce time-drift to capture data heterogeneity across time. The authors also present some preliminary convergence results. Finally, the authors carryout numerical experiments in time-varying and heterogeneous settings. The reviewers identified the following strengths: (1) combining FL and CL is interesting, (2) the development of a new algorithm and providing some initial analysis is a good step. They also identified weaknesses as follows: (1) limited technical novelty as the use of replay buffer is quite standard, (2) cumbersome and not easy to interpret results, (3) lack of time evolving patterns with a common component (4) lack of different metrics that demonstrate how the algorithm is able to maintain accuracy as time-shifts occur, (5) lack of questionable assumptions. The reviewers had a very bimodal view advocating acceptance with a score of 8 and 2 advocating a rejection and neither group changed their opinion. Although the authors thorough responses did alleviate the concerns IMO. My own reading of the paper is that this is an interesting paper working on an emerging area. However, I must agree with some of the reviewers that the final conclusions are not easy to interpret, and the assumptions are not fully motivated. After this is carried out, I think the novelty of the paper can also become much clear. Therefore, I cannot strongly advocate acceptance of the paper in its currently state given the scores. However, I very strongly encourage the authors to submit to a future ML venue after addressing the remaining comments of the reviewers. I would also like to commend the authors for a very strong rebuttal sorry the final decision couldn’t be more favorable given the borderline ratings and the aforementioned issues.
Decision: Reject