ArXiv

What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity

2026-07-16 · 08:56 UTC ·Kumar Kshitij Patel, Rustem Islamov, Sebastian U Stich... ·1 min read
Authors
Kumar Kshitij Patel, Rustem Islamov, Sebastian U Stich...
Categories
cs.LG, math.OC, stat.ML
arXiv
https://arxiv.org/abs/2607.14731v1
PDF
https://arxiv.org/pdf/2607.14731v1

Brief

Local SGD (Federated Averaging) under a bounded second-order heterogeneity model: the authors extend prior strong-convex results to general convex objectives, proving improved convergence guarantees and producing nearly-tight matching lower bounds. Techniques also yield a lower bound for serial SGD with replacement that links rare high-curvature clients to degraded rates. Summary is based on the abstract; full text was not available.

Why it matters

The paper proves the 2025 conjecture of Patel et al. that a bounded second-order heterogeneity assumption yields improved convergence guarantees for Local SGD (Federated Averaging) on general convex objectives; the authors (K. K. Patel, R. Islamov, S. U. Stich, A. Lucchi, E. Gorbunov, L. Wang) give improved upper bounds and nearly-tight lower bounds (arXiv:2607.14731v1, published 2026-07-16).

Key details

  • As an additional contribution, the authors derive a new lower bound for serial (with-replacement) SGD showing that second-order heterogeneity quantitatively captures the impact of rare high-curvature clients, clarifying when and why local updates can outperform minibatch SGD.
Source evidence

Abstract

Local SGD, also known as Federated Averaging, is a widely used distributed optimization algorithm. Although Local SGD often outperforms alternatives such as Mini-batch SGD in practice, theory still only partially explains when and why local updates help under realistic data heterogeneity. Recent work by [Patel et al., 2025] shows that a bounded second-order heterogeneity assumption captures the efficiency of Local SGD for strongly convex objectives, and conjectures that the same principle extends to the general convex setting. In this paper, we prove this conjecture by establishing an improved convergence guarantee for Local SGD on general convex objectives under bounded second-order heterogeneity. We also improve the best-known lower bounds for Local SGD in this setting, showing that our upper bounds are nearly tight. Together, these results provide a sharper, more fine-grained convergence theory for Local SGD. As a further application of our techniques, we provide a lower bound for serial SGD with replacement, showing how second-order heterogeneity captures the impact of rare high-curvature clients.