SCAFFOLD

The core innovation of SCAFFOLD is the use of control variates—client-specific and server-side correction terms. The client control variate c_i estimates the direction of the client's drift from the global objective. During local training, the client's update is corrected by subtracting its own control variate and adding the server's control variate c. This mechanism directly counteracts the variance introduced by non-IID data, steering local updates toward the global optimum.

• Client Update Correction: local_gradient = gradient - c_i + c
• Reduces Update Variance: By accounting for persistent client bias, the variance of the aggregated updates is significantly lower than in standard FedAvg.

SCAFFOLD maintains and updates two sets of control variates in each communication round, creating a feedback loop for bias correction.

• Server Control Variate (c): Represents the average direction of all client updates. It is updated on the server using the difference between the new global model and the previous one.
• Client Control Variate (c_i): Captures the individual bias of client i. It is updated locally by the client based on the difference between its local update and the server's direction (c).

This dual update ensures the control variates accurately track both the global progress and each client's unique statistical skew.

SCAFFOLD provides provably faster convergence than Federated Averaging (FedAvg) in heterogeneous data settings. Its theoretical guarantee shows a convergence rate that is independent of data heterogeneity (the degree of non-IID-ness), unlike FedAvg whose convergence slows significantly as heterogeneity increases.

• Eliminates Client Drift: The control variate correction prevents clients from over-optimizing toward their local data minima.
• Linear Speedup: Convergence improves proportionally with the number of clients participating per round, a property often lost in FedAvg under non-IID data.

While SCAFFOLD transmits both a model update and a control variate update, it often achieves a net reduction in total communication rounds required to reach a target accuracy. The increased per-round communication cost is offset by drastically faster convergence.

• Fewer Rounds to Convergence: The variance reduction means each aggregation step is more effective, requiring fewer rounds than FedAvg.
• Fixed Overhead: The control variate is the same size as the model gradient, doubling the per-client upload size but not scaling with dataset size.

Both SCAFFOLD and FedProx address client drift, but through fundamentally different mechanisms.

• FedProx: Adds a proximal term to the local loss function, penalizing the local model for straying too far from the global model. This is a constraint-based approach.
• SCAFFOLD: Uses additive correction via control variates to adjust the update direction itself. This is a bias-correction approach.

Empirically, SCAFFOLD often converges faster and to a better final accuracy on highly heterogeneous data, as it actively corrects the update direction rather than merely restraining it.

Deploying SCAFFOLD introduces specific system design choices.

• Stateful Clients: Clients must persistently store their local control variate c_i across rounds. This requires stable client identities and storage, which may not suit highly transient edge device populations.
• Server Compute: The server must compute and broadcast the global control variate c, adding a small overhead to the aggregation step.
• Partial Participation: The algorithm can accommodate partial client participation, but the server control variate update must account for which clients were active. The original analysis provides guidance for this setting.

The foundational algorithm for federated learning. FedAvg coordinates multiple clients to train a shared global model by having each client perform multiple local epochs of SGD on its private data. The server then aggregates the resulting model deltas via a weighted average proportional to local dataset sizes. It is the baseline against which advanced algorithms like SCAFFOLD are compared.

The primary problem SCAFFOLD is designed to correct. Client drift occurs when local client models diverge from the global objective due to optimization on statistically heterogeneous (non-IID) data. This divergence causes the simple average of client updates to point in a suboptimal direction, slowing convergence and reducing final model accuracy. SCAFFOLD uses control variates to explicitly estimate and correct for this drift.

A federated optimization algorithm that mitigates client drift by adding a proximal term to the local client's loss function. This term penalizes the local model for straying too far from the global model received at the start of the round. Unlike SCAFFOLD's corrective control variates, FedProx uses a constraint-based approach, which can be more computationally stable but may converge slower under high heterogeneity.

A generalized framework for federated optimization where the server applies adaptive optimizers (e.g., Adam, Yogi) to the aggregated client updates, rather than using simple averaging. Algorithms like FedAdam fall under this framework. SCAFFOLD can be viewed as a client-side correction method that is often complementary to server-side adaptive optimization, with combined approaches (SCAFFOLD + FedOpt) showing strong performance.

The core statistical mechanism in SCAFFOLD. A control variate is an auxiliary variable with a known expected value used to reduce the variance of an estimator. In SCAFFOLD, each client maintains a client control variate that estimates the drift in its local update direction. The server maintains a server control variate. The difference between these is used to correct the client's update, steering it toward the global objective and reducing variance across clients.

The defining characteristic of real-world federated learning that makes algorithms like SCAFFOLD necessary. It means the data distribution differs significantly across clients (e.g., different writing styles per user, local climate patterns per sensor). This breaks the core assumption of IID data in centralized ML, causing client drift and making convergence challenging. SCAFFOLD provides stronger theoretical convergence guarantees under these conditions compared to FedAvg.