Selection Policy

The core of any selection policy is its utility function, a mathematical formula that quantifies the expected benefit of selecting a specific client. This function balances multiple, often competing, objectives:

• Statistical Utility: Prioritizes clients whose data will most improve the global model, often measured by local loss or gradient norm.
• System Efficiency: Favors clients with strong computational resources, stable network connections, and high battery levels to reduce straggler mitigation overhead.
• Fairness: Incorporates constraints to prevent systematic under-representation of certain device types or data distributions, a key aspect of bias mitigation. The policy's behavior is entirely dictated by how this utility is defined and calculated.

A primary challenge in federated edge learning is the vast edge device heterogeneity in compute, memory, battery, and connectivity. An effective selection policy must be resource-aware.

• It profiles clients to understand their capabilities (client profiling).
• It selects participants that can complete training within a deadline, a core idea of frameworks like FedCS.
• It may use client clustering to group similar devices, enabling tiered selection strategies like TiFL to ensure all device classes contribute without causing excessive delays. This characteristic ensures the federated process is practical and efficient in real-world, constrained environments.

The best clients for training evolve over time. Sophisticated policies treat client selection as an online learning problem, often framed as a multi-armed bandit.

• The policy explores by selecting new or infrequently chosen clients to gather information about their utility.
• It exploits by frequently selecting clients known to provide high-quality updates or fast completion.
• Frameworks like Oort explicitly implement this by continuously updating a client's utility score based on its recent statistical and system performance. This adaptive characteristic allows the policy to respond to changing data distributions and device conditions.

To build a robust global model that generalizes well, the selected cohort must reflect the overall data landscape. This is the goal of achieving client diversity.

• Stratified sampling ensures participants are drawn from all major data distributions or device types.
• Policies may use federated coresets (small, representative data subsets) to guide selection toward clients whose data fills gaps in the current global model's knowledge.
• Without this characteristic, selection can lead to bias, where the model overfits to the data of a frequently selected, non-representative subset of devices.

Edge environments are unreliable. A robust selection policy is designed to handle client dropout and the presence of Byzantine clients.

• It often selects more clients than strictly needed, anticipating that some will drop out.
• It may incorporate lightweight verification steps or reputation systems to deprioritize clients with a history of failure or malicious behavior.
• For asynchronous FL selection, the policy must decide whether to wait for a potentially slow but valuable client or to aggregate available updates immediately. This characteristic ensures training progress despite inevitable system faults.

While the server defines the policy, its execution often involves a negotiation with client devices, respecting their local constraints and privacy.

• The server broadcasts client eligibility criteria (e.g., minimum battery, required data size).
• Eligible clients may then bid for participation by reporting a summary of their utility (e.g., data size, estimated compute time), a process that can be made privacy-preserving.
• The final client scheduling decision is made by the server, but informed by client-reported metadata. This characteristic balances system-wide optimization goals with the decentralized, autonomous nature of the federated edge.

The baseline strategy where participants are chosen uniformly at random from the available pool. It is simple, unbiased, and provides strong theoretical convergence guarantees under ideal conditions (IID data). However, it ignores system heterogeneity (slow devices can become stragglers) and statistical heterogeneity (non-IID data), often leading to slower convergence in real-world deployments.

A strategy that prioritizes devices based on their available computational power, memory, battery level, and network bandwidth. The goal is to improve system efficiency by reducing round completion time and mitigating stragglers. Common metrics include:

• Estimated time to compute an update.
• Available energy budget.
• Uplink bandwidth. Frameworks like FedCS (Federated Learning with Client Selection) formalize this approach using resource reporting and deadline-based selection.

A heuristic that improves upon pure random selection. In each round, the server evaluates a small random subset of clients (e.g., d clients) and selects the one with the highest utility (e.g., largest local dataset, highest gradient norm). This simple exploitation step significantly accelerates convergence speed compared to random selection, as it biases selection towards clients likely to provide more informative updates, while maintaining low overhead.

A pragmatic client selection framework that jointly optimizes for statistical utility and system efficiency. Oort uses a utility function that combines:

• Statistical utility: Prioritizes clients with higher local training loss, indicating their data is poorly fit by the current global model.
• System efficiency: Favors clients with shorter expected training durations based on profiled resources. By dynamically balancing these factors, Oort achieves faster time-to-accuracy targets in heterogeneous environments.

An approach that incorporates fairness constraints to prevent the systematic under-representation of certain device groups or data distributions. This mitigates bias in the global model. Techniques include:

• Stratified sampling: Ensuring minimum participation from predefined strata.
• Fairness metrics: Enforcing selection based on metrics like client diversity or demographic parity.
• Credit-based systems: Tracking historical participation to guarantee long-term fairness. The goal is to produce a model that performs equitably across all client populations.

Models client selection as an online learning problem. Each client is an arm of a bandit. Pulling an arm (selecting a client) yields a stochastic reward (e.g., improvement in global model accuracy). Algorithms like Upper Confidence Bound (UCB) or Thompson Sampling balance:

• Exploration: Selecting lesser-known clients to gather information.
• Exploitation: Selecting clients known to provide high rewards. This formulation is effective for learning an optimal selection policy over time in non-stationary environments.