- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper analyzes alternating gradient descent-ascent for two-player zero-sum matrix games and shows that the average iterate of the algorithm globally converges at a rate of . The authors further provide counterexamples showing that the last iterate does not necessarily converge.
Critical strengths
The paper establishes a significant result. It shows the convergence of AltGDA in the general setting without assuming the existence of an interior equilibrium. The complicating factor compared to Nan et al. (2026) is the collisions of the projection step with the simplex boundary. The authors address this by carefully characterizing the projection residual and showing that it is smaller relative to the dissipation term over the horizon. This seems to be a novel analytical design to my knowledge.
Critical weaknesses
-
While I do not see major issues in the paper, I find parts of the paper difficult to read. Particularly, the PEP framework for Lyapunov function search section is rather unclear for an audience unfamiliar with PEP. The authors should consider explaining in a more plain language how exactly the PEP framework contributes to the Lyapunov analysis.
-
Theorem 2 does not seem to be a strong result. The bound holds when "the Lyapunov LMI of Appendix B is exactly feasible for -- can the authors clarify when this is true and whether the condition can be easily verified given an arbitrary problem?
Questions for authors
-
How does the results generalize and help with the analysis with AltGDA in the stochastic setting? Also empirically does AltGDA outperform SimGDA when the update directions have a stochastic noise term?
-
It is worth noting that besides extragradient and optimistic gradient methods, another line of work obtains last-iterate convergence in two-player games by adding a regularization with decaying strength, including Koshal et al., 2012, Zeng et al., 2022. Both of these works study more general settings. Koshal et al., 2012 considers stochastic VIs that abstract the bi-linear problem as a special case, and Zeng et al., 2022 is on two-player zero-sum stochastic games.
References
Koshal, J., Nedic, A. and Shanbhag, U.V., 2012. Regularized iterative stochastic approximation methods for stochastic variational inequality problems. IEEE Transactions on Automatic Control, 58(3), pp.594-609.
Zeng, S., Doan, T. and Romberg, J., 2022. Regularized gradient descent ascent for two-player zero-sum Markov games. Advances in Neural Information Processing Systems, 35, pp.34546-34558.
2 comments
Author Rebuttals
- How does the results generalize and help with the analysis with AltGDA in the stochastic setting? Also empirically does AltGDA outperform SimGDA when the update directions have a stochastic noise term?
We thank the reviewer for this insightful question.
To generalize our analysis to the stochastic setting, a proof would have to control how errors propagate through the two updates. This would likely require controlling the variance of the gradients using additional techniques, such as noise-aware stepsizes and variance reduction, while keeping the stepsize bounded away from zero to preserve the convergence rate. We leave the analysis of the stochastic setting as an interesting direction for future work.
The PEP framework can also potentially be extended to the stochastic setting: a finite-support oracle would permit a PEP extension that explicitly averages over its possible outcomes, as in this work.
Empirically, we implemented preliminary stochastic gradient feedback experiments. In our preliminary experiments, AltGDA still preserves the convergence rate with small noises. In the regime of large noise, neither AltGDA nor SimGDA converges with constant stepsizes. We have added the additional experiments to Appendix D of the revised paper. We leave a theoretical analysis and a comprehensive empirical study of stochastic AltGDA as directions for future work.
- It is worth noting that besides extragradient and optimistic gradient methods, another line of work obtains last-iterate convergence in two-player games by adding a regularization with decaying strength, including Koshal et al., 2012, Zeng et al., 2022. Both of these works study more general settings. Koshal et al., 2012 considers stochastic VIs that abstract the bi-linear problem as a special case, and Zeng et al., 2022 is on two-player zero-sum stochastic games.
We thank the reviewer for pointing us to these papers.
We added both to the revised version of the paper.
Author Rebuttals
We thank the reviewer for their supportive comments and insightful suggestions. We appreciate them. We respond to each point to address the questions raised.
We thank the reviewer for the question.
We agree that Section 5 was difficult to follow for readers unfamiliar with PEP. We have revised its opening to explain how PEP guided our search for a proof.
Dual multipliers give weights for combining inequalities that hold at every iteration. Our search chooses these weights together with a quadratic potential. It asks whether the decrease in that potential over one update bounds the payoff difference against any fixed pair of strategies. Summing over iterations cancels the intermediate potentials. Dividing by the number of iterations and maximizing over the comparison pair then bounds the duality gap of the averaged strategies.
We also identify the step this search guided in the proof of Theorem 1. In Section 4.2, the bounded correction Bt accounts for movement outside the equilibrium support. Combining the energy balance (11) with the residual estimate (14) shows that the corrected energy Vt+Bt decreases by at least Dt/2 per step, where Dt is the dissipation. Since the corrected energy is bounded below, summing this inequality bounds the total dissipation. Summing (14) then bounds the accumulated projection residual used in the averaged-gap proof.
We thank the reviewer for the question.
Theorem 1, our main convergence result for finite matrix games, has an independent analytical proof. The role of Theorem 2, while conditional, gives a sufficient condition for an O(1/T) ergodic rate and guided us in constructing the proof to Theorem 1 (as described in our previous response). Please note that, we have only presented approximately feasible numeerical solution to the Lyapunov LMI and do not claim to establish exact feasibility for any particular pair (h,η).
We now explain, why given an arbitrary problem, establishing an exact solution to an LMI is a nontrivial and challenging problem. First, finding an exact certificate to an LMI can be difficult even when all the LMI data are rational. Consider the small LMI with two constraints
\quad \begin{pmatrix}2&x \\\\ x&1\end{pmatrix}\\succeq0.$$ The first matrix has eigenvalues $x\pm\sqrt{2}$, so minimizing $x$ under the first constraint alone gives the exact optimum $\sqrt{2}$. The second constraint imposes $x^2\le2$. Together they make $x=\sqrt{2}$ the only feasible solution. A floating-point solver such as MOSEK or Clarabel can approximate this value to high accuracy, e.g., 1.4142... but cannot deduce the actual solution $\sqrt{2}$. So no matter how much we tune the precision, a MOSEK (or any other flotating point solver) can only give us a solution that is *approximately feasible* but *not exactly feasible* because every finite decimal approximation of $\sqrt{2}$ violates one of the two constraints by a small but strictly nonzero amount. While symbolic tools such as SPECTRA (https://arxiv.org/pdf/1611.01947) can represent such algebraic solutions to LMIs exactly, they work for only very small LMIs. For our problem, at $h=2$, our LMI already has **1,389 scalar decision variables and 12 positive-semidefinite blocks** that is well outside the reach of symbolic tools such as SPECTRA. Hence, the only practical choice for us is to use MOSEK to search for candidate Lyapunov functions at this scale. At $h=2,\eta=0.1$, for example, the candidate in Figure 1(b) passed all four numerical tests, with a maximum equality residual of $1.35\times10^{-8}$ against a tolerance of $10^{-6}$.