Global Convergence to Local Minmax Equilibrium in Classes of Nonconvex Zero-Sum Games
Year: 2022

Abstract:
We study gradient descent-ascent learning dynamics with timescale separation (τ -GDA) in unconstrained continuous action zero-sum games where the minimizing player faces a nonconvex optimization problem and the maximizing player optimizes a Polyak-Łojasiewicz (PŁ) or strongly-concave (SC) objective. In contrast to past work on gradient-based learning in nonconvex-PŁ/SC zero-sum games, we assess convergence in relation to natural game-theoretic equilibria instead of only notions of stationarity. In pursuit of this goal, we prove that the only locally stable points of the τ -GDA continuous-time limiting system correspond to strict local minmax equilibria in each class of games. For these classes of games, we exploit timescale separation to construct a potential function that when combined with the stability characterization and an asymptotic saddle avoidance result gives a global asymptotic almost-sure convergence guarantee for the discrete-time gradient descent-ascent update to a set of the strict local minmax equilibrium. Moreover, we provide convergence rates for the gradient descent-ascent dynamics with timescale separation to approximate stationary points.

heading: 1 Introduction
text: We study continuous action zero-sum games of the form
min x∈X max y∈Y f(x, y)
where f ∈ C2(X × Y,R) and X = Rd1 and Y = Rd2 denote the individual action spaces and d = d1 + d2. In particular, we focus on unconstrained, continuous strategy space zero-sum games in which f(·, y) is potentially nonconvex in x ∈ X and f(x, ·) satisfies the Polyak-Łojasiewicz (PŁ) condition [47] or is strongly-concave (SC) in y ∈ Y . We refer to these classes of games as nonconvex-PŁ and nonconvex-SC zero-sum games, respectively.
This general formulation has a broad spectrum of applications such as fair classification [45], distributionally robust optimization [44, 48, 53], and adversarial training [38]. Consequently, there has been a surge of interest in recent years toward developing methods for solving these problems efficiently. So far, existing work on gradient-based learning in nonconvex-PŁ/SC zero-sum games has exclusively focused on providing global convergence rates to approximate stationary points with no attention given to the characterization in terms of game-theoretic equilibrium concepts [33, 34, 36, 45, 48, 62].
In contrast, a common theme in the study of general nonconvex-nonconcave zero-sum games is to assess the types of stationary points an algorithm locally converges toward in terms of their higher
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
order structure [10, 15, 16, 23, 40, 41, 58, 64]. The purpose of this analysis is generally to determine whether commonly deployed algorithms can guarantee local convergence to only game-theoretic equilibria or to design algorithms that achieve this objective.
The goal of this paper is to close the gap between the two problem classes and determine whether gradient-based learning algorithms in nonconvex-PŁ/SC zero-sum games can be shown to globally converge to only game-theoretically meaningful equilibria (local minmax/Stackelberg or Nash). We focus our attention on the canonical gradient descent-ascent learning dynamics with timescale separation between players. In this algorithm, timescale separation is manifested in the different (yet constant) learning rates of the maximizing and minimizing players. The description of this system, which we refer to as τ -GDA, where the ratio of learning rates denoted by τ > 0 parameterizes the timescale separation between players, is provided in Algorithms 1–2 for deterministic and stochastic settings respectively. Simply put, τ -GDA (Algorithm 1) corresponds to each player following their individual gradient in a noiseless setting, while stochastic τ -GDA (Algorithm 2) describes each player following their individual stochastic gradient. The τ -GDA update only requires first-order gradients and thus is a computationally efficient method for machine learning problems formulated as games.

heading: 1.1 Contributions
text: We show that τ -GDA has global convergence guarantees in nonconvex-PŁ/SC zero-sum games to the natural game-theoretic solution concept for this problem class of strict local minmax equilibria.1 The specific contributions of this work are now summarized.
1) In Theorem 1, we prove the only critical points that are locally stable with respect to the τ -GDA continuous-time limiting system are strict local minmax equilibrium in nonconvex-PŁ/SC zerosum games. A key implication of this is that any critical point which is not a strict local minmax equilibrium is a saddle point of the continuous-time limiting system.
2) In Theorem 2, we combine Theorem 1 with a potential function construction (Lemma 1) and an asymptotic saddle avoidance result (Lemma 2) to prove that the τ -GDA update in deterministic settings (Algorithm 1) globally asymptotically converges to strict local minmax equilibria almost surely in the class of nonconvex-PŁ/SC zero-sum games.
3) In Corollary 1, using the potential function from Lemma 1, we show that τ -GDA in deterministic settings reaches an ε-critical point in Õ(ε−2) steps in nonconvex-PŁ/SC zero-sum games. Moreover, specific to nonconvex-SC zero-sum games, Lemma 3 shows there exists learning rates for τ -GDA such that the cost function of the game itself can be made a potential. Corollary 2 then uses the potential function from Lemma 3 to show that τ -GDA reaches an ε-critical point in Õ(ε−2) and Õ(ε−6) steps in deterministic and stochastic problems, respectively.
Prior to moving on, we briefly comment on and provide context for each contribution of this paper. As we discuss later on in Remark 1, beyond its importance toward proving Theorem 2, Theorem 1 is potentially of independent interest given the implications it also has for the local stability of τ -GDA around critical points in the more general setting of nonconvex-nonconvave zero-sum games. Furthermore, to our knowledge, Theorem 2 provides the broadest existing global convergence guarantee for gradient-based algorithms to game-theoretically meaningful equilibria in zero-sum continuous games. Finally, while there exists known convergence rates for gradient-based learning algorithms to ε-critical points in nonconvex-PŁ/SC zero-sum games, we are unaware of such a result in nonconvex-PŁ zero-sum games for τ -GDA, and the fact that we derive a rate in nonconvex-SC zero-sum games using the cost function itself as a potential function has practical implications given that it can easily be monitored when running the algorithm to evaluate progress toward a solution.

heading: 1.2 Practical Motivation
text: The study of nonconvex-PŁ/SC zero-sum games has often been motivated by machine learning problems formulated as games. We remark that given the problem formulations, it is natural from both game-theoretic and machine learning perspectives to seek notions of minmax equilibria. Indeed, notions of stationarity are not guaranteed to reflect a meaningful solution to the underlying problem. Consequently, it is critical to give convergence guarantees to minmax equilibrium as we pursue in
1Strict local minmax equilibria characterized by gradient-based sufficient conditions are also known as differential Stackelberg equilibria in the literature [15, 16] and we use the terms interchangeably in this work.
this work. We now provide examples from the literature of machine learning applications that are relevant to the class of games studied in this paper. Note that the following application problems are illustrative in nature and do not immediately fall into the classes of games we study. However, as is elaborated on shortly, each of the problems can be transformed into unconstrained nonconvex-PŁ/SC zero-sum games while retaining the optimization objectives after simple, standard modifications. Example 1. In fair classification [45] and learning from multiple distributions, the objective is to minimize the maximum loss over multiple categories. An example formulation is the problem
minw∈Rd maxi∈{1,...,K} `i(w)
where `i(w) represents the loss on category i with w denoting neural network parameters. A reformulation of this problem [45] with T is the simplex in RK is given by the zero-sum game
minw∈Rd maxt∈T ∑N i=1 ti`i(w). (1)
Example 2. To train a neural network classifier robust against adversarial attacks, a common approach is to formulate training as a robust minmax optimization problem of the form
minw∈Rd ∑N i=1 maxδi:|δi|∞≤ `(xi + δi, yi, w),
where `(xi + δi, yi, w) represents the loss on sample xi perturbed by δi with budget and label yi as a function of the parameter weights w [38]. A reformulation of this problem [45] is given by
minw∈Rd ∑N i=1 maxt∈T ∑K j=1 tj`(x̂ij , yi, w) (2)
where x̂ij is the result of a targeted attack on the sample xi seeking to change the output of the network to label j and T is the simplex in RK . Example 3. Distributionally robust optimization often results in a zero-sum game of the form
minw∈Rd maxt∈T ∑N i=1 ti`i(w)− r(t) (3)
where `i(x) is the loss of a model w on the i–th data point, T is the simplex in RN , and r(t) is carefully selected convex regularizer [44, 48, 53].
The machine learning problem formulations in (1)–(3) from Examples 1–3 represent nonconvexconcave zero-sum games in which the strategy space of the minimizing player is unconstrained and the strategy space of the maximizing player is constrained to the simplex. These problems are naturally adapted to the unconstrained nonconvex-PŁ/SC zero-sum game setting considered in this paper by removing the constraint on the strategy space of the maximizing player and including a suitable PŁ/SC regularization penalty on the choice variable of the maximizing player.

heading: 1.3 Organization
text: The rest of the paper is organized as follows. Section 2 details related work and Section 3 presents game-theoretic, mathematical, and algorithmic preliminaries for our results. Section 4 is devoted to studying the local stability properties around critical points of the continuous-time limiting system for the τ -GDA learning dynamics. In Section 5, we present our study of the convergence properties of τ -GDA in nonconvex-PŁ/SC zero-sum games. We conclude with a discussion in Section 6. Finally, the supplementary material (appendix) contains the proofs of theoretical results.

heading: 2 Related Work
text: We now cover the most relevant related work with further discussion provided in Appendix A.
Nonconvex-Nonconcave Zero-Sum Games. A common theme in analyzing gradient descent-ascent with or without timescale separation in nonconvex-nonconcave zero-sum games has been to assess the local stability around critical points of the continuous-time limiting system and draw connections to local Nash and Stackelberg equilibrium notions characterized by gradient-based sufficient conditions (see Definition 4) [10, 15, 16, 23, 40, 42, 43, 63]. Importantly, it has been shown that unless the timescale separation is chosen very carefully, the stable critical points of gradient descent-ascent may not be game-theoretically meaningful and game-theoretically meaningful critical points may
not be stable [15, 23]. We obtain stronger stability characterizations (see Theorem 1) for τ -GDA in nonconvex-PŁ/SC zero-sum games using the structure imposed on the game cost function. The result of Theorem 1 also has novel implications for the local stability of τ -GDA around critical points in the more general setting of nonconvex-nonconvave zero-sum games (see Remark 1). Moreover, it is fundamental toward proving the global almost sure asymptotic convergence guarantee for τ -GDA in deterministic settings to strict local minmax equilibria in nonconvex-PŁ/SC zero-sum games (Theorem 2). Further discussion of this topic is given in Section 4.
Nonconvex-PŁ and Nonconvex-SC Zero-Sum Games. Table 1 provides a comprehensive comparison between our convergence results and existing convergence results for gradient descent variants in nonconvex optimization and nonconvex-PŁ/SC zero-sum games. We leave discussion of research on these classes of games with other algorithmic methods to Appendix A. The key distinction between this paper and past work is that instead of assessing convergence in terms of only reaching an approximate stationary point of the dynamics or a surrogate function, we obtain convergence guarantees in regards to differential Stackelberg equilibria (equivalently strict local minmax equilibria). Despite this being a much stricter and meaningful notion of solving the problem, Theorem 2 shows that global asymptotic convergence guarantees for τ -GDA in deterministic settings to this type of solution remain obtainable in nonconvex-PŁ/SC zero-sum games. This is the main result of the paper. While we do not prove a rate of convergence to differential Stackelberg equilibria or an approximate notion, Corollary 1 shows τ -GDA in deterministic settings with parameter choices satisfying the conditions of Theorem 2 reaches an ε-critical point in Õ(ε−2) steps in nonconvex-PŁ/SC zero-sum games. We are unaware of an existing rate for τ -GDA in deterministic settings in nonconvex-PŁ zero-sum games. Finally, as a complementary result, Lemma 3 shows there exists learning rates for τ -GDA such that the cost function of the game itself can be made a potential in nonconvex-SC zero-sum games, which is a desirable property given that this potential function can be monitored while running the algorithm. Corollary 2 then uses this potential function to show that τ -GDA reaches an ε-critical point in Õ(ε−2) and Õ(ε−6) steps in deterministic and stochastic nonconvex-SC zero-sum games, respectively. Escaping Saddle Points. Saddle avoidance results for variants of gradient descent in nonconvex optimization are asymptotic or finite-time. The former states that almost surely the algorithm does not converge to saddles points [28, 29], while the latter gives rates of escape to conclude convergence to approximate local minimum [17, 20, 24]. A primary assumption in the aforementioned works is what is known as the strict saddle property, which ensures directions of escape exists from a saddle point. The methods for showing gradient descent escapes saddle points almost surely in nonconvex optimization have more recently been extended to gradient descent-ascent in the setting of continuous games under an analogous strict saddle assumption [10, 40]. A key component of proving the global asymptotic convergence guarantee to strict local minmax for τ -GDA turns out to be ensuring that the
update escapes saddle points of the continuous-time limiting system almost surely. To show this property holds for τ -GDA in nonconvex-PŁ/SC zero-sum games, we are able to invoke existing saddle avoidance results for gradient-based learning in continuous games [40].

heading: 3 Preliminaries
text: In the zero-sum games we study, we refer to the minimizing player controlling x as player 1 and the maximizing player controlling y as player 2. The set of players is denoted by I = {1, 2}. We consider objective functions f ∈ C2(Z,R) where the joint strategy space is denoted by Z = X × Y where X = Rd1 and Y = Rd2 denote the individual action spaces and d = d1 + d2. We often denote a joint strategy using the shorthand notation z = (x, y) ∈ Z = X × Y . Notation. We denote∇f as the total derivative of f , ∇if as the derivative of f with respect to the choice variable of player i, ∇ijf as the partial derivative of∇if with respect to the choice variable of player j, and ∇2i f as the partial derivative of ∇if with respect to the choice variable of player i. We let ‖ · ‖ denote the 2-norm of vectors unless otherwise specified, spec(·) denote the set of eigenvalues of a matrix, Re(·) denote the real part of a complex number, and C◦− and C◦+ denote the open left-half and right-half complex plane, respectively. Let λmin(A) denote the eigenvalue of A with the minimum real part, and λmax(A) the eigenvalue of A with the maximum real part. Finally, we indicate A is positive and negative definite using the notation A 0 and A ≺ 0, respectively. Classes of Games. We study and analyze both nonconvex-PŁ and nonconvex-SC zero-sum games. To begin, we state a standard smoothness assumption that is needed throughout. Assumption 1. Given a zero-sum game (f,−f) defined by f ∈ C2(Z,R),∇1f(x, y) and∇2f(x, y) are L1 and L2 Lipschitz, respectively. That is, ∀ x, x′ ∈ X , y, y′ ∈ Y ,
‖∇1f(x, y)−∇1f(x′, y′)‖ ≤ L1(‖x− x′‖+ ‖y − y′‖), ‖∇2f(x, y)−∇2f(x′, y′)‖ ≤ L2(‖x− x′‖+ ‖y − y′‖).
This assumption immediately implies that the vector of individual gradients denoted by
g(x, y) := (∇1f(x, y),−∇2f(x, y))
is also Lipschitz with parameter L = L1 + L2.
We now define a nonconvex-PŁ zero-sum game [45]. This class of games allows for the objective to be nonconvex in x ∈ X , but it needs to satisfy the Polyak-Łojasiewicz (PŁ) condition [47] in y ∈ Y . Definition 1 (Nonconvex-PŁ Game). Consider a zero-sum game (f,−f) defined by f ∈ C2(Z,R). The game is called nonconvex-PŁ if f(x, ·) is µ-PŁ with respect to the argument y ∈ Y . That is, for µ > 0 and for all z = (x, y) ∈ Z ,
‖∇2f(x, y)‖2 ≥ 2µ(maxy′∈Y f(x, y′)− f(x, y)),
where for any fixed x ∈ X , maxy′∈Y f(x, y′) has a nonempty solution set and a finite optimal value.
In nonconvex-PŁ zero-sum games, the solution set of argmaxy′∈Y f(x ∗, y′) for any fixed x∗ ∈ X may not be a singleton and the maximizing player’s objective may be nonconcave. However, by Definition 1 it follows immediately that any (x∗, y∗) such that ‖∇2f(x∗, y∗)‖ = 0 satisfies f(x∗, y∗) = maxy′∈Y f(x ∗, y′) so any stationary point with respect to y is a global maximum.
The following provides a definition for what we call a nonconvex-SC zero-sum game. In this class of games, the function that defines the game may be nonconvex in x ∈ X , but it must be SC in y ∈ Y . Definition 2 (Nonconvex-SC Game). Consider a zero-sum game (f,−f) defined by f ∈ C2(Z,R). The game is nonconvex-SC if f(x, ·) is µ-SC with respect to the argument y ∈ Y . That is, given any x ∈ X and for all y, y′ ∈ Y ,
f(x, y′) ≤ f(x, y) + 〈∇2f(x, y), y′ − y〉 − µ
2 ‖y′ − y‖22.
It is important to note that nonconvex, µ-SC zero-sum games are nonconvex, µ-PŁ zero-sum games, but nonconvex-PŁ zero-sum games may not be nonconvex-SC zero-sum games, which follows from the relationship between PŁ and SC functions [25]. This is to say that the class of nonconvex-PŁ
Algorithm 1 τ -GDA
Input: x0 ∈ Rd1 , y0 ∈ Rd2 for k = 0, 1, . . . do xk+1 ← xk − γ∇1f(xk, yk) yk+1 ← yk + γτ∇2f(xk, yk) end for
Algorithm 2 Stochastic τ -GDA
Input: x0 ∈ Rd1 , y0 ∈ Rd2 for k = 0, 1, . . . do xk+1 ← xk − γg1(xk, yk; θ1,k) yk+1 ← yk + γτg2(xk, yk; θ2,k) end for
zero-sum games is a superset of the class of nonconvex-SC zero-sum games. Thus, results we state for nonconvex-PŁ zero-sum games immediately hold for nonconvex-SC zero-sum games.
Learning Dynamics. We study gradient descent-ascent with timescale separation. Let γ be the learning rate of player 1 and τ > 0 be the timescale parameterization so that the learning rate of player 2 is given by τγ. The deterministic τ -GDA dynamics are presented in Algorithm 1 and the stochastic τ -GDA dynamics are given in Algorithm 2 (see Section 5.2 for the relevant notation). The key distinction between this study of gradient descent-ascent with timescale separation and past work is how we assess convergence as we now begin to formalize.
Stationarity Notions. We call critical points strategy profiles at which the individual gradient of each player is equal to zero; that is (x, y) ∈ Z such that ∇1f(x, y) = 0 and ∇2f(x, y) = 0. Critical points correspond to stationary points of the τ -GDA dynamics. The nonconvex-PŁ/SC zero-sum game literature has generally assessed convergence in terms of the complexity of finding an ε-critical point (see, e.g., [45, 62]). We formally define an ε-critical point now for later reference.
Definition 3 (ε-Critical Point.). The joint strategy (x∗, y∗) ∈ Z is an ε-critical point when the conditions ‖∇1f(x∗, y∗)‖ ≤ ε and ‖∇2f(x∗, y∗) ≤ ε hold.
A closely related and common notion of convergence in this body of work (see e.g., [33]) is that of finding an ε-critical point of the function maxy∈Y f(·, y). This criterion amounts to seeking to achieve the condition ‖∇1 maxy∈Y f(x, y)‖ ≤ ε. In contrast, we assess convergence with connections to the equilibrium notions that are commonly studied in the nonconvex-nonconcave zero-sum game literature. Since either stationarity notion may lack any game-theoretic meaning, we consider a strictly harder notion of solving a game.
Equilibrium Notions. The typical solution concept in game theory when an implicit or explicit order of play is present in the structure of the game is the (local) Stackelberg (equivalently minmax in zero-sum games) equilibrium concept [6].2 Informally, in nonconvex-PŁ/SC zero-sum games, a local minmax equilibrium corresponds to a strategy pair (x∗, y∗) ∈ Z such that x∗ is a local minimum of the function f(x, y∗(x)) where y∗(x) ∈ argmaxy∈Y f(x, y) is a local maximum of the function f(x∗, y). When the function f is bounded or when f(·, y) is bounded and f(x, ·) is strongly concave, a minmax equilibrium is guaranteed to exist.
We characterize the local minmax (Stackelberg) equilibrium notion in terms of sufficient conditions on player costs as is typical in learning in games (see, e.g., [15, 16, 23, 40, 58, 64]). Toward presenting this definition, we denote by J(x, y) the Jacobian of the individual gradient vector g(x, y) given by
J(x, y) = [ ∇21f(x, y) ∇12f(x, y) −∇>12f(x, y) −∇22f(x, y) ] . (4)
Let S1(·) denote the Schur complement of (·) with respect to the d2 × d2 block in (·). The following definition is characterized by sufficient conditions for a local minmax equilibrium in zero-sum games.
Definition 4 (Differential Stackelberg/Strict Local Minmax Equilibrium [16, 23]). The joint strategy (x∗, y∗) ∈ Z is a differential Stackelberg equilibrium when the conditions ∇1f(x∗, y∗) = 0, ∇2f(x∗, y∗) = 0 and S1(J(x∗, y∗)) 0, ∇22f(x∗, y∗) ≺ 0 hold.
We remark that in nonconvex-PŁ/SC zero-sum games, S1(J(x∗, y∗)) as in Definition 4 is well-defined at any critical point (x∗, y∗) since det(∇22f(x∗, y∗)) 6= 0 (see Lemma 8 in Appendix B.3).
2By implicit order of play, we mean the min and max order are not interchangeable.

heading: 4 Local Stability Analysis
text: To characterize the convergence of τ -GDA, we begin by studying its continuous-time limiting system
ż = −Λτg(z) (5) where ż = (ẋ, ẏ), Λτ = blockdiag(Id1 , τId2), and g(z) is the vector of individual gradients. The Jacobian of this system is given by Jτ (z) = ΛτJ(z). (6) We analyze the stability of the continuous-time system around critical points z∗ = (x∗, y∗) as a function of the timescale separation τ using the Jacobian Jτ (z∗) in this section toward drawing conclusions about the stability and convergence of the discrete time system τ -GDA. A critical point is said to be locally (exponentially) stable when the spectrum of−Jτ (z∗) is in the open left-half complex plane C◦− (cf. Theorem 3, Appendix B.2). Simply put, a critical point z∗ is locally exponentially stable if and only if the real parts of the eigenvalues of −Jτ (z∗) are strictly negative. Throughout, we use the broader term “stable" to mean the following. Definition 5 (Stability). A critical point z∗ = (x∗, y∗) ∈ Z is locally exponentially stable for ż = −Λτg(z) if and only if spec(−Jτ (z∗)) ⊂ C◦− (≡ spec(Jτ (z∗)) ⊂ C◦+).
Stability with respect to the continuous-time τ -GDA dynamics guarantees that the system asymptotically converges at an exponential rate to the critical point in a local neighborhood. Moreover, given a suitable choice of learning rates, equivalent insights hold for the discrete-time dynamics [8].
Stability in Nonconvex-Nonconcave Zero-Sum Games. Given the implications regarding convergence, a number of papers in the past several years study the stability of τ -GDA around critical points and the connections to differential Nash and Stackelberg equilibrium in zero-sum games [10, 15, 16, 23, 40]. However, this body of research focuses on general nonconvex-nonconcave zero-sum games. In general across the spectrum of nonconvex-nonconcave zero-sum games, the stable critical points of τ -GDA coincide with the set of differential Stackelberg equilibria only when the timescale separation τ →∞ [23]. Given that such a choice of timescale separation requires the learning rate γ → 0 in order to retain stability of the discrete-time system, it is not clear how to derive a practical algorithm from this insight.
Toward remedying this problem, Fiez and Ratliff [15] provide stability results in terms of the timescale separation concerning a given critical point, rather than across the space of nonconvexnonconcave zero-sum games. In particular, they prove a stability and instability result as a function of the timescale separation in the τ -GDA dynamics. The stability results say that given a differential Stackelberg equilibrium z∗, there exists a finite τ∗ ∈ (0,∞) that can be constructed such that z∗ is stable for all τ ∈ (τ∗,∞). On the other hand, the instability results says that given a critical point which is not a differential Stackelberg equilibrium, there exists a finite τ0 ∈ (0,∞) that can be constructed such that z∗ is not stable for all τ ∈ (τ0,∞). Stability in Nonconvex-PŁ/SC Zero-Sum Games. To our knowledge, the connection between the stability (and instability) of critical points with respect to τ -GDA dynamics and game-theoretic equilibrium notions in the semi-structured problems of nonconvex-PŁ and nonconvex-SC zero-sum games has not been fully characterized. We show in the following result that when a nonconvexnonconcave game is specialized to a nonconvex-PŁ zero-sum game as from Definition 1, significantly more general stability characterizations can be obtained by exploiting the fact that ∇22f(x∗, y∗) ≺ 0 at any critical point z∗ = (x∗, y∗) (see Lemma 8 in Appendix B.3). Notably, any critical point z∗ = (x∗, y∗) that is not a differential Stackelberg equilibrium is not stable (“unstable”) for all τ > 0. In other words, τ -GDA does not admit spurious stable points in nonconvex-PŁ zero-sum games. This is in stark contrast to the known fact that 1-GDA admits spurious stable points in the more general class of nonconvex-nonconcave games as has been shown in previous literature [10, 23, 40]. Moreover, if z∗ is a differential Stackelberg equilibrium, then z∗ is stable for all τ larger than the minimum τ∗ for which z∗ is stable and such a finite τ∗ is guaranteed to exist. This result implies that in practice, one can select a finite value of τ to run τ -GDA with, and all stable critical points (if they exist) will be differential Stackelberg equilibria, and if τ is scaled up and the set of stable points grows, then only differential Stackelberg equilibria can be introduced to the set. Theorem 1. Consider a nonconvex-PŁ/SC zero-sum game (f,−f) where f ∈ C2(Z,R). Then, the following hold: 1) Any critical point z∗ ∈ Z that is not a differential Stackelberg equilibrium is unstable with respect to τ -GDA for all τ ∈ (0,∞); 2) If z∗ is a differential Stackelberg equilibrium,
then spec(−Jτ (z∗)) ⊂ C◦− for all τ ∈ [τ∗,∞) where τ∗ is the minimum τ ∈ (0,∞) such that spec(−Jτ (z∗)) ⊂ C◦− and a finite τ∗ is guaranteed to exist.
In comparison to the stability results for nonconvex-nonconcave zero-sum games of Fiez and Ratliff [15], we obtain the stronger results in nonconvex-PŁ zero-sum games that (i) τ0 = 0 for any critical point that is not a differential Stackelberg equilibrium and (ii) a differential Stackelberg equilibrium is never unstable after it becomes stable as a function of the timescale separation τ . Remark 1. The proof of Theorem 1 also reveals novel insights into the local stability of τ -GDA around critical points in nonconvex-nonconcave zero-sum games. In particular, given any critical point z∗ = (x∗, y∗) in a nonconvex-nonconcave zero-sum game (f,−f) where f ∈ C2(Z,R) such that ∇22f(x∗, y∗) ≺ 0, if z∗ is not a differential Stackelberg equilibrium, then it is unstable with respect to τ -GDA for all τ ∈ (0,∞). This observation follows from the proof of Theorem 1 relying on the fact that∇22f(x∗, y∗) ≺ 0 holds at any critical point in nonconvex-PŁ/SC zero-sum games.

heading: 5 Convergence Analysis
text: Theorem 1 in the previous section characterizes the local behavior of the continuous-time τ -GDA dynamics around critical points. However, ultimately we are most interested in the convergence properties of the discrete-time τ -GDA dynamics. This forms the focus of this section. Specifically, Section 5.1 is devoted to showing that τ -GDA in deterministic settings almost surely asymptotically converges to strict local minmax equilibria in nonconvex-PŁ/SC zero-sum games and Section 5.2 develops convergence rates to ε-critical points in these classes of games.

heading: 5.1 Asymptotic Convergence to Strict Local Minmax Equilibrium
text: We prove in Theorem 2 of this subsection that the deterministic τ -GDA (Algorithm 1) update almost surely converges to a differential Stackelberg equilibrium in nonconvex-PŁ/SC zero-sum games. Despite this result being asymptotic, to our knowledge it is the most general class of zero-sum games in which a global convergence guarantee to established game-theoretic equilibria has been given.
To begin, observe that the continuous-time τ -GDA dynamics do not necessarily correspond to a gradient flow of a function, which can be observed from the fact that the Jacobian Jτ is not guaranteed to be symmetric. As a consequence, there may exist complex limiting behavior beyond convergence to a critical point such as non-trivial limit cycles or periodic orbits. To rule out this phenomenon, we prove that there exists a bounded potential function that decreases along the iterates of τ -GDA and only stops decreasing at critical points of τ -GDA. In what follows, y∗(x) denotes an element of argmaxy∈Y f(x, y) and we define κ := L1/µ. Moreover, as an implication of Assumption 1 and Definition 1,∇maxy∈Y f(·, y) is L4 = (L1 + κL2) Lipschitz (see Lemma 7 in Appendix B.3). Lemma 1. Consider a nonconvex-PŁ/SC zero-sum game defined by f ∈ C2(Z,R) satisfying Assumption 1. For any Γ ∈ (0, 1/7], suppose that τ ≥ Γ−1κ2 and γ < min{ 12L , 1 2τL , 1 2L4 }, then Φ(x, y) = f(x, y∗(x))− Γf(x, y) is a potential function for τ -GDA.
The function f(x, y∗(x)) can be seen as the function the x player would minimize if the y player was playing a best-response y∗(x). The potential function Φ(x, y) essentially captures that along trajectories of τ -GDA, either the value of f(x, y∗(x)) should decrease, or the value of f(x, y∗(x))− f(x, y) should decrease since the y-player converges at a fast rate to y∗(x) given the time-scale separation. Indeed, this potential function implicitly guarantees that the maximizing player tracks the best response set, and that the minimizing player essentially ends up minimizing f(x, y∗(x)) as desired. The choice of τ and the learning rate γ allow us to guarantee that this occurs.
Given the potential function in Lemma 1, we can conclude that Algorithm 1 converges to critical points. The critical points may correspond to stable points of the continuous-time τ -GDA dynamics (Definition 5) or saddle points of the continuous-time τ -GDA dynamics, which are defined as follows. Definition 6 (Saddle Point). The critical point z∗ = (x∗, y∗) ∈ Z is a saddle point of the τ - GDA continuous-time dynamics ż = −Λτg(z) if Re(λmax(−Jτ (z∗))) ≥ 0 and a strict saddle if Re(λmax(−Jτ (z∗))) > 0 and Re(λ) 6= 0 ∀ λ ∈ spec(−Jτ (z∗)).
Recall that Theorem 1 indicates the only stable points of the continuous-time τ -GDA dynamics are differential Stackelberg equilibria. Thus, if we can show that the discrete-time τ -GDA dynamics
avoid saddle points of the continuous-time τ -GDA dynamics, then we can conclude that Algorithm 1 converges to only differential Stackelberg equilibria. The following result of Mazumdar et al. [40] states that the discrete-time τ -GDA dynamics avoid strict saddle points of the continuous-time limiting system almost surely.3
Lemma 2 (Theorem 4.1 [40]). Consider a zero-sum game defined by the nonconvex-nonconcave function f ∈ C2(Z,R) satisfying Assumption 1. The set of initial conditions z ∈ Z from which τ -GDA with γ < min{ 1L , 1 τL} converges to strict saddle points of ż = −Λτg(z) is of measure-zero.
Lemma 2 can be combined with the existence of a potential function (Lemma 1) and the guarantee all stable points of the τ -GDA continuous-time system are strict local minmax (Theorem 1) to arrive at a desirable global convergence guarantee for τ -GDA when given the following assumption.
Assumption 2 (Strict Saddle Property). Given a zero-sum game (f,−f) defined by f ∈ C2(Z,R), we assume every saddle point of the continuous-time τ -GDA dynamics given by the system ż = −Λτg(z) from (5) is a strict saddle point for the choice of τ ∈ (0,∞).
Assumption 2 can be seen as an analogue for gradient dynamics in nonconvex zero-sum games to the commonly assumed strict saddle property in nonconvex optimization [17, 20, 24]. A key distinction is that in nonconvex optimization, strict saddles of the function and strict saddles of the gradient dynamics are equivalent, whereas this property does not carry over to the zero-sum game setting and instead the assumption needs to be explicitly made on saddle points of the gradient dynamics. Given this assumption, we are now ready to the state main result of this paper.
Theorem 2. Consider a nonconvex-PŁ/SC zero-sum game (f,−f) defined by f ∈ C2(Z,R) that satisfies Assumptions 1–2. Then, τ -GDA with τ ≥ Γ−1κ2, and γ < min{ 12L , 1 2τL , 1 2L4 } for Γ ∈ (0, 1/7] asymptotically converges to the set of strict local minmax that are stable for ż = −Λτg(z) almost surely. That is, for almost all initial conditions, τ -GDA will converge to a strict local minmax.
If we fix a τ satisfying the assumptions of the above theorem, then if we consider the set of stable critical points for ż = −Λτg(z), we know that by Theorem 1 this set only contains differential Stackelberg (and hence, strict local minmax) points. It is precisely this set of strict local minmax to which τ -GDA converges almost surely. Note that a stable differential Stackelberg equilibrium is ensured to exist for the choice of τ and γ. Moreover, by Theorem 1, as we increase τ , no new spurious non-minmax points are introduced to the set of stable critical points; only additional strict local minmax points can be added to this set. Thus, this result provides a novel convergence guarantee to not just ε-stationary points but those that are game theoretically meaningful.

heading: 5.2 Convergence Rates to Approximate Stationary Points
text: While Theorem 2 implies a global convergence guarantee to a strict local minmax equilibrium, a global convergence rate to the same set does not easily follow. This is due to the fact that obtaining such a result requires the dynamics to escape strict saddle points not just asymptotically, but efficiently. In lieu of pursuing such a result, in this subsection, we derive global complexity bounds for τ -GDA reaching an ε-critical point. To begin, we have the following convergence result for τ -GDA, which follows rather directly from the potential function given in Lemma 1.
Corollary 1. Consider a nonconvex-PŁ/SC zero-sum game (f,−f) defined by f ∈ C2(Z,R) that satisfying Assumption 1. Then, τ -GDA from any initialization with τ ≥ Γ−1κ2, γ < min{ 12L , 1 2τL , 1 2L4 } for Γ ∈ (0, 1/7], has at least one iterate that is an ε-critical point after Õ(ε−2) iterations.
We remark that we are unaware of an existing convergence result to a ε-critical point for τ -GDA in nonconvex-PŁ zero-sum games. Moreover, it is worth noting that this convergence guarantee holds for choices of τ and γ that satisfy the conditions of Theorem 2. Thus, together, we have shown that τ -GDA finds an approximate stationary point efficiently, and then asymptotically is guaranteed to converge to a strict local minmax equilibrium. It is also known that τ -GDA locally converges
3The strict saddle avoidance result of Mazumdar et al. [40, Theorem 4.1] holds more generally for simultaneous gradient descent with heterogeneous learning rates in n-player general-sum nonconvex games. For simplicity, we only state the result in the context of this work. We also remark that Daskalakis and Panageas [10, Theorem 2.2] show an analogous strict saddle avoidance result for τ -GDA in nonconvex-nonconcave zero-sum games, but restricted to τ = 1, hence the reason it is not referenced in Lemma 2.
exponentially fast around stable strict local minmax equilibrium in nonconvex-nonconcave zero-sum games [15] and thus in this class of games as well.
We now restrict our focus to nonconvex-SC zero-sum games and provide a complimentary convergence analysis. In the existing literature on convergence in the nonconvex-SC literature [35, 59, 62], the proposed potential function has a structure closely related to the potential function in Lemma 1; in particular, it takes the form f(x, y)+r(x, y) where r(x, y) is a tracking term of the form ‖y−y∗(x)‖2 or f(x, y∗(x)). Yet, perhaps surprisingly, despite the fact that the game cost depends on the sequences generated by two separate gradient updates—one from minimizing f and one from maximizing it—we show below that there are choices of τ and γ for τ -GDA such that it is decreasing along trajectories of τ -GDA. The benefit of knowing that the cost function is a potential is that it is a computable quantity that can be monitored to evaluate progress during training in machine learning problems formulated as zero-sum games in this class. For this set of results, we consider both the deterministic and stochastic settings. In the stochastic setting, for any (x, y), a gradient query to an oracle returns g1(x, y; θ1) and g2(x, y; θ2) to the two players respectively, where each θi is a random variable drawn from distribution Di with i ∈ I and the stochastic gradients satisfy the following assumptions.4 Assumption 3. For any (x, y) ∈ Z and each i ∈ I , Eθi∼Di [gi(x, y; θi)] = ∇if(x, y) and ∀ t ∈ R:
P(‖gi(x, y; θ)−∇if(x, y)‖ ≥ t) ≤ 2 exp(− t 2
2σ2i ).
Given this assumption and defining ` := L1 + 3κ′L2 and κ′ := L2/µ, we have the following result. Lemma 3. Consider a nonconvex-SC zero-sum game (f,−f) defined by f ∈ C2(Z,R) satisfying Assumption 1 and Assumption 3. If γ ≤ 1/` and τ = Γ/(µγ) for any constant Γ ≥ 4, then with probability at least 1− δ for any δ ∈ (0, 1), f(xk, yk) is a (stochastic) potential function for τ -GDA in the stochastic and deterministic settings.
This result then leads to the following convergence guarantee to ε-critical points, given that there is a finite minimum value f∗ of the game cost function. Corollary 2. Consider a nonconvex-SC zero-sum game (f,−f) defined by f ∈ C2(Z,R) satisfying Assumption 1 and Assumption 3. For any δ ∈ (0, 1), there exists γ and τ satisying the conditions of Lemma 3 such that, with probability at least 1− δ, starting from any initialization, at least half the iterates of (stochastic) τ -GDA will be ε-critical points after Õ(ε−2) and Õ(ε−6) iterations in the deterministic and stochastic settings, respectively.

heading: 6 Discussion
text: To the best of our knowledge, our results are the first to guarantee global convergence of gradientbased algorithms to game theoretically meaningful equilibria in nonconvex-PŁ/SC zero-sum games. We believe an interesting direction of future work in these classes of games would be to obtain an equivalent guarantee in the setting with constraints. Moreover, in the unconstrained setting, it would be desirable to show not only does a τ -GDA variant provably converge in an almost sure asymptotic sense to strict local minmax equilibria, but that there is also finite-time guarantee (preferably matching the rates from nonconvex optimization) to an appropriate approximate notion. The difficulty in showing this stems from possibility that the game dynamics can get stuck in a region around a non-game theoretically meaningful strict saddle. This problem has been observed in the nonconvex single player setting [12] with gradient descent and trivially extends to τ -GDA in the zero-sum game setting. A body of work in nonconvex optimization has developed algorithmic methods that address this issue [9, 14, 17, 20, 24] including by injecting artificial noise to perturb the updates away from strict saddle points. Yet, to our knowledge, such methods have not yet been extended to the zero-sum game setting. Notably, escaping strict saddles is more of nuanced issue in this setting since strict saddles of the dynamics are not always strict saddles of the function and vice versa.
Acknowledgments and Disclosure of Funding
This work was supported by Office of Naval Research Young Investigator Program and NSF CAREER Award 1844729. Tanner Fiez was also supported in part by a NDSEG Fellowship.
4Note that we are overloading notation by using g1(x, y; θ1) and g2(x, y; θ2) to denote stochastic individual gradients for each player, whereas previously g(x, y) has denoted the vector of each players gradients.

Review summaries:
This paper studies gradient descent ascent learning dynamics with timescale separation in unconstrained continuous action zero-sum games. The minimizing player faces a nonconvex optimization problem, and the maximizing player optimizes a Polyak-Łojasiewicz (PŁ) or strongly-concave (SC) objective. Like [15], this paper assesses convergence to Stackelberg equilibria instead of only notions of stationary. A differential Stackelberg equilibrium corresponds to a joint strategy at which the minimizing player is at a local optimum to its choice variable along the best response curve of the maximizing player, and the maximizing player is at a local optimum concerning its choice variable. In pursuit of this goal, the authors prove that the only locally stable points of the continuous-time limiting system correspond to strict local Stackelberg equilibria in nonconvex-PŁ and nonconvex-SC games. Specifically, this paper exploits timescale separation to construct a potential function of the nonconvex-PŁ game that gives a global asymptotic almost-sure convergence guarantee to the set of strict local Stackelberg equilibria with the stability and asymptotic saddle avoidance. Moreover, this paper shows that nonconvex-SC games do gradient descent ascent provably converge in an almost sure asymptotic sense and a finite time escape time from saddle points.  Overall, this paper gives some theoretical contributions, with the caveat for the clarifications of the assumptions and the shortage of empirical studies. 

In this paper, the authors study the problem of solving specific classes of non-convex min-max optimization problems. More specifically, they consider the problem when the maximizing player optimizes a Polyak-Lojasiewicz or strongly concave objective. In contrast to existing work, the paper focuses on characterizing the convergence of gradient-based algorithms to local Nash Equilibria that are meaningful in game theoretical settings. The authors show that for non-convex PL games and under a strict saddle property, $\tau$-GDA  asymptotically converges to strict local minmax equilibria almost surely. For the class of non-convex strongly concave games, the authors show that $\tau$-PGDA converges to an approximate $epsilon$-local minmax equilibria. For both cases the complexity rate of the algorithms are provided.

The authors focus on the analysis of gradient descent ascent dynamics with timescale separation to solve unconstrained min-max optimization for landscapes that are non-convex on the min player (say x) and strongly concave or satisfy the PL condition for the max player. They focus on the stability analysis and convergence rates of GDA (and its perturbed variant) to the local minimax points (defined in Jin et al paper "What is locally..."). The definition of local min-max points is that the max player plays local best response and the min player chooses a local minimum for the function \max_{y \in B} f(.,y) where B is a ball of small radius. The authors show that local min-max points are stable/ attracting for GDA dynamics; the learning rate of the max player must be naturally larger than that of the min player in GDA (in some sense y updates more often). They also show convergence in \tilde{O}(1/\eps^2) of GDA to an \esp- local min-max in the case of non-convex stronly concave landscapes and non-convex, PL and \tilde{O}(1/\eps^4) of SGDA for the case of non-convex strongly concave landscapes.