On the Convergence of FedAvg on Non-IID Data
Authors: Xiang Li
Kaixuan Huang
Wenhao Yang
Shusen Wang
Zhihua Zhang
Venue:  (2020)
Keywords: Federated Learning
stochastic optimization
Federated Averaging

Abstract: Federated learning enables a large amount of edge computing devices to jointly learn a model without data sharing. As a leading algorithm in this setting, Federated Averaging (\texttt{FedAvg}) runs Stochastic Gradient Descent (SGD) in parallel on a small subset of the total devices and averages the sequences only once in a while. Despite its simplicity, it lacks theoretical guarantees under realistic settings. In this paper, we analyze the convergence of \texttt{FedAvg} on non-iid data and establish a convergence rate of $\mathcal{O}(\frac{1}{T})$ for strongly convex and smooth problems, where $T$ is the number of SGDs. Importantly, our bound demonstrates a trade-off between communication-efficiency and convergence rate. As user devices may be disconnected from the server, we relax the assumption of full device participation to partial device participation and study different averaging schemes; low device participation rate can be achieved without severely slowing down the learning.  Our results indicate that heterogeneity of data slows down the convergence, which matches empirical observations. Furthermore, we provide a necessary condition for \texttt{FedAvg} on non-iid data: the learning rate $\eta$ must decay, even if full-gradient is used; otherwise, the solution will be $\Omega (\eta)$ away from the optimal.

Published as a conference paper at ICLR 2020
ON THE CONVERGENCE OF FEDAVG ON NON-IID DATA
Xiang Li'
Kaixuan Huang"
School Mathematical Sciences Peking University Beijing, 100871, China
School of Mathematical Sciences
Peking University
Beijing, 100871, China
sms 1 amslixiang@pkurr edu. en
hackyhuang@pku. wwtph/kkku.uuuc... edu
Wenhao Yang' '
Shusen Wang
Center for Data Science Peking University Beijing, 100871, China
Department of Computer Science
Stevens Institute of Technology Hoboken, NJ 07030, USA shusen shusen. wangeeswweeesseeeeeeeee edu
Zhihua Zhang
School of Mathematical Sciences Peking University
Beijing, 100871, China
zhzhang@mathh ppu....pp........... www..dd......................... edu. cn
ABSTRACT
Federated learning enables large amount of edge computing devices to jointly learn a model without data sharing. As a leading algorithm in this setting, Federated Averaging (F (FedAvg) runs Stochastic Gradient Descent (SGD) in parallel on small subset of the total devices and averages the sequences only once in a while. Despite its simplicity, it lacks theoretical guarantees under realistic settings. In this paper, we analyze the convergence of FedAvg on non-iid data and establish a convergence of ((+) for strongly convex and smooth problems, where T is the number of SGDs. Importantly, our bound demonstrates a trade-off between communication efficiency and convergence rate. As user devices may be disconnected from the server, we relax the assumption of full device participation to partial device participation and study different averaging schemes; low device participation rate can be achieved without severely slowing down the learning. Our results indicates that heterogeneity data slows down the convergence, which matches empirical observations. Furthermore,
provide necessary condition for FedAvg non-iid data: the learning rate 7 must decay, even if full-gradient is used; otherwise, the solution will be (2(r) away from the optimal.
INTRODUCTION
Federated Learning (FL), also known as federated optimization, allows multiple parties to collab- oratively train model without data sharing (Konevený et al., 2015; Shokri and Shmatikov, 2015; McMahan et al., 2017; Konevený, 2017; Sahu et al., 2018; Zhuo et al., 2019). Similar to the central- ized parallel optimization (Jakovetic, 2013; Li al., 2014;;b; Shamir et al., 2014; Zhang and Lin, 2015; Meng et al., 2016; Reddi et al., 2016; Richtárik and Takác, 2016; Smith et al., 2016; Zheng al., 2016; Shusen Wang et al., 2018), FL let the user devices (aka worker nodes) perform most of the computation and central parameter server update the model parameters using the descending directions returned by the user devices. Nevertheless, FL has three unique characters that distinguish it from the standard parallel optimization Li et al. (2019).
"Equal contribution.

---

Published as a conference paper at ICLR 2020
First, the training data are massively distributed over an incredibly large number of devices, and the connection between the central server and a device is slow. A direct consequence is the slow communication, which motivated communication-efficinc Smith et al., 2017; Sahu et al., 2018; Sattler et al., 2019). Federated averaging (FedAvg) is the first and perhaps the most widely used FL algorithm. It runs E steps of SGD in parallel small sampled subset of devices and then averages the resulting model updates via central server once in a while. In comparison with SGD and its variants, FedAvg performs more local computation and less communication.
FL algorithms (McMahan et al., 2017;
Second, unlike the traditional distributed learning systems, the FL system does not have control over users' devices. For example, when mobile phone is turned off or WiFi access is unavailable, the central server will lose connection to this device. When this happens during training, such a non-respondiinginactiee device, which is called straggler, appears tremendously slower than the other devices. Unfortunately, since it has no control over the devices, the system can do nothing but waiting or ignoring the stragglers. Waiting for all the devices' response is obviously infeasible; it is thus impractical to require all the devices be active.
Third, the training data are non-iid that is, device's local data cannot be regarded samples drawn from the overall distribution. The data available locally fail to represent the overall distribution. This does not only bring challenges to algorithm design but also make theoretical analysis much harder. While FedAvg actually works when the data are non-iid McMahan et al. (2017), FedAvg on non-iid data lacks theoretical guarantee even in convex optimization setting.
There have been much efforts developing convergence guarantees for FL algorithm based on the assumptions that (1) the data iid and (2) all the devices are active. Khaled et al. (2019); Yu et al. (2019); Wang et al. (2019) made the latter assumption, while Zhou and Cong (2017); Stich (2018); Wang and Joshi (2018); Woodworth al. (2018) made both assumptions. The two assumptions violates the second and third characters of FL. Previous algorithm Fedprox Sahu et al. (2018) doesn't 't require the two mentioned assumptions and incorporates FedAvg special case when the added proximal term vanishes. However, their theory fails to cover FedAvg.
Notation. Let N be the total number of user devices and K (S N) be the maximal number of devices that participate in every round's communication. Let T be the total number of every device's SGDs, E be the number local iterations performed in a device between two communications, and is the number of communications.
thus E
T
Contributions. For strongly convex and smooth problems, we establish a convergence guarantee for FedAvg without making the two impractical assumptions: (1) the data are iid, and (2) all the devices are active. To the best of our knowledge, this work is the first to show the convergence rate of FedAvg without making the two assumptions.
We show in Theorem 1, 2, and 3 that F FedAvg has ((+) convergence rate. In particular, Theorem 3 shows that to attain a fixed precision e, the number of communications is
T - -
((((1++
EN C (1+ 1+ kx) EG2 P + G2) {
E - O
(1)
E
Here, G, T. Pk. and T are problem-related constants defined in Section 3.1. The most interesting insight is that E is a knob controlling the convergence rate: neither setting E over-small (E = makes FedAvg equivalent to SGD) nor setting over-large is good for the convergence.
This work also makes algorithmic contributions. We summarize the existing sampling and averaging schemes for FedAvg (which do not have convergence bounds before this work) and propose a new scheme (see Table l). We point out that a suitable sampling and averaging scheme is crucial for the convergence eddvg. To the best of our knowledge, we are the first to theoretically demonstrate
In original paper (MeMahan et al., 2017), E epochs of SGD are performed in parallel. For theoretical analyses, we denote by E the times of updates rather than epochs. 'Throughout this paper, "non-iid" means data are identically distributed. More precisely, the data distributions in the k-th and 1-th devices, denote D₃ and Dj, can be different.
Throughout this paper, "sampling" refers to how the server chooses K user devices and use their outputs for updating the model parameters. "Sampling" does not mean how a device randomly selects training samples.
2

---

Published as a conference paper at ICLR 2020
Table 1: Sampling and averaging schemes for FedAvg, S; U(N, K) means St size-K subset uniformly sampled without replacement from [N]. St ~ W(N, K, p) means S contains K elements that are iid sampled with replacement from [N] with probabilities {p the latter scheme, S is not set.
Paper
Sampling
Averaging
Convergence rate
McMahan al. (2017)
St U(N, (((NK)) K) St W(N,K.p) St K)
Enes, PhW, EKES, Dow?
Sahu et al. (2018)
# ENES, W E ExES, Pk K
O )
Ours
O
that FedAvg with certain schemes (sce Table 1) can achieve O convergence rate non-iid federated setting. We show that heterogeneity of training data and partial device participation slow down the convergence. We empirically verify our results through numerical experiments.
Our theoretical analysis requires the decay of learning rate (which is known hinder the convergence rate.) Unfortunately, we show Theorem that the decay of learning rate is necessary for FedAvg with E 1, if full gradient descent is used." If the learning rate fixed y throughout, FedAvg would converge to a solution at least (n) E - 1)) away from the optimal. To establish Theorem 4, we construct a specific & 2n-mm regularized linear regression model which satisfies our strong convexity and smoothness assumptions.
Paper organization. In Section 2, we elaborate on FedAvg. In Section 3, we present our main convergence bounds for FedAvq. In Section 4, we construct a special example to show the necessity of learning rate decay. In Section 5, we discuss and compare with prior work. In Section 6, we conduct empirical study to verify our theories. All the proofs are left to the appendix.
2 FEDERATED AVERAGING (FEDAvG)
Problem formulation. In this work, we consider the following distributed optimization model:
min {F(w) Σ PPFk(w)).
where N is the number of devices, and pk: the weight of the k-th device such that pk 2 0 and Ex' Pk 1. Suppose the k-th device holds the ng training data: Th,1 Dk.2. .. Ih The local objective (-) is defined by
F&
((w;ax5).
(3)
71J j=1
where E(3)) is user-specified loss function.
Algorithm description. Here, describe around (say the 1-th) of the standard FedAvg algorithm. First, the central server broadcasts the latest model, w,, to all the devices. Second, every device (say the k-th) lets w W, and then performs E (2 local updates:
wh wh
w M V Fe ct.,), -= 0,1,...,E-11
where 7e is the learning rate (a.k.a. step size) and </ is sample uniformly chosen from the local data. Last, the server aggregates the local models, w w'+ w.N E+ g- to produce the new global model, W.+.. Because of the non-iid and partial device participation issues, the aggregation step vary.
'It is well know that the full gradient descent (which is equivalent to FedAvg with E' = 1 and full batch) do not require the decay of learning rate.
'The sampling scheme is proposed by Sahu al. (2018) for FedAvg baseline, but this convergence our contribution.
TThe convergence relies the assumption that data are balanced, i.c., rescaling trick to get rid of this assumption. We will discuss this point later Section 3.
nx. However,
3

---

Published as a conference paper at ICLR 2020
IID versus non-iid. Suppose the data in the k-th device are i..d. sampled from the distribution
DE- Then the overall distribution is mixture of all local data distributions: 'D = -i=1/ Pa Di- The prior work Zhang et al. (2015a); Zhou and Cong (2017); Stich (2018); Wang and Joshi (2018); Woodworth al. (2018) assumes the data iid generated by or partitioned among the N devices, that is. D2 D for all & E [ However, real real-world applications do not typically satisfy the iid assumption. One of our theoretical contributions is avoiding making the iid assumption.
Full device participation. The prior work Coppola (2015); Zhou and Cong (2017); Stich (2018); Yu et al. (2019); Wang and Joshi (2018); Wang et al. (2019) requires the full device participation in the aggregation step of FedAvg. In this case, the aggregation step performs
N
W
Ph w E-E
Unfortunately, the full device participation requirement suffers from serious "straggler's 's effect" (which means everyone waits for the slowest) in real-world applications. For example, if there thousands of users' devices in the FL system, there are always small portion of devices offline. Full device participation means the central server must wait for these "stragglers", which obviously unrealistic.
Partial device participation. This strategy is much more realistic because does not require all the devices' output. We can set threshold K (1 < K < N) and let the central server collect the outputs of the first K responded devices. After collecting K outputs, the server stops waiting for the rest; the K + 1-th to N-th devices regarded stragglers in this iteration. Let S, ([S, K) be the set of the indices of the first K responded devices in the t-th iteration. The aggregation step performs
N
Σ
WHE
Pa
K
RES.
can be proved that K Ekes, Pk equals one in expectation.
Communication cost. The FedAvg requires two rounds communications- one broadcast and one aggregation- per E iterations. If T iterations are performed totally, then the number of communications is 2f' During the broadcast, the central server sends w, to all the devices. During the aggregation, all or part of the N devices sends its output, say w to the server.
CONVERGENCE ANALYSIS OF FEDAVG IN NON-IID SETTING
In this section, show that FedAvg converges the global optimum rate of (1/TT) for strongly convex and smooth functions and non-iid data. The main observation is that when the learning rate sufficiently small, the effect of E' steps of local updates similar one step update with a larger learning rate. This coupled with appropriate sampling and averaging schemes would make each global update behave like an SGD update. Partial device participation (K N) only makes the averaged sequence {w,} have a larger variance, which, however, can be controlled by learning rates. These imply the convergence property of FedAvg should not differ too much from SGD. Next, we will first give the convergence result with full device participation (i.e., K = N) and then extend this result to partial device participation (i.c., K < N).
3.1 NOTATION AND ASSUMPTIONS
We make the following assumptions the functions Fi,... Fr. Assumption I and standard; typical examples are the f--norm regularized linear regression, logistic regression, and softmax classifier.
Assumption 1. Fi,... Fr are all L-smooth: for all and w, Fa(v) S Fe(w) + (v w)T Fi (w) + [/1l - w|? wilv-w13.
Assumption 2. F,.... Fv are all p-strongly convex: for all v and w, Fx(v) 2 F&(w) + +(v w) V + f w|i
4

---

Published as a conference paper at ICLR 2020
Assumptions 3 and 4 have been made by the works Zhang et al. (2013); Stich (2018); Stich et al. (2018); Yu et al. (2019).
Assumption 3. Let E be sampled from the k-th device's local data uniformly at random. The variance of stochastic gradients in each device is bounded: E V < (Fll S o for k 1,..., ,N.
Assumption 4. The expected squared norm of stochastic gradients is uniformly bounded, i.e., E V + G² for all = =,,.,, and 1. =0, .
Quantifying the degree of non-iid (heterogeneityy. Let F and F2 be the minimum values of F and Fk, respectively. We use the term r = F -E Pk: FE for quantifying the degree of non-iid. If the data are iid, then I obviously goes to zero the number of samples grows. If the data are non-iid, then nonzero, and its magnitude reflects the hetcrogeneity of the data distribution.
3.2 CONVERGENCE RESULT: FULL DEVICE PARTICIPATION
Here analyze the case that all the devices participate in the aggregation step; Section 2 for the algorithm description. Let the FedAvg algorithm terminate after iterations and return wr as the solution. We always require T' is evenly divisible by E so that FedAvg can output Wr expected.
Theorem 1. Let Assumptions to 4 hold and I., μ. ohe G be defined therein. Choose 4/2 m Sk, E} and the learning rate fi- p( Then FedAvg with full device participation satisfies
2K
B + +2L Wo w w²11)
F S E [[F(WT)]
(4)
7 +T
where
Pl 117 + +8E++8E---- - 1)² B= Σ
(5)
3.3 CONVERGENCE RESULT: PARTIAL DEVICE PARTICIPATION
As discussed in Section 2, partial device participation has more practical interest than full device participation. Let the set S; (C [N] index the active devices in the f-th iteration. To establish the convergence bound, need make assumptions on S.-
Assumption 5 assumes the indices are selected from the distribution Pı. independently and with replacement. The aggregation step is simply averaging. This first proposed in (Sahu et al., 2018), but they did not provide theoretical analysis.
Assumption 5 (Scheme I). Assume S. contains a subset of K indices randomly selected with replucement according to the sampling probabilities pv. ,pN. The aggregation step of FedAvg performs We - t E w
Theorem 2. Let Assumptions
hold and L, ur, ou, G be defined therein. Let K. Ts Tet, and B be defined in Theorem 1. Let Assumption 5 hold and define C = K G²G Then
E [[([T)]] - F" <
2k
B B+C
+ +2 w'13)
(6)
T
Alternatively, we can select K indices from [N] uniformly at random without replacement. As a consequence, we need different aggregation strategy. Assumption 6 assumes the K indices selected uniformly without replacement and the aggregation step is the same as in Section 2. However, guarantee convergence,
require additional assumption of balanced data.
Assumption 6 (Scheme II). Assume S, contains subset of K indices uniformly sampled from [N] without replacement. Assume the duta is balanced in the sense that P
PN N- The
aggregation step of FedAvg performs W, - N. Ekes, Pk. wk.
K
Theorem 3. Replace Assumption 5 by Assumption 6 and by C N-K 4 E² 2 Then the same bound in Theorem holds.
N-1
5

---

Published as a conference paper at ICLR 2020
Scheme II requires P1 PN N which obviously violates the unbalance nature of FL. Fortunately, this can be addressed by the following transformation. Let Fx(w) = PieNFFi( (w(w)))))))))) be scaled local objective Fg. Then the global objective becomes simple average of all scaled local objectives:
F(w) Σ P&
1 N Σ (w().
Theorem 3 still holds if L, μ4 oke G are replaced by _ vL, j - sp, oz vvo, and G vDG, respectively. Here, V/ = N max; Ph and & = -minn Pk.
3.4 DISCUSSIONS
Choice of E. Since |wo- w'12 S G² for p-strongly convex F, the dominating term in eqn. (6)
is
N Ex
hh oo LI + (1+ + E + RG
μf
Let T. denote the number required steps for FedAvg to achieve an accuracy. follows from eqn. (7) that the number of required communication rounds is roughly
Tc (1+
1 1 EG D + LI + KG2 K
(8)
Thus, E is function of E' that first decreases and then increases, which implies that over-small or over-large E may lead to high communication cost and that the optimal F exists.
Stich (2018) showed that if the data are iid, then E can be set to O(VT). However, this setting does not work if the data are non-iid. Theorem implies that must not exceed ((VT)): otherwise, convergence not guaranteed. Here we give intuitive explanation. If E is set big, then w can converge to the minimizer of Fs, and thus FedAvg becomes the one-shot average Zhang et al. (2013) of the local solutions. If the data are non-iid, the one-shot averaging does not work because weighted average of the minimizers of Fi. FN can be very different from the minimizer of F.
Choice of K. Stich (2018) showed that if the data are iid, the convergence rate improves substan- tially as increases. However, under the non-iid setting, the convergence rate has a weak dependence on K, show in Theorems 2 and 3. This implies FedAvg is unable achieve linear speedup. We have empirically observed this phenomenon (see Section 6). Thus, in practice, the participation ratio & be set small alleviate the straggler's effect without affecting the convergence rate.
Choice of sampling schemes. We considered two sampling and averaging schemes Theorems and 3. Scheme selects K devices according to the probabilities pl, PPN with replacement. The non-uniform sampling results in faster convergence than uniform sampling, especially when Pi.... PN are highly non-uniform. If the system can choose to activate any of the N devices at any time, then Scheme should be used.
However, oftentimes the system has control over the sampling: instead, the server simply the first returned results for the update. In this case, we can assume the K devices are uniformly sampled from all the N devices and use Theorem to guarantee the convergence. If Pi. pv highly non-uniform, then v = N max; Ps is big and = N min; Ph small, which makes the convergence of FedAvg slow. This point of view is empirically verified in experiments.
4 NECESSITY OF LEARNING RATE DECAY
In this section, point out that diminishing learning rates crucial for the convergence of FedAvg in the non-iid setting. Specifically, we establish the following theorem by constructing a ridge regression model (which strongly convex and smooth).

---

Published as a conference paper at ICLR 2020
Theorem 4. We artificially construct strongly corvex and smooth distributed optimization problem. With full batch size, >> 1. and any fixed step size, FedAvg will converge to sub-optimal points. Specifically, let w be the solution produced by FedAvg with small enough and constant 1), and w" the optimal solution. Then we have
I w 1 ||w"|l2-
where we hide some problem dependent constants.
Theorem 4 and its proof provide several implications. First, the decay of learning rate is necessary of FedAvg. On the one hand, Theorem 1 shows with E > and decaying learning rate, FedAvg converges to the optimum. On the other hand, Theorem 4 shows that with E > 1 and any fixed learning rate, FedAvg does not converges to the optimum.
Second, FedAvg behaves very differently from gradient descent. Note that FedAvg with F = 1 and full batch size exactly the Full Gradient Descent; with a proper and fixed learning rate, its global convergence to the optimum is guaranteed Nesterov (2013). However, Theorem shows that FedAvg with E > and full batch size cannot possibly converge to the optimum. This conclusion doesn't 't contradict with Theorem I in Khaled et al. (2019). which, when translated into our case, asserts that w will locate in the neighborhood of w with a constant learning rate.
Third, Theorem 4 shows the requirement of learning rate decay is not artifact of our analysis; instead, it is inherently required by FedAvg. An explanation is that constant learning rates, combined with E steps of possibly-biased local updates, form sub-optimal update scheme, but diminishing learning rate can gradually eliminate such bias.
The efficiency of F FedAvg principally results from the fact that it performs several update steps local model before communicating with other workers, which saves communication. Diminishing step sizes often hinders fast convergence, which may counteract the benefit of performing multiple local updates. Theorem 4 motivates more efficient alternatives to FedAvg.
RELATED WORK
Federated learning (FL) was first proposed by McMahan al. (2017) for collaboratively learning a model without collecting users' data. The research work on FL is focused on the communication- efficiency Konevený al. (2016); McMahan et al. (2017); Sahu et al. (2018); Smith et al. (2017) and data privacy Bagdasaryan et al. (2018); Bonawitz et al. (2017); Geyer et al. (2017); Hitaj et al. (2017); Melis et al. (2019). This work is focused on the communication--fficienng issue.
F FedAvg, synchronous distributed optimization algorithm, was proposed by McMahan et al. (2017) as an effective heuristic. Sattler et al. (2019); Zhao et al. (2018) studied the non-iid setting, however, they do not have convergence rate. A contemporaneous and independent work Xie et al. (2019) analyzed asynchronous FedAvg; while they did not require iid data, their bound do not guarantee convergence saddle point or local minimum. Sahu et al. (2018) proposed a federated optimization framework called FedP rox to deal with statistical heterogeneity and provided the convergence guarantees in non-iid setting. FedP rox adds proximal term each local objective. When these proximal terms vanish, FedP r ox is reduced to FedAvg. However, their convergence theory requires the proximal terms always exist and hence fails cover FedAvg.
When data are iid distributed and all devices are active, FedAvg is referred to as LocalSGD. Due to the two assumptions, theoretical analysis of LocalSCH SCD is easier than F FedAvg. Stich (2018) demonstrated LocalsGD provably achieves the same linear speedup with strictly less communication for strongly-come convexx stochastic optimization. Coppola (2015); Zhou and Cong (2017); Wang and Joshi (2018) studied Local SGD in the non-convex setting and established convergence results. Yu et al. (2019); Wang et al. (2019) recently analyzed Loca SGD for non-convex functions in heterogencous settings. In particular, Yu et al. (2019) demonstrated LocalSGD also achieves O(L/VNT) convergence (i.e., linear speedup) for non-convex optimization. Lin et al. (2018) empirically shows variants of Loca increase training efficiency and improve the generalization performance of large batch sizes while reducing communication. For Local 1 GD on non-iid data (as opposed to LocalSGD), the best result is by the contemporaneous work (but slightly later than our first version) (Khaled et al., 2019). Khaled et al. (2019) used fixed learning rate di and showed (++)
7

---

Published as a conference paper at ICLR 2020
convergence to point O E?) away from the optimal. In fact, the suboptimality is due to their fixed learning rate. As we show in Theorem 4, using a fixed learning rate 7j throughout, the solution by LocalGD is at least (2((E - 1)m) away from the optimal.
If the data are iid, distributed optimization can be efficiently solved by the second-order algorithms Mahajan et al. (2018); Reddi et al. (2016); Shamir al. (2014); Shusen Wang et al. (2018); Zhang and Lin (2015) and the one-shot methods Lee et al. (2017); Lin et al. (2017); Wang (2019); Zhang al. (2013; 2015b). The primal-dual algorithms Hong al. (2018); Smith al. (2016; 2017) are more generally applicable and more relevant to FL.
NUMERICAL EXPERIMENTS
Models and datasets We examine our theoretical results on a logistic regression with weight decay A le - 4. This is stochastic convex optimization problem. We distribute MNIST dataset (LeCun et al., 1998) among N = 100 workers in a non-iid fashion such that each device contains samples of only digits. We further obtain two datasets: mnist ba l lanced and mn insst unbal anced. The former is balanced such that the number of samples in each device is the same, while the latter is highly unbalanced with the number samples among devices following a power law. To manipulate heterogeneity more precisly, we synthesize unbalanced datasets following the setup in Sahu et al. (2018) and denote as synthetic (a, B) where a controls how much local models differ from each other and I controls how much the local data at each device differs from that of other devices. We obtain two datasets: synthetic (0, 0) and synthetic (1, Details can found in Appendix D.
velote vebnee
Levt seputs
(a) The impact of E
(b) The impact of K
(c) Different schemes
(d) Different schemes
Figure 1: (a) To obtain an e accuracy, the required rounds first decrease and then increase when we increase the local steps E. (b) In Synt Synthetic (0, 0) dataset, decreasing the numbers of active devices each round has little effect on the convergence process. (c) In mnist balanced dataset, Scheme slightly outperforms Scheme II. They both performs better than the original scheme. Here transformed Scheme coincides with Scheme due to the balanced data. (d) In mnist unbal 1 a anced dataset, Scheme performs better than Scheme II and the original scheme. Scheme II suffers from instability while transformed Scheme II has a lower convergence rate.
Experiment settings For all experiments, initialize all runnings with wo O. In each round, all selected devices run E steps of SGD in parallel. We decay the learning rate at the end of each round by the following scheme 7)t = _m0_ where 17o is chosen from the set {1, 0.1,1,1.000 0.013. We evaluate the averaged model after each global synchronization on the corresponding global objective. For fair comparison, we control randomness in experiments so that the set of activated devices the same across all different algorithms one configuration.
Impact E We expect that T./E, the required communication round to achieve curtain accuracy, is a hyperbolic finction of E as equ (8) indicates. Intuitively, small E means heavy communication burden, while a large E means a low convergence rate. One needs to trade off between communication efficiency and fast convergence. We empirically observe this phenomenon unbalanced datasets in Figure la. The reason why the phenomenon does not appear in mnist future investigations.
dataset requires
8

---

Published as a conference paper at ICLR 2020
Impact of K Our theory suggests that larger K may slightly accelerate convergence since T./E EG K Figure 1b shows that K has limited influence on the convergence of FedAvg in synthetic (0, 0) dataset. reveals that the curve of a large enough K' slightly better. We observe similar phenomenon among the other three datasets and attach additional results in Appendix D. This justifies that when the variance resulting sampling is not too large (i.e., B > C), use small number of devices without severely harming the training process, which also removes the need to sample as many devices as possible in convex federated optimization.
contains a term O
Effect of sampling and averaging schemes. We compare four schemes among four federated datasets. Since the original scheme involves history term and may be conservative, we carefully set the initial learning rate for it. Figure Ic indicates that when data are balanced, Schemes and II achieve nearly the same performance, both better than the original scheme. Figure 1d shows that when the data are unbalanced, i.e., P3 are uneven, Scheme performs the best. Scheme suffers from some instability in this case. This is not contradictory with our theory since we don't guarantee the convergence of Scheme when data is unbalanced. As expected, transformed Scheme II performs stably at the price of lower convergence rate. Compared to Scheme I, the original scheme converges at a slower speed even its learning rate is fine tuned. All the results show the crucial position of appropriate sampling and averaging schemes for FedAvg.
CONCLUSION
Federated learning becomes increasingly popular in machine learning and optimization communities. In this paper we have studied the convergence of FedAvg, a heuristic algorithm suitable for federated setting. We have investigated the influence of sampling and averaging schemes. We have provided theoretical guarantees for two schemes and empirically demonstrated their performances. Our work sheds light on theoretical understanding of FedAvg and provides insights for algorithm design in realistic applications. Though our analyses are constrained in convex problems, we hope our insights and proof techniques can inspire future work.
ACKNOWLEDGEMENTS
Li, Yang and Zhang have been supported by the National Natural Science Foundation of China (No. 11771002 and 61572017), Beijing Natural Science Foundation (Z190001), the Key Project of MOST of China (No. 2018AAA0101000), and Beijing Academy of Artificial Intelligence (BAAI).
REFERENCES
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning, arXiv preprint arXiv:1807.0000 2018. 7
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017.
Gregory Francis Coppola. Iterative parameter mixing for distributed large- training of struc- tured predictors for natural language processing, PhD thesis, 2015. 4,7
Robin C Geyer, Tassilo Klein, Moin Nabi, and SAP SE. Differentially private federated learning: client level perspective. arXiv preprint arXiv: / 12.007557 2017.
Briland Hitaj, Giuseppe Ateniese, and Fernando Bérez-Cruz. Deep models under the GAN: infor- mation leakage from collaborative deep learning. In ACM SIGSAC Conference on Computer and Communications Security, 2017.
Mingyi Hong, Meisam Razaviyayn, and Jason Lee. Gradient primal-dual algorithm converges to second-order stationary solution for nonconvex distributed optimization over networks. In International Conference Machine Learning (ICMI.,, 2018. 8

---

Published as a conference paper at ICLR 2020
Dusan Jakovetic. Distributed optimization: algorithms and convergence rates. PhD, Carnegie Mellon University, Pinsburgh PA, USA, 2013.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local gd on heteroge- neous data, arXiv preprint wrXiv:1909004715. 2019. 2.7
Jakub Konevený. Stochastic, distributed and federated optimization for machine learning. arXiv preprint arXiv:177..01155, 2017.
Jakub Konevený,, Brendan McMahan, and Daniel Ramage. Federated optimization: distributed optimization beyond the datacenter. arXiv preprint 1XXi::5111.035/ 2015.
Jakub Konevený, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency, arXiv preprint arXiv:1610.05499 2016. 7
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86( (1))::2778-2244,, 1998. 8, 24
Jason D Lee, Qiang Liu, Yuekai Sun, and Jonathan Taylor. Communication-effiti sparse regression. The Journal of Machine Learning Research, 18(1):115-144, 2017.
Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene Shekita, and Bor- Yiing Su. Scaling distributed machine learning with the parameter server. 1/th {USENIX] Symposium on Operating Systems Design and Implementation ((OSDI) 14), pages 583-598, 2014a.
Mu Li, David G Andersen, Alexander J Smola, and Kai Yu. Communication efficient distributed machine learning with the parameter server. In Advances in Neural Information Processing Systems (NIPS), 2014b.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. arXiv preprint arXiv: 1900.0788, 2019.
Shao-Bo Lin, Xin Guo, and Ding Xuan Zhou. Distributed learning with regularized least squares. Journal of Machine Learning Research, 18(1):3202-3233 2017. 8
Tao Lin, Sebastian U Stich, and Martin Jaggi. Don't use large mini-batches, use local sgd. arXiv preprint arXiv: 1808. 072 2018. 7
Dhruv Mahajan, Nikunj Agrawal, S Sathiya Keerthi, Sundararajan Sellamanickam, and Léon Bottou. An efficient distributed learning algorithm based on effective local functional approximations. Journal of Machine Learning Research, 19(1):2942-299 29788 2018. 8
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-Efffiee Learning of Deep Networks from Decentralized Data. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2017. 1, 3, 7, 17,
Luca Melis, Congzheng Song, Emiliano De Cristofaro, and Vitaly Shmatikov. Exploiting unintended feature leakage in collaborative learning. In IEEE Symposium on Security & Privacy (S&P). IEEE, 2019. 7
Xiangrui Meng. Joseph Bradley, Burak Yavuz, Evan Sparks, Shivaram Venkataraman, Davies Liu, Jeremy Freeman, DB Tsai, Manish Amde, and Sean Owen. MLLib: machine learning in Apache Spark. Journal of Machine Learning Research, 17(34):1-7, 2016.
Yurii Nesterov, Introductory lectures on convex optimization: a basic course, volume 87, Springer Science & Business Media, 2013. 7
Sashank J Reddi, Jakub Konecný, Peter Richtárik, Barnabás Póczós, and Alex Smola. AIDE: fast and communication efficient distributed optimization. arXiv preprint arXiv:1608.06877 2016. 1, 8
Peter Richtárik and Martin Takáe. Distributed coordinate descent method for learning with big data. Journal of Machine Learning Research, (7(1):65772263 2016. 1
10

---

Published as a conference paper at ICLR 2020
Anit Kumar Sahu, Tian Li, Maziar Sanjabi, Manzil Zaheer, Ameet Talwalkar, and Virginia Smith. Federated optimization for heterogeneous networks. arXiv preprint arXiv:1812.06127, 2018. 1, 2, 3, 7, 8, 17, 24, 25
Felix Sattler, Simon Wiedemann, Mlaus-Rober Müller, and Wojeiech Samek. Robust and communication-effie 2019. 2,7
federated learning from non-iid data. arXiv preprint arXiv:
Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-effiiene distributed optimization using an approximate Newton-type method. In International conference on machine learning (ICML), 2014. 8,8
Reza Shokri and Vitaly Shmatikov. Privacy-preserving deep learning. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 2015.
Shusen Wang, Farbod Roosta Khorasani, Peng Xu, and Michael W. Mahoney. GIANT: Globally
improved approximate newton method for distributed optimization. In Conference Neural
Information Processing Systems (NeurIPS), 2018. 8
Virginia Smith, Simone Forte, Chenxin Ma, Martin Takac, Michael I Jordan, and Martin Jaggi. CoCoA: A general framework for communicationn-eficcenn distributed optimization. arXiv preprint arXiv: 161 180, 2016. 1,8
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar. Federated multi-task learning. Advances in Neural Information Processing Systems (NIPS), 2017. 2, 7,8
Sebastian U Stich. Local SGD converges fast and communicates little. arXiv preprint 1805 2018. 2, 6,
Sebastian U Stich, Jean- Sap-tatt Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems (NIPS), pages 4447-4458, 2018.
Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of communication-efficient SGD algorithms. arXiv preprint arXiv: 008.07576 2018. 2, 7,7
Shigiang Wang. Tiffany Tuor, Theodoros Salonidis, Kin K Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems. I6EE Journal on Selected Areas in Communications, 2019. 2, 2,
Shusen Wang. A sharper generalization bound for divide-and and-ucuuuueerr ridge regression. In The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI), 2019. 8
Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2018. 2.4
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization. arXiv preprint arXiv: 2019. 7
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 AAAI Conference on Artificial Intelligence, 2019. 2, 5,7
Sixin Zhang, Anna E Choromanska, and Yann LeCun. Deep learning with elastic averaging SGD, In Advances in Neural Information Processing Systems (NIPS), 201 5a. 4
Yuchen Zhang and Xiao Lin. DiSCO: distributed optimization for self-concordant empirical loss. In International Conference on Machine Learning (ICML), 2015. 1,8
Yuchen Zhang, John C. Duchi, and Martin J. Wainwright, Communication--ffiiiienn algorithms for statistical optimization. Journal of Machine Learning Research, 14:3321-3363, 2013. 5, 6, 8
Yuchen Zhang, John Duchi, and Martin Wainwright. Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates. Journal of Machine Learning Research, 16: 3299-3340, 2015b. 8
11

---

Published as a conference paper at ICLR 2020
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint arXiv:1806. 00582, 2018.
Shun Zheng, Fen Xia, Wei Xu, and Tong Zhang. A general distributed dual coordinate optimization framework for regularized loss minimization. arXiv preprint 1604. 1604.03663, 2016.
Fan Zhou and Guojing Cong. On the convergence properties of a k-step averaging stochastic gradient descent algorithm for nonconvex optimization. arXiv preprint arXiv: 2017. 2,4,7
Hankz Hankui Zhuo, Wenfeng Feng. Qian Xu, Qiang Yang, and Yufeng Lin, Federated reinforcement learning, arXiv preprint arXiv:1901.08277) 2019.
A PROOF OF THEOREM
We analyze FedAvg in the setting of full device participation in this section.
A.1 ADDITIONAL NOTATION
Let w be the model parameter maintained in the k-th device at the t-th step. Let Ig be the set of global synchronization steps, i.e., Ig {n.E 1.2...... If + Ig, ie., the time step to communication, FedAvg activates all devices. Then the update of FedAvg with partial devices active can be described
k Vi+1 = w - m VF.
(9)
if + 1 Ig.
k 1+1
(10)
Σ PLvta
if 1 Ig.
Here, an additional variable v 1 is introduced to represent the immediate result of one step SGD update from w We interpret w as the parameter obtained after communication steps (if possible).
In our analysis, we define two virtual sequences Vi E P& and w. = =E P&w This motivated by (Stich, 2018). Ve+1 results from an single step of SGD from w.. When t + 1 & Ig. both are inaccessible. When + 1 E Lg, we can only fetch W For convenience, we define g, Σk=1 FF and g: Σ V (w,, (t). Therefore, Vi+1 = W. 7kgt and Eg: ge-
A.2 KEY LEMMAS
To convey our proof clearly, it would be necessary prove certain useful lemmas. We defer the proof of these lemmas to latter section and focus on proving the main theorem.
Lemma (Results of one step SGD), Assume Assumption and 2. If S TL we have
E V4I w01 < M W. w01l + + - Bell +6 2E
> ph W: will"
km
where I F - 2
Lemma 2 (Bounding the variance). Assume Assumption 3 holds. It follows that
E Elg. 8.113 Σ oo
Lemma (Bounding the divergence of { {w:) }). Assume Assumption 4, that Th is non-increasing and N S 21/+ for all & 0. follows that
Pk We
w
<
(E
12

---

Published as a conference paper at ICLR 2020
A.3 COMPLETING THE PROOF OF THEOREM 1
Proof. It is clear that no matter whether / + E Zr or / + 1 & Zz. we always have Wx+1 Ve41- Let A = E Wi+1 - w*ll From Lemma 1, Lemma 2 and Lemma 3, it follows that
A+t1 & (1- - + BB
(11)
where
B
Σ
2 P 6LL 8(E G)?
For diminishing stepsize, 1): and f) I 2T++E- We will prove A, S 7 where max 3 8 (r + 1)
B for some B > and > 0 such that 7 S minf TL z
We prove it by induction. Firstly, the definition of v ensures that it holds for 1. Assume the conclusion holds for some t, it follows that
A S (1 1;
+ m B
2
Bu
B
t+, 7)
t 8+?
(t 7)²
++
BB
8p - 1 (1 (1+
(1 71+
7)+
++
Then by the strong convexity of F(.),
L
L
E[ (w:) F
2
2
7
Specifically, if we choose B = n 7 max 18 - 1, }} and denote = 41- then and
E[F( F S 7t 4
2k
B
+ 22L1)
A.4 DEFERRED PROOFS OF KEY LEMMAS
Proof of Lemma
Notice that Vi+1 W. T/ then
|++1 - w²12 |w;
7) w- - -1 + 7/: |2
W. w mg
21 (w: w 1/.8. B, [:
+1/ lg:
1
(12)
A2
Note that EA2 We next focus bounding Ar. Again we split A into three terms:
w. nBdl w. w* 2m (w,
B.
|g
(13)
B
B2
From the the T-smoothness of FR((),, it follows that
VF (w?) 2 < 2L (Fx (wt) FE).
(14)
By the convexity of 2 and eqn. (14), we have
B, - n2 I
Σ
pk
V (w?)) 12 $ 2L Σ Pk (Fx(w.) FE)
13

---

Published as a conference paper at ICLR 2020
Note that
Bi -m (w, W .ge)
-277: Σ
Pk (: w VF (w\))
A=
N w/, (F&(w() - 27t
N (w? - w", V VF(())))
= -2
ph W.
(15)
By Cauchy-Schware inequality and AM-GM inequality, we have
2 -2(we - - V (w)) - T/t
We will" + +m |I (w/)]l².
(16)
By the j-strron convexity of Fe(.), we have
1 -wt w", F. (w+)) S (Fx (w/) - Fl(w"))
[w w=1/²-
(17)
2
By combining eqn. (13), eqn. (15), eqn. (16) and eqn. (17), it follows that
A1 |W, w "1/..l 2 < [w:- w=11 + 2T
2
Ph (Fa(w!) - Fi)
W. w |1 + 770
V (w)
+ 1)
pk
1/t
N
2/h
Fe (w²) - (ww)
+ 4
w - w w11)
2
k=1
= (1 pmmi
|| w=1 +
We w ||
A=
N + 4Tm
N 2n D
Σ pt (FL(w;)) k=1
Fi)
Pk (Fx (w?) Fr((w))
k=1
where we use eqn. (14) again.
We next aim to bound C. We define "1 2m/( (1 2Lm)). Since nt S t 't S 7t. S 2m. Then we
split C' into two terms:
N Σ k=1
N
C = 21 - 2LT)))
ph (Fa(w!) FT) + 2m
Pk (Fr(w")- FF)
k=1
N
Pk (Fi(WW)) 1T)) +(21: - 7+) Σ
Pk (F" -FE)
#
1=1
N
Ph (Fx(w?) - F*) +
where in the last equation, we the notation
T= = Pk (F*-Ft)
Ft) F* >
14

---

Published as a conference paper at ICLR 2020
To bound D, we have
N
N Σ
(Fa(w()) - Fr
Phe (Fx(w)) - Fa(
Phe F*)
1=1
ps (VF((w.)) w w.) + (F(w.) F*)
N
- | well] + (F(w)) F*)
T1 [V.
Pk
2 k=
w w.ll) + (F(w.) - F*)
Σ Ph (F. Fi) k=1
27
where the first inequality results from the convexity of (x).), the second inequality from AM-GM inequality and the third inequality from eqn. (14).
Therefore
l/ woll?
C=
7
Pk
MiL (Fi FK)
7a (F(w.)
FF) + 4L
27/;
N
N
= = Io - 1)
Σ
Pk (F&(we) F*) + (4Iaf + T.
+
7t
Ph w w.ll
2TT
k=1
s 6L r + Σ Pk I well
where in the last inequality, we use the following facts: (1) nL S -3 S 0 and
.
Pk (F& (Fx(w.) F*) = F(w.) - F 1.
(2) r 0 and 4Ta + nhth L. I 6n I. and (3)
27p
Recalling the expression of A, and plugging C' into it, we have
A W: w 17:g.11"
$ (1 pm)) [ - w+1 -|
+ Ph W. w + 6n, LT
(18)
Using eqn. (18) and taking expectation on both sides of eqn. (12), we erase the randomness from stochastic gradients, we complete the proof.
Proof of Lemma 2. From Assumption 3, the variance of the stochastic gradients in device At is bounded by of. then
E lg
g E
Σ Pk (VF((W
N VF((wi) vAb(w/)) -VAtt/)))
k=1
p 2 k=1
L
Proof of Lemma 3. Since FedAvg requires a communication each steps. Therefore, for any 2 0. there exists a to such that f < F and w Wto for all & = 1,2, .... N. Also,
15

---

Published as a conference paper at ICLR 2020
the fact that ni is non- non-increasing and Mo
2m for all t to S E - 1, then
N
N
E
Pk
W.
Pk ll(w;
wooo - (w, w
k=1
N
12
1| - -wrol
1-1
P&
Σ (E 1)m2
(
t=
1-1
Σ (E - 1y1i G2
Pk
tm
Σ Pig (E - 1)
S (E 1E
B PROOFS OF THEOREMS 2 AND 3
We analyze FedAvg in the setting of partial device participation in this section.
B.1 ADDITIONAL NOTATION
Recall that w is the model parameter maintained in the k-th device at the f-th step. Ig = {nEE n 2, ... } the time to communicate, i.e., / ++ 1 E Ir, the scenario considered here is that FedAvg randomly activates a subset of devices according to some sampling schemes. Again, C. = E PA V (w))
is the set of global synchronization steps. Unlike the setting in Appendix A, when it is
and g: = k= Pk Fk (w <h) Therefore, V W.- ml.g and Eg. = gt.
Multiset selected. All sampling schemes can be divided into two groups, with replacement and the other without replacement. For those with replacement, it is possible for a device to be activated several times in a round of communication, even though each activation is independent with the rest. We denote by He the multiset selected which allows any element to appear more than once. Note that H4 is only well defined for E Ig. For convenience, we denote by S. HN((,E) the most recent set of chosen devices where (t,, E) mn S t, n Ig}.
Updating scheme. Limited to realistic scenarios (for communication efficiency and low straggler effect), FedAvg first samples random multiset S, of devices and then only perform updates on them. This make the analysis little bit intricate, since S, varies each E steps. However, we use thought trick to cireumvent this difficulty. We assume that FedAvg always activates all devices at the beginning of each round and then uses the parameters maintained in only few sampled devices to produce the next-round parameter. It is clear that this updating scheme is equivalent to the original. Then the update of FedAvg with partial devices active can be described as: for all k [N].
1+1 w
17: F c!),
(19)
v
if t + 1 IE, if + 1E Ig.
w +11 samples S441 and average (vit Jees.:.
(20)
Sources of randomness. In our analysis, there are two sources of randomness. One results from the stochastic gradients and the other is from the random sampling of devices. All the analysis in Appendix A only involve the former. To distinguish them, we use the notation Es, (.), when we take expectation erase the latter type of randomness.
16

---

Published as a conference paper at ICLR 2020
B.2 KEY LEMMAS
Two schemes. For full device participation, we always have Wi+1 V++1- This is true when ++1 E LE for partial device participation. When /+1 E Zy, we hope this relation establish in the sense of expectation. To that end, we require the sampling and averaging scheme to be unbiased in sense that
Es W4+1
Vi+1-
We find two sampling and averaging schemes satisfying the requirement and provide convergence guarantees.
The server establishes S by i.i.d. with replacement sampling an index A: E (1,.... .N3 with probabilities " PN for K times. Hence S is multiset which allows element to occur more than once. Then the server averages the parameters by w * Eies vê+1- This is first proposed in (Sahu et al., 2018) but lacks theoretical analysis.
(II)
The server samples S(+1 uniformly in without replacement fashion. Hence each element in S1+1 only occurs once. Then server averages the parameters by w = -kES Ph: K 1+1-
N vk
Note that when the p are not all the same, one cannot ensure ExES.n Pk K
Unbiasedness and bounded variance. Lemma 4 shows the mentioned two sampling and averaging schemes are unbiased. In expectation, the next-round parameter (i.e., Wt+1) is equal to the weighted average of parameters in all devices after SGD updates (i.e., Vi+1). However, the original scheme in (McMahan et al., 2017) (see Table 1) does not enjoy this property. But is very similar to Scheme except the averaging scheme. Hence analysis cannot cover the original scheme.
Lemma 5 shows the expected difference between V and W is bounded. Es, l| W.+ is actually the variance of Wr+1-
Lemma 4 (Unbiased sampling scheme). Ift + IF, for Scheme I and Scheme II, we have
Es, (W++1) = Vi+1.
Lemma 5 (Bounding the variance of w.). For t t 1 I, assume that Th. is non-increasing and x 21 for all i. 2 0. We have the following results.
(1) For Scheme I, the expected difference between V4+1 and We+1 is bounded by
Es. V++1 W < K
GE
(2) For Scheme II assuming P1 = P2 ... PN N, the expected difference between Ve+1 and Wi+1 is bounded by
N K 4 N K T G
Es. | 2
B.3 COMPLETING THE PROOF OF THEOREM 2 AND 3
Proof. Note that
W w w11 || Vet1 + Ve+1 w²12
|| vetill |i+11 w
2(WH1
V41 V++1
w
Aa
When expectation is taken over S441, the last term (Ag) vanishes due to the unbiasedness of W,+1-
& Iz. A₁ vanishes since W Ve+1- We use Lemma 5 to bound Ag. Then follows that
E|[wett1 w1
(//)///w w + B.
17

---

Published as a conference paper at ICLR 2020
If 1 E Ig, additionally Lemma 5 to bound A1. Then
E W1+1
w*1l = E Wi+1 V4+1 + + w" 11
I (1 17 LE W. w'll + n/ (B + C)2
(21)
where C' is the upper bound of Es, Vi+1 W (C is defined in Theorem and 3).
%
The only difference between eqn. (21) and eqn. (11) the additional C. Thus we can use the same argument there to prove the theorems here. Specifically, for diminishing stepsize, Y) = 1+7 for some 3 > and > 0 such that I <min x at) ar and тn S 21t+E, can prove
8
We+1 - w S स where v max (B+C) Bp-1 (r + 1) W w w-1133
Then by the strong convexity of F(.).
L D.
L
[[F((::] F
2
2 7 7
Specifically, if we choose 3 = #.? m8 - 1, }}} and denote x = L. then
= 1 7+1
and
2k
B +
+ 21| w'1)²
B[F(w,)] - F S 7 +t
B.4 DEFERRED PROOFS KEY LEMMAS
Proof of Lemma 4. We first give key observation which is useful prove the followings. Let {x:)i=1 1N denote any fixed deterministic sequence. We sample a multiset S, (with size K) by the procedure where for each sampling time, sample zy with probability qu for each time. Pay attention that two samples are not necessarily independent. We only require each sampling distribution identically, Let S (in,... ,ix] C [N] (some in ''s may have the same value). Then
K
N
Es.
Σ 2g = Es. Σ kES.
KES Fi, =
k=1
For Scheme I, qt = and for Scheme II, ok N. It is easy to prove this lemma when equipped with this observation.
Proof of Lemma 5. We separately prove the bounded variance for two schemes. Let S [ik]" denote the multiset of chosen indexes.
(1) For Scheme I, W = 1 EK v Taking expectation over S we have
K
N En Pk | - -
Es, W Ve+1 F.S.
Σ v V
(22)
K2
K
where the first equality follows from v are independent and unbiased. To bound eqn. (22), time to = t- - E + +++ E Ig is the communication time, which implies { Eg ]N is identical. Then
the same argument in Lemma Since 1 E Zz. we know that the
N
Σ Pk v Vetil =
Σ Pk [I We.) - (Ve+1 w
Pk v wrol?
k=
18

---

Published as a conference paper at ICLR 2020
where the last inequality results from Σ |||x|| Similarly, we have
Wio) V
W and E|i Ex||? 1
N
Es.
Wi+1
Ve41ll
P&
veti -woll?
N
P&lE
v - -
K
k=1
pi
E
E V.l Et)l
K
i=to
E
Tho
G2
G
K
K
where in the last inequality we use the fact that Q) is non-increasing and The 2mh
(2) For Scheme II, when assuming P1
P2
PN
+ we again have w+11 R Ei=l K
V41
N Σ fff 8.)
Es, We+1 - Vo+1l12 Es.
Σ
Vit1 - Vi+1
Es.
- -v(+1 Fetil
K
iE5
P(i E Si+1) 1Ive+ - - + Σ
P (i,j E S441) (V - VeLi, v441 - vet1)
K2
iE|N]
N
-V+111 ΣΣ 1-1
-
KN(N - (V - V441.2441 - V
KN
i
K(N- -1- 1) (1 (1-
K N
Σ 1
where we use the following equalities: (I) E S441) = and (i,j S441 K(K-1)
N(N-1) for all
i * j and (2) EieM llvi+2 - -e+ill +
(vi+1 -V+11, v/41 Ve+1) =0.
Therefore,
N
N
K
E We41 - V
E
V441l
K(N - 1)
N
N
1=
N
K
E
N
wtoll 11
K(N - 1)
N
N
N
K
1
4n
E2
K(N-1)
N
where in the last inequality we use the same argument in (1).
C THE EMPIRICAL RISK MINIMIZATION EXAMPLE IN SECTION 4
C.I DETAIL OF THE EXAMPLE
Let > be positive integer. To avoid the trivial case, we assume N > Consider the following quadratic optimization
min F(w)
W Aw
Tb w/ + / w 2
(23)
w
2N
19

---

Published as a conference paper at ICLR 2020
where A ((N++))(NN+))) w, b I Np+1 and μ >> 0. Specifically, let b e1 - (1,0, ...0,....0000 ")) and A be a symmetric and tri-diagonal matrix defined by
2, -1,
[ +1 11, - and i.j Np,
(A)..
(24)
0, otherwise,
where i. are row and column indices, respectively. We partition into a sum of N symmetric
matrices (A = Σx= A&) and b into b Σx= bą- Specifically, we choose b₁ = b = e₁ and b2 -... by 0. To give the formulation of A₂ 's we first introduce series of sparse and
symmetric matrices Bg (1 S k < N):
1,
i= i= {kk - 1)p + 1. + +1}.
2,
and (k 1)p + si<ijj-
i,j < kp +1
(BE)a
(25)
-1,
i - i| = 1 and i.j E [[k - + 1]
otherwise.
B. (2 k ( and AN = Bx ENpti, where E,y is the matrix where only the (i. entry is one and the rest are zero.
Now Ag 's are given by A B1+ E1,1, A
Back to the federated setting, distribute the k-th partition (Ax, by) to the k-th device and construct its corresponding local objective by
Fi w
W A 2b w + wl/w12 2
(26)
In the next subsection (Appendix C.3), we show that the quadratic minimization with the global objective (23) and the local objectives (26) is actually a distributed linear regression. In this example, training data are not identically but balanced distributed. Moreover, data each device are sparse in the sense that non-zero features only occur in one block. The following theorem (Theorem 5) shows that FedAvg might converge to sub-optimal points even if the learning rate is small enough. We provide numerical illustration in Appendix C.2 and a mathematical proof in Appendix C.4.
Theorem 5.
In the above problem of the distributed linear regression, assume that each device computes exact gradients (which are not stochastic). With a constant and small enough learning rate 1j and F > FedAvg converges to sub-optimal solution, whereas FedAvg with (iee, gradient descent) converges to the optimum. Specifically, in quantitative way, we have
(E (E-1) A1
|
16
where w is the solution produced by FedAvg and w the optimal solution.
C.2 NUMERICAL ILLUSTRATION ON EXAMPLE
We conduct a few numerical experiments illustrate the poor performance of FedAvg the
example introduced in Section 4. Here we set N 5,p 4, l = 2 x 10-4 The annealing
scheme of learning rates is given by π) 5+t-a where is the best parameter chosen from the set {10-* 2, 10 10-6).
1/5
C.3 SOME PROPERTIES OF THE EXAMPLE
Recall that the symmetric matrix A (NND+)))(N++1)) is defined in eqn. (24). Observe that A is invertible and for all vector w E NN+1
Np+1
Np
Np (w: - w ( S 4/|w
W W
2
2
w,Wi+1
w2 w w
(27)
which implies that 0 < A 4I.
20

---

Published as a conference paper at ICLR 2020
Em
0.00
E=1
-0.02
E=5
E=5
8= 10
0.02
E= 10
C=
== 50
Global loss
100
Gilobal loss
-0.04
== 100
optimal
optimal
-0.06
-0.06
-0.08
-0.08
10
10
10
10
10
Round (TIE)
Round (TIE)
(a) Fixed learning rates
(b) Decayed learning rates
Figure 2: The left figure shows that the global objective value that FedAvg converges is optimal unless E = 1. Once we decay the learning rate, FedAvg can converge to the optimal even E >>>
The sparse and symmetric matrices B& (1 S N) defined in eqn. (25) can be rewritten
0 1xx (k- 1)p
-1
2
(Ba)
-1
2
-1
-1
1
(p+1)x(p+1)
0 ON -))xx(XxX (N- kk)p
From theory of linear algebra, it is easy to follow this proposition.
Proposition 1. By the way of construction, A 's have following properties:
1. A is positive semidefinite with | S 4;
2. rank(Ag)
rank(AN p and rank(A,) rank p=
3. For each k. there exist matrix X₃ E RTxx(No+1) such that A₁; = =X, Xx where T rank(Ag). Given any k, each row of X has non-zero entries only on a block of coordinates,
namely Ig = {(k: 1)p + 1, (k 1)p + 2. ... kp+11 1}. As a result, = E A
X X, where X = .'..... x E (N++))
4. w A the global minimizer of problem eqn. (23), given by (w"); = 1 Npt2 (1 Np 1). Let w
&N++1 then A W X X, b
p-1
(N-1)p
From Proposition we can rewrite these local quadratic objectives in form of ridge linear regression. Specifically, for 1,
Fi(w) w A 2b w =/]lw|/]]
[w X X
2w x X w [[]
| (w wl
+
21

---

Published as a conference paper at ICLR 2020
where C' is some constant irrelevant with w). For 2 2 N,
Fx(w)= - 2 w A 2bb w + /
1 ?ullw]?
X xx al
Similarly, the global quadratic objective eqn. (23) can be written as F(w) 2N X (w w > jullw//²
Data in each device are sparse the sense that non-zero features only occur the block In of coordinates. Blocks neighboring devices only overlap one coordinate, i... [Ig MIx+1| 1. These observations imply that the training data in this example not identically distributed.
The k-th device has ти (= p p 1) non-zero feature vectors which are vertically concatenated into the feature matrix Xg. Without loss of generality, we can assume all devices hold + 1 data points since can always add additional zero vectors expand the local dataset. Therefore 71 = _... n2 = p + in this case, which implies that the training data in this example is balanced distributed.
C.4 PROOF OF THEOREM 5.
Proof of Theorem 5, To prove the theorem, we assume that (i) all devices hold the same amount of data points, (ii) all devices perform local updates in parallel, (iii) all workers rate n and (iv) all gradients computed by each device make use of its full local dataset (hence this case is deterministic optimization problem). We first provide the result when μ
the same learning
For convenience, we slightly abuse the notation such that w, is the global parameter at round t rather than step Let (*()) the updated local parameter k-th worker round Once the first worker that holds data (A,, by) runs E step of SGD on F1 (w) from we, it follows that
E-1
w (1)
(I mA1) We + 1
Σ
(I-
--mAAbbb
For the rest of workers, we have w(()) nA,) 2 W. (2SkSM) Therefore, from the algorithm,
N
E-1
Wi+1
N
61
(K)
N
Σ [I nA W. +
N
"
Σ 1=0
(I
A
1=1
Define p A 11 ΣN
ii= IT A Next we show that when
<
4. we have p < 1. From
1
and A, = for V [N]. This means Then for any E Np+ and ||>||2 = 1, we have x decreasing when E is increasing. Then
Proposition 1, A 2
11 A for all [N].
TT(L (I A
< 1 and is monotonically
N
x
nA
xSXT
[ nA.)) x
N 1=1
N
1=1
=x
I (I-
A
x<1
N
since 0 < A 3 4I means (I N A) x I.
Then ||w:-1 welle pl(w. 1or-ww1ll w S p² || wwll2. By the triangle incquality,
n- |/e44n well2
n-1
0 [| wolla s p² |w wolla
| W
p
which implics that (Wi)e21 is a Cauchy sequence and thus has a limit denoted by w We have
N
B-1
w =
n
Σ I-
nA
(28)
N
N
==1
22

---

Published as a conference paper at ICLR 2020
Now discuss the impact of E.
When E. = 1, follows from eqn. (28) that w A- w", i.e., FedAvg converges the global minimizer.
(2) When E 0o, lim 11 E
Ei (I A1) A = w and lim
E-100 N - x) I A (1- 11 where M 2IN-2)p+Ix(N-220
diag( - + Ip symmetric matrix. Actually M is almost diagonal matrix in the sense that there are totally N -2 completely the same matrices (i.e., p+1 eee E R(++1)x(++)) placed on the diagonal of M but each overlapping only the lower right corner element with the top left corner element of the next block. Therefore w (1,..,, VI..... VVN (V-22)p+10 2,1+ 0,... 0)2 where V M) -1
is some
P
From (4) of Proposition
different from w*
(3) When 2 S < co, note that
w
N nA,)*
B-1 7
N --.aaa))
1
1 N
I -
-I-nAA) 2-0
I
Σ
I -
w".
N
N
(29)
The right hand side of the last equation cannot be zero. Quantificationally speaking, we have the following lemma. We defer the proof for the next subsection.
Lemma If the step size nj is sufficiently small, then this example, we have
E - 1)m A1
w
(30)
16
Since A₁ + and w is dense, the lower bound in eqn. (30) is not vacuous.
Now have proved the result when μ 0. For the case where μ 0, replace A, with A, + μI and assume < 44μ instead of the original. The discussion on different choice E is unaffected.
C.5
PROOF OF LEMMA
Proof. We will derive the conclusion mainly from the expression eqn. (29). Let f()) be a function of
7). We say a matrix T (((()) and only there exist some positive constants namely C1 and
C2 such that C1 f |T| Cn) for all n 0. In the following analysis, we all consider the regime where is sufficiently small.
Denote by V = Σ A,, First we have
E(E E(E - 1), 1 A + +
I
=
=1
EmA
N
N
1=1
En
E(E
- 1)
A
v O
(31)
N
2N
Then by plugging this equation into the right hand part of eqn. (29), we have
E-1
N
I
A
I
AA)
E-1
En A
E(E 11 v + 0
N
Σ
I In
+ +072))A
-
N
2N
1=0
[(EE
V
A1A) + +
N
23

---

Published as a conference paper at ICLR 2020
Second from eqn. (31), we have that
I
I
1 N I N
nA,)
-1
En
N A - (11) En
N
Plugging the last two equations into eqn. (29), we have
A - 0(1)) r
E(E
Iw
w
(V AAA)) w'
Em
N
11 -v - A1A) + O(n)) w*
2
(E
1)m
I(V - AIA)w"l
16
E 1)
16
where the last inequality holds because (i) we require 7) to be sufficiently small and (ii) |A-1x] |||x|| for any vector x as result of < A|| S 4. The last equality uses the fact (i) V AA
A Ei= A, and (ii) A 0 for any i 2 3.
D EXPERIMENTAL DETAILS
D.I EXPERIMENTAL. SETTING
Model and loss. We examine our theoretical results multinomial logistic regression. Specif- ically, let f(w; x.) denote the prediction model with the parameter w (W, b) and the form xw) sofumax(W2 (Wx; b). The loss function is given by
1 Σ
F F(w)
CrossEntropy (f(w:x)).)) + X /
This is convex optimization problem. The regularization parameter is set À 10-4
Datasets. We evaluate our theoretical results on both real data and synthetic data. For real data, we choose MNIST dataset (LeCun al., 1998) because of its wide academic To impose statistical heterogeneity, we distribute the data among N = 100 devices such that each device contains samples of only two digits. To explore the effect of data unbalance, we further vary the number of samples among devices. Specifically, for unbalanced cases, the number of samples among devices follows power law, while for balanced cases, we force all devices to have the same amount of samples.
Synthetic data allow us to manipulate heterogeneity more precisely. Here we follow the same setup as described in (Sahu et al., 2018). particular, we generate synthetic samples (X,, Y,) according to the model y argmax (softmax W & + bx)) with E T800 W E IR 10x60 and by E R.00 where X, R x and Y, E "x We model each entry of W. and D as N(u,, 1) with μıg ~ (0 a). and (Ix); NVu, ştz) with Us (B, 1) and B₃ NO, 3). Here and 3 allow for more precise manipulation of data heterogeneity: controls how much local models differ from each other and 3 controls how much the local data at each device differs from that other devices. There N 100 devices in total. The number of samples ny in each device follows power law, i.e., data are distributed in an unbalanced way. We denote by synthetic (o, (3) the synthetic dataset with parameter a and B.
We summarize the information of federated datasets in Table 2.
Experiments. For all experiments, selected devices run E steps of SGD in parallel. We decay the learning rate at the end of each round by the following scheme πソ I+ where 7/o chosen from the set {1, 0. 0.013. We evaluate the the corresponding global objective. For fair
initialize all runnings with Wo 0. In each round, all
no
averaged model after each global synchronization comparison, we control all randomness in experiments so that the set of activated devices is the same across all different algorithms one configuration.
24

---

Published as a conference paper at ICLR 2020
Table 2: Statistics federated datasets
Dataset
Details
# Devices (N)
#Training samples (n)
Samples/device
mean
std
balanced unbalanced
100
54200
542
MNIST
100
62864
628
800
0, B 0
100
42522
425
1372
Synthetic Data
αx 1,
100
27348
273
421
D.2
THEORETICAL VERIFICATION
The impact of E. From our theory, when the total steps 7 is sufficiently large, the required number of communication rounds achieve a certain precision
EG K
Ex
120² + LI R
T//E
EG2
F.
which is function of E that first decreases and then increases. This implies that the optimal local step E exists. What's more, the Te/ E evaluated at E*
G
N Σ 02 + LT + K02
o
which implies that FedAvg needs more communication rounds to tackle with severer heterogeneity.
To validate these observations, test FedAvg with Scheme on four datasets listed in Table 2. In each round, we activate = 30 devices and set 7/u = 0.1 for all experiments this part. For unbalanced MNIST, we use batch size b 64. The target loss value is 0.29 and the minimum loss value found is 0.2591. For balanced MNIST, we also use batch size b = 64. The target loss value is 0.50 and the minimum loss value found is 0.3429. For two synthetic datasets, we choose b = 24. The target loss value for synthetic(O.0) is 0.95 and the minimum loss value is 0.7999. Those for synthetic(1,1] are 1.15 and 1.075.
The impact of K. Our theory suggests that larger K may accelerate convergence since Te/ contains a term O EG We fix E and f/u = 0.1 for all experiments in this part. We set the batch size to for two MNIST datasets and 24 for two synthetic datasets. We test Scheme for illustration. Our results show that, matter what value K is, FedAvg converges. From Figure 3, all the curves each subfigure overlap a lot. To show more clearly the differences between the curves, we zoom in the last few rounds in the upper left corner of the figure. It reveals that the curve of large enough K slightly better. This result also shows that there no need to sample as many devices possible in convex federated optimization.
Sampling and averaging schemes. We analyze the influence of sampling and averaging schemes. As stated in Section 3.3, Scheme iid samples (with replacement) K indices with weights Pk and simply averages the models, which is proposed by Sahu et al. (2018). Scheme II uniformly samples (without replacement) K devices and weightedly averages the models with scaling factor N/K. Transformed Scheme II scales each local objective and uses uniform sampling and simple averaging. We compare Scheme I, Scheme and transformed Scheme II, as well as the original scheme (McMahan et al., 2017) on four datasets. We carefully tuned the learning rate for the original scheme. In particular, we choose the best step size from the set {0.1, 0.5, 0.9, 1.1]. We did not fine tune the rest schemes and пдo 0.1 by default. The hyperparameters are the same for all schemes: E = 20, = 10 and = 64. The results are shown Figure Ic and 1d.
Our theory renders Scheme the guarantee of convergence in common federated setting. As expected, Scheme performs well and stably across most experiments. This also coincides with the findings of Sahu et al. (2018). They noticed that Scheme I performs slightly better than another scheme: server
25

---

Published as a conference paper at ICLR 2020
K-10
10
K-30
K-
2.0
K-50
20
K-30
Giobal lose
K- 100
Glabal loe
0:37
K- 100
1.0
0.5
0.5
Round (7TE)
Round (TT))
(a) Balanced MNIST
(b) Unbalanced MNIST
K-10
2.50
K-
K-30
K-30
K-50
50
K-70
K070
Globall boss
K- 100
Globalos
2.00
K-
1.75
1.25
50
100
150
200
100
150
200
Round
Round (178)
(c) Synthetic(O,, 0)
(d) Synthetic(1, I)
Figure 3: The impact of K four datasets. To show more clearly the differences between the curves, we zoom in the last few rounds the upper left corner of the box.
first uniformly samples devices and then averages local models with weight p&/ Eles, Pt. However, our theoretical framework cannot apply to it, since for E I. Es, w. V, does not hold in general.
Our theory does not guarantee FedAvg with Scheme could converge when the training data are unbalanced distributed. Actually, if the number of training samples varies too much among devices, Scheme II may even diverge. To illustrate this point, we have shown the terrible performance on mnist anba 1 lanced dataset in Figure 1b. In Figure 4, we show additional results of Scheme II on the two synthetic datasets, which are the most unbalanced. and п/ 0.1 for these experiments. However, transformed Scheme II performs well except that has a lower convergence rate than Scheme
choose b 24, K 10, 10
Original
Original
Schsmel Schemell II T-Scheme
Schemel
Schome II T-Schome
Glockal hea
Global
2-
50
100
1.0
200
30
100
150
200
Round (77E)
Bound(TiE
(a) Synthetic(0.0)
(b) Synthetic(1.1)
Figure 4: The performance of four schemes on two synthetic datasets. The Scheme I performs stably and the best. The original performs the second. The curve of the Scheme fluctuates and has no sign of convergence. Transformed Scheme II has lower convergence rate than Scheme I.
26


Reviews:
[{"review_id": "rkl4PWCsKB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 presents convergence rates for straggler-aware averaged SGD for non-identically but independent distributed data. The paper is well-written and motivated with good discussions of the algorithm and the related works. The proof techniques involve bounding how much worse can the algorithm do because of non-identical distribution and introduction of stragglers into the standard analysis of SGD-like algorithms. The presented theory is useful, and also provides new insights such as a new sampling scheme and an inherent bias for the case of non-decaying step size. The empirical evaluation is adequate and well-presented. I think this paper is a strong contribution and should spark further discussions in the community. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SyeCOwkk9r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "Federated learning is distinguished from the standard distributed learning in the following sense: \n1) training is distributed over a huge number (say N) of devices and communication between the central server and devices are slow.\n2) The central server has no control of individual devices, and there are inactive devices that does not respond to the server; full participation of all devices is unrealistic.\n3) The local data distribution at each device is different from each other; i.e., the data is non-iid.\n\nDue to property 1), communication-efficient algorithms such as Federated Averaging (FedAvg) have been proposed and studied. FedAvg runs SGD in parallel on K (≤N) local devices using their local datasets, and updates the global parameter after E local iterations by aggregating the updates from the local devices.\n\nProperties 2) and 3) makes analysis of FedAvg difficult, and previous results have proven convergence of FedAvg assuming that the data is iid and/or all devices are active. In contrast, this paper studies FedAvg on the non-iid data and inactive devices setting and shows that, with adequately chosen aggregation schemes and decaying learning rate, FedAvg on strongly convex and smooth functions converges with a rate of O(1/T). \n\nOverall, I enjoyed reading this paper and I would like to recommend acceptance. This is the first result showing convergence rate analysis of FedAvg under presence of properties 2) and 3), which is a nontrivial, important, and timely problem. The paper is well-written and reads smoothly, except for some minor typos. The convergence bounds provide insights of practical relevance, e.g., the optimal choice of E, the effect of K in convergence rate, etc. The authors also provide empirical results supporting their theoretical analysis.\n\nSome questions I have in mind:\n- What is \"transformed Scheme II\"? Is it the scaling trick described at the end of Section 3.3? The name appears in the experiment section before being defined.\n- What happens if we choose \\eta_t that is decaying but slower than O(1/t), say O(1/\\sqrt t)? Can convergence be proved? If so, in what rate?\n\nMinor typos:\n- Footnote 3: know -> known\n- Assumptions 1 & 2: f in $f(w)$ is math-bold\n- Choice of sampling schemes: \"If the system can choose to active...\" -> activate\n- mnist balanced and mnist unbalanced: the description after them suggests they should be switched\n- Apdx D.1: widely -> wide, summary -> summarize", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkxft2PptH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 analyzes the convergence of FedAvg, the most popular algorithm for federated learning. The highlight of the paper is removing the following two assumptions: (i) the data are iid across devices, and (ii) all the devices are active. For smooth and strongly convex problems, the paper proves an O(1/T) convergence rate to global optimum for learning rate decaying like 1/t with time. It is also shown that with constant learning rate eta, the solution found can be necessarily Omega(eta) away from the optimum (for a specific problem instance), thus justifying the decaying learning rate used in the positive result.\n\nFederated learning has been an important and popular research area since it models a highly distributed and heterogeneous learning system in real world. Previous theoretical analysis of FedAvg was quite scarce and either made the iid data assumption or required averaging all the devices. This work is the first to prove a convergence guarantee without these two assumptions. In particular, it only requires averaging a (random) subset of devices each round, which is much more realistic than averaging all.\n\nI don't quite have an intuition for why you need strong convexity. I hope the authors could explain this in words and maybe comment on what are the challenges of removing this assumption.\n\n\n------\nThanks to the authors for their response.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This manuscript analyzes the convergence of federated learning wit hstragellers, and provides convergence rates. The proof techniques involve bounding the effects of the non-identical distribution due to stragglers and related issues. The manuscript also includes a thorough empirical evaluation. Overall, the reviewers were quite positive about the manuscript, with a few details that should be improved. 
Decision: Accept (Talk)