Non-IID Data

The most common and studied form of Non-IID data, where the frequency of class labels varies significantly across clients. For example, in a federated image classification task, one client's device may hold mostly pictures of cats, while another's holds mostly dogs.

• Local models become highly specialized to their dominant classes.
• This skew causes client drift, where local updates pull the global model in conflicting directions.
• Standard benchmarks use Dirichlet distribution sampling (e.g., with concentration parameter α=0.1) to simulate realistic, severe label skew.

Clients share the same set of labels, but the feature distributions for those labels differ. This is often due to differences in data collection environments or sensors.

• Example: Hospitals diagnosing the same disease (label) but using different medical imaging machines, resulting in variations in image contrast, resolution, or color profile (features).
• This skew degrades model performance because the learned feature representations are not transferable.
• Techniques like Federated Batch Normalization (FedBN) address this by allowing clients to keep local feature normalization statistics private.

The amount of data held by each client varies dramatically, from a few samples to millions. This imbalance affects both learning and system fairness.

• Clients with large datasets can dominate the global model update, biasing it toward their distribution.
• Small-data clients may fail to learn effectively locally, suffering from poor personalization.
• Client selection strategies and weighted averaging (e.g., weighting updates by dataset size) are common mitigations, though they can exacerbate bias if not carefully managed.

The semantic meaning of a label differs across clients. This is a severe and challenging form of heterogeneity.

• Example: The label "vehicle" might refer primarily to sedans in an urban client's data but to tractors in a rural client's data.
• The model must learn a disentangled representation to handle multiple concepts under the same label, which is extremely difficult with standard aggregation.
• This often necessitates personalized federated learning or clustered federated learning to group clients with similar concepts.

Data distributions evolve over time for individual clients, a challenge compounded in federated learning with streaming data.

• A client's local data stream may experience concept drift, where the relationship between features and labels changes (e.g., user typing patterns evolve).
• Different clients may drift at different rates and in different directions, creating a moving target for global aggregation.
• This requires algorithms capable of online federated learning and continual adaptation without catastrophic forgetting of past knowledge.

For non-tabular data, heterogeneity exists in the underlying structure of the data samples themselves.

• In federated learning with graph data, clients hold subgraphs with different network topologies, node degree distributions, and community structures.
• In time-series data, clients may have sequences of different lengths, sampling rates, or underlying periodicities.
• Aggregating models trained on structurally different data requires specialized architectures and aggregation mechanisms beyond simple parameter averaging.

FedProx modifies the local client objective function by adding a proximal term. This term penalizes the local model for deviating too far from the current global model, effectively acting as a regularizer. This technique:

• Mitigates client drift by constraining local updates.
• Is robust to system heterogeneity (varying client compute power), as it allows for variable amounts of local work.
• The hyperparameter μ controls the strength of the regularization; a higher μ forces clients to stay closer to the global model.

SCAFFOLD (Stochastic Controlled Averaging) uses control variates—correction terms stored on both the server and each client—to reduce the variance between local updates. This directly counteracts the client drift caused by Non-IID data.

• Each client computes the difference between its local update and its control variate.
• The server aggregates these corrected updates and updates a global control variate.
• This method corrects for the 'client update bias,' leading to significantly faster and more stable convergence, especially when client participation is partial each round.

FedOpt generalizes Federated Averaging by applying adaptive optimization algorithms (like Adam, Yogi, or Adagrad) on the server during the model aggregation step, instead of using a simple weighted average.

• Treats the aggregated client update as a pseudo-gradient.
• Applies momentum and adaptive learning rates to this update, which can better navigate the complex optimization landscape created by heterogeneous client gradients.
• This is particularly effective when client updates are noisy or biased due to Non-IID data, leading to improved final accuracy and convergence speed.

Instead of forcing a single global model on all clients, Personalized Federated Learning aims to produce a tailored model for each client. Key methods include:

• Local Fine-Tuning: Clients perform a few steps of local training on the global model after aggregation.
• Multi-Task Learning: Frameworks the problem as learning related but distinct tasks for each client.
• Model Mixture: Combines a global model with a local personalized layer.
• Ditto: A specific PFL algorithm that trains personalized models regularized towards the global model, improving fairness and robustness.

This technique groups clients into clusters based on the similarity of their local data distributions. A separate global model is then trained for each cluster.

• Clustering can be based on model updates, loss values, or data statistics.
• Effectively transforms a highly Non-IID problem into several more IID-like sub-problems.
• Improves model performance for all clients by ensuring they collaborate primarily with others who have similar data, reducing the negative interference from dissimilar clients.

Federated Distillation shifts the paradigm from sharing model parameters to sharing knowledge, typically in the form of logits (soft labels) or predictions on a shared public dataset.

• Clients train local models and send their predictions (not weights) to the server.
• The server aggregates these predictions (e.g., by averaging) and sends the consensus knowledge back.
• Clients then distill this knowledge into their local models.
• This method can be more communication-efficient and is often more robust to Non-IID data, as it aligns outputs rather than intermediate parameters.

Statistical heterogeneity is the umbrella term for the variation in data distributions across clients in a federated system. It is the root cause of Non-IID data challenges and manifests in three primary forms:

• Feature Distribution Skew (Covariate Shift): The distribution of input features P(x) differs across clients.
• Label Distribution Skew (Prior Probability Shift): The distribution of output labels P(y) varies (e.g., different prevalence of classes).
• Quantity Skew: The amount of data per client varies by orders of magnitude. This heterogeneity violates the core IID assumption of centralized learning, leading to client drift and convergence issues.

Client drift is the phenomenon where local models, optimized on their unique Non-IID data, diverge from the global objective. This occurs because each client's stochastic gradient is a biased estimator of the true global gradient. The consequences are:

• Slowed or unstable convergence of the global model.
• Performance degradation as the aggregated model becomes a poor fit for any individual client's distribution.
• Increased communication rounds required to achieve target accuracy. Algorithms like FedProx and SCAFFOLD are explicitly designed to correct for this drift.

Personalized Federated Learning is a paradigm shift that abandons the goal of a single global model. Instead, it aims to learn a personalized model for each client that performs well on its local Non-IID data. Key approaches include:

• Local Fine-Tuning: Starting from a global model and adapting it locally.
• Multi-Task Learning: Framing each client's problem as a related task.
• Model Interpolation: Learning to mix global and local models (e.g., Ditto).
• Meta-Learning: Learning a model initialization that can be quickly personalized. PFL directly addresses the performance fairness issues caused by data heterogeneity.

FedProx is a foundational federated optimization algorithm designed for statistical and system heterogeneity. It modifies the local client objective function by adding a proximal term. The local optimization problem becomes: min (local_loss(θ) + (μ/2) * ||θ - θ_global||^2) Where μ is a hyperparameter. This term:

• Penalizes large deviations from the global model θ_global.
• Theoretically guarantees convergence under heterogeneous data.
• Allows for variable amounts of local work (partial client participation), handling system heterogeneity. It is a direct and effective mitigation for client drift.

SCAFFOLD (Stochastic Controlled Averaging) is an algorithm that uses control variates to correct the client drift inherent in Non-IID settings. It maintains two sets of variables:

• Client control variate (c_i): Tracks the drift direction for each client.
• Server control variate (c): The average of client variates. During local training, clients use their control variate to adjust their gradient updates, effectively removing the local bias. This correction:
• Reduces variance between client updates.
• Achieves linear speedup in convergence, matching centralized SGD rates even under high heterogeneity.
• Requires maintaining and communicating additional state per client.

Clustered Federated Learning addresses Non-IID data by grouping clients with similar data distributions and training a separate model for each cluster. The process involves:

1. Similarity Measurement: Using metrics like model update similarity, loss profiles, or data statistics.
2. Clustering: Algorithms like K-Means or correlation-based grouping.
3. Cluster-Specific Aggregation: Running federated averaging within each cluster. This approach transforms a single, highly heterogeneous problem into multiple, more homogeneous sub-problems. It is particularly effective when data distributions naturally fall into distinct groups (e.g., geographic regions, device types).