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

Local SGD, also known as Federated Averaging, is a widely used distributed optimization algorithm. Although it frequently outperforms alternatives such as Mini-batch SGD in practice, its theoretical advantage under realistic data heterogeneity remains only partially understood. Recent work demonstrates that bounded second-order heterogeneity accounts for the benefits of Local SGD for strongly convex objectives and conjectures similar advantages for general convex objectives. In this paper, we establish such gains for general convex objectives by providing an improved convergence guarantee for Local SGD 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 almost tight. Using our techniques, we also improve the convergence guarantee of SGD-with-replacement under bounded second-order heterogeneity and obtain an almost-matching lower bound.