Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent
Year: 2022

Abstract:
Many recent AI architectures are inspired by zero-sum games, however, the behavior of their dynamics is still not well understood. Inspired by this, we study standard gradient descent ascent (GDA) dynamics in a specific class of non-convex nonconcave zero-sum games, that we call hidden zero-sum games. In this class, players control the inputs of smooth but possibly non-linear functions whose outputs are being applied as inputs to a convex-concave game. Unlike general zero-sum games, these games have a well-defined notion of solution; outcomes that implement the von-Neumann equilibrium of the “hidden" convex-concave game. We provide conditions under which vanilla GDA provably converges not merely to local Nash, but the actual von-Neumann solution. If the hidden game lacks strict convexity properties, GDA may fail to converge to any equilibrium, however, by applying standard regularization techniques we can prove convergence to a von-Neumann solution of a slightly perturbed zero-sum game. Our convergence results are non-local despite working in the setting of non-convex non-concave games. Critically, under proper assumptions we combine the Center-Stable Manifold Theorem along with novel type of initialization dependent Lyapunov functions to prove that almost all initial conditions converge to the solution. Finally, we discuss diverse applications of our framework ranging from generative adversarial networks to evolutionary biology.

heading: 1 Introduction
text: Traditionally, our understanding of convex-concave games revolves around von Neumann’s celebrated minimax theorem, which implies the existence of saddle point solutions with a uniquely defined value. These solutions are called von Nemann solutions and guarantee to each agent their corresponding value regardless of opponent play. Although many learning algorithms are known to be able to compute such saddle points [13], recently there has there has been a fervor of activity in proving stronger results such as faster regret minimization rates or analysis of the day-to-day behavior [46, 17, 7, 1, 66, 19, 2, 45, 5, 25, 70, 29, 6, 48, 30, 56].
This interest has been largely triggered by the impressive successes of AI architectures inspired by min-max games such as Generative Adversarial Networks (GANS) [26], adversarial training [40] and reinforcement learning self-play in games [63]. Critically, however, all these applications are based upon non-convex non-concave games, our understanding of which is still nascent. Nevertheless,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
some important early work in the area has focused on identifying new solution concepts that are widely applicable in general min-max games, such as (local/differential) Nash equilibrium [3, 41], local minmax [18], local minimax [31], (local/differential) Stackleberg equilibrium [24], local robust point [69]. The plethora of solutions concepts is perhaps suggestive that “solving" general min-max games unequivocally may be too ambitious a task. Attraction to spurious fixed points [18], cycles [65], robustly chaotic behavior [15, 16] and computational hardness issues [20] all suggest that general min-max games might inherently involve messy, unpredictable and complex behavior.
Are there rich classes of non-convex non-concave games with an effectively unique game theoretic solution that is selected by standard optimization dynamics (e.g. gradient descent)?
Our class of games. We will define a general class of min-max optimization problems, where each agent selects its own vectors of parameters which are then processed separately by smooth functions. Each agent receives their respective payoff after entering the outputs of the processed decision vectors as inputs to a standard convex-concave game. Formally, there exist functions F : RN → X ⊂ Rn and G : RM → Y ⊂ Rm and a continuous convex-concave function L : X × Y → R, such that the min-max game is
min θ∈RN max φ∈RM L(F(θ),G(φ)). (Hidden Convex-Concave (HCC))
We call this class of min-max problems Hidden Convex-Concave Games. It generalizes the recently defined hidden bilinear games of [65].
Our solution concept. Out of all the local Nash equilibria of HCC games, there exists a special subclass, the vectors (θ∗,φ∗) that implement the von Neumann solution of the convex-concave game. This solution has a strong and intuitive game theoretic justification. Indeed, it is stable even if the agents could perform arbitrary deviations directly on the output spaces X,Y . These parameter combinations (θ∗,φ∗) “solve" the “hidden” convex-concave L and thus we call them von Neumann solutions. Naturally, HCCs will typically have numerous local saddle/Nash equilibria/fixed points that do not satisfy this property. Instead, they correspond to stationary points of the F,G where their output is stuck, e.g., due to an unfortunate initialization. At these points the agents may be receiving payoffs which can be arbitrarily smaller/larger than the game theoretic value of game L. Fortunately, we show that Gradient Descent Ascent (GDA) strongly favors von Neumann solutions over generic fixed points.
Our results. In this work, we study the behavior of continuous GDA dynamics for the class of HCC games where each coordinate of F,G is controlled by disjoint sets of variables. In a nutshell, we show that GDA trajectories stabilize around or converge to the corresponding von Neumann solutions of the hidden game. Despite restricting our attention to a subset of HCC games, our analysis has to overcome unique hurdles not shared by standard convex concave games.
Challenges of HCC games. In convex-concave games, deriving the stability of the von Neumann solutions relies on the Euclidean distance from the equilibrium being a Lyapunov function. In contrast, in HCC games where optimization happens in the parameter space of θ,φ, the non-linear nature of F,G distorts the convex-concave landscape in the output space. Thus, the Euclidean distance will not be in general a Lyapunov function. Moreover, the existence of any Lyapunov function for the trajectories in the output space of F,G does not translate to a well-defined function in the parameter space (unless F,G are trivial, invertible maps). Worse yet, even if L has a unique solution in the output space, this solution could be implemented by multiple equilibria in the parameter space and thus each of them can not be individually globally attracting. Clearly any transfer of stability or convergence properties from the output to the parameter space needs to be initialization dependent. It is worth mentioning that similar challenges like transfering results from the output to the input space was also faced in the simpler class of hidden bilinear games. However, [65] to sidestep this issue assume the restricitve requirement of F,G to be invertible operators. Our results go beyond this simplified case requiring new proof techniques. Specifically, we show how to combine the powerful technologies of the the Center-Stable Manifold Theorem, typically used to argue convergence to equilibria in non-convex optimization settings [34, 52, 54, 53, 35], along with a novel Lyapunov function argument to prove that almost all initial conditions converge to the our game theoretic solution.
Lyapunov Stability. Our first step is to construct an initialization-dependent Lyapunov function that accounts for the curvature induced by the operators F and G (Lemma 2). Leveraging a potentially
infinite number of initialization-dependent Lyapunov functions in Theorem 5 we prove that under mild assumptions the outputs of F,G stabilize around the von Neumann solution of L.
Convergence. Mirroring convex concave games, we require strict convexity or concavity of L to provide convergence guarantees to von Neumann solutions (Theorem 6). Barring initializations where von Neumann solutions are not reachable due to the limitations imposed by F and G, the set of von Neumann solutions are globally asymptotically stable (Corollary 1). Even in non-strict HCC games, we can add regularization terms to make L strictly convex concave. Small amounts of regularization allows for convergence without significantly perturbing the von Neumann solution (Theorem 7) while increasing regularization enables exponentially faster convergence rates (Theorem 8). Similar to the aforementioned theoretical work, our model of HCC games provides a formal and theoretical tractable testbed for evaluating the performance of different training methods in GAN inspired architectures. As a concrete example, [36] recently proved the success of WGAN training for learning the parameters of non-linearly transformed Gaussian distributions, where for simplicity they replaced the typical Lipschitz constraint of the discriminator function with a quadratic regularizer. Interestingly, we can elucidate on why regularized learning is actually necessary by establishing a formal connection to HCC games. On top of other such ML applications, our game theoretic framework can furthermore capture and generalize evolutionary game theoretic models. [57] analyze a model of evolutionary competition between two species (host-parasite). The outcome of this competition depends on their respective phenotypes (informally their properties, e.g., agility, camouflage, etc.). These phenotypes are encoded via functions that map input vectors (here genotype/DNA sequences) to phenotypes. While [57] proved that learning in these games does not converge to equilibria and typically cycles for almost all initial conditions, we can explicitly construct initial conditions that do not satisfy our definition of safety and end up converging to artificial fixed points. Safety conditions aside, we show that a slight variation of the evolutionary/learning algorithm suffices to resolve the cycling issues and for the dynamics to equilibrate to the von Neumann solution. Hence, we provide the first instance of team zero-sum games [62], a notoriously hard generalization of zero-sum games with a large duality gap, that is solvable by decentralized dynamics.
Organization. In Section 2 we provide some preliminary notation, the definition of our model and some useful technical lemmas. Section 3 is devoted to the presentation of our the main results. Section 4 discusses applications of our framework to specific GAN formulations. Section 5 concludes our work with a discussion of future directions and challenges. We defer the full proofs of our results as well as further discussion on applications to the Appendix.

heading: 2 Preliminaries

heading: 2.1 Notation
text: Vectors are denoted in boldface x,y unless otherwise indicated are considered as column vectors. We use ‖·‖ to denote the `2−norm. For a function f : Rd → R we use ∇f to denote its gradient. For functions of two vector arguments, f(x,y) : Rd1 × Rd2 → R , we use ∇xf,∇yf to denote its partial gradient. For the time derivative we will use the dot accent abbreviation, i.e., ẋ = ddt [x(t)]. A function f will belong to Cr if it is r times continuously differentiable. Additionally, f ◦ g = f(g(·)) denotes the composition of f, g. Finally, the term “sigmoid” function refers to σ : R→ R such that σ(x) = (1 + e−x)−1.

heading: 2.2 Hidden Convex Concave Games
text: θ11 θ12 · · · θ1n1 θ1 f1(θ1)
...
θN1 θN2 · · · θNnN θN fN (θN )
F(θ) L(F(θ),G(φ))
φ11 φ12 · · · φ1n1 φ1 g1(φ1)
...
φM1 φM2 · · · φMnM φM gM (φM )
G(φ)
θ̇i = −∇θiL(F(θ),G(φ)) φ̇j = ∇φjL(F(θ),G(φ))Figure:Hidden Seperable Zero-Sum Game Model & Optimization Dynamics
We will begin our discussion by defining the notion of convex concave functions as well as strictly convex concave functions. Note that our definition of strictly convex concave functions is a superset of strictly convex strictly concave functions that are usually studied in the literature. Definition 1. L : Rn × Rm → R is convex concave if for every y ∈ Rn L(·,y) is convex and for every x ∈ Rm L(x, ·) is concave. Function L will be called strictly convex concave if it is convex concave and for every x×y ∈ Rn×Rm either L(·,y) is strictly convex or L(x, ·) is strictly concave.
At the center of our definition of HCC games is a convex concave utility function L. Additionally, each player of the game is equipped with a set of operator functions. The minimization player is equipped with n functions fi : Rni → R while the maximization player is equipped with m functions gj : Rmj → R. We will assume in the rest of our discussion that fi, gj , L are all C2 functions. The inputs θi ∈ Rni and φj ∈ Rmj are grouped in two vectors
θ = [ θ1 · · · θn ]> F(θ) = [ f1(θ1) · · · fn(θn) ]> φ = [ φ1 · · · φm ]> G(φ) = [ g1(φ1) · · · gm(φm)
]> We are ready to define the hidden convex concave game
(θ∗,φ∗) = arg min θ∈RN arg max φ∈RM L(F(θ),G(φ)).
where N = ∑n i=1 ni and M = ∑m j=1mj . Given a convex concave function L, all stationary points of L are (global) Nash equilibria of the min-max game. We will call the set of all equilibria of L, von Neumann solutions of L and denote them by Solution(L). Unfortunately, Solution(L) can be empty for games defined over the entire Rn × Rm. For games defined over convex compact sets, the existence of at least one solution is guaranteed by von Neumann’s minimax theorem. Our definition of HCC games can capture games on restricted domains by choosing appropriately bounded functions fi and gj . In the following sections, we will just assume that Solution(L) is not empty. We note that our results hold for both bounded and unbounded fi and gj . We are now ready to write down the equations of the GDA dynamics for a HCC game:
θ̇i = −∇θiL(F(θ),G(φ)) =−∇θifi(θi) ∂L
∂fi (F(θ),G(φ))
φ̇j = ∇φjL(F(θ),G(φ)) =∇φjgj(φj) ∂L
∂gj (F(θ),G(φ))
(1)

heading: 2.3 Reparametrization
text: The following lemma is useful in studying the dynamics of hidden games. Lemma 1. Let k : Rd → R be a C2 function. Let h : R→ R be a C1 function and x(t) denote the unique solution of the dynamical system Σ1. Then the unique solution for dynamical system Σ2 is z(t) = x(
∫ t 0 h(s)ds){
ẋ = ∇k(x) x(0) = xinit
} : Σ1 { ż = h(t)∇k(z)
z(0) = xinit
} : Σ2 (2)
By choosing h(t) = −∂L(F(t),G(t))/∂fi and h(t) = ∂L(F(t),G(t))/∂gj respectively, we can connect the dynamics of each θi and φj under Equation (1) to gradient ascent on fi and gj . Applying Lemma 1, we get that trajectories of θi and φj under Equation (1) are restricted to be subsets of the corresponding gradient ascent trajectories with the same initializations. For example, in Figure 1 θi(t) can not escape the purple section if it is initialized at (a) neither the orange section if it is initialiazed at (f). This limits the attainable values that fi(t) and gj(t) can take for a specific initialization. Let us thus define the following: Definition 2. For each initialization x(0) of Σ1, Imk(x(0)) is the image of k ◦ x : R→ R.
Applying Definition 2 in the above example, Imfi(θi(0)) = (fi(−2), fi(−1)) if θi is initialized at (c). Additionally, observe that in each colored section fi(θi(t)) uniquely identifies θi(t). Generally, even in the case that θi are vectors, Lemma 1 implies that for a given θi(0), fi(θi(t)) uniquely identifies θi(t). As a result we get that a new dynamical system involving only fi and gj Theorem 1. For each initialization (θ(0),φ(0)) of Equation (1), there are C1 functions Xθi(0) , Xφj(0) such that θi(t) = Xθi(0)(fi(t)) and φj(t) = Xφj(0)(gj(t)). If (θ(t),φ(t)) satisfy Equation (1) then fi(t) = fi(θi(t)) and gj(t) = gj(φj(t)) satisfy
ḟi = −‖∇θifi(Xθi(0)(fi))‖ 2 ∂L
∂fi (F,G)
ġj = ‖∇φjgj(Xφj(0)(gj))‖ 2 ∂L
∂gj (F,G)
(3)
By determining the ranges of fi and gj , an initialization clearly dictates if a von Neumann solution is attainable. In Figure 1 for example, any point of the pink, orange or blue colored section like (e), (f) or (g) can not converge to a von Neumann solution with fi(θi) = f∗i . The notion of safety captures which initializations can converge to a given element of Solution(L).
Definition 3. . We will call the initialization (θ(0),φ(0)) safe for a (p,q) ∈ Solution(L) ifφi(0) and θj(0) are not stationary points of fi and gj respectively and pi ∈ Imfi(θi(0)) and qj ∈ Imgj (φj(0)).
Leveraging the Center-Stable Manifold Theorem [55], the following observation shows that under mild assumptions almost all initializations are safe:
Theorem 2. If fi and gj have isolated stationary points, only strict saddle points, compact sublevel-sets, both equilibria pi ∈ (max LocalMin(fi),min LocalMax(fi)) and qj ∈ (max LocalMin(gj),min LocalMax(gj)), then almost all initializations are safe for a (p,q) ∈ Solution(L).
Finally, in the following sections we use some fundamental notions of stability. We call an equilibrium x∗ of an autonomous dynamical system ẋ = D(x(t)) stable if for every neighborhood U of x∗ there is a neighborhood V of x∗ such that if x(0) ∈ V then x(t) ∈ U for all t ≥ 0. We call a set S asymptotically stable if there exists a neighborhoodR such that for any initialization x(0) ∈ R, x(t) approaches S as t→ +∞. IfR is the whole space the set globally asymptotically stable.

heading: 3 Learning in Hidden Convex Concave Games

heading: 3.1 General Case
text: Our main results are based on designing a Lyapunov function for the dynamics of Equation (3):
Lemma 2. If L is convex concave and (φ(0), θ(0)) is a safe for (p,q) ∈ Solution(L), then the following quantity is non-increasing under the dynamics of Equation (3):
H(F,G) = N∑ i=1 ∫ fi pi z − pi ‖∇fi(Xθi(0)(z))‖2 dz + M∑ j=1 ∫ gj qj z − qj ‖∇gj(Xφj(0)(z))‖2 dz (4)
F(θ)
G (φ
)
(p,q)
Figure 2: Level sets of Lyapunov function of Equation (4) for both F and G being one dimensional sigmoid functions.
Observe that our Lyapunov function here is not the distance to (p,q) as in a classical convex concave game. The gradient terms account for the non constant multiplicative terms in Equation (3). Indeed if the game was not hidden and fi and gj were the identity functions then H would coincide with the Euclidean distance to (p,q). Our first theorem employs the above Lyapunov function to show that (p,q) is stable for Equation (3).
Theorem 3. If L is convex concave and (φ(0), θ(0)) is a safe for (p,q) ∈ Solution(L), then (p,q) is stable for Equation (3).
Clearly, for the special case of globally invertible functions F,G we could come up with an equivalent Lyapunov function in the θ,φ-space. In this case it is straightforward to transfer the stability results from the induced dynamical system of F,G (Equation (3)) to the initial dynamical system of θ,φ (Equation (1)). For example we can prove the following result: Theorem 4. If fi and gj are sigmoid functions and L is convex concave and there is a (φ(0), θ(0)) that is safe for (p,q) ∈ Solution(L), then (F−1(p),G−1(q)) is stable for Equation (1). In the general case though, stability may not be guaranteed in the parameter space of Equation (1). We will instead prove a weaker notion of stability, which we call hidden stability. Hidden stability captures that if (F(θ(0)),G(φ(0))) is close to a von Neumann solution, then (F(θ(t)),G(φ(t))) will remain close to that solution. Even though hidden stability is weaker, it is essentially what we are interested in, as the output space determines the utility that each player gets. Here we provide sufficient conditions for hidden stability. Theorem 5 (Hidden Stability). Let (p,q) ∈ Solution(L). Let Rfi and Rgj be the set of regular values1 of fi and gj respectively. Assume that there is a ξ > 0 such that [pi − ξ, pi + ξ] ⊆ Rfi and [qj − ξ, qj + ξ] ⊆ Rgj . Define
r(t) = ‖F(θ(t))− p‖2 + ‖G(φ(t))− q‖2. If fi and gj are proper functions2, then for every > 0, there is an δ > 0 such that
r(0) < δ =⇒ ∀t ≥ 0 : r(t) < .
Unfortunately hidden stability still does not imply convergence to von Neumann solutions. [65] studied hidden bilinear games and proved that Ḣ = 0 for this special class of HCC games. Hence, a trajectory is restricted to be a subset of a level set of H which is bounded away from the equilibrium as shown in Figure 2. To sidestep this, we will require in the next subsection the hidden game to be strictly convex concave.

heading: 3.2 Hidden strictly convex concave games
text: In this subsection we focus on the case where L is a strictly convex concave function. Based on Definition 1, a strictly convex concave game is not necessarily strictly convex strictly concave and thus it may have a continum of von Neumann solutions. Despite this, LaSalle’s invariance principle, combined with the strict convexity concavity, allows us to prove that if (θ(0),φ(0)) is safe for Z ⊆ Solution(L) then Z is locally asymptotically stable for Equation (3). Lemma 3. Let L be strictly convex concave and Z ⊂ Solution(L) is the non empty set of equilbria of L for which (θ(0),φ(0)) is safe. Then Z is locally asymptotically stable for Equation (3).
The above lemma however does not suffice to prove that for an arbitrary initialization (θ(0),φ(0)), (F(t),G(t)) approaches Z as t→ +∞. In other words, a-priori it is unclear if (F(θ(0)),G(φ(0))) is necessarily inside the region of attraction (ROA) of Z. To get a refined estimate of the ROA of Z, we analyze the behavior of H as fi and gj approach the boundaries of Imfi(θi(0)) and Imgj (φj(0)) and more precisely we show that the level sets of H are bounded. Once again the corresponding analysis is trivial for convex concave games, since the level sets are spheres around the equilibria. Theorem 6. Let L be strictly convex concave and Z ⊂ Solution(L) is the non empty set of equilbria of L for which (θ(0),φ(0)) is safe. Under the dynamics of Equation (1) (F(θ(t)),G(θ(t))) converges to a point in Z as t→∞. The theorem above guarantees convergence to a von Neumann solution for all initializations that are safe for at least one element of Solution(L). However, this is not the same as global asymptotic stability. To get even stronger guarantees, we can assume that all initializations are safe. In this case it is straightforward to get a global asymptotic stability result: Corollary 1. Let L be strictly convex concave and assume that all intitializations are safe for at least one element of Solution(L). The following set is globally asymptotically stable for continuous GDA dynamics.
{(θ∗,φ∗) ∈ Rn × Rm : (F (θ∗), G(φ∗)) ∈ Solution(L)} 1A value a ∈ Im f is called a regular value of f if ∀q ∈ dom f : f(q) = a, it holds∇f(q) 6= 0. 2A function is proper if inverse images of compact subsets are compact.
Notice that the above approach on global asymptotic convergence using Lyapunov arguments can be extended to other popular alternative gradient-based heuristics like variations of Hamiltonian Gradient Descent. For concision, we defer the exact statements, proofs in the supplement.

heading: 3.3 Convergence via regularization
text: Regularization is a key technique that works both in the practice of GANs [47, 33] and in the theory of convex concave games [56, 59, 60]. Our settings of hidden convex concave games allows for provable guarantees for regularization in a wide class of settings, bringing closer practical and theoretical guarantees. Let us have a utility L(x,y) that is convex concave but not strictly. Here we will propose a modified utility L′ that is strictly convex strictly concave. Specifically we will choose
L′(x,y) = L(x,y) + λ 2 ‖x‖2 − λ 2 ‖y‖2
The choice of the parameter λ captures the trade-off between convergence to the original equilibrium of L and convergence speed. On the one hand, invoking the implicit function theorem, we get that for small λ the equilibria of L are not significantly perturbed. Theorem 7. If L is a convex concave function with invertible Hessians at all its equilibria, then for each > 0 there is a λ > 0 such that L′ has equilibria that are -close to the ones of L.
Note that invertibility of the Hessian means that L must have a unique equilibrium. On the other hand increasing λ increases the rate of convergence of safe initializations to the perturbed equilibrium. Theorem 8. Let (θ(0),φ(0)) be a safe initialization for the unique equilibrium of L′ (p,q). If
r(t) = ‖F(θ(t))− p‖2 + ‖G(φ(t))− q‖2
then there are initialization dependent constants c0, c1 > 0 such that r(t) ≤ c0 exp(−λc1t).

heading: 4 Applications
text: In this section, we discuss how HCC framework can be used to give new insights in a variety of application areas including min-max training for GANs and Evolutionary Game Theory. We also describe applications of regularization to normal form zero sum games in Appendix D.3.
Hidden strictly convex-concave games. We will start our discussion with the fundamental generative architecture of [26]’s GAN. In the vanilla GAN architecture, as it is commonly referred, our goal is to find a generator distribution pG that is close to an input data distribution pdata. To find such a generator function, we can use a discriminator D that “criticizes” the deviations of the generator from the input data distribution. For the case of a discrete pdata over a set N , the minimax problem of [26] is the following:
min pG(x)≥0,∑
x∈N pG(x)=1
max D∈(0,1)|N| V (G,D)
where V (G,D) = ∑ x∈N pdata(x) log(D(x)) + ∑ x∈N pG(x) log(1 −D(x)). The problem above can be formulated as a constrained strictly convex-concave hidden game. On the one hand, for a fixed discriminator D∗, the V (G,D∗) is linear over the pG(x). On the other hand, for a fixed generator G∗,
V (G∗, D) is strongly-concave. We can implement the inequality constraints on both the generator probabilities and discriminator using sigmoid activations. For the equality constraint ∑ x∈N pG(x) = 1 we can introduce a Langrange multiplier. Having effectively removed the constraints, we can see in Figure 3, the dynamics of Equation (1) converge to the unique equilibrium of the game, an outcome consistent with our results in Corollary 1. While the Euclidean distance to the equilibrium is not monotonically decreasing, H(t) is.
Hidden convex-concave games & Regularizaiton. An even more interesting case is Wassertein GANs–WGANs [4]. One of the contributions of [36] is to show that WGANs trained with Stochastic GDA can learn the parameters of Gaussian distributions whose samples are transformed by non-linear activation functions. It is worth mentioning that the original WGAN formulation has a Lipschitz constraint in the discriminator function. For simplicity, [36] replaced this constraint with a quadratic regularizer. The min-max problem for the case of one-dimensional Gaussian N (0, α2∗) and linear discriminator Dv(x) = v>x with x2 activation is:
min α∈R max v∈R
VWGAN(Gα, Dv) = EX∼pdata [D(X)]− EX∼pG [D(X)]− v2/2
= Ex∼N (0,α2∗)2 [vx]− Ex∼N (0,α2)2 [vx]− v 2/2
= (α2∗ − α2)v − v2/2 Observe that VWGAN is not convex-concave but it can posed as a hidden strictly convex-concave game with G(α) = (α2∗−α2) and F(v) = v. When computing expectations analytically without sampling, Theorem 6 guarantees convergence. In contrast, without the regularizer VWGAN can be modeled as a hidden bilinear game and thus GDA dynamics cycle. Empirically, these results are robust to discrete and stochastic updates using sampling as shown in Figure 4. Therefore regularization in the work of [36] was a vital ingredient in their proof strategy and not just an implementation detail.
The two applications of HCC games in GANs are not isolated findings but instances of a broader pattern that connects HCC games and standard GAN formulations. As noted by [27], if updates in GAN applications were directly performed in the “functional space”, i.e. the generator and discriminator outputs, then standard arguments from convex concave optimization would imply convergence to global Nash equilibria. Indeed, standard GAN formulations like the vanilla GAN [26], f-GAN [50] and WGAN [4] can all be thought of as convex concave games in the space of generator and discriminator outputs. Given that the connections between convex concave games and standard GAN objectives in the output space is missing from recent literature, in Appendix D.1 we show how one can apply Von Neumann’s minimax theorem to derive the optimal generators and discriminators even in the non-realizable case. In practice, the updates happen in the parameter space and thus convexity arguments no longer apply. Our study of HCC games is a stepping stone towards bridging the gap in convergence guarantees between the case of direct updates in the output space and the parameter space.
Evolutionary Game Theory & Biology. The study of learning dynamics in games has always been strongly and inherently connected with mathematical models of biology and evolution. Typically, this line of research is studied under the name of Evolutionary Game Theory [28, 67]. Zero-sum games and variants thereof are of particular interest for this line of work as they encode settings of direct competition between species (e.g., prey-predator or host-parasite/virus). Even in the simplest such setting of matrix zero-sum games, used to capture competition between asexually reproducing species, it is well known that the emerging dynamics can be non-equilibrating and even chaotic [61, 58].
Studying the effects of evolutionary competition between sexually evolving species results in significantly more intricate models, as it does not suffice to merely keep track of the fractions of the different types of individuals that self-replicate. Instead it is necessary to keep a much more detailed accounting of the evolution of the frequencies of different genes that get reshuffled and recombined to create new individuals, whilst giving evolutionary preference to the most fit individuals given the current environment. Recent work on intersection of learning theory and game theory has provided concrete such game theoretic models [37, 14, 44, 42]. Due to the intricate nature of their dynamics, deciding even the simplest questions in regards to them (e.g. does genetic diversity survive or not?) is typically computationally hard [43].
A notable exception, where the dynamics of sexual evolution and, in fact, sexual competition have been relatively thoroughly understood, is the work of [57], on two species (host-parasite) antagonism. The outcome of this competition depends on their respective phenotypes (informally their properties, e.g., large wings versus small wings.) of the two species. The crucial assumption that makes this model theoretically tractable is that the phenotype for each species is a Boolean attribute (this assumption is also used [38]). Despite these simplifications, the dynamics are still not equilibrating and are, in fact, cyclic for almost all initial conditions. Two natural questions emerge: 1) Is the almost everywhere condition necessary? I.e. Do there exist initial conditions which are not cyclic? 2) More importantly, can a slightly perturbed dynamic stabilize these systems and converge to a meaningful equilibrium? Next, we will see how our framework addresses both of these questions.
To understand the connection these we will examine the model of [57] in more detail. Concretely, the phenotype of species A,B can be described as a Boolean function over the species genome which is encoded by a binary string (this acts as a simplified version of a DNA string). While the phenotype plays the dominant role for the survival of the species, sexual reproduction modifies only the genotype of an organism. As a result the species are actually involved in a hidden zero-sum game. More formally, each species is game-theoritically represented as a team of agents where each agent controls one bit of the genotype:
GA = (g A 1 , · · · , gAn ),GB = (gB1 , · · · , gBm)
uA = L[PhenotypeA(GA),PhenotypeB(GB)] uB = −uA
Where gAi , g B j ∈ {0, 1}, PhenotypeA,PhenotypeB is a Boolean function (e.g., AND,XOR) and L is a 2× 2 matrix encoding a zero-sum game (e.g., Matching Pennies). Naturally, one can allow agents to use randomized/mixed strategies in which case the expected utilities of all agents/genes are defined using the standard multi-linear extension of utilities. Thus, these models of evolutionary sexual competition share the same basic structure as hidden linear-linear games, which explains their recurrent, non-equilibrating nature [65].
In Figure 5, each gene/agent gAi tunes one real variable θi such that Pr[g A i = 1] = σ(θi) and gene/agent gBj tunes one real variable φj correspondingly. Choosing as Boolean phenotype to be the XOR of two genes, almost all initializations are safe for any bilinear game with a mixed equilibrium. Actually, only the case θ1(0) = θ2(0) or φ1(0) = φ2(0) can be problematic, since for XOR the expected phenotype is bounded in [0, 0.5] and a mixed equilibrium out of this range would be infeasible. Finally, leveraging Theorem 7, we can design a regularized version of the game such that the dynamics converge arbitrarily close to the true von Neumann solution of these games, which is encoded by the min-max strategies of the hidden bi-linear zero-sum game.

heading: 5 Discussion & Future Work
text: While this work is a promising first step towards understanding GAN training, significant challenges remain. Neural network architectures do not use disjoint set of parameters for each of the outputs. Additionally, the hidden competition of GANs can take place in an output space of probability distributions and classifiers whose vector space dimension is typically infinite. On the bright side, we establish point-wise (day to day) convergence results which are, to the best of our knowledge, the first result of their kind for a wide class of non-convex non-concave games that do not necessarily satisfy the Polyak-Łojasiewicz conditions studied in [68]. Such conditions imply that the notions of saddle points, global min-max and stationary points coincide. Instead our work showcases how to make progress without leveraging such strong assumptions in zero-sum games. Beyond ML applications, we believe that our framework could provide even further insights for evolutionary game theory, mathematical biology as well as team-zero-sum games. For example an interesting hybrid class of games could be network generalizations of team-zero-sums games, e.g. by combining [12] and [57].
Acknowledgments and Disclosure of Funding
This research/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-07, NRF2019-NRF-ANR095 ALIAS grant, grant PIE-SGP-AI-2018-01, AME Programmatic Fund (Grant No. A20H6b0151) from the Agency for Science, Technology and Research (A*STAR). Additionally, E.V. Vlatakis-Gkaragkounis is grateful to be supported by NSF grants CCF-1703925, CCF1763970, CCF-1814873, CCF-1563155, and by the Simons Collaboration on Algorithms and Geometry. He would like to acknowledge the support of Onassis Foundation under the Scholarship(ID: FZN 010-1/2017-2018.)

Review summaries:
In this paper, the authors introduce a class of games called Hidden Convex-Concave where a (stricly) convex-concave potential is composed with smooth maps. On this class of problems, they show that the continuous gradient dynamics converge to (a neighbordhood of) the minimax solutions of the problem. This is an exploratory theoretical paper which aims at better capturing the behaviors that can be observed e.g. in the training of GANs.

This paper extends "hidden bilinear" games [1]  to "hidden convex-concave (HCC)" games, and studies a special case of HCC games (denoted as HCC* from below) where output of each dimension of a nonlinear function depends on a seperate group of parameters .  For HCC* games, the authors utilize Lyapunov-type arguments and show that GDA dynamics stabilizes around the output-space Nash equilibrium (Theorem 3), whose parameter counterparts are named as "von Neumann solutions".  With an additional assumption that the game has one-sided strictness property, the authors further show that GDA converges to a "von Neumann solution" (Theorem 6), by combining Lasalle's principle and the fact that "safe initializations" reside in ROA of such solutions.  Additionally, the authors show that adding a regularization term can accelerate the convergence of GDA towards the perturbed equilibrium in the output space (Theorem 8).  Finally, the authors exemplify GANs and evolutionary games, and argue that such games can be nicely formulated as HCC games.

This paper studies a special problem structure in min-max optimization. Specifically, the paper considers the setting when the objective function can be reparametrized into a (strict) convex-concave game, or referred to as a hidden convex-concave game in the paper.   More formally, the considered function is of the form L(F(\theta), G(\phi)), where L is convex-concave. F and G are of separable structure, namely both the max and min player are from a cartesian product of scalar functions from disjoint sets of parameters. With the separable structure, the authors can thoroughly investigate the conditions for stable GDA dynamics and the good initializations for GDA to find the equilibrium of L.   Finally, the authors give some discussion on connecting the structures to GANs and evolutionary game theory/biology. 

In this paper, the authors study a two-player zero-sum convex-concave game whose inputs are parameterized by nonlinear functions. This results in the overall game being nonconvex-nonconcave in the parameter space. This setting is similar to that observed in GANs where the game is convex-concave in function space of discriminator and generator but is nonconvex-nonconcave in the space of parameters. The authors call such games as Hidden Convex-Concave (HCC) games.