- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The authors claim to prove a linear last-iterate convergence rate for optimistic and extragradient FTRL in multiplayer harmonic games, a class beyond two-player zero-sum games that includes games with nonlinear, non-monotone operators and multiple equilibria. The rate is proved for a family of regularizers including entropy, Tsallis and log-barrier, under a regularity condition the authors call mild, and the reached equilibrium is identified as the Minty-equality equilibrium closest to the initialization in a weighted Bregman divergence.
Critical strengths
The proofs look correct. The linear last-iterate convergence rate for optimistic and extragradient FTRL in harmonic games with linear operators seems novel.
Critical weaknesses
The paper presents its result for harmonic games under a regularity condition it calls mild. However, Assumption 5 requires the Jacobian of the stationarity map to be nonsingular at the reachable equilibrium, which is not true of general harmonic games (see the argument below). Therefore, the result as proven applies to a strict subset of harmonic games, and calling the condition mild misrepresents its scope.
The result does hold for harmonic games with linear operators, for which the authors prove that Assumption 5 holds (Proposition E.6). Even there the novelty is limited. Last-iterate convergence to the set of equilibria was already known for these games [1], so what is new is the rate and the characterization of the limit point. The rate itself is a modest generalization of [2], which already gives one for two-player zero-sum games with a unique interior equilibrium. What the paper adds to [2] is the multiplayer case, multiple equilibria, the extragradient variant and other regularizers.
Argument. The reachable equilibrium satisfies the Minty equality (Corollary E.5). Differentiating it twice there makes the weighted Jacobian of the operator skew-symmetric on the tangent space, so the Jacobian in Assumption 5 is similar to a skew-symmetric matrix and singular whenever the effective dual space has odd dimension. Harmonic games with an odd-dimensional effective dual space therefore violate Assumption 5 at every reachable equilibrium.
[1] Legacci et al. No-regret learning in harmonic games: Extrapolation in the face of conflicting interests. NeurIPS, 2024.
[2] Lazarsfeld et al. When and why is optimistic multiplicative weights slow? The geometry of energy dissipation. arXiv:2605.13242, 2026.
Questions for authors
- Can you characterize the broader class of nonlinear harmonic games for which Assumption 5 holds?
6 comments
Rebuttal part 2/3
Novelty and technical contributions
The rate itself is a modest generalization of [2], which already gives one for two-player zero-sum games with a unique interior equilibrium. What the paper adds to [2] is the multiplayer case, multiple equilibria, the extragradient variant and other regularizers.
Quantitative last-iterate convergence rates for optimistic FTRL in harmonic games were explicitly left open by [Legacci+24a, Section 5], who conjectured linear convergence and noted that establishing it would likely require different techniques. Our work establishes such rates with the following scope and technical contributions:
-
Harmonic game operators. The analysis of [Lazarsfeld+26] exploits the linear skew-symmetric operator representation of two-player zero-sum games to analyze OMWU. In contrast, our guarantees hold for both OFTRL and EGFTRL for the broader class of multiplayer harmonic games under the stated regularizer, stepsize conditions and the nondegeneracy condition in Assumption 5 (which holds automatically in the subclass of linear operators; see Proposition E.6). However, in general, harmonic games induce nonlinear operators (see Appendix B.4 for examples), and thus our analysis cannot rely on the linear skew-symmetric structure of zero-sum game operators. Instead, our analysis exploits the underlying weighted Minty equality structure (expression 6) that corresponds to the harmonic property. We also explicitly verify Assumption 5 for a nonlinear harmonic family with a nonconvex Nash equilibrium set in Appendix B.4.2.
-
Unified proof for both algorithms with more general regularizers. [Lazarsfeld+26] analyzes OMWU as an optimistic correction to a forward discretization of a skew-gradient flow, while [Wei+21] analyzes OMWU through a primal potential function. We first introduce symmetrized primal-dual coordinates that convert the weighted Minty equality into an unweighted identity (Proposition 5.1) while preserving the OFTRL/EGFTRL update structure and the conjugate relationship between the transformed regularizer and energy (Proposition 5.2). Under this change of basis, our proof then starts from the backward Euler discretization of the energy-conserving FTRL flow: implicit FTRL (IFTRL), whose updates dissipate energy. We show how both OFTRL and EGFTRL approximate this implicit scheme. The key technical step is to control their coupling errors in the local geometry induced by the energy Hessian, and to show that these errors remain dominated by the implicit dissipation (Proposition 5.5, Appendix H). This yields a common quantitative explanation of last-iterate convergence for both algorithms for a general class of regularizers, including entropy, Tsallis, and log-barrier regularization, potentially differing across players. The resulting two-sided dissipation bounds match up to absolute constants and do not require Assumption 5 (Lemma 5.4), separating the mechanism producing dissipation from the additional regularity used to obtain a linear rate. We also establish a contrasting quantitative divergence result for vanilla FTRL in linear harmonic games (Theorem 4.5).
-
Multiple equilibria, identification of the limit, and equilibrium selection. Unlike the unique interior equilibrium setting of [Lazarsfeld+26], harmonic games can have a continuum of Nash equilibria (Appendix B.4.1) and more generally nonconvex Nash equilibrium sets (Appendix B.4.2). The latter cannot occur in two-player zero-sum games. This multiplicity creates a technical challenge: an operator-domination inequality relative to one fixed equilibrium fails at any other interior equilibrium because the stationarity residual vanishes, but the Bregman divergence from the reference equilibrium remains positive. Our analysis overcomes this obstruction by exploiting the set reachable from initialization: under Assumption 5, we identify a unique equilibrium within this set and establish operator domination on its compact subsets, even though the game may have many equilibria elsewhere. More precisely, we prove that there is at most one reachable Minty equality point (Proposition E.2) and that, under Assumption 5, every reachable Nash equilibrium is such a point (Proposition E.4, Corollary E.5). These arguments identify the selected limit as the weighted Bregman projection of initialization onto the Minty-equality set (Lemma I.1). We then convert the local error bound into an operator domination inequality that holds uniformly over compact reachable sets (Proposition 5.6, Appendix J). This establishes both the equilibrium selected by the dynamics and a global linear rate to that equilibrium, without assuming global uniqueness of a Nash equilibrium.
Rebuttal part 3/3
Additional references mentioned:
[Azizian+2024]: “The rate of convergence of bregman proximal methods: Local geometry versus regularity versus sharpness.”, SIAM Journal on Optimization, 2024.
[Wei+2021]: “Linear last-iterate convergence in constrained saddle-point optimization.”, ICLR 2021
[Giannou+2022]: “On the convergence of policy gradient methods to Nash equilibria in general stochastic games.” NeurIPS 2022
Rebuttal part 1/3
We thank the reviewer for their feedback.
Reply to Q1
The verification of Assumption 5 in our paper is not limited to linear polymatrix games. Specifically, in Appendix B.4.2 we explicitly verify the condition for a nonlinear harmonic family whose Nash equilibrium set is nonconvex. We note that there exist other parameterized families of nonlinear harmonic games that also satisfy the condition. We will make these nonlinear examples more prominent.
As described in Remark 3.5, one key consequence of Assumption 5 is that it supplies a local linear error bound around reachable Nash equilibria. The use of local error bound assumptions and related regularity conditions to establish quantitative convergence rates has substantial precedent in the literature on learning in games and variational inequalities (see, e.g., [Azizian+2024, Assumption 2], [Wei+2021, Definition 1 and Theorem 8], and [Giannou+2022, Proposition 1]). In our proof, Proposition 5.6 converts the local error bound into an operator domination inequality that is uniform over compact reachable sets. Combining this inequality with the energy dissipation bounds yields the linear last iterate rate.
The energy dissipation bounds we prove in Lemma 5.4 do not require Assumption 5. Assumption 5 is important for establishing linear convergence rates. However, under weaker structural conditions, such as local Hölder error bounds around reachable Nash equilibria, the same dissipation framework can yield slower polynomial last-iterate convergence guarantees.