Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity

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 in these settings, as device failures, network instabilities, and synchronization overheads introduce significant inefficiencies (Chen et al., 2016; Grattafiori et al., 2024). 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 (Konečný et al., 2016; McMahan et al., 2016; Li et al., 2020; Kairouz et al., 2021). 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 (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 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, Tyurin & Richtárik (2024) 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 Tyurin & Richtárik (2024) 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 Maranjyan et al. (2025d), 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 Maranjyan et al. (2025d) 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 (Zhao et al., 2018; Li et al., 2020; Tan et al., 2022). 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 (Mishchenko et al., 2022; Koloskova et al., 2022; Nguyen et al., 2022; Islamov et al., 2024). 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 Wang et al. (2025) 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 Table 1)—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 Tyurin & Richtárik (2024), 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 Maranjyan et al. (2025d).

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¹¹1Throughout the paper, we refer to our method as optimal. Formally, this holds whenever the constant $L$—associated with our new smoothness-type assumption (Section 2.3)—is at most a constant factor larger than the smoothness constant $L_{f}$ used in the derived lower bounds (Tyurin & Richtárik, 2024). See Table 1 for details. in the heterogeneous data setting. Importantly, Ringleader ASGD attains this without relying on restrictive similarity assumptions.

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:

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}$.

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 (Tyurin & Richtárik, 2024), 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 (Wang et al., 2025) and its limitations. Finally, we outline how these limitations can be addressed and introduce the core idea behind our algorithm.

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⁴⁴4It is not strictly necessary to maintain a table on the server. An alternative, as in IA²SGD (Wang et al., 2025), 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. 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 (Section 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 Algorithm 1.

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

where the gradient estimator $\bar{g}^{k}$ is defined by

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

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 11 and 19. 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$.

To validate our theoretical results we perform a toy simulation.

We consider image classification on MNIST (LeCun et 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 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$ (Yurochkin et al., 2019). 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 $\nicefrac{{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:

For each method we tune the stepsize $\gamma$ within a fixed wall-clock budget. We sweep

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.

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 Tyurin & Richtárik (2024). 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 (Appendix B).