Permutation-Based SGD: Is Random Optimal?
Authors: Shashank Rajput
Kangwook Lee
Dimitris Papailiopoulos
Venue: ICLR 2022 Poster (2022)
Keywords: Convex Optimization
Stochastic Optimization
Large Scale Learning

Abstract: A recent line of ground-breaking results for permutation-based SGD  has corroborated a widely observed phenomenon: random permutations offer faster convergence than with-replacement sampling. However, is random optimal? We show that this depends heavily on what functions we are optimizing, and the convergence gap between optimal and random permutations can vary from exponential to nonexistent. We first show that for 1-dimensional strongly convex functions, with smooth second derivatives, there exist optimal permutations that offer exponentially faster convergence compared to random. However, for general strongly convex functions, random permutations are optimal. Finally, we show that for quadratic, strongly-convex functions, there are easy-to-construct permutations that lead to accelerated convergence compared to random. Our results suggest that a general convergence characterization of optimal permutations cannot capture the nuances of individual function classes, and can  mistakenly indicate that one cannot do much better than random.

Published as a conference paper at ICLR 2022
PERMUTATION-BASEL SGD: Is RANDOM OPTIMAL?
Shashank Rajput
Kangwook Lee
Dimitris Papailiopoulos
University of Wisconsin-Madison
ABSTRACT
A recent line of ground-breaking results for permutation-baset SGD has corrobo- rated a widely observed phenomenon: random permutations offer faster conver- gence than with-replacement sampling. However, is random optimal? We show that this depends heavily on what functions we are optimizing, and the conver- gence gap between optimal and random permutations can vary from exponential to nonexistent. We first show that for 1-dimensional strongly convex functions, with smooth second derivatives, there exist permutations that offer exponentially faster convergence compared to random. However, for general strongly convex functions, random permutations optimal. Finally, show that for quadratic, strongly-conve functions, there are casy-to-construct permutations that lead to accelerated convergence compared random. Our results suggest that general convergence characterization of optimal permutations cannot capture the nuances of individual function classes, and can mistakenly indicate that one cannot do much better than random.
INTRODUCTION
Finite sum optimization seeks to solve the following:
a
min F(x) = Σ M()).
Stochastic gradient descent (SGD) approximately solves finite sum problems, by iteratively updating the optimization variables according to the following rule:
It+1 == x - V fo, (x.),
(2)
where a the step size and 0; E [n]] = (1. nn is the index of the function sampled at iteration t. There exist various ways of sampling d,, with the most common being with- and without-replacemen sampling. In the former, a; is uniformly chosen at random from [ni], and for the latter, o, represents the 1-th element of random permutation of [r]]. We henceforth refer to these two SGD variants as vanilla and permutation based, respectively.
Although permutation-bu based SGD has been widely observed to perform better in practice (Bottou 2009) Recht & Ré 2012]] 2013). the vanilla version has attracted the vast majority of theoretical analysis. This is because of the fact that each iteration, in expectation the update is scaled version of the true gradient, allowing for simple performance analyses of the algorithm, e.g., see (Bubeck al. 2015).
Permutation-based SGD has resisted a tight analysis for a long time. However, a recent line of breakthrough results provides the first tight convergence guarantees for several classes of convex functions F (Nagaraj et al. 2019)) Safran & Shamir 2019 Rajput et al. 2020 Mishchenko et al.
2020 Ahn al. |020 Nguyen al.) 20200). These recent studies mainly focus on two variants of permutation- based SGD where (1) a new random permutation is sampled at each epoch (also known
as RANDOM ReSHUFFLE) (Nagaraj et al.) 20199) Safran & Shamir 2019) Rajput et al. 2020), and (2)
a random permutation is sampled once and is reused throughout all SGD epochs (SINGLE SHUFFLE)
(Sfrrnn & Shamir 2019 Mishchenko et al. 2020 Ahn et al. 2020).
"Correspondence Shashank Rajput (rajput3 @ wisc.edu)

---

Published as a conference paper at ICLR 2022
Perhaps interestingly, RANDOM RESHUFFLE and SINGLE SHUFFLE exhibit different convergence rates and a performance gap that varies across different function classes. In particular, when run for K epochs, the convergence rate for strongly convex functions is ((/nkk² for both RANDOM RESHUFFLE and SINGLE SHUFFLE (Nagaraj al. 2019 Ahn et al. 2020 Mishchenko et 2020). However, when run specifically on strongly convex quadratics, RANDOM RESHUFFLE experiences an acceleration of rates, whereas SINGLE SHUFFLE does not (Safran & Shamir 2019: Rajput et al.)
2020 Ahn et al. [2000] MMshhhenko et al. 2020). All the above rates have been coupled by matching
lower bounds, at least up to constants and sometimes log factors (Safran & Shamir 2019 Rajput
et al. 2020).
From the above we observe that reshuffling at the beginning of ev- ery epoch may not always help. But then there are cases where RANDOM RESHUFFLE is faster than SINGLE SHUFFLE, implying that certain ways of generating permutations are more suited for certain subfamilies of func- tions.
Algorithm 1 Permutation-basse SGD variants
Input: Initialization wy step size a, epochs K I: a a random permutation of [x]]
2: for l: = 1....,K. K do
3:
if IGD then
4:
O² = -11,2....,
5: else if SINGLE SHUFFLE then
6:
O² =
else if RANDOM RESHUFFLE then
The goal of our paper is take first step into exploring the relation- ship between convergence rates and the particular choice of permutations. We are particularly interested in un- derstanding if random permutations are as good as optimal, or if SGD can experience faster rates with carefully crafted permutations. As we see in the following, the answer the above is not straightforward, and depends heavily on the function class at hand.
8:
O² random permutation of [n]]
end if
10:
if FLIPFLOP and k even then
11:
0² reverse of oh=1
12:
end if
13:
for = 1, 1,..., n, do
14:
x/. == x oV fot (x
Epoch A
15:
end for
k+ := x
16:
17:
end for
Our Contributions: We define as permutation-basser SGD to be any variant of the iterates in 2 where permutation of the n. functions, at
Plain
with FLIPFL.OP
RR Q
Thm.
the start of each epoch, can be gen- erated deterministically, randomly, or
n2K
nK3
n²
7K3 1
SS
S2
Thm.
with a combination of the two. For example, SINGLE SHUFFLE, RAN- DOM RESHUFFLE, and incremen- tal gradient descent (IGD), all permutation- banede SGD variants (see Algorithm|]
T.Ke
n²
1
IGD
Ω
Thm.
K2
n2K²
K3
Table 1: Convergence rates of RANDOM RESHUFFLE (RR), SINGLE SHUFFLE (SS) and INCREMENTAL GRA- DIENT DESCENT (IGD) on strongly convex quadratics: Plain vs. FLIPFLOP. Lower bounds for the "plain" ver- sions are taken from (Safran & Shamir 2019). When K, that when the training set is much larger than the number of epochs, which arguably is the case in practice, the convergence rates of RANDOM RESHUF- FLE,SINGLE SHUFFLE, and INCREMENTAL GRADIENT DESCENT are Ω x 2 2(,Ak)) ). and Ω {²)) respec- tively. On the other hand, by combining these methods with FLIPFLOP the convergence rates become faster, i.e., Ō ), Ō k)) and Ō + respectively.
We first want to understand-even in the absence of computational constraints in picking the optimal permutations what is the fastest rate one can get for permutation-bastt based SGD? In other words, are there per- mutations that are better than random in the eyes of SGD?
Perhaps surprisingly, we show that there exist permutations that may of- fer up exponentially faster conver- gence than random permutations. but for a limited set of functions. Specifically, we show this for 1 1-dimensional functions (Theorem T). However, such exponential improvement is no longer possible
2

---

Published as a conference paper at ICLR 2022
in higher dimensions (Theorem 2). for general strongly convex objectives (Theorem 3 where random is optimal. The above highlight that an analysis of how permutations affect convergence rates needs to be nuanced enough to account for the structure of functions hand. Otherwise, in lieu of further assumptions, random permutations may just appear to be as good as optimal.
In this work, we further identify subfamily of convex functions, where there exist easy-to- generate permutations that lead accelerated convergence. We specifically introduce a new technique, FLIPFLOP, which can be used in conjunction with existing permutation-based methods, e.g. RAN- DOM RESHUFFLE, SINGLE SHUFFLE, or INCREMENTAL GRADIENT DESCENT, to provably improve their convergence on quadratic functions (Theorems 4 5 and p). The way that FLIPFLOP works is rather simple: every even epoch uses the flipped (or reversed) version of the previous epoch's permutation. The intuition behind why FL.IFFLOP leads faster convergence is as follows. Towards the end of an epoch, the contribution of earlier gradients gets attenuated. To counter this, we flip the permutation for the next epoch so that every function's 's contribution is diluted (approximately) equally over the course of two consecutive epochs. FLIPFLOP demonstrates that finding better permu- tations for specific classes of functions might be computationally easy. We summarize FLIPFLOP's convergence rates in Table D and report the results of numerical verification in Section 6.2
Note that in this work, we focus on the dependence of the error on the number of iterations, and in particular, the number of epochs. However, we acknowledge that its dependence other parameters like the condition number also very important. We leave such analysis for future work.
Notation:
We use lowercase for scalars (a), lower boldface for vectors (a), and upper boldface for matrices (A).
2 RELATED WORK
Gürbüzbalaaan et al. 2019a b) provided the first theoretical results establishing that RANDOM RESHUFFLE and INCREMENTAL GRADIENT DESCENT (and hence SINGLE SHUFFLE) were indeed faster than vanilla SGD, they offered an asymptotic rate of O (1/K?) for strongly convex functions, which beats the convergence rate of O (1/nK) for vanilla SGD when K = (n)). Shamir 20 used techniques from online learning and transductive learning theory to prove an optimal convergence rate of Ö(1nn) for the first epoch of RANDOM RESHUFFLE E (and hence SINGLE SHUFFLE). Later, Haochen & Sra 2019 also established a non-asympiotic convergence rate of Ô G + RT) when the objective function is quadratic, or has smooth Hessian.
Nagaraj et al. (019) used very interesting iterate coupling based approach to give a new upper bound on the error rate of RANDOM RESHUFFLE, thus proving for the first time that for general strongly convex smooth functions, it converges faster than vanilla SGD in all regimes of n and K. This was followed by (Safran & Shamir 2019), where the authors were able to establish the first lower bounds, in terms of both and K, for RANDOM RESHUFFLE. However, there these upper and lower bounds. The gap in the convergence rates was closed by |Rajput et al. (2020). who showed that the upper bound given by Nagaraj et al. (2019) and the lower bound given by Safran & Shamir (2019) were both tight up to logarithmic terms.
gap in
For SINGLE SHUFFLE, Mishchenko al. (2020) and Ahn et al. (2020) showed an upper bound of Ö 0, 1 ). which matched the lower bound given earlier by (Safran & Shamir 2019). up to logarithmic terms. (Ahn et al. (2020) and Mishchenkk et al. (2020) also proved tight upper bounds for RANDOM RESHUFFLE, with a simpler analysis and using more relaxed assumptions than (Nagaraj et al., 2019) and (Rajput al.) 2020). In particular, the results by Ahn et al. (2020) work under the PE condition and do not require individual component convexity.
INCREMENTAL GRADIENT DESCENT strongly convex functions has also been studied well in literature (Nedić & Bertsekas 2001 Bertsekas 2011 Gürbüzbalaban et al. 2019a). More recently, Nguyen al. (2200) provide unified analysis for all permutation- based algorithms. The dependence of their convergence rates on the number of epochs K is also optimal for INCREMENTAL GRADIENT DESCENT, SINGLE SHUFFLE and RANDOM RESHUFFLE.
There has also been some recent work on the analysis of RANDOM RESHUFFLE on non non-strongly convex functions and non-convex functions. Specifically, Nguyen al. 20200) and Mishchenko
3

---

Published as a conference paper at ICLR 2022
al. (2020) show that there, RANDOM RESHUFFLE outperforms SGD under certain conditions. Mishchenko et al. (2020) show that RANDOM RESHUFFLE and SINGLE SHUFFLE beat vanilla SGD non-strongly convex functions after (2n)) epochs, and that RANDOM RESHUFFLE is faster than vanilla SGD on non-convex objectives the desired error is O()/vn).
Speeding up convergence by combining without replacement sampling with other techniques like variance reduction (Shamir 2016) Ying et al.) 2020) and momentum (Tran et al.) 2020) has also received some attention. In this work, we solely focus on the power of "good permutations" to achieve fast convergence.
PRELIMINARIES
We will combinations of the following assumptions: Assumption (Component convexity). f((x) are convex.
Assumption 2 (Component smoothness). fi(x)' 's are L-smooth, i.e.,
Yx, y Vf(()) V.(lg) S L| -
Note that Assumption immediately implies that F also has L-Lipschitz gradients:
Ya,y [VF(() VF s L|| - yyl- Assumption (Objective strong convexity). p-strongly convex, i.e.,
Vx, y F(y) 2 F(z)+ (VF(z), y - x) u x1|2.
Note that Assumption implies
vz, y: (VF(x) VF x y) 2 14 x1|².
(3)
We denote the condition number by which is defined as 4 It can be seen easily that > always. Let xx denote the minimizer of Eq. [ that is, x arg ming F(x).
1
We will study permutation- basedd algorithms in the constant step size regime, that is, the step size is chosen the beginning of the algorithm, and then remains fixed throughout. We denote the iterate after the i-th iteration of the k-th epoch by a/. Hence, the initialization point is z/j Similarly, the permutation of (1...., n) used in the k-th epoch is denoted by a², and its i-th ordered element is denoted by of. Note that if the ambient space is I-dimensional, then we represent the iterates and the minimizer using non-bold characters, i.e. x and x², to remain consistent with the notation.
In the following, due to lack of space, we only provide sketches of the full proofs, when possible. The full proofs of the lemmas and theorems provided in the Appendix.
4 EXPONENTIAL CONVERGENCE IN 1-DIMENSION
In this section, we show that there exist permutations for Hessian-smooth 1-dimensional functions that lead exponentially faster convergence compared random.
Assumption (Component soosthnnsmmothhesss... f((x''s 's have -mmooh second derivatives, that is,
Vz, y 2 f((x) - v f(()) s Lu yl-
We also define the following instance dependent constants: G == max; [[
max { ||abb x=11 G and G 2D...
Theorem 1. Let Assumptionss 2 3nd Ahold. hhold. Let D and G be as defined above. If + then there exists sequence of permutations a² 22....,a* oK such that using those permutations from any initialization point 2 gives the error
lorK x S (D 4naG)e -CK
where C = I6(L +G
4

---

Published as a conference paper at ICLR 2022
An important thing to notice in the theorem statement is that the sequence of permutations o¹, 00,0? ..... ..... only depends the function, and not on the initialization point zo- This
MAV
implies that for any such function, there ists a sequence of permutations o², o² ,...., ox which gives exponentially fast convergence, conditionally of the initialization. Note that the convergence rate slower than Gradient Descent, for which the constant 'C" would be larger. However, here we are purely interested in
the convergence rates of the best permutations and their (asymptotic) dependence on K.
Aare
10
of epochs
Proof sketch The core idea is to establish that there exists an initialization point æt (close to the minimizer w²), and a sequence of permuta- tions such that that starting from zj and using that sequence of permutation leads exactly to the minimizer. Once we have proved this, we show that if two parallel runs of the optimiza- tion process are initialized from two different iterates, and they are coupled so that they use the exact same permutations, then they approach each other at an exponential rate. Thus, we the same permutation from any initialization point, it will converge to the minimizer at an exponential rate. See Figure [or graphical depiction of this sketch. We note that the figure is not the result of an actual run, but only serves to explain the proof sketch.
Figure 1: proof sketch.) Assume that the minimizer is at the origin. The proof of Theorem [ first shows that there exists an initialization and a sequence of permutations, such that using those, we get to the exact minimizer. Let the sequence of iterates for this run be x Consider parallel run, which uses the same sequence of permutations, but an arbitrary initialization point. Let this sequence be Tk- The figure shows how x converges to the exact optima, and the distance between z and Tę decreases exponentially, leading to an exponential convergence for zk.
(A graphical depiction of Theorem I's
LOWER BOUNDS FOR BERDU SGD
The result in the previous section leads wonder if exponentially fast convergence can be also achieved in higher dimensions. Unfortunately, for higher dimensions, there exist strongly convex quadratic functions for which there does not exist any sequence of permutations that lead to an exponential convergence rate. This is formalized in the following theorem.
Theorem 2.
For any n 2 (n must be even). there exists a 2n + 1-dimensional strongly convex function F which is the mean of convex quadratic functions, such that for every permutation- algorithm with any step size,
|| n
x x011==
=
n K2
This theorem shows that cannot hope to develop constant step size algorithms that exhibit exponentially fast convergence in multiple dimensions.
Proof sketch Here we give a proof sketch for simpler version of the theorem, which works in 2-Dimensions, for n = 2, and when the step size a = Q(1/K). Consider F(x, = (x, 1/ (x,, such that
x²
y² y +
[1 = - x + and
Hence, F (x² + 2) ). and has minimizer at the origin. Each epoch has two possible permutations, (1, (2, 1). Working out the details manually, it be that regardless of the permutation, = + y0 k+1 = + v that is, the sum of the co-ordinates keeps increasing. This can be used to get bound the error term [
5

---

Published as a conference paper at ICLR 2022
Next, we show that in I-Dimension, individual function convexity might be necessary to obtain faster rates than RANDOM RESHUFFLE.
Theorem 3. There exists I-Dimensional strongly convex function F which is the mean of two quadratic functions $1 and J2 such that one of the functions is non-convex. Then, every permutation- based algorithm with constant step size a S gives an error of at least
K-1 2
x²11
K2
Proof sketch The idea behind the sketch have one of the two component functions as strongly concave. This gives it the advantage that the farther away from its maximum the iterate is, the more pushes the iterate away. Hence, it essentially results increasing the deviation in each epoch. This leads to slow convergence rate.
In the setting where the individual Si may be non-convex, Nguyen et al. (020) and Ahn et al. (2020) show that SINGLE SHUFFLE RANDOM RESHUFFLE, and INCREMENTAL GRADIENT DESCENT achieve the error rate of O (²zz for a fixed n. In particular, their results only need that the component functions be smooth and hence their results apply to the function from Theorem 3 The theorem 2, this is the best possible error rate, for any permutation- based algorithm- deterministic or random. Hence, at least for n = 2, the three algorithms are optimal only
above essentially shows that when
when the component functions considering the dependence of the convergence rate on K. It possible that these are not optimal, further take into account the dependence of the convergence K. Indeed, we consider the dependence on n as well, INCREMENTAL GRADIENT DESCENT has convergence rate of (2(1K²²) (Safran Shamir 2019), whereas the other two have convergence rate (1/nk33)
possibly be non-convex. However, note that here
the combination of both n and
Ahn et al. 2020).
FLIPPING PERMUTATIONS FOR FASTER CONVERGENCE QUADRATICS
In this section, we introduce a new algorithm FLIPFLOP, that can improve the convergence rate of SINGLE SHUFFLE, RESHUFFLE, and INCREMENTAL GRADIENT DESCENT strongly convex quadratic functions.
The following theorem gives the convergence rate of FLIPFLOP wITH SINGLE SHUFFLE:
Assumption 5. f+(x)) 's are quadratic.
Theorem 4. If Assumptions 7 3 and hold, then running FLIPFLOP WITH SINGLE SHUFFLE
for K epochs, where K 2 3/2 log(nK) max {1, /n. is an even integer, with step size
n
logg()K) gives the error pnk
E || K-
x 111
=
1
(4)
n²
nk*
For comparison, Safran Shamir (2019) give the following lower bound on the convergence rate of vanilla SINGLE SHUFFLE:
E
K - x: 1011]] = nk2
(5)
Note that both the terms in Eq. 4 are smaller than the term in Eq. (5) In particular, when n >>> k² and n is fixed
vary K, the RHS of Eq. (5) decays as O R whereas the RHS of Eq. (4)
decays as Ö ( Otherwise, when 2 > n and is fixed as we vary n, the RHS of Eq. (5) decays O(L), whereas the RHS of Eq. (4) decays Ō ((,)). Hence, in both the cases, FLIPFLOP WITH
SINGLE SHUFFLE outperforms SINGLE SHUFFLE.
The next theorem shows that FI.IFFL.Op improves the convergence rate of RANDOM RESHUFFL.E:

---

Published as a conference paper at ICLR 2022
Normalized errer
Nommllzed
Randam Reshuffle Flittlp
Single Shuffio
11 218
LiK"
11K7
Flytlop
Flottop KiD
11K?
of epochs
epochs
epochs
Figure Dependence of convergence rates on the number of epochs K for quadratic functions. The figures show the median and inter-quartile range after 10 runs of each algorithm, with random initializations and random permutation seeds (note that SS and IGD exhibit extremely small variance). We set 800, so that n > K and hence the higher order terms of K dominate the convergence rates. Note that both the axes are in logarithmic scale.
Theorem Asssmmttio for K epochs, where K 2 55k log(nk] max (1, T is even integer, with step size a
2 and hold, then running FLIPFLOP WITH RANDOM RESHUFFLE
10 (0lginK)) gives the error pnk
E |
K-1
x 111
=
n2
nK'
For comparison, /affran & Shamir (2019) give the following lower bound the convergence rate of vanilla RANDOM RESHUFFLE:
E
x K
x² x=11²] =
K2
nk3
Hence, we see that the regime when n >> K, which happens when number components in the finite sum of F is much larger than the number of epochs, FLIPFLOP WITH RANDOM RESHUFFLE much faster than vanilla RANDOM RESHUFFLE.
Note that the theorems above do not contradict Theorem 2. because for a fixed n, both the theorems above give a convergence rate of (1)
We also note here that the theorems above need the number of epochs be much larger than x. in which range Gradient Descent performs better than with or without- replacement SGD, and hence GD should preferred over SGD in that case. However, we think that this requirement on epochs limitation of our analysis, rather than that of the algorithms.
Finally, the next theorem shows that FLIPFLOP improves the convergence rate of INCREMENTAL GRADIENT DESCENT.
Theorem 6. If Assumptionss 7 and hold, then running FLIPFLOP WITH INCREMENTAL GD for K epochs, where 2 36x log (K)
) is an even integer, with step size a 6log nk
gives the error pnk
-0( 12 K3
E
K x
x
For comparison, Safran & Shamir (2019) give the following lower bound on the convergence rate of vanilla INCREMENTAL. GRADIENT DESCENT:
E
a K-1 x
52
K2
In the next subsection, we give short sketch of the proof of these theorems.
6.1 PROOF SKETCHI
In the proof sketch, we consider scalar quadratic functions. The same intuition carries over to a,3²
multi-dimensional quadratics, but requires involved analysis. Let fe(x)) b
7

---

Published as a conference paper at ICLR 2022
Assume that F(x) E f((z) has minimizer at O. This assumption is valid because it can be achieved by simple translation of the origin (see (Safran & Shamir 2019) for a more detailed explanation). This implies that Σ b 0.
For the sake of this sketch, assume 2 0, that is, we are starting at the minimizer itself. Further, without loss of generality, assume that σ = (1, 1,,,,..,,) n.). Then, for the last iteration of the first epoch,
F n (/(((1)-1))
- a a(a + bn)
(1 aan ) abn-
Applying this to all iterations of the first epoch, we get
II ana))ag
II (1 oxa)). f=i+1
(6)
Substituting =g we get
5 = -
II (1 oay)) -=++1
(7)
1=1
Note that the sum above is not weighted uniformly: 61 is multiplied by (1 ady). whereas b, multiplied by 1. Because alaa,,) weights were all 1, then would get 2 -a Σx= b, = 0. i... would not move away from the minimizer. Since we want to stay close to the minimizer, we want the weights of all the b, to be roughly equal.
see that b weight much smaller than bn If the
The idea behind FLIPFLOP add something like -a Ei= IT; aay) in the next epoch, to counteract the bias in Eq. (7). To achieve this, simply take the permutation that the algorithm used in the previous epoch and flip it for the next epoch. Roughly speaking, in the next epoch b will get multiplied by 1 whereas b, will get multiplied by I1 (1 aaz). Thus over two epochs, both get scaled approximately the same.
The main reason that the analysis for multidimensional quadratics is not simple as the 1-dimensional analysis sketched above is because unlike scalar multiplication, matrix multiplication not commu- tative, and the AM-GM inequality is not true in higher dimensions (Lai & Lim 2020; De Sa 2020). One way to bypass this inequality is by using the following inequality for small enough o::
II aA II - aA ii)-
11 <1-amp. amp.
t=1
Ahn et al. (2020) proved stochastic version of this (see Lemma 6 in their paper). We prove deterministic version in Lemma (in (in the Appendix).
6.2 NUMERICAL. VERIFICATION
We verify the theorems numerically by rumning RANDOM RESHUFFLE, SINGLE SHUFFLE and their FLIPFLOP versions on the task of mean computation. We randomly sample n = 800 points from a 100-dimensional sphere. Let the points be 2; for 1,..., n. Then, their mean the solution to the following quadratic problem arg min, F(xx) ا. i-1 x 1: We solve this problem by using the given algorithms. The results are reported in Figure 2 The results are plotted in a log-log graph, so that we get to see the dependence of error on the power of K.
Note that since the points are sampled randomly, INCREMENTAL. GRADIENT DESCENT essentially becomes SINGLE SHUFFLE. Hence, to verify Theorem 6 we need 'hard' instances of INcREMENTAL GRADIENT DESCENT, and in particular we use the ones used in Theorem in (Safran & Shamir 2019). These results are also reported in log- graph in Figure 2
We also tried FLIPFLOP in the training of deep neural networks, but unfortunately we did not see a big speedup there. We ran experiments results for which are in Figure 3 and its details are in Appendix[H] The code for all the experiments jput. jput//fljpppppppp
logistic regression for I-Dimensional artificial data, the
can be found at /tttttt///// / thub. com/ shashankra hwwtssaaaaaaaaauttaaaoa
8

---

Published as a conference paper at ICLR 2022
Normelized enrer
Nomalired
Normalzee
Randam Reshuffle Flittlp with
D/K" 21K
Single Shufflo
11K"
Flyttop with SS
2
Flottop with KiD
11K?
of epoc hs
Number epachs
Number epochs
Figure Dependence of convergence rates on the number of epochs K for logistic regression. The figures show the median and inter-quartile range after 10 runs of each algorithm, with random initializations and random permutation seeds (note that IGD exhibits extremely small variance). We set n. = 800, so that > K and hence the higher order terms of K dominate the convergence rates. Note that both the axes are in logarithmic scale.
6.3 FASTER PERMUTATIONS FOR NON-QUADRATIC OBJECTIVES
The analysis of FlipFlop leverages the fact that the Hessians of quadratic functions are constant. We think that the analysis FlipFlop might be extended to strongly convex functions or even PE. functions (which are non-convex general). under some assumptions on the Lipschitz continuity of the Hessians, similar to how Haochen & Sra (2019) extended their analysis of quadratic functions to more general classes. A key take-away from FlipFlop is that had to understand how permutation based SGD works specifically for quadratic functions, that is, we did white-box analysis. In general, we feel that depending on the specific class of non-convex functions (say deep neural networks), practitioners would have to think about permutation-based SGD in white-box fashion, to come up with better heuristics for shuffling.
In a concurrent work by Lu et al.) (202I). it is shown that by greedily sorting stale gradients, permutation order can found which converges faster some deep learning tasks. Hence, there do exist better permutations than random, even for deep learning tasks.
7 CONCLUSION AND FUTURE WORK
In this paper, we explore the theoretical limits of permutation-ban SGD for solving finite sum optimization problems. We focus on the power of good, carefully designed permutations and whether they can lead to much better convergence rate than random. We prove that for 1-dimensional, strongly convex functions, indeed good sequences of permutations exist, which lead convergence rate which is exponentially faster than random permutations. We also show that unfortunately, this is true for higher dimensions, and that for general strongly convex functions, random permutations might be optimal.
However, think that for some subfamilies of strongly convex functions, good permutations might exist and may be easy to generate. Towards that end, we introduce a very simple technique, FLIPFL OP.P, generate permutations that lead to faster convergence on strongly convex quadratics. This is black box technique. that is, it does not look at the optimization problem to come up with the permutations; and can be implemented easily. This serves as an example that for other classes of functions, there can exist other techniques for coming up with good permutations. Finally, note that we only consider constant step sizes in this work for both upper and lower bounds. Exploring regimes in which the step size changes, e.g., diminishing step sizes, is very interesting open problem, which we leave for future work. We think that the upper and lower bounds this paper give some important insights and can help in the development of better algorithms or heuristies. We strongly believe that under nice distributional assumptions on the component functions, there can exist good heuristics to generate good permutations, and this should also be investigated in future work.

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
This paper explores the theoretical limits of convergence rates of variants of popular SGD type algorithms. Thus, the authors do not think there are any ethical concerns regarding the paper.
REPRODUCIBILITY STATEMENT
The proof for all the theoretical claims are provided in the Appendix. The assumptions and notations are specified in the Preliminaries section (Section 3 The code for all the experiments can be found at /ttttts:p/ggiteeeeee com/ http://cw./h.hahaaaeeeeee jut /flipfflpp.p
REFERENCES
Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. Sgd with shuffling: optimal rates without component convexity and large epoch requirements, 2020.
Dimitri Bertsekas. Incremental gradient, subgradient, and proximal methods for convex optimiza- tion: A survey. Optimization for Machine Learning, 2010(1-38):3, 2011.
Léon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. Unpublished open problem offered to the attendance of the SLDS 2009 conference, 2009. URL http
///eeon.botton otg/papers hww.r//ttootttttoe -oee--dd------r----o-eeee em 2009
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-357, 2015.
Christopher M De Sa. Random reshuffling is not always better. Advances Neural Information Processing Systems, 33, 2020.
M Gürbüzballban, Asuman Ozdaglar, and Pablo A Parrilo. Convergence rate of incremental gradient and incremental newton methods. SIAM Journal Optimization, 29(4):2542-2565 2019a.
Mert Gürbüüzallaban, Asu Ozdaglar, and Pablo A Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, pp. 1-36, 2019b.
Jeff Haochen and Suvrit Sra. Random shuffling beats sgd after finite epochs. In International Conference on Machine Learning, pp. 2233,, 2019.
Zehua Lai and Lek-Heng Lim. Recht-ré noncommutative arithmetic-geometti false. In International Conference on Machine Learning, pp. 5608-5617. PMLR, 2020.
conjecture is
Yucheng Lu, Si Yi Meng, and Christopher De Sa. A general analysis of example-selection for
stochastic gradient descent. International Conference Learning Representations, 2021.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. ArXiv, abs/2006.05988. 2020.
Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. Sgd without replacement: Sharper rates for general smooth convex functions. In International Conference Machine Learning, pp. 4703-4711, 2019. 2019.
Angelia Nedić and Dimitri Bertsekas. Convergence rate of incremental subgradient algorithms. In Stochastic optimization: algorithms and upplications, pp. 223-264. Springer, 2001.
Yurii Nesterov. Introductory Lectures on Convex Optimization A Basic Course, volume 87 of Applied doi: 10.1007/978-114449-8888 URL
Optimization. Springer, 2004. ISBN 978- 978-1-46113-461-33
https::/doi.com org. http://..1111110110 10111111100077111-11------33
Lam M Nguyen, Quoc Tran-Dinh Dzung T Phan, Phuong Ha Nguyen, and Marten Dijk. A
unified convergence analysis for shuffling-type gradient methods, arXiv preprint arXiv:2002.08246.
2020.
10

---

Published as a conference paper at ICLR 2022
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. Closing the convergence gap of sgd without replacement. In International Conference Machine Learning, pp. 7964-7973. PMLR, 2020.
Benjamin Recht and Christopher Ré. Beneath the valley of the noncommutative arithmetic- arithmetic-geometric mean inequality: conjectures, case-studies, and consequences. arXiv preprint arXiv: arXiv:/202.411 /202.4184, 2012.
Benjamin Recht and Christopher Ré. Parallel stochastic gradient algorithms for large-scale matrix completion. Mathematical Programming Computation, 5(2):201 -266, 2013.
Itay Safran and Ohad Shamir. How good is sgd with random shuffling?. 2019.
Itay Safran and Ohad Shamir. Random shuffling beats sgd only after many epochs on ill-conditioned problems. arXiv preprint arXiv:2106.0m 100.020000008800, 2021.
M. Schneider. Probability inequalities for kernel embeddings in sampling without replacement. In AISTATS, 2016.
Ohad Shamir. Without-repplaeemen sampling for stochastic gradient methods. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 46-54, 2016.
Trang H Tran, Lam M Nguyen, and Quoe Tran-Dinh. Shufiling gradient- based methods with momentum. arXiv preprint arXiv:201 1884, 2020.
Bicheng Ying, Kun Yuan, and Sayed. Variance-reduced stochastic learning under random reshuffling. IEEE Transactions Signal Processing, 68: 18:1330-1440 140000110,.00011 2020.

---

Published as a conference paper at ICLR 2022
A DISCUSSION AND FUTURE WORK
Being the first paper (to the best of our knowledge) theoretically analyze the optimality of random permutations, we limited our scope to a specific, but common theoretical setting strongly convex functions with constant step size. We think that future work can generalize the results of this paper to settings of non-convexity, variable step sizes, as well as techniques like variance reduction, momentum, etc.
A.1 LOWER BOUNDS FOR VARIABLE STEP SIZES
All the existing lower bounds (to the best our knowledge) work in the constant step size regime (Safran & Shamir (2019): Rajput et al. (2020p; [Safran & Shamir (2021)). Thus, generalizing the lower bounds to variable step size algorithms would be a very important direction for future research.
However, the case when step sizes are not constant can be tricky to prove lower bounds, since the step size could potentially depend on the permutation, and the current iterate. more reasonable setting to prove lower bounds could be the case when the step sizes follow schedule over epochs, similar to what happens in practice.
A.2 FLIPFLOP ON RANDOM COORDINATE DESCENT
A shuffling scheme similar to FlipFlop has been used in random coordinate descent for faster practical convergence (see page 231 in Nocedal Wright (2006)). This should be further investigated empirically and theoretically in future work. Even though the current analysis of FlipFlop does not directly go through for random coordinate descent, we think the analysis can adapted to work.
B PROOF OF THEOREM
In certain places in the proof, would need that Thz To see how this is satisfied, note that we have assumed that a S Bn(L=+Ln1c]] in the theorem statement. Using the inequality S L in
S L gives that a an(L+(LnG/a) S TnI.
In this proof, we assume that the minimizer of is at 0 to make the analysis simpler. This assumption can be satisfied by simply translating the origin to the minimizer (Safran & Shamir (019).
There are three main components the proof:
Say that an epoch starts off at the minimizer. We prove that there exists at least one pair of permutations such that if we do two separate runs of the epoch, the first using the first permutation and the second using the second, then at the end of that epoch, the iterates corresponding the two runs end up opposite sides of the minimizer.
2. There exists a sequence of permutations and a point in the neighborhood of the minimizer, such that intializing at that point and using these sequence of permutations, we converge exactly to the minimizer.
3. Starting from any other point, we can couple the iterates with the iterates which were shown in the previous component, to get that these sequences of iterates come close each other exponentially fast.
We prove the first and second components in the Subsections B.I and B.2 and conclude the proof in Subsection B.3 where also prove the third component.
B. PERMUTATIONS IN ONE BPOCII
In this subsection, we prove that Zu, I1,... In are the iterates an epoch such that 2g = 0, then there exists a permutation of functions such that Jx 2 0. By the same logic, show that there exists a permutation of functions such that こ, < 0. These will give us control over movement of iterates across epochs.
12

---

Published as a conference paper at ICLR 2022
Order the gradients the minimizer, (f) in decreasing order. WLOG assume that it is just f1, V......, Vnn. We claim that this permutation leads to In 2 0.
We will need the following intermediate result. Let y/, 34-1 be such that yt Dh-1 aV Assume I L/L and yi-1 2 1;-1- Then,
V/ - x; = yi-1 - I:-1 al a(VVi(yii V(((os-)))
2 V4-1 -i-1 ab(yii-1 xi-1)
= (1 - (yi( 21-1)
2 0,
(8)
that is, V/-1 2 2i-1
2
Because the minimizer, we know that Σ Vf((0) Also, recall that zo There can be two cases:
1. Vi E [1,n] : :2 < O. This cannot be true because Vi Sis n2 1 : D3 < 0, then
( 2 a Vf(0) 2 0,
In
1=1
where we used the fact that (z( S Vfi(v) S and fi is convex.
2. Thus, Di E [1, n| x, 2 0. Now, consider the sequence yi, li.l..... such that yi 0 and for j i 1, M/j 1 - aV ʃj (リj Then because 1/L and xq yı
get that 2y 2 My for all j 2 (Using Ineq. (8)
Hence, there is an 2 1 such that 2; 2 ys = 0, and further æ, 2 yj for all j 2 i. Next, we repeat the process above for Yts ... yn. That is, there can be two cases:
1. Vj E [i + 1, Uj < 0. This cannot be true because if Vj 1i+1 S J 1: < 0. then
Yn VVf(()) 2
vf 2
2. Thus, 3j E 1, 2 0. Now, consider the sequence 2j. 2j+1..... such that
2j and for & j + 2b žk-1 a (z Then because S 1/L and yソ 2 2j = O. we get that yk 2 for all k j (Using Ineq.
Hence, there exists an integer j > <>> 0 such that yj 2 O. We have already proved that æj 2 Uj- Thus, have that .. O. We continue repeating this process (apply the same two cases above for 2j, :j+..-.., Zn. and so on), to get that v, 2 O. We define to be this non-negative value of Fip- Note that the following lemma gives that the gradients are bounded by G
Lemma 1. Define G == max, f1 II and D max { ||ا]
x= I1. 27, }. If Assumptions and
hold, and a SunI. then for any permutation- algorithm (deterministic or random), we have
Vi,j.k k =||= x=11 2D, and
[+f s G 2DL.
Because the gradients are bounded by G, we get that p < naG.
Similarly, we can show that the reverse permutation leads to Fn < 0. We define g to be this non- positive value of Ent Because have assumed that the gradients are bounded by G, we get that 2 -naG.
B.2 EXACT CONVERGENCE TO THE MINIMIZER
In this section, we show that there exists a point such that if we initialize there and follow a specific permutation sequence, we land exactly the minimizer.
13

---

Published as a conference paper at ICLR 2022
In particular, we will show the following: There exists point in [4g, 4p] such that if we initialize there and follow a specific permutation sequence, then we land exactly at the minimizer.
We show this recursively. We will prove that there exists point m x [4g, 4p] such that if the last epoch begins there, that is z = mx then we land at the minimizer at the end the last epoch, that is, 2 O. Then, we will show that there exists point m m-1 [4g. 4p] such that if the 40 K-1 K-1, then u
=- m= Repeating this for K 2, ....... 1, we get that there exists a point m. E [Ag, 4p] such that if we initialize the first epoch there, that is xp m., then there is a permutation sequence such that ultimately 2 O.
We prove that any point m² E [4q, 4p] can be reached at the end of an epoch by beginning the epoch at some point m²-1 E [4q, 4p), that is if zi- m then x4_ m'.
Case: m² E 4p]. this case, we show that m E [0, 4p]. We have proved in the previous subsection that there exists a permutation a such that if o 0 then xj-1 = p. Next, we have the following helpful lemma that we will also use later.
Lemma 2. Let To. .1........ In be a sequence of iterates in an epoch and yo: V1..... yr. be another sequence of iterates in an epoch such that both use the same permutation of functions. If S Ln( then
- 1yn - xol S (1 La) yo zol
S 11m Fnll S (1-
1yo xal-
If we set xo = -4p = 0 in Lemma and we follow the permutation a, then we get that
In yn E (xo y00 11-ammn anL, cx71j1
In - p E (4p 0) anL, any
(Since using o and y/o 0 results in y/. p.)
In 4p,
where we used the fact that a S TnL is the last step.
Thus, if =nd 4p and we follow the permutation o, then 1 2 4p.
Next, note that
- =/- a So(0 x2 i- = - a aa
1 = --1 - aV for fn (
Looking above, we see that af-1 continuous function of =:-'; - continuous function of 21 - and so on. Thus, using the fact that composition of continuous functions is continuous, we get that x is also continuous function of xn--1 We have shown that if ni that - is a continuous function of - we get that for any point m [p. 4p), there is at least one point m² 1 E [0, 4p], such that 2 - = mi-1 leads to -ي-ي- = m².
= 0, then x p and if x
4p, then 2x11 2 4p. Thus, using the fact that
Case: my E [4q, q]. We can apply the same logic as above show that there is at least one point m 1 E [4g. 0], such that x/ = m = x]_ m²
Case: m, E [q. p). WLOG assume that lql lp]. Let og be the permutation such that zff = and the epoch uses this permutation, then we end up at æ = q.
If we set xo 4p, = 0 in Lemma and we follow the permutation a. then we get that
In yn E (No - yu) 1 1--amL111 an4
2
14

---

Published as a conference paper at ICLR 2022
In - q E (4p - 0) anL, a7/
(Since using 04 and yo = 0 results in yn = q.)
In 2 q 4p anL) 2 2 3p 2 2p.
where we used the fact that a S Thus, if =nd-1 4p and we follow the permutation og. then - 2 2p. Thus, using similar argument of continuity as the first case, know that there a point m/ [0, 4p), such that an- m leads to 2/ xx m when the permutation 0q.
1 is the last step.
4nf.
B.3 SAME SEQUENCE PERMUTATIONS GET CLOSER
In the previous subsection, we have shown that there exists a point m. E [4g,44) and a sequence of permutations o², o² ..... g such that if xx) m and epoch j uses permutation σ¹, then a O. In this subsection, we will show that if xb initialized at any other point such that [z]]] < D, then using the same permutations a² _² ...., gives us that | (D + naG)e For this we will repeatedly apply Lemma 2 on all the K epochs. Assume that zig v with | D.
Let uf be the sequence of iterates such that yb m and uses the permutation sequence x.. be the sequence of iterates such that 2! n and uses the same permutation sequence o¹ o² ....,
a², 2 ...., o. Then, know that y O. Let
Then, using Lemma 2 gives us that l x I 1 m m (1 2 Thus, we get that luî am S | m2 pao Again applying Lemma Therefore, after applying K times, get
2 gives us that 1 2a S [n0 mm pan )a
1 xx 1100 m0 pan
Note that [xr]] = |1o0 S D, and lubl = |mm, with m E [4q, 4p). We showed earlier in Subsection B.I that [pl S naG and [g| naG. Therefore,
1 2 1 4naG (1- pan
2
Further, we know that y 0. Thus,
(1- (1-uam uan
K
Ir S ID + 4naGl
2
< D + 4naGle
Hon
Substituting the value of a completes the proof. Next we prove the lemmas used in this proof.
B.4 PROOF OF LEMMA M
We restate the lemma below.
Lemma. Define G max; f((x")) and D = max ||lbb - x=1. 2L
G- Assumptions 2 and
hold, and SanT. then for any permulation-based algorithm (deterministic or random), we have
Vi,j.k k +|a x 2D, and [VS}(})]| G* +DL.
This lemma says that for any permutation-based algorithm, the domain of iterates and the norm of the gradient stays bounded during the optimization. This means that we can assume bounds on norm of iterates and gradients, which is not true in general for unconstrained SGD. This makes analyzing such algorithms much easier, and hence this lemma can be of independent interest for proving future results for permutation- based algorithms.
15

---

Published as a conference paper at ICLR 2022
Remark 1. This lemmna does not hold in general for vanilla SGD where sampling is done with replacement. Consider the example with two functions fi (z) = x² - I, and f2(z) = z; and F(z) = fz(z) + f2(2). This satisfies Assumptions 2 and but one may choose f2 consecutively for arbirarry many iterations, which will lead the iterates a proportional distance away from the minimizer. This kind of situation can never happen for permutation-based SGD because we see every function exactly once in every epoch and hence no particular function can attract the iterates too much towards its minimizer, and by the end of the epochs most of the noise gets cancelled out.
Note that the requirement < believe the lemma should also hold in that regime. For the current paper, however, this stronger requirement suffices.
SienT. is stricter than the usual requirement
O ( but
Proof. To prove this lemma, we show two facts: If for some epoch k, || x=1| S D, then a) Vi: || x=1 < 2D and b) || ==1l || ==1l < D. To see how a) and b) are sufficient to prove the lemma, assume that they are true. Then, since the first epoch begins inside the bounded using b) that every subsequent epoch begins inside the same bounded region, that is || x*I| S D as well. Hence using a) we get that during these epochs, the iterates satisfy ||a=" 201 S 2D, which is the first part of the lemma. Further, this bound together with the gradient Lipshitzness directly gives the upper bound G + 2DL on the gradients. Thus, all we need to do to prove this lemma is prove a) and b), which we do next.
region| ||-]] x=1 D,
We will prove a) and b) for D [ax x=1|, T-4wno }. Once we do this, using will give us the exact statement of the lemma.
SAnL
Let ( - x=1 needed so that - x=1 2 2D. Within this region, the gradient is bounded by G + 2DL. Thus, the minimum number of iterations needed are 2D-D +2DL)
for some epoch k. Then, we try to find the minimum number of iterations
However,
2D-D
aG 2DLL
al S 2L)
(Using the fact that D >
2eno
(G
1- -. 2T. 2knaa
---na. I.
a(
I=4xnoL +LL
2xna
2kn
2 2n.
Thus, the minimum number iterations needed go outside the bound | -x"l 2 2D is more than the length of the epoch. This implies that within the epoch, | x=1 < 2D, which proves a). We prove b) next:
x
2
b
far (att)
x
n
faty (x)) + Σ
(V (x Vfaa (ax)))
x
Note that En V (x)) is just the sum of all component gradients at z5. that is V (zt)). Using this, we get
En Vfat (xt)
x
z * xx -a VaVFF + > Vf - Vffat (af)))
1 x
+
v fot (2f)) - V (xt)
(Triangle inequality.)
16

---

Published as a conference paper at ICLR 2022
0 x= no VF aT > | ax
where we used gradient Lipschitzness (Assumption 2) in the last step.
To bound the first term above, we use the standard analysis of gradient descent on smooth, strongly convex functions as follows
|| x" - naV F (x = 2 x²11 2n - x., vF(()( +n² VVF=5))
I 2 x x²1
2napllaa - x n² (x) ||
(Using Ineq. (3)
= (1 nap)
|| - x²I
$1 + na(na
V V= xx)) || || - مر |2 x x=1??)
$ (1 nap) || x ||² + naanaa || - x || اب | - x x01 11
(Using gradient Lipschitznest
nap
-| x²I|
||
+ - p) =|
S (1 nap || x²1
where in the last step we used that a S a since a S SueT.. we get
Substituting this incquality in Ineq.
n
|| n x=1l S V - nayi I x11 +
aL
x
2=
(1- || w'1l
+ ab
|
1=0
We have already proven a) that says that the iterates at satisfy |a: x=1| S 2D. Using gradient
Lipschitzness, this implies that the gradient norms stay bounded by G* DDL. Hence, | x!1 s ai(G' + 2DL.. Using this,
|| 1
x²1l
5
1 11
nay
|
x11 + + aL Σ
ai(G +DLL)
==
1
1
nap
n D D
Σ ai(G +DLL)
2
2 nap
D D+ D+n 2DL)
D,
where we used the fact that D 2 2enaG
in the last step.
1-inaaL
B.5 PROOF OF LEMMA 2
Without loss of generality, let a = (1.2,3....,,)) analysis goes through for any other permutation too.
n).
This is only done for ease of notation. The
First we show the lower bound. WLOG assume > zq. Because a < 1/L, we have that Vi, y > x; by induction (see the equations below). Then,
Iz = Vi-1 - Ti-1 - -fiii) (f((==1))
2 Mi-1 r;-1 aL (1)-1 xz-1)
= (1 - aL) 2;-1)
att)((no x0)
17

---

Published as a conference paper at ICLR 2022
2 (1 - iaL)(V0 -ru)-
(10)
Next we show the upper bound
Yn In yo 20 (V - -ff(((11))
y0 20 a
f((wn) v(((z))) + a
Σ
(V - V\i(o))))))))))>>>)))))) - V/i(u
+ V(i((=-)))
i=1
= V/ - 3o - nac (V(())) VF(mn)) + a
(VSi(y)) V/i(2)) V/i(0-1) V.((+=))))
1=1
(1 (uo) xo) (V/()0)) Vf((z))
Vi((--)) V((o-)))((()))))) (f(
(Using strong convexity)
We use the fact that the function is twice differentiable:
90
Wi-1
yn (1 (ynp))( - mo) +
Σ
fi(tdtt
2=1
(1 (wo - 20)
240
p4 190 zol
1h-1 V2 f((t)dt
+
V2 f((t)dt
V2 ftt)dtt
1=1
J4-1
11-1+(00000 20)
= (1 - (30 - vo)
90
Mh-1
+ a
fi(t) f2 - 3a + t))dt
fet((t)dt)
11-1+(00-20 (2)
In the above, we used the convention that J f(#)dz is the same as - Sh f(z)dr if b. Now, use the Hessian Lipschitzness to bound the term as follows
V0 Lu 1 - ddl / (
Va In 5 (1 napp)(0 - -x0) + Σ
22 si()dd 1=1-1
i=1
20 LHGan
24
< (1 nap) - 20) ) +
V2fi(t)dt
-
30
1-100
n
Bi-1
(1 napi) - m0) + Ln 2 (x0 - vo)
14-1+(90 (xo)
i=1
n
(1 nop)(yo -0)) Lg ( vo) +
T((Vo Ho) (1/ x:))
t=1
(1 nap)(1n xx0) + LnGaan 2 yo) +
L(iaL)((0 - xo)
i=
(Using Ineq. (10).
< (1 nap)(1n =00) + Gaannn (xo vo) + 2 -xo). "
Thus, we have a S 2m(L+LLaG) then
Un - In < (1 pma
(yo - -ro).
C PROOF OF THBOREM 2
To prove this theorem, we consider three step-size ranges and do a case by case analysis for each of them. We construct functions for each range such that the convergence of any permutation-baase
18

---

Published as a conference paper at ICLR 2022
algorithm is "slow" for the functions their corresponding step-size regime. The final lower bound the minimum among the lower bounds obtained for the three regimes.
In this proof, we will use different notation from the rest of the paper because we work with scalars in the proof, and hence the superscript will denote the scalar power, and not the epoch number. We will use a denote the i-th iterate of the k-th epoch.
We will construct three functions F1 (x). Fu( and (2( each the means of n component functions, such that
Any permutation-base algorithm on (xx with a E 12(n-1)KE 3 and initialization
11, 0 results in
F 1|
Ω
12.3 K2
F1 will be an n--dimensional function, that a E R". This function will have minimizer at 0 E IR. NOTE: This is the "key" step-size range, and the proof sketch explained in the main paper corresponds to this function's 's construction.
Any permutation -baeed algorithm on F2(9) with a E [ + and initialization yı.0 results in
yy 112
52
n
F2 will be an n--imensional function, that is E R", This function will have minimizer O E RR" The construction for this is also inspired by the construction for Fi, but this is constructed significantly differently due to the different step-size range.
Any permutation- based algorithm on F2(2) with a & 1yKE- 1.1 and initialization 21,0 = 1 results in
|= = -2 (2)
F3 will an 1-dimensional function, that E This function will have minimizer
Then, the 2n + I-dimensional function F(xx", T [ (x) + F2(3) + F3(2) will show bad convergence any step-size regime. This function will have minimizer at O E 222+1 Furthermore,
n2 LI 3 FF V2 P3, V 2L1,
that is, Fi. F2, Fg. and F are all T-strrnglyy convex and 2T.ssmothh.
In the subsequent subsections, we prove the lower bounds for Fi, F2, and F3 separately.
NOTE: We note that above, we have used specific initialization. However, in Appendix discuss how the lower bound is actually invariant to initialization.
C.I LOWER BOUND FOR F1, a E [nn=1 mL
We will work in v--dimensions (л is even) and represent a vector in the space as [21, ........Tn/a.. /n/22. These 2; and y are not related to the vectors used by F& and F3 later, only I, and y; make the proof for this part casier to understand.
We start off by defining the n component functions: For E [n/2], define
L
[( == 2nd F4 9
+
マ リ
and
1+1
L 2
(x)z) =
2 1/ y/ +
2
j
Thus, F(z): = (> / St +
= (اا))
| 7
This function has minimizer at z" 0.
19

---

Published as a conference paper at ICLR 2022
Let Z denote the j-th iteration in k-thh epoch. We initialize 21,0 O. For the majority of this proof, we will work inside a given epoch, so we will skip the subscript denoting the epoch. We denote the j-th iterate within the epoch 2j and the coordinates 2j 1 V5.1..... j,, Uj,n/2)
In the current epoch, let be the permutation of {fi..... / 2. 91 ...... ..... 9n/2) 2 used.
For any E [n/2], let and q be indices such that op - f and og = 9r- Let us consider the case that p q (the case when p q will be analogous). Then, can be seen that
In (1 -... ".T.)""lmm To,s + (1 - -a p0-p (1 a..)" aa and
Un, = (1 - (L-)))) -aa)"~11o yous - (1 - aa-aa) + - (1-aL) "a.
(11)
Hence,
Uo.s) + 2(1 aI.nn---aa In,i + Un. = (1 -.L' 2 (1
vo.,) + 2(1 aL)"-1aaLL
In the other case, when p > 9. will get the same inequality. Let and yK,,, n. denote the value of In and yn at the K-th epoch. Then, recalling that 2 was initialized to O, we use the inequality above to get
KK,,i + VK,ni 2 (1 - oI.) .0 +0 aL)" -02, 1 (1 aL)
1 (1 --
= 2 22(1-al) 221-- o²L 1- 1- aL) (011 1- (1 - aL)a-1
(12)
Since this inequality valid for all i, we get that
n/2
k 2
Σ
(o km + mik
nf2
(IK + +.K,..))
2
i=1
n/2
2(1 -abL" 1 - (1 aL) aL)(n-1)K 2
Σ
2
1 (1 al)n-t
1=1
=" =n(1- a1.)
022 11-11- - aL)
(13)
1 1 (1 aL)n-1
3 Note that if < ml and n 2 4, then (1 - aL)a-1 2 Using this in
13
we get
1 (1 (n-
| 2 (1 - aL) 2 2
1 (1 ab)n-1
1 (1 aL) (1-1)))1111))
a 2
128
1 - ab)a-1
(aL)²
(1- (1 aL)
12812
aL)
We consider cases:
(aL)²
1. Case A, al < 2 It can be verified that 1-(1-a2)~- is increasing function of
when aT < 2[n+2] Noting that we are working in the range when a 2 -n-1jK then
2
2
| 2
12 128L2
2(n
1jK
(1- (1 - aI)( 2
(1
n-1
1
20

---

Published as a conference paper at ICLR 2022
2
)²
2
1
2(n- 1jK
(1-(1-at)(0))
-ab-aab)--10 2
128T,2
(n -1]
2( IJK
72
1 1-(1aa))
512(n K2
512(n 1)AK2T2
1 - --1- 2
512(n 1)
Ω
122212
2. Case B, aL 2[m+2] In this case,
2 2(x+2)
|
n2
(1 (1- (1 - 1D))
128
T1
2(n+2)
-a)(n-1)K) 2
1
2
π2
2(n+2)
11 e 2(++2)
3(n-136 1)
128L
Ω
L2
C.2 LOWER BOUND FOR F2, a E IT. +
We will work in r-dimensions and represent a vector in the space as y = [yi....,. mnl.
We start off by defining the n component functions: For i E [n]. define
Ly²
f(ly) = Ui +
Σ 8#1
Thus, F(y) = 1 (= L |1
This function has minimizer at y = 0.
Let yk. denote y the j-th iteration in k-th epoch. We initialize at yı,0 O. For the majority of this proof, we will work inside a given epoch. We denote the j-th iterate within the epoch as y, and the coordinates as Yj [U....-..,
In the current epoch, let a be the permutation of (fi...., fu used. Let i be the index such that on i, that is, i is the last element of the permutation σ. Then at the end of the epoch,
Un, = (1 -
you + ((l-aL)--yyo. a Σ
aL-aLY aLY
5=
1- yo, + a (1 -
= a1-a
(14)
(n 1)L
For some j [r]], let be the integer such that a j. that is is the s-th element in the permutation σ. Then for any j and any epoch.
n-2 2
yn = (a-a))"- yo.s + a(l aL)==s
Σ
aL).
n
21

---

Published as a conference paper at ICLR 2022
Then,
n-
Vn.j 2 (1- --b)a~1 yo..
nt - Σ aLP
j=0
(1 - (1 aL)
=1 -1--ah a-) Yu.j
(n 1)
Note that the above is independent of 0, and hence applicable for all epochs. Applying it recursively and noting that we initialized y1,0 O, we get
vn.j 2 (1 (1 -aL)
K
Σ 11 - aL)
(n 1)L
2 (n 1)L
Note that yo.; is just Un,i from the previous epoch. Hence we can substitute the inequality above for Vo. in (1). Thus,
(1 aL) n-1
(1 (1 aL)n-1)
Un,
+a
(n
1)L
(n 1)
1
(n 1)L
3
1
nL
(n - 1)
Ω
nL
This gives us that || 1
for any k.
C.3 LOWER BOUND FOR F3, a & 12(n-1)KL 21
Consider the function F(z) = Σe fi(2), where fi(2) = L2² for all i. Note that the gradient of any function is just -2Lz. Hence, regardless of the permutation, we start the shuffling based gradient descent method at #1,0 = 1, we get that
K (1 2aL) nk 21.0 = (1 2nLL)n
In the case when a I 2(n I)KL' we see that
1
KK.n 2
1
-
2(n 1)KL L
nk
2 1
(n 1)K
((1),
for n. K 22 2. Finally, in the case when 2 1, we see that
2 = 2aIL
nK
nk
1
2
I
2 nn
2(1).
22

---

Published as a conference paper at ICLR 2022
C.4 DISCUSSION ABOUT INITIALIZATION
The lower bound partitions the step size in three ranges
In the step size ranges E 12a-1TkK nf. and E nT. H.I. the initializations are done at the minimizer and it is shown that any permutation-baseet algorithm will still move away from the minimizer. The choice of initializing at the minimizer was solely for the convenience of analysis and calculations, and the proof should work for any other initialization as well. Furthermore, the effect of initializing at any arbitrary (non-zero) point will decay exponen- tially fast with epochs anyway. To see how, note that every epoch can be treated as n steps of full gradient descent and some noise, and hence the full gradient descent part will essentially keep decreasing the effect of initialization exponentially, and what would be left with is the noise each epoch. Thus, was more convenient for us to just assume initialization at the minimizer and only focus on the noise in each epoch.
The step size range a & 12KK= > I. can be divided into two parts, o E [0, 2(n 1)KL
and a [ oo).
For the range a [0, 2(x-i)KL essentially show that the step size is too small to make any meaningful progress towards the minimizer. Hence, instead of initializing at initializing at any other arbitrary (non-zero) point will also give the same slow convergence rate.
For the range a E [ oo), we show that the optimization algorithm will fact diverge since the step size is too large. Hence, even here, any other arbitrary (non-zero) point of initialize will also give divergence.
D PROOF OF THEOREM
Define f1(x) , x and f2( == -4.2 x.. Thus, F(a,,) 4.2. This function has minimizer at x² = 0. For this proof, we will use the convention that Ji.j is the iterate after the i-th iteration of the j-th epoch. Further, the number in the superscript will be the scalar power. For
example oī = Ti.j Ii.j
Initialize F0,0 +. Then at epoch k. there are two possible permutations: (1, and o = (2, 1). In the first case a = 2), we get that after the first iteration of the epoch,
11,k Fo,k Vi ko,k)
(1 aL) + a.
Continuing on, in the second iteration, we get
F2, F1,k
a a V2 v1,
+ aL
21,k a
+ 2 aa
al
((1 - -aT))oo k + +a) -a
(1-aL)ao.t + 1
1+ (1+2 2 aL
22 LZL
Note that go,++1 = T2 Thus, Do = (1 jaT.) (1 - -aa) + 2
Similarly. for the other possible permutation, o = (2, 1). we get 20,4+1 = (1 + aaL) (1 (1-o a²L. Thus, regardless of what permutation we use, we get that
J0,6+1 2 1 - 1 jal) (1 (1-0))111 aL)zo, +
1 a - (1 aL)oo, + + a²
Hence, recalling that we initialized at 20,0 1. we get
Kn,K F0,K+1
23

---

Published as a conference paper at ICLR 2022
R-
1
(11 - aL)
+
L
Σ
- aL.
2
1=0
1
1
1- (1 a
7 al) K
+ a
2
1
al)
1
= L (1 - aL) k + 2a
(1 - (1 - aL) -1-ab) k)
(15)
Now, a 2 RT. then
1 a (1-
1
Ω
8
KL
and hence, -²² = 0 kmp
). Otherwise, if a S KT.
I
then continuing on from
15
1 (1 (1 =a
Kn,K 2 aL)*
2
(1 -a
L
aa.k
Le
Q(1/D);
and hence in this case, "², = 52( +
E PROOF OF THEOREM 4
Let ([(=)==]) == fz( be such that its minimizer it at the origin. This can be assumed without loss of generality because we can shift the coordinates appropriately, similar (Safran & Shamir 2019). Since the fi are convex quadratics, we can write them as fi(x) 1 A, b, æ + C where A; are symmetric, positive-semine semiefiiite matrices. We can omit the constants c because they do not affect the minimizer or the gradients. Because we assume that the minimizer of F(x:) is at the origin, we get that
b: 0.
(16)
Let (01, o2...., σn) be the random permutation of (1, the algorithm. Then for k E 21, K/2), epoch 2k 1 sees the n functions in the following sequence:
nn) generated at the beginning of
1 Aog b bT, x.... 2 Ao. x b x (~ Ao, x by x.
whereas epoch 2k sees the n functions in the reverse sequence:
T (~ Ao, x b,_ x. x Aon_, bJ xt.
Ao, x b
We define S; : aA, and t; ab,, for convenience of notation. We start off by computing the progress made during an even indexed epoch. Since the even epochs use the reverse permutation, we get
26+1 T
x=t
xit - a (Ao, 2² - by.)
(fo, is used at the last iteration of even epochs.)
=(I -a 2.2k
ab
24

---

Published as a conference paper at ICLR 2022
-I (1)=))a + t
We recursively apply the same procedure as above to the whole epoch get the following
2k+1
(I S1) )= t
20
(I 51) (1I 52)=m 12) + tı
- Si) -22) 2k + (I S1) + t1
n-ド
S.)
2h
+
II S/)
entl-i-
(17)
where the product of matrices {M,} is defined as I otherwise. Similar to Eq. (17), we can compute the progress made during odd indexed epoch. Recall that the only difference will be that the odd indexed epochs see the permutations in the order (01, ,2, .n) instead of (o,, On-1y-..;01) After doing the computation, get the following equation:
M, = M...- M if m 2 / and 1
2h T
II Sn-141)
2k 20
+
- Sn-st))) t.
Combining the results above, we can get the total progress made after the pair of epoch 21: 1 and 2k:
2k++ 40
II
S:)
20
24
Σ
II [I - Sj)
tntl-i
1=1
1=1
j=1
II (I - s.)
II Sn-1+1)
2
2k-1 +
II
((I-S)) S₁)
Σ
II j=1
Sn+1-1)
1=1
1
n-
int1-i-
(18)
In the sum above, the first term will have an exponential decay, hence we need to control the next two terms. We denote the sum of the terms z (see the definition below) and we will control its norm later in this proof.
-I))
Σ
Satl-s)
t,
[I -s))
txt1-i
1=1
Σ
(I- - S₁)
II
S
Sp+1-1)
4, +
[I - SJ)
fo+1-b
i=1
To see where the iterates end up after K epochs, simply 2k applying the equation recursively to preceding epochs. Then, we get
K in Eq.
18 and then keep
12 [[ Si)
KKK
K+1
[[ Sn-stt)
an
K-1 +=+
+
1=1
(iiu-si) 5.))
[[ [T- S
K-3
S:)
[ i=1
n1
S Sn-iti) +
25

---

Published as a conference paper at ICLR 2022
(Lij s.)
)
Sn
K/2
z
+
[Ii 5.)
(iiu
S Sn-s11) 2.
A=
Taking squared norms and expectations on both sides, we get
K/2
2 E
a (N s.) II Sw-t1))
E||
||
$
[[(
si) -s)
[Iu S--11)
+
k=
( (1 -s)) (iiur S Sm-tti)
K/2
< 2E
2/
Σ [ S.)
-s)) s.)
1
II
Sa Sn-i41) ))
+ 2E
k=
i=1
(Since (a + b)2 < 2a² + 21²))
m (I (1i
[Niu [ S.
K/2
$ 2E
x
|| $ Σ
27
1 SD II Sn-141)
+ 2E
II
We assumed that the functions fo have L-Lipschitz gradients (Assumption 2}. This translates to A; having maximum eigenvalue less than L. Hence, if a 1/L, we get that I aA, is positive semi-definite with maximum eigenvalue bounded by 1. Hence, || - S < 1. Using this and the fact that for matrices M1 and M2, [|M, M2 & |M |II M2]|,
we get that
27 n
n (i
si)
[ S 5mm11)))
12
K/2
< 2E
z
K-1 Σ
A
n
R S
2
|||||
I S.
Sn-itall
K=
1/2
$
27
12 [I
< 2E
[[ -s)
si)
- Sn ([IT-S,-(H)))
+ 2
||
Σ |1
1=1
(iiu S.)
12 I Sn ((U--S-mm))
1//2
1
K²
2E
x/
+ E
[||=||3
We handle the two terms above separately. For the first term, have the following bound:
Lemma 3. a < BAI min
2, /
then
n
[
SD) II
S Sn-1t1)
$ 21-anj
1=1
26

---

Published as a conference paper at ICLR 2022
Note that K 2 80x (og(K)) max {1, y/t
a
SKL min {2, v/e n
J.
We also have the following lemma that bounds the expected squared norm of Lemma 4. If S t. then
= + a log n,
where G = max; b,]|, and the expectation is taken over the randomness of 2.
Using these lemmas, we get that
|| K 2 s 2 naje)
K/2 |00||
L2 +8KK - log
s 2e koak
|= a 85 L log n.
Substituting a = 10 log nK pnk
gives us the result.
E. PROOF OF LEMMA
We define (S1...., S.) = (Si, ........: S,) and (Sa+1,.... ) .S...... St). Then,
n
n S.) II Sn Sn-it1)
2n
II
5.)
2n
1
5, + Σ
S
icj
2n
I
S + Σ S
+ Σ
S,S,S,
Kjj
2n
<
I Σ S + Σ
S,S,
Σ
5.
S
S
1=1
<CjK
Note that
S.S, =2 -
2 S.S, +
Σ S?
KJ
itj
1=1
n
n
n
= Σ S
Σ S
Σ
Sp.
Substituting this and noting that E S, = 2 Σ
S, we get
- "
-
[ S.) I S, sp-+1)
<
1 2
S, +
Σ S
Σ
S:
1=1
1=1
1=1
1=1
|5 5
S
+ +...
Kick
5
n
S, 2
Σ s
n
Σ
n
ss
$
Σ Kojc
3
5,
3
+....
27

---

Published as a conference paper at ICLR 2022
Let denote T := Ei=1 S,. Then, know by Assumptions 2 and 3 that T has eigenvalues in [nap) Then, as long In
get that
n I-2 _ ==1
n
S
+2
Σs; S:
Σ i=1
S
= || 2T + 2T
i=1
nap.
Substituting this, we get
Sm- $ 1111(19)) nay
n +
II S.)
I S.
Σ s i=1
Σ
S
5
5
By Assumption 2 we know that ||::|| < L. Hence,
|S S ab. Hence,
3
nna2 ((z))
(2n)
II S.) II I S i+1))
5
mapi
a 1,,
{4)
a 2 +...)
3
2n
<
1
naH + na² + Σ (2naL)'
2
3
8n L
$ 1
maji + na 2 L2 + 1 2nal
2
3
S 1 maji + na 2 + 16n L3
(Since a S 1/4nL.)
2
Finally, as long as S TsI and 8nt.y/
n
II
5,)
II (I Sn 8n-141)
$ naj.
i=1
E.2 PROOF OF LEMMA 4
We start off by computing the first order expansion of We have the following lemma for this:
Lemma 5.
2n-j
Stt+ Σ II 5p)
S
Σ
Sp)
SiS,
Σ
Etuti-s)
l=1
where (Si..... 5..) = (Si.... S.) and (Sut1..... S2n) = (S.. ........ S1).
The proof of this lemma quite algebraic and hence has been pushed to the end, Appendix E.4
The strategy is to bound S 2n-5 &dll. and E En+1-il/. Hence, we apply Lemma and use triangle inequality:
2n-1
E
|21
=E
Σ
Stt, +
Σ
II Sp)
S
Σ
t
j=n+1 k=l
p=1
II Sp))
SiS;
Σ bn+1 1
2n-1
2n ||8/1115|1
E
Σ
||
Σ
I 5pll
Σ
||tall
j=m+1 1=1
p=1
28

---

Published as a conference paper at ICLR 2022
ΣE
I Spll)
|||||||;||||
Σ
|1=+-=s||
Now, we recall that ||S S aT. and ||+a]| Using these,
S oG. Because S 1/I, we also get that | S: s 1.
2n-1
2n
B =||+[|*
E E
Σ
LG Σ
aLab
1
j=n+1
i=1
p=l
1=1
27
aLaL
Σ
t
1=1
1)
27
2n-1
j2n-j
n- 1
12
$ E
no na + L² 1
Σ
Σ t;
+ na 2 L
Σ
t ++1--
jmn+1
2n
2n-j
1)
27
LLE
G+2L
Σ
t
+ L
Σ
j=n+1
2n-j
S 2n 2naa"
+LE
Σ
Σ
in+1-1
j=n+1
i=1
(Since (a + 6) < 2a + 2b²)
Using Hoeffding-Seriie inequality for bounded random vectors (Shhneider 2016 Theorem 2), we get the following lemma
Lemma 6. For all j, E [1,m] have that
E
t
S 2 log(n)
1=1
E
< (C*)
where G = max; bi]], and the expectation is taken over the randommess of t,.
Writing out the expansion of 2 ( s=n+1 ΣinT' lemma above on the individual terms, we get
2n-5 6: + ΣØ= E t tmt1--)) |))
and using the
E [|=1|]]
< 2n T.22
2n
E.3 PROOF OF LEMMA
This proof similar to the one Ahn et al. 2020). Define G == max; |bl]. We use the following theorem adapted to our setting
Theorem 7. Schnnider
2016
Theorem 2)] With probability at least 1 5 n
j
t:
S aG"
v 8j (1 1- j j-1
(1- n
log 2n 5
29

---

Published as a conference paper at ICLR 2022
Then taking union bound over j = 1, .,...: get that with probability at least 8,
j aG
2n log
2n 88
vj E [1,
Σ
t
V
8j
S aG
n
5
Then, for the complementary event (which happens with probability 8), we use the fact that ||&:]] |abb, S aG get the following:
Vj e [
|&,ll S aG'j.
Now, choose 1/n. Then, we get that
< - [ 8ja 2 (og((n2)) - (aG")) j)²
t
12
I 18ja" (G*)² logn.
Similarly, we can also get
Σ t Σ t
I 18 log(n).
E.4 PROOF OF LEMMA 5
As in the lemma's statement, define (S,...., 22n) as (SI...,, (Si...., S,) and
(Sath,..., S2n) = (Sn,..... S1). As reminder, the term z defined as follows:
n
= I )₁)
II
S-+1-s)
Σ 4: + i=1
- Sj) luti-s
(19)
First, we analyze the first term in z. [[= -s)) [I Snt1-s)):
Towards that end, we start by expanding
12
n-i II Sat1-;)
2n
[[ ( 5,)) (s) j=1
II (I-5))
(20)
2n-i-1
II (I-5,) j=1
(1- 52n-1)
2n-i-1
22n-i11
II (I (I-S,)
II (I (I- $2n-i.
j=1
(II3-- (I (5) and then recursively keep doing it to get the
Similarly, we expand the term following:
2n-i-1
2m
|I [I 5,)
II
Sut1-s) =
II (I (55)
II (I 5y)
(I-
Szm-
j=l
==1
j=1
2n 2n-
2n-
22--i11
II (I 5
(I -S,)
(.))
S2n-1-1-
II (I 3,) 3
==1
/=1
Ø=1
30

---

Published as a conference paper at ICLR 2022
-1 (I-S,)S.
2n-i-2
2n-i-1
II (I (3) j=1
5j)
S2n-i-1-
II (I (I)5)) 82n-i
2n-1
(j-1
II 51) 33.
I
Note that the term II - 3)) above is similar to the RHS of Eq. (20). process again on this term to get the following
Hence, we repeat the
n-i [ Sutl-s) -
2n i
II -s))
8,)
=
I
[I 5,)
St 8,
i=1
2n-i
2n
Sj
(I -sp)
S.S,- (21)
/=1
Using this in the first term Ei=1 (II- - (1-))
(II - Sn+1-;)
tinin Eq. 19 ). we get
n
2n-i
II II (s)
)
II Sn+1-s)
4= = Σ
I
Σ
S
+ ΣΣ
Sp)
SiS
t;
j=l
J=1
n
2n-
2n
2n-ij=l
[1-1
t
Stt,
+
Σ
[I Sp)
5,
i=1
j=1
j=l
1=1
Now, we use the fact that
Σ b, 0 (Eq. 16
to get that Σ t; 0. Then,
2n-1
- 5,))
II Sn+1-;)
t= Σ
Syt, ΣΣΣ
(1-5p)
[I 5p)
S,S,t.
p=1
For convenience, we define M, = E [1 1- (I 5,)) SyS,. Then,
n
n II 5,)
n-1 II Sn+1-;)
12 2n
2n-í M,te
t, Σ
Stt +
2n
n n ΣΣ
2n
5y4 +
M,r Σ
Σ
M,t,
j=1
1=1 /=
1=1 j=
2n-j
2n-i
Σ Σ
Sy4
Σ M
Σ
Σ
M₁t
i=1 jint1
2n-1
2n- Σ Σ
Σ Σ
Syt +
M,t.
(Since Σ t, = 0)
1-1
(=1 1=
Note that Σn= 2n -==
M,t,- = Ejantz M,
2 t,
Hence,
n-
t= Σ 2n-
2n-1 Σ
2n
[I
[I [I Sm+1-1)
Syt, +
M,
t
/=1
1=1 1=1
-=
1=1
31

---

Published as a conference paper at ICLR 2022
2n
2n-1
2n
55t
Syt +
Σ
Mj
Σ
t
1=
1=
j=n+1
j=++1
1=1
2n--
2n-1
2n
Σ 5
4
Σ
t1
+
Σ
Mj
Σ
ti
1=1
1=1
1=
1=n+1
j=++1
2n-
2n-1
2n
Σ
Σ
5 +
Σ
Mj
Σ
ti
(Since >x b = 0)
1+
j=++1
i=1
2n-1
1-1 (I
2n f
5
+
Σ
Sp)
Σ t
j=++1
p=1
2n J
Syt +
Σ
E
3p)
S,S,
Σ
(22)
jin+
I=1
Next we analyze the second term in z. For this, we start by expanding [] (I - SS)) in similar way as Eq. 21
R-i -I- S,) -1)---1--11
n-i
R-ij-1
S
II Sp)
S,S,
(23)
1=1
j=1== 1=1
p=1
Using this, we get
n-
1-1
[I - Sn)
t 1nt1-s=
=
Σ
I
S +
II - Sp)
SIS, tn-
1=1
1=1
1=1
Ap=
n-ij-1
S n --1
ΣΣΣ
II Sp) S,S,,nti-i
i=1
j=1
=1j=1
n-ij-1
(-1
S t +1
ΣΣΣ
II 5p)
S,S,tutiii
1=1
p=1
where we used the fact that Σn t 0 in the last equality. For convenience, we define M,
Σ
(I
S,S,. Then.
n-4 II -I,)
n-3
n-t
Σ i=l
4nt1-;=-
S₁ Stttti
+ Σ Σ
M,t
1=1 j=l
Since Σ nーー
EE Mj
En b
we get
n n=i
n n-i tut1-1=- Σ
n-1 1
n-j
II [I
5i) (})
1tt+t1it+
Σ
M2
Σ
tn+l-i 1-
j=l
i=1
n-1 s₁4 + Σ
M
bn+i-i
1=1
R-1 Stt + Σ M,
ΣΣ
tnt1-s
/=1
a i
カー
n-j
ΣΣ
St4 +
ΣΣ
II [I Sp)
SiS,
Σ tntl-1
1=
(24)
32

---

Published as a conference paper at ICLR 2022
Finally, substituting Eq.
22
and (24)
in the definition of (Eq.
19 ),
get
n
Sy4
2n
Σ
[-1
II (11)),)
3,) S
2n-j
Σ 4
j=++1
I-1 sp))
n=j
5,4
ΣΣ
Sp)) S,S,
Σ
ba+i-i
1
/=1
p=1
Σ 5 + Σ
S
t
j=++1
2n-j
n-
(I -sp)
S
Σ ti
+ +Σ
I Sp))
S.S
Σ
bn+l-i
j=+
[=
p=
1=1
i=
n
n
S
1 +
Σ
S,t,
2n-1
1-1
2n-
n- 3
Σ
5p)
5
Σ t,
+ +ΣΣ
[ sp) SiS, Σ
tntl-i
1 -=
1=1
1=1
1=1
Σ
S
4 +
Σ
Stt.
2n-1
2n-
n-
Sp)
5
Σ t
+ ΣΣ
sp)
SiS,
Σ
butl-i
j=1
2n-1
2n-
m-1j-1
n-
Σ S,t.
Σ
Sp)
S
Σ
t
ΣΣ
-Ip)))
[I Sp)
SiS
Σ bnti-e
where we used the fact that E t = 0 in the last equality.
F PROOF OF THEOREM 5
The proof is similar to that of Theorem except for that here we leverage the independence of random permutations in every other epoch. The setup is also the same as Theorem but explain it again here nevertheless, for the completeness of this proof.
Let F(x) = = ((r)) be such that its minimizer it the origin. This can be assumed without loss of generality because we can shift the coordinates appropriately, similar to (Safran & Shamir 2019). Since the fa are convex quadratics, we can write them as fi(z) f A, b, x c, where A; are symmetric, do affect the minimizer or the gradients. Because we assume that the minimizer of F(x:) the origin, we get that
matrices. We can omit the constants c; because they
by O.
(25)
Let 0² (oft oottob.. oi..... ... at) be the random permutation of 21, .n) sampled in epoch 2 1. Then epoch 2h sees the n functions in the reverse sequence:
........n)
A
2
1
A,
-b b,
2
Agg
bJ x.
2
1
x
Ag bJ:00
whereas epoch 2k sees the n functions in the reverse sequence:
{ x
1 x.
A
TT x. D A
T.
A
A
b
2
2
2
33

---

Published as a conference paper at ICLR 2022
We define S := a and t = abot for convenience of notation. We start off by computing the progress made duting even indexed epoch. Since the even epochs use the reverse permutation of o², we get
xn
In
-
[ A bat
(fot used at the last iteration of epoch 2k.)
I -1-04 aA In xn +
abot
(I - S )a; + e
We recursively apply the same procedure as above to the whole epoch get the following
2 2k+1
(1- S ) t
= (I - S (11 S2 x + +t/ + t
= (I - ST)(I- 2 + -I- S1)t t
II 5
2k 2
+
II 1=1
t t
(26)
where the product of matrices } is defined as IT M. = M.MI-I..- Mm if m 2 I and 1 otherwise. Similar to Eq. (26), we can compute the progress made during an odd indexed epoch. Recall that the only difference will be that the odd indexed epochs see the permutations in the order (at, . .h) equation:
-=
instead of (ah, o off After doing the computation, we get the following
12
[I
S
-
2k-1 x
+
Σ
I I
Sk -h-s+1)
t
1=1
Combining the results above, we can get the total progress made after the pair of epoch 2 1 and 2k:
a-i
2 2
II
II
(3)
tth
thtt-1
j=1
II [ s
[I
s
an -
(I
Σ
II j=1
[
s
-
+ Σ i=1
[I
5
th
(27)
In the sum above, the first term will have an exponential decay, hence we need to control the next two terms. Similar to Theorem 4
we denote the sum of the terms as zt:
7 II (I- 8T) 1=1
Σ
II
s
II
St))
J=1
/=1
n Σ [
s/)
I[ st
t
[I
th
--
To see where the iterates end up after K epochs, we simply set 2k = in Eq. 27 and then keep applying the equation recursively to preceding epochs. Then, get
K n = x
K+1
[1
5
[ 5
x
K
+ 2
34

---

Published as a conference paper at ICLR 2022
n
s , )
[
2
5
S
s
11
[I
s
a-1+1)
2 +
n
8-
-
-
S (--11) )) ab
II
II
s s
[[
S mii+1) )) 2 2
Taking squared norms and expectations on both sides, we get
n
) a
x
K ||
E
II s
II
s -k
S
I s -)
n II
S vx
2 2$
k=
1=0
2E
-1
11
12
k - -
n
S
x
[==
II (1 - s $
n
+ 2E
K -1 - S
x -k
(28)
k=
1=0
{==
where we used the fact that (a + 1122 < 2a + 212. Next, we expand the second term above to get
B[| || < 2E
- s , )
-k - (1-111)
S
x
K-1
+ 2
Σ
E
II (I- s s..1) 1)
[I
S -1
S
s
K -k
k=0
1=0
iill
k-1 II - s/=T))
n
+4
Σ
E
S -1
OSk
# -1
1m0
II
s s
)
-1 |I I---st
S
2 $
im
We
handle
each of the three
terms separately.
Let
N
The first term can be written as: [T (I S ))) (IT (I - S -+
))
|| [ s 5
[[
K - S
E
s
=
E
N
k=0
35

---

Published as a conference paper at ICLR 2022
3- -1
K
-1
(
II A=
N
N
4 II N
E
(o))
II
NE
NO
No
k=1
-1
E
(x)) T
π No
E
N
Z0
where, in the last line, used the fact that the permutations in every epoch independent of the permutations in other epochs, Next, we have the following lemma that bounds the spectral norm of [N No for any & [0, K
2 1]:
Lemma 7, For any S a S 3 min 1,
16n
||
Noll 1 ony
Note that 2 lox max {1, Using it, we get
E x
a S
3 16nL min }. and thus this lemma.
K
II
n
S s
n II
S -
s
4-1
$ II N
E (ar)) T
II No
E
N No.
k=1
-1
$-1 II
< (1 nap)
(xb)
N
N
k=1
T
E -1 II N
4/4 4-1 II km
(1 n
(Z!))
E
E N1
N
k=
< (1 nap) K/2 22)
(30)
Next we look at the second term in Ineq. 29
E
R
-
5
II
[I-
s )
$
2
n 112 1p)
< EE
|
S # -1(p)
I
S x -1
|| 1112
1=0
< E
where the last step we used that |
S < 1 for all i, k. To see why this is true, recall that
Sth = ..At. Further by Assumption 2 A || < L and hence as long as a S 1/L, we have that
I St 1
36

---

Published as a conference paper at ICLR 2022
Next, note that for any ls apply Lemma 4 on the second term:
||||= $ ->1] Hence, get the following bound
K
n1 II
s. s
[I s (
2
E
i=1
K (2n a L + 170n a (
= 2
(31)
Finally, we focus on the third term in Ineq. bound for it:
We have the following lemma that gives an upper
Lemma 8. Let a S. ZnT. and n > 6. Then for 0 < < k S K 1
k-1
I s
S $
x
(1-tt))
)
II
- S + II - S # ( -
x x
|
1000m a T. + 2000m 6 (G*) log n.
Using Lemma 8 and inequalities
30 and
in Ineq.
we get
E =||
||2 < 2(1 - naau 1/2 1/0|!= + 2n Ka LL (G + 170m" Ka (("")" logn
+ 1000n x2 0. (G')² 2000n 6 K 1. (.
$ 2(1 nap) K/2 | 1002n2 Ka L (G+) 2170n K2 a (G*)² logn.
Substituting
10 nk pnk
gives the desired result.
F.1 PROOF OF LEMMA 7
Recall that we have defined N₂ = [T (I -I- ,) (IT=
- S +
Hence,
T
N
[I s -
II-
-ー
n-1+1
S
n I
S 4
# - n-it1
S
K
[[
n2
k S
No.
where we used the fact that S K
are symmetric. Hence N₂ is symmetric. Then,
I N&lll max E[x" N Nıæ]
max E NgNgx..
2: Ø
Next, note that || < 1 as long as S n.. This combined with the fact that N₂ is symmetric
gives that x N₂ I T Nax. Hence, get
N Ng]l S max E[x= T Ngæ ==||=||=1
37

---

Published as a conference paper at ICLR 2022
|
E
II
S
")
II
S
k n-
E
S K
II
S
To complete the proof, we apply the following lemma from Ahn et al. 2020
Lemma 9 (Lemma 6, Ahn et al. (2020)). For any 0 S S
3 16nz.
min (1, i and & E [K].
n Ma S " +) "
2 II [ S
E
< amp.
To avoid confusion, remark here that, the term 'Sy' in the paper Ahn et al. (2020) is the same as the term '[ S in our paper, and hence the original lemma statement in their paper looks different from what is wrilten above.
Remark 2.
F.2 PROOF OF LEMMA
We begin by decomposing the product into product of independent terms, similar proof of Lemma 8 in [Ahn et al.] (2020). However, after that we diverge from their proof since we use FLIPFI.OP specific analysis.
E
II -
[I
-1 s n
24
1=0
k'-1
II
s )
[I
-1
2/
1=
x
k++
II - s
n
# -1 S
S K
n
K
[[
S 1
[[ -
S $-1
))
2 -K
Since k we get that (x T
k+ (IT= (I-S )) (II
s ) and
II I
s )) I - )
- s
II
n I - s [i s
-1
))
are independent. Hence, we can write the expectation as product of expectations:
II I s s.t))) II r -
S -
K-
E
S *11)
# [ [I-
) z
[I
n-++1)
38

---

Published as a conference paper at ICLR 2022
E
2
E
II
s s 1)
s (
II - - s
n
n [[u-- S ([(u-shini)
E
II 1=0
W-1
n II I[ )
n - (
x -k'
Applying the Cauchy-Schwarz Schwarz inequality on the decomposition above, we get
I [T s )
S $ [iuu-s
n
E
1=0
II (I - S K s/2(41)) ))
s s
2 x3-1))
II s
II - (
E
E
- )
n I (
x
E
s , )
k
[I
--++1)
S ||
n
-1
E
E
n-++1l
s 2
n
-1
E
n
R-1
s s
n
-
k
x
12
II (I- - [1--s,55)
[
12
S s
E
1=0
II 1=0
II
s s/5-1) [ - S
k
x -K'
where in the last step we used that
St = a AAA.. Further by Assumption 2 || || || S L and hence as long as S 1/L, we have S |I-
< 1 for all i, k. To see why this is true, recall that
- S | 1
For the two terms in the product above, we have the following lemma:
Lemma 10. If n > 6 and S nt. then
||B|2 x -1]l < 28 I.G + "0011'' /2n 222logn. n.
39

---

Published as a conference paper at ICLR 2022
Lemma 11. If > 6 and I 2nl. then
s
1 [
S )
E
II
1=0
II
I
s $
II
n
S --
s ))
K -kk
I 32na LG + 24a L'n G 2n logn.
Finally, using these lemma get
1-1
II
sT-)))
[I
S
3 -1
#
n-i+1)
1=0
k --1
S 3
II S -1
2 2
n-i+1
(28na) LG 90. 3 L'' GO /2nlog
32maa 2 LG" + I. G 22n log
896n2 2 (TT 960g T,2n (
2n log 432o. "0 1 (G*) log
10000' 10 2000a 200002L5p000 ( logn.
F.3 PROOF OF LEMMA 10
Since we are dealing with just a single epoch, we will skip the superscript. Using Lemma 5
we get
2n
Σ
2n
E
E
E
S
+
(I
5p)
S,S,
Σ
ti
1=1
1=1
1-1
n-j
E
II sp))
S,S,
Σ intl-i
p=
2n-1
2n
B
+
E
-Sp)
Sp)
S.S,
Σ
t
j=++l
ΣΣ H
E
(I (I-)) Sp)
S Σ tutt-i
(32)
Define G := max; |.|l. Then |||||||||||| = || |b
o || S a² LG and hence
Σ
S | < n LG
(33)
Next we bound the other two terms. Using Eq.
23 we get that for any 1 < j.
n j
Σ EmLL))
I Sp)
S,S,
1-1
1-p-11
9--1
nn-j
E
1
Sp
II [I
Sa)
S.Sp
S,S,
Σ
tn+1-s
p=1
(=1
40

---

Published as a conference paper at ICLR 2022
1-1
- E
Σ
S,S,S,
Σ (nti-))
p=1
7-1p-1
g-1
+
Sq)
S,S,S.S,
Σ tntz-i
1-1p-1
q-1
カーj
Σ Cill
E
Σ
ΣΣ
E
II 5q))
S,S,S.S,
Σ Bmtzzn))
pelicii
p= q=1
= Σ
E
Σ
S S
Sii
peluci
1-1p-1
g-1
n-j
Σ (mati-))
E
- S.)) S,S,
p= g=1
Since E -= 4 = 0, and we use uniform random permutations, |tt/ S,] = Etitta 4
lift/
- n-2
Similarly, St, SJ. = n-3 - Hence,
B
II Sp) S Σ bn
B [S Sylll
Σ
I SS, splll
p<lji<i
E
I - sall)
S
Σ
||0 tyll
+ t, + tp n- 3
|||||||||||
Σ
||S|||||||||
T1
peljei
s.ll
||5. ||S||||,,1|||||||| |||S||II,
Σ
m=1 q=1
2n
3 LL'G"
3n²
L3 + a ΣΣΣ
E
n-2 2
2(n - 3)
q=1
(Since
|| S aL, ||t/||
S aG (34)
< L30 + 3 + L 188 log
where we used Lemma and the assumption that 6 in the last step.
The third term in Ineq. (32 can be handled similarly. For any j,
2n-jj
II
3,)
S
t
2n-j
E
I
Σ
Sp
5.))
S.S,
S
Σ ti
p=1
2n-j
[-1 2n-
2n
E S,S,t,
Σ E S, +
5y))
S,S,5
Σ
ti
Now, is easy to see that + j and * 2n - j 1. Then, if = I or i = 2n - -+ we
use for that case the fact that || < a L2 For all other i, we can again use that -4- ifl 5 E,, SS, S,] -22-1411 -1, otherwise. Similarly, we can bound n-
Ett. Sy]
41

---

Published as a conference paper at ICLR 2022
E S, t. ||- Proceeding in a way similar to how we derived Ineq. (34), we get
2n j
E
[I 5p)
S,S,
Σ
t;
i=1
2n-j
[-1 2n-
<
E
5 ||
+
Σ Σ
E
S,
p
i=1
2n-j
ΣΣ
E
[ S,))
S.S,SiS,
Σ
4
11
i=1
2n
3n2
S L +
a
L²
na L3
a
L
2
2(n 3)
9-1
2n-j
ΣΣ
E
3.))
3,3,5,5,
Σ
t
plg
5a LL 5
ΣΣ
9-1
E
-
||S- ||I 3
Flg
< 5 L
5na L L V18n
(35)
Substituting Ineq. 33
and 35 into
We get
||[|]||| < na LG + 10n a L'G + 10n a LL + 2a L'n V ISn
4n² a G + 3 L + a² LL G /18nlogg
28na LG" LG
9a L n G 2n logn,
where we used the assumption that nl in the last step.
F.4 PROOF OF LEMMA
Define the matrix M as
M
W-11 n II S
II
I1
s
4-1 )
II
II s s
n
s -- (Hlu-s
))
Since M is independent of [T 5.¹ ) tower rule, we get
[
s -K' s
and 4 using the
T
E
II
(I
s s )
[[ -
a
s
S K -
1-
I[ 5/-1))
n
[I
s s )
1=0
I - S k -K' t - 1)
n
=E
S
k
E|M] -V'
We will now drop the superscript K k for convenience. Hence, we need to control the following term:
( s.))
[[ - smntti))
12
E
E[M]z
i=1
42

---

Published as a conference paper at ICLR 2022
We define (5...... S2n) (Si,..., S.) (Si,...,,,, S,)) and (S.+1,.... .2n) (S Then, we use Eq. (2T) to get
n
II Smmtt1)) 1)
2n
1 - S.))
= II
(I
S.)
i=1
2n j-1
I
5J +
II 5,) 8,S,.
j=1
j=l I=1
Ap=
Note that I
مy=1 Sy is constant matrix. Since SJ aAo,, have that ||S||| S al by
2m
Assumption
Hence, S 2nl then ||
-= Sill < 1. Further, or S 1/L implies that - Σド
2n
|| - S, S which implies |M| S 1. Hence.
II I - smmren)) E/M
E
5.)
T
2n
<
E
Σ ==1
S
E[M]z
T
2n j-1
1-1
+
E
[I 5,)
8,5,
E|M| N
j=1
Ap=1
T
2
2n j Σ
I Σ
S
E [z]
E
+ E
II
3p)
3,5,
E|M z
1=1
j=1
y=1
+
E
ΣΣ
II
-pp)
5,5,
E =
Ap=1
We can apply Lemma 10 to bound
| [=]]] So, we focus on the other term. Using Lemma
2n j-1
[I - 5,))
5,5,
E|M]z
2n j
Σ
3p)
5,5,
B[M]
Sttt
T
2n j-1
2n
2n
Σ
(I 3,))
-5,)
5,5,
E[M]
Σ
5,)
S.S,
Σ ti
p=1
j=ntl
1=1
p=1
E
Σ
-5p)
Sp))
5
EIM
ΣΣ
s,)) Sis, Σ
bntl-i
E
5p)
S.S,
E|M
Σ S.t.
2n j-1 1
2n-1
4 (I 5,)
2n
E
[ 5,)
S.S,
E[M
Σ
S.S,
Σ ti
1=1
1=
j=n+1 t=l
p=1
1=1
43

---

Published as a conference paper at ICLR 2022
T
2n j
11-
--11-1
1-1
n-j
-p)
5p)
8.5,
B|M
Σ
[I 5,)) Sis, Σ in+1-i
/=l
1=1
E
Sp
||S|
BIIM
Σ
S,t:
2n-1
2n |5111|5911
Σ to 1)
E
I Spll
||||||||||||
E [|]
Σ
I 5pll
Σ b 1)]
R
I Spll
||S11|||)
|||
ΣΣ
I - spll
||S/|||||||
p=1
Now, we use that |M
S 1, I|
8.11 11 1 S S aL and ||
S at:
2n
I
(I (1-))) 5p)
S.S,
E[M]
p=1
2n-
S a L + Ln
Σ
anaa+ L
Σ bn+1-
Using Lemma
we get
2n ΣΣ
E
-p)
S/š,
E|M|
<4na
15n'aaL'G" 2 n.
p==
Putting everything together,
E
II -Ia
5b-1)
-
II
s サ-1
n-1+1)
1=0
A==
π
II s b) i=1
II S k
$ -K
n-
i=1
(28na² LG + 9a $ I." / 2n log
+ 15ntt logn)
< 32na" LG + 24a $ 4 n G / 2n logn.
G PROOF OF THEOREM
Proof. We start off by defining the error term
n p Σ (x
T1 fi (o
))+
n V -+1 111 (xtt.)
Σ
Σ v fn-it1 (x) (x22-11)
where l E K//2] This captures the difference between true gradients that the algorithms observes, and the gradients that full step of gradient descent would have seen.
For two consecutive epochs of FLIPFLOP WITH INCREMENTAL GD, we have the following inequality
||22 x= =11==
0 24-1 x 2
2a
I
2k-1
x²
x 2k-1 +
Vfn-it1 (x?-1)
44

---

Published as a conference paper at ICLR 2022
a²
Σ
Vi 22-1 + Σ V fn In (27=1)
2k-1
x" x²12² 2a (20 2k-1 xx= V (30 2(--11) -)
= 40
2a (a
21-1 x;, r*)
+ a²2 |2 F( (2n 3 1) + rl
< || 2
26-1
x=1 1|2 4n
T,ps
2k-1
x x²1 + L+ p
1
VF (x) 2k ( 1) |1²
L + /
2a ( (
21-1 x², r
+ 2² 122 2h
(x
10 1 + r²1
1 || x
26-1 1 x x²11² 4na
T,p
2k-1 x²12 +
1
VF (x) 2k 1)12 )1²
L + /
L+ /
2a ( a
22-1 xx, rr²)
+ 88 2
V Fx
2k
")|2²220 2a 2 aaa2|111 ||
+
4na
T,ps
||00
2h-2-1 x 11?
[4na
1
sa?n²
| 2k 2
||
L + F1
L +
2a
( 1
x
xk
+ +aa 2 ||>"||??
(36)
where the first inequality is due to Theorem 2.1.11 in Nesterov (2044) and the second one is simply
(a + 6)2 v 2a² + 26².
What remains to be done is to bound the two terms with rK dependence. Firstly, we give a bound on the norm of rk:
n
f (x
Σ
Vi
(a (2)--1)
+
Σ V Sn i+1 24
n
V fn-it+1 (ag 2
1=1
72
f
f.
(
||| +
Σ Winee (m?²
Vfn-it1 (z (2)
Next, we will use the smoothness assumption and bounded gradients property (Lemma)
n
11
||^*|| S L
2
2k
24
L
2
2k
x
2k-1
-1
< LGa
i + LGa Σ
(n 1 i)
i=1
= n(n I)aGL.
Hence,
||a < 4n 2222
(37)
For the n term, we need a more careful bound. Since the Hessian is constant for quadratic functions, we use H, to denote the Hessian matrix of function fe(-). We start off by using the definition of rk:
g.k n
f (z 24 Σ
fo (x) 2k 1
V In-i+1 (2
V
fn-i+1 (2) 1
[.): (o ( 1 Vi (2 2k 1)) +
(iiiii (w
V Win-iti (2z
= Σ H (1 1=1
2k
2 2k-1)
H
(x221 an =)
where used the fact that for quadratic function f with Hessian H. we have that -f(x)-V()) H (x y)- After that, we express a; 2k-1
an 2k-1 and an x 2k-1 sum of gradient descent
45

---

Published as a conference paper at ICLR 2022
steps:
+ +Σ n
r
Σ H
VV V --1)
a
#1
aV (x
2k-
fr j+1 (x)
==1
i=1
H
Σ
H n i11
V fn Jn --ا
1=1
Σ (
H i1
1=1
= 0
H
V T5
- a Σ
Ha-in iitl
Σ V fn fn-j+1(2 )
i=1
1
a
Hn
Σ (f
1=1
n
a
H
( - 11(
1
(0- - V ((n-)t((0)))
Hn-i+1
n
Σ (1 -
H n- 11
1=1
V (f 1) +a Σ
22
H
H. V V f((2a*11)
i=1
:=1
H
V (-m)) - f5(2/h-1)
1=1
V (n-5+1(03ttt - vfn-sti
1=1
0
H
-
Next, we use the fact that Σ}= Viz(a) = VVF()). We will also again use the fact that for quadratic function ff with Hessian H. we have that ff(z) - Vf(y) = H pe--y) y):
b = 22
H (n 28
+
H H -\Aaa)) + a
H
V (1 ( - Jz (1)6-1
1=1
J=l
H R 141
V fn -2, - V fn fn-
1=1
46

---

Published as a conference paper at ICLR 2022
n
n
a
Σ H
[1 2 - (a)
S
2a
Σ
Hi
(T) 2k-1
x²) + a
H (x) 2k xz) aa)+a>>> I H.V)i(z')
1=1
1=1
H
Vf (5 - 12
i=1
H
Vn In V Sin-j+1 (2
Hi
-
a + b².
where the random variables a b² as
2
n
n
a ===-00 Σ
H;
(a ( 2k-1 -x')+ + Σ
H (m0
2k x²)) + Σ
H Vi(""") and
n
b6 =
Σ
H.
ff [0] 15
1=1
H Hn11+1
Σ V fn-541(20th1
(
i=1
Σ
i=1
Again, using smoothness assumption and bounded gradients property (Lemma I we get,
||b^|| S 3 Gnn
(38)
Next, we decompose the inner product of 2k x² and E ( in Eq. (3)
-2xx (xx²
2k x², rt) -2a
(x 2k w², at + bb,
-2a
(x)
2k-1 x² aaa 22 12
2k-1
x x²"
(39)
For the first term in 33
-2x (x:)) 2k-1 x², a² = 2
2k -1
Σ Hi
(x)
2k x²)
i=l
20 2
24 1
H²² ax)
2k-1 x²
40
x
20
2k 1
H, V fi(x))
i
< 2
D
x²
Σ i=l
Hi
(I) 24-1 x²)
47

---

Published as a conference paper at ICLR 2022
-2a²
40
2k-1 x.; Σ H, V Vi((a²))
= 4002n 1 VV 2k-
2 1)1
2cx²
x
2k- x², Σ
H: H.Vii(a)))
I 4a 4 VF 2k- I|1 + 22222nnnn n
22
2h-1
x<1
(40)
For the second term in 33 we use Sehuary- and Incq.
(38)
2a
2k
x²" b²) S 6a 3 Gn
2k-1
-x"11-
(41)
Substituting (40) and 41
back to 39 we get
-2a To
2k- x²'
4a 4a2n"
22 |11 + nII2 2k-1 VVF
x²1l
6a G' ||
2
-
x"1|.
(42)
Substituting 37 42 back to (36),
we finally get a recursion bound for one epoch:
| x= 1| v 1 - 4na L+ 11
Lt
|
2k
xx111
[Ana 1
8a²n²
|| (x 11
L u+1 p
2a (a/h-11 x², x=, ,
+ +2a² 1|7111?
< 1 4na L+ 1
Lt
||= 1x=--11 - =x²112
|4na
1
8a²n²
|| | 26 11
L + p
4a 2 || F [
1)1 + 202222n2222 2 2x -
x01l 66 L2 2| xx
x='
+ 88a 'n Gn222
1 4ma LH
x01 - [nna I, 1+1 11
1
12a2n²)
(
||
+ 2a2nLG(1 + LaLn")|| 2h-1 - xI || + 8a *n *
Next, we use the fact that 2ab s da + b²/a (for any X > 0) on the term 2a2nLG(1 3aIn?)ll=d x²1 || to get that
2a 2a²nLG(1 + 3a 28-1 x=1l S (a2nIG(1+ 3aLm))) 2 (nap) + napllaz 2k x 11
= μ aa'LL 3/
x²1
Substituting this back we get,
112 1 4na L1
|| 12
||=@ - 1= [na L L+ 1
12a²n²
L 11
+ 1 a² nT G2 + +.xxnn22 2/2 + -aappllaa 1|00
2k-1
x212 + 8ar G22
$ (1 2nap + natin || 2 1- x11 [4na
12a2n²
|/ Fa 2k 1|
L I 11
+ - a 3 nI, G² (1 + 3aIn 2/2 + Snnnnnn" T,2
(Since /A S L)
= (1 napu | 2k-1 - 1²12 |na L+
12a2n22
|VF(=**11>1
+ a 3 + + nn
Now, substituting the values of a and the bound on K, we get that 4na 1.p 12a2n2 2 and hence,
1
| x < (1 - nacu)) | x=11 +
+ 6022 + 3aIn2)3 ann..22 11
Now, iterating this for K/2 epoch pairs, we get
K 4
|| K x x11 < (1 - (1-nap)) K/2 110| -
x112 10=x111
2
a 3aLn2 + n
48

---

Published as a conference paper at ICLR 2022
K
Se 22
x=1 +
2 "0nan 4Ka'n h
S e nann//2labb x 112 + Kr a + 9Kμ a + 4Ka
(Since (1 a)² 26"
Substituting
Glog nK ank
gives us the desired result.
H ADDITIONAL EXPERIMENTS
Although our theoretical guarantees for FLIPFLOP only hold for quadratic objectives, we conjecture that FL.IPFI.P might be able improve the convergence performance for other classes of functions, whose Hessians are smooth near their minimizers. To see this, we also ran some experiments on I-dimensional logistic regression. As we can see in Figure 3 the convergence rates are very similar to those quadratic functions. The data synthetically generated such that the objective function becomes strongly convex and well conditioned near the minimizer. Note that logistic loss is not strongly convex on linearly separable data. Therefore, to make the loss strongly convex, ensured that the data was not linearly separable. Essentially, the dataset was the following: all the datapoints 1,, and their labels were y 1 =>0 with probability 3/4 and y 1l 1200 with probability 1/4. Framing this as an optimization problem, we have
min F(x) == E loglllollhhae (((o))gg((=))))))))))))))))))))) (1 y) log(1 -(xx))]
where h(x2) 1/(1 + e x) Note that = log is the minimizer of this function, which is helpful because we can use compute the exact error. Similar to the experiment on quadratic functions, n was set to 800 and step size set in the same regime in Theorems and 6
49


Reviews:
[{"review_id": "vW3F00xFD1", "reviewer": "Reviewer_53pE", "summary": "", "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": "### Strengths\n1. This paper provides some insights into permutation-based SGD for finite sum optimization. Theoretical contributions include exponential convergence rate for 1-d smooth functions, lower bound for general strongly-convex functions, and lower bound 1-d strongly-convex function with nonconvex component. \n2. The paper proposes an algorithm FlipFlop, which is easy to implement and proved to have better performance than random permutations for quadratic functions. Empirical results also show FlipFlop performs better for logistic-like functions. \n3. The paper is well organized and clearly organized.\n\n### Weakness\n1. Convergence rates of FlipFlop are only proved for quadratic functions. This is too restricted. I expect to see some discussions on the difficulty of generalizing the proof to more general functions.\n2. Other restrictions include: fixed step size; dependence only in the number of iterations; numerical verification is only for a toy example\n\n### Minor comments:\n1. A different but related problem is the permutation in coordinate-wise SGD. A discussion on whether the proposed algorithm FlipFlop can be applied to coordinate-descent would be interesting.\n", "summary_of_the_paper": "This paper studies theoretical properties of permutation-based fixed-step size SGD for finite sum optimization. The main theorems state that \n* For 1-d Hessian-smooth functions, there exists permutations such that the convergence rate is exponential in the number of iterations $K$\n* For higher dimension, there exists strongly-convex function such that the convergence rate is at best $O(1/K^3)$\n* If some component in the strongly-convex objective function is nonconvex, the convergence rate has a lower bound $O(1/K^2)$\n\nThe paper then proposes the algorithm FlipFlop, where adjacent epochs use permutations of reverse order. The algorithm is proved to improve upon random permutation when all the component functions are quadratic. The results are corroborated with simulations.", "summary_of_the_review": "In general, I recommend accepting the paper. Although the settings studied in the paper is limited, it provides a better understanding of permutation-based SGD and can motivate further studies.", "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": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "lcvJY3I6dPo", "reviewer": "Reviewer_D2Ry", "summary": "", "questions": "", "limitations": "", "rating": 10, "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": "## Writing\n\nThe submission is well written with a carefully thought-out story. I'd like to congratulate the authors on their highly polished submission.\n\n## Theory\n\nI believe the theoretical claims in the submission are sound. I thoroughly checked the proofs for Theorems 1-3 and found only minor typographic issues. \nI checked the remaining theorems (although less thoroughly) and did not discover any issues. \nSome questions/comments for the authors are as follow:\n\n**Theorem 1**: How did the authors conclude that permutations used to obtain the exponential rate are optimal?\nI would have thought a minimax lower-bound for permutation-based SGD on 1-dimensional, Hessian-smooth functions to conclude (minimax) optimality and the paper does not cite such a result.\n\n**Theorem 2**: the lower bound appears to be invariant to initialization, but only as long as the initialization is deterministic so that it can be observed by a resisting oracle. \nThis knowledge seems necessary in order to use a standard translation argument. Is this correct?\nIf so, do the authors think that a randomized bound is attainable?\nThis would more closely match practice, where $x_0$ is typically chosen at random.\n\n**Section 6.1**: I don't think this proof sketch contributes significantly to the paper as it is written.\nThe intuition that FlipFlop approximately equalizes the weights applied to the $b_i$ terms in Eq. 7 is helpful and should be retained.\nHowever, the number of approximations --- linearizing twice and then dropping higher order terms in the display at the bottom of Page 8 --- reduces my confidence in the final conclusion.\nHow do we know that Eq. 10 is still a good representation of the error after two epochs of FlipFlop given the sequence of approximations?\nThis space might be better used by Figure 3, which could be moved in to the main paper, and a discussion of potential difficulties extending the analysis to general convex functions. \n\n**Lemma 1**: This is a nice result that I agree is of independent interest.\nFor example, analyses of some stochastic gradient methods (e.g. Adagrad) require that the iterates remain in a compact set.\nTypically, constrained optimization with a compact constraint set is assumed; \nhowever, perhaps restricting the analysis to \"permutation Adagrad\" and using a result analogous to Lemma 1 could do away with this unrealistic assumption and yield more practical theorems.\n\n\n## Experiments\n\nThe experiments are small-scale and intended to confirm the theoretical developments.\nAs the methods experimented with are stochastic, they could be improved by including distribution information over multiple \"restarts\" or repeats.\nFor example, running 10 repeats with different seeds and then plotting the median + inter-quartile range would increase my confidence in the results. \nSince this is not an empirical paper, I think the change is desirable rather than essential. \n\nFigure 2:  I suggest including $n = 800 > K $ so that $1/(n^2 * K^2) \\approx K^4$ and the high-order (in $K$) terms dominate as part of the figure caption, since this information is provided two pages later in Sec. 6.2. \nThe font sizes and line-widths should be increased so that the figure is legible when printed.\nThese same comments apply to Figure 3.\n\n## Minor Comments\n\nPage 2:\n- \"As we see in the following, the answer the the above is not straightforward, and depends heavily on the function class at hand.\" --- delete extra \"the\". \n\nAppendix A.3:\n- \"In the previous subsection, we have show that...\" -> \"In the previous subsection, we have \\*\\*shown\\*\\* that...\"\n\nAppendix A.4:\n- The `restatable` environment provided by `thmtools` is useful when proving lemmas which were stated earlier in the text.\n- Bottom of page 17: you might want to be a bit careful limits of the last integral here, since there is no guarantee that $x_{i - 1} + (y_{0} - x_0)$.\n\nAppendix B.1:\n- For any $i \\\\in [n/2]$, let $p$ and $q$ be indices such that $\\\\sigma_p = f_i$ and $\\\\sigma_p = g_i$ --- I believe the second $\\\\sigma_p$ should be $\\\\sigma_q$. \n\nAppendix B.2: \n- Def.\\ of $F(y)$: I believe the definition is missing a $1/n$ term, i.e. $F(y) = \\\\frac{1}{n} \\\\sum_{i=1}^n f_i(y)$.\n- It is worth noting in the proof that the bound on $y_{n, j}$ can be applied recursively (over epochs) because it is independent of $\\sigma_s$ and thus holds for all $K$. \n\nAppendix C:\n- \"Similarly, for the other possible permutation...\" --- I think you're missing $x_{0, k+1} = \\\\ldots$ in the equation at the end of this line.", "summary_of_the_paper": "# === Update ===\n\nI have decided to maintain my score. This is very strong submission in my opinion. A brief overview of my thoughts is the following:\n\n**Topic**: This paper comes in the middle of a wave of interest in permutation SGD and similar variants. It is highly topical and a good fit for the conference.\n\n**Theoretical Results**: It is easy focus on FlipFlop and its limited analysis (i.e. quadratics only), but there are many other highly interesting results in this submission. Theorems 1 and 2 show that one-dimensional functions are \"easy\" for permutation-based optimization, while quadratics in higher dimensions are hard. Yes, this result requires a fixed step-size, but it is also the first analysis of permutation SGD conducted on the level of specific permutations. Theorem 3 refines these results to show that the improvement in Theorem 1 is specific to quadratics. The proof technique for these results is elegant (continuity of the composition of updates + IVT) and, as a I noted in my review, leads to useful intermediate results.\n\n**Experiments** The experiments are limited to synthetic data, but this is a theoretical paper with ~37 pages of appendices already. I think that an intensive evaluation of FlipFlop is beyond the scope of this submission. Moreover, since the analysis considers quadratics only, I think that the nice results on logistic regression in Appendix H are quite encouraging.\n\n# ======\n\nThis submission analyzes the effects of permutation choice on the convergence of the random-reshuffling, shuffle-once, and incremental variants of stochastic gradient descent (SGD).\nIn particular, the goal of this work is to determine settings whether specific permutations can give faster convergence than random reshuffling and in what settings. \nThe authors show that, in the case of one-dimensional finite-sum functions with smooth Hessians, there exists a sequence of permutations for which SGD converges at a linear (i.e. exponential) rate. \nHowever, they also prove that this phenomenon is specific to one-dimensional functions using a new, dimension-dependent lower bound for any permutation-based SGD method.\nThis lower bound is tight with the known convergence rate of random reshuffling, implying this method is optimal in the general setting.\nFinally, the authors restrict themselves to finite-sums of convex quadratics and develop a simple heuristic permutation \"schedule\" giving provably faster convergence. \nThis approach, which is called FlipFlop, alternates between fresh permutations and the previous permutation, but in _reverse_ order.\nSmall experiments confirm that FlipFlop accelerates convergence of permutation-based SGD variants.\n", "summary_of_the_review": "This is a very strong submission that contributes new theoretical insights to a hot topic in optimization for machine learning.\nThe lower-bound showing that random permutations are optimal in the general setting answers an open question about permutation-based variants of SGD, while the analysis of FlipFlop opens to the door to clever permutation schedules which improve convergence in specific settings.\nI think, with additional empirical justification, FlipFlop could become another standard trick in stochastic optimization. \nAdditionally, the analysis in the appendix develops many small, but novel results which may also have use for other problems in optimization; see \"Theory\" for an example.\nIn addition to the novelty of the theoretical results, the paper is polished and the writing is well executed. \n\nGiven the above, I strongly advocate for this submission to be accepted. ", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "griLa-zApx6", "reviewer": "Reviewer_jCFt", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "**Strengths**\n\nThis paper gives interesting theoretical results detailing precisely when random permutations are optimal for SGD under different settings for strongly-convex functions. The proof techniques are pretty clever. I also agree with the authors that Lemma 1 is indeed of independent interest and could facilitate future analysis on permutation-based algorithms in the strongly-convex setting. The FlipFlop technique they introduced is also very easy to implement with basically zero overhead, yet is able to speed up convergence both provably and in the synthetic experiments considered. The accelerated rate obtained are also quite impressive considering how simple the method is.\n\n**Weaknesses**\n\nBelow are some nice-to-have's that are beyond the scope of this paper, but would significantly strengthen the paper if included:\n- All analyses in this work are for either quadratic functions or strongly convex functions. It'd be nice if the authors have further insights for non-convex functions as well. \n- Since FlipFlop is such a low-cost, easy to implement way to boost the performance in the strongly-convex case, trying them out on real-data benchmarks for (strongly-)convex functions or even some deep learning benchmarks would be very interesting to see. I am especially curious whether FlipFlop can bring \"free speedup\" in practice when the objective is non-convex.\n\n\n**Typos and minor issues**\n- Theorem 2: the initialization requirement in the proof should be stated more clearly in the theorem statement. The toy example given in the proof sketch does not work when initialized arbitrarily with arbitrary step size.\n- page 13: \"Similarly, we can find show that\" -> \"Similarly, we can show that\"\n", "summary_of_the_paper": "This work investigates the optimality of random permutation as a scan ordering for SGD. They found that for general strongly convex functions with Lipschitz Hessian, random permutations are optimal in high dimension but not optimal in 1-dimension. For general convex quadratics, random permutations are also not optimal. Finally, the authors introduced a new technique termed FlipFlop that works by reversing the permutation of the previous epoch at every even epoch, and at the odd epochs the algorithm just follows its original permutation, whether it be random or cyclic. FlipFlop has been proven to improve the convergence of random reshuffling, single shuffle, and incremental gradient descent on quadratic functions. Experiments on a 100-dimensional quadratic objective and 1-dimensional logistic regression demonstrate that FlipFlop indeed converges faster than random reshuffling.", "summary_of_the_review": "Although the paper considers the optimality of permutation-based SGD only for strongly-convex functions, the theoretical results are interesting enough and the proposed trick FlipFlop seems to be a very promising approach to further accelerate random reshuffling. I am leaning towards accepting the paper, although additional experiments could further strengthen the paper.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VM5cFbF3LEt", "reviewer": "Reviewer_JbYX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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:\n1. The paper studies SGD, the workhorse of optimization in machine learning.\n2. The algorithms are simple and natural.\n3. A natural twist (flipflopping, that is, reversing the permutation every other epoch) improves convergence on some subfamilies of strongly convex functions, beating known lower bounds without such twist.\n4. The analysis does not appear to be complicated.\n5. The paper is well written and easy to read and understand.\n\nRegarding weaknesses, as admitted in the paper, the results are:\n1. Not applicable to all convex function (for flipflopping), or non-convex functions.\n2. Not applicable to other techniques such as variance reduction and momentum.\n3. Not applicable when step size is not constant.\nThose extensions will be left as future work, if possible.", "summary_of_the_paper": "This paper is motivated by the observed phenomenon that, in stochastic gradient descent (SGD), without-replacement sampling (random permutation) gives faster convergence than with-replacement sampling.\nThe paper studies whether random permutations are optimal among permutation-based SGD, by considering different deterministic, random, or hybrid ways of generating permutations of input points.\n\nFocusing on optimizing convex functions at a constant step size, the paper shows that:\n1. there exist optimal permutations which converges exponentially faster than random permutations for 1-dimensional functions.\n2. such improvement is not possible in higher dimensions or for strongly convex objectives, where random permutations are optimal.\n3. by reversing the permutation every other epoch (flipflopping), convergence on quadratic functions improves for three permutation-based methods: Incremental Gradient Descent (deterministic), Random Reshuffle (random), and Single Shuffle (hybrid).", "summary_of_the_review": "The research is well motivated, and a simple intuitive idea (flipflopping) improves convergence for certain (admittedly limited) settings.\nThis reviewer thinks the paper could be a contribution to this conference.", "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": {}}]

Author rebuttal:

Meta-review: The paper considers the effect of permutations in SGD - exploring the question of can we go beyond random permutations (which themselves have shown to be better than with replacement sampling)? The paper studies these questions from multiple viewpoints - showing that there is a one dimensional function for which the optimal permutation can be exponentially better in terms of rate than random. Further they show that for the general high dimensional the gap between random and optimal is non-existent. Further they study a Flip-Flop algorithm which flips the permutation every alternate epoch and for convex quadratics they show that this technique can lead to improved convergence rates for multiple base permutation schemes. 

Overall the results of the paper was found to be interesting across the reviewers. The reviewers agree that the paper is well written. The paper initiates the analysis in a new direction for optimization, i.e. how can we leverage permutations to further improve the convergence of GD and how much further can we go beyond random permutations. 

The only weakness highlighted by the reviewers is the limitation of scope to quadratic functions for the FlipFlop algorithm - while this is a significant restriction, given the new line of enquiry opened by the paper this can be discounted.
Decision: Accept (Poster)