Research map / Optimization / Distributed and compressed
Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that Local GD for distributed logistic regression on heterogeneous separable data can achieve O(1/KR) convergence by using a two-stage learning rate warmup (large stepsize after warmup) and gives preliminary Local Gradient Flow results for M=2 clients.
Problem
Whether local steps provably accelerate Local GD for distributed logistic regression, since existing worst-case analyses require small learning rates eta <= 1/K and give no benefit from local updates (rate at least Omega(1/R)).
Approach
Exploits the logistic loss property that smoothness decreases with the loss value (||grad F|| <= F, ||Hessian F|| <= F), so after a small-stepsize warmup phase a large constant stepsize (eta_2 = Theta(1)) can be used, enabling the 1/(KR) rate; also proposes Local Gradient Flow with a Lyapunov analysis for M=2, n=1.
Key results
- Two-Stage Local GD achieves F(w_2) <= 2/(eta_2 gamma^2 K(R-r_0)), i.e. O(1/KR) for large R, versus the baseline O(1/(gamma^2 R)) for fixed small stepsize.
- Local GF with M=2, n=1 converges at rate tilde O(1/(eta K R)) after a transition time tau, giving communication cost tilde O(C^alpha / (gamma^4 eps^{1-alpha})) with alpha -> 0 logarithmically.
- Experiments show small stepsize 1/(KH) yields overlapping loss curves regardless of K, while the two-stage stepsize converges faster with larger K.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase local steps K while using the two-stage learning rate | Local GD on synthetic and heterogeneous MNIST data · Synthetic dataset; heterogeneous MNIST | training loss convergence | Helped |
| Use the small learning rate η = 1/(KH) instead of the two-stage learning rate (ablation) | Local GD · Synthetic dataset; heterogeneous MNIST | training loss convergence | Hurt |
| Use large constant learning rate η = 1/H instead of the two-stage learning rate (ablation) | Local GD · Synthetic dataset; heterogeneous MNIST | long-term training loss convergence | Helped |
| Use large constant learning rate η = 1/H with large K (ablation) | Local GD · Synthetic dataset | early-round training loss | Hurt |
| Use large constant learning rate η = 1/H, even with very large K (ablation) | Local GD · Heterogeneous MNIST | training loss stability | Helped |
| Increase K while retaining the baseline small learning rate (ablation) | Local GD · Synthetic dataset; heterogeneous MNIST | training loss convergence | No clear effect |
| Use large constant learning rate η = 1/H rather than small learning rate η = 1/(KH) (ablation) | Local GD · Synthetic dataset; heterogeneous MNIST | training loss convergence | Mixed |
Surprising findings
- Vanilla Local GD with a large stepsize can converge faster with large K despite early instability, and non-monotonicity arises from large eta*K rather than eta > 1/H.
- The small stepsize 1/(KH) required by baseline guarantees gives no benefit from increasing K, since the stepsize cancels the gain from more local steps.
Limitations
- Results do not apply to vanilla Local GD; the two-stage warmup is required in the main theorem.
- Local GF analysis is limited to M=2 clients and n=1 data point per client and needs strong assumptions on dataset size and clients.
- Analysis is for separable logistic regression with deterministic gradients and a linear model.
Experimental setup
Datasets: synthetic two-client dataset MNIST (binarized, heterogeneous partition over 5 clients) CIFAR-10
Benchmarks: synthetic two-client logistic regression heterogeneous MNIST binary classification CIFAR-10 (ResNet, Local SGD vs Minibatch SGD, appendix)
Metrics: training loss communication rounds to epsilon-approximate solution
Baselines: Local GD with small stepsize eta=1/(KH) Local GD with large stepsize eta=1/H Minibatch SGD
Builds on: Local SGD / FedAvg analysis Minibatch SGD gradient descent implicit bias for logistic regression
Closest papers by meaning
- Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability (ICML 2025 · similarity 0.94)
- Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes (ICML 2025 · similarity 0.90)
- Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression (NeurIPS 2025 · similarity 0.90)
- Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design (NeurIPS 2026 · similarity 0.87)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.87)
- Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.