On the Last-iterate Convergence in Time-varying Zero-sum Games: Extra Gradient Succeeds where Optimism Fails
Authors: Yi Feng
Hu Fu
Qun Hu
Ping Li
Ioannis Panageas
bo peng
Xiao Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: zero sum game
time-varying game
optimistic gradient
extra gradient
momentum method
TL;DR: We study the last-iterate convergence of several learning algorithms in time-varying zero-sum games.

Abstract: Last-iterate convergence has received extensive study in two player zero-sum games starting from bilinear, convex-concave up to settings that satisfy the MVI condition. Typical methods that exhibit last-iterate convergence for the aforementioned games include extra-gradient (EG) and optimistic gradient descent ascent (OGDA). However, all the established last-iterate convergence results hold for the restrictive setting where the underlying repeated game does not change over time.
Recently, a line of research has focused on regret analysis of OGDA  in time-varying games, i.e., games where payoffs evolve with time; the last-iterate behavior of OGDA and EG in time-varying environments remains unclear though. In this paper, we study the last-iterate behavior of various algorithms in two types of unconstrained, time-varying, bilinear zero-sum games: periodic and convergent perturbed games. These models expand upon the usual repeated game formulation and incorporate external environmental factors, such as the seasonal effects on species competition and vanishing external noise. In periodic games, we prove that EG will converge while OGDA and momentum method will diverge. This is quite surprising, as to the best of our knowledge, it is the first result that indicates EG and OGDA have qualitatively different last-iterate behaviors and do not exhibit similar behavior. In convergent perturbed games, we prove all these algorithms converge as long as the game itself stabilizes with a faster rate than $1/t$.

On the Last-iterate Convergence in Time-varying Zero-sum Games: Extra Gradient Succeeds where Optimism Fails
Yi Feng
Hu Fu SUFE fuhu @ shufe.edu.cn
SUFE"
202131018601ive.ce sufe. edu. cn
Qun Hu
Ping Li SUFE
Joannis Panageas University of California, Irvine ipanagea
SUFE
huqun29@ 163.com
1ping0423 163.com
Bo Peng SUFE
Xiao Wang SUFR wangxiao@shufe.eduu.c
ahqspb@ 163.sufe.edu.cn
Abstract
Last-iterate convergence has received extensive study two player zero-sum games starting from bilinear, convex-concat up to settings that satisfy the MVI condi- tion. Typical methods that exhibit last-iterate convergence for the aforementioned games include extra-gradient (EG) and optimistic gradient descent ascent (OGDA). However, the established last-iterate convergence results hold for the restrictive setting where the underlying repeated game does not change over time. Recently, a line of research has focused on regret analysis of OGDA in time-varying games, i.e., games where payoffs evolve with time; the last-iterate behavior of OGDA and BG in varying environments remains unclear though. this paper, we study the last-iterate behavior of various algorithms in two types of unconstrained, time-varying, bilinear zero-sum games: periodic and convergent perturbed games. These models expand upon the usual repeated game formulation and incorporate external environmental factors, such as the seasonal effects on species competition and vanishing external noise. In periodic games, while OGDA and momentum method will diverge. This is quite surprising, as to the best of our knowledge, is the first result that indicates EG and OGDA have qualitatively different last-iterate behaviors and do not exhibit similar behavior. convergent perturbed games, we prove all these algorithms converge as long the game itself stabilizes with a faster rate than 1/1.
prove that EG will converge
Introduction
central problem in game theory and min-max optimization is to come up with a pair of vectors (xr, y/ that solves
min max x #EX yEy
Ay,
Authors listed according the alphahetical order. Shanghai University Finance and Economics
Key Laboratory of Interdisciplinary Research of Computation and Economics, Ministry of Education.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

where X' C R" and y C R are convex sets, and A is n x payoff matrix. The above captures two-player zero-sum games in which x T Ay is interpreted as the payment of the "min player" to the "max player" y. If X = R" and y = IR" the setting is called unconstrained, otherwise it constrained. Soon after the minimax theorem of Von Neumann was established (for compact X. Y), learning dynamics such as fictitious play (Brown [95T]) were proposed for solving min-max optimization problems. Blackwell's approachability theorem Blackwell (1956) further propelled the field of online learning, which lead to the discovery of several learning algorithms; such learning methods include siiiiiiiative-iigtt---us optimistic variants and extra sstra-gradient methods.
method, online gradient descent/ascent and their
Last Iterate Convergence. There have been a vast literature on whether or not the aforementioned dynamics converge in average sense exhibit last-iterate convergence when applied zero-sum games. Dating back to Nesterov (Nesterov (005 D, there have been quite a few results showing that online learning algorithms have last-iterate convergence to Nash equilibria in zero-sum games. Examples include optimistic multiplicative weights update (Daskalakis and Panageas (019 Wei et al. (022]) )), optimistic gradient descent ascent (OGDA) (Daskalakis et al. [2018] Liang and Stokes (2019a]) (applied even to GANs) for unconstrained sero-sum games, OGDA for constrained zero-sum (appliee games (Wei et al. [202T]. Cai al. 20022, Gorbunov al. [002bb] and extra-gradient methods (Mertikopoulos et al. (2019), Cai et al. [2022]. Gorbunov et al. 2022a]] using various techniques, including sum of squares.
Nevertheless, all aforementioned results assume that the underlying repeated zero-sum game remains invariant throughout the learning process. In many learning environments that assumption is unrealis- tic, see (Duvocelle et al. [2022]. Mai et al. [2018), Cardoso et al. 2019)) and references therein. One more realistic learning setting is where the underlying game is actually changing; this game is called time-varying. There have been quite a few works that deal with time-varyine games, where they aim analyzing the duality gap dynamic regret (Zhagg al. [022] and references therein for OGDA and variants. However, in all these prior works, last-iterate convergence has not been investigated; the main purpose of this paper is fill in this gap. We aim at addressing the following question:
Will learning algorithms such as optimistic gradient descent ascent or extra- satra-grrdient exhibit last-iterate converge in time-varying zero-sum games?
Our contributions. We consider unconstrained two-player zero-sum games with a time-varying payoff matrix (that is the payoff matrix A, depends on time t)
min max T Agy, #ER" yE
(Time-varying zero sum game)
in which the payoff matrix A, varies with time in the following two ways:
Periodic games: A, is a periodic function with period T, i.e., ACtT = A+-
Convergent perturbed games: A, = A + Br, lim B, O.
In a repeated time-varying zero-sum game, players choose their learning algorithms and repeatedly play the zero-sum game. In the 1-th round, when the players use strategy (Ie, Vt), they receive their payoff - AT 24 and Aryt-
In this paper we show the following results:
For periodic games: We prove that when two players use extra-grades gradient, their strategies will converge to the common Nash equilibrium of the games within a period with exponential rate, see Theorem 3.T for details. Additionally, we provide an example where optimistic gradient descent ascent and negative momentum method diverge from the equilibrium with an exponential rate, see Theorem 3.2
To the best of our knowledge, this is the first result that provides clear separation between the behavior of extra-gradient methods and optimistic gradient descent ascent.
For convergent perturbed games: Assuming Σe= |l B, || is bounded, we prove that the ettra-gradient optimistic gradient descent ascent, and negative momentum method all converge to the Nash equilibrium of the game defined by payoff matrix A with a rate determined by BBe} and singular values of A, see Theorem 3.3 Furthermore, we prove that extra-gradins stra-gradient will asymptotically converge to equilibrium without any additional assumptions on perturbations besides limy++oe B. = 0, see Theorem 3.4

---

Related work on time-varying games. The closest work to ours that argues about stabilization of
mirror descent type dynamics on convergent strongly monotone games is (Duvocelle al. [202]).
Most of the literature has been focused on proving either recurrence/oscillaaing behavior of learning
dynamics time-varying periodic games (Mai et. [2018) Fiez et al. [202T] and references therein
or performing regret analysis (Roy et al. [2019]. Cardoso et al. [2019]. Zhang et al. (022]). In
particular, the latter work extends results on RVU (Sygkkanis et al 2015 bounds to argue about
dynamic regret (Zinkeiich (2003]).
Technical Comparison. We investigate the last iterate behaviors of learning dynamics through their formulation of linear difference systems. This approach has also been used to establish last iterate convergence results for learning dynamics in time-independent games (Zhang and Yu 2020 Liang and Stokes [2019b) Gidel et al. 2019]). One common key point of these works is to prove that certain matrix has cigenvalues with modulus larger than 1, then the last iterate convergence can be guaranteed by the general results of autonomous difference systems. However, this method cannot be generalized the time-varying games where the corresponding difference systems non-autonomous. In particular, the dynamical behavior a non-autonomous system is not determined by the eigenvalues of single matrix. In fact, it is difficult establish convergence/diverggnee results even for non-autonomous system with special structures, such as periodic or perturbed systems. In this paper, to get such results, we employ both general results in linear difference systems, such as Floquet theorem and Gronwall inequality, and special structures of the difference systems associated to learning dynamics.
Organization. In Section we present the necessary background for this work. The main results are stated in Section 3 In Section E
we present numerical experiments and in Section 5 we conclude with discussion and propose some future research problems.
2 Preliminaries
2.1 Definitions
Zero-sum blinear game. An unconstrained two players zero-sum game consists of two agents
V = 2), and losses of both players are determined via payoff matrix A E Raxm Given that player selects strategy x E I" and player 2 selects strategy y E R"", player receives loss "1 (1(2, y) (z, Ay). and player 2 receives loss u2(2, y)
(v, A 2). Naturally, players want to
minimize their loss resulting the following min-max problem:
min max x Ay wE yER"
(Zero-Sum Game)
Note that the set ((x', """) = 0, Ay 0} represents the set of equilibrium of the game.
Time-varying zero-sum bilinear game. In this paper, we study games in which the payoff matrices vary over time and we define two kinds of such time-varying games.
Definition 2.1 (Periodic games). A periodic game with period T an infinite sequence of zero-sum bilinear games {Ar C Rn*m, and A A, for all t 0.
Note that the periodic game defined here is the same as Definition 1 in (Fizz et al. 2021]) except for the fact that we are considering a discrete time setting. Therefore, we do not make the assumption that payoff entries are smoothly dependent on L.
Definition 2.2 (Convergent perturbed games). A convergent perturbed game is an infinite sequence of zero-sun bilinear games ) C Iaxxm, and lim; sc. A. = A Afor some Ru Equivalently, write A, A + B. then liu B, 0. We will refer to the zero-sum bilinear game defined by A as stable game.
Learning dynamics in games. In this paper, we consider three kinds of learning dynamics: optimistic gradient descent ascent (OGDA), extra-gradient (EG), and negative momentum method. All these methods possess the last-iterate convergence property in repeated game with time-independent payoff matrix, as demonstrated in previous literature. However, here we state their forms within time- varying context.
3

---

Optimistic gradient descent-ascent. We study the optimistic descent ascent method (OGDA)
defined as follows:
Ft+1 = It - -2 + 13/--1
(OGDA)
yr++ - yt + A Tt 1 Ft-11
Optimistic gradient descent ascent method was proposed in (Popoy (1980]) and here we choose the
same parameters as (Daskalakis al. (018)). The last iterate convergence property of OGDA in unconstrained bilinear game with time-independent payoff was proved in (Daskalakis et al. (2018).
Recently, there are also works analyzing the regret behaviors OGDA under time varying setting
/Zang et al. [2022], Anagnostides et al. 2023
Extra gradient. We study the extra gradient descent ascent method (EG) defined as follows:
Fe+ =x+ -z -AA-, Ve+
yt 7Ag It. Te+1 a 1h+1 + A,A, 2
(EG)
Note that the extra-gradient method first calculates an intermediate state before proceeding to the next state. Extra-gradient firstly proposed in (Korpelevich (1766) with the restriction that = Here we choose the parameters same as in (Liang and Stokes (019a)), where the linear convergence rate of extra-gradient
the bilinear zero-sum game with ume-independent was also proven. Convergence of extra-gradient on convex-concave game was analyzed in (Nemirovski [2004) Monteiro and Svaiter (2010), and convergence guarantees for special con-convex-non non-concave game was provided in (Mertikopoulos et al. (2019)).
Negative momentum method. We study the alternating negative momentum method (NM), defined as follows:
Tt-1 Iz 7A + f2(11= x(-1),
(NM)
Ut+1 = Yr + 744 1 B2(11 - y0-1),
where B1, < 0 are the momentum parameters.
Applications of negative momentum method in game optimization was firstly proposed in (Gidel et al. (209)). ). Note that the algorithm has an alternating implementation: the update rule y-+1 the payoff Af41 thus in each round, the second player chooses his strategy after the first player has chosen his. It was shown in (Gidel et al. (2019) that both the negative momentum parameters and alternating implementations with inneeindependent payoff matrices. Analysis of the convergence rate of negative momentum method in strongly-conver crongly-concawe games was provided in (Zhang and Wang 2021
crucial for convergence in bilinear zero-sum games
2.2 Difference systems
The analysis of the last-iterate behavior of learning algorithms can be reduced to analyzing the dynamical behavior of the associated linear difference systems (Zhang and Yu (2020), Daskalakis and Panageas 2018)). When the payoff matrix is time-independent, the associated difference systems is autonomous. However, as we are studying games with time-varying payoff matrices, we have to deal with non-autonomous difference systems. general, the convergence behavior of non-autonomous difference systems is much more complicated than that of autonomous ones (Colonius and Kliemann
2214
Linear difference system. Given sequence of iterate matrices {Ar] condition X, E R", a linear difference system has form
R and initial
X = A,X,-
(Linear difference system)
If A, = A is matrix independent of time, the system is called an autonomous system, otherwise, it called non-autonomous system. We care about the asymptotic behavior of X,, that is, what can we say about X; as 20.

---

Definition 2.3. A point X is called asymptotically stable under the linear difference system if
38 > O,VY, s.t. IY - x 8 + lim 1I -112=0
Moreover, X is called exponentially asymptoticalll stable if the above limit has an exponentially convergence rate, i.e,, a E (0, 1), such that
-
- X1125 a X112.
is well known that for autonomous linear systems, being asymptotically stable is equivalent being exponentially asymptotically stable, as shown in Thm 1.5.11 in (Colonius and Kliemann (2014) However, this equivalence does not hold for non-autonomous systems.
Linear difference system has a formal solution Xr+1 = oI' A, However, such a representation does not yield much information about the asymptotic behavior of solution as co, except the case of autonomous system. In this paper, we mainly consider two classes of non-autonomous linear difference systems: if the iterate matrix Ag is periodic function of t, the system called periodic system; and if A, has limit as t tends to infinity, the system is called perturbed system.
Periodic linear system. If the iterate matrix A, in linear difference system satisfies A, = AA+T. VI E E, then the system is called a periodic linear system. Denote = I Ar-j. For a T- periodic equation, the eigenvalues a E C of À is called the Floquet multipliers, and the Floquet exponents are defined by A + In(la,]). The following Floquet theorem characterizes the stability of periodic linear difference equation.
Proposition 2.4 (Floquet theorem, (Colonius and Kliemann 2014 )). The zero solution of a periodic linear difference equation is asymptotically stable if and only if all Floquet exponents are negative.
Although Floquet theorem provides a method to determine whether a periodic system converges in general, considerable further work may be necessary in order obtain explicit convergence criteria for specific equation. That is because even we know the modulus of the largest eigenvalue of each Ar, it is usually difficult to compute the the modulus of the largest eigenvalue of each I1 A due to the complex behavior of eigenvalues under matrix multiplication.
Perturbed linear system. If the iterative matrix A in linear difference system satisfies A. A++B and lim;- B. = O, then the system is called a perturbed linear system. The convergence behavior of perturbed linear system is not clear in the literature. A general result in this direction is the following Perron's 's theorem:
Theorem 2.5 (Perron's 's theorem, Pituk
2002 If Xn a solution of a perturbed linear system, then either X, for all sufficient large n or lim XIX,, exists and is equal to the modulus of one of the eigenvalues of matrix A.
This result can only guarantee the convergence of X,, when all eigenvalues of A have modulus smaller than 1. In this case, limp- X, = 0. However, for analyzing the non-autonomous linear systems associated to learning dynamics, is not sufficient as we will show that the stablized matrix of these systems generally has eigenvalues equal to
3 Main results
In this section, we present main results. We present the relationship between learning dynamics and linear difference equation in Section 3.1
investigate the last-iterate behaviors of learning dynamics in periodic game in Section and investigate the last-iterate behaviors of learning dynamics in convergent perturbed game in Section 3.3 Proof' are deferred to the appendix.
"To gain intuition of the differences between autonomous and con-autonomous system, consider the following simple I-dimension example: Te+1 (1 --1)).. is stationary point of this system, but every initial points converges to with rate O( ), thus 0 is asymptotically stable but not exponentially asymptotically stable
5

---

3.1 Learning dynamics as linear difference systems
Formalizing learning dynamics as linear difference systems useful for studying their dynamical behaviors. In the following, we present the formulation of optimistic gradient descent ascent, extra- gradient, and negative momentum method as linear difference systems.
Proposition 3.1. Optimistic gradient descent ascent can be writlen as the following linear difference system:
Tt+1
-mm
nA
M/+1
2
1
-4
yt
(2)
0
2(-1
yt
0
Ulc
Extra-gree geatraggrddent can be writlen as the following linear difference system
F++1
1
AYA,
-oeAt
(3)
Mt++
aA!
1-70A
A
yt
Negative momentum method can be written as the following linear difference system:
r++11
(1+33))
-nA,
-811
St
V/+1
n71 + 3.) (1 (2+
A
-
A
-B2T
y/t
(4)
0
It-1
yt
0
I
0
Ly--14
It is easy to verify that these linear difference systems equivalent to their corresponding learning dynamics by directly writing down the matrix-vector product.
We will also refer to the iterative matrix of these linear difference systems as the iterative matrix of their corresponding learning dynamics. the following, we will study the convergence/divergenee behaviors of these linear difference systems under the condition that (Acr is periodic game or convergent perturbed game. Note that although an intermediate step (Te+ 3e+g) is required in extra-gradient, it is eliminated in
3.2 Periodic games
Recall that periodic game with period T, the payoff matrices (A,)²= satisfy AstT Ag for any > 0. Define
A | zelle I|
(5)
A., measurement of the distance between the current strategy (It, Yt and Nash equilibrium of the zero-sum bilinear game defined by the kernel space of payoff matrix A,, Note that if (x*, y²" is Nash equílibrium of the game defined by A, then (A. x² Agy") (0, 0), and
for E [7]. As in (Daskalakis and Panageas 2018)) ),
)
A ||A (z, x") ==2===++))(((()) ->"lle
thus when strategy is close to equilibrium, A,, will be small. Moreover, A., = 0 if and only (z,, yr) is an equilibrium. In this section, we will consider the convergence/groothh rate of A at function of
We firstly consider Extra- Extra-gradient method. Denote the iterative matrix in the linear difference form of Extra extrra-rradeet Q as At. In the following theorem, we prove that if two players use the extra-gradiem method, their strategies will converge to the common Nash equilibrium of games in the period with an exponential rate.
Theorem 3.1. When two players use extra-grudient in a periodic games with period T, with step size
< 1 where max(o' |ol is singular value A, for some E [T]]. Then
A O (Q. Poly(t)) ViE
where X, max{ [|]] À is an eigenvalue of (II'a Ai) 1}, and ) 1.

---

Note that in periodic game, the iterative matrices of learning dynamics are also periodic, which means that the learning difference systems of these learning dynamics are periodic systems. According to Floquet theorem, see proposition 2.4, the study of dynamical behaviors of a periodic system can be reduced to the autonomous system whose asymptotic behavior is determined by I Av-
The key point on proof of Theorem is an observation that the iterative matrix of extra-gradient a normal matrix, which makes it possible to calculate the Jordan normal form of II A, for arbitrary large T. The details of proof are left Appendix B
In the following theorem, we provide an example demonstrating that when two players use the optimistic gradient descent ascent or negative momentum method, their strategy will diverge an exponential rate, regardless of how they choose their step-sizes and momentum parameters.
Theorem 3.2. Consider periodic game with period T 2, and described by the following payoff matrix
[1. -11. 1], is odd [-111] f. is even
A.
with 2, E. yt E R2, If two players use optimistic gradient descent ascent or negative momentum method, then regardless of how they choose step sizes and momentum parameters, we have
sup A.. E EQ()", where À > i (1,2). sE(c]
Here determined by the largest modulus of the eigenvalues of the iterative matrix of optimistic gradient descent ascent or negalive momentum method.
To prove theorem 3.2 we directly calculate the characteristic polynomials of the iterative matrices products in one period for optimistic gradient descent ascent and negative momentum method under the game defined by 6 To show that these systems have an exponential divergence rate, it is sufficient to demonstrate that their characteristic polynomials have root with modulus larger than 1. Schur stable theorem, which also employed to demonstrate the last iterate convergence of several learning dynamics in time-independent game (Zhang and Yu 2020
achieve this by using
The proof is deferred to Appendix
In Figure present the function curves of A1.: for these three types of game dynamics under the periodic game defined by (6. From the experimental results, extra-gradient converges, while both optimistic gradient descent ascent and negative momentum method diverge.
Patis codbet
Datiniii grobed
2011
12.00
100
Figure Function curves of A1, the game presented in Theorem Extra-gradient converges, while other two methods diverge.
3.3 Convergent perturbed game
Recall that the payoff matrix of convergent perturbed game has form A, = A + B,, where lim;-+ac B, = 0, and we refer to the zero-sum game defined by payoff matrix as the stable game. We denote
A: |A +ell2+||Ayell..
thus A, measures the distance between the strategy (Ir,, yt) in the 1-th round and the Nash equilibrium of the stable game defined by A. Moreover, A, = if and only (are, yt) is an equilibrium of the stable game.

---

In the literature on linear difference systems, a common assumption that needs to be added for convergence guarantee is the following bounded accumulated perturbations (BAP) assumption
(Benzaid and Lutz 1987 Elaydi et al. 1999 Flaydi and Györi 1995
B bounded.
(BAP assumption)
1=0
In the following theorem, we prove that under BAP assumption, all three learning dynamics considered dependent the vanishing rate of Bt.
in this paper will make A, converge to O, with
Theorem 3.3. Assume that the (BAP assumption) holds, i.e., Ex=o Bell2 is bounded, and let be the maximum modulus of the singular value of payoff matrix A, then with parameters choice:
for extra-gradiemt with step size a 1) < 25'
for optimistic gradient descent ascent with step size 1) <
1 2
for negalive momentum method with step size n < and momentum parameters B1 and 32 = O,
have A converge to 0 with rate O(f(t). Here
f(t) max
|Bal2hh
1-1/2
and X E (0, 1) is determined by the eigenvalues of the iterative matrix of corresponding learning dynamics and the payoff matrix A of the stable game.
There are two main ingredients in the proof of Theorem firstly, we show that the iterative matrices associated with these learning dynamics are diagonalizable; secondly, these matrices do not have eigenvalues with modulus larger than 1. Moreover, prove general results which states any linear difference system satisfying these two conditions will converge. The details of proof are left to Appendix E
Remark 3.2. The BAP assumption) can be converted into a constraint on the vanishing rate of Bú Be has vanishing rate like O ((ttz), for some arbitrary small >> 0, then E Bell2 is bounded. We also note that the condition for B, vanish to ensure convergence in general linear difference system, For example, consider the 1-dimension system 21 (1 1 where a O convergence rate of perturbations leads xı diverging with ((t)) rate.
rate O(ztr), Ve 0 necessary
Surprisingly, in the next theorem, we prove that Extra- cetta-ggradien makes A; asymptotically converge to 0, without making any further assumptions about the converge rate of Br.
Theorem 3.4. a convergent perturbed game, if two players use Extra-gradice there holds 1 where a is the maximum modulus of the singular value
lim; A = 0 with step size =1 < 2a
of payoff matrix A.
To prove Theorem 3.4 we first observe that [1eel2+ non-increasing function of since the
iterative matrix of extra-gradient
normal matrix. Next, we prove that if Theorem 3.4 doesn't hold, then | ||y ll will decrease by constant for infinite number of times, thus leading to contradiction with the non-increasing property and the non-negativity of ||xe|l2++1lvell The proof deferred to Appendix
Experiments
In this section we present numerical results for our theoretical results in Section
Experiments on Theorem 3.1 are chosen to be
We verify Theorem
3.1 through period-3 game, the payoff matrices
[
2
3
7
4 2 4
A
A2
Ag =
2
4
7
1
2
8

---

We run extra- stta-ggradient and optimistic gradient descent ascent on this example, both with step size 0.01, the experimental results are presented in Figure D We can see extra-gradient (left) makes A, converge, while optimistic gradient descent ascent (right) makes Ai, diverge. This result supports Theorem 3.T and provides numerical example the separation of stra-gradieet and optimistic gradient descent ascent in periodic games.
poriod game
300
DEaL2:
D4R
300
200
Figure 2: Function curves of Ar for extra-gradient (left). and optimistic gradient descent ascent (right).
Experiments Theorem
3.3
We verify Theorem 3.3 by examples:
2
A
B₁, = 1-l. B22 = B- 1-,,, and, Ba, B 1
4
6
where B = 1-1 70), 1-90, .0]] The step size is chosen to be 0.005. The initial points are chosen [35, 1]. The experimental results are presented in Figure Bl all of the three dynamics make A. converge to and slower convergence rate of perturbations can decelerate the convergence rate of learning dynamics, thus support the convergence result in Theorem 3.3 We also observe that the convergence rate is faster than the upper bound provided the thcorem. Therefore, we conjecture the bound of convergence rate can be improved.
to z0 15, 13)
- [11,3] and No = [35, 1]. y
Datta,
1000
5006
0000
2008
200
1000
30
Figure 3: Values of A for extra-gradient (left), optimistic gradient descent ascent (middle), negative momentum method (right).
Experiments on Theorem 3.4 We verify Theorem 3.4 by two group of examples. The perturbations are
B1, = B. B2, = B- 003 Ba, = B. -022
and
Ba, B -1 Br, B log(()- Bo.t B log(() -1.3
where B [I-10, 10), [-], 10]] The payoff matrix of stable game chosen to be A [ 3), [4, 6]]. Note that the perturbations do not satisfy (BAP assumption). The experimental results are shown Figure We can see these curves converge to O. thus support the result in Theorem Furthermore, can observe that large perturbations may lead to more oscillations during convergence processes, which turn slows down the rate of convergence. We present more experiments in Appendix G

---

01117114
01 01
011870
153
103
1200
2500
3000
283
Figure 4: Values of A, for extra- extra-gradient with A + BL.,, P 1,2, (left), and A₂ + BrA, = 4,5, (right).
Discussion
In this paper, we study the last-iterate behavior of extra-gradient, optimistic gradient descent ascent, and negative momentum method in two types of time-varying games periodic game and convergent perturbed game. In the case periodic game, we prove that extra-gradin sarrd-graiient will converge to a Nash equilibrium while other two methods diverge. To the best of our knowledge, this is the first result that provides a clear separation between the behavior of extra-gradien methods and optimistic gradient descent ascent. In the of convergent perturbed game, prove all three learning dynamics converge to Nash equilibrium under the BAP assumption, which commonly used in the literature dynamical systems.
Our results leave many interesting open questions. Firstly, is the BAP assumption necessary for en- suring convergence in optimistic gradient descent ascent and negative momentum method? Secondly, the bound of convergence rate in Theorem 3.3 may rather slight as we shown in experiments section. Obtaining a tighter bound on the convergence rate is an important future research problem. Thirdly, can the results here be generalized to other settings, such as constrained zero-sum game?
A Acknowledgement
Yi Feng is supported by the Fundamental Research Funds for the Central Universities. Ioannis Panageas wants to thank startup grant. Xiao Wang acknowledges Grant 2021 10458 from SUFE and support from the Shanghai Research Center for Data Science and Decision Technology.
References
loannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On the convergence of no-regret learning dynamics in time-varying games. arXiv preprint arXiv:2301.1 /241, 2023.
Z Benzaid and DA Lutz. Asymptotic representation of solutions of perturbed systems of linear difference equations. Studies in Applied Mathematics, 195-21,, 1987.
David Blackwell. An analog of the minimax theorem for vector payoffs. In Pacific J. Math., pages 1-8, 1956.
George W Brown. Iterative solution of games by fictitious play, Act. Anal. Prod Allocation, 13(1): 374, 1951.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. In NeurIPS, 2022.
Adrian Rivera Cardoso, Jacob D. Abernethy, He Wang, and Huan Xu. Competing against nash equilibria in adversarially changing zero-sum games. In Proceedings of the 36th International Conference on Machine Learning. ICML 2019, volume 97 of Proceedings of Machine Learning Research, pages 921-930. PMLR. 2019.
Fritz Colonius and Wolfgang Kliemann. Dynamical systems and linear algebra, volume 158. American Mathematical Society, 2014.
10

---

Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. Advances in neural information processing systems, 31, 2018.
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego California, USA, volume 124 of LIPlcs, pages 27:1-27:18. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2019.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with Optimism. In Proceedings of ICLR, 2018.
Benoit Duvocelle, Panayotis Mertikopoulos, Mathias Staudigl, and Dries Vermeulen. Multiagent online learning in time-varying games. Mathematics of Operations Research, 2022.
S Elaydi and Györi. Asymptotic theory for delay differene equations. Journal of Difference Equations and Applications, 1(2):99-116, 1995.
Saber Elaydi, Satoru Murakami, and Etsuyo Kamiyama. Asymptotic equivalence for difference equations with infinite delay. Journal of Difference Equations and Applications, 5(1):1-23, 1999.
Tanner Fiez, Ryann Sim, Stratis Skoulakis, Georgios Piliouras, and Lillian Ratliff. Online learning in periodic zero-sum games. Advances in Neural Information Processing Systems, 34, 2021.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Simon Lacoste-Julien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1802-1811. PMLR, 2019.
Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: O(1KK last-iterate convergence for monotone variational inequalities and connections with cocoercivity. In Gustau Camps Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 366-402. PMLR, 2022a.
Eduard Gorbunov, Adrien Taylor, and Gauthier Gidel. Last-iterate convergence of optimistic gradient method for monotone variational incqualities. In NeurlPS, 2022b.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756. 1976.
Tengyuan Liang and James Stokes. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. AISTATS, 2019a.
Tengyuan Liang and James Stokes. Interaction matters: A note non-asymptotic local convergence of generative adversarial networks. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 907-915. PMLR, 2019b.
Tung Mai, Milena Mihail, Ioannis Panageas, Will Ratcliff, Vijay V. Vazirani, and Peter Yunker. Cycles in zero-sum differential games and biological diversity. In Éva Tardos. Edith Elkind, and Rakesh Vohra, editors, Proceedings of the 2018 ACM Conference on Economics and Computation. Ithaca, NY, USA, June 18-22, 2018, pages 339-350. ACM, 2018
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Renato DC Monteiro and Benar Fux Svaiter. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM Journal on Optimization, 20(6): 2010.
Arkadi Nemirovski. Prox-method with rate of convergence (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-coneave saddle point problems. SIAM Journal on Optimization, 22:22222,,1, 2004.
11

---

Yurii Nesterov. Smooth minimization of non-smooth functions. Math. Program., 103(1):127-152, 2005.
Mihály Pituk. More on poincaré's and perron's theorems for difference equations. The Journal of Difference Equations and Applications, 8(3):201-216, 2002.
Leonid Denisovich 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-800 848, 1980.
Abhishek Roy. Yifang Chen, Krishnakumar Balasubramanian, and Prasant Mohapatra. Online and bandit algorithms for nonstationary stochastic saddle-point optimization. CoRR, abs/1912.01698. 2019.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning games. In Corinna Cortes, Neil Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 2989-2997, 2015.
Chen- Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate conver- gence constrained saddle-poin optimization. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
Guodong Zhang and Yuanhao Wang. On the suboptimality of negative momentum for minimax optimization. In International Conference on Artificial Intelligence and Statistics, pages 2098-2106. PMLR, 2021.
Guojun Zhang and Yaoliang Yu. Convergence of gradient methods on bilinear zero-sum games, In International Conference Learning Representutions, 2020.
Mengxiao Zhang. Peng Zhao, Haipeng Luo, and Zhi-Hua Zhou. No-regret learning in time-varying zero-sum games. In International Conference on Machine Learning, ICML 2022, volume 162 of Proceedings of Machine Learning Research, pages
PMLR, 2022.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Tom Fawcett and Nina Mishra, editors, Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA, pages 928-936. AAAI Press, 2003.
12


Reviews:
[{"review_id": "UlVGLAJj3l", "reviewer": "Reviewer_abUR", "summary": "This work investigates the problem of last-iterate convergence in time-varying zero-sum games. Specifically, the authors study the last-iterate convergence of three kinds of algorithms (OGDA, EG, and negative momentum method) considering two kinds of time-varying games with specific structures, i.e., periodic games and convergent perturbed games. The authors obtained a convergence rate of EG in periodic games while providing a counterexample showing that OGDA and negative momentum method will diverge in this kind of game. In convergent perturbed games, the authors showed that all three kinds of algorithm will converge with a rate dependent on the perturbation $B_t$. Finally, experiments validate the statements proposed by the authors.", "questions": "I only have a major question on Theorem 3.1. What is the range of $t$? If $t$ is only chosen in $[1,T]$, choosing $t=T$ yields a convergence rate of $O(\\lambda_* \\text{poly}(T))$, which can be seen as a constant in terms of $T$. As mentioned in the 'Weaknesses' part, a bound linear in $T$ is pretty bad in the standard online learning convention. Theorem 3.1 exhibits an exponential rate only when $t$ can be significantly larger than the period length. Can the authors give some further explanations on this point?\n\nIn the end, I am very curious about whether the method in this paper, which models the learning algorithms as dynamical systems, can be applied to the constrained case, where the projection operations may bring some unique challenges to the modeling issue. Can the authors give some further explanations on this point?", "limitations": "Please mainly refer to the 'Weaknesses' part.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "In general, I think there is no last-iterate convergence rate in time-varying games due to the changing nature of the games. However, with specific problem structures, I believe that last-iterate convergence results can be established, and this work provides a piece of clear evidence. Overall, although the solutions are relatively simple by modeling the learning algorithms as dynamical systems and leveraging some existing results in the control theory, I am satisfied with the motivation and the final results of this work.", "weaknesses": "There are no significant weaknesses that affect my rating of the whole paper. In the following, I only list some minor issues.\n\n1. The notion of $T$ in periodic games. The notion of $T$ is commonly used to refer to the total number of rounds in online learning. In this work, the authors use $T$ to represent the number of rounds inside each period, which may lead to unnecessary understandings. I suggest the authors could choose a different notion to denote the period length.\n2. The notion of $\\text{ker}(\\cdot)$. This notion, which appears in Line 98 for the first time, seems not to be defined or given a clear description before.\n3. In Line 120, the authors mention that 'Recently, there are also works analyzing the regret behaviors of OGDA under a time-varying setting [1]'. The reference to [1] is not accurate enough. The work of [33], which is published at ICML2022, firstly gives a comprehensive study of the optimistic methods in time-varying zero-sum games by optimizing multiple performance measures simultaneously. I suggest the authors could refer to [33] in the aforementioned statement to make the credits more accurate.\n4. The negative momentum method requires the $x$-player to evolve to the next round first to give its gradient $A_{t+1} x_{t+1}$ to the $y$-player. In some cases where the learning procedure is strictly in an online style, this algorithm is NOT applicable since both players must act first to make the game evolve. I suggest the authors could give a discussion on this point in the revised version.\n\nTypos:\n1. Line 89: 'Section 4' not 'section 4'.\n2. Line 188: 'Section 3.3' not 'Section3.3'.\n3. The reference to theorems are not unified, e.g., in Line 237, 'theorem 3.2', and in Line 255, 'Theorem (3.1)'.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading, supportive comments, and helpful suggestions in improving the paper. We will clarify the issues in revision. Please see our itemized responses below:\n\nQuestions part：\n\n1. What is the range of $t$ in Theorem 3.1 ? \n    \nHere $t$ denotes the number of rounds that players have played in the game, thus $t$ takes value in range $[0,+\\infty)$ and $T$ denote the length of the period, which can be thought as a constant for a given periodic game. In Theorem 3.1 we provide a $\\mathcal{O}( (\\lambda_*)^{t/T} \\cdot \\text{Poly}(t) )$ with $ \\lambda_* <1$ bound on the distance between the current strategy and equilibrium. Therefore, when two players use extra-gradient, both players' current strategies will converge to equilibrium with an exponential rate.\n****\n2. Whether the method in this paper, which models the learning algorithms as dynamical systems, can be applied to the constrained case ?\n\nLearning algorithms in which there are constraints (like simplex constraints in games) can be analyzed using techniques from dynamical systems (e.g., see Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization, Daskalakis et al). As long as the NE is in the interior of the constrained set, the same techniques as used in this paper are applicable. The main challenge occurs when the NE is on the boundary of the constrained set. Our techniques can be applied in the constrained case as long as the constrained set can be expressed as a polytope (linear equalities and inequalities). In the more general case in which the set is an arbitrary convex set, more involved techniques are needed and further assumptions (assumptions on the curvature of the constrained set, see for example analysis of manifold gradient descent in First-order Methods Almost Always Avoid Saddle Points Lee et al.). This is an interesting open question for future investigation, though we believe similar results will occur. There are several techniques from differential geometry that deal with constraints (see for example analysis of manifold gradient descent in First-order Methods Almost Always Avoid Saddle Points Lee et al. which expresses manifold gradient descent as a dynamical system). As long as the constrained set is a smooth compact submanifold, one can use the projection operator and Riemannian gradient to express the learning dynamics as a dynamical system. Our techniques can deal with polytope constraints, it is very interesting future question to generalize these results to more general constrained convex sets.\n****\nWeaknesses part：\n\nThank you for your helpful comments.\n\n4. Notion of $T$\n\nIn the new version of the paper we will use $\\mathcal {T}$ to represent the length of period in a periodic game.\n****\n5. Definition of $\\ker(\\cdot)$\n\nWe will add a formal definition of $\\ker(\\cdot)$ in line 98 in the paper. Here $\\ker(A) = \\\\{ x \\in \\mathbb{R}^m | Ax = 0  \\\\}$. \n****\n6. Inaccurate reference\n\nThank you for your pointing out this issue. We apologize for our inattention. In the new version we will refer [33] in line 120 to ensure more accurate credits.\n****\n7. Question about $A_{t+1}x_{t+1}$ in negative momentum method.\n\nHere we are using the $\\textbf{alternating}$ negative momentum method studied in (Gidel et al. Negative Momentum for Improved Game Dynamics) instead of the usual $\\textbf{simultaneous}$ setting. In the alternating setting, at  round $t$, the $y$-player first chooses his strategy $y_t$ based on the payoff caused by $A^{\\top}\\_{t-1}x\\_{t-1}$, and then the $x$-player choose her strategy $x_t$ based on the payoff caused by $A_{t}y_{t}$. In the stationary game setting, (Gidel et al. ) proved that the simultaneous negative momentum method will lead to an exponential divergence rate, while the alternating negative momentum method will converge. Since our focus in this paper is on determining which algorithm will converge in a time-varying game, we only consider the alternating setting.\n\n****\nTypos will be corrected in the new version of the paper, thank you for pointing them out.\n"}, {"review_id": "u0cVGKLnuD", "reviewer": "Reviewer_oHHw", "summary": "Over the last few years an extensive literature has studied the last iterate convergence of learning dynamics in zero-sum games, particularly those using optimism and extra-gradient approaches.  This paper extends that approach to two classes of unconstrained non-stationary game (periodic and decaying noise) and shows a difference in behavior between the two classes.", "questions": "Please respond regarding the two main weaknesses.", "limitations": "The conditions to which the results apply are clearly explained.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem studied is natural and clearly explained with strong results, including the interesting split in behavior (Theorems 3.1 and 3.2)\n\nThe approach uses several technical innovations derived from the literature on non-autonomous linear difference systems.\n", "weaknesses": "The particular classes of games studied could be better motivated.  Is there a reason to focus on these other than technical convenience?  Do they have important applications?  What more general but harder class is this a step towards?  The conclusion mentions constrained games as future work, nothing about other interesting directions fof future work.  Are there other theorems from non-autonomous linear difference systems that seem promising?\n\nThere is a gap left by Theorems 3.3 and 3.4 about whether the other two dynamics converge under the weaker conditions of Theorem 3.4.  Figure 4 gives an experiment on this setting, so it seems like a missed opportunity to not at least show what the other dynamics do on this example.  \n\nMinor comments:\n- There is some inconsistency in the way “equilibrium” is used.  It is defined on line 98 as what I would instead have called the set of equilibria.  However, in other places, like line 252 it seems to be used to refer to a single element of this set.  Depending on how this is resolved, some care may be needed in places about whether something is “the” or “a” equilibrium (e.g. on line 216).\n- Line 178 and 181 the formulas use n but the limits are taken over t\n- Line 216 the “common Nash equilibrium” is not defined, nor is there an explanation of why it mush exist (presumably because 0 is always an equilibrium?)\n- Line 305 group[s]\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support, interest to current work, and inspiring question for future work. Please see our itemized responses below:\n\n1. Is there a reason to focus on these classes of games other than technical convenience? Do they have important applications? What more general but harder class is this a step towards? \n\nFor the first and second question, please refer to the second part in global rebuttal for a detailed explanation.\n\nFor the third question, we believe that the class of convergent perturbed games with a convergence rate slower than $\\frac{1}{t}$ is more challenging compared to our current setting. As discussed in Section 5, the dynamical behaviors of optimistic gradient and negative momentum methods under this setting remain unclear. Based on the numerical results presented in the experiments in global rebuttal, we believe that the dynamical behaviors of optimistic gradient and negative momentum method under this setting are much more complex than those in the BAP setting, as stated in Theorem 3.3. \n\n****\n2. The conclusion mentions constrained games as future work, nothing about other interesting directions of future work. Are there other theorems from non-autonomous linear difference systems that seem promising?\n\nStability theory of non-autonomous dynamical system from learning algorithms has been studied recent years, e.g. \"AdaGrad Avoid saddle points, Antonakopoulos et al.\" and \"First-order method almost always avoid saddle points:the case of vanishing step-size, Panageas et al.\". Both works investigate non-autonomous dynamical systems from non-convex minimization problems. Their method belongs to a general theoretical framework called Lypunov-Perron method and stable manifold theorem, which enables one to prove certain dynamical systems do not converge to unstable fixed points. One promising future direction is to fit such method into min-max optimization algorithms so that we can have a better understanding on the asymptotic behavior of different algorithms in time-varying settings. One might expect some result similar to \"The limit points of (optimistic) gradient descent in Min-Max optimization, Daskalakis et al.\", but in a time-varying setting. Since the Lyapunov-Perron method depends on spectral analysis of update rules (spectral analysis is a main technique in all  aforementioned papers), it is interesting to explore if these techniques can be combined with current paper. \n ****\n3. Gap between Theorem 3.3 and Theorem 3.4.\n\nPlease refer to the first part of the global rebuttal for additional numerical results and explanations regarding this question. \n\n****\nThank you for the other comments on writing, the typos will be fixed in the new version of the paper.\n"}, {"review_id": "RiPDVUZdWf", "reviewer": "Reviewer_qpgT", "summary": "This paper studies the problem of learning Nash equilibria in two-player zero-sum bilinear games where the payoff matrix varies with time.\nWhen the payoff matrix is a periodic function, it is proven that the extra gradient algorithm converges to a Nash equilibrium, whereas the optimistic gradient descent ascent and negative momentum method could diverge from the equilibrium.\nFurthermore, it is shown that all the above three algorithms converge to the equilibrium for the convergent perturbed game.", "questions": "* (Section 2.1) What is the definition of $\\mathrm{ker}(\\cdot)$?\n* (Section 3.2) What are the key differences between the extra gradient algorithm and the other two algorithms?\n* (Section 3.2) For the periodic games with $\\lambda_{\\ast}=0$, would similar convergence/divergence results hold to Theorem 3.1 and 3.2?\n* (Section 4) Do the optimistic gradient descent ascent algorithm and negative momentum method empirically converge in the same instance in the experiments for Figure 4?", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is well-written and studies an interesting problem. \n* The author provided an instance of periodic zero-sum games where extra gradient algorithms and optimistic gradient descent ascent algorithms behave distinctly differently.\n* The analysis looks to be sound, and the experimental results seem to bare out the theory.", "weaknesses": "* Perhaps a short intuitive explanation of why extra gradient is better than optimistic gradient descent ascent would help readers understand the main results of this paper.\n* The titles and legends in Figures 1,2,3 and 4 should be enlarged.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your support, careful reading and helpful suggestions. Please see our itemized responses below:\n\n1. What is the definition of $\\ker(\\cdot)$ ？\n\nFor a payoff matrix $A \\in \\mathbb{R}^{n \\times m}$, $\\ker(A)$ is defined to be the set $\\\\{ x \\in \\mathbb{R}^m |\\ Ax = 0  \\\\}.$\n\n****\n\n2. What are the key differences between the extra gradient algorithm and the other two algorithms?\n\n*A quick answer: Only the iterative matrix of extra gradient is a normal matrix, while the other algorithms' iterative matrices are just diagonalizable but not normal.\n\n*A detailed answer: From the techniques we used to prove the separation between extra gradient and the other two methods, the key difference is that the iterative matrix of extra gradient algorithm is a normal matrix,  while the other two algorithms are not.  For example, in the period case, the advantages of normality are twofold : it helps to bound the modulus of eigenvalues of iterative matrix and makes the strategy components that do not correspond to equilibrium vanish over time. In the following, we provide further explanations. \n\nFirstly, let's denote the overall iterative matrix as $\\prod_{t=1}^T \\mathcal{A}\\_t$, which is product of iterative matrix for a period of $T$. For matrix $\\prod_{t=1}^T \\mathcal{A}_t$, the maximum modulus of eigenvalues is no more than 1 due to the normality, thus during the iterative process, the strategy can't diverge. \n\nSecondly,  we introduce a decomposition of the two players' current strategy $X_t$ into two parts. The first component $X_t^1$ represents eigenvector corresponding to eigenvalue $1$ of the iterative matrix, which corresponds to an equilibrium of the game. The second component $X_t^2$ consists of linear combinations of other eigenvectors. Due to the normality property of the iterative matrix of extra gradient, $X_t^1$ remains unchanged over time and modulus of $X_t^2$ approaches zero as time goes to infinity. (See Corollary B.4 and proof of Theorem 1 in Appendix B).  This ensures convergence of extra gradient algorithm towards Nash Equilibrium point. For the other two algorithms, without the normality property, for the overall iterative matrix, as we shown in the example (See Theorem 3.2 and its proof in Appendix C), its maximum modulus of eigenvalues can be larger than 1. Then, we can choose the initial point which makes the strategy point diverge from Nash Equilibrium point. The normality of iterative matrix of extra gradient also plays important role in convergent perturbed game. \n\n****\n3. For the periodic games with $\\lambda_* = 0$, would similar convergence or divergence results hold to Theorem 3.1 and 3.2?\n\nYes, the result still hold, since in this case from the general result in linear algebra, the iterate matrix $\\prod^T_{t=1} \\mathcal{A}_t$ will be a nilpotent matrix, which means after finite time iteration, the strategy $(x_t,y_t)$ must come to be the trivial equilibrium $(0,0)$.\n\nThe divergence result in Theorem 3.2 depend on the the fact that for the special periodic game defined by the payoff matrix\n\\begin{align}\n A_t=\n\\begin{cases}\n\\left[1,-1\\right], & t \\textnormal{\\ \\ is \\ odd} \\\\\\\\\n\\left[-1,1\\right], & t\\textnormal{\\ \\ is \\ even}\n\\end{cases},\n\\end{align}\nthe iterate matrix of optimistic gradient and negative momentum method always have a eigenvalue with modulus larger than $1$, combine with Floquet theorem (proposition 2.4, line 166), this is enough to show the exponential divergence result, and whether $\\lambda_* = 0$ is irrelevant for Theorem 3.2. \n****\n4. Do the optimistic gradient descent ascent algorithm and negative momentum method empirically converge in the same instance in the experiments for Figure 4?\n\nYes, both the optimistic gradient descent ascent algorithm and the negative momentum method also converge in the same instance in the experiments for Figure 4. However, we also find examples where these two methods do not empirically converge due to violations of the BAP assumption, please refer to part 1 in the global rebuttal for detailed explanation. \n****\nThank you for your comments on the titles and legends in the figures, we will address these issues in the new version of the paper."}, {"review_id": "A0wukfqbiU", "reviewer": "Reviewer_PugT", "summary": "This paper studies the last-iterate behavior of three different algorithms on two types of time-varying zero-sum games: periodic and convergent perturbed games. For periodic games, the authors prove that EG will converge while OGDA and the negative momentum method could diverge. For convergent perturbed games, all these algorithms converge as long as the error term decays sufficiently fast.", "questions": "1. Could the authors provide some examples of periodic and convergent perturbed games?\n\n2. In line 225, the authors say that the key point on the convergence of EG for periodic games is that the iterative matrix is a normal matrix. Could the authors give a more intuitive explanation? Moreover, the update rule of EG only depends on the current point $(x_t, y_t)$, while OGDA and negative momentum method also need to employ the gradient information at the last point $(x_{t-1}, y_{t-1})$. Is this a reason for the different behavior of these methods?\n\n3. For the experiments on Theorem 3.4, the authors only plot the convergent curve of EG. I wonder about the behabior of the other two methods in this case.\n", "limitations": "See Questions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-organized and easy to follow.\n2. The different behavior between EG and OGDA seems novel in the literature. ", "weaknesses": "1. Some results lack an intuitive explanation.\n2. Some figures are not well-plotted. Maybe a log-log graph is more proper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your supportive comments, suggestions and questions on intuitive explanation and experiments. Please see our itemized responses below:\n\n1. Could the authors provide some examples of periodic and convergent perturbed games?\n\nPlease refer to part 2 of the global rebuttal for an explanations of this question.\n****\n    \n2. Intuitive explanation for why EG's iterative matrix is a normal matrix.\n    \nThank you for asking this important question. \"EG's iterative matrix is normal\" is an observation that is also surprising to authors. Our intuition actually came from experiments. First of all, we expect that all iterative matrices to be diagonalizable. However, we observe that the dynamics never diverges, which is a much stronger phenomenon than being diagonalizable. Since normal matrices has eigenvalues with magnitudes at most 1, and this means their dynamics never diverge, which agreed with all the experiments we had run. Therefore, we turn our attention from diagonalizable to normal and eventually discover only EG is normal, and it became the key property for periodic settings.\n\nFor the differences between EG and optimistic/momentum methods, other than their disparities in eigenvalues/eigenvectors. The suggestion that the differences in dependence between the update rules and past payoffs is an interesting viewpoint, we will consider this to see whether it can give an intuitive explanation. We also verify that the iterative matrix of gradient descent algorithm, which also uses only one step information is normal matrix.\n****\n3. Behaviors of the other two methods in this case in the experiments on Theorem 3.4,\n\nThe other two methods also converge under the conditions of experiments on Theorem 3.4. However, we have also found a numerical example that does not satisfy the BAP assumption, and it seems that the optimistic gradient/momentum method does not converge in this example. Please refer to the first part of global rebuttal for additional experiments and explanations of this question.\n\n    "}, {"review_id": "s3fGH3QkkT", "reviewer": "Reviewer_tqyN", "summary": "This paper considers the problem of unconstrained min-max optimization with bilinear structure. Specifically, this paper considers the setting where the payoff matrix $A_t$ changes over time. The two changing dynamics of $A_t$ considered in this paper is the periodic game and the converging perturbed game. Three strategy dynamics are cosidered in this paper, which is OGDA, extra gradient (EG) and Negative momentum method. In this paper, the authors show that in the period game case, under certain initialization, OGDA provably diverges no matter what learning rate is chosen while EG with a certain choice of learning rate converges to the common NE with exponential rate. In the convergent perturbed game case, all the three types of algorithms converge with a proper choice of learning rate. The analysis is basd on analyzing the eigenvalues of the linear operator in the recursive form of the strategies. Empirical results further verifies their theoretical results.", "questions": "- As mentioned in weakness, whether the current result can be extended to a generalized linear case with $f_t(x,y)=x^\\top A_ty+b_t^\\top x+c_t^\\top y$?\n- Is there a specific reason considering the periodic games and the convergent perturbed games? Can the results generalize to some other type of time-varying games with common NE?", "limitations": "See weakness and questions for details.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The min-max optimization with time-varying functions is an important question and has wide real-world applications.\n- This paper first considers the last-iterate convergence performance for the unconstrained bilinear min-max problem and show that under two different changing dynamics of the bilinear matrix, OGDA performs provably differently and EG always converges. Specifically, the diverging results for OGDA looks intereting to me.\n- I did not check all the proof details but the general idea of the proof makes sense to me.", "weaknesses": "- One issue is whether the optimization of unconstrained min-max optimization with bilinear structure is interesting. Specifically, even when the game is changing over time, one trivial Nash Equilibrium is $(0,0)$. Therefore, all the three algorithms initialized with $(0,0)$ will converge, though the dynamic of these three algorithms may still be interesting with different initializations. Extending the current framework to a slightly general case $x^\\top A_ty+b_t^\\top x+c_t^\\top y$ or an even more general convex-concave function $f(x,y)$ will strengthen the results a lot.\n- As the authors mentioned, the constrained version of the min-max optimization problem may be more interesting and the dynamic of the strategy can not be expressed in a clean linear recurrsive form as shown in the unconstrained bilinear case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your support and interests to our results, especially we thank you for proposing important and challenging question to strengthen current results. Please see our itemized responses below:\n\n1. Whether the current result can be extended to a generalized linear case with $f_t(x,y) = x^{\\top}A_ty + b^{\\top}_tx + c^{\\top}_ty $ ?\n\nThank you for asking this important question. Generalizing the current results to other settings, such as convex-concave payoff, is definitely an important question for future research. Our results can be extended to the above general linear case, as the linear payoff can be reduced to bilinear case with translation of the strategy variables. Similar technologies were also introduced in (Zhang et al. convergence of gradient methods on bilinear zero-sum games) in the stationary game setting. In the following we provide a more detailed explanation.  For convenience we formulate the payoff function as \n \\begin{align}%\\label{gene}\nf_t(x,y) = x^{\\top}A\\_ty + x^{\\top}b\\_t + c^{\\top}\\_ty. \\\\ \\\\ \\\\ (1)\n\\end{align}\nBy first order stationary condition, if a point $(x^*,y^*)$ is a equilibrium of $f_t(x,y)$, then \n\\begin{align}%\\label{equi}\n        A\\_ty^* = - b\\_t, \\  A^{\\top}\\_t x^* = -c\\_t.\\\\ \\\\ \\\\ (2)\n\\end{align}\n\nFor a periodic game with payoff matrix $\\\\{A\\_t\\\\}^{\\infty}\\_{t=1}$, payoff vectors $\\\\{b\\_t\\\\}^{\\infty}\\_{t=1}, \\\\{c\\_t\\\\}^{\\infty}\\_{t=1}$ and period $\\mathcal{T}$, if a strategy point $(x^*,y^*)$ is a common equilibrium, then it satisfies (2) for any $t \\in [\\mathcal{T}]$. We assume such common equilibrium exists, thus there exist $(b,c)$ such that\n    \\begin{align}%\\label{111}\n        A\\_t b = - b\\_t, \\  A^{\\top}\\_t c = -c\\_t,\\  \\forall t \\in [\\mathcal{T}]. \\\\ \\\\ \\\\ (3)\n    \\end{align}\n    Now we denote $x' = x - c,\\ y' = y - b$, then it can be verified that\n    \\begin{align}\n        \\min\\_x \\max\\_y f\\_t(x,y) = \\min\\_{x'} \\max_{y'} (x')^{\\top}A\\_ty'+c^{\\top}A\\_tb.  \n    \\end{align}\nThus every periodic game with general linear payoff is an equivalent to a bilinear periodic game considered in the current paper, thus the result in Theorem 3.1. also holds in general linear payoff case. However, according to (3), it may be difficult for a periodic game with a general linear payoff to have a common equilibrium. This is different from the bilinear game where $(0,0)$ is always a common equilibrium.\n\nFor convergent perturbed game, it can be demonstrated that Theorem 3.3. still holds true with a similar translation of the variables and techniques employed in the paper.\n\n****  \n2. Is there a specific reason considering the periodic games and the convergent perturbed games? Can the results generalize to some other type of time-varying games with common NE?\n\nFor the first question, please refer to the second part of the global rebuttal.\n\nFor the second question, generalizing the current results to other type of time-varying games with common NE is a very interesting question. It is not clear to us if our results would carry over for more general class of games with common NE and if our techniques will be applicable. An assumption that probably is needed if one wants to show convergence (e.g., of extra gradient), is that the difference $||A_{t+1}-A_t||_2$ is not too large for all $t$. We would like to mention that general theory of non-autonomous linear differential/difference equation is not as simple as autonomous ones, it is still a quite open-ended area by itself (see Fritz Colonius and Wolfgang Kliemann. Dynamical systems and linear algebra, volume 158.344 American Mathematical Society, 2014.). Thus we believe that any interesting generalization will depends on some specific observations case by case, which means there are many potential problems to be answered.\n    \n"}]

Author rebuttal:
We appreciate the efforts of all reviewers, thanks for your constructive questions and critical suggestions! The PDF file contains additional experimental results as requested by reviewers. If you have questions about the experimental parts of the paper, please refer to this file.  In the following, we address two questions that have been raised by several reviewers.
****
1. Gap between Theorem 3.3 and Theorem 3.4., and behaviors of optimistic gradient/momentum method in the instance in Figure 4 of the paper.

We provide additional experiments to demonstrate the behaviors of the optimistic gradient and negative momentum methods in convergent perturbed games that do not satisfy the BAP assumption. The numerical results reveal cases where optimistic gradient/momentum method converge ( Figure 1 in PDF records experimental results) and cases where they do not converge (Figure 2,3 in PDF records experimental results).

In the same setting as the experiments on Theorem 3.4 , we find that both optimistic gradient descent ascent and negative momentum method converge as shown in Figure 1 of the PDF records experimental results.

However, there are other cases in which these two algorithms do not converge. In Figure 2 and 3, we present one such example. Here the payoff matrix is chosen as $A = [ [1,0],[0,0]], B = [[0,8],[0,0]]$ and 

\begin{align}
 A_t=
\begin{cases}
A, & t \textnormal{\ \ is \ odd} \\\\
A + (1/t^{0.1}) * B , & t\textnormal{\ \ is \ even}
\end{cases}.
\end{align}

 In Figure 2, the numerical results show when using a step size of $0.015$, optimistic gradient and negative momentum algorithms will diverge, but extra gradient will converge. In Figure 3, by reducing the step size to very small numbers ($0.0003$ or $0.0001$ in this case),  optimistic gradient and negative momentum algorithms do not seem to diverge but maintain a nonzero distance from the equilibrium points. Based on these numerical results, we believe that beyond the setting that satisfies the BAP assumption mentioned in line 256 of the paper, there exists a more complex relationship between the dynamical behaviors of optimistic gradient and negative momentum methods and their respective step sizes, which presents an interesting question for future exploration. 

****
2. Reasons to consider periodic/convergent perturbed game and examples of them.

We note that both of these game classes have been studied in previous literature as testing grounds of learning algorithms in online learning community ([11], [14]). However, our paper focuses on different viewpoints compared to the existing research, making it a natural extension of this line of research. Moreover, periodic game and convergent perturbed game are natural generalizations of the usual repeated game formulations. When the period $\mathcal{T} = 1$, the periodic game becomes a repeated game, and when the perturbation $B_t = 0$, then convergent perturbed game becomes a repeated game.

The periodic games model competitive settings where the exogenous environment varies periodically. This naturally occurs in competitions where day-to-day trends, and seasonality can affect the game between players. For example, consider a competition between two species whose life states are affected by seasonal changes or sellers in a fish market, where the value of fish depends on their freshness, thus exhibiting daily period behavior. Periodic zero-sum games can also fit into the frameworks of multi-agent contextual games (Sessa et al. Contextual games: Multi-agent learning with side information, NIPS 2020). In a multi-agent contextual game, the environment selects a context from a set before each round of play and this selection determines the specific game that will be played. Periodic zero-sum games can be viewed as a multi-agent contextual game where the environment periodically chooses contexts from the available set, creating zero-sum games with a common equilibrium. The convergent perturbed game naturally models games with noise that decays over time. The noise can arise from players' own beliefs, such as in an auction where a certain type of goods is being auctioned off day after day to  buyers, and the buyers' assessment of the value of this good will eventually converge to a fixed value as their experience growth. The noise can also model external effects when players repeatedly play the game, such as interference factors in the feedback process. 

****
We are looking forward to further discussion in the next stage of review process. We thank your again for all your hard work! 


Meta-review: This paper shows a very interesting and somewhat surprising result: that the extragradient method may have stronger convergence properties in certain zero-sum games than optimistic gradient descent-ascent. This is surprising because most results are essentially the same for both algorithms, and people even sometimes refer to OGDA as a variant of "single-call extragradient."

At the same time, a reviewer pointed out a somewhat significant weakness: that bilinear games are somewhat trivial, in that (0,0) is always an equilibrium. Despite the weakness, all the reviewers are in favor of acceptance. Drawing an analogy to the trajectory of work on last-iterate convergence in zero-sum games, one might also expect that follow-up work will be able to move to more realistic and less trivial games.
Decision: Accept (poster)