Diverse Client Selection for Federated Learning via Submodular Maximization
Authors: Ravikumar Balakrishnan
Tian Li
Tianyi Zhou
Nageen Himayat
Virginia Smith
Jeff Bilmes
Venue: ICLR 2022 Poster (2022)
Keywords: federated learning
submodularity
diversity

Abstract: In every communication round of federated learning, a random subset of clients communicate  their  model  updates  back  to  the  server  which  then  aggregates them all.  The optimal size of this subset is not known and several studies have shown that typically random selection does not perform very well in terms of convergence, learning efficiency and fairness. We, in this paper, propose to select a small diverse subset of clients, namely those carrying representative gradient information, and we transmit only these updates to the server.  Our aim is for updating via only a subset to approximate updating via aggregating all client information. We achieve this by choosing a subset that maximizes a submodular facility location function defined over gradient space. We introduce “federated averaging with diverse client selection (DivFL)”. We provide a thorough analysis of its convergence in the heterogeneous setting and apply it both to synthetic and to real datasets. Empirical results show several benefits to our approach including improved learning efficiency, faster convergence and also more uniform (i.e., fair) performance across clients. We further show a communication-efficient version of DivFL that can still outperform baselines on the above metrics.

Published as a conference paper at ICLR 2022
DIVERSE CLIENT SELECTION FOR FEDERATED LEARNING VIA SUBMODULAR MAXIMIZATION
Ravikumar Balakrishnan
Tian Li CMU
Tianyi Zhou
Intel Labs
University of Washington
ravi kumar. ba @akrishnannii www.n.tl..oo com
tianl cmu edu
ti aiayii zh@uw. edu
Nageen Himayat
Virginia Smith CMU
Jeffrey Bilmes
Intel Labs
University of Washington bi Lime@uuw.ed
nageen. www.hhattatteel.c.oom
smithv8 cmu.
ABSTRACT
In every communication round of federated learning, a random subset of clients communicate their model updates back to the server which then aggregates them all. The optimal size of this subset is not known and several studies have shown that typically random selection does perform very well in terms of convergence, learning efficiency and fairness. We, in this paper, propose to select small diverse subset of clients, namely those carrying representative gradient information, and we transmit only these updates to the server. Our aim is for updating via only a subset to approximate updating via aggregating all client information. We achieve this by choosing a subset that maximizes a submodular facility location function defined over gradient space. We introduce "federated averaging with diverse client selection (DivFI) We provide thorough analysis of its convergence in the heterogeneous setting and apply both to synthetic and to real datasets. Empirical results show several benefits of our approach, including improved learning efficiency, faster convergence, and more uniform (i.e., fair) performance across clients. We further show communication--ffiienn version of ViV that can still outperform baselines on the above metrics.
INTRODUCTION
Federated learning (FL) involves collaboratively training of machine learning model across large number of clients while keeping client data local. Recent approaches to this problem repeatedly alternate between device-local (stochastic) gradient descent steps and server-aggregation of the clients' model updates (McMahan et al., 2017). In cross-device settings, a server and its model usually serve several thousands of devices. Therefore, the communication between clients and the server can be costly and slow, forming a huge impediment to FL's viability.
One property of the collection of clients that mitigate these problems, however, is often not exploited, and that is redundancy. Specifically, many clients might provide similar, and thus redundant, gradient information for updating the server model. Therefore, transmitting all such updates the server is a waste communication and computational resources. How best to select a representative and more informative client set while adhering practical constraints in federated learning still an open challenge. Although several selection criteria have been investigated in recent literature, e.g.. sampling clients with probabilities proportional to their local dataset size (McMahan al., 2017), sampling clients of larger update norm with higher probability (Chen et al., 2020), and selecting clients with higher losses (Balakrishnan al., 2020; Cho al., 2020), the redundancy and similarity of the clients' updates sent the server is not represented and exploited in these approaches. In particular, communicating multiple clients' updates to the server may cause statistical and system inefficiency if too many of them too similar each other. The commonly studied modular score/probability for each individual client incapable of capturing information as a property over a group of clients.
Equal contributions

---

Published as a conference paper at ICLR 2022
Ideally, diverse set of clients would be selected, thereby increasing the impact of under-represented clients that contribute different information, and thereby improving fairesss. This, in fact, is a topic of increasing interest (Mohri et al., 2019; Cho et al., 2020; Dennis et al., 2021; Huang et al., 2021).
In this paper, we introduce diversity to client selection in FL, namely a strategy to measure how a selected subset of clients can represent the whole when being aggregated on the server. Specifically, in each communication round, we aim to find a subset whose aggregated model update approximates the aggregate update over all clients. By doing this, we aim to limit the impact of subset selection which introduces variance in the model updates across round, that could otherwise slow the learning process. Inspired by the CRAIG method of coreset selection for efficient machine learning training (Mirza- soleiman et al.. 2020), we derive an upper bound of the approximation error as supermodular set function (in particular, the min-form of the facility location function (Cornuéjols et al., 1977)) evaluated on the selected subset. We can then apply submodular maximization (Fujishige, 2005; Iyer et al., 2013; Wei et al., 201 4) on a complement submodular function to (approximately) minimize the error upper bound. We employ the greedy selection (Nemhauser et al., 1978) of subset of clients according to the marginal gain of the submodular function to achieve solution with provable approximation guarantee (Conforti & Coruueoos, 1984). By integrating the diverse client selection into the most commonly studied FL scheme, i.e., Federated Averaging (FedAvg) (MeMahan et al., 2017), we propose Di vFL that applies global model aggregation over a selected subset of clients after multiple local steps on every client. We present theoretical convergence analysis of Di and show its tolerance the heterogeneity of data distributions across clients and large numbers of local steps. However, our method differs from the CRAIG method where selection is performed based on model updates (involving multiple epochs at the clients). In addition, our approach allows for partial device participation where the server does not have access to all data at any communication round, as is standard in FL (McMahan et al., 2017). In experiments, we compare DivFL with other client selection approaches on both synthetic dataset and FEMNIST, wherein our method excels on convergence, fairness, and learning efficiency.
2 BACKGROUND AND RELATED WORK
We consider a typical federated learning objective:
N
min f(w) Σ (w)),,
k=1
where for each client & E [M], Pk is a pre-defined weight (such that Σ Pk 1) that can be set to N or the fraction of training samples, and F3 is the client-specific empirical loss. While there are various possible modeling approaches, we consider this canonical objective of fitting a single global model to the non-identically distributed data across all clients (McMahan et al., 2017).
1
Client Selection in Federated Learning. Client' sampling is a critical problem particularly for cross-device settings where it is prohibitive to communicate with all devices. Two common (or default) strategies are (a) sampling the clients based on the number of local data points and uniformly averaging the model updates, and (b) sampling the clients uniformly at random and aggregating the model updates with weights proportional to the local samples (Li et al., 2020). There is also recent work proposing advanced sampling techniques to incorporate dynamic systems constraints, accelerate the convergence of federated optimization, or to obtain better model with higher accuracy (Nishio & Yonetani, 2019; Ribero & Vikalo, 2020; Cho et al., 2020: Lai et al., 2020). We investigate client selection through the lens of encouraging client diversity at each communication round which largely remains unexplored in previous work. The closest client selection method to ours is based on clustering (e.g., selecting representative clients from separate clusters (Dennis et al., 2021)). We note that performing (private) clustering in federated settings is still an open problem, and our method can be viewed as a soft version of dynamic clustering at each round (discussed in the next paragraph). The benefits of gradient (or model) diversity has been demonstrated in other related contexts, such as scaling up mini-batch stochastic gradient descent (SGD) (Yin et al., 2018). Enforcing sample or gradient diversity during optimization also implicitly places more emphasis on the underrepresented
Following conventions, we use the term "client' for the problem of client selection. Throughout the paper, we 'devices' and 'clients' interchangeably.
2

---

Published as a conference paper at ICLR 2022
sub-population of clients, and can promote faimess defined representative disparity (Hashimoto et al., 2018). Similar to previous work (c.g., Cho et al., 2020; Balakrishnan et al., 2020), we observe approach yields more fair solutions across the network in Section 5.
Diverse Subset Selection via Submodularity. Modular scores have been widely studied for subset selection in machine learning and federated learning, e.g., a utility score for each sample or client often measured by the loss. However, the diversity of a subset cannot be fully captured by such modular scores since there is no score interaction. Diversity is often well modeled by diminishing return property, i.e., the (marginal) gain an element brings to subset diminishes as more elements added to the subset. There exists rich and expressive family of functions, all of which are natural for measuring diversity, and all having the diminishing returns property: given finite ground set V of size n, and any subset A C B C V and a & B, set function F :2:2 2/- - R is submodular if B) F(B).
(1) This implies e is no less valuable to the smaller set A than to the larger set B. The marginal gain of e conditioned on A is denoted (A) & A)) f(A) and reflects the importance of e to A. Submodular functions (Fujishige, 2005) have been widely used for diversity models (Lin & Bilmes, 2011; Batra et al., 2012; Prasad et al., 2014; Gillenwater et al., 2012; Bilmes & Bai, 2017).
F(bUA) F(A) 2 F(v U
Maximizing submodular function usually encourages the diversity and reduces the redundancy of a subset. This property has been utilized for data selection in active learning (Guillory & Bilmes, 2011), curriculum learning (Zhou & Bilmes, 2018), mini-batch partitioning (Wang et al., 2019), gradient approximation (Mirzasoleiman et al., 2020), etc. Although the number of possible subsets is (2), enumerating them all to find the maximum intractable. Thanks to submodularity, fast approximate algorithms (Nemhauser et al., 1978; Minoux, 1978; Mirzasoleiman et al., 2015) exist to find an approximately optimal A with provable bounds (Nemhauser et al., 1978; Conforti & Cornuejols, 1984). Despite its success in data selection, submodularity has not been explored for client selection in federated learning. Encouraging diversity amongst local gradients (or model updates) of selected clients can effectively reduce redundant communication and promote faimess. Moreover, it raises several new challenges in the FL. setting, e.g.. (1) it is unclear which submodular function to optimize and in which space to measure the similarity/diversity between clients; (2) What convergence guarantee can be obtained under practical assumptions such as heterogeneity among clients, and (3) What are the effects of outdated client selection due communication constraints?
3 DIVERSE CLIENT SELECTION
In this section, we introduce "federated averaging with diverse client selection" (or DivFL), a method that incorporates diverse client selection into the most widely studied FL scheme, federated averaging (FedAvg). We will first derive a combinatorial objective for client selection via an approximation of the full communication from all clients, which naturally morphs into facility location function in the gradient space that can be optimized by submodular maximization. We then present the standard greedy algorithm that optimizes the objective by selecting a diverse subset of clients at every communication round.
3.1 APPROXIMATION OF FULL COMMUNICATION
We aim to find subset S of clients whose aggregated gradient can approximate the full aggregation over all the N clients V = [N]. To formulate this problem, we start by following the logic in Mirzasoleiman et al. (2020). Given subset S, we define mapping : V - S such that the gradient information V (fa(+*) from client k is approximated by the gradient information from a selected client okk E S. For i E S, let C. _ {k E Vl((k)- = i} be the set of clients approximated by client-i and 7/4 A [aal. The full aggregated gradient can be written as
(b*)
Σ KE[N]
VFL( - VF VV (D))) + + VF*
(2)
KE[N] Subtracting the second term from both sides, taking the norms, and applying triangular inequality, we can obtain an upper bound for the approximation the aggregated gradient by S, i...
kES
VFa(1*) - Σ V
VFL(D") - VFOL)(00((3)]]
(3)
KEIN]
RES
kE[N]
3

---

Published as a conference paper at ICLR 2022
The above inequality holds for any feasible mapping a since the left hand side does not depend So we can take the minimum of the right-hand side w.n.. olk), Ak E [M],
Σ VF((U*) REIN]
Σ TA VV RES
Σ NE
min ES
-VE())) G(())
(4)
The right hand side provides a relaxed objective G(S) for minimizing the approximation error on the left hand. Minimizing ((S) (or maximizing G. a constant minus its negation) equals maximizing a well-known submodular function, i.c., the facility location function (Cornuéjols et al.. 1977). To restrict the communication cost, we usually limit the number of selected clients to be no greater than K, i.e., |S| & K. This resorts to a submodular maximization problem under cardinality constraint, which is NP-hard but approximation solution with 1 e- bound be achieved via the greedy algorithm (Nemhauser et al., 1978).
3.2 GREEDY SELECTION OF CLIENTS
The naïve greedy algorithm for minimizing the upper bound of gradient approximation starts from S < 0, and adds one client k E V with the greatest marginal gain to S in every step. i.e.,
S - SUk,, h² E argmax(((()) kEVis
G(()) US]
(5)
until | K. Although it requires evaluating the marginal gain for all clients V in every step, there exists several practical accelerated algorithms (Minoux, 1978; Mirzasoleiman et al., 2015) to substantially reduce the number of clients participating in the evaluation. For example, stochastic greedy algorithm (Mirzasoleiman et al., 2015) selects client k* from small random subset of V\S with size in each step, i.e.,
S SUk, K"
argmax k-Grand( VV5, sizems)
(G(S) ((())-((()UUS))))
(6)
To incorporate the client selection into any federated learning algorithm, we apply the stochastic greedy algorithm in each aggregation round and perform selection only from a random subset of active clients in the network. The complete procedure is given in Algorithm assuming the base algorithm is Federated Averaging (FedAvg) (McMahan et al., 2017).
On the left-hand side of Eq. (3)-(4) we aim at approximating the full communication by weighted sum over selected clients in
Algorithm 1 DivFL
Input: T, E, m,,
with weights {1x hes. However, since relax the problem minimizing its up- per bound and the (stochastic) greedy solu-
1 for t = -,....,. T do
Server selects subset of K active clients Se using the stochastic greedy algorithm in Eq. (6), and sends w, to them.
tion is not guaranteed to achieve the global minimum of the relaxed objective, the weight associated with the greedy solution S, i... = [Cal with C. = {K Vli E arg minjes ( (F)()')))) is sub-optimal. In fact, given S, the optimal weight hes can be achieved by directly minimizing the left hand side of Eq. (3)-(4) but it is infeasible because the full aggre- gation ΣLENN F&& is not available our setting. Though there might exist bet- ter choices, we find that simple uniform weights work promisingly in all evaluated scenarios of our experiments. The stochas- tie greedy selection in line 2 of Algorithm
for device l: E S, in parallel do
w <- Wtt
Solve the local sub-problem of client-k inex-
actly by updating wh for E local mini-batch
SGD steps:
w 17 VF.(((
Send A w we back to Server
end Server aggregates {A/}:
Σ A
Wt+1 f- We +
S.
end 10 return WT
RES.
requires access to the gradients from all clients, which might be expensive in communication costs. In practice, we may take several approaches to minimize the communication costs. One is to receive periodic gradient updates from all clients every communication rounds. Another is to only the
4

---

Published as a conference paper at ICLR 2022
gradients from the selected clients at the current round update part of the N x N dissimilarity trix. In our evaluation, we take the latter method with "no-overheads". While this maybe suboptimal since large part of the dissimilarity matrix will contain stale gradients, we observe significant loss in performance in our empirical studies.
4 CONVERGENCE ANALYSIS
In this section, we provide theoretical analyses of the convergence behavior of Algorithm for strongly convex problems under practical assumptions of non-identically distributed data, partial device participation, and local updating. While the current analysis only holds for the proposed client selection algorithm applied to FedAvg, methods as well.
be naturally extended other federated optimization
As discussed in Section 1, draw connections between full gradient approximation and submodu- lar function maximization. By solving a submodular maximization problem in the client selection procedure, we effectively guarantee that the approximation error is small (see Eq. (4)). We state an assumption on this below.
Assumption (Gradient approximation error). At each communication round t, we assume the server selects set St of devices such that their aggregated gradients (with weights {Ty JeS,,) is good approximation of the full gradients on all devices with error i.e.,
Σ TA VFF() KES.
1 Σ VF((U)) N RE(N]
Se.
The same assumption has been studied in previous works on coreset selection for mini-batch SGD (Mirzasoleiman et al., 2020, Theorem 1). Note that e used measure characterize how good the approximation is and our theorem holds for any e < c0. Our algorithm (Algorithm 1) is effectively minimizing an upper bound of c to achieve a potentially small value via running submod- ular maximization to select diverse clients (Eq. (4)). Next, we state other assumptions used in our proof, which are standard the federated optimization literature (e.g., Li al., 2019).
Assumption 2. Each Fk (k [N] is L-smooth.
Assumption 3. Each FR (k E [N] is p-strongly convex.
Assumption 4. For l E [N] and all 1,, in-device variance of stochastic gradients on random samples Ç are bounded, i.e., [E[[] FillFF - <) FF&(w)))
o².
Assumption 5. For le [N] and all t. the stochastic gradients random samples Ç are uniformly bounded, i.e. [V C) G?.
Assumption (Bounded heterogeneity). Statistical heterogeneity defined as F - -KE(N P&Ft is bounded by C, where F = min (w) and Fý = min, (x)
Let w" arg ming fw) and oi arg min, Pu(u)) for k [N]. In our analysis, need to bound another variant of heterogeneity |[ P& - w*1 in the parameter space. Note that under Assumption 3 (p-strongly convexity), Assumption 6 implies that EKE[N] Padt bounded by constant.
w'Il is also
Setup. Following Li al. (2019), we flatten local SGD iterations at each communication round, and index gradient evaluation steps with (slightly abusing notation). We define virtual sequences {vf hEe[N] and {wf ]EE[N] where
o if not aggregate, select S and average (utt)RES, 13 otherwise.
1 3 n (F, wit
=seteer
While all devices virtually participate in the updates of } at each virtual iteration t, the effective updating rule of {wot } the same as that in Algorithm 1. Further, 5, := Σke(M] paotf w. ==
ExE[N] pk Therefore, w.
Vz
if not aggregate, The goal of defining T, and w. Exes, of otherwise.
1
K
5

---

Published as a conference paper at ICLR 2022
to relate the updates of 8s mini-batch SGD-style updates, and relate the actual updates of w, to those of Vy. We aim at approximating Ut-1 by We+1 (when aggregating) and next state a main lemma bounding || 1-
Lemma 1. For any virtual iteration under Algorithm and Assumptions 1-6, have
|0++11 - Ue+ill S LGE(E - 1) + EERtto
where is the smoothness parameter, G is the bounded stochastic gradient parameter, E is the number of local iterations, and T/oo is indexing the latest communication round.
We defer the proof to Appendix A. The main step involves using Assumption 1 bound the approximate error of gradients and relating accumulative gradients with model updates. With Lemma 1, we state our convergence results as follows.
Theorem (Convergence of Algorithm 1). Under Assumptions 1-6, we have
E[ll"" - w & O(1/t)++10))
The non-vanishing term e encodes the gradient approximation error (Assumption 1), and will become zero when select all clients each round (i.e., K N). In experiments, we observe that DivFL allows us to achieve faster convergence (empirically) at the cost of additional solution bias (a non-diminishing term dependent on e).
We provide a sketch of the proof here and defer complete analysis to Appendix A. Examine the distances between W[+1 and w²
|| w 1 || - "1+1ll 1 || - w=112 + 2(w - P4+1,00+1 =²)
If iteration is not an aggregation step, W U2+1 and || w" 1| || w011
which we can bound with Lemma Li al. (2019):
E E[| w" 1 $ (1 m w" 11 nBB
for some constant B. If is an aggregation step, we need to bound
F || + [[[| w" || 2IE Ue+ Jc+1 w²)l.
The second term can be bounded by Eq. (7), which contains (1 nP))El| [1] Therefore, combined with Lemma 1, with decaying step size, can obtain a recursion on El] T w ||
which leads to Theorem 1. We provide the complete proof in Appendix A.
EXPERIMENTS
Setup. We evaluate the DivFL approach utilizing both synthetic and real federated datasets from the LEAF federated learning benchmark (Caldas et al., 2019). The synthetic dataset enables us control the data heterogeneity across clients for evaluation. We consider two baselines to compare our DivFL against: a) random sampling without replacement, and b) the power-of-choice approach (Cho et al., 2020) where clients with the largest training losses are selected. For Di DivFL, we consider an ideal setting where 1-step gradients are queried from every device in the network for each global round. In addition, we also evaluate the "no overhead" setting where (a) client updates from previous rounds are utilized to update part of the dissimilarity matrix, and (b) we run the stochastic greedy algorithm to avoid selecting from an entire set of clients. While the former provides the upper bound on the performance, the "no overhead" approach and other variants are more suited to realistic settings. For all the methods, we fix the number of clients per round K 10 and report the performance for other choices of K in Appendix. Each selected client performs sharing the updates with the server unless otherwise noted. We report the performance of DivFL across metrics including convergence, fairness and learning efficiency. We further report the impact of the subset size K these metrics. Our code is publicly available at github.
round of local model update before

---

Published as a conference paper at ICLR 2022
5.1 RESULTS ON THE SYNTHETIC DATASET
We generate syntheric data following the setup described in Li et al. (2020). The parameters and data are generated from Gaussian distributions and the model is logistic regression. y = arg max(ssoftmax( [ W + b)). We consider total of 30 clients where the local dataset sizes for each client follow the power law. We set the mini batch-size to 10 and learning rate = 0.01. We report training loss as well as the mean and variance of test accuracies versus the number of communication rounds in Figure for the synthetic IID setting. We observe three key benefits of DivPL compared to random sampling and power-of-choic approaches. On the one hand, Di VFL achieves significant convergence speedup (~10x faster) to reach the same loss and accuracy relative to random sampling and power-of-choice. The convergence speed could potentially be attributed to the reduction in the variance of updates across epochs DivFL aims minimize the gradient approximation error w.r.t the true gradient. Furthermore, DivFL also achieves the lowest loss and highest accuracy among the client selection approaches. By reaching lower variance of accuracy in comparison to the baselines, DivFL also shows marginal improvement in faimess, even when the data distribution is IID.
As one would expect, while being impractical, utilizing the gradient computation from all clients to update the dissimilarity matrix provides an upper bound on the achievable performance. Our "no overhead" approach to update the dissimilarity matrix partially from only the participating clients still outperforms the baselines in the test accuracy and training loss, while preserving the faster convergence of L.. In Appendix B.I, we report the above metrics for different choices of K.
Now ooteeeii
Niverohcuaaa (erl hncoveheed)
Figure 1: Training loss, mean and variance of test accuracies of DivEL compared with random sampling and power-of-choice on the synthetic IID data. For DivFL (no overhead), we utilize only the gradients from clients participating in the previous round. We see that Di DIL achieves faster convergence and converges to more accurate and slightly more fair solutions than all baselines.
We report the training loss as well as the mean and variance of testing accuracies for the synthetic non-IID dataset in Figure 2. We notice the noisy updates of the random sampling approach and slightly less noisy ones of the power-of-choice approach. In addition, both the baselines converge to a less optimal solution than DivFL. The mean accuracy gains of Di vFI. are quite significant (10% points). In terms of convergence, power-of-choice approach converges in 2x fewer rounds than random sampling to reach an accuracy of 70% but DivFL converges in 5z fewer rounds with less noisy updates than both baselines. The fairness gains of DivFL for the non-IID setting is more significant. This is due the higher degree of heterogeneity in client updates and the ability of DivFL to find diverse representative clients in the update space. In Appendix B.I, we provide more ablation studies for different choices of the hyperparameter K.
Kangting
Aandoy Seriiing Dartt (sire)
Figure 2: Training loss and test accuracy of DivFL compared with random sampling and power-of-choice on synthetic non-IID data. DivFL L converges faster and to more accurate solutions and much improved fairness than all baselines.
7

---

Published as a conference paper at ICLR 2022
5.2 RESULTS ON REAL DATASETS
We present extensive results on the robustness of DivFL on LEAF federated learning datasets. This includes image datasets (FEMNIST, CelebA) and language dataset (Shakespeare). For each of these cases, we report the convergence behavior and fairness performance of Di Di..
For FEMNIST, there are a total of 500 clients where each client contains out of 10 lowercase hand- written characters. Clients use CNN-based 10-class classifier model with two 5x5-convolutional and 2x2-maxpooling (with a stride of 2) layers followed by a dense layer with 128 activations. For our experiments, CelebA contains 515 clients where each client is celebrity and CNN- binary classifier is utilized with 4 covooluavllli and 2x2-maxe ma2pooiin layers followed by dense layer. For Shakexpeare, two-layer LSTM classifier containing 100 hidden units with an 8D embedding layer utilized. The task next-character prediction with 80 classes of characters in total. There are total of 109 clients. The model takes imput sequence of 80 characters, embeds the characters into a learned 8-dimensional space and outputs one character per training sample after 2 LSTM layers and densely-connecter layer. For the Shakespeare case, each client performs 5 local updates in every global round. For the other two datasets, client updates are shared after only local update.
5.2.1 CONVERGENCE BEHAVIOR
We first present the convergence behavior of DivFL in comparison to the baselines for the above 3 datasets in Figure 3. On FEMNIST, DivFL converges faster than both random sampling and power-of-choice approaches also with less noisy updates. DivFL with "no overhead" performs as well as the ideal case. We note that in the case of FEMNIST, there are several clients that have similar distribution over class labels. DivFL. can be crucial in such cases where redundancies can be minimized and diversity encouraged by maximizing a submodular function.
On CelebA, DivFL has a faster convergence than both baselines in the ideal setting. However, the "no overhead" setting converges at the same rate as random sampling followed by the power- of-choice approach. In the case of Shakespeare, interestingly. both DivEL and power-of-choice approaches converge at the same rate and faster than random sampling (by 6x). Overall, for CelebA and Shakespeare datasets, we note that Di DivFL either converges at least at the same rate as the fastest baseline.
140
c.0
Fom
Samping
Aumrr Chice boed
Figure 3: Training loss and test accuracy of DivFL compared with random sampling and power-of-choice on real datasets. We observe clear improvement for Div2L on FEMNIST. For the other two datasets, the ceapuuuiiiaiionffffiieeee DivFL "no-overhead" converges at the same rate as the fastest baseline.
5.2.2 FAIRNESS
We also compare the fairness performance of the different approaches for the above 3 real datasets in Figure 4. We measure this through the variance of test accuracies vs training rounds and observe both the trajectory as well as the final variance of the test accuracies. For the image datasets FEMNIST and CelebA, it's clear that DivFL has better fairness after convergence with superior mean accuracy and better/comparable variance of accuracies. This shows that diversity helps result in a more uniform performance across clients. Interestingly for the case of Shakespeare, we observe the variance of
8

---

Published as a conference paper at ICLR 2022
accuracies for DivFL, especially under the "no overhead" setting is larger than both baselines. This could possibly be the result of the sparsity in the gradient updates for language models, in general. While the random sampling approach has lower accuracy variance, the mean accuracies are also lower showing that it not necessarily more "fair".
Pedepuue temeee Co.
Pore Crince
Pule of
Figure 4: Variance of test accuracies over the 3 real datasets shows that DivFl has fairness benefits on the image datasets. Poorer fairness performance for Shakespeare could be attributed to the sparsity in the gradient updates for language models.
5.2.3 IMPACT OF K AND LEARNING EFFICIENCY
We also empirically evaluate how the choice of number of clients per round (K) affects the final model performance. We take the case of CelebA dataset and observe the (smoothened) mean and variance of final test accuracies after 400 rounds for different choices of K. The final mean test accuracy generally increases and then decreases for random sampling showing that more participation has the potential to improve the final model performance but not always due to potential risk of overfitting. We also note that for D DivFL, the test accuracy improves as K grows to 30, but does not fall off as steeply as in the case of random sampling. On the one hand, this highlights the robustness of D DivFL. On the other hand, DivFL L achieves the highest mean accuracy of about 0.79 for K 30. This shows considerably fewer client participation in comparison to K 60 for random sampling and = 80 for power-of-choie of-choice achieve their respective highest test accuracies. This reveals that Di DivFL offers improved learning efficiency by its ability to learn from fewer clients per round compared to the baselines. It must also be noted that D vFL outperforms both baselines in final mean and variance of test accuracies for all choices of K in Figure 5.
Celeba
Celetà
6.75 g6.200
Rower Cheic
6,000
Rfwer Chein ONE ExerReed
6675
2 6.000
Z6070
5.00
6.25
Nurber
Clients per (R)
Figure 5: Final Testing Accuracies (smoothened) after 400 epochs CelebA dataset shows the power of Di vFL to have robust learning beating baselines for all choices of K. Furthermore, DivFL. achieve the highest test accuracy and lowest variance using the smallest number of clients per round in comparison to baselines.
6 CONCLUSION
In this paper, we posed the problem of selecting the most diverse subset clients for federated learning as the solution to maximizing submodular facility location function defined over gradient space. To this end, we developed DivEL and provided a thorough analysis of its convergence in heterogeneous settings. Through extensive empirical results both synthetic and real datasets, we demonstrated strong gains of DivFL over state-off toite--f-the-ate art baseline client selection strategies across key metrics including convergence speed, faimess, and learning efficiency. Furthermore, communication-efii -fffeciiinnnnnnnnnttt variant of DivFL holds all these advantages while making them amenable practical federated learning systems.

---

Published as a conference paper at ICLR 2022
7 ETHICS AND REPRODUCIBILITY STATEMENT
Our algorithm to select the most diverse set of clients not only aims to speed up learning but can also allow for fair representation of clients in the training process. This issue has been identified as a key challenge in federated learning in several studies and algorithms exist that specifically address this concern. In our paper, our approach unique addressing client diversity (without any additional knowledge of client data) by encouraging diversity in the gradient space with (near) optimality guarantees through the optimization framework.
In order to make our paper reproducible, we provide a detailed proof of Theorem 1 in Appendix A. Further, detailed experimental description including 1) data preparation, 2) model architecture, 3) training algorithm and
are provided in Section 5 and Appendix B.
ACKNOWLEDGEMENTS
This work was supported in part by the CONIX Research Center, one of six centers in JUMP, Semiconductor Research Corporation (SRC) program sponsored by DARPA.
10

---

Published as a conference paper at ICLR 2022
REFERENCES
Ravikumar Balakrishnan, Mustafa Akdeniz, Sagar Dhakal, and Nageen Himayat. Resource man- agement and fairness for federated learning over wireless edge networks. In 2020 IEEE 2 International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pp. 1-5, 2020. doi:
Dhruv Batra, Payman Yadollahpour, Abner Guzzman-Rivery and Gregory Shakhnarovich. Diverse m-best solutions in markov random fields. ECCV, pp. 1-16, 2012.
Jeffrey A. Bilmes and Wenruo Bai. Deep submodular functions. CoRR, abs/ (ttp//701.0999, 2017. URL http:///txxa .weesiiiorrr.eeooooe abs /1701. 08939.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar, Leaf: benchmark for federated settings, 2019.
Wenlin Chen, Samuel Horvath, and Peter Richtarik. Optimal client sampling for federated learning, 2020.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection in federated learning: Convergence analysis and power-of-choice selection strategies, 2020.
Michele Conforti and Gerard Cornuejols. Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discrete Applied Mathematics, 7(3):251-274, 1984.
G. Cornuéjoss, M. Fisher, and G.L. Nemhauser. On the uncapacitated location problem. Annals of Discrete Mathematics, 1:163-177, 1977.
Don Kurian Dennis, Tian Li, and Virginia Smith. Heterogencity for the win: One-shot federated clustering. arXiv preprint arXiv:2103.0063) 2021.
Satoru Fujishige. Submodular finctitoon and optimization. Annals of discrete mathematics. Elsevier, 2005.
Jennifer Gillenwater, Alex Kulesza, and Ben Taskar. Near-optimal map inference for determinantal point processes. In NeurlPS, pp. 2735-2743, 2012.
Andrew Guillory and Jeff Bilmes. Active semi-supervised learning using submodular functions. In Uncertainty in Artificial Intelligence (UAI), Barcelona, Spain, July 201 1. AUAI.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang, Fairness without demographics in repeated loss minimization. In International Conference on Machine Learning, 2018.
Tiansheng Huang, Weiwei Lin, Li Shen, Keqin Li, and Albert Y. Zomaya. Stochastic client selection for federated learning with volatile clients, 2021.
Rishabh Iyer, Stefanie Jegelka, and Jeff A. Bilmes. Fast semidifferentiall-uss submodular function optimization. In ICML, 2013.
Fan Lai, Xiangfeng Zhu, Harsha V Madhyastha, and Mosharaf Chowdhury. Oort: Efficient federated learning via guided participant selection. arxiv. org/abs/2010.06081, 2020.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2020.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. arXiv preprint 1907v01907.002 2019.
Hui Lin and Jeff Bilmes. class of submodular functions for document summarization. ACL, pp. 510-520, 2011.
11

---

Published as a conference paper at ICLR 2022
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication Cinmuuniaaton-EEfiiientt Learning of Deep Networks from Decentralized Data. In International Conference Artificial Intelligence and Statistics, 2017.
Michel Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Opti- mization Techniques, volume of Lecture Notes in Control and Information Sciences, chapter 27, pp. 234-243. Springer Berlin Heidelberg, 1978.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pp. 1812-1818, 2015.
Baharan Mirzasolciman, Jeff Bilmes, and Jure Leskovee. Coresets for data-efficient training of machine learning models. In International Conference Machine Learning. 2020.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- tional Conference on Machine Learning, 2019.
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular functions. Mathematical Programming. 14(1):265-294 1978.
Takayuki Nishio and Ryo Yonetani. Client selection for federated learning with heterogeneous resources in mobile edge. In ICC 2019-2019 IEEE International Conference on Communications, 2019.
Adarsh Prasad, Stefanie Jegelka, and Dhruv Batra. Submodular meets structured: Finding diverse subsets in exponentially-large structured item sets. In NeurlPS, pp. 2645-2653, 2014.
Monica Ribero and Haris Vikalo. Communication--ffiiienn federated learning via optimal client sampling. arXiv preprint arXiv:2007.15197, 2020.
Shengjie Wang, Wenruo Bai, Chandrashekhar Lavania, and Jeff Bilmes. Fixing mini-batch sequences with hierarchical robust partitioning. In Proceedings the Eventy-Secone International Conference on Artificial Intelligence and Statistics, volume 89, pp. 3352-3361, 2019.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Fast multi-stage submodular maximization. In ICML, 2014.
Dong Yin, Ashwin Pananjady, Max Lam, Dimitris Papailiopoulos, Kannan Ramchandran, and Peter Bartlett. Gradient diversity: a key ingredient for scalable distributed learning. In International Conference on Artificial Intelligence and Statistics, 2018.
Tianyi Zhou and Jeff Bilmes. Minimax curriculum learning: Machine teaching with desirable difficulties and scheduled diversity. In ICLR, 2018.
APPENDIX
A COMPLETE CONVERGENCE ANALYSIS
Below shows the convergence analysis. Many steps make a distinction between if we are doing an aggregating steps (from the clients to the server), not (when the clients do not communicate). We assume that we aggregate every E time steps. Define virtual sequences {1² ke(N]] and (wt) ke[N] where for all [N].
ut w - - VF
(8)
not aggregating,
w ++ sample S:-1 and average (ot Pres
(9)
otherwise.
12

---

Published as a conference paper at ICLR 2022
Let
Σ
(10)
KEIN]
W1 =
Σ
Pk
(11)
NE[N]
where pk 2 is is the given weight of the htth client and w.l.o.g., we assume Σ Pk- = 1. Therefore,
02 wt
if not aggregating, ie., when t o LE for some integer otherwise.
(12)
Eles uf
R
Let
:= = E (eF KE(N]
(13)
and
0t-1 = W4 1
Σ RE(N]
Ph P&FF(
we - -119t-
(14)
We have
[e+1 ==11
|10111 Uet1 Det1 w"1l
(15)
10+++1 Uc+1 2|2 |u++1 - w01l 2|2 + 2( 1441, 1241 w")
(16)
If not aggregating,
Te+1 U2+1-
(17)
Hence
W++1 w²11== -1|Tr+1 - ==112
(18)
Using Lemma in Li al. (2019), we know [[[ w" [|3] S (1 (1-ma)EE[ w" w0|l3]
holds for some constant B. we are aggregating, we need to bound
|[] W || B[[| - w11 + [
Ue+1, Ut+1 w²)
(19)
Let the last time of aggregation happens step to = + E, when we select subset (associated with weights (Yk hees) using the greedy algorithm. Let De be the updates on w at the 7-th iteration,
ie., Auf u of. Then U
We, + 1/4 ENE(N) Σt= Auf. To bound the first term above,
1e+1 Tet1l1
Wt
+
Σ RES
Tto
A
(20)
N
N
T=to
RE
r=ta
Th
Au
Σ
Aut
(21)
N
N
KES
KE(N
Σ
AVA
(22)
N
N
==
RES
KE[N]
Similar to the CRAIG paper (Mirzasoleiman et al., 2020), we assume that the subset selected in step to = f + 1 - E provides an approximation of the full gradient such that
1
Σ (F.
Σ VEL(UE))) RE[N]
Sc.
(23)
N
N
KES
13

---

Published as a conference paper at ICLR 2022
For every local step (fo, t). we use the same S to approximate the full gradient because we only communicate the local gradients every E local steps. To bound the gradient approximation at step using the stale S, we have
1
7A VLL(())
1 E ( N
Σ KES
74 VEL())
E KES
Th
+
KES
kE[N]
(24)
1 E
Th (
+
N
RES
KEIN]
(25)
1 Σ
(26)
N
N
KEIN
KEIN]
S 2TG
Σ
Tl +
(27)
where the first and the third term the right hand side are bounded using the L-smoothness of (+)() and G-bounded norm of its stochastic gradient. Hence, we can continue to bound the first term in Eq. (22) by
|| - ut41l
S
7k Av
1 N
A kE(N
Σ
(28)
N
T=t0
KES
1
1 Σ (ta(t+)
Σ T/r
Σ
7h V(((())
(29)
N
N
to
KES
KE[N]
<21G
Σ Th + Eenr
(30)
< LGF(EF 1)T + EEMO
(31)
2 t t + (E-1)
E-
)²
E 1
AGGEEE11
1+
me Ec 1+
t t+ - (E - 1)
(32)
where the number of local steps between two communication (aggregation) rounds. Therefore, Eq. (19) can be bounded as follows:
E Wee1 31
(33)
<B]|wr4 Ve41 1|]] + E[[ - w0 2
U,41, - w')]
(34)
< (LGE(E- - 1)mio + E + [[1 mP) w0 w01 + + (LGE(E- - 1)mi + EEnt))
E||lE4+1 w"ll
(35)
<(1 mu)BillT, w0 1 + EEpTRo + |LGE(E 1)g (LGE(E- - 1)Mes + EE)?] n/
Bud
(36)
<(1 nn)Bill w01 EpEm + (LGEM, + +c) E + Bni
(37)
14

---

Published as a conference paper at ICLR 2022
where 7/2 zty.
B
noo
1-E-1-7
8
and [[[
w=
I p. shown as follows.
w01
S E
Σ
P.u
+ E
Σ
Prug
w²
(38)
iE[N]
KE[N]
SB
D
Σ
p.u
+M
(39)
Blpps
B
(7. ++
0,)1 +
M
(40)
VE[N]
Pi E [[i(v())]
(41)
NE(N] 1
+ Msp.
(42)
The final convergence rates follows from Lemma 3 in Mirzasoleiman et al. (2020).
B ADDITIONAL EXPERIMENTS
B.1 MORE ABLATION STUDIES ON SYNTHETIC AND FEMNIST DATASETS
We present more findings from training DivFL on synthetic IID and non-IID dataset for K = 20 in Figure 6, 7 and 8. In addition to the training loss, mean and variance of test accuracies, also plot the 10th percentile test accuracy that shows the worst-case performance of the different client selection strategies. As in the case of K 10, we observe gains across convergence, faimess and improved model accuracy for Di LL. In addition, the 10th percentile accuracy further confirms that DivFL improves the worst-case clients' accuracies.
Surs Cleeet
San Cetteee
Tenangichaic
Difiiine
30
310
350
153
150
21c 300
S4mh Seletie Clett K
Jun of Clenk
Randor Samsiing
3030
2000
Rankir
Nee po-1 1u0 parencedd
Figure 6: We measure the training loss, mean and variance of test accuracies as well as 10th percentile test accuracy for Di on synthetic IID dataset for K = 20.
B.2 IMPACT OF NUMBER OF LOCAL EPOCIS
In our experiments, we already adopted local updating schemes with fixed number of local epochs (r) being 1 (running multiple local iterations). However, we further show the robustness of DivFL under different choices of 7 via observing the training loss and variance of test accuracies. The results for Synthetic IID, non-III and FEMNIST are presented in Figure 9, 10, 11, 12, 13 for different values of r. We observe that for different choices of the number of clients K and the number of local epochs
15

---

Published as a conference paper at ICLR 2022
Random Cempling
Fonenaichulos DM 74d
bounce
Pounde
Ramh Seleccad Chertt 20
tuin Sesecceed Ciraa
tove-ckches Hut koul
Bandor Synding
[M. Jaet
Figure 7: The training loss, mean and variance of test accuracies as well 10th percentile test accuracy for DivFL on synthetic non-IID dataset for K 20.
Nans Selecas Gata
Ram, d'Slccas Chana
Delt lood
Samplig D.rk loab
Tanson Sumpling
Jone OWN sentes)
Simpding
Dlafk th anothadd)
Figure 8: Training loss, mean and variance test accuracies as well as 10th percentile test accuracy for DivFL on FEMNIST dataset for K 20.
T, both variants of DivFL converge faster than both the baselines. The fairness gains over random sampling are also preserved under large values of shown in Figure 13.
16

---

Published as a conference paper at ICLR 2022
K 10, Local epochs =5
K 10, Local epochs T =10
2.25
Random Sampling
Random Sampling
8 2.00
Power-of-Choice
Training Loss
2.0
Power-of-Choice DivFL (ideal) DivFL (no overhead)
1.75
11.50
DivFL (ideal)
1.25
DivFL (no overhead)
1.0
0.75
0.50
50
100
150
200
250
300
50
100
200 250 300 Rounds
150
Rounds
K 20,
Local epochs =5 Random Sampling Power-of-Choice
K= 20,
Local epochs =10 Random Sampling Power-of-Chooe DivFL (ideal)
2.00
Training Loss
2.0
1.75
e1.50
DivFL (ideal)
1.25
DivFL (no overhead)
DivFL (no overhead)
1.00
1.0
0.50
0.25
0
50
100
150
200
250
300
0
50
100
250 300 # Rounds
150
200
Rounds
Figure Training Loss on Synthetic IID for different choices of т.
10, Local epochs T
10, Local epochs
Accuracy Variance
Random Sampling
Variance
Random Sampling
0.030
Power-of-Choice
Power-of-Choice
0.025
DivFL (ideal)
0.025
DivFL (ideal)
0.020
DivFL (no overhead)
0.000
DivFL (no overhead)
0.015
0.010
0.010
0.005
50
100
200 250 Rounds
150
300
100
150
200
250
300
# Rounds
20,
Local epochs
20, Local epochs =10
Accuracy Variance
00.03
Random Sampling
Jarlance
0.035
Random Sampling Power-of-Choice DivFL (ideal)
0.030
Power-of-Choice
0.030
0.025
DivFL (ideal)
0.025
9.020
DivFL (no overhead)
0.002
DivFL (no overhead)
0.015
0.015
0.010
0.010
0.005
150 Rounds
250 300
100
200 Rounds
Figure 10: Variance of Test Accuracy on Synthetic IID
K = 10, Local epochs =
K 10, Local epochs =00
3.0
Random Sampling
Random Sampling Power-of-Choice DivFL (ideal)
2.5
Power-of-Choice
2.5
02.00
Trainine
DivFL (ideal)
2.0
DivFL (no overhead)
DivFL (no overhead)
1.5
1.5
1.0
0.5
0.5
50
100
150
200
250
300
50
100
150
200
250
300
Rounds
K = 20,
Local epochs =5
K
20,
Local epochs =10 Random Sampling Power-of-Choice DivFL (ideal)
3.0
Random Sampling
Treining Loss
2.55
Power-of-Choice
2.5
92.0
DivFL (ideal)
22.0
DivFL overhead)
DivFL (no overhead)
1.5
1.0
50
100
150
200
250
300
50
100
150 Rounds
200
250
300
Rounds
Figure 11: Training Loss on Synthetic non-IID for different choices of т.
17

---

Published as a conference paper at ICLR 2022
epachs
epochs I
Random Sampling
Random Sampling
0.14
Power-of-Choice
0.14
Power-of-Choice
0.12
0.110
DivFL (ideal)
DivFL (ideal)
Accurac
60.08
DivFL (no overhead)
0.08
DivFL (no overhead)
0.06
TU
0.06
0.04
0.04
0.02
0.02
50
100
150
200 250
300
100 150 200 250 Rounds
# Rounds
Local epochs =5
20, Local epochs
Accuracy Varianye
0.16
0.14
Random Sampling Power-of-Chaice
Ce Variank
0.16
0.14
Random Sampling Power-of-Choice DivFL (ideal) DivFL (no overhead)
0.12
0.12
DivFL (ideal)
0.00
20.08
DivFL (no overhead)
7.008
0.10
0.06
0.06
0.04
0.04
0.02
100
200 # Rounds
150
250 300
100
200 Rounds
150
250 300
Figure 12: Variance of Test Accuracy Synthetic non-lID
Locd spects
K= Local saccho
Random Samp Ing
Poweroll Choice
DiuF: tho oxothedd
<= Local epects +5
Random Sampling
Power-of Chaiie tne overtead
AcCteney Vettane Umromeeeee
8.03
0.04
0.02
Bounds
Figure 13: Faster convergence benefits of DivFL over Random Sampling and Power-of-Choike approaches is preserved even when clients multiple local epochs before sharing model updates.
18


Reviews:
[{"review_id": "wctYIQDirMx", "reviewer": "Reviewer_CFhn", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n\n- 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. \n- 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.\n- With some reasonable assumptions, the convergence analysis for the proposed approach is provided.\n\n### Weaknesses\nAlthough 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.\n\nSpecifically, 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).\n\n### Minor comments\n- The text size of the plot labels and ticks should be a bit larger.\n- The left margin of Algorithm 1 needs to be a bit larger.", "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.", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "vKVAWt3UHzD", "reviewer": "Reviewer_KjQr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nTheoretical and empirical results are significant.", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "uWBrGT_NLw2", "reviewer": "Reviewer_2aPT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nMain questions:\n-\tI 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? \n-\tAssumption 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?\n-\tThe authors focus on the full communication case, can this approach be adapted to the partial case?\n-\tExperiments: 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.\n\nMinor comments:\n-\tAssumption 4 and 5 are for all t? \n-\tPage 5: in the definition of $\\overline{v}_t$, it is $v^k_t$.\n-\tThe 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.\n-\tAppendix: $g_t$ and $\\Delta v^k_t$ are not defined.\n\n", "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.\n\n\n[1] Ryan Gomes and Andreas Krause. Budgeted Nonparametric Learning from Data Streams, 2015.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "qo5EzGfECdw", "reviewer": "Reviewer_RXZV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "page 4: Minimizing G(S) is certainly equivalent to maximizing \\bar{G}. However, the equivalence\nbreaks down when you consider approximation. In particular, the (1-1/e) approximation to \\bar{G}\ndoes not imply a similar approximation to G(S), in general\n\nEnd of section 3: the greedy step is not clearly explained and needs more discussion, since it will\naffect the communication complexity. It is mentioned that the algorithm only utilizes\n\"updates from the clients that participated in the previous round\", and it is claimed that this works\nquite well. This is pretty surprising. Is there some special structure in the instance due\nto which this holds?\n\nAssumption 1: this is a property of the algorithm. So I don't understand why this is an assumption.\nYou need to prove that for the sets S_t chosen in each step t, this property will hold. The authors\nclaim that this assumption is also made in (Mirzasoleiman et al., 2020). They should say more clearly\nwhere that is (though an assumption in a prior paper doesn't automatically make it correct).\n\nIn view of the issue with assumption 1, it is not clear if Theorem 1 is correct\n\nThe formulation in the paper has a lot of similarity with the setup in (Mirzasoleiman et al., 2020).\nThe authors should explain this more carefully, instead of cursorily stating it in the Introduction", "summary_of_the_paper": "The paper studies a problem of improving the efficiency of federated learning by selecting a\nsubset of clients whose gradients are representative. This is formulated as a submodular maximization\nproblem, and the authors analyze a greedy algorithm for it. This is evaluated through experiments\non synthetic as well as real datasets.", "summary_of_the_review": "The problem considered in the paper is interesting and well motivated. However, the formulation is\nincremental, and builds quite heavily on earlier paper. The main contribution is the analysis of the\ngreedy algorithm, which has serious issues as mentioned above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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)