Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the use of diversity sampling (based on submodular functions) for selecting clients who send updates to the server in a federated learning environment. As the authors show, this provides more efficient use of communication budget in terms of convergence and model accuracy.
main_review: Subdmoularity-based subset selection is widely used in many contexts, but as far as I can tell, it's the first time in federated learning. Use of gradients in this context is not novel.

Theoretical and empirical results are significant.
summary_of_the_review: The paper proposes a new approach for diverse sampling of clients in each update round of federated learning. This significantly improves convergence rate and model accuracy. Though the idea is not particularly novel in the broader context, it does advance state of the art in federated learning.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper studies a problem of improving the efficiency of federated learning by selecting a
subset of clients whose gradients are representative. This is formulated as a submodular maximization
problem, and the authors analyze a greedy algorithm for it. This is evaluated through experiments
on synthetic as well as real datasets.
main_review: page 4: Minimizing G(S) is certainly equivalent to maximizing \bar{G}. However, the equivalence
breaks down when you consider approximation. In particular, the (1-1/e) approximation to \bar{G}
does not imply a similar approximation to G(S), in general

End of section 3: the greedy step is not clearly explained and needs more discussion, since it will
affect the communication complexity. It is mentioned that the algorithm only utilizes
"updates from the clients that participated in the previous round", and it is claimed that this works
quite well. This is pretty surprising. Is there some special structure in the instance due
to which this holds?

Assumption 1: this is a property of the algorithm. So I don't understand why this is an assumption.
You need to prove that for the sets S_t chosen in each step t, this property will hold. The authors
claim that this assumption is also made in (Mirzasoleiman et al., 2020). They should say more clearly
where that is (though an assumption in a prior paper doesn't automatically make it correct).

In view of the issue with assumption 1, it is not clear if Theorem 1 is correct

The formulation in the paper has a lot of similarity with the setup in (Mirzasoleiman et al., 2020).
The authors should explain this more carefully, instead of cursorily stating it in the Introduction
summary_of_the_review: The problem considered in the paper is interesting and well motivated. However, the formulation is
incremental, and builds quite heavily on earlier paper. The main contribution is the analysis of the
greedy algorithm, which has serious issues as mentioned above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the selection of clients for federated learning under the assumption of full participation via submodular function maximization. Specifically, the goal is to obtain a subset of the clients such that the aggregation of the gradients of their loss functions approximates the full aggregated gradient. The authors show that the error defined by the difference between both aggregations (the full one and the one defined by the subset) can be upper bounded by a supermodular function. Therefore, minimizing this function (subject to a single cardinality constraint, which is motivated by communication costs) gives an upper bound for the problem of minimizing the error. The minimization of this particular supermodular function can be equivalently posed as the maximization of a submodular function, which has been previously studied in the literature (e.g. [1] below). Given this, the authors propose a variant of the federated averaging scheme, called *DivFL*, which uses the standard greedy algorithm to select $K$ clients to communicate the current value $w_t$. They show that under the “gradient approximation error” assumption, the error between $w_t$ and $w^*$ decreases as $O(1/t)+O(\epsilon)$, where $\epsilon$ is a parameter of the assumption. Finally, they test their scheme in synthetic and real-data sets against other methods in the literature.


[1] Ryan Gomes and Andreas Krause. Budgeted Nonparametric Learning from Data Streams, 2015.
main_review: The paper is overall well-written and somehow easy to follow (see minor comments). I checked most of the math in the Appendix and it seems correct, but standard. The authors could emphasize more on the key differences between their analysis and the previous literature.

Main questions:
-	I understand the use of the standard greedy algorithm for the selection of clients in DivFL, however, the role of submodularity doesn’t seem to give an advantage, at least theoretically speaking. In other words, which role does submodularity play in the analysis of the algorithm? Is there any connection between Assumption 1 and submodularity? 
-	Assumption 1 seems rather strong. The authors should motivate more this. For example, which classes of functions satisfy this? How large is $\epsilon$ in that case or in the worst-case?
-	The authors focus on the full communication case, can this approach be adapted to the partial case?
-	Experiments: the authors should discuss Assumption 1 for the objectives used in this section, at least to have a sense of how large is $\epsilon$ for these applications. Also, it would be great to have an idea of the of time that each method spends.

Minor comments:
-	Assumption 4 and 5 are for all t? 
-	Page 5: in the definition of $\overline{v}_t$, it is $v^k_t$.
-	The Setup paragraph in Page 5 is a bit confusing, it would be great if the authors could explain more the role of $\overline{v}$ and $\overline{w}$, in particular, why they are needed for the analysis in Theorem 1.
-	Appendix: $g_t$ and $\Delta v^k_t$ are not defined.


summary_of_the_review: The paper is interesting and well-written. The convergence analysis seems to be correct. However, the theoretical role of submodularity is not quite clear, besides the use of the greedy algorithm for the selection of clients. Assumption 1 seems quite strong, the authors should motivate this part more in detail. The experiments clearly show the advantage of DivFL over previous approaches in the literature.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents a new client selection strategy for federated learning. The key idea is to view the client selection problem as a facility location problem, where the objective is to approximate the aggregation of gradients of all the clients with that of a subset of selected clients. A greedy solution to the problem is derived, and the theoretical convergence analysis is also provided. Although the proposed algorithm ideally requires the gradients of all clients, the paper also introduces its practical extension that instead leverages gradients collected in previous rounds. Experimental results on synthesized and real datasets show the effectiveness of the proposed approach.
main_review: ### Strengths

- Overall, the paper is very well written. The proposed work is well-motivated, as developing better client sampling techniques is one important direction in FL. 
- Proposed approach is technically solid and seems novel enough. Although formulating client selection in FL by a combinatorial optimization problem is not completely new (e.g., Nishio and Yonetani 2019), the objective of approximating the aggregation of gradients of all clients by that from a client subset is novel, as far as I can check. I think that this is a reasonable objective for both data iid and non-iid settings and indeed worked well as shown in the experiments.
- With some reasonable assumptions, the convergence analysis for the proposed approach is provided.

### Weaknesses
Although the proposed approach is technically sound, requiring the local gradients of all clients becomes a critical limitation to adopt the approach to practical problems, as also pointed out in the manuscript. Utilizing updates collected in previous rounds would be one possible approach, but it was not fully evaluated in the experiments in my opinion.

Specifically, using previous gradients will inevitably come with a stale gradient problem (as also noted in the paper). If I understand it correctly, this problem was mitigated in the experiments by limiting the number of local updates to be one for each client so as not to make model weights change dramatically over rounds. However, this is against a previous finding of federated learning where asking each client to update models multiple times leads to efficient training, as confirmed in FedAvg (McMahan et al, 2017). Even though limiting the number of local epochs could result in no significant loss when using previous gradients, does it make the overall learning procedure inefficient compared to when clients perform multiple local updates before aggregation? This is not obvious in the current manuscript. To address this concern, I'd like to see how training curves and final performances change depending on the number of local updates (\tau parameter in the experiment).

### Minor comments
- The text size of the plot labels and ticks should be a bit larger.
- The left margin of Algorithm 1 needs to be a bit larger.
summary_of_the_review: Overall, I think this is a nice paper that addresses an important aspect of federated learning: improving a client sampling strategy. Experimental results are promising, though I would like to see how not limiting the number of local updates will affect the performances. If this brings a considerable gap between DivFL (ideal) and DivFL (no overhead), that implies the limitation of the proposed approach for practical settings.
review_title: null

Meta-review: The paper proposes a novel method for (diverse) client selection at each round of a federated learning procedure with the aim of improving performance in terms of convergence, learning efficiency and fairness. The main idea is to  introduce a facility location objective to quantify how representative/informative is the gradient information of a given set of clients is, and then choose a subset that maximizes this objective.  Given the monotonicity and submodularity of the proposed facility location objective, the authors have been able to provide theoretical guarantees. Experimental results on two data sets (FEMNIST and CelebA) show the effectiveness to the proposed approach and algorithm. 

The reviewers had a number of concerns most of which were addressed in the authors response. The reviewers believe that the theoretical results of the paper are incremental given the prior work (see the reviews for more details); however, the reviewers (as well as myself) agree that the proposed method is novel and can provide significant practical advantage. Utilizing sub modular objectives for diverse selection is a well-known (and effective approach), but I am seeing it in the context of federated learning for the first time. 

My suggestion to the authors: (i) Improve the experimental section by adding a few more common data sets (such as CIFAR when data is distributed in a heterogeneous manner). CelebA and FEMNIST are not really the best data sets to try in FL (although they are commonly used). (ii) One of the reviewers had several critical comments about the theoretical results, please address those in the updated version. (iii) Please clarify in more detail how the theoretical and algorithmic contributions of there paper go beyond the recent work of (mirzasoleiman et el. 2020); (iv) iIt seems to me that the paper is missing some references on client selection in federated learning. Please revise the related work accordingly.
Decision: Accept (Poster)