Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity

We thank the reviewer for the review.

This paper studied federated learning where each client has a different computation resource.

Our setup is relevant not only to Federated Learning but also to datacenter environments, where heterogeneous GPU clusters are common. Even in datacenters with identical GPUs, failures become inevitable as the number of GPUs increases, introducing additional heterogeneity. For example, see [0], Section 3.3.4.

[0] Grattafiori, Aaron, et al. "The llama 3 herd of models." arXiv preprint arXiv:2407.21783 (2024).

No experimental results are shown in this paper.

Experiments are presented in Section F of the appendix. We included them there because the primary focus of our paper was to refine the method and establish that it is not only practical but also theoretically optimal. That said, Figures 1 and 2 further demonstrate the practicality of our method, with Figure 2 specifically showing that it outperforms existing benchmarks in speed.

The reviewer feels that the relationship between this paper and existing papers is a bit unclear. Some of the results shown in this paper have been already proposed in the existing papers. Specifically, Theorem 2.1 has been already shown in [1], while the reviewer feels that the authors claimed that these results are also novel results in this paper.

Let us clarify the relationship between [1] and our work. [1] establishes lower bounds for the time complexity of first-order methods, while we propose a fully asynchronous method and derive an upper bound that matches these lower bounds. Additionally, [1] analyzes Rennala SGD, which also attains the lower bound, but the key difference is that Rennala SGD is not fully asynchronous—it operates as Minibatch SGD (which performs synchronous model updates) combined with an asynchronous minibatch collection mechanism. We discuss this distinction in detail in Section 1.2. Our main contribution lies in closing the gap by developing a fully asynchronous method that achieves the lower bound on time complexity.

Regarding Theorem 2.1, it is not explicitly stated in prior work, though it follows as a direct consequence of existing results. The analysis of Asynchronous SGD (Algorithm 1) appears in [2] and [3], while [1] establishes its time complexity. We formally state this in lines 175-183 and then show that Theorem 2.1 naturally follows with a different choice of workers, leading to the optimal time complexity. Notably, this specific choice of workers and its role in achieving optimal time complexity has not been shown in prior work.

[1] Alexander Tyurin, Peter Richtárik, Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model, NeurIPS 2023

[2] Koloskova, A., et al. Sharper convergence guarantees for Asynchronous SGD for distributed and federated learning. NeurIPS 2022.

[3] Mishchenko, K., et al. Asynchronous SGD beats minibatch SGD under arbitrary delays. NeurIPS 2022.

In Sec. 2.2, the authors claimed that "Naively selecting the fastest workers at the start of the method and keeping this selection unchanged may therefore lead to significant issues in practice". However, since there is no need to select the same clients over time, the reviewer is wondering if Algorithm 3 really does not work well when the client speeds change over time.

It is possible to reselect workers each time the $\tau_i$ values change, but this would introduce additional computational overhead due to the need for continuous selection. Plus, it is not obvious when we should reselect workers. Additionally, a bigger issue is that $\tau_i$ is typically unknown, making this approach impractical. Instead, we propose a simpler solution using a threshold-based approach, as presented in Algorithms 4 and 5, which does not require $\tau_i$ and automatically and adaptively chooses the fastest subsets of workers.

The reviewer feels that this paper is claiming Algorithm 3 and Threom 2.1 are novel, while these results have already been shown in [1]. Thus, the main contribution of this paper is Sec. 3. The reviewer would like to suggest that the authors clarify which parts of this paper are novel.

No, these results are not shown in prior work, as discussed above.

The primary contribution of this paper is theoretical, while the reviewer would like to suggest that the authors verify their results by demonstrating the experimental results.

Indeed, our work is primarily theoretical, as mentioned earlier. However, we provide experimental results in Section F of the appendix.

Thank you for the review.

Asynchronous parallel SGD was the focus of SGD research from 2014 to 2020. With the popularity of the Adam algorithm, research on SGD has begun to decline.

We respectfully disagree with this statement. One of the important works [1] in stochastic optimization (a field that includes both SGD and Adam) was published only in 2023 (preprint in 2019). [1] proves that SGD is an optimal method in the nonconvex stochastic setting, meaning that, theoretically, Adam cannot be better than SGD. At the same time, we agree that Adam is a very important method that requires further investigation, but it is based on SGD. Without understanding SGD, it would be much more difficult to understand Adam.

I believe the biggest issue with this paper is that it merely adds a delay constraint on top of Algorithm 3 without altering any of its other mathematical properties.

Adding this delay constraint in Alg. 4 is a non-trivial and elegant fix for the original Async SGD. Surprisingly, this simple yet essential algorithmic improvement was previously overlooked.

Furthermore, the analysis of Algorithm 3 itself, such as that of the Hogwild! algorithm, already includes discussions on maximum delay .. The main conclusions of this paper are closely related to the analysis of Algorithm 3. Based on the analysis of Algorithm 3, such as the Hogwild! algorithm analysis, I believe that the analysis presented in this paper is quite straightforward ...

Note that the analysis of Async SGD in the Hogwild! paper is not the tightest previous result. [2,3] establish a better rate. We further improve it to the optimal time complexity, which is unimprovable due to the lower bounds.

The mathematical properties change significantly. Instead of the classical asynchronous SGD, we analyze a new version in which outdated and irrelevant data are ignored. First, we analyze the sum $\sum_{k=0}^K \mathbb{E}[|x^k - x^{k-\delta^k} |^2]$ in Lemma C.2 more carefully and improve upon the analysis in [2,3]. Next, Lemma 4.1, Theorem 4.2, Lemma 5.1, and Theorem 5.1 are entirely new results, which show the optimality of the Async SGD approach for the first time in the literature!

Providing such an analysis requires only minor modifications to the analysis of Algorithm 3. Therefore, the paper should have extensively discussed the shortcomings of Algorithm 3 ... the content in Section 2.2 does not convince me that Algorithm 3 has significant flaws.

Algorithm 3 presents at least two key flaws. First, it requires computation times as input and assumes that these times are fixed, an assumption that is clearly unrealistic in practical scenarios. Second, as detailed in Section 2.2, there is another significant flaw: Algorithm 3 is neither robust nor adaptive to adversarial computation environments.

This paper does indeed present two asynchronous parallel algorithms and provides relatively complete proofs and very simple experiments for these algorithms. However, from an experimental perspective, it is difficult to support the arguments made in this paper.

The goal of this paper was to prove the theoretical optimality of the Asynchronous SGD approach. This paper closes an important theoretical question from the optimization field. This paper should be read primarily as a theoretical paper.

In practical industrial scenarios, significant fluctuations in node delays are relatively rare.

This observation does not always hold; significant fluctuations appear in federated learning. Even when fluctuations are minimal, we still obtain improved and optimal theoretical guarantees (see Table, Thm. 4.2, 5.1).

Spending additional computational resources to control delay may result in higher performance losses than those caused by the delay itself.

Additional computations due to control of the delays are negligible compared to stochastic gradient computation times. How can a simple comparison $\delta^k < R$ of two integers decrease the performance of modern computation systems?

Hence, from both algorithm design and theoretical analysis perspectives, the value of this paper is quite limited.

We strongly believe obtaining an optimal Async SGD method is an important task for the ICML community. This is the first paper to demonstrate the optimality of asynchronous SGD in terms of time complexity—a point we believe was overlooked by the reviewer. The corresponding complexity is significantly better than that of previous variants (see Table 1). We believe this work closes an important open problem in asynchronous optimization.

[1] Arjevani, Y, et al. "Lower bounds for non-convex stochastic optimization." Mathematical Programming 199.1 (2023): 165-214.

[2] Koloskova, A., et al. Sharper convergence guarantees for Asynchronous SGD for distributed and federated learning. NeurIPS 2022.

[3] Mishchenko, K., et al. Asynchronous SGD beats minibatch SGD under arbitrary delays. NeurIPS 2022.

Thank you for the review.

As shown in Theorem 4.2 and Theorem 5.1, the value of the delay threshold does not depend on the computation times. Does this imply that the same value of R can be used across different distributed systems? This conclusion is somewhat confusing and counter-intuitive. It seems that the optimal value of R should be related to the computing capability of the workers in the cluster.

To clarify, in the proof of Theorem 4.2, we select $R$ to minimize the upper bound on time complexity (Equation 11), up to a universal constant. The exact minimizer—without this constant—depends on the worker times $\tau_i$. However, the resulting time complexity differs only by a constant factor.

Consider an optimization problem with varying worker times $\tau_i$. Let’s examine two extreme cases:

• $\tau_i = \infty$ for all $i > 1$ and $\tau_1 = \tau > 0$ (only one active worker) – The optimal choice here is simply $R = 1$.
• All $\tau_i$ are equal – The optimal $R$ in this case is potentially larger than $1$.

While the optimal $R$ varies across these scenarios, the final time complexities remain within a constant factor of each other.

This property is, in fact, quite powerful: as you pointed out, the same value of $R$ can be used across different data centers, leading to, at most a constant-factor difference in performance. We appreciate this observation and will clarify it further in the camera-ready version of the paper.

Only one very simple problem, a simulated convex problem, is used in experiment. Furthermore, only one specific value of R is evaluated. More experiments with more complex models and real datasets, under different settings of R, are needed to validate the efficiency of Ringmaster ASGD.

The primary goal of this paper is to establish the theoretical optimality of Asynchronous SGD. Our work addresses a fundamental open problem in optimization, providing the first proof of optimal time complexity for asynchronous SGD. We firmly believe that developing an optimal Asynchronous SGD method is essential for the ICML community. This work represents a significant step in that direction, offering theoretical guarantees that pave the way for future practical advancements.

Thank you for the review.

The techniques feel incremental, with the main proof being completed mainly using Lemmas from Koloskova et al (2022).

We acknowledge that the proof is not complicated, but we see this as an advantage rather than a limitation. A small yet impactful change can often be more valuable than a more complex modification achieving the same result.

Our work provides the first proof of the optimality of asynchronous SGD in the literature. We establish this through a simple yet non-trivial and elegant idea: introducing a threshold on gradient delays. Surprisingly, this fundamental algorithmic improvement had been previously overlooked.

Moreover, our approach significantly alters the mathematical properties of the method. Unlike classical asynchronous SGD, it discards outdated and irrelevant data, leading to a refined theoretical analysis. Specifically, we analyze the sum $\sum_{k=0}^K \mathbb{E}[|x^k - x^{k-\delta^k} |^2]$ in Lemma C.2 more carefully, improving upon the analysis in [1,2]. Additionally, Lemma 4.1, Theorem 4.2, Lemma 5.1, and Theorem 5.1 present entirely new results.

I would like to recommend restructuring the paper as follows:

Thank you for the suggestions. We will make the changes for the camera-ready version of the paper.

You assume that all $v_i$ are continuous. This might be an unrealistic assumption; moreover, I don't think you use this assumption.

We assume that $v_i$ is non-negative and continuous almost everywhere. It means that $v_i$ can be discontinued in a countable set of points, and our analysis still works. We believe that this is general enough since it allows the computation powers to "jump" on a countable set of times. We use this assumption (non-explicitly) when integrating $v_i$. Under this assumption, $v_i$ is Riemann integrable. Notice that we can easily assume that $v_i$ is measurable and use the Lebeague integral, but for clarity, we work with the Riemann integral.

Your algorithm uses a binary decision for every gradient: use it if the delay is less than R, and ignore it otherwise. This is fine if one knows a proper value of R, which introduces an additional hyperparameter. Do you think it's possible to avoid using such a hyperparameter, e.g. by scaling the gradients inversely proportionally to the delay?

We think it may be possible to make $R$ adaptive by estimating it in an online fashion, but this is beyond the scope of our current research and is left for future work.

Regarding scaling. Prior work [1,2] explored this approach by scaling gradients inversely proportionally to their delay, a method known as delay-adaptive ASGD. However, this does not achieve optimal time complexity—some outdated gradients must be ignored. We discuss this in the “Comparison to Previous Work” section (lines 306-318).

That said, introducing an additional hyperparameter is unavoidable. However, the choice of $R$ is not particularly sensitive. Specifically, in Theorem 4.2, setting $R = \max\\{1, \lceil c \frac{\sigma^2}{\varepsilon} \rceil \\}$ for any absolute constant $c$ still ensures optimal time complexity up to a constant factor depending on $c$.

[1] Koloskova, A., et al. Sharper convergence guarantees for Asynchronous SGD for distributed and federated learning. NeurIPS 2022.

[2] Mishchenko, K., et al. Asynchronous SGD beats minibatch SGD under arbitrary delays. NeurIPS 2022.