Iosif Sakos
email: iosif_sakos@mymail.sutd.edu.sg

Emmanouil V Vlatakis-Gkaragkounis

AND Georgios Piliouras
email: georgios@sutd.edu.sg

EXPLOITING HIDDEN STRUCTURES IN NON-CONVEX GAMES FOR CONVERGENCE TO NASH EQUILIBRIUM

Keywords: 2020 Mathematics Subject Classification. Primary 91A10, 91A26, secondary 68Q32 Non-convex games, hidden games, stochastic algorithms, Nash equilibrium

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.

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 (GANs) [START_REF] Goodfellow | Generative adversarial nets[END_REF], robust reinforcement learning [START_REF] Pinto | Robust adversarial reinforcement learning[END_REF], adversarial training [START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF], multi-agent reinforcement learning in games [START_REF] Perolat | Mastering the game of stratego with model-free multiagent reinforcement learning[END_REF][START_REF] Silver | Mastering the game of go without human knowledge[END_REF][START_REF] Vinyals | Grandmaster level in starcraft ii using multi-agent reinforcement learning[END_REF], and even multi-player games that include free-form natural-language communication [START_REF] Bakhtin | Mastering the game of no-press diplomacy via human-regularized reinforcement learning and planning[END_REF]. 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 [START_REF] Daskalakis | The complexity of computing a Nash equilibrium[END_REF][START_REF] Daskalakis | The complexity of constrained min-max optimization[END_REF] as well as dynamic impossibility results [START_REF] Hart | Uncoupled dynamics do not lead to Nash equilibrium[END_REF][START_REF] Hart | Stochastic uncoupled dynamics and Nash equilibrium[END_REF][START_REF] Hsieh | The limits of min-max optimization algorithms: Convergence to spurious non-critical sets[END_REF][START_REF] Letcher | On the impossibility of global convergence in multi-loss optimization[END_REF][START_REF] Mertikopoulos | A unified stochastic approximation framework for learning in games[END_REF][START_REF] Milionis | An impossibility theorem in game dynamics[END_REF]. 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 [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave N -person games[END_REF]. As special cases, this setting includes singleagent 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., [START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF][START_REF] Scutari | Convex optimization, game theory, and variational inequality theory in multiuser communication systems[END_REF] 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 [START_REF] Vlatakis-Gkaragkounis | Poincaré recurrence, cycles and spurious equilibria in gradient-descent-ascent for non-convex non-concave zero-sum games[END_REF], 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, [START_REF] Gidel | Minimax theorem for latent games or: How i learned to stop worrying about mixed-nash and love neural nets[END_REF] 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 [START_REF] Vlatakis-Gkaragkounis | Solving min-max optimization with hidden structure via gradient descent ascent[END_REF] 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, [START_REF] Mladenovic | Generalized natural gradient flows in hidden convex-concave games and gans[END_REF] 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

• • • softmax θ R P S R P S softmax ϕ • • • • • • • • • • • • • • • 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. [START_REF] Mladenovic | Generalized natural gradient flows in hidden convex-concave games and gans[END_REF]). 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.

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 [START_REF] Mladenovic | Generalized natural gradient flows in hidden convex-concave games and gans[END_REF], 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 O(1/ √ 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 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.

Problem setup and preliminaries

Throughout the sequel, we will focus on continuous N -player games where each player, indexed by i ∈ N := {1, . . . , N }, has a convex set of control variables θ i ∈ Θ i := R mi , and a continuously differentiable loss function ℓ i : Θ → R, where Θ := i Θ i denotes the game's control space. For concreteness, we will refer to the tuple Γ ≡ Γ(N , Θ, ℓ) as the base game.

The most relevant solution concept in this setting is that of a Nash equilibrium, i.e., an action profile θ * ∈ Θ that discourages unilateral deviations. Formally, we say that θ * ∈ Θ is a Nash equilibrium of the base game Γ if where we employ the standard game-theoretic shorthand (θ i ; θ -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 [START_REF] Hart | Uncoupled dynamics do not lead to Nash equilibrium[END_REF][START_REF] Hart | Stochastic uncoupled dynamics and Nash equilibrium[END_REF] already preclude the existence of uncoupled dynamics that converge to a Nash equilibrium in all games; more recently, Milionis et al. [START_REF] Milionis | An impossibility theorem in game dynamics[END_REF] established a similar impossibility result even for possibly coupled dynamics (in both discrete and continuous time), while Daskalakis et al. [START_REF] Daskalakis | The complexity of computing a Nash equilibrium[END_REF][START_REF] Daskalakis | The complexity of constrained min-max optimization[END_REF] has shown that even the computation of an approximate equilibrium can be beyond reach.

ℓ i (θ * ) ≤ ℓ i (θ i ; θ * -i ) for all θ i ∈ Θ i , i ∈ N (NE) θ • Control variables x = χ(θ) • Latent variables χ R d R m R f ℓ = f • χ
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 [START_REF] Vlatakis-Gkaragkounis | Poincaré recurrence, cycles and spurious equilibria in gradient-descent-ascent for non-convex non-concave zero-sum games[END_REF][START_REF] Vlatakis-Gkaragkounis | Solving min-max optimization with hidden structure via gradient descent ascent[END_REF] we have the following definition. Definition 1. We say that the game Γ ≡ Γ(N , Θ, ℓ) admits a latent -or hidden -structure if:

(1) Each player's control variables can be mapped faithfully to a closed convex set of latent variables x i ∈ X i ⊆ R di ; formally, we posit that there exists a Lipschitz smooth map χ i : Θ i → X i with no critical points and such that cl(χ i (Θ i )) = X i . (2) Each player's loss function factors through the game's latent space X := i X i as

ℓ i (θ) = f i (χ 1 (θ 1 ), . . . , χ N (θ N )) (1)
for some Lipschitz smooth function f i : X → R called the player's latent loss function. For concreteness, we will refer to the product map χ(θ) = (χ i (θ i )) i∈N as the game's representation map, and the tuple G ≡ G(N , X , f ) will be called the hidden / latent game. To simplify notation later on, we also assume that X i has nonempty topological interior, so, in particular, dim(X i ) = d i ≤ m i . We illustrate the above notions in two simple -but not simplistic -examples below; for a schematic representation, cf. Fig. 2. Example 2.2. A more complex scenario involves non-convex / non-concave min-max optimization problems of the form min θ1 max θ2 χ 1 (θ 1 ) ⊺ Cχ 2 (θ 2 ) where χ 1 and χ 2 are preconfigured multi-layer perceptrons (MLPs) 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 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 cl(χ(Θ)) = X means that all latent variable profiles x ∈ X can be approximated to arbitrary accuracy in the game's control space. The reason that we do not make the stronger assumption χ(Θ) = X is to capture cases like the sigmoid map: if χ(θ) = [1 + exp(-θ)] -1 for θ ∈ R, the image of χ is the interval (0, 1), which is convex but not closed.

Remark 2. Second, the requirement that χ has no critical points simply means that, for any control variable configuration θ ∈ Θ, the Jacobian Jac(χ(θ)) of χ at θ has full rank. By the implicit function theorem [START_REF] Lee | Introduction to Smooth Manifolds[END_REF], this simply means that χ locally looks like a projection (in suitable coordinates around θ), 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 χ 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 [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave N -person games[END_REF], a condition more commonly known in the optimization literature as monotonicity [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. Formally, let

g i (x) = ∇ i f i (x) := ∇ xi f i (x) (2)
denote the individual gradient of the latent loss function of player i ∈ N , and write g(x) = (g 1 (x), . . . , g N (x)) for the profile thereof. We then say that the latent game G is:

• Monotone if ⟨g(x ′ ) -g(x), x ′ -x⟩ ≥ 0 for all x, x ′ ∈ X . (3a)
• Strictly monotone if

⟨g(x ′ ) -g(x), x ′ -x⟩ > 0 for all x, x ′ ∈ X , x ̸ = x ′ . (3b)
• Strongly monotone if, for some µ > 0, we have

⟨g(x ′ ) -g(x), x ′ -x⟩ ≥ µ∥x ′ -x∥ 2 for all x, x ′ ∈ 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 Γ admits a hidden monotone structure when the latent game G is monotone as above (and likewise for strictly / strongly monotone structures).

Examples of monotone games include neural Kelly auctions and Cournot oligopolies [START_REF] Beltratti | Neural networks for economic and financial modelling[END_REF][START_REF] Bichler | Learning equilibria in symmetric auction games using artificial neural networks[END_REF][START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF][START_REF] Liu | Neural auction: End-to-end learning of auction mechanisms for e-commerce advertising[END_REF], covariance matrix optimization problems and power control [START_REF] Mertikopoulos | Learning in an uncertain world: MIMO covariance matrix optimization with imperfect feedback[END_REF][START_REF] Mertikopoulos | Distributed stochastic optimization via matrix exponential learning[END_REF][START_REF] Scutari | Convex optimization, game theory, and variational inequality theory in multiuser communication systems[END_REF], certain classes of congestion games [START_REF] Orda | Competitive routing in multi-user communication networks[END_REF], 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 * = χ(θ * ) of a Nash equilibrium θ * ∈ Θ of the base game satisfies a Stampacchia variational inequality of the form ⟨g(x * ), x -x * ⟩ ≥ 0 for all x ∈ X .

(SVI)

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

⟨g(x), x -x * ⟩ ≥ 0 for all x ∈ X . (MVI)
To avoid trivialities, we will assume throughout that the solution set X * of (SVI)/(MVI) is nonempty. This is a standard assumption without which the problem is not well-posedand hence, meaningless from an algorithmic perspective. Notation. To streamline notation (and unless explicitly mentioned otherwise), we will denote control variables by θ i and θ, and we will write x i = χ i (θ i ) and x = χ(θ) for the induced latent variables. We will also write m := i m i for the dimensionality of the game's control space Θ and d := i d i for the dimensionality of the latent space X (so, in general, m ≥ d). Finally, when the representation map χ is clear from the context, we will write J i (θ i ) := Jac(χ i (θ i )) ∈ R di×mi for the Jacobian matrix of χ i at θ i ∈ Θ i , and J(θ) = i J i (θ i ) for the associated block diagonal sum.

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: (i ) the literature so far has focused exclusively on continuous-time dynamics, with no discrete-time algorithms proven to efficiently converge to a solution; (ii ) the number of players is typically limited to two; and (iii) the representation maps are separable in the sense that the control variables are partitioned into subsets and each subset affects exactly one latent variable. 1We 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 [START_REF] Mladenovic | Generalized natural gradient flows in hidden convex-concave games and gans[END_REF], min-max games with a hidden convex-concave structure and unconstrained one-dimensional control and latent spaces per player, i.e., Θ i = R = 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 [START_REF] Mladenovic | Generalized natural gradient flows in hidden convex-concave games and gans[END_REF], it will serve as an excellent starting point.

Concretely, Mladenovic et al. [START_REF] Mladenovic | Generalized natural gradient flows in hidden convex-concave games and gans[END_REF] analyze the natural hidden gradient dynamics

θi = - 1 |χ ′ i (θ i )| 2 ∂ℓ i ∂θ i for all i ∈ 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 ℓ i = f i •χ of the game's latent loss functions yields

∂ℓ i /∂θ i = χ ′ i (θ i )•∂f i /∂x i so, in turn, (NHGD) becomes θi = - 1 χ ′ i (θ i ) ∂f i ∂x i (4)
where, for simplicity, we are tacitly assuming that χ i (θ i ) ′ > 0. This expression brings two important points to light. First, even though (NHGD) is defined in terms of the actual, control-layer gradients ∂ℓ i /∂θ i of Γ, Eq. ( 4) shows that the dynamics are actually driven by the latent-layer, "hidden gradients" g i (x) = ∂f i /∂x i of G. Second, the preconditioner |χ ′ i (θ i )| -2 in (NHGD) can be seen as a Riemannian metric on Θ: instead of defining gradients relative to the standard Euclidean metric of Θ ≡ R N , (NHGD) can be seen as a gradient flow relative to the Riemannian metric g ij (θ) = δ ij χ ′ i (θ i ), which captures the "natural" geometry induced by the representation map χ. 2 From an operational standpoint, the key property of (NHGD) that enabled the analysis of [START_REF] Mladenovic | Generalized natural gradient flows in hidden convex-concave games and gans[END_REF] is the observation that the L 2 energy function

E(θ) = 1 2 ∥χ(θ) -x * ∥ 2 (5)
between the latent representation x = χ(θ) of θ and a solution x * of (SVI) / (MVI) is a Lyapunov function for (NHGD). Indeed, a straightforward differentiation yields

Ė(θ) = 1 2 d dt ∥x -x * ∥ 2 = i ẋi • (x i -x * i ) = -[g(χ(θ))] ⊺ (χ(θ) -x * ) ≤ 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) = χ(θ(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 = χ i (θ i ) can be backsolved easily for θ (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(θ) 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 χ : Θ → X , we will consider an abstract preconditioning scheme of the form θi

= -P i (θ i )v i (θ) (7)
where

v i (θ) := ∇ θi ℓ i (θ) (8)
denotes the individual loss gradient of player i, while the preconditioning matrix P i (θ i ) ∈ R mi×mi is to be designed so that (6) still holds under [START_REF] Bravo | Bandit learning in concave N -person games[END_REF]. In this regard, a straightforward calculation (which we prove in Appendix A) yields the following: Lemma 1. Under the dynamics (7), we have

Ė(θ) = - i∈N [g i (χ(θ))] ⊺ J i (θ i )P i (θ i )[J i (θ i )] ⊺ (χ i (θ i ) -x * i ) (9)
where, as per Section 2, J i (θ i ) ∈ R di×mi denotes the Jacobian matrix of the map χ i : Θ i → X i . More compactly, letting P := i P i denote the block-diagonal ensemble of the players' 2 We do not attempt to provide here a primer on Riemannian geometry; for a masterful introduction, see [START_REF] Lee | Riemannian Manifolds: an Introduction to Curvature[END_REF].

f (θ) = KL(logit(θ1, θ2)∥(1/2, 1/3, 1/6)) over Θ ≡ R 2 .
In the subfigure to the right, we illustrate the hidden convex structure of the energy landscape, from the nonconvex sublevel sets of Θ to the latent space

X ≡ {(x1, x2) ∈ R 2 ≥0 : x1 + x2 ≤ 1}.
individual preconditioning matrices P i (and suppressing control variable arguments for concision), we have

Ė = -g(x) ⊺ • JPJ ⊺ • (x -x * ) (10)
In view of Lemma 1, a direct way to achieve the target Lyapunov property ( 6) would be to find a preconditioning matrix P such that JPJ ⊺ = I. However, since J is surjective (by the faithfulness assumption for χ), the Moore-Penrose inverse J + of J will be a right inverse to J, i.e., JJ + = I. Hence, letting P = (J ⊺ J) + = J + [J + ] ⊺ , we obtain:

JPJ ⊺ = J(J ⊺ J) + J ⊺ = JJ + (J ⊺ ) + J ⊺ = I • I = I (11)
In this way, unraveling the above, we obtain the preconditioned hidden gradient flow

θi = -P i (θ i )∇ i ℓ i (θ i ) with P i (θ i ) = [J i (θ i ) ⊺ J i (θ i )] + (PHGF)
By virtue of design, the following property of (PHGF) is then immediate:

Proposition 1. Suppose that Γ 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 θ * of θ(t) is a Nash equilibrium of Γ.

Proposition 1 validates our design choices for the preconditioning matrix 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 [START_REF] Mladenovic | Generalized natural gradient flows in hidden convex-concave games and gans[END_REF] for (NHGD). To streamline our presentation, we defer the proof of Lemma 1 and Proposition 1 to Appendix A, and instead proceed directly to provide a bona fide, algorithmic implementation of (PHGF).

3.2.

Preconditioned hidden gradient descent. 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 [START_REF] Hazan | A survey: The convex optimization approach to regret minimization[END_REF][START_REF] Lan | First-order and Stochastic Optimization Methods for Machine Learning[END_REF]: Assumption 1. Each agent's loss function is an expectation of a random function L i : Θ×Ω → R over a complete probability space (Ω, F, P), i.e., ℓ i (θ) = E[L i (θ; ω)]. We further assume that:

(1) L i (θ; ω) is measurable in ω and β-Lipschitz smooth in θ (for all θ ∈ Θ and all ω ∈ Ω respectively).

(2) The gradients of L i have bounded second moments, i.e.,

sup θ∈Θ E[∥∇L i (θ; ω)∥ 2 ] ≤ M 2 . ( 12
)
Taken together, the two components of Assumption 1 imply that each ℓ i is differentiable and Lipschitz continuous (indeed, by Jensen's inequality, we have

∥E[∇L i (θ; ω)]∥ 2 ≤ E[∥∇L i (θ; ω)∥ 2 ] ≤ M 2 )
. Moreover, by standard dominated convergence arguments, ∇L i (θ; ω) can be seen as an unbiased estimator of ∇ℓ i (θ), that is,

ℓ i (θ) = E[∇L i (θ; ω)] for all θ ∈ Θ.
In view of this, we will refer to the individual loss gradients ∇ i L i (θ; ω) of player i ∈ 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

θ i,t+1 = θ i,t -γ t P i,t V i,t (PHGD)
where:

(1) θ i,t denotes the control variable configuration of player i ∈ N at each stage t = 1, 2, . . .

(2) γ t > 0 is a variable step-size sequence, typically of the form γ t ∝ 1/t p for some p ∈ [0, 1].

(3) P i,t := P i (θ i,t ) = [J i (θ i,t ) ⊺ J i (θ i,t )] + is the preconditioner of player i ∈ N at the t-th epoch.

(4) V i,t := ∇ i L(θ i,t ; ω t ) is an individual stochastic loss gradient generated at the control variable configuration θ t by an i.i.d. sample sequence ω t ∈ Ω, t = 1, 2, . . .

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.

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 x is typically evaluated by means of the restricted merit function

Gap C (x) := sup x∈C ⟨g(x), x -x⟩ (13)
where the "test domain" C is a relatively open subset of X [START_REF] Auslender | Interior projection-like methods for monotone variational inequalities[END_REF]. The raison d'être of this definition is that, if g is monotone and x * ∈ C is a solution of (SVI) / (MVI), we have

⟨g(x), x * -x⟩ ≤ ⟨g(x * ), x * -x⟩ ≤ 0 for all x ∈ C, (14)
so the supremum in (B.6) cannot be too positive if 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 x is a solution of (SVI) / (MVI), we have Gap C (x) = 0 whenever x ∈ C. Conversely, if Gap C (x) = 0 and C is a neighborhood of x in X , then
x is a solution of (SVI) / (MVI).

Lemma 2 extends similar statements by Auslender & Teboulle [START_REF] Auslender | Interior projection-like methods for monotone variational inequalities[END_REF] and Nesterov [START_REF] Nesterov | Dual extrapolation and its applications to solving variational inequalities and related problems[END_REF]; the precise variant that we state above can be found in [START_REF] Antonakopoulos | An adaptive mirror-prox algorithm for variational inequalities with singular operators[END_REF], but, for completeness, we provide a proof in Appendix B. Now, since a latent variable profile x * = χ(θ * ) solves (SVI) if and only if the control variable configuration θ * is Nash equilibrium of the base game, the quality of a candidate solution θ ∈ Θ with x = χ( θ) can be assessed by the induced gap function

Gap( θ) := Gap X (χ( θ)) = sup x∈X ⟨g(x), x -x⟩. (15)
Indeed, since x = χ( θ) ∈ X , Lemma 2 shows that Gap( θ) ≥ 0 with equality if and only if x is a Nash equilibrium of the base game Γ. In this regard, Eq. ( 15) provides a valid equilibrium convergence metric for Γ, 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.

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. 3 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 χ : Θ → X .

Assumption 2. The singular values of the Jacobian J(θ) of the representation map χ are bounded as

σ 2 min ≤ eig(J(θ)J(θ) ⊺ ) ≤ σ 2 max ( 16
)
for some σ min , σ max ∈ (0, ∞) and for all θ ∈ Θ.

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 γ t ∝ 1/t 1/2 . Then, under Assumptions 1 and 2, the averaged process θt ∈ χ -1 t -1 t s=1 x s enjoys the equilibrium convergence rate

E[Gap( θt )] = O(log t/ √ t). ( 17
)
3 As expected, convergence rates improve along the way.

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 θt cannot be efficiently computed for general representation maps; second, even if it could, the O(log t/ √ 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 * in the game's control space, so we will measure convergence in terms of the latent equilibrium distance Err( θ

) := 1 2 ∥χ( θ) -x * ∥ 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 µ-strongly monotone game with γ t = γ/t for some γ > µ. Then, under Assumptions 1 and 2, the induced sequence of play θ t ∈ Θ, t = 1, 2, . . . , enjoys the equilibrium convergence rate

E[Err(θ t )] = 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(θ 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 µ-strongly monotone game with full gradient feedback, and a suffciently small learning rate γ > 0. Then, under Assumptions 1 and 2, the induced sequence of play θ t ∈ Θ, t = 1, 2, . . . , converges to equilibrium at a geometric rate, i.e.,

Err(θ t ) = O(ρ t ) (20)
for some constant ρ ∈ (0, 1) that depends only on the primitives of Γ and the representation map χ.

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(θ) = (∇ i ℓ i (θ)) i∈N which, coupled with the specific choice of preconditioner P i (θ i ) = [J i (θ i ) ⊺ J i (θ i )] + in (PHGD) allows us to effectively couple the latent and control layers of the problem in a "covariant" manner: Lemma 3. Fix some x ∈ X , and consider the energy function E(θ; x) = (1/2)∥χ(θ) -x∥ 2 . Then, for all θ ∈ Θ, we have

J(θ)P(θ)∇ θ E(θ; x) = χ(θ) -x. (21)
Our second intermediate result builds on Lemma 3 and provides a "template inequality" for the energy function E(θ; x) in the spirit of [START_REF] Bravo | Bandit learning in concave N -person games[END_REF][START_REF] Duvocelle | Multi-agent online learning in time-varying games[END_REF][START_REF] Hsieh | On the convergence of single-call stochastic extra-gradient methods[END_REF]. Lemma 4 (Template inequality). Suppose that Assumptions 1 and 2 hold. Then, with notation as in Lemma 3, the sequence

E t := (1/2)∥χ(θ t ) -x∥ 2 , t = 1, 2, . . . , satisfies E t+1 ≤ E t -γ t g(x t ) ⊺ (x t -x) + γ t ϕ t + γ 2 t ψ t , (22)
where

x t := χ(θ t ), ϕ t := (J(θ t )P(θ t )V t -g(x t )) ⊺ (x t -x) and ψ t is a random error sequence with sup t E[ψ t ] < ∞.
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.

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 χ i , which for each input θ i outputs a uni-dimensional latent variable x i = χ i (θ i ) guaranteed to lie in X i ≡ [0, 1]; the player's latent space.

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 [START_REF] Beltratti | Neural networks for economic and financial modelling[END_REF]. 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 (χ 1 (0), χ 2 (0)) = ( 12 , 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 [START_REF] Arthur | Complexity in economic and financial markets[END_REF][START_REF] Whitehead | The el farol bar problem revisited: Reinforcement learning in a potential game[END_REF]. In this setup, we let the control space of each player i be multi-dimensional, namely, Θ i ≡ R 5 , i ∈ N , and, as in the previous example, the representation map of each player is instantiated by some preconfigured differentiable MLP whose output x i := χ i (θ 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. 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.

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.

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 Lemma 1 and Proposition 1. For convenience, we restate the relevant results as needed.

Lemma 1. Under the dynamics (7), we have

Ė(θ) = - i∈N [g i (χ(θ))] ⊺ J i (θ i )P i (θ i )[J i (θ i )] ⊺ (χ i (θ i ) -x * i ) (9)
where, as per Section 2, J i (θ i ) ∈ R di×mi denotes the Jacobian matrix of the map χ i : Θ i → X i . More compactly, letting P := i P i denote the block-diagonal ensemble of the players' individual preconditioning matrices P i (and suppressing control variable arguments for concision), we have

Ė = -g(x) ⊺ • JPJ ⊺ • (x -x * ) (10)
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 ∈ N , for all profiles θ ∈ Θ, and for all coordinates α ∈ {1, . . . , m i }:

θiα = mi β=1 P iαβ (θ i ) ∂ℓ i (θ) ∂θ iβ . (A.1)
Now, since Γ has a hidden monotone structure, and due to the decomposition ℓ i (θ) = f i (x), we can expand the above as

θiα = mi β=1 P iαβ (θ i ) di r=1 ∂f i (x) ∂x ir ∂x ir ∂θ iβ . (A.2)
Furthermore, if we expand the left-hand side (LHS) of ( 9) we also get

Ė(θ) = N i=1 mi α=1 ∂E(θ) ∂θ iα θiα , (A.3)
where each of the summands of the above expression can also be expanded further to

∂E(θ) ∂θ iα θiα = - di l=1 (x il -x * il ) ∂x il ∂θ iα θiα . (A.4)
Putting everything together (9) follows by some trivial substitutions.

■ Proposition 1. Suppose that Γ 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 θ * of θ(t) is a Nash equilibrium of Γ.

Proof. First, observe that for any player i ∈ N , and θ i ∈ Θ i , since the player's representation map χ i is faithful, i.e., J i (θ i ) is maximal rank, it holds:

J i (θ i )P i (θ i )J i (θ i ) ⊺ = J i (θ i )J i (θ i ) + J i (θ i ) + ⊺ J i (θ i ) ⊺ = J i (θ i )J i (θ i ) + ⊺ = I. (A.5)
That is, mi α=1 mi β=1 ∂x il ∂θiα ∂xir ∂θiβ P iαβ (θ i ) = δ lr for all l, r ∈ {1, . . . , d i }, where δ lr is the Kronecker delta. Now, by Lemma 1 we have that:

Ė(θ) = - N i=1 di l=1 di r=1 δ lr (x il -x * il ) ∂f i (x) ∂x ir = - N i=1 di l=1 (x il -x * il ) ∂f i (x) ∂x il = -g(x), x -x * . (A.6)
which is negative, since x * is an optimizer of f , i.e., it satisfies the (MVI) due to monotonicity of g. Additionally, since g is strictly monotone, x * is the unique optimizer of f , and, therefore, the above condition holds with equality if and only if x = x * . ■ 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-4 in Section 3.2. As before, we restate the relevant results as needed.

Lemma 2. Suppose that g is monotone. If x is a solution of (SVI) / (MVI), we have Gap C (x) = 0 whenever x ∈ C. Conversely, if Gap C (x) = 0 and C is a neighborhood of x in X , then x is a solution of (SVI) / (MVI).

Proof of Lemma 2. Let x ∈ X be a solution of (SVI)/(MVI) so ⟨g(x), x -x⟩ ≥ 0 for all x ∈ X . Then, by the monotonicity of g, we get:

⟨g(x), x -x⟩ ≤ ⟨g(x) -g(x), x -x⟩ + ⟨g(x), x -x⟩ = -⟨g(x) -g(x), x -x⟩ -⟨g(x), x -x⟩ ≤ 0, (B.1)
so Gap C (x) ≤ 0. On the other hand, if x ∈ C, we also get Gap(x) ≥ ⟨g(x), x -x⟩ = 0, so we conclude that Gap C (x) = 0.

For the converse statement, assume that Gap C (x) = 0 for some x ∈ C and suppose that C contains a neighborhood of x in X . We then claim that x is a solution of (MVI) over C, i.e.,

⟨g(x), x -x⟩ ≥ 0 for all x ∈ C. (B.2)
To see this, assume to the contrary that there exists some

x 1 ∈ C such that ⟨g(x 1 ), x 1 -x⟩ < 0 (B.3) so, in turn, we get 0 = Gap C (x) ≥ ⟨g(x 1 ), x -x 1 ⟩ > 0, (B.4) a contradiction.
With this intermediate "local" result in hand, we are now in a position to prove that x solves (SVI). Indeed, if we suppose to the contrary that there exists some z 1 ∈ X such that ⟨g(x), z 1 -x⟩ < 0, then, by the continuity of g, there exists a neighborhood U ′ of x in X such that ⟨g(x), z 1 -x⟩ < 0 for all x ∈ U ′ . (B.5) Hence, assuming without loss of generality that U ′ ⊂ U ⊂ C (the latter assumption due to the assumption that C contains a neighborhood of x), and taking λ > 0 sufficiently small so that x = x + λ(z 1 -x) ∈ U ′ , we get that ⟨g(x), x -x⟩ = λ⟨g(x), z 1 -x⟩ < 0, in contradiction to (B.2). We thus conclude that 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 Gap( θ) 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 Gap X defined over the cone of tangent directions at x, namely the so-called "tangent residual gap"

TGap X (x) := -min z∈TC X (x),∥z∥≤1 ⟨g(x), z⟩ (B.6)
i.e., the maximum "ascent" step ⟨-g(x), z⟩ over all admissible displacement directions z from x. 4 Just like Gap C , this linearized merit function correctly identifies solutions of (SVI)/(MVI):

Lemma B.1. For all x ∈ X , we have TGap X (x) ≥ 0 with equality if and only if x solves (SVI)/ (MVI).

Proof. Let x ∈ X be some arbitrary profile of latent variables. By definition, we have that TGap X (x) = -min z∈TC X (x),∥z∥≤1 ⟨g(x), z⟩, where TC X (x) is the tangent cone to X at x. Observe that since TC X (x) is a cone, 0 ∈ TC X (x), so TGap X (x) ≥ -⟨g(x), 0⟩ = 0. Now assume that TGap X (x) = 0. Then, the following are equivalent:

TGap X (x) = 0 ⇐⇒ -min z∈TC X (x),∥z∥≤1 ⟨g(x), z⟩ = 0 ⇐⇒ ⟨g(x), z⟩ ≥ 0 for all z ∈ TC X (x), ∥z∥ ≤ 1 ⇐⇒ ⟨g(x), z⟩ ≥ 0 for all z ∈ TC X (x),

(B.7)
where the last equivalence follows because TC X (x) is a cone. Rearranging the terms, we may equivalently write ⟨-g(x), z⟩ ≤ 0 for all z ∈ TC X (x). Notice that, by the definition of the tangent cone, the latter is equivalent to ⟨-g(x), x -z⟩ ≤ 0 for all z ∈ X . Therefore, TGap X (x) = 0 if and only if x satisfies (SVI).

■ Now, if θ * is a Nash equilibrium of the base game, the latent variable configuration x * = χ(θ * ) solves (SVI)/(MVI), so TGap X is a valid equilibrium convergence metric for Γ. However, since TGap 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

TGap Θ ( θ) := -min η∈R m ,∥η∥≤1 ⟨v( θ), η⟩ = ∥v( θ)∥ * (B.8)
where v(θ) := (∇ i ℓ i (θ)) i∈N collects the players' loss gradients relative to their control variables, and ∥•∥ * denotes its dual norm (so TGap Θ ( θ) is evaluated directly on the game's control space). Of course, as control variables are mapped to latent variables, χ introduces a certaint distortion (due to nonlinearities). This distortion can be quantified by the following lemma (see also Fig. 6 above):

J i (θ) σ min (θ) σmax(θ) ∥z∥ ≤ σ min ∥z∥ ≤ σmax ∥η∥ ≤ 1
Lemma B.2. Let x = χ( θ) for some θ ∈ Θ. We then have

σ min TGap X (x) ≤ TGap Θ ( θ) ≤ σ max TGap X (x) (B.9)
In particular, TGap Θ ( θ) ≥ 0 for all θ ∈ Θ, with equality if and only if θ is a Nash equilibrium of Γ.

Proof. To begin with, let us define the balls B Θ ≡ {η ∈ R m : ∥η∥ ≤ 1}, and B X ≡ {z ∈ R d : ∥z∥ ≤ 1}. Now, let θ ∈ Θ be some arbitrary profile of control variables. By Assumption 2, we have that the singular values of the Jacobian J( θ) of the representation map χ are bounded from above and below by σ max < ∞ and σ min > 0 respectively. That is, σ min ∥η∥ ≤ ∥J( θ)η∥ ≤ σ max ∥η∥ for all η ∈ R m , which implies that σ min B X ⊆ J( θ)B Θ ⊆ σ max B X . By definition, we also have that, v( θ) = J( θ) ⊺ g χ( θ) = J( θ) ⊺ g(x), and, hence

TGap Θ ( θ) = -min η∈BΘ ⟨v( θ), η⟩ = -min z∈J( θ)BΘ ⟨g(x), z⟩ (B.10)
Now, recall that the set of Nash equilibria Θ * ⊂ Θ is non-empty. In particular, since the Θ ≡ 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 Θ to X , also implies that χ(Θ * ) lies in the interior of X . Finally, since χ is smooth, and in conjunction with the previous observations, it follows that TGap Θ ( θ) = ∥v( θ)∥ and TGap X (x) = ∥g(x)∥, hence it is easy to see from the above discussion that

σ min TGap X (χ( θ)) ≤ TGap Θ ( θ) ≤ σ max TGap X (χ( θ)) (B.11)
and our proof is complete.

■

In view of the above discussion, the reader may wonder why not use the tangent gap TGap Θ directly as a performance metric. The reason for this is that, if the solutions x * of (SVI)/(MVI) do not belong to the image of χ, the dual norm of v( θ) 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 Gap and Err are more appropriate as performance measures.

B.2. Convergence analysis and template inequalities.

Lemma 3. Fix some x ∈ X , and consider the energy function E(θ; x) = (1/2)∥χ(θ) -x∥ 2 . Then, for all θ ∈ Θ, we have

J(θ)P(θ)∇ θ E(θ; x) = χ(θ) -x. ( 21
)
Proof. Let i ∈ N be some arbitrary player, let θ ∈ Θ be some arbitrary profile of control variables, and let η ∈ R di be some arbitrary vector. Then for each coordinate α ∈ {1, . . . , m i }, and latent profile x ∈ X , we have that

∂E(θ; x) ∂θ iα = di j=1 (x ij -xij ) ∂x ij ∂θ iα . (B.12) That is ∇ θi E(y; x) = J i (θ i ) ⊺ (x i -xi )
. Now, we can multiply both sides of the above expression with P i (θ i ) to get

P i (θ i ) ∇ θi E(θ; x) = P i (θ i )J i (θ i ) ⊺ (x i -xi ) = J i (θ i ) + J i (θ i ) + ⊺ J i (θ i ) ⊺ (x i -xi ) = J i (θ i ) + (x i -xi ), (B.13)
where in the last equality we used the fact that the i-th player's representation map χ i is a faithful representation, i.e., J i (θ i ) is maximal rank. Finally, by expanding the LHS of ( 21), and applying the above simplification the result follows.

■ Lemma 4 (Template inequality). Suppose that Assumptions 1 and 2 hold. Then, with notation as in Lemma 3, the sequence E t := (1/2)∥χ(θ t ) -x∥ 2 , t = 1, 2, . . . , satisfies

E t+1 ≤ E t -γ t g(x t ) ⊺ (x t -x) + γ t ϕ t + γ 2 t ψ t , (22)
where x t := χ(θ t ), ϕ t := (J(θ t )P(θ t )V t -g(x t )) ⊺ (x t -x) and ψ t is a random error sequence with sup t E[ψ t ] < ∞.

Proof. For each t = 1, 2, . . . we expand x t+1 using its second-order Taylor approximation at θ t ; i.e., for each player i = 1, . . . , N and each coordinate l = 1, . . . , d i :

x il,t+1 = χ il (θ t+1 ) = χ il (θ i,t ) + γ t ⟨∇ χ il (θ i,t ), θ i,t+1 -θ i,t ⟩ + γ 2 t (θ i,t+1 -θ i,t ) ⊺ H il ( θi,t )(θ i,t+1 -θ i,t ), (B.14)
where H il ( θi,t ) is the Hessian of the latent map χ il at some convex combination θi,t of θ i,t and θ i,t+1 . Then, further expanding θ t+1 , we also get

x il,t+1 = x il,t -γ t ⟨∇ χ il (θ i,t ), P i,t V i,t ⟩ + γ 2 t (P i,t V i,t ) ⊺ H il ( θi,t )(P i,t V i,t ). (B.15)
Plugging the above expansion to E(θ t+1 ; x) for arbitrary state x we get

E t+1 = E(θ t+1 ; x) = 1 2 N i=1 di l=1 (x t+1 -x) 2 = 1 2 N i=1 di l=1 [x il,t -xil -γ t ⟨∇ χ il (θ i,t ), P i,t V i,t ⟩ + γ 2 t (P i,t V i,t ) ⊺ H il ( θi,t )(P i,t V i,t )] 2 = E t -γ t N i=1 di l=1 ⟨∇ χ il (θ i,t ), P i,t V i,t ⟩(x il,t -xil ) + γ 2 t ψ t = E t -γ t (J t P t V t ) ⊺ (x t -x) + γ 2 t ψ t , (B.16)
where the second-order term ψ t is given by the formula

ψ t = N i=1 di l=1 ⟨∇ χ il (θ i,t ), P i,t V i,t ⟩ 2 + N i=1 di l=1 (P i,t V i,t ) ⊺ H il ( θi,t )(P i,t V i,t )(x il,t -xil ) -γ t N i=1 di l=1 ⟨∇ χ il (θ i,t ), P i,t V i,t ⟩(P i,t V i,t ) ⊺ H il ( θi,t )(P i,t V i,t ) + γ 2 t N i=1 di l=1 [(P i,t V i,t ) ⊺ H il ( θi,t )(P i,t V i,t )] 2 .
(B.17)

For the second-order term, observe that by Assumption 2, we have that

[J ⊺ t J t ] + ⪯ 1 σ 2 min I. Using that fact, it follows that N i=1 di l=1 ⟨∇ χ il (θ i,t ), P i,t V i,t ⟩ 2 = (J t P t V t ) ⊺ J t P t V t = V ⊺ t [J ⊺ t J t ] + J ⊺ t J t [J ⊺ t J t ] + V t = V ⊺ t [J ⊺ t J t ] + V t ≤ 1 σ 2 min ∥V t ∥ 2 , (B.18)
Furthermore, since the representation maps χ i are β-Lipschitz smooth for some Lipschitz modulus β, we have that H i,l ( θi,t ) ⪯ βI for each player i and coordinate l. Consequently, we have that

(P i,t V i,t ) ⊺ H il ( θi,t )(P i,t V i,t ) ≤ βV ⊺ i,t P 2 i,t V i,t ≤ β σ 4 min ∥V i,t ∥ 2 ≤ β σ 4 min ∥V t ∥ 2 . (B.19)
Let D = diam(χ), then, by applying the Cauchy-Schwarz inequality, we also get that

ψ t ≤ 1 σ 2 min ∥V t ∥ 2 + dD √ β σ 2 min ∥V t ∥ + γ √ β σ 3 min ∥V t ∥ 2 + γ 2 dβ 2 σ 8 min ∥V t ∥ 2 , (B .20)
where γ = sup t=1,2,... γ t , and d = N i=1 d i . Finally, let us consider the first-order term of (B.16). Let v t = (∇ i ℓ i (θ t )) i∈N , and g t = g(x t ). Then, by definition, we also have that v t = J ⊺ t g t . Moreover, recall that, by construction, J t P t J ⊺ t = I. Consequently, we can write

(J t P t V t ) ⊺ (x t -x) = (J t P t v t ) ⊺ (x t -x) + [J t P t (V t -v t )] ⊺ (x t -x) = (J t P t J ⊺ t g t ) ⊺ (x t -x) + [J t P t (V t -J ⊺ t g t )] ⊺ (x t -x) = g ⊺ t (x t -x) + (J t P t V t -g t ) ⊺ (x t -x), (B.21)
which concludes our proof.

■

Appendix C. Proofs of Theorems 1-3

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

Theorem 1 (PHGD in hidden monotone games). Suppose that players run (PHGD) in a hidden monotone game with learning rate γ t ∝ 1/t 1/2 . Then, under Assumptions 1 and 2, the averaged process θt ∈ χ -1 t -1 t s=1 x s enjoys the equilibrium convergence rate

E[Gap( θt )] = O(log t/ √ t). (17)
Proof. Let θ 1 ∈ Θ be some arbitrary initialization of the algorithm, and let x ∈ X be some arbitrary profile of latent variables. Next, by Lemma 4, we have that for all t ≥ 1:

E t+1 ≤ E t -γ t ⟨g(x t ), x t -x⟩ + γ t ϕ t + γ 2 t ψ t ϕ t = (J(θ t )P(θ t )V t -g(x t )) ⊺ (x t -x) ψ t = κ∥V t ∥ 2 , for some κ > 0. (C.1)
Rearranging the terms, the above is equivalent to

γ t g(x t ), x t -x ≤ E t -E t+1 + γ t ϕ t + γ 2 t ψ t . (C.2)
Furthermore, by the monotonicity of g, we also have that g(x t ) -g(x), x t -x ≥ 0, and by combining the two, we get that for all t ≥ 1:

γ t g(x), x t -x ≤ γ t g(x t ), x t -x ≤ E t -E t+1 + γ t ϕ t + γ 2 t ψ t . (C.3)
Summing up the above terms in both sides of the inequality, we also get that

t s=1 γ s g(x), x s -x ≤ t s=1 E s -E s+1 + γ s ϕ s + γ 2 s ψ s = E 1 -E t+1 + t s=1 γ s ϕ s + t s=1 γ 2 s ψ s ≤ E 1 + t s=1 γ s ϕ s + t s=1 γ 2 s ψ s . (C.4)
Dividing all terms by γt := t s=1 γ s , also yields

g(x), xt -x = g(x), t s=1 γ s γt x s -x = t s=1 γ s γt g(x), x s -x ≤ E 1 γt + t s=1 γ s ϕ s γt + t s=1 γ 2 s ψ s γt , (C.5)
where xt := t s=1 γs γt x s is the time-average. Next, let us define the following auxiliary process that will assist us in further bounding the above expression:

y 1 = x 1 y t+1 = arg min x∈X ∥y t -γ t η t -x∥ for all t ≥ 2, (C.6)
where η t := J(θ t )P(θ t )V t -g(x t ) for all i ∈ N . Observe that

γ t ϕ t = γ t ⟨η t , x t -x⟩ = γ t ⟨η t , y t -x⟩ + γ t ⟨η t , x t -y t ⟩ for all t ≥ 1. (C.7)
Let us, first, focus on the former of the two terms. Notice that for all t ≥ 1, we can write

γ t ⟨η t , y t -x⟩ = γ t ⟨η t , y t+1 -x⟩ + γ t ⟨η t , y t -y t+1 ⟩. (C.8)
Furthermore, by the optimality of y t+1 , t ≥ 2, we have also have that

⟨y t+1 -y t + γ t η t , y t+1 -x⟩ ≤ 0. (C.9)
That is, γ t ⟨η t , y t+1 -x⟩ ≤ ⟨y t -y t+1 , y t+1 -x⟩.

Let us also recall a couple of useful quadratic identities, namely, we have that ∥y t -x∥ 2 = ∥y t -y t+1 + y t+1 -x∥ 2 = ∥y t -y t+1 ∥ 2 + 2⟨y t -y t+1 , y t+1 -x⟩ + ∥y t+1 -x∥ 2 , and

∥γ t η t -(y t -y t+1 )∥ 2 = γ 2 t ∥η t ∥ 2 -2γ t ⟨η t , y t -y t+1 ⟩ + ∥y t -y t+1 ∥ 2 .
Then, in conjunction with the above, we get that for all t ≥ 1:

γ t ⟨η t , y t -x⟩ = γ t ⟨η t , y t+1 -x⟩ + γ t ⟨η t , y t -y t+1 ⟩ ≤ ⟨y t -y t+1 , y t+1 -x⟩ + γ t ⟨η t , y t -y t+1 ⟩ = 1 2 ∥y t -x∥ 2 - 1 2 ∥y t+1 -x∥ 2 - 1 2 ∥γ t η t -(y t -y t+1 )∥ 2 + γ 2 t 2 ∥η t ∥ 2 ≤ 1 2 ∥y t -x∥ 2 - 1 2 ∥y t+1 -x∥ 2 + γ 2 t 2 ∥η t ∥ 2 (C.10)
Finally, summing both sides of the above inequalities, we also get that

t s=1 γ s ⟨η s , y s -x⟩ ≤ 1 2 t s=1 ∥y s -x∥ 2 - 1 2 t s=1 ∥y s+1 -x∥ 2 + 1 2 t s=1 γ 2 s ∥η s ∥ 2 = 1 2 ∥y 1 -x∥ 2 - 1 2 ∥y t+1 -x∥ 2 + 1 2 t s=1 γ 2 s ∥η s ∥ 2 ≤ 1 2 ∥y 1 -x∥ 2 + 1 2 t s=1 γ 2 s ∥η s ∥ 2 = 1 2 ∥x 1 -x∥ 2 + 1 2 t s=1 γ 2 s ∥η s ∥ 2 = E 1 + 1 2 t s=1 γ 2 s ∥η s ∥ 2 (C.11)
With the above established, let us reconsider the quantity g(x), xt -x . Specifically, due to the above derivations, we have that for all t ≥ 1:

g(x), xt -x ≤ E 1 γt + t s=1 γ s ϕ s γt + t s=1 γ 2 s ψ s γt = E 1 γt + 1 γt t s=1 γ t ⟨η t , y t -x⟩ + 1 γt t s=1 γ t ⟨η t , x t -y t ⟩ + t s=1 γ 2 s ψ s γt ≤ 3E 1 2γ t + 1 2γ t t s=1 γ 2 s ∥η s ∥ 2 + 1 γt t s=1 γ t ⟨η t , x t -y t ⟩ + κ γt t s=1 γ 2 s ∥V s ∥ 2 .
Considering the mean of supremum over x ∈ X of the LHS, we end up with

E sup x∈X g(x), xt -x ≤ 3E 1 2γ t + 1 2γ t t s=1 γ 2 s E[∥η s ∥ 2 ] + κ γt t s=1 γ 2 s E[∥V s ∥ 2 ] ≤ 3E 1 2γ t + M 2 γt t s=1 γ 2 s + κM 2 γt t s=1 γ 2 s = 3E 1 2γ t + (1 + κ) M 2 γt t s=1 γ 2 s = O t s=1 γ 2 s /γ t = O(log t/ √ t), (C.12)
where the last inequality is direct consequence of the bounded second moment of the stochastic gradient in Assumption 1 ■ Theorem 2 (PHGD in hidden strongly monotone games). Suppose that players run (PHGD) in a hidden µ-strongly monotone game with γ t = γ/t for some γ > µ. Then, under Assumptions 1 and 2, the induced sequence of play θ t ∈ Θ, t = 1, 2, . . . , enjoys the equilibrium convergence rate

E[Err(θ t )] = O(1/t). (19)
Proof. Let θ 1 ∈ Θ be some arbitrary initialization of the algorithm, and let γ ≥ 1 2µ be arbitrary. Since the map f is µ-strongly monotone, we have, by the definition of strong monotonicity, that g(x t ), x t -x * ≥ µ∥x -x * ∥ 2 for all x ∈ X .

(C.13)

Next, by Lemma 4, we have that for all t ≥ 1:

E t+1 ≤ E t -γ t ⟨g(x t ), x t -x⟩ + γ t ϕ t + γ 2 t ψ t ϕ t = (J(θ t )P(θ t )V t -g(x t )) ⊺ (x t -x) ψ t = κ∥V t ∥ 2 , for some κ > 0. (C.14)
That is

E t+1 ≤ E t -µγ t ∥x t -x * ∥ 2 2 + γ t ϕ t + γ 2 t ψ t = E t -2µγ t E t + γ t ϕ t + γ 2 t ψ t = (1 -2µγ t )E t + γ t ϕ t + γ 2 t ψ t .
(C.15)

Let H t = {θ s : s = 1, . . . , t} be the history of play up to iteration t. In expectation, it follows from the above that, for all t ≥ 1:

E[E t+1 ] ≤ (1 -2µγ t ) E[E t ] + γ t E[ϕ t ] + γ 2 t E[ψ t ] = (1 -2µγ t ) E[E t ] + γ t E E[ϕ t | H t ] + γ 2 t E E[ψ t | H t ] . (C.16)
Note that x t is H t -measurable; hence, we have that

E[ϕ t | H t ] = J(θ t )P(θ t ) E[V t | H t ] -g(x t ) ⊺ (x t -x) = J(θ t )P(θ t )v(θ t ) -g(x t ) ⊺ (x t -x) = J(θ t )P(θ t )J(θ t ) ⊺ g(x t ) -g(x t ) ⊺ (x t -x) = g(x t ) -g(x t ) ⊺ (x t -x) = 0.
(C.17) Furthermore, since, by Assumption 1, we have that

E[∥V t ∥ 2 | H t ] ≤ M 2 , it also holds that E[ψ t | H t ] = κ E[∥V t ∥ 2 | H t ] ≤ κM 2 (C.18)
Next, by some simple substitutions, we have

E[E t+1 ] ≤ (1 -2µγ t ) E[E t ] + κM 2 γ 2 t = 1 - 2µγ t E[E t ] + κM 2 γ 2 t 2 (C.19)
Finally, since γ > 1 2µ , we may apply Chung's lemma [START_REF] Chung | On a stochastic approximation method[END_REF] to get that, for all t ≥ 1:

E[E t ] ≤ κM 2 γ 2 2µγ -1 • 1 t + O 1 t 2 + 1 t 2µγ .
(C.20)

■ Theorem 3 (PHGD with full gradient feedback in hidden strongly monotone games). Suppose that players run (PHGD) in a hidden µ-strongly monotone game with full gradient feedback, and a suffciently small learning rate γ > 0. Then, under Assumptions 1 and 2, the induced sequence of play θ t ∈ Θ, t = 1, 2, . . . , converges to equilibrium at a geometric rate, i.e.,

Err(θ t ) = O(ρ t ) (20)
for some constant ρ ∈ (0, 1) that depends only on the primitives of Γ and the representation map χ.

Proof. Due to the absence of randomness, and therefore the absence of noise, Lemma 4 may be simplified to E t+1 ≤ E t -γ t g(x t ), x t -x * + κγ 2 t ∥v t ∥ 2 (C.21) for some constants κ > 0, where v t := (∇ i ℓ i (θ t )) i∈N .

Let β be the modulus of Lipschitz continuity of the gradients v t = J(θ t ) ⊺ g(x t ), and let µ 2 be the modulus of the strong monotonicity of g. Recall that, by Assumption 2, we have that the singular values of the Jacobian J(θ) of the representation map χ are bounded from above and below by σ max < ∞ and σ min > 0 respectively. Therefore, since v t is β-Lipschitz, it follows that

∥v t -v * ∥ 2 ≤ β 2 ∥θ t -θ * ∥ 2 ≤ β 2 σ 2 min ∥x t -x * ∥ 2 (C.22)
In conjunction to the above, we then also have

E t+1 ≤ E t -γ t g(x t ), x t -x * + κγ 2 t ∥v t ∥ 2 = E t -γ t g(x t ), x t -x * + κγ 2 t ∥v t -v * ∥ 2 ≤ E t -µγ t 1 2 ∥x t -x * ∥ 2 + κγ 2 t β 2 σ 2 min ∥x t -x * ∥ 2 = E t -µγ t E t + 2κγ 2 t β 2 σ 2 min E t = E t 1 -µγ t + 2κγ 2 t β 2 σ 2 min (C.23)
Restricting γ t such that

1 -µγ t + 2κγ 2 t β 2 σ 2 min < 1 ⇐⇒ γ t < σ 2 min µ 2κβ 2 , (C.24)
we finally have that, for the choice of γ t = γ := σ 2 min µ 8κβ 2 , it holds

E t = O(ρ t ) where ρ := 1 - 3σ 2 min µ 32κβ 2 < 1. (C.25)
Leveraging the equivalence of Err Θ (θ t ) and Err 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 Γ among two or more players N ≡ {1, . . . , N }. Each player i control a m-dimensional vector of control variables θ i ∈ R m , which they feed in an individual differentiable preconfigured MLP with two hidden layers that act as the player's representation map χ i : R m → X i . The dimensions of each layer of the MLPs vary among the different examples. However, the MLP's output x i = χ i (θ 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 G of Γ, is given by the "hidden" loss functions f i : X → R, i ∈ N . Each loss function f i is a regularized variation of the aforementioned normal-form game, tuned by some µ 2 -strongly convex regularizer

h µ (x) = µ 2 • i∈N ∥x i -x * i ∥ 2
, where x * is the normal-form game's unique equilibrium point. The modulus µ is a hyper-parameter, which we tune such that the vector field g(x) = ∇ xi f i (x) i∈N to be strongly monotone, and to avoid finite-precision numerical errors, which can potentially arise during the computation of x. 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 θ i are uni-dimensional, and are fed to each player's individual MLP given by the representation maps

χ i (θ i ) = sigmoid α (2) i • CeLU (α (1) i • θ i ) for all i = 1, 2, (D.1)
where α

i , α

∈ [-1, 1] are randomly chosen. Although the definition of the activation functions sigmoid : R → [0, 1], and CeLU : R → (-1, ∞) are widely common, we give them below for reference; that is:

sigmoid(x) = 1 + exp(-x) -1 (D.2a) CeLU (x) = 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 θ * = ⃗ 0, and to simplify the notation. Each of the MLP's output x i = χ(θ 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) • (2x 2 -1) + h 0.75 (x). (D.3)
The latent game's unique equilibrium, in this case, is at

x * = χ(θ * ) = ( 1 2 , 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 R 2 , and the space of latent variables [0, 1] 2 . In Fig. 7a 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 [START_REF] Beltratti | Neural networks for economic and financial modelling[END_REF]. A similar trajectory of the GD algorithm is depicted in Fig. 7b. 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 θ * , as opposed to the trajectory of GD, which exhibits an erratic behavior. In particular, as is depicted in the semi-log plot in Fig. 7c, 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 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 θ i ∈ R 5 of control variables, which, once again, they may feed their individual differentiable preconfigured MLP, whose output x i = χ i (θ 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:

χ i (θ i ) = softmax A (2) i × CeLU (A (1)
i × θ i ) for all i = 1, 2, (D.4) where the matrices A 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 * i = χ i (θ * i ) = ( 1 3 , 1 3 , 1 3 ), i = 1, 2: f 1 (x) = -f 2 (x) = -x ⊺ 1 Ax 2 + h 0.2 (x) where A =   0 -1 1 1 0 -1 -1 1 0   . (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. 8a 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. 8b. 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. 8c, 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. for some β ∈ (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:

f 1 (x) = -x ⊺ 1 Ax 2 + h 0.2 (x) f 2 (x) = -x ⊺ 2 B ⊺ x 1 + h 0.2 (x).
(D.8)

As in the hidden Rock-Paper-Scissors game, this game's unique equilibrium also lies in

x * i = χ i (θ * i ) = ( 1 3 , 1 3 , 1
3 ), i = 1, 2. A second difference is the small modulus, µ = 0.2, that we choose for the strongly-convex regularizer of this game. In Fig. 9 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. 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 ≥ 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 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 θ i ∈ R 5 , which feeds to an individual, differentiable, and preconfigured MLP. The MLP's output x i = χ i (θ 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 χ i : R 5 → [0, 1] are defined as

χ i (θ i ) = sigmoid α (2) i • CeLU (A (1)
i × θ i ) for all i = 1, 2, (D.9)

where A

(1) i ∈ [-0.85, 0.85] 4×5 , and α

(2) i ∈ [-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 sigmoid activation function. The activation function CeLU : R → (-1, ∞) is given as in (D.2b) and is applied pair-wise to the output of A and the latent game's unique equilibrium is at x * i = C N , i ∈ 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. 10. 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.

Figure 2 :

 2 Figure 2: Schematic representation of a game with a hidden / latent structure.

Example 2 . 1 .

 21 Consider a single-agent game (N = 1) where the objective is to minimize the non-convex function ℓ(θ) = |D| α=1 (sigmoid(θ α ) -s α ) 2 over a dataset D = {s α }. This problem can be recast as a hidden convex problem with f (x) = |D| α=1 (x α -s α ) 2 and χ(θ) = sigmoid(θ).

Figure 3 :

 3 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 (θ) = KL(logit(θ1, θ2)∥(1/2, 1/3, 1/6)) over Θ ≡ R 2 . In the subfigure to the right, we illustrate the hidden convex structure of the energy landscape, from the nonconvex sublevel sets of Θ to the latent space X ≡ {(x1, x2) ∈ R 2 ≥0 : x1 + x2 ≤ 1}.

Figure 4 :

 4 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 5 :

 5 Figure5: The evolution of the L 2 error function ErrX (χ(θ)) of (PHGD) and gradient descent (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.

Figure 6 :

 6 Figure 6: The distortion of a ball by J(θ).

  A trajectory of PHGD in a regularized game of Matching Pennies over the sub-levels of the energy function in[START_REF] Beltratti | Neural networks for economic and financial modelling[END_REF]. 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. A trajectory of GD in a regularized game of Matching Pennies over the sub-levels of the energy function in[START_REF] Beltratti | Neural networks for economic and financial modelling[END_REF]. 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. The distance of x to the latent game's equilibrium point x * = ( 1 2 , 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 trajectory of PHGD in a regularized game of Rock-Paper-Scissors as depicted in each player's 2dimensional simplex of latent variables. Notice that the trajectory converges to the latent game's equilibrium point x * . 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. The mean distance and confidence bound of x to the latent game's equilibrium point x * 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.

∈ [- 1 , 1 ]

 11 3×4 are random, and the activation function CeLU : R → (-1, ∞), given as in (D.2b), is applied pair-wise. The definition of softmax : R d → ∆ d-1 , where ∆ d-1 is the (d -1)-dimensional simplex is given, for reference, bysoftmax j (x) = exp(x j ) d k=1 exp(x k )for all j = 1, . . . , d. (D.5)

Figure 9 :

 9 Figure9: The mean distance and confidence bounds of x to the latent game's equilibrium point x * 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.

Figure 10 :

 10 Figure10: The mean distance and confidence bounds of x to the latent game's equilibrium point x * 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.

( 1 )

 1 i × θ i . The loss functions of this game follow the standard variant's definitions, namely, we have thatf i (x) = S + x i G -S + P i̸ =j x i ≥ C (B -G) + h 0.5 (x) for all i ∈ N , (D.10)

The separability assumption also rules out the logit representation exp(θ iα ) β exp(θ iβ ) that is standard when the latent structure expresses mixed strategies in a finite game.

In the above, TC X (x) denotes the tangent cone to X at x, that is, the closure of the set of all rays emanating from x and intersecting X in at least one other point.

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