Year: 2021

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.

heading: 1 INTRODUCTION
text: Federated learning (FL) involves collaboratively training of machine learning model across a 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 serves 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 can 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 to the server is a waste of communication and computational resources. How best to select a representative and more informative client set while adhering to practical constraints in federated learning is still an open challenge. Although several selection criterion have been investigated in recent literature, e.g., sampling clients with probabilities proportional to their local dataset size (McMahan et al., 2017), sampling clients of larger update norm with higher probability (Chen et al., 2020), and selecting clients with higher losses (Balakrishnan et al., 2020; Cho et al., 2020), the redundancy and similarity of the clients’ updates sent to 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 are too similar to each other. The commonly studied modular score/probability for each individual client is incapable of capturing information as a property over a group of clients. Ideally, a diverse set of clients would be selected, thereby increasing the impact of under-represented clients that contribute different information, and thereby improving fairness. This, in fact, is a topic of increasing interest (Mohri et al., 2019; Cho et al., 2020; Dennis 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 (Mirzasoleiman et al., 2020), we derive an upper bound of the approximation error as a 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., 2014) on a complement submodular function to (approximately) minimize the error upper bound. We employ the greedy selection (Nemhauser et al., 1978) of a subset of clients according to the marginal gain of the submodular function to achieve a solution with provable approximation guarantee (Conforti & Cornuejols, 1984). By integrating the diverse client selection into the most commonly studied FL scheme, i.e., Federated Averaging (FedAvg) (McMahan et al., 2017), we propose DivFL that applies global model aggregation over a selected subset of clients after multiple local steps on every client. We present theoretical convergence analysis of DivFL and show its tolerance to the heterogeneity of data distributions across clients and large number 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.

heading: 2 BACKGROUND AND RELATED WORK
text: We consider a typical federated learning objective:
min w f(w) = N∑ k=1 pkFk(w),
where for each client k ∈ [N ], pk is a pre-defined weight (such that ∑N k=1 pk = 1) that can be set to
1 N or the fraction of training samples, and Fk 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).
Client Selection in Federated Learning. Client1 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 a 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 sub-population of clients, and can promote fairness defined as representative disparity (Hashimoto et al., 2018). Similar to previous work (e.g., Cho et al., 2020; Balakrishnan et al., 2020), we observe our 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
1Following conventions, we use the term ‘client’ for the problem of client selection. Throughout the paper, we use ‘devices’ and ‘clients’ interchangeably.
modular scores since there is no score interaction. Diversity is often well modeled by a diminishing return property, i.e., the (marginal) gain an element brings to a subset diminishes as more elements added to the subset. There exists a rich and expressive family of functions, all of which are natural for measuring diversity, and all having the diminishing returns property: given a finite ground set V of size n, and any subset A ⊆ B ⊆ V and a v /∈ B, a set function F : 2V → R is submodular if
F (v ∪A)− F (A) ≥ F (v ∪B)− F (B). (1) This implies v is no less valuable to the smaller set A than to the larger set B. The marginal gain of v conditioned on A is denoted f(v|A) , f(v ∪A)− f(A) and reflects the importance of v 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).
Maximizing a 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 A is ( n k ) , enumerating them all to find the maximum is 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 fairness. 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 to communication constraints?

heading: 3 DIVERSE CLIENT SELECTION
text: 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 a 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.

heading: 3.1 APPROXIMATION OF FULL COMMUNICATION
text: We aim to find a 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 a subset S, we define a mapping σ : V → S such that the gradient information ∇Fk(vk) from client k is approximated by the gradient information from a selected client σ(k) ∈ S. For i ∈ S, let Ci , {k ∈ V |σ(k) = i} be the set of clients approximated by client-i and γi , |Ci|. The full aggregated gradient can be written as∑
k∈[N ] ∇Fk(vk) = ∑ k∈[N ] [ ∇Fk(vk)−∇Fσ(k)(vσ(k)) ] + ∑ k∈S γk∇Fk(vk). (2)
Subtracting the second term from both sides, taking the norms, and applying triangular inequality, we can obtain an upper bound for the approximation to the aggregated gradient by S, i.e.,∥∥∥∥∥∥ ∑ k∈[N ] ∇Fk(vk)− ∑ k∈S γk∇Fk(vk) ∥∥∥∥∥∥ ≤ ∑ k∈[N ]
∥∥∥∇Fk(vk)−∇Fσ(k)(vσ(k))∥∥∥ . (3) The above inequality holds for any feasible mapping σ since the left hand side does not depend on σ. So we can take the minimum of the right hand side w.r.t. σ(k), ∀k ∈ [N ], i.e.,∥∥∥∥∥∥ ∑ k∈[N ] ∇Fk(vk)− ∑ k∈S γk∇Fk(vk) ∥∥∥∥∥∥ ≤ ∑ k∈[N ] min i∈S ∥∥∇Fk(vk)−∇Fi(vi)∥∥ , G(S). (4)
The right hand side provides a relaxed objective G(S) for minimizing the approximation error on the left hand. Minimizing G(S) (or maximizing Ḡ, a constant minus its negation) equals maximizing a well-known submodular function, i.e., 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 an approximation solution with 1− e−1 bound can be achieved via the greedy algorithm (Nemhauser et al., 1978).

heading: 3.2 GREEDY SELECTION OF CLIENTS
text: The naïve greedy algorithm for minimizing the upper bound of gradient approximation starts from S ← ∅, and adds one client k ∈ V \S with the greatest marginal gain to S in every step, i.e.,
S ← S ∪ k∗, k∗ ∈ argmax k∈V \S [Ḡ(S)− Ḡ({k} ∪ S)] (5)
until |S| = K. Although it requires evaluating the marginal gain for all clients k ∈ V \S 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 a client k∗ from a small random subset of V \S with size s in each step, i.e.,
S ← S ∪ k∗, k∗ ∈ argmax k∈rand(V \S, size=s) [Ḡ(S)− Ḡ({k} ∪ S)] (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 1 assuming the base algorithm is Federated Averaging (FedAvg) (McMahan et al., 2017).
Algorithm 1 DivFL Input: T,E, η, w0
1 for t = 0, · · · , T − 1 do 2 Server selects a subset of K clients St by greedy algorithm in Eq. (6) , and sends wt to them. 3 for device k ∈ St in parallel do 4 wk ← wt 5 Solve the local sub-problem of client-k inex-
actly by updatingwk forE local mini-batch SGD steps:
wk = wk − η∇Fk(wk) 6 Send ∆kt := w k t − wt back to Server 7 end 8 Server aggregates {∆kt }:
wt+1 ← wt + 1 |St| ∑ k∈St ∆kt
9 end 10 return wT
On the left hand side of Eq. (3)-(4), we aim at approximating the full communication by a weighted sum over selected clients in S with weights {γi}i∈S . However, since we relax the problem to minimizing its upper bound and the greedy solution is not guaranteed to achieve the global minimum of the relaxed objective, the weight associated with the greedy solution S, i.e., γi = |Ci| with Ci = {k ∈ V |i ∈ arg minj∈S
∥∥∇Fk(vk)−∇Fj(vj)∥∥}, is sub-optimal. In fact, given S, the optimal weight {γi}i∈S can be achieved by directly minimizing the left hand side of Eq. (3)-(4) but it is infeasible because the full aggregation ∑ k∈[N ]∇Fk(vk) is not available in our setting. Though there might exist better choices, we find that simple uniform weights work promisingly in all evaluated scenarios of our experiments. The stochastic greedy selection in line 2 of Algorithm 1 requires collecting the local gradients of 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 clients every m communication rounds. In our evaluation, we consider the most communication efficient method with “no-overheads” by only utilizing the updates from the clients that participated in the previous round. While this maybe suboptimal since a large part of the dissimilarity matrix will contain stale gradients at every round, we observe no significant loss in performance in our empirical studies.

heading: 4 CONVERGENCE ANALYSIS
text: In this section, we provide theoretical analyses of the convergence behavior of Algorithm 1 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, it can be naturally extended to other federated optimization methods as well.
As discussed in Section 3.1, we draw connections between full gradient approximation and submodular 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 1 (Gradient approximation error). At each communication round t, we assume the server selects a set St of devices such that their aggregated gradients (with weights {γk}k∈St) is a good approximation of the full gradients on all devices with error , i.e.,∥∥∥∥∥∥ 1N ∑ k∈St γk∇Fk(vkt )− 1 N ∑ k∈[N ] ∇Fk(vkt )
∥∥∥∥∥∥ ≤ . The same assumption has been studied in previous works on coreset selection for mini-batch SGD (Mirzasoleiman et al., 2020, Theorem 1) . Note that is used as a measure to characterize how good the approximation is and our theorem holds for any < ∞. Our algorithm (Algorithm 1) is effectively minimizing an upper bound of to achieve a potentially small value via running submodular maximization to select diverse clients (Eq. (4)) . Next, we state other assumptions used in our proof, which are standard in the federated optimization literature (e.g., Li et al., 2019).
Assumption 2. Each Fk (k ∈ [N ]) is L-smooth. Assumption 3. Each Fk (k ∈ [N ]) is µ-strongly convex. Assumption 4. For k ∈ [N ] and all t , in-device variance of stochastic gradients on random samples ζ are bounded, i.e., E[‖∇Fk(wkt , ζ)−∇Fk(wkt )‖2] ≤ σ2. Assumption 5. For k ∈ [N ] and all t , the stochastic gradients on random samples ζ are uniformly bounded, i.e., ‖∇Fk(wkt , ζ)‖2 ≤ G2. Assumption 6 (Bounded heterogeneity). Statistical heterogeneity defined as F ∗ − ∑ k∈[N ] pkF ∗ k is bounded by C, where F ∗ := minw f(w) and F ∗k := minv Fk(v).
Let w∗ ∈ arg minw f(w) and v∗k ∈ arg minv Fk(v) for k ∈ [N ]. In our analysis, we need to bound another variant of heterogeneity ‖ ∑ k∈[N ] pkv ∗ k − w∗‖ in the parameter space. Note that
under Assumption 3 (µ-strongly convexity), Assumption 6 implies that ‖ ∑ k∈[N ] pkv ∗ k −w∗‖ is also bounded by a constant.
Setup. Following Li et al. (2019), we flatten local SGD iterations at each communication round, and index gradient evaluation steps with t (slightly abusing notation). We define virtual sequences {vkt }k∈[N ] and {wkt }k∈[N ] where
vkt+1 = w k t − ηt∇Fk(wkt ), wkt+1 = { vkt+1, if not aggregate, select St+1 and average {vkt+1}k∈St+1 , otherwise.
While all devices virtually participate in the updates of {vkt } at each virtual iteration t, the effective updating rule of {wkt } is the same as that in Algorithm 1. Further, let vt := ∑ k∈[N ] pkv
k t , wt :=∑
k∈[N ] pkw k t . Therefore, wt = { vt if not aggregate, 1 K ∑ k∈St v k t otherwise. . The goal of defining vt and wt is to relate the updates of vt to mini-batch SGD-style updates, and relate the actual updates of wt to those of vt . We aim at approximating vt+1 by wt+1 (when aggregating) and next state a main lemma bounding ‖wt+1 − vt+1‖. Lemma 1. For any virtual iteration t, under Algorithm 1 and Assumptions 1-6, we have
‖wt+1 − vt+1‖ ≤ LGE(E − 1)η2t0 + E ηt0 ,
where L is the smoothness parameter, G is the bounded stochastic gradient parameter, E is the number of local iterations, and ηt0 is indexing the latest communication round.
We defer the proof to Appendix A. The main step involves using Assumption 1 to bound the approximate error of gradients and relating accumulative gradients with model updates. With Lemma 1, we state our convergence results as follows. Theorem 1 (Convergence of Algorithm 1). Under Assumptions 1-6, we have
E[‖w∗ − wt‖2] ≤ O(1/t) +O( ).
The non-vanishing term encodes the gradient approximation error (Assumption 1), and will become zero when we select all clients at 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 ).
We provide a sketch of the proof here and defer complete analysis to Appendix A. Examine the distances between wt+1 and w∗,
‖wt+1 − w∗‖2 = ‖wt+1 − vt+1‖2 + ‖vt+1 − w∗‖2 + 2〈wt+1 − vt+1, vt+1 − w∗〉.
If iteration t is not an aggregation step, wt+1 = vt+1 and
‖wt+1 − w∗‖2 = ‖vt+1 − w∗‖2,
which we can bound with Lemma 1 in Li et al. (2019):
E[‖vt+1 − w∗‖2] ≤ (1− ηtµ)E[‖wt − w∗‖2] + η2tB (7)
for some constant B. If t is an aggregation step, we need to bound
E[‖wt+1 − vt+1‖2] + E[‖vt+1 − w∗‖2] + 2E[〈wt+1 − vt+1, vt+1 − w∗〉].
The second term can be bounded by Eq. (7), which contains (1 − ηtµ)E[‖wt − w∗‖2]. Therefore, combined with Lemma 1, with a decaying step size, we can obtain a recursion on E[‖wt+1 − w∗‖2] which leads to Theorem 1. We provide the complete proof in Appendix A.

heading: 5 EXPERIMENTS
text: Setup. We evaluate DivFL approach utilizing both synthetic and real federated datasets from the LEAF federated learning benchmark (Caldas et al., 2019). The synthetic dataset enables us to 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 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 round are utilized to update part of 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 τ = 1 round of local model update before 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 out the impact of the subset size K on these metrics.

heading: 5.1 RESULTS ON THE SYNTHETIC DATASET
text: We generate synthetic 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(softmax(WTX + b)). We consider a total of 30 clients where the local dataset sizes for each client follows 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 1 for the synthetic IID setting. We observe three key benefits of DivFL compared to random sampling and power-of-choice approaches. On the one hand, DivFL achieves a significant convergence speedup (∼10× 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 as DivFL aims to 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 a lower variance of accuracy in comparison to the baselines, DivFL also shows marginal improvement in fairness, 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 dissimiarlity matrix partially from only the participating clients still outperforms the baselines in the test accuracy and training loss, while preserving the faster convergence of DivFL. In Appendix B.1, we report the above metrics for different choices of K.
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 for the synthetic non-IID for the random sampling approach and slightly less noisy update for the power-of-choice approach. In addition, both the baselines converge to a less optimal solution than DivFL. The mean accuracy gains of DivFL is 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 5x 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 to 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.1, we provide more ablation studies for different choices of the hyperparameter K.

heading: 5.2 RESULTS ON REAL DATASETS
text: 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 DivFL.
For FEMNIST, there are a total of 500 clients where each client contains 3 out of 10 lowercase handwritten characters. Clients use a 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 a celebrity and a CNN-based binary classifier is utilized with 4 3x3-convolutional and 2x2-maxpooling layers followed by a dense layer. For Shakespeare, a two-layer LSTM classifier containing 100 hidden units with an 8D embedding
layer is utilized. The task is next-character prediction with 80 classes of characters in total. There are a total of 109 clients. The model takes as input a 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 a densely-connected 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 1 local update.

heading: 5.2.1 CONVERGENCE BEHAVIOR
text: 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 powerof-choice approach. In the case of Shakespeare, interestingly, both DivFL 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 DivFL either converges at least at the same rate as the fastest baseline.

heading: 5.2.2 FAIRNESS
text: 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 in a more uniform learning across clients. Interestingly for the case of Shakespeare, we observe the variance of 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 variance of accuracies, the mean accuracies are also lower showing that it is not necessarily more “fair”.

heading: 5.2.3 IMPACT OF K AND LEARNING EFFICIENCY
text: 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 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 DivFL. On the other hand, DivFL 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 K = 80 for power-of-choice to achieve their respective highest test accuracies. This reveals that 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 DivFL outperforms both baselines in final mean and variance of test accuracies for all choices of K in Figure 5.

heading: 6 CONCLUSION
text: In this paper, we posed the problem of selecting the most diverse subset of clients for federated learning as the solution to maximizing a submodular facility location function defined over gradient space. To this end, we developed DivFL and provided a thorough analysis of its convergence in heterogeneous settings. Through extensive empirical results on both synthetic and real datasets, we demonstrated strong gains of DivFL over state-of-the-art baseline client selection strategies across key metrics including convergence speed, fairness, and learning efficiency. Furthermore, our communication-efficient variant of DivFL holds all these advantages while making them amenable to practical federated learning systems.

heading: 7 ETHICS AND REPRODUCIBILITY STATEMENT
text: Our algorithm to select the most diverse set of clients not only aims to speed up learning but can also allow for a 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 addresses this concern. In our paper, we take a unique stand in making sure client diversity is addressed (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 hyper-parameters are provided in Section 5 and Appendix B.

heading: A COMPLETE CONVERGENCE ANALYSIS
text: Below shows the convergence analysis. Many steps make a distinction between if we are doing an aggregating steps (from the clients to the server), or not (when the clients do not communicate). We assume that we aggregate every E time steps. Define virtual sequences {vkt }k∈[N ] and {wkt }k∈[N ] where for all k ∈ [N ],
vkt+1 = w k t − ηt∇Fk(wkt ) (8)
wkt+1 = { vkt+1 if not aggregating, sample St+1 and average {vkt+1}k∈St+1 otherwise.
(9)
Let
vt := ∑ k∈[N ] pkv t k, (10)
wt := ∑ k∈[N ] pkw k t . (11)
where pk ≥ 0 is the given weight of the kth client and w.l.o.g., we assume ∑ k pk = 1. Therefore,
wt = { vt if not aggregating, i.e., when t 6= `E for some integer `, 1 K ∑ l∈St v l t otherwise.
(12)
Let
gt := ∑ k∈[N ] pkFk(w k t ; ζ k t ), (13)
and
vt+1 = wt − ηt  ∑ k∈[N ] pkFk(w k t , ζ k t )  := wt − ηtgt. (14) We have
‖wt+1 − w∗‖2 = ‖wt+1 − vt+1 + vt+1 − w∗‖2 (15) = ‖wt+1 − vt+1‖2 + ‖vt+1 − w∗‖2 + 2〈wt+1 − vt+1, vt+1 − w∗〉. (16)
If not aggregating,
wt+1 = vt+1. (17)
Hence
‖wt+1 − w∗‖2 = ‖vt+1 − w∗‖2. (18)
Using Lemma 1 in Li et al. (2019), we know E[‖vt+1 − w∗‖2] ≤ (1− ηtµ)E[‖wt − w∗‖2] + η2tB holds for some constant B. If we are aggregating, we need to bound
E[‖wt+1 − vt+1‖2] + E[‖vt+1 − w∗‖2] + 2E[〈wt+1 − vt+1, vt+1 − w∗〉]. (19)
Let the last time of aggregation happens at step t0 = t+ 1−E, when we select a subset S (associated with weights {γk}k∈S) using the greedy algorithm. Let ∆vkτ be the updates on vk at the τ -th iteration, i.e., ∆vkτ := v k τ+1 − vkτ . Then vt+1 = wt0 + 1N ∑ k∈[N ] ∑t τ=t0 ∆vkτ . To bound the first term above,
‖wt+1 − vt+1‖ = ∥∥∥∥∥∥ ( wt0 + 1 N ∑ k∈S γk t∑ τ=t0 ∆vkτ ) − wt0 + 1N ∑ k∈[N ] t∑ τ=t0 ∆vkτ ∥∥∥∥∥∥ (20) = ∥∥∥∥∥∥ t∑
τ=t0
 1 N ∑ k∈S γk∆v k τ − 1 N ∑ k∈[N ] ∆vkτ ∥∥∥∥∥∥ (21) ≤
t∑ τ=t0 ∥∥∥∥∥∥ 1N ∑ k∈S γk∆v k τ − 1 N ∑ k∈[N ] ∆vkτ ∥∥∥∥∥∥ (22) Similar to the CRAIG paper (Mirzasoleiman et al., 2020), we assume that the subset S selected in step t0 = t+ 1− E provides an approximation of the full gradient such that∥∥∥∥∥∥ 1N ∑ k∈S γk∇Fk(vkt0)− 1 N ∑ k∈[N ] ∇Fk(vkt0)
∥∥∥∥∥∥ ≤ , (23) For every local step τ ∈ (t0, 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
∥∥∥∥∥∥ 1N ∑ k∈S γk∇Fk(vkτ )− 1 N ∑ k∈[N ] ∇Fk(vkτ ) ∥∥∥∥∥∥ ≤ ∥∥∥∥∥ 1N ∑ k∈S γk∇Fk(vkτ )− 1 N ∑ k∈S γk∇Fk(vkt0) ∥∥∥∥∥+ (24)∥∥∥∥∥∥ 1N ∑ k∈S γk∇Fk(vkt0)− 1 N ∑ k∈[N ] ∇Fk(vkt0)
∥∥∥∥∥∥+ (25)∥∥∥∥∥∥ 1N ∑ k∈[N ] ∇Fk(vkτ )− 1 N ∑ k∈[N ] ∇Fk(vkt0)
∥∥∥∥∥∥ (26) ≤ 2LG
τ∑ ν=t0 ην + , (27)
where the first and the third term on the right hand side are bounded using the L-smoothness of Fk(·) and G-bounded norm of its stochastic gradient. Hence, we can continue to bound the first term in Eq. (22) by
‖wt+1 − vt+1‖ ≤ t∑
τ=t0 ∥∥∥∥∥∥ 1N ∑ k∈S γk∆v k τ − 1 N ∑ k∈[N ] ∆vkτ ∥∥∥∥∥∥ (28) =
t∑ τ=t0 ητ ∥∥∥∥∥∥ 1N ∑ k∈S γk∇Fk(vkτ )− 1 N ∑ k∈[N ] ∇Fk(vkτ ) ∥∥∥∥∥∥ (29) ≤ 2LG
t∑ τ=t0 τ∑ ν=t0 ητην + E ητ (30)
≤ LGE(E − 1)η2t0 + E ηt0 (31) = LGE(E − 1) ( 1 + E − 1
t+ γ − (E − 1)
)2 η2t + E ( 1 +
E − 1 t+ γ − (E − 1)
) ηt
(32)
where E is the number of local steps between two communication (aggregation) rounds. Therefore, Eq. (19) can be bounded as follows:
E[‖wt+1 − w∗‖2] (33) ≤E[‖wt+1 − vt+1‖2] + E[‖vt+1 − w∗‖2] + 2E[〈wt+1 − vt+1, vt+1 − w∗〉] (34)
≤ ( LGE(E − 1)η2t0 + E ηt0 )2 + [ (1− ηtµ)E[‖wt − w∗‖2] + η2tB ] + 2 ( LGE(E − 1)η2t0 + E ηt0 ) E[‖vt+1 − w∗‖]
(35) ≤(1− ηtµ)E[‖wt − w∗‖2] + E ρηt0 + [ LGE(E − 1)ρ+ (LGE(E − 1)ηt0 + E )2 ] η2t0 +Bη 2 t
(36) ≤(1− ηtµ)E[‖wt − w∗‖2] + ρEηt0 + [ LGρ+ (LGEηt0 + ) 2 ] E2η2t0 +Bη 2 t , (37)
where ηt = βt+γ , ηt0 = β t−E+1+γ and E[‖vt+1 − w ∗‖] ≤ ρ, shown as follows.
E ∥∥vt+1 − w∗∥∥ ≤ E ∥∥∥∥∥∥vt+1 − ∑ i∈[N ] piv ∗ i ∥∥∥∥∥∥+ E ∥∥∥∥∥∥ ∑ i∈[N ] piv ∗ i − w∗ ∥∥∥∥∥∥ (38) ≤ E
∥∥∥∥∥∥vt+1 − ∑ i∈[N ] piv ∗ i ∥∥∥∥∥∥+M (39) ≤ ∑ i∈[N ] E‖pi(vt+1i − v ∗ i )‖+M (40)
≤ ∑ i∈[N ] pi µ E ∥∥∇fi(vti)∥∥+M (41)
≤ G µ +M ≤ ρ. (42)
The final convergence rates follows from Lemma 3 in Mirzasoleiman et al. (2020).

heading: B ADDITIONAL EXPERIMENTS
text: 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, we 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, fairness and improved model accuracy for DivFL. In addition, the 10th percentile accuracy further confirms that DivFL improves the worst-case clients’ accuracies.
B.2 IMPACT OF NUMBER OF LOCAL EPOCHS τ
Revised: In our experiments, we already adopted local updating schemes with a fixed number of local epochs (τ ) being 1 (running multiple local iterations). However, we further show the robustness of DivFL under different choices of τ via observing the training loss and variance of test accuracies. The results for Synthetic IID, non-IID and FEMNIST are presented in Figure 9, 10, 11, 12, 13 for different values of τ . We observe that for different choices of the number of clients K and the number
of local epochs τ , both variants of DivFL converge faster than both the baselines. The fairness gains over random sampling are also preserved under large values of τ as shown in Figure 13.

heading: K = 10, Local epochs =5

Review summaries:
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.

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.

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.