Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent
Authors: Emmanouil-Vasileios Vlatakis-Gkaragkounis
Lampros Flokas
Georgios Piliouras
Venue:  (2021)
Keywords: Min-max optimization
Lyapunov functions
Stability Analysis
Generative Adversarial Networks
Non-convex optimization

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 min-max games, these games have a well-defined notion of solution; outcomes that implement the von-Neumann equilibrium of the ``hidden convex-concave game. We prove that if the hidden game is strictly convex-concave then vanilla GDA converges not merely to local Nash, but typically to the von-Neumann solution. If the 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 min-max game. Our convergence guarantees are non-local, which as far as we know is a first-of-its-kind type of result in non-convex non-concave games. Finally, we discuss connections of our framework with generative adversarial networks. 


Under review as a conference paper at ICLR 2021
SOLVING MIN-MAX OPTIMIZATION WITH HIDDEN STRUCTURE VIA GRADIENT DESCENT ASCENT
Anonymous authors Paper under double-blind review
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 stan- dard 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 out- puts are being applied as inputs to a convex- conccvee 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 prove that if the hidden game is strictly convex-concave then vanilla GDA converges not merely to local Nash, but typically to the von-Neumann solution. If the game lacks strict convexity properties, GDA may fail to converge to any equi- librium, however, by applying standard regularization techniques we can prove convergence von-Neumann solution of slightly perturbed zero-sum game. Our convergence guarantees are non-local, which as far as we know is a first- of-its-kind type of result in non-convex non-concave games. Finally, we discuss connections of our framework with generative adversarial networks.
INTRODUCTION
Traditionally, our understanding of Sanvex-concaye games revolves around von Neumann's cele- brated minimax theorem, which implies the existence of saddle point solutions with a uniquely defined value. Although many learning algorithms are known points
able to compute such saddle & Lugoisi (006). recently there has there has been fervor of activity in proving stronger results such as faster regret minimization rates or analysis of the day-to-day behav- ior (Mertikopoulos et al., 2018; Daskalakis et al. 2018 Bailey & Piliouras 2018 Abernethy et al.) Wang & Abernethy 2018; Daskalakis & Panageas
Aberrntty et al. 2019 Mertikopuu
los et al. 2019 Bailey & Piliouras]
2019
Gidel et al.
2019 Zhang & Yu 2019
Hsieh et al. 2019
Bailey et al. 2020 Mokhtari et al. 2020
Hsieh et al.
2020 Pérolat et al. 2020)
This interest has been largely triggered by the impressive successes of Al architectures inspired by min-max games such as Generative Adversarial Networks (GANS) (Goodfellow et al.) 20144)) adversarial training (Madry al.) (018)) and reinforcement learning self-play in games (Silver al.) 2017). Critically, however, all these applications are based upon non-coneer non-concave games, our understanding of which still nascent. Nevertheless, some important early work in the area has focused on identifying new solution concepts that are widely applicable in general min-man games, such as (local/differeettaaa) Nash equilibrium (Adolphs et al. 2019 Mazumdar & Ratlifi 2019). local minmax (Daskalakis & Panageas 2018), local minimax (Jin et 2019), (local/differentiaa)
Stackleherg equilibrium (Fiez et 2000). local robust point (Zhang et al.J 2020). The plethora of solutions concepts is perhaps suggestive that "solving" general min-man games unequivocally
may be too ambitious a task. Autraction to spurious fixed points (Daskalakis & Panageas 2018).
eycles Vllaaaiis-Gkaragkouun Gkaragkounis al. 2019), robustly chaotic behavior (Cheung & Piliouras 2019
Cheung & Piliouras] (2020) and computational hardness issues (Daskalakis et al. (2020) 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 theo- retic solution that is selected by standard optimization dynamics (e.g. gradient descent)?

---

Under review as a conference paper at ICLR 2021
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 C R" and G R.M + Y C R and continuous convex-concave function X x I., such that the min-max game is
min max ERR $ER
(Hidden Convex-Concave (HCC))
We call this class of min-max max problems Hidden defined hidden bilinear games of Vlatakis-Gkkragkkainn et al. (2019).
Games, generalizes the recently
Our solution concept. Out of all the local Nash equilibria of HCC games, there exists a special subclass, the vectors (0", x²) 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 (0'.0") o²)) "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 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 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 so- lutions relies on the Euclidean distance from the equilibrium being Lyapunov function. In contrast, in HCC games where optimization happens in the parameter space of 0 o, the non-linear nature of F, G distorts the convex concave landscape the output space. Thus, the Euclidean distance will not be in general Lyapunov function. Moreover, the existence of any Lyapunov function for the trajectories in the output space F, G does not translate to a well-defined function in the parameter space (unless F, G trivial, invertible maps). Worse yet, even if L has 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.
Lyapunov Stability. Our first step is construct initialization-deeendeee I. Lyapunov function that accounts for the curvature induced by the operators F and G (Lemma 2). Leveraging a potentially infinite number of weteliiiatioodddeeeeeede mild assumptions the outputs of F, G stabilize around the von Neumann solution of L.
Lyapunov functions in Theorem we prove that under
Convergence. Mirroring convex concave games, we require strict convexity concavity of L to pro- vide convergence guarantees to von Neumann solutions (Theorem 5). 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[) [D. Even in non-strict HCC games, we can add regularization terms to make T. strictly convex concave. Small amounts of regulariza- tion allows for convergence without significantly perturbing the von Neumann solution (Thcorem 6) while increasing regularization enables exponentially faster convergence rates (Theorem
Organization. In Section we provide some preliminary notation, the definition of our model and some useful technical lemmas. Section Bis devoted to the presentation of our the main results. Sec- tion 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 well further discussion on applications to the Appendix.
2

---

Under review as a conference paper at ICLR 2021
2 PRELIMINARIES
2.1 NOTATION
Vectors are denoted in boldface x, unless otherwise indicated are considered as column vectors. We use |1-|| corresponds denote the f--norm. For function f R R we use Vf denote its gradient. For functions of two vector arguments, y) R x R + R, we use Vxf. Vyf to denote its partial gradient. For the time derivative we will use the dot accent abbreviation, i.e., x d [()]. A function J will belong to C" if it is r times continuously differentiable. The term "sigmoid" function refers to R + R such that o (2) (1 (1)-)))-
2.2 HIDDEN CONVEX CONCAVE GAMES
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 superset of strictly convex strictly concave functions that are usually studied in the literature.
Definition L IR" Rm + is convex concave if for every y E R L(-y) convex and for every E R. L(x,)) is concave. Function I, will be called strictly convex concave if it is convex concave and every x x E R² x RTT 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 functions fi R R while the maximization player is equipped with m functions Ø3 Rm - R. We will assume in the rest of our discussion that fú, Uj L are all C functions. The inputs 0, rR and Φ, E Rm are grouped in vectors
00
22
Om]
F(O) (0,
f2(02)
fx(0.))
$2
$m
G(0)) (
92 (2(22) .. (xm
We are ready to define the hidden convex concave game
(0" x8) = arg min arg max L(F G(Ø)).
BERN
ERRM
where N En n. and M Σド= Mj. Given 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 R" x RR. For games defined over convex compact sets, the existence of at least one solution guaranteed by von Neumann's 's minimax theorem. Our defi- nition of HCC games can capture games on restricted domains by choosing appropriately bounded functions fi and 9j- In the following sections, we will just assume that Solution(L) 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 HCC game:
aL. Vo, L(F(O), G(Φ) = (o...(0)) (F(0), G())) 0f: dL
0, =
b
V L(F G(Ø)) = (0,) 0g;
(F(0), G())
8.1
ON2
@xnx
fx(0N)
gar (dar drrl
F(0)
L(F(8).
G
011
81z
...
fi (0:)
(db))
d/
P12
...
0. V. ((F(O))))))))) (())
b = LF(())
3

---

Under review as a conference paper at ICLR 2021
2.3 REPARAMETRIZATION
The following lemma is useful in studying the dynamics of hidden games.
Lemma 1. Let k Rd R be C2 function. Let h R - R be C' function and x(t) denote the unique solution of the dynamical system E,. Then the unique solution for dynamical system Dg is
211 = x(So h(())s))
&
= Vk(x)
{ 2 v(t)Vk((z)) Σz
(2)
x((1)
Xinit
2z(0)
Xinit
f(((,)
A (b)
(d)
Equilibrium-value fr
(
(g) 0:
1.5
Figure 1: Neither Gradient Descent nor Ascent can traverse stationary points. An immediate conse- quence of Lemma| is that if we initialize in the above example 0 (0) at (a), (i)) can not escape the purple section. This extends cases where 0, is vector of variables.
By choosing h(t) = (t)((tt) G(t))/Ofz and h(t) = (F)( G(t))/Og, respectively, we can connect the dynamics of each 0; and 3j under Equation (1 to gradient ascent on Ji and Øj- Apply- ing Lemma] [] we get that trajectories of 0: and Φ, under Equation (1) are restricted to be subsets of the corresponding gradient ascent trajectories with the same initializttonss For example, in Fig- ure D (t) can not escape the purple section if it is initialized at (a) neither the orange section if mitiilliazd at (f). This limits the attainable values that ft( and gj (t) can take for a specific initialization. Let us thus define the following:
Definition 2. For each initialization x(0) E1, Ime (x()) is the image of ls x R R.
Applying Definition 2 in the above example, Im,, (0)( = f( if 0, is initialized at (c). Additionally, observe that in each colored section (O.(t) uniquely identifies (t). Generally, even in the case that 0; are vectors, Lemma [ implies that for given (,))). (t)) uniquely identifies (t). As result we get that new dynamical system involving only fa and gj
Theorem 1. For each initialization (0(0), ((0) of Equation I there are C² finctioons Xo.(o) (²,(0) such that (t( = Xe.co) (t) and (t) = X (1)(), If ((()),((t) sat-
isfy Equation (1) then fi(l)= = (1). and 95(() g3 ()) satisfy
f. = V fo X (0) (f ØL Of.
(F.G)
ØL
9; V 9 X (X),
(F, G)
0g;
By determining the ranges of f, and 9j. an initialization clearly dictates if von Neumann solution is attainable. In Figure [ for example, any point of the pink, orange or blue colored section like (e), (f) or (g) can not converge to von Neumann solution with f((0.) = ft The notion of safety captures which initializations can converge to given element of Solution(L).
We will call the initialization (0(0), ((0) safe for a (p, q) E Solution( L) if (0) and (0) are not stationary points of ft and 9j respectively and p; E (0,,0000)) and
Definition
9 E Img, (Ø)
some fundamental notions of stability. We call an equilib- rium x* of an autonomous dynamical system = (xx(t)) stable if for every neighborhood U of x" there is neighborhood V of x" such that if x(0) E V then x(t) U for all t O. We call set asymptotically stable there exists a neighborhood R such that for any initialization x(0) e R, x()) approaches S as l +00. If R. is the whole space the set globally asymptotically stable.
Finally, in the following sections
4

---

Under review as a conference paper at ICLR 2021
3 LEARNING IN HIDDEN CONVEX CONCAVE GAMES
3.1 GENERAL CASE
Our main results are based on designing Lyapunov function for the dynamics of Equation (3)
Lemma 2. If L is convex concave and (0( 0(0)) is safe for (p. q) E Solution L), then the following quantity is non-increasing under the dynamics of Equation
N
h
(F, G)
Σ (o
dz
9j
dz
(4)
(2))
Vgz (Xa,
95
Observe that our Lyapunov function here is not the distance (p. q) in classical convex con- cave game. The gradient terms account for the non constant multiplicative terms in Equation 3 Indeed if the game was not hidden and fi and Øj were the identity functions then H would coin- cide with the Euclidean distance to (p. q). Our first theorem employs the above Lyapunov func- tion show that (p. q) is stable for Equation (
G
Theorem 2. If L is convex concave and (Ø(0), (()) then (P. q) is stable for Equation 3b.
safe for (p.q) SoluuiionL).
(p.q)
Clearly, for the special case of globally invertible functions F, G we could come up with equiv- alent Lyapunov function in the 0 sppcce. this case it is straightforward to transfer the stabil- ity results from the induced dynamical system of F, G (Equation (3) to the initial dynamical sys- tem of 0, & (Equation (T)). For example we can prove the following result:
F(
Level sets of Lyapunov function of Equation (4) for both F and being one dimen- sional sigmoid functions.
Figure 2:
Theorem 3. If ft and g, are sigmoid functions and L is convex concave and there is a (Ø(0), (())
that is safe for (p, q) E Solution(L), then (p), G (a) is stable for Equation
In the general case though, stability may not be guaranteed in the parameter space of Equation We will instead prove a weaker notion of stability, which we call hidden stability. Hidden stability captures that if (F)) (d)())) is close 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.
von Neumann solution, then (F()(t)), G()()))
Theorem 4 (Hidden Stability). Let (p.q) E SSolution L). Let Rj, and Rg, be the set of regular values of of ft and respectively. Assume that there is & >> O such that [p, E,p. + E] C Ry, and [gj 5. + + Rg. Define
r(t) F(O(t)) p11 (G((()) -
If ft and gj are proper functions then for every > 0, there is an such that
r(0) 6 = Vt > 0 r(t) <c
Unfortunately hidden stability still does not imply convergence to von Neumann solutions. Vlatakis- Gkaragkounis et al. (2019) 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 shown in Figure 2 To sidestep this, we will require in the next subsection the hidden game to be strictly convex concave.
value a E Im f is called a regular value of f if 44g E dom f: f(g) = o, it holds Vf(2) # O.
A function is proper if inverse images of compact subsets compact.
5

---

Under review as a conference paper at ICLR 2021
3.2 HIDDEN STRICTLY CONVEX CONCAVE GAMES
In this subsection we focus on the case where L is strictly convex concave function. Based on Definition 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 S Solution(L) L) then Z is locally asymptotically stable for Equation 33.
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 is locally asymptotically stable for Equation (3)
The above lemma however does not suffice to prove that for an arbitrary initialization (0 (0))
(F()), G())) approaches Z as t - +oo. In other words, a-priori it is unclear if (F()())) ( (0)
necessarily inside the region of attraction (ROC) of Z. To get refined estimate of the ROC of Z, analyze the behavior of H fs and 9 approach the boundaries of Im,, (0) and Img, ( (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 5. Let L, be strictly convex concave and Z Solution( L. is the non empty of equi- Ibria of I for which (0()), ((0) is safe. Under the dynamics of Equation 1 (F(O(1)), ((O()))) converges a point in 2 as t + xc.
The theorem above guarantees convergence to Neumann solution for all initializations that are safe for at least one element of Solution(L) L). However, this is not the same as global asymptotic stability. To get even stronger guarantees, can assume that all initializations it is straightforward to get global asymptotic stability result:
safe. In this case
Let L be strictly convex concave and assume that all intitializationss are safe for at least one element of Solution(L.. The following set is globally asymptotically stable for continuous GDA dynamics.
Corollary 1.
(0' " EER" X R". (F("", E &Solution()) [L)
Notice that the above approach global asymptotic convergence using Lyapunov arguments can be extended to other popular alternative gradient- heuristics like variations of Hamiltonian Gradient descent. For concision, we defer the exact statements, proofs in Section 8.2.2
3.3 CONVERGENCE VIA REGULARIZATION
Regularization is a key technique that works both in the practice of GANs Mescheder et al. (2018); Kurach et al.] (2019) and in the theory of convex concave games Pérolat et al. (2020); Roth et al. (2017): Sanjabi et al. (2018). 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 a utility L(x.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
X L'(x,y) L(x,y) + 2 |xx|
1
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 X the equilibria of L are not significantly perturbed.
Theorem 6. If a convex concave function with invertible Hessians at all its equilibria, then for each e 0 there is X > 0 such that T,' has equilibria that c-close the ones of L..
Note that invertibility of the Hessian means that L must have unique equilibrium. On the other hand increasing increases the rate convergence of safe initializations to the perturbed equilibrium Theorem 7. Let (0(0), (0)) be a safe initialization for the unique equilibrium of L' (p, q). If
r(t) (F((())) 212 (G((t)) qll
then there are initialization dependent constants Co Cr such that r(1) S co expepXxccl

---

Under review as a conference paper at ICLR 2021
4 APPLICATIONS
In this section we show how our theorems provide connections between the framework of hidden games and practical applications of min-max optimization like training GANs.
Hidden strictly convex-coneave games. We will start our discussion with the fundamental gen- erative architecture of Gooofellow al. (2014a)'s GAN. In the vanilla GAN architecture, as it is commonly referred, our goal is to find a generator distribution tribution Pdata- To find such generator function, we can use discriminator D that "criticizes" the deviations of the generator from the input data distribution. For the case of discrete Pdata over set N, the minimax problem of GGodffllow al. (2014a) is the following:
that is close to an input data dis-
min (o EIEN (a)===
max DE(0.1)
D) = Σ
Paaa(()) log( (((x)) +
Σ ZEN
po(x) log(1 - - D(x))
=EN
The problem above can be formulated as a constrained strictly convex-concave hidden game. the one hand, for a fixed discriminator D* the V VGG, D*) is linear over the pa(z). 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 EeeN (z) = we can introduce a Langrange multiplier. Having effectively removed the constraints, equilibrium of the game, an outcome consistent with our results in Corollary T It is worth noting that while the Euclidean distance to the equilibrium is not monotonically decreasing, Ht)) is.
see in Figure the dynamics of Equation ① converge to the unique
[[FF0 P 1G0 qll [A
steps
steps
Figure 3: Comparison of f2 distance from the equilibrium and the Lyapunov function. Both of them converge to zero as we state but & distance not monotonically to zero. For Pdata we choose fully mixed distribution of dimension = Given the sigmoid activations all the initializations are safe. We defer the detailed proof of convergence in Section 9.2
Hidden convex-concave games & Regularizaiton. An even more interesting case is Wassertein GANs-WGANs (Arjovsky al. (2017)) ). One of the contributions of Lei al. (0019) is 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 Lipschitz constraint in the discriminator function. For simplicity, Lei et al. (2019) replaced this constraint with quadratic regularizer. The min-mas problem for the case of one-dimensional Gaussian N af) and linear discriminator (x(x)) o with x activation is:
min max TWGAN(Gas Do) Ex~pan [D(X) - Ex [(X)] - 2²122
oeR HER
E [ (a a²) 02/2
E Eew u²
Observe that VWGAN not convex-concave but it can posed as a hidden strictly convex-concave game with G(a) = (a? - -a²) and F(r) v. When computing expectations analytically without sampling. Theorem 5 guaranteess convergence. In contrast, without the regularizer VWGAN can be modeled as a hidden linear-linear game and thus GDA dynamics cycle. Empirically, these results are robust to discrete and stochastic updates using sampling as shown in Figure 4 Therefore regu- larization in the work of Lei et al. (2019) was vital ingredient in their proof strategy and not just an implementation detail. In Section 9.3 we also discuss applications of regularization to normal form zero games.
7

---

Under review as a conference paper at ICLR 2021
3
GDA
1
2000
-1
10000
-0.1
0.
3
0.0
10
20
Figure 4: On the left, we show the trajectories of regularized GDA for a = 1 as well as the level sets of Equation 4 All trajectories converge one of the two equilibria (0, 1) and (0, -1) whereas without regularization, GDA would cycle the level sets. In the right figure, we replace the exact expectations VWGAN with approximations
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 Lei et al. (2019) converges to the (0, 1) equilibrium.
The two applications of HCC games in GANs are not isolated findings but instances of broader pattern that connects HCC games and standard GAN formulations. As noted by Goodfellow (2017), 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 Goodfellow et al. 4014 f-GAN (Nowozin et al. (2016) and WGAN AGGAN/Arjovsky et al. (2017) can all be thought 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 missing from recent literature, in Section 9.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.
5 DISCUSSION
In this work, we introduce a class of non-convex non-concave games that we call hidden convex concave (HCC) games. this class of games, the competition on the output/operator space has convex concave structure but training happens in the input/parameter space, where the mappings between input and output space are smooth non-convex non-coneave functions. The main spiration for this class is the indirect competition of the parameters of generator and discriminator on GANs architectures. Our analysis combines ideas from game theory, dynamical systems and control theory such Lyapunov functions and LaSalle's theorem. Our convergence results favor not arbitrary local Nash equilibria, but only von Neumann solutions. To the best of our knowledge, such last iterate convergence results are the first result of their kind. Given the modular structure of our model and proofs, HCC games show particular promise as a theoretical testbed for studying which dynamics more well suited to which GANs. We believe that further positive results of this kind for different combinations of GAN formulations and learning algorithms are possible by properly adapting our current techniques.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Jacob Abernethy, Kevin A Lai, Kfir Levy, and Jun-Kun Wang. Faster rates for convex-concave games. In COLT, 2018.
Jacob Abernethy, Kevin A Lai, and Andre Wibisono. Last-iterate convergence rates for min-max optimization. arXiv preprini arXiv: (tle::990.0202,, 2019.
Leonard Adolphs, Hadi Daneshmand, Aurélien Lucchi, and Thomas Hofmann. Local saddle point optimization: A curvature exploitation approach. In The 22nd International Conference on Ar- rificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, pp- 486 486-495, 2019. URL URLLtttp://rrceeaiiggg mlr. press / v adolphsl9a........ html
Martín Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein GAN. CoRR, abs/1701.07875. 2017. URL http: www.:org/aaee abs 1701. C7875
James Bailey and Georgios Piliouras. Fast and furious learning in zero-sum games: vanishing regret with non-vanishing step sizes. In Advances Neural Information Processing Systems, pp- 12977-12987, 2019.
James P. Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games. In Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, doi: 10. 10.1145/3219966.321933..
June 18-22, 2018, pp. 321-338, 2018.
htt.h:tpp://ddo
org 1xg/10.10 11e.11155555 3219166. 3219235
James P Bailey, Gauthier Gidel, and Georgios Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. In COLT, 2020.
David Balduzzi, Sébastien Racanière, James Martens, Jakob N. Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n-player differentiable games. Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference
Machine Learning, ICML 2018, Stockholmssmassan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 363-372. PMLR, 2018. URI TtRLhttp://// httttt:://prrcceedinnge m.ress/ v8C/ba ddzzzi Ba. html
Sanjay P. Bhat and Dennis S. Bemstein. Nontangency-based іуарunov tests for convergence and stability in systems having continuum of equilibria. SIAM J. Control and Optimization, 42(5): 1745-1775, 2003. doi: 10. 10.1133 13.11///3663311292200777 $0363012902407730
URL htttps:///aatt ootpeii..rrg/11. 1137/
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, USA, 2004. ISBN 0521833787.
Nikolo Press, 2006.
and Gabor Lugoisi. Prediction, Learning, and Games, Cambridge University
Yun Kuen Cheung and Georgios Piliouras. Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games. In COLT, 2019.
Yun Kuen Cheung and Georgios Piliouras. Chaos, Extremism and Optimism: Volume Analysis of Learning in Games. arXiv e-prints, art. McXiv:2005.13995 May 2020.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradi- ent descent in min-max optimization. In Advances in Neural Information Process- ing Systems 31: Annual Conference on Neural Information Processing Systems 2018,
NewrIPS 2018, 3-8 December 2018, Montréal, Canada., pp. 9256-9266. 2018. URL
cc wttp://ccppppppppppeeeeee http:/811166t1t1111e Shee-imiit wwiiilmmiiittt------ cotoofooppiimiiiiiiioo
Stadient-descent in min wwt--minnaa-x---ooeee www.aaa-ttppiiii www.ttiiiiiiiiii.n.om.m....iioii
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and
constrained min-max optimization. 10th Innovations in Theoretical Computer Science Con- ference, ITCS 2019, January 10-12, 2019, San Diego California, USA. pp. 27:1-27:18, 2019. doi:
URL https:/:: btttps://doi.... /ww. org 123000..43331110 ITCS.
201 9. 27

---

Under review as a conference paper at ICLR 2021
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In ICLR, 2018.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization, 2020.
Lawrence C Evans. Partial differential equations and monge-kantorovich mass transfer. Current developments in mathematics, 1997(1):65-1266 1997.
Ky Fan. Minimax theorems. Proceedings of the National Academy of Sciences of the United States of America, 39(1):42, 1953.
Farzan Farnia and Asuman E. Ozdaglar. Gans may have nash equilibria. CORR, 2244200 2020. URL httpp:///axxi...rrrt httii..xvvv.oo..... www.oooggggaaaaoaaoee /aap//bb.....22222222
Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in stackelberg
games: Equilibria characterization, convergence analysis, and empirical study. In JCML, 2020.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A
variational inequality perspective on generative adversarial networks. In ICLR, 2019. URL
net https://openreviii wttp://wwww..eet//oooolldldllli-
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014a.
lan Goodfellow. NIPS 2016 tutorial: Generative adversarial networks. CoRR, 0oos/1001.0016 2017. / wttp://wwwww.aaa/..l/.oooooo/ 00160000000000
Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neu- ral Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014. Montreal, Quebec, Canada, pp. 2672-26688 2014b. URL nips. ec aaap:e//..--ggeeaaaaeee-aaaeeeee
attp:://appee
Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. In Advances in Neural Information Processing Systems, pp. 6938-6948, 2019.
Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggres- sively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. arXiv preprint arXiv:2003. 2020.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. CoRR, abs/1902.00618,, 2019. URL http:// arxiv. .rg. abs 111111002200111888
Hassan K Khalil, Nonlinear systems; 3rd ed. Prentice-Han Hall, Upper Saddle River, NJ, 2002. URL
https:// cds cern wtt.:.eww......ee//e11100001
Karol Kurach, Mario Lucic, Xiaohua Zhai, Marcin Michalski, and Sylvain Gelly. A large-scale study on regularization and normalization in gans. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9- 15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 3581-3590 PMLR, 2019. URL http::tp:/// http::/ppoocedinngg..c mir wwwpss/vv// kurach1 9a. html
Qi Lei. Jason D Lee, Alexandros G Dimakis, and Constantinos Daskalakis, Sgd learns one-layer networks in wgans. arXiv preprint arXiv:1910.07030, 2019.
Chris J. Maddison, Daniel Paulin, Yee Whye Teh, Brendan O' O'Donoghue, and Amaud Doucet. Hamiltonian descent methods. CoRR, abs// 809.05042, 2018. URL attp: http://aaxivvvoo/ abs/1809 05042
10

---

Under review as a conference paper at ICLR 2021
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
Eric Mazumdar and Lillian Ratliff. Local nash equilibria are isolated, strict local nash equilibria in "almost all' zero-sum continuous games. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 6899-6904. IEEE, 2019.
Panayotis Mertikopoulos, Christos H. Papadimitriou, and Georgios Piliouras. Cycles in adversar- ial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018 pp. 2703- 2717, 2018. doi:
URL httph:tttoosioii. www.doo...ooooooooooooooo 1137/1.
97816 975031 122
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Shenn Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra(-gradient) mile. In ICLR, 2019. URL https: https://ppeeviieeeeee net/ cont/forumidd
Lars M. Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually converge? In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th Inter- national Conference on Machine Learning, ICML 2018. Stockholmsmässan. Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 3478-3487. PMLR, 2018. URL htkphtttp://pocceeee ngs ml wwwppresssvvee. httl///0mmmeeeeeeeee 8a html
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis extra estra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pp. 1497-1507. PMIR, 2020.
Yurii E. Nesterov. Introductory Lectures on Convex Optimization A Basic Course, volume 87 of Applied Optimization. Springer, 2004. ISBN 978 178-1-461334661-3, doi: 1010009997----419. 8853-9. URI. https: .rg/ /0/00000100 1007 907-077788--4411- 9-843199-883-99
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative ral samplers using variational divergence minimization. In Daniel D. Lee. Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016. December 5-10, 2016, Barcelona, Spain, pp. 271-279, 2016. http:://sapeer.nnnpscccccses//pp
URL http: wiw.......ppp.coom.m cttppp.ccccceeeeeeeee http://ppaaaeeeoooaaaaaaaaaaaaaa
generative
Brendan O' O'Donoghue and Chris J. Maddison. Hamiltonian descent for composite objectives. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché Bue, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Anmual Conference Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. an an- for composite-objeetiieee
2019. URL nip......ipi...........mm .ccppssc..
Lawrence Perko. Differential Equations and Dynamical Systems. Springer, 3nd. edition, 1991.
Julien Pérolat, Rémi Munos, lean-Baptisse Lespiau, Shayegan Omidshafici, Mark Rowland, Pe- dro 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. CoRR, abs/2002.08455, 2020. URL httg/bb//// https://arxiv> org/ abs / http:/bb//00020 20020000000000000 08456
Kevin Roth, Aurélien Lucchi, Sebastian Nowozin, and Thomas Hofmann. Stabilizing training of generative adversarial networks through regularization. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Anmual Conference on Neural Infor- mation Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 2018 2028, 2017. URL 1tt.:///ee.aaaaaaaaaaaaa//////aa
n http://pwww....appoopa.cpppeeaap

---

Under review as a conference paper at ICLR 2021
Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn. and Jason D. Lee. On the convergence and robust- ness of training gans with regularized optimal transport. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Gareet (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Pro- cessing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pp. 7091-7101, 2018. URL htRL:ttp:/// httptt:::p/pppp..nipp... cc/ robustness of training--ans- gans with teg..aaeeiiooe-oooaaaaaaaaaaaaaa
ottppp/ss.i.pscc//ppp////////--- on the convergeneeeeeeeeeee...ce.e and
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 350(7666):544335) 2017.
Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
Simmanouil-Vasileee YaatakisGGaaagkkon Lampros Flokas, and Georgios Piliouras. Poincaré recurrence, cycles and spurious equilibria in gradient-descent--sseelt for non-convex non-concave zero-sum games. In Advances Neural Information Processing Systems, pp. 10450-10461, 2019.
Jun-Kun Wang and Jacob Abernethy. Acceleration through optimistic no-regret dynamics. In Advances in Neural Information Processing Systems, pp. 3824-3834, 2018.
Guojun Zhang and Yaoliang Yu. Convergence of gradient methods bilinear zero-sum games. In International Conference on Learning Representations, 2019.
Guojun Zhang, Pascal Poupart, and Yaoliang Yu. Optimality and Stability in Non-Cone Non-Convex-Non: Concave Min-Max Optimization, arXiv e-prints, arXiv:2002. 1875,, February 2020.
12

---

Under review as a conference paper at ICLR 2021
CONTENTS
Introduction
Preliminaries
2.1
Notation
2.2
Hidden Convex Concave Games
2.3
Reparametrization
3
Learning in Hidden Convex Concave Games
General Case
3.2
Hidden strictly convex concave games
3.3
Convergence via regularization
6
Applications
Discussion
6
Background
14
6.1
Background dynamical systems
14
6.2
Background in convex optimization
16
6.3
Background in Game Theory
16
7
Preliminaries
17
8
Hidden Convex Concave Games
18
General case
19
8.2
Hidden strictly convex concave games
22
8.2.1
Gradient Descent-Ascenl Dynamics
2
22
2,2
Connections to Hamiltonian Descent
25
8.3
Regularization and convergence
26
9
Applications
28
9.1
Connecting GANs and Hidden
Games
..a.............................
28
9.1.1
GAN
29
9.1.2
f-GAN
31
9.1.3
WGAN
34
9.2
GANs and Hidden Constrained Optimization
35
9.3
Zero-Sum Games
37
13

---

Under review as a conference paper at ICLR 2021
BACKGROUND
6.1 BACKGROUND IN DYNAMICAL SYSTEMS
Our analysis combines tools from dynamical systems, stability analysis and invariance prin- ciples theory. We start with the definitions of the different stability notions. We remind the well known Lyapunov's Lyapunov stability criterion (Theorem 8 Stability analysis in con- vex concave games is further complicated due the possibility of non-isolated fixed points. To tackle this issue, we recall Krasovskii-LaSalle Invariance Principle (Theorem 2 powerful result that has several implications for the asymptotic stability of set in an au- tonomous (possibly nonlinear) dynamical system. In the special case where the goal set con- tains only stable fixed points a pointwise convergence theorem can be derived (Theorem [0]. Finally, we remind the notions of diffeomorphism and topological conjugacy of two dynam- ical systems, which are useful to transfer behavioral claims between equivalent dynamics.
Let f D -> Rh be a locally Lipschitz map from a domain D C R to R We consider dynamical systems of the form
f(x)
A point x for which f(x) 0 is called fixed point. We will be interested in the following notions
of stability for the fixed point points of Equation (*).
Definition (Stability properties, (Khalil 2002 Definition 4.1)). The fixed point x = - of Equa-
tion is
stable if. for each e >> 0, there is a 5 8(c) > 0 such that
[x(0]]| < 6 = ||x(t)|| <e V2
unstable if it is not stable
asymptotically stable if is stable and 5 can be chosen such that
||x(0)]| = lim x(t) =
1-00
The Lyapunov Theorem will be a useful tool to prove (asymptotic) stability of fixed point.
Theorem (Lyapunov Theorem, (Khalill 2002 Theorem 4.1)). Let x be a fixed point point for Equation (x) and D c IR" be domain containing differentiable function such that
0. Let V D R be continuously
(0) and V(x) > 0 in D - (0)
(()) < 0 D
then x = 0 is stable. Moreover if
V(x) < in D D- (0)
then x = 0 is asymptotically stable.
Unfortunately, the Lyapunov theorem is not very helpful when it comes to proving convergence in dynamical systems with non isolated fixed points. By definition, non-isolated fixed points cannot be asymptotically stable. Non isolated fixed points may give rise to more complex behaviour than point-wise convergence.
Definition 5. We say that a trajectory x(t) approaches set as for each 0 there is a T > 0 such that
dist(x(t),M) <e, v>
where the operator "dist" is the minimum distance from a point to set M
dist(p,
inf pp- x XEM
14

---

Under review as a conference paper at ICLR 2021
Definition 6. We say that set M is invariant for Equation if
x(0) M = x(t) E M, Vt E IR
We will say M is positively invariant if the above holds for 2 O.
We are ready to state LaSalle's Invariance Principle, general theorem that can help us study the stability of non isolated fixed points.
Theorem 9 LaSalle's Invariance Principle, Khalil 2002
Theorem 4.4)). Let S C D be a compact
set that positively invariant with respect to Equation ( Let D R be a continuously
differentiable function such that V (x) in Q. Let E be the set of all points where V(x) 0. Let M be the largest invariant set in E. Then every solution starting in St approaches M as t + oc.
LaSalle's theorem does not give us pointwise convergence directly. But the special case that contains only stable fixed points
apply the following theorem
Theorem 10 (Pointwise Convergence Theorem, (Bhat & Bernstein, 2003 Proposition 5.4)). Let x(t) be a trajectory of Equation the positive limit sets of x(t) contain a stable fixed point then x() converges to it as 0o.
Definition (Differomorphism, Perko 19911). Let U, V be manifolds. A map f: - V is called a diffeomorphism if f carries U onto and also both and f are smooth.
Definition 8 (Topological conjugacy, Perko 1991 ) Two flows 4, A A and V : B B are conjugate if there exists homeomorphism A + B such that
Vo E A,t E R
g (x)) = Vr(g(z))
Furthermore, two flows 4, phism g A + B such that
A and v, + B are diffeomorphic if there exists diffeomor-
VI E A, : =
Ve(g(z)).
If two flows are diffeomorphic, then their vector fields are related by the derivative of the conjugacy, That is, we gel precisely the same result that we would have obtained we simply transformed the coordinates their differential equations.
15

---

Under review as a conference paper at ICLR 2021
6.2 BACKGROUND IN CONVEX OPTIMIZATION
For the sake of completeness, we recall here the definition of (strict) convex/concave func- tion and its first order necessary and sufficient criterion. We will also discuss strong convex- ity and its second order characterizations.
We will be interested in notions from convex optimization throughout this work Definition (Boy & Vandenberghe, 2004 67)). Let
R" RR be a function then
f is convex if y ttE [0, f(tx t)y) S <tf(x) + +
f is strictly convex if
E (0,1): f(xx+ (1- < <f((x) t)f())
J is (strictly) concave if ff is (strictly) convex.
We will also use the first order characterizations convex and concave functions
Theorem 11 ((Boyd & Vandenberghe 2004
69-70)). Let f : R + R be a differentiable
function.
f is convex if and only vx, IR" f(y) 2 f(x) + fx(x) (y xx)
f is concave if and only if E R" f(y) S f(x) + (X(x) x)
To establish convergence rates, we will use the notion of strong convexity
Definition 10 (Nesterovv) 2004 p. 63)). A continuously differentiable function f of RR" will be called μ strongly convex for positive constant μ for all x,y IR" we have
f(y) f(x) + (VI(x). x) 2 yl1
We will also use second order characterizations of strong convexity
Theorem 12 ((Nesterov) 2004 p. 65)). twice continuously differentiable function f is μ strongly convex for positive constant and only if for all x E TR. have
2 f()
ul
Symmetrically, function will be called strongly concave if - is μ strongly convex.
6.3 BACKGROUND IN GAME THEORY
In this short section, we remind to the reader generalization of Con-Neumann's 's Minimax theorem, which will exploit to analyze the equilibrium solution of the different GANs' architectures. A special case of Fan's minimax theorem is the following
Corollary (Fan's minimax theorem, Fan 1953 ) Let c Rn and Y C T be convex non- emply sets. Suppose that X is compact and f:X. x Y + R is function such that [( v) is lower semicontinuous on X. for each y E Y and that f is conver concave. Then we have that
min sup f(x, v) sup min f(x, v). #EX veY
yey yey=EX ZEX
16

---

Under review as a conference paper at ICLR 2021
7 PRELIMINARIES
The below time-reparamettizztion lemma shows that the solution for non-autonomous sys- tem, multiplicative gradient flow can be derived by just time-rescaling of the solution of the simplified gradient ascent dynamics. Indeed, since the multiplicative term is common across all terms of the vector field then over the time it dictates only the magnitude of the vector field (the speed of the motion), but does not affect the directionality other than moving backwards or forwards along the same trajectory.
Lemma 1, Let k Rdd - TR. be a C2 function. Let R - be a C2 function and x(1) denote the unique solution of the dynamical system Et. Then the unique solution for dynamical system Dn is 2(1) = x(So h(s)ds)
X =
Vk(x) Xinit
{
2 (()) Xinit
x(0)
Ei
(1)
(5)
Proof. Firstly, notice that it holds x(0) = =inni and x = Vk((), since x is the unique solution of Σn It is easy to check that:
20) x( L/" h(s)ds) = x(0) = Xinit
(Si Mssdss dlfo h(s)ds]
(L, h(s)dss)
) h(t) - Vk(z)h(t)
Vh x
In order to leverage the convex-concave properties of the operators in our hidden structure under the Gradient Descent Ascent dynamics we need to recover the equivalent system (T) the operator space
(t)
(+)
3 1 1
VL(F(O), G( VI(F(0), G()) 0
0
(o. )
From this point, applying the aforementioned lemma, under GDA each fa and 9, follows time dependent rescaling of the corresponding gradient ascent solution. Exploiting the monotonicity of (1( and g)) under gradient ascent, we can construct an invertible map between the parameter space {0.,. o,)} and the operator space {(fr. 9,)} which allows us to construct the equivalent system
the operator space. Notice that the properties of gradient ascent are crucial since the operator space can be arbitrarily smaller in dimension. In this case a smooth invertible map that is common for all initializations cannot exist.
Theorem 1. For each initialization (0(0), ((0) of Equation
1 there are C functions X (o)())a If (0(t). o(t) sat-
Xo.(0) X0,(0) such that (t) Xo. (t)) and o; (t)
isfy Equation (1) then fi(()) = (()) and g, (1) 9j ( (1)) satisfy
OL (F.G)
Ve, f X
ØL 0g,
9; = V Φ, 9 X (o)()))
(F, G)
Proof. Let us first study a simpler dynamical system (Σ*) with unique solution of (0) (t).
(z) = (0)
E = =='==
z()) (z())
17

---

Under review as a conference paper at ICLR 2021
It is easy to observe that:
f; = Vf(2)² [V
(0) is a stationary point of fú then the trajectory of z is single point. But the trajectory 0; under the dynamics of Equation (I) is also single point
can pick the following function
(o) (fi) (,))).
On the other hand if (0) is not stationary point of fi. fi continuously increases along the trajec- tory of (E*). Therefore (0) = (o( (t)) is an increasing function and therefore invertible. Let us call (0) (fi) the inverse.
Let's recall now the 0g part of the dynamical system of interest Equation
aL
0. - v.
G(O))
0f:
initialized at 0.(0). Applying Lemma 1 for the first equation with
aL
h(1) of:
(F()()),, G()())) G((())
we have that under the dynamics of Equation
I
0,(t) = (0) (L h(s)ds)
(P)
Thus it holds
1 ((ooddd))
Ao,co) (So M())ds)
[((O((1)) =
(T0.c0)
or equivalently
f. M(s)ds = 1 10,10) (f((O.(1))
Plugging in back Equation (P
(1(1) (0) (0) (A (f.(O.
Therefore we can pick
Xo. (/.) 10) (A (f+)
which is C³ composition of C functions. We can perform an equivalent analysis for (,) and Øj to pick CD function X4 (0) Let us now track the time derivative of fi(O.) and (Ø)))
0f. aL
= Vo.f( = Vo, f: (1))
(F, G)
0L.
9 Vo,9)(0,)0 V ( 1
(F G) 0g,
can now replace 0, = Xo (fi) and Φ5 (o, to get the equations required.
HIDDEN CONVEX CONCAVE GAMES
In this section, we analyze the derived stability propertics of the hidden convex concave games. It is worth mentioning that without strict/strong convexity/concavity from at least one the operators, the quality the results are limited to "Lyapunov Stability". Firstly, present construction of Lyapunov function for the operators' dynamics Theorem 2 Then, in Theorem 3 Theorem we explore the stability of the initial conditions in the parameter space.
18

---

Under review as a conference paper at ICLR 2021
8.1
GENERAL CASE
The following theorem presents the construction of a Lyapunov potential function for the in- duced operator dynamics. To motivate its construction, we can study a fundamental convex- concave function L(x, y) pr= (y g)² with saddle point (p.g). q). Under the gradient- descent-ascent dynamics
i =
VoL(x,3) 8) v,I(a.y)
(minimization of convex part) (maximization of concave part)
is easy to check that (x,, y) (x 2)2 (v x)² meets all the criteria of a Lyapunov function. The construction below extends this argument any convex-concave function L(F, G) and bypasses the more complex multiplicative terms for the gradient induced dy- namics of Theorem Notice that
H(F, G) G) Σ/"
N
2- (2)1
M E// Σ
2 2- 9
dz +
dz (X,,
i=1
j=1
coincides with the Eg distance from (p, q) in the case of gradient norms equal to one, i.e.
|V || =1
Lemma 2. If is convex concave and ()) 0(0)) is a safe for (p. q) E Solution(L) L),, then the following quantity is non-increasing under the dynamics of Equation (3:
N
f
H(F, G)
(=))1 dz +
dz
VV
[ (x, (2)
95
Proof. Simple substitution gets us the following
Σ U1 p4) OL
(g) 43) 0L
0f. (F, G) Σ
(F, G)
0gj
(F p. VF G)) + (G q, VaL(F G))
By Theorem 11 for the convex LL. G) and concave L(F.)).
F - p. VpL G) < L(p, G) - L(F,G)
(G q. VeL G) < L(F, G) L(F.q)
Thus we can end up writing
# S [pp, G)
< L(p G) L(p.q) L(p.g) L(F. <
The last inequality holds since (p. q) E Solution L.). Indeed, if (p, q) is a saddle point L then
L(p, G) S L(p, q) S L(F,q).
Theorem 2. If L is convex concave and (Ø(0), ((0)) is a safe for (p, q) e Solution L), then (p, q) stable for Equation
Proof. Leveraging Lemma 2 there is function И which is well defined in D
(Im,, (0)( {Img, (0))) and in this domain A < 0. Given the safety conditions we know that q) E D. Observe that for the proposed function, it holds that H q) 0. Also for each fi and g, term in H we know that it has its minimum of value 0 at the corresponding p. and qj- We can deduce this by taking the derivative of each term study its monotonicity. For example, the f; terms are strictly increasing in fi > P; and strictly decreasing in f: P:- Thus for all D {(p.q) H > 0. Applying Theorem for the continuously differentiable H we have that (p, q) is stable for Equation 3).
19

---

Under review as a conference paper at ICLR 2021
In the following example, we examine how it is possible transfer the stability properties between two (topological conjugate) dynamical systems.
Theorem 3. If Is and 9j are sigmoid functions and L. is convex concave and there is (0) (0)) that is safe for (p, q) E Solution(L) then (F)), G G-) is stable for Equation
Proof. Firstly, we recall the property of sigmoid's gradient:
do(x))
= (1))(1
dr
Thus the transformed dynamical system in the operator space can be written as:
f =
- - OL (F, F. a%.
(T)
93
(1 ogg
22 FF G)
Notice that
The dynamical system (T) in the operator space is independent of the initial conditions. In fact, the dynamical system of (T) and the one of Equation ( called (E) for short, are diffeomorphic for all initializations, not just a specific trajectory.
2. Since (0))), ((0) is safe, using Theorem we get that (p, q) is stable for (T)).
We would like to prove that for every open neighborhood V (F)) G-) there exists an open neighborhood U of (F (p), Ga) such that
iiit imit) E VI 2 0: (0(().(()) E V.
Using the diffeomorphism neighborhood of (p, q) since is open and ((F= (q)( = (p.q) E >VV). By Item 2 since (p, q) is stable for (I') there is an open neighborhood Ü (p, q) such that:
7x-r between GDA dynamics of (Σ) and (T) (VV is open
(Fintt Ganit) E Ú
vt 0: (F(t). G(t) (V)
equivalently
(O mit) E
Vt 0: 7 (0 (()))((t)) 7VV
Indeed, using the inverse diffeomorphism -1 we can establish that for U = (Ú) ) it holds that
iiin Pinit) E U
VI. 0: (0()) e V
Until now, we have established the stability of pair (p. q) for the induced dynamics (7)- By the construction of the induced dynamics, (T) is coupled only with very specific initial condition 10mit M.nit.. In order to tackle the challenge of a stability result for a whole region of initial conditions, in the following lemma we prove that r(0, x) = | F - 2 (
all² can work like an intrinsic measure of closeness for the (0. Φ parameter space around hidden fixed point of the (F, G G--opeato space. Under this "hidden" neighborhood notion, stability property be taken by assuming the properness of the hidden operators.
Theorem 4. Let (p, q) E Solution L). Let R,, and Rg, be the set of regular values of fo and gj respectively. Assume that there is 0 such that [p, E. P: + Rs, and [9; E, qj + Rgg Define
r(t)
F((()) 2 (t(((t) q11
If ft and are proper functions
then for every > 0, there is an such that
r()) < = 2 0: rtt) < e.
value a E Im is called a regular value of f if 44 E dom f f(g) = o, it holds Vf(g) # 0. 'A function is proper if inverse images of compact subsets compact.
20

---

Under review as a conference paper at ICLR 2021
Proof. Let define the following sets
Vi n Ej m
: Bj = |
0 $ R
R
f((0.) (p. {. + 9)(0;) E [gj - 5.9g +
Since Si and Øj are proper A, and B3 compact sets. Thus, the continuous functions (0:)) and |1V (0,) have minimum and maximum value on A; and B3 respectively. Let call K f. and Kg, the maxima and K,, and Kig the minima. Observe that the minima and maxima must be all greater than zero since [p: E.P; + +] and [ 5.9, are regular values. Let us define
min min f min Kg; Isi5n
15$5m
K max max K max Kgj ISign
1Sism
where K 2 x > O as we discussed. Let us create the following set
S= (( E ERN x R
Vi [ E Ai, Vj [m E B₁}
We can prove that every (0. E S is safe initialization for (p. q). Of course, every 0, and Φ; are not stationary points of fi and 9j respectively. We also need to prove that the equilibrium (p. q) feasible. We will prove this by contradiction. Let there be (0. Φ) E such that (p. q) is not feasible. Without loss of generality we can assume that there is E [m] such that É Im,, (0.). The case for the gj is symmetrical. Along the gradient ascent trajectory of fi with initialization at 9, observe that (t) cannot attain infimum or a supremum in [p: E. Pt + E] because there are no stationary points of J& A,. Observe also that at initialization f((0,) [p: E,P; + 6. Thus [p. - p. E] C Im,, (0.), contradiction.
Let us pick an initialization (0()), ((0) such that r(0) S 5?. It clear that (0()), (()) E S and so it is safe for (p, q). We can do the same steps as in Theorem below does not increase under the dynamics of Equation ①
2 to prove that the function HFF, G)
N
f
H(F. G)
Σ
Pt fi (o) (2))
de +
qj Xx (0) (z)
dz
VV
Observe that since (0(0), ((0)) E we have that the interval between pt and (0) belongs in [p: - E.p. + E and f.)) 2 k in this interval. Thus we can write
(O)) - Pb)
(((0.(0))
2- Pr
2x
IV (x)
Repeating the same argument for all fa and g, have that
r(0)
2 ((F(O())) G($()) 2 H(F((()),
G($(1))
2x
Let us pick r(0) (2 g2 x- We already know that trajectories start in S. We will
prove that they also remain in S. We will do this by contradiction. If a trajectory escaped 5, then without loss of generality this means that there is at least an [m] such that some > 0, f(()((t)) & lp. - E. + E.. The case of gj is similar. Clearly we have that (1))
PL
p X (0) (2))
dz min
VX dz,
Pt VX (2)) de
ps
p.
As above, we have that the gradients in the integrals of the right hand side are less or equal than K so
(.0)(11))
g²
= Pj
de 2
2K
The terms of H are all nen-negative so we have that
r(0)
(((0((1)
$² 2K
2 H(F(O())) G($(1))
P:
dz
2x
21

---

Under review as a conference paper at ICLR 2021
But r(0) < < k. contradiction. So the trajectories will stay in S. We can then write
((()((1))
(Ji(O.(()) pt)
Pi Vi (2))II de 2
2K
Repeating the same argument for all fi and 9, we have that
r(0)
2 H(F(O(O), G(O 2 r(t)
2x
2k
For every >> O, there is positive 8 = min(f".c| such that
K
r(0) 8 = r(t) <E
A special case of the above result is the standard convex-concave games:
)) be strictly convex concave and Solution L) is the non emply set of equil- bria of L. Then Solution[]] L) locally asymptotically stable for continuous GDA dynamics.
Corollary 3. Let L(x,y)
Proof. The proof of the above classical result can be derived by the straightforward application of Lemma 3 for the case of Fxx) = X and G = y. Notice that i) if F, G are the identity maps all the initial configurations are safe and ii) if VF || == 1, then the initialization-deeeneent
Lyapunov functions coincide to a single Lyapunov function, which is actually the squared Euclidean
distance r(0, Φ) = [())) pll + [[) qll
pll 16 q
8.2
HIDDEN STRICTLY CONVEX CONCAVE GAMES
8.2.1 1
GRADIENT DESCENT-ASCENT DYNAMICS
In the following preliminary result, we show that strict convexity or concavity in L(. :), for at least one of its arguments, suffices to yield locally asymptotic stability starting from safe initial condition. Our argumentation leverages the power of Theorem / and combines the previous section stability results. Here, will firstly outline the basic steps below:
1. We start by showing that there exists compact set Ω C D.
2. Therefore, since H < 0 (Lyapunov property), any configuration (F(0), G(O)) starting from a bounded sub-level set Ω of H, will remain inside Ω over all time.
3. The second crucial observation is that thanks to the strictness on convexity or con- cavity of L. the largest invariant set of i contains only points belonging to Von Neumann's Solution(L).
Then Theorem 9 implies the local asymptotic stability of set Z for Equation
Lemma 3. Let L be strictly convex concave and Z C Solution L) is the non empty set of equilbria of L for which (0()), (00) is safe. Then Z is locally asymptotically stable for Equation (3).
Proof. Pick a point (p, q) E Z. Since our initialization is safe for this saddle point, we can construct the H function as in Theorem 2 and prove that it has the following property
H < D (Im,, (0, (O)) x (Im,, (b,
(F() G()())) (p. q) then the theorem holds trivially. Otherwise, take a ball centered at the equilibirum with small enough radius such that it is contained in the interior of D.
Hg = min
H(F, G)
(F. B)
= {FF G) B|H G) < Ho/2]
We know that in both of the cases Hg 0 from Theorem
22

---

Under review as a conference paper at ICLR 2021
Since H < 0, starting in ?2 it implies that (F G(t) I Ho fort 2 0, so is forward invariant. Since 5 C D we know that it is bounded. Q is closed since it is a sublevel set of continuous function. Notice that the restriction of f2 on B does not affect the above properties since Q is in the interior of B. Thus Q is a compact forward invariant set, satisfying the requirement of Theorem 9
Let E = {E, G) E (F, G) = 0}. Without loss of generality we can assume that L(: q) is strictly convex the case of L(p. -) being strictly concave is similar. In the following inequality
H < (p,, G) L(p. q) + L(p. q) L(F, q) S
we know that L(p, G) (p. q) I 0 and L(p, q) L(F, q) S.
So H 0 implies L(p. G) L(p. q) L(F, q). By the strict convexity of L(-, q) we know that this means that F p. Let M be the largest invariant set inside E. By the properties of M being invariant subset of E we have
(F()), G(O)) E EM =
vl F(() and L(p, G(() - L(p, q)
Taking the time derivatives each of the constant quantities, they should be zero.
aL Vi [ Vio. (p.))
0
pp. G)
of.
M
0L
2
L(p, G(t))
> 1 (0)) (1)))
(p. G)
0g,
We know that || fi (p.)) * 00: by the safety conditions and that 0 inside D again by safety conditions. This implies
aL
Vi [N]
(p.
G) ()-G)
0f
OL
Vj E [M]
0g, (p. G) G)= 00
Thus M contains only stationary points of so M C Solution(T.). In addition M C D so only stationary points of L for which the initialization is safe are allowed so M S Z. Applying 9 we have that for any initialization of Equation (3) inside Q2 as t + Do (F(t), G(t)
Theorem
approaches M and thus Z is locally asymptotically stable for Equation
A special case of the above result is the standard convex-concave games:
Corollary 4. Let y(x,y) ) be strictly convex concave and Solution( L) is the non empty set of equil- bria of Then Solution( L) locally asymptotically stable for continuous GDA dynamics.
In the following main result of our work, we show that strict convexity or concavity in L(--)). for at least one of its arguments, suffices to yield convergence result to a Von Neumann's Solution L) starting from a safe initial condition. In order to get convergence results for any safe initialization, we need to study the region of attraction of the set Z Solution(L).. We refine the estimation of the region of attraction proposed in Lemma 3 by analyzing behavior of the level sets of H. More precisely, we show that the proposed Lyapunov function
N H(F = Σ 1=1
-- Ps (X (2))
M
95
2- qj Vg, (z) (o)
de +
dz
is radially unbounded. In other words, while the operators converges to their limit values (supremum/infimum of their domain) + +oc. In order to show that we analyze the asymptotic behavior of 1e TV/T. while F - sup fi. Hence,
A) Theorem implies that the trajectory will approach the set of stationary points of H or equivalently set of Von Neumann's 's Solution( L).
B) The stability of Solution L) and Theorem 10 leads to the conclusion that the tra- jectory will converges specific point of Solution(L).
23

---

Under review as a conference paper at ICLR 2021
Let L be strictly convex concave and Z C Solution(L) L) is the empry of equi- Ibria of for which (0(0), (()) is safe. Under the dynamics of Equation ( (F(O(t)), G(((t)) converges point in Z as t -
Theorem 3.
Again let's pick a point (p. q) E Z. Since our initialization is safe for this saddle point, we can construct the function as in Theorem D and prove that it has the following property
Proof.
# < 0 in D = (0,00)) x (Img, (0))
If G()))) (p. q) then the theorem holds trivially. Otherwise define
Hu = ((F((())) G(+(())
0 (F,, G) (F,(F, G) S Ho)
where we know that Ho > 0 from Theorem 2 Let assume that indeed Q is in the interior of D. Then, applying the same argumentation as Z are stable. So applying Theorem I0 we get that the trajectory initialized (F(O())), G()(0)))
commmnncombinee with Theorem) 2 all fixed points in
converges to a point Z. remains to prove our assertion about the set Q::
Claim 1. Ω is in the interior of D.
Proof. We will argue that as (F, G) approaches the boundary of D. the value of H should become unbounded. If this is true then for the finite upper bound of Ho. 12 should have no points close the boundary of H and thus it should be in the interior.
As (F, G) approach the boundary of points points of I (0)) or Img, (0)) respectively. We will study the case of f; since the case of 9j is symmetrical. The endpoint fis can be either the supremum or the infimum of the gradient ascent trajectory on Si or too if they do not exist, Let Jis be the supremum or depending on if the former exists. We can take the gradient ascent dynamics and apply Lemma to get
least one of the variables fi or gj approaches the end-
A Ve.J((Xe. (0) (f:))lI
We know that (t)) goes to fis when initialized at (0)) Let us define the following function
a(fi) /"
(X dz
Observe that = 1, thus oo a(f((t)) = co. In other words
f((t)
fix
lim 1-00
d=
dz op
IV (o)
Symmetrically if fis is the infimum or -c, then the limit above would -o. In either case
f: 4 St.
dz + 0
[V (o)
For the last step it is important to note that p; is not the boundary of D based the safety conditions. Therefore as (F, G) approach the boundary of D in the dynamics of Equation (3). at least of the terms of H goes infinity. Also note that all the terms of H are individually non- negative so no matter what the other variables in (F, G) are doing they cannot stop H + co.
Again, special of the above result is the standard convex-concawe games:
Corollary 5. Let L(x.y) y) be strictly convex concave and Solution(L) is the empty set of equil- bria of Under the continuous GDA dynamics (z(t), (t)) converges to a point in colution(L), as t +
24

---

Under review as a conference paper at ICLR 2021
8.2.2 CONNECTIONS TO HAMILTONIAN DESCENT
In GANs numerous learning heuristics are being tested and explored. One technique that has par- ticular interesting theoretical justification as well as practical performance is Hamiltonian Gradient Descent (HGD). Understanding the convergence guarantees for HGD an open research question Maddison et al. (2018); Balduzzi et al. 22:18::0 O'Donoghue & Maddison (2019). We provide some new justification about its success in GANs by provably establishing convergence of a modified version of HGD in relatively simple but illustrative subclass of hidden convex concave games, namely 2x2 hidden bi-linear games. This class of games is fairly expressive. Despite the restriction of planar bi-linear competition in the output space, the hidden game have an arbitrary number of variables in the parameter space, It's important to note that given the bi-linear nature of com- petition, the classical GDA dynamics cycles instead of converging the equilibrium as shown in et al. (2019)
MlttakisGGaaragkee
More precisely, in the hidden 2x2 bi-linear game presented in Vlatakis Mattakis-Gkaraakkoua Goaragkoumis et al. 2019
we have two functions/ / R- - [0, 1] and TRM - [o, 1 and two constants (p, q) (0, 1) where (p, 9) is the fully mixed equilibrium of the bi-linear game. Without loss of generality, interested in solving the following problem
min max (S(0) - ())(()) - MR EER
Defining L(0,0) = (f(0)- - ( - q). the dynamics HGD are:
1 Vol
0 Vol (0
(6)
1 - V 2
Φ 4 L
2
Observe that the second term of each right hand side would be zero in a classical bi-linear game but involves second order derivatives of f and g in the case of hidden bi-linear games. To circumvent the complexities of the second order derivatives and mimic the classical bi-linear game we will study modified version of Equation (6) namely:
i =
2 V V
à = = V --VV-- VoL(0. 6)12
Employing an analysis similar to the one in Section 3.2 we get the following convergence result:
Theorem 13. Let (0()), (()) be safe for (p. q). Then ((((t)).g(((t)) converges to (p. q) under the dynamics of Equation
Proof. Simple substitution gives us
Vof V= p)
(g(0) - 9)
Applying Lemma ! and following the same steps as before
f = - [of
(g) (f) pp) ğ = 1ao--VVVeee Veg(X ( Vef(X (f))l 9)
Once again we consider the function
H(f.9) S' (2))11 dz 1" z-9 dz
(2)]
Simple substitution gives
h -- (
-g -60=0
A little bit of reorganization gives
#= -J 1) (2))l12 (o0 s
25

---

Under review as a conference paper at ICLR 2021
Thus, get
H in lm) x Img
Similarly with the strict convex analysis of the previous section, if (f(((0)), = (p, 4) then the theorem holds trivially. Otherwise define
Hg ((F(((0)).(((00)
f = ((.9) E ()H(S.)) S Ho}
where we know that Ho > 0 from Theorem 2 Additionally, we can apply Claim I even in the new dynamics, Ω is in the interior of D. Since H < 0, starting in Ω it implies that (f(), g(t) s Ho for 2 0, so f (t), (t)) stays in Q. Additionally, Ω is closed since it is a sublevel set of a continuous function. Notice that the restriction of f2 on D does not affect the above properties since Ω is in the interior of D. Thus Ω is a compact forward invariant set.
For safe initialization (0(0), (0), both V V (g(())) (of (f(t))) cannot go to as this happens only at the boundaries D which are outside D. So A = 0 only at (p, q) in Q. Therefore, applying Theorem 9
we get that (f(0()), converges to (p,
8.3 REGULARIZATION AND CONVERGENCE
In this section, we show that even in the absence of strict convexity/concavity for both of the operators, it is possible to achieve a positive convergence result by sacrificing the exactness of a targeted equilibrium. In other words, prove that by adding small regularization term, the new utility function becomes strictly convex strictly concave. Beside the guaran- teed convergence of the "perturbed" L', can always choose sufficiently small magnitude of regularization such that the new equílibria are arbitrarily close to the initial ones.
Theorem 6. If a convex concave function with invertible Hessians at all its equilibria, then for each 0 there is X > 0 such that L'' has equilibria that c-close the ones of L.
Proof. For any choice of À 0 we have that L' is strictly convex strictly concave so the KKT conditions are sufficient to determine equilibria.
y + >xx; =
8x.
OL(x,y) Ayys
We can view the above set of constraints single vector constraint r(),x,)) = O. Note that by assumption of the Hessians being invertible all equilibria. L has unique equilibrium xx*x"") Clearly we have that r00, x", ,y") = 0. Observe that for the Jacobian of r at (0, 10,x",00 (0""","") with respect (x, y) we have that
((x,))((,,'',1 .y" = V²L(x",
and thus it is invertible. Invoking the Implicit function Theorem, there is differentiable function g, defined in a small enough neighborhood of O, that takes À and returns g(A) = (x()), such that r(), s(A) O. Thus for a small enough A, we have that g returns the corresponding equilibria of L'. By continuity of for all there is a 8 > 0
v0
8: [Ix(A) x(0) + (Iy(A) 20 <
But (x(0) = (x" .y") the equilbrium of L' has c-close equilibrium of L for À < 8. By strict convexity strict concavity of L', it has a unique equilibrium as well. So the equilibria of i' and T. are e-close each other.
26

---

Under review as a conference paper at ICLR 2021
The previous theorem highlights that small values of induce only small changes to the equilibria of the hidden game. As is the case for classical convex concave games, larger values of lead to (exponentially) faster convergence. To prove this for HCC games, we provide a detailed upper and lower bound analysis of the gradients of f; and 9j-
Theorem 7. Let (0(0), (0)) be a safe initializatiin for the unique equiliirrium of L' (p. q). r(t) = [[)()))) - -p + [G(((t) q/l then there are initialization dependent constants Co. C1 such that r()) S exp((Xxxpp
Proof. Following the same analysis with the strict convex concave analysis of the previous section, if (F()(0)), (0)( (p. q) then the theorem holds trivially. Otherwise, since our initialization is safe for (p, q). we can construct the H function as in Theorem and prove that it has the following property in D {Im,, (0))) {Im,, (Ø, (0)))
f s L' G) L' q) q) L' ('F
2 (1F((())) - [G((())) - qll?)
r()
Where the second step follows from ('P -) being À strongly concave and L' q) being À strongly convex and q. p being the corresponding optima of these functions since (p. q) an equilibrium. Let us define
Ho H(F((())) G()()))
Ω = ((F G) E $
Additionally, we can apply Claim | even in the new dynamics, so Ω is in the interior of D. Since H < 0, starting in Ω, it implies that (F(((t)) G()())) S Hu for 2 O, so (F (t)) stays in Ω. Additionally, 52 is closed since is sublevel set of a continuous function. Notice that the restriction of Ω on D does not affect the above properties since Q is in the interior of D. Thus i compact forward invariant set.
where we know that Ho > 0 from Theorem 2
For safe initialization (0(0), ((0),, the following continuous functions must have a minimum and maximum value on Q respectively.
KG 2 VV (o) (-))12 2 Kg Kg, Z 1V (X (o) (-)) Kig Observe that the minima and maxima must be all greater than zero since both V Øj (Xo, (0) (I(t))) fa (o)))) cannot go to 0 as this happens only at the bound- aries of D which are outside Ω
Let us define
min min fif min Kgz
1555m
K max max Isisn
Kf max Kgy
1535m
Observe that K 2 (X) 2 k in this interval. Thus we can write
(1) p:)3
f.(0.(1))
P-
dz (f)()((t) p2)
(o. Repeating the same argument for all fa and gj we have that
2x
2K
p.
r(t)
> (FF((())) G(o(t))) 2 r(t)
2k
2K
Thus we can extend our analysis
2xA
カ - <
H(t) - (tt < Hoe - Axtt + r(t) 22 K x Hoe Axt Art
2
27

---

Under review as a conference paper at ICLR 2021
9 APPLICATIONS
9.1 CONNECTING GANS AND HIDDEN CONVEX- CONCAVE GAMES
At the heart of many GAN formulations like the standard GAN Goodfellow et al. (2014b), f-GAN
Nowozin et al. ( and Wassertein GAN (WGAN) Arjovsky al. (2017) lies a classical convex concave game in the operator output space. Indeed for the realizeable case Goodfellow et al. (2014b) used the underlying convexity properties to find the Nash equilibria of standard GAN and Farnia & Ozdaglar (2020) did the same thing for the f-GAN and WGAN. Perhaps surprisingly, neither work references explicitly the convex concave nature of the operator output space game von Neumann's minimax theorem. To highlight the significance of von Neumann equilibria as a solution concept for GANs, we show how the optimal G* and D can be derived separately from each other by solving the corresponding min-max (max-min) problems. This allows one to independently verify the validity of von Neumann's 's minimax theorem and its generalizations for GANs. We also extend our analysis to a wide class of non-realizeable cases well.
In practice however, as noted explicitly by Goodfellow (2017). the updates in GAN training happen in the parameter space giving rise to HCC game. This has exactly motivated studying the learning dynamics of HCC games in Section 3
Thus, in this section, we present these connections between Hidden Convex-Concave games and the different architectures of Generative Adversarial Networks. More specifically, we start by exploring the structure of GANs and we verify their hidden convex-concave intrinsic form.
1. Under this scope of hidden games, the strong (or strict) convexity/concavity of at least one of the players (Diserininator(Generaae of the following sections provide some theoretical explanation about the convergence prop- erties of those architectures even under the vanilla Gradient Descent-Ascent Dynamics.
in combination with the convergence results
2. To indicate the relation of Von-Neumann solution with this hidden model, leverage this hidden convex-concave structure in order to compute the well-known both min max and max min optima of GANs under the realizability or not assumption. The results of this section are summarized in the following table:
Type of GAN
G
D
Hidden Structure
GAN
Pdata
2
Linear VS Strongly-Concave
GAN
arg mig (SD PP))
Plats Pesus PP
Linear VS Strongly-Concave
f-GAN
Pdata
f'(1)
Linear VS Concave
f-GAN
arg min (PG)
Plxe Por
Linear VS Concave
WGAN
Pdata
Linear VS Linear
WGAN
arg mingeg EMD EMD(pastall lPG)
Linear VS Linear
Table I: Pduta represents the target data distribution. G is the min-max generator and D" is the max-min discriminator. JSD) denotes the Jensen-Shannon divergence, D, the f-divergence for the convex function f and EMD the earth mover distance and the constant discriminator. xGAN, XGAN correspond to the realizable and the non-realizable case accordingly. indicates the lack of a closed form solution for D* of WGAN.
28

---

Under review as a conference paper at ICLR 2021
In the following three subsections, analyze both the derivation of arg min and arg max min for the "vanilla-GANss, I-GANs, W-GANs using min-max optimization ar- guments based on the Minimax Theorem for convex-concave functions. More precisely,
1. In the Lemmas 4 9 and [4]
present the optimal discriminators which consist the best-response for the case of a fixed generator. In all these maximization prob- lems, typically each (xx) is decoupled and De (z) is derived by the hidden con- cavity of the discriminator architecture.
2. In the Lemmas 5 10 and 15 we present the optimal generators which consist the best-response for the of fixed discriminator. In all these minimization prob- lems, typically the generator can cheat the fixed discriminator by producing greed- ily a distribution only over the restricted subset of the points for which the discrim- inator has the highest confidence about their originality.
3. In the Lemmas 6 II and [6 we leverage lemmas of (Item I to understand the form GAN's utility function which corresponds typically to J f-divergence and Wasserstein distance which donate their name to their GAN architecture as well. Thus, it is then trivial show that Pdata is the optimal choice in the realizable case.
4. In the Lemmas 7 12 and 17 the other side of the coin, emphasize to derive the minmax solutions too. Our proof strategy invokes the partition to two basic sets, Sc, and S6; ,the "preferable" or not data points by the generator. Leveraging the concavity part of the objective, is to label all the points uniformly with the same confidence in order to incentivize the generator to expands its support to the maximum possible.
show that the best strategy for the discriminator
5. In the Lemmas & and 13 using Item 3 we are able to compute the arg max min generator G To conclude about the arg min max discriminators we apply the Von Neumann's 's Minimax the- orem to prove D Best-Response((").
analyze the non-realizable case. One the hand
9.1.1 GAN
The utility of the zero-sum game V(G, D) for the distribution Pdat over the discrete set is - D) Σ Pana (x) (xx)) - Σ log(1-(((())())) JEN
=EN
On the one hand, it is easy to check that for fixed discriminator D, the utility function is linear over the Po operator. On the other hand, for fixed generator G, the utility function is of the form a alog D) + b bogg(1 - D) which is strongly-concave.
We start our work with the following lemmas
Lemma 4 (Goodfellow et al. (014b)). For fixed generator G the optimal discriminator is
Pdaaaa (x)
(=(() Pdato (ddat(x)) + Po(x)
Proof. Observe that the optimization problem for each D(x) is decoupled. Thus
(=(()) = arg max maxpaaaaxx)) (x) log (D) + pa(x) log(1 D) DE(0.1]
By concavity the unique maximum of the above is given by
Pdata
(z(x))
Pdata (x) + pa(x)
Lemma 5. For a fixed discriminator D, any distribution supported only on Sa, E Yxl EN D(x) 2 D(r')}
is an optimal generator when it is allowed to choose any distribution over N.
29

---

Under review as a conference paper at ICLR 2021
Proof. Observe that for fixed discriminator, the optimal generator optimizes
Σ
(a(x))og(( - D(x))
ZEN
since the other term is independent of the generator. Let us define the following
D Duax
max (2x) #EN
Then we have that with the equality being true only for distributions supported only on Say,
Σ po(2) D(x)) 2 log(1 -mmx))
ZEN
Lemma
(Goodfellow al. (2014b)) The min-max generator the following distribution
G arg min JSD( (Pa)-
GEG
Proof. We can substitute in V(G, D) the optimal discriminator from Lemma
Thus we get
Ddata (x)
pG(x)
(GG = Σ
Paita (x)) log
Σ zEN
pa(a)) log
Pdiatal (x) + Pc(
Pdiaa (x) pc(
zEN
We can now prove that
Po + Paata
pGlll Pc Pdata
V(G, D2) = log(4) 1)
KL Pdota
+ KL
2
2
log ()) 2.JSD (Panaal IPa) By minimizing V(G, D2),, the result follows trivially. Lemma 7. The max-min discriminator is
Yz N N=
when the generator is allowed choose any distribution over N.
Proof. We can substitute in V(G, D) the optimal generator from Lemma 5
V(G D) log Dinax)
Σ
Pauaa (x) log(1 D
PG(#)
#ESez
zESe
+
Σ
Pdata ( log D(x)) +
Σ rgSop
(a(
log(1 - D
N Sap
Observe that for Scy, if D takes more than two values then setting D equal to the highest of the them for all x of Soy improves utility. So for optimal discriminator would have single value Dinax > Dmin- In the end we have that
& Sap Scp
(*) D (r) D
Observe that for any combination of Dmax and Dmnn with Dmax Diinx the constant discrimi- nator Dmax has higher utility. Therefore we can focus our attention on the constant discriminator Deons D
V(G Deons)) log D) + log(1 D)
The optimal value for D is and as a result
(x(x) =
30

---

Under review as a conference paper at ICLR 2021
Lemma (Non-reat hoa-realizeblle case). we assume that choice of generator G is restricted in g, convex compact subset of the [ dimensional simplex, such that Pdana & G. Then
(G","") arg min JSD (P (P6)) GEG
Pdata
Pdlaa + PG
Proof. We cannot readily apply von Neumann's minimax theorem since the V(G, D) may be infinite at the boundary points of 'D = (0, 1)W for the discriminator. We can still apply Fan's Minimax Theorem
min sup V(G, D) = sup min V D). DED GEG
GE9 DED
is easy to check that Lemma even in the non-realizable case. As a result, the generator is minimizing (PD (Pa) whose value is finite. Clearly the quantities above finite. Thus there exists a real number v, the value of the game, such that:
VD ED VVGG" D S V(G", D G :VGG, 2 D*) (B)
(4)
for G the minimizer of JSD PG) and D [0, 1IM1 Now applying Lemma we have that
δ = BesttRRespose((")
Pdata
Pdata + PG
Additionally, by the optimality of the response and the consequence (A) of Minimax Theorem it holds that VG D) v. Finally, since V(G*,-) is strongly concave, all other discriminators receive value less than v and are not optimal. Thus
D D
Pouta
Piasa Pp*
9.1.2 F-GAN
The utility of the zero-sum game V(G, D) for the distribution Pdata over the discrete N is
V(G, D) =
Σ Pana (x) TEN
Σ (a(o))
ZEN
We will assume that is strictly convex function with f(1) = 0. On the one hand, it is easy check that for fixed discriminator D, the utility function is linear over the pa operator. On the other hand, for fixed generator G, the utility function is of the form aD (D) which is strictly-coneave.
We start our work with the following lemmas
Lemma Nowozin et al. (0166). For a fixed generator G the optimal discriminator is
D²(x)= (Paaaaaaa [Paota (x)
Proof. Observe that the optimization problem each D(x) is decoupled. Thus
(²(x) arg max Pama (x)) pa(x))"
By concavity the unique maximum of the above is given by Fermat criterion
|Paatu (2r) = -8'( |Dduaa (2) Dz(x) = ((
po(2))
(z)
We note that D", may take the value I for some N if the generator G* does not have full support.
Assigning D(x) = 1 for some may lead to infinite utilities in general. We prove however for that the pair
(G" D") this not the We thus consider that pair cquilibrium.
31

---

Under review as a conference paper at ICLR 2021
Lemma 10. For fixed discriminator D, any distribution supported only
Scp {x EN::: EN ((D())2
an optimal generator when it is allowed to choose any distribution over N.
Proof. Observe that for fixed discriminator, the optimal generator optimizes
Σ po(x))
TEN
since the other term is independent of the generator. Let define the following
F Fmax
max (D((x))
=EN
Then we have that
Σ pp((t) - -F
zEN
with the equality being true only for distributions supported only on Scp
Lemma 11 (Nowozin al. )016)). The min-max generator is the following distribution
G
arg min D (Paaaal PPG).
Geg
Proof. We can substitute in V (GG, D) the optimal discriminator from Lemma
9 Thus we get
V(G, (Z)
Σ Panna()))'
(dana(()
Pditta (xz)
Pr((x))
(5'
Pdata (z) ))
DG
We will first prove that:
VGG, D2) = (P(puallppd
Let's recall firstly the definition of f-divergence:
Pdata (xx
Dy l|PG)
Σ pa(x)) ZEN
PG
Since f is convex and lower semi-continuous, Frenchel convex duality guarantees that we can write terms of conjugate dual as f(u) = supbER { ww - f*(v). Equivalently we get:
{ (Paua(x)) 0 ( PG(x)
(Pdatal (PG)
Σ *EN
pa( sup
veR
Σ sup {pama (x)v - (v)po(z))
.EN
vER
Σ Pdna((x)) #EN
(P
Pddata (x:
)
Σ p=(x)) (f (Plamlo) ) TEN
(z(
po(r))
The last line follows arguments similar to Lemma 9 applied for each term. By minimizing V(G, D2), the result follows trivially.
Lemma 12. The max-min discriminator is
Ya E D'()== f'L)
when the generator is allowed choose any distribution over N.
32

---

Under review as a conference paper at ICLR 2021
Proof. We want to substitute in V(G, D) the optimal generator from Lemma Observe that for all I E SGg, we may not have all ((r) to be equal. Only the values of f are guaranteed to be equal, (D)()) = Fmax. However, there are two distinct D values then we can always pick the higher and improve utility. Thus D Demax be the corresponding value
focus discriminators that constant over Saz Let
V(G D) Draax
Σ #ES;
Priata (x) - Finnn))
Σ pC(#)
DES,
Σ
Pdata (o)(()))0 (x)D(x)-
E pG(x) fr (D(x))
xESop
Observe that for Scg, if D takes more than values then setting D equal the highest of the them for all x $ Say improves utility. So for an optimal discriminator we would have a single value D Fuii with 1 (Drmin)
< ( FDaaa) As result
$ Sa; D*(x)) = Daun E Sc;
D*(x)= D
We now have two cases. For any combination with Druin > Drmax the constant discriminator D(x) Drmn has higher utility. Symmetrically, for any combination with D > Dr the constant discriminator Dxx) = Demax has higher utility. Thus the optimal discriminator is constant.
Plugging in the constant discriminator Deona (I) D we get
V(G Demns) D + (*)
The optimal value for follwoing the approach of Lemma is f'(1) and result
(*) f1)
Lemma 13 (Non-realizable case). Assume that f e C strictly convex and lim 2 exists and is finite If the choice of generator is restricted in G. a convex compact subset of the IW] dimensional simplex, such that Paaa then
(G*,D")= arg min (Pdaull(P))) f PG-
Pdiata
Geg
Proof. We cannot readily apply Neumann's 's minimax theorem since the V(G, D) since D RIAT is not compact for the discriminator. We still apply Fan's Minimax Theorem
min sup V(G, D) sup min D). DED GEG
GEg DED
It is easy to check that Lemma 12 holds even in the non-realizable case. As result, the generator minimizing (P(mulllpec) whose value is finite under the assumptions we made on f. Clearly the quantities above are finite. Thus there exists real number the value of the game, such that:
(VDE ED VVG D) < V(G* D*) (A) VGEG :V(G, 2 = V(G", (B)
for G* the minimizer of ( (PG)) and D* E MR Now applying Lemma we have that
Pdata (I)
δ Best-Response((") f
PG- (x)
Additionally, by the optimality of the response and the consequence (A) of Minimax Theorem holds that V D) v. Finally, assuming that f is strictly convex we get that V(G.-) strictly concave, Best- Restt-Response("" is unique and thus
|Pttta (x) pa (x:
D = pー= -
'This assumption guarantees that the Dy is always finite even if the distribution chosen by the generator is not fully supported on A.. This in turn guarantees that D) is also finite resulting in meaningful equilibrium. Unhounded divergences like KI. are known to be problematic for GANs in practice Arjovsky et al. (017).
33

---

Under review as a conference paper at ICLR 2021
9.1.3 WGAN
The utility of the zero-sum game DG for the distribution Pdata over the discrete metric space (A, dist)
V(G, D) Exxpan [D Ex-pa [X)
Σ (pamn (x) pa (z) where || S
On the one hand, it is easy to check that for fixed discriminator D, the utility function is linear over the po operator. On the other hand, for fixed generator G, the utility function is linear over D.
We start our work with the following lemmas
Lemma 14 (Arjovsky et al. (2017)) For fixed generator G the optimal discriminator is solution of the following linear program
maximize over D()
Σ (p)ano Po(x)) ZEN
subject
D((x) D(x')l S dist(r, x²), Vx, x N
where the optimal value of the LP is the Earth mover's distance between Pdato and pc-
Proof. Indeed, by definition any solution of the above LP is optimal discriminator over fixed generator G. To complete the proof of the statement, we recall that Earth Mover's distance of (Ptata PG) is equal to
min A AECoupling(Pen.eee (xx.xt)=a(dist(( (X, X*)
Now we consider the dual formulation of the Wasserstein distance, then the Kantorovich duality Evans 1997); Villani (2008) implies that the above linear program consists exactly the dual linear program which computes the Earth Mover's distance.
Lemma 15. For a fixed discriminator D, any distribution supported only on
Scy {ir N:: EN D(z) 2 D(x')}
an optimal generator when it is allowed to choose any distribution over N.
Proof. Observe that for fixed discriminator, the optimal generator optimizes
Σ (a(
#EN
since the other term is independent of the generator. Let us define the following
D Duax
max D(x)
JEN
Then we have that with the equality being true only for distributions supported only on Sap-
Er((r) 2 -D
zEN
Lemma (Arjovsky et al. (2017)) The min-max generator is the following distribution
G* arg min EMD(páau PG).
Geg
Proof. We can substitute in (G,, the optimal discriminator from Lemma 14
Thus we get
V(G, EMD (Paaa. Po)
By minimizing V(G, D2), the result follows trivially.
34

---

Under review as a conference paper at ICLR 2021
Lemma 17. The max-min discrininator is
Yz E EN: (x)x)= Constant function
when the generator is allowed choose any distribution over N,
Proof. We can substitute in VVG, the optimal generator from Lemma 5
V( D) =D Dmax max
Σ
Paiata
Dmax
Po(x)
aESaB
xESob
+
Σ
Pdama (aam(>)D(
(x)
E
( ((x)
24Sep
DH S
Observe that for Sc; if D takes more than two values then setting D equal the highest of the them for all x & Soy improves utility, So for an optimal discriminator we would have a single value D > minn- In the end we have that
x & Sop x E So = (x) = Diax
(x) = Dunin
Observe that for any combination of Dmax and Dmin with Dmax Dmins the constant discrimi- nator Dmax has higher utility. Therefore can focus our attention on the constant discriminator D Deons (x) = D, where the optimal value is exactly zero.
V(G Deana)
Finally, it is easy to check that the choice of constant discriminator satisfies trivially the Lipschitz constraints, i.e | Donns(()) - conss (x') = S xist(x,x') for any metric function dist.
9.2 GANS AND HIDDEN CONSTRAINED OPTIMIZATION
In the following section, we will generalize the results of Section 3.2 and Section 3.3 for the case of vanilla GAN of Goodfellow et al. (2014a) whose objective thear-strong-concave where the maximization part is constrained in the distributional simplex. More precisely,
max D) = Σ (daaa() log zEN
Σ pa(x) log(1 - D(x)) zEN
min Po(2)20, ΣTEN Pa(x)=1
DE(O.)) W1
At a first glance, by rewriting the equivalent Langrangian formulation the aforementioned constrained min-max problem we can see that strong-concaviy property does not hold any more. However our following theorem shows that by exploiting further the structure of (Goodfellow et al. (2014a) architecture convergence result is possible.
Theorem 14. Let (Geng, Discs) ) be Goodfellow GAN as described in Section where G, D use sigmoid activations. Then for fully mixed distribution Pdtto (F Genou)) (t) -isca(o)
converges to (pdats 1 l ww as L > do under the dynamics of Equation
Proof. Let write down our original objective
min max Po(m) DE(0.1) wi D) = Σ EIEN (o(===1
Paaaa lo) (ox()())))=
Σ pa(x) log(1 - D(x)) zEN
ZEN
In order to remove the constraints from the objective above, we plan to make use of Lagrange multiplier. We remind the reader that since both the discriminator and the generator use the sig- moid activations, we only have to capture the ΣLEN (2 = constraint. Thus, our equivalent Langragian is:
min max L(F, G, A) = Pdata log (()) F(0) log(1 G(d)) + x(F 1 - 1)
BERINI MERINI
35

---

Under review as a conference paper at ICLR 2021
where
F [fi(01) f2(
fi (9 [
(
92(02) [1((1
and Si and Sj are sigmoid functions and 0; and Φy are their one dimensional inputs. Let's write again
the equivalent dynamics of Equation (3) for the sigmoid activations and the Langrage multiplier.
Applying the same steps with Theorem for sigmoids:
f =
OL f fi)
(F.G)
Vi [W]]
05:
9j
B2 Bas
(F, G)
Vj [W]
X
Σ
Since all initializations are safe in this game, our "generalized" Lyapunov function:
H(F.G, G, 1= (2.)
Σ
W
Pdlaaa (x:) =2 2)2
dz
+
W
1/2 22 2)2 dz + (A (A-1-)²
95 2 1-1
2
1=0
where X is the Langrange multiplier at the equilibrium the non-hidden game and o; is the i-th
element of N. Applying the same steps in Lemma 3 get that GDA approaches the largest invariant set E of points (F, G, A) that have the following properties
((Patta G, =
Pdata 11 X"
L { 1. P A4
1
For the first equality, we have that the value À does not affect when the generator respects the sum constraint. Thus
L(Paata G, A) L(Paatn G,
Then we can observe that L(Pdata, minimum we have that
G, ) strictly concave G and given that 1 1ww1 is its unique
1 [PPataa G, G, = Pdita 2 (w111a)
= - 1
Given that E is an invariant set and G is constant in F, we have that G 0. In other words,
aL
F. 2 (
0 =
Vj E [W]]
2
2
0g;
As consequence we have that
ØL
F
=0 J3 Pastaa (xy))
Vj E [[]]]
0gj
Once again, given that E is an invariant set and F is constant in E, we have that F = 0
OL āʃ:
0 = Pdataa (x:)) (1 Pdata (x:))²
Pdata 111)
Vi [[]]]
This leads to
aL 0f
Paam 2 [ =0 x = log 2
Vi E [[V]]
Observe that by the optimality conditions of the non-hidden game, X needs to satisfy the same equation and thus \ = X*. Clearly have that
(F,G,)) = (F,G.A) Pdatu: (
Thus the dynamics converge to the unique equilibrium of the hidden game.
36

---

Under review as a conference paper at ICLR 2021
9.3 ZERO-SUE SUM GAMES
We close this section with an application of our regularization machinery in hidden bilinear games. Hidden bilinear zero-sum games were introduced by MataaissCGkaragkuuni al. (2019) and they are formally defined as:
Definition 11 (Hidden Bilinear Zero-Sum Game), a hidden bilinear zero-sum game there are
two players, each equipped with smooth function F R" - R. and G R + RM and payoff matrix UNx such that each player inputs its own decision vector 0 E IR" and & E I and trying to maximize minimize r(0. Φ)) F(O) (G) respectively.
For the special case of hidden bilinear games, Wlatakis-Gkaragaee the dimension of the game greater or equal than two like (c.g. akin to Sock-Paper-Scissory then GDA dynamics tend to "cycle" through their parameter space with even more complex behavior than a typical periodic trajectory. Specifically, the system is formally analogous to Poincaré recurrent systems (e.g. many body problem in physies). In contrast, leveraging Theorem (6] know that by adding small regularization term we can "break" the cycling behavior and converge approximate Nash Equilibrium. We close this section by presenting comparison between the optimization portraits GDA dynamics with the absence or not of a regularization for the archetypical game of Kock-Paper-Scissors
et al. (2019) proved that if
Figure 5: Trajectories of single player using gradient-descent-asee dynamics for hidden bilin- ear game ((), G()) = F (0) AG()) where A is the classical Pack-Paper-Scissors table and F, G have the sigmoid activations. The two left figures present the Poincaré recurrence for different initializations of the dynamics, a behavior consistent with the Lyapunov stability of Theorem) 2 On the other hand, the two figures on the right illustrate convergent to the mixed Nash equilibrium exe- cutions which exploit the regularization tools as described in Section 3.3 The regularization terms added are centered at the mixed equilbrium of the game, leading convergence the unmodified equilibrium of the Pock-Paper-Scissoon game.
37


Reviews:
[{"review_id": "uDmFioIsY_G", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nWith the aim of improving our understanding of GAN training, the paper studies the behavior of gradient descent ascent (GDA) dynamics in a subclass of the so-called _hidden convex-concave games_. In this family of problems, the players control the input variables of smooth functions whose outputs are taken as inputs of a convex-concave game. \nFor the problems covered by this paper, different types of stability around nash equilibria of the hidden game are proved under different assumptions. In particular, the concept of _safe_ initializations is introduced, which clearly distinguishes between the case where the trajectory can and cannot converge to a hidden game solution. As an example, the authors prove that when the hidden game is strictly convex-concave, with safe initialization GDA dynamics converge to a point that solves the hidden minimax game.\n\n### Pros\n\nThis paper can have an impact on the analysis of GAN optimization by examining a different line of attack on the problem. \nThe analysis and the presentation are clean and the appendix is extremely well-organized. \nThe importance of the initialization is further highlighted by the concept of safety, reflecting the additional complexity caused by the nonlinear transformation. \nOverall, this paper presents some beautiful results for the problem under study, and provide concise explanations on how these results are obtained.\n\n### Cons / Limitations of the paper\n\nThere are however several important limitations of the work which make it difficult to evaluate the significance of the results.\n\n#### Slight overclaim on the problems covered by the paper\nUp to page 2, one may believe that the paper addresses the general hidden convex-concave game as defined by (HCC). Then, on page 3, it turns out actually the paper only focuses on a special type of HCC for which every coordinate of the function output is independently determined by its input variables. This seems to be rather restricted and it is unclear how the results of the paper can be applied to general HCC. Moreover, this limitation is mentioned nowhere in the abstract or the introduction of the paper.\n\n#### Ambiguities in how GANs fit the framework\nWhile the authors claim that GAN training is a specific case of HCC, it is not straightforward from the text that this in fact indicates either of the following\n1. The probability distribution has finite discrete support.\n2. The discriminator outputs a function and the generator outputs a measure.\n\nThe paper (and Section 9 in particular) centers on case 1 which is quite far from real GAN problems, and this message is not so clear in the paper (with only the keyword \"discrete\" mentioned discreetly). On the other hand, for the second case, we need to study minimax games in a Banach space which is not covered by the paper.\n\n#### The potential of the approach is unclear\n\nFinally, in addition to the above two limitations which weaken the link between the problems studied by the paper and real GAN training, the discretization from continuous ODE to practical algorithms is also non-trivial. The study of the dynamics itself is surely of interest. Nonetheless, taking all these into account, I am just wondering if it would really be possible/suitable to study GAN optimization through the lens of hidden convex-concave games.\n\n### Score justification\n\nI appreciate the efforts that the authors have made to come out with all the results and to present them in such a succinct manner. I however do not put a higher score due to the concerns that I raised above.", "extra_scores": {}, "extra_text": {}}, {"review_id": "cFWDSonGCcX", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies min-max problems of the form L(F(x),G(y)), where L is a strictly convex-concave loss. The authors prove that, under certain assumptions, the GDA dynamics converges to von Neumann solutions. Toy examples are provided to illustrate the usage of the framework.\n\nI see this paper as a rather incremental extension of the work (Vlatakis-Gkaragkounis et al. 2019). Specifically, Lemma 1 appeared in (Lemma 1, Vlatakis-Gkaragkounis et al. 2019), Theorem 1 appeared in (Lemma 2, Vlatakis-Gkaragkounis et al. 2019), Definition 3 makes a strong assumption that basically gets rid of the challenges of non-convexity, and Lemma 2 appeared in (Theorem 2, Vlatakis-Gkaragkounis et al. 2019).\n\nThe key difference between this work and (Vlatakis-Gkaragkounis et al. 2019) is the strict convex-concave losses (present work) vs. bilinear losses (Vlatakis-Gkaragkounis et al. 2019). Due to this difference, the function (4) in Lemma 2 is time-invariant (or acts as a Hamiltonian) in (Vlatakis-Gkaragkounis et al. 2019), whereas in this submission it is non-increasing in the presence of strict convexity, and hence enabling Lyapunov-type analysis. This is an almost immediate conclusion one can draw from studying (Vlatakis-Gkaragkounis et al. 2019), and hence the contribution does not seem to meet the standard of top ML venues.\n\nIn addition, the authors studied unconstrained min-max problems with hidden structures, while in Section 4 they claimed that GANs can be viewed as **constrained** min-max problems. I would like to point out that the presence of constraints is a significant difference as it would completely invalidate all the analysis in this paper. The toy example of WGAN is also not convincing enough as it is tied to one dimensionality with a (practically irrelevant) quadratic regularizer.\n\nIn conclusion, I did not see much novelty of this submission in terms of theory, and there is no practical implication. I hence suggest rejection for the Area Chair.", "extra_scores": {}, "extra_text": {}}, {"review_id": "MQEFB2F0BHU", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nWhile single-agent optimization is quite well understood and even convergence results in the nonconvex setting, the study of non-convex-concave saddle point problems is still in its infancy. In particular, recent work by Letcher (2020) and Hsieh et al (2020) suggests that even many recently proposed modifications of simultaneous gradient descent are not guaranteed to converge in the non-convex-concave case.\nThe present work makes significant progress on this problem by introducing hidden convex-concavity, a class of structured problems nonlinear functions $F(\\theta)$ and $G(\\phi)$ that depend on only one of the agents $\\theta$ and $\\phi$, are plugged into a convex-concave problem $L(\\cdot, \\cdot)$, resulting in $\\min_{\\theta} \\max_{\\phi} L(F(\\theta), G(\\phi))$.\nHere, the components $F_i$ and $G_j$ of $F$ and $G$ are multivariate, real-valued functions $f_i$, $g_i$ of disjoint sets of components of $\\theta$ and $\\phi$.\nBy cleverly relating the dynamics of the $f_i$,$g_i$ to those of the $\\theta_j$, $\\phi_j$, the authors derive a Lyapunov function for the underlying dynamics and use it to prove asymptotic stability and convergence under very minor additional assumptions.\nThey furthermore show a notion of \"hidden convergence\" of the $f_i$, $g_i$ that is particularly relevant to the overparametrized regime. \nIn the last section, the authors relate their findings to GANs.\n\nDecision:\nI believe that this is good work that will be interesting to a wide range of readers. My only concern is the following:\n\nIn the definition of hidden convex-concavity, the functions $f_i, g_j$ are multivariate and real valued, but depend on **disjoint** sets of parameters. In particular, it does not seem to cover the case of  $L(f(\\phi), g(\\theta))$ where $f$ and $g$ are multivariate vector valued functions. \nHowever, this is arguably the case in GANs, where the discriminator and generator can be thought of high/infinite-dimensional \"vectors\" that depend nonlinearly on all parameters. \nTherefore, the results of the authors do not seem to apply to GANs even formally? Please let me know if there is something that I overlooked.\n\nI believe that the results are interesting and relevant even if they would not apply to GANs. However, in this case the application section and motivation of the paper might need some restructuring.\n\nOther suggestions/questions to authors\n- I would suggest citing https://arxiv.org/abs/2005.12649 and https://arxiv.org/abs/2006.09065 as they provide additional motivation for the necessity to consider more structured classes of nonconvex games. \n- A popular extension beyond convexity is pseudo-monotonicity (see for instance https://arxiv.org/abs/1807.02629). How does strict hidden convexity relate to strict pseudo-monotonicity? Does the former imply the latter? Are there counterexamples?\n- Do the authors expect that methods that converge in the bilinear case such as extragradient, symplectic gradient adjustment, or competitive gradient descent can be guaranteed to converge even for weak hidden convexity?\n\nminor comments: \n- Statement of Lemma 1: I think the statement would be more clear if \\Sigma_1 and \\Sigma_2 were defined before the conclusion.\n- Theorem 2: \"is a safe\" -> \"is safe\" \n- \"Hidden convex-concave games & Regularizaiton\" -> \"...Regularization\"\n\n=============================================================================================================\nAfter author discussion: After discussion with the authors, I am now convinced that any applicability of the theory proposed in this work to GANs is fundamentally tied to univariate latent space or generator output since the \"hidden convexity assumption\" does not allow for a multivariate set of latent variables to be combined to a multivariate set of outputs.\nI still find the theoretical findings and method interesting, but I think that the work requires substantial refocusing and the identification of more examples of \"hidden strong convexity\" before being published at a top-tier conference. I therefore change my rating from 7 to 5 and recommend rejection, for now.", "extra_scores": {}, "extra_text": {}}, {"review_id": "EvdW-pqg8_", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\n\nWhile the paper has merits, it fails in my opinion to clearly explain its theoretical grounds and findings to a non-specialist of continuous dynamics (like me). I thus cannot recommend acceptance for this version based on my comprehension.\n\n\n* The authors consider the gradient descent/ascent as a standard optimization dynamics. However, in min-max optimization (and even in practical GAN training see e.g. \"Reducing Noise in GAN Training with Variance Reduced Extragradient\" by Tatjana Chavdarova, Gauthier Gidel, François Fleuret, Simon Lacoste-Julien), extragradient techniques are actually more often used that gradient descent-ascent due to they better theoretical properties (see the first paragraph of the introduction). Notably, EG can converge to a saddle point in bilinear games where gradient fails (see Chavdarova et al. above or Hsieh et al. 2020) even though they globally come from the same continuous-time dynamics. Thus, it is natural to wonder why/if the continuous-time gradient dynamics bears valuable information about the saddle-point problem and associated behaviors. I would like to see the authors address this in the introduction.\n\n* The paragraph \"Our class of games\" and \"Our solution concept\" quite verbose and hard to understand (maybe adding in equations the definitions of Nash Eq. and Von Neumann solutions would help). Since a goal of the paper is to provide intuition on the dynamics of certain games with respect to certain solution, these should be made very clear for the reader, this is not the case at the moment.\n\n* I am concerned with the definition of \"safe initialization\" (Def 3) and notably how it can be checked (which is unfortunately not discussed). Typically, most results assume a safe initialization which looks like a local basin of attraction. This kind of contradicts the statement that the results are \"non-local\" in the abstract.\n\n* Concerning the difference between the considered setup and previous ones: i) Apart from the \"reparametrization\" of Section 2.3, what changes between this setup and the convex-concave saddle point gradient dynamics?  ii) and Compared to hidden bilinear games?\n\n* The authors claim in the conclusion that the \"modular structure\" of their proofs make HCC games suitable \"theoretical testbeds\". However, it is a bit hard while reading the paper to pinpoint the mathematical tools that can actually be used for further studies. While looking at the 23 pages appendix, I feel that Eq. (1) -- the dynamics; Theorem 1 -- the reparametrization; and Lemma 2 -- derivation of the non-increasing potential, are the most important results (or rather their instantiation for GDA dynamics). In th present version, they are a bit lost in the very long appendix. Maybe dropping down the general case and the regularization parts would enable to better present these points in the paper.\n\n\nMinor Comments:\n* In the first paragraph of the introduction, the authors cite 16 references at once. I am not sure that this is actually informative. Either the authors could break down these refs into smaller chunks/units that relate to one particular kind of results (as id done in the second paragraph) or drastically reduce the number of papers cited there.\n* The term \"hidden convexity\" may be a bit confusing since it may refer to e.g. local strong convexity around the solution. In the literature, the term convex composite problem is sometimes used to denote minimization problems of the form \\min_x h(c(x)) with h a convex function and c a smooth mappings (see e.g. \"Efficiency of minimizing compositions of convex functions and smooth maps\" by Drusvyatskiy and Paquette), this may be mentioned as well.\n* In Lemma 2 and Theorem 2, \"is a safe for\" probably misses the word \"initialization\".\n* In Theorem 2, the sense of \"stable\" here should be defined.\n* Lemma 3: \"is the non-empy\" should be \"be the non-empty\".\n* bottom of p7: \"regularization\" is spelled wrong, \"it can posed\" -> \"be posed\"\n* In Figure 3, how is the continuous dynamics discretized?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the convergence of gradient descent ascent (GDA) dynamics in a specific class of non-convex non-concave zero-sum games that the authors call "hidden zero-sum games". Unlike general min-max games, these games have a well-defined notion of a "von Neumann solution". The authors show that if the hidden game is strictly convex-concave then vanilla GDA converges not merely to local Nash, but typically to this von Neumann solution.

The paper received four high quality reviews and was discussed extensively during the author rebuttal phase. From an application angle, the authors' replies did not convince the reviewers on the relevance of this paper to GANs, and one of the original "accept" recommendations was downgraded to a "reject" because of this. On the theory side, the novelty over Vlatakis-Gkaragkounis et al. (2019) is not clear and the reviewers found the writing often confusing or hard to connect with practice. The reviewer with the most positive recommendation did not champion the paper post-rebuttal. In the end, the consensus was that the work shows significant promise, but it requires refocusing before appearing at a top-tier conference.
Decision: Reject