Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: # === Update ===

I have decided to maintain my score. This is very strong submission in my opinion. A brief overview of my thoughts is the following:

**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.

**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.

**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.

# ======

This submission analyzes the effects of permutation choice on the convergence of the random-reshuffling, shuffle-once, and incremental variants of stochastic gradient descent (SGD).
In particular, the goal of this work is to determine settings whether specific permutations can give faster convergence than random reshuffling and in what settings. 
The 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. 
However, 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.
This lower bound is tight with the known convergence rate of random reshuffling, implying this method is optimal in the general setting.
Finally, the authors restrict themselves to finite-sums of convex quadratics and develop a simple heuristic permutation "schedule" giving provably faster convergence. 
This approach, which is called FlipFlop, alternates between fresh permutations and the previous permutation, but in _reverse_ order.
Small experiments confirm that FlipFlop accelerates convergence of permutation-based SGD variants.

main_review: ## Writing

The submission is well written with a carefully thought-out story. I'd like to congratulate the authors on their highly polished submission.

## Theory

I believe the theoretical claims in the submission are sound. I thoroughly checked the proofs for Theorems 1-3 and found only minor typographic issues. 
I checked the remaining theorems (although less thoroughly) and did not discover any issues. 
Some questions/comments for the authors are as follow:

**Theorem 1**: How did the authors conclude that permutations used to obtain the exponential rate are optimal?
I 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.

**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. 
This knowledge seems necessary in order to use a standard translation argument. Is this correct?
If so, do the authors think that a randomized bound is attainable?
This would more closely match practice, where $x_0$ is typically chosen at random.

**Section 6.1**: I don't think this proof sketch contributes significantly to the paper as it is written.
The intuition that FlipFlop approximately equalizes the weights applied to the $b_i$ terms in Eq. 7 is helpful and should be retained.
However, 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.
How do we know that Eq. 10 is still a good representation of the error after two epochs of FlipFlop given the sequence of approximations?
This 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. 

**Lemma 1**: This is a nice result that I agree is of independent interest.
For example, analyses of some stochastic gradient methods (e.g. Adagrad) require that the iterates remain in a compact set.
Typically, constrained optimization with a compact constraint set is assumed; 
however, 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.


## Experiments

The experiments are small-scale and intended to confirm the theoretical developments.
As the methods experimented with are stochastic, they could be improved by including distribution information over multiple "restarts" or repeats.
For example, running 10 repeats with different seeds and then plotting the median + inter-quartile range would increase my confidence in the results. 
Since this is not an empirical paper, I think the change is desirable rather than essential. 

Figure 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. 
The font sizes and line-widths should be increased so that the figure is legible when printed.
These same comments apply to Figure 3.

## Minor Comments

Page 2:
- "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". 

Appendix A.3:
- "In the previous subsection, we have show that..." -> "In the previous subsection, we have \*\*shown\*\* that..."

Appendix A.4:
- The `restatable` environment provided by `thmtools` is useful when proving lemmas which were stated earlier in the text.
- 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)$.

Appendix B.1:
- 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$. 

Appendix B.2: 
- 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)$.
- 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$. 

Appendix C:
- "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_review: This is a very strong submission that contributes new theoretical insights to a hot topic in optimization for machine learning.
The 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.
I think, with additional empirical justification, FlipFlop could become another standard trick in stochastic optimization. 
Additionally, 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.
In addition to the novelty of the theoretical results, the paper is polished and the writing is well executed. 

Given the above, I strongly advocate for this submission to be accepted.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
The 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.

Focusing on optimizing convex functions at a constant step size, the paper shows that:
1. there exist optimal permutations which converges exponentially faster than random permutations for 1-dimensional functions.
2. such improvement is not possible in higher dimensions or for strongly convex objectives, where random permutations are optimal.
3. 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).
main_review: Strengths:
1. The paper studies SGD, the workhorse of optimization in machine learning.
2. The algorithms are simple and natural.
3. 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.
4. The analysis does not appear to be complicated.
5. The paper is well written and easy to read and understand.

Regarding weaknesses, as admitted in the paper, the results are:
1. Not applicable to all convex function (for flipflopping), or non-convex functions.
2. Not applicable to other techniques such as variance reduction and momentum.
3. Not applicable when step size is not constant.
Those extensions will be left as future work, if possible.
summary_of_the_review: The research is well motivated, and a simple intuitive idea (flipflopping) improves convergence for certain (admittedly limited) settings.
This reviewer thinks the paper could be a contribution to this conference.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: **Strengths**

This 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.

**Weaknesses**

Below are some nice-to-have's that are beyond the scope of this paper, but would significantly strengthen the paper if included:
- 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. 
- 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.


**Typos and minor issues**
- 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.
- page 13: "Similarly, we can find show that" -> "Similarly, we can show that"

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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 
* For 1-d Hessian-smooth functions, there exists permutations such that the convergence rate is exponential in the number of iterations $K$
* For higher dimension, there exists strongly-convex function such that the convergence rate is at best $O(1/K^3)$
* If some component in the strongly-convex objective function is nonconvex, the convergence rate has a lower bound $O(1/K^2)$

The 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.
main_review: ### Strengths
1. 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. 
2. 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. 
3. The paper is well organized and clearly organized.

### Weakness
1. 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.
2. Other restrictions include: fixed step size; dependence only in the number of iterations; numerical verification is only for a toy example

### Minor comments:
1. 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.

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.
review_title: null

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)