A Sharper Analysis of Scaffold on Quadratics

Heterogeneity across client datasets poses a challenge in federated learning (FL), impairing the convergence and performance of classical distributed optimization methods. The Scaffold algorithm has emerged as a prominent approach to mitigate heterogeneity; despite many efforts, its theoretical properties remain incompletely understood. In this paper, we present a refined analysis of Scaffold for quadratic objectives. Our results establish convergence guarantees valid for an arbitrary number of local steps. A distinctive aspect of our analysis is the spectral decomposition of the Hessian matrix governing the quadratic optimization problem, revealing that the convergence dynamics of Scaffold are determined by its behavior across individual eigenspaces. We complement our theoretical contributions with illustrative numerical examples, elucidating empirical observations previously unexplained by existing analyses. Our findings deepen the understanding of variance-reduction techniques in federated learning and provide insights for future algorithmic design.