Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation

Introduction

In this paper we study learning in zero-sum games of the form

As a result of this perspective, there has been significant interest in the study of gradient descent-ascent owing to the fact that the learning rule is computationally efficient and a natural analogue to gradient descent from function optimization. Formally, the learning dynamics are given by each player myopically updating a strategy with an individual gradient as follows:

The analysis of gradient descent-ascent is complicated by the intricate optimization landscape in non-convex, non-concave zero-sum games. To begin, there is the fundamental question of what type of solution concept is desired. Given the class of games under consideration, local solution concepts have been proposed and are often taken to be the goal of a learning algorithm. The primary notions of equilibrium that have been adopted are the local Nash and local minmax/Stackelberg concepts with a focus on the set of strict local equilibrium that can be characterized by gradient-based sufficient conditions. Following several past works, from here on we refer to strict local Nash equilibrium and strict local minmax/Stackelberg equilibrium as differential Nash equilibrium and differential Stackelberg equilibrium, respectively.

Regardless of the equilibrium notion under consideration, a number of past works highlight failures of standard gradient descent-ascent in non-convex, non-concave zero-sum games. Indeed, it has been shown gradient descent-ascent with a shared learning rate ($\gamma_{1}=\gamma_{2}$) is prone to reaching critical points that are neither differential Nash equilibrium nor differential Stackelberg equilibrium (Daskalakis and Panageas, 2018; Mazumdar et al., 2020; Jin et al., 2020). While an important negative result, it does not rule out the prospect that gradient descent-ascent may be able to guarantee equilibrium convergence as it fails to account for a key structural parameter of the learning dynamics, namely the ratio of learning rates between the players.

Motivated by the observation that the order of play between players is fundamental to the definition of the game, the role of timescale separation in gradient descent-ascent has been explored theoretically in recent years (Heusel et al., 2017; Chasnov et al., 2019; Jin et al., 2020). On the empirical side of past work, it has been widely demonstrated and prescribed that timescale separation in gradient descent-ascent between the generator and discriminator, either by heterogeneous learning rates or unrolled updates, is crucial to improving the solution quality when training generative adversarial networks (Goodfellow et al., 2014; Arjovsky et al., 2017; Heusel et al., 2017). Denoting $\gamma_{1}$ as the learning rate of the player 1, the learning rate of player 2 can be redefined as $\gamma_{2}=\tau\gamma_{1}$ where $\tau=\gamma_{2}/\gamma_{1}>0$ is the ratio of learning rates or timescale separation parameter. The work of Jin et al. (2020) took a meaningful step toward understanding the effect of timescale separation in gradient descent-ascent by showing that as $\tau\rightarrow\infty$ the stable critical points of the learning dynamics coincide with the set of differential Stackelberg equilibrium. In simple terms, the aforementioned result implies that all ‘bad critical points’ (that is, critical points lacking game-theoretic meaning) become unstable as the timescale separation approaches infinity and that all ‘good critical points’ (that is, game-theoretically meaningful equilibria) remain or become stable as the timescale separation approaches infinity. While a promising theoretical development on the local stability of the underlying dynamics, it does not lead to a practical, implementable learning rule or necessarily provide an explanation for the satisfying performance in applications of gradient descent-ascent with a finite timescale separation. It remains an open question to fully understand gradient descent-ascent as a function of the timescale separation and to determine whether the desirable behavior with an infinite timescale separation is achievable for a range of finite learning rate ratios.

This paper continues the theoretical study of gradient descent-ascent with timescale separation in non-convex, non-concave zero-sum games. We focus our attention on answering the remaining open questions regarding the behavior of the learning dynamics with finite learning rate ratios and provide a number of conclusive results. Notably, we develop necessary and sufficient conditions for a critical point to be stable for a range of finite learning rate ratios. The results imply that differential Stackelberg equilibria are stable for a range of finite learning rate ratios and that non-equilibria critical points are unstable for a range of finite learning rate ratios. Together, this means gradient descent-ascent only converges to differential Stackelberg equilibrium for a range of finite learning rate ratios. To our knowledge, this is the first provable guarantee of its kind for an implementable first-order method. Moreover, the technical results in this work rely on tools that have not appeared in the machine learning and optimization communities analyzing games and expose a number interesting directions of future research. Explicitly, the notion of a guard map, which is arguably even an obscure tool in modern control and dynamical systems theory, is ‘rediscovered’ in this work as a technique for analyzing the stability of game dynamics.

To motivate our primary theoretical results, we present a self-contained description of what is known about the local stability of gradient descent-ascent around critical points in Section 3.1. The existing results primarily concern gradient descent-ascent without timescale separation and with a ratio of learning rates approaching infinity (see Figure 1 for a graphical depiction of known results in each regime). In contrast, this paper is focused on characterizing the stability and convergence of gradient descent-ascent across a range of finite learning rate ratios. To hint at what is achievable in this realm, we present simple examples for which gradient descent-ascent converges to non-equilibrium critical points and games with differential Stackelberg equilibrium that are unstable with respect to gradient descent-ascent without timescale separation (see Examples 1 and 2, Section 3). While the existence of such examples is known (Daskalakis and Panageas, 2018; Mazumdar et al., 2020; Jin et al., 2020), we demonstrate in them that a finite timescale separation is sufficient to remedy the undesirable stability properties of gradient descent-ascent without timescale separation.

Toward characterizing this phenomenon in its full generality, we provide intermediate results which are known, but we prove using technical tools not yet broadly seen and exploited by this community. To begin, it is known that the set of differential Nash equilibrium are stable with respect to gradient descent-ascent (Mazumdar and Ratliff, 2019; Daskalakis and Panageas, 2018), and that they remain stable for any timescale separation parameter $\tau\in(0,\infty)$ (Jin et al., 2020). We provide a proof for this result (Proposition 3.1) using the concept of quadratic numerical range (Tretter, 2008). Furthermore, Jin et al. (2020) recently showed that as the timescale separation $\tau\rightarrow\infty$, the stable critical points of gradient descent-ascent coincide with the set of differential Stackelberg equilibrium. We reveal that this result has long existed in the literature on singularly perturbed systems (Kokotovic et al., 1986, Chapter 2 and the citations within) and provide a proof (see Proposition 3.2) using analysis methods from the aforementioned line of work that are novel to the literature on learning in games from the machine learning and optimization communities in recent years.

A relevant line of study on singularly perturbed systems is that of characterizing the range of perturbation parameters for which a system is stable (Kokotovic et al., 1986; Saydy et al., 1990; Saydy, 1996). Debatably introduced by Saydy et al. (1990), guardian or guard maps act as a certificate that the roots of a polynomial lie in a particular guarded domain for a range of parameter values. Historically, guard maps serve as a tool for studying the stability of parameterized families of dynamical systems. We bring this tool to learning in games and construct a map that guards a class of Hurwitz stable matrices parameterized by the timescale separation parameter $\tau$ in order to analyze the range of learning rate ratios for which a critical point is stable with respect to gradient descent-ascent. This technique leads to the following result.

Consider a sufficiently regular critical point $x^{\ast}$ of gradient descent-ascent. There exists a $\tau^{\ast}\in(0,\infty)$ such that $x^{\ast}$ is stable for all $\tau\in(\tau^{\ast},\infty)$ if and only if $x^{\ast}$ is a differential Stackelberg equilibrium.

Theorem 3.1 confirms that there does indeed exist a range of finite learning ratios such that a differential Stackelberg equilibrium is stable with respect to gradient descent-ascent. Moreover, such a range of learning rate ratios only exists if a critical point is a differential Stackelberg equilibrium. As we show in Corollary 4.1, the former implication of Theorem 3.1 nearly immediately implies there exists a $\tau^{\ast}\in(0,\infty)$ such that gradient descent-ascent converges locally asymptotically for all $\tau\in(\tau^{\ast},\infty)$ if and only if $x^{\ast}$ is a differential Stackelberg equilibrium given a suitably chosen learning rate and deterministic gradient feedback. We give an explicit asymptotic rate of convergence in Theorem 4.1 and characterize the iteration complexity in Corollary 4.2. Moreover, we extend the convergence guarantees to stochastic gradient feedback in Theorem 4.2.

The latter implication of Theorem 3.1 says that there exists a finite learning rate ratio such that a non-equilibrium critical point of gradient descent-ascent is unstable. Building off of this, we complement the stability result of Theorem 3.1 with the following analagous instability result.

Consider any stable critical point $x^{\ast}$ of gradient descent-ascent which is not a differential Stackelberg equilibrium. There exists a finite learning rate ratio $\tau_{0}\in(0,\infty)$ such that $x^{\ast}$ is unstable for all $\tau\in(\tau_{0},\infty)$.

Theorem 3.2 establishes that there exists a range of finite learning ratios non-equilibrium critical points are unstable with respect to gradient descent-ascent. This implies that for a suitably chosen finite timescale separation, gradient descent-ascent avoids critical points lacking game-theoretic meaning. Together, Theorem 3.1 and Theorem 3.2 answer affirmatively that gradient descent-ascent with timescale separation can guarantee equilibrium convergence, which answers a standing open question. Moreover, we provide explicit constructions for computing $\tau^{\ast}$ and $\tau_{0}$ given a critical point. In fact our construction of $\tau^{\ast}$ in Theorem 3.1 is tight, and this is confirmed by our numerical experiments.

We finish the theoretical analysis of gradient descent-ascent in this paper by connecting to the literature on generative adversarial networks. We show under common assumptions on generative adversarial networks (Nagarajan and Kolter, 2017; Mescheder et al., 2018) that the introduction of gradient penalty based regularization to the discriminator does not change the set of critical points for the dynamics and, further, there exists a finite learning rate ratio $\tau^{\ast}$ such that for any learning rate ratio $\tau\in(\tau^{\ast},\infty)$ and any non-negative, finite regularization parameter $\mu$, the continuous time limiting regularized learning dynamics remain stable, and hence, there is a range of learning rates $\gamma_{1}$ for which the discrete time update locally converges asymptotically.

The theoretical results we provide are complemented by extensive experiments. In simulation, we explore a number of interesting behaviors of gradient descent-ascent with timescale separation analyzed theoretically including differential Stackelberg equilibria shifting from being unstable to stable and non-equilibrium critical points moving from being stable to unstable. Furthermore, we examine how the vector field and the spectrum of the game Jacobian evolve as a function of the timescale separation and explore the relationship with the rate of convergence. We experiment with gradient descent-ascent on the Dirac-GAN proposed by Mescheder et al. (2018) and illustrate the interplay between timescale separation, regularization, and rate of convergence. Building on this, we train generative adversarial networks on the CIFAR-10 and CelebA datasets with regularization and demonstrate that timescale separation can benefit performance and stability. In the experiments we observe that regularization and timescale separation are intimately connected and there is an inherent tradeoff between them. This indicates that insights made on simple generative adversarial network formulations may carry over to the complex problems where players are parameterized by neural networks.

Collectively, the primary contribution of this paper is the near-complete characterization of the behavior of gradient descent-ascent with finite timescale separation. Moreover, by introducing a novel set of analysis tools to this literature, our work opens a number of future research questions. As an aside, we believe these technical tools open up novel avenues for not only proving results about learning dynamics in games, but also for synthesizing algorithms.

2 Organization

The organization of this paper is as follows. Preliminaries on game theoretic notions of equilibria, gradient-based learning algorithms, and dynamical systems theory are reviewed in Section 2.

Convergence analysis proceeds in two phases. In Section 3, we study the stability properties of the continuous time limiting dynamical system given a timescale separation between the minimizing and maximizing players. Specifically, we show the first result on necessary and sufficient conditions for convergence of the continuous time limiting system corresponding to gradient descent-ascent with time scale separation to game theoretically meaningful equilibria (i.e., local minmax equilibria in zero-sum games). Following this, in Section 4, we provide convergence guarantees for the original discrete time dynamical system of interest (namely, gradient descent ascent). Using the results in the proceeding section, we show that gradient descent-ascent converges to a critical point if and only if it is a differential Stackelberg equilibrium (i.e., a sufficiently regular local minmax). In addition, we characterize the iteration complexity of gradient descent-ascent dynamics and provide finite-time bounds on local convergence to approximate local Stackelberg equilibria.

We apply the main results in the preceding sections to generative adversarial networks in Section 5, and in Section 6 we present several illustrative examples including generative adversarial networks where we show that tuning the learning rate ratio along with regularization and the exponential moving average hyperparameter significantly improves the Fréchet Inception Distance (FID) metric for generative adversarial networks.

Given its length, prior to concluding in Section 7, we review related work drawing connections to solution concepts, gradient descent-ascent learning dynamics, applications to adversarial learning where the success of heuristics provide strong motivation for the theoretical work in this paper, and historical connections to dynamical systems theory. Throughout the sections proceeding Section 7, we draw connections to related works and results in an effort to place our results in the context of the literature. We conclude in Section 8 with a discussion on the significance of the results and open questions. The appendix includes the majority of the detailed proofs as well as additional experiments and commentary.

Preliminaries

In this section, we review game theoretic and dynamical systems preliminaries. Additionally, we formulate the class of learning rules analyzed in this paper.

There are two natural equilibrium concepts for such games depending on the order of play—i.e., the Nash equilibrium concept in the case of simultaneous play and the Stackelberg equilibrium concept in the case of hierarchical play. Each notion of equilibria can be characterized as the intersection points of the reaction curves of the players (Başar and Olsder, 1998).

The joint strategy $x\in X$ is a local Nash equilibrium on $\prod_{i\in\mathcal{I}}U_{i}\subset X$, where $U_{i}\subseteq X_{i}$, if $f(x_{1},x_{2})\leq f(x_{1}^{\prime},x_{2})$, for all $x_{1}^{\prime}\in U_{1}\subset X_{1}$ and $f(x_{1},x_{2})\geq f(x_{1},x_{2}^{\prime})$ for all $x_{2}^{\prime}\in U_{2}\subset X_{2}$. Furthermore, if the inequalities are strict, we say $x$ is a strict local Nash equilibrium.

Consider $U_{i}\subset X_{i}$ for $i=1,2$ where, without loss of generality, player 1 is the leader (minimizing player) and player 2 is the follower (maximizing player). The strategy $x_{1}^{\ast}\in U_{1}$ is a local Stackelberg solution for the leader if, $\forall x_{1}\in U_{1}$,

where $r_{U_{2}}(x_{1})=\{y\in U_{2}|f(x_{1},y)\geq f(x_{1},x_{2}),\forall x_{2}\in U_{2}\}$ is the reaction curve. Moreover, for any $x_{2}^{\ast}\in r_{U_{2}}(x_{1}^{\ast})$, the joint strategy profile $(x_{1}^{\ast},x_{2}^{\ast})\in U_{1}\times U_{2}$ is a local Stackelberg equilibrium on $U_{1}\times U_{2}$.

Predicated on existence,Characterizing existence of equilibria is outside the scope of this work. However, we remark that Nash equilibria exist for convex costs on compact and convex strategy spaces and Stackelberg equilibria exist on compact strategy spaces (Başar and Olsder, 1998, Thm. 4.3, Thm. 4.8, & Sec. 4.9). equilibria can be characterized in terms of sufficient conditions on player costs. Indeed, in continuous games, first and second order conditions on player cost functions leads to a differential characterization (i.e., necessary and sufficient conditions) of local Nash equilibria reminiscent of optimality conditions in nonlinear programming (Ratliff et al., 2016).The differential characterization of local Nash equilibria in continuous games was first reported in (Ratliff et al., 2013). Genericity and structural stability we studied in general-sum settings in (Ratliff et al., 2014) and in zero-sum settings in (Mazumdar and Ratliff, 2019).

We denote $D_{i}f_{i}$ as the derivative of $f_{i}$ with respect to $x_{i}$, $D_{ij}f_{i}$ as the partial derivative of $D_{i}f_{i}$ with respect to $x_{j}$, $D_{i}^{2}f_{i}$ as the partial derivative of $D_{i}f_{i}$ with respect to $x_{i}$, and $D(\cdot)$ as the total derivative.Example: given $f(x,h(x))$, $Df=D_{1}f+D_{2}f\circ Dh$.

If $x$ is a local Nash equilibrium of the zero-sum game $((f,-f)$, then $D_{1}f(x)=0$, $-D_{2}f(x)=0$, $D_{1}^{2}f(x)\geq 0$ and $D_{2}^{2}f(x)\leq 0$. On the other hand, if $D_{1}f(x)=0$, $D_{2}f(x)=0$, and $D_{1}^{2}f(x)>0$ and $D_{2}^{2}f(x)<0$, then $x\in X$ is a local Nash equilibrium.

The following definition, characterized by sufficient conditions for a local Nash equilibrium as defined in Definition 2.1, was first introduced in (Ratliff et al., 2013).

The joint strategy $x\in X$ is a differential Nash equilibrium if $D_{1}f(x)=0$, $-D_{2}f(x)=0$, $D_{1}^{2}f(x)>0$ and $D_{2}^{2}f(x)<0$.

The joint strategy $x=(x_{1},x_{2})\in X$ is a differential Stackelberg equilibrium if $D_{1}f(x_{1},x_{2})=0$, $-D_{2}f(x_{1},x_{2})=0$, $D^{2}f(x_{1},x_{2})>0$, and $D_{2}^{2}f(x_{1},x_{2})<0$.

Observe that in a general sum setting the first order conditions for player $1$ are equivalent the total derivative of $f$ being zero at the candidate critical point where $x_{2}$ is implicitly defined as a function of $x_{1}$ via the implicit mapping theorem applied to $D_{2}f(x_{1},x_{2})=0$. Since in this paper and in Definition 2.4, the class of games is zero sum, $D_{1}f(x_{1},x_{2})=0$ and $D_{2}f(x_{1},x_{2})=0$ (along with the condition that $\det(D_{2}^{2}f(x_{1},x_{2}))\neq 0$ which is implied by the second order conditions) are sufficient to imply that the total derivative $Df(x_{1},x_{1})$ is zero.

The Jacobian of the first order necessary and sufficient condition—i.e., conditions that define potential candidate differential Nash and/or Stackelberg equilibria—is a useful mathematical object for understanding convergence properties of gradient based learning rules as we will see in subsequent sections. Consider the vector of individual gradients $g(x)=(D_{1}f(x),-D_{2}f(x))$ which define first order conditions for a differential Nash equilibrium. Let $J(x)$ denote the Jacobian of $g(x)$ which is defined by

We recall from Fiez et al. (2020) an alternative (to Definition 2.4, but equivalent set of sufficient conditions for a differential Stackelberg in terms of $J(x)$. Let ${\tt S}_{1}(\cdot)$ denote the Schur complement of $(\cdot)$ with respect to the $n_{2}\times n$ block-row matrix in $(\cdot)$.

2 Gradient-based learning algorithms

As noted above, in this paper we focus on settings in which agents or players in this game are seeking equilibria of the game via a learning algorithm. We study arguably the most natural learning rule in zero-sum continuous games: gradient descent-ascent (GDA). This gradient-based learning rule is a simultaneous gradient play algorithm in that agents update their actions at each iteration simultaneously.

Gradient descent-ascent is defined as follows. At iteration $k$, each agent $i\in\mathcal{I}$ updates their choice variable $x_{i,k}\in X_{i}$ by the process

where $\gamma_{i}$ is agent $i$’s learning rate, and $g_{i}(x)$ is agent $i$’s gradient-based update mechanism. For simultaneous gradient play,

is the vector of individual gradients and in a zero-sum setting, GDA is defined using $g(x)=(D_{1}f(x),-D_{2}f(x))$ where the first player is the minimizing player and the second player is the maximizing player.

We analyze the iteration complexity or local asymptotic rate of convergence of learning rules of the form (2) in the neighborhood of an equilibrium. Given two real valued functions $F(k)$ and $G(k)$, we write $F(k)=O(G(k))$ if there exists a positive constant $c>0$ such that $|F(k)|\leq c|G(k)|$. For example, consider iterates generated by (2) with initial condition $x_{0}$ and critical point $x^{\ast}$. Suppose that we show $\|x_{k+1}-x^{\ast}\|\leq M^{k}\|x_{0}-x^{\ast}\|$. Then, we write $F(k)=O(M^{k})$ where $c=\|x_{0}-x^{\ast}\|$.

3 Dynamical Systems Primer

In this paper, we study learning rules employed by agents seeking game-theoretically meaningful equilibria in continuous games. Dynamical systems tools for both continuous and discrete time play a crucial role in this analysis.

Before we proceed, we recall and remark on some facts from dynamical systems theory concerning stability of equilibria in the continuous-time dynamics

relevant to convergence analysis for the discrete-time learning dynamics in (2). Observe that equilibria are shared between (2) and (5). Our focus is on the subset of equilibria that satisfy Definition 2.4, and the subset thereof defined in Definition 2.3. Recall the following equivalent characterizations of stability for an equilibrium of (5) in terms of the Jacobian matrix $J(x)=Dg(x)$.

The continuous time dynamical system takes the form $\dot{x}=-\Lambda_{\tau}g(x)$ due to the timescale separation $\tau$. Such a system is known as a singularly perturbed system or a multi-timescale system in the dynamical systems theory literature (Kokotovic et al., 1986), particularly where $\tau^{-1}$ is small. Singularly perturbed systems are classically expressed as

where $\epsilon=\tau^{-1}$ is most often a physically meaningful quantity inherent to some dynamical system that describes the evolution of some physical phenomena; e.g., in circuits it may be a constant related to device material properties, and in communication networks, it is often the speed at which data flows through a physical medium such as cable.

Given a dynamical system $\dot{x}=F(x)$, the state or solution of the system at time $t$ starting from $x$ at time $t_{0}$ is called the flow and is denoted $\phi^{t}(x)$.

Consider the $n$-dimensional dynamical system $\dot{x}=F(x)$ with equilibrium point $\bar{x}$. If $DF(\bar{x})$ has no zero or purely imaginary eigenvalues, there is a homeomorphism $h$ defined on a neighborhood $U$ of $\bar{x}$ taking orbits of the flow $\phi^{t}$ to those of the linear flow $e^{tDF(\bar{x})}$ of $\dot{x}=F(x)$—that is, the flows are topologically conjugate. The homeomorphism preserves the sense of the orbits and is chosen to preserve parameterization by time.

The above theorem says that the qualitative properties of the nonlinear system $\dot{x}=F(x)$ in the vicinity (which is determined by the neighborhood $U$) of an isolated equilibrium $\bar{x}$ are determined by its linearization if the linearization has no eigenvalues on the imaginary axes in the complex plane. We also remark that Hartman-Grobman can also be applied to discrete time maps (cf. Sastry (1999, Thm. 2.18)) with the same qualitative outcome.

In proving results for stochastic gradient descent-ascent, we leverage what is known as the ordinary differential equation method in which the flow of the limiting continuous time system starting at sample points from the stochastic updates of the players actions is compared to asymptotic psuedo-trajectories—i.e., linear interpolations between sample points. To understand stability in the stochastic case, we need the notion of internally chain transitive sets. For more detail, the reader is referred to (Alongi and Nelson, 2007, Chap. 2–3).

Stability of Continuous Time GDA with Timescale Separation

To characterize the convergence of $\tau$-GDA, we begin by studying its continuous time limiting system

By analyzing the stability of the continuous time system as a function of the timescale separation $\tau$ using the Jacobian from (8) in this section, we can then draw conclusions about the stability and convergence of the discrete time system $\tau$-GDA in Section 4.

The organization of this section is as follows. To begin, we present a collection of preliminary observations in Section 3.1 regarding the stability of continuous time gradient descent-ascent with timescale separation to motivate the results in the subsequent subsections by establishing known results and introducing alternative analysis methods that the technical results in this paper build on. Then, in Sections 3.2 and 3.3 respectively, we present necessary and sufficient conditions for stability of the continuous time system around critical points in terms of the learning rate ratio along with sufficient conditions to guarantee the instability of the continuous time system around non-equilibrium critical points in terms of the timescale separation.

In Figure 1 we present a graphical representation of known results on the stability of gradient descent-ascent with timescale separation in continuous time, where we remark that such results nearly directly imply equivalent conclusions regarding the discrete time system $\tau$-GDA with a suitable choice of learning rate $\gamma_{1}$. The primary focus of past work has been on the edge cases of $\tau=1$ and $\tau\rightarrow\infty$. For $\tau=1$, the set of differential Nash equilibrium are stable, but differential Stackelberg equilibrium may be stable or unstable, and non-equilibrium critical points can be stable. As $\tau\rightarrow\infty$, the set of differential Nash equilibrium remain stable, each differential Stackelberg equilibrium is guaranteed to become stable, and each non-equilibrium critical point must be unstable. We fill the gap between the known results by providing results as a function of finite $\tau$. With an eye toward this goal, we now provide examples and preliminary results that illustrate the type of guarantees that may be achievable for a range of finite learning rate ratios.

To start off, we consider the set of differential Nash equilibrium. It is nearly immediate from the structure of the Jacobian that each differential Nash equilibrium is stable for $\tau=1$ (Mazumdar et al., 2020; Daskalakis and Panageas, 2018). Moreover, Jin et al. (2020) showed that regardless of the value of $\tau\in(0,\infty)$, the set of differential Nash equilibrium remain stable. In other words, the desirable stability characteristics of differential Nash equilibrium are retained for any choice of timescale separation. We state this result as a proposition for later reference and since our proof technique relies on the concept of quadratic numerical range (Tretter, 2008), which has not appeared previously in this context. The proof of Proposition 3.1 is provided in Appendix B.

Fiez et al. (2020) show that the set of differential Nash equilibrium is a subset of the set of differential Stackelberg equilibrium. In other words, any differential Nash equilibrium is a differential Stackelberg equilibrium, but a differential Stackelberg equilibrium need not be a differential Nash equilibrium. Moreover, Jin et al. (2020) show that the result of Proposition 3.1 fails to extend from differential Nash equilibria to the broader class of differential Stackelberg equilibrium. Indeed, not all differential Stackelberg equilibrium are stable with respect to the continuous time limiting dynamics of gradient descent-ascent without timescale separation. However, as the following example demonstrates, differential Stackelberg equilibrium that are unstable without timescale separation can become stable for a range of finite timescale learning rate ratios.

Within the class of zero-sum games, there exists differential Stackelberg equilibrium that are unstable with respect to $\dot{x}=-g(x)$ and stable with respect to $\dot{x}=-\Lambda_{\tau}g(x)$ for all $\tau\in(\tau^{\ast},\infty)$ where $\tau^{\ast}$ is finite. Indeed, consider the quadratic zero-sum game defined by the cost

We explore Example 1 further via simulations in Section 6.1. The key takeaway from Example 1 is that it is clearly not always necessary for the timescale separation $\tau$ to approach infinity in order to guarantee the stability of a differential Stackelberg equilibrium and instead there exists a sufficient finite learning rate ratio. Put simply, the undesirable property of differential Stackelberg equilibria not being stable with respect to gradient descent-ascent without timescale separation can potentially be remedied with only a finite timescale separation.

It is well-documented that some stable critical points of the continuous time gradient descent-ascent limiting dynamics without timescale separation can lack game-theoretic meaning, as they may be neither a differential Nash equilibria nor differential Stackelberg equilibria (Mazumdar et al., 2020; Daskalakis and Panageas, 2018; Jin et al., 2020). The following example demonstrates that such undesirable critical points that are stable without timescale separation can become unstable for a range of finite learning ratios.

Within the class of zero-sum games, there exists non-equilibrium critical points that are stable with respect to $\dot{x}=-g(x)$ and unstable with respect to $\dot{x}=-\Lambda_{\tau}g(x)$ for all $\tau\in(\tau_{0},\infty)$ where $\tau_{0}$ is finite. Indeed, consider a zero sum game defined by the cost

The game construction from (9) is quadratic and as a result has a unique critical point. Games can be constructed in which critical points lacking game-theoretic meaning that are stable without timescale separation become unstable for all $\tau>\tau_{0}$ even in the presence of multiple equilibria. Indeed, consider a zero-sum game defined by the cost

We investigate the game defined in (10) from Example 2 with simulations in Section 6.2. In an analogous manner to Example 1, Example 2 demonstrates that it is not always necessary for the timescale separation $\tau$ to approach infinity in order to guarantee non-equilibrium critical points become unstable as there can exist a sufficient finite learning rate ratio. This is to say that the unwanted property of non-equilibrium critical points being stable without timescale separation can also potentially be remedied with only a finite timescale separation.

The examples of this section have provided evidence that there exists a range of finite learning rate ratios for which differential Stackelberg equilibrium are stable and a range of learning rate ratios for which non-equilibrium critical points are unstable. Yet, no result has appeared in the literature on gradient descent-ascent with timescale separation confirming this behavior in general. We focus on doing precisely that in the subsection that follows. Before doing so, we remark on the closest existing result. As mentioned previously Jin et al. (2020) show that as $\tau\rightarrow\infty$, the set of stable critical points with respect to the dynamics $\dot{x}=-\Lambda_{\tau}g(x)$ coincide with the set of differential Stackelberg equilibrium. However, an equivalent result in the context of general singularly perturbed systems has been known in the literature (cf. Kokotovic et al. 1986, Chap. 2). We give a proof based on this type of analysis because it reveals a new set of analysis tools to the study of game-theoretic formulations of machine learning and optimization problems; a proof sketch is given below while the full proof is given in Appendix F.

The basic idea in showing this result is that there is a (local) transformation of coordinates from the linearized dynamics of $\dot{x}=-\Lambda_{\tau}g(x)$, which we write as

in a neighborhood of a critical point to an upper triangular system that depends parametrically on $\tau$ and hence, the asymptotic behavior is readily obtainable from the block diagonal components of the system in the new coordinates. Indeed, consider the change of variables $z=x_{2}+L(\tau^{-1})x_{1}$ for the second player so that

A transformation of coordinates $L(\tau)$ such that $R(L,\tau)=0$ always exists (cf. Lemma F.1, Appendix F). Hence, the characteristic equation of (11) can be expressed as

where $\chi_{s}(s,\tau)=\det(sI-(A_{11}-A_{12}L(\tau^{-1})))$ and $\chi_{f}(p,\tau)=\det(pI-(A_{22}+\tau^{-1}A_{12}L(\tau^{-1})))$ with $p=s\tau^{-1}$. As $\tau\to\infty$, $L(\tau^{-1})\to L(0)=-A_{22}^{-1}A_{12}^{\top}$. Consequently, $n$ of the eigenvalues of $\dot{x}=-\Lambda_{\tau}g(x)$, denoted by $\{\lambda_{1},\dots,\lambda_{n_{1}}\}$, are the roots of the slow characteristic equation $\chi_{s}(s,\tau)=0$ and the rest of the eigenvalues $\{\lambda_{n_{1}+1},\dots,\lambda_{n_{1}+n_{2}}\}$ are denoted by $\lambda_{i}=\nu_{j}/\varepsilon$ for $i=n_{1}+j$ and $j\in\{1,\dots,n_{2}\}$ where $\{\nu_{1},\dots,\nu_{n_{2}}\}$ are the roots of the fast characteristic equation $\chi_{f}(p,\tau)=0$. The roots of $\chi_{s}(s,\tau)$ are precisely those of the (first) Schur complement of $-J_{\tau}(x^{\ast})$ while the roots of $\chi_{f}(p,\tau)$ are precisely those of $D_{2}^{2}f(x^{\ast})$. ∎

This simple transformation of coordinates to an upper triangular dynamical system shown in (11) leads immediately to the asymptotic result in Proposition 3.2. It also shows that if the eigenavlues of ${\tt S}_{1}(J_{\tau}(x^{\ast}))$ are distinctDistinct eigenvalues is a generic property in the space of $n\times n$ real matrices. and similarly, so are those of $D_{2}^{2}f(x^{\ast})$ (although, ${\tt S}_{1}(J_{\tau}(x^{\ast}))$ and $D_{2}^{2}f(x^{\ast})$ are allowed to have eigenvalues in common), then the asymptotic results from Proposition 3.2 imply the following approximations for the elements of $\operatorname{spec}(J_{\tau}(x^{\ast}))$:

This follows simply by observing that when the eigenvalues are distinct, the derivatives $ds/d\tau$ and $dp/d\tau$ are well-defined by the implicit mapping theorem and the total derivative of $\chi_{s}(s,\tau)$ and $\chi_{f}(p,\tau)$, respectively.

2 Necessary and Sufficient Conditions for Stability

The proof of Proposition 3.2 provides some intuition for the next result, which is one of our main contributions. Indeed, as shown in Kokotovic et al. (1986, Chap. 2), as $\tau\rightarrow\infty$ the first $n_{1}$ eigenvalues of $\dot{x}=-\Lambda_{\tau}g(x)$ tend to fixed positions in the complex plane defined by the eigenvalues of $-{S}_{1}=-(D_{1}^{2}f(x^{\ast})-D_{12}f(x^{\ast})(D_{2}^{2}f(x^{\ast}))^{-1}D_{12}^{\top}f(x^{\ast}))$, while the remaining $n_{2}$ eigenvalues tend to infinity, with the linear rate $\tau$, along as asymptotes defined by the eigenvalues of $D_{2}^{2}f(x^{\ast})$. The asymptotic splitting of the spectrum provides some intuition for the following result.

Before getting into the proof sketch, we provide some intuition for the construction of $\tau^{\ast}$ and along the way revive an old analysis tool from dynamical systems theory which turns out to be quite powerful in analyzing stability properties of parameterized systems.

There is still the question of how to construct such a $\tau^{\ast}$ and do so in a way that is as tight as possible. Recall Theorem 2.1 which states that a matrix is exponentially stable if and only if there exists a symmetric positive definite $P=P^{\top}>0$ such that $PJ_{\tau}(x^{\ast})+J^{\top}_{\tau}(x^{\ast})P>0$. The operator $\mathcal{L}(P)=J_{\tau}^{\top}(x^{\ast})P+PJ_{\tau}(x^{\ast})$ is known as the Lyapunov operator. Given a positive definite $Q=Q^{\top}>0$, $-J_{\tau}(x^{\ast})$ is stable if and only if there exists a unique solution $P=P^{\top}$ to

so that if $x^{\ast}$ is a non-degenerate (a condition implied by the hyperbolicity of $x^{\ast}$ for ${S}_{1}$ and $D_{2}^{2}f(x^{\ast})$), $\det(-J_{\tau}(x^{\ast}))$ does not change the properties of the guard map. In particular, the values of $\tau\in(0,\infty)$ where $\nu(\tau)=0$ does not depend on $\det(-J_{\tau}(x^{\ast}))$. Hence, we can use the reduced guard map

Reflecting back to (12), we see that this guard map in $\tau$ is closely related to the vectorization of the Lyapunov operator and of course, this is not a coincidence. For any symmetric positive definite $Q=Q^{\top}>0$, there will be a symmetric positive definite solution $P=P^{\top}>0$ of the Lyapunov equation

The ‘necessary’ direction follows directly from the above observation, while the ‘sufficiency’ direction follows by construction.

In short, selecting the maximum value of $\tau^{\ast}$ over the finite set of equilibria guarantees that the local linearization of $\dot{x}=-\Lambda_{\tau}g(x)$ around any differential Stackelberg equilibria is stable, and hence, the nonlinear system is locally stable around each of these critical points.

Before moving on, we remark on the utility of the algebraic tools we use in the proof for Theorem 3.1. Indeed, the guard map concept is extremely powerful for understanding stability of parameterized families of dynamical systems, and it is not limited to single parameter families. Hence, there is potential to extend the above results to games with more than two players or additional parameters. In fact, we do exactly this in Section 5 where we present results for GANs trained with gradient-penalty type regularizers for the discriminator. Moreover, it is fairly easy to construct analogous guard maps for non-zero sum games. Many of the tools and constructions readily extend. We leave these results to a different paper so as to not create too much clutter in the present work.

3 Sufficient Conditions for Instability

Unlike $\tau^{\ast}$ Theorem 3.1, $\tau_{0}$ in Theorem 3.2 is not tight in the sense that $-J_{\tau}(x^{\ast})$ may become unstable for $\tau<\tau_{0}$. The reason for this is that there are potentially many matrices $P_{1}$ and $Q_{1}$ that satisfy ${\tt S}_{1}(J(x^{\ast}))P_{1}+P_{1}{\tt S}_{1}(J(x^{\ast}))=Q_{1}$ such that ${\tt S}_{1}(J(x^{\ast}))$ and $P_{1}$ have the same inertia; an analogous statement holds for $P_{2}$, $Q_{2}$ and $-D_{2}^{2}f(x^{\ast})$. The choice of these matrices impact the value of $\tau_{0}$. Hence, the question of finding the exact value of $\tau$ beyond which a spurious stable critical point for $1$-GDA is unstable remains open.

Provable Convergence of GDA with Timescale Separation

In this section, derive convergence guarantees for $\tau$-GDA to differential Stackelberg equilibria in both the deterministic (i.e., where agents have oracle access to their individual gradients) and the stochastic (i.e., where agents have an unbiased estimator of their individual gradient) settings.

As a corollary to Theorem 3.1, we first show that the discrete time $\tau$-GDA update is locally asymptotically stable for a range of learning rates $\gamma_{1}$.

We need the following lemma to prove asymptotic convergence as well as the subsequent results on convergence rates.

In addition to showing asymptotic convergence, we also provide an asymptotic convergence rate. To prove the main theorems on convergence rates for both differential Stackelberg and differential Nash equilibria, we use a common argument which is summarized in the lemma below.

The full proof of the above lemma is provided in Appendix C, and a short proof sketch with the main ideas is summarized below.

Consider a zero-sum game $(f,-f)$ as articulated in the lemma statement where $x^{\ast}$ is either a differential Stackelberg or differential Nash equilibrium and fix any $\tau$ such that $\operatorname{spec}(J_{\tau}(x^{\ast}))$.

For the discrete time dynamical system $x_{k+1}=x_{k}-\gamma_{1}\Lambda_{\tau}g(x_{k})$, it is well known that if $\gamma_{1}$ is chosen such that $\rho(I-\gamma_{1}J_{\tau}(x^{\ast}))<1$, then $x_{k}$ locally asymptotically converges to $x^{\ast}$ (cf. Proposition A.1, Appendix A). With this in mind, we formulate an optimization problem to find the upper bound $\gamma$ on the learning rate $\gamma_{1}$ such that for all $\gamma_{1}\in(0,\gamma)$, the spectral radius of the local linearization of the discrete time map is a contraction which is precisely $\rho(I-\gamma_{1}J_{\tau}(x^{\ast}))<1$. The optimization problem is given by

The above lemma provides a convergence rate given a differential Stackelberg equilibrium $x^{\ast}$ and a learning rate ratio $\tau$ such that $x^{\ast}$ is stable with respect to the dynamics $\dot{x}=-\Lambda_{\tau}g(x)$.

The following theorem—which uses Lemma 4.2 in its proof—characterizes the iteration complexity for $\tau$-GDA. Specifically, the result leverages Theorem 3.1 to construct a finite $\tau^{\ast}\in(0,\infty)$ such that $-J_{\tau}(x^{\ast})$ is (Hurwitz) stable, and then for any $\tau\in(\tau^{\ast},\infty)$, Lemma 4.2 implies a local asymptotic convergence rate.

is locally asymptotically (in fact, exponentially) stable by the Hartman-Grobman theorem (cf. Theorem 2.2). Therefore, for any $\tau\in(\tau^{\ast},\infty)$, by Lemma 4.2, $\tau$-GDA converges with a rate of $O((1-\tfrac{\alpha}{4\beta})^{k/2})$. ∎

Theorem 4.1 directly implies a finite time convergence guarantee for obtaining an $\varepsilon$-differential Stackelberg equilibrium—i.e., an point with an $\varepsilon$-ball around a differential Stackelberg $x^{\ast}$.

Given $\varepsilon>0$, under the assumptions of Theorem 4.1, $\tau$-GDA obtains an $\varepsilon$–differential Stackleberg equilibrium in $\lceil\tfrac{4\beta}{\alpha}\log(\|x_{0}-x^{\ast}\|/\varepsilon)\rceil$ iterations for any $x_{0}\in B_{\delta}(x^{\ast})$ with $\delta={\alpha/(4L\beta)}$ where $L$ is the local Lipschitz constant of $I-\gamma J_{\tau}(x^{\ast})$.

We note that we have essentially given a proof that there exists a neighborhood on which $\tau$-GDA converges. Of course, due to the non-convexity of the problem in general, this neighborhood could be arbitrarily small. We provide an estimate of the neighborhood size using the local Lipschitz constant of the local linearization $I-\gamma_{1}J_{\tau}(x^{\ast})$. One way to better understand the size of this neighborhood is to use Lyapunov analysis, a tool which is well explored in the singular perturbation theory (Kokotovic et al., 1986). In particular, Lyapunov methods can be applied directly to the nonlinear system if one can construct Lyapunov functions for the fast and slow subsystems individually—also known as the boundary layer model and reduced order model. With these Lyapunov functions in hand, one can “stitch” the two together (via convex combination) and show under some reasonable assumptions that this combined function is a Lyapunov function for the overall singularly perturbed system. The benefit of this analysis is that the Lyapunov function gives one an estimate of the region of attraction (via, e.g., the level sets); however, it is not easy to construct a Lyapunov function for a nonlinear system in general. We leave expanding to such methods to future work.

Before turning to the stochastic setting, we comment on saddle point avoidance in the deterministic setting. It was shown by Mazumdar et al. (2020) that gradient-based learning in continuous games with heterogeneous learning rates avoids saddles on all but a set of measure zero initializations. Hence, $\tau$-GDA avoids saddles for almost every initialization. We also know that all differential Nash equilibria are locally asymptotically stable for zero-sum settings. Hence, there are no differential Nash equilibria that are saddle points of the dynamics $\dot{x}=-\Lambda_{\tau}g(x)$. On the other hand, as Example 1 shows, there are differential Stackelberg equilibria which correspond to saddle points of the dynamics for some choices of $\tau$—in particular, $\tau=1$ in that example. Theorem 3.1 and Corollary 3.1, however, implies that for a given zero-sum game (or minmax problem), there exists a finite $\tau^{\ast}$ such that all locally asymptotically stable equilibria are differential Stackelberg equilibria. Hence, an ‘almost sure’ saddle point avoidance result together with the local convergence guarantee provided by Theorem 4.1 provides a strong characterization of long-run learning behavior.

Avoidance of saddles nor the if and only if convergence guarantee of Theorem 3.1 are, however, enough to ensure avoidance of limit cycles. In fact, it is known that limit cycles can exist in zero sum games (Daskalakis et al., 2018; Mazumdar et al., 2020). Understanding when such complex phenomena exist in games and determining how to ascribe meaning the behavior is an active area of study (see, e.g., the work of Papadimitriou and Piliouras (2019)).

2 Convergence of Stochastic GDA with Timescale Separation

In this section, we analyze convergence when players do not have oracle access to their gradients but instead have an unbiased estimator in the presence of zero mean, finite variance noise. Specifically, we show that the agents will converge locally asymptotically almost surely to a differential Stackelberg equilibrium.

The stochastic form of the update is given by

where $w_{k+1}$ is a zero mean, finite variance random variable and $\{\gamma_{k}\}$ is the learning rate sequence.

The stochastic process $\{w_{k}\}$ is a martingale difference sequence with respect to the increasing family of $\sigma$-fields defined by

We note that this assumption has been relaxed in the literature (cf. Thoppe and Borkar (2019)), however simplicity, we state the theorem with the most accessible criteria. We remark below in the paragraph on extensions to concentration bounds on the nature of the relaxed assumptions.

The convergence of $\{x_{k}\}$ to a, possibly sample path dependent, compact connected internally chain transitive invariant set of $\dot{x}=-\Lambda_{\tau}g(x)$ follows from classical results in stochastic approximation theory (cf. Borkar (2008, Chap. 2); Benaim (1996)).

While (local) almost sure convergence in gradient descent-ascent (Chasnov et al., 2019) to a critical pointTo date it has not been shown that for a sufficient separation in timescale the only critical point attractors are local minmax. in the stochastic setting, the result requires time varying learning rates with a sufficient separation in timescale. Specifically, the players need to be using learning rate sequences $\{\gamma_{i,k}\}$ for each $i\in\{1,2\}$ such that (without loss of generality) not only is it assumed that $\gamma_{1,k}=o(\gamma_{2,k})$, but also $\sum_{k}\gamma_{1,k}^{2}+\gamma_{2,k}^{2}<\infty$ and $\sum_{k}\gamma_{i,k}=\infty$ for each $i\in\{1,2\}$. The challenge with these assumptions on the learning rate sequences is that empirically the sequences that satisfy them result in poor behavior along the learning path such as getting stuck at saddle points or making no progress. This is, in essence, due to the fact that the faster player—i.e., player 2 if $\gamma_{1,k}=o(\gamma_{2,k})$—equilibriates too quickly causing progress to stall. This can result in undesirable behavior such as vanishing gradients (so that the discriminator does not provide enough information for the generator to make progress), mode collapse, or failure to converge in practical applications such as generative adversarial networks.

On the other hand, our convergence result gives a similar guarantee with less restrictive requirements on the stepsize sequence. In particular, only a single stepsize sequence is required (so that the algorithm can be viewed as a single timescale stochastic approximation update) as long as the fast player (who, without loss of generality, is player 2 in this paper) scales their estimated gradient by $\tau\in(\tau^{\ast},\infty)$ where $\tau^{\ast}$ is as in Theorem 3.1.

Furthermore, we note that in applications such as generative adversarial networks, while it has been observed that timescale separation heuristics such as unrolling or annealing the stepsize of the discriminator work well, in the stochastic case, summmable/square-summable assumptions on stepsizes are generally too restrictive in practice since they lead to a rapid decay in the stepsize which, in turn, can stall progress. On the other hand, stepsize sequences such as $\gamma_{k}=1/(k+1)^{\beta}$ for $\beta\in(0,1]$—a sequence which satisfies the assumptions posed in (Thoppe and Borkar, 2019)—tend not to have this issue of decaying too rapidly for appropriately chosen $\beta$, while also maintaining the guarantees of the theoretical results. We state a convergence guarantee under these relaxed assumptions in Proposition J.1 which is contained in Appendix J.

Regularization with Applications to Adversarial Learning

In this section, we focus on generative adversarial networks with regularization. Specifically, using the theory developed so far, we extend the results in Mescheder et al. (2018) to provide a convergence guarantee for a range of regularization parameters and learning rate ratios.

As has been repeatedly observed in recent theoretical works on generative adversarial networks, the training dynamics of generative adversarial networks are not well understood even though we have seen impressive practical advances over the last few years. In an attempt to address this, recent works—e.g., (Nagarajan and Kolter, 2017; Mescheder et al., 2017; Fiez et al., 2020; Berard et al., 2020) amongst others—study the optimization landscape of generative adversarial networks through the lens of dynamical systems theory which provides analysis tools for convergence based on the eigen-structure of the local linearization of the learning dynamics. Nagarajan and Kolter (2017) show, under suitable assumptions, that gradient-based methods for training generative adversarial networks are locally convergent assuming the data distributions are absolutely continuous. However, as observed by Mescheder et al. (2018), such assumptions not only may not be satisfied by many practical generative adversarial network training scenarios such as natural images, but it can often be the case that the data distribution is concentrated on a lower dimensional manifold. The latter characteristic leads to nearly purely imaginary eigenvalues and highly ill-condition problems.

Mescheder et al. (2018) provide an explanation for observed instabilities consequent of the true data distribution being concentrated on a lower dimensional manifold using discriminator gradients orthogonal to the tangent space of the data manifold. Further, the authors introduce regularization via gradient penalties that leads to convergence guarantees under less restrictive assumptions than were previously known. Here, we further extend these results to show that convergence to differential Stackelberg equilibria is guaranteed under a wide array of hyperparameter configurations.

Consider the training objective of the form

It is observed in Lemma 3.1 Mescheder et al. (2018) that GDA will not generally converge even with unrolling of the discriminator, a proxy for timescale separation. We observe, however, that this is because the equilibrium is not hyperbolic, and hence it is not structurally stable (Broer and Takens, 2010). In fact, introducing regularization remedies these issues. Under reasonable generative adversarial network assumptions, we show that the introduction of a gradient penalty based regularization to the discriminator does not change the set of critical points for the dynamics and, further, for any learning rate ratio $\tau\in(0,\infty)$ and any positive, finite regularization parameter $\mu$, the continuous time limiting regularized learning dynamics remain stable, and hence, there is a range of learning rates $\gamma_{1}$ for which the discrete time update locally converges asymptotically.

Gradient penalties ensure that the discriminator cannot create a non-zero gradient which is orthogonal to the data manifold without suffering a loss. Introduced by Roth et al. (2017) and refined in Mescheder et al. (2018), we consider training generative adversarial networks with one of two fairly natural gradient-penalties used to regularize the discriminator:

Also following Mescheder et al. (2018), we use relaxed assumptions—as compared to the work by Nagarajan and Kolter (2017)—which allow us to consider generative adversarial networks with data distributions that do not (locally) have the same support and hence, are concentrated on lower dimensional manifolds, a commonly observed phenomena in practice (Arjovsky et al., 2017).

The Jacobian of the regularized dynamics, for either $j=1$ or $2$, is of the form

It is straightforward to compute the block components of the Jacobian. Observe that Assumption 2.a implies that $D_{1}^{2}f(\theta^{\ast},\omega^{\ast})$ is identically zero, and hence $x^{\ast}=(\theta^{\ast},\omega^{\ast})$ is never a differential Nash equilibrium. However, we show that $x^{\ast}$ is not only a differential Stackelberg equilibrium, but also characterize the learning rate ratio and regularization parameter range for which $x^{\ast}$ is (locally) stable with respect to $\tau$-GDA and give a convergence rate.

To proof that $x^{\ast}$ is a differential Stackelberg equilibrium follows analogous arguments to those in the proof of Theorem 4.1 in Mescheder et al. (2018). Given any positive regularization parameter $\mu$, to prove the stability of $x^{\ast}$ for any fixed $\tau\in(0,\infty)$, we leverage the concept of the quadratic numerical range of a block operator which is a superset of the spectrum of the operator (cf. Appendix A). The key for both arguments is that Assumption 2 implies that the Jacobian of the regularized game has a specific structure. Indeed, observe that the structural form of $J_{(\tau,\mu)}(x^{\ast})$ is

The proof of the above corollary follows a similar line of reasoning as the proof of Corollary 4.1.

Theorem A.7 of Mescheder et al. (2018) shows that matrices of the form

are stable if $B$ is full rank and $C>0$. The following proposition provides necessary conditions on the sizes of the network architectures for the discriminator and generator network for stability.

Experiments

We now present extensive numerical experiments examining gradient descent-ascent with timescale separation. As we explored theoretically so far, the stability of gradient descent-ascent critical points has an intricate relationship with timescale separation. We begin to investigate this behavior empirically by simulating the gradient descent-ascent dynamics for the games from Examples 1 and 2 and examining how the spectrum of the game Jacobian evolves as a function of the timescale separation. Then, on a polynomial game, we demonstrate how timescale separation warps the vector field of gradient descent-ascent and consequently shapes the region of attraction around critical points in the optimization landscape. There are a number of both qualitative and quantitative theoretical questions that remain open related to characterizing the region of attraction and how it depends parameterically on $\tau$.

After exploring the optimization landscape, we focus in on gradient descent-ascent in the Dirac-GAN game and illustrate the interplay between timescale separation, regularization, and rate of convergence. Finally, we train generative adversarial networks on the CIFAR-10 and CelebA datasets with regularization and show timescale separation can significantly improve stability and performance. Moreover, we find that several of the insights we draw from the Dirac-GAN game carry over to this complex setting. Appendix L contains several more experimental results including a generative adversarial network formulation to learn a covariance matrix and a torus game. The code for our experiments is available at github.com/fiezt/Finite-Learning-Ratio.

We now revisit the game from Example 1 that demonstrated there exists differential Stackelberg equilibrium that are unstable for choices of the timescale separation $\tau$. To be clear, we repeat the game construction and some characteristics of the game. Let us consider the quadratic zero-sum game defined by the cost

For this experiment, we select $v=4$ and simulate $\tau$-GDA from the initial condition $(x_{1}^{0},x_{2}^{0})=(5,4,3,2)$ with $\gamma_{1}=0.0005$ and $\tau\in\{2,2.5,3,5,10\}$. In Figures 4a and 4b, we show the trajectories of the players coordinate pairs $(x_{11},x_{21})$ and $(x_{21},x_{22})$, respectively. We observe that $\tau$-GDA cycles around the equilibrium with $\tau=2$ since it is marginally stable with respect to the dynamics. For $\tau\in(2,\infty)$, the equilibrium is stable and $\tau$-GDA ends up converging to it at a rate that depends on the choice of $\tau$. We demonstrate how the convergence rate depends on the choice of $\tau$ in Figure 4c by showing the distance from the equilibrium along the learning path for each of the trajectories. The primary observation is that the cyclic behavior of $\tau$-GDA dissipates as $\tau$ grows and as a result the dynamics then rapidly converge to the equilibrium.

The behavior of the learning dynamics as a function of the timescale separation $\tau$ can be further explained by evaluating the eigenvalues of the game Jacobian at the equilibrium. We show the eigenvalues of the Jacobian at the equilibrium in several forms in Figures 4e, 4f, and 4g. Analyzing the spectrum, we are able to verify that for all $\tau\in(2,\infty)$ the equilibrium is indeed stable. Moreover, we see that the imaginary parts of the conjugate pairs of eigenvalues decay after $\tau=1$ and $\tau=6$, and then the eigenvalues of the conjugate pairs eventually become purely real at $\tau=1.87$ and $\tau=11.66$, respectively. After the eigenvalues of a conjugate pair become purely real, they split so that one of the eigenvalues asymptotically converges to an eigenvalue of ${\tt S}_{1}(J(x^{\ast}))$ by moving back along the real line, while the other eigenvalue tends toward an eigenvalue of $-\tau D_{2}^{2}f(x^{\ast})$. This occurrence is exactly what was described in Section 3 as an immediate implication of Proposition 3.2 when the eigenvalues of ${\tt S}_{1}(J(x^{\ast}))$ and $\tau D_{2}^{2}f(x^{\ast})$ are distinct. The convergence rate is in fact limited by the eigenvalues splitting since as $\tau$ grows, the spectrum of the Jacobian is limited by the eigenvalues of the Schur complement which remain constant. A related open question centers on finding the worst case convergence rate as a function of the spectral properties of ${\tt S}_{1}(J(x^{\ast}))$ and $D_{2}^{2}f(x^{\ast})$. Finally, the evolution of the eigenvalues as a function of the timescale separation $\tau$ demonstrates that the rotational dynamics in $\tau$-GDA vanish as the ratio between the magnitude of the real and imaginary parts of the eigenvalues grows.

2 Polynomial Game: Timescale Separation and Non-Equilibrium Stability

We now return to the game from Example 2 that showed a non-equilibrium critical point which is stable without timescale separation and becomes unstable for a range of finite learning ratios with multiple equilibria in the vicinity. Again, we repeat the game construction along with some of the key characteristics that were previously presented in Example 2. Consider a zero-sum game defined by the cost

This game has critical points at $(0,0,0,0)$, $(1,1,1,1)$, and $(-4.73,0.28,-92.47,0.53)$. Among the critical points, only $(1,1,1,1)$ and $(-4.73,0.28,-92.47,0.53)$ are game-theoretically meaningful equilibrium. In fact, they are each differential Nash equilibrium and are locally stable for any choice of $\tau\in(0,\infty)$ as a result of Proposition 3.1. On the other hand, the critical point $x^{\ast}=(0,0,0,0)$ is neither a differential Nash equilibrium nor a differential Stackelberg equilibrium. However, $x^{\ast}$ is stable for $\tau\in(0,2)$ and it is marginally stable for $\tau=2$. In general, convergence to the non-equilibrium critical point $x^{\ast}$ in the presence of multiple game-theoretically meaningful equilibrium would be viewed as undesirable. In fact, this is precisely the type of critical point that sophisticated schemes for converging to only differential Nash equilibria or only differential Stackelberg equilibria seek to avoid (Adolphs et al., 2019; Mazumdar et al., 2019; Wang et al., 2020; Fiez et al., 2020). We show in this example that the simple inclusion of timescale separation in gradient descent-ascent is sufficient to avoid $x^{\ast}$ and instead converge to a differential Nash equilibrium.

3 Polynomial Game: Vector Field Warping and Region of Attraction

Consider a zero-sum game defined by the cost

The cost structure of this game is visualized in Figure 6a, where we present a three dimensional view of $-f(x_{1},x_{2})$ along with the cost contours and the locations of critical points. This game has eleven critical points including one differential Nash equilibrium and two differential Stackelberg equilibria that are not a differential Nash equilibrium. The critical points that are neither a differential Nash equilibrium nor a differential Stackelberg equilibrium are unstable for any choice of timescale separation $\tau$. The differential Nash equilibrium is at $(x_{1},x_{2})=(10.57,-8.95)$ and it is stable for all $\tau\in(0,\infty)$ by Proposition 3.1. The differential Stackelberg equilibria are at $(x_{1},x_{2})=(-1.625,-1.625)$ and $(x_{1}^{\ast},x_{2}^{\ast})=(-11.03,-11.03)$; each is stable for all $\tau\in(1,\infty)$. We computed $\tau^{\ast}$ for the pair of differential Stackelberg equilibrium using the theoretical construction from Theorem 3.1 and observed that it properly recovered $\tau^{\ast}=1$ for each equilibrium as the timescale separation such that the continuous time system is stable for all $\tau\in(\tau^{\ast},\infty)$. Finally, we note that while the set of equilibrium follow a linear translation, this game is generic and the equilibria are in fact isolated.

In Figure 6b, we show the trajectories of $\tau$-GDA with $\gamma_{1}=0.0001$ and $\tau\in\{1,2,5,20\}$ given the initialization $(x_{1}^{0},x_{2}^{0})=(-9,-9)$ near the differential Stackelberg equilibrium at $(x_{1}^{\ast},x_{2}^{\ast})=(-11.03,-11.03)$. Moreover, in Figure 7a, we overlay the trajectories on the vector field generated by the respective timescale separation parameters. As expected, the choice of $\tau=1$ results in a trajectory that cycles around the equilibrium in a closed curve since it is marginally stable and $J_{\tau}(x^{\ast})$ has purely imaginary eigenvalues. Notably, as $\tau$ grows, the cyclic behavior dissipates as the timescale separation reshapes the vector field until the trajectory moves near directly to the zero derivative line of the maximizing player and then follows a path along that line toward the equilibrium and converges rapidly. The eigenvalues of $J_{\tau}(x^{\ast})$ as a function of $\tau$ are presented in Figures 6c and 6d. As was the case for the previous experiments, we observe that after the eigenvalues become purely real as $\tau$ grows, they then split and asymptotically converge toward the eigenvalues of ${\tt S}_{1}(J(x^{\ast}))$ and $-\tau D_{2}^{2}f(x^{\ast})$. It is worth noting that much of the rotational behavior in the dynamics and vector field disappears as a result of timescale separation well before the eigenvalues become purely real; this seems to occur after the timescale separation is such that the magnitude of the real part of the eigenvalues is greater than that of the imaginary part.

Finally, in Figure 7b, we demonstrate how the choice of timescale separation $\tau$ not only warps the vector field but also shapes the regions of attraction around critical points. The vector field is again shown for each $\tau\in\{1,2,5,20\}$, but now zoomed out to include each of the equilibria. The colors overlayed on the vector field indicate the equilibria that the dynamics converge to given an initialization at that position. Positions in the strategy space without color did not converge to an equilibrium in the fixed horizon of 75000 iterations with $\gamma_{1}=0.001$. This is explained by the fact that the dynamics are not guaranteed to be globally convergent and may get stuck in limit cycles or may simply move slowly for a long time in flat regions of the optimization landscape. We produced this experiment by running $\tau$-GDA for a dense set of initial conditions chosen uniformly over the space of interest. It is clear from the experiment that the choice of timescale separation determines not only the stability of equilibria, but also has a fundamental impact on the equilibria the dynamics converge to from a given initial condition as a result of the warping of the vector field. As a concrete example, given an initialization of $(x_{1},x_{2})=(-10,-2)$, the dynamics with $\tau=1$ converge to the differential Nash equilibria at $(x_{1},x_{2})=(10.57,-8.95)$. However, for any $\tau>1$, the dynamics instead converge to the differential Stackelberg equilibrium at $(x_{1},x_{2})=(-11.03,-11.03)$ that is significantly closer to the initial condition. This example motivates future work on methods for obtaining accurate estimates of the regions of attraction around critical points and techniques to design $\tau$ in order to explicitly shape the region of attraction around an equilibrium of interest. We refer to the end of Section 4.1 for further discussion on potentially relevant analysis methods in this direction.

4 Dirac-GAN: Regularization, Timescale Separation, and Convergence Rate

In Section 5, we studied gradient descent-ascent with regularization in generative adversarial networks and showed that the general theory we provide can be extended to such a formulation. Recall that the training objective for generative adversarial networks is of the form

The unique critical point of gradient descent-ascent is a local Nash equilibrium given by $(\theta^{\ast},\omega^{\ast})=(0,0)$. However, the structure of the game is such that

Mescheder et al. (2018) proposed to remedy the degeneracy issues of generative adversarial networks by using the following gradient penalties to regularize the discriminator with $\mu>0$:

The zero-sum game corresponding to the Dirac-GAN with regularization can be defined by the cost

The unique critical point of the game remains at $(\theta^{\ast},\omega^{\ast})=(0,0)$, but we now see that

From Figures 8a and 8d, we observe that the impact of timescale separation with regularization $\mu=0.3$ is that the trajectory is not as oscillatory since it moves faster to the zero line of $-D_{2}f(\theta,\omega)$ and then follows along that line until reaching the equilibrium. We further see from Figure 8b that with regularization $\mu=0.3$, $\tau$-GDA with $\tau=8$ converges faster to the equilibrium than $\tau$-GDA with $\tau=16$, despite the fact that the former exhibits some cyclic behavior in the dynamics while the latter does not. The eigenvalues of the Jacobian with regularization $\mu=0.3$ presented in Figure 8e explains this behavior since the imaginary parts are non-zero with $\tau=8$ and zero with $\tau=16$, but the eigenvalue with the minimum real part is greater at $\tau=8$ than at $\tau=16$. This example highlights that a degree of oscillatory behavior in the dynamics is not always harmful for convergence and it can even speed up the rate of convergence. Building off of this, for regularization $\mu=1$ and timescale separation $\tau=1$, Figures 8a and 8b show that even though $\tau$-GDA follows a direct path toward the equilibrium and does not cycle since the eigenvalues of the Jacobian are purely real, the trajectory converges slowly to the equilibrium. While not presented, we ran experiments with $\tau\in\{2,4,8,16\}$ with $\mu=1$ as well and timescale separation only made the convergence rate worse. The eigenvalues of the Jacobian with each regularization parameter presented in Figures 8e and 8f are able to explain this phenomenon. Indeed, for each regularization parameter, the eigenvalues split after becoming purely real and then converge toward the eigenvalues of ${\tt S}_{1}(J(\theta^{\ast},\omega^{\ast}))$ and $-\tau D_{2}^{2}f(\theta^{\ast},\omega^{\ast})$. Since ${\tt S}_{1}(J(\theta^{\ast},\omega^{\ast}))\propto 1/\mu$ and $-\tau D_{2}^{2}f(\theta^{\ast},\omega^{\ast})\propto\tau\mu$, there is a trade-off between the choice of regularization $\mu$ and the timescale separation $\tau$ on the conditioning of the Jacobian matrix. As shown in Figures 8e and 8f, the minimum real part of the eigenvalues with $\mu=0.3$ is significantly larger than with $\mu=1$ after sufficient timescale separation, which makes the convergence rate faster. Together, this example demonstrates that there may often be a delicate relationship between timescale separation, regularization, and convergence rate, where after a certain threshold each parameter choice may inhibit the rate of convergence.

5 Generative Adversarial Networks: Image Datasets

We now investigate the role timescale separation has on training generative adversarial networks parameterized by deep neural networks. The empirical benefits of training with a timescale separation have been documented previously. For example, Heusel et al. (2017) showed on a number of image datasets that a timescale separation between the generator and discriminator improves generation performance as measured by the Frechet Inception Distance (FID). Since then a significant number of papers have presented results training generative adversarial networks with timescale separation. Moreover, it is common in the literature for the discriminator to be updated multiple times between each update of the generator (Arjovsky et al., 2017). Indeed, it has been widely demonstrated that this heuristic improves the stability and convergence of the training process and locally it has a similar effect as including a timescale separation between the generator and discriminator. The disadvantage of this approach is that the number of gradient calls per generator update increases and consequently the convergence is then slower in terms of wall clock time when a similar effect could potentially be achieved by a learning rate separation between the generator and discriminator. We remark that it appears to be reasonably common for practitioners to fix a shared learning rate for the generator and discriminator along with a pre-selected number of discriminator updates per generator update and not thoroughly investigate the impact timescale separation has on the training process.

The goal of our generative adversarial network experiments is to reinforce the importance of the timescale separation between the generator and the discriminator as a hyperparameter in the training process, demonstrate how it changes the behavior along the learning path, and show that it is compatible with a number of common training heuristics. This is to say that our goal is not necessarily to show state-of-the art performance, but rather to perform experiments that allow us to make insights relevant to the theory in this paper. We remark that our empirical work on training generative adversarial networks is distinct from and complimentary to that of Heusel et al. (2017) in several ways. The theory given by Heusel et al. (2017) only applies to stochastic stepsizes, however in the experiments they implemented constant step sizes. We train with mini-batches and decaying stepsizes, which does satisfy the theory we provide. Moreover, by and large, the experiments by Heusel et al. (2017) compare a fixed learning rate ratio between the generator and discriminator to multiple fixed shared learning rates for the generator and discriminator. In contrast, we fix a learning rate for the generator and explore the behavior of the training process as the timescale parameter $\tau$ is swept over a given range.

We build our experiments based on the methods and implementations of Mescheder et al. (2018) and explore both the CIFAR-10 and CelebA image datasets. We train the generative adversarial networks with the non-saturating objective function and the $R_{1}$ gradient penalty proposed by Mescheder et al. (2018) with regularization parameters $\mu\in\{1,10\}$. We note that the non-saturating objective results in a game that is not zero-sum, however it is commonly used in practice and under the realizable assumptions is it locally equivalent to the zero-sum objective as discussed at the end of Section 6.4. The network architectures for the generator and discriminator are both based on the ResNet architecture. The initial learning rate for the generator in all of our experiments is fixed to be $\gamma=0.0001$ and we decay the stepsizes so that at update $k$ the learning rate of the generator is given by $\gamma_{1,k}=\gamma_{1}/(1+\nu)^{k}$ where $\nu=0.005$ and the learning rate of the discriminator is $\gamma_{2,k}=\tau\gamma_{1,k}$. For each experiment the batch size is $64$, the latent data is drawn from a standard normal distribution of dimension $256$, and the resolution of the images is $32\times 32\times 3$. Finally, as an optimizer, we run RMSprop with parameter $\alpha=0.99$. Again, the theory we provide does not strictly apply to using RMSprop, but it is ubiquitous in practice for training generative adversarial networks and if the timescale separation is sufficiently large so that the eigenvalues are purely real in the Jacobian then the theory we provide is applicable as remarked previously. We provide further details on the network and hyperparameters in Appendix L.4. A final heuristic and hyperparameter that we explore in conjunction with the timescale separation $\tau$ is that of using an exponential moving average to produce the model that is evaluated. This means that at each update $k$, given that the parameters of the generator are given by $x_{1,k}$, the moving average $\bar{x}_{k}=x_{1,k}\beta+\bar{x}_{1,k-1}(1-\beta)$ is kept where $\beta\in(0,1)$. Experimental studies have shown that this heuristic can yield a significant improvement in terms of both the inception score and the FID (Yazici et al., 2019; Gidel et al., 2019a). The success of this method is thought to be a result of dampening both rotational dynamics and the noise from the randomness in the mini-batches of data.

We run the training algorithm with the learning rate ratio $\tau$ belonging to the set $\{1,2,4,8\}$ and the regularization parameter $\mu$ belonging to the set $\{1,10\}$. For each choice of $\tau$ and $\mu$, we retain exponential moving averages of the generator parameters for $\beta\in\{0.99,0.999,0.9999\}$. The training process is repeated $3$ times for each hyperparameter configuration to rule out noise from random seeds and the performance is evaluated along the learning path at every 10,000 updates in terms of the FID score. We report the mean scores and the standard error of the mean over the repeated experiments. We run the experiments with $\mu=1$ for 150k mini-batch updates and the experiments with $\mu=10$ for 300k mini-batch updates.

The results for each dataset across the hyperparameter configurations are presented in numeric form in Figure 12. Figure 11 shows some generated samples selected at random for each dataset with the hyperparameter configuration that performed best in terms of the FID score at the end of the training process. Figure 17 in Appendix L.4 has several more generated samples for each dataset selected at random. We now describe the key observations from the experiments for each dataset.

The FID scores along the learning path for CIFAR-10 with $\mu=10$ and $\mu=1$ are presented in Figures 9a and 9b, respectively. The corresponding scores in numeric form are given in Figures 12a, 12c, and 12e for $\mu=10$ at 150k iterations and $\mu=1$ at 150k and 300k iterations, respectively. To begin, we observe that the exponential moving average significantly improves performance, and of the parameters considered, $\beta=0.9999$ performed best. Relevant to this work, we observe that the performance gain from using an exponential moving average appears to be maximized when the ratio of learning rates is smallest. This may indicate that some of the dynamics in $\tau$-GDA are dampened by timescale separation in this generative adversarial network experiment, similarly to as observed for the simpler experiments presented previously. Moreover, we that timescale separation also has a significant impact on the FID score of the training process. Indeed, even selecting $\tau=2$ versus $\tau=1$ can yield an impressive performance gain. In this experiment for each regularization parameter, $\tau=4$ converges fastest, followed by $\tau=8$, then $\tau=2$, and finally $\tau=1$. Finally, observe that the performance with regularization $\mu=1$ is far superior to that with regularization $\mu=10$. Interestingly, the last pair of conclusions are in line with the insights drawn from the simple Dirac-GAN experiment in Section 6.4. In particular, timescale separation only speeds up to convergence until hitting a limiting value and there is a fundamental interplay between timescale separation, regularization, and convergence rate. This indicates that it may be possible to transfer some of the insights made on simple generative adversarial network formulations to the much more complex problem where players are parameterized by neural networks.

The FID scores along the learning path for CIFAR-10 with $\mu=10$ and $\mu=1$ are presented in Figures 10a and 10b, respectively. The corresponding scores in numeric form are given in Figures 12b, 12d, and 12f for $\mu=10$ at 150k iterations and $\mu=1$ at 150k and 300k iterations, respectively. In this experiment we that while the exponential moving average helps performance, the gain is not as drastic as it was for CIFAR-10. However, timescale separation in combination with the regularization does have a major effect on the the FID score of the training process in this experiment. For regularization $\mu=10$, the timescale parameters of $\tau=2$ and $\tau=4$ outperform $\tau=1$ and $\tau=8$ by a wide margin, again highlighting that timescale separation can speed up convergence until a certain point where it can potentially slow it down owing to the effect on the conditioning of the problem locally. A similar trend can be observed with regularization $\mu=1$, but with $\tau=8$ performing closer to $\tau=2$ and $\tau=4$. We again observe in this experiment that for all timescale separation parameters, the performance is significantly improved with regularization $\mu=1$ as compared with $\mu=10$. This once again highlights the importance of considering how this the hyperparameters of regularization and timescale interact and dictate the local convergence rates.

In summary, we took a well-performing method and implementation for training generative adversarial networks and demonstrated that timescale separation is an extremely important, and easy to implement, hyperparameter that is worth careful consideration since it can have a major impact on the convergence speed and final performance of the training process.

Related Work

In this section, we provide a review of related work at the intersection machine learning and game theory, as well as connections to dynamical systems theory and control.

Given the extensive work on the topic of learning in games in machine learning that has gone on over the last several years, we cannot cover all of it and instead focus our attention on only the most relevant to this paper. We begin by reviewing solution concepts developed for the class of games under consideration and then discuss some learning dynamics studied in the literature beyond gradient descent-ascent. Following this, we delineate the related work studying gradient descent-ascent in non-convex, non-concave zero-sum games and finish by making note of the literature on non-convex, concave optimization.

Owing to the numerous applications in machine learning, a significant portion of the modern work on learning in games has focused on the zero-sum formulation with non-convex, non-concave cost functions. Most recently, Daskalakis et al. (2020) tout the importance and significance of this class of games in a paper on the complexity of finding equilibria (in particular, in the constrained setting) in such games. Consequently, local solution concepts have been broadly adopted. Compared to the standard game-theoretic notions of equilibrium that characterize player’s incentive to deviate given the game and information structure, local equilibrium concepts restrict the deviation search space to a suitable local neighborhood. Following the standard game-theoretic viewpoint, a vast number of works in machine learning study the local Nash equilibrium concept and critical points satisfying gradient-based sufficient conditions for the equilibrium, which are often referred to as differential Nash equilibria (Ratliff et al., 2013, 2014, 2016). Based on the observation that in non-convex, non-concave zero-sum games the order of play is fundamental in the definition of the game, there has been a push toward considering local notions of the Stackelberg equilibrium concept, which is the usual game-theoretic equilibrium when there is an explicit order of play between players. In the zero-sum formulation, Stackelberg equilibrium are often referred to as minmax equilibria. Similar to as for the Nash equilibrium, gradient-based sufficient conditions for local minmax/Stackelberg equilibrium have been given (Fiez et al., 2020; Jin et al., 2020; Daskalakis and Panageas, 2018) and such critical points have been referred to as differential Stackelberg equilibria (Fiez et al., 2020). We remark that it has been shown that local/differential Nash equilibria are a subset of local/differential Stackelberg equilibria (Jin et al., 2020; Fiez et al., 2020). Following past works, we adopt the terminology of differential Nash equilibrium and differential Stackelberg equilibrium in this paper as the meaning of strict local Nash equilibrium and strict local minmax/Stackelberg equilibrium, respectively. Finally we mention the proximal equilibria proposed by Farnia and Ozdaglar (2020), which we do not consider in this work, that depending on a regularization parameter can interpolate between the local Nash and local Stackelberg equilibrium notions.

Given that the focus of this work is on gradient descent-ascent, we center our coverage of related work on papers analyzing its behavior. Nonetheless, we mention that a significant number of learning dynamics for zero-sum games have been developed in the past few years, in some cases motivated by the shortcomings of gradient descent-ascent without timescale separation. The methods include optimistic and extra-gradient algorithms (Daskalakis et al., 2018; Gidel et al., 2019a; Mertikopoulos et al., 2019), negative momentum (Gidel et al., 2019b), gradient adjustments (Mescheder et al., 2017; Balduzzi et al., 2018; Letcher et al., 2019a), and opponent modeling methods (Zhang and Lesser, 2010; Metz et al., 2017; Foerster et al., 2018; Letcher et al., 2019b; Schäfer and Anandkumar, 2019), among others. While the aforementioned learning dynamics possess some desirable characteristics, they cannot guarantee that the set of stable critical points coincide with a set of local equilibria for the class of games under consideration. However, there have been a select few learning dynamics proposed that can guarantee the stable critical points coincide with either the set of differential Nash equilibria (Adolphs et al., 2019; Mazumdar et al., 2019) or the set of differential Stackelberg equilibria (Fiez et al., 2020; Wang et al., 2020)—effectively solving the problem of guaranteeing local convergence to only a class of local equilibria. However, since each of the algorithms achieving the equilibrium stability guarantee require solving a linear equation in each update step, they are not efficient and can potentially suffer from degeneracies along the learning path in applications such as generative adversarial networks. These practical shortcomings motivate either proving that existing learning dynamics using only first-order gradient feedback achieve analogous theoretical guarantees or developing novel computationally efficient learning dynamics that can match the theoretical guarantee of interest.

Gradient descent-ascent has been studied extensively in non-convex, non-concave zero-sum games since it is a natural analogue to gradient descent from optimization, is computationally efficient, and has been shown to be effective in practice for applications of interest when combined with common heuristics. A prevailing approach toward gaining understanding of the convergence characteristics of gradient descent-ascent has been to analyze the local stability around critical points of the continuous time limiting dynamical system. The majority of this work has not considered the impact of timescale separation. Numerous papers have pointed out that the stable critical points of gradient descent-ascent without timescale separation may not be game-theoretically meaningful. In particular, it has been shown that there can exist stable critical points that are not differential Nash equilibrium (Daskalakis and Panageas, 2018; Mazumdar et al., 2020). Furthermore, it is known that there can exist stable critical points that are not differential Stackelberg equilibria (Jin et al., 2020). The aforementioned results rule out the possibility that gradient descent-ascent without timescale separation can guarantee equilibrium convergence. In terms of the stability of equilibria, it is known that differential Nash equilibrium are stable for gradient descent-ascent without timescale separation (Daskalakis and Panageas, 2018; Mazumdar et al., 2020), but that there can exist differential Stackelberg equilibria which are not stable with respect to gradient descent-ascent without timescale separation.

The work of Jin et al. (2020) is the most relevant exploring how the aforementioned stability properties of gradient descent-ascent change with timescale separation. In particular, Jin et al. (2020) investigate whether the desirable stability characteristics (stability of differential Nash equilibria) and undesirable stability characteristics (stability of non-equilibrium critical points and instability of differential Stackelberg equilibria) of gradient descent without timescale separation are maintained and remedied, respectively with timescale separation. In terms of the former query, extending the examples shown in Mazumdar et al. (2020) and Daskalakis and Panageas (2018), Jin et al. (2020) show that differential Nash equilibrium are stable for gradient descent-ascent with any amount of timescale separation.

On the other hand, for the latter query, Jin et al. (2020) shows (in Proposition 27) two interesting examples: (a) for an a priori fixed $\tau$, there exists a game with a differential Stackelberg equilibrium that is not stable and (b) for an a priori fixed $\tau$, there exists a game with a stable critical point that is not a differential Stackelberg equilibrium. However, (a) does not imply that for the constructed game, there does not exist another (finite) $\tau$—independent of the game parameters—such the differential Stackelebrg equilibrium is stable for all larger $\tau$. In simple language, the result summarized in (a) says the following: if a bad timescale separation is chosen, then convergence may not be guaranteed. Similarly, (b) does not imply that there is no $\tau$ such that for all larger $\tau$ for the constructed game instance, the critical point becomes unstable. Again, in simple language, the result summarized in (b) says the following: if a bad timescale separation is chosen, then non-game theoretically meaningful equilibria may persist. While at first glance this set of results may appear to indicate that the undesirable stability characteristics of gradient descent without timescale separation cannot be averted by any finite timescale separation, it is important to emphasize that these results do not answer the questions of whether there (a) exists a game with a critical point that is not a differential Stackelberg equilibrium which is stable with respect to gradient descent-ascent without timescale separation and remains stable for all finite timescale separation ratios or (b) exists a game with a differential Stackelberg equilibrium that is not stable for all finite timescale separation ratios. The preceding questions are left open from previous work and are exactly the focus of this paper. In Appendix K, we go into greater detail on the comparison between Proposition 27 of Jin et al. (2020) as we believe this to be an important point of distinction between Theorem 3.1 and 3.2 in this paper.

Finally, Jin et al. (2020) study the an infinite timescale separation ratio and show that the stable critical points of gradient descent-ascent coincide with the set of differential Stackelberg equilibria in this regime. This result effectively shows that gradient descent-ascent can guarantee only equilibrium convergence with timescale separation, albeit infinite. We remark that an equivalent result in the context of general singularly perturbed systems has been known in the literature (Kokotovic et al., 1986, Chap. 2) as we discuss further in Section 3.1. Finally, we point out that since an infinite timescale separation does not result in an implementable algorithm, fully understanding the behavior with a finite timescale separation is of fundamental importance and the motivation for our work.

Beyond the work of Jin et al. (2020) considering timescale separation in gradient descent-ascent, it is worth mentioning the work of Chasnov et al. (2019) and Heusel et al. (2017). Chasnov et al. (2019) study the impact of timescale separation on gradient descent-ascent, but focus on the convergence rate as a function of it given an initialize around a differential Nash equilibrium and do not consider the stability questions examined in this paper. Heusel et al. (2017) study stochastic gradient descent-ascent with timescale separation and invoke the results of Borkar (2008) for analysis. The stochastic approximation results the claims rely on guarantee the convergence of the system locally to a stable critical point. Consequently, the claim of convergence to differential Nash equilibria of stochastic gradient descent-ascent given by Heusel et al. (2017) only holds given an initialization in a local neighborhood around a differential Nash equilibrium. In this regard, the issue of the local stability of the types of critical point is effectively assumed away and not considered. In contrast, we are able to combine our stability results for gradient descent-ascent with timescale separation together with the stochastic approximation theory of Borkar (2008) to guarantee local convergence to a differential Stackelberg equilibrium in Section 4.2. We remark that Heusel et al. (2017) empirically demonstrate that timescale separation can significantly improve the performance of gradient descent-ascent when training generative adversarial networks.

The final relevant line of work studying gradient descent-ascent is specific to generative adversarial networks. The results from this literature develop assumptions relevant to generative adversarial networks and then analyze the stability and convergence properties of gradient descent-ascent under them (see, e.g., works by Metz et al. (2017); Goodfellow et al. (2014); Daskalakis et al. (2018); Nagarajan and Kolter (2017); Mescheder et al. (2018)). Within this body of work, there has been a significant amount of effort focusing on how the stability (and, hence, convergence properties) of gradient descent-ascent in generative adversarial networks can be enhanced with regularization methods. Nagarajan and Kolter (2017) show, under suitable assumptions, that gradient-based methods for training generative adversarial networks are locally convergent assuming the data distributions are absolutely continuous. However, as observed by Mescheder et al. (2018), such assumptions not only may not be satisfied by many practical generative adversarial network training scenarios such as natural images, but it can often be the case that the data distribution is concentrated on a lower dimensional manifold. The latter characteristic leads to nearly purely imaginary eigenvalues and highly ill-condition problems. Mescheder et al. (2018) provide an explanation for observed instabilities consequent of the true data distribution being concentrated on a lower dimensional manifold using discriminator gradients orthogonal to the tangent space of the data manifold. Further, the authors introduce regularization via gradient penalties that leads to convergence guarantees under less restrictive assumptions than were previously known. In this paper, we further extend these results to show that convergence to differential Stackelberg equilibria is guaranteed under a wide array of hyperparameter configurations (i.e., learning rate ratio and regularization).

2 Historical Perspective: Dynamical Systems and Control

The study of gradient descent-ascent dynamics with timescale separation between the minimizing and maximizing players is closely related to that of singularly perturbed dynamical systems (Kokotovic et al., 1986). Such systems arise in classical control and dynamical systems in the context of physical systems that either have multiple states which evolve on different timescales due to some underlying immutable physical process or property, or a single dynamical system which evolves on a sub-manifold of the larger state-space. For example, robot manipulators or end effectors often have have slower mechanical dynamics than electrical dynamics. On the other hand, in electrical circuits or mechanical systems, certain resistor-capacitor circuits or spring-mass systems have a state which evolves subject to a constraint equation (Sastry and Desoer, 1981; Lagerstrom and Casten, 1972). Due to their prevalence, singularly perturbed systems have been studied extensively with one of the outcomes being a number of works on determining the range of perturbation parameters for which the overall system is stable (Kokotovic et al., 1986; Saydy et al., 1990; Saydy, 1996). We exploit these results and analysis techniques to develop novel results for learning in games. One of contributions of this work is the introduction of the algebraic analysis techniques to the machine learning and game theory communities. These tools open up new avenues for algorithm synthesis; we comment on potential directions in the concluding discussion section.

This being said, there are a couple key difference between the present setting and that of the classical literature including the following:

The perturbation parameter is no longer an immutable characteristic of the physical system, but rather a hyperparameter subject to design. Indeed, in singular perturbation theory, the typical dynamical system studied takes the form

where the $x$–player seeks to minimize $f$ with respect to $x$ and the $y$–player seeks to maximize $f$ with respect to $y$, and $\tau$ is the ratio of learning rates (without loss of generality) of the maximizing to the minimizing player. These learning rates—and hence the value of $\tau$—are hyperparameters subject to design in most machine learning and optimization applications. Another feature of (27) as compared to (26), is that the dynamics $D_{i}f$ are partial derivatives of a function $f$, which leads to the second key difference.

There is structure in the dynamical system that arises from gradient-play which reflects the underlying game theoretic interactions between players. This structure can be exploited in obtaining convergence guarantees in machine learning and optimization applications of game theory. For instance, minmax optimization is analogous to a zero sum game for which the local linearization of gradient descent-ascent dynamics has the structure

where $A=A^{\top}$ and $C=C^{\top}$ and $\tau$ is the learning rate ratio or timescale separation parameter. Such block matrices have very interesting properties. In particular, second order optimality conditions for a minmax equilibrium correspond to positive definiteness of the first Schur complement ${\tt S}_{1}(J)=A-BC^{-1}B^{\top}>0$, and of $-C>0$ (Fiez et al., 2020). This turns out to be keenly important for understanding convergence of gradient descent-ascent. Furthermore, due to the structure of $J$, tools from the theory of block operators (see, e.g., works by Tretter (2008); Magnus (1988); Lancaster and Tismenetsky (1985)) such as the quadratic numerical range can be exploited (and combined with singular perturbation theory) to understand the effects of hyperparameters such as $\tau$ (the learning rate ratio) and regularization (which is common in applications such as generative adversarial networks) on convergence.

Discussion

In this paper, we prove a necessary and sufficient condition for the convergence of gradient descent-ascent with timescale separation to differential Stackelberg equilibria in zero sum games. This answers a long standing open question about provable convergence of first order methods for zero-sum games to local minimax equilibria. Specifically, we provide necessary and sufficient conditions for the convergence of $\tau$-GDA to differential Stackelberg equilibria. A key component of the proof is the construction of a (tight) finite lower bound on the learning rate ratio $\tau$ for which stability of the game Jacobian is guaranteed, and hence local asymptotic convergence of $\tau$-GDA. In addition, we provide results on iteration complexity and convergence rate and apply the results to generative adversarial networks under mild assumptions on the data distribution. For both differential Nash equilibira and the superset of differential Stackelberg equilibria, we provide estimates on the neighborhood on which convergence is guaranteed.

This being said, the question of the size of the region of attraction remains open. As commented on earlier in the paper, an alternative but related technique tackles the nonlinear system directly. The downside of this technique is that one needs to have in hand (or be able to construct) Lyapunov functions for both the boundary layer model (i.e., the system that arises from treating the choice variable of the slow player as being ‘static’) and the reduced order model (i.e., the system that arises from plugging in the implicit mapping from the fast player’s action to the slow player’s action into the slow player’s dynamics). A convex combination of these functions provides a Lyapunov function for the original system $\dot{x}=-\Lambda_{\tau}g(x)$. The level sets of this combined Lyapunov function then give a better sense of the region of attraction and, in fact, one can optimize over the weighting in the convex combination in order to obtain better estimates of the region of attraction. This is an interesting avenue to explore in the context of learning in games with lots of intrinsic structure that can potentially be exploited to improve both the rate of convergence and the region on which convergence is guaranteed.

Another significant contribution of this work is the fact that we introduce tools that are arguably new to the machine learning and optimization communities and expose interesting new directions of research. In particular, the notion of a guard map, which is arguably even an obscure tool in modern control and dynamical systems theory, is ‘rediscovered’ in this paper. The is potential to leverage this concept in not only providing certificates for performance (e.g., beyond stability to robustness) but also in synthesizing algorithms with performance guarantees. For instance, one observation from our empirical analysis is that convergence rate is not only limited by the eigenvalues of the Schur complement of the Jacobian, but the fastest convergence appears to occur when there are complex components of the eigenvalues. In short, some cycling is beneficial. Better understanding this fact from a theoretical perspective is an open question, as is optimizing the rate of convergence by exploiting these observations.

Finally, another set of related open questions center on practical considerations for the efficient use of first order methods. For instance, with respect to generative adversarial networks, the exponential moving average is known to empirically reduce the negative effects of cycling. Additionally, increasing the learning rate ratio does lead to predominantly real eigenvalues which in turn reduces cycling. Understanding the trade offs between not only these two hyperparameters but also regularization is very important for practical implementations. Empirically, we study the tradeoffs between the learning rate ratio, regularization parameter, and the parameter controlling the degree of “smoothness” in the exponential moving average, another common heuristic that performs well in practice. There is an open line of research related to analytically characterizing the tradeoffs between these three hyperparameters. However, in the absence of theoretical tools for exploring these issues, what are reasonable and principled heuristics?

To conclude, while we arguably definitively address a standing open question for first order methods for learning in zero-sum games/minmax optimization problems, there a many open directions exposed by the tools introduced and empirical observations discovered in this work.

Acknowledgements

This work is funded by the Office of Naval Research (YIP Award) and National Science Foundation CAREER Award (CNS-1844729). Tanner Fiez is also funded by a National Defense Science and Engineering Graduate Fellowship. We thank Daniel Calderone for the helpful discussions, in particular on linear algebra results as they pertain to the results in this paper. Finally, we thank Mescheder et al. (2018) for providing a high quality open source implementation of the generative adversarial network experiments they performed, which facilitated and expedited the experiments we performed.

References

Appendix A Helper Lemmas and Additional Mathematical Preliminaries

In this appendix, we present a handful of technical lemmas and review some additional mathematical preliminaries excluded from the main body but which are important in proving the results in the paper.

The following technical lemma is used in proving an upper bound on the spectral radius of the linearization of the discrete time update $\tau$-GDA a requirement for obtaining the convergence rate results.

The function $c(z)=(1-z)^{1/2}+\tfrac{z}{4}-(1-\tfrac{z}{2})^{1/2}$ satisfies $c(x)\leq 0$ for all $z\in$.

Since $c(0)=0$ and $c(1)=\tfrac{1}{4}-\tfrac{1}{\sqrt{2}}\leq 0$, we simply need to show that $c^{\prime}(z)\leq 0$ on $(0,1)$ to get that $c(z)$ is a decreasing function on $$, and hence negative on$$. Indeed, $c^{\prime}(z)=\tfrac{1}{4}+\tfrac{1}{2\sqrt{4-2z}}-\tfrac{1}{2\sqrt{1-z}}\leq 0$ since $(1-z)^{-1/2}-(4-2z)^{-1/2}\geq 1/2$ for all $z\in(0,1)$. ∎

The following proposition is a well-known result in numerical analysis and can be found in a number of books and papers on the subject. Essentially, it provides an asymptotic convergence guarantee for a discrete time update process or dynamical system.

Let $x^{\ast}$ be a fixed point for the discrete dynamical system $x_{k+1}=F(x_{k})$. If the spectral radius of the Jacobian satisfies $\rho(DF(x^{\ast}))<1$, then $F$ is a contraction at $x^{\ast}$ and hence, $x^{\ast}$ is asymptotically stable.

The following technical lemma, due to Mustafa and Davidson (1994), is used in constructing the finite learning rate ratio.

For completeness (and because there is a typo in the original manuscript), we provide the proof here.

Suppose that $V$ and $Y-XV^{-1}W$ are non-singular so that the partial Schur decomposition

Applying the determinant operator, we have that

Combining (28) with (31) in (29) gives exactly the claimed result. ∎

The following lemma is Theorem 2 Lancaster and Tismenetsky (1985, Chap. 13.1). We use this lemma several times in the proofs of Theorem 3.1 and 3.2 so we include it here for ease of reference. For a given matrix $A$, $\upsilon_{+}(A)$, $\upsilon_{-}(A)$, and $\zeta(A)$ are the number of eigenvalues of the argument that have positive, negative and zero real parts, respectively.

If $P$ is a symmetric matrix such that $AP+PA^{\top}=Q$ where $Q=Q^{\top}>0$, then $P$ is nonsingular and $P$ and $A$ have the same inertia—i.e.,

On the other hand, if $\zeta(A)=0$, then there exists a matrix $P=P^{\top}$ and a matrix $Q=Q^{\top}>0$ such that $AP+PA^{\top}=Q$ and $P$ and $A$ have the same inertia (i.e., (32) holds).

The quadratic numerical range of $A$ is defined by

where $\operatorname{spec}(\cdot)$ denotes the spectrum of its argument.

The quadratic numerical range can be described as the set of solutions of the characteristic polynomial

for $v\in W_{1}$ and $w\in W_{2}$. We use the notation $\langle Av,w\rangle=\bar{v}^{\top}Aw$ to denote the inner product. Note that $\mathcal{W}^{2}(A)$ is a (potentially non-convex) subset of $\mathcal{W}(A)$ and contains $\operatorname{spec}(A)$.

Appendix B Proof of Proposition 3.1

Before proving this result, we note that the result has already been shown in the literature by Jin et al. (2020). We included the result primarily because the proof approach is different and the tools we use (in particular, the quadratic numerical range) have not been utilized before in this type of analysis. Hence, we view the proof technique itself as a contribution.

Then, the elements of $\mathcal{W}^{2}(J_{\tau}(x^{\ast}))$ are of the form

where $a=\langle D_{1}^{2}f(x^{\ast})v,v\rangle$, $b=\langle D_{12}f(x^{\ast})w,v\rangle$ and $d=\langle-D_{2}^{2}f(x^{\ast})w,w\rangle$ for vectors $v\in W_{1}$ and $w\in W_{2}$.

We claim that for any $\tau\in(0,\infty)$, $\text{Re}(\lambda_{\tau})>0$ for all $a$,$b$, and $d$ where $a>0$ and $d>0$ since $x^{\ast}$ is a differential Nash equilibrium.

Indeed, we argue this by considering the two possible cases: (1) $(a-\tau d)^{2}\leq 4|b|^{2}\tau$ or (2) $(a-\tau d)^{2}>4\tau|b|^{2}$.

Case 1: Suppose $\tau\in(0,\infty)$ is such that $(a-\tau d)^{2}\leq 4|b|^{2}\tau$. Then, $\text{Re}(\lambda_{\tau})=\tfrac{1}{2}(a+\tau d)>0$ trivially since $a+d>0$.

Case 2: Suppose $\tau\in(0,\infty)$ is such that $(a-\tau d)^{2}>4\tau|b|^{2}$. In this case, we want to ensure that

The last inequality is equivalent to $-ad<|b|^{2}$. Indeed,

Moreover, $-ad<|b|^{2}$ holds for any pair of vectors $(v,w)$ such that $v\in W_{1}$ and $w\in W_{2}$ since $a>0$ and $d>0$.

Appendix C Proof of Lemma 4.1 and Lemma 4.2

In this appendix section, we prove Lemma 4.1 and Lemma 4.2 from Section 4. We note that the proof of Lemma 4.2 starts where the proof of Lemma 4.1 leaves off.

as claimed. From this argument, it is clear that for any $\gamma_{1}\in(0,\gamma)$, $|1-\gamma_{1}\lambda|<1$ for all $\lambda\in\operatorname{spec}(J_{\tau}(x^{\ast}))$.

Hence, the $\rho(I-\gamma_{1}J_{\tau}(x^{\ast}))<1$ so that an application of Proposition A.1 gives us the desired result.

C.2 Proof of Lemma 4.2

To prove this lemma, we build directly on the conclusion of the proof of Lemma 4.1. Indeed, since

given $\varepsilon=\tfrac{\alpha}{4\beta}>0$ there exists a norm $\|\cdot\|$ (cf. Lemma 5.6.10 in Horn and Johnson (1985))The norm that exists can easily be constructed as essentially a weighted induced $1$-norm. Note that the norm construction is not unique. The proof in Horn and Johnson (1985) is by construction and the construction of this norm can be found there. such that

where the last inequality holds by Lemma A.1. Taking the Taylor expansion of $I-\gamma_{1}g_{\tau}(x)$ around $x^{\ast}$, we have

where $R_{2}(x-x^{\ast})$ is the remainder term satisfying $R_{2}(x-x^{\ast})=o(\|x-x^{\ast}\|)$ as $x\rightarrow x^{\ast}$.The notation $R_{2}(x-x^{\ast})=o(\|x-x^{\ast}\|)$ as $x\rightarrow x^{\ast}$ means $\lim_{x\rightarrow x^{\ast}}\|R_{2}(x-x^{\ast})\|/\|x-x^{\ast}\|=0$. This implies that there is a $\delta>0$ such that $\|R_{2}(x-x^{\ast})\|\leq\frac{\alpha}{8\beta}\|x-x^{\ast}\|$ whenever $\|x-x^{\ast}\|<\delta$. Hence,

where the last inequality holds again by Lemma A.1. Hence,

whenever $\|x_{0}-x^{\ast}\|<\delta$ which verifies the claimed convergence rate.

Appendix D Proof of Corollary 4.2

Let $\|\cdot\|$ be the norm that exists (via construction a la Horn and Johnson (1985, Lem. 5.6.10)) in the proof of Lemma 4.2 which is given in Appendix C. Following standard arguments, (35) in the proof of Lemma 4.2 implies a finite time convergence guarantee. Indeed, let $\varepsilon>0$ be given. Since $0<\tfrac{\alpha}{4\beta}<1$ we have that $(1-\alpha/(4\beta))^{k}<\exp(-k\alpha/(4\beta))$. Hence,