Federated Learning's Blessing: FedAvg has Linear Speedup
Authors: Zhaonan Qu
Kaixiang Lin
Zhaojian Li
Jiayu Zhou
Zhengyuan Zhou
Venue:  (2021)
Keywords: Federated learning

Abstract: Federated learning (FL) learns a model jointly from a set of participating devices without sharing each other's privately held data. The characteristics of non-\textit{i.i.d.} data across the network, low device participation, high communication costs, and the mandate that data remain private bring challenges in understanding the convergence of FL algorithms, particularly in regards to how convergence scales with the number of participating devices. In this paper, we focus on Federated Averaging (FedAvg)--arguably the most popular and effective FL algorithm class in use today--and provide a unified and comprehensive study of its convergence rate. Although FedAvg has recently been studied by an emerging line of literature, it remains open as to how FedAvg's convergence scales with the number of participating devices in the fully heterogeneous FL setting--a crucial question whose answer would shed light on the performance of FedAvg in large FL systems. We fill this gap by providing a unified analysis that establishes convergence guarantees for FedAvg under three classes of problems: strongly convex smooth, convex smooth, and overparameterized strongly convex smooth problems. We show that FedAvg enjoys linear speedup in each case, although with different convergence rates and communication efficiencies. While there have been linear speedup results from distributed optimization that assumes full participation, ours are the first to establish linear speedup for FedAvg under both statistical and system heterogeneity.  For strongly convex and convex problems, we also characterize the corresponding convergence rates for the Nesterov accelerated FedAvg algorithm, which are the first linear speedup guarantees for momentum variants of FedAvg in the convex setting. To provably accelerate FedAvg, we design a new momentum-based FL algorithm that further improves the convergence rate in overparameterized linear regression problems. Empirical studies of the algorithms in various settings have supported our theoretical results.

Under review as a conference paper at ICLR 2021
FEDERATED LEARNING'S BLESSING: FEDAVG HAS LINEAR SPEEDUP
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning (FL) Icarns a model jointly from a set of participating devices without sharing each other's privately held data. The characteristics of non-i.id. data across the network, low device participation, high communication costs, and the mandate that data remain private bring challenges in understanding the convergence of FL algorithms, particularly in regards how convergence scales with number of participating devices. In this paper, we focus on Federated Averaging (FecdAv))-aruublly the most popular and effective FL algorithm class in use today-and and provide unified and comprehensive study of its convergence rate. Although FedAvg has recently been studied by emerging line literature, remains open as to how FedAvg's convergence scales with the number of participating devices the fully heterogencous FL setting-a - crucial question whose answer would shed light on the performance of FedAvg in large FL systems, We fill this gap by providing unified analysis that establishes convergence guarantees for FedAvg under three classes problems: strongly convex smooth, convex smooth, and overparameterized strongly convex smooth problems. show that FedAvg enjoys linear speedup each case, although with different convergence rates and communication efficiencies. While there have been linear speedup results from distributed optimization that assumes full participation.
the first to establish linear speedup for FedAvg under both statistical and system heterogeneity. For strongly convex and convex problems, we also characterize the corresponding convergence rates for the Nesterov accelerated FedAvg algorithm, which are the first linear speedup guarantees for momentum variants of FedAvg in the convex setting. To provably accelerate FedAvg, we design that further improves the convergence rate overparameterized lincar regression problems. Empirical studies of the algorithms in various settings have supported our theoretical results.
momentum based FI. algorithm
INTRODUCTION
Federated learning (FL) is a machine learning paradigm where many clients (e.g., mobile devices or organizations) collaboratively train model under the orchestration of a central server (e.g.. service provider), while keeping the training data decentralized (Smith et al. (201 7017;; Kairouz et al. (2019)) In recent years, FL has swiftly emerged an important learning paradigm (McMahan et al. (2017) Li et al. (2020a))-one that enjoys widespread success in applications such as personalized recommendation (Chen et al. (2018), virtual assistant (Lam et al. (2019)), and keyboard prediction (Hard et al. (2018). to name a few-for at least three reasons: First, the rapid proliferation of smart devices that are equipped with both computing power and data-capturing capabilities provided the infrastructure core for FL. Second, the rising awareness of privacy and the explosive growth of computational power mobile devices have made it increasingly attractive to push the computation to the edge. Third, the empirical success of communication increasingly larger-scale parallel computing and learning with less communication overhead.
FL algorithms has enabled
Despite its promise and broad applicability in our current era, the potential value FL delivers is coupled with the unique challenges brings forth. In particular, when FI. learns a single statistical model using data from across all the devices while keeping each individual device's data isolated (Kairouz ctt al. (2019)). it faces two challenges that are absent in centralized optimization and distributed (stochastic) optimization (Zhou & Cong (2088); Stich (2019); Khaled et al. (2019); Liang al. (2019); Wang & Joshi (2018); Woodworth et al. (2018) 8 Wang et al. (2019): Jiang & Agrawal (2018). Yu et al. (2019b a); Khaled et (2020); Koloskova et al. (2020); Woodworth et al. (2020b a)):
Diang
1) Data (statistical) heterogeneity: data distributions in devices are different (and data cannot be shared);

---

Under review as a conference paper at ICLR 2021
Objjcctive fanction
Strongly Convex
Convex
Overparametenized
Overparametenized linear regression
Participation
general case
Full
O
g Tz
N
Olexp( NT ))
Oeexp( NT )) Ex
NT
T
Partial
g
E VKT
K
O(exp(
KT EN1
))
O KT ))
Table I: Our convergence results for FedAvg and accelerated FedAvg in this paper. Throughout the paper, N is the total number of local devices, and K S .V the maximal number of devices that are accessible the central server. 7 is the total number of stochastic updates performed by each local device, is the local steps between two consecutive server communications (and hence T/E E' is the number of communications). In the linear regression setting, have x K₁ for FedAvg and x VKi K for momentum accelerated FedAvg (FedMaSS), where Hi and V & are condition numbers defined in Section G V R. for accelerated FedAvg.
Since Ni 2 K, this implies a speedup factor of
2) System heterogeneity: only a subset of devices may access the central server at each time both because the communications bandwidth profiles vary across devices and because there is no central server that has control over when a device is active (the presence of "stragglers").
To address these challenges, Federated Averaging (FedAvg) McMahan al. (2017) was proposed as a particularly effective heuristic, which has enjoyed great empirical success. This success has since motivated growing line of research efforts into understanding its theoretical convergence guarantees in various settings. For instance, HHddaddoour & Mahdavi (2019) analyzed FedAvg (for non-convex smooth problems satisfying PL conditions) under the assumption that each local device's minimizer is the same as the minimizer of the joint problem (if all devices' data is aggregated together), an overly restrictive assumption that restricts the extent of data heterogeneity. Very recently, [i et al.) (2020b) furthered the progress and established O convergence rate for FedAvg for strongly convex smooth Federated learning problems with both data and system heterogeneity. A similar result in the same setting Karimireddy et al. (219)) also established an ( result that allows for linear speedup when the number of participating devices is large. At the same time, Huo et al. (2020) studied the Nesterov accelerated FedAvg for non-convex smooth problems and established
convergence rate to stationary points.
However, despite these very recent fruitful pioneering efforts into understanding the theoretical convergence properties of FedAvg, remains open as to how the number of eevriess-particulatte the number of devices that participate in the compulation-affects the convergence speed. In particular, is linear speedup of FedAvg a universal phenomenon across different settings and for any number of devices? What about when FedAvg is accelerated with momentum updates? Does the presence of both data and system heterogeneity in FL imply different communication complexities and require technical novelties over results in distributed and decentralized optimization? These aspects currently unexplored or underexplored FI.. We fill in the gaps here by providing affirmative answers.
Our Contributions We provide a comprehensive and unified convergence analysis of FedAvg and its accelerated variants in the presence of both data and system heterogeneity. Our contributions are threefold.
First, we establish an O1/KTT) convergence rate under FedAvg for strongly convex and smooth problems and an ///))TT) convergence rate for convex and smooth problems (where K is the number of participating devices), thereby establishing that FedAvg enjoys the desirable linear speedup property in the FL. setup. Prior to our work here, the best and the most related convergence analysis is given by Li et al. (020b) and Karimireddy et al. (2019) which established an O(2)) convergence rate for strongly convex smooth problems under FedAvg. Our rate matches the same (and optimal) dependence on T. but also completes the picture by establishing the linear dependence on K, for any K < N, where N is the total number of devices, whereas Li et al. (2020b) does not have linear speedup analysis, and Karimireddy et al. (2019) only allows linear speedup close to full participation (K O(N)). As for convex and smooth problems, there
prior work that established the O VF) ) rate under both system and data heterogeneity. Our unified analysis highlights the common elements and distinctions between the strongly and convex settings.
Second, we establish the same convergence rates- ((tes-(((/TT)))) for strongly convex and smooth problems and 0(1/ (P1/VKK)) / for convex and smooth problems for Nesterov accelerated FedAvg. We analyze the accelerated version of FedAvg here because empirically it tends perform better; yet, its theoretical
2

---

Under review as a conference paper at ICLR 2021
convergence guarantee is unknown. To the best of our knowledge, these are the first results that provide a linear speedup characterization of Nesterov accelerated FedAvg in those two problem classes (that FedAvg and Nesterov accelerated FedAvg share the same convergence rate is to be expected: this is the case even for centralized stochastic optimization). Prior to our results here, the most relevant results Yu et al. (2019a); Li al.) (2020a); HHuo et al. (2020) only concern the non-convex setting, where convergence is measured with respect to stationary points (vanishing of gradient norms, rather than optimality gaps). Our unified analysis of Nesterov FedAvg also illustrates the technical similarities and distinctions compared to the original FedAvg algorithm, whereas prior works (in the non-convex setting) were scattered and used different notations.
Third, we study subclass of strongly convex smooth problems where the objective is over- parameterized and establish a faster O(exp( KT) convergence rate for FedAvg, in contrast to the O(cxp(-²)) rate for individual solvers Ma et al. (2018). Within this class, we further consider the linear regression problem and establish an even sharper rate under FedAvg. In addition, we propose a new variant of accelerated FedAvg based on a momentum update Liu & Belkin - accelerated FedAvg-and establish faster convergence rate (compared to if acceleration is used). This stands in contrast to generic (strongly) convex stochastic problems where theoretically no rate improvement obtained when one accelerates FedAvg. The detailed convergence results are summarized in Table
Connections with Distributed and Decentralized Optimization Federated learning is closely re- lated to distributed and decentralized optimization, and as such it is important to discuss connections and distinctions between our work and related results from that literature. First, when there is neither system heterogeneity, i.e. all devices participate in parameter averaging during communication round, nor statistical heterogeneity, i.e. all devices have access to a common set of stochastic gra- dients, FedAvg coincides with the "Local SGD" of (tich (2019). which showed the linear speedup rate OLL/NT) for strongly convex and smooth functions. Woodworth et al. (2020b) and Woodworth et al. (220a)) further improved the communication complexity that guarantees the linear speedup rate. When there is only data heterogeneity, some works have continued to use the term Local SGD to refer to FedAvg, while others subsume it in more general frameworks that include decentralized model averaging based on a network topology or a mixing matrix. They have provided linear speedup analyses for strongly convex and convex problems, e-g. Khaled et al. (2020); Koloskova al. (2020) as well as non-convex problems, c.g. Jiang & Agrawal (2018); Yu et al. (2019b); Wang & Joshi (2018). However, these results do not consider system heterogeneity, i.e. the presence of stragglers in the device network. Even with decentralized model averaging, the assumptions usually imply that model averages over all devices is the same as decentralized model averages based on network topology (e.g. Koloskova et al. (2020) Proposition 1), which precludes system heterogeneity as defined in this paper and prevalent in FL problems. For momentum accelerated FedAvg. Yu et al. (2019a) provided linear speedup analysis for non-convex problems, while results for strongly convex and convex settings are entirely lacking, even without system heterogeneity. Karimireddy et al. (2019) considers both types of heterogeneities for FedAvg, but their rate implies linear speedup only when the number of stragglers is negligible. In contrast, our linear speedup analyses consider both types of heterogeneity present in the full federated learning setting, and are valid for any number of participating devices. We also highlight a distinction in communication efficiency when system heterogeneity is present. Moreover, our results for Nesterov accelerated FedAvg completes the picture for strongly convex and convex problems. For detailed comparison with related works, please refer to Table in Appendix Section B
SETUP
In this paper, we study the following federated learning problem:
min
F(w)
Σ k=1 Pk Fl((w)
(1)
where N is the number of local devices (wsers/noddeswworkers))) and pk is the k-th device's weight sat- isfying Pk 2 0 and EN= Ps = 1. In the k-th local device, there are my data points: x xi. x The local objective F+(-) is defined as: Fl(w) e 1 Eje (w:x)). where & denotes a user- specified loss function. Each device only has access to its local data, which gives rise its
3

---

Under review as a conference paper at ICLR 2021
local objective Fg. Note that we do not make any assumptions the data distributions of each local device. The local minimum F = minw Fk (w) can be far from the global minimum of Eq (data heterogencity).
2.1 THE FEDERATED AVERAGING (FEDAVG) ALGORITIM
We first introduce the standard Federated Averaging (FedAvg) algorithm which was first proposed by McMahan et al. (017). FedAvg updates the model in each device by local Stochastic Gradient Descent (SGD) and sends the latest model to the central server every E steps. The central server conducts weighted average over the model parameters received from active devices and broadcasts the latest averaged model to all devices. Formally, the updates of FedAvg at round f is described as follows:
if + $ LE, ift+ IE.
1+1 V++1 = w argek w = ExEsc gevi_1
(2)
where w is the local model parameter maintained in the k-th device at the f-th iteration and is the stochastic gradient based on <k the data point sampled from k-th
gr. == Vi (w?, <t) - device's local data uniformly at random. ZE = {E, 25,2E.... steps, when local parameters from set of active devices are averaged and broadcast to all devices. We use S to represent the (random) set of active devices at + 1. qs is a set of averaging weights that are specific to the sampling procedure used to obtain the set of active devices S4+1-
the set of global communication
Since federated learning usually involves an enormous amount of local devices, it is often more realistic to assume only subset of local devices is active at each communication round (system heterogeneity). In this work, we consider both the case of full participation where the model is averaged over all devices each communication round, in which case qs = ph for all k and w Ex= Pe P& if E Ig, and the case of partial participation where |St+a| N.
With partial participation, we follow Li et al. (2020a); Karimireddy et al. (2019) Li et al. (2020b) and assume that S,+1 is obtained by one of two types of sampling schemes simulate practical scenarios. One scheme establishes S1+1 by i.i.d. sampling the devices with probability ps with replacement, and uses q: = R. where K = |S while the other scheme samples S411 uniformly i.i.d. from all devices without replacement, and uses Ok Pk 인 Both schemes guarantee that gradient updates in FedAvg are unbiased stochastic versions of updates in FedAvg with full participation, which is important in the theoretical analysis of convergence. Because the original sampling scheme and weights proposed by McMahan et al. (2017) lacks this nice property, it not considered in this paper. For more details on the notations and setup as well as properties of the two sampling schemes, please refer to Section A the appendix.
2.2 ASSUMPTIONS
We make the following standard assumptions on the objective function Fi..... Ex. Assumptions and commonly satisfied by a range of popular objective functions, such as &-regularized logistic regression and cross-entropy loss functions.
|
Assumption (L-smooth). Fi, FN are all L-smooth: for all v and w, F&(v) S Fx(w)+
w) () + f1 - w|
Assumption 2 (atrongly-convex) F1, 2 -
EN are all -strongly convex: for all and w, Fs(v) 2
Fx(w) (v))
Assumption 3 (Bounded local variance). Lei gk be sampled from the k-th device's local data uniformly at random. The variance of stochustic grudients in each device is bounded: E V (wt. <h) FF [I² S for for k= 1, ,N and any wh: Let 0² = E k Assumption 4 (Bounded local gradient). The expected squared norm of stochastic gradients is .....
uniformly bounded. i.e., E V FR (w//st)
G2, all k =,...,, and
Assumptions and have been made in many previous works in federated learning, e.g. Yu et al.] (019b)) Li et al. (2020b); Stich (2019). We provide further justification for their gen- erality. As model average parameters become closer to w", the L-smoothness property im- plies that E. V FL (w/, 12 and F. ( {t) VF&(w())l approach E|| Fi(w", ("" and
4

---

Under review as a conference paper at ICLR 2021
B { (Fx(2") Therefore, there is substantial difference between these assump- tions and assuming the bounds at w" only Koloskova et al. (2020). Furthermore, compared to assuming bounded gradient diversity in related work Haddadpour & Mahdavi (2019); Li et al. (2020a), Assumption A is much less restrictive. When the optimality gap converges to zero, bounded gradient diversity restricts local objectives to have the same minimizer the global objective, contra- dicting the heterogencous data setting, For detailed discussions of our assumptions, please refer to Appendix Section
LINEAR SPEEDUP ANALYSIS OF FEDAVG
In this section, we provide convergence analyses of FedAvg for convex objectives in the general setting with both heterogeneous data (statistical heterogeneity) and partial participation (system heterogeneity). We show that for strongly convex and smooth objectives, the convergence of the optimality gap of averaged parameters across devices is O KT). while for convex and smooth objectives, the rate is OLIVVKT) Our results improve upon Li et al. (2020b); Karimireddy et al. (2019) by showing linear speedup for any number of participating devices, and upon Khaled et al. (2020); ; Koloskova et al. (2020) by allowing system heterogeneity. The proofs also highlight similari- ties and distinctions between the strongly convex and convex settings. Detailed proofs are deferred to Appendix Section
3.1 STRONGLY CONVEX AND SMOOTH OBJECTIVES
We first show that FedAvg has an O(1 convergence rate for μ-strongly convex and L-smooth objectives. The result relies on a technical improvement over the analysis in Li et al. (2020b). Moreover, it implies distinction in communication efficiency that guarantees this linear speedup for FedAvg with full and partial device participation. With full participation, E can be chosen as large as O (VTTNN without degrading the linear speedup in the number of workers. On the other hand, with partial participation, E must be O(1) to guarantee O(1/KT) convergence.
Theorem 1. Let WT = Ek=n Pk w in FedAvg, Umax = maxx Npt. and set decaying learning rates a ply+ej with 7 max{32k, E} and k L Then under Assumptions to with full device participation,
kV 02/p
R
max
NT
T2
and with partial device participation with at most K sampled devices at each communication round,
EF(WT) - F0= KKEGG//
kD2
0 ///n
E²
K
max
KT
NT
T
Proof sketch. Because our unified analyses of results the main text follow the same framework with variations in technical details, first give outline of proof for Theorem to illustrate the main ideas. For full participation, the main ingredient a recursive contraction bound
E W++1 - w/ < (1 E w'1 a 2
02 LE
where the (a term is the key improvement over the bound in Li et al. (2020b). which has E instead. We then use induction to obtain non-recursive bound E Wr w=1? which converted to a bound on (F((r) - F using T-smoothness. For partial participation, an additional term O } F F²22) of leading order resulting from sampling variance is added to the contraction bound. To facilitate the understanding our analysis, please refer to a high-level summary Appendix C
Linear speedup. We compare our bound with that in al. (2220)). which O NT
KT
Because the term =²G² is also (1/TT) without dependence N, for any choice of F. their bound "
cannot achieve linear speedup. The improvement of our bound comes from the term "²"=00 /n. which
5

---

Under review as a conference paper at ICLR 2021
now is O(E2/TT) and so is not of leading order. As result, all leading terms scale with 1/N in the full device participation setting, and with 1/ K in the partial participation setting. This implies that in both settings, there is a linear speedup in the number of active workers during communication round. We also emphasize that the reason one cannot recover the full participation bound by setting K = N in the partial participation bound is due to the variance generated by sampling.
Communication Complexity. Our bound implies a distinction in the choice of E' between the full and partial participation settings. With full participation, the term involving E, O /20), is not of leading order (1/TT), so we can increase E and reduce the number of communication rounds without degrading the linear speedup in iteration complexity O(1 /NT), as long as F = Olv T/N), (1/NT)) matches the leading term. This corresponds to communication
since then D complexity of T/E (VVNT). In contrast, the bound in Li et al. (2020b) does not allow E to scale with vT preserve (1//T) rate, even for full participation. On the other hand, with partial participation, x=²G²/" is also a leading term, and so E must be ((1). In this case, our bound still yields a linear speedup in K, which is also confirmed by experiments. The requirement that E = O(1) in order to achieve linear speedup in partial participation cannot be removed for our sampling schemes, as the term OEE )) In Proposition D in Section E of the appendix, we provide a problem instance where the dependence of the sampling variance E is tight.
KT
xE²G²/u /u comes from variance in the sampling process, which is
KT
Comparison with related works. To better understand the significance of the obtained bound, we compare our rates to the best-known results in related settings. [Haddadpour & Mahdavi (009)) proves linear speedup ((1/KT) result for strongly convex and smooth objectives with O
communication complexity with non-i.id. data and partial participation. However, their results build on the bounded gradient diversity assumption, which implies the existence of w that minimizes all local objectives (see discussions in Section 2.2 and Appendix B). effectively removing statistical heterogeneity. The bound in Koloskova al. (2020) matches our bound in the full participation case, but their framework excludes partial participation (Koloskova et al. 2020 Proposition 1). The result of Karimireddy et al. (2019) applies the full FL setting, but only has linear speedup when K = ONN), i.e. close to full participation, whereas our result has linear speedup for any number of participating devices. When there no data heterogeneity, i.e. in the classical distributed optimization paradigm, communication complexity can be further improved, e.g. WWodworth et al. (2020b a). but such results are not directly comparable to ours since we consider the setting where individual devices have access to different datasets.
3.2 CONVEX SMOOTH OBJECTIVES
Next we provide linear speedup analysis of FedAvg with convex and smooth objectives and show that the optimality gap is O(1/VKT) This result complements the strongly convex case in the previous part, as well the non-convex smooth setting in Jiang & Agrawal (2018); Yu et al. (2019b); Haddadpour & Mahdavi 2019)), where ((1v/KT) results are given in terms of averaged gradient norm, and it also extends the result in Khaled et al. (2020), which has linear speedup in the convex setting, but only for full participation.
Theorem 2. Under Assumptions
=O(V 4). FedAvg satisfies 1 3 and constant learning rate at
ST min F(w:) - F(w*)= = O (" Fiaxx
NE
/NT
T
with full participation, and with partial device participation with K sampled devices at each commu- nication round and learning rate ax = =O(V V K)
min F(w,) F(w*)= O V2 VKT
E²G²
KE
t
VKT
T
The analysis again relies recursive bound, but without contraction:
1
E W w 12 - F(w*)) < El
w
1 2 a 2 N
02 02 + 6a, L²2
Their result applies a larger class of non-convex objectives that satisfy the Polyak-L.ojasiewicr condition.

---

Under review as a conference paper at ICLR 2021
which is then summed over time steps to give the desired bound, with a; = = O(V 7).
Choice of E and linear speedup. With full participation, as long as F = -0(TL//////)) the con- vergence rate is O(1/ /VT) with (NN3/T7//1) communication rounds. In the partial participation setting, E. must be ((1) in order achieve linear speedup of O1/vKTT). This is again due to the fact that the sampling variance [E|ww; vell = ( G²) cannot be made independent of E, as illustrated by Proposition [ See also the proof in Section B for how the sampling variance and the term E /vKT are related. Our result again demonstrates the difference in communi- cation complexities between full and partial participation, and is to our knowledge the first result on linear speedup in the general federated learning setting with both heterogeneous data and partial participation for convex objectives.
4 LINEAR SPEEDUP ANALYSIS OF NESTEROV ACCELERATED FEDAVG
natural extension of the FedAvg algorithm to use momentum- local updates instead of local SGD updates in order to accelerate FedAvg. As we know from stochastic optimization, Nesterov and other momentum updates fail to provably accelerate over SGD (Liu & Belkin 2020); Kidambi al. (2018); Liu al. 2018); Yuan & Ma (. This is in contrast to the classical acceleration result of Nesterov- -aceerr-accceeratedd gradient descent over GD. Thus in the FL setting, the best provable convergence rate for FedAvg with Nesterov updates is the same FedAvg with SGD updates. Nevertheless, Nesterov and other momentum updates are frequently used in practice, in both non-FL FL and FL settings, and are observed to perform better empirically. In fact, previous works such as Sttchh (2019) on FedAvg with vanilla SGD uses FedAvg with Nesterov or other momentum updates in their experiments to achieve target accuracy. Because of the popularity of Nesterov and other momentum- based methods, understanding the linear speedup behavior of FedAvg with such local updates is important. To our knowledge, the only convergence analyses of FedAvg with momentum- based stochastic updates focus on the non-convex smooth case Huo et al. (2020); Yu et al. (2019a); [Li et al. (2020a), and no results existed in the convex smooth settings. In this section, we complete the picture by providing the first (()KTT) and 0 /КT)) convergence results for Nesterov-accelerated FedAvg for convex objectives that match the rates for FedAvg with SGD updates. Detailed proofs of convergence results in this section are deferred to Appendix Section
4.1 STRONGLY CONVEX AND SMOOTH OBJECTIVES
The Nesterov Accelerated FedAvg algorithm follows the updates:
[vit1 + Be(v - v()
ift 1 IE. if + ++1 Ig.
* V+1 = w/ aggr.
W "+1
Exes... 0k [v++ + 3:
where gt. == FR (w, c is the stochastic gradient sampled on the k-th device at time t,, and gk again depends on participation and sampling schemes.
Theorem 3. Let VT
Σx V Nesterov accelerated FedAvg, and set learning rates
at a 24g0 3r-1 14(++)((1 2 max(u.]]
Then under Assumptions 4 with full device
participation,
O NT
R. G
EF(TT) - F' =
T2
and with partial device participation with K sampled devices at each communication round,
Nu2 m 0² //
KFF. /n 122 x2E /px
BF(VT) F= =O
NT
KT
T
Similar FedAvg, the key step in the proof of this result recursive contraction bound, but different in that it involves three time steps, due to the update format of Nesterov SGD (see Lemma]] 7 in Appendix F.T. Then we can again use induction and I--smoothness to obtain the desired bound. To our knowledge, this is the first convergence result for Nesterov accelerated FedAvg in the strongly convex and smooth setting. The same discussion about linear speedup of FedAvg applies to the Nesterov accelerated variant. In particular, to achieve (1/NT) linear speedup, T iterations of the algorithm require only O (VNT) communication rounds with full participation.
7

---

Under review as a conference paper at ICLR 2021
4.2 CONVEX SMOOTH OBJECTIVES
We now show that the optimality gap of Nesterov--acceleatted FedAvg has O(1/VKT KT) rate for convex and smooth objectives. This result complements the strongly convex case in the previous part, as well as the non-convex smooth setting in Huo et al. 2020); Yu et al. (2019a): Li et al. (2020a). where a similar O(1/VKT) rate is given in terms of averaged gradient norm.
Theorem 4. Set learning rates 0a 8 = /OON )) Then under Assumptions accelerated FedAvg with device participation has rate
13 Nesterov
NE T
F(v.) - = 1
+
NT
and with partial device participation with K sampled devices each communication round,
2 (
V
E
KE*LG*
min F(V.) F -F= [ST
VKT
VKT T
We emphasize again that the stochastic optimization setting, the optimal convergence rate that FedAvg wtih Nesterov udpates can achieve is the same FedAvg with SGD updates. However, due to the popularity and superior performance of momentum methods in practice, it is still important to understand the linear speedup behavior of such FedAvg variants. Our results in this section fill exactly this gap.
Bumber Koratin
maration
Watr mor Peraaunnc
E-6
End
Rumber werkers
Number workers
Number active
3x17
Wumber of Renations
Wumber of Marratios
Wunseer or mANOINAN
Eel
End
E:16
E:
Number of warkers (N)
Number of warkers
Number of sorkens (N)
(a) Strongly convex objective
(b) Convex smooth objective
(c) Linear regression
Figure The linear speedup of FedAvg in full participation, partial participation, and the linear speedup of Nesterov accelerated FedAvg, respectively.
8

---

Under review as a conference paper at ICLR 2021
5 NUMERICAL EXPERIMENTS
In this section, we empirically examine the linear speedup convergence of FedAvg and Nesterov accelerated FedAvg various settings, including strongly convex function, convex smooth function, and overparameterized objectíves, as analyzed in previous sections.
Setup. Following the experimental setting in Stich 2019), conduct experiments both synthetic datasets and woaldworld dataset w8a Platt (1998) (d = 300, n = 49749). We consider the distributed objectives F F(w) Σx= Pk: Fie(Fe( (w). and the objective function the k-th local device includes three cases: 1) Strongly convex objective: the regularized binary logistic regression problem, (w(w) = N2 Ei=1 log(1 + exp(-y, w x + l|l] The regularization parameter is set to A= 1/n 2e 5. 2) Convex smooth objective: the binary logistic regression problem without regularization. 3) Overparameterized setting: the linear regression problem without adding noise to the label, F&(w)) N.
E
No (w
b 2
Linear speedup of FedAvg and Nesterov accelerated FedAvg. To verify the linear speedup conver- gence shown in Theorems 3234 evaluate the number of iterations needed reach e-accuracy in three objectives. We initialize all runs with wo = 02 and measure the number of iterations to reach the target accuracy For each configuration (F., K), we extensively search the learning rate from min I47 ), where E (0.1,0.12, 1, 32 according to different problems and c can take the values 2' Vi E Z. As the results shown in Figure 1 the number of iterations decreases as the number of (active) workers increasing, which is consistent for FedAvg and Nesterov accelerated FedAvg across all scenarios. For additional experiments the impact of E, detailed experimental setup, and hyperparameter setting, please refer to the Appendix Section

---

Under review as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint 1911.81811036 2018.
Fei Chen, Zhenhua Dong, Zhenguo Li, and Xiuqiang He. Federated meta-learning for recommenda- tion. arXiv preprint 10XX::88822077766 2018.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprini arXiv: 14425, 2019.
Andrew Hard, Chloé M Kiddon, Daniel Ramage, Francoise Beaufays, Hubert Eichner, Kanishka Rao, Rajiv Mathews, and Sean Augenstein. Federated learning for mobile keyboard prediction, 2018. URL httts:ts/tsaiiiii
ort. abs/1811 03604
Zhouyuan Huo, Qian Yang. Bin Gu, Lawrence Carin Huang, et al. Faster on-device training using new federated momentum algorithm. arXiv preprint arXiv:2002.020090 2020.
Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Accelerating stochastic gradient descent. Proc. STAT, volume 1050, pp. 26, 2017.
Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. In Advances in Neural Information Processing Systems, pp. 2525-2536 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: 191.vv9912.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: 19/0.06///003777 2019.
A Khaled, K Mishchenko, and P Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local gd on hetero- gencous data. NeurIPS Workshop Federated Learning for Data Privacy and Confidentiality, 2019.
Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham Kakade. On the insufficiency of existing momentum schemes for stochastic optimization. In 2018 Information Theory and Applications Workshop (ITA), pp. 1-9. IEEE, 2018.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized sgd with changing topology and local updates. arXiv preprint 2rXiv:2003.10422 2020.
Monica S Lam, Giovanni Campagna, Silei Xu, Michael Fischer, and Mehrad Moradshahi. Protecting privacy and open competition with almond: an spen-source virtual assistant. XRDS: Crossroads, The ACM Magazine for Students, 26(1):40-44 2019.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. MLSys, 2020a.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. ICLR, 2020b.
Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local sgd with lower communication complexity. arXiv preprint arXiv: /9/2./24444 2019.
Chaoyue Liu and Mikhail Belkin. Accelerating sgd with momentum for over perrpparameterized learning. ICLR, 2020.
10

---

Under review as a conference paper at ICLR 2021
Tianyi Liu, Zhehui Chen, Enlu Zhou, and Tuo Zhao. Toward deeper understanding of noncon-
vex stochastic optimization with momentum using diffusion approximations. arXiv preprint arXiv:1802.005155. 2018.
Wei Liu, Li Chen, Yunfei Chen, and Wenyi Zhang. Accelerating federated learning via momentum gradient descent. IEEE Transactions on Parallel and Distributed Systems, 2020.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness sgd in modern over per-parametrized learning. ICML, 2018.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communication--ffciinn learning of deep networks from decentralized data. Proceedings of the 20 International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
Eric Moulines and Francis R Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, pp- 451-459, 2011.
Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In Advances in neural information processing systems, pp. 1017-1025, 2014.
J Platt. Fast training of support vector machines using sequential minimal optimization, in, b. scholkopf, c. burges, a. (eds); Advances in kernel methods-suppprt vector learning, 1998.
R Tyrrell Rockafellar. Convex analysis. Number 28. Princeton university press, 1970.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under strong growth condition. arXiv preprint arXiv:1308.66 6370, 2013.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar. Federated multi-task learning, Advances in Neural Information Processing Systems, pp. 4424-4434, 2017.
Sebastian U Stich. Local sgd converges fast and communicates little. ICLR, 2019.
Thomas Strohmer and Roman Vershynin. randomized kaczmarz algorithm with exponential convergence. Journal of Fourier Analysis and Applications, 15(2):262, 2009.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of caammmunication-ffffiiin sgd algorithms. arXiv preprint arXiv:1808.00576 2018.
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, 37(6): 1205) 205-12211 2019.
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local sgd for heterogeneous distributed learning, arXiv preprint arXivv2006.0477 2020a.
Blake Woodworth, Kumar Kshitij Patel, Sebastian U Stich, Zhen Dai, Brian Bullins, H Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? arXiv preprint arXiv:2002.078.2 2020b.
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, pp. 8496-85066 2018.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis communication efficient momentum sgd for distributed non-convex optimization. /CML, 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 on Artificial Intelligence, volume 33, pp. 5693-5700, 2019b.
Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. Advances in Neural
Information Processing Systems, 33, 2020.

---

Under review as a conference paper at ICLR 2021
Kun Yuan, Bicheng Ying, and Ali H Sayed. On the influence of momentum acceleration online learning. The Journal of Machine Learning Research, 17(1):6602-666 6667, 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 16Xiv:1611.03555 2016.
Fan Zhou and Guojing Cong- On the convergence properties of k-step averaging stochastic gradient descent algorithm for nonconvex optimization. I/CAI, 2018.
12

---

Under review as a conference paper at ICLR 2021
A ADDITIONAL NOTATIONS AND BOUNDS FOR SAMPLING SCHEMES
In this section, we introduce additional notations that are used throughout the proofs. Following com- mon practice, e.g. Stich 2019); Li et al. (2020b), we define two virtual sequences V; Ek=1PhV and w.
2k=1 Pk w where recall the FedAvg updates from
N
if & IE, W = ExEs. ge if Ig.
{
v = w argr,
The following observations apply to FedAvg updates, while Nesterov accelerated FedAvg requires modifications. For full device participation partial participation with Ig. note that V, W. Ek= k= kk=1Pk P&V.. For partial participation with t Ig. + since V. =Ek= P&V while unbiased sampling strategies such that Es,, W. V.. Note that vt+1 is one-step SGD from W..
W, Lkss, zw However,
++1
aggt
(3)
where g: - -K & is the one-step stochastic gradient averaged over all devices.
gr, V (w/, <tt)
Similarly, we denote the expected one-step gradient g: = LEg, [B:] - gf where
gr = V.Fk (w/),
(4)
and & {St === denotes random samples all devices at time step
N
Since in this work we also consider the case of partial participation, the sampling strategy to approximate the system heterogeneity can also affect the convergence. Here we follow the prior works Li et al. (2020b) and Li et al. (2020a) and consider two types of sampling schemes that guarantee Es. W. = v. The sampling scheme establishes S by i.i.d. sampling the devices according to probabilities pş with replacement, and setting 9k Tc. In this case the upper bound of expected square norm of W,+1 Ve+1 is given by (Li et al. 20206 Lemma 5):
Esa
We+1 V+tal? GA.E
(5)
The sampling scheme II establishes S by uniformly sampling all devices without replacement and N in which case we have setting 9k = K
4(N -K) ES. W 1++1l
K(N - ai E2.
(6)
We summarize these upper bounds as follows:
ES |e+t V K
E2
and this bound will be used in the convergence proof of the partial participation result.
B COMPARISON OF CONVERGENCE RATES WITH RELATED WORKS
In this section, we compare our convergence rate with the best-known results the literature (see T In Haddadpour & Mahdavi (201)), the authors provide (L/NTT) convergence rate of non- (PL) condition, which means their results can directly
convex problems under apply to the strongly convex problems. However, their assumption is based on bounded gradient diversity, defined as follows:
A(w) = EAPA (w
VF <
This is a more restrictive assumption comparing to assuming bounded gradient under the case of target accuracy 0 and PI. condition. To see this, consider the gradient diversity the global optimal
13

---

Under review as a conference paper at ICLR 2021
w", i... A(w*) Σ. (
15 & For A(w*) to be bounded, it requires [VF
This indicates w" is also the minimizer of each local objective, which contradicts to the practical setting of heterogeneous data. Therefore, their bound is not effective for arbitrary small e-accuracy under general heterogeneous data while our convergence results still hold in this case.
In Karimireddy et al. (2019), the linear speedup convergence rate of FedAvg are provided for strongly convex, general convex, and non-convex problems under full participation setting. However, their rate does not enjoy linear speedup for any number of devices while our results apply to any valid
K S N. For example, they provides an optimality gap of O ((1 E/T) for the strongly convex case (Karimireddy et al. 2019 Theorem V). With partial participation, and when K = O1), their convergence rate is O which does not have linear speedup. Under partial participation, the FedAvg analyses in Karimireddy et al. 2019) requires F. O(1). For example, the strongly convex result O((1 f ) in Theorem V is (E/TT) when K O(1) and is O(E/NT) when K = O(N). In either case, to achieve a ( convergence rate, it requires E = O(1) as well.
Similar conclusion also holds for the general convex problem.
Referenee
Conva gence mie
NonlID
Paricipation
Extra Ascamptions
Setting
FedAv MilAvlliir ut
20206-
0
0(1) O1K 173 1711
Portial
Bounded gradient
Strongly sonvex
FelAvglladksdpoor Mahdavi
2019
O x
Partial
Boundel gradient diversity
Strunly cunves F
FedAy Kolockowa et
2000
O )
O(N
/
Full
Bounded gradiens
Strongly coevex
FodAAv FadAAu Karimireddy et
2019
C7 mr )T1
O1N 122
/
Portial
Rouneed pealient dissimiilariy
Strongly convex
FolAvgN (our werks
o xer
O(N 11N-172-1/27
Portial
Bounded gradient
Stroegly convex
FedAv Khaled al.
2020
C (y))))
O(N 1/271/3)
/
Full
Bounded gradient
Comexx
PedAt Koloskova et
2000
C( (Vv))
O(N 1/47
/
Full
Bounded gradient
Comex
YeciAv/Karimiieddy
2019
O /VT yTT
O(N 1441
/
Purtial
Bounded gradient dissimilarity
Comeex
FedAvg/N FedArg (our work)
0 vier)
O(N O(N-3/"1'
Partial
Bounded gradient
Comex
FedAvg
0 [xp([
O(T")
Purtil
Bounded gradiens
Overparameterized LR
FedMass
exp(
NT
o(T²)
Parial Bounded gradiest
Overpanameterized
Table 2: A high-level summary of the convergence results in this paper compared to prior state-of- the-art FL. algorithms. This table only highlights the dependence on T (number of iterations). E (the maximal number of local steps), NN (the total number of devices), and K < N the number of participated devices. k is the condition number of the system and | E (0, 1). We denote Nesterov accelerated FedAvg as N-FedAvg in this table.
This E is obtained under i.i.d. setting.
1 This obtained under full participation setting.
8 In Haddadpour & Mahdavi (2019). the convergence rate is for non-convex smooth problems with PI. condition, which also applies to strongly convex problems. Therefore, we compare with our strongly convex results here.
# The bounded gradient diversity assumption is not applicable for general heterogencous data when converging to arbitrarily small e-aceuracy (see discussions in B
It Although the results in Karimireddy et al. (2019) is applicable for partial participation setting, their results only achieve linear speedup under full participation setting K = N while show linear speedup convergence for K < N (see discussions in Sec B). The E in the table is obtained under full participation. Under partial participation, the communication complexity is E O(1).
C HIGH-LEVEL SUMMARY OF FEDAVG ANALYSIS
To facilitate the understanding of our analysis and highlight the improvement of work comparing to prior arts, we summarize the general steps used in the proofs across the various settings. In this section, we take the strongly convex case as an example illustrate our analysis. The corresponding proof for general convex functions follows the same framework.
One step progress bound
This step establishes the progress of distance (| w1 to optimal solution after one step SGD update (see line 9, Alg as the following equation shows:
E
W w0| On
w" + + oGE
14

---

Under review as a conference paper at ICLR 2021
Algorithm 1 FEDAVG: Federated Averaging
1: Server input: initial model initial step size cn. local steps E.
Client imput:
3: for each round r = 0, 1,.,, , R, where r =
4: Sample clients S C (1,,.., N}
5: Broadcast
all clients & St
6: for each client & [ S, do initialize local model w = W ...... (r (r+ + 1) E do
8: for = -
w w. Ot.t.h
10: end for
11: end for
12:
Average the local models at server end: W, ExEo, w/.
13:
end for
The above bound consists of three main ingredients, the distance to optima in previous step (with N E (0, 1) to obtained contraction bound), the variance of stochastic gradients in local clients (second term), the variance across different clients (third term). Notice that the third term in this bound is the primary source of improvement in the rate. Comparing to the bound in Li et al.] (2020b), improve the third term from (aa G² to Oa E22). which enables the linear speedup the convergence rate.
Iterative deduction
This step uses the one step progress bound iteratively to connect the the current distance to optimal solution with the initial distance Wo w' )1,, follows:
w 11 < O w
Then we can use the distance to optima to upper bound the optimality gap (F(w)) - F* S O(L/T)). as follows:
B(F(w.)) F I O w²ll)).
The convergence rate of the optimality gap is equally obtained as the convergence rate of the distance optima.
From full participation to partial participation
There are three sources of variances that affect the convergence rate. The first two sources come from the variances of within local clients and across clients (second and third term in one step progress bound). The partial participation, which involves sampling procedure, is the third source variance. Therefore, comparing to the rate in full participation, this will add another term of variance into the convergence rate, where we follow a similar derivation as in Li al. (2020b).
D TECHNICAL LEMMAS
To facilitate reading, we first summarize some basic properties of L-smooth and p-strongly convex functions, found in e.g. RRockaellarr (1970), which are used in various steps of proofs in the appendix.
Lemma 1. Let F be convex L-smooth function. Then we have the following inequalities:
1. Quadratic upper bound: 0 < F(w) F(w') (VF(w'), w') S $ l| w/12.
Coercivity: +[IVF(w) VF(w (VF(W) -FFW))-F((W)) V
w')
3. Lower bound: F(w) 2 F(w') + (VF(('), w VFF(w VF(w")112 particular, < 2L(((w)) [/V(())]1
F(w*))
4. Optimality gap: F(w) - F(w") WV
Lemma 2. Let F be a p-strongly convex function. Then
F(w)= S F(w') (VF(w'). w w') + 1 IVF((w) VF(w))l 2p
15

---

Under review as a conference paper at ICLR 2021
1 F(w) F(w)) - [VF(w))] 24
E PROOF OF CONVERGENCE RESULTS FOR FEDAVG
E. STRONGLY CONVEX SMOOTH OBJECTIVES
To organize our proofs more effectively and highlight the significance of our results compared to prior works, we first state the following key lemmas used proofs of main results and defer their proofs to later.
Lemma (One step progress, strongly convex). Lei W. = Ek=1 Ps w and suppose our functions satisfy Assumptions 3 and set step size a, = p()+() with n = max{32k, }} and 4. then the updates of FedAvg with full participation satisfy
n='
E W.+1 w w01 s (1 pad )E W. w"1l aj v v2 N max + La
We emphasize that the above lemma is the key step that allows us to obtain a bound that improves on the convergence result Li et al. (2020b) with linear speedup. Its proof will make of the following two results.
Lemma (Bounding gradient variance (Lemma 2 al. (2020b)) ) Given Assumption 3 the upper bound of gradient variance is given as follows,
E g: gell
2 P
k=
Lemma (Bounding the divergence of w (Leemma
al. (020b)) ). Given Assumption
and assume that ar is non-incredd non-increasing and S. 201+ E for all t 0, we have
E
Pk W. w/1l?
< 04E
We now restate Theorem I from the main text and then prove it using Lemma 3
Theorem 1. Let WT === Pk w 2h in FedAvg, Vmax maxk Nps, and set decaying learning rates a₁ p( with ry max{32k. 332x, E} and K 4. Then under Assumptions 1 with full device participation,
RV2 o2 /U
E2
R²
F'
NT
T2
and with partial device participation with at most K sampled devices at each communication round,
GE KT
RV²
02 122
E² pp
EF p" O
max
NT
T2
Proof. The road map the proof for full device participation contains three steps. First, we establish
recursive relationship between E W w|' and [E| w. w 1| upper bounding the progress of
FedAvg from step to step + 1. Second, we show that E| w| O "mmag"// + E²LG3 /u² by induction using the recursive relationship from previous step. Third, we use the property of L-smoothness to bound the optimality gap by E w, w1l
By Lemma we have the following upper bound for the one step progress:
W w1 < (1 [o
w+1l a
2 maz + Lo
16

---

Under review as a conference paper at ICLR 2021
We show next that RR|[w, W, w w =0 1 "mmn 02/2
+ F2
using induction. To simplify the presentation, we denote = LE and = 1 Uman o² Suppose that we have the bound E|[w; w* < b- (o, - afC) for some constant b and learning rates 0z, Then the one step progress from Lemma becomes:
IN
N
Wi+1 w 11 - (6(1 - paz) + arja (b(1 - pai) + at)a
To establish the result at step 1. it remains to choose and b such that (6(1-pay (aaaaaa))+aaaa) +ai)a S ba and (b(1 (04) + az)af & b required to guarantee the one step progress) and set 6 = 1
let a n(++>) where ? = max ( E, 32k} (choice of
we have:
(6(1 - pai) ai)ar = (6( 8+7
- ) 1(t + 7)
4
S
ba
1(t + 7)
Mlt +
t 7 - 2
16
16
(b(1 - pa.) + on)a = b(
= bo
t + 1e (t+ +
pe + 1)2
where we have used the following inequalities:
t 1
4+7- -2
S (++
(t 7)+
11+
(t + 7)3
Thus we have established the result at step + assuming the result is correct at step t:
W - w0 s b- (as+1 D + +z2+1C)
At step we can ensure the following inequality by scaling b with ellwo w=1 for a sufficiently
large constant
4
16
Iw w² < b- (ao D + agj) b.
( D 1n7
0)
1272
It follows that
W. w01 S cllwo w 11 Caf)
(8)
for all 2 0.
Finally, the L-smoothness of F implies
L
[((((T))) F
B |T w1
2
L
$ cl/wo- w'l 1112"
(Dar Caft
2
2ccl|
w' >'13xx(Dar + Cat)
4
1
4 + . ( 7) )2
S 2ol|wo w1122x
Umazo
[T) N
00 1
x² T P +
1
0²
E²G
μ N man
where in the first line, the property of L-smooth function (see Lemma I. and in the second line, we use the conclusion in Eq ().
With partial participation, the update each communication round now given by weighted averages over subset of sampled devices. When t + 1 & Zg. V = W1+1, while when t + 1 E Ig, we have Ew,-1 V by design of the sampling schemes (Li et al. (2020b). Lemma 4), so that
W w0 = W V + V w'1l
E We+1
V 1| 1 w
This in particular implies E w' < E w:
-
w 2 for all Since V. = MN Ae p&v always
averages over all devices, the full participation one step progress result Lemma appliied to v, implies
Vi+1 w" w < B(11-a:)llv - w01 6E GE"La,G + at V o
17

---

Under review as a conference paper at ICLR 2021
1 v
S B - pat) w"ll +E La + a
N maz o²
The bound for We+1 V 1| for the two sampling schemes we consider is provided in Eq 7) and applying it write the step progress for partial participation
We+1 w 1 S (1 - poo, po.))Bl.. w
2 Oie
mazo
+
4
6E (9)
N
and the same arguments using induction and T-ssmoothness the full participation case implies
kiv max
o² 0²/u
KE /u R²a
E²
/m
EF(WT)= F = =0(
NT
KT
T
E.1.1 DEFERRED PROOFS OF KEY LEMMAS
Here first rewrite the proofs of lemmas and from Li et (2020b) with slight modifications for the consistency and completeness of this work, since later we will use modified versions of these results in the convergence proof for Nesterov accelerated FedAvg.
Proof of lemma 4
g: 8el12 -E1 g:
Egg
pk gr. Ege,l
oi
Proof of lemma 5 Now we bound E E Pk W. w following Li et al. (202bb). Since com- munication is done every E. steps, for any 2 we can find a to S such that l- S E 1 and w to Wt, for all k. Moreover, using a, is non-increasing and Otto 20,; for any L - lo S E -
we have
Pk w. w/112
Pk /w
We (w, -l
<R
Pk: || w/
weo 12
k=1
Pk: /w
w/,11 11
N
=E
Σ
Pkll
Σ
a;gi,al2
k=1
i=to
N
1-1
<2
LE
Ea²
gi,
i=40
N
<2
Pk: E
E G2
k=
<4E²
18

---

Under review as a conference paper at ICLR 2021
prove the upper bound of one step SGD progress. This proof improves on the previous work Li et al. (2020b) and is the first to reveal the linear speedup of convergence of FedAvg.
Based the results of Lemma 4
5
Proof of lemma 3
We have
W
w
[W; a(gr) -w'12= = |( 0,g; - -w") - 0,(g.
8
W
w -a1gi 112 + +02 20, w" a1g Bi
+ t
8.l
A1
A2
As
where we denote:
A [W W 0+grl1 2
A 20r (W: W
-l: B: - -gr)
A3 = of ge Bel
By definition of g, and g, (see Eq 44 ) we have EA2 = 0. For A3, we have the following upper bound (see Lemma
a Bell 0
Pk
k=1
Next we bound Ai: W. w g.
W. w w=| 2(W, w", - + |log,e1l
and we will show that the third term ||ag, 2 can be canceled by an upper bound of the second term, which is one of major improvement comparing to prior art [i al. (2020b). The upper bound of second term can be derived as follows, using the strong convexity and L-smoothness of Fg::
-2 W.
w ge)
20
Pk (w: -w. ()
20,
Pk (W; W.
w VF&(w))) 20g
Pk (w w', VF((w!))
N
N
< 20r
Pk (w. - w/, vPx(w()) + 20r
Pk ll - -1 pk (F - -F((W))) -01f4 Σ
k=1
k=1
<204
Ph
F Fl((..) + L
w ww'l + Fk(w") Fu(wW))
auull Σ p&
w/
k=l
=0, L
Σ
Ps pkllw, w/ + 204, Σ Ph [R((")) (w()) a.jll/w w=1l
1=1
We record the bound we have obtained so far, as it will also be used the proof for convex case:
N
E W We+1
w=11
<E(1
uay)
w=1l + a
Ph
We w!!l?
20r
Σ k=1
Ph (Fa(w") Pa(ww)) o
12 of
P k=1
(10)
For the term 20, Ex= Pk: [4Fx (w") Fi(w (w:)). which is negative, we can ignore it, but this yields suboptimal bound that fails to provide the desired linear speedup. Instead, we upper bound it using the following derivation:
20
Pk [F((w") (w(w))
19

---

Under review as a conference paper at ICLR 2021
2aa (F(w++1) F(w.)]
<20,E(VF( (w.) W - W.) + 0r LIE Wr-1 well"
(VF +
0 g: 2
20 81) + + L.E
g: |
- aZ
VIF(W/ W
1.1
| W
+ a. LE g:ll
= - af
[FF(w))) )112 + g
(V
Σ ps VE(()) )1
+ a7 LE gg 1
< o
VF( + IIB > Σ
- VF(w/)1
+ a LE LE|
< 3
[F(( + 11 L2 Σ W. -0
w/11?
+ a LE |
k
S - a 1.1 + af Σ Pillw, w/ + a 1 -2
k
where we have used the smoothness of twice.
Note that the term -aēlle |e exactly cancels the alllg B: 12 in the bound in Eq 10 so that plugging in the bound for - -20z W: w", gt)), we have so far proved
E 2+1 w=1l < B(1 po:))l w0 + L
phll l. -w/l- + ai
2 2
k=1
k=1
Pk l/ w| + a. LE |g: 11 + 0 L
ag (VF())l)
(11)
Under Assumption we have El 12 S G². Furthermore, we can check that our choice of a satisfies a₁ is non- non-increasing and a₁ 204+E, so may plug in the bound E E Ph: IW:
w/11 < of to the above inequality (see Lemma 5.
Therefore, we can conclude that, with Vmax == N max; Ps and Vnin = N ming Pk.
F++ w=
N <E(1 (a,) || w. - w² + 4E La 4E"LLa, + of
pf + L²
km
2 =E(1 ua.) w. w 4E La C2 + 4E o + di
(pn N) a²
N2
<IE( /l w. w2 45 Lai 4 13 G2 + a N2
2
Σ of + at LC
max
at 1 2
<E(1- -
6 La
man o²
N
where in the last inequality use 0² En k= pho and that by construction a satisfies La; S }
KE // can be removed, or equivalently KT
One may ask whether the dependence on E in the term whether Ex h.PPk/// |w well" = O1/TT²) can be independent of E. We provide a simple counterex- ample that shows that this not possible in general.
Proposition 1. There exists dataset such that if E ( for any B > 0 then En Pkll w2 ((722zz).
20

---

Under review as a conference paper at ICLR 2021
(x w) contains data points x w" with n. Moreover, the w*. come in pairs around the origin. minimized at w
Proof. Suppose that have number of devices and each Fi((w) "h وj=1
As result, the global objective by design of the dataset the updates in local steps exactly cancel each other at each iteration, resulting w, = 0 for all I. On the other hand, if E = 7 then starting from any O(T) with constant step size O ()), ), after E iterations of local steps, the local parameters are updated towards w** with ||w 1| S(TT 7) (Trww). This implies that
Moreover, if we start from Wo 0, then
Σ Pk Pkllw W++El1 = Σ Pk /|
2 7 72-23)
which is slower rate than T for any B > Thus the sampling variance B|| v--1l 2 ks p& | [ w decays at a slower rate than 22: resulting in convergence rate slower than O++) with partial participation.
E.2 CONVEX SMOOTH OBJECTIVES
In this section provide the proof of the convergence result for FedAvg with convex and smooth objectíves. The key step is a one step progress result analogous to that in the strongly convex case, and their proofs share identical components as well.
Lemma 6 (One step progress, convex case). Let We = Ex= D&W in FedAvg. Under assump-
tions] 7 3 4 the following bound holds for all t:
E w +1
w (F(()) - F(w")) SB w²1 + ag 2 o + 6a, LG N
Proof. The first part of the proof follows directly from Eq (1)) in the proof of Lemma B J = 0 in Eq (TOp (since we are in the convex setting instead of strongly convex), we obtain
Setting
N
We+1 w01 & [w w1 + 0r T.
Pk w. w/112 Σ
k=1
N
N 11 a > p
+ 20
Pk [F(("")
- FA Wt -
The difference of this bound with that the strongly convex case is that we no longer have a contraction factor of 1 aa in front of lw, w*1l In the strongly convex case, we were able to cancel az || with 2xx Σ Pk (Fe(w") - (w.)) and obtain only lower order terms. In the convex case, we use a different strategy and preserve Σ Pk [Fa(w")= - Fl,(),)] in order to obtain the desired optimality gap.
We have
g
Σ
PK (W!i11
Σ
PA VFL
Σ PAVFLL(.)) Σ Pa (F
2|
Σ
PK (W
EPNTPAWW)) +2 Σ Ps V
2T.
Σ Ckllw w. 211 Σ (w.))
2L
Pwllw
21

---

Under review as a conference paper at ICLR 2021
using (F(w") = 0. Now using the L smoothness of F, we have |VF(()))] 2L(F(w.)
F(w") }), so that
W1+1 w=11
N
< <w - w'11 + arL)
pk Σ
lw w 20z Σ
Ph:
(F((w)) - Fw(w)ll
k=1
A=
N
+ La Σ Phil w /
well + LaF - F(ww))) + ta Σ o
k=
N
-l[w, w²11 (20 L. Σ
pk pk|lw, w/ll + az
pa [F.(w")FFF(w.)))
N
+ 2
Σ of + a: (F(w)) - F(w.))
1m
Since F(w*) < F(w,). as long as 40,L S 1, we can ignore the last term, and rearrange the
inequality to obtain
W++1 w 2 ar (F(( F(w"))
W. --ww11 3 + (2a L2 + aLL) Σ Pkl w.
pkl
w/11 + +a,
k=1
N
N W. - w a Σ
3
W. - ww
Ph
2
k=1
The same argument as before yields E
Σ
k= Pkl - - 4E a G² which gives
N
N
Wi+1 w'1 + aa(F(w)) - F(w")) < w. 3313 a
ok + ba E
2 2
k=
w. w w11
2 1
2
0² + 6a LG
N
max
With the one step progress result, we can now prove the convergence result in the convex setting, which we restate below.
Theorem 2. Under assumptions 1 and constant learning rate a; = =0 LOVV ()
)) FedAvg satisfies
min F(w.) - F(w")= = o 1mmax ST
LE
VNT
T
with full participation, and with partial device participation with K sampled devices at each commu- nication round and learning rate ax =0(/ )
02 (VRT
FºG²
KE
min F'w) F(w") = O FST
VKT
VKT
T
Proof. We first prove the bound for full participation. Applying Lemma 6 we have
| - w/ 2 (F. - F(w")) < |W, w w01 at N o + GaQ
Summing the inequalities from t 0 to t = T', obtain
T
T 0 + Σ
a (F - F(w")) < |w w + Σ
3 6E LG
N
0=
t=0
t=0
22

---

Under review as a conference paper at ICLR 2021
so that
min
((:)) F(w")
|Iwo w'|l
Σ
0i
max
2
Σ
of
3
6F.
SST
Ei at
N
t=
t=0
By setting the constant learning rate at =
N T
we have
1
N
1
1
N
min F(,,) 1ST
F(w")
Wo
w
1
T
max
02
T(
NT
VNT
T
N
VNT
T
1
1
N
1
N
l/wo w11
T
Vmmaxx
6E
LG²
VNT
VNT
T
N
T
= -Ilwo
w012 +
6F.T.G
max
VNT
T
= -0 o2 o²
LE
VNT
T
For partial participation, the step progress bound in Lemma is updated in similar manner as the strongly convex case in (9) to incorporate the sampling varince. More precisely, with partial participation,
W Wet1
w=1
W V+11 V 1
= EJ W++1 V + V -'1?
V411 for all by the unbiasedness of our sampling schemes. Since Ex P always averages over all devices, the full participation one step progress bound in Lemma 6 applied to v. implies
where Ew e+1
1 N
E V
w + a.((Fv))) F(w < E w"11 + aj max
=aa
E W; -
w1 w + o 02 + F2
The bound for We+ V++ill 2| for the two sampling schemes we consider is provided in Eq 7
and applying it to the above bound write the step progress for partial participation as
E W++1 w w1 (F(()) - F(w") E W. w0 of 1
12 man 0² C + 6E G.
N
where = 6² or K Summing up the one-step progress over t,
N-T & E² depending on the sampling scheme.
min F(w.) F(w*)= Et as
(Iwo 11 + Σ
a ( pmaxx
1
+C)+ Σ at 6E'LG²) 1=
1=
so that with ar / , we have
min F(w.) F(w")= = O Vmaxxx2 0 m
E&G² KELLG VKT
+
VKT
T
PROOF OF CONVERGENCE RESULTS FOR NESTEROV ACCELERATED FEDAVG
F.1 STRONGLY CONVEX SMOOTH OBJECTIVES
Recall that the Nesterov accelerated FedAvg follows the updates
v + 3e(v - v()
ift + IE.
(+1 = w/ - -argrkk
w EkEsc 9k [vi+ + B.(v -v)]
ift+ Ig.
23

---

Under review as a conference paper at ICLR 2021
The proof's of convergence results for Nesterov Accelerated FedAvg consists of components that direct analogues of the FedAvg case. We first state these analogue results before proving the main theorem. Like before, the proofs of the lemmas are deferred after the main proof.
Lemma (One step progress, Nesterov). V
Ps v in Nesterov accelerated FedAvg, and suppose our functions satisfy Assumptions 123 and set step sizes at - d - Be-1
3
ma,( with 7 max E and # the updates of Nesterov accelerated
14(++)X11- 5t7
f
FedAvg satisfy
V
w
La S E(1 pa+) (1-1) - w²1 + L + +11 (1- (0--))))3311 (1Ve-1lll-11--- (1- w
2 1 at N Vmaax0 + 2 B1-1) au))l -1-p)ll -w"ll 1|ve-1 -wl
The step progress result makes use of the same bound on the gradient variance in Lemma as well as a divergence bound analogous to Lemma which we state below.
Lemma (Bounding the divergence of w/,, Nesterov). Given Assumption and assume that as non-increasing, a₁ S 204-E. E. and 2 + 20 S 1/2 all 2 O. w. k= Pk w in Nesterov accelerated FedAvg satisfies
E
Σ Pk w. w/1l? 16(E-
Theorem 3.
Let VT EN pevt in Nesterov accelerated FedAvg and set learning rates 14(+1))
0r 4 E4g' 3i-1 participation,
5
max(u.]] Then under Assumptions 7 3 with full device
EF((T) - FM = (NVmaao X2EEG
NT
T
and with partial device participation with K sampled devices each communication round,
EF( - F" =OO [KPmaxo2
xFPGP/
x²
NT NT
KT
T
Proof. We first prove the result for full participation. we have
Applying the one step progress bound in
Lemma 7
E w
< E(1 1a,) 1.-1) w 20 + (1 a,14) 10 [[V, w )11
1 a N "maxx2 +
3r-1) - a1,44 -wll w'll /| - w"l
Recall that we require Okto < 20r for any 1- < E 1, Lax, < and 2,3 + 2a < 1/2 in order for Lemmas and 7 to hold, which can check by definition of ar and Br.
We show next that E V 2 = O ( om 0²/v LL 1
by induction. Assume that we have
IN
shown
ElIV w012 (Caa + Doa))
for all iterations until I, where C = 1OE D
1 1 0², and is some constant to be chosen
N
later. For step sizes recall that we choose at z4y
and 3 14(++))1 max(p.13 where
3
y max m32x, F), so that B,-1 04 and
3
- (1= + 148, < (1
[1
+
1. 1
(t + 7)
-
6
6
3
3
= -
+
=
t+
t+
t+
2
24

---

Under review as a conference paper at ICLR 2021
Moreover, E| V w- - b(Coq_1 + Dau-1) & 4b(Ca; + Dai) with the chosen step sizes. Therefore the bound for E V++1 w01 can be further simplified with
23,- + 3y /1) v w-ll -Ive -w'l < 43,- (1 + B(-1)(1 ((1))))) blCal + Das)
and
(1 (L- - w')l - - 4(1 0. -(Ca, + Das)
so that
E| V141
w'11 s (1 - (1=)((1) + Bc_1)² + 131-1(1 + BL-1) + 15 -(Ca, + Dat)
+ +20 Lai + ai N
Umaxxo
S SE[11 (1a)(1 + 14 b(Ca, + Doa) + 20E La + of 1 N Umaxo?
S 6(1
pat
(Ca + Da.)) + Cu. + D
2
pay
+ aa)a C + (b(1 han
= (b(1
) + aD
2
2
and so remains to choose b such that
(b(1 uay + ar)a, S bo2+1
(b(1 pay + aa) at)aa S b
from which we can conclude B|| w=1 S o C' + a.
With b _=¹ we have
(6(1 - uac 2 )+ + aa)a = (b(1 - ( [ + 7
6
6
+
ulll + 7)
ull+
(b t + y - 3
6
6
+
t ++, γ
ult 7)) (7)
< b( + γ -
++ 77)
6
< b
box4+1
1(t +1++
where we have used 14y-1 (1+7)²
S
1
144+1*
Similarly
(b(1
pay
+ +az)a? = (b(1 -
3
+
6
)
(
)
2
1
ull 7)
mll + 7)
1 t 3
6
6
+
ult + 7) )(
t+
p(t + 7)
b( ++ -2 2
6
)(
}²
t+y
u(( + 7)
36
< b 122
bo
(t
+
+ 1)2
where we have used
2 (1+7)² < [1+7+1)*
Finally, ensure ||vo - w²| < b b(Cağ + Doo),, we can rescale b by clivo w² for some c. It
follows that Eliv, - w= S b(Coe + Dot)) for all / 2 0. Using the L-smooothness of F.
E(F(VT)) F (V(F(V)) F((w))
L
L L <llvvo -w2 (DoT + Co3))
Bl|VT ww1 <
2
/
25

---

Under review as a conference paper at ICLR 2021
3cl|vo
-w'1? ( + Car)
6
6 M(T + 7)
3cl|vvo - -w"1l2m
1/maxx0++ +000²
2-200ELC LG
u 77) N
00- R 1 p N m
1 x²
1 T
T
With partial participation, the same argument with added term for sampling error yields
EF( F = O KVVmax /p
KE /p
R²² E² /p
+
NT
KT
T
F.1.1 DEFERRED PROOFS OF KEY LEMMAS
Proof of lemma & The proof of bound for IE Σ k= lw w/ 1| in the Nesterov accelerated FedAvg follows similar logic in Lemma but requires extra reasoning. Since communication done every E' steps, for any f 2 O, we can find to I such that t - to S E' and w We, for all Moreover, using 04 is non-increasing, ato I 22,, and Be S a for any t to I 1, we have
E
Pk W.
w/112
E
Ph lw
Wio -(w, -Wo--w,0ll )1
E
Ph w/
w1,,l?
N
E
P
P/ -wiol1 w/ol?
k=1
E
Phl Σ 3. 3i 3 -v,) Σ
aggi
k=1
1=to
N
1-1
N
2
Pk
(R - 10-1)022l Σ
E Σ 1F-1))8(((v2) -
k=1
1=1
t=
P E
EE 1)a (1 1+++11(11 [1 v/)133)
N
< 4 Σ
E
EE - G)a
k=1
i=to
S 44EF F-
a) G2 < 16( - 1) 2
where have used E| V v 2 < G To see this identity for appropriate ar, 8r, note the recursion
*
(+1 v t = - - - (argr.k at- 1.)
w c+1 w -0, Be( -t²)
so that
++1 v -a 18--181-1,* + (v - vi-1) - (aggik--o - -1-18-111
= (v - - aggrt
Since the identity k vi = (v - -v/_)) 0lggr, implies
El v/i12 < E. v
20?
as long a,, 3,-1 satisfy 2,3 2a < 1/2, can guarantee that Ellv - v/= 1 < G² for all
I by induction. This together with Jensen's inequality also gives TEl[V, V,-1 12 < G for all I. n
26

---

Under review as a conference paper at ICLR 2021
Now are ready to prove the step progress result for Nesterov accelerated FedAvg. The first part of the proof is identical to that the FedAvg case, while the main recursion takes a different form.
Proof of lemma
7
We again have
V
w'1 l( argr)
w=
and using exactly the same derivation as the FedAvg case, we can obtain the following bound (same as Eq in the proof of Lemma 3):
N
N
Wi+1 w=
Pk Wt - w/11 + a $ B(1 - pas)ll - 11 + a Σ
N
L + ai
Pk pkll w. will ai LiE g: - a (w.
Different from the FedAvg case, we no longer have W, V,. Instead,
||,, - w 2| V. + 3 (V, Vt-1) w²11
= [[(1 + 3)-1) - -w) - ----1(Ve-1 - (
10-1-w))- = (1 + 8-1 )ll,, - -w"12 -1,--22 + f (0-1)((v, -w:,-w",ve V - w²)
- -
$ (1+
+ FFf-wwll - -
-
which gives recursion involving both v. and v.-1:
N
M - - 1 + w011 + +2(1 - cap) B:-1)lll - -w"l / w"ll + a. > p
k=1
N arL Σ w 2 ph: ps/ - - LG2
and we will using this recursive relation to obtain the desired bound.
We can check that our choice of a and 8r satisfy is non-increasing, 0₂ < 20 and 25, + 2 S 1/2 for 2 0, so that we can apply the bound from Lemma on E to conclude that, with Mmax = N max Pk:
N k= Ph Wt w
V w
< E(1 pai) B )l
w 1 + 16 + 1' + LG
+ - (1-041) 11 w²]l + af Σ p 23 (1 3;-1) a. - w"ll 1/V -
< E(1 pan) + Br ( w 1 + 20E La G2 + - a1 ( -
1
a N "maxx= 23, -1- w'll 1|v wil
where we have used x² ExProo and by construction our o₁ satisfies Los S 1.
F.2 CONVEX SMOOTH OBJECTIVES
In this section we provide proof of the convergence result for Nesterov accelerated FedAvg with convex and smooth objectives. Unlike with the FedAvg algorithm, where convex and strongly convex results share identical components, the proof for the convergence result in the convex setting for Nesterov FedAvg uses change of variables, although the general ideas are in the same vein: have a one step progress bound for E| W - w*1l2 + (F(..)) - F(w*)), )), which is then used to form telescoping sum that gives upper bound on minegr F(w.) F(w*).
27

---

Under review as a conference paper at ICLR 2021
Lemma 9 (One step progress, convex case, Nesterov). Let
Σ k= p&w in Nesterov accel- the following bound holds for all
oc erated FedAvg, and define I-D:- Under assumptions 7 134
1 o0² 2 + 21/t
3
BlJ w (F(ss) F(w")) & Bl|w., w0 32LFF2 mhe Vinx N
G²
3
Theorem 4. Set learning rates an 3, = OOV )) Then under Assumptions 134 Nesterov
accelerated FedAvg with full device participation has rate
=O= Vmaax NE
min F(w.) tST
VNT
T
and with partial device participation with K sampled devices at each communication round,
F -F*== 0 (
EºG
KE
min F(we) KT
VKT
VKT
Proof. Applying the bound from Lemma
9 with mp I-p1 have
1 0² + 2n
33
W w' + +c F(w'((()))) S E W. w 32LE af + nh Vmax
G²
N
1- Bc
Summing the inequalities from t to t T, obtain
B
Σ (F (Fww)))>www))) |Wo w +
th
may 32LE + >
2m
G²
N
3
0=
0=0
t=0
t=0
so that
min P(w.) F(w")
IST
Eizo Nt
[I w w/1 +
Σ
T
11(
N
V
Vaax
0²
Σ
T
naf
32
T Σ
2111
18
B
G²
t=0
t=
[=0
By setting the constant learning rates (; / N4 and 3r ev N so that 1/- = =
v
1-cv
+
N 2
T
we have
min F(W.) - -(ww") tST
$ 2/NT
-lwo - wI +
T N 02
N T(
332LE
N TT TW
T 1.02
VNT
VNT
T
VNT
Iwloo 21 2v 2 ?
1
(32LE 2G²)
N
VNT
=0( 2maxo2
NE
VNT
T
Similarly, for partial participation, we have
T
T
min F(w.) - F(w") ST
[lo - -w1 +
Σ
aj
(
1
Vmaax + +C) + Σ at 6E LG2
ΣT ai
N
1=0
t=
where C' 4 or
N K
E2 so that with
/
K T
and 3r = / 4, we have
N- R
F(w.) - F(w") = O O2
FºG² KEIL T
min
KT
VKT
VKT
28

---

Under review as a conference paper at ICLR 2021
F.2.1 DEFERRED PROOFS OF KEY LEMMAS
38 (v. - Vz-1) for / 2 and 0
Proof of lemma g
Define P, I-p Dz Wr Wr-1 + 0...-1]
I-33
fort = 0. We can check that
04
W++1 + P1+1 W P
3g
Now we define 2, = We P and
oi 11t 1-3. for all i, so that we have the recursive relation
24+1 = 1/:8t
Now
E++1 - w'113 || 17/ge) w"1l
= =I(Z 1/ - -w") 7/( - E.)l
A1 + A + As
where
A = 17 w 1/.B. 1
A = 211 w
-1):22 8: gc)
Ag n/ lll. Be ||
where again EA2- 0 and EA33 S nे Σx o. For Ai we have
12 w
7/ |1 = 1|2 w1 2(z - -110)) + ||
Using the convexity and T--smoothness of Fu.
2mp (Z w", g.)
2n ph (z. w', (F&(w())
N
2m
Pk (Z: w/ (FF(w()) 27k
Pk (wt - -w", -w, VFx(w))
k=1
N
-27
Pk [7, w. (w(( - 27p
Phe Ph: - w VF&(w)))
21T
Pa (w VF,,FF((?))
k=1
k=1
A==
21/
Σ Pk: (z, W., (F(())))
21 Σ Ww 2m Σ P& Px(Fx(w") Fs(w())
N
L
< 2T
Σ
pk: Fk(WW)) - FA (W,) + 2 w. =f()= -
27p.
Ph (z: w., W., (We))
k=1
| Pk
W.
w + 27/ Σ Pk [Fa(w") F&(We)) 27
Plo (z w. (F(()
which results in
N
N
W1+1 w
- W. 11 + L Σ
Pk
w. p
- w/ll 112 + 2n Σ Pk [F((w") FA(w.))
km
N
g
1/
Ok
k
2m:
Pk
(z. w., FF)(w
1=1
k=1
29

---

Under review as a conference paper at ICLR 2021
As before, | 1ell22
222 Ex
Ps:l l!? - well + (L(F(w))) F(w")), so that
N 1: 2 +
S 22 Epullwe - well + m1 -4::)(F(ww)) - F(w:))
Phe
< 2222n m/ EpHllw -wel?
for T) 1 1/4L. Using Σ k= Pk w w w/ll 16 a and Σ oo S Vmax N 0² it follows that
N
W 411
w²112 + (F(.)) - F(w")) $ Bl| w=12 +22
Ph pallw, - w/ll -. + ni Σ
km
Amm
N
21/
Σ
Pk (Zi We, VF&(w
w012 + + a, + nhe Vinax N 0²
E
W.
2m
Pk (Zi
We, (Fi(ww)))
if T/ 1 1
It remains to bound E >k=n Pk (Z:
Wx, VFx(())) Recall that 2 We =
2L
W W + a-::-1==
1-3, (V: v(-1) and
8²
B - v--1 VF G².
3
Cauchy-Schwarz gives
N iz W., VF&( S Σ
E
Pk P&VE E 2
wil BI
k=1
8²
G2
1 - Br
Thus
3
E| W ww F(w")) < Bl|w. w²1 + 32 + ni Vmax N +
21
G²
3
G GEOMETRIC CONVERGENCE OF FEDAVG IN THE OVERPARAMETERIIZED SETTING
Overparameteriizaion is prevalent machine learning setting where the statistical model has much more parameters than the number of training samples and the existence of parameter choices with zero training loss is ensured Allen-Zhu al. (2018); [hhnn et al. (016). Due the property of automatic variance reduction in overparameterization, a line of recent works proved that SGD and accelerated methods achieve geometric convergence Ma al. (2018), Moulines Bach (20TT); Needell et al.) (0044): (Schmidt & Roux 2013);; Strohmer & Vershynin (009). A natural question is whether such result still holds in the federated learning setting. In this section, we provide the first geometric convergence rate of FedAvg for the overparameterized strongly convex and smooth problems, and show that it preserves linear speedup at the same time. We then sharpen this result the special case of linear regression. Inspired by recent advances in accelerating SGD Liu et al. (2020); Jain et al. (2017). we further propose a novel momentum-bart convergence rate over FedAvg. Detailed proofs are deferred to Appendix Section H. In particular, do not need Assumptions and and use modified versions of Assumptions T and detailed in this section.
FedAvg algorithm, which enjoys an improved
30

---

Under review as a conference paper at ICLR 2021
G.1 GEOMETRIC CONVERGENCE OF FEDAVG IN THE OVERPARAMETERIZE SETTING
Recall the FL problem min Ek=1 Pk P&(() with Pa (w) ny Σラ= ((w; In this section, we consider the standard Empirical Risk Minimization (ERM) setting where is non-negative, 1-smooth, and convex, and as before, each F5 (x(W) is T-smooth and j--ttrongly convex. Note that / > L. This setup includes many important problems in practice. In the overparameterized setting, there exists w" E arg min, ==1 Px-F (w) such that {(w"; x 0 for all x We first show that FedAvg achieves geometric convergence with linear speedup in the number of workers.
Theorem 5. In the overparameterizee setting, FedAvg with communication every E iterations and constant step size a = 1 Iumax LLNN- -umin) has geometric convergence:
N
T. (T( - (1 a)² Wo w w o (Lexp) (-E EElmmax + L(N Mmin)
NT
1|wo w" w²1l3)
Linear speedup and Communication Complexity The linear speedup factor is the order of O(N/E) for N I O i.e. FedAvg with workers and communication every E iterations provides geometric convergence speedup factor of O(N/E) for N s O(1)). When N is above this threshold, however, the speedup is almost constant in the number of workers. This matches the findings in Ma et al. (0118). Our result also illustrates that E can be taken O for any < 1 to achieve geometric convergence, achieving better communication efficiency than the standard FL setting. We emphasize again that compared to the single- server results in Ma et al. (2018). the difference of our result lies in the factor of in the speedup. which cannot be obtained if one simply applied the single-server result to each device in problem.
G.2 OVERRARAAEEERRIEE LINEAR REGRESSION PROBLEMS
We now turn to quadratic problems and show that the bound Theorem can be improved to ((exp(-EN Ex_ ()) for larger range of N. We then propose variant of FedAvg that has provable acceleration over FedAvg with SGD updates. The local device objectives are now given by the sum of squares F&g (w) 2ng Eje, - (w"x) x 2 and there exists w such that F(w") = 0. Two notions of condition number are important in our results: K1 which is based on local Hessians, and R, which is termed the statistical condition number Liu & Belkin (2020); Jain al. (2017). For
their detailed definitions, please refer to Appendix Section Here we use the fact & S Kj Recall
Umax max; pk N and Unii ming N...
Theorem 6. For the overparanterized linear regression problem, FedAvg with communication every N
E iterations with constant step size = ( Trmax +N(N -vmaa) has geometric convergence:
EF(wr) 50 [Lexp(- E(vmax K1 (N v )l(wo w'))'
NT
Ex, )). which exhibits linear speedup in the number of workers, as well as a 1/K1 dependence on the condition number Ki- Inspired by Liu & Belkin 20200, propose the MaSS accelerated FedAvg algorithm (FedMaSS):
When N = (x1), the convergence rate O(11 )²,))) = ((exp(-AX)
u n/geA
if + 1 1 Ip. ift+leZ. Iz.
w +++ Evesm |u
w w + w/) gr,k-
1+1
When v/ = O, this algorithm reduces to the Nesterov accelerated FedAvg algorithm. the next theorem, we demonstrate that FedMaSS improves the convergence to Olexp( EVELR = To our knowledge, this is the first acceleration result of FedAvg with momentum updates over SGD updates. Theorem 7. For the overparamterized linear regression problem, FedMaSS with communication
N every E iterations and constant step sizes 7/2 = -0 Lumaxe FuNN -Vmin) T/2 has geometric convergence:
(1(1 VaJa
K EF(WT) 5 [Lexp(- Elymax Kikk k + (N Mminn)
NT
) )/ - wx1l2)
31

---

Under review as a conference paper at ICLR 2021
Speedup of FedMaSS over FedAvg To better understand the significance of the above result, briefly discuss related works on accelerating SGD. Nesterov and Heavy Ball updates are known to fail to accelerate over SGD in both the overparameterized and convex settings Liu & Belkin (2020); Kidambi et al. (2018); Liu et al. 2018); Yuan et al. (2016). Thus in general one cannot hope obtain acceleration results for the FedAvg algorithm with Nesterov and Heavy Ball updates. Luckily, recent works in SGD Jain et al. (2017); p: [iu & Belkin (2020) introduced an additional compensation term the Nesterov updates address the non-acceleration issue. Surprisingly, show the same approach can effectively improve the rate of FedAvg. Comparing the convergence rate of FedMass (Theorem 7) and FedAvg (Theorem 6). when N (()))) the convergence rate is .T
Es )). Since K1 2 this implies speedup factor of y for FedMaSS. On the other hand, the same línear speedup in the number of workers holds for N in smaller range of values.
((L EVKRR )²) = O(exp(-xxp)) O[exp(-Everr "
opposed to O(exp(-
EVEiK
H PROOF OF GEOMETRIC CONVERGENCE RESULTS FOR OVERPARAMETERIZED PROBLEMS
H.1 GEOMETRIC CONVERGENCE OF FEDAVG FOR GENERAL STRONGLY CONVEX AND SMOOTH OBJECTIVES
Theorem 5. For the overparameterized setting with general strongly convex and smooth objectives, FedAvg with local SGD updates and communication every E iterations with constant step size
2E Iumax +NN Vumin) gives the exponential convergence guarantee
N
L - (1 wa w= O(exp(- 2E IVmax + L(N Vmmnn) EF S
N
t) l|wo w=1
Proof. To illustrate the main ideas of the proof, we first present the proof for E = 2. Let t be communication round, so that w = Wc-1- We show that
w11 (01))1))1111 a4-141) - -w1l
for appropriately chosen constant step sizes Ot2, a1-1- We have
W(41 w 3| = |[ - a(gi) - w=1
W; w011 20z (w, w',gr) + +g
and the cross term can be bounded as usual using p-convexity and L-smoothness of Fg:
-20; 2o, (w.
w'. .()
-02
Pk Pl w", FF&(W())
N
N
20g
Pk (w, - W/ (F((W))) - 20,
Σ
Pk (w w", (F(()))
k=1
k=1
N
N
N
-20g
(w, w/. (F)(w!)) + 20,
Pk (Fa(W") Fx(w()) - a0ff >
/ w=112
k=1
k=1
k=1
200
Pk
(w()) Pk(w.)) + 1/2 || - - Fa(w3)) a.pl
(aww
w=)
N
= L
Σ
Pk w. - 11 1 + 20, Σ Dk [F+("") Fx(W))) a.u We -w11
32

---

Under review as a conference paper at ICLR 2021
N
N Σ
-.,L Σ
Ph: ww w/112 -22,
ph - -w
k=1
1=1
and so
We+1 W E(1 aa -'113-2a,, (w,) + lgll 2 + a, _
Ph: wr w/1
R=
Applying this recursive relation to l/w, w²12 and using || w 112 = 0, we further obtain
E|| Fi|w++1 w1 - B(1 a,p²) ((1 02-111) w w011 1100- F(W(-1) + az- 11_-1
N w will?
Fa,F + at a:l|g: 2| + +aLL Σ
Now instead of bounding Σx= P& W. - w|ll using the arguments in the general convex case, we follow Ma et al. (2018) and use the fact that in the overparameteriize setting, w" is minimizer of each [(w, 22)) and that each E is I-smooth to obtain
&h 1)l? (w.,,,,
Fi (w", ek )), where recall (w < ((w, (f-1)) 1). so that
N
N
Pk. I/
w/1l =
w + 11-1811,,11 Ph W 0--18-11
k=1
P&O g/-1 11-1,A112
2
Pk g 1 11
0
N
2
Ph VF V 1
k=1
2 <
p.2 Fw
again using W w Taking expectation with respect to ck 4 's and using the fact that F(w*) = 0, we have
E
Pk W, wf'l < 20021 ph Pp -
k=1
= F(W,1]) - - 16g_11g 11
Note also that
N
gg 2
Pk
while
N Σ Ph
N 2 Σ F.
Pk V (we, + Σ Pk (V..(W,.))) - VFL(W, E.)))
g
km
km
N
N
2
VF.. + Σ
pul w. w
A=1
k=
Substituting these into the bound for ||W--1 w/ll
we have
33

---

Under review as a conference paper at ICLR 2021
W w'11 & (E - (114((1 - -0-111)
- - 20 ( + of
2axF(we) + 22a2l
V (we, (21% + t 14) (21F(W(-1) - -18)-1113))
Ph
k=1
EE(1 -ax a4-1) W -w- w'1
N
20l(F((W)) aull Σ
pk V.
-00 Ots11) (1 lax
10 + a²L)
} F[(
0t-1
VF (1,,,, ,6-1)11))1
Ph
1-091
2
from which we can conclude that
E W
w*1 s (1- -
we can choose ag a to guarantee
E(F(w,) - arl Σ
Ps (W
k=1
la--1 1212 + arLb) )F
E (1
F(w,-1)
0t-1
Pk V 20
1 -011
2
k=1
Note that
N Ps V (W,
E/ll
Pk
VF = E, Σ
(t) Σ pk (P..).(We.tt)
N
N
p
V
B. (VP.
PiPa
(Fy(W,, VFF
k=1jzk
N
PVP (F))
N
Σ
(P. Σ
VF(W)) Σ p (w,)
PsPk
VF + Σ P& VFF
Pmin Σ PP.VFA(W.)1
V
N Mmin /F(w:)]1
and following Ma et al. optimized later, we have
(0188) if we let az
mine oN Bl
1-9 for a [0, to be
2L(1 $ (emin)
E.F((W.) 0nl
ph F. (11,+)))
N
N Σ
2 E,
Phe Fx W
VF
+ +(1 N VFF.))FF(W.)))
34

---

Under review as a conference paper at ICLR 2021
N
E
Po
Or N max [VF ((1 - g)w,,, arl1 N mmmi ('
1
1 VF((:))1))
(F w
2L
again using w' optimizes Fi(ww et with Fi(w", (t 0.
Maximizing ar min{ mi 2L(1 x Pmin)) over [0, 1], that q Wmaax + LAN Manin)
aN 1-g
Wiaax
results in the fastest convergence, and this translates at Limaa LIN vmmnn) Next we claim that N ac-1 = cJ Wmxxx L(N +L(N-Pain) also guarantees
B(1 la (2 + oab) F((w(11)
Ctt-1
N V
1 agp
2
Note that by scaling a4-1 by a constant S if necessary, we can guarantee Inc 1(219 L. and so the condition is equivalent to
<
1-0cK
N
F(W.-1) - 01-1
Σ
Ph
(
N which was shown to hold with 04-1 S IVmay L(N-Vmin)
For the proof of general E 2 2, we use the following two identities:
g+
2 2
Pk
V
We,
52)
+2
pat W. w/
1=1
1=1
E E w/ E2 1
Pk w.
21
Ph Px|[w,-11
w/ 80 20 l1g. 11
where the first inequality has been established before. To establish the second inequality, note that
N
Pie lw:
w/112=
Σ
Pk
W
-4-18-1111111111 w/_ + 11-118-1,
k=1
N
2
Σ
Pk (1 W wh 1|100 10-181-1.1113
k=1
and
Σ Phll - -8-111 Σ Pl P, 11
( + V (F 1 (21 V W -w
ck 1112 -|g ||
2 > (I & w - ||g:-112
so that using the I-smoothness of E,
P& W. 1
N
< E2( + 21 a
Σ
pk w.
w/
4a?
Σ Pkl
35

---

Under review as a conference paper at ICLR 2021
N
S E2(1 + 22
Σ
Ph: W--1 w - + 40,-121
EPx(FF
(a - (_(w".._) 1oi-ill:-11
k=
E2(1 + al
- - 12a
Using the first inequality, we have
E| El/w++1
-aru)]lw - -w1
20,F(Ww + 22
pk Fi (w,,
k=1
N
+ (20 L,
Pk pkll - pxllww w! Σ
k=1
and we choose ar and 0 such that ((F((,,))) aeel Σ Ek=I P.) and (2a a,L) s (1 a2,1) 122 14-13 This gives
B|| w²11 < [E1 (114)((1 az 11) -w'12 -21 20 F(W,,1) 20
Σ
(F
k=
(2a 12 ai- 2 P& Wi-1 w Σ Pke w. w
Using the second inequality
N pkll - w|11 < E2(1 22 Σ
Ph. Wc-1 w2-111 (F -1a2-111g--1
km
and that 21122120711 3, 20 12 + 1/-1 L 5 1, we have
Wr41 - w=11 < IE(1 a:14 -00--01-11/0 at-14) W w11
N
20:11F(we-1 + 20
Σ
V W (w:-1,
k=1
+ 12a (2) 2 Ph
W -
and if a4-1 is chosen such that
(F(W.-1) 40, -
Σ pk VF -
and
(20 + (n(1 01-111) S 22 + //211//3
again have
N
W w' 1 < E((1_ a-1 - w 22 + a1 (2 Pk -
Applying the above derivation iteratively E times, we have
El|we+1 - < E(1 oufz) ... (1- (1-04-- -0 -1--/]][w/--- 2
36

---

Under review as a conference paper at ICLR 2021
N
-0 F(W,-T) + 20,_7! 11
Ph V (w, (w,,,, IF
k=1
+ (2a) 112 ()- + 1)
Ph w - -
k=1
as long as the step sizes at-r are chosen such that the following inequalities hold
12 + - -41-/1)) (20 + a-r-1
2 + 21 53
20 12 + 11-
N
(F(w:-))-Araa-ll - 4T()-:1((W--))) - 06-T/1
Σ Amm
P& W 5t-,)1 20
We can check that setting at-r CT41 Timax
for some small constant satisfies the
Umin)
requirements.
Since communication is done every E iterations, Wio = w for some to > t- - E, from which we can conclude that
t- Lg
E W.
w
11
p [1)0+))][[w,, 2
< (1
1
b- Wto w11 1
E
luuax L(N Vanin
and applying this inequality iterations between each communication round,
W. - 12 < (1
1 E |Vmax + L(N
N
)' 'l[wo w=11
Vmmin)
N
(expl(
t))l(wo w 11
E IVmaa + L(N Vminn)
With partial participation, we note that
E |||
1² = E. W++1 Ve+1 Ve+1 w²1
E W++1 V+til12 B1| w'11
1
Σ F w F -
K
and so the recursive identity becomes
E W
w 1 < E(1 as./)) .. (1 -
N
20, -24_, F(W.-T) + 20
1
Pk VF &Ta FF (WW
N
+ (2a +
[(T +
Σ
Ph pkl W -
K
1=1
which requires
(202_,12 + -0- + _ (1 -04--- -4-7/11) S (20² (207_ + 1
R 1
K
2(1 + 212 53
20 2 12 1 a
K <
37

---

Under review as a conference paper at ICLR 2021
N
(F(w,-r)- 4T0; ar-rll
Σ k=1
Pe (W
to hold. Again setting at-r = Cr41 Uimar L(N-Muin)
for a possibly different constant from before
satisfies the requirements.
Finally, using the L-smoothness of F.
F(Wr) F(w")( WT - w'1l O(Lexp(- 1b
1 E
L
N
T]) wo
w/
UVmax + L(N 1/min)
H.2 GEOMETRIC CONVERGENCE FEDAVG FOR OVERPARAMETERIZED LINEAR REGRESSION
We first provide details on quantities used proof of results on linear regression Section The local device objectives there exists w" such that F(w") )= = 0. Define the local Hessian matrix as H = Σド= x (x))
given by the of squares F&(w) 2nd Σド= (w²
x 2 and
and the stochastic Hessian matrix as H == E: (T,)T, where ş the stochastic sample on the kth device time t. Define I to be the smallest positive number such that E||sk ( 3 /H* for all
k. Note that < m ||x] 112 Let and μ be lower and upper bounds of non-zero eigenvalues of H Define K1 := 1/ and == L/μ.
Following Liu & Belkin (2020): Jain et al. (2017). we define the statistical condition number ñ as the smallest positive real number such that E >x Pa H H < RH. The condition numbers #1 and are important in the characterization of convergence rates for FedAvg algorithms. Note that K1 and R1 > R.
Let H E. H In general H has zero eigenvalues. However, because the null space of and range of H are orthogonal, in our subsequence analysis it suffices to project W, w" onto the range of H. thus we may restrict the non-zero eigenvalue H.
useful observation is that we can use w x
z
rewrite the local objectives as Fs(w)
(ww w", H&(w w")) = l|l
w 1 Ii
Fw(w) = 1
w [kj Zkj - (w"
Xk.j
(w
"')""x""" xk.
2nk
2m
2 (ww w Hw w*)) ||w 111
so that F(w)= = 1 || w" 1?z--
Finally, note that EH me Σド (x())) H and gi, (w&.w ( w*) while g: PA
Em p (w! w*) and E. E
H (w! w*)
Theorem 6. For the overparanterized linear regression problem, FedAvg with communccatinn every E. iterations with constant step size ( = O
1 Tvaas +u(N -Pmms) has geometric convergence:
EF(wT) 50 [eeppl
NT
)[[wo w" w²1l2)
E(Vinax (N Vmin))
Proof. We again show the result first when E = 2 and t 1 is communication round. We have
W w² 2 = [[(; orgg) - w w0ll
w, w11 2 20x, ( w".g.) + o
and
-2 w", w')
38

---

Under review as a conference paper at ICLR 2021
N
= -220
Ph ( w", (w+(w)))
k=1
-24
Pk (. w (w)) - 20
pk: (w -w", FFF(w())
k=1
k=1
-20
Ph: Pk:(W; - w (w((w(
200
pk (w? - w", H -w))
1=1
N
N
= -24
Σ
P - w. (FF(w()) 4a Σ Fl(())
kml
km
< 20;
Ps (w? Fw,,,)
2
- -w?113 40, Σ Ph Fx(?))
-
k=1
N
a,L
Ps: W; - w//12
20x
Fk Fk (w.) - -axe Σ PxFF(w
N
N
T
Pk ||: w/1l
Σ
((w(( H²), -w")) 204
Σ
Pk (w
k=1
k=1
1=1
and
N
I|: 2
Σ
ph H (w, - ww
k=1
H (w. ww") + Σ
p (w w.)l
k=1
k=1
N
$ 2||
Ph H (we - - 2/1 2 Pk H. (w? ww)]l2
k=1
which gives
B|| w01l S El|ww,
w=1
(w,
-w" H ww -w") + 20
Ph: H H.H:H, (w: w")l
k=1
#=1
L
p
w. w/'l
2a Σ Pk H (w w:)l 20, Σ (w
following Ma et al. (2018) we first prove that
N
W, - 11 ae
Ph ((w, w"), (w, - w²)) + 2a Σ
pa - -W:"""""
N
< 8(2max K1 + (N Vmnin) ) El(w 11
with appropriately chosen du Compared to the rate O ((Trans L(N Panm - for general strongly convex and smooth objectives, this an improvement as linear speedup is now available for a larger range of N.
nN
0 Vinus - Pinin )
We have
E.ll
Pk H. (w:- w2
N
E,
Pa H.
(w,
w"). Σ
H w)))
39

---

Under review as a conference paper at ICLR 2021
N
N
Σ
pk E
H w - -w) +
PiPa
(w H. (we - w"))
k=1 jzt
N
Ph Be H ( -->>= +
( - w²))
k= jz
N
p B
( w²)1 +
Pypale ( -w), H. w*)) Σ
pk H (w: w")l
A=1j=1
N
H ( -=) + Σ (..
Pk
N
Ph B.
-w: + Σ -w
Vini Σ p& H ww)|1
N
Vmax
Pk Eg H w. - + (1 N
Munin) )l
ΣptH H We - -w")l
N
k=1
k
max
Pk (w w' H (w, w) + (1-
N Mmin)) )| Σ Di w")l
V'max ((w, w'). H(W, w + (1
N Vmin
(We -w", ",,HH(W -W())
N
using || || 16 L.
Now we have
E W. w/11 0t Σ Ph ((W, w"), w"), w")) + 2a Σ H (w: w²]l
(w w ( 20
Vmax
H
N
Vmnin
H )) w())
N
and it remains to bound the maximum eigenvalue of
Vmaxl
N Vmin H²)
(I - a H + 2a
H
N
N
and we bound this following
Ma et al. (0118)
If we choose ar < 2[ + (N- umm)) then
N
Pmax!
N Vmin
02 H + 20
+
H²) 00
N
N
and the convergence rate is given by the maximum of 1 a, + 2a ( N X N N- X²) maximized over the non-zeru cigenvalues of H. To select the step size at that gives the smallest upper bound, then minimize over ar,, resulting in
min
max Hu
1 1- + 2a²
Pmmxd N
X
N
Pmin x2)
N
0.5 < 2(Pmaox H+ miin M.
Since the objective is quadratic in X, the maximum is achieved at either the largest eigenvalue Amax of H or the smallest non-zero eigenvalue Amin H.
When N <
4dwarl L-Amin 4/mm iec. when N O11/Amin) O(Ki), the optimal objective value is
achieved at Amin and the optimal step size is given by ar [[Pmau/+[N Pmni Aminn The optimal
NAmin convergence rate (i.e. the optimal objective value) is equal to 8 P Viain Amiia) = 1
(Panas K1 +(N -Mmin)) This implies that when N O(K1), the optimal convergence rate has linear speedup in N. When is larger, this step size is no longer optimal, but we still have an upper bound on the convergence rate.
1 (Pmax Ni +NN PPmin]
N
40

---

Under review as a conference paper at ICLR 2021
Now have proved
N
E El| Wl11+11 ww' <
]BI[w. -1
8 (1 + (N vmiin)
+ 0r L
w/ll2 Σ pk|lw, ww.l- 2 + 2
pa H (w -w.ll
200
Σ Pk Fx((()
k=1
k=1
Next we bound terms in the second line using a similar argument as general case. We have
N
N
2a
(w)
wo)l < 20
Pk W. w
and
N
E
Ph
w.
= + 22?aa
W - w11111++ 1F
R=1
km
4a [(W:WWW--11 w". W
and if ae, 0 satisfy
N
u+L+200 1 (1
Mac- 1 L +220 10/3
8 (Umax/F1 + (N Umiin)
2(1 + 21 212a2 33
1g 20 1
we have
W w 1|
N Σ
N
(1 8 (Vmaxx1 + (N
| [ w²11 -a ( w HW,-1 -w") + 2a
pa
H W.
-w-"""
Mmin))
k=1
(ar-1 20
2 Pk Wr-1 w/ 4a 1(W,.llwwW w", H[W,H(WW) -
and again by choosing a:-1 C Miin Aminn)
for small constant c, guarantee that
W w w=1 1p--aa11 Hw - w")
N
+2a, 2 11 Σ P k
(W - w²]l (1----")[1" + 1 w H(w.-1 - w"))
N
S (1 16(Pmax + (N
W - w=112
Uniin )mmin)
For general F, we have the recursive relation
N
N
W+41 w 3 S [E(1 c (Vmax K1 + (N Vunin) (1 C
)| W W
87 (Vmax + (N Vmin))
N
at-r Wi-r w", HW.-, w*) + 20?_-1
Σ
pa H (W-r w²)l
1=1
+TO (w,-1 -w" H(W,-1 -w")
(2aB_ ,p + a) + 1)
pk W 1191
as long as the step sizes are chosen 04-- ities hold
N
Domnn) such that the following inequal-
1202_11 + o)- L.) S (1 (2) o 1.)/3
41

---

Under review as a conference paper at ICLR 2021
2(1 + 21 3 20 at 5
and
W
w w'1l ax- (We-r w" .w:,. ww"
N
+ +222-11
H
W -w)l + 4ra2_1((w,
- w" w'
k=1
N
$ (1 8(T + (2 + (N- Mminn)
which gives
N
W. w01l S (1
''lwoo w1
8E (1maxK) + (N V/min)
N
Oexp( E (Vmax + (N Vmin)) t))l|wo w ||
and with partial participation, the same bound holds with possibly different choice of c.
H.3 GEOMETRIC CONVERGENCE OF FEDMASS FOR OVERPARAMETERIZED LINEAR REGRESSION
Theorem 7. For the overparanterized linear regression problem, FedMaSS with communication
every E iterations and constant step sizes 1/1 = =0 Wumax MNNN -miin) unau)) has geometric convergence:
N
7/2
T7 (1-12
1+
VaIa 7
k)
1+
Vajk
EF(wr) S (Lexpl- E( W
NT
olwo --wwwl) w²1?)
(N Vmin))
Proof. The proof is based on results in Liu & Belkin (020) which originally proposed the MaSS algorithm. Note that the update can equivalently be written
1-1 (1 a² a²vv + +a aut
8 gi.k
u - 1)" gt.
if IE ift IE
1-1
km Pk [ut - 1/
N
a
1
1 1 a i+1
1 a w
1-a* where there is a bijection between the parameters 14a = -** 1yt 1/² 0"-0"""" = n and we "+a
further introduce auxiliary parameter v/. which is initialized at vh. We also note that when 5* = _", the update reduces to the Nesterov accelerated SGD. This version of the FedAvg algorithm with local MaSS updates is used for analyzing the geometric convergence.
As before, define the virtual sequences W. E Pk w V: E P&V U. EN pe and
g, = E and u Itax
1= pr.g We have Eg, E. and W U Th.. V = (1 a - w. 8 ge.
a
Vett + Itat W,+1-
We first prove the theorem with E and being a communication round. We have
Vi+1 w" 1
= ||(1 - a)v, + au, - 3 H (u
- w
-
k
||(1 a.v. + au, - w + +8211 Σ H. - w -
42

---

Under review as a conference paper at ICLR 2021
26 Σ Pk Hu w"), (1 a)v, au, -
[[1 V. at; - w H
+2
Σ
P (ū: w : + 2891 Σ
Ph H (u. - -
k
13
26
Ps. (ū, w²), (1-101100) V.V, + au, w H
28() Σ Ps H (u uz), (1 - a.v, + ou, - w")
Following the proof in Liu & Belkin (2020).
EA < E[ a) V+
w" I| HH11 + aall: ww H w H-1
[[1 a) V
[
w*1
using the convexity of the norm
||l-1 and that j is the smallest non-zero eigenvalue of H.
Now
EB S 25 (Umax
No
1
Mmin
[[(
-w)
N
using the folowing bound:
E
H
H-1
Σ P.F.
E
Σ
p
H
H
Σ
P&P
k
1
Vmax
E
pi H
Σ
Pkp, H 'H'
kfj
V/max
1
E
pr
H H
Σ
pap,
H'H 'H' Σ p H 'H*
kjj
I Vinax
E
pk
H
H
+ H
Vmin Σ p H 'H
N
N
k
Vinax
E.
pk H
H
Umin
Σ H 1 | ph H*)
N
N
Vmax
E
py
H
H
H
N
Vmin
H
N
N
N
Mmmin
Vmax
K
H
N
N
where we have used E Σn Pk H H
H
A by definition of is and the operator convexity of the
mapping W - WH IW.
Finally,
EC E22 Σ
pe (1; w"), (1 a)v, au w
28
Ps H (,: w ). (1 a)v, +au w w")
-25((1 w*), a)v; + all; w')
-28((U; w"), प w a ū w.)
--28 i w 2| + 5(1 w. - w 012
a
w 112
-|(
uull
43

---

Under review as a conference paper at ICLR 2021
1 8 Wt w²1l
1
T w
a
where we have used
(1 a Vv + au;
(1 a) a.u w.)/a+ au,
i1 a We
and the identity that -2(a, b) = |||a
||b|| ||a + b/12.
It follows that
E Ve+1 w" 11
1-a w, w=1
I (1 R)][T - w 2
H 11 +
a
+ _
1
8)| ir - w=11 + +2822Mmax N
1 k +
N min
||| (ū. - w
a
N
+ +2821
Σ H (u: 1
26
( -ue), (1 a)ve au, - w
On the other hand,
E Wr+1
w - Σ ph H - w!
= T w w"ll" 112 - 2nl Tl w= + n7' Σ PaH (T. - -w")1
e l + N Umin
1
S
T - w 1 2n Tt - w 112 + (Ummax
T. w 11
N
N
where we use the following bound:
(Imntt)
E
Σ P
E
H
Σ
HH
3 Vmax
EE
pk H H
H'P
kØj
Vmax
Pa
H
Σ
P&P PAP,H H'H
Σ H*
Aj
A
Vmax N
Pk H
2
N Vinin Σ P HH
3 Mmax IF
Pk
H²_
N Vunin Σ P H*
Σ p& H*)
Vmax N
I.
Pk
H
H
N
Vain 2
N
N
Vmin
3 Vmax
(H
H
N
again using that W W is operator convex and that H = /H* by definition of I.
44

---

Under review as a conference paper at ICLR 2021
Combining the bounds for E B/ We+1 w01l and B
V w"ll
8
We+1 w 112 + VI2++ w
2
1 (1 -a)a) V= w w'1l 1-
o|[ w w=11 (
at --)((u [|
a
+ (20 (2max
1 k + - Vmin
-
270/a + 11² 7725(1 ((
+ L
N Vmin )/a)|T -
- w
N
N
N
N
+ + Σ
Ph. H. [i, n I|
8L
Σ pk - u|
Following
Liu & Belkin 2020) if we choose step sizes so that
Q
5 < 0
p
1 26²(vax R + N
N Vmin
2n0/a + (22
+
N
Vmni
1/a S 0
N
N
N
or equivalently
a/8 μ
1
Vmin
Vmii
200
R
2) 0
N
N
N
N
the second and third terms negative. To optimize the step sizes, note that the two inequalities imply
2 17( [P N
N
Vinin
))a/2( (mmax N
1
N
Mmin
N
N
and maximizing the right hand side with respect to 7, which is quadratic, we see that 17 = 1/(muxx 1 N Mynin maximizes the right hand side, with
2(Mmaxx 2or Ki + N Mmui (U N + N N-Muiu
N N-gmin) 8 al &
Note that
O
N VKiR
when N O(min (R, k1/K]).
V 2(Mmax A x1 + N Yauin (Veas t a+ N Kauin)
Finally, to deal with the terms 26 use Jensen
Σx Ph H (TT, )
+ 8T, Σ * Pe
|| (ū. 12 we can
28 || Σ Pa H. (u, - - - + +5L Σ Pk - (
< (2 + 88) Σ pk Ilu - uf
(28212 + 8L) Σ
Pkl
W.
vi 1 a
w ||
+
1 a
< (282p+ + +L)
228 + 2(
)2n²² Σ
Pk: [ (-1 (u,-1 w|
1+a
1 1
< (2891= + (L))
a
282 2
3
(u,
1
1
45

---

Under review as a conference paper at ICLR 2021
which can be combined with the terms with [|(ū,-1 -[[[-1-w"|]""
2 in the recursive expansion of E
1 VE=
w
E
11 V
H-1
x a)ll
- + 1
8 -W ( - -w"|
+ (282 (Mmax
+ N Pmminy ) 2nd/a a ( 1
Umin )/a) U w'l
N
and the step sizes can be chosen so that the resulting coefficients are negative. Therefore, we have shown that
E W1+1 - w²11 s (1- wi-1 - w
where
O Mmax /RKK Mainn
when N
V 2(vmaax B to N Ruiin (Vmau gCt R+ 8 Rimin))
O(min (Ri, k1/K)))
For general E > 1, choosing 17 c/ E (Vmax 1. + N N-umin) for some small constant e results in and this guarantees that
= =0
EV (Mioax tox N Kyiin (M N. R- N N-mman)
E W. w 1 S (1 - a)) w=11
for all L.
I DETAILS ON EXPERIMENTS AND ADDITIONAL RESULTS
We describe the precise procedure to reproduce the results in this paper. As we mentioned in Section 5] we empirically verified the linear speed up on various convex settings for both FedAvg and its accelerated variants. For all the results, we set random seeds as 0, 1, and report the best convergence rate across the three folds. For each run, initialize Wo and measure the number of iteration to reach the target accuracy e. We use the small-scale dataset w8a Plat (199),, which consists of n 49749 samples with feature dimension d 300. The label is either positive one or negative one. The dataset has sparse binary features in {0, 1}. Each sample has 11.15 non-zero feature values out of 300 features on average. We set the batch size equal to four across all experiments. In the next following subsections, we introduce parameter searching in each objective separately.
1.1 STRONGLY CONVEX ORJECTIVES
We first consider the strongly convex objective function, where we use a regularized binary logistic
regression with regularization À 1/n x 2e 5. We evenly distributed 1,2, 4,8, 16, 32 devices and report the number of iterations/ruunds needed to converge to 6- accuracy. where e = 0.005. The optimal objective function value f* is set as f 0. 0.126433176216544
This determined numerically and we follow the setting in [ttch 2011). The learning rate is decayed as the 1)t = min. 1+t), where we extensively search the best learning rate E {2- lcp. 2 2 Cu, 20g, 2 co) In this case, we search the initial learning rate Yoo E (1,32) and Co = 1/8.
ne
I.2 CONVEX SMOOTH OBJECTIVES
We also binary logistic regression without regularization. The setting is almost same its regularized counter part. We also evenly distributed all the samples on 1, 2, 4, 8, 16, 32 devices. The figure shows the number of iterations needed optiaml objective function value is set as f = 0. 0.113790890575 11099057554449,, determined numerically. The learning rate is decayed the π) min (7)0 ne ). where we extensively search the best Icarning rate
converge
accuracy, where
0.02. The
c E {2-1 cn. 2 2co, co. 2cp, }. In this case, we search the initial learning rate To E {1, 32) and co 1/8.
46

---

Under review as a conference paper at ICLR 2021
1.3 LINEAR REGRESSION
For linear regression, we use the same feature vectors from w8a dataset and generate ground truth [w", b*] from multivariate normal distribution with zero and standard deviation one. Then generate label based on = x(w* +b*. This procedure will ensure we satisfy the over-parameterizeed
setting as required in our theorems. We also evenly distributed all the samples on 1, 4, 8, 16, 32 devices. The figure shows the number of iterations needed to converge to e accuracy, where = 0.02. The optiaml objective function value is f = O. The learning rate is decayed as the 1)t min(1o, 1 where we extensively search the best learning rate с E {2- cn. 2 202 Co2 2cp, 2 In this case, search the initial learning rate Y/o E {0.1, 0.12) and co 1/256..
1.4 PARTIAL PARTICIPATION
To examine the linear speedup of FedAvg in partial participation setting, evenly distributed data on 4, 8, 16, 32, 64, 128 devices and uniformly sample 50% devices without replacement. All other hyperparameters the same previous sections.
1.5 NESTEROV ACCELERATED FEDAVG
The experiments of Nesterov accelerated FedAvg (the update formula is given as follows) uses the same setting as previous three sections for vanilia FedAvg.
yt-1 w. - 0igt,
ytt Br yt) ERESH (y + Be yt))
if 1 $ Iæ i IF
We set Be = 0.1 and search Or the same way as vy in FedAvg.
1.6 THE IMPACT OF E.
In this subsection, we further examine how does the number of local steps (E) affect convergence. As shown Figure Z the number iterations increases as E increase, which slow down the convergence in terms of gradient computation. However, it can communication costs the number of rounds decreased when the E' increases. This showcase that we need a proper choice E to rrae-ooff the communication cost and convergence speed.
47

---

Under review as a conference paper at ICLR 2021
Numbor Monaatema (1)
Number Morationn
Number
10
K+18 K:32
Nammbou of coumms 1112)
K+32
Member of mounde 11:9
1:32
Nember rounds
10
Local
Strongly convex objective
(b) Convex smooth objective
(c) Linear regression
Figure 2: The convergence of FedAvg w.r. the number local steps E.
48


Reviews:
[{"review_id": "s_4dPMwlOS8", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper provided convergence analyses for federated averaging and a momentum-based variant for convex and strongly convex problems, with a focus on the effect of the number of participating devices.\n\nPros: \nThis paper fills a gap in the theory literature. While the convergence of federated averaging is already studied for convex/strongly convex/nonconvex problems in literature, the effect of client sampling is usually not taken into consideration. This paper considered the effect of unbiased client sampling in the convergence analysis.\n\nCons:\n1. The results that a larger number of devices can accelerate training is quite expected and standard in distributed optimization literature. There are no new insights from the paper except for the choice of E implied by Theorem 2. The insight is that E can be O(T^{1/4}/N^{3/4}) when all devices are participating in every iteration, however, E should be O(1) if client sampling is used. This an important insight and it is rather counter-intuitive. This is not discussed in depth in the paper and it is not sure whether it is an artifact of the analysis or such a phenomenon exists in practice. Possible improvements could be discussing how the requirement of E being O(1) arises in the analysis and looking for problem instances where E being O(1) is required. \n\n2. Another concern is this paper seems to be incremental, the analysis for federated averaging with client sampling should not be difficult given the existing theoretical frameworks for strongly convex/convex/nonconvex problems. If the analysis is non-trivial, I encourage the authors to discuss the difficult parts in the main paper.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "JwNeW0iT2uj", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper gives convergence analysis for FedAvg and its accelerated version under data heterogeneity and system heterogeneity. The main improvement comes from a more careful analysis for one-step descent where the authors make use of the term $\\alpha_{t} \\sum_{k=1}^{N} p_{k}\\left[F_{k}\\left(\\mathbf{w}^{*}\\right)-F_{k}\\left(\\overline{\\mathbf{w}}_{t}\\right)\\right]$ that is ignored by previous work Li (2020b). The paper focuses on how FedAvg’s convergence scales with the number of participating devices. It improves previous analysis for FedAvg under more federated settings and shows that FedAvg has linear speedup for any number of participating devices. \n\nPros:\n1. The paper is well written and easy to follow. It is very appreciated that the authors analyze both strongly convex and general convex cases. All proof seems correct (though I didn’t check very carefully). \n2. They summarize existing convergence results for FL algorithms in Table 2 of Appendix B, which helps comparison and I appreciate a lot, though some are missed.\n\nCons and discussions:\nTo extend the results of full device participation to partial device participation, one can use the technique from Li (2020b), which is also pointed out by Haddadpour & Mahdavi (2019). So I will focus on the innovative part.\n1. The descanting lemmas are quite novel. In particular, both Lemma 6 and Lemma 3 are descending lemmas for FedAvg, except that the former is for (general) convex while the latter is for strongly convex. However, based on their bounds, it seems that the result of Lemma 6 is much stronger than Lemma 3 since $\\alpha_{t}\\left(F\\left(\\overline{\\mathbf{w}}_{t}\\right)-F\\left(\\mathbf{w}^{*}\\right)\\right)$ is always non-negative. This is counterintuitive since Lemma 6 requires a much weaker condition (where strong convexity is not required) but has stronger results. I feel that Lemma 3 seems redundant. \n2. There are other papers related to the discussed topic [2-3]. I think it is better to cite them since they give a better understanding of FedAvg for full device participation. The state-of-the-art analysis of Local SGD is given in [2-3]. However, when the case is reduced to full device participation, it is unlikely for Theorem 1-2 to cover them, which implies the analysis is somewhat weak.\n3. The motivation to formulate Nesterov-accelerated FedAvg seems unclear. From theorems and experiments, it seems that the accelerated FedAvg has no advantage over FedAvg even in the full participation setting. This is strange since intuitively the accelerated version should converge much faster and thus have less communication cost. By contrast, FedAC[1] could achieve a faster convergence without the assumption of overparameterization, so it strikes me that the convergence analysis for accelerated FedAvg is quite weak. In original Nesterov full gradient descent, $\\beta_t$ can be set as $\\frac{\\sqrt{L}-\\sqrt{\\mu}}{\\sqrt{L}+\\sqrt{\\mu}}$ (a constant) but here it is set as $O(\\frac{1}{t})$ (which decays, see Lemma 7). Is it the reason for slow convergence?\n4. Since Theorem 3 and 4 have the same error bounds as Theorem 1 and 2, it is better to recite the bounds rather than restate them for a quicker understanding. Besides, the overparameterized convergence result is only mentioned in the ‘contribution’ part, while in the main body, it is just a passing. I think the author should talk more about FedMaSS and less about Nesterov-accelerated FedAvg considering the latter algorithm is poorly guaranteed.\n\n[1] Yuan, Honglin, and Tengyu Ma. \"Federated Accelerated Stochastic Gradient Descent.\" arXiv preprint arXiv:2006.08950 (2020).\n[2] Woodworth, Blake, et al. \"Is Local SGD Better than Minibatch SGD?.\" arXiv preprint arXiv:2002.07839 (2020).\n[3] Woodworth, Blake, Kumar Kshitij Patel, and Nathan Srebro. \"Minibatch vs Local SGD for Heterogeneous Distributed Learning.\" arXiv preprint arXiv:2006.04735 (2020).", "extra_scores": {}, "extra_text": {}}, {"review_id": "J008y9XY-YF", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\nThis work studies federated learning (FL) and analyzes FedAvg, the most widely used FL algorithm. The contribution is mainly theoretical. This paper contributes better convergers rates than prior work, arguably. \n\n\n##########################################################################\n\nReasons for score:\n\nThis is a borderline paper. I am fine with either acceptance and rejection. While the new theories are somehow interesting, my main concern is that the convergence rates are not better than the standard SGD. I elaborate on this point in below.\n\n\n\n##########################################################################\n\nPros:\n\nThis paper has theoretical contributions. This paper contributes new theories for FedAvg, which is a very popular algorithm, under various settings.\n\n\n##########################################################################\n\nCons:\n\nThe point of FedAvg is that setting $E$ (number of local updates) greater than one makes the convergence faster. This is why FedAvg is more useful than distributed SGD. However, the bounds in this paper are not very reasonable: as $E$ increases, the convergence gets slower. If it is the case, then why not using distributed SGD? I am not sure if I missed anything. Please address my concern.\n\n\n\n##########################################################################\n\nAfter reading the authors' feedback, I decided to increase my rating from 5 to 6. The authors convinced me that setting $E>1$ can reduce the number of communications. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-MaxB00vFvg", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows a linear speedup in FedAvg w.r.t. number of devices, mainly theoretically, while most prior works ignore it. The main convergence results are given for three cases: a) Strongly Convex+Smooth, b) Convex+Smoth, and c) Strongly/x convex+Smooth+0 training loss can be achieved. The paper is well-written and motivated with good discussions of the algorithm and the related works. \n\nEven though, I still have doubts about this paper:\n1).  In the over-parameterized case, this paper shows a linear convergence rate $O(exp(-NT/E\\kappa))$. Could you explain how large $\\kappa$ would be when width goes infinity (polynomially or exponentially)? Or $\\kappa$ is bounded by a universal constant? While I go through Appendix G, I find the proof in the over-parameterized case relies on Strongly Convex+ Smooth and further Assumption that 0 loss can be achieved. However, I don't reckon this is the over-parameterization case, as the over-parameterized functions are, as far as I know, always Non-convex. In my opinion, there is no necessity to connect FedAvg with Over-Parameterization in such a way. \n\nOverall, I think this paper is qualified for acceptance except for the part of the over-parameterized case. I rate my score 5 at first, but consider raising it if the authors dispel my doubts. I'm looking forward to the discussion.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work provides theoretical analysis for FedAvg, contributing better convergence rates than prior work. Moreover, the paper shows that setting E > 1 can reduce the number of communications.  The contribution is incremental. 
Decision: Reject