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

Abstract:Existing constant-step analysis of stochastic \Scaf{} identifies a leading $O(\gamma/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\ge2$, $$ \begin{aligned} \mathbb{E}_{\pi_{\gamma,N,H}}[x]-x^\star ={}& -\frac{f'''(x^\star)\sigma^2}{4f''(x^\star)^2}\frac{\gamma}{N}\\ &- \frac{f'''(x^\star)\sigma^2}{12f''(x^\star)} \frac{(H-1)(5H-1)}{H}\gamma^2 +O_H\!\left(\frac{\gamma^2}{N}+\gamma^3\right). \end{aligned} $$ Hence client averaging suppresses the leading $O(\gamma/N)$ bias but does not remove the client-independent $O(\gamma^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.

Machine Learning (cs.LG); Statistics Theory (math.ST)

arXiv:2608.26765 [cs.LG]

(or arXiv:2608.26765v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2608.26765 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.