Research map / Optimization / Distributed and compressed
SLowcalSGD : Slow Query Points Improve Local-SGD for Stochastic Convex Optimization
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.
Proposes SLowcal-SGD, a local-update method for heterogeneous stochastic convex optimization that queries gradients at slowly changing weighted averages (Anytime-SGD style) and provably beats Minibatch-SGD and Local-SGD in communication rounds.
Problem
Distributed stochastic convex optimization with heterogeneous data across M machines: existing local-update methods (Local-SGD) do not provably beat Minibatch-SGD, and accelerated Minibatch-SGD remains the best known baseline.
Approach
Customize Anytime-SGD (slowly changing query points given by weighted averages of iterates, with increasing weights alpha_t = t+1) to the local-update distributed setting, so that the bias between machines' query points shrinks, reducing the bias from local updates; importance weights are shown to be crucial.
Key results
- Theory: SLowcal-SGD requires fewer communication rounds than Minibatch-SGD and Local-SGD to reach linear speedup in M in the heterogeneous SCO setting (Table 1 R_min comparison).
- MNIST logistic regression with 16, 32, 64 workers and K in {4,...,64}: SLowcal-SGD gains over Local-SGD and Minibatch-SGD grow with K and M, with negligible differences at small K.
- Uniform weights (alpha_t=1) are reported to perform worse than Minibatch-SGD, so increasing weights are necessary for the benefit.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use slowly changing averaged query points for local gradient updates | Local-SGD (Slowcal-SGD) · Heterogeneous SCO | minimum rounds for linear speedup: $G_*580MK^{1/2} +MK^{1/2} $ vs. ${MK}$ | Helped |
| Use slowly changing averaged query points for local gradient updates | Local-SGD (Slowcal-SGD) · MNIST test | test accuracy | Helped |
| Use slowly changing averaged query points for local gradient updates | Local-SGD (Slowcal-SGD) · MNIST test | test loss | Helped |
| Use increasing weights $\alpha_t=t+1$ instead of uniform weights (ablation) | Slowcal-SGD · Heterogeneous SCO | excess loss | Helped |
| Use uniform weights $\alpha_t=1$ instead of increasing weights (ablation) | Slowcal-SGD · Heterogeneous SCO | excess loss | Hurt |
| Increase the number of local steps | Slowcal-SGD · MNIST test | test accuracy | Helped |
| Increase the number of local steps | Minibatch-SGD · MNIST test | test accuracy | Mixed |
Surprising findings
- With uniform weights alpha_t=1, SLowcal-SGD performs worse than Minibatch-SGD; increasing importance weights are crucial.
- At small numbers of local steps, Minibatch-SGD slightly outperforms the local approaches.
Limitations
- Analysis requires knowledge of problem parameters (sigma, L) for step size; adaptive variant left to future work.
- Does not provably dominate accelerated Minibatch-SGD, an open question.
- Experiments are limited to MNIST logistic regression on a single GPU.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST
Metrics: test accuracy test loss
Baselines: Minibatch-SGD Local-SGD SCAFFOLD Accelerated Minibatch-SGD
Builds on: Anytime-SGD Local-SGD Minibatch-SGD SCAFFOLD
Closest papers by meaning
- Minibatch vs Local SGD for Heterogeneous Distributed Learning (NeurIPS 2020 · similarity 0.92)
- SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (ICLR 2020 · similarity 0.90)
- Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.89)
- Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond (ICLR 2022 · similarity 0.89)
- Convergence of Distributed Adaptive Optimization with Local Updates (ICLR 2025 · similarity 0.88)
- Towards Stability and Generalization Bounds in Decentralized Minibatch Stochastic Gradient Descent (AAAI 2024 · similarity 0.88)
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.