Client Scoring

This factor assesses the statistical utility of a client's local dataset. Key metrics include:

• Local Dataset Size: Larger datasets often provide more informative gradients.
• Data Distribution: Proximity to the global or target distribution (e.g., using KL divergence).
• Label Quality & Noise: The presence of clean, correctly labeled data versus noisy or mislabeled samples.
• Data Freshness: How recently the data was generated, critical for time-sensitive tasks.

Example: A scoring function may compute a data utility score as log(dataset_size) * (1 - distribution_divergence).

This factor evaluates a client's hardware and network capability to complete training efficiently and avoid becoming a straggler. It includes:

• Compute (CPU/GPU/TPU): Available processing power and memory.
• Battery Level & Power State: Critical for mobile/IoT devices; a low-battery device may be deprioritized.
• Network Bandwidth & Latency: Current and predicted uplink speed for transmitting model updates.
• Storage Availability: Sufficient space for the model and training data.

Scoring here directly impacts round completion time and system-wide efficiency.

This factor tracks a client's past behavior to predict future performance and ensure system stability. Metrics include:

• Update Norm Magnitude: Historical significance of the client's gradient updates.
• Completion Rate: Frequency of successfully returning updates after selection.
• Latency History: Consistency in meeting round deadlines.
• Contribution Valuation: Calculated Shapley value or similar to quantify marginal impact on global model accuracy.

This creates a reputation system, rewarding reliable participants and deprioritizing unreliable or malicious ones.

This factor uses real-time model performance on the client to gauge training potential. It requires lightweight, privacy-preserving computation:

• Local Training Loss: Clients with higher loss may have more to contribute to model improvement.
• Gradient Norm: The magnitude of the local update, often used as a proxy for update significance.
• Model Drift: The difference between the client's local model and the global model.

Frameworks like Oort explicitly optimize for statistical utility (loss) alongside system efficiency. This requires clients to perform a quick forward/backward pass to compute the signal.

This factor ensures the selected cohort is representative and prevents systematic bias. It incorporates:

• Client Demographics: Ensuring selection across device types, geographic locations, or user groups.
• Data Distribution Coverage: Actively selecting clients to increase the diversity of data seen by the global model.
• Temporal Fairness: Preventing any single client from being over-selected, which can drain its resources.

Techniques like stratified sampling or adding a recency penalty to the score enforce these constraints, mitigating selection bias in the final model.

This factor evaluates client trustworthiness to defend against adversarial participants. It uses:

• Byzantine Detection Signals: Anomaly scores based on the similarity of a client's update to others (e.g., using cosine similarity or median-based filters).
• Attestation & Authentication: Verification of client hardware/software integrity.
• Privacy Compliance: Confirmation that local training adheres to required differential privacy bounds.

The score can incorporate a trust weight, severely downgrading or excluding clients flagged by these security heuristics.

The client score is computed by a utility function U(c) that maps client metadata to a scalar value. This function is the central policy lever. Common inputs include:

• Statistical Utility: Local loss value, gradient norm, or data distribution divergence.
• System Efficiency: Available compute (FLOPs), memory, battery level, and network bandwidth.
• Historical Contribution: Past participation rate, update quality, or Shapley value approximation.
• Data Quality: Label noise estimates, dataset size, or feature richness. The function is often a weighted sum, U(c) = w1 * Statistical(c) + w2 * System(c), where weights are tuned for the training objective.

TiFL (Tier-based Federated Learning) tackles system and statistical heterogeneity by grouping clients into tiers based on their historical training performance (e.g., accuracy or loss improvement). Scoring and selection occur within tiers:

• Clients are scored relative to others in their same performance tier.
• Each round, participants are selected proportionally from each tier. This tier-based scoring ensures that slower clients (often in lower tiers) are not perpetually starved, promoting fairness and preventing bias towards only the fastest or most data-rich devices. It improves model accuracy on underrepresented client data distributions.

Power-of-choice is a simple yet powerful scoring heuristic. In each round:

1. The server randomly samples a small subset d of available clients (the candidate pool).
2. It scores each client in this pool using a simple metric, typically the size of the local dataset.
3. It greedily selects the top k scorers from this pool for training. By scoring and choosing the best from a random pool, it achieves a favorable bias towards clients with more data without the overhead of scoring the entire population. This method provably accelerates convergence compared to purely random selection.

Client scoring can be framed as a Multi-Armed Bandit (MAB) problem, where each client is an "arm." The server learns a scoring policy online:

• Reward: The improvement in global model performance after aggregating the client's update.
• Exploration: Trying clients with uncertain scores to gather more information.
• Exploitation: Selecting clients currently believed to have the highest scores. Algorithms like Upper Confidence Bound (UCB) or Thompson Sampling are used to maintain and update scores, balancing the need to learn client utilities with the need to train an effective model. This is effective in non-stationary environments where client utility changes over time.

Client selection is the overarching process of determining which edge devices or data silos participate in a given training round of federated learning. It is the decision-making framework within which client scoring operates.

• The primary goal is to improve training efficiency and model convergence by selecting a beneficial subset from a large, heterogeneous pool.
• Strategies range from simple random sampling to complex optimization algorithms that consider multiple, often competing, objectives.

A utility function is a mathematical formula that quantifies the expected benefit of selecting a specific client for a federated learning round. It is the formal mechanism that combines various scoring factors into a single, comparable value.

• Common inputs include data quality metrics, resource availability, and historical contribution.
• The function defines the trade-offs between objectives like model accuracy, training speed, and fairness. For example: Utility = α * (Data Quality) + β * (1 / Expected Training Time).

Client profiling is the process of collecting, maintaining, and updating metadata about federated learning clients. This metadata forms the raw data used for client scoring.

• Profiles typically include:
  • Hardware capabilities (CPU, memory, NPU)
  • Network conditions (bandwidth, latency)
  • Data statistics (dataset size, label distribution)
  • Historical behavior (past participation, reliability, dropout rate)
• Profiling enables predictive scoring, allowing the server to estimate a client's utility before selection.

Resource-aware selection is a client selection strategy that prioritizes devices based on their available computational resources, battery level, and network bandwidth. It is a primary objective often encoded in a client scoring function.

• The goal is to minimize stragglers—clients that delay round completion—and improve overall system efficiency.
• Scoring might penalize devices with low battery or slow connections, or favor those with dedicated neural processing units (NPUs) for faster local training.

Oort is an influential client selection framework that pioneered the joint optimization of statistical utility and system efficiency. It exemplifies an advanced scoring and selection system.

• Oort scores clients by combining:
  1. Statistical utility: Measured by the client's local training loss, indicating the potential to improve the global model.
  2. System efficiency: Based on the client's resource profile and past training duration.
• It uses an adaptive exploration-exploitation strategy to balance selecting known high performers with discovering new, potentially valuable clients.

Straggler mitigation refers to techniques designed to prevent or manage slow or unresponsive clients from delaying a federated learning round. Effective client scoring is a key proactive mitigation strategy.

• Beyond scoring, other techniques include:
  • Deadline-aware selection: Only choosing clients that can complete work within a time window.
  • Asynchronous aggregation: Proceeding without waiting for all clients.
  • Model compression: Reducing the communication load for bandwidth-constrained clients.
• Poor scoring that ignores resource constraints directly leads to increased stragglers and wasted compute cycles.