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

9. Three minor comments (W8):

   We agree that it is best to include the dependency on the condition number, but for the rebuttal period we had to focus on addressing other major issues. We will make this clear in our next revision.

   In the initial submission, some theorems did not explicitly include the assumptions used. As correctly guessed by the reviewer, Assumptions 1–4 are used in most of the theorems. We have modified the statements accordingly.

   We added "when $K$ is large enough" below Theorem 4.1.

4. Statement regarding convergence to neighborhood of an optimum (W2)

   The reviewer is correct that both (Theorem 4.4, Diakonikolas et al., 2021) and (Theorem 3, Mishchenko et al., 2020b) show that they can find an $\epsilon$-stationary point. However, what we originally meant by “convergence to neighborhood” was that the analyses do not imply that the methods will reach an optimum as $k \to \infty$, in the sense that the optimality measure goes all the way to zero as $k \to \infty$. (Here $k$ denotes the number of iterations.) In particular, by taking a close look at the proof of (Theorem 4.4, Diakonikolas et al., 2021), one can see that we need to choose the number of samples per iteration that is greater than $\mathcal{O}(1/\epsilon)$ to guarantee finding an $\epsilon$-stationary point, and to guarantee reaching an optimum one needs $n \to \infty$ in the proof. In addition, (Theorem 3, Mishchenko et al., 2020b) presents a rate bound for a constant step size $\mathcal{O}(1/\sqrt{t})$ for a fixed budget of $t$ iterations, hence cannot handle the $t \to \infty$ case. Nevertheless, we learned that this is subtle and may confuse the readers. So, we decided to emphasize more on our other advantages over existing literature (especially those brought up by the reviewers) in unconstrained cases, and do not argue on the aspect of the convergence to neighborhood.

   We also would like to note that, as now explicitly stated in our Section 2, Diakonikolas et al. (2021) assume the variance to be uniformly bounded over the domain, which is more restrictive than our setting. In addition, Mishchenko et al. (2020b) require the domain to be bounded (as they take the supremum over the entire domain in the final bound) and the stochastic component to be monotone almost surely.

5. Lipschitz Hessian assumption (W4):

   For our comments for the Lipschitz Hessian assumption, we kindly ask the reviewer to refer to the general comments. We would also like to point out that our results in the strongly monotone setting are guarantees on the last iterate.

6. Convergence rates of SEG-RR and SEG-FF (W5):

   It is indeed true that our convergence rates $\mathcal{O} ( \frac{1}{n K^{2-3\epsilon}} )$ for SEG-RR and SEG-FF are slightly slower than the known $\tilde{\mathcal{O}} ( \frac{1}{nK^2} )$ of SGDA-RR. We believe that it is an artifact of our attempt on establishing a unified analysis (Theorem 6.2), and it is not a serious limitation since $\epsilon$ is a number that we can choose arbitrarily small. Also, our main focus is to show the effectiveness of SEG-FFA, which attains a strictly improved rate over SGDA and other SEG variants on both strongly-monotone and monotone problems, with provable gaps (recall Theorems 4.2 and 5.6 in particular).

7. On the questions regarding Section 5 (W6):

   Proposition 5.3 states that after introducing the anchoring step with $\theta =1$, choosing $\beta = \eta$ and $\alpha = \eta/2$ makes the LHS and RHS terms in (13) (which is now (15) in the revised manuscript) to match with "$\eta_1 = \eta_2 = n\eta$". This is not easy to verify because, in case of filp-flop sampling ($N = 2n$), the sum $\sum_{0 \leq i < j \leq N-1} D\boldsymbol{T}_j (\boldsymbol{z}_0) \boldsymbol{T}_i (\boldsymbol{z}_0)$ on the RHS contains both of the sums in the LHS of (13). So, we would like to refer the reviewer to Lemma C.4 for more exact calculations.

   Here, the reviewer is correct on observing that the overall update made in the FFA epoch (consisting of $2n$ steps and the anchoring) is equivalent to a single step of EG plus some small noise. This is in fact the key idea in many existing analysis of shuffling-based methods: aggregate the stochastic updates over an epoch and write them as a single deterministic update plus small noise. For SEG-FFA we have $N = 2n$ because one epoch contains $2n$ updates, but we chose this general notation $N$ because other methods may have different values of $N$; for example, we have $N = n$ for SEG-RR. We have further clarified this in our revised Section 5.

8. Anchoring but without FF (W7):

   According to our analyses demonstrated in Section 5, adding anchoring on US/RR will not show a decisive improvement, because anchoring by itself cannot achieve second-order matching. Nevertheless, we performed an ablation study testing the effect of anchoring applied to SEG-US and SEG-RR; please see Appendix H. We have not considered applying anchoring to SGDA-US and SGDA-RR, since it is obvious that they diverge for a simple bilinear finite-sum problem when $f_1(x, y) = f_2(x, y) = \dots = f_n(x, y) = xy$.

   As for the computational burden caused by flip-flop shuffling, one can simply reduce the number of epochs by half. So, in our experiments, we make comparisons between RR and FF schemes with respect to the number of passes through the components.

We appreciate the reviewer for the constructive feedback and thoughtful comments

1. Gradient norm as an optimality measure, and Nash equilibria (W1, W3):

   We would like to first point out that for (unconstrained) convex-concave problems, a point $(\boldsymbol{x}^∗, \boldsymbol{y}^∗)$ is a first-order stationary point if and only if it is a global Nash equilibrium, since $f(\boldsymbol{x}, \boldsymbol{y}^*) \geq f(\boldsymbol{x}^*, \boldsymbol{y}^*) + \langle \nabla_{\boldsymbol{x}} f(\boldsymbol{x}^*, \boldsymbol{y}^*), \boldsymbol{x} - \boldsymbol{x}^* \rangle$ and $f(\boldsymbol{x}^*, \boldsymbol{y}) \leq f(\boldsymbol{x}^*, \boldsymbol{y}^*) + \langle \nabla_{\boldsymbol{y}} f(\boldsymbol{x}^*, \boldsymbol{y}^*), \boldsymbol{y} - \boldsymbol{y}^* \rangle$.

   While we agree that the squared gradient norm is not an adequate measure of convergence for constrained problems (as also pointed out in Section 1.1 of (Gorbunov et al., 2022b)), taking the squared gradient norm as an optimality measure is not unnatural in unconstrained problems. We would also like to note that Gorbunov et al. (2022b) study the convergence of EG in the unconstrained case, using the squared gradient norm as the optimality measure.

   We would like to also note that the convex and compact domain assumption in von Neumann’s minimax theorem is a sufficient condition for the existence of a Nash equilibrium, but not a necessary condition. For example, consider a simple bilinear problem with $f (x, y) = xy$. This has a unique first-order stationary point $(0, 0)$, which is a global Nash equilibrium. For this reason, we believe that Assumption 2 is natural, as it is analogous to assuming the existence of a minimum in convex minimization.

2. Existing results on anchoring (W1):

   We appreciate the reviewer for bringing up the existing results that adopt similar ideas of anchoring, which was not explained well. First of all, we have clarified in footnote 1 that our anchoring and the Halpern-based anchoring are different in their formulations. In addition, their motivations differ as the former (ours) is for the second-order matching that makes SEG converge in the convex-concave cases, while the latter is for acceleration in rate. Therefore, we would like to claim that our anchoring approach is new, in the sense that we adopt the idea for making SEG converge in the first place. The (Cai et al., 2022) [arXiv:2203.09436] paper you kindly mentioned introduces the Halpern-based anchoring to SEG for acceleration, but it requires increasing the batch size after each epoch, on top of the requirement that the variance is uniformly bounded over the domain, which are quite restrictive compared to our setting. This is now stated in Section 2.

3. Stochastic GDA (W2):

   We are not sure which paper the reviewer is referring to, and we would appreciate it if the reviewer could give us a pointer; nevertheless, we suspect that the mentioned convergence guarantee might not apply to our unconstrained convex-concave setting. This is because, in the unconstrained $\min_x \max_y f (x, y) = xy$ case, the duality gap $\max_y f (\bar{x}, y) − \min_x f (x, \bar{y})$ is always $\infty$ unless $(\bar{x}, \bar{y}) = (0, 0)$. Hence, duality gap results should require the assumption of bounded domain. Nevertheless, we would be happy to learn about the reference that discusses the ergodic convergence of the stochastic GDA.

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

1. On the experiments (Q1):

   As suggested, we expanded the experiment section with details, and moved it to Appendix H.

2. Clarification on the last sentence in Section 7 (Q1):

   We entirely rewrote the experiment section to accommodate the reviewer’s suggestions, and the last sentence in Section 7 is now removed. Anyway, by the last sentence in Section 7, we were pointing to the observation that even though the step size chosen according to our analysis successfully converges, the algorithm also converges with much larger choices of step size. This behavior suggests that maybe the convergence of SEG-FFA can be shown for a larger step size and hence with a faster rate; this is what we meant by "room for improvement".

3. Flip-flop shuffling to other problems (Q2):

   Since a minimization problem can be viewed a special case of a minimax problem whose objective function is constant with respect to the maximization variable, at the very least, our results should be directly applicable to convex minimization problems. Still, our arguments and proofs are tailored to minimax problems, so investigating whether one can improve upon our results for minimization problems would be an interesting future work.

We appreciate the reviewer for acknowledging the importance of studying the shuffling-based SEG and for providing the comprehensive feedback.

1. Comparing with (Hsieh et al., 2020) (W1):

   You are correct that the initial version was confusing, and we have now revised the paper (in footnote 2) so that it is clear that we focus on a same-sample version of the SEG (i.e., use the same component function for both extrapolation and update steps), which we believe is a more efficient and natural implementation of EG in without-replacement sampling scenarios. Hsieh et al. (2020) consider different independent samples for the two steps within one update of the SEG, so there is no contradiction between (Hsieh et al., 2020) and our results.

   A noteworthy remark regarding the comparison of our algorithm against (Hsieh et al., 2020) is that the existing paper shows convergence to an optimum for a convex-concave problem but does not have an explicit rate; in contrast, we prove convergence with a rate.

2. On whether EG is a good approximation of PP (W2):

   The claim by Gorbunov et al. (2022b) on the “significant” difference between EG and PP is based on the observation that PP update, as an operator, is always nonexpansive, while EG update may be expansive. In contrast, we look at the two algorithms from a different angle; our motivation was that a method that differs from EG by at most $\mathcal{O}(\eta^3)$ would lead to convergence in convex-concave settings, where $\eta$ is the step size. This was based on the observation, in (Mokhtari et al., 2020), that the update equations of the convergent methods—namely EG and PP (and even OGDA)—differ from each other by at most $\mathcal{O}(\eta^3)$ per epoch. Importantly, the updates of divergent methods such as GDA and various SEGs without FFA differ from the convergent methods by at least $\mathcal{O}(\eta^2)$, leading to our conjecture that the $\mathcal{O}(\eta^2)$ error is the main cause of nonconvergence. We believe this concern arose because of our unclear writing of Section 5, and we put efforts on improving the presentation of that section.

3. On the presentation of Section 5 and second-order matching (W3-4):

   By second-order matching we mean choosing proper step sizes, sampling scheme, and anchoring scheme so that our without-replacement SEG can deterministically match the update equation of a convergent algorithm (EG or PP) up to the $\mathcal{O}(\eta^2)$ terms (i.e., second-order terms in the Taylor expansion). We added the term “Taylor expansion” and improved corresponding sentences in the revision to make the definition of second-order matching clear.

   We have also improved Section 5 to make our argument “$\mathcal{O}(\eta^3)$ for the approximation error turns out to be the key to the exact convergence to an optimum under the monotone setting” clearer. We provide a brief summary of Section 5 below for your understanding.

   We show in Section 5.1 that the second-order matching is not achievable for both SEG-RR and SEG-FF. SEG-RR suffers a difference of at least $\mathcal{O}(\eta^2)$ from the convergent methods. For SEG-FF, as we show in Proposition 5.2, the best we can do is to choose specific step sizes and get an $\mathcal{O}(\eta_1^3)$ approximation of an instance of EG+ with $\eta_2 = 2\eta_1$. However, unfortunately, EG+ with $\eta_2 = 2\eta_1$ fails to converge already on bilinear problems. On the contrary, as we show in Proposition 5.3, SEG-FFA can approximate the standard EG with an error of $\mathcal{O}(\eta^3)$. In Section 5.2, we show that this second-order matching property of SEG-FFA indeed enables us to establish improved convergence rates.

4. On the Assumptions for Theorems (W5):

   In the initial submission, statements of some theorems did not explicitly include the assumptions used. As correctly guessed by the reviewer, Assumptions 3 and 4 are used in most of the convergence proofs. We have modified the statements accordingly.

5. Reasonableness of the assumptions 3 and 4 (W6):

   For our comments for Assumption 3, we invite the reviewer to check the general comment.

   In regard of Assumption 4, the analyses of Gorbunov et al. (2022a) does not require any bound on the variance, but they do require the stochastic gradients to be sufficiently regulated in the following sense: assuming for each $i$ that the operator $\boldsymbol{F}_i$ is $\mu_i$-strongly monotone (allowing $\mu_i < 0)$, it should hold that $\sum_{i=1}^{n} \mu_i ({\boldsymbol{1}_{{\mu_i \geq 0}}} + 4 \cdot \boldsymbol{1}_{ \mu_i \textless 0 }) > 0$ where $\boldsymbol{1}$ denotes the indicator function (see eq. (9) in their paper). Thus, this is close to assuming strong monotonicity of the majority of component functions $\boldsymbol{F}_i$, and we believe that this already should provide sufficient level of “contraction” to show convergence without bounded variance assumptions. In stark contrast, we do not make any (strong) monotonicity assumptions on $\boldsymbol{F}_i$; our monotonicity assumptions only apply to their mean $\boldsymbol{F}$. Thus, we believe that our paper and (Gorbunov et al., 2022a) are not directly comparable because of different regularity conditions on the stochastic gradients. We now briefly mention this in footnote 3.

6. On the experiments (W7-8):

   We hope now that your concern on our choice of same step size $\alpha_k = \beta_k$ in the experiment has been somewhat alleviated, considering that we focus on the same-sample case. Nevertheless, we learned that a numerical comparison with a convergent independent-sample SEG in (Hsieh et al., 2020) is necessary, so we added an experiment in which we discovered that SEG-FFA outperforms the method in (Hsieh et al., 2020). We also conducted an experiment on strongly monotone problems in which SEG-FFA again outpaced all other baseline methods.