STay-On-the-Ridge (STON'R): Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games
Authors: Constantinos Costis Daskalakis
Noah Golowich
EFSTRATIOS PANTELEIMON SKOULAKIS
Emmanouil Zampetakis
Venue: Submitted to ICLR 2023 (2023)

Abstract: Min-max optimization problems involving nonconvex-nonconcave objectives have found important applications in adversarial training and other multi-agent learning settings. Yet, no known gradient descent-based method is guaranteed to converge to (even local notions of) min-max equilibrium in the nonconvex-nonconcave setting. For all known methods, there exist relatively simple objectives for which they cycle or exhibit other undesirable behavior different from converging to a point, let alone to some game-theoretically meaningful one [Flokas et al. '19, Hsieh et al. '21]. The only known convergence guarantees hold under the strong assumption that the initialization is very close to a local min-max equilibrium [Wang et al. '19]. Moreover, the afore-described challenges are not just theoretical curiosities. All known methods are  unstable in practice, even in simple settings.
  
We propose the first method that is guaranteed to converge to a local min-max equilibrium for smooth nonconvex-nonconcave objectives. Our method is second-order and provably escapes limit cycles as long as it is initialized at an easy-to-find initial point. Both the definition of our method and its convergence analysis are motivated by the topological nature of the problem. In particular, our method is not designed to decrease some potential function, such as the distance of its iterate from the set of local min-max equilibria or the projected gradient of the objective, but is designed to satisfy a topological property that guarantees the avoidance of cycles and implies its convergence. 

Under review as a conference paper at ICLR 2023
STAY-ON-THE-RIDGH GUARANTEED CONVERGENCE TO LOCAL MINIMAX EQUILIBRIUM IN NONCONVEX- NONCONCAVE GAMES
Anonymous authors Paper under double-blind review
ABSTRACT
Min-max optimization problems involving nonconvex- cow.ovvve---nccccveeee objectives have found important applications in adversarial training and other multi-agent learning settings. Yet, no known gradient descent-based method is guaranteed converge (even local notions of) min-mat max equilibrium in the nonconvex-nonconcavv For all known methods, there exist relatively simple objectives for which they cycle or exhibit other undesirable behavior different from converging to point, let alone to some
nonconcave setting.
meaningful one Vlatakis Vlatakis-Gkaragkae Gkaragkounis al. (201 9); Hsich et al. (2021). The only known convergence guarantees hold under the strong assumption that the initialization is very close to a local min-max equilibrium Wang et al. (2019). Moreover, the afore-described challenges are not just theoretical curiosities. All known methods are unstable in practice, even simple settings.
We propose the first method that is guaranteed to converge to a local min-max equilibrium for smooth mnnconve-nnononnawe objectives. Our method second- order and provably escapes limit cycles as long as it is initialized at an easy-to-find initial point. Both the definition of our method and its convergence analysis are motivated by the topological nature of the problem. In particular, our method is not designed to decrease some potential function, such as the distance of iterate from the set of local min-max equilibria the projected gradient of the objective, but is designed to satisfy a topological property that guarantees the avoidance cycles and implies its convergence.
INTRODUCTION
Min-max optimization lies at the foundations of Game Theory von Neumann (1928), Convex Optimization Dantzig (1951a); Adler (2013) and Online Learning Blackwell (1956); Hannan (1957); Cesa
Cesa-Bianch Bianchi & Lugosi (2006), and has found many applications in theoretical and applied fields including, more recently, in adversarial training and other multi-agent learning problems Goodfellow et al. (2014); Madry et al. (2018); Zhang et al. (2019). In its general form, it can be written
min max (0, AEE wenl
where è and Ω are convex subsets of the Euclidean space, and f continuous.
Equation (I) can be viewed as a model of a sequential-mon -ove game wherein player who is interested minimizing ff chooses first, and then a player who is interested in maximizing f chooses after seeing 0. Solving (1) corresponds to an equilibrium of this sequential-movt game.
We may also study the simultaneous-ni move move game with the same objective f wherein the minimizing player and the maximizing player choose O and w simultaneously. The Nash equilibrium of the simultaneous move game, also called a min-max equilibrium, a pair (0*, (0*="" E θ such that
f(0", w S w"),")) for all 0 θ and f(0", w²) 2 f(00, w), for all w e Ω.
(2)
It is easy to see that Nash equilibrium of the simultaneous-mont move game also constitutes a Nash equilibrium of the sequential move game, but the converse need not be true Jin et al. (2019). Here, focus on solving the (harder) simultaneous-move game. In particular, study the existence

---

Under review as a conference paper at ICLR 2023
of dynamics which converge to solutions of the simultaneous move game, namely the existence of methods that make incremental updates to a pair (f,, wi) so as the sequence (0,, wir converges, as t + 00, to some (0*, w*) satisfying equation 2 or some relaxation of it.
This problem has been extensively studied in the special case where é and Q2 are convex and compact and f is convex-concave set of Nash equilibria of the simultameous-mont move game is equal to the set of Nash equilibria of the sequential-move game, and these sets are non-empty and convex von Neumann (1928). Even in this simple setting, however, many natural dynamics surprisingly fail to converge: gradient descent- ascent, as well as various continuous- converge to a min- min-max equilibrium, even for very simple objectives, but may even exhibit chaotic behavior Mertikopoulos et al. (2018); Vlatakis- Gkaragkounis et al. (2019); Hsieh et al. (2021). In order to circumvent these negative results, an extensive line of work has introduced other algorithms, such as extragradient Korpelevich (1976) and optimistic gradiens descent Popov (1980), which exhibit last-iterate convergence to the set of min-max equilibria in this setting; see e.g. Daskalakis et al. (2018); Daskalakis & Panageas (2018); Mazumdar & Ratliff (2018); Rafique et al. (2018); Hamedani & Aybat (2018); Adolphs et al. (2019); Daskalakis & Panageas (2019); Liang & Stokes (2019); Gidel et al. (2019); Mokhtari et al. (2019); Abernethy et al. (2019); Golowich et al. (2020b;a); Gorbunov et al. (2022); Cai al.. Alternatively, one may take advantage of the convexity of the problem, which implies that several no-regret learning procedures, such as online gradient descent, exhibit average-iterate convergence to the set of min-max equilibria Cesa-Biande & Lugosi (2006); Shalev-Shwartz (2012); Bubeck & Gesa-Bianch (2012); Shalev-Shwarte & Ben-David (2014); Hazan (2016). Beyond the convex/concave setting Lin et al. (2020); Kong & Monteiro (2021); Ostrovskii et al. (2021) show that convexity with respect to one of the two players is enough to design algorithms that exhibit average-iteran convergence to min- min-max max equilibria while Diakonikolas al. (2021) and Pethick et al. (2022) provide convergence results for weak Minty variational inequalities.
i.e. convex in 0 for all w and concave in w for all A. In this case, the
versions of wegloo-thh-regulatt
-laderr not only fail to
Our focus in this paper is on the more general case where I not convex-concave i.e. it may fail to be convex in 0 for all w, or may fail to be concave in w for all 0, or both. We call this general setting where neither convexity with respect to l nor concavity with respect to w is assumed, the nonconvex- nonconcave setting. This setting presents some substantial challenges. First, min-max equilibria are not guaranteed to exist, i.e. for general objectives there may be no (0",w*) _-) satisfying equation 2; this happens even in very simple cases, e.g. when @ = Ω [0, 1] and f(, = (0 - w)². Second, it is NP- to determine whether a min-max equilibrium exists Daskalakis et al. (2021) and, as easy see, it is also NP-hard to compute Nash equilibria of the sequential-move game (which do exist under compactness of the constraint sets). For these reasons, the optimization literature has targeted the computation of local and/or approximate solutions in this setting Daskalakis & Panageas (2018); Mazumdar & Ratliff (2018): Jin et al. (2019); Wang et al. (2019); Daskalakis et al. (2021); Mangoubi & Vishnoi (2021). This is the approach we also take in this paper, targeting the computation of (c, 5y-oocal min-max equilibria, which were proposed in Daskalakis et al. (2021). These are approximate and local Nash equilibria of the simultaneous-move game, defined as feasible points (0*, w*) which satisfy a relaxed and local version of equation 2, namely:
f(8,, < f(0, + c, for all f E θ such that ||0 8* < 8: 5(0", (0","")> /(0", w) - e, for all w E Ω such that ||ا w || < 8.
(3)
(4)
Besides being natural concept of local, approximate min-max equilibrium, an attractive feature of (e, -locll min-max equilibria that they are guaranteed to exist when f is A-smooth and the locality parameter, 5, is chosen small enough in terms of the smoothness, A, and the approximation
Indeed, in this regime of parameters the (c, -oocal parameter, namely whenever 5 < V A
min-max equilibria are in correspondence with the approximate fixed points of the Projected Gradient Descent/Ascent dynamics. Thus, the existence of the former can be established by invoking Brouwer's fixed point theorem to establish the existence of the latter. (Theorem 5.1 of Daskalakis et al. (2020)).
There are a number of existing approaches which would be natural to use to find solution (0* ,w") satisfying equation 3 and equation 4, but all run into significant obstacles. First, the idea of averaging, which can be leveraged in the convex-concave setting to obtain provable guarantees for otherwise chaotic algorithms, such as online gradient descent, no longer works, as it critically uses Jensen's 's inequality which needs convexity/concavity. On the other hand, negative results abound for last- iterate convergence: Hsich et al. (2021) show that a variety of zeroth, first, and second order methods may converge limit cycle, even in simple settings. Vlatakis Saaakkik-Gaaakkoouiii et al. (2019) study
2

---

Under review as a conference paper at ICLR 2023
particular class of nonconvex-
games and show that continuous- time gradient descent- ascent (GDA) exhibits recurrent behavior. Furthermore, common variants of gradient descent-ascent, such optmistic GDA (OGDA) extra- aataiegradeet (EG), may be unstable even in the proximity of local min-max equilibria, or converge to fixed points that are not local min-max equilibria Daskalakis & Panageas (2018); Jin et al. (2019). While there do exist algorithms, such FOLL.OW-THE-RIDE proposed by Wang et al. (2019), which provably exhibit local convergence to a (relaxation of) local min-max equilibrium, these algorithms do not enjoy global convergence guarantees, and no algorithm is known with guaranteed convergence to local min-man max equilibrium.
These negative theoretical results are consistent with the practical experience with mii-maximization of nonconvex nonconcave objectives. which is rife with frustration as well. A common experience is that the training dynamics of first-order methods are unstable, oscillatory or divergent, and the quality of the points encountered in the course of training can be poor; see e.g. Goodfellow (201 6); Metz et al. (2016); Daskalakis et al. (2018); Mescheder et al. (2018), Daskalakis & Panageas (2018); Mazumdar Ratliff (2018); Mertikopoulos et al. (2018); Adolphs et al. (2019). In light of the failure of essentially all non-trivial, i.e., non brute-force, algorithms to guarantee convergence, even asymptotically, to local min-max equilibria, we ask the following question: Is there any local-search algorithm which is guaranteed to converge to a local min-mus max equilibrium in the nonconvex nonconcccee setting? (see Table
1.1 OUR CONTRIBUTION
In this work we answer the above question in the affirmative: we propose second-order method that is guaranteed to converge to local min-max equilibrium (Theorem 1).. Our algorithm, called STAY-ON-THE-RIDE which only converges locally. STON'R is the first method guaranteed to local min-max equilibrium setting. Both the structure of our
or STON'R, R, has some similarity to FOLLOW- BELLOO--TT-RRREE THE-RIDGE or FTR,
beyond the brute-force grid-search in the non-convex/non-coneee algorithm and its global convergence analysis are motivated by the topological nature of the problem, as established by Daskalakis et al. (2021) who showed that the problem is equivalent to Brouwer fixed point computation. In particular, the structure and analysis of STON'R are not based on potential function argument but on a parity argumen! (see Section 4), akin to the argument used to prove the existence of Brouwer fixed points. The main challenge of our work to prove that there exists an algorithm that uses only local information of the objective function f. i.c., only its second derivative, while satisfying the topological properties that are necessary to guarantee global convergence. In order to understand the main technical contributions of our paper we need first to introduce the main steps of showing the convergence using a topological argument in Section 4. Then Section 5.4 we provide sketch of our proof and we highlight the technical difficulties that we face.
convex-concave
nonconvex-concave
nonconvex-noncconaae
existence
yes
no!
not
Nash Eq.
complexity
poly-time
NP-hard*
NP-hard*
convergent dynamics
many*
not applicable
not applicable
Local Nash Eq.
existence
same as above
yes+
yes*
complexity
same above
poly-time+
PPAD-hard*
convergent
same as above
many+
This paper
dynamics
Table 1: Summary of known results for simultaneous zero-sum games with differing complexity in their objective function. (D) v. Neumann (1928) (t) c.g., the min-max game with objective function f(0 w) -(0 - w) where 0 E [-1, 1] and 11, does not have any Nash Equilibrium. (+) Daskalakis et al. (2021) (t) e.g., Dantzig (1951b); Freund & Schapire (1997); Shwlarz (2012): Cesa- Cesa-Bianche Bianchi Lugosi (2006) (+) e.g., Lin al. (2020); Kong & Monteiro (2021); Ostrovskii al. (2021)
3

---

Under review as a conference paper at ICLR 2023
2 SOLUTION CONCEPT
We begin with formulating our problem in the more general framework of variational inequalities. This simplifies our definitions and notations and also makes our result applicable to more general settings such as multi-player concave games Rosen (1965).
Variational Inequalities (VI). For K C IR" consider continuous map V : K - R We say that I E K is a solution of the variational inequality VI(V, K) iff: V(x) (2 y) 2 for all E K.
It is well known that finding local min-max equilibria of smooth objectives can be expressed as a non mon-moont VI problem. Specifically, consider the min-max optimization problem (1), take K == θ x f and simplify notation by using x: E K to denote points (f,w) E K. Call the subset of coordinates of x identified with I the "minimizing coordinates" and the subset of coordinates of x: identified with w the "maximizing coordinates." 'Ten define V K + Rº as follows:
For j E [na] set (z(z) == af(z) if is minimizing, and (z( ;= 0f(z)
dz, otherwise.
dz, Computing (s, 6)-local min-max equilibria of smooth objectives, i.c. points satisfying (3) & (4), can be reduced to finding solutions to VI(V, K). In fact, finding even an approximate VI solution x satisfying 7(x))(< (xx y) 2 aa, Vy E K, would suffice as long as a > is small enough. For more details see Theorem 5.1 of Daskalakis et al. (2020). Hence, for the rest of the paper we focus on solving variational inequality problems. For simplicity exposition we take our constraint set to be K [0, In this case there is a simple characterization of the solutions to VI(V,
Definition 1. We call a coordinate satisfied at point x E [0, 1|"h if one of the following holds:
1. i is zero-satisfied at v, ie, V1(1:) 0, or
2. i is boundary-satissied at x, i.e, (Vx S 0 and x; 0) or (Vi(1) 2 0 and 1). Lemma (Proof Appendix D). x a solution of V1(V, 1) iff j is satisfied at x, Vj E [n].
Finally, in the rest of the paper we make the following assumptions for V: (A-Lipschitz)
[IV(z) - V2y)l22 S A || vll2, for all 2, E [0, 1]"
(L-smooth)
[J(z) Il s L- || yll2. for all x, y E 1]
where J is the Jacobian of and ||||| denotes the Frobenious norm of the matrix A.
3 STAY-ON-THE-RIDGE HIGH-LEVEL DESCRIPTION
In this section we describe our algorithm and discuss the main design ideas leading to its convergence properties presented in Section 5. As explained in the previous section, our goal is to find point such that every coordinate E [n] is satisfied at J according to the Definition 1.
Our algorithm is initialized =0) (0.... 0). The goal of the algorithm is to satisfy all unsatisfied coordinates one-by-one in lexicographic order (although, as we will see, coordinates may go from being satisfied to being unsatisfied in the course of the algorithm). We say that our algorithm "starts epoch at point x" iff all coordinates < - are satisfied at x and the algorithm's immediate goal is find a point x' * x that satisfies all coordinates S namely:
Goal of epoch i, starting at point w:: find x' 7 satisfying all coordinates S i.
Let us assume that, at time f, our algorithm starts epoch at point rtt). Let us also assume that, at rtt). all coordinates < é-1 are aero-satisfied (see Section 5.1 for the general case), i.e., Vz(()) 0 for all j 5 - 1. Our algorithm tries to achieve the goal of epoch starting at 20 (t) as follows:
Our algorithm tries to find such a point inside the connected subset 5 (x(()) C [0, 1]" that contains all points satisfying the following: (a) all coordinates < i 1 are zero-satisfied z, and (b) for all j 2 i 1, = (t).
Our algorithm navigates S (=(t)) in the hopes of satisfying the goal of epoch i. A natural approach is to navigate (x((()) is run continuous-time dynamics {=(7))+20 that is initialized at 20)) = z(t) and moves inside S (z((). What possible directions of movement so that our dynamics stay within St (x(()) If the dynamics is at some point e {²(xt)), it will remain in this set if it moves, infinitessimally, in unit direction d satisfying the following constraints:
4

---

Under review as a conference paper at ICLR 2023
1. d, = for all 1; / guarantee (b) in the definition of S' (x(()) %/ (VV;(=))* d= 0, for all j E (1.....;- Notice that and 2 specify n constraints on variables. We will place mild assumptions V so that there is unique, up to sign flip, unit direction satisfying these constraints (see Assumption 1). Moreover, in Definition 2 we specify a rule to choose one of the two unit directions satisfying constraints. We denote by (z) the direction that our tic- brobbrrakigg rule selects at z.
/ to guarantee (a) %/
With the above choices, the continuous-time dynamies ((T) = (+))) initialized at =(0) xx(), is well-defined. We follow this dynamics until the earliest time that one of the following happens:
-Good Event): the dynamics stops at a point * xrtt) where coordinate i is satisfied;
- (Bad Event): the dynamics stops at point x' lying on the boundary of [o, 1]"h (and it were to continue would violate the constraints).
So we have described what our algorithm does if, at time t, it starts epoch i at xr).. Suppose x' the point where our dynamics executed during epoch i terminates. If the good event happened, coordinate i is satisfied at x', and our algorithm starts epoch i + at x'. If the bad event happened, our algorithm will in fact start epoch 1 at point x'. What does this mean? That will run the continuous-time dynamics corresponding to epoch i 1 on the set (a=1(x') starting at a' in order find some point x" * x' where all coordinates < i - are satisfied. It may fail to do this, in which case it will start epoch i 2 next. Or it may succeed, in which case, it will start epoch i, and so forth until (as we will show!) all coordinates will be satisfied. The high-level pscudocode of our algorithm is given in Dynamics 1.
Dynamics STaa-ON-the Ridge (STON'R, High-Level Description
1: Initially x0) + (O..... 0). i t 1, + 0.
2: while ztt) not a VI solution do
3: Initialize epoch i's continuous-time dynamics, =(r) (*(2)))) at =(0) = =x(t). 4: while exit condition of this dynamics has not been reached do
5: Execute æ(T) (=((T)) forward in time.
6: end while
7:
Set ar(1 +7) z(T) for all E [0, Texis] (where Texis is time exit condition was met).
8:
ir a(t + Texit) # x(f) and coordinate i is satisfied at art + Texit) then
9:
Update the epoch i < i 1.
10: else
11:
(Bad event happened so) move to the previous epoch i <- i 1.
12:
end if
13:
Set <- - Texit-
14:
end while
return (t)
At this point we have described an algorithm that explores the space in a natural way in its effort to satisfy coordinates, but is unclear why would eventually satisfy of them, how would escape cycles, and how it would not get stuck at non non-equilibrium points. Importantly, there is no quantity that seems to consistently improving during the execution of the algorithm.
How we can show convergence since no quantity seems to be consistently improving?
A TOPOLOGICAL ARGUMENT OF CONVERGENCE
Our main idea to show the convergence of the STON'R algorithm is to use topological argument illu- trated in Lemma 2 that has been employed to show the convergence of other equilibrium computation algorithms such as the elebrated
algorithm Lemke & Howson (1964).
Let G (N, E) be directed gruph such that every node has in-degree at most and out-degree at most 1. If there exists some node N with in-degree 0 and out-degree 1, then there is unique directed path starting at u and ending at some v' E N that has in-degree 1 and out out-ooutreee degree
Lemma 2.
The proof of Lemma is straightforward, as Figure illustrates. The lemma suggests recipe for proving the convergence of some deterministic, iterative algorithm, with update rule V-+1 <- F(ve). whose iterates lie in finite set N:
5

---

Under review as a conference paper at ICLR 2023
Figure 1: directed graph whose nodes have in-degree and out-degree at most 1 is collection of directed paths, directed cycles, and isolated nodes. Hence, if node has in-degree 0 and out-degree 1 then it has to be the start of directed path that must end node v' after finite number of steps.
1. Define graph G with vertices N and edges F = {u,, v) o and F(u)). i.e., there is an edge from u to iff u o u and v is reached after an iteration the algorithm starting at u.
2. Argue that every vertex of G has in-degree I 1. It is clear that every vertex has out-degree < 1.
3. Show that the algorithm can be initialized some vo that has in-degree 0 and out-degree 1.
4. Employ Lemma to argue that if the algorithm initialized at vo must, eventually, arrive at some node Vend whose out-degree is O. Out-degree 0 means that Vend F(Vend).
5. The above prove that the algorithm starts at vi it guaranteed converge.
In the course of the description of the algorithm and its convergence proof in Section 5, specify finite set of nodes of the graph that we will construct to employ the above convergence argument. Intuitively, these are all the points which map F(.) that we use to construct our graph is the outcome of the continuous process that our algorithm execute when it starts an epoch at such a point.
algorithm
possibly start new epoch. The
DETAILED DESCRIPTION OF STON'R R AND MAIN RESULT
We provide formal description of our algorithm (Section 5.1), state our main convergence theorem (Section 5.2), and the main components of its proof building on the ideas (Section 5,4),
5.1 STON'R R: DETAILED DESCRIPTION
In Section 3 we focused on the epochs where all coordinates point and the goal is to identify some x' A x all coordinates <. i are satisfied. To achieve this, we execute a continuous-time dynamics constrained by keeping all coordinates S i zero-satisfied. However, in the course of these dynamics we be hit the boundary. So, when start some coordinates will be zero-satisfied and some will be boundary-satisfied. algorithm needs to execute continuous-time dynamics constrained by keeping the vero-satisfied coordinates zero-satisfied as well as the coundary-satisfin coordinates at the right boundary.
are zero-satisfied at the initial
epoch, that general case, the
Namely, the epochs indexed by coordinate i [n] and subset of coordinates S C [i 1] that are zero-satisfied at the point x where the epoch starts. The goal of each epoch is the following.
Goal of epoch (i,S). starting point (where S S [i- 1], coordinates in S are zero- zero- satisfied and coordinates in [i 1] S are boundary-satissied); find x' A x where all coordinates S are satisfied, all coordinates in S are zero-satisfied, and all coordinates in [1] S are boundary-satissied.
Epoch S) starting at æ might achieve its goal or end before achieves its goal. In both cases, a new epoch will start. Within each epoch our algorithm executes continuous-time dynamics that maintains all the coordinates. j E S zero-satisfied, all the coordinates. j E [i - 1] \ boundary-satisfied, and leaves all coordinates [n] \ [8] unchanged.
Definition 2 (Tangent Unit Vector of Epoch ()).)). Let i [n], S {si,.... 8m) } S 11. and x E [0, 1) we say that a unil vector dl E IR" is admissible if:
1. d = for all j & USUUU (i), and
2. VV) d d= 0, all E S, and
aV, (z)
aV,, (x)
aVa. (2) Owa.
dap
de.,
3. the sign of
equals the sign of (-1)18),
8V, (x)
8V,, (x)
oV (x)
dam
Dzem
02
8V. (Ga)
aV,, (2) di..
av..
de
dz.
Des
there unique unit direction satisfying the above constraints, denote that direction D's(2)).

---

Under review as a conference paper at ICLR 2023
Conditions 1 and 2 above describe a line in R" and condition 3 specifies direction on this line. We will place some assumptions on V so that (2)( is defined for all æ E [0, 1]" where coordinates S zero-satisfied (see Assumption 1). Now, when start epoch (i. S) at point æ, we will execute the continuous-tiie dynamics =(7) = D' (=))) initialized at =00 = x; forward in time. We this dynamics until the earliest time Texit such that 2Foxitt is exit point according the next definition.
Definition 3. Suppose E [n]. S [ 1--1, 11, at x' E [0, 1]", the coordinates in S are sarossatisfied at x', the coordinates in fi-10 1] \. S are boundary- at x'. Then x' is exit point for epoch (i,S) S) iff it satisfies one of the following:
(Good Exit Point): Coordinate i is satisfied at x', i.e. Vi(x²) = O. or x = =0 and Vi(x') < 0, or
x == and Vi(x')
) > 0.
(Bad Exit Point): 3j USU [i} s.I. (D'(z')); O and x²y L, or (Di(I'))s 0 and a/j
ie.. if the dynamics of epoch (i, were to continue from x', they would violate the constraints.
(Middling Exit Point): 3j E - 1] S s.I. Vy(x²) = 0 and (VV;(x') (ig='))(((xxx))) > 0 and xtJ 0) or (VVj(x')) T D's(z') < 0 and zzy 1), i.e., the dynamics for epoch (i, S) were to continue from x', some boundary- coundary-satisfied coordinate would become unsatisfied.
We will place some assumptions on V so that there can be a unique triggering the condition of Bad Exit Point and there can be a unique j triggering the Middling Exit Point condition (see Assumptions 2). Below we describe the actions that we take when one of the above exit conditions is triggered.
Action at Good Events. In case of a good event, we start epoch (i + 1, S") at x', where S SU is zero-satisfied n', and
S, if is noundary-satisffi
Action at Bad Events. In case of bad event, note that the coordinate j responsible for the condition in the bad event must belong SU {i} because in all other coordinates (D'((''), 0 by definition.
Our action depends on which triggers the bed event as follows:
(1) if the triggering j = i, then we start epoch
1, S (i- (i- 1)) at x', otherwise
(2) if the triggering * i, then start epoch (i, (i)) at z'.
Action at Middling Events. In this case, we start epoch (i, U (i)) at because the coordinate j is both zero- and boundary-satisfi at x' we add to S to keep it zero-satisfied next.
Combining the above rules we get full description of our algorithm in Dynamics 2. In Appendix do step-by-step execution of this algorithm for simple 2D min-max optimization problem.
Dynamics STay-ON-the (STON'R)
1: Initially (0) + (O....,.0) 0). + 1, 1.
2: while (z) a VI solution do
3: Initialize epoch (i, S)'s continuous
dynamics, *(T) = D'{(=(T),, at 2(0) z(t).
4: while 2(7) is not an exit point as per Definition do
5: Execute 2(T) Dis(z(T)) forward in time.
6: end while
7: Set rtt + r) =(T) for all E [0, Texie] (where Texit is the time 2(T) became an exit point).
8:
if att + Texit) is (Good Exit Point) as Definition 3 then
9:
if i is zero-satisfied at ætt + Texit) then
10:
Update S (i).
11:
end if
12:
Update i + i 1.
13:
else if x1( + Texit) is (Bad Exit Point) as in Definition 3 for j then
14:
Update i + i - and S + S [d-1).
15:
else if .r(1 + Texit) is (Bad Exit Point) as in Definition 3 for j ب i then
16:
Update S + S [j}-
else if (t + Texit)
(Middling Exit Point) as in Definition 3 for j < then
18:
Update S + S UUS.U. {i}.
end if
20: Set t < t Texit-
21:
end while
22: return x(1)
7

---

Under review as a conference paper at ICLR 2023
5.2 OUR ASSUMPTIONS AND OUR MAIN THEOREM
We next present the assumptions on V that are needed for our convergence proof. We discuss these assumptions further in Appendix A where present some high level reasons why they are mild. Assumption 1. There exist real numbers max > min > such that: for all x E [0, 1 and for all S -S1,...,,,,, 1m1 S [n] if V+(x) for all E S, then the singular values of the m x matrix
J (x) are greater than min and less than mans where
9V,, (a) Oe
8V, (a)
Oz mm
(x)
mV (x) Owa
oV (x) d2.m
Assumption ensures that the direction (-)()) of Definition uniquely defined (see Lemma in Appendix 8).
Assumption 2. For all x E [0, 1]", for all i [n], and for all S S 1]: if Vf( = A E S and Iz E (0, 1) vl & SU {i} then there is at most one coordinate j E S { such that Ij E 1),
Assumption 2 ensures that any time at most one coordinate can trigger a middling or a bad event. To see this, imagine there are two different coordinates J1. triggering bad event x, then JJ E {0. 11,4g, E {0, and Vj, (x) Vj2 (z) = O and therefore Assumption 2 is violated. A similar observation applies for middling events. See also Lemma and Lemma 10 the Appendix. for
Assumption 3. For all x E [0, 1)", for all i E [m]] for all 5 C -1 such that Vi(z) 0 E S and E 1) VA & SU {i), and for all vectors (ds))... dsm= d4) satisfying the equations,
SL (z) (d.,........................((.. den. d.) = 0 for all E S,
have that dj + 4 if = 0 or or
Assumption ensures that looking at the Jacobian of V. For example, consider a coordinate j such that z; = and Vj (x) = also (z) VV = 0 then higher-order information is needed in order to determine whether the direction (-) makes the coordinate j satisfied or unsatisfied (see Lemma the Appendix).
determine whether coordinate begins stops being satisfied by
We now ready state main theorem.
Theorem 1. Under Assumptions 1, 2, and 3, there exists some T = T T Ti, A) such that "TAY-ON-THE-RIDAN
(Dynamics 2) will stop, at some time S T, at some point xTT) E [0, 1]th that is solution of VI(V, [0, 1]").
Remark (Discrete-time Algorithm). is possible to combine the proof of Theorem with standard numerical analysis techniques to show the convergence of simple discrete version of the dynamics assuming that the step size is small enough. For more details about this we refer to Appendix J.
5.3
SIMULATED 2-DIMENSIONAL EXAMPLE
In Figure we present the behavior of the main existing al- gorithms for min-max optimization the 2-dimensional min- problem with objective f(0,w)
Aw w2 2
2 w2, where S(z) is the smooth-step function equal to S for S 0. for 2 and 2² 22 otherwise. With biue observe the behavior of GDA, EG, and OGDA that have the same behavior this example when initialized at (-0.5, -1). With orange we observe the behavior of the follow-the-ridee (FtR) algorithm initialized at (-0.5, 0.5)) and with green we observe the behavior of STON'R RON'.RAA As we can see GDA, EG. OGDA are get- ting trapped to a cycle whereas FIR hits the boundary at (-1, 1) that does not correspond to equilibrium point. Our algorithm is the only one that directly converges to the equilibrium following very short path. In Appendix C we provide explanation of this example and we observe similar behavior for different initializations GDA, EG, OGDA, and FiR.
0.5
0.0
-0.5
1.00
-1.0
-0.5
0.0
0.5
1.0
Figure 2
detailed
8

---

Under review as a conference paper at ICLR 2023
5.4 SKETCH OF PROOF OF THEOREM
1
For a sketch of our proof of Theorem 1 we follow the recipe that we described in Section 4. During this proof sketch we highlight some technical challenges that we face. (The full proof can be found in Appendix E.)
1. We start with the definition of the set of nodes N. The set N contains triples of the form a,
where i E [n). 5 is a subset of [ 11-1] 1] and x E [o, 1]" that satisfies the following:
(a) all coordinates in S are zero-satisfied, (b) all coordinates in [č 1] \ S are boundary-satisee satisfiedd
(c) 2jj = 0 for all j 2 i + 1, and either (d1) 2; = 0 or (d2) z is an exit point for epoch (i. S) according to Definition 3
Our first technical challenge to show that the size of N finite (see Lemma 3 in the Appendix). Next we describe a mapping
N - N. Let (1, S, E N, we use the dynamics = D's (2) with initial condition z(0) = I and we find the minimum time Texit such that z(Texit) ) is an exit point. We then update i, S to i', S" according to the rules for actions on exit points of Section 5,1 and we define F((i, S, x)
(d', ((Textt)) One of our main technical challenges is to show that the dynamics & = D (2) have a unique solution under our assumptions and hence F is well defined (see Lemma 4 in the Appendix).
The set N and the mapping F' define the directed graph G, as described in Section 4, that is guaranteed to have vertices with out-degree at most 1. We also show that any e E V with out-degree 0 is an equilibrium point (see Lemma 4 in the Appendix).
2. To show that the in-degree is at most 1, we face our next technical challenge which is to show that we can actually solve the dynamies backwards in time. particular, if we specify z(0) and there is the smallest time Texit such that =--Texit) is an exit point then z 3(-Texit) ) is uniquely determined. This means that there exists F-1
+ N such that if o' = F(v) then [v') = e which means that no vertex in N can have in-degree more than (see Lemma 5 in the Appendix).
3.
0)) E N and that if run the dynamics 1 = D1(x)) backwards in time starting at =0) = then we get outside [o, 1]" and so vo has in-degree O. We also show that the dynamics
We show that ti = (1, D. (O,...,0))
(2) can move forward in time and stay inside [0, 1]" zy has out-degree 1
(see Lemma 6 in the Appendix).
4. The above show that our algorithm converges according to Section 4.
6 CONCLUSIONS
Summary. In this work we propose a novel local-search algorithm, called STON'R, R, that is guaranteed to converge local min-max equilibrium in the general case of non-convex non-concave objectives. To the best of our knowledge STON'R R is the first method, beyond trivial brute-force, that is guaranteed to find local min-max equilibrium starting from a simple initialization. We remark that existing min-max optimization methods required either convexity (resp. concavity) in one of the players or an initialization very close to the optimal point in order to guarantee convergence. Finally, our approach differs from existing methods in the fundamental way that both its design and analysis are based on topological rather than potential arguments. We believe that these types of arguments can play an important role in the future of multi-agent machine learning.
Comparison with Brute-Force. Since we assume that is Lipschitz function and that K is an n n-dimensional hypercube, it is not hard to see that there exists a small enough discretization of the space such that the brute-force search over all the discrete points is guaranteed to find a solution. Such brute-force algorithms exist in most of the optimization problems like solving linear programs or finding Nash equilibria in normal form games. These trivial algorithms suffer from the curse of dimensionality even in very simple instances and hence they almost never useful. Instead local- search algorithms such as simplex or Hookee Lemke& & Howson (1964) have been extremely successful in practice because they converge very fast in the majority of real world instances although in the worst-case their complexity is the same as the brute-force. Our contribution to provide the min-max optimization
first such algorithm for the fundamental problem of and we believe that it will play an important role in the future of multi-agent optimization in machine learning.
'The actual set of nodes that we used in the proof does not contain the information of i and S but we refer to the Appendix for the exact proof.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Jacob Abernethy, Kevin A Lai, and Andre Wibisono. Last-iterate convergence rates for min-max optimization. arXiv preprint arXiv:/906.0200 2019.
Ilan Adler. The equivalence of linear programs and zero-sum games. International Journal of Game Theory, 12(1))165-177, 2013, doi: 10.10077:000122-0---222---
Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann. Local saddle point optimization: A curvature exploitation approach. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 486-495, 2019.
David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific J. Math., 6(1):1-8, 1956. doi: 10.21400pjm..1956 1956.6.1.
Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012. doi: 10.1561/22000000224
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games.
Nikolo Dasa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
George B. Dantzig. A proof of the equivalence of the programming problem and the game problem. In Koopmans, T. C., editor(s), Activity Analysis of Production and Allocation. Wiley, New York, 1951a.
George B Dantzig. A proof of the equivalence of the programming problem and the game problem. Activity analysis of production and allocation, 13, 1951b.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, pp. 9236-9246,
2018.
Constantinos Daskalakis and loannis Panageas. Last-iterate convergence: 7ero-sum games and constrained min-max optimization. Innovations Theoretical Computer Science, 2019.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In International Conference on Learning Representations (ICLR 2018), 2018.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. CoRR, abs/2009.09623. 2020. URL https: http:p::///xxx..xxrt/.. org. abs/ 2009.096220
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The Complexity of Constrained Min-Max Optimization. In Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC), 2021.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael I. Jordan. Efficient methods for structured -ow.neev---onocccveeee min-max optimization. In Arindam Banerjee and Kenji Fukumizu (eds.). The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, volume 130 of Proceedings of Machine Learning Reseurch, pp. 2746-2754. PMLR, 2021.
Yoav Freund and Robert E Schapire. A decision-theoreee generalization on-line learning and an application to boosting. Journal of computer and system sciences, 55(1): 19--139, 1997.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Simon Lacoste-Julien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1802-1811, 2019.
10

---

Under review as a conference paper at ICLR 2023
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), 2020a.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-coneave saddle point problems. In Conference on Learning Theory, pp. 1758-17844 PMLR, 2020b.
lan Goodfellow. Nips 2016 tutorial: Generative adversarial networks. arXiv preprint
arXiv:1701.00160, 2016.
Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative Adversarial Nets. In Proceedings of the Annual Conference on Neural Information Processing Systems, 2014.
Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: (1/k) last-iterate con- vergence for monotone variational inequalities and connections with cocoercivity. In International Conference on Artificial Intelligence and Statistics, pp. 366-402. PMLR, 2022.
Erfan Yazdandoost Hamedani and Necdet Serhat Aybat. A primal-dual algorithm for general convex- concave saddle point problems. arXiv preprint (oXivv/803.01444 2018.
Hannan. Approximation to Bayes risk in repeated play. Contributions the Theory of Games, 97-139, 1957.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157-325, 2016.
Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-max optimization algorithms: Convergence spurious non-critical sets. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Arieh Iserles. A first course in the numerical analysis of differential equations. Cambridge university press, 2009.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvcx-noncomeee minimax optimization? arXiv preprint 192.001902.006// 2019.
Weiwei Kong and Renato DC Monteiro. An accelerated inexact proximal point method for solving nonconvex-concav min-max problems. SIAM Journal on Optimization, 31(4):2558-255 2585, 2021.
GM Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Carlton E Lemke and Joseph T Howson, Jr. Equilibrium points of bimatrix games. Journal of the Society for industrial and Applied Mathematies, 12(2):413 423, 1964.
Tengyuan Liang and James Stokes. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 905-915, 2019.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concal minimax problems. In International Conference on Machine Learning, pp. 6083-6093, PMLR, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Oren Mangoubi and Nisheeth Vishnoi. Greedy adversarial equilibrium: An efficient alternative to min-max optimization. In Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC), 2021.
Eric Mazumdar and Lillian J Ratliff. On the convergence of gradient- bastt learning in continuous games. arXiv preprint arXiv: (004 804.05464, 2018

---

Under review as a conference paper at ICLR 2023
Panayotis Mertikopoulos, Christos H. Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually converge? In International Conference on Machine Learning, pp. 3481-3490, 2018.
Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein. Unrolled generative adversarial networks. arXiv preprint arXiv: /61 16/100263, 2016.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. unified analysis of extra extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. arXiv preprint arXiv:1901.085// 2019.
Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash equilibria in sinconvex-concaat smooth min-max problems. SIAM Journal on Optimization, 31 (4):2508-2538, 2021.
Thomas Pethick, Puya Latafat, Panos Patrinos, Olivier Fercoq, and Volkan Cevher. Escaping limit cycles: Global convergence for constrained nonconvex-noncone minimax problems. In The Tenth International Conference Learning Representations, ICLR 2022, 2022.
L. D. Popov. A modification of the AtrowHHuwice, method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845-848, Nov 1980.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications machine learning. arXiv preprint arXiv:1810.0206/ 2018.
J Ben Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econo- metrica: Journal of the Econometric Society, pp. 520-534, 1965.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in
Machine Learning, 4(2):107-194, 2012. doi: 10. 10.1566/2200000011.
Shai Shalev-Shwartz and Shai Ben Devid. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
J Neumann. Zur theorie der gesellschaftssieee.. Maheemttische annalen, 100(1):295-320, 1928.
Eimaaouul-Vasilcioss MlttakisGGaarakoooie Lampros Flokas, and Georgios Piliouras. Poincaré recurrence, cycles and spurious equilibria in gradient-descent-aseee for non-convex non-concave zero-sum games. Advances in Neural Information Processing Systems, 32, 2019.
John von Neumann. Zur Theorie der Gesellschaftsspiele. In Math. Ann., 295-320, 1928.
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. International Conference on Learning Representations, 2019.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprint arXiv:1911.1066 2019.
12


Reviews:
[{"review_id": "eKe1NcGZXyU", "reviewer": "Reviewer_Ej7m", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes Stay-On-the-Ridge $(STON'R)$ algorithm, which according to the authors it is the first method that is guaranteed to converge to a local min-max equilibrium for smooth nonconvex-nonconcave objectives. The proposed method is a second-order algorithm that provably escapes limit cycles as long as it is initialized at an easy-to-find initial point. Finally, the algorithm is designed to satisfy a topological property that guarantees the avoidance of cycles and implies its convergence.", "summary_of_the_review": "The paper in its current format is very hard to read. \n\nI believe the approach and results are interesting however a more clear presentation will be needed for the results to be able to be understood and get appreciated by a broader audience. \n\nFor this reason, I gave a score of \"5: marginally below the acceptance threshold\" for this work.\n", "strength_and_weaknesses": "The paper proposes a novel idea for the convergence to a local min-max equilibrium for smooth nonconvex-nonconcave objectives. The fact, that the proposed method and the analysis are motivated by the topological nature of the problem positions this paper in a different category than other classical and recent works.  As the authors mentioned the method is not designed to decrease some potential function but is designed to satisfy a topological property that guarantees the avoidance of cycles and implies its convergence.\n\nHaving in mind the tight timeline for the submission of the reviews (less than 2 weeks to review 3-5 papers), I would be positively surprised if any of the reviewers were able to follow and understand the proof techniques of this work. The paper is heavily theoretical and the proof arguments are not standard.  \n\nMain Issue: Presentation\n\nAs it is now the paper gives the impression that it was rapidly cut before the submission to simply fit into 9 pages (looks more like a draft of a final paper). I understand that the authors try to fit the novel idea into the given ICLR space but in my opinion, this is an impossible task for such results. For having a proper presentation and allowing the reader to appreciate every aspect of this work I believe one needs much more space. \n\nSome suggestions for squeezing the results but keeping important parts in the main paper: \n\n1. I would suggest removing section 5.3 in the appendix and adding some experiments in the main paper as well as a conclusion.\n2. In part of the main contributions in section 1 a table with what are the existing results in terms of convergence guarantees and the main contribution will give a better idea to the reader of what is needed. A paragraph explaining what are the challenges of the new approach will be also needed there. \n\nQuestion: \n\nHow this method is related to the Hamiltonian gradient and consensus optimization methods proposed in Abernethy et al. (2019)? Why these second-order methods cannot be used in the setting under study?\n\nSome missing references from related work on last-iterate convergence:\n\n[1] E. Gorbunov, N. Loizou, and G. Gidel. Extragradient method: O(1/K) last-iterate convergence for\nmonotone variational inequalities and connections with cocoercivity. AISTATS 2022\n\n[2] Yang Cai, Argyris Oikonomou, Weiqiang Zheng\nFinite-Time Last-Iterate Convergence for Learning in Multi-Player Games, NeurIPS 2022", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MsYqIoXF7Z", "reviewer": "Reviewer_PZ8h", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "To the authors' knowledge, this work proposes the first algorithm that provably converges to a local min-max equilibrium for smooth nonconvex-nonconcave minimax optimization. ", "summary_of_the_review": "This paper is very well written, which studies the unsolved challenging problem of finding local minimax equilibrium of nonconvex-nonconcave minimax optimization, with highly novel algorithm. The convergence is proved in a novel topological way, and also well demonstrated by experiments. There are a few unclear points which I think are not hard to clarify. Therefore, I would like to see this paper accepted. ", "strength_and_weaknesses": "Pros: This work is highly novel in both algorithm and proof technique, as elaborated in **Novelty** below. The convergence is also well supported by both theorem and experiments. \n\nCons: A few points need to be clarified as listed in **Clarity** below. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AT7zemVaBV", "reviewer": "Reviewer_5vqs", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This submission proposes a new algorithm called the STay-ON-the-Ridge (STON'R) for converging to the local minimax of constrained nonconvex-nonconcave games. The problem is reformulated in terms of variational inequalities. The key idea is to find a set of points on which one can define a directed graph with in- and out-degree at most one, with one node being the sought equilibrium.", "summary_of_the_review": "The paper proposes contains many novel ideas. However, my concerns are that \n1. The presentation is messy and it is almost impossible to check the proofs. \n2. Stylistically speaking, I believe this is more of a TCS paper than an ML paper. The relevance to ML is not very clear.", "strength_and_weaknesses": "Strength:\n\n- The ideas are substantially new.\n\nWeaknesses: While I really appreciate the highly innovative algorithm and ideas, I feel like the paper, in its current state, is more of a draft than is ready to be published. I have three main concerns:\n\n1. The presentation, especially on the proof, is very messy and difficult to follow. Here are only a few examples:\n   - The argument for \"Assumption 1 is mild\" is very vague. For instance, can the authors explain why adding a periodic function wouldn't change the VI solutions? In its current form, the authors only gave an explanation to approximate stationary points but nothing on the boundary. Moreover, what is the basis for \"In higher dimensions we do not provide a formal argument for a reduction, although we conjecture that it is true.\"?\n   - The authors argued that Assumption 2 is mild since one can start in a smaller (random) subset of $[0,1]$. In this case, where do we initialize STON'R? Does this not destroy the pivot argument in the proof for Theorem 1? Moreover, the curve $C$ in Example 1 of Section C.2 is just a singleton $(1,0)$ so I don't really grasp its meaning.\n    - Why does Lemma 8 imply Lemma 3? In Definition 7, pivots include boundary satisfied points, whereas Lemma 8 only deals with the cardinality of 0-satisfied points.\n\n    This list can go on. Essentially, whenever I check for a rigorous statement, there is some ambiguity. I believe many of them can be easily fixed, but in its current form I find it almost impossible to verify the correctness of the paper. Since this paper is all about theory, I consider it a serious flaw.\n\n2. The relevance of the proposed algorithm to machine learning is unclear:\n    -  The authors claimed that the proposed algorithm is second-order, which is not really true. At best, it can be described as a **piecewise** second-order algorithm involving various breakpoints, but it is significantly more complicated than any bona fide second-order method. In any case, it is computationally much more demanding than existing second-order algorithms such as (Wang et al., 2019).\n    \n    - The claim that the authors have solved the open problem \"Is there an algorithm which is guaranteed to converge to a local min-max equilibrium in the nonconvex-nonconcave setting (Wang et al., 2019)?\" is an overstatement for me. Since the authors **changed** the problem formulation to constrained min-max problems, a simple grid search + Follow-the-Ridge of (Wang et al., 2019) would work; note that this naive algorithm is more practical than STON'R.\n\n        This is not intended to say that the contribution of the paper is trivial; it simply points out that the interest of the paper mainly lies in its theoretical insights, something that is not accessible from prior works. I therefore suggest the authors to rephrase their contribution.\n\n\n3. The argument seems to be highly specific for box constraints. For instance, how do I extend the algorithm to $\\ell_2$-balls?\n\nIn addition, there are some issues with the reduction to VIs in Section 2. For instance, a local **max-min** (instead of min-max) in the interior would verify the VI proposed at the bottom of page 3, contradicting the authors' claim that VIs are equivalent to local min-max. Can the authors clarify?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject