Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games

Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Georgios Piliouras

Introduction

This problem is much more complicated compared to classical minimization problems, as even understanding under which conditions such a solution is meaning-full is far from trivial Daskalakis and Panageas (2018); Mai et al. (2017); Oliehoek et al. (2018); Jin et al. (2019). What is even more demanding is understanding what kind of algorithms/dynamics are able to solve this problem when a solution is well defined.

Recently this problem has attracted renewed interest motivated by the advent of Generative Adversarial Networks (GANs) and their numerous applications Goodfellow et al. (2014); Radford et al. (2016); Isola et al. (2017); Goodfellow et al. (2014); Zhang et al. (2017); Arjovsky et al. (2017); Ledig et al. (2017); Salimans et al. (2016). A classical GAN architecture mainly revolves around the competition between two players, the generator and the discriminator. On the one hand, the generator aims to train a neural network based generative model that can generate high fidelity samples from a target distribution. On the other hand, the discriminator’s goal is to train a neural network classifier than can distinguish between the samples of the target distribution and artificially generated samples. While one could consider each of the tasks in isolation, it is the competitive interaction between the generator and the discriminator that has lead to the resounding success of GANs. It is the "criticism" from a powerful discriminator that pushes the generator to capture the target distribution more accurately and it is the access to high fidelity artificial samples from a good generator that gives rise to better discriminators. Machine Learning researchers and practitioners have tried to formalize this competition using the min-max optimization framework mentioned above with great success Arora et al. (2017); Ma (2018); Ge et al. (2018); Yazıcı et al. (2019).

One of the main limitations of this framework however is that to this day efficiently training GANs can be a notoriously difficult task Salimans et al. (2016); Metz et al. (2017); Mertikopoulos et al. (2018); Kodali et al. (2017). Addressing this limitation has been the object of interest for a long line work in the recent years Mescheder et al. (2018); Metz et al. (2017); Pfau and Vinyals (2016); Radford et al. (2016); Tolstikhin et al. (2017); Berthelot et al. (2017); Gulrajani et al. (2017). Despite the intensified study, very little is known about efficiently solving general min-max optimization problems. Even for the relatively simple case of bilinear games, the little results that are known have usually a negative flavour. For example, the continuous time analogue of standard game dynamics such as gradient-descent-ascent or multiplicative weights lead to cyclic or recurrent behavior Piliouras and Shamma (2014); Mertikopoulos et al. (2018) whereas when they are actually run in discrete-timeInterestingly, running alternating gradient-descent-ascent in discrete-time results once again in recurrent behavior Bailey et al. (2019). they lead to divergence and chaos Bailey and Piliouras (2018); Cheung and Piliouras (2019); Bailey and Piliouras (2019b). While positive results for the case of bilinear games exist, like extra-gradient (optimistic) training (Daskalakis et al. (2018); Mertikopoulos et al. (2019a); Daskalakis and Panageas (2019)) and other techniques Balduzzi et al. (2018); Gidel et al. (2019b, a); Abernethy et al. (2019), these results fail to generalize to complex non-convex non-concave settings Oliehoek et al. (2018); Lin et al. (2018); Sanjabi et al. (2018). In fact, for the case of non-convex-concave optimization, game theoretic interpretations of equilibria might not even be meaningful Mazumdar and Ratliff (2018); Jin et al. (2019); Adolphs et al. (2019).

We call the resulting class of problems Hidden Bilinear Games.

The motivation behind the proposed class of gamess is actually the setting of training GANs itself. During the training process of GANs, the discriminator and the generator "submit" the parameters of their corresponding neural network architectures, denoted as $\boldsymbol{\theta}$ and $\boldsymbol{\phi}$ in our problem formulation. However, deep networks introduce nonlinearities in mapping their parameters to their output space which we capture through the non-convex functions $F,G$ . Thus, even though hidden bilinear games do not demonstrate the full complexity of modern GAN architectures and training, they manage to capture two of its most pervasive properties: i) the indirect competition of the generator and the discriminator and ii) the non-convex non-concave nature of training GANs. Both features are markedly missing from simple bilinear games.

Our results. We provide, the first to our own knowledge, global analysis of gradient-descent-ascent for a class of non-convex non-concave zero-sum games that by design includes both features of bilinear zero-sum games as well as of single-agent non-convex optimization. Our analysis focuses on the (smoother) continuous time dynamics (Section 4,5) but we also discuss the implications for discrete time (Section 7). The unified thread of our results is that gradient-descent-ascent can exhibit a variety of behaviors antithetical to convergence to the min-max solution. In fact, convergence to a set of parameters that implement the desired min-max solution (as e.g. GANs require), if it actually happens, is more of an accident due to fortuitous system initialization rather than an implication of the adversarial network architecture.

Informally, we prove that these dynamics exhibit conservation laws, akin to energy conservation in physics. Thus, in contrast to them making progress over time their natural tendencies is to "cycle" through their parameter space. If the hidden bilinear game $U$ is 2x2 (e.g. Matching Pennies) with an interior Nash equilibrium, then the behavior is typically periodic (Theorem 3). If it is a higher dimensional game (e.g. akin to Rock-Paper-Scissors) then even more complex behavior is possible. Specifically, the system is formally analogous to Poincaré recurrent systems (e.g. many body problem in physics) (Theorems 6, 7). Due to the non-convexity of the operators $F,G$ , the system can actually sometimes get stuck at equilibria, however, these fixed points may be merely artifacts of the nonlinearities of $F,G$ instead of meaningful solutions to the underline minmax problem $U$ . (Theorem 8).

In Section 7, we show that moving from continuous to discrete time, only enhances the disequilibrium properties of the dynamics. Specifically, instead of energy conservation now energy increases over time leading away from equilibrium (Theorem 9), whilst spurious (non-minmax) equilibria are still an issue (Theorem 10). Despite these negative results, there are some positive news, as at least in some cases we can show that time-averaging over these non-equilibrium trajectories (or equivalently choosing a distribution of parameters instead of a single set of parameters) can recover the min-max equilibrium (Theorem 4). Technically our results combine tools from dynamical systems (e.g. Poincaré recurrence theorem, Poincaré-Bendixson theorem, Liouville’s theorem) along with tools from game theory and non-convex optimization.

Understanding the intricacies of GAN training requires broadening our vocabulary and horizons in terms of what type of long term behaviors are possible and developing new techniques that can hopefully counter them.

The structure of the rest of the paper is as follows. In Section 2 we will present key results from prior work on the problem of min-max optimization. In Section 3 we will present the main mathematical tools for our analysis. Sections 4 through 6 will be devoted to studying interesting special cases of hidden bilinear games. Section 8 will be the conclusion of our work.

Related Work

Non-equilibrating dynamics in game theory. Kleinberg et al. (2011) established non-convergence for a continuous-time variant of Multiplicative Weights Update (MWU), known as the replicator dynamic, for a 2x2x2 game and showed that as a result the system converges to states whose social welfare dominates that of all Nash equilibria. Palaiopanos et al. (2017) proved the existence of Li-Yorke chaos in MWU dynamics of 2x2 potential games. From the perspective of evolutionary game theory, which typically studies continuous time dynamics, numerous nonconvergence results are known but again typically for small games, e.g., Sandholm (2010). Piliouras and Shamma (2014) shows that replicator dynamics exhibit a specific type of near periodic behavior in bilinear (network) zero-sum games, which is known as Poincaré recurrence. Recently, Mertikopoulos et al. (2018) generalized these results to more general continuous time variants of FTRL dynamics (e.g. gradient-descent-ascent). Cycles arise also in evolutionary team competition Piliouras and Schulman (2018) as well as in network competition Nagarajan et al. (2018). Technically, Piliouras and Schulman (2018) is the closest paper to our own as it studies evolutionary competition between Boolean functions, however, the dynamics in the two models are different and that paper is strictly focused on periodic systems. The papers in the category of cyclic/recurrent dynamics combine delicate arguments such as volume preservation and the existence of constants of motions (“energy preservation"). In this paper we provide a wide generalization of these type of results by establishing cycles and recurrence type of behavior for a large class of non-convex non-concave games. In the case of discrete time dynamics, such as standard gradient-descent-ascent, the system trajectories are first order approximations of the above motion and these conservation arguments do not hold exactly. Instead, even in bilinear games, the “energy" slowly increases over time Bailey and Piliouras (2018) implying chaotic divergence away from equilibrium Cheung and Piliouras (2019). We extend such energy increase results to non-linear settings.

Learning in zero-sum games and connections to GANs. Several recent papers have shown positive results about convergence to equilibria in (mostly bilinear) zero-sum games for suitable adapted variants of first-order methods and then apply these techniques to Generative Adversarial Networks (GANs) showing improved performance (e.g. Daskalakis et al. (2018); Daskalakis and Panageas (2019)). Balduzzi et al. (2018) made use of conservation laws of learning dynamics in zero-sum games (e.g. Bailey and Piliouras (2019a)) to develop new algorithms for training GANs that add a new component to the vector field that aims at minimizing this energy function. Different energy shrinking techniques for convergence in GANs (non-convex saddle point problems) exploit connections to variational inequalities and employ mirror descent techniques with an extra gradient step Gidel et al. (2018); Mertikopoulos et al. (2019a). Moreover, adding negative momentum can help with stability in zero-sum games Gidel et al. (2019c). Game theoretic inspired methods such as time-averaging work well in practice for a wide range of architectures Yazıcı et al. (2019).

Preliminaries

2 Definitions

In this work we will mostly study continuous time dynamics of solutions for the problem of Equation 1 for hidden bilinear zero-sum games but we will also make some important connections to discrete time dynamics that are also prevalent in practice. In order to make this distinction clear, let us define the following terms.

We will call $f$ the vector field of the dynamical system. In order to understand the properties of continuous time dynamical systems, we will often need to study their behaviour given different initial conditions. This behaviour is captured by the flow of the dynamical system. More precisely,

In this work we will be mainly study the gradient-descent-ascent dynamics for the problem of Equation 1. The continuous (discrete) time version of the dynamics (with learning rate $\alpha$ ) are based on the following equations:

A key notion in our analysis is that of (Poincaré) recurrence. Intuitively, a dynamical system is recurrent if, after a sufficiently long (but finite) time, almost every state returns arbitrarily close to the system’s initial state.

Cycles in hidden bilinear games with two strategies

Let us assume that the hidden bi-linear game has a unique mixed Nash equilibrium $(p,q)$ :

Then we can write down the equations of gradient-descent-ascent : $\begin{Bmatrix}\begin{aligned} \dot{\boldsymbol{\theta}}&=-v\nabla f(\boldsymbol{\theta})(g(\boldsymbol{\phi})-q)\\ \dot{\boldsymbol{\phi}}&=v\nabla g(\boldsymbol{\phi})(f(\boldsymbol{\theta})-p)\end{aligned}\end{Bmatrix}~{}(3)$

In order to analyze the behavior of this system, we would like to understand the topology of the trajectories of $\boldsymbol{\theta}$ and $\boldsymbol{\phi}$ , at least individually. The following lemma makes a connection between the trajectories of each variable in the min-max optimization system of Equation 4 and simple gradient ascent dynamics.

By applying the previous result for $\boldsymbol{\theta}$ with $k=f$ and $h(t)=-v(g(\boldsymbol{\phi}(t))-q)$ , we get that even under the dynamics of Equation 4, $\boldsymbol{\theta}$ remains on a trajectory of the simple gradient ascent dynamics with initial condition $\boldsymbol{\theta}(0)$ . This necessarily affects the possible values of $f$ and $g$ given the initial conditions. Let us define the sets of values attainable for each initialization.

For each $\boldsymbol{\theta}(0)$ , $f_{\boldsymbol{\theta}(0)}$ is the set of possible values of $f(\boldsymbol{\theta}(t))$ can attain under gradient ascent dynamics. Similarly, we define $g_{\boldsymbol{\phi}(0)}$ the corresponding set for $g$ .

What is special about the trajectories of gradient ascent is that along this curve $f$ is strictly increasing (For a detailed explanation, reader could check the proof of Theorem 1 in the Appendix) and therefore each point $\boldsymbol{\theta}(t)$ in the trajectory has a unique value for $f$ . Therefore even in the system of Equation 4, $f(\boldsymbol{\theta}(t))$ uniquely identifies $\boldsymbol{\theta}(t)$ . This can be formalized in the next theorem.

Equipped with these results, we are able to reduce this complicated dynamical system of $\boldsymbol{\theta}$ and $\boldsymbol{\phi}$ to a planar dynamical system involving $f$ and $g$ alone.

If $\boldsymbol{\theta}(t)$ and $\boldsymbol{\phi}(t)$ are solutions to Equation 4 with initial conditions $(\boldsymbol{\theta}(0),\boldsymbol{\phi}(0))$ , then we have that $f(t)=f(\boldsymbol{\theta}(t))$ and $g(t)=g(\boldsymbol{\phi}(t))$ satisfy the following equations

As one can observe both form Equation 4 and Equation 4, fixed points of the gradient-descent-ascent dynamics correspond to either solutions of $f(\boldsymbol{\theta})=p$ and $g(\boldsymbol{\phi})=q$ or stationary points of $f$ and $g$ or even some combinations of the aforementioned conditions. Although, all of them are fixed points of the dynamical system, only the former equilibria are game theoretically meaningful. We will therefore define a subset of initial conditions for Equation 4 such that convergence to game theoretically meaningful fixed points may actually be feasible:

We will call the initialization $(\boldsymbol{\theta}(0),\boldsymbol{\phi}(0))$ safe for Equation 4 if $\boldsymbol{\theta}(0)$ and $\boldsymbol{\phi}(0)$ are not stationary points of $f$ and $g$ respectively and $p\in f_{\boldsymbol{\theta}(0)}$ and $q\in g_{\boldsymbol{\phi}(0)}$ .

For safe initial conditions we can show that gradient-descent-ascent dynamics applied in the class of the hidden bilinear zero-sum game mimic properties and behaviors of conservative/Hamiltonian physical systems Bailey and Piliouras (2019a), like an ideal pendulum or an ideal spring-mass system. In such systems, there is a notion of energy that remains constant over time and hence the system trajectories lie on level sets of these functions. To motivate further this intuition, it is easy to check that for the simplified case where $\lVert\nabla{f}\rVert=\lVert\nabla{g}\rVert=1$ the level sets correspond to cycles centered at the Nash equilibrium and the system as a whole captures gradient-descent-ascent for a bilinear $2\times 2$ zero-sum game (e.g. Matching Pennies).

Let $\boldsymbol{\theta}(0)$ and $\boldsymbol{\phi}(0)$ be safe initial conditions. Then for the system of Equation 4, the following quantity is time-invariant

The existence of this invariant immediately guarantees that Nash Equilibrium $(p,q)$ cannot be reached if the dynamical system is not initialized there. Taking advantage of the planarity of the induced system - a necessary condition of Poincaré-Bendixson Theorem - we can prove that:

Let $\boldsymbol{\theta}(0)$ and $\boldsymbol{\phi}(0)$ be safe initial conditions. Then for the system of Equation 4, the orbit $(\boldsymbol{\theta}(t),\boldsymbol{\phi}(t))$ is periodic.

On a positive note, we can prove that the time averages of $f$ and $g$ as well as the time averages of expected utilities of both players converge to their Nash equilibrium values.

Let $\boldsymbol{\theta}(0)$ and $\boldsymbol{\phi}(0)$ be safe initial conditions and $(\boldsymbol{P},\boldsymbol{Q})=\Big{(}\binom{p}{1-p},\binom{q}{1-q}\Big{)}$ , then for the system of Equation 4

Poincaré recurrence in hidden bilinear games with more strategies

In this section we will extend our results by allowing both the generator and the discriminator to play hidden bilinear games with more than two strategies. We will specifically study the case of hidden bilinear games where each coordinate of the vector valued functions $F$ and $G$ is controlled by disjoint subsets of the variables $\boldsymbol{\theta}$ and $\boldsymbol{\phi}$ , i.e.

where each function $f_{i}$ and $g_{i}$ takes an appropriately sized vector and returns a non-negative number. To account for possible constraints (e.g. that probabilities of each distribution must sum to one), we will incorporate this restriction using Lagrange Multipliers. The resulting problem becomes

Writing down the equations of gradient-ascent-descent we get

Once again we can show that along the trajectories of the system of Equation LABEL:eq:eq_gda_multi, $\boldsymbol{\theta}_{i}$ can be uniquely identified by $f_{i}(\boldsymbol{\theta}_{i})$ given $\boldsymbol{\theta}_{i}(0)$ and the same holds for the discriminator. This allows us to construct functions $X_{\boldsymbol{\theta}_{i}(0)}$ and $X_{\boldsymbol{\phi}_{j}(0)}$ just like in Theorem 1. We can now write down a dynamical system involving only $f_{i}$ and $g_{j}$ .

If $\boldsymbol{\theta}(t)$ and $\boldsymbol{\phi}(t)$ are solutions to Equation LABEL:eq:eq_gda_multi with initial conditions $(\boldsymbol{\theta}(0),\boldsymbol{\phi}(0),\lambda(0),\mu(0))$ , then we have that $f_{i}(t)=f_{i}(\boldsymbol{\theta}_{i}(t))$ and $g_{j}(t)=g_{j}(\boldsymbol{\phi}_{j}(t))$ satisfy the following equations

Similarly to the previous section, we can define a notion of safety for Equation LABEL:eq:eq_gda_multi. Let us assume that the hidden Game has a fully mixed Nash equilibrium $(\boldsymbol{p},\boldsymbol{q})$ . Then we can define

We will call the initialization $(\boldsymbol{\theta}(0),\boldsymbol{\phi}(0),\lambda(0),\mu(0))$ safe for Equation LABEL:eq:eq_gda_multi if $\boldsymbol{\theta}_{i}(0)$ and $\boldsymbol{\phi}_{j}(0)$ are not stationary points of $f_{i}$ and $g_{j}$ respectively and $p_{i}\in f_{i_{\boldsymbol{\theta}_{i}(0)}}$ and $q_{j}\in g_{j_{\boldsymbol{\phi}_{j}(0)}}$ .

Assume that $(\boldsymbol{\theta}(0),\boldsymbol{\phi}(0),\lambda(0),\mu(0))$ is a safe initialization. Then there exist $\lambda_{*}$ and $\mu_{*}$ such that the following quantity is time invariant:

Given that even our reduced dynamical system has more than two state variables we cannot apply the Poincaré-Bendixson Theorem. Instead we can prove that there exists a one to one differentiable transformation of our dynamical system so that the resulting system becomes divergence free. Applying Louville’s formula, the flow of the the transformed system is volume preserving. Combined with the invariant of Theorem 5, we can prove that the variables of the transformed system remain bounded. This gives us the following guarantees

Assume that $(\boldsymbol{\theta}(0),\boldsymbol{\phi}(0),\lambda(0),\mu(0))$ is a safe initialization. Then the trajectory under the dynamics of Equation LABEL:eq:eq_gda_multi is diffeomoprphic to one trajectory of a Poincaré recurrent flow.

This result implies that if the corresponding trajectory of the Poincaré recurrent flow is itself recurrent, which almost all of them are, then the trajectory of the dynamics of Equation LABEL:eq:eq_gda_multi is also recurrent. This is however not enough to reason about how often any of the trajectories of the dynamics of Equation LABEL:eq:eq_gda_multi is recurrent. In order to prove that the flow of Equation LABEL:eq:eq_gda_multi is Poincaré recurrent we will make some additional assumptions

Let $f_{i}$ and $g_{j}$ be sigmoid functions. Then the flow of Equation LABEL:eq:eq_gda_multi is Poincaré recurrent. The same holds for all functions $f_{i}$ and $g_{j}$ that are one to one functions and for which all initializations are safe.

It is worth noting that for the unconstrained version of the previous min-max problem we arrive at the same conclusions/theorems by repeating the above analysis without using the Lagrange multipliers.

Spurious equilibria

In the previous sections we have analyzed the behavior of safe initializations and we have proved that they lead to either periodic or recurrent trajectories. For initializations that are not safe for some equilibrium of the hidden game, game theoretically interesting fixed points are not even realizable solutions. In fact we can prove something stronger:

One can construct functions $f$ and $g$ for the system of Equation 4 so that for a positive measure set of initial conditions the trajectories converge to fixed points that do not correspond to equilibria of the hidden game.

The main idea behind our theorem is that we can construct functions $f$ and $g$ that have local optima that break the safety assumption. For a careful choice of the value of the local optima we can make these fixed points stable and then the Stable Manifold Theorem guarantees that a non zero measure set of points in the vicinity of the fixed point converges to it. Of course the idea of these constructions can be extended to our analysis of hidden games with more strategies.

Discrete Time Gradient-Ascent-Descent

In this section we will discuss the implications of our analysis of continuous time gradient-ascent-descent dynamics on the properties of their discrete time counterparts. In general, the behavior of discrete time dynamical systems can be significantly different Li and Yorke (1975); Bailey and Piliouras (2018); Palaiopanos et al. (2017) so it is critical to perform this non-trivial analysis. We are able to show that the picture of non-equilibriation persists for an interesting class of hidden bilinear games.

Let $f_{i}$ and $g_{j}$ be sigmoid functions. Then for the discretized version of the system of Equation LABEL:eq:eq_gda_multi and for safe intializations, function $H$ of Theorem 5 is non-decreasing.

An immediate consequence of the above theorem is that the discretized system cannot converge to the equlibrium $(\boldsymbol{p},\boldsymbol{q})$ if its not initialized there. For the case of non-safe initializations, the conclusions of Theorem 8 persist in this case as well.

One can choose a learning rate $\alpha$ and functions $f$ and $g$ for the discretized version of the system of Equation 4 so that for a positive measure set of initial conditions the trajectories converge to fixed points that do not correspond to equilibria of the hidden game.

Conclusion

In this work, inspired broadly by the structure of the complex competition between generators and discriminators in GANs, we defined a broad class of non-convex non-concave min max optimization games, which we call hidden bilinear zero-sum games. In this setting, we showed that gradient-descent-ascent behavior is considerably more complex than a straightforward convergence to the min-max solution that one might at first suspect. We showed that the trajectories even for the simplest but evocative 2x2 game exhibits cycles. In higher dimensional games, the induced dynamical system could exhibit even more complex behavior like Poincare recurrence. On the other hand, we explored safety conditions whose violation may result in convergence to spurious game-theoretically meaningless equilibria. Finally, we show that even for a simple but widespread family of functions like sigmoids discretizing gradient-descent-ascent can further intensify the disequilibrium phenomena resulting in divergence away from equilibrium.

As a consequence of this work numerous open problems emerge; Firstly, extending such recurrence results to more general families of functions, as well as examining possible generalizations to multi-player network zero-sum games are fascinating questions. Recently, there has been some progress in resolving cyclic behavior in simpler settings by employing different training algorithms/dynamics (e.g., Daskalakis et al. (2018); Mertikopoulos et al. (2019b); Gidel et al. (2019c)). It would be interesting to examine if these algorithms could enhance equilibration in our setting as well. Additionally, the proposed safety conditions shows that a major source of spurious equilibria in GANs could be the bad local optima of the individual neural networks of the discriminator and the generator. Lessons learned from overparametrized neural network architectures that converge to global optima Du et al. (2018) could lead to improved efficiency in training GANs. Finally, analyzing different simplification/models of GANs where provable convergence is possible could lead to interesting comparisons as well as to the emergence of theoretically tractable hybrid models that capture both the hardness of GAN training (e.g. non-convergence, cycling, spurious equilibria, mode collapse, etc) as well as their power.

Acknowledgements

Georgios Piliouras acknowledges MOE AcRF Tier 2 Grant 2016-T2-1-170, grant PIE-SGP-AI-2018-01 and NRF 2018 Fellowship NRF-NRFF2018-07. Emmanouil-Vasileios Vlatakis-Gkaragkounis was supported by NSF CCF-1563155, NSF CCF-1814873, NSF CCF-1703925, NSF CCF-1763970. Finally this work was supported by the Onassis Foundation - Scholarship ID: F ZN 010-1/2017-2018.

References

Appendix A Background in dynamical systems

The Poincaré-Bendixson theorem is a powerful theorem that implies that two-dimensional systems cannot exhibit chaos. Effectively, the limit behavior is either going to be an equilibrium, a periodic orbit, or a closed loop, punctuated by one (or more) fixed points. Formally, we have:

Given a differentiable real dynamical system defined on an open subset of the plane, then every non-empty compact $\omega$ -limit set of an orbit, which contains only finitely many fixed points, is either a fixed point, a periodic orbit, or a connected set composed of a finite number of fixed points together with homoclinic and heteroclinic orbits connecting these.

A.2 Liouville’s formula and Poincaré recurrence

In order to study the flows of dynamical systems in higher dimensions, one needs to understand more about the behaviour of the flow $\Phi$ both in time and space. An important property is the evolution of the volume of $\Phi$ over time:

An interesting class of dynamical systems are those whose vector fields have zero divergence everywhere. Liouville’s formula trivially implies that the volume of the flow is preserved in such systems. This is an important tool for proving that a flow of a dynamical system is Poincaré recurrent.

Let $(X,\Sigma,\mu)$ be a finite measure space and let $f\colon X\to X$ be a measure-preserving transformation. Then, for any $E\in\Sigma$ , the set of those points $x$ of $E$ such that $f^{n}(x)\notin E$ for all $n>0$ has zero measure. That is, almost every point of $E$ returns to $E$ . In fact, almost every point returns infinitely often. Namely,

A.3 Additional Definitions

Let $U,V$ be manifolds. A map $f:U\rightarrow V$ is called a diffeomorphism if $f$ carries $U$ onto $V$ and also both $f$ and $f^{-1}$ are smooth.

Two flows $\Phi_{t}:A\to A$ and $\Psi_{t}:B\to B$ are conjugate if there exists a homeomorphism $g:A\to B$ such that

Furthermore, two flows $\Phi_{t}:A\to A$ and $\Psi_{t}:B\to B$ are diffeomorphic if there exists a diffeomorphism $g:A\to B$ such that

If two flows are diffeomorphic, then their vector fields are related by the derivative of the conjugacy. That is, we get precisely the same result that we would have obtained if we simply transformed the coordinates in their differential equations

Let $\Phi(\boldsymbol{x}_{0},\cdot)$ be the flow of an autonomous dynamical system $\dot{pmb{x}}=f(\boldsymbol{x})$ . Then

Let $\Phi_{t}:A\to A$ and $\Psi_{t}:B\to B$ be conjugate flows and $\gamma$ be the diffeomorphism which connects them. Then a point $\boldsymbol{x}\in V$ is recurrent for $\Phi$ if and only if $\gamma(\boldsymbol{x})\in\gamma(V)$ is recurrent for $\Psi$ .

We will first prove the if direction. Let’s take any open neighborhood $U\subseteq V$ around $\boldsymbol{x}$ . Using the diffeomorphism, there is a unique $\gamma(U)\subseteq\gamma(V)$ and additionally since $U$ is open $\gamma(U)$ is also open. Obviously, $\gamma(\boldsymbol{x})\in\gamma(U)$ . Thus, if $\gamma(\boldsymbol{x})$ is recurrent there is an unbounded increasing sequence of moments $t_{n}$ such that

This is equivalent with the fact that there is an unbounded increasing sequence of moments $t_{n}$ such that

Using the basic property of topological conjugacy, we have that

It follows that $\boldsymbol{x}$ is also recurrent for $\Phi$ . The result for the opposite direction follows immediately by using the inverse map. ∎

A.4 Stable Manifold Theorems

and there exists an $n-k$ dimensional differentiable manifold $U$ tangent to the unstable subspace $E^{u}$ of the linear system $\dot{\boldsymbol{x}}=Df(\mathbf{0})\boldsymbol{x}$ at $\mathbf{0}$ such that for all $t\leq 0$ , $\phi_{t}(U)\subseteq U$ and for all $\boldsymbol{x}_{0}\in U$ :

A.5 Regular Value Theorem

Let $f:U\rightarrow V$ be a smooth map between same dimensional manifolds. We denote that $x\in U$ is a regular point if the derivative is nonsingular. $y\in V$ is called a regular value if $f^{-1}(y)$ contains only regular points. If the derivative is singular, then $x$ is called a critical point. We also say $y\in V$ is a critical value if $y$ is not a regular value.

If $y\in Y$ is a regular value of $f:X\rightarrow Y$ then $f^{-1}(y)$ is a manifold of dimension $n-m$ , since $dim(X)=n$ and $dim(Y)=m$ .

Appendix B Omitted Proofs of Section 4 Warm up: Cycles in hidden bilinear games with two strategies

In this first section, we show a key technical lemma which will be used in many different parts of our proof. More specifically, it shows how someone can derive the solution for a non-autonomous system via a conjugate autonomous dynamical system. The main intuition is that if the non-autonomous term is multiplicative and common across all terms of a vector field then it dictates the magnitude of the vector field (the speed of the motion), but does not affect directionality other than moving backwards or forwards along the same trajectory.

Firstly, notice that it holds $\rho(0)=\boldsymbol{x}_{0}$ and $\dot{\rho}=\nabla k(\rho)$ , since $\rho$ is the unique solution of $\Sigma_{1}$ It is easy to check that:

The next proposition states that initial condition $(\boldsymbol{\theta}(0),\boldsymbol{\phi}(0))$ as well as $\{f(t),g(t)\}_{t=0}^{\infty}$ are sufficient to derive the complete system state of Continuous GDA $(\theta_{\theta_{0}}(t),\phi_{\phi_{0}}(t))$ . The importance of the below theorem arises when someone takes into consideration periodicity and recurrence phenomena. Due to the existence of mapping $(f(t),g(t))$ to a unique $(\boldsymbol{\theta}(t),\boldsymbol{\phi}(t))$ given some initial condition $(\boldsymbol{\theta}(0),\boldsymbol{\phi}(0))$ , any periodic or recurrent behavior of $(f(t),g(t))$ extends to the system trajectories.

Let us first study a simpler dynamical system $(\Sigma^{*})$ with unique solution of $\gamma_{\boldsymbol{\theta}(0)}(t)$ .

If $\boldsymbol{x}_{0}$ is a stationary point of $f$ then the trajectory is a single point and the theorem holds trivially. If $\boldsymbol{x}_{0}$ is not a stationary point of $f$ , $f$ continuously increases along the trajectory of the dynamical system. Therefore $A_{\boldsymbol{\theta}(0)}(t)=f(\gamma_{\boldsymbol{x}_{0}}(t))$ is an increasing function and therefore invertible. Let us call $A^{-1}_{\boldsymbol{\theta}(0)}(f)$ the inverse.

Let’s recall now the dynamical system of our interest ( Equation 4 )

and more precisely to the $\boldsymbol{\theta}$ -part of the system,i.e

Applying Lemma 5 for the first equation with $h(t)=-v(g(\boldsymbol{\phi}(t))-q)$ , we have that the solution of the dynamical system $(\Sigma)$ is

Plug in back to the definition of the solution, clearly we have that :

Therefore for $X_{\boldsymbol{\theta}(0)}(f)=\gamma_{\boldsymbol{\theta}(0)}\circ A^{-1}_{\boldsymbol{\theta}(0)}(f)$ , which is $C^{1}$ as composition of $C^{1}$ functions, the theorem holds.

Notice that the domains of the aforementioned functions are in fact either singleton points or open intervals. This will be important when we study the safety of initial conditions.

If $\boldsymbol{\theta}(0)$ is a stationary point of $f$ , then $f_{\boldsymbol{\theta}(0)}$ consists only of a single number. Otherwise, $f_{\boldsymbol{\theta}(0)}$ is an open interval.

If $\boldsymbol{\theta}(0)$ is a fixed point then for the gradient ascent dynamics $\boldsymbol{\theta}(t)=\boldsymbol{\theta}(0)$ and therefore the Theorem holds trivially. On the other hand, in Theorem 1 we argued that $f(\boldsymbol{\theta}(t))$ is a continuous and strictly increasing function so it should map $(-\infty,\infty)$ to an open set and thus the theorem holds. Obviously we can prove an equivalent theorem for $g$ . ∎

Having established the informational equivalence between the parameter and functional space, we are ready to derive the induced dynamics of the distribution with which two players participate into the game.

Applying chain rule and the definition of Continuous GDA (Equation 4) we can see that :

Finally, we establish that the above 2-dimensional system that couples $f,g$ together is akin to a conservative system that preserves an energy-like function. Under the safety conditions, the proposed invariant is both well-defined and equipped with interesting properties. It is easy to check that it can play the role of a pseudometric around the Nash Equilibrium of the hidden bilinear game.

Let $\boldsymbol{\theta}(0)$ and $\boldsymbol{\phi}(0)$ be safe initial conditions. Then for the system of Equation 4, the following quantity is time-invariant

Firstly, one should notice that since $\boldsymbol{\theta}(0)$ and $\boldsymbol{\phi}(0)$ are safe initial conditions, $H(f,g)$ is well defined when $f,g$ follows the dynamics Continuous-GDA. We will examine the derivative of the proposed invariant of motion.

Using the existence of the invariant function for the safe initial conditions, we will prove that the trajectory of the planar dynamical system stays bounded away from all possible fixed points. Therefore the limit behavior must be a cycle. We can also prove that the system does not just converge to a periodic orbit but it actually lies on the periodic trajectory from the very beginning. The key intuition that allows us to do this is that the level sets of $H$ are one-dimensional manifolds. To get convergence to a periodic orbit, one would require two orbits (the initial trajectory and the periodic orbit) to merge into the same one dimensional manifold, but this is not possible (requires that no transient part exists).

Let $\boldsymbol{\theta}(0)$ and $\boldsymbol{\phi}(0)$ be safe initial conditions. Then for the system of Equation 4, the orbit $(\boldsymbol{\theta}(t),\boldsymbol{\phi}(t))$ is periodic.

If $(\boldsymbol{\theta}(0),\boldsymbol{\phi}(0))$ is a fixed point then it is trivially a periodic point. Suppose $(\boldsymbol{\theta}(0),\boldsymbol{\phi}(0))$ is not a fixed point, then either $f\neq p$ or $g\neq q$ (or both). Given that $H$ is invariant, the trajectory of the planar system stays bounded away from all equilibria. We will examine each case separately:

It is bounded away from these since $H(p,q)=0$ and $H(f(\boldsymbol{\theta}(0)),g(\boldsymbol{\phi}(0)))>0$ .

Equilibria with f=p𝑓𝑝f=p and ∇f=𝟎∇𝑓0\nabla f=\mathbf{0}

These equilibria are not achievable since they are not allowed by the safety conditions. $\nabla f=\mathbf{0}$ when $f=p$ means that $p$ is one of the endpoints of $f_{\boldsymbol{\theta}(0)}$ . But by Lemma 6, $f_{\boldsymbol{\theta}(0)}$ is an open set and $p\in f_{\boldsymbol{\theta}(0)}$ which leads to a contradiction.

Equilibria with g=q𝑔𝑞g=q and ∇g=𝟎∇𝑔0\nabla g=\mathbf{0}

They are also not feasible due to the safety assumption.

Equilibria with ∇f=𝟎∇𝑓0\nabla f=\mathbf{0} and ∇g=𝟎∇𝑔0\nabla g=\mathbf{0}

Observe that such points lie in the corners of $f_{\boldsymbol{\theta}(0)}\times g_{\boldsymbol{\phi}(0)}$ . These points correspond to local maxima of the invariant function. We will prove this for one of the corners and the same proof works for all others in the same way. Let $(p^{*},q^{*})$ be one such corner with both $p^{*}>p$ and $q^{*}>q$ . Let us take any other point $(r,z)$ with $p^{*}\geq r>p$ and $q^{*}\geq z>q$ but different from $(p,q)$ . Without loss of generality let us assume $p^{*}>r$ . Then in this region $H$ is increasing in both $f$ and $g$ . Thus

So this corner (and all the other three corners) are local maxima. A continuous trajectory cannot reach these isolated local maxima while maintaining $H$ invariant.

Thus we can create a trapping/invariant region $C$ so that $f$ and $g$ always stay in $C$ and $C$ does not contain any fixed points. By the Poincaré-Bendixson theorem, the $\alpha,\omega$ -limit set of the trajectory is a periodic orbit. Thus they are isomorphic to $S^{1}$ .

Since the gradient of $H$ is only equal to at $(p,q)$

Therefore $H(f(\boldsymbol{\theta}(0)),g(\boldsymbol{\phi}(0)))>H(p,q)$ is a regular value of $H$ . By the regular value theorem the following set is a one dimensional manifold

Notice that by the invariance of $H$ and definition of $\alpha,\omega-$ limit sets of $(f(\boldsymbol{\theta}(0)),g(\boldsymbol{\phi}(0)))$ , we know that both the trajectory starting at $(\boldsymbol{\theta}(0),\boldsymbol{\phi}(0))$ , along with its $\alpha,\omega-$ limit sets belong to the above manifold. Thus, their union is a closed, connected $1-$ manifold and thus it is isomorphic to $S^{1}$ .

Assume that the trajectory was merely converging to the $\alpha,\omega-$ limit sets. Then our one dimensional manifold is containing two connected one dimensional manifolds: the trajectory of the system as well as the $\alpha,\omega-$ limit sets . But one can easily show that this would not be a one dimensional manifold, leading to a contradiction.

Up to now we have analyzed the trajectories of the planar dynamical system of $f$ and $g$ . But since we have proved that there is one to one correspondence between $\boldsymbol{\theta}$ and $f$ and $\boldsymbol{\phi}$ and $g$ , the periodicity claims transfer to $\boldsymbol{\theta}(t)$ and $\boldsymbol{\phi}(t)$ . ∎

On a positive note, one can prove that the time average of $f$ and $g$ do converge as well as the utilities of the generator and discriminator.

In Theorem Theorem 3 we have discussed that the safety of the initial conditions guarantees that stationary points of $f$ and $g$ are going to be avoided. So using Lemma 2, we can integrate the following quantities over a time interval $[0,T]$ and divide by $T$ .

Let us define the follwoing functions of $f$ and $g$ :

Thus the above dynamical system is equivalent with:

However, by a simple change of variables we have that :

Next, we will proceed with the argument about the time average of the objective function.

If $(\boldsymbol{P},\boldsymbol{Q})$ is fully mixed Nash Equilibrium, then it holds

It suffices to prove the first part of the claim, since the second part is its immediate consequence. Since we have conditioned that $(\boldsymbol{P},\boldsymbol{Q})$ is a fully mixed Nash Equilibrium, it holds :

By our previous analysis in this theorem, we have already argued that

However using similar arguments as before we can prove that

Appendix C Omitted Proofs of Section 5 Poincaré recurrence in hidden bilinear games with more strategies

Then by the dynamics of Continuous GDA (Equation 4)

Finally using Theorem 1 we know that there exist $N+M$ functions such that :

Combining the last two expressions we get the desired claim. ∎

We know that $(\boldsymbol{p},\boldsymbol{q})$ is an equilibrium of the hidden bilinear game

Let us make the same Lagrangian transformation we did in Section 5.

Since $(\boldsymbol{p},\boldsymbol{q})$ is an equilibrium of the problem of Equation 9, the KKT conditions on the Problem of Equation 10 imply that there are (unique) $\lambda^{*},\mu^{*}$

We will analyze the time derivative of $H(\boldsymbol{F}(t),\boldsymbol{G}(t),\lambda(t),\mu(t))$ over the trajectory of CGDA (Equation LABEL:eq:eq_gda_multi).

Observe that summing the two expressions the $u_{i,j}$ terms cancel out. Thus we can write

Additionally we have that $\boldsymbol{p}$ and $\boldsymbol{q}$ are probability vectors so

Since the proof of the following Theorem is fairly complicated, we will firstly outline the basic steps below: 1. We first show that there is topological conjugate dynamical system whose dynamics are incompressible i.e. the volume of a set of initial conditions remains invariant as the dynamics evolve over time. By Theorem 14, if every solution remains in a bounded space for all $t\geq 0$ , incompressibility implies recurrence. 2. To establish boundedness in these dynamics, we exploit the aforementioned invariant function.

Let us start with the dynamics of Equation LABEL:eq:eq_gda_multi. We we call its flow $\Phi_{\textrm{original}}$ :

In the previous theorems we have proved that $(X_{\boldsymbol{\theta}_{i}(0)},X_{\boldsymbol{\phi}_{j}(0)})$ are diffeomorphisms. We also know that by definition we have that

We can thus define the following diffeomorphism

Applying the transform we get a new dynamical system, whose flow we will call $\Phi_{\textrm{distributional}}$ :

Although $\Phi_{\textrm{distributional}}$ could be well defined for a wider set of points, we will focus our attention on the following set of points

Observe that this choice is not problematic since:

$V$ is an invariant set of $\Phi_{\textrm{distributional}}$

and thus by the equations of $\dot{f_{i}}$ , we have $\dot{f_{i}}=0$ . On the one hand, observe that for $\Phi_{\textrm{distributional}}(\boldsymbol{\mathfrak{D}}_{\textrm{critical}},\cdot)$ we have that $f_{i}$ should be constant. On the other hand, for $\Phi_{\textrm{distributional}}(\boldsymbol{\mathfrak{D}}_{0},\cdot)$ it is not the case since $\boldsymbol{\mathfrak{D}}_{0}\in V$ and $\boldsymbol{\mathfrak{D}}_{\textrm{critical}}$ has an $f_{i}$ that is on the edge of $f_{i_{\boldsymbol{\theta}_{i}(0)}}$ . Thus $\Phi_{\textrm{distributional}}(\boldsymbol{\mathfrak{D}}_{0},\cdot)$ and $\Phi_{\textrm{distributional}}(\boldsymbol{\mathfrak{D}}_{\textrm{critical}},\cdot)$ are different. This is a contradiction since $\boldsymbol{\mathfrak{D}}_{\textrm{critical}}$ and $\boldsymbol{\mathfrak{D}}_{0}$ belong to the same trajectory of the flow. The same argument applies for $g_{j}$ .

Clearly $\Phi_{\textrm{original}}(\{\boldsymbol{\theta}_{i}(0),\boldsymbol{\phi}_{j}(0),\mu(0),\lambda(0)\},\cdot)$ and $\Phi(\{f_{i}(\boldsymbol{\theta}_{i}(0)),g_{j}(\boldsymbol{\phi}_{j}(0)),\mu(0),\lambda(0)\},\cdot)$ are diffeomorphic. It thus remains to prove that $\Phi$ is Poincaré recurrent.

We will transform the above dynamical system to a divergence free system on different space via the following map :

are positive and smooth functions. Thus $\mathcal{A}_{i}(f_{i}),\mathcal{B}_{j}(g_{j})$ are monotone functions and consequently bijections and are continuously differentiable. Again because of the monotonicity using Inverse Function Theorem we can show easily that $\mathcal{A}_{i}(f_{i}),\mathcal{B}_{j}(g_{j})$ have also continuously differentiable inverse. ∎

As a first step let us apply $\gamma$ on the equations of our dynamical system:

Observe that on the right hand side of our equations, $f_{i}$ can be written as $\mathcal{A}_{i}^{-1}(a_{i})$ and $g_{j}$ can be written as $\mathcal{B}_{j}^{-1}(g_{j})$ , so this is an autonomous dynamical system, whoose flow we will call $\Psi$ and whose vector field we will call $\boldsymbol{Y}$ :

Taking the Jacobian of $\boldsymbol{Y}$ , all elements across the diagonal are zero : The coordinate of $\dot{a_{i}}$ does not depend on $a_{i}$ and the same goes for all state variables. Given that the divergence of the vector field is equal to the trace of the Jacobian, we are certain that this new dynamical system is divergence free:

Once again we focus our attention on $\gamma(V)$ that is invariant for $\Psi$ . To prove this invariant, assume that one trajectory of $\Psi$ starting from inside $\gamma(V)$ escaped it. Then given that $\gamma$ is a diffeomorphism, the corresponding trajectory of $\Phi$ will start from $V$ and also escape it, which is not possible since $V$ is invariant for $\Phi$ .

Boundness of Trajectories

In the next section of the proof, we will show that the trajectories of $\Psi$ are also bounded. Our analysis will be based on the invariant function of Theorem 5. Note that based on the way we proved Theorem 5, the invariant supplied there is binding for all initializations in $V$ and not just the trajectory of $\Phi(\{f_{i}(\boldsymbol{\theta}_{i}(0)),g_{j}(\boldsymbol{\phi}_{j}(0)),\mu(0),\lambda(0)\},\cdot)$ .

For all initializations in $\gamma(V)$ , it holds that $\lambda(t),\mu(t)$ are bounded.

The last step of this analysis comes from the fact that $H$ is a sum of non-negative terms so if one of them goes to infinity the whole sum becomes unbounded. Since initializations in $V$ start with finite values of $H$ , it is necessary that $\lambda$ remains bounded. Obviously, the same proof strategy applies to the case of $\mu(t)$ . ∎

Now let us analyze the rest of the variables

For all initializations in $\gamma(V)$ , it holds that $a_{i}(t),b_{j}(t)$ are bounded.

This is true because $z-p_{i}$ is bounded away from zero when $f_{i}$ is converging to the edges of $f_{i_{\boldsymbol{\theta}_{i}(0)}}$ as $p_{i}$ is in the interior of the set for safe initializations. Thereofe we can once again conclude that

Once again for initializations in $V$ , $H$ remains constant and finite. Therefore $a_{i}$ should be bounded. The same analysis works for $b_{j}$ . ∎

Application of Poincaré Recurrence Theorem

To summarize the properties that we have established until now , we have shown that system of $\Psi$ is divergence free and has only bounded orbits. Liouville’s formula also yields that $\Psi$ is a volume preserving flow. By applying Poincaré Recurrence Theorem ( Theorem 14 ) almost all initial conditions in $\gamma(V)$ of $\Psi$ are recurrent. Thus the set $W$ of all non-recurrent points in $\Psi$ has measure zero.

Using the properties of diffeomorphism, we can to propagate the recurrence behavior of $\Psi$ back to $\Phi_{\textrm{disitributional}}$ using Lemma 4 Thus the set of recurrent points of $\Phi$ is $\gamma^{-1}(W)$ . Since diffeomorphisms preserve measure zero sets and $W$ has measure zero, the set of recurrent points of $\Phi$ has measure zero, indicating that $\Phi$ is indeed recurrent. ∎

One can notice that since $f_{i}$ and $g_{j}$ are invertible functions $X_{\theta_{i}(0)}(\cdot)$ is totally independent of the choice $\theta_{i}(0)$ . In other words we can substitute

Thus, in contrast to the previous theorem (Theorem 6), the construction of $\Phi_{\textrm{distributional}}$ does not depend on the initialization. There is a unique $\Phi_{\textrm{distributional}}$ for all initializations. In fact using the same map $\nu$ as in the previous theorem, we can prove that $\Phi_{\textrm{original}}$ is diffeomorphic to $\Phi_{\textrm{distributional}}$ . However, using the previous theorem the flow $\Phi_{\textrm{distributional}}$ is Poincaré recurrent. Repeating the topological conjugacy argument of the previous theorem we can transfer the Poincaré recurrence property from the dynamical system of $\Phi_{\textrm{distributional}}$ to the dynamical system of $\Phi_{\textrm{original}}$ . ∎

Appendix D Omitted Proofs of Section 6 Spurious equilibria

Our strategy is to analyze the structure of the Jacobian of the vector field of Equation 4 at stationary points of $f$ and $g$ . Let us call $\boldsymbol{Y}(\boldsymbol{\theta},\boldsymbol{\phi})$ the vector field of Equation 4. Now we can write down its Jacobian

Let us focus our attention on stationary points of $f$ and $g$ . Let us call them $\boldsymbol{\theta}^{*}$ and $\boldsymbol{\phi}^{*}$

Here we will analyze the case of $v>0$ (the case of $v<0$ is completely similar). To get that all eigenvalues are negative we can simply require:

$\nabla^{2}f(\boldsymbol{\theta}^{*})$ and $\nabla^{2}g(\boldsymbol{\phi}^{*})$ are invertible.

$\boldsymbol{\phi}^{*}$ is a local minimum with $g(\boldsymbol{\phi}^{*})>q$ . Combined with the first condition we get that $\nabla^{2}g(\boldsymbol{\phi}^{*})$ is positive definite.

$\boldsymbol{\theta}^{*}$ is a local minimum with $f(\boldsymbol{\theta}^{*})<p$ . Combined with the first condition we get that $\nabla^{2}f(\boldsymbol{\theta}^{*})$ is positive definite.

One can observe that the second condition allows the existence of unsafe initializations if $\boldsymbol{\phi}(0)$ is in the vicinity of $\boldsymbol{\phi}^{*}$ .

Clearly based on Theorem 15, there is a full dimensional manifold of points that eventually converge to this fixed point. Given that the manifold has full dimension, this set of points has positive measure. Additionally, $g(\boldsymbol{\phi}^{*})$ and $f(\boldsymbol{\theta}^{*})$ do not take the values of the unique equilibrium of the hidden Game. ∎

Appendix E Omitted Proofs of Section 7 Discrete Time Gradient-Descent-Ascent

The outline of this Section is the following: 1. We first review an existing result that shows that invariants of continuous time systems that have convex level sets, even though they may not be invariants for the discrete time counterparts, they are at least non-decreasing for the discrete case. 2. We show that the invariant of Theorem 5 is convex for the case of sigmoid functions. Therefore it has convex level sets. 3. We extend the construction of Theorem 8 to discrete time systems.

Suppose a continuous dynamic $y(t)$ has an invariant energy $H(y)$ . If $H$ is continuous with convex sublevel sets then the energy in the corresponding discrete-time dynamic obtained via Euler’s method/integration is non-decreasing.

Let us consider a continuous time dynamical system:

Let $t$ denote the current time instant of a trajectory with initial conditions $\boldsymbol{y}_{0}$ . Doing discrete time gradient-descent-ascent with with step-size $\eta$ yields an approximation of $\boldsymbol{y}_{\boldsymbol{y}_{0}}(t+\eta)$

To prove our theorem it suffices to show that

Suppose $H(\boldsymbol{y}_{\boldsymbol{y}_{0}}(t))=c$ and without loss of generality, assume $\{\boldsymbol{y}_{\boldsymbol{y}_{0}}:H(\boldsymbol{y}_{\boldsymbol{y}_{0}})\leq c\}$ is full-dimensional. Since $\{\boldsymbol{y}_{\boldsymbol{y}_{0}}:H(\boldsymbol{y}_{\boldsymbol{y}_{0}})\leq c\}$ is convex, there exists a supporting hyperplane $\{\boldsymbol{y}_{\boldsymbol{y}_{0}}:a^{\intercal}\boldsymbol{y}_{\boldsymbol{y}_{0}}=a^{\intercal}\boldsymbol{y}_{\boldsymbol{y}_{0}}(t)\}$ such that $a^{\intercal}\boldsymbol{y}_{\boldsymbol{y}_{0}}\leq a^{\intercal}\boldsymbol{y}_{\boldsymbol{y}_{0}}(t)$ for all $\boldsymbol{y}_{\boldsymbol{y}_{0}}\in\{\boldsymbol{y}_{\boldsymbol{y}_{0}}:H(\boldsymbol{y}_{\boldsymbol{y}_{0}})\leq c\}$ .

For contradiction, suppose $H(\hat{\boldsymbol{y}_{\boldsymbol{y}_{0}}}^{t+\eta})<c$ . By continuity of $H$ , for sufficiently small $\epsilon>0$ , $\hat{\boldsymbol{y}_{\boldsymbol{y}_{0}}}^{t+\eta}+\epsilon a\in\{\boldsymbol{y}_{\boldsymbol{y}_{0}}:H(\boldsymbol{y}_{\boldsymbol{y}_{0}})\leq c\}$ . However,

contradicting that $\{\boldsymbol{y}_{\boldsymbol{y}_{0}}:a^{\intercal}\boldsymbol{y}_{\boldsymbol{y}_{0}}=a^{\intercal}\boldsymbol{y}_{\boldsymbol{y}_{0}}(t)\}$ is a supporting hyperplane. Thus, the statement of the theorem holds. ∎

The invariant of Theorem 5 is jointly convex in $\boldsymbol{\theta}$ , $\boldsymbol{\phi}$ , $\lambda$ and $\mu$ when $f_{i}$ and $g_{j}$ are sigmoid functions of one variable.

Since $H$ is a sum of terms each involving disjoint variables, it suffices to prove that each term is convex with respect to its own variables. This follows immediately for $\lambda$ and $\mu$ . Let us take one term involving $f_{i}$ (the same analysis works for $g_{j}$ terms as well). In fact we want to prove that the following function is convex

where $f$ is the sigmoid function. Taking the first derivative, knowing that $f^{\prime}=(1-f)f$ for sigmoid we have

$X_{\theta_{i}(0)}(f(\theta_{i}))$ is equal to $\theta_{i}$ since $f$ is one-to-one. Thus we can simplify

Once again we can use the formula for the derivative of $f$

In order to complete the convexity analysis we must take the second derivative test.

Of course for $p_{i}\in(0,1)$ these roots are not real. So for all $\theta_{i}$ , $f(\theta_{i})\in(0,1)$ and the second derivative is positive. This concludes our convexity proof. ∎

First observe that given that sigmoids are invertible functions so $X_{\theta_{i}(0)}(f_{i})$ and $X_{\phi_{j}(0)}(g_{j})$ are independent of the initial conditions similar to the proof of Theorem 7. Thus invariant of Theorem 5 $H$ preserved by all the trajectories of the continuous time dynamical system is common across all initializations. Using Lemma 9, $H$ is convex and therefore has convex level sets. Of course it is also continuous. Using Theorem 26 we get the requested result. ∎

The proof follows the same construction as in the continuous case of Theorem 8. In fact, the Jacobian of the discrete time map is

Then the Jacobian of the discrete time map has positive eigenvalues that are less than one. Therefore the discrete time map is locally a diffeomorphism and by the Stable Manifold Theorem for discrete time maps (Theorem 16), the stable manifold is again full dimensional and therefore has positive measure. ∎