Search papers, labs, and topics across Lattice.
This paper establishes tighter convergence guarantees for Local SGD under the assumption of bounded second-order heterogeneity, extending previous results from strongly convex objectives to general convex settings. The authors improve existing lower bounds, demonstrating that their upper bounds are nearly tight, which refines the theoretical understanding of Local SGD's efficiency in distributed optimization. Additionally, they derive a lower bound for serial SGD with replacement, highlighting the influence of rare high-curvature clients on convergence rates.
Local SGD's efficiency can be rigorously explained through bounded second-order heterogeneity, revealing nearly tight convergence rates for general convex objectives.
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.
