Venue: NeurIPS 2022 Conference

Reviews:

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: This work provides a theoretic study on the convergence rates of asynchronous SGD under distributed homogeneous and heterogeneous settings. The main contributions are (i) a sharper analysis for the constant stepsize async-SGD, which improves over the existing ones, and (ii) a delay-adaptive stepsize for async-SGD, which leads to the best known convergence rate, and without extra hyperparameter tuning and extra communications required in [13], (iii) improved analysis in the heterogeneous case compared with FedBuff [31].
strengths_and_weaknesses: ======= After Rebuttal =========
Thank the authors for the response, which clarified my confusions.

============================
Strengths:
- This paper is very well-written and has a nice flow of ideas.
- The key analytic technique, which I believe is the notion of active set/concurrency, seems pretty novel to me.
- Simple and intuitive algorithmic constructions with improved convergence guarantees.

Weaknesses (or comments):
- This work would benefits from some empirical evaluations, given that there is nothing impractical or hard-to-tune in the proposed schemes.
- The authors claimed that they show "for the first time, asynchronous SGD is always faster than mini-batch SGD". Ain't the convergence results in [13] (Picky SGD) already show this, did I miss something?
- Algorithm 2 does not consider local steps, which is however a key feature of federated learning systems. I am not sure if it is a straightforward extension in theory, especially with delayed updates. Could the authors discuss how the number of local steps would affect the convergence rate in Theorem 10?
questions: Questions: see comments above.

Typos:
- Algorithm 1, Line 1: sever -> server.
- Line 164, C_0 =[n]?
- Line 287, there exists
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
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: This paper study the convergence properties of asynchronous SGD for distributed and federated learning. The authors tighten the convergence rate of non-convex smooth objectives that depend on the maximum delay to $\epsilon$-stationary point from $O\left(\sigma^2\epsilon^{-2}+ \tau_{\max}\epsilon^{-1}\right)$ to $ O\left(\sigma^2\epsilon^{-2}+ \sqrt{\tau_{\max}\tau_{avg}}\epsilon^{-1}\right)$ without any change to the algorithm., where $\tau_{\max}$ is maximal delay and $\tau_{avg}\$ is the average delay. Then, the authors propose a new delay-adaptive learning rate scheme of a faster convergence rate of $ O\!\left(\sigma^2\epsilon^{-2}+ \tau_{avg}\epsilon^{-1}\right)$. This is the first time that asynchronous SGD becomes faster than the synchronous SGD.  The authors also discuss the case of of heterogeneous functions.
strengths_and_weaknesses: Pros:

+ This paper makes novel and significant contributions in asynchronous SGD for distributed and federated learning. The authors significantly reduce the reliance of the convergence on the maximal delay to the average delay, by leveraging the notion of concurrency. This decreases the worst-case impact of the communications between the workers.
+ The idea makes sense. The authors suggest that the average delay matters in determining the convergence rather than totally relying on the maximal delay.
+ The proofs are rigorous and presented clearly. I did not find major flaws.
+ The literature review is comprehensive and well-discussed. The contributions are well-positioned in the existing results. Readers can easily understand the novelty and contributions of this work compared with the existing works.
+ This paper is well-written. The paper is organised in a clear structure. 

Con:

- My concern is mainly about the proposed algorithm. The authors argue that this algorithm has advanced convergence rate but does not give any experimental results. The authors are encouraged to conduct experiments to verify this statement.
questions: The authors are encouraged to conduct experiments to verify the advantages of the proposed delay-adaptive learning rate scheme
limitations: No limitations and potential negative societal impact are identified, while the authors do not explicitly discuss this in the paper.
review_title: null

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: The authors provide the analysis of Asynchronous SGD algorithms in the homogeneous and heterogeneous regimes. First, in the homogeneous regime, they provide a better analysis of Asynchronous SGD and get better rates without additional changes in the original algorithm with a constant step size. Next, they omit the dependence on the maximum delay by exploiting the delay-adaptive learning rate scheme. Finally, the authors provide an analysis of the heterogeneous regime, where the dependence on the maximum delay is improved, or the dependence can be omitted under the gradient boundness assumption.
strengths_and_weaknesses: The paper provides very interesting and nontrivial results in a timely topic. Even the fact that the authors improved dependence from $O(\frac{\sigma^2}{\epsilon^2} + \frac{\tau_{max}}{\epsilon})$ to $O(\frac{\sigma^2}{\epsilon^2} + \frac{\sqrt{\tau_{max} \tau_{avg}}}{\epsilon})$ is a strong result for a NeurIPS publication. Besides that, the authors improved the convergence rates even further to $O(\frac{\sigma^2}{\epsilon^2} + \frac{\tau_{avg}}{\epsilon})$ using adaptive step sizes. The same order of improvements was done in the heterogeneous setting. 

I see that the dependence $O(\frac{\sigma^2}{\epsilon^2} + \frac{\tau_{avg}}{\epsilon})$ was obtained before by Cohen et al. "Asynchronous Stochastic Optimization Robust to Arbitrary Delays", but they use an alternative strategy with another hyperparameter that can be difficult to tune.

The proofs sound to me and I didn't find any major issues. But, I only checked the proof of Theorem 6 in detail.
questions: Minor problems:
1. It is better to check terms $\xi_t$ and $\xi_{t - \tau}.$ For instance, in Algorithm 1, I would expect to see $\nabla F(x^{t - \tau_t}, \xi_{t - \tau_t})$ because $\xi_{t - \tau_t}$ was generated at time $t - \tau_t.$
2. 640: The line says $\tau_{avg} \leq \tau_C.$ Does it hold for every $T$? Maybe, as in Remark 5, there should be some additional factor in the inequality?

Suggestions:
1. Recently, Mishchenko et al. prepared "Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays" paper. Can the authors kindly add some sentences where they describe the differences between the papers?

limitations: No
review_title: null

Meta-review: metareview: The paper studies the convergence of asynchronous SGD in the setting of distributed/federated nonconvex smooth optimization with . The first contribution of the paper is to tighten the existing convergence guarantees, improving the dependence on the delay parameter from maximum ($\tau_{\max}$) to the geometric mean of maximum and average delay ($\sqrt{\tau_{\max}\tau_{\rm avg}}$). The paper then proceeds to introduce an asynchronous SGD variant with delay-adaptive learning rate that further reduces the dependence to simply $\tau_{\rm avg}.$ On a conceptual level, the paper shows that asynchronous SGD is always faster than minibatch SGD. The main techniques based on active set/concurrency seem novel and are presented in a clear way. The paper is well written, has solid contributions, and is a good fit for NeurIPS. 
confidence: Certain
Decision: Accept