Sources of Heterogeneity: Statistical and System

"While the foundational Federated Averaging (FedAvg) algorithm offers a framework for collaborative model training, it operates best under idealized conditions that rarely hold true in practice. Federated networks are characterized by significant variability among clients, a phenomenon broadly termed heterogeneity. Understanding the different facets of heterogeneity is essential for designing effective federated learning systems. We primarily distinguish between two types: statistical heterogeneity and system heterogeneity."

Statistical Heterogeneity (Non-IID Data)

Statistical heterogeneity refers to the differences in the underlying data distributions across participating clients. In an ideal Independent and Identically Distributed (IID) scenario, each client's local dataset $D_k$ would be drawn from the same global data distribution $P(x, y)$. However, in most practical applications, the data distribution on client $k$, denoted as $P_k(x, y)$, differs significantly from the global distribution and from the distributions on other clients ($P_{k'}(x, y)$ where $k \neq k'$). This is often called Non-IID data.

Sources:

• User Behavior and Preferences: In applications like mobile keyboard prediction or recommendation systems, users have distinct vocabularies, interests, and interaction patterns.
• Geographic Location: Data collected from different regions might reflect local languages, demographics, or environmental conditions (e.g., sensor data).
• Time: Data collected at different times can exhibit temporal shifts or seasonality.
• Device Specificity: Different devices might capture data differently (e.g., camera sensors, microphone quality).
• Data Partitioning: In cross-silo settings, organizations naturally hold data representing different populations or business segments (e.g., hospitals specializing in different areas).

Manifestations: Non-IID data can appear in several ways:

1. Feature Distribution Skew: $P_k(x)$ differs across clients, but $P(y|x)$ is similar. (e.g., handwritten digit recognition where some clients only write certain digits).
2. Label Distribution Skew: $P_k(y)$ differs across clients, but $P(x|y)$ is similar. (e.g., face recognition where clients primarily have photos of specific individuals).
3. Conditional Distribution Skew (Concept Shift): $P_k(y|x)$ differs across clients, even if $P_k(x)$ is similar. (e.g., sentiment analysis where the meaning of certain phrases varies culturally).
4. Quantity Skew: Clients hold significantly different amounts of data.

The visualization below illustrates label distribution skew across four clients in a digit classification task (e.g., MNIST).

Distribution of samples per digit label across four clients. Client 1 has mostly '1's, Client 2 has '6's and '8's, Client 3 has '0's and '3's, and Client 4 has '2's and '4's. This contrasts sharply with an IID scenario where distributions would be roughly uniform.

Impact: Statistical heterogeneity poses significant challenges:

• Client Drift: Local models trained on skewed data can diverge significantly from the global objective during local training steps. When aggregated, these divergent updates can interfere destructively, slowing down or even preventing convergence of the global model.
• Reduced Global Model Accuracy: The final global model might perform poorly on the overall data distribution and particularly poorly for clients whose local distributions deviate most from the average.
• Fairness Concerns: The model may exhibit biases, performing well for majority data patterns but failing for minority groups or specific clients.
• Increased Communication Rounds: More rounds may be needed to reach a target accuracy compared to an IID setting.

System Heterogeneity

System heterogeneity relates to the variations in hardware capabilities, network conditions, and availability among clients in the federated network.

Sources:

• Hardware Variability: Clients (especially in cross-device settings) possess diverse CPUs, GPUs, memory capacities, and battery levels.
• Network Conditions: Clients connect via networks with different bandwidths, latencies, and stability (e.g., fast WiFi vs. slow, intermittent cellular connections).
• Availability: Clients may join or leave the training process unpredictably due to user activity, network issues, or battery constraints.

The diagram below illustrates system heterogeneity.

Clients in a federated network often have varying computational power, memory, and network connectivity. Some clients might be offline or respond very slowly.

Impact:

• Stragglers: In synchronous FL, where the server waits for updates from a subset of clients before aggregating, slow clients (stragglers) become bottlenecks, delaying the entire training process. Fast clients remain idle, wasting resources.
• Participant Drop-out: Clients dropping out mid-round can lead to lost updates and potentially biased aggregation if not handled carefully.
• Inefficient Resource Utilization: Variability makes it hard to optimize parameters like the number of local epochs ($E$) uniformly across all clients. A fixed $E$ might be too much computation for slow devices or too little for fast ones.
• Bias in Client Selection: Naive client selection might favor faster, more reliable clients, potentially skewing the model towards their data distributions if correlated with statistical heterogeneity.
• Challenges for Asynchronous FL: While asynchronous FL avoids the straggler bottleneck by processing updates as they arrive, it introduces challenges like managing update staleness (using old global models) and ensuring convergence stability.

Interaction and Consequences

Statistical and system heterogeneity often coexist. For instance, users with older, less powerful devices (system heterogeneity) might also exhibit different app usage patterns (statistical heterogeneity) compared to users with high-end devices. This interaction complicates the optimization process further. Failing to address heterogeneity leads to slower convergence, lower final model accuracy, potential unfairness across clients, and difficulties in deploying reliable FL systems. The subsequent sections in this chapter examine techniques specifically designed to mitigate these issues, ranging from robust aggregation rules to personalized model training.