On the $O(1/T)$ Convergence of Alternating Gradient Descent–Ascent in Bilinear Games
Authors: Tianlong Nan
Shuvomoy Das Gupta
Garud Iyengar
Christian Kroer
Venue: ICLR 2026 Poster (2026)
Keywords: Two-player zero-sum games
Alternating gradient descent-ascent
Performance estimation programming
Primary area: optimization
TL;DR: We show O(1/T) convergence rates of alternating gradient descent-ascent in bilinear two-player zero-sum games, with an interior Nash equilibrium or in a local region

Abstract: We study the alternating gradient descent-ascent (AltGDA) algorithm in two-player zero-sum games. 
    Alternating methods, where players take turns to update their strategies, have long been recognized as simple and practical approaches for learning in games, exhibiting much better numerical performance than their simultaneous counterparts.
    However, our theoretical understanding of alternating algorithms remains limited, and results are mostly restricted to the unconstrained setting. 
    We show that for two-player zero-sum games that admit an interior Nash equilibrium, AltGDA converges at an $O(1/T)$ ergodic convergence rate when employing a small constant stepsize. This is the first result showing that alternation improves over the simultaneous counterpart of GDA in the constrained setting.
    For games without an interior equilibrium, we show an $O(1/T)$ local convergence rate with a constant stepsize that is independent of any game-specific constants. 
    In a more general setting, we develop a performance estimation programming (PEP) framework to jointly optimize the AltGDA stepsize along with its worst-case convergence rate. 
    The PEP results indicate that AltGDA may achieve an $O(1/T)$ convergence rate for a finite horizon $T$, whereas its simultaneous counterpart appears limited to an $O(1/\sqrt{T})$ rate.

Published as a conference paper at ICLR 2026
ON THE O(1/T) CONVERGENCE OF ALTERNATING GRADIENT DESCENT-ASCENT IN BILINEAR GAMES
Tianlong Nan
Shuvomoy Das Gupta CMOR Department, Rice University Houston, TX 77005, USA sd1 sd158grice.es edu
IEOR Department, Columbia University New York, NY 10027, USA
tianlong. nan. columbio edu
Garud Tyengar
Christian Kroer
IEOR Department, Columbia University New York, NY 10027, USA
IEOR Department, Columbia University New York, NY 10027, USA christian kroer & co umb ia edd
garud ioor. columbie edu
ABSTRACT
We study the alternating gradient descent-ascent (AIGGDA) algorithm in two- player zero-sum games. Alternating methods, where players take turns to update their strategies, have long been recognized as simple and practical approaches for learning in games, exhibiting much better numerical performance than their si- multaneous counterparts. However, our theoretical understanding of alternating algorithms remains limited, and results mostly restricted to the unconstrained setting. We show that for two-player zero-sum games that admit an interior Nash equilibrium, AltGDA converges at an (1/TT) ergodic convergence rate when em- ploying small constant stepsize. This is the first result showing that alternation improves over the simultaneous counterpart of GDA in the constrained setting. For games without an interior equilibrium, we show an O(1/T) local convergence rate with a constant stepsize that is independent any game-specific constants. more general setting, we develop performance estimation programming (PEP) framework to jointly optimize the AltGDA stepsize along with its worst-case con- vergence rate. The PEP results indicate that AltGDA may achieve O(1/T) convergence rate for a finite horizon T, whereas its simultaneous counterpart ap- pears limited to an O(1/VT) rate.
INTRODUCTION
No-regret learning is of the premier approaches for computing game-theoretic equilibria in multi-agent games. is the primary method employed for solving extremely large-scale games, and used for computing superhuman poker Als (Bowling al. 20155 Moravčík et al. 2017 Brown & Sandholm, 2018) 2019). as well as human-level AIs for Stratego (Perolat et al. 2022) and Diplomacy (FAIR al. (022)..
In theory it is known that no-regret learning dynamics can converge to a Nash equilibrium at a rate of O(1/T) through the use of optimistic learning dynamics, such optimistic gradient descent- ascent or optimistic multiplicative weights (Rakhlin & Sridharan 2013a by Syrgkanis et al.) 2015). Nonetheless, the practice of solving large games has mostly focused on theoretically slower meth- ods that guarantee only an O(1/VT) convergence rate in the worst case, notably the CFR regret decomposition framework (Zinkevich et al., (007) combined with variants of the regret matching algorithm (Hart & Mas-Colel] 2000 Tammelin 2014 Farina et al., 202I). critical "trick" for achieving fast practical performance with these methods is the idea of alternation, whereby the gret minimizers for the two players take turns updating their strategies and observing performance, rather than the simultaneous strategy updates traditionally employed in the classical folk-theoren that reduces Nash equilibrium computation in a two-player zero-sum game to regret minimization problem in repeated play.

---

Published as a conference paper at ICLR 2026
Initially, alternation was employed as a numerical trick that greatly improved performance (e.g., in Tammelin et al. (2015), ) and was eventually shown not to hurt performance in theory (Farina et al. [019 Burch et al. 2019). Yet its great practical performance begs the question of whether alternation provably helps performance. The first such result in a game context (and more generally
for constrained bilinear saddle-point problems), was given by Wihisono et al. (2022), where they
show that alternating mirror descent with a Legendre regularizer guarantees O regret, and thus ( convergence to equilibrium. This bound was later tightened by Katona et al. 2024). A Legendre regularizer is, loosely speaking, one that guarantees that the updates in mirror descent never touch the houndary. This is satisfied by the entropy regularizer, which leads the multiplica- tive weights algorithm, but not by the Euclidean regularizer in the constrained setting, and thus not for alternating gradient descent-ascent (AlIGDA). practice, AltGDA often achieves better perfor- mance than Legendre-bassee methods (Kroer 2020). and the practically-successfuu regret-matching methods are also more akin to GDA than multplicattvve weights (Farina al. 202T).
In spite of recent progress on alternation, it remains an open question whether AliGDA achieves a speedup over simultancous GDA for game solving, which is known to achieve O(L/VT) conver- gence. More generally, is unknown whether any of the standard learning methods that touch the boundary during play benefit from alternation. Empirically, there is evidence suggesting this may be the case. For instance, Kroer (2020) observed that the empirical performance of AltGDA exhibits O(1TT) behavior on random matrix games. In this paper, we demonstrate that an O1/TT) conver- gence rate can be achieved in various settings, thereby providing the first set of theoretical results supporting the success of AltGDA in solving games and constrained minimax problems.
Contributions.
The contribution of this paper is three-fold.
We show that AltGDA achieves (1/TT) rate of convergence in bilinear games with an interior Nash equilibrium. Our result shows that alternation is enough to achieve 0(1 (T) rate of convergence, whereas every prior result achieving a ((1TT) rate of convergence for two-player zero-sum games required some form of optimism.
We prove that AltGDA converges locally at an O11TT) rate in any bilinear game. More- over, in this case, we can set constant stepsize that is independent of any game-specific constant.
By leveraging the techniques of performance estimation programming (PEP) framework, we numerically compute worst-case convergence bounds for AltGDA by formulating the problem as SDPs. We present the numerically optimal fixed stepsizes for each T, and the corresponding optimal worst-case convergence bounds. Our methodology is the first instance of stepsize optimization of such performance estimation problems for primal-dual algorithms involving linear operators.
2 RELATED WORK
AltGDA in unconstrained minimax problems. Bailey et al. (2020) studied AltGDA in uncon- strained bilinear problems, and showed an (11/T) convergence rate. They also proposed a useful energy function that is a constant along the AltGDA trajectory. Proving a (L/TT) convergence rate is easier in the unconstrained setting, where the pair of strategies (0, 0) is guaranteed to be a Nash equilibrium no matter the payoff matrix. More discussion given in Section
Zhang et al. (2022) established local linear convergence rates for both unconstrained strongly- strongly-concave (SCSC) minimax problems. [ee et al. (2024) studied AltGDA for unconstrained smooth SCSC minimax problems. More recently, |eng et al. (2025) studied AltGDA with momen- tum in unconstrained smooth minimax problems.
AltGDA in constrained bilinear games. From the game theory context, the constrained setting is more important, because it is the one capturing standard solution concepts such as Nash equilibrium. Prior to our work, are not aware of any theoretical results showing that alternation improves GDA compared to the simultaneous algorithm in constrained minimax problems. See also Orabona (2019) for extended discussion of the history of alternation in game solving and optimization.
As a common technique in game-solving, alternation has been investigated in settings related to ours. Mertikopoulos et al. (2018) showed that the continuous-time dynamics (in their Section A.2) achieve
2

---

Published as a conference paper at ICLR 2026
an OLL/T) average regret bound. Cevher al. 2023 study novel no-regret learning setting that captures the type of regret sequences observed in alternating self play in two-player zero-sum games.
They show a O(T1/3) no-regret learning result for a somewhat complicated learning algorithm for the simplex, and show that Ollog I") regret is possible when the simplex has two actions, through a reduction to learning on the Euclidean ball, where they show the same bound. HHait et al. (2025) generalize this result to any convex-concan zero-sum games. Recently, [azarsfeld et al. (2025)
prove lower bound of (211 for alternation in the context of fictitious play.
Optimistic methods in constrained bilinear games. As mentioned earlier, it is well known that an O convergence rate be achieved by certain variants of extragraidient methods (Kor- pelevich 1976) and optimistic GDA (Popov) 1980) (here simply called optimistic methods). For constrained bilinear games, the O(1 convergence rate has been established by a long line of work for various optimistic methods, including Mirror-Prox (Nemirovski) (0044). Dual Extrapo- lation (Nesterov 2007), Primal-Dual Hybrid Gradient (Chambolle & Pock (20T). Accelerated Primal-Dus (Chen et al. 2014), and Adaptive Mirror- Prox (Antonakopoulos et al. 2019), among others. We emphasize that AlIGDA is not theoretically superior optimístic methods in general; rather, it is an appealing algorithmic choice that is widely used in practice.
PEP for primal-dual algorithms. There has been prior work using the SDP-based PEP framework to evaluate the performance of primal-dual algorithms involving a linear operator with known step- size (Bousselmi et al. 2024 Zamani et al. 2024 Krivchenko et al. 2024), but they do not investigate optimizing the stepsize to get the best convergence bound. Das Cupta et al. (2024); Jaag et al. (2023) proposed for optimizing stepsizes of first-order methods for minimizing single function or sum of two functions, by using spatial branch-and boondd based frameworks. Unfortunately such frame- works can become prohibitively slow when comes to optimizing primal-dual algorithms because of additional nonconvex coupling between the variables in the presence of the linear operator.
Notation. For vectors a, b E Rd, we write T or (a, b) for the standard inner product and ||all = va a for the Euclidean norm. The spectral norm of a matrix A is denoted by ||AA||2 = max ( (A), where m (A) represents the largest singular value of A. We use ||a]| and ||a||| 22 to denote E and & vector norms, respectively. Projection onto a compact convex set X' is denoted by [xx(x)= = argmin,ex* | - =1 llz. We write [d] = (l.....d,, dd} for any positive integer
PRELIMINARIES
We consider bilinear saddle point problems (SPPs) of the form
min max y' AAx, #EX yEy
(1)
where X' C Rd and ) C 1m are compact convex sets and A is an n x m matrix. We are especially interested in bilinear two-player zero-sum games (or matrix games), where An, = fa E R Ex = 1} and y A. {y E ET Ex= 8j 1} are the probability simplexes. In the game context, Eq. ([) corresponds to a game in which two players (called the x-player and y-player) choose their strategies from decision sets An and Am, and the matrix A encodes the payoff of the player (which the x player wants to minimize).
We say (x", .v") E An x Am is Nash equilibrium (NE) or saddle point of the game if it satisfies
y Ax" I (3")T Ax" < (y")TAa Ax V An. y Am-
(2)
By von Neumann's min-max theorem (v. Neumann 1928). in every bilinear two-player zero-sum game, there always exists a Nash equilibrium. and a unique value v" := minzes, maxyEA,.. y' Ax = maxyEa,, minges,, y Ax which is called the value of the game. Furthermore, the set of NE is convex, and V² = (An,(A7) y²); max, mAx"")x)) We call an NE (x",y") an interior NE if x > for all i E [n] and V; > 0 for all j E [m].
For strategy pair (ž. 9) A, x Ams we use the duality gap (or saddle-point residual) measure the proximity to NE:
Duali Malittyaap(it (ă, 5) == (supyes,. y Aa (TA))
(ūJ Au
inf ÿ Ax) mr A.,
SUPPEE (y AĀ - ÿj Az))
(Duality Gap)
3

---

Published as a conference paper at ICLR 2026
Algorithm 1 Alternating Gradient Descent-Ascent (AIIGDA)
input: Number of iterations T, step size > 0
initialize: (xx) yy" X' x y for 1. T. 0,..., do
x++1 (x' - nA y²)
y y'+l Iy :/Ax
end for output:
(+ - x', D y
By definition, DualityGap(ā; 3) 2 0 for any Ø) E An x Am Moreover, DualityCap(2; Ú) if and only if (æ. 3) is a Nash equilibrium.
For general bilinear SPPs as in Eq. DualityGap(i; () = suPaex (y T -Ax). A point (z, 3) E X y is called an e-saddle point if DualityGap(E2 ã. y) S.
AltGDA and SimGDA. For solving Eq. T the alternating and simultaneous GDA (AliGDA and SimGDA) algorithms are simple and commonly used in practice. In AltGDA, the players take turns updating their strategies by performing single projected gradient descent update based on their expected payoff for the current state. We state the AltGDA algorithm in Algorithm [ In contrast, SimGDA updates both players' strategies simultancously, using the expected payoff evaluated at the previous state. Compared to Algorithm[[] the inner projected gradient descent takes the form
x (xxx'' n y'), y -llly' + n)Ax)).
(SimGDA Updates)
PERFORMANCE ESTIMATION PROGRAMMING FOR ALTGDA
In this section, we present a computer-assisted methodology based on the PEP framework (Drori & Teboulle 2014 Taylor et al. 2017b a) along with results on PEP with linear operators (Bousselmi ct al. 2024) to compute the tightest convergence rate of AltGDA numerically.
Computing the worst-case performance with a known 7). We consider bilinear SPPs over com- pact convex sets as described by (T]. The worst-case performance (or complexity) of AltGDA corresponds to the number of oracle calls the algorithm needs find e-saddle point. Equiva- lently, we can measure AltGDA's worst-case performance by looking at the duality gap of the aver- aged iterates, i.e., DualityGap(+ + Σi= xt, E y²) max WEY (y) A(+ Σi= x") (+ - w²) Ax), where {(x', y²)) are generated by AltGDA with stepsize 1).
To keep the worst-case performance bounded, we need to bound the norm of A and the radii of the compact convex sets X. y. In particular, without loss of generality, we assume mma < Let Rs and Ry be the radii of the sets X and y. respectively. Then, without loss of generality, we can set R == max Rz, R, = 1. This is due to scaling argument: for any other finite value of R, the new performance measure will R²2 x (worst-case performances for R R=1).
Let A1+GDA(1), .,,y² denote the sequence of iterates generated by Algorithm with stepsize starting from initial point (az", 9)) Then, we can compute the worst-case performance of AltGDA with stepsize 7 O and total iteration T by the following tion problem:
nonconvex optimiza-
T
maximize
T (
Σ 1=1
Ax''
(y')TA Aa))
((a' w² Doceer CR" CR" "
XxYER" m
A m.n
Pr(1): :=
subject to
X' is convex compact in I= with radius 1, y is a convex compact set in R with radius 1,
(INNER)
mmax (A) < 1,
((x' y JISIS AltGDA(n, ..y
(x y (x, y) E E V.
4

---

Published as a conference paper at ICLR 2026
Optimized Step Size vs
Optimized Objective Value T
2.
SINGDA
Cottiiized Oijjective Value
Optinizzed Step Size (n)
2000
20
0.5
30
10
3000
10
(a)
(b)
Figure 1: Optimized stepsizes and corresponding optimized objective values for T' = 5, .,.....0 50 via PEP. The left plot shows the optimized stepsizes. The optimized objective value in the right plot denotes the worst-case performance measure (i.e., duality gap of the averaged iterates) correspond- ing to the optimized stepsizes on log scale.
Problem (INNER is intractable because it contains infiiit-diimensional objects such as X, V, and A where dimensions n,, m are also variables. Nevertheless, for our setup, all possible iterates and their associated gradients up to I can be captured by a finite collection of interpolation inequalities. These inequalities fully encode the entire class of admissible instances, thereby allowing (INNER) to be reduced a dinee-dimessioall SDP, as elaborated in Appendix E] This SDP is also free from the dimensions n and m under large-scale assumption. In other words, computing Pr (n) numerically provides us a tight dimension-inen inneiiidenndeeeeeennt convergence bound for AltGDA for given 1j and T.
Best convergence rate with optimized 1). For a fixed T. the best convergence rate of AltGDA can be found by solving Pj- minimize,,Pr(() To solve this problem, we perform grid-like search on the stepsize 7 and solve the corresponding SDP for each of the finitely-many 1) choice:
Step 1: Set an initial search range [Tmin "mmax];
Step 2: Pick n points within this range such that their reciprocal is equally spaced, i.e.,
candidate stepsizes s.t. 7mmn = 7/1 S ... I Tn = 7max and 1 1
Step 3: Compute the worst-case performance corresponding to each candidate stepsize, and
denote the best stepsize 17";
Step 4: Set an updated search range: [Mmin Truax] f [nn -a" TInax Pumin
"7" Toaxx Yanin
Step 5: Repeat Step 2 and Step until Tmax Vmin S Ex-
Here, Mmin, 7max T2, a; E, are hyperparameters to be fine-tuned. In our numerical experiments, we set 20, 1 and E, 10 3; and fine-tuned Mmin: Maax based different algorithms and time horizon T. Because the precision of the grid search En is not equal to exactly zero, we call our computed stepsize to be optimized rather than optimal.
Results and discussion. See Fig. 1 for the optimized stepsizes and corresponding worst-case per- formance. We also provide the data values to generate Fig. i Appendix E.
From Fig. la we observe a structured sequence of optimized stepsizes for AltGDA. The origin of this periodic optimized stepsize pattern interesting in itself and worth exploring. Moreover, this phenomenon indicates the possibility of improving the convergence rate by employing iteration- dependent structured stepsize schedules in the minimax problems. Beyond this, we observe that the decay rate of the stepsizes scales as ((o/ ")) for some a > O. which indicates that the optimal convergence rate may hold with "nearly-constamt" stepsizes. Fig, Tbsshows that the optimized duality gap approaches O11/T) convergence rate as T increases. This suggests that AltGDA obtains a (1/T)) convergence rate after a short transient phase. This finding also raises an interesting question about the origin of the initial convergence phase. In contrast, SimGDA exhibits a ((IVTT) convergence rate, even with optimized stepsize schedule.
By taking non-equally spaced points, place greater emphasis exploring the range of smaller step sizes.
5

---

Published as a conference paper at ICLR 2026
1.0
Iterationn
Ieeraions
1.40
1.0
VIMI
0.6
Duality Gep
0.7
Energy
100
0.01
02
0.001
10
10
10a
102
102
X1
Figure 2: Numerical results on the rock-pape bock-paper-scissoo game. From left right, we show the trajec- tories of the AltGDA iterates (in ternary plots), the changes in duality gaps, and the evolution of the energy functions.
The PEP literature provides potential solution theoretically prove the tightest convergence
rate for a given algorithm (Drori & Teboulle 2014) Taylor et al.] 201 a) A proof in this frame- work requires discovering analytical solutions the optimal dual variables of the underlying SDPs, including proving semi-definiteness of the SDP matrices (Goujaud et al. 2023). For AlrGDA, our attempts at a proof via this route lead us observing rather intricate optimal dual variable structures that appear to make the proof difficult. As an alternative, we will show in the following sections that more classical proof approaches, with some interesting variations, can be used show (1//T) convergence in several settings.
5 O(//T) CONVERGENCE RATE WITH AN INTERIOR NASH EQUILIBRIUM
In this section, we establish an O1/TT) convergence rate AltGDA for bilinear two-player zero- sum games that admit interior NE. We begin by presenting the motivation and interpretation of the proof, followed by a sketch the formal proof.
MOTIVATION AND INTERPRETATION
observations about the trajectory generated by AltGDA, which the inspiration for our proof. In contrast to the unconstrained setting (Bailey et al., 2020). the iterates of AltGDA do not necessarily cycle from the beginning, even in the presence of interior NE. Fig. 2 shows the numerical hehavior of AltGDA in the mekk-paper-scisoors game, which is bilinear game admitting an interior NE. The left plot shows that the trajectories of the players' strategies exhibit two distinct phases. In the first phase, the orbit hits the boundary of the simplex and is "pushed back" into its interior. In the second phase, the orbit settles into state where it cycles within the relative interior of the simplex and no longer touches the boundary.
We will start by presenting
We observe that this two-phase behavior can be captured by the following energy function with respect to any interior NE (x*,v")
(Energy) We plot the evolution of Exx y²) on the right of Fig. [ Interestingly, we find a correspondence between the "collision and friction" of the trajectory and the "energy decay" of E(x", y¹). In par- ticular, the energy function admits a meaningful physical interpretation-ii decays whenever the trajectory collides with and rubs against the boundary of the simplex.
E(x', v²) = ||æ. x: 111
I/y y'11 (18") Axx
Moreover, in the middle of Fig. [2] we see the duality gap decreases slowly when the energy de- creases, and shrinks at (1) rate after the energy function remains constant. This indicates the connection between the energy function and the convergence rate of the averaged iterate, which forms the foundation of our proof.
While the energy function is dependent on the stepsize y,. write E(at, yy") rather than E(y, f y²) to reduce the notational hurden.

---

Published as a conference paper at ICLR 2026
5.2 CONVERGENCE ANALYSIS
In classical optimization analysis, convergence guarantees are often established using some potential function: one first establishes an inequality showing that the duality gap at an arbitrary iteration is bounded by the change of a potential function plus some summable term, then telescopes this inequality to obtain the convergence rate. In contrast, our proof works with an inequality involving the duality gap at two successive iterates, as shown in the following lemma. The complete proofs in this section are deferred to Appendix B
Lemma 1. Let {(x', "",,.,,..... be a sequence of iterates generated by Algorithum 7 with rj 0.
Then, for any (xc, y) E An x Am. we have
1) ( T Axx - (y') Axx) S (xx y) - 1/41111 (xx y) + n7( -AAAAA yy x++ - =x")
1 10/1 - x² 112 1 1 36 1| for 1 1,
(3)
2
1) (y) TOTAoo Axx*11 (1) ( S (xt, y) - D1+1 ( y) + tn{ Axx 2 - 8²)
- 1//t1_ - -x112 1 2 | n for t 2 0,
1
(4)
2
where Φr (x, y) = 211=0* 2012
+
y1 + n/l'r Ax and () = 1 - x: +
1 y 2112 - b y ||
The main challenge in the proof is determining whether the sum of the residual terms on the right- hand sides of Eqs. 3 and (4 are summable, i.e., Eroo V2 < oc where
Fr : A yy =(-nA yy - 41 + +x' x0t1- =x") + (nAx't) ++ y ++ + v', y v²)
x²) + AAxx'= y 4+ 3²) || x x²112
18/ +1
3 1|
(5)
In the unconstrained case, we have r; = for all t 2 O, and hence the O(1/T) convergence rate follows directly. In contrast, in the constrained case, the first-order optimality conditions of the projection operators imply that r 2 0. Therefore, it is not immediate whether r; is summable. To handle this, we exploit the connection between energy decay and the convergence rate of the duality gap, as shown in Fig. 2 In particular, when an interior NE exists, we show that the residual ry can be bounded by the decay of the energy function, established in the following lemma.
Lemma 2. Assume that the bilinear game admits an interior NE. Let (aa,, ((a',y"))e y'),.. be se- quence of iterates generated by Algorithm with S 1 TAll2 min(minge(v) 2t, minse(m) Dj). Then, we have 0 S rt S E(x,,, yy)) E(x't1 for all t 2 O.
By combining Lemmas I and 2. telescoping over 0, 1,...,,T, T, and using the boundedness of é, vt, E, we obtain the O(1/T) convergence rate.
Theorem 1. Assume that the bilinear game admits an interior NE. Let ((x", ((x")y")) y') be a se- 1 minfmingen at minzelm) Vî}. Then, Talla
quence of iterates generated by Algorithm with S
we have
1 T
T
9 + 4n A/||
DualityGap
T
rf
t=1
Theorem I provides the first finite regret and O(1/T) convergence rate result for AltGDA in con- strained minimax problems. Although such a result has been known for several years the uncon- strained setting (Bailey et al., 2020), no better than O(1/VT) convergence rate has been established in the constrained case. Even for the broader class of alternating mirror descent algorithms, no in- stantiations of the algorithm were known to achieve a O(1/T) convergence rate- despite having
been observed numerically (Wibisono et al. 2022 Katona al. 2024 Kroer 2025).
Although our primary goal is to develop the theoretical foundations for AltGDA, we also include additional results relevant for practice in Appendix C For instance, we present adaptive step-size rule that does not require knowledge of the interior NE yet still achieves an O(1/T) convergence
rate in Appendix C
7

---

Published as a conference paper at ICLR 2026
1.
Iterations
Ieeraions
Duality Gep
0.7
Energy
0.01
0.
0.001
10a
10a
10
10a
10a
102
102
10a
Figure 3: Numerical results on 3 x random matrix instance without an interior NE. The experi-
mental setup is the same as in Fig. 2
The trajectory of AltGDA exhibits more intricate behavior when the game does not have an interior NE, As shown in Fig. the trajectory tends to approach the face of the simplex spanned by the NE with maximal support, which we refer to as the essential face. However, the trajectory does converge to the essential face monotonically-iit can leave the face after touching it. This non- monotonicity persists even after many iterations in our experiments, and, accordingly, the energy may increase on some iterations. In this case, the difference of the energy no longer yields an upper bound for r. as in Lemma] 2
6 LOCAL O(1/T) CONVERGENCE RATE
As previously discussed, our O1/TT) convergence rate only applies to games with an interior NE due to non-monotonicity of the energy function in the general case. Nevertheless, even without an interior NE, we show that in local neighborhood of an NE, we can prove an O(1/T) convergence rate with constant stepsize. Notably, this stepsize is independent of any game-specifie parameters.
Let (x", yn) be a NE with maximal support. Then we first partition each player's action set into two subsets: I" {i [m] x. > 0} and 'n] I"; J {i E [m] vz 0) and [m]] \ J", and introduce the following parameter measuring the gap between the suboptimal payoff's to the optimal payoff for both player
(AT y²); ~-
/" - (Axx);
min
min Egr-
min ||A||2 -e.
min 2t, min yi "ES* JEJ
||
If the equilibrium has full support, then 5 is the minimum probability of any action played in the full-support equilibrium. there is no full-support equilibrium, then Mertikopoulos et al. 2018 Lemma C.3) show that for maximum-support equilibrium have that ò Define To = min(
|r" n- -.-T,, n). ry min [J' J.1, m). and local regior
8
7/
A11 2
2 88 max y₁ 11 ,0
S = (2. || x= 11 - 4 1y 1
D; S
i
2
The following lemma establishes a separation between the entries in 1 and [m] 1"; S and [m] U" The complete proofs in this section are deferred to Appendix D
Lemma 3. If the current iterate (æ, v) E S, and the next iterate (a+ .y+) is generated by Algo-
rithm 7 with the stepsize S A1I then we have (i) x 2 2 for all i E I and v Uj 2 2 for
all j E J"; (ūi) x; S v, for all & I* and v I Vÿ for all j & J
Next, define an initial region:
So = { (a. y)
x x=1
y 1'1 S 8
max 84 S - rno max j
C
S C 2 5r Cs, (7)
8'
ig 1- 2
Note that the parameter is invariant under scaling of the payoff matrix A. "The last constraints redundant when [7"| n or [J' m.
8

---

Published as a conference paper at ICLR 2026
LINIFORM
RANDIMT
BINARY
101
Sindit
Emao Std Dev!
122
ANSDA
10-1
Eiror Range Sod Dev!
Gap
Duelity Gop
20"
Duality
10
10"
SeriaAA
12th
SenG2A
Enor Range to S0d DevI
Emor Range S00 Devt
AISDA
Ronge Deni
30-
Range Dcrt
307
10
107
32"
107
10*
124
10'
10
105
NORMAL
LOGNORMAL
EXPONENTIAL
10
120
Duaiity 10-3
Duality Gep
Dusitty
10
10
AM1
AIIDA Emror Devt
5kd Dev)
12
Sange
Figure 4: Numerical performances of AlIGDA and SimGDA on 10 20 synthesized matrix games.
where c Anll 7 192 J92.-1 }- Also, for ease of presentation, define variant of the
6
energy function: V(xx, y) = - x= 12- ly y211 - 7 y²) A(x - (oe==x) x²) In the following lemma, we prove that we initialize AliGDA within So, then the sequence of iterates stays within S. With this in hand, we can derive an upper bound for the cumulative increase of the energy V.
Lemma 4. Let {(x', ((x',y') Hezo be sequence of iterates generated by Algorithm / with stepsize I and an initial point (x", yy)) E So. Then, the iterates {(x', yy br20 stay within the local S 2 AT,
region S. Furthermore, for any T O, we have Σ (V(x++1 .y*+) V(x', y²)) 1 82.
Combining this results with analogous inequalities as in Lemma we obtain the local O(1/T) convergence rate.
Theorem 2. Let f(x', yy))')) 1220 be a sequence of iterates generated by Algorithm D with stepsize and an initial point (x", 3 ) E So. where So defined in Eq. Then, we have that
17 S 2 A|
1 T
S 9 + 7nll All, + (6 /18)
DualityGap
a T
Σ
yy
nTT
1=1
t=l
where 5 is defined in Eq. 66
7 NUMERICAL EXPERIMENTS
We conduct numerical experiments to compare the performance of AltGDA and SimGDA on bilin- car matrix games, under a constant stepsize over a large time horizon.
We evaluate AltGDA and SimGDA random matrix game instances. The payoff matrices generated from six distributions: uniform over [0, 1]. uniform over integers in [-10, 10), binary (0. with P(O) 0.8, standard normal, standard lognormal, and exponential with location 0 and scale 1. For each distribution, we generate instances of sizes 10 x 20, 30 x 60, and 60 x 120. All algorithms implemented with stepsize 7 = 0.01 and for T 10 iterations. We repeat each experiment ten times, and we initialize the starting point randomly. We report the mean and standard deviation across repeats at every iteration. Results on the 10 20 instances are shown in Fig. 4 while the remaining figures are provided in Appendix
Agaan,, we pick any NE with the maximum support if there multiple.

---

Published as a conference paper at ICLR 2026
The experimental results show that AltGDA achieves an O(1/T) convergence rate numerically, and this rate is robust to the choice of the initial point. As consistently observed, the convergence is slow in the early phase, which In contrast, SimGDA fails to converge under a constant stepsize that independent of the time horizon. In Appendix [222 test AltGDA with different stepsizes, demonstrating that the empirical convergence rate scales linearly with 1/7,, which is roughly in agreement with Theorems and
be explained by the "energy decay" introduced in Section [
8 CONCLUSION
We establish the first result demonstrating Al(GDA achieves faster convergence than its simultane- counterpart constrained minimax problems. In particular, we prove O(1'T") convergence rate of AltGDA in bilinear games with an interior NE, along with local O1/TT) convergence rate for arbitrary bilinear games. Moreover, we develop PEP framework that simultaneously optimizes the performance measure(s) and stepsizes, and we show that AltGDA achieves an (1/"T) conver- gence rate for any bilinear minimax problem over convex compact sets when the total number of iterations is moderately small.
ACKNOWLEDGMENTS
This research was supported by the Office of Naval Research awards N00014-22-1-2530 and N00014-23-1-2377 and the National Science Foundation awards IIS-2147361 and IIS-2238960. S. Das Gupta acknowledges support from AFOSR Grant Number 7A9550-25-1-0185
REFERENCES
Kimon Antonakopoulos, Veronica Belmega, and Panayotis Mertikopoulos. An adaptive mirror- prox method for variational inequalities with singular operators. Advances Neural Information Processing Systems, 32, 2019.
James P Bailey, Gauthier Gidel, and Georgios Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. In Conference on Learning Theory, pp. 391-407. PMLR, 2020.
Heinz Bauschke and Patrick Combettes. Convex analysis and monotone operator theory in Hilbert spaces. Springer, second edition, 2017.
Amir Beck. First-order methods in optimization, volume 25. SIAM, 2017.
Nizar Bousselmi, Julien M Hendrickx, and François Glineur. Interpolation conditions for linear operators and applications to performance estimation problems. SIAM Journal on Optimization, 1443):303330063 2024.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold' fold'em poker is solved. Science, 14:56228)
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(677)):418-444, 2018.
Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 365(6456): 885-890, 2019.
Neil Burch, Matej Moraveik, and Martin Schmid. Revisiting efr+ and alternating updates. Journal of Artificial Intelligence Research, 64:429-443, 2019.
Ozan Candogan, Ishai Menache, Asuman Ozdaglar, and Pablo A Parrilo. Flows and decompositions of games: Harmonic and potential games. Mathematics of Operations Research, 36(3):474-503, 2011.
Volkan Cevher, Ashok Cutkosky, Ali Kavis, Georgios Piliouras, Stratis Skoulakis. and Luca Viano. Alternation makes the adversary weaker in two-player games. Advances in Neural Information Processing Systems, 36:18263-18290 2023.
10

---

Published as a conference paper at ICLR 2026
Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40(1):120-145, 2011.
Yunmei Chen, Guanghui Lan, and Yuyuan Ouyang. Optimal primal-dual methods for class of saddle point problems. SIAM Journal Optimization, 24(4):1779-1814, 2014.
Shuvomoy Das Gupta, Bart PG Van Parys, and Ernest K Ryu. Branch-and- performance
estimation programming: A unified methodology for constructing optimal optimization methods. Mathematical Programming, 204(1):567-639, 2024.
Yoel Drori and Marc Teboulle. Performance of first-order methods for smooth convex minimization: A novel approach. Mathematical Programming. 145(1-2):451-44 482, 2014.
Meta Fundamental AI Research Diplomacy Team FAIR, Anton Bakhtin, Noam Brown, Emily Di- nan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, et al. Human-level play in the game of diplomacy by combining language models with strategic reasoning. Science, (166624):167-1000 2022.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Online convex optimization for sequen- tial decision processes and extensive-fomm games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1917-1925, 2019.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive black- well approachability: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence. AAAI, 2021.
Yi Feng, Kaito Fujii, Stratis Skoulakis, Xiao Wang, and Volkan Cevher. Contimuous-time analysis of heavy ball momentum in min-max games. arXiv preprint arXiv:2505. 195377 2025.
Baptiste Goujaud, Aymeric Dieuleveut, and Adrien Taylor. On fundamental proof structures in first-order optimization. In 2023 62nd IEEE Conference on Decision and Control (CDC), pp. 3023-3030. IEEE, 2023.
Soumita Hait, Ping Li, Haipeng Luo, and Mengxiao Zhang. Alternating regret for online convex optimization. arXiv preprint arXiv:2502.12550 2025.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127-113: 2000.
Michael Held, Philip Wolfe, and Harlan P Crowder. Validation of subgradient optimization. Math- ematical programming, 6:62-88, 1974.
Roger Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Uijeong Jang, Shuvomoy Das Gupta, and Ernest K Ryu. Computer- assisted design of accelerated composite optimization methods: Optista. arXiv preprint arXiv:2305.15744 2023.
Jonas Katona, Xiuyuan Wang, and Andre Wibisono. A symplectic analysis of alternating mirror descent. arXiv preprint amXiv:2405.03472 2024.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Valery O Krivchenko, Alexander Vladimirovich Gasnikov, and Dmitry A Kovalev. Convex-concave interpolation and application of pep to the bilinear-coupled saddle point problem. Russian Journal of Nonlinear Dynamics, 20(5):875-892 2024.
Christian Kroer. Lecture note 5: Computing nash equilibrium via regret minimization. Lecture notes for IFOR8100: Economics, AI, and Optimization, Columbia University, February 2020. URI. https:: httts::/wwebs rcchi ve. org web 20221 002062403/0020200 Sabb/rok2945/Elles/// 0100008100/11111
//ww:t::://///..// co lumbi. a.
note_ ___na_______________________aasa _rom__rrm rm. pdf
Christian Kroer. Games, Markets, and Online Learning. Cambridge University Press, 2025, In press.
11

---

Published as a conference paper at ICLR 2026
John Lazarsfeld, Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Optimism without regular- ization: Constant regret in zero-sum games. arXiv preprint arXiv:2506.16736, 2025.
Jaewook Lee, Hanseul Cho, and Chulhee Yun. Fundamental benefit of alternating uptades in min- imax optimization. Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 26439-26514, PMLR, 21-27 Jul 2024. URL httpt:tttp/ppooeeeeee .ress wtt.mmpppw....////mmm
ngs. press/
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial reg- ularized learning. In Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms, pp. 2703-2717. SIAM, 2018.
Matej Moravčík, Martin Schmid, Neil Burch. Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-57) -1308 2017.
Arkadi Nemirovski. Prox-method with rate of convergence (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, (5()):229-251, 2004.
Yurii Nesterov. Dual extrapolation and its applications to solving variational incqualities and related problems. Mathematical Programming, 109(2):11-334,,2) 2007.
Francesco Orabona. A modern introduction to online learning, arXiv preprint arXiv:1912.1322 2019.
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 378(6623):990 001000996,911 2022.
Leonid Denisovich Popov. A modification of the arrow-hurwit method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845-88)) 1980.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Confer- ence on Learning Theory, pp. 993-1019, PMLR, 2013a.
Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable se- quences. In Proceedings of the 26th International Conference on Neural Information Processing Systems- Volume 2, pp. 3066-30000 3074, 2013b.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regu- larized learning in games. In Proceedings of the 28th International Conference on Neural Infor- mation Processing Systems- Systems-Volume Volume 2. pp. 2989-2997. 2015.
Oskari Tammelin. Solving large imperfect information games using CFR+. arXiv preprint arXiv: NX07::407.5042 2014.
Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit Texas hold'em. In Twent-Fourthh International Joint Conference on Artificial Intelligence, 2015.
Adrien B Taylor, Julien M Hendrickx, and François Glineur. Exact worst-case performance of first-order methods for composite convex optimization. SIAM Journal on Optimization, 27(3): 1283-1313, 2017a 2017a.
Adrien B Taylor, Julien M Hendrickx, and François Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming, 161(1-2): 307-345, 2017b.
J Neumann. Zur theorie der gesellschaftsspiele. Mahheattsche annalen, 100(1):295-320, 1928.
Andre Wibisono. Molei Tao, and Georgios Piliouras. Alternating mirror descent for constrained min-max games. Advances in Neural Information Processing Systems, 35:35201-35212, 2022.
12

---

Published as a conference paper at ICLR 2026
Moslem Zamani, Hadi Abbaszadehpeivasti, and Etienne de Klerk. The exact worst-case convergence rate of the alternating direction method of multipliers. Mathematical Programming, 208(1):243-
276, 2024.
Guodong Zhang, Yuanhao Wang, Laurent Lessard, and Roger Grosse. Near-optimal local conver- gence of alternating gradient descent-ascent for minimax optimization. In International Confer-
ence on Artificial Intelligence and Statisties, pp. 7659-7679. PMLR, 2022.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In Advances in neural information processing systems, pp- 1729-1736, 2007.
13

---

Published as a conference paper at ICLR 2026
APPENDIX
A ADDITIONAL DETAILS ON FIG. 2 AND FIG. 3
Since the behavior of AltGDA can differ depending on whether an interior NE exists, we examine the behavior of AltGDA on two instances. the rock-paper-seissont game which admits an interior NE, we show the trajectory of AlGGDA starting from the initial points x = (1, O, 0) and y/ = (0. O). For the game without interior NE, we generate 3 3 matrix game whose payoff matrix is sampled from the standard normal distribution with random seed 1. This matrix has non-interior NE:
xx = (0, 0.56, 0.44), y (0.37, 0.63, 0). We initialize AltGDA from zg = yo = (1/3, 1/3, 1/3).
In both instances, we use a stepsize of = 1 0.01, and we plot the evolution of the duality gap and the energy function as defined in Eqs. (Dullity Gap) and (Energy..
See Fig. 10 and Fig. for the evolutions of Fig. and Fig. respectively.
B OMITTED PROOFS IN SECTION 5
We start by summarizing the notations used in Appendices B and D in Table
Table I: Notation table
NOTATION
EXPRESSION
On
n--iiennsional all-zero vector
1,
n-dimensional all-one vector Probability simplices for x-player and y-player
An; Am
A Am
{ar E Th Σ x 1}. {y E R.m Σ リド = 1}
(x, y)
An arbitrary pair of strategies in An Am An arbitrary NE of the maximum support A pair of iterates at the (-th iteration
(x" .y")
(xx y²), 14 2
Oe (x, y), Vt 0
1
||
x
2 + +
=y + +7(y") Ax
We (x, y). V 1
x
"ly
y >1ly' - y -
I"
fie
[n]
x; 0
J 14 Vtz0
[ [m]
y7 0}
{ie [n]
>
Jr, Vt20
{j
[mi]
V3 0}
(x,
|| x
11 + 11
y ny
T Axx
V(x,y)
| x 11 + 11y
y 113
(
y
A(x x²)
Vr. 2 0
(ax'
- AA' y² + Er v' 1n
U V12 0
Ax mm (Ax")
wt At 20 0
y,, 44 2 0
I1 (m' nA y² -t+
x typ 1+1
X Vt 20 0
1m +1/mm" ++1) 1) -y
3/2 4- +4 39
31, AA 2 O
max4e[1] 7
X 1A 2120 0
max A
Before the proof, we first show the following elementary inequalities that will be used later.
Lemma 5. For any x, x E An, y. y Am. we have
1. x - x 2'1|2 < 2, ly
y < 2,
2. (y y²) A(x x²)
|| x 2'112111 v'lla 2/1
3. y Ax < ||A]|2
4. A yl2 || and
A
la A|
14

---

Published as a conference paper at ICLR 2026
Proof. The first item can be shown by || x' 12 S ||
||2/ [| 2, where the +|22112 S ||0||2 +
last equality follows by x; x' E An; the part can be done in the same way.
The second item follows from Cauchy-Schwarz incquality and the fact that because the vector norm ||-1|/ is compatible with the matrix norm 11-112 (Horn & Johnson 2012 Theorem 5.6.2):
(y 3²) (y'y A(x x²) lyy y' Al2 22
|
x
x
2
y
y 2- Then, the first
item implies the second one.
For the third item, for any An: y Ams we have
(a) y A S || yll - | I Ull2 = | 112 S | y S ||| y = ||A|//2
(6)
where (a) follows from Cauchy-Schwarc inequality. (6) follows because the vector norm 11-112 is compatible with the matrix norm ||-112 (Horn & Johnson 2012 Theorem 5.6.2), and the two in- equalities hold because x E A, and y E Am.
The proof of the forth item is analogous to that of the second one: for any y Am. we have |A 8/l2 I || l122 I ||A|||]]| = ||Al|2. where the first inequality follows by Horn & Johnson 2012 Theorem 5.6.2) and the last inequality holds because y Am- Similarly, for any E A m we have | - ||4 |||2||/=||| & ||4||2 [z]|]2 = ||A||2.
We start with the proof of Lemma 1
Lemma 1. Let {xx, h=),....... be a sequence of iterates generated by Algorithm D with > 0.
Then, for any (2r, 3) E An x Am, we have
(y A''xxx= (zy)) (xx)
S (ee y) - Uh+1 (ar y) n ATT x² - =x²) a| -x -x'1/2
1 $ (ar, y) - 2141 y) n Azt gtth - y²)
1
y²112
V2 1 (8)
17 (y Axx - ( Ax)
1 1
1012
1 2
12 3/112
11 2 (9)
where (2, v) = 11 2 + Elly' y1l2 + n(00) Ax and (e(
1 +lle**
20 +
11y--11 - v112 lllyy - y²11 11
Proof of Lemmal 7 Consider any x E X' and y y. By the property of the projection operators, we have
(2' -a'-nATa y' xt+ x+11 -x) 2 0, Vt 0
(10)
(y' + A+x - 1+ e+ - -y) 00, V1 0.
Thus, we have
xx 11 c+ x) 2 7(AA yr x²+1 - x²)
= = y01 xl+1 - x²) + (AA y² -A 1ytt1, , x).
(11)
( - y'' yltl - y) -n (Ax 41 y 8).
(12)
Note that
2(x² 111 x - xz) = 1.² x 2
| x x1+112 2 || 20
2(y² 44 y2t1 4) yy¹ y1 lyy y ++1 1|2 | 2/12-
and
yyt 141 x² (Ax yot
y) y Axx (1) Ax..
15

---

Published as a conference paper at ICLR 2026
Denote (z. 3) 1| - x11
2 + 2 v112 + + y¹, x). Combining the above inequalities
and identities, we obtain Eq. (4).
Similar to Eq. (10), we have
(xt
nA T 8¹ - x²+ x. x x 2 0, A1
(0' + 1/ -y² 3² 4) 2 0, 1121. 1.
Thus, have
(x' 2t +2 - x 2 17 A y¹ x ++ 2)) = (ATT TTy x." - x) + +n(AT 2tt -x!) x²),
(g'-1 y², 3/ - -y) 2 - { Ax! n¹ -y).
Denote (x, y) 1 | inequalities, we obtain Eq.
x 2 1111r
2//l/² y11 Combining the above two y
Next, we proceed with proving Lemma Before that, we present few lemmas.
For any positive integer d, we denote Âa far Rd Σ ti = 1}, which is the affine hull of the probability simplex Ad. The following lemma connects the projection onto a simplex Aa with the projection onto its affine hull.
Lemma 6. For any y E Rd we have II,, (y) AI (Is, (y)). Furthermore, for any x E Ad. we have (y, IT ( x) 2 0 where 7 == 11 (v) IT (y)
Proof. Using the properties of projection onto a closed affine set (Bauschke & Combettes 2017
Corollary 3.22), have ||æ: 2l12 | TA (v)ll +| + (y) y 112 for any A.. Hence, using the definition of projection,
HA (V) = argmin||a mEAr
v1l argmin|| Hz (v)l II (MA, (v)) =cA,
Then, using the properties of projection onto a closed convex set again, we have (Ix, (v) Ma, (v) Ia, (g) x 2 0 for any Aa.
Denote
r = Iāx, (x' NATT² v²) x+11
(13)
and
A II (y' + mAx 4
(14)
7
The following lemma provides two useful inequalities involving 7 and X
Lemma 7. Assume that the bilinear game admits interior NE. Let ((a', y (....... be quence of iterates generated by Algorithm with S |All, min(minge(n) at minje(m) Uf}. Then, the iterates of AltGDA satisfy
1. {r' x - -x) O, Vx E A. and (X. 4 y) 2 0, Vy Am.
2. ( x² =x)) 2 0 and (Xe, y² y" 2 0.
Proof. The first item directly follows from Lemma
For the second item, we have
| x'1|2 |A (x'
T IIA, (20) & ||0
Tr <'112 1//AA/2 (15)
16

---

Published as a conference paper at ICLR 2026
where the first inequality is by the nonexpansiveness of the projection operator II,,, and the last inequality follows by Lemma 5
As a result, x'+1 x E B(O,. A2) Then, we have
(r', x² x²)
=(r,, xx/11 x²) + (r x²' x
t
2(r", x²+1 - -x") + r", -1llA11
(by x²+1 - x' E =(, 7114112))
| 12
7"' 1+1 - -11lA11
7 x²
2 0
(16)
|
where the last inequality follows from the first item and
x² -"+ +1llAAl2
B B("' min
min 27, min (iE(n)
vi 1) Sn CA..
17,/|2
je(m
Here, x² / गيन..
An is because Eienn 76 0. Similarly, we can prove that
(X', y' y 2 0.
Recall that the energy function & An X Am - defined as
E (xx )²) x=' x= 1
y 112 nT(²' Ax",
where (x" (x) is any Nash equilibrium with full support. We now show this energy function is non-increasing in in the following lemma.
Lemma 8. Assume that the bilinear game admits an interior NE. Let {(x', b') be se- 1 quence of iterates generated by Algorithm with S TAl min fin 2;, minje[m] bf Then,
we have (x'+1, ee+t1,y'+ 11) {x('', (e',z) for all t 2 O. In particular, we have for all 2 0
E (x',y²) - (x'+1, (a'"",,"'') ,y**!) = n1(r" xx +1 + x² 2xx) + n g + 3² -2y") 2 0. (17)
Proof. Because AI (u+ + g) + g } (1]g) la for any u Ds and g R Beck 2017
Lemma 6.26), we have
x [+1 = x² - -nA 3¹ +
(A vy) 1n 179
im
(18)
y 1+ = yy + ++ 11
7
(Azltl), 1m n72'
m j=1
Hence, we have
x (1 x0 nA'
T y¹¹ ! E" (A (ATy'): yy) 1, "rr² 1+1 + x² 2x
n
n1
(19)
(t 3² - -1xx 1+1 + 17 m
m E (Ax )1- 1m + n y 4+1 + r² - -2y = 0.
Because (In, , x111 + - 2xr) Im 4² + y² - 2y = 0. and (a - b, a + b) = ||al|
||bl for any vectors a, b, the above inequalities are equivalent to
++ x= x²1 - ||a0" - x + n y² 1+ + x' - 2x + 1772" x++ + x² 2x = 0
g yn 1122 ,/y - y²11 7 Ax 2 + yy 2y + 9 (X' y (+1 + y² 2y (20)
Summing up the above two inequalities and plugging in the definition of energy function E, we have
E (x't1.y'+) +) - E (x',y') 2nx( Ax=" yr) + 2n A TTy x 11) < xl+1 + x 2x*) n X n'1 + y² -2y") = 0. (21)
17

---

Published as a conference paper at ICLR 2026
Equivalently,
8 ( ,0 E (x', y²) + +2n(v" Im Ax", 3²) (n y¹ -v"in, xet1)
+ +n(r"' x't1 + x² - -2x") + 11(21, y + yy - --y") =
(22)
Note that yy Ax" < n² (y') Ax= S (1²)) Ax V x E An, A. implies that Ax S v 1m
and A y 2 v"In. Therefore, we have
E (xx+1, ,(th) -E (x', (x''8') v²) + n x141 + x.' 2xx) + nT(2² g - yy -2y) s O.
That is.
E & (alt1, )(t 2 n7> xtt1 + x² 2xx) + n7(2" yi+ + y² 2y").
If additionally the game admits an interior NE, we have Ax = I'1m and y³ = v² v'ln. There- fore,
& {aa, v²) - E (x.' y =n(r", # + x' 2x*) + ,n(( y²+! y¹ -2yy)
(23)
Combining Eq. (23) with Lemma 7 (whose second item requires the presence of an interior NE)
completes this lemma.
Now, we are ready to prove Lemma 2 Recall that
= y², x'-1 - x²) + n7( Ax g - 3²) || 20112 1/// - 30122
=(-nAT yy x111 + x., x1+1 x²) + (nAx(+1 yetz + y', g - -z²).
Lemma 2. Assume that the bilinear game admits an interior NE, Let {(x', o",,. be a se- quence of iterates generated by Algorithm with S TAlla min (minse()))) 2i minje(m] uz Then, have
0 S r. S E(x,, ,y¹) - Exxtt,, ,
A4 0.
Proof of Lemma
2 By Eq.
18) and (In, x²t1 - x²)) =11 (Im y2t1 4²) = 0. we have
'< TTy yr t11 x²) ||at-11 x2 =0²122 (mrr' xx x²)
(Ax (1 yt y²) - 42 - 2 { (n11, y 44 - 2))
On the other hand, we have
(in',, ++1 + x. - 2x²) - (170" xx - x²)) = 2(m x² - x0-) 20 0
(n12, y ++ + y² ) - (112t, 21 n²) = =2(12 y² 3") 20, 0,
where the inequalities follow from the second item in Lemma and inequalities yields
Combining the above equalities
A y¹, 2 - -x²) | x. 1/ < (1r7", 2+1 + x² 2x.'
(24)
Ax*x ytt1 )²) |1y y" p1 < (nd', n²1 + y² 2yy"
Summing up the two inequalities in Eq. 24 by Lemma & we obtain Lemma 2
Then, arrive the O(1/T) convergence rate.
Theorem 1. Assume that the bilinear game admits an interior NE. Let (w0,, "lae",y))) o,, be a se- quence of iterates generated by Algorithm with S we have
T min (min.e 27 minje(m) Vz Then,
DualityGap
1
Σ
T
Σ
T
9 + 4n || AAlp
(25)
T
T
n/
t=l
t=l
18

---

Published as a conference paper at ICLR 2026
Proof of Theorem 7 Summing up Eqs. and (4) we have
1) (y) T Ax ( Ar) + 1) (y Ax (y') AAx)
< (x. 3) 0r+1 (z. 8) + 4/ (x, y) 1 1
+ n Axxt11 t1 y²) nn( A T y² xxt - x²) - -1|2 - 20/12 -11ytt1 -2/122-
By Lemma 2 we obtain that
1 (yy Ax +1 - (y )
T Aw) + 1 (y' Ax' - -(y') (Ax) s
0x - de+1 (z. y) + dh (x. 8) + (a. y) + E (z', v²) - y(th). (26)
Summing up Eq. 26 over 1 -= 1,.... T plus Eq.
for L = 0, we have
2n y Ax' (gy) Ax) + 17 (3) Ax Ax
(y) ( Ax)
5 ( y) - 0T+1 (x. y) + U (z. 3) サтー (x. y) + 3 (xt 3²) - - (x=-11, . +1
1 マ x² 2012 1 y -001/
+ Φ0 (r, y) Φ1 (zx, v) 7 Am vy /²)
< (2. y) ( y) + 12 1r+ (x. y) + E (x" yz²) 8(x" "."-."""
(Ax', y' yy))
This inequality gives the following upper bound:
A
Σ
x'
7 E )' Ax
T Σ 1=1
y Ax' - ( 1
C(x,,) y)
(27)
T
T
21/T
t=1
where
=( = 2ol(x, 3) Ør (x,, y) 1h (2x - + (x, y) + Ex0 y1²) E (1x+t1 ,y TTt1
- TH( Ax yy' - y²) - 1/ (y Ax T+I (y T Axx)
Va, y E Am x An.
For any x E An, y E Am. we can bound each term in C(z,, y) as follows:
Φ0(2, y)
1
x
x
11
+
1
100
2112 + 7 Ax S4+ n||
2
-01+1(0 y)
1
x
T+1
2
y
T+1 - v112
n T+1) Ax 1/|A|12,
2
2
(x) = x
+
y4
2112
1
v 301 < 4,
2
2
2
(28)
/// (z. y) = 2
T+1
x
1
2
+ 2
+ 2
1
1 T+1 y² || 22 2,
2
E = || x
1 + 11
1| 7 ) A <8 + 7/1-A112
x
-8 (2
+) = - || T+1 x=
|
T+1 y
2 7( (t) T+2 < A/l
and Ax y yo) > - 17 (y)
T T+1 - (yT+)) Ax)
< An|1 where all the inequalitics
follow by Lemma Therefore, we can bound C'æx, y) by 18 + A 1lz By taking the maximum
on the both sides of Eq. (27). we complete the proof.
C ADDITIONAL RESULTS IN SECTION 5
In this section, we provide several additional results implied by our main results in Section 5
First, we notice that in harmonic games (Candogan et al. 2011). the uniformly mixed strategy profile is always a Nash equilibrium (Candogan et al. 2011 Theorem 5.5.). Therefore, as a corollary of Theorem I we have
19

---

Published as a conference paper at ICLR 2026
Corollary 1.
In harmonic games, let {(x', .y') t==,..... be sequence of iterates generated by Al- gorithm with S T min ni }.) starting from any initial point within An x Am- Then, the duality gap of the averaged iterate converges with a rate of O(1/T).
C.I "INTERIOR CYCLIC TRAJECTORIES" INDICATE INTERIOR NE
As additional result, show that detect the presence of interior NE via observing the trajectories of AlGGDA. In particular, the presence "interior cyclic trajectories" indicates that the game cannot admit non-degenerate non-interior NE.
Here, we adopt a strict definition of "interior cyelic trajectories."" Specifically, we call a trajectory an inferior cyclic trajectory if (1) it evolves along periodic orbit, and (2) it remains strictly in the interior of the simplices. Formally, we say AltGDA eventually exhibits an interior cyclic trajectory there exist T,
such that
(a', 3²) (x y)*+) for all T; rd O,, and X On for all > T:
. for any i E [m], there exists t; > T such that x; > 0, and for any j E [m], there exists t, T such that 1 > 0.
A Nash equilibrium is non-degenerate if (Ax"); < V² whenever yī = and (A y > V whenever x; O. With these notions, present the following lemma.
Lemma 9. If AliGDA eventually exhibits an interior cyclic trajectory bilinear game, then there cannot be any non-degenerate non-interior NE in the game.
Proof. We prove this lemma by contradiction. Suppose that there exists non-degenerate non- interior NE (x', Let E'(x', 3²) be the energy function defined w.r.t. (æ', y²) in Eq. (Energy Recall that, without assuming an interior NE, we have Eq.
(22). i.e.
E' (x'"1 y )) - -E' (a', y²)
) + 2n(p"" 1m - Ax', y²) + 2n((ATy - -vv1, In x. x
+ 7(>", x. + x. - 2x') + n n + y -2yy) = 0.
(29)
Given that x On, X' Om for all >> T, and Ax! S v and A A ' v² v',, we have
E' (a*+1 y +) I E' (a',y") VI>
Further, with non-degenerate non-interior NE there has to be at least an i' j' such that (A y')) > v² or (Ax')y < v². Because of the third items in the definition of "interior cyclic trajectory", there has to be least one iteration per period in which
7/v"1, Ax', y²) (AAA y ~v11, x'+))> 0. Then, by the second item in the definition of interior cyclic trajectory, we obtain that (a", y²) < & (y0)) A1> T,
which contradicts the first item in the definition of interior cyclic trajectory.
C.2 AN ADAPTIVE STEPSIZE RULE WITHOUT KNOWING THE NE
In this subsection, we design an adaptive stepsize rule that searches for an admissible stepsize. With this rule, without knowing any interior NE, can still set up the AltGDA algorithm and achieves O1) convergence rate. Additionally, this rule allows us to start with an initial stepsize that is potentially much larger than the theoretical one, therefore might lead to better performances in practice. We present the AltGDA algorithm equipped with this adaptive stepsize rule in Algorithm Theorem 3. Assume that the bilinear game admits interior NE. Let {(x', .y") y') be quence of iterates generated by Algorithm 2
with an initial stepsize 17 S T Then, we have
C
DualityGap
(30)
T
T
where 17" = |||||= min (min 27, min minje(m) 3. (x","") any interior NE, and C [log2 (1/) [ (9 + 51 Al12) + (18 / (112)-
20

---

Published as a conference paper at ICLR 2026
Algorithm 2 AltGDA with an adaptive stepsize rule
input: number of iterations T, initial step size 17
initialize: (x"; yy) X' x Vnn = r7" T /sum = 0
for t 0, ...., T do
x . (x' n A y²)
g²+ lyy + 1r'
Compute r; via Eq. (5)
rsum ssum + rr
if' rsum > 8 2n7 2/ ||
then
n = /2/²2
ssum 0
else
n n
end if
end for
output: ( ET= x¹, 1 ( Ex
Proof. First, note that the stepsizes are monotonically non-increasing, thereby nf' S 77 for all f 2 0. Second, if we are using an admissible stepsize, i.e., stepsize 1) satisfying 7 1/" Then, by Lemma 2 the residual terms Yz (defined in Eq. (5) is summable and (by the same bounds as
in Eq. 28
T Σn TI S 1(0 3d) E(x T+ y T+) < 8 + 2m 11//2
Next, we denote la the k-th time point at which the stepsize shrinks (by 1/2). We call the iterations from 0 to t1 - (inclusively) as the O-th epoch, and the iterations from t4 to fx+1 - (inclusively) as the k-th epoch for k 1.2..... Let 17" denote the stepsize across the k-th epoch. Let K denote the total number of stepsize shrinkage before we find an admissible stepsize, i.e., 11 = i S 11". It then follows that K < [log2 (n¹/n) (n))"))] and the final stepsize ό 2 n /2. Then, we consider the following two cases:
(the first case) For all l < K - 1, i.e., for all i such that ry* 11,,, we have
1++111
2
Σ
n (TTAx* Ax' (1') Ax)
r² (y) Ax - (T Axx) + +1 (y Ax
(1 Axx)
>' 1+41-1 t= n/ (y) T Ax (g')T Ax)) n² (y Axt+1 (1a+ Ax)
1411-1
(0,(0,y) y) 1liz+ v) + Φb (x, 3) 0le+1 (x, y)
Tt
(by Lemma
S/h (z. 1/ett1 (x, + Φe (x. 3) 0ie4: (x, 4) + (8 27 (1All))))) 2
<10 + |||||| + (8 + 2/y A 1| + ((7 |1
(31)
where the last inequality follows by the similar bounds as in Eq. 28 To show the second last inequality, first by the stepsize shrinkage condition, we have the accumulated residual terms are at most + 27y ||
2 + where rt for all Then, we obtain F as follows:
x²) <n |/ y" [2||= =x'12 + A| ++1 12 12lly'11 8112
mn> (AATAT A y² - _x") + n7² Axx + x²) ||
x 1|2
11
32 112
<n ||A y I2 - ' AT=
y¹ - x 20112 + 1 112ll2/ + Ax
v21l2
<2AA
<2(n)) 11
21

---

Published as a conference paper at ICLR 2026
where the last three inequalities follow by non-expansiveness. the forth item in Lemma 5 and ny' 1 r7" for all 2 It then follows by Eq. (31 and the third item Lemma
5 that
1441-1
Ck 2T 21¹*
Ck
Ax' Ax' y
(z')
Az)
-
S
where C₁: = 10 + 2-/2 11 + (8 + 2n/ (1/11) + || + 4nj² ||
(the second case) For l K, i.c., for all tx and ك 17" the regret will remain finitely bounded by the same proof as in the proof of Theorem Specifically, we have
Σ
T
y
Axx
(T')
Ax) v
C(æ, y)
<
C(x, y) 18 87
20j
Let C = m ......KKK K C₁ < 18 + 10m0l| ||Al22 Combining the two cases, we have
T (v Az' - (v') Ax) v
'70 ) 17"
18 + 10, ||
18 + 81/11
log2
(32)
2n"
17"
==0
We completes the proof by dividing T and taking maximum over (x, y) E An Am on the both sides of Eq.
(32
D OMITTED PROOFS IN SECTION 6
In this section, we introduce some additional notations to facilitate the proof. We already define
1" (i E [n] x > 0} and J = {j E [m] yz > 0} in Section 5 Analogously, we denote I' = (i E [n] | > 0} and J = (j E [m] vf > 0} for all t. 2 0. For conciseness, for any t 2 O,
we introduce the following vectors to denote the "projected" gradients for a pair of (x',y')
0² = A y + Σx (A 30) 1n
(33)
Er (Ax"))
u' = Ax
1m
17
Note that EiE(n) of E jElml u. 0. Recall that IIs (u g) uutg 1/ (1T9) 1a for any
u E Âs and g E Bdd Beck 2017 Lemma 6.26), thereby we have II (x' - "yATT²) = x' + tyo" mut+1 With o' and u', we can also write the nonsmooth parts of
and IT (y' + Ax.
y
the iterate updates 7 and X defined in Eqs.
13 and 144 as follows:
+ ny ++1
17
(34)
A y' + ny nutt11
y ++
Additionally, we define
7' max of and X max A5.
(35)
.Ein]
jE(m)
In this convention, the update rule of Algorithm Caan be expressed as
c+1 = x + njo" 177
(36)
y ++ = yy + +nu ++ n
We start the proof of the O(1/T) local convergence rate with the following lemma. This lemma captures useful properties of r² and A1.
Lemma 10. For any t 2 O, we have 7 x 2 for all i E 1++1 and X = X 2 0 for all
j E J++ Furthermore, if o < 0 for some then hi!l < luil, similarly, if X1 < 0.ror some j then |N < 1.
22

---

Published as a conference paper at ICLR 2026
Proof. Note that ryy" x' tno II.. (z' + ). By the first-order optimality aitforrderotiimmme of the minimization
problem corresponding to III.. there exists unique such that x max(#t + mot T, 0} for
all i E [n]] (Sce, c.g., Page 77 in Held et al. (174)). Note that T 2 0 because
Σ aE(m)
Σ iE(m]
max + not - T, 0} 2
Σ kE(n]
(of + toe - -r)==1 n5;
where we have used Eie[n] of = 0. It follows that m. = o + noo - m + +nof - T, 0} S of mot (x) + not n - 7) = for all i E [n]. Moreover, if + > (i.e., i E [ we have of = xt + not - T thus mnf - 7. As m7 S T for all E [n] and mn! T for all i E 1[t1, we have T = '7.. Symmetrically, we can show X3 = X for all j E J++1
To show the second part of this lemma, we consider two cases: 51 > 0 and gt 0. We first
assume 3" > 0. If of S 0 for some i, then we have that n = x; + not -m 2 x; + net- On the other hand, because z,+1 = max( + nut - -77, 0} and x; + qot - -1y < क + mut, we
have =x=1 0 = x² + got mf and therefore x; + nuf < 0. Since x! 2 0. we have of S 0.
Also, it holds that 177; = st + not 2 syof, This implies hill S |u as 7 S 0 and of S 0. For
the other case in which 7 = O. by the definition of 7t we have yf S 0 for all i. Then, we have
of + muf - mi 2 o + not for each i E [n] and
Σ
Σ iE(x)
x + nut - m. 2
Σ :E(m]
x + mou = 1,
iE (x)
which implics Eiein) 7/- = O. Because of - 0 for all i e for every E [n]. Therefore, In1l S |uğ| holds trivially. Symmetrically, we can show A1] S |u] if 23 < 0.
[r]] when 5f = 0, we must have 7f =
Recall that, the value of the game is denoted as min:(A (AT yy): = maxx (Ax"), and the game- specific parameter is defined as
y')) v²
V¹ - (Axx)) min #t, min vi }
8 min min agr
min JEJ
(37)
||Al|2
||ll2
ies
JEJ
This parameter measures the gap between the suboptimal payoffs to the optimal payoff for the both players. In particular,
(A y )4 2 0" + (A
Vigr" Vj & J
(38)
(Ax"), , 5 -5--51144 5|A
Now, we present the proof of Lemma In words, this lemma says that if the current iterate (a. y) in S, then the components H; and yy corresponding to I and J are kept bounded away from zero; and other components monotonically decrease and approach zero. In a high level, this lemma provides the monotonicity we need to finish the proof.
Lemma 3. If the current iterate (x, y) E S, and the next iterate (x+, ,)) is generated by Algo- rithm with the stepsize 1) < 2T then we have
1. xt x; 2 2 for all i E I* and wtt Mj 2 $ for all j E J
2. xt S for all i & I* and vJ I by for all j & J
Proof of Lemma 3 To keep the presentation concise, we only prove the "x" part; the "y" part can be done symmetrically. Because y 32ll2 < $. for all E [n], we have
8 - 1141222
(-(AT)) v), (A  )4 || A Avl1
(39)
As a result, for any i E 7", we have ~" = v)) : = (A T y )r, therefore
IAA "): + (AT v) < (AA " | + + - T y 12 + (A g)rl - 8
2
(40)
23

---

Published as a conference paper at ICLR 2026
This further implies that
U/y S ii + 6 2llll Vider..
(41)
Moreover, for all E Ia and r.
39
38
59
5
(A y) (A y 4
||ll
yA'y') 8||A||2 + 4 1lAlll = (A y) -11AA12 +
2 211A1l2
2
6
(A y)v
2 11A
Equivalently,- -(A y)v S -(A y); All and therefore
6
uy S U;- 2 21 S 12
vier,eer.
(42)
Next, we show that v; - 7/4 2 A| for all i Is by contradiction. Suppose otherwise, we have
0/- 7 I Us % < -11Al11 for some i E I" Fix this E 1. Then, for all [n]] such that
27 > O, we have
8
2t xe + 1p 17 S de + nu; 2 27lll11 177 zt;
where the first equality follows by Lemma 10 and the first inequality is implied by Eqs. (41) and 442). This leads to Ere(m) z Ets) >0 Le Eex/ 20 20 S Eie(n ze 1 and thus contradiction.
Then, we can prove the first part of the lemma. For each i E I", since - 7/4 2 -111 and
0 17 ||l have ny, 77% 2 -4. On the other hand, since |2; x || x= 1122 S 2
have x Thus, - x, + 17u; 777 o/ > 0 for all E I*. By Lemma 10 % = 7 for all i I".
36 where the second inequality follows by the definition of 6.
To show the second part, we first provide a lower bound for 5. Observe that
1|AA|12
1
(xr x3)
Σ
(at
vx)
(187 177 (n 17
(43)
2 n
iEI*
iEl
where the inequality follows by and maxigr 24 < 1ll ||"
a 1116..
8. By rearranging terms,
Eq. 443 yields
| 2
| 2
min 1E1
1'
Then, 2, <. x4 for each i & 1 can be shown by contradiction: suppose that x, > x, 2 0, then
by Lemma 10 we have 7/ = 7 and therefore x; Iz 170 1/5 S zs. which is contradiction. O
Recall that, for case of presentation, we define a variant of the energy function, V An X R. as follows:
Vxx v) ||= x 11 y y 11 nL y') A(x x²).
For simplicity, we also use a shorthand notation
> = (²
(44)
Then, we derive upper bound for the difference of this variant of the energy function.
Lemma 11. Let V₁ be defined as in Eq. (44). where ((x' y T'zo be a sequence of iterates gener- ated by Algorithm wiith stepsize 17 > then the change of the energy function per iteration satisfies that
AV; == V - V, < -n(r" xt+1 x' -2x") - n(Xi . y + y² -2y")
< -11 x²' x²)) - miia v¹ -y").
(45)
24

---

Published as a conference paper at ICLR 2026
Proof. By Eq. (6), we have
(xlt1 x² - 11p0 + -pp x x - -2x")
(46)
y y' - -nm -nutt1 1 + n1,1 ntth + y¹ 2yy") O.
By Eq.
33 and the fact that xtt1 x²,x" x E Dn and y .y', y
E
A Am we have
(In, x²+ x² x²) (Im; nt+ 1 + y¹ - 2y )- 0, which leads to
(v', x1 + x² 2xr) = = (ATy x ++ + x² 2x."
(47)
(u't1, yttl + - -2y") (Axlt1, y + +yy - 2y
By using Eq.
47 and (a b, b) ||al|3 |1b122 for any vectors a, b, is equivalent to
that Eq. (46)
x x
11 ||''=='''"" x x- +
y², x1+1 + x² - -xxx) +n(rr x111 + x' - -22") = 0 (48)
| +1
y" 1 1ly y 112 7 Ax 4t + +y - -2y") +m X², ytt + y - 2yy = 0. (49)
To derive the energy change between two consecutive iterates, notice that
r A y¹ x + x² 2xr) 17 Ax 8 + y² oy-"
=nly² Ax") )- 27(y' Ax') 7/y 1+ Ax + 2n/ Ax
=n(y² yy) T A(xx - xx*) - 7/8", Ax") - n/1" Ax") - 7/ Axx)
-n( ++1 - y² A(x xx') - -n Ax") ) + n00" Ax") + nly" A
=n(y²= y¹) A(x' - x²) -ny 4²) -
A(x xx")
+ tn y" x + 2111) - n/AA" ny +y t1
(50)
and
(1A y" x.' + n +11
AAx y² + +y 111
n(A Tyy "²" v² In xx' + x(t + nnn(v" Ax" y + g(th) 2 0.
(51)
Summing up Eqs. (50p and 51). we have
( A yy, x ++
+
x²
2x
ny( Ax 111 + 88 - 2y""
2 nyy -y²) " A(xx
xx") "
n1 1+1 11ytt1- yn) A(x 1+1 x*). (52)
Combining Eqs.
49 and 52 and the definition energy function V., Ve+1, we have
V++ S V. <(r" xn [+ xx 2xx" n y 1+1 + 3² 2yy).
Additionally, by Lemma we further have Eq. 455
By leveraging Lemma 10 we can derive the following identities regarding the right-hand side of Eq. (45).
Lemma 12. Let y, X, 7, X defined as in Eqs. 34 and
35
Then, we have
(r' x² - x²) = Σ igren (ot - -x) - x;)
(53)
(X' ".'"" y²) =Σ i (0; 2)((z) n₁))
25

---

Published as a conference paper at ICLR 2026
Proof.
(7,, x² - x²)) =(r², x' x + (7,, x²t1 xx")
Σ igrr-1 Naj + Σ igtce M(x1 - x ) + (7' x²t1 - -x")
Σ iggre Nay 5/ Eignen (0) - -2 ) + (n'
xtt x²) (by Lemma 10
Eien- Nag (1 ((1-E,e E x1) (r/ x x²)
(by the definition of I I
E Nags - 5/' E iggee= 2 + (77 x 1+1 x²)
Σ Lignri (9 -7))a + (7' - -5'1n x²+11 x²)
(by (1, x x²) = 00
Σ igrr- (9 7/)x Ener -5)) x;
(by Lemma 10 and the definition of /=+1)
E ( (0) =x))-
(54)
Symmetrically, we have (Xe, y¹ y²) = Ejant (x)
If the game does not have an interior NE, then the right-hand side of Eq. (45) can be positive for some iterations. That said, the energy function is not monotonically decreasing. Even though, as shown below, by exploiting the local property we can derive that the sum of the energy increase has an upper bound, and hence we still obtains an (1)/T) convergence rate.
In the rest of the proof, provides the proof of Lemma 4 to formalize this idea, and then conclude the O1/TT) convergence rate by an analogous argument as in the proof of Theorem
Recall that
S. = {1xx y) 10|l
5 g.
8 max
2 Grao, maxy; S G G cs 3EJ
x x2112
1y
11
8' o
where e min(1/|AAl2, 1-2 192 1-2 always stay S.
Lemma 4. Let {(x², y²) h22 be sequence of iterates generated by Algorithm | with stepsize 7 2|[A|| and an initial point (æ.,, gd) E So- Then, the iterates {(xr', y²)) stay within the local region S. Furthermore, for any T O, we have
== ((7', x' - +='++('', v' -1")) <
1
82.
128
Proof of Lemma 4
We prove the first part of this lemma by contradiction. Since (x. yy) E So C S. by Lemma 3 as long as (a*", .y"") E S for all t' < t,, we have that
|||
i < x <
Vigl"
2
1/ A|
2 Ty
VJ
Suppose, the contrary, that there exists time point 0 such that (wr y²) leaves the region for the first time. Then, the above observation implies that at least of I|a= xx" ll2 > & and
26

---

Published as a conference paper at ICLR 2026
11y 121l2 6 happens. Therefore, the energy at the t-th iteration has the following lower bound:
V. ||
x² yy 30 1| n'y" y²) "(xx' xx))
|
x= ||v" y" 1| n||A|12||>d -x5=xx" x= 11412|/=''=>0"/
12112l110* -y²l12
allAlla
|
x
11 + ||y 4 11
2 (1|=' x= 112 ++11// y 12)
1 ||
3
x=
122+
3 y/ 10
3
8².
(55)
4
64
On the other hand, the initial energy is guaranteed to be sufficiently small. Let Vo be the initial energy corresponding (x",, ")) By definition, we have
Vo= x x²
1 + 1
y
ny ---" A(x - --=TAAxx"
-x")
xx
12
+ 0/ yn
1 +n1lA11211y" -2'1221000 -x=1la
8 2
8
2 + 1/| Alla
5
+
+ A|l
8²
S
5².
(56)
8
64
128
By Lemma 11 we know the change of the energy function AVR is upper bounded by (n(2> a= x*)
' X* y -y") for all k 2 O. As l denotes the first time which the it-
erate leaves the local region S, for each k = O...., - 1, we can further bound AV, as
AV. < - 7/(7", x² -x-) n((a, 3² -2"
(by Lemma 11
= Σ Eiennn (nt (at -xi) - E Engnen (1) - -Z0 vf)
(by Lemma 12
- Eiggerseee (71 - ) - =n Juggeis "EJ (1/ - -xtx(
(by Lemma
(7 - [ + Σ pegget (*+
(57)
ig
The first term in the right-hand side of Eq. 57 can be bounded as follows:
Σ Eagi ier (1 - -+))
Σ Enggitt ier ot (7th -;) + E Enserneer ser (5* - -)t)
Sn inght Jgr 20
x/a + Σ Emgenneents (s* + +n1t)a
(58)
To derive an upper bound for Th we observe that (a* v*) E S for all h E [0, 1].
Thereby, 3 that a > 0 for all illiEn! 1*. Then, we have u/421 = ox + muo - ViE
I" Summing up this equation over i E 1", we have
I 1yr
Σ ser. (at 2 =xtt1) + Σ sE1 of
> NET |o! x + Eier.lof 1021
x0 ||2 + 1/ || ||2
< 2 T" |n|
where the last inequality holds because
(a)
1x- 6+1 - x² 112
< x - 7 T nx 00112 A111AA1/
0 ||2 = - (A" T n²
)
+ - Σn
1
(A )0
$1AA y 122 S 111
27

---

Published as a conference paper at ICLR 2026
where (a) follows from nonexpansiveness of projection onto closed convex set. Therefore,
obtain 7t < 2|[A||2. On the other hand, by Lemma 10,
In" I |oo|
I || 2 S || 2 for each
such that N S O. Combining the above results, we have
E
-+-))aa - 3|
Σ
=
= ||
E EEE SEEI" HEI
Nig .gr
NEE Ser
Notice that, by Lemma 3 I k+1 I I for all i & I' and l E [0, t 1]. Hence, there is at most one
k E 10, - 1] satisfying E I & 1 for each i & I". Also, of S gra I 354/7-1 52 for all
i 1 and & [0,t-1] 1]. This translate
Σ K= Eiggettiee
E
(5+ -
1
S
Σ
Σ
||
k=o ts 1 a .gr
$
21|A|12 (n - 1111)311A112
1
1
8²
1
8².
[ 384
256
A symmetrical analysis gives that
Σ Σ (5* - (5
-
1
(m - |J 1
Ty
8²
8²
2||A||2
|
384
256
A= joj (jj
Therefore, the change of energy up to is at most
62
V1- Vo-
AV
Σ
(f--))at +
Σ
(A* (5*
S 128"
k=
k=0
JUEJ jE
(59)
This contradicts Eqs.
555 and 56
Because (ar", 2²) for all f 2 0, i.e., the condition in Lemma is satisfied by all iterates generated by Algorithm with stepsize S 2||A|| and an initial point (x yy) E So. one can then verify that the upper bound in Eq. (59) still holds for an arbitrary 2 0 by the same derivation as above. In this way, the second part of this lemma follows.
Theorem 2. Let {(x', (le',y" k2) be sequence of iterates generated by Algorithm with stepsize " 2 2 and an initial point (ee", =0)) E So, where So is defined in Eq. (7. Then, have that
DualityGap
1
Σ
T
Σ
T
y²
S 9 +
9
7r/ + (82/128)
(60)
T
T
1/T
1=1
where 8 is defined in Eq. 6
Proof of Theorem
2
By Eq. 36
we have
- 4¹ x 1+ x²)
x
+1 x² 112 = (-nAA T '²² - -x'-1 1- + +x', x 1+1 x²)
1//2" x+11 -x")
'/7" r11 x." -2x") ) - -27/(7² x²' - -x") (61)
Axx - x²) -²) -11y
3'112
(nAxtt1 - -y + ,3" - -y²)
= '1\' yr - 11")
= nTA", y4 + yy 1 -2y") -2n 32 -y)) (62)
By Lemma I and Eqs. 61 and 62 we have
n (y Ax (g (1)) Ax) + (y Ax - (T²)TAz)) Az))
I -0041(0, 3) + dr (x, 3) (x, 3) + th (x, y)
+n/r', glt1 + x² - -2x") 2n(7', x²' x²) + t ntt + --22-y") (n y² --)"))
28

---

Published as a conference paper at ICLR 2026
By Lemma 11 for any I. y E An Am and t 2 0, we have:
n7 (v Ax ++ - (y +1 T Ax) + 1 (y" Axt - (v'') T Aar)
$ - -- (x, y) + 0e (x. y) - (1 (z. y) + 11(2, y) + Vt- - V4+1
-2 x' - x²) 2n(2² y' - y²)-
(63)
Recall that (x. y) := E/1z= - æ=122 + E1ll'' - -yll + n T Ax and (x. =- E11,²² - -x112- +
b ||ly"r - -yll2 E1ly' y 1
Summing up Eq. 663 over / = ,...., T plus Eq. (4 for ( = 0, we have
T
20 y Ax' - (Ty)T + (y) Ax T+1
1=1
<hi (ar, y) - Φh (ae, y) + wh (a. y) - 1b++1 (at; y) + Vi VT+1 + 82
64
+ do(2x y) - Φi (ac, y) (Az', y² --"y") 10ee -x0 x²112
2 y y 1012
1
<ō0(0, y) oT+1 (zx y) + 31 (z. y) U (x, y) + V1 - VT+1 + mn((Aa ' yy - yy- + -2002
1
8².
61
This inequality gives the following upper bound:
T y T
T
T Σ 1=1
C(x,, y)
A
Σ
x²
yy
Aa = T
y Ax' - -ty') Axx)= <
(64)
T
2n/T
1=1
1=1
where
1
C(z, v) = ( 3)
-r- (x. y) + 2// (x, v) - + (x., y) +V- V/++1 +
82
64
+ m)(Aa 3 - -²) -n (y Ax T+1 - (1)+
T Ax)
V xx y E An x An-
For any x E An,Y y E Am, we can bound each term in C(x, 3) as follows:
Φ0 y)
2 1000
==122 + - |1100 - 01(2 + mT(²)) T Aar S 4 + nill
- - (xe, y)
2 x0e T+1 =l1²
_ | T+1 1--1-ylla
y1
7 + Ax S n||A|2,
2
V/ (2x, y) = x
+ 11100 - 2112
2 | 01 S 4,
1
-1hT+1 (2x, y)
x T+1
2
2
1
+ 2112
+ 2 1 T+1 y < 2,
2
2
Vo= ||000 0
x: 112
|100 0
v 11
7y y²) TA(A"" A(x²" -xx) $8 A//|A||2,
-VT+1 -1 T+1 x
11 T+1
y 12 n(y T+1
T+1 11 T A(x0 x²)
S 44/1 All,,
and AmxAarr 1/ ) 17 (y T Ax. - (IT+1)T Am) < 41/1 where all the inequalities
follow by Lemma Therefore, we can bound C(x,, y) by 18 18 14m|||||| All2 + 82 82/64, By taking the maximum on the both sides of Eq. (64), we complete the proof.
E SDP FORMULATION OF (INER
In this section, we reformulate the inner problem (NNER) as a convex SDP by using results from
Taylor et al.) 2017a; Bousselmi et al. 2024). We use the following notation: write @(x, y) xy + yz 1/2 to denote the symmetric outer product between the vectors æ, y E Rd For a
symmetric matrix M 0 means that M is positive semidefinite.
29

---

Published as a conference paper at ICLR 2026
Span based form of A First, present equivalent form of AltGA, which will use in our transformation to keep the resultant formulation a compact form by decoupling the iterates and their interaction with A. To that goal, first recall the following definition.
Definition 1 (Indicator function and normal cone of set.). For any set S R", its indicator
function (r( is O if x S and is oc if x: & S. For closed convex set C C R", the subdifferential of its indicator function (also called normal cone), denoted by dôc, satisfies:
- 10 (y - y (= x)) for all = EEC
i $
(6c(x)
ECC.C.
Define an arbitrary element of (2) by &g
Lemma 13 (Equivalent representation of AlGGAA,, Algorithm 7 can be written equivalently as:
1-1 LE (1,
w' = σ
(x((0)))
Σ
j=1
1=0
y¹ = y Σ 8y(r²) ) + Ep', p',
tE (1,2.....
(65)
j=1
p' Ar', LE (1,,,.....
q' = Ty. 1E (1,, (1,2....,77
Proof. Recall that for any closed convex set C, we have p lc((x) if and only - (x))) for some (p) E (5c(p) (Bauschke & Combettes, 2017 Proposition 6.47). Using this, we can write the z--iterates of AltGDA as
x ++1 11x (x' - -nnA -²)
<xx 11 x' - (xx(x4+1) n
'¹' for some (x E 06xx(x+1))
which can be expanded to
1-1 te (1,2....,77
Σ 8x((x)) - Σ A ATy.
(66)
j=1
1=0
Similarly, we can write the y-iterates AltGDA as
+ 1ly (v' + +1)
++ yy -8y +2) + nAw where (1 E (6)
leading to:
y' = y0 Σ (3 +
Axd (1,,,,
(67)
j=1
Finally, setting
D¹ = Ax',
LE (1,,,....,
9' = A ATy LE
(66) and (67 we arrive at 65
Infinite-dimensionall inner maximization problem. For notational convenience of indexing the variables, first write == 20, y 3 and merely rewrite (INNER) as follows:
30

---

Published as a conference paper at ICLR 2026
maximize XCR" JCR"" .
- ((g9)A Ax" (Ty')
(a (o"),,t.........)......
m.nER.
subject
Pr(n) =
X' is a convex compact set in R" with radius 1, is convex compact set in R with radius 1, A E IR=x has maximum singular value 1, ((x', y²) (' are generated by AltGDA with stepsize from initial point (æ" y X x x
(INNER)
(x y EXXx
Using Lemma 13 and by denoting pd Ax and qº =Ayy write INNER in the
following infinite- chinte-dimensiona form:
maximize
T E ((q9) ( TT)
XCR" W/R AER m (e'):e(0.......7..... ( (e(.0.........) CRm
m.nEN.
subject
X' is convex compact set in R" with radius 1,
Pr(n)=
y is convex compact set in 1n with radius 1,
(68)
x² x Σ - 0 q',
t (1.2..... T tE (1,2.....
y² = yd - -ド== (3 +
A E Rm has maximum singular value 1,
pe = Ax", 1 1,,,,,,,...
q' A y', LE (0.1,2..... T}.
ATy
(x y e
Interpolation argument. We next convert the infinieediimensional inner maximization problem (88) into minen-dimensionl (albeit still intractable) one with the following interpolation results. The core intuition behind these results is that a first-order algorithm such as AltGDA interacts with the infinite-dimensional objects X, V, or A only through the first-order information it observes the iterates. Hence, under suitable conditions, it may be possible to reconstruct these objects from the iterates and their associated first-order information in such way that, based solely the first-order information, the algorithm cannot distinguish between the original infiniteddimensional object and the reconstructed one. The following lemmas show that such reconstruction possible our setup.
Lemma 14 (Interpolation of convex compact set with bounded radius. (Taylor et al, 2017a Theo- rem 3.6)). Let be an index set and let {æ² .e' g')"")e hiez IRd Rd, Then there exists compact convex
set C C IRd with radius R satisfying 8x((x") g" for all E I if and only if
(g') <
[x x²) 00 Vi,jEI
R Vi
Lemma 15 (Interpolation of a matrix with bounded singular value.
(Bousselmi value.
et al. 2024 Theorem
3.1)). Consider the sets of pairs ((x', .ae,,')) (e),,.1 C R R. and {(y), q') (e (1.......TT) S
1mm x R", and define the following matrices:
= a
Til E Raxxi
= Ip
p²
p E mm
Y = ly'
y²
y m
Q
lq' q²
T E R Rux
31

---

Published as a conference paper at ICLR 2026
Then there exists a matrix A Rmx with maximun singular value m (A) S L such that p' Ax' for all E (1,2..... Ti} and q¹ = AAA y for all j E (1.2...., [22 if and only if
x²Q=PTx
-
In order apply Lemma 14 and Lemma
68
define the following for notational convenience:
index 0 is denoted by 1, L { 0,0, 1, T), (x(x') f.. i Ir,
85((') h4 i IT,
X (al x²
... x E RaxT
[p' p²
p"] E R
Y ly
v"1 E R
Q q 1
144
ROXT ERRT
Finite-dimensional inner maxinization problem.
Using Lemma and Lemma 1. and the
notation above, we can reformulate (68) as:
maximize (a' "..'f'''''ee hezp SR",
E 1) p-1)
(v' h. hery CR", m.ENN
subject to
( x²) <0,
i,j EI,
| < 11, iE IT,
Pr(1)
h5 -3' i.j EI.
(69)
1 IEIT,
xt = EE - Σ1-1 q'
(1,,,.....
y = y E h + Σ pd
ic (1,2
(x.) 9' (p') y, i Ir
X PP0
yTy - QTQ=O.
Note that the problem does not contain any is nonconvex and intractable due to terms such f (xx xx') and h, (y/ y²) and presence of dimensions m and variables. Next, we show how (69) can be transformed into a semidefinite programming problem that is dimension-free without any loss.
variable anymore, however, it still
Grammian formulation. maximization form. Let
Next we formulate
INNER into finte-ddimensional convex SDP in
Ha.q [2:
0 f-
fi l... fr q q | E (22
Gz.q H Hu. E (/2T+6)
Hy.p [g n h ho hj I... hr p pp p pp E (2
Gy.p H H E S2T+6
32

---

Published as a conference paper at ICLR 2026
where rank Gz.q I and rank Gy.p I m, that becomes void when maximizing m, do in (69). Next define the following notation to select the columns of Hz.q and Hy.p
x_1 e1 E 2- Xo 62 E R27+6
2
f, c++1 R 2
for i IT.
q = e++++6 E R 26 for E IT:
i-1
X, = X
qj E F
2T for i E f1.2....,
==1
X = x Xg
X1
XT E ((T++))
y-1 = E R
2T
.00 = E 2T
h; c+ E 2T for E IT.
Pi = G4T+6 E 2T for E IT,
y: = Yo h Pj E RT+ for E (1,2..... 7)
Y y- Yo y1 Yrl E (224)))((+2)
Note that X, and y; depend linearly on the stepsize n for i E 21, T.. The notation above is defined so that for all i E IT we have
x² Hu f. Hxqli q¹ Hz
y' Hy.NNr hu Hypphi p' Hy.pP'
leading to the identities:
T
= = Σ Gr..g O (q-1,x,)) fr 3 (V:, ... T Σ ((q 2) 22 (1) p
1
fJ (a' x') = tr 2 6 xf - -2,), h3 (y) -yy) = tr Grp up 3 (h..3: -8,)
||0||/ tr Gr.z X;), 11'0113 tr Gr (y:,
(xt)Tg q² - -p')) yy = G..g 3 [x, 2 q Gy.p @ (p.
x x - p x GG x p G..pP, Y YTy - YTy, Y - Q QZ.qq
Using these identities, we can formulate (69) as the following semidefinite optimization problem in maximization form:
maximize + E (trG 3 (Q-1, tr Gy.p 2 (F,, (Fi,p-1)) 1-1)
Gu. E0 Gy.pES2TH
subject to
tr Gz..
(f.. X, xx) 50, E
tr Ga.g
3 (x,, -150 iE
Pr(1)
(70)
tr Gy.p
① 0h,, --5--- -j)
i Ir,
tr Gy.p
(Vi,y:) -20, iE
tr G O (X,99;) tr tr @ OPr.);) =0, i,j E Ir.
X XTGnqq X X
0,
Y YTG - Q
Gz ż 0, Gy 2 0.
Note that this formulation does not contain dimensions m, anymore and is tractable convex prob- lem that can solved to global optimality to compute the convergence bound of AltGDA numerically for given 7) and finite T.
33

---

Published as a conference paper at ICLR 2026
E.1 DETAILED NUMERICAL RESULTS
See Tables 2 and for the detailed data values for Fig. 1
Table 2: Optimized stepsizes and duality gaps given a time horizon of for AliGDA
T
Optimized
Optimized Duality Gap
5
1.527
0.614
6
1.389
0.555
7
1.632
0.488
8
1.574
0.411
9
1.467
0.371
10
1.370
0.345
11
1.304
0.327
12
1.517
0.302
13
1.454
0,274
14
1.377
0,256
15
1,314
0,243
16
1.262
0.233
17
1.438
0.220
18
1.387
0.207
19
1.333
0.196
20
1,283
0.188
21
1,239
0.181
22
1.389
0.174
23
1.347
0.166
24
1.302
0.159
25
1.263
0.153
26
1.229
0.149
27
1.355
0.144
28
1,319
0.139
29
1. 1.283
0.134
30
1.249
0.130
31
1,220
0.126
32
1.332
0.123
33
1.301
0.119
34
1,269
0.116
35
1.240
0.112
36
1.214
0.110
37
1.314
0.107
38
1,286
0.104
39
1,258
0.102
40
1.232
0.099
41
1,209
0.097
42
1,300
0.095
43
1.275
0.093
44
1.250
0.091
45
1,226
0.089
46
1,206
0.087
47
1.288
0.086
48
1.266
0.084
49
1.243
0.082
50
1.221
0.080
34

---

Published as a conference paper at ICLR 2026
Table Optimized stepsizes and duality gaps given time horizon of for SimGDA
T
Optimized
Optimized Duality Gap
5
1.989
1.238
6 1.450
1.150
7
1.165
1.072
8
1.018
1.009
9
0.877
0.958
0.769 10
0.916
0.684 11
0.880
0.616 12
0.850
13 0.567
0.823
0.527 14
0.801
0.492 15
0.781
16
0.466
0.763
0.440 17
0.747
18
0.417
0.733
19
0.398
0.721
20
0.379
0.710
21
0.362
0.699
22
0.347
0.690
23
0.333
0.681
24
0.320
0.673
25
0.308
0.665
26
0.298
0.658
27
0.487
0.654
28
0.472
0.643
29
0.456
0.633
30
0.443
0.623
31
0.431
0.613
32
0.416
0.604
33
0.406
0.596
34
0.394
0.588
35
0.384
0.580
36
0.373
0.573
37
0.363
0.565
38
0.353
0.559
39
0.345
0.552
40
0.335
0.546
41
0.326
0.539
42
0.318
0.533
43
0.310
0.528
44
0.303
0.522
45
0.296
0.517
46
0.289
0.511
47
0.284
0.506
48
0.278
0.501
49
0.272
0.497
50
0.266
0.492
35

---

Published as a conference paper at ICLR 2026
F ADDITIONAL NUMERICAL EXPERIMENTS
F.1 NUMERICAL PERFORMANCES: ALTGDA VERSUS SIMGDA
UNIFORM
RANDINT
BINARY
100
1014
Duality Gop
Duality GSp
10-1
10-
Duality
10-
SimGDa
SinnDA
SinGDA
Enorr Rango 300 Devi
Error Fange Dest
Enoo Range 590 Devi
ANSDA
32-4
ABGGAA
AIEDA
Eroor Hange 12 50d Dcvi
Erice furge 12 Std Devd
Bro fange 504 Dent
10F
10
16
15r
1."
10
10
10x
100
10
10
30"
109
13
107
101
10
10
15P
10*
NORMAL
LOGNORMAL
EXPONENTIAL
SIMODA
12
Emor Range Std Dev
ABDEA Froo Aange Ond Dev)
Duality 10-1
Gop
Quality Cop
13
10-1
10-7
Rango
10-
Rango
10-5
Figure 5: Numerical performances of AliGDA and SimGDA on 30 60 synthesized matrix games.
UNIFORM
RANDINT
BINARY
30-1
Gap
Duality Gep
10-
12
Duality
SiniSA Bange Devt
SynGDA
10-
Sini 34
Sange
Erer fange
10 10-2
NORMAL
LOGNORMAL
EXPONENTIAL
Smiii
105
Eneer nango Dest
Duclty 10-1
Dival byy Cap
12-3 12
Std
20
Range
AHIDA
AHGDA
Ente Range 50d DEV)
12-1
Emor Range Sod Devt
10
1.5
307
3.44
124
Figure 6: Numerical performances of AltGDA and SimGDA on 60 120 synthesized matrix games.
36

---

Published as a conference paper at ICLR 2026
F.2 NUMERICAL PERFORMANCES: ALTGDA WITH DIFFERENT STEPSIZES
We conduct the numerical experiments for AltGDA in the same setup as in the preceding subsection. For each instance, we run AlGGDA with three different stepsizes: = 0.001, 0.01, and 0.1.
UNIFORM
RANDINT
BINARY
Duality 10-1
Gap
Qualit Gep
10-
ANGDA Inwo..11
10
ARGGA (1.0.11
WIGGA inyb-11
Enor Range tz 50d Dev)
Erice Range la Std Davt
Eror Bange Std Dent
ANGDA (n-d.01)
APG (1-0 011
WIGD4 in 6-33)
Bange Dent
Sange
Enee flange Devt
01-0
NORMAL
LOGNORMAL
EXPONENTIAL
100
305
Duality 16-1
10"
Duality Coo
10-7
12
ANGDA (n-0.00)
10 15
ARGIA (1
10
AMGDA110 --333
bid Devt
Targe
Enre Barge Shd Devl
ANGDA trwe 2013
ARGOA 01-00.00 0013
4IGCA 2013
Errer Range 2kd Deni
Ercer Sange La Ste DaNS
Error Range Std Devi
20a
30
10"
30
1.a
10" 10
127
Figure 7: Numerical performances of AltGDA with different stepsizes on x synthesized matrix games.
UNIFORM
BINARY
302
10-2
30P
Quelity Cop
16-2
10
Duality
Duality
10
10
AHGDA (nmd.11
ARGIA (1-0.1)
AHEEA (nm-.11
Mul Devt
hange le Dest
Bro Hange Sod Dort
AHGDA (n).d.03)
ABGSA 01-0 OLI
Emoor Range 12 300 Devi
Ercer lange 15 3ts Devt
18-1
Error Hange
ANIDA (n00)
10t
(pon 001]
flage Devt
lange
10a
109
10>
10a
107
30
13a
NORMAL
LOGNORMAL
EXPONENTIAL
10>
107
Duality 10-1
Duality Cop
30-1
16-1
20'
AHSDA Inyd.31
ABSOA (p-0.31
12"
EVICE Aongen L6 Devt SpwO. DLI
Barie
AUSIDA inm1
10 10
Fongels
AIGDDA 1n-0-3011
3id Den
Enee fange Devl
Figure 8: Numerical performances of AltGDA with different stepsizes on 30 x 60 synthesized matrix games.
37

---

Published as a conference paper at ICLR 2026
LINIFORM
RANDIMT
BINARY
Duality 10- 10-
22
Gap
Duality Gap
10
10
AJISDA trye..1 21
ARGDA (1-0.11
AIIEA (ip0..1
Ente Range skd Dev)
12"
Erice hange (+ Std Des)
Eror Hange Snd Devt
AJIGDA (nyd.01)
Range SM Dewi
22
AJGOOA 11m0.00 DL1
Ericr hange 15 Best
D2-1
AIECEA tyyo0.23)
Emoor Range S00 Devt
Inmd
Range
10"h
hangels
Rango
10
10'
107
30
134
10
10
NORMAL
LOGNORMAL
EXPONENTIAL
107
10-
10t1
Quality Gep
10-1
10
Duailty
AHGDA Inydd.11
30
1nm8-1 Eree Hange
Hunge Dert
Erice Targe l8
10 10
10"
AH1SDA Dev)
(1.0.0001
Sange Dest
Emror Range Devt
Figure 9: Numerical performances of AltGDA with different stepsizes on 60 120 synthesized matrix games.
F.3 EVOLUTIONS OF FIG. AND FIG.
38

---

Published as a conference paper at ICLR 2026
Iterations
140
Iterations
0.8
3.6
Duality
Energy
100
80
02
640
101
10
167
10a
101
R100
101
107
107
10f
10"
Berations
leerations
140
36
Duality
Energy
100
60
02
100
"10"
10
10"
301
10"
10*
R10'
101
107
10*
10"
10*
Iterations
Iterations
100
0.8
100
Duality
Energy
0.4
80
0.2
0,001
100
10:
107
107
10*
101
R107
107
1.7
107
10f
10a
Iterations
140
Iterations
3.6
Duality Cop
Energy
100
0.4
0.03
60
0.2
0.001
100
10a
100
10a
10a
10a
8100
10a
102
102
10
103
Berations
140
Iterations
06
Qualit cop
Energy
100
0.01
60
0.2
0.001
4.0
10F
10a
10a
10a
10a
10"
10
107
30
100
10a
Figure 10: Evolution of Fig.
39

---

Published as a conference paper at ICLR 2026
Iteration
40
Iterations
0.8
30
0.6
Duality
Energs
20
02
640
101
10
167
10a
101
100
101
102
107
10
105
Berations
leerations
30
Duality
Energy
20
0
02
"10"
10:
10"
10
10"
10*
10"
107
10
10*
10*
10*
Ieeratoon
40
Iterations
30
Duality
Energs
20
0.2
100
107
1.7
107
10a
101
100
10
107
102
10f
10a
Iterations
Iterations
40
30
Energy
Dualty
20
0.01
10
02
10
0.001
10a
10
10a
102
10a
10a
10a
100
10a
102
10"
102
Berations
Iteration
30
96
Duality cop
Energy
20
10
0.2
0.001
10F
10
10a
10a
10a
10a
10
102
30
100
10a
Figure 11: Evolution of Fig.
40


Reviews:
[{"review_id": "ofBuyzEP6n", "reviewer": "Reviewer_uo6Y", "summary": "This paper studies alternating gradient descent–ascent with Euclidean projections in two-player zero-sum bilinear games over convex compact sets. They focus on constrained matrix games where alternation is widely used in practice but poorly understood theoretically. The authors first show that when the game admits an interior Nash equilibrium, AltGDA with a suitably small constant stepsize enjoys an ergodic  $\\mathcal{O}(1/T)$ convergence rate in duality gap. Giving the first result where plain alternation provably improves over simultaneous GDA, they prove a local $\\mathcal{O}(1/T)$ convergence result for general bilinear games. Beyond these analytic results, the paper develops a performance estimation problem (PEP) formulation that encodes AltGDA’s worst-case behavior as an SDP and numerically optimizes stepsizes. The PEP evidence suggests AltGDA may in fact achieve an $\\mathcal{O}(1/T)$ rate more broadly for finite horizons, while simultaneous GDA appears limited to $\\mathcal{O}(1/\\sqrt{T})$, and experiments on random matrix games corroborate the faster empirical convergence of AltGDA.", "questions": "* In Theorem 1, $\\eta$ depends on $\\min x_i, \\min y_i$, which are unknown. Can you provide data-driven or adaptive rules that maintain the $\\mathcal{O}(1/T)$ rate?\n* Are there lower bounds showing that (a) AltGDA cannot do better than $\\mathcal{O}(1/T)$ in this setting, or (b) the constants in Theorems 1–2 are not too pessimistic?\n* Which parts of your proof crucially use bilinearity? Could the energy-based argument or the Lemma 1–2 telescoping scheme extend to smooth convex–concave problems with Lipschitz gradients but non-linear coupling?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The combination of a global result under an interior NE and a local result around a maximal-support NE gives a fairly complete picture.\n* The energy termed $\\mathcal{E}$ used to capture the two-phase dynamics (boundary hits vs. interior cycling) and to bound residual terms is conceptually interesting.\n* Experiments verify the theoretical results.", "weaknesses": "* The global convergence rate requires an interior NE, which is quite restrictive in game applications.\n* The PEP-based evidence for global convergence in general convex compact sets is compelling but not a proof.\n* The analysis assumes deterministic gradients. Many game-solving methods operate with sampling or bandit feedback, it is unclear whether the energy-based analysis or PEP insights extend to noisy gradients.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EQ6TKE42Vp", "reviewer": "Reviewer_o6a6", "summary": "This paper studies the AltGDA algorithm in the constrained min-max setting. It gives a convergence rate $O(1/T)$ under interior NE assumptions.", "questions": "Can the authors say more about how their analysis differs from the analysis in Bailey et al. (2020)?\n\nCan the authors explain what they believe is the purpose of analyzing alternating first-order methods, since optimal first-order methods have already been known for several decades?\n\nCan the authors explain what they believe to be the non-trivial parts of their analysis?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The paper gives $O(1/T)$ convergence for the AltGDA algorithm under interior NE assumptions in the constrained case.", "weaknesses": "The algorithm is known, so the main claimed novelty is the analysis. Lemma 2 is the key new piece, which follows once interior NE existence is assumed. The result and proof are straightforward, leading the contribution to appear incremental since Theorem 1 follows almost immediately.\n\nThe authors fail to sufficiently discuss long-known theoretical results of $O(1/T)$ for the constrained min-max setting, with only a brief mention of optimistic methods, though there is a rich line of literature here (e.g. [1-3]), nearly all of which has been ignored by the authors.\n\nThe authors' results hold only for games with an interior Nash equilibrium, or else for local convergence. Previous first-order algorithms achieve $O(1/T)$ rates without these conditions. The authors should explain this point better and clarify how their first-order results are weaker than previous first-order results.\n\n[1] Korpelevich, Galina M. \"The extragradient method for finding saddle points and other problems.\" Matecon 12 (1976): 747-756.\n\n[2] Nemirovski, Arkadi. \"Prox-method with rate of convergence O (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems.\" SIAM Journal on Optimization 15, no. 1 (2004): 229-251.\n\n[3] Nesterov, Yurii. \"Dual extrapolation and its applications to solving variational inequalities and related problems.\" Mathematical Programming 109, no. 2 (2007): 319-344.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UGYX289A7u", "reviewer": "Reviewer_ppTd", "summary": "The paper studies Alternating Gradient Descent–Ascent (AltGDA) in two-player zero-sum constrained bilinear games. While previous works have shown an empirical faster rate of AltGDA and some improved $O(T^{-2/3})$ convergence rate, this paper proves an $O(1/T)$ convergence rate when an **interior** Nash equilibrium (NE) exists, using a constant stepsize dependent on the value of the interior NE. Specifically, the sufficient condition is to have the stepsize no larger than the smallest non-zero equilibrium mass. It contrasts this with simultaneous GDA’s typical $O(1/\\sqrt{T})$ behavior. The paper also shows a local $O(1/T)$ rate for non-interior games under a universal constant stepsize, with the bound expressed via a gap parameter linked to a maximal-support NE. Finally, a performance-estimation-programming (PEP) SDP is used to numerically optimize stepsizes and visualize a near $O(1/T)$ curve for finite $T$.", "questions": "- Is there an adaptive stepsize rule (e.g., backtracking based on duality-gap trends or energy-surrogate monotonicity) that achieves the same $O(1/T)$ rate when an interior NE exists, without using $\\min\\{\\min_i x_i^*, \\min_j y_j^*\\}$ a priori?  \n- I wonder whether there is some way to detect the existence of an interior NE in an online fashion. For example, can persistent monotone decrease of the energy and support persistence be shown to imply interior-NE structure (or neighborhood), while non-monotonic energy indicates the alternative regime?  \n- Can the aurthors explain more on the choice of the learning rate $\\eta$. Is that possible to bound the largest admissible constant stepsize using spectral/simplex geometry of $A$ alone, or give conditions under which $\\min( \\min_i x_i, \\min_j y_j )$ are bounded away from zero?  \n- Can this analysis be generalized to two-player general-sum game?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well motivated by the empirical success of AltGDA and establishes the first $O(1/T)$ rate for AltGDA with constraints under an interior NE. This is a clear improvement over simultaneous GDA while using a constant stepsize. The proof leverages a monotone energy decay, which is neat conceptually and interesting in its own right.  \n- The use of the PEP framework is also interesting to show the benefit of using alternation. The SDP study provides tangible (though with approximations) finite-time evidence for the benefits of alternation and suggests structured.", "weaknesses": "- One main weakness is that even under the assumption that there exists an interior equilibrium, the stepsize $\\eta$ depends on the unknown equilibrium masses. Specifically, the global $O(1/T)$ theorem (interior NE $(x,y)$) requires a stepsize scaled by $\\min( \\min_i x_i, \\min_j y_j )$, which are unknown in practice and may be extremely small. No adaptive rule is provided that attains the same rate without such knowledge.  \n- In addition, if the interior NE is near the boundary, the admissible constant stepsize can be impractically tiny. There is no quantification of worst-case constants or a detection-and-retuning mechanism, and this will also leads to a bad convergence guarantee.\n- The other concern is that the global analysis relies on the existence of an interior NE. When no interior NE exists, the same energy monotonicity fails; the paper does not provide an in-process diagnostic to decide which regime one is in.\n- For the second result with local convergence rate, while the learning rate now is not dependent on $\\min( \\min_i x_i, \\min_j y_j )$, this requires the initial point to be close to an NE, with the distance also dependent on these problem-dependent constants.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MVcxPm5V9B", "reviewer": "Reviewer_xbjq", "summary": "The paper studies alternating gradient descent ascent for bilinear games and provides three results, a rate of $O(1/T)$ for average convergence in games with interior Nash Equilibria, a local convergence of the same rate without the aforementioned restriction and a reformulation of the method under a performance estimation framework that allows the computation of an optimized stepsize. Regarding the first two contributions, the authors identify a non-decreasing energy function associated with the duality gap, that facilitates the analysis. The last contribution requires a series of transformations to reduce the original problem to a tractable form.", "questions": "Could the authors elaborate on any approaches that they perhaps try but fail to generalize the result completely?\n\nI will also add some minor comments:\nIn Lemma 8, you can conclude the monotonicity of the energy function without using the fact that the NE lies in the interior, since the third and fourth terms of equation 20 are jointly nonnegative. \n\nIn line 1418, “Lemma 12” instead of “12”.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses an important open problem and makes substantial progress towards resolving it. The approach for deriving the convergence rate may be based on a simple energy function but is quite technical and involved. The same holds true regarding the PEP framework. I also found the presentation clear.", "weaknesses": "The only weakness I can point to is that the existence of an interior NE is not a very weak assumption, like say the uniqueness of a NE.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "71s43Bw5Es", "reviewer": "Reviewer_MTEk", "summary": "This paper studies the problem of the average convergence rate of online gradient descent-ascent in bilinear zero-sum games. The main results include:  \n* A computer-assisted framework to find the optimized step sizes for a given time horizon.  \n* A proof of the $O(1/T)$ average convergence rate of online gradient descent-ascent in constrained bilinear zero-sum games with interior equilibrium. For games without interior equilibrium, a local result is also provided.\n\nNumerical results are also provided to support the theoretical findings.", "questions": "What are the obstacles to extending the current framework to the analysis of alternating Mirror Descent algorithms in zero-sum games (Wibisono et al., 2022)?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The purposed PEP framework provide new tools to proof the convergence rate of learning algorithms in games.\n* The result of $O(1/T)$ convergence rate of online gradient descent-ascend for constrained zero-sum games greatly improves the results of (Bailey et al., 2020) in the unconstrained setting. \n* The proof techniques, especially the construction of the decayed energy function and its relation to the duality gap, are interesting.\n* The paper is well-written and easy to follow, and the motivation and the strategy of proofs are clearly stated.\n* Numerical results coincide well with the theoretical findings.", "weaknesses": "One weakness I see is that the PEP part (Section 4) is a bit rough. For example, a crucial point of how to reduce the infinite-dimensional nonconvex optimization problem INNER to a solvable finite-dimensional problem is not clearly stated in the main text.\n\nMoreover, I think two recent works of (Feng et al., 2025), which studied the seperation between alternating and simultaneous momentum dynamics in zero-sum games, and (Hait et al., 2025), which studied the regret properties of alternating learning dynamics in convex games, are also relevant to this work. It would be good if the authors could include them in the related work section.\n\nA minor problem: In Figure 1, the label of the x-axis should be T instead of N.\n\nReference:\n1. Feng et al., Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games . ICML 2025\n2. Hait et al, Alternating regret for online convex optimization. COLT 2025", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)