GraB: Finding Provably Better Data Permutations than Random Reshuffling
Authors: Yucheng Lu
Wentao Guo
Christopher De Sa
Venue: NeurIPS 2022 Accept (2022)

Abstract: Random reshuffling, which randomly permutes the dataset each epoch, is widely adopted in model training because it yields faster convergence than with-replacement sampling. Recent studies indicate greedily chosen data orderings can further speed up convergence empirically, at the cost of using more computation and memory. However, greedy ordering lacks theoretical justification and has limited utility due to its non-trivial memory and computation overhead. In this paper, we first formulate an example-ordering framework named \emph{herding} and answer affirmatively that SGD with herding converges at the rate $O(T^{-2/3})$ on smooth, non-convex objectives, faster than the $O(n^{1/3}T^{-2/3})$ obtained by random reshuffling, where $n$ denotes the number of data points and $T$ denotes the total number of iterations. To reduce the memory overhead, we leverage discrepancy minimization theory to propose an online Gradient Balancing algorithm (GraB) that enjoys the same rate as herding, while reducing the memory usage from $O(nd)$ to just $O(d)$ and computation from $O(n^2)$ to $O(n)$, where $d$ denotes the model dimension. We show empirically on applications including MNIST, CIFAR10, WikiText and GLUE that GraB can outperform random reshuffling in terms of both training and validation performance, and even outperform state-of-the-art greedy ordering while reducing memory usage over $100\times$.

GraB: Finding Provably Better Data Permutations than Random Reshuffling
Yucheng Lu, Wentao Guo, Christopher De Sa Department of Computer Science Cornell University
fy12967, wg247, cmdd33))@cornell.eed
Abstract
Random reshuffling, which randomly permutes the dataset each epoch, is widely adopted in model training because yields faster convergence than with- replacement sampling. Recent studies indicate greedily chosen data orderings can further speed up convergence empirically, at the cost using more compu- tation and memory. However, greedy ordering lacks theoretical justification and has limited utility due to its non-tre trivial memory and computation overhead. this paper, we first formulate example-ordering framework named herding and answer affirmatively that SGD with herding converges at the rate O(3-2/3) on smooth, non-convex objectives, faster than the 1/ obtained by random reshuffting, where n denotes the number of data points and T denotes the total number of iterations. To reduce the memory overhead, we leverage discrepancy minimization theory to propose an online Gradient Balancing algorithm (GraB) that enjoys the same rate as herding, while reducing the memory usage from O (nd) to just ((d) and computation from O(n²) to O(n). where d denotes the model dimension. We show empirically' WikiText and GLUE that GraB can outperform random reshuffling in terms of both training and validation performance, and even outperform titte--f-hheartt greedy ordering while reducing memory usage over 100x.
applications including MNIST, CIFAR 10,
Introduction
Many machine learning problems can be formulated as minimizing differentiable (loss) function f: IRd R for a set of data examples {> To train a parameterized model, the goal is to obtain a set of target parameters w² arg min f(w)), where ((w) Σi= f(u; æx), and f(ur; a;) denotes the loss incurred on the i-th data example æ; (usually mini-batch of images, sentences, etc.) with model parameters w. A typical model training, or optimization process, is to iteratively update the model parameter w starting from some initial (!) by running
w (t+1) w (f) a aV)(w ;00
t= 1,2,
(1)
where denotes the step size, and (1.....n) nI. denotes a permutation (ordering) from which the examples are chosen compute the stochastic gradients?. widely adopted ordering protocol is Random Reshuffling (RR), where the optimizer scans in an order drawn at random without
replacement over the entire training dataset multiple times during training (a common name for single such scan is "epoch"). RR allows the optimizer to converge faster empirically and enjoys
'The experimental code is available https://githis cwn/ com//uueeeLYC/////ooooooooo.oc GraB... In this paper, we consistently use the term stochastic gradients to refer to gradients computed on single (or set of) data example(s), even when those examples not selected random.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

better convergence rate in theory [1]. Despite RR's theoretical improvement, it has been proven that RR does not always guarantee good ordering [2, 3]; fact a random permutation is far from being optimal even when optimizing a simple quadratic objective [4]. In light of this, a natural research question is:
Can we find provably better orderings than Random Reshuffling and do efficiently?
Recent studies indicate the possibility of greedily constructing better permutations using stale estimates of each V (s(w; æ;)) from the previous epoch [5, 6]. Concretely, Lu et al. [5] proved that for any model parameters E R" if sums of consecutive stochastic gradients converge faster to the full gradient, then the optimizer will converge faster. Formally, in one epoch, any permutation minimizing the term (named average gradient error)
Σ vf(w; - Vf(w)
max (E(L......
gradient error
leads to fast convergence. Leveraging this insight, Lu et al. [5] proposes to greedily select (t) one a time for all f {1, (1,....77 ) at the beginning of the (k + 1)-th epoch, using the stochastic gradients computed during the k-th epoch as an estimate. This strategy works well empirically, but it remains an open question how its convergence rate compares to that of RR. Moreover, the greedy ordering method intensively consumes ( memory to store the gradients and O(n²) computation order, which significantly hinders its usefulness in practice. For instance, training simple logistic regression on MNIST would easily cost more than I GB additional memory compared to RR.
In this paper, we address the limitations of previous order-selcction approaches, culminating in proposing a new algorithm, GraB, which converges faster than RR both in theory and in practice without any blow-up in memory computational time. First, we address the theoretical gap by connecting the convergence of permuted-ordes SGD to the classic herding problem [7]: we show how any algorithm for solving the herding problem can be run on stale stochastic gradients to select an example ordering. While the greedy selection method of previous work may fail to select a good ordering, using the best herding algorithms from the literature yields better convergence rate: -(33)/3) compared RR's /3 on smooth non-convex problems and ( compared to RR's 3(nT=2) under PL condition, where T the total number of iterations. Building on this, we leverage discrepancy minimization theory [8] to propose an online Gradient Balancing algorithm (GraB) that achieves the same ( rate but only requires (d) memory and (()) computation. Perhaps surprisingly, on multiple deep learning applications we observe GraB not only allows fast minimization of the empirical risk, but also lets the model generalize better. Our contributions in this paper can be summarized as follows:
We formulate general framework of sorting stochastic gradients with herding, and prove SGD with herding converges at faster rate than Random Reshufiling (Section 3).
We propose an online Gradient Balancing (GraB) algorithm that enjoys the same fast conver- gence rate as herding SGD while significantly reducing the memory from O(nd) to O(d) and
computation from O(?)) to O(n) (Section 5)-
We conduct extensive experiments models. We demonstrate that GraB converges faster in terms of both training and validation compared to Random Reshuflling and other baselines (Section 6).
MNIST, CIFAR1O, Wiki'eet and GLUE with different
2 Related Work
While traditional data ordering research mostly focuses on with-replacement samplers [9-11] without- replacement sampling more common in practice [12]. Random Reshuffling (RR) [13] and the related shuffle-once (SO) method [14, 15] are among the most popular data permutation methods. Recht and Ré [16] undertakes the first theoretical investigation of RR, while subsequent works like [2, 17] give counter examples where RR orders badly. HaoChen and Sra [18], Gürbüzbalaban et al. [19], and Mishchenko et al. [1] discuss extensively on the conditions needed for RR to benefit. Some recent works [5, 6] suggest constructing better data permutations than RR via a memory-intensing greedy strategy. Concretely, Mohtashami et al. [6] proposes evaluating gradients on all the examples first to minimize Equation (2) before starting an epoch, applied to Federated Learning; Lu et al. [5]

---

Algorithm Herding with Greedy Ordering [5]
1: Input: group of vectors {
Center all the vectors: 2, f- 2 1 2 zn. Vi E [n].
3: Initialize arbitrary o, running partial sum: + candidate set &b +- fI,...,,
for I,...,?' do
select 2j from that minimizes || 6: Remove from O update partial sum and order: # f- a - Zj; (1) f j-j.
Iterate through
7: end for
8:
return
Algorithm 2 General Framework of SGD with Offline Herding
1: Input: number of epochs K, initialized order dy initialized weight wi, learning rate a.
2: for k = 1,.., K do
3: for t- I,..., do
4:
Compute gradient V ? (o)()))
5: Store the gradient:
Vi(w (t) (o2
6: Optimizer Step: w w((+1) w a f(wl ;
(++1)
7: end for
8: Generate new order: atti + #erding((2:)2
9:
wi+t i++1 < m
(1)
(m+1)
10: end for
11: return wk""
(1)
provides an alternative of minimizing Equation (2) using stale gradients from previous epoch to estimate the gradient on each example. Rajput et al. [4] introduces an interesting variant to RR by reversing the ordering every other epoch, achieving better rates for quadratics. Other approaches, such as curriculum learning [20]. try to order the data to mimic human learning and improve generalization [21-23]: these approaches differ from goal of finding good permutations for minimizing loss in finite-sum setting.
3 Offline Stale-Gradient Herding
In this section, we study the use of stale gradients- the stochastic gradients for each example from the previous epoch, saved in memory-to construct data permutation at the start of each epoch. Lu al. [5] and Mohtashami al. [6] propose to use greedy ordering in this wra--selecingg examples one at time to minimize Equation (2). Here, we first show that this objective is closely related to the classic herding problem from discrepancy theory. We demonstrate with examples from the herding formulation that in the adversarial setting, greedy selection is bad at herding and can underperform basic random reshuffling. We conclude this section by proving SGD with proper herding converges faster than random reshuffling.
Herding. The herding problem originates from Welling [24] for sampling from a Markov random field that agrees with a given data set. Its discrete version is later formulated in Harvey and Samadi [7]. Given vectors 1a that are d-dimensional (i.e. in (Rd) and have norm ||2 S 1, the herding problem we study is the task of finding a permutation [m] + [n] that minimizes
Σ*
*
" T2
max kE (1.......
Za(t)
23
(3)
1=1
voctor offor
State-of-the-art algorithms guarantee an Õ(1) bound to this objective [7]. straightforward to observe the the formulation of Equation (3) generalizes Equation (2) if we replace each z; with the stochastic gradient computed on the example In other words, any algorithm that minimizes Equation (3) can be used minimize Equation (2) and find better data permutation. The simplest way to do this is with the greedy algorithm for herding, which we show in Algorithm I: this is
A small distinction is Harvey and Samadi [7] investigates infinite sequences while here we are studying finite ordering, iee. permutation.

---

Table 1: Table summarizing the theoretical results in this paper, where denotes the total number of data points (examples), d denotes the model dimension and denotes the total number of iterations (n times the number of epochs).
Rate (Non-convex)
Rate (PL)
Computation over RR
Storage over RR
RR Herding
0 3
O(n
N/A
N/A
(T $
O
(
GraB
0(T-2)
O(n)
O
essentially what the previous work doing select order based on stale gradients. Unfortunately, despite its elegance, it was first pointed out in Chelidze et al. [25] that the greedy ordering can underperform random permutation. We adapt their result to show the following.
Statement 1. There exist n vectors in IR? such that when applying Algorithm 1, the objective in Equation (2) becomes (2n); random permulation is guaranteed to achieve O(yn) on average.
Herding SGD with Stale Gradients. Based on the herding framework, a path to SGD with better data permutation becomes clear: when training models during a epoch, we can simply store all the stochastic gradients, and then herd them (with some herding algorithm) offline at the start of the next epoch to obtain the order for that epoch. This stale- male-ggadieet approach is formally described in Algorithm 2, and could be contrasted with a rresh-gradient approach (as in Mohtashami al. [6]) that herded with newly computed stochastic gradients at the start of each epoch-it it is desirable to avoid the use of fresh gradients if possible as they double the gradient computations needed each epoch. The greedy ordering of Lu et al. [5] can be described running Algorithm 2 using Algorithm I as the Herding subroutine. However, as greedy herding with Algorithm does not have a good worst-case guarantee, we propose using some other herding algorithm instead. There have been many algorithms proposed that can reduce the Equation (3) (1) in polynomial time. Here, we show that this herding-obye objeecive bound is sufficient to prove convergence of herded SGD and even yield a better convergence rate than Random Reshuffling. We defer the details of the herding algorithm to Section 5, as they do not affect the convergence rate SGD.
We start by stating some assumptions for non-convex optimization, as well as our herding bound. Assumption 1. (Smoothness.) For any example æj in the dataset (for j E (L)),.,n))) the loss for 2j is L2 -smooth and Los- -mmooth meaning that,for any w, v E Rdd, it holds that and
f xx; f(u;,,,),, S 22 00 w - vlloc V m.)) - (w; I T e1l.00
The averaged loss function is also L-smooth in that, for any w. E TRd, it holds that
[Vf(w) - Vf(v)ll S L||w- ull2-
Assumption 2. (PL condition.) We say the loss function f fulfills the Dolyak-Lojasiewiee (PL) condition there exists J O such that for any E TR..
ス [VS(w))1 2 (f(w)) )²),
where S" inf f(v). HERd
Assumption 3. (Bounded Gradient Error.) For any jE .., ..l....,,) .n} and any E Rd.
Vf((w -. Vf(w; ([Ww:x))ll,
Assumption 4. (Herding Bound.) In Algorithm 2, the subroutine Herding algorithm has the following property [26]: if given input vectors 21...., Zn E Rdd that satisfy || S and Σx= zi = 0, Herding outputs a permutation of [I....,n]] such that for all E [I....,n) | 200 < H for some constant H.
Remarks on the assumptions. Assumptions 1, 2, and are commonly used assumptions in the study of permutation-bast based SGD, except that we separate different smoothness constants with respect to different norms to tighten the final bound. The cross-norm Lipschitz constant T22,0 is often used to obtain tight cuimension-independdee bounds [27, 28]. Note that these cross-norm assumptions can

---

Receive
Z1
Z2
Z3
Z4
150
Mm Reorder (repeat time)
Random
Summed norm
Reorder (repeat 10 times)
Balance
50
0
Reorder
Z1
Z4
Z3
Z2
2000 4000 6000 8000 10000 Num of vectors summed
(a) Balancing and then reordering.
(b) Toy Example of Random GraB.
Figure 1: (a) illustrates how Algorithm reorders the vectors with balancing the new order is obtained by concatenating original order of the examples with +1, followed by the reverse order of the examples with -1; (b) demonstrates toy example on 10000 vectors ) where 2; randomly sampled from [0, 1222 For a given order o, we plot the norm of the prefix sums <> (Za(() - 1/n > 21)ll for all k 1,...,
be dropped by incurring extra factors of the dimension d, as Lo S L2,0 S VdL for any function. Assumption 4 holds for multiple algorithms for some H = Ó(1): we will discuss this in depth in Section 5, while treating // parameter here as we in the final bound. Under these assumptions, the convergence rate of Algorithm 2 is given in the following theorem.
observe the dependence on this variable
Theorem 1. In Algorithm 2, under Assumptions 1, 3 and 4, if set be
f(wi)- f 2 K' 8n(L + L2,00) 32nl. 16HL22,0 min (V
min
then it converges at the rate
1 K
H H2 F2
+ 22 K
32F + 12,00 +
Loo)
64F 12,00
[(((w)) < 36
K
n²K22
K
nK
k=1
where F f(w)) f Furthermore, under the additional PL condition (Assumption 2), with as
1
2
ff
p
min
Wo npk
np 4811 42,0 96n(L + 12,00 + Loo)
19211=12,00
where Wo denotes the Lambert W function, Algorithm 2 converges at the rate
f(wk) - 8r 5ō H2 H²
Improved Rate Compared to RR. Theorem gives better rate than random reshuffling, in that there is no dependence on the number of examples n in the dominant term. If we let T = n be the total number of steps, then Theorem 1 shows Algorithm 2 converges at rate O 7273 + $). In
contrast, random reshuffling gives rate of O 7 + #) as given in Mishehenko et al. [1], Theorem
1/3
4. Similarly, herding improves the rate from ( to Ö in the PL case. This gives us an affirmative answer our question from the intro: faster rate can be obtained even if herd with stale gradients estimates, without computing additional gradients.
4 Enabling Memory-Efficien Herding with Balancing
In Section we introduce the herding problem, and prove that with proper herding, SGD converges at faster rate than Random Reshuffling. However, downside of offline herding SGD is that it
5

---

Algorithm 3 Reordering Vectors based on Balanced Signs [7]
I: Input: a group of signs {cr Ji for {z, ! from a balancing algorithm, initial order Initialize two order-sensitive lists Lepastive + []. Lnngueiee f [].
3: for i= L...... do
4: Append (1) to Tpussiive if 6 is +1 else append it to Imneatiie
5: end for
6: return new order o' concatenatel [ reverse Tneegtiie))
requires storing all the vectors (i.e., in the case of SGD, all the stochastic gradients) which incurs O(nd) memory overhead. In this section, we present background the vector balancing problem, the solutions of which will enable us to solve the herding problem in an online fashion.
Background: Online Vector Balancing. The problem of online vector balancing was first formulated in Spencer [29]: given n vectors { E R arriving one at time, the goal is assign sign & E (-1,,+1 to each vector upon receiving it so as to minimize max -> G2z llac. Over the last few decades, many efforts have been spent on bounding this -norm objective. Specifically, Aru al. [30] and Bansal and Spencer [31] shows it can be made to be on the order of ((1) when the coordinates of each vector are independent. Bansal et al. [32] gives a poly(log(n), d) bound when there dependencies among coordinates. The adversarial setting with interval discrepancy is discussed in [33]. Other works focus on balancing variants such as stochastic arrival [34] or box discrepancy [35].
Solving Herding via Balancing. While the objectives of balancing and herding are different, an algorithm for balancing can be used as subroutine to do herding as well. Consider the simple case of vectors 21...., 2n in some order, where Σm= 2; = 0, and suppose we have obtained a group of signs {e, via some balancing algorithm: can solve the herding problem? Harvey and Samadi [7], Chobanyan et al. [36), and Chobanyan [37] approach this problem by clever reordering that works in Algorithm 3. Concretely, a new order is obtained by first taking all the vectors with positive signs in order, followed by all the vectors with negative signs in reversed order from the original sequence. This process is visualized in Figure I. Harvey and Samadi [7] shows that this balancing and---nd-tettt thee--hrrrrrrringg has the following effect on the herding objective in Equation (3).
this to determine
order of } that
Theorem ([7), Theorem 10) Consider n vectors 21...., Zn E Rd that fulfill Σi= 2;
and | < 1. Suppose that for some permutation o, the herding objective is bounded by max;
Σ =o(s)]lo S H for some constant H. Suppose we have computed some signs -1.--.: On such that the vector-balancing objective max; E (; llx S A for some constant A. Then if we let af be the permutation output by Algorithm 3, the herding objective on this new permutation is bounded by maxs E Zo'(0) Imx S (A + H2/2.
Theorem 2 shows that calling Algorithm 3 allows us to construct a new ordering from balancing. which reduces the current herding bound by a constant factor A < H. This means that if we have a balancing algorithm that is guaranteed to reduce the balancing objective to less than A, by applying this "reordering" many times, we can also reduce the herding objective to be less than A: this approach used in many offline herding algorithms that achieve ((1) bounds.
5
GraB: SGD with Gradient Balancing for Good Data Permutation
Building on the balance-then -herder paradigm from the previous section, in this section propose an algorithm named GraB that improves SGD with herding by choosing the ordering online-without storing tradients-thus using only (dd) memory and (n)) computation. However, the conditions of applying the aalancing-reordering framework bring up additional challenges in this online setting:
To apply Theorem 2, we will need to pre-center all the vectors (as in line 2 of Algorithm 1) to ensure they sum to zero. This cannot be done online, as we need to make decisions on-the-fly before seeing all the vectors.
Challenge I.
Challenge II. The reordering strategy, as shown in Theorem 2, only reduces the herding bound by a constant factor, which does not give the accelerated rate directly since applying Theorem 1

---

Algorithm 4 SGD with Online Gradient Balancing (GraB)
I: Input: numher of epochs K, initialized order dı, initialized weight stale mean = 0, step size
2: for k .,.., KK do
Initialized indices and running average: 1 1; < n. 8 +- O: m4411 0.
4: for I,..., Y2 do
5: Compute gradient (unf; (rz(())-
6:
Compute centered gradient and update stale mean:
gh.t + f(wj; Tog(1)) mi
mi++1 7x+4 + V (i Fo, (1)/// Compute sign for the current gradient: cx,t c- Balancing gk.1) if C +1 then
7:
8:
else a gr (1) +- (x):)))))+++
10:
11:
+ ga.ci 0h+1 + au(t); r + r-
12: end if
13: Optimizer Step: wa (++1) w a /Ww (t)
end for
15: wk++1 < w (n+1)
(1)
16: end for
17:
return wk
Algorithm 5 Balancing without normalization.
1: Input: current sum s, vector v.
2: +1 if ||s + vll < ||s vll else <- -.
3: return
would require Equation (3) to be on the order of Ô(1). We can repeatedly call the balancing- reordering subroutines, but that would again require storing all the stochastic gradients.
To overcome challenge I, we apply a two-step stale gradient estimate: for any k; we use the running average of stale gradients to "center" stochastic gradient in epoch k + (this centering is itself stale, and does not guarantee the vectors sum to 0, but this is still enough to prove convergence). Then, the online balancing balaneeng--roodeeiinn reordering subroutine will determine the proper order to in epoch + 2. To address challenge II, we leverage a noisy reordering process: let 0 denote the order to use in epoch k. then the next order 0++1 will be obtained from σge- The intuition here is that if train the model with enough epochs, the reordering will in general push the herding bound towards A in Theorem without storing any additional vectors. We present the full GraB algorithm in Algorithm 4.
We proceed to provide convergence guarantee for Algorithm 4. Since now we are working with balancing rather than herding, in the convergence analysis we replace Assumption 4 with the following one related to balancing.
Assumption 5. (Balancing Bound.) There exists constant A > such that in Algorithm 4, if the subroutine Balan Balancing is given input vectors 21.... on E dd that satisfy || S then f-1, such that E 4Z lo0 S A for all k E .n).
Ba l ancing outputs signs
We defer discussing the complexity of A to the later part of this section, and first present the convergence guarantee for GraB (Algorithm 4) as follows.
Theorem 3. In Algorithm 4, under Assumptions 1, 3 and 5, if we set a to be
f(wi) f
a= min (V
32m.A2 22 K nI 26(n + 22 260mL
then converges at the rate
H2 F2
2 +
65(F
L2,00 Loo) +
8F 8FAL2,00
[ $
K²
K
K
nK
7

---

Algorithm 6 Probabilistic Balancing with Logarithm Bound. [38]
1: Input: current sum s, received vector 2, hyperparameter c.
2: if [s, 2 > cor || > c. then
3: Fail.
4: end if
5: +1 with probability (e,=) 2c
and e -1 with probability 1
(s,z) 2c
6: return
where F = f(w1) f*. Furthermore, under the additional PL condition (Assumption 2) with as
a = min 1 1
1
2
(f(wr)-ffe +
Wo nuK
ny nL 52(n + 2) 520mL
256.A-L2.
where Wo denotes the Lambert W function, it converges at the rate
12 1² K2
f(WK) 5 5 S
Comparing Theorem 1 and 3, asymptotic convergence rate as SGD with herding (Algorithm 2).
observe GraB (Algorithm 4) achieves essentially the same fast
Asymptotic complexity for A and H. So far we have covered the main design of GraB. A remaining yet unanswered question how do A in Assumption 4 and in Assumption 5 relate other factors exactly, and what are the concrete algorithms to achieve small A and H. Some recent progress in the theory community shows that there exists an online algorithm (Algorithm 6) that guarantees with high probability that A is on the order Ô(1) as shown in the following theorem.
Theorem 4. (Alweiss et al. (38]) In Algorithm 6, if all the vectors have ||=||] and the parameter e is set e = 30 log(nd/8), then with probability 6, the maximum partial signed sum is bounded by max,
E {ı3حlm c Olog(nnd) = Ō(1).
This theorem gives us a statement that the result of Theorem 3 holds with A replaced by Ó(1). Theorem 4 also yields good offline herding algorithm and bound on H: recall from Theorem that given any herding bound H on an ordering, running Algorithm 3 once allows us to obtain new herding bound (A + H)/2. Given Theorem 4 that Ó(1) bound is guaranteed as described in Section 4, we can eventually push the herding bound H towards A, which yields H Ó(1). This can done with probability offline by simply restarting on failure; however, as stated in Section 3, this still requires storing all the vectors.
bound on A that can easily be converted to high-probability
A, then if we repeatedly run Algorithm
On the normalization of vectors. Note that typical balancing subroutine (e.g. Algorithm 6) requires normalized vectors || S. 1.vi. This, in practice, implies we will need to estimate large enough constant to normalize gradients when we run GraB. To alleviate this issue, we can instead adopt a balancing subroutine that is invariant to the normalizer, for instance, Algorithm 5. As shown in the next section, this naive balancing algorithm suffices for non-trivial improvements.
Experiment
In this section, we evaluate GraB and other baseline algorithms multiple machine learning applications. We compare GraB (Algorithm 4) with the following baselines: Random Reshuffling (RR), Shuffle Once (SO) [1], FlipFlop [4] and Greedy Ordering* [5]. All the experiments run an instance configured with a 4-core Intel(R) Xeon(R) 2.50GHz CPU, 32GB memory and an NVIDIA GeForce RTX 2080 Ti GPU. Although we used Algorithm 6 to show Ö(1) bound can be obtained for herding, in experiments, adopt the simple balancing algorithm of Algorithm 5, which performs well in practice. More results with other balancing algorithms can be found in the Appendix.
'For FlipFlop, we follow the exact implementation code from https: //tgtttb..tttttt////eeeeege com/ shashankaajjut/ flipflop: and for Greedy Ordering, we strictly follow https: /tt///ttttttt thub. com Btt//BggeeLLC//pcc.ccm www.reore/.ooooooooriiinngg
8

---

1.50
Stuffe
0.350
0.523
Rand Reshuffe
0.323
0.000
Cready
0.300
0.273
0.90
0250
0.23
0.22
100
320
2000
2300
200
500
2000
(a) Logistic Regression MNIST. GraB reduces the memory from 224.6MB (Greedy) to 0.06MB.
14
Stuffe Onee
70.0
70.0
1.2
Hand Heahulle
Ripitpp
67.5
67.5
Gready
e3.0
63.0
62.5
(2.5
0.8
106
3500
300
1200
2000
1000
Time
Time
(b) LeNet on CIFARIO. GraB reduces the memory from 1.44GB (Greedy) to 0.46MB.
5.5
Shuffe Once
Rard Reshuttte
(OOM)
229
210
213
200
200
5.0
5.gg
Ea
Time Sec
Ezoch
Time 1000
(c) LSTM on WikiText-2. Greedy Ordering incurs Out Of Memory (OOM) error.
0.60
0.6
Co675
0.75
0,550
0.70
Rand Rechumte
a.255
FilT
0.80
0.
Grab
Greedy I00M)
30
20
0.75
0.000
10
20
6.1
10
15
20
25
30
30
70
(d) Finetune BERT-Tiny on two GLUE tasks (left: QNLI; right: SST-2). Greedy Ordering incurs Out Of Memory (OOM) error both tasks, and thus is not shown.
Figure 2: Training/Validation on MNIST, CIFARIO, WikiText-2 and GLUE with different models.
Model and Dataset. We adopt the following model training tasks for evaluation: (1) training logistic regression on MNIST, (2) training LeNet on CIFARIO [39], (3) training LSTT on wikitext-2 [40], and (4) finetuning BERT-Ting Tiny [41] on GLUE [42]. Detailed information regarding models, datasets and hyperparameters can be found in Appendix A.
Convergence Speedup. The convergence plots for each algorithms are summarized in Figure 2. We observe that in general, GraB able to converge faster in terms of both training and validation loss on various tasks. Of all the baseline algorithms, Greedy Ordering is able to achieve comparable convergence speed with respect to epochs to GraB. However, Greedy Ordering consumes much more memory and wall-clock time as shown in the figure. In the BERT training case, we observe the Greedy Ordering runs Out Of Memory (OOM), causing an error on our machine. Based on simple calculations, GraB only requires less than 1% the memory used by Greedy Ordering for all the tasks. is worth pointing out that throughout the experiments, we do not tune hyperparameters for GraB but let it reuse the hyperparameters from RR (details in the Appendix). This implies GraB can provide in-place improvement without any additional tuning in practice, and a well-tuned GraB could benefit with even larger margin. Shuffle Once (SO) performs worst in all the cases, and FlipFlop is generally the same as RR, which is aligned with the conclusion made in Rajput et al. [4].
are good permutations fixed? In GraB, the example ordering a is carried and improved over epochs, which motivated from minimizing the herding bound. This raises another question of whether the found permutation changes at later stage of training, and if so, can we find fixed permutation that outperforms the RR in practice? Here we conduct an ablation study on two fixed order strategies with GraB, We include the following two variants:
Ablation Study:

---

Stuffe Once
Shuffe Orce Reshuffling
Sandom Rectuff Ing
Colap Greld
1.-
Retmin from
Betrain from
Stuffe Once
Crubi
Stuffl Once
Tansdem Raauliing
Bardom Heatulliigg
stspp GraB
sittep Grad
Gred
Dran
1poch
Epoch
Epoce
(a) LeNeUCIFARIO (non-convex).
(b) logistic regression/MNIITT (convex).
Figure 3: Ablation Study of GraB with fixed orders. I-step GraB refers the algorithm that uses GraB only in the first epoch to obtain an order, and then use it as fixed order for the rest of the training. Retrain from GraB refers the algorithm that uses fixed order obtained at the end of the epoch from GraB full run (the latter one is not for practice, only for understanding GraB with fixed orders). The main takeaway here is that for convex problems, we can find a fixed example order that outperforms both RR and SO.
1-step GraB: it only runs GraB for epoch to obtain ordering, and then use it as a fixed order for the rest of the training.
Retrain from GraB: First launch full run of GraB, and then use the ordering in the final epoch as a fixed order in a new run.
We test these new variants on two tasks: LeNet CIFARIO (non-convex) and logistic regression on MNIST (convex). The training loss and validation accuracy curves can found in Figure We observe that on both tasks, the 1-step GraB does not work well, which is aligned with our theory and motivation in Section 5 Challenge II. On the other hand, Retrain from GraB achieves the comparable performance than original GraB the convex task, but not on the non-convex one. This is mainly because a good ordering is going to depend on the local optimum the algorithm is approaching and for convex problem, there is only one such optimum. It again verifies that GraB finds better orderings compared to baseline Random Reshuffling and Shuffle Once.
On the granularity of example ordering. Throughout this paper, we have discussed how to find good data permutations via per-example gradients. In practice, however, per-example gradients are usually not easy to obtain since data is usually loaded in batches, and many ML libraries (e.g. PyTorch) directly accumulate gradients over the batch. direct workaround is to fix the data within batches and reorder the batches (treating them as coarse- gransee examples). This, however, would compromise the benefits of ordering since the total number of examples n is reduced by a factor of batch size, while the statistical improvement of herding (GraB) in the order of ( -133). To alleviate this, provide two alternatives: (1) Use ML frameworks that support quick per-example gradients computation (e.g. JAX*); ); (2) Leverage gradient accumulation steps as used in large language model training, i.e., use smaller batch sizes in the code but perform optimizer. .sep once every few steps so that we can obtain the finer- mrainee gradients on-the-fly fly while still optimizing the models with the desired batch size. This is the default method used throughout the experiments, will include more details in the appendix.
Conclusion
In this paper, we formulate a herding framework for data-ordering in SGD. We prove SGD with herding finds better data orderings, and converges faster than random reshuffling on smooth non- convex and PL objectives. We propose online gradient balancing algorithm named GraB that finds a better ordering with little compute or memory overhead. We substantiate our theory and the usefulness of GraB multiple machine learning applications.
Acknowledgement
This work is supported by NSF-2046760. Yucheng is supported by Meta PhD Fellowship. The authors would like to thank Si Yi Meng and anonymous reviewers from NeurlPS 2022 for providing valuable feedbacks on this paper.
'nttps://jax http://ss..rrrrrteossocccccc.se httpi/ssssoooo/eat////seesee -otttessst/aaxx111////-/ auuio autodiff html# per cor-example-ee gradients
10

---

References
[1] Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. In Advances in Neural Information Processing Systems, 2020.
[2] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Open problem: Can single-shuffte SGD be better than reshuffling SGD and GD? In Conference on Learning Theory, 2021.
[3] Christopher M De Sa. Random reshuffling is not always better. Advances in Neural Information Processing Systems, 33:5957-5967, 2020.
[4] Shashank Rajput, Kangwook Lee, and Dimitris Papailiopoulos. Permutation- bbased sgd: Is random optimal? arXiv preprint 102.x::2002.07/88. 2021.
[5] Yucheng Lu, Si Yi Meng, and Christopher De Sa. A General Analysis of Example-Selectee for Stochastic Gradient Descent. In International Conference on Learning Representations, 2021.
[6] Amirkeivan Mohtashami, Sebastian Stich, and Martin Jaggi. Characterizing finding good data orderings for fast convergence of sequential gradient methods. arXiv preprint arXiv:220..01838 2022.
[7] Nick Harvey and Samira Samadi. Near-Optimal Herding. In Proceedings ofe 27th Conference on Learning Theory, volume 35, pages 166--1882, 2014.
[8] Nikhil Bansal and Joel Spencer. Deterministic discrepancy minimization. Algorithmica, 67(4): 451-471,2013
[9] Mark Schmidt, Nicolas Le Roux, and Francis R. Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):33112,2200 2017
[10] Deanna Needell, Rachel Ward, and Nathan Srebro. Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm. Advances in Neural Information Processing Systems, pages 1017-1025, 2014.
[11] Yucheng Lu, Youngsuk Park, Lifan Chen. Yuyang Wang, Christopher De Sa, and Dean Foster. Variance reduced training with stratified sampling for forecasting models. In Proceedings of the International Conference on Machine Learning, pages 7145-7155. PMLR, 2021.
[12] Léon Bottou. Stochastic gradient descent tricks. In Neural networks: Tricks of the trade, pages 421-436. Springer, 2012.
[13] Bicheng Ying, Kun Yuan, Stefan Vlaski, and Ali Sayed. On the performance of random reshuffling in stochastic learning. In 2017 Information Theory and Applications Workshop (ITA), pages 1-5, IEEE, 2017.
[14] Dimitri P. Bertsekas. Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey. In Optimization for Machine Learning. The MIT Press, 2011.
[15] Mert Gürbüzbalaban, Asuman Ozdaglar, and Pablo A. Parrilo. Convergence rate of in- cremental gradient and incremental Newton methods. SIAM Journal on Optimization, 29(4): 1342-2565,, 2019.
[16] Benjamin Recht and Christopher Ré. Toward a noncommutative arithmetic--eomeeri mean inequality: Conjectures, case-studies, and consequences. In Conference Learning Theory, volume 23, pages 11.1-11.24, 2012.
[17] Christopher De Sa. Random reshuffling is not always better. In Advances in Neural Information Processing Systems, 2020.
[18] Jeff HaoChen and Suvrit Sra. Random shuffling beats SGD after finite epochs. In Proceedings of the International Conference on Machine Learning, volume 97, pages 2624-2633, 2019.
[19] Mert Gürbüüzalabaa,, Asu Ozdaglar, and Pablo Parrilo. Why random reshufiling beats stochastic gradient descent. Mathematical Programming, 186(1):49-84) 1021.
11

---

[20] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th anmual international conference on machine learning, pages 41-48, 2009.
[21] Alex Graves, Mare G Bellemare, Jacob Menick, Remi Munos, and Koray Kavukcuoglu. Au- tomated curriculum learning for neural networks. In international conference on machine learning, pages 131 1-1100. PMLR, 2017.
[22] Tambet Matiisnn, Avital Oliver, Taco Cohen, and John Schulman. learning. IEEE transactions on neural networks and learning systems, 31(9):3732-374 2019.
curriculum
[23] Petru Soviany, Radu Tudor lonescu, Paolo Rota, and Nicu Sebe. Curriculum learning: A survey. International Journal of Computer Vision, pages 1-40, 2022.
[24] Max Welling. Herding dynamical weights to learn. In Proceedings of the 26th Annual Interna- tional Conference on Machine Learning, pages 111-11128, 2009.
[25] George Chelidze, Sergei Chobanyan, George Giorgobiani, and Vakhtang Kvaratskhelia. Greedy algorithm fails in compact vector summation. Bull. Georg. Natl. Acad. Sci, 4(2), 2010.
[26] Nikhil Bansal and Shashwat Garg. Algorithmic discrepancy beyond partial coloring. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 914 926, 2017.
[27] Zheng Li and Christopher De Sa. Dimension-fin free bounds for low- low-precision training, Advances Neural Information Processing Systems, 32, 2019.
[28] Yucheng Lu and Christopher De Sa. Moniqua: Modulo quantized communication in decen- tralized sgd. In International Conference on Machine Learning, pages 6415-6425, PMLR, 2020.
[29] Joel Spencer. Balancing games. Journal of Combinatorial Theory, Series B, 23(1):68-744 1977.
[30] Juhan Aru, Bhargav Narayanan, Alex Scott, and Ramarathnam Venkatesan. Balancing sums of random vectors. arXiv preprint arXiv: 1610.05221, 2016.
[31] Nikhil Bansal and Joel H Spencer. On-line balancing of random inputs. Random Structures & Algorithms, 57( 891, 2020.
[32] Nikhil Bansal, Haotian Jiang, Sahil Singla, and Makrand Sinha. Online vector balaneing and geometric discrepancy. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. pages 1339-152,, 2020.
[33] Haotian Jiang, Janardhan Kulkarni, and Sahil Singla. Online geometric discrepancy for stochas- tic arrivals with applications to envy minimization. arXiv preprint arXiv: 19.001073, 2019.
[34] Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha. Online discrep- ancy minimization for stochastic arrivals. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithmms (SODA), pages 2842-2861. SIAM, 2021.
[35] Jirí Matoušek and Aleksandar Nikolov. Combinatorial discrepancy for boxes via the gamma 2 norm. In 31st International Symposium on Computational Geometry (SoCG 2015). Schloss Dagstuhl-Letbbiiz-ZZentru fuer Informatik, 2015.
[36] S Chobanyan, Shlomo Levental, and Habib Salehi. Maximum inequalities for rearrangements of summands and assignments of signs. Theory of Probability & Its Applications, 5944)6677-684 2015.
[37] Sergei Chobanyan. Inequalities on rearrangements of summands with applications in as conver- gence of functional series. In VII International Joint Conference of Georgian Mathematical Union & Georgian Mechanical Union, page 56, 2016.
[38] Ryan Alweiss Yang P Liu, and Mehtaab Sawhney. Discrepancy minimization via a self- balancing walk. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 14-20, 2021.
12

---

[39] Alex Krizhevsky and Geoff Hinton. Convolutional deep belief networks on cifar- 10. Unpub- lished manuscript, 40(7):1-9, 2010.
[40] Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing Istm language models. arXiv preprini arXiv:
2017.
[41] Iulia Turc, Ming-We Wiig Chang, Kenton Lee, and Kristina Toutanova. Well-read students learn better: On the importance of pre-training compact models. arXiv preprint 10Xv::9088.0862222 2019.
[42] Jacob Devlin, Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 2018.
[43] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 36(11):2278-2)) 2324, 1998.
13


Reviews:
[{"review_id": "yImBJjAo59p", "reviewer": "Reviewer_baYc", "summary": "This paper considers the problem of minimizing the sum of a differentiable loss function over a set of examples and\nbuilds 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:\n* 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.\n* 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.\n* 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.\n\nYucheng 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", "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?\n\n(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?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper makes a solid contribution to an important problem in machine learning.\n* 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.\n* The paper is well-written and the flow of ideas is generally easy to follow.\n\nWeaknesses:\n* 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.\n* 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. \n\nComments:\n* 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$. \n\nI did not thoroughly check the proofs provided in the appendix.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "veclbtr_Yi2", "reviewer": "Reviewer_UoVJ", "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.", "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? \n\n* 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? \n\n* 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?\n\n* Would it make sense to run Herding just once at the first epoch to obtain a good ordering? \n\n* 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?\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nGiven 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.\n\nOverall, the writing is clear and the paper is well organized so it is easy to follow. I spotted a minor typo:\n\n* In Theorem 3 and Lemma 4, it says Algorithm 6. Do you mean Algorithm 4?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "R8GYZ-BODx", "reviewer": "Reviewer_nHa9", "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. \n\nThis 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. \n\nTheoretical analysis shows an improvement from $O(n^{1/3}T^{\u00002/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. \n\nUsually $n$ is very large in machine learning (deep learning) applications, so even $n^{1/3}$ is significant improvement. \n\nAuthors 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. \n\n\n ", "questions": "1) Is it possible to get results under bounded variance assumption or more general assumption? \n\n2) 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?\n\n3) Is it possible to apply the new approach to find a better permutation to use it for Shuffle Once even with some additional computations?\n\n4) Is it possible in general to apply new technique for convex problems?\n\n5) How can you estimate $f^*$ to calculate alpha parameter? \n\n", "limitations": "As I mentioned before there are three main limitations:\n\n1) Analysis is made only for non-convex functions, convex and strongly convex analysis is desirable. \n\n2) The current assumptions are reasonable, but not standard. The comparison with previous results under the same assumptions.\n\n4) $f^*$ is used for alpha parameter, but it is usually unknown.\n\n3) Experimental evaluation is not transparent. Additional descriptions of tuned parameters is also needed. \n\nOverall, I believe that this paper has good quality with some limitations. I lean towards to weak accept. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis 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. \n\nThe 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. \n\nThe 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. \n\nThis paper has a lot of experiments with different large neural networks showing how this method works in practice.\n\nWeaknesses:\n\nThis 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. \n\nThis 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. \n\nThis 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. \n\nSmoothness 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}$. \n\nBounded Gradient Error: \n$\\text { For any } j \\in\\{1, \\cdots, n\\} \\text { and any } \\boldsymbol{w} \\in \\mathbb{R}^{d} \\text {, }$\n\n$\\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$.\n\nThis assumption is stricter than classical bounded variance assumption, since the new bound holds for any index $I$, but not in expectation. \n\nIn theory parameter alpha depend on $f^*$ value which is usually unknown. \n\nThis 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.  \n\n\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept