Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
Authors: Itay Safran
Ohad Shamir
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Convex Optimization
Stochastic Gradient Descent
Without-Replacement SGD

Abstract: Recently, there has been much interest in studying the convergence rates of without-replacement SGD, and proving that it is faster than with-replacement SGD in the worst case. However, known lower bounds ignore the problem's geometry, including its condition number, whereas the upper bounds explicitly depend on it. Perhaps surprisingly, we prove that when the condition number is taken into account, without-replacement SGD \emph{does not} significantly improve on with-replacement SGD in terms of worst-case bounds, unless the number of epochs (passes over the data) is larger than the condition number. Since many problems in machine learning and other areas are both ill-conditioned and involve large datasets, this indicates that without-replacement does not necessarily improve over with-replacement sampling for realistic iteration budgets. We show this by providing new lower and upper bounds which are tight (up to log factors), for quadratic problems with commuting quadratic terms, precisely quantifying the dependence on the problem parameters.

Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
Itay Safran Princeton University isafran@princet.nn edu
Ohad Shamir
Weizmann Institute of Science ohad. shami r@we izmann ac. il
Abstract
Recently, there has been much interest in studying the convergence rates of without- replacement SGD, and proving that it is faster than with-replacement SGD in the worst case. However, known lower bounds ignore the problem's geome- try, including its condition number, whereas the upper bounds explicitly depend on it. Perhaps surprisingly, we prove that when the condition number taken into account, sethout-replacement SGD does significantly improve with- replacement SGD in terms of worst-case bounds, unless the number of epochs (passes over the data) is larger than the condition number. Since many problems in machine learning and other areas are both ill-conditioned and involve large datasets, this indicates that without-replacemment does necessarily improve over with-replacement sampling for realistic iteration budgets. We show this by provid- ing new lower and upper bounds which are tight (up log factors), for quadratic problems with commuting quadratic terms, precisely quantifying the dependence the problem parameters.
Introduction
We consider solving finite-sum optimization problems of the form
F(x) = (x))
using stochastic gradient descent (SGD). Such problems are extremely common in modern machine learning (e.g., for empirical risk minimization), and stochastic gradient methods are the most popular approach for large-scale problems, where both n and the dimension are large. The classical approach to apply SGD to such problems to repeatedly sample indices E .1..... .n] uniformly at random, m fx(x)) where тд is step-size parameter. With
and perform updates of the form X,+1 this sampling scheme, each (x(,), a random unbiased estimate of Fxxx) (conditioned on x.). be seen a "cheap" noisy version of plain gradient descent F(-), where
Thus, the algorithm each iteration requires computing the gradient just a single function f.(.). rather than the gradient of F(-) (which would require computing and averaging individual gradients). This key observation facilitates the analysis SGD, while simultaneously explaining why SGD is much more efficient than gradient descent large-scale problems.
However, the practice of SGD differs somewhat from this idealized description: practice, it much more common to perform sethout-replacemeet sampling of the indices, by randomly shuffling the indices [1..... n2 and processing the individual functions in that order that is, choosing a random permutation on (1,....n) and performing updates of the form X,+1 x 7 So (x,). After a full pass over the functions, further passes are made either with the same permutation a (known
as single shuffling), with new random permutation chosen before each pass (known random
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Upper bounds on the expected optimization error for quadratic strongly-convex problems, ignoring constants and log factors. The upper table corresponds to random reshuffling, and the lower table corresponds to single shuffling. The right column presents a necessary (possibly non-sufficient) condition for the bound to be valid and smaller than that of with-replacement SGD, which order of 1/(Ank) [Shamir and Zhang, 2013, Jain et al., 2019a]. An asterisk (*) denotes results where the bound is on the expected squared distance to the global minimum, rather than optimization error. For squared distance, the corresponding bound for with-replacemmet SGD is order of 1/ n/(*nk)) [Nemirovski al., 2009, Rakhlin al., 2012].
Paper
Bound
Improves with- with-Replacement?
Gürbüzbalaban et al. [2015b](*))
Only if 2 n Only if 2 A max 1,
(AR)2
HaoChen and Sra [2018]
(nk)= +
if k
X
R
Rajput et al. [2020]
if X
Only if 2 X
(nk)]²
nk
Ahn al. [2020]
Only if Z XtX
x²
(nk))
Paper
Bound
Improves with with-Replaccment?
Gürbüüzbalaban al. [2015a](*)
Only if k Ž
Ahn et al. [2020]
if
Only If 2 X
Mishchenko et al. [2020](*)
Only if Z X
reshuffling). Such without-replacement schemes are not only more convenient to implement in many cases, they often also exhibit faster error decay than with-replacement SGD [Bottou, 2009, Recht and Ré, 2012]. Unfortunately, analyzing this phenomenon has proven to be notoriously difficult. This because without replaccment sampling creates statistical dependencies between the iterations, so the stochastic gradients computed at each iteration can no longer be seen as unbiased estimates of gradients of F(-).
Nevertheless, in the past few years our understanding of this problem has significantly improved. For concreteness, let us focus on classical setting where each f-(-) is convex quadratic, and F()) is strongly convex. Suppose that SGD is allowed to perform & epochs, each of which consists of passing over the n individual functions in random order. Assuming the step size appropriately chosen, it has been established that SGD with single-shuffling returns point whose expected optimization error on the order of 1/ (nkk²). For random reshuffling, this further improves 1/(nk)) 1/(nk*) (see further discussion in the related work section below). In contrast, the expected optimization error of vith-replaccment SGD after the same overall number of iterations (nk) is well-known to be on the order of 1/ 1/(kk) (e.g., Nemirovski et al. [2009], Rakhlin et al. [2012]). Moreover, these bounds are known to be unimprovable in general, due to the existence of nearly matching lower bounds [Safran and Shamir, 2020, Rajput et al., 2020]. Thus, as the number of epochs l: increases, without-replacement SGD seems to provably beat with-replacement SGD.
Despite these encouraging results, it is important to note that the bounds as stated above quantify only the dependence on n, k. and ignore dependencies on other problem parameters. In particular, it is well-known that the convergence of SGD is highly sensitive to the problem's 's strong convexity and smoothness parameters, their ratio ka. the condition number), as well as the magnitude of the gradients. Unfortunately, existing lower bounds ignore some of these parameters (treating them as constants), while in known upper bounds these can lead to vacuous results realistic regimes. To give concrete example, let us return to the case where each fa(-) is a convex quadratic function, and assume that F(-) is Stsrrongly convex for some À > 0. In Table 1, we present existing upper bounds for this case, function of both A well as À (fixing other problem parameters, such as the

---

smoothness parameter, as constants). The important thing to note about these bounds is that they are valid and improve over the bound for with-replacement SGD only when the number of epochs is at least or 1/A (or even more). Unfortunately, such regime is problematic for two reasons: First, large-scale high-dimensional problems are often ill-conditioned, with À being very small and being very large, so requiring that many passes k over all functions can easily be prohibitively expensive. Second, if we allow & > A. there exist much better and simpler methods than SGD: Indeed, we can simply run deterministic gradient descent for A iterations (computing the gradient of F(-) at each iteration by computing and averaging the gradients
fa(-) in any order we please). Since the optimization error of gradient descent (as function of k A) scales we compute a nearly exact optimum (up to error c) as long as Z X log( t Moreover, slightly more sophisticated methods such as accelerated gradient descent or the conjugate gradient method enjoy an error bound scaling exp(-kx Rv)), so in fact, we can compute c-optimal point already when k 2 VX log(?) ).
(xp( [Nesterov, 2018],
Thus, the power of SGD is mostly when k is relatively small, and definitely smaller than quantities such as L/A. However, the upper bounds discussed earlier do not imply any advantage of without- replacement sampling in this regime. Of course, these are only upper bounds, which might possibly be loose. Thus, it is not clear if this issue is simply an artifact of the existing analyses, or a true issue of without--eplacemmen sampling methods.
In this paper, we rigorously study this question, with the following (perhaps surprising) conclusion: At least in the worst-case, without- without-replaceet replacement schemes do not significantly improve over with- replacement sampling, unless the number of epochs k is larger than the problem's condition number (which suitably defined, scales as 1/)). As discussed above, this implies that the expected benefit of without-replacemen schemes may not be manifest for realistic iteration budgets. In more detail, our contributions are as follows:
We prove that there is a simple quadratic function F-)). which is X-strongly convex and Amax-Smooth, such that the expected optimization error of SGD with single shuffling (using any fixed step size) is at least
1 Ankk
{ Amax/ / A))
k A
Ω
min
(See Thm. 1.) Comparing this to the ((1/(nnk) bound for with-replacemmnt SGD, we see that we cannot possibly get significant improvement unless k is larger than the condition number term A=
For SGD with random reshuffling, we prove similar lower bound of
(NI min
1 Ankk
{
Amax/A
Xanax/ }))
Ω
nk
h2
(See Thm. 2.) As before, this improves on the ((1/(Ank) bound of with-replacement SGD only when k > Amax
We provide matching upper bounds in all relevant parameters (up to constants and log factors and assuming the input dimension is fixed See Sec. 4), which apply to the class of quadratic functions with commuting quadratic terms (which include in particular the lower bound constructions above).
To illustrate theoretical results, we perform few simple experiments comparing with- and without-replacemmet sampling schemes on our lower bound constructions (see Sec. 5). Our results accord with theoretical findings, and show that if the number of epochs is not greater than the condition number, then without-rrelacemmen does not necessarily improve upon with-replacement sampling. Moreover, it observed that for some of the values of k exceeding the condition number by as much as 50%, with-reeplacmmen still provides comparable results rethout-replacemeet, even when averaging their performance over many instantiations.
Focusing only on À is enough for the purpose of our discussion here, and moreover, the dependence on other problem parameters is not always explicitly given the results of previous papers.
3

---

We conclude with a discussion of the results and open questions in Sec. 6.
We note that lower and upper bounds apply SGD using fixed step size, 1/2 = of for all i, and for the iterate reached after epochs. Thus, they do not exclude the possibility that better upper bounds can be obtained with a variable step size strategy, some iterate averaging scheme. However, we conjecture that it is not true, as existing upper bounds either do not make such assumptions or do not beat the lower bounds presented here. Moreover, SGD with variable step sizes can generally be matched by SGD employing a fixed optimal step size (dependent on the problem parameters and the overall number of iterations).
Related Work
Proving that without-replacement SGD converges faster than with-replacement SGD has been the focus of a line of recent works, which we briefly survey below (focusing for concreteness on quadratic and strongly convex problems, as we do in this paper). Gürbüizbalaban al. [2015a.b] proved that without--eplacement beats with-replacement in terms of the dependence on l: (1/k² vs. 1/k, without specifying a decay terms of n). Shamir [2016] proved that without--relacemment is not worse than with-replacement in terms of dependence on but only for k = 1. HaoChen and Sra [2018] managed to prove a better bound for random reshuffling, scaling as 1/(nk>)² + 1/1.. Safran and Shamir [2020] proved a lower bound of 1/(nk)² + 1/nk-3 for random reshuflling and 1/(nk²) for single shuffling, and also proved matching upper bounds in the (very) special case of one-dimensional quadratic functions. A series of recent works [Jain et al., 2019b, Rajput et al., 2020, Ahn et al., 2020, Mishchenko et al., 2020, Nguyen et al., 2020] showed that these are indeed the optimal bounds in terms of n, k. by proving matching upper bounds which apply to general quadratic functions and beyond. Rajput et al. [2020] were also able to show that for strongly convex and smooth functions beyond quadratics, the error rate provably becomes order of 1/nkk) for both single shuffling and random reshuffting.
A related and ongoing line of work considers the question of whether without-replacement SGD can be shown to be superior to with-replacement SGD, individually on any given problem a certain type [Recht and Ré, 2012, Lai and Lim, 2020, De Sa, 2020, Yun et al., 2021]. However, this is different than comparing worst-case behavior over problem classes, which is our focus here. Without-replacement SGD was also studied under somewhat different settings than ours, such as Ying et al. [2018], Tran et al. [2020]. Huang et al. [2021].
In our paper, we focus on the well-known and widely popular SGD algorithm, using various sampling schemes. However, we note that for finite-sum problems, different and sometimes better convergence guarantees can be obtained using other stochastic algorithms, such as variance-reducel methods, adaptive gradient schemes, or by incorporating momentum. Analyzing the effects of without- replacement sampling on such methods is interesting topic (studied for example in Tran et al. (2020J), which is however outside the scope of our paper.
2 Preliminaries
Notation and terminology. We let bold-face letters (such as x) denote vectors. For a vector x, Ty denotes its j-th coordinate. For natural n. let [n] be shorthand for the set [I, For some vector v. ||v|| denotes its Euclidean norm. We let [lsp denote the spectral norm of a matrix. A twice-differentiable function f on E is X-strongly convex, if its Hessian satisfies F²F( > XI for all x, and is L-smooth if its gradient is L-Lipschitz. f is quadratic if it is of the form fxx) = fx Ax + T + for some matrix A, vector b and scalar c.2 Note that if is a PSD matrix. then the strong convexity and smoothness parameters of f correspond to the smallest and largest eigenvalues of A, respectively. Moreover, the ratio between the largest and smallest eigenvalues is known as the condition number of f. We use standard asymptotic notation ()-), ((),),()),)) ((-)) to hide constants, and é(.), Óc)), (--) to hide constants and logarithmic factors.
SGD. As mentioned in the introduction, we focus on plain SGD using a constant step size π)- which performs & epochs, and in each one takes n stochastic gradients steps w.r.t. the functions
We note that throughout the paper we omit the constant scalar terms, since these do not affect optimization when performing SGD (only the optimal value attained).

---

f with o being a random permutation which is either sampled afresh at each epoch (random reshuffling) or chosen once and then used for all &o epochs (single shuffling). We let Xo denote the initialization point, and x1,...: X denote the iterates arrived at the end of epoch .,.... respectively.
Lower Bounds
In this section, formally present our lower bounds for single shuffling and random reshuffling SGD. Our lower bounds will use a particularly simple class quadratic functions, which satisfy the following assumptions.
Assumption 1 (Lower Bounds Assumption), F(x) is A-strongly convex and of the form 1 E f((x), and each fi of the form f((x) := Ej 2ajxz byæz, where for all j. aj [X, Amax] U {0} and b, E 1 G. Suppose nk is large enough that log(nk) I We assume that the algorithm is initialized af some X on which [VF s G.
Ank
Note that any such function F is >max--mootth and so are its components. We emphasize that since our lower bounds apply to such functions, they also automatically apply to larger function classes (e.g. more general quadratic functions, the class of all A-strongly convex and >max--moott functions, etc). Moreover, our lower bounds also apply in harder and more general settings where for example only partial noisy view of the Hessian of the functions is revealed.
Having stated our assumptions, we now turn to present our results for this section, beginning with our single shuffling lower bound.
Theorem 1 (Single Shuffling Lower Bound). For any k 2 1, > 1, and positive G. X there exist function on IR?2 and an initialization point Xy satisfying Assumption 1, for which single shuffling SGD using any fixed step size n > O satisfies
G Ank
(1,
Amnaxe /
E [[((x 2
min
k
for some universal constant c
The function F used in the above theorem is given by the component functions
fx(x fz(1
A
Amax
22
G
x2
is
(I)
2
G x2 i i> 7
For the random reshuffling sampling scheme, have the following theorem.
Theorem 2 (Random Reshuffling Lower Bound). For any k 2 1, > 1, and positive G. X, there exist a function on R and an initialization point Xy satisfying Assumption for which random reshuffling SGD using any fixed step size >> O satisfies
G Ank
min {1,
Amax/ X
X2 X 1x2
E [[F(xx)]
+
nkk
122
for some universal constant
The function F used in the above theorem is given by the component functions
A 2 Amax 2
G
+ Amar
x3 +
G 2
is
s((x) = [((11, = 2
122
2
2
(2)
2
J
233
In contrast, with-replacemmnn SGD bounds are of the form ( (Ank))). Thus, we see that for both single shuffling and random shuffling, we cannot improve the worst-case performance of
'There is subtlety here. most such bounds either the last iterate, or use a non-constant step-size (in which case possible prove bound O(G*/ /)nk)) However, Shamir and Zhang [2013] prove bound of Ó /nuk) (involving additional log(nk) factor) for the last iterate. using a variable step-size tje = (xt)). and is not difficult to adapt analysis to SGD with constant step size r é(1/(Ank)
average of the iterates rather than
5

---

with-replacement SGD by more than constants or logarithmic terms, unless ls is larger than the condition number parameter Awas As discussed earlier, this can be an unrealistically large regime for k in many cases.
The proofs of the above theorems, which appear in Appendices A.1 and A.2. follow a broadly similar strategy to the nieddimesiooall constructions in Safran and Shamir [2020], with the crucial difference that we construct a multivariate function having different curvature in each dimension. The constructions themselves are very simple, but the analysis is somewhat technical and intricate. Roughly speaking, our analysis splits into three different cases, where in each a different magnitude of the step size is considered. In the first case, where the step size is too small, we use dimension with small curvature to show that if we initialize far enough from the global minimizer then SGI) will converge too slowly. The construction in the remaining dimensions is similar to that in Safran and Shamir [2020], and uses a larger curvature than the first dimension to generate dependency on the condition number, due to the somewhat too large step size that is dictated by the first case. In the remaining two cases, the step size is either too large and the resulting bound is not better than with-replacement SGD; or is chosen in a manner which achieves better dependence on n, k, but also incurs additional error terms dependent on Xmax A, due to the statistical dependencies between the gradients created via replacmmett sampling. Combining the cases leads to the bounds stated in the theorems.
We also make the following remarks regarding our lower bounds:
Remark 1 (Separating Amax and L). Our parameters satisfy the following chain of inequalities S Amax S L. Since the condition number commonty defined in the literature as L/>, X, we note that in our lower bound constructions we have Amax L.. However, since Xmax could potentially be smaller than L., this raises the question of whether is possible to construct a lower bound in which Amax is sufficiently smaller than L yet the lower bound depends on L. The upper bounds we present in the next section indicate that this is not possible when the A, 's commute, since in this case we get bounds with no dependence
L (at least when nk is large enough). This implies that to separate the two quantities Amax, L, one would necessarily need a construction where the As 's do not commute. We leave the derivation of such a construction future work.
1 is equivalent to requiring nk to be at least on the order of the condition number T./X (up to log factors). This is mild requirement, since if nk smaller than the condition number, then even f all i (that is, we perform deterministic gradient descent on the function f), there are quadratic functions functonic for which no non-trivial guarantee can be obtained [Nesterov, 2018J.
Remark 2 (Bound on L). We note that the condition log(nk)L Ank S
Remark 3 (A Random Reshuffling Lower Bound in I2²), Our lower bound construction for single shuffling is a function in TR?, whereas our random reshuffling construction is in RR3 We believe that construction in TR2 is also possible for random reshuffling, however this would require a more technically involved proof which for example also lower bounds the right-most most summand in Eq. (5).
4 Matching Upper Bounds
In this section, we provide upper bounds that match our lower bounds from the previous section (up to constants and log factors, and for a fixed input dimension). Whereas our lower bounds use quadratic constructions where each matrix A; is diagonal, here we prove matching upper bounds in the somewhat more general case where the quadratic terms commute. Before we state our upper bounds, however, we will first state and discuss the assumptions used in their derivation.
Assumption 2 (Upper Bounds Assumption). Suppose the input dimension d is a fixed constant. Assume F(x)= = _/x Ax- x is a quadratic finite-sumfunen function of the form a E fx(x) for some >>> 1, which is X-strongly convex and satisfies ||Al|sp >max. Each J's is convex quudratic function of the form fa(x)) -1xxT A - b, x, for commuting, symmetric, and PSD matrices A, E Rdddd which all satisfy ||A sp < L. Moreover, suppose that [xx'))) < for all i E [n], where
x" == -arg minx F(x) is the global minimizer. Assume nk is large enough so that log(nk)L. assume that the algorithm is initialized at some Xy on which || F - G.
Ank < 1. We
Note that our lower bound constructions satisfy the assumptions above. We remark that as far as upper bounds go, these assumptions are somewhat different than those often seen in the literature. F.g. we require that V f. is bounded only at the global minimizer x", ratherr than in some larger domain as

---

commonly assumed in the literature. However this comes at cost of assuming that d is fixed. We remark that we believe that is possible extend our upper bounds to hold for arbitrary d with no dependence d, but this would require more technically involved analysis (e.g. a multivariate version of Proposition 3). Nevertheless, the bounds presented here are sufficient for the purpose of establishing the tightness of our lower bound constructions, which involve 2-3 dimensions. Lastly, we recall that the assumption on the magnitude of nk is very mild as explained in Remark 2.
E.=1 fi( satisfy Assumption We now present the upper bound for single shuffling SGD:
Theorem (Single Shuffling Upper Bound), Suppose F(x) n
and fix the step size 17
log(nk) Ank
Then single shuffling SGD satisfies
[[F(x S 0 0 G² --iin
{1 m
Ammax/ (1,Am//))
Ank
k
where the Ô hides a universal constant, factors logarithmic in n, Amax. 1/2, and a factor linear in d.
Next, we have the following result for random reshuffling SGD.
Theorem 4 (Random Reshuffling Upper Bound). Suppose F(x) = Ei= fi(x) satisfy Assumption
2, and fix the step size 1)-
log(nk)
Then random reshuffling SGD satisfies
Ankk
G Ank
minn {1, Amax/
Xmax/
E
[xxxx s δ
nik +
k2
where the Ô hides a universal constant, factors logarithmic in n, k, Amax, 1/2, and a factor linear in d.
The proofs of the above theorems, which appear in Appendices A.3 and A.4, are based on reducing our problem to one-dimensional setting, deriving a closed-form expression for 3yK (as done in Safran and Shamir [2020]), and then carefully bounding each term the resulting expression. However, our bounds refine those of Safran and Shamir [2020], allowing us to achieve upper bounds that precisely capture the dependence on all the problem parameters, Both proof's split the analysis into two cases: (i) The case where we perform sufficiently many epochs (k: Amaxx A) and are able to improve upon with-replacement SGD; and (ii), where too few epochs are performed (k: < >mmax/ A), in which case the sub-optimality rate matches that of with-replacement SGD. In both theorems, new tools to control the random quantities that arise during the problem analysis are required to attain bounds that match our lower bounds (see Proposition in the Appendix for example). We point out that the choice of step size in the theorems is not unique and that the same upper bounds, up to log factors, apply to other choices of the step size (we did not attempt to optimize the logarithmic terms in the bounds).
It is interesting to note that somewhat surprisingly, our upper bounds do depend on L, only on the smaller quantity Amax- L only appears via the condition nL < 1 in Assumption 2. This can be attributed to the assumption that the A, commute, in which case the spectral norm of their average governs the bound rather than the maximal norm of the individual A, ss It is interesting to investigate what extent our bounds could generalize to the non-commuting case, and if the dependence on will remain mild. Since our upper bounds make essential use of the AM-GM inequality and of the even more general Maclaurin's 's inequalities, seems like we would need strong non-commutative versions of these inequalities to achieve such bounds using our technique. We refer the interested reader Yun et al. [2021] for further discussion on non-commutative versions of such inequalities.
Another noteworthy observation is regarding the phase transitions in the bounds. In the previously known upper bounds for random reshuffling for quadratics, which scale as 1 + I मरग (see Table 1),
(WR)T the dominant term switches from ार to (nkpp once A 2 In the ill-conditioned setting, our
random reshuffling upper bound reveals that such phase transition only occurs when k > Amax which is significantly stronger assumption. This suggests that many real-world applications, the sub-optimality rate would be G² budget.
A
> A /13
Xuk min
unless can afford very large iteration
Lastly, make the following additional remarks upper bounds.
7

---

Remark 4 (Bounds with High Probability). Our proof the single shuffling upper bound can be adapted to imply a proobbbbbabilityy bound, rather than merely an in- in-expectation bound, at a cost of logarithmic dimension dependence (e.g. by taking union bound over the guarantee in Thm. 5 in the proof across all dimensions). Moreover, in the case where k S >mmxx/ /,, then our random reshuffling upper bound also holds with high probability. 4 This implies a concentration of measure around the expected bounds, which shows that our derived sub-optimality rates are the "typical' behavior of without without-replacemen replacement SGD in the worst case for single shuffling, and that the inability to improve upon without replacement when S Xmax/ X is not just on average but also with high probability for random reshuffling.
in One-Dimension). Since in the one- dimensional case we have X = Amax, our upper bounds reveal that perhaps in contrast to what previous upper bounds that depended on L suggested, the one-dimensoonal case is always well- conditioned. That is, rephoutt-eplacement will always beat reph-replaeement SGD in one -ieeiimnnionn given that Assumption holds.
Remark 5 (The Problem is Always Well-Conditionn
Experiments
In this section, we empirically verify the phenomenon that our theory predicts by running simulations on the constructions used in Equations (I) and (2). Our lower bounds show that to beat with- replacement on those problem instances, the number of epochs must be in the order of magnitude of the condition number. However, since our analysis is asymptotic in its nature, ignoring constants and logarithmic terms, it is not clear to what extent this phenomenon can be observed in practice. To investigate this, averaged the performance of 100 SGD instantiations over various values of l ranging from & = 40 up to k- = 2, 000, where for each value a suitable step size of 7 = log(nk)
was chosen. Our problem parameters were chosen to satisfy n 500, G = 1, X = 1 and X max 200. Note that this implies that the condition number equals 200 in the constructed
Ank
problem instances. Each SGD instantiation was initialized from Xo (- G
2X -_ which
satisfies both Assumptions and 2. We used Python 3.6 in our code, which is freely available at http://iiihubbooomaaaaaaaaaaeeee LataainttSDDoooiionnnnnnooa number. Our code was run on a single machine with an Intel Core i7-8550U 1.80GHz processor.
Our experiment results, which appear in Fig. 1, reveal that get a noticeable advantage with- replacement, the number of epochs must be very large and indeed exceed the condition number. Moreover, by that point the remaining error is already extremely tiny (less than 10 10-5). Additionally, for values of k up to 300, it is evident that with-replacemmnt sampling occasionally performed almost the same as without-replacemmet sampling schemes, exhibiting significant overlap of the confidence intervals. This indicates that in certain ill-conditioned applications, it can be quite common for with- replacement to beat withoutt-eplaccmmet. Another interesting observation that random reshuffling does not significantly improve upon single shuffling, unless k is at least 1, 000. This is in line with our theoretical results, which indicate that the advantage of random reshuffling will only be manifest once k is considerably larger than the condition number. It also indicates that the additional effort of reshuffling the functions in every epoch might not pay off on ill-conditioned problems, unless a considerable iteration budget is possible.
We remark that similar experiment was shown in De Sa [2020], where a construction is presented in which with-replacement outperforms without--eplaacement SGD. However, a major difference between the above experiment and ours is that in the former, despite under-performing compared to with-replacement,, without-replacement achieves an extremely small error, which requires exact arithmetic to monitor, to the point where the difference becomes arguably insignificant from practical perspective. In contrast, our experiment shows that hethout-replacement merely does not significantly improve upon bith-reelacement for moderate values of k, in a setting where much more realistic error rates are attained.
*This is because that in this case, the dominant term in the high probability bound given by Amax/A is the squared term, which is also the dominant term in the upper bound in Thm. 4. 'For the sake of simplicity and to better distinguish the two constructions, we only used the first and third dimensions in the construction in Eq. (2), since the second dimension is identical to the second dimension in Eq. (1).
A /x²
8

---

With-replacement
Single Shuffling
Random Reshuffling
Mean Log-Loss
-5
10a
10a
With-replacement
Single Shuffling
Random Reshuffling
-5
Mean Log-Loss
-6
-7
10a
103
k
Figure 1: The average value of logı0 F (xxx) attained after running 100 instantiations of SGD on F(-) in Eq. (1) (top) and Eq. (2) (bottom), using with-replacement (blue circle), single shuffling (red plus) and random reshuffling (green triangle) sampling, for varying values of k and where the step size is chosen accordingly. The confidence intervals depict a single standard deviation of the log-loss for each value of k. Best viewed in color.

---

6 Discussion
In this paper, theoretically studied the performance of without-replacemmnt sampling schemes for SGD, compared to the performance of with-replacement SGD. Perhaps surprisingly (in light of previous work on this topic), we showed that without-replacement schemes do not significantly improve over with-replacement sampling, unless the number of epochs A: is larger than the condition number, which is unrealistically large in many cases. Although the results are terms of worst-case bounds, they already hold over a class of rather simple and innocuous quadratic functions. We also showed upper bounds essentially matching our lower bounds, as well as some simple experiments corroborating our findings.
Overall, our results show that the question of how without--eplacemmett schemes compare to with- replacement sampling is intricate, and does not boil down merely to convergence rates in terms of overall number of iterations. Moreover, it re-opens the question of when replacement schemes to have better performance, for moderate values of k. Our lower bounds imply that for ill-conditioned problems, this is not possible in the worst-case, already for very simple quadratic constructions. However, an important property of these constructions (as evidenced in Equations (1) and (2)) is that the eigenvalue distribution of the matrices defining the quadratic terms is sharply split between Amax: A, and both directions of maximal and minimal curvature are significant. In a sense, this makes impossible to choose step size that is optimal for all directions, and is indeed required to be larger than the condition number Amax/A Á for without-replacement schemes to beat with-replacemmen sampling. In contrast, for quadratics whose eigenvalue distribution is smoother (e.g. where the curvature is roughly the same in "most" directions). we expect the "effective" condition number to be smaller, and hence possibly see an improvement already for smaller values of k. Formally quantifying this, and finding other favorable cases for without-replacemeen schemes, is an interesting question for future work. Another open question is to generalize our upper and lower bounds (getting the precise dependence on the condition number) to more general quadratic functions, or the even larger class of strongly-conver and smooth functions.
hope without-
Acknowledgments and Disclosure of Funding
This research is supported in part by European Research Council (ERC) Grant 754705. We thank Gilad Yehudai for helpful discussions.
References
Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. Sgd with shuffling: optimal rates without component convexity and large epoch requirements. arXiv preprint arXiv:2006.06944 2020.
Rémi Bardenet, OdmlriccAmbrym Maillard, al. Concentration inequalities for sampling without replacement. Bernoulli, 21(3): 2015.
L. Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. In Proceedings of the symposium on learning and data science, Paris, 2009.
Christopher M De Sa. Random reshuffling is not always better. Advances in Neural Information Processing Systems, 33, 2020.
Mert Gürrüüzaalaaan, Asu Ozdaglar, and Pablo Parrilo. Convergence rate of incremental gradient and Newton methods. arXiv preprint arXiv: 151..8852, 2015a.
Mert Gürbüzbalaban, Asu Ozdaglar, and Pablo Parrilo. Why random reshuffling beats stochastic gradient descent. arXiv preprint arXiv: 15t::11100 110.08560 2015b.
Jeffery Z HaoChen and Suvrit Sra. Random shuffling beats sgd after finite epochs. arXiv preprint arXiv:1806.10077 2018
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge University Press, Cambridge, 2013.
Xinmeng Huang, Kun Yuan, Xianghui Mao, and Wotao Yin. On the comparison between cyclic sampling and random reshuffling, arXiv preprint 104i::2204.12111 2021.
10

---

Prateck Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Making the last iterate of sgd information theoretically optimal. In Conference on Learning Theory, pages 1752-1755. PMLR, 2019a.
Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Sgd without replacement: Sharper rates for general smooth convex functions. arXiv preprint 1rXiv:1903.01400 2019b.
Zehua Lai and Lek-Heng Lim. Recht-ré noncommutative crtthmefic-geomerte false. In International Conference on Machine Learning, pages 5608-5617. PMLR, 2020.
conjecture is
Konstantin Mishchenko, Ahmed Khaled Ragab Bayoumi, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33, 2020.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574- 1609, 2009.
Yurii Nesterov. Lectures convex optimization, volume 137. Springer, 2018.
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 preprint arXiv:2002.02244 2020.
Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. Closing the convergence gap of sgd without replacement. arXiv preprint (Xv::2002.1040) 2020.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1571-1578. Omnipress, 2012.
B. Recht C. Ré. Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences. In COLT, 2012.
Itay Safran and Ohad Shamir. How good is sgd with random shuffling? In Conference Learning Theory, pages 3250-3284, 2020.
Ohad Shamir. Without-replacement sampling for stochastic gradient methods. In Advances in neural information processing systems, pages 46-54, 2016.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International conference on machine learning, pages 71-79. PMLR, 2013.
Trang Tran, Lam M Nguyen, and Quoe Tran-Dinh. Shuffling gradient-basse methods with momentum. arXiv preprint arXiv:2011.11884 2020.
Bicheng Ying, Kun Yuan, Stefan Vlaski, and Ali H Sayed. Stochastic learning under random reshuffling with constant step-sizes. IEEE Transactions on Signal Processing, 67(2):474-489 2018.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Can single-shuffle sgd be better than reshuffling sgd and gd? arXiv preprint arXiv:2103.0700 07009,, 2021.


Reviews:
[{"review_id": "ztKEO9LVF0N", "reviewer": "Reviewer_WHdM", "summary": "The paper shows that there exists classes of quadratic objectives where single shuffling or random reshuffling cannot offer improvements over SGD with-replacement sampling unless the number of passes exceeds the condition number of the problem. The paper supplements these lowerbound constructions with matching upperbounds that apply to the class of functions considered in their lowerbound construction. In addition, the paper offers simulations supplementing their theoretical results.", "questions": "", "limitations": "", "rating": 7, "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": "I found the paper to be an interesting read and the technical results appear correct. The results appear to have little to do with how SGD is run in practice, which potentially explains why the result appears to be at odds with running SGD with and without replacement in practice -- from my experience, SGD with random reshuffling dominates with replacement SGD in terms of its convergence behavior. \n\nOne discrepancy can be elaborated as follows: The construction used in this paper is different from the multiplicative noise oracle view of analyzing SGD, where, we do not see a full view of all eigendirections of hessian of the objective when we sample one component of the finite sum. In the construction used by this paper, we get a full view of the hessian based on the construction used say in equation (1) - you could take the second derivative of this function and you get a full rank second derivative matrix. This hardly resembles how SGD is run in practice. See for example, the paper of Bach and Moulines (2013), Defossez and Bach (2015) - which work with least squares with a multiplicative noise oracle. In these cases, we get a rank-1 view of the hessian if we sample one term in a finite-sum. \n\nMoreover, note that when working with the multiplicative noise oracle, the matrix products obtained in SGD recursions do not commute with each other, unless, we deal with specific class of problems where each of the d-dimensions are independent of each other and we can decouple the recursions into a single dimensional recursion. Even in this case, note that we do not receive a full view of the Hessian of the problem, and that reflects more appropriately how SGD is run in practice for finite sum problem instances faced in machine learning settings. Note that in order to get a full view of the hessian, one may require to use a mini-batch size, that in some cases can be as large as the condition number of the problem, in order to see spectral concentration kick in, and for the empirical covariance matrix to start resembling the true Hessian.\n\n1. Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n) - Bach and Moulines (2013)\n2. Averaged Least-Mean-Squares: Bias-Variance Trade-offs and Optimal Sampling Distributions - Defossez and Bach (2015)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "HBAZMYUwrV0", "reviewer": "Reviewer_erne", "summary": "This paper studies lower bounds for without-replacement fixed-step-size SGD  (both single shuffling and random reshuffling) for the finite-sum optimization problem with an attention to dependence on the condition number of the problem. Their primary result is to prove a lower bound on the optimization error (realized by a convex quadratic construction) that suggests that unless the number of epochs $k$ is significantly larger than the condition number, neither single shuffling nor random reshuffling variants of without-replacement SGD outperform with-replacement SGD (previously, upper bounds for the with-replacement variants of SGD were considered to beat without-replacement SGD since often results did not take the condition number into account in the bounds). Moreover, they show their lower bound is tight with respect to a class of quadratics which includes the lower bound instance, suggesting that the analysis is somewhat tight. \n\nThe restriction on $k$ being large in order for without-replacement SGD to be more efficient is problematic for practical justification for using without-replacement SGD, since if $k$ is large enough, at some point one will prefer to use methods like conjugate gradient instead of using SGD, thus making the regime in which without-replacement experiences gains irrelevant to practice (since there is a better algorithm).", "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": "This paper is very well-written and clear, identifies a well-motivated, interesting question and a clean answer. It nicely builds upon previous work in the sub-area, provides improvements on pre-existing analysis, and challenges existing wisdom by highlighting the importance of the condition number parameter. I read the lower bound proofs and they seem correct.  I didn't check the (restricted upper bound) proofs as closely, but in my opinion (though requiring a lot of technical calculations), the restricted upper bounds were not as important to the results. The exposition was also clear.\n\nOne thought: It would be nice to say earlier on (somewhere in Section 3) an intuitive reason why the random reshuffling without-replacement lower bound requires three dimensions in the lower bound construction instead of two. (You are using one dimension to get the $1/nk^3 $ dependence, and the other to get the $1/(nk)^2$ dependence, but a little more insight into why the this construction has that dependence fall out would be nice.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I didn't see anything that's related to societal impact that needs to be addressed. \n\nThe authors were very clear about the limitations of their results,  as well as the opportunities for future work. The limitations of their results are reasonable enough for acceptance.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "AXCrRaMPy8C", "reviewer": "Reviewer_zgxB", "summary": "## I update my score after authors' rebuttal\nI thank the authors for their detailed rebuttal. I now understand better why and how the results can be useful. I hope that the authors would do a great job of fixing some of the confusing parts in their work, in particular about the exact novelty of their paper, most notably regarding the conditioning. As promised, I thought more about this work and decided to increase my rating from 4 to 5.\n####\n\nThis paper presents improved upper and lower bounds for shuffling-based algorithms, which are without-replacement variants of SGD. In particular, the authors consider Random Reshuffling, which reshuffles the functions at each epoch, and Single Shuffle that reshuffles them only once at the very start. For both methods, the authors provide bounds that take into account the conditioning number.\n\nThe abstract of the paper about the prior work ignoring the problem geometry looks like a big overstatement, while the title seems to claim something already known from prior literature. Thus, I find the results to have limited motivation, even though both upper and lower bounds are of some interest. Another small flaw of the upper bounds is that they are stated for quadratic objectives.", "questions": "", "limitations": "", "rating": 5, "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": "I am very confused by this work. On the one hand, it has new results that contribute to the theoretical development of shuffling-based methods, and it gives new guarantees for both RR and SS. On the other hand, the motivation for these guarantees is unclear. First of all, the works of (Ahn et al.) and (Mishchenko et al.) do provide conditioning numbers in their guarantees. Secondly, the message that RR/SS is only better after some number of epochs is essentially already known. It follows from the existing upper bounds of (Ahn et al.) and (Mishchenko et al.) and existing lower bounds of (Safran and Shamir) and (Rajput et al). All of these bounds show that RR/SS is better eventually but not immediately.\n\nI am also not sure why the authors are so interested in proving upper bounds for quadratic objectives. My understanding is that RR/SS is not used as a solver for quadratic problems but rather is a method widely adopted for training neural networks. From that perspective, it could be much more interesting if the authors studied the nonconvex settings where fewer guarantees are known and little is known about the tightness of existing bounds.\n\n### Small comments\nWhy not provide the new results in the summary table?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "0eg-9gNh9gk", "reviewer": "Reviewer_WsEL", "summary": "This paper compares the efficiency of using different variants of stochastic gradient descent to find the minimum of a function that is the sum of multiple convex functions. It focuses on the case where the minimum of the function is dramatically flatter in some directions than in others. More specifically, it compares using a random sample at each time step, going through the samples in a fixed cycle, and repeatedly going through the entire list of samples in a random order. The conclusion is that the more complicated versions do not significantly outperform regular stochastic gradient descent unless the number of timesteps is unreasonably large.", "questions": "", "limitations": "", "rating": 6, "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 notes that comparable analyses have been carried out before, but that they treated parameters other than $n$ and $k$ as being constant, and generally gave results less favorable to SGD. This paper's version of the comparison appears to be new, although I am not familiar enough with the literature to be sure.\n\nThe paper's organization is good and the proofs are generally solid. However, the functions used for theorem 2 appear to violate assumption 1 due to half of the $f_i$ having no $x_3^2$ term.\n\nThis appears to make a useful contribution to the question of how one should try to minimize a convex function chosen from a family by arguing that the more complicated methods of choosing what sample to use when do not necessarily make a useful improvement over straight SGD.\n\n----------------------------edit-------------------------\n\nI stand by my original assessment.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

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

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

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