# Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up

arXiv: https://arxiv.org/abs/2503.07594 · HTML: https://mlsanity.com/paper/2503.07594/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2025.

## Built on by (most cited first, 3 of 3)

- [Tight Analysis of Decentralized SGD: A Markov Chain Perspective](https://mlsanity.com/paper/2601.07021/) (2026)
- [How Edge of Stability Hinders SCAFFOLD in Federated Optimization](https://mlsanity.com/paper/2608.25873/) (2026)
- [Beyond Client Averaging: A Client-Independent Second-Order Stationary-Bias Component in Stochastic SCAFFOLD](https://mlsanity.com/paper/2608.26765/) (2026)

## Abstract (arXiv)

This paper proposes a novel analysis for the Scaffold algorithm, a popular method for dealing with data heterogeneity in federated learning. While its convergence in deterministic settings--where local control variates mitigate client drift--is well established, the impact of stochastic gradient updates on its performance is less understood. To address this problem, we first show that its global parameters and control variates define a Markov chain that converges to a stationary distribution in the Wasserstein distance. Leveraging this result, we prove that Scaffold achieves linear speed-up in the number of clients up to higher-order terms in the step size. Nevertheless, our analysis reveals that Scaffold retains a higher-order bias, similar to FedAvg, that does not decrease as the number of clients increases. This highlights opportunities for developing improved stochastic federated learning algorithms