Client Selection in Federated Learning: Principles, Challenges, and Opportunities

In plain words

Federated learning trains one model across many devices, such as phones, and only the model updates leave each device. In each round the server picks some devices to take part. Picking at random ignores that some devices have more useful data, and some are slow or have poor connections.

This paper is a survey of the ways researchers score each device and choose the best ones. A device gets a score for how useful its update is likely to be, multiplied by a score for how fast and cheap it is to use. The paper groups the existing methods by the signal they use, lists the frameworks people use to test them, and explains what is still unsolved. It is a guide for choosing a method and a list of open questions. It does not propose a new method and does not run experiments.

TL;DR

Survey of federated learning client selection (arXiv v2). The core rule is an overall utility per client: a statistical part times a system part, with the top-scoring clients chosen each round §4 eq. 1. The paper lists 15 representative methods tab. 1, the frameworks used to test them §5.2, and open problems such as availability, exploration, theory and benchmarks §6 §7. It reports no experiments of its own.

Problem

Clients in cross-device federated learning differ in hardware, network speed, availability and data §1 §3. Random selection ignores this difference, and the paper cites a study of 136k smartphones in which device heterogeneity lowered accuracy by up to 9.2% and increased convergence time 2.64X §3. A client selection rule has to measure each client's usefulness and speed, and these measurements are hard to make: a client's utility is usually known only after it has trained, so it must be forecast beforehand §4.3.

Method

The paper's organising idea is that choosing clients means ranking them by a utility score, and that the overall utility is a product §4 eq. 1:

Util(i) = Util_{stat}(i) \times Util_{sys}(i) eq. 1

The paper says other factors such as fairness, robustness or privacy can be written the same way, and that a multiplicative form can ignore a term by setting it to 1 §4.4. Eiffel uses an additive, weighted sum instead §4.4.

Step 1. Statistical utility (usefulness of a client's update) §4.1. Two families are listed.

• Data-sample based §4.1.1:
  • client data size, |D_i|, which the paper says is valid when samples are equally informative, e.g. IID data eq. 2;
  • an importance-sampling optimum, which it calls "one optimal solution", based on the squared gradient norm of each sample. The paper says this is very costly to compute eq. 3;
  • a loss-based approximation of that optimum: the sample count times the root mean square of the per-sample losses, which it attributes to Oort, since large loss tends to mean large gradient eq. 4;
  • the cumulative loss of the client's samples, used by POWER-OF-CHOICE eq. 5.
• Model-based §4.1.2: each measure compares the client's model or update with the global model:
  • normalized divergence, the mean relative difference of weights eq. 6;
  • sign agreement, the fraction of weights with the same sign as the global model eq. 7 (the paper notes a study that prefers the lower value);
  • a layer-wise cosine of weight movement, from FCFL eq. 8;
  • the norm of the change in weights during local training eq. 9;
  • the L2 norm of the local gradients eq. 10;
  • the inner product of local and global gradients, where FOLB and FedPNS drop clients with a negative product eq. 11.

Step 2. System utility (speed) §4.2.

• Hard deadline. A client counts only if its round time is below T, the indicator 1(t_i < T) eq. 12. t_i is the total round time: local training, transmission and compression §4.2.
• Soft deadline (Oort). Stragglers are not removed but scaled down by (T / t_i) raised to alpha, which equals 1 for clients inside the deadline eq. 13. The paper leaves the value of alpha unstated.
• T can measure other things than time, such as FLOPs or bandwidth §4.2.
• FedBalancer adjusts T automatically §4.2.

Step 3. Scheduling §4.3. Utility is multiplied out per client eq. 1. Because a utility is only known after training, a method forecasts it over training and corrects the forecast once the client has joined a round. The scheduler then faces an exploitation-exploration choice, discussed in §6.

The generic round, reduced to pseudocode from §4 and §4.3:

# Utility-based client selection, one training round  [§4.3] [eq. 1]
# Input:  clients (N); M clients per round [tab. 3]; deadline T [§4.2]
# Output: the M selected clients

def select_round(clients, M, T):
    # Overall utility = statistical x system part  [eq. 1]
    for client in clients:
        # Forecast if not yet trained, else use the measured value  [§4.3]
        stat = statistical_utility(client)
        sys = system_utility(client, T)  # [eq. 12] or [eq. 13]
        util[client] = stat * sys
    # Choose the highest-utility clients; the paper does not give a rule
    # for how M interacts with exploration  [§4.3] [§6]
    selected = top_m(util, M)
    return selected

Loss-based statistical utility and the soft-deadline penalty:

# Loss-based statistical utility  [eq. 4] [§4.1.1]
# Input:  losses: per-sample losses from local training, length |B_i|
# Output: scalar utility

def statistical_utility(losses):
    # |B_i| is read as the sample count; "batch" and "bin" are both used
    # for B_i in the text  [tab. 3] [§4.1.1]
    count = len(losses)
    # Root of the mean squared loss, times the count  [eq. 4]
    mean_square = sum(loss * loss for loss in losses) / count
    return count * sqrt(mean_square)

# Soft-deadline system utility (Oort-style)  [eq. 13] [§4.2]
# Input:  round time t_i; deadline T; exponent alpha (value not stated)
# Output: factor in (0, 1]

def system_utility(t_i, T, alpha):
    # 1 for clients inside the deadline; below 1 for stragglers  [eq. 13]
    if t_i > T:
        return (T / t_i) ** alpha
    return 1.0

Hyperparameters

The paper is a survey and sets no training hyperparameters. The values below are the ones it states or quotes.

Results

Not applicable. The paper is a survey and reports no experiments of its own. Its only numbers are quoted from other work, and the paper does not verify them:

Table 1 of the paper lists the 15 selected works. The "System" and "Data" columns are the authors' tags for whether the work targets system or data heterogeneity. Descriptions below are condensed from the table.

Figure 1 fig. 1 shows a standard FL round in four steps: download from server to clients, local training, upload to the server, and aggregation.

Paper vs code

No official code.

The paper has no code and no project page. Its abstract, body and TeX source contain no repository link, and the arXiv metadata has no comment field. A GitHub repository search for "federated client selection survey" returned one third-party paper list on wireless FL (xin-ying-z/federated-learning-in-wireless-communication-paper-survey), which is not by the authors and is not used.

Pitfalls

• No experiments. All numbers in this card are quoted from other works and were not checked. Comparisons across the 15 methods are qualitative §7.3.
• Narrow scope. The paper includes only work with explicit utility and scheduling decisions, the standard server-client setting, and no hierarchical, serverless, reinforcement-learning or fuzzy-logic selection §2.2 §8. Those methods are not covered and should not be read into the rules above.
• Search bias. The corpus is the first 20 results from three libraries plus citation chasing, and it ended at 15 papers §2.2. The novelty claim, "the first overview paper" §1, is the authors' own and was not checked.
• Contradictory evidence. Some work prefers clients whose models diverge most from the global model, and some shows the opposite §7.2. The sign-agreement measure is one example where the cited study favours the lower value §4.1.2. Do not assume "more divergent is better" without checking the source.
• Notation. Table 3 defines B_i as "a batch of data samples", the text calls it a "bin" §4.1.1, and eq. 4 uses |B_i| as a count. Read it as the client's sample set and confirm against the source before implementing.
• Undetermined constants. The Oort penalty exponent alpha eq. 13 and the deadline T have no value on the card, and the paper does not say how to choose them beyond "manually determining the deadline could result in inferior performance" §4.2.
• Strict inequality. Eq. 12 keeps clients with t_i < T strictly, while the text says clients with a deadline "longer than T" are removed §4.2. Eq. 13 gives 1 at t_i = T, so the two definitions disagree at the boundary.
• Eq. 3 cost. The paper calls the exact per-sample gradient version "overwhelming" to compute §4.1.1. Eq. 4 is a stand-in whose justification, that large loss implies large gradient, is cited, not derived §4.1.1.
• Eq. 1 is a choice. The multiplicative form is presented as expressive; no experiment in the paper compares it with other forms §4.4.
• Source discrepancy. The TeX source contains a commented-out older figure of 2.32X for convergence time. The live text says 2.64X, and this card uses the live text §3.

Lineage

• Builds on: the utility functions above come from Oort §4 and PyramidFL §4, and the frameworks come from FedScale, TFF, LEAF and FedML §5.2.
• Compared against: eight general FL surveys (data partitioning, communication, IoT, privacy) that the paper says touch client selection only briefly tab. 2.
• Related variants named but not covered: hierarchical, cluster-based, online and serverless FL §7.4.
• Superseded by: not known from content in this wiki.