Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper analyzes asynchronous SGD (also known as delayed SGD) where stochastic gradients are computed over $M$ machines and sent to a central server and the server updates its iterates every time it receives a noisy gradient. The challenge in analyzing this algorithm is that some slow machines get to compute the gradients at out-dated iterates.

A baseline for this algorithm is a synchronous version called minibatch SGD where the server waits until all the $M$ machines finish gradient computation and makes a single update out of the aggregated minibatch of $M$ gradients.

Previous analyses on asynchronous SGD assume delays bounded above by $\tau_{max}$ and then show iteration complexities that grow with $\tau_{max}$. This paper analyzes asynchronous SGD with *delay-adaptive step sizes* and proves that asynchronous SGD has the same computational complexity as the baseline minibatch SGD, independent of the delays. This in turn implies that due to the asynchronous nature of SGD (i.e., it doesn't have to wait until all $M$ machines finish gradient calculation), it converges faster than minibatch in wall-clock time.
strengths_and_weaknesses: S1. This is a solid contribution improving the theoretical analysis of asynchronous SGD. The paper is well-written and conveys the main ideas clearly. Proof sketches are also quite helpful.

S2. Convergence of asynchronous SGD is analyzed in various setups such as Lipschitz convex (Thm 1), smooth Lipschitz nonconvex (Thm 2), smooth convex (Thm 3.1), smooth strongly convex (Thm 3.2), and smooth nonconvex (Thm 3.3) functions.

W1. It is unfortunate that the analysis does not extend well to heterogeneous setups, leaving an extra $\zeta^2$ term that prevents global convergence.

Overall, this paper is a solid theoretical contribution to the community and I would like to recommend acceptance of this paper.

questions: Q1. As I detail in L2 below, there is a concurrent work that is very similar to this submission. Can you comment on how your results compare with this concurrent paper?

Q2. In the equation below Line 159, shouldn't the second term have $next(i+1,m_i)$ instead of $next(i,m_i)$, as $next(i,m_i) = i$ always? Correct me if I'm wrong.
limitations: L1. In Table 1, it is written that the rates for the strongly convex case shown in this paper is $\exp(-\frac{\mu K}{L M}) + \frac{\sigma^2}{K}$. However, from Theorem 3.2 it seems that there should be a leading $M$ factor in the first term. Hiding this leading $M$ term in the strongly convex case is a bad omission in my opinion. (By the way I think $T$ in Theorem 3.2 should be $K$, right?)

L2. This is not necessarily a limitation of this submission, but it is quite unfortunate for the authors that a concurrent paper has presented an overlapping set of results. I am pretty sure that by now the authors would have become aware of the paper "Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning" by Koloskova et al. The paper tackles exactly the same problem as this submission and develops a very similar set of theoretical results. Koloskova et al.'s results depend on $\tau_{avg}$ but this can be thought as the number of machines ($M$) in this submission (see their Remark 5). In this regard, Koloskova et al.'s Corollary 7 shows a rate that corresponds to Theorem 2 of this paper, and Corollary 9 of theirs matches with Theorem 3.3 of this submission. Reading the two papers, I came up with a quick list of pros and cons of this paper compared to Koloskova et al.:

Pros:
- Koloskova et al. only cover nonconvex smooth cases.

Cons:
- Koloskova et al. study a slightly more general algorithm which captures both minibatch SGD and asynchronous SGD.
- Koloskova et al. show convergence in heterogeneous case (although with some modification to the algorithm)

…and I'm looking forward to the authors' comments on more detailed comparisons.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In the paper, the authors proposed a new method to analyze the convergence rate of asyn SGD method. The proposed analysis showed that the convergence rate of asyn SGD is not dependent on the delay of the gradients and comparable or even faster than the convergence of mini-batch SGD under certain conditions. 
strengths_and_weaknesses: Strenges:
1. Based on the observation that SGD should be robust to the delay and 99.9999% of the SGD steps taken have gradients with no delay, the authors proposed a new analysis for aync-SGD and showed faster convergence rate than previous analysis. 

Weaknesses:
1.  Where is the statement "99.9999% of the SGD steps taken have gradients with no delay" obtained?
2. There are a lot of works showing that asynchronous SGD hurt performance, from the theoretical analysis in the paper, asyn SGD should be at least comparable. Could the authors comment on this? 
questions: 1.  Where is the statement "99.9999% of the SGD steps taken have gradients with no delay" obtained?
2. There are a lot of works showing that asynchronous SGD hurt performance, from the theoretical analysis in the paper, asyn SGD should be at least comparable. Could the authors comment on this? 
limitations: NA
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: Authors propose a new way to analyze convergence of asynchronous SGD that does not depend on the maximum delay of gradient updates among the workers but of the number of machines. This is achieved by introducing delay-adaptive step sizes and a new virtual iterate-based analysis.
strengths_and_weaknesses: Strengths
- early part of the paper is nicely written, especially the last paragraph of 1.1 illuminated well the problem of previous analysis
- studying asynchronous SGD is important topic, as synchronous SGD has serious scalabiity limitations
- theoretical analysis is structured quite cleanly, and much of the work is in the paper itself instead of appendix
- good language

Weaknesses
- I find it suspicious to compute speedups between two Ohs, i.e  O(a) / O(b) does not make sense, because the underlying constants are not known, and may not be the same for left and right side. This makes me consider the claims of the paper overblown. In addition, to claim async SGD wins minibatch SGD over arbitrary delays seems unrealistic: what if there are very large delays for all gradient communication, i.e arbitrary large delays?  Please rephrase the title.
- there is too much in the paper, so it does not include proper experiments section which would be necessary to validate the (strong) claims.
- paper structure is messy. Hard to see where the results for Table 1 are derived, as they are presented in different form in the theorems.
- paper is missing Conclusion/Summary.
questions: - since the step size is scaled by 1/delay,  if delay is large, would it be just fine to discard those updates alltogether? At least if all machines have data from same distribution.
- in Table 1, what is sigma?
- in Table 1, where is the M/K + sigma/sqrt(K) derived in the paper? It would be good to refer to the theorem and show it in the same form in the paper text as in the table.
limitations: Limitations not discussed. Societal impact not relevant.
review_title: null

Meta-review: metareview: The paper makes a significant contribution towards the  analysis of asynchronous SGD, which hinges on a new delay-adaptive step sizes and a new virtual iterate-based analysis. The authors also cover a rather wide range of assumptions, including Lipschitz convex (Thm 1), smooth Lipschitz nonconvex (Thm 2), smooth convex (Thm 3.1), smooth strongly convex (Thm 3.2), and smooth nonconvex (Thm 3.3) functions. All the reviewers understood this contribution, and its novelty. The authors also did a good job reviewing the related literature, and clearly contextualising their work. 
confidence: Certain
Decision: Accept