Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity
Authors: Arto Maranjyan
Peter Richtárik
Venue: ICLR 2026 Poster (2026)
Keywords: asynchronous SGD
data heterogeneity
optimal time complexity
nonconvex optimization
parallel methods
stochastic optimization
Primary area: optimization
TL;DR: We show that asynchronous SGD can be provably optimal under heterogeneous data by buffering gradients and updating the model at the right time.

Abstract: Asynchronous stochastic gradient methods are central to scalable distributed optimization, particularly when devices differ in computational capabilities. Such settings arise naturally in federated learning, where training takes place on smartphones and other heterogeneous edge devices. In addition to varying computation speeds, these devices often hold data from different distributions. However, existing asynchronous SGD methods struggle in such heterogeneous settings and face two key limitations. First, many rely on unrealistic assumptions of similarity across workers' data distributions. Second, methods that relax this assumption still fail to achieve theoretically optimal performance under heterogeneous computation times. We introduce Ringleader ASGD, the first asynchronous SGD algorithm that attains the theoretical lower bounds for parallel first-order stochastic methods in the smooth nonconvex regime, thereby achieving optimal time complexity under data heterogeneity and without restrictive similarity assumptions. Our analysis further establishes that Ringleader ASGD remains optimal under arbitrary and even time-varying worker computation speeds, closing a fundamental gap in the theory of asynchronous optimization.

Published as a conference paper at ICLR 2026
RINGLEADER ASGD: THE FIRST ASYNCHRONOUS SGD WITH OPTIMAL TIME COMPLEXITY UNDER DATA HETEROGENEITY
Artavazd Maranjyan, Peter Richtárik King Abdullah University of Science and Technology (KAUST) farto. maranjjan, richtarik]@@mme com
ABSTRACT
Asynchronous stochastic gradient methods are central to scalable distributed op- timization, particularly when devices differ in computational capabilities. Such settings arise naturally in federated learning, where training takes place smart- phones and other heterogeneous edge devices. addition to varying computation speeds, these devices often hold data from different distributions. However, isting asynchronous SGD methods struggle in such heterogeneous settings and face two key limitations. First, many rely on unrealistic assumptions of similarity across workers' data distributions. Second, methods that relax this assumption still fail achieve theoretically optimal performance under heterogeneous com- putation times. We introduce Ringleader ASGD, the first asynchronous SGD al- gorithm that attains the theoretical lower bounds for parallel first-order stochastic methods in the smooth nonconvex regime, thereby achieving optimal time com- plexity under data heterogeneity and without restrictive similarity assumptions. Our analysis further establishes that Ringleader ASGD remains optimal under ar- bitrary and even time-varying worker computation speeds, closing a fundamental gap in the theory of asynchronous optimization.
INTRODUCTION
Modern machine learning increasingly depends on large-scale distributed training across clusters with hundreds or even thousands of GPUs (Shoeybi et al., 2019; Brown et al., 2020; Narayanan et al., 2021). However, classical synchronous training methods struggle to scale, as device failures, network instabilities, and synchronization overheads introduce inefficiencies (Chen et al., 2016; Grattafiori et al., 2024). These issues become even more pronounced in environments with hetero- geneous computational power, such as Federated Learning (FL), where devices range from high-end datacenter GPUs to resource-constrained edge hardware (Konečný et al., 2016; McMahan et al., 2016; Li et al., 2020; Kairouz et al., 2021). Because synchronous methods bottlenecked by the slowest participants, faster devices remain idle, leading to underutilization of resources when stragglers- slowed by computation or communication--ag significantly behind.
One way to reduce synchronization bottlenecks is to equip data centers with homogeneous GPUs. However, this approach expensive and difficult scale: upgrading to faster GPUs requires re- placing all devices simultaneously, since heterogeneous hardware cannot be combined efficiently. Even then, homogeneity does not eliminate synchronization issues, as hardware failures and de- vice dropouts still cause stragglers and idle time. Moreover, this solution applies only to controlled datacenter environments and is infeasible FI., where edge devices are outside the server's control.
A more promising approach is to shift from hardware to algorithmic solutions using asynchronous optimization methods. These methods remove the need for synchronization, allowing fast workers to contribute without waiting for slower ones (Tsitsiklis et al., 1986; Recht et al., 2011; Agarwal & Duchi, 2011; Dean et al., 2012; Li et al., 2014). Despite their appeal, asynchronous methods are harder to analyze. In particular, meaningful analysis would require studying time convergence, rather than iteration complexity only. Iteration count alone does not reflect training speed in parallel settings: method with iterations may still finish faster if those steps avoid waiting for slow

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of time complexities for parallel first-order methods under the fixed computa- tion time model, where worker i needs Ti seconds to compute stochastic gradient, with the times ordered so that Tn is the largest (2). We denote by Tavg == Σi=1 Ti the average computation time. Problem parameters include the initial function suboptimality A == f==xx= -ff target stationarity e, the variance bound of the stochastic gradients a² (Assumption 1), and smooth- ness constants. Specifically, Ly is the smoothness constant of f (3); Lmax == maXie[a] L, with L1, the smoothness constant of fi: and L is constant associated with our new smoothness-type assumption (Assumption 2). They satisfy L S L S Lumax (Lemma 1) All stated time complexi- ties hide universal constant factors. Each column indicates whether method satisfies the following desirable properties: Optimal: achieves the theoretical lower bound derived by Tyurin & Richtárik (2024) for parallel first-order stochastic methods in heterogeneous data setting. No sync.: does not require synchronization and is therefore asynchromous. No idle workers: all workers remain busy without waiting, so computational resources are fully utilized. No discarded work: no computation is wasted, and no worker is stopped mid- nid-computation.
I" (Assumption 3) the
Method
Time Complexity
Optimal
sync.
No idle workers
No discarded work
Naive Minibatch SGD (Section 3)
4 To
+ Iu sur
x
x
IA'SGD (Wang al., 2025)
A (Tn
In
x
V
(Appendix H)
Malenia SGD
Tr + Tave ad
(Tyurin & Richtárik, 2024)
Ringleader ASGD (new)
(T + Tave
(Algorithm I; Theorem 5.3)
Lower Bound
L
(Tyurin & Richtárik, 2024)
+ Tave
(1) The analysis of Wang et (2025) assumes that f, share the same smoothness constant, i.c., cach f. L,, -smooth and bound Immax is used for all. This assumption is unnccssary: under our Assumption 2. the constant improves to while the analysis remains unchangod. (9) The time complexities Ringleader ASGD and Malenia SGD differ in the smoothhess constant only. Since Malenia SGD is optinal. Ringleader ASGD also optimal whenever I. exceeds F,y most universal constant factor, that I. = (ll,)).
workers. This raises a fundamental question: among all parallel methods, which ones are provably fastest in theory? To make this precise, we restrict our attention to smooth nonconvex problems and to stochastic first-order methods, encompassing algorithms with or without synchronization.
Recently, Tyurin & Richtárik (2024) studied this regime, where they derived lower bounds. They then proposed two algorithms: Rennala SGD, designed for the homogeneous data setting, where all workers draw samples from the same distribution, and Malenia SGD, for the heterogeneous data ser- ting, where data distributions differ across workers. They showed that both methods are optimal- achieving the lower bounds-and, perhaps surprisingly, both are synchronous (they periodically synchronize workers). The key idea in both is to fully utilize the available computational resources by keeping workers continuously busy: each worker computes independently, and synchronization occurs only after sufficient number of gradient computations have been accumulated.
At first, the result of Tyurin & Richtárik (2024) suggested a rather pessimistic outlook for asyn- chronous methods: despite their practical appeal, they showed that existing asynchronous methods are not optimal and that the method achieving the lower bound is synchronous. This created the view that optimality is inherently tied to synchronization. However, this view was overturned by Maran- iyan et al. (2025d), who, the homogeneous data setting, introduced Ringmaster ASGD-the first asynchronous SGD method to achieve optimal time complexity as the synchronous Rennala SGD. Although both methods share the same theoretical guarantees, Ringmaster ASGD can be faster than Rennala SGD in practice, since it avoids synchronization and benefits from more frequent updates.
Nevertheless, the work of Maranjyan et al. (2025d) established optimality in the homogeneous data setting only. The question of whether some variant of parallel method that does not rely syn- chronization (i.e., is asynchronous) can also be optimal in the more general heterogeneous data setting remained open. In this work, we close this gap and answer the question affirmatively.
The relevance of the heterogeneous data setting is clear in FL, where participants naturally hold distinct datasets (Zhao al., 2018; Li et al., 2020; Tan al., 2022). This setting is more chal-
2

---

Published as a conference paper at ICLR 2026
lenging than the homogeneous one, since the usual asynchronous SGD upplattn after every gradient- can bias training toward fast workers' local data. Most existing methods address this by assuming similarity across client distributions (Mishchenko et al., 2022: Koloskova et al., 2022; Nguyen et al., 2022; Islamov et al., 2024), an assumption that simplifies analysis but is often unrealistic in practice (e.g., hospitals with distinct demographics, mobile users in different regions).
Recent work by Wang et al. (2025) took a step toward removing these restrictive assumptions by proposing Incremental Aggregated Asynchronous SGD (IA" (IA'S method that provably converges without similarity assumptions. However, their method achieves the same time complexity as stan- dard Naive Minibatch SGD (see the first two rows of Table 1)-the the simplest synchronous SGD base- line, which waits to collect one gradient from each worker before every update thus failing to provide the computational advantages that motivate asynchronous approaches the first place.
To the best of our knowledge, the only method proven to be optimal in the heterogeneous data setting the synchronous algorithm Malenia SGD of Tyurin Richtárik (2024), which, notably, does not rely on similarity assumptions. However, synchronization is major bottleneck in practice: although synchronous and asynchronous methods can share the same theoretical complexity, asynchronous methods are often faster in practice because they avoid costly synchronization and benefit from more frequent updates, as demonstrated in the homogeneous case by Maranjyan et al. (2025d).
This raises fundamental question: Is it possible to design asynchronous method that requires no similarity assumptions while still achieving optimal time complexity? In this paper, we answer this question affirmatively by introducing Ringleader ASGD, the first asynchronous SGD method that achieves optimal time complexity the heterogeneous data setting. Importantly, Ringleader ASGD attains this without relying on restrictive similarity assumptions.
1.1 CONTRIBUTIONS
Our main contributions are the following:
Optimal asynchronous SGD under data heterogeneity. We prove that Ringleader ASGD (Algo- rithm 1) is. to the best of our knowledge, the first asynchronous method in the heterogeneous setting under the fixed computation model (2) matching the lower bounds for parallel methods of Tyurin & Richtárik (2024), when the smoothness-type constant T. in Assumption 2 is within a constant factor of the smoothness I,f used to obtain the lower bounds (Table 1). Importantly, Ringleader ASGD attains this without any similarity assumptions across clients' data.
Additional useful propertics. Beyond optimal time complexity, Ringleader ASGD satisfies two additional properties: (i) all workers remain continuously active (no idle workers), and (ii) every computed gradient is used in the update (no discarded work). These properties are crucial in practice, ensuring full resource utilization: all workers contribute at all times, and no computation is wasted. Table 1 compares Ringleader ASGD with benchmark algorithms on these properties.
Parameter-free design. Unlike the optimal synchronous method Malenia SGD (Tyurin & Richtárik, 2024), which requires prior knowledge of the gradient variance bound and target accuracy, our method operates in the fixed computation time model without such parameters (except for the step- size, needed only to match the optimal rate). This makes it more practical for real-world deploy- ments, where these quantities are usually unknown or hard to estimate. The same parameter- improvement can also be applied to Malenia SGD, as we discuss in Appendix I.
Universal computation model. In Appendix we extend our analysis beyond the fixed compu- tation time model to the setting of arbitrarily varying times, accommodating virtually any computa- tional behavior, including stochastic or adversarial patterns, while retaining optimal time complexity.
Empirical validation. In Appendix A, we evaluate Ringleader ASGD on toy problems, confirming the theory and showing clear practical gains over baselines.
'Throughout the paper, we refer to our method as optimal. Formally, this holds whenever the constant L associated with our new smoothness-type assumption (Assumption 2)-is at most constant factor larger than the smoothness constant I,, in the derived lower bounds (Tyurin & Richtárik, 2024). See Table for details.
3

---

Published as a conference paper at ICLR 2026
2
PROBLEM SETUP
We consider a distributed learning setting with n workers, where each worker i possesses its own local data distribution D;. Our goal is to solve the following distributed optimization problem:
- 72
minimize ZER
[(()
(a))
where f((x) = EEEDD [f();;
(1)
Here fi: Rd - R denotes the local objective of worker i, defined as the expectation of the sample loss fa(;;; E,) over data points E, drawn from its local distribution D,,
We first focus on the case where workers have constant computation speeds, as this setting is more intuitive and serves as a foundational model for understanding the dynamics of asynchronous dis- tributed optimization. The extension to arbitrary computation times is presented in Appendix D.
Following the fixed computation model (Mishchenko al., 2022), we formalize:
Each worker i requires seconds to compute one stochastic gradient (I,
Without loss of generality, assume 0 < TI S
S Tn
We assume communication infinitely fast (taking seconds), both from workers to the server and from the server to workers². This is modeling choice choice-arguale arguably the simplest- and has been standard in prior work (Mishchenko et al., 2022; Koloskova al., 2022; Tyurin Richtárik, 2024; Maranjyan et al., 2025d), even if not always stated explicitly. We further discuss the motivation and limitations this abstraction in Appendix C. related study by Tyurin al. (2024b) considers case where communication is non negliggle and proposes techniques address it.
Finally, we denote by Tavg == 1 Σ.= Ts the average computation time across all workers.
2.1 NOTATIONS
We denote the standard inner product in Rd by
(v, v)
rilk
and the corresponding Fuclidean norm by ||^||| = / (ar x). We use [n] = 21,2, ..,,....,]
n) ) denote the index set, and E [-] for mathematical expectation. For functions o, Z + R. write (1²) if there exists a constant C' such that d(2) s Cri(z) for all = Z.
2.2 ASSUMPTIONS
We consider the following standard assumptions for the nonconvex setting. Assumption 1. For each i [n] and every ć, the function f((x; {) is differentiable with respect to its first argument x. Moreover, the stochastic gradients unbiased and have bounded variance 2 2 0, that is,
BE,ND, [[(((;))) = Vs((z), Vo YRR. Vi [m],
EEND [V]();; - v=(())] so? E Vi E [m]]
Assumption 2. Each function fi is differentiable. There exists a constant L. > 0 such that, for all R.d and yI...., Un E Rdd
vx(x) 1 n Σ (())))
2
1 vall?
"One could alternatively assume that each worker requires al most т. seconds. Under this formulation, all of upper bounds would still hold; however, the lower bound would no longer be valid. For this reason, adopt the assumption that each worker requires exactly 7; seconds.
Alternatively, one could define as the time required for worker to both compute gradient and commu- nicate it to the server, while keeping server-to-worfe worker communication infinitely fast. Our upper bounds would still hold under this formulation, but the lower bounds would longer apply,
the simpler model.

---

Published as a conference paper at ICLR 2026
Recall that differentiable function Φ: R IR is called Lg smooth if
[Vo(z) - vo(y)) 4 || ull, Væ,y R2
(3)
By convention, La denotes the smallest such constant.
Note that Assumption stronger than requiring f itself to be syyomooth, yet weaker than all fi being -smothh. The constants satisfy the following relation (Lemmaa E.1)
b S S
max L,, Imax
EE(n]
To the best of our knowledge, prior work on asynchronous SGD under data heterogeneity has always assumed smoothness of each ft (Koloskova al., 2022; Nguyen al., 2022; Wang et al., 2025). Assumption 3. There exists f* > f(x") - f*, where xº is the starting point of the optimization methods.
such that f(x) > f for all E R. We define A
We seek an e-stationary point-a (possibly random) vector x satisfying E| [] S..
3 BACKGROUND AND MOTIVATION
In this section, we review relevant existing methods in distributed optimization and discuss their limitations to motivate algorithmic design.
Naive Minibatch SGD. This algorithm is the most straightforward way to solve (1) in a distributed setting. each iteration the server waits for one gradient from every worker and updates
k
V (x"iet)
This guarantees an unbiased minibatch gradient but synchrony makes inefficient: the iteration time set by the slowest worker, Tn max; (2), fast workers idle while waiting for stragglers.
Malenia SGD. The algorithm (Tyurin & Richtárik, 2024) addresses straggler problem by keeping all workers active: each computes gradients x* while the server accumulates them until
max
(4)
ne
where by is the number of gradients received from worker i. Once this holds, the update
b
8+1
x -7
V
(
cki
performed and broadcast synchronously. This achieves the optimal time complexity, but requires knowledge of a and and discards ongoing computations during synchronization.
Toward Asynchronous Methods. immediately upon receiving a gradient:
naive way to make optimization asynchronous update
k+1 = = V. (2 E :5x
where * denotes the worker that sent the gradient at iteration k. and 8 > 0 is its delay, i.e., the number of server updates that occurred while the gradient was being computed. Delays arise naturally: fast workers return gradients quickly, while slow ones compute stale iterates.
This scheme biased under heterogeneous data. Fast workers dominate updates, pulling the model toward their local minima, while slow workers contribute too rarely, so iterates may oscillate or

---

Published as a conference paper at ICLR 2026
stagnate. Such bias also blocks classical SGD-style proofs, which rely one-step progress toward minimizing the global function, but here each update reflects a different local objective. Without data similarity assumptions (Mishchenko et al., 2022; Koloskova et al., 2022; Nguyen et al., 2022; Islamov et al., 2024), it is harder to extend the analysis to the global function-yet such assumptions rarely realistic when data can be arbitrarily heterogeneous across machines or organizations.
The root issue is that each update uses only one worker's gradient. A better approach is to aggregate information from all workers, even if some gradients are stale, in Incremental Aggregated Gradi- ent (IAG) (Blatt et al., 2007; Gurbuzbalaban et al., 2017; Vanli et al., 2018) or Stochastic Averaged Gradient (SAG) (Roux al., 2012; Schmidt et al., 2017).
This method (Wang al., 2025) constructs updates using information from all workers by maintaining a gradient table on the server, similar to SAG or IAG but with asynchronous table updates. The table is initialized with one stochastic gradient from each worker x after which the server updates
IA
Σ 91
79,
9 =
where 9: is the most recent stochastic gradient in the table from worker i (possibly evaluated at stale iterate =²=4)). ). Each arrival replaces the corresponding entry and triggers an update, so every step uses the latest information from all workers while avoiding global synchronization.
The iteration complexity of the algorithm was established by Wang et al. (2025); converting the fixed computation time model (see Appendix H) yields the same time complexity as Naive Minibatch SGD (Table 1). Thus, asynchronous execution alone does not yield speedups.
Motivation.
The main limitation of asynchronous algorithms is gradient delay, which can severely harm convergence by pushing steps along suboptimal trajectories. This issue arises even in homoge- neous settings (f, = f). The state-of-the-ee solution, Ringmaster ASGD (Maranjyan et al., 2025d), achieves optimal time by discarding overly delayed gradients.
In heterogeneous settings, however, this strategy fails. Slow workers inevitably suffer large delays; if their gradients discarded, their table entries remain outdated and may never refresh, creating persistent information bottleneck that harms convergence. One option is to drop some updates from fast workers to balance delays, but this contradicts the core principle of asynchronous methods, where all workers compute continuously.
Instead, our approach buffers gradients from fast workers rather than applying them immediately. By updating only once enough gradients are collected, we control delays while keeping all workers active. Buffering also offers second benefit: aggregating multiple gradients from the same iterate reduces variance, further improving convergence.
4 RINGLEADER ASGD
Ringleader ASGD (Algorithm 1) builds on three key insights from prior work. First, inspired by IA'SGD, we maintain a gradient table to ensure information from all workers is incorporated into every update, eliminating the need for data similarity assumptions between workers. Second, follow- ing Ringmaster ASGD, we control gradient delays for efficient asynchronous optimization. Third, drawing from Malenia SGD, we buffer rather than discard delayed ones to control delays while preserving valuable computations, enabling continuous utilization of all resources.
important property of the algorithm is that all workers remain continuously active. Each worker sends a gradient to the server immediately after computing it. with communication assumed instan- tancous (Section 2). On receipt, the server either buffers the gradient-in which case the worker simply continues computing and sending new ones applies it to update the model. If an update occurs, the new model is instantly returned to the worker, which resumes at the new point. Thus, workers never idle.
The algorithm proceeds in rounds of exactly n model updates-aat one per worker. When a worker sends stochastic gradient, the server may apply update and return the updated model to that

---

Published as a conference paper at ICLR 2026
Algorithm 1 Ringleader ASGD (server algorithm)
1: Input: Stepsize y > initial point x² IR
2: Initialization: Broadcast æ to all workers, which then start running Algorithm 2 in parallel
3: Set & = 0, 5 0; initialize G, = 0, b, = for all E [n]
4: while True do
5: Phase 1: await stochastic gradients from all workers
6: while S * [n] do
Receive stochastic gradient of (computed at ~ー~5)) from some worker j E [xx]
7:
8:
G, CG=G, oÿ; by bj + 1; S = su
9:
end while
10:
Phase 2: perform exactly update for every worker
11:
akt1 = x² 7 Ei= Gifb.
o Update using averaged gradients from all workers o Last worker to complete Phase 1
12:
Broadcast x k+1 to worker
&o k 1; S= {i}
14:
gt 0, bt 0 for all i [n]; S while # 9 do
Initialize temporary buffer for the next round
15:
Receive stochastic gradient of (computed x² ===²)) from some worker j [1]] j E then
16:
17:
18:
G3 = Gj o5: by by +1 k+1 x² - - b;= G1/b, Broadcast kk+ to worker
19:
20:
21:
k 1; 5= 5 (s}
22:
else
23:
G Gj + gh: 0j = bう +1 S = St U
Buffer for next round
24:
end if
25:
end while
26: G, = G ; = bu for all E [n]; == S+
Transfer buffered gradients to main table
27: end while
Algorithm Worker i's subroutine
1: Input: Model
2: while True do
3: Compute gi ()((; using freshly sampled data point & D.
4: Send to the server
5: end while
worker, but ensures that each worker receives an updated model at most once per round. Repeating this times guarantees every worker obtains exactly one new model per round, which keeps delays bounded. To avoid discarding computations from fast workers, their extra gradients are buffered and applied later at the appropriate time, ensuring each round still consists of exactly updates.
Each round has two phases: first, stochastic gradients are buffered until at least one from every worker is available; then exactly updates are performed (one per worker), after which the old gradients are discarded and the next round begins.
4.1 DETAILED DESCRIPTION
Initialization. The server broadcasts x Rd to all workers, which then start the worker subrou- tine (Algorithm 2). Each worker continuously computes stochastic gradients and sends them the server; if not updated, it simply continues, so workers are never idle.
The server maintains gradient table {(,,, b,)) initialized with G, 0 and 0. Here G, stores accumulated gradients and b, counts how many have been received from worker We also initialize S @ track which entries have at least one gradient.

---

Published as a conference paper at ICLR 2026
Phase 1 - Gradient Collection. In this phase, the server receives stochastic gradients from work- ers and stores them in the table {(G,, b,) b-));=1- Let 9 be the gradient sent by worker ý at iteration k. computed at =*=6 with E ~ Dj. The delays of are not needed to run the algorithm-the will only appear later in the analysis and can be inferred the gap between the current iterate and the one used to compute 9/-
Upon receiving of from worker j (Line 7), the server updates the corresponding table entry and the stochastic gradient counter as follows (Line 8)
G, G 9" b SU
This process continues until S [n]. i.e., the server has collected least one gradient from every worker. No model updates are performed during this phase, and workers do not receive new points; hence, all stochastic gradients from given worker are computed at the same point.
Sequential Updates. In this phase, the server performs exactly one model update for each worker i, for total of n updates. Phase 2 starts with the last worker that completed Phase 1, i.e., the worker whose gradient made the table complete. The server first computes an update by averaging the accumulated stochastic gradients in the table {(G,, b:) and taking a descent step with this estimate (Line 11). The updated model is then sent this worker (Line 12), the worker removed from the set S, and the iteration counter is incremented (Line 13).
Phase 2
Next, the server must update the remaining n workers. These updates are performed sequentially as soon as each worker finishes its current computation. During this waiting period, new gradients may arrive from workers not in S-e.g. for example, the last updated worker may send another stochastic gradient before the other workers complete their computation. Since discarding these gradients would waste information, they are instead buffered for the next round.
e.g.
Temporary Table Management. To achieve this, the server maintains temporary table {(G .b," b, initialized to zero (Line 14). together with set S that records which workers have contributed to the table. Whenever gradient arrives from worker not in S, it stored in the temporary table (Line 23).
instead the gradient comes from j E S. the server updates the main table {(G,, b;)], (Line 18), performs a model update using its averages (Line 19), broadcasts the new model to worker (Line 20), increments the iteration counter, and removes j from S (Line 21).
Preparing for the Next Round. Once all workers in have been updated and Phase ends (S = 0), the server copies the temporary table {GT b] into the main table {G,,, b, } (Line 26) and resets 5 = S+, since these workers already contributed gradients at their updated models. Entries for workers not in S+ remain zero, as the temporary table was initialized with zeros at the start of Phase 2 (Line 14). The server then returns to Phase to begin the next gradient collection round.
The two-phase structure of Ringleader ASGD prevents the unbounded delays of standard asyn- chronous methods. The precise bound on delays is given in the following lemma
Lemma 4.1 (Bounded Delay; Proof in Appendix E.2). In Ringleader ASGD (Algorithm 1), the delays 8t satisfy 8t < 2 for any worker i [n] and any iteration k 2 0.
4.2 COMPARISON TO IA SGD AND MALENIA SGD
IADGD. Our method is delay-controlled version of SAGD We can recover IAR by remov- upon gradient arrival. In
ing Phase 1 and Phase 2, and thus perform updates contrast, our algorithm operates in structured rounds, performing exactly one update per worker in each round, which provides the crucial delay control that SA lacks.
In SAD delays for slow workers can grow unboundedly because the server continuously updates the model using gradients from fast workers, causing slow workers to fall increasingly behind. Our method prevents this issue by buffering gradients from fast workers rather than immediately applying these gradients, ensuring that all workers receive updated models within n subsequent iterations.
8

---

Published as a conference paper at ICLR 2026
Malenia SGD. Malenia SGD also operates in two phases. In Phase 1, it collects gradients much like our approach, but with a termination condition (4) that requires knowing the noise parameter and target stationarity making it impractical. In Phase 2, it performs synchronous update by averaging all collected gradients and broadcasting the new model to all workers, discarding ongoing method performs Phase 2 asynchronously, updating
computations in the process. In contrast, workers sequentially as they finish so that no work is wasted.
Regarding Malenia SGD's termination condition (4), in Appendix I demonstrate that this con- dition can be replaced with our simpler requirement of obtaining at least one gradient from every worker. With this modification, Malenia SGD remains optimal in the fixed-time regime (2) while becoming parameter- parameter-free variant, the only difference between Malenia SGD and Ringleader ASGD lies in Phase 2: we perform updates asynchronously without discarding gradients, while Malenia SGD operates synchronously.
which eliminates the need for prior knowledge of and e. Under this
THEORETICAL RESULTS
Before presenting the theoretical results, first write the algorithm in compact form. The gradi- ents for each worker in the table are all computed at the same point; for worker at iteration k, the point is x 8/ The update rule can be written compactly as
x ++ = x 70"
where the gradient estimator gh is defined by
g Σ
9; RJ
Aj Since multiple gradients may be received from the same worker, denote by gi the j-th gradient from worker i at iteration k. Here the index j corresponds to the i.i.d. sampled data point, and more concretely
9, k-j Vi.
The quantity by denotes the number of gradients from worker i stored in the table at iteration k, i.e., the value of b, in Lines 11 and 19. Thus, (bf 8,) fully determine the method's behavior.
Note that the sequence {b") depends only on the computation times {π;} and the algorithm design (i.e.. the stopping rule for collecting gradients). Once these are fixed, all b for every i [m]] and it- eration & determined. Crucially, the values b/ do not depend the method's hyperparameters y, x or on the variance parameter or the stationarity level c.
Iteration Complexity. sizes across rounds
We begin by establishing notation for the harmonic means of the batch
B² = 1-1- -
and B= inf B k20
Note that B > 1, since by the algorithm's design each by 2 A sharper bound on B will be established later in Lemma 5.2. We obtain the iteration complexity from this theorem.
Theorem 5.1 (Iteration Complexity; Proof in Appendix F). Under Assumptions 1, 2, and 3, let the stepsize in Ringleader ASGD (Algorithm 1) be
1 eB 8nL 10Lo²
? min
Then,
K
|1 SE,
K
k=0
for
L2
4
nLA (1
o² Bne
2
O
B

---

Published as a conference paper at ICLR 2026
For parallel and asynchronous methods, iteration complexity is less important than time complexity. What truly matters is how quickly we can finish training. We are willing to perform more iterations and extra computation if it means completing the process faster. Having established the iteration complexity, we now turn to the time complexity.
Time Complexity. Since the algorithm operates in rounds with steps per round, and its iteration complexity is already known, it remains to determine the duration of each round. We have the following lemma
Lemma 5.2 (Proof in Appendix G.I), Each block of n consecutive iterations (each round) of Algo- rithm I takes at most 2Tn seconds. Moreover, have
Tn 2
Tn
B2
2Tavg
Based on this lemma, we derive the time complexity guarantee our algorithm
Theorem 5.3 (Proof in Appendix G). Let the assumptions and parameter choices of Theorem 5.1 hold. Then, under the fixed computation model (2), Ringleader ASGD achieves the optimal time complexity
LA O
+ Tavg
The obtained time complexity consists of two key terms that illuminate the algorithm's behavior: The first term depends on the slowest device. which is fundamental since all devices must contribute solving the problem. The second term, however, involves Tavg rather than Tn as in Naive Minibatch SGD (see Table 1) -hthis substitution captures the core benefit of asynchronous execution. Specif- ically, this advantage becomes pronounced when is relatively large. Intuitively. in high-noise regimes, collecting many gradients from workers is essential for convergence, and asynchronous methods can leverage faster workers more effectively. Conversely, in low-noise settings, fewer gra- dient evaluations suffice for good performance, making Naive Minibatch SGD already quite effective and rendering the additional complexity of asynchrony unnecessary.
Remark 5.4. The optimality claim for Theorem 5.3 holds when the smoothness-type constant L in Assumption 2 is within a constant factor of the smoothness L, used to derive the lower bound (Tyurin & Richtárik, 2024) (Table 1).
Under this condition, the resulting time complexity matches the lower bound of Tyurin Richtárik (2024), making Ringleader ASGD the first asynchronous algorithm to achieve optimality under het- erogeneous data.
CONCLUSION
We have introduced Ringleader ASGD, the first asynchronous stochastic gradient method achieve optimal time complexity under arbitrary data heterogeneity and arbitrarily heterogeneous com- putation times in distributed learning, without requiring similarity assumptions between workers' datasets.
Its core innovation is two-phase structure within each round: the model is updated once per worker (for a total of n updates), while a buffering mechanism manages gradient delays and preserves the efficiency of asynchronous execution. By maintaining gradient table and alternating between gra- dient collection and sequential updates, Ringleader ASGD prevents the unbounded delays common in naive asynchronous methods. Every gradient received by the server is either used in the current round or stored for future use, ensuring computation is wasted.
Our analysis shows that Ringleader ASGD matches the optimal time complexity bounds established by Tyurin & Richtárik (2024). In contrast the optimal but synchronous Malenia SGD method, Ringleader ASGD is asynchronous and requires no prior knowledge of problem parameters in the algorithm design, making it practical for real-world deployments.
Finally, with minor modification, Ringleader ASGD also achieves optimality in the more general setting of arbitrarily varying computation times (Appendix D).
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
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) CRG Grant ORFS- CRGI2-2024-6460, and iii) Center of Excellence for Generative AI, under award number 5940.
REFERENCES
Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. Advances in Neural Information Processing Systems, 24, 2011.
Abdelkrim Alahyane, Céline Comte, Matthicu Jonckheere, and Éric Moulines. Optimizing asyn- chronous federated learning: A delicate trade-off between model-parameter staleness and update frequency. arXiv preprint arXiv:2502.08200 2025.
Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic gra- dient descent with delayed updates. In Algorithmic Learning Theory, pp. 111-132. PMLR, 2020.
Mahmoud Assran, Arda Aytekin, Hamid Reza Feyzmahdavian, Mikael Johansson, and Michael G Rabbat. Advances in asynchronous parallel and distributed optimization. Proceedings of the IEEE, 108(1 1):2033-2031, 2020.
Doron Blatt, Alfred O Hero, and Hillel Gauchman. A convergent incremental gradient method with a constant step size. SIAM Journal on Optimization, 18(1):29-51, 2007.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert-Voss Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Ma- teusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Asso- ciates, Inc., 2020. URL. https: /ttp:::://///eeee/e wggerooeeeddiin.....o.oo.. neurips aappscc//apppee cct.paapr//222//111111 pdf.
1457c0d6bfcb4966 22t (ttpbBaaac44244a-Paaaaaaa
Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. Revisiting dis- tributed synchronous SGD. arXiv preprint 10400:160..00981, 2016.
Alon Cohen, Amit Daniely, Yoel Drori, Tomer Koren, and Mariano Schain. Asynchronous stochastic optimization robust to arbitrary delays. Advances in Neural Information Processing Systems, 34: 9035, 2021.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' au- relio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, Quoe Le, and Andrew Ng. Large scale distributed deep networks. In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 25, Curran Associates, Inc., 2012. URL https: https:// http://///coccccceeeeecsoceo wnw.eeeeeeeeeneee.neeeeeeeeeeeee ce cc/paper fi files/paper/2012: file/ /ttp////000661111002215116000..0
pdf.
Sanghamitra Dutta, Gauri Joshi, Soumyadip Ghosh, Parijat Dube, and Priya Nagpurkar. Slow and stale gradients can win the race: Enror-runtime trade-offs in distributed SGD. In International Conference Artificial Intelligence and Statistics, pp. 812- PMLR, 2018.
Hamid Reza Feyzmahdavian and Mikael Johansson. Asynchronous iterations in optimization: New sequence results and sharper algorithmic guarantees. Journal of Machine Learning Research, 24 1158):1-75, 2023.
Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. An asynchronous mini-batch algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, (12):3740-3754, 2016.

---

Published as a conference paper at ICLR 2026
Yann Fraboni, Richard Vidal, Lactitia Kameni, and Marco Lorenzi. A general theory for federated optimization with asynchronous and heterogeneous clients updates. Journal of Machine Learning Research, 24(1 10):1-43, 2023.
Margalit R Glasgow and Mary Wootters. Asynchronous distributed optimization with stochastic de- lays. In International Conference on Artificial Intelligence and Statistics, pp. 9247-9279. PML.. 2022.
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.c 1783, 2024.
Mert Gurbuzbalaban, Asuman Ozdaglar, and Pablo A Parrilo. On the convergence rate of incremen- tal aggregated gradient algorithms. SIAM Joumal on Optimization, 27(2): 2017.
Rustem Islamov, Mher Safaryan, and Dan Alistarh. AsGrad: A sharp unified analysis of asynchronous-SGD algorithms. In International Conference on Artificial Intelligence and Statis- tics, pp. 649-657. PMLR, 2024.
Sashank J Reddi, Ahmed Hefny,, Suvrit Sra, Barnabas Poczos, and Alexander J Smola. On vari- ance reduction in stochastic gradient descent and its asynchronous variants. Advances in Neural Information Processing Systems, 28, 2015.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1-2):1-200, 2021.
Anastasiia Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. Advances in Neural Information Pro- cessing Systems, 35:17202- 17215, 2022.
Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. In NIPS Workshop Private Multi Multi-Party Machine Learning 2016.
Remi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien Improved asynchronous parallel op- timization analysis for stochastic incremental methods. Journal of Machine Learning Research, 19681):1-68, 2018. URL http::/t///. / //mmr//mr..///////// org/ htppp/pppsss/////// 9 9119/1166660 650 html.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yam.leccum.com wtw.e//www..oo/ee///iiiiiit 2, 2010.
Mu Li, David G Andersen, Alexander Smola, and Kai Yu. Communication efficient distributed machine learning with the parameter server. Advances in Neural Information Processing Systems, 27, 2014.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Sys- lems, 2:429-450 2020.
Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. Advances in Neural Information Processing Systems, 28, 2015.
Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael I Jordan. Perturbed iterate analysis for asynchronous stochastic optimization. SIAM
Journal on Optimization, 27(4):2202-277 2017.
Artavazd Maranjyan, Omar Shaikh Omar, and Peter Richtárik. Mindflayer SGD: Efficient parallel SGD in the presence of heterogeneous and random worker compute times. In The 41st Conference on Uncertainty in Artificial Intelligence, 2025a. URL https: htttps://openzeeieees /ppperevieeeeeeeeooo net forum?
did=NNpuu 3m
12

---

Published as a conference paper at ICLR 2026
Artavazd Maranjyan, El Mehdi Saad, Peter Richtárik, and Francesco Orabona. ATA: Adaptive task allocation for efficient resource management in distributed machine learning. In International Conference on Machine Learning, 2025b.
Artavazd Maranjyan, Mher Safaryan, and Peter Richtárik. GradSkip: cemamuuication-acceleeia local gradient methods with better computational complexity. Transactions on Machine Learn- ing Research, 2025c. ISSN 2835-8856. URL https: /wwp/opppeeew...////// net forum?ide 6R3ERqF Ehn.
Artavazd Maranjyan, Alexander Tyurin, and Peter Richtárik. Ringmaster ASGD: The first Asyn- chronous SGD with optimal time complexity. International Conference on Machine Learning, 2025d.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effcienn learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR, 2017.
H Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas. Federated learning of deep networks using model averaging. arXiv preprint 1rXiv 05669,, 2:2, 2016.
Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake Woodworth. Asynchronous SGD beats minibatch SGD under arbitrary delays. Advances in Neural Information Processing Systems, 35:420-433. 2022.
Deepak Narayanan, Mohammad Shoeybi, Jared Casper, Patrick LeGresley, Mostofa Patwary, Vi- jay Korthikanti, Dmitri Vainbrand, Prethvi Kashinkunti, Julie Bernauer, Bryan Catanzaro, et al. Efficient large-scale language model training on GPU clusters using Megatron-L.M. In Proceed- ings of the International Conference for High Performance Computing, Networking. Storage and Analysis, pp. 1-15, 2021.
Yurii Nesterov. Lectures on Convex Optimization, volume 137. Springer, 2018.
John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Mike Rabbat, Mani Malek, and Dzmitry Huba. Federated learning with buffered asynchronous aggregation. In International Conference Artificial Intelligence and Statistics, pp. 3581-3607. PMLR, 2022.
Lam Nguyen, Phuong Ha Nguyen, Marten Dijk, Peter Richtárik, Katya Scheinberg, and Martin Takác. SGD and Hogwild! convergence without the bounded gradients assumption. Interna- tional Conference on Machine Learning, pp. 3750-3758 PMLR, 2018.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. HOGWILD!: A lock-free ap- proach to parallelizing stochastic gradient descent. Advances in Neural Information Processing Systems, 24, 2011.
Nicolas Roux, Mark Schmidt, and Francis Bach. stochastic gradient method with exponential convergence rate for finite training sets. Advances in Neural Information Processing Systems, 25, 2012.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162:83-112, 2017.
Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-LM: Training billi-billion parameter language models using model par- allelism. arXiv preprint arXiv: 19Xivv/999.000 19999000055. 2019.
Alysa Ziying Tan, Han Yu, Lizhen Cui, and Qiang Yang. Towards personalized federated learning. IEEE Transactions on Neural Networks and Learning Systems, 34(12):9587-6003 2022.
John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Transactions Automatic Control, 31(9): 803-812, 1986.
Alexander Tyurin. Tight time complexities in parallel stochastic optimization with arbitrary compu- tation dynamics. arXiv preprint 2.Xx:2448..04299 2024.
13

---

Published as a conference paper at ICLR 2026
Alexander Tyurin and Peter Richtárik. Optimal time complexities of parallel stochastic optimization methods under a fixed computation model. Advances in Neural Information Processing Systems, 36, 2024.
Alexander Tyurin and Peter Richtárik. On the optimal time complexities in decentralized stochastic asynchronous optimization. Advances in Neural Information Processing Systems, 37, 2024.
Alexander Tyurin, Kaja Gruntkowska, and Peter Richtárik. Freya PAGE: First optimal time com- plexity for large-scale nonconvex finite-sum optimization with heterogeneous asynchronous com- putations. Advances in Neural Information Processing Systems, 37, 2024a.
Alexander Tyurin, Marta Pozzi, Ivan Ilin, and Peter Richtárik. Shadowheart SGD: Distributed asyn- chronous SGD with optimal time complexity under arbitrary computation and communication heterogeneity. Advances in Neural Information Processing Systems, 37, 2024b.
N Denizcan Vanli, Mert Gurbuzbalaban, and Asuman Ozdaglar. Global convergence rate of proxi- mal incremental aggregated gradient methods. SIAM Journal on Optimization, 28(2):1282-13000 2018.
Qiyuan Wang, Qianqian Yang, Shibo He, Zhiguo Shi, and Jiming Chen. AsyncFedED:: Asyn- chronous federated learning with euclidean distance based adaptive weight aggregation. arXiv preprint DxXiv:2205513797 2022a.
Xiaolu Wang, Zijian Li, Shi Jin, and Jum Zhang, Achieving linear speedup in asynchronous federated learning with heterogeneous clients. IEEE Transactions on Mobile Computing, 2024.
Xiaolu Wang. Yuchang Sun, Hoi To Wai, and Jun Zhang. Incremental aggregated asynchronous SGD for arbitrarily heterogeneous data, 2025. URL https: https:://peeneviieeeee http///enneeeeeeeeeeeeeeee net nww.:frumt forum? id=m3x4kDbYAK.
Zhongyu Wang. Zhaoyang Zhang. Yuqing Tian, Qianqian Yang, Hangguan Shan, Wei Wang, and Tony QS Quck. Asynchronous federated learning over wireless communication networks. JEEE Transactions Wireless Communicattinns, 21()):661-66778 2022b.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: novel image dataset for bench- marking machine learning algorithms. arXiv preprint 1wt.iiv:700.07700 2017.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization. arXiv preprint 1rXiv:1903.03934 2019.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. In Kama- lika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Con- ference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 7252-7261. PMLR, 09-15 Jun 2019. URL https: yurochkin19e maaiiinnaa.hi.. html.
bettss:/pproceedie http///popeee...ee/ee mil..press//97
Feilong Zhang. Xianming Liu, Shiyi Lin, Gang Wu, Xiong Zhou, Junjun Jiang, and Xiangyang Ji. No one idles: Efficient heterogeneous federated learning with parallel edge and server computa- tion. In International Conference on Machine Learning, pp. 41399 41413. PMLR, 2023.
Shen-Y Yi Zhao and Wu-Jun Li. Fast asynchronous parallel stochastic gradient descent: A lock- free approach with convergence guarantee. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint 180.008800.08.... 2018.
Shuxin Zheng, Qi Meng. Taifeng Wang, Wei Chen, Nenghai Yu, Zhi-Ming Ma, and Tie- Yan Liu. Asynchronous stochastic gradient descent with delay compensation. In International Conference on Machine Learning, pp. 4120-4129, PMLR, 2017.
Kaiwen Zhou, Fanhua Shang, and James Cheng. A simple stochastic variance reduced algorithm with fast convergence rates. In International Conference on Machine Learning, pp. 3980-5989. PMLR, 2018.
14

---

Published as a conference paper at ICLR 2026
A EXPERIMENTS
To validate our theoretical results we perform a toy simulation.
We consider image classification MNIST (LeCun al., 2010) and on Fashion-MNIST (Xiao et al., 2017) with standard normalization for both datasets. To enable equal client sizes, we first trim the dataset that the total number of examples is divisible by the number of clients
100. To obtain heterogeneous datasets across clients, we then partition the trimmed set using an equal-size Dirichler procedure with concentration parameter a 0.1 (Yurochkin et al., 2019). For each client j [n]. we draw proportions Pj Dirichlet (a, (a..... a) over the classes and compute a rounded class-allocation vector whose entries sum exactly to N/n, where is the trimmed dataset size. This creates non-lll data where each client has skewed distribution over classes (with = 0.1, clients typically observe only 1-2 classes frequently).
When assigning samples, we take the requested number from each class pool for client If class pool does not have enough remaining examples to meet the requested amount, the client receives whatever is left from that class and the shortfall is topped up using samples from other classes that still have available examples.
Our model is two-layer MLP Linear(d, (d, 128) ReLU Linear(1228 10) trained with mean cross- entropy. Stochastic gradients at the clients use a minibatch of size 4, while reported gradient norms computed on the full dataset.
We emulate heterogeneous compute by assigning each client i a base delay and a random jitter:
Tj + [m]. Th N (0, i), for all E [n]
For each method we tune the stepsize within fixed wall-clock budget. We sweep
Y E {0.001, 0.005, 0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1.0, 2.0}.
and then fix the best y per method for evaluation.
We report the full-batch gradient-norm squared [/ versus wall-clock time. Each method run 30 times over different seeds. We report the median with interquartile range (IQR). To reduce fighffrreuency noise, apply centered mhoiing-average smoothing to the aggregated curves (post-aggregation), while keeping the initial point unchanged.
Figure shows the results. We observe that Ringleader ASGD converges faster compared to Malenia SGD and IA2SGD. Although theory suggests that Ringleader ASGD and Malenia SGD have the same time complexity, in practice Ringleader ASGD benefits from the n updates performed in Phase instead of one synchronous update. This design enables more optimization steps within the same wall-clock budget, which is especially advantageous when updates are sparse.
B RELATED WORK
Research asynchronous stochastic gradient methods dates back to the seminal work of Tsitsiklis et al. (1986), and gained renewed momentum with the introduction the HOGWILD! algorithm (Recht et al., 20. HOGWILD! is fundamentally an asynchronous coordinate descent method: up- dates are performed lock-free with inconsistent reads and writes, and its convergence guarantees rely on sparsity assumptions that are rarely realistic in modern large-scale machine learning. Subsequent refinements of this paradigm include works by Reddi et al. (2015); Zhao & Li (2016); Mania et al. (2017); Leblond al. (2018); Nguyen et al. (2018); Zhou et al. (2018), but these works remain tied to the coordinate descent setting with inconsistent memory accesses, and thus differ substantially from our focus.
Closer to our setting are works where updates are based on gradients that are applied consistently. Early contributions, typically under the homogeneous-data assumption (all workers sample from the same distribution), include the work of Agarwal & Duchi (2011), who studied convex objec- tives, as well as later extensions to the non-convex case such as the work of Lian et al. (2015) and Dutta et al. (2018), the latter analyzing exponentially distributed computation times. Other rele- vant results in this line include those of Feyzmahdavian et al. (2016); Zheng et al. (2017); Arjevani et al. (2020); Feyzmahdavian & Johansson (2023), all of which assume fixed delays. More recently,
15

---

Published as a conference paper at ICLR 2026
Ringleader Nalena SGD
Ringleader
Malenia SGD
SGD
IA SCD
1190>/12
2011
197+
21380
11200
12000
Runtime
(a) MNIST
(b) Fashion-MNiS
Figure 1: Convergence comparison showing median gradient norm squared [ (solid lines)
with interquartile ranges (shaded regions) versus wall-clock time, averaged over 30 random seeds.
Setup: Two-layer MLP with architecture Linear(d, 128) + ReLU - Linear(128, 10) trained on (a) MNIST and (b) Fashion-MNIST datasets. Client delays: Heterogeneous delays simulated as T. = |7ss where 7i ~ NO, i) for client é E [nx] where we choose n = 100. Results: With optimally tuned stepsizes, Ringleader ASGD achieves faster convergence than both Malenia SGD and SGD, despite Ringleader ASGD and Malenia SGD having equivalent time complexity guarantees.
delay-adaptive methods have heen proposed, aiming to improve performance by down-weighting very stale gradients (Cohen al., 2021; Koloskova et al., 2022; Mishchenko et al., 2022).
Particularly relevant to our work are asynchronous variants of SAGA. Leblond et al. (2018) devel- oped shared-parameter version in the spirit of HOGWILDI, while Glasgow Wootters (2022) studied distributed setting that employs full gradients, in contrast to our stochastic-gradien per- spective.
large body of recent work investigates asynchronous methods in federated learning (FL., where clients hold data from heterogeneous distributions. Notable contributions include works by Xie et al. (2019); Mishchenko et al. (2022); Koloskova et al. (2022); Wang et al. (2022a;b); Glasgow & Wootters (2022); Fraboni al. (2023); Zhang et (2023); Wang al. (2024); Islamov et al. (2024); Alahyane et al. (2025).
More broadly, Assran et (2020) provide comprehensive survey of asynchronous optimization methods.
There is another line of work that began with Tyurin & Richtárik (2024), who established lower bounds for parallel methods and proposed optimal synchronous algorithms together with an asyn- chronous counterpart. Several follow-up papers extended this semi-asynchronous framework to other settings (Tyurin et al., 2024a;b; Tyurin & Richtárik, 2024; Maranjyan et al., 2025a).
Finally, beyond asynchronous approaches, several synchronous methods address system heterogene- ity by adapting local training to worker speeds. The canonical method, FedAvg (McMahan et al., 2017), performs multiple local steps on each worker. Variants have adapted the number of local steps to match workers' computation speeds (Li al., 2020; Maranjyan et al., 2025c), effectively balancing task assignments across heterogeneous systems. More recently, Maranjyan et al. (2025b) proposed adapting the number of local steps dynamically, without requiring prior knowledge of worker speeds.
C THE COMPUTATION-ONIY MODEL. AND THE ROLE OF ASYNCHRONY
This section clarifies the scope of our modeling assumptions and the specific phenomenon our results target. Asynchrony is designed to eliminate waiting time: the idle time that arises when workers have heterogeneous computation speeds or experience straggling behavior due to hardware stalls, load imbalance, or network delays. A key point is that the goal of asynchrony
reduce
16

---

Published as a conference paper at ICLR 2026
communication cost, but to ensure that slow or delayed workers do not force faster workers remain idle.
Critically, in the simplest setting Besting-hhmogeneoon homogeneous data and communication cost-it was unknown until very recently whether an asynchronous SGD method could match the optimal syn- chronous rate. In fact, existing asynchronous methods were shown be worse than the optimal syn- chronous algorithm in this basic regime (Tyurin & Richtárik, 2024). The recent work of Maranjyan al. (2025d) resolved this foundational case for the first time by showing that, under homogeneous data, an asynchronous method can achieve the same optimal time complexity as the synchronous method Rennala SGD (Tyurin Richtárik, 2024). Our work extends this understanding the sig- nificantly more challenging heterogeneous-dane setting and shows that asynchrony can solve the problem it designed and that can do so optimally.
Asynchrony and stragglers. Stragglers may be caused by slow computation, device variability, or even communication delays. From the server's perspective, a worker whose gradient arrives late because it is still communicating appears identical to one that is slow at computing. Asynchrony ensures that such tributing updates while slow or delayed workers catch up. This ability to eliminate idle time is precisely the purpose of asynchronous methods.
of source- do not block progress: fast workers continue con-
Asynchrony does not reduce communication cost. Although asynchrony prevents waiting dur- ing communication-indueed delays, it does not reduce the communication overhead itself. Reducing communication cost requires orthogonal techniques such as gradient compression, sparsification, quantization, or local-update schemes (e.g.. FedAvg (McMahan et al., 2016)). For example, Tyurin et al. (2024b) explicitly study communication-awwl training and use compression-bust to reduce communication rithmic axis that must be combined with, rather than replaced by, asynchrony. Thus, asynchrony resolves the waiting problem caused by delays, but not the communication-cosi problem; addressing the latter requires additional mechanisms.
methods mem-ddmonttrating that communication efficiency is a separate algo-
Why communication is not modeled explicitly here. For these reasons, we adopt the stan- dard computation-only model used in essentially all theoretical works on asynchronous SGD (Mishchenko et al., 2022; Koloskova et al., 2022: Tyurin & Richtárik, 2024; Tyurin & Richtárik, 2024; Maranjyan al., 2025d), which is also the model under which the lower bounds Tyurin & Richtárik (2024) are derived. Our claims of optimal time complexity therefore refer to this shared and well-established model. Studying asynchrony under explicit communication cost where must interact with compression, local updates, or ferent theoretical framework, and beyond the scope of this work.
new lower bounds and a dif-
D ARBITRARILY CHANGING COMPUTATION TIMES
In practice, the fixed computation model (2) is often not satisfied. The compute power of devices can vary over time due to temporary disconnections, hardware or network delays, fluctuations in processing capacity, other transient effects (Maranjyan et al., 2025a).
In this section we extend our theory to the more general setting arbitrarily varying computation times.
D.1 UNIVERSAL COMPUTATION MODEL
To formalize this setting, we adopt the universal computation model introduced by Tyurin (2024).
For each worker i [n], define compute power function
P: -R
assumed nonnegative and continuous almost everywhere (countably many jumps allowed). For any T2 2 Ti 2 0, the number of stochastic gradients completed by worker on [Ti is
1
T2
#gradients in [Ti =
pi(t)(e
17

---

Published as a conference paper at ICLR 2026
Here, (t) models the worker's vary-ig computational ability: smaller values interval yield fewer completed gradients, and larger values yield more.
For instance, if worker i remains idle for the first T seconds and then becomes active, this corre- sponds to pt(t) = 0 for t < T and p;(t) > for > T. More generally, (t) may follow periodic or irregular patterns, leading to bursts of activity, pauses, chaotic changes in compute power. The process (t) may even be random, and all results hold conditional on the realized sample paths of {p:).
The universal computation model reduces to the fixed computation model (2) when p;) = 1/r. for all / 2 0 and E [n]. In this case,
#gradients in [T1, Tb] T2 Ti
meaning that worker i computes one stochastic gradient after Ti T; seconds, gradients after T1 + 2T, seconds, and so on.
D.2 TOWARD AN OPTIMAL METHOO
In the general setting of arbitrarily varying computation times, Algorithm 1 is not optimal. To see why, consider the following adversarial timing pattern.
Suppose there are two workers. During one gradient computation by the slower worker, the faster worker computes gradients. Immediately afterwards, they switch roles: the previously fast worker slows down by factor of s, while the previously slow one speeds up by the same factor. This pattern repeats each time the slower worker finishes gradient computation.
In this setting, if we run Algorithm 1, the server waits in each Phase 1 for a single gradient from every worker. Thus, the slower worker always contributes only one gradient, and the harmonic mean of the batch sizes satisfies
S B* I 2.
From Theorem 5.1, the iteration complexity is
nLA
Bne
When <²/ne is much larger than B, this dependence can be highly suboptimal.
Instead, suppose the server waits until one full round of the above process completes, collecting + 1 gradients from each worker. Then the harmonic mean satisfies 8 2 + 1, which can be arbitrarily larger than 2. Since in practice both s and ''/ne can be very large, the naive strategy of waiting for only one gradient per worker (as in Algorithm 1) cannot be optimal in the arbitrary-time setting.
D.3 AN OPTIMAL METHOD
The solution simple and follows directly from the iteration complexity bound. From
nT.
o²
Bne
we see that to balance the terms it suffices to ensure
d²
B
nE
Accordingly, we modify the stopping condition in Phase 1 of Algorithm 1. Instead of requiring the server to receive at least one gradient from each worker, we require the stronger condition used in Malenia SGD, namely
o² mE
2 max 1,
(4)
72
by
18

---

Published as a conference paper at ICLR 2026
where b; is the number of gradients received from worker i.
In the low-noise regime, where o//ne I 1, the condition reduces to requiring b, 2 1 for all i, so the algorithm coincides with the original Algorithm 1. In the high-noise regime, the algorithm collects more gradients in Phase 1, ensuring that B is sufficiently large for optimal convergence.
With this change, Phase of algorithm matches that of Malenia SGD. The difference lies in Phase 2: our algorithm continues to use the ongoing gradient computations from workers to perform updates, while Malenia SGD discards any unfinished gradients, performs a single update, and then proceeds to the next round.
The following theorem establishes the time complexity of our algorithm under the universal compu- tation model.
Theorem D.1. Under Assumptions I, 2, and 3, let the stepsize in Ringleader ASGD be
10nL
Then, under the universal computation model, Ringleader ASGD finds an E-stationary point within at most TK seconds, where
160L
K
and T denotes the K-th element of the recursively defined sequence
[" (t(t) dt
max {1, o²
T min T 0:
Te-1
NE
for all k 2 with initialization T 0.
This result matches the lower bound derived by Tyurin (2024), and therefore the proposed method optimal.
Proof. Under the condition in (4), each gradient-type step of the algorithm satisfies
B
max
L,
71
In Theorem 5.1, instead of using B can substitute any valid lower bound. Here we choose
B = max {1
With this substitution, the iteration complexity becomes
K = S0nLA
To derive the time complexity, consider the time required to perform n iterations. Each block of updates occurs in Phase 2 following the Phase gradient collection. Starting from time T 0, Phase ends once the accumulated number of gradients satisfies condition (4), which occurs at time
pi(l)ai di [)
1 Σ
/'
o²
T min
T 0:
max 1, me
After Phase 1, to complete n updates in Phase 2 we must wait for the ongoing computations to finish. This requires most
1 Σ
T min
T T20- 0:
Pa(t) dt
>
1=1
19

---

Published as a conference paper at ICLR 2026
Thus, the total time complete all K iterations is bounded by
TP*
where the sequence (T* )x20 is defined recursively as
T = min T20:
dt dt
max
1, ne
T = 0.
T
E AUXILIARY LEMMAS
Here we provide proofs of lemmas omitted from the main text, along with auxiliary results that will be used later.
E. RELATIONS BETWEEN SMOOTHNESS CONSTANTS
We begin with lemma relating the different smoothness constants.
Lemma E.1 (Smoothness Bounds). Suppose Assumption 2 holds with constant L 0. Then is sm-othoth with Lg I L. Moreover, if each fi is L.f-smooth, then Assumption is satisfied, and we have
LIS
Σ 1=1
3 S max Ly. =: Lmax sE(n]
Finally, if all Si are identical, i.e,, fi - f all [n]. then L Ls-
Recall from Assumption that assumed the following generalized smoothness condition: for some constant > 0 and for all E Idd and yn E R",
2
1
Vf(z)
ye
(5)
n
n
Recall that a function & is called Lm-othoth if
[Vo(z) - voly)l s Lo || - vll
Va, y Rd
Here Lg denotes the minimal such constant. We are ready to prove the lemma.
Proof. For the first inequality, take
Un = y. Then (5) reduces to
[Vf(2) f((r) 2 < L vl
so f is L-smooth. By definition of Ly as the minimal smoothness constant, this implies Ly S L.
For the second inequality, by the triangle inequality, then by the smoothness of each fi, and finally by Cauchy-Schwarz,
Vf(x) 1 VV(li)
< V((())) V (l.)ll < 1 Σ Ly. || vill
x vill
Squaring both sides shows that (5) holds with L
v
1/ Σ 12
20

---

Published as a conference paper at ICLR 2026
Finally, suppose all fi are identical: fi f for all Then
()(x) VS(
1
Vf(x) vs(x))l
S
Lf
x yi
f
yell?
7
where the last step uses Sauchy-Schwarz. Squaring both sides yields
2
(f(x) Σ
S
i... (5) holds with L < Ly. Combined with L3 S L, we conclude L = LG.
E.2 PROOF LEMMA 4.1
The following lemma gives bound on the delays of Ringleader ASGD, Lemma 4.1 (Bounded Delay). In Ringleader ASGD (Algorithm 1), the delays of satisfy
8
$ 22
for any worker i [n] and any iteration k
Proof. We prove this by analyzing the structure Ringleader ASGD. The algorithm operates in rounds, where each round consists of Phase (gradient collection) followed by Phase (sequential updates). In each Phase 2, the server performs exactly n updates, one for each worker. Phase begins at iterations 0, n, 2n, 3n,..., i.e., at multiples of
First round (iterations 0 to 1): Initially, all workers compute gradients at point x., during iterations 0, 0,1,..., n 1, the server receives gradients computed at x For any iteration this range, the server processes gradients [x ( so 5 k - n Thus, delays simply increment during Phase 2.
At the end of this round, each worker has received new model xy for some j (1.2,...,n) and these update iterations are distinct across workers.
Second round (iterations n to 2n 1): At the start of the second Phase (at iteration nt,, the gradient table contains gradients [x"===0" where 8 E {0, (0.1.....a n- 1}. These delay values are distinct across workers since each worker received its update a different iteration the previous round.
During iterations n to 2n - 1, these delays increase by 1 at each iteration for the same reason as in the first Phase 2, giving 5?n-1 (n- 1, 2n - 2} at the end of this round. At the same time, all workers receive new points to compute gradients from, so during the next Phase 2, the delays will again be distinct for all workers and in {0, 10.1,...1.111
General pattern: By induction, at the beginning of each round starting at iteration on (for integer c 2 1), the delays 8."H take distinct values in {0, 1,..., 1}. During each Phase these delays increase by at most n - 1, giving the bound:
8 S (n 1) + (n
2n 2.
E.3 VARIANCE TERM
The following lemma bounds the variance of the gradient estimator in Ringleader ASGD.
21

---

Published as a conference paper at ICLR 2026
Lemma E.2 (Variance Bound), Under Assumption 1, the following variance-type inequality holds for the gradient estimator used in Algorithm
12)
o²
Vf
B
1=1
Proof. Recall that the gradient estimator is defined as
fi kk :ht (et-
9.
9
T1
Let FF denote the sigma-field containing all randomness up to the start of the current round, i.c., up to iteration & - (k mod n.). Conditioning on F the evaluation points ==* are deterministic, and the stochastic gradients kJ are independent across both workers and samples j-
Using the law total expectation and the independence of stochastic gradients, we have
n
n
E
Vi (
V k
ot
Ft
i=1
E
v
(2
xz
n
For each worker i, the conditional variance of the minibatch gradient estimator is
o vli (
E
vf
j=1
)1²
v
Fz
b
where the last inequality follows from Assumption 1. Combining these results, we get
n
"|'
|"
2
d²
fi x
11
n
D
B&n
where the last equality uses the definition of the harmonic mean B²
1
Em
#
F PROOF OF THEOREM 5.
Our convergence analysis follows the structured approach employed by Maranjyan et al. (2025d), which decomposes the proof into two key components: descent lemma that tracks the progress of the objective function and a residual estimation lemma that controls the accumulated delays in the system.
The first lemma quantifies how much the objective function decreases at each iteration, account- ing for both the standard gradient descent progress and the additional complexities introduced by asynchronous updates.
22

---

Published as a conference paper at ICLR 2026
Lemma F.1 (Descent Lemma; Proof in Appendix F.1). Under Assumptions I and 2. if the stepsize in Algorithm satisfies Y I 1/aL, then the following inequality holds
E [ 2
+
- }
[f (x*))
E
fi (zt-s))
4
i=1
712
B
1
t
of
||)
2
372
2n
2B
2
Σ
E
k= (k mod m)
This descent lemma shares a similar structure with its counterpart in the homogeneous setting ana- lyzed by Maranjyan et al. (2025d), but with crucial additional term. The final summation term in the upper bound captures the effect of using stale gradients from the gradient table-a a phenomenon we refer to as "table delay". This term is absent in the homogeneous case because no gradient table is maintained. Indeed, when ble becomes unnecessary, and this additional term vanishes, recovering the original descent lemma established by Maranjyan al. (2025d).
our setting reduces to the homogeneous case, the gradient ta-
Next, similar to (Maranjyan et al., 2025d), we derive a lemma to bound the term involving the difference between current and old points.
Lemma F.2 (Residual Estimation; Proof in Appendix F22, Under Assumption 1, the iterates of Ringleader ASGD (Algorithm 1) with stepsize "f S 1/anL satisfy the following bound
1 K
Σ E k=
2ym LK
E
Vij
2
(2
2 +
LB
k=
Finally, we get the iteration complexity combining these two lemmas.
Theorem 5.1 (Iteration Complexity). Under Assumptions 2, and 3, let the stepsize in Ringleader ASGD (Algorithm 1) be
1
cB
? min
88L
10Lo²
Then,
K
E
f (x*)) ||]
Se.
K
for
K
2
32nLA
2
= =
|nLA
1
Bs²
Bne/
Proof. We start by averaging the inequality from Lemma F.1 over K iterations and dividing both sides by 7/2
K
fo ot)
E
E
K
2K
K=
k=0
24
Lo
+
B
L 1 K-1
E
n K
k=0 i=1
K-1
+ 2
Σ
Σ
E
M
St
of
K
k=0 t=k
(k mod n)
23

---

Published as a conference paper at ICLR 2026
We now bound the third term the right using Lemma F.2
K-1
K-1
|7]
(z
E
Si
K
2K K=
k=
2A
37
271.0²
+
B
B
+ Lm
1
K-1
E
1
n
fsz
(at-
K
k=
1=1
K-
+ 1
Σ
Σ
E
fi
(22
K
k=0
t=k
(k mod n)
2A
5
B
1
K-1
n
+ 27 Lm
E
fi
K
11 5=1
k==
K
1
n Σ
+ 2
Σ
E
K
Now, using the bound 7 S 1/8nL, we obtain
K
2A KK
5y
+
K
B
Finally, plugging in the stepsize and the expression for K ensures the right-hand side is bounded by
F.1 PROOF OF LEMMA F.1
We now prove the descent lemma.
Lemma F.1 (Descent Lemma). Under Assumptions 1 and 2, if the stepsize in Algorithm satisfies
? S 3/4r. then the following inequality holds
27
E (a ]
S S [s
[a²)]
fi
(5)
i=1
+ T.2
2
3,22.02
E
st
+
2n
2B
+ 2 L
E
t=k- (k mod n)
Proof. Some proof techniques are adapted from the works of Maranjyan et al. (2025d) and Wang et al. (2025).
From Assumption 2 and Lemma E. we know that f is L-smooth. Therefore, the following stan- dard incquality holds (Nesterov, 2018)
E [[( S R [(x+)) - (VI(a)) + L2 2 || 1|2
(6)
24

---

Published as a conference paper at ICLR 2026
Recall that the gradient estimator is defined
1 9:
1 n 9
1 n
gº
Let Fk denote the sigma-field containing all randomness up to the start of the current Phase 2, i.., up to iteration k- (k mod n). A key observation is that all gradients the current gradient table were computed and received during the current round. Since these gradients were computed at points from previous iterations within the current round, we have k - 0 z - (k mod n) for all i E [w]. Conditioning on FK, the points = are deterministic. Therefore, we can compute the conditional expectation of the gradient estimator:
n Σ
E
F
Ki 9
F
=
fs x (2
j=1
The last equality follows from the unbiasedness of the stochastic gradient estimator (Assumption 1). Using this conditional expectation and the law of total expectation, we can now simplify the inner product term in (6):
Vf (z*) - (2
=E
V (x*) Σ Vfi
(
+ E
E
Vs (2t)) 'n
1 Σ vsi (2
+ E
f (at) - vf (2 (k mod mi)
g
1 Vif (at
i-1
v.f (att- (Ko mod mod mi) .
- -- 1
V (at-st))
+ E
i=1
Vii (x (xt-at))
E
x=1
+ E
( vs (at mod m))
gg
Σ V (xt-ot)
i=1
22
Next, using Assumption 2, we have
1
(dt-ct))
2T
E
2
Vi
n
( x 17
- n -
E
|V
fz
E
V
(a*)
Vi
(2
7
|
> E
+
vi
a ot)
1
E
b -
n
25

---

Published as a conference paper at ICLR 2026
Next, we analyze T2
V (xt) -V/ (a( mod mod m))
(
T2 R
Vi
EE
f (x**) - J/ 2x--
mod mod
Σ
fi
==1
xk (K mod m)
LE
LE
g
f
t=
(I mod m)
L
E |
mod m)
k-
Ly
E
||a
+E
V
f
a (5
t= mod n))
t=1
Ln
Σ
E ||o00
[|]]
(k mod n))
2B
(k mod n)
LA
Σ
E ||000
||]
Lyya²
2B
t=k-(h (k mod n)
The inequalities follow from the Cauchy-Schward inequality, L-smoothness of f. the triangle in- equality, Young's 's inequality, Lemma E.2, and finally (k mod n) S n < n.
remains bound the term E [|0*) [r]
Using Young's inequality, have
12
12
72
E
||
||00
27
< 2E
fi 6 8
+ +E
g
V
fi
x
i=1
< 2
12 Σ V
x
-//
+ 202
B
where in the last step used Lemma E.2.
26

---

Published as a conference paper at ICLR 2026
Now, by combining all terms in (6), we obtain
E [ (a*+1)] s SR [s [x*)]
| (1*)
||
E
Si
(xt
2
2
R
2n
2
||10"1"]]
Lo?
72 E
[|001]]
2B
t= (At mod mi)
$ E
[f
-
[| V (z**)
|1
? E
V fé
(x4-00)
2
i=1
712
|o
ot
+
2n
i=1
+ +
Σ
k-1
E
1
Σ
fi
8mnk (k mod m2)
Σ fi (a
+ 2 LE
72 Lo²
22
+
Σ
B'n +
2Bk
Bh
8m (k mod n)
This completes the proof under the stepsize condition 7 S 1/4r. and = inf B*.
F.2 PROOF OF LEMMA F.2
The following lemma provides an upper bound on the residual error due to delays.
Lemma F.2 (Residual Estimation). Under Assumption 1, the iterates of Ringleader ASGD (Algo- rithm 1) with stepsize y S 1/4nt. satisfy the following bound
E
x²
8-87
<
27m
K
E
Viz
(2
+
270²
K
LK
LB
0=0
0=0
27

---

Published as a conference paper at ICLR 2026
Proof. By Young's inequality, we have
17-
2
E x
x
k
Y
g
t=
S 2
Σ
1 Σ
v fo
(26
k= n
j=1
+ B
Σ
g
k=k- 8k
A-1
0²
S 2-² 8%
Σ
E
(5)
+2>² (0,)
Bn.
Ł k-
Tic
In the last inequality, we used Jensen's inequality and Lemma E.2. Next, we estimate the sum of Tik
Σ
ih
E
V
f3
n
k=
k=0
1=1
Σ
1
Σ
E
k=
ビ=
K-
2
E
f
(24-
15)
1=
k=0
k= 6
K -1
n
< 2
8
mmax
E
Σ V
1=1
km0
K
n
< 4n
2
E
fi
In the first and last inequality, we used the bound 6mnax < 2n from Lemma 4.1. Finally, applying the stepsize condition 7 < 1/ant. yields the result.
G PROOF OF THEOREM 5.3
Before proving the theorem, we first prove the following lemma.
G.1 PROOF OF LEMMA 5.2
This lemma establishes a time bound for one round of iterations and, more importantly, a lower bound on B.
28

---

Published as a conference paper at ICLR 2026
Lemma 5.2. Each block of n consecutive iterations (each round) of Algorithm takes most 2n seconds. Moreover, we have
T 2
Tn
B
2Tavg
Proof. The upper bound of 2T, follows from the structure of the algorithm, which consists of two phases. In the first phase, the server waits until all workers complete least one gradient computa- tion, which takes at most T, seconds. In the second phase, the server applies the received gradients and waits all ongoing computations to finish-whie again takes at most Ta seconds. Thus, the total time for n. iterations is bounded by 2T..
We now prove the second part the lemma. Recall that
inf B
inf R20
where we define
6, inf k20
6
We interested in the number of gradients stored in the table at iteration k. This count includes gradients computed during Phase plus one additional gradient from Phase (except for the worker that finished Phase last).
Since every worker needs to compute at least one gradient during Phase 1, the slowest worker will take Tn seconds to complete single gradient computation. During this -scood interval, faster workers < n may still be finishing gradients from the previous round's Phase before starting their Phase computations for the current round.
After completing any remaining Phase 2 work (which takes at most seconds), worker i has at least 7, 7, seconds remaining compute additional gradients for the current round's Phase 1. The number of gradients that worker can compute satisfies
b, max
Tn
Ti
max 1, Ta
1
Ti
For workers where Ta 2 2T, we have
Tn
Tn 2T;
2
and hence
b, Tn
2Ti
Plugging this bound into the expression for B gives the claimed result.
We are now ready to prove Theorem 5.3.
Theorem 5.3. Let Assumptions 3, and hold. Let the stepsize in Ringleader ASGD (Algorithm 1) be min {1/SxL, =B/ =B/10Lo"}, Then, under the fixed computation model (2), Ringleader ASGD achieves the optimal time complexity
(
LA (tr
)
+ Tavg Ne
Proof. We start with the iteration complexity from Theorem 5.1
32nLA
40LAg²
|ILA
2
2
O
B
Bns
The time to do n steps is at most 2T, form Lemma 5.2. Then the time complexity is
K K=0
LA
x²
2T. X
Tn
+
Bug
It remains put B 2 Ta/27 from Lemma 5.2.
29

---

Published as a conference paper at ICLR 2026
H
TIME COMPLEXITY OF SGD
The iteration complexity of SA (Wang et al., 2025) is
m LA
K k O
ne
We now analyze the corresponding wall-clock time under the fixed computation model (2). Since the algorithm performs an update whenever a single worker finishes computation, we seek the minimal time 7 such that
K.
Observe that
Σ
Hence, we define T" by
a T Σ
K
T
then
T
K
It follows that the minimal time T is necessarily larger than T"
remains to bound 8max_ At initialization, all workers start computing their first gradients simulta- neously. By the time the slowest worker completes its first gradient (at time 7n). the other workers may each have completed multiple gradients. In particular,
gmax
Tn
Combining this with the iteration complexity bound, we obtain that the total runtime satisfies
T.
0²
T 2
1
E
NE
for some universal constant
Note that the expression above should not be viewed as an exact upper bound on the runtime. It is better understood simplified estimate of T, which sufficient for our purposes and provides cleaner basis for comparison.
1 IMPROVED MALENIA SGD
Malenia SGD has the following iteration complexity (Tyurin & Richtárik, 2024)
12A4,
12AL.
+
8
where S' is lower bound on the harmonic mean of the batch sizes, i.e.,
1
SS
72
for all iterations k. the original Malenia SGD analysis (Tyurin & Richtárik, 2024), this bound follows from the condition in (4), which fixes the same value of S across all iterations.
30

---

Published as a conference paper at ICLR 2026
In the fixed-time regime (2), however, this condition is no longer necessary. By adopting the same strategy as Ringleader ASGD (Algorithm 1) D-namely, waiting for at least one gradient from each worker-we effectively replace S with B in the rate. This yields the following time complexity
12T,
1
Tn K
enB
Substituting the expression for B from Lemma 5.2 and proceeding in the proof of Theorem 5.3, we obtain the same overall time complexity as before this time without requiring condition (4), which depends on knowing and fixing in advance.
Finally, note that this improvement is only valid in the fixed-time regime. In the setting with arbi- trarily varying computation times, the same optimization cannot be applied, for the same reasons discussed for Ringleader ASGD in Appendix D.
NOTE ON LLM USAGE
Large Language Models were used to help polish the writing of the manuscript. LLM usage did not affect the scientific content of the paper.
31


Reviews:
[{"review_id": "qCyZvKp3XT", "reviewer": "Reviewer_rk1S", "summary": "This paper studies the task of finding an approximate stationary point for the average of smooth and non-convex objectives in a distributed optimization framework. It proposes and analyzes a new asynchronous optimization algorithm, Ringleader ASGD. The primary setting the paper discusses is that of fixed but heterogeneous computation speeds on different clients. In the regime where communication times to and from the server are negligible, the algorithm is shown to have optimal time complexity, up to a difference in the second-order smoothness constants across the machines. \n\nIn the appendix, the analysis is also extended to other, more general asynchronous models, along with experiments that demonstrate Ringleader SGD offers performance competetive to other baseline algorithms.", "questions": "1. The authors discuss the issue of non-negligible communication costs (arguably the most realistic setting) only once while mentioning Tyurin et al. (2024b). On the other hand, multiple places in the paper, including the title, discuss optimal time complexity. This is a bit misleading. I urge the authors to dedicate a whole section to communication costs, discussing any known results in the setting with communication costs, their own algorithm and its guarantees in that setting, and potential sources of sub-optimality. In the experiments, it would be beneficial to simulate communication costs and demonstrate how the proposed algorithm performs compared to other baselines, as communication forms a larger portion of the overall physical time. Given that the improvements with respect to IA-SGD are not drastic, I am curious how these different algorithms compare when communication costs increase. Intuitively, since IA-SGD has lower overhead per communication (because buffers and other states do not need to be maintained/updated on the server), one would expect it to improve upon ringleader SGD when communication costs increase/overhead per communication increases. This can be simulated by changing model size or by increasing parallelization, which would force the server to \"wait out\" any clients trying to communicate. \n\n2. It would also be good to discuss as well as implement a variant of minibatch SGD with different mini-batch sizes on each machine, which is another natural synchronous baseline in the face of different compute speeds. In a sense, this is the simplest synchronous algorithm, not the naive mini-batch discussed in Section 3. When communication costs are high, I would expect this algorithm to outperform both IA-SGD and ringleader SGD, as it requires fewer locks (a single lock per communication round between all devices). In the setup discussed in the previous bullet point, as the authors vary the communication cost, this should intuitively beat all baselines at some point. \n\nThe last two points highlight the age-old heuristic in distributed optimization: \"Is the precious compute on the server better spent in compressing/implementing asynchrony/de-biasing or running more synchronous updates for a fixed time budget?\" Naturally, this is an empirical question, and the role of the theory should be to help weed out different regimes where different choices make sense. \n\n3. The discussion around Assumption 2 and the need for data similarity assumptions in this paper is a bit unclear to me. To me, it appears that in the non-trivial regime where $L^2$ is smaller than the average smoothness-squared across the machines, it essentially amounts to a data heterogeneity assumption. For instance, in the synchronous setting where Assumption 2 is only required on $x = \\frac{i}{n}\\sum_{i\\in[n]}y_i$, then it is akin to a second-order data heterogeneity assumption, which several works have considered for analysing local update algorithms ([1](https://openreview.net/forum?id=SNElc7QmMDe), [2](https://arxiv.org/abs/2008.03606), [3](https://arxiv.org/abs/2102.03198), [4](https://arxiv.org/abs/2405.11667), [5](https://arxiv.org/abs/1910.06378)). I understand that if the authors assume all clients are smooth, it is in some sense not restrictive to think of $L$ as just a smoothness constant; however, I would like to see a discussion of the second-order heterogeneity literature. More specifically, can the analysis in this paper be extended to the setting with a bounded second-order heterogeneity constant? Hence, the time-complexity decouples between a heterogeneity term, and another that depends on $L_f$? As a motivation, in the quadratic setting, instead of the right-hand side of Assumption 2 with just L one can write an upper bound of, $\\frac{2}{n}\\sum_{i\\in[n]}\\left(L_f^2\\|\\|x-y_i\\|\\|_2^2 + \\tau^2 \\|\\| y_i - \\bar y\\|\\|_2^2\\right),$ where $\\bar y$ is the average of $y_i$'s and $\\tau$ is the second-order heterogeneity parameter. It is unclear whether this alone will lead to an analysis in the asynchronous setting, but it at least highlights that the constant $L$ encapsulates both $L_f$ and a data-heterogeneity effect.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written, the setting is rigorously defined, and the baseline algorithms and related works are discussed clearly and sufficiently. The key theoretical result of the paper is stated clearly, and both the build-up to the algorithms and their proof sketch provide helpful intuition for the problem. Overall, it is straightforward to follow the paper's contribution. The experiments offered in the appendix also provide insight into the algorithm's actual performance.", "weaknesses": "My main criticism of the paper and the related literature is that it seems unreasonable to ignore communication costs, given that they are well known to often comprise one of the most significant chunks of overall time complexity in practice, in both synchronous and asynchronous workloads. Within the scope of the assumptions made in the paper, all the results and conclusions are valid; however, I believe that emphasizing optimality in this arguably unrealistic computation-communication model is potentially misleading. I list some explicit questions about this below. \n\nI do not expect the authors to consider communication costs in this work, but I want to see a thorough discussion of the limitations of this setting before I am convinced to raise my score.  \n\nSimilarly, I am also a little concerned about the claim that the work does not consider any heterogeneity assumptions, because Assumption 2 appears to be one. Specifically, the assumption appears to be related to the second-order heterogeneity assumption, which has been considered in the [non-convex](https://openreview.net/forum?id=SNElc7QmMDe) and [convex](https://arxiv.org/abs/2405.11667) settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "aUIttdbkpv", "reviewer": "Reviewer_kQKe", "summary": "This paper introduces Ringleader ASGD, a stochastic gradient descent method designed to achieve optimal time complexity in distributed nonconvex optimization under data heterogeneity. The work addresses a fundamental gap in asynchronous optimization theory by proposing a method that avoids restrictive similarity assumptions across workers' data distributions while matching established lower bounds.", "questions": "Refer to Weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper provides a rigorous analysis of Ringleader ASGD, proving optimal time complexity.", "weaknesses": "1. The presence of the initial gradient collection phase (Phase 1) introduces a dependency whereby the failure of any single worker node halts the entire algorithmic process. Consequently, Ringleader ASGD cannot be classified as purely asynchronous. Its core design represents a hybrid methodology that integrates elements of both synchronous and asynchronous paradigms. \n\n2. Each iteration of Ringleader ASGD may require numerous gradient computations. The paper only provides both iteration complexity and time complexity. Could you analyze its computational complexity and compare it with other methods?\n\n3. In my opinion, academic writing should adhere to fundamental structural conventions. The experimental section and conclusions should be placed within the main body of the text rather than in an appendix.\n\n4. The experimental scope could be strengthened by evaluating the method on more challenging benchmarks. Expanding the experiments to include larger-scale datasets (e.g., ImageNet, CIFAR-100) and more complex model architectures would help better validate the robustness and scalability of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Dc4IoMZw6k", "reviewer": "Reviewer_M5AX", "summary": "This paper proposes Ringleader ASGD, an asynchronous stochastic gradient descent (SGD) algorithm that claims to achieve optimal time complexity under both data and computation heterogeneity. The method integrates mechanisms from several prior works: it uses a gradient table similar to IA2SGD, employs delay control ideas from Ringmaster ASGD, and adopts a two-phase update structure inspired by Malenia SGD. Theoretical results show that, under a fixed computation-time model, the algorithm matches the known lower bound for parallel first-order stochastic methods, thereby closing a theoretical gap regarding the optimality of asynchronous SGD in heterogeneous settings.\n﻿\n\nI should note that I am **not** an expert in asynchronous or distributed optimization theory, so my ability to judge the novelty and technical rigor of the proofs is limited. From my reading, the paper appears clearly written and the analysis internally consistent, but I would encourage the area chair to give greater weight to the opinions of reviewers with deeper expertise in this area, particularly regarding the theoretical contributions and their significance.", "questions": "The experimental section is rather limited, focusing only on small-scale simulations with simple MLP models on MNIST and Fashion-MNIST. Could the authors provide more comprehensive empirical evaluations to better demonstrate the practical impact of the proposed method?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Strong theoretical contribution.**\nThe paper provides a rigorous theoretical analysis establishing that Ringleader ASGD achieves the *optimal time complexity* under heterogeneous data and computation speeds. This closes an open gap left by prior work which achieved optimality only in synchronous or homogeneous settings.\n﻿\n2. **Clear connection to prior literature.**\nThe authors carefully position their method relative to previous parallel SGD variants and articulate how each component contributes to achieving both asynchrony and optimality. The theoretical results are clearly stated and supported by well-organized proofs in the appendix.\n﻿\n3. **Conceptual clarity of the design.**\nThe proposed two-phase structure (gradient collection and sequential asynchronous updates) provides a clear mechanism to control gradient delays while avoiding idle workers or wasted computation. The algorithmic description is logically consistent and easy to follow.", "weaknesses": "The experimental section is limited and does not convincingly demonstrate the practical relevance of the proposed algorithm. Experiments are restricted to small datasets (MNIST, Fashion-MNIST) and a simple two-layer MLP, which do not reflect realistic distributed or federated learning scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "jPFeN4U9Fl", "reviewer": "Reviewer_nJYq", "summary": "The paper studies asynchronous optimization methods for smooth nonconvex functions while relaxing the similarity across workers’ data and considering heterogeneous computational times. The authors proposed a new asynchronous algorithm called Ringleader SGD, which they show to achieve the theoretically optimal rate in the regimes considered in the paper.", "questions": "My only question is about the presentation of the results. Why didn’t the authors write down the algorithmic-independent lower bound from (Tyurin & Richtarik, 2024) explicitly in the paper? They claimed their algorithm is optimal throughout the paper, but the readers will have to download (Tyurin & Richtarik, 2024) and check the lower bound therein to confirm it. It would be great to cite the lower bound of $\\Omega \\left( \\frac {L_f \\Delta} {\\epsilon} \\left( \\tau_n + \\tau _{avg} \\frac {\\sigma^2} {n \\epsilon} \\right)  \\right)$ as a separate theorem statement, or at least include it explicitly as a row in Table 1. \n\nOne suggestion is to present the results more modestly. While the authors keep claiming their methods are “optimal” (with the word “optimal” appearing for about 20 times in the paper), it should be noted that the optimality is only achieved when $L = O(L_f)$, and their method is not optimal in the general regime. The authors have mentioned this but only in the footnotes. I would recommend this restriction on “optimality” to be stated explicitly at least in the contribution and in the remarks below their main theorem. From the current presentation, it is very misleading in general, since their method might be even worse than Minibatch SGD in certain regimes. (Just to clarify, I think stating the exact restrictions helps to avoid vagueness, thus making the true contribution of this paper clearer.)", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper proposed an asynchronous optimization method called Ringleader SGD. This method extends the previous method of Ringmaster SGD to heterogeneous settings. When $L = O(L_f)$, the method of Ringleader SGD is proven to match the algorithmic independent lower bound proven in (Tyurin & Richtarik, 2024). Despite the minimax optimal rate is already achieved by a synchronous method called Malenia SGD, Ringleader SGD is a truly asynchronous variant and does not discard any gradient works. Also, the new algorithm does not need to know the gradient variances and target accuracies. \n\nI check the proofs of the main theoretical results in section 5. The proofs seem correct to me. However, I did not check the proofs of the additional results on time-varying delays.", "weaknesses": "The Malenia SGD is already optimal in the regime considered in this paper. Therefore, despite the arguments of “truly asynchronous method” and “no discarding work”, it is impossible to show any theoretical improvement over Malenia SGD in the same regime. I totally agree on this one, and this is not the weakness. *However,* I was wondering whether it is possible to show any improvement over Malenia SGD under certain cases. On the theory side, under additional restriction of data similarity, whether Ringleader SGD might be provably faster? \n\nSince there isn’t any clear theoretical advantage and the scale of the numerical experiments provided in this paper is also not convincing enough, the truly non-incremental part of contribution seems to be a parameter-free method without knowing gradient variances and target accuracies in advance. Hence, I think this contribution alone is a bit limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)