Thanks for the feedback—please see below our responses to the main points you raised.

“This work is entirely theoretical; the lack of empirical evaluation limits the practical effectiveness and robustness of Algorithms 1 and 2 in real-world scenarios.”

Our work is primarily theoretical, focusing on providing improved convergence guarantees for asynchronous stochastic optimization and improving our understanding of this fundamental problem. That said, we agree with the reviewer that a numerical evaluation comparing our methods to classical asynchronous algorithms can further strengthen our results. Since the rebuttal period this year is extremely short, we will only be able to complete this for the final version. Specifically, our plan is to implement a simulated environment of delays, and to conduct a small-scale experiment with synthetic data, allowing for a larger number of simulated machines, as well as a larger experiment (with a deep NN on a standard benchmark) with a smaller number of simulated machines.

“Do the authors plan to include empirical validations, and can you share any preliminary results?”

See comment above.

“Does the method in this paper cover heavy-tailed or non-stationary delay distributions?”

Note that we actually consider arbitrary sequences of delays that need not come from a probability distribution. Therefore we do support any kind of distribution (as a special case), including heavy tailed and/or non-stationary distributions.

Thanks for pointing out additional references and further suggestions.

Thanks for the review and strong support! Please see below our responses to the main points you raised.

“I would expect a theoretical bound $\bar{\tau}_q$ on $\tau_q$. This is because that $\bar{\tau}_q$ is used to determine $B$ in Algorithm 1, while $B$ may affect $\tau_q$. Therefore, without a theoretical bound, $\bar{\tau}_q$ may be difficult to determine.”

$\tau_q$ may range from $0$ to $\Omega(T)$, depending on the adversary determining the delays, as we do not impose any assumptions on their distribution. Consequently, Algorithm 1 requires external knowledge ($\bar{\tau}_q$) about the observed delays. This is analogous to the use of the average delay (or an upper bound on it) in previous work, except that quantiles are less sensitive to outliers.

“The adaptivity result in Theorem 3 is impressive, but I still don't understand how this adaptivity is achieved. I would expect the authors to explain more.”

The somewhat surprising adaptivity stems from two key components. First, (synchronous) SGD can be used with a large batch size—determined by problem parameters—with minimal degradation in performance, even though the number of update steps is reduced, as long as the noise term dominates the error. Second, the sweep of batch sizes bypasses the discrepancy between the number of asynchronous updates that are not filtered (which is unknown) and the number of updates to $\mathcal{A}$. This doubling trick, at the cost of a small constant, enables us to “simulate” knowledge of the number of updates $\mathcal{A}$ will receive.

“Does Theorem 1 allow for the same parameter range of the algorithm $\mathcal{A}(\sigma,K)$? I ask this question because many methods such as delayed gradient descent requires the step-size to be inversely proportional to the maximum delay to guarantee convergence.”

This is a good distinction. There are no constraints on the parameter range of $\mathcal{A}$ that stem from the asynchronous nature of the problem. The only effect of asynchronous gradients on $\mathcal{A}$ is the number of update steps, which is unknown in advance and thus requires a bound $\bar{\tau}_q$ or a batch size sweep.

Thank you for pointing out additional relevant works. We will expand the literature review to include these settings in the final version.

Thank you for your feedback and for your transparency regarding your familiarity with the field in relation to the review.

“The algorithms are poorly written, to the point of being nearly incomprehensible.”

The algorithms aggregate gradients for mini-batching while filtering stale ones based on the delay. Algorithm 2 employs an additional outer loop to determine the optimal batch size, which is unknown in advance, using the standard doubling technique.

“It seems quite difficult to claim an acceleration in convergence without demonstrating it through a simulation study.”

Accelerated SGD and accelerated rates are standard terms associated with Nesterov’s seminal accelerated gradient method and its stochastic variants, which achieve convergence rates of $O(1/T^2 + \sigma / \sqrt{T})$, without necessarily a connection to empirical performance.

Thanks for the feedback—please see below our responses to the main points you raised.

“The authors provided no experiments. As the goal of this paper is to propose an algorithm, I request the authors to provide some experiments for their algorithm in practice.”

Our work is primarily theoretical, focusing on providing improved convergence guarantees for asynchronous stochastic optimization and improving our understanding of this fundamental problem. That said, we agree with the reviewer that a numerical evaluation comparing our methods to classical asynchronous algorithms can further strengthen our results. Since the rebuttal period this year is extremely short, we will only be able to complete this for the final version. Specifically, in agreement with your suggestions, our plan is to implement a simulated environment of delays, and to conduct a small-scale experiment with synthetic data, allowing for a larger number of simulated machines, as well as a larger experiment (with a deep NN on a standard benchmark) with a smaller number of simulated machines.

“One issue with several stochastic optimization algorithms, even those in (Lan 2020), are that the optimal step sizes depend on problem parameters like smoothness, or suboptimality gap. So, when implementing algorithms in practice, especially on NNs, one has to resort to tuning. In the case of Algorithm 2 here, the batch size $B_i$ also depend on problem parameters, so the authors should show if a tuning procedure alongwith some growth conditions on $B_i$ is sufficient in practice. ”

Compared to Algorithm 1, Algorithm 2 performs an outer sweep over different batch sizes. This addition is made to identify the optimal batch size, as the number of non-stale updates is unknown without prior knowledge of the delays. In a tuning scenario, one can directly tune the batch size, resulting in a simpler asynchronous algorithm that aggregates gradients for a mini-batch synchronous algorithm (essentially Algorithm 1 with a tuned batch size). We will include your suggestion in the experiments we will complete for the final version.

“Lower bound: I see that (Tyurin 2024) has a lower bound for delay distributions in their Theorem 1. Does the lower bound hold here, as this does not seem to be a zero-respecting algorithm. Also, I understand that it is concurrent work, but I request the authors to provide a more detailed comparison.”

The lower bound from the concurrent work (Tyurin 2024) applies, in their specific delay model, to the algorithms we discuss. The main distinction between our paper and (Tyurin 2024) lies in the computational model: they introduce a framework that deviates significantly from the arbitrary delay models considered in prior work (e.g., Cohen et al., 2021; Mishchenko et al., 2022; Koloskova et al., 2022). While their model is general, it is also somewhat abstract, resulting in somewhat more complex guarantees compared to the (arguably) more intuitive quantile-based convergence guarantees we provide. On the other hand, (Tyurin 2024) also establishes the optimality of filtering stale gradient technique with a well tuned batch size by proving a lower bound for zero-respecting first-order algorithms. We will include a more detailed comparison in the revision.

“Delay distributions independent of stochastic gradients: In Line 188-189, the authors assume that delay distributions are independent of stochastic gradients. Are there cases in distributed optimization where this is violated, for instance where machines with a bad delay and gradient noise, but the average gradient noise over all machine is small? Also, do existing works like (Tyurin & Richtarik 2023) handle these cases?”

The scenario you refer to falls within the setting of asynchronous optimization with heterogeneous data, where different workers have access to different samples. Some works address this setting but require additional assumptions, such as fixed delays per machine (Theorem A.4 of Tyurin & Richtarik, 2023) or certain distributional assumptions (Assumption 2 of Mishchenko et al., 2022). Supporting this case without additional assumptions is not feasible, as the data on slower machines must be accessed sufficiently many times for effective minimization. This could indeed be a valuable extension, but one that probably deserves a separate study.

Thanks for pointing out typos and further suggestions.

Thanks for the feedback. Due to space constraints, we provide our responses to the main points below.

“What does “Play $w_t=\tilde{w}_k$” means?”

In the asynchronous paradigm we consider, at each step $t$ the algorithm plays a point $w_t$ (essentially the current model at time $t$). This line means that the point the algorithm selects is $\tilde{w}_k$.

“Since $w_{t-d_t}=\tilde{w}_k$, at the iteration $k$-th of algorithm $A$…always receives a mini-batch…how the asynchrony in the proposed algorithm can achieve acceleration against synchronous SGD…”

Consider a scenario with $M$ workers, where one is significantly slower while the remaining workers are fast (e.g., three times as fast). Synchronous mini-batch SGD with batch size $M$ would wait for the slow worker at each iteration. In contrast, our algorithm with batch size $M$ leverages the fast workers to compute the one missing gradient, achieving a 1.5x speedup.

“Explanation regarding the above ambiguities shall be included…”

We will provide a more detailed version of the proof of Lemma 1 in the final version. Throughout the proofs, we treated the quantile delays ($\tau_q$) as integers, which can be done without loss of generality because (A) the delays are all integers, so $\lfloor\tau_q\rfloor$ is also a $q$-quantile, and (B) smaller delay is better. So, we can always use $\lfloor \tau_q \rfloor$ instead of $\tau_q$. We will state it more clearly in the final version---thanks for pointing this out. Below are more details on the specific transitions the review mentioned.

“...how $a_i-a_1\leq\tau_q$ is obtained in line 310.”

As the integer sequence $a_1,..,a_{n(k)}$ is increasing, $a_i\geq a_1+(i-1)$. As $i>\tau_q$, $i\geq \tau_q+1$ (these are integers), so $a_i\geq a_1+\tau_q$.

“...how the argument "since there are at least $B+1$ rounds with $i>\tau_q$." is obtained in line 314.”

We assumed by contradiction that $n(k)>B+\tau_q$, where $n(k)$ is the number of rounds with delay less or equal $\tau_q$. Working with integers, $n(k)\geq B+\tau_q+1$. So the last $B+1$ of these will have indices $i>\tau_q$.

“By the notation $\mathcal{A}(\sigma,K)$, I assume algorithm $A$ queried and received $K$ stochastic gradients…how do we introduce another $K’$...”

We differentiate between $K$, which is the number of updates $A$ needs to produce an output, and $K’$, the actual number of updates received. $K’$ cannot be larger than $K$ due to the loop structure, but we need to prove that $T$ asynchronous steps are enough to produce $K$ updates to $A$, which is ensured by proving that $K’\geq K$.

“...how the second inequality in line 324 is obtained.”

The second inequality is a part of Lemma 1. What we prove in the Lemma is that if this inequality holds, then $K’\geq K$.

“I suggest the authors to provide…proof for the case of smaller $\eta$...as claimed in the paragraph of line 390.”

We will include the proof for this case and are happy to provide further elaboration if requested by the reviewer.

“The claim of this paper would be more convincing if the authors can present numerical experiments…”

Our work is primarily theoretical, focusing on providing improved convergence guarantees for asynchronous stochastic optimization and improving our understanding of this fundamental problem. That said, we agree with the reviewer that a numerical evaluation comparing our methods to classical asynchronous algorithms can further strengthen our results. Since the rebuttal period this year is extremely short, we will only be able to complete this for the final version. Specifically, our plan is to implement a simulated environment of delays, and to conduct a small-scale experiment with synthetic data, allowing for a larger number of simulated machines, as well as a larger experiment (with a deep NN on a standard benchmark) with a smaller number of simulated machines.

“The proof of Theorem 4 considered the mini-batching algorithm, which is not the vanilla asynchronous SGD algorithm [Stich & Karimireddy, 2020] [Arjevani et al., 2020] as claimed in the first paragraph of Section 5.”

The vanilla asynchronous SGD algorithm is SGD which performs update steps in an asynchronous manner. The asynchronous SGD algorithm presented in [Stich & Karimireddy, 2020] is the instance of vanilla asynchronous SGD with constant delay. To accommodate arbitrary delays, previous works (e.g., Mishchenko et al., 2022) extended asynchronous SGD to general delays. Theorem 4 follows the definition of asynchronous SGD with arbitrary delays.

“According to Table 1…for large enough $T$…$O(\sigma/\sqrt{qT})$ would be slower than the existing $O(\sigma/\sqrt{T})$ rate….”

As we remark in lines 111-113 and in Section C, for $q=0.5$, our new rates are of the same order or better than those of previous work. The reason is that $\tau_q\leq 2\tau_{avg}$ when $q=0.5$. As the median is a more robust quantity to outliers than the average, our bounds are preferable.