Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning
Authors: Haibo Yang
Minghong Fang
Jia Liu
Venue: ICLR 2021 Poster (2021)
Keywords: Federated Learning
Linear Speedup
Partial Worker Participation

Abstract: Federated learning (FL) is a distributed machine learning architecture that leverages a large number of workers to jointly learn a model with decentralized data.  FL has received increasing attention in recent years thanks to its data privacy protection, communication efficiency and a linear speedup for convergence in training (i.e., convergence performance increases linearly with respect to the number of workers). However, existing studies on linear speedup for convergence are only limited to the assumptions of i.i.d. datasets across workers and/or full worker participation, both of which rarely hold in practice. So far, it remains an open question whether or not the linear speedup for convergence is achievable under non-i.i.d. datasets with partial worker participation in FL.  In this paper, we show that the answer is affirmative.  Specifically, we show that the federated averaging (FedAvg) algorithm (with two-sided learning rates) on non-i.i.d. datasets in non-convex settings achieves a convergence rate $\mathcal{O}(\frac{1}{\sqrt{mKT}} + \frac{1}{T})$ for full worker participation and a convergence rate $\mathcal{O}(\frac{\sqrt{K}}{\sqrt{nT}} + \frac{1}{T})$ for partial worker participation, where $K$ is the number of local steps, $T$ is the number of total communication rounds, $m$ is the total worker number and $n$ is the worker number in one communication round if for partial worker participation. Our results also reveal that the local steps in FL could help the convergence and show that the maximum number of local steps can be improved to $T/m$ in full worker participation. We conduct extensive experiments on MNIST and CIFAR-10 to verify our theoretical results.

Published as a conference paper at ICLR 2021
ACHIEVING LINEAR SPEEDUP WITH PARTIAL WORKER PARTICIPATION IN NON-IID FEDERATED LEARNING
Haibo Yang, Minghong Fang. and Jia Liu Department of Electrical and Computer Engineering
The Ohio State University Columbus, OH 43210 USA (yang. 5952, fang. 841, 1iu.1738 eosu. edu
ABSTRACT
Federated learning (FI.) a distributed machine learning architecture that leverages large number of workers to jointly learn model with decentralized data. FI. has received increasing attention in recent years thanks to its data privacy protection, communication efficiency and linear speedup for convergence in training (i.e., convergence performance increases linearly with respect to the number workers). However, existing studies linear speedup for convergence the assumptions of i.i.d. datasets across workers and/or full worker participation, both of which rarely hold in practice. So far, it remains open question whether or not the linear speedup for convergence is achievable under non-i.i.d. datasets with partial worker participation in FL. In this paper. we show that the answer is affirmative. Specifically, we show that the federated averaging (FedAvg) algo- rithm (with two-sided learning rates) on non-i.i.d. datasets in non-convex settings achieves a convergence rate O( 1
only limited
/KKT + )) for full worker participation and a
VnT 7) for partial worker participation, where K is the number of local steps, T is the number of total communication rounds, m is the total worker number and is the worker number in communication round if for partial worker participation. Our results also reveal that the local steps in FL could help the convergence and show that the maximum number of local steps be improved to T /m in full worker participation. We conduct extensive experiments on MNIST and CIFAR-10 10 to verify our theoretical results.
convergence rate O( /KK
INTRODUCTION
Federated Learning (FL) is distributed machine learning paradigm that leverages large number of workers to collaboratively learn model with decentralized data under the coordination of centralized server. Formally, the goal of FL is solve an optimization problem, which can be decomposed as:
m
min f(x) ZERO
Fi(x),
m
where Fe(x:) A BE.-D, [F, (x.{,) is the local (non-convex) loss function associated with local data distribution D; and m is the number of workers. FL allows large number of workers (such as edge devices) participate flexibly without sharing data, which helps protect data privacy. However, also introduces two unique challenges unseen in traditional distributed learning algorithms that are used typically for large data centers:
don--indepennee---detttillll-l- distrrbbbed (non-ii.d.) datasets across workers (data hetero- geneity): In conventional distributed learning in data centers, the distribution for each worker's local dataset can usually be assumed to be i.i.d., i.e., D; D, Ví E {1,..., m). Unfortunately, this assumption rarely holds for FL since data cireumstances, i.c., D, + Dj. for + j. It will be seen later that the non-i.i.d assumption imposes significant challenges in algorithm design for FL. and their performance analysis.
generated locally the workers based on their

---

Published as a conference paper at ICLR 2021
Tary-ng partial worker participation (systems non non-stationarity): With the flexibility for workers' participation in many scenarios (particularly in mobile edge computing), workers may randomly join or leave the FL system at will, thus rendering the active worker set stochastic and time-varying across communication rounds. Hence, it is often infeasible to wait for all workers' responses as in traditional distributed learning, since inactive workers stragglers will significantly slow down the whole training process, As result, only a subset of the workers may be chosen by the server in each communication round, i.e., partial worker participation.
In recent years, the Federated Averaging method (FedAvg) and its variants (MMMahan et al. 2016 Li et al. 2018; Hsu et al., 2019; Karimireddy et al.) 2019] Wang et al. (019a) have emerged as prevailing approach for FL. Similar to the traditional distributed learning, FedAvg leverages local computation at each worker and employs a centralized parameter server to aggregate and update the model parameters. The unique feature of FedAvg is that each worker runs multiple local stochastic gradient descent (SGD) steps rather than just one step as in traditional distributed learning between two consecutive communication rounds. For i.idd datasets and the full worker participation setting, Stich (2018) and Yu et al.] (2019b) proposed two variants of FedAvg that achieve a convergence rate of OlTk VmKTT with bounded gradient assumption for both strongly convex and non- convex problems, where m the number of workers, K' is the local update steps, and T is the total communication rounds. [Wang& & Joshi (2018) and [Stich & Karimireddy (2019) further proposed improved FedAvg algorithms to achieve an ( VmKTT convergence rate without bounded
gradient assumption. Notably, for a sufficiently large T. the above rates become O V(V which implics linear speedup with respect to the number of workers This lincar speedup is highly desirable for an FL algorithm because the algorithm is able to effectively leverage the massive parallelism in large FL system. However, with non-i.i.d. datasets and partial worker participation in FL., a fundamental open question arises: Can we still achieve the same linear speedup for convergence, i.e., O( ((TKKT) ), with non-i.idd. datasets and under either full or partial worker participation?
In this paper, we show the answer to the above question affirmative. Specifically, we show that a generalized FedAvg with two-sided learning rates achieves linear convergence speedup with non-i.i.d datasets and under full/partial worker participation. We highlight our contributions as follows:
For non-convex problems, show that the convergence rate of the FedAvg algorithm on non-i.i.d dataset are O / + +)) and O yR where n is the size of the partially participating worker set. This indicates that our proposed algorithm achieves linear speedup for convergence rate for a sufficiently large T. When reduced to the i.i.d. case, our convergence rate is O TK + <m ), which is also better than previous works. We summarize the convergence rate comparisons for both i.i.d. and non-i.i.d. cases in Table It is worth noting that our proof does not require the bounded gradient assumption. We note that the SCAFFOLD algorithm (Karimireddy al.) 2019) also achieves the linear speedup but extra variance reduction operations are required, which lead to higher communication costs and implementation complexity. By contrast, do not have such extra requirements in this paper.
VnT + ++) for full and partial worker participation, respectively,
In order to achieve a linear speedup, i.e., convergence rate O ( (mKKT) ) we show that the number of local updates K can be as large as T/m. which improves the T1/3 /mm result previously shown in Yu et al. (2019a) and Karimireddy et al. (2019). As shown later in the communication complexity comparison in Table 1 a larger number of local steps implies relatively fewer communication rounds, thus less communication overhead. Interestingly, our results also indicate that the number of local updates K does not hurt but rather help the convergence with a proper learning rates choice in full worker participation. This overcomes the limitation as suggested in Li et al. (2019b) that local SGD steps might slow down the convergence (O K ) for strongly convex case). This result also reveals new insights on the relationship between the number of local steps and learning rate.
'This rate also matches the convergence rate order of parallel SGD in conventional distributed learning. To attain accuracy for an algorithm, it needs take O(+) steps with convergence rate 0 ((+))) while needing O ((...)) steps the convergence rate is O 1 sense, one achieves linear speedup with respect the number of workers.
(mm)) (the hidden constant Big-O the same). In this
2

---

Published as a conference paper at ICLR 2021
Table I: Convergence rates of optimization methods for FL.
Partial Worker
Convergence Rate
Communication complexity
Dataset
Algorithm
Convexity?
Stich1
SC
x
mnk
0
VMRT
MM
Yul
NC
X
mk
T
VIRKT
mk
mke
Wang
NC
x
0
VmKT
mke²
Stich2
NC
X
0
T
m
VmKT
m
mk?
This paper
NC
V
0 TK VmnTT
O 1
Rr mk?
Khaled
C
x
VITTT
mke
NON-
IID
Yu22
NC
X
0 T
TK
VmkT
0 m + mke)
Ke
Li
SC
0
Karimireddy
NC
0 T2/3
M VSKT
0 3/2 ske)
1 M
Karimireddy
NC
(
0 + mk2
VmkT
This paper*
NC
0
O mke
VmkT
Full gradients are used for each worker.
Local momentum is used at each worker.
A FedAvg algorithm with two-sided learning rates. M 0(1) OO(S)) )) S (S
for full (partial) worker participation.
The SCAFFOLD algorithm in Karimireddy al. (019)) for non-convex case.
The convergence rate becomes O + vK under partial worker participation.
VnT
Shorthand notation for references: Stich1 := Stich (2018), Yu2 := Yu al. (019b)) Wang: Wang & Joshi (2018). Stich2:= <Stchh & Karimireddy (2019); Khaled:=|Khaled: et al. (2019b). Yu2: Yu et al.
),), Li:= Li et al. (2019b), and Karimireddy: Karimireddy al. (2019)
Shorthand notation for convexity: SC: Strongly Convex, C: Convex, and NC: Non-Convex.
Notation. this paper, we let m the total number of workers and S, be the set of active workers for the t-th communication round with size [S, the number of local steps per communication round at each worker. We T be the number of total communication rounds. In addition, represent the parameter of k-th local step in the i-th worker after the 1-th communication. We use |l-ll2 to denote the 12 -orm.. For a natural number m,, we use [m] to represent the set [1,...,1))
for some E (0, m]. We use K to denote
use boldface to denote matrices/vectors. We let Hi
The rest of the paper is organized follows. In Section comparative perspectives. Section presents the convergence analysis for our proposed algorithm. Section DoctionAdisen discusses the implication of the convergence rate analysis. Section 5 presents numerical results and Section (oooonoocooo concuuds this paper. Due to space limitation, the details of all proofs and some experiments are provided in the supplementary material.
review the literature to put work in
RELATED WORK
The federated averaging (FedAvg) algorithm was first proposed by McMahan al. (2016) FL as heuristic to improve communication efficiency and data privacy. Since then, this work has sparked many follow-ups that focus on FL with i.i.d. datasets and full worker participation (also known as
LocalSGD Stich 2018 Yu et al. 2019b: Wang & Joshi 2018 Stich & Karimireddy 2019 Lin et al. 2018 Khaled et al. 2019a Zhou & Cong 2017)). Under these two assumptions, most of the theoretical works achieve linear speedup for convergence, i.e., O VmRTT for sufficiently large T, matching the rate of the parallel SGD. In addition, LocalSGD is empirically shown to be communication-effiian and enjoys better generalization performance (Lin et al.] (018). For comprehensive introduction to FL, we refer readers Li et al. (2019a) and Kairouz et al. (2019).
For simplicity and ease of presentation in this paper, we let [S We note that this is not restrictive condition and our proofs and results still hold for [S&] n, which he easily satisfied in practice.

---

Published as a conference paper at ICLR 2021
Algorithm I A Generalized FedAvg Algorithm with Two-Sided Learning Rates.
Initialize
for ( = 00 0,... , - do
The server samples subset St of workers with |St| = n. for each worker i E St in parallel do
X X for k = 0, ... K do
Compute unbiased estimate gi, VF St,b) VF
Local worker update: x1,K+1 Xi, 1),.gi,k.
end for Let A; = x2, x = I k== Ki Send A to the server. end for
KK1
At Server:
Receive i
Let A. = [9] Lies
Server Update: X++1 X2 + n Broadcasting X++1 to workers.
end for
For non-i.idd. datasets, many works (Sattler et 2019 Zhao et al. 2018 Li al. 2018 Wang et
2019a; Karimireddy et al. 2019 (Hung et al.) 2018: Jeong et al.) 2018) heuristically demonstrated convergence rate with full worker participation, many
the performance of FedAvg and variants. works (Stich et al. 2018: Yu et al. [2019a] Wang & Joshi 2018 Karimireddy et al. 2219 Reddi et al. 2020) can achieve linear speedup, but their convergence rate bounds could improved as shown in this paper. On convergence rate with partial worker participation.] [Li et al.) (2019b) showed that the original FedAvg can achieve (K/TT for strongly convex functions, which suggests that local SGD steps slow down the convergence in the original FedAvg. Karimireddy et al. (2019) analyzed generalized FedAvg with two-sided learning rates under strongly convex, convex and non-convex cases. However, shown in Table T none of them indicates that linear speedup is achievable with non-i.idd. datasets under partial worker participation. Note that the SCAFFOLD algorithm (Karimireddy al., 2019) can achieve linear speedup but extra variance reduction operations are required, which lead to higher communication costs and implementation complexity. In this paper, we show that this linear speedup can be achieved without any extra requirements. For more detailed comparisons and other algorithmic variants in FL and decentralized settings, we refer readers to Kairouz et al. 20119).
3 LINEAR SPEEDUP OF THE GENERALIZED FEDAVG WITH TWO-SIDED LEARNING RATES FOR NON-IID DATASETS
In this paper, we consider a FedAvg algorithm with two-sided learning rates as shown Algorithm I which is generalized from previous works (Karimireddy et al.) 2019 Reddi et al. 2020). Here, workers perform multiple SGD steps using a worker optimizer to minimize the local loss on its own dataset, while the server aggregates and updates the global model using another gradient-based server optimizer based on the returned parameters. Specifically, between two consecutive communication rounds, each worker performs K SGD steps with the worker's local learning rate Vız- We assume an unbiased estimator in each step, which is denoted by g = V ( (x local data sample for k-th steps after t-th communication round at worker i. Then, each worker sends the accumulative parameter difference A to the server. On the server side, the server aggregates all available Af-vluues and updates the model parameters with a global learning rate The FedAvg algorithm with two-sided learning rates provides a natural way to decouple the learning of workers and server, thus utilizing different learning rate schedules for workers and the server. The original FedAvg can be viewed as a special case of this framework with server-side learning rate being one.
ei ( St, where E is a random
In what follows, we show that a linear speedup for convergence is achievable by the generalized FedAvg for non-convex functions on non-i.i.d. datasets. We first state our assumptions as follows.
4

---

Published as a conference paper at ICLR 2021
Assumption 1. (L-Lipschitz Continuous Gradient) There exists constant L > 0, such that [[V (Flly) & L||x yll, Vx. E R and E [m].
Assumption 2. (Unbiased Local Gradient Estimator) Let Et be random local data sample in the I-th step at the i-th worker. The locul gradient estimator is unbiased, i.e., (x., [t) (x.)). di {mm] where the expectation over all local datasets samples.
Assumption 3. (Bounded Local and Global Variance) There exist two constants d 0 and ag >
such that the variance of each local gradient estimator is bounded by EIII (x,, E.) ( [13] I
L. Vi [m]) and the global variability of the local gradient of the cost function is bounded by (x,,). [(xx))] - o vi E [m], Vt.
The first two assumptions are standard in non-convex optimization (Ghadimi Lan
2013 Bottou
et al. 2018). For Assumption [3] the bounded local variance is also standard assumption. We use universal bound ag to quantify the heterogeneity of the non-i.i.d. datasets among different workers. In particular, og 0 corresponds i.i.d. datasets. This assumption also used in other works for FL under non-i.i.d. datasets (Reddi et al., [2020] Yu et al. 2019b Wang et al. 2019b) as well as in decentralized optimization (Kairouz et al.) 2019). It worth noting that we do not require a bounded gradient assumption, which is often assumed in FL optimization analysis.
3.1 CONVERGENCE ANALYSIS FOR FULL WORKER PARTICIPATION
In this subsection, we first analyze the convergence rate of the generalized FedAvg with two-sided learning rates under full worker participation, for which we have the following result:
Theorem 1. Let constant local and global learning rates πu and 17 be chosen as such that nL S 8LK and mL KL. Under Assumptions
1
3 and with full worker participation, the sequence of outputs {xr} generated by Algorithm satisfies:
fo f. CHMLKT + 4,
min f(IV EE
where 2 1 Lyvi 2m of, +
5K (a + 6Ko'))), is a constant, fo 2 f(xo), fo 2 fxx.) and the 2
expectation is over the local dataset samples among workers.
fo=f=- expi KT as T increases and a constant term & whose size depends on the problem instance parameters and is independent of T. The vanishing term's 's decay rate matches that of the typical SGD methods.
Remark The convergence bound contains two parts: a vanishing term
Remark 2.
The first part of & (i.e., Love ot) ) is due the local stochastic gradients each worker, 2m
which shrinks at rate m as increases. The cumulative variance of the K local steps contributes to
the second term in (i.e., 5K 1.2 2 (oz + 6KoE)), which is independent of m and largely affected by the data heterogeneity. To make the second part small, an inverse relationship between the local learning rate and local steps should satisfied, i.e., 17 ((+), ). Specifically, note that the global and local variances are quadratically and linearly amplified by K. This requires sufficiently small m to offset the variance between two successive communication rounds to make the second term in & small. This is consistent with the observation in strongly convex FL that a decaying learning rate is needed for FL to converge under non-i.i.d. datasets even if full gradients used in each worker (Li note that our explicit inverse relationship between 7)r and K in the above
al. 2019b). However, is new. Intuitively, the K local steps with a sufficiently small v)r, can be viewed as one SGD step with a large learning rate.
With Theorem D we immediately have the following convergence rate for the generalized FedAvg algorithm with a proper choice of two-sided learning rates:
Corollary 1. Let nL
VTKL and n =
= Vmm. The convergence rate of the generalized FedAvg
algorithm under full worker participation is min
= VmKT +
The generalized FedAvg algorithm with two-sided learning rates can achieve linear speedup for non-i.i.d datasets, i.e., a O 1 mm convergence rate as long as T 2 mK. Although many works have achieved this convergence rate asymptotically, we improve the maximum number
Remark 3.
5

---

Published as a conference paper at ICLR 2021
of local steps K to T T/m. m. which is significantly better than the state-of-art bounds such T /3/3/a /m shown in (Karimireddy et al. [019 Yu et al. (2019a) Kairouz et al. 2019). Note that a larger number of local steps implies relatively fewer communication rounds, thus less communication overhead. See also the communication complexity comparison in Table For example, when T = 10 and m 100 (as used in (Kairouz al. 2.19)), the local steps in our algorithm is K I T/m 10
T = 1 means that no extra local steps can be taken to reduce communication costs.
However, K I
Remark 4. When degenerated to the i..d. case (og 0). the convergence rate becomes O VmKT ), which has a better first term the bound compared with previous work as shown in Table
3.2 CONVERGENCE ANALYSIS FOR PARTIAL WORKER PARTICIPATION
Partial worker participation in each communication round may be more practical than full worker participation due to many physical limitations of FL. in practice (e.g., excessive delays because of too many devices to poll, malfunctioning devices, etc.). Partial worker participation
also accelerate the training by neglecting stragglers. We consider two sampling strategies proposed by Li et al. (2018) and Li al. (2019b). Let S, be the participating worker index set communication round f with |S, n. VE. for some n E (0,m), S. is randomly and independently selected either with replacement (Strategy 1) or without replacement (Strategy 2) sequentially according to the sampling probabilities Vi E [m]. For each member in S,, we pick a worker from the entire set [m]] uniformly at random with probability p: = m. Vi [m]] That is, selection likelihood for anyone worker Sc is psp= Then we have the following results:
Theorem 2. Under Assumptions 3 with partial worker participation, the sequence of outputs {xx} generated by Algorithm with constant learning rates and TJr satisfies:
So KT + +
min B[IV EE
where fo = f(xo), f. fxx),, and the expectation over the local dataset samples among workers.
For sampling Strategy 1, let 1 and be chosen as such that п S SLK. MTLKL < n=1 and 30K?n2 12 Lone (90K3 1 + +3K) < 1. It then holds that:
LAME 2n
of, + 3LKMLL
5k L2
15K2m L3
(0). + 6ko2d
o +
2n
2
2n
For sampling Strategy 2, let n and mI. be chosen as such that nu S BLK
MLLL S
n(m-1) and m(n-1)
10.2nj - LAnL m-n (90K 1 L2 + 3K) < 1. It then holds that:
ni
A
LameL of, +3LK3mm 2n(m 2n
m n
5 L2
+15K mI
m n2
(0 -
(oi+6Ko7))
2
2n(m -
we immediately have the following convergence rate for the generalized FedAvg algorithm with a proper choice of two-sided learning rates:
From Theorem 2
VTKL and 1 = Vnn. The convergence rate of the generalized FedAvg algorithm under partial worker participation and both sampling strategies are:
Corollary 2. Let iiL
min EE V S so o ( (UTTT ++++)
Remark 5. The convergence rate bound for partial worker participation has the same structure but with larger variance term. This implies that the partial worker participation through the uniform sampling does not result in fundamental changes convergence (in order sense) except for an amplified variance due to fewer workers participating and random sampling. The intuition is that the uniform sampling (with/without replacement) for worker selection yields a good approximation of the entire worker distribution in expectation, which reduces the risk of distribution deviation due to the partial worker participation. As shown in Section 5 the distribution deviation due to fewer worker participation could render the training unstable, especially in highly non-i.i.d. cases.

---

Published as a conference paper at ICLR 2021
The generalized FedAvg with partial worker participation under non-i..d. datasets can still achieve a linear speedup O v addition, when degenerated i.idd case (og = 0), the convergence rate becomes O VnkT
Remark 6.
VnI with proper learning rate settings as shown in Corollary In
Remark 7. Here, we let |S,] only for ease of presentation and better readability. We note that this is not a restrictive condition. We can show that |S,] = n can be relaxed to | 2 n. Vt E [T] and the same convergence rate still holds. In fact, our full proof in Appendix A.2 is for [S n.
DISCUSSION
In light of above results, in what follows, we discuss several insights from the convergence analysis:
We show that the generalized FedAvg algorithm with two-sided learning rates achieve linear speedup, i.e., O( /KKT) convergence rate with a proper choice of hyper- parameters. Thus, works well in large Fl. systems, where massive parallelism can be leveraged to accelerate training. The key challenge in convergence analysis stems from the different local loss functions (also called "model drift" in the literature) among workers due to the non-i.i.d. datasets and local steps. As shown above, containing a vanishing term and a constant term (the constant term is similar to that of SGD). In contrast, the constant term in SGD is only due to the local variance. Note that, similar to SGD, the iterations do not diminish the constant term. The local variance oî, (randomness of stochastic gradients), global variability & (non-i.i.d. datasets), and the number of local steps K (amplification factor) all contribute to the constant term, but the total global variability in K local steps dominates the term. When the local learning rate 7 is set to an inverse relationship with respect to the number of local steps K, the constant term is controllable. An intuitive explanation is that the K small local steps can be approximately viewed as one large step in conventional SGD, So this speedup and the more allowed local steps can be largely attributed to the two-sided learning rates setting.
Convergence Rate:
obtain a convergence bound for the generalized FedAvg method
Number of Local Steps: Besides the result that the maximum number of local steps is improved to K < T/m, we also show that the local steps could help the convergence with the proper hyper- parameter choices, which supports previous numerical results (McMahan et al. 2016 Stich 2018
Lin et al. 2018) and is verified in different models with different non-i.i.d. degree datasets in Section 5 However, there are other results showing the local steps slow down the convergence (Li et al. 2019b).
We believe that whether local steps help or hurt the convergence in FL worths further investigations.
Number of Workers: We show that the convergence rate improves substantially as the the number of workers in each communication round increases. This is consistent with the results for i.idd. cases in |tich (2018). For i.i.d. datasets, more workers means more data samples and thus less variance and better performance. For non-i.i.d. datasets, having more workers implies that the distribution of the sampled workers is a better approximation for the distribution of all workers. This is also empirically observed in Section 5 On the other hand, the sampling strategy plays important role in non-i.i.d. case as well. Here, we adopt the uniform sampling (with/without replacement) to enlist workers to participate in FL. Intuitively, the distribution of the sampled workers' collective datasets under uniform sampling yields good approximation of the overall data distribution in expectation.
Note that, in this paper, we assume that every worker is available participate once being enlisted. However, this may not always be feasible. In practice, the workers need to be in certain states in order to be able to participate in FI. (e.g., in charging or idle states, etc. (Fichner et al. 2019)). Therefore, care must be taken in sampling and enlisting workers in practice. We believe that the joint design of sampling schemes and the generalized FedAvg algorithm will have a significant impact on the convergence, which needs further investigations.
5 NUMERICAL RESULTS
We perform extensive experiments to verify our theoretical results. We use three models: logistic regression (LR), a cully-connected neural network with two hidden layers (2NN) and a convolu- tion neural network (CNN) with the non-i.i.d version of MNIST (LeCun et al. 1998) and one ResNet model with CIFAR-10 (Krizhessky et al. 2009). Due to space limitation, we relegate some experimental results in the supplementary material.
7

---

Published as a conference paper at ICLR 2021
2.5
2,5
255
Icn max
2.0
2.0
2.0
2.5
1.5
2.5
Traising
Trainin
Training
0.5
0.5
0.5
0.0
60
20
100
0.0
60
Communioon latton Round
Commun cation Round
Commun cattinniinnnnnn Round
1.0
1.0
0.8
0.8
Tea: Accunicy
Test Accuracy
0.6
16xt
noree 100
0.4
04
noree Humb
3
0.2
80
100
60
Commun Cation Round
Commun cation Round
Commun cation Round
(a) Impact of non-i..d. datasets.
(b) Imppct of worker number.
(c) Impact of local steps
Figure I: Training loss (top) and test accuracy (bottom) for the 2NN model with hyper-parameters setting: local learning rate 0.1, global learning rate 1.0: (a) worker number 100, local steps 5 epochs; (b) local steps 5 epochs; (c) digits in each worker's 's dataset.
In this section, we elaborate the results under non-ii.d MNIST datasets for the 2NN. We distribute the MNIST dataset among m = 100 workers randomly and evenly in a digit-based manner such that the local dataset for each worker contains only certain class of digits. The number of digits in each worker's dataset represents the non-i.i.d. degree. For digits_ _igiits_O,_____ each worker has training/testing samples with ten digits from 0 to 9, which is essentially samples only associated with one digit, which leads to highly non-i.i.d. datasets among workers. For partial worker participation, we set the number of workers n 10 in each communication round.
i.i.d. case. For digits_ 1, each worker has
Impact of non-i.idd datasets: As shown in Figure D a), for the 2NN model with full worker participation, the top-row figures are for training loss versus communication round and the bottom- row are for test accuracy versus communication round. We can see that the generalized FedAvg algorithm converges under non-i.i.d. datasets with a proper learning rate choice in both cases. For five digits (digits_ 5) in each worker's dataset with full (partial) worker participation in Figure [ a). the generalized FedAvg algorithm achieves a convergence speed comparable to that of the i.i.d. case ddigits_10), Another key observation is that non-i.i.d. datasets slow down the convergence under the same learning rate settings for both cases. The higher the non-i.i.d. degree, the slower the convergence speed. As the non-i.i.d. degree increases (from case digits_ 10 to case digits 1), it is obvious that the training loss is increasing and test accuracy is decreasing. This trend is more obvious from the zigzagging curves for partial worker participation. These two observations can also be verified for other models as shown in the supplementary material, which confirms our theoretical analysis.
Impact of worker number: As shown in Figure we compare the training loss and test accuracy between full worker participation n = 100 and partial worker participation n = 10 with the same hyper-parameters. Compared with full worker participation, partial worker participation introduces another source of randomness, which leads to zigzagging convergence curves and slower convergence. This problem is more prominent for highly non-i.i.d datasets. For full worker participation, it can neutralize the the system heterogeneity in each communication round. However, it might not be able to neutralize the gaps among different workers for partial worker participation. That is, the datasets' distribution does not approximate the overall distribution well. Specifically, it is not unlikely that the digits in these datasets among all active workers are only a proper subset of the total 10 digits in the original MNIST dataset, especially with highly non-i.i.d. datasets. This trend is also obvious for complex models and complicated datasets as shown in the supplementary material. The sampling strategy here is random sampling with equal probability without replacement. In practice, however, the actual sampling of the workers in FL could be more complex, which requires further investigations.
8

---

Published as a conference paper at ICLR 2021
Impact of local steps: One open question of FL is that whether the local steps help the convergence or not. In Figure [[]], we show that the local steps could help the convergence for both full and partial worker participation. These results verify showed that the local steps may hurt the convergence, which was demonstrated under unbalanced non-i.i.d. MNIST datasets. We believe that this may be due to the combined effect of unbalanced datasets and local steps rather than just the use of local steps only.
theoretical analysis. However, [i al. (2019b)
Table Comparison with SCAFFOLD.
SCAFFOLD Communication cost (MB)
This paper
IID or Non-IID
Worker selected
Dataset
Model
# of Round
Wall-clock time (6)
Round
Communication cost (MB)
Wall-clock (6)
Logistic
0.36
0.22
9.12
0.56
CNN
26.64
3
13.32
1.57
IID
Logistic
0.60
0.53
5
0.30
0.42
2NN
15.20
1.51
8
12.16
1.49
CNN
8.88
0.79
1
4.44
0.50
MNIST
Lngistie
1.68
1.48
14
0.84
1.16
T1 10
2NN
14
42.55
4.23
14
21.28
2.46
Non IID
CNN
14
124.34
11.12
10
44.41
4.92
Lugistic
7
0.84
0.72
11
0.66
0.91
== 100
2NN
7
21 21.28
2.11
17
25.84
3.16
CNN
150.98
13.50
7
31,08
3.51
ITD
Resnet18
9548.07
583.24
44
3751.03
256.63
358.22
Bandwidth 20MR/s.
Comparison with SCAFFOLD: Lastly, we compare with the SCAFFOLD algorithm (Karimireddy ct al. 2019) since also achieves the same linear speedup effect under non-i.i.d. datasets. We compare communication rounds, total communication load, and estimated wall-clock time under the same settings to achieve certain test accuracy. and the results are reported in Table The non-i.i.d. dataset is digils_2 22 and the i.i.d. dataset is digils_Ii ___ The learning rates are TJr. 0.1, 1.0, and number of local steps K epochs. We set the target accuracy = 95% for MÄIST and e 75% for CIFAR-10. Note that the total training time contains two parts: i) the computation time for training the local model at each worker and ii) the communication time for information exchanges between the workers and the server. We assume the bandwidth 20 MB/s for both uplink and downlink connections. For MNIST datasets, we can see that our algorithm is similar to or outperforms SCAFFOLD. This is because the numbers of communication rounds of both algorithms are relatively small for such simple tasks. For non-i.i.d. CIFAR-IO the SCAFFOLD algorithm takes slightly fewer number of communication rounds than our FedAvg algorithm achieve 75% thanks to its variance reduction. However, it takes more than 1.5 times of communication cost and wall-clock time compared those of our FedAvg algorithm. Due space limitation, we relegate the results of time proportions for computation and communication to Appendix B (see Figure
6 CONCLUSIONS AND FUTURE WORK
In this paper, we analyzed the convergence generlized FedAvg algorithm with two-sided learning rates non-i.i.d. datasets for general non-convex optimization. We proved that the generalized FedAvg algorithm achieves a linear speedup for convergence under full and partial worker participa- tion. We showed that the local steps in FL could help the convergence and we improve the maximum number of local steps to T/m. While our work sheds light on theoretical understanding of FL, it also opens the doors to many new interesting questions FL, such how sample optimally in partial worker participation, and how to deal with active participant sets that are both tine-varying and size-varying across communication rounds. We hope that the insights and proof techniques in this paper can pave the way for many new research directions in the aforementioned areas.
ACKNOWLEDGEMENTS
This work is supported in part by NSF grants CAREER 193-19,4884, ONR grant ONR N00014-17-1-2411,, and Google Faculty Research Award.
CIF-21 10252, ECCS- 1818791,

---

Published as a conference paper at ICLR 2021
REFERENCES
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning, Siam Review, 60(2):223-3111 2018.
Hubert Eichner, Tomer Koren, H Brendan McMahan, Nathan Srebro, and Kunal Talwar. Semi-cyclic stochastic gradient descent. arXiv preprint /904: 2019.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, (3(4):2341-2366 2013.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv::909.000
2019.
Li Huang, Yifeng Yin, Zeng Fu, Shifa Zhang. Hao Deng, and Dianbo Liu. Loadaboost: Loss-based adaboost federated machine learning on medical data. arXiv preprint arXiv:1811. 1...:2291..129,, 2018.
Eunjeong Jeong. Seungeun Oh, Hyesung Kim, Jihong Park, Mehdi Bennis, and Seong- Kim. ciaauumiatiion-effiienn on-device machine learning: Federated distillation and augmentation under non-iid private data. arXiv preprint arXiv: /8/ 1. 1479, 2018
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977, 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for on-device federated learning. arXiv preprint arXiv: 190.v.191, 2019.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Better communication complexity for 2019a.
local sgd. arXiv preprint
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local gd on heteroge- neous data. arXiv preprint
2019b..
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-235 1998.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith.
Federated optimization in heterogeneous networks. arXiv preprint arXiv:7812.06122 2018.
Tian Li, Anit Kumar Sahu, Amect Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. arXiv preprint /2tV:/990..07888 2019a.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. arXiv preprint arXiv:1907.02118 2019b.
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, 2018.
local sgd. arXiv preprint 1808.00
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communication-effiiceee learning of deep networks from decentralized data. arXiv preprint wxXi::602.006622 2016.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Koneeny, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00225.. 2020.
Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojeiech Samek. Robust and communication-cffiiii federated learning from non-iid data. IEEE transactions neural networks and learning systems, 2019.
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv:1805.0976 2018.
10

---

Published as a conference paper at ICLR 2021
Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv preprint wwX.iv:909.0553.0 2019.
Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Advances in Neural Information Processing Systems, pp. 4447-4458, 2018.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-effcceent sgd algorithms. arXiv preprint 1r0iv:/808.07555 2018.
Jianyu Wang. Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving
conmunication-efficee distributed sgd with slow momentum. arXiv preprint 1r100:1910.00643, 2019a.
Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems. IEEE Journal on Selected Areas in Communications, 1205):1205-110
2019b.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis communication efficient momentum sgd for distributed non-convex optimization. arXiv preprini arXiv: 1905.03817 2019a.
Hao Yu, Sen Yang. and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp.
2019b.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint arXiv: 00582, 2018.
Fan Zhou and Guojing Cong. On the convergence properties of k-step averaging stochastic gradient descent algorithm for nonconvex optimization. arXiv preprint arXiv:1708.01012 2017.

---

Published as a conference paper at ICLR 2021
A APPENDIX I: PROOFS
In this section, we give the proofs in detail for full and partial worker participation in Scction A. and Section A.2 respectively.
A.1 PROOF OF THEOREM II
Theorem Let constant local and global learning rates qu and ij be chosen as such that TJ. S 8LK 3 and with full worker participation, the sequence of outputs
1 and mm I KT,; Under Assumptions 3
{xx} generated by Algorithm satiifies:
fo f. + Φ
min f(IV EE[T]
CTMLKT
where 2 1[ Lome of. 2m expectation is over the local dataset samples among workers.
5K + 6Koe),, i constant, fo - f(xo). fo & f(x.) and the 3
Proof. For convenience, we define A,
A H E= Ai. Under full device participation (i.c., St A.
[m]), it is clear that A, -. m A
Due to the smoothness Assumption taking expectation of [(x++1) over the randomness at communication round we have:
L
[x & f(x)) + (V Bx - xx1) +
- Er 1 [||x[+11 -xel1
2
= E, mm.
177 KV 1
E,
= [10
1E,,11 117
(1)
Note that the term A, in T can be bounded as follows:
A (x)())), E, [ + KVF(()))
K-1
Vf(()), EE
nggiA + ML +LKVf(x)
K-1
V)(x)). E.
Mr VF M Σ v Fi
(x:)
1=1
k=
K-1
(VVKKVf(X)).
VI
-
mVK
(11) K
M1
E,
K-1
-
-F(())
7T
E,
K
(x k))
2
2Km²
2Km²
1==0
(a2) m
[[(x))]1+++
ML
K-1
(
E,
K
2m
2Km
i=1 K=U
i= 1==
(a3) n1 K
|| | + M1 T.2
m
m
Eallx -
E,
V.
2m
2Km²
R=0
(o1)
S Sm1
1
5K
(0z +KKo2)
ML
E
K-1
V
V
2
2km²
(2)
12

---

Published as a conference paper at ICLR 2021
where (al) follows from that (x,y) =|||x||² + ||yll - ||x - yl for x - (/nKV((()))) and
./TE E E Ek= (VF) (x:(x,)), (a2) is due that E|l|=1 + xn [|] -
y myK
nB[l|z1 + ................................ + | |2 (a3) is due to Assumption | and (a4) follows from Lemma
The term A2 in I can be bounded as:
A2
E, A |
1 Σ
E
A
R
Σ
4
m
ni
K
By
m
k=
(a5) VL
m
K
2 E m²
m K-1
E,
(gi,
V ))
Σ
V (x
m²
(a6) Kni,
Vi m
K
- 0
+
E
V
F.
(x²,))
k.
(3)
k=0
where (a5) follows from the fact that |||[x|1] to the bounded variance assumption in Assumption 3 and the fact that B[[|=] + + 2nll3 =
E. [[[]]|]] [|E[x]]| [12] and (a6) is due
||||2|||2 + ... + || ||] if z/ss are independent with zero mean and E(g', = (.
Substituting the inequalities in of A and 3 of Ag into inequality T we have:
T.
Eff((x+a)) (
E + t KV f > 2 1.1
A.
A2
LK
S sxx)) MLL K 1/ [3)
OL
2m
5 2 1
K-1 m
(0 + (Kog)) (
JE
ΣΣ (F((
2Km²
2m²
(07)
L. oi,
5n 5n (o7+6Koz)
2 f(x.) - 1171 K -5K2 (xx,)))
2m
2
(08)
LKn2ni
Kn
L.
< f(x)) CTML K {\) )2
2m 03, + 2
(o (Koo)
where (a7) follows from
DUL Ikm
Lni
2 0 if m7 S KI. (a8) holds because there exists a
2
constant c > satisfying ( 15 L2) > 0 mI V30KL'
Rearranging and summing from / - =0,... 0,..., - 1, we have:
LimE 2m
5K L2
cmL < f(xo) f(XT) T(MME)
02 +
(o +Kog)
which implies.
fo - fo
min E (
<
+ +.
CqpL KT
where +- !! Lome of,
5K L2
(o 6Kog))
This completes the proof.
13

---

Published as a conference paper at ICLR 2021
A.2 PROOF OF THEOREM 2
Theorem 2. Under Assumptions 73 with partial worker participation, the sequence of outputs with constant learning rates and TJr. satisfies:
{xa} generated by Algorithm 7
fo fo + +
min BIIVI((X))12 tE(T]
CIpTL KT CT
where To = [(x)), S. = f(x.). and the expectation over the local dataset samples canong workers.
For sampling Strategy 1, let 1 and nr be chosen as such that o S ELK WA KT. < 2=1 and 30K²n
Lana (90K3) L + +3K) < 1. then holds that:
LAME of. + 3LKYI o + (5Kn 15K 15K 2n
107 + 6Koz)
2n
2
2n
For sampling Strategy let n and nT be chosen as such that au S
SLK MLKL
1
n(m-1) and m(n-
10 12 Lumi, 1[m-1] (90K3, L + 3K) 1. It then holds that:
LAME of +3.43K 2m(m 2n
m n 0
5K 5k L
+15 mL
2n(m (0) (ok+6K08)
m 12
2
Proof. Let A, be defined the same in the proof of Theorem Under partial device participation, and |St] = n)). The random-
note that A. + Ar (recall that A, Σx Ai. A, E, Ai. ness for partial worker participation contains two parts: the random sampling and stochastic gradient. We still use [. represent the expectation with respect to both types of randomness.
Due to the smoothness assumption Assumption ness at communication round t:
taking expectation f(x+11) over the random-
-/2
L. Bxllxx++1 - xx
E Ef s f(x:) + (V,, E, - x:l)
2
L
=((x)) + (V.((, +mnKVJ(xx) -MIKKV((xx)) + クタ [1
L
+ 2²n² E|
=
AC
(4)
The term A in 4 can be bounded as follows: Since Es, [A = Ai due to Lemma for both sampling strategies, have the same bound in inequality for Ai:
5K2 L2
A s
2 + 15K2)11)))V<(0))1
(oī + +KKa))
K
ML
E,
V
F
(F
(5)
2Km
1=1
k=0
For strategy 1:
We can bound A' in (4) as follows.
Note S, is an index set (multiset) for independent sampling (equal probability) with replacement in which some elements may have the same value. Suppose S, (1..... [41....,b).
4.).
1 = E, ||| 11
L 71
Σ
14

---

Published as a conference paper at ICLR 2021
Y1 Σ
Br
K
Kー 1
'1
(b1)
(x
||
# E.
Σ
V F. (x 1=0
72
(b2) 02
Km
Ex
n
where (61) follows from the fact that ||||||| = - [[x]|[]+ + ||[|||]||] +|||||]]]1 and (62) is due the
bounded variance assumption 3 and [|] + ... + xn1l S nB][] + +...- + || [..
By letting t.
K-1
(x(.)))
). we have:
E2
Vi. (x42))
-Ee
t1
1=
==1
[t,
11? +
Σ
(teso Ris)
(h3)
E7,
|tt 112
+ +nnn ((tt.,ttts))
n
||tz|l +
n(n 1)
(ti.
m
{.Emmm]
n(n 1)
||t:||
t |1?
m
m² 2
where (b3) is due to the independent sampling with replacement.
So bound A²e follows.
A² E, |4|1
<
Kn 2
+
TT.
Er t;
(n - 1um
E.
Σ t;
vn
(6)
mnn
n
For t;, we have:
K
Σ E
1
=
E
V VF(()- ((xx)>v((xx))) 7
mm
(h4)
K
< 3KL
E Ex - x111 + 33mK2 +
2m
0
(65) < 15mk 3
+ 3mk 333 +3m om
where (64) is due to the fact that [E[| + +... 1 < nL x + + ||x,,1 Assumptions
a and (b5) follows from Lemma 2
Substituting the inequalities in 5 of A and 6 of A' into inequality have:
15

---

Published as a conference paper at ICLR 2021
L
E. [x]s(x++1]] S -(x (V (. /4
""² B.IlA.117
Ai
A
K( 1
5nk miiLL
I f(x)) 1771, 'm,,
15K2 1|
+
(0), + 6Ko2)
2
2
+ (n 1)
LK
Lnpnn qz.
Eg
Σ
41
0
Σ Ee|t,
2m22
2Km²
2n
2mn
(b6)
5nk L²
(xx) 1871. K[2 1 15K2ni V
(oz + 6Kog)
LKn2nn.
Li
07.
+
E |1
2n
2mn
(87)
f(x1) mm 1 15K22ni1'"
LmMe (90K 13 1/ + (33))
2n
K 1.2 15k 1,31p
T.K1p' o7,
3K
(o7.+6Ko))
2n
2n
2n
(18)
L
3K=LIj"
S ((x)) - capi. K| V (x
0
+
2
2n
2n
5K L
15K
+ mMLK
(0l +6Ko)),
(8)
2
2n
where (66) follows from (n-1))apm
2km S Of S n_1 (b7 jis due to incquality 7 and
2m2n
(b8) holds since there exists constant such that 1 15K "1 12 2n
Lone (90K + +3K))
e > 0 if 30K?
I n2 Lypr 100K3II21) + 3K) 1.
Note that the requirement of |S,] communication round.88j i
be relaxed to |S| With pa 2 workers in t-th
LK
3KL
[x(((x(+1) S f(x.) - capL K (Xx)(()))
2pt
2pt
15
1?
15Knin
m K
+
(o] + +6K02)
2
2pt
LK
3K
S f(x.) - capir K KIV (xx)))++
0
2
0G
2n
2n
5Knj. L2
15K
MMLK K
(oî + -KKo))
2n
That is, the same convergence rate can be guaranteed if at least n workers in each communication round (no need to be exactly n).
Rearranging and summing from t 0,.... . - 1, we have the convergence for partial device participation with sampling strategy as follows:
fo - f. CTJTi KT + 4,
min E fxx |12) T
where +
[ Lyne 0f, + 3K Lapi 2n
o7 +
5K L2
15K m 2n
(o7, + 6Koz)) and i constant.
For strategy 2: Under the strategy of independent sampling with equal probability without replace- ment. We bound A, as follows.
A₂ = E, 1|
1 Σ A
EE
iE
16

---

Published as a conference paper at ICLR 2021
S
1
Y22
Mii E s.JAi []
Ex
VZ E n
Mi E }t}}
K-1
Σ
181,
V 201
z n²
E
Σ
m
Mi E $.}
K-1
[ ]]
y=0
1=0
L
K-1
m
Ee n2
Σ
Pf E S
Σ
[x((x(,))
+
Mi S
Σ [F((
π1
j=0
1=
(b9)
LL
E,
K-1
Bi. VA((
1/]
+
E
Σ 1=1
Mi S.}
K-1 Σ
n2
1877
:=1
1=
(b10) Kn L
K-1
Σ
Pfi
E S
Σ
n2
1=0
where (b9) is due to the fact that B[| 11 + ... + +
12] =|]
+ +..... + | 12] if zis are
independent with zero mean, x; = gij - (xt,)) is independent random variable with mean zero and P(i E St} = . (b10) is due to bounded variance assumption in Assumption 3
Substituting the inequalities in of A and 9 of A into inequality (4)
we have:
L 2 ""
/1/ E,,,,,,,,,,,, + nr. KV f
I
A
A
LKn 07. +
K L2
vx(xx) - MLL
15K
(07 + -6K0%)
2n
2
Ln
K-1 Σ PfiE S.}
K-1 1 m
Er
Σ v((())))
TTLL
EE,
Σ
(.((
2n
2k
1=0
i=1
k=o
A'3
Then we bound A'g as follows.
By letting t; = E (x((x),)) ). we have:
E. 1t:11 < 15mk (o + 6Ko2) + (90mK*12 + +3mk3 ([I33)/V[((x,))] + 33m 3mk220g
It then follows that
||t:|12
+
< tr ti >
1 [m]
$51
(b11)
ml|t;]1
Σ
||t: t1
2 #5
[[(m]
m
Σ Pli E 3, = Σ
P(i So 11 +
Pfi.j E Si) < <,,,,>>
$E [m)
(b12) n
|,,
n( - 1)
Σ <,,
m mm
m m(m m 1)
($1
17

---

Published as a conference paper at ICLR 2021
(b13) n²
n(n - 1)
||t:l1
|t: - -t,1?
m
2m m - 1)
<c(m
where (611) and (b13) are due to the fact that (x.
- 1| 1 + 1
(b12) follows from the fact that P(i E St = and j E St} = m(m-1y Therefore, we have
LAPUi 2n
K-1
m K
A33
ΣE
PliE
S
Σ
MII
VF
2Km²
5=0
Inp nz
m
Ln (n 1)
ML
ML ||te|l? +
||t; t, ||
2m
2Km
4Km²
4mm(m - 1)
itj
(b14)
Ln
Lni (n 11 2n(m - 1)
m |1t:12
Ln7² (n - 12,
)||
Σ t.112 kE|m
2m
2Km²
2mn(m - 1)
1=1
(b15)
Lninn
2
Lai (n= -1)
S
l|t:11
2m
2m(m 1)
= Luf 2
m. - n
||::11
2m (m 1=1
where (b14) follows from the fact that
Eigim)] 1 Eiemm] m m||t,|1=- 2 Eist ||t, -tyl?, and
(b15) is due to the fact that
mig 2km=
Ln 00 (n-1)
2 if mm KL S m(m-1)
2m
m(n-1]'
Then we have
Exf((x++)) M S f(xi)
mLk1 - -15K3n1, 1," -LML 2m(m 1)
m
LKn² of +KK2 Taj AI 2n(m 1)
m 03
2n
T.
+ +m
+ 15K
13 m n2
2n(m - 1) (oi + 6Kog)
2
(616)
1K 07 + 13K 33LL ni. m- n
$ f(x+)= - c... (Vxx)
2n(m - 1) 0
2n
52 + 15K2 mi. L3 m n
mm
2n(m (o + +6Ko2),
(10)
2
where (b16) holds because there exists a constant c > 0 satisfying ( - 5k2
LAML 2n(m-1)
000K2n L2 + +K)) > c 0f 10 1/ L2 Lime n(m-1) (90K 1/ L2 + 3K) 1.
m-n
Note that the requirement of |St| = n can be relaxed to |S.| 2 n. With p. 2 n workers in 1-th communication round, 10 is
LK 72
E, [f S f(x)) CMLLK
of + 3K 1I 2p (m - 1) d
m Pt
2p:
K( 5K 1,2
15K2 mm 1,3 2pr(m - 1) (o7 + 6Ko
Pt
2
< [xx)) - cmr. K (Xx
LK ni
of + 43K LTj 1/ 2 m- n
2n(m m - 1) OG
2n
5K L? mix
+ K
L3 m n
2n(m - 1) (oz + 6Ko
2
That is, the same convergence rate can be guaranteed if at least n workers in each communication round (no need to be exactly n).
18

---

Published as a conference paper at ICLR 2021
Rearranging and summing from t 0,... T 1, we have the convergence for partial device participation with sampling strategy as follows:
fo f+
min B fxx EE
CmiL + 4,
where Φ-
Lyyi [
2n of + +3KTam 2n(m-1]
a +
5k 1.
+5k 2 1 m) + +KKg8)
and è is constant. This completes the proof.
A.2.1 KEY LEMMAS
Lemma (Unbiased Sampling). For strategies and the estimator Dg is unbiased, ie.,
Es, [ A.
Proof of Lemma 7
Let St = {41.-.- (n with size n. Both for sampling strategies I and 2, each sampling distribution identical. Then we have:
Es, [s] Es.
Σ
A/
=
Es. A Es,
1 m
Σ
m
B.
72
71
4.S.
A.3 AUXILIARY LEMMAS
Lemma 2 (Lemma 4 in Reddi et al. 2020)). For any step-size satisfying Tr. S SLK we can have the following results:
1 Σ - -
+ 330K VV
Proof. In order for this paper be self-contained, we restate the proof of Lemma 4 in (Reddi et al.. 2020 here.
For any worker E [m]] and & [K], we have:
E x
x, 11 = E[[|x [ - X
71.6 -
-
1
$ (1 +
- 1
2K
V/. 64440/14444044444777777707666644 (a
(
F.
<(1+ 2K-1
) k- 12
1
=(1+ +
+ 6K
LK
11 vi02 6K 67
2K 1
<
1 (1
xx x1+ -
+6K 60 [l.
K
Unrolling the recursion, we get:
k-1
E [ - xx < 2 (1+
K - Pf + +Kog + 6K (1
m
p=0
K イー - kk - 11 6Koz + 6K M. (((x)))
< (K [ +
< 55K (o} + 6K 3k0 + 30K V
This completes the proof.
19

---

Published as a conference paper at ICLR 2021
B APPENDIX II: EXPERIMENTS
We provide the full detail of the experiments. We uses non-i..d. versions for MNIST and CIFAR-10, which are described as follows:
B.I MNIST
We study image classification of handwritten digits 0-9 in MNIST and modify the MNIST dataset to a non-i.id. version.
To impose statistical heterogeneity, we split the data based on the digits (p) they contain in their dataset. We distribute the data to m 100 workers such that each worker contains only a certain class of digits with the same number of training/test samples. For example, for p = each worker only has training/testing samples with one digit, which causes heterogeneity among different workers. For p = 10, each worker has samples with 10 digits, which essentially i.idd case. In this way, we can use the digits in worker's local dataset to represent the non-i.i.d. degree qualitatively. In each communication round, 100 workers run K epochs locally in parallel and then the server samples n workers for aggregation and update. We make grid-search experiments for the hyper-parameters as shown in Table
Table 3: Hyper-parameters Tuning.
Server Learning Rate
E (1, 10}
Client Learning Rate
VI1. E (0.001, 0.01, 0.01,
Local Epochs
K E: {1,5, 10)
Clients Partition Number Non-i..d. Degree
n1 E {10,50, 100}
p E 1,
We run three models: multinomial logistic regression, fully- cully-connected network with two hidden layers (2NN) (two 200 neurons hidden layers with ReLU followed by an output layer), convolutional neural network (CNN), as shown in Table
The results are shown Figures] 2 and
Table 4: CNN Architecture for MNIST.
Layer Type
Size
Convolution + Rel.u
5 x x 32
Max Pooling
2 x 2
Convolution + ReLu
5 64
Max Pooling
2 x 2
Fully Connected ReLU
1024 x 512
Fully Connected
512 x 10
B.2 CIFAR-10
Unless stated otherwise, we use the following default parameter setting: the server learning rate and client learning rate are set to = 1.0 and 7ı = 0.1, respectively. The local epochs is set to K = 10. The total number of clients is set to 100, and the clients partition number is set to same strategy to distribute the data over clients as suggested in McMahan et al. (2016). For the i.i.d. setting, evenly partition all the training data among all clients, i.e., each client observes 500 data; for the non-i.i.d. setting, we first sort the training data by label, then divide all the training data into 200 shards of size 250, and randomly assign two shards to each client. For the CIFAR- 10 dataset, train our classifier with the ResNet model. The results are shown in Figure 5 and Figure 6
10. We use the
B.3 DISCUSSION
Impact of non-i.i.d datasets: Figure 2 shows the results of training loss (top) and test accuracy (bottom) for three models under different non-i.i.d. datasets with full and partial worker participation
20

---

Published as a conference paper at ICLR 2021
2.5
2.5
2.0
2.5
Traiig
2.0
1.0
0.5
0.0
40
60
100
0.0
20
40
60
100
0.0
40
60
100
Commun caliin Round
Commun calion Round
Commun calton Round
0.8
0.8
0.6
9.6
0.2
0.2
Commun Round
calion Round
Commun Rooun
(a) LR
(b) 2NN
(c) CNN
Figure 2: Training loss (top) and test accuracy (bottom) for three models on MNIST with hyperpa- rameters setting: local learning rate 0.1, global learning rate 1.0, local steps 5 epochs.
2.0
2.0
2.0
Mati Siic
Lona
1.0
1.0
0.0
80
0.0
60
Commun cation Round
Commun catton Round
Commun catton Round
1.0
Test Accursty
0.6
0.6
0.4
40
60
40
60
Commun
(a) LR
(b) 2NN
(c) CNN
Figure 3: Training loss (top) and test accuracy (bottom) for three models on MNIST with hyperpa- rameters setting: local learning rate 0.1, global learning rate 1.0, worker number 100.
that the FedAvg algorithm converges under non-i.i.d. datasets with proper learning rate choice in these cases. We believe that the major challenge in FL is the non-i.i.d. datasets. For these datasets with lower degree of non-i.i.d., the FedAvg algorithm can achieve good result compared with the i..d. case. For example, when the local dataset in each worker has five digits (p 5) with full (partial) worker participation, the FedAvg algorithm achieves convergence speed comparable with that of the i.i.d. case (p 10). This result can be observed in Figure for all three models. As the degree of non-i.i.d. datasets increases. its negative impact on the convergence is becoming more obvious. The higher the degree of non-i.i.d., the slower the convergence speed. As the non-i.i.d. degree increases (from case p 10 to case p = 1), it is obvious that the training loss increasing and test accuracy is decreasing. For these with high degree of non-i.id. the convergence curves oscillate and are highly unstable. This trend is more obvious for complex models such for CNN in Figure c).
MNIST. We
Impact of worker number: For full worker participation, the server can have an accurate estimation of the system heterogeneity after receiving the updates for all workers and neutralize this heterogeneity in each communication round. However, partial worker participation introduces another source of randomness, which leads to zigzagging convergence curves and slower convergence. In each
21

---

Published as a conference paper at ICLR 2021
2.5
2.5
Ond
2.5
Tonnr
Troming
2.0
2.0
0.5
0.0
40
60
100
0.0
20
40
60
100
0.0
40
60
80
100
Commun caliin Round
Commun calton Round
Commun cation Round
T TeaLAccurc
Testaccuracy
0.8
0.6-
0.2
0.2
Commun Round
Cummun calion Round (b) 2NN
Commun cation Round
(a) LR
(c) CNN
Figure 4: Training loss (top) and test accuracy (bottom) for three models on MNIST with hyperpa- rameters setting: local learning rate 0, global learning rate 1.0, worker number 10.
10
20
Acourscy
0.6
0.6
0.4
0.4
0.0
0.0
Communication Round
(a) IID.
(b) Non-IID.
Figure 5: Test accuracy with respect to worker number on CIFAR-10 dataset.
1.0
K
K
0.8
0.8
X 110
scourcyy
0.6
0.6
0.4
0.0
100
200
500
2000
300
Communication round
Communiction round
(a) IID.
(b) Non-IID.
Figure Test accuracy with respect to different local steps on CIFAR-10 dataset.
communication round, the server can only receive a subset workers based on the sampling strategy. So the server could only have a coarse estimation of the system heterogeneity and might not be able to neutralize the heterogeneity among different workers for partial worker participation. This problem is more prominent for highly non-i.i.d datasets. It is not unlikely that the digits in these datasets among all active workers are only a proper subset the total 10 digits in the original MNIST dataset, especially with highly non-i.i.d. datasets. For example, for with 10 workers in each
22

---

Published as a conference paper at ICLR 2021
communication round, it is highly likely that the datasets formed by these ten workers only includes certain small number of digits (say, or 5) rather than total 10 digits. But for p = 5, it is the opposite, that is, the digits in these datasets among these 10 workers are highly likely to be 10. So in each communication round, the server can mitigate system heterogeneity since it covers the training samples with all 10 digits. This trend is more obvious for complex models and datasets given the dramatic drop of test accuracy in the result of CIFAR-I0 in Figure 5
The sample strategy here is random sampling with equal probability without replacement. In practice, the workers need to be in certain states in order to be able to participate in FL (e.g., in charging or idle states, etc. (Eccheer al., 2019). Therefore, care must be taken in sampling and enlisting workers in practice. We believe that the joint design of sampling schemes, number of workers and the FedAvg algorithm will have a significant impact on the convergence, which needs further investigations.
Impact of local steps: Figure and A the results of training loss (top) and test accuracy (bottom) for three models under different local steps with full and partial worker participation respectively. Figure []] shows the impact of local steps in CIFAR-10. One open question of FL is that whether the local steps help the convergence or not. et al. (2019b) showed convergence rate O (($). i.e., the local steps may hurt the convergence for full and partial worker participation. In this two figures, we can see that local steps could help the convergence for both full and partial worker participation. However, it only has slight effect on the convergence compared to the effects of non-i.i.d. datasets and number of workers.
Comparison with SCAFFOLD: We compare SCAFFOLD (Kariirredy al. 2019) with the generalized FedAVg algorithm this paper in terms of communication rounds, total overloads and estimated wall-clock time achieve certain test accuracy in Table We run the experiments using the same GPU (NVIDIA V100) to ensure the same conditions. Here, we give specific comparison for these two algorithms under exact condition. Note that we divide the total training time to two parts: the computation time when the worker trains the local model and the communication time when information exchanges between the worker and server. We only compare the computation time and communication time with fixed bandwidth 20M B/ /s for both uploading and downloading connections. less communication round due to the variance reduction techniques. That is, it spends less time on computation. However, it needs to communicates as twice as the FedAvg since the control variate to perform variance reduction in each worker needs to update in each round. In this way, the communication time would be largely prolonged.
communication
shown Figure 7 to achieve 75%, SCAFFOLD performs
SCAFFOLD
Computation time Communication time
This paper
0
100
200
300 Time (s)
400
500
600
Figure 7: Wall-clock time to achieve test accuracy 75% on CIFAR-10 dataset.
23


Reviews:
[{"review_id": "gjsCYDqU3bw", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### Summary of the paper:\nThis paper analyzes convergence rates of the standard \"FedAvg\" algorithm  (with two sided learning rates) that is widely used in federated learning in multiple orthogonal perspectives:\na) non I.I.D datasets - with reasonable assumptions about the heterogeneity and suitable parameters, convergence guarantees comparable to I.I.D setting can be achieved.\nb) partial worker participation - provides an analysis of convergence based on the number of workers participated (constant $n$) in each round.\nc) number of local steps - analysis of overall convergence rate that depends on this is provided, but full effects are not yet clear (open problem).\nThis paper provides ample empirical evaluations to validate the theoretical claims shown.\n\n#### Quality:\nThis paper is generally well written and structured well. Although I did not read the proof of the theorems thoroughly, the claims sound natural and believable. Thorough explanations and insights of the theoretical claims are provided.\n\n#### Clarity:\nClarity of certain parts needs to be improved.\n- The claim about the number of local updates $K$ improving to $T/m$ from $T^{1/3}/m$ is not clear. At first glance this does not look like an improvement because it gets worse for the the workers(devices). But remark 3 explains that this indeed causes an improvement in the overall convergence rate. I think this should be clearly mentioned in the contributions.\n- It is better if the authors can change some superscripts for footnotes in table 1, the superscripts 4 and 6 look like exponents at the first glance which can be confusing.\n- In related work, it is mentioned that \"(Karimireddy et al., 2019) can achieve linear speedup but extra variance reduction operations are required, which lead to high communication costs and implementation complexity. In this paper, we show that this linear speedup can be achieved without any extra requirements.\" State this clearly in the contributions since the table 1 does not imply this and it is difficult to understand the improvements, thus the novelty of these results by looking at table 1 or contributions.\n-  I believe the the expectations in assumption 2 and theorems 1, 2 are over local datasets samples. Clearly state this.\n- $f_0, f_*$ are not defined in theorem 1,2 (I believe they are loss function values at start and the optimal point). Define these quantities.\n\n\n#### Originality and significance:\nAlthough this paper does not technically introduce a new algorithm for federated, I believe that the theoretical analysis of \"FedAvg\" in the non I.I.D. and partial worker participation setting and relevant parameters are nice contributions to the ICLR community. I think the insights obtained by this work can be very useful in developing better algorithms and in practice since it considers more realistic scenarios and the model assumptions are reasonable. \n\nPros:\n- Main contributions on non I.I.D data and partial worker settings are nice and relevant realistic scenarios.\n- I think the result on linear speed up that does not depend on a requirement of bounded gradient assumption is nice especially in non I.I.D and non-convex settings since such dependencies in these scenarios can be unrealistic.\n- Extensive experimental evaluations on the theoretical claims validate the results.\n\nCons:\n- One concern I have is the claimed convergence rate in FedAvg is achievable when $T \\ge mK$, but in federated learning settings, it is  often the case that $m$ is very large. Therefore this requires $T$ to be very large and thus blow up the required number of communication rounds for convergence. Is this a common issue in the other works compared in table 1 or inherent in FedAvg? The experiments are also done with $m=100$, therefore it is difficult to gauge the impact of large(which is realistic) number of clients in practice.\n\nOther comments:\nI would like to understand that the requirement $|S_t| = n$ in section 3.2 can be relaxed to something like at least $n$ workers in each round and the same convergence guarantees would hold. While strategy 1 and 2 are viable, I believe this can also be a nice way to understand the partial worker setting.\n\nFinal feedback:\nI thinks this paper has decent contributions to the understanding of federated averaging method in more realistic scenarios. I am willing to increase my score if the concerns mentioned above are properly addressed.\n===============================================================================================================\n\nAdded after reading author response:\n\n------------------------------------------------------\n\nI believe authors have addressed the issues I raised about clarity in certain parts of the paper in their response sufficiently.  I agree that in this paper, the convergence rates' dependency on $m$ has been improved significantly compared to previous work. Thus I increase my score. I encourage authors to investigate $m$'s effects on the convergence rate more to see whether there is a structural limitation in federated learning settings, perhaps better left for future work.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ut9r_uo2iIp", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "EDIT after discussion:\n\nThanks for the authors' comments and revisions to this paper. I'm glad to see that some of my concerns have been addressed so I decide to change my score.\n\nJust some minor comments about writing for the revised version. I think the proof sketch is clear and easy to follow the logic with some room for further improvement. Like the other reviers' comments, I think some part of the paper like notations should be with clear explanation.\n\n-------------------------------------------------------------\n\nThis paper provides a theoretical analysis for FedAvg, the seminal optimization algorithm for federated learning. The analysis is featured at client sampling and non-iid distributions among clients, which are two well-known challenges in federated learning. The theoretical results in this paper provide us an optimization view to understand why FedAvg works, and how it saves communication cost by allowing low SGD updates and by model averaging.\n\nI think the authors can further improve this paper from the following aspects.\n\nFirst, the metric for convergence rate is slightly less common in the methods shown in Table 1. Most existing works (e.g., Yu et al. 2019a, Karimireddy et al. 2019) use the average norm of stochastic gradients in the previous T steps. However in this paper the authors consider the minimum of these T values. It's not a problem per se because the minimum also shows the convergence trend somehow. The problem is, comparison with existing work as listed in Table 1 looks confusing to me. I would like to see if there is a way of showing the linear speedup in the same fashion.\n\nSecond, I think the experiment section has some room for improvement. The whole section doesn't show comparison with any existing but some curves with hyperparameter variants. In particular, I really want to see how the proposed algorithm compared with SCAFFOLD, because both rates are matched (despite my comment above). \n\nLike the authors said, SCAFFOLD needs to maintain an additional set of variables for variance reduction, which may introduce more communication and computation costs. For this reason, I would like to see comparison not only the convergence w.r.t. steps/epochs, but also in wall clock, under the same bandwidth constraint, FLOPS, .etc.\n\nOne minor suggestion is about writing. The technique to show the linear speedup in this paper is worth writing some lines of proof sketch. One such example is the SCAFFOLD paper. It will help readers to understand the main contribution, and may help readers to apply such technique in other related problems.", "extra_scores": {}, "extra_text": {}}, {"review_id": "LSYKcLCZWno", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a new analysis for the FedAvg algorithm, which assumes the data on different workers are non-IID and the objective functions are non-convex. The new analysis improved the existing bounds of FedAvg. Besides, the analysis is also extended to the non-stationary network, where the number of workers participating in the optimization may vary.\n\nAs FedAvg is the most important optimization algorithm in federated learning, I think such theoretical progress is good. \n\nIf my understanding is correct, as the new bound allows a larger number of local steps, one important improvement for the algorithm is that the number of communication rounds can be also reduced. I suggest the authors demonstrate this fact in the paper, e.g., by adding a column concerning communication complexity in Table 1 and appending some discussion about communication cost.\n\nOne drawback of the theoretical results is that the model for the non-stationary network is too strong. It assumes the number of participants in each round is fixed, and each worker has an equal probability to participate. Such an assumption can be rarely satisfied in practice.\n\nOne typo: I guess $p_i=\\frac{1}{m}$ should be $p_i=\\frac{n}{m}$ in the last line of page 5.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors have addressed the issues raised by the reviewers. All the reviewers think that the paper deserves to be published at ICLR 2021. The authors should implement all the reviewers’ suggestions into the final version, especially for clarity issues and clear explanations. The reviewer also encourages authors to investigate $m$’s effects on the convergence rate more to see whether there is a structural limitation in federated learning settings for future work. 
Decision: Accept (Poster)