Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
Authors: Arto Maranjyan
Alexander Tyurin
Peter Richtárik
Venue: ICML 2025 poster (2025)
Keywords: Asynchronous SGD
optimal time complexity
nonconvex optimization
parallel methods
stochastic optimization
Primary area: optimization->large_scale_parallel_and_distributed
TL;DR: Ringmaster ASGD is the first optimal Asynchronous SGD method—it achieves optimality by ignoring gradients with delays larger than a certain threshold.

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 (NeurIPS 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.

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
Artavazd Maranjyan'
Alexander Tyurin" 23 Peter Richtárik
Abstract
optimization, goal is to find an E-stationary point, i.e., (random) vector I E R such that [[]
Asynchronous Stochastic Gradient Descent (Asyn- chronous SGD) a cornerstone method for paral- lelizing learning in distributed machine learning. However, its performance suffers under arbitrarily heterogeneous computation times across workers, leading to suboptimal time complexity and inef- ficiency 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 com- plexity, leaving a significant gap in the literature. In this paper, we propose Ringmaster ASGD, a novel Asynchronous SGD method designed address these limitations and tame the inherent challenges of Asynchronous SGD. We establish, through rigorous theoretical analysis, that Ring- master ASGD achieves optimal time complex- ity under arbitrarily heterogeneous and dynam- ically fluctuating worker computation times. This makes it the first Asynchronous SGD method meet the theoretical lower bounds for time com- plexity in such scenarios.
We consider a setup involving n workers (e.g., CPUs, GPUs, servers), each with access to the same distribution D. Each worker is capable of computing independent, unbiased stochastic gradients with bounded variance (Assumption 1.3). We consider setup with asynchronous, heteroge- neous, and varying computation speeds. We aim 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 dis- tributed training. Although parallelism facilitates rapid con- vergence, variations in worker speeds make effective coor- dination more challenging.
Asynchronous Stochastic Gradient Descent (Asynchronous SGD) is a popular approach for parallelization in such dis- tributed settings. The algorithm operates follows (Algo- rithm 1), formalized below.
Algorithm Asynchronous SGD
Input: point x" E IRd, stepsizes " 2 0
1. Introduction
Set & = 0
Workers start computing stochastic gradients at 2
We consider stochastic nonconvex optimization problems of the form
while True do Gradient V : -6 arrives from worker
min (f(x) Eg (x): ZERE
Update: x²+1 = r²th - 7 V k- : ck-ot Worker begins calculating V [, ckt1)
where f Rd x 8 RR
Rd is linear space, and Sg is sample space. In machine learning, f(; E) denotes the loss of a model parameterized by x on data sample e, and D denotes the distribution of the training dataset. nonconvex
Update the itcration number +1 end while
This is a greedy and asynchronous method. Once a worker finishes computation of the stochastic gradient, it immedi- ately 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 k-8 where the index h - 8¹ corresponds to the iteration when the worker started computing the gradient, which can be significantly
'King Abdullah University of Science and Technology, Thuwal, Saudi Arabia AIRI, Moscow, Russia 'Skolkovo Institute of Sci- ence and Technology, Moscow, Russia. Correspondence to: tavazd Maranjyan httpp:///atomaaaniaagggiubbboobo
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
outdated. The sequence {6*) is a sequence of delays of Asynchronous SGD, where 8t 2 0 is defined the differ- ence between the iteration when worker i started computing the gradient and iteration k, when it was applied.
Algorithm 2 Rennala SGD (Tyurin & Richtárik, 2023)
Input: point x² ε R stepsize y > 0. batch size B E N
Workers start computing stochastic gradients at æ
for k = 0, ...... K do
Asynchronous SGD methods have a long history, originating in 1986 (Tsitsiklis et al., 1986) and regaining prominence with the seminal work of Recht al. (2011). The core idea behind Asynchronous SGD is simple: to achieve fast con- vergence, 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 (Feyzmahda- vian et al., 2016; Dutta et al., 2018; Nguyen et al., 2018; Arjevani et al., 2020; Cohen et al., 2021; Mishchenko et al., 2022; Koloskova al., 2022; Islamov et al., 2024; Feyzmah- davian& & Johansson, 2023).
9k 0; b b=
while b < B do
Gradient [[(x*~0";; ; arrives from worker dkg
if 8h = 0 then
9k = Ik + V end
; ch:); b = b
Worker dk, begins calculating gradient at w
end while
Update: rk+1 x² -9
end for
gradients required to find an E e-stationary point is
1.1. Assumptions
LA
LLLA
E2
In this paper, we consider the standard assumptions from the nonconvex world.
achieved by the vanilla SGD method (Ghadimi & Lan, 2013; Arjevani et al., 2022). In the parallel setting with many work- ers, several approaches have been proposed to obtain oracle lower bounds (Scaman et al., 2017; Woodworth et al., 2018; Arjevani al.. 2020; Lu & De Sa, 2021). Recent work by Tyurin & Richtárik (2023); Tyurin (2025) addressed the question by establishing lower bounds for the time complex- ity 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.
Assumption 1.1. Function f is differentiable, and its gra- dient is L-pisschitz continuous, i.e.,
[x) ffyi)l S L L
vll, Vz, y E Rd.
Assumption 1.2. There exist fiul E I such that (xx Z fintt for all x E Rd. We define A == f(x")- fint, where I. is the starting point of optimization methods.
Assumption 1.3. The stochastic gradients f((x; are unbiased and have bounded variance o² 2 0. Specifically,
Be [))x fx))), Vx E ER.
EE
- V < oo,
Rennala SGD is semi-asynchronous and can be viewed as Minibatch SGD (which takes synchronous iteration/model updates) combined with an asynchronous minibatch collec- tion mechanism. Let us now explain how Rennala SGD works, in the notation of Algorithm 2, which facilitates com- parison with further methods described in this work. Due to the condition 6² O, which ignores all stochastic gradients calculated at the previous points, Rennala SGD performs the step
1.2. Notations
R+ := [0, 00): N = f1, ||||| the standard Eu- clidean norm of x E RR: (x, = >; IJy; is the standard
i-
dot product; for functions f.g: Z + R: g = O(f) means that there exist C > 0 such that g(=) I C x f(z) for all
E Z, 9- {2) means that there exist C >> such that
o(z) C x f f2) for all 2, and g O(f) means that
B
1
g Of) and g R(f); [n]] == {1, 2............................... ... n E [.] refers to mathematical expectation.
kk x
where 5h , g lected asynchronously across all workers. Note that the workers compute the stochastic gradients at the same point w with worker i computing B; 2 O gradients such that -- B, B.
eke are independent samples from D col-
1.3. Related Work
Despite the variety of Asynchronous SGD algorithms pro- posed over the years, a fundamental question remained un- resolved: What is the optimal strategy for parallelization in this setting?
This approach has at least two fundamental drawbacks: (i) Once the fastest worker completes the calculation of
When we have one worker, the optimal number of stochastic
2

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
Table I: The time complexities of asynchronous stochastic gradient methods, which preform the step x = x² The f=(="=0 - 8") , to get an e-stationary point in the nonconvex setting, In this table, we consider the fixed computation model from Section 2. Abbr.: o² is defined Egll fæ { f=))]] S o² for all R L is the smoothness constant of f. A = s(x") - f Ti E [0, oo] is the time bound to compute a single stochastic gradient by worker
Adaptive to Changing Computation Times
Method
The Worst-Case Time Complexity Guarantees
Optimal
Asynchronous SGD
(Koloskova et al., 2022)
2 LA ne
n
Tt
8
(Mishchenko et al., 2022)
[=1
Naive Optimal ASGD (new) (Algorithm 3; Theorem 2.1)
min mE(n]
1
Σ
-1
LA
o LA
x
m=
1=
Ringmaster ASGD (new)
(Algorithms 4 or 5;
min me
m i=1
1
Σ
x
LA
o LA
me²
Theorem 4.2)
Lower Bound (Tyurin & Richtárik, 2023)
min me [m]
LA
o LA
i=1
the first stochastic gradient, [x(*;; ; ing another stochastic gradient at the same point z², even though it already possesses additional information from (ht) Rennala SGD does not update iterate x im- mediately.
), it begins comput-
descent method, Ringmaster ASGD, described in Algo- rithm 4 and Algorithm 5. This is the first asynchronous method achieve optimal time complexity under arbitrary heterogeneous worker compute times (see Table 1). Specifically, in Theorems 4.2 and 5.1, we establish time complexities that match the lower bounds developed by Tyurin & Richtárik (2023); Tyurin (2025).
(ii) Once Rennala SGD finishes the inner while loop, will ignore all stochastic gradients that were being cal- culated before the loop ended, even a worker started the calculation just a moment before. contrast, Asynchronous SGD avoids these issues by fully utilizing all currently avail- able information when asking worker to calculate the next stochastic gradient and not ignoring any stochastic gradi- ents.
Our work begins with another new optimal method, Naive Optimal ASGD (Algorithm 3). We demonstrate that Naive Optimal ASGD achieves optimality under the fixed computation model. However, we find that it is overly simplistic and lacks robustness in scenarios where worker computation times are chaotic and dynamic. To address this limitation, we designed Ringmaster ASGD, which combines the strengths of Naive Optimal ASGD, previous non-optimal versions of Asynchronous SGD methods (Cohen al., 2021; Koloskova et al., 2022; Mishchenko al., 2022), and the semi-synchronous Rennala SGD (Tyurin & Richtárik, 2023).
These revelations raise an intriguing question: Is asyn chronous parallelization fundamentally flawed? the op- timal solution lies in synchronous approaches, should the community abandon Asynchronous SGD and redirect its focus to developing synchronous methods? Perhaps the widespread enthusiasm for Asynchronous SGD methods was misplaced.
Alternatively, could there be a coe-tt--be-iscoveer variant of Asynchronous SGD that achieves optimal time complex- ity? In this work, we answer this question affirmatively. We reestablish the prominence of Asynchronous SGD by proposing a novel asynchronous optimization method that attains optimal time complexity.
All our claims are supported by rigorous theoretical analysis showing the optimality of the method under virtually any computation scenario, including unpredictable downtimes, fluctuations in computational performance over time, delays caused by slow or straggling workers, and challenges in maintaining synchronization across distributed systems (see Sections 4 and 5), Using numerical experiments, we demonstrate that Ringmaster ASGD outperforms existing methods (see Section G).
1.4. Contributions
Our contributions are summarized follows:
We introduce a novel asynchronous stochastic gradient
3

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
2. Preliminaries and Naive Method
optimization process, instead of utilizing all available work- ers, can lead to more efficient and stable approach. As we shall show, this adjustment not only simplifies the compu- tational dynamics, but also proves sufficient to achieve the optimal time complexity.
To compare methods, we consider the fixed computation model (Mishchenko et al., 2022). In this model, is as- sumed that
worker takes no more than 7; seconds to compute a single stochastic gradient.
The idea is to select the fastest [m] := {1, 2..... . m) work- ers, thereby ignoring the slow ones and eliminating delayed gradient updates. We demonstrate that the optimal algorithm involves finding the ideal number of workers m and running Asynchronous SGD (Algorithm 1) on those workers. The method is formalized in Algorithm 3.
and
0 < 1I S2. Tm.
(2)
without loss of generality. However, in Section 5, we will discuss how one can easily generalize result to arbitrary computational dynamics, e.g., when the computation times are not bounded by the fixed values {ri], and can change in arbitrary/chaotic manner in time. Under the fixed com- putation model, Tyurin & Richtárik (2023) proved that the optimal time complexity lower bound is
Algorithm 3 Naive Optimal ASGD
Find m, arg min mE(n]
i T
2: Run Asynchronous SGD (Algorithm 1) [m_.] workers
PLA me
TR =
min mc(n)
(3)
The choice of m, in Algorithm effectively selects the fastest m, workers only. Note that it is possible for m, to be equal to meaning that all workers participate, which occurs when all workers are nearly equally fast. In this case, the harmonic mean in Line unchanged if all T,S are equal, but the right-hand side de- creases. However, if some workers experience large delays, the harmonic mean in Line 1 increases as m grows, intro- ducing trade-off between the two factors. Conversely, if most workers are very slow, it may be optimal to have as few as one worker participating.
seconds achieved by Rennala SGD (Algorithm 2). How- ever, the best analysis of Asynchronous SGD (Koloskova et al., 2022; Mishchenko et al., 2022) with appropriate step- sizes achieves the time complexity (see Sec. L in (Tyurin & Richtárik, 2023))
Algorithm remains
(( (1=21)
LA ne? )
LA 3
TA -
(4)
Note that T3 < TAi this is because minmein] g(m) S g(n) for any function g N -> R. Moreover, TR can arbitrarily smaller. To illustrate the difference, consider an example with T; Vi for all E [n]. Then,
Next, we can easily prove that our algorithm, Naive Optimal ASGD (Algorithm 3), is optimal in terms of time complexity.
Theorem 2.1. Consider the fixed computation model ((1) and (2)). Let Assumptions 1.1, 1.2, and 1.3 hold. Then Naive Optimal ASGD (Algorithm 3) with m, workers achieves the optimal time complexity (3).
OLD LAG21
TR θ max
3//2 / VnEe
and
VnLA
L
Proof. The proof is straightforward. Indeed, the time com- plexity (4) of Algorithm with m. workers is
TA =
max
E
V
see the derivations in Section E. If is large, as is often en- countered in modern large-scale training scenarios, TA can be arbitrarily larger than TR. Thus, the best-known variants of Asynchronous SGD are not robust to the scenarios when the number of workers is large and computation times are heteroggencous/chattic...
m-
LA
LLLA
m.
Ts
m
which equals to (3) due to the definition of m, in Algo- rithm 3.
2. A Naive Optimal Asynchronous SGD
We now introduce our first simple and effective strategy to improve the time complexity TA. Specifically, we hypothe- size that selecting a subser of workers at the beginning of the
To the best of our knowledge, this is the first variant of Asynchronous SGD that provides guarantees for achieving the optimal time complexity.
4

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
Algorithm 4 Ringmaster ASGD (without calculation stops)
Algorithm 5 Ringmaster ASGD (with calculation stops)
Input: point xº E I24, stepsize y > 0, delay threshold
Input: point x" Rd stepsize y > 0, delay threshold
R E N
R E N
Set k=
Set l
Workers start computing stochastic gradients x
Workers start computing stochastic gradients at zz
while True do
while True do
Gradient Vf(x==0"; 8": ck ) arrives from worker i
Stop calculating stochastic gradients with delays 2 R, and start computing new ones at x instead
8* < R then
Update: x4+1 - ~ :
Gradient V=((=~>6* ; ck-5" 5²)) arrives from worker
Worker i begins caleulating V (itht1 ; 2ktz)
Update: x²+11 = I² -V ;t ck-5t
Update the iteration number & k+1
Worker begins calculating (
else
Ignore the outdated gradient V f2
;5) _
Update the iteration number + end while
Worker i begins calculating V 5t5
(The core and essential modifications to Alg. 1 are high- lighted in green. Alternatively, Alg. 4 is Alg. 1 with a specific choice of adaptive stepsizes defined by (5))
end if' end while
2.2. Why Is Algorithm 3 Referred to as "Naive"?
3.1. Description
Note that determining the optimal m, requires the knowl- edge of the computation times . Tu. If the workers' computation times were indeed static in time, this would not be an issue, as these times could be obtained by querying single gradient from each worker before the algorithm is run. However, in real systems, computation times are rarely static, and can vary with from iteration to iteration (Dean & Barroso, 2013; Chen et al., 2016; Dutta et al., 2018; Maranjyan et al., 2025), or even become infinite at times, indicating down-time.
Let us compare Algorithm 4 and Algorithm 1: the only difference, highlighted with green color, lies in the fact that Algorithm disregards "very old stochastic gradients," " which are gradients computed points with significant de- lay. Specifically, Algorithm 4 receives V : ck-5" ), compares 6² to our delay threshold hyperparameter R. If 8 2 R, then Algorithm completely ignores this very outdated stochastic gradient and requests the worker to com- pute new stochastic gradient the most relevant point zt
Naively selecting the fastest m. workers the start of the method and keeping this selection unchanged may therefore lead to significant issues in practice. The computational en- vironment may exhibit adversarial behavior, where worker speeds change over time. For instance, initially. the first worker may be the fastest, while the last worker is the slow- est. In such cases, Naive Optimal ASGD would exclude the slowest worker. However, as time progresses, their per- formance may reverse, causing the initially selected m. workers, including the first worker, to become the slowest. This exposes critical limitation of the strategy: it lacks robustness to time-varying worker speeds.
Notice that Ringmaster ASGD (Algorithm 5) is Algorithm I with the following adaptive stepsize rule:
7
if
8 < R,
7h- =
0,
if
8
R
0,
if
j j=
(5)
84++1
8h
+
1,
if
j & 8 < R
if j & 8 2 R,
where i is the index of the worker whose stochastic gradient is applied at iteration k and where we initialize the virtual sequence of delays 185 i by setting 89 = 0 for all j E [m].
3. Ringmaster ASGD
3.2. Delay Threshold
We are now ready to present our new versions of Asyn- chronous SGD, called Ringmaster ASGD (Algorithm 4 and Algorithm 5), which guarantee the optimal time complexity without knowing the computation times a priori. Both meth- ods are equivalent, up to a minor detail that we shall discuss later. Let us first focus on Algorithm 4.
Returning to Algorithm 4, note that we have a parameter R called the delay threshold. When R R= 1, the algorithm reduces to the classical SGD method, i.e.
k+1 x ~V
since 8* = 0 for all 2 O. In this case, the algorithm becomes highly conservative, ignoring all stochastic gradi-
5

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
ents computed earlier points _ "...., Conversely, if R co, the method incorporates stochastic gradients with arbitrarily large delays, and becomes classical Asyn- chronous SGD. Intuitively, there should be balance "proper" value of R that would i) prevent the method from being overly conservative, while ii) ensuring stability by making sure that only informative stochastic gradients are used to update the model. We formalize these intuitions by proposing an optimal R in Section 4. Interestingly, the value of I does not depend on the computation times.
concept using the delay threshold R.
In summary, while both Rennala SGD and Ringmaster ASGD are optimal from a theoretical perspective, the com- plete absence of synchronization in the latter method intu- itively makes it more appealing in practice, and allows it to collect further gains which are not captured in theory. As we shall see, this intuition is supported by our experiments.
3.5. Comparison to Previous Asynchronous SGD Variants
3.3. Why Do We Ignore the Old Stochastic Gradients?
Koloskova et al. (2022) and Mishchenko et al. (2022) pro- vide the previous state-of-the-art analysis of Asynchronous SGD. However, as demonstrated in Section 2, their analysis
The primary reason is that doing so enables the development of the first optimal Asynchronous SGD method that achieves the lower bounds (see Sections 4 and 5). Ignoring old gradi- ents allows us to establish tighter convergence guarantees. Intuitively, old gradients not only fail to provide additional useful information about the function f. but they can also negatively impact the algorithm's 's performance. Therefore, disregarding them in the optimization process is essential for achieving our goal of developing an optimal Asynchronous SGD method.
does not guarantee optimality, This is due to at least two factors:
(i) their approaches do not discard old stochastic gradients, instead attempting to utilize all gradients, even those with very large delays;
(ii) although they select stepsizes "ik that decrease as the delays increase, this adjustment may not be sufficient to ensure optimal performance, and the choice of their stepsize may be suboptimal compared to (5).
3.4. Comparison to Rennala SGD
3.6. Stopping the Irrelevant Computations
Unlike Rennala SGD, which combines a synchronous Mini- batch SGD update with an asynchronous minibatch col- lection strategy, Ringmaster ASGD is fully asynchronous, which, as we show in our experiments, provided further practical advantages:
If stopping computations is feasible, we can further enhance Algorithm 4 by introducing Algorithm 5. Instead of waiting for workers to complete the calculation of outdated stochas- tic gradients with delays larger than R which would not be used anyway, we propose to stop/terminate these compu- tations immediately and reassign the workers to the most relevant point ,² This adjustment provides workers with opportunity to catch up. as they may become faster and perform computations more efficiently at the updated point.
(i) Ringmaster ASGD updates the model immediately upon receiving a new and relevant (i.e., not too outdated) stochastic gradient. This immediate update strategy is partic- ularly advantageous for sparse models in practice, where dif- ferent gradients may update disjoint parts of the model only, facilitating faster processing. This concept aligns with the ideas of Recht et al. (2011), where lock-free free asynchronous updates were shown to effectively leverage sparsity for im- proved performance.
4. Theoretical Analysis
We are ready to present the theoretical analysis of Ringmas- ter ASGD, We start with an iteration complexity bound: Theorem 4.1 (Proof in Appendix C). Under Assumptions 1.1, 1.2, and 1.3, let the stepsize in Ringmaster ASGD (Al- gorithm 4 or Algorithm 5) be
(ii) Ringmaster ASGD ensures that stochastic gradients computed by fast workers are never ignored. In contrast, Rennala SGD may discard stochastic gradients, even if they were recently initiated and would be computed quickly (see discussion in Section 1).
7 min
At the same time, Ringmaster ASGD adheres to the same principles that make Rennala SGD optimal. The core phi-
2RL
4L
Then
losophy of Rennala SGD is to prioritize fast workers by employing asynchronous batch collection, effectively ignor- ing slow workers. This is achieved by carefully choosing the batch size B in Algorithm 2: large enough to allow fast workers to complete their calculations, but small enough to disregard slow workers and excessively delayed stochastic gradients. Similarly, Ringmaster ASGD implements this
K
[1]]
E
Se,
K
k=U
as long as
8RLA 6
160 LA
K
(6)
22
where R E (1, .) is an arbitrary delay threshold.
6

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
The classical analysis of Asynchronous SGD achieves the same convergence rate, with R defined R = ma 5* (Stich & Karimireddy, 2020; Arjevani et al., 2020). This outcome is expected, as setting R = [ 8 in Ring- master ASGD makes it equivalent to classical Asynchronous SGD, since no gradients are ignored. Furthermore, the analyses by Cohen et al. (2021); Koloskova et al. (2022); Mishchenko et al. (2022) yield the same rate with R n. However, it is important to note that R. is free parameter in Ringmaster ASGD that can be chosen arbitrarily. While setting R = ma] 8 or R = n effectively recovers the earlier iteration complexities, we show that there exists a different choice of leading to optimal time complexities (see Theorems 4.2 and 5.
Proef. From Theorem 4.1, the iteration complexity of Ring- master ASGD is
SRLA
160 LAT
K
(10)
22
Using Lemma 4.1, we know that Ringmaster ASGD requires at most t R)) seconds to finish any R consecutive updates of the iterates. Therefore, the total time at most
K R
((R) x
Without loss of generality, we assume? that LA > E/2. Therefore, using (10), we get
is important to recognize that the iteration complexity (6) does not capture the actual "runtime" performance of the algorithm. To select optimal value for R, we must shift our focus from iteration complexity to time complexity, which measures the algorithm's runtime. We achieve the best practical and effective choice by optimizing the time complexity over R. In order to find the time complexity, we need the following lemma.
K R
LA
))
t(R)
X = ((R)
+
(11)
Re²
It is left to substitute our choice (9) into (11) to get (8). We take (9), noticing that this choice of R minimizes (11) up to universal constant.
To the best of our knowledge, this is the first result in the literature to establish the optimality of a fully asynchronous variant SGD: the time complexity (8) is optimal and aligns with the lower bound established by Tyurin & Richtárik (2023).
Lemma 4.1 (Proof in Appendix A). Let the workers' com- putation times satisfy the fixed computation model ((1) and (2)). Let R be the delay threshold of Algorithum 4 or Algo- rithm The time required to complete any R consecutive iterate updates of Algorithm or Algorithm is at most
The derived time complexity (8) has many nice and desirable properties. First, it is robust to slow workers: if Tm + 00, the expression equals
1 Tr
R m
((R) := min mE(n)
1
(7)
1 m
LA
o² LA
min
mE (n-
m
Combining Theorem 4.1 and Lemma 4.1, we provide our main result.
effectively disregarding the slowest worker. Next, assume that m, is the smallest index that minimizes (8). In this case, (8) simplifies further to
Theorem 4.2 (Optimality of Ringmaster ASGD). Lel As- sumptions 1.1, 1.2, and 1.3 hold. Let the stepsize in Ringmaster ASGD (Algorithm 4 or Algorithm 5) be Ty = min 2RL 4f.==) }. Then, under the fixed computation model (() and (2)), Ringmaster ASGD achieves the op- timal time complexity
-
LA 5
2 LA
m,
This shows that the method operates effectively as if only the fastest m. workers participate in the optimization process, resembling the idea from Algorithm 3. What is important, however, the method determines m. adaptively and auto- matically.
-1
1 m
LA
0LLA m
O
min mEIn]
(8)
1=1
with the delay threshold
4.1. The Choice of Threshold
002 1,
Another notable property of the method and the time com- plexity result in Theorem 4.2 is that the threshold R is inde- pendent of the individual computation times T;- As result,
R -= max
(9)
Note that the value of R does not in any way depend on the computation times (Ti,...,TT).
2LA E, and initial point is an s-stationary point, See Section
Otherwise, using I-ssmoothness, [[
7

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
the method can be applied across heterogeneous distributed systems- where workers have varying speeds-whiie -wille still achieving the optimal time complexity given in (1I), up to a constant factor.
framework of the fixed compulation model (()) and (2)). We now prove Ringmaster ASGD is optimal under virtually any computation behavior of the workers. One way to formalize these behaviors is to use the universal computation model (Tyurin, 2025).
a tighter, constant-level expression for the optimal thresh- old desired, It can be computed explicitly. that case, it will depend on the values of Tg. The optimal R solves
For each worker i E [n], we associate a computation power function 8, : R+ + R.. The number of stochastic gradi- ents that worker i can compute between times To and Ti given by the integral of its computation power et, followed by applying the floor operation:
σ² Re
arg min R21
((R)
1
which follows from (11) after discarding constants indepen- dent of R. Here, t(R) denotes the total time required for R consecutive iterations, and upper bounded by (7).
"# of stoch. grad. in [To, TiJ" = J. us (F(( (12)
Substituting this bound yields the following expression for the optimal R:
The computational power characterizes the behavior of workers, accounting for potential disconnections due to hard- ware or network delays, variations in processing capacity over time, and fluctuations or trends in computation speeds. The integral of e over given interval represents the com- putation work performed. If o, is small within [To, Ti), the integral is correspondingly small, indicating that worker i performs less computation. Conversely, if o; is large over [To, Tı], the worker is capable of performing more compu- tation.
R max
0
1
E
where
( (
(
m" = arg min
+
1
+
2
+
mEIn]
ms
For our analysis, we only assume that v; is non-negative and continuous almost everywhere We use this assumption non-explicitly when applying the Riemann integral. The computational power 0; can even vary randomly, and all the results discussed hold conditional on the randomness of {u:}.
As the expression shows, the optimal threshold R depends on m", which in turn is determined by the values.
4.2. Proof Techniques
Several mathematical challenges had to be addressed to achieve the final result. Lemmas 4. I and 5.1 are novel, as es- timating the time complexity of the asynchronous Ringmas- ter ASGD method requires distinct approaches compared to the semiisynncronous Rennala SGD method because Ring- master ASGD is more chaotic and less predictable. Com- pared to (Koloskova al., 2022; Mishchenko et al., 2022), the proof of Theorem 4.1 is tighter and more refined, as we more carefully analyze the sum
Let us examine some examples. If worker i remains inac- tive for the first seconds and then becomes active, this corresponds to (T) for all т S and (T( > 0 for allow v; to exhibit periodic or
all r > f. Furthermore, even chaotic behavior'. The universal computation model reduces to the fixed computation model when v4(() = 1/T. for all 2 0 and i E [m.] In this case, (12) = [Ti-2n/r.]) indicating that worker computes one stochastic gradient after To + T; seconds, two stochastic gradients after To + 2T; seconds, and forth.
K
84 27
Note that Theorem 4.1 is valid under any computation model. Next, we introduce alternative to Lemma 4.1 for the universal computation model.
in Lemma C.2. We believe that the simplicity of Ringmaster ASGD, combined with the new lemmas, the refined analysis, and the novel choice of Rt in Theorem 4.2, represents a set of non-trivial advancements that enable us to achieve the optimal time complexity.
Lemma 5.1 (Proof in Appendix B). Let the workers' com- putation times satisfy the universal computation model. Let R be the delay threshold of Algorithm or Algorithm As- sume that some iteration starts at time To- Starting from this iteration, the R consecutive iterate updates of Algorithm 4
5. Optimality Under Arbitrary Computation Dynamics
Thuss it can be discontinuous and "jump" on a countable set. *For example, vy(t) might behave discontinuously follows: (t) = 0.5t sin(10r) for t 10, (t(t) = 0 for 10 t 20, and (t) = max(80 (80- 0.5t, 0).
In the previous sections, we presented the motivation, im- provements, comparisons, and theoretical results within the
8

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
or Algorithm 5 will be performed before the time
time complexity. By employing a carefully designed algo- rithmic approach, which can be interpreted Asynchronous SGD with adaptive step sizes (5), we successfully reach this goal. By selecting an appropriate delay threshold R in Al- gorithm 4, the method attains the theoretical lower bounds established by Tyurin & Richtárik (2023); Tyurin (2025).
Σ - 4 1=1
T
T(R,T)) :- -min 020:
vi(T)dd
2 R
4 In
This result extends Lemma 4.1. Specifically, if v;(() = 1/r for all t 2 0 and E [n]. can be shown that TRR, To) To θ (I(R) for all To O.
Future work can explore heterogeneous scenarios, where the data on each device comes from different distributions, which are particularly relevant for federated learning (FL) (Konečný et al., 2016; McMahan et al., 2016; Kairouz et al., 2021). In FL, communication costs also become crucial, making it worthwhile to consider similar extensions (Alis- tarh et al., 2017; Tyurin et al., 2024b; Tyurin & Richtárik, 2024). It would be also interesting to design a fully asyn- chronous analog to the method from (Tyurin al., 2024a), Additionally, discussed by Maranjyan al. (2025), com- putation and communication times can be treated as random variables. It would be valuable to investigate these cases further and derive closed-form expressions for various dis- tributions.
Combining Theorem 4.1 and Lemma 5.1, we are ready to present our main result.
Theorem 5.1 (Optimality of Ringmaster ASGD; Proof in Appendix D). Let Assumptions 1.1, 1.2, and 1.3 hold. Let the stepsize in Ringmaster ASGD (Algorithm 4 or Algo- rithm 5) be
1
7 min
2RL
4Lo²
and delay threshold
R= max
1,
A Acknowledgments
Then, under the universal computation model, Ringmaster ASGD finds an e-stationary point after at most TR seconds, where K : |SLA] and Tg is the Thhh element of the following recursively defined sequence:
The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) Center of Excellence for Generative AI, under award number 5940, iii) SDAIA-KAUSE Center of Excel- lence in Artificial Intelligence and Data Science The work of A.T. was supported by the Ministry of Economic Devel- opment of the Russian Federation (code 25- 25-139-66879-1 0003). We would like to thank Adrien Fradin for valuable discussions and helpful suggestions that contributed to the improvement of this work.
[
L"
Tk: = min
T T20:
ve(r)dr
2 R
1=1
TK-1
for all K 2 1 and To O.
Granted, the obtained theorem is less explicit than Theo- rem 4.2. However, this is the price to pay for the generality of the result in terms of the computation time dynamics it allows. Determining the time complexity T& requires com- puting Ti, T2, and so on, sequentially. However, in certain scenarios, Tk can be derived explicitly. For example, if (t()) 1/7, for all 2 0 and [n], then Tg is given by (8). Furthermore, Ti represents the number of seconds required to compute the first R stochastic gradients, 72 rep- resents the time needed to compute the first 2 x R stochastic gradients, and so on. Naturally, to compute T2, one must first determine Tı, which is reasonable given the sequential nature of the process.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. QSGD: Communication-effiiiee SGD via gradient quantization and encoding. In Advances in Neural In- formation Processing Systems (NIPS), pp. 1709-1720, 2017.
The obtained result is optimal, aligns with the lower bound established by Tyurin (2025), and cannot be improved by any asynchronous parallel method.
6. Conclusion and Future Work
Arjevani, Y., Shamir, O., and Srebro, N. A tight convergence analysis for stochastic gradient descent with delayed up- dates. In Algorithmic Learning Theory, pp. 112- PMLR, 2020.
In this work, we developed the first Asynchronous SGD method, named Ringmaster ASGD, that achieves optimal
9

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pp. 1-50, 2022.
Konečný, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. 'T, and Bacon, D. Federated learning: Strate- gies for improving communication efficiency. arXiv preprint arXiv: 100vv:6610005422 2016.
Chen, J., Pan, X., Monga, R., Bengio, S., and Jozefowicz, R. Revisiting distributed synchronous SGD, arXiv preprint arXiv: 00981, 2016.
LeCun, Y., Bottou, L.,, Bengio, Y., and Haffner, P. Gradient- based learning applied to document recognition. Proceed- ings of the IEEE, 86(1 0::278--3224, 1998.
Cohen, A., Daniely, A., Drori, Y., Koren, T., and Schain, M. Asynchronous stochastic optimization robust arbi- trary delays. Advances in Neural Information Processing Systems, 34:9024-9035, 2021.
Lian, X., Zhang, W., Zhang, C., and Liu, J. Asynchronous decentralized parallel stochastic gradient descent. In In- ternational Conference on Machine Learning, pp. 3043- 3052. PMLR, 2018.
Lu, Y. and De Sa, C. Optimal complexity in decentral- ized training. In International Conference on Machine Learning, pp. 7111-7123, PMLR, 2021.
Dean, J. and Barroso, L. A. The tail at scale. Communica- lions of the ACM, 56(2):74-80, 2013.
Dean, J., Corrado, G., Monga, R., Chen, K., Devin, M., Mao, M., Ranzato, M., Senior, A., Tucker, P., Yang, K., et al. Large scale distributed deep networks. Advances in Neural Information Processing Systems, 25, 2012.
Maranjyan, A., Omar, O. S., and Richtárik, P. MindFlayer SGD: Efficient parallel SGD in the presence of heteroge- neous and random worker compute times. In Conference on Uncertainty Artificial Intelligence, 2025.
Dutta, S., Joshi, G., Ghosh, S., Dube, P., and Nagpurkar, P. Slow and stale gradients can win the race: Error- runtime trade-offs in distributed SGD. In International Conference on Artificial Intelligence and Statistics, pp- 803-812. PMLR, 2018.
McMahan, H. B., Moore, E., Ramage, D., and y Arcas, A. Federated learning of deep networks using model averaging. arXiv preprint arXiv: /ttv:/602..0 06220002200552 2:2, 2016.
Mishchenko, K., Bach, F., Even, M., and Woodworth, B. Asynchronous SGD beats minibatch SGD under arbitrary delays. arXiv preprint arXiv:2206.07633 2022.
Feyzmahdavian, H. R. and Johansson, M. Asynchronous iterations in optimization: New sequence results and sharper algorithmic guarantees. Journal of Machine Learning Research, 14155 2023.
Nesterov, Y. Lectures on convex optimization, volume 137.
Springer, 2018
Nguyen, L., Nguyen, P. H., Dijk, M., Richtárik, P., Schein- berg, K., and Takác, M. SGD and Hogwild! convergence without the bounded gradients assumption. In Interna- tional Conference on Machine Learning, pp. 3750-3758. PMLR, 2018.
Feyzmahdavian, H. R., Aytekin, A., and Johansson, M. An asynchronous mini-bater algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, 61(12)3770-3374, 2016.
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2333 2013.
Recht, B., Re, C., Wright, S., and Niu, F. Hogwild!: lock- free approach parallelizing stochastic gradient descent. Advances in Neural Information Processing Systems, 24, 2011.
Islamov, R., Safaryan, M., and Alistarh, D. AsGrad: A sharp unified analysis of asynchronous-SGi algorithms. In International Conference on Artificial Intelligence and Statistics, pp. 649-657. PMLR, 2024.
Scaman, K., Bach, F,, Bubeck, S., Lee, Y. T., and Mas- soulié, L. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In Interna- tional Conference on Machine Learning, pp. 3027-3036. PMLR, 2017.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z.,, Cormode, G., Cummings, R., al. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
Stich, S. U. and Karimireddy, S. P. The error-feedback framework: SGD with delayed gradients. Journal of Machine Learning Research, 21(237):1 2020.
Koloskova, A., Stich, S. U., and Jaggi, M. Sharper conver- gence guarantees for Asynchronous SGD for distributed and federated learning. Advances in Neural Information Processing Systems, 15:17202-17155 2022.
Tsitsiklis, J., Bertsekas, D., and Athans, M. Distributed asynchronous deterministic and stochastic gradient opti- mization algorithms. IEEE Transactions on Automatic Control, (1(9):803-88)) 812, 1986.
10

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
Tyurin, A. Tight time complexities in parallel stochastic op- timization with arbitrary computation dynamics. In 13th International Conference on Learning Representations, 2025.
Tyurin, A. and Richtárik, Optimal time complexities of parallel stochastic optimization methods under fixed computation model. Advances in Neural Information Processing Systems, 36, 2023.
Tyurin, A. and Richtárik, P. On the optimal time complex- ities in decentralized stochastic asynchronous optimiza- tion. Advances in Neural Information Processing Systems, 37, 2024.
Tyurin, A., Gruntkowska, K., and Richtárik, P. Freya PAGE: First optimal time complexity for large-scale nonconvex finite-sum optimization with heterogeneous asynchronous computations. Advances in Neural Information Process- ing Systems, 37, 2024a.
Tyurin, A., Pozzi, M., Ilin, I., and Richtárik, Shadowheart SGD: Distributed asynchronous SGD with optimal time complexity under arbitrary computation and communi- cation heterogeneity. Advances in Neural Information Processing Systems, 37, 2024b.
Woodworth, B. E.,, Wang, J., Smith, A., McMahan, B., and Srebro, N. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. Advances in Neural Information Processing Systems, 31, 2018.

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
A. Proof of Lemma 4.1
Lemma 4.1. Let workers' computation times satisfy the fixed computation model ((1) and (2)). Let R be the delay threshold of Algorithm or Algorithm 5. The time required to complete any R. consecutive iterates updates of Algorithm or Algorithm 5 is at most
m m
t(R) := min mein]
(1+
(7)
Proof. We now focus on Algorithm 5. Let us consider a simplified notation of ((R):
m Σ
-
R
t: := t(R) 2 min me [Ps
(R +m) m)
2 min
1
me [8)
Let us fix any iteration k, and consider the consecutive iterations from k worker will be stopped at most time, meaning that most stochastic gradient will be ignored from the worker. After that, the delays of the next stochastic gradients will not exceed It 1 during these iterations. As soon as some worker finishes calculating a stochastic gradient, it immediately starts computing new stochastic gradient.
1. By the design of Algorithm 5, any
Using a proof by contradiction, assume that Algorithm 5 will not be able to finish iteration k: + R 1 by the time t. At the same time, by the time all workers will calculate at least
- T - 1.0)
max
(13)
1=1
stochastic gradients with delays R because is the number of stochastic gradients that worker i can calculate after t seconds. We subtract 1 to account for the fact that one stochastic gradient with large delay can be ignored. Let us take an index
j arg min mE(n]
Σ
m
1
-1 (R + m)
Ts
Since [ 2 x 1 for all & 2 0, we get
- 1,0
max
T. - 1,0
max
1,0
2
2j
1=1
i=1
1=1
2
(R+3*)
-2j = 2R 2ÿ - 2j 2 R.
We can conclude that by the time (7), the algorithm will calculate R stochastic gradients with delays < R and finish iteration
A + R - 1, which contradicts the assumption.
The proof for Algorithm 4 is essentially the same. In Algorithm 4, one stochastic gradient with large delay for each worker will be ignored, and other stochastic will be used in the optimization process.
B. Proof of Lemma 5.1
Lemma 5.1. Let the workers' computation times satisfy the universal computation model. Let R. be the delay threshold of Algorithum& 4 or Algorithm 5. Assume that some iteration starts at time To- Starting from this ileration, the R consecutive iterative updates of Algorithm 4 or Algorithum will be performed before the time
T(R, To) := min
T20:
0:
Σ
1
vx(T)dr
2 R
4
To
i=1
12

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
Proof. Let
T T(R,T) -min T 0:
Σ 1=1
(((Tdd 2 R B
To
At the beginning, this proof follows the proof of Lemma 4.1 up to (13). Here we also use proof by contradiction and assume that Algorithm will not be able to do consecutive iterative updates by the time T.
Instead of (13), all workers will calculate least
= Σ max {L (((T)dr - 1,00
stochastic gradients by time 7 because, due to (12), J/ (i(T)dr] is the number of stochastic gradients that worker i will calculate in the interval [To, Tj. We define V;(T) = 12, (((T)dr. Thus,
(((T) 4
N = max [LV;(T) - 1, and T = min T200 Σ
2
R
Let us additionally define
(i(T)
S i i [n]
(14)
Note that
12
Vi(T)
Vi(T)
(15)
4
since
V.TT
for all &f S. Using simple algebra, we get
N max [V)( 1,0} 2 Σ max -
[V(T) |
Vi(T)
2|S],
ies
iES
where the last inequality due [x] 2 r 1 for all x E Next
N
VI(T)
+ 2
Σ 2|S|
VI(T) 2
VI(T) 4
(15)
Vi(T) 4
N R
iES
iES
iES
where the last inequality due to the definition of T. As in the proof of Lemma 4.1, we can conclude that by the time T (R, To), the algorithm will calculate stochastic gradients with delays < R and finish iteration A: + - which contradicts the assumption.
C. Proof of Theorem 4.1
Theorem 4.1. Under Assumptions 1.1, 1.2, and 1.3, let the stepsize in Ringmaster ASGD (Algorithm 4 or Algorithm 5) be
min
2RL
4Lo²
Then, the following holds
K
V (2 |1 SE
E
K
km0
for
SRLA
160 LA 2
KZ
(6)
where R (1,2,... an arbitrary delay threshold.
13

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
We adopt the proof strategy from Koloskova al. (2022) and rely the following two lemmas.
Lemma C.1 (Descent Lemma; Proof in Appendix C.I), Under Assumptions 1.1 and 1.3, if the stepsize in Ringmaster ASGD (Algorithm 4 or Algorithm 5) satisfies Y S Z the the following inequality holds:
Es+1 [f (x (z++t)] S (2*)
V [
2 V (1 (1--5)))
1
2.
722 0
where Ex+1 [-] represents the expectation conditioned on all randomness up to iteration k.
Lemma C.2 (Residual Estimation; Proof in Appendix C.2). Under Assumptions 1.1 and 1.3, the iterates of Ringmaster ASGD (Algorithm 4 or Algorithm 5) with stepsize y S 2RL satisfy the following bound:
K
xk x0
"1]
2
202
E
E
V
K
212(K
k=0
k=
With these results, we are now ready prove Theorem 4.1.
Proof of Theorem 4.1. We begin by averaging over + iterations and dividing by y in the inequality from Lemma C.I:
E [vf
+ E V ()))))))))))))))))))))))))))))
(11))
A
I 0²
+
K
7K + 1)
1 1
K
E
x
x
8t
2
K
+ 2
k=0
Next, applying Lemma C.2 to the last term, we have:
K Σ k=0
1 VV (x*) [²]
+ + [()00=0>>)))))
(1]]
A
2
02
+
7( +1)
2
+
K
E
v s
- 0
)1
+
22000
4(K +1)
k=0
Simplifying further, obtain:
K
V (z |1
7(K +1) 2yyLo
2A
K
Now, we choose the stepsize "y as:
1
1
7 min
2RL 4Lo²
2RL
With this choice 7, it remains to choose
SARL
16ALo²
K 2
2²
to ensure
K
Σ E (2+))) sc.
K 1
This completes the proof.
14

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
C.I. Proof of Lemma C.I
Lemma C.I (Descent Lemma). Under Assumptions 1.1 and 1.3, the stepsize in Ringmaster ASGD (Algorithm or II. the following inequality holds:
Algorithm 5) satisfies
Ex+1 [x(+t1]] sf fx())*
2 Vf [ -
(
)|²
222
x
2 0 +
2
2
where Ex+1 [ represents the expectation conditioned on all randomness up to iteration k.
Proof. Assume that we get stochastic gradient from the worker with index is when calculating x++1, Since the function is L-smooth (Assumption 1.1), we have (Nesterov, 2018):
Ex+1 [f (x++))] S (x*) Bx++
Vv
(x*),
Vf
xx 88" -(h00)))
))
+
2" -- Ex+1
L
|| ; 11?
Using Assumption 1.3, we estimate the second term as
Vf (2* )) 1 (x*) + vf (x | 4s (at) - vs (a* )1²]
t = (v
Using the variance decomposition equality and Assumption 1.3, we get
[5 (2- 8+
::t -chh-"") v. (w (0==))1 )1}] | (1(500)))
1/ Ex+1
$ 0² + Vf (22
Vf (x*) - Vs (2 we get:
Combining the results for and 12, and using L-smoothness to bound
Ex+1 [f (x*+1]] (x*)
2 || |1 -3
(2
71²
x
x k-ot 12
+
22L
0².
2
2
Finally, applying the condition S 2L completes the proof.
C.2. Proof of Lemma C.2
Lemma C.2 (Residual Estimation). Under Assumptions 1.1 and 1.3, the iterates of Ringmaster ASGD (Algorithm 4 or
Algorithm: 5) with stepsize S 2RL satisfy the following bound:
K
K
E
1
k-
k-
E
vs x (2
+ T.
2oa
K
+
212
K
+
k=0
Proof. Assume that we get stochastic gradient from the worker with index is when calculating x+1 We begin by
15

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
expanding the difference and applying the tower property, Assumption 1.3, Young's inequality, and Jensen's inequality:
E
2
k-6
=
Σ
Vf
x 22
j=k- 8k
k-1
2B
Σ
7V (V(
+2
Σ
(Vi (1)-b;;;;) 4. (xd-b.)
j=kー 8k
Σ
< 2E
v (
+ 720"
j= 8t
< y0²
Σ
E
Vf
(x 4) 11
+ 28 700
j=k-8* 8h
Using that 7
and 8 < R - (by the design), we obtain:
2RL
| - s 06
Σ E
[ + 700
2L2R
j=k-5 5t
Next, summing over all iterations k O...., K, get:
E
z b- 5t ||]
Σ
E [[[ j=
+ (K + 1) 7
2L2
Observe that each squared norm Vf (x) (1)= || in the right-hand sums appears at most R times due to the algorithms'
design. Specifically, 8* < R - 1 for all k > O, ensuring no more than It squared norms appear in the sums. Therefore:
K >
E
x ||]
Σ
Vf
x (at )1]
(K 1) 722
2L
O
0
Finally, dividing the inequality by K + completes the proof.
D. Proof of Theorem 5.1
Theorem 5.1. Let Assumptions 1.1. 1.2, and 1.3 hold. Let the stepsize in Ringmaster ASGD (Algorithm 4 or Algorithm 5) be 7 min Iें. af.=); ) and delay threshold R max 11, { } Then, under the universal computation model, Ringmaster ASGD finds an e-stationary point after at most T & seconds, where K = 48LA and R is the Kth element of the following recursively defined sequence:
Tk min 720: Σ 1 1 vi(r)dr R
for all K 2 1 and To 0.
Proof. From Theorem 4.1, the iteration complexity of Ringmaster ASGD is
8RLA
160 LA
K
(16)
2
6
16

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
Without loss of generality, we assume that 5 LA > e/2.
Thus,
SRLA
LG 6²
IGRLA
32.2
32o
and
K
16LA
320 LA
K
R x
R
Re
Using the choice of R, we get
48LA
K Rx
In total, the algorithms will require 1SLA by I consecutive updates of I to find an e-stationary point. Let us define K=
48LA Using Lemma 5.1, we know that Ringmaster ASGD requires at most
1 l. (i(T)dr
T T== min T T2
0:
Σ
R]
seconds to finish the first R consecutive updates of the iterates. Since the algorithms will finish the first R consecutive updates after at most Ti seconds, they will start the iteration R + 1 before time Ti. Thus, using Lemma 5,1 again, they will require at most
T2 T(R, min T T2 0: Σ [" wx(T)dr 2 R
seconds to finish the first R consecutive updates. Using the same reasoning, they will finish the first [BLA x consecutive updates after at most
1 T
Tk = T(R,TRR min
T 0
vz(T)dr
2 R zR}
4
JR-
1=1
seconds.
E. Derivations for the Example from Section
Let Vi for all i [n], then
-1
LA
0² LA
)
TR θ
min me/n|
+
Vi
m
i=
Using
m
- (Vm)
Vi
=
for 2 1, we simplify the term:
1 m
O(vm),
m71
LA
a² LA
LA
GLLA) Vme²
TR min
+
min mEin]
mm(n)
mg²
E
The minimum is achieved when the two terms are balanced, i.e., at
m min
7
'Otherwise, using J.ssoothnesss, |/((>)]| < 2LA < s, and the initial point is an e-stationary point
17

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
Substituting this value of m, we obtain:
OLA
d'LA])
Vn=² )
Tk = 4
max
e3/2
We now consider Tx:
(1>-4)
-1
LA
T T.
)
TA = θ
i=1
Tt
e
NE?
Using
Σ
1 = O
Vi
1=1
for n. 2 1, we simplify the term:
n
-1
0 (Vn).
Vi
71
Substituting this result into Ta, we have:
TA = + (vr
LA
o² LA LA
)) =0
LAVI
d v /ne2
LAVn LL
max
ns²
v nne2
F. When the Initial Point is an e-Stationary Point
Under the assumption of I-smoothness (Assumption 1.1), we have:
L bly z||
f(y) f()) + (Vf(z), x)
2
for all x, y E Rd. Taking x VV)(2),
( f((x)
1 2L [x)
Since f(x - [.v())) 2 finf and taking x = Z0, we get
|)(0>>|| 2TA
Thus, 2LA < e, then [+)'))) Se.
G. Experiments
Asynchronous SGD has consistently demonstrated its effectiveness and practicality, achieving strong performance in various applications (Recht et al., 2011; Lian et al., 2018; Mishchenko et al., 2022), along with numerous other studies supporting its utility. Our main goal of this paper was to refine the method further and establish that it is not only practical but also theoretically optimal.
At the same time, Tyurin & Richtárik (2023) found out that the previous version of Asynchronous SGD has slow convergence when the number of workers is large, and their computation performances are heterogeneous using numerical experiments (see Figure 1).
We now reproduce this experiment with the new Ringmaster ASGD method and compare it with the previous Asynchronous SGD (we call it Delay-Adaptive ASGD in our experiments and take the version from (Mishchenko et al., 2022)) and Rennala SGD methods. The optimization task is based on the convex quadratic function f : Rd - R such that
1 x Ax - -TT Va E Id..
f(x)
2
18

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
Asynchronous SGD: Step size: 0.00048628125
Asynchronous Step 0.000244140625
10a
Asynchronous Step size: 0.0001220703125
Minibatch SGD: Step size: 1.0 (Timeout)
Minibatch SGD: Step size: 2.0 (Timeout)
10a
Minibatch SGD: Step size: 0.5 (Timeout)
flx
Rennala SGD: Step size: 2.0 Batch Size: 40
Rennala SGD: Step size: 2.0 Batch Size:
100
Rennala SGD: Step size: 1.0 Batch Size;
10-1
10-2
400
600
800
1000
times (seconds)
Figure Experiment with 10000 from (Tyurin & Richtárik, 2023) showing the slow convergence of the previous
Asynchronous SGD method.
where
A
-1
Rdxd b
b=
1 4
0
E
Rd.
-1
-1
We set d = 1729 and 6174. Assume that all workers have access to the following unbiased stochastic gradients:
vf(z.() Vf(x)++
where & (0000
The experiments were implemented in Python. The distributed environment was emulated on machines with Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz. The computation times for each worker are simulated as T; = i [nsl for all i E [n]. where ~ N (0, i). We tuned the stepsize from the set {5" p E [-5,5] Both the batch size for Rennala SGD and the delay threshold for Ringmaster ASGD were tuned from the set {[nz /4 E No.. The experimental results are shown in Figure 2.
The obtained result confirms that Ringmaster ASGD is indeed faster than Delay-Adapti ASGD and Rennala SGD in the considered setting. One can see the numerical experiments support that our theoretical results, and we significantly improve the convergence rate of the previous version of Asynchronous SGD (Delav-Adaptive ASGD).
G.1. Neural Network Experiment
To show that our method also works well for neural networks, trained small 20-layer neural network with ReLU activation on the MNIST dataset (LeCun et al., 1998). We used the same number of workers as in the previous experiment (n = 6174) and kept the same time distributions. The results are shown in Figure 3.
19

---

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
Ringmaster ASGD: 7 0.2, R 6
Rennala SGD: y 1, B 6
10a
Delay-Adaptive ASGD: 7 0.00032
finf
100
10-2
10-4
250
500
750
1000
1250
1500
1750
2000
Runtime (seconds)
Figure 2: Experiment with n 6174 and d 1729 showing the convergence of Ringmaster ASGD, Delay-Adaptive ASGD, and Rennala SGD.
10²
Ringmaster ASGD: Rennala SGD: 7 y= =,, B = 6
10a
DelpyiAd ASGD: 0.0016
10a
finf
10-2
10-5
f(x²)
10-8
10-11
10-11
200
400
600
800
1000
Runtime (seconds)
Figure 3: We an experiment small 2-layer neural network with ReLU activation the MNIST dataset, showing that our method, Ringmaster ASGD, is more robust and outperforms Delay-Adaptive ASGD and Rennala SGD.
20


Reviews:
[{"review_id": "g2OYuU1r9u", "reviewer": "Reviewer_Mp5i", "summary": "In the settings when all clients compute the same function, the paper introduces a family of Asynchronous SGD algorithms:\n\n-- A trivial algorithm which chooses the optimal number of fastest machines. The paper shows that this algorithm achieves the optimal convergence rate. The downside of the algorithm is that it doesn’t handle the case when clients have variable performance.\n\n-- Two algorithms which ignore or cut off computations which last more than some specified number of rounds. For these algorithms, the paper shows optimal convergence rate for the settings when the client performances are constant and when they are variable.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\n> The techniques feel incremental, with the main proof being completed mainly using Lemmas from Koloskova et al (2022).\n\nWe acknowledge that the proof is not complicated, but we see this as an advantage rather than a limitation. A small yet impactful change can often be more valuable than a more complex modification achieving the same result.\n\nOur work provides the first proof of the optimality of asynchronous SGD in the literature. We establish this through a simple yet non-trivial and elegant idea: introducing a threshold on gradient delays. Surprisingly, this fundamental algorithmic improvement had been previously overlooked.\n\nMoreover, our approach significantly alters the mathematical properties of the method. Unlike classical asynchronous SGD, it discards outdated and irrelevant data, leading to a refined theoretical analysis. Specifically, we analyze the sum $\\sum_{k=0}^K \\mathbb{E}[|x^k - x^{k-\\delta^k} |^2]$ in Lemma C.2 more carefully, improving upon the analysis in [1,2]. Additionally, Lemma 4.1, Theorem 4.2, Lemma 5.1, and Theorem 5.1 present entirely new results.\n\n> I would like to recommend restructuring the paper as follows:\n\nThank you for the suggestions. We will make the changes for the camera-ready version of the paper.\n\n> You assume that all $v_i$ are continuous. This might be an unrealistic assumption; moreover, I don't think you use this assumption.\n\nWe assume that $v_i$ is non-negative and continuous almost everywhere. It means that $v_i$ can be discontinued in a countable set of points, and our analysis still works. We believe that this is general enough since it allows the computation powers to \"jump\" on a countable set of times. We use this assumption (non-explicitly) when integrating $v_i$. Under this assumption, $v_i$ is Riemann integrable. Notice that we can easily assume that $v_i$ is measurable and use the Lebeague integral, but for clarity, we work with the Riemann integral.\n\n> Your algorithm uses a binary decision for every gradient: use it if the delay is less than R, and ignore it otherwise. This is fine if one knows a proper value of R, which introduces an additional hyperparameter. Do you think it's possible to avoid using such a hyperparameter, e.g. by scaling the gradients inversely proportionally to the delay?\n\nWe think it may be possible to make $R$ adaptive by estimating it in an online fashion, but this is beyond the scope of our current research and is left for future work.\n\nRegarding scaling. Prior work [1,2] explored this approach by scaling gradients inversely proportionally to their delay, a method known as delay-adaptive ASGD. However, this does not achieve optimal time complexity—some outdated gradients must be ignored. We discuss this in the “Comparison to Previous Work” section (lines 306-318).\n\nThat said, introducing an additional hyperparameter is unavoidable. However, the choice of $R$ is not particularly sensitive. Specifically, in Theorem 4.2, setting $R = \\max\\\\{1, \\lceil c \\frac{\\sigma^2}{\\varepsilon} \\rceil \\\\}$ for any absolute constant $c$ still ensures optimal time complexity up to a constant factor depending on $c$.\n\n[1] Koloskova, A., et al. Sharper convergence guarantees for Asynchronous SGD for distributed and federated learning. NeurIPS 2022.\n\n[2] Mishchenko, K., et al. Asynchronous SGD beats minibatch SGD under arbitrary delays. NeurIPS 2022.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "-- I don’t think paragraph “Proof techniques” actually provides any insights about the proof\n\n-- The techniques feel incremental, with the main proof being completed mainly using Lemmas from Koloskova et al (2022).", "experimental_designs_or_analyses": "Ok", "relation_to_broader_scientific_literature": "Ok", "essential_references_not_discussed": "Ok", "other_strengths_and_weaknesses": "Ok", "other_comments_or_suggestions": "I would like to recommend restructuring the paper as follows:\n\n-- Move some of the discussion right before 1.1 to “Related work”\n\n-- Move section 1.3 earlier, before section 1.1\n\n-- Move paragraph “Why do we ignore the old stochastic gradients?” earlier, maybe around Equation (3)\n\n-- You might want to clarify that there are other definitions of ε-stationary point (in particular, ones which would use ε^2)\n\n-- You don’t refer to Table 1 in the text\n\n-- Footnote 2 might be not obvious to a reader\n\n-- You assume that all v_i are continuous. This might be an unrealistic assumption; moreover, I don’t think you use this assumption.\n\n-- In Theorem 4.2, since you know the value of R, you can simplify the statement", "questions_for_authors": "Your algorithm uses a binary decision for every gradient: use it if the delay is less than R, and ignore it otherwise. This is fine if one knows a proper value of R, which introduces an additional hyperparameter. Do you think it’s possible to avoid using such a hyperparameter, e.g. by scaling the gradients inversely proportionally to the delay?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K7GHm6COaT", "reviewer": "Reviewer_kWtQ", "summary": "This paper proposes a method called Ringmaster ASGD to achieve the optimal time complexity for asynchronous methods as described in [1]. Ringmaster ASGD is a simple modification of vanilla asynchronous SGD. In Ringmaster ASGD, gradients with large delays (>R) are discarded.\n\n[1] Tyurin, A. and Richt´arik, P. Optimal time complexities of parallel stochastic optimization methods under a fixed computation model. Advances in Neural Information Processing Systems,36,2023.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\n> As shown in Theorem 4.2 and Theorem 5.1, the value of the delay threshold does not depend on the computation times. Does this imply that the same value of R can be used across different distributed systems? This conclusion is somewhat confusing and counter-intuitive. It seems that the optimal value of R should be related to the computing capability of the workers in the cluster.\n\nTo clarify, in the proof of Theorem 4.2, we select $R$ to minimize the upper bound on time complexity (Equation 11), up to a universal constant. The exact minimizer—without this constant—depends on the worker times $\\tau_i$. However, the resulting time complexity differs only by a constant factor.\n\nConsider an optimization problem with varying worker times $\\tau_i$. Let’s examine two extreme cases:  \n- $\\tau_i = \\infty$ for all $i > 1$ and $\\tau_1 = \\tau > 0$ (only one active worker) – The optimal choice here is simply $R = 1$.  \n- All $\\tau_i$ are equal – The optimal $R$ in this case is potentially larger than $1$.  \n\nWhile the optimal $R$ varies across these scenarios, the final time complexities remain within a constant factor of each other.  \n\nThis property is, in fact, quite powerful: as you pointed out, the same value of $R$ can be used across different data centers, leading to, at most a constant-factor difference in performance. We appreciate this observation and will clarify it further in the camera-ready version of the paper.\n\n> Only one very simple problem, a simulated convex problem, is used in experiment. Furthermore, only one specific value of R is evaluated. More experiments with more complex models and real datasets, under different settings of R, are needed to validate the efficiency of Ringmaster ASGD.\n\nThe primary goal of this paper is to establish the **theoretical optimality** of Asynchronous SGD. Our work addresses a fundamental open problem in optimization, providing the first proof of **optimal time complexity** for asynchronous SGD. We firmly believe that developing an optimal Asynchronous SGD method is essential for the ICML community. This work represents a significant step in that direction, offering theoretical guarantees that pave the way for future practical advancements.", "claims_and_evidence": "The claims are partially supported by evidence. Please see details below.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the problem.", "theoretical_claims": "As shown in Theorem 4.2 and Theorem 5.1, the value of the delay threshold does not depend on the computation times. Does this imply that the same value of R can be used across different distributed systems? This conclusion is somewhat confusing and counter-intuitive. It seems that the optimal value of R should be related to the computing capability of the workers in the cluster.", "experimental_designs_or_analyses": "Only one very simple problem, a simulated convex problem, is used in experiment. Furthermore, only one specific value of R is evaluated. More experiments with more complex models and real datasets, under different settings of R, are needed to validate the efficiency of Ringmaster ASGD.", "relation_to_broader_scientific_literature": "The key contributions of the paper are related to federated learning.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Algorithm 5 is a modification of Algorithm 4 that stops irrelevant computations. The update rules of these two algorithms are equivalent. Hence, the statement from line 319 to line 328 is sufficient, and the details of Algorithm 5 can be moved to the appendix for simplicity.", "other_comments_or_suggestions": "No.", "questions_for_authors": "Please refer to the above issues.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GcevqE0YUi", "reviewer": "Reviewer_kbLE", "summary": "This paper discusses the characteristics of asynchronous parallel algorithms when a delay upper bound is provided, specifically Algorithm 4 and Algorithm 5. Asynchronous parallel SGD was the focus of SGD research from 2014 to 2020. With the popularity of the Adam algorithm, research on SGD has begun to decline. This paper offers rigorous proofs for Algorithm 4 and Algorithm 5, and simple experiments are provided in the appendix.\n\nI believe the biggest issue with this paper is that it merely adds a delay constraint on top of Algorithm 3 without altering any of its other mathematical properties. Providing such an analysis requires only minor modifications to the analysis of Algorithm 3. Therefore, the paper should have extensively discussed the shortcomings of Algorithm 3, particularly in Section 2.2. However, the content in Section 2.2 does not convince me that Algorithm 3 has significant flaws. Furthermore, the analysis of Algorithm 3 itself, such as that of the Hogwild! algorithm, already includes discussions on maximum delay. Consequently, I find the contribution of this paper to be insufficient.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\n> Asynchronous parallel SGD was the focus of SGD research from 2014 to 2020. With the popularity of the Adam algorithm, research on SGD has begun to decline.\n\nWe respectfully disagree with this statement. One of the important works [1] in stochastic optimization (a field that includes both SGD and Adam) was published only in 2023 (preprint in 2019). [1] proves that SGD is an optimal method in the nonconvex stochastic setting, meaning that, theoretically, Adam cannot be better than SGD. At the same time, we agree that Adam is a very important method that requires further investigation, but it is based on SGD. Without understanding SGD, it would be much more difficult to understand Adam.\n\n> I believe the biggest issue with this paper is that it merely adds a delay constraint on top of Algorithm 3 without altering any of its other mathematical properties. \n\nAdding this delay constraint in Alg. 4 is a non-trivial and elegant fix for the original Async SGD. Surprisingly, this simple yet essential algorithmic improvement was previously overlooked.\n\n> Furthermore, the analysis of Algorithm 3 itself, such as that of the Hogwild! algorithm, already includes discussions on maximum delay  .. The main conclusions of this paper are closely related to the analysis of Algorithm 3. Based on the analysis of Algorithm 3, such as the Hogwild! algorithm analysis, I believe that the analysis presented in this paper is quite straightforward ... \n\nNote that the analysis of Async SGD in the Hogwild! paper is not the tightest previous result. [2,3] establish a better rate. We further improve it to the optimal time complexity, which is unimprovable due to the lower bounds.\n\nThe mathematical properties change significantly. Instead of the classical asynchronous SGD, we analyze a new version in which outdated and irrelevant data are ignored. First, we analyze the sum $\\sum_{k=0}^K \\mathbb{E}[|x^k - x^{k-\\delta^k} |^2]$ in Lemma C.2 more carefully and improve upon the analysis in [2,3]. Next, Lemma 4.1, Theorem 4.2, Lemma 5.1, and Theorem 5.1 are entirely new results, which show the optimality of the Async SGD approach for the first time in the literature!\n\n> Providing such an analysis requires only minor modifications to the analysis of Algorithm 3. Therefore, the paper should have extensively discussed the shortcomings of Algorithm 3 ... the content in Section 2.2 does not convince me that Algorithm 3 has significant flaws. \n\nAlgorithm 3 presents at least two key flaws. First, it requires computation times as input and assumes that these times are fixed, an assumption that is clearly unrealistic in practical scenarios. Second, as detailed in Section 2.2, there is another significant flaw: Algorithm 3 is neither robust nor adaptive to adversarial computation environments.\n\n> This paper does indeed present two asynchronous parallel algorithms and provides relatively complete proofs and very simple experiments for these algorithms. However, from an experimental perspective, it is difficult to support the arguments made in this paper.\n\nThe goal of this paper was to prove the theoretical optimality of the Asynchronous SGD approach. This paper closes an important theoretical question from the optimization field. This paper should be read primarily as a theoretical paper.\n\n> In practical industrial scenarios, significant fluctuations in node delays are relatively rare.\n\nThis observation does not always hold; significant fluctuations appear in federated learning. Even when fluctuations are minimal, we still obtain improved and optimal theoretical guarantees (see Table, Thm. 4.2, 5.1).\n\n> Spending additional computational resources to control delay may result in higher performance losses than those caused by the delay itself. \n\nAdditional computations due to control of the delays are negligible compared to stochastic gradient computation times. How can a simple comparison $\\delta^k < R$ of two integers decrease the performance of modern computation systems?\n\n> Hence, from both algorithm design and theoretical analysis perspectives, the value of this paper is quite limited.\n\n**We strongly believe obtaining an optimal Async SGD method is an important task for the ICML community. This is the first paper to demonstrate the optimality of asynchronous SGD in terms of time complexity—a point we believe was overlooked by the reviewer. The corresponding complexity is significantly better than that of previous variants (see Table 1). We believe this work closes an important open problem in asynchronous optimization.**\n\n[1] Arjevani, Y, et al. \"Lower bounds for non-convex stochastic optimization.\" Mathematical Programming 199.1 (2023): 165-214.\n\n[2] Koloskova, A., et al. Sharper convergence guarantees for Asynchronous SGD for distributed\nand federated learning. NeurIPS 2022.\n\n[3] Mishchenko, K., et al. Asynchronous SGD beats minibatch SGD under arbitrary delays. NeurIPS 2022.", "claims_and_evidence": "This paper does indeed present two asynchronous parallel algorithms and provides relatively complete proofs and very simple experiments for these algorithms. However, from an experimental perspective, it is difficult to support the arguments made in this paper.", "methods_and_evaluation_criteria": "From a theoretical perspective, this paper provides a fairly complete proof. From an experimental perspective, it is difficult to support the arguments made in this paper.", "theoretical_claims": "I I have basically reviewed the proof frame approach.", "experimental_designs_or_analyses": "There is almost no experiments in this paper", "relation_to_broader_scientific_literature": "The main conclusions of this paper are closely related to the analysis of Algorithm 3. Based on the analysis of Algorithm 3, such as the Hogwild! algorithm analysis, I believe that the analysis presented in this paper is quite straightforward.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "This paper discusses an asynchronous parallel algorithm with a bounded delay, which essentially adds a delay constraint to Algorithm 3. The proof and analysis of Algorithm 3 are already very well-established, and in these proof,  the requirement for delay in these proofs is based on maximum delay. Therefore, the algorithm and analysis presented in this paper have limited value. \n\nIn practical industrial scenarios, significant fluctuations in node delays are relatively rare. Spending additional computational resources to control delay may result in higher performance losses than those caused by the delay itself. Hence, from both algorithm design and theoretical analysis perspectives, the value of this paper is quite limited.", "other_comments_or_suggestions": "no", "questions_for_authors": "Show more  discussion about  the analysis difference between tradtional ASGD and algorithm 4/5.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qeus54J9QI", "reviewer": "Reviewer_HLwu", "summary": "This paper studied federated learning where each client has a different computation resource. \nThe authors first showed that it is optimal to run Asynchronous SGD on the fastest $m^\\star$ clients. (Theorem 2.1)\nThis naive approach is optimal, but it does not work well when the computation power of each client changes over time.\nThen, the authors proposed Ringmaster ASGD, showing that Ringmaster ASGD can also achieve the optimal convergence rate while it does not require prior knowledge of the computation power of each client.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review.\n\n> This paper studied federated learning where each client has a different computation resource.\n\nOur setup is relevant not only to Federated Learning but also to datacenter environments, where heterogeneous GPU clusters are common. Even in datacenters with identical GPUs, failures become inevitable as the number of GPUs increases, introducing additional heterogeneity. For example, see [0], Section 3.3.4.\n\n[0] Grattafiori, Aaron, et al. \"The llama 3 herd of models.\" arXiv preprint arXiv:2407.21783 (2024).\n\n\n> No experimental results are shown in this paper.\n\nExperiments are presented in Section F of the appendix. We included them there because the primary focus of our paper was to refine the method and establish that it is not only practical but also theoretically optimal. That said, Figures 1 and 2 further demonstrate the practicality of our method, with Figure 2 specifically showing that it outperforms existing benchmarks in speed.\n\n\n> The reviewer feels that the relationship between this paper and existing papers is a bit unclear. Some of the results shown in this paper have been already proposed in the existing papers. Specifically, Theorem 2.1 has been already shown in [1], while the reviewer feels that the authors claimed that these results are also novel results in this paper.\n\nLet us clarify the relationship between [1] and our work. [1] establishes lower bounds for the time complexity of first-order methods, while we propose a fully asynchronous method and derive an upper bound that matches these lower bounds. Additionally, [1] analyzes Rennala SGD, which also attains the lower bound, but the key difference is that Rennala SGD is not fully asynchronous—it operates as Minibatch SGD (which performs synchronous model updates) combined with an asynchronous minibatch collection mechanism. We discuss this distinction in detail in Section 1.2. Our main contribution lies in closing the gap by developing a fully asynchronous method that achieves the lower bound on time complexity.\n\nRegarding Theorem 2.1, it is not explicitly stated in prior work, though it follows as a direct consequence of existing results. The analysis of Asynchronous SGD (Algorithm 1) appears in [2] and [3], while [1] establishes its time complexity. We formally state this in lines 175-183 and then show that Theorem 2.1 naturally follows with a different choice of workers, leading to the optimal time complexity. Notably, this specific choice of workers and its role in achieving optimal time complexity has not been shown in prior work.\n\n[1] Alexander Tyurin, Peter Richtárik, Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model, NeurIPS 2023\n\n[2] Koloskova, A., et al. Sharper convergence guarantees for Asynchronous SGD for distributed and federated learning. NeurIPS 2022.\n\n[3] Mishchenko, K., et al. Asynchronous SGD beats minibatch SGD under arbitrary delays. NeurIPS 2022.\n\n\n> In Sec. 2.2, the authors claimed that \"Naively selecting the fastest workers at the start of the method and keeping this selection unchanged may therefore lead to significant issues in practice\". However, since there is no need to select the same clients over time, the reviewer is wondering if Algorithm 3 really does not work well when the client speeds change over time.\n\nIt is possible to reselect workers each time the $\\tau_i$ values change, but this would introduce additional computational overhead due to the need for continuous selection. Plus, it is not obvious when we should reselect workers. Additionally, a bigger issue is that $\\tau_i$ is typically unknown, making this approach impractical. Instead, we propose a simpler solution using a threshold-based approach, as presented in Algorithms 4 and 5, which does not require $\\tau_i$ and automatically and adaptively chooses the fastest subsets of workers.\n\n\n> The reviewer feels that this paper is claiming Algorithm 3 and Threom 2.1 are novel, while these results have already been shown in [1]. Thus, the main contribution of this paper is Sec. 3. The reviewer would like to suggest that the authors clarify which parts of this paper are novel.\n\nNo, these results are not shown in prior work, as discussed above.\n\n\n> The primary contribution of this paper is theoretical, while the reviewer would like to suggest that the authors verify their results by demonstrating the experimental results.\n\nIndeed, our work is primarily theoretical, as mentioned earlier. However, we provide experimental results in Section F of the appendix.", "claims_and_evidence": "The proposed method and the derived convergence results sound reasonable for the reviewer.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The reviewer did not check the proof, while the claim of this paper sounds reasonable.", "experimental_designs_or_analyses": "No experimental results are shown in this paper.", "relation_to_broader_scientific_literature": "The proposed method, Ringmaster ASGD sounds novel, and it sounds novel that Ringmaster ASGD does not require the prior knowledge of computation powers of each client.", "essential_references_not_discussed": "* The reviewer feels that the relationship between this paper and existing papers is a bit unclear. Some of the results shown in this paper have been already proposed in the existing papers. Specifically, Theorem 2.1 has been already shown in [1], while the reviewer feels that the authors claimed that these results are also novel results in this paper.\n\n## Reference\n[1] Alexander Tyurin, Peter Richtárik, Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model, NeurIPS 2023", "other_strengths_and_weaknesses": "See other sections.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "* In Sec. 2.2, the authors claimed that \"Naively selecting the fastest $m^\\star$ workers at the start of the method and keeping this selection unchanged may therefore lead to significant issues in practice\". However, since there is no need to select the same clients over time, the reviewer is wondering if Algorithm 3 really does not work well when the client speeds change over time. \n* The reviewer feels that this paper is claiming Algorithm 3 and Threom 2.1 are novel, while these results have already been shown in [1]. Thus, the main contribution of this paper is Sec. 3. The reviewer would like to suggest that the authors clarify which parts of this paper are novel.\n* The primary contribution of this paper is theoretical, while the reviewer would like to suggest that the authors verify their results by demonstrating the experimental results.\n\n\n## Reference\n[1] Alexander Tyurin, Peter Richtárik, Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model, NeurIPS 2023", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper gives a new complexity analysis of asynchronous SGD, improving upon the previous bounds given in Koloskova et al. The algorithm controls gradient staleness by discarding updates that are stale beyond a threshold R. The bounds provided by the paper match order-wise with lower bounds, thus ensuring that the analysis is tight. Here are some concerns raised by reviewers. The authors addressed these fairly well in the rebuttal prompting some reviewers to increase their scores. 
* There are no experiments in the submitted version of the paper. During the rebuttal, the authors added some simple experiments, however, these could be further improved by considering larger neural networks and real-world datasets.
* Since the techniques are similar to Koloskova et al, there are some concerns about novelty.
* While the theoretical contribution of this work is solid, the practical value might be limited since most industry implementations are moving back to synchronous SGD. Asynchronous SGD could be of value in edge ML settings.
Decision: Accept (poster)