††footnotetext: Authors are listed according to the alphabetical order.

# On the Last-iterate Convergence in Time-varying Zero-sum Games: Extra
Gradient Succeeds where Optimism Fails

Yi Feng
SUFE
<EMAIL_ADDRESS>
&Hu Fu
SUFE
<EMAIL_ADDRESS>
Qun Hu
SUFE
<EMAIL_ADDRESS>
&Ping Li
SUFE
<EMAIL_ADDRESS>
&Ioannis Panageas
University of California, Irvine
<EMAIL_ADDRESS>
&Bo Peng
SUFE
<EMAIL_ADDRESS>
&Xiao Wang
SUFE
<EMAIL_ADDRESS>
Shanghai University of Finance and Economics

###### 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$.

##  1 Introduction

A central problem in game theory and min-max optimization is to come up with a
pair of vectors $(x,y)$ that solves

$\displaystyle\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}x^{\top}Ay,$ (1)

where $\mathcal{X}\subset\mathbb{R}^{n}$ and
$\mathcal{Y}\subset\mathbb{R}^{m}$ are convex sets, and $A$ is a $n\times m$
payoff matrix. The above captures two-player zero-sum games in which
$x^{\top}Ay$ is interpreted as the payment of the “min player” $x$ to the “max
player” $y$. If $\mathcal{X}=\mathbb{R}^{n}$ and $\mathcal{Y}=\mathbb{R}^{m}$
the setting is called _unconstrained_ , otherwise it is _constrained_. Soon
after the minimax theorem of Von Neumann was established (for compact
$\mathcal{X},\mathcal{Y}$), learning dynamics such as fictitious play (Brown
(1951)) 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 multiplicative-weights-update method, online
gradient descent/ascent and their optimistic variants and extra-gradient
methods.

#### Last Iterate Convergence.

There have been a vast literature on whether or not the aforementioned
dynamics converge in an average sense or exhibit last-iterate convergence when
applied to zero-sum games. Dating back to Nesterov (Nesterov (2005)), 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
(2019); Wei et al. (2021)), optimistic gradient descent ascent (OGDA)
(Daskalakis et al. (2018); Liang and Stokes (2019a)) (applied even to GANs)
for unconstrained zero-sum games, OGDA for constrained zero-sum games (Wei et
al. (2021); Cai et al. (2022); Gorbunov et al. (2022b)) 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 unrealistic, 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-varying games, where they aim at analyzing the duality gap
or dynamic regret (Zhang et al. (2022)) 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 to fill in this gap. We
aim at addressing the following question:

_Will learning algorithms such as optimistic gradient descent ascent or extra-
gradient 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_{t}$ depends on time $t$)

$\displaystyle\min_{x\in{\mathbb{R}}^{n}}\max_{y\in{\mathbb{R}}^{m}}x^{\top}A_{t}y,$
(Time-varying zero sum game)

in which the payoff matrix $A_{t}$ varies with time in the following two ways:

  * •

Periodic games: $A_{t}$ is a periodic function with period $T$, i.e.,
$A_{t+T}=A_{t}$.

  * •

Convergent perturbed games: $A_{t}=A+B_{t}$, $\lim_{t\to\infty}B_{t}=0$.

In a repeated time-varying zero-sum game, players choose their learning
algorithms and repeatedly play the zero-sum game. In the $t$-th round, when
the players use strategy $(x_{t},y_{t})$, they receive their payoff
$-A_{t}^{\top}x_{t}$ and $A_{t}y_{t}$.

In this paper we show the following results:

  * •

For periodic games: We prove that when two players use extra-gradient, their
strategies will converge to the common Nash equilibrium of the games within a
period with an exponential rate, see Theorem 3.1 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 a clear
separation between the behavior of extra-gradient methods and optimistic
gradient descent ascent.

  * •

For convergent perturbed games: Assuming $\sum^{\infty}_{t=1}\lVert
B_{t}\lVert_{2}$ is bounded, we prove that the extra-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
$\\{B_{t}\\}_{t}$ and singular values of $A$, see Theorem 3.3. Furthermore, we
prove that extra-gradient will asymptotically converge to equilibrium without
any additional assumptions on perturbations besides
$\lim_{t\to\infty}B_{t}=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 et al.
(2022)). Most of the literature has been focused on proving either
recurrence/oscillating behavior of learning dynamics in time-varying periodic
games (Mai et al. (2018); Fiez et al. (2021) ) and references therein or
performing regret analysis (Roy et al. (2019); Cardoso et al. (2019); Zhang et
al. (2022)). In particular, the latter work extends results on RVU (Syrgkanis
et al. (2015)) bounds to argue about dynamic regret (Zinkevich (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 a certain matrix
has no eigenvalues 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 to the time-varying games
where the corresponding difference systems are non-autonomous. In particular,
the dynamical behavior of a non-autonomous system is not determined by the
eigenvalues of a single matrix. In fact, it is difficult to establish
convergence/divergence 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 2, we present the necessary background for this work. The main
results are stated in Section 3. In Section 4, we present numerical
experiments and in Section 5, we conclude with a 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 ${\mathcal{N}}=\\{1,2\\}$, and losses of both players are
determined via payoff matrix $A\in{\mathbb{R}}^{n\times m}$. Given that player
$1$ selects strategy $x\in{\mathbb{R}}^{n}$ and player $2$ selects strategy
$y\in{\mathbb{R}}^{m}$, player 1 receives loss $u_{1}(x,y)=\langle
x,Ay\rangle$, and player 2 receives loss $u_{2}(x,y)=-\langle
y,A^{\top}x\rangle$. Naturally, players want to minimize their loss resulting
the following min-max problem:

$\min_{x\in{\mathbb{R}}^{n}}\max_{y\in{\mathbb{R}}^{m}}x^{\top}Ay$ (Zero-Sum
Game)

Note that the set $\\{(x^{*},y^{*})|A^{\top}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$ is an infinite sequence of zero-sum bilinear
games $\\{A_{t}\\}^{\infty}_{t=0}\subset{\mathbb{R}}^{n\times m}$, and
$A_{t+T}=A_{t}$ for all $t\geq 0$.

Note that the periodic game defined here is the same as Definition 1 in (Fiez
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 $t$.

######  Definition 2.2 (Convergent perturbed games).

A convergent perturbed game is an infinite sequence of zero-sum bilinear games
$\\{A_{t}\\}^{\infty}_{t=0}\subset{\mathbb{R}}^{n\times m}$, and
$\lim_{t\to\infty}A_{t}=A$ for some $A\in{\mathbb{R}}^{n\times m}$.
Equivalently, write $A_{t}=A+B_{t}$, then $\lim_{t\to\infty}B_{t}=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 a time-independent payoff matrix,
as demonstrated in previous literature. However, here we state their forms
within a time-varying context.

Optimistic gradient descent-ascent. We study the optimistic descent ascent
method (OGDA) defined as follows:

$\displaystyle x_{t+1}=x_{t}-2\eta A_{t}y_{t}+\eta A_{t-1}y_{t-1},$ (OGDA)
$\displaystyle y_{t+1}=y_{t}+2\eta A^{\top}_{t}x_{t}-\eta
A^{\top}_{t-1}x_{t-1}.$

Optimistic gradient descent ascent method was proposed in (Popov (1980)), and
here we choose the same parameters as (Daskalakis et al. (2018)). The last
iterate convergence property of OGDA in unconstrained bilinear game with a
time-independent payoff was proved in (Daskalakis et al. (2018)). Recently,
there are also works analyzing the regret behaviors of OGDA under a time
varying setting (Zhang et al. (2022); Anagnostides et al. (2023)).

Extra gradient. We study the extra gradient descent ascent method (EG) defined
as follows:

$\displaystyle x_{t+\frac{1}{2}}=x_{t}-\gamma A_{t}y_{t},\ \
y_{t+\frac{1}{2}}=y_{t}+\gamma A_{t}^{\top}x_{t},$ (EG) $\displaystyle
x_{t+1}=x_{t}-\alpha A_{t}y_{t+\frac{1}{2}},\ \ y_{t+1}=y_{t}+\alpha
A_{t}^{\top}x_{t+\frac{1}{2}}.$

Note that the extra-gradient method first calculates an intermediate state
before proceeding to the next state. Extra-gradient was firstly proposed in
(Korpelevich (1976)) with the restriction that $\alpha=\gamma$. Here we choose
the parameters same as in (Liang and Stokes (2019a)), where the linear
convergence rate of extra-gradient in the bilinear zero-sum game with time-
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 non-convex-non-concave game was provided in
(Mertikopoulos et al. (2019)).

Negative momentum method. We study the alternating negative momentum method
(NM), defined as follows:

$\displaystyle x_{t+1}=x_{t}-\eta A_{t}y_{t}+\beta_{1}(x_{t}-x_{t-1}),$ (NM)
$\displaystyle y_{t+1}=y_{t}+\eta
A_{t+1}^{\top}x_{t+1}+\beta_{2}(y_{t}-y_{t-1}),$

where $\beta_{1},\beta_{2}\leq 0$ are the momentum parameters.

Applications of negative momentum method in game optimization was firstly
proposed in (Gidel et al. (2019)). Note that the algorithm has an alternating
implementation: the update rule of $y_{t+1}$ uses the payoff
$A_{t+1}^{\top}x_{t+1}$, 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 are crucial for convergence in bilinear zero-sum games with
time-independent payoff matrices. Analysis of the convergence rate of negative
momentum method in strongly-convex strongly-concave games was provided in
(Zhang and Wang (2021)).

###  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. In general,
the convergence behavior of non-autonomous difference systems is much more
complicated than that of autonomous ones (Colonius and Kliemann (2014)).

Linear difference system. Given a sequence of iterate matrices
$\\{\mathcal{A}_{t}\\}^{\infty}_{t=1}\subset{\mathbb{R}}^{n\times n}$ and
initial condition $X_{0}\in{\mathbb{R}}^{n}$, a linear difference system has
form

$\displaystyle X_{t+1}=\mathcal{A}_{t}X_{t}.$ (Linear difference system)

If $\mathcal{A}_{t}\equiv\mathcal{A}$ is a matrix independent of time, the
system is called an autonomous system, otherwise, it is called a non-
autonomous system. We care about the asymptotic behavior of $X_{t}$, that is,
what can we say about $X_{t}$ as $t\to\infty$.

######  Definition 2.3.

A point $X$ is called asymptotically stable under the linear difference system
if

$\displaystyle\exists\ \delta>0,\forall\ Y,\ s.t.\ \lVert
Y-X\lVert_{2}\leq\delta\Rightarrow\lim_{t\to\infty}\lVert(\prod^{\infty}_{t=1}\mathcal{A}_{t})Y-X\lVert_{2}=0.$

Moreover, $X$ is called exponentially asymptotically stable if the above limit
has an exponentially convergence rate, i.e., $\exists\ \alpha\in(0,1)$, such
that

$\displaystyle\lVert(\prod^{s}_{t=1}\mathcal{A}_{t})Y-X\lVert_{2}\leq\alpha^{s}\lVert
Y-X\lVert_{2}.$

It is well known that for autonomous linear systems, being asymptotically
stable is equivalent to 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. 111To gain intuition of the differences
between autonomous and non-autonomous system, consider the following simple
1-dimension example: $x_{t+1}=(1-\frac{1}{t+1})x_{t}$. $0$ is a stationary
point of this system, but every initial points converges to $0$ with a rate
${\mathcal{O}}(\frac{1}{t})$, thus $0$ is asymptotically stable but not
exponentially asymptotically stable .

Linear difference system has a formal solution
$X_{T+1}=\prod^{T}_{t=0}\mathcal{A}_{t}X_{0}.$ However, such a representation
does not yield much information about the asymptotic behavior of solution as
$t\to\infty$, except in the case of autonomous system. In this paper, we
mainly consider two classes of non-autonomous linear difference systems: if
the iterate matrix $\mathcal{A}_{t}$ is a periodic function of $t$, the system
is called a periodic system; and if $\mathcal{A}_{t}$ has a limit as $t$ tends
to infinity, the system is called a perturbed system.

Periodic linear system. If the iterate matrix $\mathcal{A}_{t}$ in a linear
difference system satisfies $\mathcal{A}_{t}=\mathcal{A}_{t+{\mathcal{T}}}$,
$\forall t\in{\mathbb{Z}}$, then the system is called a periodic linear
system. Denote
$\widetilde{\mathcal{A}}=\prod^{\mathcal{T}}_{j=1}\mathcal{A}_{{\mathcal{T}}-j}$.
For a $T$-periodic equation, the eigenvalues $\alpha\in{\mathbb{C}}$ of
$\widetilde{\mathcal{A}}$ is called the Floquet multipliers, and the Floquet
exponents are defined by
$\lambda_{j}=\frac{1}{{\mathcal{T}}}\ln(\lvert\alpha_{j}\lvert)$. The
following Floquet theorem characterizes the stability of a 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 to obtain explicit convergence criteria for specific equation. That is
because even if we know the modulus of the largest eigenvalue of each
$\mathcal{A}_{t}$, it is usually difficult to compute the the modulus of the
largest eigenvalue of each $\prod^{{\mathcal{T}}}_{t=0}\mathcal{A}_{t}$ due to
the complex behavior of eigenvalues under matrix multiplication.

Perturbed linear system. If the iterative matrix $\mathcal{A}_{t}$ in a linear
difference system satisfies $\mathcal{A}_{t}=\mathcal{A}+\mathcal{B}_{t}$ and
$\lim_{t\to\infty}\mathcal{B}_{t}=0$, then the system is called a perturbed
linear system. The convergence behavior of a perturbed linear system is not
clear in the literature. A general result in this direction is the following
Perron’s theorem:

######  Theorem 2.5 (Perron’s theorem, (Pituk (2002))).

If $X_{n}$ is a solution of a perturbed linear system, then either $X_{n}=0$
for all sufficient large $n$ or $\rho=\lim_{n\to\infty}\sqrt[n]{\lVert
X_{n}\lVert_{2}}$ exists and is equal to the modulus of one of the eigenvalues
of matrix $\mathcal{A}$.

This result can only guarantee the convergence of $X_{n}$ when all eigenvalues
of $\mathcal{A}$ have modulus smaller than 1. In this case,
$\lim_{n\to\infty}X_{n}=0$. However, for analyzing the non-autonomous linear
systems associated to learning dynamics, it is not sufficient as we will show
that the stablized matrix of these systems generally has eigenvalues equal to
$1$.

##  3 Main results

In this section, we present our 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 a periodic game
in Section 3.2, and investigate the last-iterate behaviors of learning
dynamics in a convergent perturbed game in Section 3.3. Proofs are deferred to
the appendix.

###  3.1 Learning dynamics as linear difference systems

Formalizing learning dynamics as linear difference systems is 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 written as the following linear
difference system:

$\displaystyle\begin{bmatrix}x_{t+1}\\\ y_{t+1}\\\ x_{t}\\\
y_{t}\end{bmatrix}=\begin{bmatrix}I&-2\eta A_{t}&0&\eta A_{t-1}\\\ 2\eta
A_{t}^{\top}&I&-\eta A_{t-1}^{\top}&0\\\ I&0&0&0\\\
0&I&0&0\end{bmatrix}\begin{bmatrix}x_{t}\\\ y_{t}\\\ x_{t-1}\\\
y_{t-1}\end{bmatrix}.$ (2)

Extra-gradient can be written as the following linear difference system :

$\left[\begin{array}[]{c}x_{t+1}\\\ \\\
y_{t+1}\end{array}\right]=\left[\begin{array}[]{cc}I-\alpha\gamma
A_{t}A_{t}^{\top}&-\alpha A_{t}\\\ \\\ \alpha A_{t}^{\top}&I-\gamma\alpha
A_{t}^{\top}A_{t}\end{array}\right]\left[\begin{array}[]{c}x_{t}\\\ \\\
y_{t}\end{array}\right].$ (3)

Negative momentum method can be written as the following linear difference
system:

$\displaystyle\begin{bmatrix}x_{t+1}\\\ \\\ y_{t+1}\\\ \\\ x_{t}\\\ \\\
y_{t}\end{bmatrix}=\begin{bmatrix}(1+\beta_{1})I&-\eta A_{t}&-\beta_{1}I&0\\\
\\\
\eta(1+\beta_{1})A_{t+1}^{\top}&(1+\beta_{2})I-\eta^{2}A_{t+1}^{\top}A_{t}&-\eta\beta_{1}A_{t+1}^{\top}&-\beta_{2}I\\\
\\\ I&0&0&0\\\ \\\ 0&I&0&0\end{bmatrix}\begin{bmatrix}x_{t}\\\ \\\ y_{t}\\\
\\\ x_{t-1}\\\ \\\ y_{t-1}\end{bmatrix}.$ (4)

It is easy to verify that these linear difference systems are 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. In the
following, we will study the convergence/divergence behaviors of these linear
difference systems under the condition that $\\{A_{t}\\}_{t}$ is a periodic
game or convergent perturbed game. Note that although an intermediate step
$(x_{t+\frac{1}{2}},y_{t+\frac{1}{2}})$ is required in extra-gradient, it is
eliminated in (3).

###  3.2 Periodic games

Recall that in a periodic game with period ${\mathcal{T}}$, the payoff
matrices $\\{A_{s}\\}^{\infty}_{s=1}$ satisfy $A_{s+{\mathcal{T}}}=A_{s}$ for
any $s>0$. Define

$\displaystyle\Delta_{i,t}=\lVert A_{i}^{\top}x_{t}\lVert_{2}+\lVert
A_{i}y_{t}\lVert_{2}$ (5)

for $i\in[{\mathcal{T}}]$. As in (Daskalakis and Panageas (2018)), we use
$\Delta_{i,t}$ as a measurement of the distance between the current strategy
$(x_{t},y_{t})$ and a Nash equilibrium of the zero-sum bilinear game defined
by the kernel space of payoff matrix $A_{i}$. Note that if $(x^{*},y^{*})$ is
a Nash equilibrium of the game defined by $A_{i}$, then
$(A_{i}^{\top}x^{*},A_{i}y^{*})=(0,0)$, and

$\displaystyle\Delta_{i,t}$ $\displaystyle=\lVert
A_{i}^{\top}(x_{t}-x^{*})\lVert_{2}+\lVert A_{i}(y_{t}-y^{*})\lVert_{2}$

thus when strategy is close to equilibrium, $\Delta_{i,t}$ will be small.
Moreover, $\Delta_{i,t}=0$ if and only if $(x_{t},y_{t})$ is an equilibrium.
In this section, we will consider the convergence/growth rate of
$\Delta_{i,t}$ at a function of $t$.

We firstly consider Extra-gradient method. Denote the iterative matrix in the
linear difference form of Extra-gradient (3) as $\mathcal{A}_{t}$. In the
following theorem, we prove that if two players use the Extra-gradient 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-gradient in a periodic games with period $T$, with
step size $\alpha=\gamma<\frac{1}{\sigma}$ where
$\sigma=\max\\{\sigma^{\prime}|\sigma^{\prime}\textnormal{\ is a singular
value of\ }A_{i}\textnormal{\ for some\ }i\in[{\mathcal{T}}]\\}.$ Then

$\displaystyle\Delta_{i,t}\in{\mathcal{O}}\left((\lambda_{*})^{t/{\mathcal{T}}}\cdot\textnormal{Poly}(t)\right),\
\forall i\in[{\mathcal{T}}]$

where $\lambda_{*}=\max\\{\ \lvert\lambda\lvert\ |\ \lambda\textnormal{\ is an
eigenvalue of \
}\left(\prod^{\mathcal{T}}_{t=1}\mathcal{A}_{t}\right),\lambda\neq 1\\}$, and
$\lambda_{*}<1$.

Note that in a 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
$\prod^{\mathcal{T}}_{t=1}\mathcal{A}_{t}$.

The key point on the proof of Theorem 3.1 is an observation that the iterative
matrix of extra-gradient is a normal matrix, which makes it possible to
calculate the Jordan normal form of $\prod^{\mathcal{T}}_{t=1}\mathcal{A}_{t}$
for arbitrary large ${\mathcal{T}}$. The details of proof are left to 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 at an exponential rate, regardless of how
they choose their step-sizes and momentum parameters.

######  Theorem 3.2.

Consider a periodic game with period ${\mathcal{T}}=2$, and described by the
following payoff matrix

$\displaystyle A_{t}=\begin{cases}\left[1,-1\right],&t\textnormal{\ \ is \
odd}\\\ \left[-1,1\right],&t\textnormal{\ \ is \ even}\end{cases}$ (6)

with $x_{t}\in{\mathbb{R}},\ y_{t}\in{\mathbb{R}}^{2}$. 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

$\displaystyle\sup_{s\in[t]}\Delta_{i,s}\in\Omega(\lambda^{t}),\
\textnormal{where\ }\lambda>1,\ i\in\\{1,2\\}.$

Here $\lambda$ is determined by the largest modulus of the eigenvalues of the
iterative matrix of optimistic gradient descent ascent or negative 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 a root with modulus
larger than $1$. We achieve this by using the Schur stable theorem, which is
also employed to demonstrate the last iterate convergence of several learning
dynamics in time-independent game (Zhang and Yu (2020)). The proof is deferred
to Appendix C.

In Figure (1), we present the function curves of $\Delta_{1,t}$ 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.

Figure 1: Function curves of $\Delta_{1,t}$ of the game presented in Theorem
3.2. Extra-gradient converges, while the other two methods diverge.

###  3.3 Convergent perturbed game

Recall that the payoff matrix of a convergent perturbed game has form
$A_{t}=A+B_{t}$, where $\lim_{t\to\infty}B_{t}=0$, and we refer to the zero-
sum game defined by payoff matrix $A$ as the stable game. We denote

$\displaystyle\Delta_{t}=\lVert A^{\top}x_{t}\lVert_{2}+\lVert
Ay_{t}\lVert_{2},$ (7)

thus $\Delta_{t}$ measures the distance between the strategy $(x_{t},y_{t})$
in the $t$-th round and the Nash equilibrium of the stable game defined by
$A$. Moreover, $\Delta_{t}=0$ if and only if $(x_{t},y_{t})$ 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);
Elaydi and Györi (1995)):

$\displaystyle\sum_{t=0}^{\infty}\lVert B_{t}\lVert_{2}\textnormal{\ is \
bounded.}$ (BAP assumption)

In the following theorem, we prove that under BAP assumption, all three
learning dynamics considered in this paper will make $\Delta_{t}$ converge to
$0$, with a rate dependent on the vanishing rate of $B_{t}$.

######  Theorem 3.3.

Assume that the (BAP assumption) holds, i.e., $\sum_{t=0}^{\infty}\lVert
B_{t}\lVert_{2}$ is bounded, and let $\sigma$ be the maximum modulus of the
singular value of payoff matrix $A$, then with parameters choice:

  * •

for extra-gradient with step size $\alpha=\eta<\frac{1}{2\sigma}$,

  * •

for optimistic gradient descent ascent with step size
$\eta<\frac{1}{2\sigma}$,

  * •

for negative momentum method with step size $\eta<\frac{1}{\sigma}$ and
momentum parameters $\beta_{1}=-\frac{1}{2}$ and $\beta_{2}=0$,

we have $\Delta_{t}$ converge to $0$ with rate ${\mathcal{O}}(f(t))$. Here

$\displaystyle f(t)=\max\\{\lambda^{t},\sum^{\infty}_{i=t/2}\lVert
B_{i}\lVert_{2}\\},$

and $\lambda\in(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 3.3: 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, we prove a 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_{t}$: if $B_{t}$ has a vanishing rate like
${\mathcal{O}}(\frac{1}{t^{1+\epsilon}})$, for some arbitrary small
$\epsilon>0$, then $\sum_{t=0}^{\infty}\lVert B_{t}\lVert_{2}$ is bounded. We
also note that the condition for $B_{t}$ to vanish at a rate
${\mathcal{O}}(\frac{1}{t^{1+\epsilon}}),\ \forall\epsilon>0$ is necessary to
ensure convergence in general linear difference system. For example, consider
the 1-dimension system $x_{t}=(1+\frac{1}{t})x_{t-1}$ where a
${\mathcal{O}}(\frac{1}{t})$ convergence rate of perturbations leads to
$x_{t}$ diverging with a $\Omega(t)$ rate.

Surprisingly, in the next theorem, we prove that Extra-gradient makes
$\Delta_{t}$ asymptotically converge to $0$, without making any further
assumptions about the converge rate of $B_{t}$.

######  Theorem 3.4.

In a convergent perturbed game, if two players use Extra-gradient, there holds
$\lim_{t\to\infty}\Delta_{t}=0$ with step size $\alpha=\eta<\frac{1}{2\sigma}$
where $\sigma$ is the maximum modulus of the singular value of payoff matrix
$A$.

To prove Theorem 3.4, we first observe that $\lVert x_{t}\lVert_{2}+\lVert
y_{t}\lVert_{2}$ a non-increasing function of $t$ since the iterative matrix
of extra-gradient is a normal matrix. Next, we prove that if Theorem 3.4
doesn’t hold, then $\lVert x_{t}\lVert_{2}+\lVert y_{t}\lVert_{2}$ will
decrease by a constant for infinite number of times, thus leading to a
contradiction with the non-increasing property and the non-negativity of
$\lVert x_{t}\lVert_{2}+\lVert y_{t}\lVert_{2}$ . The proof is deferred to
Appendix F.

##  4 Experiments

In this section we present numerical results for our theoretical results in
Section 3.

Experiments on Theorem 3.1 We verify Theorem 3.1 through a period-$3$ game,
the payoff matrices are chosen to be

$\displaystyle A_{1}=\begin{bmatrix}1&2\\\
2&4\end{bmatrix},A_{2}=\begin{bmatrix}3&7\\\
7&1\end{bmatrix},A_{3}=\begin{bmatrix}4&2\\\ 4&2\end{bmatrix}.$

We run extra-gradient and optimistic gradient descent ascent on this example,
both with step size = 0.01, the experimental results are presented in Figure
(2). We can see extra-gradient (left) makes $\Delta_{i,t}$ converge, while
optimistic gradient descent ascent (right) makes $\Delta_{i,t}$ diverge. This
result supports Theorem 3.1 and provides a numerical example of the separation
of extra-gradient and optimistic gradient descent ascent in periodic games.

Figure 2: Function curves of $\Delta_{t}$ for extra-gradient (left), and
optimistic gradient descent ascent (right).

Experiments on Theorem 3.3 We verify Theorem 3.3 by examples:

$\displaystyle A=\begin{bmatrix}2&3\\\ 4&6\end{bmatrix},B_{1,t}=B\cdot
t^{-1.1},B_{2,t}=B\cdot t^{-4},\textnormal{\ and\ },B_{3,t}=B\cdot t^{-8}$

where $B=[[-15,70],[-90,90]]$. The step size is chosen to be $0.005$. The
initial points are chosen to be $x_{0}=[15,13],x_{-1}=[11,3]$ and
$y_{0}=[35,1],y_{-1}=[35,1]$. The experimental results are presented in Figure
3, all of the three dynamics make $\Delta_{t}$ converge to $0$, 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 in
the theorem. Therefore, we conjecture the bound of convergence rate can be
improved.

Figure 3: Values of $\Delta_{t}$ 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 :

$\displaystyle B_{1,t}=B\cdot t^{-0.4},\ B_{2,t}=B\cdot t^{-0.3},\
B_{3,t}=B\cdot t^{-0.2},$

and

$\displaystyle B_{4,t}=B\cdot\log(t)^{-1.8},\ B_{5,t}=B\cdot\log(t)^{-1.5},\
B_{6,t}=B\cdot\log(t)^{-1.3}.$

where $B=[[-10,10],[-10,10]]$. The payoff matrix of stable game is chosen to
be $A=[[2,3],[4,6]]$. Note that the perturbations do not satisfy (BAP
assumption). The experimental results are shown in Figure (4). We can see all
these curves converge to $0$, thus support the result in Theorem 3.4.
Furthermore, we can observe that large perturbations may lead to more
oscillations during the convergence processes, which in turn slows down the
rate of convergence. We present more experiments in Appendix G.

Figure 4: Values of $\Delta_{t}$ for extra-gradient with $A+B_{i,t},i=1,2,3$
(left), and $A_{2}+B_{i,t},i=4,5,6$ (right).

##  5 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 of periodic game, we prove that extra-gradient 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-gradient methods and optimistic gradient descent ascent. In the case
of convergent perturbed game, we prove all three learning dynamics converge to
Nash equilibrium under the BAP assumption, which is commonly used in the
literature on dynamical systems.

Our results leave many interesting open questions. Firstly, is the BAP
assumption necessary for ensuring 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?

## Acknowledgement

Yi Feng is supported by the Fundamental Research Funds for the Central
Universities. Ioannis Panageas wants to thank a startup grant. Xiao Wang
acknowledges Grant 202110458 from SUFE and support from the Shanghai Research
Center for Data Science and Decision Technology.

## References

  * Anagnostides et al. [2023] Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm.  On the convergence of no-regret learning dynamics in time-varying games.  _arXiv preprint arXiv:2301.11241_ , 2023.
  * Benzaid and Lutz [1987] Z Benzaid and DA Lutz.  Asymptotic representation of solutions of perturbed systems of linear difference equations.  _Studies in Applied Mathematics_ , 77(3):195–221, 1987.
  * Blackwell [1956] David Blackwell.  An analog of the minimax theorem for vector payoffs.  In _Pacific J. Math._ , pages 1–8, 1956.
  * Brown [1951] George W Brown.  Iterative solution of games by fictitious play.  _Act. Anal. Prod Allocation_ , 13(1):374, 1951.
  * Cai et al. [2022] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng.  Finite-time last-iterate convergence for learning in multi-player games.  In _NeurIPS_ , 2022.
  * Cardoso et al. [2019] 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.
  * Colonius and Kliemann [2014] Fritz Colonius and Wolfgang Kliemann.  _Dynamical systems and linear algebra_ , volume 158.  American Mathematical Society, 2014.
  * Daskalakis and Panageas [2018] Constantinos Daskalakis and Ioannis Panageas.  The limit points of (optimistic) gradient descent in min-max optimization.  _Advances in neural information processing systems_ , 31, 2018.
  * Daskalakis and Panageas [2019] 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 _LIPIcs_ , pages 27:1–27:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * Daskalakis et al. [2018] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng.  Training GANs with Optimism.  In _Proceedings of ICLR_ , 2018.
  * Duvocelle et al. [2022] Benoit Duvocelle, Panayotis Mertikopoulos, Mathias Staudigl, and Dries Vermeulen.  Multiagent online learning in time-varying games.  _Mathematics of Operations Research_ , 2022.
  * Elaydi and Györi [1995] S Elaydi and I Györi.  Asymptotic theory for delay differene equations.  _Journal of Difference Equations and Applications_ , 1(2):99–116, 1995.
  * Elaydi et al. [1999] 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.
  * Fiez et al. [2021] 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.
  * Gidel et al. [2019] 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.
  * Gorbunov et al. [2022a] Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel.  Extragradient method: O(1/K) 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.
  * Gorbunov et al. [2022b] Eduard Gorbunov, Adrien Taylor, and Gauthier Gidel.  Last-iterate convergence of optimistic gradient method for monotone variational inequalities.  In _NeurIPS_ , 2022b.
  * Korpelevich [1976] Galina M Korpelevich.  The extragradient method for finding saddle points and other problems.  _Matecon_ , 12:747–756, 1976.
  * Liang and Stokes [2019a] Tengyuan Liang and James Stokes.  Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks.  _AISTATS_ , 2019a.
  * Liang and Stokes [2019b] Tengyuan Liang and James Stokes.  Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 907–915. PMLR, 2019b.
  * Mai et al. [2018] 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.
  * Mertikopoulos et al. [2019] 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.
  * Monteiro and Svaiter [2010] 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):2755–2787, 2010.
  * Nemirovski [2004] 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.
  * Nesterov [2005] Yurii Nesterov.  Smooth minimization of non-smooth functions.  _Math. Program._ , 103(1):127–152, 2005.
  * Pituk [2002] 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.
  * Popov [1980] 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–848, 1980.
  * Roy et al. [2019] Abhishek Roy, Yifang Chen, Krishnakumar Balasubramanian, and Prasant Mohapatra.  Online and bandit algorithms for nonstationary stochastic saddle-point optimization.  _CoRR_ , abs/1912.01698, 2019.
  * Syrgkanis et al. [2015] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire.  Fast convergence of regularized learning in games.  In Corinna Cortes, Neil D. 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.
  * Wei et al. [2021] Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo.  Linear last-iterate convergence in constrained saddle-point optimization.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.
  * Zhang and Wang [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.
  * Zhang and Yu [2020] Guojun Zhang and Yaoliang Yu.  Convergence of gradient methods on bilinear zero-sum games.  In _International Conference on Learning Representations_ , 2020.
  * Zhang et al. [2022] 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 26772–26808. PMLR, 2022.
  * Zinkevich [2003] 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.

##  Appendix A Step sizes and eigenvalues of the iterative matrix

The eigenvalues of the iterative matrices in the linear differences systems in
(2) (3) and (4) play a crucial role in analyzing the dynamic behavior of
learning dynamics. In this section, we study how the choice of step sizes in
learning dynamics affects the eigenvalues of these iterative matrices.

We firstly present the following corollary of Schur’s theorem, which was also
used in Zhang and Yu [2020] to demonstrate the convergence of learning
dynamics in time-independent games.

######  Lemma A.1.

(Corollary 2.1 in Zhang and Yu [2020]). The roots of a real quartic polynomial
$\lambda^{4}+a\lambda^{3}+b\lambda^{2}+c\lambda+d$ are within the (open) unit
disk of the complex plane if and only if $|c-ad|<1-d^{2}$, $|a+c|<b+d+1$ and
$b<(1+d)+(c-ad)(a-c)/(d-1)^{2}$.

######  Lemma A.2.

Let $\sigma$ be the maximum modulus of the singular value of payoff matrix
$A$. Then if for extra-gradient method with step size
$\alpha=\gamma<\frac{1}{2\sigma}$, optimistic gradient descent ascent with
step size $\eta<\frac{1}{2\sigma}$, and negative momentum method with step
size $\eta<\frac{1}{\sigma}$ and momentum parameters $\beta_{1}=-\frac{1}{2}$
and $\beta_{2}=0$, then for the iterative matrices $\mathcal{A}$ in (2) (3)
and (4), we have the following conclusion:

  * •

If payoff matrix $A$ is non-singular, then the modulus of eigenvalues of these
iterative matrices $\mathcal{A}$ are strictly less than $1$.

  * •

If payoff matrix $A$ is singular, then $1$ is an eigenvalue of the iterative
matrix $\mathcal{A}$, and other eigenvalues of $\mathcal{A}$ have modulus
strictly less than $1$.

###### Proof.

OGDA. We first write the characteristic polynomials of the iterative matrix
$\mathcal{A}$ in (2) when payoff matrix is equal to $A$. Recall in this case,
we have

$\displaystyle\mathcal{A}=\begin{bmatrix}I&-2\eta A^{\top}&0&\eta A^{\top}\\\
\\\ 2\eta A&I&-\eta A&0\\\ \\\ I&0&0&0\\\ \\\ 0&I&0&0\end{bmatrix}.$ (8)

The characteristic polynomial equations are:

$\displaystyle\lambda^{2}(\lambda-1)^{2}+\eta^{2}\sigma_{i}^{2}(1-2\lambda)^{2}=0,i\in[m]$
(9)

where $\sigma_{i}$ is a singular value of $A$. And then according to Lemma
A.1, it is easy to verify if $0<\eta\sigma<\frac{1}{2}$, then the norm of
roots of the above polynomial is always less than 1. When $\sigma_{i}=0$, we
have the eigenvalues of $\mathcal{A}$ come from (9) are equal to 1.

In all, if the payoff matrix $A$ is non-singular, we have the modulus of
eigenvalue of $\mathcal{A}$ is strictly smaller than 1. And if there exists
some singular value of $A$ equals to 0, we can obtain that if $\sigma_{i}=0$,
then $\mathcal{A}$ has eigenvalue equal to 1, otherwise, $\mathcal{A}$ only
has eigenvalues whose norm is less than 1.

EG. We first write characteristic polynomial of iterative matrix $\mathcal{A}$
in (3), with payoff matrix equals to $A$. We have

$\displaystyle\mathcal{A}=\begin{bmatrix}I-\alpha\gamma AA^{\top}&-\alpha A\\\
\\\ \alpha A^{\top}&I-\gamma\alpha A^{\top}A\end{bmatrix}.$

The characteristic polynomial equations are:

$\displaystyle(\lambda-1)^{2}+2\gamma\alpha\sigma_{i}^{2}(\lambda-1)+\alpha^{2}\sigma_{i}^{2}+\alpha^{2}\gamma^{2}\sigma_{i}^{4}=0,i\in[m]$

where $\sigma_{i}$ is a singular value of $A$. And then by Lemma A.1, the norm
of roots of the above polynomial is always less than 1 if the following holds
for all $i\in[m]$,

$\displaystyle\alpha^{2}\sigma_{i}^{2}+(\alpha\gamma\sigma_{i}^{2}-1)^{2}<1.$
(10)

It is easy to verify that $\alpha=\gamma<\frac{1}{2\sigma}$ satisfies the
above inequalities. Then we can use similar analysis in the part of OGDA to
prove the conclusion for EG.

Negative Momentum Method. First we write characteristic polynomial of
iterative matrix $\mathcal{A}$ defined in (4) when payoff payoff equals to
$A$, we have

$\displaystyle\mathcal{A}=\begin{bmatrix}(1+\beta_{1})I&-\eta
A&-\beta_{1}I&0\\\ \\\
\eta(1+\beta_{1})A^{\top}&(1+\beta_{2})I-\eta^{2}A^{\top}A&-\eta\beta_{1}A^{\top}&-\beta_{2}I\\\
\\\ I&0&0&0\\\ \\\ 0&I&0&0\end{bmatrix}.$ (11)

The characteristic polynomial equations are:

$\displaystyle(\lambda-1)^{2}(\lambda-\beta_{1})(\lambda-\beta_{2})+\eta^{2}\sigma_{i}^{2}\lambda^{3}=0,i\in[m]$

when $\beta_{1}=-\frac{1}{2}$, $\beta_{2}=0$ and $\eta<\frac{1}{\sigma}$
satisfies conditions in Lemma A.1. We can also use a similar analysis as in
the OGDA part to prove the conclusion for negative momentum method. ∎

##  Appendix B Omitted Proofs from Theorem 3.1

See 3.1

In this section, we prove Theorem 3.1. In the following, we use
$\tilde{\mathcal{A}}$ to denote matrix $\prod_{i=1}^{T}\mathcal{A}_{i}$. As
shown by the Floquet theorem, the asymptotic behavior of a periodic linear
system is determined by the product of iterative matrices over one period.
Therefore, the analysis can be reduced to that of an autonomous system. We
analyze the Jordan normal form of the product matrix for extra-gradient. We
prove that the product matrix has no eigenvalues with a modulus larger than
$1$. Moreover, the Jordan blocks of $1$ as an eigenvalue of the product matrix
have size equals to $1$. These facts are enough to show the exponentially
convergent behavior of extra-gradient. Before going through details of the
proof, we provide a road map for the proof in Figure LABEL:rb.

Recall that EG can be written in a single linear difference system as

$\displaystyle\begin{bmatrix}x_{t+1}\\\ \\\
y_{t+1}\end{bmatrix}=\begin{bmatrix}I-\alpha\gamma A_{t}A_{t}^{\top}&-\alpha
A_{t}\\\ \\\ \alpha A_{t}^{\top}&I-\gamma\alpha
A_{t}^{\top}A_{t}\end{bmatrix}\begin{bmatrix}x_{t}\\\ \\\ y_{t}\end{bmatrix}.$
(12)

Denote $\mathcal{A}_{t}$ the iterative matrix in (12). The following lemma
tells us that $\mathcal{A}_{t}$ is a normal matrix.

######  Lemma B.1.

For any $i\in[T]$, $\mathcal{A}_{i}$ is a normal matrix.

###### Proof.

We have

$\displaystyle\mathcal{A}_{i}\mathcal{A}_{i}^{\top}=\mathcal{A}_{i}^{\top}\mathcal{A}_{i}=\begin{bmatrix}(I-\alpha\gamma
A_{i}A_{i}^{\top})^{2}+\alpha^{2}A_{i}A_{i}^{\top}&0\\\ \\\ 0&(I-\alpha\gamma
A_{i}^{\top}A_{i})^{2}+\alpha^{2}A_{i}^{\top}A_{i}\end{bmatrix}.$

∎

Using above lemma, we can present several useful lemmas to describe Jordan
form of matrix $\tilde{\mathcal{A}}$.

######  Lemma B.2.

If $\alpha=\gamma<\frac{1}{\sigma}$, then for any $i\in[T]$,
$\lVert\mathcal{A}_{i}\lVert_{2}\leq 1$, and
$\ker(\tilde{\mathcal{A}}-I)=\cap^{T}_{i=1}\ker(\mathcal{A}_{i}-I)$. Moreover,
denote

$\lambda_{*}=\max\\{\ \lvert\lambda\lvert\ |\ \lambda\textnormal{\ is an
eigenvalue of \ }\tilde{\mathcal{A}},\lambda\neq 1\\},$

then we have $\lambda_{*}<1$.

###### Proof.

$(\Leftarrow)$ : If $v\in\cap^{T}_{i=1}\ker(\mathcal{A}_{i}-I)$, then for any
$i\in\\{1,...,T\\}$, $\mathcal{A}_{i}v=v$, thus

$\displaystyle\tilde{\mathcal{A}}v=\mathcal{A}_{T}\mathcal{A}_{T-1}...\mathcal{A}_{1}v=v.$

Then we have
$\cap^{T}_{i=1}\ker(\mathcal{A}_{i}-I)\subseteq\ker(\tilde{\mathcal{A}}-I)$.

$(\Rightarrow)$ : Let $v\in\ker(\tilde{\mathcal{A}}-I)$, then we have $\lVert
v\lVert_{2}=\lVert\mathcal{A}_{T}...\mathcal{A}_{1}v\lVert_{2}$. Denote
$\lVert\cdot\lVert_{2}$ as 2-norm of matrices and vectors. According to Lemma
A.2, if $\alpha=\gamma<\frac{1}{\sigma}$, then the spectral radius
$\rho({\mathcal{A}_{i}})$ of $\mathcal{A}_{i}$ is no larger than 1. Combining
with the fact that $\mathcal{A}_{i}$ is normal, we have
$\lVert{\mathcal{A}_{i}}\lVert_{2}=\rho(\mathcal{A}_{i})\leq 1$ for $i\in[T]$.
We claim that if $\lVert
v\lVert_{2}=\lVert\mathcal{A}_{T}...\mathcal{A}_{1}v\lVert_{2}$, then we have
$A_{i}v=v$ for $i\in[T]$. We prove it by contradiction. Suppose the claim is
not true. Let $s$ be the minimum $i$ such that $\mathcal{A}_{i}v\neq v$. Since
$\mathcal{A}_{s}$ is normal and its eigenvalues whose modulus equal to 1 can
only be 1, we have $\lVert\mathcal{A}_{s}v\lVert_{2}<\lVert v\lVert_{2}$, then
there holds

$\displaystyle\lVert v\lVert_{2}$
$\displaystyle=\lVert\mathcal{A}_{T}...\mathcal{A}_{s}...\mathcal{A}_{1}v\lVert_{2}$
$\displaystyle=\lVert\mathcal{A}_{T}...\mathcal{A}_{s}v\lVert_{2}$
$\displaystyle<\lVert\mathcal{A}_{T}...\mathcal{A}_{s+1}\lVert_{2}\lVert
v\lVert_{2}$ $\displaystyle\leq\lVert v\lVert_{2},$

which leads to a contradiction. Therefore, for any $i\in[T]$, we obtain that
$\mathcal{A}_{i}v=v$, i.e., $v\in\ker(\mathcal{A}_{i}-I)$. From the claim, we
know that if $v\in\ker(\tilde{\mathcal{A}}-I)$ , then
$v\in\ker(\mathcal{A}_{i}-I)$ for $i\in[T]$. Thus we have
$\ker(\tilde{\mathcal{A}}-I)\subseteq\cap^{T}_{i=1}\ker(\mathcal{A}_{i}-I)$.

Next we prove that $\lambda_{*}\leq 1$. By the definition of $\lambda_{*}$, we
obtain

$\displaystyle\lambda_{*}$
$\displaystyle\leq\rho(\mathcal{A}_{T}\cdots\mathcal{A}_{1})$
$\displaystyle\leq\lVert\mathcal{A}_{T}\cdots\mathcal{A}_{1}\lVert_{2}$
$\displaystyle\leq\lVert\mathcal{A}_{T}\lVert_{2}\cdots\lVert\mathcal{A}_{1}\lVert_{2}\leq
1,$

where the second inequality holds because the spectral radius
$\rho(A)\leq\lVert A\lVert_{2}$ for any matrix $A$.

Now we prove that $\lambda_{*}\neq 1$, which means that $\tilde{\mathcal{A}}$
have no eigenvalue $\lambda$ satisfying $\lambda\neq 1$ and
$\lvert\lambda\lvert=1$. Assuming $v$ is the eigenvector of
$\tilde{\mathcal{A}}$ corresponding to $\lambda^{\prime}$, where
$\lvert\lambda^{\prime}\lvert=1$, we can obtain
$\lVert\mathcal{A}_{T}...\mathcal{A}_{1}v\lVert_{2}=\lVert\lambda^{\prime}v\lVert_{2}=\lVert
v\lVert_{2}$. Similar to the proof above, $\mathcal{A}_{i}v=v$ for $i\in[T]$,
which implies that $\lambda^{\prime}=1$. This completes the proof of
$\lambda_{*}<1$.

∎

######  Lemma B.3.

Under a suitable orthogonal normal basis, $\tilde{\mathcal{A}}$ has form

$\displaystyle\begin{bmatrix}\bf{I_{r\times r}}&\bf{0}\\\ \\\
\bf{0}&\bf{C}\end{bmatrix},$ (13)

where $\bf{I_{r\times r}}\in{\mathbb{R}}^{r\times r}$,
$\bf{C}\in{\mathbb{R}}^{(n+m-r)\times(n+m-r)}$, and
$r={\mathrm{dim}}_{{\mathbb{R}}}(\ker(\tilde{\mathcal{A}}-I))$.

###### Proof.

Let $\\{v_{1},...,v_{r}\\}$ be an orthogonal normal basis of
$\ker(\tilde{\mathcal{A}}-I)$, i.e., $\langle v_{i},v_{j}\rangle=1$ if $i=j$,
$\langle v_{i},v_{j}\rangle=0$ if $i\neq j$. First, we extend
$\\{v_{1},...,v_{r}\\}$ to an orthonormal basis of ${\mathbb{R}}^{n+m}$ and
denote this basis by $\\{v_{1},...,v_{r},v_{r+1},...,v_{n+m}\\}$. We also
denote $M$ the matrix consisting of
$\\{v_{1},...,v_{r},v_{r+1},...,v_{n+m}\\}$ as columns. With these settings,
we have $M^{\top}M=MM^{\top}=I$.

Under this basis, $\mathcal{A}_{i}$ is represented by matrix

$\displaystyle\begin{bmatrix}\bf{I_{r\times r}}&\bf{0}\\\ \\\
\bf{C_{i,1}}&\bf{C_{i,2}}\end{bmatrix}.$ (14)

Moreover, as $\mathcal{A}_{i}$ is a normal matrix, its representation under an
orthogonal normal basis is still a normal matrix, thus we have

$\displaystyle\begin{bmatrix}\bf{I_{r\times r}}&&\bf{0}\\\ \\\
\bf{C_{i,1}}&&\bf{C_{i,2}}\end{bmatrix}\begin{bmatrix}\bf{I_{r\times
r}}&&\bf{C^{\top}_{i,1}}\\\ \\\
\bf{0}&&\bf{C^{\top}_{i,2}}\end{bmatrix}=\begin{bmatrix}\bf{I_{r\times
r}}&&\bf{C^{\top}_{i,1}}\\\ \\\
\bf{0}&&\bf{C^{\top}_{i,2}}\end{bmatrix}\begin{bmatrix}\bf{I_{r\times
r}}&&\bf{0}\\\ \\\ \bf{C_{i,1}}&&\bf{C_{i,2}}\end{bmatrix}.$ (15)

Note that (15) is equivalent to

$\displaystyle\begin{bmatrix}\bf{I_{r\times r}}&&\bf{C^{\top}_{i,1}}\\\ \\\
\bf{C_{i,1}}&&\bf{C_{i,1}C^{\top}_{i,1}}+\bf{C_{i,2}C^{\top}_{i,2}}\end{bmatrix}=\begin{bmatrix}\bf{I_{r\times
r}}+\bf{C^{\top}_{i,1}C_{i,1}}&&\bf{C^{\top}_{i,1}C_{i,2}}\\\ \\\
\bf{C^{\top}_{i,2}C_{i,1}}&&\bf{C^{\top}_{i,2}C_{i,2}}\end{bmatrix}.$

As a consequence, we have $\bf{C^{\top}_{i,1}}\bf{C_{i,1}}=0$, and
furthermore, this implies $\bf{C_{i,1}}=0$. Thus (14) has form

$\displaystyle\begin{bmatrix}\bf{I_{r\times r}}&\bf{0}\\\ \\\
\bf{0}&\bf{C_{i,2}}\end{bmatrix},$

and under this basis, $\tilde{\mathcal{A}}$ can be represented by

$\displaystyle\begin{bmatrix}\bf{I_{r\times r}}&&\bf{0}\\\ \\\
\bf{0}&&\prod^{T}_{i=1}\bf{C_{i,2}}\end{bmatrix}.$

Since $\prod^{T}_{i=1}\bf{C_{i,2}}$ is a matrix with size of
$(n+m-r)\times(n+m-r)$, we complete the proof. ∎

######  Corollary B.4.

If $\lambda=1$ is an eigenvalue of $\tilde{\mathcal{A}}$, then the Jordan
blocks of $\tilde{\mathcal{A}}$ corresponding to eigenvalue $1$ has size $1$.

###### Proof.

From Lemma B.3, we have a decomposition
${\mathbb{R}}^{m+n}=\ker(\tilde{\mathcal{A}}-I)\oplus V^{\prime}$, and both
these two spaces are invariant under the action of $\tilde{\mathcal{A}}$. Thus
we can choose a basis of $V^{\prime}$ consisting of Jordan chains and denote
this basis by $\\{w_{1},...,w_{m+n-r}\\}$, then under the basis
$\\{w_{1},...,w_{m+n-r}\\}\cup\\{v_{1},...,v_{r}\\}$, $\tilde{\mathcal{A}}$ is
a block diagonal matrix. Moreover, there is no eigenvectors corresponding to
eigenvalue $1$ in $\\{w_{1},...,w_{m+n-r}\\}$, because any $w_{i}$ is linearly
independent with $\\{v_{1},...,v_{r}\\}$ (since they are basis), thus if some
$w_{i}$ is an eigenvector of eigenvalue $1$, then a contradiction is conducted
since it is assumed that
${\mathrm{dim}}_{{\mathbb{R}}}(\ker(\tilde{\mathcal{A}}-I))=r$. ∎

######  Lemma B.5.

Denote $X_{t}=(x_{t},y_{t})$ be the strategies of players at round of $t$ when
they are playing extra-gradient. For any $i\in[T]$, if
$\lVert(\mathcal{A}_{i}-I)X_{t}\lVert_{2}$ converges to 0 with rate
${\mathcal{O}}\left((\lambda_{*})^{t/T}\cdot\textnormal{Poly}(t)\right)$, then
$\Delta_{i,t}$ converges to 0 with rate
${\mathcal{O}}\left((\lambda_{*})^{t/T}\cdot\textnormal{Poly}(t)\right)$.

###### Proof.

Writing $(\mathcal{A}_{i}-I)X_{t}$ in a matrix form:

$\displaystyle\begin{bmatrix}-\alpha\gamma A_{i}A_{i}^{\top}&-\alpha A_{i}\\\
\\\ \alpha A_{i}^{\top}&-\alpha\gamma
A_{i}^{\top}A_{i}\end{bmatrix}\begin{bmatrix}x_{t-1}\\\ \\\ y_{t-1}\\\
\end{bmatrix}=\begin{bmatrix}-\alpha\gamma A_{i}A_{i}^{\top}x_{t-1}-\alpha
A_{i}y_{t-1}\\\ \\\ \alpha A_{i}^{\top}x_{t-1}-\alpha\gamma
A_{i}^{\top}A_{i}y_{t-1}\end{bmatrix}.$

For the sake of readability, we denote
$g(t)=(\lambda_{*})^{t/T}\cdot\textnormal{Poly}(t)$. According to the
assumption, there is a constant $c$ such that
$\lVert(\mathcal{A}_{i}-I)X_{t}\lVert_{2}\leq cg(t)$, then we have

$\displaystyle\lVert-\gamma
A_{i}A_{i}^{\top}x_{t-1}-A_{i}y_{t-1}\lVert_{2}\leq\frac{cg(t)}{\alpha},$
$\displaystyle\lVert A_{i}^{\top}x_{t-1}-\gamma
A_{i}^{\top}A_{i}y_{t-1}\lVert_{2}\leq\frac{cg(t)}{\alpha}.$

Let $c_{1}=\max\\{\lVert A_{i}\lVert_{2},i\in[T]\\}$. Using these two
inequalities to bound $\lVert A_{i}^{\top}x_{t}\lVert_{2}$, we have

$\displaystyle\lVert(\gamma^{2}A_{i}^{\top}A_{i}+I)A_{i}^{\top}x_{t-1}\lVert_{2}$
$\displaystyle=$
$\displaystyle\lVert\gamma^{2}A_{i}^{\top}A_{i}A_{i}^{\top}x_{t-1}+A_{i}^{\top}x_{t-1}\lVert_{2}$
$\displaystyle=$ $\displaystyle\lVert A_{i}^{\top}x_{t-1}-\gamma
A_{i}^{\top}A_{i}y_{t-1}-\gamma A_{i}^{\top}(-\gamma
A_{i}A_{i}^{\top}x_{t-1}-A_{i}y_{t-1})\lVert_{2}$ $\displaystyle\leq$
$\displaystyle\lVert A_{i}^{\top}x_{t-1}-\gamma
A_{i}^{\top}A_{i}y_{t-1}\lVert_{2}+\gamma\lVert
A_{i}^{\top}\lVert_{2}\lVert-\gamma
A_{i}A_{i}^{\top}x_{t-1}-A_{i}y_{t-1}\lVert_{2}$ $\displaystyle\leq$
$\displaystyle\frac{c(1+\gamma c_{1})g(t)}{\alpha}.$

Since matrix $\gamma^{2}A_{i}^{\top}A_{i}+I$ is invertible, then

$\displaystyle\lVert A_{i}x_{t}\lVert_{2}=$
$\displaystyle(\gamma^{2}A_{i}^{\top}A_{i}+I)^{-1}(\gamma^{2}A_{i}^{\top}A_{i}+I)A_{i}^{\top}x_{t-1}\lVert_{2}$
$\displaystyle\leq$
$\displaystyle\lVert(\gamma^{2}A_{i}^{\top}A_{i}+I)^{-1}\lVert_{2}\lVert(\gamma^{2}A_{i}^{\top}A_{i}+I)A_{i}^{\top}x_{t-1}\lVert_{2}$
$\displaystyle\leq$
$\displaystyle\lVert(\gamma^{2}A_{i}^{\top}A_{i}+I)A_{i}^{\top}x_{t-1}\lVert_{2}$
$\displaystyle\leq$ $\displaystyle\frac{c(1+\gamma)g(t)}{\alpha},$

where the last inequality is due to
$\lVert(\gamma^{2}A_{i}^{\top}A_{i}+I)^{-1}\lVert_{2}\leq 1$. Similarly, we
can obtain

$\lVert A_{i}y_{t}\lVert_{2}\leq\frac{c(1+\gamma c_{1})g(t)}{\alpha}.$

Thus by definition of $\Delta_{i,t}=\lVert A_{i}^{\top}x_{t}\lVert_{2}+\lVert
A_{i}y_{t}\lVert_{2}$, $\Delta_{i,t}$ converges to 0 with rate
${\mathcal{O}}\left((\lambda_{*})^{t/T}\cdot\textnormal{Poly}(t)\right)$. ∎

Now we are ready to prove Theorem 3.1.

###### Proof of Theorem 3.1..

We have proved $\lambda_{*}<1$ in Lemma B.2, now we prove the part of
convergence rate. Note that here we cannot directly apply the Floquet theorem
in Proposition 2.4, as it requires all iterative matrices within a period to
be invertible. However, the proof here follows the same idea as the Floquet
theorem : the convergence behavior of a periodic linear difference system is
determined by the product of all iterative matrices of the system in a period.
According to Corollary B.4, we can write Jordan form $J$ of
$\tilde{\mathcal{A}}$ in the following way:

$\displaystyle J=\begin{bmatrix}I&0\\\ 0&\tilde{J}\end{bmatrix},$

where $\tilde{J}$ consists of Jordan blocks corresponding to eigenvalues whose
modulus not equal to 1. According to Lemma B.2, we have that the modulus of
eigenvalues of $\tilde{J}$ are less than 1. Moreover, we assume

$\displaystyle J=P^{-1}\tilde{A}P.$

Denote $J_{k}(\lambda)$ as a Jordan block corresponding to eigenvalue
$\lambda$ with size $k$, and $\lvert\lambda\lvert<1$. We can write
$J_{k}(\lambda)=\lambda I+N$, where $N$ represents the nilpotent matrix whose
superdiagonal contains $1$’s and all other entries are zero. Moreover, we have
$N^{k}=0$ and $\lVert N\lVert_{2}=1$.

For each Jordan block $J_{k}(\lambda)$, without loss of generality, when
$s>2k$, by the binomial theorem:

$\displaystyle J^{s}_{k}(\lambda)=(\lambda
I+N)^{s}=\sum_{r=0}^{s}\left(\begin{array}[]{l}s\\\
r\end{array}\right)\lambda^{s-r}N^{r}.$

Then

$\lVert J^{s}_{k}(\lambda)\lVert_{2}\leq(k-1)\left(\begin{array}[]{l}s\\\
k-1\end{array}\right)\lvert\lambda\lvert^{s-k+1},$

since $\lVert N\lVert_{2}=1$ and $s>2k$. We know that
$\left(\begin{array}[]{l}s\\\ k-1\end{array}\right)$ is a polynomial of $s$
with degree $k\leq n+m$. Since $\lvert\lambda\lvert<1$, $\lVert
J^{s}_{k}(\lambda)\lVert_{2}$ goes to zero in rate
${\mathcal{O}}\left((\lambda_{*})^{s}\cdot\textnormal{Poly}(s)\right)$. Since
$J^{s}_{k}(\lambda)$ are blocks in block diagnol matrix $\tilde{J}^{s}$, then

$\displaystyle\lVert\tilde{J}^{s}\lVert_{2}\leq\sum_{\lambda\in\text{Eigenvalue}\left(\tilde{\mathcal{A}}\right),\lambda\neq
1}\lVert J^{s}_{k}(\lambda)\lVert_{2},$

and $\lVert\tilde{J}^{s}\lVert_{2}$ goes to zero in rate
${\mathcal{O}}\left((\lambda_{*})^{s}\cdot\textnormal{Poly}(s)\right)$. For
any $t$, without loss of generality, we assume that $t=sT+j$, and $j\in[T]$ is
the remainder. Then we have

$\displaystyle(\tilde{\mathcal{A}}-I)X_{t}=$
$\displaystyle(\tilde{\mathcal{A}}-I)\tilde{\mathcal{A}^{s}}X_{j}$
$\displaystyle=$
$\displaystyle(\tilde{\mathcal{A}}^{s+1}-\tilde{\mathcal{A}}^{s})X_{j}$
$\displaystyle=$ $\displaystyle P^{-1}(J^{s+1}-J^{s})PX_{j}$ $\displaystyle=$
$\displaystyle P^{-1}\left(\begin{bmatrix}I&0\\\
0&J_{1}^{s+1}\end{bmatrix}-\begin{bmatrix}I&0\\\
0&J_{1}^{s}\end{bmatrix}\right)PX_{j}$ $\displaystyle=$ $\displaystyle
P^{-1}\left(\begin{bmatrix}0&0\\\
0&J_{1}^{s+1}-J_{1}^{s}\end{bmatrix}\right)PX_{j}.$

Taking norm on both sides, we have

$\displaystyle\lVert(\tilde{\mathcal{A}}-I)X_{t}\lVert_{2}\leq(\lVert
J_{1}^{s+1}\lVert_{2}+\lVert J_{1}^{s}\lVert_{2})\lVert X_{j}\lVert_{2}\leq
2\lVert J_{1}^{s}\lVert_{2}\lVert X_{j}\lVert_{2}.$

From definition of $s$, we know that $s=\lfloor t/T\rfloor\geq t/T-1$, leading
to $(\lambda_{*})^{s}\leq\frac{1}{\lambda_{*}}(\lambda_{*})^{t/T}$. Since
$\lVert J_{1}^{s}\lVert_{2}$ converges to zero with rate
${\mathcal{O}}\left((\lambda_{*})^{s}\cdot\textnormal{Poly}(s)\right)$, then
$\lVert(\tilde{\mathcal{A}}-I)X_{t}\lVert_{2}$ converges to zero with rate
${\mathcal{O}}\left((\lambda_{*})^{t/T}\cdot\textnormal{Poly}(t)\right)$. By
Lemma B.2, for any $i\in[T]$, $\lVert(\mathcal{A}_{i}-I)X_{t}\lVert_{2}$ goes
to zero in rate
${\mathcal{O}}\left((\lambda_{*})^{t/T}\cdot\textnormal{Poly}(t)\right)$.

According to Lemma B.5, we conclude for any $i\in[T]$, $\Delta_{i,t}$ goes to
zero with convergence rate
${\mathcal{O}}\left((\lambda_{*})^{t/T}\cdot\textnormal{Poly}(t)\right)$, this
completes the proof. ∎

##  Appendix C Omitted Proofs from Theorem 3.2

See 3.2

###  C.1 On initialization

Before proving Theorem 3.2, we discuss a more detailed question :

_Which initial points will make (OGDA) and (NM) diverge ?_

In fact, it is obviously that not every initial point will make optimistic
gradient descent ascent and negative momentum method diverge. For example, if
the initial point is chosen to be

$\displaystyle(x_{0},y_{0})\in(\ker A_{t}^{\top},\ker A_{t}),$ (16)

then these point will be not diverge because they are stationary points of the
game dynamics.

In the proof of Theorem 3.2 below, we explicitly construct initial points that
diverge exponentially fast under (OGDA) or (NM). In Figure 6, we present an
example of an initial point that converges under (NM) with the game defined by
(35). In fact, we can see that these converge initial points of (OGDA) or (NM)
lie on a low dimension space, thus have measure zero. Note that this doesn’t
conflict with Theorem 3.2, since we are not claiming that optimistic gradient
descent ascent or negative momentum method will make every initial point
diverge.

Figure 6: A converge initial point for negative momentum method, with initial
condition $x_{0}=x_{-1}=0$, and $y_{0}=(-0.4,1),\ y_{-1}=(1,-1)$. The curve is
$\Delta_{1,t}$.

In the following sections C.2 and C.3, we will prove that both negative
momentum method and OGDA diverge with an exponential rate under certain
initial conditions. The proof idea is the same for these two learning dynamics
: firstly, we prove that the product of iterative matrices in a period for
these learning dynamics have an eigenvalue with modulus larger than $1$; then,
we show that eigenvectors corresponding to this eigenvalue as initial
condition will diverge under the learning dynamics.

###  C.2 Negative Momentum Method

We first consider negative momentum method with step size $\eta$, recall it
can be written as:

$\displaystyle x_{t+1}=x_{t}-\eta A_{t}y_{t}+\beta_{1}(x_{t}-x_{t-1}),$
$\displaystyle y_{t+1}=y_{t}+\eta
A_{t+1}^{\top}x_{t+1}+\beta_{2}(y_{t}-y_{t-1}),$

where $\beta_{1},\beta_{2}\leq 0$ are the momentum parameters. Writing
negative momentum method in matrix form, we have

$\displaystyle\begin{bmatrix}x_{t+1}\\\ \\\ y_{t+1}\\\ \\\ x_{t}\\\ \\\
y_{t}\end{bmatrix}=\begin{bmatrix}(1+\beta_{1})I&-\eta A_{t}&-\beta_{1}I&0\\\
\\\
\eta(1+\beta_{1})A_{t+1}^{\top}&(1+\beta_{2})I-\eta^{2}A_{t+1}^{\top}A_{t}&-\eta\beta_{1}A_{t+1}^{\top}&-\beta_{2}I\\\
\\\ I&0&0&0\\\ \\\ 0&I&0&0\end{bmatrix}\begin{bmatrix}x_{t}\\\ \\\ y_{t}\\\
\\\ x_{t-1}\\\ \\\ y_{t-1}\end{bmatrix}$ (17)

Denote the iterative matrix in (17) as $\mathcal{A}_{t}$ and
$X_{t}=(x_{t}^{\top},y_{t}^{\top},x_{t-1}^{\top},y_{t-1}^{\top})^{\top}$. Let
$\tilde{\mathcal{A}}_{NM}=\mathcal{A}_{t+1}\mathcal{A}_{t}$, by Floquet
Theorem, $\tilde{\mathcal{A}}_{NM}$ will determine the dynamical behaviors of
negative momentum method. We have

$X_{t}=\tilde{\mathcal{A}}_{NM}X_{t-2},\ \text{for any $t\geq 2$}.$

In the following lemma, we show that the spectral radius of
$\tilde{\mathcal{A}}_{NM}$ is always larger than $1$.

######  Lemma C.1.

For any step size $\eta>0$, and momentum parameters $\beta_{1},\ \beta_{2}\leq
0$, the spectral radius of $\tilde{\mathcal{A}}_{NM}$ is larger than $1$.

###### Proof.

We directly compute the characteristic polynomial
$P_{\tilde{\mathcal{A}}_{NM}}(\lambda)$ of matrix $\tilde{\mathcal{A}}_{NM}$
as follows 222Symbolic computing software, such as Matlab, can be used to
perform the computation of characteristic polynomial. :

$\displaystyle P_{\tilde{\mathcal{A}}_{NM}}(\lambda)$
$\displaystyle=\det(\lambda I-\tilde{\mathcal{A}}_{NM})$ $\displaystyle=$
$\displaystyle[\lambda^{4}-\big{(}4\eta^{4}+4\eta^{2}(\beta_{2}-\beta_{1})+\beta_{1}^{2}+\beta_{2}^{2}+2\big{)}\cdot\lambda^{3}$
$\displaystyle+\big{(}4\eta^{2}(\beta_{2}-\beta_{1})+\beta_{1}^{2}\beta_{2}^{2}+2\beta_{1}^{2}+2\beta_{2}^{2}+1\big{)}\cdot\lambda^{2}$
$\displaystyle-\big{(}2\beta_{1}^{2}\beta_{2}^{2}+\beta_{1}^{2}+\beta_{2}^{2}\big{)}\cdot\lambda+\beta_{1}^{2}\beta_{2}^{2}]\cdot(\lambda-1)\cdot(\lambda-\beta_{2}^{2}).$

Note that this is a polynomial on $\lambda$ of degree $6$, with two roots
$\lambda=1$ and $\lambda=\beta^{2}_{2}$.

Thus, eigenvalues of matrix $\tilde{\mathcal{A}}_{NM}$ consists of $1$,
$\beta_{2}^{2}$ and roots of the quartic polynomial

$\displaystyle g(\lambda)=\lambda^{4}+a\lambda^{3}+b\lambda^{2}+c\lambda+d,$

with coefficients

$\displaystyle
a=-(4\eta^{4}+4\eta^{2}(\beta_{2}-\beta_{1})+\beta_{1}^{2}+\beta_{2}^{2}+2),$
$\displaystyle
b=4\eta^{2}(\beta_{2}-\beta_{1})+\beta_{1}^{2}\beta_{2}^{2}+2\beta_{1}^{2}+2\beta_{2}^{2}+1,$
$\displaystyle c=-(2\beta_{1}^{2}\beta_{2}^{2}+\beta_{1}^{2}+\beta_{2}^{2}),$
$\displaystyle d=\beta_{1}^{2}\beta_{2}^{2}.$

In order to prove the spectral radius of $\tilde{\mathcal{A}}_{NM}$ is larger
than 1, we just need to verify that the maximal modulus of the roots of $g$ is
larger than 1. According to Lemma A.1, the polynomial $g(\lambda)$ has a root
with modulus no less than $1$ if $|a+c|>b+d+1$. Next we want to prove that
$|a+c|>b+d+1$ holds for any step size $\eta>0$ and any momentum parameter
$\beta_{1}$, $\beta_{2}$. Computing directly,

$\displaystyle|a+c|-(b+d+1)=\ $ $\displaystyle-(a+c)-(b+d+1)$ $\displaystyle=\
$ $\displaystyle
4\eta^{4}+4\eta^{2}(\beta_{2}-\beta_{1})+\beta_{1}^{2}+\beta_{2}^{2}+2+2\beta_{1}^{2}\beta_{2}^{2}+\beta_{1}^{2}+\beta_{2}^{2}$
$\displaystyle-(4\eta^{2}(\beta_{2}-\beta_{1})+\beta_{1}^{2}\beta_{2}^{2}+2\beta_{1}^{2}+2\beta_{2}^{2}+1+\beta_{1}^{2}\beta_{2}^{2}+1)$
$\displaystyle=\ $ $\displaystyle 4\eta^{4}>0,$

where the first equality holds since

$\displaystyle a+c$
$\displaystyle=-(4\eta^{4}+4\eta^{2}(\beta_{2}-\beta_{1})+2\beta_{1}^{2}+2\beta_{2}^{2}+2+2\beta_{1}^{2}\beta_{2}^{2})$
$\displaystyle\leq-(4\eta^{4}+4\eta^{2}(\beta_{2}-\beta_{1})+(\beta_{1}-\beta_{2})^{2})$
$\displaystyle\leq-(2\eta^{2}+\beta_{2}-\beta_{1})^{2}$ $\displaystyle\leq 0.$

The inequality $|a+c|>b+d+1$ violates the second condition in Corollary A.1,
which means the maximal modulus of the roots of $g$ is at least $1$.

Next, we want to prove the maximal modulus of the roots of $g$ is strictly
larger than $1$. Assuming that the maximal modulus of the roots of $g$ is
equal to $1$, then for any given $r>1$, the roots of

$(r\lambda)^{4}+a(r\lambda)^{3}+b(r\lambda)^{2}+c(r\lambda)+d=0$

are within the (open) unit disk of the complex plane (the roots $\lambda$
satisfy $\left|r\lambda\right|\leq 1$). Divide the quartic polynomial by
$r^{4}$, we have
$\lambda^{4}+\frac{a}{r}\lambda^{3}+\frac{b}{r^{2}}\lambda^{2}+\frac{c}{r^{3}}\lambda+\frac{d}{r^{4}}=0$.
By Corollary A.1, we have the second condition for the polynomial above, that
is,

$\left|\frac{a}{r}+\frac{c}{r^{3}}\right|<\frac{b}{r^{2}}+\frac{d}{r^{4}}+1.$

Notice that the inequality above holds for any $r>1$. Let $r\to 1^{+}$, we
obtain,

$\displaystyle\left|a+c\right|\leq b+d+1$ $\displaystyle(\Leftrightarrow)$
$\displaystyle\
|4\eta^{4}+4\eta^{2}(\beta_{2}-\beta_{1})+2\beta_{1}^{2}+2\beta_{2}^{2}+2+2\beta_{1}^{2}\beta_{2}^{2}|$
$\displaystyle\leq
4\eta^{2}(\beta_{2}-\beta_{1})+2\beta_{1}^{2}+2\beta_{2}^{2}+2\beta_{1}^{2}\beta_{2}^{2}+2$
$\displaystyle(\Leftrightarrow)$ $\displaystyle\ \eta^{4}\leq 0.$

which contradicts with the step size $\eta>0$. Therefore, our assumption that
the maximal modulus of the roots of $g$ is equal to 1 cannot hold.

In conclusion, we have that the spectral radius of $\tilde{\mathcal{A}}_{NM}$
is strictly greater than $1$. ∎

Now we are ready to proof Theorem 3.2 for the part of negative momentum
method.

######  proof of Theorem 3.2, (part I, Negative Momentum).

As we have shown in Lemma C.1, $1$ and $\beta_{2}^{2}$ are two eigenvalues of
$\tilde{\mathcal{A}}_{NM}$. We claim that if
$[0,a,a,0,b,b]^{\top}\in{\mathbb{R}}^{6}$ is an eigenvector of
$\tilde{\mathcal{A}}_{NM}$, with condition $a$ and $b$ not simultaneously
equal to $0$, then it can only be an eigenvector corresponds to either $1$ or
$\beta_{2}^{2}$. In the following,we prove the above claim.

Without loss of generality, we assume that $b\neq 0$ (the case $a\neq 0$ is
similar), moreover, we can assume that $b=1$ by a normalization. Then, we have

$\displaystyle\tilde{\mathcal{A}}_{NM}\cdot\begin{bmatrix}0\\\ a\\\ a\\\ 0\\\
1\\\ 1\end{bmatrix}=\begin{bmatrix}0\\\
a(\beta_{2}^{2}+\beta_{2}+1)-\beta_{2}(\beta_{2}+1)\\\
a(\beta_{2}^{2}+\beta_{2}+1)-\beta_{2}(\beta_{2}+1)\\\ 0\\\
a(\beta_{2}+1)-\beta_{2}\\\ a(\beta_{2}+1)-\beta_{2}\end{bmatrix}$

Firstly, if $a=0$ and $[0,a,a,0,1,1]^{\top}=[0,0,0,0,1,1]^{\top}$ is an
eigenvector of $\tilde{\mathcal{A}}_{NM}$, then either $\beta_{2}=0$ or
$\beta_{2}=-1$. If $\beta_{2}=0$, then $[0,0,0,0,1,1]^{\top}$ is eigenvector
corresponding to eigenvalue $\beta_{2}^{2}$; if $\beta_{2}=-1$, then
$[0,0,0,0,1,1]^{\top}$ is eigenvector corresponding to eigenvalue $1$.

Secondly, if $a\neq 0$ and $[0,a,a,0,1,1]^{\top}$ is eigenvector of
$\tilde{\mathcal{A}}_{NM}$, then

$\displaystyle\dfrac{a(\beta_{2}^{2}+\beta_{2}+1)-\beta_{2}(\beta_{2}+1)}{a}=\dfrac{a(\beta_{2}+1)-\beta_{2}}{1}$
$\displaystyle\Rightarrow$ $\displaystyle(a-\beta_{2})(a-1)(\beta_{2}+1)=0.$

When $\beta_{2}\neq-1$, then $a=\beta_{2}$ or $a=1$, and
$[0,a,a,0,1,1]^{\top}$ is an eigenvector corresponding to eigenvalue
$\beta_{2}^{2}$ or $1$. When $\beta_{2}=-1$, $[0,1,1,0,1,1]^{\top}$ and
$[0,0,0,0,1,1]^{\top}$ are eigenvectors of $\tilde{\mathcal{A}}_{NM}$
corresponding to eigenvalue $1$. Thus we conclude for any $a$ and $b$ not
simultaneously equal to $0$, $[0,a,a,0,b,b]^{\top}$ can only be an eigenvector
of $\tilde{\mathcal{A}}_{NM}$ corresponding to eigenvalue $1$ and
$\beta^{2}_{2}$, this completes the proof of the claim.

Next we construct an initial condition that has exponential divergence rate
under negative momentum method. Let $\lambda^{\prime}$ be the eigenvalue of
$\tilde{\mathcal{A}}_{NM}$ with largest modulus except $\beta_{2}^{2}$, then
by Lemma C.1, $\lvert\lambda^{\prime}\lvert>1$. We also denote
$X_{0}=[x_{0},y_{0,1},y_{0,2},x_{-1},y_{-1,1},y_{-1,2}]^{\top}\in{\mathbb{R}}^{6}$
as the corresponding eigenvector of $\lambda^{\prime}$. Here
$y_{i}=(y_{i,1},y_{i,2})$, and $x_{i}$ for $i=0,-1$ are initial conditions.
Then from the claim proved above, one of $x_{0}$, $x_{-1}$, $y_{0,1}-y_{0,2}$
and $y_{-1,1}-y_{-1,2}$ not equals to $0$. Let $c=\max\\{\lvert
x_{0}\lvert,\lvert x_{-1}\lvert,\lvert y_{0,1}-y_{0,2}\lvert,\lvert
y_{-1,1}-y_{-1,2}\lvert\\}$, then $c>0$.

In the following, we construct the initial point by considering two cases :
$\lambda^{\prime}$ is a real number or complex number.

Firstly, we consider the case that $\lambda^{\prime}$ is a real number. We can
write the iterative process using $\tilde{\mathcal{A}}_{NM}$ as follows:

$\displaystyle
X_{2t}=\tilde{\mathcal{A}}_{NM}^{t}X_{0}=(\lambda^{\prime})^{t}X_{0}.$

which implies

$\displaystyle
x_{2t}=(\lambda^{\prime})^{t}x_{0},y_{2t,1}=(\lambda^{\prime})^{t}y_{0,1},y_{2t,2}=(\lambda^{\prime})^{t}y_{0,2},$
$\displaystyle
x_{2t-1}=(\lambda^{\prime})^{t}x_{-1},y_{2t-1,1}=(\lambda^{\prime})^{t}y_{-1,1},y_{2t-1,2}=(\lambda^{\prime})^{t}y_{-1,2}.$

Since $A_{1}=[1,-1]$, then

$\displaystyle A_{1}^{\top}x_{t}=$
$\displaystyle[x_{t},-x_{t}]^{\top},A_{1}y_{t}=y_{t,1}-y_{t,2},$
$\displaystyle\Rightarrow\Delta_{1,t}=$ $\displaystyle\lVert
A_{1}^{\top}x_{t}\lVert_{2}+\lVert A_{1}y_{t}\lVert_{2}$ $\displaystyle=$
$\displaystyle\sqrt{2}\lvert x_{t}\lvert+\lvert y_{t,1}-y_{t,2}\lvert$
$\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{c}\lvert\lambda^{\prime}\lvert^{\frac{t}{2}}(\sqrt{2}\lvert
x_{0}\lvert+\lvert y_{0,1}-y_{0,2}\lvert),\ \text{if t is even}\\\ \\\
\lvert\lambda^{\prime}\lvert^{\frac{t+1}{2}}(\sqrt{2}\lvert
x_{-1}\lvert+\lvert y_{-1,1}-y_{-1,2}\lvert),\ \text{if t is
odd}.\end{array}\right.$

Then, $\max\\{\Delta_{1,t-1},\Delta_{1,t}\\}\geq
c\lvert\lambda^{\prime}\lvert^{\frac{t}{2}}$. Let
$\lambda=\lvert\lambda^{\prime}\lvert^{\frac{1}{2}}$, we have
$\sup_{s\in[t]}\Delta_{1,s}\geq
c\lambda^{t}\in\Omega\left(\lambda^{t}\right)$. Similarly, then we have
$\sup_{s\in[t]}\Delta_{2,s}\in\Omega\left(\lambda^{t}\right)$.

Secondly, we consider $\lambda^{\prime}$ as a complex number. Denote this
eigenvalue by $a+bi$, then $a-bi$ is also an eigenvalue of
$\tilde{\mathcal{A}}_{NM}$. Denote $v$ the eigenvector of eigenvalue $a+bi$,
then $\bar{v}$ is the eigenvector of eigenvalue $a-bi$. Let $X_{0}=v+\bar{v}$.
In the following, we prove $X_{0}\neq 0$ by contradiction. Assuming $X_{0}=0$
which means $v=v^{\prime}i$, where $v^{\prime}$ is a real vector. Then,
$Av=Av^{\prime}i=(a+bi)v^{\prime}i=av^{\prime}i-bv^{\prime}$. Since $A$ is a
real matrix, then vector $Av^{\prime}i$ only consists of pure imaginary
numbers, leading to $b=0$. Then the contradiction appears since
$\lambda^{\prime}=a+bi$ is a complex number. According to previous analysis,
one of $x_{0}$, $x_{-1}$, $y_{0,1}-y_{0,2}$ and $y_{-1,1}-y_{-1,2}$ is not
$0$. Here we analyze the case when $c=\lvert y_{0,1}-y_{0,2}\lvert$ is not
equal to zero and omit other cases because these analyses are very similar.
According to the iterative process, we have

$\displaystyle X_{2t}=$ $\displaystyle\tilde{\mathcal{A}}_{NM}^{t}X_{0}$
$\displaystyle=$ $\displaystyle\tilde{\mathcal{A}}_{NM}^{t}(v+\bar{v})$
$\displaystyle=$ $\displaystyle(a+bi)^{t}v+(a-bi)^{t}\bar{v}$ $\displaystyle=$
$\displaystyle
e^{it\theta}(a^{2}+b^{2})^{\frac{t}{2}}v+e^{-it\theta}(a^{2}+b^{2})^{\frac{t}{2}}\bar{v},$

where $\theta=\textbf{sign}(b)\frac{\pi}{2}$ if $a=0$, otherwise
$\theta=\arctan(\frac{b}{a})$. Since $A_{1}=[1,-1]$, then,

$\displaystyle\lVert A_{1}y_{t}\lVert_{2}=$ $\displaystyle\lvert
y_{t,1}-y_{t,2}\lvert$ $\displaystyle=$ $\displaystyle\lvert
2c(e^{it\theta}+e^{-it\theta})(a^{2}+b^{2})^{\frac{t}{2}}\lvert$
$\displaystyle=$ $\displaystyle\lvert
4c\cdot\cos(t\theta)\lvert(a^{2}+b^{2})^{\frac{t}{2}}.$

For $\cos(t\theta)$, either $\cos(t\theta)\equiv 1$ when $\theta=0$, or
$\lim_{t\rightarrow+\infty}\cos(t\theta)$ doesn’t exist, which means there
exists a constant $\delta>0$ and $\\{t_{j}\\}_{j=1,2,\dots}$ , where
$\\{t_{j}\\}_{j=1,2,\dots}$ is a sequence that goes to infinity, such that
$\lvert\cos(t_{j}\theta)\lvert>\delta$. We know that
$\lvert\lambda^{\prime}\lvert=(a^{2}+b^{2})^{\frac{1}{2}}$, then
$\lvert\lambda^{\prime}\lvert>1$. Let
$\lambda=\lvert\lambda^{\prime}\lvert^{\frac{1}{2}}$, leading to $\lambda>1$.
In addition to $c\neq 0$, we have

$\Delta_{1,t_{j}}\geq\lVert
A_{1}y_{t_{j}}\lVert_{2}\geq\delta\lambda^{t}\in\Omega(\lambda^{t}).$

Thus $\sup_{s\in[t]}\Delta_{1,s}\in\Omega(\lambda^{t})$, and
$\sup_{s\in[t]}\Delta_{2,s}\in\Omega(\lambda^{t})$ can be proven in the same
way. ∎

###  C.3 Optimistic Gradient Descent Ascent

In this subsection, we consider optimistic gradient descent ascent with step
size $\eta$. Recall that the linear difference form of OGDA can be written as
following:

$\displaystyle\begin{bmatrix}x_{t}\\\ \\\ y_{t}\\\ \\\ x_{t-1}\\\ \\\
y_{t-1}\end{bmatrix}=\begin{bmatrix}I&-2\eta A_{t-1}&0&\eta A_{t-2}\\\ \\\
2\eta A_{t-1}^{\top}&I&-\eta A_{t-2}^{\top}&0\\\ \\\ I&0&0&0\\\ \\\
0&I&0&0\end{bmatrix}\begin{bmatrix}x_{t-1}\\\ \\\ y_{t-1}\\\ \\\ x_{t-2}\\\
\\\ y_{t-2}\end{bmatrix}.$ (18)

We denote the matrix in (18) as $\mathcal{A}_{t}$ and let
$X_{t}=(x_{t}^{\top},y_{t}^{\top},x_{t-1}^{\top},y_{t-1}^{\top})^{\top}$.
Since payoff matrix has period of $2$, by Floquet Theorem, we only have to
analyze matrix $\mathcal{A}_{t+1}\mathcal{A}_{t}$. Let
$\tilde{\mathcal{A}}_{OGDA}=\mathcal{A}_{t+1}\mathcal{A}_{t}$, then, we have

$X_{t}=\tilde{\mathcal{A}}_{OGDA}X_{t-2},\ \text{for any $t\geq 2$}.$

######  Lemma C.2.

For any step size $\eta>0$, the spectral radius of
$\tilde{\mathcal{A}}_{OGDA}$ is larger than $1$.

###### Proof.

Directly compute the characteristic polynomial
$P_{\tilde{\mathcal{A}}_{OGDA}}(\lambda)$ of matrix
$\tilde{\mathcal{A}}_{OGDA}$ gives

$\displaystyle P_{\tilde{\mathcal{A}}_{OGDA}}(\lambda)=$ $\displaystyle\
\det(\lambda I-\tilde{\mathcal{A}}_{OGDA})$ $\displaystyle=$ $\displaystyle\
\lambda\cdot(\lambda-1)\cdot\left(\lambda-\left(4\eta^{2}-\frac{1}{2}\sqrt{64\eta^{4}+8\eta^{2}+1}+\frac{1}{2}\right)\right)^{2}$
$\displaystyle\cdot\left(\lambda-\left(4\eta^{2}+\frac{1}{2}\sqrt{64\eta^{4}+8\eta^{2}+1}+\frac{1}{2}\right)\right)^{2}.$

Then, $\tilde{\mathcal{A}}_{OGDA}$ has an eigenvalue
$\lambda^{\prime}=4\eta^{2}+\frac{1}{2}\sqrt{64\eta^{4}+8\eta^{2}+1}+\frac{1}{2}$.
It is easy to verify that $\lambda^{\prime}$ is strictly monotonically
increasing with $\eta\in[0,+\infty)$, and $\lambda^{\prime}$ equals to $1$ iff
$\eta=0$. Since step size $\eta>0$, thus the spectral radius of matrix
$\tilde{\mathcal{A}}_{OGDA}$ is larger than 1. ∎

Now we are ready to prove Theorem 3.2 for the part of optimistic gradient
descent ascent method.

###### proof of Theorem 3.2, (part II, OGDA).

Let $X_{0}=[x_{0},y_{0,1},y_{0,2},x_{-1},y_{-1,1},y_{-1,2}]^{\top}$ be the
eigenvector corresponding to the eigenvalue $\lambda^{\prime}$ defined above.
Then, it is directly to verify $x_{0},x_{-1}\neq 0$.

In the iterative process, we have

$\displaystyle
X_{2t}=\tilde{\mathcal{A}}_{OGDA}^{t}X_{0}=(\lambda^{\prime})^{t}X_{0},\
x_{2t}=(\lambda^{\prime})^{t}x_{0}.$

Since $A_{1}=[1,-1]$, then

$\displaystyle A_{1}^{\top}x_{t}=$
$\displaystyle[x_{t},-x_{t}]^{\top},A_{1}y_{t}=y_{t,1}-y_{t,2}.$
$\displaystyle\Rightarrow\Delta_{1,t}=$ $\displaystyle\lVert
A_{1}^{\top}x_{t}\lVert_{2}+\lVert A_{1}y_{t}\lVert_{2}$ $\displaystyle=$
$\displaystyle\sqrt{2}\lvert x_{t}\lvert+\lvert y_{t,1}-y_{t,2}\lvert$
$\displaystyle\geq$
$\displaystyle\sqrt{2}\lambda^{\prime\frac{t}{2}}\min\\{x_{0},x_{-1}\\}.$

By Theorem C.2, $\lambda^{\prime}>1$. Let
$\lambda=(\lambda^{\prime})^{\frac{1}{2}}$, then $\lambda>1$. According to the
inequality above, we have

$\sup_{s\in[t]}\Delta_{1,s}\geq\Delta_{1,t}\geq\sqrt{2}\min\\{x_{0},x_{-1}\\}\lambda^{t}\in\Omega\left(\lambda^{t}\right).$

Similarly, we have
$\sup_{s\in[t]}\Delta_{2,s}\in\Omega\left(\lambda^{t}\right)$. ∎

##  Appendix D Proof for convergent perturbed games with invertible payoff
matrix

In this section, we provide a proof of a special case of Theorem 3.3 under the
assumption that the payoff matrix is an invertible square matrix. Furthermore,
we can demonstrate that this assumption leads to an exponential convergence
rate.

######  Proposition D.1.

When the payoff matrix $A$ of the stable game is an invertible square matrix
and $\lim_{t\to\infty}B_{t}=0$, we have
$\lim_{t\to\infty}(x_{t},y_{t})=(\boldsymbol{0},\boldsymbol{0})\in{\mathbb{R}}^{2n}$
in (OGDA), (EG), and (NM) with an exponential rate.

###### Proof.

According to Perron Theorem 2.5, we only need to prove maximum modulus of
eigenvalues of iterative matrix $\mathcal{A}$ is less than 1. Lemma A.2
indicates that if the parameter condition on step sizes is satisfied, we have
maximum modulus of eigenvalues of iterative matrix $\mathcal{A}$ is less than
1. This complete the proof. ∎

The above proof cannot be generalized to non-invertible matrices, as we have
shown in Lemma A.2 that when the payoff matrix is non-invertible, then
iterative matrices of the difference system associated with the game dynamics
must have an eigenvalue equals to $1$.

In the following, we prove Theorem 3.3 for the general case.

##  Appendix E Omitted Proofs from Theorem 3.3

See 3.3

We separate the proof into several lemmas. Before going into details, we
present a road map of the proof in Figure (7).

Figure 7: Road map for the prove of Theorem 3.3

As a first step, we demonstrate that the iterative matrices of learning
dynamics can be diagonalized using singular value decomposition (SVD), as
shown in Lemma E.2. This phenomenon was also shown in Gidel et al. [2019] for
a general class of first order method. By singular value decomposition, we can
write $A=U\Sigma_{A}V^{\top}$, where $U$, $V$ are unitary matrices, and
$\Sigma_{A}$ is rectangular diagonal matrix with its diagonal entries being
singular values of $A$. We denote this by

$\Sigma_{A}=\begin{bmatrix}\bf{\sigma_{r\times r}}&\bf{0_{r\times(m-r)}}\\\
\\\ \bf{0_{(n-r)\times r}}&\bf{0_{(n-r)\times(m-r)}}\\\
\end{bmatrix}\in{\mathbb{R}}^{n\times m},$

and

$\displaystyle\bf{\sigma_{r\times r}}=\begin{bmatrix}\sigma_{1}\\\ &\ddots&\\\
&&\sigma_{r}\\\ \end{bmatrix}\in{\mathbb{R}}^{r\times r},$

where $\sigma_{i}>0$ are the singular values of $A$, $i\in[r]$. Let
$\bar{x}_{t}=U^{\top}x_{t}$, $\bar{y}_{t}=V^{\top}y_{t}$, then we can
transform the iterative process of three algorithms in convergent perturbed
game into the equivalent form as followings :

#### SVD formulation for OGDA in convergent perturbed game:

$\displaystyle\bar{x}_{t+1}=\bar{x}_{t}-2\eta(\Sigma_{A}+U^{\top}B_{t}V)\bar{y}_{t}+\eta(\Sigma_{A}+U^{\top}B_{t-1}V)\bar{y}_{t-1},$
$\displaystyle\bar{y}_{t+1}=\bar{y}_{t}+2\eta(\Sigma_{A}+V^{\top}B_{t}^{\top}U)\bar{x}_{t}-\eta(\Sigma_{A}+V^{\top}B_{t-1}^{\top}U)\bar{x}_{t-1}.$

We represent the above in the form of a linear difference system:

$\displaystyle\bar{X}_{t+1}=(\bar{\mathcal{A}}+\bar{\mathcal{B}}_{t})\bar{X}_{t},$
(19)

where
$\bar{X}_{t}=(\bar{x}_{t}^{\top},\bar{y}_{t}^{\top},\bar{x}_{t-1}^{\top},\bar{y}_{t-1}^{\top})^{\top}$,

$\displaystyle\bar{\mathcal{A}}=\begin{bmatrix}I&-2\eta\Sigma_{A}&0&\eta\Sigma_{A}\\\
\\\ 2\eta\Sigma_{A}^{\top}&I&-\eta\Sigma_{A}^{\top}&0\\\ \\\ I&0&0&0\\\ \\\
0&I&0&0\end{bmatrix}\in{\mathbb{R}}^{2(m+n)},$ (20)

and

$\displaystyle\bar{\mathcal{B}}_{t}=\begin{bmatrix}0&-2\eta
U^{\top}B_{t}V&0&\eta U^{\top}B_{t-1}V\\\ \\\ 2\eta
V^{\top}B^{\top}_{t}U&0&-\eta V^{\top}B_{t-1}^{\top}U&0\\\ \\\ 0&0&0&0\\\ \\\
0&0&0&0\end{bmatrix}\in{\mathbb{R}}^{2(m+n)}.$ (21)

#### SVD formulation for EG in convergent perturbed game:

$\displaystyle\bar{x}_{t+1}=(I-\alpha\gamma(\Sigma_{A}\Sigma_{A}^{\top}+U^{\top}(AB_{t}^{\top}+B_{t}A^{\top}+B_{t}B_{t}^{\top})U)\bar{x}_{t}-\alpha(\Sigma_{A}+U^{\top}B_{t}V)\bar{y}_{t},$
$\displaystyle\bar{y}_{t+1}=(I-\alpha\gamma(\Sigma_{A}^{\top}\Sigma_{A}+V^{\top}(A^{\top}B_{t}+B_{t}^{\top}A+B_{t}^{\top}B_{t})V)\bar{y}_{t}+\alpha(\Sigma_{A}^{\top}+V^{\top}B_{t}^{\top}U)\bar{x}_{t}.$

We represent the above in the form of a linear difference system:

$\displaystyle\bar{X}_{t+1}=(\bar{\mathcal{A}}+\bar{\mathcal{B}}_{t})\bar{X}_{t},$
(22)

where $\bar{X}_{t}=(\bar{x}_{t}^{\top},\bar{y}_{t}^{\top})$,

$\displaystyle\bar{\mathcal{A}}=\begin{bmatrix}I-\alpha\gamma\Sigma_{A}\Sigma_{A}^{\top}&-\alpha\Sigma_{A}\\\
\\\ \\\ \alpha\Sigma_{A}^{\top}&I-\alpha\gamma\Sigma_{A}^{\top}\Sigma_{A}\\\
\end{bmatrix}\in{\mathbb{R}}^{m+n}$ (23)

and

$\displaystyle\bar{\mathcal{B}}_{t}=\begin{bmatrix}-\alpha\gamma
U^{\top}(AB_{t}^{\top}+B_{t}A^{\top}+B_{t}B_{t}^{\top})U&-\alpha
U^{\top}B_{t}V\\\ \\\ \\\ \alpha V^{\top}B_{t}^{\top}U&\alpha\gamma
V^{\top}(A^{\top}B_{t}+B_{t}^{\top}A+B_{t}^{\top}B_{t})V\end{bmatrix}.$ (24)

#### SVD formulation for NM in convergent perturbed game:

$\displaystyle\bar{x}_{t+1}$ $\displaystyle=\
(1+\beta_{1})\bar{x}_{t}-\eta\left(\Sigma_{A}+U^{\top}B_{t}V\right)\bar{y}_{t}-\beta_{1}\bar{x}_{t-1},$
$\displaystyle\bar{y}_{t+1}$ $\displaystyle=\
\left(I-\eta^{2}\left(\Sigma_{A}^{\top}\Sigma_{A}+V^{\top}(A^{\top}B_{t}+B_{t+1}^{\top}A+B_{t+1}^{\top}B_{t})V\right)\right)\bar{y}_{t}$
$\displaystyle+\eta\left(\Sigma_{A}^{\top}+V^{\top}B_{t+1}^{\top}U\right)\left((1+\beta_{1})\bar{x}_{t}-\beta_{1}\bar{x}_{t-1}\right)-\beta_{2}\bar{y}_{t-1}.$

We represent the above in the form of a linear difference system:

$\displaystyle\bar{X}_{t+1}=(\bar{\mathcal{A}}+\bar{\mathcal{B}}_{t})\bar{X}_{t},$
(25)

where
$\bar{X}_{t}=(\bar{x}_{t}^{\top},\bar{y}_{t}^{\top},\bar{x}_{t-1}^{\top},\bar{y}_{t-1}^{\top})^{\top}$,

$\displaystyle\bar{\mathcal{A}}=\begin{bmatrix}(1+\beta_{1})I&&-\eta\Sigma_{A}&&-\beta_{1}I&&0\\\
\\\
\eta(1+\beta_{1})\Sigma_{A}^{\top}&&I-\eta^{2}\Sigma_{A}^{\top}\Sigma_{A}&&-\eta\beta_{1}\Sigma_{A}^{\top}&&-\beta_{2}I\\\
\\\ I&&0&&0&&0\\\ \\\ 0&&I&&0&&0\end{bmatrix}\in{\mathbb{R}}^{2(m+n)},$ (26)

and

$\displaystyle\bar{\mathcal{B}}_{t}=\begin{bmatrix}0&-\eta
U^{\top}B_{t}V&0&&0\\\ \\\
\eta(1+\beta_{1})V^{\top}B^{\top}_{t+1}U&-\eta^{2}V^{\top}(A^{\top}B_{t}+B_{t+1}^{\top}A+B_{t+1}^{\top}B_{t})V&-\eta\beta_{1}V^{\top}B^{\top}_{t+1}U&&0\\\
\\\ 0&0&0&&0\\\ \\\ 0&0&0&&0\end{bmatrix}.$ (27)

######  Lemma E.1.

The iterative matrix of SVD formulation for EG in convergent perturbed game in
(23) is a normal matrix.

###### Proof.

Directly calculate shows

$\displaystyle\bar{\mathcal{A}}\bar{\mathcal{A}}^{\top}=\bar{\mathcal{A}}^{\top}\bar{\mathcal{A}}=\begin{bmatrix}(I-\alpha\gamma\Sigma_{A}\Sigma_{A}^{\top})^{2}+\alpha^{2}\Sigma_{A}\Sigma_{A}^{\top}&0\\\
\\\
0&(I-\alpha\gamma\Sigma_{A}^{\top}\Sigma_{A})^{2}+\alpha^{2}\Sigma_{A}^{\top}\Sigma_{A}\end{bmatrix}.$
(28)

∎

######  Lemma E.2.

For a fixed payoff matrix $A$, the corresponding iterative matrices in (20)
for OGDA, (23) for EG, and (26) for negative momentum method are
diagonalizable.

Note that the claim is true for EG since the iterative matrix is normal as we
have shown in lemma E.1. Therefore, we will only consider the cases of OGDA
and negative momentum method below. The idea behind proving these two claims
is the same, we construct a set of linearly independent eigenvectors of (20)
or (26) that form a basis of ${\mathbb{R}}^{2(m+n)}$, and under this basis,
(20) or (26) can be represented by a diagonal matrix.

###### Proof.

We firstly define some notation. In the following, we denote $e_{i}^{n}$ as an
$n$-dimensional unit vector with 1 in the $i$-th position and 0 in other
positions and denote $\sigma_{p}$ as the $p$-th singular value of the payoff
matrix $A$ of the stable game, and denote $r$ as the rank of $A$. Thus for
$p\in[r]$, $\sigma_{p}>0$, and otherwise $\sigma_{p}=0$. We will also denote
the $n$-dimensional ($m$-dimensional) zero vector as $0^{n}(0^{m})$.

#### Part I, Diagonalization of (20):

Now we consider the diagonalization of matrix in $\eqref{SVD-OGDA}$. Recall
that

$\Sigma_{A}=\begin{bmatrix}\bf{\sigma_{r\times r}}&\bf{0_{r\times(m-r)}}\\\
\\\ \bf{0_{(n-r)\times r}}&\bf{0_{(n-r)\times(m-r)}}\\\
\end{bmatrix}\in{\mathbb{R}}^{n\times m},$

and

$\displaystyle\bf{\sigma_{r\times r}}=\begin{bmatrix}\sigma_{1}\\\ &\ddots&\\\
&&\sigma_{r}\\\ \end{bmatrix}\in{\mathbb{R}}^{r\times r}.$

To prove $\bar{\mathcal{A}}$ is diagonalizable, we only need to find $2(n+m)$
linearly independent eigenvectors of the matrix.

Then we can check the equations below

$\displaystyle\begin{cases}\Sigma_{A}e_{p}^{m}=\sigma_{p}e_{p}^{n},&\text{for
$1\leq p\leq r$},\\\ \\\ \Sigma_{A}e_{j}^{m}=0^{n},&\text{for $r+1\leq j\leq
m$},\end{cases}$

and

$\displaystyle\begin{cases}\Sigma_{A}^{\top}e_{p}^{n}=\sigma_{p}e_{p}^{m},&\text{for
$1\leq p\leq r$},\\\ \\\ \Sigma_{A}^{\top}e_{i}^{n}=0^{m},&\text{for $r+1\leq
i\leq n$}.\end{cases}$

Now we respectively construct the eigenvectors corresponding to each
eigenvalue, and prove these $2(n+m)$ vectors are linearly independent, forming
a basis of ${\mathbb{R}}^{2(n+m)}$.

  1. Case 1

Eigenvectors correspond to eigenvalue 1 :
It can be verified that for $r+1\leq i\leq n$

$\displaystyle v_{1,i}=\begin{bmatrix}e_{i}^{n}\\\ \\\ 0^{m}\\\ \\\ 0^{n}\\\
\\\ 0^{m}\end{bmatrix},$

and for $r+1\leq j\leq m$

$\displaystyle w_{1,j}=\begin{bmatrix}0^{n}\\\ \\\ e_{j}^{m}\\\ \\\ 0^{n}\\\
\\\ 0^{m}\end{bmatrix}$

are eigenvectors of $\bar{\mathcal{A}}$ belonging to eigenvalue 1.

  2. Case 2

Eigenvectors correspond to eigenvalue 0 :
It can be verified that for $r+1\leq i\leq n$,

$\displaystyle v_{0,i}=\begin{bmatrix}0^{n}\\\ \\\ 0^{m}\\\ \\\ e_{i}^{n}\\\
\\\ 0^{m}\end{bmatrix}$

and for $r+1\leq j\leq m$,

$\displaystyle w_{0,j}=\begin{bmatrix}0^{n}\\\ \\\ 0^{m}\\\ \\\ 0^{n}\\\ \\\
e_{j}^{m}\end{bmatrix}$

are eigenvectors of $\bar{\mathcal{A}}$ belonging to eigenvalue 0.

  3. Case 3

Other eigenvectors :
For $p=1,\cdots,r$, consider the roots of the following polynomial :

$\displaystyle\lambda^{2}(\lambda-1)^{2}+\eta^{2}\sigma_{p}^{2}(1-2\lambda)^{2}=0$
(29)

where $\sigma_{p}$ is the $p$-th diagonal element of $\Sigma_{A}$, and the
solution of these polynomials are eigenvalues of $\bar{\mathcal{A}}$.

We first claim that except for finite choices of $\eta$, equation (29) has
four different non-zero roots, denote them as $\lambda_{p,q}$, $q=1,2,3,4$.
That is because a quartic polynomial equation has multiple roots if and only
if its discriminant polynomial, a homogeneous polynomial with degree $6$ on
the coefficients of the quartic polynomial equation, equals to $0$. Since a
degree $6$ polynomial has at most $6$ roots, thus if $\eta$ is not a root of
this discriminant polynomial, (29) will not have multiple roots. In the
following, we will choose $\eta$ such that (29) has no multiple roots.
According to Lemma A.2, the modulus of these eigenvalues are less than 1.

Let

$\alpha_{p,q}=\frac{\eta\sigma_{p}(1-2\lambda_{p,q})}{{\lambda_{p,q}}^{2}-\lambda_{p,q}}.$

It can be verified that for $1\leq p\leq r$ and $q=1,2,3,4$,

$\displaystyle u_{p,q}=\begin{bmatrix}\lambda_{p,q}\alpha_{p,q}e_{p}^{n}\\\
\\\ \lambda_{p,q}e_{p}^{m}\\\ \\\ \alpha_{p,q}e_{p}^{n}\\\ \\\
e_{p}^{m}\end{bmatrix}$

are the eigenvectors of $\bar{\mathcal{A}}$ corresponding to eigenvalue
$\lambda_{p,q}$.

Then we have constructed $2(n+m)$ eigenvectors, now we prove they are linearly
independent. Suppose there exists coefficients $k_{1,i},k_{0,i}$, where
$i=r+1,\cdots,n$ , $g_{1,j},g_{0,j}$, where $j=r+1,\cdots,m$ and $f_{p,q}$,
where $p=1,\cdots,r$ and $q=1,2,3,4$, such that

$\displaystyle\sum_{i=r+1}^{n}k_{1,i}v_{1,i}+\sum_{j=r+1}^{m}g_{1,j}w_{1,j}+\sum_{i=r+1}^{n}k_{0,i}v_{0,i}+\sum_{j=r+1}^{m}g_{0,j}w_{0,j}+\sum_{p=1}^{r}\sum_{q=1}^{4}f_{p,q}u_{p,q}=0.$
(30)

For $r+1\leq i\leq n$, only $v_{1,i}$ has non-zero element at the $i$-th
position of vector, so $k_{1,i}=0$.

For $r+1\leq j\leq m$, only $w_{1,j}$ has non-zero element at the $(j+n)$-th
position of vector, so $g_{1,j}=0$.

For $r+1\leq i\leq n$, only $v_{0,i}$ has non-zero element at the $(i+n+m)$-th
position of vector, so $k_{0,i}=0$.

For $r+1\leq j\leq m$, only $w_{0,j}$ has non-zero element at the
$(j+2n+m)$-th position of vector, so $g_{0,j}=0$.

For $1\leq p\leq r$, at the $p$-th position of vector, only $u_{p,q}$, where
$q=1,2,3,4$ has non-zero element. So we can yield

$\displaystyle\sum_{q=1}^{4}f_{p,q}u_{p,q}=0.$

The above equation holds for $p=1,\cdots,r$. Because the eigenvectors of
different eigenvalues are linearly independent, we have $f_{p,q}=0$, where
$q=1,2,3,4$ and $p=1,\cdots,r$. Now we have concluded that all coefficients in
(LABEL:OGDAsum0) are zero, thus these eigenvectors are linearly independent.

Let $P$ be the matrix whose columns are consisted by the eigenvectors of
$\bar{\mathcal{A}}$ constructed above, and $D$ be the diagonal matrix whose
diagonal elements are eigenvalues of $\bar{\mathcal{A}}$. After an appropriate
order arrangement of columns on $P$ and elements on $D$, we have

$\displaystyle\bar{\mathcal{A}}P=PD.$

Moreover, as we have shown above, the columns of $P$ are linearly independent,
therefore $P$ is invertible, which implies $\bar{\mathcal{A}}$ is
diagonalizable.

#### Part II, Diagonalization of (26):

Now we consider the diagonalization of the matrix in $(\ref{SVD-NM})$ and
denote it as $\bar{\mathcal{A}}$. Similiarly, to prove this matrix is
diagonalizable, we only need to find $2(n+m)$ linearly independent
eigenvectors of the matrix. Now we respectively construct the eigenvectors
corresponding to each eigenvalue, and prove these $2(n+m)$ vectors are
linearly independent, forming a basis of ${\mathbb{R}}^{2(n+m)}$.

  1. Case 1:

Eigenvectors correspond to eigenvalue 1 :
It can be verified that for $r+1\leq i\leq n$,

$\displaystyle v_{1,i}=\begin{bmatrix}e_{i}^{n}\\\ \\\ 0^{m}\\\ \\\
e_{i}^{n}\\\ \\\ 0^{m}\end{bmatrix}$

and for $r+1\leq j\leq m$,

$\displaystyle w_{1,j}=\begin{bmatrix}0^{n}\\\ \\\ e_{j}^{m}\\\ \\\ 0^{n}\\\
\\\ e_{j}^{m}\end{bmatrix}$

are eigenvectors of $\bar{\mathcal{A}}$ belonging to eigenvalue 1.

  2. Case 2:

Eigenvectors correspond to eigenvalue $\beta_{1}$.
It can be verified that for $r+1\leq i\leq n$,

$\displaystyle v_{\beta_{1},i}=\begin{bmatrix}\beta_{1}e_{i}^{n}\\\ \\\
0^{m}\\\ \\\ e_{i}^{n}\\\ \\\ 0^{m}\end{bmatrix}$

are eigenvectors of $\bar{\mathcal{A}}$ corresponding to eigenvalue
$\beta_{1}$.

  3. Case 3:

Eigenvectors correspond to eigenvalue $\beta_{2}$.
It can be verified that for $r+1\leq j\leq m$,

$\displaystyle w_{\beta_{2},j}=\begin{bmatrix}0^{n}\\\ \\\
\beta_{2}e_{j}^{m}\\\ \\\ 0^{n}\\\ \\\ e_{j}^{m}\end{bmatrix}$

are eigenvectors of $\bar{\mathcal{A}}$ corresponding to eigenvalue
$\beta_{2}$.

  4. Case 4:

Other eigenvectors.
For $p=1,\cdots,r$, consider four roots of polynomial

$\displaystyle(\lambda-1)^{2}(\lambda-\beta_{1})(\lambda-\beta_{2})+\eta^{2}\sigma_{p}^{2}\lambda^{3}=0$
(31)

where $\sigma_{p}$ is the $p$-th diagonal element of $\Sigma_{A}$.

Now we consider the effect of different value of $\beta_{1}$ and $\beta_{2}$.
If $\beta_{1}=0$ and $\beta_{2}=0$, the model degenerates to gradient descent
algorithm, we only consider when $\beta_{1}$ and $\beta_{2}$ are not both
zero. Similar to the situation in the Case 3 of diagonalization of (20),
except for several values for $\eta$, equation (31) has four different roots,
denote them as $\lambda_{p,q}$, $q=1,2,3,4$. If $\lambda_{p,q}\neq 0$, for
$q=1,2,3,4$, let

$\displaystyle\alpha_{p,q}=\frac{-{\lambda_{p,q}}^{2}+(1+\beta_{1})\lambda_{p,q}-\beta_{1}}{\eta\sigma_{p}\lambda_{p,q}}.$

We can check that

$\displaystyle u_{p,q}=\begin{bmatrix}\lambda_{p,q}e_{p}^{n}\\\ \\\
\lambda_{p,q}\alpha_{p,q}e_{p}^{m}\\\ \\\ e_{p}^{n}\\\ \\\
\alpha_{p,q}e_{p}^{m}\end{bmatrix}$

is the eigenvector of $\bar{\mathcal{A}}$ corresponding to eigenvalue
$\lambda_{p,q}$, that is $\bar{\mathcal{A}}u_{p,q}=\lambda_{p,q}u_{p,q}$. Else
if $\lambda_{p,q}=0$, that means either $\beta_{1}=0$ or $\beta_{2}=0$.

If $\beta_{1}=0$,

$\displaystyle u_{p,q}=\begin{bmatrix}0^{n}\\\ \\\ 0^{m}\\\ \\\ e_{p}^{n}\\\
\\\ 0^{m}\end{bmatrix}$

is the eigenvector of $\bar{\mathcal{A}}$ corresponding to eigenvalue $0$.

If $\beta_{2}=0$,

$\displaystyle u_{p,q}=\begin{bmatrix}0^{n}\\\ \\\ 0^{m}\\\ \\\ 0^{n}\\\ \\\
e_{p}^{m}\end{bmatrix}$

is the eigenvector of $\bar{\mathcal{A}}$ corresponding to eigenvalue $0$.

Now we obtain $2(n+m)$ eigenvectors, in the following we will prove these
$2(n+m)$ eigenvectors are linearly independent. Suppose there exists
coefficients $k_{1,i},k_{\beta_{1},i}$, where $i=r+1,\cdots,n$ ,
$g_{1,j},g_{\beta_{2},j}$, where $j=r+1,\cdots,m$ and $f_{p,q}$, where
$p=1,\cdots,r$ and $q=1,2,3,4$, such that

$\displaystyle\sum_{i=r+1}^{n}k_{1,i}v_{1,i}+\sum_{j=r+1}^{m}g_{1,j}w_{1,j}+\sum_{i=r+1}^{n}k_{\beta_{1},i}v_{\beta_{1},i}+\sum_{j=r+1}^{m}g_{\beta_{2},j}v_{\beta_{2},j}+\sum_{p=1}^{r}\sum_{q=1}^{4}f_{p,q}u_{p,q}=0.$
(32)

First we prove $f_{p,q}=0$ for $p=1,\cdots,r$ and $q=1,2,3,4$. If
$\beta_{1}=0$, let $l=1,\cdots,r$, then at the $l+n+m$-th position of vector,
only $u_{l,q}$, $q=1,2,3,4$ has non-zero element. Else if $\beta_{1}\neq 0$,
let $l=1,\cdots,r$, then at the $l+2n+m$-th position of vector, only
$u_{l,q}$, $q=1,2,3,4$ has non-zero element. For these two case we both have

$\displaystyle\sum_{q=1}^{4}f_{p,q}u_{p,q}=0.$

The above equation holds for $p=1,\cdots,r$. Because the eigenvectors of
different eigenvalues are linearly independent, we have $f_{p,q}=0$, where
$q=1,2,3,4$ and $p=1,\cdots,r$.

For $i=r+1,\cdots,n$, at the $i$-th position of vector, only $v_{1,i}$ and
$v_{\beta_{1},i}$ has non-zero element at this position, so we obtain

$\displaystyle k_{1,i}v_{1,i}+k_{\beta_{1},i}v_{\beta_{1},i}=0.$

Notice that $\beta_{1}\neq 1$, this means $k_{1,i}=0$ and $k_{\beta_{1},i}=0$,
where $i=r+1,\cdots,n$.

For $j=r+1,\cdots,m$, at the $j$-th position of vector, only $w_{1,j}$ and
$w_{\beta_{2},j}$ has non-zero element, so we can yield

$\displaystyle g_{1,j}w_{1,j}+g_{\beta_{2},j}w_{\beta_{2},j}=0.$

Similarly, because of $\beta_{2}\neq 1$, this means $g_{1,j}=0$ and
$g_{\beta_{2},j}=0$, where $j=r+1,\cdots,m$.

We prove that if $\eqref{sum0}$ holds, then all coefficients are zero, which
illustrates that these eigenvectors are linearly independent. Same as the
argument in Part $I$ of the proof, the existence of these $2(m+n)$
eigenvectors implies $\bar{\mathcal{A}}$ is diagonalizable.

∎

######  Remark E.3.

For payoff matrix $A$, given its SVD decomposition $A=U\Sigma_{A}V^{\top}$,
let

$\displaystyle Q=\begin{bmatrix}U&&&\\\ &V&&\\\ &&U&\\\ &&&V\end{bmatrix},$

then $Q$ is a unitary matrix. Furthermore, it can be verified that

$\displaystyle Q^{\top}\mathcal{A}Q=\bar{\mathcal{A}}$

for both OGDA and negative momentum method. That means

  1. 1.

${\bar{\mathcal{A}}}$ in (20) is diagonalizable implies that ${\mathcal{A}}$
in (8) is diagonalizable.

  2. 2.

${\bar{\mathcal{A}}}$ in (26) is diagonalizable implies that ${\mathcal{A}}$
in (11) is diagonalizable.

######  Lemma E.4 (Gronwall inequality, Colonius and Kliemann [2014]).

Let for all $t\in{\mathbb{N}}$, the functions
$u,p,q,f:{\mathbb{N}}\to{\mathbb{R}}$ satisfy

$u(t)\leq p(t)+q(t)\sum^{t-1}_{\ell=a}f(\ell)u(\ell).$

Then, for all $t\in{\mathbb{N}}$

$\displaystyle u(t)\leq
p(t)+q(t)\sum^{t-1}_{\ell=a}p(\ell)f(\ell)\prod^{k-1}_{\tau=\ell+1}(1+q(\tau)f(\tau)).$
(Gronwall inequality)

Gronwall inequality is a useful tool to treat linear difference equations, it
also has an analogy in continuous time case. For more about Gronwall
inequality, see Lemma 6.1.3 in Colonius and Kliemann [2014].

######  Lemma E.5.

If $\\{B_{t}\\}_{t}$ satisfy the BAP assumption, i.e.,
$\sum^{\infty}_{t=1}\lVert B_{t}\lVert_{2}$ is bounded, then
$\\{\bar{\mathcal{B}}_{t}\\}_{t}$ defined in (21), (24) and (27) also satisfy
BAP assumption.

###### Proof.

We claim there exists some constant $c$, such that for any $t$,
$\lVert\bar{\mathcal{B}}_{t-1}\lVert_{2}\leq
c\left(\lVert{B}_{t}\lVert_{2}+\lVert{B}_{t}\lVert_{2}+\lVert{B}_{t+1}\lVert_{2}\right)$.
With this property, we have

$\displaystyle\sum_{t=0}^{\infty}\lVert\bar{\mathcal{B}}_{t}\lVert_{2}\leq
3c\sum_{t=0}^{\infty}\lVert B_{t}\lVert_{2}<+\infty,$

then we prove the statement. In the following, we prove above claim for OGDA,
EG, and negative momentum method.

#### Case of OGDA :

We consider the matrix $\eqref{B-OGDA}$

$\displaystyle\bar{\mathcal{B}}_{t}=$ $\displaystyle\begin{bmatrix}0&-2\eta
U^{\top}B_{t}V&0&\eta U^{\top}B_{t-1}V\\\ \\\ 2\eta
V^{\top}B^{\top}_{t}U&0&-\eta V^{\top}B_{t-1}^{\top}U&0\\\ \\\ 0&0&0&0\\\ \\\
0&0&0&0\end{bmatrix}$
$\displaystyle=2\eta\begin{bmatrix}0&-U^{\top}B_{t}V&0&&0\\\ \\\
V^{\top}B^{\top}_{t}U&0&0&&0\\\ \\\ 0&0&0&&0\\\ \\\
0&0&0&&0\end{bmatrix}+\eta\begin{bmatrix}0&&0&0&U^{\top}B_{t-1}V\\\ \\\
0&&0&-V^{\top}B_{t-1}^{\top}U&0\\\ \\\ 0&&0&0&0\\\ \\\ 0&&0&0&0\end{bmatrix}.$

Denote the first matrix in right side of the equation as $H_{1}$, and the
second one as $H_{2}$. From the above equation, we can obtain that
$\lVert\bar{\mathcal{B}}_{t}\lVert_{2}\leq\lVert H_{1}\lVert_{2}+\lVert
H_{2}\lVert_{2}$. Recall the definition of 2-norm of matrix,

$\displaystyle\lVert
H_{1}\lVert_{2}=\max\sqrt{\text{Eigenvalue}\\{H_{1}^{\top}H_{1}\\}},$
$\displaystyle\lVert
H_{2}\lVert_{2}=\max\sqrt{\text{Eigenvalue}\\{H_{2}^{\top}H_{2}\\}},$

then,

$\displaystyle
H_{1}^{\top}H_{1}=4\eta^{2}\begin{bmatrix}U^{\top}B_{t}B^{\top}_{t}U&0&0&&0\\\
\\\ 0&V^{\top}B^{\top}_{t}B_{t}V&0&&0\\\ \\\ 0&0&0&&0\\\ \\\
0&0&0&&0\end{bmatrix}$

and

$\displaystyle H_{2}^{\top}H_{2}=\eta^{2}\begin{bmatrix}0&&0&0&0\\\ \\\
0&&0&0&0\\\ \\\ 0&&0&U^{\top}B_{t-1}B^{\top}_{t-1}U&0\\\ \\\
0&&0&0&V^{\top}B^{\top}_{t-1}B_{t-1}V\end{bmatrix}.$

Because $U$ and $V$ are unitary matrices, we have

$\displaystyle\lVert
H_{1}\lVert_{2}=\max\sqrt{\text{Eigenvalue}\\{H_{1}^{\top}H_{1}\\}}=4\eta^{2}\max\sqrt{\text{Eigenvalue}\\{B_{t}^{\top}B_{t}\\}}=4\eta^{2}\lVert
B_{t}\lVert_{2}$

and

$\displaystyle\lVert
H_{2}\lVert_{2}=\max\sqrt{\text{Eigenvalue}\\{H_{2}^{\top}H_{2}\\}}=\eta^{2}\max\sqrt{\text{Eigenvalue}\\{B_{t-1}^{\top}B_{t-1}\\}}=\eta^{2}\lVert
B_{t-1}\lVert_{2}.$

Let $c=4\eta^{2}$, then

$\displaystyle\lVert\bar{\mathcal{B}}_{t}\lVert_{2}\leq c\cdot(\lVert
B_{t}\lVert_{2}+\lVert B_{t-1}\lVert_{2}),$

we have completed the proof for OGDA.

#### Case of EG :

We consider the matrix $\eqref{B-EG}$

$\displaystyle\bar{\mathcal{B}}_{t}=$
$\displaystyle\begin{bmatrix}-\alpha\gamma
U^{\top}(AB_{t}^{\top}+B_{t}A^{\top}+B_{t}B_{t}^{\top})U&-\alpha
U^{\top}B_{t}V\\\ \\\ \alpha V^{\top}B_{t}^{\top}U&\alpha\gamma
V^{\top}(A^{\top}B_{t}+B_{t}^{\top}A+B_{t}^{\top}B_{t})V\end{bmatrix}$
$\displaystyle=$ $\displaystyle\begin{bmatrix}-\alpha\gamma
U^{\top}(AB_{t}^{\top}+B_{t}A^{\top}+B_{t}B_{t}^{\top})U&0\\\ \\\
0&0\end{bmatrix}$ $\displaystyle+\begin{bmatrix}0&0\\\ \\\ 0&\alpha\gamma
V^{\top}(A^{\top}B_{t}+B_{t}^{\top}A+B_{t}^{\top}B_{t})V\end{bmatrix}$
$\displaystyle+\begin{bmatrix}0&-\alpha U^{\top}B_{t}V\\\ \\\
0&0\end{bmatrix}+\begin{bmatrix}0&0\\\ \\\ \alpha
V^{\top}B_{t}^{\top}U&0\end{bmatrix}.$

We separate $\mathcal{B}_{1}$ into four matrices and denote these matrices in
right side of the equation as $H_{1}$, $H_{2}$, $H_{3}$ and $H_{4}$,
respectively. Then

$\displaystyle\lVert\bar{\mathcal{B}}_{t}\lVert_{2}\leq\lVert
H_{1}\lVert_{2}+\lVert H_{2}\lVert_{2}+\lVert H_{3}\lVert_{2}+\lVert
H_{4}\lVert_{2}.$

Since $\sum_{t=1}^{\infty}\lVert B_{t}\lVert_{2}\leq c$, then $\lVert
B_{t}\lVert_{2}\leq c$ for any $t$. We also assume that $c_{2}=\lVert
A\lVert_{2}$.

Then we have,

$\displaystyle\lVert H_{1}\lVert_{2}=$ $\displaystyle\alpha\gamma\lVert
U^{\top}(AB_{t}^{\top}+B_{t}A^{\top}+B_{t}B_{t}^{\top})U\lVert_{2}$
$\displaystyle=$ $\displaystyle\alpha\gamma\left(\lVert
AB_{t}^{\top}+B_{t}A^{\top}+B_{t}B_{t}^{\top}\lVert_{2}\right)$
$\displaystyle\leq$ $\displaystyle\alpha\gamma\left(\lVert A\lVert_{2}\lVert
B_{t}\lVert_{2}+\lVert A\lVert_{2}\lVert B_{t}\lVert_{2}+\lVert
B_{t}\lVert_{2}\lVert B_{t}\lVert_{2}\right)$ $\displaystyle\leq$
$\displaystyle\alpha\gamma(2c_{2}+c)\lVert B_{t}\lVert_{2},$

where the second equality is due to $U$ is unitary matrix. Similarly, $\lVert
H_{2}\lVert_{2}\leq\alpha\gamma(2c_{2}+c)\lVert B_{t}\lVert_{2}$. In addition,
$\lVert H_{3}\lVert_{2}=\lVert H_{4}\lVert_{2}=\alpha\lVert B_{t}\lVert_{2}$.

Thus for any $t$, we have the inequality between
$\lVert\bar{\mathcal{B}}_{t}\lVert_{2}$ and $\lVert B_{t}\lVert_{2}$:

$\displaystyle\lVert\bar{\mathcal{B}}_{t}\lVert_{2}\leq\lVert
H_{1}\lVert_{2}+\lVert H_{2}\lVert_{2}+\lVert H_{3}\lVert_{2}+\lVert
H_{4}\lVert_{2}\leq\alpha\left((4c_{2}+c)\gamma+2\right)\lVert
B_{t}\lVert_{2}.$

Let $c_{1}=c(4c_{2}+c)\gamma+2c$, summing the above inequality over $t$, we
have

$\displaystyle\sum_{t=1}^{\infty}\lVert\bar{\mathcal{B}}_{t}\lVert_{2}\leq\left((4c_{2}+c)\gamma+2\right)\sum_{t=1}^{\infty}\lVert
B_{t}\lVert_{2}\leq c\left((4c_{2}+c)\gamma+2\right)=c_{1}.$

#### Case of Negative Momentum Method :

We consider the matrix (27) ,

$\displaystyle\bar{\mathcal{B}}_{t}=$ $\displaystyle\begin{bmatrix}0&-\eta
U^{\top}B_{t}V&0&&0\\\ \\\
\eta(1+\beta_{1})V^{\top}B^{\top}_{t+1}U&-\eta^{2}V^{\top}(A^{\top}B_{t}+B_{t+1}^{\top}A+B_{t+1}^{\top}B_{t})V&-\eta\beta_{1}V^{\top}B^{\top}_{t+1}U&&0\\\
\\\ 0&0&0&&0\\\ \\\ 0&0&0&&0\end{bmatrix}$
$\displaystyle=\begin{bmatrix}0&0&0&0\\\ \\\
\eta(1+\beta_{1})V^{\top}B^{\top}_{t}U&0&0&0\\\ \\\ 0&0&0&0\\\ \\\
0&0&0&0\end{bmatrix}+\begin{bmatrix}0&-\eta U^{\top}B_{t}V&0&0\\\ \\\
0&0&-\eta\beta_{1}V^{\top}B^{\top}_{t+1}U&0\\\ \\\ 0&0&0&0\\\ \\\
0&0&0&0\end{bmatrix}$ $\displaystyle+\begin{bmatrix}0&0&0&0\\\ \\\
0&-\eta^{2}V^{\top}(A^{\top}B_{t}+B_{t+1}^{\top}A+B_{t+1}^{\top}B_{t})V&0&0\\\
\\\ 0&0&0&0\\\ \\\ 0&0&0&0\end{bmatrix}.$

Denote the first matrix at the right side of equation as $H_{1}$, the second
one as $H_{2}$ and the third as $H_{3}$. Then we have
$\lVert\bar{\mathcal{B}}_{t}\lVert_{2}\leq\lVert H_{1}\lVert_{2}+\lVert
H_{2}\lVert_{2}+\lVert H_{3}\lVert_{2}$.

By definition,

$\displaystyle\lVert
H_{1}\lVert_{2}=\max\sqrt{\text{Eigenvalue}\\{H_{1}^{\top}H_{1}\\}},$
$\displaystyle\lVert
H_{2}\lVert_{2}=\max\sqrt{\text{Eigenvalue}\\{H_{2}^{\top}H_{2}\\}}.$

Because $U$ and $V$ are unitary matrices,

$\displaystyle
H_{1}^{\top}H_{1}=\eta^{2}(1+\beta_{1})^{2}\begin{bmatrix}U^{\top}B_{t}B^{\top}_{t}U&0&0&0\\\
0&0&0&0\\\ 0&0&0&0\\\ 0&0&0&0\end{bmatrix}$ $\displaystyle\Rightarrow$
$\displaystyle\max\sqrt{\text{Eigenvalue}\\{H_{1}^{\top}H_{1}\\}}=\eta^{2}(1+\beta_{1})^{2}\max\sqrt{\text{Eigenvalue}\\{B_{t}^{\top}B_{t}\\}}$
$\displaystyle\Rightarrow$ $\displaystyle\lVert
H_{1}\lVert_{2}=\eta^{2}(1+\beta_{1})^{2}\lVert B_{t}\lVert_{2}$

and

$\displaystyle H_{2}^{\top}H_{2}=\eta^{2}\begin{bmatrix}0&0&0&0\\\
0&V^{\top}B^{\top}_{t}B_{t}V&0&0\\\
0&0&\beta_{1}^{2}U^{\top}B_{t+1}B^{\top}_{t+1}U&0\\\ 0&0&0&0\end{bmatrix}$
$\displaystyle\Rightarrow$
$\displaystyle\max\sqrt{\text{Eigenvalue}\\{H_{2}^{\top}H_{2}\\}}=\eta^{2}(\max\sqrt{\text{Eigenvalue}\\{B_{t}^{\top}B_{t}\\}}+\beta_{1}^{2}\max\sqrt{\text{Eigenvalue}\\{B_{t+1}^{\top}B_{t+1}\\}})$
$\displaystyle\Rightarrow$ $\displaystyle\lVert
H_{2}\lVert_{2}=\eta^{2}(\lVert B_{t}\lVert_{2}+\beta_{1}^{2}\lVert
B_{t+1}\lVert_{2})$

and

$\displaystyle\lVert H_{3}\lVert_{2}$ $\displaystyle\leq\eta^{2}\left(\lVert
A^{\top}B_{t}\lVert_{2}+\lVert B_{t}^{\top}A\lVert_{2}+\lVert
B_{t}^{\top}B_{t}\lVert_{2}\right)$ $\displaystyle\leq\eta^{2}\left(\lVert
A\lVert_{2}\lVert B_{t}\lVert_{2}+\lVert A\lVert_{2}\lVert
B_{t}\lVert_{2}+\lVert B_{t}\lVert_{2}\lVert B_{t}\lVert_{2}\right)$
$\displaystyle\leq c\lVert B_{t}\lVert_{2},$

where $c=2\lVert A\lVert_{2}+c^{\prime}$, $c^{\prime}=\max_{t\geq 0}\lVert
B_{t}\lVert_{2}$. From $\sum_{t=0}^{\infty}\lVert B_{t}\lVert_{2}<+\infty$ and
$\lVert B_{t}\lVert_{2}\geq 0$, we know $c^{\prime}$ is a bounded constant. By
combining the bounds for $H_{1}$, $H_{2}$ and $H_{3}$, we have completed the
proof for negative momentum method. ∎

######  Lemma E.6.

Assume that there exists a constant $c$ such that
$\sum_{t=1}^{\infty}\lVert\bar{\mathcal{B}}_{t}\lVert_{2}\leq c$, and
$\bar{\mathcal{A}}$ is as defined in (20), (23), or (26), then
$\lVert(\bar{\mathcal{A}}-I)\bar{X}_{t}\lVert_{2}$ converges to $0$ with rate
${\mathcal{O}}(f(t))$, where

$\displaystyle f(t)=\max\\{\lambda^{t},\sum^{\infty}_{i=t/2}\lVert
B_{i}\lVert_{2}\\}.$

Here $\lambda\in(0,1)$ is determined by the eigenvalues of the iterative
matrix $\bar{\mathcal{A}}$ of corresponding learning dynamics and the payoff
matrix $A$ of the stable game.

###### Proof.

Recall that we denote the SVD formulation of iterative process in (19) (22)
and (25) as follows:

$\displaystyle\bar{X}_{t+1}=(\bar{\mathcal{A}}+\bar{\mathcal{B}}_{t})\bar{X}_{t},$

Since $\bar{\mathcal{A}}$ is a diagonalizable matrix from Lemma E.2, thus,
there exists an invertible matrix $P$ such that $P\bar{\mathcal{A}}P^{-1}=D$,
where $D$ is a diagonal matrix with the eigenvalues of $\bar{\mathcal{A}}$ as
its entries. Since maximum modulus of eigenvalues of iterative matrix
$\bar{\mathcal{A}}$ is no more than 1, then $\lVert D\lVert_{2}\leq 1$. Let

$\hat{X}_{t}=P\bar{X}_{t},\ \textnormal{and}\ \
\hat{\mathcal{B}}_{t}=P\bar{\mathcal{B}}_{t}P^{-1},$

then the iterative process becomes
$\hat{X}_{t+1}=(D+\hat{\mathcal{B}}_{t})\hat{X}_{t}$.

By induction, we have

$\displaystyle\hat{X}_{t}=(D+\hat{\mathcal{B}}_{t-1})\hat{X}_{t-1}=D^{t}\hat{X}_{0}+\sum_{l=1}^{t}D^{t-l}\hat{B}_{l-1}\hat{X}_{l-1}$
(33) $\displaystyle\Longrightarrow$
$\displaystyle\hat{\mathcal{B}}_{t}\hat{X}_{t}=\hat{\mathcal{B}}_{t}D^{t}\hat{X}_{0}+\hat{\mathcal{B}}_{t}\sum_{l=1}^{t}D^{t-l}\hat{\mathcal{B}}_{l-1}\hat{X}_{l-1}.$

Since $\lVert D^{l}\lVert_{2}\leq\lVert D\lVert_{2}^{l}\leq 1$ for any
$l\in[t]$, taking norm on both sides, we have

$\displaystyle\lVert\hat{\mathcal{B}}_{t}\hat{X}_{t}\lVert_{2}\leq\lVert\hat{\mathcal{B}}_{t}\lVert_{2}\lVert\hat{X}_{0}\lVert_{2}+\lVert\hat{\mathcal{B}}_{t}\lVert_{2}\sum_{l=1}^{t}\lVert\hat{\mathcal{B}}_{l-1}\hat{X}_{l-1}\lVert_{2},$

Now we apply Gronwall inequality, let
$u_{t}=\lVert\hat{\mathcal{B}}_{t}\hat{X}_{t}\lVert_{2}$,
$p_{t}=\lVert\hat{\mathcal{B}}_{t}\lVert_{2}\lVert\hat{X}_{0}\lVert_{2}$,
$q_{t}=\lVert\hat{\mathcal{B}}_{t}\lVert_{2}$ and $f_{t}\equiv 1$ in Gronwall
inequality, see Lemma E.4, then we have

$\lVert\hat{\mathcal{B}}_{t}\hat{X}_{t}\lVert_{2}\leq\lVert\hat{\mathcal{B}}_{t}\lVert_{2}\lVert\hat{X}_{0}\lVert_{2}+\lVert\hat{\mathcal{B}}_{t}\lVert_{2}(\sum_{l=1}^{t}\lVert\hat{\mathcal{B}}_{l}\lVert_{2}\prod_{k=l-1}^{t-l}(1+\lVert\hat{\mathcal{B}}_{l}\lVert_{2}))\lVert\hat{X}_{0}\lVert_{2}.$

Let $c_{1}=\lVert P\lVert_{2}\lVert P^{-1}\lVert_{2}$. According to the
assumption, there exists a constant $c$ such that
$\sum_{t=1}^{\infty}\lVert\bar{\mathcal{B}}_{t}\lVert_{2}\leq c$, then

$\displaystyle\sum_{t=1}^{\infty}\lVert\hat{\mathcal{B}}_{t}\lVert_{2}$
$\displaystyle=\sum_{t=1}^{\infty}\lVert
P\bar{\mathcal{B}}_{t}P^{-1}\lVert_{2}$
$\displaystyle\leq\sum_{t=1}^{\infty}\lVert
P\lVert_{2}\lVert\bar{\mathcal{B}}_{t}\lVert_{2}\lVert P^{-1}\lVert_{2}$
$\displaystyle\leq c_{1}c.$

Note that $\hat{\mathcal{B}}_{t}=P\bar{\mathcal{B}}_{t}P^{-1}$, so
$\lVert\hat{\mathcal{B}}_{t}\lVert_{2}\leq\lVert
P\lVert_{2}\lVert\bar{\mathcal{B}}_{t}\lVert_{2}\lVert P^{-1}\lVert_{2}\leq
c_{1}\lVert\bar{\mathcal{B}}_{t}\lVert_{2}$. Since $e^{x}\geq 1+x$ for
$x\in{\mathbb{R}}$, we obtain

$\displaystyle\prod_{t=1}^{\infty}(1+\lVert\hat{\mathcal{B}}_{t}\lVert_{2})$
$\displaystyle\leq\prod_{t=1}^{\infty}e^{\lVert\hat{\mathcal{B}}_{t}\lVert_{2}}$
$\displaystyle=e^{\sum_{t=1}^{\infty}\lVert\hat{\mathcal{B}}_{t}\lVert_{2}}$
$\displaystyle\leq e^{c_{1}c}.$

Let $c_{2}=(1+c_{1}c\cdot e^{c_{1}c})\lVert\hat{X}_{0}\lVert_{2}$, then

$\displaystyle\lVert\hat{\mathcal{B}}_{t}\hat{X}_{t}\lVert_{2}$
$\displaystyle\leq\lVert\hat{\mathcal{B}}_{t}\lVert_{2}\lVert\hat{X}_{0}\lVert_{2}(1+\sum_{l=1}^{t}\lVert\hat{\mathcal{B}}_{l}\lVert_{2}\prod_{k=l-1}^{t-l}(1+\lVert\hat{\mathcal{B}}_{l}\lVert_{2}))$
$\displaystyle\leq\lVert\hat{\mathcal{B}}_{t}\lVert_{2}\lVert\hat{X}_{0}\lVert_{2}(1+e^{c_{1}c}\sum_{l=1}^{t}\lVert\hat{\mathcal{B}}_{l}\lVert_{2})$
$\displaystyle\leq\lVert\hat{\mathcal{B}}_{t}\lVert_{2}\lVert\hat{X}_{0}\lVert_{2}(1+c_{1}c\cdot
e^{c_{1}c})$ $\displaystyle\leq c_{2}\lVert\hat{\mathcal{B}}_{t}\lVert_{2}.$

Multiplying $(D-I)$ on the equality (33)of both sides, we have

$(D-I)\hat{X}_{t}=(D-I)D^{t}\hat{X}_{0}+\sum_{l=1}^{t}(D-I)D^{t-l}\hat{\mathcal{B}}_{l-1}\hat{X}_{l-1}.\\\
$

Let
$c_{3}=\max\\{c_{2},c_{2}\sum_{l=1}^{\frac{1}{2}t}\lVert\hat{\mathcal{B}}_{l}\lVert_{2}\\}$,
taking the norm on both sides, we have

$\displaystyle\lVert(D-I)\hat{X}_{t}\lVert_{2}$
$\displaystyle\leq\delta^{t}\lVert\hat{X}_{0}\lVert_{2}+\sum_{l=1}^{t}\delta^{t-l}\lVert\hat{\mathcal{B}}_{l-1}\hat{X}_{l-1}\lVert_{2}\leq\delta^{t}\lVert\hat{X}_{0}\lVert_{2}+\sum_{l=1}^{t}c_{2}\delta^{t-l}\lVert\hat{\mathcal{B}}_{l}\lVert_{2}$
$\displaystyle\leq\delta^{\frac{1}{2}t}(\lVert\hat{X}_{0}\lVert_{2}+c_{2}\sum_{l=1}^{\frac{1}{2}t}\lVert\hat{\mathcal{B}}_{l}\lVert_{2})+c_{2}\sum_{l=\frac{1}{2}t}^{t}\lVert\hat{\mathcal{B}}_{l}\lVert_{2}$
$\displaystyle\leq c_{3}f(t).$

Let $\lambda=\delta^{\frac{1}{2}}$, recall that
$f(t)=\max\\{\lambda^{t},\sum^{\infty}_{i=t/2}\lVert B_{i}\lVert_{2}\\}$. The
last inequality is due to Lemma E.5, we can see that there is constant $c_{4}$
such that $\sum^{\infty}_{i=t/2}\lVert\hat{\mathcal{B}}_{i}\lVert_{2}\leq
c_{4}\sum^{\infty}_{i=t/2}\lVert B_{i}\lVert_{2}$. Recall that
$f(t)=\max\\{\lambda^{t},\sum^{\infty}_{i=t/2}\lVert B_{i}\lVert_{2}\\}$.
Then, there exists a constant $c_{5}$ such that

$\lVert(\bar{\mathcal{A}}-I)\bar{X}_{t}\lVert_{2}\leq\lVert
P^{-1}\lVert_{2}\lVert(D-I)\hat{X}_{t}\lVert_{2}\leq c_{5}f(t).$

∎

######  Lemma E.7.

If $\lVert(\bar{\mathcal{A}}-I)\bar{X}_{t}\lVert_{2}$ converges to 0 with rate
${\mathcal{O}}(f(t))$ as $t$ tends to infinity, then for OGD, EG and negative
momentum method, $\lVert A^{\top}x_{t}\lVert_{2}+\lVert Ay_{t}\lVert_{2}$
converges to 0 with rate ${\mathcal{O}}(f(t))$ when $t$ tends to infinity .

###### Proof of Lemma E.7.

We break the proof into three parts. Recall that $A=U\Sigma_{A}V^{\top}$, and
$h=\lVert\Sigma_{A}\lVert_{2}$.

Firstly we prove the lemma for OGDA.

OGDA Writing $(\bar{\mathcal{A}}-I)\bar{X}_{t}$ into matrix form:

$\displaystyle\begin{bmatrix}0&-2\eta\Sigma_{A}&0&\eta\Sigma_{A}\\\ \\\
2\eta\Sigma_{A}^{\top}&0&-\eta\Sigma_{A}^{\top}&0\\\ \\\ I&0&-I&0\\\ \\\
0&I&0&-I\end{bmatrix}\begin{bmatrix}U^{\top}x_{t-1}\\\ \\\ V^{\top}y_{t-1}\\\
\\\ U^{\top}x_{t-2}\\\ \\\
V^{\top}y_{t-2}\end{bmatrix}=\begin{bmatrix}-2\eta\Sigma_{A}V^{\top}y_{t-1}+\eta\Sigma_{A}V^{\top}y_{t-2}\\\
\\\ 2\eta\Sigma_{A}U^{\top}x_{t-1}-\eta\Sigma_{A}U^{\top}x_{t-2}\\\ \\\
U^{\top}x_{t-1}-U^{\top}x_{t-2}\\\ \\\
V^{\top}y_{t-1}-V^{\top}y_{t-2}\end{bmatrix}$

Since there is a constant $c$ such
that$\lVert(\bar{\mathcal{A}}-I)\bar{X}_{t}\lVert_{2}\leq cf(t)$, then

$\displaystyle\lVert
2\eta\Sigma_{A}U^{\top}x_{t-1}-\eta\Sigma_{A}U^{\top}x_{t-2}\lVert_{2}\leq
cf(t),$ $\displaystyle\lVert U^{\top}x_{t-1}-U^{\top}x_{t-2}\lVert_{2}\leq
cf(t).$

Using these two inequalities to bound $\lVert A^{\top}x_{t}\lVert_{2}$, we
have

$\displaystyle\lVert\eta\Sigma_{A}U^{\top}x_{t-1}\lVert_{2}$ $\displaystyle=$
$\displaystyle\lVert
2\eta\Sigma_{A}U^{\top}x_{t-1}-\eta\Sigma_{A}U^{\top}x_{t-2}-\eta\Sigma_{A}(U^{\top}x_{t-1}-U^{\top}x_{t-2})\lVert_{2}$
$\displaystyle\leq$ $\displaystyle\lVert
2\eta\Sigma_{A}U^{\top}x_{t-1}-\eta\Sigma_{A}U^{\top}x_{t-2}\lVert_{2}+\lVert\eta\Sigma_{A}(U^{\top}x_{t-1}-U^{\top}x_{t-2})\lVert_{2}$
$\displaystyle\leq$ $\displaystyle cf(t)+\eta cf(t).$

Since $A^{\top}x_{t}=V\Sigma_{A}U^{\top}x_{t}$, then

$\displaystyle\lVert A^{\top}x_{t}\lVert_{2}$ $\displaystyle=\lVert
V\Sigma_{A}U^{\top}x_{t}\lVert_{2}$ $\displaystyle\leq\lVert
V\lVert_{2}\lVert\Sigma_{A}U^{\top}x_{t}\lVert_{2}$
$\displaystyle\leq\frac{ch(1+\eta)f(t)}{\eta},$

where the last inequality is due to $\lVert\Sigma_{A}\lVert_{2}=h$ and $V$,
$U$ are unitary matrices. Similarly, we can obtain $\lVert
Ay_{t}\lVert_{2}\leq\frac{(1+\eta)chf(t)}{\eta}$.

Next, we prove the lemma for extra-gradient.

EG Writing $(\bar{\mathcal{A}}-I)\bar{X}_{t}$ into matrix form:

$\displaystyle\begin{bmatrix}-\alpha\gamma\Sigma_{A}\Sigma_{A}^{\top}&-\alpha\Sigma_{A}\\\
\\\
\alpha\Sigma_{A}^{\top}&-\alpha\gamma\Sigma_{A}^{\top}\Sigma_{A}\end{bmatrix}\begin{bmatrix}U^{\top}x_{t-1}\\\
\\\ V^{\top}y_{t-1}\\\
\end{bmatrix}=\begin{bmatrix}-\alpha\gamma\Sigma_{A}\Sigma_{A}^{\top}U^{\top}x_{t-1}-\alpha\Sigma_{A}V^{\top}y_{t-1}\\\
\\\
\alpha\Sigma_{A}^{\top}U^{\top}x_{t-1}-\alpha\gamma\Sigma_{A}^{\top}\Sigma_{A}V^{\top}y_{t-1}.\end{bmatrix}$

Since there is a constant $c$ such that
$\lVert(\bar{\mathcal{A}}-I)\bar{X}_{t}\lVert_{2}\leq cf(t)$, then

$\displaystyle\lVert-\gamma\Sigma_{A}\Sigma_{A}^{\top}U^{\top}x_{t-1}-\Sigma_{A}V^{\top}y_{t-1}\lVert_{2}\leq\frac{cf(t)}{\alpha},$
$\displaystyle\lVert\Sigma_{A}^{\top}U^{\top}x_{t-1}-\gamma\Sigma_{A}^{\top}\Sigma_{A}V^{\top}y_{t-1}\lVert_{2}\leq\frac{cf(t)}{\alpha}.$

Using these two inequalities to bound $\lVert A^{\top}x_{t}\lVert_{2}$, we
have

$\displaystyle\lVert(\gamma^{2}\Sigma_{A}^{\top}\Sigma_{A}+I)\Sigma_{A}^{\top}U^{\top}x_{t-1}\lVert_{2}$
$\displaystyle=$
$\displaystyle\lVert\Sigma_{A}^{\top}U^{\top}x_{t-1}-\gamma\Sigma_{A}^{\top}\Sigma_{A}V^{\top}y_{t-1}-\gamma\Sigma_{A}^{\top}\left(-\gamma\Sigma_{A}\Sigma_{A}^{\top}U^{\top}x_{t-1}-\Sigma_{A}V^{\top}y_{t-1}\right)\lVert_{2}$
$\displaystyle\leq$
$\displaystyle\lVert\Sigma_{A}^{\top}U^{\top}x_{t-1}-\gamma\Sigma_{A}^{\top}\Sigma_{A}V^{\top}y_{t-1}\lVert_{2}+\gamma\lVert\Sigma_{A}^{\top}\lVert_{2}\lVert-\gamma\Sigma_{A}\Sigma_{A}^{\top}U^{\top}x_{t-1}-\Sigma_{A}V^{\top}y_{t-1}\lVert_{2}$
$\displaystyle\leq$ $\displaystyle\frac{(1+\gamma h)cf(t)}{\alpha}.$

Since matrix $\gamma^{2}\Sigma_{A}^{\top}\Sigma_{A}+I$ is invertible, then

$\displaystyle\lVert\Sigma_{A}U^{\top}x_{t}\lVert_{2}=$
$\displaystyle\lVert(\gamma^{2}\Sigma_{A}^{\top}\Sigma_{A}+I)^{-1}(\gamma^{2}\Sigma_{A}^{\top}\Sigma_{A}+I)\Sigma_{A}^{\top}U^{\top}x_{t-1}\lVert_{2}$
$\displaystyle\leq$
$\displaystyle\lVert(\gamma^{2}\Sigma_{A}^{\top}\Sigma_{A}+I)^{-1}\lVert_{2}\lVert(\gamma^{2}\Sigma_{A}^{\top}\Sigma_{A}+I)\Sigma_{A}^{\top}U^{\top}x_{t-1}\lVert_{2}$
$\displaystyle\leq$
$\displaystyle\lVert(\gamma^{2}\Sigma_{A}^{\top}\Sigma_{A}+I)\Sigma_{A}^{\top}U^{\top}x_{t-1}\lVert_{2}$
$\displaystyle\leq$ $\displaystyle\frac{(1+\gamma h)cf(t)}{\alpha},$

where the last inequality is due to
$\lVert(\gamma^{2}\Sigma_{A}^{\top}\Sigma_{A}+I)^{-1}\lVert_{2}\leq 1$. Since
$A^{\top}x_{t}=V\Sigma_{A}U^{\top}x_{t}$, then

$\displaystyle\lVert A^{\top}x_{t}\lVert_{2}$ $\displaystyle=\lVert
V\Sigma_{A}U^{\top}x_{t}\lVert_{2}\leq\lVert
V\lVert_{2}\lVert\Sigma_{A}U^{\top}x_{t}\lVert_{2}\leq\frac{(1+\gamma
h)cf(t)}{\alpha},$

where the last inequality is due to $V$ is unitary matrices. Similarly, we can
obtain

$\lVert Ay_{t}\lVert_{2}\leq\frac{(1+\gamma h)}{\alpha}f(t)c.$

Finally, we prove the lemma for negative momentum method.

Negative Momentum Method Writing $(\bar{\mathcal{A}}-I)\bar{X}_{t}$ into
matrix form:

$\displaystyle\begin{bmatrix}\beta_{1}I&-\eta\Sigma_{A}&-\beta_{1}I&0\\\ \\\
\eta(1+\beta_{1})\Sigma_{A}^{\top}&-\eta^{2}\Sigma_{A}^{\top}\Sigma_{A}&-\eta\beta_{1}\Sigma_{A}^{\top}&-\beta_{2}I\\\
\\\ I&0&-I&0\\\ \\\ 0&I&0&-I\end{bmatrix}\begin{bmatrix}U^{\top}x_{t-1}\\\ \\\
V^{\top}y_{t-1}\\\ \\\ U^{\top}x_{t-2}\\\ \\\ V^{\top}y_{t-2}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\beta_{1}U^{\top}x_{t-1}-\eta\Sigma_{A}V^{\top}y_{t-1}-\beta_{1}U^{\top}x_{t-2}\\\
\\\
\eta(1+\beta_{1})\Sigma_{A}^{\top}U^{\top}x_{t-1}-\eta^{2}\Sigma_{A}^{\top}\Sigma_{A}V^{\top}y_{t-1}-\eta\beta_{1}\Sigma_{A}^{\top}U^{\top}x_{t-2}-\beta_{2}V^{\top}y_{t-2}\\\
\\\ U^{\top}x_{t-1}-U^{\top}x_{t-2}\\\ \\\
V^{\top}y_{t-1}-V^{\top}y_{t-2}\end{bmatrix}$

Since there is a constant $c$ such that
$\lVert(\bar{\mathcal{A}}-I)\bar{y}_{t}\lVert_{2}\leq cf(t)$, then

$\displaystyle\lVert\beta_{1}U^{\top}x_{t-1}-\eta\Sigma_{A}V^{\top}y_{t-1}-\beta_{1}U^{\top}x_{t-2}\lVert_{2}\leq
cf(t),$ $\displaystyle\lVert U^{\top}x_{t-1}-U^{\top}x_{t-2}\lVert_{2}\leq
cf(t).$

Using these two inequalities to bound $\lVert Ay_{t}\lVert_{2}$, we have

$\displaystyle\lVert\eta\Sigma_{A}V^{\top}y_{t-1}\lVert_{2}$ $\displaystyle=$
$\displaystyle\lVert\beta_{1}\left(U^{\top}x_{t-1}-U^{\top}x_{t-2}\right)-\left(\beta_{1}U^{\top}x_{t-1}-\eta\Sigma_{A}V^{\top}y_{t-1}-\beta_{1}U^{\top}x_{t-2}\right)\lVert_{2}$
$\displaystyle\leq$
$\displaystyle\lVert\beta_{1}\left(U^{\top}x_{t-1}-U^{\top}x_{t-2}\right)\lVert_{2}+\lVert\beta_{1}U^{\top}x_{t-1}-\eta\Sigma_{A}V^{\top}y_{t-1}-\beta_{1}U^{\top}x_{t-2}\lVert_{2}$
$\displaystyle\leq$ $\displaystyle\beta_{1}cf(t)+cf(t).$

Since $Ay_{t}=U\Sigma_{A}V^{\top}y_{t}$, then

$\displaystyle\lVert Ay_{t}\lVert_{2}$ $\displaystyle=\lVert
U\Sigma_{A}V^{\top}y_{t}\lVert_{2}\leq\lVert
U^{\top}\lVert_{2}\lVert\Sigma_{A}V^{\top}y_{t}\lVert_{2}\leq\frac{c(1+\beta_{1})f(t)}{\eta},$

where the last inequality is due to $\lVert U\lVert_{2}=1$.

We also have

$\displaystyle\lVert\eta(1+\beta_{1})\Sigma_{A}^{\top}U^{\top}x_{t-1}-\eta^{2}\Sigma_{A}^{\top}\Sigma_{A}V^{\top}y_{t-1}-\eta\beta_{1}\Sigma_{A}^{\top}U^{\top}x_{t-2}-\beta_{2}V^{\top}y_{t-2}\lVert_{2}\leq
cf(t)$

and

$\displaystyle\lVert V^{\top}y_{t-1}-V^{\top}y_{t-2}\lVert_{2}\leq cf(t).$

Then,

$\displaystyle\lVert\eta\Sigma_{A}\Sigma_{A}^{\top}U^{\top}x_{t-1}\lVert_{2}$
$\displaystyle=$
$\displaystyle\lVert\Sigma_{A}\cdot([\eta(1+\beta_{1})\Sigma_{A}^{\top}U^{\top}x_{t-1}-\eta^{2}\Sigma_{A}^{\top}\Sigma_{A}V^{\top}y_{t-1}-\eta\beta_{1}\Sigma_{A}^{\top}U^{\top}x_{t-2}-\beta_{2}V^{\top}y_{t-2}]$
$\displaystyle-\eta\Sigma_{A}^{\top}\left(\beta_{1}U^{\top}x_{t-1}-\eta\Sigma_{A}V^{\top}y_{t-1}-\beta_{1}U^{\top}x_{t-2}\right)+\beta_{2}\Sigma_{A}^{\top}V^{\top}y_{t-2})\lVert_{2}$
$\displaystyle\leq$
$\displaystyle\lVert\Sigma_{A}\lVert_{2}cf(t)+\lVert\Sigma_{A}\lVert_{2}cf(t)+\frac{\beta_{2}(1+\beta_{1})}{\eta}cf(t)$
$\displaystyle\leq$
$\displaystyle\left(2h+\frac{\beta_{2}(1+\beta_{1})}{\eta}\right)cf(t)$

Since $\lVert\Sigma_{A}\lVert_{2}=h$, then
$\lVert\Sigma_{A}^{\top}U^{\top}x_{t}\lVert_{2}\leq\frac{2\eta
h+\beta_{2}(1+\beta_{1})}{\eta^{2}h}cf(t)$. Since
$A^{\top}x_{t}=V\Sigma_{A}U^{\top}x_{t}$, then

$\displaystyle\lVert A^{\top}x_{t}\lVert_{2}$ $\displaystyle=\lVert
V\Sigma_{A}U^{\top}x_{t}\lVert_{2}$ $\displaystyle\leq\lVert
V\lVert_{2}\lVert\Sigma_{A}U^{\top}x_{t}\lVert_{2}$
$\displaystyle\leq\frac{2\eta h+\beta_{2}(1+\beta_{1})}{\eta^{2}h}cf(t).$

∎

Now we are ready to prove Theorem 3.3.

###### proof of Theorem 3.3.

According to Lemma E.5, assumptions of Lemma E.6 have been satisfied by the
difference equations associated to our learning dynamics, thus we have
$\lVert(\bar{\mathcal{A}}-I)\bar{X}_{t}\lVert_{2}$ converges to 0 with rate
$f(t)$. Moreover, by Lemma E.7 , $\Delta_{t}$ converges to 0 with rate $f(t)$
in OGD, EG and negative momentum method. We complete the proof. ∎

##  Appendix F Omitted Proofs from Theorem 3.4

See 3.4

Recall that Extra Gradient satisfies the linear difference equation (3),
denote the iterative matrix in equation (3) with payoff matrix $A_{t}$ as
$\mathcal{A}_{t}$. According to the convergence of payoff matrix, we have
$\lim_{t\rightarrow\infty}A_{t}=A$. Let $B_{t}=A_{t}-A$, then we have
$\lim_{t\rightarrow\infty}B_{t}=0$. Denote $\mathcal{A}$ as the iterative
matrix when payoff matrix is time invariant and equal to $A$. Let

$\mathcal{B}_{t}=\mathcal{A}_{t}-\mathcal{A}.$

To prove the theorem, we first establish several necessary lemmas.

######  Lemma F.1.

Given $\lim_{t\rightarrow\infty}B_{t}=0$, we have
$\lim_{t\rightarrow\infty}\mathcal{B}_{t}=0$.

###### Proof.

Recall that

$\displaystyle\mathcal{A}_{t}=\left[\begin{array}[]{cc}I-\alpha\gamma
A_{t}A_{t}^{\top}&-\alpha A_{t}\\\ \\\ \alpha A_{t}^{\top}&I-\gamma\alpha
A_{t}^{\top}A_{t}\end{array}\right]$

and

$\displaystyle\mathcal{A}=\left[\begin{array}[]{cc}I-\alpha\gamma
AA^{\top}&-\alpha A\\\ \\\ \alpha A^{\top}&I-\gamma\alpha
A^{\top}A\end{array}\right],$

we can obtain that

$\displaystyle{\mathcal{B}}_{t}$
$\displaystyle=\begin{bmatrix}-\alpha\gamma(AB_{t}^{\top}+B_{t}A^{\top}+B_{t}B_{t}^{\top})&-\alpha
B_{t}\\\ \\\ \\\ \alpha
B_{t}^{\top}&\alpha\gamma(A^{\top}B_{t}+B_{t}^{\top}A+B_{t}^{\top}B_{t})\end{bmatrix}$
$\displaystyle=\begin{bmatrix}-\alpha\gamma(AB_{t}^{\top}+B_{t}A^{\top}+B_{t}B_{t}^{\top})&0\\\
\\\ \\\ 0&0\end{bmatrix}+\begin{bmatrix}0&0\\\ \\\ \\\
0&\alpha\gamma(A^{\top}B_{t}+B_{t}^{\top}A+B_{t}^{\top}B_{t})\end{bmatrix}$
$\displaystyle+\begin{bmatrix}0&-\alpha B_{t}\\\ \\\ \\\
0&0\end{bmatrix}+\begin{bmatrix}0&0\\\ \\\ \\\ \alpha
B_{t}^{\top}&0\end{bmatrix}.$

We separate ${\mathcal{B}}_{t}$ into four matrices and denote these matrices
in right side of the equation as $H_{1}$, $H_{2}$ , $H_{3}$ and $H_{4}$,
respectively. Then

$\displaystyle\lVert\mathcal{B}_{t}\lVert_{2}\leq\lVert H_{1}\lVert_{2}+\lVert
H_{2}\lVert_{2}+\lVert H_{3}\lVert_{2}+\lVert H_{4}\lVert_{2}.$

Since $\lim_{t\rightarrow\infty}B_{t}=0$ , then
$\lim_{t\rightarrow\infty}\lVert B_{t}\lVert_{2}=0$, so we can yield that
there exists $c$ such that $\lVert B_{t}\lVert_{2}\leq c$ for any t. We also
assume that $c_{1}=\lVert A\lVert_{2}$.

Then we have

$\displaystyle\lVert H_{1}\lVert_{2}$ $\displaystyle=\alpha\gamma\lVert
AB_{t}^{\top}+B_{t}A^{\top}+B_{t}B_{t}^{\top}\lVert_{2}$
$\displaystyle\leq\alpha\gamma\left(\lVert A\lVert_{2}\lVert
B_{t}\lVert_{2}+\lVert A\lVert_{2}\lVert B_{t}\lVert_{2}+\lVert
B_{t}\lVert_{2}\lVert B_{t}\lVert_{2}\right)$
$\displaystyle\leq\alpha\gamma(2c_{1}+c)\lVert B_{t}\lVert_{2},$

Similarly, $\lVert H_{2}\lVert_{2}\leq\alpha\gamma(2c_{1}+c)\lVert
B_{t}\lVert_{2}$. In addition, $\lVert H_{3}\lVert_{2}=\lVert
H_{4}\lVert_{2}=\alpha\lVert B_{t}\lVert_{2}$.

Then we can obtain that there exists a constant $c_{2}$, such that