Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers

• URL: http://arxiv.org/abs/2606.13287v1
• Date: Thu, 11 Jun 2026 12:43:53 GMT
• Title: Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers
• Abstract summary: parallelization of training is an important strategy for increasing scale.<n>With constant step sizes, the convergence of ASGD is affected negatively by slow workers due to large delays in updates.<n>We show convergence in expectation, and the first time in asynchronous optimization, convergence with high probability.
• Score: 8.286183477962203
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In modern machine learning, parallelization of training is an important strategy for increasing scale. Asynchronous stochastic gradient descent (ASGD), which maximizes the utilization of available hardware by avoiding waiting for slow workers. However, with constant step sizes, the convergence of ASGD is nonetheless affected negatively by slow workers due to large delays in updates. At the same time, it has been empirically observed in asynchronous training of deep learning models that gradient clipping "stabilizes" training. In this work, we provide a theoretical justification for this behavior, as we show that clipping removes the dependence of the maximum delay in the oracle complexity. We employ a sub-Weibull model of gradient noise which generalizes sub-Gaussian and sub-exponential distributions to more heavy-tailed distributions, motivated by empirical observations in deep learning. We show convergence in expectation, and the first time in asynchronous optimization, convergence with high probability.

Related papers

• Mitigating Staleness in Asynchronous Pipeline Parallelism via Basis Rotation [6.710608163117798]
  Asynchronous pipeline parallelism maximizes hardware utilization by eliminating the pipeline bubbles inherent in synchronous execution.<n>This efficiency gain can be compromised by gradient staleness, where the immediate model updates with delayed gradients introduce noise into the optimization process.<n>We propose the use of basis rotation, demonstrating that it effectively mitigates the alignment issue and significantly accelerates convergence in asynchronous settings.
  arXiv  Detail & Related papers  (2026-02-03T13:31:51Z)
• Nesterov Method for Asynchronous Pipeline Parallel Optimization [59.79227116582264]
  We introduce a variant of Nesterov Accelerated Gradient (NAG) for asynchronous optimization in Pipeline Parallelism.<n>Specifically, we modify the look-ahead step in NAG to effectively address the staleness in gradients.<n>We theoretically prove that our approach converges at a sublinear rate in the presence of fixed delay in gradients.
  arXiv  Detail & Related papers  (2025-05-02T08:23:29Z)
• Ordered Momentum for Asynchronous SGD [12.810976838406193]
  We propose a novel method called momentum (OrMo) for ASGD.<n>In OrMo, momentum is incorporated into ASGD by organizing the gradients in order based on their indexes.<n> Empirical results demonstrate that OrMo can achieve better convergence performance compared with ASGD.
  arXiv  Detail & Related papers  (2024-07-27T11:35:19Z)
• Distributed Stochastic Gradient Descent with Staleness: A Stochastic Delay Differential Equation Based Framework [56.82432591933544]
  Distributed gradient descent (SGD) has attracted considerable recent attention due to its potential for scaling computational resources, reducing training time, and helping protect user privacy in machine learning.<n>This paper presents the run time and staleness of distributed SGD based on delay differential equations (SDDEs) and the approximation of gradient arrivals.<n>It is interestingly shown that increasing the number of activated workers does not necessarily accelerate distributed SGD due to staleness.
  arXiv  Detail & Related papers  (2024-06-17T02:56:55Z)
• Stragglers-Aware Low-Latency Synchronous Federated Learning via Layer-Wise Model Updates [71.81037644563217]
  Synchronous federated learning (FL) is a popular paradigm for collaborative edge learning. As some of the devices may have limited computational resources and varying availability, FL latency is highly sensitive to stragglers. We propose straggler-aware layer-wise federated learning (SALF) that leverages the optimization procedure of NNs via backpropagation to update the global model in a layer-wise fashion.
  arXiv  Detail & Related papers  (2024-03-27T09:14:36Z)
• Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent [63.43247232708004]
  A gradient descent performed in an asynchronous manner plays a crucial role in training large-scale machine learning models.<n>Existing generalization error bounds are rather pessimistic and cannot reveal the correlation between asynchronous delays and generalization.<n>Our theoretical results indicate that asynchronous delays reduce the generalization error of the delayed SGD algorithm.
  arXiv  Detail & Related papers  (2023-08-18T10:00:27Z)
• Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates [67.19481956584465]
  It has been experimentally observed that the efficiency of distributed training with saturation (SGD) depends decisively on the batch size and -- in implementations -- on the staleness. We show that our results are tight and illustrate key findings in numerical experiments.
  arXiv  Detail & Related papers  (2021-03-03T12:08:23Z)
• Extrapolation for Large-batch Training in Deep Learning [72.61259487233214]
  We show that a host of variations can be covered in a unified framework that we propose. We prove the convergence of this novel scheme and rigorously evaluate its empirical performance on ResNet, LSTM, and Transformer.
  arXiv  Detail & Related papers  (2020-06-10T08:22:41Z)
• DaSGD: Squeezing SGD Parallelization Performance in Distributed Training Using Delayed Averaging [4.652668321425679]
  Minibatch gradient descent (SGD) algorithm requires workers to halt forward/back propagations. DaSGD parallelizes SGD and forward/back propagations to hide 100% of the communication overhead.
  arXiv  Detail & Related papers  (2020-05-31T05:43:50Z)
• Slow and Stale Gradients Can Win the Race [39.750046808758526]
  Distributed Gradient Descent (SGD) when run in a synchronous manner, suffers from delays in runtime as it waits for the slowest workers (stragglers) Asynchronous methods can alleviate stragglers, but cause gradient staleness that can adversely affect the convergence error. We present a novel theoretical characterization of the speedup offered by asynchronous methods by analyzing the trade-off between the error in the trained model and the actual training runtime.
  arXiv  Detail & Related papers  (2020-03-23T23:27:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.