Revisiting Consensus Error: A Fine-grained Analysis of Local SGD under Second-order Data Heterogeneity
Kumar Kshitij Patel, Ali Zindari, Sebastian Stich, Lingxiao Wang
Local SGD, or Federated Averaging, is one of the most widely used algorithms for distributed optimization. Although it often outperforms alternatives such as mini-batch SGD, existing theory has not fully explained this advantage under realistic data heterogeneity. Recent work has suggested that a second-order heterogeneity condition may suffice to justify the empirical gains of local SGD and to characterize its communication efficiency. We confirm this conjecture by establishing new upper and lower bounds on the convergence of local SGD. These bounds demonstrate how low second-order heterogeneity, combined with third-order smoothness, enables local SGD to interpolate between heterogeneous and homogeneous regimes while maintaining communication efficiency. Our main technical contribution is a refined analysis of the consensus error, a central quantity in such results. We validate our theory with experiments on a distributed linear regression task.