Revisiting Consensus Error: A Fine-grained Analysis of Local SGD under Second-order Data Heterogeneity

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 assumptions about data heterogeneity. Recent work has suggested that a second-order heterogeneity assumption may suffice to justify the empirical gains of local SGD. We confirm this conjecture by establishing new upper and lower bounds on the convergence of local SGD. These bounds demonstrate how a low secondorder 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.

• Part of the work was done when the author was a student at Toyota Technological Institute, Chicago (TTIC).

M m∈[M ] x m t , which may not be computed in practice (when t mod K ̸ = 0). Regularity Assumptions. We assume that the local objectives are convex and smooth. Assumption 1 (Convexity and Smoothness). For all m ∈ [M ], the function F m (•) is twice differentiable and satisfies µ • I d ⪯ ∇ 2 F m (•) ⪯ H • I d for some 0 ≤ µ ≤ H. When µ > 0, we say F m is strongly convex and denote its condition number by κ = H µ . Furthermore, there exists Q ≥ 0 such that for all x, y ∈ R d , we have

Recall that a strongly convex function admits a unique minimizer. Also, Q = 0 implies that F m is quadratic. We further discuss the role of third-order smoothness in Section 5.

We also assume the stochastic gradients have bounded fourth moments. Assumption 2 (Bounded Fourth Moment of Stochastic Gradients). For all m ∈ [M ] and x ∈ R d , we have E z∼Dm [∇f (x; z)] = ∇F m (x), and

Using Jensen's inequality, the above assumption implies the second moment of the stochastic gradients are also bounded, i.e., E z∼Dm [∥∇f (x; z) -∇F m (x)∥