- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper considers the bilinear skew-symmetric matrix games where each policy is parameterized by a softmax representation. In this game, the authors study the continuous-time Euclidean extragradient applied directly in softmax-logit space, and provide a set of results on convergence, boundary behavior, and equilibrium selection of extragradient flow in the original bilinear game. In particular, the paper identifies two cases (interior NE, ‘flat dominance’) where the direct extragradient achieves global convergence in different senses. The implicit bias characterizes the extragradient flow, including a theorem saying the trajectory almost goes to pure NE instead of mixed Nash equilibrium assuming ‘flat dominance’ and the point-wise convergence in the policy space.
Critical strengths
- The paper studies an important and interesting problem, given the major applications in neural networks and the nonconvex-nonconcave properties of the logit space.
- The paper provides a set of results on boundary behaviors and equilibrium selection, which seems to be missing in this setting. These results look interesting to me.
Critical weaknesses
- The scope of this paper is kind of limited compared to previous work. Even though the specific setting: skew-symmetric matrix games, softmax representation are well-motivated, this setup is more restrictive than, e.g., Vlatakis-Gkaragkounis et al. (2021).
- The global convergence is meaningful but not very new, especially considering the specific class of games considered in the paper and the two required conditions.
- (minor) “Nash set”, “Nash convergence”, “Nash face” were used without clear definitions.
Questions for authors
- Are there any necessary conditions under which the dynamics converges? It seems like the interior NE and flat dominance are not necessary for convergence to the set of NE.
- What is the benefit of applying the Euclidean extragradient directly in the logit space, compared to using natural gradient algorithms which correspond to OMWU and have better convergence properties?
3 comments
W3. Terminology
We revised the terminology and marked the changes in blue. We explicitly identified as the Nash set in Section 2. We replaced "Nash convergence" with "convergence in the Nash sense". Under flat dominance, the Nash face coincides with the Nash set (Proposition K.2). We replaced "Nash face" with "Nash set" or rephrased it.
Q1. Necessary conditions for convergence
It is true that neither condition is necessary; Proposition J.1 implies that convergence in the Nash sense can happen in the absence of both conditions. However, the necessary conditions for convergence are expected to be highly nontrivial to characterize, and initialization should be taken into account. Indeed, Proposition J.2 shows that convergence fails by simply changing the initial values even under the same game. The observation that convergence depends on initialization is somewhat expected, since the game is nonconvex-nonconcave due to the softmax parameterization.
Q2. Benefits of applying EG in logit space
We do not claim that Euclidean extragradient (EG) applied directly in logit space offers an algorithmic advantage over natural-gradient methods such as OMWU. Rather, our motivation is to understand the convergence behavior and implicit bias of a standard first-order minimax method applied directly to softmax-parameterized models. Indeed, softmax parametrization is widely used in machine learning, where gradient-based optimization methods are commonly applied directly in the parameter space (see our Introduction for relevant references). EG is a natural choice in this setting, given its established role in mitigating the instability caused by rotational dynamics in minimax optimization.
We believe that our setting provides a useful theoretical testbed for understanding several challenges arising in modern minimax optimization. Although the underlying game is bilinear, softmax parameterization induces a nonconvex-nonconcave problem in logit space, where standard convex-concave convergence guarantees do not directly apply. Moreover, boundary equilibria can only be approached through diverging logits, and the Euclidean dynamics do not explicitly exploit the hidden bilinear structure. Consequently, even establishing convergence, let alone characterizing the limiting policy, is nontrivial.
Our contribution is to show that, despite these difficulties, the high-resolution EG flow admits a detailed theoretical characterization. In particular, we establish global convergence under two structural conditions, derive sharp convergence rates to boundary equilibria, and characterize initialization-dependent equilibrium selection. These results provide insight into how softmax parameterization shapes the behavior of a standard minimax optimization method, rather than establishing its superiority over natural-gradient algorithms.
I thank the authors for the clarifications and for answering my questions. I think this work indicates some interesing future directions, e.g., studying learning dynamics in the logit space, studying more general minimax optimization instances. The results in this paper are meaningful, although I think simpler (alternating) gradient-descent-ascent algorithm might be more standard first-order minimax method in practice. I lean towards acceptance.
We sincerely thank the reviewer for their careful review, and for recognizing the significance of our research question and theoretical results. We address their points below.
W1. Limited scope of the paper
We believe there is a misunderstanding here: Our setup is not subsumed by [1]; there are two distinctions between the two settings.
First, the parameterizations differ. [1] analyzes the class of games minθ∈RNmaxϕ∈RML(F(θ),G(ϕ)), where each coordinate of F,G is controlled by disjoint sets of variables. Specifically, F:RN→Rn is computed as F(θ)=[f1(θ1)…fn(θn)]⊤ where θ=[θ1…θn]⊤ is partitioned into n groups and fi are C2 scalar-valued functions. G:RM→Rm is similarly defined for disjoint ϕ1,…,ϕm and g1,…,gm. In contrast, our softmax parameterization couples every output to all logits through the shared normalization; it does not fall into this class of games.
Second, the convergence assumptions differ. The convergence guarantees in [1] require a strict convex-concave property of the utility L. Namely, L is strictly convex-concave if it is convex-concave, and either L(⋅,y) is strictly convex or L(x,⋅) is strictly concave for every (x,y). When this strictness is absent, [1] introduces L2 regularization and obtains convergence for a perturbed game. In contrast, we establish convergence and implicit-bias results for unregularized bilinear zero-sum games, whose utility is not strictly convex-concave.
We have further clarified these distinctions in the revised manuscript.
[1] EV Vlatakis-Gkaragkounis et al. Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent. In NeurIPS 2021
W2. Novelty of global convergence
Thank you for raising this. Our two global convergence results use alternative sufficient conditions. When the game has an interior equilibrium, S2P-EG-Flow converges in logit space for every γ>0 (Theorem 3.1). Under flat dominance and the stated bound on γ, it converges in the Nash sense (Theorem 3.2).
Each assumption imposes structure on the underlying game, but the objective in the logits remains nonconvex–nonconcave. This places the logit dynamics outside the scope of standard convex–concave guarantees. A PŁ-based argument would require establishing a suitable inequality in the logits, and entropic regularization would change the objective. The softmax parameterization also gives the game a hidden bilinear structure. S2P-EG-Flow models Euclidean extragradient applied directly in the logits, so prior analyses that exploit this hidden structure by changing the update geometry concern a different flow.
Our technical contribution is to establish global convergence for the unregularized Euclidean logit dynamics under these structural assumptions, despite these difficulties. We found it surprising that this flow admits an equilibrium-anchored Lyapunov potential. We believe that our proof flow, combining conservation of the logit sum induced by softmax with dynamical-systems tools such as LaSalle’s invariance principle, may also help analyze related nonconvex–nonconcave problems.
Extending the boundary convergence guarantee beyond flat dominance would strengthen the results, and we leave this to future work. Our Remark 1 shows that even convergence in the Nash sense can fail in a game with only boundary equilibria, so some restriction on the game class is needed for a global guarantee.