Year: 2021

Abstract:
Game-theoretic formulations in machine learning have recently risen in prominence, whereby entire modeling paradigms are best captured as zero-sum games. Despite their popularity, however, their dynamics are still poorly understood. This lack of theory is often substantiated with painful empirical observations of volatile training dynamics and even divergence. Such results highlight the need to develop an appropriate theory with convergence guarantees that are powerful enough to inform practice. This paper studies the generalized Gradient Descent-Ascent (GDA) flow in a large class of non-convex non-concave Zero-Sum games dubbed Hidden Convex-Concave games, a class of games that includes GANs. We focus on two specific geometries: a novel geometry induced by the hidden convex-concave structure that we call the hidden mapping geometry and the Fisher information geometry. For the hidden mapping geometry, we prove global convergence under mild assumptions. In the case of Fisher information geometry, we provide a complete picture of the dynamics in an interesting special setting of team competition via invariant function analysis.

heading: 1 INTRODUCTION
text: Min-max optimization has found extensive applications in modern Machine Learning (ML) and Deep Learning. Popular application settings include Generative Adversarial Networks (GANs) (Goodfellow et al., 2014), adversarial training (Madry et al., 2018), and multi-agent reinforcement learning (Silver et al., 2017). In all of these cases, a pair of networks is typically trained towards finding an approximate equilibrium of a highly non-convex non-concave problem. However, such settings go beyond classical and well-known results in game theory for which equilibria only exist in more restrictive settings, i.e., convex-concave games (Sion et al., 1958). Unfortunately, there is no parallel guarantee if the payoff is not convex-concave, and all these applications are indeed based upon non-convex non-concave games. Even worse, many negative results occur when dealing with such payoffs: global or local minimax may not exist (Jin et al., 2020), and even if they exist, there is, in general, no “reasonable algorithm”1 that can globally converge to any meaningful notion of local optimum (Letcher, 2021; Hsieh et al., 2020). In order to overcome these negative results, we analyze a specific restricted class of non-convex non-concave games called Hidden Convex-Concave (HCC) games (Flokas et al., 2020; Gidel et al., 2021; Flokas et al., 2021) that include many Machine Learning applications such as GANs (Goodfellow et al., 2014), Adversarial Example Games (AEG) (Bose et al., 2020), or Minimax Estimation of Conditional Moment (Dikkala et al., 2020).
Our contributions. In the setting of HCC games, our analysis tackles unique challenges not captured l standard in the convex-concave games setting. As a way to overcome those challenges, we propose a new type of dynamics, dubbed Natural Hidden Gradient dynamics (NHG), and we prove its convergence to stationary points of the HCC game. Critically, our convergence results are global, i.e., we do not make any assumptions about initial conditions, e.g., that the initial points belong to some local neighborhood. This novel algorithm is, in fact, inspired by the generalization of gradient flows in different Banach spaces than the standard Euclidean one. Arguably, the most well-known non-Euclidean gradient is the natural gradient flow induced by the Fisher information matrix, which enjoys deep connections to the Replicator Dynamics (RD). Thus, a natural question emerges: Can we have similar convergence guarantees for RD? In that regard, we provide a complete picture of the
1see (Letcher, 2021, Definition 5) for a definition of “reasonable algorithm”
resulting dynamics in a setting of team competition via invariant function analysis. Specifically, the flow of the dynamics is shown to be reduced to a competition between two generalized gradients, one for each team. We show that the behavior of the dynamics in this setting is constrained by a maximal number of invariant functions, which, combined with the actual geometry of the available strategies, shows that the system can either converge or cycle. These results showcase, both, the importance of adapting the “algorithmic geometry” to the application and the data at hand, as well as the unexplored effects of feasibility constraints on the complexity of well-known game dynamics.

heading: 2 RELATED WORK
text: Despite the popularity of deep learning applications involving non-convex non-concave games, our understanding of their optimization dynamics and the nature of their solution concepts is still preliminary. However, this space has already witnessed a few important early works that focus on identifying new solution concepts. These solution concepts—which are also broadly applicable in general min-max games—include (local/differential) Nash equilibria (Adolphs et al., 2019; Mazumdar & Ratliff, 2019), (local/differential) Stackelberg equilibria (Fiez et al., 2020; Wang et al., 2020), local minmax (Daskalakis & Panageas, 2018), local robust points (Zhang et al., 2020), and approximate minimax theorems (Jin et al., 2019; Gidel et al., 2021). Numerous solutions concepts such as cycles (Vlatakis-Gkaragkounis et al., 2019), chaotic behavior (Cheung & Piliouras, 2019; Cheung & Tao, 2021), and computational issues (Daskalakis et al., 2021) indicate that solving min-max games, in general, might involve challenging and complex behavior.
Many algorithms have been proposed to solve restricted classes of non-convex non-concave games such as Polyak-Łojasiewicz games (Nouiehed et al., 2019; Yang et al., 2020), nonconvex-concave games (Lin et al., 2020; Ostrovskii et al., 2021; Yang et al., 2020; Kong & Monteiro, 2021), as well as classes of games inspired by variational inequalities (Mertikopoulos et al., 2019; Diakonikolas et al., 2021; Lee & Kim, 2021). However, even though they are significant advances in the understanding of non-convex non-concave game dynamics, such classes of games may not encompass games where the players are parameterized neural networks such as GANs.
While convergence in GANs has been a topic of exploration (Kodali et al., 2017; Heusel et al., 2017; Mescheder et al., 2018; Gemp & Mahadevan, 2018; Li et al., 2018; Hsieh et al., 2019; Cao & Guo, 2020), its hidden convex-concave structure has not been exploited before, and there were no theoretical global convergence guarantees in a general setting up to this date. In particular, Hsieh et al. (2019) use a lifting trick and proceed in solving a relaxation of the problem in the distribution space, while in our work we work entirely in the parameter space. With this respect, we consider Flokas et al. (2021), and Gemp & Mahadevan (2018) as the closest related works. On the one hand, in Gemp & Mahadevan (2018), the authors propose crossing-the-curl, a second-order technique, and provide global convergence guarantees for the Wasserstein Linear Quadratic GAN (W-LQGAN). While the W-LQGANs is a class of non-convex non-concave GANs it remains far from the GAN formulation used in practice where the discriminator and the generator are neural networks. On the other hand, the idea of Hidden Convex-Concave (HCC) games was first proposed by Flokas et al. (2021) and Gidel et al. (2021). While Flokas et al. (2021) study the Gradient Descent-Ascent (GDA) dynamics in the HCC setting, their work relies on hard-to-verify safety conditions. Our global convergence results without hard-to-test assumptions on initialization are first of their kind, to the best of knowledge.

heading: 3 PRELIMINARIES

heading: 3.1 HIDDEN CONVEX-CONCAVE GAMES
text: Many game-theoretic applications in machine learning often involve a specific structure where the models’ payoff is a convex-concave function (e.g., minimizing Jensen-Shannon-Divergence when training GANs). In order to model this specific structure, we propose the following definition of Hidden Convex-Concave (HCC) games where intuitively, the game’s payoff is convex-concave while the actions are parametrized by non-convex mappings.
Definition 1 (Hidden Convex-Concave game). A Hidden Convex-Concave game comprises a collection of payoff (Lx,x′)x,x′∈Rd , a distribution p, and two parametrized mappings, F : RM×Rd → R,
and G : RN × Rd′ → R, such that the minimax game of interest is
min θ∈RM max φ∈RN
Ψ(θ,φ) where Ψ(θ,φ) = L(Fθ, Gφ) := E(x,x′)∼p[Lx,x′(Fθ(x), Gφ(x′))] . (1)
In this setting, while we do not expect Ψ(θ,φ) to be convex-concave, we assume the function L : F×G→ R to be convex-concave where F and G are, respectively, convex subsets of {F : Rd → R} and {G : Rp → R} .2 We extended Flokas et al. (2021)’s definition to now be able to include most minimax machine learning applications such as GANs or AEG.
Example 1 (Hidden Matching Pennies (HMP) games). Let us consider p, q ∈ [0, 1] the probabilities of picking HEADS for the first and the second player, respectively, in a Matching Pennies game with payoff matrix A ∈ R2×2, where Ai,j = 1 if i = j; −1, otherwise. Then the payoff of this game is defined via
Lx,x′(p, q) :=
{ (1− 2p)(1− 2q), if (p, q) ∈ [0, 1]2 (Player 1 matches the pennies)
0, otherwise . (2)
Now, let us consider any mappings F : RM×Rd → [0, 1] andG : RN×Rd → [0, 1], such that their output does not depend on the d-dimensional input, i.e., Fθ(x) = f(θ), and Gφ(x) = g(φ), ∀x ∈ Rd. The payoff Ψ(θ,φ) = L(Fθ, Gφ) := E[Lx,x′(Fθ(x), Gφ(x′))] = (1 − 2f(θ))(1 − 2g(φ)) defines a HCC game.
In this example, the two agents play the typical bilinear game of Matching Pennies. However, they do not act on it directly (i.e., choose randomized actions to apply, e.g., the probability of playing HEADS), instead they choose the input parameters θ, and φ, which are fed into functions f , and g, respectively, whose outputs define the probability of playing HEADS for each agent.
Example 2 (GANs). A Generative Adversarial Network (GAN) is a minimax game where the first player, i.e., generator, aims at learning a distribution pθ similar to a reference data distribution pdata. In practice, the reference data distribution is taken to be the empirical data distribution. Conversely, the second player, usually called the discriminator or critic, Dφ, tries to distinguish the distributions of pθ and pdata. The payoff, Ψ , of this game is defined as:
Ψ(θ,φ) = Ex∼pdata [logDφ(x)] + Ex∼pθ [log(1−Dφ(x))] . (3)
Assuming that pdata and pθ have a density with respect to Lebesgue measure, 3 and that pdata has full support, we can consider the distribution p such that p(x,x′) = pdata(x) if x = x′; 0, otherwise, and set Lx,x(p′, D) := logD+ p ′
pdata(x) log(1−D), and Lx,x′(p′, D) = 0 , ∀x 6= x′. Thus Lx,x′ is
convex-concave for any x ∈ Rd. We have that Ψ(θ,φ) = E(x,x′)∼p[Lx,x′(pθ(x), Dφ(x′))], which is a HCC game.
A GAN formulates the generative modeling task as finding a Nash equilibrium of a minimax game. The generator of a GAN is defined as a function that aims to produce realistic data samples by transforming samples drawn from a fixed noise distribution, e.g.,N (0, Id). Here, we notice that the GAN payoff is convex (actually linear) with respect to the density of the generated distribution. An alternative formulation of a GAN is a Wasserstein GAN (WGAN) (Arjovsky et al., 2017). It turns out that this GAN is also a HCC game.
Example 3 (WGANs). A Wasserstein GAN is a constrained minimax game, where the second player Dφ is a 1-Lipchitz function and where the payoff is
Ψ(θ,φ) = Ex∼pdata [Dφ(x)]− Ex∼pθ [Dφ(x)] . (4)
Similarly, as in Example 2, the WGAN payoff can be shown to be a HCC game.
As the last class of examples of HCC games we present the Adversarial Example Games (AEG) (Bose et al., 2020).
2One can always assume F and G to be convex sets by considering their convex hulls. 3We make this assumption for simplicity. We can consider Radon–Nikodym derivatives for the general case.
Example 4 (AEG). An Adversarial Example Game is a minimax game between a generatorGθ and a classifier f . Given samples (x, y) ∼ pdata, the generatorGθ aims at finding adversarial examples x′ such that ‖x − x′‖∞ ≤ and that x′ is not classified as y by f , thus generating a distribution pθ. Overall, the payoff of this game is
Ψ(θ,φ) = −E(x′,y)∼pθ [`(fφ(x ′), y)] for (x′, y) ∼ pθ ⇐⇒ x′ = Gθ(x), (x, y) ∼ pdata, (5)
and where ` is the cross-entropy loss and Gθ is such that ‖x−Gθ(x)‖ ≤ , ∀x. By using a similar construction as in Example 2, we can show that (5) is a HCC game with respect to pθ and fφ.
Throughout this work, we make the assumption that the minimax problem induced by L admits a solution: Assumption 1. The HCC game defined by (1) admits a Nash equilibrium, (F ∗, G∗), i.e.,
min F∈F max G∈G L(F,G) = max G∈G min F∈F
L(F,G) = L(F ∗, G∗) . (6)
Such an assumption is relatively mild since, by Sion et al. (1958), it holds when the set F is compact (since, by definition, it is convex). Here we do not assume that this solution is achievable, i.e., we do not assume that there exists θ∗ and φ∗ such that (Fθ∗ , Gφ∗) = (F ∗, G∗). Such sufficient conditions for the existence of a Nash equilibrium of L : F × G → R are discussed in detail in Gidel et al. (2021, Prop. 1), e.g., Assumption 1 holds if the parameters θ and φ are bounded. From a high-level perspective, this assumption is analogous to the existential assumption of a optimizer in non-convex optimization. In that sense, we use the equilibrium (F ∗, G∗) as a target to build a Lyapunov function for a natural gradient flow.

heading: 3.2 NATURAL GRADIENT FLOW
text: In this section, we introduce the notion of a natural gradient flow (Amari, 1985; 1998). Let us consider a function f : S→ R and a class of symmetric positive definite matrices (Pθ)θ∈S 0 that we will refer to as metric tensors. The natural gradient flow is the flow given by the steepest descent direction (Ollivier et al., 2017) with respect to the geometry induced by the matrices Pθ,
θ̇ = −P−1θ ∇f(θ) . (7)
WhenPθ = I , we consider the standard Euclidean geometry and recover the standard gradient flow. One celebrated example of a natural gradient in machine learning is the natural gradient induced by the Fisher information matrix (Amari, 1998; Martens, 2020). Example 5 (The natural gradient flow of the Fisher information matrix). Let us consider P (X) the space of probability distributions on a set X ⊆ R with the metric induced by the Kullback–Leibler (KL) divergence. Then the natural gradient flow of the Fisher information matrix is given by
θ̇ = −F−1θ ∇f(θ) where Fθ := −Ex∼pθ [∇ 2 θ log pθ(x)], pθ ∈ P (X) . (8)
Moreover, if n := |X| = dim S is finite, and if pθ = θ, the flow (8) is the natural gradient flow of the Shahshahani metric (Shahshahani, 1979) induced by the metric tensors
Sθ := diag( 1 θ1 , . . . , 1θn ) . (9)

heading: 3.3 CONNECTIONS BETWEEN REPLICATOR DYNAMICS AND GRADIENT FLOWS
text: The Replicator Dynamics (RD) are standard dynamics used in Evolutionary Game Theory and learning in games. It is, arguably, the most widely used model of evolutionary selection with multiple applications in economics, biology, and other fields. Interestingly, RD enjoys a close connection to gradient flows (see Sigmund (1984); Hofbauer et al. (1998); Harper (2009); Mertikopoulos & Sandholm (2018)). Specifically, in the case of a symmetric and linear fitness landscape, the gradient induced by the Shahshahani metric of the mean fitness is a special case of RD. Such a landscape can be formally represented by a Potential game. A Potential game is a n-player game G = (n, S := [m1] × . . . × [mn], u : S → Rn), with payoff function u, characterized by the existence of a potential function Φ : S→ R that satisfies
Φ(si, s−i)− Φ(s′i, s−i) = ui(si, s−i)− ui(s′i, s−i) ∀i ∈ [n] . (10)
The connection between the Potential games and the gradient flows induced by the Shahshahani metric can be formally shown by a generalization of Hofbauer et al. (1998)’s lemma in the space of a Cartesian product of simplices. Proposition 1. The Replicator Dynamics of a potential game G with potential function Φ is an (extended) Shahshahani gradient in int(∆m1 × . . .×∆mn) having potential Ψ(θ) := Esi∼θi
i∈[n] [Φ(s)].
It follows that, in the context of potential games, RD are a gradient flow with respect to a very specific geometry. In the next section, we consider a different geometry. One that is induced by the HCC structure, and which we leverage to obtain a new natural gradient flow that we call Natural Hidden Gradient flow (NGH).

heading: 3.4 THE NATURAL HIDDEN GRADIENT FLOW FOR HCC GAMES
text: In HCC games, we assume Ψ(θ,φ) = L(Fθ, Gφ) (see Definition 1), and, therefore, since the entities that characterize a solution to the minimax problem are the mappings Fθ and Gφ instead of their parametrizations, θ and φ, respectively, a natural geometry for consideration is the one defined by the L2 distance in the space of F × G. Formally, let θ and θ′ be two parameterizations for F (similarly, for G). The L2 distance between Fθ and Fθ′ is ‖Fθ′ − Fθ‖2 := Ex∼px(Fθ′(x)− Fθ(x))2 (11) where px is the first marginal (second for G) of p. We can then derive the metric tensors that define this geometry. Proposition 2 (Metric tensors of the model space). For any θ, we have that ‖Fθ+δθ − Fθ‖2 = 〈δθ,Aθδθ〉 + o(‖δθ‖2) where Aθ := E[∇θFθ(x)∇θFθ(x)ᵀ] . (12)
Consequently, Aθ defines a metric on the parameter space in which the “distance” between two values, θ, and θ′, corresponds to the L2 distance between Fθ and Fθ′ . We can, thus, construct the natural gradient flow given by this metric. Proposition 3 (Natural Hidden Gradient dynamics). The flow induced by the geometry (11) is
θ̇ = −A†θE(x,x′)∼p[∇θLx,x′(Fθ(x), Gφ(x ′))] φ̇ = B†φE(x,x′)∼p[∇φLx,x′(Fθ(x), Gφ(x ′))]
(D1)
where Aθ := Ex∼px [∇θFθ(x)∇θFθ(x)ᵀ] and Bφ := Ex′∼px′ [∇φGφ(x)∇φGφ(x) ᵀ] and C†
denotes the pseudo-inverse of a matrix C.

heading: 4 CONVERGENCE OF THE NATURAL HIDDEN GRADIENT FLOW
text: In this section, we propose a new type of dynamics, dubbed Natural Hidden Gradient dynamics (NHG), and in the following two theorems, we prove their convergence in HCC games and GANs. At the heart of our analysis lies the construction of a proper Lyapunov function that measures the distance from the game’s equilibrium point. By proving that the Lyapunov function is proper, i.e., monotonic, we will prove our proposed dynamics are approaching a Nash Equilibrium, i.e., converging to a stationary point.

heading: 4.1 WARM-UP: A SINGLE DATAPOINT
text: In this section, as a warm-up, we will consider the single datapoint case. In this case, the payoff that defines the HCC game, can be written as
Ψ(θ,φ) = L(Fθ(x), Gφ(x ′)) (13)
where L : R × R → R is convex-concave (see Example 1). In this case, since the mapping Fθ and Gφ are evaluated at a single point, one can simplify the notation and consider Fθ(x) = f(θ) and Gφ(x′) = g(φ) where f : RM → R and g : RN → R are real-valued mappings that do not depend on an input x or x′. This situation is already non-trivial since, as illustrated in Example 1, it can correspond to a non-convex non-concave parametrization of the Matching Pennies game. Let us recall that we want to use a Nash equilibrium (f∗, g∗) of this game as a target. In order to solve this game we consider the Natural gradient of the metric defined in Proposition 2.
Proposition 4. In the uni-dimensional case, the Natural Hidden Gradient flow D1 takes the form of
θ̇ = −∇θL(f(θ),g(φ))‖∇θf(θ)‖2 and φ̇ = ∇φL(f(θ),g(φ)) ‖∇φg(φ)‖2 . (D2)
Using Proposition 4, it is relatively straightforward to show that the distance to the optimum is a Lyapunov function for the Natural Hidden Gradient flow. Theorem 1. Let Ψ be the payoff of an HCC game defined as in (13) and consider the game dynamics in (D2). Then, the quantity
V (θ,φ) := 12 (f(θ)− f ∗)2 + 12 (g(φ)− g ∗)2 (14)
is a Lyapunov function, i.e., it is positive, non-increasing, and null if and only if it evaluated at a game solution. Moreover, if L is strictly convex-concave, we have that V is decreasing and that any limit point (θ,φ) satisfies∇θL(f(θ), g(φ)) = ∇φL(f(θ), g(φ)) = 0.
In order to see this, one can compute the time derivative of V . After some elementary computations, it follows V̇ (θ,φ) = −(f(θ) − f∗)∂L(f,g(φ))∂f ∣∣∣ f=f(θ) + (g(φ) − g∗)∂L(f(θ),g)∂g ∣∣∣ g=g(φ) , and, thus, by the convex-concavity of L, we have that V̇ ≤ 0. However, generalizing this theorem to HCC games with non-constant mappings (with respect to x) is non-trivial since we drastically used the simplicity of the mappings (in Proposition 4) to simplify the expression of the flow. In the next section, we propose to extend our convergence analysis to finite sum HCC games.

heading: 4.2 THE GENERAL FINITE SUM CASE
text: In this section, we consider a finite-sum version of the HCC games as they appear in Definition 1. In this case, the payoff is defined as
Ψ(θ,φ) := 1nm ∑ (i,j)∈[n]×[m] Li,j(Fθ(xi), Gφ(x ′ j)) =: L((Fθ(xi))i∈[n], (Gφ(x ′ j))j∈[m]) , (15)
where the function L : Rn × Rm → R is assumed to be convex-concave. We note Li,j := Lxi,x′j for compactness. Let us recall that we assumed the existence of a Nash equilibrium (F ∗, G∗) for the minimax problem (Assumption 1). In this situation, the Natural gradient defined in Proposition 3 has the following form:
θ̇ = − A † θ
nm ∑ (i,j)∈[n]×[m] ∇θLi,j(Fθ(xi), Gφ(x′j)), φ̇ = B†φ nm ∑ (i,j)∈[n]×[m] ∇φLi,j(Fθ(xi), Gφ(x′j)) , (D3)
whereAθ := 1n ∑n i=1∇θFθ(xi)∇θFθ(xi)ᵀ andBφ := 1 m ∑m j=1∇φGφ(x′j)∇φGφ(x′j)ᵀ.
We will generalize the Lyapunov function considered in the uni-dimensional case (14). The idea is to consider the L2 distance between (Fθ(xi), Gφ(x′j))i,j and (F ∗(xi), G ∗(x′j))i,j as our Lyapunov function V . However, in order to prove our result, we will need the following technical assumption. Assumption 2. For any θ ∈ RM andφ ∈ RN , we have that the families of vectors (∇θFθ(xi))i∈[n] and (∇φGφ(x′j))j∈[m] are linearly independent.
This assumption is relatively mild since it can be insured by an arbitrarily small perturbation of the considered vectors. In practice, it suggests regularizing the matrices Aθ and Bφ by adding · Id which is a standard way to stabilize methods requiring matrix inversions. Theorem 2. Let Ψ be the payoff of a finite-sum HCC game given by (15) and consider the game dynamics in (D3). Under Assumption 1, Assumption 2, and that d > n we have that the quantity
V (θ,φ) := 1
2n n∑ i=1 (Fθ(xi)− F ∗(xi))2 + 1 2m m∑ j=1 (Gφ(x ′ j)−G∗(x′j))2 (16)
is a Lyapunov function, i.e., is positive, non-increasing and null if and only if evaluated at a game solution. Moreover, if L is strictly convex-concave, V is decreasing as long as (θ,φ) 6= (θ∗,φ∗) and if L is a µ-strongly convex-concave function we have that V is decreasing exponentially as V (θ,φ) = V (θ0,φ0) exp(−µt).
The proofs of Theorem 1 and Theorem 2 can be found in §A.3.

heading: 5 CHARACTERIZATIONS OF REPLICATOR DYNAMICS IN HCC GAMES
text: In this section, we consider a specific instance of HMP games (cf. Example 1), dubbed 2-Team HMP games or the XOR-XOR games. Although the possibility of cycling orbits for RD in such games was established before (Piliouras & Schulman, 2018), in this section, we show stronger results. Specifically, as we prove in subsection 5.2, by enforcing restrictions to the game’s parameters, it is possible to affect the game’s outcome, e.g., we may deviate from the well-known cyclic behavior in the unrestricted setting, and moreover, enforce divergence away from the game’s original equilibrium and convergence to novel fixed points. We completely characterize the geometry of possible limit cycles in such a restricted setting by exploiting intuitions developed via the connection between RD and the Shahshahani information geometry. Specifically, we show the dynamics are controlled by invariant functions, which correspond to weighted sums of the cross-entropy of the current mixed strategies of opposing members relative to the uniform, equilibrium strategies (20). For the complete proofs of this section, we refer the interested reader to §A.4.

heading: 5.1 2-TEAM HIDDEN MATCHING PENNIES GAMES
text: We introduce the 2-Team HMP game, G = (n := n1 + n2,S := {0, 1}n, u : S → Rn), between n1 + n2 members divided into two teams. The first team, team 1, consists of n1 members, while the second team, team 2, consists of n2 members. The payoff function u for a strategy profile s := (s1, s2) ∈ S is given by
uk,i(s) := (−1)k−1 nk (1− 2 · 1XOR(s1)=XOR(s2)), k ∈ [2], i ∈ [nk] . (17)
where XOR(sk) = 1 if |{sk,i | sk,i = 1}| is odd, and 0, otherwise. Given a mixed-strategy profile, (θ,1− θ), θ := (θk)k∈[2] ∈ [0, 1]n, the expected payoff of the i-th member of team k is given by
Ψk,i(θ) := Esk,i∼Ber(θk,i) k∈[2], i∈[nk]
[uk,i(s)] = (−1)k−1 nk (1− 2f(θ1))(1− 2g(θ2)) (18)
where f(θ1) := Es1∼Ber(θ1)[XOR(s1)] and g(θ2) := Es2∼Ber(θ2)[XOR(s2)]. Notice that, since each member of a given team aims at maximizing the same payoff, G is a Hidden Matching Pennies game (Example 1) with hidden mappings f(θ1), and g(θ2),
min θ2 max θ1 Ψ(θ1,θ2) := n1∑ i=1 Ψ1,i(θ) = (1− 2f(θ1))(1− 2g(θ2)) . (19)
It is not difficult to prove that the RD exhibit cyclic behavior in this setting. The following theorem provides a fine-grained characterization of the dynamics of the HCC game in (19) since we know that the trajectories will lie on the intersection of level sets of the invariant functions identified by the following theorem: Theorem 3. Consider the Replicator Dynamics of G. Given any interior initial condition, the resulting orbit is a cycle that satisfies the following n1 + n2 − 1 independent invariant functions:
Vi1,i2(θ) = 2∑ k=1 nk[log(θk,ik) + log(1− θk,ik)], ik ∈ [nk], k ∈ [2] . (20)

heading: 5.2 REPLICATOR DYNAMICS OF HIDDEN MATCHING PENNIES IN A RESTRICTED SETTING
text: Next, we introduce restrictions in the range of each member’s strategies in G such that θk,i ∈ Sk,i := [αk,i, βk,i] ⊆ [0, 1], ∀k ∈ [2], i ∈ [nk]. These restrictions reflect in RD as halts, i.e., θ̇k,i = 0, every time the strategy of the i-th member of the k-th team exceeds those bounds. To ease our notation, we let Sk := {i ∈ [nk] | 12 ∈ Sk,i}, k ∈ [2] denote all the members of the k-th team for which ( 1 2 , 1 2 ) is an allowed mixed strategy, and, to simplify this part of the analysis, we also make the following mild assumption on the initialization of the dynamics: Assumption 3. For all k ∈ [2] and i ∈ [nk], θk,i(0) ∈ Sk,i ⊂ (0, 1).
A significant observation is that for any mixed-strategy profile (θ,1 − θ), θ := (θ1,θ2) ∈ [0, 1]n, if there exists some ik ∈ [nk], ∀k ∈ [2] such that θik = 12 , then θ is an equilibrium point; in fact, it
is not difficult to see that these are the only interior equilibrium points of G, which implies that an interior equilibrium point is reachable if and only if Sk 6= ∅, ∀k ∈ [2]. In our first result, we prove that if the Nash Equilibrium of the unrestricted case is not reachable by both teams due to the enforced constraints, then the dynamics are bound to converge to a point which only depends on those restrictions. Theorem 4. Under Assumption 3, if Sk = ∅, ∀k ∈ [2], the restricted RD of G converge to
θ∗1,i = { α1,i, if β1,i < 12 β1,i, otherwise i ∈ [n1]
θ∗2,i = { β2,i, if β2,i < 12 α2,i, otherwise
i ∈ [n2]︸ ︷︷ ︸ if |S| is even
or θ∗1,i =
{ β1,i, if β1,i < 12 α1,i, otherwise i ∈ [n1]
θ∗2,i = { α2,i, if β2,i < 12 β2,i, otherwise
i ∈ [n2]︸ ︷︷ ︸ if |S| is odd
(21)
where S := {(k, i) | k ∈ [2], i ∈ [nk], αk,i > 12}.
The key idea behind this result is that at any given time t ≥ 0, the direction of a strategy θk,i(t) only depends on whether |S|, the total number of members who can access the uniform strategy, is odd or even. Thus, we can decouple the evolution of the dynamics of each of the members and analyze its behavior separately. On the other hand, if an equilibrium point of the unrestricted setting is reachable by both teams, i.e., Sk 6= ∅, ∀k ∈ [2], then the dynamics converge to an invariant set whose degrees of freedom depend on the number of members who have access to the uniform strategy, ( 12 , 1 2 ). Theorem 5. Under Assumption 3, if Sk 6= ∅, ∀k ∈ [2], then the restricted RD of G converge to an invariant set defined by the |S1|+ |S2|−1 independent invariant functions, Vi1,i2(θ), ik ∈ Sk, ∀k ∈ [2], where Vi1,i2(θ) is given as in (20).
One can prove this result by partitioning the time based on the set of members that have halted. The analysis of Vi1,i2(θ) in each time-partition is almost trivial, and the result follows by a continuity argument on Vi1,i2(θ). For completeness, we remark that the intermediate case where ∃k, k′ ∈ [2] with Sk = ∅, and Sk′ 6= ∅, still leads to the convergence of RD, though the actual point of convergence depends on the initial conditions θ(0). However, its analysis merely combines elements of the other two cases without providing any interesting insight, and, therefore, we omit it. These results depict how the behavior of RD depends on the parameter space of the game. Notably, we show that if no equilibrium point is feasible, the RD converge to a point described entirely by the strategy space restrictions. On the other hand, if an equilibrium point is feasible, we prove the existence of a maximal number of invariant functions, with close connections to the KL divergence. The latter does not merely show that the RD cycle in this setting, but that they actually converge to an invariant set with specific degrees of freedom, and which we characterize. For exemplary parameterizations that visualize the behavior of RD in such restricted settings, please see §B.1.

heading: 6 EXPERIMENTAL RESULTS
text: NHG dynamics: The multi-dimensional case. As a first experiment, we consider a hidden convexconcave objective
Ψ(θ,φ) = L(Fθ, Gφ) := F ᵀ θMGφ + λ 2 (‖Fθ − 1 3‖ 2 − ‖Gφ − 13‖ 2) ,
where M is the payoff matrix of the Rock-Paper-Scissors game (see e.g. Gidel et al. (2021)). We note Fθ(xi) = [Fθ]i, i ∈ [3], and 13 , i.e., the uniform distribution, is the game’s equilibrium. The mappings F and G are 2-layer MLP with 130 parameters and GELU non-linearities (Hendrycks & Gimpel, 2016). In Figure 1, we depict a comparison between the performance of GDA and NHG dynamics on the task of solving minθ maxφ Ψ(θ,φ). We remark, our NHG dynamics converge smoothly (Figure 1 (Right)), compared to GDA (Figure 1 (Center)), which fail to converge. The value of the Lyapunov function of the game described is depicted in (Figure 1 (Left)).
NHG dynamics: GANs. For our second experiment, we implement the NHG dynamics to train a GAN. We consider a synthetic experiment to learn a sine wave sampled uniformly from 0 to π with 1024 observations. Regarding the GAN, we consider a Flow-GAN architecture where our generator,
G, is a Real NVP consisting of 8 coupling layers (Dinh et al., 2017; 2014), and the discriminator is a 4-layer MLP with 256-128-64-1 output features. We adapt K-FAC (Martens & Grosse) as an approximator to compute NHG, with a learning rate of 10−4, selected using the standard parameter optimizer package Optuna (Akiba et al., 2019). We used gradient clipping with gradient clip to a maximum norm of 1 on, both the discriminator and the generator, to stabilize the optimization.
As observed in (Figure 2 (Center)), by iteration 200, the GAN optimized using K-FAC learns the true sinusoid almost perfectly and converges to a better Wasserstein-1 score than the conventional GDA (Figure 2 (Right)). The experiments reveal that our approach provides good performance and convergence guarantees. However, we observe instabilities during training, and lack of convergence in certain instances, which stay in line with the empirical observations regarding the difficulty of GAN training, and the instability of matrix inversions close to singularities. We remark that this experiment goes slightly beyond the theoretical results: while in theory, we assume a natural gradient flow on a “full-batch”, our experiments are based on discrete stochastic updates, and an approximation of the pseudo-inverses of the matrices (see (D1)) using K-FAC. Thus, this experiment acts as a proof-of-concept rather than a large-scale comparison between NHG and GDA. The details of both experiments can be found within the source-code files included with this work.

heading: 7 DISCUSSION
text: In this work, we proposed a novel version of Gradient Descent Ascent dynamics in Hidden ConvexConcave games, a subset of non-convex non-concave games. In this class of games, which includes GANs, the utility is convex-concave in the function space. Still, training happens in the parameter space, where the mappings between the input and output are non-convex non-concave functions. Our analysis of the convergence of the new type of dynamics, Natural Hidden Gradient (NHG) dynamics, uses ideas from Game Theory and Dynamical Systems. We proved global convergence guarantees for NHG in HCC games to local stationary points via Lyapunov function analysis in the finite-sum case. To the best of our knowledge, such a non-local convergence result in HCC games and GAN-like settings, is one of the first of its kind. We explored the dynamics of gradient flows induced by different Banach spaces (e.g., the Fischer information geometry) that led to the discovery of Lyapunov functions suited to these geometries. This work shows a deep connection between the natural gradients and the Lyapunov function analysis of complex non-convex non-concave game dynamics that pave the way to a better understanding of learning in games. We show that we can obtain promising experimental results on practical GANs using NHG and standard gradient approximation techniques such as KFAC. However, we are aware that the current formulation of NHG may be challenging to scale up to large neural networks because of the tensor pseudo-inversion step that is part of the dynamics. Investigating experimentally novel versions of Gradient Descent Ascent dynamics with a richer set of experiments and developing techniques to scale our results for large neural networks is a natural direction for our future work.
STATEMENT OF REPRODUCIBILITY
We made sure to provide sufficient details to ensure the reproducibility of our results. The complete proofs of the theoretical results can be found in §A, and all the assumptions have been stated and are referenced in each statement. We provide details regarding the experimental results, such as code language, required libraries, and parametrization to execute and reproduce the experiments in section 6 and §B. We also include the source code files and the necessary input files in the supplementary material that accompanies this work.

heading: A OMITTED PROOFS
text: A.1 OMITTED PROOFS OF SECTION 3.2
Proposition A.1. Let us consider P (X) the space of probability distributions on a set X ⊆ R with the metric induced by the Kullback–Leibler (KL) divergence. If n := |X| = dimS, and pθ := θ ∈ P (X), then the natural gradient flow of the Fisher information matrix in (8) is the natural gradient flow of the Shahshahani metric induced by the metric tensors in (9).
Proof. All we need to show is that Fθ = Sθ, ∀θ ∈ S. Simply, note that ∀i, j ∈ [n]:
(Fθ)i,j = −Ex∼pθ [ ∂2 log pθ(x) ∂θi∂θj ] = − ∑ x∈X ∂2 log pθ(x) ∂θi∂θj pθ(x)
= − ∑ x∈X ∂2 log θx ∂θi∂θj θx = ∑ x∈X δx,iδx,j θx = δi,j θi = (Sθ)i,j .
A.2 OMITTED PROOFS OF SECTION 3.3
Let G = (n, S := [m1]× . . .× [mn], u : S→ Rn) be a n-player (exact) potential game with payoff function u and potential Φ : S → R, and let M := ∆m1 × . . . ×∆mn be the mixed-strategy space of G. We are going to consider the RD of G in intM = int ∆m1 × . . . × int ∆mn as given in the following proposition.
Proposition A.2. The Replicator Dynamics of G in intM are given by the following dynamical system of equations:
θ̇i,j := θi,j(Esk∼θk k∈[n] [ui(sj , s−i)]− Esk∼θk k∈[n] [ui(s)]) = θi,j
( ∂Ψ(θ)
∂θi,j −Ψ(θ)
) (D4)
where Ψ(θ) := Esi∼θi i∈[n] [Φ(s)] is the the expected potential function of the game.
Proof. First note that
∂Ψ(θ) ∂θi,j = ∑ s ∏ k 6=i θk,skΦ(s) ∂θi,si ∂θi,j = ∑ s ∏ k 6=i θk,skΦ(s)δj,si
= ∑ s−i ∏ k 6=i θk,skΦ(j, s−i) = Esi∼θi i∈[n] [Φ(j, s−i)] .
From which follows that
θ̇i,j = θi,j(Esk∼θk k∈[n] [ui(j, s−i)− ui(s)]) = θi,j(Esk∼θk k∈[n] [Φ(j, s−i)− Φ(s)])
= θi,j
( ∂Ψ(θ)
∂θi,j −Ψ(θ)
) .
Next, let us consider a point θ ∈ intM, and note that the following proposition holds:
Proposition A.3. For any θ ∈ intM = int ∆m1 × . . . × int ∆mn , the tangent plane of intM at θ is
Tθ(intM) = {µ ∈ Rm1 × . . .× Rmn | ∑ j µi,j = 0} . (22)
Proof. We first note that intM is an open-subset of the surface D := {µ ∈ Rm1 × . . . × Rmn | Ui(µ) = 1}, where Ui(µ) = ∑ j µi,j = 1; hence, Tθ(intM) = Tθ D, up to isomorphism. Let r(t) be a smooth curve in D with r(0) = θ. Then, by definition, Ui(r(t)) = 1 for all i, and, by differentiating with respect to t, we have
∇Ui(r(t)) · d
dt r(t) =
d dt Ui(r(t)) = d dt 1 = 0 .
However, ddtr(t) is tangent to D for all t; hence, d dtr(t) ∣∣∣ t=0 ∈ Tθ D. It follows that ∇Ui(r(0)) = ∇Ui(θ) is normal to Tθ D for all i, and ,thus, we have
Tθ D ⊆ {µ ∈ Rm1 × . . .× Rmn | 〈∇Ui(θ),µ〉 = 0} = {µ ∈ Rm1 × . . .× Rmn | ∑ j µi,j = 0} . Finally, notice that dim{µ ∈ Rm1 × . . . × Rmn | ∑ j µi,j = 0} = dimD, which implies the proposition.
Proposition 1. The Replicator Dynamics of a potential game G with potential function Φ is an (extended) Shahshahani gradient in int(∆m1 × . . .×∆mn) having potential Ψ(θ) := Esi∼θi
i∈[n] [Φ(s)].
Proof. Let θ ∈ intM := int ∆m1 × . . .× int ∆mn . Then for every ξ ∈ Tθ(intM) we have:
〈θ̇, ξ〉θ = ∑ 1
θi,j θ̇i,jξi,j = ∑(∂Ψ(θ) ∂θi,j −Ψ(θ) ) ξi,j = ∑ ∂Ψ(θ) ∂θi,j ξi,j −Ψ(θ) ∑ ξi,j
= ∑ ∂Ψ(θ)
∂θi,j ξi,j = ∇Ψ(θ) · ξ .
Hence, by definition, we have that ∇Ψ(θ) = θ̇, where the Del operator is defined with respect to the Shahshahani metric, which implies the lemma.
Now, let us consider a different class of games, which we define as 2-Team Zero-Sum games.
Definition 2. A 2-Team Zero-Sum game, G = (m := m1 +m2,S := [n1] × . . . × [nm], u : S → Rm), is a game between m players with strategy-space S whose utility function, u, satisfies the following:
ui(s) =
{ 1 m1
Φ(s), if i ∈ [m1] − 1m2 Φ(s), otherwise
∀s ∈ S (23)
for some function Φ : S→ R.
We are going to, collectively, refer to the first m1 players of a 2-Team Zero-Sum game, G = (m := m1 + m2,S := [n1] × . . . × [nm], u : S → Rm), as team 1 and to the rest of them as team 2. Notice that if we consider each team as a single player, then the two teams are playing a 2-Player Zero-Sum game, G′ = (2,S′ := S1 × S2, u′ : S′ → R2) where S1 = [n1] × . . . × [nm1 ], S2 = [nm1+1 × . . .× nm], and the utility function u′k is the total utility of the corresponding team k, i.e. ∀s ∈ S we have
u′1(s) = m1∑ i=1 1 m1 Φ(s) = Φ(s) and u′2(s) = − m∑ i=m1+1 1 m2 Φ(s) = −Φ(s) . (24)
Note that, by definition, the 2-Team Hidden Matching Pennies game (see section 5) is a a 2-Team Zero-Sum game. Let us consider the Replicator Dynamics of G given by the following dynamical system of equations:
θ̇i,j := θi,j(Esk∼θk [ui(j, s−i)]− Esk∼θk [ui(s)])
=  1 m1 θi,jEsk∼θk [Φ(j, s−i)− Φ(s)], if i ∈ [m1]
− 1 m2 θi,jEsk∼θk [Φ(j, s−i)− Φ(s)], otherwise
(D5)
where, as before, we can rewrite (D5) in terms of Ψ(x) := ESk∼xk [Φ(S)] as
θ̇i,j =  1 m1 θi,j( ∂Ψ(θ) ∂θi,j −Ψ(θ)), if i ∈ [m1]
− 1 m2 θi,j( ∂Ψ(θ) ∂θi,j −Ψ(θ)), otherwise .
(D6)
Notice that the Replicator equations of each team are similar to the Replicator equations of a Potential game. In fact, it’s not difficult to prove the following lemma. Lemma 1. Let G = (m := m1 + m2,S := [n1] × . . . × [nm], u : S → Rm) be a 2-Team Zero-Sum game. If we assume the strategies of team 2 to be time-invariant, then the Replicator Dynamics of G, given by (D5) (or (D6), equivalently), is a (m1-scaled) Shahshahani gradient in intM := int ∆n1 × . . .× int ∆nm with potential Ψ′1(θ) = Ψ◦Π1(θ) where Ψ(θ) := Esi∼θi [Φ(s)], and Π1 : intM→ intM is the natural projection
Πk,i,j(θ) =
{ θi,j , if i in team k
0, otherwise . (25)
Likewise, if we assume the strategies of team 1 to be time-invariant, then the Replicator Dynamics of G is a (m2-scaled) Shahshahani gradient in intM with potential Ψ′2 = −Ψ ◦Π2(θ).
Proof. This proof is similar to the proof of Proposition 1, but we need to perform the correct projection before applying the definition of a gradient flow. Let θ ∈ intM. Without any loss of the generality, let us assume that the strategies of team 2 are time-invariant, i.e., θ̇i,j = 0 for all i ≥ m1. Then, for every ξ ∈ Tθ(intM) we have
〈θ̇, ξ〉θ = ∑ m1
θi,j θ̇i,jξi,j = m1∑ i=1 ∑ j m1 eθi,j 1 m1 θi,j ( ∂Ψ(θ) ∂θi,j −Ψ(θ) ) ξi,j
= m1∑ i=1 ∑ j ∂Ψ(θ) ∂θi,j ξi,j −Ψ(θ) m1∑ i=1 ∑ j ξij = m1∑ i=1 ∑ j ∂Ψ(θ) ∂θi,j ξi,j
= ∑ ∂Ψ(Π1(θ))
∂θi,j ξi,j = ∇Ψ′1(θ) · ξ .
Hence, by definition, we have that dΨ′1(θ) = θ̇ [, which implies the theorem.
Proposition 2 (Metric tensors of the model space). For any θ, we have that
‖Fθ+δθ − Fθ‖2 = 〈δθ,Aθδθ〉 + o(‖δθ‖2) where Aθ := E[∇θFθ(x)∇θFθ(x)ᵀ] . (12)
Proof. To prove that we use the fact that for all x,
Fθ+δθ(x) = Fθ(x) + 〈∇Fθ(x), δθ〉 + o(δθ) .
Then we have that
‖Fθ+δθ − Fθ‖2 = Ex∼px [(〈∇Fθ(x), δθ〉 + o(δθ))2] = Ex∼px [(∇Fθ(x)ᵀδθ)2] + o(δθ)2
= Ex∼px [δθᵀ∇Fθ(x)∇Fθ(x)ᵀδθ] + o(δθ)2 = δθᵀEx∼px [∇Fθ(x)∇Fθ(x)ᵀ]δθ + o(δθ)2;
which concludes the proof.
Proposition 3 (Natural Hidden Gradient dynamics). The flow induced by the geometry (11) is
θ̇ = −A†θE(x,x′)∼p[∇θLx,x′(Fθ(x), Gφ(x ′))] φ̇ = B†φE(x,x′)∼p[∇φLx,x′(Fθ(x), Gφ(x ′))]
(D7)
where Aθ := Ex∼px [∇θFθ(x)∇θFθ(x)ᵀ] and Bφ := Ex′∼px′ [∇φGφ(x)∇φGφ(x) ᵀ] and C†
denotes the pseudo-inverse of a matrix C.
Proof. The proposition directly follows from Proposition 2 applied to the definition of (7). However, in order to convey more intuition we could use the definition that the natural gradient flow of the objective function f induced by the distance d if
θ̇ = arg min δθ lim λ→0
1 λ f(θ + λδθ) + 1 2λ2 d2(Fθ+λδθ, Fθ) .
By using the L2 distance and noting that when λ→ 0 we have f(θ+λδθ) = f(θ)+λ∇f(θ)ᵀδθ+ o(λ) and 12λ2 ‖Fθ+λδθ − Fθ‖
2 = 12 〈δθ,Aθδθ〉 + o(1) we have that the RHS of the equation above is
arg min δθ ∇f(θ)ᵀδθ + 1 2 〈δθ,Aθδθ〉;
which is minimized for δθ = −A†θ∇f(θ).
A.3 OMITTED PROOFS OF SECTION 4
Proposition 4. In the uni-dimensional case, the Natural Hidden Gradient flow D1 takes the form of
θ̇ = −∇θL(f(θ),g(φ))‖∇θf(θ)‖2 and φ̇ = ∇φL(f(θ),g(φ)) ‖∇φg(φ)‖2 . (D8)
Proof. For the uni-dimensional case, Aθ = ∇f(θ)∇f(θ)ᵀ is a rank-1 matrix that projects any vector in the direction of ∇f(θ) and scales it by ‖∇f(θ)‖2. Thus, by definition of the pseudoinverse, we have that for any vector u ∈ Rd:
A†θu = ∇f(θ)〈u,∇f(θ)〉 ‖∇f(θ)‖4 .
Finally, notice that
∇θL(f(θ), g(φ)) = ∇f(θ) ∂(f, g(φ))
∂f
∣∣∣ f=f(θ) ,
which leads to the stated proposition.
Theorem 1. Let Ψ be the payoff of an HCC game defined as in (13) and consider the game dynamics in (D2). Then, the quantity
V (θ,φ) := 12 (f(θ)− f ∗)2 + 12 (g(φ)− g ∗)2 (14) is a Lyapunov function, i.e., it is positive, non-increasing, and null if and only if it evaluated at a game solution. Moreover, if L is strictly convex-concave, we have that V is decreasing and that any limit point (θ,φ) satisfies∇θL(f(θ), g(φ)) = ∇φL(f(θ), g(φ)) = 0.
Proof. By taking the time derivative of V (θ,φ), we get
V̇ (θ,φ) = − (∇f(θ)(f(θ)− f∗))ᵀ ∇f(θ) ‖∇f(θ)‖2 ∂L(f, g(φ)) ∂f ∣∣∣ f=f(θ)
+ (∇g(φ)(g(φ)− g∗))ᵀ ∇g(φ) ‖∇g(φ)‖2 ∂L(f(θ), g) ∂g ∣∣∣ g=g(φ)
= −(f(θ)− f∗)∂L(f, g(φ) ∂f ∣∣∣ f=f(θ) + (g(φ)− g∗)∂L(f(θ), g) ∂g ∣∣∣ g=g(φ) ≤ 0
where the last inequality holds because L is convex-concave. Specifically, let L : RM × RN → R be any differentiable convex-concave function with saddle point (f∗, g∗), then we have, respectively
−〈f − f∗,∇fL(f, g)〉 ≤ L(f∗, g)− L(f, g) and 〈g − g∗,∇gL(f, g)〉 ≤ L(f, g)− L(f, g∗) .
By adding the two inequalities, we get
− 〈f − f∗,∇fL(f, g)〉 + 〈g − g∗,∇gL(f, g)〉 ≤ L(f∗, g)− L(f, g∗) ≤ 0 (26)
where the last inequality holds because (f∗, g∗) is a saddle point. Hence, by definition, L is a Lyapunov function.
Finally, when L is strictly convex-concave, if there exists a limit point of (θ,φ) that is not a point where ∇θL(f(θ), g(φ)) = 0 and ∇φL(f(θ), g(φ)) = 0 then by strict convex-concavity we get that V should decrease by a “significant enough amount” to create a contradiction with the fact that V does converge.
Next, before proving the general case of Theorem 1, we’ll have to prove the following lemma: Lemma 2. Let (ui)i∈[n] be a linearly independent family of vectors on Rd. Then, the matrix
A := n∑ i=1 uiu ᵀ i . (27)
is the Gram matrix of the family (ui)i∈[n] and and we have that 〈ui,A†uj〉 = δi,j , ∀i, j ∈ [n].
Proof. Let us introduce the matrix P := [u1, . . . ,un]ᵀ; we can easily verify that A = P ᵀA. Let P = UDV ᵀ be the SVD decomposition of P and, thus, A† = V (DᵀD)†V ᵀ where DᵀD is a diagonal matrix. Then, we have
〈ui,A†uk〉 = 〈P ᵀe(i),A†P ᵀe(j)〉 = 〈V DᵀUᵀe(i),V (DᵀD)†V ᵀV DᵀUᵀe(j)〉 = 〈e(i),UD(DᵀD)†DᵀUᵀe(j)〉 .
To conclude this lemma, we just need to notice that the matrix D is a matrix with non-zero entries on the diagonal and, since we assumed that the vectors in (ui)i∈[n] are linearly independent, we have that Di,i > 0, ∀i ∈ [n]. Thus, by a direct computation, we get that
D(DᵀD)†Dᵀ = In
which leads to 〈ui,A†ui〉 = δi,j .
Theorem 2. Let Ψ be the payoff of a finite-sum HCC game given by (15) and consider the game dynamics in (D3). Under Assumption 1, Assumption 2, and that d > n we have that the quantity
V (θ,φ) := 1
2n n∑ i=1 (Fθ(xi)− F ∗(xi))2 + 1 2m m∑ j=1 (Gφ(x ′ j)−G∗(x′j))2 (16)
is a Lyapunov function, i.e., is positive, non-increasing and null if and only if evaluated at a game solution. Moreover, if L is strictly convex-concave, V is decreasing as long as (θ,φ) 6= (θ∗,φ∗) and if L is a µ-strongly convex-concave function we have that V is decreasing exponentially as V (θ,φ) = V (θ0,φ0) exp(−µt).
Proof. Similarly as the proof of Theorem 1, we consider the time derivative of V (θ,φ). For compactness, we are going to simplify the notation slightly by setting Fi := Fθ(xi), Gj := Gφ(x′j), F ∗i := F ∗(xi), G∗j := G ∗(x′j), and Li,j := Lxi,x′j .
V̇ (θ,φ) = 1
n n∑ i=1 (Fi − F ∗i )〈∇θFi, θ̇〉 + 1 m m∑ j=1 (Gj −G∗j )〈∇φGj , φ̇〉
= − 1 n2m n∑ i=1 (Fi − F ∗i )〈∇θFi,A † θ ∑ (j,k)∈[m]×[n] ∇θLk,j(Fk, Gj)〉
+ 1
nm2 m∑ j=1 (Gj −G∗j )〈∇φGj ,B † φ ∑ (k,i)∈[m]×[n] ∇φLi,k(Fi, Gk)〉
= − 1 n2m n∑ i=1 (Fi − F ∗i ) ∑ (j,k)∈[m]×[n] 〈∇θFi,A†θ∇θFk〉 ∂Lk,j(F,Gj) ∂F ∣∣∣ F=Fk
+ 1
nm2 m∑ j=1 (Gj −G∗j ) ∑ (k,i)∈[m]×[n] 〈∇φGj ,B†φ∇φGk〉 ∂Li,k(Fi, G) ∂G ∣∣∣ G=Gk .
From Lemma 2 we have that 〈∇θFi,A†θ∇θFk〉 = n · δi,k, ∀i ∈ [n], k ∈ [m], and that 〈∇φGj ,B†φ∇φFk〉 = m · δj,k. Hence, it follows
V̇ (θ,φ) = − 1 nm ∑ i∈[n] j∈[m] (Fi − F ∗i ) ∂Li,j(F,Gj) ∂F ∣∣∣ F=Fi + 1 nm ∑ i∈[n] j∈[m] (Gj −G∗j ) ∂Li,j(Fi, G) ∂G ∣∣∣ G=Gj
= −〈∂FL(F,G), F − F ∗〉 + 〈∂GL(F,G), G−G∗〉
where [∂FL(F,G)](i,j) := ∂Li,j(F,Gj)
∂F
∣∣∣ F=Fi , ∂GL(F,G)](i,j) := ∂Li,j(Fi,G) ∂G ∣∣∣ G=Gj , and F , G, F ∗,
and G∗ are indexed by (i, j), as well (while repeating vector elements as necessarily). Thus, using the same reasoning as in Theorem 1, it follows that if L is convex-concave we have that V is nonincreasing, and, if L is strictly convex-concave, V̇ (θ,φ) < 0 whenever (θ,φ) 6= (θ∗,φ∗). Finally, if L is µ-strongly convex-concave, we have by definition that
−〈∂FL(F,G), F − F ∗〉 + 〈∂GL(F,G), G−G∗〉 ≥ −µ(‖F − F ∗‖2 + ‖G−G∗‖2) = −µV (θ,φ)
Thus we conclude that V (θ,φ) ≤ V (θ0,φ0) exp(−µt).
A.4 OMITTED PROOFS OF SECTION 5
In order to prove (18), and (D9) we are, first, going to prove the following useful lemma:
Lemma 3. Let hθ(i) := Exj∼Ber(θj)[XOR(x1, . . . , xi)] where θ ∈ [0, 1]n, and i ≤ n. Then the following equality holds:
1− 2hθ(i) = i∏
j=1
(1− 2θj) . (28)
Proof. The easiest way to prove this relationship is by induction on n ∈ N. For n = 1, we only need to verify that (28) holds for i = 1. Indeed, we have,
1− 2hθ(1) = 1− 2Ex∼Ber(θ1)[XOR(x1)] = 1− 2Ex∼Ber(θ1)[x1] = 1− 2θ1 .
Next, let us assume that Lemma 3 holds for some n = n′ ∈ N. We are going to prove that Lemma 3 also holds for n = n′ + 1, and this comes down in proving that (28) holds for i = n′ + 1:
1− 2hθ(n′ + 1) = 1− 2E[XOR(x1, . . . , xn′+1)] = 1− 2E[E[XOR(x1, . . . , xn′+1) | xn′+1]] = 1− 2(θn′+1E[XOR(x1, . . . , xn′ , 1)] + (1− θn′+1)E[XOR(x1, . . . , xn′ , 0)]) = 1− 2(θn′+1E[1−XOR(x1, . . . , xn′)] + (1− θn′+1)E[XOR(x1, . . . , xn′)])
= 1− 2(θn′+1(1− hθ(n′)]) + (1− θn′+1)hθ(n′)) = (1− 2θn′+1)(1− 2hθ(n′))
= (1− 2θn′+1) n′∏ j=1 (1− 2θj) = n′+1∏ j=1 (1− 2θj) .
And we that, the proof by induction is complete.
Proposition A.4. Let G = (n := n1+n2,S := {0, 1}n, u : S→ Rn) be a 2-Team Hidden Matching Pennies game with payoff function given by (17). Then, the expected payoff of the i-th member of team k is given by (18).
Proof. The first equality follows, trivially, from the definition of Φ(s). All is left to prove is that −Esk,i∼Ber(θk,i)[Φ(s)] = (1 − 2Es1,i∼Ber(θ1,i)[XOR(s1)])(1 − 2Es2,i∼Ber(θ2,i)[XOR(s2)]) for all θ ∈ [0, 1]n. We define, xk = XOR(sk), k ∈ [2]. Note that, by definition, xk ∼ Ber(pk), where pk := Esk,i∼Ber(θk,i)[XOR(sk)]; hence,
Esk,i∼Ber(θk,i)[Φ(s)] = Esk,i∼Ber(θk,i)[1− 2 · 1XOR(s1)=XOR(s2)] = Exk∼Ber(pk)[1− 2 · 1x1=x2 ] = Exk∼Ber(pk)[(1− 2 XOR(x))] = 1− 2hp(2) = (1− 2p1)(1− 2p2) = (1− 2Es1,i∼Ber(θ1,i)[XOR(s1)])(1− 2Es2,i∼Ber(θ2,i)[XOR(s2)]) .
Proposition A.5. Let G = (n := n1+n2,S := {0, 1}n, u : S→ Rn) be a 2-Team Hidden Matching Pennies game with payoff function given by (17). Then, the RD of G is given by the dynamical system of equations:
θ̇k,i = (−1)k−1 2
nk θk,i(1− θk,i) ∏ k′∈[2] ∏ i′∈[nk′ ]
(k,i) 6=(k′,i′)
(1− 2θk,i) . (D9)
Proof. From (18) we have that
Esk,i∼Ber(θk,i)[uk,i(s)]
= (−1)k−1 1 nk (1− 2Es1,i∼Ber(θ1,i)[XOR(s1)])(1− 2Es2,i∼Ber(θ2,i)[XOR(s2)])
= (−1)k−1 1 nk (1− 2hθ1(n1)(1− 2hθ2(n2) = (−1)k−1 1 nk ∏ k∈[2] ∏ i∈[nk] (1− 2θk,i) .
Then, by the definition of RD of G, we get
θ̇k,i := θk,iEsk,i∼Ber(θk,i)[uk,i(0, s−k,i)− uk,i(s)]
= (−1)k−1 1 nk θk,i  ∏ k′∈[2] ∏ i′∈[nk′ ]
(k,i)6=(k′,i′)
(1− 2θk,i)− ∏ k′∈[2] ∏ i′∈[nk′ ] (1− 2θk,i)  = (−1)k−1 2
nk θk,i(1− θk,i) ∏ k′∈[2] ∏ i′∈[nk′ ]
(k,i)6=(k′,i′)
(1− 2θk,i) .
Theorem 3. Consider the Replicator Dynamics of G. Given any interior initial condition, the resulting orbit is a cycle that satisfies the following n1 + n2 − 1 independent invariant functions:
Vi1,i2(θ) = 2∑ k=1 nk[log(θk,ik) + log(1− θk,ik)], ik ∈ [nk], k ∈ [2] . (20)
Proof. For all k ∈ [2] and i ∈ [nk], we have
∂Vi1i2(θ)
∂θk,i =  nk(1− 2θk,i) θk,i(1− θk,i) , if (k, i) ∈ {(k′, ik′) | k′ ∈ [2]}
0, otherwise .
Subsequently, we have
V̇i1i2(θ) = 〈∇θVi1i2(θ), θ̇〉 = 2 ∏ k∈[2] ∏ i∈[nk] (1− 2θk,i)− 2 ∏ k∈[2] ∏ i∈[nk] (1− 2θk,i) = 0 .
Observe that the above imply the existence of n1 + n2 − 1 independent invariant functions. Hence, the dynamics converge to a limit set of a single degree of freedom, i.e., a cycle.
Proposition A.6. Let G = (n := n1 + n2,S := {0, 1}n, u : S → Rn) be a 2-Team Hidden Matching Pennies game with payoff function given by (17). Given a mixed-strategy profile (θ, 1 − θ), θ := (θ1,θ2) ∈ (0, 1)n, (θ, 1− θ) is an equilibrium of G if and only if ∃ik, ∀k ∈ [2] such that θk,ik = 1 2 , ∀k ∈ [2].
Proof. We know that G is equivalent to a Hidden Matching Pennies game (Example 1) with payoff Ψ(θ) = (1 − 2f(θ1))(1 − 2g(θ2)), where f(θ1) := Es1,i∼Ber(θ1,i)[XOR(s1)], and g(θ2) := Es2,i∼Ber(θ2,i)[XOR(s2)] are its hidden mappings. The only fully mixed-Nash equilibrium of this Hidden Matching Pennies game is (f(θ1), g(θ2)) = ( 12 , 1 2 ); hence, a mixed-strategy profile (θ, 1− θ) is a fully mixed-Nash equilibrium of G, if and only if f(θ1) = g(θ2) = 12 . From f(θ1) = 1 2 we get
Es1,i∼Ber(θ1,i)[XOR(s1)] = 1
2 ⇐⇒ 1− 2hθ1(n1) = 0 ⇐⇒ n1∏ i=1 (1− 2θ1,i) = 0
⇐⇒ ∃i1 ∈ [n1] : θ1,i = 1
2 .
We remark that, for any ik ∈ [nk], k ∈ [2],
Vi1,i2(θ) := 2∑ k=1 nk[log(θk,ik) + log(1− θk,ik)] = 2∑ k=1 2 · nk[ 12 log(θk,ik) + 1 2 log(1− θk,ik)]
= 2∑ k=1 2 · nkH(Ber( 12 ),Ber(θk,ik))
where H(p, q) is the cross-entropy of a distribution q relative to a distribution p. In other words, every one of the invariant functions in (20) is the weighted sum of the cross entropy of two mixedstrategies (of the i1-th member of team 1, and the i2-th member of team 2) relative to the uniform strategy. That is, each invariant function measures (up to a constant) the Kullback–Leibler divergence of two opposing members to an actual equilibrium of the game. Notice that, for any equilibrium point of the Hidden Matching Pennies game, there exists at least on such pair of opposing members i1 ∈ [n1], and i2 ∈ [n2] such that
DKL(Ber( 1 2 ) ‖ Ber(θ1,i1)) = DKL(Ber( 1 2 ) ‖ Ber(θ2,i2)) = 0 .
For the rest of this section we are going to consider the RD of a 2-Team Hidden Matching Pennies game G = (n := n1 + n2,S := {0, 1}n, u : S→ Rn) in a restricted setting, given by the following dynamical system of equations:
θ̇k,i = 
0, if θk,i /∈ Sk,i 0, if θk,i = αk,i and (−1)kDk,i(θ) < 0 0, if θk,i = βk,i and (−1)kDk,i(θ) > 0
(−1)k−1 2 nk θk,i(1− θk,i)Dk,i(θ), otherwise
(D10)
where Dk,i(θ) := ∏ k′∈[2] ∏ j∈[nk′ ]
(k′,j)6=(k,i) (1 − 2θk′,j), k ∈ [2] i ∈ [nk], and where we restrict each
mixed-strategy profile (θ, 1 − θ) such that θk,i ∈ Sk,i := [αk,i, βk,i], ∀k ∈ [2], i ∈ [nk]. We let Ω be an orbit defined by this RD whose initial conditions satisfy Assumption 3. This assumption serves a dual purpose. To begin with, it ensures that any orbit is initialized inside the restricted parameter space that is defined by Sk,i. Furthermore, it makes sure the initial strategy profile has full support, i.e., (θk,i(0), 1−θk,i(0)) is an interior point of the simplex for all k ∈ [2], and i ∈ [nk]. It is easy to see that any dimension of the strategy space initially without support is impossible to be updated by the RD in (D10); hence, it would be irrelevant for the analysis. Before we proceed, we are going to introduce a couple of useful lemmas. Lemma 4. ∀k ∈ [2], and i ∈ [nk] if θk,i(0) ∈ Sk,i, then θk,i(t) ∈ Sk,i, ∀t ≥ 0.
Proof. Let k ∈ [2] and i ∈ [nk] such that θk,i(0) ∈ Sk,i =⇒ αk,i ≤ θk,i(0) ≤ βk,i. We are going to prove our case by abduction.
Suppose ∃t0 > 0 such that θk,i(t0) /∈ Sk,i and, without any loss of the generality, let us assume that θk,i(t0) > βk,i. We let T = {t ∈ (0, t0) | θk,i(t) = βk,i and we note that, since θk,i(0) ≤ βk,i, it is implied by the continuity of θk,i(t) (Equation D10) and by the Intermediate Value Theorem that T 6= ∅. Finally we define tmax = max(T). Let us now consider the value of θk,i(t) for some t ∈ (tmax, t0) and observe that if θk,i(t) = βk,i we have
t ∈ T =⇒ t ≤ max(T) = tmax =⇒ tmax < t ≤ tmax .
This contradiction implies that θk,i(t) 6= βk,i. However, if θk,i(t) < βk,i, the Intermediate Value Theorem, once again, implies ∃t′ ∈ (t, t0) such that θk,i(t′) = βk,i, which as before implies tmax < t′ ≤ tmax. Hence, it must be the case that, for all t ∈ (tmax, t0):
θk,i(t) > βk,i (D10) =⇒ θ̇k,i(t) = 0 .
However, by applying the Mean Value Theorem, if follows ∃t′ ∈ (tmax, t0) such that
θ̇k,i(t) = θk,i(0)− θk,i(tmax) t0 − tmax = θk,i(0)− βk,i t0 − tmax > 0 ,
which is once again a contradiction.
Lemma 5. Under Assumption 3, if Sk = ∅, ∀k ∈ [2] then the following hold:
(a) Ψ1,i1(θ(t))Ψ2,i2(θ(t)) < 0 for all ik ∈ [nk], k ∈ [2], and t ≥ 0.
(b) Ψk,ik(θ(t)) preserves sign for all ik ∈ [nk], k ∈ [2].
Proof. Since Sk = ∅ for all k ∈ [2], it follows, by definition, that
1 2 /∈ Sk,i, ∀k ∈ [2], i ∈ [nk]
Furthermore, by Assumption 3, we have that θk,i(0) ∈ Sk,i for all k ∈ [2], i ∈ [nk]. Hence, it follows, by Lemma 4, that ∀k ∈ [2], i ∈ [nk], and t ≥ 0:
θk,i(t) ∈ Sk,i =⇒ θk,i(t) 6= 1
2 =⇒ 1− 2θk,i(t) 6= 0 .
Then, by Equation 18, we have
Ψk,i(θ(t)) = (−1)k−1
nk (1− 2Es1,j∼Ber(θ1,j)[XOR(s1)])(1− 2Es2,j∼Ber(θ2,j)[XOR(s2)])
= (−1)k−1
nk (1− 2hθ1)(1− 2hθ2) =
(−1)k−1
nk
n1∏ j=1 (1− 2θ1,j) n2∏ j=1 (1− 2θ2,j)
= (−1)k−1
nk
2∏ k′=1 nk′∏ j=1 (1− 2θk′,j(t)) 6= 0 .
That implies (a). We can now condition on Ψk,i(θ(0)). Since Ψk,i(θ(t)) 6= 0 for all t ≥ 0, it must be the case that either Ψk,i(θ(0)) > 0 or Ψk,i(θ(0)) < 0; let us, first, assume the former case. We are going to prove, by abduction, that Ψk,i(θ(t)) > 0, ∀t ≥ 0. Suppose ∃t′ > 0 such that Ψk,i(θ(t′)) ≤ 0. Since Ψk,i(θ(t)) 6= 0 for all t ≥ 0 it follows that Ψk,i(θ(t
′)) < 0 must be the case. However, by the continuity of Ψk,i(θ(t)) and the Intermediate Value Theorem, it follows that ∃t′′ ∈ (0, t′) such that Ψk,i(θ(t′′)) = 0, and that is, indeed, a contradiction. It follows that it must be the case Ψk,i(θ(t)) > 0, ∀t ≥ 0. In a similar manner we may prove that Ψk,i(θ(0)) < 0 =⇒ Ψk,i(θ(t)) < 0, ∀t ≥ 0; hence, (b) holds.
Theorem 4. Under Assumption 3, if Sk = ∅, ∀k ∈ [2], the restricted RD of G converge to
θ∗1,i = { α1,i, if β1,i < 12 β1,i, otherwise i ∈ [n1]
θ∗2,i = { β2,i, if β2,i < 12 α2,i, otherwise
i ∈ [n2]︸ ︷︷ ︸ if |S| is even
or θ∗1,i =
{ β1,i, if β1,i < 12 α1,i, otherwise i ∈ [n1]
θ∗2,i = { α2,i, if β2,i < 12 β2,i, otherwise
i ∈ [n2]︸ ︷︷ ︸ if |S| is odd
(21)
where S := {(k, i) | k ∈ [2], i ∈ [nk], αk,i > 12}.
Proof. We begin by conditioning on the value of |S| and, since the proof is similar in both cases, and without any loss of the generality, we are going to assume that |S| is even. Since Sk = ∅ for all k ∈ [2], i.e., 12 /∈ Sk,i for all k ∈ [2], i ∈ [nk], and, by Assumption 3, θk,i(0) ∈ Sk,i := [αk,i, βk,i] for k ∈ [2], i ∈ [nk] it follows that θk,i(0) > 12 , if αk,i > 1 2 ; θk,i(0) < 1 2 ; otherwise. Then, for all i ∈ [n1], we have
Ψ1,i(θ(0)) = 1
nk 2∏ k=1 nk∏ j=1 (1− 2θk,j(0))
= 1
nk  ∏ (k,j)∈S (1− 2θk,j(0))  ·  ∏ (k,j)/∈S (1− 2θk,j(0))  > 0,
since |S| is even. Subsequently, by Lemma 5, Ψ1,i(θ(t)) > 0, ∀t ≥ 0. That implies that Ψ1,i(θ(t)) > 0, ∀i ∈ [n1], t ≥ 0, and, hence, by Lemma 5, we also have that Ψ2,i(θ(t)) < 0, ∀i ∈ [n2], t ≥ 0. Take any k ∈ [2], and i ∈ [nk]. In order to complete the proof, we’ll have to condition on the value of k, and on whether (k, i) ∈ S. There are four cases in total that we”ll have to consider, but, since in all of them we follow a similar reasoning, we’ll just go ahead and demonstrate the single case of k = 1, and (k, i) ∈ S. We are going to prove that there exists t∗1,i ≥ 0 such that θ1,i(t) = β1, i, ∀t ≥ t∗1,i. By Assumption 3, and Lemma 4, we have α1,i ≥ θ1,i(t) ≥ β1,i for all t ≥ 0. Furthermore, since (1, i) ∈ S, and, since Sk = ∅, we have that α1,i ≥ β1,i > 12 . That is, θ1,i(t) > 1 2 for all t ≥ 0, and, hence,
D1,i(θ(t)) := ∏ k∈[2] ∏ j∈[nk]
(k,j)6=(1,i)
(1− 2θk,j(t)) = 1
1− 2θ1,i(t) · 2∏ k=1 nk∏ j=1 (1− 2θk,j(t))
= n1 · 1
1− 2θ1,i(t) · Ψ1,i(t) < 0 .
Then, by Equation D10 it follows that ∀t ≥ 0:
θ̇1,i(t) =  0, if θ1,i = β1,i 2
n1 θ1,i(1− θ1,i)D1,i(θ), otherwise .
(D11)
Hence, θ1,i = β1,i is the single attracting point of the dynamical system described by D11 and, hence, by definition, ∃t∗1,i ≥ 0 such that θ1,i(t) = θ∗1,i = β1,i, ∀t ≥ t∗1,i. Similarly, we can prove that ∃t∗k,i ≥ 0 such that θk,i(t) = θ∗k,i, ∀t ≥ t∗k,i, and by letting t
∗ = max k∈[2] i∈[nk] (t∗k,i), Theorem 4
follows.
Theorem 5. Under Assumption 3, if Sk 6= ∅, ∀k ∈ [2], then the restricted RD of G converge to an invariant set defined by the |S1|+ |S2|−1 independent invariant functions, Vi1,i2(θ), ik ∈ Sk, ∀k ∈ [2], where Vi1,i2(θ) is given as in (20).
Proof. We are going to begin by defining the following time-dependent set:
C(t) := { {(k, i) | k ∈ [2], i ∈ [nk], θk,i(t) ∈ {αk,i, βk,i}}, if t ≥ 0
∅, otherwise .
We perform a time partitioning based on the values of C(t), t ≥ 0. Specifically, we let P = {(t1, t2) | t1, t2 ∈ T : t /∈ T, ∀t ∈ (t1, t2)}, where
T := {t ≥ 0 | ∃ 0 > 0 : C(t− ) 6= C(t), ∀ ∈ (0, 0)} .
It is not difficult to see that the continuity of θ(t) implies that T consists entirely of isolated points and, due to this fact, P is well-defined. Let I ∈ P be one of these partitions. We are going to prove that V̇i1,i2(θ(t)) ≥ 0, ∀ik ∈ Sk, ∀k ∈ [2], t ∈ I. First of all, observe that, by definition, the following two properties have to hold:
(a) C(t1) = C(t2), ∀t1, t2 ∈ I
(b) By Equation D10, we have that ∀t ∈ I ,
θ̇k,i(t) =  0, if (k, i) ∈ C(t)
(−1)k−1 2 nk θk,i(1− θk,i)Dk,i(θ), otherwise .
(D12)
For any ik ∈ Sk, k ∈ [2], we proceed by conditioning on the value of C(t), t ∈ I and, since C(t1) = C(t2), ∀t1, t2 ∈ I , we distinct only three cases:
(a) (k, ik) ∈ C(t), ∀k ∈ [2], t ∈ I.
(b) (k, ik) /∈ C(t), ∀k ∈ [2], t ∈ I.
(c) ∃k, k′ ∈ [2] such that (k, ik) ∈ C(t) and (k′, ik′) /∈ C(t) for all t ∈ I.
The analysis of the first two cases is relatively straightforward. Let t ∈ I; then, if (k, ik) ∈ C(t), ∀k ∈ [2] is the case, then by Equation D12, we have that θ̇k,ik(t) = 0, ∀k ∈ [2] and, hence,
V̇i1,i2(θ(t)) = (∇θ(t)Vi1,i2(θ(t)))ᵀθ̇(t) = 2∑ k=1 ( nk(1− 2θk,i(t)) θk,i(t)(1− θk,i(t)) · θ̇k,ik(t) ) = 0 .
On the other hand, if (k, ik) /∈ C(t), ∀k ∈ [2] is the case, then, once again, by Equation D12, we have that θ̇k,ik(t) = (−1)k−1 2nk θk,i(1− θk,i)Dk,i(θ), ∀k ∈ [2]. That implies,
V̇i1,i2(θ(t)) = 2∑ k=1 ( nk(1− 2θk,i(t)) θk,i(t)(1− θk,i(t)) · (−1)k−1 2 nk θk,i(t)(1− θk,i(t))Dk,i(θ(t)) )
= 2 · 2∏ k=1 nk∏ j=1 (1− 2θk,j(t)) · 2∑ k=1 (−1)k−1 = 0 .
In order to proceed with the final case we’ll first need to prove a small technical lemma:
Lemma 6. If (k, i) ∈ C(t) for some t ∈ I, I ∈ P = {(t1, t2) | t1, t2 ∈ T : t /∈ T, ∀t ∈ (t1, t2)} then one of the following holds:
a) θk,i(t) = αk,i, ∀t ∈ I.
b) θk,i(t) = βk,i, ∀t ∈ I.
To see that, let I ∈ P and (k, i) ∈ C(t) for some t ∈ I. Then it, holds, by definition, that
C(t1) = C(t2), ∀t1, t2 ∈ I =⇒ C(t′) = C(t), ∀t′ ∈ I
And, since (k, i) ∈ C(t), we also have that
(k, i) ∈ C(t′), ∀t′ ∈ I =⇒ θk,i(t′) ∈ {αk,i, βk,i}
Let us assume that θk,i(t) = αk,i and suppose ∃t′ ∈ I such that θk,i(t′) 6= αk,i =⇒ θk,i(t′) = βk,i and αk,i 6= βk,i. By the Intermediate Value Theorem, it follows ∃t′′ ∈ (min(t, t′),max(t, t′)) such that
θk,i(t ′′) ∈ (αk,i, βk,i) =⇒ (k, i) /∈ C(t′′)
That is a contradiction, and, hence, a) holds. a) follows by a similar argument, assuming θk,i(t) = βk, i is the case, instead.
Having established Lemma 6, we continue with the proof of Theorem 5. Let us assume that ∃k, k′ ∈ [2] such that (k, ik) ∈ C(t) and (k′, ik′) /∈ C(t). Then Lemma 6 implies that either θk,ik(t′) = αk,ik , ∀t′ ∈ I or θk,ik(t′) = βk,ik , ∀t′ ∈ I. Let us assume, without any loss of the generality, the former case and let us consider some t ∈ I. Since Sk,ik ∈ Sk, i.e., αk,ik ≤ 12 , that implies 1 − 2θk,ik(t) ≥ 0. Next, Let us consider the value of (−1)k−1Dk,i(θ). We are going to prove by abduction that (−1)k−1Dk,i(θ) ≤ 0.
If (−1)k−1Dk,i(θ) > 0 then by Equation D10 we have thatθ̇k,ik(t) = (−1)k−1 2nk θk,i(1 − θk,i)Dk,i(θ) 6= 0, where the last inequality follows by Assumption 3. By the continuity θ(t), it follows that ∃ 0 > 0 such that ∀ ∈ (0, 0), θk,ik(t + ) 6= θk,ik(t) = αk,ik =⇒ (k, ik) /∈ C(t); that is, indeed, a contradiction. It must then be the case that (−1)k−1Dk,i(θ) ≤ 0 and, thus, we have that
V̇i1,i2(θ(t)) = nk′(1− 2θk′,i(t)) θk′,i(t)(1− θk′,i(t)) · (−1)k ′−1 2 nk′ θk′,i(t)(1− θk′,i(t))Dk′,i(θ(t))
= 2 · (−1)k ′−1 · (1− 2θk′,i(t))Dk′,i(θ(t)) = 2 · (−1) · (−1)k−1 · (1− 2θk,i(t))Dk,i(θ(t)) ≥ 0 .
Thus, we showed that in every case V̇i1,i2(θ(t)) ≥ 0, ∀t ∈ I. However, since θ(t) is continuous (since it is differentiable), we can extend this property for any t ≥ 0, i.e., V̇i1,i2(θ(t)) ≥ 0, ∀t ≥ 0. Finally, notice that Vi1,i2(θ(t)) is bounded, and, hence, it follows that −Vi1,i2(θ(t)) is a Lyapunov function (up to a constant) of the dynamical system described by Equation D10, and, Theorem 5 follows by the definition of a Lyapunov function.

heading: B SUPPLEMENTARY EXPERIMENTAL RESULTS
text: B.1 EXPERIMENTAL RESULTS FOR 2-TEAM HIDDEN MATCHING PENNIES GAMES
In this section we present exemplary settings for the dynamics presented in section 5. For an overview of the conditions that characterize the behaviors presented in these examples, we reference the interested reader to section 5; for formal definitions and the proofs of these concepts, see §A.4.
Let G = (n := n1 + n2,S := {0, 1}n, u : S → Rn) be a 2-Team Hidden Matching Pennies game with n1 = n2 = 3 and payoff function given by (17). Figure 3 depicts the behavior of the RD in an unrestricted instance of G, i.e., Sk,i = [0, 1] for all i ∈ [3], k ∈ [2]. The restrictions applied to team 1 and team 2 are visualized by the feasible range of each member’s strategies (Figure 3 (Left), and (Right), respectively). The black dot in each range indicates the initial strategy of each member, i.e., θk,i(0). Note that, by Assumption 3, this strategy profile, (θ(0),1 − θ(0)), is assumed to lie inside the feasible region enforced by the constraints Sk,i.
We solve the initial value problem of the ODE that corresponds to this RD using the RADAU integration method implemented by the scipy package in Python 3, and we perform 500 evaluations over the time interval t ∈ [0, 100]. The orbit of the RD with initial parametrization θ(0) is depicted as a curve on the F×G space defined by the hidden mappings in (19) (Figure 3 (Center)). The red dot indicates the the point (f(θ1(t)), g(θ2(t)) at the end of the simulation, i.e., at time t = 100. The corresponding strategies of each member are indicated by blue (team 1) and orange (team 2) dots inside the corresponding feasible regions (Figure 3 (Left), and (Right)). The individual trajectory of each θk,i, i ∈ [3], k ∈ [2] is depicted in Figure 3 (Bottom), where the curve labeled TkPi corresponds to the trajectory of the i-th member of team k if k = 1, or the i− n1-th member of team k if
k = 2. In the case that the RD cycle, e.g., in the unrestricted setting, we depict one of the Lyapunov functions of the RD (Figure 3 (Bottom)). Specifically, the Lyapunov function of our choice is
V (t) := 2∑ k=1 1 |Sk| ∑ i∈Sk nk · [log(θk,i(t)) + log(1− θk,i(t))], (29)
the average value of all the linearly independent Lyapunov functions defined in (20). We selected this specific Lyapunov function as the average is, in general, more numerically stable and for compactness.
In Figure 3, we verify that the RD of G, indeed, cycle in an unrestricted setting (Theorem 3). The choice of initial points does not matter in this case; for completeness, we note that θ1 = (0.1, 0.9, 0.2), and θ2 = (0.1, 0.9, 0.8) in all of the examples in this section.
As the first example in a restricted setting (Figure 4), we are going to enforce S1,1 = S1,3 = S2,1 = [0.05, 0.4], and S1,2 = S2,2 = S2,3 = [0.6, 0.95]. First, observe that Sk,i ⊂ (0, 1) for all i ∈ [3], k ∈ [2]; hence, Assumption 3 is satisfied. Next, notice that 12 /∈ Sk,i for all i ∈ [3], k ∈ [2]. It follows, by Theorem 4, that the RD should converge in this case (Figure 4 (Center), and (Bottom)), and the point of convergence is, indeed, θ∗1 = (0.4, 0.6, 0.4), and θ ∗ 2 = (0.05, 0.95, 0.95), as given in Theorem 4.
There exists a similar setting (Figure 5), where the RD of G converge, as well. Note, in this case, while 12 /∈ S2,i for all i ∈ [3], we let 1 2 ∈ S1,i for some i ∈ [3] (specifically, 1 2 ∈ S1,i for all i ∈ [3] in this particular example). Although we did not provide a convergence analysis for this case, it is not difficult to see that the convergence guarantees from Theorem 4 can be generalized to include this case. As is visualized in Figure 5 (Center), the exhibited behavior is a hybrid of the two behaviors described by Theorem 4, and Theorem 5. In particular, the behavior of the dynamics depends on the quadrant of the F×G space that the θ(t) lies. Ultimately though, the dynamics can be shown to converge to a point θ∗, which depends not only on the initialization θ(0) but also on the restrictions in the space parameters, Sk,i, i ∈ [3], k ∈ [2]. The particular point of convergence
for this example is θ∗1 = (0.05, 0.95, 0.95), and θ ∗ 2 = (0.4, 0.6, 0.6), where the space restrictions are given as S2,1 = [0.05, 0.4], S2,2 = S2,3 = [0.6, 0.95], and S1,i = [0.05, 0.95] for all i ∈ [3]. Finally, we present an example of cycling behavior in the restricted setting (Figure 6) where we applied the restrictions S1,1 = S1,3 = [0.05, 0.8], S1,2 = S2,2 = [0.6, 0.95], S2,1 = [0.05, 0.4], and S2,3 = [0.2, 0.95]. Note that 12 ∈ S1,1,S1,3,S2,3; hence, |S1|+ |S2| = 3, and there exists ik ∈ [nk] for all k ∈ [2] such that 12 ∈ Sk,ik . By Theorem 5, it follows that the restricted RD cycle in this case; specifically, they converge to an invariant set defined by V1,3(θ) = 0, and V3,3(θ) = 0 as given by (20). This behavior is depicted in Figure 6 (Center). Notice how the Lyapunov function, V (θ) (Figure 6 (Bottom)) is monotonically increasing, and stabilizes at approximately t = 25.

Review summaries:
The authors study a generalized Gradient Descent/Ascent flow in a class of non-convex non-concave games known as hidden convex-concave (HCC) games. Their first contribution is to establish a global convergence guarantee to stationary points. Moreover, for an important instance of the proposed dynamics they characterize the limit cycles using invariant function analysis. Empirical results are also presented to support the theoretical findings. 

This paper studied a non-convex non-concave Zero-Sum game setting called Hidden Convex-Concave game (HCC), as shown in Def. 1, which includes several examples, such as Hidden Matching Pennies games, Generative Adversarial Networks (GANs) / WGANs, and Adversarial Example Game (AEG). The observation is that although the min-max objective is non-convex non-concave w.r.t. the parameters (e.g., weights of neural networks), it could be convex concave of the outputs/strategies of the players $F$ and $G$.  Under Assumption 1 of there exists a Nash equilibrium $(F^*, G^*)$, the authors studies/proposed an algorithm called Natural Hidden Gradient flow (NHG), which is a preconditioned gradient flow update, such that $F$ and $G$ are doing normal Euclidean gradient descent because of the HCC game is convex concave w.r.t. $F$ and $G$.  The authors first showed that for a one-dimensional and finite-sum of convex-concave objectives, the distance to optimum is a Lyapunov function of NHG, and thus NHG converges to the Nash equilibrium.  The authors then connected NHG to replicator dynamics (RD) in literature, under a certain metric of geometry. They showed that in a 2-Team Hidden Matching Pennies game, there exist several invariant functions, which explains why RD manifest cycling orbits.  Finally, the authors conducted simulations to verify the proposed NHG method, showing that it is more stable than Gradient Descent-Ascent (GDA).

This paper follows a recent and interesting line of research on strategic approaches to GAN training in which the optimization problem of the players is lifted to the space of models employed by the discriminator and generator. The main aim of this literature is to shed light to the question why simple first-order methods perform quite well in this application, although the basic hypothesis (such as monotonicity of the variational inequality) are not very likely to be satisfied. The price to pay via this lifting, due to Gidel, G., Balduzzi, D., Czarnecki, W., Garnelo, M., & Bachrach, Y. (2021, March). A Limited-Capacity Minimax Theorem for Non-Convex Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets. In International Conference on Artificial Intelligence and Statistics (pp. 2548-2556). PMLR, is that the saddle-point problem is defined in a Banach space of functions and measures. This paper proposed natural gradient training parameters defining the models employed by the discriminator and generator, respectively.