1 Introduction↩︎

Modern machine learning increasingly depends on large-scale distributed training across clusters with hundreds or even thousands of GPUs [@shoeybi2019megatron; @GPT3; @narayanan2021efficient]. However, classical synchronous training methods struggle to scale in these settings, as device failures, network instabilities, and synchronization overheads introduce significant inefficiencies [@chen2016revisiting; @grattafiori2024llama]. These issues become even more pronounced in environments with heterogeneous computational power, such as Federated Learning (FL), where devices range from high-end datacenter GPUs to resource-constrained edge hardware [@konevcny2016federated; @mcmahan2016federated; @li2020federated; @kairouz2021advances]. Because synchronous methods are bottlenecked by the slowest participants, faster devices remain idle, leading to severe underutilization of computational resources when stragglers—nodes slowed down by computation or communication—lag significantly behind.

One way to reduce synchronization bottlenecks is to equip data centers with homogeneous GPUs. However, this approach is prohibitively expensive and difficult to scale: upgrading to faster GPUs would require replacing all devices simultaneously, since heterogeneous hardware cannot be combined efficiently. Even then, homogeneity does not eliminate synchronization issues, as hardware failures and device dropouts during training still cause stragglers and idle time. Moreover, this solution applies only to controlled datacenter environments and is infeasible in FL, where edge devices are outside the server’s control.

A more promising approach is to shift from hardware solutions to algorithmic ones by adopting asynchronous optimization methods. These methods remove the need for synchronization, allowing fast workers to contribute updates without waiting for slower ones [@tsitsiklis1986distributed; @recht2011hogwild; @agarwal2011distributed; @dean2012large; @li2014communication]. Despite their appeal, asynchronous methods are more difficult to analyze. In particular, a meaningful analysis would require studying time to convergence, rather than iteration complexity only. While iteration complexity is the traditional metric in optimization, it does not necessarily reflect real-world training speed in parallel settings: a method that performs more iterations may finish faster in wall-clock time if those iterations can be computed without waiting for slow workers. This distinction raises a fundamental question: among all parallel methods, which ones are provably fastest in theory? To make this question precise, we restrict our attention to smooth nonconvex problems and to stochastic first-order methods, encompassing algorithms with or without synchronization. This will be the only setting considered in this paper.

Recently, [@tyurin2024optimal] studied this very 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 setting, 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 the 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 a sufficient number of gradient computations have been accumulated.

At first, the result of [@tyurin2024optimal] suggested a rather pessimistic outlook for asynchronous 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 [@maranjyan2025ringmaster], who, in the homogeneous data setting, introduced Ringmaster ASGD—the first asynchronous SGD method to achieve the same 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 [@maranjyan2025ringmaster] established optimality in the homogeneous data setting only. The question of whether some variant of a parallel method that does not rely on synchronization (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 heterogeneous data setting is both important and practically relevant. In FL, for instance, such heterogeneity arises naturally as participants hold distinct datasets [@zhao2018federated; @li2020federated; @tan2022towards]. Yet this setting is significantly more challenging than the homogeneous one. The standard philosophy of asynchronous SGD—updating the model after every gradient computation—can be harmful here: fast workers contribute updates more frequently, causing the optimization process to become biased toward their local data. To mitigate this, most existing asynchronous methods address this issue by assuming similarity across client distributions [@mishchenko2022asynchronous; @koloskova2022sharper; @nguyen2022federated; @islamov2024asgrad]. While this assumption simplifies the analysis, it is often unrealistic in practice, where clients may involve fundamentally different populations (e.g., hospitals with distinct demographics, mobile users in different countries, or financial institutions under varied regulations).

Recent work by [@wang2025incremental] took an important step toward removing these restrictive assumptions by proposing Incremental Aggregated Asynchronous SGD (IA²SGD), a method that provably converges without similarity assumptions. However, their method achieves the same time complexity as standard Naive Minibatch SGD(see the first two rows of ¿tbl:table:fixedtime?)—the simplest synchronous SGD baseline, which waits to collect one gradient from each worker before every update—thus failing to provide the computational advantages that motivate asynchronous approaches in the first place.

To the best of our knowledge, the only method proven to be optimal in the heterogeneous data setting is the synchronous algorithm Malenia SGD of [@tyurin2024optimal], which, notably, does not rely on similarity assumptions. However, synchronization is a 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 [@maranjyan2025ringmaster].

This raises a fundamental question: Is it possible to design an 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¹ in 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(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 [@tyurin2024optimal], when the smoothness-type constant \(L\) in [ass:lipschitz95constant] is within a constant factor of the smoothness \(L_f\) used to obtain the lower bounds (¿tbl:table:fixedtime?). Importantly, Ringleader ASGD attains this without any similarity assumptions across clients’ data.

• Additional useful properties. Beyond achieving optimal time complexity, our method Ringleader ASGD satisfies two additional desirable properties: (i) all workers remain continuously active (no idle workers), and (ii) every computed gradient is incorporated into the update (no discarded work). These properties are crucial in practice, as they ensure maximum resource utilization: all workers contribute at all times, and their computations are never wasted. ¿tbl:table:fixedtime? compares Ringleader ASGD against benchmark algorithms with respect to these properties.

• Parameter-free design. In contrast to the optimal synchronous method Malenia SGD[@tyurin2024optimal], 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 stepsize, needed only to match the optimal theoretical rate). This makes it far more practical for real-world deployments, where these quantities are typically unknown or difficult to estimate. The same parameter-free improvement can also be extended to Malenia SGD, as we discuss in 13.

• Universal computation model. In 10, we extend our analysis beyond the fixed computation time model to the general setting of arbitrarily varying computation times, accommodating virtually any computational behavior, including stochastic or adversarial patterns, while retaining optimality time complexity.

• Empirical validation. In 6, we evaluate Ringleader ASGD against benchmark methods on illustrative toy problems. The results validate our theoretical findings and demonstrate clear practical advantages over the baselines.

2 Problem Setup↩︎

We consider a distributed learning setting with \(n\) workers, where each worker \(i\) possesses its own local data distribution \(\mathcal{D}_i\). Our goal is to solve the following distributed optimization problem: \[\label{eq:problem} \mathop{\mathrm{minimize}}\limits_{x \in \mathbb{R}^d} \left\{ f(x) :=\frac{1}{n}\sum_{i=1}^{n}f_i(x) \right\}, \quad\text{where}\quad f_i(x) :={\mathbb{E}}_{\xi_i \sim \mathcal{D}_i}\left[f_i(x; \xi_i)\right].\tag{1}\] Here \(f_i \colon \mathbb{R}^d \to \mathbb{R}\) denotes the local objective of worker \(i\), defined as the expectation of the sample loss \(f_i(x;\xi_i)\) over data points \(\xi_i\) drawn from its local distribution \(\mathcal{D}_i\).

2.1 Worker Heterogeneity Model↩︎

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 distributed optimization. The extension to arbitrary computation times is presented in 10.

Following the fixed computation model [@mishchenko2022asynchronous], we formalize: \[\label{eq:fixed95time} \begin{align} &\text{Each worker } i \text{ requires } \tau_i \text{ seconds\footnotemark\;to compute one stochastic gradient} \;\nabla f_i(x,\xi_i)~.\\ &\text{Without loss of generality, assume } 0 < \tau_1 \leq \tau_2 \leq \cdots \leq \tau_n~. \end{align}\tag{2}\] We assume communication is infinitely fast (taking \(0\) seconds), both from workers to the server and from the server to workers². This is a modeling choice—arguably the simplest one—and has been the standard assumption in prior work [@mishchenko2022asynchronous; @koloskova2022sharper; @tyurin2024optimal; @maranjyan2025ringmaster], even if not always stated explicitly. We further discuss the motivation and limitations of this abstraction in 9. A related study by [@tyurin2024shadowheart] considers the case where communication is non-negligible and proposes techniques to address it.

Finally, we denote by \(\tau_{\mathrm{avg}}:=\tfrac{1}{n}\sum_{i=1}^n \tau_i\) the average computation time across all workers.

2.2 Notations↩︎

We denote the standard inner product in \(\mathbb{R}^d\) by \[\left\langle x,y\right\rangle = \sum_{i=1}^{d} x_i y_i~,\] and the corresponding Euclidean norm by \(\left\| x \right\| :=\sqrt{\left\langle x,x\right\rangle}\). We use \([n] :=\{1,2,\dots,n\}\) to denote the index set, and \({\mathbb{E}}\left[\cdot\right]\) for mathematical expectation. For functions \(\phi, \psi : \mathcal{Z} \to \mathbb{R}\), we write \(\phi = \mathcal{O}(\psi)\) if there exists a constant \(C > 0\) such that \(\phi(z) \leq C \psi(z)\) for all \(z \in \mathcal{Z}\).

2.3 Assumptions↩︎

We consider the following standard assumptions for the nonconvex setting.

Recall the standard definition of smoothness

Note that [ass:lipschitz95constant] is stronger than requiring \(f\) itself to be \(L_f\)–smooth, yet weaker than all \(f_i\) being \(L_{f_i}\)–smooth. The following lemma establishes the relation among the constants \(L_f\), \(L\), and \(L_{f_i}\).

To the best of our knowledge, prior work on asynchronous SGD under data heterogeneity has always assumed smoothness of each \(f_i\), including works by [@koloskova2022sharper; @nguyen2022federated; @wang2025incremental].

Under these assumptions; our objective is to find an \(\varepsilon\)–stationary point—a (possibly random) vector \(x\) satisfying \(\mathbb{E}\left[\left\| \nabla f(x) \right\|^2\right] \leq \varepsilon\).

3 Background and Motivation↩︎

In this section, we review relevant existing methods in distributed optimization and discuss their limitations to motivate our algorithmic design. We begin with Naive Minibatch SGD as the canonical synchronous baseline, then consider Malenia SGD[@tyurin2024optimal], the first synchronous SGD method to attain optimal time complexity. We then turn to the challenges of asynchronous approaches, focusing on the recent IA²SGD[@wang2025incremental] and its limitations. Finally, we outline how these limitations can be addressed and introduce the core idea behind our algorithm.

3.1 Naive Minibatch SGD↩︎

Naive Minibatch SGD provides the most straightforward approach to solving problem 1 in a distributed setting.

3.1.0.1 Algorithm Description.

At each iteration \(k\), the algorithm performs the following update: \[x^{k+1} = x^k - \gamma \frac{1}{n} \sum_{i=1}^n \nabla f_i \left(x^k; \xi_i^k\right).\] The algorithm operates synchronously: at each iteration, the server waits to receive one stochastic gradient from each of the \(n\) workers, all of which are evaluated at the current iterate \(x^k\). Once all gradients are collected, the server constructs an unbiased minibatch estimator of the full gradient by averaging these stochastic gradients and performs a standard gradient descent step.

3.1.0.2 Limitations.

This synchronous approach has a significant computational bottleneck. Each iteration requires waiting for the slowest worker to complete its gradient computation, resulting in the iteration time \(\tau_n :=\max_{i \in [n]} \tau_i\) 2 . Consequently, faster workers remain idle while waiting for stragglers, which leads to inefficient utilization of available computational resources.

3.1.0.3 Theoretical Performance.

From a convergence perspective, Naive Minibatch SGD achieves the iteration complexity \(\mathcal{O}\left( \frac{L_f\Delta}{\varepsilon}\left(1 + \frac{\sigma^2}{n\varepsilon}\right)\right)\) to reach an \(\varepsilon\)–stationary point [@cotter2011better; @goyal2017accurate; @gower2019sgd]. The corresponding time complexity becomes \[\mathcal{O}\left(\frac{\tau_n L_f\Delta}{\varepsilon}\left(1 + \frac{\sigma^2}{n\varepsilon}\right)\right).\] This motivates the development of methods that can better utilize fast workers without waiting for stragglers.

3.2 Malenia SGD↩︎

Malenia SGD[@tyurin2024optimal] addresses the straggler problem of Naive Minibatch SGD by ensuring continuous worker utilization, rather than waiting for the slowest worker in each iteration. However, it is fundamentally a Minibatch SGD algorithm: in every iteration, it constructs an unbiased gradient estimator from multiple gradients and then performs a synchronous update. The key distinction lies in how the batch is collected—Malenia SGD gathers gradients asynchronously, allowing potentially multiple contributions from the same worker within a single iteration, unlike Naive Minibatch SGD.

3.2.0.1 Algorithm Description.

At each iteration \(k\), all workers continuously compute stochastic gradients at the current point \(x^k\). The server accumulates these gradients until the stopping condition \[\label{eq:malenia95condition} \left(\frac{1}{n} \sum_{i=1}^n \frac{1}{b_i^k} \right)^{-1} \ge \max\left\{1,\frac{\sigma^2}{n\varepsilon}\right\}\tag{3}\] is satisfied, where \(b_i^k\) denotes the number of gradients received from worker \(i\). Once this condition is met, the server performs the update \[x^{k+1} = x^k - \gamma \bar g^k :=x^k - \gamma \frac{1}{n} \sum_{i=1}^n \bar g_i^k~,\] where \(\bar g_i^k\) is the average of the stochastic gradients received from worker \(i\) \[\bar g_i^k = \frac{1}{b_i^k} \sum_{j=1}^{b_i^k} \nabla f_{i}\left(x^{k}; \xi_{i}^{k,j}\right).\] Because stochastic gradients are collected asynchronously, but the update is performed only after all required gradients are received, the algorithm can be regarded as semi-asynchronous—asynchronous in gradient collection but synchronous in parameter updates.

3.2.0.2 Stopping Condition Rationale.

The left-hand side of condition 3 appears in the variance of the gradient estimator \(\bar g^k\). Ensuring that this quantity is sufficiently large allows the algorithm to control the variance at each step. Moreover, condition 3 guarantees that every worker computes at least one gradient, which in turn yields a smaller variance than that of the estimator in Naive Minibatch SGD.

3.2.0.3 Theoretical Performance.

This asynchronous gradient collection strategy achieves the optimal time complexity \[\mathcal{O}\left(\frac{L_f\Delta}{\varepsilon}\left(\tau_n + \tau_{\mathrm{avg}}\frac{\sigma^2}{n\varepsilon}\right)\right),\] as shown by [@tyurin2024optimal]. The key improvement over Naive Minibatch SGD is that the variance term \(\sigma^2\) is now multiplied by \(\tau_{\text{avg}}\) instead of \(\tau_n\). Since \(\tau_{\text{avg}} \ll \tau_n\) in computationally heterogeneous environments, Malenia SGD can potentially provide substantial speedup in highly heterogeneous regimes.

The algorithm’s benefits are most pronounced in the high-noise settings (where \(\frac{\sigma^2}{n \varepsilon}\) is large). In low-noise scenarios or when \(\sigma = 0\), Malenia SGD offers no advantage over Naive Minibatch SGD, since collecting multiple gradients per worker provides no benefit in terms of variance reduction.

3.2.0.4 Limitations.

The main limitation of Malenia SGD is its synchronous nature. After collecting the necessary gradients, the server must broadcast the updated model to all workers simultaneously. This all-at-once synchronization creates substantial communication overhead, which can become a major scalability bottleneck in large-scale or bandwidth-limited environments.

Moreover, the synchronization process forces the server to discard ongoing gradient computations from workers who are actively computing when the broadcast occurs. Since workers operate continuously during the gradient collection phase, they must abandon their current computations upon receiving the new model, wasting valuable computational resources that could otherwise contribute to convergence.

Additionally, Malenia SGD requires prior knowledge of the noise level \(\sigma\) and the target accuracy \(\varepsilon\) to evaluate the stopping condition 3 . This dependence on problem-specific parameters, which are often unknown or difficult to estimate in practice, significantly limits its practical applicability.

These synchronization bottlenecks motivate the development of asynchronous optimal methods. Beyond avoiding coordination overhead, asynchronous approaches enable immediate model updates upon gradient arrival, which can accelerate convergence through more frequent parameter updates. This immediate processing is particularly beneficial for sparse models where gradients typically affect disjoint parameter subsets, allowing parallel updates without interference [@recht2011hogwild].

3.3 Toward Asynchronous Methods↩︎

A naive approach to making optimization asynchronous would be to update the model immediately upon receiving any gradient, using \[x^{k+1} = x^k - \gamma \nabla f_{i_k}\left(x^{k-\delta^k};\xi_{i_k}^{k-\delta^k}\right),\] where \(i_k\) denotes the worker that sent the gradient at iteration \(k\), and \(\delta^k \ge 0\) is its delay, i.e., the number of server updates that occurred while the gradient was being computed. Delays arise naturally in asynchronous execution: fast workers return gradients quickly and proceed with updated models, while slower workers compute on stale iterates; by the time they return their gradients, several server updates may already have occurred. Consequently, \(\delta^k\) is only determined when the server receives a gradient: at that point, it knows both the model iterate used by the worker and the current server iterate, and \(\delta^k\) is simply the difference between the two.

3.3.0.1 Limitations.

This approach suffers from a fundamental bias problem when workers have heterogeneous data distributions. Faster workers send updates more frequently, causing their local objectives to dominate the optimization and pull the model toward their own minimizers. Slower workers, when their updates finally arrive, push the model back toward different solutions. As a result, the iterates may oscillate or stagnate, failing to converge to a stationary point.

This bias also makes theoretical analysis difficult. Classical SGD-style proofs rely on one-step progress toward minimizing the global function, but here each update direction reflects a different local objective. Without additional data similarity assumptions [@mishchenko2022asynchronous; @koloskova2022sharper; @nguyen2022federated; @islamov2024asgrad], it becomes impossible to extend the analysis to the global function—yet such assumptions are rarely realistic when data can be arbitrarily heterogeneous across machines or organizations.

The root cause is that each update uses a gradient from one worker only. A better strategy is to incorporate information from all workers, even if some gradients are computed at stale iterates. This idea motivates methods such as Incremental Aggregated Gradient (IAG) [@blatt2007convergent; @gurbuzbalaban2017convergence; @vanli2018global] and Stochastic Averaged Gradient (SAG) [@roux2012stochastic; @schmidt2017minimizing], which maintain and aggregate gradients from all workers.

3.4 IA²SGD↩︎

As discussed above, the key insight is to construct a gradient estimator using information from all workers at each model update. IA²SGD[@wang2025incremental] achieves this by maintaining a gradient table on the server, similar to SAG or IAG, but with asynchronous table updates.

3.4.0.1 Algorithm Overview.

The server maintains a gradient table \(\{g_i\}_{i=1}^n\) that stores the most recent gradient received from each of the \(n\) workers. The table is initialized by collecting one gradient from each worker at the starting point \(x^0\). The server then computes the first model update \[x^1 = x^0 - \gamma \bar g :=x^0 - \gamma \frac{1}{n} \sum_{i=1}^n g_i\] and broadcasts \(x^1\) to all workers. Subsequently, the workers compute stochastic gradients in parallel, and their corresponding table entries are updated asynchronously as soon as the computations finish.

At each iteration \(k\), the server performs the following steps:

1. Receive gradient \(\nabla f_{i_k}\left(x^{k-\delta_{i_k}^k};\xi_{i_k}^{k-\delta_{i_k}^k}\right)\) from worker \(i_k\)

2. Update the gradient table entry: \(g_{i_k} = \nabla f_{i_k}\left(x^{k-\delta_{i_k}^k};\xi_{i_k}^{k-\delta_{i_k}^k}\right)\)

3. Perform model update: \(x^{k+1} = x^k - \gamma \bar g = x^k - \gamma \frac{1}{n} \sum_{i=1}^n g_i\)

4. Send the updated iterate \(x^{k+1}\) to worker \(i_k\) for its next computation

The gradient estimator \(\bar g\) combines the most recent gradient from each worker, ensuring that every update reflects information from the entire set of workers despite asynchronous execution. In this way, the method retains the statistical benefits of using all workers’ data while allowing them to operate independently, thereby avoiding the synchronization bottlenecks that limit scalability.

Note that, due to asynchrony, the stochastic gradients stored in the table generally correspond to different iterates of the model. We therefore record each worker \(i\)’s delay \(\delta_i^k\) to track the iterate at which its gradient was computed.

3.4.0.2 Theoretical Performance.

The iteration complexity of this algorithm was established by [@wang2025incremental], and by a straightforward conversion to the fixed computation time model (see 12), we obtain the corresponding time complexity \[\mathcal{O}\left(\frac{\tau_nL_{\max}\Delta}{\varepsilon}\left(1 + \frac{\sigma^2}{n\varepsilon}\right)\right),\] which matches the complexity of Naive Minibatch SGD. This indicates that asynchronous execution alone does not provide computational advantages over synchronous approaches. Thus, a fundamental challenge lies in how gradient delay affects convergence, which we address next.

3.5 Motivation↩︎

The primary limitation of asynchronous algorithms stems from gradient delay, which can significantly degrade convergence performance. Large delays can cause the optimization steps to follow suboptimal trajectories, which disrupts convergence.

This delay problem occurs even in homogeneous settings where all functions \(f_i\) are equal (\(f_i \equiv f\) for all \(i\in [n]\)). The state-of-the-art solution for this case, Ringmaster ASGD [@maranjyan2025ringmaster], achieves optimal time complexity by explicitly controlling delay to prevent it from becoming large. Ringmaster ASGD accomplishes this by discarding gradients that arrive with large delays.

Unfortunately, this gradient-discarding strategy fails in the heterogeneous setting of IA²SGD. The fundamental issue is that slow workers inevitably experience large delays due to their computational constraints. If we ignore or discard their delayed gradients, the corresponding table entries remain outdated and may never be updated again if subsequent gradients also arrive late and are discarded. This creates a persistent information bottleneck that degrades the quality of the gradient estimator and harms convergence.

This issue suggests we should prevent such situations from occurring by controlling the number of updates performed using fast workers. The simplest approach would be to ignore some updates from fast workers, but this contradicts the core principle of asynchronous methods whereby all workers compute gradients continuously.

Instead, our approach buffers the gradients produced by fast workers rather than applying them immediately, similar to the strategy in Malenia SGD. By buffering gradients and performing a model update only once a sufficient number have been collected, we control the delays induced by slow workers while keeping all workers continuously active. This buffering mechanism provides an additional advantage: when multiple gradients computed at the same iterate are aggregated, they yield lower-variance estimates, thereby improving convergence.

4 Ringleader ASGD↩︎

We now formally introduce our algorithm, Ringleader ASGD.

Ringleader ASGD builds upon three key insights from existing methods. First, inspired by IA²SGD, we maintain a gradient table³ to ensure that information from all workers is incorporated into every update, which eliminates the need for data similarity assumptions between workers. Second, following Ringmaster ASGD, we recognize that controlling gradient delay is essential for efficient asynchronous optimization. Third, drawing from Malenia SGD, we use buffering of stochastic gradients—rather than discarding delayed ones—to control delays while preserving valuable computations, enabling continuous utilization of all resources.

An important property of the algorithm is that all workers remain continuously active, computing stochastic gradients. As soon as a worker finishes computing a gradient, it immediately sends it to the server. Recall that we assumed communication is instantaneous, i.e., takes zero time (2.1). When the server receives a gradient, it either buffers it for later use or applies it immediately to perform a model update. If the gradient is buffered, no further action is taken and the worker simply continues computing and sending new gradients. If the server decides to perform an update, it updates the model and sends the updated model back to the worker that provided the gradient. This server-to-worker communication is also assumed instantaneous, after which the worker resumes computing gradients at the new model point, ensuring that workers are never idle.

The algorithm proceeds in rounds. In each round, exactly \(n\) model updates are performed—one for each worker. Specifically, when a worker sends a stochastic gradient, the server may apply an update and return the updated model to that worker, but it ensures that each worker receives an updated model at most once per round. Repeating this procedure \(n\) times ensures that every worker obtains exactly one fresh model per round, which in turn keeps delays bounded. To avoid discarding the computations of fast workers, the server buffers their gradients and applies them only at the appropriate moment, thereby guaranteeing that each round consists of exactly \(n\) updates.

Each round consists of two phases:

• Phase 1: Buffer stochastic gradients in a table until at least one gradient from each worker is available.

• Phase 2: Perform exactly \(n\) updates (one for each worker), then discard the old stochastic gradients from the table and return to Phase 1 to start collecting fresh ones.

The complete algorithm is formalized in 1.

4.1 Detailed Description↩︎

4.1.0.1 Initialization.

The algorithm begins by broadcasting the initial point \(x^0 \in \mathbb{R}^d\) to all workers, which then start executing the worker subroutine ([algo:Ringleader95worker]). Each worker continuously computes stochastic gradients at its current point and sends them to the server until instructed to stop, at which point the server provides a new point to resume from. This design ensures that workers remain fully utilized and never idle.

The server maintains a gradient table with entries \(\{(G_i, b_i)\}_{i=1}^n\), all initialized to zero. Here, \(G_i\) accumulates gradients, while \(b_i\) tracks the number of stochastic gradients received from worker \(i\) to form proper minibatch estimators, with \(b_i = 0\) for all \(i \in [n]\) at the start.

Before Phase 1 begins, we also initialize the set \(S = \emptyset\), which tracks which table entries contain at least one stochastic gradient. Since no gradients have yet arrived, \(S\) is empty.

4.1.0.2 Phase 1 — Gradient Collection.

In this phase, the server continuously receives stochastic gradients from the workers and stores them in the gradient table \(\{(G_i, b_i)\}_{i=1}^n\). We denote by \(g_j^k\) the stochastic gradient sent by worker \(j\) at iteration \(k\), which is computed at point \(x^{k-\delta_j^k}\) using an i.i.d. sample \(\xi_j \sim D_j\).

We do not specify how the delays \(\delta_j^k\) evolve, since this information is not needed to run the algorithm: whenever necessary, a delay can be obtained as the difference between the current model iterate and the iterate at which the stochastic gradient was computed. The delays will only play a role in the analysis, not in the execution of the method.

Upon receiving \(g_j^k\) from worker \(j\) (Line [line:receive95ph1]), the server updates the corresponding table entry and the stochastic gradient counter as follows (Line [line:update95ph1]) \[G_j = G_j + g_j^k ~, \quad b_j = b_j + 1 ~, \quad S = S \cup \{j\} ~.\] This process continues until \(S = [n]\), i.e., the server has collected at 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 a given worker are computed at the same point.

4.1.0.3 Phase 2 — Sequential Updates.

In this phase, the server performs exactly one model update for each worker \(i\), for a 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_i, b_i)\}_{i=1}^n\) and taking a descent step with this estimate (Line [line:step95last95worker]). The updated model is then sent to this worker (Line [line:broadcast95last95worker]), the worker is removed from the set \(S\), and the iteration counter is incremented (Line [line:counter95last95worker]).

Next, the server must update the remaining \(n-1\) 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.

4.1.0.4 Temporary Table Management.

To achieve this, the server maintains a temporary table \(\{(G_i^+, b_i^+)\}_{i=1}^n\), initialized to zero (Line [line:buffer95initialization]), together with a set \(S^+\) that records which workers have contributed to the table. Whenever a gradient arrives from a worker not in \(S\), it is stored in the temporary table (Line [line:buffer]).

If instead the gradient comes from a worker \(j \in S\)—i.e., one of the workers whose model we still need to update—the server first updates the main table \(\{(G_i, b_i)\}_{i=1}^n\) with this new stochastic gradient (Line [line:update95table95ph2]). It then performs a model update by again averaging the accumulated stochastic gradients in the table (Line [line:step95ph2]), broadcasts the new model to worker \(j\) (Line [line:broadcast95ph2]), increments the iteration counter, and removes \(j\) from the set \(S = S \setminus \{j\}\) (Line [line:counter95ph2]).

4.1.0.5 Preparing for the Next Round.

Once all workers in \(S\) have been updated and Phase 2 is complete (\(S=\emptyset\)), the server prepares for the next round by copying the contents of the temporary table \(\{(G_i^+, b_i^+)\}_{i=1}^n\) into the main table \(\{(G_i, b_i)\}_{i=1}^n\) (Line [line:transfer95table]). The set \(S\) is also reset to \(S = S^+\), since these workers already contributed gradients at their updated models. Entries in the main table corresponding to workers not in \(S^+\) remain zero, as the temporary table was initialized with zeros at the start of Phase 2 (Line [line:buffer95initialization]).

The server can now proceed to the next round by returning to Phase 1 and beginning a new gradient collection phase.

4.2 Delay Control Analysis↩︎

The structure of Ringleader ASGD, with its two phases, is specifically designed to prevent the unbounded delays that arise in standard asynchronous methods. To understand why this works, consider that in each round we perform exactly \(n\) updates—one per worker—before moving to the next round. This ensures that no worker can fall more than one full round behind the current iteration. The precise bound on delays is given in the following lemma

4.3 Comparison to IA²SGD↩︎

Our method is a delay-controlled version of IA²SGD. We can recover IA²SGD by removing Phase 1 (gradient collection) and Phase 2 (structured updates), and thus perform updates naively—immediately upon gradient arrival. In contrast, our algorithm operates in structured rounds, performing exactly one update per worker in each round, which provides the crucial delay control that IA²SGD lacks.

In IA²SGD, 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 the gradients from fast workers rather than immediately applying these gradients, to ensure that all workers receive updated models within \(n\) subsequent iterations.

4.4 Comparison to Malenia SGD↩︎

Malenia SGD also operates as an algorithm with two phases. In Phase 1, Malenia SGD collects gradients using a similar method to our approach, but uses a different termination condition 3 that requires knowledge of the noise parameter \(\sigma\) and the target stationarity level \(\varepsilon\), making it impractical. In Phase 2, Malenia SGD performs a synchronous update by averaging all collected gradients and broadcasting the new model to all workers simultaneously before returning to Phase 1. This synchronization forces Malenia SGD to discard ongoing gradient computations from workers that are active during the broadcast.

In contrast, our method performs Phase 2 asynchronously: we update workers sequentially as they complete their current gradient computations, which ensures that no computational work is wasted.

Regarding Malenia SGD’s termination condition 3 , in 13 we demonstrate that this condition 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-free, which eliminates the need for prior knowledge of \(\sigma\) and \(\varepsilon\). Under this 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.

5 Theoretical Results↩︎

Before presenting the theoretical results, we first write the algorithm in a compact form. The gradients for each worker in the table are all computed at the same point; for worker \(i\) at iteration \(k\), the point is \(x^{k-\delta_i^k}\). The update rule can be written compactly as \[x^{k+1} = x^k - \gamma \bar g^k~,\] where the gradient estimator \(\bar g^k\) is defined by \[\bar g^k :=\frac{1}{n} \sum_{i=1}^n \bar g_i^k :=\frac{1}{n} \sum_{i=1}^n \frac{1}{b_i^k} \sum_{j=1}^{b_i^k} g_i^{k,j} ~.\] Since multiple gradients may be received from the same worker, we denote by \(g_i^{k,j}\) 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 \[g_i^{k,j} :=\nabla f_i\left(x^{k-\delta_i^k};\xi_i^{k-\delta_i^k, j}\right)~.\] The quantity \(b_i^k\) denotes the number of gradients from worker \(i\) stored in the table at iteration \(k\), i.e., the value of \(b_i\) in Lines [line:step95last95worker] and [line:step95ph2]. Thus, the pair \((b_i^k, \delta_i^k)\) fully determines the method’s behavior at iteration \(k\).

Note that the sequence \(\{b_i^k\}\) depends only on the computation times \(\{\tau_i\}\) and the algorithm design (i.e., the stopping rule for collecting gradients). Once these are fixed, all \(b_i^k\) for every \(i \in [n]\) and iteration \(k\) are determined. Crucially, the values of \(b_i^k\) do not depend on the method’s hyperparameters \(\gamma\), \(x^0\), or on the variance parameter \(\sigma\) or the stationarity level \(\varepsilon\).

5.1 Iteration Complexity↩︎

Our convergence analysis follows the structured approach employed by [@maranjyan2025ringmaster], which decomposes the proof into two key components: a descent lemma that tracks the progress of the objective function and a residual estimation lemma that controls the accumulated delays in the system.

We begin by establishing notation for the harmonic means of the batch sizes across rounds: \[B^k = \left( \frac{1}{n} \sum_{i=1}^n \frac{1}{b_i^k} \right)^{-1}, \quad \text{and} \quad B = \inf_{k \ge 0} B^k.\] Note that \(B \geq 1\), since by the algorithm’s design each \(b_i^k \geq 1\). A sharper bound on \(B\) will be established later in [lemma:time95for95n95iter].

The first lemma quantifies how much the objective function decreases at each iteration, accounting for both the standard gradient descent progress and the additional complexities introduced by asynchronous updates.

This descent lemma shares a similar structure with its counterpart in the homogeneous setting analyzed by [@maranjyan2025ringmaster], but with a crucial additional term. The final summation term in the upper bound captures the effect of using stale gradients from the gradient table—a phenomenon we refer to as “table delay". This term is absent in the homogeneous case because no gradient table is maintained. Indeed, when \(n=1\), our setting reduces to the homogeneous case, the gradient table becomes unnecessary, and this additional term vanishes, recovering the original descent lemma established by [@maranjyan2025ringmaster].

Next, similar to the work by [@maranjyan2025ringmaster], we derive a lemma to bound the term involving the difference between current and old points.

Finally, we get the iteration complexity combining these two lemmas.

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.

5.2 Time Complexity↩︎

Since the algorithm operates in rounds with \(n\) steps per round, and its iteration complexity is already known, it remains to determine the duration of each round. We have the following lemma

Based on this lemma, we derive the time complexity guarantee of our algorithm

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 to solving the problem. The second term, however, involves \(\tau_{\mathrm{avg}}\) rather than \(\tau_n\) as in Naive Minibatch SGD(see ¿tbl:table:fixedtime?)—this substitution captures the core benefit of asynchronous execution. Specifically, this advantage becomes pronounced when \(\sigma\) 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 gradient evaluations suffice for good performance, making Naive Minibatch SGD already quite effective and rendering the additional complexity of asynchrony unnecessary.

Under this condition, the resulting time complexity matches the lower bound of [@tyurin2024optimal], making Ringleader ASGD the first asynchronous algorithm to achieve optimality under heterogeneous data.

6 Experiments↩︎

To validate our theoretical results we perform a toy simulation.

We consider image classification on MNIST [@lecun2010mnist] and on Fashion-MNIST [@xiao2017fashion] with standard normalization for both datasets. To enable equal client sizes, we first trim the dataset so that the total number of examples is divisible by the number of clients \(n=100\). To obtain heterogeneous datasets across clients, we then partition the trimmed set using an equal-size Dirichlet procedure with concentration parameter \(\alpha=0.1\) [@yurochkin2019bayesian]. For each client \(j\in[n]\), we draw proportions \(p_j \sim \mathrm{Dirichlet}(\alpha,\ldots,\alpha)\) over the classes and compute a rounded class-allocation vector whose entries sum exactly to \(\frac{N}{n}\), where \(N\) is the trimmed dataset size. This creates non-IID data where each client has a skewed distribution over classes (with \(\alpha=0.1\), clients typically observe only 1-2 classes frequently).

When assigning samples, we take the requested number from each class pool for client \(j\). If a 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 a two-layer MLP \(\mathrm{Linear}(d,128)\!\to\!\mathrm{ReLU}\!\to\!\mathrm{Linear}(128,10)\) trained with mean cross-entropy. Stochastic gradients at the clients use a minibatch of size \(4\), while reported gradient norms are computed on the full dataset.

We emulate heterogeneous compute by assigning each client \(i\) a base delay and a random jitter: \[\tau_i \;=\; i \;+\; |\eta_i|~, \qquad \eta_i \sim \mathcal{N}(0,i)~, \quad \text{for all } i\in [n]~.\] For each method we tune the stepsize \(\gamma\) within a fixed wall-clock budget. We sweep \[\gamma \in \{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 \(\gamma\) per method for evaluation.

We report the full-batch gradient-norm squared \(\|\nabla f(x^k)\|^2\), versus wall-clock time. Each method is run \(30\) times over different seeds. We report the median with interquartile range (IQR). To reduce high-frequency noise, we apply a centered moving-average smoothing to the aggregated curves (post-aggregation), while keeping the initial point unchanged.

2 shows the results. We observe that Ringleader ASGD converges faster compared to Malenia SGD and IA²SGD. 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 2 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.

7 Conclusion↩︎

We have introduced Ringleader ASGD, the first asynchronous stochastic gradient method to achieve optimal time complexity under arbitrary data heterogeneity and arbitrarily heterogeneous computation times in distributed learning, without requiring similarity assumptions between workers’ datasets.

Its core innovation is a 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 a gradient table and alternating between gradient 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 no computation is wasted.

Our analysis shows that Ringleader ASGD matches the optimal time complexity bounds established by [@tyurin2024optimal]. In contrast to 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 a minor modification, Ringleader ASGD also achieves optimality in the more general setting of arbitrarily varying computation times (10).

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-CRG12-2024-6460, and iii) Center of Excellence for Generative AI, under award number 5940.

8 Related Work↩︎

Research on asynchronous stochastic gradient methods dates back to the seminal work of [@tsitsiklis1986distributed], and gained renewed momentum with the introduction of the HOGWILD! algorithm [@recht2011hogwild]. HOGWILD! is fundamentally an asynchronous coordinate descent method: updates 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 [@reddi2015variance; @zhao2016fast; @mania2017perturbed; @leblond2018improvedAsynchronous; @nguyen2018sgd; @zhou2018simple], 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 [@agarwal2011distributed], who studied convex objectives, as well as later extensions to the non-convex case such as the work of [@lian2015asynchronous] and [@dutta2018slow], the latter analyzing exponentially distributed computation times. Other relevant results in this line include those of [@feyzmahdavian2016asynchronous; @zheng2017asynchronous; @arjevani2020tight; @feyzmahdavian2023asynchronous], all of which assume fixed delays. More recently, delay-adaptive methods have been proposed, aiming to improve performance by down-weighting very stale gradients [@cohen2021asynchronous; @koloskova2022sharper; @mishchenko2022asynchronous].

Particularly relevant to our work are asynchronous variants of SAGA. [@leblond2018improvedAsynchronous] developed a shared-parameter version in the spirit of HOGWILD!, while [@glasgow2022asynchronous] studied a distributed setting that employs full gradients, in contrast to our stochastic-gradient perspective.

A large body of recent work investigates asynchronous methods in federated learning (FL), where clients hold data from heterogeneous distributions. Notable contributions include works by [@xie2019asynchronous; @mishchenko2022asynchronous; @koloskova2022sharper; @wang2022asyncfeded; @wang2022asynchronous; @glasgow2022asynchronous; @fraboni2023general; @zhang2023no; @wang2024achieving; @islamov2024asgrad; @alahyane2025optimizing].

More broadly, [@assran2020advances] provide a comprehensive survey of asynchronous optimization methods.

There is another line of work that began with [@tyurin2024optimal], who established lower bounds for parallel methods and proposed optimal synchronous algorithms together with an asynchronous counterpart. Several follow-up papers extended this semi-asynchronous framework to other settings [@tyurin2024freya; @tyurin2024shadowheart; @tyurin2024optimalgraph; @maranjyan2025mindflayer].

Finally, beyond asynchronous approaches, several synchronous methods address system heterogeneity by adapting local training to worker speeds. The canonical method, FedAvg [@mcmahan2017communication], performs multiple local steps on each worker. Variants have adapted the number of local steps to match workers’ computation speeds [@li2020federated; @maranjyan2025gradskip], effectively balancing task assignments across heterogeneous systems. More recently, [@maranjyan2025ata] proposed adapting the number of local steps dynamically, without requiring prior knowledge of worker speeds.

9 The Computation-Only 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 even network delays. A key point is that the goal of asynchrony is not to reduce communication cost, but to ensure that slow or delayed workers do not force faster workers to remain idle.

Critically, even in the simplest setting—homogeneous data and no communication cost—it was unknown until very recently whether an asynchronous SGD method could match the optimal synchronous rate. In fact, existing asynchronous methods were shown to be worse than the optimal synchronous algorithm in this basic regime [@tyurin2024optimal]. The recent work of [@maranjyan2025ringmaster] 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[@tyurin2024optimal]. Our work extends this understanding to the significantly more challenging heterogeneous-data setting and shows that asynchrony can solve the problem it is designed for—and that it can do so optimally.

9.0.0.1 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 delays—regardless of source—do not block progress: fast workers continue contributing updates while slow or delayed workers catch up. This ability to eliminate idle time is precisely the purpose of asynchronous methods.

9.0.0.2 Asynchrony does not reduce communication cost.

Although asynchrony prevents waiting during communication-induced 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 [@mcmahan2016federated]). For example, [@tyurin2024shadowheart] explicitly study communication-aware training and use compression-based methods to reduce communication time—demonstrating that communication efficiency is a separate algorithmic axis that must be combined with, rather than replaced by, asynchrony. Thus, asynchrony resolves the waiting problem caused by delays, but not the communication-cost problem; addressing the latter requires additional mechanisms.

9.0.0.3 Why communication is not modeled explicitly here.

For these reasons, we adopt the standard computation-only model used in essentially all theoretical works on asynchronous SGD [@mishchenko2022asynchronous; @koloskova2022sharper; @tyurin2024optimal; @tyurin2024optimalgraph; @maranjyan2025ringmaster], which is also the model under which the lower bounds of [@tyurin2024optimal] are derived. Our claims of optimal time complexity therefore refer to this shared and well-established model. Studying asynchrony under explicit communication cost—where it must interact with compression, local updates, or buffering—requires new lower bounds and a different theoretical framework, and is beyond the scope of this work.

10 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, or other transient effects [@maranjyan2025mindflayer].

In this section we extend our theory to the more general setting of arbitrarily varying computation times.

10.1 Universal Computation Model↩︎

To formalize this setting, we adopt the universal computation model introduced by [@tyurin2024tighttimecomplexitiesparallel].

For each worker \(i \in [n]\), we define a compute power function \[p_i : \mathbb{R}_{+} \to \mathbb{R}_{+}~,\] assumed nonnegative and continuous almost everywhere (countably many jumps allowed). For any \(T^2 \ge T^1 \ge 0\), the number of stochastic gradients completed by worker \(i\) on \([T^1, T^2]\) is \[\#\text{gradients in }[T^1, T^2] \;=\; \left\lfloor \int_{T^1}^{T^2} p_i(t)\,dt \right\rfloor.\] Here, \(p_i(t)\) models the worker’s time-varying computational ability: smaller values over an 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 corresponds to \(p_i(t) = 0\) for \(t \leq T\) and \(p_i(t) > 0\) for \(t > T\). More generally, \(p_i(t)\) may follow periodic or irregular patterns, leading to bursts of activity, pauses, or chaotic changes in compute power. The process \(p_i(t)\) may even be random, and all results hold conditional on the realized sample paths of \(\{p_i\}\).

The universal computation model reduces to the fixed computation model 2 when \(p_i(t) = \frac{1}{\tau_i}\) for all \(t \geq 0\) and \(i \in [n]\). In this case, \[\#\text{gradients in }[T^1, T^2] = \left\lfloor \frac{T^2 - T^1}{\tau_i} \right\rfloor,\] meaning that worker \(i\) computes one stochastic gradient after \(T^1 + \tau_i\) seconds, two gradients after \(T^1 + 2\tau_i\) seconds, and so on.

10.2 Toward an Optimal Method↩︎

In the general setting of arbitrarily varying computation times, 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 \(s\) gradients. Immediately afterwards, they switch roles: the previously fast worker slows down by a factor of \(s\), while the previously slow one speeds up by the same factor. This pattern repeats each time the slower worker finishes a gradient computation.

In this setting, if we run 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 \[1 \;\le\; B^k \;\le\; 2~.\] From [theorem:convergence], the iteration complexity is \[\mathcal{O}\!\left( \frac{nL\Delta}{\varepsilon} \left( 1 + \frac{\sigma^2}{Bn\varepsilon} \right) \right).\] When \(\frac{\sigma^2}{n \varepsilon}\) 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 \(s+1\) gradients from each worker. Then the harmonic mean satisfies \(B^k \ge s+1\), which can be arbitrarily larger than 2. Since in practice both \(s\) and \(\frac{\sigma^2}{n\varepsilon}\) can be very large, the naive strategy of waiting for only one gradient per worker (as in 1) cannot be optimal in the arbitrary-time setting.

10.3 An Optimal Method↩︎

The solution is simple and follows directly from the iteration complexity bound. From \[\mathcal{O}\!\left( \frac{nL\Delta}{\varepsilon} \left( 1 + \frac{\sigma^2}{Bn\varepsilon} \right) \right),\] we see that to balance the terms it suffices to ensure \[B \;\ge\; \frac{\sigma^2}{n\varepsilon}~.\] Accordingly, we modify the stopping condition in Phase 1 of 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 \[} \left(\frac{1}{n} \sum_{i=1}^n \frac{1}{b_i} \right)^{-1} \;\;\ge\;\; \max\left\{1, \frac{\sigma^2}{n\varepsilon}\right\}~,\] where \(b_i\) is the number of gradients received from worker \(i\).

In the low-noise regime, where \(\frac{\sigma^2}{n\varepsilon} \le 1\), the condition reduces to requiring \(b_i \ge 1\) for all \(i\), so the algorithm coincides with the original 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 1 of our algorithm matches that of Malenia SGD. The difference lies in Phase 2: our algorithm continues to use the ongoing gradient computations from all workers to perform \(n\) 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 computation model.

This result matches the lower bound derived by [@tyurin2024tighttimecomplexitiesparallel], and therefore the proposed method is optimal.

11 Auxiliary Lemmas↩︎

Here we provide proofs of lemmas omitted from the main text, along with auxiliary results that will be used later.

11.1 Proof of [lemma:smoothness95relation]↩︎

We begin with a lemma relating the different smoothness constants.

Recall from [ass:lipschitz95constant] that we assumed the following generalized smoothness condition: for some constant \(L>0\) and for all \(x \in \mathbb{R}^d\) and \(y_1,\dots,y_n \in \mathbb{R}^d\), \[\begin{align} \label{eq:smoothness} \left\| \nabla f(x) - \frac{1}{n}\sum_{i=1}^n \nabla f_i(y_i) \right\|^2 \;\le\; \frac{L^2}{n} \sum_{i=1}^n \left\| x - y_i \right\|^2~. \end{align}\tag{4}\] Recall that a function \(\phi\) is called \(L_\phi\)–smooth if \[\left\| \nabla \phi(x) - \nabla \phi(y) \right\| \le L_\phi \left\| x - y \right\|, \quad \forall x,y \in \mathbb{R}^d~.\] Here \(L_\phi\) denotes the minimal such constant. We are ready to prove the lemma.

11.2 Variance Term↩︎

The following lemma bounds the variance of the gradient estimator in Ringleader ASGD.

11.3 Proof of [lemma:descent]↩︎

We now prove the descent lemma.

11.4 Proof of [lemma:residual]↩︎

The following lemma provides an upper bound on the residual error due to delays.

12 Time Complexity of IA²SGD↩︎

The iteration complexity of IA²SGD[@wang2025incremental] is \[K = \mathcal{O}\!\left(\frac{\delta^{\max}L\Delta}{\varepsilon} \left(1 + \frac{\sigma^2}{n\varepsilon}\right)\right).\] 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 a computation, we seek the minimal time \(T\) such that \[\sum_{i=1}^n\left\lfloor\frac{T}{\tau_i}\right\rfloor \;\ge\; K~.\] Observe that \[\sum_{i=1}^n \frac{T}{\tau_i} \;\ge\; \sum_{i=1}^n\left\lfloor\frac{T}{\tau_i}\right\rfloor.\] Hence, if we define \(T^\prime\) by \[\sum_{i=1}^n \frac{T^\prime}{\tau_i} \;=\; K~,\] then \[T^\prime = \left(\sum_{i=1}^n \frac{1}{\tau_i}\right)^{-1} K~.\] It follows that the minimal time \(T\) is necessarily larger than \(T^\prime\).

It remains to bound \(\delta^{\max}\). At initialization, all workers start computing their first gradients simultaneously. By the time the slowest worker completes its first gradient (at time \(\tau_n\)), the other workers may each have completed multiple gradients. In particular, \[\delta^{\max} \;\ge\; \sum_{i=1}^n \left\lfloor \frac{\tau_n}{\tau_i}\right\rfloor.\] Combining this with the iteration complexity bound, we obtain that the total runtime satisfies \[T \;\ge\; c \times \frac{\tau_n L\Delta}{\varepsilon} \left(1 + \frac{\sigma^2}{n\varepsilon}\right),\] for some universal constant \(c > 0\).

Note that the expression above should not be viewed as an exact upper bound on the runtime. It is better understood as a simplified estimate of \(T\), which is sufficient for our purposes and provides a cleaner basis for comparison.

13 Improved Malenia SGD↩︎

Malenia SGD has the following iteration complexity [@tyurin2024optimal] \[K \;\ge\; \frac{12\Delta L_f}{\varepsilon} \;+\; \frac{12 \Delta L_f \sigma^2}{\varepsilon^2 n S}~,\] where \(S\) is a lower bound on the harmonic mean of the batch sizes, i.e., \[\left(\frac{1}{n}\sum_{i=1}^n \frac{1}{b_i^k}\right)^{-1} \;\ge\; S~,\] for all iterations \(k\). In the original Malenia SGD analysis [@tyurin2024optimal], this bound follows from the condition in 3 , which fixes the same value of \(S\) across all iterations.

In the fixed-time regime 2 , however, this condition is no longer necessary. By adopting the same strategy as Ringleader ASGD(1)—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 \[\tau_n K \;=\; \frac{12\tau_n\Delta L_f}{\varepsilon}\left(1 + \frac{\sigma^2}{\varepsilon n B}\right).\] Substituting the expression for \(B\) from [lemma:time95for95n95iter] and proceeding as in the proof of [thm:time95complexity], we obtain the same overall time complexity as before—this time without requiring condition 3 , which depends on knowing \(\sigma\) and fixing \(\varepsilon\) in advance.

Finally, note that this improvement is only valid in the fixed-time regime. In the setting with arbitrarily varying computation times, the same optimization cannot be applied, for the same reasons discussed for Ringleader ASGD in 10.

---

1. Throughout the paper, we refer to our method as optimal. Formally, this holds whenever the constant \(L\)—associated with our new smoothness-type assumption ([ass:lipschitz95constant])—is at most a constant factor larger than the smoothness constant \(L_f\) used in the derived lower bounds [@tyurin2024optimal]. See ¿tbl:table:fixedtime? for details.↩︎

2. Alternatively, one could define \(\tau_i\) as the time required for a worker to both compute a gradient and communicate it to the server, while keeping server-to-worker communication infinitely fast. Our upper bounds would still hold under this formulation, but the lower bounds would no longer apply, so we use the simpler model.↩︎

3. It is not strictly necessary to maintain a table on the server. An alternative, as in IA²SGD[@wang2025incremental], is to store one vector on each worker along with an additional vector on the server. However, this can be problematic when workers have limited memory. For clarity and simplicity, we adopt the server-side table formulation in our description.↩︎