Global Convergence  to Local Minmax Equilibrium in Classes of Nonconvex Zero-Sum Games
Authors: Tanner Fiez
Lillian J Ratliff
Eric Mazumdar
Evan Faulkner
Adhyyan Narang
Venue: NeurIPS 2021 Poster (2021)
Keywords: zero-sum games
nonconvex-strongly-concave
nonconvex-PL
game theory
dynamical systems
stability

Abstract: We study gradient descent-ascent learning dynamics with timescale separation ($\tau$-GDA) in unconstrained continuous action zero-sum games where the minimizing player faces a nonconvex optimization problem and the maximizing player optimizes a Polyak-Lojasiewicz (PL) or strongly-concave (SC) objective. In contrast to past work on gradient-based learning in nonconvex-PL/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 $\tau$-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.

Global Convergence to Local Minmax Equilibrium in Classes of Nonconvex Zero-Sum Games
Tanner Fiez
Lillian J. Ratliff
Eric Mazumdar
University of Washington fiezt@uw. edu
University of Washington ratliffl@uw. edu
California Institute of Technology
mazumdar@cal tech. edu
Evan Faulkner
Adhyyan Narang
University of Washington evanjf5@uv. edu
University of Washington
adhyyanguw.cm
Abstract
We study gradient descent-ascent learning dynamics with timescale separation (T-GDA) in unconstrained continuous action zero-sum games where the minimizing player faces nonconvex optimization problem and the maximizing player opti- mizes a Folyak--.ojasiewice (PL) or strongly-concet past work gradient-based learning in nonconvex-PE./ we assess convergence in relation to natural game-theoretic equilibria instead of only notions of stationarity. In pursuit of this goal, prove that the only locally stable points of the 7-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 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-ane ascent update set of the strict local minmax equilibrium. Moreover, we provide convergence rates for the gradient descent-ascent dynamics with timescale separation approximate stationary points.
(SC) objective. contrast
zero-sum games,
Introduction
We study continuous action zero-sum games of the form
min max f(z, v) aEX yEy
where f E C2 Y)R) and X Rd and y dg denote the individual action spaces and = di + d2. In particular, we focus on unconstrained, continuous strategy space zero-sum games in which f(., y) is potentially nonconvex in X and f(x satisfies the (PE) condition [47] or is strongly-concav (SC) in E V. We refer to these classes of games as nonconvex-P2 PL and nonconvex-SC zero-sum games, respectively.
This general formulation has a broad spectrum of applications such as fair classification 45 distribu- tionally robust optimization 44
48 [33] and adversarial training (38] Consequently, there has been surge of interest in recent years toward developing methods for solving these problems efficiently. So far, existing work gradient-based learning in nonconvex- PPLSCC 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 B3 34
36
45
48
62
In contrast, common theme the study of general eenconvvx-nnnccoccaee 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 (NcurIPS 2021).

---

58 64]. The purpose of this analysis is generally to determine whether commonly deployed algorithms can guarantee local convergence to only game- -hhorretc equilibria or to design algorithms that achieve this objective.
order structure 10 16
23
40
41
The goal of this paper is close the gap between the two problem classes and determine whether gradient-based learning algorithms in nonconvex-PL/SC zero-sum games can be shown to globally converge to only game-theoretically meaningful equilibria (local minnax/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 F-GDA, where the ratio of learning rates denoted by r parameterizes the timescale separation between players, is provided in Algorithms [ deterministic and stochastic settings respectively. Simply put, T-GDA (Algorithm I corresponds to each player following their individual gradient in a noiseless setting, while stochastic 7-GDA (Algorithm ( describes each player following their individual stochastic gradient. The 7-GDA update only requires first-order gradients and thus is a computationally efficient method for machine learning problems formulated games,
1.1 Contributions
We show that T-GDA has global convergence guarantees in nonconvex-PL/S zero-sum games to the natural cume-theoretic solution concept for this problem class of strict local minmax equilibria 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 GDAA continuous- time limiting system are strict local minmax equilibrium in nonconvex- sum games. A key implication of this is that any critical point which is not a strict local minmax equilibrium a saddle point of the continuous-time limiting system.
zero-
2) In Theorem? 2, we combine Theorem [ with a potential function construction (Lemma D and an asymptotic saddle avoidance result (Lemma 2) to prove that the 7-GDA update in deterministic settings (Algorithm[] [ globally asymptotically converges to strict local minmax equilibria almost surely in the class of Monconvex-PL/SS zero-sum games.
3) In Corollary [ using the potential function from Lemma
[ we show that G-GDA in deterministic settings reaches an s-critical point in Ō(s-²) steps in nonconvex-PL/S5 zero-sum games. More- over, specific to nonconvex-SC, zero-sum games. Lemma Ssows shows there exists learning rates for 7-GDA such that the cost function of the game itself can be made a potential. Corollary then uses the potential function from Lemma to show that 7-GDA reaches an e-critical point in Ō(s-2) and ((e-)) 9) 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 [ beyond its importance toward proving Theorem 2 Theorem [] is potentially of independent interest given the implications also has for the local stability of 7-GDA around critical points in the more general setting of Donconvex-nonconvavy zero-sum games. Furthermore, to our knowledge, Theorem provides the broadest existing global convergence guarantee for maddeent-based algorithms continuous games. Finally, while there exists known convergence rates for gradient- pradient-based learning algorithms to e-critical points in nonconvex- PL/SC zero-sum games, are unaware of such result in nonconvex- Pt. zero-sum games for T-GDA, and the fact that we derive a rate in nonconvex-SC zero-sum games using the cost function itself a potential function has practical implications given that it can easily be monitored when running the algorithm to evaluate progress toward a solution.
chee-ttheryyycally meaningful equilibria in zero-sum
1.2 Practical Motivation
The study of nonConvex-Pt/SCC 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 equilibri.. Indeed, notions of stationarity are not guaranteed to reflect a meaningful solution to the underlying problem. Consequently, it critical to give convergence guarantees to minmax equilibrium as we pursue in
'ttrict local minmax equilibria characterized by maddeent-basd sufficient conditions are also known as differential Stackelberg equilibria in the literature [15] 16 and we the terms interchangeably in this work.

---

this work. We now provide examples from the literature of machine learning applications that are relevant 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 the problems can transformed into unconstrained nonconvex-Pt/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
min maxie (I...,K) (2w))
where (ww) represents the loss on category i with w denoting neural network parameters. A reformulation of this problem [45] with 7 the simplex in IR is given by the zero-sum game
min m Ex= te((w).
Example 2. To train neural network classifier robust against adversarial attacks, common approach to formulate training as a robust minmax optimization problem of the form
wen 1= 1n le ((x; + d,, Me. w);
where ((2; + di, Me, w) represents the loss sample z; perturbed by 8; with budget and label ys as a function the parameter weights w. [88). reformulation of this problem [45 is given by
min Σ mAXIET Σj=1 E wi)
(2)
where øig is the result of targeted attack the sample æ; seeking change the output of the network to label j and T is the simplex in IR
Example 3. Distributionally robust optimization often results in a zero-sum game of the form
min maxtET E ((e(() r())
where (xx is the loss of a model w on the i-th data point, T the simplex in R.W, and r(t) is carefully selected convex regularizer [4 48 53
The machine learning problem formulations in concave zero-sum games in which the strategy space of the minimizing player is unconstrained and the strategy space the maximizing player is constrained to the simplex. These problems are naturally adapted to the unconstrained nonconvex-Pt/SS zero-sum game setting considered in this paper by removing the constraint on the strategy space of the maximizing player and including suitable PL/SC regularization penalty on the choice variable of the maximizing player.
from Examples D represent nonconvex-
1.3
Organization
The rest of the paper is organized as follows. Section deetils related work and Section 3 presents thee-the, mathematical, and algorithmic prelimmaries for our results. Section 4 devoted to studying the local stability properties around critical points of the continuous for the T-GDA learning dynamics. In Section 5 we present our study of the convergence properties of 7-GDA nonconvex-PL.. PP./SC zero-sum games. We conclude with discussion in Section 6 Finally, the supplementary material (appendix) contains the proofs of theoretical results.
limiting system
2 Related Work
We now cover the most relevant related work with further discussion provided in Appendix A
Nonconvex-Nonccoccave 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 Importantly, it has been shown that unless the timescale separation chosen very carefully, the stable critical points of gradient descent-ascent may not be game-theoretically meaningful and game- same--heorettcally meaningful critical points may
nonconvex-noncomeavv
(see Definition 4 10
16
23
40
42
43
63)

---

Table 1: The gradient complexity of gradient descent (GD) and its perturbed variant (PGD), gradient descent-ascent with timescale separation (T-GDA), and alternating (including multi-step) gradient descent-ascent (AGDA) in deterministic and stochastic nonconvex optimization, nonconvex-SC zero- sum games, and nonconvex-PL zero-sum games. We state the complexity in terms of the e tolerance of the guarantee with the notation (-) hiding logarithmic factors in E.
Complexity
Problem
Algorithm & Reference
Guarantee
Deterministic
Stochastic
Nonconvex
GD
(
O !
Stationnaitty
Optimization
PGD
O(s
Ö
Local Min
Nonconvex
T-GDA, ACAD 33
(ss-2)
O(e
8 Stationnarity
SC Zero-Sum
Theorem 2
(7-GDA)
Asymptotic
DSE
Corollary
Corollary 2
(T-GDA)
O(s-²)
O( 9)
8 SStationarity
Nonconvex
AGDA
45
62
Appendix D]
O
8 Staationarity
Pt. Perm-rs-um
Theorem
(T-GDA)
Asymptotic
DSE
Corollary
(T-GDA)
8 e-Stationarity
We obtain stronger stability characterizations (see Theorem T for r-GDA in nonconvex- Pt.SCC zero-sum games using the structure imposed on the game cost function. The result of Theorem D also has novel implications for the local stability of T-GDA around critical points in the more general setting of is fundamental toward proving the global almost sure asymptotic convergence guarantee for 7-GDA in deterministic settings to strict local minmax equilibria in nonconvex-PL/SC zero-sum games (Theorem Further discussion of this topic is given in Section
not be stable 15 23
noncoovvvveee zero-sum games (see Remark D Moreover, it
Nonconvex-PL. and Nonconvex-SC Zero-Sum Games. Table provides a comprehensive compar- ison between our convergence results and existing convergence results for gradient descent variants in nonconvex optimization and Nonconvex-PL/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 approx- imate stationary point of the dynamics or a surrogate function, we obtain convergence guarantees in regards to differential Stackelberg equilíbria (equivalently strict local minmax equilibria). Despite this being a much stricter and meaningful notion of solving the problem, Theorem shows that global asymptotic convergence guarantees for G-A in deterministic settings this type of solution remain obtainable in nonconvex PPE/oO zero-sum games. This is the main result of the paper. While we do not prove rate of convergence to differential Stackelberg equilibria or an approximate notion, Corollary I shows 7-GDA in deterministic settings with parameter choices satisfying the conditions of zero-sum games. We
Theorem 2 reaches an e-critical point in (s-- steps in nonconvex-Pt.A are unaware of an existing rate for 7-GDA in deterministic settings in nonconvex-PP PE. zero-sum games. Finally, as complementary result, Lemma shows there exists learning rates for F-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 then uses this potential function to show that GDDA reaches e-critical point in (ss-2) and ( )) steps in deterministic and stochastic nonconvex-So zero-sum games, respectively.
Escaping Saddle Points. Saddle avoidance results for variants of gradient descent in nonconvex optimization are asymptotic or finitettmee The former states that almost surely the algorithm does while the latter gives rates of escape to conclude convergence
not converge to saddles points (28 29
20 24). primary assumption in the aforementioned works what is known as the strict saddle property, which ensures directions of escape exists from saddle point. The methods for showing gradient descent escapes saddle points almost surely 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 key component of proving the global asymptotic convergence guarantee to strict local minmax for 7-GDA turns out to be ensuring that the
to approximate local minimum [7

---

update escapes saddle points of the continuous-tima time limiting system almost surely. To show this property holds for 7-GDA in nonconvex-PL.C zero-sum games, we are able invoke existing saddle avoidance results for gradient-based learning in continuous games 40)
3 Preliminaries
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, We consider objective functions f E (Z, R) where the joint strategy space is denoted by Z = X x y where X' Rdd and y' IR d2 denote the individual action spaces and d d1 + d2. We often denote a joint strategy using the shorthand notation
(z, y) E Z = X' y.
Notation. We denote V the total derivative of J. V. the derivative of f with respect the choice variable of player i, Vij. as the partial derivative of V with respect to the choice variable of player j. and f as the partial derivative of V.f with respect to the choice variable of player We let || denote the 2-norm of vectors unless otherwise specified, spec(.) denote the set of eigenvalues a matrix, Ro(-) denote the real part of a complex number, and Co and C denote the open left-half and right-half complex plane, respectively. Let Amin (A) denote the eigenvalue of A with the minimum real part, and Xmax (A) the eigenvalue of A with the maximum real part. Finally, we indicate A is positive and negative definite using the notation
0 and A O, respectively.
Classes of Games. We study and analyze both nonconvex-P -P. and nonconvex-So zero-sum games. To begin, we state standard smoothness assumption that is needed throughout.
Assumption 1. Given a zero-sum game (J, -f) defined by I E (2 (2.R), V. Vis(z, v) and V2 (x, v) are L1 and L2 Lipschitz, respectively. That is, x, x' E X. v/ E y.
V y) iff(2'' b')ll S L1(1= - + lly s Il,, I'1l
V2f(z, y) 22 I')ll S - ='1l + lll - 3/ II).
This assumption immediately implies that the vector of individual gradients denoted by g(x, v) = (Vif(z, v). (2,(x,)))
is also Lipschitz with parameter L L= L1 L2.
We now define a nonconvex-PE zero-sum game 45). This class of games allows for the objective to be nonconvex in x E X, but it needs to satisfy the colyak-E.ojasiwwic. (Pt.) condition (47) in E y Definition (Nonconvex-Ptt Game). Consider a zero-sum game (J--)) defined by f E C2 R)) The game is called nonconvex-PL. if [(x,)) is p-PL with respect to the argument y E V. That is, for J > and for all z (z,y) v) E Z,
22 2)1 2 2m(maxyee> f(z, v²) - f(z,v)),
where for any fixed x E X, max f(x, yf) has a nonempty solution set and a finite optimal value.
In nonconvex-Pi PL. zero-sum games, the solution set of argmax, f f(x", v') )) for any fixed x" X may not be a singleton and the maximizing player's objective may be nonconcave. However, by Definition D it follows immediately that any (x", yy" such that [/22(<"" ,"""""""
0 satisfies f("', m f(x", ,,"")))) ) so any stationary point with respect to is a global maximum.
The following provides 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 E X' but it must be SC in y E y.
Definition 2 (Nonconvex-St) Game). Consider a zero-sum game (S,-S) defined by I E (2, The game is nonconvex-SC if f(x,-) is y-SC with respect to the argument E y. That is, given any X and for all y. v' E y.
f(z. v') S f(x + (Vef(z,v),)) - 3)
11 Illl'' -
It is important to note that nonconvex, J-SC zero-sum games are nonconvex, μoPPE zero-sum games, but nonconvex-PE. zero-sum games may not be nonconvex-Se zero-sum games, which follows from the relationship between PL and SC functions (25). This is to say that the class of nonconvex-PL
5

---

Algorithm T-GDA
Algorithm Stochastic 7-GDA
Input: 2o Rd Mo E R2
Input: 2g E [Rd,, y/ R24
for = 0, 1,.... do
for = 0, 1,... do
2x+1 t 2k y Vff 0k)
Fk+1 3 791 (ax Uk: 01.k)
Mk+1 f yk + yT (2f(
yb++1 t- yk + YT ( Uki 02.6)
end for
end for
zero-sum games a superset of the class of nonconvex- SSC zero-sum games. Thus, results we state for nonconvex-Pt. zero-sum games immediately hold for nonconvex-SC zero-sum games.
Learning Dynamics. We study gradient descent-ascent with timescale separation. Let y be the learning rate of player and T > be the timescale parameterization so that the learning rate of player is given by 7y. The deterministic T-GDA dynamies are presented in Algorithm [ and the stochastic T-GDA dynamics are given in Algorithm 2 (see Section 5.2 the relevant notation). The key distinction between this study of gradient descent-ascen -nccent 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 (z, y) E Z such that f y) = 0 and V2f(x. y) = 0. Critical points correspond to stationary points of the 7-GDA dynamics. The nonconvex-Pt/S literature has generally assessed convergence in terms of the complexity of finding an e-critical point (see, e.g., 45 (2).. We formally define e-critical point now for later reference.
zero-sum game
Definition 3 (a-Critical Point.). The joint strategy (x", .y") Z is E-critical point when the conditions ViI("",,'') S e and [V22(<"" "r""""""") ) S & hold.
closely related and common notion of convergence in this body of work (see e.g., of finding an e-critical point of the function max f(. This criterion amounts to seeking to achieve the condition V[V, max f(z y)ll S..
33 that
In contrast, we assess convergence with connections to the equilibrium notions that are commonly studied in the nonconvex-nonconcaaee zero-sum game literature. Since either stationarity notion may lack any game-theoretic meaning, we consider a strictly harder notion of solving game.
Equilibrium Notions. The typical solution concept in game theory when implicit or explicit order of play is present the structure of the game is the (local) Stackelberg (equivalently minmax in zero-sum games) equilibrium concept 66 Informally, in nonconvex-PLe -PL/SC zero-sum games, local minmax equilibrium corresponds to a strategy pair (x"."" E Z such that x" is a local minimum of the function f(x y. (z)) where y. (z) argmax f(z y) is local maximum of the function f(*", When the function f is bounded or when f(: 3) is bounded and f(z, -) 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 this definition, we denote by J(r, y) the Jacobian of the individual gradient vector g(x, u) given by
40 58 64).. Toward presenting
Vis( J v) v (2,
V -V/
Let (-) denote the Schur complement of (-) with respect the de d2 block in (-). The following definition is characterized by sufficient conditions for local minmax equilibrium in zero-sum games.
Definition 4 (Differential Stackelberg/Strict Local Minmax Equilibrium 16 23 The joint strat- egy (x" y²) E Z is a differential Stackelberg equilibrium when the conditions Vif(=" 0, V2f(x", 8²) 0 and S (J(x", yy)) O, V (a" yy" hold.
We remark that in nonconvex-PH.A PFCSC zero-sum games, S (J("",, "o""."" yy") as in Definition 4 is well-defined at any critical point (x* y²" since det (v .y")) * (see Lemma in Appendix B.3
By implicit order of play, mean the min and max order not interchangeable.

---

4 Local Stability Analysis
To characterize the convergence of 7-GDA, we begin by studying its continuous-timg time limiting system
2 = --,(((z))
(5)
where 2 (á: v). A, blockdiag La. TIaz). and 9(2) is the vector of individual gradients. The Jacobian of this system is given by
-= A,,)))
(6)
We analyze the stability of the continuous- time system around critical points 2" (x" y²) as function of the timescale separation r using the Jacobian (² in this section toward drawing conclusions about the stability and convergence of the discrete time system T-GDA, A critical point is said be locally (exponentially) stable when the spectrum of -==(2") is in the open left-half complex plane C2 (cf. Theorem 3] Appendix B.2). Simply put, critical point =" is locally exponentially stable if and only if the real parts of the eigenvalues of -== are strictly negative. Throughout, we use the broader term "stable" to mean the following.
Definition 5 (Stability). A critical point 2" = (x".v") E 2 is locally exponentially stable for 2 A=)(2)) if and only if (f)" C2 (= speo(J+(=")) C C.).
Stability with respect to the continuous- time T-GDA dynamics guarantees that the system asymptoti- cally converges at exponential rate to the critical point in local neighborhood. Moreover, given suitable choice of learning rates, equivalent insights hold for the discrete-tine dynamics (8]
Zero-Sum Games Given the implications regarding con- vergence, a number of papers the past several years study the stability of r-GDA around critical points and the connections to differential Nash and Stackelberg equilibrium in zero-sum games 16 23, [4]] However, this body of research focuses on general nonconvex-noncom zero-sum games, the stable critical points of GDGDA coincide with the set of differential Stackelberg equilibria only when the timescale separation
Stability in Monconvex-Nonconeee
10 15|
zero-sum games. In general across the spectrum of nonconvex-nonconcea
[23. Given that such choice of timescale separation requires the learning rate y + 0 in order to retain stability of the discrete-tima system, it is not clear how to derive practical algorithm from this insight.
Toward remedying this problem, Fiez and Ratliff [5] provide stability results in terms of the timescale separation concerning given critical point, rather than across the space of nonconvex- nonconcave zero-sum games. In particular, they prove a stability and instability result as a function of the timescale separation in the r-GDA dynamics. The stability results say that given differential Stackelberg equilibrium 2², there exists a finite T" e (0, oo) that can be constructed such that 2* is stable for all E (r" 20). On the other hand, the instability results says that given critical point which is not a differential Stackelberg equilibrium, there exists a finite To E (0, 20) that can be constructed such that 2" is not stable for all J E (To, 00).
Stability in Nonconvex-PL.SC Zero-Sum Games. To our knowledge, the connection between the stability (and instability) of critical points with respect to 7-DA dynamics and game-theone theoretic equilibrium notions in the semi-structured problems of nonconvex-PE. and nonconvex-SC zero-sum games has not been fully characterized. We show in the following result that when a nonconvex- nonconcave game is specialized to a nonconvex-PP Pt. zero-sum game as from Definition [ significantly more general stability characterizations can be obtained by exploiting the fact that V yy") 0 at any critical point 2* (x*, y²) (see Lemma in Appendix B.3) Notably, any critical point = (x",, v²) that is not a differential Stackelberg equilibrium is not stable ("unstable") for all 7 > 0. In other words, T-GDA does not admit spurious stable points in nonconvex-PP zero-sum games. This in stark contrast to the known fact that 1-GDA admits spurious stable points in the more general class of nonconvex- -ecconvex-nnoccncvve games as has been shown in previous literature 10 23 40 Moreover, if 2" is a differential Stackelberg equilibrium, then 2" is stable for all 7 larger than the minimum r, for which 2" is stable and such a finite т. is guaranteed to exist. This result implies that in practice, one can select a finite value of run GDAA with, and all stable critical points (if they exist) will be differential Stackelberg equilibria, and if r is scaled up and the set of stable points grows, then only differential Stackelberg equilibria can be introduced the set.
Theorem 1. Consider a conconvex-PI/SC zero-sum game (f.-f) where J E C² R). Then, the following hold: 1) Any critical point z" E Z that not differential Stackelberg equilibrium is unstable with respect to 7-GDA for all (0, oo); 2) If z" is a differential Stackelberg equilibrium.
7

---

then spec(-J+(x>)) C C for all E [Tx, where T, is the minimum E 00) such that speo(-J)(2*)) C and a finite T, is guaranteed to exist.
In comparison to the stability results for nonconvex-nonconcee zero-sum games of Fiez and Ratliff [15], we obtain the stronger results in nonconvex-PL zero-sum games that (i) To = 0 for any critical point that is not a differential Stackelberg equilibrium and (ii) a differential Stackelberg equilibrium is never unstable after becomes stable as a function of the timescale separation т.
Remark 1. The proof of Theorem ] also reveals novel insights into the local stability of T-GDA around critical points point x' = (x", ,.") in that V2f(=", yn) < O, if xn is not a differential Stackelberg equilibrium, then is unstable with respect to T-GDA for all 7 E (0, oc). This observation follows from the proof of Theorem reelying on the fact that (1f("", .y*) < O holds at any critical point in nonconvex-PEAe zero-sum games.
zero-sum games. In particular, given any critical sunconvex-nonconeee zero-sum game (f.-f) where f E. C2 (Z, (Z, R) such
Convergence Analysis
Theorem I in the previous section characterizes the local behavior of the continuous-time T-GDA dynamics around critical points. However, ultimately we are most interested in the convergence properties of the discrete-time T-GDA dynamics. This forms the focus of this section. Specifically, Section is devoted to showing that F-GDA in deterministic settings almost surely asymptotically converges to striet local minmax equilibria in nonconvex-PL/ST PP./SC zero-sum games and Section 5.2 develops convergence rates to e-critical points in these classes of games.
5.1 Asymptotic Convergence to Strict Local Minmax Equilibrium
We prove in Theorem 2 of this subsection that the deterministic r-GDA (Algorithm I update almost surely converges to a differential Stackelberg equilibrium in nonconvex-PL.A 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 7-GDA dynamics do not necessarily correspond to gradient flow of 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 GDAA. In what follows, y. (x) denotes an element of argmaxyey fz, y) and we define K. == L p. Moreover, as an implication of Assumption I and Definition V max f())) is L4- (L, + kL2) Lipschitz (see Lemma 7 in Appendix B.3
Lemma 1. Consider a noncomex- zero-sum game defined by f C2 R) satisfying Assumption For any I E (0, 1/7]. suppose that t 2 r-1x" x2 and 7 < min 2L 2 2L, ]. then (xx = f(, fx,,,xx)) fz, y) is a potential function for GDAA.
The function f( y. (x:) can be seen as the function the player would minimize if the player was playing a best-response ye (ar). The potential function ( y) essentially captures that along trajectories of 7-GDA, either the value of f(z, y. (x)) should decrease, or the value of f(x, (x)) f(x, y) should decrease since the yyplayer 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(r y- (z)) as desired. The choice of 7 and the learning rate ? allow to guarantee that this occurs.
Given the potential function in Lemma D we can conclude that Algorithm converges to critical points. The critical points may correspond to stable points of the continuous-ting 7-CDA dynamics T-GDA dynamics, which are defined as follows.
(Definition or saddle points of the continuous-tin
Definition 6 (Saddle Point). The critical point 2" (x", y²) E Z is saddle point of the GDA continuous-tim dynamics & = -A, if Re(Amax(-IJ (x"(()))) 2 and a strict saddle if (z"))) > 0 and Re(A) & A X E spec(-J, (2*))
Recall that Theorem T indicates the only stable points of the continuous-time G-DD dynamics are differential Stackelberg equilibria. Thus, if we can show that the discrete-time T-GDA dynamics
8

---

avoid saddle points of the continuous-timg time 7-GDA dynamics, then we can conclude that Algorithm T converges only differential Stackelberg equilibria. The following result of Mazumdar et 44 states that the discrete-ting T-GDA dynamics avoid strict saddle points of the continuous-time limiting system almost surelyP
Lemma (Theorem 4.1 40). Consider a zero-sun game defined by the nonconvex-nonconen
function f E (2, R) satisfying Assumption ! The set of initial conditions E Z from which 7-GDA with y < min L } converges to strict saddle points of & -A) is of measure-zero.
Lemma 2 can be combined with the existence of a potential function (Lemma T and the guarantee all stable points of the T-GDA continuous-tima system are strict local minmax (Theorem [ to arrive at desirable global convergence guarantee for T-GDA when given the following assumption.
Assumption 2 (Strict Saddle Property). Given zero-sum game (f,-J) defined by (2) we assume every saddle point of the continuous- time T-GDA dynamics given by the system = -A,g(2) from (3) is 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 I7
20 24 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 noncomvex-
tero-sure game (f, -f) defined by f (2, that 1
? Then, T-GDA with T 2 g= and < min 21: 2-L: 2L, for I E (0, 1/7] asymptotically converges to the set of strict local minmax that stable for - almost surely. That is, for almost all initial conditions, 7-GDA will converge to a strict local minmax.
satisfies Assumptions
If we fix a satisfying the assumptions of the above theorem, then if we consider the set of stable critical points for غ = g we know that by Theorem [ this set only contains differential Stackelberg (and hence, strict local minmax) points. It precisely this set of strict local minmax to which r-GDA converges almost surely. Note that stable differential Stackelberg equilibrium ensured to exist for the choice of r and 7. Moreover, by Theorem [ 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 novel convergence guarantee to not just e-stationary points but those that are game theoretically meaningful.
5.2 Convergence Rates to Approximate Stationary Points
While Theorem 2 lippiess a global convergence guarantee to a strict local minmax equilibrium, a global convergence rate to the same set does not easily follow. This 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 7-GDA reaching an e-critical point. To begin, we have the following convergence result for T-GDA, which follows rather directly from the potential function given in Lemma |
1 Corollary 1. Consider a nonconvex- Perroovvee--P/CCCCC- zero-sum game (f, -f) defined by f E C²2 R) that sat- isfying Assumption 1 Then, T-GDA from any initialization with T 2 r-1x" < min 27, 2 2ha
for D E 1/7) has at least one iterate that is an 8-critical point after (s--2) iterations.
We remark that we are unaware of an existing convergence result to a e-critical point for GDAA in nonconvex-Pt PP. zero-sum games. Moreover, it is worth noting that this convergence guarantee holds for choices of r and 7 that satisfy the conditions of Theorem 2 Thus, together, we have shown that 7-GDA finds approximate stationary point efficiently, and then asymptotically is guaranteed to converge to a striet local minmax equilibrium. It is also known that T-GDA locally converges
'The strict saddle avoidance result of Mazumdar et al. 40 Theorem 4.1] holds more generally for simul- taneous gradient descent with heterogeneous learning rates in n-player general-sur sumeral--um 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 G-GDA in nonconvex nonconcave zero-sum games, but restricted to 1. hence the reason is not referenced in Lemma 2
-oncovex--onconccve

---

exponentially fast around stable strict local minmax equilibrium in nonconvex-noncooeeaw nonconeave zero-sum games [1] and thus in this class of games as well.
We now restrict our focus to nonconvex-S zero-sum games and provide a complimentary conver- gence 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 in particular, it takes the form fa, + y) where r(z, y) is tracking term of the form 1yy y || or fax 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 r and y for 7-GDA such that it is decreasing along trajec- tories of F-GDA. The benefit of knowing that the cost function is a potential is that 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 (z; y). gradient query to an oracle returns 91 (2r, y; 01) and 92 (Ir, y; 02) to the two players respectively, where each 6; a random variable drawn from distribution D, with E Z and the stochastic gradients satisfy the following assumptions Assumption 3. For any (z. y) E Z and each E I. ED, 19. y; 0.)] = V.f y) and V e RR
P(ll: y: 0) v. w)ll 2 1) S 2 exp( 207
Given this assumption and defining := L1 + 3K' L2 and K' := L2/μ, we have the following result.
Lemma 3. Consider a nonconvex-SC zero-sum game (f, (f) defined by f E C2 (2, R) satisfying
Assumption [ and Assumption 3 If- S 1/8 and T = (1/(4)) for any constant I 2 4, then with probability at least - ō for any E (0, 1), [TK, W1) is a (stochastic) potential function for GDAA in the stochastic and deterministic settings.
This result then leads to the following convergence guarantee to e-critical points, given that there is a finite minimum value f of the game cost function.
Corollary 2. Consider a nonconve--SC zero-sum game (J:-f) defined by J E C2 R) satisfying Assumption| 7 and Assumption 3 For any ó E (0,1), there exists yy and T satisying the conditions of Lemma 3 such that, with probability at least 1 8, starting from any initialization, at least half the iterates of (stochastic) 7-GDA will be E-critical points after OE=22) and Ö(E-0) iterations in the deterministic and stochastic settings, respectively.
Discussion
To the best of our knowledge, results are the first to guarantee global convergence of gradient- based algorithms to game theoretically meaningful equilibria in nonconvex-PLE PLL/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 7-GDA variant provably converge in 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 appropriate approximate notion. The difficulty in showing this stems from possibility that the game dynamics can get stuck in a region around 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 7-GDA in the zero-sum game setting. body of work in nonconvex optimization has developed algorithmic methods that address this issue 19 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 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 striet 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.
'Note that we are overloading notation by using gn (æ, y; 01) and 92(2, 0z) to denote stochastic individual gradients for each player, whereas previously g(Ø, 8) has denoted the vector of each players gradients.
10

---

References
[1] Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann. Local saddle point optimization: A curvature exploitation approach. In International Conference Artificial Intelligence and Statistics, pages 486-495, 2019.
[2] Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. In ACM SIGACT Symposium on Theory of Computing, pages 1 1195-1199, 2017.
[3] Zeyuan Allen-Zhu. Natasha 2: faster non-convex optimization than sgd. In Advances Neural Information Processing Systems, pages 2680-2691, 2018.
[4] Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. In Advances in Neural Information Processing Systems, pages 3716-3726, 2018.
[5] Mihai Aniteseu. Degenerate nonlinear programming with a quadratic growth condition. SIAM Journal on Optimization, 10(4):1116-111 2000.
[6] Tamer Başar and Geert Jan Olsder. Dynamic noncooperative game theory. SIAM, 1998.
[7] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal Optimization, 28(2):151--1772 2018..
[8] Benjamin Chasnov, Lillian Ratliff, Eric Mazumdar, and Samuel Burden. Convergence analysis of gradient-based learning in continuous games. In Conference on Uncertainty in Artificial Intelligence, pages 935 924,944,20 2020.
[9] Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. In International Conference on Machine Learning, pages 1155-1164, 2018.
[10] Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, pages 9236 9246, 2018
[11] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In ACM SIGACT Symposium on Theory of Computing, pages 1466-1478, 2021.
[12] Simon S Du, Chi Jin, Jason Lee, Michael Jordan, Barnabás Póezos, and Aarti Singh. Gradient descent can take exponential time to escape saddle points. Advances in Neural Information Processing Systems, pages 1068-1078, 2017.
[13] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path integrated differential estimator. In Advances Neural Information Processing Systems, pages 687-697, 2018.
[14] Cong Fang, Zhouchen Lin, and Tong Zhang. Sharp analysis for nonconvex sgd escaping from saddle points. In Conference on Learning Theory, pages 1192-1234, 2019.
[15] Tanner Fiez and Lillian Ratliff. Local convergence analysis of gradient descent ascent with finite timescale separation. In International Conference on Learning Representations, 2021.
[16] Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in stackelberg games: Equilibria characterization, convergence analysis, and empirical study. International Conference Machine Learning, pages 3133-3144, 2020.
[17] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online online stochastic gradient for tensor decomposition. In Conference on Learning Theory, pages 797- 842, 2015.
[18] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.

---

[19] Ya-Ping Hsich, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-max optimiza- tion algorithms: Convergence to spurious non-critical sets. In International Conference on Machine Learning, pages 4337--3348, 2021.
[20] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724-1732, 2017.
[21] Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pages 1042-1085, 2018.
[22] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. 1902.0339,, 2019.
[23] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What local optimality in nonconvex- nonconcave minimax optimization? In International Conference on Machine Learning, pages 4880-4889, 2020.
[24] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM, 18(2):1-29, 2021.
[25] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Polyak-Lojasiewicc condition. In Machine Learning and Knowledge Discovery in Databases, pages 795-811. Springer International Publishing, 2016.
[26] Hassan Khalil. Nonlinear Systems. Prentice Hall, 3rd edition, 2002.
[27] Peter Lancaster and Miron Tismenetsky. The theory of matrices: with applications. Elsevier, 1985.
[28] Jason D Lee, Max Simchowitz, Michael I Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Conference on Learning Theory, pages 1246-1257, 2016.
[29] Jason D. Lee, loannis Panageas, Georgios Piliouras, Max Simchowitz, Michael Jordan, and Benjamin Recht. First-order methods almost always avoid strict saddle points. Mathematical Programming, 176(1):311-337 2019.
[30] Alistair Letcher. On the impossibility of global convergence in multi-loss optimization. Interna- tional Conference on Learning Representations, 2021.
[31] Kfir Y Levy. The power of normalization: Faster evasion of saddle points. arXiv:1611.0483 2016.
[32] Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for sononvee-ssrongly-conec.o min-max optimization. arXiv:2 2021.
[33] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. International Conference on Machine Learning, pages 6083-6093, 2020.
[34] Tianyi Lin, Chi Jin, Michael Jordan, et al. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pages 2738-2777 2020.
[35] Sijia Liu, Songtao Lu, Xiangyi Chen, Yao Feng, Kaidi Xu, Abdullah Al-Dujaili, Mingyi Hong, and Mna-May O' O'Reilly. Min-max optimization without gradients: Convergence and applications to black-box evasion and poisoning attacks. In International Conference on Machine Learning, pages 6282-6293, 2020.
[36] Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive approximation for one-sided non-convex min-max problems: algorithms and applications. IEEE Transactions on Signal Processing, 68:3676-3691. 2020.
[37] Zhi-Quie Zhi-Quan Luo and Paul Tseng. Error bounds and convergence analysis of feasible descent methods: a general approach. Annals of Operations Research, 46(1):157-178, 1993.
12

---

[38] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representation, 2018.
[39] Eric Mazumdar and Lillian J Ratliff. Local Nash Equilibria are Isolated, Strict Local Nash Equilibria in 'Almost All' Zero-Sum Continuous Games. In IEEE Conference on Decision and Control, pages 6899-6904, 2019.
[40] Eric Mazumdar, Lillian J Ratliff, and S Shankar Sastry. On gradient- based learning in continuous games. SIAM Journal on Mathematics of Data Science, 2(1):103-131, 2020.
[41] Eric V Mazumdar, Michael I Jordan, and S Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv:190..00 190100088,, 2019.
[42] Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually converge? In International Conference on Machine Learning, pages 3481-3490, 2018.
[43] Vaishnavh Nagarajan and J Zico Kolter. Gradient descent gan optimization is locally stable. In Advances in Neural Information Processing Systems, pages 5591-5600, 2017.
[44] Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Advances in Neural Information Processing Systems, pages 2216, 2016.
[45] Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. In Advances Neural Information Processing Systems, pages 14934 14942, 2019.
[46] Ioannis Panageas and Georgios Piliouras. Gradient descent only converges to minimizers: Non-isolated critical points and invariant regions. In Innovations in Theoretical Computer Science Conference, 2017.
[47] Boris Teodorovich Polyak. Gradient methods for minimizing functionals. Zhurnal vychisittl noi matematiki i matematicheskoi fiziki, 3(4):643-653 1963.
[48] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-convex-conent min- max optimization: provable algorithms and applications in machine learning. Optimization Methods and Software, pages 1-35, 2021.
[49] Lillian J Ratliff, Samuel A Burden, and S Shankar Sastry. Characterization and computation of local Nash equilibria in continuous games, In Allerton Conference on Communication, Control, and Computing, pages 917-924, 2013.
[50] Lillian J Ratliff, Samuel A Burden, and S Shankar Sastry. Genericity and structural stability of non-degenerate differential Nash equilibria. In American Control Conference, pages 3990-3995, 2014.
[51] Lillian J Ratliff, Samuel A Burden, and S Shankar Sastry. On the characterization of local Nash equilibria in continuous games. IEEE Transactions on Automatic Control, 61()):2301-2307, 2016.
[52] S. Shankar Sastry. Nonlinear Systems Theory. Springer-Verlag, 1999.
[53] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018.
[54] Matthew Staib, Sashank Reddi, Satyen Kale, Sanjiv Kumar, and Suvrit Sra. Escaping saddle points with adaptive gradient methods. In International Conference on Machine Learning, pages 5956-5965, 2019.
[55] Gerald Teschl. Ordinary differential equations and dynamical systems, volume I 140. American Mathematical Society, 2000.
13

---

[56] Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael Jordan. Stochastic cu- bic regularization for fast nonconvex optimization. Advances in Neural Information Processing Systems, 201 11:2899-2290,, 2018.
[57] Jun-Kun Wang, Chi-Heng Lin, and Jacob Abemnethy. Escaping saddle points faster with stochastic momentum. In International Conference on Learning Representations, 2019.
[58] Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. In International Conference on Learning Representations, 2020.
[59] Zhongruo Wang. Krishnakumar Balasubramaniann, Shiqian Ma, and Meisam Razaviyayn. Zeroth-order algorithms for nonconvex minimax problems with improved complexities. arXiv:2001.07811 2020.
[60] Tengyu Xu, Zhe Wang, Yingbin Liang, and H Vincent Poor. Gradient free minimax optimization: Variance reduction and faster convergence. arXiv:2006.09.60 09361, 2020.
[61] Yi Xu, Rong Jin, and Tianbao Yang. First-order stochastic algorithms for escaping from saddle points in almost linear time. In Advances in Neural Information Processing Systems, pages 5530-5540, 2018.
[62] Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for a class of nonconvex-nonconeee minimax problems. Advances in Neural Information Processing Systems, 2020.
[63] Guojun Zhang, Pascal Poupart, and Yaoliang Yu. Optimality and stability in non-convex-now concave min-max optimization. arXiv:2002.11875 2020.
[64] Guojun Zhang, Kaiwen Wu, Pascal Poupart, and Yaoliang Yu. Newton-type methods for minimax optimization. arXiv:2006. 14592, 2020.
[65] Siqi Zhang, Junchi Yang. Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of noncomvex-strongly-conees minimax optimization. In Conference on Uncertainty in Artificial Intelligence, 2021.
[66] Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. Journal of machine learning research, 21:1-63, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See conclusion of paper.
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See the stated assumptions in the paper and the appendix.
(b) Did you include complete proofs of all theoretical results? [Yes] See the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [N/A]
14

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "l1BjRP-HFX", "reviewer": "Reviewer_kefj", "summary": "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.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I will start by saying that the fact that local minimax points are stable for non-convex strong concave or PL landscapes is not suprising since effectively the hessian with respect to y is negative definite (invertible) and all degenerecies are avoided (we can decide about stability by checking the eigenvalues of the hessian and not cheking third order terms) and moreover use the multiplicative property of the determinant and Schur complement to derive a relation between the eigenvalues of the Hessian, the lower right block matrix of the Hessian and its schur complement. What seems a bit more interesting is that all the other critical points are unstable (I feel that every critical point that is unstable, it is unstable because of the x variables (for the examined landscapes), is this true? The fact that we have convergence to local minimax is not surprising (similar result appears in https://arxiv.org/abs/1902.08297), I like though that the authors use potential argument to show this fact.\n\nThe result about SGDA follows standard machinery for perturbed GD dynamics (see Jin et al 2017) and the \\tilde{O}(1/\\eps^4) was expected. Overall, I think the paper is an interesting but not super strong. Can also the authors argue about constructing functions (non-convex in x and PL condition in y) with a critical point the corresponding matrix of which has at least one imaginary eigenvalue (for the continuous time dynamics)? Which parts of the proofs carry over for constrained min-max optimization?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is theoretical and the reviewer does not see any societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "K5giymVGZef", "reviewer": "Reviewer_ZYYQ", "summary": "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.\n\nOverall, this paper gives some theoretical contributions, with the caveat for the clarifications of the assumptions and the shortage of empirical studies. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "For the theory, there are a few assumptions that need clarification and further clarification on novelty. Theorem 1 is established for non-convex PŁ games. Theorem 1 looks like a corollary of  [Theorem 1, 15].  Moreover, Theorem 1 does not give the choice of $\\tau_*$. Although the PŁ and SC conditions bring the global asymptotic convergence of $\\tau$-GDA and $\\tau$-PGDA, the results of Sec. 5 and 6 are familiar with non-convex optimization researchers. Therefore, the authors should include the results of [15]  in Table 1. \n\nMoreover, this paper ignores the empirical studies at all. The authors claim that fair classification, adversarial training, and distributionally robust optimization belong to the class of games they consider. None of these applications are conducted in the paper. It intensified the reviewers’ concerns about the above assumptions. Although the code is in the supplementary material, numerical visualization is an indispensable part. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "-Js0BTR_Zph", "reviewer": "Reviewer_gXSR", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies a significant topic that belongs to a vibrant research field. The paper is easy to follow and clearly written.\nDespite being extensively studied in the past few years, the authors distinguish the paper by obtaining more stringent convergence guarantees. More specifically, they obtain convergence guarantees in regards to differential Stackelberg equilibria compared to assessing convergence to approximate stationary points in past works. The results presented are not very surprising since Danskin's (or a Danskin's like) theorem holds for these classes of non-convex settings. However, the results are not trivial and cleanly developed. \n\nI have the following concerns:\n\n1. Some practical examples presented in section 1.2 do not apply to the non-convex PL/SC settings. Also in equation (3), should it be f_i?\n\n2. Line 162: I believe the gradient does not always exist.\n\n3. The authors define the constrained min-max problem, but then study the unconstrained problem. Also why f^* is defined in line 379.\n\n4. A major concern is that the paper lacks experimental results. Motivating the class of problem under study with practical examples and  illustrating the results through empirical results would help improve the paper.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors study the behavior of simultaneous gradient descent-ascent with timescale separation (i.e. a slower learning rate for the descent dynamics compared to the ascent dynamics) to solve unconstrained and sequential min_x max_y f(x,y) optimization problems for objectives f(x,y) that are nonconvex wrt the variables of the outer (min) player and strongly concave or satisfy the PL condition wrt to the variables of the inner (y) player. 

They focus on the stability analysis and convergence rates of GDA (and its perturbed gradient variant) to local minimax points. The definition of local min-max points is that the max player plays a global best response to min, while 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, as long as the learning rate of the inner/max player is large enough compared to that of the min player. For nonconvex-strongly concave landscapes, they also show convergence in \tilde{O}(1/\eps^2) of perturbed GDA to an \esp- local min-max  and \tilde{O}(1/\eps^4) of perturbed SGDA.

Prior work had shown convergence to stationary points of \max_{y \in B} f(.,y) (for a slightly different algorithm) and this work does stability analysis to argue that the points it converges to are actually local minima. Stability analyses had also been done for related algorithms. So at a high level the results here are not surprising. Yet, they are not trivial. Doing the complete analysis to establish the results requires quite a bit of work, and this is the first paper that goes beyond stationarity. Given that min-max optimization for objectives that are not convex-concave is an interesting direction for the field, this is a solid contribution. 
Decision: Accept (Poster)