mlsanityData to 14 Oct 2026

STSyn: Speeding Up Local SGD with Straggler-Tolerant Synchronization

arXiv 2210.03521 ↗First posted 6 Oct 2022cs.LG cs.DC cs.ITcited by 2

Not on the map. Why?

Abstract (arXiv)

Synchronous local stochastic gradient descent (local SGD) suffers from some workers being idle and random delays due to slow and straggling workers, as it waits for the workers to complete the same amount of local updates. In this paper, to mitigate stragglers and improve communication efficiency, a novel local SGD strategy, named STSyn, is developed. The key point is to wait for the K fastest workers, while keeping all the workers computing continually at each synchronization round, and making full use of any effective (completed) local update of each worker regardless of stragglers. An analysis of the average wall-clock time, average number of local updates and average number of uploading workers per round is provided to gauge the performance of STSyn. The convergence of STSyn is also rigorously established even when the objective function is nonconvex. Experimental results show the superiority of the proposed STSyn against state-of-the-art schemes through utilization of the straggler-tolerant technique and additional effective local updates at each worker, and the influence of system parameters is studied. By waiting for faster workers and allowing heterogeneous synchronization with different numbers of local updates across workers, STSyn provides substantial improvements both in time and communication efficiency.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 43 of its 63 references that are in the map. First posted on arXiv 6 Oct 2022.

Builds on

43 of 63 references.

References · 43

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,492
  3. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,229
  4. 2018Federated Learning with Non-IID Datacited by 1,108
  5. 2020Adaptive Federated Optimizationcited by 1,046
  6. 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 906
  7. 2017Federated Multi-Task Learningcited by 672
  8. 2018Local SGD Converges Fast and Communicates Littlecited by 605
  9. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 502
  10. 2019Robust and Communication-Efficient Federated Learning from Non-IID Datacited by 419
  11. 2018Adaptive Federated Learning in Resource Constrained Edge Computing Systemscited by 409
  12. 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 278
31 more
  1. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 202
  2. 2021Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learningcited by 193
  3. 2021Federated Learning with Buffered Asynchronous Aggregationcited by 190
  4. 2020FetchSGD: Communication-Efficient Federated Learning with Sketchingcited by 179
  5. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 153
  6. 2015Asynchronous Parallel Stochastic Gradient for Nonconvex Optimizationcited by 116
  7. 2019Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronizationcited by 107
  8. 2018Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithmscited by 106
  9. 2016Asynchronous Stochastic Gradient Descent with Delay Compensationcited by 99
  10. 2017On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimizationcited by 92
  11. 2019SAFA: a Semi-Asynchronous Protocol for Fast Federated Learning with Low Overheadcited by 82
  12. 2019Communication-efficient distributed SGD with Sketchingcited by 81
  13. 2019First Analysis of Local GD on Heterogeneous Datacited by 81
  14. 2018Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGDcited by 77
  15. 2018Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGDcited by 68
  16. 2020Towards Flexible Device Participation in Federated Learningcited by 65
  17. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 60
  18. 2017Collaborative Deep Learning in Fixed Topology Networkscited by 60
  19. 2020Straggler-Resilient Federated Learning: Leveraging the Interplay Between Statistical Accuracy and System Heterogeneitycited by 56
  20. 2018Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimizationcited by 34
  21. 2021Federated Learning with Spiking Neural Networkscited by 23
  22. 2019ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Codingcited by 22
  23. 2015Model Accuracy and Runtime Tradeoff in Distributed Deep Learning:A Systematic Studycited by 19
  24. 2016A Fundamental Tradeoff between Computation and Communication in Distributed Computingcited by 12
  25. 2019Gradient Coding with Clustering and Multi-message Communicationcited by 12
  26. 2020Dynamic Federated Learningcited by 12
  27. 2019LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learningcited by 10
  28. 2020Anytime MiniBatch: Exploiting Stragglers in Online Distributed Optimizationcited by 9
  29. 2020STL-SGD: Speeding Up Local SGD with Stagewise Communication Periodcited by 8
  30. 2016CYCLADES: Conflict-free Asynchronous Machine Learningcited by 5
  31. 2022Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learningcited by 1

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 1.

2 papers.

  1. 2024Distributed Stochastic Gradient Descent with Staleness: A Stochastic Delay Differential Equation Based Frameworkcited by 1
  2. 2025Water Quality Data Imputation via A Fast Latent Factorization of Tensors with PID-based Optimizercited by 0