Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
This addresses the challenge of communication efficiency in federated learning for logistic regression, offering a faster convergence method with theoretical guarantees, though it is incremental in extending single-machine analysis to a distributed setting.
The paper tackles the problem of Local Gradient Descent for logistic regression with heterogeneous data by allowing any stepsize, showing convergence at a rate of O(1/ηKR) after an initial unstable phase of O(ηKM) rounds, which improves upon the existing O(1/R) rate for general convex objectives.
Existing analysis of Local (Stochastic) Gradient Descent for heterogeneous objectives requires stepsizes $η\leq 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 $\mathcal{O}(1/ηK R)$ after an initial unstable phase lasting for $\widetilde{\mathcal{O}}(ηK M)$ rounds. This improves upon the existing $\mathcal{O}(1/R)$ rate for general smooth, convex objectives. Our analysis parallels the single machine analysis of~\cite{wu2024large} in which instability is caused by extremely large stepsizes, but in our setting another source of instability is large local updates with heterogeneous objectives.