SCAFFOLD improves federated learning convergence with Hessian similarity
SCAFFOLD under Hessian Similarity: Sharp Convergence Rates
Machine Learning
Summary
Federated learning lets multiple devices train a model together without sharing their data, but differences in their data can make training less efficient. The paper studies an existing method called SCAFFOLD that helps fix these differences, called client drift, by using special correction terms. The authors analyze how well SCAFFOLD works depending on how similar the data's curvature (Hessian) is across devices, showing improved training speed and better guarantees for both simple and complex problems. They also show conditions where extra local work doesn't help when not all devices participate.
What this means in practice
- •For machine learning engineers: Design federated learning systems with improved convergence rates by adjusting local steps based on Hessian similarity among clients.
- •For data engineers in edge computing: Optimize communication and computation trade-offs in distributed training when clients have heterogeneous data and partial availability.
Authors
Zhirayr Tovmasyan, Slavomír Hanzely, Egor Shulgin, Peter Richtárik, Sebastian U. Stich
Abstract
One of the main challenges of federated learning is heterogeneous data split among the clients, leading to biased local updates called client drift. The SCAFFOLD algorithm (Karimireddy et al., 2020) corrects client drift with control variates, but its relation to the similarity of client data is not yet fully understood: the original similarity-based guarantees cover only quadratics with a stronger second-order similarity assumption, and a follow-up weakly convex analysis (Luo et al., 2025) obtains a $\sqrt{Lδ}$ dependence for $L$-smooth losses with averaged Hessian similarity $δ$. We analyze SCAFFOLD with minibatch-based control variates and establish linear dependence on Hessian similarity beyond quadratics, for both convex and nonconvex objectives. In particular, for convex objectives with exact gradients, $R$ SCAFFOLD rounds with $K$ local steps lead to an objective gap of order $(L/K+δ)D_0^2/R$, where $D_0$ is the initial distance to a minimizer. When $K=Θ(L/δ)$, it improves the minibatch SGD rate by a factor $Θ(L/δ)$. For nonconvex objectives, we prove an analogous stationarity guarantee under uniform Hessian similarity for a client-selection variant. In both settings, we extend these guarantees to stochastic gradients and prove matching lower bounds for the analyzed methods with constant local stepsizes. We also show that, under partial participation, even identical clients need not obtain the full communication benefit of additional local steps.