- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper investigates the Edge of Stability (EoS) phenomenon in minimax optimization, extending a line of research previously focused primarily on minimization problems. The authors propose a generalized characterization of EoS based on the stability regions of iterative optimization methods and the eigenvalues of the saddle-gradient Jacobian. The main contributions are threefold. First, the paper introduces a formulation of progressive sharpening and EoS for minimax optimization using the Scaled Relative Graph (SRG) framework. The authors derive approximate stability regions for Extragradient (EG) and Optimistic Gradient Descent Ascent (OGDA), allowing complex-valued Jacobian eigenvalues to be incorporated into the analysis. Second, the paper presents empirical evidence of EoS in several two-player zero-sum game settings, including a two-stage Rock-Paper-Scissors game, pursuit-evasion games, and neural optimal transport. The experiments reveal an interesting distinction between EG and OGDA: both methods can exhibit EoS when the dominant eigenvalues approach the stability boundary away from the real axis, whereas OGDA exhibits EoS and EG becomes unstable when the eigenvalues approach the boundary near the real axis. Third, the authors extend the self-stabilization framework of previouse to minimax optimization. They introduce a self-stabilization coefficient that characterizes whether the nonlinear dynamics push unstable eigenvalues back toward the stability region. Proposition 5.1 provides sufficient conditions for the sign of this coefficient, while Theorem 6.5 establishes an approximation of the original minimax dynamics by projected dynamics under several regularity and structural assumptions. Overall, the paper provides an interesting connection between spectral stability, nonlinear optimization dynamics, and the behavior of minimax algorithms near their stability boundaries.
Critical strengths
The authors proposed a novel and interesting research direction in this submission. The paper addresses a natural and important question concerning whether the EoS phenomenon extends beyond minimization to minimax optimization. Since minimax problems arise in adversarial learning, generative modeling, and game-theoretic learning, understanding their stability dynamics is relevant to the broader machine learning community. The authors also presented unified spectral characterization of stability. The use of SRG to characterize the stability regions of minimax algorithms provides a useful geometric perspective. In particular, allowing dominant Jacobian eigenvalues to be complex-valued captures rotational dynamics that are absent from the conventional Hessian-based analysis of minimization.
The theoretical contributions of this submission is nontrivial. The introduction of the self-stabilization coefficient , together with Proposition 5.1 and Theorem 6.5, represents a meaningful attempt to extend existing self-stabilization theory to minimax methods. The treatment of complex eigenvalues and the associated oscillatory effects makes the analysis substantially more involved than its minimization counterpart. Moreover, the distinction between EG and OGDA is interesting. One of the most compelling findings is that EG and OGDA can behave differently near the real-axis stability boundary, despite their similar convergence guarantees under standard assumptions. The experiments in Section 4.2 and the analysis in Section 5 offer a plausible explanation for this phenomenon.
Finally, the authors also conduct numerical experiments and there are consistency between the theoretical results and the empirical results from the experiments. The paper does more than establish abstract theoretical properties. The experimental observations are used to motivate the theoretical analysis, and the self-stabilization coefficient is evaluated numerically to explain the different behaviors of EG and OGDA.
Critical weaknesses
The major weakness of this submission include that the theoretical results rely on restrictive assumptions whose practical validity remains unclear. The main theoretical result, Theorem 6.5, requires Assumptions 6.1–6.4, including normality of the Jacobian, spectral separation, regularity conditions, and additional structural constraints on the nonlinear dynamics. In particular, Assumption 6.4 imposes approximate normality and quadratic alignment conditions that appear rather restrictive for general minimax optimization problems. Although the authors provide some empirical verification of normality, the paper acknowledges that certain assumptions are only approximately satisfied in the experiments. It would strengthen the theoretical contribution if the authors could identify important classes of minimax problems for which these assumptions can be rigorously verified. Without such examples, the applicability of Theorem 6.5 to practical minimax optimization remains somewhat uncertain.
Also, the stability regions for EG and OGDA are approximate rather than exact. In Section 3.2, the authors derive the stability regions and using approximations relating the eigenvalues of to those of . These approximations assume that the Jacobian varies only slightly during a single update. However, the EoS phenomenon occurs precisely near the stability boundary, where nonlinear effects and changes in the Jacobian may become important. It is therefore unclear whether the approximate stability boundaries accurately characterize the actual stability of EG and OGDA throughout the EoS regime. The authors should provide quantitative estimates for the approximation errors or establish sufficient conditions under which these approximate stability regions remain reliable. The relationship between the self-stabilization coefficient and actual EoS behavior is not fully established. The paper introduces and uses its sign to characterize self-stabilization. Although the experiments suggest that positive is associated with EoS and negative with instability, positivity alone does not appear sufficient to guarantee EoS without additional assumptions. For example, the simplified analysis in Section 6.1 relies on an argument that the oscillatory term involving has a smaller cumulative effect than the non-oscillatory term involving . The validity of this approximation depends on the rotational dynamics and deserves further explanation. The authors should clarify whether is merely a local indicator of negative feedback or can provide a sufficient condition for sustained EoS under suitable assumptions.
Moreover, the theoretical explanation for the difference between EG and OGDA is incomplete. One of the central empirical findings is that OGDA exhibits EoS near the real axis, whereas EG becomes unstable. Proposition 5.1 provides sufficient conditions for the sign of , and the authors use these conditions to explain the observed difference. However, the proposition does not provide a complete characterization of self-stabilization for either algorithm. Furthermore, the argument explaining the instability of EG relies on the behavior of the corresponding eigenvalue as it approaches zero. A more direct theoretical comparison between EG and OGDA would substantially strengthen the paper. For instance, it would be interesting to establish explicit conditions on the eigenvalues of under which EG fails to self-stabilize while OGDA retains the self-stabilization property.
Finally, the empirical evaluation could be more comprehensive. The experiments consider several interesting zero-sum game settings, but the empirical conclusions would benefit from a broader evaluation. In particular, the authors could investigate whether the observed EoS behavior persists across different neural network architectures, initialization schemes, and problem dimensions. It would also be useful to evaluate the sensitivity of the phenomenon to the learning rate and to the degree of non-normality of the Jacobian. Additionally, comparing the actual optimization trajectories with the projected dynamics predicted by Theorem 6.5 would provide more direct empirical validation of the main theoretical result.
Questions for authors
Can the authors provide a concrete, nontrivial class of minimax optimization problems for which Assumptions 6.1–6.4 can be rigorously verified? In particular, how restrictive are the approximate normality and quadratic alignment conditions?
3 comments
The rebuttal solved some of the issues. I have raised the score to weak acceptance.
We are glad that our rebuttal resolved your concerns, and we thank you for raising your score.
We thank the reviewer for their constructive feedback.
W2 and Q2. The normality assumptions are restrictive.
We agree that normality is a restrictive assumption. Our original statement in Section 5.2 that "DT remains approximately normal throughout training" referred to specific experiments, but may have given the impression that approximate normality generally holds in minimax training. We have clarified this point in the revised manuscript and provided additional experiments showing that EoS can also occur when DT is far from normal (see Figure 13 in Appendix C.2).
We emphasize that normality is imposed for our theoretical analysis, not for the occurrence of EoS itself. It enables the orthogonal spectral decomposition used in our extension of the self-stabilization framework of Damian et al. (2023). Extending the theory to non-normal settings remains an important direction for future work.
W1 and Q1. The other assumptions are restrictive.
We agree that some of our assumptions are restrictive even apart from normality. To address this concern, we have weakened the first condition in Assumption 6.4 and provide empirical evidence that our assumptions other than normality typically hold along the trajectories in our two-stage RPS and simple minimization experiments (see Figure 14 in Appendix D.3). This is analogous to the approach of Damian et al. (2023), who also empirically examined the validity of similar assumptions, including spectral separation and higher-order regularity conditions, in minimization.
W3. The DF-based stability regions for EG and OGDA are approximate.
We agree that the approximation relating DT and DF may become inaccurate in the EoS regime. We use the eigenvalues of DF(zt) to characterize progressive sharpening and EoS within a common framework, whereas our theoretical analysis directly uses the exact eigenvalues of DT without relying on this approximation.
To empirically assess the accuracy of this approximation, we have added plots of the eigenvalue trajectories of DT together with its exact spectral stability region Dη. These results show that the approximate DF-based boundaries accurately capture the observed behavior in our experiments (see Figures 6 and 7 in Appendix B). We thank the reviewer for helping us clarify this distinction.
W4. Is the cumulative effect of γ-term really small?
We thank the reviewer for pointing out that we did not fully explain this point in Section 6.1, although it was addressed in the proof in the appendix. When summed over iterations t, the γ-term approximately telescopes, reducing its cumulative contribution through cancellation (see Section 6.1 of the revised manuscript for details). Thus, under our assumptions, the γ-term is negligible, allowing β>0 to induce self-stabilization.
W5. Theoretical explanation between EG and OGDA is incomplete.
We thank the reviewer for pointing out that Section 5.2 of the original manuscript did not sufficiently explain the contrasting self-stabilization behavior of EG and OGDA. In the revised manuscript, we extend our discussion to OGDA and clarify the difference between their stability boundaries (see Section 5.2).
We agree that a complete characterization remains open. Proposition 5.1 provides sufficient conditions for the sign of β, helping explain the observed instability of EG near the real axis. However, unlike in minimization, the sign of β in minimax optimization depends on the relative locations of the dominant and non-dominant eigenvalues of DT. This makes a general characterization of self-stabilization for EG and OGDA substantially more challenging and motivates further theoretical investigation.
W6. Further empirical verification.
To demonstrate that EoS can occur in higher-dimensional problems and across different architectures, we trained a generative adversarial network (GAN) with a deep convolutional architecture (see Figure 8 in Appendix B). We are currently training a GAN with a different architecture (a Transformer-based GAN), as Reviewer Hayu also suggested. We also empirically validated our assumptions in two-stage RPS and simple minimization and compared the original dynamics with the projected and predicted dynamics for EG applied to the two-stage RPS game in the regime where all our assumptions hold (see Figure 14 in Appendix D.3). For OGDA, DT is far from normal in these experiments, violating the normality assumption of our theory. Accordingly, the orthogonally projected dynamics do not closely track the original trajectories, which suggests that non-orthogonal projections may be worth investigating. Given our focus on GAN experiments and theoretical validation during the rebuttal period, we plan to further investigate the effects of architectures, initializations, and problem dimensions on EoS behavior and our theoretical assumptions afterward.