Research map / Optimization / Distributed and compressed

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

NeurIPS 2026 · Optimization › Distributed and compressed · approach: Local and asynchronous SGD

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves that Local SGD on general convex objectives benefits from bounded second-order heterogeneity (tau), giving tighter upper bounds via a self-bounding argument, near-matching lower bounds, and a lower bound for SGD with replacement under rare high-curvature clients.

Problem

Understanding when Local SGD (Federated Averaging) provably beats Mini-batch SGD under realistic data heterogeneity, specifically in general convex federated optimization where prior analyses rely on uniform first-order heterogeneity.

Approach

Replaces uniform gradient-dissimilarity control with trajectory-dependent heterogeneity bounds, linking consensus error to gradient dissimilarity along the average iterate, and closes a self-bounding loop between iterate error and heterogeneity using bounded second-order heterogeneity (tau) plus first-order heterogeneity at the optimum (zeta_star).

Key results

• Upper bound for Local SGD on general convex problems with tau-second-order and zeta_star-first-order heterogeneity: HB^2/(KR) + (H tau^2)^{1/3} B^2/R^{2/3} + ... , which beats Mini-batch SGD when tau is small relative to H/sqrt(R).
• New lower bound for Local SGD matching the upper bound up to constants in the small-tau regime; a red regime of the tau-zeta_star plane remains with a gap.
• Lower bound for multi-pass SGD with replacement shows the worst-client smoothness hat H B^2/(TM) term is tight when hat H ~ sqrt(M) tau.

Surprising findings

• Local SGD cannot strictly dominate Mini-batch SGD under first-order heterogeneity at the optima alone, for any zeta_star.

Limitations

• Gap remains between upper and lower bounds in a red regime of the tau-zeta_star plane.
• Lower bound is for the final iterate while upper bound is for the averaged iterate.
• Lower bound construction relies on non-twice-differentiable functions for the first-order block; necessity unclear.

Experimental setup

Metrics: expected function suboptimality E[F(x)] - F(x*)

Baselines: Mini-batch SGD Local SGD upper bound under uniform first-order heterogeneity Local SGD lower bound under second-order heterogeneity (strongly convex/general

Builds on: Local SGD / FedAvg Mini-batch SGD DANE Woodworth et al. lower bounds for local SGD

Closest papers by meaning

• Revisiting Consensus Error: A Fine-grained Analysis of Local SGD under Second-order Data Heterogeneity (NeurIPS 2025 · similarity 0.93)
• Faster Rates For Federated Variational Inequalities (NeurIPS 2026 · similarity 0.88)
• A New Theoretical Perspective on Data Heterogeneity in Federated Optimization (ICML 2024 · similarity 0.85)
• Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.85)
• Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression (ICLR 2025 · similarity 0.85)
• Stability and Generalization Analysis of Decentralized SGD: Sharper Bounds Beyond Lipschitzness and Smoothness (ICML 2025 · similarity 0.85)