A General Analysis of Example-Selection for Stochastic Gradient Descent
Authors: Yucheng Lu
Si Yi Meng
Christopher De Sa
Venue: ICLR 2022 Spotlight (2022)

Abstract: Training example order in SGD has long been known to affect convergence rate. Recent results show that accelerated rates are possible in a variety of cases for permutation-based sample orders, in which each example from the training set is used once before any example is reused. In this paper, we develop a broad condition on the sequence of examples used by SGD that is sufficient to prove tight convergence rates in both strongly convex and non-convex settings. We show that our approach suffices to recover, and in some cases improve upon, previous state-of-the-art analyses for four known example-selection schemes: (1) shuffle once, (2) random reshuffling, (3) random reshuffling with data echoing, and (4) Markov Chain Gradient Descent. Motivated by our theory, we propose two new example-selection approaches. First, using quasi-Monte-Carlo methods, we achieve unprecedented accelerated convergence rates for learning with data augmentation. Second, we greedily choose a fixed scan-order to minimize the metric used in our condition and show that we can obtain more accurate solutions from the same number of epochs of SGD. We conclude by empirically demonstrating the utility of our approach for both convex linear-model and deep learning tasks. Our code is available at: https://github.com/EugeneLYC/qmc-ordering.

Published as a conference paper at ICLR 2022
A GENERAL ANALYSIS OF EXAMPLE-SELECTION FOR STOCHASTIC GRADIENT DESCENT
Yucheng Lu," Si Yi Meng", Christopher De Sa
Department of Computer Science
Cornell University Ithaca, NY 14853, USA {y12967, sm2833, cmd3533
ABSTRACT
Training example order in SGD has long been known to affect convergence rate. Recent results show that accelerated rates are possible in variety of cases for permutation-bant sample orders, in which each example from the training set is used once before any example is reused. In this paper, we develop broad condition on the sequence of examples used by SGD that is sufficient to prove tight convergence rates in both strongly convex and non-convex settings. We show that our approach suffices to recover, and in some cases improve upon, previous state-of-thee toffthhe-attt art analyses for four known example-selection schemes: (1) shuffle once, (2) random reshuffling, (3) random reshufflng with data echoing, and (4) Markov Chain Gradient Descent. Motivated by our theory, we propose two new methods, we achieve unprecedented accelerated convergence rates for learning with data augmentation. Second, we greedily choose fixed scan-order to minimize the metric used in our condition and show that we can obtain more accurate solutions from the same number of epochs of SGD. We conclude by empirically demonstrating the utility of our approach for both convex linear linear-model and deep learning tasks. Our code is available at: https: / //ggttttttt com Eugenee LLC/ ///////oo/// ceeccoordeinng
example-selection approaches. First, using quasi-Monte-
INTRODUCTION
To minimize a differentiable function f Fd R, stochastic gradient descent (SGD) iteratively updates a parameter vector w E Rd starting at some we by running
w1+1 we 04
where o is the step size at iteration f, I; is data example (often minibatch of data) chosen by some
by subsampling a training dataset-for SGD to use at iteration i, and V ff 22) is an example gradient, which hope will be good approximation for the gradient of the objective fw; In the standard setup, the x's are drawn from a dataset D of size n, and f(w) = E.co LcD f(w; z), which is often referred to Empirical Risk Minimization (ERM). The order in which the example sequence Tp, T1,... are chosen is known to affect the convergence of SGD, For instance, compare so-called "random reshuffling" strongly convex objective with 7' total iterations, random reshuffling samples the x, from D without replacement and achieves an accelerated convergence rate of 1/r², while with-replacement sampling yields a convergence rate of 1/r (Bottou, 2012: Recht & Ré, 2012; Gürbüüzallaaa et al., 2021). Similar accelerated rates have been shown in other settings and for other example orders, such as shuffling the dataset once (Nguyen et al., 2020; Ahn et al., 2020; Mishchenko et al., 2020). However, schemes, and study only the
with-replacement sampling: optimizing
these analyses have mostly focused only on specific example-selectie case of ERM-type finite-sum objectives. This does not help us understand how new example orders (such as the data echoing method of Choi et al. (2019)) affect the convergence of SGD.
This paper develops general condition on the example gradients themselves that is sufficient to provide a convergence rate for SGD. Intuitively, our main result is: the convergence rate of SGD
"Equal Contribution.

---

Published as a conference paper at ICLR 2022
depends how fast the averages of consecutive example gradients ff(w; x2)) converge to the full objective gradient V fw). Using with-replacemmnt sampling, the average of m consecutive gradient examples starting at any timestep T, m in terms of the norm squared: we show SGI with any example sequence that fulfills this condition will converge at the same asymptotic rate with-replacement sampling. Alternatively, if that average converges at the faster O()m") rate typical of Thasi-Monte-Con Carlo (QMC) (Caflisch, 1998), then we show SGD enjoys the accelerated rate that random reshufiling gets. Our contributions are as follows:
+. Exi" V f(,; 24), converges to V f(w) at rate of O(/m)
We propose a new condition on the example gradients-averuee gradient error-and provide convergence analysis using this general condition for both non-convex and strongly-convex problems. We justify the validity of this condition on synthetic experiments (Section 3).
We show that many commonly used example orderings- shuffle once, random reshuffting. data echoing, Markov Chain Gradient Descent-can be analyzed as special cases under our theoretical results, which match or improve upon their existing rates in the literature (Section 4).
We propose two new algorithms: (1) QMC-based data augmentation that transforms examples via a low-discrepancy sequence, improving generalization; and (2) a greedy algorithm that sorts the examples before each epoch based on new average gradient error metric (Section 5).
Empirically, we evaluate our two algorithms on several image classification benchmarks including MNIST, CIFAR 10/100 and ImageNet. We show with QMC-based data augmentation, higher validation accuracy can be achieved without hyperparameter tuning- this suggests that QMC may be good default driver to use with data augmentation for deep learning in general. Meanwhile, the greedy algorithm converges faster both in terms of iteration and wall-clock time (Section 6).
2 RELATED WORK
Example ordering in stochastic optimization. Traditional example ordering in SGD is carried out in with-replacement fashion, which is used to ensure unbiased estimation of the full gradient (Robbins& & Monro, 1951; Bach & Moulines, 2011; I; Zhang, 2004; Bottou et al., 2018; Drori & Shamir, 2020). Significant attention has been paid to importance sampling with respect to various measures, such as Lipschitz constants (Schmidt et al., 2017; Needell et al., 2014), example gradient norms and bounds (Zhao & Zhang, 2015; Alain et al., 2015; Papa et al., 2015; Lee al., 2019), individual losses (Kawaguchi & Lu, 2020; Loshchilov & Hutter, 2015), and data heterogeneity (Lu et al., 2021). Withouttreplasemment sampling. however, is more common in practice and empirically allows faster convergence (Bottou, 2012). Among the most popular without-replacement approaches are shuffle once (SO) (Bertsekas, 2011: I; Gürbüzbalaban et al., 2019) and random reshuffling (RR) (Ying et al., 2017). In theory, Recht & Ré (2012) undertook the first investigation on convergence of RR via the noncommutative arithmetic- geomeeric mean conjecture, to which subsequent works provide counter examples (Yun et al., 2021: De Sa, 2020). HaoChen & Sra (2019) performed epoch-wise acceleration analysis on RR while Gürbüzzalaban et al. (2021) considered its convergence over infinite epochs. Safran & Shamir (2020) analyzed the lower bounds for both SO and RR methods, and their results are further polished by Mishchenko et al. (2020) via the Bregman divergence bound. Aside from manual ordering, another line of research focuses on perturbed example ordering from data echoing (Choi et al., 2019; Agarwal et al., 2020).
Quasi-Monte Carlo (QMC) is a variant of Monte Carlo (MC) methods that uses low-discrepancy sequence instead of a pseudorandom sequence. QMC has been successfully applied in a wide variety of domains including computer graphics (Keller, 1995), finance (Joy et al., 1996), and computational biology (Cieslak et al., 2008). In machine learning, using QMC in place of MC can significantly improve many techniques including variational inference (Buchholz et al.. 2018; Liu & Owen, 2021), feature mapping (Yang et al., 2014; Avron et al., 2016), normalizing flows (Wenzel et al., 2018), deep learning based PDE (Chen et al., 2019), and time series analysis (Philipson et al., 2020). For stochastic optimization, early works like Homem-de Mello (2008) and Pennanen (2005) established the asymptotic convergence of a QMC sequence in terms of the training set size, while Jank (2005) proposed replacing MC with QMC in computing the E-step of the EM algorithm. Similar to our motivation, Buchholz et al. (2018) analyzed the convergence of SGD when samples are drawn using QMC. Their approach differs significantly from ours in that their method draws an independent unbiased length-b QMC sequence for each minibatch, while our examples come from contiguous subsequences of length-7 QMC sequence that is used across all iterations.
Quasi-Monte Carlo.
2

---

Published as a conference paper at ICLR 2022
3 EXAMPLE-GRADIENT AVERAGES AND SGD CONVERGENCE
In this section, we describe our setup, define the average gradient error condition we are proposing, and state our main result. Our objective is to minimize continuously differentiable function f IR + E using examples 2, from some set X retrieved at each iteration t. We make the usual assumption that both the loss gradient and the example gradients are L-Lipschitz continuous. Assumption (I-Smoothnesss) For some < (C, for any u, E TRdd and any example x E X, (u;;); - ( x=)l < L. ||u - wll and || s(u) - vs(0)ll S L. ||u v||-
We propose new condition on the average gradient error. Informally, this condition bounds how averages of consecutive example gradients approximate the objective gradient. Formally,
Assumption In the context of Equation (1), we say that the example sequence zo, Z1.... is (7,, C, concentraain for y E [1,2], C' > 0, Φ 2 0, if any timestep 2 0 and any m > 0,
1 T+
Vf(w===)) f
S m (0R (C*+
where wi is the weight parameter vector arrived at after T SGD update steps in Equation (1).
The constants C. and & here may depend the total number of iterations T: specifically, they may absorb logarithmic factors like log(T + m2 typical a QMC error bound, where 8 is the dimension of the sample space. In addition, when the {ar)'s are random, holds with high probability. Furthermore, it suffices to show that the incquality holds for any wt our requirement that it holds only for the specific w, arrived by SGD is weaker. We can develop intuition about Assumption 2 by considering familiar cases:
will show that this assumption
For general with-replacement sampling, the sum (2) is a sum of independent random variables; so, a concentration argument would yield Assumption 2 with y 1 with high probability. For general rethout-replacement sampling from a dataset of size n, any whole-epoch subsequences from the sum in (2) will cancel to zero, so we expect that sum to have magnitude (n) independent of m, and thus Assumption should hold with y = (Propositions to 4).
For low-discrepancy sampling, multiplicative log(T + m) term: this is the classic error rate for QMC (Proposition 6).
would expect Assumption 2 to hold with y along with
In Section 4, we will make this intuition rigorous with high probability under the bounded gradient error assumption. This intuition illustrates both how Assumption 2 can cover previously analyzed settings and how it can generalize to cases not previously studied, such as QMC data augmentation. Also observe that Assumption 2 is easily adapted to minibatch SGD: it holds for the eingle-example case, it should also hold with modified constants for minibatches of size b (consisting of averages of b consecutive example gradients) by substituting m r> mb.' Since this is straightforward, for simplicity of presentation our theory focuses on the batch-size-1 case. Our analysis is based on the following key lemma, which bounds the evolution of SGD over an "analysis phase" of m steps.
Lemma 1. Suppose our setup satisfies Assumptions and and that For all timesteps T 2 0, let m. > O be some integer such that 30m! 1/2 & am S 1 objective at timestep m is bounded by
a constant step size
e1. Then the
f(w++m) S fw+) famm (w+)11 2am-- C-2
By applying this lemma inductively and choosing the step size appropriately, we can derive conver- gence rates for SGD in variety of settings. Note that while here for simplicity we state results for fixed step size, Lemma I can also be used to get essentially the same rates for diminishing step size schemes, which we analyze in Appendices A.2 and A.3. In what follows, we let f* be the global minimum of f. let A = (wp) f², and use Ô to hide logarithmic terms in the problem parameters such as C, 4. L. A, and e, while treating y as constant.
Theorem (Non-convex case). Suppose that our setup satisfies Assumptions / and 2, and let c > 0 be any target error. Using SGD (1) with a constant step size a oL [[AC/ //1 the number of steps T needed to achieve min;=0.... V f(wr]] < e² is at most
T
48LA
4C + 36) 3
2/1 Ô (ChIA + L//LA + 203
'The only technical subtlety is that the iterates w, of SGD would vary with minibatch sizes.
3

---

Published as a conference paper at ICLR 2022
Online
Offline
Online
Offline
10'4
10
10
10"
10-1
10-*
10
10"4
10
IB Liitrrm
13 Uniiom
10.*
Sobu
Sebsl
Sabol
5R
10-40
IE Unitemm
52
50
5ibul
50
107 10'
13
1D
12
13
10
(a) Distance to optimum over iterations
(b) Average gradient enror (LHS of Assumption 2)
Figure I: Comparison of sampling schemes on a synthetic least squares problem.
Observe that when y 1, this gives the standard c- rate expected for non-convex SGD, and for Y 2, this gives us the accelerated c-3 rate of shuffling methods. We can get an even faster rate if f satisfies the ---oooa--oojsiieeeee
(PL) condition || [w)]] ( - f*), which generalizes strong convexity and has been applied before in the study of sample orders (Mishchenko et al., 2020; Ahn et al., 2020): in particular the following theorem holds for μ-strongly convex functions.
Theorem 2. Suppose that I satisfies the p-PL. condition and our setup satisfies Assumptions and 2. Let > be any target error, and K. = 1/ju be the condition number of the problem. Using SGD (1) with a constant step size a GT. [88C* (ME") + +942)411 ttee number of steps T needed to guarantee fWWF) - f S e² is at most
T= 12x [ log (
[ SC pe + 9022
V/ =
(
Ca/T (-alT plireer7
+ xx22/7 + xx).
Observe that when 7 = 1, this recovers the ordinary T = KEe rate we usually get for strongly convex SGD, and when 7 = 2 we get a faster rate of Ice These theorems together show that our Assumption 2 is sufficient to show the convergence of SGD, and the convergence-rate parameter of the assumption translates affect the convergence rate of SGD. This validates our intuition that faster convergence of averages of consecutive example gradients to the full gradient V fw) leads to faster convergence of SGD.
synthetic 10-dimensional strongly-convex problem. The first setting we consider is the expected risk minimization of R(w) E [(xTw y) where x NO, Ia) and I ~ N(x"=", 1) for some optimal value w We run SGD in an online fashion-an at iteration we draw samples (xx, y:) from the underlying distribution to compute V x;) used in the update. We compare drawing these samples indepen- dently at random against drawing using a QMC sequence (Sobol in i0, 1] via an inverse transform, using for both cases the same diminishing step size scheme selected to minimize the expected risk for the random-sampling case-the optimal step size scheme for vanilla SGD. The online plot of Fig. (a) shows that the convergence rate is strictly superior with QMC, which achieves a 0(1P) rate compared to the (1)() rate of random sampling, which is what Theorem 2 predicts.
Synthetic experiments. We quickly validate these results
We also evaluate the offline setting, where we draw n independent examples from the same distribution to form a training set, and minimize the empirical risk Rn (w) = 1 >i (I. - 3;)². This corresponds a least squares problem with optimal solution w, We run SGD epoch-wise for K epochs, in which we compare sampling from the training set uniformly with replacement (IID Uniform), random reshuffling (RR), shuffle once (SO), and sampling using one QMC sequence in [0, 1] of length T = nkK followed by mapping to example indices (Sobol). In the offline plot of Fig. I(a), we see that the low-diserepancy methods all yield an accelerated rate compared IID Uniform, which again validates our theory. Additional details can be found in Appendix A.1.3.
With the same synthetic setup, we also verified our bound in Assumption by measuring the average gradient error over sequence of examples. The fixed point w, is arbitrarily set to the origin. For the online setting (left of Fig. 1(b)), we use the same set of examples as in the SGD experiments above starting at = 0. Similarly, in the offline setting, we go through the examples spoch-wise As see, the sample orderings given by QMC, RR and SO (offline only) indeed give us an accelerated rate of decrease in the average gradient emrr as we increase m (y 2). justifying our main assumption.
4

---

Published as a conference paper at ICLR 2022
4 ANALYSIS OF EXISTING SCAN ORDERS
In this section, we illustrate the power of our approach by proving convergence rates for example- selection methods proposed and analyzed in previous literature. For each method, show Assump- tion 2 holds with high probability, and then by applying Theorems and 2 to these results, we show how existing rates for these methods can be recovered and in some ways improved upon. To the best of our knowledge, these are the first high-probability results for shuffle once and random reshuffle for general non-convex optimization. When using finite training set of examples, we let n denote its size, let the examples be indexed as x ,x!",, ......"!hh (x-1) (to avoid confusion with 2t, the example used by SGD at step t), and let T nK denote the total number of iterations after K epochs. We
will also require the following standard assumption that bounds the error of single example gradient.
Assumption 3. For all examples x E X and points w RR, there exists A, B 2 0 such that the gradient errors satisfy [V, V fw))ll I A B² [
Shuffle once (SO). In the shuffle-once variant of SGD, a single permutation a of {O...., n -13 is chosen uniformly random at the start, and the examples are used repeatedly in that order: explicitly, T. = (t mod n)), One way to analyze shuffle-once is to prove Assumption 2 for permutation-base methods generally.
Proposition 1. Let Assumptions 1 and 3 hold, and suppose that we are using permulation method of sampling, that is, any method such that Tkn; #kn+1,.... Fkn+n-1 is a permutation of r10) .2!1) ...... ..!n-)) for all epochs k 0. Any such method satisfies Assumption 2 with y 2, C === n² A2 and $2 nn² B²2
This immediately lets us recover previous rates up constant factors, but case where we are learning over a bounded region, we can prove a stronger result for shuffle once.
do better. In the
Proposition 2. Suppose that we are using the shuffle once variant of SGD to learn over region B E &d of radius at most R, such that the iterates are guaranteed to remain within this region. Assume that for all w B and all examples x in the training set of size n, Assumption (L- Assumption 2 holds with
Smoothness) and Assumption 3 hold. Then with probability at least
C (dA2 - (n + B²)), and x² = (...
In comparison previous results and our rate implied by Proposition this improves the dependence from to Vnd, which a significant improvement over the best rates for shuffle once available in the literature when the dimension is small relative the training set size. In particular, if we set B- = O and consider small e, our rate the non-convex case becomes
T = δ ALAvvnd
which implies e² Ó (ALA) (ALA))/3 (md) (/3 1/3 - -(((A) nk
T
This rate matches that for shuffle once achieved in Nguyen al. (2020, Corollary 1) in terms of up to logarithmic factors. In the p-PL (or strongly convex) case for B = O, we again obtain a rate matching that of Nguyen al. (2020), Ahn et al. (2020), and Mishchenko al. (2020):
T= δ
AA
ad
which implies
2² ~
= 5 A2d jonK"
Random reshuffling is similar to shuffle once, except that a new ordering is chosen each epoch: sampling the dataset without replacement. Concretely, if o denotes the permutation used by random reshuffling at the leth epoch, then 2; [/((:// (t mod n)).
Random reshuffling (RR).
Proposition 3. Suppose that we are using the random reshuffling variant of SGD. Assume that for all E Rdd and all examples, Assumption I (L-Smoothnesss and Assumption 3 hold. For some p E (0, 1), set the constant step size to satisfy a < (max { [1460BnL log (4e2T/p) 2m Then with probability at least - p, Assumption 2 holds with = 2, C = Ö(nA2) and 22 = Ó(.B)).
Setting B our rate in the non-convex case now becomes
T = δ ALAVA
which implies < Ö( (ALA) 373 (m) = Ō n
T
Thhe prohahility p is only present in log terms in these expressions, does not appear in the Ô
5

---

Published as a conference paper at ICLR 2022
Here match the best rate obtained by Mishchenko et al. (2020, Corollary 3) in the small setting. In the puPPL (or ttooglyyconven. case, we get
T=
mA
which implies
e {
A A2 pT = Ō
N x² j
As in shuffle once, here our rate for random reshuffling matches that obtained by Nguyen al. (2020) and Ahn et al. (2020), as well as Mishchenko et al. (2020) albeit with a slightly worse dependency on K. It's worth noting that for simple quadraties, RR and SO are only faster than with-replacement SGD when K 2 1/2 (Safran & Shamir, 2021).
Random reshuffling with data echoing. Data echoing is technique that can be easily imple- mented in a machine learning training pipeline to increase throughput and improve performance. was first introduced and tested empirically by Choi al. (2019) and analyzed by Agarwal et al. (2020). The idea is to perform multiple SGD updates on each example (or minibatch) before proceeding to the next. By "echoing" examples we allow more time for upstream data loading and preprocessing, and consequently decrease downstream GPU idle time for gradient computation. For simplicity, we also use a fixed number of echos e as in Agarwal et al. (2020). Concretely, a c-echoed version of sample order 2 is given by 2, [t/e]] Data echoing can essentially be applied to any examplc-ordering scheme, and here we provide one analysis under random reshuffling. The justification for Assumption 2 under random reshuffling with data echoing follows essentially without modification from the = 1 version in the previous subsection.
Proposition 4. Suppose that we are using the random reshuffling variant of SGD, where each example is echoed times using the same step size in RR. Under the same assumptions in Proposition 3, with probability at least 1 p. Assumption 2 holds with ? 2, C Ö(enA?) and x² O(n.B²)
It immediately follows that data echoing should get the same convergence rates we showed in Section with A and B² multiplied by c. Although Agarwal et al. (2020) also provided an analysis for data echoing. they require that the examples are sampled independently, rather than the random reshuffling setting that is more commonly-use accelerated e rate that shuffled methods enjoy. Another advantage of our analysis is that the proof follows exactly from that of vanilla random reshuffling, from which the constant c simply propagates.
as a result, their analysis did not achieve the
Markov chain gradient descent (MCGD). To illustrate the versatility of Assumption 2, show how it can be satisfied by problem where the objective is not a finite sum and where / 2. Consider f(w)) Be (w:: {)] with some underlying distribution E. Running SGD then requires that each iteration f. we draw V f &,) where & ~ E: however, sampling from E can be intractable. The method of Markov Chain Gradient Descent addresses this problem by sampling the & from the trajectory of a single Markov chain with stationary distribution E (Sun et al., 2018). The intuition that although at early iterations the é's have not converged to their true distribution, the iterates visited by SGD are also far from the optimum, thus larger approximation error in the early Ç's is rather harmless. As we continue iterating, the Markov chain will mix as SGD converges. We show that the convergence of MCGD can be bounded in terms of the mixing time of that Markov chain.
Proposition 5. Suppose that we use samples It. from a Markov chain with mixing time bmix- Assume that for all w E IR and all examples It, Assumption 3 holds. Then with probubility at least p. Assumption 2 holds with y = 1, C2 (A22t2 ) and 22 = Ö (2 pmis)
It follows that for non-convex optimization in the B case, our convergence rate is given by
T == LA
which implies e² S Ö Almo VLA T
Sun al. (2018, Theorem 2) use a diminishing step size (1/v)) to obtain T= O(c 3/-x), where E (4/2, 1). In contrast, our rate is faster and holds with high probability instead of in expectation.
5 NEW EXAMPLE-SELECTIE
METHODS FOR FASTER CONVERGENCE
The amalysis in Section 4 focused on recovering the convergence rates for SGD with known example- ordering algorithms. In this section, we propose two new saappe--election approaches that allow faster convergence: QMC-based data augmentation and greedily minimizing the metric in (2).

---

Published as a conference paper at ICLR 2022
Algorithm 1 [Example-rdere SGD via Greedily Minimizing Average Gradient Error
Input: step size a, number of iterations T, random projection matrix II, buffer for gradients estima- tion: 9: + 0, Vi E {0, .... n - 1). < 0, initial weights wo, initial permutation do. T/n 1 do
1: for = 0,
2: Initialize: 9i < 0, Vi E {0. n 1}:9 g 0II 0.
3: fori= 0, , 1 do
4:
Update the model parameters: Win+i-1 <- Win+i V s( xlox()))
5: Update the buffers: (oz(i) k IV (WWttttt: 9 - + Do.(o)-
6:
end for
7:
for i
do (1) + arg min
= O,
Σ (g) - m/mil (EZU(r)
8:
I 1--UU fo (1))
rE 1-1
9: end for
10: end for
11:
return WT
QMC-based data augmentation. In many scenarios where only limited examples are given, we want to augment the dataset for better generalization. More formally, given a transform function A that takes example and random variable Ç uniformly distributed in [0, 1Je as input, where denotes the dimension augmentation space, the augmented objective for a dataset of size n is
f(w)
= 3 .CD
Ex-up.rr (w: A(z, ()) = 1 Σ frr fww: ()) dç.
(3)
D
The rationale is that by performing some reasonable random transformation on a given example, we assume the output would be another example that is identically distributed, and the expected value models an infinitely-large training set consisting of such transformed examples. For example, in an image classification task, we could set s and have A(z, () output the image x rotated by an angle of 20 (2ç- - 1), modeling that a slight rotation of an image should preserve its label.
QMC can approximate this expectation with a low-discrepancy sequence of & drawn from the s-dimensional unit cube [o, 1|a. Examples of such sequences include the Halton and Sobol sequences (Drmota Tichy, 2006). QMC is especially favorable for data augmentation because is usually small in most data augmentation methods. We propose use QMC for data augmentation together with random reshuffling. Concretely, if Co. Si,... is our low-discrepancy sequence and σ denotes the permutation used by random reshuffling in the kth epoch, then we propose to the example Iy = A(x ("Ly/j'f mod n))
(Cis/ teL//n (1 mod ) That is, when we sample example in epoch k, we use the (A: + i)th element of the low-discrepancy sequence. This is not the only reasonable way of combining QMC and RR: it is just one way we found to work well. In theory
would expect the approximation error here to decay at the rate O()m²), instead of the O(7m)) of the random sampling that is standard for data augmentation. To prove this rigorously, make two additional assumptions which are commonly used in analyzing QMC sequences (Aistlcitner & Dick, 2014).
Assumption (Bounded gradient variation). There exists a constant V > 0 such that for any fixed W E IRd and x E X. the example gradients as function of ( under QMC data augmentation, F(C)
f[;; A(x, {)), has Hardy-Krand Krause variation (Tezuka, 2000) at most V, that is VIK(F)) V.
Assumption 5. The QMC sequence {Gr) has low star cia-ddicryppacy (Owen, 2003): for all m > 0,
1 Σ 1( E [0,a)) - Na, 3-1
S CCMC log(m)"
sup "E(o,1]
1-0
< a, -, d3 for some constant COME- where (0, = E [0, 10
Proposition 6. Suppose that we are using the random reshuffling variant of SGD with QMC data augmentation as described. Assume that for all 4 and 5 hold for Equation 3. For some p E (0,1), set the step size to be a constant such that < (maax]1460Bn) 1444414464n -oog(eeT/pp) 22L Then with probability at least 1 - p, Assumption 2 holds with 2, C = = (og nAA²) and x² = Ō(n
Ee and all examples, Assumptions
Comparing it with Proposition 3, this QMC variant enjoys the same 0(1r))) rate we get for vanilla random reshuffling: to our knowledge, this is the first accelerated rate for learning with data augmen-
7

---

Published as a conference paper at ICLR 2022
0.50
HD Uniform (tuned)
Unifom (tuned)
0.45
QMC (untuned)
ituned)
Accumaty
Valtaaion Losa
1.25
OMC (tuned)
OMC luntuned)
ValtSation Accuracy
50
92.0
0.40
Vallgeton
91.5
07
0.35
1.20
93.0
HE-Unfoom
GMC (untuned)
QMC (untuned]
0.25
100
125
175
200
125
GMC (urred)
150
175
120
140
160
65
120
OMC (uredi
160 Epoch
200
Epoch
Epach
Epocis
(a) Validation of ResNer20 on CIFARIO
(b) Validation of ResNer20 on CIFAR100
Figure 2: Data augmentation with II-uunifomm (standard) and QMC-based methods on CIFAR.
tation. In addition the theoretical advance, we demonstrate in Section 6 that our QMC variant can achieve better validation performance in practice in multiple applications.
Better example ordering via greedy selection. Taking a closer look at Assumption 2, the magnitude of the left-hand side plays crucial role in the convergence. In the ERM setting, this motivates us to select permuted example order that minimizes this expression, following which SGD would converge with minimized average gradient error. However, naively constructing such sequence tedious as iterating over all the т, m > and all permutations can be computationally intensive. In light of this, we apply several approximation techniques into the construction and formulate it into Algorithm 1. The first technique is to use stale gradients, i.c., using the gradients computed at each epoch to estimate the sequence used in the next epoch (line 5 in Algorithm 1). The intuition is that based on the smoothness of loss function (Assumption 1), we would expect the stale gradients to approximate the current gradients with tolerant approximation error as long as the step size is reasonably small. The second technique is random projection (line 9): we search lower-dimensional space, which allows faster construction and reduces memory use (see similar strategies of using smoothness and dimension reduction techniques in (Caflisch, 1998)). Because this a selection-by- by-eemutatioonn method, under Assumption our greedy selection method will trivially satisfy Assumption 2 with 7 = 2, C = nA. and & = nB (see Proposition 1).
6 EXPERIMENTS
Table 1:
Topl validation accuracy (%) of ResNet18 on ImageNet. The original one the standard benchmark provided by PyTorch.
In this section we evaluate our new algorithms on several deep learning benchmarks. First, we compare QMC-based data augmentation against IID-uniform augmentation CIFARI0/100 and ImageNet datasets. Second, we compare greedy ordering (Algorithm 1) with RR and SO, and show how to further accelerate it with randomly projected sorting. Other details on the experimental setup can be found in Appendix 1.1.1. Each experiment is repeated 10 times with consistent seeds among the algorithms.
Original
Uniform (tuned)
QMC (untuned)
69.76
70.19
70.48
QMC-based data augmentation. We start by training ResNet20 on CIFAR1O and CIFAR 100, where discrete and continuous data augmentations are applied, respectively. Specifically, CIFARIO uses random crop and random horizontal flip while CIFAR 100 uses an additional random rotation of 15 degrees. To apply the QMC-based data augmentation, appropriate dimension using the qmcpy package (Choi et al., 2020+), and then replace the pseudo- random sequence used in the original random augmentation pipelines with that Sobol sequence. We run the bascline IID-unifomm method with finetuned hyperparameters (weight decay 10 which reproduces the result from He et al. (2016) with an error rate 8.4%. Then we run QMC-base augmentation with the same hyperparameter (untuned) and finetuned counterparts, with a grid search over weight decay values in {r 10-10-10- 10- From Figure 2 we observe the QMC-based augmentation consistently outperforms the baseline methods, even without hyperparameter tuning. Comparing Figure with He et al. (2016), we observe the QMC-based augmentation allows ResNet20 to reach comparable validation accuracy ResNet44 while requiring only 40% as many parameters (0.27M vs 0.66M). We run a t-test on these results (in Appendix 1.1. to show the validation accuracy from the two augmentation methods different statistically significantly (p-value p 7 10-7 on
first generate Sobol sequence of
8

---

Published as a conference paper at ICLR 2022
0.27
Shutfle
0.260
Shuffle
Random Reshuffing
Random Reshuffling
Validation Accurap
2.2.5
Training Leg
0.26
Greedy w OR
Training Lass
0.253
Greedy w/ OR
Greedy sparse+OR
0.250
Greedy
02.0
0.25
01.5
Shuffle Once
0.245
Bandom Reshuffinn
Greedy wi QR Greedy w/ sparse+QR
0.240
1500
1000
1500
Epoch
Timelsecl
Timetsec)
(a) Logistic Regression on MNIST. The greedy algorithm reuses the hyperparameters finetuned on RR.
0.020
0.030
92.0
Shuffic
Shuffle
Random Reshufffing Greedy wi
Random Reshuffling
391.
Training Lozp
30.018
Treining Lass
0.025
Greedy OR
91.0
Greedy sparze-OR
Greedy sparse+QR
Shumee Once Reshuffling Greedy OR
0.036
0.020
90.0
0.014
Greedy wi sparse-OR (tuned)
Greedy
150
160
170
180
190
200
2500
3000
3500
4000
$9.800
2000
2530 3000 3500 4000 Timelsec]
Epoch
Timelsec)
(b) ResNet20 on CIFARIO. The greedy algorithm able to converge faster when optimizing the same loss function while achieving SOTA validation accuracy with mild tuning.
Figure 3: Comparison between Algorithm and RR/SO on MNIST and CIFARIO.
CIFARIO 10 and 7=0.036 on CIFAR Importantly, this improvement comes essentially for free, as generating low discrepancy sequences in low dimension has very little overhead.
We also evaluate our method on fine-tuning ResNet18 on ImageNet. We apply different augmentation methods on pre-trained model and train for additional epochs with step size 10-4, We report their Top1 accuracies in Table 6, which shows that our QMC method improves the validation accuracy by 0.3% compared to the same number of epochs of fine-tuning using random sampling.
Better example ordering via greedy selection. In this section we evaluate Algorithm 1 on two benchmarks: Logistic Regression on MNIST and ResNet20 on CIFAR1O. As discussed, sorting the stale gradients naively could incur substantial overhead on memory and computation. To mitigate this, we adopt two methods: random projection and QR decomposition. The former is mainly to reduce storage: we obtain gradient computed at some time in an epoch and project it into lower-dimensions space before storing it. Classic ways of projection include Gaussian projection or random sparsification: we adopt the latter as it does not require storing the projection matrix, which minimizes the storage cost. After we obtain all the stale gradients, we concatenate them into a matrix and perform QR decomposition before sorting, which allows while preserving the order of gradients since the inner products between any two tensors will remain the same Gander (1980). We set the target dimension to be of 10% size of the original space. In the spirit of evaluating the applicability of Algorithm I, we do not perform hyperparameter tuning in this section but reuse the ones tuned in the literature on Random Reshuffling.
sort in low-dimensional space
We plot the results in Figure 3. In Figure 3(a) we observe greedy algorithms can consistently converge faster than RR and SO epoch-wise with optimizing the same loss function. When QR is used without projection, the algorithm is able to reach higher validation accuracy but converges slower with respect to the wall-clock time. On the other hand, when we use random sparsification additionally, the algorithm converges faster with respect to both epoch and wall-clock time without compromising the validation accuracy. For CIFARIO, we observe the greedy method can converge faster when optimizing the same loss as other baselines, and achieves higher validation accuracy when fine-tuned.
7 CONCLUSION
We present a unified analysis on example orderings used in SGD, which generalizes several widely- used orderings in the literature. We propose a greedy algorithm that allows faster convergence via constructing better example order with approximate sorting techniques, well as QMC-based augmentation that achieves higher validation accuracy on multiple benchmarks. One potential future direction is designing example orderings to more efficiently minimize the average gradient errors.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The authors would like thank A. Feder Cooper and anonymous reviewers from ICLR 2022 for their valuable feedbacks on earlier versions of this paper.
REFERENCES
Naman Agarwal, Rohan Anil, Tomer Koren, Kunal Talwar, and Cyril Zhang. Stochastic optimization with laggard data pipelines. In Advances in Neural Information Processing Systems, 2020.
Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. SGD with shuffling: optimal rates without component convexity and large epoch requirements. In Advances in Neural Information Processing Systems, 2020.
Christoph Aistleitner and Josef Dick. Functions of bounded variation, signed measures, and general Koksma-Hlawka inequality. arXiv:I406.022 0230, 2014.
Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron C. Courville, and Yoshua Bengio. Variance reduction in SGD by distributed importance sampling. arXiv:1511.06481, 2015.
Haim Avron, Vikas Sindhwani, Jiyan Yang, and Michael W. Mahoney. Quasi-Monte Carlo Feature Maps for Shift- Invarianv Kernels. The Journal of Machine Learning Research, 17:120:1-120:38 2016.
Francis R. Bach and Eric Moulines. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, pp. 451-459, 201
Bernard Bercu, Bernard Delyon, and Emmanuel Rio. Concentration inequalities for sums and
martingales. SpringerBriefs in Mathematics. Springer, 2015.
Dimitri P. Bertsekas. Incremental Gradient, Subgradient, and Proximal Methods for Convex Opti- mization: A Survey. In Optimization for Machine Learning. The MIT Press, 2011.
Léon Bottou. Stochastic gradient descent tricks. In Neural networks: Tricks of the trade, pp. 421-436. Springer, 2012.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-3) -112,, 2018.
Alexander Buchholz, Florian Wenzel, and Stephan Mandt. Quasi-Monte Carlo Variational Inference. In Proceedings of the International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 667-676. PMLR, 2018
Russel E. Caflisch. Monte Carlo and quasi-Monte Carlo methods. Acta Numerica, 7:1-49, 1998.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):7,, 2011.
Jingrun Chen, Rui Du, Panchi Li, and Liyao Lyu. Quasi-Monte Carlo sampling for machine-learning partial differential equations. arXiv:/9/ 1.01612, 2019.
Dami Choi, Alexandre Passos, Christopher J. Shallue, and George E, Dahl. Faster neural network training with data echoing. arXiv: 2019.
S.-C. T. Choi, F. J. Hickernell, M. McCourt, and Sorokin. QMCPy: quasi-Monte Carlo Python library, 2020+. URL https::///// /ttp://gttth com/ MMccooftwaree/MMSotttoo
Mikolaj Cieslak, Christiane Lemieux, Jim Hanan, and Przemyslaw Prusinkiewicz. Quasi-Monte Carlo simulation of the light environment of plants. Functional Plant Biology. 35(10):837-849, 2008.
Christopher De Sa. Random reshuffling is not always better. Advances Neural Information Processing Systems, 2020.
10

---

Published as a conference paper at ICLR 2022
Michael Drmota and Robert F/ Tichy. Sequences, discrepancies and applications. Springer, 2006.
Yoel Drori and Ohad Shamir. The complexity of finding stationary points with stochastic gradient descent. In Proceedings of the International Conference Machine Learning, volume 119, pp. 2658-2667. PMLR, 2020.
Walter Gander. Algorithms for the QR decomposition. Seminar für Angewandte Mathematik: Research report, 80(02):1251-1268 1980.
Mert Güürbüzbalaban, Asuman E. Ozdaglar, and Pablo A. Parrilo. Convergence rate of incremental gradient and incremental Newton methods. SIAM Journal on Optimization, 29(4)2554-2265, 2019.
Mert Gürrüzzbalaaan, Asuman E. Ozdaglar, and Pablo A. Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, 186(1):49 84, 2021.
Z. HaoChen and Suvrit Sra. Random shuffling beats SGD after finite epochs. In Proceedings of the International Conference on Machine Learning, volume 97, pp. 2624-2633, 2019.
Thomas P. Hayes. A large-deviation inequality for vector-valued martingales. Combinatorics, Probability and Computing, 2005.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Tito Homem-de Mello. On rates of convergence for stochastic optimization problems under non- independent and identically distributed sampling. SIAM Journal on Optimization, 19(2):524-551, 2008.
Wolfgang Jank. Quasi-Monte Carlo sampling to improve the efficiency of Monte Carlo EM. Compu- tational statistics & data analysis, 6884)7685-70, 2005.
Corwin Joy, Phelim P. Boyle, and Ken Seng Tan. Quasi-Monte Carlo methods in numerical finance. Management Science, ((66):92-9338 1996.
Kenji Kawaguchi and Haihao Lu. Ordered SGD: A new stochastic optimization framework for empirical risk minimization. In The 23rd International Conference on Artificial Intelligence and Statistics, volume 108, pp. 669-679, 2020.
Alexander Keller. A Quasi-Monte Carlo Algorithm for the Global Illumination Problem in the Radiosity Setting. In Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, pp. 239-251. Springer New York, 1995.
Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10657-10665, 2019.
David A. Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathe- matical Society, 2017.
Sifan Liu and Art B. Owen. Quasi-Newton Quasi-Monte Carlo for variational Bayes. arXiv:2104.02865, 2021.
Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. /5I1::/51..063/ 2015.
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, pp. 7145-7155. PMLR, 2021.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. In Advances in Newral Information Processing Systems, 2020.

---

Published as a conference paper at ICLR 2022
Deanna Needell, Rachel Ward, and Nathan Srebro. Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm. In Advances in Neural Information Processing Systems, pp. 1017-1025, 2014.
Lam M. Nguyen, Quoe Tran-Dinh, Dzung T. Phan, Phuong Ha Nguyen, and Marten van Dijk. A unified convergence analysis for shuffling-type gradient methods. arXiv:2002.082466 2020.
Art B. Owen. Quasi-Monte Carlo sampling. Monte Carlo Ray Tracing: SIGGRAPH, 1:69-88, 2003.
Guillaume Papa, Pascal Bianchi, and Stéphan Clémençon. Adaptive sampling for incremental optimization using stochastic gradient descent. In Algorithmii Learning Theory, volume 9355 of Lecture Notes in Computer Science, pp. 317-331. Springer, 2015.
Teemu Pennanen. Epi-convergent discretizations of multistage stochastic programs. Mathematics of Operations Research, 30(1):245-256, 2005.
Pete Philipson, Graeme L. Hickey, Michael J. Crowther, and Ruwanthi Kolamunnage- Dona. Faster Monte Carlo estimation of joint models for time-to-event and multivariate longitudinal data. Computational Statistics & Data Analysis, 11:1107010, 2020.
Benjamin Recht and Christopher Ré. Toward noncommutative arithmetic- geometric mean inequality: Conjectures, case-studies, and consequences. Conference on Learning Theory, volume 23, pp. 11.1-11.24, 2012.
Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Mathemati- cal Statistics, 22(3):400 - 407, 1951.
Itay Safran and Ohad Shamir. How good is SGD) with random shuffling? In Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 3250-3284. PMLR, 2020.
Itay Safran and Ohad Shamir, Random shuffling beats SGD only after many epochs on ill-conditioned problems. arXiv:2/06.06888 06880, 2021.
Mark Schmidt, Nicolas Le Roux, and Francis R. Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):3--112 2017.
Tao Sun, Yuejiao Sun, and Wotao Yin. On Markov chain gradient descent. In Advances in Neural Information Processing Systems, pp. 9918-9927, 2018.
Shu Tezuka. Discrepancy theory and its application to finance. In IFIP International Conference on Theoretical Computer Science, pp. 243 256...66555 Springer, 2000.
Florian Wenzel, Alexander Buchholz, and Stephan Mandt. Quasi-Monte Carlo Flows. In Proceedings of the 3rd Workshop on Bayesian Deep Learning, 2018.
Jiyan Yang, Vikas Sindhwani, Haim Avron, and Michael W. Mahoney. Quasi- Carlo Feature Maps for Shift-Invariant Kernels. Proceedings of the International Conference on Machine Learning, volume 32, pp. 493, 2014.
Bicheng Ying, Kun Yuan, Stefan Vlaski, and Ali H. Sayed. On the performance of random reshuffling in stochastic learning. 2017 Information Theory and Applications Workshop (ITA), pp. 1-5. IEEF, 2017.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Open problem: Can single-shuffle SGD be better than reshuffling SGD and GD? In Conference on Learning Theory, 2021.
Tong Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. Proceedings of the International Conference on Machine Learning, volume 69, pp. 116, 2004.
Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, pp. 1-9, 2015.
12

---

Published as a conference paper at ICLR 2022
A
APPENDIX
TABLE OF CONTENTS
A.I Experiment details
14
A.1.1 Additional details for Section
14
A.1.2
1-test for data augmentation results
14
A.1.3
Small experiments
14
A.1.4
Optimal step size derivation
16
A.2
Convergence analysis: diminishing step size
18
A.2.1 Non-convex case
................................
18
A.2.2
Strongly-convex case
A.3
Proof for Lemma
................................
24
A.4
Convergence analysis: constant step size
................................
28
A.4.1
Non-convex case
28
A.4.2
Strongly-convex case
29
A.5
Justifications for Assumption 2 under various example orderings
30
A.5.1
Arbitrary permutation
30
A.5.2
Shuffle once
30
A.5.3
Random reshuffling
33
A.5.4
Random reshuffling with data echoing
37
A.5.5
Markov chain gradient descent
38
A.5.6
QMC-based data augmentation with random reshufiling
40
A.6
Miscellaneous lemmas
42
13

---

Published as a conference paper at ICLR 2022
A.1 EXPERIMENT DETAILS
A.1.1 ADDITIONAL DETAILS FOR SECTION 6
In Section 6, all the training scripts are implemented via PyTorch1.6 1.6 and run a single machine configured with an 2.6GHz 4-core Intel (R) Xeon(R) CPU, 16GB memory and NVIDIA GeForce GTX 1080Ti with CUDA 10.1.
In the example ordering comparison, we use the same seed among different algorithms in the same to guarantee every algorithm works with the same loss function.
In the ImageNet experiment, the standard step size schedule for ImageNet training is starting at 0.1 and decaying by 10 every 30 epochs. The pre-trained model is the trained model at epoch 90. Naturally, our learning rate should be le-4 by the same schedule. Other hyperparameters are adopted by the open source implementation: https: /ggtttb.tttggggggggg com hatn/yyytcc///cc exampl /tree/ master / i mm genet.
In the data augmentation comparison, obviously other augmentation techniques be used. The strategies we used are taken from open source implementation www.coo/////oooo www.wwwwwiaaaaaaaemm and https://gitte
com/
akamaster/pytoree wtw_rrreeeeeeiteeeeeeeeeeeeeeeee
pytorch - cifarl00 00 that can reproduce the validation accuracy in He et al. (2016), so that our comparison can be consistent with the correct benchmarks. Below we include the convergence plot for the experiment on ImageNet with ResNet18, where each algorithm is repeated three times with seeds uniformly selected from [0, 1000].
II-Unnffrmm
Top1 jop-1 Validation Accuracy
70.4
QMC
Validation Loss
1.24
70.2
1.23
1.22
IID-Uniform
69.8
QMC
90
91
92
93
94
95
90
91
92
93
94
95
Epoch
Epoch
Figure 4: Data augmentation with IID-uniform (standard) and QMC-based methods ImageNet.
A.1.2 1-TEST FOR DATA AUGMENTATION RESULTS
We now perform t-test on the validation accuracy on data augmentation results, show the improvement from QMC is statistically significant. We include validation accuracy at epoch 200 for CIFARIO and best accuracy for CIFAR100 Table A.1.2. We compute the p- p-value between ID-Uniifrmm and tuned QMC, and found the p-value on CIFAR10 and CIFAR100 to be 7e-7 and 0.036, respectively. Since they are both smaller than 0.05, we reject the null hypothesis which concludes they are of the same mean.
A.1.3 SMALL EXPERIMENTS
For both experiments in Section 3, generated w* from standard Normal distribution. The minibatch size is 1, and the total number iterations 10", with n = 10 over 1000 epochs for offline setting. For all variants, use the theoretical step size optimized for SGD with replacement (corresponding to IID Uniform) on this particular problem, given by
(1 (v))
| 1
0++1
of(
with
| (d 2)
which are derived in Appendix A.1.4 below. To obtain low dis-discry samples from the Gaussian distribution, the inverse transform method. First obtain the QMC sequences (Sobol in
14

---

Published as a conference paper at ICLR 2022
Table 2: Validation accuracy for different data augmentation methods CIFAR datasets.
CIFAR10
CIFARI00
Runs
IDDUnnifomm
QMC
QMC (tuned)
IID-Uniform
QMC
QMC (tuned)
91.87
92.05
92.45
67.92
68.91
68.21
91.67
92.13
92.53
68.01
68.92
68.
91.68
92.03
92.33
68.03
68.53
68.42
91.88
91.9
92.35
67.82
68.03
68.71
5
92.05
92.03
92.41
68.89
68.41
67.99
91.79
91.93
92.15
66.99
68.66
68.51
7
91.91
92.79
92.59
68.31
68.92
68.53
91.53
91.73
92.44
68.14
68.09
68.53
91.3
91.96
92.21
68.02
67.91
68.12
10
91.82
92.21
92.16
67.73
68.31
68.53
case) G. E [0, 1|s where s is the appropriate dimension, and then use that the inverse CDF function of Gaussian distribution obtain the corresponding Gaussian sample.
In addition to using synthetic data, we also performed an offline version of the experiment Figure 1(b) on real dataset, a6a from the LIBSVM repository (Chang & Lin, 2011). The dataset contains n=1 1220 examples with d=124 features (including bias), and all labels are binary. We use logistic regression with lz regularization (with X=le-4) the empirical risk:
n
(w) =
log(1 + (xp(-yxx(w) + $110
To measure the left hand side of Assumption 2, again fix wy to be at the origin, and take the number of epochs to be 1000. The results are in Figure 5 for one run with an arbitrarily-set seed, and we draw similar conclusions as observed with synthetic data (see Figure 1(b) in the main paper).
Offline (a6a)
(wo(2
IID Uniform
10-3
Sobol
RR
10
SO
(Wo: xt)
10-5
10
2 P VV
10-7
10
103
104
105 m
106
107
Figure 5: Comparison of sampling schemes on fz-regularized logistic regression with real data.
15

---

Published as a conference paper at ICLR 2022
A.1.4 OPTIMAL STEP SIZE DERIVATION
In this section, we derive the optimal step-size sequence used in our synthetic toy example from Section 3. Recall our setup I (O, Ia). y= "" + c
where w is the true model parameters that we are trying to recover, and < NO0, 1) is some intrinsic error. The goal minimize the expected risk
1 E =F(("' ( y)
f(w)
By using the tower rule of expectation conditioning on æ, this objective can be written as
[(w) (1 w + 1).
The full gradient and the example gradient given pair (x: y) drawn from the above distribution are f((w) = w - w", fw x. (a' w y) (xx w²) c)æ.
Define the gradient error to be
A f( w; x(, v) ff(w) = (xx² [a) - -=²)== ex.
(4)
Let us first analyze the expected gradient error conditioned on any randomness in that might arise from the sampling history:
E ||. (w - w') "E - Ia)²] 2E(ex" (xx" [a)](w - w²) + E(e2z' x])
The last term is simply EE("x" x]] = d since is independent of x. The middle term cancels to 0 again by independence and zero-mean of For the first term,
TE [xxx Ta)
E. pxx xxx 22xx" + T]
(d + 2) 21d + (d + 1)
Together, we have
E | = (d + 1)]l w² w=11² d.
(5)
Now let us derive an suboptimality gap recursion for the SGD update step using the step size ac:
W++1 - w' = w/ a₁ V fwrr y) - w =(w: w²) + V a V((.) aa (WW3s, = (1 - (z))
w²) a,
where A is the expression in Eq. (4) with we as input. The expected suboptimality gap conditioned on all randomness up to timestep is then
|| w |13] = (1 - ox) " [|w w [|"] 2(1 -.)) w"''A," + a 14
Observe that under iid uniform sampling, E[ 0. and using Eq. (5) gives us
[ - w [13] = (1 I1 wn 1| + af + 1)ll - w 112 + add.
Taking an expectation over the entire history to remove conditioning and let p: = E [[lw - w w11
Pet1 = (1 p.) 100++11p:22 aad
= =11 - 2a, + a 2)) + a,
(6)
Note that the RHS is convex in a;, we can differentiate to minimize the expected suboptimality at every iteration P++1 = || - w²]
0= (-2+ 2d + 2))p: + 20rd = at (d+2)pp + d'
Pt.
16

---

Published as a conference paper at ICLR 2022
This also gives expression for pt in terms of az:
1 (d 2)
which combined with Eq. (6) gives us
d
P+1 = a1-ot)pr (1 (1))
02 (d + 2)
Finally, the optimal step-size sequence can be implemented via the following recursion
d d 2
(d +
d+2+
0x++1
P++1
1
2
+ 2+ + |1100 w ==1 1|
0g
is easy to verify that this is indeed a decreasing sequence. If we initialize at wo 0, then our step sizes given by
a1 - -aa) 01+1 1- ad +
100 1| 1 (d + 2) +
with
17

---

Published as a conference paper at ICLR 2022
A.2 CONVERGENCE ANALYSIS: DIMINISHING STEP SIZE
In the main text, our convergence results focused on the constant step size regime for simplicity of presentation and ease of comparison prior works, they often lack diminishing step size results for permutation-ben basedd SGD variants. Here we formally present the convergence rate under our main Assumption using a diminishing step size sequence. In Theorems 3 and 4 that we present below, the rate is of the same order what obtained under constant step size (Theorems and 2) up to a factor of (T' that typically arises when using a diminishing step size.
Our analysis for the diminishing step size setting is accomplished by breaking the total number of iterations into phases. Suppose we want to run a total of iterations of SGD updates. We will break the analysis into / number of phases. In each phase = O,... 1, we run mm) number of iterations with constant step size (6)), The step size is decayed at the beginning of each phase. For this, define the triplets (a m k)),, where {m(")) is an increasing sequence.
Recall that y and / are constants in Assumption In the non-convex case, the inner interval length chosen to be
[3( 1)
where as for the strongly-convex setting it is
[3 + 1) elh1
For both function classes the diminishing step-size is set to
6Tm
A.2.1 DIMINISHING STEP SIZE: NON-CONVEX CASE
Theorem 3 (Diminishing step size: non-convex case). Suppose that our setup satisfies Assumptions I and 2, and let O be any target error. After T iterations of SGD (Eq. (1)) with a diminishing step-size (Eq. (7)), we can obtain
16
T)
LA (3 +1) T (2( 1)3)
log (T)
min [[=()) < 12
3(
11
T-/1+7
This implies the number of gradient evaluations to achieve min, | (wx)]1 S e²
T = Ö(
Proof. To apply Lemma to the iterations within particular phase we need
3Φ < m 7/2
and a
6Lm
where we have temporarily dropped the index (1) for convenience. Lemma gives us the following bound on the objective value between any length-m number of iterations within that phase: for T E (0, m 2m 1,..., (K - 1)m - 11.
2C
[wr+m) 5 (s(w))
2 I [[]](w>]] +
am2m22 2-7
11
$ f(w,)
am
V (w 21 2m
since the step size is constant throughout one phase. Summing over K such intervals from 0 followed by a telescope,
K
am
V (W(m))) 5 f(wo) f(Wm 2C Kam
18

---

Published as a conference paper at ICLR 2022
We now restore phase index,
K
(1) K()
Σ
[V S f(w)) kC
KG)
C²
=f(wo) f(mm ( (m)))))
3L
where we have chosen the largest possible a 1/6Lm(t) for all Summing over / phases and letting A = f(wo) f"
2 m KO
1 K())
K
IA +
C2
Σ
(m)
3L. i=
where the left hand side can be further lower bounded with
10 ( K())
C
[ < IA
Σ
K
(m))))
3L
i=
using the inclusion that {0, (3) 1, 1,..., K( -
i=0 C "o.....,T 1}. Now let us choose
1-1
(1) = [3( + 1))
K(O0 [2
Here the choice of m guarantees that
(m/z (1(3(1) 11)97777))))))))))))))))))))))7) 7/2
[33( + 1/)
2 (3(4 + 1))2 2 34.
Next, observe that for the last term in the previous sum,
K (1) (m (2)
2 ()((((+)))))1
(2 +1)(32 + 1))8//21)~
+ + (1)
2(3( 1)) -27
1=0
1
Combining with the above,
(0) m K
20
min
[f(uw))]1 2 IAA +
1(3
(8)
3L
Furthermore, using our choice of (i)
(4) K((
Σ k()
4
6L
1=0
19

---

Published as a conference paper at ICLR 2022
Re-arranging Eq. (8),
6IL _ 1(3 1))
(9)
Σ K(
The total number of iterations is given by
k(9 mm
1-1
Σ 12 [(3($ + 1))
1-1
2 (3( + 1)
//
2
1=0
10
2 (3(4 + 1)/ 2(x+1)/ -
(3 1))²//
2
27+1
Solving for I and using ig to denote log2, obtain
2
27+2
I 1 ++11 lg
1))% T +1
lg
(3( + (3(0+11)) 1))" T
(3(
Moreover, we can also upper bound 7 using similar arguments,
T
12 [(3([ + 1))
1-1
$
Σ 2(2 2(3( 1))
1=0
4(3(4 + 1)
2
2=0
4(3(4 + 1) 2(++1
2
which gives
27+1
12
lg
T
7+1
4(3( + 1))²/
We are left to bound
I-1
I-1
1-1
2
Σ
KO
Σ
[2
>
2
27
1=0
1=0
1=0
2 lg(TT)
-
2
(TT)
27
1/147
2711-1
T
4(3(0+1))
27
20

---

Published as a conference paper at ICLR 2022
using lower bound for I. Substituting this and the upper bound for I into Eq. (9),
6TLA +
C T(3( + 1))
min I=0,...
Σ K
27+2
6LA + (3 + 1))
lg
7+
(3( 1))
4(310+13) "9 T
27
29
16
LA + (3(
S 12
T
3( + +1) 1)
4(3(0+1)) T) 1/149
21+1-1
-1
16
LA + C2 (3
< 121g
T
3( 1)
T (12 1)2) 1/1t7
log(T)
0
7
which yields our convergence rate in the nonconvex setting.
A.2.2 DIMINISHING STEP SIZE: STRONGLY-CONVER CASE
Theorem (Diminishing step size: strongly-convex case). Suppose f is Polyak-Lojasiewite (PL), and that our setup satisfies Assumptions I and 2 Let e >> 0 be any target error, and k L/u be the condition number of the problem. After T iterations of SGD (Eq. (1)) with a diminishing step-size (Eq. (7)), can obtain
7(-
402 (3( + 1))
f(WT) 5
1[ (3( 1))3/
c(1 12kk]
T
This implies the number of gradient evaluations to achieve [WTT f S < is
T= O(c 9/1).
Proof. We will begin with the same analysis technique used in the non-convex case. To apply Lemma to the iterations within a particular phase i, we need
34 S m 1/2
and a E 6Lm
dropping the index (i) for convenience and will re-introduce it later when appropriate. Lemma gives us the following bound on the objective value between any length-m number of iterations within that phase: for (0, I..... (K- 1)m 1}.
2C
(w++mm S f(w)) 4
2-m²-
17
f(ww)) - am
| [V
)11
4
since the step size is constant throughout one phase. Strong-convexity (or the Polyak-t.ojasiewicz
(PL) inequality) of f implies |/V fww) 1 > 2p(f(w) f*) for all w E Rd, Using this while subtracting f on both sides leads to
(w.-m) - s <5(11
amp
(f(w+) 1*) + 20
2
21

---

Published as a conference paper at ICLR 2022
Applying this recursively K times gives
[(wmk) - 8 5 (1-112111 am
K 21-
2 [[(w))-]' + 22-2 om
K
amn
&
2
k=0
amp
k
(f(wo) - -8²) + +00² am 1-7
Σ
00
k
2
2
k=0
K
(f(wo) - -8¹) + 2C amm 1-
12L
ampp
1
(f(wo) 5*) + 40 m0 1
12k
where we have used
1
a S 60m
2 <
<
as S L.
12L
We now restore the phase index. Letting T; = Σ
1=0
i-1
ml
(()
k(')
be the total number of iterations
passed after i phases so that T = ,, and
A == f(w))
- f
K(
f(WT...) - -5 s
1
AT, +
4C
(m)
12x
Now let us choose
(+) [[3( 1)) ev/1
-1
K = K = [12x] = log(1 - 1/12x)
2 12.
Here the choice of (0) guarantees that
(m 1/)0//~ (I(3(() Φ + 1))th ex )
1/2
(33(++ + 1
1/2
0/'
30.
Using the constant K across all phases, our recursion can be simplified to
K
4C2
((Wr+)) f s 12k
Ar.
+
(7)
P
Since this holds for any i = 0,..., 1,,,,,10 applying recursion over I phases yields,
4C2
1-1
S(WT) - fr < (1 - (1- Do
(10)
==
where we defined p = 1/12k. Observe that for our choice of ( and K,
1-1 T
1-1
Σ
k0
(
K
Σ
[[3(0
+ 1)) .9/1
e/
1=0
i=0
1-1
< K
2(3(4) + 1)) . 2/
1=0
23(3(4 + 1))
Σ el
1=0
2K(3(4 + 1)
2K(3(4 + 2K(3(++1))) 1)) 8/1 th!
1/ - <
5% 6%--1 -1
e./7 e1/-1 -1
which implies
e./T -
1 log
2K + 1))²/7 T)
22

---

Published as a conference paper at ICLR 2022
and
(1 p) S Sexp(-pKT) & exp cxp(- -pKy- -ogg
2K(3( ( +1))3h 1))3// -1)%%))))) 7)
e//1
note that
-1 log(1 - p)
pk9 70pl
2 7.
This gives us
e// -
(1-p) -
T
(1I)
2K(3( 1))3/4
Substituting this into Eq. (10),
t/ -1
4C 1-1
f(WT) 5 - So Ao
T-
Σ
1 p) (m
(12)
2K(3( 1))
1 1=
For the last term,
1-1 Σ 11- p) k0 (m)
1-1
Ki (1
+ 13) -6-1977-
0=
im0
T-1
s (3(0) 1)) 2
Σ
(1
p) ki :-1
2=0
T-1
(3(4 1)) 2 Σ
(e(1 k)
1=
(3(2 + 1))- (e(1 y)
e(1 (K) p)k
p)
KI
(3( + e(1 p)
Substituting these into Eq. (12), and using Eq. (11) to bound (1 - p) KT gives the convergence rate for strongly-convex functions using a diminishing step size:
402
2 (1 p) KI
[(WT) - 1 S A(1 - p)KT
KT
(3
$
1))
c(1 p)R
1C
(3( + 1))
$ (1 - p) KI
A+
e(1 -p)
e/
-7
7
A + 402 (3( + +1)
T
2 12k
(3( 1 + 1))
e(1 11nk]
1
0
T
23

---

Published as a conference paper at ICLR 2022
A.3 PROOF FOR LEMMA 1
We now prove the lemma that bounds the evolution of SGD over a length-m analysis phase. This lemma is the key to our convergence analyses in both the diminishing and constant step size regimes. Before we proceed, we first state and prove the following bound on the gradient error when scaled by a nonincreasing sequence.
Lemma 2. Suppose Assumption 2 holds. If {px} is deterministic, nonincreasing, and nonnegative sequence, then
++m-1
Σ
Pc (V - Vs(w,))
S S ....m. mmm (0² + 12 +V(VV[()>))
Proof. Let 3r = Pt - Pa- fort E {T, T + I....., T +m 22], and let 37+m-1 = P1+m-1. Observe that these all nonnegative, and
++m-1
Pe (V V
Be (Vf(w);z)) - vf(w+))
k=t
3g - ((()))
T+
(V (V[(W;;))) (((=)))
PT
Applying Jensen's 's inequality using Entm-1
By ===Pr
2
Pt (VF(W+;2)) -
7+m-1
3x
V (V((wixz)) - v[(w)))
Pr
k=
1=
3k (k + 1)2
(wwrit)- ([(w))
Pr
Applying Assumption on the squared norm,
r4m-1
Σ
Pe (V((W;i))) v)(Ww)))
++m-1
8e (k- - + ++++1* 1)² [k- -k- 117
+ +2 (++++IVF(w>>))
Pr
k=t
2
Σ
Bx
-K- 1)2-3 11)27 (0a क3 +'
Pr.
K=T
S /
7+
Σ
3k
2=-7 (c²² (
Pr
K=T
= _ m² 2-7
(0 82 | (f(w))))))
which is what we wanted to show.
24

---

Published as a conference paper at ICLR 2022
We now recall the statement for Lemma 1. In the main paper, state the lemma with constant step size. the following proof, we prove holds for non-decreasing step size, where constant step size will hold naturally as a special case. For this, we define == Ei=r --+m-1 att-
Lemma Suppose our setup satisfies Assumptions I and and that we use constant step size For all timesteps т 2 0, let m 0 be some integer such that 30, mm-mm//// S 1 S 6L Then the objective at timestep + m is bounded by
[w++m) S (w+) 2 (w)+)=
2 "1
Proof. Let 1) and g denote
T+
7+m
Og
and
This means that w W4 1g.. From Assumption (L-Smoothness),
[wr+mm = f (w, 19))
n2
$ f (w,) 17 (V fw,
||911
n/LL
/ (w+)
7
2 [V((w)) )11
2 "11l
2
"
[[(x))11=
||91
$ / (w+) 77 [V/(w>)]1 +
17 وg [[(w))]1"
where the last inequality follows because we assumed n S 1/8 (< 1). Next, observe that
77 ggg
v[(w))] )1(
1
I!ng-
v (w,))l
2n
1
0e - - v)(ww))
27
+
2
++m-1
$
Σ
at (Vf(w,:z) ()(=)))
Σ
a
-V -
To bound the second term,
T+m
Σ
at (Vf(wzzz)) vf(W;)=)))
=1
at
(Vf(wx Vf
t=
< 17
[IV (V](ww)))) - - vf(w++))))1
"
Σ
L,LW -ow:-wrlll wrll?
Combining the above,
7+m-1
4+m-1
" llg - vf(w))) <
Σ at (Vf(w,;2.) vf(w)))
+
Σ
a w-11. (13)
Applying Lemma 2 on the first term in Eq. (13) gives
7
Σ a (V)( - vf(w)))
<
a 2-y -0++
7
25

---

Published as a conference paper at ICLR 2022
For the second term in Eq. (13),
-+m-1
ar L 1| w-11²= =
Σ a,L?
On V
T+m-1
5
Σ
Σ Ou (V[(ws; V (w=r:t)))
t=
T+m-1
1-1
12
+3
Σ
0
Σ
au (VS(Wr; - V [[(+))
W
T+m-1
1-1
+3
Σ
0,
Σ
au ([((+)
1=
++m-1
(-1
33
Σ
arL
Σ
au
aallus 1w - w+l1
1=
N15
T+
+3
Σ
T,
a.m²
(c2 + +2 /2|[S[W>>)1'
T+m-1
t-1
+3
Σ
122
Σ On
| [((())]1
where the second term in the last inequality follows from Lemma 2. Continuing,
-+m-1
arL2|Iwe-
wr11? 53
Σ
aLL'n
au w/ 1
t=
7-m-1
Σ
0r 1r12202 02 2-7 (02 x2 [V((w))))
+
+ 3n 3 L2 [2 21
++m-1
= 12
Σ
a L w - w- 12
+ 3I. 10,nmm,m² 2-
(C²
)1²)
+ 3r T,2 [/
This implies that
-+m-1
(1 (1-37
Σ
a,L?l lonn-wwlll
w,11 11 < 3L C2 na?mm=
+ (3 L22 + +312 no m
|| [V)()
And because by our assumption, amm²-102 <
n², it follows that g.
T+m-1
10 n +
(1"372
R - w, 12 namm
L f(,,)
3
Since we also assumed 1)
it follows that 32 12 and
57.
1
T+m-1
Σ
S w-11 < 3I2 ma²
7
5
nl (w:)),
54
26

---

Published as a conference paper at ICLR 2022
which gives
12
12 5
T,T2211144 110 w-ll²
31. Cma2mmm 2-7
11
11
36
L² n/ n0,
11
99
So, putting this all together,
1 - 7 ( + Φ2
f(w++m) $ (w+)
V fww )1
|V [w,())))
2
1)
36 +
10
LL na nam
7
V (w,))11
11
99
"
Vf(w,) )1²
1
a
2-22
2
+ a,m² x2 (
"
36
10
L CCamamm
+ gg 1/ f( )1?
11
S f (w+)
Vf(ww))))))))) )
a,, C2
2
/ )1
1
10
+ Ca
2-
7 V (w,))1
99
=[ 3/2 V [
"
mm C2
21
+ +4L'C² mm?mmm² +
n V f(,,){l
99
< (w+) 1 \V/(w>> 11
-a m 2 C2
-
1 Ca + 7 V (w,) )
4n
(w(w 2 [V[(w>)) a 2 C22
This is what wanted to show.
27

---

Published as a conference paper at ICLR 2022
A.4 CONVERGENCE ANALYSIS: CONSTANT STEP SIZE
A.4.1 CONSTANT STEP SIZE: NON-CONVEX CASE
Theorem 1 (Non-convex case). Suppose that our setup satisfies Assumptions I and 2, and let c > 0 be any target enror. Using SGD (1) with constant step size a GL number of steps T needed to achieve min -. I E² is at most
1 [[4C/e + 34) ) the
T
48LA
4/ = Ō [ + 32)
(CtLL 2444
+ L ch e + 2
Proof. To satisfy the requirements of Lemma the constant step size, constant m case, we need
3am /// S ma S
6L
This breaks apart into first a constraint on only m:
34 S
(14)
and then a constraint on a in terms m:
S
6Tm
In the nonconvex setting, we invoke Lemma followed by summing up K phases and telescop- ing,
V (wmm)) S f(wo) - -5" 2K 2mmm" C
am
= [(ww) -r + 2KKamm C2
which gives a rate of
4(f(wo) f*) + 8m CC?
Σ V (um))))
amk
we want to minimize the right side, observe that we will always want to set a as large as possible, ie.. set 1/6tm. This gives
K-1
24L(f(wo) - -1") + 8m 8m-
Σ
(()mm)) <
K
K
k=0
Now, for this to all be less than e², suffices for
24 - f*)
²
and 8m 0 - 2
- 2
K
2
The former occurs when
48L(f(wo) - fz)
K
while the latter happens when
4C
< m 1/2
(15)
If we A ((w)) - ʃ" using Eqs. (14) and (15) and taking the minimum m and K required, we can bound the number of iterations
48LA 2
40
3/
T = ==mK3 >
+
3Φ
So,
CHILA
LA
04
T=O
+
+ /
24/7/
2
c/
where suppose that 7 constant.
28

---

Published as a conference paper at ICLR 2022
A.4.2 CONSTANT STEP SIZE: STRONGLY-CONVER CASE
Theorem Suppose that satisfies the p-PL condition and our setup satisfies Assumptions and 2. Let E > O be any target error, and K. = 1/ju be the condition number of the problem. Using SGD the number of steps T needed to
(1) with a constant step size a 6f. |(8CC/ /(ue") + -02")%/ [-
guarantee [((T) - f S is most
1/2 T = 12xx log (22)1 [ (sc² + 9
)01 = = = (nitiinn + x022/7 +
Proof. The strongly convex setting has the same constraints on m and a as the non-convex setting. Recall that jestrong convexity or μ-PL of f implies that for all x, [V > 2n(s(x) f*). Applying this to the result of Lemma gives
f(r++m) S (w,) - amy (f(w))- - - 2amm->C3
2
which is equivalent to
(w)++m) - (1- - (f(w)) - 1r) + C
Applying this recursively over K intervals of length m starting from T == 0,
f(mn)) 8r 5-= (1-1000 K
K-1
amm k
(S(wo) 1*) + 2am 0-
k=
I exp
ammh
(f(wo) -5 + 2am 1 0-
1
ammp
2
2
k=0
ammuk
(f(wo) -f") + 2am c- (1
ammp ))
exp
2
ammpk
2
(f(w)) - -f + 2am 1om--1a C2
exp
2
ammp
ampk
4C2
exp
(f(wo) f*) +
m
2
As in the non-convex case, it best advantages us to set a as large as possible. Setting a = 1/6Lm gives
f(Wkk) - f S exp (-
4C²
(f(wo) f*)
7
12L.
For this to be less than e², it suffices for each of these two terms to be less than '/2. In the latter case, we would need
8C²
S m²
(16)
The former case holds when
12L
24 ?
2A
K>
log
= 12k log
where x L/p, Applying a ceiling, using the minimum requirement on and m from Eq. (16) above and Eq. (14) required in Lemma 1, we can lower bound the total number of iterations as
2A
1
T8C2 me? + )66))
1/7
T= mK 2
log
Ignoring logarithmic terms gives
C2
1/7 +
T=
k
K
mE?
29

---

Published as a conference paper at ICLR 2022
A.5 JUSTIFICATIONS FOR ASSUMPTION 2 UNDER VARIOUS EXAMPLE ORDERINGS
A.5.1 PROOF FOR PROPOSITION (ARBITRARY PERMUTATION)
Proposition 1. Let Assumptions and hold, and suppose that we are using permutation- method of sampling. that is, any method such that Tkn; Pkntl..... :...... is a permutation of 100) .211) ..... ,,=n-11 for all epochs k 2 0. Any such method satisfies Assumption 2 with 2. C =²= A² and x² =
Proof. This result follows trivially from Assumption 3. Consider an arbitrary sum of gradient errors going from to + m -: 1:
++m-1
Vf(w;;za()) -Vf())))))))))))))
where or (t) is the index into the training set given by the permutation a used time step Since the interval (T, 1,.... 7 + }} is arbitrary, this can potentially be greater than the epoch size. We can split this interval up as follows. Let 7i be the first epoch boundary in the interval, such that all & going from Tı 1 are within the same epoch Wr, else TI
m if there is no epoch boundary in the interval. Let 72 be the last epoch boundary in the interval, such that all t going from T2 to T
are within a later epoch than w, (it may be the case that 71 T2). Then the sum
Vi(Wii)0()) - -VI(T)
must be zero, since this interval goes over full epochs. This leaves us with
T(()) -Vf(w,)
Vf(w);zo()) - vf(w;)
+ -(0)
1=T
Sn <n(A2
B IV f( ((:)))))
where we have used the fact that the intervals {r.....T] } and {T2, 7 m 10--1 are of length at most |n/2| (if such interval of length greater than nn/2], then bounding its norm is equivalent to bounding the sums of the remaining terms, for which there are at most [n/2] of them). Therefore
1 m
++m-1
- -
S ni (AP B=]l)((w;,)))
m²
and so Assumption 2 is satisfied with = 2, C =?? and Φ² = n²
A.5.2 PROOF FOR PROPOSITION (SHUFFLE ONCE)
Proposition 2. Suppose that we are using the shuffle once variant of SGD to learn over a region B Rdd of radius at most R, such that the iterates we are guaranteed to remain within this region. Assume that for all w E B and all examples x in the training set of size n, Assumption (L- Smoothness) and Assumption 3 hold. Then with probability at least p, Assumption 2 holds with 2, C O(dA2 =
B²)), and &² O(d
Proof. We begin by invoking Lemma (Permuted vector Hoeffding inequality) with
X1, Vf(w; V v((w)
(A² B [f(w))() 1/2
"The prohability p only present in log terms in these expressions, does not appear in the Ô
30

---

Published as a conference paper at ICLR 2022
where Zi, to denote the j-th example after time step for all i E [I....m).] E {I...., n). with n 2 m > 0. Note that here we are using a fixed w E B that does not depend on the permutation used in shuffle once. Clearly, Σド= X 0 for all due to the periodicity in shuffle once, and || by our assumption. Therefore the requirements of Lemma 6 are satisfied, which gives the following high probability bound for some > 0 on any sequence drawn without replacement:
P
vf(w))o()) - Vf(w)) - 2 2
2e exp
32m
Using the periodicity property of shuffle once, i.e. if o is the drawn permutation at the beginning of training then (l + n) = a()), which allows to arbitrarily shift the starting time step in the above:
-+--1 Σ
2 è (A² (A*+ (A++
P
(f(w -
- 2e exp
32m
Consider an arbitrary interval of length m out of the permutation. As all of the "(n- 11/2 intervals are equivalent to an interval of size at most |n/2], by the sum to 0 property, we only need to consider intervals with m s 1/2. This gives us
P
Σ t=T
V f(( -V
2 (A*+ B² (VIV
< 2e² exp
(-
62 16n
By union bound across all intervals we have
2 (A² (A* )(IB)(())))
P
3r,m m E E
(lW; - vs(w))
S < exp
(-16)) 16n
6²
Unfortunately, we cannot take a union bound over R" or (or even just over (wo..... wr }) since the set may contain iterates visited by shuffle once that depend a, and thus Lemma 6 may not hold. Instead, suppose that we cover the whole region with balls of radius 6. We will be able to do this with (1 + 2R/b)² balls by Lemma 7 (c-net lemma). So, if the centers of the balls form a set W, then
T+m-
P
3r, m E 1 EW
Σ
Vf(ūū; (o(() - V f(1))
2 2 2 (A
A2
BIVV(())))))
2R 5
d
e²
I e2n²
1
exp
16n
Note that the centers we use to cover the region is completely independent of the running algorithm, therefore the union bound over Lemma 6 can be applied. Next, consider some W, that is not necessarily the center of a ball. The function
7+m-1
Vf(w):Ra()) V (w++
is Ln-Lipschitz continuous, because each of the components is L-Lipschitz, and we can sum only most 7/2 of them. Let ú W be such that l|,, w| < 6. Adding and subtracting ( a1) and ( applying triangle inequality followed by Lipschitz continuity, have
Σ 7f(w+:aoto) Vf(w+)
$ 2Ln8 +
Vf(ū; V
< 2Tmō + ee A2 Ba [
(w.h.p.)
31

---

Published as a conference paper at ICLR 2022
Adding and subtracting (w+) from f(ū) and bound using and Lipschitz continuity again,
-
V Vf(wzioo(e) - f(w=)
s 2Lno + cv A2 + V VV
S 2Lno + c/ +22282 +22///((>=11
and consequently
vf(Wiizo()) Vf(w,) -V(()
< 42 + +22 (AP 2B222B2200 +2 [V
Note that this inequality will fail hold with probability most
2R
d
c²
e²n²
1+
exp
16n
we want this to fail with probability less than some p. it suffices to set
( E=2n²
+ dloog (1+ 2R
6² = 16n
log
This gives
2
vf(w)iza()) - v.((w))
I 2222
+ 32n
(log
e2222
+ d dloog
1+ 2R ))
2 +2 1V
p
If we set 8 such that 2 A then bound this with
((WW)) - v)(w))
< 4n.2
een
1 2RLVT) )) (A² 2A²B²
+ 32n
log
+ dlog
+ 2B² [V(w,))
A
which gives
vf(W);za(1) [[(W;)
m
32n m²
e222² + dlog 1+ 2RLyn) )) (AP
22
loog
+2
p
n
Hiding logarithmic terms involving n, p, R, L, A, the shuffle once setup satisfies the requirement of Assumption that with probability least
p.
T- 372
Vf(W);Zo()) - vf(w,)
nd 12
2A
2B P [[ )1²)
m
m²
n
(ndA2 + 2d + 2nd 1 ([)())))
m?
(dA'(n + +2B²) + 2nd \vdB"I)((.,)'''))
and the parameters are 7 2, C O(dA2(n + B²)), and क2 ((ndB2)
32

---

Published as a conference paper at ICLR 2022
A.5.3 PROOF FOR PROPOSITION (RANDOM RESHUFFLING)
We first introduce a lemma that bounds the distance between iterates obtained from SGD with random permutation and that obtained from deterministic gradient descent, over one epoch.
Lemma 3. Consider a single epoch of SGD with constant step size a > O, where the examples come from random permutation over the training set. Let Assumption I (L-Smoothness) and the bounded gradient enror Assumption 3 be satisfied. Without loss of generality, assume that the epoch starts at time = 0 at wo- Let the sequence u, be defined by ug We and
Ut-1 Ue a vVf((.)
while
Wh-1 aV [(w;;
for some Ze chosen from the permutation. With probability at least (1 8) it will hold that for all T (1...., n.. if we set
1
< min
64e(c² + 1)BnL log
22tn
2nL
then
22
||T url1 < 128ax (n(e + 1)2.))o0
B2
A2
Proof. Given our setup, observe that we can write the difference between these sequences as
W++1 14++1 W. U (V f(w;gr)) f(())) = W0 3e a (Vf(w;;;)) ff(4:2))) - a (Vf(u;zz) - vf(u)),
such that summing this up and using un un gives
WT u7
Vf(gg))) vf(u)))) -(()))))v((.))
and so
Σ - vS(U))
| - w
Vf(w) vf(u;zi)l+ +a
t=0
T-1
S aL Σ
|
uill +
M
(Vf(un))) vf(w)))
Recall the update rule of u., with Assumption (L-Smoothness), obtain
[Vf((,-)) - aL) [L]
By the reverse triangle inequality, this implies
IV,())) -(1- - [ <11 a [l)
which further implies for any T E (1, nn and E ,0.-..-T-11.
[vf(w)) 5(1 aL) - (
aL
1 1- al
[Vf((r)]
aIn
< exp 1-
|[
< exp
(2aLn)
|[Vf(r)]]
(ur)),,
33

---

Published as a conference paper at ICLR 2022
while for any t {T 1,,,,,,,, ,n),
[V S(1 + [oL))]
<e Vf(u))ll:
where we apply the condition that a S 11)(2n)). For given T, consider the following vector set [z(nzzz)) (((ú,) 3j E (0,..,.))
X, + 8 (v,
it can be easily verified that they sum to zero.
Now apply Lemma (Permuted vector Hoeffding inequality). , for any r 0.
(V(())))) - V((na)) 2 2V B (
72
P
S 26 exp
327
1=
722
2c exp
32n
as T' S n. Now, this holds for just one T. By a union bound,
P 7 E (1...., Σ V (()5))) - V)(mm)) 2 7QT
S $2e2nexp
72
32m
where Qr / B2 V (uT) Now, if set such that
72
2
ne2nexp
72 3:322oog log
32n
then we get that
37 nI,
Σ V (VI(uxx)) v[(ui))
2 27QT
56.
this case, we will have that with probability at least (1 - (8),
T-1
|wr - urll S aL
[0g - uell + arQr. Σ
1=
If we let Po 0 and
PT aL
Pt + ayQr,
1=0
then |er wrll S pr- Here, if >
PT+1 PT = al. - a Qr).
on the other hand, obviously 01 = =07
+ aL) (Qu+1 Qu)
PT =ay
A=
T-1
=07
[1 + aL) a+) -k+
Σ
E(1 ab) (1+
(1
k=1
k=0
say
(1 (1+
Σ (1+ Q+
Σ (1 -1 Qr
k=0
k=0
T-1
San
1/2
Qk + Qr Σ
k=0
San(62 + 1)Qr
=an(e² + 1)y A2 + Bee
san(c² 1)(A Be (f
34

---

Published as a conference paper at ICLR 2022
Put it back we obtain
[wo--ur) - San(e (107(e++1)(0 (A (ellVS((r)]])
Say(e? +1) (A + we - urll
which gives
(1
+ B1) wrll s + 1) ())( Be [f
If we require
as 64e(e² + 1)BBL log
20tn
Squaring and substituting the value of y gives
262n (A 1
| wr s 128a"n(e2 1)² log
8
with probability at least (1 - 6).
We now provide justifications to Assumption 2 for the random reshuffling scheme.
Proposition 3. Suppose that we are using the random reshuffling variant of SGD. Assume that for all E I and all examples, Assumption (L-Smoothness) and Assumption 3 hold. For some p E (0, 1), set the constant step size to satisfy a S (max (1460Bn L. log (4<2T/p) 2nI.)) Then with probability at least p, Assumption 2 holds with = 2, C = =((nA?) and t² Ö(nB²).
Proof. For some > (but different from the y of Lemma 3, consider the event that for some specific epoch k, for some W, E {wo, " (n(k-1)) U {ug, u1...., Un where the u, are the from Lemma 3 for epoch k; and for some and me such that n(k - S < my nk.
V - S A3 B B
Since all the Za((1) are from the k-th epoch, but w, independent of any randomness in the k-th epoch (as it is either point visited in previous epoch, or a value from the sequence which depends only on the position at the start of the k-th epoch and not on any k-th epoch randomness), follows that we can apply Lemma 6 (Permuted vector Hoeffding inequality) on either this sum or, alternatively, the terms from epoch & but
the sum (the terms left out) get that
P
Σ
Vf(W;;oo()) - vf(w>)
2 271
A2 + B²
V [
92
2c exp
32 min (mg n m4)
As my S n. it follows that
m
P
Σ
-(w v)(w+))
2 2 A2 A B2 ((:)))
72
S 2e² exp
16n
Now, by a union bound the probability that there exists some wr, and my such that the average gradient error is large is bounded by
7+m-1
P
3
Σ
V vflw, Vf(w) 2 TV A ((w))
E=
72
2 exp
16n
35

---

Published as a conference paper at ICLR 2022
where T is the total number of iterations across all epochs (and assume that finish all epochs so n divides T). This follows from the fact that there are at most such 7 that we could take on, at most T values of w that can be adopted for each, and at most values my take on. If we set y such that
nT exp (-12m
[4c2nT' p
= 7 x²=
p
16n log
(17)
16n
2
then with probability least (1 - P/2)), it will hold that for all epochs, Wy, т, and mk.
m-ma-1
Vf(wziTo()) - v((++) sav A B
(18)
Additionally, set the d in Lemma be PM/2T. By union bound on the result of Lemma 3, across all 7/n epochs, with probability at least (1 P/2), it must follow that
[4e2T'
|| urll² 128a2n(e' + 1)2 log
(A² + +=++I
(19)
for the corresponding sequence for all epochs. Therefore, both of these inequalities Eqs. (18) and (19) hold together with probability least (1 p).
Now, consider an arbitrary sum of gradient errors going from to + m 1. Note since the interval here is arbitrary, this m can be different from my and potentially greater than n. We can split this interval up as follows. Let 7i be the first epoch boundary in the interval, such that all f going from to T are within the same epoch as Wyy or else 7 = T + m there no epoch boundary in the interval. Let be the last epoch boundary in the interval, such that all going from 72 to + 1 are within a later epoch than w-r (it may be the case that Tı = 72). It follows that
V vf(W)1z0()) -V))))))))
V[(w; (w++
r+m
Vf(w;:Za()) -V(())
Σ
Vf(w,:z0)) Vf(w+)
Observe that since the second of these sums must go some number of full epochs, its value must be Therefore,
f(W)) - V f(wrr)
V((wi))0()) v[(wr)
+
Σ V(WWi))00)) V Vs(w+)
Observe that the term in the first sum must be =1t/2-ipschitz continuous in w, because it can be written the sum of most ['/2] terms each of which is L-Lipschitz (either as the actual terms of the sum, or else the terms left out of the sum). So, add and subtract V ff(u;; To(t)) and V (ur),
V Vf(W) V f(w+))
S nLI[w, - urll
+
Σ Vf(u)izo()) -ff()))) +
Σ
V((W;:oo()) -f
36

---

Published as a conference paper at ICLR 2022
Now applying Eq. (19) the first term and Eq. (18) the last two terms gives
vf(wei -
4e27
I nL
V 128a2n(e2 + 1)2 10)..1. log
(A2 (
2 A2 + B (
Squaring both sides for simplicity, we can bound this with
++m
((( V.((w,)
Ae22) (A2 (=+]
S 25 + 1)2 log
p
+ (A² +
where we have also used Eq. (17) for y. If we apply our requirement that aLn S 1/2, we get
7+m-l
2
Vf(W;; vf(w;)
$ 64n(c² + 1)2. logg
(A2 (A++Be
ne22
+ 128n(A2 + B | f(==))11 log
It follows that for random reshuffling with probability - if we set
< min
64(e² + BenLnL log
4o2T
2nL
1
(4c2T)
max 1460BmL
2nL
random reshuffling satisfies the requirement of Assumption 2 with = 2, C² - Ö(nA), and @ On.B²), where Ó(.) hides logarithmic terms in n, T,
A.5.4 PROOF FOR PROPOSITION (RANDOM RESHUFFLING WITH DATA ECHOING)
The proof for Proposition 4 is nearly repeat of the random reshuffling proof in Proposition 3. The trick is to re-define an epoch when data echoing is used. Instead of referring to an epoch as a random permutation of the examples in the training en samples as an epoch, where each example (i)) is repeated e times. For instance, let c = 3, then the k-th epoch with permutation σ is given by the sequence
in vanilla random reshuffling, here define the
L (1), (1) Fox (2) ................................ Fa Io (n)) Fos Fay:: Fay(n).....
examples used in epoch à
As result of this redefinition, Lemma 3 needs to be modified such that wherever appears, now need en. We omit the proof for the following lemma as is a trivial adaptation from that of Lemma 3.
Lemma 4, Consider single epoch of SGD with constant step size O, where the examples come from a random permutation over the training set, each echoed e times. Without loss of generality, assume that the epoch starts at time L wp- Let the sequence un be defined by us wo and
u ue aV(()))
37

---

Published as a conference paper at ICLR 2022
while
Wt-1 = aV f(w;;
for some Ia chosen from the permutation. Under the same assumptions Lemma 3, with probability at least (1 5) it will hold that for all E {1,... (n,...,,nn
(2ecom) +
|or wr 12 S 128a² 12 + 1)2 log
B² (
8
The justifications for Assumption 2 for the random reshuffting with data echoing scheme also be obtained from Appendix A.5.3 similarly. At appropriate places one should invoke Lemma 4 instead of Lemma 3, and replace n with cn. We omit the proof is again trivial modification.
A.5.5 PROOF FOR PROPOSITION (MARKOV CHAIN GRADIENT DESCENT (MCGD))
To justify Assumption 2 for MCGD, we will first need the following lemma.
Lemma' 5. Let F be any vector-valued measurable function, and let Ta, #1.... be a sequence of samples from Markov chain with mixing time tmis and stationary distribution starting from an arbitrary initial distribution. If the function is constrained such that [1) S 1 for all and if we also have Ex Ex~x [PX)] = 0, then for any E (0, 1),
2ee2 8
P
Σ 1=0
F(x)
2 51mir 2m log
< 6,
Proof. Consider the Doob martingale
m
W
E
F(x:)
Fx
where F& contains all randomness up to timestep k. i.c. zo, 21.... Zk. and so (as usual for Doob martingale) the martingale property is trivially satisfied using repeated conditioning:
m
m
W F
E
F(a:)
Fk+1
Fx
F(x:)
Fx
Wk.
Observe that the sum we want is Wm has increments
F(xx)) Fm = En= F(x;), and that this sum
m
m-
Wh +++1
W4
E
F(x:))
Fx+1
F(x;) Fr
E
F(x:) [
+ E
F(x)) |F+t1
1=
m
Σ F(z,) Fx
E
F(x:) Fr
k+1
F(x))
F(x:) +
Σ
E [F
[R+1)
Σ
E E( Fa)
1=
==++
m-1
m-1
F(*++1) +
Σ E[F(x))
Futil
Σ E[F(x,) 1=++1
Fx).
k=
Now, observe that since the mixing time the Markov chain is fmix for any i 2 k, if μ denotes the distribution of r; conditioned on Ft. then using results from Levin & Peres (2017, Section 4.5)
| M +lbrv $ 2 L(e-k)/Mmm))
38

---

Published as a conference paper at ICLR 2022
It follows from this and the fact that F is bounded that
E (24) F&]ll s 2--106-) k1/eml]
Therefore,
m--1
m--1
Σ E(F(2)) | Fatil
S
E (x(,) | FR-1ll
i=k+2
m
2 ((t 1)/(/
1=k+2
2 g-1(i-k-1)/1
2fmi
and similarly for the last term. follows that
[W&+1
W& 46
Therefore, by the vector Azuma's 's inequality of Hayes (2005, Theorem 1.8), for any 0,
a²
P ([ Woll 2 4m s 26 exp
2m
On the other hand, by the same reasoning as before,
Woll
E
F(x;)
Fo
1=0
m-1 F(x:) Fu
[xo))l
E
S 1 + 2f
2ix
So,
(- a²
P [m.l || 2 2m + 44 a) S 26 exp
2m
Now, setting a such that
a²
22
2c exp
7 a² = 2m log
=
2m
8
and noting that this makes a 2 2, we get
m-1
'2e
P
Σ
F(x:)
2 5t
2m log
I 8,
2=0
which is what we wanted to show.
The justification for Assumption 2 then follows straightforwardly.
Proposition 5. Suppose that we use samples x, from a Markov chain with mixing time tmix- Assume that for all E R and all examples Tt, Assumption 3 holds. Then with probability at least 1 Assumption 2 holds with 1, C (A2212 and 22 = O(B (2
Proof. Observe that we need Lemma to hold for all subintervals of examples, of which there are only at most 2 So, setting 8 be p/r² in Lemma 5, we can show that for all t, m, the probability
2e 27
Σ
(V((w+ --f(-)))))))))))))))))))))))))()
2 25 A² + B²I th 2m log
p
39

---

Published as a conference paper at ICLR 2022
at least 1 p. Equivalently,
7+m-1
(f((=;))) - (((())))
2
S
50
f (A² B² V log
26.272
m
It follows that MCGD satisfies the requirements of Assumption 2 with ? = 1,
2
12621
C² 2 log
and x² = 50 mix log
The big-O expressions in the proposition statement immediately follow.
A.5.6 JUSTIFICATION FOR QMC-BASED DATA AUGMENTATION WITH RANDOM RESHUFFLING
Before we begin with the proof, let us first present the introductory material necessary on quasi-Monte Carlo methods. Similar to Monte Carlo integration, QMC is also used for numerical integration but using cow-discrppancy sequences instead of pseudorandom number sequences. Concretely, the problem is to approximate the integral of function over some s-dimensional hypercube [0, 1]
I(f) = Jo f(x)dr
using the average of the function evaluated sequence of points F1,...,.m.
In (f) = m Σ f(x)).
1
The approximation error rate defined as e = [I()) (m (f)), and it is well-known that in the case of Monte Carlo integration where the 2; 'ss are drawn uniformly at random from [0, 1]", the error rate ² O1/m). If the sequence of x. has low star-discrepancy, which defined as
D = sup
Σ 1 (aEEU) EU Volume(U) 1=1
where U' =1,11, by] b, E [0, 1), and the volume is measured using the s-dimensional Lebesgue measure. Intuitively, the smaller this quantity is the more evenly the sequence of points covers the space. Some popular low-discrepancy sequences include the Halton sequence, Sobol sequence, van der Corput sequence, etc., which are essentially deterministic sequences that are cleverly constructed mimic random numbers but in fact have low dinddiccrepancy. For instance, the Halton sequence satisfies D ((logm)"/m)
To ensure fast convergence of In to as we increase m, addition to using low discrepency sequences we also need f to be relatively well-behaved For this, the Hardy- Krause variation VиK is often used, for which we refer the reader to Drmota & Tichy (2006, Definition 1.13) for its detailed characterization. Most importantly, if has finite VHK on [0, 1] then the Allawa inequality guarantees that
S VHR Din-
This implies that using quasi-Monte Carlo with, for instance, the Halton sequence, integrate function f with bounded Hardy-Krause variation, the error rate would be c² = O(1og (i) "m/" /mr). In comparison to the Monte Carlo error rate, the QMC error rate can be much faster when the dimensionality is relatively small. For an in-depth exposition of the related materials we recommend Owen (2003) and Drmota Tichy (2006).
We are now ready to restate our proposition from Section 5, in which we describe our QMC data augmentation setup.
Proposition 6. Suppose that we are using the random reshuffling variant of SGD) with QMC data augmentation as described. Assume that for all w E RRd and all examples, Assumptions 1 3. 4 and 5 hold for Equation 3. For some p (0, 1), set the step size be a constant such that (max{14600B)) 1440 BnL tog(Ac?T/p)) 2nL Then with probability least 1 p, Assumption holds with 2, C Oln2v' log(T) 2* nA²) and 22 0(nH2).
40

---

Published as a conference paper at ICLR 2022
Proof. Recall that the example used in the t-th iteration is being transformed
Ft A( A(x((1// mod n)) (Lt/n]+ mod n))-
We start from the average gradient error term, that is,
V (Wr; (Ia,
V (w++
Vs(W=: (210) (at0:s)) 2
1
A
E
(~10.11
++m-1
2
E
A
S~10.1]
|2
+
Σ
E C-10.1]-
()) Vf(w;A
Σ n
E C~(0.1)
(z:(0; (2x1) A
Vf(w;
where the first step follows from the definition of f in the data augmentation setup (Eq. (3)). In the second step. the first norm relates the QMC approximation error while the second norm relates to the RR analysis. From the analysis in Section A.5.3 we know the second norm can be bounded asymptotically (and probabilistically) by Ó(n42) + Ó(n f(==)) first term. Since we use contiguous QMC subsequence on each individual example, for the period of [T, m 1]. we define Ty and m, the starting point and length of example 2;(1) being chosen during this period, such that Σド=1 my = m. With this notation, we can now rewrite the first norm as
Now we analyze the
E ((ww;)(
m
c~10.11
Ty m,m
Vf A (260).s))
V A (200:c)
E
5~10.11
t
Σ
Wri A (210),55)
E
Vf (wi:A (x(0):c)
c~10.11
Ty tm
2T(T, + +,
Vʃ (wwiA (1o6)
vs Vs (wwii (o0riA(000;))
E
m²
Tj + my
c~10.1)-
0=0
2
2
T1-1
Wr: A (att),
E
V
Wi: A
(200)
m
<-/00,10
1=
Now can the Koksma-Hlawkk inequality (Aistleitner & Dick, 2014) to bound these norms, which gives us
vs (wii (x), - (,-
m
nC2
V2
n
n C 12 (T) logg()22
0
QMC
Σ
(log(T, + 22 + log (Ty) 22) 50
m
m
Putting it together, we have shown that random reshuffling with QMC data augmentation satisfies Assumption 2 with 7 2, C2 Ô (n?C2 12 log(T)2* (oogTT)+ na?)). and Φ² O (nB²).
41

---

Published as a conference paper at ICLR 2022
A.6 MISCELLANEOUS LEMMAS
We now collect some technical lemmas used in our analyses.
The following lemma is Hoeffding-type concentration bound on the sums of random permutations of vectors. This lemma is particularly useful for simplifying the logie of the proofs of our shuffling propositions above, as it frees us from having to use Doob-martin boob-martingal--yye
arguments throughout.
Lemma 6 (Permuted vector Hoeffding inequality). Let 2 0 be some inlegers, and let X for i {1...., m and j E (l,...,n] n. be vectors in R We also require for all i, ||X S and that for all i,
X = 0.
f=1
Then, a {I....,,1 n} + ,.) is a random permutation and that the individual Xx, 's do not depend
(-
a²
(i)
2 $ exp
exp
32m
Note that this lemma trivially also applies to random subsamples of vector sums, by just letting X1, Y, for the desired vector sequence Yj.
Proof. This proof is adapted from the proof of Theorem 4.3 in Bercu al. (2015). Their approach is more sophisticated and tends to a Bernstein-type inequality, but is specialized to only scalars. Consider sampling the elements the permutation one at time, and let J, be the filtration containing the random variables (LL), o (2), (2,....)....) ( but not o + 1)....... o,, For & < n, define the process
W1 E Σ
X X
F
Observe that this must be a (vector) martingale process, as it Doob martingale. Explicitly, we can write it as
k
W₁- = E
Xi,(()) + n k im 1 ie (K))..))))))
Σ Ex
m/
E
X1,((0
X4,o1) FF
t=k+1
42

---

Published as a conference paper at ICLR 2022
where here used the fact that the X2, 's sum 0 over j = [n]. Thus, the increments of this process will have
k
WA
W
E
X (o(())
X (i) Fs
n k ==
E
(i,(())
Xio()) F
7 k +
== == =1
m
E
Xio(s Fr
11 k
M+ j
m
(i())
Fk-1
n k +
i= j=1
(k.o(k)
Xi,o(k)
i= R++
R-1
Σ 1=
Xi. + n k
Xk,
k
3=1
where we have repeatedly applied the martingale property. Now to bound all of these, first by assumption
| [x 51.
Also,
Σ X
S m7 S 1.
π
n1 k
i=k+1
Next, again using the sum to 0 assumption, we have
Σ
Xk
X2,o(1)
< n +
1,
+
j=1
b=
and finally, by a combination of these bounds,
1
k-1 Σ
((o(1)
Σ
k-1
n2 k n k +1
[n k) - k: 11
(=++1
1=1
i=k+1 j=1
(m k) (n - k 11
(n k) 1: k+
11
follows that the increment satisfies
W Wt-1ll ||| <4
with probability 1. We can now apply the vector Azuma's inequality of Hayes (2005, Theorem 1.8). Applying this to Wm gives the result that, for any a,
a
P (I[ |l 2 a) < 2 exp
32m
This proves the lemma.
The next lemma we state a standard result showing that we can cover a region of radius with bounded number of balls of radius
43

---

Published as a conference paper at ICLR 2022
Lemma 7 (e-net lemma). For any region D of radius R in d-dimensional space, and any e 0, there exists a subset _ D such that S is of size at most
2R
|S| S 1+
E
for every point x D, there exists à S such that || SE.
Proof. Consider the following procedure. As long as there are points in D that are not within distance an existing point in S, choose one such point arbitrarily and add it to S. Observe that with this construction, any points in S must be at distance greater than from each other. This means that if we center a ball with radius e e/2 at each of the points in S, these balls will be disjoint.
The total volume of these balls will be [S] V1 (c/2)", where Vi the volume of the unit ball in d-dimensional space. However, the centers of all these balls must lie in D, and the balls themselves must
within slightly larger region of radius t/2 This region will have volume Vi (R + c/2)". This shows that our process must eventually stop, implying that S must exist, and gives us bound on the size of S as
|S| < e/+)
2R
1
(c/2)
and the proof is complete.
44


Reviews:
[{"review_id": "t20Tm4R6tZG", "reviewer": "Reviewer_rjuV", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths:\n\nThis paper provides a principled way to study the effect of example selection on convergence of SGD. By connecting the average stochastic gradient error to the SGD convergence, it reduces the SGD convergence problem to the problem of controlling the average stochastic gradient error. The latter problem is clearly much easier to address.\n\nCompared to most prior works which usually focus on analyzing specific sampling/scanning strategies, this principled approach in this paper can potentially provide much more guidance on how to design new methods, and in which directions new approaches should go.\n\nOn the analysis of a few existing example orderings, the theory established in this paper can recover the convergence rates obtained before. This indicates that the convergence rate obtained through the analysis of average stochastic gradient error is tight enough, and should be useful for analyzing new sampling strategies in the future.\n\nWeakness:\n\nThe proposed QMC-based algorithm is an extension of random reshuffling to the scenario of data augmentation. This is not building a new sampling strategy, but extending a known method to a different setting, which seems orthogonal to the main discussions of the paper.\n\nThe theory established in Section 3 has not touched “the deepest” yet. The assumption 2, which is the condition on average stochastic gradient error, remains a mathematical condition. So far, it is not quite clear how one should build an optimal sampling method, and how one can build a better sampling method than current ones, to accelerate SGD. \n", "summary_of_the_paper": "1: This paper theoretically builds the following connection: if the averages of consecutive stochastic gradients converge faster to the full gradient, then the SGD with the corresponding sampling strategy will have a faster convergence rate.\n\n2: Applying this theoretical finding on a few commonly used sampling strategies, the convergence rates established by prior works can be recovered.\n\n3: Two algorithms are proposed based on this theory.\n", "summary_of_the_review": "This paper provides a principled way to study the effect of example selection/sampling on convergence of SGD", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "pOP-WVvnQe", "reviewer": "Reviewer_SC9E", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper derives an intuitive and simple result that SGD convergence depends on how well the average of consecutive example gradients approximate true gradient. Even though the result is simple, the authors show that it helps recover several previous convergence guarantees using their framework. Their framework also helps develop two new example selection algorithms. ", "summary_of_the_paper": "The paper studies the dependency of SGD convergence on order of examples. For smooth loss functions, the paper bounds SGD convergence based on averages of consecutive example gradients. Specifically better the average of consecutive example gradients approximate the objective gradient, faster the SGD convergence is. The paper recovers (and in some cases improves) the convergence results of various example selection schemes. \n\nBased on the framework. the paper also introduces couple of new example selection sequences: QMC based data augmentation and greedy algorithm that optimizes on  average gradient metric. The authors also propose using stale gradients and random projection for faster approximate greedy example selection.\n\nThe paper evaluates their theoretical guarantees on several deep learning benchmarks and demonstrate the faster convergence with respect to other example selection techniques such as random sampling, shuffle once and random reshuffling. ", "summary_of_the_review": "The paper presents new albeit simple result that helps bound SGD convergence based on example sequence. The authors also propose two new selection algorithms and demonstrate their efficacy using experiments on MNIST and CIFAR. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FAKVvbdn9zA", "reviewer": "Reviewer_nwty", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper proposes a general metric which can be used to prove convergence rates for a range of stochastic optimization algorithms such as Random Reshuffling, Shuffle Once, SGD with replacement, or any technique that uses sequences of examples for computing the gradients. The metric quantifies how fast the mean of a sequence of $m$ gradients (evaluated at a fixed point) concentrates (as a function of $m$) around the true mean. Then, the paper proves theorems showing that the convergence rate for PŁ and non-convex objectives can be computed in terms of this metric. Hence, proving the convergence rate of any sampling scheme requires only computing this metric. Hence, this paper takes a step in the direction of unifying convergence analysis of sampling schemes.\n\nOverall, the paper is well written, and presents new and intuitive ideas, and useful results. \n\nI have the following major concerns:\n\n1. The convergence rates in prior work for shuffle once do not have a dependence on dimension $d$, whereas Proposition 2 has such a dependence. This is a concern because modern machine learning applications have huge dimensions. Can this be removed? Is this fundamental to the approach proposed in this paper, or do the authors think this is just an artifact of the analysis? This seems to arise from the fact that the analysis tries to prove Assumption 2 on the entire space using an $\\epsilon$-net argument. However, existing works only use something like Assumption 2 on the optimizer (Mishchenko et al. (2020) use Lemma 1 only on the optimizer $x_*$, and Ahn et al. (2020) use Lemma 5 in the proof of Lemma 26, only at the optimizer $0$). Maybe this approach can help?\n\n2. Proposition 2 assumes that the iterates $w_t$ remain in a region of radius $R$. This does not seem justified. For convex objectives, we can imagine that the iterates do not move far away and are somehow attracted towards the minimizer, however for non-convex objectives, this intuition would not hold.\n\n3. The paper says that Proposition 5 gives a faster rate than Sun et al. (2018). However, setting $q=1/2$ would give that $T=O(\\epsilon^{-4})$ even for Sun et al.(2018). I think the authors should provide some more details in the comparison.\n\n4. While comparing the results of Proposition 2 and 3 with Mishchenko et al. (2020) and Nguyen et al. (2020), the authors should also compare with the upper bounds provided in Ahn et al. (2020), as well as the lower bound provided in Safran and Shamir (2020) for SO and Rajput et al. (2020) for RR.\n\nI also have the following (minor) suggestions:\n1. Theorem 2 (along with Proposition 3) seems to suggest that RR beats SGD with replacement when $\\epsilon = o(1/\\sqrt{n})$, which would be when the number of epochs is more than $\\kappa$. This seems to agree with the recent results by Safran and Shamir (2021) saying that RR beats SGD only after $\\kappa$ epochs. A discussion on this would be very useful to the reader.\n\n2. When comparing with older results, the paper assumes that $B=0$, which seems like a strong assumption. For example, if $f=\\|w\\|^2$, and one of the functions $f(w;x)=\\frac{1}{2}\\|w\\|^2$, then this assumption is not satisfied. However, I think this might not be a major concern because even if $B$ is not 0, the comparison would remain similar.\n\nReferences:\n\nMishchenko, Konstantin, Ahmed Khaled Ragab Bayoumi, and Peter Richtárik. \"Random reshuffling: Simple analysis with vast improvements.\" Advances in Neural Information Processing Systems 33 (2020).\n\nAhn, Kwangjun, Chulhee Yun, and Suvrit Sra. \"SGD with shuffling: optimal rates without component convexity and large epoch requirements.\" Advances in Neural Information Processing Systems 33 (2020).\n\nNguyen, L.M., Tran-Dinh, Q., Phan, D.T., Nguyen, P.H. and van Dijk, M., 2021. A unified convergence analysis for shuffling-type gradient methods. Journal of Machine Learning Research, 22(207), pp.1-44.\n\nSun, Tao, Yuejiao Sun, and Wotao Yin. \"On Markov chain gradient descent.\" In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 9918-9927. 2018.\n\nSafran, Itay, and Ohad Shamir. \"Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems.\" arXiv preprint arXiv:2106.06880 (2021)\n\nSafran, Itay, and Ohad Shamir. \"How good is SGD with random shuffling?.\" In Conference on Learning Theory, pp. 3250-3284. PMLR, 2020.\n\nRajput, Shashank, Anant Gupta, and Dimitris Papailiopoulos. \"Closing the convergence gap of SGD without replacement.\" In International Conference on Machine Learning, pp. 7964-7973. PMLR, 2020.\n", "summary_of_the_paper": "The paper proposes a new condition (metric) on the sequence of samples seen by SGD (with or without replacement), which can be used to prove tight convergence rates for strongly convex and non-convex objectives. The metric quantifies how quickly the average gradient of a subsequence of length $m$ converges to the true gradient. This metric is computed for popular schemes like shuffle once, and random reshuffling, as well as for random reshuffling with echoing and Markov chain gradient descent. Then, the paper proposes to combine quasi-Monte Carlo based data augmentation with random reshuffling, proves the condition for it, and shows empirically that it performs well. The paper also proposes a technique which greedily tries to optimize the metric in the proposed condition.", "summary_of_the_review": "This paper presents new and intuitive ideas, and useful results, and is a step in the direction of unifying convergence analysis for different sampling schemes of SGD.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5Dau3xsFO0H", "reviewer": "Reviewer_XLAG", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "## Main\nI am somewhere between \"weak accept\" and \"accept\" for this paper. On the one hand, I think the topic of this work is very promising and a small improvement in the convergence of RR may have a huge impact since it is widely used to train neural networks. Moreover, I am really glad to see that the authors managed to obtain guarantees for Shuffle Once that are better than the guarantees for Incremental Gradient established by Mishchenko et al. (2020), assuming dimension $d$ is smaller than $n$. On the other hand, many aspects of this work are worrisome. It is a bit disappointing to see that the rate in Proposition 2 depends on $d$ and that the proposition requires the domain to be bounded. But the main concern that I have is that all rates for RR and SO seem to be strictly worse than the rate of standard gradient descent. This is in contrast to the results of Theorem 1 of Mishchenko et al. (2020), which shows that RR and SO can be $n$ times faster than gradient descent as long as $\\sigma^2$ is small and the loss functions are strongly convex. It seems that for the nonconvex setting there are no results showing that one can outperform gradient descent with RR, but I hoped that at least under some assumptions, there can be shown an improvement.\n\n## Clarity\nI think the presentation of the theoretical results could be improved. For instance, I would appreciate if the authors gave more details about Hardy-Krause variation bound and why we should expect it to be satisfied. I find the current discussion to be very limited and I believe the authors should include more information than just stating that they \"are commonly used in analyzing QMC sequence\". Similarly, I feel like I do not understand Assumption 5, which seems to be discussed neither in the main paper nor in the appendix. Finally, I think it would be nice to have a table that compares theoretical complexities with the prior literature.\n\n## Experiments\nThe experiments look very insightful and I appreciate that the authors provided confidence intervals in addition to the average results. I am glad to see a numerical study of the average gradient error in Figure 1. It'd be very nice if the authors could study this phenomenon on a non-synthetic problem. The only concern that I have is about the results for ImageNet: Did the authors use a single random seed for it? If not, please also provide the standard errors in Table 1. In addition, I am a bit puzzled as to why the authors did not provide convergence plots for the ImageNet experiment?\n\n## Please add discussion of limitations\nLet me conclude by saying that I really appreciate the topic of the work, but I don't think this paper solves the direction. Many aspects can be improved and I encourage the authors to dedicate a paragraph or two in the conclusion section to describe potential improvements and the limitations of the current results.\n\n### --MINOR ISSUES--\n\"optimizing an strongly convex\" -> \"optimizing a strongly convex\"  \n\"e.g.\" or \"e.g.,\": either put a comma after every \"e.g.\" or do not put it at all  \nOn page 5, in the \"Shuffle once (SO)\" section, the index is placed as superscript instead of subscript \"$x_t = x^{(\\sigma(t\\ mod\\ n))}$\"  \nCosine annealing would probably work better on both Cifar10 and Imagenet. In particular, training with weight decay=5e-4 with 300 epochs often allows to train Resnet20 to a test accuracy higher than 95%.  \nTheorem 3 and its proof use notation $lg()$. Is it a typo? I don't think this extra logarithmic notation is introduced anywhere.  \n\"As all of the $n^2/2$ intervals are equivalent\" did you mean $\\frac{n(n-1)}{2}$ intervals? $n^2/2$ does not even make sense for $n$ odd.  \nIn the proof of Theorem 3, when you say \"By a union bound across all intervals we have\", I think it should be the probability of *existence* of some $\\tau$ and $m$ that the inequality holds, so $P(\\exists \\tau ...)$ instead of $P(\\forall \\tau ...)$, because you prove that this inequality may hold only rarely. The inequality itself, nevertheless, has the correct coefficients and can be proved by the union bound for the negation of the inequality inside $P()$. Similarly, when you define $\\mathcal{W}$ later in the proof, the probability argument should have $\\exists \\hat w\\in \\mathcal{W}$.", "summary_of_the_paper": "The paper studies the convergence of SGD, Random Reshuffling (RR), and, more generally, algorithms that process data examples in an order satisfying a certain assumption, which is a variant of bounded variance assumption with variance decreasing as $O(m^{-\\gamma})$, where $\\gamma$ ", "summary_of_the_review": "This work revolves around a new assumption on the gradient variance that captures SGD, Random Reshulffing (RR), and Shuffle Once (SO), but it is not limited to these methods. As such, it is a bit more universal and it even allows the authors to obtain new rates for Shuffle Once in the nonconvex setting. Some parts of the theory are not clear to me, in particular, I do not feel like I understand Assumptions 4 and 5. I think some polishing of how the results are presented could help. On the other hand, I checked the proof of Proposition 2 and it seems quite novel to me. Mostly, the results look quite good and the theory is not a straightforward modification of prior work. It has some weaknesses though, in particular, it does not guarantee any benefit of RR or SO when comparing to plain gradient descent.  \nWhat I really like about this work is the new variants of data selection proposed by the authors. In particular, they show some promising results on ImageNet by using their new data augmentation technique and study its guarantees, although based on rather exotic assumptions. The authors also get insight from their main assumption to construct a better permutation ordering based on greedy selection. I think that this direction is very promising and may lead to improved training strategies in a wide range of applications.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the dependency of SGD convergence on order of examples. The main observation of the paper is: if the averages of consecutive stochastic gradients converge faster to the full gradient, then the SGD with the corresponding sampling strategy will have a faster convergence rate. For different sampling strategies, sampling with replacement has slower convergence in stochastic gradient, where sampling without replacement can converge faster. The paper also proposes two new algorithms that can improve convergence rates in some interesting settings. The reviewers find the analysis clean and the new algorithms are interesting. There is some concern on the dependency on n or d for the faster rate, which should be discussed more clearly in the final version of the paper. Overall this is a solid contribution to the example selection problem.
Decision: Accept (Spotlight)