Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability

2025/06/16 by Michael Crawshaw, Crawshaw, Michael, Blake Woodworth +3
Decision Sciences · Engineering · #Advanced Numerical Analysis Techniques #FOS: Computer and information sciences #Grey System Theory Applications #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2506.13974

openalex publication_date 2025/06/16 · openalex created_date 2025/10/13 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression
• Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization
• The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication
• Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency
• Stochastic Controlled Averaging for Federated Learning with Communication Compression
• Federated Learning of Gboard Language Models with Differential Privacy
• Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability
• Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability
• On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Data
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• A Field Guide to Federated Optimization
• Fast Margin Maximization via Dual Acceleration
• Gradient Descent on Neural Networks Typically Occurs at the Edge of\n Stability
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Adaptive Federated Optimization
• The Break-Even Point on Optimization Trajectories of Deep Neural\n Networks
• Is Local SGD Better than Minibatch SGD?
• Advances and Open Problems in Federated Learning
• On the Convergence of Local Descent Methods in Federated Learning
• Tighter Theory for Local SGD on Identical and Heterogeneous Data
• Stochastic Gradient Descent on Separable Data: Exact Convergence with a\n Fixed Learning Rate
• Local SGD Converges Fast and Communicates Little
• Characterizing Implicit Bias in Terms of Optimization Geometry
• The Implicit Bias of Gradient Descent on Separable Data
• Communication Complexity of Distributed Convex Learning and Optimization
• Optimal Distributed Online Prediction using Mini-Batches

Related

• Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression
• Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency
• Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes
• Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression
• Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?