Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability

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/ηKR) after an initial unstable phase lasting for O(ηKM ) rounds. This improves upon the existing O(1/R) rate for general smooth, convex objectives. Our analysis parallels the single machine analysis of (Wu et al., 2024a) in which instability is caused by extremely large stepsizes, but in our setting another source of instability is large local updates with heterogeneous objectives.