SCAFFOLD

The core innovation of SCAFFOLD is the maintenance of control variates (c and c_i) for the server and each client. These variates estimate the global model's update direction. During local training, the client corrects its stochastic gradient by subtracting the drift between its local variate and the server's variate: g_i = ∇F_i(x) - c_i + c. This correction prevents the local model from straying too far toward its local optimum, directly addressing the client drift problem that plagues standard FedAvg on non-IID data.

In standard Federated Averaging, when client data distributions are heterogeneous (non-IID), local models drift toward their individual local minima. SCAFFOLD's control variates mathematically bound this drift. The correction term c - c_i acts as a force pulling the local update back toward the global optimum. This allows clients to perform many more local steps without diverging, which is the key mechanism enabling a significant reduction in total communication rounds compared to FedAvg.

SCAFFOLD achieves communication efficiency not by compressing gradients, but by reducing the total number of communication rounds required to reach a target accuracy. Because the control variates prevent divergence, the algorithm converges in significantly fewer rounds than FedAvg, especially under high data heterogeneity. The trade-off is that each round transmits both the model update and the updated local control variate, doubling the payload size per round. However, the reduction in total rounds typically yields a net decrease in overall communication.

SCAFFOLD provides strong theoretical convergence guarantees under non-IID data distributions. It provably converges to a stationary point at a rate comparable to SGD on a single machine, even with arbitrarily heterogeneous client data. This is a significant theoretical advantage over FedAvg, which can converge to a suboptimal point or require a carefully tuned learning rate decay when data is non-IID. SCAFFOLD's convergence is robust to both statistical heterogeneity and partial client participation.

SCAFFOLD defines two algorithmic variants:

• Option I: The server maintains a single global control variate c. Clients update their local variate c_i and transmit the difference Δc_i back to the server, which aggregates them to update c.
• Option II: Clients transmit their updated local variate c_i directly, and the server averages them to form the new c. Option II is simpler but requires clients to maintain state across rounds, making it suitable for cross-silo settings with stateful clients.

A practical limitation of SCAFFOLD is that it requires clients to be stateful—each client must store and update its local control variate c_i across rounds. This is feasible in cross-silo federated learning (e.g., hospitals training collaboratively) where clients are persistent and reliable. However, in cross-device settings with millions of ephemeral mobile devices, maintaining per-client state is impractical. Variants like FedDyn and Mime have been proposed to address this limitation.

The core mathematical mechanism of SCAFFOLD. Each client maintains a local control variate (c_i) that estimates the update direction of the global model, while the server maintains a global control variate (c). The local update is corrected by subtracting c_i and adding c, effectively neutralizing the drift caused by heterogeneous local data distributions. This correction ensures each client's update moves toward the true global optimum rather than its local minimum.

A phenomenon in Federated Averaging (FedAvg) where local models diverge from the global optimum when trained on non-IID data for multiple local epochs. Each client's model moves toward its local minimum, and simply averaging these drifted models can lead to slow convergence or suboptimal performance. SCAFFOLD directly addresses this by estimating and subtracting the drift during local training, making it robust to statistical heterogeneity.

Two primary approaches to handling data heterogeneity:

• FedProx: Adds a proximal term to the local objective, penalizing deviation from the global model. Simpler to implement but provides a static correction.
• SCAFFOLD: Uses control variates to dynamically estimate and correct the true gradient direction. Achieves faster convergence and lower communication rounds, but requires clients to maintain state across rounds and transmit control variate updates.

SCAFFOLD achieves communication efficiency through faster convergence rather than gradient compression. By correcting for client drift, it reduces the total number of communication rounds required to reach a target accuracy by up to 90% compared to FedAvg on highly non-IID data. However, each round transmits slightly more data because control variate updates must accompany model updates, creating a trade-off between round count and per-round payload size.

Unlike FedAvg, SCAFFOLD requires stateful clients that retain their local control variate (c_i) across training rounds. This introduces engineering complexity:

• Clients must persist state between rounds
• New clients joining mid-training must initialize their control variate
• Clients that drop out permanently lose their accumulated correction This statefulness is the primary deployment challenge in cross-device federated learning scenarios with ephemeral participants.

SCAFFOLD provides strong theoretical guarantees for convex and non-convex optimization under data heterogeneity. Key properties:

• Converges at a rate independent of data heterogeneity
• Matches the convergence rate of SGD on centralized data under ideal conditions
• Robust to partial client participation with bounded variance These guarantees make SCAFFOLD particularly suitable for regulated healthcare environments where predictable convergence behavior is required for validation.