Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper improves the iteration complexity to get $\epsilon$ small gradients for smooth non-convex functions using SGD with delayed gradients. This setting, in particular, captures asynchronous distributed SGD. The previously known best algorithm [1] accumulates error feedback to provide a $\sigma^2/\epsilon^4 + \tau_{max}/\epsilon^2$ rate, where $\tau_{max}$ is the maximum delay in any update. This can be catastrophic in cross-device federated learning with edge devices, where a device gets disconnected for multiple rounds, and then sends its gradient for the update. 

This paper deals with such a scenario in a very simple manner, by measuring the distance between the current iterate and the old iterate at which the gradient was computed, and making the update only if it is smaller than a threshold value. This algorithm is aptly called *picky SGD*. Surprisingly, this removes the need for error feedback and is able to guarantee a $\sigma^2/\epsilon^4 + \tau_{avg}/\epsilon^2$ rate where $\tau_{avg}$ is the average delay over all the rounds. Picky SGD with a different threshold also offers state-of-the-art convergence rates for convex smooth functions, with the dependence on the maximum delay changed to the one on average delay.

The authors also study the effect of sampling the delays from distributions with different levels of variance in their experiments. The results demonstrate that picky SGD requires comparable or fewer steps to reach a fixed level of accuracy than vanilla asynchronous SGD. This is attributed to the fact that picky SGD tolerates a much larger step size than asynchronous SGD.



**References**

[1] Stich, Sebastian U., and Sai Praneeth Karimireddy. "The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication." arXiv preprint arXiv:1909.05350 (2019).
main_review: This is a well-written paper, with a clear description of the goals, contributions, results, and proof sketch. The proposed algorithm is in fact simpler (albeit at the cost of storing the past iterates) than the error-corrected SGD but still improves upon its convergence guarantee, making the upper bound *data-dependent*. I have some concerns though, and I would be happy to increase my score if they are resolved. 
 
1) Can the analysis be extended to a more general noise model like the strong growth model as in [1]? 

2) In the theoretical guarantees the paper compares to error-correcting SGD. However, why was it not included as a baseline in the experiments?

3) It is useful to see the magnified tail of the plot, but it might make more sense to plot the y-axis on a log scale. Further, the experiments should be repeated multiple times to kill some noise in the curves and understand the variance of these algorithms. In fact, it would be good to include repetitions for the same delay schedule as well as different delay schedules sampled from the same distribution. 

4) It is not clear how the algorithms stop making updates in the experiments. Were they stopped after reaching a particular target accuracy? It doesn't seem to be the case looking at the figure. In setting (D) SGD stops earlier and vice versa for setting (C).  

5) While picky SGD is simpler to analyze and discuss in theory, it has two limitations in practice. First tuning the for the threshold $\epsilon/2\beta$, and second storing the past iterates only up to some point in history. How to go around these issues in practice? It is important to show how robust the algorithm is to each of these choices. Also, since memory costs can often be the bottleneck, some wall clock time experiments would also be useful, again over some reasonable range of the tunable parameters. These limitations can make EC-SGD [1] a better choice in some settings because we need to tune it as much as usual SGD. 

**Typos**

1) L58 previous art -> previous state of the art

2) L283 SGD -> SGD's

# Final Verdict

I liked this paper overall except for some minor concerns and suggestions. They have been addressed, and the authors have promised to add some important discussions in the revised version. In light of that, I am improving my score. 


**References**

[1] Stich, Sebastian U., and Sai Praneeth Karimireddy. "The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication." arXiv preprint arXiv:1909.05350 (2019). 
 

limitations_and_societal_impact: Some experimental limitations as mentioned in the main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper gives an alternative to SGD, called picky SGD, for stochastic optimization with delays. While Stich & Karimireddy proved that SGD was robust to delays as long as the maximum delay is controled, here picky SGD is proved to be robust to much larger delays, as it requires only the average delay (and not the maximum delay) to be controled. This is supported by both theoretical convergence to a stationary point (in the non-convex case) or to a minimum (in the convex case) and with simulations with artificially introduced delays. 
main_review: The authors expose clearly their results. The simulations show an important improvement of picky SGD over SGD. However, the code is not provided, thus reproducing the experiments would be quite tedious. 

As the central objective of the paper is to replace the dependence in the maximum delay by the average delay, it is natural to ask what empirical evidence do we have that in practical distributed systems, the distribution of delays is heavy tailed. Do you have experiments or references supporting this? The simulations are for heavy-tailed delays that are introduced artificially, thus we could wonder if such delays occur in practice. 

The paper presents their result as a variation over a result of Stich & Karimireddy. However, this papers studies more generally non-uniformly bounded noises (their assumption 3). Stich & Karimireddy explain at great length why this is more relevant to machine learning practice. However, the authors of these papers restrict themselves to uniformly bounded noise, with no comment on this restriction. Could you elaborate? 
Also, while the theoretical result is well compared with the one of Stich & Karimireddy, the difference in the proof technique is not commented. Is it a variation over the same proof technique? Does picky SGD require completely different techniques? 

Finally, I did not succeed in understanding the proof of Theorem 1. It might be only miskates on my side, but I think I need a clarification from the authors.
Mostly, I do not understand the paragraph of l. 159-164. 
- What does it mean for the algorithm to "fail"? Does it happen when the algorithm has not found a critical point in a given number of iterations? What is this number of iterations? 
- I do not understand the statement "the guarantee of Theorem 1 is valid for this variant if and only if it is valid for the original algorithm". Is it proved somewhere? 

In my attempt to understand the definition of "fail", I read the proof of Lemma 4 (I thought that I could understand the statement from the proof). In this proof, two lower bounds are derived for U_{2\tau}. How can you conclude on an inequality between those two bounds?
Also, could you detail the application of Markov inequality? As the delays are arbitrary (and not random), U_{2\tau} is deterministic and I do not understand how Markov inequality intervenes here. 


Minor comments:
- l.70: was it necessary to know \tau_max in the work of Stich and Karimireddy?
- why do you assume the function to be non-negative?
- l.151-155: when amplifying, how do you know which of the final points is successful? Gradients are stochastic thus is it not obvious to test if a point is an approximate critical point.


----------- 
I increased my grade after the rebuttal, see below an updated review. 
limitations_and_societal_impact: The articulation with the result of Stich & Karimireddy is not detailed enough. I gave suggestions for improving this in the main review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the problem of distributed stochastic asynchronous optimization, in which workers send delayed stochastic gradients to a server. The focus is on non-convex smooth objectives, although results for convex objectives are provided in the supplementary material. 

Standard asynchronous distributed SGD algorithms are first discussed, and the authors highlight that their step-size (and thus, also their iteration complexity) depends on a bound over the maximum possible delay over all iterations. Instead, this paper introduces an algorithm that does not require to know this bound, and only depends on the average observed delay.

This algorithm is called Picky-SGD, and its main difference with standard delayed SGD is that the update is only performed if the delayed iterate is close enough to the current iterate. Theoretical results are then given to show that Picky-SGD achieves the standard complexity results for these problems, but replacing the maximum delay by the average one. The proof is then presented in details, and a set of experiments is given to illustrate the superiority of Picky-SGD over delayed SGD. 

main_review: The introduction is very well written, quite thorough, and clear. The contributions (both the algorithm and its analysis) are interesting contributions to this field, and could be leveraged beyond this setting. 

The global approach is very intuitive but also quite efficient. Standards algorithms assume a bound on the maximum delay $\tau$, and they reduce the step-size accordingly so that $x_{t - \tau_{\max}}$ is never too far from the current iterate $x_t$ even in the worst case, so that the gradient at $x_{t - \tau_{\max}}$ remains relevant. On the other hand, Picky-SGD directly verifies a condition on $\||x_{t - \tau} - x_t\||$ at each step, and thus avoids having to lower the step-size too much. 

Although this seems conceptually simple, work is then needed to show that the algorithm does not discard too many gradients and converges fast enough. 

In Picky-SGD, the knowledge of $\tau_\max$ is replaced by the knowledge of a target accuracy for the algorithm. Yet, this is still a hyperparameter to tune, and generally an extra one compared to standard delayed SGD since the bound on the delay only appeared in the step-size, which is generally tuned anyway. I believe that the authors should be significantly more straightforward about this limitation, since it is not so clearly stated anywhere. 

Similarly, it is expected that the Picky SGD algorithm outperforms standard delayed SGD since it recovers it when taking $A \rightarrow \infty$ (with the notations of Appendix C.2.2), which corresponds to accepting all iterations. It is good to show that introducing this extra degree of freedom via the acceptance threshold actually helps, but it seems to be at the cost of extra tuning. Again, I believe that this paper would benefit from highlighting this more clearly. 

I would be interested in the practical performances of Picky-SGD in the convex / strongly convex cases, in which the theoretical parameters can generally be used (more than in the non-convex case at least), and so in which SGD and Picky-SGD could be compared in a (almost) tuning-free setting. I do not specifically ask for this kind of experiments in the rebuttal though.    

Other comments:
I believe that there is a typo in the proof of Lemma 4 (Line 188) in that Markov Inequality should guarantee that $U_{2\tau} \leq T/2$ (and not the other way round). This is consistent with the statement of line 193. 

The reference following reference could be relevant:
Hannah, Robert, and Wotao Yin. "On unbounded delays in asynchronous parallel fixed-point algorithms." Journal of Scientific Computing 76.1 (2018): 299-326.
limitations_and_societal_impact: No foreseeable societal impact
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a distributed SGD algorithm, called Picky SGD, for asynchronous implementation of SGD with multiple workers and arbitrary delays. Compared to prior works which analyzed a plain SGD algorithm, the main advantage of picky SGD is that it has a tighter complexity bound of $O(\sigma^2/\epsilon^4 + \tau_{avg}/\epsilon^2)$ instead of $O(\sigma^2/\epsilon^4 + \tau_{max}/\epsilon^2)$ as in the prior work. 
main_review: As mentioned above, the main contribution of this paper is a new algorithm with improved complexity bound with respect to the delays in the asynchronous algorithm. The main idea is to perform a selective SGD update only made when the transmitted stochastic gradient is computed from an iterate that is "close" to the current one at the server. The proof seems to be follow from standard analysis of distributed SGD (and actually SGD in general). Numerical experiments seem to indicate a better performance of the proposed algorithm compared to standard SGD. 

The reviewer has the following comments:

- The reviewer is concerned with the practicality of the proposed algorithm and the theoretical result provided in the study. 

First, it should be noted that at every update, the worker has to send both $x_{t-d_t}$ and $g_t$ to the server which involves a doubled communication cost. In addition, given this additional requirement on the communication protocol, it is unclear if the proposed algorithm can be extended to be used with compression, e.g., as studied in [25]. 

Second, the current proof in the paper only analyzes the time complexity with a success probability of greater than 1/2. After Theorem 1, it is stated that this success probability can be "amplified" to $1-\delta$ for any $\delta > 0$ by repeating the algorithm with $T$ iterations and "running through a point with gradient norm $\leq \epsilon$". Such scheme appears to be impractical since it involves checking the gradient norms of the iterates, e.g., a distributed system where the gradient is only posessed by the workers and the latter can only be accessed through a stochastic oracle. In general, such existence proof for an $\epsilon$-stationary point is in contradiction to the stochastic gradient and distributed optimization setting, as it may result in an impractical scheme.

As a minor point, it should be noted that the algorithm requires an estimate of $\beta$ and the desired $\epsilon$ as an input to run the algorithm, which are hard to determine-a-priori in practice. 

- In the convergence analysis, there are several confusing technical statements which require further clarifications:

-- On page 5, it is stated that $I_t = 1$ implies $|| \nabla f(x_s) || \geq \epsilon$ for $s=1,...,t$. Why is this true? This statement doesn't seem to hold in general. 

-- In the proof of Lemma 4, it is not clear what does it mean by "By Markov Inequality, $U_{2\tau} \geq T/2$". To the reviewer's best knowledge, the Markov's inequality bounds the probability of the event that a certain non-negative r.v. is greater than a certain constant. Yet in the statement of Lemma 4 nor in the proof of the lemma, there is no specification of any random event nor its probability. Perhaps the reviewer has missed something from the lemma's statement or from the proof, but at the moment I am unable to deduce the said statement. 

-- Also in the proof of Lemma 4, it is stated that $U_{2\tau} \geq T/2$ and $U_{2\tau} \geq T - k(1+2 \tau)$ imply the statement $k \geq T/4(\tau+1)$. Again, the reviewer fails to see why this hold. It seems that the statement would hold instead if $U_{2 \tau} \leq T/2$. 

-- The proof of Lemma 3 applies Lemma 2. However, the independence between the stochastic gradients and the iterates should be handled carefully. In particular, Lemma 2 requires $x$ and $N$ to be independent random variables. This may not be the case when the lemma is applied in the proof of Lemma 3. Particularly, the latter involves $x = x_t$ and $N = g_t - \nabla f(x_{t - d_t})$ which may not be independent from each other. 
limitations_and_societal_impact: There isn't any potential negative societal impact. The limitation/suggestions for improvement have been discussed in the main review above.
review_title: null

Meta-review: This paper studies the convergence of gradient descent with delayed updates. While most prior results depended on a parameter corresponding to the largest encountered delay, this paper derives convergence analysis depending on just the average delay.
The presented algorithm does not need to know the average delay parameter beforehand.

The reviewers found this an overall solid technical contribution and recommend acceptance. 

The authors are strongly encouraged to take the reviewer's feedback into account when preparing the revision, as a few concerns remain:
- reviewer v3Nq spotted some inaccuracies in the proofs, which the author's promised to fix
- while indeed prior methods need 'to know' the maximum delay to set the theoretical step size, in practice the tuning is limited to a single parameter only (the stepsize). The proposed scheme has two hyperparameters (stepsize and threshold), and the reviewers concerns on practical benefits seem justified. It would be great if these comments could be addressed diligently in the revision.

Additionally, I would encourage the authors to comment on the concurrent work [[Aviv et al, Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays, ICML 2021](http://proceedings.mlr.press/v139/aviv21a/aviv21a.pdf)] published at ICML earlier this year. It would be great to explain the key differences and similarities of the proof techniques and results to the readers.

Decision: Accept (Poster)