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

Grigory Begunov; Alexander Tyurin

cs.DCFeb 3, 2026

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

Authors: Grigory Begunov, Alexander Tyurin

Organizations: AXXX, Moscow, Russia · Lomonosov Moscow State University, Moscow, Russia

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, which can be interpreted as a method with a backup-worker strategy, and theoretically show that they are nearly optimal in many heterogeneous computation and communication scenarios, which is somewhat unexpected. We analyze the synchronous methods under random 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 theoretically that they are sufficient for many modern heterogeneous computation and communication scenarios.

Figures & tables

Figure 2

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Notation	Meaning
$\mathbb{R}_{+}$	Denotes $[0,\infty).$
$[n]$	Denotes a finite set $\{1,\dots,n\}$ .
$\left\\|x\right\\|$	Euclidean norm of a vector $x$ .
$g=\mathcal{O}(f)$	There exists $C>0$ such that $g(z)\leq C\,f(z)$ for all $z\in\mathcal{Z}$ .
$g=\Omega(f)$	There exists $C>0$ such that $g(z)\geq C\,f(z)$ for all $z\in\mathcal{Z}$ .
$g=\Theta(f)$	There exist $C_{1},C_{2}>0$ such that $C_{1}f(z)\leq g(z)\leq C_{2}f(z)$ for all $z\in\mathcal{Z}$ .

Appendix

Table 1: List of notations used throughout the paper.

\textstyle g^{k}=\frac{1}{m}\sum\limits_{i\in S_{k}}\frac{1}{B}\sum_{j=1}^{B}\nabla f(x^{k};\xi_{ij}^{k}),\,\,S_{k}\subseteq[n],\,\,\left|S_{k}\right|=m

Appendix

Algorithm 4

m

-Synchronous SGD with mini-batching

Figure 6: Q-Q Plot of the data from Section N versus a normal distribution.

Panel of Figure 7 — Figure 7: Comparison of the methods on the quadratic optimization problem under different computation time scenarios and noise levels.

Panel of Figure 8 — Figure 8: Comparison of the methods on the quadratic optimization problem with different number of workers ( $p=0.01,\tau_{i}=\sqrt{i}$ ).

Panel of Figure 9 — Figure 9: Comparison of the methods on a quadratic optimization problem with different types of random computation times. We take $p=0.01$ , $n=1000$ , and $\tau_{i}=\sqrt{i}$ . Three noise regimes are considered: (i) no noise in the first row; (ii) weak noise in the second row; and (iii) stronger noise in the third row. In the first column, we sample computation times from the truncated normal distribution. In the second column, from the gamma distribution. In the third column, from the uniform distribution.

Panel of Figure 10 — Figure 10: Comparison of the methods on a quadratic optimization problem with different types of random computation times. We take $p=0.01$ , $n=1000$ , and $\tau_{i}=i$ . Three noise regimes are considered: (i) no noise in the first row; (ii) weak noise in the second row; and (iii) stronger noise in the third row. In the first column, we sample computation times from the truncated normal distribution. In the second column, from the gamma distribution. In the third column, from the uniform distribution.

Panel of Figure 11 — Figure 11: Comparison of the methods on the quadratic optimization problem with the same mean $\tau_{i}=1$ and uniform noise ( $p=0.01,\tau_{i}=1,n=1000$ ). In these experiments, for all methods, we choose the best step size from the set $\left\{2^{-16},\dots,2^{-2},2^{-1},1,1.2,1.6,1.8,2\right\}.$

Panel of Figure 12 — Figure 12: Experiments with the CIFAR-10 dataset ( $n=1000$ ). Each row corresponds to a fixed noise level. The first column corresponds to function values, while the second column corresponds to accuracies.

Panel of Figure 13 — Figure 13: Experiments with the CIFAR-10 dataset ( $n=1000$ ). Each row corresponds to a fixed noise level. The first column corresponds to function values, while the second column corresponds to accuracies.

Panel of Figure 14 — Figure 14: Experiments with the MNIST dataset ( $n=1000$ ). Each row corresponds to a fixed noise level. The first column corresponds to function values, while the second column corresponds to accuracies.

Panel of Figure 15 — Figure 15: Experiments with the MNIST dataset ( $n=1000$ ). Each row corresponds to a fixed noise level. The first column corresponds to function values, while the second column corresponds to accuracies.

Figure 16: Training and validation losses versus measured wall-clock time for Synchronous SGD (Algorithm 1 ) and Asynchronous SGD (Algorithm 2 ) in NanoGPT, using

4

workers. We run the experiments with

3

seeds and plot the error bars.

Distributed Optimization

Distributed optimization coordinates computation across multiple agents or machines while balancing convergence, communication, privacy, and reliability.

See all 92 papers

Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity
May 13, 2026Ammar Mahran, Artavazd Maranjyan, Peter RichtárikDistributed Optimization Nonconvex Stochastic Optimization
KAUST
Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult
Sep 15, 2026Alexander TyurinDistributed Optimization Stochastic Optimization Convergence
AXXX, Moscow, Russia · Applied AI Institute, Moscow, Russia
Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Method
May 18, 2026Abdurakhmon Sadiev, Artavazd Maranjyan, Ivan Ilin +1LMO Methods Momentum Methods
KAUST

May 13, 2026J/K move · Enter open · S save

Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity

Ammar Mahran, Artavazd Maranjyan, Peter Richtárik

KAUST

Distributed Optimization Nonconvex Stochastic Optimization Heterogeneous Computing Heterogeneous Federated Learning Stochastic Gradient Descent

Open paper AskPDF arXiv

Asynchronous stochastic gradient descent (ASGD) is a standard way to exploit heterogeneous compute resources in distributed learning: instead of forcing fast workers to wait for slow ones, the server updates the model whenever a gradient arrives. Vanilla ASGD applies each arriving gradient with the same weight. When local data distributions are heterogeneous, this becomes problematic: faster workers contribute more updates, and we show theoretically that the method is biased toward a frequency-weighted average of the local objectives rather than the desired global objective. Existing remedies typically move away from the simple ASGD template by introducing gathering phases, buffering, or extra memory. We show that this is unnecessary. Keeping the standard ASGD mechanism, we recover the correct objective by rescaling worker-specific stepsizes in proportion to their computation times, so that each worker contributes the same aggregate learning rate over a cycle. In the non-convex setting, under smoothness and bounded heterogeneity assumptions, we prove that the resulting method, Rescaled ASGD, converges to stationary points of the correct global objective in the fixed-computation model. Its time complexity matches the known lower bound in the leading term, while the effects of staleness and data heterogeneity appear only in lower-order terms. Experiments confirm that the method converges to the correct objective and is competitive with state-of-the-art baselines.

Abstract

Distributed Optimization

Explore similar work

Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity

Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult

Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Method