Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression

2025/01/23 by Michael Crawshaw, Crawshaw, Michael, Blake Woodworth +3 · 1 citation
Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2501.13790

openalex publication_date 2025/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We analyze two variants of Local Gradient Descent applied to distributed logistic regression with heterogeneous, separable data and show convergence at the rate O(1/KR) for K local steps and sufficiently large R communication rounds. In contrast, all existing convergence guarantees for Local GD applied to any problem are at least Ω(1/R), meaning they fail to show the benefit of local updates. The key to our improved guarantee is showing progress on the logistic regression objective when using a large stepsize η≫ 1/K, whereas prior analysis depends on η≤ 1/K.

Cited by

• Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability

Related

• Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
• Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes
• Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?
• Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression
• Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes