- Rating
- 4
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3(+1)
Read review
Paper summary
The paper provides matching lower and upper bounds for SGD with random shuffling (they call RR) for strongly convex and smooth objectives. This extends recent work by Safran & Shamir that only held for quadratics (with commuting Hessians). The paper also considers the case where the individual loss functions are convex, or not. Perhaps the main take away is that RR can be theoretically faster than SGD with iid sample for the large epoch setting, where epochs$> $ condition number.
Overall, the paper is well written and clear. Its contributions match exactly the contents, the bibliography is adequate, and I think there is some interest in understanding SGD with random shuffling, since this is what is done in practice when taking multiple passes over the data. Presenting also careful matching lower bounds really closes this question around analysiing RR for strongly convex. Finally, I've also sampled the proofs in the appendix, and find they too are written to a high standard, one for which I could easily follow the proofs. As such, I recommend accepting the paper. I have only minor questions and comments to make.
[SGD-gen] SGD: General Analysis and Improved Rate, Robert M. Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, Peter Richtarik 2019 / International Conference on Machine Learning (ICML)
Critical strengths
-
Filling in a clear gap in the analysis of SGD with random shuffling in the smooth strongly convex case
-
Very clearly comparing this against SGD with i.i.d sampling
Critical weaknesses
The only weakness is really the standard asks for "more results", so I could always ask for more (what about the convex but non-strongly convex setting?), or "more impactful" since this is a specialized work for a rather specialized audience. But I do not think these are grounds for rejecting the paper.
Questions for authors
After Response The authors have answers all my question regarding unification or their results and the reliance on component wise convexity, and more. I'm satisfied with these answers, and maintain my high score (with a bit more confidence in my score)
I have only two main questions, and a few minor ones below.
Q1: With or without component convexity. I'm confused about the need for assuming component wise convexity for the SGD results in Proposition 3.3 and 3.4. First, the two results are very similar (just a bigger burn in phase of for Prop 4.3).But also, I know that Proposition 3.3 also holds without strictly requiring that the componet functions be convex, see Theorem 3.2 in [SGD-gen]. This version of the proof assumes that a "expected smoothness" condition holds, for which the components function being convex and smooth is a sufficient condition. But there are also non-convex functions for which this condition holds, though I'm unaware of significant class of smooth functions (other than component wise convex) for which expected smoothness holds. You might also be able to loosen the assumptinos for you Theorem 3.2 (A.3 in appendix) by simply making (19) the assumption, as opposed to the consequence of component-wise convexity and smoothness. By doing this you might find that your resulting theorems holds for other functions classes. Furthermore, the proof of Proposition 4.3 (A.5) also requires only assuming expected smoothness, instead of the bound just above equation (12). In this sense, the proof of Proposition 3.3 and 3.4 could be unified using this expected smoothness assumption, the two results follow as mere corollaries,
Q2: Comparing theory to practical multi epoch training. This is really a mix between a question and suggestion. Given how you show RR can be theoretically faster in the high epoch as compared to condition number regime, it would be interesting to at least take some of the smaller classification tasks and compare the number of epcohs to condition number. Such a logistic regression, with L2 regularization, and standard data sets from libsvm. This would highlight what your theory says in practice. It would maybe slightly strengthen the paper, but it also might not be insightful, or useful for this theoretical work (so take this as a light suggestion)
I also have some very minor point:
- Line 81: "RR can retain a constant fraction of its initial square distance when..." I couldn't make sense of this sentence when I first read it, but later understood after reading Proposition 3.1. I think it needs to be re-written. Maybe "The iterates of RR are bounded away from the solution by D/\sqrt{8}, where D is the initial distance?"
- Line 155: This quantity is sometimes referred to as gradient noise, see Garrigos 2023
- Proposition 3.1: Wouldn't it be better just to state that ? Using this approx greater than for a constant bound is a little bit odd, since the "approx" bit could sometimes refer to dropping constants.
- Proposition 3.3: First, I was a bit confused if this proof was taken from Nguyen 2018 Theorem 2? If so you should state Proposition 3.3 [Nguyen 2018 Theorem 2]
And explain that you repeat the proof for convenience. If it's only adapted from Nguyen 2018 Theorem 2, then I think this is ok. The same question holds for Proposition 4.3
- You somtimes use or to denote the initial distance
3 comments
Minor Points
Q3-1. We now state the lower bound explicitly as .
Q3-2. We have replaced the term “component-gradient variability” with “gradient noise”.
Q3-3. We originally used for notational consistency with the upper bounds. We agree with the reviewer that writing with an explicit constant is clearer, and following the suggestion, we have revised the statements of Proposition 3.1, Theorem 4.2, and Proposition 4.4 accordingly.
Q3-4. The upper bounds in Propositions 3.3 and 4.3 are obtained by adapting the analyses underlying Theorems 2 and 4 of Nguyen et al. (2018), respectively, to a constant stepsize scheme. The proofs share the same backbone, but differ in how the recursions are unrolled to accommodate a constant stepsize. Since these bounds are not direct restatements of Nguyen et al. (2018), we describe these as adaptations in the text instead of using a heading such as “Proposition 3.3 [Nguyen et al., 2018, Theorem 2]”.
Q3-5. We now use consistently.
We hope our responses and revisions address your questions and suggestions. We would be happy to provide further clarification or discuss any remaining points.
Thanks
Thanks for addressing all my questions. Ok, interesting that expected smoothness can unify these propositions, though not clear that this would actually improve the exposition of your results. In particular, because your proof still rely directly on assuming component-wise convexity, there are probably no gains in exposition in using expected smoothness to unite these propositions. Also thank you for the additional controlled logistic regression experiments. I'm satisfied with your answers, and will increase the confidence I have in my score.
We sincerely thank the reviewer for the thorough reading of our paper. We particularly appreciate the detailed comments on our assumptions and proofs, as well as the suggestions for experiments and improvements to the presentation. Below, we address the two main questions and the minor comments.
Q1. Could Propositions 3.3 and 4.3 be unified using expected smoothness instead of component-wise convexity?
Could we also remove component-wise convexity for RR by directly assuming Eq. (19)?
Q2. Can we verify a faster convergence of RR in high epoch as compared to condition number regime in a simple but practice-aligned experimental setting?