Summary
This paper addresses the problem of accessing large datasets in an efficient manner without compromising on the accuracy of SGD. In particular, for datasets stored on the cloud in homogeneous shards, the authors try to address the performance degradation of CorgiPile, which is an online shuffling algorithm. The authors design an extra offline shuffling procedure, which can be implemented without requiring extra storage, that diversifies the examples seen during the training. Depending on block sizes $b$, the provable speed-up relative to CorgiPile can be much larger than 1. The authors then empirically study the test accuracy accuracyon standard benchmarks of training ResNet on CIFAR100 and ImageNet, and, in addition, the test loss when training on a proprietary dataset.
Strengths
1. The problem of efficient data partitioning and loading has a high potential. If we can achieve an improvement on these steps, it might affect all of large-scale deep learning.
2. The authors gave a theoretical justification for why their method can be better and quantified the speed-up.
3. There seems to be almost no downside (other than some extra work before training) to the proposed shuffling procedure.
4. The method is tested empirically on real-world problems.
Weaknesses
1. The assumptions for the theoretical analysis do not look reasonable. While SGD without replacement has been studied with various assumptions, state-of-the-art results (convex and nonconvex) rely only on smoothness and bounded variance. This work, on the other hand, requires bounded gradients and Lipschitz Hessians. It seems that the reason is that the authors used the suboptimal theory of Xu et al. (2022a).
2. The experiments are a bit limited (only vision models) and the authors report only a single random seed.
3. I do not see any empirical evaluation of how much time (relative to the whole training time) we can save by using Corgi2 instead of shuffling the data once before the training.
## Minor
The abstract ends with ". paragraph."
"and Nguyen et al. (2022), where" -> "and (Nguyen et al., 2022), where"
"illustrate a a qualitative" -> "illustrate a qualitative"
I found Figure 2 to be rather confusing than helping, I was particularly confused as to where Sample 7 came from and what black color means.
"to minimize an average of functions" -> "to minimize the average of functions"
"Sample an example $f_i$ from the dataset, where $i$ is selected uniformly at random." Since you're talking about running SGD in epochs, $i$ should not be selected uniformly but rather it should be sampled without replacement until we process the full dataset. Otherwise, epochs shouldn't be mentioned here.
"left hand side" -> "left-hand side"
I was completely unfamiliar with the name "Bienaymé’s identity" for the variance of the sum, I'd suggest the authors clarify its meaning in the text or simple write the identity there
The identity (ii) on page 6 is missing a "." at the end
Theorem 2, "$F(x)$ are" -> "$F(x)$ is"
"While scenarios where this modification is useful may very well exists" I did not understand the meaning of this sentence
"in section 2" -> "in Section 2"
Please fix the references, for example, "Pablo A Parrilo" -> "Pablo A. Parrilo", "sgd" -> "SGD", add the name in "S Kocherlakota", etc.
The punctuation in the appendix is currently missing
Questions
1. Why you didn't run CorgiPile on the proprietary dataset?
2. I might be mistaken, but it appears to me that the requirement to sample with replacement to provide a theoretical guarantee can be actually lifted. In particular, using Lemma 1 in (Mishchenko et al, "Random Reshuffling: Simple Analysis with Vast Improvements"), you can directly bound the variance of the sum without replacement. This should resolve the issues mentioned in Section 5.
3. Can the authors measure the empirical speed-up achieved by using Corgi2 instead of full shuffle?
Rating
6: marginally above the acceptance threshold
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.