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 1Figure 2Figure 3
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
Notation
Meaning
R+
Denotes [0,∞).
[n]
Denotes a finite set {1,…,n} .
∥x∥
Euclidean norm of a vector x .
g=O(f)
There exists C>0 such that g(z)≤Cf(z) for all z∈Z .
g=Ω(f)
There exists C>0 such that g(z)≥Cf(z) for all z∈Z .
g=Θ(f)
There exist C1,C2>0 such that C1f(z)≤g(z)≤C2f(z) for all z∈Z .
Appendix
Table 1: List of notations used throughout the paper.
Figure 6: Q-Q Plot of the data from Section N versus a normal distribution.
Figure 7: Comparison of the methods on the quadratic optimization problem under different computation time scenarios and noise levels.
Figure 8: Comparison of the methods on the quadratic optimization problem with different number of workers ( p=0.01,τi=i ).
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 τ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.
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 τ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.
Figure 11: Comparison of the methods on the quadratic optimization problem with the same mean τi=1 and uniform noise ( p=0.01,τi=1,n=1000 ). In these experiments, for all methods, we choose the best step size from the set {2−16,…,2−2,2−1,1,1.2,1.6,1.8,2}.
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.
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.
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.
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 coordinates computation across multiple agents or machines while balancing convergence, communication, privacy, and reliability.
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.
Modern large-scale machine learning tasks often require multiple workers, devices, CPUs, or GPUs to compute stochastic gradients in parallel and asynchronously to train model weights. Theoretical results typically distinguish between two settings: (i) the homogeneous setting, where all workers have access to the same data distribution, and (ii) the heterogeneous setting, where each worker operates on different data distributions. Known optimal time complexities in these settings reveal a significant gap, with far more pessimistic guarantees in the heterogeneous case. In this work, we investigate whether these pessimistic optimal time complexities can be overcome under different assumptions. Surprisingly, we show that improvement is provably impossible under widely used first- and second-order similarity assumptions for any randomized algorithm. We then turn to the interpolation regime and demonstrate that the weak interpolation assumption alone is also insufficient. Finally, we introduce a minimal combination of irreducible assumptions, strong interpolation and the local Polyak-Lojasiewicz condition, to derive a new time complexity bound that matches the dependence on worker computation times in the best-known result in the homogeneous setting, without requiring identical data distributions.
Alexander Tyurin
AXXX, Moscow, Russia · Applied AI Institute, Moscow, Russia
Muon has recently emerged as a strong alternative to AdamW for training neural networks, with encouraging large-scale pretraining results and growing evidence that matrix-structured updates can be faster in practice. Yet Muon, and more generally Linear Minimization Oracle (LMO) based methods, are typically used synchronously. This is problematic in heterogeneous distributed systems, where workers complete gradient computations at different speeds and synchronous training must repeatedly wait for slower workers. In this work, we introduce Ringmaster LMO, an asynchronous LMO-based momentum method for unconstrained stochastic nonconvex optimization. Our method builds on the delay-thresholding idea of Ringmaster ASGD. For SGD-type methods, Ringmaster ASGD achieves optimal time complexity by discarding overly stale gradients. Ringmaster LMO extends this mechanism to general LMO-based updates. We establish convergence guarantees under generalized (L0,L1)-smoothness and further develop a parameter-agnostic variant with decreasing stepsizes and adaptive delay thresholds. Finally, we translate our iteration guarantees into time complexity bounds under heterogeneous worker computation times. In the classical Euclidean smooth setting, these bounds recover the optimal time complexity of Ringmaster ASGD. Experiments on stochastic quadratic problems and NanoChat language-model pretraining show that the advantages of Ringmaster LMO grow with system heterogeneity and that the method outperforms strong synchronous and asynchronous baselines.
Abdurakhmon Sadiev, Artavazd Maranjyan, Ivan Ilin +1