Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model

Summary

Consider the classical statistical risk minimization framework with stochastic gradients, and propose new lower bounds on the optimal time complexity. Also propose a new method Rennala SGD that attains the lower bound. This work makes the case for asynchronous methods. In particular, this work proposes a new oracle-based lower bound on the optimal convergence rate in time, rather than iterations, and develops an algorithm (essentially straggler-based SGD) that achieves this bound in the shared-system/parameter-server setting.

Strengths

**Significance** This work takes a step towards developing more practical asynchronous optimization methods, and providing convergence rates and complexity bounds that more closely reflect practical considerations of convergence time, rather than iterations. **Originality** The proposed method is not entirely novel (e.g., see Dutta et al., 2018 or related works on straggler-based SGD methods that ignore computation from stragglers), however the new lower bounds, problem formulation, and analysis are of sufficient novelty, to the best of my knowledge. **Clarity** The work is well written and easy to follow.

Weaknesses

Lacking empirical evaluations, the only such experiments are on quadratics, buried deep inside the appendix. While these plots are compelling, I would encourage the authors to consider small-scale numerical results on other machine learning workloads. Another weakness of this work is on assuming a fixed computation time for each worker. Such models are highly restrictive and impractical. I would encourage the authors to consider ways for extending their framework to arbitrary, but bounded worker delays. I would appreciate a discussion on how such lower-bounds (or the optimal method), may change if these bounds were overly conservative and long-tailed.

Questions

Please see my questions provided in-line above, in the weaknesses section.

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.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Limitations of the work are not adequately addressed. There are for instance, many assumptions that are taken for granted in the analysis that may limit the applicability of the findings to practical settings... namely the fixed delay model per worker, and the relationship between the batch-size S and the number of workers n. I am curious how findings would change in settings where S >> n or S << n.

Summary

This paper proposes a protocol that generalizes the classical oracle framework approach. Using this protocol, it establishes minimax complexities for parallel optimization methods that have access to an unbiased stochastic gradient oracle with bounded variance.

Strengths

- The motivation of this paper is clear. - The theoretical analysis seems sound.

Weaknesses

I am not an expert on this topic of this paper. 1. The challenge of theoretical analysis should be made more clear, which highly relates to the contribution of this paper. 2. The empirical study lacks. 3. The organization of this paper is strange. E.g., related work is located in 6.1, and conclusion section lacks, etc.

Questions

Please cf. weaknesses part.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

none

Summary

This paper studies time complexity of parallel stochastic optimization, establishes lower bounds, and proposes algorithms achieving matching complexity results.

Strengths

Based on my reading of the main paper (I haven't read the proofs), this is a solid theoretical work. The theoretical results improve widely used asynchronous SGD, and are even a bit surprising, especially the fact that ignoring some computations actually helps.

Weaknesses

General comments: - The organization of the paper is a bit reader unfriendly. The assumptions are mentioned at multiple places, starting with page 1, but are formally introduced almost at the end (page 8). This makes the reading tedious. Minor comments: - line 16, shouldn't the codomain of $f$ be $\mathbb R$ rather than $\mathbb R^d$? - line 39: $L, \Delta$ have not been introduced so far in the paper - Async. SGD (after line 52): step 2 gives the impression that only homogeneous data distribution across devices is considered in the paper. This is true for the main paper, but since the authors do have heterogeneous case results as well, they might consider reflecting that here. - Lines 98-99: "this approach is not convenient" Maybe giving a short intuition why (which becomes clear on the next page), would help the reader. - Typo in line 212

Questions

Doubts: - In (6), S_t is the set of indices that started computing gradients before time t. Shouldn't we consider k's which "finished" computation before t? - Line 205: what does it mean by the freedom to interrupt oracles? Questions: - As the authors themselves remark in line 237, Rennala SGD goes contradictory to the idea of using all stochastic gradients. In that case, have the authors studied how it performs in practice in comparison to async SGD, especially with heterogeneity? - In Theorem 7.4, we need a large batch size in the presence of sizable noise. Since in a lot of analyses, the ratio of learning rate and batch size is the crucial quantity, is it possible to choose $S=1$, and $\gamma = \Theta (\epsilon)$, and still get convergence? One would expect this to be closer to asynch SGD while achieving better rates, and performing better in practice. - I haven't looked at Appendix A, but looking at the heterogeneous result in Table 1, the lower bound and Malenia SGD complexity have no dependence on the heterogeneity term. How come? - The bound in (12) for when the workers start simultaneously: What is the explanation for this approach being slower?

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.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

n/a

Summary

This paper studies the minimax complexities of distributed asynchronous stochastic optimization methods. By extending the oracle framework previously used in the literature, it establishes new (lower) lower bounds for parallel optimization methods. Based on the insights from their proof, they propose a new algorithm meeting these bounds. Notably, it is provably faster than previous synchronous and asynchronous methods in the homogeneous case, which is verified experimentally.

Strengths

* This paper naturally extends the oracle protocol of previous work to cater for analysing parallel methods instead of sequential ones, which allows for a finer analysis of distributed methods. * Efforts have been made in the writing to explain the introduced novelties step by step, which greatly helps understand and position the contributions. * The insight taken from their new complexity proof that “ignoring stale gradients might actually help to converge faster” is interesting and highly relevant to the community, as it led to the development of a new state-of-art optimal method, which has provably and experimentally faster convergence rates than previous asynchronous algorithms in the homogeneous case.

Weaknesses

* Many notations are introduced, which makes the paper a bit cluttered and cumbersome to read at times. * No experiments comparing Renata & Asynchronous SGD to minibatch (synchronized) SGD are made to confirm the “provably better rates” claimed Section 8.

Questions

* Your model assumes fixed delays per worker: could your analysis also hold with stochastic ones? * You experimented with a fixed delay of $\sqrt i$ for worker $i$ (line 1163). Did you also experiment with real-life delays experienced naturally in the distributed asynchronous setting (as in Mischenko 2022 [1])? (For example, this would hint that your method also work with stochastic delays) * Did you experiment with other convex functions other than the one introduced line 1159, and did you consistently observe that Renata leads to better results than Asynchronous SGD, or is this highly dependent on the convex functions used? * Why Goyal et al 2017 [2] is cited line 45? **Typos :** * Line 212: our framework *is*. **References :** [1] Mishchenko, K., Bach, F., Even, M., andWoodworth, B, *Asynchronous SGD beats minibatch SGD under arbitrary delays*, In NeurIPS, 2022. [2] Goyal, P., Dolla´r, P., Girshick, R., Noordhuis, P., Wesolowski, L., Kyrola, A., Tulloch, A., Jia, Y., and He, K., *Accurate, large minibatch SGD: Training imagenet in 1 hour.*

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.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

*

Re: Rebuttal

I acknowledge having read the author response, which addressed my minor comments. I have no major issues with this work, and will maintain my recommendation.