Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes to use importance sampling in client sampling in federated learning to improve convergence behavior and reduce communication. 
Contribution:
1. A new importance sampling scheme based on the norm of gradients/updates.
2. Experiments show the proposed sampling scheme outperforms uniform sampling.
main_review: Strengths:
1. Theoretical optimality of the new client sampling method is given to motivate it.
2. The proposed client sampling method outperforms uniform client sampling.

Weaknesses:
1. The major concern is there is no comparison with other importance sampling methods. There is a large amount of literature on importance sampling methods for optimization algorithms to improve convergence, the proposed importance sampling scheme should be properly compared with existing literature and highlight the novelty of the proposed scheme. For example, [1] is a well-known importance sampling scheme for SGD to reduce update variance, the sampling probabilities depend on the magnitude of gradient (which will become update magnitude if trivially adapted to federated learning setting). The authors have a one-sentence argument that the difficulty of using [1] is the complexity is equivalent to using the full-batch gradient, which I think is because estimating the sampling probabilities requires computing all per-sample gradients. However, in the authors' setting, estimating sampling probabilities require estimating updates from all clients or at least some selected clients, though it might be practical, why can't one apply the importance sampling method in [1] with the sampling candidates being all clients or the selected clients (instead of the per-sample gradient)? Also, I feel the importance sampling technique in [1] is quite similar to the proposed importance sampling method, though the proposed scheme has some special adaptation to distributed settings (Algorithm 2). In a word, my concern is that the novelty of the proposed sampling scheme is unclear compared with other existing importance sampling methods for SGD. I hope the authors could add a more clear discussion on this point especially the difference and improvement compared with [1] since the sampling scheme is the main contribution.

2. There is not much in-depth analysis on the improvement of the proposed client sampling method over uniform client sampling. The convergence analysis relates the convergence rate with \alpha^k (12) but the discussion on how \alpha^k changes with gradient/update distribution are very limited.  I think the most important thing is to get an in-depth understanding of how the reduction of variance depends on gradient/update distribution, which is not given enough attention in the paper. Instead, the paper focus on the convergence analysis of algorithms. However, in my impression, many convergence analysis of SGD and FedAvg directly depends on the variance of the update (I am pretty sure this is the case for SGD, but for some advanced sharp analysis for FedAvg it might be different), with importance sampling applied, when the estimator is unbiased, the only thing that is changed in the convergence analysis could be the variance term, so the new analysis could be just directly substituting the variance term into the existing analysis which is kind of trivial. If the convergence analysis is non-trivial, it could be great to point out the difficulties in analysis when using importance sampling to highlight the challenges and avoid giving the readers an impression of trivialness.

Summarizing my two points, I think the novelty of the proposed scheme is not clear to me. I have an impression that the proposed importance sampling scheme is not much different from traditional importance sampling methods for SGD and the convergence analyses are not much different from existing ones. If my impression is true, it makes the contribution of this paper being the application of importance sampling in FedAvg which I believe is not enough to pass the acceptance bar for NeurIPS. I am willing to change my score if the authors could convince me of the novelty of the paper.

[1]. Zhao, Peilin, and Tong Zhang. "Stochastic optimization with importance sampling for regularized loss minimization." international conference on machine learning. PMLR, 2015.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose an efficient client (sub) sampling scheme for federated learning (FL) which relies on the quality of the update of each (sampled) client. The authors justify their construction by designing the (sub) sampling strategy that minimizes the gradient variance over the whole network (or sampled clients). The authors analytically show the convergence of DSGD and FedAvg under their sampling strategy which improves on the uniform sampling strategy. Finally, the authors empirically validate the proposed sampling algorithm by showing considerable communication gains compared to both and uniform client sampling strategies. 
main_review:  
Communication is a bottleneck for large-scale FL applications and the design of efficient sampling strategies is, therefore, an important problem. The authors consider the sampling design problem from the viewpoint of minimizing the variance of the estimated gradient. The paper is well written and the presentation is sufficiently clear. The experiments presented in the paper show that the proposed sampling algorithm can reduce the communication requirements of the standard algorithms considerably compared to the baselines. Below some of the concerns and comments are listed which the authors should address, especially, the technical concerns:

1.	The discussion from lines 148 to 149 is not clear. Specifically, it is not clear why the authors claim the optimality of the proposed client sampling strategies. In inequality (4), the authors present an upper bound of the client sampling strategy and show that i) the upper bound is minimized for the independent sampling strategy (via the choice of $v_i$’s) and ii) the inequality will be equality for independent sampling. It seems to me that the above-discussed sampling strategy will minimize the upper bound on the r.h.s. of equation (4) rather than minimizing the variance of the sampled gradient. Please make the above discussion clear and verify the claims.   

2.	The first equation in Section 2.1 will hold if the expectation of the inner product between the two terms $G^k - \sum_{i=1}^n w_i U_i^k$ and $ \sum_{i=1}^n w_i U_i^k - \nabla f(x^k)$ is zero. This will happen only if conditioned on  $U^k_i$ the estimate $G^k$ is unbiased (the probabilities $p_i^k$ are dependent on $U^k_i$ as from Algorithms 1 and 2 the distribution of $S^k$ changes with $p_i^k$). Please clarify this in the paper. It would be helpful if the authors can explain the expectations.  

3.  The goal of the paper is to minimize the communication requirement but the authors only try to minimize the gradient variance as the authors also state in Lines 93-95 that their scheme “probably” leads to communication reduction. So, I am not sure if calling the proposed sampling strategies optimal is justified.  
  
4.	The authors should give intuition behind the approximate Algorithm 2, specifically, why it will approximately minimize the variance. Moreover, it appears that Algorithm 2 can be fully executed at the server which might alleviate some of the communication requirements.  

5.	For FedAvg (Algorithm 3), the $U_i^k$ used for sampling the clients is different from the one discussed in Section 2. Do the proposed analysis and the discussion of Section 2 still work, and again, can the authors claim optimality for their sampling strategy?   

6.	FL algorithms as well as the experiments authors conduct are on non-convex losses. So, it would be interesting to see the performance of the proposed sampling strategies for non-convex losses.  

7.	The approach proposed by the authors is closely related to event-triggered distributed algorithms. The authors should discuss the advantages/drawbacks compared to event-triggered problems.
 
Minor Comments:
1.	In Theorem 2 strong convexity of $f_i$’s is not required, however, in Theorem 3 it is required. Why?
2.	Discussion in Line 203: “at most $m$ non-zero updates” is not clear
3.	In Line 166-167, what is the ideal situation authors are referring to?
4.	In the 4th contribution bullet the authors say that a larger learning rate leads to better communication complexity. Why is that so? Because of faster convergence? Also, if relevant please discuss this in detail with the main results.
5.	Please correct, Line 142: “the sampling procedure that minimizes (3)” 
6.	In the abstract line 4: correct participated to participating
7.	In the abstract, instead of “formula” probably use “expression”  
8.	Line 22: $\mathcal{D}_i$ is data or distribution of data. Also, define $\xi$.
9.	Please add some references to the claims made in Section 1.1 of the Introduction. 
10.	Section 1.2: Lines 58-59 are not clear. It was shown in [29] that the sampling in [26] is optimal? Please clarify
11.	Line 83: replace “addressing” by “address”
12.	Update the discussion from Lines 148-151
13. Is it standard to have the dependence of the step-sizes on $\alpha^k$?

-----------
Updated the score.
limitations_and_societal_impact: 
yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a strategy to _optimally_ sample clients on a given FL global round. The sampling strategy selects more informative updates by their magnitude. This criterion minimizes the variance of the sampling scheme. 

Experiments show this method outperforms uniform sampling. 

main_review: 
**Originality**
- The paper proposes a nice closed formula deriving a sampling scheme with good properties: minimizing variance. However, it is missing relevant references in the field, particularly the following paper which has a really similar strategy:
--  Rizk, Elsa, Stefan Vlaski, and Ali H. Sayed. "Federated learning under importance sampling." arXiv preprint arXiv:2012.07383 (2020).
This paper seems to derive the same sampling strategy and apply it both to client selection and, within each client, datapoint selection.
- The related work section misses several client sampling strategies in FL.
-- [1] Li, Xiang, et al. "On the convergence of fedavg on non-iid data." arXiv preprint arXiv:1907.02189 (2019).
Chen, Tianyi, et al. "LAG: Lazily aggregated gradient for communication-efficient distributed learning." arXiv preprint arXiv:1805.09965 (2018).
-- Cho, Yae Jee, Jianyu Wang, and Gauri Joshi. "Client selection in federated learning: Convergence analysis and power-of-choice selection strategies." arXiv preprint arXiv:2010.01243 (2020).
-- Ribero, Monica, and Haris Vikalo. "Communication-efficient federated learning via optimal client sampling." arXiv preprint arXiv:2007.15197 (2020).
-- N. Singh, D. Data, J. George, and S. Diggavi. Sparq-sgd: Event-triggered and compressed communication in decentralized stochastic optimization. arXiv preprint arXiv:1910.14280, 2019.

**Quality**
- Line 116 affirms that this method _easily_ extends to an arbitrary availability distribution. This is not vlear to me since previous work has found that, for example under a cyclic distribution, SGD can diverge. How does this extend?
- How to control in practice the number of participant users m?
- How to deal with a large number of clients? In practice not all users can train since the number of clients is in the order order of millions…
- Theorem 2 implies that there is no convergence? since \eta^k is fixed the last term won’t vanish
- Experiments are limited and only compare with uniform sampling and full participation. However, it has been shown in [1] that sampling proportionally to p_i can have better performance. How would this method compare with this sampling strategy? 
- The experimental setting is limited and only tested on variations of EMNIST. It would be interesting to see how this sampling behaves in different tasks. 

**Clarity**
- The introduction is clear but as it advances the paper could improve the phrasing, it is easy to get lost in the convergence guarantees. 
- Small comments:
-- In line 170 is it p_is that are larger or smaller?
-- Line 227 It should be “our obtained”. In general this paragraph needs some editing, there are several typos. 

**Significance**
-  In certain FL settings, client sampling can improve the accuracy of the model while reducing communication. This paper proposes a sampling scheme theoretically motivated. However, the proposed strategy (or similar ones mentioned above) have already been proposed by previous work. I would recommend the authors to clearly state how their work differentiates from these works that select clients for training - particularly approaches relying on update norm and/or importance sampling. 

limitations_and_societal_impact: Yes, this is a theoretical paper and societal impacts,  besides fairness that is addressed in the paper, are out of the scope of this work. I would recommend clarifying and being more specific about the fairness metric used, I am assuming it means just accuracy for all clients? In this case it should be justified why the global optimum is more fair than other solutions.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper works on strategies of client subsampling for federated learning. Specifically, it proposes an adaptive partial participation strategy, which can carefully sample clients in each round to sending their updates to the server. More importantly, the paper proposes a practical approximation to optimal sampling strategy. Theoretical analyses are given for the proposed sampling scheme, which shows better performance than existing FedAvg with uniform sampling.
main_review: Originality:  The paper has proposed a client sampling scheme, which shows better convergence performance for federated learning algorithms.  However, the new sampling scheme heavily depends on Lemma 1, which has been well studied in papers for arbitrary sampling. 


Quality: The submission technically is sound. Claims are well supported by theoretical analysis or experimental results.

Clarity: The submission is clearly written and well organized.

limitations_and_societal_impact: Lemma 1 has been studied in other literature for arbitrary sampling, for example, "S. Horvath and P. Richtarik, “Nonconvex variance reduced optimization ´ with arbitrary sampling,” in International Conference on Machine Learning, 2019, pp. 2781–2789". The authors should cite the related works for reviewers to better position the paper.  What's more, can authors show difficulties and challenges encountered during theoretical analysis?

The theoretical results need the assumption of strong convexity.  However, in experiments, two-layer CNN is used, which is nonconvex. Therefore, in order to be consistent and verify theoretical findings, the authors should either show theoretical results for nonconvex function or run experiments with linear or logistic regression etc.

In experiments, only Fderated EMNIST data is used. The authors should also include more experiments.
review_title: null

Meta-review: In this work, the authors propose an efficient client sampling scheme for federated learning (FL) which relies on the quality of the update of each (sampled) client. The sampling strategy is designed based on  minimizing the gradient variance over clients. The authors provided convergence analysis for the DSGD and FedAvg algorithms under the proposed sampling strategy. Finally, the authors showed that numerically, considerable communication gains can be achieved compared  the uniform client sampling strategies.

Pros:

1) A new importance sampling scheme has been introduced to the FL setting, which is based on the norm of gradients/updates. Theoretical optimality of the new client sampling method is given to motivate it.

2) Convergence analysis has been conducted. 

3) Experiments show the proposed sampling scheme outperforms uniform sampling.


Cons:

1) Many reviewers have pointed out, that the authors have not made a fair comparison with [43]. The optimal sampling scheme is strongly motivated by the sampling scheme in [43], but the authors fail to point this out in the paper. This has caused a lot of confusion about the main contribution of the paper. 

2) Analytical improvement of the proposed client sampling method over uniform client sampling is not clear. 


3) Claims about extensions, for example to client intermittency, non-convex losses, have been mentioned, but these claims are somewhat misleading since they should be either analytically or empirically justified.

4) Finally, despite the fact that large gains have been shown, the empirical result is a bit limited compared to typical FL papers (which include multiple datasets and tasks).

Overall, the most important reason for rejecting this paper is that, the AC and the reviewers remain not convinced about the main contribution of this work. I would suggest the authors to take these comments into consideration, and thoroughly compare their scheme with [43], and clearly demonstrate that their approach is non-trivial extension of the existing optimal sampling scheme. 

Decision: Reject