Two-timescale Extragradient for Finding Local Minimax Points
Authors: Jiseok Chae
Kyuwon Kim
Donghwan Kim
Venue: ICLR 2024 poster (2024)
Keywords: Minimax optimization
Nonconvex-nonconcave optimization
Extragradient method
Dynamical systems
Primary area: optimization
TL;DR: We characterize to which points the extragradient method with timescale separation converges, and show that those points are related to local minimax points.

Abstract: Minimax problems are notoriously challenging to optimize. However, we present that the two-timescale extragradient method can be a viable solution. By utilizing dynamical systems theory, we show that it converges to points that satisfy the second-order necessary condition of local minimax points, under mild conditions that the two-timescale gradient descent ascent fails to work. This work provably improves upon all previous results on finding local minimax points, by eliminating a crucial assumption that the Hessian with respect to the maximization variable is nondegenerate.

Published as a conference paper at ICLR 2024
TWO-TIMESCALE EXTRAGRADIENT FOR FINDING LOCAL MINIMAX POINTS
Jiseok Chae, Kyuwon Kim & Donghwan Kim
Department of Mathematical Sciences, KAIST (jsch, kkw4053, donghwank m) é @kaist.ac:
ABSTRACT
Minimax problems are notoriously challenging to optimize. However, we present that the two-timescale extragradient method can be viable solution. By utilizing dynamical systems theory, we show that it converges to points that satisfy the second-order necessary condition of local minimax points, under mild conditions that the two-timescale gradient descent ascent fails to work. This work provably improves upon all previous results on finding local minimax points, by climinating a crucial assumption that the Hessian with respect to the maximization variable is nondegenerate.
INTRODUCTION
Many noteworthy modern machine learning problems, such as generative adversarial networks (GANs) (Goodfellow al., 2014), adversarial training (Madry et al., 2018), and sharpness-aware minimization (SAM) (Foret et al., 2021), are instances of minimax problems, formulated as ming maN, fxx y). First-order methods, such as gradient descent ascent (GDA) (Arrow et al., 1958) and extragradient (EG) (Korpelevich, 1976), workhorses of minimax optimization in modern machine learning, but they still remain remarkably unreliable. This in contrast to the remarkable success of gradient descent for minimization problems machine learning, which is supported by theoretical results; under mild conditions, gradient descent converges to a local mini- mum, and almost surely avoids strict saddle points (Lee al., 2016; 2019). Minimax optimization, however, lacks such comparable theory, and this paper is a step towards establishing it.
If the problem is convex- conecx,, then by Sion's minimax theorem (Sion, 1958), the order of min and max is insignificant. However, modern machine learning problems are highly nonconvex- nonconcave, and thus their order does matter. Indeed, one of the complications in training GANs, called the mode collapse phenomenon, is considered to be due to finding solution of a max-min problem, rather than that of the min-max problem (Goodfellow, 2016). The widely used notion of saddle points, also called Nash equilibria, fails to capture the ordered structure of minimax prob- lems (Jin et al., 2020). Accordingly, Jin et al. (2020) introduced a new appropriate notion for local optimum in minimax problems, called local minimax points, built upon Stackelberg equilibrium from sequential game theory (von Stackelberg, 2011), which encompasses the Nash equilibrium.
Yet, how one find such local minimax points (possibly via first-order methods) is still left an open question. A partial answer was provided also by Jin et al. (2020); they showed that the swo- timescale GDA (Heusel et al., 2017), i.e., GDA with different step sizes for x and y, converges to certain (but not any) local minimax points. In particular, they only covered the case where the Hes- sian with respect to the maximization variable / is nondegenerate, which disregards possibly meaningful "degenerate" local optimal points, e.g., in peerpparaeeerrieed training (Liu et al., 2022). In this paper, we show that the two-timescale EG can actually find local minimax points beyond the assumption that Vi is nondegenerate. So, our main contribution is providing more complete answer the aforementioned open question. Our specific contributions can be listed follows.
In Section 3, we derive a second order characterization of local minimax points, without assuming that 2 f is nondegenerate. In doing so, we introduce the notion of restricted Schur complement. This leads to a natural way of defining strict non-minimax points that we would like to avoid, analogous to the strict saddle points in minimization.

---

Published as a conference paper at ICLR 2024
In Section 4, we develop new tools to achieve the main results in Section 5. These tools in- clude a new spectral analysis that does not rely on the nondegeneracy assumption on yg well as the concept of hemicurvature to better understand the behavior of cigenvalues.
In Section 5, from dynamical system perspective, we show that the limit points of the two-timescale EG in the continuous time limit are the local minimax points under mild conditions, by establishing second order property of those points. This continuous-time analysis is then used to derive a similar conclusion in the discrete-time case. In the discrete- time case, Section 5.4 further shows that two-timescale EG almost surely avoids (undesir- able) strict non non-miniman points, as desired, while Section 4.3 shows that two-timescale GDA may avoid (desirable) local minimax points where wy is degenerate.
In Section 6, we extend the local result of Section to a global statement: under the Minty variational inequality (MVI) condition (Minty, 1967) and additional mild conditions, the two-timescale EG globally converges to local minimax points.
2 PRELIMINARIES
2.1 NOTATIONS AND PROBLEM SETTING
The spectrum of a square matrix A, denoted by spec(A), is the set of all eigenvalues of A. The range of matrix A, denoted by R(A), is the span of its column vectors. The open left (resp. right) half plane, denoted by C (resp. CD), is the set of all complex numbers such that Re z < (resp. Re > 0). The imaginary axis is denoted by iR. To denote the minimization variable x E Rd and the maximization variable y E T2 at once, we use the notation z == (ar, y). Let C2 be the set of twice continuously differentiable functions. The saddle-gre goaddieg operator of the objective function f will be denoted by F == (Vzl,- -V,), and the derivative of F will be denoted by DF. When necessary, we will impose the following standard assumption on f.
Assumption 1. Let f C2, and there exists L > 0 such that [[F[(=)] S fforr all z.
2.2 LOCAL MINIMAX POINTS
Jin et al. (2020) introduced the following new notion of local optimality for minimax problems.
Definition 1 (Jin et al. (2020)). A point (x" "e""")) " is said to be local minimax point if there exists
50 > and a function satisfying h(5) + 0 as + 0 such that, for any (0, 8o] and any (æ, y)
satisfying ||æ x²1 < 5 and ly y² < 8, we have
max f(x", 4) f(x", v²) V 11y -3 ((M)
f(x, y
(I)
Local minimax points can be characterized by the following conditions (Jin et al., 2020).
(First-order necessary) For f E C², any local minimax point 2" satisfies Vf(=", yy" 0.
(Second-order necessary) For f E C2, any local minimax z" satisfies wy f(x' yy 0. In addition, if fx=", ,,r",""""" y²) < 0, then (V2.. V (V? () f) yz fl (x: .y") )* > 0.
(Second-order sufficient) For f C², any stationary point satisfying
2 / f) -V2 2g flx",, yy))
and V2 f
0
(2)
is a local minimax point.
Here, the second-order necessary condition is loose when V / works mostly overlook this diserepancy between that and the second-order sufficient condition (2), and focus only on the strict' local minimax points (Jin et al., 2020), also known as differential Stackelberg equilibria (Fiez et al., 2020), which are the stationary points that satisfy (2). We close this gap Section 3, and consider broader set of local minimax points later sections.
/ is degenerate. However, the existing
'The term strict used here is slightly more restrictive than that in the usual strict notion of local optimum in minimization; see e.g. (Wright& & Recht, 2022, 15))
2

---

Published as a conference paper at ICLR 2024
2.3 GRADIENT DESCENT ASCENT AND EXTRAGRADIENT
This paper considers the following two standard gradient methods (with time separation introduced later). Here, 1) denotes the step size.
Gradient descent ascent (GDA) (Arrow et al., 1958): Extragradient (EG) (Korpelevich, 1976):
2b+1 = 2/ (=F)
-k++ 2k n (#*))
We also consider their continuous time limits, as the analyses in continuous time is more accessible than their discrete counterparts. The analyses in discrete time, which is more of our interest, can be easily translated from the continuous time limit analyses. Taking the limit as - 0. both GDA and EG share the same continuous time limit 2(t) -F(x(t)). However, it is also known that even when f is convex-concave, EG converges to an optimum, while GDA and =(1) = -F((()) may not (Mescheder al., 2018). This distinction suggested need for ODEs with higher order of ap- proximation. In partieular, Lu (2022) derived the ODE s(1) = - F() - (v/2) D (=((()) ((=())(((()))) (() as the (ppaappproinnnooon of EG, the sense that captures the dynamics of EG up to order (n) as 1 + 0. In our dynamical system analyses, we found the following to be particularly more useful.
Lemma 2.1. Under Assumption 1, let = 7/2 and 0 s < 1/L. Then, the ordinary differential a (pprrxxpxoinntoionn of EG.
equation ((t) = -I +
2.4 DYNAMICAL SYSTEMS
This paper analyzes (two-timescale) GDA and EG methods through dynamical systems, in both continuous-time and discrete-time. In particular, determine whether an equilibrium point =" is asymptotically stable, which means that a trajectory starting at a point that is sufficiently close to z" will remain close enough and eventually converge z". We adopt the following widely used criteria, which we refer to as strict linear stability, as sufficient condition for an equilibrium to be asymptotically stable; see, e.g., (Khalil, 2002, Theorem 4.7) and (Galor, 2007, Theorem 4.8).
Definition (Linear stability of dynamical systems).
(i) (Continuous system) For C² mapping Φ. equilibrium point 2" of (()) Φ (())..). such that x(z²) = 0, is a strict linearly stable point if its Jacobian matrix at x* has all eigenvalues with negative real parts, i.e., spec(Do((* )) C C2.
(ii) (Discrete system) For C² mapping w, equilibrium point z" of zk+1 w(xx), such that xt = w(22). is strict linearly stable point if its Jacobian matrix at x" has spectral radius smaller than 1, i.e., p(Dw(zz) 1.
The set of unstable equilibrium points discrete dynamical system is similarly defined. Definition 3. Given a C mapping w, the set A (w) == (= x" = w(="), p(Dw(==)) > 13 is the set of strict linearly unstable equilibrium points.
We also study whether the methods avoid strictly non-optimal points in minimax problems, using the following theorem, built upon the stable manifold theorem (Shub, 1987). This was used by Lee al. (2019) to show that gradient descent in minimization almost surely escapes strict saddle points.
Theorem 2.2 (Lee et al. (2019, Theorem 2)). Let w be a C mapping such that det (et(Dw(z)) + for all z. Then the set of initial points that converge to strict linearly unstable equilibrium point has (Lebesgue) measure zero, i.e., p({zo lim (20) E A" (w)) = O.
ON THE NECESSARY CONDITION OF LOCAL MINIMAX POINTS
In minimization, both second-order necessary and sufficient conditions of local minimum are simply characterized by the Hessian of the objective function; see e.g., (Wright & Recht, 2022, Theorems 2.4 and 2.5). However, not similar simple correspondence between conditions for local minimax point was previously known, making it difficult to further develop a theory for minimax optimization comparable that in minimization. In this section, show that such correspondence in fact exists.
3

---

Published as a conference paper at ICLR 2024
3.1 RESTRICTED SCHUR COMPLEMENT
For the clarity of presentation, we first define a variant of Schur complement, named restricted Schur complement, which we will soon relate to second-order conditions of local minimax point.
From now on, we assume that f is twice continuously differentiable. Let us denote the second derivatives of f by A Vf Rd xd. B V vy E _d and C 2f E Rdixda Xd2, In particular we can express the Jacobian matrix of the saddle-gradient F as
H = = DF
A -C
C
TR (2)
Although A, B, and C' are, strictly speaking, matrix valued functions of (d1 + dimmennsila vector inputs, the point where those functions are evaluated will be clear from context, so we simply write A, B, and C to denote the function values.
Let = rank B). As B is symmetric, it can be orthogonally diagonalized as B = = PAPT, where A diag 6,.00 O,... 0) and is orthogonal. Let T be submatrix of C.P, which consists of the d2 r rightmost columns of CP, let q = rank (T), and let U E 1 be matrix whose columns form an orthonormal basis of ) Under this setting, we define the following. Definition 4. For a matrix H in the block form of (3), using the definition' of U given above, the restricted Schur complement is defined as Sres H) == U (A A CB CU E g))(1
........)
The positive semidefiniteness the restricted Schur complement Sres is related to the (generalized) Schur complement S := A CB C being positive semidefinite certain subspace, as follows. We remark that a 0 x matrix considered to be "vacuously" positive semidefinite.
Proposition 3.1. The restricted Schur complement Sces (H) is positive semidefinite if and only if v T Se 2 0 for any u E Rd satisfying C U E (B).
3.2 REFINING THE SECOND-ORDER NECESSARY CONDITION
We then have the following second-order necessary condition in terms of the restricted Schur com- plement, which is our first main contribution. Notice that when B is invertible, the restricted Schur complement becomes the usual Schur complement A CB- which appears in the second- order sufficient condition (2). Thus, the restricted Schur complement provides a unified point of view in considering both the necessary and sufficient conditions.
Proposition 3.2 (Refined second-order necessary condition). Let f C22 then any local minimax point (x:', 8²) satissfess V f (x", ,y") = O. In addition, if the function h(8) in Definition satisfies limsup;-404 h(6)/a < oc, then Remark 3.3. The additional condition on h in Proposition 3.2 slightly limits the choice of h, which determines the size of the set we take the maximum over in Definition 1. Hence, this can be terpreted restricting the local minimax points we are interested in, or alternatively, refining the definition of local minimax points itself: c.f., (Ma et al., 2023). Note, however, that such refined definition is yet much broader than the definition of strict local minimax points.
y²) 0.
Based on the refined second-order necessary condition, we define strict non-minimax points as be- low. These are the points hope to avoid, and the definition is analogous to that of strict saddle points in minimization problems (Lee et al., 2016). In Section 5.4, we show that two-timescale EG almost surely avoids strict non-minimax points.
Definition 5 (Strict non non-minimax point: T*). A stationary point x" is said to be a strict non- AminnSSuse minimax point of f if \miiu (Sres (DF(2z)) denotes the smallest eigenvalue of A. We denote the set of strict non- non-minimax points by T
O Amin Xmin (yy < O, where Xunin (A)
When necessary, will impose the following assumption stationary points 2" that is weaker than the nondegeneracy condition on 42 f(²),, which was crucial in all existing literatures.
A matrix U is not unique in general, but there ways to fix the choice of U. e.g., applying predeter- mined QR factorization algorithm on r. However, because only the spectrum of S.e, (H) will be important the subsequent analyses, we do not specify the choice U.
A similar matrix has also been considered by Zhang et al. (2022, Theorem 4.4), but part of local optimality condition for quadvatic problems only.
4

---

Published as a conference paper at ICLR 2024
Assumption 2.
For stationary point z' in consideration, at least of the matrices (De((D((2)) and f is nondegenerate.
Example 1. We provide two simple representative examples of "non-strict" local minimax points satisfying Assumplion 2, especially with nondegenerate Sies (DF) and degenerate V
f6(2, xy has unique local minimax point 0 (0,0);
x222 Viys has non-unique and non-isolated local minimax points 10,0,,,0,7 0),, all E R.
fq(11, T2, y1, V2. ya) = txp
- 1y y 2
See Appendix D.3 for the details and proofs. Later in Examples 2, and 4, show that our proposed two-timescale EG finds these optima, while GDA (and its timescaled variant) avoids them.
Only when characterizing strict linear stability of equilibrium points in Sections 5.2 and 5.3, we will use the following slightly stronger version of Assumption 2.
Assumption 2'. For z" in consideration, in addition to Assumption 2, DF(=*) is nondegenerate.
4 CHARACTERIZING TIMESCALE SEPARATION WITHOUT NONDEGENERACY
CONDITION ON V f
In this section we begin with reviewing the close relationship between two-timescale GDA and strict local minimax points, under nondegeneracy condition on V fzz"(=²)) (Jin al., 2020). Then, extend this to more general setting without such nondegeneracy condition, and observe a negative result stating that two-timescale GDA avoids some degenerate local minimax points.
4.1 TIMESCALE SEPARATION IN GDA AND ITS RELATION TO STABILITY
Let recall the two-timescale GDA method, which is GDA with timescale separation with timescale parameter т 2
*k+1 = w (zx) = 2k -A,
where A, = diag
(4)
and its continuous time limit =(t) -(z)(zt))). The stability of (4) and its continuous limit depends the spectrum of timescaled matrix
34 cc
H. A,H
- -B
Jin et al. (2020) studied the following asymptotic behavior of its spectrum 1/r - O, under nondegeneracy condition on V f2²")
Lemma 4.1 (Jin al. (2020, Lemma 40)). Suppose that B V f2") is nondegenerate. Then, the d1 d2 complex eigenvalues X, of H, have the following asymptotics
1/7 0+:
- o(e), j= I,...... d1,
Dij+di 13y o(1), j= d2.
where μúj and vj are the eigenvalues of CB-ICT and B, respectively.
The eigenvalues of H- become related to the definition of the strict local minimax point (2) as + O, and this was used to show that GDA with sufficiently large timescale separation converges strict local minimax point in Fiez & Ratliff (2021, Theorem 1), and also Jin al. (2020, Theorem 28).
Theorem 4.2 (Fiez. & Ratliff (2021, Theorem 1)). For f E C² and its stationary point x* with det( (V"yy(z"))
the point z" is strict local minimax point and only if there exists a constant T* > such that the point z" is strict linearly stable for two-timescale GDA with any 7 > T².
This seems to be complete, but this tells us nothing about when the nondegeneracy condition on V2 fx") is removed. So, the timescaled matrix H,, and investigate the stability of the two-timescale GDA without such nondegeneracy condition.
next step, generalize Lemma 4.1, the spectral analysis of
5

---

Published as a conference paper at ICLR 2024
4.2 TIMESCALE SEPARATION WITHOUT THE NONDEGENERACY CONDITION ON V f
Mimicking how we constructed the restricted Schur complement (in Definition 4 and above), we can reduce H, into a simpler form without changing the spectrum. More precisely, for a block diagonal matrix Q -diag{ I, J. the matrix QH,Q' the same spectrum with H-. Thus, by replacing C' with CP necessary, we may assume without loss of generality that B is diagonal matrix. Moreover, with r rank( B). we may further assume that there exists a diagonal D E R with nonzero diagonal entries where B is of the form B - 0 Then subdivision C = [Ci C2] arises naturally, where C1 is constructed from C by taking the leftmost columns, and C2 takes the rest. Note that 9 rank (T)
1 tCP is similar to H,, hence has (CP: -
rank rank(C2).
Using these notations, we can characterize the asymptotic behaviors of the eigenvalues of H,, when > 20, in the following theorem. This reduces to Lemma 4.1 when r d2 (and thus g = 0)- Theorem 4.3. Let A E fgdixd1 be square matrix, and let B Rdaxda and C E R x be matrices in the form that is discussed above. Assume that I E C Then, under Assumption 2, for T 21 and c == 1/T, it is possible to construct continuous fanctions X²(c). j = .,...: d1 + d2 so that they are the d + d2 complex eigenvalues of H,, with the following asymptotics as - 0+:
(i) 12g i0, Vel = =(v]), D4s+d + = o(VE).
j 9.
(ii) Dii+o Ep2z = o(E).
j
d1
(iii) 1ytdi+t - - o(1).
j 1,...,T. T
with being nonzero whenever e > O while the remaining d2 - 9 - r are constantly O. Here, μj are the eigenvalues of the restricted Schur complement Sres (H), Vj are the nonzero eigenvalues of B. and oj are the singular values of Cz.
As we remove the nondegeneracy condition on B. the d1 q eigenvalues of type (ii) are now related to the eigenvalues of the restricted Schur complement S rather than the Schur complement as in Lemma 1. This illustrates a close connection to the refined second-order necessary condition. Nevertheless, the overall form of the asymptotic behavior of the eigenvalues of types (ii) and (ii) remains unchanged from that of Lemma 4. What differentiates Theorem 4.3 from Lemma 4.1 the most is the existence of the unprecedented 29 eigenvalues of type (i).
Example 2. Consider the bilinear function fs(z, = zy in Example 1. A straightforward com- putation gives spec(H, and Theorem 4.2 does not apply. In fact, spec(- -HH) & C² for any tion 2(i) one can see that a unique (non-strict) local minimiax point is not strict linearly stable for continuous titte GDA, even with timescale separation. Moreover, Definition 3 implies that the point is in fact rather a strict linearly unstable point for discrete-time two-timescale GDA.
{+ive). Notice that this spectrum cannot be explained by Lemma 4. I,
0, from Desini-
On the contrary, Theorem 4.3 exactly explains why spec(H,, is (Ei this is an example where spec H2) contains only the eigenvalues of rype (i). As we will see in Proposition 5.1 and 5.5, for equilibrium point to be strict linearly stable for EG with timescale separation, the spectrum spec Hz) must lie on a certain target set, which contains a deleted neighborhood of the origin in the imaginary axis. Thus, 0 becomes strict linearly stable for ww-eimese EG, as desired.
However, the general situation in terms of the type (i) eigenvalues is of course not always as simple as those in Example 2. This necessitated us to introduce the term hemicurvature of the eigenvalue function Xy (e), as in next subsection, to help identify whether spec H,) lie in certain target set.
4.2.1 HEMICURVATURE OF THE EIGENVALUE FUNCTION (c
Let us focus the eigenvalues of type (i), i.e., Xy with j I= (I........) +1...., di + g). Identifying the complex plane with R we may consider Ay(c) as a plane curve (Re Xy(c), Im (y))) parametrized by e. All that Theorem 4.3 tells us about >;(e) is that its leading term is of order ve, which determines the tangential direction of Ay. More precisely. Xς(e) converges to 0 as asymptotically in the direction along the imaginary axis. The complication here is that the target sets, mentioned in Example 2, for both GDA and EG happen to have the imaginary axis also as their tangential line at the origin. That is, the tangential information (Theorem 4.3) alone is not sufficient for our stability analysis. For further details, with figures, on this issue, see Appendix E.3.
0+

---

Published as a conference paper at ICLR 2024
The local canonical form of curves suggests investigating the curvature information of Xj. To this end, let us identify the coordinate functions Re(Ay) and Im(Ay), when j E T. By reindexing the singular values of C2 for notational convenience, we already know that Im()y) =io,
To characterize Re(A)). by identifying H, c one can use a classical result from perturbation theory (see, e.g., Section 11.1.2 of (Kato, 1995)) to (k) expand (E) into convergent Puiseux series Aş(E) -x= a e for some positive integer Pj- Let ky be the smallest & such that Re (k)
el 61 a perturbed linear operator,
; * 0, and define 2j == ka/pp, Si a (ka) and Ej = Re Then, may write Re(2y) E + o(c ). Notice that 2j > 1/2. If such ky does not exist, then Re(A,) holds, so we may simply put @j = and & = O. Now, instead of the curvature itself, define and consider the following value, named hemicurvature:
bg
lim 00
(5,e%)"))/3 1//3-
In Proposition E.4 we show that the hemicurvature ij is equal to -122 times the curvature of the trajectory of Xy when e + O+. The reason we consider this quantity instead of the curvature is because not only it captures the curvature information, but also it is the limit of Re(1/>,) as e - 0; see Proposition E.5. This simplifies the subsequent analyses, as we see in Section 5.
4.3 TWO-TAMES GDA AVOIDS SOME VON-STRICT LOCAL MINIMAX POINTS
It is obviously desirable have method that converges the point is strict or non-strict. This unfortunately fails for two-timescale GDA, which almost surely avoids some non-strict local minimax points. We already saw such an instance in Example 2. More generally, consider the set X of non-strict local minimax points satisfying ij < '/2 for some j E I. We have a negative result below that timescale separation does not help GDA to converge to such non-strict points, despite being useful in converging to strict local minimax points.
optimal point, regardless of whether
Under Assumptions 1, 2 and < r < 1/1, there exists a constant T* > 0 such that for any > T", the set of initial points converging to z" by the discrete-time two-timescale GDA w has Lebesgue measure zero, i.e., pltzo lim4-400 (z = z }} = O.
Theorem 4.4. Let z" E X
LOCAL MINIMAX POINTS AND THE LIMIT POINTS OF TWO-TIMESCALE EG
In this section show that the two-timescale EG converges to stationary point that satisfies the refined second-order necessary condition mentioned in Proposition 3.1. We first show that such points with an invertible DF F are the strict linearly stable points of two-timescale EG. Then, we show that two- two-timesee timescale EG almost surely avoids a strict non- non-minimax point, even without the invertibility assumption on DF. These results are comparable to the convergence guarantees known for gradient descent on minimization problems-namely namely that gradient descent locally converges to local minima, and almost surely avoids strict saddle points (Lee et al., 2016).
Before we begin, we would like to remark that a point not being strict linearly stable for example because of DF being not invertible dobeleeeedeeseeeeeeo not imply that the point strict linearly unstable. In other words, the strict linear stability is sufficient but not necessary for method to find that point, as will soon be detailed in Section
5.1 TWO-TIMESCALE EG
We now consider the EG with timescale separation, to resolve the aforementioned avoidance issue of GDA. For simplicity in the analysis, we first work with the continuous time limit of EG, especially the high-order approximation version in Lemma 2. that have clear distinction from GDA. Applying the timescale separation on the ODE in Lemma 2.1 using A, as in (4), we get
(() = x (x(1) = I + =A, DF (x)))) - (=())).
(6)
Its discretization with s = 1/2, namely the two-timescale EG, becomes
1 / (zx) = 2 n, F(z Tj,, F(x)))
(7)
Their correspondence can be easily shown by following the proof of Lemma 2.1 with ||A||| < 1. From now on, will refer both of them simply as T-EG, and denote their Jacobian matrix, either
7

---

Published as a conference paper at ICLR 2024
DΦ, Dw,, as J,. Whether they are in terms of continuous time or discrete- time will be clear from the context. T E-EG takes the stationary points of F as its equilibria, see Appendix F.
The analyses of the stability properties are based on Definition 2, the Jacobian matrices, of the systems (6) and (7), play a central role. Hence, in this section, for convenience, the Jacobian matrix at given equilibrium point z' will be denoted by J; (="). Meanwhile, similar to Theo- rem 4.2, the upcoming stability results share a property of being held for all T larger than a certain threshold. So for simplicity, we introduce the following notion of xc-BG.
Definition 6, We say that z" is a strict linearly stable equilibrium point oo-EG if. there exists some T" such that, for any T > T" the point z" is strict linearly stable equilibrium point of T-EG.
5.2 RELATION WITH TWO-TIMESCALE EG CONTINUOUS--IIM
For the stability analysis of continuous-time two-timescale EG (6) in terms of Definition 2(),, we need examine spec( (Jt). but computing J, in general is cumbersome. However, there is simple characterization of s)) in terms of spec H;), where H == H, (z*). For < 1/z, define a subset of the complex plane D. = fz E C: |2 + 1/2a| I 1/2x} . which is closed disk centered -1/2- with radius 1/2s. Then we have the following fact, implying that the stability analysis of the ODE (6) can be done by examining spec spec(H;;, See Appendix G.2 for visualization of this statement, with a comparison to the continuous-time GDA.
Proposition 5.1. Under Assumption 1, (J) C C2 if and only ipep H;;) n D, = 2.
We are now ready to state our main stability result of two-timescale EG in terms of the refined second-order necessary condition. This states that under Assumption 2', for step size taken not too small, a point satisfying the refined second-order necessary condition strict linearly stable. Theorem 5.2. Suppose Assumptions I and 2'. Let so == maxjez(- (-))) for ij defined in (28). Then, an equilibrium point z" satisfies Sres 2 0, B 3 O, and s0 < 1/L if and only if there exists a constant 0 < 8* < 1/1 such that z" is a strict linearly stable point of c.-EG for any step size 8 E (8", 1/1).
Proof. Let us briefly sketch the proof, whose detail is deferred to Appendix G.4. For any j E I, using the hemicurvature lj in (5), it possible to determine whether the eigenvalues >i of H;; are in D. or not, using Lemma G.4. Then, combining this result with the behaviors of X3 where j I, which is established in Theorem 4.3, we can characterize exactly when does spec HH)) D, 2 hold. The conclusion then follows from Proposition 5.1 and Definition 2(1).
Although choosing step size s close enough to 1/2 would suffice in practice, it is possible that s may not be large enough in view of Theorem 5.2. Furthermore, the condition so I/L may not hold, and even checking such condition is challenging as one needs to compute all the hemicurvatures 1j- As complement, we provide stability conditions that do not depend on so (and consequently on s*).
Theorem 5.3. Let x" be an equilibrium point. Suppose Assumptions I and 2' hold.
(i) (Sufficient condition) Suppose that z" satisfies S > 0 and B < 0. Then for any step size 0 < s < 1/L, the point x" is a strict linearly stable point of oo-EG.
(ii) (Necessary condition) Suppose that x² is strict linearly stable equilibrium point of oG-EG for any step size < 8 < 1/z. Then, it satisfies S.o. Z 0 and B 330 O.
If we introduce mild additional assumption that all Jj values are distinct, Theorem 5.3 can be refined into a tight necessary and sufficient condition. This, however, excludes local minimax points that satisfy u. Su < O for some j. We leave treating such points for any given s future work.
Theorem 5.4. Under Assumptions I and 2', suppose that all oj values are distinct. Then, an equilibrium zt satisfies Sres 0, B = O, and u, Su, 2 0 for every left singular vector uj of C2 if and only if x* is strict linearly stable point of co-EG for any step size 0 < I/L.
5.3 RELATION WITH TWO-TIMESCALE EG IN DISCRETE-TIME
For the stability analysis of the discrete-time two-timescale EG (7), this time in terms of Def- inition 2(i1), we need examine spec(J,), and this can be similarly characterized in terms of
8

---

Published as a conference paper at ICLR 2024
spec(H;) For 77 < 1/L, define a peanut-shaped subset of the complex plane
Pg = {=
by E C: (yy-- - 1/2)² + n2²r² 8/4 < v + +1
(8)
containing a subset of iIR \ (0), as shown Appendix H.1. Then we have the following. See Appendix H.2 for visualization of this statement, with comparison to the discrete- time GDA. Proposition 5.5. Under Assumption 1, (())) < and only if spee H;;) C Ptr
We then analyze the stability of (7), using arguments similar to the continuous-tine counterparts. Theorem 5.6. Suppose Assumptions and 2' hold. Then, an equilibrium pecteiiiiiiiiiinnniii z" salisfies Stes Ž O, B 3 and so < 1/2L if and only if there exists a constant 17" <//L such that z" is a strict linearty stable point of co-EG for any step size satisfying 1)" < 1/L.
In Appendix H.5, we also provide stability conditions that do not depend So (and consequently on v7"), similar to the continuous-time analyses in Theorems 5.3 and 5.4.
Example 3. Consider the bilinear function fo(2, y) = xy in Example 1, and recall that spec(H, H {+ive]. Notice that spec(Hs H2) DDD Ø for any >> 0, and spee (xx) C Pr whenever is sufficiently small. Therefore, as mentioned Example 2, the local minimiax point is strict linearly stable for both continuous- and discrete-time two-timescale EG.
5.4 TWO-TIMESCALE EG ALMOST ALWAYS AVOIDS STRICT NON-MINIMAX POINTS
Using Theorem 2.2, we show that two-timescale EG almost surely avoids strict non-minimax points.
Theorem 5.7. Let z² be strict non-minimax point, i.e., z" E TT Under Assumptions 2, and < 1 < (V5-1)22 there exists > such that for any T 5", the set of initial points that converge to x" by two-timescale (discrete) EG w, has measure zero. Moreover, if is finite', then there exists r* > 0 such that for any T > T", p({20 lime- w E TT)))
This, however, does not mean that strict non-minimax points are always the only points that two- timescale EG almost surely escapes, as one would desire. Considering Theorems 5.6 and 5.7, this is possible if so < 1/2L. holds and we can choose the step size so that 17 < 17 < (v5-1)/21. Nevertheless, these conditions are somewhat restrictive and we leave removing them future work.
TWO-TIMESCALE EG GLOBALLY FINDS LOCAL MINIMAX POINTS
Our analysis has thus far been local, but can be extended to global statement. One can show that any accumulation point of the iterates computed by two-timescale EG stationary point, for in- stance under the Minty variational inequality (MVI) condition (Minty, 1967) which encompasses nonconvex-nonconcave settings; see Appendix With appropriate settings on 8g- 7), and T*, Theo- rem 5.7 guarantees almost sure avoidance of strict non-minimax points. Hence, under these settings, with Assumptions and 2 and assuming that the wwo-timescale EG converges and there are no non- strict con-minimax points, akin to the of gradient descent in (Lee et al., 2016, Theorem 1 11), we can conclude that the two- timescale EG globally and almost surely finds local minimax points.
As consequential result, max points even with a singular DF, i.e, some Xy of H, in Theorem 4.3 are zero, as demonstrated in the following example with non-isolated local minimax points.
have that two-timescale EG is also capable of finding local mini-
Example 4. Consider the quadratic function fq in Example Similar to the case of Example 2, since spec H,) 2, c, Hi/e), all (non-strict) local minimax points strict linearly unstable for discrete-time two-timescale GDA. Yet, while 0 spec H,), both C D, and P,, never contain O. Thus, unlike Example 3, the optima are not strict linearly stable for two-timescale EG. However, recall that a point not being strict linearly stable does not imply that the point is strict linearly unstable. Indeed, for this fa we have Su = 0 because {>₃ I =)= { and thus 1e" S O. Therefore, the local minimax points are not avoided by two-timescale EG. fact, any stationary point of this fa is local optimal point that satisfies the MVI condition (see Lemma J.3), hence the local optimal points are rather found by discrete-tin awo-timescale EG.
We defer the final discussions and a review on the related works to the appendices.
'If we assume that all points in T isolated and the iterates bounded, then T is essentially finite.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported in part by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2019RIA5AI0255 2022RICICI003940) and the Sam- sung Science Technology Foundation grant (No. SSTF-BA2101-02..
REFERENCES
K. J. Arrow, L. Hurwicz, and H. Uzawa. Studies in Linear and Non-Linear Programming, volume of Stanford Mathematical Studies in the Social Sciences. Stanford University Press, 1958.
H. Attouch and B. F. Svaiter. A continuous dynamical Newton-like approach to solving monotone inclusions. SIAM J. Control Optim., 49(2):574-98,, 2011.
A. Beck. Ordsr Methods in Optimization. SIAM, 2017.
Chae, Kim, and D. Kim. Open problem: Is there first-order method that only converges to local minimax optima? In Conference Learning Theory, pp. 5957-5964. PMLR, 2023.
Z. Chen, Z. Hu, Q Li. Z. Wang, and Y. Zhou. A cubic regularization approach for finding local min- imax points in nonconvex minimax optimization. Transactions on Muchine Learning Research, 2023.
C. Daskalakis and I. Panageas. The limit points of (optimistic) gradient descent in min-max opti- mization. In Neural Info. Proc. Sys., 2020.
J. Diakonikolas, C. Daskalakis, and M. Jordan. Efficient methods for structured nonconvex- nonconcave min-max optimization. In International Conference Artificial Intelligence and Statistics, pp. 2746-2754, PMLR, 2021.
M. P. do Carmo. Differential Geometry of Curves and Surfaces. Dover Publications, revised and updated second edition, 2016.
Y. G. Evtushenko. Some local properties of minimax problems. USSR Comp. Math. and Math. Phys., 14(3):129-13 118. 1974.
F. Farnia and A. Ozdaglar. Do GANs always have Nash equilibria? In Proc. Intl. Conf. Mach. Learn, 2020.
Fiez and L. Ratliff. Local convergence analysis gradient descent ascent with finite timescale separation. In Proc. Intl. Conf. Learning Representations, 2021.
T. Fiez, B. Chasnov, and L. Ratliff. Implicit learning dynamics in Stackelberg games: equilibria characterization, convergence analysis, and empirical study. In Proc. Intl. Conf. Mach. Learn, 2020.
Foret, A. Kleiner, H. Mobahi, and B. Neyshabur. Sharpness-aware minimization for efficiently improving generalization. In Proc. Intl. Conf. on Learning Representations, 2021.
O. Galor. Discrete Dynamical Systems. Springer, 2007.
I. Goodfellow. NIPS 2016 Tutorial:
Generative adversarial networks, 2016. arXiv 1701.00160.
I. J. Goodfellow, J. Bouget-Abadie M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial networks. In Neural Info. Proc. Sys., 2014.
E. Gorbunov, A. B. Taylor, S. Horváth, and G. Gidel. Convergence proximal point and extragradient-based methods beyond monotonicity: the case of negative comonotonicity. In Proc. Intl. Conf. Mach. Learn, 2023.
M. Heusel, H. Ramsauer, Unterthiner B. Nessler, and S. Hochreiter. GANs trained by a two time-scale update nule converge local Nash equilibrium. In Neural Info. Proc. Sys., 2017.
N. J. Higham. Functions of Matrices. SIAM, 2008
10

---

Published as a conference paper at ICLR 2024
R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 2nd edition, 2012.
C. Jin, P. Netrapalli, and M. I. Jordan. What is local optimality in nonconvex-nonconcave minimax optimization? In Proc. Intl. Conf. Mach. Learn, 2020.
T. Kato. Perlurbation Theory for Linear Operators. Springer, 2nd edition, 1995.
H. K. Khalil. Nonlinear Systems. Pearson, 3rd edition, 2002.
G. M. Korpelevich. An extragradient method for finding saddle points and other problems. Ekonomika Mateaticheskie Metody, 12(4):747-56, 1976.
D. Lee, M. Simchowitz, M. Jordan, and B. Recht. Gradient descent only converges minimiz- PMLR, 2016.
ers. In Conference on Learning Theory, pp.
J. D. Lee, I. Panageas, G. Piliouras, M. Simchowitz, M. I. Jordan, and B. Recht. First-order methods almost always avoid strict saddle points. Mathematical Programming, 176:31 1-337, 2019.
C. Liu, L. Zhu, and M. Belkin. Loss landscapes and optimization in werrpparameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85-116, 2022.
H. Lu. An "ress--nnolutionn ODE framework for understanding discrete-time algorithms and ap- plications to the linear convergence of minimax problems. Mathematical Programming, 194: 1061-1112, 2022.
X. Ma, W. Yao. J. Ye, and Zhang. Calm local optimality for noncomvex-noneoocany nonconcave minimax problems, 2023. arXiv 2306. 17443.
P. Mahdavinia, Y. Deng, H. Li, and M. Mahdavi. Tight analysis of extra-gradient and optimistic gradient methods for nonconvex minimax problems. In Neural Info. Proc. Sys., 2022.
L. Mescheder, A. Geiger, and S. Nowozin. Which training methods for GANs do actually converge? In Proc. Intl. Conf. Mach. Learn, 2018.
G. J. Minty. the generalization of a direct method of the calculus variations. Bull, Amer. Math. Soc, 73:314-322 321, 1967.
A. Madry, A. Makelov, L. Schmdit, D. Tsipras, and A. Vladu. Towards deep learning models resistant adversarial attacks. Proc. Intl. Conf. on Learning Representations, 2018
E. Ryu and W. Yin. Large-Scale Convex Optimization. Cambridge University Press, 2022.
E. K. Ryu, K. Yuan, and W. Yin. ODE analysis of stochastic gradient methods with optimism and anchoring for minimax problems and GAÑs, 2019. arXiv 1909.10899.
M. Shub. Global Stability of Dynamical Systems. Springer, 1987.
M. Sion. On general minimax theorems. Pacific Math., 8(1):171-6) 1958.
J. Stoer and R. Bulirsch. Introduction to Numerical Analysis. Springer, 3rd edition, 2002.
T. Tao. Analysis II. Springer, third edition, 2016.
H. von Stackelberg. Market Structure and Equilibrium. Springer, 2011.
Y. Wang, G. Zhang, and J. Ba. On solving minimax optimization locally: A follow-the-ridge ap- proach. In Proc. Ini. Conf. on Learning Representations, 2020.
S. J. Wright and B. Recht. Optimization for Data Analysis. Cambridge University Press, 2022.
M. Zedek. Continuity and location of zeros of linear combinations of polynomials. Proceedings of the American Mathematicul Society, 16(1):78-88) 1965.
G. Zhang, K. Wu, P. Poupart, and Y. Yu. Newton-type methods for minimax optimization, 2020. arXiv 14592.
G. Zhang, Poupart, and Yu. Optimality and stability in non-convex smooth games. J. Mach. Learn. Res., 23:35-1, 2022.
11

---

Published as a conference paper at ICLR 2024
CONTENTS
Introduction
2
Preliminaries
2.1
Notations and problem setting
2.2
Local minimax points
2.3
Gradient descent ascent and extragradient
2.4
Dynamical systems
3
On the necessary condition of local minimax points
3.1
Restricted Schur complement
3.2
Refining the second-order necessary condition
4
Characterizing timescale separation without nondegeneracy condition on
V
4.1
Timescale separation in GDA and its relation to stability
4.2
Timescale separation without the nondegeneracy condition on V yy f
4.2.1
Hemicurvature of the eigenvalue function Λy(E)
4.3
Two-timescale GDA avoids non-strict local minimax points
5
Local minimax points and the limit points of two-timescale EG
5.1
Two-timescale EG
5.2
Relation with two-timescale EG in continuous-time
8
5.3
Relation with two-timescale EG in discrete-time
5.4
Two-timescale EG almost always avoids strict non-minimax points
Two-timescale EG globally finds local minimax points
Discussions
13
B Related works
14
C Proofs and Missing Details for Section 2
14
C.I Proof of Lemma 2.1
14
C.2 Further discussions on the new ODE
14
Proofs for Section
15
D.I Proof of Proposition 3.1
15
D.2 Proof of Proposition 3.2...
15
D.3 Proof of Example
16
Proofs and Missing Details for Section 4
16
E.1 Proof of Theorem 4.3
16
12

---

Published as a conference paper at ICLR 2024
E.2 Proofs the properties of the hemicurvature
21
E.3 On the necessity of considering the hemicurvature
22
E,4 Proof of Theorem 4.4
Proof for Section 5.1
23
G Proofs and Missing Details for Section 5.2
24
G.1 Proof of Proposition 5.1
24
G.2 Target sets continuous- time methods
25
G.3 A consequence of Assumption 2'
26
G.4 Proof of Theorem 5.2
26
G.5 Proof of Theorem 5.3
27
G.6 Proof of Theorem 5.4
30
H Proofs and Missing Details for Section 5.3
33
H.1 On the peanut-shaped region Pa
33
H.2 Target sets of discrete-ting methods
H.3 Proof of Proposition 5.5
H.4 Proof of Theorem 5.6
35
H.5 Additional stability conditions of two-timescale EG in discrete-tine
36
H.6 Proof of Theorem H.3
36
H.7 Proof of Theorem H.4
37
Proof for Section 5.4
37
1.1 Proof of Theorem 5.7
37
J Global convergence analysis of two-timescale EG
38
A DISCUSSIONS
We demonstrated that two-timescale extragradient converges to local minimax points without a non- degeneracy condition Hessian with respect to the maximization variable, from dynamical sys- tem viewpoint. We have then shown that two-timescale extragradient almost surely avoids strict non-minimax points, using theorem built upon the stable manifold theorem. To the best of our knowledge, this is the first result in minimax optimization that attempts to fully characterize the stability behavior near stationary points, comparable to that of gradient descent in Lee et (2016).
Still, our work is just a takeoff in exploring first-order methods for finding non-strict local minimax points, leaving several unanswered questions. While our results state that they hold whenever the timescale parameter is sufficiently large, we do not discuss how large exactly should be. A slight gap remains between the second order necessary and sufficient conditions of local minimax points, due to the additional condition h given in Proposition 3.2. The analysis of the limit points of two-timescale EG involves conditions on S.e and sp- For further discussion, we advise the reader refer to (Chae al., 2023). Investigations these issues will lead interesting future works.
13

---

Published as a conference paper at ICLR 2024
B RELATED WORKS
Equilibria in minimax problems Nash equilibrium a widely used notion of (local) optimality in minimax optimization, especially when minimax problems are interpreted as simultaneous games, where both players act simultaneously (Jin et al., 2020). However, there are problems that do not have local Nash equilibrium point including realistic GAN applications (Farnia & Ozdaglar, 2020). In fact, the correct way of interpreting minimax problems, especially in modern machine learning applications. are as sequential games (Jin et al., 2020). These necessitated a new notion of local optimality that reflects the sequential nature of minimax optimization. The notion of local opti- mality in sequential games, built upon Stackelberg equilibrium (von Stackelberg, 2011), was first introduced by Eytushenko (1974), but this was later found to be not truly local (Jin et al., 2020). Instead, Fiez et al. (2020) and Jin et al. (2020) considered another notion of (true) local optimum, called strict local minimax points, which are exactly the points satisfying the sufficient condition of local optimum proposed by Evtushenko (1974). This, however, only covers the cases where Vyy! is nondegenerate, hence disregards possibly meaningful "non-strict" local optimal points, e.g., in over-parameterized training (Liu et al., 2022).
So, Jin al. (2020) also introduced max points; see Section 2.2 for more details. To the best of our knowledge, all existing methods in Evtushenko (1974); Fiez al. (2020); Wang al. (2020); Zhang al. (2020): Chen et al. (2023), even that in Jin et al. (2020), focus on finding only strict local minimax points.
general definition of local optimum, named local mini-
Two-timescale methods Plain GDA can converge to nonoptimal points (Daskalakis & Panageas, 2020; Jin et al., 2020). So, Jin et al. (2020) adopted (computationally cheap) timescale separation into GDA, i.e., using different timescales, or step sizes, for each player's action. two-timescale GDA with sufficiently large timescale separation converges to strict local minimax points (Jin et al., 2020; Fiez & Ratliff, 2021). Recently, two-timescale EG was studied Zhang et al. (2022); Mahdavinia et al. (2022), but it was only shown to behave similar to the two-timescale GDA; this paper demonstrates the particular usefulness of two-timescale EG when V f is degenerate.
proven that
C PROOFS AND MISSING DETAILS FOR SECTION 2
C.I PROOF OF LEMMA 2.1
Letting n/ the ODE derived by Lu (2022), mentioned in Section 2.3, can be written as
{1) = F=(()) + 2 (F(=(())F((()) = -1 (DL=))F((()))((((()
(9)
As we assume that 0 < < 1. by Assumption the matrix I + sDF(2) is invertible. Applying the approximation +I+ sD sDF - O(s)), the ODE
*(1) =
(10)
can then be seen as an approximation of (9).
C.2 FURTHER DISCUSSIONS ON THE NEW ODE Let (t) = F(z(t)). Using the chain rule, we have
D DF(2()))()== = -()))
Therefore, (10) is equivalent to
(t) = -(((t)) = (I (())
(1I)
= =((() + st).
We would like to mention that special case of (11) when has originally been studied
continuous- time limit of the Newton's 's method by Attouch & Svaiter (2011), and also as that of the optimistic GDA by Ryu et al. (2019).
14

---

Published as a conference paper at ICLR 2024
D PROOFS FOR SECTION 3
D.1 PROOF OF PROPOSITION 3.1
We use P. P and U that are introduced above Definition Interpreting as a change-of-basis matrix, we have C' The latter holds and only if is orthogonal to the last (d2 - r) columns CP,, or in other words, if and only if v 1 (T).
R(B) if and only if the last (d2 r) components of P C' v are zero.
Let W = R( 1 and w = dim W. If w = O, then this means that the zero vector the only vector such that C v E R (
there is nothing show. Assuming 2 1, by how U is constructed, we have v E W if and only if there exists u E IR" such that v = Uw. Hence, the condition
T (A CB C y 2 0 for any satisfying C' R(B) equivalent to having
w T (A- CB-CBBC
UUW Uw = w Sreg w 2 0
for any w E R
D.2 PROOF OF PROPOSITION 3.2
Proof. Let A = f=n B V ff y²), and C = fx" ,y). Since y" is a local maximum of f(x", ). it holds that B = 0.
Because (x",y") is local minimax point, there exists function h such that (1) holds. Moreover, by the assumption we made on h, there exist dj and constant M such that 8 < M whenever 0 < 5 I d1. We may then replace do in Definition 1 by min(5p. (5,, 51} without affecting the local optimality, other words, without loss generality we may assume that
h(8) 5
S
M whenever
< 5 80
(12)
holds in Definition Let denote h²(6) max (1 16).
Using the first order necessary condition, we have
1 18 Bö, + R(6,, 6,)
f(x -. 3n + +yy) =f(x", yy"
Ad 5J C8, 20
(13)
where R(6 6y) is the remainder term of a degree 2 Taylor series expansion. Now let assume that |6 = 5 (0, do] and C 8x E R(B). Then, by the second order necessary assumption B 0, it holds that
- argmax f(x", ((x",x")= + 2 00 Ad + 6_ Co, + o Bög
by
Mcanwhile, let >> 0 be arbitrary. Then, noticing that
R(6 6y) o(118x] 2 + 11,,,)
know that there exists 82 > 0 such that
R(6 8y)
|| ||
82
|
|18y11
Here, || < (()), then by (12) and that 5 < do we have
| 2 + |6,,]l
|8 12
h((6)
=1+
1
51+M1
(14)
15_ 2
|5_
which then implies
fm, 8,)
||5 12 + |,,
R m, 8,)
$ (1 + M2)..
(15)
6_
| 2
15
15

---

Published as a conference paper at ICLR 2024
Note that, by (14), the condition ||6=|| | < 82 holds whenever ||6x|| 1 VI+MT
4g
Thus, since
e was chosen arbitrarily, we conclude that R(0x. 5y) o(160 I²=,, as long as || - h(6).
Therefore, again invoking that (a=", " is local minimax point, have f(x" 5zzyy yy + + -fxx",
max 16, (1((5)
1 2 8 Ad + 82 Co,
1
max 1 (1((()
Bdy)
+ max (6,115h(8)
R(d 8ÿ)
2
1
max ||6, 1 (8)
82 Ad Cdy + 20 Böy)
+ +0llda11?
o (A ( 06 + o(118x11
This inequality holds for any 6 satisfying C 82 RBB), are done.
D.3 PROOF OF EXAMPLE
fb(2, v) zy: The saddle-gradient of fo is F(2, y) = (z,- -),, where (x*,²") (0,0)
is a unique stationary point. Since fb(x",3) = fb(2",'' y²) fo(,, = 0 for any (x,y), we can say that (0. 0) a unique local minimax point by definition. Regarding Assumption 2, the Jacobian matrix of the saddle-gradient F is
A CT
C
0
0
DF
B
-
where degenerate with rank B) = Since di 1, [1 ERIl and 9 rank(T) = 1, the matrix U is of size 1 x 0. So, (DF) is then 0 0 matrix. A linear map from a zero dimensional vector space to a zero dimensional vector space is trivially identity map, so the corresponding 0 x matrix is trivially nondegenerate.
(a 22, W1 32, v/) jut 1uu LU #232 + yiys: The saddle-gradient of fa is F(r,, I2, y1 y2, Wa) = (I), y2, y3, -x2, ys - W1), where {l E R. (0,0,4,0, set of stationary points. Since the inequality
0, ()] is
1 x fa 4) - -0i (ur va)² s fq(x" ,y = 0 fa(x,
2²
holds for any (x", .y) E (t E R 0, and for any (x, y). the set local minimax points is by definition e (0, 0,t)).
Regarding Assumption 2, the Jacobian matrix of the saddle -aadeeg F
0
0
0
0
0
A
C
DF
-C
-B
=
0
0
-1
0
1
0
0
0
0
1
where B degenerate with r rank 2. Since dj 2, d r=
[-]
22 [
and rank(r) 1, we have U = [i] E 2x and thus Sies(FF) [1]
kixi is
nondegenerate. Notice that for this example, the classical generalized Schur complement S A C [100 E R2x2 is degenerate.
E PROOFS AND MISSING DETAILS FOR SECTION
E. PROOF OF THEOREM 4.3
This theorem exactly reduces Lemma 4.1 when V V (=*)) is nondegenerate, it is only left to show this theorem for the case where S (DF(=*) is nondegenerate.
16

---

Published as a conference paper at ICLR 2024
We begin with the following observation. Suppose that restricted Schur complement Sres is invert- ible. Then, one can show that DF similar to
A
C₁
C
G
C
D
0
0
but C2 may not be of full column rank. Let rank(C2) and let C2 UEVT be the (full) singular value decomposition C2 where for some invertible diagonal matrix En it holds that
Σ 0 0
E =
0
Σg
Then, by defining Ly U
notice that UE
[L,
0].
Thus, for Q
diag I, V
we
have
C
L
0
A
C
V
QGQ
CT
D
0
- C
D
0
0
- L
0
0
0
V
C
0
0
0
0
and therefore
A
C1
Lg
det - DF) = det ) X det
XI
CT
D
0
T
0
0
So, the eigenvalues DF are either or the eigenvalues
A
C
Lg
C T
(16)
0
0
and analogously the eigenvalues of H, are either or the eigenvalues Φ; := A, Φ.
Moreover, by how Lg is defined, it holds that the singular values of Lg exactly the singular values of C2. and R R(L,) = R (2)... particular, there is no essential change Srea(H) when C2 replaced by Lg. Also, notice that Ly of full column rank.
Therefore, characterizing the eigenvalues Φ is equivalent to characterizing the nonzero eigen- values of H,.
To prove Theorem 4.3 we need the following result, which shows a relation between the eigenval- ues of the restricted Schur complement and determinantal equation that resembles the eigenvalue equation of Φ
Lemma E.1. A (possibly complex) number p. is an eigenvalue of the restricted Schur complement if and only it root of the equation
A
-C
Lg
det.
C
D
0.
(17)
L
T
0
Proof. By the property of Moore-Penrose pseudoinverses, it holds that
D
o
0
cT
CBiCT = [Cr
C₂
-.C.D-'CT.
o
C
17

---

Published as a conference paper at ICLR 2024
Multiplying matrices of determinant 1 does not change the determinant, so by observing
D
0
A
Ci
Lg
I
0
0
0
I
0
C
-
D
0
D
C
I
0 I
0
0
I
L
0
0
0
0
pI
C
-
by
0
-D
L
0
0
+ CB.CT
D
0
L
0
0
nl S
0
Lu
0
D
L
0
0
get that (17) is equivalent to the determinantal equation det T
where
pI
Lg
T
0
- D
(18)
L
Since permuting the rows and the columns change the determinant only up sign, have
Lg
det T
det
0
D
0
L
0
0
ul
S
0
L,
det.
L
T
0
0
0
D
0
HI
S
Lg
det
L T
0
0
0
-D
As D is invertible by assumption, we obtain that det T is further equivalent
L
det
(19)
L
Now we choose an orthogonal matrix Q such that it has block matrix form
UU1
Uz
where Un is the d1 x q matrix of left singular vectors appearing in the reduced singular value decomposition of Lg U2E,V V2" and Un is consequently a d, (dN -q) matrix with the columns consisting orthonormal basis of R (Ly)+ Note that U₁ corresponds the matrix U that appears in the restricted Schur complement, and considering how Lg is defined, we may take Vz = I. Applying similarity transformation, have
Q
0
[ S
Lg
Q 0
pI - Q SQ
Q Lg 0
[o
1
LT
1
=
L,Q Q
(20)
Exploiting the block structure of U, observe that
U
UUT Lg
0
Q L
Lg
U
U.
L
Eg V2
Σg
18

---

Published as a conference paper at ICLR 2024
by the orthogonality of R(U1) and R(Ly) and
U
SU
U. SU2
Q
sQ SQ
S [
U2]
U
Un SU
U2 SU2
Thus, the matrix in (20) can be also expressed as
pl UJ SU
U SU2
0
M
U SU 0
μ U2 SU2
- -2
Eg
0
Similarity transformations preserve determinants. (19) holds if and only if det M 0. Using again that the fact that permuting the rows and the columns change the determinant only up to sign, we obtain
pI - U. SU
SU, μI U. SU2
0
det M
det
-U2 SU
Σn
Σg
Eg
det
μI - U, SU
- SU2
0
-U2 SU
μI UT SU2
Eg
0
0
det
- -U SU2 [ U. SU2
uI U, SU U2 SU
Notice that both pI - U,T SU, and Mg are all square matrices, hence
det M det(pI
(e))
Because Ly is of full rank, we know that Eg is invertible. Therefore, det M = 0 if and only det(pI - U,T SU1)= =0 0.
Combining all of the chain of equivalent equations established, we conclude that
uI - A
-C
- LLy
del.
C
D
=0
if and only if det(ul U, SUI) 0.
(21)
L
0
Noting that U,T SU, is the restricted Schur complement, are done.
The following is an immediate corollary of the previous theorem.
Corollary F.2. Suppose that the restricted Schur complement invertible. Then equation (17) does not have μ 0 as solution. In particular, & is invertible.
Proof. The first part directly follows from the equivalence (21). For the second part, because sub- stituting μ 0 in (17) does not make the equation hold, must have det(- +) A 0.
We also use the following lemma, which tells us that the roots of polynomial is continuous with respect its coefficients. For the proof, see the original reference.
Lemma E.3 (Zedek (1965, Theorem 1)), Given polynomial (=)(2) == Ek anzt, an + O, integer m 2 ni and a number e > O, there exists a number 8 such that whenever the m complex numbers by. 0 < k S m, satisfy the inequalities
1b4 agl < 8 for 0 Osks n, and
[bk] < 8 for n+1 m.
then the roots 3r. < k S m, of the polynomial (z) En baz can be labeled in such way as to satisfy, with respect to the zeros ag,, 1 S k S n, of Pr. (2), the inequalities
1.8g - anl <e for Isksn n, and |&xl for n n+1sks m.
19

---

Published as a conference paper at ICLR 2024
Proof of Theorem 4.3. The eigenvalues of or the solutions of the equation
AI
cA
-CC1
LeLo g
0 = =Pp(AA= = det
C L
-
D
det(AI - ++).
(22)
0
AI
By Lemma E.3, constructing the functions Ay(E) so that they are continuous is possible. Also by
that lemma, letting - O, we see that the eigenvalues converges the solutions of the equation
XI
0
(A = det
C
-
0.
L
T
0
XI
Hence, the eigenvalues of H, converges to the r nonzero eigenvalues of B, and the other d1 + cigenvalues converges to zero, as + O.
To investigate the eigenvalues that converges zero further, we begin by observing that, whenever [k] is small enough so that XI- is invertible, holds that
AI
cA
-C
<g
TXI cA -
-D-
cg
det
C
D
det
-
0
L
0
AI
L
AI
AI (A- 11--i(M--
D
-ehi
det(AI D) det
L
AI
That is, any Aj that converges to zero + 0 is solution of the equation
A1 (AA C1 -
-eLy
0 = det
(23)
L
AI
Now 1et us reparametrize (23) by \ = e to get
lv/C (A Ci
-D-
-ch, Kvel
0 = det
L
[xl Ve(A CI -(
-VEL, kv/el
Ve det
L
VC di til det
[xl V -) -)
Log
D
I
Since - D)-1 converges solution of the equation
- 0, have that if X2 as 0 then ny should be
[Rl - VE(A -
det
(24)
Lg
RI
By Lemma E.3, we see that such eigenvalues divided by Ve converge to the roots of
KI
xI Lg
0 = det
(25)
L
Following the first few statements in the proof of Lemma E. we get that Ly must be full column rank. This implies that Lg has exactly g singular values. Thus, the nonzero solutions of (25) exactly tiok, & = 1.....g where Jj are the singular values of Lg, and therefore there are 2g instances among A; where each \ş Ve converges each one of =io as e e 0.
So far, we have shown that eigenvalues have magnitude O(1), and 2q eigenvalues have magnitude ( Meanwhile, because assume that the restricted Schur complement invertible, from
A
C
Lg
det. Φ, dd det
CT
D
0
L
0
0
20

---

Published as a conference paper at ICLR 2024
and that the determinant the right hand side is nonzero by Corollary E.2, we know that the product of all Ay should be of order ((c")). From these two observations, one can deduce that the product of the remaining dj - 9 cigenvalues should be of order ((e")=9) We claim that these dj - eigenvalues all exactly of order ((c). To this end, let examine what properties would the eigenvalues of order O(c) have. Reparametrizing = Juc in (22), we get
pel EA
-EC1
0 ==
CT
ucI - D
0
L
uel
uI
A
-C
q
= det
CT
uel
D
0
L
ucI
Then, by Lemma E.3, a converges to root of the equation
Fl
A
C
Lg
det
C T g
D
(26)
Again by Corollary E.2, μ = 0 cannot be a root of (26). This in particular implies that no X can be of order o(c), in other words, all eigenvalues of H, of order St(c). Therefore, for product of di eigenvalues of 4 to be of order ((ed1-9), each of those eigenvalues must be of order exactly (e)), and the claim follows.
Notice that the discussions previous paragraph further imply the following two facts:
If À is eigenvalue of order Occ) then A/c converges to root of (26) 0.
The right side of (26) is polynomial of degree dj q in μs, whose roots nonzero.
is now immediate that the d1 eigenvalues o, that are of order ((c) is of the form X(c) = μ.c o(c) for a (nonzero) root μu of (26).
The claim that (e + whenever e for any of the d, + eigenvalues that are not constantly zero is direct consequence of the simple fact det ($,) = det (A,) det ④)) o 0.
E.2 PROOFS THE PROPERTIES THE HEMICURVATURE
In Section 4.2.1, for (c( with
Re(A = E + o(el)), Im (Ay(e))) = o,Ve+ olVe),
(27)
and 0j > 1/2, we defined its hemicurvature to be the quantity
5 -1
lim --
of
As briefly mentioned therein, the term is named after the following observation.
Proposition E.4. Let a<E) = (Re (e), Im (e))) be a plane curve whose components are given as (27). Let k(() be the (signed) curvature of then it holds that
lim ro(c). 2 +00
=
Proof. For convenience, let us denote x<e) = Re(A)(E)) and y(e) = Im())(e)). Let us also omit the subscript j. as there is no confusion by doing so. We use the well known formula (do Carmo, 2016, p. 27)
z'y6" - x"
#
+2
21

---

Published as a conference paper at ICLR 2024
to compute the curvature of plane curve. To this end, observe that
x' (E) Eoc
+ o(c
="(c) Ep(p - 1)c0-2 o(cl-2),
1
(e()) 2 0
1/2 ole -1/2),
3/2 + o(E -3/2). 5²(() 4
Substituting, and using the fact that p > 1/2 hence 2 - - we get
150000-6/2 500(e 1) 8- 5/2 o(c0-
lim x(()) = lim e-+0+
<-00
(52 0 o(E 3/2
-250(20 1)06 + -00
lim
(162 + 02 o 3//2
Eee-1
-22(220 - 1) lim e-0 o²
If 1/2 0 1, then the limit is oc, the constant factor e(2g 1) does not affect the limit.
Similarly, if g > 1, then the limit is 0, so the constant factor o(2g 1) does not affect the limit also. Finally, if Q 1, then e(2g- 1) 1,
are done.
In Section 1.2.1. we have also mentioned that one noteworthy property of the hemicurvature is that is related to Re(1/A,). A precise statement on this is as follows.
Proposition E.5. For Ay(c) as in (27), it holds that
4j = lim Re
(28)
c-0
(g(()
Proof. We use the simple fact that x, y E R then
1
x- iy
Re
Re
(29)
+ Kn
x2 + y²
x2 y2²
Substituting (27) into the above leads
Re (y)
lim Re
= lim ++ (Re Xy(e)) + (Im (yt))
c-0
1,(e)
Eyels + o(c3))
lim -00
oîe + o(e)
E
c-0+
lim
of
=4
where in the second line we use the fact that @ > 1/2 implies eh = o(e).
E.3 ON THE NECESSITY OF CONSIDERING THE HEMICURVATURE
Let us present a depiction on why the tangential information alone may not be sufficient for our stability analyses: see Figure 1. Consider two disks Dz/2 and D, on the complex plane, both tangent to the imaginary axis at O, but with different radi;; and zz respectively. The respective boundaries @D./2 and OD, are circles, so assuming without loss of generality that they are positively oriented, it is straightforward that the hemicurvatures of each boundary curves are each and -s, respectively. Now suppose that some Xy(e) satisfies (27) with @j = 1 and S = =
بs The shape
of the trajectory of such Xy will be as drawn in the figure, and in particular, this trajectory is also tangent to the imaginary axis at O. As c - 0+ so that Ay(c) - O. one hand, we can visually see that the inclusion Xy(e) E D./2 eventually becomes true. On the other hand, although the fact that x//2 and D. share the same tangent line 0 implies that they are indistinguishable locally at only the tangential information is used, somewhat interestingly it holds that Xy(e) & D, for all (sufficiently small) > 0.
22

---

Published as a conference paper at ICLR 2024
2y(c)
D
D.
2x
Figure Two disks and curve, all tangent the same line the same point.
E.4 PROOF OF THEOREM 4.4
To prove Theorem 4.4 we need the following results. Proposition E.6. Under Assumption and 0 nj L. then det(DDū; (z)) + 0 0.for all
Proof. Assumption implies that any eigenvalue À of DF satisfies 0 < 17 < 1. any eigenvalue μ of Dü, (z) = I-mA-,,,D( satisfics < [a| < 2. Hence, we have det(Dww (=)) > O.
|X] < L.. So, assuming
Proposition E.7. For any z" E Nis there exists a positive constant T > 0 such that x" E A20 for any T"
Proof. Since Dw, I HH, we have
Ar = {z" =" = =w,(2", Dro (z")) > 1}
{=" x" (z()"), YE spee H, n 1}.
Observing that {a E |1 11-12 -=| > 1} can be equivalently formulated as {a E C Re (+) < 3) there exists some 7* > such that E A" (w0) for any T > 7*, since E X satisfies lim,-+0 Re(1/A,) 4j < for some j E I.
Proof of Theorem 4.4. Notice that x" E A" (wx) implies
{zo : lim w²(z)) = 2²) C {zo k+00
lim (=o)) E Awx)))
Therefore, it follows from Theorem 2.2 that there exists positive constant 7* > 0 such that u({z): lim (zo)) =))) for any T > 7*
F PROOF FOR SECTION 5.1
Proposition F11 Under Assumption 1, a point z" is an equilibrium point of (6) for 0 < s < 1/1, or respectively of for 0 n 1/2, if and only if F(z") 0.
Proof. The "if" part is straightforward from both equations (6) and (7). To show the reverse direc- tion, suppose that z" is an equilibrium point. For the case (6), we must have
(I + AA,
0.
23

---

Published as a conference paper at ICLR 2024
Under Assumption and 0 1. (I (F,))(=")) is invertible, this is equivalent to F(z") = 0. For the case (7), we must have
F(z" -=,, 0.
For the sake of contradiction, suppose that F(z") + O, and let w = ====)) Note that w* + z" by assumption. Then,
n F(z) = z" -
= =w- "A,
hence have w" A (F F(w")). Under Assumption which is equivalent the L-Lipschitz continuity of F, and
J., we have
|| - w"1 = A, (F(z") F(w"))I ))I
$ nL || 1|2" w'
< n ||=" w"1l
|| w"
which is absurd. Therefore, conclude that F(z") 0.
G PROOFS AND MISSING DETAILS FOR SECTION 5.2
G. PROOF OF PROPOSITION 5.1
The following lemmata will be used in the proof.
Lemma G.1. At an equilibrium point of ODE (6), holds that
-- +H;
Proof. Differentiating the right hand side of (6) with respect to 2, one gets that the 7th column of the Jacobian matrix J, is equal to
[J
DF dzg
=-(I+sA, (A))F(()) (A. - SA (AA.de, dz,
d
DF(2)) (I
where D,F denotes the ,thh partial derivative of F. Recall that F(z*) = by Proposition F.1. So, when evaluate the expression above at 2", the last term vanishes, giving what corresponds the 7th column of the matrix identity
-===)==- (A,,A
Note that this is exactly the claimed.
Lemma G.2. A complex number À E C } an eigenvalue of H; if and only if T=s is an eigenvalue of J
Proof. The "only if" part direct consequence of applying Theorem 1.13 in (Higham, 2008) on the function X + -(1 - - For the "if" part, note that + -L long as À C. hence I + sJ always invertible. The assertion then follows from fact that the map -(1+ -1 X is an involution.
Proof of Proposition 5.1. It is clear that f Cufo) - CU foo) defined f(A) I is continuous. Also. it is an involution, hence bijection. Therefore, f is homeomorphism.
Let us identify the image of the imaginary axis iR under the map f. Let i E R be any real number, then observe that
1 =
-it
i st
f(it) +
28 1 ist
2s 2s(i st)
24

---

Published as a conference paper at ICLR 2024
As st R. it follows that
f(it) + 2s
Vt R.
2s
Moreover, lime-+o f (itt) - This shows that f(iR U (oo)) OD., where 0D, denotes the (
boundary of "D., a circle of radius 2a centered at 2s the complex plane.
In C iR we have two connected components C and C2 and in f(C) (R) we have two connected components D& 0D, and C D.. To see which is mapped to which, notice that
f(1) 1+8
and thus - < < 0. follows that f(1) E D. \\ (,,,, and therefore,
S(C2) C (D.,
[(C))= = D. ..
In particular, f' is a bijective mapping between CL and C D.. So, by Lemma G.2, the spectrum of J lies inside the open left half plane if and only if spec H C D,, which is equivalent to the claimed statement.
We would like to remark that spec(DF) n D, = Ø, appearing in the statement of Proposition 5.1, equivalent to the so-called negative comonotonicity condition F, which is condition that guarantees the convergence of (discrete) EG, as demonstrated by Gorbunov et al. (2023). While their discussions rely algebraic manipulations, work offers dynamical systems perspective that sheds light on the significance of this condition.
G.2 TARGET SETS OF CONTINUOUS-TING METHODS
Using Proposition 5. we can depict the larget sety two-timescale EG. By larget sets we mean the region in the complex plane that the spectrum of spec (H7) must be contained in, in order to make spec J C C hold. See Figure 2a for depiction. To additionally demonstrate how the target set of E- depends the parameter s, overlaid two target sets the same plot.
For continuous-time T-GDA, as studied by Fiez & Ratliff (2021), the target set is the open right half plane. To contrast this set to the set in the case of T-EG, we depicted the target set for 7-GDA in Figure 2b. An interesting thing to note here is that the target set of r-GDA can seen as the (set-theoretic) limit of the target set of T-EG when open left half plane. (Here we consider D, as the closure D.. where the latter denotes the open disk obtained by taking the interior of D..)
0+, since the limit of D3 - 0+ is the
C) 1/22
C D.
C)D
2s
(a) Target set of continuous-time 7-BG
(b) Target set of continuous-time r-GDA
Figure 2: depiction of the target sets of continuous two-timescale methods. Notice that for 7-BG have overlaid target sets with different choices of the same plot.
25

---

Published as a conference paper at ICLR 2024
G.3 A CONSEQUENCE OF ASSUMPTION 2'
As all of the remaining theorems in Section 5.2 employ Assumption 2', let us begin with studying what do we get by additionally assuming the invertibility of DF. Proposition G.3. Suppose that Assumption 2' holds. Then Sres(DF(z")) is necessarity invertible.
Proof. Because Assumption 2' implies Assumption 2, either one of Sres (DF(z")) or (z²) is nondegenerate. For the sake of contradiction, suppose that Ses (DF(z*)) is singular, which asserts that B V f (=*) is nondegenerate. As DF is invertible, classical result on Schur complements tells us that S = 2012, Section 0.8.5). Meanwhile, if B is invertible then d2, I is matrix with zero columns. Hence, RTT)- Rdd and so the matrix U that defines the restricted Schur complement through the relation Ses (F) U SU becomes square orthogonal matrix, which is in particular invertible. However, this implies that the restricted Schur complement See FFF (DF(=") is product of invertible matrices, which cannot be singular. Therefore, our hypothesis must be false, and Ses (DF (DF must be invertible.
CT is also invertible; see, egg., (Horn Johnson,
Thus, assuming the invertibility of DF ensures that all jij are nonzero in Theorem 4.3. Moreover, because H, A is then also invertible hence cannot have a O as its eigenvalue, we must have d2 - and all eigenvalues of H, fall into one of type (i), (ii), (iii) eigenvalues characterized in Theorem 4.3.
G.4 PROOF OF THEOREM 5.2
Lemma G.4. Let so max)e If > so, then there exists some T* >> O such that whenever x", all the eigenvalues Xj with I lie outside of the disk D.. Conversely, if so, then for any sufficiently large T, there exists some j such that (c) E D,,
Proof. Fix any j E {l,... d2 r}. Observing that D, can be equivalently formulated as
D. = = E Re ( S 5
(30)
we may alternatively analyze how the real part of 1/A, behaves. By Proposition E.5, it holds that
lim Re
lj.
(31)
For j E {d1 + 1,.... .d d2 - r), by simply replacing o, by -o we also have (31).
equivalently have So minjez 4j. Hence, if -8 -80- then for all j E I, the quantity (e(1/A((()) will eventually be larger than -8 as 7 - oc. That is, in view of (30), there exists some 7* 0 such that whenever > r", all the eigenvalues X, with j E I lie outside of the disk D..
As define 80 max
Conversely, if - > 8p, then because I a finite set, there exists some j E I such that Re(1/A,(e) + so as + oc. In other words, for such j. whenever sufficiently large holds that Re(1/Ay(c) ss, or equivalently, >y(c) E D.. according (30).
Remark G.5. Ef 2 0 for all j E I, then we have S O. In that case, since we always assume that s > O, we trivially have so- On the other hand. if 2 and & <, 0 for some E then = -C, so as consequence s0 = sc. In that case, since is finite, we trivially have s < so-
We analyze the necessary and sufficient condition for each set of eigenvalues Xj of H; categorized in Theorem 4.3 to lie outside D. below, and combining them leads to the claimed statement.
Proof of Theorem 5.2.
26

---

Published as a conference paper at ICLR 2024
(i) Consider X with j I. Suppose that so 1.- Then, by Lemma G.4, for any step size s such that so < 7. holds that Ay(E) & D. whenever Conversely, suppose that 80 2 .. Then, for any such that 0 < 8 < I we have a < 80. In that case, by Lemma G.4, for any sufficiently large timescale 7 >> 0 there exists some such that Ay(e) E D.. Therefore, 80 1 if and only there exists some < s* < such that, for any satisfying s* <s< I. being sufficiently large implies Xy(c) & D, for all J
sufficiently large.
I
(ii) Consider X = ej4 cjtc for some k. Note that they converge zero asymptotically along the real axis. particular, whenever e sufficiently small, if μa then Xy(e) $ D... and if jok < then Xy(c) E DD.. Recall that in Theorem 4.3 we have established that (4u are the eigenvalues of the restricted Schur complement Sres- One can then deduce that STes 0 if and only if there exists some y" where 7 > r" implies that every X3 of order ( satisfies Ay(c) $ D..
(iii) Consider A = + o(1 for some k. As we take Assumption 1, for any > 1 it holds that H; |A, s || [| L.
As (e(e) an eigenvalue H; it follows that Ayy s L. Similarly, for Ia denoting the
d2 x d2 identity matrix, observe that
B = :
0 a
-
:
0 0
A
C
0 0 O
S <IDDF(2')1
1ig
-C
B
Idg
It follows that [pxl S. L for the cigenvalues 2) of BB Now, let 0 < < F. and suppose that B & O, that there exists some & such that - S v 0. Then, since the half- will
open interval [-I, is contained in the interior of D., for sufficiently large have Ay(c) D.. Conversely, if B < O, then V42 0 for all k, as consequence, whenever 0 and is sufficiently large, we will have Ay(e) D. for all j such that Ae(e) Ma o(). Therefore, B < 0 if and only if there exists some T being sufficiently large implies every X3 order ((1) satisfies (c( & D
+ such that
Combining all the discussions made, we conclude that Stes 2 0, B 1 0, and so < if and only there exists some 0 < s* < 1 such that, for any satisfying s* < s < t. 7 being sufficiently large implies (T) & D, for all j. The conclusion then follows from Proposition 5.1.
G.5 PROOF OF THEOREM 5.3
The proof of this theorem utilizes several theorems on the locations of eigenvalues. For complete- ness, hereby include their statements.
Theorem G.6 (Weyl). Let A, B be Hermitian matrices, and let the respective eigenvalues of A, B, and A + be {Ax (A)), (B)) and {>x B)}, each sorted in increasing order. Then for each k, it holds that
A Ae-j+i + ( S (A+
for any j 1,....,k
Definition 7. For any matrix A, let AH denote the conjugate transpose of A. When A is a square matrix, the matrix [A A") is called the Hermitian part of A.
Theorem G.7 (Bendixson). Let A be any square matrix, and let R be its Hermitian part. Then for every eigenvalue À of A holds that
Auii R. < Re S Amax
where Amain R) and Amaxl (R) are the minimum and the maximum eigenvalues of R, respectively. Theorem G.8 (Rayleigh). Let be a Hermitian matrix, and denote by Amax(A) (A) the maximum eigenvalue of A. Then it holds that
Amax ()
max at Ax.
(32)
||
27

---

Published as a conference paper at ICLR 2024
Theorems G.6 and G.8 can be found in (Horn & Johnson, 2012) Theorem 4.3.1 and Theo- rem 4.2.2, respectively. Theorem G.7 can found as Theorem 6.9.15 in (Stoer & Bulirsch, 2002). For the proof of these theorems, the references.
To be more precise, in terms of Rayleigh's 's theorem, we need the following corollary rather than the theorem itself.
Corollary G.9. Let E = diag [11.................... Dn be real diagonal matrix. Choose 3 to be nonnegative
number such that B < min (....... nn). Then for any real matrix C' E IR it holds that
Amin (CEC 2 -3 ||T]|
where Aminn (CECT) denotes the minimum eigenvalue of C
Proof. Let Amaxe (.) denote the largest eigenvalue of a given matrix. By how we chose 3, we have 0h B for all k. Hence, for any fixed æ, let C y ly ... ym then
x CC(EEE) x = x-y
m2
yh 3 11 3|1|C
x|| B|
Taking the maximum ||>||| 1, by Rayleigh's 's theorem we get
Amaxx ( (-CCC ||=||=1
x. ="C(-EEC C
As À is an eigenvalue of T if and only if - an eigenvalue of CECT, it holds that -mmin (CEC ) so we are done.
In order to make the proof clearer, let us state the following simple but technical fact also as separate lemma.
Lemma G.10. Let be a nonnegative real number. Then, for any X E C2, it holds that
-1 -1 Re
O.
Proof. Let X = x + iy for v, E R, and then note that x S 0. As it holds that
x + yj² 1)
VX
vy x² + y²
we have Re (# - -1 < 1, and consequently as we know that < < 11, we obtain
1/4 1
2 1. Let xx2 -1 in for E, E R, then
E < 0. E2 + 12
Mcanwhile, since the size of the real part of complex number cannot be larger than its absolute value, it also holds that
1
Re
1 F
Combining the two bounds gives us the result.
Proof of Theorem 5.3(i). For any j such that Ay(e) + o(1), since B < 0 implies 1% > 0, for any sufficiently large we have λy(e) C.. In particular, for any 0. it holds that (y(e) $ D. whenever is sufficiently large.
For any j such that X)(c) eus + o(e), notice that S = 0 implies S, > O, so we have # 0. Because (c) converges to μıx for any sufficiently large we have ()y(c) E C. which implies that (c) E Cº. Therefore, for any 0, it holds that >y(c) & DD whenever is sufficiently large.
28

---

Published as a conference paper at ICLR 2024
Now for convenience, let 0,(c) = (e)(e) TAy(c). Our next step is to show that
lim Re (0)(c)) 20 c-+++
Vj EI.
If that is the case, for all j E I we would have
(
Eye + olEe) c03
0 5
lim Re (0)(e))) = lim Re +++ of 6
lim c-0+
ljs
+u
and consequently 80 V O. Then, for any 8 O, we trivially have 8 > 80- Hence, by applying Lemma G.4 and Proposition 5.1, it is possible conclude that x" is strict linearly stable point. Notice that 0g are the eigenvalues of the matrix
A -TC -TB
C
H
As in Section 4.2, by applying similarity transformation, we may assume without loss of generality that B is diagonal matrix. Following the notation therein, let - dia. ......... 0}.
Fix any Z. Recall that have convergent Puiseux series expansion (c 2k=1 aj and notice that it suffices to assume that E R, that, as c - 0+, either Re (c))(c)) = Re (c)) converges to a finite number, diverges to +o0, or diverges to -oc. For the sake of contradiction, suppose that limy Re (0)(e) < 0. By the Schur determinantal formula, the eigenvalue 02 of r H must be root of the equation
(k) hips
are studying the limit as - 0+. Then
det(T - 01) = det ([
(1--0"
01
C
-TB -1
det ( 01) det (A- 01 - -
-et)-TB-O1)dde A A- 01 - c
B 8+-1 -1 CT
Since B < 0, and for sufficiently large we would have Re(O,(tt) < 0, it must be the case where del(- ( 0,1) + With this mind, observe that
0 -1) 1++-1
A- 01
-1 - C
CT
0
A - AI - C (diag
-v1 +
-
+
CT
A - 01 + C diag
t
T
CT
TV1 -0"
0'
TV,
0'
0
A - - - + C diag
1
7
CT
1/1
ru 0
1
1/
0
0
To see why the last line holds, observe that
1
Let us denote
TV
vl
TT
1
1
E diag
11
Vr
TVc 0
so that (e) becomes a root of the equation
dct(A C AI + - 0.
(33)
Now suppose that limy Re (e) -0. For sufficiently large т. having Re(O, < implies (e(()(e)/T) < 0. So by Lemma G.10,
1 < Re
50
(34)
TVL 0,
29

---

Published as a conference paper at ICLR 2024
for all & = I...., Here, note that the Hermitian part of CEC* is
1 2 (CEC* + (CECT) C
E + E 2
CT
-CR((E))
where Re( E) denotes the elemenswise real part of E, by the fact that E' is diagonal. Hence, using Corollary G.9 with (34), we get that the Hermitian part of CEC has spectrum that is bounded below by a constant, uniformly on т. As we assume that A - CB > O, by Weyl's theorem, the spectrum of the Hermitian part of A CB'C +CEC is also bounded below by constant, uniformly on 7. Finally, noticing that the Hermitian part of #I is Re(0)I, and that we assume -o, Bendixson's theorem tells us that being sufficiently large implies
lim,- Re (0) (c)) every eigenvalue A CBCC 0 + CEC having a strictly positive real part. However, this means that A CB¹C 8 CEC is invertible, hence (33) cannot hold.
We are left with the case where Re (f)(c)) converges to a negative finite value, say - -W- as - co. In that case, notice that
lim 000
TeL B
for all k 1,...,, T. As we assume that A- CB¹CT > O, following the same logic used in the previous paragraph, this time part of A- CBCC + CEC becomes bounded below by ,, there also exists Ti such that т > Ti implies - (e)(O) > J Therefore, by Bendixson's 's theorem, whenever > max(7o, Ti) the eigenvalues of A - CB.C 0,I + CEC will have a positive real part that is greater than /6./6. But then, this again implies that (33) does not hold, which is absurd.
find such that for any т > the spectrum of the Hermitian
Therefore, for any j it holds that lim Re (0)(c) ) 2 0. As claimed in the above, this completes the proof.
Proof of Theorem 5.i( Suppose that Sies o 0, or equivalently, there exists some k such that H < O. Then, by Theorem 4.3, we have (e( = eμ4, + o(e) for some j. In other words, for some
holds that Ay(c)/c- la as c + 0+. So by choosing = 2/m4 > 0 we must have Xy(c)/c E D, whenever sufficiently large. Since cD, D, whenever < c <S 1, follows that Xy(c) E D. whenever 7 is sufficiently large. However by Proposition 5.1 this implies that 2 is not strict linearly stable, which is absurd. Therefore, necessary that Sres >
1
Next, suppose that B A O, or equivalently, there exists some k such that Ds < 0. Then, by Theorem 4.3, (E( converges to Vy for some if we choose
2|a 0 we must have Ay(e) D. whenever is sufficiently large. However again by Proposition 5.1 this implies that x* not strict linearly stable, which is absurd. Therefore, is necessary that B <
Li
G.6 PROOF OF THROREM 5.4
Let us first identify what happens if o all distinct. In doing so, the following proposition, which summarizes the discussion made in (Kato, 1995, Section II.1.2), will be useful. For further details and the proof of the statements, see the original reference.
Proposition G.11. Consider a convergent perturbation series T(x) = To + + 2 + and suppose that O is in the spectrum of the unperturbed operator To. Let (z())).... >x(x)) be the eigenvalues of T(x) with (;(0) 0 for all j = 1,...,8. We may assume that such functions are holomorphic on a deleted neighborhood O.
we may assume that those functions can be grouped into {>1()). ... Ag. (z)), (Z) >gs og (x)),... so that within each group, by letting g to be the size of that group and relabelling the indices of the functions in that group as Ap.s.. Agg. the Puiseux series expansion
Furthermore,
Ajn (e) = Σ ap (a (w02
30

---

Published as a conference paper at ICLR 2024
holds for all h l....... Here, is primitive g root of unity.
The fact that the eigenvalues can be grouped in way that is described above is crucial, leading to the following observation.
Lemma G.12. Suppose that all oj distinct. Then, the Puiseux series Az(e) ku Oj essentially becomes power series of 2/22, In particular, Lj 2 1.
(k) h/D.
Proof. Fix any Xj with j I. By Proposition G.I1, there exists some positive integer g such that we can find Aÿz = Aj..... Aj whose Puiseux series expansions are
(1) = Σ ap (w>2
P=
for w primitive tthh root of unity. particular, the absolute values of the coefficients corresponding to the terms of the same order in each of these series must be all equal. Since all o, values are distinct by assumption, and since they are all real and positive, we conclude that = It is also now clear that the second lowest order term in the Puiseux series expansion is of order O(e).
Now, observe that if 2j > 1, then 4; = 0. Hence, in the case where 2j 1, there is no loss of generality when considering it as having @j and Sj O. In other words, by allowing Sj 0, we may assume that the Puiseux expansion of Xj is of the form
> -iovvee Gee o(e).
This suggests reparametrization, say for example letting V = ô, so that the Puiseux series can be dealt as if an ordinary power series.
In case where an eigenvalue of a perturbed linear operator (on finite dimensional space) admits a power series expansion, much more is known on quantitative results regarding the coefficients of that power series. For instance, the following proposition summarizes the discussions made in Sections I.5.3, II.2.2, and II.3.1 in (Kato, 1995). For the details and the proof of the statements, see the original reference.
Proposition G.13. Consider a convergent perturbation series T(x) = To + xT + 2T + Suppose that Xa is simple eigenvalue of To, and define
PA. = 2Ti J (SI-Ta)
(35)
where I' is a positively oriented simple closed contour around Xn which does not contain any other eigenvalues To- Then, there exists eigenvalue X(x) of perturbed operator T(x) such that x(0) = Ag, which admits a power series expansion
Mxx = do xX (1)
22 +
(36)
Here, it holds that
=T,
Moreover, let R. be the radius of convergence of the power series (36). Then, the fact that the per- turbation series is convergent guarantees the existence of nonnegative constants a and satisfying
[Ta] S ac for all 1,2..... For such and it holds that
R To min CEr' IK Toll + +c²
(37)
and there exists a positive constant p such that
P 0|21
xxx) No x1
(38)
(r xx
The operator Ps, defined as in (35) called the eigenprojection of Tg for Ag If T, is additionally assumed be normal, we have the following characterization of the eigenprojection for An-
31

---

Published as a conference paper at ICLR 2024
Lemma G.14.
Suppose that An is simple eigenvalue normal operator To. Let be the unit norm eigenvector of To associated with Ag. Then, Pxo = ww
Proof. Because To is normal, it admits a diagonalization To WOWT, where we may assume without loss of generality that è diag (01, 82. with 01 = A and W is a unitary matrix with its first column being w. Then, by definition (35), holds that
2ti [(CT
[(CI--Tb)
Pro
-To)
W
2m / ((II-
(CI- W
1
dc
2Ti [ 5 02 02'.... -0)....?) W
1 dc
W
diag
2Ti Jr
01
W diag
(1,
ww
where in the fourth line we use the fact that I' encloses An = 01 but no other eigenvalues of Tp-
Proof of Theorem 5.4. Recall that, in the proof of Theorem 4.3, we have shown that any eigenvalue such that >3- 0 as
0 should be solution of the equation (24), namely the equation
RI Vē(A- C D) CT]
-C2
0 = det
C
kI
Reparametrizing the above by 8 = Ve givesv
III - 5(A
Ci D) CT]
-C2
0 det
C
kI
Now fix any index j E {1, 21, d2 - r}. The cases where j E {dl - I,..., di + d2 - can be dealt in the exact same way that is presented hereinafter, by simply changing every instance of aj to -O-- We a priori know that (6) = Xy (6) = i0 + G + o()). Fix do > 0 arbitrarily, but small enough so that (6)) D < 1. Setting & Xy (o0) /o0, we have that K2 is solution of the equation
KI 50 (A Ci - CT-
C2
0 = det
CT
RI
In other words, Ky (d)) is eigenvalue of
C2
A
Ci I
DD
0
+ 60
0
C
0
C₂
A + C
Ak
D 0
o
80
0
gk
C
0
0
Notice that the infinite series expansion above is valid, as óg is chosen to satisfy the condition kdo |||| = (o)) DI < 1. Now, because A - io, 5n - 0, by restricting the range of óe
further if necessary, we may assume that & is uniformly bounded on 8g. In particular, we can set range of &, that R < jj uniformly on dg. Then, the coefficients of the perturbation series are bounded by
C1D* CT
o < || (o) -1)-11 *
Notice that these bounds are independent of dy. Invoking Proposition G.13, with restricting the range of &n further if necessary in order guarantee the convergence of the power series (36), obtain
( cI
0 p 0
(8)8 ii,,, 60 tr
0
32

---

Published as a conference paper at ICLR 2024
Moreover, by further restricting the range of du if necessary that du I ro/2, where is the quantity introduced in (37), we can apply the bound (38) to get a constant C' that is independent of ón and satisfies
kg) -i0 - du tr ( A CA+CCD--C
0
P
Co..
Note that this estimate holds for all sufficiently small 6p- Therefore, we can conclude that
G = tr A + A+C (
0 0 P
Observe that, for u and Vy the left and right singular vectors of C2 associated with the singular value oj respectively, the vector [w,]] is the eigenvector of the unperturbed operator that is associated to the eigenvalue io,, Normalizing the eigenvector gives us
0 C2
-c
U
Uj
I
V L 11? + ||y
2
and Lemma G.14, we moreover have P uvr T.
Then, by the eyclic invariance the trace, we get
DDD-IC
0 0
C = tr
0
P)
[ + D.D-DD-CC 0
0
1
リ CA+
2
By the structure of B, we have C,D- = =CB so we done.
H PROOFS AND MISSING DETAILS FOR SECTION 5.3
H.1 ON THE PEANUT-SHAPER REGION P,
The peanut-shaped region P, defined in (8) is illustrated in Figure 3. This P,, is a dilation of Pi by factor of J, and contains subset of the imaginary axis il L (- u (o,
1 n C i..
4n
2/4
-//
Figure 3: The peanut-shaped region P,, in the complex plane
Similar to the analysis in Appendix E.2, the tangential information alone may not be sufficient for discrete-time case stability analysis: Figure 4. Consider two peanut-shaped regions P,/16 and P, on the complex plane. Both are tangent to the imaginary axis at O, but have different dilation parameter; 1 and 16 respectively. Suppose that some Xy(e) satisfies (27) with e; 1 and & 7 7 Then visually that >e( P., and A5(E) PPn/16 becomes true 0+.
0f
33

---

Published as a conference paper at ICLR 2024
2x(E)
P Pn/16
3/1
2/1
Pn
Pn
1/4
1/n
(a) An overall view of the depiction.
(b) Enlarged version of the figure the left.
Figure 4: Two peanut-shaped region and a curve, all tangent to the same line at the same point.
4/
1/a
3/1
1/9
Figure 5: Target of discrete-time 7-EG and GDDA, both using 7) as their step sizes. The (blue) peanut-shaped region is the target set of 7-EG, and the (orange) disk is the target set of r-GDA.
H.2 TARGET SETS OF DISCRETE-TING METHODS
Similar to the continuous-time case, let us compare this to the target set of T-GDA. As studied by Fiez & Ratliff (2021), the Jacobian of (discrete) 7-GDA becomes the open disk with radius !/n centered at 1/n. In Figure we have overlaid the depictions of the target of E-EG and the target set of 7-BG, when both methods use 77 as their step size.
n,H, the target set of 7-GDA
Notice that it is now visually apparent why 0 in Example 2 is not strict linearly stable point for 7-GDA. Clearly, the target set of 7-GDA- the bisk never contain =ive for any >
H.3 PROOF OF PROPOSITION 5.5
For convenience, let us define subset of the complex plane
D D2/2 f =
which is open disk centered at 1 with radius
+
At an equilibrium point z", it holds that
34

---

Published as a conference paper at ICLR 2024
and can easily show that p(J;) < if and only if spec(H;; nH;)) E D n/22- The only remaining part to be proven is that spee H (I ();)) C D equivalent to spec spec(H;; P.p
Let À be an eigenvalue of H Then spec H - h);) C D D,/2 implies À .7 E D2/22 By letting À + iy. where x denotes the real part and y denotes the imaginary part of X, we have 17,2 = x - næ + myy + i(y - 2nzy). Then, the condition 1-12 -np² E D2//2 can be equivalently
written as
(1 x2x² + u 1)² + (ny 2n¹ xy)² < 1.
This can be further simplified
1 )1-
T 2
+ < / + 3n
and the assertion then follows from the definition of Pyy-
H.4 PROOF OF THEOREM 5.6
In proving Theorem 5.6, the following two results will be used. Proposition H.1. For (e) as (27), holds that
lim Re (x,11- - -npnn) ) = + 17. c-0
(39)
Proof.
Using (29) and substituting (27) into the above leads to
- (, (2 (,,,))
1
Re(A, (1-1)(1111)) 1)11)) Re(A, - (
lim Re ++
lim +00
+ + o(ce)-1)
no? o())
= lim
++
+f o(1)
1j +
where the second line uses the fact that @ > 1/2 implies 20 = o(c).
Lemma H.2. Let 50 == max)e If > so, then there exists some T* 0 such that whenever >> r", all the eigenvalues Xj with E I lie in P,, Conversely, if 2 < So, then for any sufficiently
large T, there exists some I such that (y(c) $ Pn
Proof of Lemma H.2. Recall that, in the proof of Proposition 5.5, we have shown that the peanut- shaped region can be represented as follows
Pn = 2 E
> 2
2(1 -
((1-72) 12)
Therefore, if -80 = minjez (j > 1 then for any sufficiently large and for all j we will have Re [5(1-1A3) > N. Hence, all cigenvalues will lie in P,, for a sufficiently large On the other whenever is
2
hand, if -8 = minjez ij < - 3 then for some j we will have Re (X,(-1A)) sufficiently large. Hence, there exists some j such that >, & Pr, as T oc.
Proof of Theorem 5.6. Similar to the proof of the Theorem 5.2, we analyze the necessary and suffi cient condition for each set of eigenvalues A of H. categorized in Theorem 4.3 to lie in P,, below, and combining them leads the claimed statement.
1 Then, by Lemma H.2, for any step (i) Consider Xj with j Z. Suppose that < 2T.
size n such that so < g < 27. it holds that Ay(E) E P, whenever is sufficiently large. Conversely, suppose that so 2 ZI. Then, for any 7 such that n < I. have
35

---

Published as a conference paper at ICLR 2024
2 so- In that case, by Lemma H.2, for any sufficiently large timescale 0 there exists some II such that 2y(c) Py. Therefore, 80 < 22 if and only if there exists some being sufficiently large implies
0 < n" r. such that for any 7) satisfying 17" < X,(c) E P., for all j E.
(ii) Consider A c/4 + +o(c for some k. Note that they converge zero asymptotically along the real axis. In particular, whenever c is sufficiently small, if μ > then Xy(c) E Ps, and if pa then Aş(e) Ps. Recall that in Theorem 4.3 we have established that jau the eigenvalues of the restricted Schur complement Sres- One can then deduce that Sres 2 0 if and only if there exists some T" where > T* implies that every x of order (ee) satisfies Xy(e)= E Pg.
(iii) Consider X, Ms: + o11 for some k. By the proof of Theorem 5.2, we have [| S L for eigenvalues of H and || S T. for the eigenvalues of -B. Now, let 0 < n < I. and suppose that B A O, so that there exists some k such that -I S V2 < 0. Then, since the half-open interval [-L, 0) is contained the interior of complement of Pg. for sufficiently large we will have (e( E P,, Conversely, if B 3 O, then is > 0 for all k. so consequence, whenever 17 > 0 and T is sufficiently large, we will have 2y E Pg for all j such that (e) = V2- + o()) Therefore, such that being sufficiently large implies every X of order ((1) satisfies X (e) E Pn
z 0 if and only there exists some 0 < 1j < I
Combining all the discussions made, we conclude that Sres = 0, B 3 0, and Sp < 2r. if and only there exists some < 11" < +, such that, for any v satisfying 1y* < l < 7., t being sufficiently large implics (T) E Pn for all The conclusion then follows from Proposition 5.5.
H.S ADDITIONAL STABILITY CONDITIONS OF TWOTTIMESCALE EG IN DISCRETE TIME
Theorem H.3. Let x² be equilibrium point. Suppose Assumptions I and 2' hold.
(i) (Sufficient condition) Suppose that z" satisfies S > 0 and B 3 0. Then for any step size < 1) < 1/1, the point z" is a strict linearly stable point of oo-EG.
(ii) (Necessary condition) Suppose that z" is a strict linearly stable equilibrium point of oc-EG for any step size < 17 < 1/1. Then, satisfies S.e, Z 0 and B O.
Theorem H.4. Under Assumptions I and 2', suppose that all the values of a are distinct. Then, an equilibrium point z" satisfies Stes ž N and u, Su, 2 0 for every left singular vector u, of C2 if and only if 2" is a strict linearly stable point of oG-EG for any 0 <, 1 < I/L.
H.6 PROOF OF THEOREM H.3
Proof of Theorem H.3(i). For any j such that Xy(e) vy + oL)) B W 0 implies that vs 0. Since [Px] < and 0 < 1) implies that P, contains a half-open interval (0, L). for any sufficiently large we have Xy(e)= E Pg-
And for any j such that Ay(c) = c/4: + o(c), since A - CBBCT > 0 implies Sies ż 0, for any sufficiently large T we have (e) E P,.
55e -1 of
On the other hand, for any I proof of Theorem 5.3(1) implies that lim so maxxez(-1g) < 0. The conclusion then follows from Lemma H.2.
2 0 hence
To prove Theorem (ii( we use the following technical lemma. For convenience, let us define subset of the complex plane, for positive constant a > 0,
a O, = f= 1a al
2
which an open disk centered at -a with radius g.
Lemma H.5. On P., 2 for any positive constant 0.
36

---

Published as a conference paper at ICLR 2024
Proof. Noticing that On lies in the left half plane, the only region about is CL. Thus. if the disk O₂ and the seanut-shaped P. do not intersect on that region, then the assertion follows immediately.
Consider a circle centered at origin with radius R, denoted by O Then, if the circle O and the boundary of On intersects, then it intersects at point 21 with real part Re = - R² + 2e ). 2a
Similarly, if the circle O' and the boundary of Py intersects, then intersects at a point #2 with
real part Re =
RR²
R42 16 +
382 For O₂ and Ps, to have an overlap, there 8
Ton
must exist some R such that Re and 1), by proving the following statement
Re
We show that such R does not exist for any positive
R
R
30
1
3nd
Rd
3R
Re 32
Re 21
+
4n
2a
16n2
16
8
for any positivie values a, 77 and R. This is done by showing that the following
nR
R
3a
1
3r7² R
3R²
2a
167
16
8
9a²
3a
+ R²2
3an
+
+ R²
17
167)
16
4am
4a
40
4
holds for any positive a, 17 and R, and this concludes the proof.
Proof of Theorem H.3(ii). Suppose that Sres A O. equivalently, there exists some k such that fs < Then, by Theorem 4.3, we have (e) = e/ux + +o(e) for some j. So by choosing sufficiently large т, Lemma H.5 implies that (e) ş P,, However by Proposition 5.5 this implies that 2" is not strict linearly stable, which is absurd. Therefore,
necessary that Sies > 0.
Next, suppose that B A O, equivalently, there exists some k such that 1% 0. Then, by Theorem 4.3, as Ay(e) converges to P3 for some j. if we choose sufficiently large т, we must have (c(c) Pr, However again by Proposition 5.5 this implies that =" is not strict linearly stable, which is absurd. Therefore, it is necessary that B = 0.
H.7 PROOF OF THBOREM H.4
Note that Ç, = J0,7 (A C by the proof of Theorem 5.4. Then the fact that Su S 0 directly follows from the assumption. Lemma H.2 implies that the eigenvalues of the form (c) = Lio, + eE) lie in P,, for any positive 77. And the remaining eigenvalues lie in P,, if and only if S 2 0 and B = O. The assertion then follows from the Proposition 5.5.
Conversely, suppose that Sees + 0 proof of Theorem H.3(ii)
* O. Then unstability of the z* directly follows from the
Next, suppose that there exists some such that &j 0. Then the fact that so 0 directly fol- lows from Lemma G.12. Hence for step size Y 8p, the 2" is not strict linearly stable point by Lemma H.2 and Proposition 5.5.
I PROOF FOR SECTION 5.4
1.1 PROOF OF THEOREM 5.7
To prove Theorem 5.7 we need the following results.
Proposition I.1. Under Assumption and 0 < n < fb-1
we have det(Dw, (z)) # 0 for all z.
2L
Proof. We begin by observing that
Dw)(2) -- DF,DF( DDDF-=-A,FLE))C--AAA.. mA,
37

---

Published as a conference paper at ICLR 2024
Since |A, || I 1, Assumption I implies that | I || DFI - L. Therefore, whenever < 1j < x5-1 21
for clarity by letting ă = = - F(), we obtain the bound
|n,, ( -A,, (MA.DD(---MAFF)))LAAAA..D)))))) -
-A, - DF()),
- [F (1+ [F(=))
(1+
2 nL (1 + nL)
<1.
follows that any eigenvalue of AA,,DE )A, - 11, has an absolute value strictly less than 1, and hence, 0 cannot be eigenvalue of (w,(z). The conclusion is now immediate.
Proposition 1.2. For any z" E T", under Assumption 2, there exists a positive constant T such that x= A" Aw,, for any 7*
Proof. By Proposition 5.5, we have
A (w=) = {2² z² = =w(22), pl p(Dw-(22)) > 1}
= (=" =² = w-(2"); FE spec (Hr(=*) s.t. X P,)-
For any strict non-minimax point x" E T either Sres (x*) or -B(²") has at least one strictly negative eigenvalue. First, suppose that (2") has strictly negative eigenvalue μ < 0. By Theorem 4.3, there exists a constant n" such that at least one eigenvalue of H; lies in a disk D pe for any > r² So by Lemma H.5, we would have D n Pa Ø. On the other hand, suppose that -=²²)) ) has strictly negative eigenvalue V < O. Similarly, by Theorem 4.3, there exists a constant r* such that at least one eigenvalue of H; lies disk D for any T > T² So by Lemma H.5, we would have DE nP, Ø. Therefore, we can conclude that for any z" E T there exists constant 7* such that x" E A (w,, for any T T
Proof of Theorem 5.7. Because z" A" (w,) implies
zo lim w²(z)) E A (w=)) (w=)) 10000
Zu
lim wh (zo) = 2- k0000
c
by Theorem 2.2, there exists positive constant 7* > such that
1 ((
#0 lim " (zo) x²) 1) =0
for any 7
Moreover, if T finite, then a maximum of T" for all xt E T is also finite. Let us denote such maximum by Tmax Then, for any Thax have T Aw,,) This implies that
lim wh c (zx) E ETT c 10000
Zu: lim wt (z0) E A" (w0-) k0
Zg
for any T > T and by Theorem 2.2, we can conclude that
1 ((
20 lim w w²(z)) E ET =0 10000
J GLOBAL CONVERGENCE ANALYSIS OF TWO-TIMESCALE EG
Let us consider the Minty variational inequality (MVD condition, defined follows, require- ment that holds for nonconvex-nonconee setting.
Assumption 4 (Minty variational inequality). For the saddle gradient operator F, a stationary point z- (x" y²") under consideration satisfies (F(z), =²) for all
38

---

Published as a conference paper at ICLR 2024
Let us now show that the two-timescale EG
u 3yK " V f 9k.) T
" V. f(uk, Vk)
Øk+1 = I/
T
U/ = yk + v (TK, yk:)
yk+1 = yk + +
s(us: / Uy)
finds a stationary point satisfying the MVI condition, built upon the proof for the plain EG (Di- akonikolas et al., 2021). Note that Diakonikolas et al. (2021) consider variant of EG, named EG+, and shows that it works for a even weaker condition, namely the weak MVI condition. The ideas behind our dynamical system analysis and the proof in the section are general enough to be further extended to EG+ and the weak MVI condition, but we leave a more detailed study in this direction as future work.
The objective function f is said to be L-smooth if the inequality [V - Vf(w)]] S LI|z - w holds for any two points x and in the domain of f. If f E C?, then it is known that f is L-smooth and only if f| < L; see, e.g., (Beck, 2017, Theorem 5.12). As ff and are equal up to a sign difference, one can observe that Assumption is equivalent to the assertion that f is L-smooth.
Theorem J.1. Suppose that f is L-smooth, and Assumption 4 holds. Then, the iterates {0x| and {yx of two-timescale EG with 1l < 4, and 2 1 satisfies |/V fI yk)ll 0 and f(r yx)ll + 0 as k + Xc.
Proof. We have the inequality
[b+11 - xx 1 + 33 - -/2
10 1 Vv (un Uk) x01
|2a + yk + 11 V (un Uk)) - -y"
1 1
2n (( V xt (ux: ux), 2x x²)) (url(us, 4¹))
| x=1 112
-v1
22
n72 +
+ 72 V (us:
W vx))
1
27 (( (V (ux; Ux), un) (us, yk -0z)
< |00g x=
1|2
11
-²1
-
2
n?2
+ 72
V Ve
fus:
+
Wuf(us. 02)1
|| x²I 112
1
y
1²122
27
((Vasuun, ow), 2 V ((ts (1)) (Vui(us, vx), -n (x0.)))
1/2
n?2 +
+ 72 V (ux: )22
[ 01)l1
-
1 |l 3²1 + ,
1?2
|| x=1 +
(1 x fu,, vk) - Val ( (a,
+ 12 (I y 5 (ux, 2na - Vys( yk )1 (
1 1 11 + (1) (ux: vn) - V V [|ll/++I[V//)) [ vn) J 9x)))
< || x: 1|2 +
2
- 7 || (xx 112
Vee f (xxx
)12
1
y2 + L2 (1|ux= - + 1111 3x
< ||00 x 1| + 1
12 V a (xx yx))
n
т || (xx y112
72
2? 7
(1 (1- 7
12122
'?? (1 - 12 V yx) yx)
< || x: 1|2 +
yv 3 1|2
(x),
7
where the first inequality uses Assumption 4, the second inequality uses 7 2 1, the third inequality uses the T-smoothness of and the last inequality uses the update rules.
39

---

Published as a conference paper at ICLR 2024
By taking telescoping summation, we have
1
L
172 x (2t, y1)11
T (1 (1-1) L²2
V f 21)1
x0" $1
+ 1y0 y 1²12 ||a++11 x=112
yv++1 y²11
VA
Fo
x² 112
-1180 y²1
1? and Σ Since both the series Ei= V y:2 they converge. Therefore we have / (mx, y
= [f v:)l are monotone and bounded,
and || V (ar,, yl1 0 as k + oo.
In general, even when a sequence (22 satisfies lime-o Fz + there is nothing we can say about the convergence of the sequence itself. In other words, the statement of Theorem J.1 alone does not guarantee the convergence of the iterates. However, what the condition limæ-o Fz - does guarantee, regardless of the MVI condition, is that any accumulation point of the sequence (zx 1220 becomes a stationary point of the objective function f. Recall that a point 2' is called an accumulation point of a sequence {=k J220 if, for any given > O, there exist infinitely many indices 1: 2 0 such that || - 2'1l <.
Lemma J.2. Suppose that f is L-smooth, and let {#k]*20 be sequence such that [[ + as k + oc. Then, any accumulation point of the sequence {z*]k20 is a stationary point of the objective function f.
Proof. Let x be accumulation point of the sequence {* J220 In that case, there exists sub- sequence { 1i20 of {= that converges to z' (Tao, 2016, Proposition 1.4.5). Then for any j 2 0, by triangle inequality it holds that
0
F(2')l < ||((2') - F(Zk, Il + ((x,))
S L||=' =k, || + F [( I||-
As both || - -zkyl and [ ||| converge to 0 as + co, we must have [[F(2') = 0.
Finally, let us demonstrate that all local minimax points of the quadratic function fa used in Exam- ple 4 satisfy the MVI condition.
Lemma J.3. Consider the functionn Any stationary point of f a local minimax point that satisfies the MVI condition.
function fæ1, F2, v1, U2,ys) = - -it--y---j00 1.3 - +220
Proof. We already saw in Section D.3 that the stationary points of f are exactly the points of the form (0, 0, f, 0, t) where & E R. and that every such point a local minimax point.
Now fix any & E R and let x" (0. 0, 0, t). One way to show that this point satisfies the MVI condition is to note that Fz* = O, while f is in fact convex-concave hence its saddle gradient F becomes so-called monotone operator; see (Ryu & Yin, 2022, Section 2.2.3). Alternatively, one can also verify this by direct computation: for any z = (I1, 22 1/. V2, Bs). it holds that
(F 2 - z²) = ((01, M/2 /1 - ys-- - 22 1/1 + v3), (x1 T2, 8/1
t, V22 Us - t))
= x + vी + v² 2y1
= 2ी + (t1 y2)
2 0
so the Minty variational inequality holds.
40


Reviews:
[{"review_id": "36GOhO3rOU", "reviewer": "Reviewer_aBEe", "summary": "This paper delves into the realm of minimax optimization, offering a comparative analysis of the two-time scale extra gradient against the two-time scale gradient descent ascent. The authors demonstrate that while the two-time scale GDA successfully converges to a specific minimax point, it encounters difficulties in the presence of a degenerate Hessian. Viewing the problem through the lens of a continuous dynamical system, the two-time scale extra gradient emerges as the superior method. It converges to the minimax point, maintaining its effectiveness even when faced with a degenerate Hessian.", "questions": "- The timescale separation technique is proposed in Jin et al. (2020) to solve the convergence of GDA, is it still necessary in the analysis of EG? How will your analysis change if using a single-timescale EG? Is it possible to still obtain similar results?\n\n- Is it possible to extend some of the analysis to the stochastic EG setting?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper is the first to remove the non degenerate assumption in literature. It defines nature new notions of restricted Schur complement and strict non-minimax point in correspondence with their assumption.\n\n- The paper adopts the high order ODE of EG, to resolve the issue of avoiding nonminimax points. This approach utilizes continuous dynamics techniques, which are then adeptly extended to the analysis of discrete dynamics.", "weaknesses": "- The authors could enhance their presentation by including additional examples or illustrative figures that emphasize the significance of the non-degenerate assumption and its impact on the algorithm's practical applicability. i.e. are there any examples that two-time scale GDA fails while two-time scale EG works?\n\n- The absence of the conclusion and discussion sections from the main text disrupts the flow and detracts from the overall reading experience.", "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": "", "extra_scores": {}}, {"review_id": "e4jkEARTNf", "reviewer": "Reviewer_yB9R", "summary": "The paper studies the local properties of the extragradient method with timescale separation between the minimizing and maximizing player. They crucially drop the previous requirement of nondegenerate $\\nabla^2_{yy} f$, by instead considered conditions on what they call the _restricted_ shur complement of the Jacobian of the saddle gradient. They show convergence to local minimax points for the discrete two timescale extragradient method and a second order continuous approximation. They further show avoidance of strict non-minimax points almost surely.", "questions": "- Thm. 4.4 of [Zhang et al. 2022](https://jmlr.csail.mit.edu/papers/volume23/20-918/20-918.pdf) seem to consider similar conditions on the restricted Shur complement. How does your results compare?\n- How does the choice of $\\tau$ propagate to e.g. Thm 6.2 or Thm 6.6? You make the final claims in terms of infinite time separation ($\\infty$-EG). Can you claim anything about finite time separation?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses the important problem of local behaviour of two-timescale extragradient in nonmonotone problems, it is technically strong and well-written.", "weaknesses": "I only have the following remark:\n\nIt seems that Thm. 6.2-6.4, Thm 6.6 and Thm. F.3 all treats _strict_ linearly stable points. The main claim that two-timescale extragradient finds (nonstrict degenerate) local minimax points (e.g. example 3) is found in Remark 6.8. The argument relies on showing avoidance of non local minimax point coupled with a _global_ convergence guarantee to a fixed point. \n\nThe remark makes it appear as if global convergence for general nonconvex-nonconcave is solved, while Diakonikolas et al., 2021 only applies to the structured problems satisfying the weak Minty variational inequality. Furthermore, the proof provided in the appendix only applies to the Minty variational inequality (MVI).\n\nI suggest toning down the claim and instead state that \"_when_ global convergence can be guaranteed (as e.g. under MVI), Thm. 6.7 implies convergence to (degenerate) local minimax points\".\n\nApart from this one case, the paper is otherwise very transparent about the claim that it makes.\n\nMinor suggestions:\n\n- Some definitions are hard to find (e.g. $H_\\tau$ on page 5). I suggest moving definitions that are needed for the theorem statements to a central place to the extend that it is possible.\n- It is probably worth mentioning [Bauschke et al. 2019](https://arxiv.org/pdf/1902.09827.pdf) work on linear operators regarding the relationship to comonotonicity. \n- It is maybe worth contrasting the timescale separation between players with timescale separation ala [Hsieh et al. 2020](https://arxiv.org/pdf/2003.10162.pdf) (also used for weak MVI).", "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": "", "extra_scores": {}}, {"review_id": "2K0t3l3KA5", "reviewer": "Reviewer_dqsM", "summary": "This paper focuses on nonconvex-nonconcave minimax optimization when the Hessian $\\nabla_{yy}^2 f$ is possibly degenerate. The authors introduce the concept of restricted Schur complement to refine the second-order condition and provide a characterization of the eigenvalues of the Jacobian matrix of the saddle gradient in an asymptotic sense. In particular, the degeneracy leads to pairs of nearly imaginary eigenvalues. To describe these eigenvalues, the authors investigate the curvature information through the *hemicurvature*. Based on this, it is established that the limit points of two-timescale EG in continuous time are local minimax points under mild conditions. Moreover, two-time-scale GDA may avoid non-strict minimax points, while two-timescale EG could find them, which demonstrates the superiority of two-timescale EG over two-timescale GDA.", "questions": "1. In Example 1, the restricted Schur complement for the two cases is zero or degenerate. Could the authors provide an example such that the restricted Schur complement is non-zero and non-singular?\n\n2. If Assumption 2 is removed, do some results in Theorem 5.3 still hold?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "The methods and conclusions in this article are valuable in terms of both originality and significance.\n\n1. In terms of originality, the authors propose a new concept, the restricted Schur complement, to refine the second-order conditions. To study the stability, the authors introduce the concept of the *hemicurvature* to characterize the eigenvalues. These concepts and tools seem novel and fascinating.\n\n2. Regarding significance, this paper improves upon previous results by eliminating the nondegenerate condition on the Hessian $\\nabla_{yy} f$ and provides solid evidence to demonstrate the superiority of two-timescale EG over two-timescale GDA. I believe the methodology and conclusions in this paper are helpful for future research in degenerate cases. \n\n3. I have checked some parts of the appendices and think the derivation is rigorous.", "weaknesses": "This is room for improvement in the presentation.\n\n1. The organization is less satisfactory and some results lack intuitive interpretation in the main text. I provide several examples below.\n \n* (i) The concept of hemicurvature is a bit opaque and the result of Proposition 6.7 is not intuitive. However, the figures in the appendix are a good illustration and could be put in the main text. \n* (ii) The authors mention that they adopt the hemicurvature instead of the curvature because of the property in Proposition C.4. From the proof, this property is indeed important and the authors should elaborate on this in the main text. \n* (iii) Theorem 6.4 is based on two additional conditions: the distinction of $\\sigma_i$ and $u_j^\\top S u_j \\ge 0 $. The authors should give more explanations on these conditions, e.g., why we need these conditions or what their role is. \n* (iv) In Theorems 6.2 and 6.6, there appear $s^*$ and $\\eta^*$. It is worth discussing their values. For example, what is the relationship between them and $s_0$?\n\nIn summary, I advise the authors to compress the review of previous results and add more interpretation in Sections 5 and 6. The methods and conclusions are valuable and deserve more elaboration. Moreover, the abstract is a bit uninformative and should also be extended.\n\n2. To demonstrate the superiority of two-timescale EG over two-timescale GDA, the authors could provide the results of GDA corresponding to Propositions 6.1 and 6.5, and then plot these regions in the complex plane as a better illustration. \n\nMinor concerns:\nIn the second instance in Example 1, the local minimax points should be $(0,0,t,0,t)$.", "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": "", "extra_scores": {}}, {"review_id": "47S03c6BO0", "reviewer": "Reviewer_8GfH", "summary": "The paper studies the local minimax points in minimax optimization when the objective is smooth and possibly nonconvex-nonconcave. They first examine the previous second-order necessary and sufficient conditions for minimax points and propose a new necessary condition that allows $\\nabla^2_{yy} f$ to be degenerate. Using dynamical system tools, they further show that two-timescale extragradient converges to points satisfying this condition under mild assumptions and almost surely avoids strict non-minimax points, while two-timescale GDA may avoid some local minimax points that are degenerate.", "questions": "See Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper proposes a new second-order necessary condition for local minimax points, which allows the Hessian $\\nabla^2_{yy} f$ to be degenerate. For some local minimax points with degenerate $\\nabla^2_{yy} f$, it is shown that two-timescale extragradient will converge to them while two-timescale GDA may avoid them. This provides a better understanding of the behaviors of classical first-order algorithms for minimax optimization. I believe this contribution is interesting enough to the community.", "weaknesses": "1. Although the proposed restricted Schur complement $S_{res}$ allows the Hessian $\\nabla^2_{yy} f$ to be degenerate, the obtained necessary condition still requires some other assumptions on $h(\\delta)$, and characterizing the limit points of extragradient through $S_{res}$ also requires other conditions like $s_0$, $\\eta^*$, $\\sigma_j$ or $\\iota_j$. These conditions, including $S_{res}$, could be computationally more heavy and cumbersome to check. Some high-level intuition about how $S_{res}$ is designed and why it is helpful could be good as well.\n\n2. What does the assumption that $S_{res}$ is nondegenerate imply? What assumptions on $H$ are necessary to make sure $S_{res}$ is nondegenerate?\n\n3. I think it would help improve the clarity of the paper by explicitly saying continuous-time GDA/EG or discrete-time GDA/EG to distinguish them. In Example 2, the paper uses both Definition 2(i) and 3 when justifying the behaviors of $xy$. However, 2(i) is for continuous time and 3 is for discrete time. Actually, $\\rho\\\\{\\pm i\\sqrt{\\epsilon}\\\\}\\leq 1$ implies linearly stability if applying Definition 3. Similar confusions between continuous time and discrete time exist elsewhere as well.\n\n4. It would improve the clarity of the paper if some notations were introduced before using them, although the meaning is well-known and can be guessed from the context.  For example, $C^2$ and $DF$ in Assumption 1, $\\lambda_j$ in Lemma 5.1, etc.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)