Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the partial participation aspect in local SGD method. In previous works uniform sampling of clients is usually assumed, which is not close to real situation in practice. In this work authors introduce a new general framework for analyzing and understanding different strategies of partial participation. 

The framework allows to decouple terms such that it is possible to analyze effect of partial participation separately. Authors firstly provide general results and then analyze some special cases and reflect results. 

In the end of the paper a wide range of experimental results was provided.
strengths_and_weaknesses: Strengths:

The provided framework is general and it covers many practical examples. The paper is well-written in general, all assumptions and definitions are clearly stated. All formulations of theorems are clear.

Theoretical analysis seems to be correct. I checked the appendix and I did not find mistakes, but I might miss something.

Obtained results are interesting and they lead to new prospectives and insights. 

The experimental comparison is meaningful and illustrative.

Weaknesses:

The analysis relies on Bounded gradient divergence assumption. It means that level heterogeneity is limited. This assumption contradicts to experimental design, where they "partition the data into clients so that each client has data of one majority class label." It would be interesting to see analysis without bounded heterogeneity. 

The analysis is done only for non-convex objectives. It would be interesting to see analysis for strongly convex and general convex objectives. Also it is interesting to study PL condition. 


questions: Can you please explain if it is possible to do such analysis for local methods which can tackle heterogeneity? (https://arxiv.org/pdf/1910.06378.pdf, https://arxiv.org/abs/2202.09357)

Is it possible to extend the analysis for the case when bounded heterogeneity is not used?
limitations: There are two main limitations: 

1) No analysis for convex objectives 

2) Bounded heterogeneity assumption

3) No analysis for local methods that can tackle client drift (heterogeneity): SCAFFOLD, ProxSkip, FedLin.

Overall, contribution is quite good and despite all limitations I lean towards to accept.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers federated learning with arbitrary patterns of client participation and provides a novel analysis. Several participation patterns have been studied and analyzed.
strengths_and_weaknesses: Strengths:
1. The paper is largely well-written and provides adequate intuition and explanation for the math introduced.
2. The paper makes a relevant and significant contribution, addressing the problem of arbitrary client participation.

Weaknesses:
1. Although the authors have made a good effort toward explaining all the math, in quite a few places I found myself scrolling back and forth to remind myself of the terms being discussed. I understand that the authors were working under a hard page limit. Therefore, if accepted, I would suggest the authors expand the description, especially in Sections 4.2 and 5. It might even help to remind the authors what some terms mean, even if they are defined earlier.
questions: 1. In all the results, it is assumed that $P \leq T/2$. And for the $\delta^2$ term to be zero, the average participation weights need to be equal over any $P$ interval. Will these results be able to accommodate the case when $N$ is huge, such that a client will likely only participate once?
2. With $\sigma = $ in Corollary 4.3, the bound reduces to $O(1/T)$, which is what one gets with gradient descent. However, the bound in Corollary 4.7 does not reduce to $O(1/T)$ in this special case. Can the authors comment on this difference, and is there a way to address apparent sub-optimality?
3. I'm not sure if I follow the reasoning in the remark following Corollary 4.8, explaining how $I$ need not be small. Can you elaborate?
limitations: The main limitation of the paper for me is the large $N$ case, where Proposition 4.2 may be difficult to satisfy. To get a decent convergence rate, $P$ will have to be smaller than $\sqrt T$ (see Corollary 3.2, 3.3). However, for large $N$, each client may not even be sampled in each $P$ length interval.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper mainly provides a general convergence analysis of federated learning when there is arbitrary client participation and proposes an amplification method to update gradients in federated learning under the arbitrary participation of clients. More specifically, there are four main client participation patterns that the authors consider in their analysis: regularized, ergodic participation, mixing, and independent. The paper shows that under these participation patterns, their proposed application method for federated learning can achieve convergence to zero, and also some patterns can match the linear speed-up in the convergence rate (shown in prev. works) with the increase in the number of participating clients. The experiments on FMNIST and CIFAR-10 are presented to show validation of the speed-up that the proposed method can achieve.
strengths_and_weaknesses: *Strengths:
In general, the paper is well written and provides meaningful insight into federated learning with a unified convergence analysis for arbitrary client participation. Specifically, these are the main strength of the paper:  
- The paper theoretically and empirically addresses an important problem of federated learning which is arbitrary client participation. While many work in federated learning considers a fixed client participation pattern, in real implementations of cross-device federated learning, clients can leave or join arbitrarily depending on their circumstances. There are not much work that has a unified analysis of different patterns (including stochastic) of client participation, and this paper contributes to the federated learning community largely by presenting such analysis. 
- The paper compares its analysis with relevant other work including [11], [27] referenced in the paper as well as the other work which shows linear speedup in convergence with partial client participation in federated learning [31]. It is interesting to see in what scenarios for arbitrary client participation we can achieve a similar linear speedup which the paper thoroughly provides insights on. 
- Although the contribution of this paper is more on the theoretical side, it proposes an interesting amplification method (line 11-14 in Algo. 1) which does not really need additional computation/communication at the client side, and only requires additional memory saving at the server side (which in general is a plus for federated learning). This method also achieves 0 convergence error in some client participation patterns which is interesting and validated in the experiments.


*Weaknesses:  In general, the paper has several weaknesses but they do not surpass the strength of the paper in my opinion. Here are some of the weaknesses:
- The intuition behind the amplification method in Algorithm 1 is unclear. Although it is a strength that using this method can assist in achieving 0 convergence error in the analysis, the insight/reason for this is unclear. The paper also lacks a bit in explaining the main intuition behind algorithm 1.
- In addition to the point above, the $\eta$ seems like a very important hyperparameter that can largely affect the performance/convergence of the algorithm. However, the clear effect of these hyperparameters has not been viewed much either theoretically or empirically throughout the paper. Perhaps having some ablation study on the $\eta$ can help further understand the implications/effectiveness of the proposed algorithm 1.
- The four main different client participation patterns that the paper considers are quite general, partly I assume is because they are defined to be applied to the theoretical analysis. It would be more interesting if the authors gave some connection with the arbitrary client participation patterns that exist in the real-world federated learning applications such as periodic shifts [6-7] (as cited in the paper). 

questions: I have questions related to the three weaknesses mentioned in the section above. In short the following three questions:
- What is the intuition for the amplification method in algorithm 1?
- How does the hyperparameter $\eta$ effect the algorithm performance? How sensitive is the algorithm to this parameter? Is there an ablation study that can show this?
- What are some realistic scenarios that represent the four main different client participation patterns?
limitations: The authors have clearly stated the limitations of their work.
review_title: null

Meta-review: metareview: The paper was appreciated by all three reviewers, and all gave strong endorsement. Some of the positive comments include:

- The paper is well-written in general, all assumptions and definitions are clearly stated. 
- All formulations of theorems are clear.
- Theoretical analysis seems to be correct. I checked the appendix and I did not find mistakes, but I might miss something.
- Obtained results are interesting and they lead to new prospectives and insights.
- The experimental comparison is meaningful and illustrative.
- The paper is largely well-written and provides adequate intuition and explanation for the math introduced.
- The paper makes a relevant and significant contribution, addressing the problem of arbitrary client participation.
- In general, the paper is well written and provides meaningful insight into federated learning with a unified convergence analysis for arbitrary client participation.
- The paper theoretically and empirically addresses an important problem of federated learning which is arbitrary client participation. While many work in federated learning considers a fixed client participation pattern, in real implementations of cross-device federated learning, clients can leave or join arbitrarily depending on their circumstances. There are not much work that has a unified analysis of different patterns (including stochastic) of client participation, and this paper contributes to the federated learning community largely by presenting such analysis.
- The paper compares its analysis with relevant other work including [11], [27] referenced in the paper as well as the other work which shows linear speedup in convergence with partial client participation in federated learning [31]. It is interesting to see in what scenarios for arbitrary client participation we can achieve a similar linear speedup which the paper thoroughly provides insights on.
- Although the contribution of this paper is more on the theoretical side, it proposes an interesting amplification method (line 11-14 in Algorithm 1) which does not really need additional computation/communication at the client side, and only requires additional memory saving at the server side (which in general is a plus for federated learning). This method also achieves 0 convergence error in some client participation patterns which is interesting and validated in the experiments.

I have read the reviews, rebuttal, and also skimmed through the paper. Virtually all criticism was successfully addressed; and I would ask the authors to make sure all changes that were promised would be implemented. 

I agree with the reviewers that this paper clearly passes the acceptance bar. Congratulations on such a nice paper!

AC
confidence: Certain
Decision: Accept