Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods

• URL: http://arxiv.org/abs/2602.03802v1
• Date: Tue, 03 Feb 2026 18:02:14 GMT
• Title: Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods
• Authors: Grigory Begunov, Alexander Tyurin,
• Abstract summary: We revisit Synchronous SGD and its robust variant, called $m$-Synchronous SGD, and theoretically show that they are nearly optimal in many heterogeneous computation scenarios.<n>While synchronous methods are not universal solutions and there exist tasks where asynchronous methods may be necessary, we show that they are sufficient for many modern heterogeneous computation scenarios.
• Score: 59.72933231179977
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Modern distributed optimization methods mostly rely on traditional synchronous approaches, despite substantial recent progress in asynchronous optimization. We revisit Synchronous SGD and its robust variant, called $m$-Synchronous SGD, and theoretically show that they are nearly optimal in many heterogeneous computation scenarios, which is somewhat unexpected. We analyze the synchronous methods under random computation times and adversarial partial participation of workers, and prove that their time complexities are optimal in many practical regimes, up to logarithmic factors. While synchronous methods are not universal solutions and there exist tasks where asynchronous methods may be necessary, we show that they are sufficient for many modern heterogeneous computation scenarios.

Related papers

• First Provably Optimal Asynchronous SGD for Homogeneous and Heterogeneous Data [0.0]
  dissertation develops a rigorous framework for asynchronous order optimization.<n>We show that with proper design, asynchronous SGD can achieve optimal time complexity, matching guarantees previously known only for synchronous methods.
  arXiv  Detail & Related papers  (2026-01-05T19:51:09Z)
• Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity [51.56484100374058]
  We introduce Ringleader ASGD, the first asynchronous algorithm that attains the theoretical lower bounds for parallel computation.<n>Our analysis further establishes that Ringleader ASGD remains optimal under arbitrary gradient and even time-varying speeds.
  arXiv  Detail & Related papers  (2025-09-26T19:19:15Z)
• Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity [92.1840862558718]
  Ringmaster ASGD achieves optimal time complexity under arbitrarily heterogeneous computation times.<n>This makes it the first Asynchronous SGD method to meet the theoretical lower bounds for time complexity in such scenarios.
  arXiv  Detail & Related papers  (2025-01-27T16:07:26Z)
• Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
  In practical distributed systems, workers typically not homogeneous, and can have highly varying processing times. We introduce a new parallel method Freya to handle arbitrarily slow computations. We show that Freya offers significantly improved complexity guarantees compared to all previous methods.
  arXiv  Detail & Related papers  (2024-05-24T13:33:30Z)
• Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity [85.92481138826949]
  We develop a new method-Shadowheart SGD-that provably improves the time complexities of all previous centralized methods. We also consider the bidirectional setup, where broadcasting from the server to the workers is non-negligible, and develop a corresponding method.
  arXiv  Detail & Related papers  (2024-02-07T12:15:56Z)
• Asynchronous Distributed Optimization with Delay-free Parameters [9.062164411594175]
  This paper develops asynchronous versions of two distributed algorithms, Prox-DGD and DGD-ATC, for solving consensus optimization problems over undirected networks. In contrast to alternatives, our algorithms can converge to the fixed point set of their synchronous counterparts using step-sizes that are independent of the delays.
  arXiv  Detail & Related papers  (2023-12-11T16:33:38Z)
• AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms [45.90015262911875]
  We analyze asynchronous-type algorithms for distributed SGD in the heterogeneous setting. As a by-product of our analysis, we also demonstrate guarantees for gradient-type algorithms such as SGD with random tightness.
  arXiv  Detail & Related papers  (2023-10-31T13:44:53Z)
• An Efficient Asynchronous Method for Integrating Evolutionary and Gradient-based Policy Search [76.73477450555046]
  We introduce an Asynchronous Evolution Strategy-Reinforcement Learning (AES-RL) that maximizes the parallel efficiency of ES and integrates it with policy gradient methods. Specifically, we propose 1) a novel framework to merge ES and DRL asynchronously and 2) various asynchronous update methods that can take all advantages of asynchronism, ES, and DRL.
  arXiv  Detail & Related papers  (2020-12-10T02:30:48Z)
• Advances in Asynchronous Parallel and Distributed Optimization [11.438194383787604]
  Asynchronous methods do not require all processors to maintain a consistent view of the optimization variables. They are not sensitive to issues like stragglers (i.e., slow nodes) and unreliable communication links. This article reviews recent developments in the design and analysis of asynchronous optimization methods.
  arXiv  Detail & Related papers  (2020-06-24T16:10:19Z)

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.