Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity

Artavazd Maranjyan, Alexander Tyurin, Peter Richtárik · 2025

Read Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity by Artavazd Maranjyan, Alexander Tyurin, Peter Richtárik (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-16168.txt.

Introduction

Artavazd Maranjyan, Alexander Tyurin, and Peter Richtárik fix a speed flaw in parallel training in a 2025 paper. Asynchronous gradient descent lets many workers update a model without waiting for each other. Wildly uneven worker speeds spoil its timing, though, and a 2023 result showed no known variant hits the best possible time. Their method, Ringmaster ASGD, reorganizes the updates to tame stragglers.

Careful theory proves optimal time complexity even when worker speeds swing without pattern, they report. It is the first asynchronous method to meet the lower bound for such settings. The result closes a named gap in distributed learning theory and guides faster large scale training.

Catalog record

CREATORArtavazd Maranjyan, Alexander Tyurin, Peter Richtárik
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-16168

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity Artavazd Maranjyan, Alexander Tyurin, Peter Richtárik Abstract Asynchronous Stochastic Gradient Descent ( Asynchronous SGD ) is a cornerstone method for parallelizing learning in distributed machine learning. However, its performance suffers under arbitrarily heterogeneous computation times across workers, leading to suboptimal time complexity and inefficiency as the number of workers scales. While several Asynchronous SGD variants have been proposed, recent findings by Tyurin & Richtárik (2023) reveal that none achieve optimal time complexity, leaving a significant gap in the literature. In this paper, we propose Ringmaster ASGD , a novel Asynchronous SGD method designed to address these limitations and tame the inherent challenges of Asynchronous SGD . We establish, through rigorous theoretical analysis, that Ringmaster ASGD achieves optimal time complexity under arbitrarily heterogeneous and dynamically fluctuating worker computation times. This makes it the first Asynchronous SGD method to meet the theoretical lower bounds for time complexity in such scenarios. 1 Introduction We consider stochastic nonconvex optimization problems of the form \min_{x\in\mathbb{R}^{d}}\left\{f(x):={\mathbb{E}}_{\xi\sim\mathcal{D}}\left[f(x;\xi)\right]\right\}, where f\,:\,\mathbb{R}^{d}\times\mathbb{S}_{\xi}\to\mathbb{R}, \mathbb{R}^{d} is a linear space, and \mathbb{S}_{\xi} is a sample space. In machine learning, f(x;\xi) denotes the loss of a model parameterized by x on a data sample \xi , and \mathcal{D} denotes the distribution of the training dataset. In nonconvex optimization, our goal is to find an \varepsilon –stationary point, i.e., a (random) vector \bar{x}\in\mathbb{R}^{d} such that \mathbb{E}\left[\left\|\nabla f(\bar{x})\right\|^{2}\right]\leq\varepsilon . We consider a setup involving n workers (e.g., CPUs, GPUs, servers), each with access to the same distribution \mathcal{D} . Each worker is capable of computing independent, unbiased stochastic gradients with bounded variance (Assumption 1.3 ). We consider a setup with asynchronous, heterogeneous, and varying computation speeds. We aim to account for all potential scenarios, such as random outages, varying computational performance over time, and the presence of slow or straggling workers ( Dean & Barroso, 2013 ) . This setup is common in both datacenter environments ( Dean et al., 2012 ) and federated learning ( Konečný et al., 2016 ; McMahan et al., 2016 ; Kairouz et al., 2021 ) for distributed training. Although parallelism facilitates rapid convergence, variations in worker speeds make effective coordination more challenging. Asynchronous Stochastic Gradient Descent ( Asynchronous SGD ) is a popular approach for parallelization in such distributed settings. The algorithm operates as follows ( Algorithm 1 ), formalized below. Algorithm 1 Asynchronous SGD Input: point x^{0}\in\mathbb{R}^{d} , stepsizes \gamma_{k}\geq 0 Set k=0 Workers start computing stochastic gradients at x^{0} while True do Gradient \nabla f(x^{k-\delta^{k}};\xi^{k-\delta^{k}}_{i}) arrives from worker i Update: x^{k+1}=x^{k}-\gamma_{k}\nabla f(x^{k-\delta^{k}};\xi^{k-\delta^{k}}_{i}) Worker i begins calculating \nabla f(x^{k+1};\xi^{k+1}_{i}) Update the iteration number k=k+1 end while This is a greedy and asynchronous method. Once a worker finishes computation of the stochastic gradient, it immediately sends the gradient to the server, which updates the current iterate without waiting for other workers. Notice that, unlike vanilla SGD , the update is performed using the stochastic gradient calculated at the point x^{k-\delta^{k}} , where the index k-\delta^{k} corresponds to the iteration when the worker started computing the gradient, which can be significantly outdated. The sequence \{\delta^{k}\} is a sequence of delays of Asynchronous SGD , where \delta^{k}\geq 0 is defined as the difference between the iteration when worker i started computing the gradient and iteration k , when it was applied. Asynchronous SGD methods have a long history, originating in 1986 ( Tsitsiklis et al., 1986 ) and regaining prominence with the seminal work of Recht et al. (2011) . The core idea behind Asynchronous SGD is simple: to achieve fast convergence, all available resources are utilized by keeping all workers busy at all times. This principle has been validated in numerous studies, showing that Asynchronous SGD can outperform naive synchronous SGD methods ( Feyzmahdavian et al., 2016 ; Dutta et al., 2018 ; Nguyen et al., 2018 ; Arjevani et al., 2020 ; Cohen et al., 2021 ; Mishchenko et al., 2022 ; Koloskova et al., 2022 ; Islamov et al., 2024 ; Feyzmahdavian & Johansson, 2023 ) . 1.1 Assumptions In this paper, we consider the standard assumptions from the nonconvex world. Assumption 1.1 . Function f is differentiable, and its gradient is L –Lipschitz continuous, i.e., \left\|\nabla f(x)-\nabla f(y)\right\|\leq L\left\|x-y\right\|,\;\forall x,y\in\mathbb{R}^{d}. Assumption 1.2 . There exist f^{\inf}\in\mathbb{R} such that f(x)\geq f^{\inf} for all x\in\mathbb{R}^{d} . We define \Delta:=f(x^{0})-f^{\inf}, where x^{0} is the starting point of optimization methods. Assumption 1.3 . The stochastic gradients \nabla f(x;\xi) are unbiased and have bounded variance \sigma^{2}\geq 0 . Specifically, \displaystyle{\mathbb{E}}_{\xi}\left[\nabla f(x;\xi)\right]=\nabla f(x),\;\forall x\in\mathbb{R}^{d}, \displaystyle{\mathbb{E}}_{\xi}\left[\left\|\nabla f(x;\xi)-\nabla f(x)\right\|^{2}\right]\leq\sigma^{2},\;\forall x\in\mathbb{R}^{d}. 1.2 Notations \mathbb{R}_{+}:=[0,\infty); \mathbb{N}:=\{1,2,\dots\}; \left\|x\right\| is the standard Euclidean norm of x\in\mathbb{R}^{d} ; \left\langle x,y\right\rangle=\sum_{i=1}^{d}x_{i}y_{i} is the standard dot product; for functions f,g:\mathcal{Z}\to\mathbb{R} : g=\mathcal{O}(f) means that there exist C>0 such that g(z)\leq C\times f(z) for all z\in\mathcal{Z} , g=\Omega(f) means that there exist C>0 such that g(z)\geq C\times f(z) for all z\in\mathcal{Z}, and g=\Theta(f) means that g=\mathcal{O}(f) and g=\Omega(f); [n]:=\{1,2,\dots,n\}; {\mathbb{E}}\left[\cdot\right] refers to mathematical expectation. 1.3 Related Work Despite the variety of Asynchronous SGD algorithms proposed over the years, a fundamental question remained unresolved: What is the optimal strategy for parallelization in this setting? When we have one worker, the optimal number of stochastic gradients required to find an \varepsilon –stationary point is \Theta\left(\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{\varepsilon^{2}}\right), achieved by the vanilla SGD method ( Ghadimi & Lan, 2013 ; Arjevani et al., 2022 ) . In the parallel setting with many workers, several approaches have been proposed to obtain oracle lower bounds ( Scaman et al., 2017 ; Woodworth et al., 2018 ; Arjevani et al., 2020 ; Lu & De Sa, 2021 ) . Recent work by Tyurin & Richtárik (2023) ; Tyurin (2024) addressed the question by establishing lower bounds for the time complexity of asynchronous methods under the fixed computation model and the universal computation model . Surprisingly, they demonstrated that none of the existing Asynchronous SGD methods are optimal. Moreover, they introduced a minimax optimal method, Rennala SGD , which achieves the theoretical lower bound for time complexity. Table 1: The time complexities of asynchronous stochastic gradient methods, which preform the step x^{k+1}=x^{k}-\gamma_{k}\nabla f(x^{k-\delta^{k}};\xi^{k-\delta^{k}}_{i}), to get an \varepsilon -stationary point in the nonconvex setting. In this table, we consider the fixed computation model from Section 2 . Abbr.: \sigma^{2} is defined as {\rm\mathbb{E}}_{\xi}[\|\nabla f(x;\xi)-\nabla f(x)\|^{2}]\leq\sigma^{2} for all x\in\mathbb{R}^{d}, L is the smoothness constant of f , \Delta:=f(x^{0})-f^{\inf} , \tau_{i}\in[0,\infty] is the time bound to compute a single stochastic gradient by worker i . Method The Worst-Case Time Complexity Guarantees Optimal Adaptive to Changing Computation Times Asynchronous SGD ( Koloskova et al., 2022 ) ( Mishchenko et al., 2022 ) \left(\frac{1}{n}\sum\limits_{i=1}^{n}\frac{1}{\tau_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{n\varepsilon^{2}}\right) ✘ ✔ Naive Optimal ASGD (new) ( Algorithm 3 ; Theorem 2.1 ) \min\limits_{m\in[n]}\left[\left(\frac{1}{m}\sum\limits_{i=1}^{m}\frac{1}{\tau_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right] ✔ ✘ Ringmaster ASGD (new) (Algorithms 4 or 5 ; Theorem 4.2 ) \min\limits_{m\in[n]}\left[\left(\frac{1}{m}\sum\limits_{i=1}^{m}\frac{1}{\tau_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right] ✔ ✔ Lower Bound ( Tyurin & Richtárik, 2023 ) \min\limits_{m\in[n]}\left[\left(\frac{1}{m}\sum\limits_{i=1}^{m}\frac{1}{\tau_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right] — — Algorithm 2 Rennala SGD ( Tyurin & Richtárik, 2023 ) Input: point x^{0}\in\mathbb{R}^{d} , stepsize \gamma>0 , batch size B\in\mathbb{N} Workers start computing stochastic gradients at x^{0} for k=0,\dots,K-1 do g_{k}=0 ; b=0 while b<B do Gradient \nabla f(x^{k-\delta^{k_{b}}};\xi^{k_{b}}) arrives from worker i_{k_{b}} if \delta^{k_{b}}=0 then g_{k}=g_{k}+\nabla f(x^{k-\delta^{k_{b}}};\xi^{k_{b}}) ; \;b=b+1 end if Worker i_{k_{b}} begins calculating gradient at x^{k} end while Update: x^{k+1}=x^{k}-\gamma\frac{g_{k}}{B}

Read the complete text