Research map / Optimization / Distributed and compressed
Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
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 Local GD on separable heterogeneous logistic regression converges with any constant stepsize and local interval, with an accelerated O(M/(γ^5 R^2)) rate for large ηK via an unstable-then-stable phase analysis.
Problem
Whether vanilla Local GD with large constant stepsizes (η K ≫ 1) converges on heterogeneous separable logistic regression, where existing worst-case analyses require η ≤ O(1/K) for monotone decrease and give only O(1/R) rates.
Approach
Adapts single-machine large-stepsize GD analysis for logistic regression (split comparator and gradient potential) to Local GD by decomposing each round's update into per-data-point contributions and bounding the ratio beta of local to initial gradient magnitudes; a refined local descent lemma (Hessian bounded by loss) gives monotone decrease once the objective is below a threshold.
Key results
- Theory: Local GD with eta K = Θ~(γ^3 R / M) and eta ≥ 1 achieves objective gap Õ(M/(γ^5 R^2)), beating the O(1/R) worst-case rate for general smooth convex Local GD.
- Stable-phase last-iterate bound F(w_r) ≤ 16/(η γ^2 K (r-τ)) holds for any η>0 and K≥1 after transition time τ.
- Experiments with η up to 2^8 and K up to 2^6 show final loss decreases when either η or K is increased, while larger K does not increase rounds to stability.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Local GD with eta K = \widetilde{\Theta} \left( \frac{\gamma^3 R}{M} \right) instead of the general convex-optimization setting | Local GD for separable logistic regression · Separable heterogeneous logistic regression | objective gap upper bound: \frac{1}{R} -> \frac{M}{\gamma^5 R^2} | Helped |
| Increase eta while holding K fixed | Local GD · Synthetic data and MNIST | objective gap | Helped |
| Increase K while holding eta fixed | Local GD · Synthetic data and MNIST | objective gap | Helped |
| Increase eta while holding K fixed | Local GD · Synthetic data and MNIST | rounds to stability | Hurt |
| Increase K while holding eta fixed | Local GD · Synthetic data and MNIST | rounds to stability | Helped |
| Increase K while tuning eta to K | Local GD · Synthetic data | objective gap | Helped |
| Increase K while tuning eta to K | Local GD · MNIST | stability at larger eta | Helped |
| Increase K while keeping eta K constant | Local GD · Synthetic data and MNIST | objective gap | No clear effect |
| Increase K while keeping eta K constant | Local GD · Synthetic data and MNIST | rounds to stability | Helped |
| Use eta = 2^10 | Local GD · Synthetic data and MNIST | convergence | Hurt |
| Use eta = 256 with K = 16 or K = 64 rather than K = 1 or K = 4 | Local GD · MNIST | convergence | Helped |
Surprising findings
- Increasing the local interval K tends to preserve or reduce the number of rounds needed to reach stability while giving a smaller final loss, stronger than the theory predicts.
- Larger K permits larger stable stepsizes on MNIST: eta=256 diverged for K=1 and K=4 but converged (unstably) for K=16 and K=64.
Limitations
- Derived error bound for Local GD is worse than single-machine GD parallelized over M machines in terms of M and gamma (gamma^5 vs gamma^4).
- Bounds depend on eta and K only through the product eta K, so the theory shows no benefit of local steps over K=1.
- Analysis restricted to logistic regression with separable data; does not cover general convex objectives or SGD.
Experimental setup
Datasets: synthetic two-client dataset MNIST (binarized labels, 1000 images) CIFAR-10
Benchmarks: synthetic dataset MNIST subset CIFAR-10
Metrics: objective gap F(w_R) - F_*
Baselines: Local GD worst-case bounds two-stage Local GD GD with M machines (single-machine analysis) Local GD with eta=1/K
Builds on: GD with large stepsizes for logistic regression (Wu et al.) split comparator technique gradient potential argument two-stage Local GD
Closest papers by meaning
- Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression (ICLR 2025 · similarity 0.94)
- Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression (NeurIPS 2025 · similarity 0.91)
- Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes (ICML 2025 · similarity 0.90)
- Any-stepsize Gradient Descent for Separable Data under Fenchel–Young Losses (NeurIPS 2025 · similarity 0.88)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.87)
- Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization (NeurIPS 2024 · similarity 0.86)
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.