Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum

• URL: http://arxiv.org/abs/2605.02043v1
• Date: Sun, 03 May 2026 20:24:24 GMT
• Title: Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum
• Abstract summary: Asynchronous distributed gradient training (SGD) enables scalable distributed training but suffers from staleness.<n>Existing mitigation strategies, such as delay-dependent learning rates and staleness-aware training, typically or discard delayed gradients.<n>We propose a momentum-based asynchronous framework designed to preserve information from delayed gradients while mitigating staleness.
• Score: 16.032739611868685
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Asynchronous stochastic gradient descent (SGD) enables scalable distributed training but suffers from gradient staleness. Existing mitigation strategies, such as delay-adaptive learning rates and staleness-aware filtering, typically attenuate or discard delayed gradients, introducing systematic bias: updates from simpler or faster-to-process samples are overrepresented, while gradients from more complex samples are delayed or suppressed. In contrast, prior approaches to data-dependent delays rely on a Lipschitz assumption that yields suboptimal rates or leave the smooth, convex case unaddressed. We propose a momentum-based asynchronous framework designed to preserve information from delayed gradients while mitigating the effects of staleness. We establish the first optimal convergence rates for data-dependent delays in both convex and non-convex smooth setups, providing a new result for asynchronous optimization under standard assumptions. Additionally, we derive robust learning-rate schedules that simplify hyperparameter tuning in practice.

Related papers

• CurvZO: Adaptive Curvature-Guided Sparse Zeroth-Order Optimization for Efficient LLM Fine-Tuning [15.930478833291827]
  Fine-tuning large language models (LLMs) with backpropagation achieves high performance but incurs substantial memory overhead.<n>We propose CurvZO, which tracks curvature signals online from scalar ZO feedback.<n>We show that CurvZO consistently improves fine-tuning performance and reduces training time over ZO baselines.
  arXiv  Detail & Related papers  (2026-03-23T09:13:45Z)
• 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)
• Closed-Form Last Layer Optimization [72.49151473937319]
  Under a squared loss, the optimal solution to the linear last layer weights is known in closed-form.<n>We show this is equivalent to alternating between gradient descent steps on the backbone and closed-form updates on the last layer.
  arXiv  Detail & Related papers  (2025-10-06T09:14:39Z)
• Adaptive Deadline and Batch Layered Synchronized Federated Learning [66.93447103966439]
  Federated learning (FL) enables collaborative model training across distributed edge devices while preserving data privacy, and typically operates in a round-based synchronous manner.<n>We propose ADEL-FL, a novel framework that jointly optimize per-round deadlines and user-specific batch sizes for layer-wise aggregation.
  arXiv  Detail & Related papers  (2025-05-29T19:59:18Z)
• 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)
• Optimizing Asynchronous Federated Learning: A Delicate Trade-Off Between Model-Parameter Staleness and Update Frequency [2.1990852305468533]
  Synchronous federated learning (FL) scales poorly with the number of clients due to the straggler effect.<n>In this work, we rely on modeling and analysis to better understand the impact of design choices in asynchronous FL algorithms.<n>We characterize in particular a fundamental trade-off for optimizing asynchronous FL: minimizing gradient estimation errors by avoiding model parameter staleness.
  arXiv  Detail & Related papers  (2025-02-12T08:38:13Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• Stochastic Optimization with Laggard Data Pipelines [65.20044914532221]
  We show that "dataechoed" extensions of common optimization methods exhibit provable improvements over their synchronous counterparts. Specifically, we show that in convex optimization with minibatches, data echoing affords speedups on the curvature-dominated part of the convergence rate, while maintaining the optimal statistical rate.
  arXiv  Detail & Related papers  (2020-10-26T14:55:31Z)

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.