Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper analyzes the convergence of FedAvg with biased client selection strategies. And the new strategy power-of-choice is designed based on the convergence results. This new strategy is numerically compared with two benchmark strategies and shows faster convergence and higher testing accuracy.

Pros:
1. The convergence analysis is new and novel. This paper provides the first convergence analysis for a general class of biased client selection strategies. New concept, selection skew, is introduced as the measure of strategies. Based on the new concept, the analysis quantifies how the bias of the strategy affects the convergence speed of FedAvg.
2. New strategy pow-d is proposed based on the insights of the convergence analysis. The performance of pow-d is impressive in the FMNIST experiment, where it significantly improves the test accuracy under random selection strategy.

Cons:
1. Although the analysis is interesting and insightful, the effect of \rho seems to be limited. There are three constant terms in the vanishing error term in Eq.(7). And only the first term will be decreased when increasing \bar{\rho}. However, it is not obvious if the first term is the dominating term.
2. Is it possible to give an exact or estimated values of \bar\rho and \tilde\rho for different strategies in the numerical experiments?
review_title: Review of Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies

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

Summary:

This paper studies federated learning (FL) and proposes nonuniform sampling of participating clients. Clients are selected according to their losses; clients with big losses are likely selected. The proposed algorithm has a rigorous convergence analysis. The proposed algorithm is demonstrated powerful on small scale datasets.



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

Reasons for score:

I find this submission a borderline paper. I am fine with either acceptance or rejection. This paper has theoretical guarantees and strong empirical advantages. But the actually used algorithm may not be very useful. The experiments are conducted on small datasets. I am not confident whether this work will have an advantage on large-scale data.




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

Pros:

+ The idea of choosing participating clients according to loss is an interesting and reasonable idea.

+ The non-uniform sampling of clients is proved to converge.

+ The nonuniform sampling algorithm has a strong empirical advantage.


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

Cons:

1. The actually used algorithm is the power-of-choice strategy. It firstly uses a uniformly sampled set of $d$ clients to compute losses and then sample a subset of $m < d$ clients out of the $d$ clients.
Here is my question: The server needs to communicate with the $d$ clients from the candidate set. The server must wait for their responses. So the $d$ clients are actually active. Why not use all the $d$ clients to compute gradients? Is the proposed strategy comparable to using all the $d$ clients? 

2 FMNIST seems to be the only used dataset. The dataset is not big enough. Even if it is big enough, I would like to see empirical results on other datasets, e.g., MNIST, CIFAR10, mini-ImageNet, etc. Admittedly, this work has an advantage on FMNIST. But I am not convinced that this work is better in general.



##########################################################################
review_title: Borderline paper; Needs more experiments

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

Summary:

The paper analyzes a biased client selection policy in the context of the federated learning paradigm. 
In particular, instead of random selection of the clients with a probability that is proportional to 
the size of the local dataset, clients with higher local loss values are selected.
Despite being already used as heuristics, the authors claim that their work is the first one to 
propose a convergence analysis of a biased client selection mechanism in the context of federated
learning. Under some (quite stringent) assumptions, the authors derive a global bound for the expected 
error after $T$ iterations. The bound is composed of two terms: a vanishing term and a non-vanishing one
which comes as a consequence of the biased client selection mechanism. From Theorem 3.1 it emerges clearly 
that the biased selection mechanism poses a trade-off: on one hand the non-vanishing term increases the more biased is the selection, on the other hand the vanishing one benefits from the biased selection mechanism since the more biased is the selection the faster it will decay to zero.     
The biased selection mechanism comes with some additional computational and communication costs with respect to a fully random selection: the authors propose a couple of heuristics to alleviate these extra-costs. 
In the experimental section the proposed method is evaluated on different benchmarks and with different datasets.

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

Reasons for score: 

The paper is well-written and the theoretical results look correct. At the same time, there are some weaknesses
(see the section on Cons).
 
########################################################################## 

Pros:
 
1. The paper takes is well-written and really easy to follow.

2. The authors attempt to provide a more rigorous analysis to an already-in-use heuristic and it is the first time that such 
analysis is carried out in this context.  

3. The paper has a good balance across the sections and it touches on theory and experimental part in a balanced way.

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

Cons: 

 1. The assumptions on which the theoretical analysis is based are quite stringent and could be further relaxed (especially
strong convexity). 

 2. Incoherent benchmarks: the authors are not reasoning regarding the introduced assumptions and whether they hold. It actually seems that at least in the DNN case the assumptions are not holding since the landscape is notoriously non-convex. 

 3. Experiments only show the behavior of the heuristics pow-d. What happens when d=K? In order for the experiment to be in line with the theoretical results this case should be analyzed at least once. Introducing the extra random selection of $m\leq d\leq K$ clients could indeed change the setting and therefore the convergence.

 4. Way too strong and unjustified statements, i.e. faster convergence to a global minimum (according to Th.3.1. it does not converge), convergence up to 3 times faster (in one benchmark, might easily depend on hyperparameter settings or on the heuristic added on top on power-of-chance).

5. All the statements regarding the test accuracy are pure speculations as there are no theoretical and/or consistent and extensive empirical evidence which suggest that the biased selection mechanism leads to better generalization. Intuitively adding a bias in the selection should lead more easily to overfitting.


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

Questions during rebuttal period: 

Please address and clarify the cons above 
 
#########################################################################

Interesting General Aspect Not Considered

1. local SGD iterations: how does $\tau$ impacts on the convergence? Is it beneficial to perform more local SGD steps or does it become harmful for the convergence? How does this relate with the biased selection mechanism?

2. first random selection of $d$ clients based on proportions of dataset: unbalanced work load might create inefficiency since the general method described is synchronized.




review_title: Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies 

final_score: rating: 4: Ok but not good enough - rejection
review_content: This work investigates federated optimization considering data heterogeneity, communication and computation limitations, and partial client participation. In contrast to past works, this paper focuses on deeper understanding of the effect of partial client participation on the convergence rate by considering biased client participation. The paper provides convergence analysis for any biased selection strategy, showing that the rate is composed of vanishing error term and non-vanishing bias term. The obtained rates explicitly show the effect of client selection strategy and the trade-off between convergence speed and the solution bias. Then it proposes a parametric family of biased selection strategy, called power-of-choice, which aims to speed up the convergence of the error term at the cost of possibly bigger bias term. Experiments are provided to highlight the benefits of the proposed pow-d strategy over the standard unbiased selection strategies.

In terms of the assumptions on the loss functions, there is no improvement as the same assumptions are used in recent works [4,5]. The Assumption 3.4 seems problematic as together with Assumption 3.3 it implies that gradients of local loss functions $F_k$ are uniformly bounded. This is in conflict with Assumption 3.2 as local losses $F_k$ are assumed to be strongly convex. For instance, in papers [1,2,3] the Assumption 3.4 is not needed. Can the current theory be extended by relaxing Assumption 3.4 ?

For Definition 3.1 on local-global objectivity gap, it should be mentioned that this notion was defined and used earlier in [4]. It should be credited properly.

The metrics $\bar{\rho}$ and $\tilde{\rho}$ describing the skewness of client selection strategy, and their explicit effect on convergence rate (7) are interesting. It is also nice that the theory, e.g. Theorem 3.1, recovers the result of unbiased client selection case without any solution bias. Since Theorem 3.1 is generic and works for any selection strategy, it does not explicitly show a clear benefit of biased selection strategy over unbiased one. Biased selection strategy reduces the vanishing error term by $\bar{\rho}$, and adds a non-vanishing bias $Q(\bar{\rho}, \tilde{\rho})=O(\frac{\tilde{\rho}}{\bar{\rho}}-1)$. So, based on the rate given in Theorem 3.1, biased selection is beneficial only if $\bar{\rho}>1$ and the difference $\tilde{\rho}-\bar{\rho}$ is small (formally it should be $O((\bar{\rho}-1)/T))$. The question is, can such biased selection strategy be designed so that it is theoretically better (or at least not worse) than unbiased selection strategy ?

The proof of the main Theorem 3.1 largely follows the proof of Theorem 1 of [4]. It seems that the proof of Theorem 3.1 deviates from the proof of Theorem 1[4] only in derivations (53)-(63), where biased-ness of the client selection kicks in and skewness metrics get involved. Such overlaps in proof techniques should be mentioned and some discussion is needed to highlight the novelty of the proposed analysis. 

Using insights from Theorem 3.1, the paper proposes a client selection strategy (with two practical variations), called power-of-choice, which aims to speed up the convergence of vanishing error by maximizing rho_bar. However, it is not clear how the other metric $\tilde{\rho}$ would behave in this selection strategy. Although inspired from Theorem 3.1, I view the power-of-choice selection strategy as a heuristic idea as (i) it focuses only on the vanishing error term and does nothing to minimize the bias term, (ii) no theoretical estimates are developed for the metrics $\bar{\rho}, \tilde{\rho}$ in this specific selection strategy.

With points made above, the theoretical contribution of the paper is weak. I think, the paper would largely improved if it were developed a way on how to avoid the bias term while using biased selection. One possible way is to design a suitable selection strategy which allows to bound the bias. For instance, from the experiment shown on Figure 2.b, it is tempting to show that for the proposed pow-d selection strategy the bias term $(\frac{\tilde{\rho}}{\bar{\rho}} - 1)$ is $O(d/K)$, which can be controlled via parameter $d$. Another possible way might be to incorporate some mechanism on top of FedAvg algorithm similar to what error compensation(or error feedback) does for biased (contractive) compression operators.

Experiments are okay, but they use up to 100 clients which is far from the scale of typical FL applications. In addition, in the experiment shown in Figure 4.b, the training loss seems to be decreasing steadily and non vanishing bias term is not dominated there. As the vanishing error term reduces by choosing larger $d$, why in this experiment smaller $d=6$ performs better than larger $d=15$ ?


[1] A Khaled, K Mishchenko, and P Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 2020.

[2] Blake Woodworth, Kumar Kshitij Patel, Sebastian U Stich, Zhen Dai, Brian Bullins, H Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? arXiv preprint arXiv:2002.07839, 2020.

[3] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized SGD with changing topology and local updates. arXiv preprint arXiv:2003.10422, 2020.

[4] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations (ICLR), July 2020.

[5] Yichen Ruan, Xiaoxi Zhang, Shu-Che Liang, and Carlee Joe-Wong. Towards flexible device participation in federated learning for non-iid data. ArXiv, 2020.
review_title: An interesting submission with limited theoretical novelty

Meta-review: In federated learning, distributed and resource-limited client nodes cooperatively train a model without sharing their local data. The results thus far on analyzing the  convergence of federated learning are restricted to “unbiased” client participation, where the probability of a client c being selected is proportional to c’s data size. This work presents the first convergence analysis of federated learning for biased client selection, and quantifies the impact of selection skew on time to convergence. Specifically, biasing toward clients with higher local loss is shown to be beneficial, and a protocol is developed based on this, to trade between convergence time and solution bias.

The paper is in general well-written, and develops a natural idea. 

The strong-convexity assumption is a concern: how much can it be weakened? The authors are also asked to run experiments systematically on (much) larger datasets. The test-accuracy and possible-overfitting concerns also need to be addressed in more depth. The authors are also encouraged to see how much Assumption 3.4---uniformly-bounded stochastic gradients---can be dispensed with. 

Decision: Reject