Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes a new method to improve previous (cluster-based) important client sampling methods in federated learning. The new method is motivated by the insight that it would be beneficial to select clients from diverse groups. Convergence analysis are also provided and the authors claim they improve over existing ones. At last, experiments on FEMNIST and CIFAR-10 are provided to validate the performance.
strength_and_weaknesses: Strength
- The idea of sampling from diverse gradient groups is a novel idea and seems to be promising.
- The authors make the proposed sampling algorithm to be unbiased.

Weakness
- The writing of this paper should be improved. There are many vague statements. For example, in the introduction, the authors explain why previous works are not good. But all the explanations are just intuitions or conjectures. They cannot be used to support the observations in Figure 2. We do not know whether these conjectures are true or not (e.g. whether cluster-IS really select clients with small gradients and whether this is the core reason causing slow convergence).
- Also, many mathematical expressions are wrong. For example, in equation 2 and 6, the function $f$ should also have some subscripts because its form changes when we sample different clients. Also, in equation (5), the authors define $E|\nabla f(x)|^2 = E|\nabla \tilde{f}(x)|^2 + \chi^2$. However, in equation (15), they wrote $E|\nabla \tilde{f}(x)|^2 = E|\nabla f(x)|^2 + \chi^2$. It is obvious these two equations are conflict with each other.
- The proof may not be correct. I didn't find any proof details for Theorem D.2, which I suspect is wrong due to the above mistakes.
- Remark 3.2 (3) is not accurate. "Chen (2020) ... with additional gradient similarity bound". This sounds like this paper did not do this and remove this assumption. But in fact, the authors define it in Assumption 3 and also use it.
clarity,_quality,_novelty_and_reproducibility: The quality of this paper should be improved. The authors should polish the writing with rigorous statements and check the correctness of the theoretical results.
summary_of_the_review: I suspect that this paper has mistakes in the proof. The theoretical results may not be valid.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes novel client sampling strategies to accelerate the convergence of 
federated averaging methods with partial client participation. The idea is to determine 
the sampling strategies to minimize variance from the worst-case convergence bounds of the methods.
strength_and_weaknesses: Designing optimal client sampling strategies is a problem of broad interest for designing scalable federated learning methods. 
The authors attempt to **design optimal client sampling strategies in theory and practice** to accelerate the convergence of commonly used federated averaging methods. 

However, I would like to state the following **major concerns**: 

1. **Limitations of using the optimal sampling for DELTA.** 

From Corollary 3.4, the optimal sampling depends on $\Vert \nabla F_i(x) - \nabla f(x) \Vert$. This strategy cannot be implemented in practice, mainly because the gradient of the whole objective $\nabla f(x)$ cannot be accessed usually for problems over huge amounts of data.

Therefore, the authors should state how this strategy is modified to be able to implement it in their experiments.

2. **Redundant assumptions for deriving the convergence results for FedIS and DELTA.**

Assumptions 2 and 3 are commonly used for deriving convergence guarantees for federated methods. This is because Assumption 2 states how different the local stochastic gradient and the local full gradient is, and Assumption 3 implies how different the local full gradient and the whole full gradient is. 

However, Assumption 4 seems to be redundant to Assumption 2, since both of them impose the property of local stochastic gradients. Therefore, the stated convergence results for FedIS and DELTA seem too restricted. 

3. **Lack of motivation on how to design the optimal client sampling strategies for FedIS and DELTA.** 

Since FedIS or Algorithm 3 from (Chen et al., 2020) looks similar to DELTA, the proof techniques between these methods should be similar. Hence, I am not sure how the variance from convergence guarantees for FedIS and DELTA is different. Can the authors elaborate on this and perhaps add the motivation before stating theoretical results?  

4. **Numerical evaluations against other unclear existing sampling strategies.** 

In the experiments, the authors compared their sampling strategies against others, e.g. the power of choice, norm, and heterogeneity. However, these strategies are not clearly stated (i.e. what is $p_i^t$)? Are they existing sampling strategies, e.g., from (Chen et al., 2020)? 

Since different $p_i^t$ lead to different additional computational costs, it would be also more interesting to compare performance of the algorithms using different sampling with respect to the wall-clock time. 

Furthermore, I have the following **small concerns**: 

1. The step-size condition in Theorem 3.1 for $\eta_L$ and $\eta$ can be simplified to improve readability of this theorem. 

The authors can write $\eta_L < \min\( 1/(8LK), C \)$ where the constant $C$ is obtained from the condition that
$1/2 - (10L^2/m)\sum_{i=1}^m K^2\eta_L^2(A^2+1)>0$. Then, the author can state the condition for $\eta$ which is $\eta \leq 1/(\eta_L L)$.

However, the constant $A$ is not clearly stated. Does it depend on the index of the client $i = 1,2,\ldots,m$?
Can the authors check this? 

2. The legend in Figure 5 includes FedSRC-G and FedSRC-D. I believe that they refer to DELTA and FEDIS. Can the authors check and edit the legend? 

3. Fedprox from (Li et al., 2018) does not use variance-reduction techniques to design federated optimization methods.
Therefore, the authors should revise this part of the text which is in their contribution section.

**Typo(s) I can spot:** 
- the data heterogeneity to **fast** the convergence speed $\rightarrow$  the data heterogeneity to **accelerate** the convergence speed.

Note that due to limited time, I cannot check convergence proofs carefully. 

clarity,_quality,_novelty_and_reproducibility: The clarity and novelty of the work should be improved and better highlighted. Details related to these concerns are mentioned in the section of strength and weaknesses. 
summary_of_the_review: I think this paper considers the problem of broad interest. However, the contributions seem to be unclear, due to unclear motivation on why and how the authors design optimal sampling strategies which are better than existing strategies. In addition, some of the proposed strategies cannot be implemented in practice, thus raising the issue on how they modify the strategies to be implementable in the experiments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considered the problem of client sampling in federated learning (FL) to improve the convergence speed of FL training. The authors proposed a new client sampling scheme called DELTA, which is unbiased and able to sample more diverse clients that carry valuable information for global model updates. The authors conducted a theoretical convergence rate performance analysis and verified the theoretical convergence performance of their proposed algorithm through simulation experiments.
strength_and_weaknesses: Strengths:
1. The client sampling problem in FL is a timely and important problem in FL.
2. The proposed DELTA client sampling scheme captures diverse clients similar to the federated importance sampling (FedIS) scheme while offering unbiased client sampling performance.
3. The new and tighter convergence results for FedIS contribute to new understandings of FedIS.

Weaknesses:
1. The bounded stochastic gradient assumption in Assumption 4 is a bit restrictive and no longer needed in many state-of-the-art FL algorithms' convergence analyses. It may be interesting to see whether this assumption can be relaxed for the DELTA client sampling scheme.

2. The sampling probability $p_i^t$ in Eq. (11) requires full gradient evaluations, which are difficult to implement in practice (also admitted by the authors). To address this challenge, the authors proposed the use of stochastic gradients to approximate the computations. However, the authors didn't theoretically analyze the impacts of the approximation errors on the convergence rate performance, which is somewhat disappointing.

3. The experiment comparisons in Section 5 may be unfair. In the comparisons between DELTA, FedAvg, and FedIS, the authors only compared the convergence speeds in terms of iterations. However, the proposed DELTA method requires rather complicated calculations of $p_i^t$ in Eq. (11) compared to simple uniform sampling in FedAvg and relatively straightforward calculations of $p_i^t$ in FedIS. That is, the per-iteration complexities of these methods are quite different. Thus, it may be better to also compare the wall-clock convergence time between these methods.
clarity,_quality,_novelty_and_reproducibility: This paper is well-written in general. However, the paper could have been organized in a better way. For example, the DELTA algorithm should be placed in much earlier sections. In the current form of this paper, the DELTA algorithm appears rather late, which left quite a few notations undefined (e.g., $\eta$ and $\eta_L$) and created some difficulty/confusion in following the paper. The proposed DELTA algorithm is novel. The reproducibility of this paper is good.
summary_of_the_review: This paper studied the problem of client sampling in FL. The authors proposed a new client sampling algorithm called DELTA, which could achieve both unbiasedness and capture diverse client information. The authors provided rigorous theoretical performance analysis and also provided new insights for FedIS, which is also a new contribution. However, the authors didn't provide any theoretical performance analysis for DELTA with stochastic gradient approximation. Also, some experimental results on convergence speed comparisons may be unfair.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors explore the use of importance sampling (IS) its extensions for selecting clients in FL, where IS is based off gradient norms. They first provide a convergence analysis for standard IS sampling (sampling proportional to size of gradients). They then propose an alternative IS sampling which captures both gradient magnitude, as well as gradient diversity (the difference between the client's gradient and the global objective function gradient). They provide a convergence analysis for this sampling scheme and compare the scheme with the original FedIS.
strength_and_weaknesses: Strengths
- Strong theoretical analysis. 
- Theory is interpretable and illuminating about the nature of the problem.

Weaknesses
- Experimental results are somewhat weak, with only a marginal improvement over FedIS in experiments on real datasets. 
clarity,_quality,_novelty_and_reproducibility: The paper is very well written, which is impressive for a theoretically focused paper. 
Experiments are well described and would not be too challenging to reproduce.

summary_of_the_review: This paper extends the analysis of IS for FL, and proposes a principled extension which (at least partially) solves a well known diversity issue that is common to IS in general (though it's certainly even more pronounced in FL). The clear theoretical analysis is a valuable contribution to the field of client selection for FL.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a new method to improve previous (cluster-based) important client sampling methods in federated learning. The new method is motivated by the insight that it would be beneficial to select clients from diverse groups. Convergence analysis are also provided and the authors claim they improve over existing ones. At last, experiments on FEMNIST and CIFAR-10 are provided to validate the performance.

Key issue with the work: the optimal sampling depends in information not available in the partial participation setting: "Corollary 3.4 says that the optimal sampling depends on the full gradient, which is not available." Thus, the claimed theoretical benefits are valid for a method that can't be implemented. The statements related to theoretical superiority to the mentioned works are thus not fully justified; this key limitation is not mentioned in the right places. Moreover, the new rates are inferior to some recent advances/results in the field, example: https://arxiv.org/abs/2205.15580 and the references therein. These works were not mentioned, and this is a serious omission as they deal with the same problem: improving results for partial participation in the nonconvex regime. Assumption 3 is not justified beyond stating it is commonly used. This assumption (as well as other commonly used assumptions) was recently criticized in https://arxiv.org/abs/2002.03329 .

Other than this, I appreciate that the authors responded to the reviewers in detail, and that they adjusted their manuscript based on some of the criticism raised. 

However, I believe that the paper cannot be accepted in its current form due to the above issues which I think are of a significant nature, especially since ICLR is a top venue in the field. 

AC

justification_for_why_not_higher_score: The improvements over the baseline are based on an assumption that full gradient is available in each communication round, which is exactly not the case in the partial participation setting the authors study. So, the theoretical improvements are meaningless. Moreover, stronger baselines exist (with better rates than what the authors obtain), and these have not been compared against. These are fatal issues in my view and the paper can't be accepted.
Decision: Reject