mlsanityData to 7 Oct 2026

Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity

arXiv 2402.04785 ↗First posted 7 Feb 2024math.OC cs.LGcited by 13

Not on the map. Why?

Abstract (arXiv)

We consider nonconvex stochastic optimization problems in the asynchronous centralized distributed setup where the communication times from workers to a server can not be ignored, and the computation and communication times are potentially different for all workers. Using an unbiassed compression technique, we develop a new method-Shadowheart SGD-that provably improves the time complexities of all previous centralized methods. Moreover, we show that the time complexity of Shadowheart SGD is optimal in the family of centralized methods with compressed communication. We also consider the bidirectional setup, where broadcasting from the server to the workers is non-negligible, and develop a corresponding method.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Feb 2024.

Builds on

0 of 0 references.

No references here yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 9; 2026: 3.

13 papers.

Sort:

  1. 2025Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexitycited by 17
  2. 2024Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computationscited by 5
  3. 2025Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneitycited by 5
  4. 2025Optimizing Asynchronous Federated Learning: A Delicate Trade-Off Between Model-Parameter Staleness and Update Frequencycited by 2
  5. 2025Efficient AllReduce with Stragglerscited by 1
  6. 2025Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learningcited by 1
  7. 2025Pseudo-Asynchronous Local SGD: Robust and Efficient Data-Parallel Trainingcited by 0
  8. 2025Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Constructioncited by 0
  9. 2025Beyond Communication Overhead: A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learningcited by 0
  10. 2025Taming Latency and Bandwidth: A Theoretical Framework and Adaptive Algorithm for Communication-Constrained Trainingcited by 0
  11. 2026Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methodscited by 0
  12. 2026Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reductioncited by 0
1 more
  1. 2026Robustifying Asynchronous SGD via Soft Throttlingcited by 0