Client selection in federated learning

Overview

In cross-device federated learning, the server cannot use every client in every round. Clients differ in hardware, network speed, availability and data, and random selection ignores all of this 2211.01549 §1, §3. The problem is to decide, each round, which clients to ask for an update.

The shared idea is to score each client and take the highest scores. The overall score is a statistical utility (usefulness of the client's update) multiplied by a system utility (speed) 2211.01549 §4, eq. 1. A client's usefulness is usually only known after it has trained, so methods forecast it beforehand and correct the forecast once the client has joined a round 2211.01549 §4.3. The survey that this page draws on is Client Selection in Federated Learning: Principles, Challenges, and Opportunities. It is a survey with no experiments of its own, so the page describes the design space and does not rank the methods.

Variants

Statistical utility from data samples

The score uses facts about the client's local samples 2211.01549 §4.1.1:

• Client data size. The number of samples is a valid proxy when samples are about equally informative, for example under IID data [arxiv:2211.01549 eq. 2].
• Exact importance-sampling optimum. Scores each sample by the squared norm of its gradient. The survey calls this the best solution in principle but very costly to compute 2211.01549 eq. 3, §4.1.1.
• Loss-based approximation. Uses the sample count times the root mean square of the per-sample losses, attributed to Oort on the reasoning that a large loss tends to mean a large gradient. The survey states this as a cited reasoning, not a derivation 2211.01549 eq. 4, §4.1.1. Card: Client Selection in Federated Learning.
• Cumulative loss. Used by POWER-OF-CHOICE 2211.01549 eq. 5.

Statistical utility from the model

These measures compare the client's model or update with the global model 2211.01549 §4.1.2:

• normalized divergence of the weights 2211.01549 eq. 6;
• sign agreement, the share of weights whose sign matches the global model 2211.01549 eq. 7;
• a layer-wise cosine of weight movement, from FCFL 2211.01549 eq. 8;
• the norm of the weight change during local training 2211.01549 eq. 9;
• the L2 norm of the local gradients 2211.01549 eq. 10;
• the inner product of local and global gradients. FOLB and FedPNS drop clients whose product is negative 2211.01549 eq. 11.

System utility: hard or soft deadline

• Hard deadline. A client scores only if its round time is below a deadline T. The indicator is 1 for clients inside T and 0 otherwise [arxiv:2211.01549 eq. 12]. The round time covers local training, transmission and compression 2211.01549 §4.2.
• Soft deadline (Oort). Stragglers are scaled down rather than removed. The factor is (T / t_i) raised to a power alpha, and equals 1 inside the deadline 2211.01549 eq. 13. The survey does not state a value for alpha.
• Other measures. The deadline can measure FLOPs or bandwidth instead of time. FedBalancer adjusts T automatically 2211.01549 §4.2.

Combining the terms

• Multiplicative (eq. 1). The survey says other factors, such as fairness, robustness or privacy, fit the same form, and that a term can be ignored by setting it to 1 2211.01549 §4.4.
• Additive, weighted. Eiffel sums its terms with weights instead 2211.01549 §4.4.

When to use which

Choices are based on the constraints the survey discusses. The survey reports no experiments comparing these choices, so none of the rows below is a measured ranking.

Methods that are hierarchical, serverless, reinforcement-learning based or fuzzy-logic based are outside the survey's scope 2211.01549 §2.2, §8. Do not apply the rules above to them without checking their own sources.

Implementation sketch

A round-level sketch that follows the survey's structure: compute each client's utility, then keep the top M. Stat and sys are the choices above; the survey does not fix how M interacts with exploration 2211.01549 §4.3, §6.

# Score every client for this round  [arxiv:2211.01549 eq. 1]
# Input:  clients, number to pick M, deadline T [arxiv:2211.01549 §4.2]
# Output: ids of the M selected clients

def pick_clients(clients, M, T):
    scores = {}
    for c in clients:
        # Use the measured value if the client has trained, else a forecast
        # [arxiv:2211.01549 §4.3]
        stat = statistical_term(c)
        # Speed term: soft or hard deadline  [arxiv:2211.01549 eq. 12, eq. 13]
        sys = speed_term(c, T)
        scores[c.id] = stat * sys
    # Highest scores join the round  [arxiv:2211.01549 §4.3]
    return top_m_ids(scores, M)

# Soft-deadline speed term (Oort style)  [arxiv:2211.01549 eq. 13]
# Input:  t_i round time, T deadline, alpha penalty exponent (not stated)
# Output: factor in (0, 1]

def speed_term(t_i, T, alpha):
    # Stragglers are scaled down, not removed  [arxiv:2211.01549 §4.2]
    if t_i <= T:
        return 1.0
    return (T / t_i) ** alpha

Contradictions

• Divergence direction. Some work prefers clients whose models diverge most from the global model, and other work shows the opposite [arxiv:2211.01549 §7.2]. For sign agreement, the cited study favours the lower value 2211.01549 §4.1.2. The survey does not resolve this.
• Deadline boundary. Eq. 12 keeps clients with t_i strictly below T, while the text describes removing clients whose time is longer than T. Eq. 13 gives 1 at t_i = T. The text and the two equations disagree at the boundary 2211.01549 §4.2, eq. 12, eq. 13.
• Quoted figures. The heterogeneity figures (accuracy drop up to 9.2%, convergence time 2.64X longer) come from one cited smartphone study and were not verified by the survey 2211.01549 §3. Gboard's 100 clients per round and about 2-minute deadline are one project's values, not general settings 2211.01549 §4.2, §7.1.

Papers

• Client Selection in Federated Learning: Principles, Challenges, and Opportunities: survey of utility-based client selection, its formulas, 15 representative methods and open problems. No experiments of its own.