mlsanityData to 14 Oct 2026

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability

arXiv 2506.13974 ↗First posted 16 Jun 2025cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

Existing analysis of Local (Stochastic) Gradient Descent for heterogeneous objectives requires stepsizes η ≤ 1/K where K is the communication interval, which ensures monotonic decrease of the objective. In contrast, we analyze Local Gradient Descent for logistic regression with separable, heterogeneous data using any stepsize η > 0. With R communication rounds and M clients, we show convergence at a rate O(1/η K R) after an initial unstable phase lasting for widetildeO(η K M) rounds. This improves upon the existing O(1/R) rate for general smooth, convex objectives. Our analysis parallels the single machine analysis of~citewu2024large in which instability is caused by extremely large stepsizes, but in our setting another source of instability is large local updates with heterogeneous objectives.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 27 of its 40 references that are in the map. First posted on arXiv 16 Jun 2025.

Builds on

27 of 40 references.

References · 27

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019Advances and Open Problems in Federated Learningcited by 3,046
  3. 2020Adaptive Federated Optimizationcited by 1,046
  4. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  5. 2018Local SGD Converges Fast and Communicates Littlecited by 605
  6. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
  7. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 367
  8. 2021A Field Guide to Federated Optimizationcited by 315
  9. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  10. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  11. 2022Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stabilitycited by 155
  12. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 153
15 more
  1. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  2. 2020The Break-Even Point on Optimization Trajectories of Deep Neural Networkscited by 150
  3. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  4. 2023Stochastic Controlled Averaging for Federated Learning with Communication Compressioncited by 101
  5. 2023Federated Learning of Gboard Language Models with Differential Privacycited by 66
  6. 2018Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Ratecited by 64
  7. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 60
  8. 2023Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stabilitycited by 42
  9. 2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
  10. 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 38
  11. 2024Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiencycited by 35
  12. 2021Fast Margin Maximization via Dual Accelerationcited by 33
  13. 2024Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimizationcited by 17
  14. 2024The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communicationcited by 12
  15. 2025Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regressioncited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimensioncited by 1
  2. 2026Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devicescited by 0