Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements

We appreciate the effort made by the reviewer in inspecting our manuscript.

1. Monotone Case: Why Not Use Full Batch? (W1):

   This point, raised by the reviewer, is valid. However, in practice, shuffling-based stochastic methods are prevalent; it is not an exaggeration to say that they are now the de facto standard. While shuffling-based stochastic minimization is now relatively well understood, there has been limited progress on studies that theoretically support using shuffling-based stochastic minimax optimization methods. In particular, it was unknown whether shuffling is beneficial in the monotone setting. The main purpose of our study is to enhance our understanding of this already widely used sampling scheme.

   Just to add our two cents: in minimization problems, recall that SGD is asymptotically slower than GD, as SGD only converges sublinearly on strongly convex problems while GD enjoys linear convergence. In spite of that, SGD and its variants are used everywhere in practice, whereas full-batch GD appears rarely. We believe the machine learning community has reached a consensus that using SGD has benefits beyond textbook convergence rates, such as better generalization properties and implicit regularization; see for example [A] and [B], and we refer to [C, Chapter 9] for an in-depth discussion. It is natural to expect similar benefits in minimax problems if stochastic methods are used, but to reach that state, we first have to understand the convergence properties of stochastic minimax methods. Thus, we believe our work is an important step forward in this direction.

2. Tradeoff in the Convergence Rate for Strongly Monotone Problems (W2):

   We have realized that the convergence rate in the original submission was derived suboptimally regrading $\varepsilon$, and a slight modification in the final few steps of the proof makes the exponent of the exponentially decaying term to depend on $K$ instead of $K^\varepsilon$. Please refer to the general comments for the details.

3. Theorem 4.1 vs. Hsieh et al. (W3):

   Hsieh et al. [24] use independent-sample SEG, while we consider same-sample SEG. Thus, the two results can coexist. Our focus lies on the same-sample strategy as it combines more naturally with shuffling-based schemes. Please refer to the paragraph on lines 57–65, and the footnote in the same page.

4. Dependencies on Noise Parameters (W4):

   Please refer to the general comments.

5. On How Rates are Demonstrated in Table 1 (W5):

   Considering that an improved rate (regarding the exponentially decaying term) has now been obtained, we now could safely say that omitting the exponentially decaying term does not give a decisive advantage to us. In fact, as we can see from Table 1 in [17] as an example, it is customary to hide the logarithmic dependencies when one summarizes the convergence rates into a table, while deferring the exact formulae to the theorem statements. We hope that the reviewer will agree that, given the improved exponential term, omitting the exponential terms in the table is no longer misleading.

6. On Using Two Stepsizes (W6):

   We are indeed using the term EG in a broad sense, allowing it to use two stepsizes. Hence we introduced the update rule of EG using two stepsizes from the beginning, in (2). However, while we admittedly have not made this point clear enough, we do not assume any explicit constraints on $\alpha_k$ and $\beta_k$, unlike [16] which only considers when $\alpha_k \geq \beta_k$.

   Also, while the inner iteration of SEG-FFA does use $\alpha = \beta/2$, thanks to the anchoring step, the overall update of the epoch sums up to the "standard" EG as introduced by Korpelevich [27]), modulo a small noise. Hence, our method is not completely different from [16].

   We understand that these might cause slight confusions. We will try to find a way to present this clearer in our revision.

7. Additional Related Work (W7):

   Thank you for notifying us about the related work. We agree with you on that there is an interesting resemblance between SEG-FFA and the mentioned Lookahead methods, and we will add a comment on it in our revision.

We hope that our response resolves your concerns. We would greatly appreciate it if you could consider re-evaluating our paper. Thank you.

[A] On Large-Batch Training for Deep Learning, Keskar et al. (2017)

[B] On the Generalization Benefit of Noise in Stochastic Gradient Descent, Smith et al. (2020)

[C] Understanding Deep Learning, S.J.D. Prince (2023)

We appreciate the reviewer for the constructive feedback and thoughtful comments.

1. Importance of Initial Point due to the Anchoring Step (W1):

   For any optimization method, its behavior is more or less influenced by the choice of the initial point, and our SEG-FFA is not an exception. However, as we have shown (in Prop. 5.3) that the total update of SEG-FFA made over an epoch is equal to an update made by a deterministic EG up to a small $\mathcal{O}(\eta^3)$ noise, we think the dependency of SEG-FFA on the initial point is as minimal as that of the deterministic EG.

2. On $\varepsilon$ in the Convergence Rates (W2):

   Please refer to the general comments.

3. Lower Bounds on SEG-FFA (W3):

   Unfortunately, at the moment we are not aware of the lower bound complexities for SEG-FFA. To the best of our knowledge, our work is the first to introduce the idea of flip-flop + anchoring, and has not been investigated even in the context of minimization problems. A search for an explicit lower bound would also be an interesting direction of future work.

4. Why SEG-FFA is better than SEG-FF (Q1):

   The explanations on how SEG-FFA outperforms SEG-FF are detailed thoroughly in Section 5 through the lens of Taylor expansion matching, with a summary in lines 257–261, rather than in the proofs. To summarize, SEG-FFA can achieve a second-order matching to the deterministic EG, leaving an error as small as $\mathcal{O}(\eta^3)$. Whereas, SEG-FF is at best only a first-order matching method, since an attempt to make it a second-order matching method leads to it approximating a nonconvergent method. Please refer to to Section 5.1.2, and the related Appendices D and E, for the details.

5. Difference in the Notations for Stepsizes across the Methods (Q2):

   Please refer to the general comments.

6. Interpretations on Fig. 4 (Q3):

   The reviewer has made a correct observation. However, as discussed in lines 1519–1521, these results do not counter our theoretical analyses. Indeed, the convergence results in the strongly monotone setting are established under a fixed choice of the time horizon $K$ (see Thm. 5.5). More precisely, the results for strongly monotone $F$ are interested on how small $\|\| F z \|\|$ can be eventually made after running for $K$ epochs. So, for the initial few steps, the speed of convergence may be slightly suboptimal.

7. Typos (Q4):

   Thank you for notifying us about the typos. We will try our best to fix them. We would also greatly appreciate it if you could point out some of them to help us correcting them.

8. Paper is Too Long (L1):

   It is true that the paper is longer than average, but we hope that the reviewer understands the length of the paper as an unavoidable side effect of encompassing multiple rigorous proofs with technical details.

9. Additional Experiments on Large-Scale Problems (L2):

   Due to the nature of our paper focusing more on the theoretical results, we admittedly did not consider much about additional experiments. Yet, we thank the reviewer's suggestion, and will contemplate on which additional experiments will be beneficial to our paper.

We appreciate the reviewer for the positive feedback and thoughtful comments.

1. On the Comments on the Notations Used (W1, W2):

   The reviewer has made valid points, and let us share our thoughts about the comments made by the reviewer. The second set of equations in (2) may cause a bit of confusion, as concerned by the reviewer. However, considering the problem formulation in Eq. $(1)$, the subscripts $x$ and $y$ are to represent which argument we are taking the derivative with respect to. In contrast, $u$ and $v$ in Eq. $(2)$ are actual points we evaluate the gradients at. This notation is consistently used throughout the paper.

   Regarding the second suggestion, we realized that saying that $F_i$ is $L$-Lipschitz and $M$-smooth indeed sounds more natural, coherent to the existing literature. We will make necessary changes in the revision.

   In line 178, as the first equation in Asmp. 3.3 asserts that $F$ is $L$-Lipschitz, we would have $f$ being $L$-smooth, as in the original submission.

2. Existence of $\varepsilon$ in the Convergence Rate (Q1):

   Please refer to the general comments.

3. Other Possible Variants of SEG-FFA (Q2):

   The weights $1/2$ in the convex combination $(12)$ are judiciously chosen so that SEG-FFA achieves second-order matching, under the choice of $\alpha_k = \eta_k /2$ and $\beta_k = \eta_k$. Our Prop. D.1 demonstrates what happens when we choose other convex combinations. It is indeed possible to choose $\alpha_k$, $\beta_k$, and the weight $\theta$ in the convex combination as long as Eq. (29) achieves an error of $\mathcal{O}(\eta^3)$ à la Prop. 5.3.

4. On the Idea of Tail Averaging (Q3):

   Based on our current understanding, the benefits of the averaging technique (in minimization problems) mostly comes from applying Jensen's inequality. However, in minimax problems where a possibly nonconvex function $||F(\cdot)||$ is used as an optimality measure, we are not sure how averaging could be applied. We would also like to remark that this inability to apply Jensen's inequality to $||F(\cdot)||$ was overlooked in [17], leading to an invalid convergence result.

5. Appearence of the Noise Parameters $\rho$ and $\sigma$ (Q4):

   Please refer to the general comments.

6. Extending to Independent Sampling (Q5):

   As we work in the context of random reshuffling schemes, the correct update rule for the independent-sample setting is less clear than in the same-sample setting. The main challenge in generalizing our framework to independent-sample SEGs thus lies in interpreting it in terms of random reshuffling, rather than in technical difficulties. Nonetheless, should we aim to devise an independent-sample method, the simplest way would be to use two independently chosen permutations, one for the extrapolation step and the other for the update step. For such a method, Eq. (8) reads $w_i^k = z_i^k - \alpha T_i^k z_i^k$, $z_{i+1}^k = z_i^k - \beta T_{\pi(i)}^k w_i^k$ for some permutation $\pi:[n]\to[n]$. Accordingly, the right hand side of Eq. (11) then becomes ${\alpha\beta} \sum_{j=0}^{N-1} DT_{\pi(j)}^k (z_0^k) T_j^k z_0^k + {\beta^2} \sum_{ i < j } DT_{\pi(j)}^k (z_0^k) T_i^k z_0^k$. It is not difficult to check that the exact same choices of $\alpha$, $\beta$, and $\theta$ used in the same-sample SEG-FFA will also achieve second-order matching in the independent-sampling case. As our convergence analyses are valid for generic methods that achieve the second-order matching property (recall the statements of Theorems F.5 and G.4), we expect that it is possible to derive analogous results for the independent-sample variant of SEG-FFA, but there remain details to be checked of course.

We appreciate the effort made by the reviewer in inspecting our manuscript.

1. On the Lipschitz Hessian Assumption (W1): As both our manuscript and the reviewer have mentioned, the Hessian Lipschitz assumption is a somewhat unusual one, not widely assumed in the literature. Still, it is not too difficult to find machine learning problems that satisfy the Hessian Lipschitz condition. As a basic example, consider the logistic loss function $\ell(w;a) = \log(1+e^{aw})$. It is not difficult to verify that $\ell'''(w;a) = \frac{a^3 e^{aw} \left(1 - e^{aw}\right)}{\left(1 + e^{aw}\right)^3} = \frac{a^3}{1+e^{aw}} \cdot \frac{e^{aw}}{1+e^{aw}} \cdot \tanh(-\frac{1}{2}aw)$ and thus $|\ell'''(w;a)| \leq |a|^3$. Now, when given a dataset $(x_i, y_i), i=1, \dots, n$, recall the typical form of the loss function $\frac{1}{n} \sum_{i=1}^n \ell(w;-y_ix_i)$. Since $|\ell'''(w;-y_ix_i)|$ is upper bounded by a constant $\max_{i=1,\ldots,n} |y_i x_i|^3$ for all $i$, the Hessian Lipschitzness follows.

2. Relaxations of Assumption 3.3 (Q2): While we unfortunately do not have a definite answer to this question, let us at least share our intuitions on this assumption. The reason we impose the Hessian Lipschitzness assumption originates from the analysis of the flip-flop sampling scheme (cf. [41]). In short, the desideratum is that the change in the Hessian of $f$ remains controllable throughout an epoch, so that after aggregating the updates we get a good enough approximation of a deterministic EG step. If such control is possible with other assumptions then one would be able to replace Assumption 3.3 with it.

   We would also like to make a final remark that as we discussed in lines 199–202, the lower bound results that are obtained under our set of assumptions also serve as valid lower bounds for weaker settings that are implied by ours, so having the Lipschitz Hessian assumption is not a weakness in this scope.

3. Comparing Methods on the Same Plot (W2): We would like to remark that, in the plot(s), we actually do count in the fact that SEG-FF and SEG-FFA make twice as many oracle calls than other methods. That is why for those two methods we plot the values of $\|\|Fz_0^{t/2}\|\|$ instead of $\|\|Fz_0^{t}\|\|$; please refer to the captions below the plots.

4. Choice of Stepsizes in the Experiments (W3): We thank the reviewer for bringing up this point. We realized that the rationale behind our choice of the $\mathcal{O}(1/k^{0.34})$ stepsize schedule has not been thoroughly discussed in the submission, so please allow us to elaborate further.

   Strictly speaking, to make use of the convergence result of Thm 5.4—or more precisely, Thm. G.4—one should choose $\eta_0$ so that it satisfies both equations $(121)$ and $(122)$. However, if one closely examines the proof of Thm. G.4., it is not difficult to realize that choosing the stepsizes so that $\eta_k = \Omega({1}/{k^q})$ for $\frac{1}{3} < q < \frac{1}{2}$ while $\eta_k \leq \frac{\eta_0 \sqrt[3]{2} \log 2}{(k+2)^{1/3} \log (k+2) }$, we will still achieve a convergence to a stationary point, but at a cost of having a slightly slower rate of convergence $\mathcal{O} ({1}/{K^{1-2q}} )$. But then, since the decay of $1/k^q$ is faster than that of $1/(k^{1/3}\log k)$, simply taking $\eta_k = {\eta_0^*}/{k^e}$ for a suitably small $\eta_0^*$ will suffice, as there will exist some $K_0$ such that $k \geq K_0$ implies the inequality $\eta_k \leq \frac{\eta_0 \sqrt[3]{2} \log 2}{(k+2)^{1/3} \log (k+2) }$, and we may simply ignore the first $K_0$ iterates to get a convergence guarantee.

   We will add a more formal version of the discussion above in our revision.

5. Notation in Thm. 5.4 (Q1): Please refer to the general comments.

6. Additional Comparisons with the Existing Works (Q3): Despite everything, if we were to compare the number of gradient oracle calls according to their face values, SEG-FFA would in fact require $\tilde{\Omega}(1/\epsilon^3)$ calls as the rate of convergence is $\tilde{\mathcal{O}} (1/K^{1/3})$, whereas, for example SPEG would require $\Omega(1/\epsilon^2)$ calls as claimed in p. 34 in their paper.

   However, we would like to raise the point of whether it is fair to compare our SEG-FFA in its current form to methods that allow increasing batch sizes. SEG-FFA allows a constant batch size (of 1), which is common in practice, by coping with noise induced by gradient variance. Conversely, increasing batch size is not only rarely used in practice but also essentially sidesteps the complexities of dealing with gradient variance, as a batch size of $b$ reduces variance by a factor of $b$. Please recall Thm. H.4, where we showed that methods known to converge with increasing batch sizes may no longer converge if the batch size is kept constant.

   Thus, if we really were to compare SEG-FFA to such methods, it shall be allowed for SEG-FFA to have increasing batch sizes as well. But this approach not only reduces the RHS of Assumption 3.4 by the size of the batch but also reduces the number of passes in an epoch—which is $n$ for single-sample-in-a-batch SEG-FFA—according to how batches are formed. Consequently, the size of the noise term $\|\|r^k\|\|$ will be reduced, and SEG-FFA would enjoy a much better convergence rate. We believe that convergence analyses incorporating this change should be conducted as future work.

   On a different note, as we have listed in Table 2, the work on BC-SEG+ ([39] in our paper) assumes uniformly bounded gradients. This, as discussed in lines 190–196, is too strong to be a realistic assumption, so we have not included a thorough review of it in the current submission. But yet, we agree that supplementing additional comparisons with [39], and the suggested related work by Choudhury et al., will make how our paper is positioned within the existing literature clearer. We will modify Section B.1 accordingly.