TL;DR
SCAFFOLD introduces a powerful new algorithm for Federated Learning (FL) that solves the "client-drift" problem—a common issue where local updates on heterogeneous data lead models astray. By using control variates to correct these local updates, SCAFFOLD achieves significantly faster and more stable convergence than the industry-standard Federated Averaging (FedAvg), even when data is highly non-IID or clients are sampled infrequently.
The Dark Side of FedAvg: Client-Drift
In Federated Learning, models are trained across thousands of edge devices (like phones or sensors) without ever moving their data to a central server. The go-to algorithm for this is Federated Averaging (FedAvg), which saves communication costs by letting clients perform multiple local updates before syncing with the server.
However, FedAvg suffers from client-drift. When data is heterogeneous (non-IID)—meaning one device's data looks very different from another's—the local updates on each device pull the model toward that device's local optimum rather than the global optimum.
This drift results in unstable training and forces researchers to use painfully small step sizes, slowing down the entire process. The authors prove that in some cases of high gradient dissimilarity, FedAvg can actually be slower than simple Stochastic Gradient Descent (SGD).
The SCAFFOLD Solution
To combat this, the authors propose SCAFFOLD (Stochastic Controlled Averaging). SCAFFOLD borrows the concept of control variates from the variance reduction literature (like SAGA or SVRG) and adapts it for the distributed setting.
The core idea is to maintain a "state" for the server ($c$) and for each client ($c_i$). These variables estimate the direction of the gradient. During local training, instead of just following the local gradient, a client uses the difference $(c - c_i)$ to "correct" its path.
The Intuition: If a client's local data usually pulls the model "North," but the global average needs it to go "East," the control variate acts as a compass correction, pushing the local update back toward the global East.
Key Insights and Theoretical Guarantees
- Quantifying the Drift: The paper provides a rigorous proof that FedAvg's performance is strictly limited by "gradient dissimilarity." If clients are too different, FedAvg must slow down.
- SCAFFOLD is "Drift-Proof": Unlike FedAvg, SCAFFOLD’s convergence rate does not depend on how dissimilar the clients' gradients are. It is proven to be at least as fast as SGD in all cases.
- Hessian Similarity Matters: A major theoretical breakthrough in the paper shows that if clients have similar loss "landscapes" (Hessian similarity), SCAFFOLD can actually take advantage of local steps to beat large-batch SGD. This formally quantifies when local steps are genuinely helpful in distributed optimization.
Key Results
The researchers evaluated SCAFFOLD using standard FL benchmarks like EMNIST (Extended MNIST) under varying levels of data heterogeneity (0% to 100% similarity).
- Massive Speedups: On the EMNIST dataset with 0% similarity (the hardest, highly non-IID case), FedAvg failed to reach target accuracy within 1,000 rounds. SCAFFOLD reached it in just 77 rounds.
- Efficiency with Local Steps: As the number of local epochs increased, FedAvg's performance degraded due to exacerbated drift. In contrast, SCAFFOLD's performance improved or stabilized. In some IID settings, SCAFFOLD achieved a 104x speedup over SGD.
- Superior Accuracy: In non-convex neural network experiments, SCAFFOLD consistently reached higher test accuracy (84.2%) compared to FedAvg (82.8%) and SGD (76.4%).
Limitations and Future Work
While highly effective, SCAFFOLD does have practical trade-offs:
- Statefulness: SCAFFOLD requires clients to store a control variate ($c_i$). In cross-device systems with millions of clients who might only participate once, managing this state is challenging.
- Communication Overhead: While SCAFFOLD drastically reduces the number of communication rounds, each round requires sending both the model and the control variate, effectively doubling the payload size per round compared to vanilla FedAvg.
- Theoretical Generalization: The authors proved that similarity helps for quadratic functions, but generalizing this "local step advantage" to general non-convex functions (like deep neural networks) remains an open theoretical challenge.
Summary updated