Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##########################################################################

Summary:

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


##########################################################################

Reasons for score:

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



##########################################################################

Pros:

This paper has theoretical contributions. This paper contributes new theories for FedAvg, which is a very popular algorithm, under various settings.


##########################################################################

Cons:

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



##########################################################################

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

review_title: Concern about the dependence on E

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Pros: 
This 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.

Cons:
1. 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. 

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



review_title: A theoretical study on federated averaging for convex and strongly convex loss

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

Pros:
1. 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). 
2. 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.

Cons and discussions:
To 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.
1. 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. 
2. 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.
3. 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?
4. 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.

[1] Yuan, Honglin, and Tengyu Ma. "Federated Accelerated Stochastic Gradient Descent." arXiv preprint arXiv:2006.08950 (2020).
[2] Woodworth, Blake, et al. "Is Local SGD Better than Minibatch SGD?." arXiv preprint arXiv:2002.07839 (2020).
[3] Woodworth, Blake, Kumar Kshitij Patel, and Nathan Srebro. "Minibatch vs Local SGD for Heterogeneous Distributed Learning." arXiv preprint arXiv:2006.04735 (2020).
review_title: Good work but can be improved

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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. 

Even though, I still have doubts about this paper:
1).  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. 

Overall, 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.
review_title: Reivew

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