Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: This paper considers the problem of minimizing the sum of a differentiable loss function over a set of examples and
builds on the observation by Lu et al. that convergence can be sped up compared to randomized reshuffling by choosing a permutation that minimizes the average gradient error (defined in equation 2). The authors make the following sequence of contributions:
* Section 3: Minimizing the average gradient error is shown to be equivalent to the herding problem in which the goal is to return an ordering of a sequence of vectors such the maximum deviation of the partial sum from the average is minimized.  The authors show that performing herding with a greedy ordering based on the stale gradients from the previous epoch as proposed by Lu et al. can underperform random reshuffling.  However, if herding is performed properly (i.e. if a constant bound is achieved for the herding objective), this ordering will outperform random reshuffling.
* Section 4: Up to this point, the herding methods proposed require storing a gradient for each example which incurs a large amount of memory overhead.  Vector balancing is presented as an online method which can be used to perform herding.  In short, each vector is assigned a sign as it is viewed in a streaming fashion and then a reordering is performed based on these signs (Algorithm 3).  Applying this procedure multiple times (each of which requires a pass through the gradients) can achieve the desired bound for herding.
* Section 5 + 6: Two remaining challenges are considered: how to center vectors when they are observed in a streaming fashion and the fact that without storing the gradients one can only perform the balancing-reordering routine once per epoch. Solutions are presented and shown to be sufficient to obtain essentially the same convergence rate as proper herding; the full algorithm is named SGD with online gradient balancing (GraB). The advantage of the data order produced by GraB is demonstrated in training for multiple machine learning applications.

Yucheng Lu and Si Yi Meng and Christopher De Sa. "A General Analysis of Example-Selection for Stochastic Gradient Descent" ICLR 2022. https://openreview.net/forum?id=7gWSJrP3opB
strengths_and_weaknesses: Strengths:
* The paper makes a solid contribution to an important problem in machine learning.
* The development of an algorithm which can find provably better data permutations without storing all the gradients from the previous epoch enables the scaling of such techniques to large-scale problems.
* The paper is well-written and the flow of ideas is generally easy to follow.

Weaknesses:
* The theory and experiments consider a constant learning rate whereas the majority of modern neural network training utilizes a learning rate schedule with learning rate decay towards the end and possibly learning rate warmup at the beginning.
* I think the experiments would be strengthened by including experiments on CIFAR-10 with a more recent architecture than LeNet, e.g. ResNet-20 which achieves a much higher test accuracy. 

Comments:
* For clarity, it might be worth explicitly stating that when connecting the herding objective (eq. 3) and the average gradient error (eq. 2) you are presumably using the relationship $||\mathbf{x}||_{\infty} \leq ||\mathbf{x}||_2$. 

I did not thoroughly check the proofs provided in the appendix.
questions: (1) In Theorem 1, the convergence rate is written in terms of the $\ell_2$-norm of the gradient squared averaged over epochs.  Is there a reason this isn't written in terms of the minimum over epochs?

(2) Could you comment on what it would take to extend your results to optimization with a learning rate schedule? Is this easier in the case where you change the learning rate in a step-wise fashion rather than something like cosine decay?
limitations: I did not see a discussion of limitations of the paper.  I would consider the most relevant discussion to be what common changes to the optimizer (e.g. momentum, learning rate schedule) would be challenging to adapt your theory to?
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies a herding procedure applied for finding better permutation of dataset for Random Reshuffling algorithm. Authors firstly provide explanations of more illustrative but not practically effective algorithm. Then they provide Gradient Balancing technique, which still has the same properties of herding procedure but it is better in practice. Gradient Balancing requires only $O(d)$ memory and $O(n)$ computations instead of $O(nd)$ and $O(n^2)$ respectively. 

This work analyses convergence guarantees of Random Reshuffling with herding procedure for non-convex objectives under L-smoothness  and PL assumptions. Moreover, authors use Bounded Gradient Error assumption. Additionally, authors used different smoothness constants for different norms. 

Theoretical analysis shows an improvement from $O(n^{1/3}T^{2/3})$ to $O(T^{2/3})$, where $n$ is number of data points. This result means that the new method is $O(n^{1/3})$ times faster. 

Usually $n$ is very large in machine learning (deep learning) applications, so even $n^{1/3}$ is significant improvement. 

Authors conducted a wide range of experiments with logistic regression and popular deep learning architecture. Plots show practical advantage of new methods compared with other permutation based algorithms. 


 
strengths_and_weaknesses: Strengths:

This paper has a good structure and it is well-written. In sections 3-5 the idea of herding and gradient balancing is fully described. This paper has 6 algorithms, which is quite informative. All assumptions are clearly stated and described in remarks. 

The idea of finding a better permutation is not new and authors mentioned it in literature review. However, the proposed general framework and efficient implementation is interesting. 

The theory seems to be sound. I checked appendix briefly and I did not find problems. However, I could miss something because technical lemmas are long. 

This paper has a lot of experiments with different large neural networks showing how this method works in practice.

Weaknesses:

This paper considers only Random Reshuffling scheme and it ignores Shuffle Once version, when permutation is computed only at the beginning of training process. It would be also interesting to see how to choose better permutation and fix it to use the same permutation the whole training process. 

This paper does not consider distributed version of random reshuffling (https://arxiv.org/abs/2102.06704, https://arxiv.org/abs/2201.11066, https://arxiv.org/abs/2204.13169) and variance reduced random reshuffling (https://arxiv.org/abs/2104.12112, https://arxiv.org/abs/2104.09342, https://arxiv.org/abs/2111.13322). It would be also interesting to see how proposed technique can be applied to distributed case and variance reduction methods. 

This paper considers only non-convex objectives. However, even in current experiments authors consider logistic regression models. Theory for strongly convex and general functions could be appreciable. 

Smoothness assumptions for different norms are not standard and if we compare new guarantees with previous results we can see that new bounds depend on dimension $d$. In practical applications $d$ is usually large number and probably large than $d^{1/2}$ can be similar to $n^{1/3}$. 

Bounded Gradient Error: 
$\text { For any } j \in\{1, \cdots, n\} \text { and any } \boldsymbol{w} \in \mathbb{R}^{d} \text {, }$

$\left\|\nabla f\left(w ; x_{j}\right)-\frac{1}{n} \sum_{s=1}^{n} \nabla f\left(w ; x_{s}\right)\right\|_{2} \leq \varsigma$.

This assumption is stricter than classical bounded variance assumption, since the new bound holds for any index $I$, but not in expectation. 

In theory parameter alpha depend on $f^*$ value which is usually unknown. 

This paper contains a lot of experiments and plots. However, in supplementary materials I cannot find the source code to understand how parameters were chosen or tuned. In supplementary materials authors provide some details about experimental settings, but it is not enough to recover the results.  






questions: 1) Is it possible to get results under bounded variance assumption or more general assumption? 

2) Can you please provide a table with comparison of results between new method and previous approaches? Also, can you please provide results under the same smoothness assumptions?

3) Is it possible to apply the new approach to find a better permutation to use it for Shuffle Once even with some additional computations?

4) Is it possible in general to apply new technique for convex problems?

5) How can you estimate $f^*$ to calculate alpha parameter? 


limitations: As I mentioned before there are three main limitations:

1) Analysis is made only for non-convex functions, convex and strongly convex analysis is desirable. 

2) The current assumptions are reasonable, but not standard. The comparison with previous results under the same assumptions.

4) $f^*$ is used for alpha parameter, but it is usually unknown.

3) Experimental evaluation is not transparent. Additional descriptions of tuned parameters is also needed. 

Overall, I believe that this paper has good quality with some limitations. I lean towards to weak accept.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Recent works have shown the possibility of speed up by using good orderings of data samples rather than shuffling them randomly. This paper identifies a mapping between the problem of finding good orderings with "herding" problem leading to a new method that provably improves convergence. The method is further improved to reduce its memory usage leading to a practical algorithm. The algorithm is tested on various tasks and models and is able to yield improved results not just in terms of speed but also in terms of final accuracy.
strengths_and_weaknesses: This paper provides a practical method for choosing orderings that theoretically converges faster than random reshuffling. This is proven both in theory (when T>n^2). Obtaining these results needs additional smoothness assumptions on infinity norm (in addition to L2) which are justified given that they are guaranteed to some extent (depending on the dimension d) given the L2 smoothness assumption.

Given that the algorithm overhead seems quite low (an additional vector sum at each iteration), this method should be applicable in many cases. Therefore, I believe this to be an important contribution both theoretically and practically and interesting to the community. The experiments are done on different tasks encompassing both image classification and NLP. However, the models used are not the ones that obtain State of the Art results. I believe these results should be included given that the algorithm is being proposed as a replacement for Random Reshuffling and would be happy to update my evaluation after examining them.

Overall, the writing is clear and the paper is well organized so it is easy to follow. I spotted a minor typo:

* In Theorem 3 and Lemma 4, it says Algorithm 6. Do you mean Algorithm 4?

questions: * I did not understand how did you arrive at line 491 from 489. In particular, how do you cancel norm_inf(grad) with norm_2(grad) without needing the dimension? 

* Since GraB is very well optimized in terms of memory, it seems it should be applicable to larger models such as ResNet. Is there any specific reason that experiments on CIFAR10 were done using LeNet? 

* While this can be possibly out of the scope of this paper, I was wondering how much the orderings change throughout training. Especially since the new ordering is based on a re-ordering of the previous epoch.  In particular, does the process converge to a single ordering?

* Would it make sense to run Herding just once at the first epoch to obtain a good ordering? 

* How does solving Herding offline compare with GraB? While it is not very practical, is there a huge difference?
limitations: There is not much discussion around the limitation of the final algorithm, GraB. In particular, Given the low overhead of GraB, I would be interested to know if there are cases that it is still better to use Random Reshuffling? Also, are there cases where GraB can not be currently applied?
review_title: null

Meta-review: metareview: This paper improves the Random Reshuffling method via a herding procedure aimed at finding a better permutation of the training dataset. Authors start by providing intuitive explanations based on a practically ineffective algorithm, and subsequently propose a gradient balancing technique; this enjoys the favorable properties of the herding procedure but is better in practice as it requires $O(n)$ times less memory and computation, where $n$ is number of data points. The authors provide convergence guarantees for Random Reshuffling with empowered with their herding procedure for smooth non-convex problems, under the standard L-smoothness and PL assumptions. Importantly, their theory points to an improvement from $O(n^{1/3}T^{2/3})$ to $O(T^{2/3})$. This result means that the new method is $O(n^{1/3})$ times faster, which is significant.

The reviewers were supportive of the paper, and described its various contributions in the following positive ways:

- Authors conducted a wide range of experiments with logistic regression and popular deep learning architecture. Plots show practical advantage of new methods compared with other permutation based algorithms.
- The paper makes a solid contribution to an important problem in machine learning.
- The development of an algorithm which can find provably better data permutations without storing all the gradients from the previous epoch enables the scaling of such techniques to large-scale problems.
- The paper is well-written and the flow of ideas is generally easy to follow.
- This paper has a good structure and it is well-written. 
- This paper studies 6 algorithms, which is quite informative. 
- All assumptions are clearly stated and described in remarks.
- The idea of finding a better permutation is not new and authors mentioned it in literature review. However, the proposed general framework and efficient implementation is interesting.
- The theory seems to be sound. I checked appendix briefly and I did not find problems. 
- This paper has a lot of experiments with different large neural networks showing how this method works in practice.
- This paper provides a practical method for choosing orderings that theoretically converges faster than random reshuffling. 
- Given that the algorithm overhead seems quite low (an additional vector sum at each iteration), this method should be applicable in many cases. Therefore, I believe this to be an important contribution both theoretically and practically and interesting to the community. 
- The experiments are done on different tasks encompassing both image classification and NLP. 
- Overall, the writing is clear and the paper is well organized so it is easy to follow. 

This is a clear acceptance case in my view; the authors were supportive and the rebuttal and the subsequent discussion clarified and addressed most issues. I would request the authors to make sure all criticism will be properly addressed in the camera ready version of the paper.

Congratulations on a nice paper!

AC


confidence: Certain
Decision: Accept