# Prediction Accuracy of Learning in Games :
Follow-the-Regularized-Leader meets Heisenberg

Yi Feng  Georgios Piliouras  Xiao Wang

###### Abstract

We investigate the accuracy of prediction in deterministic learning dynamics
of zero-sum games with random initializations, specifically focusing on
observer uncertainty and its relationship to the evolution of covariances.
Zero-sum games are a prominent field of interest in machine learning due to
their various applications. Concurrently, the accuracy of prediction in
dynamical systems from mechanics has long been a classic subject of
investigation since the discovery of the Heisenberg Uncertainty Principle.
This principle employs covariance and standard deviation of particle states to
measure prediction accuracy. In this study, we bring these two approaches
together to analyze the Follow-the-Regularized-Leader (FTRL) algorithm in two-
player zero-sum games. We provide growth rates of covariance information for
continuous-time FTRL, as well as its two canonical discretization methods
(Euler and Symplectic). A Heisenberg-type inequality is established for FTRL.
Our analysis and experiments also show that employing Symplectic
discretization enhances the accuracy of prediction in learning dynamics.

Machine Learning, ICML

##  1 Introduction

In recent years understanding the behavior of learning algorithms in repeated
games has attracted increasing interests from the machine learning community
(Lanctot et al., 2017; Yang & Wang, 2020). Follow-the-Regularized-Leader
(FTRL) algorithm (Abernethy et al., 2009; Shalev-Shwartz et al., 2012),
arguably the most well known class of no-regret dynamics, plays a prominent
role in analysis of behavior of learning algorithms. The dynamics of such
online learning algorithm in zero-sum games has been a particularly intense
object of study as zero-sum games related to numerous recent applications and
advances in AI such as, achieving super-human performance in Go (Silver et
al., 2016), Poker (Brown & Sandholm, 2018) and Generative Adversarial Networks
(GANs) (Goodfellow et al., 2014) to name a few.

Predicting players’ long term behaviors in a repeated game is a fundamental
and challenging problem (Nachbar, 1997; Cesa-Bianchi & Lugosi, 2006). The
conventional wisdom in this regard is that players’ strategies will eventually
converge to some equilibrium. However, recent studies have shown that such a
belief usually fails, in particular, FTRL dynamics do not converge in zero-sum
games and exhibit complex behaviors such as recurrence and divergence
(Mertikopoulos et al., 2018; Bailey & Piliouras, 2018). Therefore, one needs
to predict the future behaviors of players by tracing their day-to-day (a.k.a.
last-iterate) behaviors (Daskalakis et al., 2018; Gidel et al., 2019a, b). By
modeling the learning dynamics as a deterministic dynamical system, an
observer with the computational ability to trace the learning dynamics can
accurately predict future player states by knowing their exact current states.

However, in practice, the observer may have some uncertainty about the current
states of players. This kind of uncertainty is common both from a game-
theoretic perspective (i.e., the unknown external action on agents’
preference) as well as from a Machine Learning perspective (i.e., system
initialization by sampling from a distribution and noise introduced during
training ). Thus, the observer may hope that slightly inaccurate knowledge of
current conditions can lead to slightly inaccurate prediction. For example, by
tracking the expectation of the evolving distribution along the learning
dynamics that model his uncertainty, satisfactory predictions can be obtained.

(a) t = 0, variance = 0.00020781

(b) t = 50, variance = 0.01038411

(c) t = 80, variance = 0.05732407

(d) t = 130, variance = 0.09969448

(e) t = 150, variance = 0.07895284

(f) t = 200, variance = 0.08126675

Figure 1: Evolution of 400 initial conditions (blue points) for one player
using (AltMWU) in R-P-S game, the red point is the expectation of blue points,
the variance is calculated on the first pure strategy. At time $t=0$, these
point are sampled in a small square. As time evolves, it appears that these
points are randomly located on the simplex and the variance is magnified by a
factor of 400. Moreover, the expectation (red point in the figures) cannot
accurately predict future outcomes, as sample points in subsequent times may
deviate significantly from the expected value. A demo animation can be found
here.

Unfortunately, this hope didn’t materialize as expected. One remarkable aspect
of several learning dynamics, like Multiplicative Weights Updates (FTRL with
negative entropy regularizer), is that even slight initial deviation can give
rise to significantly divergent strategy trajectories for players over
extended periods (Sato et al., 2002; Vilone et al., 2011; Galla & Farmer,
2013). Figure 1 illustrates that in a repeated Rock-Paper-Scissor game, the
evolution of many orbits starting from a small region when players use
Alternating Multiplicative Weights Update. Figure 1 shows that even small
initial uncertainty can be amplified and make the accurate prediction
difficult. Moreover, tracking the expectation fails to accurately prediction
as a large portion of points will deviate significantly from the expectation;
in terms of statistics, the (co)variance of the distribution can be large over
time, hindering accurate predictions of players’ future behaviors. Motivated
by this example, we naturally formulate the following question:

How to track the accuracy of prediction in learning dynamics?

The most relevant paper in this direction is (Cheung et al., 2022), which
utilized differential entropy as their metric of uncertainty and demonstrated
that it grows linearly fast in two-player zero-sum games, quantifying the
amount of excess information an observer must gather to keep track of the
uncertain system evolution. However, as we will show in following,
differential entropy cannot capture the uncertainty evolution of the
_alternating_ update rule of game dynamics, such as the alternating MWU in
Figure 1.

In this work, we will study the evolution of covariance (standard deviation)
associated with related random variables that govern the dynamics of FTRL,
utilizing the framework of the Hamiltonian formulation of FTRL (Bailey &
Piliouras, 2019; Wibisono et al., 2022). This perspective studies the
evolution of covariance closely related to the well known _Heisenberg
Uncertainty Principle_ in quantum mechanics, which states that the covariance
of the momentum and position of a microscopic particle cannot be small at the
same time, i.e., $\Delta p\Delta q\geq\text{some positive constant}$. The
Hamiltonian formulation of FTRL endows the cumulative strategy and cumulative
payoff of each agent the roles of position $q$ and momentum $p$ of each
particle, and these quantities completely determine the dynamics of the game.
Once the initialization is randomized, the deterministic learning dynamics
still makes the cumulative strategy and payoff random variables whose mean and
covariance matrix is related to that of the initialization. As what is implied
from Heisenberg Uncertainty Principle (Busch et al., 2007), information on
covariance (standard deviation) measures the _accuracy of prediction_ in
learning dynamics. We will also demonstrate that this analogy is not vague;
similar phenomena to the Heisenberg Uncertainty Principle already exist in
FTRL dynamics.

##### Our contributions.

We highlight our main contributions as follows:

  * •

We prove that differential entropy remains constant when two players
alternatively update their strategies. Therefore, it is not a strong concept
for capturing the evolution of uncertainty in alternating update, see
Proposition 4.1.

  * •

We propose the covariance matrix as an uncertainty measurement which captures
both simultaneous and alternating updates, with rate of increasing calculated
concretely in Euclidean regularized FTRL, see Theorem 5.1. Our results imply a
separation between simultaneous and continuous time/alternating plays. As an
immediate application, Corollary 5.3 provides a prediction with quantitative
description of risk, i.e., probability of deviating from expectation up to
time $t$;

  * •

For FTRL with general regularizers, a Heisenberg type inequality on variances
of cumulative strategy and payoff is obtained, i.e., $\Delta
X_{i,\alpha}\Delta y_{i,\alpha}\geq\text{positive constant}$. Similar to the
Heisenberg Uncertainty Principle in quantum mechanics, this inequality
indicates a trade-off between prediction accuracy in strategy spaces versus
payoff spaces for game dynamics, see Theorem 5.4. In Figure 2 we present an
example to illustrate this point.

Figure 2: The two curves represent the evolution of $\Delta X_{i,\alpha}$ and
$\Delta y_{i,\alpha}$ on 100 random samples of two players when they use
(AltMWU). When one curve is decreasing, another curve is increasing. This
implies a tradeoff between accuracy in strategy spaces versus payoff spaces.

##### Technical innovations.

The techniques used in drawing the above conclusions come from different
areas. The theoretical framework for analyzing the uncertainty evolution is
the classic mechanical formulation of games (Bailey & Piliouras, 2019;
Wibisono et al., 2022). A rigorous correspondence has been established between
symplectic discretization (Haier et al., 2006) and alternating plays to study
their properties. To demonstrate that differential entropy is constant in
alternating plays, we utilize the volume preservation property of Symplectic
discretization. Furthermore, the intuition in deriving the covariance
evolution of Symplectic discretization is from (Wang, 1994), and the proof
combine tools from application of matrix analysis in dynamical systems
(Colonius & Kliemann, 2014). The uncertainty inequality for general FTRL is a
consequence of a classic result from symplectic geometry known as non-
squeezing theorem (McDuff & Salamon, 2017) and variance analysis methods from
multivariate statistics.

##  2 Preliminaries

##### Learning in games.

A two agent zero-sum game consists of two agent ${\mathcal{N}}=\\{1,2\\}$,
where agent $i$ selects a strategy from the strategy space (or primal space)
$\mathcal{X}_{i}\subset{\mathbb{R}}^{n_{i}}$ and $n_{i}$ represents the number
of actions available to agent $i$. Typically, $\mathcal{X}_{i}$ is chosen to
be ${\mathbb{R}}^{n_{i}}$, which we called the unconstrained zero-sum game, or
it is chosen to be the simplex constrains

$\displaystyle\Delta_{i}=\\{x\ \lvert\ \sum^{n_{i}}_{s=1}x_{i,s}=1,x_{i,s}\geq
0\\}.$

Utilities of both agents are determined via payoff matrix
$A^{(ij)}\in{\mathbb{R}}^{n_{i}\times n_{j}}$, and in a zero-sum game, the pay
off matrix satisfy $A^{(ij)}=-A^{(ji)}$. For convenience, we will also use $A$
to refer to $A^{(12)}$, and thus $A^{(21)}=-A^{\top}$. Given that agent $i$
selects strategy $x_{i}\in\mathcal{X}_{i}\subset{\mathbb{R}}^{n_{i}}$, agent 1
receives utility $u_{1}(x_{1},x_{2})=\langle x_{1},Ax_{2}\rangle$, and agent 2
receives utility $u_{2}(x_{2},x_{1})=-\langle x_{2},A^{\top}x_{1}\rangle$.
Naturally agents want to maximize their utility resulting the following max-
min problem:

$\displaystyle\max_{x_{1}\in\mathcal{X}_{1}}\min_{x_{2}\in\mathcal{X}_{2}}x^{\top}_{1}Ax_{2}.$
(Zero-Sum Game)

##### Follow-the-Regularized-Leader.

Follow-the-Regularized-Leader (FTRL) is a widely used class of no-regret
online learning algorithms. In continuous time FTRL, at time $t$, agent $i$
updates strategies $x_{i}(t)$ based on the cumulative payoff vector
$y_{i}(t)$,

$\displaystyle y_{i}(t)=y_{i}(0)+\int_{0}^{t}A^{(ij)}x_{j}(s)ds$ (Continuous
FTRL) $\displaystyle
x_{i}(t)=\operatorname*{arg\,max}_{x_{i}\in\mathcal{X}_{i}}\\{\langle
x_{i},y_{i}(t)\rangle-h_{i}(x_{i})\\}$

where $h_{i}$ is a strongly convex function, which is called the regularizer.
It is also well known that

$\displaystyle x_{i}(t)=\nabla h^{*}_{i}\left(y_{i}(t)\right),$ (1)

where

$\displaystyle h^{*}_{i}(y_{i})=\max_{x_{i}\in\mathcal{X}_{i}}\\{\langle
x_{i},y_{i}\rangle-h_{i}(x_{i})\\}$ (2)

is the convex conjugate of $h_{i}$ (Shalev-Shwartz & Singer, 2006). Therefore,
if an observer knows the regularizer used by players, they can convert the
information of $y_{i}(t)$ into the primal space $x_{i}(t)$.

Gradient descent ascent (GDA) and multiplicative weights updates (MWU) are two
of the most well known special cases of FTRL algorithms. For unconstrained
GDA, the regularizers are chosen to be the Euclidean norm, i.e.,
$h_{i}(x_{i})=\lVert x_{i}\lVert^{2}$ and
$\mathcal{X}_{i}={\mathbb{R}}^{n_{i}}$. For MWU, the regularizers are chosen
to be negative entropy, i.e.,

$\displaystyle h_{i}(x_{i})=\sum_{j\in[n_{i}]}x_{i,j}\ln(x_{i,j})$

and $\mathcal{X}_{i}$ be the simplex constrains.

In discrete time, FTRL has two kinds of implementations : simultaneous and
alternating. Let $y^{t}_{1}=Ax^{t}_{2},\ \ y^{t}_{2}=A^{\top}x^{t}_{1}.$ In
the case of GDA and MWU, the update rules with step size $\eta$ are :

$\displaystyle x^{t}_{1}=x^{t-1}_{1}+\eta y^{t-1}_{1},\ \
x^{t}_{2}=x^{t-1}_{2}-\eta y^{t-1}_{2}.$ (GDA) $\displaystyle
x^{t}_{2}=x^{t-1}_{2}-\eta y^{t-1}_{2},\ \ x^{t}_{1}=x^{t-1}_{1}+\eta
y^{t}_{1}.$ (AltGDA)

and

$\displaystyle x^{t}_{1}=\left(\frac{x^{t-1}_{1,s}e^{\eta
y^{t-1}_{1,s}}}{\sum^{n_{1}}_{j=1}x^{t-1}_{1,j}e^{\eta
y^{t-1}_{1,j}}}\right)_{s}x^{t}_{2}=\left(\frac{x^{t-1}_{2,s}e^{-\eta
y^{t-1}_{2,s}}}{\sum^{n_{2}}_{j=1}x^{t-1}_{2,j}e^{-\eta
y^{t-1}_{2,j}}}\right)_{s}$ (MWU) $\displaystyle
x^{t}_{2}=\left(\frac{x^{t-1}_{2,s}e^{-\eta
y^{t-1}_{2,s}}}{\sum^{n_{2}}_{j=1}x^{t-1}_{2,j}e^{-\eta
y^{t-1}_{2,j}}}\right)_{s}x^{t}_{1}=\left(\frac{x^{t-1}_{1,s}e^{\eta
y^{t}_{1,s}}}{\sum^{n_{1}}_{j=1}x^{t-1}_{1,j}e^{\eta y^{t}_{1,j}}}\right)_{s}$
(AltMWU)

for $s=\\{1,2,...,n_{i}\\}$ and $i=1$ or $2$. Note that in simultaneous
updates, both two players use the payoff feedback from round $t-1$ to update
their strategies in round $t$, while in alternating updates, Player 2 first
update his strategy $x^{t}_{2}$, and Player 1 subsequently updates her
strategy $x^{t}_{1}$ based on payoff feedback of $x^{t}_{2}$. Comparing to its
simultaneous partner, a series of recent works show that alternating update
rule has a slower regret growth rate (Bailey et al., 2020; Wibisono et al.,
2022; Cevher et al., 2023).

##### Dynamical system.

A system of ordinary differential equations $\dot{x}=f(x)$ where
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is a differentiable dynamical
system. $f(x)$ is called the vector field of the dynamical system. If $f$ is
Lipschitz continuous, there exists a continuous map

$\varphi(t,x_{0}):\mathbb{R}\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$

such that for all $x_{0}\in\mathbb{R}^{n}$, $\varphi(t,x_{0})$ is the unique
solution of the initial condition problem $\\{\dot{x}=f(x),x(0)=x_{0}\\}$. The
solution $\varphi(t,x_{0})$ is called a _trajectory_ or _orbit_ of the
dynamical system.

Hamiltonian systems. A Hamiltonian system is a class of differential equations
describing the evolution of momentums and positions of particles by a scalar
function $H(X,Y)$ called Hamiltonian function. The state of the system, the
momentum $Y=(y_{1},...,y_{n})^{\top}$ and position
$X=(x_{1},...,x_{n})^{\top}$ evolves according to the following Hamilton’s
equations:

$\frac{dx_{i}}{dt}=\frac{\partial H}{\partial y_{i}},\ \ \ \
\frac{dy_{i}}{dt}=-\frac{\partial H}{\partial x_{i}},\ \ \ \ \text{for}\ \ \
i\in[n].$ (3)

The solution $\varphi(t,\cdot)$ of a Hamiltonian system is called a
_symplectic_ map which is a special case of volume-preserving maps, thus the
absolute value of determinant of the Jacobian matrix equals to $1$. The
variables $(X,Y)$ are also referred to the canonical coordinates of the system
(Arnold, 2013).

###  2.1 Measure of Observer Uncertainty

Differential Entropy. The concept of differential entropy was introduced by
Shannon (Shannon, 1948) as a measure of the uncertainty associated with a
continuous probability distribution. For a random vector
$X\in{\mathbb{R}}^{n}$ with probability density function $g(x)$ supported on
$\mathcal{X}\subset{\mathbb{R}}^{n}$, the differential entropy of $X$ is
defined as

$\displaystyle S(X)=-\int_{\mathcal{X}}g(x)\log g(x)dx.$ (Differential
Entropy)

Covariances of random vectors. Given a random vector
$X=(x_{1},...,x_{m})^{\top}$ such that every $x_{i}$ is a random variable with
finite variance and expected value, the covariance matrix
$P(X)\in{\mathbb{R}}^{m\times m}$ of $X$ is a symmetric and positive semi-
definite square matrix whose $(i,j)$ entry is the covariance, i.e.,

$\mathrm{Cov}(x_{i},x_{j})={\mathbb{E}}[(x_{i}-{\mathbb{E}}(x_{i}))(x_{j}-{\mathbb{E}}(x_{j}))].$

Note that the diagonal elements of $P(x)$ are variances of
$\\{x_{1},...,x_{m}\\}$.

In general, the differential entropy of a random variable provides a lower
bound on the determinant of its covariance matrix. Precisely, if a random
vector $X\in{\mathbb{R}}^{m}$ has zero mean and covariance matrix $P(X)$, then

$\displaystyle S(X)\leq\frac{1}{2}\log\left((2\pi e)^{n}\det P(X)\right).$

##  3 Setup

In this section we leverage the power of the Hamiltonian formulation of game
dynamics (Bailey & Piliouras, 2019; Wibisono et al., 2022). To study the
strategy-payoff evolution from the perspective of each agent, it is convenient
to apply the Hamiltonian formulation of the continuous time FTRL. We will
establish the equivalence between discretization of the Hamiltonian system
induced by continuous time FTRL and direct discretization of FTRL, where the
latter leads to the GDA or MWU.

Euler discretization. Given an ordinary differential equation $\dot{x}=f(x)$
with initial condition $x(t_{0})$ at time $t_{0}$, the Euler discretization
begin the process by setting $x_{0}=x(t_{0})$, next choose a step size $\eta$
and set $t_{n}=t_{0}+n\eta$, then the Euler discretization
$\phi_{\eta}(\cdot)$ is defined by $x_{n+1}=\phi_{\eta}(x_{n})=x_{n}+\eta
f(x_{n})$. The value $x_{n+1}$ is an approximation of the solution of
$\dot{x}=f(x)$ at time $t_{n+1}$.

Symplectic discretization. Given a Hamiltonian system as in (3), a numerical
method $\phi_{\eta}(\cdot)$ is called a Symplectic discretization if when
applied to a Hamiltonian system, the discrete flow
$\phi_{\eta}:x\to\phi_{\eta}(x)$ is a Symplectic map for sufficient small step
sizes. In this paper we focus on the following Symplectic discretizations: for
$X=(x_{1},...,x_{n})^{\top},Y=(y_{1},...,y_{n})^{\top}$,

$\displaystyle Y^{t+1}=Y^{t}-\eta\nabla_{X}H(X^{t},Y^{t+1}),$ $\displaystyle
X^{t+1}=X^{t}+\eta\nabla_{Y}H(X^{t},Y^{t+1}),$ (Type I method)

or

$\displaystyle X^{t+1}=X^{t}+\eta\nabla_{Y}H(X^{t+1},Y^{t}),$ $\displaystyle
Y^{t+1}=Y^{t}-\eta\nabla_{X}H(X^{t+1},Y^{t}).$ (Type II method)

Both methods are Symplectic methods, i.e., they make the map
$(X^{t},Y^{t})\to(X^{t+1},Y^{t+1})$ to be symplectic. More details of
Symplectic method can be found in (Haier et al., 2006). Note that although
both methods are generally implicit, they become explicit when the Hamiltonian
function is separable, i.e., can be expressed as $H(X,Y)=f(X)+g(Y)$ with
functions f and g. This property holds for the Hamiltonian formulation of FTRL
dynamics.

##### Canonical coordinates of FTRL dynamics.

In this paper we will focus on the dynamics of cumulative strategy and
cumulative payoff. The cumulative strategy $X_{i}(t)$ of agent $i\in[2]$ is
defined as follows :

$X_{i}(t)=\int^{t}_{0}x_{i}(s)ds.$ (4)

(Bailey & Piliouras, 2019) demonstrates that (Continuous FTRL) can be
formulated as a Hamiltonian system through $(X_{i}(t),y_{i}(t))$ using the
Hamiltonian function

$\displaystyle
H(X_{i},y_{i})=h^{*}_{i}(y_{i}(t))+h^{*}_{j}(y_{j}(0)+A^{(ji)}X_{i}(t))$ (5)

for $j\neq i$ be the Hamiltonian function 111Intuitive explanation of this
Hamiltonian function can be found in Appendix A.1.. Thus $X_{i}(t)$ and
$y_{i}(t)$ evolve according to the following Hamiltonian system

$\frac{dX_{i}}{dt}=\frac{\partial H(X_{i},y_{i})}{\partial y_{i}},\ \ \
\frac{dy_{i}}{dt}=-\frac{\partial H(X_{i},y_{i})}{\partial X_{i}}.$ (6)

Following the tradition of Hamiltonian mechanics, we will refer to
$(X_{i}(t),y_{i}(t))$ for $i=1$ or $2$ as the canonical coordinates of FTRL
dynamics. This can be analogously understood as the position-momentum
coordinates used to describe the dynamic of a particle.

It may initially seem strange to trace the dynamics of players in a game based
on their cumulative strategies/payoffs rather than their actual strategies
$x_{i}(t)$. However, there is no loss in tracing these variables since
$y_{i}(t)$ can be translated into $x_{i}(t)$ through the map $\nabla
h^{*}(\cdot)$ introduced in (1), and $X_{i}(t)$ can be easily translated into
$y_{j}(t)$ through
$y_{j}(t)=y_{j}(t_{0})+A^{(ji)}\left(X_{i}(t)-X_{i}(t_{0})\right)$.

##### Primal-dual correspondence via discretization.

Since we use Euler and Symplectic discretization on the Hamiltonian system,
which is not obviously equivalent to the conventionally natural update rules
in the strategy spaces $\mathcal{X}_{i}$, we next establish formally that the
Euler or Symplectic discretization of continuous time FTRL with Euclidean norm
/ negative entropy regularizer implies GDA/MWU or AltGDA/AltMWU respectively.
This correspondence can be stated in the following proposition.

######  Proposition 3.1.

For each agent $i\in[2]$, let $\mathcal{X}_{i}$ denote the strategy spaces.
Then following statements holds:

  * •

If both players use Euclidean regularizers and
$\mathcal{X}_{i}={\mathbb{R}}^{n_{i}}$, then the Euler discretization of (6)
is equivalent to Gradient Descent-Ascent (GDA) on the strategy spaces; and the
Symplectic discretization of (6) is equivalent to Alternating Gradient
Descent-Ascent (AltGDA) on the strategy spaces.

  * •

If both players use entropy regularizers and $\mathcal{X}_{i}=\Delta_{i}$ be
the simplex, then the Euler discretization of (6) is equivalent to
Multiplicative Weights Update (MWU) on the strategy spaces; and the Symplectic
discretization of (6) is equivalent to Alternating Multiplicative Weights
Update (AltMWU) on the strategy spaces.

Here equivalent means the variables $(X^{t}_{i},y^{t}_{i})$ getting from the
discretizations is the same as the cumulative strategy and payoff of the game
dynamics.

It is known that Euler discretization significantly alters the properties of
continuous system (Holmes, 2007). This results the differences between
continuous FTRL and simultaneous plays. For example, continuous FTRL exhibits
cycle behaviors (Mertikopoulos et al., 2018) while simultaneous plays
typically diverge (Bailey & Piliouras, 2018). Compared to Euler discretization
, Symplectic discretization can preserve the structure of the continuous
system (Haier et al., 2006). Therefore, Proposition 3.1 suggests that

_The dynamical behaviors of alternating update rules should be consistent with
those of continuous learning dynamics._

An example of this phenomenon is (AltGDA) keeps the cycle behaviors of its
continuous partner (Bailey et al., 2020).

To prove Proposition 3.1, we introduce a novel method of discretizing the
continuous Hamiltonian system (6) by a combination of two types Symplectic
methods, while still keep the symplectic structures on the dynamics of each
agents. We believe this method is of independent interests. The detailed
proofs of Proposition 3.1 are deferred to Appendix A.

##### Random initialization.

We consider the case when noise is introduced to the canonical coordinates
$(X_{i}(t_{0}),y_{i}(t_{0}))$ at time moment $t_{0}>0$ in continuous FTRL or
$(X_{i}^{t_{0}},y_{i}^{t_{0}})$ in discrete time settings. The main objective
of this paper is to study the evolution of observer uncertainty given the
covariance matrix $P_{0}$ of the initialization $(X_{i}(t_{0}),y_{i}(t_{0}))$
or $(X_{i}^{t_{0}},y_{i}^{t_{0}})$. Take discrete time FTRL for example, the
covariance matrix $P_{0}$ consists of variances
$\mathrm{Var}(X_{i,\alpha}^{t_{0}})$, $\mathrm{Var}(y_{i,\alpha}^{t_{0}})$,
and covariances $\mathrm{Cov}(X_{i,\alpha}^{t_{0}},y_{i,\beta}^{t_{0}})$ for
all $\alpha,\beta\in[n_{i}]$ . Tracing the evolution of
$\mathrm{Var}(X_{i,\alpha}^{t})$ and $\mathrm{Var}(y_{i,\alpha}^{t})$ in
iterations, we are able to quantify how accurate the prediction will be in
FTRL dynamics.

##  4 Deficiency of Differential Entropy

Differential entropy, as a measure of observer uncertainty, was used in
studying the predictability of MWU in zero-sum games (Cheung et al., 2022). In
this section we investigate the evolution of differential entropy in FTRL with
differential discretization methods. In Proposition 4.1 we show that
differential entropy is insufficient in capturing the uncertainty evolution
for alternating plays.

######  Proposition 4.1.

When two players use (AltMWU) with arbitrary step size, the differential
entropy of their cumulative strategy and payoff keeps constant, i.e., if
$t>t_{0}$,

$\displaystyle S(X_{i}^{t},y_{i}^{t})=S(X_{i}^{t_{0}},y_{i}^{t_{0}}).$ (7)

######  Proposition 4.2.

When two players use (MWU) with step sizes $\eta<\min\\{1,1/\lVert
A\lVert_{2}^{2}\\}$, the differential entropy of their cumulative strategy and
payoff has linear growth rate, i.e.,

$\displaystyle S(X_{i}^{t},y_{i}^{t})\geq S(X_{i}^{t_{0}},y_{i}^{t_{0}})+ct$
(8)

where $c>0$ is a constant determined by payoff matrix $A$.

Different from the proof of (Cheung et al., 2022) for the differential entropy
evolution of (MWU), which relies a detailed calculation of the Jacobin map of
the dynamics, our proof of Proposition 4.1 is established based on the
relationship between Symplectic discretization and (AltMWU), as state in
Proposition 3.1. In fact, the evolution of differential entropy is determined
by the determinant of the Jacobin matrix of the update rule from
$(X_{i}^{t},y_{i}^{t})$ to $(X_{i}^{t+1},y_{i}^{t+1})$, and in each update,
the differential entropy is invariant if and only if the absolute value of
this determinant equals to $1$. As shown in Proposition 3.1, the update rule
of $(X_{i}^{t},y_{i}^{t})$ in (AltMWU) constitutes a symplectic map, and the
absolute value of the determinant of Jacobin matrix for every symplectic map
must equal to $1$, therefore we can conclude that the differential entropy in
(AltMWU) keeps a constant. The detailed proofs of Propositions 4.2 and 4.1 are
deferred to Appendix B, where we also provide numerical examples for these two
propositions.

##  5 Covariance in FTRL

In this section, we are presenting formally the evolution of covariances of
cumulative strategies and payoffs. We start with continuous time FTRL with
Euclidean regularizers, and proceed in considering Euler and Symplectic
discretization of continuous time FTRL. In the end, for general FTRL,
covariance evolution follows an inequality derived by using techniques of
symplectic geometry.

###  5.1 Covariance evolution in Euclidean regularizer.

The evolution of covariance matrix with continuous time FTRL can be deduced
from the Hamiltonian formulation of learning dynamics. The Euler
discretization of each agent’s continuous time FTRL exponentially amplifies
the covariance in the learning process. In contrast, symplectic
discretization, which has been proven equivalent to alternating update in
strategies, amplify covariance of cumulative strategies polynomially and keep
that of cumulative payoffs bounded. In this section we will focus on the view
point of agent 1, and the same results also hold for agent 2 as they are
symmetry.

######  Theorem 5.1.

In two-player zero-sum games, suppose both players use FTRL with Euclidean
norm regularizers and unconstrained strategy sets
$\mathcal{X}_{i}={\mathbb{R}}^{n_{i}}$. Suppose at time $t_{0}>0$ the random
cumulative strategy and payoff form a random vector
$\left(X_{i}^{t_{0}},y_{i}^{t_{0}}\right)$ with covariance matrix
$P(t_{0})\neq 0$. Then for all $t>t_{0}$ and
$\alpha,\beta\in\\{1,...,n_{1}\\}$, the covariance of
$\left(X_{i}^{t},y_{i}^{t}\right)$ evolves in continuous and discrete FTRL
according to the following :

  1. 1.

In Euler discretization, for all $\alpha,\beta\in[n_{1}]$, it holds that
$\mathrm{Cov}(X_{1,\alpha}^{t},X_{1,\beta}^{t})$, and
$\mathrm{Cov}(y_{1,\alpha}^{t},y_{1,\beta}^{t})$ are of
$\Theta\left((1+\gamma\eta^{2})^{2t}\right)$, where $\eta$ is the step size
and $\gamma$ is the maximal eigenvalue of $AA^{\top}$.

  2. 2.

In continuous time and symplectic discretization, for all
$\alpha,\beta\in[n_{1}]$, it holds that

     * •

if $AA^{\top}$ is non-singular, then
$\mathrm{Cov}(X_{1,\alpha}^{t},X_{1,\beta}^{t})$ and
$\mathrm{Cov}(y_{1,\alpha}^{t},y_{1,\beta}^{t})$ are of $\mathcal{O}(1)$.

     * •

if $AA^{\top}$ is singular, $\mathrm{Cov}(X_{1,\alpha}^{t},X_{1,\beta}^{t})$
is of $\Theta(t^{2})$, $\mathrm{Cov}(y_{1,\alpha}^{t},y_{1,\beta}^{t})$ is of
$\mathcal{O}(1)$.

Theorem 5.1 distinguishes clearly between the covariance evolution on Euler
discretization and Symplectic discretization: Euler discretization exhibits an
exponential growth rate, while Symplectic discretization maintains a quadratic
growth rate that matches the growth rate of the primary continuous dynamics.
Therefore, an observer can achieve higher prediction accuracy when players use
Symplectic discretization. The proof of Theorem 5.1 are deferred to Appendix
C, and experimental results are presented in Section 6.

The dependence on singularity of $AA^{\top}$ can be intuitively explained in
terms of the covariance evolution of the average strategies (i.e., $X^{t}/t$).
In an unconstrained zero-sum game, the average strategies of (AltGDA) will
converge to some equilibrium (Gidel et al., 2019a). When $AA^{\top}$ is non-
singular, the only equilibrium is the all-zero vector. The average strategy
converges to this point for all initial points, resulting in a small
covariance of average strategy and implying slow cumulative strategy growth.
However, when $AA^{\top}$ is singular, there exist multiple distinct
equilibria and the average strategy will converge towards these different
equilibrium. Consequently, throughout this process, the covariance of average
strategy remains substantial which leads to a large covariance of cumulative
strategy.

Theorem 5.1 also implies the following corollary regarding to the covariance
evolution of primal space. The proof is directly as in this case
$x^{t}_{i}=y^{t}_{i}$ holds. See Appendix A.4.

######  Corollary 5.2.

Under the same conditions as in Theorem 5.1, the covariance of the actual
strategy $x^{t}_{1}$ evolves as following : for all $\alpha,\beta\in[n_{1}]$

  1. 1.

In Euler discretization, it holds that
$\mathrm{Cov}(x_{1,\alpha}^{t},x_{1,\beta}^{t})$ is of
$\Theta\left((1+\gamma\eta^{2})^{2t}\right)$.

  2. 2.

In continuous time and symplectic discretization, it holds that
$\mathrm{Cov}(x_{1,\alpha}^{t},x_{1,\beta}^{t})$ is of $\mathcal{O}(1)$.

An immediate application of Theorem 5.1 is to utilize Chebyshev’s inequality
for predicting the quantitative measure of the risk associated with random
variables that deviate significantly from the expected value.

######  Corollary 5.3.

Let $k$ be any constant that is greater than 1, $X_{i,\alpha}(t)$ and
$y_{i,\alpha}(t)$ are cumulative strategy and payoffs of the $i$th agent with
respect to strategy $\alpha$ at time $t$. Then we have

$\displaystyle\text{Pr}\\{\left|X_{i,\alpha}(t)-\mu_{X}(t)\right|>k\sqrt{c}t\\}$
$\displaystyle<\frac{1}{k^{2}}$
$\displaystyle\text{Pr}\\{\left|y_{i,\alpha}(t)-\mu_{y}(t)\right|>k\\}$
$\displaystyle<\frac{c}{k^{2}}$

where $c$ is a constant, and $\mu_{X}(t)$ and $\mu_{y}(t)$ are expectations of
cumulative strategy and payoffs up to time $t$.

###  5.2 Covariance evolution with general regularizer.

So far we have left the evolution of covariance in continuous time FTRL with
general regularizers unaddressed. The challenge comes from the non-linearity
of Hamiltonian system induced by continuous time FTRL algorithm. Suppose the
integral flow of Hamiltonian system is $\phi_{t}(X_{i}(t_{0}),y_{i}(t_{0}))$.
In the most general setting, we are able to provide a lower bound for the
product of standard deviation of $X_{i,\alpha}(t)$ and $y_{i,\alpha}(t)$,
i.e., $\Delta X_{i,\alpha}(t)\Delta y_{i,\alpha}(t)\geq\text{constant}$. We
state the conditions and results formally in the following Theorem.

######  Theorem 5.4.

Let vector $X_{i}(t)$ and $y_{i}(t)$ be cumulative strategy and payoff, for
$i\in[2]$ and $\alpha\in[n_{i}]$. Assume that the higher order differentials
of $\phi_{t}(\cdot)$ are bounded by some constant $K$, and the standard
deviations $\Delta X_{i,\alpha}(t_{0})$ and $\Delta y_{i,\alpha}(t_{0})$ at
initial time $t_{0}$ are sufficient small,222”Sufficietly small” follows the
convention in statistical modeling, e.g. p166 in (Benaroya et al., 2005),
refer to Appendix D.3 for more details. then for $t>t_{0}$ it holds that

$\displaystyle\Delta X_{i,\alpha}(t)\Delta
y_{i,\alpha}(t)\geq\frac{1}{\sqrt{2}}\frac{w_{L}(P(t_{0}))}{\pi},$

where $w_{L}(P(t_{0}))$ is the linear Gromov width of the ellipsoid defined by
the initial covariance matrix $P(t_{0})$.

The definition of Gromov width can be found in Appendix D.2. Note that the
inequality holds trivially when there is no uncertainty, i.e., $P(t_{0})=0$,
since in this case $w_{L}^{2}(P(t_{0}))=0$. The necessary background and
details of proof are left in Appendix D.

Figure 3: Covariance evolution of $\Delta(X_{1,1}^{t})$ and
$\Delta(y_{1,1}^{t})$ when two players use (AltMWU) in a randomly generated
game. Covariance is calculate based on sample variance of 500 randomly
generated initial conditions.

The significance of Theorem 5.4 lies not only in providing a lower bound on
the covariance evolution of general FTRL dynamics. Similar to the _Heisenberg
Uncertainty Principle_ in quantum mechanics, Theorem 5.4 implies that it is
impossible for both $\Delta X_{i,\alpha}(t)$ and $\Delta y_{i,\alpha}(t)$ to
be simultaneously small. A numerical experiment illustrating this point is
presented in Figure 3. In this figure, it can be observed that when the curve
representing $\Delta X_{i,\alpha}(t)$ is on an increasing stage, the curve
representing $\Delta y_{i,\alpha}(t)$ is on an decreasing stage, and vice
versa. Moreover, the occurrence time of the local minima of
$\Delta(y_{1,1}(t))$ coincides with the local maxima of $\Delta(X_{1,1}(t))$.
This implies that $\Delta(X_{1,1}(t))$ and $\Delta(y_{1,1}(t))$ cannot be
small at the same time.

It is interesting to ask whether similar phenomena as in Theorem 5.4 occur in
the primal space $(x_{1}(t),x_{2}(t))$. In Figure 4, we demonstrate an
experiment on the covariance evolution in the primal space, and observe that
similar phenomena exist, at least when the number of pure strategies for
players is small. Further discussions can be found in Appendix D.4.

Figure 4: Covariance evolution on primal space. Calculate based on 100 random
samples of the initial mixed strategies used by two players when they employ
(AltMWU) in a randomly generated $3\times 3$ game.

##  6 Experiments

In this section we provide numerical experiments illustrating the covariance
evolution results proved for Euclidean norm regularized FTRL in Theorem 5.1.
More numerical experiments on the non-singular cases are presented in Appendix
E.

Continuous time FTRL. We illustrate how $\mathrm{Var}(X_{1,1}(t))$ and
$\mathrm{Var}(y_{1,1}(t))$ evolve with continuous time FTRL with payoff
matrices

$\displaystyle\cdot A_{1}=[[1,-1],[-1,1]],\ \cdot A_{2}=[[1.2,-1.2],[-1,1]]$
$\displaystyle\cdot A_{3}=[[1.5,-1.5],[-1,1]].$

See Figure 5. In (a), the $\mathrm{Var}(X_{1,1}(t))$ has a quadratic growth
rate, and in (b) $\mathrm{Var}(y_{1,1}(t))$ is bounded, which support results
of continuous time part in Theorem 5.1.

(a) $\mathrm{Var}(X_{1,1}(t))$

(b) $\mathrm{Var}(y_{1,1}(t))$

Figure 5: Variance evolution of continuous FTRL, singular cases.

Symplectic discretization. We illustrate how $\mathrm{Var}(X^{t}_{1,1})$ and
$\mathrm{Var}(y^{t}_{1,1})$ evolves with symplectic discretization, the payoff
matrices are given as follows:

$\displaystyle\cdot B_{1}=[[1,-1],[-1,1]],\ \cdot B_{2}=[[1.2,-1.2],[-1,1]]$
$\displaystyle\cdot B_{3}=[[1,-1.3],[-1,1.3]].$

See Figure 6. From the experimental results, we can see the variance behavior
of symplectic discretization is same as continuous case, which support results
of symplectic discretization part of Theorem 5.1.

(a) $\mathrm{Var}(X^{t}_{1,1})$

(b) $\mathrm{Var}(y^{t}_{1,1})$

Figure 6: Variance evolution of Symplectic discretization.

Euler discretization. We show experimental results on
$\mathrm{Var}(X^{t}_{1,1}),\mathrm{Var}(y^{t}_{1,1})$ where
$(X^{t}_{1},y^{t}_{1})$ evolve as Euler discretization and payoff matrices are
given as follows:

  * •

$C_{1}=[[1,-1.31],[-1,1.31]]$ is singular.

  * •

$C_{2}=[[2,-1.7],[-1.7,1.5]]$ is non-singular.

(a) $C_{1}$, singular

(b) $C_{2}$, non-singular

Figure 7: Variance evolution of Euler discretization.

In Figure 7 we can observe $\mathrm{Var}(X^{t}_{1,1})$ and
$\mathrm{Var}(y^{t}_{1,1})$ exhibit an exponential growth rate which support
the result of Euler discretization part in Theorem 5.1. As shown in Appendix
5.1, the function of the covariance evolution process contains polynomials
combinations of trigonometric functions, which cause the oscillations in
Figure 7.

##  7 Conclusion

In this paper we investigate the evolution of observer uncertainty in learning
dynamics from a covariance perspective. We prove concrete rates of covariance
evolution for different discretization schemes of FTRL dynamics and establish
a Heisenberg-type uncertainty inequality that constrains the predictive
ability of an observer. In our analysis, we leverage the techniques from
symplectic geometry for analyzing the evolution of uncertainty, which to the
best of our knowledge is the first of its kind. An interesting direction is to
extend current results for different classes of games (e.g. potential games,
multiplayer games).

## Acknowledgments

Xiao Wang acknowledges Grant 202110458 from Shanghai University of Finance and
Economics and support from the Shanghai Research Center for Data Science and
Decision Technology.

## Impact Statement

This paper presents work whose goal is to advance the field of Machine
Learning. There are many potential societal consequences of our work, none
which we feel must be specifically highlighted here.

## References

  * Abernethy et al. (2009) Abernethy, J. D., Hazan, E., and Rakhlin, A.  Competing in the dark: An efficient algorithm for bandit linear optimization.  2009\.
  * Arnold (2013) Arnold, V. I.  _Mathematical methods of classical mechanics_ , volume 60.  Springer Science & Business Media, 2013.
  * Bailey & Piliouras (2019) Bailey, J. and Piliouras, G.  Muti-agent learning in network zero-sum games is a hamiltonian system.  In _AAMAS_ , 2019.
  * Bailey & Piliouras (2018) Bailey, J. P. and Piliouras, G.  Multiplicative weights update in zero-sum games.  In _Proceedings of the 2018 ACM Conference on Economics and Computation_ , pp. 321–338, 2018.
  * Bailey et al. (2020) Bailey, J. P., Gidel, G., and Piliouras, G.  Finite regret and cycles with fixed step-size via alternating gradient descent-ascent.  In _Conference on Learning Theory_ , pp. 391–407. PMLR, 2020.
  * Benaroya et al. (2005) Benaroya, H., Han, S. M., and Nagurka, M.  _Probability models in engineering and science_ , volume 192.  CRC press, 2005.
  * Bronson (1991) Bronson, R.  _Matrix methods: An introduction_.  Gulf Professional Publishing, 1991.
  * Brown & Sandholm (2018) Brown, N. and Sandholm, T.  Superhuman ai for heads-up no-limit poker: Libratus beats top professionals.  _Science_ , 359(6374):418–424, 2018.
  * Busch et al. (2007) Busch, P., Heinonen, T., and Lahti, P.  Heisenberg’s uncertainty principle.  _Physics reports_ , 452(6):155–176, 2007.
  * Cesa-Bianchi & Lugosi (2006) Cesa-Bianchi, N. and Lugosi, G.  _Prediction, learning, and games_.  Cambridge university press, 2006.
  * Cevher et al. (2023) Cevher, V., Cutkosky, A., Kavis, A., Piliouras, G., Skoulakis, S., and Viano, L.  Alternation makes the adversary weaker in two-player games.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Cheung et al. (2022) Cheung, R. K., Piliouras, G., and Tao, Y.  The evolution of uncertainty of learning in games.  In _ICLR_ , 2022.
  * Colonius & Kliemann (2014) Colonius, F. and Kliemann, W.  _Dynamical systems and linear algebra_ , volume 158.  American Mathematical Society, 2014.
  * (14) Conrad, B.  Higher derivatives and taylor’s formula via multilinear maps.  In _http://math.stanford.edu/ conrad/diffgeomPage/handouts/taylor.pdf_.
  * Daskalakis et al. (2018) Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, H.  Training gans with optimism.  _ICLR_ , 2018.
  * Feutrill & Roughan (2021) Feutrill, A. and Roughan, M.  A review of shannon and differential entropy rate estimation.  _Entropy_ , 23(8):1046, 2021.
  * Galla & Farmer (2013) Galla, T. and Farmer, J. D.  Complex dynamics in learning complicated games.  _Proceedings of the National Academy of Sciences_ , 110(4):1232–1236, 2013.
  * Gidel et al. (2019a) Gidel, G., Berard, H., Vignoud, G., Vincent, P., and Lacoste-Julien, S.  A variational inequality perspective on generative adversarial networks.  _ICLR_ , 2019a.
  * Gidel et al. (2019b) Gidel, G., Hemmat, R. A., Pezeshki, M., Le Priol, R., Huang, G., Lacoste-Julien, S., and Mitliagkas, I.  Negative momentum for improved game dynamics.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pp. 1802–1811. PMLR, 2019b.
  * Goodfellow et al. (2014) Goodfellow, I. J., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y.  Generative adversarial nets.  In _Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2_ , NIPS’14, pp. 2672–2680, Cambridge, MA, USA, 2014. MIT Press.
  * Gromov (1985) Gromov, M.  Pseudo holomorphic curves in symplectic manifolds.  _Inventiones Mathematicae_ , 82,307-347, 1985.
  * Haier et al. (2006) Haier, E., Lubich, C., and Wanner, G.  _Geometric Numerical integration: structure-preserving algorithms for ordinary differential equations_.  Springer, 2006.
  * Holmes (2007) Holmes, M. H.  _Introduction to numerical methods in differential equations_.  Springer, 2007.
  * Hong & Horn (1991) Hong, Y. and Horn, R. A.  The jordan cononical form of a product of a hermitian and a positive semidefinite matrix.  _Linear Algebra and its Applications_ , 147:373–386, 1991.
  * Horn & Johnson (2012) Horn, R. A. and Johnson, C. R.  _Matrix analysis_.  Cambridge university press, 2012.
  * Hsiao & Scheeres (2006) Hsiao, F.-Y. and Scheeres, D. J.  Fundamental constraints on uncertainty evolution in hamiltonian systems.  In _2006 American Control Conference_ , pp. 6–pp. IEEE, 2006.
  * Hyvärinen (1997) Hyvärinen, A.  New approximations of differential entropy for independent component analysis and projection pursuit.  _Advances in neural information processing systems_ , 10, 1997.
  * Lanctot et al. (2017) Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Pérolat, J., Silver, D., and Graepel, T.  A unified game-theoretic approach to multiagent reinforcement learning.  _Advances in neural information processing systems_ , 30, 2017.
  * McDuff & Salamon (2017) McDuff, D. and Salamon, D.  _Introduction to symplectic topology_ , volume 27.  Oxford University Press, 2017.
  * Mertikopoulos & Sandholm (2018) Mertikopoulos, P. and Sandholm, W. H.  Riemannian game dynamics.  _Journal of Economic Theory_ , 177:315–364, 2018.
  * Mertikopoulos et al. (2018) Mertikopoulos, P., Papadimitriou, C., and Piliouras, G.  Cycles in adversarial regularized learning.  In _SODA_ , 2018.
  * Nachbar (1997) Nachbar, J. H.  Prediction, optimization, and learning in repeated games.  _Econometrica: Journal of the Econometric Society_ , pp. 275–309, 1997.
  * Sato et al. (2002) Sato, Y., Akiyama, E., and Farmer, J. D.  Chaos in learning a simple two-person game.  _Proceedings of the National Academy of Sciences_ , 99(7):4748–4751, 2002.
  * Shalev-Shwartz & Singer (2006) Shalev-Shwartz, S. and Singer, Y.  Convex repeated games and fenchel duality.  _Advances in neural information processing systems_ , 19, 2006.
  * Shalev-Shwartz et al. (2012) Shalev-Shwartz, S. et al.  Online learning and online convex optimization.  _Foundations and Trends® in Machine Learning_ , 4(2):107–194, 2012.
  * Shannon (1948) Shannon, C. E.  A mathematical theory of communication.  _The Bell system technical journal_ , 27(3):379–423, 1948.
  * Silver et al. (2016) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484–489, 2016.
  * Vilone et al. (2011) Vilone, D., Robledo, A., and Sánchez, A.  Chaos and unpredictability in evolutionary dynamics in discrete time.  _Physical review letters_ , 107(3):038101, 2011.
  * Wang (1994) Wang, D.  Some aspects of hamiltonian systems and symplectic algorithms.  _Physica D: Nonlinear Phenomena_ , 73(1-2):1–16, 1994.
  * Wibisono et al. (2022) Wibisono, A., Tao, M., and Piliouras, G.  Alternating mirror descent for constrained min-max games.  _Advances in Neural Information Processing Systems_ , 35:35201–35212, 2022.
  * Yang & Wang (2020) Yang, Y. and Wang, J.  An overview of multi-agent reinforcement learning from game theoretical perspective.  _arXiv preprint arXiv:2011.00583_ , 2020.
  * Zhou (2018) Zhou, X.  On the fenchel duality between strong convexity and lipschitz continuous gradient.  _arXiv preprint arXiv:1803.06573_ , 2018.

##  Appendix A Proof of Proposition 3.1

###  A.1 Hamiltonian formulation of FTRL

We first recall the Hamiltonian formulation of continuous FTRL in zero sum
game from (Bailey & Piliouras, 2019).

The Hamiltonian function $H(X_{1},y_{1})$ for agent $1$ is defined to be

$\displaystyle
H(X_{1},y_{1})=h^{*}_{1}(y_{1}(t))+h^{*}_{2}(y_{2}(0)+A^{(21)}X_{1}(t)),$ (9)

and the Hamiltonian function $H(X_{2},y_{2})$ for agent $2$ is defined to be

$\displaystyle
H(X_{2},y_{2})=h^{*}_{2}(y_{2}(t))+h^{*}_{1}(y_{1}(0)+A^{(12)}X_{2}(t)),$ (10)

where $h^{*}_{i}$ is the regularizer used by agent $i$, $i=1,2$.

Theorem 3.2 of (Bailey & Piliouras, 2019) shows the dynamical behaviors of
$(X_{i}(t),y_{i}(t))$ are completely determined by these two Hamiltonian
functions. A similar non-canonical Hamiltonian system formulation (also known
as a Possion system) for continuous time mirror descent algorithms is also
presented in (Wibisono et al., 2022). Theorem 5.1 of (Bailey & Piliouras,
2019) demonstrates that the Hamiltonian function defined here is inherently
connected to the Bregman divergence, which is a commonly used concepts in
optimization, plus a an additional term determined by the regularizers and
equilibrium of the game.

More precisely, (Bailey & Piliouras, 2019) was shown that the cumulative
strategies and payoffs of agent $1$, $(X_{1},y_{1})$, of continuous FTRL for
agent 1 satisfies the following equations:

$\displaystyle\frac{d}{dt}X_{1}(t)=\frac{\partial H}{\partial
y_{1}}(X_{1},y_{1})=\nabla h^{*}_{1}(y_{1}(t)),$ (11)
$\displaystyle\frac{d}{dt}y_{1}(t)=-\frac{\partial H}{\partial
X_{1}}(X_{1},y_{1})=A^{(12)}\nabla h^{*}_{2}(y_{2}(0)+A^{(21)}X_{2}(t)).$ (12)

Similarly results also hold for agent $2$, $(X_{2},y_{2})$, of continuous FTRL
for agent 2 satisfies the following equations:

$\displaystyle\frac{d}{dt}X_{2}(t)=\frac{\partial H}{\partial
y_{2}}(X_{2},y_{2})=\nabla h^{*}_{2}(y_{2}(t)),$ (13)
$\displaystyle\frac{d}{dt}y_{2}(t)=-\frac{\partial H}{\partial
X_{2}}(X_{2},y_{2})=A^{(21)}\nabla h^{*}_{1}(y_{1}(0)+A^{(12)}X_{1}(t)).$ (14)

The proof of Proposition 3.1 is divided into two parts :

  * •

The proof of entropy regularizers is presented in Section A.3,

  * •

The proof of Euclidean norm regularizers is presented in Section A.4,

and in Section A.2, we introduce the Euler and Symplectic discretization of
FTRL.

###  A.2 Euler and Symplectic discretization of FTRL

Both in Euler and Symplectic, we denote the initial condition of the discrete
equation on $(X^{t}_{i},y^{t}_{i}),\ i=1,2$ to be $y^{0}_{i}=y_{i}(0)$ and
$X^{0}_{i}=0$.

######  Lemma A.1 (Euler discretization of FTRL).

Discretizing equation (6) with Euler method for both agent $i=1,2$ gives

$\displaystyle X^{t+1}_{1}=X^{t}_{1}+\eta\frac{\partial H}{\partial
y_{1}}(X^{t}_{1},y^{t+1}_{1})=X^{t}_{1}+\eta\nabla h^{*}_{1}(y^{t}_{1}),$
(agent 1 Euler discretize equation) $\displaystyle
y^{t+1}_{1}=y^{t}_{1}-\eta\frac{\partial H}{\partial
X_{1}}(X^{t}_{1},y^{t}_{1})=y^{t}_{1}+\eta A^{(12)}\nabla
h^{*}_{2}(y^{0}_{2}+A^{(21)}X^{t}_{1}),$

and

$\displaystyle X^{t+1}_{2}=X^{t}_{2}+\eta\frac{\partial H}{\partial
y_{2}}(X^{t}_{2},y^{t}_{2})=X^{t}_{2}+\eta\nabla h^{*}_{2}(y^{t}_{2}),$ (
agent 2 Euler discretize equation) $\displaystyle
y^{t+1}_{2}=y^{t}_{1}-\eta\frac{\partial H}{\partial
X_{2}}(X^{t+1}_{2},y^{t}_{2})=y^{t}_{2}+\eta A^{(21)}\nabla
h^{*}_{1}(y^{0}_{1}+A^{(12)}X^{t}_{2}).$

###### Proof.

Note that in Euler discretization, we use the derivative on point of $t$-th
round to find the point of $t+1$ round. Thus (agent 1 Euler discretize
equation) directly follows from applying Euler discretization to 11 and 12.
Similarly, (agent 2 Euler discretize equation) directly follows from applying
Euler discretization to 13 and 14. ∎

######  Lemma A.2 (Symplectic discretization of FTRL).

Discretizing (6) for $i=1$ with I-type Euler symplectic method (3) gives

$\displaystyle y^{t+1}_{1}=y^{t}_{1}-\eta\frac{\partial H}{\partial
X_{1}}(X^{t}_{1},y^{t}_{1})=y^{t}_{1}+\eta A^{(12)}\nabla
h^{*}_{2}(y^{0}_{2}+A^{(21)}X^{t}_{1})$ (agent 1 Symplectic discretize
equation) $\displaystyle X^{t+1}_{1}=X^{t}_{1}+\eta\frac{\partial H}{\partial
y_{1}}(X^{t}_{1},y^{t+1}_{1})=X^{t}_{1}+\eta\nabla h^{*}_{1}(y^{t+1}_{1})$

and discrete (6) for $i=2$ with II-type Euler symplectic method (3)gives

$\displaystyle X^{t+1}_{2}=X^{t}_{2}+\eta\frac{\partial H}{\partial
y_{2}}(X^{t}_{2},y^{t}_{2})=X^{t}_{2}+\eta\nabla h^{*}_{2}(y^{t}_{2})$ (agent
2 Symplectic discretize equation) $\displaystyle
y^{t+1}_{2}=y^{t}_{1}-\eta\frac{\partial H}{\partial
X_{2}}(X^{t+1}_{2},y^{t}_{2})=y^{t}_{2}+\eta A^{(21)}\nabla
h^{*}_{1}(y^{0}_{1}+A^{(12)}X^{t+1}_{2})$

###### Proof.

(agent 1 Symplectic discretize equation) directly follows from applying (3) to
equation 11 and 12. Similarly, (agent 2 Symplectic discretize equation)
directly follows from applying (3) to equation 13 and 14. ∎

We define $(x^{t}_{1},x^{t}_{2})$ to be

$\displaystyle x^{t}_{1}=\frac{X^{t+1}_{1}-X^{t}_{1}}{\eta},\
x^{t}_{2}=\frac{X^{t+1}_{2}-X^{t}_{2}}{\eta}.$ (15)

In the case of Euler discretization of FTRL (Lemma A.1), we have

$\displaystyle x^{t}_{1}=\nabla h^{*}_{1}(y^{t}_{1}),\ x^{t}_{2}=\nabla
h^{*}_{2}(y^{t}_{2}),$ (16)

and in the case of Symplectic discretization of FTRL (Lemma A.2), we have

$\displaystyle x^{t}_{1}=\nabla h^{*}_{1}(y^{t+1}_{1}),\ x^{t}_{2}=\nabla
h^{*}_{2}(y^{t}_{2}).$ (17)

Note that in Symplectic method, $x^{t}_{1}$ is determined by $y_{1}^{t+1}$,
but in Euler method, $x^{t}_{1}$ is determined by $y_{1}^{t}$.

In the following, we will show $(x^{t}_{1},x^{t}_{2})$ evolves as (MWU) under
Euler method or (AltMWU) under Symplectic method on the strategy space if the
regularizers $h_{i}(\cdot)$ are choose to be entropy functions, and the
constrained sets $\mathcal{X}_{i}$ are chosen to be simplexes for $i=1,2$,
this exactly the second part of Proposition 3.1.

######  Lemma A.3.

Both in Euler discretization of FTRL dynamics and Symplectic discretization of
FTRL dynamics, the equalities

$\displaystyle y^{n}_{1}=y^{0}_{1}+A^{(12)}X^{n}_{2}$ (18) $\displaystyle
y^{n}_{2}=y^{0}_{2}+A^{(21)}X^{n}_{1}$ (19)

hold for any $n\geq 0$.

###### Proof.

Here we only prove the case of Symplectic discretization of FTRL dynamics, as
the case of Euler discretization of FTRL dynamics is similar. We prove this by
induction. For $n=0$, (18) and (19) are

$\displaystyle y^{0}_{1}=y^{0}_{1}+A^{(12)}X^{0}_{2}$ (20) $\displaystyle
y^{0}_{2}=y^{0}_{2}+A^{(21)}X^{0}_{1},$ (21)

which hold trivially since by definition $X^{0}_{1}=X^{0}_{2}=0$.

Now assume (18) and (19) hold for $n$, i.e,

$\displaystyle y^{n}_{1}=y^{0}_{1}+A^{(12)}X^{n}_{2}$ (22) $\displaystyle
y^{n}_{2}=y^{0}_{2}+A^{(21)}X^{n}_{1}.$ (23)

Then, we have

$\displaystyle y^{n+1}_{1}$ $\displaystyle=y^{n}_{1}+\eta A^{(12)}\nabla
h^{*}_{2}(y^{0}_{2}+A^{(21)}X^{n}_{1})$ (24)
$\displaystyle\overset{(\ref{yX2n})}{=}y^{n}_{1}+\eta A^{(12)}\nabla
h^{*}_{2}(y^{n}_{2})$ (25) $\displaystyle=y^{n}_{1}+\eta A^{(12)}x^{n}_{2}$
(26) $\displaystyle\overset{(\ref{yX1n})}{=}y^{0}_{1}+A^{(12)}X^{n}_{2}+\eta
A^{(12)}x^{n}_{2}$ (27) $\displaystyle=y^{0}_{1}+A^{(12)}X^{n+1}_{2}.$ (28)

Moreover, we have

$\displaystyle y^{n+1}_{2}$ $\displaystyle=y^{n}_{2}+\eta A^{(21)}\nabla
h^{*}_{1}(y^{0}_{1}+A^{(12)}X^{n+1}_{2})$ (29)
$\displaystyle\overset{(\ref{yX1n+1})}{=}y^{n}_{2}+\eta A^{(21)}\nabla
h^{*}_{1}(y^{n+1}_{1})$ (30) $\displaystyle=y^{n}_{2}+\eta A^{(21)}x^{n}_{1}$
(31) $\displaystyle\overset{(\ref{yX2n})}{=}y^{0}_{2}+A^{(21)}X^{n}_{1}+\eta
A^{(21)}x^{n}_{1}$ (32) $\displaystyle=y^{0}_{1}+A^{(21)}X^{n+1}_{1}$ (33)

This finish the proof. ∎

###  A.3 Proof of Entropy regularizers

######  Lemma A.4.

For entropy regularizer $h(x)=\sum^{n}_{i=1}x_{i}\ln x_{i}$ with simplex
constrain, i.e.,
$\Delta=\\{x\in{\mathbb{R}}^{n}|\sum^{n}_{i=1}x_{i}=1,x_{i}\geq 0\\}$, we have

$\displaystyle\nabla
h^{*}(y)=\left(\frac{e^{y_{i}}}{\sum^{n}_{s=1}e^{y_{s}}}\right)^{n}_{i=1}.$
(34)

###### Proof.

By the definition, $h^{*}(y)=\max_{x\in\Delta}(\langle x,y\rangle-h(x)),$ and
$\nabla h^{*}(y)=\arg\max_{x\in\Delta}(\langle x,y\rangle-h(x)).$

Denote $f(x)=\left(\langle x,y\rangle-h(x)\right)$, by the KKT condition, if
$x^{*}$ is the maximum of $f$, then there exist $\mu_{i}$ and $\lambda$ such
that

$-\nabla f(x^{*})+\sum_{i=1}^{n}\mu_{i}\nabla g_{i}(x^{*})+\lambda\nabla
h(x^{*})=0$

and

$\displaystyle g_{i}(x^{*})=-x^{*}_{i}\leq 0\ \ \text{for all}\ \ i\in[n],$
$\displaystyle h(x^{*})=\sum_{i=1}^{n}x_{i}^{*}-1=0,$
$\displaystyle\mu_{i}g_{i}(x^{*})=0\ \ \text{for all}\ \ i\in[n].$

Since the gradient of $f$ can be computed to be

$\nabla f(x)=y-(\log x_{1}+1,...,\log x_{n}+1),$

the KKT condition becomes

$-y+(\log x_{1}+1,...,\log
x_{n}+1)+\sum_{i=1}^{n}\mu_{i}(0,...,-1,...,0)+\lambda(1,...,1)=0.$

Suppose the feasible $x^{*}$ is interior point of $\Delta$, i.e., $x_{i}>0$,
then we have for all $i\in[n]$, $\mu_{i}=0$. Then the KKT condition is reduced
to the following equations $\log x_{i}+1+\lambda=y_{i}\ \ \text{for all}\ \
i\in[n],\sum_{i=1}^{n}x_{i}=1.$ This gives solution of $x_{i}$ and $\lambda$:

$\displaystyle x_{i}=\frac{e^{y_{i}}}{\sum_{s=1}^{n}e^{y_{s}}}\ \ \text{for
all}\ \ i\in[n],\ \ \lambda=\log\left(\sum_{s=1}^{n}e^{y_{s}}\right)-1,$

thus we have completed the proof. ∎

######  Lemma A.5.

The $(x^{t}_{1},x^{t}_{2})$ in (16) with entropy regularizer is the same as
(MWU).

###### Proof.

In (16), we have $x^{t}_{1}=\nabla h^{*}_{1}(y^{t}_{1})$, thus

$\displaystyle x^{t}_{1}$ $\displaystyle=\nabla h^{*}_{1}(y^{t}_{1})$ (35)
$\displaystyle\overset{(\ref{nablaentropy})}{=}\left(\frac{e^{y^{t}_{1,s}}}{\sum^{n_{1}}_{j=1}e^{y^{t}_{1,j}}}\right)^{n_{1}}_{s=1}$
(37)
$\displaystyle\overset{(\ref{yX1})}{=}\left(\frac{e^{y^{0}_{1,s}+(A^{(12)}X^{t}_{2})_{s}}}{\sum^{n_{1}}_{j=1}e^{y^{0}_{1,j}+(A^{(12)}X^{t}_{2})_{j}}}\right)^{n_{1}}_{s=1}$
(39)
$\displaystyle=\left(\frac{e^{y^{0}_{1,s}+\eta(A^{(12)}\sum^{t-1}_{k=1}x^{k}_{2})_{s}}}{\sum^{n_{1}}_{j=1}e^{y^{0}_{1,j}+\eta(A^{(12)}\sum^{t-1}_{k=1}x^{k}_{2})_{j}}}\right)^{n_{1}}_{s=1}$
(41)
$\displaystyle=\left(\frac{x^{t-1}_{1,s}e^{\eta(A^{(12)}x^{t-1}_{2})_{s}}}{\sum^{n_{1}}_{j=1}x^{t-1}_{1,j}e^{\eta(A^{(12)}x^{t-1}_{2})_{j}}}\right)^{n_{1}}_{s=1}.$
(43)

The case of 2 agent is exactly same as 1 agent as they are symmetry, and we
have

$\displaystyle x^{t}_{2}$
$\displaystyle=\left(\frac{x^{t-1}_{2,s}e^{\eta(A^{(21)}x^{t-1}_{2})_{s}}}{\sum^{n_{2}}_{j=1}x^{t-1}_{2,j}e^{\eta(A^{(21)}x^{t-1}_{2})_{j}}}\right)^{n_{2}}_{s=1}.$
(44)

That is same as (MWU) . ∎

######  Lemma A.6.

The $(x^{t}_{1},x^{t}_{2})$ in (17) with entropy regularizer is the same as
(AltMWU).

###### Proof.

For 1 agent, from (17), we have $x^{t}_{1}=\nabla h^{*}_{1}(y^{t+1}_{1})$,
thus

$\displaystyle x^{t}_{1}$ $\displaystyle=\nabla h^{*}_{1}(y^{t+1}_{1})$ (45)
$\displaystyle\overset{(\ref{nablaentropy})}{=}\left(\frac{e^{y^{t+1}_{1,s}}}{\sum^{n_{1}}_{j=1}e^{y^{t+1}_{1,j}}}\right)^{n_{1}}_{s=1}$
(47)
$\displaystyle\overset{(\ref{yX1})}{=}\left(\frac{e^{y^{0}_{1,s}+(A^{(12)}X^{t+1}_{2})_{s}}}{\sum^{n_{1}}_{j=1}e^{y^{0}_{1,j}+(A^{(12)}X^{t+1}_{2})_{j}}}\right)^{n_{1}}_{s=1}$
(49)
$\displaystyle=\left(\frac{e^{y^{0}_{1,s}+\eta(A^{(12)}\sum^{t}_{k=1}x^{k}_{2})_{s}}}{\sum^{n_{1}}_{j=1}e^{y^{0}_{1,j}+\eta(A^{(12)}\sum^{t}_{k=1}x^{k}_{2})_{j}}}\right)^{n_{1}}_{s=1}$
(51)
$\displaystyle=\left(\frac{x^{t-1}_{1,s}e^{\eta(A^{(12)}x^{t}_{2})_{s}}}{\sum^{n_{1}}_{j=1}x^{t-1}_{1,j}e^{\eta(A^{(12)}x^{t}_{2})_{j}}}\right)^{n_{1}}_{s=1}.$
(53)

Note that the update rule of $x^{t}_{1}$ use $x^{t}_{2}$, this is a
characteristic of (AltMWU).

For 2 agent, from (17) we have $x^{t}_{2}=\nabla h^{*}_{2}(y^{t}_{2})$, thus

$\displaystyle x^{t}_{2}$ $\displaystyle=\nabla h^{*}_{2}(y^{t}_{2})$ (54)
$\displaystyle=\left(\frac{e^{y^{t}_{2,s}}}{\sum^{n_{2}}_{j=1}e^{y^{t}_{2,j}}}\right)^{n_{2}}_{s=1}$
(56)
$\displaystyle\overset{(\ref{yX2})}{=}\left(\frac{e^{y^{0}_{2,s}+(A^{(21)}X^{t}_{1})_{s}}}{\sum^{n_{2}}_{j=1}e^{y^{0}_{2,j}+(A^{(21)}X^{t}_{1})_{j}}}\right)^{n_{2}}_{s=1}$
(58)
$\displaystyle=\left(\frac{e^{y^{0}_{2,s}+\eta(A^{(21)}\sum^{t-1}_{k=1}x^{k}_{1})_{s}}}{\sum^{n_{2}}_{j=1}e^{y^{0}_{2,j}+\eta(A^{(21)}\sum^{t-1}_{k=1}x^{k}_{1})_{j}}}\right)^{n_{2}}_{s=1}$
(60)
$\displaystyle=\left(\frac{x^{t-1}_{2,s}e^{\eta(A^{(21)}x^{t-1}_{1})_{s}}}{\sum^{n_{2}}_{j=1}x^{t-1}_{2,j}e^{\eta(A^{(21)}x^{t-1}_{1})_{j}}}\right)^{n_{2}}_{s=1}.$
(62)

Combine (62) and (53), we can see the update rule of $(x_{1}^{t},x_{2}^{t})$
is same as (AltMWU) . ∎

Combine Lemma A.5 and Lemma A.6, we proved the second part of Proposition 3.1.
The first part is very similar, except the regularizers are changed to
Euclidian norm. However, this change will not affect the proof, so we omit it
here.

###  A.4 Proof of Euclidean norm regularizers

Note that for Euclidean norm regularizers, i.e., $h_{i}(x)=\lVert
x\lVert^{2}$, we have

$\displaystyle\nabla h^{*}_{i}(y)=\arg\max_{x\in{\mathbb{R}}^{n}}\\{\langle
x,y\rangle-\lVert x\lVert^{2}\\}=y.$ (63)

######  Lemma A.7.

The $(x^{t}_{1},x^{t}_{2})$ in (16) with Euclidean norm regularizer is the
same as (GDA).

###### Proof.

For agent 1, we have

$\displaystyle x^{t}_{1}\overset{(\ref{sse})}{=}\nabla
h^{*}_{1}(y_{1}^{t})\overset{(\ref{eunabla})}{=}y^{t}_{1}=x_{1}^{t-1}+\eta\cdot
A^{(12)}x_{2}^{t-1}.$ (64)

Agent 2 is exactly same as agent 1 since in Euler method, two agent are
symmetry. Thus we have shown the update rule of $(x^{t}_{1},x^{t}_{2})$ is
same as (GDA). ∎

######  Lemma A.8.

The $(x^{t}_{1},x^{t}_{2})$ in (17) with Euclidean norm regularizer is the
same as (AltGDA).

###### Proof.

For agent 1, we have

$\displaystyle x^{t}_{1}\overset{(\ref{sss})}{=}\nabla
h^{*}_{1}(y_{1}^{t+1})\overset{(\ref{eunabla})}{=}y^{t+1}_{1}=x_{1}^{t-1}+\eta\cdot
A^{(12)}x_{2}^{t}.$ (65)

For agent 2, we have

$\displaystyle x^{t}_{2}\overset{(\ref{sss})}{=}\nabla
h^{*}_{1}(y_{2}^{t})\overset{(\ref{eunabla})}{=}y^{t}_{2}=x_{2}^{t-1}+\eta\cdot
A^{(21)}x_{2}^{t-1}.$ (66)

Thus we have shown the update rule of $(x^{t}_{1},x^{t}_{2})$ is same as
(AltGDA).

∎

##  Appendix B Proof of Section 4

In this appendix we prove results in Section 4. Proposition 4.2 is proved in
Section B.3, and Proposition 4.1 is proved in Section B.4. In fact, we prove a
more general result, which states that when two players choose arbitrary
regularizers that satisfies strongly convex and Lipschitz gradient condition
except a bounded region on the domain, then the differential entropy of Euler
discretization has linear growth rate, while differential entropy of
Symplectic discretization keeps constant. Note that both Euclidian norm
regularizer and entropy regularizer satisfy these conditions, for example,
entropy regularizer is 1-strongly convex on the interior points of simplex and
has Lipschitz gradient except an arbitrary small neighbourhood of zero point.

The main technical lemma for proving Proposition 4.2 is Lemma B.6, which
states for sufficient small step size, the update rule of Euler discretization
of FTRL is an injective map. This injective property is necessary for
calculating the evolution of differential entropy, see Lemma B.1. The proof of
Proposition 4.1 is easier, as the symplectic discretization is naturally an
injective map.

###  B.1 Evolution of differential entropy under diffeomorphism

The following result and its proof are informally stated in (Cheung et al.,
2022), for convenience of applying their statement later, we formulate it into
a lemma as follows.

######  Lemma B.1.

Let $X\in{\mathbb{R}}^{d}$ be a random vector with probability density
function $g(x)$ and the support set of $g(x)$ is $\mathcal{X}$. Assume
$f:{\mathbb{R}}^{d}\to{\mathbb{R}}^{d}$ be a diffeomorphism, thus $f(X)$ is a
random vector. Then we have

$\displaystyle S(f(X))=S(X)+\int_{\mathcal{X}}g(x)\log\left(\lvert\det
J_{f}(x)\lvert\right)dx$ (67)

where $J_{f}(x)$ is the Jacobian matrix of $f$ at point
$x\in{\mathbb{R}}^{d}$.

###### Proof.

Denote $Y=f(X)$, and let $\widehat{g}(Y)$ represent the probability density
function of $Y$, and $\mathcal{Y}$ be the support set of $Y$.

Then we have

$\displaystyle S(Y)$
$\displaystyle=S(f(X))=-\int_{\mathcal{Y}}\widehat{g}(y)\cdot\log\left(\widehat{g}(y)\right)dy$
(68) $\displaystyle=-\int_{\mathcal{Y}}g\left(f^{-1}(y)\right)\lvert\det
J_{f^{-1}}(y)\lvert\cdot\log\left(g(f^{-1}(y))\lvert\det
J_{f^{-1}}(y)\lvert\right)dy$ (69)
$\displaystyle=-\int_{\mathcal{X}}g(x)\lvert\det
J_{f^{-1}}\left(f(x)\right)\lvert\cdot\log\left(g(x)\lvert\det
J_{f^{-1}}(f(x))\lvert\right)\cdot\lvert\det J_{f}(x)\lvert dx$ (70)
$\displaystyle=-\int_{\mathcal{X}}g(x)\cdot\log\left(g(x)\lvert\det
J_{f^{-1}}(f(x))\lvert\right)dx$ (71)
$\displaystyle=-\int_{\mathcal{X}}g(x)\log\left(g(x)\right)dx-\int_{\mathcal{X}}g(x)\log\left(\lvert\det
J_{f^{-1}}\left(f(x)\right)\lvert\right)dx$ (72)
$\displaystyle=S(X)+\int_{\mathcal{X}}g(x)\log\left(\lvert\det
J_{f}(x)\lvert\right)dx,$ (73)

where (71) comes from the inverse function theorem, which states

$\displaystyle J_{f^{-1}}\left(f(x)\right)=\left(J_{f}(x)\right)^{-1}.$ (74)

∎

###  B.2 Technical lemmas for Proposition 4.2

We first present several lemmas used later.

######  Lemma B.2 (Corollary 2.2 and 2.3 of (Hong & Horn, 1991)).

Let $A,B\in{\mathbb{R}}^{n\times n}$ be symmetry and positive semidefinite.
Then $AB$ is diagonalizable and has nonnegative eigenvalues. Moreover, if $A$
is positive definite, then the number of positive eigenvalues, negative
eigenvalues, and $0$ eigenvalues of $AB$ are the same as $B$.

######  Lemma B.3.

If $A\in{\mathbb{R}}^{n\times n}$ is a symmetry matrix, and $\lambda$ is an
eigenvalue of $A$, then $\lambda^{2}$ is an eigenvalue of $A^{2}$.

###### Proof.

Since $A$ is a symmetry matrix, there is an invertible matrix $P$ makes

$\displaystyle P\cdot A\cdot P^{-1}=\begin{bmatrix}\lambda_{1}&&\\\
&\ddots&\\\ &&\lambda_{n}\end{bmatrix},$ (75)

where $\lambda_{1},...,\lambda_{n}$ are eigenvalues of $A$. Thus

$\displaystyle P\cdot(A)^{2}\cdot P^{-1}$ $\displaystyle=\left(P\cdot A\cdot
P^{-1}\right)\cdot\left(P\cdot A\cdot P^{-1}\right)$ (76)
$\displaystyle=\begin{bmatrix}(\lambda_{1})^{2}&&\\\ &\ddots&\\\
&&(\lambda_{n})^{2}\end{bmatrix},$ (77)

this implies $\\{\lambda^{2}_{i}\\}$ are eigenvalues of $A^{2}$. ∎

The following lemma is the standard Fenchel duality property, a proof can be
found in Theorem 1 (Zhou, 2018).

######  Lemma B.4.

Let $h:\mathcal{X}\to{\mathbb{R}}$ be a $\mu$-strongly convex function with
$L$-Lipschitz continuous gradient, let

$\displaystyle h^{*}(y)=\max_{x\in\mathcal{X}}\\{\langle x,y\rangle-h(x)\\}$
(78)

be the convex conjugate of $h$, then we have

  * (1)

$h^{*}$ is a $\frac{1}{L}$-strongly convex function.

  * (2)

$h^{*}$ has $\frac{1}{\mu}$-Lipschitz continuous gradient.

######  Lemma B.5.

Let $f:{\mathbb{R}}^{n}\to{\mathbb{R}}^{n}$ be a differentiable function on a
convex set $U\subset{\mathbb{R}}^{n}$, and

$\displaystyle\lVert J_{f}(x)-I\lVert<1$ (79)

for any $x\in U$, where $\lVert\cdot\lVert$ is the $L^{2}$-operator norm, then
$f$ is an injective map.

###### Proof.

Let $g(x)=f(x)-x$. Then for any $x\neq y$, we have

$\displaystyle\lVert f(x)-f(y)+y-x\lVert$ $\displaystyle=\lVert
g(x)-g(y)\lVert$ (80) $\displaystyle=\lVert J_{g}(\zeta)(x-y)\lVert$ (81)
$\displaystyle\leq\lVert J_{g}(\zeta)\lVert\cdot\lVert x-y\lVert$ (82)
$\displaystyle<\lVert x-y\lVert,$ (83)

where (81) use the mean value theorem, and (83) is due to the fact that
$\lVert J_{g}(\zeta)\lVert<1$ for any $\zeta\in U$. Thus $f(x)\neq f(y)$. ∎

######  Lemma B.6.

If the step size $\eta<\min\\{\mu_{1},\mu_{2}/\lVert A^{(21)}\lVert^{2}\\}$,
then the iterate map

$\displaystyle\phi:(X_{1}^{n},y_{1}^{n})\to(X_{1}^{n+1},y_{1}^{n+1})$ (84)

of Euler discretization of FTRL in Lemma A.1 is an injective function.

###### Proof.

Recall the iterate map
$\phi:(X_{1}^{n},y_{1}^{n})\to(X_{1}^{n+1},y_{1}^{n+1})$ can be written as an
Euler discretization with the following form

$\displaystyle y^{n+1}_{1}=y^{n}_{1}-\eta\cdot\frac{\partial H}{\partial
X_{1}}(X^{n}_{1},y^{n}_{1})$ (85) $\displaystyle
X^{n+1}_{1}=X^{n}_{1}+\eta\cdot\frac{\partial H}{\partial
y_{1}}(X^{n}_{1},y^{n}_{1})$ (86)

and the Hamiltonian function has form

$\displaystyle
H(X_{1},y_{1})=h^{*}_{1}(y_{1})+h^{*}_{2}(y_{2}(0)+A^{(21)}X_{1}).$ (87)

Note that $H_{1}(X_{1},y_{1})$ is separable, i.e., $h^{*}_{1}(\cdot)$ is
independent with $X_{1}$ and $h^{*}_{2}(\cdot)$ is independent with $y_{1}$,
thus we have

$\displaystyle\frac{\partial^{2}H}{\partial X_{1}\partial y_{1}}=0,\
\frac{\partial^{2}H}{\partial y_{1}\partial X_{1}}=0.$ (88)

Next we calculate the Jacobin matrix of $\phi$,

$\displaystyle J_{\phi}=\begin{bmatrix}\frac{\partial
y^{n+1}_{1}}{\partial{y^{n}_{1}}}&\frac{\partial
y^{n+1}_{1}}{\partial{X^{n}_{1}}}\\\ \\\ \\\ \frac{\partial
X^{n+1}_{1}}{\partial{y^{n}_{1}}}&\frac{\partial
X^{n+1}_{1}}{\partial{X^{n}_{1}}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}I-\eta\frac{\partial^{2}H}{\partial
y_{1}\partial
X_{1}}(X^{n}_{1},y^{n}_{1})&-\eta\frac{\partial^{2}H}{\partial^{2}X_{1}}(X^{n}_{1},y^{n}_{1})\\\
\\\ \\\ \\\
\eta\frac{\partial^{2}H}{\partial^{2}y_{1}}(X^{n}_{1},y^{n}_{1})&I+\eta\frac{\partial^{2}H}{\partial
X_{1}\partial y_{1}}(X^{n}_{1},y^{n}_{1})\end{bmatrix}$ (89)
$\displaystyle=\begin{bmatrix}I&-\eta(A^{(21)})^{\top}\cdot\nabla^{2}h^{*}_{2}\cdot
A^{(21)}\\\ \\\ \\\ \eta\nabla^{2}h^{*}_{1}&I\end{bmatrix},$ (90)

and

$\displaystyle
J_{\phi}-I=\begin{bmatrix}0&-\eta(A^{(21)})^{\top}\cdot\nabla^{2}h^{*}_{2}\cdot
A^{(21)}\\\ \\\ \\\ \eta\nabla^{2}h^{*}_{1}&0\end{bmatrix}.$ (91)

Since $h_{i}$ is $\mu_{i}$-strongly convex, by Lemma B.4, $h^{*}_{i}$ has
$\frac{1}{\mu_{i}}$-Lipschitz continuous gradient, thus we have

$\displaystyle\lVert\nabla^{2}h^{*}_{i}\lVert\leq\frac{1}{\mu_{i}}$ (92)

holds at arbitrary points within the domain of $h^{*}_{i}$.

Next we estimate the $L^{2}$-operator norm of the matrix $J_{\phi}-I$, since
the $L^{2}$-operator norm is equivalent to the spectral norm, we have

$\displaystyle\lVert J_{\phi}-I\lVert$
$\displaystyle=\sqrt{\lambda_{\max}\left((J_{\phi}-I)^{\top}\cdot(J_{\phi}-I)\right)},$
(93)

and

$\displaystyle(J_{\phi}-I)^{\top}\cdot(J_{\phi}-I)$
$\displaystyle=\eta^{2}\cdot\begin{bmatrix}\left(\nabla^{2}h^{*}_{1}\right)^{2}&0\\\
\\\ 0&\left((A^{(21)})^{\top}\cdot\nabla^{2}h^{*}_{2}\cdot
A^{(21)}\right)^{2}\end{bmatrix}.$ (94)

Since both $\nabla^{2}h^{*}_{1}$ and
$(A^{(21)})^{\top}\cdot\nabla^{2}h^{*}_{2}\cdot A^{(21)}$ are symmetry matrix,
thus by Lemma B.3, eigenvalues of $(J_{\phi}-I)^{\top}\cdot(J_{\phi}-I)$ has
form $\eta^{2}\lambda^{2}$, where $\lambda$ is an eigenvalue of
$\nabla^{2}h^{*}_{1}$ or $(A^{(21)})^{\top}\cdot\nabla^{2}h^{*}_{2}\cdot
A^{(21)}$.

Note that $h^{*}_{i}$ is a function of $X_{1},y_{1}$, thus $\lambda$ is also a
function of $X_{1},y_{1}$, and it is not clear whether there is an upper bound
on $\lambda$ without more information on the Hessian matrix of $h^{*}_{i}$.
However, as we have shown in (92), the $L^{2}$-operator norm of
$\nabla^{2}h^{*}_{i}$ has an upper bound $\frac{1}{\mu_{i}}$, thus we have

$\displaystyle 0\leq\lambda<\max\left\\{\frac{1}{\mu_{1}},\frac{\lVert
A^{(21)}\lVert^{2}}{\mu_{2}}\right\\}.$ (95)

Thus we can choose $\eta<\min\left\\{\mu_{1},\frac{\mu_{2}}{\lVert
A^{(21)}\lVert^{2}}\right\\}$ to make

$\displaystyle\lVert J_{\phi}-I\lVert<1,$ (96)

and by Lemma B.5, $\phi$ is an injective map. ∎

###  B.3 Proof of Proposition 4.2

###### Proof.

By Lemma B.6, the iterate map of simultaneous FTRL is an diffeomorphism, thus
we can use Lemma B.1 to calculate the evolution of differential entropy in
simultaneous FTRL. We firstly prove differential entropy is a non-decrease
function.

Recall (9), the Hamiltonian function of FTRL is

$\displaystyle
H(X^{t}_{1},y^{t}_{1})=h^{*}_{1}(y^{t}_{1})+h^{*}_{2}(y^{0}_{2}+A^{(21)}X^{t}_{1}),$
(97)

and the iterate map $\phi:(y_{1}^{n},X^{1}_{n})\to(y_{1}^{n+1},X^{n+1}_{1})$
of simultaneous FTRL can be written as Euler discretization of continuous
FTRL, i.e.,

$\displaystyle y^{t+1}_{1}$ $\displaystyle=y^{t}_{1}-\eta\cdot\frac{\partial
H}{\partial X_{1}}(X^{t}_{1},y^{t}_{1})$ (98) $\displaystyle X^{t+1}_{1}$
$\displaystyle=X^{t}_{1}+\eta\cdot\frac{\partial H}{\partial
y_{1}}(X^{t}_{1},y^{t}_{1}).$ (99)

Recall from (90), the jacobian map of $\phi$ is

$\displaystyle
J_{\phi}(X,y)=\begin{bmatrix}I&-\eta(A^{(21)})^{\top}\cdot\nabla^{2}h^{*}_{2}(X,y)\cdot
A^{(21)}\\\ \\\ \\\ \eta\nabla^{2}h^{*}_{1}(X,y)&I\end{bmatrix},$ (100)

thus

$\displaystyle\det\left(J_{\phi}(X,y)\right)=\det\left(I+\eta^{2}\cdot\nabla^{2}h^{*}_{1}(X,y)\cdot(A^{(21)})^{\top}\cdot\nabla^{2}h^{*}_{2}(X,y)\cdot
A^{(21)}\right).$ (101)

Since $\nabla^{2}h^{*}_{1}$ and
$(A^{(21)})^{\top}\cdot\nabla^{2}h^{*}_{2}\cdot A^{(21)}$ are both symmetry
and positive semidefinite matrix, by Lemma B.2, their product is
diagonalizable and has non-negative eigenvalues. Thus we have

$\displaystyle\det\left(J_{\phi}(X,y)\right)\geq 1.$ (102)

Combine this with (67), we have

$\displaystyle S(X^{t+1}_{1},y^{t+1}_{1})$
$\displaystyle=S\left(\phi(X^{t+1}_{1},y^{t+1}_{1})\right)$ (103)
$\displaystyle=S(X^{t}_{1},y^{t}_{1})+\int_{\mathcal{X}}g^{t}(X^{t}_{1},y^{t}_{1})\log\left(\lvert\det
J_{\phi}(X^{t}_{1},y^{t}_{1})\lvert\right)dX^{t}_{1}dy^{t}_{1}$ (104)
$\displaystyle\geq
S(X^{t}_{1},y^{t}_{1})+\int_{\mathcal{X}}g^{t}(X^{t}_{1},y^{t}_{1})\log(1)dX^{t}_{1}dy^{t}_{1}$
(105) $\displaystyle=S(X^{t}_{1},y^{t}_{1}),$ (106)

where $g^{t}(\cdot)$ is the probability density function of
$(X^{t}_{1},y^{t}_{1})$, and (105) comes from
$\det\left(J_{\phi}(X,y)\right)\geq 1$. Thus $S(X^{t}_{1},y^{t}_{1})$ is a
non-decreasing function.

Moreover, as $\log(1+x)>x/(1+x)$ for $x>0$, thus from (104), to prove a linear
growth rate of differential entropy, it is sufficient to prove a uniform lower
bound on $\det\left(J_{\phi}(X,y)\right)$. With the assumption that
$h_{i}(\cdot)$ has Lipschitz continuous gradient, by Lemma B.4,
$h_{i}^{*}(\cdot)$ is $\mu_{i}$-strongly convex, thus
$\nabla^{2}h^{*}_{i}(X,y)$ is positive definite, i.e.,

$\displaystyle\nabla^{2}h^{*}_{i}(X,y)\succcurlyeq\mu_{i}I$ (107)

for some $\mu_{i}>0$. From Lemma B.2, with $A=\nabla^{2}h^{*}_{1}(X,y)$ and
$B=(A^{(21)})^{\top}\cdot\nabla^{2}h^{*}_{2}(X,y)\cdot A^{(21)}$, we have

$\displaystyle\eta^{2}\cdot\nabla^{2}h^{*}_{1}(X,y)\cdot(A^{(21)})^{\top}\cdot\nabla^{2}h^{*}_{2}(X,y)\cdot
A^{(21)}$ (108)

is a diagonalizable matrix, and there are all eigenvalues of $J_{\phi}(X,y)$
are real number and larger than $1$. Moreover, these eigenvalues has a uniform
lower bound $1+c$, where $c$ is determined by the strongly convex coefficients
$\mu_{i}$ and the payoff matrix $A^{(21)}$. ∎

###  B.4 Proof of Proposition 4.1

######  Lemma B.7.

The update map

$(X_{1}^{t},y_{1}^{t})\to(X_{1}^{t+1},y_{1}^{t+1})$

from (agent 1 Symplectic discretize equation) is an injective map.

###### Proof.

Recall the update rule can be written as

$\displaystyle y^{t+1}_{1}=y^{t}_{1}-\eta\frac{\partial H}{\partial
X_{1}}(X^{t}_{1},y^{t}_{1})=y^{t}_{1}+\eta A^{(12)}\nabla
h^{*}_{2}(y^{0}_{2}+A^{(21)}X^{t}_{1}),$ (109) $\displaystyle
X^{t+1}_{1}=X^{t}_{1}+\eta\frac{\partial H}{\partial
y_{1}}(X^{t}_{1},y^{t+1}_{1})=X^{t}_{1}+\eta\nabla h^{*}_{1}(y^{t+1}_{1}).$
(110)

Thus given $(X_{1}^{t+1},y_{1}^{t+1})$, we can directly find an unique
$X^{t}_{1}$ from (110), i.e.,

$X^{t}_{1}=X^{t+1}_{1}-\eta\nabla h^{*}_{1}(y^{t+1}_{1}).$

Then use this $X^{t}_{1}$, we can also determine a unique $y^{t}_{1}$ from
(109), i.e.,

$y^{t}_{1}=y^{t+1}_{1}-\eta A^{(12)}\nabla
h^{*}_{2}(y^{0}_{2}+A^{(21)}X^{t}_{1}).$

This finish the proof. ∎

Now we are ready to prove Proposition 4.1.

###### Proof.

Since the iterate map $\psi:(X_{1}^{n},y_{1}^{n})\to(X_{1}^{n+1},y_{1}^{n+1})$
in Symplectic discretization of FTRL defined A.2 in is naturally an injective
map from Lemma B.7 , we can directly use lemma B.1. We have

$\displaystyle
S(X_{1}^{n+1},y_{1}^{n+1})-S(X_{1}^{n},y_{1}^{n})=\int_{\mathcal{X}}g^{n}(X_{1}^{n},y_{1}^{n})\log\left(\lvert\det
J_{\phi}(X_{1}^{n},y_{1}^{n})\lvert\right)dx$ (112)

where $g^{n}(\cdot)$ is the probability density function of random vector
$(X_{1}^{n},y_{1}^{n})$.

Moreover, since $\psi$ is a symplectomorphism, we have $\lvert\det
J_{\psi}(X_{1}^{n},y_{1}^{n})\lvert=1.$ Thus the right hand side of (112)
equals to $0$, and this implies
$S(X_{1}^{n+1},y_{1}^{n+1})=S(X_{1}^{n},y_{1}^{n})$. ∎

###  B.5 Numerical examples of Proposition Propositions 4.2 and 4.1

Although differential entropy plays important roles in several subjects,
estimating the value of differential entropy under transformations is
generally a challenging task. Even in the one-dimensional case, special
methods need to be designed for calculating differential entropy (Hyvärinen,
1997). A recent review of this topic can be found in (Feutrill & Roughan,
2021).

However, for the case of gradient descent, it is possible to calculate the
variation of differential entropy due to the linear structure of the algorithm
and the equality

$\displaystyle S(AX)-S(X)=\log(\lvert\det(A)\lvert).$ (113)

In Figure 2, we present numerical experiments on the variation of differential
entropy using game defined by $A=[[1,-1],[-1,1]]$. Numerical results show
differential entropy has a linear growth rate in simultaneous case and keeps
invariant in alternating case, which support Propositions 4.2 and 4.1.

Figure 8: Variation of differential entropy for simultaneous and alternating
GDA. The growth rate of the variation in DE is linear for simultaneous GDA,
while it is $0$ for alternating GDA.

##  Appendix C Proof of Theorem 5.1

This appendix is divided into two parts. In Section C.1, we presented
necessary backgrounds from linear algebra, differential equation, and
difference equation. In Section C.2, we provide detailed prove of Theorem 5.1.

###  C.1 Additional Backgrounds

####  C.1.1 Complex Jordan normal form

We will consider the complex Jordan normal form of a real square matrix
$A\in{\mathbb{R}}^{d\times d}$. Let ${\mathrm{Spec}}(A)$ be the set of
eigenvalues of $A$. Consider $A$ acts on vector space ${\mathbb{C}}^{d}$ as a
linear operator.

######  Definition C.1 (Generalized Eigenvector).

A vector $v_{m}\in{\mathbb{C}}^{d}$ is called a generalized eigenvector of
type $m$ corresponding to the eigenvalue $\mu$ if

$(A-\lambda I)^{m}v_{m}=0$

but

$(A-\mu I)^{m-1}v_{m}\neq 0.$

######  Definition C.2 (Jordan Chain).

let $v_{m}$ be a generalized eigenvector of type m corresponding to the matrix
$A$ and the eigenvalue $\mu$. The Jordan chain generated by $v_{m}$ is a set
of m vectors $\\{v_{m},v_{m-1},...,v_{1}\\}$ given by

$\displaystyle v_{m-1}$ $\displaystyle=(A-\mu I)v_{m}$ $\displaystyle v_{m-2}$
$\displaystyle=(A-\mu I)^{2}v_{m}=(A-\mu I)v_{m-1}$ $\displaystyle...$
$\displaystyle v_{1}$ $\displaystyle=(A-\mu I)^{m-1}v_{m}=(A-\mu I)v_{2}$

######  Remark C.3.

If $\mu\in{\mathbb{R}}$ is a real eigenvalue of $A$, then the generalized
eigenvectors of $\mu$ are also vectors over real numbers, and the Jordan chain
are also made up by vectors over real numbers.

######  Proposition C.4.

A Jordan chain is a linearly independent set of vectors.

###### Proof.

Let $\\{v_{m},v_{m-1},...,v_{1}\\}$ be a Jordan chain generated by a type $m$
generalized eigenvector $v_{m}$ corresponding to an eigenvalue $\lambda$ of
$A$, and consider the equation

$\displaystyle c_{m}v_{m}+c_{m-1}v_{m-1}+...+c_{1}v_{1}=0$ (114)

We will show $c_{m}=c_{m-1}=...=c_{1}=0$.

Multiply equation 114 by $(A-\mu I)^{m-1}$, and note that for $j\leq m-1$

$\displaystyle(A-\mu I)^{m-1}c_{j}v_{j}$ $\displaystyle=c_{j}(A-\mu
I)^{m-j-1}(A-\mu I)^{j}x_{j}$ $\displaystyle=0$

Thus equation 114 becomes to be $c_{m}(A-\mu I)^{m-1}v_{m}=0$. However, since
$v_{m}$ is a type $m$ generalized eigenvector, we have

$(A-\mu I)^{m-1}v_{m}\neq 0,$

thus $c_{m}=0$. Continuing this process, we will finally obtain
$c_{m}=c_{m-1}=...=c_{1}=0$. ∎

######  Proposition C.5 (page 366 of (Bronson, 1991) ).

Every $d\times d$ matrix has $d$ linearly independent generalized
eigenvectors.

Given a Jordan chain $\\{v_{1},v_{2},...,v_{m}\\}$ of length $m$, by
Proposition C.4, we will get a subspace spans by
$\\{v_{1},v_{2},...,v_{m}\\}$. The linear operator
$A:{\mathbb{C}}^{d}\to{\mathbb{C}}^{d}$ can acts on vectors’ set
$\\{v_{1},v_{2},...,v_{m}\\}$.

Denote $[v_{1},v_{2},....,v_{m}]$ to be the matrix consists of column vectors
$\\{v_{1},v_{2},...,v_{m}\\}$, then $A$ acts on $[v_{1},v_{2},....,v_{m}]$ as

$\displaystyle A[v_{1},v_{2},....,v_{m}]$
$\displaystyle=[Av_{1},Av_{2},...,Av_{m}]$ $\displaystyle=[\mu v_{1},v_{1}+\mu
v_{2},...,v_{m-1}+\mu v_{m}]$
$\displaystyle=[v_{1},v_{2},...,v_{m}]\begin{bmatrix}\mu&1&\\\ &\mu&1&\\\
&&\ddots&\ddots\\\ &&&\mu&1\\\ &&&&\mu\\\ \end{bmatrix}.$

Thus we have

$\displaystyle[v_{1},v_{2},....,v_{m}]^{-1}A[v_{1},v_{2},....,v_{m}]=\begin{bmatrix}\mu&1&\\\
&\mu&1&\\\ &&\ddots&\ddots\\\ &&&\mu&1\\\ &&&&\mu\\\ \end{bmatrix}$ (115)

which is a $m\times m$ upper triangular matrix, with eigenvalue $\mu$ on
diagonal and each non-zero off-diagonal entry equal to 1. Such an upper
triangular matrix is called a size m Jordan block of $A$ corresponding to
eigenvalue $\mu$.

######  Proposition C.6 (Page 367 of (Bronson, 1991)).

Every $d\times d$ matrix $A$ has a set of $d\times d$ linearly independent
generalized eigenvectors composed entirely of Jordan chains, such a set of
generalized eigenvectors is a called a canonical bases of $A$.

######  Definition C.7 (Generalized modal matrix).

Let $A$ be an $d\times d$ matrix. A generalized modal matrix $M$ for $A$ is a
$d\times d$ matrix whose columns, considered as vectors, form a canonical
basis for $A$ and appear in $M$ according to the following rules:

  * (1)

All vectors of the same chain appear together in adjacent columns of $M$.

  * (2)

Each chain appears in $M$ in order of increasing type.

######  Remark C.8.

The Jordan chain corresponding to a real eigenvalue $\mu\in{\mathbb{R}}$ of
$A$ will composed by vectors in ${\mathbb{R}}^{d}$, but if
$\mu\in{\mathbb{C}}$ is a complex eigenvalue of $A$, then the Jordan chain
corresponding to $\mu$ will contain vectors in ${\mathbb{C}}^{d}$.

Combine equation 115 and Proposition C.6, we have following proposition.

######  Proposition C.9.

Any matrix $A\in{\mathbb{R}}^{d\times d}$ is similar to a matrix in Jordan
normal form under the similarity transformation of a generalized modal matrix
$M$ of $A$, i.e.,

$J^{{\mathbb{C}}}=M^{-1}AM$

has block diagonal form $J^{{\mathbb{C}}}=\oplus_{i}J_{i}$ with Jordan blocks
$J_{i}$ given with $\mu\in{\mathrm{Spec}}(A)$ by

$J_{i}=\begin{bmatrix}\mu&1&\\\ &\mu&1&\\\ &&\ddots&\ddots\\\ &&&\mu&1\\\
&&&&\mu\\\ \end{bmatrix}.$

The Jordan normal form is unique up to the order of the Jordan blocks.

We have the following proposition that determines the number of a particular
size of Jordan blocks in Jordan normal form corresponding to an eigenvalue
$\lambda$ .

######  Proposition C.10 (Page 368 of (Bronson, 1991)).

Let $\lambda$ be an eigenvalue of $A$, and denote

$m=\max\\{i|\ \ker(A-\mu I)^{i}\varsupsetneqq\ker(A-\mu I)^{i-1}\\}.$

Denote $\rho_{k}$ as the number of linear independent generalized eigenvectors
of type $k$ corresponding to the eigenvalue $\mu$ that appear in a canonical
basis for $A$, then

$\rho_{k}=\dim\ker(A-\mu I)^{k}-\dim\ker(A-\mu I)^{k-1}\ (k=1,2,...,m).$

Since every Jordan chains of length $k$ in a canonical basis gives a size $k$
Jordan block, $\rho_{k}$ is also the number of size $k$ Jordan blocks in the
complex Jordan normal form corresponding to $\lambda$.

There is another characterization on the size of the largest Jordan block
corresponding eigenvalue based on the minimal polynomial of $A$:

######  Proposition C.11 (Theorem 3.3.6 in (Horn & Johnson, 2012)).

Let $m$ be the size of the largest Jordan block corresponding to the
eigenvalue $\mu$ of a matrix $A$, then $m$ equals to the degree of the factor
$(x-\mu)$ in the minimal polynomial of $A$.

####  C.1.2 Real Jordan normal form

The real Jordan normal is important for computing exponential function of a
matrix $A\in{\mathbb{R}}^{d\times d}$. In the complex Jordan form, Jordan
blocks may contain elements in ${\mathbb{C}}-{\mathbb{R}}$. Thus for a matrix
$A\in{\mathbb{R}}^{d\times d}$, we cannot use its complex Jordan normal form
to calculate exponential functions of $A$ directly. We need to define a
standard form of $A$, which should only contain real numbers and keep the
shape as a diagonal block matrix. This motive the definition of real Jordan
normal form.

Let $\mu={\mathrm{Re}}(\mu)+i{\mathrm{Im}}(\mu),{\mathrm{Im}}(\mu)\neq 0$ be
an eigenvalue of $A$, and $v_{m}\in{\mathbb{C}}^{d}$ is a generalized
eigenvalue of type $m$ corresponding to $\mu$. Then the complex conjugate of
$\mu$, denote by $\bar{\mu}$, is also an eigenvalue of $A$, and the complex
conjugate of $v_{m}$, denote by $\bar{v}_{m}\in{\mathbb{C}}^{d}$ is a
generalized eigenvalue of type $m$ corresponding to $\bar{\mu}$. Let

$\\{v_{m-i}|\ v_{m-i}=(A-\mu I)^{i}v_{m},\ i=0,1,...,m-1\\}$

be a Jordan chain of length $m$ corresponding to $\lambda$, then it gives a
complex Jordan block of size $m$ in the complex Jordan normal form of $A$ as
in equation 115.

The $2m$ vectors
$\\{{\mathrm{Re}}(v_{1}),{\mathrm{Im}}(v_{1}),{\mathrm{Re}}(v_{2}),{\mathrm{Im}}(v_{2}),...,{\mathrm{Re}}(v_{m}),{\mathrm{Im}}(v_{m})\\}\subset{\mathbb{R}}^{d}$
will play the role of complex generalized vectors of eigenvalues
$\mu,\bar{\mu}$. It is directly to check $A$ acts on
$[{\mathrm{Re}}(v_{1}),{\mathrm{Im}}(v_{1}),{\mathrm{Re}}(v_{2}),{\mathrm{Im}}(v_{2}),...,{\mathrm{Re}}(v_{m}),{\mathrm{Im}}(v_{m})]$
gives the following matrix representation :

$\displaystyle
A[{\mathrm{Re}}(v_{1}),{\mathrm{Im}}(v_{1}),{\mathrm{Re}}(v_{2}),{\mathrm{Im}}(v_{2}),...,{\mathrm{Re}}(v_{m}),{\mathrm{Im}}(v_{m})]$
$\displaystyle=[A{\mathrm{Re}}(v_{1}),A{\mathrm{Im}}(v_{1}),A{\mathrm{Re}}(v_{2}),A{\mathrm{Im}}(v_{2}),...,A{\mathrm{Re}}(v_{m}),A{\mathrm{Im}}(v_{m})]$
$\displaystyle=[{\mathrm{Re}}(\mu v_{1}),{\mathrm{Im}}(\mu
v_{1}),{\mathrm{Re}}(v_{1})+{\mathrm{Re}}(\mu
v_{2}),{\mathrm{Im}}(v_{1})+{\mathrm{Im}}(\mu
v_{2}),...,{\mathrm{Re}}(v_{m-1})+{\mathrm{Re}}(\mu
v_{m}),{\mathrm{Im}}(v_{m-1})+{\mathrm{Im}}(\mu v_{m})]$
$\displaystyle=[{\mathrm{Re}}(v_{1}),{\mathrm{Im}}(v_{1}),{\mathrm{Re}}(v_{2}),{\mathrm{Im}}(v_{2}),...,{\mathrm{Re}}(v_{m}),{\mathrm{Im}}(v_{m})]\begin{bmatrix}D&I\\\
&\cdot&\cdot\\\ &&\cdot&\cdot&\\\ &&&\cdot&\cdot&\\\ &&&&\cdot&I\\\ &&&&&D\\\
\end{bmatrix}$

where $D=\begin{bmatrix}{\mathrm{Re}}(\mu)&{\mathrm{Im}}(\mu)\\\ \\\
-{\mathrm{Im}}(\mu)&{\mathrm{Re}}(\mu)\end{bmatrix}$ and
$I_{2}=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}.$

The matrix

$\displaystyle\begin{bmatrix}D&I\\\ &\cdot&\cdot\\\ &&\cdot&\cdot&\\\
&&&\cdot&\cdot&\\\ &&&&\cdot&I\\\ &&&&&D\\\ \end{bmatrix}$ (116)

is called the real Jordan blocks corresponding to a conjugate pair of image
eigenvalues $\mu,\bar{\mu}$.

As in the case of complex Jordan normal form, we need to define the real
generalized modal matrix, and under the similar transformation by real
generalized modal matrix, the original matrix will be transformed into a real
Jordan normal form.

######  Definition C.12 (Real generalized modal matrix).

Let $A$ be an $d\times d$ matrix. A real generalized modal matrix $M$ for $A$
is a $d\times d$ matrix whose columns, considered as vectors, are real or
image parts of a complex generalized eigenvectors in a canonical basis for $A$
and appear in $M$ according to the following rules:

  * (1)

Real and image parts of a generalized eigenvectors corresponding to same image
eigenvalues appear in the first columns of $M$

  * (2)

If ${\mathrm{Re}}(v),{\mathrm{Im}}(v)$ appear in the real generalized modal
matrix, $({\mathrm{Re}}(v),{\mathrm{Im}}(v))$ appear in adjacent columns of
$M$

  * (3)

All vectors of the same chain appear together in adjacent columns of $M$.

  * (4)

Each chain appears in $M$ in order of increasing type.

Note that comparing to definition C.7, the new requirements are $(1)$ and
$(2)$. $(1)$ will make the Jordan blocks as in equation 116 appear firstly in
the real Jordan normal form, and the necessary of $(2)$ can be seen from the
derivation of equation 116.

######  Proposition C.13 ( Theorem 1.2.3 in (Colonius & Kliemann, 2014)).

Any matrix $A\in{\mathbb{R}}^{d\times d}$ is similar to a matrix in the real
Jordan normal from via a similarity transformation by $A$’s real generalized
modal matrix. That is, $\exists M\in{\mathbb{R}}^{d\times d}$ be $A$’s real
generalized modal matrix to make

$J^{{\mathbb{R}}}=M^{-1}AM$

where $J^{{\mathbb{R}}}=(J_{\mu_{1},\bar{\mu}_{1}}\oplus...\oplus
J_{\mu_{k},\bar{\mu}_{k}})\oplus^{l}_{i=1}(J_{\mu_{k+i}})$ with real Jordan
blocks given for $\mu\in{\mathrm{Spec}}({\mathcal{L}})\cap{\mathbb{R}}$ by

$J_{\mu}=\begin{bmatrix}\mu&1&\\\ &\mu&1&\\\ &&\ddots&\ddots\\\ &&&\mu&1\\\
&&&&\mu\\\ \end{bmatrix}$

and for $\mu,\bar{\mu}=\lambda\pm
i\nu\in{\mathrm{Spec}}({\mathcal{L}}),\nu>0$, by

$J_{\mu,\bar{\mu}}=\begin{bmatrix}D&I_{2}&\cdot&\cdot&0\\\ 0&D&&&.\\\
\cdot&\ddots&\ddots&.\\\ \cdot&&&D&I_{2}\\\ 0&&&0&D\end{bmatrix}$

where $D=\begin{bmatrix}\lambda&-\nu\\\ \nu&\lambda\end{bmatrix}$ and
$I_{2}=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$.

Note that the difference between complex and real Jordan form, complex and
real generalized modal matrix are only in the Jordan blocks corresponding to a
eigenvalue whose image part is not $0$. Thus the number of a given size Jordan
blocks corresponding to a real eigenvalue is same in complex and real Jordan
form. For a pair of conjugate complex eigenvalues with nonzero image part,
every real Jordan block is a combination of two complex Jordan blocks.

####  C.1.3 Solution formula for linear differential equation

For a linear differential equation with constant coefficients
$A\in{\mathbb{R}}^{d\times d}$

$\displaystyle\frac{dx}{dt}(t)=Ax$

with initial condition $x(0)$, it’s solution formula is given by
$x(t)=e^{tA}x(0)$. Thus to understand the dynamic behavior of $x(t)$, it is
necessary to calculate the matrix exponential matrix $e^{tA}$. This can be
done by using the real Jordan normal form of $A$. Let $J_{A}$ be $A$’s real
Jordan normal form, and $J_{A}=MAM^{-1}$, then $e^{tA}=Me^{tJ_{A}}M^{-1}$.
Thus calculation of $e^{tA}$ can be reduced to calculation of $e^{tJ_{A}}$ and
the real generalized modal matrix of $A$. The real generalized modal matrix of
$A$ is a combination of real and image parts of $A$’s generalized
eigenvectors, and in this section we consider calculation of $e^{tJ_{A}}$.

######  Proposition C.14.

(page 12 in (Colonius & Kliemann, 2014)) Let $J_{\mu}$ be a real Jordan block
of size $m\times m$ associated with the real eigenvalue $\mu$ of a matrix
$A\in{\mathbb{R}}^{d\times d}$. Then

$\displaystyle J_{\mu}=\begin{bmatrix}\mu&1&\\\ &\mu&1&\\\ &&\ddots&\ddots\\\
&&&\mu&1\\\ &&&&\mu\\\ \end{bmatrix}\in{\mathbb{R}}^{m\times m}$ (117)

and

$\displaystyle e^{J_{\mu}t}=e^{\mu
t}\begin{bmatrix}1&t&\frac{t^{2}}{2!}&\cdot&\cdot&\frac{t^{m-1}}{(m-1)!}\\\
&\cdot&\cdot&\cdot&\cdot&\cdot\\\ &&\cdot&\cdot&\cdot&\cdot\\\
&&&\cdot&\cdot&\frac{t^{2}}{2!}\\\ &&&&\cdot&t\\\
&&&&&1\end{bmatrix}\in{\mathbb{R}}^{m\times m}.$ (118)

Let $J_{\mu,\bar{\mu}}$ be a real Jordan block of size $2m\times 2m$
associated with the real eigenvalue $\mu,\bar{\mu}=\lambda\pm i\nu,\nu>0$ of a
matrix $A\in{\mathbb{R}}^{d\times d}$. With

$D=\begin{bmatrix}\lambda&-\nu\\\ \nu&\lambda\end{bmatrix},\
R:=R(t)=\begin{bmatrix}\cos(\nu t)&-\sin(\nu t)\\\ \\\ \sin(\nu t)&\cos(\nu
t)\end{bmatrix},\ I_{2}=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix},$

one obtains for

$\displaystyle J_{\mu,\bar{\mu}}=\begin{bmatrix}D&I_{2}\\\ &\cdot&\cdot\\\
&&\cdot&\cdot&\\\ &&&\cdot&\cdot&\\\ &&&&\cdot&I_{2}\\\ &&&&&D\\\
\end{bmatrix}\in{\mathbb{R}}^{2m\times 2m},$ (119)

and

$\displaystyle e^{J_{\mu,\bar{\mu}}t}=e^{\lambda
t}\begin{bmatrix}R&tR&\frac{t^{2}}{2!}R&\cdot&\cdot&\frac{t^{m-1}}{(m-1)!}R\\\
\\\ &\cdot&\cdot&\cdot&\cdot&\cdot\\\ &&\cdot&\cdot&\cdot&\cdot\\\
&&&\cdot&\cdot&\frac{t^{2}}{2!}R\\\ &&&&\cdot&tR\\\
&&&&&R\end{bmatrix}\in{\mathbb{R}}^{2m\times 2m}.$ (120)

####  C.1.4 Solution formula for linear difference equation

For a matrix $A\in{\mathbb{R}}^{d\times d}$, a linear difference equation with
coefficient matrix $A$ has form

$\displaystyle x_{n+1}=Ax_{n}$ (121)

By induction, equation 122 has solution formula

$\displaystyle x_{n}=A^{n}x_{0},\ x_{0}\in{\mathbb{R}}^{d}.$ (122)

If $J_{A}=M^{-1}AM$ be the real Jordan normal form of $A$, then
$x_{n}=M(J_{A})^{n}M^{-1}x_{0}.$ Thus to solve equation 122, it is sufficient
to know the formula for $(J_{A})^{n}$ and the real generalized modal matrix
$M$. Moreover, if $J_{A}=\oplus_{i}J_{i},$ then
$(J_{A})^{n}=\oplus_{i}(J_{i})^{n},$ thus we only need to consider the power
of real Jordan blocks.

######  Proposition C.15 (Page 19 in (Colonius & Kliemann, 2014)).

Let $J$ be a real Jordan block of size $m\times m$ associated with a real
eigenvalue $\mu$ of $A\in{\mathbb{R}}^{d\times d}$. Then

$\displaystyle J_{\mu}$ $\displaystyle=\begin{bmatrix}\mu&&\\\ &\mu&&\\\
&&\ddots&\\\ &&&\mu&\\\ &&&&\mu\\\ \end{bmatrix}+\begin{bmatrix}0&1&\\\
&0&1&\\\ &&\ddots&\ddots\\\ &&&0&1\\\ &&&&0\\\ \end{bmatrix}$ (123)
$\displaystyle=\mu I+N$ (124)

with $N^{m}=0$. Thus we have

$\displaystyle J_{\mu}^{n}=(\mu
I+N)^{n}=\sum^{m-1}_{i=0}\binom{n}{i}\mu^{n-i}N^{i}.$ (125)

Note that if $\mu>1$, elements in $J_{\mu}^{n}$ will have an exponential
growth rate as $\mu^{n}$. If $\mu=1$, elements in $J_{\mu}^{n}$ have a
polynomial growth rate. If $\mu<1$, elements in $J_{\mu}^{n}$ tends to $0$ as
$n$ growth.

######  Proposition C.16 (Page 20 in (Colonius & Kliemann, 2014)).

Let $J$ be a real Jordan block of size $2m\times 2m$ associated with a pair of
conjugate complex eigenvalue $\mu=\lambda+i\nu,\bar{\mu}=\lambda-i\nu$ of
$A\in{\mathbb{R}}^{d\times d}$. With $D=\begin{bmatrix}\lambda&-\nu\\\
\nu&\lambda\end{bmatrix}$ and $I_{2}=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$,
one obtains that

$\displaystyle J_{\mu,\bar{\mu}}$ $\displaystyle=\begin{bmatrix}D&0\\\
&\cdot&\cdot\\\ &&\cdot&\cdot&\\\ &&&\cdot&\cdot&\\\ &&&&\cdot&0\\\ &&&&&D\\\
\end{bmatrix}+\begin{bmatrix}0&I_{2}\\\ &\cdot&\cdot\\\ &&\cdot&\cdot&\\\
&&&\cdot&\cdot&\\\ &&&&\cdot&I_{2}\\\ &&&&&0\\\ \end{bmatrix}$ (126)
$\displaystyle=\tilde{D}+N$ (127)

with $N^{m}=0$. Moreover, since $\mu=\lvert\mu\lvert e^{i\phi}$ for some
$\phi\in[0,2\pi)$, one can write

$\displaystyle D=\begin{bmatrix}\lambda&-\nu\\\
\nu&\lambda\end{bmatrix}=\lvert\mu\lvert R,\
R=\begin{bmatrix}\cos\phi&-\sin\phi\\\ \sin\phi&\cos\phi\end{bmatrix}.$ (128)

Thus

$\displaystyle J_{\mu,\bar{\mu}}^{n}=(\tilde{D}+N)^{n}$
$\displaystyle=\sum^{m-1}_{i=0}\binom{n}{i}\tilde{D}^{n-i}N^{i}=\sum^{m-1}_{i=0}\binom{n}{i}\lvert\mu\lvert^{n-i}\tilde{R}^{n-i}N^{i}.$
(129)

where $\tilde{R}$ is a block diagonal matrix with matrix block $R$. Note that
if $\lvert\mu\lvert>1$, elements in $J_{\mu,\bar{\mu}}^{n}$ have exponential
growth rate as ${\mathcal{O}}(\lvert\mu\lvert^{n})$. If $\lvert\mu\lvert=1$,
elements in $J_{\mu,\bar{\mu}}^{n}$ have polynomial growth rate. If
$\lvert\mu\lvert<1$, elements in $J_{\mu,\bar{\mu}}^{n}$ tends to $0$ as $n$
growth.

###  C.2 Proof of Theorem 5.1

Now we are ready to prove Theorem 5.1. The proof is divided into three parts :

  * •

covariance evolution of continuous time equation, proved in C.2.1.

  * •

covariance evolution of Euler discretization, proved in C.2.2.

  * •

covariance evolution of Symplectic discretization, proved in C.2.3.

####  C.2.1 Covariance evolution of continuous equation

We firstly give a summary of the proof. The continuous time equation of FTRL
with Euclidean norm for agent 1 is written as:

$\displaystyle\frac{dy_{1}}{dt}$ $\displaystyle=-\frac{\partial
H(X_{1},y_{1})}{\partial X_{1}}=-AA^{\top}X_{1}(t)+Ay_{2}(0)$ (130)
$\displaystyle\frac{dX_{1}}{dt}$ $\displaystyle=\frac{\partial
H(X_{1},y_{1})}{\partial y_{1}}=y_{1}(t).$ (131)

Similarly for agent 2 we have

$\displaystyle\frac{dy_{2}}{dt}$ $\displaystyle=-\frac{\partial
H(X_{2},y_{2})}{\partial X_{2}}=-A^{\top}AX_{2}(t)-A^{\top}y_{1}(0)$ (132)
$\displaystyle\frac{dX_{2}}{dt}$ $\displaystyle=\frac{\partial
H(X_{2},y_{2})}{\partial y_{2}}=y_{2}(t).$ (133)

In the following, we will focus on the viewpoint of agent 1, thus we will
consider equation (130) and (131).

######  Lemma C.17.

The solution of the linear differential system consisted by equation (130) and
(131) and initial condition $(y_{1}(t_{0}),X_{1}(t_{0}))$ can be written as

$\displaystyle\begin{bmatrix}y_{1}(t+t_{0})\\\ \\\
X_{1}(t+t_{0})\end{bmatrix}=e^{{\mathcal{L}}t}\cdot\begin{bmatrix}y_{1}(t_{0})\\\
\\\
X_{1}(t_{0})\end{bmatrix}+e^{{\mathcal{L}}t}\cdot\int^{t+t_{0}}_{t_{0}}e^{-{\mathcal{L}}s}Ay_{2}(0)ds$
(134)

###### Proof.

It is directly to verify the derivate of right hind side satisfies equation
(130) and (131), and the solution satisfies initial condition
$(y_{1}(t_{0}),X_{1}(t_{0}))$. Due to the uniqueness of the solution of linear
differential equation, we can conclude this is the solution of equation (130)
and (131). ∎

Form (134) we can also see that if uncertainty are introduced to the system at
some initial time $t_{0}$, i.e., $(y_{1}(t_{0}),X_{1}(t_{0}))$ is a random
variable, then the evolution of covariance of random variable
$(y_{1}(t+t_{0}),X_{1}(t+t_{0}))$ will not be affected by the term
$\int^{t+t_{0}}_{t_{0}}e^{-{\mathcal{L}}s}Ay_{2}(0)ds$ since this is a
determined quantity, thus will only affect the expectation of
$(y_{1}(t+t_{0}),X_{1}(t+t_{0}))$ . Therefore, without loss of generality, we
will let $y_{2}(0)=0$ in the following.

Thus the continuous equation of agent 1 is

$\displaystyle\begin{bmatrix}\frac{dy_{1}}{dt}\\\ \\\
\frac{dX_{1}}{dt}\end{bmatrix}={\mathcal{L}}\begin{bmatrix}y_{1}(t)\\\ \\\
X_{1}(t)\end{bmatrix}$ (135)

where

${\mathcal{L}}=\begin{bmatrix}0&-AA^{\top}\\\ \\\
I&0\end{bmatrix}\in{\mathbb{R}}^{2n\times 2n}.$

Since the solution of (135) is $\begin{bmatrix}y_{1}(t)\\\ \\\
X_{1}(t)\end{bmatrix}=e^{t{\mathcal{L}}}\begin{bmatrix}y_{1}(0)\\\ \\\
X_{1}(0)\end{bmatrix},$ we have

$\begin{aligned}
P(t+t_{0})=e^{t{\mathcal{L}}}P(t_{0})(e^{t{\mathcal{L}}})^{\top}\end{aligned}.$

Thus to analysis the behavior of
$\mathrm{Var}(X_{1}(t)),\mathrm{Var}(y_{1}(t))$, and
$\mathrm{Cov}(X_{1}(t),y_{1}(t))$, we need to understand the behavior of
$e^{t{\mathcal{L}}}$. A standard method to calculate the matrix exponential of
a matrix with elements in ${\mathbb{R}}$ is though the matrix’s real Jordan
normal form and real generalized modal matrix, see Proposition C.14. For our
purpose, the most important question about the Jordan form of ${\mathcal{L}}$
is :

$\mbox{What is the size of the largest Jordan blocks corresponding to}\
{\mathcal{L}}^{\prime}s\ \mbox{eigenvalues ?}$

Because this number will determine the growth rate of elements in
$e^{t{\mathcal{L}}}$. In Proposition C.20, we will determine the minimal
polynomial of ${\mathcal{L}}$, combine this result with Proposition C.11, we
can get elements in $e^{t{\mathcal{L}}}$ that will at most have a linear
growth rate. However as we see in Theorem 5.1 there is a difference between
$\mathrm{Var}(X_{1}(t))$ and $\mathrm{Var}(y_{1}(t))$,
$\mathrm{Var}(X_{1}(t))$ may have quadratic growth and
$\mathrm{Var}(y_{1}(t))$ will always be bounded, only the growth rate of
$e^{t{\mathcal{L}}}$ is not sufficient for one to explain this difference. To
show that $\mathrm{Var}(y_{1}(t))$ is always bounded, we need a more detailed
analysis of the real generalized modal matrix of ${\mathcal{L}}$. We will see
that the first $n$ rows of the real generalized modal matrix has many $0$
elements, and these $0$ elements will make the first $n$ rows of
$e^{t{\mathcal{L}}}$ not to have linear growth rate. This will be shown in
Proposition C.23.

######  Lemma C.18.

Let

${\mathcal{L}}=\begin{bmatrix}0&-AA^{\top}\\\ \\\ I&0\end{bmatrix}$

be the coefficient matrix of (135), then the eigenvalues of ${\mathcal{L}}$
are pure imaginary numbers or $0$. Moreover, if $0$ is an eigenvalue of
${\mathcal{L}}$, then its multiplicity is an even number.

###### Proof.

Let $f(x)$ be the character polynomial of $-AA^{\top}$, thus

$\displaystyle f(x)=\det(xI_{n\times n}+AA^{\top})$ (136)

Firstly, every eigenvalue of $-AA^{\top}$ is a negative number or $0$. That is
because if $\mu$ is an eigenvalue of $-AA^{\top}$ and $v$ is an eigenvector of
$\mu$, then

$\displaystyle\mu\langle v,v\rangle$ $\displaystyle=\langle-
AA^{\top}v,v\rangle$ $\displaystyle=-\langle A^{\top}v,A^{\top}v\rangle$
$\displaystyle=-\left\|A^{\top}v\right\|^{2}\leq 0,$

since $\langle v,v\rangle\geq 0$, thus we have $\mu\leq 0$. This implies the
zeros of (136) are $0$ or negative.

The character polynomial of ${\mathcal{L}}$ is

$\displaystyle\det(\lambda I_{2n\times 2n}-{\mathcal{L}})$
$\displaystyle=\det(\lambda^{2}I_{n\times n}+AA^{\top})$ (137)
$\displaystyle=f(\lambda^{2})$ (138)

Thus the eigenvalues of ${\mathcal{L}}$ are square roots of zeros of (136).
Since the zeros of (136) are $0$ or negative, thus the eigenvalues of
${\mathcal{L}}$ are $0$ or pure imaginary numbers. Moreover, since (137) is an
even polynomial, it means that the polynomial only have terms of even degree,
thus if $0$ is a zero of (137), then its multiplicity is at least 2. ∎

Next we will calculate the minimal polynomial of ${\mathcal{L}}$. Combining
the calculated results with Proposition C.11, we will get the size of the
biggest Jordan blocks in the Jordan normal form of ${\mathcal{L}}$. Before
that, we need the following lemma.

######  Lemma C.19.

(Corollary 3.3.10. in (Horn & Johnson, 2012))Let $M\in{\mathbb{R}}^{d\times
d}$ and $f_{M}(x)$ be its minimal polynomial. Then $M$ is diagonalizable if
and only if every eigenvalue of M has multiplicity 1 as a root of
$f_{M}(x)=0$.

######  Proposition C.20 (Minimal polynomial of ${\mathcal{L}}$).

Let $\lambda_{1}\neq\lambda_{2}\neq...\neq\lambda_{l}$ be the distinct
eigenvalues of $-AA^{\top}$, thus $\forall
i\in[l],\lambda_{i}\in{\mathbb{R}},\ \lambda_{i}\leq 0$. Then the minimal
polynomial of ${\mathcal{L}}$ is :

$f_{{\mathcal{L}}}(x)=(x-\sqrt{\lambda_{1}}i)(x+\sqrt{\lambda_{1}}i)...(x-\sqrt{\lambda_{l}}i)(x+\sqrt{\lambda_{l}}i)$

Note that this implies that eigenvalues of ${\mathcal{L}}$ are purely
imaginary or $0$, moreover, if $\lambda_{i}=0$ for some $i$, then the factor
$x$ in $f_{{\mathcal{L}}}(x)$ has degree $2$.

###### Proof.

Let $f_{-AA^{\top}}(x)$ be the minimal polynomial of $-AA^{\top}$. Since
$-AA^{\top}$ is symmetric, thus diagonalizable, by Lemma C.19,
$f_{-AA^{\top}}(x)$ only contains linear factor of $(x-\lambda_{i})$,where
$\lambda_{i}$ is an eigenvalue of $-AA^{\top}$. Thus we have

$f_{-AA^{\top}}(x)=\prod_{i}(x-\lambda_{i})$

We claim $f_{-AA^{\top}}({\mathcal{L}}^{2})=0$, since:

${\mathcal{L}}^{2}=\begin{bmatrix}-AA^{\top}&0\\\ \\\ \\\
0&-AA^{\top}\end{bmatrix},$

therefore

$f_{-AA^{\top}}({\mathcal{L}}^{2})=\begin{bmatrix}f_{-AA^{\top}}(-AA^{\top})&0\\\
\\\ \\\ 0&f_{-AA^{\top}}(-AA^{\top})\end{bmatrix}=0.$

Thus if $f_{{\mathcal{L}}}(x)$ is the minimal polynomial of ${\mathcal{L}}$,
we have

$\displaystyle f_{{\mathcal{L}}}(x)\ |\
f_{-AA^{\top}}(x^{2})=\prod_{j}(x-\sqrt{\lambda_{j}}i)(x+\sqrt{\lambda_{j}}i)$
(139)

Moreover, since every eigenvalue of ${\mathcal{L}}$ is also a root of
$f_{{\mathcal{L}}}(x)$, from (139), we have :

  * (1)

If $\pm\sqrt{\lambda_{j}}i\neq 0$ is an eigenvalue of ${\mathcal{L}}$, then
the degree of $(x\pm\sqrt{\lambda_{j}}i)$ in $f_{{\mathcal{L}}}(x)$ must be 1.

  * (2)

If $\lambda_{j}=0$ is an eigenvalue of ${\mathcal{L}}$, then the degree of $x$
in $f_{{\mathcal{L}}}(x)$ must be $1$ or $2$.

In the following arguments, we will prove that there is at least a real Jordan
block corresponding to eigenvalue $0$ has size $2$. We have

${\mathcal{L}}=\begin{bmatrix}0&&-AA^{\top}\\\ \\\ I&&0\end{bmatrix},\
{\mathcal{L}}^{2}=\begin{bmatrix}-AA^{\top}&&0\\\ \\\
0&&-AA^{\top}\end{bmatrix}.$

Thus for some $x=(x_{1},x_{2})\in{\mathrm{Ker}}({\mathcal{L}}^{2})$,where
$x_{1},x_{2}\in{\mathbb{R}}^{n}$. Then we have

$\displaystyle{\mathcal{L}}^{2}\cdot\begin{bmatrix}x_{1}\\\ \\\
x_{2}\end{bmatrix}$ $\displaystyle=\begin{bmatrix}-AA^{\top}\cdot x_{1}\\\ \\\
-AA^{\top}\cdot x_{2}\end{bmatrix}=0.$

This implies $x_{1},x_{2}\in{\mathrm{Ker}}-AA^{\top}$. Since $-AA^{\top}$ has
eigenvalue 0, $x_{1},x_{2}$ may not equal to $0$. But

$\begin{aligned} {\mathcal{L}}\cdot\begin{bmatrix}x_{1}\\\ \\\
x_{2}\end{bmatrix}&=\begin{bmatrix}-AA^{\top}\cdot x_{2}\\\ \\\
x_{1}\end{bmatrix}\end{aligned},$

so if $(x_{1},x_{2})\in{\mathrm{Ker}}{\mathcal{L}}$, $x_{1}$ must be $0$. This
completes the proof of
${\mathrm{Ker}}({\mathcal{L}})\neq{\mathrm{Ker}}({\mathcal{L}}^{2})$. By
Proposition C.10, there exists Jordan block of size $2$. ∎

######  Lemma C.21.

Let $J_{0}$ be the largest Jordan blocks of ${\mathcal{L}}$ corresponding to
$0$ eigenvalues, then elements in $e^{J_{0}t}$ are of ${\mathcal{O}}(t)$. Let
$J_{\mu,\bar{\mu}}$ be the largest Jordan blocks of ${\mathcal{L}}$
corresponding to a pair of conjugate purely imaginary eigenvalues
$(\mu,\bar{\mu})$, then elements in
$e^{J_{\mu,\bar{\mu}}t}\in{\mathcal{O}}(1)$.

###### Proof.

From Proposition C.20, the size of the largest Jordan blocks of
${\mathcal{L}}$ corresponding to the $0$ eigenvalues are $2$. Thus the
corollary follows from (118) with $\mu=0$ and $m=2$. From Proposition C.20,
the size of the largest Jordan blocks of ${\mathcal{L}}$ corresponding to a
pair of conjugate imaginary eigenvalues $(\mu,\bar{\mu})$ are $2$. So the
corollary follows from (120) with $\lambda=0$ and $m=1$. ∎

Next we consider the set of real generalized vectors of ${\mathcal{L}}$. Let
$S_{{\mathcal{L}}}$ be the set of vectors that appear in the real generalized
modal matrix $M_{{\mathcal{L}}}$ . Then as shown in Proposition C.20, these
generalized eigenvectors corresponds to an imaginary eigenvalues or $0$
eigenvalues. If $v\in S_{{\mathcal{L}}}$ corresponds to $0$, $v$ may in a
Jordan chain with length $1$ or length $2$. If $v\in S_{{\mathcal{L}}}$
corresponds to a purely imaginary number, then there exists some $w$ be the
eigenvector of an imaginary eigenvalue and $v={\mathrm{Re}}(w)$ or
$v={\mathrm{Im}}(w)$.

Thus we have

$S_{{\mathcal{L}}}=(\cup_{(\mu,\bar{\mu})}S_{{\mathcal{L}}}(\mu,\bar{\mu}))\cup
S_{{\mathcal{L}}}(0)$

where

$S_{{\mathcal{L}}}(\mu,\bar{\mu})=\\{v\in{\mathbb{R}}^{2n}|\ \exists\ w\
\mbox{be an eigenvector for}\ \mu\ \mbox{or}\
\bar{\mu}\in{\mathbb{C}}-{\mathbb{R}}\ ,v={\mathrm{Re}}(w)\ \mbox{or}\
v={\mathrm{Im}}(w)\\},$

and

$S_{{\mathcal{L}}}(0)=\\{v\in{\mathbb{R}}^{2n}|\ v\mbox{ is a generalized
eigenvector for}\ 0\\}.$

So as in definition C.12, $M_{{\mathcal{L}}}$ has the following form:

$\displaystyle
M_{{\mathcal{L}}}=\begin{bmatrix}\mathrlap{\smash{\overbrace{\phantom{\begin{matrix}v_{1},&...&,v_{m_{1}}\end{matrix}}}^{\mbox{$\mbox{$m_{1}$
columns}$}}}}v_{1},&...&,v_{m_{1}},&\mathrlap{\smash{\overbrace{\phantom{\begin{matrix}v_{1+m_{1}},&...&,v_{m_{1}+m_{2}}\end{matrix}}}^{\mbox{$\mbox{$m_{2}$
columns}$}}}}v_{1+m_{1}},&...&,v_{m_{1}+m_{2}},&\mathrlap{\smash{\overbrace{\phantom{\begin{matrix}v_{m_{1}+m_{2}+1},&...&,v_{m_{1}+m_{2}+m_{3}}\end{matrix}}}^{\mbox{$\mbox{$m_{3}$
columns}$}}}}v_{m_{1}+m_{2}+1},&...&,v_{m_{1}+m_{2}+m_{3}}\end{bmatrix}$ (140)

where

  * •

$\\{v_{1},....,v_{m_{1}}\\}\subset\cup_{(\lambda,\bar{\lambda})}S_{{\mathcal{L}}}(\mu,\bar{\mu})$
.

  * •

$\\{v_{1+m_{1}},...,v_{m_{1}+m_{2}}\\}\subset S_{{\mathcal{L}}}(0)$, and each
each $v_{i}$ is a Jordan chain of length $1$.

  * •

$\\{v_{m_{1}+m_{2}+1},...,v_{m_{1}+m_{2}+m_{3}}\\}\subset
S_{{\mathcal{L}}}(0)$, $(v_{i},v_{i+1})$ is a Jordan chain of length $2$, and
$v_{i}={\mathcal{L}}v_{i+1}$.

  * •

$m_{1}+m_{2}+m_{3}=2n.$

######  Lemma C.22.

If $w=(w_{1},w_{2},...,w_{2n})^{\top}\neq 0$ is a type 1 generalized
eigenvectors of ${\mathcal{L}}$ corresponding to $0$ eigenvalue , then the
first n components $(w_{1},w_{2},...,w_{n})^{\top}=0$, and the the last n
components $(w_{n+1},...,w_{2n})^{\top}\in\ker(-AA^{\top})$ .

If $s=(s_{1},s_{2},...,s_{2n})^{\top}\neq 0$ is a type 2 generalized
eigenvectors of ${\mathcal{L}}$ corresponding to $0$ eigenvalue , then
$(s_{1},...,s_{n})^{\top}\neq 0$ and
$(s_{1},...,s_{n})^{\top},(s_{n+1},...,s_{2n})^{\top}\in\ker(-AA^{\top})$.

###### Proof.

Firstly, note that type 1 generalized eigenvectors of ${\mathcal{L}}$
corresponding to $0$ are just vectors in $\ker({\mathcal{L}})$. Thus if $w$ is
a type 1 generalized eigenvectors of ${\mathcal{L}}$ corresponding to $0$, we
have

$\displaystyle{\mathcal{L}}\cdot w$
$\displaystyle=\begin{bmatrix}0&-AA^{\top}\\\ \\\
I&0\end{bmatrix}\cdot(w_{1},w_{2},...,w_{2n})^{\top}$
$\displaystyle=\begin{bmatrix}-AA^{\top}\cdot(w_{n+1},...,w_{2n})^{\top}\\\
\\\ \\\ (w_{1},...,w_{n})^{\top}\end{bmatrix}=0$

Thus $(w_{1},w_{2},...,w_{n})^{\top}=0$ and
$(w_{n+1},...,w_{2n})^{\top}\in\ker(-AA^{\top})$ .

Secondly, if $s=(s_{1},s_{2},...,s_{2n})^{\top}\neq 0$ is a type 2 generalized
eigenvectors of ${\mathcal{L}}$ corresponding to $0$ eigenvalue, then we have

${\mathcal{L}}\cdot s\neq 0\ \ \mbox{and}\ \ {\mathcal{L}}^{2}\cdot s=0.$

Since

$\displaystyle{\mathcal{L}}^{2}\cdot s$
$\displaystyle=\begin{bmatrix}-AA^{\top}&0\\\ \\\
0&-AA^{\top}\end{bmatrix}\cdot(s_{1},s_{2},...,s_{2n})^{\top}$
$\displaystyle=\begin{bmatrix}-AA^{\top}\cdot(s_{n+1},...,s_{2n})^{\top}\\\
\\\ \\\ -AA^{\top}(s_{1},...,s_{n})^{\top}\end{bmatrix}=0$

This implies
$(s_{1},...,s_{n})^{\top},(s_{n+1},...,s_{2n})^{\top}\in\ker(-AA^{\top})$.
Moreover, since $s$ is a type $2$ generalized eigenvector, we have
$(s_{1},...,s_{n})^{\top}\neq 0$. ∎

From the correspondence between real generalized vectors and real Jordan
blocks as described in Proposition C.13, the real Jordan form
$J_{{\mathcal{L}}}$ of ${\mathcal{L}}$ under a similar transformation by real
generalized modal matrix $M_{{\mathcal{L}}}$ has form

$\displaystyle
J_{{\mathcal{L}}}=\begin{bmatrix}\mathrlap{\smash{\overbrace{\phantom{\begin{matrix}J_{\mu_{1},\bar{\mu}_{1}}&&&&&&\end{matrix}}}^{\mbox{$\mbox{$m_{1}$
columns}$}}}}J_{\mu_{1},\bar{\mu}_{1}}&&&&&&\\\ &\ddots&&\\\
&&J_{\mu_{m_{1}/2},\bar{\mu}_{m_{1}/2}}&\\\
&&&\mathrlap{\smash{\overbrace{\phantom{\begin{matrix}0&&&&\end{matrix}}}^{\mbox{$\mbox{$m_{2}$
columns}$}}}}0&&&&\\\ &&&&\ddots\\\ &&&&&0\\\
&&&&&&\mathrlap{\smash{\overbrace{\phantom{\begin{matrix}J^{2}_{0}&&&\end{matrix}}}^{\mbox{$\mbox{$m_{3}$
columns}$}}}}J^{2}_{0}&&&\\\ &&&&&&&\ddots\\\ &&&&&&&&J^{2}_{0}\\\
\end{bmatrix}$ (141)

$J_{\mu_{k},\bar{\mu}_{k}}=\begin{bmatrix}{\mathrm{Re}}(\mu_{k})&-{\mathrm{Im}}(\mu_{k})\\\
\\\ {\mathrm{Im}}(\mu_{k})&{\mathrm{Re}}(\mu_{k})\end{bmatrix}$ are real
Jordan blocks corresponding to conjugate eigenvalue $(\mu_{k},\bar{\mu}_{k})$
and $J^{2}_{0}=\begin{bmatrix}0&1\\\ 0&0\end{bmatrix}$ is the real Jordan
block corresponding to the type $2$ generalized eigenvectors of $0$
eigenvalue. Thus we have

$\displaystyle
e^{tJ_{{\mathcal{L}}}}=\oplus^{m_{1}}_{i=1}(e^{tJ_{\mu_{i},\bar{\mu}_{i}}})\oplus^{m_{2}}_{i=1}I_{1}\oplus^{m_{3}}_{i=1}e^{tJ^{2}_{0}}$
(142)

where

  * •

$e^{tJ_{\mu_{i},\bar{\mu}_{i}}}$ is defined in (120) with $\lambda=0,\ m=1$.
Thus elements in $e^{tJ_{\mu_{i},\bar{\mu}_{i}}}$ are in ${\mathcal{O}}(1)$.

  * •

$I_{1}=[1]\in{\mathbb{R}}^{1\times 1}$.

  * •

$e^{tJ^{2}_{0}}$ is defined in (118) with $\mu=0,m=2$. Matrix elements in
$e^{tJ^{2}_{0}}$ are in ${\mathcal{O}}(t)$.

More precisely, we have

(150)

and only elements in the upper diagonal of the last $m_{3}$ columns belongs to
${\mathcal{O}}(t)$, other elements are all bounded function of $t$.

######  Lemma C.23.

Let $(e^{t{\mathcal{L}}})_{i}$ denote the $i$-th row of $e^{t{\mathcal{L}}}$.
Then we have

  * •

If $AA^{\top}$ has $0$ eigenvalues, then for $i\in\\{1,2,...,n\\}$, elements
in $(e^{t{\mathcal{L}}})_{i}$ are bounded and for $i\in\\{n+1,n+2,...,2n\\}$,
$(e^{t{\mathcal{L}}})_{i}$ belongs to ${\mathcal{O}}(t)$.

  * •

If $AA^{\top}$ doesn’t have $0$ eigenvalues, all elements in
$e^{t{\mathcal{L}}}$ are bounded.

###### Proof.

Let $(M_{{\mathcal{L}}})^{-1}=[p_{1},p_{2},...,p_{2n}],\
p_{i}\in{\mathbb{R}}^{2n}$ be the inverse of the real generalized modal matrix
of ${\mathcal{L}}$, then we have

$\displaystyle
e^{t{\mathcal{L}}}=M_{{\mathcal{L}}}(e^{tJ_{{\mathcal{L}}}}[w_{1},w_{2},...,w_{2n}]).$
(151)

If $AA^{\top}$ has $0$ eigenvalues, from (150), we have
$e^{tJ_{{\mathcal{L}}}}w_{i}$ has form

$\displaystyle\leavevmode\hbox to143.22pt{\vbox
to103.06pt{\pgfpicture\makeatletter\hbox{\hskip-120.8752pt\lower-50.1074pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{{}}{}{{}}{}\pgfsys@moveto{142.2638pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{124.2082pt}{-32.90079pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\left[\begin{array}[]{c}\vdots\\\ \vdots\\\ \vdots\\\ \hline\cr t\\\
{\mathcal{O}}(1)\\\ \vdots\\\ t\\\ {\mathcal{O}}(1)\end{array}\right]$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}{}{{}}{}\pgfsys@moveto{156.49017pt}{34.14322pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{160.02318pt}{21.16685pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\left.\rule{0.0pt}{28.45274pt}\right\\}$ $\in{\mathcal{O}}(1)$,
$m_{1}+m_{2}$ rows}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}{}{{}}{}\pgfsys@moveto{156.49017pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{160.02318pt}{-44.2744pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\left.\rule{0.0pt}{34.1433pt}\right\\}$ $m_{3}$ \mbox{ rows}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>(160)

From Lemma C.22, the first $n$ rows of $M_{{\mathcal{L}}}$ has form

$\displaystyle\leavevmode\hbox to229.19pt{\vbox
to135.43pt{\pgfpicture\makeatletter\hbox{\hskip
82.93367pt\lower-40.14894pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{{}}{}{{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-79.60066pt}{-28.49666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\left[\begin{array}[]{cc|cccccc}&&0&&0&&0&\\\ &&0&&0&&0&\\\
&&0&&0&&0&\\\ &&\vdots&&\vdots&&\vdots&\\\ &&0&&0&&0&\\\
\cdots&\cdots&\vdots&v_{m+2}&\vdots&\cdots&\vdots&v_{2n}\\\ &&&&&&&\\\
&&0&&0&&0&\\\ &&&&&&&\\\ &&\vdots&&\vdots&&\vdots&\\\ \end{array}\right]$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}{}{{}}{}{{}}{}{{}}{}\pgfsys@moveto{-65.44142pt}{68.28644pt}\pgfsys@moveto{-62.59598pt}{79.6678pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-69.19142pt}{73.81944pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\overbrace{\rule{42.67912pt}{0.0pt}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-79.1761pt}{85.00525pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$m_{1}+m_{2}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}{}{{}}{}{{}}{}{{}}{}\pgfsys@moveto{28.45276pt}{68.28644pt}\pgfsys@moveto{25.6073pt}{79.6678pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{24.70276pt}{73.81944pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\overbrace{\rule{113.81102pt}{0.0pt}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.34497pt}{85.00525pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$m_{3}$
\mbox{columns}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}{}{{}}{}\pgfsys@moveto{99.58466pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{103.11766pt}{-34.31593pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\left.\rule{0.0pt}{71.13188pt}\right\\}$ \mbox{n rows}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>(171)

The first $n$ rows of $M_{{\mathcal{L}}}e^{tJ_{{\mathcal{L}}}}p_{i}$ is the
matrix-vector product of (171) and (160), we can see the term $t$ in (160)
will product with term $0$ in (171), thus the first $n$ rows of
$M_{{\mathcal{L}}}e^{tJ_{{\mathcal{L}}}}p_{i}$ belong to ${\mathcal{O}}(1)$.
The last $n$ rows of $M_{{\mathcal{L}}}e^{tJ_{{\mathcal{L}}}}p_{i}$ belong to
${\mathcal{O}}(t)$ because there may exist nonzero elements in the last $n$
rows of $M_{{\mathcal{L}}}$ that can product with $t$ in (160).

If $AA^{\top}$ doesn’t have $0$ eigenvalues, from Lemma C.21, all elements in
$e^{J_{{\mathcal{L}}}t}$ are bounded and since
$e^{t{\mathcal{L}}}=M_{{\mathcal{L}}}e^{tJ_{{\mathcal{L}}}}(M_{{\mathcal{L}}})^{-1}$,
thus all elements in $e^{t{\mathcal{L}}}$ are bounded. ∎

The covariance evolution directly follows from above calculation.

###### Proof of covariance in continuous time equation.

Denote

$P(t_{0})=\begin{bmatrix}\mathrm{Var}(y_{1}(t_{0}))&\mathrm{Cov}(y_{1}(t_{0}),X_{1}(t_{0}))\\\
\\\
\mathrm{Cov}(y_{1}(t_{0}),X_{1}(t_{0}))&\mathrm{Var}(X_{1}(t_{0}))\end{bmatrix}$

and $e^{t{\mathcal{L}}}=\begin{bmatrix}A(t)&B(t)\\\ \\\
C(t)&D(t)\end{bmatrix}$. Since
$P(t+t_{0})=e^{t{\mathcal{L}}}P(t_{0})(e^{t{\mathcal{L}}})^{\top}$, we have

$\displaystyle P(t+t_{0})=\begin{bmatrix}A(t)&B(t)\\\ \\\
C(t)&D(t)\end{bmatrix}\begin{bmatrix}\mathrm{Var}(y_{1}(t_{0}))&\mathrm{Cov}(y_{1}(t_{0}),X_{1}(t_{0}))\\\
\\\
\mathrm{Cov}(y_{1}(t_{0}),X_{1}(t_{0}))&\mathrm{Var}(X_{1}(t_{0}))\end{bmatrix}\begin{bmatrix}(A(t))^{\top}&(C(t))^{\top}\\\
\\\ (B(t))^{\top}&(D(t))^{\top}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}A(t)\mathrm{Var}(y_{1}(t_{0}))+B(t)\mathrm{Cov}(y_{1}(t_{0}),X_{1}(t_{0}))&A(t)\mathrm{Cov}(y_{1}(t_{0}),X_{1}(t_{0}))+B(t)\mathrm{Var}(X_{1}(t_{0}))\\\
\\\
C(t)\mathrm{Var}(y_{1}(t_{0}))+D(t)\mathrm{Cov}(y_{1}(t_{0}),X_{1}(t_{0}))&C(t)\mathrm{Cov}(y_{1}(t_{0}),X_{1}(t_{0}))+D(t)\mathrm{Var}(X_{1}(t_{0}))\end{bmatrix}\begin{bmatrix}(A(t))^{\top}&(C(t))^{\top}\\\
\\\ (B(t))^{\top}&(D(t))^{\top}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}(A\mathrm{Var}(y_{1})+B\mathrm{Cov})A^{\top}+(A\mathrm{Cov}+B\mathrm{Var}(X_{1}))B^{\top}&(A\mathrm{Var}(y_{1})+B\mathrm{Cov})C^{\top}+(A\mathrm{Cov}+B\mathrm{Var}(X_{1}))D^{\top}\\\
\\\
(C\mathrm{Var}(y_{1})+D\mathrm{Cov})A^{\top}+(C\mathrm{Cov}+D\mathrm{Var}(X_{1}))B^{\top}&(C\mathrm{Var}(y_{1})+D\mathrm{Cov})C^{\top}+(C\mathrm{Cov}+D\mathrm{Var}(X_{1}))D^{\top}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\mathrm{Var}(y_{1}(t_{0}+t))&\mathrm{Cov}(y_{1}(t_{0}+t),X_{1}(t_{0}+t))\\\
\\\
\mathrm{Cov}(y_{1}(t_{0}+t),X_{1}(t_{0}+t))&\mathrm{Var}(X_{1}(t_{0}+t))\end{bmatrix}$

From Lemma C.23, if $AA^{\top}$ has $0$ eigenvalue, elements in $A(t),B(t)$
are bounded and elements in $C(t),D(t)$ are in ${\mathcal{O}}(t)$ and there
exist elements in $C(t),D(t)$ belongs to $\Theta(t)$ , thus from above
equation we have $\mathrm{Var}(y_{1}(t_{0}+t))\in{\mathcal{O}}(1)$,
$\mathrm{Cov}(y_{1}(t_{0}),X_{1}(t_{0}+t))\in\Theta(t)$,$\mathrm{Var}(X_{1}(t_{0}+t))\in\Theta(t^{2})$.
Moreover, if $AA^{\top}$ doesn’t have $0$ eigenvalue, Lemma C.23 implies all
elements in $A(t),B(t),C(t),D(t)$ are bounded, thus all elements in
$P(t+t_{0})$ are bounded. ∎

####  C.2.2 Covariance evolution of Euler discretization

###### Proof.

The Euler discretization of (135) with step size $\eta$ can be written as

$\displaystyle\begin{bmatrix}y^{t}_{1}\\\ \\\ X^{t}_{1}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}y^{t-1}_{1}\\\ \\\
X^{t-1}_{1}\end{bmatrix}+\begin{bmatrix}0&-\eta AA^{T}\\\ \\\ \eta
I&0\end{bmatrix}\cdot\begin{bmatrix}y^{t-1}_{1}\\\ \\\
X^{t-1}_{1}\end{bmatrix}$ $\displaystyle=\begin{bmatrix}I&-\eta AA^{T}\\\ \\\
\eta I&I\end{bmatrix}\cdot\begin{bmatrix}y^{t-1}_{1}\\\ \\\
X^{t-1}_{1}\end{bmatrix}.$ (172)

We want to prove if $(y^{t}_{1},X^{t}_{1})$ evolve as this equation, then
$\mathrm{Cov}(y^{t}_{1}),\mathrm{Cov}(X^{t}_{1})$ have exponential growth
rate. This can be done by calculating the real Jordan normal form of
$\begin{bmatrix}I&-\eta AA^{T}\\\ \\\ \eta I&I\end{bmatrix}$. Since
$AA^{\top}\in{\mathbb{R}}^{n\times n}$ is a diagonalizable matrix, there
exists a matrix $P$, such that

$\displaystyle PAA^{\top}P^{-1}=\begin{bmatrix}\gamma_{1}&&&\\\
&\gamma_{2}&&\\\ &&\ddots&\\\ &&&\gamma_{n}\end{bmatrix}$ (173)

where $\gamma_{1},...,\gamma_{n}$ are eigenvalues of $AA^{\top}$. Moreover,
since $AA^{\top}$ is a positive semidefinite matrix, we have $\gamma_{i}\geq
0,i\in[n]$.

Then we have

$\displaystyle\begin{bmatrix}P&&\\\ \\\ &&P\end{bmatrix}\begin{bmatrix}I&-\eta
AA^{T}\\\ \\\ \eta I&I\end{bmatrix}\begin{bmatrix}P^{-1}&\\\ \\\
&P^{-1}\end{bmatrix}=\begin{bmatrix}\begin{array}[]{cccc|cccc}1&&&&-\gamma_{1}\eta&&&\\\
&1&&&&-\gamma_{2}\eta&&\\\ &&\ddots&&&&\ddots&\\\ &&&1&&&&-\gamma_{n}\eta\\\
\hline\cr\eta&&&&1&&&\\\ &\eta&&&&1&&\\\ &&\ddots&&&&\ddots&\\\
&&&\eta&&&&1\end{array}\end{bmatrix}.$ (174)

This matrix is similar to $\begin{bmatrix}I&-\eta AA^{T}\\\ \\\ \eta
I&I\end{bmatrix}$, thus they have same character polynomial defined by

$\displaystyle\det(\mu I-$
$\displaystyle\begin{bmatrix}\begin{array}[]{cccc|cccc}1&&&&-\gamma_{1}\eta&&&\\\
&1&&&&-\gamma_{2}\eta&&\\\ &&\ddots&&&&\ddots&\\\ &&&1&&&&-\gamma_{n}\eta\\\
\hline\cr\eta&&&&1&&&\\\ &\eta&&&&1&&\\\ &&\ddots&&&&\ddots&\\\
&&&\eta&&&&1\end{array}\end{bmatrix})$ (175)
$\displaystyle=\det(\begin{bmatrix}\begin{array}[]{cccc|cccc}\mu-1&&&&\gamma_{1}\eta&&&\\\
&\mu-1&&&&\gamma_{2}\eta&&\\\ &&\ddots&&&&\ddots&\\\
&&&\mu-1&&&&-\gamma_{n}\eta\\\ \hline\cr-\eta&&&&\mu-1&&&\\\
&-\eta&&&&\mu-1&&\\\ &&\ddots&&&&\ddots&\\\
&&&-\eta&&&&\mu-1\end{array}\end{bmatrix})$ (176)
$\displaystyle=\det(\begin{bmatrix}(\mu-1)^{2}+\gamma_{1}\eta^{2}&&&\\\
&(\mu-1)^{2}+\gamma_{2}\eta^{2}&&\\\ &&\ddots&\\\
&&&(\mu-1)^{2}+\gamma_{n}\eta^{2}\end{bmatrix})$ (177)
$\displaystyle=\prod^{n}_{i=1}((\mu-1)^{2}+\gamma_{i}\eta^{2})$ (178)

Recall we have $\gamma_{i}\geq 0,i\in[n]$, thus the root of character
polynomial is $\mu_{j},\bar{\mu}_{j}=1\pm i\sqrt{\gamma_{j}}\eta,\ j\in[n]$.
Moreover, we have $\lvert\mu_{j}\lvert=1+\gamma_{j}\eta^{2}\geq 1$. Thus by
Proposition C.16, elements in $\begin{bmatrix}I&-\eta AA^{T}\\\ \\\ \eta
I&I\end{bmatrix}^{t}$ have an exponential growth rate as
$\Theta(\lvert\mu\lvert^{t})$, where $\mu$ is the eigenvalue of $AA^{\top}$
which has largest norm.

Since

$\displaystyle P(t)$
$\displaystyle=\begin{bmatrix}\mathrm{Var}(y^{t}_{1})&\mathrm{Cov}(y^{t}_{1},X^{t}_{1})\\\
\mathrm{Cov}(X^{t}_{1},y^{t}_{1})&\mathrm{Var}(X^{t}_{1})\end{bmatrix}$ (179)
$\displaystyle=\begin{bmatrix}I&-\eta AA^{T}\\\ \\\ \eta
I&I\end{bmatrix}^{t-t_{0}}\begin{bmatrix}\mathrm{Var}(y^{t_{0}}_{1})&\mathrm{Cov}(y^{t_{0}}_{1},X^{t_{0}}_{1})\\\
\\\
\mathrm{Cov}(X^{t_{0}}_{1},y^{t_{0}}_{1})&\mathrm{Var}(X^{t_{0}}_{1})\end{bmatrix}(\begin{bmatrix}I&-\eta
AA^{T}\\\ \\\ \eta I&I\end{bmatrix}^{t-t_{0}})^{\top}$ (180)

Since elements in matrix $\begin{bmatrix}I&-\eta AA^{T}\\\ \\\ \eta
I&I\end{bmatrix}^{t-t_{0}}$ has growth rate $\Theta(\lvert\mu\lvert^{t})$,
thus elements in $P(t)$ has growth rate $\Theta(\lvert\mu\lvert^{2t})$. ∎

####  C.2.3 Covariance evolution of Symplectic discretization

We firstly determine the Symplectic discretization of continuous FTRL (135)
with Euclidian norm regularizer.

######  Lemma C.24.

Discrete continuous FTRL (135) with (3), we get

$\displaystyle\begin{bmatrix}y_{1}^{n+1}\\\ \\\
X_{1}^{n+1}\end{bmatrix}=\begin{bmatrix}I&-\eta AA^{\top}\\\ \\\
\eta&I-\eta^{2}AA^{\top}\end{bmatrix}\cdot\begin{bmatrix}y_{1}^{n}\\\ \\\
X_{1}^{n}\end{bmatrix}.$ (181)

###### Proof.

Directly calculate gives

$\displaystyle y_{1}^{t+1}$ $\displaystyle=y^{t}_{1}-\eta AA^{\top}X^{t}_{1},$
(182) $\displaystyle X_{1}^{t+1}$ $\displaystyle=X^{t}_{1}+\eta y_{1}^{t+1}$
(183) $\displaystyle=X^{t}_{1}+\eta y^{t}_{1}-\eta^{2}AA^{\top}X^{t}_{1}.$
(184)

Combine above gives

$\displaystyle\begin{bmatrix}y_{1}^{n+1}\\\ \\\
X_{1}^{n+1}\end{bmatrix}=\begin{bmatrix}I&-\eta AA^{\top}\\\ \\\
\eta&I-\eta^{2}AA^{\top}\end{bmatrix}\cdot\begin{bmatrix}y_{1}^{n}\\\ \\\
X_{1}^{n}\end{bmatrix}.$ (185)

This finish the proof. ∎

Let ${\mathcal{M}}_{\eta}=\begin{bmatrix}I&-AA^{\top}\cdot\eta\\\ \\\
\eta&I-AA^{\top}\cdot\eta^{2}\end{bmatrix}$. Since $AA^{\top}$ is
diagonalizable, and $AA^{\top}$’s eigenvalues are all non-negative, there
exists a matrix $P\in{\mathbb{R}}^{n\times n}$ and $P$ invertible, such that

$\displaystyle P^{-1}AA^{\top}P$
$\displaystyle=\begin{bmatrix}\gamma_{1}&&&\\\ &\gamma_{2}&&\\\ &&\ddots&\\\
&&&\gamma_{n}\end{bmatrix}$ (186)

where $\gamma_{1},...,\gamma_{n}\geq 0$ are eigenvalues of $AA^{\top}$.

######  Lemma C.25.

${\mathcal{M}}_{\eta}$ has real eigenvalues if and only if $AA^{\top}$ has $0$
eigenvalue, and in this case the only real eigenvalue of
${\mathcal{M}}_{\eta}$ equals to $1$. Moreover, every image eigenvalue of
${\mathcal{M}}_{\eta}$ has norm equals to $1$.

###### Proof.

With (186), we have

$\displaystyle\det(\mu I-{\mathcal{M}}_{\eta})$
$\displaystyle=\det(\begin{bmatrix}\mu-I&AA^{\top}\eta\\\ \\\
-\eta&\mu-I+AA^{\top}\eta^{2}\end{bmatrix})$ (187)
$\displaystyle=\det((\mu-I)(\mu-I+AA^{\top}\eta^{2})+AA^{\top}\eta^{2})$ (188)
$\displaystyle=\det(\mu^{2}-2\mu+I+\mu AA^{\top}\eta^{2})$ (189)
$\displaystyle\overset{(\ref{diagAAtop})}{=}\det(\begin{bmatrix}\mu^{2}-2\mu+1+\mu\eta^{2}\gamma_{1}&&&\\\
&\mu^{2}-2\mu+1+\mu\eta^{2}\gamma_{2}&&\\\ &&\ddots&\\\
&&&\mu^{2}-2\mu+1+\mu\eta^{2}\gamma_{n}\end{bmatrix})$ (190)
$\displaystyle=\prod^{n}_{i=1}(\mu^{2}-2\mu+1+\mu\eta^{2}\gamma_{i})$ (191)

From above, we can see if $\mu$ makes $\det(\mu I-{\mathcal{M}}_{\eta})=0$,
then there exists some $i\in[n]$, such that

$\displaystyle\mu^{2}-2\mu+1+\mu\eta^{2}\gamma_{i}=0.$ (192)

(192) is a quadratic function about $\mu$, and has solution
$\mu=\frac{(2-\eta^{2}\gamma_{i})\pm\sqrt{(\eta^{2}\gamma_{i}-2)^{2}-4}}{2}$.

To make $\mu\in{\mathbb{R}}$, we need $(\eta^{2}\gamma_{i}-2)^{2}-4\geq 0$.
For sufficient small $\eta$ ($\eta^{2}\gamma_{i}\leq 2$), that can only happen
when $\gamma_{i}=0$, and in this case we have $\mu=1$. Moreover, if
$(\eta^{2}\gamma_{i}-2)^{2}-4<0$, we have

$\displaystyle\lVert\mu\lVert^{2}$
$\displaystyle=\lVert\frac{(2-\eta^{2}\gamma_{i})\pm
i\sqrt{4-(\eta^{2}\gamma_{i}-2)^{2}}}{2}\lVert^{2}$ (193)
$\displaystyle=\frac{(2-\eta^{2}\gamma_{i})^{2}+4-(\eta^{2}\gamma_{i}-2)^{2}}{4}$
(194) $\displaystyle=1$ (195)

Thus we have

  * •

${\mathcal{M}}_{\eta}$ has a real eigenvalue if and only if $\gamma=0$ is an
eigenvalue of $AA^{\top}$, and in this case the real eigenvalue of