- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies asynchronous SGD, an variation of SGD in which stochastic gradients have delay. The authors focus on a setting where delays may be sample/data-dependent, making the analysis and convergence harder. Vanilla Asynchronous SGD is modified using first momentum and yielding a perturbed iterate analysis, while a second momentum is then added to obtain better rates.
Critical strengths
- The setup is very interesting: delays should indeed depend on samples. There are harder and easier ones, for instance if samples are generated using simulations (in RL applications for instance): easy ones will be always faster. It is also a difficult problem.
- The paper is very easy to follow: assumptions and theorems are clearly marked and assessing the contributions is facilitated.
- Although the analysis was not checked by the reviewer, it seems that the analysis extends the perturbed iterates analysis of Mishchenko et al. 2022 to momentum: the difference between the virtual sequence (without delays) and the one with delay can be written similarly. Momentum enables to not have to use delay-dependent online stepsizes.
- The double-momentum algorithm obtains better rates than all previous works in the data-dependent delays setting.
Critical weaknesses
There are no major weaknesses, since the setup is clearly motivated and formalized. However, my main concern is that it seems that delay-dependency is only handled by assuming bounded gradients. This assumption is strong, and in the results it means that dependence is made worst-case. One would wonder if there could be an in-between, since here the result is robust to adversarial dependence. Since the dependence is not adversarial (in most settings), different assumptions than bounded gradients (Markovian dependency ? etc) could be used and their impact could be quantified.
Questions for authors
Could the authors comment on the above comment on the bounded gradient assumption?
2 comments
I thank the authors for their answers, and maintain my score.
Thank you for the thoughtful review. Your RL example captures the motivation for our work well, and we're glad to read that you appreciated both the fixed-step momentum results and the improved rates from double momentum.
Regarding intermediate forms of data-delay dependence, we thank the reviewer for raising this great question. We believe that sharper guarantees are achievable under suitable assumptions on the interaction between samples and delays. Exploring this requires characterizing how the interaction between samples and delays affects the pending-gradient contributions, then incorporating that structure into our analysis of the discrepancy bt from ideal momentum (Lemmas B.5 and C.6). An interesting point is that our framework already handles both endpoints: it achieves tight data-independent rates and the best-known data-dependent guarantees under their respective assumptions. This suggests that the same approach may also yield refined guarantees for intermediate regimes. Establishing how the rates improve under more favorable dependence, and whether these rates are optimal, is indeed an interesting direction for future work.