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

• URL: http://arxiv.org/abs/2607.14731v1
• Date: Thu, 16 Jul 2026 08:56:45 GMT
• Title: What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity
• Abstract summary: Local SGD, also known as Federated Averaging, is a widely used distributed optimization algorithm.<n>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.<n>We prove this conjecture by establishing an improved convergence guarantee for Local SGD on general convex objectives under bounded second-order heterogeneity.
• Score: 39.01981872811199
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Sharp Gaussian approximations for Decentralized Federated Learning [1.2489632787815885]
  Federated Learning has gained traction in privacy-sensitive collaborative environments, with local SGD emerging as a key optimization method.<n>We present two generalized Gaussian approximation results for local SGD and explore their implications.<n>The time-uniform approximations support bootstrap-based tests for detecting adversarial attacks.
  arXiv  Detail & Related papers  (2025-05-12T23:40:13Z)
• The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication [37.210933391984014]
  Local SGD is a popular optimization method in distributed learning, often outperforming other algorithms in practice. We provide new lower bounds for local SGD under existing first-order data heterogeneity assumptions. We also show the min-max optimality of accelerated mini-batch SGD for several problem classes.
  arXiv  Detail & Related papers  (2024-05-19T20:20:03Z)
• Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
  We study to what extent may gradient descent (SGD) be understood as a "conventional" learning rule that achieves generalization performance by obtaining a good fit training data. We analyze the closely related with-replacement SGD, for which an analogous phenomenon does not occur and prove that its population risk does in fact converge at the optimal rate.
  arXiv  Detail & Related papers  (2022-02-27T13:25:01Z)
• Differentially Private SGDA for Minimax Problems [83.57322009102973]
  We prove that gradient descent ascent (SGDA) can achieve optimal utility in terms of weak primal-dual population risk. This is the first-ever-known result for non-smoothly-strongly-concave setting.
  arXiv  Detail & Related papers  (2022-01-22T13:05:39Z)
• SGD with a Constant Large Learning Rate Can Converge to Local Maxima [4.014524824655106]
  We construct worst-case optimization problems illustrating that gradient descent can exhibit strange and potentially undesirable behaviors. Specifically, we construct landscapes and data distributions such that SGD converges to local maxima. Our results highlight the importance of simultaneously analyzing the minibatch sampling, discrete-time updates rules, and realistic landscapes.
  arXiv  Detail & Related papers  (2021-07-25T10:12:18Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Demystifying Why Local Aggregation Helps: Convergence Analysis of Hierarchical SGD [39.75009345804017]
  Hierarchical SGD (H-SGD) has emerged as a new distributed SGD algorithm for multi-level communication networks. In H-SGD, before each global aggregation, workers send their updated local models to local servers for aggregations. Despite recent research efforts, global convergence still lacks theoretical understanding.
  arXiv  Detail & Related papers  (2020-10-24T22:05:41Z)
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates [70.9701218475002]
  We introduce a unified convergence analysis of decentralized communication methods. We derive universal convergence rates for several applications. Our proofs rely on weak assumptions.
  arXiv  Detail & Related papers  (2020-03-23T17:49:15Z)
• Is Local SGD Better than Minibatch SGD? [60.42437186984968]
  We show how all existing error guarantees in the convex setting are dominated by a simple baseline, minibatch SGD. We show that indeed local SGD does not dominate minibatch SGD by presenting a lower bound on the performance of local SGD that is worse than the minibatch SGD guarantee.
  arXiv  Detail & Related papers  (2020-02-18T19:22:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.