Research map / Optimization / Distributed and compressed
Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity
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 Shadowheart SGD, an asynchronous centralized distributed SGD method with unbiased compression that adapts per-worker batch sizes and message counts via an equilibrium time, and proves its time complexity is optimal among compressed centralized methods.
Problem
Nonconvex stochastic optimization in asynchronous centralized distributed settings where worker computation and worker-to-server communication times are heterogeneous and non-negligible, with compressed communication.
Approach
Each worker computes a time-budgeted number of stochastic gradients (minibatched) and sends multiple independently compressed copies to the server; the server aggregates with weights chosen to minimize variance, and the time budget is set by an implicitly defined equilibrium time t* that also yields a matching lower bound.
Key results
- Shadowheart SGD matches the optimal time complexity T* = (32 L Δ/ε)·t* among centralized compressed methods, with a matching lower bound up to constants.
- Numerically (d=10^6, n=10^3), Minibatch SGD and QSGD are worse by up to ×10^4 and Asynchronous SGD by ×10^2 at σ²/ε=1 in the stated random-time setup.
- When the slowest worker has infinite time, Minibatch SGD and QSGD have infinite complexity while Shadowheart SGD remains finite.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Shadowheart SGD instead of Minibatch SGD | Centralized distributed optimization · Last worker is slow | time complexity: \infty -> < \infty | Helped |
| Use Shadowheart SGD instead of QSGD | Centralized distributed optimization · Last worker is slow | time complexity: \infty -> < \infty | Helped |
| Use Shadowheart SGD instead of Minibatch SGD | Centralized distributed optimization · Equal worker performance | time complexity | Helped |
| Use Shadowheart SGD instead of QSGD | Centralized distributed optimization · Equal worker performance | time complexity | Helped |
| Use Shadowheart SGD instead of Rennala SGD / Asynchronous SGD | Centralized distributed optimization · Equal worker performance | time complexity | Helped |
| Use Shadowheart SGD instead of Minibatch SGD | Centralized distributed optimization · Numerical comparison, $\nicefrac{\sigma^2}{\varepsilon} = 1$ | relative time complexity: \times 10^3 vs. \times 1 | Helped |
| Use Shadowheart SGD instead of QSGD | Centralized distributed optimization · Numerical comparison, $\nicefrac{\sigma^2}{\varepsilon} = 1$ | relative time complexity: \times 3 vs. \times 1 | Helped |
| Use Shadowheart SGD instead of Rennala SGD / Asynchronous SGD | Centralized distributed optimization · Numerical comparison, $\nicefrac{\sigma^2}{\varepsilon} = 10^3$ | relative time complexity: \times 10 vs. \times 1 | Helped |
| Use Shadowheart SGD instead of Rennala SGD / Asynchronous SGD | Centralized distributed optimization · Numerical comparison, $\nicefrac{\sigma^2}{\varepsilon} = 10^6$ | relative time complexity: \times 1.5 vs. \times 1 | Helped |
| Use Bidirectional Shadowheart SGD with server-side compression and EF21-P | Shadowheart SGD when server broadcast is costly · Bidirectional communication | time complexity | Helped |
Surprising findings
- Optimal choice of the Rand-K compressor is K=1 up to a constant factor, i.e., sending one coordinate at a time.
Limitations
- Does not consider statistical (data) heterogeneity across workers.
- Equilibrium time is defined implicitly with no closed form.
- Adaptive variant incurs a worse complexity depending on fluctuation ratio r_i.
Experimental setup
Datasets: logistic regression on ML data (unspecified) synthetic functions
Metrics: time complexity (seconds to epsilon-stationary point) numerical comparison factors
Baselines: Minibatch SGD QSGD Rennala SGD Asynchronous SGD vanilla SGD on fastest worker
Builds on: Rennala SGD QSGD Asynchronous SGD MARINA EF21-P
Closest papers by meaning
- Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods (NeurIPS 2026 · similarity 0.90)
- On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization (NeurIPS 2024 · similarity 0.89)
- Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics (ICLR 2025 · similarity 0.88)
- Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity (NeurIPS 2024 · similarity 0.88)
- Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits (NeurIPS 2026 · similarity 0.88)
- Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations (NeurIPS 2024 · 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.