scaffold

**SCAFFOLD** (Stochastic Controlled Averaging for Federated Learning) is a **federated learning algorithm that uses control variates to correct client drift** — each client maintains a control variate that tracks the difference between local and global gradients, dramatically reducing the impact of data heterogeneity. **How SCAFFOLD Works** - **Control Variates**: Each client $k$ maintains $c_k$ (local control) and knows $c$ (global control). - **Corrected Update**: Local SGD uses $g_k - c_k + c$ instead of raw gradient $g_k$ — subtracts local bias, adds global direction. - **Update Controls**: After local training, update $c_k$ based on the local gradient drift observed. - **Communication**: Send model update AND control variate update to the server. **Why It Matters** - **Variance Reduction**: Control variates eliminate the client drift that causes FedAvg to diverge on non-IID data. - **Fewer Rounds**: SCAFFOLD converges in significantly fewer communication rounds than FedAvg on heterogeneous data. - **Theory**: Provably converges at the same rate as centralized SGD, regardless of data heterogeneity. **SCAFFOLD** is **drift-corrected federated learning** — using control variates to eliminate the client drift problem that plagues FedAvg on non-IID data.