Two-timescale Extragradient for Finding Local Minimax Points

We thank the reviewer for a positive evaluation and constructive feedback.

1. Computation of quantities such as $\boldsymbol{S}_\text{res}$, $s_0$, $\eta ^ *$, $\sigma_j$, and $\iota_j$ are expensive (W1)

   The reviewer’s concern on the computational difficulties on the quantities we introduced (e.g., $\boldsymbol{S}_\text{res}$, $s_0$, etc.) is indeed a valid point. However, we would also like to stress that the main point of our work is on the theoretical side; establishing a sound study on local minimax points and demonstrating the first ever result on how they can be found by a first order method, when the strong invertibility condition on $\nabla_{\boldsymbol{y}\boldsymbol{y}}^2 f$ is removed. Nonetheless, note that we also provide the results (Theorem 6.4 and the discrete-time counterpart in the appendix) that relaxes much of the computational load by removing the dependencies on $s_0$ (and $\eta_0$ in the discrete-time), under the mild assumption of $\sigma_j$ all being distinct.

2. Intuition on $\boldsymbol{S}_\text{res}$ (W1)

   The design of $\boldsymbol{S}_\text{res}$ is done so that the (classical) Schur complement $\boldsymbol{S}$ being "positive definite on a certain subspace" is equivalent to $\boldsymbol{S}_\text{res}$ being positive semidefinite (cf. Proposition 4.1). Such a property is directly related to the "refined second-order necessary condition" for local minimax points; see Proposition 4.2. While this line of thoughts can be inferred from Section 4, we acknowledge that our concise presentation on this part might make it hard for the readers to capture this idea. However, we regretfully ask the reviewer (and all the other readers of this paper) to mercifully understand that we cannot help but keep this part to be compactly presented as it is done now, in order to comply with the page limit.

3. Nondegeneracy of $\boldsymbol{S}_\text{res}$ (W2)

   From the theoretical point of view, the nondegeneracy of $\boldsymbol{S}_\text{res}$ enables us to establish the stability analyses. It is well known that determining local optimality for nonconvex-nonconcave problems efficiently without imposing any assumptions is a nearly impossible task; already for minimization problems determining if a stationary point is a minimum or not is a co-NP complete problem (see, e.g., Lee et al., 2019). The current understanding of ours is that the nondegeneracy of $\boldsymbol{S}_\text{res}$ is the necessary ingredient that enables the spectrum analyses.

   As for an intuitive explanation, considering that when $\nabla_{\boldsymbol{y}\boldsymbol{y}}^2 f$ is invertible the ordinary Schur complement is strongly related to the Hessian of the primal function (Fiez et al., 2020), we conjecture that the restricted Schur complement should also take an analogous role, but unfortunately we currently do not have a rigorous proof of this claim.

   Still, we would like to stress that we have extended the stability analysis by introducing the new nondegeneracy assumption on the restricted Schur complement which is much less restrictive than the previously assumed nondegeneracy of $\nabla_{\boldsymbol{y}\boldsymbol{y}}^2 f$. For now, we shall leave the investigations on the implications and/or intuitive interpretations of the invertibility of $\boldsymbol{S}_\text{res} (\boldsymbol{H})$ and the studies on whether such condition can be further relaxed as future works.

4. Continuous/Discrete and EG/GDA (W3)

   Admittedly, Example 2 was indeed confusingly written in the original manuscript, not clearly distinguishing continuous-time and discrete-time discussions. The arguments in Example 2 are now fixed to address this issue, and similar revisions are made across the paper.

   Meanwhile, we would like to point out that the stability analysis of discrete GDA should be—considering the update rule of GDA—done with $\boldsymbol{I} - \eta \boldsymbol{H}_{\tau}^{*}$ instead of $\boldsymbol{H}_\tau^*$ itself. Hence, the equilibrium $(0, 0)$ of $\min_x \max_y \ xy$ is a local minimax point but is strict linearly unstable for (discrete-time) GDA even with timescale separation. This is now (visually) demonstrated in Appendix G.2, which we added to enhance the contrast between (discrete-time) GDA and EG.

5. Clarifying notations (W4)

   Thank you for your suggestion. We have added the introduction of notations in the definitions and theorem statements.

We thank the reviewer for a positive evaluation of our work and constructive feedback.

1. Organizations of the paper (W1)

   Thank you for the considerate suggestions. Here are our thoughts on your recommendations.

   • As correctly pointed out by the reviewer, the hemicurvature does play an interesting role in the analyses conducted in Section 6. Yet, we ask the reviewer to kindly understand our decision to keep the details in the appendices, in order to focus more on the results and the discussions in Section 6; the protagonists of our paper. Still, we would like to mention that at the end of Section 5.2.1 there does exist a brief sketch on the properties, with pointers to the relevant sections in the appendices.

   • Currently, our understandings on the role of additional assumptions of $\sigma_j$ being distinct is mostly from a technical point of view; the main reason we take it is to have Lemma E.11 (which is now Lemma F.11 in the revised manuscript). Still, we think this assumption is mild one, because when the size of a matrix is fixed, the set of matrices with non-distinct singular values is of measure zero.

   • The condition $\boldsymbol{u}_j^\top \boldsymbol{S} \boldsymbol{u}_j \geq 0$ is more of a result of the theorem than an assumption, because it appears as one of the conditions for a necessary and sufficient condition for strict linear stability. Nonetheless, an interesting point to observe is that $\boldsymbol{S}_\text{res} \succeq \boldsymbol{0}$ with the additional $\boldsymbol{u}_j^\top \boldsymbol{S} \boldsymbol{u}_j \geq 0$ gives us a condition that is somewhere between the necessary ($\boldsymbol{S}_\text{res} \succeq \boldsymbol{0}$ only) and the sufficient ($\boldsymbol{S} \succeq \boldsymbol{0}$) conditions from Theorem 6.3.

   • There does exist a latent relationship between $s^*$ and $s_0$, as elaborated in the proof of Theorem 6.2. However, in the perspective of the statement of Theorem 6.2, we don’t really have to focus on how those two are related; rather, it is more natural to consider them appearing from two different conditions, which are shown to be equivalent by Theorem 6.2. The same goes to $\eta^*$ and $s_0$ in Theorem 6.6. But always, one can refer to the proofs of those theorems to find a full explanation on the quantities $s^*$ and $\eta^*$ .

   • As suggested, we made the abstract more instructive, reduced the related work section, and added more explanation in Section 5. We will make the paper more readable in our next revision.

2. Benefits of EG over GDA (W2)

   We added the results from (Fiez & Ratliff, 2021) on GDA that corresponds to our Proposition 6.1 and 6.5, with some remarks, in Appendices F.2 and G.2. There we compare GDA and EG, in particular contrasting the regions where the spectrum of $\boldsymbol{H}_\tau^∗$ can lie on for $\boldsymbol{z}^∗$ to be stable for each methods. We hope this enhances the presentation of our work.

3. Typo in Example 1

   You are correct; the local minimax points are $(0, 0, t, 0, t)$. We appreciate your careful proofreading. The typo is now fixed.

4. Example concerning the restricted Schur complement (Q1)

   The second example in Example 1 (which is also Example 3) is in fact a case where the restricted Schur complement is nonsingular, while the (classical) generalized Schur complement is degenerate. We kindly refer the reviewer to the details presented in Appendix B.3 (which is now Appendix C.3).

5. Relation between Assumption 2 and Theorem 5.3 (Q2)

   Analyzing the spectrum of a perturbed linear operator is in general a highly challenging task, but there will still be some things we can say about Theorem 5.3 without Assumption 2. For instance, following our proof of the theorem, one should be able to draw similar conclusions about type (i) and type (iii) eigenvalues. Recalling that the type (i) eigenvalues are the ones newly identified—that is, the ones that do not appear in (Jin et al., 2020)—to some extent this also demonstrates the effectiveness of our new spectral analysis. Yet, it is also true that some conclusions will no longer hold without Assumption 2; for instance, we would not be able to conclude whether the remaining eigenvalues (i.e., the ones that would have been the type (ii) eigenvalues if Assumption 2 was present) are of order $\Theta(\epsilon)$ or not.

We thank the reviewer for a positive evaluation of our work and constructive feedback.

1. On the global convergence

   We added the phrase "under a nonconvex-nonconcave setting, such as the MVI, where a global convergence to a stationary point is guaranteed" in Remark 6.8, so that the readers know the limitation of our global convergence analysis, coming from the existing limitation of the global convergence of EG.

   As noted by the reviewer, Appendix I for the global convergence of the two-timescale EG is proven under the MVI condition, but not the weak MVI condition considered in (Diakonikolas et al., 2021). We would like to note that, as briefly mentioned in Appendix I, one can extend the results to the weak MVI for the EG+.

2. On the suggestions

   • We agree that some definitions are hard to follow, which is mostly due to the page limit. We at least made the definition of $\boldsymbol{H}_\tau$ more visible.

   • The work by Bauschke et al. (2019) is notable, but considering that the concept of comonotonicity in our work is introduced as an interesting side remark (and also the strict page limit of 9 pages), it seems for us that mentioning (Gorbunov et al., 2023) is sufficient for our presentation.

   • Contrasting the timescale separation between players with the double step strategy in (Hsieh et al., 2020) will only make the paper clearer, but please understand that we are already running out of space, and the distinction between double step (as in (Hsieh et al., 2020)) and timescale separation (as in ours) seems clear from equation (4).

3. Comparison with (Zhang et al., 2022) (Q1)

   Zhang et al. (2022) indeed came up with a similar concept to study the nature of local optimal points for quadratic problems, but our study applies to general minimax problems. We added mentioning Zhang et al. (2022) when introducing the restricted Schur complement, as it admittedly seems that we missed giving Zhang et al. (2022) the necessary credits for establishing a prototypical analysis in this direction.

4. Finiteness timescale separation (Q2)

   The notation $\infty$-EG is introduced purely for convenience, and does not actually mean that the timescale separation parameter $\tau$ should be infinitely large. As stated in Definition 6, our results hold whenever we choose a finite time separation $\tau$ that is larger than a certain threshold $\tau^*$. The infinity symbol $\infty$ is to emphasize that the timescale separation $\tau$ being larger than a certain threshold is sufficient, and it does not matter how large $\tau$ actually is.

We thank the reviewer for a positive evaluation of our work and constructive feedback.

1. Benefits of EG over GDA (W1)

   We would like to point out that Examples 2 and 3 describe two illustrative examples (with degenerate $\nabla_{\boldsymbol{y}\boldsymbol{y}}^2 f$) that two-timescale GDA fail while two-timescale EG work.

   Also, Appendices F.2 and G.2 are added to compare EG to GDA, in particular contrasting the regions where the spectrum of $\boldsymbol{H}_\tau^*$ can lie on for $\boldsymbol{z}^*$ to be stable for each methods. We hope this enhances the presentation of our work.

2. Conclusions and Discussions Section (W2)

   We do also acknowledge that the current position of the final discussions section is unnatural. However, due to the strict page limit, we could not help but to move that section to the appendix. We at least moved the discussion section furthest forward in the appendix to make it closest to the main text.

3. Timescale separation with EG (Q1)

   The primary intention of introducing timescale separation is indeed to achieve convergence, but more specifically, convergence to local minimax points. In particular, Jin et al. (2020) showed that, under the assumption that $\nabla_{\boldsymbol{y}\boldsymbol{y}}^2 f$ is invertible, a sufficient timescale separation in GDA leads to a convergence to local minimax point, while an insufficient timescale separation (e.g., a single-timescale GDA) fails to converge to local minimax points. Our paper similarly presents that insufficient timescale separation (e.g., a single-timescale EG) fails to converge to local minimax points, but without the invertibility condition on $\nabla_{\boldsymbol{y}\boldsymbol{y}}^2 f$. So, our result already discusses the local behavior of the single-timescale EG, which states that it does not have convergence to local minimax points.

4. Extending to stochastic settings (Q2)

   Considering the attempts to explain stochastic gradient descent through the lens of stochastic differential equations (SDEs), it might be possible to extend our analyses to stochastic EG by blending it with SDEs; but we are not sure about the details of this idea at the moment. Still, it would certainly be an interesting direction for a future work.