A Snapshot of the Frontiers of Client Selection in Federated Learning
Authors: Gergely Dániel Németh
Miguel Angel Lozano
Novi Quadrianto
Nuria M Oliver
Venue: Accepted by TMLR ()

Abstract: Federated learning (FL) has been proposed as a privacy-preserving approach in distributed machine learning. A federated learning architecture consists of a central server and a number of clients that have access to private, potentially sensitive data. Clients are able to keep their data in their local machines and only share their locally trained model's parameters with a central server that manages the collaborative learning process. FL has delivered promising results in real-life scenarios, such as healthcare, energy and finance. However, when the number of participating clients is large, the overhead of managing the clients slows down the learning. Thus, client selection has been introduced as a strategy to limit the number of communicating parties at every step of the process. Since the early naïve random selection of clients, several client selection methods have been proposed in the literature. Unfortunately, given that this is an emergent field, there is a lack of a taxonomy of client selection methods, making it hard to compare approaches. In this paper, we propose a taxonomy of client selection in Federated Learning that enables us to shed light on current progress in the field and identify potential areas of future research in this promising area of machine learning.

Published in Transactions on Machine Learning Research (12/2022)
A Snapshot of the Frontiers of Client Selection in Federated Learning
Gergely Dániel Németh ELLIS Alicante
gergely@ellisaliannt..oy
Miguel Áneel Lozano University of Alicante
malozano Qua.es
Novi Quadrianto University of Sussez
n.quadrianto denadriinnto@sssee...... uk
Nuria Oliver
muria@ellissaiiantt..or
ELLIS Alicante
Reviewed on OpenReview: https: // openreview. net/ forum? id= vuOKBl d=uu
Abstract
Federated learning (FL) has been proposed as a crivacy-preserving approach in distributed machine learning. federated learning architecture consists of a central server and a number of clients that have access private, potentially sensitive data. Clients are able keep their data in their local machines and only share their locally trained modcl's parameters with a central server that manages the collaborative learning process. FL has delivered promising results in real-life scenarios, such as healthcare, energy, and finance. However, when the number of participating clients is large, the overhead of managing the clients slows down the learning. Thus, client selection has been introduced as an approach to limit the number of communicating parties every step of the process. Since the early naïve random selection of clients, several client selection methods have been proposed in the literature. Unfortunately, given that this is an emergent field, there is lack of taxonomy of client selection methods, making it hard to compare approaches. In this paper, propose taxonomy of client selection in Federated Learning that enables us to shed light current progress in the field and identify potential areas of future research in this promising area of machine learning.
1 Introduction
Federated Learning (FL) is a recently proposed machine learning approach that aims to address privacy and security concerns in centralized machine learning. It consists of collaborative, distributed learning architecture, where a server communicates with many cliends such that the clients keep their potentially sensitive, private data locally and only share the processed model weights and metadata information with the server. The core of the central server's task is aggregate the model parameters that have been received from the clients to learn improved global model that is then shared back with the clients. The central server might choose different termination conditions for the training process and perform model aggregation using different strategies and optimizers.
Since its proposal 2017 by McMahan et al. 2017 the FL field has grown very rapidly. A recent com- prehensive survey describes the advances and open problems FL and collects more than 500 related works (Kairouz al.] 2021). This paper follows the same notation and definitions as those presented in Kairouz et al. (2021

---

Published in Transactions on Machine Learning Research (12/2022)
To date, two types of federated learning have been proposed in the literature: First, vertical federated learning, where clients have access to different data about the same individuals, who are related by means of a unique identifier. The motivation for the collaboration in this setting is to build more accurate models by including complementary information about the individuals while preserving their privacy and avoiding sending data to the central server. Second, horizontal federated learning, where the features are the same in each elient. In this case, the motivation for the collaboration is to have access to more data points thanks to the federation while keeping them privately on the clients' side. The central server learns better performing model than the local models of any of the individual clients and sends it back to the clients they benefit from the federation. In this paper, we focus on horizontal federated learning techniques.
Regarding the nature of the clients, there are two distinguishable types of FL architectures: cross-silo and cross-device (Kairouz et al., 2021). ) In cross-silo federated learning, clients are expected to be reliable, available, stateful, and addressable. Conversely, in cross-device federated learning the clients are separate and diverse individual actors that may not participate in the federation for a variety of reasons, such as a loss of connectivity or excessive energy consumption.
When a federated learning scenario involves few clients, it is feasible to incorporate their parameters in every training round. However, as the number of clients increases, so does the communication overhead, such that considering the data from all the clients becomes a challenge. At the same time, when the number of clients is large, some of the clients might have access to redundant, noisy or less valuable data than other clients. Therefore, client selection methods are introduced to reduce the number of working clients in each training round. Recent works have shown that client selection methods are able to keep the performance of the overall model while improving the convergence rate of the FL training (Nishio & Yonetani 2019), reducing the number of required training rounds (Goetz et al. 2019 enhancing fairness in case of imbalanced data [Li et al. 2020).
While implementing sophisticated client selection methods may help to achieve these goals, they require the server to have information about the clients, such as training time (Nishio & Yonetani 2019) or communica- tion stability (Zhou et al. (02T). Thus, the use of client selection methods might have privacy implications, representing a trade-off between potentially losing privacy and achieving good performance while keeping the overhead low, improving the overall utility (Dennis et al. 2021 Wang et al. 2020 or the fairness (Mohri
2019 Li et al. 2020 of the system. et al.
In recent years, different client selection methods have been proposed in the literature (Chen et al. 2018 Mohri et al. 2019 Zeng et al. 2020 with a wide range of objectives, requirements, and experimental settings. Such wealth of proposals such a short timeframe makes it hard for researchers to properly compare results and evaluate novel algorithms. Furthermore, it limits the ability of practitioners to apply the most suitable of the existing FL techniques to a specific real-world problem, because it is not clear what the shate-of-the-art is in the scenario required by their application. The purpose of this paper to fill this gap by providing comprehensive overview of the most significant approaches proposed to date for client selection in FL.
Our contributions are two-fold: First, we present a taxonomy of FL client selection methods that enables us to categorize existing client selection techniques and propose it as a framework to report future work in the field. Second, we identify missing gaps in existing research and outline potential lines of future work in this emergent arca.
The structure of the rest of the paper is follows: in section 2 we summarize the problem formulation and the mathematical notation used in the manuscript. Section describes the proposed taxonomy and identifies future research directions. Commonly used benchmark datasets are presented in section 4 followed by our conclusions.
2 Problem formulation and notation
Federated Learning is a cooperation of N clients, K = CI,,,, where each client e; has access to a datasct ID; which is considered to be private to the client. The clients work together under a central server to train global model f(0) with model parameters 0. The central server aims to minimize the global cost function
2

---

Published in Transactions on Machine Learning Research (12/2022)
Clients
Server
IK
Round Commmication timeline
Request 0, for client i
Client selection Pederated update
Collect M₁
o/ (M.))
of = of (1, )..)
S¹ = h ((11, ((o1,...,, uN
Value generation
Value interpretation
g
Broadcast 0
Client update
0
0 agg (10) +1
EES
Aggregation
Figure 1: Diagram of general federated learning training round with client selection. The server communi- cates with the client set K. select the participating client set S. Only this subset of clients trains their local data in given round and reports their parameters back to the server. Not all steps are required for every algorithm
L(0) given by Equation Here N the total number of clients, = U Dj and [D] is the total number of data samples in all the clients, (x.y) E Dj is an input-output pair of training samples in the dataset of the ith client and I is the loss function.
min L(
Σ (Z.y)ED;
1y [xx 0))
(1)
However, the central server has no access to the clionts' private data. Thus, it broadcasts the global model parameters to all clients which are used by each client a E KK as the starting point to compute the local parameters 0, that minimize their local cost function (0; [)) described in Equation 2
min L.) D
Σ (n.M)).
f(x 0:))
(2)
Once the server has collected the local parameters (0,), aggregates them into the next iteration of the global parameter 0 order to minimize the global cost. function L(0). Each iteration of the global parameter update called a training round and the parameters in the round are denoted with 0*. naive aggregation function is to weight each client's parameter proportionate to their data sample size, given by Equation 3 The federated training proceeds until reaching convergence of the global cost function L.
1++1
0
The communication with cach client after each local model update may generate large overhead, particularly when the number of clients is large. To address this problem, McMahan et al. (2017) introduced the Fed Avg algorithm where the clients communicate with the server only after e local epochs. From the server's point of view, the global model parameters are updated with the clients' data training rounds t 1,..., From the clients' perspective, every training round consists ..... e local epochs. Thus, the clients train a total number of eT epochs.
3

---

Published in Transactions on Machine Learning Research (12/2022)
Additionally, FedAvg uses random selection St of M participating clients in every training round t, S S IK with [8*| = M, such that a client is selected with probability p(c; E @* N. The client update and aggregation steps given by 0
M
pritteeppdate(Pe D)) and g++1 = ( +1 . EST)), respectively.
After the seminal work of FedAvg, subsequent research works have proposed a diversity of client selection methods, most of which follow the flow illustrated in Figure [ First, the server requests a value U; from each client, which the client computes based on its local information M,, Once the server has received the o from all the clients, it selects a subset S' of the clients according to function h(v1, UN). Stateful selection methods also use previous information about the clients, calculating e from the client feedback vg and a function (7) of previous values of the client. After this, the server broadeasts its global parameters Of only to the selected clients S' which update their local models and send back their updated local parameters 6t+1. With this information, the server computes the updated global parameter 0'-1.
Based on this general description of client selection in federated learning, we present next the proposed laxonomy to characterize client selection methods.
3 Proposed taxonomy of client selection methods
Our proposed taxonomy, depicted in Figure 2 aims ease the study and comparison of client selection methods. It contains six dimensions that characterize each client selection method. The top part of the Figure displays the three dimensions (marked in red) that concern the server in the Federated Learning framework whereas the bottom three dimensions concern the clients (marked in groen) or both the clients and the server (marked in blue). In the following, we describe in detail each of these dimensions and present the most relevant works in the client selection literature in FL according to the proposed taxonomy.
3.1 Client Selection Policies
The main purpose of client selection in Federated Learning is to automatically determine the number of working clients improve the training process. A broad range of policies have been proposed in the literature, including variety of global constraints (e.g. improving the efficiency in the learning, limiting the amount of time or computation needed or ensuring fairness), pre-defined client inclusion criteria and client incentives.
We provide below a summary of the most prominent works according to their policies for client selection. The third column in Table [ provides an overview of the client selection policies of the most representative client selection methods in FL.
3.1.1 Global Constraints
The server might define different types of global constraints to drive the client selection process.
Training efficiency
The most common goal in client selection is to speed up the converyence of the training process. However, formalizing this simple goal may result in different technical solutions. Some authors (Chen et al. 2018 Dennis et al., 2021 focus on reducing the number of clients in a training round while maintaining the same convergence rate. Chen al. (2018) show that communccting only with the right clients can reduce the communication to the tenth of what it would be in a cyclie iteration of the clients. Later work by Chen al. (2020) reports that optimal client sampling may yield similar learning curves to those in full participation scheme. Other works aim to reduce the total number of training rounds to reach the same accuracy. Cho et al. (2022b) propose pow-d which takes half as many iterations to reach 60% accuracy on the FashionMNIST dataset than a random client selection.
Alternative definitions of efficioncy include energy consumption. For example, Cho et al. 2022a) propose the FLAMEe FL framework that computes energy profiles for each client and simulates different energy profiles in the federation. They report that incorporating energy consumption global constraint: in the
4

---

Published in Transactions on Machine Learning Research (12/2022)
Target accuracy
Limited resources
rounds
Fixed Sowdrouud
Global constraius
Ranking
Probability
Client inclusion
Termination
condition
Policy
Inteppretation
Val Value
Weights
Client incentives
Server
Clusters
Available
Hybrid
Loss based
characteristoe
Addressable
Client
CBent
Value
generation
Utility- based
Utility-based
Bandit- based
Stateful
Shapley values
Reliable
Stackelberg game
Shared
Trustful
information
Reinforcement L.
Local parameters
Descriptors
Compressed data
Figure 2: Proposed taxonomy of client selection methods in Federated Learning. The taxonomy has six dimensions: Policy, Termination Condition, Value Interpretation, Client Characteristics, Shared Information, and Value Generation. The top three dimensions (colored in red) capture properties on the server side, the dimensions colored green are on the client side, and the sixth dimension, colored in blue, corresponds to hybrid client-server property.
client selection method can save up to 2.86x more clients from reaching their energy quota when compared to the same method without any energy consideration.
Other authors propose limiting the time of the local training as the main guiding principle to achieve client selection. This concept was introduced by Nishio & Yonetani (201 in the FedCS method, which filters out slow clients and hence speeds up the overall training time. FedCS requires clients to estimate Tr, the time needed to perform their round of learning and the server selects only clients with T; lower than a certain threshold. The authors report that selecting the right clients according this criterion could reduce by half the total training time to reach the desired accuracy when compared to federated average (FedAvg) with limited local training round time.
Resilience
Client selection may be used to remove malicious clients from the training process, thus increasing the re- silience of the system against adversarial attacks. Rodrígucz-Barroso et al. (2022) use a server-side validation set Dy to measure the accuracy of each local model. Then, the models with low accuracy are given lower weights. Their results show that this method able to keep the same level of performance even 10 out of clients send malicious model updates. An alternative approach to filter malicious clients is using Client Incentives. these methods, the rewards offered the clients are inversely proportional the probability of being malicious harmful client. We direct the reader to section 3.1.3 for description of such methods.
5

---

Published in Transactions on Machine Learning Research (12/2022)
While client selection can be tool to fight against attacks, it opens a new vulnerability. Malicious clients may attempt to be included in the training rounds by changing their behavior or their data to be more appealing for selection. For example, the method proposed by Blanchard et al. (2017) which selects clients with the smallest weight update is vulnerable to adaptive attacks. could be abused by injecting a backdoor with a very small learning rate, and therefore small weight update. The server would then be selecting this client over other benign clients.
Fairness
An additional policy for client selection is to ensure fairness in the criteria applied to select clients. In FL, and especially in cross-device FL, algorithmic fairness definitions, particularly group fairness definitions adopted in the machine learning literature are hard to implement because they require knowledge of sensitive attributes that only available on the clients' side. For example, providing group fairness guarantees according to protected attribute (e.g. race or gender), would require the server to collect data of the performance of the model on different groups according to the protected attribute. However, the privacy motivation for FL would prevent such attributes from being shared with the server. One possible way to report scnsitive data with privacy protection would be to use differential privacy (Geyer et al.
2017 Padala
et al. 2021
In the context of FL, different definitions of fairness have emerged. Work by Mohri et al. 2019 aims increase good-intent fairness to minimize the maximum loss in the federated training between clients. In the experimental evaluation, the proposed AFLM method outperforms the baseline uniform distribution in various datasets while increasing the worst-case accuracy, i.e. the performance on the client with the lowest accuracy. This principle is related to min-max notions of fairness, such as the principle of distributed justice proposed by Rawls (2004).
et al. (020)) define fairness as the property of achieving uniform accuracy across all clients. This definition corresponds to the parity-based notion of fairness, as opposed to the min-max principle described above. They propose novel FL approach called q-FFL to reduce potential accuracy differences between clients by giving larger weight to those clients with large error during the training process. According to their experiments, the proposed method yields an increase of the worst accuracy by 3% in a class-split Fashion- MNIST federated experiment while keeping the average accuracy the same as a state-of-the-arl method
AFLM
Shi al. (021) propose taxonomy to categorize the fairness definitions that have been proposed in the FL literature. All the proposed fairness definitions belong to the Server Policies dimension of our taxonomy (see Figure D)
accuracy parity and good- good-intent fairness would be categorized as Global Constraints; selection fairness could also be considered Global Constraint or part of a Client Inclusion policy; finally, contribution, regret distribution and expectation fairness would belong to the Client Incentives policy.
3.1.2 Client inclusion policies
In some cases, the server might define specific client inclusion policies beyond the global constraints. For example, if a client has limited, but very relevant or valuable data to the problem at-hand (e.g. data from an underrepresented demographic group), the server may define client inclusion policies to ensure that such clients are selected even they would not satisfy the global constraints.
Examples of client inclusion policies include ensuring a loss tolerance for communication packages. Zhou et al. (2021) show that relaxing the global constraints for clients with poor communication channels not only improves client inclusion but also the overall performance of the FL system. Their proposed method II-FI allows clients to discard lost packages instead of asking the server to resend them. Thus, the communication time decreases and otherwise poorey-represented clients are able to participate in the training.
An alternative client inclusion policy may be seen in the context of model-agnostic FL. In this case, low- resource clients have the option to learn different, simpler models. Thus, the local training may be faster and the communication requires less data transfer. One example of such an inclusion policy is Federated Dropout (FD) proposed by Caldas et al. (2018b), where simpler deep neural networks (with fewer neurons in
6

---

Published in Transactions on Machine Learning Research (12/2022)
Highlighted Incentive Mechanisms for FL Client Sclection
Incentive score validation
1.
Zeng et al.
(020
2.
Kang et al.
2019a
3, 6, 7, 8, 9, 10
3.
Sarikaya Ercctin
2019
4.
Zhao al.
(0200)
5.
Song et al.
(0099)
2, 5, 11
6.
Wang et al.
(2019a)
7.
Liu et al.
(0200)
8.
Pandey et al. (2019
9. Hu & Gong (2020
Performance analysis
Comparison with state of the art
10. Lim et al. (2020)
11. Kang et al. (2019b)
Figure 3: Experimental evaluations of proposed incentive mechanisms in the literature lack a quantitative comparison with state-of-the-art methods on benchmark datasets with comprehensive performance and efficiency analysis.
the layers) are learned in clients and the server combines them together into larger network following the idea of dropout. Their method shows a 14x reduction in server-to-client commuicatiin,, a 1.7x reduction in local computation and 28x reduction in client-to-server communication compared to uncompressed models.
Following this work, Diao et al. (020)) and Liu al. (022) propose methods to match weaker clients with smaller models and implement model-agnostil FL. In HeteroFL, proposed by Diao al. (2020), the smaller model's paramcter matrix is cropped version of the complete matrix. During the aggregation, the server aggregates the models with different sized hidden layers from smaller to larger. They present experimental results with 5 different sized models, the largest having 250 times as many parameters as the smallest. They report similar accuracies when setting half of the clients' models to the smallest size and half to the largest size than when all the clients have the largest model while halving the average number of parameters. Liu et al. 2022 propose InclusiveFI. where larger models have more hidden layers. They show that for more complex models (e.g. transformer models with the self-attention mechanism) InclusiveFL works better than HeteroFL on several ML benchmark datasets.
3.1.3 Client incentives
A common assumption in Federated Learning is that all the clients are willing to participate in the training at any time. The reward for their contribution the federation access an updated, global -and ideally better model. However, clients might not see the benefit of the federation for a variety of reasons. For example, stateless clients in cross-device FL may never receive updated model from the server after participating because the users might disconnect their devices before being selected a second time. Thus, an active research area in the literature of client selection in FL focuses on defining incentive mechanisms for the clients so they participate in the federation. Note that such incentive mechanisms have been extensively studied in other multi-actor areas of science, such as economy (Hahn Stavins 1992 Lindbeck et al. 1999)
environmental protection (Nichols] 1984 Kremen et al. 2000). mobile crowdsensing (Yang al. 2017 and
shared distributed energy sources (Wang al. 2019b) human resources [Fazzan al. 20088).
In the context of FL, the server typically gives reward to the participating clients according their contribution. According to the work by Zhan et al. (2021). the incentive mechanism methods proposed to date may be categorized into three classes, described below. Zeng et al. (2021) additionally categorize the methods based on the used value generation Lechniques, described in Section section 3.5
The first class of incentive mechanisms considers client resource allocation and gives rewards based on the computation power, energy usage, or allocated time. For example, SSaikaya & Ercetin (2019) offer Stackelberg game-based solution based the clients' CPU power utilization. They study the server's

---

Published in Transactions on Machine Learning Research (12/2022)
strategy based on its budget and the trade-off between the number of learning rounds and the required time of a round with respect to the number of clients.
Second, the incentive mechanisms may be used to attract clients with good data quality and quantity. These incentive mechanisms are classified as data contribution incentives. For example, [Song et al. (2019) use Shapley values (Shapley 1971) to evaluate the data contribution of clients and reward them accordingly. They define the contribution index (CI) such that (1) data distributions that do not change the model have contribution; (2) two datasets with the same infiuence the model have the same CI, and (3) if there are two disjoint test sets, the contribution index in the context of the union test set should be equal to the sum of the CI of the two original test sets. The proposed CI-MR] method performs similarly to maate-of-thh-art methods while calculating the scores up to 5 times faster. Zeng et al. (2020) show that measuring the data contribution by means of a clients' utility score and applying an auction, the [More method selects 80% of the participating clients, resulting in a 40 60% speed-up in terms of the number of training rounds necessary to reach 90% accuracy on the MNIST datasct.
Third, the incentives may be correlated with the reputation of the clients. Such reputation may be com- puted from the usefulness of each of the client's models. In addition, several works have proposed using a blockchain to keep track of the clients' contributions and hence of their reputation (Kang et al. 2019a Zhao et al. 2020). Kang et al. (2019a) show that removing clients with a bad reputation may increase the model 's final accuracy. ZZhao et al. (2020) report that a reputation score may punish potentially malicious clients while maintaining the global convergence of the model.
Future Work
There are several areas of future work regarding the Policies of the server to perform client selection.
We refer to the lack of discussion highlight work on privacy as a Global Constraint. Geyer et al. (2017) define a privacy budget for each client and propose an experiment where clients terminate their participation if their privacy budget is reached. Thus, clients terminate in different rounds. This line of work can be expanded to more complex budgeting that reflect the information shared in messages.
privacy-efficiency trade-off more in Section 3.4 Here we want to
While many client selection approaches have been proposed in the literature, they lack a vulnerability analysis of potential attacks directed against the approach itself. Future work in this direction would be needed before specific client selection method is deployed in production.
Another potential research direction would focus on the clients' perspective to define the client selection strategy. While client incentive policies aim to motivate the clients' participation with fair payoffs, there is an opportunity to further study and propose FL approaches centered around the clients' interests. In this sense, we identify several relevant research questions, such as studying the trade-off between data availability and performance of the local vs federated learning models; developing models to support the clients' decisions as to when to join the federated learning scenario; and approaches that would enable clients to participate in the federation in a dynamic manner, depending on the current. state of the learning model. Recent advances in model-agnostic FL in combination with incentive mechanisms suggest an interesting direction of future work. One could design a federated learning scenario, where the server would propose contracts to the clients with different model sizes and rewards. Then, the clients would be able to select the contract that matches their available resourccs and interests the best.
Finally, believe that there is an opportunity to improve the empirical evaluation of existing and newly proposed incentive mechanisms for FL. There are 3 key components depicted in Figure g that we con- sider necessary to include in such an evaluation: first, a clear explanation as to why the proposed scoring satisfies the requirements of being an incentive mechanism; second, a performance and efficiency analysis on benchmark datasets; and third, a systematic comparison with other state-of-the-an art client selection methods. As can be seen in the Figure, most of the proposed methods in the litcrature fail to include one or more of these three elements. While several survey papers of incentive mechanisms in Foderated Learning have been published (see e.g. Zhan et al. 20021 Zeng et al. (2021)), to the best of our knowledge none of them
8

---

Published in Transactions on Machine Learning Research (12/2022)
presents thorough quantitative analysis of the topic. In section 4 we further discuss the scarcity of available benchmark datasets and experimental setups for Federated Learning.
3.2 Termination condition
The next dimension in the proposed client selection taxonomy is the Termination condition, which is defined by the server. The termination condition determines when to end the Federated Learning training process, and hence it is important choice of the experimental setup. The definition of the termination condition typically depends an overview of the termination conditions of sample of the most reprosentative client selection methods proposed to date in the FL literature.
the goal and priorities of the FL system. The seventh column in Table ! provides
We identify three main categories regarding the termination condition.
In the first category of methods, the learning process ends after a fixed number of rounds (T) of federated training. In simulated scenarios, this termination condition helps identify whether different methods reach the same accuracy. However, in some works the methods do not reach their best performance in prodefined number of rounds (Chen et al., 2020 Cho et al., 2022ab. In this case, it is imporiant to molivate why the experiments ended at that point. For real-world scenarios, this termination condition is easy to implement.
In the second category of approaches, the lcarning process ends when a minimum required accuracy is achieved. This termination condition is particularly helpful to compare different federated learning methods regarding how quickly they achieve the desired accuracy. The minimum required accuracy may be determined by the performance of a bascline method by the task at hand to solve with the federated lcarning system Nishio & Yonetani
2019 Zeng et al. 2020: Lai al., 2021.
Finally, alternative termination conditions may be defined from the perspective of limiting the partici- pation of a client: for example, Cho et al. (2022a) limit the energy drain a client's device is allowed to endure. Furthermore, Kang et al. (2019a) limit the reward clients can receive in an incentive mechanism, thus the experiment finished when all the rewards are spent. Tf the server has validation set, may apply an early stopping (Es) approach. Otherwise, the client may suggest that they are unable meaningfully contribute to produce a better model. In (Chen et al. 2018), the proposed LAG WK FL system allows the clients to evaluate whether they should send update to the server not, and the training stops when no client sends a new round of parameters.
Future work
In terms of future work regarding the termination condition, we highlight two potential directions. First. privacy could be considered as a key factor to define the termination the learning process (Geyer et al. 2017). The PyShift package, designed by Ziller et al.] (2021) was implemented with this consideration mind, giving a privacy budget to the clients which is reduced every time the server accesses information from the specific client. Beyond PyShift, the potential privacy loss of the clients that participate in several training rounds and the inclusion of a participation budget as global constraint to protect the privacy of the clients' data.
identify two potential lines of future work: analysis of
Second, current works give the right of termination to the server. However, in a real-life sconario, the clients could also decide to stop their participation the training process. Incentive mechanisms aim to achieve a fair client participation, but they still give the power of termination to the server and generally do not consider the clients' interests perspectives. Client-centric termination policies could therefore be potential line of future work.
3.3 Client characteristics
FL methods are implemented with certain assumptions regarding the characteristics that the clients should have. Thus, the Client Characteristics are the next dimension the proposed taxonomy. The second column in Table provides an overview of the client characteristics required by representative sample of the client selection methods proposed to date in the FL uiterature.
9

---

Published in Transactions on Machine Learning Research (12/2022)
Table 1: Selected works from the literature and their characteristics according to the proposed taxonomy. Appendix shows the detailed descriptions of the methods. Client characteristics: availability (V), address- ability (D), statefulness (S), reliablity (R), and trustworthiness (T). & indicates an exploration term with additional randomly selected clients and Fg indicates an early stopping mechanism.
Client characteristics
Value generation
Value interpretation
Termination
Algorithm
Policy
Message
condition
EqRepbaelinee
VDSRT
Selection fairness
Probability
EqW baseline
V VDSRT
Selection fairness
0, [D]
Probability
AFLG
VDSRT
Efficiency
L
based
Probability
Fixed rounds
pow-d
VDSRT
Efficiency
0, |D],
Loss-based
Ranking
Reach accuracy
Shapley values Validation set
S-FedAvg
VDSHT
Efficiency
0
Probability
Fixed rounds
k-FED
VDSRT
Efficiency
0, G
Clustering
Clusters
Fixed rounds
LAC
VDSRT
Efficiency
0,
Loss-based
Threshold
Fixed rounds,Es
FL-CIR
VDSRT
Efficiency
Sandit-based
Ranking
Fixed rounds
Reinforcement L.
FAVOR
VDSRT
Efficiency
Ranking
Reach accuracy
Validation set
Fixed rounds,
FedCS
VDSHT
Limit round time
0,T
Time-based
Ranking
Reach accuracy
Good-intent fairness
AFLM
VDSRT
O.L
bass-based
Probability
Fixed rounds
Q-FFL
VDSRT
Uniform accuracy
0,
based
Weights
Fixed rounds
Oort
VDSHT
Limit round time
0,L,T
Utility game
Ranking+E
Reach accuracy
Limit client
FLAMEa
VDSRT
0, J. T.
Utility game
Ranking
Limited energy
participation
Defense against
DDaBA
VDSRT
Validation set
Weights
Fixed rounds
attacks
LT-FL
VDSRT
Client inclusion
0,T
Time-based
Clusters
Fixed rounds
Model
FD
VDSHT
Client inclusion
0
Weights
Fixed rounds
compression
CL-MR
VDSRT
Client incentives
0, |D|
Shapley values
Weights
Fixed rounds
Auction
Fixed rounds,
FMore
VDSRT
Client incentives
|D] T
Ranking
Uuility score
Reach accuracy
Contract theory
CBIM
VDSRT
Client incentives
0,T, 0,T,F.. E...
Threshold
Limited reward
Utility score
10

---

Published in Transactions on Machine Learning Research (12/2022)
According to Table 1 from Kairouz et al. (2021) FL clients may have four important characteristics: availabil- ity, addressability, statefulness and reliability. We propose to add a fifth characteristic, trustworthiness, that should be considered when designing a client selection method in a FL scenario. These five characteristics are defined as follows:
Availability (V or V): Let A be the active client set, L.e. the clients that are ready to participate in the next training round. In each training round, the server may select the participating clients St from the active client set A Generally, S' S A' S K. Sometimes, for example in cross-silo scenarios, A K, Vt 1...T. The assumption of client availability in FL method will be denoted by V, otherwise V.
Addressability (D or D): Clients have unique identifiers, such that the server is able to individually address them and communicate with specific clients (D). Conversely, the server communicales in a broadcasting manner, sending the same message to all the clients (D).
Statefulncss (S or S): In stateful scenario (S), the clients are able to participate in multiple training rounds and they can refer back to the weights parameters of previous rounds. In stateless scenario (S); each client participates only once in the learning process, so the client selection (and aggregation) policy is not able to depend on their previous performance.
Reliability (R or R): Even if a client meets all the selection criteria and is selected by the server to participate in a round training, it may fail before sending its information to the server. Federated learning methods that assume that all participating clients will successfully report back at the end of their local training make a reliability assumption, R. Otherwise, the methods are characterized as R.
Trustworthiness (T T): In ideal scenario, all clients sharing truthful information with the server and hence they are trustworthy, T. However, clients may be malicious (T) and share false information. Previous research in FL has focused on tackling this problem, such as Kang et al. (2019a) who propose a client selection incentive that gives a bad reputation score to potentially harmful clients and Rodríguez- Barroso et al. )2022) who gives less weight to clients with lower accuracy on a server-side validation set.
In general terms, these five characteristics of the clients are known to the server in cross-silo FL scenarios. However, in cross-device scenarios, several of these features may not be known to the server and the methods should be able to function without depending of new FT. client selection methods to identify their dependencies on these client characteristies such that different approaches may be compared and the reproducibility of the results is facilitated.
any of them. We would like emphasize the importance
Future work
Client characteristics are not always considered when designing client selection policies which leads of ineffi- cient or inconsistent FL systems. For example, cross-device FL is in many cases stateless clients may join to the system only once during the training. However, there are apputatton-based client incentives (based on the client's performance in previous rounds) proposed for cross-device FL that are impossible to implement as the server does not have access to the clients' state in a stateless context (Kang et al. 2019a).. The same problem was identified by Wang et al. (2021) for FL in general. We would like to emphasize the importance of clearly describing the required client characteristics when proposing novel approaches to FL to case the comparison with other methods and ensure the reproducibility of the results.
Trustworthiness in FL is often addressed at the level of optimization algorithms model aggregation. Blanchard et al. (2017) propose an algorithm to weigh the client models during aggregation in a way to reduce the effect of outliers. However, few research works address trustworthiness during client selection by e.g. removing harmful clients Zhao et al. (2020). We believe the addition of this feature to the client characteristics in our taxonomy may boost future research in this direction.
In addition Client Characteristics, the proposed taxonomy includes dimension related the kind of information that the client shares with the server.
11

---

Published in Transactions on Machine Learning Research (12/2022)
3.4 Shared information by the client
Federated learning was proposed with the motivation of preserving privacy by enabling a central server to learn from distributed client data without ever having access to the actual data. As the learning heavily depends on the information shared by the clients with the server, it is important to understand and analyze the types of messages that the clients send to the server.
Client selection requires analyzing information about the clients. Thus, there is trade-off between a potential privacy loss from the client'ss perspective and the goals of implementing client selection. This section of the proposed taxonomy highlights the importance of studying and characterizing such trade-off.
The most commonly shared client information are either the updated client weights (0;) or the change in the weights when compared to the previous learning round (Nagalapatti & Narayanam 2021 Wang et al. 2020 Additional methods proposed in the literature use the loss (L) of the clients" model (Goetz et al.
2019 Mohri et al. 2019 Yang et al. 2021).
Moreover, clients might share additional information with the server. Examples from the literature may be categorized into two groups. Firstly, scalar descriptors, such as the Lipschitz-smoothnees of the client loss function (L) CChn et al.
2018
Li et al. 2020), the total size of the client data (ID)) (Song et al. 2019 Cho
ct al. 2022b Zeng et al. 2020
or the expected training time on the client (7) NNishio & Yonetani 2019
Kang et. al. 2019a Zeng et. al. 2020 Zhou et. al. 2021).
Secondly, a modified, compressed version of the client data, such as a vector of cluster centers computed from the clients' data (Dennis et al. 2021).
The message sharing between the client and the server is denoted by us g(M),, I,..,N, where M: is the shared information by client i. To select the best clients, the server needs to assign value (v;) to each client. The function generates this value from the client's shared information. This Value Generation process (described in section 3.5 below) may be done on either the server or the client side. Note that a server-side validation process to evaluate the clients' models reduces the server-client commnication, but adds extra overhead on the server as has to run all the client models on the validation set (Dv) (Wang ett al. 2020 Nagalapatti & Narayanam, 2021).
The fourth column in Table I includes the types of Messages send by the clients to the server in each of the selected representative papers from the literature and the fifth column describes the Value Generation functions used by such papers.
To preserve the clients' privacy, several privacy-preserving methods have been used in FL frameworks, such as differential privacy Abadi al. (2016) and secure aggregalion Bonawitz el al. (2017). Despite a call from Wang et al. (2021) in general field study to make client selection methods compatible with privacy- preserving methods, current client selection works do not discuss their compatibility. For example, client selection approaches relying
server-side validation set (see Value generation column in Table [ cannot apply secure aggregation as they require server-side inference on the local models. Similarly, client selection strategies might not work if local differential privacy is used to disclose the clients' update Duchi et al. 2013
Future work
While current works analyze the communication in terms of performance and calculate the trade-off of including additional messages, there is lack of rescarch analyzing the privacy cost of sharing increased amounts of information between the clients and the server. In addition, future work is needed on the interplay between client selection and privacy-preserving methods, such as diffcrential privacy and secure aggregation.
12

---

Published in Transactions on Machine Learning Research (12/2022)
Using locally generated synthetic data for client selection may be another fruitful research direction. Tackling the challenge of non-identicall, and independently distributed (TID) distributed data problem has motivated
GAN generated synthetic data sharing and progress was made in this direction (Xin et al. 2020 Rajotte ct al. 2021), however, these methods do not loverage the client selection, only use all clients or implement random selection.
The next dimension in the proposed taxonomy is Value Generation, ie. the process by which the server assigns value to each client that will be used to inform the client selection process.
3.5 Value generation
Once the server receives each clients' shared information M,, it generates a relevance value (vy) for each client. This value used select the set of participating clients the next round of training (S*). In this section, we summarize the most significant Value Generation approaches proposed in the literature.
While the value generation typically takes place the server side, in some cases the clients send an already processed value to the server, or the value might be even computed in both sides. We discuss how the server interprets this generated value in section 3.6
A commonly used technique is to evaluate the clients directly using their local training loss. Intuitively, if a client has a large loss, the training would benefit from more rounds of the client's data. However, these loss-based methods need store the results in previous rounds of the training, requiring either stateful clients (Chen et al., 2018) or clients that are able to estimate their loss in the current round. In this case and to reduce the overhead, some methods use a random selection of clients first (A C K) and then implement more sophisticated client selection strategy on this subset of clients. In (Cho et al. 2022b), the authors show that optimizing the size of this subset has a positive impact on the model's performance: their pow-c method outperforms EgRepisseline by 10% and AFLG by 5% on the FMNIST dataset.
Other research suggests that the loss is only one of different metrics that one could optimize for. Lai et al. (2021) proposes a utility function composed of different terms, including the loss-based statistical utility and the system's utility derived from the time needed for the training. They report a significant spoed-up in training time: the proposed Oort reaches better accuracy in 10 hours than a random selection method in 30 hours on the OpenImage (Kuznetsova et al. 2020) image classification task. Cho et al. (022a)) incorporates a third utility term: an energy consumption- based score. They show that distributing the workload with respect to the energy usage doubles the number of training rounds without dropping clients due to reaching their energy limit. The general formulation for computing an overall utility score given by equation
where B, D2 is a subset of the ith client's data.
Utilitt)= = M1 (1 B.)
U2 System utility
(4)
Statistioal utility
Other utilities
Other scholars have formulated the client selection problem propose multi-armed bandit approach where the clients are the arms and the S' client set is the superarm at round to achieve reduced class imbalance between clients and thus increase the training efficiency. Their method yields a 10% increase in accuracy when compared to random selection in a non IID scenario of the CIFAR10 dataset.
bandit problem. Yang et al. 22021)
In cooperative game theory, Shapley values are used to determine the contribution of clients or the value of their data (Shapley] 1951). In FL, they are used to give fair payoff to participating clients based on their contribution WWang et al. 2019a Song et al. 2019 Liu et al.) (0200) and to identify the most valuable clients for the next training round (Nagalapatti & Narayanam 2021). Wang et al. (2019a) use Shapley values to determine the features with the largest contribution in a vertical FL scenario. Song el al. (2019) show that Shapley values are effective to compute a contribution index of the clients. Liu et al. (2220) simulate clients with different data quality levels from the MNIST dataset and show that their Shapley value-basod method gives higher scores to the clients in higher data quality group. While the above 3 works use Shapley values for incentives, Nagalapatti & Narayanam (021) show that removing irrelevant clients using Shapley values
13

---

Published in Transactions on Machine Learning Research (12/2022)
can increase the overall accuracy. Their S-FedAAg increases the validation accuracy from 40% to 80% when compared to FedAvg in MNIST-based experiment.
The Stackelberg game is a market modeling structure with two types of actors: leaders and followers. In FL, the server acts as the leader and the clients as the followers. In Sarikaya & Ercetin (2019). the server proposes a price for the clients' resources which the clients use to compute their utility scores that are sent to the server. Finally, the server selects the clients with the highest scores. Their experiments support that there is an optimal number of clients from an efficiency perspective that may be identified with such client selection approach, despite the availability of more clients. Furthermore, Pandey et al. (2019) propose to reward the clients' local accuracy and show that their method can achieve optimal utility scores in a small, 4-client scenario. Huu & Gong (2020) propose a Stackelberg game to give incentives depending on the clients' data privacy loss. Unfortunately, these works lack both a comparative analysis of their empirical results with other state-of-the-art approaches and a performance analysis on commonly used benchmark FL, datasets.
Auction and contract theory have also been proposed to assign a value to clients in FL incentive mechanisms. In this case, the server acts as the auctioneer and the clients bid with their local resources. The TheFMMoee system presented in Zeng et al. (022)) uses an auction to select the clients with the best utility--id pair. The authors report a reduction of 45- 68% in the training rounds needed to reach a given accuracy in experiments with various datasets. Jiao et al. (200)) demonstrate that, the auct ion-basde met can be applied in a FL scenario where clients compete for wireless channels. [eng et al. (202aa) measure the learning quality of clients and apply an auction to select the participants. Their method is robust against attacks and achieves 50 80% accuracy in tests where the FedAvg baseline method only achieves 10%.
In contract theory, the server proposes rewards for different client types and the clients select the cluster they fit in according to their local resources. Kang et al. (2019b) separate the different types of clients by their local model accuracy. Their work focuses on maximizing the profit that remains at the server after incentive payout. Lim et al. (2020) also define the client groups based on data quality and quantity. Their experiments show that these methods effectively reward the desired clients and motivate them to participate more than the less relevant ones.
Finally, Reinforcement Learning (RL) has also been proposed for client selection. Wang et al. (2020) frame the client selection process as RL task follows: the server acts as the agent; the state s' 0%00% "i 0ly summarizes the current parameters in each client; the action consists of selecting a client for the next round; and the reward is the sever's side accuracy. In their experiments the proposed FAVOR method reduced the number of communication rounds by 23-49% on bascline datasets. Deng et al. 2021 take the client's 's data quality into account during value generation and show that their method selects fewer and more suitable clients than a simple baseline, achieving 6% better accuracy while being 2x faster. RL. has also been used to implement incentive mechanisms combined with auctions or Stackelberg games. Jiao et al. (2020) implement RL-based auction that outperforms greedy auction by 2 - 5%. Zhan et al. (2020) propose using reinforcement learning to solve the Stackelberg game problem and approximate the equilibrium.
Future work
Regarding utility score-based models, there is a trend to find new, relevant descriptors of the system ssuc as energy in Cho et al.] (2022a), include them in the utility function and show better results than those of previous methods. This trend can be recognized in incentive mechanisms as well, where the reward function is based on the utility of local resources. This line of work suggests potential direction of future work by systematically collecting all the potential parameters and mcasuring their impact on the utility of the clients.
While some progress has been made in terms of contract theory, stale-of-the-arl methods to select contract groups have not investigated all the potential parameters of the clients. Kang et al. (2019b) demonstrate that the number of contract groups impacts the performance, such that would be important to investigate different clustering methods. Additionally, this technique does not address the issue of outliers and of clients in low-value groups which might be discriminated unfairly.
14

---

Published in Transactions on Machine Learning Research (12/2022)
Once the clients have value assigned to them, the server needs to interpret the values to perform the client selection. Thus, the next dimension on our taxonomy is Value Interpretation.
3.6 Value interpretation
At the end of the client valuation step, each client has been assigned a value on the server's side. Based on this value, the server selects the clients that will be part of the next training round.
The clients' values are typically interpreted as rankings, probabilities or weights. When the values are interpreted as ranking, the server selects the top n clients with the highest values (Nishio & Yonetani Wang et al. 2020 Cho et al. 2022b). If they are interpreted as a probability to be selected, the clients are chosen according to such a probability (Goetz et al., 2019 Mohri et al.) 2019 Nagalapatii & Narayanam 2021b. Finally, the values might be considered to be weights that are applied to the clients'
2019
rosults yiclding a weighted sum of client data in the aggregation (Song ct al. 2019 Li et al. 2020
In addition to these three approaches to Value Interpretation, scholars have proposed alternative methods to interpret the clients' data. Chen et al. (2018) propose using a threshold to be applied to the client values, which results in dynamic number of selected clients in cach training round. In their experiments, they report that fewer clients (and hence less communication) are needed as the training progresses, and the training reaches the same accuracy 5x faster and with 10x less communicttion than the baseline. [Kag et al. (2019a) keep a reputation score the clients and only select the clients with a reputation above a pre-defined threshold. They report that increasing this threshold and hence selecting fewer clients boosts the accuracy of the trained model.
Other scholars have proposed clustering the clients according to different criteria (e.g. communication costs, available resources, data characteristics) and only few representatives from each cluster are selected and shared with the server. All the clients in a. cluster are treated in the same way from the server's perspective. Examples include Dennis et al. (2021) who select a reduced mumber of clients from each cluster of similar clients and report 35% less variance in the clients' final lest accuracy when compared to random selection, indicating a possible direction towards Good-Intent Fairness; and Zhou al. (2021) who cluster the clients according to the communication cost with the server.
Note that several methods proposed in the literature leave space for exploration in the process of Value Interpretation. We denote these methods with the symbol & in Table [ In this case, the server selects a subset of the clients according to their value and leaves a predefined number of slots open to add clients which are selected randomly. For example, Goetz et al. (2019) select |S'| clients based on probability and then fill the rest 6 clients by random sampling. With a loss-based value generation function, their [FLG method achieved a 2% area under the curve (AUC) performance increase while needing 30- 70% fewer epochs to reach this performance compared to random selection of clients.
Future work
The final number of participating clients has a impact on the training process. In most cases, this number is defined based on the available resources, such as energy, communication bandwidth or incentive payouts. The Value Interpretation step provides a method to select the number of participating clients depending on such constraints. However, many Value Interpretation approaches require the definition of parameters, such as thresholds or the number of clusters. Thus, automatically identifying the optimal number of participating clients based on their values is still open research problem.
Another direction of future work consists of investigating further the exploration-coploitttii trade-off in client selection. While randomness (i.e. maximal exploration) gives chance to include unseen clients and improves selection fairness, it also reduces the effectiveness of the selection method. Finding the right balance in the pagloratiio-exploittaiin spectrum is an therefore a valuable research question to pursue.
In addition to the six previously described dimensions for client selection in FL, we would like to highlight the importance of establishing benchmark datasets and experimental frameworks to facilitate the reproducibility
15

---

Published in Transactions on Machine Learning Research (12/2022)
Table 2: Commonly used datasets in client selection experiments in FL. Clients are either split by classes, more naturally along feature of the data- for example, by writers of social media posts.
Datasct
Split
Type
Mcthods
S-FedAvg
FAVOR
CI-MR
FMore
MNIST (LeCun
1998
Classes
Image
CBIM
pow-d
FAVOR
FedCS
q-FFL
FashionMNIST
Xiao et al.
2017
Classes
Image
AFLM
F
More
DDaBA
EMNIST Cohen et al.
2017
Classes Writers
Image
FD
FEMNIST
Caldas et al.
20188 8a
Image
R-FED
DDaBA
FL-CIR
FAVOR
FedCS
FD
CIFAR1O Krizhevsky
2009
Classes
Image
Morr
DDaBA
Shakespeare Caldas et al.
2018a
Roles Writers
Text
K-FED
q-FL
Sent140 (Go et al. 2009)
Text
9-FFL
Reddit (multiple varialions
Writers PhD or not
Text
4- -FFF
Oort AFLG
UCT Adult Datasct (Blake 1998
Tabular
Q-FFL
AFLM
London Low Carbon
Saai & Olivadese
2021
Briggs
[Marantes & Openshaw
2012
Households
Timeseries
et al.
2021
Schofield et al. 2015)
of the proposed models and enable the development of comparative analyses. In the next section, we provide summary of the most commonly used datasets in the literature of client selection in FL.
4 Datasets and benchmark experiments
Given the distributed nature of FL and its focus on privacy protection, is difficult to produce and share realistic open-access Federated Learning datasets.
Thus, most of the experiments reported in the FL literature have been performed on artificial FL datasets, generated from well-known benchmark machine learning datasets. Table includes a summary of these benchmark datasets and their characteristics.
Note that creating artificially distributed dataset from originally centralized one requires designer choices to be made. In the current client selection literature even if two papers use the same dataset, the results are in most cases not comparable due to different choices, such as a different distribution of the data. Moreover, the models that are used (e.g. deep neural networks) vary different evaluations, adding another layer of difficulty to make comparisons. Given the low reproducibility of current benchmarks, a fair comparison between methods requires the researchers re-implement and tune each of the relevant past works. The taxonomy proposed in this paper helps to identify the most important methods and their characteristics to enable such a comparison.
In general terms, we find two major approaches to create distributed datasets for client selection in FL. The first approach generates clients based on the taryet classes of a classification dataset. With this method, researchers are able to manipulate the non-IID] nature of the clients yet. the dataset will inherit -potentially unknown- dependencics. For example, in the case of hand-written digits datascts, multiple samples from the same writer. An ideal dataset to simulate realistic client selection experiment would need to have large amount of non clients. Unfortunately, this approach does not seem to satisfy such a condition.
known that there are
In the second approach, the clients are generated based on a fealure of the samples. In this case, the feature may be the writer of the digits in the MNIST datasets or the author of posts in social media platform datascts such as, Scnt140, Reddit listed on Table [ or StackOverflow (Reddi al.) (020). Cross-silo FL scenarios might be simulated by using multiple publicly available datasets and assigning one dataset each of the clients.
16

---

Published in Transactions on Machine Learning Research (12/2022)
In summary, generating FL datasets from known benchmark datasets does not accurately represent the FL. problem at hand, yet obtaining real FI. datasets is challenging. We believe that there might be an alternative path moving forward. There are fields with historically available distributed datasets where privacy concerns are emerging. In these cases, the cxisting data could be leveraged to propose privacy- preserving FL approaches. One of such fields residential energy consumption. Given current global energy market trends, building accurate predictions of energy consumption will be increasingly relevant both for consumers, producers and energy distributors. With the adoption of smart meters, it is possible collect detailed data on the consumers' side. In fact, there are several energy datasets available, such the London Low Carbon project data (Marantes & Openshaw 2012 Schofield et al. 2015). However, analyzing such sensitive data centrally has clear privacy consequences [Vigurs et al.] 2021). Thus, there is an increased need and interest lowards FL techniques applied to this use case (Savi & Olivadese) 2021 Briggs el al. 2021). Other domains that could also benefit from FL include self-driving cars, smart city applications, and wearable IoT deviccs.
Moreover, in many domains there might be several sources of data available to tackle a specific problem. Following the example of the energy consumption prediction problem, in addition to the energy consumption patterns, there are houschold (Schoficld et al. 2015 Wilson 2014) and weather datasets. Rescarch on model- agnostic FL would enable building models that leverage datasets of different nature across clients.
Beyond using non-FL, pre-existing datasets, there are ongoing efforts to develop specific benchmark datasets for FL. First, we would like to highlight that OpenMinded]) has started an initiative to build a network where researchers can access distributed data for FL while preserving privacy. Second, the LEAF framework by Caldas et al. (2018a) collects 6 datasets and defines specific split of the data designed for federated learning.
Regarding baseline models, the reviewed client selection research typically includes the FedAvg algorithm by McMahan et al. (2017) as the baseline. While this offers a much needed standardization in the experimental evaluations, there are more recent federated optimization algorithms that we believe should be considered as baselines, such as Fed and FedAAagrad (Reddi et al.] 2020). We would like to emphasize the importance for scientists embrace an open science approach, sharing both the data and the code of newly proposed modcls. We would also encourage the community to leverage rapidly maturing Federated Learning frameworks -such as, TFF PyShin and Flower to ease the reproducibility of the results and enable the integration of novel client selection strategies into other parts of the federated pipeline, such as FL optimizers, or differential privacy frameworks.
5 Conclusion
As an emergent field, documenting, properly evaluating and comparing novel Federated learning methods a complex task. In this paper, we have provided an overview of the most notable works in client selection in FL. We have proposed a taxonomy to help researchers identify and compare previous approaches and to support practitioners and engineers in finding the most suitable method for their task at hand. Our taxonomy is composed of 6 dimensions to characterize client selection methods: Policies, Termination Condition, Client Characteristics, Shared Information, Value Generation and Value Interpretation.
The Policies, Client Characteristics, Shared Information and Value Generation help identify the most suited method to satisfy the requirements and goals in a specific scenario. Value Interpretation and the Termination Condition are important to characterize the evaluation and enable the comparison of existing methods.
We have also outlined potential lines of future research regarding each of the six dimensions of the proposed taxonomy and highlighted the need for FL benchmark datasets and models to accelerate progress and ease the comparison of proposed approaches in this field. We hope that the proposed taxonomy will prove to be helpful in this regard.
1OpenMinded: The Medical Federated Learning Program. Accussed: 2022-06-14, https:// http::/pppmmmeeeennuaaopppeeeeep hubspottaagebullerr
caa//eediall-federttte--eererrre http:/ddrrrttttteeeeeeeeeeeeeeee program
littps://www http:////wwwwtnsooolooo.oooo www.s//srr....oooro///eeeaaaaaaa
https://github.. http:///ghhubb.ccco/eeeleeeeeeee hctpa///cccceeee/aee//////tttt
https://flover...
17

---

Published in Transactions on Machine Learning Research (12/2022)
Acknowledgements
G.D.N. and N.O. have been partially supported by funding received at the ELLIS Unit Alicante Founda- tion from the Regional Government of Valencia in Spain (Generalital. Valenciana, Conselleria d' d'Innovació, Universitats, Ciència Societat Digital, Dirección General para el Avance de la Sociedad Digital). G.D.N. is also funded by grant by the Banco Sabadell Foundation. N.Q. has been supported in part by Europcan Research Council (ERC) Starting Grant for the project "Bayesian Models and Algorithms for Fairness and Transparenc"", funded under the European Union's 's Horizon 2020 Framework Programme (grant agreement no. 851538).
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Llya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016. 12
Catherine L Blake. Repository of machine learning databasc.
http://wwwn.
ics. uci.
edu/mllerr/MMI Reposiirr hlml, 1998. 16
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with
adversaries: Byzantine tolerant gradient descent. Advances in Newral Information Processing Systems, 30, 2017.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy-preserving machine learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175-1191, 2017.
Christopher Briggs, Zhong Fan, and Peter Andras. Federated learning for short-term residential energy demand forccasting. arXie preprint arXiv:2105.13320 2021.
16 17
Scbastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint
arXiv:1812.00 010097 2018a. [6 17
Scbastian Caldas, Jakub Koncčny, H. Brendan McMahan, and Amoet Talwalkar. Expanding the reach of federated learning by reducing client resource requirements, 2018b. URL http///rxxvv.or//abaa//
07210
25
Tianyi Chen, Georgios Giannakis, Tao Sun, and Wotao Yin. Lag: Lazily aggregated gradient for communication-effle distributed learning. Advances in Neural Information Processing Systems, 31, 2018.
Wenlin Chen, Samuel Horvath, and Peter Richtarik. Optimal client sampling for federated learning. anXiv preprint Xix::20010. 13728, 2020. 9
Hyunsung Cho, Akhil Mathur, and Fahim Kawsar. Flame: Federated learning across multi-device environ-
ments, 2022a. URL https://arxiv abg/abs//e /2002 08922
13
25
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Towards understanding biased client selection in federated learning. In International Conference on Artificial Intelligence and Statistics, pp. 2022b.
PMLR,
12
23
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 international joint conference on neural networks (IJCNN) pp. 2921 2926.
IEEE, 2017.
16
Yongheng Deng, Feng Lyu, Ju Ren, Yi-Chao Chen, Peng Yang, Yuczhi Zhou, and Yaoxue Zhang. Fair: Quality-aware federated learning with precise user incentive and model aggregation. In IEEE INFOCOM 2021-IEFE Conference Computer Communications, pp. 1-10. IEFE. 2021a. 14
18

---

Published in Transactions on Machine Learning Research (12/2022)
Yongheng Deng, Feng Lyu, Ju Ren, Huaqing Wu, Yuezhi Zhou, Yaoxue Zhang, and Xuemin Shen. Auction: Automated and quality-aware client selection framework for efficient federated learning. TEEE Transactions on Parallel and Distributed Systems, 33(8))1996 2009, 2021b. 14
Don Kurian Demnis, Tian Li, and Virginia Smith. Heterogeneity for the win: One-shot lederated clus- tering. In International Conference on Machine Learning. pp. 2611-2620. PMLR, 2021. URL https:
7/proceedings. mlr. pptsss/139/dennnsssseee
html 12
15 23
Enmao Diao, Jie Ding, and Vahid Tarokh. Heteroft: Computation and communication efficient federated
learning for heterogeneous clients. Xiv preprinl arXiv:2010.0126, 2020.
25
John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 429-438. IEEE, 2013. 12
Rosta Parzan, Joan M. DiMicco, David R. Millen, Casey Dugan, Werner Geyer, and Elizabeth A. Brownholtz. Results from deploying a participation incentive mechanism within the enterprise. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, CHI '08, pp. 563 572, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 9781605580111. doi: 10.1145/137706411337155
URL https://doi.. org/10../00 10. 1145/13575554 13357444
1357145
7
Robin C Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arXie preprint or
2017.
Alec Go, Richa Bhayani, and Lei Huang. Twitter sentiment classification using distant supervision. CS224N project report, Stanford, 1112):2009, 2009.
16
Jack Goetz, Kshitiz Malik, Duc Bui, Seungwhan Moon, Honglei Liu, and Anuj Kumar. Active federated learning. arxiv preprint or Xiv: 1 1999. 190..199991111111 12641, 2019. URL.
http://bbs1999...111 12641
Robert W Hahn and Robert N Stavins. Economic incentives for environmental protection: integrating theory and practice. The American economic review, 82(2):464-466, 1992.
Rui Hu and Yanmin Gong. Trading data for learning: Incentive mechanism for on-device federated learning. In GLOBECOM 2020-2020 IEEE Global Communications Conference, pp. 1-6. IEEE, 2020. 14
Yutao Jiao, Ping Wang, Dusit Niyato, Bin Lin, and Dong In Kim. Toward an automated auction framework for wireless federated learning services market. IEFE Transactions on Mobile Computing, 20(10):3034 3048, 2020. 14
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hu- bert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, 'Zacaary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Grutesor, Zaid Harchaoui, Chaoyang Hc, Lie Hc, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mit- tal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Pranecth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Fe- lix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021. ISSN 1935-8237. doi: 10.1561/220000000 URL http://dx...
/oi.. doi, ort..0.gg11111... 15112220002222
II
Jiawen Kang, Zehui Xiong, Dusit Niyato, Shengli Xie, and Junshan Zhang. Incentive mechanism for reliable federated learning: A joint optimization approach combining reputation and contract theory. JEEE
Internet of Things Journal, 6(6):10700-10741 201 9a. 7
12
15
25
19

---

Published in Transactions on Machine Learning Research (12/2022)
Jiawen Kang, Zehui Xiong, Dusit Niyato, Han Yu, Bing-Chag Liang, and Dong In Kim. Incentive design for efficient. federated learning in mobile networks: A contract theory approach. In 2019 IEEE VTS Asia
Pacific Wireless Communications Symposium (APWCS), pp. 1 5. LEEE, 2019b. 7
14
Claire Kremen, John O Niles, MG Dalton, Gretchen C Daily, Paul R Ehrlich, John P Fay, David Grewal, and R. Philip Guillery. Economic incentives for rain forest conservation across scales. Science, 288(5472);
1828-1832, 2000. 7
A Krizhevsky. Learning multiple layers of features from tiny images. Moster's thesis, University of Trond, 2009. [6
Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings, Ivan Krasin, Jordi Tust,,, Shahab Kamali, Stefan Popov, Matteo Malloci, Alexander Kolesnikov, et al. The open images dataset v4. International Journal of Computer Vision, 1998, 2020. 13
Fan Lai, Xiangfeng Zhu, Harsha V. Madhyastha, and Mosharaf Chowdhury. Oort: Efficient federated learning via guided participant selection. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21), pp. 19 35. USENIX Association, July 2021. ISBN 978-1-939133-22-9 URL
usenix. httg://cofeeeeeeeeeaaaa/////epee
13 24
Yann LeCun. The mnist database of handwritten digits. hllp://yamm. lecun. ///ee////////////////m///// 1998. 16
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning.
In International Conference on Learning Represenlations, 2020. URL http:://pppnrreeeeeeeeeeffooroes id-ByexE1SYDr
2 Wei Yang Bryan Lim, Zehui Xiong, Chumyan Miao, Dusit Niyato, Qiang Yang, Cyril Leung, and H Vincent Poor. Hierarchical incentive mechanism design for federated machine learning in mobile networks. IEEE Internet of Things Journal, 7(10):9575 9588, 2020.
7 14
Assar Lindbeck, Sten Nyberg, and Jörgen W Weibull. Social norms and economic incentives in the welfare stale. The Quarterly Journal of Economics, 114(1):1-30 35, 1999.
Ruixuan Liu, Fangzhao Wu, Chuhan Wu, Yanlin Wang, Lingjuan Lyu, Hong Chen, and Xing Xie. No one left behind: Inclusive federated learning over heterogeneous devices. arXiv preprint ar arXiv:2202.08036,
2022.
25
Yuan Liu, Zhengpeng Ai, Shuai Sun, Shuangfeng Zhang, Zelei Liu, and Han Yu. Fedcoin: A peer-to-peer
payment system for federated learning. In Federated Learning, pp. 125 138. Springer, 2020.
Cristiano Marantes and Dave Openshaw. Low carbon london a large scale low carbon smart grid project.
Journal of International Council on Electrical Engineering, 2(2):231 236, 2012. 16 17
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communicaiion-effiiell learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 2273-1282. PMLR, 2017.
17
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International Conference on Machine Learning, pp. 4615 4625. PMLR, 2019. 2
6
12
15
23
24
Lokesh Nagalapatti and Ramasuri Narayanam. Game of gradients: Mitigating irrelevant clients in federated learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 9046 -0544
2021.
12
3
15
23
Albert L Nichols. Targeting economic incentives for environmentaa protection. Massachusetts Institute of Tochnology Press, Cambridge, MA, 1984.
Takayuki Nishio and Ryo Yonctani. Client selection for federated learning with heterogencous resources mobile edge. In ICC 2019 2019 IEEE International Conference on Communications (ICC), pp. 1-7, 2019. doi: 10.1109/ICC.2201
2
15
24
20

---

Published in Transactions on Machine Learning Research (12/2022)
Manisha Padala, Sankarshan Damle, and Sujit Gujar. Federated learning meets fairness and differential privacy. In International Conference Neural Information Processing, pp. 692-699. Springer, 2021. G
Shashi Raj Pandey, Nguyen H Tran, Mehdi Bennis, Yan Kyaw Tun, Zhu Han, and Choong Seon Hong. Incen- tivize to build: A crowdsourcing framework for fedorated learning. In 2019 IEEE Global Communications Conference (GLOBECOM), pp. 6. IEEE, 2019. 7 14
Cran-Fraccois Rajotte, Sumit Mukherjee, Caleb Robinson, Anthony Ortiz, Christopher West, Juan M Lavista Ferres, and Raymond T Ng. Reducing bias and increasing utility by federated generative modeling of medical images using centralized adversary. In Proceedings of the Conference Information Technology
for Social Good, pp. 79 84, 2021. 13
John Rawls. A theory of justice. In Ethics, pp. 229 234. Routledge, 2004. 6
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint orXiv:2003.00295, 2020. 16
Nuria Rodriguez-Barroon Eugenio Martinez-Cámara, M Victoria Luzón, and Francisco Herrera. Dynamic defense against byzantine poisoning attacks in federated learning. Future Generation Computer Systems, 133:1-9, 2022.
Yunus Sarikaya and Ozgur Ercetin. Motivating workers in federated learning: A stackelberg game perspec- tive. IEEE Networking Letters, 2(1):23 2019.
14
Marco Savi and Fabrizio Olivadese. Short-term energy consumption lorecasting at the edge: federated learning approach. IEEE Access, 9:95949 95969, 2021.
16 17
James R Schofield, Richard Carmichael, S Tindemans, Mark Bilton, Matt Woolf, Goran Strbac, et al. Low carbon london project: Data from the dynamic time-of-use electricity pricing trial, 2013. uK Data Service,
SN, 7857(2015):7857 1, 2015. 16 17
Lloyd S Shapley. Noles on the N-person Game I: Characlerislic--oinl Solutions of the Four-person Game
Rand Corporation, 1951. 13
Lloyd S Shapley, Cores of convex games. International journal of game theory, 1(1):11 26, 1971
Yuxin Shi, Han Yu, and Cyril Leung. Towards Wwireess-Aware Federated Learning. arXiv e-prints, art arX1v:2111.01872, November 2021. 0
Tianshu Song, Yongxin Tong, and Shuyue Wei. Profit allocation for federated learning. In 2019 IEEE
International Conference on Big Data (Big Data), pp. 2577- 2577-2586. IEEE, 2019. 7
12
13
15
25
Carol Vigurs, Chris Maidment, Michael Fell, and David Shipworth. Customer privacy concerns as barrier to sharing data about energy use in smart local enorgy systems: rapid realist review. Energies, 14(5):
1285, 2021. 17
Guan Wang, Charlie Xiaoqian Dang, and Ziye Zhou. Measure contribution of participants in federated learning. In 2019 IEFE International Conference on Big Data (Big Data), pp. 2597-2604. IEFE, 2019a.
Hao Wang. Zakhary Kaplan, Di Niu, and Baochun Li. Optimizing federated learning on non-iid data with reinforcement learning. In IEEE INFOCOM 2020-IEEE Conference on Compuler Commanications, pp. 1698-1707. IEEE, 2020.
2 12
14
15
24
Jianxiao Wang, Haiwang Zhong, Junjic Qin, Wenyuan Tang, Ram Rajagopal, Qing Xia, and Chongqing Kang. Incentive mechanism for sharing distributed energy resources. Journal of Modern Power Systems and Clean Energy, 7(4):837-88) 850, 2019b. doi: 10.00071-40665--019-6111-.. 7
21

---

Published in Transactions on Machine Learning Research (12/2022)
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H. Brendan McMahan, Blaise Agüera y Arcas, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, Suhas N. Dig- gavi, Hubert Eichner, Advait Gadhikar, Zachary Garrett, Antonious M. Girgis, Filip Hanzely, Andrew Hard, Chaoyang He, Samuel Horvath, Zhouyuan Huo, Alex Ingerman, Martin Jaggi, Tara Javidi, Pe- ter Kairouz, Satyen Kale, Sai Praneeth Karimireddy, Jakub Konecný, Sanmi Koyejo, Tian Li, Luyang Lūu, Mchryar Mohri, Hang Qi, Sashank J. Reddi, Peter Richtárik, Karan Singhal, Virginia Smith, Mahdi Soltanolkotabi, Weikang Song, Ananda Theertha Suresh, Sebastian U. Stich, Ameet Talwalkar, Hongyi Wang, Blake E. Woodworth, Shanshan Wu, Felix X. Yu, Honglin Yuan, Manzil Zaheer, Mi Zhang, Tong Zhang, Chunxiang Zheng, Chen Zhu, and Wennan Zhu. A field guide to federated optimization. CoRR, abs/2 22211000691, 2021. URL attps://arzxi httpp:///aaiivo.r//bbb//////////
06917
12
Eric Wilson. Commercial and residential hourly load profiles for all tmy3 locations in the united states. Technical report, DOE Open Energy Data Initiative (OEDI); National Renewable Energy Lab.(NREL.
2014. Lirl
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint 0tl:::178.0700 2017. I6
Bangzhou Xin, Wei Yang, Yangvang Geng, Sheng Chen, Shaowei Wang, and Liusheng Huang. Private fl-gan: Differential privacy synthetic data generation based on federated learning. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2927 2931. IEEE, 2020.
Guang Yang, Shibo He, Zhiguo Shi, and Jimnng Chen. Promoting cooperation by the social incentive mechanism in mobile crowdsensing. IEEE Communications Magazine, 55(3):86 -2, 2017. 7
Haibo Yang, Xin Zhang, Prashant Khanduri, and Jia Liu. Anarchic federated learning. In International
Conference on Machine Learning. PMIR, 2022. 23
Miao Yang, Ximin Wang, Hongbin Zhu, Haifeng Wang, and Hua Qian. Federated learning with class imbalance reduction. In 2021 29th European Signal Processing Conference (EUSIPCO), pp. 2174-2178.
IEEE, 2021.
12
Rongfei Zeng, Shixun Zhang, Jiaqi Wang, and Xiaowen Chu. Fmore: An incentive scheme of multi- dimensional auction for federated learning in mec. In 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS), pp.
IEFE, 2020. 2
25
Rongfei Zeng, Chao Zeng, Xingwei Wang, Bo Li, and Xiaowen Chu. comprehensive survey of incentive mechanism for federated learning. arxie preprint arXiv:2106. 15406, 2021.
g
Yufeng Zhan, Peng Li, Zhihao Qu, Deze Zeng, and Song Guo. A learning-based incentive mechanism for federated learning. IEEE Internet of Things Journal, ((7):6360-6368, 2020. 14
Yufeng Zhan, Jie Zhang, Zicong Hong, Leijie Wu, Peng Li, and Song Guo. A survey of incentive mechanism design for federated learning. IEEE Transactions Emerging Topics in Computing, 2021. URL https: //ieeexplore ieee. org/
Yang Zhao, Jun Zhao, Linshan Jiang, Rui Tan, Dusit Niyato, Zengxiang Li, Lingjuan Lyu, and Yingbo Liu. Privacy-preserving blockchain-basee federated learning for iot devices. IEEE Internet of Things Journal, 8(3):1817-1829, 2020.
11
Pengyuan Zhou, Pei Fang, and Pan Hui. Loss tolerant federated learning, arXiv preprint or arXiv:2105.0050 2021.
2
6
2
15 25
Alexander Ziller, Andrew Trask, Antonio Lopardo, Benjamin Szymkow, Bobby Wagner, Emma Bluemke,
Jean-Mickael Nounahon, Jonathan Passeral-Palmmbach Kritika Prakash, Nick Rose, el al. Pysyft: A library for easy federated learning. In Federated Learning Systems, pp. 111-139. Springer, 2021. 9
22

---

Published in Transactions on Machine Learning Research (12/2022)
A Highlighted client selection algorithms
In this section, we provide summary of the client sclection algorithms included in Table and discussed in this paper. These methods have been selected because of their relevance in the field and/or because they represent specific category of our taxonomy.
Baseline selection strategies
The two most commonly used bascline client selection strategics are EqRop and EqW, presented below.
EqRepbaseline
Equal representation of clients (EqReepaaeeline: with total of N clients and [8 selected clients in round the training, each client has is"1 N probability to participate in the round. This approach is often referred to as random client selection. Its motivation to have all clients participating equally. The original FedAvg method use EqReppaseline reduce the number of participating clients.
EqW baseline
Equal weights of data samples (Eq haselina): the probability p: of participation for client ei is proportional to the fraction of data that the client has access to. Thus, to compute the server needs to know the clients' dataset size, [De], Vi = N. The motivation is to achieve equal representation for all data samples in the training.
Methods motivated by improving training efficiency
AFLG
In Active Federated Learning (AFLc) 13 the client e; has valuation in training round t, of, based on its reported loss (Goetz el al.) 2019). If a client participates in training round 6, its valuation is updated, otherwise remains the same as in the previous training round 1- 1, o = o $ St. All the clients start with a negative infinite valuation, o' = -o0, Vc, E K. The value interpretation based on this value with additional clients selected for exploration. The motivation is achieve the same performance the baseline client selection algorithms but with fewer training epochs.
probability function
pow-d
In Power-of- Choic Strategy (pow-d), first a candidate set (A C K) is selected based on the fraction of their data, [Dd (as in EgWWean baselinee. Then the clients in & compute their local losses and report them back to the server. The clients with the highest losses are selected St C A ICho et al. 2022b). This method improves both the convergence rate and the accuracy when compared to random selection (EqRepraseline).
S-FedAvg
In the Shapley-value based federated averaging (S-FedAvg) method proposed by Nagalapatti & Narayanam (2021), the server uses a verification dataset (Dv) to determine the clients' contributions using Shapley values. Then, it selects the clionts with a probability proportional to their contribution value. This mothod reaches higher accuracy than FedAvg
k-FED
In k-FED, local k-mean clustering is proposed to generate compressed data description (Dennis et al, Then, the cluster centroids in each client, G q E K, are sent to the server. The server does not include in the training clients with similar cluster centroids. This approach is evaluated with a combination of pow-d and the results show that it can boost the training convergence even further.
2021 b.
LAG
SAFL refers Agnostic Federated Learning Mohri et al. 2019
Active Federated Learning Gootz et al 2019 and Anarchic
Federated Learning (Yang 20222. We separate them using the initials the first authors, AFLM AFLG and AFI.y
respectively.
23

---

Published in Transactions on Machine Learning Research (12/2022)
The Lazily Aggregated Gradient (LAG) (Chen et al, 2018 method stores previous updates of the clients and predicts their future performance using a Tipschitz-smoottness (4) estimator. In this approach, the updates are computed only on valuable clients as decided by the client or the server. Early stopping is possible if none the clients sends updates. The motivation for the development of this method is to reduce the communication between clients and the server.
FL-CIR
Federated learning with class imbalance reduction (FL-CIR) Yang al. 2021 proposes multi-armed bandit method to select client set with minimum class imbalance. Each client represents an arm, and the selected clients are super-arm (set of arms). The reward of the super-arm is computed based on the results of the current training round. The motivation to reduce the impact of non-IID improve the overall model's accuracy.
hhes hss in the data and hence
FAVOR
Optimizing Federated Learning on Non-IID Data with Reinforcement Learning (FAVOR) Wang al (2020) formulates the client selection problem
RL task, where the server acts agent, the state s' 0", .y summarizes the current parameters in each client, the action consists of selecting a client for the next training round and the reward is the sever-side accuracy. The server has a local validation set (Dv) to evaluate the clients' models. The method's effectiveness demonstrated with experiments where the target accuracy is reached with fewer communication rounds than previous methods.
Other global constrains
In addition to improving the training efficiency, several research works have explored other global constrains to guide the client selection process.
FedCS
Nishio & Yonetani (2019 proposed one of the first client selection methods called Federated Learning with Client Selection (FedCS). The clients report their resource requests to the server in the form of an estimated compute time T. The global constrain is defined maximum compute time per client. Thus, the server selects the clients that fulfill such constrain.
AFLM
Agnostic Federated Learning (AFLM), Mohri et al. (2099) aims to minimize the maximum loss of the clients' performance (good-intent fairness). The server updates distribution function in every training round based on these local losses, and is used to reweigh the samples or select clients that match target data distribution.
QFFFL
q-Fair Federated Learning (q-FFL) aims to achieve uniform accuracy across all clients et et al. (2220). First, the server select clients according to a uniform probability. Then, the server reweighs the client parameters based on the Lipschitz constant (C) of the local loss functions.
Oort
In Oort, Lai et al. 2021 utility scores are used to rank the clients and the server selects the top-K performers. The utility function depends on the local loss and the training time and it is given by: Util(i) = [Bal B, EkeB, I(k)2 x T
(T<T))xa where B, C is a subset of samples in client i; T and
T, are the global and local needed training time, respectively; ((x is r true, otherwise, and a is a hyperparameter. Oort also includes an exploration component to increase the data diversity.
FLAME
24

---

Published in Transactions on Machine Learning Research (12/2022)
Federated Learning Across Multi-device Environments (FLAMEc) _ builds energy profiles for each client and clients have maximum allowed budget of energy consumption. The clients compute their utility scores using the training loss (L), the energy consumption (E') and the required computational time(7). The server selects the clients with the largest overall utility. In their experiments, even though clients have limited energy and therefore, limited participation (Cho et al. 2022a). they achieve... add results
FLAME:
DDaBA
Dynamic Defense Against Byzantine Attacks (DDaBA) [Rodriguez Bordriguez-Barros Barroso et al 2022 tries to identifly ad- versarial clients based on the local update's accuracy the server-side validation set Dy. It flags potentially harmful clients when the accuracy of their local update changes dramatically between rounds. Experiments show that this approach is effective against. byzantine allacks.
Client inclusion policies
Regarding client inclusion policies, we highlight two methods proposed in the literature.
LT-FL
Loss Tolerant Federated Learning (LT-FL) (Zhou et al. 2021 classifies the clients into two categories, depending on whether they have enough resources retrieve lost communication packages or not. The clients in the first group expected to send updated model to the server in all cases. However, the weights of the clients from the second group may be set to zero if their packages get lost.
FD
Federated Dropout (FD) (Caldas et al. 2018b) use model compression (via dropped neurons) to reduce the size of the clients. The dropped neurons are not randomized but computed in such a way have the same smaller matrix dimension each client. Morcover, the server able to map them back together their original model size. This technique increases the server-client communication efficiency while keeping the original prediction accuracy. Later work (Diao et al. 2020 Liu et al. 2022) use the same idea to allow for heterogencous model sizes in clients with different capabilities.
Incentive mechanisms
Finally, we include summary of the three highlighted methods that propose different incentive mechanisms.
CI-MR
In Contribution Index Multi Round Reconstruction (CI-MR), all clients perform their local training and send the results back to the server which weights them depending on the size the local datasets in cach client, similarly to Eg baseline At the end of the training, the server uses Shapley values to determine the data quality of the clients define the payment of their incentive (Song al. 2019).
FMore
FMore: an Incentive Scheme of Multi-dimensional Auction (FMore) Zeng et al. 2020 is an incentive mechanism where the server shares a scoring function (Value Generation function) with the clients, the clients compute their utility scores based on their local resources and offer a bid with a payment proposal. Based on this information, the server selects the clients for that round of training.
CBIM
Contract-Bac Based Incentive Mechanism (CBIM) Kang et al.) 2019a uses contract theory to select the right cluster of clients based on the clients' utility scores. It also keeps track of the reputation of the clients via a blockchain mechanism.
orThere least FI. papers with the FLAME acronym. include the initial the first author subscript differentiate between them.
25


Reviews:
[{"review_id": "kas2CR59Zs", "reviewer": "Reviewer_wdU1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* This submission focuses on an important problem of client selection in federated learning. As there are more and more works in this area, it provides some centralized discussions of the current research efforts.\n* It abstracts the client selection problem into a simple framework which covers most of the existing methods (though with caveats as described later), and provides a taxonomy of different methods, considering different settings (cross-silo/cross-device) and practical constraints (systems and algorithmic requirements).\n* It discusses future works organized into different categories along with the taxonomy of existing work.\n\nWeaknesses:\n* While this is a survey paper focusing on client selection, lots of works discussed are not proposing new client selection methods, but just related to client selection (sometimes very loosely). Large portions of text are disconnected from client selection, but just enumerating existing works on some topics of federated learning (see requested changes below). For example, a large subset of methods listed in In Table 1 and Table 2 are not any specific client selection methods. The technical details of those methods are heavily discussed including their experimental results and exact numbers), but it would be better to focus more on their connections with client selection.\n* One important question—which client selection methods are generally good empirically—remains unanswered. It is still not clear how much better complicated client selection strategies really are compared with random selection. \n* Many issues and future works discussed are generally interesting problems in federated optimization/learning itself, but not closely tied to the problem of client selection.\n* Technical content, organization, and writing need to be largely improved.\n\nMy other concerns are listed in the requested changes.\n\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "\nThis paper gives a snapshot of some recent advances on the client selection problem in federated learning. It provides a taxonomy of different methods, summarizes existing works, and discusses future research questions in client selection. This submission may help both researchers and practitioners get a better view of the research landscape, apply current techniques to the tasks at hand, and inspire future research and adoption.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "* Figure 1: Some algorithms only need one round of communication to perform client selection and get the model updates from selected clients. E.g., they dynamically maintain some (maybe stale) information (e.g., client gradients, client losses) on the server side (e.g., Towards Understanding Biased Client Selection in Federated Learning, Diverse client selection for federated learning via submodular maximization). Hence, this figure cannot represent a class of client selection methods. \n\n* \" Furthermore, it limits the ability of practitioners to apply the most suitable of the existing FL techniques to a specific real-world problem, because it is not clear what the state-of-the-art is in the scenario required by their application\": this question proposed by this submission is not addressed or investigated with evidence.\n\n* Section 3.1.1: The motivation part needs to be better organized/structured. For example, what are the differences between 'training efficiency' and 'limited complexity'?\n\n* Sections 3.1.2 'Client inclusion policies' are more of approaches rather than motivation for client selection.\n\n* Section 3.1.3 has much overlap with other subsections. For example, improving 'global constraints' (training efficiency, fairness) naturally has incentives for clients. Moreover, Section 3.1.3 describes many methods on the problem of client incentive itself, but it is not clear how client selection can serve as incentivization mechanisms, and what previous works have done on this front. It is clear that client selection is related to incentive mechanisms, but this subsection is only talking about incentive mechanisms, which is disconnected from the 'motivation' of client selection.\n\n* Future work after Section 3.1.3: Several proposed future motivations are not convincing. The paragraph on privacy is arguing that future research should consider privacy as a metric when designing client selection methods, but for this point to be future work for 'motivation', the paper needs to discuss why different client selection methods can improve privacy/utility tradeoffs (which I am not sure to what extent this is true). \n\n* In terms of reliability (bottom of Page 7): (a) It is not clear what reliability means in this paragraph. From the last sentence regarding clustering, it seems that reliability can mean representation fairness, which has already been discussed in existing works.\n(b) Moreover, selecting clients from each cluster has been explored in previous works (e.g., Heterogeneity for the Win: One-Shot Federated Clustering), which shouldn't be included as future work.\n\n* The last two paragraphs of Section 3.1: The current text talks about future directions in improving client selection strategy and evaluation of incentive mechanisms, but not necessarily the future work of the 'motivation for client selection'.\n\n* Section 3.2: (a) The problem of termination conditions broadly exists in iterative methods (not necessarily machine learning). I do not think the two conditions discussed (fixed rounds and certain accuracy) are conditions that are particularly interesting for the problem of client selection. Hence, it is not necessary to include them in the current manuscript. (b) The proposed termination conditions (based on privacy budget and client-centric) are reparameterization of the existing conditions. For example, to satisfy a privacy budget, one practical implementation is to calculate the number of rounds under a privacy loss, and run the fixed number of rounds.\n\n\n* Section 3.3: In future work, the arguments made in the first paragraph (considering client states) have been proposed before (A Field Guide to Federated Optimization).In addition, using over-selection to address client dropout is actually a standard and default practice of federated methods, not future work.\n\n* Section 3.5: I do not think it is necessary to list the exact numbers in previous works, as each paper has different experiment setups and it is impossible to reason about those numbers. This applies to other parts of the submission as well.\n\n* Section 4: The discussions are very generic to FL, instead of client selection. \n\n\n", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EIfJaFIZbc", "reviewer": "Reviewer_Tz1r", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I liked a lot a thoughtful analysis of each part in the taxonomy and ideas for the future work which I mostly agree with.\n\nThe split between client and server level is also useful and very practical, e.g. the engineer/researcher might decide which part to implement.\n\nHowever, I'd ask for some clarification on the following parts:\n\n1. **Privacy**:\n    - What are the privacy definitions that are used in the paper? Client selection is inherently privacy-sensitive operation which might leak different attributes of user data including metadata such as user participation patterns or reaction to incentives (as one of the client selection methods). \n\n    - I'd maybe dedicate a part in the background on a definition for privacy loss or specify at each discussion what exactly the conversation is about. Even the basic notion, i.e. who is the adversary and that learning more about the user data than before participating in FL is privacy leakage (i.e. following differential privacy definition).\n\n    - After the definition it will be really interesting to point that some of the server-side methods specifically target the privacy leakage to rank the users.\n\n2. **Limitations with other FL techniques**\n    - Differential Privacy assumes randomized sampling (with some relaxation) and might limit some of the methods.\n    - Secure Aggregation and Local Differential Privacy are both very popular in FL literature but to me seem like incompatible as the server will have no visibility into user updates (in case of SA) or no ability to analyze the update as it will be similar to noise (LDP).\n\n3. **Trustworthiness**\n    - In general, any client-selection will motivate the attacker to game the selection protocol. \n    - Note on accuracy: the attacker might provide high accuracy for the update, but still be malicious, e.g. inject a backdoor. Also some clients might provide low accuracy and still be useful (especially in non-iid case).\n    - Some defenses might be abused by the attacker (if they manage to abuse client selection protocol). For example, the cited method (Krum by Blanchard et al, 2017) selects clients with the smallest weight update is vulnerable to adaptive attacks. It can be abused by injecting a backdoor with a very small learning rate, and therefore small weight update. The server will then be selecting this client over other benign clients.\n\n4. **Datasets**\n    - I'd emphasize even further that performing client selection on MNIST-like datasets is not the most convincing experiment. \n    - Maybe to balance it out, it's also useful to acknowledge that achieving convergence on Reddit is a computationally expensive task. \n    - Another popular dataset in FL not referenced yet is StackOverflow, might be useful for the researchers.\n\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper provides an overview of common works on client selection in Federated Learning. The review is thorough and provides a taxonomy to classify the papers and makes observations on lack of comparisons and common benchmarks. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Addressing above questions would significantly strengthen the submission.", "broader_impact_concerns": "The work has a strong potential to have an impact on application of FL. Engineers and researchers might use this work to decide on client selection methods. The quality of writing and presentation are also high.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3lmewy29CB", "reviewer": "Reviewer_AwBe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The survey is complete. It covers most selection algorithms to date.\n2. The proposed taxonomy is detailed and catches important features in FL.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a systematic study of client selection algorithms in federated learning. It proposes a taxonomy to organize and classify existing selection algorithms and compare their pros and cons.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "N/A", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a well-defined taxonomy for the important sub-problem of client selection in federated learning. This work will make future research in this area more valuable, interpretable, and comparable. The reviewers were all positive about the paper, and the authors did a good job of addressing the reviewers' comments in the revised manuscript. Overall, this paper is ready to be accepted and I also recommend it for a survey certification.
Decision: Accept (poster)