Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912433659969536 |
|---|---|
| author | Crawshaw, Michael Woodworth, Blake Liu, Mingrui |
| author_facet | Crawshaw, Michael Woodworth, Blake Liu, Mingrui |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_13974 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability Crawshaw, Michael Woodworth, Blake Liu, Mingrui Machine Learning 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. |
| title | Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2506.13974 |