Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: #### Summary of the paper:
This paper analyzes convergence rates of the standard "FedAvg" algorithm  (with two sided learning rates) that is widely used in federated learning in multiple orthogonal perspectives:
a) non I.I.D datasets - with reasonable assumptions about the heterogeneity and suitable parameters, convergence guarantees comparable to I.I.D setting can be achieved.
b) partial worker participation - provides an analysis of convergence based on the number of workers participated (constant $n$) in each round.
c) number of local steps - analysis of overall convergence rate that depends on this is provided, but full effects are not yet clear (open problem).
This paper provides ample empirical evaluations to validate the theoretical claims shown.

#### Quality:
This paper is generally well written and structured well. Although I did not read the proof of the theorems thoroughly, the claims sound natural and believable. Thorough explanations and insights of the theoretical claims are provided.

#### Clarity:
Clarity of certain parts needs to be improved.
- The claim about the number of local updates $K$ improving to $T/m$ from $T^{1/3}/m$ is not clear. At first glance this does not look like an improvement because it gets worse for the the workers(devices). But remark 3 explains that this indeed causes an improvement in the overall convergence rate. I think this should be clearly mentioned in the contributions.
- It is better if the authors can change some superscripts for footnotes in table 1, the superscripts 4 and 6 look like exponents at the first glance which can be confusing.
- In related work, it is mentioned that "(Karimireddy et al., 2019) can achieve linear speedup but extra variance reduction operations are required, which lead to high communication costs and implementation complexity. In this paper, we show that this linear speedup can be achieved without any extra requirements." State this clearly in the contributions since the table 1 does not imply this and it is difficult to understand the improvements, thus the novelty of these results by looking at table 1 or contributions.
-  I believe the the expectations in assumption 2 and theorems 1, 2 are over local datasets samples. Clearly state this.
- $f_0, f_*$ are not defined in theorem 1,2 (I believe they are loss function values at start and the optimal point). Define these quantities.


#### Originality and significance:
Although this paper does not technically introduce a new algorithm for federated, I believe that the theoretical analysis of "FedAvg" in the non I.I.D. and partial worker participation setting and relevant parameters are nice contributions to the ICLR community. I think the insights obtained by this work can be very useful in developing better algorithms and in practice since it considers more realistic scenarios and the model assumptions are reasonable. 

Pros:
- Main contributions on non I.I.D data and partial worker settings are nice and relevant realistic scenarios.
- I think the result on linear speed up that does not depend on a requirement of bounded gradient assumption is nice especially in non I.I.D and non-convex settings since such dependencies in these scenarios can be unrealistic.
- Extensive experimental evaluations on the theoretical claims validate the results.

Cons:
- One concern I have is the claimed convergence rate in FedAvg is achievable when $T \ge mK$, but in federated learning settings, it is  often the case that $m$ is very large. Therefore this requires $T$ to be very large and thus blow up the required number of communication rounds for convergence. Is this a common issue in the other works compared in table 1 or inherent in FedAvg? The experiments are also done with $m=100$, therefore it is difficult to gauge the impact of large(which is realistic) number of clients in practice.

Other comments:
I would like to understand that the requirement $|S_t| = n$ in section 3.2 can be relaxed to something like at least $n$ workers in each round and the same convergence guarantees would hold. While strategy 1 and 2 are viable, I believe this can also be a nice way to understand the partial worker setting.

Final feedback:
I thinks this paper has decent contributions to the understanding of federated averaging method in more realistic scenarios. I am willing to increase my score if the concerns mentioned above are properly addressed.
===============================================================================================================

Added after reading author response:

------------------------------------------------------

I believe authors have addressed the issues I raised about clarity in certain parts of the paper in their response sufficiently.  I agree that in this paper, the convergence rates' dependency on $m$ has been improved significantly compared to previous work. Thus I increase my score. I encourage authors to investigate $m$'s effects on the convergence rate more to see whether there is a structural limitation in federated learning settings, perhaps better left for future work.

review_title: In overall, I believe this is a decent contribution to the ICLR community which gives a clear analysis of the federated averaging in more realistic scenarios such as non I.I.D data accross devices and partial device participation. Some improvements are needed in writing and there are some concerns about the applicability to large number of workers that needs to be addressed.

final_score: rating: 6: Marginally above acceptance threshold
review_content: EDIT after discussion:

Thanks for the authors' comments and revisions to this paper. I'm glad to see that some of my concerns have been addressed so I decide to change my score.

Just some minor comments about writing for the revised version. I think the proof sketch is clear and easy to follow the logic with some room for further improvement. Like the other reviers' comments, I think some part of the paper like notations should be with clear explanation.

-------------------------------------------------------------

This paper provides a theoretical analysis for FedAvg, the seminal optimization algorithm for federated learning. The analysis is featured at client sampling and non-iid distributions among clients, which are two well-known challenges in federated learning. The theoretical results in this paper provide us an optimization view to understand why FedAvg works, and how it saves communication cost by allowing low SGD updates and by model averaging.

I think the authors can further improve this paper from the following aspects.

First, the metric for convergence rate is slightly less common in the methods shown in Table 1. Most existing works (e.g., Yu et al. 2019a, Karimireddy et al. 2019) use the average norm of stochastic gradients in the previous T steps. However in this paper the authors consider the minimum of these T values. It's not a problem per se because the minimum also shows the convergence trend somehow. The problem is, comparison with existing work as listed in Table 1 looks confusing to me. I would like to see if there is a way of showing the linear speedup in the same fashion.

Second, I think the experiment section has some room for improvement. The whole section doesn't show comparison with any existing but some curves with hyperparameter variants. In particular, I really want to see how the proposed algorithm compared with SCAFFOLD, because both rates are matched (despite my comment above). 

Like the authors said, SCAFFOLD needs to maintain an additional set of variables for variance reduction, which may introduce more communication and computation costs. For this reason, I would like to see comparison not only the convergence w.r.t. steps/epochs, but also in wall clock, under the same bandwidth constraint, FLOPS, .etc.

One minor suggestion is about writing. The technique to show the linear speedup in this paper is worth writing some lines of proof sketch. One such example is the SCAFFOLD paper. It will help readers to understand the main contribution, and may help readers to apply such technique in other related problems.
review_title: Official Blind Review #1

final_score: rating: 7: Good paper, accept
review_content: This paper provides a new analysis for the FedAvg algorithm, which assumes the data on different workers are non-IID and the objective functions are non-convex. The new analysis improved the existing bounds of FedAvg. Besides, the analysis is also extended to the non-stationary network, where the number of workers participating in the optimization may vary.

As FedAvg is the most important optimization algorithm in federated learning, I think such theoretical progress is good. 

If my understanding is correct, as the new bound allows a larger number of local steps, one important improvement for the algorithm is that the number of communication rounds can be also reduced. I suggest the authors demonstrate this fact in the paper, e.g., by adding a column concerning communication complexity in Table 1 and appending some discussion about communication cost.

One drawback of the theoretical results is that the model for the non-stationary network is too strong. It assumes the number of participants in each round is fixed, and each worker has an equal probability to participate. Such an assumption can be rarely satisfied in practice.

One typo: I guess $p_i=\frac{1}{m}$ should be $p_i=\frac{n}{m}$ in the last line of page 5.

review_title: Good theoretical results, though the model for the partial worker participation is too strong

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