Federated Averaging (FedAvg)

In each communication round, the server selects a subset of clients. Each client downloads the current global model weights and performs multiple steps of stochastic gradient descent (SGD) on its local, private dataset. This local computation reduces the frequency of communication compared to naive distributed SGD.

• Epochs: A hyperparameter E defines how many full passes a client makes over its local data.
• Batch Size: A hyperparameter B defines the mini-batch size used for local updates.
• Trade-off: More local computation (higher E) reduces communication rounds but increases the risk of client drift due to statistical heterogeneity.

The server collects the model updates from participating clients and computes a new global model by taking a weighted average of the received parameters. The weight for each client is typically proportional to the size of its local dataset (n_k).

• Formula: The global weight w_{t+1} is calculated as the sum of (n_k / n) * w^k_{t+1} for all participating clients k.
• Rationale: This ensures that clients with more data have a proportionally greater influence on the global model.
• Equivalence: In the case of a convex loss function and a single local epoch, FedAvg is mathematically equivalent to centralized mini-batch SGD.

FedAvg's primary innovation is reducing the communication-to-computation ratio. By performing multiple local updates before synchronizing, it minimizes the number of data transfers over bandwidth-constrained wireless links.

• Fraction of Clients (C): Only a random fraction of clients participate in each round, further reducing uplink congestion.
• Gradient Compression: FedAvg is often combined with sparsification or quantization to compress the model updates before transmission.
• Impact: This makes federated learning feasible for cross-device settings with millions of intermittently connected edge devices.

A fundamental challenge for FedAvg is statistical heterogeneity, where local data distributions across clients are non-identically distributed (non-IID). This causes local optima to drift away from the global optimum.

• Weight Divergence: With highly skewed non-IID data, the simple averaging of weights can lead to a global model that performs poorly on any individual client's distribution.
• Mitigations: Variants like FedProx add a proximal term to the local objective to constrain local updates, while SCAFFOLD uses control variates to correct for client drift.
• Empirical Finding: Despite its simplicity, FedAvg demonstrates surprising empirical robustness to moderate levels of non-IID data.

By design, FedAvg keeps raw training data on the client device, providing a baseline level of data minimization. However, the model updates themselves can leak sensitive information.

• Model Inversion: An honest-but-curious server can potentially reconstruct training samples from the gradients shared by a client.
• Defense Integration: FedAvg is typically deployed with Secure Aggregation to prevent the server from inspecting individual updates, and Differential Privacy to add calibrated noise to the updates.
• Poisoning Vulnerability: The server-side averaging is vulnerable to model poisoning attacks, where a single malicious client can corrupt the global model by uploading a scaled, adversarial update.

FedAvg operates in a synchronous lock-step manner. The server waits for all selected clients to complete their local computation and report back before proceeding to the next round.

• Straggler Problem: The entire round is delayed by the slowest participating device, a critical issue in heterogeneous edge networks.
• Timeout Mechanism: In practice, a server-imposed deadline is used; clients that do not respond in time are simply dropped from that round.
• Asynchronous Variants: To mitigate stragglers, Asynchronous Federated Learning protocols update the global model immediately upon receiving any client's update, trading off some mathematical consistency for reduced wall-clock time.