Generalized Natural Gradient Flows in Hidden Convex-Concave Games and GANs
Authors: Andjela Mladenovic
Iosif Sakos
Gauthier Gidel
Georgios Piliouras
Venue: ICLR 2022 Poster (2022)

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.

Published as a conference paper at ICLR 2022
GENERALIZED NATURAL GRADIENT FLOWS IN HIDDEN CONVEX-CONCAVE GAMES AND GANS
Andjela Mladenovie Univ. of Montréal & Mila
Iosif Sakos SUTD
Gauthier Gidel
Georgius Piliouras SUTD
Univ. of Montréal & Mila
ABSTRACT
Game-theore -hee-the formulations in machine learning have recently risen in promi- nence, 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 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 in- form practice. This paper studies the generalized Gradient Descent-Ascent (GDA) flow in a large class of non-convex non-concave Zero-Sum games dubbed Hid- den Convex-Concave games, class of games that includes GANs. We focus 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 com- plete picture of the dynamics in an interesting special setting of team competition via invariant function analysis.
INTRODUCTION
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, 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-concase games (Sion 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 payoff's: 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; Hsich et al., 2020). To overcome these negative results, analyze spe- cific class of non-convex non-concave games called Hidden Monvex-Concaveeeee (HCC) games (Flokas 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 occur- ring in the standard convex-concave games setting. We propose 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.c., we do not make any assumptions about initial conditions, e.g., that the initial points belong to some local neighborhood. This novel algorithm is inspired by the generalization of gradient flows in different Banach spaces than the stan- dard Euclidean one. Arguably, the most well-known non-Euclidean gradient is the natural gradient
ml adenevic, wetrwiicgiiidd giuelgau @m 1a quebec, iosif sakos 3mymail......mmmmm....m....mmmmm 1.... sutd. edu georgios(sutd. edu.sg sg 1 'Canada CIFAR AI Chair
EEails of contact
sse (Letcher, 2021, Definition 5) for definition of "reasonable algorithm"

---

Published as a conference paper at ICLR 2022
flow induced by the Fisher information matrix, which enjoys deep connections the Replicator Dynamics (RD). Thus, a natural second question emerges: Can we have similar convergence guar- antees for RD? In that regard, we provide complete picture of the resulting dynamics in a setting of team competition via invariant function analysis. Specifically, we reduce the flow of the dynamics to competition between two generalized gradients, one for each team. We show that the behavior of the dynamics in this setting is constrained by maximal number of invariant functions, which, com- bined with the actual geometry of the available strategies, shows that the system can either converge or cycle. These two results showcase, both, the importance of adapting the "algorithmic geometry" the application and the data at hand, as well as the unexplored effects of feasibility constraints on the complexity of well-known game dynamics.
RELATED WORK
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 are still pre- liminary. However, this space has already witnessed a few important early works that focus on identifying new solution concepts. These solution general min-max games-include (local/differential) Nash equilibria (Adolphs et al., 2019; Mazum- dar & Ratliff, 2019), (local/differentiaa) Stackelberg equilibria (Fiez et al., 2020; Wang et al., 2020), local minmax (Daskalakis & Panageas, 2018), local robust points (Zhang et al., 2020), and approxi- mate minimax theorems (Jin et al., 2020; Gidel et al., 2021). Numerous solutions concepts such as cycles Vlatakis-Gkaragkonn
-whchhhhwhich are also broadly applicable in
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-L.ojsiewice games (Nouiehed et al., 2019; Yang et al., 2020), nonconvex-concave games (Lin al., 2020; Ostrovskii et al., 2021; Yang et al., 2020; Kong & Monteiro, 2021), 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 topic of exploration (Kodali et al., 2017: Heusel et al., 2017: Mescheder et al., 2018; Gemp & Mahadevan, 2018: Li et al., 2018; Hsich et al., 2019; Cao & Guo, 2020), its hidden convex-concat theoretical global convergence guarantees in a general setting up to this date. particular, Hsieh et al. (2019) use lifting trick and proceed in solving 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 -theiiiggte-erll,, a second-order technique, and provide global convergence guarantees for the Wasserstein Linear Quadratic GAN (W-LQGAN). While the W-L-QGANs 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 the other hand, the idea of Hidden Convex-Concave (HCC) games was first proposed by Flokas 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.
structure has not been exploited before, and there were no
neural networks. On
PRELIMINARIES
Many game- theoretic applications in machine learning often involve a specific structure where the models' payoff is a convex-conead function (c.g.. minimizing Sensen-Shannon, -ivannon-Dieergence when training GANs). To model this specific structure, we propose the following definition of Hidden Convex- Concave (HCC) games where intuitively, the game's 's payoff is convex-concave function whose actions are parametrized by non-convex mappings.
2

---

Published as a conference paper at ICLR 2022
Definition (Hidden Convex- Convex-Concave game). A Hidden Conver- Coneee-- game comprises collec- tion of payoff (La,æ') xt ERa, a distribution p. and two parametrized mappings, F: R x R + R
and G: IN x IR + =R, such that the minimax game of interest is
min max V (0, Φ) where V ②) = [( G = (' ( a (Fo(z)) ( (1) DERM BERN
In this setting, while we do not expect ( xb) to be convex-concave, we assume the function T. Fx G - R to convex-concave where and G are, respectively, convex subsets of {F RRd -> RR and {G I!" + 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 E [0, 1] the probabilities of picking HEADS for the first and the second player, respectively, in a Matching Pennies game with payoff matrix A E IR2x2, where Arg = if = ji -1, otherwise. Then the payoff of this game is defined via
L (p.g) = (1- 11-22p1 2p) 2q) if (p. E 1],
=(1
and
0 otherwise.
(2)
Now, let us consider any mappings F R Rdd + 10, 1] and G RN x Rd + 10, 1]. such that their output does not depend on the d-dimensional input, i.e, Fo(x) = f(0). and (z(x) = g(Φ), vx e
Idd The payoff V/ (0, () = L(Fo. G&) == E[ (Fo(z) (x = (1 (12(0))))((())
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 O, and Φ. which are fed into functions f. and g.
respectively. whose outputs define the probability of playing HEADS for each agent.
Example (GANs). A Generative Adversarial Network (GAN) a minimax game where the first player, i.e,, the generator, aims at learning a distribution po similar to reference data distribution Pdata- 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 distinguish the distributions of pe and Pdata- The payoff. V, of this game is defined as:
(3) Assuming that Pdata and po have a density with respect to Lebesgue measure," 3 and that the support of po is included in the support of Pdata, we can consider the distribution p such that pla, x') = paata(x)) if x = x', and O otherwise, and set La (p', D) == log D + (a) log(1 D0g(1-
(0, Φ) Exxpssa [log (x)) + Em-po [log(1 Dx(x))
D). Thus Le,w' is convex-concave for any x, x' IRd. We have that V Φ) (x Jup [T (x)( , (2:)),, which is a HCC game.
A GAN formulates the generative modeling task as finding a Nash equilibrium of a minimax game. The generator of GAN is defined as function that aims to produce realistic data samples by transforming samples drawn from fixed noise distribution, e.g., (0, Iz). Here, we notice that the GAN payoff is convex (actually linear) function of the density of the generated distribution. An alternative formulation a GAN is a Wasserstein GAN (WGAN) (Arjovsky et al., 2017). It turns that this GAN is also HCC game.
Example 3 (WGANs). A Wasserstein GAN is constrained minimax game, where the second player D& is a functionn and where the payoff is
(0 Φ) EEx=poanal [D+(x)) Exp-p (De
Similarly, as in Example 2, the WGAN payoff can be shown to be HCC game.
As the last class of examples of HCC games, we present the Adversarial Example Games (AEG) (Bose et al., 2020).
"One can always assume F and G to he convex sets by considering their convex hulls.
We make this assumption for simplicity. We can consider Radon-Nikodym derivatives for the general case.
3

---

Published as a conference paper at ICLR 2022
Example 4 (AEG). An Adversarial Example Game is minimax game between generator Go and a classifier f. Given samples (x,y) ~ Pdata the generator Ge aims at finding adversarial examples x' such that ж x' 2211,0 S and that x' is not classified y by f, thus generating distribution Po- Overall, the payoff of this game is
(0 () =
x)>ppl y)] for (x's) ~ pe + x' = Ge( (x, ~ Pdata (5)
and where is the cross-entropy loss and Gg such that || GG())( S e, Vv. By using a similar construction as in Example 2, we can show that (5) is a HCC game with respect to pe and fa-
In this work, we make the assumption that the minimax problem induced by admits solution: Assumption 1. The HCC game defined by (1) admits Nash equilibrium, (F*, ,G),, i.e. min max L(F, G) PEB GEG
max min L(F, G) L(F" ,.) GEB FEF
(6)
Such an assumption is relatively mild since it holds when the set F is compact (by definition, it is convex) (Sion et al., 1958). Note that this solution may be achievable, i.e., we do not assume that there exists 0 and 6" such that (Fer. GΦ-) existence of Nash equilibrium of L F G R are discussed in detail in Gidel et al. (2021, Prop. 1), e.g., Assumption holds if the parameters O and Φ are bounded. From a high-level perspective, this assumption analogous to the existence of global solution non-convex optimization. We use (F*, G*) target to build Lyapunov function of the natural hidden gradient flow.
G*). Such sufficient conditions for the
3.1 NATURAL GRADIENT FLOW
In this section, we present the notion of a natural gradient flow (Amari, 1985; 1998). Let us consider function f S - R and a class of symmetric positive definite matrices (Po)oes > 0 that will refer to as metric tensors. The natural gradiens flow is the flow given by the steepest descent direction (Ollivier et al., 2017) with respect the geometry induced by the matrices Po.
θ = P VP))
(7)
When Pe - I. we consider the canonical Euclidean geometry and recover the standard gradient flow. One celebrated example of a natural gradient 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 probubility distributions on set X C R with the metric induced by the Kullbuck-Leibler (KL) divergence. Then the natural gradient flow of the Fisher information malrix is given by
① = (())
where Fe -Exxpol V log (x)], pe E P(X).
(8)
Moreover, if n = X dim S is finite, and if po 0, the flow (8) the natural gradient flow of the Shahshahani metric (Shahshahani, 1979) induced by the metric tensors
So diag( (,-
Recently, alternative natural gradient formulations have been developed using the Wasserstein dis- tance (Li & Montúfar, 2018; Arbel al., 2020).
3.2 CONNECTIONS BETWEEN REPLICATOR DYNAMICS AND GRADIENT FLOWS
The Replicator Dynamics (RD) are standard dynamics used in Evolutionary Game Theory and learn- ing 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 gradient flows (see Sigmund (1984); Hofbauer et al. (1998); Harper (2009); Mertikopoulos & Sandholm (2018) (00 Specifically, in the case of symmetric and linear fitness landscape, the gradi- ent induced by the Shahshahani metric of the mean fitness is a special case of RD. Such a land- scape can be formally represented by a Potential game. A Potential game is a n-player game = (n, S := [mi] X ... x [m u. : - IR"), with payoff function u, characterized by the existence of potential function Φ S + R that satisfies
( 8-1) (8/6 8 (1(8118-2) (4(5),,8))) Vi E [n].
(10)
4

---

Published as a conference paper at ICLR 2022
The connection between potential games and the gradient flows induced by the Shahshahani metric can be formalized with generalization Hofbauer et al. (1998)'s 's lemma.
Proposition 1. The Replicator Dynamics of a potential game G with potential function is an (extended) Shahshahani gradient in int [Am, x... Am..) having potential Vi (0) = Ex 0
[+()).
=E(n]
follows that, for potential games, RD a gradient flow with respect to a very specific geometry. In the next section, we consider geometry induced by the HCC structure, and which we leverage to obtain a new natural gradient flow that we call Natural Hidden Gradient flow (NGH).
3.3 THE NATURAL HIDDEN GRADIENT FLOW FOR HCC GAMES
In HCC games, we assume ( Φ) L(Fo. G (see Definition 1), and, therefore, since the entities that characterize solution to the minimax problem are the mappings Fo and Go instead of their parametrizations,
and Φ, respectively. natural geometry for consideration is the one defindd by the L distance in the space of F x G. Formally, let 0 and O' be two parameterizations for F (similarly, for G). The L² distance between the mappings are:
Fer -Foll Ee>p_ (Fo (Fo (x) - Fo(x))² and ||G Garll===
Euwp,, (G (x') =arpp===u---,,
(z)))
where Pa: and pat are the marginal of Para' We can then derive the metric tensors of this geometry. Proposition 2 (Metric tensors of the model space). Under mild regularity assumptions, we have that.for any 0 E R.M,
|F F 12 = (50, Ap50) + o(1150113) where
Ao = Expep ( (oo
(11)
Consequently, Ag defines metric on the parameter space in which the "distance" between two values, 0, and 0', corresponds to the L distance between I' and Fgg. We can, thus, construct the corresponding natural gradient flow.
Proposition 3 (Natural Hidden Gradient dynamics). The flow induced by the geometry (11) is
Ø = A (m. Vo w (Fo( Go(z'))
(DI)
Φ B E in V To (Fo( G
where Ao = En-pa V (oFo(z (oo( and B Egina DV denotes the pseudo-inverse of a matrix C.
and Ct
4 CONVERGENCE OF THE NATURAL HIDDEN GRADIENT FLOW
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 proper, i.e., monotonic, we will prove our proposed dynamics are approaching Nash Equilibrium.
4.1 WARM-UP: A SINGLE DATAPOINT
In this section, as a warm-up, we will consider the single datapoint case. In this case, (1) is,
(e Φ) L(Fo(z), Go(æ'))
(12)
where L : R R RR is convex-concave (see Example 1). In this case, since the mapping Fg and Go are evaluated at a single point, one can simplify the notation and consider Fo(ar) = ʃ(0) and Go(ax') = ((Φ) where f M - and g R - R are real-valued mappings that do not depend input x'. This situation is already non-trivial since, illustrated in Example 1, it can correspond to a non-convex non-concave parametrization of the Matching Pennies game. In order solve this game consider the Natural gradient of the metric defined in Proposition 2.
Proposition 4. In the uni-dimmesional case, the Natural Hidden Gradient flow DI takes the form of
θ =
Vol(F(0).ol .g( [
and ò VoL(S(0). [oo(
((()))
(D2)
5

---

Published as a conference paper at ICLR 2022
Using Proposition 4, it is relatively straightforward to show that the distance to the optimum is Lyapunov function for the Natural Hidden Gradient flow.
Theorem 1. Let v be the payoff of an HCC game (12) and consider the dynamics (D2). Then,
V(0,0) = (((()) 1²)² (g( - -²²)²
(13)
a Lyapunov function, i.e., it is positive, non-increasing. and null if and only if it evaluated at game solution. Moreover, if L is strictly convex-concave, we have that V is decreasing and that any (( = vL g g(Φ))= =
limit point (6, Φ) satisfies
In order see this, one can compute the time derivative of V. After some elementary computations, it follows (00 Φ) (f(()) )t) (L(f.
and, thus, + (g(Φ)) 9*) aL((())))
f=f(0)
8g
(=))()))
by the convex-concavity of L. we have that V S O. However, generalizing this theorem HCC games with non-constant mappings (with respect to x) is non-trivial since we drastically used the simplicity of the mappings (Proposition 4) simplify the expression of the flow. In the next section, we propose to extend our convergence analysis to finite sum HCC games.
4.2 THE GENERAL FINITE SUM CASE
In this section, we consider a finite-sum version of the HCC games as they appear in Definition In this case, the payoff is defined as
(0, Φb)
Σ LL Go(z)) L((F((z:)) (Go (G)(z)))eem)),
(14)
(5.)) x[b]
where the function L : RT X R + R is assumed to be convex-concave We note Li.j == Le
for compactness. Let recall that we assumed the existence of Nash equilibrium (F", G*) for the minimax problem (Assumption 1). In this situation, the Natural gradient defined Proposition has the following form:
0 =
A1 Σ (Fo nm
Σ (FLL) (m.j)
(D3)
(i.j)[(m) x [x)
where Ag = J. ΣM (eFe((z) and B = = Σ VoGu(t))
We will generalize the Lyapunov function considered in the uni dimdenmnnional case (13). The idea is to consider the L distance between (Fo(æ;), Go(w)) and (F* G (a') ))s , our Lyapunov function V. However, order to prove our result, we will need the following technical assumption.
Assumption 2. For any O E RRM and (Vo (V.Fo(x:))eett (x.))) and (V ( are linearly independent.
RN we have that the families of vectors
When the models are overparametrized, e.g., M > m and N > n, this assumption is relatively mild since it can be insured by small perturbation of the considered vectors. In practice, it suggests regularizing the matrices Ag and B& by adding e La which a standard way to stabilize methods requiring matrix inversions.
Theorem 2. Let V be the payoff of a finite- HCC game given by (14) and consider the game dynamics in (D3). Under Assumption Assumption we have that the quantity
V(O, Φ)) = 2n Σ (Fo(m:)) - F² (xx))
- G (Gala)))G"aa()
(15)
2m 3=1
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, is decreasing as long as (0, (.)) + (0*, x*) and if L is a p-strongly convex-concave function we have that V is decreasing exponentially as V(0, )) V ((n, Φo) exp(-uu).
We showed that, in the overparametrized regime, if we assume not to encounter any singular matrices Ag and Bg along the trajectory, then, preconditioning low dimensional gradient of and & can behave like doing gradient update F and G leverage the hidden-convex-cave structure of

---

Published as a conference paper at ICLR 2022
the the payoff. We do not know how recover the gradients updates F and G in the non- overparametrized regime. It is a great open question that we consider outside the scope of this paper as we focus on understanding convergence in minimax games for deep learning models (that are over-paramenn sver-parametrized). The proofs of Theorem and Theorem are in $A.3.
Regarding the practicability of the method described in (D3), efficient approximations of precondi- tioning, such as the K-FAC algorithm, were proposed (Martens, 2020; Li & Montúfar, 2018) and used train large models on Imagenet and CIFAR (Martens al., 2021; Arbel al., 2020).
CHARACTERIZATIONS OF REPLICATOR DYNAMICS IN HCC GAMES
In this section, consider specific instance of HMP games (ef. Example 1), dubbed 2- 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, cally, as we prove in subsection 5.2, by enforcing restrictions to the game's 's parameters, it is possible to affect the game's outcome, e.g., we may deviate from the well-known cyclic behavior in the un- restricted setting, and moreover, enforce divergence away from the game's 's original equilibrium and convergence 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 (19). For the complete proofs of this section, we refer the interested reader to $A.4.
show stronger results. Specifi-
5.1 2-TEAM HIDDEN MATCHING PENNIES GAMES
We introduce the 2-Team HMP game, G = (n = ni + 12, 10; ==.1,, 3G-R" I"). between n1 + ni members divided into two teams. The first team, leam 1, consists of nı members, while the second team, leam 2, consists of n2 members. The payoff function u for a strategy profile
($1, 82) S is given by
(s) (-1)² 2.
[xOR(s)==OO(<.)) -
& [2], i [mx].
(16)
The
where XOR(sk) 1 if Hsk.s sk,i 1} is odd, and O, otherwise. Given mixed-strategy profile, (0, 1 - 0). 0 = (0t) E [0, 1j". the expected payoff of the i-th member of team is given by
(+) = Exn, t Ber(Oe..:) [s)] (-1)a=1 (1 25(01)) -2g(O2) k< me)
(17)
Ex BBer(0, [XOR(s:)] and (02) = Exg=BBr(0,)) [xOR(s))]. Notice that, since each member of given team aims at maximizing the same payoff, G is a Hidden Matching Pennies game (Example 1) with hidden mappings f())), and g(02),
where f(01) =
min max V (0,, 02) = Σ (0) = (1 - (1-2)(()))( 2g(02)) 02 6,
(18)
It is not difficult prove that the RD exhibit cyclic behavior in this setting. The following theorem provides a tinengraieed characterization the dynamics of the HCC game (18) where we show that the trajectories lie on the intersection of level sets of invariant functions.
Theorem 3. Consider the Replicator Dynamics of G. Given any interior initial condition, the resulting orbit cycle that satisfies the following n, + n22 independent invariant functions:
Vi,,iz (0) ml(log(Ok.s.) + log(1 (k. is E [mx], [2]
(19)
5.2 REPLICATOR DYNAMICS HIDDEN MATCHING PENNIES IN A RESTRICTED SETTING
Next, we introduce restrictions in the range of each member's 's strategies in G such that 0n E Sh.i == (ou,, Bk,,]] C [0, 1J, Vk [2], E [nx]. These restrictions reflect in RD halts, i.e., dg,; O, every
7

---

Published as a conference paper at ICLR 2022
time the strategy of the i-th member of the k-th team exceeds those bounds. To ease our notation,
let Sk == {i E [ E Sk.ch. & E [2] denote all the members of the k-th team for which (3) (2:2) 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 E [2] and i E [ma], (0) E Sk,t C (0,1).
0). 0 = (0,,,00))))) E [0, 1]", if there exists some is E [n AA E [2] such that 02 = 2. then 0 is an equilibrium point; in fact, is not difficult to see that these are the only interior equilibrium points of G. which implies that
A significant observation is that for any mixed-strategy profile (0. 1
an interior equilibrium point is reachable if and only if S2 * 0, vk E [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 constraints, then the dynamics converges to a point which only depends on those restrictions.
Theorem 4. Under Assumption 3. if Sy.- = 0, Ak E [2], the restricted RD of G converge to
{ |1 B1,55
Bf < otherwise
B1.b:
if otherwise
i [m(]]
oT.
i [mi]
01,i:
or
(20)
0
B2iis
if B2 otherwise
i i [
0
122;;
32
E [ma]
32,5.
otherwise
(S even
[/18] is odd
where S = (k. & E [2). [nx], ane > 1
The key idea behind this result that at any given time t 2 O, the direction of a strategy (t., only depends on whether [8), 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. If equilibrium point of the unrestricted setting is reachable by both teams, i... Sy * 0, vk E [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, (2 2)
Theorem 5. Under Assumption 3, S + 0, Ak E [2]. then the restricted RD of G converge to an
invariant set defined by the [S1|+ + [2l - independent invariant functionn,, ViL,az (0), is E St, Vk E (2). where V (0) is given in (I9).
One can prove this result by partitioning the time based on the set of members that have halted. The analysis of ez,,e2(0 (0) in each innepaatitiinn is almost trivial and the result follows by a continuity argument on Vi, (0). These results depict how the behavior of RD depends on the parameter space of the game. Notably, we show that if no equilibrium point 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 parameterizzttions that visualize the behavior of RD in such restricted settings, see $B.1
EXPERIMENTAL RESULTS
Toy multi-dimensional case. As first experiment, we consider the HCC objective
(0, L(Fo, G&) = F. MG + (1 11 - || - 2),
game (see e.g. Gidel et al. (2021)). We 3. 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 I, we depict a comparison between the performance of GDA and NHG dynamics the task of solving ming max (O, Φ). We remark, the NHG dynamics converges smoothly (Figure 1 (Right)), compared to GDA (Figure (Center)), which fail to converge. The value of the Lyapunov function of the game described is depicted in (Figure 1 (Left)).
where M is the payoff matrix of the Rock-Paper-Scissee
note (a:) = [Fo]s i E (3). and 1
GANs. For our second experiment, we implement the NHG dynamics to train a GAN. We consider synthetic experiment to learn sine wave sampled uniformly from O to x with 1024 observations.
8

---

Published as a conference paper at ICLR 2022
Solution
0.5
Solution
P2
015
3.1
Netural Gradient Standard Gradient
0.1 0.2
550
100D
1500
7000
040.00
0.2 0.3
Figure 1: A comparison of GDA (Center) and NHG dynamics (Right) in the task of solving ming maxę (O, Φ) where p = (O), and q = g(Φ). In NHG, the Lyapunov function (Left) is monotonically decreasing, as opposed to GDA.
Regarding the GAN, we consider Flow-GAN architecture where our generator, G, is Real NVP consisting of 8 coupling layers (Dinh et al., 2017; 2014), and the discriminator is a 4-layer MLP with 256-1 28-66-1 output features. We adapt K-FAC (Martens & Grosse, 2015) as approximator to compute NHG, with a learning rate of 10-1, selected using the standard parameter optimizer package Optuna (Akiba al., 2019). We used gradient clipping with gradient clip maximum norm of on, both the discriminator and the generator, to stabilize the optimization.
As observed in (Figure (Center)), by iteration 200, the GAN optimized using K-FAC learns the true sinusoid almost perfectly and converges to better Wasserstein- 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 ex- periment goes slightly beyond the theoretical results: while in theory, we assume natural gradient flow "full-batch", our experiments are based on discrete stochastic updates, and approxima- tion of the pseudo-inversed of the matrices (see (D1)) using K-FAC. Thus, this experiment acts as a proof-of-coneed rather than large-scale comparison between NHG and GDA. The details of both experiments can be found within the source-code files included with this work.
Natural Grad int Stancard Gradien:
azx
Wostermenn
455
400
Number of MiTltaaa ataratoon
12
Figure 2: A plot of the real sinusoid sampled on the interval from 0 to 2m (Left). GAN generated samples for NHG dynamics (Center). The performance of GDA vs. NHG dynamics on GANs as measured by Wasserstein-1 distance (Right).
DISCUSSION
We proposed novel version of Gradient Descent Ascent dynamics in Hidden Convex-Concave 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. 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. Our analysis of the convergence of our proposed 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 the finite-sum case. To the best of our knowledge, such a non-local convergence result in HCC games and GAN- like settings, one of the first of its kind. We also show promising experimental results on practical GANs using NHG and standard gradient approximation techniques such as KFAC. We are aware that the current formulation of NHG may be challenging to scale up to large neural networks because of the tensor pseudo-inverse
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 scale results for larger neural networks is natural direction for our future work.

---

Published as a conference paper at ICLR 2022
STATEMENT OF REPRODUCIBILITY
We made sure to provide sufficient details to ensure the reproducibility our results. The complete proofs of the theoretical results 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 execute and reproduce the experiments in section 6 and $B. We also include the source code files and the necessary ipput files in the supple- mentary material that accompanies this work.
ACKNOWLEDGEMENTS
The authors would like to acknowledge Joey Bose for his help on the GANs experiments.
This rescarch/project is supported in part by the National Research Foundation, Singapore under its AI Singapore Program (AISG Award No: AISG2-RP-2020-016) NRF 2018 Fellowship NRF- NRFF2018-00 URF2019-NRF-ANDE grammatic Fund (Grant No. A20H6b0151) from the Agency for Science, Technology and Research (A*STAR) and Provost's Chair Professorship grant RGEPPV2101. This work is supported by the Canada CIFAR Al Chair Program and an IVADO grant.
ALIAS grant, grant
AME Pro-
REFERENCES
Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann. Local saddle point optimization: A curvature exploitation approach. In The 22nd International Conference on Arti- ficial Intelligence and Statistics. PMLR, 2019.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A eext-geneaation hyperparameter optimization framework. In Proceedings of the 25rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019.
Shun-ichi Amari. Differential-geomtiiie methods in statistics. Lecture Notes on Statistics, 28, 1985.
Shun-Ichi Amari. Natural gradient works efficiently learning, Neural computation, 10(2), 1998.
M Arbel, Gretton, W Li, and G Montufar. Kernelized wasserstein natural gradient. Interna- lional Conference on Learning Representations, 2020.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning. PMLR, 2017.
Avishek Joey Bose, Gauthier Gidel, Hugo Berrard, Andre Cianflone, Pascal Vincent, Simon Lacoste-Julien, and William L Hamilton. Adversarial example games. In NeurlPS, 2020.
Haoyang Cao and Xin Guo. Approximation and convergence of GANs training: SDE approach. arXiv preprint arXiv:2006.00041 2020.
Yun Kuen Cheung and Georgios Piliouras. Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games. In Conference on Learning Theory. PMLR, 2019.
Yun Kuen Cheung and Yixin Tao. Chaos of learning beyond zero-sum and coordination via game decompositions. In ICLR, 2021.
Constantinos Daskalakis and Ioannis Panageas. min-max optimization. In NeurIPS, 2018.
The limit points of (optimistic) gradient descent in
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. STOC, 2021.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for structured sanconvex-nonconcann min-max optimization. In ICMI,, 2021.
10

---

Published as a conference paper at ICLR 2022
Nishanth Dikkala, Greg Lewis, Lester Mackey, and Vasilis Syrgkanis. Minimax estimation of con- ditional moment models. In NeurlPS, 2020.
Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: Non-linear independent components esti- mation. arXiv preprini urXivv1410.8516, 2014.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real NVP. In
ICLR, 2017.
Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In International Conference on Machine Learning. PMLR, 2020.
Lampros Flokas, Einmanoul--aasledte Vlatakis- Miaakki-GKaragkounii, and Georgios Piliouras. Poincaré for non-convex non-concave
recurrence, cycles and spurious equilibria in zero-sum games. In NeurlPS, 2020.
Lampros Flokas, Cinmanoull-Vaileioos Vasileios Vlatakis-Gkaragkouniis and Georgios Piliouras. Solving min-max optimization with hidden structure via gradient descent ascent. In NeurIPS, 2021.
Ian Gemp and Sridhar Mahadevan. Global convergence to the equilibrium of GANs using variational inequalities. arXiv preprint arXiv: 01531, 2018.
Gauthier Gidel, David Balduzzi, Wojciech Marian Czarnecki, Marta Garnelo, and Yoram Bachrach. Minimax theorem for latent games How learned to stop worrying about mixed-nase and love neural nets. AISTATS, 2021.
I Goodfellow, Pouget-Abadie, M Mirza, B Xu, D Warde-Farley, S Ozair, A Courville, and Y Ben- gio. Generative adversarial nets. In NeurIPS, 2014.
Mare Harper. Information geometry and evolutionary game theory. CoRR, abs/0911. 11111.1188 13833, 2009.
URL http::t/axxiv..oot abs/ 1383.
Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (GELUs). arXiv preprint arXiv:1606.08 08415, 2016.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by a two time-scale update rule converge to local nash equilibrium. NeurIPS, 30, 2017.
Josef Hofbauer, Karl Sigmund, al. Evolutionary games and population dynamics. Cambridge university press, 1998.
Ya-Ping Hsieh, Chen Liu, and Volkan Cevher. Finding mixed Nash equilibria of generative adver- sarial networks. ICML, 2019.
Ya-Ping Hsich, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-max optimization algorithms: convergence to spurious non-critical sets. CoRR, 2020.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-noncomcave minimax optimization? In International Conference on Machine Learning. PMLR, 2020.
Naveen Kodali, Jacob Aberntty, James Hays, and 7solt Kira. On convergence and stability of GANs. arXiv preprint vrXiv:/705.0722 2017.
Weiwei Kong and Renato DC Monteiro. An accelerated inexact proximal point method for solving nonconvex-coneat min-max problems. SIAM Journal on Optimization, 2021.
Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems. In NeurIPS. 2021.
Alistair Letcher. On the impossibility global convergence in multi-loss optimization. In ICLR, 2021.
11

---

Published as a conference paper at ICLR 2022
Jerry Li, Aleksander Madry, John Peebles, and Ludwig Schmidt. On the limitations of first-order approximation in gan dynamics. In International Conference on Machine Learning. PMLR, 2018.
Wuchen Li and Guido Montúfar, Natural gradient via optimal transport. Information Geometry, (2):181-214, 2018.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave mini- max problems. In JCML, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In ICLR, 2018.
James Martens. New insights and perspectives on the natural gradient method. Journal of Machine Learning Research, 2020.
James Martens and Roger Grosse.
Optimizing neural networks with kronecker- approximate curvature. In International conference machine learning, 2015.
James Martens, Andy Ballard, Guillaume Desjardins, Grzegorz Swirszez, Valentin Dalibard, Jascha Sohl-Dickstein, and Samuel S Schoenholz. Rapid training of deep neural networks without skip connections or normalization layers using deep kernel shaping. arXiv preprint 1rXiv:21 2021.
Eric Mazumdar and Lillian Ratliff. Local nash equilibria are isolated, strict local nash equilibria in 'almost all' zero-sum continuous games. In 2019 IEEE 58th Conference on Decision and Control (CDC). IEEE, 2019.
Panayotis Mertikopoulos and William Sandholm. Riemannian game dynamics. Journal of Eco- nomic Theory, 2018.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra(-gradiem) mile. In ICLR, 2019.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for GANs do actually converge? In International conference on machine learning. PMLR, 2018.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. NewrIPS, 2019.
Yann Ollivier, Ludovic Arnold, Anne Auger, and Nikolaus Hansen. Information -eooeetrion-- opti-
mization algorithms: A unifying picture via invariance principles. Journal of Machine Learning Research, 18(18), 2017.
Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash equilibria nonconvex-concave smooth min-max problems. SIAM Journal on Optimization, 2021.
Georgios Piliouras and Leonard Schulman. Learning dynamics and the co-evolution of competing sexual species. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) Schloss Dagstuhl-LeibnizzZZenn
fuer Informatik, 2018.
Siavash Shahshabani. A new mathematical framework for the study of linkage and selection. Amer- ican Mathematical Soc., 1979.
Karl Sigmund. The maximum principle for replicator equations. liasa working paper, IASAA, Laxenburg, Austria, 1984.
David Silver. Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lueas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676), 2017.
Maurice Sion et al. On general minimax theorems. Pacific Journal of mathematics, 8(1), 1958.
12

---

Published as a conference paper at ICLR 2022
Emmanouil- Vasiileios Vlatakis- Gkaragkounis, Lampros Flokas, and Georgios Piliouras. Poincaré recurrence, cycles and spurious equilibria in gradient-dexcent-ssccn for non-convex non-concave zero-sum games. In NeurIPS 32: Annual Conference Neural Information Processing Systems 2019.
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. In International Conference Learning Representations, 2020.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of nonconvex-nonconeee minimax problems. In NeurlPS, 2020.
Guojun Zhang, Pascal Poupart, and Yaoliang Yu. Optimality and stability non-convex smooth games. arXiv preprint arXiv: 2020.
A OMITTED PROOFS
A.1 OMITTED PROOFS OF SECTION 3.1
Proposition A.1. Let consider P(X) the space of probability distributions set X C R with the metric induced by the Kullback-Leibler (KI) divergence. If = |*| = dim S, and po == A E P(K), then the natural gradient flow of the Fisher information matrix in (8) the natural gradient flow of the Shahshahani metric induced by the metric tensors in (9).
Proof. All we need to show that Fg = So: vO E S. Simply, note that Vi,j E [n]:
18 1ologg (x
02 log (x (x
(Fo)i.) = Expxp
08,00,
00,00,
=EX
8 log Oz
Eu Jg.
ôúj (So)
Σ
0g
30,00,
02
0,
aEX
A.2 OMITTED PROOFS OF SECTION 3.2
Let G = (n, S = [m1] x... x [m,]. u: R") be a n-player (exact) potential game with payoff function u and potential & S - R, and let M A.. X...X x A.n be the mixed-strates sttrttgy space of G. We are going to consider the RD of in int MI = int Amy x... x int Am,. as given in the following proposition.
Proposition A.2. The Replicator Dynamics of G in int M are given by the following dynamical system of equations:
θ,j = Gz.j EB (Bn [u, s- Exyro [s:(s))) = 0is (NN(()
((O))
(D4)
ae...
kc(n]
kc(n)
where (0) = Eg,0, .
(s)) is the the expected potential function of the game.
sE[n]
Proof. First note that
(V((0)
00
EII Ou ((8)
EII
Ok.5 (())
00,,5
20.;
kys
ΣI
Σ
0k 8_))
Eg (e(j)s=)))
8_ kgti
ie(m)
13

---

Published as a conference paper at ICLR 2022
From which follows that
O..5 Ozs (Be (u((iss))) us((s])
0r.s( (Bry (0(iss:)) 2(s)))
kelnl
ke(ml
(OV(0)
= His 002,
v(0))
Next, let consider point 0 E int M, and note that the following proposition holds: Proposition A.3. For any 0 E int MI = int Am, X... X int Am.. the tangent plane of int MI at
(oit M) {nr E R x... g. Σ M4. = =0.
(21)
Proof. We first note that int M. is an open-subset of the surface ID = { E m x... x R" U,(H) = 1), where (p) Ej Pi.j hence, (onin M) To ID, up isomorphism. Let r(t) be smooth curve in with r(0) = O. Then, by definition, U((r(t) 1 for all i, and, by differentiating with respect to f, we have
d rt) U,(((t))
VU,(((t))
1=
dt
dt
dt
However, d r1)) is tangent to D for all I; hence, # _1(1) 2t (0) is normal to To for all i, and ,ths, we have
E To D. follows that VU.(r(0)) =
1=
To ID C (μ E Rm x... x R (VU,,(0) p1) = =0 = {u R x... x R Σ Maj 0}
Finally, notice that dim/u g ... m proposition.
EE Mis
0} -dim D, which implies the
Proposition 1. The Replicator Dynamics of a potential game G with potential function is an
(extended) Shahshahani gradient in int Amy X Am..) having potential No (0))) = Ex 0
[
iE(n]
Proof. Let O E iint = int Amy X... int Am...
Then for every & (int (i) have:
1 (0, = E E OiiEiij Σ
OV(0))
(())
Eij Σ
(N)())
Eig - ((()) ((6)){s Eij
Bis
00.5
aB.,
(V0())
Ei.j VV(() E
20is
Hence, by definition, we have that ( á, where the Del operator defined with respect to the Shahshahani metric, which implics the lemma.
Now, let consider different class of games, which define as 2-Team Zero-Sum games.
14

---

Published as a conference paper at ICLR 2022
Definition 2. 2- 2-Team Zero-Sum game, G (m mi m2, hn]x.... [nmll, u: :u:S- Rm),, a game between m players with strategy- space S whose utility function, u, satisfies the following:
1 (s), if [mi]]
us(()
V8 E
(22)
(s)) otherwise
for some function : R.
We going to, collectively, refer to the first m, players of 2-Team Zero-Sum game, G (m mi + m2, S [n1] x x [m]],2 u + 1.,) as team and to the rest of them as team 2. Notice that if consider each team Zero-Sum game, G' = (2. S' == S₁ x $2, u S + R2) where S = [n1] x x... x [pm;). 82 = [mm1+1 ... X m and the utility function un is the total utility of the corresponding team k, i.e. V8 E 8 we have
single player, then the two teams
playing 2-Player
Σ 1
1(s) m1
(s) and w/)(s)
Σ 1=
1 17
- (8).
(23)
Note that, by definition, the 2-Team Hidden Matching Pennies game (see section 5) is a 2-Team Zero-Sum game. Let us consider the Replicator Dynamics of G given by the following dynamical system equations:
01. = 0 (Bas (1. - Es [s)(s)))
Og Bo [$j (())] if E [m]]
(DS)
m1
0 1e ~0 (j)ss))) (()).. otherwisc
12
where, as before, we can rewrite (D5) in terms of (x:) = Esara [S))
1
(V) (())). if [m]]
0..
m1
00..j
(D6)
1
(V)))
NV
(
0i.5
(())). otherwise
00
m2
Notice that the Replicator equations of each team are similar to the Replicator equations of Poten- tial game. In fact, it's not difficult to prove the following lemma.
Lemma 1. Let G (m m. m2,
[m1] x... x [mm], + R.m be 2-Team Zero-Sum game. If we assume the strategies of team 2 to be time-invariant, then the Replicator (my-scaled) Shahshahani gradient in
Dynamics of G, given by (D5) (or (D6), equivalently). int M = int An, X... x int Anm with potential V (0) v (1, where V 4r( = Es,~o, [2))), and II int M int M. the natural projection
Ik. (ii.j if team k otherwise.
(24)
Likewise, if we assume the strategies of team be time-inarrant, then the Replicator Dynamics of G is a (ma-scaled) Shahshahani gradient in int M with potential V2 - (0).
Proof. This proof is similar to the proof of Proposition 1, but need to perform the correct pro- jection before applying the definition generality, let us assume that the strategics of team 2 are time- invariant, i.c., 0., = 0 for 2 m,. Then, for every & (int M) have
gradient flow. Let 0 E int M. Without any loss of the
15

---

Published as a conference paper at ICLR 2022
E)
E
m1
0
M1
1
0ūs
(aV(O)
v(0)
EN
0i.
ebi. m1
a0,.)
1721
(V)
m1
m1
av
E/d
(0)
E1
End
00.5
80..5
j
(1
Si.
20..
Hence, by definition, we have that (0) 0% which implies the theorem.
Proposition 2 (Metric tensors of the model space). Under mild regularity assumptions, have for any 0 E RdM,
|F - Fe 1 = (80, Ago0) + x( where Ag == Exppp Volooo (11)
Proof. The assumption on F we need to prove this results are the following:
0 + Fo(x) is almost surely differentiable, i.e., almost surely (in a;),
Fe+se (x) Fe(x) + (VFe(x)) |100|) 0), YO RM,
(25)
where fæx 80) +0 0 almost surely in æ.
For small enough 50 E TRM, The remainder of the Taylor expansion of Fg has finite variance, i.e.,
Ez (f(e,, 50) +00.
(26)
A consequence of these two assumption is that (by dominated convergence theorem and Jensen's inequality)
Ez-p. (z, 80)1] 50 and Ez-pe (s 60) 550 0.
(27)
Let us now prove the desired property. We start by doing a Taylor expansion of e + Fo(x),
Fo+ Fa(x) + (VFo(z), 60) + [(00
Then we have that
F0+60 - Fell2 E. Ex (|a
= (VF=)
E Bawpe 00
50 V (7
which concludes the proof.
Proposition 3 (Natural Hidden Gradient dynamics). The flow induced by the geometry (11) is
0 - '') VoLn (Fo(z), Go(x))
(D7)
Φ = B E 'mp VoL (F
where Ao = En-ps ooFo (o and B = Ex'rpy (V (oGGs( and C denotes the pseudo-inverse of matrix C.
16

---

Published as a conference paper at ICLR 2022
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 induced by the distance d if
1 [(0 X00) 2X2
1
0 arg min lim
dl de (Fo+250 Fo)
X-0 X
60
By using the L distance and noting that when À - 0 we have f(0+ x60) = +
o()) and 21a Fo+160 - Fell = (60, Ag00) + o(1) we have that the RHS of the equation above
arg min ( (60, Ao00);
60
which is minimized for 50 = -A
A.3 OMITTED PROOFS OF SECTION 4
Proposition 4, In the uni uni-dimensional case, the Natural Hidden Gradient flow D)I takes the form of
0
(eL(F((). (f)
and
(aL(f(0),9(0)) [os(()
(D8)
Proof. For the miidimeesionall case, As V vector in the direction of ( and scales it by V (V) 12 Thus, by definition of the pseudo-
rank-1 matrix that projects any
inverse, we have that for any vector u. E Rdd
4Ju (I, VS(())
Finally, notice that
voI(((0),((0) (0
0f f=f(0))
which leads to the stated proposition.
Theorem 1. Let T be the payoff an HCC game (12) and consider the dynamics (D2). Then,
V(0,0)= = (f(0) -
f²)²
(
(13)
is Lyapunov function, i.e., it is positive, non-increasing. and null if and only if it evaluated at game solution. Moreover, L is strictly convex-concave, we have that is decreasing and that any limit point (0, Φ) satisfies VeL(((O) g()) = VoL(s(O), g(())
Proof. By taking the time derivative of V(0, Φ), we get
VS(0) aL(f.g(0) (/ of
((0 - - (V)00)-0()())
f=f(0)
Vg(Φ) aL((())g))
+ (Vg(()(((()) -
|| 0g
g=
- (r) OL. (L(
(T(S((),
OL
+ (g(#) 9¹)
5
0f f=
0g
g=9(0)
17

---

Published as a conference paper at ICLR 2022
where the last inequality holds because L is convex-coneave. Specifically, let L R x X R be any differentiable convex convex-concave concave function with saddle point ,f","") then we have, respectively
-V - 1" V,L(,))) S (( L(Sg) and 00- v,L.sn) S ((S.) L(S.9).
By adding the two inequalities, we get
-V- + -
V (g s L(
L(S.9) 0
(28)
) is a saddle point. Hence, by definition, L is where the last inequality holds because (f gg) Lyapunov function.
Finally, when L. is strictly convex-concave if there exists limit point of (0, Φ) that is not a point where (oL(f(0), (0). g()) and (f (O) g()) then by strict convex-concavity we get
that V should decrease by "significant enough amount" to create contradiction with the fact that does converge.
Next, before proving the general case of Theorem 1, we'll have to prove the following lemma: Lemma 2. Let (ui)etj) be linearly independent family of vectors IR Then, the matrix
A
uuu!
(29)
is the Gram matrix of the family (u:)se[n) and and we have that (ui, Aluj) = d.gj Vi,j E [n]]
Proof. Let introduce the matrix P == [u....., U, [ T; easily verify that A PTA. Let P = UDVT be the SVD decomposition of P and, thus, At V(DID) where DTD is diagonal matrix. Then, have
(u, Alus) = (1) A = (VD''te ((DD) = () UD(DID))DTUTe)))
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 (ut)ee()) are linearly independent, we have that Da 0, Vi [m]. Thus, by direct computation, get that
D
which leads to (ut, Alu,) 80.5-
Theorem 2. Let Vi be the payoff of a finite-sum sum HCC game given by (14) and consider the game dynamics (D3). Under Assumption Assumption we have that the quantity
V(0 = 2n Σ
1
n
(Fo(z;) F* (xx)))
2m -GGo(E))-G(E))
(15)
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 comeex-concvve, V is decreasing long (0,Ø) * (0*. x²)) and if is a p-strongly convex-concave function we have that V is decreasing exponentially as V(0,, (00,0) Φ) V(Oo, Φo) exp(-ul).
18

---

Published as a conference paper at ICLR 2022
Proof. Similarly the proof of Theorem consider the time derivative of V(0, Φ). For com- pactness, we are going to simplify the notation slightly by setting F; == Fo(x;) G3 = Gs(aa)
F G3 = G* (2r)), and Lig- == T.
() 1 E (B- 1 E(G, (G -))((
Σ
A Σ VOIn Gý))
n2m
i=1
(+A))/ml x|]]
(G - G
G B 3
Σ (o Gk))
nm j=l
(,,0)mmm)x x ml)
I. (F, Gÿ)
RR F.) VoF A
n m'
OF
F=Fa
(iA))(m))x(n
θLi, (Fi, G)
(G - Gj) Σ Va & Vb)
n
0G
G=Gx
(m)
From Lemma 2 have that (VoF, V (V&G,, F = m dz Hence, it follows
8g Vi E [n], k E [m]. and that
0L. (T,,(F,G,)
T (T. G)
((0,6)=
EA- F?)
CG, G3)
Tm
OF
F=F,
Tm
0G
G=G,
RE|n
iE(n]
jE[m]
jE(m]
-80 F`) +
G= and F, G, F", and G* are indexed by (i,j), as well (while repeating vector elements as necessarily). Thus, using the same reasoning in Theorem I, it follows that if L is convex-concave we have that V is non- increasing, and, if L is strictly convex-concave V(0, Φ) < 0 whenever (0, Φ) (0", Φ"). Finally, is p-strongly convex-conees we have by definition that
where [FF G))())) = (L.,(F.G.)) OF
F=F (F = (L..(F.G)) 8G
- F-F
2
Thus we conclude that VO Φ) < V(g, Φ0) exp(-
A.4 OMITTED PROOFS OF SECTION
In order to prove (17), and (D9) we are, first, going to prove the following useful lemma:
Lemma 3. Let hi) (xy (XO((x,,).............. .,,R(x x:)] where E [0, 1]", and i S n. Then the
following equality holds:
2ho II (1-))). j=1
(30)
Proof. The easiest way to prove this relationship is by induction on 7 E N. For n = 1, we only need verify that (30) holds for i 1. Indeed, we have,
19

---

Published as a conference paper at ICLR 2022
1 - 21) = 21 Ber(e (XOR(xx)] = 2 (er [1] = 201
Next, let assume that Lemma 3 holds for some n' N. We going prove that Lemma also holds for n = n + 1, and this comes down in proving that (30) holds for = n' +
- 22 +1) = 20[X X xx++1) [++11]=1111 = - 2 X1 xn Xx++1]
2(0m++1R((XO))
X,,, (/,11) (1-00++)) XI...... ,,',,
1 - 2(0n0+1 -XORI XX. Xnx) -
Xn.)]]
2(0n/+1(1 - ho(n'))) + (1-6 (0o = (1- 20,, 21) (n))
n'+1
= -1 -1-20 20
II - -0,) II -1-20)).
-
j=l
j=1
And we that, the proof by induction is complete.
Proposition AA. Let G = (n n +2, = ( 1R)) be a 2-Team Hidden Matching Pennies game with payoff function given by (16). Then, the expected payoff of the i-th member of team is given by (17).
Proof. The first equality follows, trivially, from the definition of ((s). All is left to prove that BBBr(()1.))) B. (B,((-) [s)] (1 r ( (XOR(s)))((1 - 2 (XOR(()))) for all
0 [0, 1]". We define. X₁ XOR(s)); [2]. Note that, by definition, X₃ Ber(pk), where Pk: = Bs Ber(B, [OR((s)]: hence,
Exg t
(0..)) p = Ex,, - Ber(( - [xoo(s))=00((z))) Ex = - 1 1x==
[[))
(xe-- ) [[1 XXR(x)) 22) (1 2p1) 2p2)
(1 - BBs,,,BBrr(e, (XO((s ())(ss)))(( 21 (XOR(s)))
Proposition A.S. Let G = (1 = (0. u: : - IR") be 2-Team Hidden Matching
Pennies game with function given by (16). Then, the RD of G is given by the dynamical system of equations:
ŌR. = (-1)--11 02,;1
Ou.i)
II
II (EEn,r) (K',))
(0-20R,))-
(D9)
Tik
Proof. From (17) we have that
- (up. [sp]
(-1)k-1 1
- (1 Ber
2 (OR(s)))) - 2B,,, v Ber(02, (XOR(s)))
(-1)*=) k-1 nk
1
(1 2ho, (11) 2he (1z2) (-1)k-1 1 II II (1 20xxx)))
T&k
(E(m)]
Then, by the definition of RD of G, get
20

---

Published as a conference paper at ICLR 2022
0x.= == Og Bert (0,, (-ii) [s)
(-1) On.
II
II
(1-20k,,))
II
II (1 - 20k.s)
Tik
K'(2]
d'Enyl
2
(-1) n
(1 0k.s)
II ME (K,
II d'Eny]
(1- 20x,)k,)).
Theorem 3. Consider the Replicator Dynamics of G. Given any interior initial condition, the resulting orbit is cycle that satisfies the following + n2 independent invariant functions::
(2
nx (Ol + log(1 - (k.da)) is E [ma], [2]
(19)
Proof. For all k E and i E [Nan], we have
nx(1 28k.i)
av (0)
if (k,, E ((K)4e) | K [2]}
0k. (1 - 0k,))
0, otherwise
Subsequently, we have
Vi (0) ( VoV... = II II kE[2] |E|mE]
(1 - 20,,00 - II II AE[2] [E|mL]
(1 20x.2) = 0.
Observe that the above imply the existence of n1 n2 independent invariant functions. Hence, the dynamics converge to limit set of single degree of freedom, i.e., a cycle.
Proposition A.6. Let G (n == n1 + n2 = {0.1)".u:3
R") be 2-Team Hidden Matching Pennies game with payoff function given by (16). Given a mixed-strategy profile (0, 0). 0 = (0,, 02) E 1)", (0, 1 0) is equilibrium of G if and only ii,, Vk [2] such that 0k.i 2 vk [2].
Proof. We know that G equivalent to Hidden Matching Pennies game (Example 1) with payoff (0)) (1 (1 (g)),)), where f(01) = Bes..BBer(e...) Be.. (XOR(ss)) and g(O2) = (00, rium of this Hidden Matching Pennies game is ((01).g(0))
are its hidden mappings. The only fully mixed-Nare equilib-
(3 1); hence, mixed-strategy profile (0, 1 0) is fully mixed-Nash equilibrium of G, if and only if f(0) g(02) 3. From
f(0)) 2 we get
Ber(O..) [XOR(s)) = = 1 1-22hh, (n1) = +
20 =
1=1
Bi [ni] : 01, =
21

---

Published as a conference paper at ICLR 2022
We remark that, for any is [ne]], [2].
V1, (0) = Σ
ne Dog (Ok.ie) + +og((1 - -0,,ie) Σ R=1
mx log(On,üe) + log(1 -Ok,in)
1=1
2
Σ 2 ny (Ber()))()) (5), Ber(OOk,a))
k=1
where (p: q) the cross-entropy of distribution q relative distribution p. In other words, every one of the invariant functions in (19) is the weighted sum of the cross entropy of two mixed- strategies (of the i1-th member of team 1, and the ig-th member of team 2) relative to the uniform strategy. That is, each invariant function measures (up constant) the Kullback-Leibler diver- gence of two opposing members an actual equilibrium of the game. Notice that, for any equi- librium point of the Hidden Matching Pennies game, there exists at least such pair of opposing members 1 E [n1], and is E [22] such that
DKL (Ber()) || Ber(01,;;)) = DxL (Ber()) || Ber(O2,;.)) = 0.
For the rest this section we are going to consider the RD of 2-Team Hidden Matching Pennies game G (n n1 n22 S = {0, 1)", S + R") in restricted setting, given by the following
dynamical system of equations:
0, if OR,i & Sk,i
0, if OR,i Obki and (-1)* Dx,, < <0
0, if OR.i Ba,s and (-1)* Dx, > 0 (D10)
(-1)x-1 0x, DR,,
otherwise
n2
where (0) N II jEIngr] (1 - 20 A [2] E [mg]. and where restrict each (k,,))
mixed-strategy profile (0,1-0 - 0) such that Os,, Sk, = Jax, 3R Vk E [2]. E [na]. We let be an orbit defined by this RD whose initial conditions satisfy Assumption 3. This assumption serves dual purpose. To begin with, it ensures that any orbit is initialized inside the restricted parameter space that defined by Sk,s- Furthermore, makes sure the initial strategy profile has full support, i.e., (0),; 1 - (0)) is an interior point of the simplex for all k E [2]. and i E [nu]- is easy to see that any dimension of the strategy space initially without support impossible 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 useful lemmas.
Lemma 4. Vk [2]. and E [nm] if (0, Sk.i. then (t,:(t) E Sk,i. VT 12
Proof. Let t E [2] and E [ng] such that (0) Sk.z to prove our case by abduction.
O.k. S (0) S Br. We going
Suppose 34 such that O1,)(1o) St.s and, without any loss of the generality, let us assume that (k.((lo) > 32,t- We let T= (1 (0, 4)) (t) = Be, and we note that, since (0) S Br, implied by the continuity of (t, (Equation D10) and by the Intermediate Value Theorem that T & O. Finally we define tmax = max(T).
Let us now consider the value of (t,((t) for some (Imax; to) and observe that if (1, BB. we have
t T t max tmax
tmax t S traxx
22

---

Published as a conference paper at ICLR 2022
This contradiction implies that (t) * Pk... However, if (t, Bk.s. the Intermediate Value Theorem, once again, implies 3t E (t, to) such that (x.,(t)) = Bk.s, which as before implies fmax < t' I max- Hence, it must be the case that, for all E (fmaae tn):
(D10)
(1,((1) > BRGi
(1) 0.
However, by applying the Mean Value Theorem, if follows 3t' (tmaxi to) such that
(t) (0) Ox,iltmaxx
0R,i(0) Bris > 0,
to mmx
40 Imax
which is once again contradiction.
Lemma 5. Under Assumplion 3, Sf = 0, vk E [2] then the following hold:
(a) 11,, (0(t))2.,, < 0 for all is E [mx]], & E [2], and 2 0.
(b) kk (0()) preserves sign for all i E [ng], 1: E [2].
Proof. Since S& for all [2]. follows, by definition, that
1 2 $ Sk Ak: [2], i [n
Furthermore, by Assumption 3, we have that (k. Sa.i for all k [2]. i E [me]]. Hence, it follows, by Lemma 4, that Vk: [2]. E [nx], and 2
(t. E Se,s
= (t, + 2
1 20x, #0.
Then, by Equation 17, we have
(O()() (-1)a-1 (1 2 [XOR(s)))((1 - 21,,, Ber( (SO((s))))
(-1)^=1 h- (1- 2ho [11 - 2ho.) = (-1)^-1
(1 20
II (1 2022,)
71k
Tkk
j=1
==1
(-1)^-1
2 ay
(1 (()) #0.
7
k=1j=1
That implies (a). We can now condition on (O(O)..)). Since (0(t)) + for all f 2 0, must be the case that either Vt. (0(0)) 0 or (e are going to prove, by abduction. that V4 (+()) > 0, Vt 2.0. 0.
0: let us, first, assume the former case. We
Suppose 3t > 0 such that Lx, (O(t)) < 0. Since (0(t) * for all t 0 it follows that (O(t)) < must be the case. However, by the continuity of (0()) and the Intermediate Value Theorem, it follows that 3t" E (0, f') such that V4, (0(t)) = 0, and that is, indeed, contradiction. It follows that it must be the case (O((() > 0, 2 0.
In similar manner may prove that 1 (0())) holds.
Vx (0())) 0, Vt 0; hence, (b)
23

---

Published as a conference paper at ICLR 2022
Theorem 4. Under Assumption 3. Sf = 0,
Wk [2], the restricted RD of converge
{ aa Bi,ss
B1, <
31.s:
B1 <
i [mi]
E [m]]
otherwise
01,1:
otherwise
or
(20)
02
if 22 < otherwise
e [m2]
0
12,5
32 <
E [na]
02,6
$2,5.
otherwise
(18) eveR
11 od
where S = ((k,)) & iE [ma]], and > 2)
Proof. We begin by conditioning 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] even. Since S₃ = 0 for all
A E [2]. i.c., 1 & S for all & [2]. [NR]]. and, by Assumption 3, 0R, (R, Sk, == [a [ for l E [2], i [ra]] it follows that (0) 2. if axi 1: (0) 2 otherwise. Then, for all i E [m we have
2 mk
(O()((()))
(1 20x (0))
Thk k=1j=1
II (1 20k, (k.j)ES
II (1 20k,((0)) 0, (K.J)ES
T
since [8] is even. Subsequently, by Lemma 5, (O(t)) 0, 4 0. That implies that (O(t) > 0, Vi [n], t 2 0, and, hence, by Lemma 5, we also have that (O()())))) < 0, Vi E [2]], / 2 O. Take any k [2]. and [na). In order to complete the proof, we'll have to condition on the value of k; and on whether (k: E S. There are four cases in total that we'll have consider, but, since in all of them we follow similar reasoning, we'll just go ahead and demonstrate the single case of k = L, and (k, i) E S.
We going to prove that there exists fi,; tion and Lemma 4, we have 01, 2 (t) > B1, for all t 2 Furthermore, since (1, S,
such that 0 01,x(t) 31, AL 2 Hi By Assump-
and, since gg 0, we have that 01,; 2 31, 1. That is, (t, for all 2 and, hence,
(0((((()))
II kE(2]
II
(1 (1-20k.))) (l-20k,(1)) 1 (1),
I 20k (1)
jEiNe] (k.))*(1.))
k=1j=1
1
=
I (t)
(t,(() <.
Then, by Equation D10 it follows that Vt 0:
0, if if = -1,i
01,(()) =
2 01, (O.), otherwise n1
(D11)
Hence, 01,; = 31,5 is the single attracting point of the dynamical system described by D11 and, hence, by definition, 3tj 2 such that (t, 0i,, = 31, Vt 2 fi.s- Similarly, we can prove that 36 2 0 such that 0z,((1) = 0 4L 2 12,,- and by letting 1" max (L,,), Theorem ke(2) vE(mu)
follows.
24

---

Published as a conference paper at ICLR 2022
Theorem 5. Under Assumption 3, Sf 0, vk E [2], then the restricted RD of G converge to invariant set defined by the [S1|+ + [yl independent invariant functions, [2], where $2 (0) is given in (19).
function,,nntiins,, V &a (0), , in Sp, Ak E
Proof. We are going to begin by defining the following time-dependent set:
C(t) ((k,8) [2), thi [ne], (t)x(t) (a Bkit)) i 0
0, otherwise.
We perform time partitioning based on the values of C(t), t 2 0. Specifically, we let P ((11,22 4,,2 T T, VI E (11, (2)], where
(1 2 0 3eo > 00: x C(I, Ve E 60)
It is not difficult to see that the continuity of (tt) implies that TT consists entirely of isolated points and, due to this fact, well-defined. Let E P one of these partitions. We are going to prove that Vi, (0))) 2 O, Vig E Sk, Ak E [2], 1 T. First of all, observe that, by definition, the following two properties have to hold:
(a) C(t) = C(t2), 12
(b) By Equation D10, we have that E I,
0, if (k, E C(t)
(l)
2 (-1)a=1 h- n2k
(D12)
01 OR. otherwise.
For any is E Sk, & [2], we proceed by conditioning on the value of C(t), I and, since C(4) = C(12), Vh, la E 7, we distinct only three cases:
(a) (k) C()), Vk E [2], t.
(b) (k, i & C()), Ak: E [2], T.
(c) k,, E [2] such that (ks ix) C(I) and (Wiw) & C(I) for all ( E
The analysis of the first two cases is relatively straightforward. Let E 1: then, if (k, ix) C(I), Vk [2] is the case, then by Equation D12, we have that OR (1) 0, vk [2] and, hence,
2 nu(1 ((), (1. (1,(()) O (t)
V..., (Vor)) Va..s (0(1)))0())
Σ
On the other hand, if (k, in) & C(t), Vk E [2] is the case, then, again, by Equation D12, have that fx.ce (t) = (-1)4-1 k-1
ny 0z. (z. wk E [2]. That implies,
(0(t)) = Σ
nx (1).
2 (-1))=1 Oz (t) (...())) n
(t. (t))
k=1
2
II [ 20,, (t))
(-1)k-1=0)
k=
k=1
In order to proceed with the final case we'll first need prove small technical lemma:
25

---

Published as a conference paper at ICLR 2022
Lemma 6. If (kt i) E C(t) for some t I, P ((t1.t2) 11,t2 E T :t & T, Vt (t1,
then one of the following holds:
a) (t.((t) Ouki VE
b) (n,((1) Bk, VEE E
To see that, Iet E P and (ks, i) E Ct) for some t E I. Then it, holds, by definition, that
C(t2) C(t2),
C(t) C(t), AA e
And, since (k, i) E C()), we also have that
(k C(t),, V El 0,,(tt) {a 8k,b3
Let us assume that (L. o and suppose 36' E such that (R.((') o oKk = (k,(1') = Bx. and agg # Se.s. By the Intermediate Value Theorem, follows 3t" E (min(t, t'), max(t, such that
(x,((t)) (aR,3, (k, C(t")
That is a contradiction, and, hence, a) holds. a) follows by a similar argument, assuming (t. 3k, is the case, instead.
Having established Lemma 6, we continue with the proof of Theorem 5. Let us assume that 3k, k E [2] such that (k, ix) C(t) and (k', ig)) C(t). Then Lemma 6 implies that either 0k,5 (t') akii At' E I or Gg.ss (t') = Sk.ie Vi' E I. Let us assume, without any loss of the generality, the former case and let us consider some E Il. Since S4 E Sp. i.c., akii S 1/2 that implies 1 20k,in (1) 2 O. Next, Let us consider the value of Dr.(O). We are going to prove by abduction that (-1)--1Das
< O.
If (-1)*-1 (0)
then by Equation D10 have thattk. (t) (-1)^=1 0
me Dr. O, where the last inequality follows by Assumption 3. By the continuity O(t), follows that 3co > 0 such that Ve E co), Ok,i, (t + c) & Bk.i, (t) akki = (k, i & C(t);
that is. indeed, contradiction. It must then be the case that (-1)*- 1- (0) s 0 and, thus, we have that
(0()) ny 01-112200 ((t),(t)
Ow 00 (1 2 ni
OF (c,(())),,,(0(00))
(t) 0k (1))
= 2-1 -1, (1)))).11),,, (f(tt) = (-1) (-1))-1 20). 2 0.
Thus, showed that in every case (0())) 2 0, Vt I. However, since (t) is continuous
(since it differeetiablee,, we can extend this property for any 2 i.c., V. (())) 0, Vt Vt2 0. Finally, notice that Vi, (0(t)) is bounded, and, hence, it follows that - -V;, (t)) is a Lyapunov function (up to a constant) of the dynamical system described by Equation D10, and, Theorem follows by the definition of a Lyapunov function.
B SUPPLEMENTARY EXPERIMENTAL RESULTS
B. EXPERIMENTAL RESULTS FOR 2-TEAM HIDDEN MATCHING PENNIES GAMES
In this section we present exemplary settings for the dynamics presented section For an overview of the conditions that characterize the behaviors presented in these examples, refer-
26

---

Published as a conference paper at ICLR 2022
Game ristory
Stiasagy Space of Nans
Stroagy Spare Tea
Term 2
48
TPP1
34
5.
0.1
10
2A
00
1.0
184m
-120
-14
To En
500 Tim
Figure 3: An example of the RD of a 2-Team Hidden Matching Pennies (Center) with no restrictions applied in the parameters space (0. 1 0) in (Left), and (Right). In this case, the RD cycles for any initial point (0(0), - (()). The evolution of (t), as a function of time, E [0, 100] depicted in (Bottom) along with the Lyapunov function given in (31).
ence the interested reader to section 5; for formal definitions and the proofs of these concepts, see $A.4.
Let G (n = ni 72 (0, 11"h S + I2") be 2-Team Hidden Matching Pennies game with n1 = n2
and payoff function given by (16). Figure 3 depicts the behavior of the RD in an unrestricted instance of G, i.e., Sk.; = [0. 1] for all i E [3], k [2]. The restrictions applied to team and team 2 are visualized by the feasible range of each member's strategies (Figure 3 (Left), and (Righr), respectively). The black dot in each range indicates the initial strategy of each member, i... (0). Note that, by Assumption 3, this strategy profile, (0(0), ((0)), assumed to lie inside the feasible region enforced by the constraints Sp.i-
We solve the initial value problem of the ODE that corresponds to this RD using the RADAU in- tegration method implemented by the scipy package in Python 3, and we perform 500 evaluations over the time interval E [0, 100j. The orbit the RD with initial parametrization ( depicted curve the F x G space defined by the hidden mappings in (18) (Figure 3 (Center)). The red dot indicates the the point (f (t)) (02 (t)) at the end the simulation, i.c., 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 dr.d. (3), & [2] is depicted in Figure 3 (Bottom), where the curve labeled ThPi corre- sponds to the trajectory of the i-th member of team A if k = 1, or the i Ry-th member of team & if In the case that the RD cycle, e.g., in the unrestricted setting, we depiet one of the Lyapunov functions of the RD (Figure 3 (Bottom)). Specifically, the Lyapunov function of our choice is
V(I)
Σ
nu (log(On,(())) log(1 (t))),
(31)
S&
JES
the average value of all the linearly independent Lyapunov functions defined in (19). We selected this specific Lyapumov function as the average is, in general, more numerically stable and for com- pactness.
27

---

Published as a conference paper at ICLR 2022
In Figure 3, verify that the RD of G. indeed, cycle in unrestricted setting (Theorem 3). The choice of initial points does not matter in this case; for completeness, we note that 01 = (0.1, 0.9, 0.2), and 02 (0.1, 0.9, 0.8) in all of the examples in this section.
Game History
Strategy Space of Rem
Strategy Space of TRam 2
Tomm2
T191
01233
60-
72P1
7272
0.
7259
Figure 4: An example of the RD of 2-Team Hidden Matching Pennies (Center) in re- stricted setting where 3 É S for all i E [3], k E [2] ((Left), and (Right)). In this case, the RD converges for any initial interior point (0(0), 1 (()). The evolution of 0(1), as a function of time, / [0, 100] is depicted in (Boltom).
As the first example in restricted setting (Figure 4), we are going to enforce $1,1 = S1.3 $2,1 [0.05, 0.4), and S1.2 = S2,2 $2.3 = [0.6, 0.95). First, observe that Sg,i C (0, 1) for all i e 33], k E [2]: hence, Assumption 3 is satisfied. Next, notice that Sk,s for all E [3], k E [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, 0 (0.4, 0.6, 0.4), and 0ž (0.05, 0.95, 0.95), as given in Theorem 4.
Game history
Strasgyy Space Ram
Strategy Space of Rea
0.6
Tham
7199
04002
2.0
0.2
0.1
39
00
02
09
08
100
0.0
02
64
3.0
71.11
0.8
T140
08-
1230
120
500 s0
Figure 5: An example of the RD of 2-Team Hidden Matching Pennies (Center) in re- stricted setting where E S1 and g S2, for all i [3] ((Left), and (Right)). this case the RD converges for any initial interior point (0(0), 1 - ((0)), but the point of convergence depends on the value of (0). The evolution of (t), as a function of time, f E [0, 100] is depicted in (Bottom).
28

---

Published as a conference paper at ICLR 2022
There exists similar setting (Figure 5), where the RD of G converge, well. Note, in this case, while & Sg,, for all i E [3], we let E $1, for some i E [3] (specifically, 2 E S1. for all i E [3] in this particular example). Although
did not provide 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 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 IF G space that the (t)) lies. Ultimately though, the dynamics can be shown to converge to a point 0", which depends not only on the initialization ((0) but also on the restrictions in the space parameters, Sk.i.
. [2]. The particular point of convergence for this example is 0f = (0.05, 0.95, 0.95), and 0% = (0.4, 0.6, 0.6), where the space restrictions are given as 22,1 = [0.05, 0.4], S2 = 22 = [0.6, 0.95j. and S = [0.05, 0.95] for all [3].
Strahacy Space
Crestway
3.0
7203
T2PC
11F1
02
12P4
33355
7.7L
7255
720
-13
-130
-20
200
Figure 6: An example of the RD of 2-Team Hidden Matching Pennies (Center) in re- stricted setting where 1 E S1.5, and E S2, for some i,j E [3] ((Left), and (Right)). this case the RD converge invariant functions for any initial interior point (0(0), 1 (()) The evolution of (t), as a function of time, f [0, 100) is depicted in (Bottom).
cycle defined by, at least, | + [ 1 linearly independent
Finally, we present an example of cycling behavior in the restricted setting (Figure 6) where we applied the restrictions $1,1 S1,3 [0.05, 0.8), S2.2 [0.6, 0.95), S2, [0.05, 0.4), and $2,3 = [0.2, 0.95). Note that 1 E SI.1, S1.3, S2 hence, |S|| + |S 3, and there exists is E [nx] for all A [2] such that 1 E Sp.i- By Theorem 5, it follows that the restricted RD cycle this case; specifically, they converge to an invariant set defined by (f) = O, and (0) O as given by (19). This behavior is depicted in Figure (Center). Notice how the Lyapunov function, V(0) (Figure (Bottom)) is monotonically increasing, and stabilizes at approximately t 25.
29


Reviews:
[{"review_id": "bdNBC-DyZBz", "reviewer": "Reviewer_qQLu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The ideas driving this paper are interesting, but the mathematical rigor is somewhat questionable. There are several points, partially detailed below, where either the presentation is unclear because of many flaws and typos in the writing, or at least not rigorously established. \n\nFurthermore, the analysis section is rather limited in terms of novelty. Proposition 1, can be deduced from Vlatakis-Gkaragkounis, E. V., Flokas, L., & Piliouras, G. (2020). Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent.\n\nThe strong and interesting parts of the paper are in Section 4.2 where a Lyapunov function for the dynamics on a finite sample is constructed. To form of the Lyapunov function is as expected, but the analysis is quite nice. \n\nThe weak parts are the sometimes ambiguous and unclear notation and a serious discussion on the computational issues involved in the proposed approach. In particular, there a several points the authors should take care of: \n\nThere are several technical problems with the paper.\n\n\t•\tI think the notation $\\varphi$ (for the saddle function) and $\\phi$ for the parameter of the generator is very unfortunate. Also, the notation for the domains of the mapping $F$ and $G$ seems to me messed up all over the paper. Be consistent with your notation. \n\n\t•\tThe way how example 2 is presented in misleading in my opinion. The key point is that the map $L(f,p)=log(f)+p log(1-f)$ is convex-concave. The way how it is written now could lead to the misunderstanding that it is a convex-concave function of x, which makes no sense of course. As a side remark, there is a typo $L_{x,x}$ should read as $L_{x,x’}$. Even more so, the definition proposed makes only sense for discrete distributions. Otherwise, the odds-ratio should be replaced with the Radon-Nikodym derivative. I also think that absolute continuity of the measures is needed. \n\n\t•\tI do not understand Example 4. In which sense do you want to approximate the random variable $x$. Almost surely? If so, with respect to which measure? How is $p_{\\theta}$ exactly constructed, and what should $f_{\\phi}$ be?\n \n\t•\tIn Proposition 1: Do you mean s is drawn from the product measure?\n\n\t•\tCompactness in Assumption 1 is a strong assumption. You work on a Banach space.\n\n\t•\tI am missing a proof of Proposition 2 and 3. In my opinion this is not as obvious as you work on a Banach space of functions. The topological details would be quite important to see here. At the current stage it looks to me like a heuristic. If it is a standard result, then at least you should provide references.\n\n\t• Explain eq. (13) better. I guess you want to say that your have one data point x and x' is the generator's realization? \n\n\t•\tSection 3.4: What is $F_{\\theta}\\times G_{\\phi}$? I guess you want to say that you measure distance in the parameter space via the $L^{2}(p)$ distance in the function space. What is $p$? Is it important for the metric? At least you should mention the domain from which mappings $F_{\\theta}$ and $G_{\\phi}$ are drawn. This is of course important to make these definition meaningful. \n\n\t•\tSection 6: It would be nice to have some (perhaps speculative) discussion why GDA does perform worse than natural gradient in this example. Has it something to do with the fact that the game of choice has a unique interior equilibrium? Also, what would happen if the equilibrium is at the boundary? In my understanding the dynamics would not be defined on the boundary, so what can be said here? \n\n\t•\tProposition A.1: What is f? I guess the potential, but it is not explained. In any case, it is not needed in this Proposition.\n\n\t•\tProposition A.2 is problematic: First the partial derivative of \\Psi does not exist as written here, unless a proper extension is defined. The way it is currently written, it suggest that it is defined on the probability simplex, which is an affine space for which only directional derivatives can be defined. The notation is also very confusing and it seems that it has not been polished carefully enough.\n\n\t•\tThe $N$ is reserved for the natural numbers, sorry. The current notation is absolutely unacceptable. \n\n\t•\tProposition 1 uses notation that has not been defined before. In any case, the result is classical; See e.g. the textbook by Sandholm „Population games and evolutionary dynamics“, a standard reference in game theory. In general, the Lyapunov functions proposed here can also be found in that reference, as well as the invariance functions for matching pennies (and other zero sum games).\n\n\t•\tLemma 1 should be $m_{1}$ and $m_{2}$. \n\n", "summary_of_the_paper": "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. ", "summary_of_the_review": "The ideas driving this paper are interesting, but the mathematical rigor is somewhat questionable. There are several points, partially detailed below, where either the presentation is unclear because of many flaws and typos in the writing, or at least not rigorously established. Overall I appreciated the contribution, but consider it as a borderline. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ZF3t_80Upg", "reviewer": "Reviewer_5G2k", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Understanding nonconvex-nonconcave games is pretty important, here the topic is pretty interesting. The paper is basically clearly written, while sometimes hard to follow because of the notations.\n\nMy main concerns are as follow:\n1. Compare with existing works. A closely related work should be the analysis of GDA in HCC games (Flokas et al. 2021), which authors also compare in experiments. Currently the theorem seems to suggest that natural gradient also attains a Lyapunov function, compared to GDA. It would be better if authors add more discussion on the difference compared to GDA. Currently I found that the Lyapunov function of natural gradient is different from that in (Flokas et al. 2021), and easier, is it the benefit in the analysis?\n\n2. By changing to natural gradient, it should be expected that the convergence will be faster compared to GD, with a cost of inversing matrices. Here authors provide some evidence in experiments. Is there any theoretical evidence to justify the claim that natural gradient is faster than GDA?\n\nSome minor thoughts:\n1. I thought the terminology \"modified version of Gradient Descent-Ascent\" is a little misleading. At first I thought it will be some common variants of GDA, e.g., EG, OGDA... While here it is natural gradient flow, which requires a matrix inversion.\n\nGenerally I think the paper is interesting, but it would be better if authors can provide more insights on it. I will appreciate the authors to address my confusions, and definitely reconsider my decision. Thank you very much.", "summary_of_the_paper": "The paper studied the dynamics of a natural gradient flow in hidden convex-concave problems, and showed that the natural gradient flow attains global convergence to stationary points.", "summary_of_the_review": "Interesting results while it would be better to add more discussions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XzJ49VVFwT", "reviewer": "Reviewer_Wrtu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper focuses on the particularly interesting class of games known hidden convex-concave games. As the authors point out, this class encompasses many important applications within the setting of min-max optimization, including adversarial example games and GANs. A unifying treatment of such settings is particularly compelling, and a very promising setting. Nonetheless, overall the paper fails to convince about the originality and the significance of the results.\n\nFirst of all, on of the key points stressed by the authors is that they establish global convergence guarantees. However, it is unclear how this result relates and compares to the existing ones in the context of HCC; e.g. Flokas et al. Solving Min-Max Optimization with Hidden Structure via Gradient Descent/Ascent. The latter paper also presents global convergence results, and a more detailed discussion/comparison with these results is missing. Another caveat is that the analysis they present does not offer a rate of convergence, while as the authors acknowledge the studied dynamics appear to not scale in practice as the involve computing (pseudo)inverses of matrices at every iteration. There have been some techniques to address such issues in the literature (e.g. using sketching), so the authors should definitely consider addressing this intractability issue. A minor unsatisfactory issue is that the analysis is performed in continuous-time and not in discrete-time, but I should note that this is common in this line of work. \n\nWith regards to Section 5, the persistence of limit cycles in such settings is a very well-known result. The authors make a further fine-grained characterization of the dynamics, using invariant function analysis, but the importance of such a characterization is not clear; perhaps the authors could explain this point further. It is also perhaps unsatisfactory that the results in Section 5 are only applicable for the specific example of the hidden matching pennies game. Finally, the experimental results are somewhat weak and have only been applied for toy examples. Overall, the practical importance of the results is questionable. \n\nPost Discussion: I thank the authors for the detailed response which addressed some of my concerns/misunderstandings. I would recommend clarifying further the results of Section 5 for the revised version. The importance of these results and a comparison with existing works appears can be further highlighted. ", "summary_of_the_paper": "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. ", "summary_of_the_review": "Overall, the authors study a very interesting emerging setting, covering many important applications. However, the progress appears to be only incremental, and comparisons with existing results appear to be missing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Vx6v9S_4d9", "reviewer": "Reviewer_PUzM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "strengths:\n\nThe observation that a lot of practical problems including GANs and AEGs are HCC games is interesting and useful, which motivated the proposed NHG method in this work.\n\nThe proposed NHG is guaranteed to converge to a Nash equilibrium in the HCC game setting and it can be used to explain cycling behaviour of RD by using a certain metric.\n\nThe presentation of results and ideas is clear and easy to understand.\n\nweakness:\n\nI am concerned the proposed NHG method is not scalable and could not be extended to other non-convex settings (like neural networks and GANs as mentioned in the examples).\n\n1. The proposed NHG method is a preconditioning gradient update such that $F$ and $G$ are updated following standard gradient descent ascent update. This would require the preconditioning matrix (e.g., pseudo inverse Fisher) be able to recover from the gradient of $\\theta$ the information in the gradient of $F$ and $G$. This is possible if $\\theta$ are not low dimensional comparing with $F$ and $G$. However, suppose we use some compact feature and low dimensional $\\theta$, then could the author comment how this is achievable (preconditioning low dimensional gradient of $\\theta$ can behave like doing gradient update on $F$ and $G$)?\n\n2. As also noted by the authors, the preconditioning requires expensive computational expenses, which seems to be a problem if we have neural networks weights as $\\theta$.\n\n\n", "summary_of_the_paper": "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$.\n\nUnder 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$.\n\nThe 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.\n\nThe 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.\n\nFinally, the authors conducted simulations to verify the proposed NHG method, showing that it is more stable than Gradient Descent-Ascent (GDA).", "summary_of_the_review": "Overall, this paper makes an interesting observation about the HCC game setting and proposes a reasonable NHG method, reducing the non-convex non-concave problem to a convex-concave problem. However, I am concerned with the preconditioning in the NHG method, making it not scalable and potentially not possible to be used in other non-convex settings. Therefore, I make a borderline decision for the current moment. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the convergence of a generalized gradient descent ascent (GDA) flow in certain classes of nonconvex-nonconcave min-max setups. While the nonconvex-nonconcave setups are computationally intractable and GDA is known to converge even in some convex-concave setups, the paper argues that (generalized) GDA can converge on what is dubbed "Hidden Convex-Concave Games" in the paper and argued that it contains GANs as a special case.

The reviewers all found the paper interesting and a worthy contribution to the literature on nonconvex-nonconcave zero-sum games. Main concerns expressed by the reviewers were w.r.t. the lack of convergence rate established for the considered dynamics, novelty compared to existing work, and practical usefulness of the considered scheme, as it involves preconditioning/matrix inversion. The authors made an effort to address all the concerns, to the extent possible.

Given the complexity of nonconvex-nonconcave min-max setups, their importance in GAN training, and the insightful perspective on hidden convexity/concavity in typical problem instances, I would like to see this paper published at ICLR. I would, however, strongly advise the authors to take all of the reviewers' comments into account when preparing a revision.
Decision: Accept (Poster)