Federated learning (FL) is a machine learning setting where many clients (e.g., mobile devices or organizations) collaboratively train a model under the orchestration of a central server (e.g., service provider), while keeping the training data decentralized [1, 2] . In recent years, FL has swiftly emerged as an important learning paradigm [3, 4] -one that enjoys widespread success in applications such as personalized recommendation [5] , virtual assistant [6] , and keyboard prediction [7] , to name a Table 1 : Our convergence results for FedAvg and accelerated FedAvg in this paper. Throughout the paper, N is the total number of local devices, and K ≤ N is the maximal number of devices that are accessible to the central server. T is the total number of stochastic updates performed by each local device, E is the local steps between two consecutive server communications (and hence T /E is the number of communications). † In the linear regression setting, we have κ = κ 1 for FedAvg and κ = √ κ 1κ for accelerated FedAvg, where κ 1 and √ κ 1κ are condition numbers defined in Section 5. Since κ 1 ≥κ, this implies a speedup factor of κ1 κ for accelerated FedAvg.
few-for at least two 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 exponential growth of computational power (blessed by Moore's law) in mobile devices have made it increasingly attractive to push the computation to the edge.
Despite its promise and broad applicability in our current era, the potential value FL delivers is coupled with the unique challenges it brings forth. In particular, when FL learns a single statistical model using data from across all the devices while keeping each individual device's data isolated (and hence protects privacy) [2] , it faces two challenges that are absent in centralized optimization and distributed (stochastic) optimization [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 ]:
1) Data heterogeneity: data distributions in devices are different (and data can't be shared);
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.
To address these challenges, Federated Averaging (FedAvg) [3] was proposed as a particularly effective heuristic, which has enjoyed great empirical success [7] . This success has since motivated a growing line of research efforts into understanding its theoretical convergence guarantees in various settings. For instance, [20] 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. Very recently, [21] furthered the progress and established an O( 1 T ) convergence rate for FedAvg for strongly convex smooth problems. At the same time, [22] studied the Nesterov accelerated FedAvg for non-convex smooth problems and established an O( 1 √ T ) convergence rate to stationary points. However, despite these very recent fruitful pioneering efforts into understanding the theoretical convergence properties of FedAvg, it remains open as to how the number of devices-particularly the number of devices that participate in the computation-affects the convergence speed. In particular, do we get linear speedup of FedAvg? What about when FedAvg is accelerated? These aspects are currently unexplored in FL. We fill in the gaps here by providing affirmative answers. 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).
Third, we study a subclass of strongly convex smooth problems where the objective is overparameterized and establish a faster O(exp(− KT κ )) convergence rate for FedAvg. 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-MaSS accelerated FedAvg-and establish a faster convergence rate (compared to if no acceleration is used). This stands in contrast to generic (strongly) convex stochastic problems where theoretically no rate improvement is obtained when one accelerates FedAvg. The detailed convergence results are summarized in Table 1 .
In this paper, we study the following federated learning problem:
where N is the number of local devices (users/nodes/workers) and p k is the k-th device's weight satisfying p k ≥ 0 and N k=1 p k = 1. In the k-th local device, there are n k data points: x 1 k , x 2 k , . . . , x n k k . The local objective F k (·) is defined as: F k (w) w; x j k , where denotes a userspecified loss function. Each device only has access to its local data, which gives rise to its own local objective F k . Note that we do not make any assumptions on the data distributions of each local device. The local minimum F * k = min w∈R d F k (w) can be far from the global minimum of Eq (1).
We first introduce the standard Federated Averaging (FedAvg) algorithm [3] . 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 a 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 t is described as follows:
where w k t is the local model parameter maintained in the k-th device at the t-th iteration, g t,k := ∇F k (w k t , ξ k t ) is the stochastic gradient based on ξ k t , the data sampled from k-th device's local data uniformly at random. I E = {E, 2E, . . . } is the set of global communication steps. We use S t+1 to represent the set of active devices at t + 1.
Since federated learning usually involves an enormous amount of local devices, it is often more realistic to assume only a 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 averaging over all devices at the communication round, i.e., w k t+1 = N k=1 p k v k t+1 , and the case of partial participation where |S t+1 | < N . With partial participation, S t+1 is obtained by two types of sampling schemes to simulate practical scenarios [21] . For example, one scheme establishes S t+1 by i.i.d. sampling the devices with probability p k with replacement. Both schemes guarantee that gradient updates in FedAvg are unbiased stochastic versions of updates in FedAvg with full participation. For more details on the notations and setup, please refer to Section A in the appendix.
We make the following standard assumptions on the objective function F 1 , . . . , F N . Assumptions 1 and 2 are commonly satisfied by a range of popular objective functions, such as 2 -regularized logistic regression and cross-entropy loss functions. Assumption 1 (L-smooth). F 1 , · · · , F N are all L-smooth: for all v and w,
Assumption 2 (Strongly-convex). F 1 , · · · , F N are all µ -strongly convex: for all v and w,
Assumption 3 (Bounded local variance). Let ξ k t be sampled from the k-th device's local data uniformly at random. The variance of stochastic gradients in each device is bounded:
k , for k = 1, · · · , N and any w k t . Let σ 2 = N k=1 p k σ 2 k . Assumption 4 (Bounded local gradient). The expected squared norm of stochastic gradients is uniformly bounded. i.e., E ∇F k w k t , ξ k t 2 ≤ G 2 , for all k = 1, ..., N and t = 0, . . . , T − 1.
Assumptions 3 and 4 have been made in many previous works in federated learning, e.g. [16, 21, 9] . We provide further justification for their generality. As model average parameters become closer to w * , the L-smoothness property implies that
Therefore, there is no substantial difference between these assumptions and assuming the bounds at w * only. Furthermore, compared to assuming bounded gradient diversity as in related work [20, 4] , Assumption 4 is much less restrictive. When the optimality gap converges to zero, bounded gradient diversity restricts local objectives to have the same minimizer as the global objective, contradicting the heterogeneous data setting. For detailed discussions of our assumptions, please refer to Appendix Section B.
In this section, we provide convergence analyses of FedAvg for convex objectives in the general setting with both heterogeneous data and partial participation. We show that for strongly convex and smooth objectives, the convergence of the optimality gap of averaged parameters across devices is O(1/N T ), while for convex and smooth objectives, the rate is O(1/ √ N T ). Detailed proofs are deferred to Appendix Section C.
We first show that FedAvg has an O(1/N T ) convergence rate for µ-strongly convex and L-smooth objectives. The result improves on the O(1/T ) rate of [21] with a linear speedup in the number of devices N . Moreover, it implies a 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( T /N ) 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/N T ) convergence.
T , ν max = max k N p k , and set decaying learning rates α t = 1 4µ(γ+t) with γ = max{32κ, E} and κ = L µ . Then under Assumptions 1 to 4 with full device participation,
and with partial device participation with at most K sampled devices at each communication round,
Linear speedup. We first compare our bound with that in [21] , which is
is also O(1/T ) without a dependence on N , for any choice of E their bound cannot achieve linear speedup. The improvement of our bound comes from the term κ 2 E 2 G 2 /µ T 2 , which now is O(E 2 /T 2 ). As a 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 a 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 which depends on E. Communication Complexity. Our bound implies a distinction in the choice of E between the full and partial participation settings. With full participation there is linear speedup O(1/N T ) as long as T to preserve O(1/T ) rate, even for full participation. On the other hand, with partial participation, κE 2 G 2 /µ KT is also a leading term, and so E must be O (1) . In this case, our bound still yields a linear speedup in K, which is also confirmed by experiments. The requirement E = O(1) in partial participation likely cannot be removed for our sampling schemes, as the sampling variance is Ω(E 2 /T 2 ) and the dependence on E is tight. Comparison with related work. To better understand the significance of the obtained bound, we compare our rates to the best-known results in related settings.
[20] proves a linear speedup O(1/N T ) result for strongly convex and smooth objectives, with O(N 1/3 T 2/3 ) communication complexity with i.i.d. 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), effectively removing system heterogeneity. The bound in [19] matches our bound in the full participation case, but their framework excludes partial participation [19, Proposition 1].
Next we provide linear speedup analyses of FedAvg with convex and smooth objectives and show that the optimality gap is O(1/ √ N T ). This result complements the strongly convex case in the previous part, as well as the non-convex smooth setting in [15, 16, 20 
with full participation, and with partial device participation with K sampled devices at each communication round and learning rate
Choice of E and linear speedup. With full participation, as long as
In the partial participation setting, E must be O(1) in order to achieve linear speedup of O(1/ √ KT ). Our result again demonstrates the difference in communication 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.
A natural extension of the FedAvg algorithm is to use momentum-based local updates instead of local SGD updates. To our knowledge, the only convergence analyses of FedAvg with momentum-based stochastic updates focus on the non-convex smooth case [22, 17, 4] . In this section, we complete the picture with O(1/N T ) and O(1/ √ N T ) convergence results for Nesterov-accelerated FedAvg for convex objectives that match the rates from the previous section. As we know from stochastic optimization, Nesterov and other momentum updates may fail to accelerate over SGD [23, 24, 25, 26] . Therefore in Section 5 we will specialize to overparameterized problems where we demonstrate that a particular FedAvg variant with momentum updates is able to accelerate over the original FedAvg algorithm. Detailed proofs of convergence results in this section are deferred to Appendix Section D.
The Nesterov Accelerated FedAvg algorithm follows the updates:
where g t,k := ∇F k (w k t , ξ k t ) is the stochastic gradient sampled on the k-th device at time t. 
and with partial device participation with K sampled devices at each communication round, 
We now show that the optimality gap of Nesterov Accelerated FedAvg has O(1/ √ N T ) rate. This result complements the strongly convex case in the previous part, as well as the non-convex smooth setting in [22, 17, 4] , where a similar O(1/ √ N T ) rate is given in terms of averaged gradient norm. 
and with partial device participation with K sampled devices at each communication round,
It is possible to extend the results in this section to accelerated FedAvg algorithms with other momentum-based updates. However, in the stochastic optimization setting, none of these methods can achieve a better rate than the original FedAvg with SGD updates for general problems [24] . For this reason, we will instead turn to the overparameterized setting [27, 23, 28] in the next section where we show that FedAvg enjoys geometric convergence and it is possible to improve its convergence rate with momentum-based updates.
Overparameterization is a 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 [29, 30] . Due to the property of automatic variance reduction in overparameterization, a line of recent works proved that SGD and accelerated methods achieve geometric convergence [27, 31, 32, 33, 34]. A natural question is whether such a 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 in the special case of linear regression. Inspired by recent advances in accelerating SGD [35, 36] , we further propose a novel momentumbased FedAvg algorithm, which enjoys an improved convergence rate over FedAvg. Detailed proofs are deferred to Appendix Section E. In particular, we do not need Assumptions 3 and 4 and use modified versions of Assumptions 1 and 2 detailed in this section.
Recall the FL problem min w N k=1 p k F k (w) with F k (w) = 1 n k n k j=1 (w; x j k ). In this section, we consider the standard Empirical Risk Minimization (ERM) setting where is non-negative, l-smooth, and convex, and as before, each F k (w) is L-smooth and µ-strongly convex. Note that l ≥ L. This setup includes many important problems in practice. In the overparameterized setting, there exists w * ∈ arg min w N k=1 p k F k (w) such that (w * ; x j k ) = 0 for all x j k . We first show that FedAvg achieves geometric convergence with linear speedup in the number of workers. Theorem 5. In the overparameterized setting, FedAvg with communication every E iterations and constant step size α = O( 1 E N lνmax+L(N −νmin) ) has geometric convergence: . When N is above this threshold, however, the speedup is almost constant in the number of workers. This matches the findings in [27] . Our result also illustrates that E can be taken O(T β ) for any β < 1 to achieve geometric convergence, achieving better communication efficiency than the standard FL setting.
We now turn to quadratic problems and show that the bound in Theorem 5 can be improved to O(exp(− N Eκ1 t)) for a larger range of N . We then propose a variant of FedAvg that has provable acceleration over FedAvg with SGD updates. The local device objectives are now given by the sum
and there exists w * such that F (w * ) ≡ 0. Two notions of condition number are important in our results: κ 1 which is based on local Hessians, andκ, which is termed the statistical condition number [23, 36] . For their detailed definitions, please refer to Appendix Section E. Here we use the factκ ≤ κ 1 . Recall ν max = max k p k N and ν min = min k p k N . 
, which exhibits linear speedup in the number of workers, as well as a 1/κ 1 dependence on the condition number κ 1 . Inspired by [23], we propose the MaSS accelerated FedAvg algorithm (FedMaSS):
. When η k 2 ≡ 0, this algorithm reduces to the Nesterov accelerated FedAvg algorithm. In the next theorem, we demonstrate that FedMaSS improves the convergence to O(exp(− N T E √ κ1κ )). To our knowledge, this is the first acceleration result of FedAvg with momentum updates over SGD updates. 
has geometric convergence: 
). Since κ 1 ≥κ, this implies a speedup factor of κ1 κ for FedMaSS. On the other hand, the same linear speedup in the number of workers holds for N in a smaller range of values.
In this section, we empirically examine the linear speedup convergence of FedAvg and Nesterov accelerated FedAvg in various settings, including strongly convex function, convex smooth function, and overparameterized objectives, as analyzed in previous sections.
Setup. Following the experimental setting in [9] , we conduct experiments on both synthetic datasets and real-world dataset w8a [37] (d = 300, n = 49749). We consider the distributed objectives F (w) = N k=1 p k F k (w), and the objective function on the k-th local device includes three cases: 1) Strongly convex objective: the regularized binary logistic regression problem,
The regularization parameter is set to λ = 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,
Linear speedup of FedAvg and Nesterov accelerated FedAvg. To verify the linear speedup convergence as shown in Theorems 1 2 3 4, we evaluate the number of iterations needed to reach -accuracy in three objectives. We initialize all runs with w 0 = 0 d and measure the number of iterations to reach the target accuracy . For each configuration (E, K), we extensively search the learning rate from min(η 0 , nc 1+t ), where η 0 ∈ {0.1, 0.12, 1, 32} according to different problems and c can take the values c = 2 i ∀i ∈ 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 on the impact of E, detailed experimental setup, and hyperparameter setting, please refer to the Appendix Section F.
With the growing availability of mobile devices and their increasing ability to capture data, enormous amounts of information can potentially be integrated to help improve and transform people's lives in many aspects such as personalized and enhanced services [38, 7] and precision medicine [39, 40] , to name a few.
Meanwhile, data breaches from central servers of big companies have become increasingly common, raising concerns about privacy and information security when individual clients' information is aggregated and stored centrally.
The challenge we face is therefore to properly integrate and leverage data from different sources to arrive at better solutions, while at the same time minimizing privacy risks. This trade-off between efficiency and privacy/security lies at the heart of many applications, including but not limited to recommendation systems [5] , virtual assistants [6] , and mobile keyboard prediction [7] . Federated learning has emerged as a promising solution to the challenge. Built on insights from decentralized and distributed optimization, it aggregates information by integrating model parameters learned locally at each source, eliminating the need to transmit and store data centrally.
This desirable feature makes federated learning an effective tool to balance efficiency and privacy not just in the aforementioned applications with mobile devices, but also in other settings such as healthcare where it has the potential to save millions of lives. Under the unprecedented outbreak of Covid'19, coronavirus patients have filled emergency rooms nationwide. It is imperative to have reliable, robust machine learning solutions that could help doctors diagnose and treat patients. However, Health Insurance Portability and Accountability (HIPAA) regulations [41] impose strict restrictions on sharing patients' clinical data: privacy is a top priority when developing solutions by leveraging information from different medical institutions. Therefore, propelling the frontiers of federated learning to develop more efficient algorithms under the privacy-preserving constraint has never been more important.
Two important aspects where federated learning departs from traditional distributed optimization is the heterogeneity of data at different sources and the fact that not all local devices/sources are able to participate in the model averaging at every iteration. In this general setting, the question remains as to whether joint learning still enjoys the desirable feature of linear speedup with respect to the number of participating devices/institutions.
In this work, we establish solid theoretical foundations for federated learning and demonstrate that linear speedup is possible in a variety of settings with the FedAvg algorithm and its variants, under both data and system heterogeneity, significantly improving previous understanding of federated learning.
We therefore show that federated learning is able to achieve efficiency and privacy at the same time.
On one hand, data is isolated in each local device/institution, preventing the potential leakage of private information. On the other hand, joint learning can speed up substantially if the number of participating devices/institutions increases. In conclusion, our work shows a promising machine learning pathway to simultaneously securing people's privacy and improving their lives.
[19] 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 arXiv:2003.10422, 2020.
[20] Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint arXiv:1910.14425, 2019.
[21] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. ICLR, 2020.
[22] Zhouyuan Huo, Qian Yang, Bin Gu, Lawrence Carin Huang, et al. Faster on-device training using new federated momentum algorithm. arXiv preprint arXiv:2002.02090, 2020.
[23] Chaoyue Liu and Mikhail Belkin. Accelerating sgd with momentum for over-parameterized learning. ICLR, 2020.
[24] 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), pages 1-9. IEEE, 2018.
[25] Tianyi Liu, Zhehui Chen, Enlu Zhou, and Tuo Zhao. Toward deeper understanding of nonconvex stochastic optimization with momentum using diffusion approximations. arXiv preprint arXiv:1802.05155, 2018. [27] Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning. ICML, 2018.
[28] Alfredo Canziani, Adam Paszke, and Eugenio Culurciello. An analysis of deep neural network models for practical applications. arXiv preprint arXiv:1605.07678, 2016.
[29] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization. arXiv preprint arXiv:1811.03962, 2018.
[30] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016.
[31] Eric Moulines and Francis R Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, pages 451-459, 2011.
[32] Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In Advances in neural information processing systems, pages 1017-1025, 2014.
[33] Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint arXiv:1308.6370, 2013.
[34] Thomas Strohmer and Roman Vershynin. A randomized kaczmarz algorithm with exponential convergence. Journal of Fourier Analysis and Applications, 15 (2) [37] J Platt. Fast training of support vector machines using sequential minimal optimization, in, b. scholkopf, c. burges, a. smola,(eds.): Advances in kernel methods-support vector learning, 1998.
[38] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta-learning approach. arXiv preprint arXiv:2002.07948, 2020.
In this section, we introduce additional notations that are used throughout the proof. Following common practice [9, 21] , we define two virtual sequences v t and w t . For full device participation and
where g t = N k=1 p k g t,k is one-step stochastic gradient, averaged over all devices.
Similarly, we denote the expected one-step gradient
and ξ t = {ξ k t } N k=1 denotes random samples at all devices at time step t. 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 arts [20] considering two types of sampling schemes. The sampling scheme I establishes S t+1 by i.i.d. sampling the devices with replacement, in this case the upper bound of expected square norm of w t+1 − v t+1 is given by [21, Lemma 5] :
The sampling scheme II establishes S t+1 by uniformly sampling all devices without replacement, in which we have the
We denote this upper bound as follows for concise presentation.
In this section, we compare our convergence rate with the best-known results in the literature (see Table 2 ). In [20], the authors provide O(1/N T ) convergence rate of non-convex problems under Polyak-Łojasiewicz (PL) condition, which means their results can directly apply to the strongly convex problems. However, their assumption is based on bounded gradient diversity, defined as follows:
This is a more restrictive assumption comparing to assuming bounded gradient under the case of target accuracy → 0 and PL condition. To see this, consider the gradient diversity at the global optimal w * , i.e.,
. For Λ(w * ) to be bounded, it requires ∇F k (w * ) 2 2 = 0, ∀ k. 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 -accuracy under general heterogeneous data while our convergence results still hold in this case.
To facilitate reading, theorems from the main paper are restated and numbered identically. We first summarize some properties of L-smooth and µ-strongly convex functions [42] .
Convergence rate E NonIID Participation Extra Assumptions Setting , the convergence rate is for non-convex smooth problems with PL condition, which also applies to strongly convex problems. Therefore, we compare it with our strongly convex results here. ‡ ‡ The bounded gradient diversity assumption is not applicable for general heterogeneous data when converging to arbitrarily small -accuracy (see discussions in Sec B).
Lemma 8. Let F be a convex L-smooth function. Then we have the following inequalities:
and set decaying learning rates α t = 1 4µ(γ+t) with γ = max{32κ, E} and κ = L µ . Then under Assumptions 1,2,3,4 with full device participation,
and with partial device participation with at most K sampled devices at each communication round,
Proof. The proof builds on ideas from [21]. The first step is to observe that the L-smoothness of F provides the upper bound
Our main step is to prove the bound
We have
By definition of g t and g t (see Eq (3)), we have EA 2 = 0. For A 3 , we have the follow upper bound:
again by Jensen's inequality and using the independence of g t,k , g t,k [21, Lemma 2].
Next we bound A 1 :
and we will show that the third term α t g t 2 can be canceled by an upper bound of the second term.
For the second term, which is negative, we can ignore it, but this yields a suboptimal bound that fails to provide the desired linear speedup. Instead, we upper bound it using the following derivation:
where we have used the smoothness of F twice.
Note that the term −α 2 t g t 2 exactly cancels the α 2 t g t 2 in the bound for A 1 , so that plugging in the bound for −2α t w t − w * , g t , we have so far proved
The term E g t 2 ≤ G 2 by assumption.
. Since communication is done every E steps, for any t ≥ 0, we can find a t 0 ≤ t such that t − t 0 ≤ E − 1 and w k t0 = w t0 for all k. Moreover, using α t is non-increasing and α t0 ≤ 2α t for any
Using the bound on E N k=1 p k w t − w k t 2 , we can conclude that, with ν max := N · max k p k and ν min := N · min k p k ,
where in the last inequality we use σ 2 = max k σ 2 k , and assume α t satisfies Lα t ≤ 1 8 . We show next that
.
and so it remains to choose α t and b such that
where γ = max{E, 32κ}, then we may check that α t satisfies both requirements.
where we have used the facts that
t+1 C) for our choice of α t and b. Now to ensure
we can simply scale b by c w 0 − w * 2 for a constant c large enough and the induction step still holds.
It follows that
for all t ≥ 0.
Finally, the L-smoothness of F implies
With partial participation, the update at each communication round is now given by averages over a subset of sampled devices. When t + 1 / ∈ I E , v t+1 = w t+1 , while when t + 1 / ∈ I E , we have Ew t+1 = v t+1 by design of the sampling schemes, so that
The key is to bound E w t+1 − v t+1 2 . For sampling scheme I we have
The same argument as the full participation case implies
One may ask whether the dependence on E in the term κE 2 G 2 /µ KT can be removed, or equivalently whether k p k w k t − w t 2 = O(1/T 2 ) can be independent of E. We provide a simple counterexample that shows that this is not possible in general. Lemma 10. There exists a dataset such that if E = O(T β ) for any β > 0 then k p k w k t −w t 2 = Ω( 1 T 2−2β ) .
Proof. Suppose that we have an even number of devices and each F k (w) = 1 n k n k j=1 (x j k − w) 2 contains data points x j k = w * ,k , with n k ≡ n. Moreover, the w * ,k 's come in pairs around the origin. As a result, the global objective F is minimized at w * = 0. Moreover, if we start from w 0 = 0, then by design of the dataset the updates in local steps exactly cancel each other at each iteration, resulting in w t = 0 for all t. On the other hand, if E = T β , then starting from any t = O(T ) with constant step size O( 1 T ), after E iterations of local steps, the local parameters are updated towards w * ,k with w k
which is at a slower rate than 1 T 2 for any β > 0. Thus the sampling variance
2 ) decays at a slower rate than 1 T 2 , resulting in a convergence rate slower than O( 1 T ) with partial participation.
Theorem 2. Under assumptions 1,3,4 and constant learning rate
with full participation, and with partial device participation with K sampled devices at each communication round and learning rate α t = O( K T ),
Proof. We again start by bounding the term
By definition of g t and g t (see Eq (3)), we have EA 2 = 0. For A 3 , we have the follow upper bound:
again by Jensen's inequality and using the independence of g t,k , g t,k [21, Lemma 2].
Next we bound A 1 :
Using the convexity and L-smoothness of F k ,
which results in
The difference of this bound with that in the strongly convex case is that we no longer have a contraction factor in front of w t − w * 2 . In the strongly convex case, we were able to cancel
and obtain only lower order terms. In the convex case, we use a different strategy and preserve
in order to obtain a telescoping sum.
We have
Since F (w * ) ≤ F (w t ), as long as 4α t L ≤ 1, we can ignore the last term, and rearrange the inequality to obtain
The same argument as before yields
Summing the inequalities from t = 0 to t = T , we obtain
By setting the constant learning rate α t ≡ N T , we have
Similarly, for partial participation, we have 
and with partial device participation with K sampled devices at each communication round,
Proof. Define the virtual sequences v t = N k=1 p k v k t , w t = N k=1 p k w k t , and g t = N k=1 p k Eg t,k . We have Eg t = g t and v t+1 = w t − α t g t , and w t+1 = v t+1 for all t. The proof again uses the L-smoothness of F to bound
Our main step is to prove the bound
By definition of g t and g t (see Eq (3)), we have EA 2 = 0. For A 3 , we have the follow upper bound:
again by Jensen's inequality and using the independence of g t,k , g t,k [21, Lemma 2].
Next we bound A 1 :
Same as the SGD case,
Different from the SGD case, we have
and we will using this recursive relation to obtain the desired bound.
Since communication is done every E steps, for any t ≥ 0, we can find a t 0 ≤ t such that t − t 0 ≤ E − 1 and w k t0 = w t0 for all k. Moreover, using α t is non-increasing, α t0 ≤ 2α t , and β t ≤ α t for any
To see this identity for appropriate α t , β t , note the recursion
as long as α t , β t−1 satisfy 2β 2 t−1 + 2α 2 t ≤ 1/2, we can guarantee that E v k t − v k t−1 2 ≤ G 2 for all k by induction. This together with Jensen's inequality also gives E v t − v t−1 2 ≤ G 2 for all t.
Using the bound on E N k=1 p k w t − w k t 2 , we can conclude that, with ν max := N · max k p k ,
Assume that we have shown
for all iterations until t, where C = 20E 2 LG 2 , D = 1 N ν 2 max σ 2 , and b is to be chosen later. For step sizes we choose α t = 6 µ 1 t+γ and β t−1 =
Recall that we also require α t0 ≤ 2α t for any t − t 0 ≤ E − 1, Lα t ≤ 1 5 , and 2β 2 t−1 + 2α 2 t ≤ 1/2, which we can also check to hold by definition of α t and β t .
Moreover, E y t − w * 2 ≤ b(Cα 2 t + Dα t ) with the chosen step sizes also implies v t−1 − w * ≤ 2 v t − w * . Therefore the bound for E v t+1 − w * 2 can be further simplified with
and so it remains to choose b such that
With partial participation, the same argument in the SGD case yields 
and with partial device participation with K sampled devices at each communication round,
for t ≥ 1 and 0 for t = 0. We can check that
Now we define z t := w t + p t and η t = αt 1−βt for all t, so that we have the recursive relation
Using the convexity and L-smoothness of F k ,
As before, g t 2 ≤ 2L 2 k p k w k t − w t 2 + 4L(F (w t ) − F (w * )), so that
Summing the inequalities from t = 0 to t = T , we obtain
By setting the constant learning rates α t ≡ N T and β t ≡ c N T so that η t = αt
Similarly, for partial participation, we have 
Proof. To illustrate the main ideas of the proof, we first present the proof for E = 2. Let t − 1 be a communication round, so that w k t−1 = w t−1 . We show that
for appropriately chosen constant step sizes α t , α t−1 . We have
and the cross term can be bounded as usual using µ-convexity and L-smoothness of F k :
Applying this recursive relation to w t − w * 2 and using w t−1 − w k t−1
Now instead of bounding N k=1 p k w t − w k t 2 using the arguments in the general convex case, we follow [27] and use the fact that in the overparameterized setting, w * is a minimizer of each (w, x j k ) and that each is l-smooth to obtain ∇F k (w t−1 ,
2 again using w t−1 = w k t−1 . Taking expectation with respect to ξ k t−1 's and using the fact that F (w * ) = 0, we have
Note also that
Substituting these into the bound for w t+1 − w * 2 , we have
from which we can conclude that
and so following [27] if we let α t = min{ qN 2lνmax ,
results in the fastest convergence, and this translates to α t = 1 2 N lνmax+L(N −νmin) . Next we claim that
Note that by scaling α t−1 by a constant c ≤ 1 if necessary, we can guarantee lαt−1(2l 2 α 2 t +αtL) 1−αtµ ≤ 1 2 , and so the condition is equivalent to
which was shown to hold with α t−1 ≤ 1 2 N lνmax+L(N −νmin) . For the proof of general E ≥ 2, we use the following two identities:
where the first inequality has been established before. To establish the second inequality, note that
so that using the l-smoothness of ,
Using the first inequality, we have
and we choose α t and α t−1 such that
and if α t−1 is chosen such that
Applying the above derivation iteratively τ < E times, we have
as long as the step sizes α t−τ are chosen such that the following inequalities hold
We can check that setting α t−τ = c 1 τ +1
N lνmax+L(N −νmin) for some small constant c satisfies the requirements.
Since communication is done every E iterations, w t0 = w k t0 for some t 0 > t − E , from which we can conclude that
and applying this inequality to iterations between each communication round,
With partial participation, we note that
and so the recursive identity becomes
N lνmax+L(N −νmin) for a possibly different constant from before satisfies the requirements.
Finally, using the L-smoothness of F ,
We first provide details on quantities used in the proof of results on linear regression in Section 5 in the main text. The local device objectives are now given by the sum of squares F k (w) = Let H = k p k H k . In general H has zero eigenvalues. However, because the null space of H and range of H are orthogonal, in our subsequence analysis it suffices to project w t − w * onto the range of H, thus we may restrict to the non-zero eigenvalue of H.
A useful observation is that we can use w * T x j k − z j k ≡ 0 to rewrite the local objectives as F k (w) = 
Proof. We again show the result first when E = 2 and t − 1 is a communication round. We have
and
following [27] we first prove that
with appropriately chosen α t . Compared to the rate O( µN lνmax+L(N −νmin) ) = O( N νmaxκ1+(N −νmin)κ ) for general strongly convex and smooth objectives, this is an improvement as linear speedup is now available for a larger range of N .
We have
and it remains to bound the maximum eigenvalue of
and we bound this following [27] . If we choose α t < N 2(νmaxl+(N −νmin)L) , then
and the convergence rate is given by the maximum of 1−α t λ+2α 2 t ( νmaxl N λ+ N −νmin N λ 2 ) maximized over the non-zero eigenvalues λ of H. To select the step size α t that gives the smallest upper bound, we then minimize over α t , resulting in 
Since the objective is quadratic in λ, the maximum is achieved at either the largest eigenvalue λ max of H or the smallest non-zero eigenvalue λ min of H.
When N ≤ 4νmaxl L−λmin + 4ν min , i.e. when N = O(l/λ min ) = O(κ 1 ), the optimal objective value is achieved at λ min and the optimal step size is given by α t = N 4(νmaxl+(N −νmin)λmin) . The optimal convergence rate (i.e. the optimal objective value) is equal to 1 − N −νmin) ) . This implies that when N = O(κ 1 ), the optimal convergence rate has a linear speedup in N . When N is larger, this step size is no longer optimal, but we still have 1 − 1 8 N (νmaxκ1+(N −νmin)) as an upper bound on the convergence rate. Now we have proved
Next we bound terms in the second line using a similar argument as the general case. We have
and again by choosing α t−1 = c N 8(νmaxl+(N −νmin)λmin) for a small constant c, we can guarantee that
For general E, we have the recursive relation
as long as the step sizes are chosen α t−τ = c N 4τ (νmaxl+(N −νmin)λmin) such that the following inequalities hold
t)) w 0 − w * 2 and with partial participation, the same bound holds with a possibly different choice of c. 
has geometric convergence:
where we have used
Following [23] if we choose step sizes so that α µ − δ ≤ 0
the second and third terms are negative. To optimize the step sizes, note that the two inequalities imply
and maximizing the right hand side with respect to η, which is quadratic, we see that η ≡ 1/(ν max 
and the step sizes can be chosen so that the resulting coefficients are negative. Therefore, we have shown that
where α = ) and this guarantees that
for all t.
We described the precise procedure to reproduce the results in this paper. As we mentioned in Section 6, 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, 2 and report the best convergence rate across the three folds. For each run, we initialize w 0 = 0 and measure the number of iteration to reach the target accuracy . We use the small-scale dataset w8a [37], 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.
We first consider the strongly convex objective function, where we use a regularized binary logistic regression with regularization λ = 1/n ≈ 2e − 5. We evenly distributed on 1, 2, 4, 8, 16, 32 devices and report the number of iterations/rounds needed to converge to −accuracy, where = 0.005. The optimal objective function value f * is set as f * = 0.126433176216545. This is determined numerically and we follow the setting in [9] . The learning rate is decayed as the η t = min(η 0 , nc 1+t ), where we extensively search the best learning rate c ∈ {2 −1 c 0 , 2 −2 c 0 , c 0 , 2c 0 , 2 2 c 0 }. In this case, we search the initial learning rate η 0 ∈ {1, 32} and c 0 = 1/8.
We also use binary logistic regression without regularization. The setting is almost same as 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 to converge to −accuracy, where = 0.02. The optiaml objective function value is set as f * = 0.11379089057514849, determined numerically. The learning rate is decayed as the η t = min(η 0 , nc 1+t ), where we extensively search the best learning rate c ∈ {2 −1 c 0 , 2 −2 c 0 , c 0 , 2c 0 , 2 2 c 0 }. In this case, we search the initial learning rate η 0 ∈ {1, 32} and c 0 = 1/8.
For linear regression, we use the same feature vectors from w8a dataset and generate ground truth [w * , b * ] from a multivariate normal distribution with zero mean and standard deviation one. Then we generate label based on y i = x t i w * +b * . This procedure will ensure we satisfy the over-parameterized The optiaml objective function value is f * = 0. The learning rate is decayed as the η t = min(η 0 , nc 1+t ), where we extensively search the best learning rate c ∈ {2 −1 c 0 , 2 −2 c 0 , c 0 , 2c 0 , 2 2 c 0 }. In this case, we search the initial learning rate η 0 ∈ {0.1, 0.12} and c 0 = 1/256.
To examine the linear speedup of FedAvg in partial participation setting, we evenly distributed data on 4, 8, 16, 32, 64, 128 devices and uniformly sample 50% devices without replacement. All other hyperparameters are the same as previous sections.
The experiments of Nesterov accelerated FedAvg (the update formula is given as follows) uses the same setting as previous three sections for vanilia FedAvg.
We set β t = 0.1 and search α t in the same way as η t in FedAvg.
F. 6 The impact of E.
In this subsection, we further examine how does the number of local steps (E) affect convergence. As shown in Figure 2 , the number of iterations increases as E increase, which slow down the convergence in terms of gradient computation. However, it can save communication costs as the number of rounds decreased when the E increases. This showcase that we need a proper choice of E to trade-off the communication cost and convergence speed.