# Beyond Client Averaging: A Client-Independent Second-Order Stationary-Bias Component in Stochastic SCAFFOLD

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 17 references that are in the map.
- First posted on arXiv 27 Aug 2026.

## Builds on (most cited first, 13 of 13)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Stochastic Gradient Descent as Approximate Bayesian Inference](https://mlsanity.com/paper/1704.04289/) (2017)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization](https://mlsanity.com/paper/2111.06328/) (2021)
- [Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2405.14285/) (2024)
- [The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize](https://mlsanity.com/paper/2405.16732/) (2024)
- [Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis](https://mlsanity.com/paper/2501.04443/) (2025)
- [Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up](https://mlsanity.com/paper/2503.07594/) (2025)
- [Tight Analysis of Decentralized SGD: A Markov Chain Perspective](https://mlsanity.com/paper/2601.07021/) (2026)

## Abstract (arXiv)

Existing constant-step analysis of stochastic Scaf identifies a leading O(γ/N) stationary mean bias and shows that higher-order bias can persist as the client count increases, but does not identify the first client-independent contribution at coefficient level. For full-participation stochastic Scaf with one-dimensional homogeneous clients, fixed local-step count H, and bounded additive gradient noise, we prove, uniformly over N≥2,  beginaligned mathbbE_πγ,N,H[x]-x^star =& -fracf'''(x^star)σ24f''(x^star)2fracγN &- fracf'''(x^star)σ212f''(x^star) frac(H-1)(5H-1)Hγ2 +OH!left(fracγ2N+γ3right). endaligned  Hence client averaging suppresses the leading O(γ/N) bias but does not remove the client-independent O(γ2) component when its coefficient is nonzero. The mechanism is indirect: although the direct control contribution cancels pathwise in the linear global average, the controls still alter within-round local trajectories and their second moments. Fresh gradient noise and persistent control fluctuations therefore generate local second-moment corrections that nonquadratic curvature converts into stationary mean bias. The coefficient vanishes for quadratic objectives. Numerical experiments are consistent with the predicted coefficient, its persistence as client count increases, and the stated joint remainder. The result is restricted to the one-dimensional homogeneous fixed-H setting.