Classic but Everlasting: Traditional Gradient-Based Algorithms Converge Fast Even in Time-Varying Multi-Player Games
Authors: Yanzheng Chen
Jun Yu
Venue: ICLR 2025 Oral (2025)
Keywords: time-varying games
Nash equilibrium
extra gradient algorithm
optimistic gradient algorithm
Primary area: learning theory

Abstract: Last-iterate convergence behaviours of well-known algorithms are intensively investigated in various games, such as two-player bilinear zero-sum games.
However, most known last-iterate convergence properties rely on strict settings where the underlying games must have time-invariant payoffs.
Besides, the limited known attempts on the games with time-varying payoffs are in two-player bilinear time-varying zero-sum games and strictly monotone games. By contrast, in other time-varying games, the last-iterate behaviours of two classic algorithms, i.e., extra gradient (EG) and optimistic gradient (OG) algorithms,  still lack research, especially the convergence rates in multi-player games.
In this paper, we investigate the last-iterate behaviours of EG and OG algorithms for convergent perturbed games, which extend upon the usual model of time-invariant games and incorporate external factors, such as vanishing noises.
Using the recently proposed notion of the tangent residual (or its modifications) as the potential function of games and the measure of proximity to the Nash equilibrium, we prove that the last-iterate convergence rates of EG and OG algorithms for perturbed games on bounded convex closed sets are $O({1}/{\sqrt{T}})$ if such games converge to monotone games at rates fast enough and that such a result holds true for certain unconstrained perturbed games. With this result, we address an open question
asking for the last-iterate convergence rate of EG and OG algorithms in constrained and time-varying settings. The above convergence rates are similar to known tight results on corresponding time-invariant games.

Published as a conference paper at ICLR 2025
CLASSIC BUT EVERLASTING: TRADITIONAL GRADIENT-BASED ALGORITHMS CONVERGE FAST EVEN IN TIME- VARYING MULTI-PLAYER GAMES
Yanzheng Chen & Jun Yu"
Department of Automation
University of Science and Technology of China
Hefei 230026, China
snbcyzêma 11, ustu. wustc.ed..cm. harryjun@ustc.eduu.om
ABSTRACT
Last-iterate convergence behaviours of well-known algorithms are intensively in- vestigated in various games, such as two-player bilinear zero-sum games. How- ever, most known last-iterate convergence properties rely on strict settings where the underlying games must have time-invariant payoffs. Besides, the limited known attempts on the games with time-varying payoff's are in two-player bi- linear time-varying zero-sum games and strictly monotone games. By contrast, in other variin games, the last-iterate behaviours of two classic algorithms, i.e. extra gradient (EG) and optimistic gradient (OG) algorithms, still lack re- search, especially the convergence investigate the last-iterate behaviours of EG and OG algorithms for convergent perturbed games, which extend upon the usual model of tine-invariant games and incorporate external factors, such as vanishing noises. Using the recently pro- posed notion of the tangent residual (or modifications) as the potential function of games and the measure of proximity to the Nash equilibrium, we prove that the last-iterate convergence rates of EG and OG algorithms for perturbed games on bounded convex closed sets are O(1/VT if such games converge to monotone games at rates fast enough and that such result holds true for certain uncon- strained perturbed games. With this result, we address an open question asking for the last-iterate convergence rate of EG and OG algorithms in constrained and time-varying settings. The above convergence rates are similar to known tight results corresponding time- invariant games.
in multi-player games. In this paper, we
INTRODUCTION
This paper discusses learning in time-varying multi-playe games converging to monotone games. Monotone games are a class of multi player games (Rosen (9655) including a wide range of impor- tant games, including two-player zero-sum games, convex-concave games, X-cocoercive games (Lin
al. 2020). zero-sum polymatrix games (Anagnostides et al. (2023); Cai & Daskalakis (20TT): Cai
al.
2016: Daskalakis & Papadimitriou (2009)), and zero-sum socially-concave games (Even-dar
ctt al.
2009 ). Due to their wide applications, a vast literature on finding methods to approximate
their Nash equilibrium actions has been produced recently.
An important part of this literature is on last-iterate behaviours of well-known algorithms, and this topic has gained much research interest in recent literature. These algorithms include extra-gradient (EG) methods (Cai et al.] (022);; Feng et a (2023); Monteiro & Svaiter (010)), optimistic gradi- (OG) methods (Cai al. (2022); Feng al. (2023)), negative momentum methods (Feng al. 20033 and weights update methods (Lin et al. (220)) proposed in Arora et al.] (2012)). Although last-iterate convergence performance a challenging topic, yet in the case monotone games, last- iterate convergence has been discussed in many papers. Last-iterate convergence of the EG algo- rithm general monotone time-invee invaiintaiaatt games has been proven in Hsieh et al. (2019) and Popoy
Corresponding Author.

---

Published as a conference paper at ICLR 2025
1980), and its convergence rate has proved to be O(1/VT) in unconstrained settings et al. (2020a)) and general settings (Cai et al. (2022). ). A recent result Wei et al. (2021) shows that there even always exists a linear convergence rate whose value depends on the problem.
Golowich
Despite the known considerable works, most recent literature on multi-paayer games is based on the assumption that the underlying repeated games are time-invariant. Nevertheless, time-invariant games are unrealistic in many real-life applications (Cardoso et al. (2019): Duvocelle et al.] (2023);
Mai et al. )2018), and more realistic learning settings should allow the underlying cost functions of games to change with time. Games with such settings are called "time-varying games".. Top-
ics on time-vane varring games have gained popularity since several years ago. Duvocelle et al. (2023).
Feng et (2023) and Zhang et al. (2022) are the first known successful attempts to solve problems about last-iterate convergence in time-varyee varying games. However, Duvocelle et al. (2023) requires decreasing step size and does not provide a convergence rate but only provides that the probabil- ity of convergence is By contrast, decreasing step size is unnatural since such a requirement considers new information be decreasingly important instead of equally increasingly as nor- mally expected Lin et al. (2020). Besides, that result only illustrates last-iterate convergence in two-player zero-sum bilinear games in the unconstrained case, which is too special compared with general multi-playe games and constrained games. Feng et al. (2023) does not require decreasing step sizes, but unconstrained set of actions is still necessary.
Considering the limits of known research mentioned above, we conclude that the last-iterate conver- gence behaviours of time-varying games still far from fully understood and none of the existing results on time-varying games provide satisfactory answers on whether and how fast an algorithm converges except unconstrained two-player bilinear games. Hence, open question arises natu- rally:
Will learning algorithms such the extra gradient optimistic gradient algorithmss exhibit last-iterate convergence rate in time-varying games with a constant step size?
Our contribution. Motivated by known results, first prove that there exist convergence rates on certain bounded and unconstrained multi-player games with a time-varying cost function for each player where the vector of cost functions varies with time in the following way (called convergent perturbed game): fe = foo + 9t, lim = 0. In this paper, we show the following results:
Assuming that Σم= max ||Gr|l the Nash equilibrium of G, we prove that the last-iterate convergence rate is max(O(L/VTT), Ol E max [[GxI)), (max [GT[])] for general convex bounded cases for the EG algorithm, max(O(L/vT)), O(max427/2 Lo.), Lo.)) / max [[+xll) with La-smooth perturbing and L-smooth limits when Gx(=") = O for the EG algorithm, (Ox(O(L/VT))) O1 max [[xxI)),, Omax [Gr]l)} for general convex bounded cases for the OG algorithm and (a((V(())))) OGy EE max ||++ O(max [|Grl),, O(LG,-))
oo where G.
Vg.. with defined as
with La-smooth perturbing and L-smooth limits when G+(=*) = 0 for the OG algorithm, where T refers to the time. For the extra gradient and optimistic gradient algorithmss that convergence rate is approximately equal to the known tight bound for time-invariant games. Those results mean that both algorithms are robust to disturbance.
Our last-iterate results of EG and OG generalize that of prior work Cai et al. (2022) and Feng et al. (2023) significantly, where convergence rates of EG and OG have only been proved in two-player bilinear time-varying games and monotone time-invariant games, respectively. Besides, our method provides a partial answer to the open question about constraint games (Feng et al. (2023)) from different view.
Organization. Section defines the game problems this paper and describes the main prelim- inaries applied to solve these problems. Sections 3 and 4 introduce the theoretical results on the last-iterate convergence of errors defined as tangent residuals in the EG and OG algorithms and pro- vide their proof sketches, respectively. Section 5 illustrates the convergence performances of the EG and OG algorithms with numerical experiments. S concludes the paper with additional discussions and proposals on directions for further investigations.
2

---

Published as a conference paper at ICLR 2025
1.1 RELATED WORK
Related works on time-varying games. In recent years, time-varying games have become the re- search interest of group of researchers. Most of the papers have focused only correlated equilib- rium or time-average convergence. The work most closely related to ours is Duvocelle et al. (2023). investigating strictly monotone games. However, even two-player zero-sum bilinear games are not strictly monotone (fF(2), 2²) = 0). Feng et al. (202)) discussed two-player zero-sum bilinear games unconstrained settings and obtained the first known result on the last-iterate convergence in time-varying games. Another related paper. Anagnostides et al. (2023), focused on correlated equi- libria for the multi-player time-varying case. Other known results, such as Zhang et al. (2022), are focused on regret bounds (two-player) in time-varying bilinear saddle-point problems parameterized by the similarity of the payoff matrices and the equilibria of these games. Another result related to üime-varying games, Harris et al. (2023), is about meta-learning in games, where each game can be repeated for multiple iterations consisting of settings in which many similar games need to be solved together. Cardoso et al. (2019) provides optimal solution based on Nash equilibrium regret. In this paper, we provide a different perspective on time-varying games.
Previous investigation convergence rates of EG, OG and other related algorithms. EG and OG algorithms have long history (Korpelevich (1976); Popov (1980) and the convergence rates of EG and OG in time-invariant games have been thoroughly investigated. In recent years, uncon- strained strongly monotone games and unconstrained bilinear games have been shown to have linear convergence rates for EG, OG, and other variants in Daskalakis et al. (2018). Later papers have proved their asymptotic convergence (Daskalakis & Panageas (2019)) The convergence property of EG on concave games has been investigated in Monteiro & Svaiter (2010) (last-iterate) and Ne- mirovski (2004). and the convergence property in special non-concave games has been proved in Mertikopoulos et al. (2019).
2 NOTATIONS AND PRELIMINARIES
In this paper, we focus on time-varying games that converge to smooth monotone games in the fol- lowing form: G = [[[]]], (z(1) ]e][[N]): { [ejLN] =: 2,, J where [[N]] == 21,
is the set of players, Z Rº is closed convex set and the action set of players, || x2|l. In addition, 2 con- sists of actions of players, and throughout the paper, with defined as the symbol of the gradient feedback vector of the vector function, i.c., Vf : (V 2f ..... V f())) for simplicity, ff is denoted as F and V is denoted as G; ft. It. F& and G3 refer to f. g. F and G at time k; and sub- script ki refers to the time & when is applied. max ||G |l. max || | max ||G,-l are maximums N) if 2 is unbounded with the EG algorithm, and on {z/li E N} U (wili E N} Z is unbounded with the OG algorithm. We define the Nash equilibrium of these time-varying games as the Nash equilibrium of the limits of these time-varying games.
the cost functions of corresponding players and Dz =
defined on Z if 2 is bounded, on {z,li E N or i-
Time-invariant monotone games, time-varying games and their Nash equilibria. In this part, we introduce our model of time-varying games and the definition of Nash equilibria on them. To introduce them, we define time-invariant monotone games in Definition I and the sufficient and necessary condition of Nash equílibria in Lemma Tat first. Lemma shows that a Nash equilibrium of the game is equivalent to solution of the variational inequality of monotone operator F.
Definition
Rooen 1965 A game G is monotone if 121,32 Z. (F(x1) F(12), -2)
0.
Lemma 1 Facchinei & Pang 2007 For monotone game G, an action 2n is Nash equilibrium ofg if and only Vf E 2, (F (,)),,
- < O.
Based on the preliminaries in time-invariant games above, we define the time-varying perturbed games investigated in our paper.
Definition (Convergent perturbed games) A convergent perturbed game consists of an infinite sequence of games with cost functions satisfying {f(())){2 C RR" where lim f((z) f(=) for
3

---

Published as a conference paper at ICLR 2025
certain f(z). An equivalent definition is that there exists sequence of cost functions {g((2)) (80 C
Ie and a function f(2) E I"" such that f((z) = f(z)+ in the same infinite sequence of games. For simplicity, f(2) above is denoted (2).
Specifically, we focus on time-varying games converging to smooth monotone games, i.e., (2) of the games monotone and T--Lipschitz. The definition of smooth games is the following.
Definition 3 [ooenn 1965) ) 9 is L-smooth if F is L-Lipschitz, ie., Ven, 22 E 2, [[(()))
F(x2))] L| -2
We define the Nash equilibrium of these time-varying games as the Nash equilibrium of the limits of these time-varying games.
Definition 4 2n is Nash equiliiriumm of convergent time-varying game G if 2 is Nash equilib- rium of 9x0 = ff))
In convergent time-varying games, we modify Lemma I as the following lemma.
Lemma 2 For game G converging to a monotone game, action 2" is a Nash equilibrium of G if and only Vz E 2, (F>o(="),
S
Note that all games converging to monotone games have at least one Nash equilibrium if 2 is bounded, while these games with unbounded 2 may also have a Nash equilibrium under certain cir- cumstances (Facchinei & Pang (2007)). Throughout the paper, we apply the following assumption on the existence of the Nash equilibrium.
Assumption (Existence of the Nash equilibrium) Any time-varying game G involved has least one Nash equilibrium.
Learning algorithm in games. In this part, we introduce two kinds of learning algorithms investi- gated here: extra gradient and optimistic gradient algorithms. Both algorithms are proved to be last- iterate convergent in time-invariant games (Cai et al. (2022)) This inspires the time-vane varying variant of the two algorithms in general time-varying multi-player games defined in Eq. ① and Eq. (2) and
illustrated in Figure where the projection operator 11 is defined 1l (z) argmin
The extra gradient algorithm is defined as follows:
x II [2k F/ (=x)) 2x+1 II 2k
FF
2x++
(1)
where the step size vj > O, 2g an arbitrary point in 2, 2 the vector consisting actions of all players at the time k. and #x+ is a vector used to calculate the actions of players at the time i- + 1.
The optimistic gradient algorithm is defined as follows:
Wk-1 IIz [z FF (w:)] 2x+1 II [*x - F (Wk+1)]
where the step size 77 > 20 and wn are arbitrary points in Z, wk the vector consisting of actions of all players at the time k. and zy is vector used to calculate the actions of players at the time k 1.
Both algorithms have long history. The extra gradient algorithm was proposed in Korpelevich (1976). The form of time dependence in our paper originates from |Feng et al. (023). The optimistic gradient algorithm was proposed in Popov 1980). Several versions of the OG algorithm exist in the known literature (Cai et.l 2022) Hsieh et (2019)) The version above is applied for convenience of analysis on time-narying F.
Tangent residual as the measure the proximity to Nash equilibria. former results, the common measures of the proximity of actions to Nash equilibria of games the gap functions (Nemirovskil (2004); (Osieh et al. (2019) defined as follows.
Definition 5 (Gap and total gap functions) For time-varying games converging to monotone games, measures of the proximity of an action profile z E Z to Nash equilibrium include their gap func- tions and total gap functions. For fixed parameter D, the gap function is defined as Pg,p(z)
4

---

Published as a conference paper at ICLR 2025
max./zznB(.D)) ( 2/), where (2,, D) is ball with radius D centered The total gap function defined as (z) EiETNT (f (2) ming/0ee(0nBtt f ( =()
where 2 consists of actions of all players except Player i.
However, gap functions far from monotone. In fact, they are monotone even in time-invariant monotone games (Cai et al. (022)). This causes inconvenience in our analysis. To solve that problem, we adopt the tangent residual from Cai al. (2022) as the measure of the proximity the Nash equilibrium, since it is, or is related to, monotone non- non-increasing functions of time in time- invariant monotone games. The tangent residual in our settings defined as follows. Though, due to the cost function being are only not increasing much with time instead monotone non-increasing functions time. The details of those functions are discussed in Sections 3 and
in our settings, the tangent residual and its relative function
Definition 6 (Tangent residual in convergent games) For any closed convex and operator F: Z - RR" define Nz(z) as the normal cone of 2. N2) = {zlz E N2 < 1} and J (z) == +z)+ where Tz(2) {z' E R (z', a) S 0, Va E Nz(z)) is the tangent cone of z. The tangent residual of 9
FF2 |1] [a F()] =|1
To show the reasonability using the tangent residual in our settings, we also show the relationship between the tangent residual and the gap and total gap functions in the following lemma. Specif- ically, shows that gap functions are not much larger than tangent residuals, which means that tangent residuals converge no more slowly than gap functions. As a result, the results shown in this paper are applicable to traditional measures of the proximity to Nash equilibria.
Lemma (Cai et al. 2002);; Golowich et al. 2020a bl) For game G converging to monotone
game and closed convex set Z, Vz Z and D there exists Pg.D(z) S D rg (z) and Tz. s (3) & VND rg (z).
Assumptions on the form of time dependence of games. We introduce the following assump- tions which will be applied lemmas and theorems. The following assumptions are inspired by Benzaid & Lutz (1987); Elaydi & Györi (1955); Elaydi et al. (1999): Feng et al. (2023): ZZho et al. (2020) and are commonly called bounded accumulated perturbations (BAP) assumptions.
Assumption g(2) in G satisfies Ei max [|{(()]| < oo where Z is bounded.
Assumption G is LipLschhitz and Ei max [=)[l)]| < oo and Eino || [(G))] < oo where Z is bounded.
Assumption 4 G is -ip-hitt with G,(=*) = 0 and E [[,]] < co.
Start
Start
initialize zo E Z and >
initialize 20, wo rj >
k
# = 11 12t Fi (#x))
00 1z 12s. 17 (wow))
2k+1
TTg =x FP Ex+
Z6+1
17 (w)++)) 11 [=x
k
l
Figure 1: An illustration of the EG (left) and OG (right) algorithms.
5

---

Published as a conference paper at ICLR 2025
also denote max L(G:) Lg. For games satisfying Assumption 4 Zg,, Wk are bounded with the EG and OG algorithms, and we do not need to assume it. The proof is deferred to Appendices B2 and Throughout the paper, each assumption is used independently.
Under Assumptions 3 and
Remark In Assumption it is not necessary to assume Ex= max |[Gr(=)] < xc, because there exists Ei=g max [+) = Ei= max [[,[(z) Gr(z") S Ei= max TTalll= - 201 S
max =l 100-==112--0
Et [[)]] cc.
LAST-ITERATE CONVERGENCE RESULTS OF THE EG ALGORITHM
In this section, we prove that EG with constant learning rate converges to a Nash equilibrium action at the rate of O(1/VT) under any one of Assumptions 2 and The EG algorithm is analyzed in the following steps: firstly, the tangent residual of applied as the measure of prox- imity in approximating a Nash equilibrium in any iteration; next, the best convergence rate within T steps is shown, which is a small number; finally, it is proved that the square of tangent residual of G is approximately non-increasing, which means the last-iterate convergence behaviour of the EG algorithm is at least not worse than the best iterate too much and that the last-iterate convergence rate of the EG algorithm is at least not much worse than the convergence rate of infinite series of perturbation.
3.1 BEST-ITERATE CONVERGENCE OF THE EG ALGORITHM
To estimate the last-iterate convergence rate of the EG algorithm, first estimate its best-iterate
convergence rate. Lemma 4 shows that there exists t* E [[7']] satisfying || 2 + 2 O()TT)
and plan 34 + (1/VT)) The full version and the detailed proof this lemma are deferred to
Appendix B33
Lemma For a game G converging to a monotone game with any closed convex set C R" and monotone and L-Lipschitz operator Fxo Z + R", with the EG algorithm, let x" be solution of the game G. Then VT 2 1, there exists a t" E [[T]] and C1, C2, C3 > satisfying
C1
21-
2
T
and satisfying
pan (2r-4)) S max
C2
+ Ca max max ||Go
(VT
under Assumption 2 ifn E (0, t); under Assumption
3 if E ViTplolltio)
C2
L. D)
pean (2r-1) S imxx
VT
under Assumption with D max || -- 2
if1 - 12 - Lo (L + LG) - 4nL. >
3.2 APPROXIMATE MONOTONICITY OF THE EG ALGORITHM
In this subsection, provide the monotonicity behaviour of the EG algorithm. Since the approach complicated, the detailed proof of the following theorem is deferred to Appendix B.4
Theorem For game G converging to monotone game, any closed convex set Z C RD and monotone and L-Lipschitz operator Foc Z + R", Vnj E (0, L)) zs
Z, plan (zx)² Z
plan (2k+1) max || G (4Dz + 41 max ( (I) /n- If Z Ra, , (zx)² 2 plan (#t+1)² )2
max | (4D + 2m max Fox /n where D max 2 2x+ll 1| 2b+1ll]. E N.
3.3 LAST-ITERATE CONVERGENCE OF THE EG ALGORITHM
This subsection combines the best-iterate results and the approximate monotonicity to estimate the last-iterate convergence rate.

---

Published as a conference paper at ICLR 2025
Theorem (Last-iterate convergence of the EG algorithm) For game converging monotone game, AT E E 0.
Tg.D(zT) Pe.D(2T)
max plan (zr).
VND
D
=0 max
k=T/2 max |Gall, max |Grll]
where D = Dz with n) E (0, +.) under Assumption or D = Dz with E
( (1442a((Ltt))
under Assumption and
max tan (Zr), Tg.D(2T) Po.D(2T)
VND
D
=0 max
2T//2 LG V k=T/2
max |Gall
where D = max ||= - zk+1lb k E with 1/ 21 (L + LG) - 4npa > under
Assumption 4
The proof is deferred to Appendix B.5
4 LAST-ITERATE CONVERGENCH RESULTS OF THE OG ALGORITHM
In this section, we use a method similar to the previous section to show the last-iterate convergence results of the OG algorithm.
We analyze the algorithm with the following steps: firstly, we apply a potential function based on the tangent residual of G, i.e., A(z,, wx) f + Fo (w(())) (wx)]l² as the measure of proximity in approximating Nash equilibrium the current iteration; next, we show the best con- vergence rate within 7 steps, which is small number; finally, we prove that the potential function of G approximately non-increasing, so the last-iterate is least not worse than the best iterate too much, which means that the last-iterate convergence rate is at least not much worse than the convergence rate of infinite series of perturbation.
4.1 BEST-ITERATE CONVERGENCE THE OG ALGORITHM
To estimate the last-iterate convergence rate of the OG algorithm, we first estimate its best-iterate
(2 convergence rate. Lemma shows that there exists t" E [[T]] satisfying ~/2r, w S 0 (1/T)
The proof for the best-iterate convergence rate of the OG algorithm is based on Hsich et al. 2019
Wei al. (202T). The full version and the proof details of the lemma are deferred Appendix C.2
Lemma For a game G converging to a monotone game with any closed convex set C R and monotone and L-Lipschitz operator F Z R", let 2" be solution of the game G. Then
1. (0, VoL) there exists t" E [['']] and C1, C2 C3, C4 > 0 satisfying
1 A wt-) S (Ca 11:00 111 C2 llwo zoll CsEmb> CgEmk
where
Emnk
k=0 max ||a
Emi
max ||
Under Assumption 3 isn 0, 761244 there exists E [[T) and C1, Cz, Ca. C4
satisfying
A wi-)
T (ci ||=0 2²12 + O2 Ilwo =0122 + CzEma CaEmit
1
while under Assumption
4 if is small, there exists t" E [[T]] and C₁, C22, D satisfying
T C1 |0 2 2 2 + C2 Imwl - 20ll + 2n² D Σn Lau (2L + LG--))
n² A(2e", we+) - T
7

---

Published as a conference paper at ICLR 2025
4.2 APPROXIMATE MONOTONICITY THE OG ALGORITHM
This section shows the approximate monotonicity of ( we) for the OG algorithm. Since the approach is complicated, defer the detailed proof of the following theorem to Appendix C.3
Theorem 3 For game G converging to monotone game with any closed convex sei 2 C R" Vn E (0,1/(2L)) ), 24 E 2, A(z; W/) 2 A (Zt41, W++11 (3Dz + 4n max || II) max |G& // if
2 is bounded, while A(z,, w/) 2 A 2 ((++1 - (3D + 2nj max Foo max || if 2 RR"
where = max[]] 2 ||++1 =x N.
4.3 LAST-ITERATE CONVERGENCE OF THE OG ALGORITHM
This subsection shows formal result the last-iterate convergence behaviour based the modi- fied tangent residual. The following theorem states that the players' strategies converge to the Nash cquilibrium of the game with a rate not slower than the rate of O(1vVT) or depending on the con- vergence rate of perturbation.
Theorem 4 (Last-iterate convergence of the OG algorithm) For game converging monotone game, VT E N
Tg (Wr)
Pg.De
tan (WT).
max
VNDz
Dz
max |Gall, max [Grill)
=0 max
VT'
k-
T/2
with E (0, VoL or under Assumption with E (0.
under Assumption while there exists
Vor. Vor2
(g.D(ur) Ps.D(Wr))
}
max plan (wT),
v VND
D
max VT' k-7/2 max |G&ll max || LG Lor1)) })
4 with E (0,min { TाTTLCJ rta)) where D max |1+11
under Assumption
Zx41 ll. || - 24
F..11..6
E
N.
The proof is deferred Appendix C.5
EXPERIMENTS FOR TIME- VARYING GAMES
In this section, provide some numerical examples for Theorem 2 and Theorem 4 proved in Section and Section 4 The numerical examples are based on examples of bilinear games in Feng al. 2023). By the following examples, we verify Theorem 2 and Theorem
Example 1.
f((z) foo (2) + (x)
2t1
T
2
5
213 +
40 cos +11)++1)0000 (oo + cos ((++1)))))) ((+=))"zs)+200cor ((+1)'
212
4
1
244 +
11+1)
Et1
7
2
5
213 + 3
2 cas ccn(((++))z +3 c3 ((t+1))))
+5 +5 ((t))(())) ct
(1+1)
4
244 +3 3
s.t. ||x||| = [ae1
242
243
214
< 2
This example is corresponding
to Assumption
2
where
2
{*|||=||
<
2}
and
De max [G]())] Eee
20vI0 (++1)*
oc if
1.
8

---

Published as a conference paper at ICLR 2025
Example 2.
21
2
213 +
200 +0000=
f((2) fz)(2) + 9((2)=
Ee2
1
4 1
244 + 3
(t- 1)t
7
60(0 + ) 60 +
211
2
5
213 + 3
212
4
211 +
s.t. | = [211
212
213
214]
This example is corresponding to Assumption where = {=|||=|| S 2], E.= max |G+(z)]] S
E
200vI0 00 if and Ei=o Lg.
(L+1))
2t=0 (t+1))
co
400vI0 00 if 1.
Example
fx(2) = Joo (2) + 9c(2)
211
T'
2 5
213 + 3
50(2 (112:-11334 1)9 -1)4222-1112((--1 +3) +-3
222
4
1
211 + 3
(t+1))
211 1
2 5
Ee3 +3
40(2 1002--1) +12+s(sss 10(=
(++1))
212
-
1
201 +
s.t. 24
2r2
2x3
zea|²
E IR
This example corresponding Assumption where Ee Lo. S Et=o (1+1) < 00 when
i 1.
Note that Ve 0, NN 0 the new initial time that VT N, Lor <c
5.1 EXPERIMENTS ON THEBRREM 2
In this section, the step size is selected as 0.05 and the initial point of 2, is selected as 20 [0.25 0.2 0.1 0.35)". As in the common practice shown in Feng et al. 2023), the BAP assumptions, i.c., Assumptions
and 4 are applied in the three examples above, respectively.
The experimental results are presented in Figure 2] which show that rfan(zz) converges to 0 under any one of 2 [nd and all three convergence rates of perturbations can decelerate the convergence rate of learning dynamics expected, thus support the convergence result in Theorem
1.5
Figure 2: Values of (2)) for Example 1 (left), Example 2 (middle) and Example 3 (right).
5.2 EXPERIMENTS ON THROREM
In this section, the step size 7 is selected as 0.05 and the initial points of wy and 2, are selected as Wp 2g = [0.25 0.2 0.1 0. As in the common practice shown Feng et al. 2023). the BAP assumptions, i.e., Assumptions
and are applied in the three examples above, respectively.
The experimental results are presented in Figure which show that (w;) converges to under any one of the Assumptions 2 and all three convergence rates of perturbations decelerate

---

Published as a conference paper at ICLR 2025
(" Euspll
1 Eiseple 2ir
1.
Figure 3: Values of r plan (wx) for Example (left), Example 2 (middle) and Example 3 (right).
the convergence rate of learning dynamics expected, thus supporting the convergence result in Theorem
CONCLUSIONS
In this paper, we provide last-iterate convergence rates of EG and OG algorithms in bounded and some unbounded cases, including unconstrained cases, for time-varying multi-player games con- verging to monotone games by proving that both algorithms show tight convergence rates compared to related time-invariant games and the property time-varying function. There exist some inter- esting future research directions. In experiments, it is suggested that the convergence rate in bilinear cases can probably be improved. Another interesting direction of investigation is whether and when games vary time periodically (called "periodic games" in Feng et al. (2023) stochastic games show similar results for EG and OG algorithms.
ACKNOWLEDGMENTS
This work was supported by the Natural Science Foundation of China (62276242), National Avia- tion Science Foundation (20222071078001), Dreams Foundation of Jianghuai Advance Technology Center (2023-2M01ZZ001.
REFERENCES
Ioannis Anagnostides, Joannis Panageas, Gabriele Farina, and Tuomas Sandholm. On the conver- gence of no-regret learning dynamics in timevvarying games. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL
net forum?
1d=0x20u3xHbb
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta- algorithm and applications. Theory of Computing, 866):111-164, 2012. doi: 10.4086/toc.201 v008a006. http::////hccccooooopppgggogogge
Z. Benzaid and D. A. Lutz. Asymptotic representation of solutions of perturbed systems of lin- ear difference equations. Studies in Applied Mathematics, 77(3):195-211, 1987. doi: https:
//doi.org/1..1002222/.. 1987773310 URL htttps::/oolineeibrrrt wi wwley.www...................ee.. com/doi/
Yang Cai and Constantinos Daskalakis. On minmax theorems for multiplayer games. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11 pp. 217-234, USA, 2011. Society for Industrial and Applied Mathematics.
Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos Papadimitriou. Zero-sum poly- matrix games: A generalization of minmax. Mathematics of Operations Research, 41(2):648- 655, 2016. doi: 10. 10.1287//oor22015.0775 URL https: doi. wtt.doio...ooooooo 1281111117// 7/moor.
201 1015.00 0745]
10

---

Published as a conference paper at ICLR 2025
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate conver- gence for learning in multi-player games. In S. Koyejo, S. Mohamed, A. Agar- wal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Pro- cexsing Systems, volume 35, pp. 33904-33919. Curran Associates, Inc., 2022. URL neur ips wwtpppprpppc.eeeeee /ttp://ees/ppprr/22//11.a.. d222201166e322100544441T1EEE oorprppeeeeettiaoaaaaooooooorero
htttps://procedd
Adrian Rivera Cardoso, Jacob Abernethy, He Wang, and Huan Xu. Competing against Nash equi- libria in adversarially changing zero-sum games. In Kamalika Chaudhuri and Ruslan Salakhut- dinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 921 130.. PMLR, 09-15 Jun 2019. URL https::/proceedingg ml. press
wtwps//ss.......p.//sseee.e.eeee https/////aarrdsssseeee html
Constantinos Daskalakis and Ioannis Panageas. Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization. In Avrim Blum (ed.). 10th Innovations in Theoreti- cal Computer Science Conference (ITCS 2019), volume 124 of Leibniz International Proceed- ings Informatics (LIPics), pp. 27:1-27:18, Dagstuhl, Germany, 2019. Schloss Dagstuhl Leibniz-Zentrum für Informatik. ISBN 978-3-95 978-3-95977-095--8
doi: 10.42300.IPlcs.TTCS.0000
27. URL LIPICS ITCS 2019.21
dev. www.saa....eeeeee...........ee.. wtw.d//eeniiieeebbeeeeeeeeeeeeee https///ww....aaaaaaaaaaaaaaaaea
4230/
Constantinos Daskalakis and Christos H. Papadimitriou. On network generalization of the minmax thcorem. In Susanne Albers, Alberto Barchetti-Spaccaantt Yossi Matias, Sotiris Nikoletseas, and Wolfgang Thomas (eds.), Automata, Languages and Programming, pp. 423-434, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. ISBN 978-3-644-00990-11
Constantinos Daskalakis, Andrew Nyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL
/ forum?id Eorum?id=sJ[ySbba
Benoit Duvocelle, Panayotis Mertikopoulos, Mathias Staudigl, and Dries Vermeulen. Multiagent online learning in time-varying games. Mathematics of Operations Research, 1 2023. doi: 10. 10.12287/o0r:2222..222 1283. URL http://////o..coo/1111///////// 2022. 1283
S. Elaydi and I. Györi. Asymptotic theory for delay differene equations. Journal of Difference Equations and Applications, 1 1(2):99-116. 1995. doi: 10.1080/102261199088800000 URL
https: //doi. http://........0.000000222211130
Saber Elaydi, Satoru Murakami:, and Etsuyo Kamiyama. Asymptotic equivalence for differ- ence equations with infinite delay. Journal of Difference Equations and Applications, 5(1); 1-23, 1999. doi: 10.1080/10336199988888888
URL attps:://ac..oog/10..
102361 91161999998888888
Eyal Even-dar, Yishay Mansour, and Uri Nadav. On the convergence of regret minimization dy- namics in concave games. In Proceedings of the Forty-First Anmual ACM Symposium on The- ory of Computing, STOC '09, pp. 523-532, New York, NY, USA, 2009. Association for Com- puting Machinery. ISBN 9781605585062.
doi:
URL https:
//doi. http://11111111111111111 1536444
Francisco Facchinei and Jong-Shi Pang. Finite-Dimensionse Variational Inequalities and Comple- mentarity Problems. Springer New York, 2007. ISBN 978-0-387-95580-3, doi: 10.1007/ b97543.
Yi Feng, Hu Fu, Qun Hu, Ping Li, Ioannis Panageas, bo peng, and Xiao Wang. On the last-iterate convergence in time-varying zero-sum games: Extra gradient succeeds where optimism fails. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 229434--2444... Curran Associates, Inc., 2023. URL ott.o//ooc/////ppoccco.oo.ooooo.
paper httppaaarrwaaapppppaaaeaappppp/e fi F1225555222555055555533332222223

---

Published as a conference paper at ICLR 2025
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate vergence rates for no-regret learning in multi-player games. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural In- formation Processing Systems, volume 33, pp. 20766-20778. Curran Associates, Inc., 2020a. URL httpss://prcceeeddddd ngs neurips www.eeiss..cppaaaeeeeeeeeeee wwtppper.pppp.peeee http://aarr_ffeeseeeeeee fit.fee/////aa//220.... Fllc/ee58Seeedcc30//055552222223
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concaye saddle point problems. In Jacob Aber- nethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 17884 PMLR, 09-12 Jul 2020b. URL httpttt:/ppccceeeeiiiiii marpagssmll.... mlm htt.a//s........pooooo//////ooo.
html
Keegan Harris, Joannis Anagnostides, Gabriele Farina, Mikhail Khodak, Steven Wu, and Tuomas Sandholm. Meta-learning in games. The Eleventh International Conference on Learning Representations, 2023. URL httpsttps::.
htttps://pperretee /ttpp//pppeeieiee//////ee net htt///ouumnn-iaaaaaaaaan/h//////
Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. the convergence of single-call stochastic extra-gradient methods. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL F111//228ee111000144633443428203 http://ppppprr.feeee///ee//////p
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976. htt.atsss//ai..eeanniiiittoooooo htt.://cchhoaaa..ooorroropslslaa 118602977
Serge Lang. Continuous Functions on Compact Sets, pp. 51-62. Springer New York, New York, NY, 1993. ISBN 978-1-4612-089771 doi: 9-119778-1--611-897---333 URL https://
doi. www.oo.g/.........o.oooo.... 1007/ 101-10007799-114662----------33-
Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, and Michael Jordan. Finite-time last- iterate convergence for multi-agent learning in games. In Hal Daumé and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Reseurch, pp. 6161-6177 PMLR, 13-18 Jul 2020. URL https: https://proceedingg mll worpes/vvi9//iie html
Charles H. C. Little, Kee L. Teo, and Bruce van Brunt. Infinite Products, pp. 39- 129. Springer Inter- national Publishing, Cham, 2022. ISBN 978-3-030-906466 doi: 10. 10.1100/977-3100 001777883-03090044--- 2__
2. URL wttpt:tt/////t http:::://doi..rrg1///0 www./ooggooo..oooo 1007 978 3-
Tung Mai, Milena Mihail, Ioannis Panageas, Will Rateliff, Vijay Vazirani, and Peter Yunker. Cy- cles in zero-sum differential games and biological diversity. In Proceedings of the 2018 ACM Conference on Economics and Computation, EC 18. pp. 339-350, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 45035523,,,,,, doi: 00.1145/2211166.2292222 3219227
URL http://////o.l.o0000.1111///////
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra(-gradient) mile. In International Conference on Learning Representations, 2019. URL
httts:://peerreviee net. http//oooomiddooeooo hotp://wwweeeeeeeeooooooooooo-e JoC
Renato D. C. Monteiro and B. F. Svaiter. On the complexity of the hybrid proximal extragradient
method for the iterates and the ergodic mean. SIAM Journal on Optimization, 20(6):255-2287)
2010. doi: 10.1137/090753127 URL http::://////..... //t.ps:://oi.ooo .rg...org//ee
Arkadi Nemirovski. 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(1):229 251, 2004, doi: 10. 10.11377510522224444445999999999 URL
12

---

Published as a conference paper at ICLR 2025
L. D. Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28:845 848, 11 1980. ISSN 0001-4346, doi: 10.1007/BF01140022 URLpttt:: spr wwwiingrrss... wtm. 10t.111000001111101011101
B. Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econo- metrica, 33(3):520-534, 1965. ISSN 00129682, 14680262. URL http:httpp/wwt jstor org/
stable/191177
Chen-Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinitehhorizon competitive markov games. In Mikhail Belkin and Samory Kpotufe (eds.), Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 4259 4299. PMLR, 15- 19 Aug 2021. URL https::t///.......... http::s////oocceeeeeeeeee ngs ml press v 34 we i 21 html
Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi Hua Zhou. No-regret learning in time-varying zero-sum games. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 26772-26808, PMLR. 17-23 Jul 2022. URL https:
http:::/ppooceeennnneeeeo////eee http:///pocceeeengspeeee www. https///w..///h//222naan.. zhwnghhannnnanncce
Peng Zhao. Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou, Dynamic regret of convex and smooth functions. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 22510-12520. Curran Associates, Inc., 2020. URL httpss:/pprcceee/nnnoeen///////t newrrseeerrssss cctp.pe.pppppeee files/ htpp://200111/s111eeeeeeesss2222
A ADDITIONAL AUXILIARY LEMMAS
In this section, we present other lemmas frequently used appendices required for proving the convergence behaviours of EG and OG. The following lemmas are fundamental to the analysis.
Lemma 6 Lang 1993)
Any continuous function on a closed bounded set within R. is bounded.
Lemma 7 Little et al. 22022) If {an} is sequence of non-negative numbers, then the series Ej=1 aj and the product I (1 + 0z) either both converge or both diverge.
The following two lemmas state known useful properties of the tangent residual.
Lemma 8 CCai et al. (2022) Let 2 C Rn be closed convex set and F 2 + IR be the operator
defined in Section 2 V2 let c(2) IIx(z) [-Foo (2)]. Then we have
tan (2) = Fo) +()]]
=0,
(Fol(z) c(2), 2 0. v. N(2).
Lemma 9 Cai et al. 2022 (Equivalent definitions of the tangent residual) For any closed convex set Z and operator F Z - R", define Nz(z) as the normal cone of z and (z(2) == {z} + Tz(z), where Tz(2) &2' E R² (z',a) S 0, Va Nz(2)} is the
tangent cone of 2. Then all of the the following quantities are equivalent:
1. 1I max N
2. min (E [[(2) (F))).
-
3. [[Tz(>)) [=F()]]]
4. [T))(()) [2- F(=)]= =
13

---

Published as a conference paper at ICLR 2025
5. |-F(z) (2) | [-F())]]
6. millgeN [=)) + all
The following lemma states useful property of the tangent residual.
Lemma 10 Let 2 C Rn be closed convex set and F Z - I2" be the operator defined in Section
If = 12z[22 - nFhi (za)l. then we have
tan (1))
22 21 + F20 - Foo(2a)
+ max [|GGkag)
Gkag is also LGw Lipschitz and Gx = 0, then
tan (2) S
22 21 + Foo(z1) - Fo0(23) + LGisg D
where max ||=" 23/1.
Proof. Due to 21 II 12 FF (2))), we have 22 mFFks (23) 21 N2((1). By that equation
and item 6 in Lemma there exists
tan (21)
min cENz(z1)
| + +cl
22 22 + F=0(22)) FRag (2s)
1)
22
+ Fx0(2)) - (2o) - Gkeg (22)
22 21
+ Foo(2) - Foolza) + max | {||Gkss kkkkgll
If Gkeg is also Lorey Lipsshiitz and Ga(z*) 0, then there exists l|Gkes (z*) Gkeg (2 s so that
LGuis - 23ll Leu.g
p tan (21) <
(an
22 21 + Foo((z) - Foo (2s)
+ LG D
In the analysis, the natural residual is applied to estimate the tangent residual. Lemma I1 shows that the tangent residual the upper bound of the natural residual.
Definition 7 For any closed convex set Z and any monotone operator F 2 - R the natural residual at z Z is not (z) = ||| 1lz(z 11/2-F((s) F(:))||.
Lemma 11 (Cai el al.
2022 )) For any closed convex set 2, any monotone operator F + R and any E 2, (F)((2)
(z).
Jon
B OMITTED PROOFS FOR LAST-ITERATE CONVERGENCE OF THE EG ALGGRRTHM
In this section, we provide detailed proof for the last-iterate convergence rate of the EG algorithm:
2x+ II [2k Fi (2x)) 2x+1 II 2* -nFF (2x++)
This section consists of the following parts. First, with a method inspired by Facchinei Pang 2007) and Korpelevich (976)), the best-iterate convergence rate of | 2 ; is proved for the EG algorithm. Then, the upper bound of tangent residual of 2 proved to be max max(O([]=* 2++ (I), (mmx ||Gxl)) if G₁ is -Lpsschit and to be O[] = y matter whether Gk Lc. -Lppschitz. Next, the tangent residual is proved to be either inn--nccraiing increasing slowly enough across iterates of the EG algorithm. Finally, the last-iterate convergence rate of the EG algorithm is concluded from the conditions above.
14

---

Published as a conference paper at ICLR 2025
B.1 PREPARATION FOR ANALYZING THE BEST-ITERATE CONVERGENCE BEHAVIOURS OF THE EG ALGORITHM
Lemma 12 For game 9 converging a monotone game with any closed convex set S R", a monotone L-Lipschitz operator F mapping from 2 to R and 24.
E Z, with the
EG algorithm, there exists
[xtt] - 2x+1| I riL + LG.) 12t 2 and
2k 2 xx+
-|=11 when E (0, LtLG) GG is LG. Lipschitz, and there always exists
2/ 2 } 1
1-nL-nLot
+2g max (GL when 17 E t). 16
Proof. Since 2 12 Saaks-nFie -nF(2x)] and 2k-1 1l [2k - -7F + ). due to non-expansiveness of z and I-L.ipschitzness of Poc and T.G, Lipschitzzess of Ge, there exists
|| | - 2x+1
- 1 (2k) F/ (2x+t)|
< Fx (2x) - fx [x+ ) || + 1 GR (2x) Gx (2kt2)
< n 2/ Ex+ + || + n nlc. | =x - 2x+7// ||
Ex+ ze+1 S ny | =x+#
Bn max ||
Since 1i LGv- = O, there exists
[ 2k+1
S St + Loww
|| - 2x+
Hence,
1z 2w+1ll 2 cs 2x+ 1 2041|
2 (1 nT. - TTTTca) ||aa #
|| 2k+1/| 2
2k 2
| - 2x+1| ||| 21 21-11/1 nTT,)
1|2x =x+
21 max |R
Lemma 13 For game G converging to monotone game with any convex set Z C R monotone L-Lipschitz operator Foe mapping from Z to I8." and 2n E Z, there exists
|z4+1 112 S 1| ==1 111-1(1-1211) 1xx
zx
4n max Gxll
where Dz= = m1888 ||-1| - =22l defined Section
2 If GR is also Los LLppsciiz,
| - 2012 < z2 - 2²1 11? - 11-12²1² 2nj² Log (L + Lor)) 1|-0-22-- - 2x
Gk (zx++) ) ||| | - ==1)
+ 2n max
while under Assumption 4
|| - =011² < (1 + 4nLG, || - =11 - (1 - 22 L (I. IGG,) AnpG,. | fka==kkp 2k+
Proof. Due to Pythagorean equality which is also used in the proof of Lemma 10 in Cai et al. (002 2x4+1 - 2", #k+1 (zE F/F (=x++)) S Hence, there exists
|| - =0112 < b4 F/ (3x=)) r/Grx (zx+*) 1|2 + zk 17 (2x+*) n/ (ze++) =z++1
15

---

Published as a conference paper at ICLR 2025
Furthermore, we have
|k41 ==11 S E 111oo0 (xx++) .) (zx+2) - =x11==11 -1|za n1Fo0 (aet2) n/Gr (aett) =x+11
1| 2=12 -11zk 2x++1 112
+ 2n1
(3-- 2k, Foo (ze+:) + Gk (skt:)
2n ( (2x+1 2k, Fox (
+ Gk
(=o+*))
= |1 - ==11² - -11=k - Eb+11
112
+ 211
8" - Ek+1, Foo (za+2) + Gh (2x+2)
= 1| x² 2²1 12 - 2b+1ll 112 + 21
Foo (3nt3) ,2* 2x.t///
+ 21 Prx (x++))
- - z6+1) )
+ 21
xx 1 Gk (20+))
S || ==112-
|| - 2 - 1| |
+ Extg - -20+1 || + 2 zk - 2 m0t1))
2
+ 2m 1o (2x+2)
==x+ - 2x+1/ ) + 2m1
(2" - 2x+1, Gx (zo+:)
Since (Pao (Ex+2) ,² #xt )
S 0, there exists
1 +22 x- -kt2 Gk (2k+
||x+11-22 - =211| < 11 - -2"11- zk 2x+ 5
kkt - 2x+1
+ 21/ 3 =, Gk [x++(]]
(=x 22(2z
2
12 (#K+1)
= 1/2 =x++ #k+1
= || - =11 - || m사 + +
12
| - = ||²
+ 2n (=* 2 Gv (#x++*)
- -2(2e 2x - (Foo (zx) + Gb (Ex))
= = - =x+1 ) + 2n] +x+ - =k+11 GR (zx++))
2m (2x+) - 2k Gx (2x)) > - 2n ( ( - zk+1, Foo (zx) Foo (aett))
Due
to
2k 17 (F (zx) + GR (Ex) - 2k+1 [k+ =b+11)
(Ee nF (2x) 2x4 -x4 2 2k+1) 2 0. 2x4 TT (2(()))) and 2k41 E 2,
there exists
||ax11 - 20112 S || - -2"11-- 2* 2 +
2
[x+]] - 2x+1 2
+ 2n (z - -kk+3 Gk (2e+t) ))
+ 2n *x+ - =, Gk +x++//
- GR (2x)) 2n
(2++ - 1 Fox (2x) - Foo (2x++))
$ |1 2=1
zk zx 1
[ 1/2 - -k+1 ||
+ 227 (x* - -k++1, Gk (2xt+)
21 (2x+)- - 1 Gk (zx) )
+ 2.yl. | - zz+1
||28- - ==1 zk 2 1
-(|==+ - zk41
nb zN Ex+
1/? 2x zx+ |2 + An Dz max ||a
< || - =1112 - (1 - 122 1 | 2
+ 4n max ||Gx|l
16

---

Published as a conference paper at ICLR 2025
If G3 is Lo. Lippschitz according to Lemma 12
there exists
1| + 2n (z* 2xt Gk (entt))
|x+1 - =²11² - || ==111 2R =
cktt - 2x+1
+ 27 = - Ext1, Gk
# )
G& (Ex))
2n ( (# - 2k+1, Foc (2x) - Foo (#x+*)
$ 1| ==112-
2k xx+ 3
c 3/2
-h+11
||² 2m (xt - Gk (Ex+E)
+2nIIcia
2k++1 1
zx| + +2npT. || | zx+2 || zs 2
||Ex - ==11|²
12
(1| + - 2
-1/L = #x+ 1)*
A 2 4
+ 1
22 2x+ 3/2
2 + 2n
22 z Gk (2x13)
+ L21
1 - -xx++1
| - zx|
$ |1 - x" x²11² (1 - ) |x - 2
+ 2n (2" - 2 Gz (ze+t)
+ 2n
1 - 2x+2/
/ - 2x|
$ || =²11²- -(1 - 27) /x* =xt
12 + 2n (max
Gx (3etz) )1
Bott - =0))
+ Lox (L + Lot) | 2s+211 11?
Under Assumption 4
||x+11 - 2 2011² S 11 - 2² 211 - (1-172 1)] |1sa =xtt
2 + +2 (2" ,
Gk (2et - Gx (x7)
2n2² Las, (L+ + LGch) ||4 2xtz|| =1?
$ 1| 21² (1 (1-11 -1]² 1|za 2xt
2
[2k+ x²11
+ 207
+ 2n² LGa (L+ + Lart) 11ax- - 2x++ 12
112
< (1 + 4nLGN) ||Ex - 2²112 - (1 1-²²
1xx - =x+ -
Ti. (I. Lox) + 4nt. ||:x- 2x433 12
B.2 BOUNDEDNESS OF THE EG ALGORITHM IN (L + LG, JLIPSCHITZZZ GAMES
This section shows that 24 across iterates of the EG algorithm are bounded under Assumption 4
Lemma 14 For a game G converging to a monotone game with any closed convex set Z C RR" monotone L-Lipschitz operator Foo mapping from Z In and zk E Z, with the EG algorithm under Assumption there exists C' E R so that || - 2" < C.
Proof. Due to Assumption limg-+o GR = 0. Hence, there exists a N E R so that Wk > N,
1 - 2,2 - 211 Lo, (I. + L...) - 4n1,,, > 0, and then
| - 2" 2² < (1 + 4nLo.) 12 - 12
By the equation above, there exists
||241 -2- < 11 211 II
K=N (1 4nLau)
T
< || 2²112 II K=N (1 + 4nLaw)
17

---

Published as a conference paper at ICLR 2025
Therefore, C 2 ||2* - 2"1 when C = max 11 =I (1 AnLoa) -1120 - =
|| - 201 ,.. .....,llaa 1|eN - 2- 1|?
B.3 BEST-ITERATE CONVERGENCE OF THE TANGENT RESIDUAL OF THE EG ALGORITHM
Lemma 15 For a game 9 converging a monotone game with any convex set C R", monotone
L-Lipschitz operator Foc mapping from Z to IR" and x" E Z, there exists
1 nI. + (nT)²) ||a8- 2x+ || +1 (3 + L1) max {1|G
plan (2k+2)
1)
If GR is L.G, -iischhitz and Gr(=*) = 0, there exists
1 + nI. (nI.)² (1 + LL)L |12. - + LG. D
tan (an(22)11) x
where D = max
12- 2x+1/
Proof.
Due to Lemma 10
there exists
ton (2A+1)
S
Zk 1k+1
+ max {1|G&|] (20 - Foo (sa.t)
Hence,
2k
2k
2k+1 - 2k+
ton (Ex+1) 5
+ L 2x+1 2x+ max [1G
"
7
1
+ 1L
| 2x
(2n) (21
1 + 1L + +1) max ([|Gal)
S
nT.))
17
17
1
nL (n)t)²
2* 2 2x+
+ (3 L) max G
If Gg is LG. Lipschitz and Gz(z") = 0, there exists
tan (zk41) x
2k 2k+1
Foo (2x44)) Foo (3++*) + Lo D
Hence,
tan (zk-1)
2x 2k+1
Foo (2x+1) - Foo (2xtt) + LGeD
24+11 2b+
W
+
+ L 2 2n+3
+ LG.
17
n
+ L + LG + nL(L + La)
11 1 2 L.,
+ nL + (nL))
+ (1 + ((+nn))()))
(1ob0>>111 112- 2
+ Lo D
Full version of Lemma For a game 9 converging to a monotone game with any closed convex set Z C RD and monotone and L-Lipschitz operator Foo Z + =R", with the EG algorithm, let z"
be a solution of the game G. Then VT 2 1, there exists E [[T]] satisfying
C T
and satisfying
C2 /T
tan (2r+1) & max
+ C3 max ||Gr-
18

---

Published as a conference paper at ICLR 2025
under Assumptions
2 and 3
p tan (2p- S max {
C2
+ La. D]
VT
under Assumption
where
C 200 - 2¹ 2¹11 + 4n
Σ 00
== (max ||G&ll)
22
C2 1+ ++1 np + (mL)²
1 - 1²1 + 41112 Ei=o (max l|Gx
1 1- 111222
11
C 3- 21L
under Assumption
2 if E (0. 7.):
C ||00 x²11²= + 21/2z En max |Ga|
1 -11212- 2n1² T. (T. LG)
C2 + 1/1 + (1)1)2
|| 2² 1² + 21/ 2 00 = max |Ga|
- 172 - 2ni² LG (L + LG)
C3 = 3 + 2
3 iff (0. (1I-2oo(LtL))
under Assumption
||:0 - 2²11 11 k (1 + 4nLow) )
C
122 277² Lo (T. + LG) 4n1.a
1 + n (nT,)²
1120 - 2- IT (1+ + 4nL.)
C2 =
+ (1 (I+
/V
122 - - (L + LG) 41LG
under Assumption 4 with D max - 2
iʃ1 1,21. 2 (I. + LG) 4nto 0.
Proof. Due to Lemma 13 there exists
||00 2 2 |,T+1 2²11 (1 11-1 ΣT
T
T Σ
zk x 1
4n G2
k=
k=0
2 (1 - 12) Σ k=0
2/ 2b+
4n max |G Dzll
k==
2 (1- - 1² L22 Σ
Any Σ
max GGa|l
k=
0=0
Hence,
120-2211 2
<
1
(1:20- - =2"11= + 4nD2 Ee. k=
(max [|Gxl))
T(1 12)
Due to Lemma 15
I20 2- + 4n Σx= (max ||&lll (1+ (1+ nT. 11+, (nTT)2
plan (20+1) S
+(3 + 2nL) max {|[G,- |}
T(1 L2)
If GE is T.G. -Lipschitz, there exists
||20 - 2=1 2 2 ||r441 - 21 + Σre k== (1-17 11= 2nn" Lo (L + Low)) 12x - -22+1
T
(2 max (z)
k=0
2 Σn kz (1 - 1,22 - L (L + Lox)) | 2
Σ k=
(2n) max ||Gx|
19

---

Published as a conference paper at ICLR 2025
For N Nº, when vk N, 1 122 1-2 - 2nj² LG, (L + LGx) > 0, there exists
1120 - 2² 2 Σ k=0
(1 - 12, - 2n (I + La))
2x 2x+
Σ k=0
(2 | D2)
Hence,
2 2e+
Σ T(1 r72 - 2nj² LG (L + LG)) (11.0 - 20112 + 2n Σ k=0
max ||&all)
Due to Lemma 15
2z0 1=1 1/2 2n Ek=u max Gixll T(1-1f21 112-11210 L2 - -2122 LG (L + LG))
1+ nb + (n])2> 2
lan (21++1)= $
+ (3 + 27 max {||G= lI)
17
Under Assumption 4
||T+|1 =- 1=1
(1 + 41 1100 - =1
k=0
Σ (1 - 1²² 1----000 211² - LGi (L + LG.) ) Lg II (1 4nLc,) |2x 2x+
For N E N", when Ak > N, 1 - 122 -217 LG (L + LG) - A1/La > O, there exists
||20 - 1 Ei (1 1 - -2n L (L + LG) 4m 11 4nLo))
21 2
I (1 4n)
Then, since IT (1 + 4nLGa) S Tk= (1 + 4n ), there exists
||20 2" I T (1 + 4nb.,,)
zx- - 21+ -
( 122 - Lc (I LG) -4nIc)
Due to Lemma 15
1100 - 2=1 1T (1 + 41)
1+ + (nL)²
tan (2)++11)) S
+ -1 -1+ (1+nb)]a))
+ L... D
T(1 11 - 20p² Lo (L + La) - 4nLc)
1
B.4 LAST-ITERATE CONVERGENCE OF THE EG ALGORITIM WITH A CONSTANT STEP SIZE Restatement of Theorem
For a game G converging to monotone game, An (0, t), 24 2,
(4Dz + 4n max |
san Hon()x²² 2 pon (2x+1)²² max ||Gall
1
2 RR. there exists
4D + 21 max Foo
pann > ,lan max ||G&|
7
where D max 2k 24t1ll. || 2b41ll}, & N.
Proof. In this proof, "LHS" stands for "left-hand side". Let c 1INz(se) (- F (2x)) and ck+1
Il [[ (Zx+1)). )). By Lemma g there exists
1l 122 2² 122 (2 (1n) + nexll - (2 + 11
(4)
Considering that Foo is both monotone and L- L-Lisschitz and J,, there exists
-(1=at+ 2x+1 1|² - |/ntioo (2x+ n/ (ek+ 1))) 50
(5)
-2 (n (EK+1) Foo (zx), 2k+1 2x) S
(6)
20

---

Published as a conference paper at ICLR 2025
Since =x+ = 11 (2x- - (2x))) and 2x+1 1lz 2k - -nF (2++1)
there exists 24 - -)FF((2))
2 E N (3x+3) and 2k - F (x++t) 26+1 E N (26+1). Hence,
-2 ( 2k 1E - 2 + - 2k++1 -
2 2k Fk (2x++) 2k+11 2k+1 - Ek S
nock 2x - 2 }/ 00
(9)
By Lemma there exists
-2 -2(11 70x+1 + 1/ (36+1);20 26 - 718's (24+2) - 2k+1 5
(10)
-2 (nC++1 + n (zk+1); -1c++1)
(11)
Hence, there exists
Expression 4 + LHS of Inequality
LHS of Inequality (6) + LHS of Inequality 7
+LHS of Inequality (8) + LHS of Inequality (9) LHS of Inequality (TO) LHS of Equation 11
| + 17ck - -k + 2
+ I (z*+:) + 17c++1 2k + 26+1
||
2 + 2m (=+(2)) - 2k+1
+2n Gk (aa-2) =k++1 -zx) 2n ( GG (2k+*) , .]]++1 17 ==
2m +
= 2k+1) ) + 2m Gx (x++ ) :2x+1 - -za) 2n Gi (ok+t) moR+1 + no (Ex+1))
4n DD max ||Gx|] 21,² (2 max Pc max ||Gx|l)
(12)
which means
[4Dz + 4n max ||Foo
Jon (zx) > s0n
(zx+1)² p0
max |G&lll
(13)
If 2 IR.", 7/+++1 = By Lemma there exists
Expression LHS of Inequality
+ LHHS of Inequality (6) + LHS of Inequality 7
+LHS of Inequality (8) + LHS of Inequality ( LHS of Inequality (1O) LHS of Equation 11
> 2m (R(((E) 2x43 - zk+1) > + 217 ( Gk [+++3] Zk+1 zu
2n (G (2++*) mo++1 + 1/ (Zx+1))
2 - (D max ||Gx 2ny² (max Fro max ||Gx|])
which means
[AD + 2n max Foo
tan (ax))² tnn (oot((x+1)2 max ||Gx|l
(14)
1
Now we combine all the results above in this section in Theorem for the proof of Theorem
Theorem For a game G converging to monotone game, VT = Ti + T2. Ti, T2 E N DD > 0, the convergence rate of the EG algorithm satisfies
tan (PT+TE+1) S /
C2 (5+
2 + 4Dz + 4mmax Fool maxmaxxannn ||Gx|l]
max |G
k Ti
when G satisfies Assumption and
if E (0, +) or G satisfies Assumption
if E 3
0, V1342ho(1+tia)
Ltaan (I7+T8+11) S
C2 VT
+ max Lo, Do
2
4D an max |
Σ
max ||Ga|
k=
21

---

Published as a conference paper at ICLR 2025
when G satisfies Assumption with Do = max -- - + and D max 1 1|
2x41 ||) e N if ²/2 -2nj LG (L + La) - AnLG > 0, and for unconstrained cases a
and for constrained cases = 4. Under Assumption
1 + nT + (n) C2
maxieN || 201 + An Ex=D (max [G&xll) L2
7
C3 - 2nL
Under Assumption 3
1 + 1 (nI)²
+ + nL)LL) )
maxien 2 ===12 Ek= max |G&|
C2 =
1 122 - -21 LG (L + LG)
C3 33 +-++11 2n1
Under Assumption 4
C2 ( + nL + (n
maxiEN || 2- I_== (1 + Ln
(1 + n
"
172 - 2n1² La (L + LG) 44
Proof. Due to Lemmas
13 14 and 15| there exists t" E (Ti, Ti + T2] n N so that paan (2t-
O(1 (1)) Since Ti
according to Theorem there exists
pla (ST++Ta+11 S ton pann (zx=41)²
4D2 + 4n max Foo
Σ
max |G&all
1
k=
under any one of Assumptions 2 and while there exists
4D + an max Foo
ton (21, tan (1)+ (2
max ||G
1
T=
under Assumption 4 with unconstrained games and 2. Considering that all 2i 2, E N are
in bounded convex set due to Lemma 14, have 4 under Assumption in constrained game. The theorem is obtained by directly combining the equation above with Lemma
B.5 PROOF OF THEOREM
Cases where T < 3 are trivial with Big O notation since a(x) O(b(z)) is true if x belongs to a limited set, Va(x) 2 0 and b(x) > 0. Suppose T = Ti + T2 + 1, Ti, T2 E N for T 2 2 and
Ti- T2 2 or Ta According Theorem it holds that
plan (2T) tan (2T++T2+1)
C2
+ C3 m ||&x|l]
+
4Dz 4n max Fool
Σ
00
max |G&
VT2
k=
[[&+1)) +0 (Eee k=T, max [|G&vl]
+ (maxee(T)
To
|Gxll) + +0 (v 1 k=
0
+ +
(maxxe(n,
max ||Gull
VT2
Hence,
ton (DT) =0 max (T' Exery max ||Gx|l, max |Grill
Then, according to Lemma
Ps. n(z)
S (dam(2) and Tolo(s) S r Hence, it holds that VND
D
Te.D(ET) Po.D(2T)
max
p
tan
(zr),
VND D
=0 max
VT Σ
max [G&ll, max |Grll
k=T/2
22

---

Published as a conference paper at ICLR 2025
Besides, we have
plan (2r) = tnn (21++2))
C2
2 + (TXT LG, Du) Du) )²
+ 4D + an max F
max ||
VT2
7
k=2;
+ O (TTT LG. Do)² 0
(E max ||G&|l)
T2
O (ma Do) +0 +0
( max |G&all
0
VT²
under Assumption
Hence,
pan (2T) =0
max
max42T/2 Lo V E 0
max ||GR|] })
VT
k=T/2
Then, according to Lemma
Po. ((+)
S rrga and To.
S Sr Hence, it holds that
VND
Tg.D(er) Pe.D(zr)
tan (ZT),
max
VND D
=0 max
00 22 L Ex-rya max ||Gulll })
C OMITTED PROOFS FOR LAST-ITERATE CONVERGENCE OF THE OG ALGORITHM
In this section, we provide detailed proof for the last-iterate convergence rate of the OG algorithm.
Vk 2 0,
Wk-1 Il [zx 1/ (w+)] 2k+1 II2 [*+ - F (Wk+1)]
(15)
The proof of last-iterate convergence of the OG algorithm is similar to that of the EG algorithm. This appendix consists of the following parts. This section consists of the following parts. First, with a method inspired by Hsieh et al. 2019); Wei et al. (202T), the best-iterate convergence rate of ((Z,, wx) for the OG algorithm is proved. Then, the upper bound of tangent residual of is proved to be m0l( - [I), O(max ||G& if G& is LG. Lipschitz and to be O(I - = 1 (l) no matter whether G3 is Lc. Lipschitz. Next, the tangent residual is proved to be either non non-increasing or increasing slowly enough across iterates of the OG algorithm. Finally, the last-iterate convergence rate of the OG algorithm is concluded from the conditions above.
Lemma 16 For any closed convex sei Z C R" if I1 [2
F/ (za)l, then we have || =2 < 2n1² (22, 23) + 4n² L max || 2all G || + +2n
|| |Gkk.g !|?
Proof. For 24 II [2g
np Foc (2 there exists
|| 22 I || 211l + || =2
Since 21 = 1T n7 F (23) exists and the projection operator is non-expansive, there exists
2| 24 || S 17 F (22) Foo + 17 Gk., (zs)
Due to Definition 7 and Lemma II there exists
|| 24|
r nat
nF ( (22) S r
lon (1 = yp tan (22)
Due to (a + b)2 < 2a² + 21/ there exists
|| 2211² < 2r (32) 22 2 Foo Foo Fos 122 + 417 2 max || 23ll |K 2n7 |Gkr, 1|
= 2n7² A(22 |32, 23) 4n max || - 23ll G || + 2n² ||G ||
23

---

Published as a conference paper at ICLR 2025
C.I PREPARATION FOR ANALYZING THE BEST-ITERATE CONVERGENCE BEHAVIOURS OF THE OG ALGORITHM
Inspired by the proof of the best-iterate convergence rate with the OG algorithm in time-invariant games Hsieh et al. (2019); Wei et al. (202T), we provide Lemma 18 to analyze the best-iterate convergence behaviours of the OG algorithm with Lemma 17
Lemma 17 For game & converging to a monotone game with any closed convex set Z C R. and monotone and I.-Lipschitz operator Foo Z + Tk. and zk; Wk E 2, there exists
1| wk+1l 11 s 2(1) (((4m)222)111 1 - zoll + 2 E (4n L2)' I|Ek-s Wk+1-ill
+ 1672
Σ 2i= (4n22 || 2
and when T 2 1, if E (0, 2
Σ
k= |
T
wk+1 2
2
Ilw0 20ll2
E T
|| - wx+ill
- 4n L2
k=
+ +8/
i= max
T-1
||Gil(²)
while under Assumption 4 there exists
||w wx+1ll2 < 2 1| wk+1l 11 + Σx k
2 III j=1 (2n² (L )() l wx-i+1ll
i=1
+ 2 II
(2n² (L + LG...))) 11200 - z0l1?
k= Imw whtill2 S Eg (1100 -201 Σ k=
2011
T'
1| wstzll? 112
where
lim 2 T
(2n²² (L + -a)3)
EG = 22
T-300
k=1
Proof. Vk 2 1,
||1x - -x112 < 172 [F - F (wx))
S 12 (L ||wk-1 wall + G - (wx-1) Gh- Gu=1(wx)ll?
s 272²
[2 + 1
Vk 2 0 there exists
|| wk Wk+1| 1| < 2 2||wu - =2al12 + 2 2||zz 111+112
Hence, Vk 2 2 and under Assumption 2 there exists
|| |wk 12+ s 207² 2 || wxll² + 2 ||22 112 227² || [[Gb-I(w--1) Gk- (wx))2
+ 4n L. [ wv ll | (wk-1)
Gk-1 (wx)]l
S 4n/² L22
||wx-1 - wx 1| + 2 || wk+1|l 1| + 417² [[G=-((w--1) - -
< 4n L?
||wk-1 - wxll 112 + 2 || wk+1 112 + 16y2² || 11?
< 1,2
1.3) k- 1|w0 zol12 +2 > i=o (41² 1.2 ||z--1i-- - wik
k-
+16n² 2 Σ iiz L3)2 | 1/
12 )) + || wx+1ll 2| +1n? ||Ga-
= 22(47² L2) 1// - 20
2 Σx *
L3)) ||== - w
1|=
+ 1672 Σ 1
(47) G|
24

---

Published as a conference paper at ICLR 2025
and when k 1,
1|wx wK+1 11 (124))(12))111100 =oll2 + =oll2+2
- 1
+ 1672 Σ == (4n) ||Gk=1-ill
Hence, there exists
Σ Σx Ilw - wh+1 11 < 4n
(lw0 =0ll2
Ex kmo || - wx+1
+81 == max ||Gil??
If Gg is LG. -Lipschii,,, Ak 2 1, there exists
[k zxll S n² (L + Lo._,) 1/ - wxll
Hence, under Assumption
|| w/
1| $ 21/² (L + IG--1) )² |10kk-1 - wx|1² + 2212 Wh+111 112
s 2 || wh+1| 11 + - i=0
k-2
2 III" j=0
(2n² (L + Lom..-s))) 110-1-1- wbl
;-1 22 (L +...)))) )²) 11200 wil?
$ 2 1| - wk+1l1 112 + + 2II; j=1 (2n² (L + Lan-,) 1izk- wx wx-i+zl12
II [=1 22n²² (T. Ioc.. ||w0 20ll
By the equation above, there exists
Σ Exooleu 1luk
ww+ill 2 1+ Σ k= i=l (2n² (L+ LG, )²)) |l10 -oll?
+2| will Σ T
2 22 (21 wx+1ll
Σ i=1
2 2nn² (L LGr_,)²) 1| Wk- wk-
= 2 1 + Σ T
(2n² (L (o..))²)
1l10 20ll?
1=1
+ Σ k=0 || wk+il?
2+ 2
T-k
22)² (L + Li )²)
2
i=1
Since Eg = 2 limy +00 2 2I (2722 (L + 2 so that 2 + 2+2 k= I 12n (L + La. ,9955 EG.
1ww 1b+1l1 < Eg (100-2012 Σ k=0 || uk+1ll?
2012
k=o
Lemma 18 For a game G converging to a monotone game with any closed convex set Z C R and monotone and L-Lipschitz operator Foo Z + _ and zk; wk E Z, if (D, v+z) there exists
2
1| 20112 1- 2 L
T
||2T+1 20122 < ||00- 2² 11² +
|| 2k+1ll
1
4n L
4nj2 L
+
16n² L
T
max || |Gxll 2 + 4n Σ
max || |
1- 4n² L?
k=0
k=0
25

---

Published as a conference paper at ICLR 2025
and Gv is Lo. Lipschitz and 1) E
0, V612+4LL0-11
there exists
|1441 11-11-211' =²1 S 11:0 - ==11/+ 2xp (L + LG)
11000- - -20l1² =0 1- 11-61/2222 -112LLG 211 1
4n2
1 --418
En
11zk -k+t1l + 161 (I. + LG)
max
|Gxll
k=0
- 4n22 km
E k=0
+ +2nD2
max ||G
while under Assumption 4 if E (0, min { [ stta)) })
|| 2²12 - EG2 =0 z²11² + Ec2n² (L + LG)² EG l|w0 zol1
- (1 - LLL - EGEGTT (L (L+ Σ T
|| wx+1ll
k=0
where
Σ
k= (2n²² (I+ T(a)²) k
T
Fg 2 lim T+x
II, T
FGG lim
(1 + AnT.ac))
T+0 k=0
Proof. Vk 2 0, there exists
|| - 2²1
1| 2 2=11 + || - 2x 2 (2x+1 2k: 2x 2²¹)
+
= || - 2" 2²11 ||x+1 - =xl1 + (2x+1 - 2k, 2k+11 2²)
|| 2²11
|| - zxl2 2 -2n (Foo (wo+(W++) 2k+1 2²)
21/ 1),
2c+1 =2")
Due to Lemma 17 there exists
|| |z - 1 S
|| - 2²11 - || - 2x11 - -2n FFo (Wx( 0k-1 =2") 2²)
2n (Gx(w)+1): 2k+1 =2"}
= || - 2²12 - -12241 - 2x11 2n (wx+ 2k-1 Wk+1)
+ 2n (wx+1);
-Wk+1) 2n (Gx (wk+1) 2k+1 wk+1)
+ 2n (Gi (Ge(wN++)) (I)+1),;** 1),=" - -wk+1)
< 2| 2²11 || - 2xll - 2m (Foo (wk+1) 2k-1 Wk+1)
- 2n (G& (Wk+1) 1), 2k+1 - wk+1) - 2n (G+( - wx41)
vk 2 0, there exists
[ - wk++ 2 = || - zxll + 1| - Wk+1 112 2 Wk-1 Zk+1 =m.
||zk11 =xl? 2 -112 wk+1l 1| 2+2 Wk-1, 2k+1 wh+1)
< ||z441 - 2x| 1| - wx+1 2 + 2n (Foo (wx), =k-1 ws+1)
+ 2n (Gx( 2k+1 Wk+1)
By adding the two equations above, we obtain
|| 2²1
< || 2= |x++1 Wh++1 11 || wk+1ll 1|2
+ 2n (Foo (w+) - (wx Zh+1 - wk-1) + 2n (G& (wb+1), - wk+1)
+ 2n (G& (wx) Gx(ww+1)) 1), 2k+11 wk+1)
< | - ==11²= - || Wh++ 112 112- || 1ik+11 1|
2n |oo (wx) (oo(
1)|l }|| || wk+ 2n (Gu (wE+1), wk++1)
+ 2n G (wx) Gx(wx+1) | w1+11
26

---

Published as a conference paper at ICLR 2025
If 2 is bounded,
| -2 S 1|zE- 2=1 ||2 Wk+1 112 + 12 1,2 livk wx+1 + 2n max |G+|ll - =1
+ 2n Gx|l
- 1| 2=1² -1= Wk+1 11 2 122 ww wx+1ll + 4nD2 max || |I
Then, there exists
S 1120 - === Ex
2 - wk+21l +n²2 >
1 wk+1ll 11
k=0
k=0
+ +41Dz E
'
max ||G
$ $1100 - 2²² - Σ k= 1 - -Wk+2ll 112 + 2 Σ
T
max |Gx
k=
2T2
|l10] - zoll + k=0
1| - - || + 8n7 Σ T-1
max [|Gr,l])
+ 1 - 112
k=
211² 1
612 L2²
$ 1|200 - 11
+
11:000 =201²²
1 - 412 Σ
|| wK+1ll
1 - 411 1,2
k=0
161/ 667/A.- 1??
Σ k=0
T-1
max Gx1l + 4n Σn == max |G
+ 1 - 2n2
If GE is La -Lipschiz, there exists
|| =²11²-
< || 2²1 - || wk+1| 1|2 || wx+1 112 21/ || - wx++-x+lll || wx+1ll II
+ 21/ (Gx( ((x((x1),, - -x++1) 1) + +22La,
|| - wx+1 1aaalll1=10 | wk+1ll
$ 1 2²1 - -1z -2411l 112 + 11² (L + LGG, )² 1|2x 11l + 2m (Gx (Wx+1), wx+1)
$ | - 201 - -1 - wx+1ll 122 + r²² (L + LG.) )² f12x - wk+ill + Dn 2 max || [wx+1+1))
Hence, there exists
||r++1 10-11-2111 =211 - 1| 12 Er
T'
T 11 11a=-wae wk+1l 1 +I (I+ La)² Enr 1wx -wktal? ?
k=
+ +2nD22 Ex T
max |xxll
(L La)2
|1000 11100~2012 2011² + >x T
< $1100 - =01
||= wk++1
1 - 1|
k=U
1 2n2212
k=
+ 8172 Σ
i= max [[G:112) + 2n D k=0
T-1
max
||G+|l
2172 (L + LG)²
1- 1-67 2 -4n²
-41 LLG 2n12
$ |1:00 - 2112² +
11w00 - 2011
1 1- -- L2
1 - -412212 1
k=o 1 - wx + 167 (L + La)²
Σ
T-1
max ||&all + 2n k=0
max ||Gb||
1- 2
k=0
Under Assumption 4 there exists
||z - 2²11² < || 2012 - -11 - WK+1 1| 2 1² (L + LGz) 1/| - wx+1ll 11 + Ln 1|2" wk+ill
< (1 + 4nLoa) 1|= - 2²122 - (1 - 4nLc, || wx+1ll + r² (L + Lox P1|wx wo+1l
27

---

Published as a conference paper at ICLR 2025
Hence,
19r+1-2"11
T - II k=0
(1 4nL - ==11 Σ k= II linkt (1+ LnLG.) (1 - An 11e wk+1 11
-(1 - (11-AnT.T))) 1|2 WT++1l
i= (1 + AnT,; )²² (I+ LG.) )² 1 wx+1ll
+ +12 l(GT)*
1/11UT WT++1l 1|
$ Ra2 =0 - =²113-
E k=0
r
(1 - 4n
||=a wh+1l?
+ EG2n (L+ LG)² 2
7
||ux wk+1ll
h=0
I Eg2 1:000=1-1011 - -2-11- -
(1 - An 1122 wh+il 11
k=0
+ EG29 (L+ La)² Eg
Eg |1w00 - =oll²+ -
k= || - -w++ll
s EG2 =0 - =01 + EC21i 2 (I. + LG)²
Eg llwo - zoll
- (1 4npba Eg Ecr2l 2 (L + La)²)
Σ k=
T
|| - wk+1 11?
C.2 BEST-ITERATE CONVERGENCE OF A (Zzk, wk)
This section shows that VT E N", there exists t* E [[T]] satisfying A we-) = O(1/T).
Following is the proof of the boundedness of any sequence of players' actions with the OG algorithm in (L+ + J-Lpschit games described under Assumption
Lemma 19 For game G converging to monotone game with any closed convex set Z E R", monotone L-Liscchitz operator Foo mapping from Z to IK" and 2 Z, with the OG algorithm under Assumption there exists Cz2 C. > O so that |/ 2- S C2 and w 20 S C.p-
Proof. Under Assumption 4 with Lemma 18
find that Vt E No, || 12 is bounded in any sequence of games in this paper with the OG algorithm. Hence, there exists C2 > so that || 20 < C..
With OG algorithm, we have 2% = II [2k-1 - FF (wx+)). Hence, for CT = 202,
|kk+1 - 2x| = [I [Z - nFkx (wx)) - II (2 - nF (ww)ll
< 2k 2k-1l| S 22 2" + || 2k-1l I 20 < C.
Lemma 20 For game G converging to a monotone game with any closed convex set Z C R and monotone and L-Liipscitz operator Foo : Z + TF." and zk, wi E 2, if E (D, VoL there exists
Σ A2 wK)
< 1 6172 1,2
4 20m I
|| - 11
4n 1 15n212 6)
|lw0 - zoll
617² T,2
47² (9 + 4n7 1 L0)
4nD2 (4 20n²* L*)
+
Emax +
Ema
1 61
- 6,1
where
Emk Σ k=0
max |G
Emia
max ||
k=o
28

---

Published as a conference paper at ICLR 2025
Under Assumption 3 if E 0, 7012 there exists
4(1 11) + 21 (12 (I++ T,)² +8+ 81
T Σ k=1 o (2k, wx) S
1120 =011 + 1|w0 zoll?
1 1- - A122 2112
21p (T. + 2 ( 21 1.2 12 (1)
21 (8+88)772 + +12 (T. + T.c)²)
(1- (1-6r) 6172 1.2 41²² LLG - 2z) - 412
1- --
8nD2(1 2n + 4n L2L2 2 1/ (L + La)² + L1)
Emi + 4n²² Emiaa
9 9 9 L²
1- 62 - 4n² LLG 21j² Li
27 (8 + 812 + 1 (L + LG))
21 (L+ L 4 21 8m7 1.2 + 7² (I + La) [G)
1- 112212
61 1,2 41p LLG 21 ( (1 - 112
Under Assumption 4 if 4nLo EGEO2 (L + LG)² > 0, there exists
4 + EGN² (L + LG) 3 (4 + 31/² L2)
Alzk, wx) <
1 41 F.G 2 2 (I + T.)) 2 Liaa 11z0 - =21
k=1
4EG2 + EgEan (L + LG) 2 (4+ 32)
+ 31 (n² (L + LG)² Ex) 11w0 zoll
1 1- An EG 2 (I + La)²
+2n D2 Σx k=l LGn-1 (2L + LGu-1)
T
where D = maxteNflle 2011,11e we 1I).
Proof. wk 2 1, due to Lemma 10 there exists
17 20 )² S (11zk-1 - 2x + f - 7/ + 17 max [|G 11)
< 2 ||žk-1 - 2x + 27² (1) - (ox + max ||
S || - 2 221²² (L || - wusl ll + max || 11)
S 4 || - wx 122 + 4 Ill - ==12 + 4172 L22 || - wx 1|? + 4n² max ||
S 4 || - wx 12 + (4+ 4n" 4,2) (2n |10k-11 - w + 8n7² max /Ga-1
+ 4n max || 112
|| - wx|l 1| + 2ny² 2 L2 (4 + 4122 - + 41, + (9+8n² L3) max || 2
Hence, according to Lemma 18 when 17 E (0, VeL
there exists
1/² A AAEk, wx) Σ k=1 (1²),tun( tun (2x)² 2 + II - nF (ww))l
T
|| - wxll 11 + (4 + 5n/ 2 L22) 2n 1
|k-k1 - wxll² 21 + 411 (9 + 10n L2)
max G -| ||
|| wk+1l 1| + +( + 5n 27 2
k=0 ||l - wk+11 112 + 4n² (9 + 10n² L2²)
k=o max ||
|| wx+1l 1|22 + (4 2y)21))) 27 L
|Iwo - =all2 + Σ k= || wx+1 1|
km
2,2
+ 81)
max [[G,]p) + 4,7 (9 + 10
max || 1|
k=0
29

---

Published as a conference paper at ICLR 2025
4 + 24
1| Wx+112+
(4+51 41
[1w00 20l2++8)
+ 81/²
Σ
T
max ||G:|??
1 1n2
Rmm
41
T-1
+ +//p (9 + 100
max ||Gx&l² 1|
k=U
4 + 200 L4
(1200 - =11 + - --4 1.2
2,
11000- 2012 + 1 41 1.2
161/ L2
T-2
max ||G:|*
i=0
+ D
T-1
max |+all
+
(4+ 51) 2
||100 - 20l1 + 8172
T
max |[G:l?
1 212
1=0
+41/ (9 + I22)
T--1
max ||G 2|
k=0 ===
4 + 200
2,2
1,1/a
|1 =11 + 1 1 |1100 -201²
2012
Fmma + 4n, 2 Pank
1 L7
1 1 41
(4+ (²) 4r22
|1000 2011 - 817² Emp,
+ +41 (9+10n² Emaa
1- 2n2
4 + 201z² T,a
||20 =11 2.2 (4 + 20my² 1.4) + (1 - 1,2) (4+ 5-555n/2 1n2 1/w0 -zul? Emuka
1 6172L2
17- (1 617
161/IL2 I22 (4 + L+) + 32 L (4 + 5n L (1 61) + 4n² (9 10n L2) (1 4n/ (1-
(1-61)² 6n1² L.?)
(1 - (1-
2z (4 + 20
Emk
1- L-
4 + 20nj' 1
1,2 (5n)²12 + +6) 6r7² 222
||100- 201l²+ + 407 (9 + 4112,2 - -20
1|:0- 2²112
Emaka
1 -61
1 1-6r2I2 L?
4nDz (4 + 2011* L7)
Emk
1-6,2
Under Assumption 3. due to Lemma 10 there exists
722 ton (2x)² S (112k-1 - 2k + n (2) - nF (wx)ll + n mmax ||Gk- 11)
4|| == 2n2² (4 4n (2) 1| w 4n² (9+88n2 Ln² max || 1?
By adding the two inequalities above and summing them with & E [[']], we obtain
Σ T k= ,iA(EE, wx)
T Σ
(17)tam + || - 1/ oFFooo (wx)
k=1
S 4 Σ T
k=1 || - wall + 2n L2 (4 + 4:² L22 Σ T'
k= |1066-1 - wwll
+ 4n (9 + 8n8 8n²L² E k=1
max 11=
T
12 1,2 (T+ IG,-1) 2 |1 -wkkk 12)
$ 4 1
|| w2 + 47j² (9 + 1818212 81)2(( Σ k=1 max || il 1|2
k==
+ 22 (2(1+ 4n² L2) n² (L + LG)² kmml
| wvll ?
= > T-1
K=0 1|z8- - 1 1| 2 + 4n² (9 + 8072 L2)
max |xxll
0=
+ L² (8 + 8 L2 + 7² (L + La)²) Σ
T-
|| W 2
k=0
30

---

Published as a conference paper at ICLR 2025
According to Lemmas 17 and 18 there exists
Σ 1
T
(F wx) < 4
T-1
1| wk+1 11 41/ (9+ + L3)
Σn max ||xxll2 + 2nj² L2
T-1
k=0
h=o
+ Snj² L2 + 1p (L+ + LG)
Ex1 h=o
T-1
|| - 112 + 41,² Σ
r-
max || G 1
1 41221.
i=
+ |l10 - 201l²)
21 (8+ 81 + +17 (L + LG)²)
1
1 1-41
- 4n22
120 2²1
1- 61 4n²² LLG 2/
2n/ (L + 2
|w0 - 2011
1- 6n²² I - 41j² LLG - 277² L3
81/² (L+ + La)²
T-1
max ||G |
1 - 67 - LLG - 2n1² L'
k=0
2n (1 1.2)
+ 1 - 6,2 - 412 - 201 2Zg
max ||Gxll
k==0
817² L2 8 (8+ 87 L2 + 11 (L + Lc)))
+
4n7 (9+ (1++87222) 87 +
Emnaa
1- 12
27/²13 2 + +-812 + 11² (L+ + La)*)
11200- - 201l2
- I?2
4 411 --721,1) + 2112 1,2 (8 + 8, + 112 (T. T.G)))
<
1120 170-22 2²1
1 1-6 - 41 LLG 2,72
(1-4410 41--112177) + 1? (8+81) 8,2 + 1p (I. + Toa)²)
+ 22
1- 1-6 L 4122 2012
81/ (8+87) 812 + 172 (L + La)²)
+ Emit
(nn (1) +
1- L.2
817² (L + 1a)² (4+ 27 (8 + (L (L+L))))
+
(1- (1-6122² 4 - 20 23) (1 L2)
2n7 (L + 2 (4
2n 2 1 81 + 12 (L + Lai))
+
(1-61212 - 4np T.G. 21)) (1 122
2r² (8 + 21 + 11 (L + Lo)²)
|1w0 =oll
1 --4121,2 122
Under Assumption 4. due to Lemma 10 there exists
222 (2x)² 12 5 (1) 1 - 24 + 1) 1F (wx)ll + nI 2)²
2 | - 2x
-
2 +
2n²² (T. || wxll + T.G,,, 1)) 2
< 4 |2 - wx 1|2 + (4 + 2T) || - wxll2 + 2nj² D22 Lem-
L (2I + Lam.)
31

---

Published as a conference paper at ICLR 2025
Hence, with I|w. zxll² s 1p (L + Los ,)8 ||wk- wxll² and according to Lemmas 17 and 18 there exists
E k=1 Aat wx) S E (L + LG)² (4+31) 37) 11w0 zoll
(4 E (L L (4 + 31 Σ ===
T --1 2 wk+ill + 22²² E k=1 Lou-, (2L LGa-1)
S FoOn (T. + T (4 + T, 11:00 - =0l12 + 211 Ex T. (2I, + I.GH-1)
4+ E (L + L (4 + 37 (3) EG2 1|20- - =1 + EG2I (L+ + LG)² EG 1100 - z s0l?)
1 4n Eg (L La)²
4 + ECT (L+ La)² (4 37 1
EG2 ||:0 - 201 + 11w0 zol1
1 - 4n Ea 2 (T. + I.G)
4 EGN² (L + L (4 317² L2)
EG2i (L+ + LG)² EG + Eas (L Lo) (+ 318 L2)
1 AnLG Eg E (L + La)²
+21 D2 E k=1 LGI-1 (2L LG.-1)
4+ E (L + L (4 37 (4t L2)
1 - 4nG - Fa2 (I+ T.a)² EGe 1|00 =2 [EEc2 + EGENT (L + La)² 31
1 -n - E.G F (G)+
+ +4+ 31 (172 (L + La) Ea) W - aoll2+2r2 D2 >
LG (2L + LG
k=1
From Lemma 20 we obtain the following lemma.
Full version of Lemma 5 For a game 9 converging to a monotone game with any closed convex sei Z C Thts and monotone and L-Lipschitz operator Fx.: 2 + R", let z" be solution of the
game G. Then VT 2 1, in E
0,
there exists t" E [[TT] satisfying VoL
1
1
4 20n L
2nj (5n) + 6)
1/2 AZL-, w(-
6,,212 11=0- 2011
||wo zol?
T
1 1- 2 I.2
41² (9 + 2 -20m
4nDz z (4+ 244)
+
Emaa
Emnk
6r
1 L
Under Assumption 3 ifne (. VBL-
there exists t" E [['']] satisfying
4((1 - (11-41721.) + 2n 1 (I. + L=)² + +8 8
12 AZzee, wer) 5 T
|1 - =0'11 + 11 - 201?
1 1-6 4 LLG - 2112
2n7 (L Lc)² (4+ 2n² L2
+ (L+ of (
2 (8 L + +12 (L+ + LG)
+
(1-61' 6,2 4n LLG 2n 18) (1 112
1 41
8nDz(1 - 4n2 + 4m DzL 112 ( La)² +8 8122
Emn + 4np Emmza 9 8
1 1 L LLG - 2112
(8 22
8 + 122 (L+ + Lc)))
27²² (L + La) 4 + 21 L2 8n) 12 + 1? (L + Lai
+
1 1 1,2
(1 - 1,2 1,2 - 41 LLG 21 21 4112
32

---

Published as a conference paper at ICLR 2025
while under Assumption 4 if 1y1-4m1h -e-nnLLG-BBBBe (L+ LG)² > 0, there exists [T]] satisfying
1
4 E LG) (4 31j I.2)
1²² 12A( wx-)
S
EG2 ||20 - 2²11 4n Eg ?2 (L + LG)
T
4EG2 + EGEG21 (L + LG)² (4 31
+ 4 + 31/ (1p (L + La)² Ba) llwo - =0ol
+
-nnla Eg P (I. Ta)²
22n D2 E k=1 I.G-1 (2I. + Taa-s))
where maxxae (1|2 2*11, 11 - well.
Proof. VT 2 1, there exists t" E [[T]]
11 (2r w S 1 T
E AZK, ws)
T
The lemma is directly obtained with the inequality above from Lemma 20
C.3 APPROXIMATE MONOTONICITY OF A(za, wx)
This section shows that A w/. either non non-increasing or increasing at a low rate across iterates with the OG algorithm.
Restatement of Theorem For a game G converging to a monotone game, Vn E (0, 2T. Zk Z, A A (R, wk) 2 (Z Wh+1) - 3/ (3Dz + 4n max || Il) max [|G&|], while A(ER, wa) 2 A Wx+1) " (3D + 2n max || I]) max ||& if = max max[[]x411 #k+1lls l| - =x1 and = R..
Proof. In this proof, "LHS" stands for "left-hand side". Due to Lemma & there exists
2 AZZZ wx) - AT² wk+1) eam (zx) + F (zx) Foo (wx)1 (12 (2++1) 1)2 1² Foo (#6+1) - Foo 1)
(177 + nexl 1| + 2/ Fro (Zx) - Pox (wx))1²)
(177Fo + mc++1 2| + 17 | (Zx41) Foo 1)1+
(16)
Considering that Foo is monotone and L-Lipschitzz and 1/ (0, ) there exists
2 (n - 1/ oo (zx), zx+1 zu) S 0
(17)
1 4
-2
||a++1 wx+1ll Fl (2++1) - F7 (wx+1))12 00
(18)
According to the OG algorithm, there exists 24 m (wk) nn (wk) - Wh+1 E (w++1) and 24 1/Foo (Wk+1) 7/Cx (wn+1) 2641 N (2x+1)) Hence,
- (2k - F) (ww) - G((x)) - wA+1: wk+1 - 2k+1) S 0
(19)
2 (2k - nf so (wx+1) 1/Gx (Wk+1) 2k+1, Z6+1 2x) <
(20)
Since c(zx) E (22), there exists
- (no((x) 24 - wk+1) 0
(21)
(no(2x), =x =k+1) 50
(22)
According to Lemma Bladd 2 -nnF -24+1
-4+1 E -N (2(2z+1); Ck+1 E 11 (- FoFo (2++1)),
-2 (nc()*+1) ) + (2 1), - (w - G (w - 2041) 50
(23)
-2 (no((*+1) + 1 Foc (#x+1); - $
(24)
33

---

Published as a conference paper at ICLR 2025
there exists the following inequality:
Expression (66 + LHS of Inequality 17 + LHS of Inequality (8 + LHS of Inequality 19
+LHS of Inequality 20
LHS of Inequality 21 + LHS of Inequality
LHS of Inequality (3
+LHS of Inequality
24
Wk+1 - 2k+1
+ In (2x) + tc((zs))) - + Wk+1 + 2x+1
+ (wx)) of (o (zx)
2
2
+ || F) (10K1) 2k41 np(=x+ ( 111 (yGG((wn)) wh+1 2x+1)
+2 (n)Gk (10k(((k+)))))+)))))))))(()))( #k+1 - 2x) + (Wx+1) n7(x++1 + FFo
2 7) ||wx+1 =*+I|| max ||&x|l 2n/ || - =all max | - 4v/² max |o max |G&|]
77 (3D2 + max Fo II) max |G&
(25)
and there exists the following inequality if the game is unconstrained:
Expression (66] LHH of Inequality
+ LHSS of Inequality (18) LHS of Inequality (99)
+LHS of Inequality
20
LHS of Inequality 21 + LHS of Inequality 22 LHS of Inequality (23
+LHS of Inequality
24
2 (wx)) Wk+1 =k+1) + (n)Gk( #k+1 zx) + +
P (#x+1))
mD max |
2np max ||Gx|| - 27j² max Foo max ||G&ell
2 17 (3D + 2n max || (FFooll) max ||&
C.4 CONVERGENCE RATE OF A(zk, wx)
fan In the following lemma, we demonstrate the relationship between (F,2) (Wk+1) 1 and A (Zk, wk).
Lemma 21 For game G converging monotone game with any closed convex set Z Re and monotone and L-Lipschitz operator Foo Z +R IR" and zk, Wk, Wk+1 E 2, there exists
fan (wn(()+1)) S (2 + nL) Viizu, wk) + (2 + 11) max ||
If Gk is LG, Lipschitz and G. = 0, there exists
lan (lan(w++1) S /2 v)) v ((z,, wx) + (1 (1+ max ||G + LG,
where min(max || wall Dz} under Assumption and stances.
Dz under other circum-
Proof.
Due to the OG algorithm and the non-expansiveness of the projection operator, there exists
| - Wk++1l
|| < || Il [zk- ( + || - Il [ (=x)]l
I r (n (Ex) + [ [2 n/&2 (wx)) TI [*x (=)
tan
S q (F.2) (2x) + I| (wk)) 1/ (2x)l [|
According to Lemma 10 we have
+ nL
fan (zx)
l|
wh+1l + (Zo) - Fxo(wx) + max[ max[|G+|]]
7
Hence, there exists
tan (wk+1) 1 S (1 + TL) fan
(2x) + (2 LT) (wx) - Foo (2x)l Il + (2 + nL) max ||
(F.2)
$ V2 11) / fan
(#x
| (wk) (2) 2 + (2 + L) max || |
= v2 + 12)) / A wh) + (2 + LL) max ||Gl|l
34

---

Published as a conference paper at ICLR 2025
If G₁ is Lo. Lippschizz there exists
ran (wk+1)
2k wk+1 Poo (Wx+1)) Fox (wx) T.on D
2 - wo+1/l + Fl - Foo (2x))l + [Fo Fa (owllll + LG D
11
np.
1| - wx+ill (Zo (ow(w)ll LG.
Hence, there exists
p pan (W++1) S (1 + nT.) tan
(2 (2) (wrk) ( + (1 + vT) [(
La. D
$ V2 + n1) V tan
(F,22) (zx)² + [F)( Foo(2x)
(1 + nL) |[Gx(=))]| II + LG. D
x (2 + bn) VA(a,, wx) + (1 + nb) max Gaall + LG D
Now combine all the results above in this section in Theorem 6 for the proof of Theorem
Theorem For a game G converging to a monotone game, under Assumption
if 1]
(0. vGL under Assumption 3 if
0, V6124411a
under Assump-
tion if n E (o, { (zu-Lay) ahe)
VA(TT WT:HTTT WT(+T2) tan (ZT(+T2)
G vT
+
T= max ||Gx]]. Under Assumption
in E (0. )or.).
tan
(w++78+1)
$
v2 + nL) Ci
+ +V2(2+nDL) V C2 Eie k=T,
max
|G
VT2
+ (2 nL) max |Gr,tzal
4+ 20n TA
22 maxteN || 2|-12 4n (5nH2 +
C "
maxieN |/0 zell
1 1-6122L2
417 (9 + 1,22 20m² L²)
4nD2 (4+20m L*)
Emaa
Emnk
1-67 L2
617² L
C2 3D + 4n max Fooll
11
Under Assumption
3
Ann (WT, +1++1) < /2(2+nL)C 4 +2(22+ Cc Σ x
max ||aa|
VT²
+ (2+ 1T) max |Gr|| + Lop Dz
4(1 - 11) + 27
1/2 (L + LG) + 8+ 87/212
1
C
maX || ==1 + max || zell
7
1 1-6 LLG 207² L3g
277 (L + Lo)² (4 14+27 L2
21 +1² Lo)))
212 (8 81 +1² (L LG)²)
11-6,22,2 4n LLG 12) (1 1,2
1 1
8nDz(1
4n DzI2 112 (L La)² +8 8
9 9 Ema + 4n² Emar
1- An 2112123
35

---

Published as a conference paper at ICLR 2025
2² ( 8rf + +2 (L + La)²)
2n (++ Lc)² (4 2 8772 + + La) )
+
1- 412 L2
(1- 2
C2 3Dz + 4mmax Fool
" Under Assumption
ton (WT, (WT1+T++1) S (2 + CL
+ +2(2+11) V |= max Gi
VT2
(1 + +D) max |TT|I LGGD
1 4 2 (I. + _ (4+ 312 (4+31
C
Loz maxieN 2=12
1/ 1 - 4n - 12 (I. T.g)
4EG2 + EGEG21 (L + L (4 (4-3172 L1)
+ 31 (1p (I + La)² Ea) maxten l| 24 12
1 -nLo Ea (L La)²
+2n² D3 k= LGz-1 (2L Launl)
C2= 3D + an max Fooll
7)
where Do = max 2 2zd 11,11lzz well,. D = wax(| - and for unconstrained cases 2 and for constrained cases = 4.
- 2x113. & E N.
Proof. According to Lemma 5 there exists 1" E (Ti, Ti +2] so that A =
Since Ti < 1", according to Theorem 3 there exists
3D + maxax || F
A A WT, +1.) I A(ze,, we-) + Σ Z
max ||G
under any one of Assumptions and and there exists
3D + an max Fooll max ||&
( +T, WT wT++)) < (zee, wi-) +
k=
under Assumption f with unconstrained games and = 2. Considering that all 2,, wy, i E N are in
bounded convex set due Lemma [9] have = 4 under Assumption 4 in constrained game. The theorem is obtained by directly combining the two equations above with Lemma and Lemma
99
C.5
PROOF OF THEOREM
Cases where T < 3 are trivial with Big O notation since a(x) O(b(x)) is true if x belongs to limited set, Va(x) > 0 and b(x) > 0. Suppose T = Ti + T2 + T, e N for T > 3 and
Ti T2 + 2 or T2 1. According Theorem 6. we have
C2 E k=I, (2 + +D) (2(++ V
tan (WT) = lan (WT, +T+++)
max G
VTz
+ (2 + LT) max [[T
where C₁, Cg > 0 under Assumptions and Hence,
tan (Wrr = 0
+ Exm max |Gall + O (max [|Gr-1l))
VTz
=0 max
1
Σ
max ||&bll max [Grll)
V V
k= k=
36

---

Published as a conference paper at ICLR 2025
Also, we have
tan (WT) =plan (WT, - (W+;+ V2 + nL)C1 + (2
V
C2 E k=li
max G
VT2
(1 + nL) max ||T + LGr-1 Do
where C1, C2 > 0 under Assumption 4 and Do is D in Theorem Ve > 0, 3No VN > No.
I[k= (1 4nLG.) - 1 < and LGN < c so that 1 4n Eg Ec2n (L + Lc) > 0 if No
were the initial time O. Since VNo > 0, T = O(T - No) for T No. (T + No) 2 T/2 and EG < 4, we have
Aon (TT) (wo)
=0
+0
2 Σ
max ||Gr]]] + O (max ||T|l) +0 (Lar Do)
22
k=
E max | max ||TT|l, Tar })
=0
max
VT' k=T/2
Then, according Lemma 3
(c. rrea (2) and To.o(*) VND I rra (z). Hence, we have
max pan (wT). To.D(WT) PG.D(WT) plan (WT)
VND D
Therefore,
max lan (WT), (WT) Pg Po.((wt)
VND D
max VT Σ k= max |Gxll, max ||rrll] })
under Assumptions 2 and including D D2 > while
max lan (wr), (g. Ps.
VND
max |G&l], max ||TT| L)r.))
=0 max VT
T/2
under Assumption
37


Reviews:
[{"review_id": "b6UqQ941VZ", "reviewer": "Reviewer_BAfq", "summary": "The authors study time-varying games in, both, bounded and unconstrained strategy spaces. In particular, they are interested in the performance of Extra Gradient and Optimistic Gradient algorithms in sequences of games that converge to some smooth monotone (also known as diagonally concave) game, i.e., the pseudogradient of the player's payoff functions is monotone and L-Lipschitz. They prove that, under bounded accumulated perturbations assumptions, both algorithms converge to the set of Nash equilibria of the monotone game at a rate approximately O(sqrt(T)^{-1}) with constant learning rates.", "questions": "Kindly refer to the weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "Although I am not familiar with the majority of the literature, I believe the class of time-varying games studied in this work is rich and interesting. Therefore, the novelty of this work should be appreciated.", "weaknesses": "1. Could the authors improve the theorem statements? Although I appreciate the accuracy of the mathematical formalism, the text has not been refined adequately to improve the clarity of the statements. I suggest either expressing some of the quantities involved in Theorems 1 through 4 in English or/and predefining some of the maximization functions before the actual statement. \n2. There exist multiple typos in the manuscript. A careful read is advised. I mention here the ones I find the most hurtful for clarity:\n* In lines 85 and 88 z^{*} is used before it is defined. \n* In line 163 \\lim_{t \\to \\infty} G is not defined in Definition 2.", "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": "wDNr5CktFa", "reviewer": "Reviewer_KZkR", "summary": "In this paper, the authors present the last-iterate convergence of EG and OG algorithms in bounded and constrained time-varying, multiplayer games that converges to a monotone game. The convergence results derived for the time-varying games are similar to known tight results on corresponding time-invariant games.\n\nIn specific, the author proved that EG and OG with a constant learning rate both converge to a Nash equilibrium at the rate of $\\mathcal{O}(1/\\sqrt{T})$ under three conditions (Assumption 1 (general convex bounded), 2 ($L_G$-smooth perturbing), 3 ($L_G$-smooth perturbing+$G_t(z^*)=0$)) respectively.", "questions": "- For assumption 3, $z^*$ is the NE right? Then would $G_t(z^*)=0$ be a very strong assumption? It makes senses to me that $G_{\\infty}(z^*)=0$, but what's the natural justification of assuming that  $G_t(z^*)=0$ for all $t$?\n- Also, for assumption 2 and 3, do you assume that $G_t$ is $L(G_t)$-Lipschitz for all $t$?\n- I believe it's a typo, but in the first line of the conclusion, you want to say \"bounded and constrained cases'' instead of \"bounded and unconstrained cases\" right?\n- For lots of your theorem statements, you include terms like $\\max ||G_{t^*}||$, $\\max ||G_k||$, $\\max ||F_\\infty||$, can you specify what $\\max$ you are taking respect to? Like $\\max_{z\\in \\mathcal{Z}} ||G_{t^*}(z)||$? Since it's quite confusing right now.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-motivated, with the introduction and related work sections effectively contextualizing recent advances in time-varying games. The authors clearly articulate how this work improves upon existing results in the field. \n- The paper is well-organized: it begins with foundational concepts, including definitions of the game, learning algorithms, the measure of proximity to Nash Equilibrium (tangent residual) and its properties, as well as assumptions about the games. The authors then proceed with separate analyses of the convergence of EG and OG methods, systematically outlining the proof techniques and presenting each step in detail.\n- While I did not examine every detail of the proofs, the mathematical reasoning appears clear and correct.", "weaknesses": "- My primary concern is that the contribution of this paper may be perceived as an incremental extension of the method from [1] to time-varying games.\nIn specific, for proofs of last-iterate convergence of both EG and OG, the author seems to follow the same proof procedure as [1] does but adding additional analysis for the time-varying $G_t$'s which results in additional terms in the bounds. \nFor example, this paper's Lemma 4 argues best-iterate convergence with rate $\\mathcal{O}(1/ \\sqrt{T})$ of tangent residual, and this corresponds exactly to Lemma 5 of [1], while Lemma 13 and 15 corresponds to Lemma 3 and 4 of [1] respectively. Moreover, Theorem 1 which establishes the monotonicity of the tangent residual, corresponds to Theorem 2 of [1].\n\nI acknowledge the authors' careful analysis of the perturbation terms. However, could you highlight and summarize the main proof techniques that are novel and distinct from those used in [1]? This additional clarification would be greatly appreciated, and discovering additional novel technical contributions would very likely lead me to improve my evaluation.\n\n\n\n\n[1] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 33904–33919. Curran Associates, Inc., 2022. URL https://proceedings.neurips.cc/paper_files/paper/2022/file/\ndb2d2001f63e83214b08948b459f69f0-Paper-Conference.pdf.", "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": "DtXseXlmyK", "reviewer": "Reviewer_Gqyb", "summary": "This paper proves last-iterate convergence rates of extra-gradient (EG) and optimal-gradient (OG) algorithms for multi-player smooth games with bounded actions and with time-varying cost functions. The time-varying game is assumed to converge to a smooth monotone game with time, i.e. the perturbations decay to zero eventually.", "questions": "1. Even two-player zero-sum bilinear games are not strictly monotone; how restrictive it is to assume that the game converges to a smooth monotone game eventually?\n2. If Nash equilibria exist, can these two learning algorithms guarantee to only converge to Nash equilibria? If not, what else assumptions and/or treatment are needed?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "While previous convergence results for EG and OG are mainly provided for time-invariant games and time-varying games that are restricted to be two-player, bilinear, zero-sum, this paper pushes the boundary and shows fast convergence results of EG and OG algorithms for multi-player, time-varying games that eventually converge to smooth monotone games and with convex constraint set for actions. In general, I think it is a strong submission and the results are quite interesting, espcially that the author(s) use tangent residual to measure proximity to Nash to overcome challenges could appear when using gap functions.", "weaknesses": "1. (Starting line 432) The numerical experiments section\n- The author(s) claim that they provide results for general multi-player games beyond two-player zero-sum games. I assume by this claim they mean multi-player general-sum games. However, the experiments only show results for zero-sum cost functions. I think the author(s) should also show results for general non-zero-sum games involving multiple players in order to make their point. Otherwise, I would like to hear more elaboration on that end.\n- The perturbation added to the two players seems to be identical; is that something required for the results to hold? If not, I would encourage the author(s) to remove the restriction in their experimental results.\n- The initial z0 picked in the experiments seems to be very non-arbitrary---both players start from exactly the same point. Could the author(s) elaborate on this? Ideally, the empirical results can be much strengthened by a Monte-Carlo study with many different initial conditions and report of statistical results.\n\n2. Other minor aspects: on a high level, quite some notations and concepts are used in the paper without giving definitions. I would appreciate a clearer presentation.\n- Line 131: variables in the game tuple undefined; game itself undefined; constrained set Z undefined\n- Line 141: variational equality → variational inequality\n- Line 171: existence of at least one Nash equilibrium better be stated explicitly as an  assumption\n- Eq (1):  Euclidean projection operator undefined\n- Line 226: Dr(z) undefined", "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 (Oral)