Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper shows that there exists classes of quadratic objectives where single shuffling or random reshuffling cannot offer improvements over SGD with-replacement sampling unless the number of passes exceeds the condition number of the problem. The paper supplements these lowerbound constructions with matching upperbounds that apply to the class of functions considered in their lowerbound construction. In addition, the paper offers simulations supplementing their theoretical results.
main_review: I found the paper to be an interesting read and the technical results appear correct. The results appear to have little to do with how SGD is run in practice, which potentially explains why the result appears to be at odds with running SGD with and without replacement in practice -- from my experience, SGD with random reshuffling dominates with replacement SGD in terms of its convergence behavior. 

One discrepancy can be elaborated as follows: The construction used in this paper is different from the multiplicative noise oracle view of analyzing SGD, where, we do not see a full view of all eigendirections of hessian of the objective when we sample one component of the finite sum. In the construction used by this paper, we get a full view of the hessian based on the construction used say in equation (1) - you could take the second derivative of this function and you get a full rank second derivative matrix. This hardly resembles how SGD is run in practice. See for example, the paper of Bach and Moulines (2013), Defossez and Bach (2015) - which work with least squares with a multiplicative noise oracle. In these cases, we get a rank-1 view of the hessian if we sample one term in a finite-sum. 

Moreover, note that when working with the multiplicative noise oracle, the matrix products obtained in SGD recursions do not commute with each other, unless, we deal with specific class of problems where each of the d-dimensions are independent of each other and we can decouple the recursions into a single dimensional recursion. Even in this case, note that we do not receive a full view of the Hessian of the problem, and that reflects more appropriately how SGD is run in practice for finite sum problem instances faced in machine learning settings. Note that in order to get a full view of the hessian, one may require to use a mini-batch size, that in some cases can be as large as the condition number of the problem, in order to see spectral concentration kick in, and for the empirical covariance matrix to start resembling the true Hessian.

1. Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n) - Bach and Moulines (2013)
2. Averaged Least-Mean-Squares: Bias-Variance Trade-offs and Optimal Sampling Distributions - Defossez and Bach (2015)

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies lower bounds for without-replacement fixed-step-size SGD  (both single shuffling and random reshuffling) for the finite-sum optimization problem with an attention to dependence on the condition number of the problem. Their primary result is to prove a lower bound on the optimization error (realized by a convex quadratic construction) that suggests that unless the number of epochs $k$ is significantly larger than the condition number, neither single shuffling nor random reshuffling variants of without-replacement SGD outperform with-replacement SGD (previously, upper bounds for the with-replacement variants of SGD were considered to beat without-replacement SGD since often results did not take the condition number into account in the bounds). Moreover, they show their lower bound is tight with respect to a class of quadratics which includes the lower bound instance, suggesting that the analysis is somewhat tight. 

The restriction on $k$ being large in order for without-replacement SGD to be more efficient is problematic for practical justification for using without-replacement SGD, since if $k$ is large enough, at some point one will prefer to use methods like conjugate gradient instead of using SGD, thus making the regime in which without-replacement experiences gains irrelevant to practice (since there is a better algorithm).
main_review: This paper is very well-written and clear, identifies a well-motivated, interesting question and a clean answer. It nicely builds upon previous work in the sub-area, provides improvements on pre-existing analysis, and challenges existing wisdom by highlighting the importance of the condition number parameter. I read the lower bound proofs and they seem correct.  I didn't check the (restricted upper bound) proofs as closely, but in my opinion (though requiring a lot of technical calculations), the restricted upper bounds were not as important to the results. The exposition was also clear.

One thought: It would be nice to say earlier on (somewhere in Section 3) an intuitive reason why the random reshuffling without-replacement lower bound requires three dimensions in the lower bound construction instead of two. (You are using one dimension to get the $1/nk^3 $ dependence, and the other to get the $1/(nk)^2$ dependence, but a little more insight into why the this construction has that dependence fall out would be nice.
limitations_and_societal_impact: I didn't see anything that's related to societal impact that needs to be addressed. 

The authors were very clear about the limitations of their results,  as well as the opportunities for future work. The limitations of their results are reasonable enough for acceptance.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: ## I update my score after authors' rebuttal
I thank the authors for their detailed rebuttal. I now understand better why and how the results can be useful. I hope that the authors would do a great job of fixing some of the confusing parts in their work, in particular about the exact novelty of their paper, most notably regarding the conditioning. As promised, I thought more about this work and decided to increase my rating from 4 to 5.
####

This paper presents improved upper and lower bounds for shuffling-based algorithms, which are without-replacement variants of SGD. In particular, the authors consider Random Reshuffling, which reshuffles the functions at each epoch, and Single Shuffle that reshuffles them only once at the very start. For both methods, the authors provide bounds that take into account the conditioning number.

The abstract of the paper about the prior work ignoring the problem geometry looks like a big overstatement, while the title seems to claim something already known from prior literature. Thus, I find the results to have limited motivation, even though both upper and lower bounds are of some interest. Another small flaw of the upper bounds is that they are stated for quadratic objectives.
main_review: I am very confused by this work. On the one hand, it has new results that contribute to the theoretical development of shuffling-based methods, and it gives new guarantees for both RR and SS. On the other hand, the motivation for these guarantees is unclear. First of all, the works of (Ahn et al.) and (Mishchenko et al.) do provide conditioning numbers in their guarantees. Secondly, the message that RR/SS is only better after some number of epochs is essentially already known. It follows from the existing upper bounds of (Ahn et al.) and (Mishchenko et al.) and existing lower bounds of (Safran and Shamir) and (Rajput et al). All of these bounds show that RR/SS is better eventually but not immediately.

I am also not sure why the authors are so interested in proving upper bounds for quadratic objectives. My understanding is that RR/SS is not used as a solver for quadratic problems but rather is a method widely adopted for training neural networks. From that perspective, it could be much more interesting if the authors studied the nonconvex settings where fewer guarantees are known and little is known about the tightness of existing bounds.

### Small comments
Why not provide the new results in the summary table?
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper compares the efficiency of using different variants of stochastic gradient descent to find the minimum of a function that is the sum of multiple convex functions. It focuses on the case where the minimum of the function is dramatically flatter in some directions than in others. More specifically, it compares using a random sample at each time step, going through the samples in a fixed cycle, and repeatedly going through the entire list of samples in a random order. The conclusion is that the more complicated versions do not significantly outperform regular stochastic gradient descent unless the number of timesteps is unreasonably large.
main_review: The paper notes that comparable analyses have been carried out before, but that they treated parameters other than $n$ and $k$ as being constant, and generally gave results less favorable to SGD. This paper's version of the comparison appears to be new, although I am not familiar enough with the literature to be sure.

The paper's organization is good and the proofs are generally solid. However, the functions used for theorem 2 appear to violate assumption 1 due to half of the $f_i$ having no $x_3^2$ term.

This appears to make a useful contribution to the question of how one should try to minimize a convex function chosen from a family by arguing that the more complicated methods of choosing what sample to use when do not necessarily make a useful improvement over straight SGD.

----------------------------edit-------------------------

I stand by my original assessment.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: The writing in this paper is clear. It is well-motivated and informs theory being actively developed in its area. The paper's lower bound accounts for the condition number where previous ones did not, and in doing so significantly strengthens the known conditions under which the community can hope to guarantee, in general, that without-replacement SGD outperforms standard SGD.

Three of four reviewers support accepting this paper. One reviewer's recommendation is just below the acceptance bar, but without a particularly strong argument against acceptance. Some of the criticism from this reviewer is around wording in presentation and motivation. I encourage the authors to consider these as suggestions in their final revisions.

Lower bounds are valuable in a community's pursuit of theory and are technically challenging to establish. Several constructive comments from reviewers have been acknowledged by the authors and I believe will improve the writing and clarity further. Together with sufficiently many positive reviews, I recommend it for acceptance.
Decision: Accept (Spotlight)