Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent
Authors: Emmanouil-Vasileios Vlatakis-Gkaragkounis
Lampros Flokas
Georgios Piliouras
Venue: NeurIPS 2021 Poster (2021)
Keywords: Minmax Optimization
Nash Equilibrium
Convex
Von Neumann
Asymptotic Stability
Hidden Games

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 non-concave 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.

Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent
Lampros Flokas"
Emmanouil V. Vlatakis-Gkarrgkkuuiis Department of Computer Science
Department of Computer Science
Columbia University
Columbia University
New York, NY 10025
New York, NY 10025 emvlatakis@es columbia.
lamf lkas@oks columbia. edu
Georgios Piliouras
Singapore University of Technology & Design georgios
goorgia...iiooruseeeeeeetd piliouras@eutd.edu.s.
Abstract
Many recent AI architectures are inspired by zero-sum games, however, the behav- ior of their dynamics is still not well understood. Inspired by this, we study standard gradient descent ascent (GDA) dynamics concave 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 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 von-Neumann lution 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 prove that almost all initial conditions converge to the solution. Finally, we discuss diverse applications of our framework ranging from generative adversarial networks evolutionary biology.
specific class of non-convex non-
game. Unlike general zero-sum games,
Introduction
Traditionally, our understanding of convex-concave games revolves around von Neumann's '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, 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 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 (NcurIPS 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/diiferentiaa) Nash equilibrium [3. 41], local minmax [18], local minimax [31]. (local/differential) Stackleherg 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. grudient 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 R - X C IR"
and G R2M + Y C. IRm and a continuous convex-concave function L min-max game is
X x Y + R, such that the
min max ((F ((()). BERN
(Hidden Convex-Concent (HCC)
EERM
We call this class of min-max problems Hidden Convex-Concave Games. generalizes the recently defined hidden bilinear games of [65].
Our solution concept. Out of all the local Nash equilibria of HCC games, there exists special subclass, the vectors (0" Φ²) that implement the von Neumann solution of the convex-concave game. This solution has strong and intuitive game theoretic justification. Indeed, it stable even the agents could perform arbitrary deviations directly on the output spaces X, Y. These parameter combinations (0". x²)) "solve" the "hidden" convex-concave L and thus we call them von Neumann solutions. Naturally, HCCs will typically have numerous local saddle/Nash equilibria/fieed 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-coneave 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 0, Φ. the non-linear nature of F, G distorts the 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 novel Lyapunov function argument to prove that almost all initial conditions converge to the our game theoretic
landscape in the output space. Thus, the Euclidean distance will
solution.
Lyapunov Stability. Our first step is to construct an inttralization-deeendettt I 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 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 funetion with a quadratic regularizer. Interestingly, we can elucidate on why regularized learning is actually necessary by establishing 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 The outcome of this competition depends on their
competition between two species 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 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 artificial fixed points. Safety conditions aside, show that a slight variation of the evolutionary/learnig algorithm suffices to resolve the cycling issues and the von Neumann solution. Hence, we provide the first instance of
for the dynamics to equilibrate 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 discusses applications of our framework to specific GAN formulations. Section 5 concludes work with discussion of future directions and challenges. We defer the full proofs of our results as well as further discussion on applications to the Appendix.
2 Preliminaries
2.1 Notation
Vectors are denoted in boldface x, y unless otherwise indicated are considered as column vectors. We use ||-1] to denote the f--nomm. For a function _ + E we use V denote its gradient. For functions of two vector arguments, (x,y) Rd x R + R. we use Vxf. Vy f to denote its partial gradient. For the time derivative we will the dot accent abbreviation, i.e., x 4 [x((). A function f will belong to C" if it r times continuously differentiable. Additionally, f g f(g(-) denotes the composition of f.g. Finally, the term "sigmoid" function refers + 12 such that (x) = (1 + -
2.2 Hidden Convex Concave Games
Ayr
Oyra
fx(0w))
Uar (dar)
darz
siara
F(0)
L(F(0), G(+))
G
P1z
(9.))
By (r(
dx
W. (FF(0) G(
Figure:Hidder Seperable Zero-Sum Game Model Optimization Dynanies
6 - R., L(F()).
3

---

We will begin our discussion by definnng the notion of convex concave functions as well as strictly convex concave functions. Note that our definition of strictly convex concave functions is superset of strictly convex strictly concave functions that are usually studied in the literature.
Definition 1. L IR x R + R is convex concave if for every y E R L(-y) ) is convex and for every R [(x,)) +) is concave. Function L will be called strictly convex concave if it is convex concave and for every x X y E R" x 1. 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 set of operator functions. The minimization player is equipped with n. functions f& IR - R while the maximization player is equipped with functions gj I + IR. We will assume in the rest of our discussion that fa. 9n. L are all C functions. The inputs 0g E 12 and Φ E "T are grouped in two vectors
01
0m] Sm]
F(O) [f1(
(O.))
G [91 (Φ1)
(m
We are ready define the hidden convex concave game
(0" x²) = arg min arg max (F(().. G(Ø)).
BERN
*ERM
where N = n4 and M = Σド 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 R" x I For games defined over convex compact sets, the existence of at least one solution is guaranteed by von Neumann's 's minimax theorem. Our definition of HCC games can capture games on restricted domains by choosing appropriately bounded functions Ji and gý. 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 fa and Jj- We are now ready to write down the equations of the GDA dynamics for a HCC game:
1== m.. Given a convex concave function L, all stationary points
0. = Vo, ((F(O)) G(Ø) = f... OL (F(O), GiØ)
0..
(1)
OL (F(O).
Vo, ((F()
=Vo (13) 0g,
2.3 Reparametrization
The following lemma is useful in studying the dynamics of hidden games. Lemma 1. Let k: Rd + Th be C2 function. Let h IR - R be C2 function and x(() denote the unique solution of the dynamical system E, Then the unique solution for dynamical system Eg is
ztt) = x(S] h(s)ds)
vk(x) Xinit }:
{
(())(()))
En
E2
(2)
x()
22(0)
Nant
By choosing h(t) = -L( ((t))/ff. and h(t) (F), G(t))/Og, respectively. we can connect the dynamics of each 0: and o; under Equation (1) to gradient ascent fi and gj. Ap- plying Lemma 1, we get that trajectories of 0; and Φjj under Equation (1) are restricted to be subsets of the corresponding gradient ascent trajectories with the same initializations. For example, in Fig- ure (() can not escape the purple section if it initialized at (a) neither the orange section if it is initialiazed at (f), This limits the attainable values that ft( and g, (t) can take for a specific initialization. Let us thus define the following: Definition 2. For each initialization x(0) of En Img (x) is the image of 1 x IR R.
f((0))
(d)
Equilibruum-value f
(b)
()
1.5 (
(g)
8:
-3
Figure Neither Gradient Descent nor Ascent can traverse stationary points. An immediate con- sequence of Lemma is that if we initialize in the above example (,))) at (a), (t) can not escape the purple section. This extends to cases where 0 is vector of variables.

---

Applying Definition 2 in the above example, Im (0,(0)) f( if 0; is initialized at (c). Additionally, observe that in each colored section (t) uniquely identifies (t).. Generally, even in the case that 0, are vectors, Lemma 1 implies that for given (0), (:(O,()) uniquely identifies (1). As a result we get that a new dynamical system involving only fi and 9j
Theorem 1. For each initialization (0(0), ((0)) of Equation (I), there are C functions Xo.(o) (0) such that (t) Xo.(o) (0) (f:(t) and (1(t) (o)())))((t). If (0(1),((1)) sat- isfy Equation (1) then Ji(1) (L)) and 93(0) g3 (1)) satisfy
OL
f Vo, fi X (0) (I 0.:
G)
AL
9; |V, 93 (x, (0) (03
|| Zg
(F, G)
By determining the ranges of fi and gj. an initialization clearly dictates if von Neumann solution is attainable. In Figure I for example, any point of the pink, orange or blue colored section like (c), (f) or (g) can not converge which initializations can converge to a given element of Solution( L).
von Neumann solution with f0())) fr. The notion of safety captures
Definition 3. We will call the initialization (0(0), (()) safe for a (p, q) E &Solution()) L) if (0) and 9 (0) are not stationary points of fs and 9, respectively and pa E [m,, (0)( and qj E Img, (6, (0)).
Leveraging the Center-Stable Manifold Theorem [55], the following observation shows that under mild assumptions almost all initializations are safe:
Theorem 2. If fs and 93 have isolated stationary points, only strict saddle points, com- pact sublevel-sets, both equilibria ps (max LocalMin(Ji). min (acalMax(fi) and q e (max LocalMin(gg). min LocalMax(g))), then almost all initializations are safe for a (p. e Solution
Finally, in the following sections we use some fundamental notions of stability. We call an equilibrium x" of autonomous dynamical system D(x(t)) stable if for every neighborhood U of there is neighborhood V of x* such that if x(0) E V then x(t) E U for all t 2 O. We call a set S asymptotically stable if there exists neighborhood R such that for any initialization x(0) E R, x(t) approaches S as t + +oo. If R is the whole space the set globally asymptotically stable.
3 Learning in Hidden Convex Concave Games
3.1
General Case
Our main results are based on designing a Lyapunov function for the dynamics of Equation (3):
Lemma 2. If is convex concave and (Φ)(), 0(0)) is a safe for (p. q) E Solution (L), then the following quantity is non-increasing under the dynamics of Equation (3):
H(F, G)
Σ (x))
N
ft
2 z- P
dz + Σ
[ 95
9i
[X, (0) dz
qj
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 con- stant multiplicative terms in Equation (3). Indeed if the game was not hidden and f; and 9j 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 (Q(0), (()) is a safe for (p,q) E Solution( T.), then (p, q) is stable for Equation (3).
Fini
Figure 2: Level sets of Lyapunov function of Equa- tion (4) for both F and G being one dimensional sigmoid functions.
5

---

Clearly, for the special case of globally invertible functions F, G we could come up with an equivalent Lyapunov function in the 0, e-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 0, & (Equation (1)). For example we can prove the following result:
Theorem 4. If Si and gj are sigmoid functions and L is convex concave and there is (()))(()) that is safe for (p, q) E Solution(L), then (p), Gg)(())))))))))))))))()))) 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 weaker notion of stability, which call hidden stability, Hidden stability captures that if (F)),)), ())) is close to a von Neumann solution, then (F)) 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 q) E Solution (L). Let Rj, and Rg, be the set of regular values' of fa and 9j respectively. Assume that there is E > 0 such that [p: E, + E) Ry, and laj 9i + E] Bay. Define
r(t) = [IF((()) - pll + (G( - all
If ft and 9j are proper functions", then for every > 0, there is an such that
r(0) < 8 14 2 0 : r()) <.
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 restricted to be a subset of 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.
3.2 Hidden strictly convex concave games
In this subsection we focus on the case where a strictly convex concave function. Based on Definition 1, strictly convex concave game is not necessarily strictly convex strictly concave and thus may have a continum of von Neumann solutions. Despite this, LaSalle's s invariance principle, combined with the strict convexity concavity, allows us to prove that if (0(0), ((0) is safe for Z C Solution(L) 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 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 - +oc. In other words, a-priori it is unclear if (F (F())))) G (()
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 ft and gj approach the boundaries of Im, (0) and Img, I (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 corvex concave and Z C Solution L) is the non empty set of equilbria of T. for which (0)), (0)) is safe. Under the dynamics of Equation (1) (F))())) G(O()))) converges to point in 7. as > co.
The theorem above guarantees convergence to Neumann solution for all initializations that are safe for at least one element of Solution( I.). However, this is not the same as global asymptotic stability. To get even stronger guarantees, can assume that all initializations are safe. In this case it is straightforward to get a global asymptotic stability result:
Let L be strictly convex concave and assume that all intitializationss are safe for at least one element of Solution(1.) I.). The following set is globally asymptotically stable for continuous GDA dynamics.
Corollary 1.
{00", x" E RR m (F(0"),
(((0")G((") G(Φ")) E Solution(()) (L)}
A value a E Tm f is called a regular value f if 4y E dom f : f(g) = a, it holds Vf(1) # 0.
2 A function is proper if inverse images of compact subsets compact.

---

Notice that the above approach on global asymptotic convergence using Lyapunov arguments can be extended other popular alternative gradient-based heuristics like variations of Hamiltonian Gradient Descent. For concision, we defer the exact statements, proofs in the supplement.
3.3 Convergence via regularization
Regularization is key technique that works both in the practice of GANs [47, 33] and in the theory of convex concave games [56, 59, 60J. Our settings of hidden convex concave games allows for provable guarantees for regularization in wide class of settings, bringing closer practical and theoretical guarantees. Let us have utility Lxx,y) y) that is convex concave but not strictly. Here we will propose modified utility L' that is strictly convex strictly concave. Specifically will choose
y' L(x,y) + |
1ly
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 are not significantly perturbed.
Theorem 7. If a convex concave function with invertible Hessians at all its equilibria, then for each e > 0 there is a X > 0 such that L' has equilibria that are e-close to the ones of L.
Note that invertibility of the Hessian means that must have unique equilibrium. On the other hand increasing À increases the rate of convergence of safe initializations to the perturbed equilibrium.
Theorem 8. Let (0), Φ (()) be safe initialization for the unique equilibrium of L' (p. q). If
r(1) = (()) - p + (G)(()) - qll
then there are initialization dependent constants co, O such that rt)) S (xxx))
4 Applications
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 Appendix D.3.
r10 [[ pl [GW (A
Bi6
1im0
Figure 3: Both the l2 distance from the equilibrium and (1) converge to zero but only the latter does so monotonically For Pdata we choose fully mixed distribution of dimension d = 4. Given the sigmoid activations all the initializations are safe. We defer the detailed proof of convergence in Appendix D.2.
Hidden strictly convex-concave games. We will start our discussion with the fundamental gener- ative architecture of [26]'s 's GAN. In the vanilla GAN architecture, as it is commonly referred, our goal is to find generator distribution Pa that is close to an input data distribution Pdata find such 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 Pa(m)20, ETEN p
max DI(O
V(G
where D) EmEN Paata (x) log( D(x)) ΣTEN Pa(x) log(1 D(x)). The problem above can be formulated as a constrained strictly convex-concave hidden game. On the one hand, for fixed discriminator D the VGG, D*) is linear over the pa(x). On the other hand, for a fixed generator G*,
7

---

V(G", D) is strongly-coneave We can implement the inequality constraints on both the generator probabilities and discriminator using sigmoid activations. For the equality constraint Erex Pa(z) 1 we can introduce a langrange multiplier. Having effectively removed the constraints, we can see in Figure 3, the dynamies 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, (t) is.
Hidden convex-concave games & Regularizaiton. An even more interesting case is Wassertein CANs-WGANs [4]. One of the contributions of [36] to show that WGANs trained with Stochastic GDA can learn the parameters of Gaussian distributions whose samples are transformed by non-linear activation functions. 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, a?) and linear discriminator (x) = v x with x2 activation is:
worth mentioning that the original WGAN formulation has Lipschitz
min max VWGAN (WGAN(Ga,DD Dv) oER oE
= Exx~pen [D( -Ex-pe [XX) v²/2
Ro [wra]] 1R [mx] - 12/2
(a - a²) 12/12
Observe that VWGAN is not convex-concave but it can posed hidden strictly convex-concave game with G(x)) (a - a²) and F(v) = u. When computing expectations analytically without sampling, Theorem guarantees convergence. In contrast, without the regularizer VWGAN can be modeled as hidden bilinear game and thus GDA dynamics cycle. Empirically, these results are robust to discrete and stochastic updates using sampling 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.
3
GDA
2
Lei
40000
0
-1
20000
10000
-2
0.5
-3
-0.3
05
10
0.1
0.
Figure 4: On the left, we show the trajectories of regularized GDA for o² 1 as well as the level sets of Equation (4). All trajectories (green curves- initialii at the red points) converge to one of the two equilibria (0, 1) and (0, 10) whereas without regularization, GDA would cycle on the level sets. In the right figure. we replace the exact expectations in VWGAN with approximations via sampling and continuous time updates on a and with discrete ones. For small learning rates and large sample sizes, unregularized GDA continues to cycle. In contrast, the regularization approach of [36] converges the (0, 1) equilibrium.
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 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 '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.
8

---

The above figures describes the evolution of the expected phenotype for two species A,B. The left one corresponds to a safe initialization leading to periodic trajectories. The middle one corresponds to unsafe initialization where 01 (0) 02(0). The dynamics converge albeit to spurious equilibrium, that different from the hidden game equilibrium (dash lines). Finally, the right one corresponds to safe initialization of the regularized game, which converges to slightly perturbed equilibrium (Theorem 7).
Figure 5:
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 capture competition between asexually reproducing species, it is well known that the emerging dynamics can be non- con-euuilibaainn and even chaotic [61, 58].
Studying the effects of evolutionary competition between sexually evolving species results in sig- nificantly 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 much more detailed accounting of the evolution of the frequencies of different genes that get reshuffled and recombined create new individuals, whilst giving evolutionary preference 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?) 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], 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 Boolean attribute (this assumption is also used [38]). Despite these simplifications, the dynamics and are, in fact, cyclic for almost all initial conditions. Two natural questions emerge: 1) Is the almost everywhere condition necessary? L.e. Do there exist initial conditions which are not cyclic? 2) More importantly, can a slightly perturbed dynamic stabilize these systems and converge to meaningful equilibrium? Next, we will see how our framework addresses both of these questions.
species (host-parasite) antagonism.
still not equilibrating
To understand the connection these we will examine the model of [57] in more detail. Concretely, Boolean function
the phenotype of species A, B can be described which is encoded by a binary string (this acts as a simplified version of 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:
the species genome
GA (gl
2)) GD (gf
gm
U L/Phenotype (GA), Phenotype (G))
ug uu
Where g/.g E 10, Phenotype Phenotype is Boolean function (e.g., AND, XOR) and L is a 2 x 2 matrix encoding a zero-sum game (e.g., Matching Pennies). Naturally, one can allow agents to use randomized/nixed 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-lineal games, which explains their recurrent, non-equilibrating nature [65].

---

In Figure 5, each gene/agent g," tumes one real variable 0 such that Príg, 1] ( and gene/agent g tunes one real variable Φ, correspondingly. Choosing as Boolean phenotype to be the XOR of two genes, almost all initializations are safe for any bilinear game with mixed equilibrium. Actually, only the case 0, (0) = 02(0) or Φ1 (0) = d2(0) can be problematic, since for XOR the expected phenotype is bounded in [o, 0.5] and mixed equilibrium out of this range would be infeasible. Finally, leveraging Theorem 7, we can design regularized version of the game such that the dynamies converge arbitrarily close to the true von Neumann solution of these games, which is encoded by the max strategies of the hidden bi-linear zero-sum game.
5 Discussion & Future Work
While this work 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 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 wide class of non-convex non-concave games that do not necessarily satisfy the Polyak-Lojasiens Lojasiewicz conditions studied in [68]. Such conditions imply that the notions of saddle points, global min-max 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, believe that 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 un- der its AI Singapore Program (AISG Award No: AISG2-RP-2020-0166, NRF 2018 Fellowship NRF-NRFF201 18-07, NRF2019-NRFF 9-NRF-ANR095 ALIAS grant, grant PIE-SGP-AI-201 8-01, AME Pro- grammatic Fund (Grant No. A20H6b0151) from the Agency for Science, Technology and Research (A*STAR). Additionally, E.V. Vlatakis Vlatakis-Gkaragkee Gkaragkounis is grateful to be supported by NSF grants CCF-1703925, CCF1763970, CCF-1814873, 1CF-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,
References
[1] Jacob Abernethy, Kevin A Lai, Kfir Y Levy, and Jun-Kun Wang, Faster rates for convex-concave games. In COLT, 2018.
[2] Jacob Abernethy, Kevin A Lai, and Andre Wibisono. Last-iterate convergence rates for min-max optimization. arXiv:1906.0200 02027, 2019.
[3] Leonard Adolphs. Hadi Daneshmand, Aurélien Lucchi, and Thomas Hofmann. Local saddle point optimization: A curvature exploitation approach. In AISTATS, 2019.
[4] Martín Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein GAN, arxiv:1701.07875, 2017.
[5] James Bailey and Georgios Piliouras. Fast and furious learning in zero-sum games: vanishing regret with non-vanishing step sizes. In NeurIPS, 2019.
[6] James Bailey, Gauthier Gidel, and Georgios Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. In COLT, 2020.
[7] James P. Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games, In EC, 2018
[8] David Balduzzi, Séhastien Racanière, James Martens, Jakob N. Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n-player differentiable games. In ICML, 2018.
10

---

[9] Michel Benaïm. Dynamics of stochastic approximation algorithms. In Seminaire de probabilites XXXIII, pages 1-68. Springer, 1999.
[10] Sanjay P. Bhat and Dennis S. Bernstein. Nontangency-based Iyapunov tests for convergence and stability in systems having continuum of equilibria. SIAM J. Control Optim, 2003.
[11] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, USA, 2004.
[12] Yang Cai and Costantinos Daskalakis. On minmax theorems for multiplayer games. In SODA, SODA, 2011.
[13] Nikolo Cesa-Biane Bianchi and Gabor Lugoisi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[14] Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani. Algorithms, games, and evolution. PNAS, 2014.
[15] Yun Kuen Cheung and Georgios Piliouras. Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning zero-sum games. In COLT, 2019.
[16] Yun Kuen Cheung and Georgios Piliouras. Chaos, extremism and optimism: Volume analysis of learning in games. In NeurlPS, 2020.
[17] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In ICLR, 2018.
[18] Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In NeurIPS, 2018.
[19] Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In ITCS, 2019.
[20] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. arxiv:2009.06633, 2020.
[21] Lawrence C Evans. Partial differential equations and monge-kantorovich mass transfer. Current developments in mathematics, 1997.
[22] Ky Fan. Minimax theorems. PNAS, 1953.
[23] Farzan Farnia and Asuman E. Ozdaglar. Do gans always have nash equilibria? In ICML, 2020.
[24] Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in stackelberg
games: Equilibria characterization, convergence analysis, and empirical study. In JCML, 2020.
[25] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A
variational inequality perspective on generative adversarial networks. In ICLR, 2019.
[26] Ian Goodfellow, Jean Pouget-Abadics Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NewrIPS, 2014.
[27] Ian Goodfellow. NIPS 2016 tutorial: Generative adversarial networks. 170.01100, 2017.
[28] Hofbauer and K. Sigmund. Evolutionary Games and Population Dynamics. Cambridge University Press, Cambridge, 1998.
[29] Yu-Guan Hsich, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the conver- gence of single-call stochastic extra-gradient methods. In NeurlPS, 2019.
[30] Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. In NewrIPS, 2020.
11

---

[31] Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. arxiv:1902.006/8. 2019.
[32] Hassan K Khalil. Nonlinear systems; 3rd ed. Prentice-Hall, 2002.
[33] Karol Kurach, Mario Lucic, Xiaohua Zhai, Marcin Michalski, and Sylvain Gelly. A large-scale study regularization and normalization in gans. In ICML,
[34] Jason D. Lee, loannis Panageas, Georgios Piliouras, Max Simchowitz, Michael I. Jordan, and Benjamin Recht, First-order methods almost always avoid saddle points. arxiv: 170.0706, 2017.
[35] Jason D. Lee, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In COLT, 2016.
[36] Qi Lei, Jason Lee, Alex Dimakis, and Constantinos Daskalakis. SGD learns one-layer networks in wgans. In ICML, 2020.
[37] Adi Livnat, Christos Papadimitriou, Jonathan Dushoff, and Marcus W. Feldman. A mixability theory for the role of sex in evolution. PNAS, 2008.
[38] Adi Livnat, Christos Papadimitriou, Aviad Rubinstein, Andrew Wan, and Gregory Valiant. Satisfiability and evolution. In FOCS, 2014.
[39] Chris J. Maddison, Daniel Paulin, Yee Whye Teh, Brendan O' O'Donoghue, and Arnaud Doucet. Hamiltonian descent methods. arxiv: 100.00220 2018.
[40] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
[41] Eric Mazumdar and Lillia J Ratliff. Local nash equilibria are isolated, strict local nash equilibria in 'almost all' zero-sum continuous games. In Proc. IEEE Conf. Decis. Control, 2019.
[42] Ruta Mehta, Ioannis Panageas, and Georgios Piliouras. Natural selection as an inhibitor of genetic diversity: Multiplicative weights updates algorithm and conjecture of haploid genetics. In ITCS, 2015.
[43] Ruta Mehta, Ioannis Panageas, Georgios Piliouras, and Sadra Yazdanbod. The Computational Complexity of Genetic Diversity. European Symposium on Algorithmss (ESA), 2016.
[44] Reshef Meir and David Parke. A note on sex, evolution, and the multiplicative updates algorithm. In AAMAS, 2015.
[45] 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(-gradient) mile. In ICLR, 2019.
[46] Panayotis Mertikopoulos, Christos H. Papadimitriou, and Georgios Piliouras. Cycles in adver- sarial regularized learning. In SODA, 2018
[47] Lars M. Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually converge? In ICML, 2018.
[48] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra- aita--gradien and optimistic gradient methods for saddle point problems: Proximal point approach. In AISTATS, 2020.
[49] Yurii E. Nesterov. Introductory Lectures on Convex Optimization Basic Course, volume 87 of Applied Optimization. Springer, 2004.
[50] Sebastian Nowozin, Botond Cseke and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. In NeurlPS, 2016.
[51] Brendan O' Donoghuue and Chris Maddison. Hamiltonian descent for composite objectives. In NewrIPS, 2019.
12

---

[52] Ioannis Panageas and Georgios Piliouras. Gradient descent only converges to minimizers: Non-isolated critical points and invariant regions. ITCS, 2017.
[53] Ioannis Panageas and Georgios Piliouras. Gradient descent only converges to minimizers: Non-isolated critical points and invariant regions. In ITCS, 2017.
[54] Ioannis Panageas, Georgios Piliouras, and Xiao Wang. First-order methods almost always avoid saddle points: The case of vanishing step-sizes. In NeurlPS, 2019.
[55]
Lawrence Perko. Differential Equations and Dynamical Systems. Springer, 3nd. edition, 1991.
[56] Julien Pérolat, Rémi Munos, Jean- Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro A. Ortega, Neil Burch, Thomas W. Anthony, David Balduzzi, Bart De Vylder, Georgios Piliouras, Mare Lanctot, and Karl Tuyls. From poincaré recurrence to convergence in imperfect information games:
Finding equilibrium via regularization. wxxiv:2002.08450 2020.
[57] Georgios Piliouras and Leonard J Schulman. Learning dynamics and the co-evolution of competing sexual species. In ITCS, 2018.
[58] Georgios Piliouras and Jeff S. Shamma. Optimization despite chaos: Convex relaxations to complex limit sets via poincaré recurrence. In SODA, 2014.
[59] Kevin Roth, Aurélien Lucchi, Sebastian Nowozin, and Thomas Hofmann. Stabilizing training of generative adversarial networks through regularization. In NeurIPS, 2017.
[60] Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and Jason Lee. On the convergence and robustness of training gans with regularized optimal transport. In NeurlPS, 2018.
[61] Yuzuru Sato, Eizo Akiyama, and J. Doyne Farmer. Chaos in learning simple two-person game. PNAS, 2002.
[62]
Leonard Schulman and Umesh V Vazirani. The duality gap for two-team zero-sum games. In ITCS, 2017.
[63] David Silver, Julian Schritwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 2017.
[64] Cédric Villani. Optimal transport: old and new, volume 338. Springer Science Business Media, 2008
[65] Emmanouil--asillee Vlatakis- GaaakiiiGkaragkouniss, Lampros Flokas, and Georgios Piliouras. Poincaré recurrence, cycles and spurious equilibria in gradient-descent asccent for non-convex non-concave zero-sum games. In NewrIPS, 2019. 2019.
[66] Jun-Kun Wang and Jacob Abernethy. Acceleration through optimistic no-regret dynamics. In NeurlPS, 2018.
[67] Jörgen Weibull. Evolutionary Game Theory. MIT Press; Cambridge, MA: Cambridge University Press., 1995.
[68] Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of minconvex-nonconcave minimax problems. In NewrlPS, 2020.
[69] Guojun Zhang, Pascal Poupart, and Yaoliang Yu. Optimality and Stability in Non-Convex-Non- Concave Min-Max Optimization. wxXi:2202..11875 2020.
[70] Guojun Zhang and Yaoliang Yu. Convergence of gradient methods on bilinear zero-sum games. In ICLR, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] We do not
see any ethical or future societal consequences of this work, since its motivation is strongly theoretical.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)?[N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] The presented experiments are used for illustrative purposes and only to validate the theoretical findings which are the core results of this work.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "ujbNxKdb2ec", "reviewer": "Reviewer_Ywxk", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "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": "The paper generalizes the work of Flokas et al. for hidden bilinear games. The generalization is theoretically nontrivial because Euclidean distance is not a Lyapunov function in general. The authors propose a generalized Lyapunov function for analyzing asymptotic convergence of dynamics to the solution of the HCC game. In that process, they need to assume that the underlying game is strictly convex-concave (which should not be confused with strictly-convex strictly-concave).\nIn the case of convex-concave games, they study a regularized underlying game. This makes the problem strictly (or rather strongly) convex-concave. While it changes the underlying equilibrium, the aforementioned results immediately imply convergence to the regularized equilibrium point.\nIn the case of GAN example in Section 4 (first application), the presence of \\lambda (\\sum_N p_G(x)-1) in the final game makes \\lambda part of the maximization variable. Then, this underlying problem is not strictly concave in the combined variable (D, \\lambda) for fixed G. Does this affect the convergence claims?\nOverall, the authors have provided a clear explanation of their claims. The paper makes interesting contributions that might contribute to a better understanding of GANs. The point that different parameters \\theta_i are used in different functions can be a source of limitation for application to the wider Neural Network-based GAN models. However, I believe the limitation outweigh the overall merits and hence I provide a high score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please address the concerns mentioned in the main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "l3Sh1jA9Cl", "reviewer": "Reviewer_Y6yb", "summary": "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 .\n\nFor 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\".\n\nWith 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.\n\nAdditionally, the authors show that adding a regularization term can accelerate the convergence of GDA towards the perturbed equilibrium in the output space (Theorem 8).\n\nFinally, the authors exemplify GANs and evolutionary games, and argue that such games can be nicely formulated as HCC games.", "questions": "", "limitations": "", "rating": 5, "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": "Pros:\n1. non-convex non-concave game optimization is still an area of active research, and we still lack game classes that are (1) expressive enough to represent practical games, and (2) structured enough to admit theoretical analysis. The proposed HCC games satisfy (2).\n\n2. Overall, the proofs seem to be clear, succinct, and well-organized. The authors also provide a brief sketch whenever the proof becomes complicated.\n\n\nCons:\n1. **(Expressivity of HCC games)**  Arguably, one of the most important non-convex non-concave games in machine learning is GAN. However, it is quite dubious whether GAN can be formulated as a HCC game (even in a simplified setting). In Section 4, the authors formulate GAN training as\n\n$\\min_{p_G(x_i)} \\max_{D(x_i)}  \\sum_i [p_{data}(x_i) \\log D(x_i) + p_G(x_i) \\log(1 - D(x_i)) ]$.\n\nHowever, in its original form, GAN objective follows\n\n$\\min_{\\theta} \\hspace{1pt} \\max_{\\phi} V(\\theta, \\phi) = \\min_{\\theta} \\hspace{1pt} \\max_{\\phi} E_x[log(D_{\\phi}(x))] + E_z[log(1-D_{\\phi}(G_{\\theta}(z)))]$,\n\nwhere $\\theta$ and $\\phi$ represent the parameters of $G$ and $D$, respectively; the generator never learns $p_G(x_i)$ directly.\n\nI am not sure how one could reformulate the above equation as a HCC game. Even worse, in case of HCC* games (with disjoint parameter groups assumption), I don't think the generator would be possible to model a data distribution with more than one-dimension. The significance of HCC games would be greatly improved if the authors could provide a reformulation of the above $V(\\theta, \\phi)$ as a HCC game $L(f(\\theta), g(\\phi))$ for some convex-concave $L$, smooth functions $f$ and $g$.\n\n\n2. **(Novelty)**\nThe main idea of “hidden game” was first proposed in [1], and this paper aims to extend [1] by replacing the bilinearity with convex-concavity. To do so, the authors utilize main assumptions (“safe initialization”, the separated parameter groups), technical tools (Lemma 1, Theorem 1), and the Lyapunov function (Equation 4, invariant quantity in [1]) developed in [1]. Considering the fact that the HCC games are a generalization of hidden bilinear games, this could be a natural thing. However, it is hard to say this work is novel, since the conceptual prototype of the game class (“hidden game”) and technical tools (Lemma 1, Theorem 1, Lyapunov function) already have been presented in the preceding work.\n\n\nMinor comments:\n- I have an impression that Theorem 8 is quite obvious and somewhat out-of-place. Any strictly-convex strictly-concave game would admit a linear convergence for GDA, and it is unclear how it relates to the unique structure of HCC games.\n- In Theorem 2, $maxLocalMin$ and $minLocalMax$ are undefined.\n- In Theorem 5, $R_{f_i}$ and $R_{g_j}$ are undefined.\n- Both in abstract and conclusion, the authors mention that *“our convergence guarantees are non-local, which as far as we know is a first-of-its-kind type of\nresult in non-convex non-concave games”*. However, I believe this is not true. For example, [2] has shown that alternating GDA globally converges for two-sided Polyak-Lojasiewicz (PL) games with a linear rate in deterministic settings, and converges with a sublinear rate in stochastic settings. This is a NeurIPS 2020 paper, so I think there would be more non-convex non-concave global convergence results published this year.\n\nAt this stage, I recommend rejection for this paper, mainly on the basis of the Cons 1 and 2.\n\n---\n\n[1] Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games. Flokas et al., NeurIPS 2019.\n\n[2] Global Convergence and Variance Reduction for a Class of Nonconvex-Nonconcave Minimax Problems. Yang et al., NeurIPS 2020.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see Cons 1 & 2 for the limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "i4AFH6fiewh", "reviewer": "Reviewer_1EDT", "summary": "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. \n\nMore 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. \n\nFinally, the authors give some discussion on connecting the structures to GANs and evolutionary game theory/biology. ", "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": "\nI believe the overall construction is pretty neat and clever. The paper is also quite nicely written and everything is easy to follow. The final discussions are quite enlightening (although not very well aligned with the main story/analysis of the paper). \n\nI do agree this is a natural and initial step for understanding more complicated nonconvex-nonconcave objectives. However once the setting is clear, the whole analysis becomes quite obvious, and the technical part is not that challenging. It is also hard to get further inspiration on how to stabilize the training or design new optimization schemes based on the studies in this paper. Therefore my overall evaluation is a borderline accept. \n\n \n\n\n\non minor comments:\n\n1. argmin of \"argmax\" doesn't make sense at the end of page 3.\n\n2. some typos like 'intitializations'", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A\n\nThis is a theoretical work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "-8STZkwP8O3", "reviewer": "Reviewer_b7eF", "summary": "This work studies the continuous dynamics of GDA in hidden convex-concave games via tools from dynamical systems.  ", "questions": "", "limitations": "", "rating": 4, "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": "Following ref [66] that studies hidden bilinear games, this paper studies hidden strict convex-concave games. It shows that GDA stabilizes around von Neumann solutions of hidden games. The authors claim that these hidden convex games could help us understand GAN training and this is a first step.\n\nHowever, I think this paper is not ready for publication yet. During my reading I'm confused about the novelty, clarity and significance. \n\nClarity: I acknowledge the attempts to add some paragraphs to summarize the main contribution (line 59-63) and the structure of the paper (Line 112-115), but there are many parts of the paper that imply that this paper is not quite well written and not polished enough.\n\n1) The question in line 38-39 comes from nowhere. Why is this question interesting? How do we relate it to previous background? \n2) line 48-58: is the von Neumann solution formally defined anywhere? Because I did not find the definition. \n3) line 76-78 seems repetitive\n4) Line 166: what is $k$ in definition 2? \n5) Thm 1: what is the meaning of $X_{\\theta(0)}$, $X_{\\phi(0)}$?\n6) Line 233: could you explain LaSalle's invariance principle or give a reference? \n7) In Section 4 it is claimed that GAN is hidden strictly convex-concave games. However, I think a caveat is that the authors are studying the game in the function space, which is convex-concave. This is already known. The nonconvexity comes from the neural net parametrization which leads to difficulty in training GANs but I have not seen it discussed anywhere. \n\nThere are many small typos which may affect the readability, such as: \n1) Line 28: GANS -> GANs\n2) Line 33: local minmax -> local min-max\n3) Line 52: quotation marks\n4) Line 151: is z(t) a definition? There is no ending mark\n5) period mark in Thm 1, and the caption of Fig 3\n6) The end of page 7: what is $\\mathcal{N}(0, \\alpha)^2$? \n7) Line 281 below: what does $(0, 1)^{|\\mathcal{N}|}$ mean?\n\nRelevance & Significance: \n1) I don't quite understand the biology application. What are $F, G, L$ in this application according to HCC? Also I'm not sure if this application is relevant to the ML community.\n2) What is the main finding towards the practice of GANs? Is it Section 3.3 that says we should do regularization? Could you do some GAN experiments to illustrate this? How do you compare this method with say WGAN with gradient penalty? \n3) GDA has been analyzed in nonconvex-concave games, see e.g.  arXiv:1906.00331. I also wouldn't say in line 365 that this paper is the first work towards understanding GAN training theoretically because there are many recent works on this, see ref [23] and refs therein.\n\n\nNovelty: I would like the authors to compare their main results with ref [66]. For example,\n\n1) Theorem 1 is similar with Lemma 2 of [66].\n2)  Lemma 2 is similar to Theorem 2 of [66].\n\nHow does your proof techniques incorporate [66] and what is different? \n\nRelated work:\nLine 256: Hamiltonian Gradient Descent needs some reference\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author did not address the limitations and potential negative societal impact and they claim it is purely theoretical work. I would suggest adding some discussion on GAN training and biology applications.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Most reviewers appreciated the novelty of the class of the problems studied and found it interesting.  There are concerns about the expressivity of HCC games in practical settings that has not been fully addressed by the authors. There were also questions about the contributions w.r.t. reference [66]. However, as authors mentioned, the invertibility assumption is one of the key differences of their work with reference [66]. Another comment was about defining various concept needed to understand the paper. It would help the reader a lot if the authors can define all necessary concepts to understand the paper (e.g. La Salle's principle Vo Neumann solution, etc.)



Decision: Accept (Poster)