acceptodds
Under review as a conference paper at ICLR 2027

AltGDA Achieves Global Ergodic Convergence in Matrix Games

Abstract

Alternating gradient descent-ascent (AltGDA) is a simple and practically effective method for solving finite two-player zero-sum matrix games. However, the theory of AltGDA remains limited: existing results either apply only to unconstrained settings or require restrictive assumptions on the equilibrium in constrained settings. We show that AltGDA converges globally at an ergodic rate in every finite two-player zero-sum matrix game. Unlike prior results, our guarantee holds for every initialization and every horizon : the uniform averages of the AltGDA iterates satisfy an duality-gap bound. Our proof is inspired by numerical results obtained using a novel performance estimation programming (PEP) framework for Lyapunov function search over compact convex sets. Additionally, we provide simple counterexamples showing that the last-iterate duality gap of AltGDA does not converge to zero. This justifies why averaging of iterates is indeed necessary to achieve an rate. We have formalized and machine-checked our global ergodic convergence result in Lean 4.

Primary area:
optimization
Keywords:
Two-player Zero-sum Games, Gradient Descent Ascent, Alternation, Convergence

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_JGLcOpenReview ↗
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 O(1/T)\mathcal{O}(1/T). 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
  1. 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.

  2. Theorem 2 does not seem to be a strong result. The bound holds when "the Lyapunov LMI of Appendix B is exactly feasible for (h,η)(h,\eta) -- can the authors clarify when this is true and whether the condition can be easily verified given an arbitrary problem?

Questions for authors
  1. 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?

  2. 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
AuthorsOpenReview ↗

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.

  1. 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.

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 BtB_t accounts for movement outside the equilibrium support. Combining the energy balance (11) with the residual estimate (14) shows that the corrected energy Vt+BtV_t+B_t decreases by at least Dt/2\mathscr{D}_t/2 per step, where Dt\mathscr{D}_t 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.

  1. Theorem 2 does not seem to be a strong result. The bound holds when "the Lyapunov LMI of Appendix B is exactly feasible for (h,η)(h,\eta) -- can the authors clarify when this is true and whether the condition can be easily verified given an arbitrary problem?

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)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,η)(h,\eta).

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}$.
AuthorsOpenReview ↗

Author Rebuttals

  1. 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 O(1/T)O(1/T) 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.

  1. 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.

Reviewer_q8wsOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies alternating gradient descent–ascent (AltGDA), in which the two players update their strategies sequentially. The authors establish a global O(1/T)O(1/T) ergodic convergence rate for AltGDA in finite two-player zero-sum matrix games, without imposing restrictions on the initialization or the existence of an interior Nash equilibrium. The proof is motivated by a performance estimation programming (PEP) framework for discovering Lyapunov functions. The authors also provide counterexamples demonstrating that last-iterate convergence is not guaranteed.

Critical strengths

The global O(1/T)O(1/T) ergodic convergence guarantee is a significant theoretical contribution, as it removes the restrictive assumptions required by previous results. Moreover, the novel decomposition used in the proof, particularly for handling the boundary effects of simplex projections, is technically interesting and may be useful for analyzing other game-theoretic learning dynamics.

Critical weaknesses

A main limitation is that the stepsize condition in Theorem 1 depends on the Goldman–Tucker separation constant δ\delta, which may not be known in advance. Consequently, it is unclear how to select a stepsize that satisfies the theorem's conditions without prior knowledge of the equilibrium structure. This limits the practical applicability of the convergence guarantee.

Questions for authors

Is there a practical way to obtain a lower bound on the Goldman–Tucker separation constant δ\delta before running AltGDA? Alternatively, can the authors suggest a stepsize selection strategy that does not require knowing δ\delta in advance? Clarifying this would help establish how the theoretical convergence guarantee can be applied in practice.

2 comments
AuthorsOpenReview ↗

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.

A main limitation is that the stepsize condition in Theorem 1 depends on the Goldman–Tucker separation constant , which may not be known in advance. Consequently, it is unclear how to select a stepsize that satisfies the theorem's conditions without prior knowledge of the equilibrium structure.

Is there a practical way to obtain a lower bound on the Goldman–Tucker separation constant δ\delta before running AltGDA? Alternatively, can the authors suggest a stepsize selection strategy that does not require knowing δ\delta in advance? Clarifying this would help establish how the theoretical convergence guarantee can be applied in practice.

We thank the reviewer for their comments on this point. We appreciate these suggestions.

Yes, we can provide a stepsize rule that can be implemented without prior knowledge of the equilibrium structure. One approach to doing so was proposed by Nan et al. (2026). Similar to their analysis, our proof provides an upper bound on the residual sum and thus allows us to use the same stepsize update rule as theirs. This leads to an algorithm that updates the stepsize using only online feedback, without any information that is unknown in advance.

We have added Subsection 4.3 to the revised version of the paper to include the AltGDA algorithm with this stepsize selection rule.

Thank you for your response and for adding the adaptive stepsize extension. This effectively addresses my main concern. I have raised my score accordingly.

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

The paper studies the convergence of Alternating Gradient Descent Ascent (AltGDA) in zero-sum bilinear games. For the notion of ergodic convergence, a bound of O(1/T)O(1/T) in the duality gap is established via both an analytical proof and a performance estimation programming (PEP) framework. For the notion of last-iterate convergence, the authors show that the algorithm’s duality gap remains away from zero. For the main proof of the paper, the authors define an energy function as a progress measure and introduce a dissipation term that depends on how the algorithm’s iterates distribute their mass among strategies on and off the equilibrium support. The proof then can be broken down into three parts: relate the notions together, which requires also a residual term, relate this residual term to the dissipation to prove a bound on the former and, finally, use an existing lemma that takes advantage of the summability of the residuals. The second result revolves around the PEP framework. The authors show the same rate as in the main result, under a feasibility assumption for the formulated program. Interestingly, the same framework is also exploited to derive counterexamples on last-iterate duality.

Critical strengths

The paper settles the problem of the convergence of AltGDA completely; prior work (accepted in last year’s ICLR) has made substantial progress on this front but a few assumptions were still needed.

Critical weaknesses

None

Questions for authors
  1. If my understanding is correct, the energy function the authors define is not entirely novel but an adaptation of the energy function in Nan et al. , with the two functions coinciding (up to a constant term that depends on the value of the game) when the equilibrium is interior. I still think the function has merit as it is more refined than the aforementioned one but the authors should briefly mention the original definition. Similarly, I think that the residual term is the same as in the prior work. Could the authors expand on the comparisons?

  2. In a recent work by Lazarsfeld et al. the term dissipation is also used. The problem there is the convergence of OMWU and the two dissipation terms are, if I am not mistaken, used differently in the proofs. Still, I think you should briefly mention this work and compare the two namesake terms.

Lazarsfeld, John, et al. "When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation." arXiv preprint arXiv:2605.13242 (2026).

1 comment
AuthorsOpenReview ↗

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.

If my understanding is correct, the energy function the authors define is not entirely novel but an adaptation of the energy function in Nan et al. , with the two functions coinciding (up to a constant term that depends on the value of the game) when the equilibrium is interior. I still think the function has merit as it is more refined than the aforementioned one but the authors should briefly mention the original definition. Similarly, I think that the residual term is the same as in the prior work. Could the authors expand on the comparisons?

We thank the reviewer for bringing up this point.

The reviewer has correctly pointed out that the energy functions and the residual terms are associated with Nan et al. and the energy function used in our paper coincides with the one used in their local convergence rate proof. We also agree with the reviewer that our energy function VtV_t is more refined than the first energy function introduced in Nan et al., since our function explicitly captures the potential between the current iterate and a strictly complementary Nash equilibrium and shrinks to zero at the equilibrium. We also found that VtV_t fits better into our proof than the other energy function. In the revised manuscript we have mentioned this connection explicitly as suggested by the reviewer.

One of our contributions related to this point is that we identify an equivalent identity for the residual terms, as shown in Eq. (10), and an explicit relation among the energy function, the dissipation term, and the residual term, as shown in Eq. (11), which potentially captures the fundamental relationship between the behavior of the dynamics and the convergence properties.

In a recent work by Lazarsfeld et al. the term dissipation is also used. The problem there is the convergence of OMWU and the two dissipation terms are, if I am not mistaken, used differently in the proofs. Still, I think you should briefly mention this work and compare the two namesake terms.

We thank the reviewer for bringing this interesting work to our attention.

Yes, we think the dissipation terms in our work and in Lazarsfeld et al. are related but play different roles in the respective proofs. In particular, based on our understanding, at least in the presence of an interior Nash equilibrium, both dissipation terms capture some mismatch between the current iterate and an interior Nash equilibrium in the primal space: our dissipation scales with the magnitude of the mismatches of the supports, while dissipation in Lazarsfeld et al. corresponds the payoff variance in the primal space---both terms can be large when the current iterate is substantially away from equilibrium and become small near an interior equilibrium, although they capture different aspects of the dynamics.

We also observe that the roles of these dissipation terms are different, although the proofs share some intermediate steps. In particular, both proofs establish that the sums of the dissipation terms are finite. In Lazarsfeld et al., in the presence of an interior NE, summability implies that the dissipation term converges to zero asymptotically, which means that the current iterate converges to the NE, as we mentioned above. In our analysis, we connect the dissipation term and the residual term using a key energy-dissipation-residual identity, which translates the summability of the dissipation term into the summability of the residual term, thus yielding the O(1/T)O(1/T) convergence rate. Here, our dissipation term can be zero even if the current iterate is not exactly at equilibrium.

In the revised version of our paper, we have cited and discussed this work, and the role of the dissipation term in both work.

Comments on the paper

1 comment

We sincerely thank all PCs, SACs, ACs, and reviewers for their time and efforts. We deeply appreciate the detailed, positive, and invaluable feedback provided by the reviewers.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.