SCAFFOLD under Hessian Similarity: Sharp Convergence Rates
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 √(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+δ)D02/R, where D0 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.
Related
- Convergence rates of mixed primal-dual dynamical systems with implicit Hessian damping and Tikhonov regularization
- Sharp convergence rates for mean field control in the region of strong regularity
- Sharp convergence rates for the vanishing discount problem with hyperbolic Aubry sets
- Weighted moments and sharp convergence rates for supercritical multitype branching processes
- SHARP CONVERGENCE RATES OF THE HERMITIAN-YANG-MILLS-HIGGS ITERATION ON RIEMANN SURFACES
BibTeX
@misc{tovmasyan2026scaffold,
title = {{SCAFFOLD under Hessian Similarity: Sharp Convergence Rates}},
author = {Zhirayr Tovmasyan and Slavomír Hanzely and Egor Shulgin and Peter Richtárik and Sebastian U. Stich},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35663},
eprint = {2610.35663},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35663},
}
RIS
TY - UNPB
TI - SCAFFOLD under Hessian Similarity: Sharp Convergence Rates
AU - Zhirayr Tovmasyan
AU - Slavomír Hanzely
AU - Egor Shulgin
AU - Peter Richtárik
AU - Sebastian U. Stich
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35663
UR - https://arxiv.org/abs/2610.35663
AB - 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 √(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.
ER -