# Exploiting hidden structures in non-convex games
for convergence to Nash equilibrium

Iosif Sakos∗ ∗ Singapore University of Technology and Design
<EMAIL_ADDRESS>,  Emmanouil V. Vlatakis-Gkaragkounis§ § UC
Berkeley<EMAIL_ADDRESS>,
Panayotis Mertikopoulos♯ ♯ Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP,
LIG, 38000 Grenoble, France<EMAIL_ADDRESS>and  Georgios
Piliouras∗<EMAIL_ADDRESS>
###### Abstract.

A wide array of modern machine learning applications – from adversarial models
to multi-agent reinforcement learning – can be formulated as non-cooperative
games whose Nash equilibria represent the system’s desired operational states.
Despite having a highly non-convex loss landscape, many cases of interest
possess a latent convex structure that could potentially be leveraged to yield
convergence to an equilibrium. Driven by this observation, our paper proposes
a flexible first-order method that successfully exploits such “hidden
structures” and achieves convergence under minimal assumptions for the
transformation connecting the players’ control variables to the game’s latent,
convex-structured layer. The proposed method – which we call preconditioned
hidden gradient descent (PHGD) – hinges on a judiciously chosen gradient
preconditioning scheme related to natural gradient methods. Importantly, we
make no separability assumptions for the game’s hidden structure, and we
provide explicit convergence rate guarantees for both deterministic and
stochastic environments.

###### Key words and phrases:

Non-convex games; hidden games; stochastic algorithms; Nash equilibrium.

###### 2020 Mathematics Subject Classification:

Primary 91A10, 91A26; secondary 68Q32.

##  1\. Introduction

Many powerful AI architectures are based on the idea of combining conceptually
straightforward settings coming from game theory with the expressive power of
neural nets. Some prominent examples of this type include generative
adversarial networks [14], robust reinforcement learning [37], adversarial
training [26], multi-agent reinforcement learning in games [40, 36, 42], and
even multi-player games that include free-form natural-language communication
[4]. Intuitively, in all these cases, the game-theoretic abstraction serves to
provide a palpable, easy-to-understand target, i.e., an equilibrium solution
with strong axiomatic justification. However, from a complexity-theoretic
standpoint, such targets are excessively ambitious, requiring huge amounts of
data to express and compute, even approximately. Because of this, the agents’
policies must be encoded via a universal function approximator (such as a
neural net) and training this architecture boils down to iteratively updating
these parameters until the process – hopefully! – converges to the target
equilibrium.

Unfortunately, despite the ubiquitousness of these settings, the design of
algorithms with provable convergence guarantees is still relatively lacking.
This deficit is not surprising if one considers that even the – comparatively
much simpler – problem of equilibrium learning in finite games is hindered by
numerous computational hardness [9, 10] as well as dynamic impossibility
results [15, 16, 19, 24, 31, 30]. In this regard, our best hope for designing
provably convergent algorithms is to focus on specific classes of games with
some _useful structure_ to exploit.

One of the most well-established frameworks of this type is the class of
_monotone games_ whose study goes back at least to Rosen [38]. As special
cases, this setting includes single-agent convex minimization problems, two-
player convex-concave min-max games, diagonally convex $N$-player games, etc.
Owing to this connection, there has been a proliferation of strong positive
results at the interface of game theory and optimization, see e.g., [39, 28]
and references therein. In our case however, the agents do not play this
monotone game directly, but can only access it _indirectly_ via an encoding
layer of _control variables_ – like the weight parameters of a neural net that
outputs a feasible strategy profile for the game in question. In this sense,
from a machine learning perspective, the strategies of the game are _latent
variables_ , so we can think of each player as being equipped with a smooth
mapping from a high-dimensional space of control variables to the strategy
space of the game. Importantly, in contrast to the control variables, the
latent variables are not directly accessible to the players themselves and
should only be viewed as auxiliary variables – to all extents and purposes,
the goal remains to find an operationally desirable control layer
configuration. In this sense, the convex structure of the game becomes
“hidden” behind the control layer, which entangles multiple input/control
variables into nonlinear manifolds of latent variables.

As a result, the convex structure of the underlying game is effectively
destroyed, resulting in highly non-convex end-to-end interactions. This raises
the following central challenge:

Can we design provably convergent algorithms for non-convex games with a
hidden structure in the presence of general couplings between control and
latent variables?

Prior work in the area has shown that this is a promising and, at the same
time, highly challenging question. In [43], the setting of hidden bilinear
games was introduced and a number of negative results were presented, to the
effect that gradient-descent-ascent can exhibit a variety of non-convergent
behaviors, even when the game admits a hidden _bilinear_ structure.
Subsequently, [13] provided an approximate minimax theorem for a class of two-
agent games where the players pick neural networks, but did not provide any
convergent training algorithm for this class of games. Instead, the first
positive result on the dynamics of hidden games was obtained by [44] who
established a series of non-local convergence guarantees to the von Neumann
max-min solution of the game in the case of two-agent hidden strictly convex-
concave games for all initial conditions satisfying a certain genericity
assumption. This approach, however, only applied to _continuous-time dynamics_
–  _not algorithms_ – and it further imposed strong separability assumptions
on the representation of the game in the control layer. More recently, [32]
established the first global convergence guarantees in hidden games but, once
again, these apply only to _continuous-time dynamics_ and a special case of
two-agent convex-concave games (akin to playing a convex combination of hidden
games with one-dimensional latent spaces). This paper is the closest
antecedent to our work as it introduces a dynamical system, called Generalized
Natural Gradient Flow, which makes the $L^{2}$ norm between the equilibrium in
the hidden game and the current set of latent variables a Lyapunov function
for the system.

#### Our results & techniques.

Our paper seeks to provide an affirmative answer to the key challenge above
under minimal assumptions on the coupling between latent and control
variables. To that effect, we only assume that each agent is able to affect a
measurable change along any latent variable by updating their control
variables appropriately; without this assumption spurious equilibria can
emerge due to the deficiency of the control layer architecture. Importantly
however, even though the map from control to latent variables is known to the
players, _we do not assume_ that it can be efficiently inverted (e.g., to
solve for a profile of control variables that realizes a profile of latent
variables). Otherwise, if it could, the entire game could be solved directly
in the latent layer and then ported back to the control layer, thus rendering
the whole problem moot – and, indeed, when working with realistic neural net
architectures, this inversion problem is, to all intents and purposes,
impossible.

For intuition, we begin by designing a new continuous-time flow, that we call
preconditioned hidden gradient dynamics, and which enjoys strong convergence
properties in games with a hidden strictly monotone structure (Proposition 1).
Similarly to [32], this is achieved by using the $L^{2}$ norm in the latent
layer as a Lyapunov function in the control layer; however, the similarities
with the existing literature end there. Our paper does not make any
separability or low-dimensionality assumptions, and is otherwise _purely
algorithmic:_ specifically, building on the continuous-time intuition, we
provide a concrete, implementable algorithm, that we call _preconditioned
hidden gradient descent_ (PHGD); this algorithm is run with _stochastic
gradients_ , and enjoys a series of strong, global convergence guarantees in
hidden games.

First, as a baseline, Theorem 1 shows that a certain averaged process achieves
an $\operatorname{\mathcal{O}}(1/\sqrt{t})$ convergence rate in all games with
a hidden monotone structure and Lipschitz continuous loss functions. If the
hidden structure is strongly monotone, Theorem 2 further shows that this rate
can be improved to $\operatorname{\mathcal{O}}(1/t)$ for the _actual_
trajectory of the players’ control variables; and if the algorithm is run with
full, deterministic gradients, the rate becomes _geometric_ (Theorem 3). To
the best of our knowledge, these are the first bona fide algorithmic
convergence guarantees for games with a hidden structure.

$\cdots$$\operatorname{softmax}$$\theta$$R$$P$$S$$R$$P$$S$$\operatorname{softmax}$$\phi$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$

Figure 1.  A hidden game of Rock-Paper-Scissors with strategies encoded by two
multi-layer perceptrons (MLPs), whose $4$-dimensional input is dictated by the
two players (cf. [32]). The nonlinearity of the MLP representation maps leads
to a highly non-convex non-concave zero-sum game. However, by employing PHGD,
both players’ MLP control variables accurately identify the $(1/3,1/3,1/3)$
equilibrium in the game’s latent space.

##  2\. Problem setup and preliminaries

Throughout the sequel, we will focus on continuous $N$-player games where each
player, indexed by $i\in\mathcal{N}\coloneqq\\{1,\ldots,N\\}$, has a convex
set of _control variables_
$\theta_{i}\in\Theta_{i}\coloneqq\mathbb{R}^{m_{i}}$, and a continuously
differentiable _loss function_ $\ell_{i}\colon\Theta\to\mathbb{R}$, where
$\Theta\coloneqq\prod_{i}\Theta_{i}$ denotes the game’s _control space_. For
concreteness, we will refer to the tuple
$\Gamma\equiv\Gamma(\mathcal{N},\Theta,\ell)$ as the _base game_.

The most relevant solution concept in this setting is that of a _Nash
equilibrium_ , i.e., an action profile $\theta^{\ast}\in\Theta$ that
discourages unilateral deviations. Formally, we say that
$\theta^{\ast}\in\Theta$ is a _Nash equilibrium_ of the base game $\Gamma$ if

$\ell_{i}(\theta^{\ast})\leq\ell_{i}(\theta_{i};\theta^{\ast}_{-i})\quad\text{for
all $\theta_{i}\in\Theta_{i}$, $i\in\mathcal{N}$}$ (NE)

where we employ the standard game-theoretic shorthand
$(\theta_{i};\theta_{-i})$ to distinguish between the action of the $i$-th
player and that of all other players in the game. Unfortunately, designing a
learning algorithm that provably outputs a Nash equilibrium is a very elusive
task: the impossibility results of Hart & Mas-Colell [15, 16] already preclude
the existence of uncoupled dynamics that converge to a Nash equilibrium in all
games; more recently, Milionis et al. [31] established a similar impossibility
result even for possibly _coupled_ dynamics (in both discrete and continuous
time), while Daskalakis et al. [9, 10] has shown that even the _computation_
of an approximate equilibrium can be beyond reach.

In view of this, our work focuses on games with a hidden, _latent_ structure
that can be exploited to compute its Nash equilibria. More precisely, inspired
by [43, 44] we have the following definition.

######  Definition 1.

We say that the game $\Gamma\equiv\Gamma(\mathcal{N},\Theta,\ell)$ admits a
_latent_ – or _hidden_ –  _structure_ if:

  1. (1)

Each player’s control variables can be mapped faithfully to a closed convex
set of _latent variables_
$x_{i}\in\mathcal{X}_{i}\subseteq\mathbb{R}^{d_{i}}$; formally, we posit that
there exists a Lipschitz smooth map
$\chi_{i}\colon\Theta_{i}\to\mathcal{X}_{i}$ with no critical points and such
that $\operatorname{cl}(\chi_{i}(\Theta_{i}))=\mathcal{X}_{i}$.

  2. (2)

Each player’s loss function factors through the game’s _latent space_
$\mathcal{X}\coloneqq\prod_{i}\mathcal{X}_{i}$ as

$\ell_{i}(\theta)=f_{i}(\chi_{1}(\theta_{1}),\dotsc,\chi_{N}(\theta_{N}))$ (1)

for some Lipschitz smooth function $f_{i}\colon\mathcal{X}\to\mathbb{R}$
called the player’s _latent loss function_.

For concreteness, we will refer to the product map
$\chi(\theta)=(\chi_{i}(\theta_{i}))_{i\in\mathcal{N}}$ as the game’s
_representation map_ , and the tuple
$\mathcal{G}\equiv\mathcal{G}(\mathcal{N},\mathcal{X},f)$ will be called the
_hidden / latent game_. To simplify notation later on, we also assume that
$\mathcal{X}_{i}$ has nonempty topological interior, so, in particular,
$\dim(\mathcal{X}_{i})=d_{i}\leq m_{i}$.

We illustrate the above notions in two simple – but not simplistic – examples
below; for a schematic representation, cf. Fig. 2.

$\theta$$\cdot$Control variables$x=\chi(\theta)$$\cdot$Latent
variables$\chi$$\begin{array}[]{l}\mathbb{R}^{d}\\\
\end{array}$$\begin{array}[]{l}\mathbb{R}^{m}\\\
\end{array}$$\begin{array}[]{l}\mathbb{R}\\\ \end{array}$$f$$\ell=f\circ\chi$
Figure 2. Schematic representation of a game with a hidden / latent structure.

######  Example 2.1.

Consider a single-agent game ($N=1$) where the objective is to minimize the
non-convex function
$\ell(\theta)=\sum_{\alpha=1}^{\lvert\mathcal{D}\rvert}(\operatorname{sigmoid}(\theta_{\alpha})-s_{\alpha})^{2}$
over a dataset $\mathcal{D}=\\{s_{\alpha}\\}$. This problem can be recast as a
hidden convex problem with
$f(x)=\sum_{\alpha=1}^{\lvert\mathcal{D}\rvert}(x_{\alpha}-s_{\alpha})^{2}$
and $\chi(\theta)=\operatorname{sigmoid}(\theta)$.

######  Example 2.2.

A more complex scenario involves non-convex / non-concave min-max optimization
problems of the form
$\min_{\theta_{1}}\max_{\theta_{2}}\chi_{1}(\theta_{1})^{\intercal}C\chi_{2}(\theta_{2})$
where $\chi_{1}$ and $\chi_{2}$ are preconfigured multi-layer perceptrons
constructed with smooth activation functions (such as CeLUs). This problem can
be reformulated as a hidden bilinear problem by setting
$f_{1}(x_{1},x_{2})=x_{1}^{\intercal}Cx_{2}=-f_{2}(x_{1},x_{2})$.

Before moving forward, there are some points worth noting regarding the above
definitions.

######  Remark 1.

First, the requirement $\operatorname{cl}(\chi(\Theta))=\mathcal{X}$ means
that all latent variable profiles $x\in\mathcal{X}$ can be approximated to
arbitrary accuracy in the game’s control space. The reason that we do not make
the stronger assumption $\chi(\Theta)=\mathcal{X}$ is to capture cases like
the sigmoid map: if $\chi(\theta)=[1+\exp(-\theta)]^{-1}$ for
$\theta\in\mathbb{R}$, the image of $\chi$ is the interval $(0,1)$, which is
convex but not closed.

######  Remark 2.

Second, the requirement that $\chi$ has no critical points simply means that,
for any control variable configuration $\theta\in\Theta$, the Jacobian
$\operatorname{Jac}(\chi(\theta))$ of $\chi$ at $\theta$ has full rank. By the
implicit function theorem [23], this simply means that $\chi$ locally looks
like a projection (in suitable coordinates around $\theta$), so it is possible
to affect a measurable change along any feasible latent direction by updating
each player’s control variables appropriately. This is no longer true if
$\chi$ has critical points, so this is a minimal requirement to ensure that no
spurious equilibria appear in the game’s latent space.

To proceed, we will assume that the latent game is _diagonally convex_ in the
sense of Rosen [38], a condition more commonly known in the optimization
literature as _monotonicity_ [12]. Formally, let

$g_{i}(x)=\nabla_{i}f_{i}(x)\coloneqq\nabla_{x_{i}}f_{i}(x)$ (2)

denote the individual gradient of the latent loss function of player
$i\in\mathcal{N}$, and write $g(x)=(g_{1}(x),\dotsc,g_{N}(x))$ for the profile
thereof. We then say that the latent game $\mathcal{G}$ is:

  * •

_Monotone_ if

$\langle g(x^{\prime})-g(x),\,x^{\prime}-x\rangle\geq 0\quad\text{for all
$x,x^{\prime}\in\mathcal{X}$}.$ (3a)

  * •

_Strictly monotone_ if

$\langle g(x^{\prime})-g(x),\,x^{\prime}-x\rangle>0\quad\text{for all
$x,x^{\prime}\in\mathcal{X}$, $x\neq x^{\prime}$}.$ (3b)

  * •

_Strongly monotone_ if, for some $\mu>0$, we have

$\langle g(x^{\prime})-g(x),\,x^{\prime}-x\rangle\geq\mu\lVert
x^{\prime}-x\rVert^{2}\quad\text{for all $x,x^{\prime}\in\mathcal{X}$}.$ (3c)

Clearly, strong monotonicity implies strict monotonicity, which in turn
implies monotonicity; on the other hand, when we want to distinguish between
problems that are monotone but not strictly monotone, we will say that $g$ is
_merely monotone_. Finally, extending the above to the base game, we will say
that $\Gamma$ admits a _hidden monotone structure_ when the latent game
$\mathcal{G}$ is monotone as above (and likewise for strictly / strongly
monotone structures).

Examples of monotone games include neural Kelly auctions and Cournot
oligopolies [20, 5, 25, 6], covariance matrix optimization problems and power
control [39, 27, 29], certain classes of congestion games [35], etc. In
particular, in the case of convex minimization problems, monotonicity (resp.
strict / strong monotonicity) corresponds to convexity (resp. strict / strong
convexity) of the problem’s objective function. In all cases, it is
straightforward to check that the image $x^{\ast}=\chi(\theta^{\ast})$ of a
Nash equilibrium $\theta^{\ast}\in\Theta$ of the base game satisfies a
Stampacchia variational inequality of the form

$\langle g(x^{\ast}),\,x-x^{\ast}\rangle\geq 0\quad\text{for all
$x\in\mathcal{X}$}.$ (SVI)

In turn, by monotonicity, this characterization is equivalent to the Minty
variational inequality

$\langle g(x),\,x-x^{\ast}\rangle\geq 0\quad\text{for all $x\in\mathcal{X}$}.$
(MVI)

To avoid trivialities, we will assume throughout that the solution set
$\mathcal{X}^{\ast}$ of (SVI)/(MVI) is nonempty. This is a standard assumption
without which the problem is not well-posed – and hence, meaningless from an
algorithmic perspective.

#### Notation.

To streamline notation (and unless explicitly mentioned otherwise), we will
denote control variables by $\theta_{i}$ and $\theta$, and we will write
$x_{i}=\chi_{i}(\theta_{i})$ and $x=\chi(\theta)$ for the induced latent
variables. We will also write $m\coloneqq\sum_{i}m_{i}$ for the dimensionality
of the game’s control space $\Theta$ and $d\coloneqq\sum_{i}d_{i}$ for the
dimensionality of the latent space $\mathcal{X}$ (so, in general, $m\geq d$).
Finally, when the representation map $\chi$ is clear from the context, we will
write
$\mathbf{J}_{i}(\theta_{i})\coloneqq\operatorname{Jac}(\chi_{i}(\theta_{i}))\in\mathbb{R}^{d_{i}\times
m_{i}}$ for the Jacobian matrix of $\chi_{i}$ at $\theta_{i}\in\Theta_{i}$,
and $\mathbf{J}(\theta)=\bigoplus_{i}\mathbf{J}_{i}(\theta_{i})$ for the
associated block diagonal sum.

##  3\. Hidden gradients and preconditioning

We are now in a position to present our main algorithmic scheme for
equilibrium learning in games with a hidden monotone structure. In this
regard, our aim will be to overcome the following limitations in the existing
literature on learning in hidden games:  (it n) the literature so far has
focused exclusively on continuous-time dynamics, with no discrete-time
algorithms proven to efficiently converge to a solution;  (it n) the number of
players is typically limited to two; and  (it n) the representation maps are
_separable_ in the sense that the control variables are partitioned into
subsets and each subset affects exactly one latent variable.111The
separability assumption also rules out the logit representation
$\exp(\theta_{i\alpha})\big{/}\sum_{\beta}\exp(\theta_{i\beta})$ that is
standard when the latent structure expresses mixed strategies in a finite
game.

We start by addressing the last two challenges first. Specifically, we begin
by introducing a gradient preconditioning scheme that allows us to design a
convergent _continuous-time_ dynamical system for hidden monotone games with
an _arbitrary_ number of players and _no separability_ restrictions for its
representation maps. Subsequently, we propose a bona fide algorithmic scheme –
which we call _preconditioned hidden gradient descent_ (PHGD) – by
discretizing the said dynamics, and we analyze the algorithm’s long-run
behavior in Section 4.

###  3.1. Continuous-time dynamics for hidden games

To connect our approach with previous works in the literature, our starting
point will be a simple setting already captured within the model of [32], min-
max games with a hidden convex-concave structure and unconstrained one-
dimensional control and latent spaces per player, i.e.,
$\Theta_{i}=\mathbb{R}=\mathcal{X}_{i}$ for $i=1,2$. We should of course note
that this specific setting is fairly restrictive and not commonly found in
deep neural network practice: in real-world deep learning applications, neural
nets generally comprise multiple interconnected layers with distinct
activation functions, so the input-output relations are markedly more complex
and intertwined. Nevertheless, the setting’s simplicity makes the connection
with natural gradient methods particularly clear, so as in [32], it will serve
as an excellent starting point.

Concretely, Mladenovic et al. [32] analyze the _natural hidden gradient
dynamics_

$\dot{\theta}_{i}=-\frac{1}{\lvert\chi_{i}^{\prime}(\theta_{i})\rvert^{2}}\frac{\partial\ell_{i}}{\partial\theta_{i}}\quad\text{for
all $i\in\mathcal{N}$}.$ (NHGD)

The reason for this terminology – and the driving force behind the above
definition – is the observation that, in one-dimensional settings, a direct
application of the chain rule to the defining relation
$\ell_{i}=f_{i}\circ\chi$ of the game’s latent loss functions yields
$\partial\ell_{i}/\partial\theta_{i}=\chi_{i}^{\prime}(\theta_{i})\cdot\partial
f_{i}/\partial x_{i}$ so, in turn, (NHGD) becomes

$\dot{\theta}_{i}=-\frac{1}{\chi_{i}^{\prime}(\theta_{i})}\frac{\partial
f_{i}}{\partial x_{i}}$ (4)

where, for simplicity, we are tacitly assuming that
$\chi_{i}(\theta_{i})^{\prime}>0$.

This expression brings two important points to light. First, even though
(NHGD) is defined in terms of the actual, control-layer gradients
$\partial\ell_{i}/\partial\theta_{i}$ of $\Gamma$, Eq. 4 shows that the
dynamics are actually driven by the latent-layer, “hidden gradients”
$g_{i}(x)=\partial f_{i}/\partial x_{i}$ of $\mathcal{G}$. Second, the
preconditioner $\lvert\chi_{i}^{\prime}(\theta_{i})\rvert^{-2}$ in (NHGD) can
be seen as a Riemannian metric on $\Theta$: instead of defining gradients
relative to the standard Euclidean metric of $\Theta\equiv\mathbb{R}^{N}$,
(NHGD) can be seen as a gradient flow relative to the Riemannian metric
$g_{ij}(\theta)=\delta_{ij}\chi_{i}^{\prime}(\theta_{i})$, which captures the
“natural” geometry induced by the representation map $\chi$.222We do not
attempt to provide here a primer on Riemannian geometry; for a masterful
introduction, see [22].

From an operational standpoint, the key property of (NHGD) that enabled the
analysis of [32] is the observation that the $L^{2}$ energy function

$E(\theta)=\tfrac{1}{2}\lVert\chi(\theta)-x^{\ast}\rVert^{2}$ (5)

between the latent representation $x=\chi(\theta)$ of $\theta$ and a solution
$x^{\ast}$ of (SVI) / (MVI) is a Lyapunov function for (NHGD). Indeed, a
straightforward differentiation yields

$\dot{E}(\theta)=\frac{1}{2}\frac{d}{dt}\lVert
x-x^{\ast}\rVert^{2}=\sum\nolimits_{i}\dot{x}_{i}\cdot(x_{i}-x^{\ast}_{i})=-[g(\chi(\theta))]^{\intercal}(\chi(\theta)-x^{\ast})\leq
0$ (6)

with the penultimate step following from (4) and the last one from (MVI). It
is then immediate to see that the latent orbits $x(t)=\chi(\theta(t))$ of
(NHGD) converge to equilibrium in strictly monotone games.

The approach in the example above depends crucially on the separability
assumption which, among others, trivializes the problem. Indeed, if there is
no coupling between control variables in the game’s latent space, the
equations $x_{i}=\chi_{i}(\theta_{i})$ can be backsolved easily for $\theta$
(e.g., via binary search), so it is possible to move back-and-forth between
the latent and control layers, ultimately solving the game in the latent layer
and subsequently extracting a solution configuration in the control layer.
Unfortunately however, extending the construction of (NHGD) to a non-separable
setting is not clear, so it is likewise unclear how to exploit the hidden
structure of the game beyond the separable case.

To that end, our point of departure is the observation that the Lyapunov
property (6) of the energy function $E(\theta)$ is precisely the key feature
that enables convergence of (NHGD). Thus, assuming that control variables are
mapped to latent variables via a general – though possibly highly coupled –
representation map $\chi\colon\Theta\to\mathcal{X}$, we will consider an
abstract preconditioning scheme of the form

$\dot{\theta}_{i}=-\mathbf{P}_{i}(\theta_{i})v_{i}(\theta)$ (7)

where

$v_{i}(\theta)\coloneqq\nabla_{\theta_{i}}\ell_{i}(\theta)$ (8)

denotes the individual loss gradient of player $i$, while the preconditioning
matrix $\mathbf{P}_{i}(\theta_{i})\in\mathbb{R}^{m_{i}\times m_{i}}$ is to be
designed so that (6) still holds under (7). In this regard, a straightforward
calculation (which we prove in Appendix A) yields the following:

######  Lemma 1.

Under the dynamics (7), we have

$\dot{E}(\theta)=-\sum\nolimits_{i\in\mathcal{N}}[g_{i}(\chi(\theta))]^{\intercal}\mathbf{J}_{i}(\theta_{i})\mathbf{P}_{i}(\theta_{i})[\mathbf{J}_{i}(\theta_{i})]^{\intercal}(\chi_{i}(\theta_{i})-x^{\ast}_{i})$
(9)

where, as per Section 2, $\mathbf{J}_{i}(\theta_{i})\in\mathbb{R}^{d_{i}\times
m_{i}}$ denotes the Jacobian matrix of the map
$\chi_{i}\colon\Theta_{i}\to\mathcal{X}_{i}$. More compactly, letting
$\mathbf{P}\coloneqq\bigoplus_{i}\mathbf{P}_{i}$ denote the block-diagonal
ensemble of the players’ individual preconditioning matrices $\mathbf{P}_{i}$
(and suppressing control variable arguments for concision), we have

$\dot{E}=-g(x)^{\intercal}\cdot\mathbf{J}\mathbf{P}\mathbf{J}^{\intercal}\cdot(x-x^{\ast})$
(10)

In view of Lemma 1, a direct way to achieve the target Lyapunov property (6)
would be to find a preconditioning matrix $\mathbf{P}$ such that
$\mathbf{J}\mathbf{P}\mathbf{J}^{\intercal}=\mathbf{I}$. However, since
$\mathbf{J}$ is surjective (by the faithfulness assumption for $\chi$), the
Moore-Penrose inverse $\mathbf{J}^{+}$ of $\mathbf{J}$ will be a right inverse
to $\mathbf{J}$, i.e., $\mathbf{J}\mathbf{J}^{+}=\mathbf{I}$. Hence, letting
$\mathbf{P}=(\mathbf{J}^{\intercal}\mathbf{J})^{+}=\mathbf{J}^{+}[\mathbf{J}^{+}]^{\intercal}$,
we obtain:

$\mathbf{J}\mathbf{P}\mathbf{J}^{\intercal}=\mathbf{J}(\mathbf{J}^{\intercal}\mathbf{J})^{+}\mathbf{J}^{\intercal}=\mathbf{J}\mathbf{J}^{+}(\mathbf{J}^{\intercal})^{+}\mathbf{J}^{\intercal}=\mathbf{I}\cdot\mathbf{I}=\mathbf{I}$
(11)

In this way, unraveling the above, we obtain the _preconditioned hidden
gradient flow_

$\dot{\theta}_{i}=-\mathbf{P}_{i}(\theta_{i})\nabla_{i}\ell_{i}(\theta_{i})\quad\text{with}\quad\mathbf{P}_{i}(\theta_{i})=[\mathbf{J}_{i}(\theta_{i})^{\intercal}\mathbf{J}_{i}(\theta_{i})]^{+}$
(PHGF)

By virtue of design, the following property of (PHGF) is then immediate:

######  Proposition 1.

Suppose that $\Gamma$ admits a latent strictly monotone structure in the sense
of (3b). Then the energy function (5) is a strict Lyapunov function for
(PHGF), and every limit point $\theta^{\ast}$ of $\theta(t)$ is a Nash
equilibrium of $\Gamma$.

Proposition 1 validates our design choices for the preconditioning matrix
$\mathbf{P}$ as it illustrates that the dynamics (PHGF) converge to Nash
equilibrium, without any separability requirements or dimensionality
restrictions; in this regard, Proposition 1 already provides a marked
improvement over the corresponding convergence result of [32] for (NHGD). To
streamline our presentation, we defer the proof of Lemmas 1 and 1 to Appendix
A, and instead proceed directly to provide a bona fide, algorithmic
implementation of (PHGF).

Figure 3. Exploiting a hidden convex structure in the control layer. On the
left, we present the dynamics (PHGF) in the example of minimizing the simple
function
$f(\theta)=\operatorname{KL}(\mathrm{logit}(\theta_{1},\theta_{2})\|(1/2,1/3,1/6))$
over $\Theta\equiv\mathbb{R}^{2}$. In the subfigure to the right, we
illustrate the hidden convex structure of the energy landscape, from the non-
convex sublevel sets of $\Theta$ to the latent space
$\mathcal{X}\equiv\\{(x_{1},x_{2})\in\mathbb{R}^{2}_{\geq 0}:x_{1}+x_{2}\leq
1\\}$.

###  3.2. PHGD

In realistic machine learning problems, any algorithmic scheme based on (PHGF)
will have to be run in an iterative, discrete-time environment; moreover, due
to the challenges posed by applications with large datasets and optimization
objectives driven by the minimization of empirical risk, we will need to
assume that players only have access to a stochastic version of their full,
deterministic gradients. As such, we will make the following blanket
assumptions that are standard in the stochastic optimization literature [17,
21]:

######  Assumption 1.

Each agent’s loss function is an expectation of a random function
$L_{i}\colon\Theta\times\Omega\to\mathbb{R}$ over a complete probability space
$(\Omega,\mathcal{F},\operatorname{\mathbb{P}})$, i.e.,
$\ell_{i}(\theta)=\operatorname{\mathbb{E}}[L_{i}(\theta;\omega)]$. We further
assume that:

  1. (1)

$L_{i}(\theta;\omega)$ is measurable in $\omega$ and $\beta$-Lipschitz smooth
in $\theta$ (for all $\theta\in\Theta$ and all $\omega\in\Omega$
respectively).

  2. (2)

The gradients of $L_{i}$ have bounded second moments, i.e.,

$\sup_{\theta\in\Theta}\operatorname{\mathbb{E}}[\lVert\nabla
L_{i}(\theta;\omega)\rVert^{2}]\leq M^{2}.$ (12)

Taken together, the two components of Assumption 1 imply that each $\ell_{i}$
is differentiable and Lipschitz continuous (indeed, by Jensen’s inequality, we
have $\lVert\operatorname{\mathbb{E}}[\nabla
L_{i}(\theta;\omega)]\rVert^{2}\leq\operatorname{\mathbb{E}}[\lVert\nabla
L_{i}(\theta;\omega)\rVert^{2}]\leq M^{2}$). Moreover, by standard dominated
convergence arguments, $\nabla L_{i}(\theta;\omega)$ can be seen as an
unbiased estimator of $\nabla\ell_{i}(\theta)$, that is,
$\ell_{i}(\theta)=\operatorname{\mathbb{E}}[\nabla L_{i}(\theta;\omega)]$ for
all $\theta\in\Theta$. In view of this, we will refer to the individual loss
gradients $\nabla_{i}L_{i}(\theta;\omega)$ of player $i\in\mathcal{N}$ as the
player’s individual _stochastic gradients_.

With all this in mind, the _preconditioned hidden gradient descent_ algorithm
is defined as the stochastic first-order recursion

$\theta_{i,t+1}=\theta_{i,t}-\gamma_{t}\mathbf{P}_{i,t}V_{i,t}$ (PHGD)

where:

  1. (1)

$\theta_{i,t}$ denotes the control variable configuration of player
$i\in\mathcal{N}$ at each stage $t=1,2,\dotsc$

  2. (2)

$\gamma_{t}>0$ is a variable step-size sequence, typically of the form
$\gamma_{t}\propto 1/t^{p}$ for some $p\in[0,1]$.

  3. (3)

$\mathbf{P}_{i,t}\coloneqq\mathbf{P}_{i}(\theta_{i,t})=[\mathbf{J}_{i}(\theta_{i,t})^{\intercal}\mathbf{J}_{i}(\theta_{i,t})]^{+}$
is the preconditioner of player $i\in\mathcal{N}$ at the $t$-th epoch.

  4. (4)

$V_{i,t}\coloneqq\nabla_{i}L(\theta_{i,t};\omega_{t})$ is an individual
stochastic loss gradient generated at the control variable configuration
$\theta_{t}$ by an i.i.d. sample sequence $\omega_{t}\in\Omega$,
$t=1,2,\dotsc$

The basic recursion (PHGD) can be seen as a noisy Euler discretization of the
continuous flow (PHGF), in the same way that ordinary stochastic gradient
descent can be seen as a noisy discretization of gradient flows. In this way,
(PHGD) is subject to the same difficulties underlying the analysis of
stochastic gradient descent methods; we address these challenges in the next
section.

##  4\. Convergence analysis and results

In this section, we present our main results regarding the convergence of
(PHGD) in hidden monotone games. Because we are interested not only on the
asymptotic convergence of the method but also on its _rate_ of convergence, we
begin this section by defining a suitable merit function for each class of
hidden monotone games under consideration; subsequently, we present our main
results in Section 4.2, where we also discuss the main technical tools
enabling our analysis. To streamline our presentation, all proofs are deferred
to Appendix B.

###  4.1. Merit functions and convergence metrics

In the variational context of (SVI) / (MVI), the quality of a candidate
solution $\hat{x}$ is typically evaluated by means of the _restricted merit
function_

$\operatorname{Gap}\nolimits_{\mathcal{C}}(\hat{x})\coloneqq\sup\nolimits_{x\in\mathcal{C}}\langle
g(x),\,\hat{x}-x\rangle$ (13)

where the “test domain” $\mathcal{C}$ is a relatively open subset of
$\mathcal{X}$ [3]. The _raison d’être_ of this definition is that, if $g$ is
monotone and $x^{\ast}\in\mathcal{C}$ is a solution of (SVI) / (MVI), we have

$\langle g(x),\,x^{\ast}-x\rangle\leq\langle
g(x^{\ast}),\,x^{\ast}-x\rangle\leq 0\quad\text{for all $x\in\mathcal{C}$},$
(14)

so the supremum in (B.6) cannot be too positive if $\hat{x}$ is an approximate
solution of (SVI) / (MVI). This is encoded in the following lemma, which,
among others, justifies the terminology “merit function”:

######  Lemma 2.

Suppose that $g$ is monotone. If $\hat{x}$ is a solution of (SVI) / (MVI), we
have $\operatorname{Gap}_{\mathcal{C}}(\hat{x})=0$ whenever
$\hat{x}\in\mathcal{C}$. Conversely, if
$\operatorname{Gap}_{\mathcal{C}}(\hat{x})=0$ and $\mathcal{C}$ is a
neighborhood of $\hat{x}$ in $\mathcal{X}$, then $\hat{x}$ is a solution of
(SVI) / (MVI).

Lemma 2 extends similar statements by Auslender & Teboulle [3] and Nesterov
[33]; the precise variant that we state above can be found in [1], but, for
completeness, we provide a proof in Appendix B.

Now, since a latent variable profile $x^{\ast}=\chi(\theta^{\ast})$ solves
(SVI) if and only if the control variable configuration $\theta^{\ast}$ is
Nash equilibrium of the base game, the quality of a candidate solution
$\hat{\theta}\in\Theta$ with $\hat{x}=\chi(\hat{\theta})$ can be assessed by
the induced gap function

$\operatorname{Gap}(\hat{\theta})\coloneqq\operatorname{Gap}_{\mathcal{X}}(\chi(\hat{\theta}))=\sup\nolimits_{x\in\mathcal{X}}\langle
g(x),\,\hat{x}-x\rangle.$ (15)

Indeed, since $\hat{x}=\chi(\hat{\theta})\in\mathcal{X}$, Lemma 2 shows that
$\operatorname{Gap}(\hat{\theta})\geq 0$ with equality if and only if
$\hat{x}$ is a Nash equilibrium of the base game $\Gamma$. In this regard, Eq.
15 provides a valid equilibrium convergence metric for $\Gamma$, so we will
use it freely in the sequel as such; for a discussion of alternative
convergence metrics, we refer the reader to Appendix B.

###  4.2. Convergence results

We are now in a position to state our main results regarding the equilibrium
convergence properties of (PHGD). To streamline our presentation, we present
our results from coarser to finer, starting with games that admit a hidden
_merely_ monotone structure and _stochastic_ gradient feedback, and refining
our analysis progressively to games with a hidden _strongly_ monotone
structure and _full_ gradient feedback.333As expected, convergence rates
improve along the way. In addition, to quantify this distortion between the
game’s latent and control layers, we will require a technical regularity
assumption for the game’s representation map $\chi\colon\Theta\to\mathcal{X}$.

######  Assumption 2.

The singular values of the Jacobian $\mathbf{J}(\theta)$ of the representation
map $\chi$ are bounded as

$\sigma_{\min}^{2}\leq\operatorname{eig}(\mathbf{J}(\theta)\mathbf{J}(\theta)^{\intercal})\leq\sigma_{\max}^{2}$
(16)

for some $\sigma_{\min},\sigma_{\max}\in(0,\infty)$ and for all
$\theta\in\Theta$.

With all this in hand, we begin by studying the behavior of (PHGD) in games
with a hidden monotone structure.

######  Theorem 1 (PHGD in hidden monotone games).

Suppose that players run (PHGD) in a hidden monotone game with learning rate
$\gamma_{t}\propto 1/t^{1/2}$. Then, under Assumptions 1 and 2, the averaged
process $\bar{}\theta_{t}\in\chi^{-1}\big{(}t^{-1}\sum_{s=1}^{t}x_{s}\big{)}$
enjoys the equilibrium convergence rate

$\operatorname{\mathbb{E}}[\operatorname{Gap}(\bar{}\theta_{t})]=\operatorname{\mathcal{O}}(\log
t/\sqrt{t}).\vskip 6.0pt plus 2.0pt minus 2.0pt$ (17)

As far as we are aware, Theorem 1 is the first result of its kind in the
hidden games literature – that is, describing the long-run behavior of a
discrete-time algorithm with stochastic gradient input. At the same time, it
is subject to two important limitations: the first is that the averaged state
$\bar{}\theta_{t}$ cannot be efficiently computed for general representation
maps; second, even if it could, the $\operatorname{\mathcal{O}}(\log
t/\sqrt{t})$ convergence rate is relatively slow. The two results that follow
show that both limitations can be overcome in games with a hidden _strongly
monotone_ structure. In this case (SVI)/(MVI) admits a (necessarily) unique
solution $x^{\ast}$ in the game’s control space, so we will measure
convergence in terms of the latent equilibrium distance

$\operatorname{Err}(\hat{\theta})\coloneqq\tfrac{1}{2}\lVert\chi(\hat{\theta})-x^{\ast}\rVert^{2}.$
(18)

With this in mind, we have the following convergence results:

######  Theorem 2 (PHGD in hidden strongly monotone games).

Suppose that players run (PHGD) in a hidden $\mu$-strongly monotone game with
$\gamma_{t}=\gamma/t$ for some $\gamma>\mu$. Then, under Assumptions 1 and 2,
the induced sequence of play $\theta_{t}\in\Theta$, $t=1,2,\dotsc$, enjoys the
equilibrium convergence rate

$\operatorname{\mathbb{E}}[\operatorname{Err}(\theta_{t})]=\operatorname{\mathcal{O}}(1/t).$
(19)

This rate is tight, even for standard strongly monotone games. To improve it
further, we will need to assume that (PHGD) is run with full, _deterministic_
gradients, i.e., $V_{t}=g(\theta_{t})$. In this case, we obtain the following
refinement of Theorem 2.

######  Theorem 3 (PHGD with full gradient feedback in hidden strongly
monotone games).

Suppose that players run (PHGD) in a hidden $\mu$-strongly monotone game with
full gradient feedback, and a suffciently small learning rate $\gamma>0$.
Then, under Assumptions 1 and 2, the induced sequence of play
$\theta_{t}\in\Theta$, $t=1,2,\dotsc$, converges to equilibrium at a geometric
rate, i.e.,

$\operatorname{Err}(\theta_{t})=\operatorname{\mathcal{O}}(\rho^{t})$ (20)

for some constant $\rho\in(0,1)$ that depends only on the primitives of
$\Gamma$ and the representation map $\chi$.

Importantly, up to logarithmic factors, the convergence rates of Theorems 1–3
mirror the corresponding rates for learning in monotone games. This take-away
is particularly important as it shows that, _when it exists, a hidden convex
structure can be exploited to the greatest possible degree, without any loss
of speed in convergence relative to standard, non-hidden convex problems._

The proofs of Theorems 1–3 are quite involved, so we defer the details to
Appendix B. That said, to give an idea of the technical steps involved, we
provide below (without proof) two lemmas that play a pivotal role in our
analysis. The first one hinges on a transformation of the problem’s defining
vector field $v(\theta)=(\nabla_{i}\ell_{i}(\theta))_{i\in\mathcal{N}}$ which,
coupled with the specific choice of preconditioner
$\mathbf{P}_{i}(\theta_{i})=[\mathbf{J}_{i}(\theta_{i})^{\intercal}\mathbf{J}_{i}(\theta_{i})]^{+}$
in (PHGD) allows us to effectively couple the latent and control layers of the
problem in a “covariant” manner:

######  Lemma 3.

Fix some $\hat{x}\in\mathcal{X}$, and consider the energy function
$E(\theta;\hat{x})=(1/2)\lVert\chi(\theta)-\hat{x}\rVert^{2}$. Then, for all
$\theta\in\Theta$, we have

$\mathbf{J}(\theta)\mathbf{P}(\theta)\nabla_{\theta}E(\theta;\hat{x})=\chi(\theta)-\hat{x}.$
(21)

Our second intermediate result builds on Lemma 3 and provides a “template
inequality” for the energy function $E(\theta;\hat{x})$ in the spirit of [7,
18, 11].

######  Lemma 4 (Template inequality).

Suppose that Assumptions 1 and 2 hold. Then, with notation as in Lemma 3, the
sequence $E_{t}\coloneqq(1/2)\lVert\chi(\theta_{t})-\hat{x}\rVert^{2}$,
$t=1,2,\dotsc$, satisfies

$E_{t+1}\leq
E_{t}-\gamma_{t}g(x_{t})^{\intercal}(x_{t}-\hat{x})+\gamma_{t}\phi_{t}+\gamma_{t}^{2}\psi_{t},$
(22)

where $x_{t}\coloneqq\chi(\theta_{t})$,
$\phi_{t}\coloneqq(\mathbf{J}(\theta_{t})\mathbf{P}(\theta_{t})V_{t}-g(x_{t}))^{\intercal}(x_{t}-\hat{x})$
and $\psi_{t}$ is a random error sequence with
$\sup_{t}\operatorname{\mathbb{E}}[\psi_{t}]<\infty$.

This inequality plays a pivotal role in our analysis because it allows us to
couple the restricted merit function (B.8) in the game’s control space with
the evolution of the algorithm’s quasi-Lyapunov function in the game’s latent
space. We provide the relevant details and calculations in Appendix B.

##  5\. Experiments

This section demonstrates our method’s applicability in a couple of different
and insightful setups. Technical details of those setups, as well as
additional experimental results are deferred to the supplementary material. We
start with a regularized version of Matching Pennies zero-sum game where the
players’ strategies are controlled by two individual preconfigured
differentiable MLPs. Each MLP acts as the player’s representation map
$\chi_{i}$, which for each input $\theta_{i}$ outputs a one-dimensional latent
variable $x_{i}=\chi_{i}(\theta_{i})$ guaranteed to lie in
$\mathcal{X}_{i}\equiv[0,1]$; the player’s latent space.

Figure 4. A solution trajectory of (PHGD) in a hidden Matching Pennies game
over the sub-level sets of the energy function in (5).

Figure 4 illustrates the trajectory of (PHGD), represented by the black curve.
The algorithm employs a constant step-size of $0.01$ and is initialized at the
arbitrary state $(1.25,2.25)$ in the control variables’ space. The color map
in the figure serves as a visual representation of the level sets associated
with the proposed energy function (5). Notably, the trajectory of the
algorithm intersects each of the energy function’s level sets at most once,
indicating its non-cycling behavior, which is an issue that shows up often in
the equilibration task. Due to the design of our hidden maps, the
stabilization at the point $(0,0)$ corresponds to the
$(\chi_{1}(0),\chi_{2}(0))=(\frac{1}{2},\frac{1}{2})$ the unique equilibrium
of the game.

In the second, more complex, example, we consider a strongly-monotone
regularized modification of an (atomic) El Farol Bar congestion game among
$N=30$ players [45, 2]. In this setup, we let the control space of each player
$i$ be multi-dimensional, namely, $\Theta_{i}\equiv\mathbb{R}^{5}$,
$i\in\mathcal{N}$, and, as in the previous example, the representation map of
each player is instantiated by some preconfigured differentiable MLP whose
output $x_{i}\coloneqq\chi_{i}(\theta_{i})$ is guaranteed to lie in $[0,1]$.
The MLP’s output is going to be the probability with which player $i$ visits
the El Farol bar. For the interested reader, further details, including
technical specification of the MLPs, and loss functions of the games, can be
found in the supplementary material.

Figure 5. The evolution of the $L^{2}$ error function
$\operatorname{Err}_{\mathcal{X}}(\chi(\theta))$ of (PHGD) and GD with
constant step-size $0.01$ in the regularized games of Matching Pennies and El
Farol Bar as depicted in a semi-logarithmic scale. In the Matching Pennies
game (left) we depict a single trajectory initialized at $(1.25,2.25)$, while
in the El Farol Bar game (right) game we depict the mean and confidence bounds
of $100$ random trajectories.

Fig. 5 provides a comparative analysis of the performance between (PHGD), and
the standard GD method in the aforementioned two game scenarios. In Fig. 5
(left) we explore the Matching Pennies game, where GD exhibits slightly
erratic behavior. Despite eventually converging to the game’s equilibrium
point, GD’s convergence rate, in this case, can be described as linear at
best. In Fig. 5 (right), we examine the El Farol Bar game. Interestingly, in
this highly complex setup, GD fails to reach the equilibrium point entirely.
In contrast, (PHGD) not only manages to converge in both of these setups, but
it also consistently maintains an exponential rate of convergence. This stark
difference underscores the efficacy and robustness of our algorithm.

##  6\. Conclusion

This paper proposed a new algorithmic framework with strong formal convergence
guarantees in a general class non-convex games with a latent monotone
structure. Our algorithmic method – which we call preconditioned hidden
gradient descent – relies on an appropriately chosen gradient preconditioning
scheme akin to natural gradient ideas. Our class of games combines the useful
structure of monotone operators as well as the notion of latent/hidden
variables that arise in neural networks and can thus model numerous AI
applications. Our results indicate the possibility of deep novel algorithmic
ideas emerging at the intersection of game theory, non-convex optimization and
ML and offers exciting directions for future work.

## Acknowledgments

This research was supported in part by the National Research Foundation,
Singapore and DSO National Laboratories under its AI Singapore Program (AISG
Award No: AISG2-RP-2020-016), grant PIESGP-AI-2020-01, AME Programmatic Fund
(Grant No.A20H6b0151) from A*STAR and Provost’s Chair Professorship grant
RGEPPV2101. PM is also a member of the Archimedes Unit, Athena RC, Department
of Mathematics, University of Athens, and is grateful for financial support by
the French National Research Agency (ANR) in the framework of the
“Investissements d’avenir” program (ANR-15-IDEX-02), the LabEx PERSYVAL
(ANR-11-LABX-0025-01), MIAI@Grenoble Alpes (ANR-19-P3IA-0003), and project MIS
5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the
European Union under the NextGenerationEU Program.

##  Appendix A Omitted proofs from Section 3

In this first appendix, we provide the technical proofs of our results for the
continuous-time dynamics (PHGF), namely Lemmas 1 and 1. For convenience, we
restate the relevant results as needed.

See 1

###### Proof.

Observe that if we expand the dynamical system of equations in (PHGF) with
respect to each individual coordinate, we have that for each player
$i\in\mathcal{N}$, for all profiles $\theta\in\Theta$, and for all coordinates
$\alpha\in\\{1,\ldots,m_{i}\\}$:

$\dot{\theta}_{i\alpha}=\sum_{\beta=1}^{m_{i}}\mathbf{P}_{i\alpha\beta}(\theta_{i})\frac{\partial\ell_{i}(\theta)}{\partial\theta_{i\beta}}.$
(A.1)

Now, since $\Gamma$ has a hidden monotone structure, and due to the
decomposition $\ell_{i}(\theta)=f_{i}(x)$, we can expand the above as

$\dot{\theta}_{i\alpha}=\sum_{\beta=1}^{m_{i}}\mathbf{P}_{i\alpha\beta}(\theta_{i})\sum_{r=1}^{d_{i}}\frac{\partial
f_{i}(x)}{\partial x_{ir}}\frac{\partial x_{ir}}{\partial\theta_{i\beta}}.$
(A.2)

Furthermore, if we expand the left-hand side (LHS) of (9) we also get

$\dot{E}(\theta)=\sum_{i=1}^{N}\sum_{\alpha=1}^{m_{i}}\frac{\partial
E(\theta)}{\partial\theta_{i\alpha}}\dot{\theta}_{i\alpha},$ (A.3)

where each of the summands of the above expression can also be expanded
further to

$\frac{\partial
E(\theta)}{\partial\theta_{i\alpha}}\dot{\theta}_{i\alpha}=-\sum_{l=1}^{d_{i}}(x_{il}-x_{il}^{\ast})\frac{\partial
x_{il}}{\partial\theta_{i\alpha}}\dot{\theta}_{i\alpha}.$ (A.4)

Putting everything together (9) follows by some trivial substitutions. ∎

See 1

###### Proof.

First, observe that for any player $i\in\mathcal{N}$, and
$\theta_{i}\in\Theta_{i}$, since the player’s representation map $\chi_{i}$ is
faithful, i.e., $\mathbf{J}_{i}(\theta_{i})$ is maximal rank, it holds:

$\begin{split}\mathbf{J}_{i}(\theta_{i})\mathbf{P}_{i}(\theta_{i})\mathbf{J}_{i}(\theta_{i})^{\intercal}&=\mathbf{J}_{i}(\theta_{i})\mathbf{J}_{i}(\theta_{i})^{+}\big{[}\mathbf{J}_{i}(\theta_{i})^{+}\big{]}^{\intercal}\mathbf{J}_{i}(\theta_{i})^{\intercal}\\\
&=\big{[}\mathbf{J}_{i}(\theta_{i})\mathbf{J}_{i}(\theta_{i})^{+}\big{]}^{\intercal}\\\
&=\mathbf{I}.\end{split}$ (A.5)

That is, $\sum_{\alpha=1}^{m_{i}}\sum_{\beta=1}^{m_{i}}\frac{\partial
x_{il}}{\partial\theta_{i\alpha}}\frac{\partial
x_{ir}}{\partial\theta{i\beta}}\mathbf{P}_{i\alpha\beta}(\theta_{i})=\delta_{lr}$
for all $l,r\in\\{1,\ldots,d_{i}\\}$, where $\delta_{lr}$ is the Kronecker
delta.

Now, by Lemma 1 we have that:

$\begin{split}\dot{E}(\theta)&=-\sum_{i=1}^{N}\sum_{l=1}^{d_{i}}\sum_{r=1}^{d_{i}}\delta_{lr}(x_{il}-x_{il}^{\ast})\frac{\partial
f_{i}(x)}{\partial x_{ir}}\\\
&=-\sum_{i=1}^{N}\sum_{l=1}^{d_{i}}(x_{il}-x_{il}^{\ast})\frac{\partial
f_{i}(x)}{\partial x_{il}}\\\
&=-\big{\langle}g(x),\,x-x^{\ast}\big{\rangle}.\end{split}$ (A.6)

which is negative, since $x^{\ast}$ is an optimizer of $f$, i.e., it satisfies
the (MVI) due to monotonicity of $g$. Additionally, since $g$ is strictly
monotone, $x^{\ast}$ is the unique optimizer of $f$, and, therefore, the above
condition holds with equality if and only if $x=x^{\ast}$. ∎

##  Appendix B Auxiliary results from Section 4

###  B.1. Convergence metrics and merit functions

In this appendix, we provide the technical scaffolding required for the
analysis of(PHGD), namely Lemmas 2, 3 and 4 in Section 3.2. As before, we
restate the relevant results as needed.

See 2

###### Proof of Lemma 2.

Let $\hat{x}\in\mathcal{X}$ be a solution of (SVI)/(MVI) so $\langle
g(\hat{x}),\,x-\hat{x}\rangle\geq 0$ for all $x\in\mathcal{X}$. Then, by the
monotonicity of $g$, we get:

$\displaystyle\langle g(x),\,\hat{x}-x\rangle$ $\displaystyle\leq\langle
g(x)-g(\hat{x}),\,\hat{x}-x\rangle+\langle g(\hat{x}),\,\hat{x}-x\rangle$
$\displaystyle=-\langle g(\hat{x})-g(x),\,\hat{x}-x\rangle-\langle
g(\hat{x}),\,x-\hat{x}\rangle\leq 0,$ (B.1)

so $\operatorname{Gap}_{\mathcal{C}}(\hat{x})\leq 0$. On the other hand, if
$\hat{x}\in\mathcal{C}$, we also get $\operatorname{Gap}(\hat{x})\geq\langle
g(\hat{x}),\,\hat{x}-\hat{x}\rangle=0$, so we conclude that
$\operatorname{Gap}_{\mathcal{C}}(\hat{x})=0$.

For the converse statement, assume that
$\operatorname{Gap}_{\mathcal{C}}(\hat{x})=0$ for some $\hat{x}\in\mathcal{C}$
and suppose that $\mathcal{C}$ contains a neighborhood of $\hat{x}$ in
$\mathcal{X}$. We then claim that $\hat{x}$ is a solution of (MVI) over
$\mathcal{C}$, i.e.,

$\langle g(x),\,x-\hat{x}\rangle\geq 0\quad\text{for all $x\in\mathcal{C}$}.$
(B.2)

To see this, assume to the contrary that there exists some
$x_{1}\in\mathcal{C}$ such that

$\langle g(x_{1}),\,x_{1}-\hat{x}\rangle<0$ (B.3)

so, in turn, we get

$0=\operatorname{Gap}_{\mathcal{C}}(\hat{x})\geq\langle
g(x_{1}),\,\hat{x}-x_{1}\rangle>0,$ (B.4)

a contradiction.

With this intermediate “local” result in hand, we are now in a position to
prove that $\hat{x}$ solves (SVI). Indeed, if we suppose to the contrary that
there exists some $z_{1}\in\mathcal{X}$ such that $\langle
g(\hat{x}),\,z_{1}-\hat{x}\rangle<0$, then, by the continuity of $g$, there
exists a neighborhood $\mathcal{U}^{\prime}$ of $\hat{x}$ in $\mathcal{X}$
such that

$\langle g(x),\,z_{1}-x\rangle<0\quad\text{for all
$x\in\mathcal{U}^{\prime}$}.$ (B.5)

Hence, assuming without loss of generality that
$\mathcal{U}^{\prime}\subset\mathcal{U}\subset\mathcal{C}$ (the latter
assumption due to the assumption that $\mathcal{C}$ contains a neighborhood of
$\hat{x}$), and taking $\lambda>0$ sufficiently small so that
$x=\hat{x}+\lambda(z_{1}-\hat{x})\in\mathcal{U}^{\prime}$, we get that
$\langle g(x),\,x-\hat{x}\rangle=\lambda\langle
g(x),\,z_{1}-\hat{x}\rangle<0$, in contradiction to (B.2). We thus conclude
that $\hat{x}$ is a solution of (SVI) – and hence, by monotonicity, also of
(MVI). ∎

For intuition, we discuss below some other merit functions that could be
considered as valid convergence metrics. In this regard, the first thing to
note is that the definition of $\operatorname{Gap}(\hat{\theta})$ effectively
goes through the game’s _latent space_ , so it is natural to ask whether a
similar merit function can be defined directly on the game’s _control space_.
To do so, it will be more convenient to start with a linearized variant of
$\operatorname{Gap}_{\mathcal{X}}$ defined over the cone of tangent directions
at $\hat{x}$, namely the so-called “tangent residual gap”

$\operatorname{TGap}_{\mathcal{X}}(\hat{x})\coloneqq-\min\nolimits_{z\in\operatorname{TC}_{\mathcal{X}}(\hat{x}),\lVert
z\rVert\leq 1}\langle g(\hat{x}),\,z\rangle$ (B.6)

i.e., the maximum “ascent” step $\langle-g(x),\,z\rangle$ over all admissible
displacement directions $z$ from $\hat{x}$.444In the above,
$\operatorname{TC}_{\mathcal{X}}(\hat{x})$ denotes the tangent cone to
$\mathcal{X}$ at $\hat{x}$, that is, the closure of the set of all rays
emanating from $\hat{x}$ and intersecting $\mathcal{X}$ in at least one other
point. Just like $\operatorname{Gap}_{\mathcal{C}}$, this linearized merit
function correctly identifies solutions of (SVI)/(MVI):

######  Lemma B.1.

For all $\hat{x}\in\mathcal{X}$, we have
$\operatorname{TGap}_{\mathcal{X}}(\hat{x})\geq 0$ with equality if and only
if $\hat{x}$ solves (SVI)/(MVI).

###### Proof.

Let $\hat{x}\in\mathcal{X}$ be some arbitrary profile of latent variables. By
definition, we have that
$\operatorname{TGap}_{\mathcal{X}}(\hat{x})=-\min\nolimits_{z\in\operatorname{TC}_{\mathcal{X}}(\hat{x}),\lVert
z\rVert\leq 1}\langle g(\hat{x}),\,z\rangle$, where
$\operatorname{TC}_{\mathcal{X}}(\hat{x})$ is the tangent cone to
$\mathcal{X}$ at $\hat{x}$. Observe that since
$\operatorname{TC}_{\mathcal{X}}(\hat{x})$ is a cone,
$0\in\operatorname{TC}_{\mathcal{X}}(\hat{x})$, so
$\operatorname{TGap}_{\mathcal{X}}(\hat{x})\geq-\langle
g(\hat{x}),\,0\rangle=0$. Now assume that
$\operatorname{TGap}_{\mathcal{X}}(\hat{x})=0$. Then, the following are
equivalent:

$\begin{split}\operatorname{TGap}_{\mathcal{X}}(\hat{x})=0&\iff-\min\nolimits_{z\in\operatorname{TC}_{\mathcal{X}}(\hat{x}),\lVert
z\rVert\leq 1}\langle g(\hat{x}),\,z\rangle=0\\\ &\iff\langle
g(\hat{x}),\,z\rangle\geq 0\quad\text{for all
$z\in\operatorname{TC}_{\mathcal{X}}(\hat{x})$, $\lVert z\rVert\leq 1$}\\\
&\iff\langle g(\hat{x}),\,z\rangle\geq 0\quad\text{for all
$z\in\operatorname{TC}_{\mathcal{X}}(\hat{x})$},\end{split}$ (B.7)

where the last equivalence follows because
$\operatorname{TC}_{\mathcal{X}}(\hat{x})$ is a cone. Rearranging the terms,
we may equivalently write $\langle-g(\hat{x}),\,z\rangle\leq 0$ for all
$z\in\operatorname{TC}_{\mathcal{X}}(\hat{x})$. Notice that, by the definition
of the tangent cone, the latter is equivalent to
$\langle-g(\hat{x}),\,\hat{x}-z\rangle\leq 0$ for all $z\in\mathcal{X}$.
Therefore, $\operatorname{TGap}_{\mathcal{X}}(\hat{x})=0$ if and only if
$\hat{x}$ satisfies (SVI). ∎

Now, if $\theta^{\ast}$ is a Nash equilibrium of the base game, the latent
variable configuration $x^{\ast}=\chi(\theta^{\ast})$ solves (SVI)/(MVI), so
$\operatorname{TGap}_{\mathcal{X}}$ is a valid equilibrium convergence metric
for $\Gamma$. However, since $\operatorname{TGap}_{\mathcal{X}}$ is still
defined on the game’s latent space, it does not give a straightforward way of
definining the quality of a candidate solution directly on the game’s control
space. To that end, one could consider the gap function

$\operatorname{TGap}_{\Theta}(\hat{\theta})\coloneqq-\min\nolimits_{\eta\in\mathbb{R}^{m},\lVert\eta\rVert\leq
1}\langle v(\hat{\theta}),\,\eta\rangle=\lVert v(\hat{\theta})\rVert_{\ast}$
(B.8)

where $v(\theta)\coloneqq(\nabla_{i}\ell_{i}(\theta))_{i\in\mathcal{N}}$
collects the players’ loss gradients relative to their control variables, and
$\lVert\cdot\rVert_{\ast}$ denotes its dual norm (so
$\operatorname{TGap}_{\Theta}(\hat{\theta})$ is evaluated _directly_ on the
game’s control space). Of course, as control variables are mapped to latent
variables, $\chi$ introduces a certaint distortion (due to nonlinearities).
This distortion can be quantified by the following lemma (see also Fig. 6
above):

$\mathbf{J}_{i}(\theta)$$\sigma_{\min}(\theta)$$\sigma_{\max}(\theta)$$\lVert
z\rVert\leq\sigma_{\min}$$\lVert
z\rVert\leq\sigma_{\max}$$\lVert\eta\rVert\leq 1$

Figure 6. The distortion of a ball by $\mathbf{J}(\theta)$.

######  Lemma B.2.

Let $\hat{x}=\chi(\hat{\theta})$ for some $\hat{\theta}\in\Theta$. We then
have

$\sigma_{\min}\operatorname{TGap}_{\mathcal{X}}(\hat{x})\leq\operatorname{TGap}_{\Theta}(\hat{\theta})\leq\sigma_{\max}\operatorname{TGap}_{\mathcal{X}}(\hat{x})$
(B.9)

In particular, $\operatorname{TGap}_{\Theta}(\hat{\theta})\geq 0$ for all
$\hat{\theta}\in\Theta$, with equality if and only if $\hat{\theta}$ is a Nash
equilibrium of $\Gamma$.

###### Proof.

To begin with, let us define the balls
$\mathbb{B}_{\Theta}\equiv\\{\eta\in\mathbb{R}^{m}:\lVert\eta\rVert\leq 1\\}$,
and $\mathbb{B}_{\mathcal{X}}\equiv\\{z\in\mathbb{R}^{d}:\lVert z\rVert\leq
1\\}$. Now, let $\hat{\theta}\in\Theta$ be some arbitrary profile of control
variables. By Assumption 2, we have that the singular values of the Jacobian
$\mathbf{J}(\hat{\theta})$ of the representation map $\chi$ are bounded from
above and below by $\sigma_{\max}<\infty$ and $\sigma_{\min}>0$ respectively.
That is,
$\sigma_{\min}\lVert\eta\rVert\leq\lVert\mathbf{J}(\hat{\theta})\eta\rVert\leq\sigma_{\max}\lVert\eta\rVert$
for all $\eta\in\mathbb{R}^{m}$, which implies that
$\sigma_{\min}\mathbb{B}_{\mathcal{X}}\subseteq\mathbf{J}(\hat{\theta})\mathbb{B}_{\Theta}\subseteq\sigma_{\max}\mathbb{B}_{\mathcal{X}}$.
By definition, we also have that,
$v(\hat{\theta})=\mathbf{J}(\hat{\theta})^{\intercal}g\big{(}\chi(\hat{\theta})\big{)}=\mathbf{J}(\hat{\theta})^{\intercal}g(\hat{x})$,
and, hence

$\operatorname{TGap}_{\Theta}(\hat{\theta})=-\min_{\eta\in\mathbb{B}_{\Theta}}\langle
v(\hat{\theta}),\,\eta\rangle=-\min_{z\in\mathbf{J}(\hat{\theta})\mathbb{B}_{\Theta}}\langle
g(\hat{x}),\,z\rangle$ (B.10)

Now, recall that the set of Nash equilibria $\Theta^{\ast}\subset\Theta$ is
non-empty. In particular, since the $\Theta\equiv\mathbb{R}^{m}$ is an open
set, the solution set lies in an open set, which, in conjunction with the fact
that the representation maps are faithful representations of $\Theta$ to
$\mathcal{X}$, also implies that $\chi(\Theta^{\ast})$ lies in the interior of
$\mathcal{X}$. Finally, since $\chi$ is smooth, and in conjunction with the
previous observations, it follows that
$\operatorname{TGap}_{\Theta}(\hat{\theta})=\|v(\hat{\theta})\|$ and
$\operatorname{TGap}_{\mathcal{X}}(\hat{x})=\|g(\hat{x})\|$, hence it is easy
to see from the above discussion that

$\sigma_{\min}\operatorname{TGap}_{\mathcal{X}}(\chi(\hat{\theta}))\leq\operatorname{TGap}_{\Theta}(\hat{\theta})\leq\sigma_{\max}\operatorname{TGap}_{\mathcal{X}}(\chi(\hat{\theta}))$
(B.11)

and our proof is complete. ∎

In view of the above discussion, the reader may wonder why not use the tangent
gap $\operatorname{TGap}_{\Theta}$ directly as a performance metric. The
reason for this is that, if the solutions $x^{\ast}$ of (SVI)/(MVI) do not
belong to the image of $\chi$, the dual norm of $v(\hat{\theta})$ may be too
stringent as a performance metric as it does not vanish near an equilibrium
(e.g., think of the operator $g(x)=x$ for $x$ between $0$ and $1$). In this
case, equilibria can be approximated to arbitrary accurarcy but never
attained, so the latent gap functions $\operatorname{Gap}$ and
$\operatorname{Err}$ are more appropriate as performance measures.

###  B.2. Convergence analysis and template inequalities

See 3

###### Proof.

Let $i\in\mathcal{N}$ be some arbitrary player, let $\theta\in\Theta$ be some
arbitrary profile of control variables, and let $\eta\in\mathbb{R}^{d_{i}}$ be
some arbitrary vector. Then for each coordinate
$\alpha\in\\{1,\ldots,m_{i}\\}$, and latent profile $\hat{x}\in\mathcal{X}$,
we have that

$\frac{\partial
E(\theta;\hat{x})}{\partial\theta_{i\alpha}}=\sum_{j=1}^{d_{i}}(x_{ij}-\hat{x}_{ij})\frac{\partial
x_{ij}}{\partial\theta_{i\alpha}}.$ (B.12)

That is
$\operatorname{\nabla}_{\theta_{i}}E(y;\hat{x})=\mathbf{J}_{i}(\theta_{i})^{\intercal}(x_{i}-\hat{x}_{i})$.
Now, we can multiply both sides of the above expression with
$\mathbf{P}_{i}(\theta_{i})$ to get

$\begin{split}\mathbf{P}_{i}(\theta_{i})\operatorname{\nabla}_{\theta_{i}}E(\theta;\hat{x})&=\mathbf{P}_{i}(\theta_{i})\mathbf{J}_{i}(\theta_{i})^{\intercal}(x_{i}-\hat{x}_{i})\\\
&=\mathbf{J}_{i}(\theta_{i})^{+}\big{(}\mathbf{J}_{i}(\theta_{i})^{+}\big{)}^{\intercal}\mathbf{J}_{i}(\theta_{i})^{\intercal}(x_{i}-\hat{x}_{i})\\\
&=\mathbf{J}_{i}(\theta_{i})^{+}(x_{i}-\hat{x}_{i}),\end{split}$ (B.13)

where in the last equality we used the fact that the $i$-th player’s
representation map $\chi_{i}$ is a faithful representation, i.e.,
$\mathbf{J}_{i}(\theta_{i})$ is maximal rank. Finally, by expanding the LHS of
(21), and applying the above simplification the result follows. ∎

See 4

###### Proof.

For each $t=1,2,\dotsc$ we expand $x_{t+1}$ using its second-order Taylor
approximation at $\theta_{t}$; i.e., for each player $i=1,\dots,N$ and each
coordinate $l=1,\dots,d_{i}$:

$\begin{split}x_{il,t+1}&=\chi_{il}(\theta_{t+1})\\\
&=\chi_{il}(\theta_{i,t})+\gamma_{t}\langle\operatorname{\nabla}\chi_{il}(\theta_{i,t}),\theta_{i,t+1}-\theta_{i,t}\rangle\\\
&\qquad+\gamma_{t}^{2}(\theta_{i,t+1}-\theta_{i,t})^{\intercal}H_{il}(\tilde{\theta}_{i,t})(\theta_{i,t+1}-\theta_{i,t}),\end{split}$
(B.14)

where $H_{il}(\tilde{\theta}_{i,t})$ is the Hessian of the latent map
$\chi_{il}$ at some convex combination $\tilde{\theta}_{i,t}$ of
$\theta_{i,t}$ and $\theta_{i,t+1}$. Then, further expanding $\theta_{t+1}$,
we also get

$\begin{split}x_{il,t+1}&=x_{il,t}-\gamma_{t}\langle\operatorname{\nabla}\chi_{il}(\theta_{i,t}),\mathbf{P}_{i,t}V_{i,t}\rangle+\gamma_{t}^{2}(\mathbf{P}_{i,t}V_{i,t})^{\intercal}H_{il}(\tilde{\theta}_{i,t})(\mathbf{P}_{i,t}V_{i,t}).\end{split}$
(B.15)

Plugging the above expansion to $E(\theta_{t+1};\hat{x})$ for arbitrary state
$\hat{x}$ we get

$\begin{split}E_{t+1}&=E(\theta_{t+1};\hat{x})\\\
&=\frac{1}{2}\sum_{i=1}^{N}\sum_{l=1}^{d_{i}}(x_{t+1}-\hat{x})^{2}\\\
&=\frac{1}{2}\sum_{i=1}^{N}\sum_{l=1}^{d_{i}}[x_{il,t}-\hat{x}_{il}-\gamma_{t}\langle\operatorname{\nabla}\chi_{il}(\theta_{i,t}),\mathbf{P}_{i,t}V_{i,t}\rangle\\\
&\qquad+\gamma_{t}^{2}(\mathbf{P}_{i,t}V_{i,t})^{\intercal}H_{il}(\tilde{\theta}_{i,t})(\mathbf{P}_{i,t}V_{i,t})]^{2}\\\
&=E_{t}-\gamma_{t}\sum_{i=1}^{N}\sum_{l=1}^{d_{i}}\langle\operatorname{\nabla}\chi_{il}(\theta_{i,t}),\mathbf{P}_{i,t}V_{i,t}\rangle(x_{il,t}-\hat{x}_{il})+\gamma_{t}^{2}\psi_{t}\\\
&=E_{t}-\gamma_{t}(\mathbf{J}_{t}\mathbf{P}_{t}V_{t})^{\intercal}(x_{t}-\hat{x})+\gamma_{t}^{2}\psi_{t},\end{split}$
(B.16)

where the second-order term $\psi_{t}$ is given by the formula

$\begin{split}\psi_{t}&=\sum_{i=1}^{N}\sum_{l=1}^{d_{i}}\langle\operatorname{\nabla}\chi_{il}(\theta_{i,t}),\mathbf{P}_{i,t}V_{i,t}\rangle^{2}\\\
&\qquad+\sum_{i=1}^{N}\sum_{l=1}^{d_{i}}(\mathbf{P}_{i,t}V_{i,t})^{\intercal}H_{il}(\tilde{\theta}_{i,t})(\mathbf{P}_{i,t}V_{i,t})(x_{il,t}-\hat{x}_{il})\\\
&\qquad-\gamma_{t}\sum_{i=1}^{N}\sum_{l=1}^{d_{i}}\langle\operatorname{\nabla}\chi_{il}(\theta_{i,t}),\mathbf{P}_{i,t}V_{i,t}\rangle(\mathbf{P}_{i,t}V_{i,t})^{\intercal}H_{il}(\tilde{\theta}_{i,t})(\mathbf{P}_{i,t}V_{i,t})\\\
&\qquad+\gamma_{t}^{2}\sum_{i=1}^{N}\sum_{l=1}^{d_{i}}[(\mathbf{P}_{i,t}V_{i,t})^{\intercal}H_{il}(\tilde{\theta}_{i,t})(\mathbf{P}_{i,t}V_{i,t})]^{2}.\end{split}$
(B.17)

For the second-order term, observe that by 2, we have that
$[\mathbf{J}_{t}^{\intercal}\mathbf{J}_{t}]^{+}\preceq\frac{1}{\sigma_{\min}^{2}}\mathbf{I}$.
Using that fact, it follows that

$\begin{split}\sum_{i=1}^{N}\sum_{l=1}^{d_{i}}\langle\operatorname{\nabla}\chi_{il}(\theta_{i,t}),\mathbf{P}_{i,t}V_{i,t}\rangle^{2}&=(\mathbf{J}_{t}\mathbf{P}_{t}V_{t})^{\intercal}\mathbf{J}_{t}\mathbf{P}_{t}V_{t}\\\
&=V_{t}^{\intercal}[\mathbf{J}_{t}^{\intercal}\mathbf{J}_{t}]^{+}\mathbf{J}_{t}^{\intercal}\mathbf{J}_{t}[\mathbf{J}_{t}^{\intercal}\mathbf{J}_{t}]^{+}V_{t}\\\
&=V_{t}^{\intercal}[\mathbf{J}_{t}^{\intercal}\mathbf{J}_{t}]^{+}V_{t}\\\
&\leq\frac{1}{\sigma_{\min}^{2}}\lVert V_{t}\rVert^{2},\end{split}$ (B.18)

Furthermore, since the representation maps $\chi_{i}$ are $\beta$-Lipschitz
smooth for some Lipschitz modulus $\beta$, we have that
$H_{i,l}(\bar{\theta}_{i,t})\preceq\beta\mathbf{I}$ for each player $i$ and
coordinate $l$. Consequently, we have that

$(\mathbf{P}_{i,t}V_{i,t})^{\intercal}H_{il}(\tilde{\theta}_{i,t})(\mathbf{P}_{i,t}V_{i,t})\leq\beta
V_{i,t}^{\intercal}\mathbf{P}_{i,t}^{2}V_{i,t}\\\
\leq\frac{\beta}{\sigma_{\min}^{4}}\lVert
V_{i,t}\rVert^{2}\leq\frac{\beta}{\sigma_{\min}^{4}}\lVert V_{t}\rVert^{2}.$
(B.19)

Let $D=\operatorname{diam}(\chi)$, then, by applying the Cauchy-Schwarz
inequality, we also get that

$\begin{split}\psi_{t}\leq\frac{1}{\sigma_{\min}^{2}}\lVert
V_{t}\rVert^{2}+\frac{dD\sqrt{\beta}}{\sigma_{\min}^{2}}\lVert
V_{t}\rVert+\gamma\frac{\sqrt{\beta}}{\sigma_{\min}^{3}}\lVert
V_{t}\rVert^{2}+\gamma^{2}\frac{d\beta^{2}}{\sigma_{\min}^{8}}\lVert
V_{t}\rVert^{2},\end{split}$ (B.20)

where $\gamma=\sup_{t=1,2,\dotsc}\gamma_{t}$, and $d=\sum_{i=1}^{N}d_{i}$.

Finally, let us consider the first-order term of (B.16). Let
$v_{t}=(\nabla_{i}\ell_{i}(\theta_{t}))_{i\in\mathcal{N}}$, and
$g_{t}=g(x_{t})$. Then, by definition, we also have that
$v_{t}=\mathbf{J}_{t}^{\intercal}g_{t}$. Moreover, recall that, by
construction,
$\mathbf{J}_{t}\mathbf{P}_{t}\mathbf{J}_{t}^{\intercal}=\mathbf{I}$.
Consequently, we can write

$\begin{split}(\mathbf{J}_{t}\mathbf{P}_{t}V_{t})^{\intercal}(x_{t}-\hat{x})&=(\mathbf{J}_{t}\mathbf{P}_{t}v_{t})^{\intercal}(x_{t}-\hat{x})+[\mathbf{J}_{t}\mathbf{P}_{t}(V_{t}-v_{t})]^{\intercal}(x_{t}-\hat{x})\\\
&=(\mathbf{J}_{t}\mathbf{P}_{t}\mathbf{J}_{t}^{\intercal}g_{t})^{\intercal}(x_{t}-\hat{x})+[\mathbf{J}_{t}\mathbf{P}_{t}(V_{t}-\mathbf{J}_{t}^{\intercal}g_{t})]^{\intercal}(x_{t}-\hat{x})\\\
&=g_{t}^{\intercal}(x_{t}-\hat{x})+(\mathbf{J}_{t}\mathbf{P}_{t}V_{t}-g_{t})^{\intercal}(x_{t}-\hat{x}),\end{split}$
(B.21)

which concludes our proof. ∎

##  Appendix C Proofs of Theorems 1, 2 and 3

We are now in a position to prove Theorems 1, 2 and 3 regarding the
convergence properties of (PHGD). We proceed sequentially, restating the
relevant results as needed.

See 1

###### Proof.

Let $\theta_{1}\in\Theta$ be some arbitrary initialization of the algorithm,
and let $\tilde{x}\in\mathcal{X}$ be some arbitrary profile of latent
variables. Next, by Lemma 4, we have that for all $t\geq 1$:

$\displaystyle E_{t+1}$ $\displaystyle\leq E_{t}-\gamma_{t}\langle
g(x_{t}),\,x_{t}-\hat{x}\rangle+\gamma_{t}\phi_{t}+\gamma_{t}^{2}\psi_{t}$
(C.1) $\displaystyle\phi_{t}$
$\displaystyle=(\mathbf{J}(\theta_{t})\mathbf{P}(\theta_{t})V_{t}-g(x_{t}))^{\intercal}(x_{t}-\hat{x})$
$\displaystyle\psi_{t}$ $\displaystyle=\kappa\lVert
V_{t}\rVert^{2},\quad\text{for some $\kappa>0$}.$

Rearranging the terms, the above is equivalent to

$\gamma_{t}\big{\langle}g(x_{t}),\,x_{t}-\tilde{x}\big{\rangle}\leq
E_{t}-E_{t+1}+\gamma_{t}\phi_{t}+\gamma_{t}^{2}\psi_{t}.$ (C.2)

Furthermore, by the monotonicity of $g$, we also have that
$\big{\langle}g(x_{t})-g(\tilde{x}),\,x_{t}-\tilde{x}\big{\rangle}\geq 0$, and
by combining the two, we get that for all $t\geq 1$:

$\gamma_{t}\big{\langle}g(\tilde{x}),\,x_{t}-\tilde{x}\big{\rangle}\leq\gamma_{t}\big{\langle}g(x_{t}),\,x_{t}-\tilde{x}\big{\rangle}\leq
E_{t}-E_{t+1}+\gamma_{t}\phi_{t}+\gamma_{t}^{2}\psi_{t}.$ (C.3)

Summing up the above terms in both sides of the inequality, we also get that

$\begin{split}\sum_{s=1}^{t}\gamma_{s}\big{\langle}g(\tilde{x}),\,x_{s}-\tilde{x}\big{\rangle}&\leq\sum_{s=1}^{t}\big{[}E_{s}-E_{s+1}+\gamma_{s}\phi_{s}+\gamma_{s}^{2}\psi_{s}\big{]}\\\
&=E_{1}-E_{t+1}+\sum_{s=1}^{t}\gamma_{s}\phi_{s}+\sum_{s=1}^{t}\gamma_{s}^{2}\psi_{s}\\\
&\leq
E_{1}+\sum_{s=1}^{t}\gamma_{s}\phi_{s}+\sum_{s=1}^{t}\gamma_{s}^{2}\psi_{s}.\end{split}$
(C.4)

Dividing all terms by $\tilde{\gamma}_{t}\coloneqq\sum_{s=1}^{t}\gamma_{s}$,
also yields

$\begin{split}\big{\langle}g(\tilde{x}),\,\bar{x}_{t}-\tilde{x}\big{\rangle}&=\Big{\langle}g(\tilde{x}),\,\sum_{s=1}^{t}\frac{\gamma_{s}missing}{\tilde{\gamma}_{t}missing}x_{s}-\tilde{x}\Big{\rangle}\\\
&=\sum_{s=1}^{t}\frac{\gamma_{s}missing}{\tilde{\gamma}_{t}missing}\big{\langle}g(\tilde{x}),\,x_{s}-\tilde{x}\big{\rangle}\\\
&\leq\frac{E_{1}missing}{\tilde{\gamma}_{t}missing}+\frac{\sum_{s=1}^{t}\gamma_{s}\phi_{s}missing}{\tilde{\gamma}_{t}missing}+\frac{\sum_{s=1}^{t}\gamma_{s}^{2}\psi_{s}missing}{\tilde{\gamma}_{t}missing},\end{split}$
(C.5)

where
$\bar{x}_{t}\coloneqq\sum_{s=1}^{t}\frac{\gamma_{s}missing}{\tilde{\gamma}_{t}missing}x_{s}$
is the time-average.

Next, let us define the following auxiliary process that will assist us in
further bounding the above expression:

$\displaystyle y_{1}$ $\displaystyle=x_{1}$ (C.6) $\displaystyle y_{t+1}$
$\displaystyle=\operatorname*{arg\,min}_{x\in\mathcal{X}}\lVert
y_{t}-\gamma_{t}\eta_{t}-x\rVert\quad\text{for all $t\geq 2$},$

where
$\eta_{t}\coloneqq\mathbf{J}(\theta_{t})\mathbf{P}(\theta_{t})V_{t}-g(x_{t})$
for all $i\in\mathcal{N}$. Observe that

$\gamma_{t}\phi_{t}=\gamma_{t}\langle\eta_{t},\,x_{t}-\tilde{x}\rangle=\gamma_{t}\langle\eta_{t},\,y_{t}-\tilde{x}\rangle+\gamma_{t}\langle\eta_{t},\,x_{t}-y_{t}\rangle\quad\text{for
all $t\geq 1$}.$ (C.7)

Let us, first, focus on the former of the two terms. Notice that for all
$t\geq 1$, we can write

$\gamma_{t}\langle\eta_{t},\,y_{t}-\tilde{x}\rangle=\gamma_{t}\langle\eta_{t},\,y_{t+1}-\tilde{x}\rangle+\gamma_{t}\langle\eta_{t},\,y_{t}-y_{t+1}\rangle.$
(C.8)

Furthermore, by the optimality of $y_{t+1}$, $t\geq 2$, we have also have that

$\langle y_{t+1}-y_{t}+\gamma_{t}\eta_{t},\,y_{t+1}-\tilde{x}\rangle\leq 0.$
(C.9)

That is, $\gamma_{t}\langle\eta_{t},\,y_{t+1}-\tilde{x}\rangle\leq\langle
y_{t}-y_{t+1},\,y_{t+1}-\tilde{x}\rangle$.

Let us also recall a couple of useful quadratic identities, namely, we have
that $\lVert y_{t}-\tilde{x}\rVert^{2}=\lVert
y_{t}-y_{t+1}+y_{t+1}-\tilde{x}\rVert^{2}=\lVert
y_{t}-y_{t+1}\rVert^{2}+2\langle
y_{t}-y_{t+1},\,y_{t+1}-\tilde{x}\rangle+\lVert y_{t+1}-\tilde{x}\rVert^{2}$,
and
$\lVert\gamma_{t}\eta_{t}-(y_{t}-y_{t+1})\rVert^{2}=\gamma_{t}^{2}\lVert\eta_{t}\rVert^{2}-2\gamma_{t}\langle\eta_{t},\,y_{t}-y_{t+1}\rangle+\lVert
y_{t}-y_{t+1}\rVert^{2}$. Then, in conjunction with the above, we get that for
all $t\geq 1$:

$\begin{split}\gamma_{t}\langle\eta_{t},\,y_{t}-\tilde{x}\rangle&=\gamma_{t}\langle\eta_{t},\,y_{t+1}-\tilde{x}\rangle+\gamma_{t}\langle\eta_{t},\,y_{t}-y_{t+1}\rangle\\\
&\leq\langle
y_{t}-y_{t+1},\,y_{t+1}-\tilde{x}\rangle+\gamma_{t}\langle\eta_{t},\,y_{t}-y_{t+1}\rangle\\\
&=\frac{1}{2}\lVert y_{t}-\tilde{x}\rVert^{2}-\frac{1}{2}\lVert
y_{t+1}-\tilde{x}\rVert^{2}-\frac{1}{2}\lVert\gamma_{t}\eta_{t}-(y_{t}-y_{t+1})\rVert^{2}+\frac{\gamma_{t}^{2}}{2}\lVert\eta_{t}\rVert^{2}\\\
&\leq\frac{1}{2}\lVert y_{t}-\tilde{x}\rVert^{2}-\frac{1}{2}\lVert
y_{t+1}-\tilde{x}\rVert^{2}+\frac{\gamma_{t}^{2}}{2}\lVert\eta_{t}\rVert^{2}\end{split}$
(C.10)

Finally, summing both sides of the above inequalities, we also get that

$\begin{split}\sum_{s=1}^{t}\gamma_{s}\langle\eta_{s},\,y_{s}-\tilde{x}\rangle&\leq\frac{1}{2}\sum_{s=1}^{t}\lVert
y_{s}-\tilde{x}\rVert^{2}-\frac{1}{2}\sum_{s=1}^{t}\lVert
y_{s+1}-\tilde{x}\rVert^{2}+\frac{1}{2}\sum_{s=1}^{t}\gamma_{s}^{2}\lVert\eta_{s}\rVert^{2}\\\
&=\frac{1}{2}\lVert y_{1}-\tilde{x}\rVert^{2}-\frac{1}{2}\lVert
y_{t+1}-\tilde{x}\rVert^{2}+\frac{1}{2}\sum_{s=1}^{t}\gamma_{s}^{2}\lVert\eta_{s}\rVert^{2}\\\
&\leq\frac{1}{2}\lVert
y_{1}-\tilde{x}\rVert^{2}+\frac{1}{2}\sum_{s=1}^{t}\gamma_{s}^{2}\lVert\eta_{s}\rVert^{2}\\\
&=\frac{1}{2}\lVert
x_{1}-\tilde{x}\rVert^{2}+\frac{1}{2}\sum_{s=1}^{t}\gamma_{s}^{2}\lVert\eta_{s}\rVert^{2}\\\
&=E_{1}+\frac{1}{2}\sum_{s=1}^{t}\gamma_{s}^{2}\lVert\eta_{s}\rVert^{2}\end{split}$
(C.11)

With the above established, let us reconsider the quantity
$\big{\langle}g(\tilde{x}),\,\bar{x}_{t}-\tilde{x}\big{\rangle}$.
Specifically, due to the above derivations, we have that for all $t\geq 1$:

$\begin{split}\big{\langle}g(\tilde{x}),\,\bar{x}_{t}-\tilde{x}\big{\rangle}&\leq\frac{E_{1}missing}{\tilde{\gamma}_{t}missing}+\frac{\sum_{s=1}^{t}\gamma_{s}\phi_{s}missing}{\tilde{\gamma}_{t}missing}+\frac{\sum_{s=1}^{t}\gamma_{s}^{2}\psi_{s}missing}{\tilde{\gamma}_{t}missing}\\\
&=\frac{E_{1}missing}{\tilde{\gamma}_{t}missing}+\frac{1}{\tilde{\gamma}_{t}missing}\sum_{s=1}^{t}\gamma_{t}\langle\eta_{t},\,y_{t}-\tilde{x}\rangle+\frac{1}{\tilde{\gamma}_{t}missing}\sum_{s=1}^{t}\gamma_{t}\langle\eta_{t},\,x_{t}-y_{t}\rangle+\frac{\sum_{s=1}^{t}\gamma_{s}^{2}\psi_{s}missing}{\tilde{\gamma}_{t}missing}\\\
&\leq\frac{3E_{1}missing}{2\tilde{\gamma}_{t}missing}+\frac{1}{2\tilde{\gamma}_{t}missing}\sum_{s=1}^{t}\gamma_{s}^{2}\lVert\eta_{s}\rVert^{2}+\frac{1}{\tilde{\gamma}_{t}missing}\sum_{s=1}^{t}\gamma_{t}\langle\eta_{t},\,x_{t}-y_{t}\rangle+\frac{\kappa}{\tilde{\gamma}_{t}missing}\sum_{s=1}^{t}\gamma_{s}^{2}\lVert
V_{s}\rVert^{2}.\end{split}$

Considering the mean of supremum over $\tilde{x}\in\mathcal{X}$ of the LHS, we
end up with

$\begin{split}\operatorname{\mathbb{E}}\bigg{[}\sup_{\tilde{x}\in\mathcal{X}}\big{\langle}g(\tilde{x}),\,\bar{x}_{t}-\tilde{x}\big{\rangle}\bigg{]}&\leq\frac{3E_{1}missing}{2\tilde{\gamma}_{t}missing}+\frac{1}{2\tilde{\gamma}_{t}missing}\sum_{s=1}^{t}\gamma_{s}^{2}\operatorname{\mathbb{E}}[\lVert\eta_{s}\rVert^{2}]+\frac{\kappa}{\tilde{\gamma}_{t}missing}\sum_{s=1}^{t}\gamma_{s}^{2}\operatorname{\mathbb{E}}[\lVert
V_{s}\rVert^{2}]\\\
&\leq\frac{3E_{1}missing}{2\tilde{\gamma}_{t}missing}+\frac{M^{2}}{\tilde{\gamma}_{t}missing}\sum_{s=1}^{t}\gamma_{s}^{2}+\frac{\kappa
M^{2}}{\tilde{\gamma}_{t}missing}\sum_{s=1}^{t}\gamma_{s}^{2}\\\
&=\frac{3E_{1}missing}{2\tilde{\gamma}_{t}missing}+(1+\kappa)\frac{M^{2}}{\tilde{\gamma}_{t}missing}\sum_{s=1}^{t}\gamma_{s}^{2}\\\
&=\operatorname{\mathcal{O}}\Big{(}\sum_{s=1}^{t}\gamma_{s}^{2}/\tilde{\gamma}_{t}\Big{)}\\\
&=\operatorname{\mathcal{O}}(\log t/\sqrt{t}),\end{split}$ (C.12)

where the last inequality is direct consequence of the bounded second moment
of the stochastic gradient in Assumption 1 ∎

See 2

###### Proof.

Let $\theta_{1}\in\Theta$ be some arbitrary initialization of the algorithm,
and let $\gamma\geq\frac{1}{2\mu}$ be arbitrary. Since the map $f$ is
$\mu$-strongly monotone, we have, by the definition of strong monotonicity,
that

$\big{\langle}g(x_{t}),\,x_{t}-x^{\ast}\big{\rangle}\geq\mu\lVert
x-x^{\ast}\rVert^{2}\quad\text{for all $x\in\mathcal{X}$}.$ (C.13)

Next, by Lemma 4, we have that for all $t\geq 1$:

$\displaystyle E_{t+1}$ $\displaystyle\leq E_{t}-\gamma_{t}\langle
g(x_{t}),\,x_{t}-\hat{x}\rangle+\gamma_{t}\phi_{t}+\gamma_{t}^{2}\psi_{t}$
(C.14) $\displaystyle\phi_{t}$
$\displaystyle=(\mathbf{J}(\theta_{t})\mathbf{P}(\theta_{t})V_{t}-g(x_{t}))^{\intercal}(x_{t}-\hat{x})$
$\displaystyle\psi_{t}$ $\displaystyle=\kappa\lVert
V_{t}\rVert^{2},\quad\text{for some $\kappa>0$}.$

That is

$\begin{split}E_{t+1}&\leq E_{t}-\mu\gamma_{t}\lVert
x_{t}-x^{\ast}\rVert_{2}^{2}+\gamma_{t}\phi_{t}+\gamma_{t}^{2}\psi_{t}\\\
&=E_{t}-2\mu\gamma_{t}E_{t}+\gamma_{t}\phi_{t}+\gamma_{t}^{2}\psi_{t}\\\
&=(1-2\mu\gamma_{t})E_{t}+\gamma_{t}\phi_{t}+\gamma_{t}^{2}\psi_{t}.\end{split}$
(C.15)

Let $\mathcal{H}_{t}=\\{\theta_{s}:s=1,\dotsc,t\\}$ be the history of play up
to iteration $t$. In expectation, it follows from the above that, for all
$t\geq 1$:

$\begin{split}\operatorname{\mathbb{E}}[E_{t+1}]&\leq(1-2\mu\gamma_{t})\operatorname{\mathbb{E}}[E_{t}]+\gamma_{t}\operatorname{\mathbb{E}}[\phi_{t}]+\gamma_{t}^{2}\operatorname{\mathbb{E}}[\psi_{t}]\\\
&=(1-2\mu\gamma_{t})\operatorname{\mathbb{E}}[E_{t}]+\gamma_{t}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}[\phi_{t}\nonscript\,|\nonscript\,\mathopen{}\mathcal{H}_{t}]]+\gamma_{t}^{2}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}[\psi_{t}\nonscript\,|\nonscript\,\mathopen{}\mathcal{H}_{t}]].\end{split}$
(C.16)

Note that $x_{t}$ is $\mathcal{H}_{t}$-measurable; hence, we have that

$\begin{split}\operatorname{\mathbb{E}}[\phi_{t}\nonscript\,|\nonscript\,\mathopen{}\mathcal{H}_{t}]&=\big{(}\mathbf{J}(\theta_{t})\mathbf{P}(\theta_{t})\operatorname{\mathbb{E}}[V_{t}\nonscript\,|\nonscript\,\mathopen{}\mathcal{H}_{t}]-g(x_{t})\big{)}^{\intercal}(x_{t}-\hat{x})\\\
&=\big{(}\mathbf{J}(\theta_{t})\mathbf{P}(\theta_{t})v(\theta_{t})-g(x_{t})\big{)}^{\intercal}(x_{t}-\hat{x})\\\
&=\big{(}\mathbf{J}(\theta_{t})\mathbf{P}(\theta_{t})\mathbf{J}({\theta_{t}})^{\intercal}{g(x_{t})}-g(x_{t})\big{)}^{\intercal}(x_{t}-\hat{x})\\\
&=\big{(}g(x_{t})-g(x_{t})\big{)}^{\intercal}(x_{t}-\hat{x})\\\
&=0.\end{split}$ (C.17)

Furthermore, since, by Assumption 1, we have that
$\operatorname{\mathbb{E}}[\lVert
V_{t}\rVert^{2}\nonscript\,|\nonscript\,\mathopen{}\mathcal{H}_{t}]\leq
M^{2}$, it also holds that

$\operatorname{\mathbb{E}}[\psi_{t}\nonscript\,|\nonscript\,\mathopen{}\mathcal{H}_{t}]=\kappa\operatorname{\mathbb{E}}[\lVert
V_{t}\rVert^{2}\nonscript\,|\nonscript\,\mathopen{}\mathcal{H}_{t}]\leq\kappa
M^{2}$ (C.18)

Next, by some simple substitutions, we have

$\begin{split}\operatorname{\mathbb{E}}[E_{t+1}]&\leq(1-2\mu\gamma_{t})\operatorname{\mathbb{E}}[E_{t}]+\kappa
M^{2}\gamma_{t}^{2}\\\
&=\Big{(}1-\frac{2\mu\gamma}{t}\Big{)}\operatorname{\mathbb{E}}[E_{t}]+\frac{\kappa
M^{2}\gamma^{2}}{t^{2}}\end{split}$ (C.19)

Finally, since $\gamma>\frac{1}{2\mu}$, we may apply Chung’s lemma [8] to get
that, for all $t\geq 1$:

$\operatorname{\mathbb{E}}[E_{t}]\leq\frac{\kappa
M^{2}\gamma^{2}}{2\mu\gamma-1}\cdot\frac{1}{t}+\operatorname{\mathcal{O}}\Big{(}\frac{1}{t^{2}}+\frac{1}{t^{2\mu\gamma}}\Big{)}.$
(C.20)

∎

See 3

###### Proof.

Due to the absence of randomness, and therefore the absence of noise, Lemma 4
may be simplified to

$E_{t+1}\leq
E_{t}-\gamma_{t}\big{\langle}g(x_{t}),\,x_{t}-x^{\ast}\big{\rangle}+\kappa\gamma_{t}^{2}\lVert
v_{t}\rVert^{2}$ (C.21)

for some constants $\kappa>0$, where
$v_{t}\coloneqq(\nabla_{i}\ell_{i}(\theta_{t}))_{i\in\mathcal{N}}$.

Let $\beta$ be the modulus of Lipschitz continuity of the gradients
$v_{t}=\mathbf{J}({\theta_{t}})^{\intercal}{g(x_{t})}$, and let
$\frac{\mu}{2}$ be the modulus of the strong monotonicity of $g$. Recall that,
by Assumption 2, we have that the singular values of the Jacobian
$\mathbf{J}(\theta)$ of the representation map $\chi$ are bounded from above
and below by $\sigma_{\max}<\infty$ and $\sigma_{\min}>0$ respectively.
Therefore, since $v_{t}$ is $\beta$-Lipschitz, it follows that

$\lVert
v_{t}-v^{\ast}\rVert^{2}\leq\beta^{2}\lVert\theta_{t}-\theta^{\ast}\rVert^{2}\leq\frac{\beta^{2}}{\sigma_{\min}^{2}}\lVert
x_{t}-x^{\ast}\rVert^{2}$ (C.22)

In conjunction to the above, we then also have

$\begin{split}E_{t+1}&\leq
E_{t}-\gamma_{t}\big{\langle}g(x_{t}),\,x_{t}-x^{\ast}\big{\rangle}+\kappa\gamma_{t}^{2}\lVert
v_{t}\rVert^{2}\\\
&=E_{t}-\gamma_{t}\big{\langle}g(x_{t}),\,x_{t}-x^{\ast}\big{\rangle}+\kappa\gamma_{t}^{2}\lVert
v_{t}-v^{\ast}\rVert^{2}\\\ &\leq E_{t}-\mu\gamma_{t}\frac{1}{2}\lVert
x_{t}-x^{\ast}\rVert^{2}+\frac{\kappa\gamma_{t}^{2}\beta^{2}}{\sigma_{\min}^{2}}\lVert
x_{t}-x^{\ast}\rVert^{2}\\\
&=E_{t}-\mu\gamma_{t}E_{t}+\frac{2\kappa\gamma_{t}^{2}\beta^{2}}{\sigma_{\min}^{2}}E_{t}\\\
&=E_{t}\Big{(}1-\mu\gamma_{t}+\frac{2\kappa\gamma_{t}^{2}\beta^{2}}{\sigma_{\min}^{2}}\Big{)}\end{split}$
(C.23)

Restricting $\gamma_{t}$ such that

$1-\mu\gamma_{t}+\frac{2\kappa\gamma_{t}^{2}\beta^{2}}{\sigma_{\min}^{2}}<1\iff\gamma_{t}<\frac{\sigma_{\min}^{2}\mu}{2\kappa\beta^{2}},$
(C.24)

we finally have that, for the choice of
$\gamma_{t}=\hat{\gamma}\coloneqq\dfrac{\sigma_{\min}^{2}\mu}{8\kappa\beta^{2}}$,
it holds

$E_{t}=\operatorname{\mathcal{O}}(\rho^{t})\quad\text{where
$\rho\coloneqq\Big{(}1-\dfrac{3\sigma_{\min}^{2}\mu}{32\kappa\beta^{2}}\Big{)}<1$}.$
(C.25)

Leveraging the equivalence of $\operatorname{Err}_{\Theta}(\theta_{t})$ and
$\operatorname{Err}_{\mathcal{X}}(x_{t})=E_{t}$ completes the proof. ∎

##  Appendix D Experiments

This section demonstrates the method’s applicability in a series of different
applccations. Along with revisiting the established examples of Section 5 in
greater detail, we also present how the PHGD method performs in a couple of
additional settings of interest. We begin with a high-level description of the
common test suite, and afterward, we move to the definitive details of each of
the presented applications.

In each example, we define a base game $\Gamma$ among two or more players
$\mathcal{N}\equiv\\{1,\ldots,N\\}$. Each player $i$ control a $m$-dimensional
vector of control variables $\theta_{i}\in\mathbb{R}^{m}$, which they feed in
an individual differentiable preconfigured MLP with two hidden layers that act
as the player’s representation map
$\chi_{i}:\mathbb{R}^{m}\to\mathcal{X}_{i}$. The dimensions of each layer of
the MLPs vary among the different examples. However, the MLP’s output
$x_{i}=\chi_{i}(\theta_{i})$ is guaranteed to be a representation of a
discrete probability distribution among the player’s actions in some normal-
form game, e.g., a Rock-Paper-Scissors game. The actual latent game
$\mathcal{G}$ of $\Gamma$, is given by the “hidden” loss functions
$f_{i}:\mathcal{X}\to\mathbb{R}$, $i\in\mathcal{N}$. Each loss function
$f_{i}$ is a regularized variation of the aforementioned normal-form game,
tuned by some $\frac{\mu}{2}$-strongly convex regularizer
$h_{\mu}(x)=\frac{\mu}{2}\cdot\big{(}\sum_{i\in\mathcal{N}}\lVert
x_{i}-x^{\ast}_{i}\rVert^{2}\big{)}$, where $x^{\ast}$ is the normal-form
game’s unique equilibrium point. The modulus $\mu$ is a hyper-parameter, which
we tune such that the vector field
$g(x)=\big{(}\operatorname{\nabla}_{x_{i}}f_{i}(x)\big{)}_{i\in\mathcal{N}}$
to be strongly monotone, and to avoid finite-precision numerical errors, which
can potentially arise during the computation of $x$.

(a) A trajectory of PHGD in a regularized game of Matching Pennies over the
sub-levels of the energy function in (5). The trajectory is depicted with
reference, both, the space of control variables (left), and the space of
latent variables (right). Notice that the trajectory crosses each sub-level
set of the energy function, at most, once, indicating that the function’s
value is monotone along the trajectory.

(b) A trajectory of GD in a regularized game of Matching Pennies over the sub-
levels of the energy function in (5). The trajectory is depicted with
reference, both, the space of control variables (left), and the space of
latent variables (right). Notice that the trajectory crosses each sub-level
set of the energy function multiple times indicating that the function’s value
is not monotone along the trajectory.

(c) The distance of $x$ to the latent game’s equilibrium point
$x^{\ast}=(\frac{1}{2},\frac{1}{2})$ along similar trajectories of PHGD and GD
in a regularized game of Matching Pennies. The distance is depicted in a
logarithmic scale in order to reveal the exponential rate of convergence of
PHGD.

#### A Hidden Game of Matching Pennies.

As a first example, we revisit the two-player hidden game of Matching Pennies
we introduced in Section 5. Here, each player’s $i$ control variables
$\theta_{i}$ are uni-dimensional, and are fed to each player’s individual MLP
given by the representation maps

$\chi_{i}(\theta_{i})=\operatorname{sigmoid}\big{(}\alpha^{(2)}_{i}\cdot
CeLU(\alpha^{(1)}_{i}\cdot\theta_{i})\big{)}\quad\text{for all $i=1,2$},$
(D.1)

where $\alpha^{(1)}_{i},\alpha^{(2)}_{i}\in[-1,1]$ are randomly chosen.
Although the definition of the activation functions
$\operatorname{sigmoid}:\mathbb{R}\to[0,1]$, and
$CeLU:\mathbb{R}\to(-1,\infty)$ are widely common, we give them below for
reference; that is:

$\displaystyle\operatorname{sigmoid}(x)$
$\displaystyle=\big{(}1+\exp(-x)\big{)}^{-1}$ (D.2a) $\displaystyle CeLU(x)$
$\displaystyle=\max\\{0,x\\}+\min\\{0,\exp(x)-1\\}.$ (D.2b)

In this, and the following examples, without any loss of the generality, we
deliberately set the bias of each of the MLP’s hidden layers to zero, in order
for the base game’s unique equilibrium to lie in $\theta^{\ast}=\vec{0}$, and
to simplify the notation. Each of the MLP’s output $x_{i}=\chi(\theta_{i})$ is
the $i$-th player’s probability of playing Heads in a regularized game of
Matching Pennies, given by the loss functions

$f_{1}(x)=-f_{2}(x)=-(2x_{1}-1)\cdot(2x_{2}-1)+h_{0.75}(x).$ (D.3)

The latent game’s unique equilibrium, in this case, is at
$x^{\ast}=\chi(\theta^{\ast})=(\frac{1}{2},\frac{1}{2})$.

In this particular example it is possible to visualize the trajectories of
PHGD and gradient descent with reference, both, the space of control variables
$\mathbb{R}^{2}$, and the space of latent variables $[0,1]^{2}$. In Fig. 8(a)
we depict the trajectory of PHGD, with step-size $0.01$, in the above game,
initialized at the arbitrary state $(1.25,2.25)$ with respect to, both, the
space of control variables (left), and the space of latent variables (right),
over the sub-level sets of the energy function in (5). A similar trajectory of
the GD algorithm is depicted in Fig. 8(b). Observe that the PHGD’s crosses the
sub-level sets of the energy function _at most once_ until it asymptotically
reaches the game’s equilibrium point at $\theta^{\ast}$, as opposed to the
trajectory of GD, which exhibits an erratic behavior. In particular, as is
depicted in the semi-log plot in Fig. 8(c), PHGD converges to the game’s
equilibrium point at an exponential rate as opposed to the rate of GD, which,
at best, can be described as linear.

(a) A trajectory of PHGD in a regularized game of Rock-Paper-Scissors as
depicted in each player’s $2$-dimensional simplex of latent variables. Notice
that the trajectory converges to the latent game’s equilibrium point
$x^{\ast}$.

(b) A trajectory of GD in a regularized game of Rock-Paper-Scissors as
depicted in each player’s $2$-dimensional simplex of latent variables. Notice
that the trajectory exhibits erratic behavior.

(c) The mean distance and confidence bound of $x$ to the latent game’s
equilibrium point $x^{\ast}$ along similar trajectories of PHGD and GD in a
regularized game of Rock-Paper-Scissors. The distance is depicted in a
logarithmic scale in order to reveal the exponential rate of convergence of
PHGD.

#### A Hidden Game of Rock-Paper-Scissors.

In the next example we consider a regularized hidden game of Rock-Paper-
Scissors between two players. In a standard Rock-Paper-Scissors game each
player may choose among three strategies, namely, Rock, Paper, or Scissors. No
strategy dominates over the others, with Rock ruling over Scissors, Paper
ruling over Rock, and Scissors ruling over Paper. In this example, each player
$i$ controls a $5$-dimensional vector $\theta_{i}\in\mathbb{R}^{5}$ of control
variables, which, once again, they may feed their individual differentiable
preconfigured MLP, whose output $x_{i}=\chi_{i}(\theta_{i})$ lies in the
$2$-dimensional simplex that encodes the space of probability distributions
among the three strategies of the latent game. The two MLPs are given by the
following representation maps:

$\chi_{i}(\theta_{i})=\operatorname{softmax}\big{(}A^{(2)}_{i}\times
CeLU(A^{(1)}_{i}\times\theta_{i})\big{)}\quad\text{for all $i=1,2$},$ (D.4)

where the matrices $A^{(1)}_{i}\in[-1,1]^{4\times 5}$, and
$A^{(2)}_{i}\in[-1,1]^{3\times 4}$ are random, and the activation function
$CeLU:\mathbb{R}\to(-1,\infty)$, given as in (D.2b), is applied pair-wise. The
definition of
$\operatorname{softmax}:\mathbb{R}^{d}\to\operatorname{\operatorname{\Delta}}_{d-1}$,
where $\operatorname{\operatorname{\Delta}}_{d-1}$ is the $(d-1)$-dimensional
simplex is given, for reference, by

$\operatorname{softmax}_{j}(x)=\frac{\exp(x_{j})}{\sum_{k=1}^{d}\exp(x_{k})}\quad\text{for
all $j=1,\dots,d$}.$ (D.5)

In this case, the latent game’s loss functions are given by the following
polynomial system of equations, whose unique equilibrium lies at the uniform
distributions
$x^{\ast}_{i}=\chi_{i}(\theta^{\ast}_{i})=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$,
$i=1,2$:

$f_{1}(x)=-f_{2}(x)=-x_{1}^{\intercal}Ax_{2}+h_{0.2}(x)\quad\text{where
$A=\begin{bmatrix}[r]0&-1&1\\\ 1&0&-1\\\ -1&1&0\end{bmatrix}$.}$ (D.6)

Although, in this example, it is not possible to visualize the trajectories of
PHGD and GD in the space of control variables due to the large dimensionality
of the base game, we may still get a glimpse of the trajectories’ behavior in
the space of latent variables. Fig. 10(a) depicts an arbitrary trajectory of
PHGD with step-size $0.01$, as it evolves in the simplices of the two players.
Notice, that the trajectory, clearly, converges to the equilibrium of the
latent game. A trajectory of GD, with the same step size and initialization
point, is depicted in Fig. 10(b). In this case, the erratic behavior of GD is
more apparent than in the previous example. A more in-depth comparison of the
algorithms in the current setup is depicted in the semi-log plot of Fig.
10(c), where we visualize the mean distance, and confidence bounds, to the
equilibrium point across $100$ random trajectories of the two algorithms.
Observe, that PHGD exhibits an exponential rate of convergence, as opposed to
the linear rate of GD.

Figure 11. The mean distance and confidence bounds of $x$ to the latent game’s
equilibrium point $x^{\ast}$ along similar trajectories of PHGD and GD in a
regularized Shapley game. The distance is depicted in a logarithmic scale in
order to reveal the exponential rate of convergence of PHGD.

#### A Hidden Shapley’s Game.

The next game we are interested in is a hidden Shapley’s game. The standard
Shapley’s game is a two-player normal-form game with payoff matrices:

$A=\begin{bmatrix}[r]1&0&\beta\\\ \beta&1&0\\\
0&\beta&1\end{bmatrix}\qquad\text{and}\qquad B=\begin{bmatrix}[r]-\beta&1&0\\\
0&-\beta&1\\\ 1&0&-\beta\end{bmatrix},$ (D.7)

for some $\beta\in(0,1)$. The setup of this example is quite similar to the
one in the previous example. However, there are a few noteworthy differences.
To begin with, the hidden Shapley’s game is not a zero-sum game. Specifically,
the latent game’s loss functions are given by the following polynomial system
of equations:

$\displaystyle f_{1}(x)$ $\displaystyle=-x_{1}^{\intercal}Ax_{2}+h_{0.2}(x)$
(D.8) $\displaystyle f_{2}(x)$
$\displaystyle=-x_{2}^{\intercal}B^{\intercal}x_{1}+h_{0.2}(x).$

As in the hidden Rock-Paper-Scissors game, this game’s unique equilibrium also
lies in
$x^{\ast}_{i}=\chi_{i}(\theta^{\ast}_{i})=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$,
$i=1,2$. A second difference is the small modulus, $\mu=0.2$, that we choose
for the strongly-convex regularizer of this game. In Fig. 11 we depict a semi-
log plot of the mean performance of PHGD and GD in the above game constructed
using the same parameters as in the case of the hidden Rock-Paper-Scissors
game. Notice that although the behaviour of PHGD is similar in both games, the
confidence bounds of GD are drastically larger in the current example.

Figure 12. The mean distance and confidence bounds of $x$ to the latent game’s
equilibrium point $x^{\ast}$ along similar trajectories of PHGD and GD in a
regularized El Farol Bar game. The distance is depicted in a logarithmic scale
in order to reveal the exponential rate of convergence of PHGD.

#### A Hidden El Farol Bar Game.

As a final example, we are going to revisit and describe the details of the
hidden El Farol Bar game we introduced in Section 5. The El Farol Bar game is
a famous congestion game that is often described as a game between
populations. However, in this example, we are interested in its atomic
$N$-playe variant. In the standard El Farol Bar game each player is given the
option of visiting a specific bar in El Farol, and the outcome of the game is
determined based on the number of players that decided to visit the bar. From
the perspective of the player, there are three possible situations they may
encounter, which carry some respective payoff. If the player decides to do not
to visit the bar, then, independently of the number of bar tenants, the player
receives a payoff $S$. On the other hand, if the player decides to visit the
El Farol bar, then depending on how crowded the bar is, they may receive a
payoff that is strictly smaller, or strictly larger than $S$. If the bar is
crowded, i.e., more than $C\geq 0$ other players have visited the bar at the
same time, then each of them receives payoff $B<S$. However, if the bar is not
crowded, i.e., the total number of tenants is less than $C$, then they receive
payoff $G>S$. It’s not difficult to verify that the El Farol Bar game has a
unique mixed Nash equilibrium, where each player chooses to visit the bar with
probability $\frac{C}{N}$.

We are going to consider a hidden variant of the above game among $N=30$
players. Each player $i$ controls a $5$-dimensional vector of control
variables $\theta_{i}\in\mathbb{R}^{5}$, which feeds to an individual,
differentiable, and preconfigured MLP. The MLP’s output
$x_{i}=\chi_{i}(\theta_{i})$ is guaranteed to lie in $[0,1]$ and is
interpreted as the probability of player $i$ visiting the El Farol bar.
Regarding the MLP configuration, we follow a similar structure as in the
previous examples. Specifically, the representation maps
$\chi_{i}:\mathbb{R}^{5}\to[0,1]$ are defined as

$\chi_{i}(\theta_{i})=\operatorname{sigmoid}\big{(}\alpha^{(2)}_{i}\cdot
CeLU(A^{(1)}_{i}\times\theta_{i})\big{)}\quad\text{for all $i=1,2$},$ (D.9)

where $A^{(1)}_{i}\in[-0.85,0.85]^{4\times 5}$, and
$\alpha^{(2)}_{i}\in[-1,1]^{4}$ are randomly chosen. The additional
restriction to the domain of $A^{(1)}$ reduces the chance for over-flow
numerical errors of the $\operatorname{sigmoid}$ activation function. The
activation function $CeLU:\mathbb{R}\to(-1,\infty)$ is given as in (D.2b) and
is applied pair-wise to the output of $A^{(1)}_{i}\times\theta_{i}$. The loss
functions of this game follow the standard variant’s definitions, namely, we
have that

$f_{i}(x)=S+x_{i}\bigg{(}G-S+\operatorname{\mathbb{P}}\Big{(}\sum_{i\neq
j}x_{i}\geq C\Big{)}(B-G)\bigg{)}+h_{0.5}(x)\quad\text{for all
$i\in\mathcal{N}$},$ (D.10)

and the latent game’s unique equilibrium is at $x^{\ast}_{i}=\frac{C}{N}$,
$i\in\mathcal{N}$.

The large dimensionality of the above game prohibits the usage of a detailed
visualization as opposed to the previous examples. However, sufficient
information about the behavior PHGD, and GD can be gathered by the performance
log-plot across $100$ random trajectories in Fig. 12. Observe that, regardless
of the increased number of players, the behavior of PHGD is unaffected, i.e.,
it converges to the game’s equilibrium at an exponential rate. On the other
hand, the GD fails to converge in the game’s equilibrium. In fact it
eventually maintains a constant distance from it, unable to procceed further;
an indication of a cycling behavior.

## References

  * Antonakopoulos et al. [2019] Antonakopoulos, K., Belmega, E. V., and Mertikopoulos, P.  An adaptive mirror-prox algorithm for variational inequalities with singular operators.  In _NeurIPS ’19: Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , 2019.
  * Arthur [1995] Arthur, W. B.  Complexity in economic and financial markets.  _Complexity_ , 1(1):20–25, 1995.
  * Auslender & Teboulle [2005] Auslender, A. and Teboulle, M.  Interior projection-like methods for monotone variational inequalities.  _Mathematical Programming_ , 104:39–68, 2005.
  * Bakhtin et al. [2022] Bakhtin, A., Wu, D. J., Lerer, A., Gray, J., Jacob, A. P., Farina, G., Miller, A. H., and Brown, N.  Mastering the game of no-press diplomacy via human-regularized reinforcement learning and planning.  _arXiv preprint arXiv:2210.05492_ , 2022.
  * Beltratti et al. [1996] Beltratti, A., Margarita, S., Terna, P., et al.  _Neural networks for economic and financial modelling_.  International Thomson Computer Press London, UK, 1996.
  * Bichler et al. [2021] Bichler, M., Fichtl, M., Heidekrüger, S., Kohring, N., and Sutterer, P.  Learning equilibria in symmetric auction games using artificial neural networks.  _Nat. Mach. Intell._ , 3(8):687–695, 2021.  doi: 10.1038/s42256-021-00365-4.  URL https://doi.org/10.1038/s42256-021-00365-4.
  * Bravo et al. [2018] Bravo, M., Leslie, D. S., and Mertikopoulos, P.  Bandit learning in concave ${N}$-person games.  In _NeurIPS ’18: Proceedings of the 32nd International Conference of Neural Information Processing Systems_ , 2018.
  * Chung [1954] Chung, K.-L.  On a stochastic approximation method.  _The Annals of Mathematical Statistics_ , 25(3):463–483, 1954.
  * Daskalakis et al. [2009] Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H.  The complexity of computing a Nash equilibrium.  _Communications of the ACM_ , 52(2):89–97, 2009\.
  * Daskalakis et al. [2021] Daskalakis, C., Skoulakis, S., and Zampetakis, M.  The complexity of constrained min-max optimization.  In _STOC ’21: Proceedings of the 53rd annual ACM SIGACT symposium on the Theory of Computing_ , 2021.
  * Duvocelle et al. [2023] Duvocelle, B., Mertikopoulos, P., Staudigl, M., and Vermeulen, D.  Multi-agent online learning in time-varying games.  _Mathematics of Operations Research_ , 48(2):914–941, May 2023.
  * Facchinei & Pang [2003] Facchinei, F. and Pang, J.-S.  _Finite-Dimensional Variational Inequalities and Complementarity Problems_.  Springer Series in Operations Research. Springer, 2003.
  * Gidel et al. [2021] Gidel, G., Balduzzi, D., Czarnecki, W. M., Garnelo, M., and Bachrach, Y.  Minimax theorem for latent games or: How i learned to stop worrying about mixed-nash and love neural nets.  _AISTATS_ , 2021.
  * 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 _NIPS ’14: Proceedings of the 28th International Conference on Neural Information Processing Systems_ , 2014.
  * Hart & Mas-Colell [2003] Hart, S. and Mas-Colell, A.  Uncoupled dynamics do not lead to Nash equilibrium.  _American Economic Review_ , 93(5):1830–1836, 2003.
  * Hart & Mas-Colell [2006] Hart, S. and Mas-Colell, A.  Stochastic uncoupled dynamics and Nash equilibrium.  _Games and Economic Behavior_ , 57:286–303, 2006.
  * Hazan [2012] Hazan, E.  A survey: The convex optimization approach to regret minimization.  In Sra, S., Nowozin, S., and Wright, S. J. (eds.), _Optimization for Machine Learning_ , pp. 287–304. MIT Press, 2012.
  * Hsieh et al. [2019] Hsieh, Y.-G., Iutzeler, F., Malick, J., and Mertikopoulos, P.  On the convergence of single-call stochastic extra-gradient methods.  In _NeurIPS ’19: Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , pp. 6936–6946, 2019.
  * Hsieh et al. [2021] Hsieh, Y.-P., Mertikopoulos, P., and Cevher, V.  The limits of min-max optimization algorithms: Convergence to spurious non-critical sets.  In _ICML ’21: Proceedings of the 38th International Conference on Machine Learning_ , 2021.
  * Kelly et al. [1998] Kelly, F. P., Maulloo, A. K., and Tan, D. K. H.  Rate control for communication networks: shadow prices, proportional fairness and stability.  _Journal of the Operational Research Society_ , 49(3):237–252, March 1998.
  * Lan [2020] Lan, G.  _First-order and Stochastic Optimization Methods for Machine Learning_.  Springer, 2020.
  * Lee [1997] Lee, J. M.  _Riemannian Manifolds: an Introduction to Curvature_.  Number 176 in Graduate Texts in Mathematics. Springer, 1997.
  * Lee [2003] Lee, J. M.  _Introduction to Smooth Manifolds_.  Number 218 in Graduate Texts in Mathematics. Springer-Verlag, New York, NY, 2003.
  * Letcher [2021] Letcher, A.  On the impossibility of global convergence in multi-loss optimization.  In _ICLR ’21: Proceedings of the 2021 International Conference on Learning Representations_ , 2021.
  * Liu et al. [2021] Liu, X., Yu, C., Zhang, Z., Zheng, Z., Rong, Y., Lv, H., Huo, D., Wang, Y., Chen, D., Xu, J., Wu, F., Chen, G., and Zhu, X.  Neural auction: End-to-end learning of auction mechanisms for e-commerce advertising.  In Zhu, F., Ooi, B. C., and Miao, C. (eds.), _KDD ’21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021_ , pp. 3354–3364. ACM, 2021.  doi: 10.1145/3447548.3467103.  URL https://doi.org/10.1145/3447548.3467103.
  * Madry et al. [2018] Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A.  Towards deep learning models resistant to adversarial attacks.  In _ICLR ’18: Proceedings of the 2018 International Conference on Learning Representations_ , 2018.
  * Mertikopoulos & Moustakas [2016] Mertikopoulos, P. and Moustakas, A. L.  Learning in an uncertain world: MIMO covariance matrix optimization with imperfect feedback.  _IEEE Trans. Signal Process._ , 64(1):5–18, January 2016.
  * Mertikopoulos & Zhou [2019] Mertikopoulos, P. and Zhou, Z.  Learning in games with continuous action sets and unknown payoff functions.  _Mathematical Programming_ , 173(1-2):465–507, January 2019.
  * Mertikopoulos et al. [2017] Mertikopoulos, P., Belmega, E. V., Negrel, R., and Sanguinetti, L.  Distributed stochastic optimization via matrix exponential learning.  _IEEE Trans. Signal Process._ , 65(9):2277–2290, May 2017.
  * Mertikopoulos et al. [2023] Mertikopoulos, P., Hsieh, Y.-P., and Cevher, V.  A unified stochastic approximation framework for learning in games.  _Mathematical Programming_ , forthcoming, 2023.
  * Milionis et al. [2023] Milionis, J., Papadimitriou, C., Piliouras, G., and Spendlove, K.  An impossibility theorem in game dynamics.  _Proceedings of the National Academy of Sciences_ , 120(41):e2305349120, 2023.
  * Mladenovic et al. [2021] Mladenovic, A., Sakos, I., Gidel, G., and Piliouras, G.  Generalized natural gradient flows in hidden convex-concave games and gans.  In _International Conference on Learning Representations_ , 2021.
  * Nesterov [2007] Nesterov, Y.  Dual extrapolation and its applications to solving variational inequalities and related problems.  _Mathematical Programming_ , 109(2):319–344, 2007\.
  * Nikaido & Isoda [1955] Nikaido, H. and Isoda, K.  Note on non-cooperative convex games.  _Pacific Journal of Mathematics_ , 5:807–815, 1955.
  * Orda et al. [1993] Orda, A., Rom, R., and Shimkin, N.  Competitive routing in multi-user communication networks.  _IEEE/ACM Trans. Netw._ , 1(5):614–627, October 1993.
  * Perolat et al. [2022] Perolat, J., De Vylder, B., Hennes, D., Tarassov, E., Strub, F., de Boer, V., Muller, P., Connor, J. T., Burch, N., Anthony, T., et al.  Mastering the game of stratego with model-free multiagent reinforcement learning.  _Science_ , 378(6623):990–996, 2022.
  * Pinto et al. [2017] Pinto, L., Davidson, J., Sukthankar, R., and Gupta, A.  Robust adversarial reinforcement learning.  In _ICML ’17: Proceedings of the 34th International Conference on Machine Learning_ , 2017.
  * Rosen [1965] Rosen, J. B.  Existence and uniqueness of equilibrium points for concave ${N}$-person games.  _Econometrica_ , 33(3):520–534, 1965.
  * Scutari et al. [2010] Scutari, G., Facchinei, F., Palomar, D. P., and Pang, J.-S.  Convex optimization, game theory, and variational inequality theory in multiuser communication systems.  _IEEE Signal Process. Mag._ , 27(3):35–49, May 2010.
  * Silver et al. [2017] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al.  Mastering the game of go without human knowledge.  _nature_ , 550(7676):354–359, 2017.
  * Singla & Feizi [2021] Singla, S. and Feizi, S.  Fantastic four: Differentiable and efficient bounds on singular values of convolution layers.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.  URL https://openreview.net/forum?id=JCRblSgs34Z.
  * Vinyals et al. [2019] Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., Oh, J., Horgan, D., Kroiss, M., Danihelka, I., Huang, A., Sifre, L., Cai, T., Agapiou, J. P., Jaderberg, M., Vezhnevets, A. S., Leblond, R., Pohlen, T., Dalibard, V., Budden, D., Sulsky, Y., Molloy, J., Paine, T. L., Gulcehre, C., Wang, Z., Pfaff, T., Wu, Y., Ring, R., Yogatama, D., Wünsch, D., McKinney, K., Smith, O., Schaul, T., Lillicrap, T., Kavukcuoglu, K., Hassabis, D., Apps, C., and Silver, D.  Grandmaster level in starcraft ii using multi-agent reinforcement learning.  _Nature_ , 575:350–354, 2019.
  * Vlatakis-Gkaragkounis et al. [2019] Vlatakis-Gkaragkounis, E.-V., Flokas, L., and Piliouras, G.  Poincaré recurrence, cycles and spurious equilibria in gradient-descent-ascent for non-convex non-concave zero-sum games.  In _Advances in Neural Information Processing Systems_ , pp. 10450–10461, 2019.
  * Vlatakis-Gkaragkounis et al. [2021] Vlatakis-Gkaragkounis, E.-V., Flokas, L., and Piliouras, G.  Solving min-max optimization with hidden structure via gradient descent ascent.  _Advances in Neural Information Processing Systems_ , 34:2373–2386, 2021.
  * Whitehead et al. [2008] Whitehead, D. et al.  The el farol bar problem revisited: Reinforcement learning in a potential game.  _ESE discussion papers_ , 186, 2008.
  * Zhang et al. [2019] Zhang, G., Martens, J., and Grosse, R. B.  Fast convergence of natural gradient descent for over-parameterized neural networks.  _Advances in Neural Information Processing Systems_ , 32, 2019.

  *[PHGD]: preconditioned hidden gradient descent
  *[MLPs]: multi-layer perceptron
  *[MLP]: multi-layer perceptron
  *[i.i.d.]: independent and identically distributed
  *[GD]: gradient descent
  *[LHS]: left-hand side