acceptodds
Under review as a conference paper at ICLR 2027

Edge of Stability Occurs in Minimax Optimization

Abstract

The Edge of Stability (EoS) phenomenon is widely observed in minimization, where gradient methods continue to decrease the loss even while remaining near their stability thresholds, a behavior associated with a self-stabilization mechanism. Yet an analogous phenomenon has not been clearly identified in minimax optimization. In this paper, we formulate EoS for minimax optimization, demonstrate that it indeed occurs, and characterize the self-stabilization mechanism underlying it. We first define EoS for minimax optimization in terms of possibly complex dominant Jacobian eigenvalues reaching the boundary of the stability region. Using two-player zero-sum games, we observe minimax EoS for both Extragradient (EG) and Optimistic Gradient Descent Ascent (OGDA). However, when the dominant eigenvalues lie near the real axis, OGDA still exhibits EoS whereas EG does not. Finally, we generalize the self-stabilization mechanism to minimax methods and show how it explains these behaviors.

Primary area:
optimization
Keywords:
Minimax optimization, Gradient methods, Edge of Stability, Self-stabilization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_YpGzOpenReview ↗
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 β(z)\beta(z), 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 Pη\mathcal P_\eta and Bη\mathcal B_\eta using approximations relating the eigenvalues of DTDT to those of DFDF. 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 β(z)=∇ϕ(z)⋅D2T(z)[u(z),u(z)‾]\beta(z)=\nabla\phi(z)\cdot D^2T(z)[u(z),\overline{u(z)}] and uses its sign to characterize self-stabilization. Although the experiments suggest that positive β\beta is associated with EoS and negative β\beta 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 γ\gamma has a smaller cumulative effect than the non-oscillatory term involving β\beta. The validity of this approximation depends on the rotational dynamics and deserves further explanation. The authors should clarify whether β>0\beta>0 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 β\beta, 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 Λ\Lambda 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 DFDF 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

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 "DTDT 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 DTDT 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 DFDF-based stability regions for EG and OGDA are approximate.

    We agree that the approximation relating DTDT and DFDF may become inaccurate in the EoS regime. We use the eigenvalues of DF(zt)DF(z_t) to characterize progressive sharpening and EoS within a common framework, whereas our theoretical analysis directly uses the exact eigenvalues of DTDT without relying on this approximation.

    To empirically assess the accuracy of this approximation, we have added plots of the eigenvalue trajectories of DTDT together with its exact spectral stability region Dη\mathcal D_\eta. These results show that the approximate DFDF-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 γ\gamma-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 tt, the γ\gamma-term approximately telescopes, reducing its cumulative contribution through cancellation (see Section 6.1 of the revised manuscript for details). Thus, under our assumptions, the γ\gamma-term is negligible, allowing β>0\beta > 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 β\beta, helping explain the observed instability of EG near the real axis. However, unlike in minimization, the sign of β\beta in minimax optimization depends on the relative locations of the dominant and non-dominant eigenvalues of DTDT. 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, DTDT 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.

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.

Reviewer_HayuOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigated the Edge of Stability (EoS) in minimax optimization problems, which is an interesting problem. The authors firstly define the notion of EoS for minimax optimization problems via nonexpansiveness of operators and Scaled Relative Graph. Then the author proved that EoS exhibits for both OGDA and Extragradient method in several simple two-player zero-sum games. Besides, the authors showed that when the dominant eigenvalue S(zt)S(z_t) closes to the real axis, OGDA exhibits EoS, while EG does not.

Critical strengths

The phenomenon investigated in this paper is very interesting. The separation behavior between OGDA and EG whenever closing the real axis is also interesting.

Critical weaknesses

The main weaknesses of this paper is that this paper only investigated several quite simple and special games, like Rocker-Paper-Scissors Game, which is very restrictive to adapt to realistic setting. The authors should investigate the general and realistic settings.

Besides, the notion of EoS including the Scaled Relative Graph need to be described more detailed, since the current description makes the reviewer less intuitive.

Lastly, the experiments implemented in this paper are all toys. The authors should make more large-scale model, like transformer GANs in CelebA datasets.

Considering the above weaknesses, I gave weak reject evaluation. If the authors can completely resolve the weaknesses, I can increase the scores to weak accept, and even clear accept.

Questions for authors

Please respond to the above weaknesses.

3 comments

We thank the reviewer for their constructive feedback.

  • W1. Limited experiments.

    While our original experiments included neural optimal transport and other neural-network-parameterized games, we agree that experiments in more realistic settings would strengthen our empirical findings. Following the reviewer's suggestion, we trained a DCGAN on CIFAR-10 using EG and OGDA. We observed progressive sharpening (PS) along the real axis, where OGDA exhibited EoS while EG became unstable (see Figure 8 in Appendix B). These results demonstrate that the contrasting stability behaviors of EG and OGDA also arise in GAN training.

    We are also conducting experiments with a Transformer-based GAN on CelebA, as specifically suggested by the reviewer, and will share the results during the discussion period if available. We thank the reviewer for this suggestion, which has helped strengthen our empirical evaluation.

  • W2. The notion of EoS, including the Scaled Relative Graph (SRG), is less intuitive.

    We agree that our original explanation of the SRG and its connection to EoS could be clearer. In the revised manuscript, we explain how the SRG geometrically represents nonexpansiveness through the unit disk and how this characterization motivates the stability regions used to define EoS in minimax optimization.

Thank you for your response. My concerns was partially addressed. I am waiting for the remaining Transformer-based GAN experiments on CelebA dataset. I will maintain/increase/significantly increase my assessment according to this experiment and discussion on other reviewers.

Thank you for your response. We have added preliminary results for a Transformer-based GAN trained on CelebA (Figure 8 in Appendix B). Consistent with our DCGAN experiments, the estimated dominant eigenvalues exhibit progressive sharpening near the real axis for both EG and OGDA. However, both methods remain stable over the current training period, and the difference between them is not yet pronounced.

Unlike our previous experiments, the estimated eigenvalues extend considerably beyond the stability boundaries. This discrepancy may be due to the use of stochastic minibatches for eigenvalue estimation, which was necessary due to computational constraints. Given the limited rebuttal period, we could not verify this through exact eigenvalue computation. We will continue training and investigate this discrepancy further in the final manuscript.

Reviewer_kp1LOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the Edge of stability phenomenon under the minimax optimization setting. They observe minimax EoS for both Extragradient (EG) and Optimistic Gradient Descent Ascent (OGDA) and introduce a self-stabilization property for minimax methods. Also, when the dominant eigenvalues of Jacobian lie near the real axis, OGDA still exhibits EoS whereas EG does not.

Critical strengths
  • The paper model the minimax problem under the complex regime, and show the analysis under the complex spectra which cannot be represented adequately by the largest real Hessian eigenvalue. And the projected-trajectory approximation states what can be established under specified spectral and regularity conditions.
  • The experiments and plots demonstrate that the phenomenon clearly.
Critical weaknesses
  • The assumptions are restriictive, say we need normality, spectral separation, positive self-stabilization coefficients, and higher-order bounds make the result rather limited. Also, as the authors pointed out, eigenvalue trajectories provide evidence of dynamics near a spectral stability boundary. However, it could not be directly interpreted as a nonexpansiveness boundary for the actual updates.
Questions for authors
  • Any implicit regulaization effect from the minimax optimization? Or say what is the practical consequences for this eos effect, like any preferable learning-rate choice?
  • Does the conclusion persist in nonnormal games and under multiple interacting boundary eigenvalues?
1 comment

We thank the reviewer for their constructive feedback.

  • Q2. Does Edge of Stability (EoS) occur with non-normal Jacobians and multiple eigenvalues near the stability boundary?

    We thank the reviewer for raising this important point. We acknowledge that our original presentation did not clearly distinguish the empirical observations from the theoretical analysis. We emphasize that the assumptions in Section 6, including normality and spectral separation, are imposed for our theoretical analysis, but not for the empirical occurrence of EoS. In particular, spectral separation is also assumed in Damian et al. (2023). In the revised manuscript, we clarify this distinction and provide additional evidence that EoS also occurs with non-normal Jacobians (see Figure 13 in Appendix C.2) and when multiple eigenvalues approach the stability boundary (see Figure 10 in Appendix B). Extending our theoretical guarantees to these settings remains an interesting direction for future work.

  • W1. The assumptions for the theoretical result are restrictive.

    We agree that normality is a restrictive assumption, but it enables the orthogonal spectral decomposition of DTDT used in our extension of the self-stabilization framework of Damian et al. (2023).

    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 bounds, in minimization.

  • W2. The relationship between spectral stability and nonexpansiveness.

    We understand the reviewer's concern, and agree that our original presentation could have clarified this distinction. Although eigenvalues lying within the spectral stability region do not necessarily guarantee nonexpansiveness, an eigenvalue lying outside this region implies that the update operator fails to be nonexpansive. Thus, the spectral stability boundary remains meaningful even without normality. Our experiments further support its relevance to EoS behavior.

  • Q1. Is there any implicit regularization effect and practical consequence from EoS?

    We thank the reviewer for raising this interesting question. In minimization, Damian et al. (2023) showed that gradient descent with large learning rates exhibits an implicit bias toward flatter regions, which is often associated with better generalization. Our results reveal an analogous implicit bias toward flatter regions when EG and OGDA exhibit EoS at large learning rates.

    Whether this implicit effect also leads to better generalization remains an interesting open question, and our work provides a starting point for investigating this connection.

    Another practical implication is that OGDA can be preferable to EG in minimax training when progressive sharpening occurs near the real axis.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.