Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Suffices
Authors: Guillaume Wang
Lénaïc Chizat
Venue: NeurIPS 2023 poster (2023)
Keywords: Gradient methods
min-max optimization
spectral analysis
last-iterate convergence

Abstract: We study the convergence to local Nash equilibria of gradient methods for two-player zero-sum differentiable games.
It is well-known that, in the continuous-time setting, such dynamics converge locally when $S \succ 0$ and may diverge when $S=0$, where $S\succeq 0$ is the symmetric part of the Jacobian at equilibrium that accounts for the "potential" component of the game. We show that these dynamics also converge as soon as $S$ is nonzero (*partial curvature*) and the eigenvectors of the antisymmetric part $A$ are in general position with respect to the kernel of $S$.
We then study the convergence rate when $S \ll A$ and prove that it typically depends on the *average* of the eigenvalues of $S$, instead of the minimum as an analogy with minimization problems would suggest.
To illustrate our results, we consider the problem of computing mixed Nash equilibria of continuous games. We show that, thanks to partial curvature, conic particle methods -- which optimize over both weights and supports of the mixed strategies -- generically converge faster than fixed-support methods.
For min-max games, it is thus beneficial to add degrees of freedom "with curvature": this can be interpreted as yet another benefit of over-parameterization.

Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Suffices
Guillaume Wang
Lénaïc Chizat
Institute of Mathematics
Institute of Mathematics
Ecole polytechnique fédérale de Lausanne Station Z. CH-1015 Lausanne gui alliel wang@epfl ch
École polytechnique fédérale de Lausanne Station Z. Lausanne lenaic ch zat wat.eppl..ccm
Abstract
We study the convergence local Nash equilibria of gradient methods for two- player zero-sum differentiable games. is well-known that such dynamics converge locally when part of the Jacobian at equilibrium that accounts for the "potential" component of the game. show that these dynamics also converge as soon as S is nonzero (partial curvature) and the eigenvectors of the antisymmetric part A are in general position with respect to the kernel of S. We then study the convergence rates when S < A and prove that they typically depend on the average of the eigenvalues S. instead of the minimum as an analogy with minimization problems would suggest. To illustrate results, consider the problem of computing mixed Nash equilibria continuous games. We show that, thanks to partial curvature, conic particle methods which optimize over both weights and supports of the mixed strategies generically converge faster than fixed-support methods. For min-max games, is thus beneficial to add degrees of freedom "with curvature": this can be interpreted as yet another benefit of over-parameterization.
and may diverge when O, where $ ž 0 the symmetric
Introduction
Min-max optimization is notoriously subtler than minimization, even in convex-concave settings. While many of the proof techniques for minimization have natural equivalent in the min-max world, some common intuitions fail to transfer. The picture is clear for strongly convex-strongly concave (SC-SC) mix-max games: all the classical gradient methods converge exponentially (for small enough step-sizes) with worst-case convergence rates dependent on the strong convexity and strong concavity parameters Prr. ply- But, most famously perhaps, for bilinear min-max games the last iterate of simultaneous Gradient Rescent-Ascent (GDA) diverges, while the Proximal Point (PP) method converges, and alternating GDA and the continuous- time limit of all of these algorithms Gradient Flow (GF) exhibit cycling behavior.
Based on those two extreme cases, it still seems that part of our intuition from minimization, where the last-iterate convergence rate is indeed determined by the strong convexity parameter, is preserved. In this paper, we argue that this intuition in fact overly pessimistic, and that gradient methods behave in general more favorably in the min-max setting than in the minimization setting.
Let first look at basic example. Consider bilinear min-max game regularized by quadratic term only in one scalar variable:
min max T
2
wERd yERr
2
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

kt xf bg
x 0.01
0.04
R - 0.1
= 0.4
(a) Local convergence of the GF iterates for fixed draw of P R and various values of Only the final phase of the dynamics is shown, so here the iterates evolve along the "dominant" cigenspace of M (the subspace along which convergence the slowest).
1011
rin (observed)
10"
An
10-2
10-2
10
10
10a
3011
10
10
10-6
10-3
10-2
10"1
10c
10a
10
10-7
10
10-1
109
10
(b) Observed and predicted (īxr) normalized conver- gence rate r /1 of GDA with small step-size n) i.e., |0 + +111* strength a (the higher the faster). Fach color rep-
(c) Spectrum of the Jacobian M for a fixed draw of P Ie (green) and its approximation by Equa- tion (3.1) (gray)
@((1 r) vs. regularization
resents one draw of P E p2x2
Figure 1: Convergence of gradient methods on a random bilinear game regularized by 5æ for small step-sizes. The fact that ja,, and so r/n, scale linearly with (for small a)) explained by Prop. 3.1.
Here there is strong convexity in either player (so Prr Mly 0), yet observed on Fig. 1a, Fig. 1b, when P E d is random with independent standard normal entries, GDA (with a small step-size) typically converges an exponential rate that scales linearly with a.!
As we will see, this phenomenon is consequence of the existing theory for general smooth min-max games
min max f(z, y) ZEX" yER"
(1.1)
with a local Nash equilibrium (NE), or local saddle point, 2" (x", .y"). is well-known from the dynamical systems literature that GF converges locally to 2* if
V
R(A)= 0, with M XESp(M)
min
(z') p(n+m)x(++m) yof
the Jacobian of the skewed gradient field z", and where Sp(-) denotes the spectrum, i.e., the of cigenvalues. For our starting basic example, this quantity² can be visualized in Fig. Ic. Moreover, Aas also characterizes the convergence behavior of gradient methods in the leading order in the step-size they all converge to z with the rate nuM + O(7²), see the Appendix for review.?
While the condition jus is very general and tight, is not obvious how control interpret it. Our purpose with this paper is to explore what this condition entails and to emphasize some of its surprising consequences.
Julia code the numerical experiments available at https: /ttpttttttb///..///////.....b... wwm/ 11aumew16
local _owccc_cccee____ee_ minmax.
In numerical analysis and stability theory, the quantity -a is known the spectral abscissa of -M. "More precisely, gradient methods converge locally (for small enough step-sizes) if minxesp(Mr) R(AA) and only if minxxsp(MM)) (0) R{() 2 0. Throughout this paper we will assume for simplicity M invertible so that those quantities are equal.

---

The rest of the paper is organized as follows. In Sec. 2 we show that, generically, P. > 0 as long as the problem has partial curvature, i.c the diagonal blocks of M are non-zero. In See. 3, we study more precisely the case of games where the "interaction" component dominates the "potential" component, i.e., when f=")( V (2²)) < V fz²). For such games, in a certain random setting, we show that P.M scales as the average of the eigenvalues of the potential part, instead of the minimum as an analogy with minimization problems would suggest. In Sec. 4 we consider the computation of mixed Nash equilibria of continuous games using particle methods, setting where the convergence under partial curvature has a striking consequence. By optimizing over both the weights and supports of the mixed strategies, than fixed-support methods, even when the latter are using the optimal supports.
obtains dynamics that generically converge faster
For ease of exposition. in most of the paper we focus on the local convergence of GF. We discuss the convergence of discrete time algorithms in Sec. 3.2.
1.1 Related work
Throughout this paper, by "convergence" mean convergence of the last iterate (local) NE, while a different line work also considers convergence of the averaged iterate [Nem04], and another considers convergence
any critical point [ALW21]. Also to prevent possible confusion, let us mention a related but distinct line of work [DH19; Doa22] that considers using different step-sizes to update the x and the y variables. The resulting po-timmecclle dynamics can be analyzed globally assuming a min-max analog of the Polyak-Lojasiewice inequality, using quite different considerations than the ones developed in this paper.
Analysis of GDA and PP for SC-SC, bilinear convex-SC games. The fact that PP converges for SC-SC and bilinear min-max games is well-established since at least [Roc76]; for a modern reformulation, see e.g. [MOP20]. The convergence of simultaneous GDA for SC-SC games and its divergence for bilinear games is also a classical fact, see e.g. [LS19; Lu22]. The cycling behavior of alternating GDA for bilinear games is proved in [BGP20, Theorem 4).
As shown more recently in [NK17, Appendix G] and [ZWLG22, Theorem 6], convexity æ, strong concavity in y and non-degeneracy of the interaction component are in fact sufficient to ensure P. > 0, and so local convergence of GDA. The setting of the former work corresponds to V2 f22" O, - -V f=*)
0 and V2 f=*) full-row-rank, extended in the latter work to V (=*) 2 0. Those two works also provide bounds on pas for those specific cases in terms of the least cigenvalues of - f and of (=") 2 T
Spectral analysis- convergence analyses. Our approach to analyzing min-max algorithms V (z) for
is to directly study the properties of the update operator (c.g.. of T(2) = 2 yJ
simultaneous GDA). Specifically, by a classical result discrete-time dynamical systems, the local exponential convergence is characterized by the spectral radius that operator's Jacobian. This approach is used for example in [Gid+19] to analyze the local convergence behavior of alternating GDA with negative momentum, and in [AMLG20] to derive tight convergence bounds dependent explicitly on 1) and Sp(M) for simultaneous GDA and multi-step Extra-Gradient.
Average-case analysis of the (local) convergence rate. In [PS20; DPS21J, the authors analyze the convergence of gradient methods for affine operator problems i.e., for finding such that ( - =²) = 0 when M is random normal matrix with a known spectral distribution. They derive average-case optimal methods for this setting. Our analysis in Sec. also has an average-case flavor, but random model is different:
assume that the symmetric S and antisymmetric parts A of M are independent and that S & A. In particular we do not require M to normal (i.c., S and A do not commute a priori, which is the typical case in min-max optimization).
Hypocoercivity. In the context of partial differential equations (PDEs), the phenomenon that a linear PDE 0,u, = - Lu, may exhibit linear convergence to even when the generator not coercive, called hypocoercivity and is studied in detail in [Vi109]. This is precisely the ciiniteedimensionn analog of the phenomenon studied in the present paper: still denoting by S, A the symmetric resp. antisymmetric parts of M, cocrcivity of L corresponds to S > 0, while hypocoercivity corresponds to
3

---

which is AM > O. Specifically, [Vi109] shows how to construct Lyapunov functions to establish hypocoercivity and convergence rates of certain PDEs, by exploiting properties of the iterated commutators of S and A. By contrast our focus is on the finieeddimensionl case, where it is easier and more natural to directly study the spectrum of M.
1.2 Notation
For any matrix T E Rddd or Cdxd, denote by Sp(T) C C its spectrum, i.e., the set its eigenvalues, and by p(T) maX) X its spectral radius. Recall that the spectral radius distinct from the operator norm, which is the largest singular value, although they coincide for Hermitian matrices. Denote eigenspaces (T) = (= C"; T= X=} and let (Tg UxeSp(r) Ex(T) the set all (complex) eigenvectors. ||-Il denotes Euclidean or Hermitian norm. For a collection of square matrices (resp, scalars) (C*)a, Diag((Cx.) denotes the (block-)diagonal matrix with blocks (resp. coefficients) (C*)
Characterization of local convergence
Consider the general smooth min-max game of Equation (1.1) and assume M is invertible. We decompose M into its symmetric and antisymmetric parts as
M
V f
(x*) {
Q PT
P
$ Q
0 R
A
0 PT
R
0
24
By the second-order optimality condition the definition of NE, Q = and R 2
Following [Let+19], S and A can be thought of intuitively as the "potential" resp. "interaction" (or Hamiltonian) components of the two-player zero-sum game (1.1). Indeed, consider the quadratic
game mingER maXyER"
x
V
2 -Q= 2/ Ry x x
PTyyyy Py
essentially sufficient to understand the local behavior of GF for (1.1) around =". Then we can interpret the terms in and R as quadratic potentials to be optimized independently by each player, with the bilinear term in P capturing all of the interaction between the players.
Partial curvature generically suffices. Let us recall that j.M minxeSp(M) R(AA) governs the local convergence GF around the local NE 2* It is a general fact that this quantity is nonnegative (the proof is included below). In the following theorem, for it to be positive, in terms of geometric conditions on Q, and P.
give necessary and sufficient conditions
Theorem 2.1. The following conditions are equivalent:
(1) PM > O.
(ii) Eigvecs(A) n Ker S = (0}-
(ii) For any eigenvector of PP (i.e., left-singular vector of P), æ o Ker or PT & Ker R.
(iv) For any eigenvector of PT P (i.e., right-singular vector of P), Py & Ker Qr & Ker R.
As consequence of Thm. 2.1, the condition P.M O holds generically in the following sense: for any fixed S & O, the set of matrices P such that f. > 0 is dense and open in Raxm, In particular, this property holds with probability 1 if P is drawn from an absolutely continuous distribution and is independent from Q and It, as in the experiment of Fig. I.
Proof. Let À Sp(M) and = E Cn-m non-zero such that Mz (S + A)= Az. Since S and A are real and symmetric resp. antisymmetric,
Tz= T
Sz = (xT) T = =zTSz, so z S2 E R
and 2 T A= (=T Az)T - Az, so _ Az E iR.
So by taking the real part in Σ T A) > ||211
R(A) ||2|| = I Sz R(2) SR(2) + 3(x) S3(x) >

---

since S = Dia O. This shows that P. 2 0.
Now let us show the equivalence of the conditions.
(ii) (i): By contraposition, suppose there exists À E Sp(M) with R(A) = O, and let a non-zero such that Mz = λz. Then = S= = R(A) |= 0, so = E Ker S. So Mz = Az = λz, and 2 (Ex Ker 5) \ {0].
(1) (ii): By contraposition, suppose there exists X E Sp(A) and non-zero Ex(4) Ker S. Since A is antisymmetric, then (()A) = O. On the other hand, Mz (S + A)z = Az = Az, i.e., Sp(M). So j.M < R(A) = 0.
i1 (iii), (iv): By contraposition, suppose there exists an eigenvector x PPT such that æ E Ker Q and
Pd Ker R. and denote a E R such that PP o²x (since PPT ; 0). Then
ia
Q P
P
ia x P
o²x io PT
ia
M
R
io
PT
and so -io Sp(M). This shows (i)
- (iii), and (i)
(iv) follows analogously.
(iii), (iv) (ii):
By contraposition, suppose there exists À io Sp(A) and non-zero (5, Ex n Ker S. Expanding the blocks in Az = Xz,
Py io P
and P PPy=o'y PP r 0²r.
x - ioy
Moreover, this implies that x = y * O. So is eigenvector of PP and, since Sa 0, x Ker Q and P x -ioy Ker R, which contradicts (ūii). Likewise, y is an eigenvector P P and y E Ker R and Py ioæ Ker Q, which contradicts (iv).
y= 0, and since = * O, then both x * 0 and
Geometric interpretation using real vectors. We draw the attention of the reader to the fact that (ii) involves complex eigenvectors. For rephrasing in terms of real objects, note that if
E (A) with E R. then A (8(2) 3(2)] 19(2)
3(²)
[
0 o
geometrically, Fio (A)
span(R(2), 3(z)) is "rotation plane" of the GF for the bilinear game min max, T: Py, in the sense that the projection of GF on Fir (4) is a circular motion with constant speed a. Condition (ii) eigenspace (S) of $ (for l > 0) that is not orthogonal to it. This causes the GF for min, max, 1 Qz Jy" Ry + x Py projected on Fir (A) to spiral down to 0 instead of cycling around it.
expresses that for each such (A),, there exists
One may naturally wonder whether notion of non-orthogonality between the potential (S) and interaction components (A) can be used to bound the convergence quantitatively; this is developed in the next section in the particular case S < A.
3 Convergence rate when interaction dominates (S < A)
Let us now discuss the case of games with a small symmetric part, that is, whose Jacobian at optimum Ma A + aS for some symmetric
Q
0
0 P
antisymmetric A -PT 0
and some
0
R
small > 0. In this section we assume = (the general case is technically more challenging as Prop. 3.1 requires have distinct eigenvalues, which requires |n - ml| S 1).
3.1 Convergence rate of Gradient Flow
As discussed previously, the normalized local exponential convergence rate r/1 of gradient methods the asymptotic regime n - - or equivalently, the convergence rate GF for a game with Jacobian at optimum M,, is equal to jMM. We can estimate this quantity using the standard formula for the asymptotic expansion of the eigenvalues of perturbed matrix, which takes an interesting form in our context.
5

---

Tr(S) Note that [ which always lies in the interval [1, v 2n], is a measure of the effective sparsity of the spectrum of S (larger meaning less sparse), so the condition Tr(S) 2 2/logm + c) means the spectrum is well spread-out. So the proposition shows that the exponential convergence rate Proposition 3.1. Suppose that P is full- and has distinct singular values, and let P = UEVT Ej=1 ,u } be its singular value decomposition. Then it holds
1 a
min " Qu, + +2 Ro,) + O(a"). P.a 2 18i5
This expansion explains in particular why the normalized convergence rate r/n ~ AMM is approx- imately proportional to in Fig. 1. Interestingly, the error term is O(a"), which suggests that the approximation can be reasonably accurate even for quite large values a, as illustrated in Fig. Ic.
Proof. Here Mo = A has distinct eigenvalues {isoz, E (-1,1), S S sn). with unit-norm -isus/v
eigenvectors A isu; //2 iso
By the calculation of the eigenvalue deriva- tives from [Tao08], we obtain the following expansion for Sp(M,):
/ 1/2
0//
Sp(Ma) = iso iso,tza (ujQu, Quy + tu Ro,) a
Σ
iso; is'o, (ss' (s''uQQu, + 0J Ru,)
(M
+ + SE ( (3.1)
Now the zeroth- and second-order terms are all in iR, hence the announced expansion for AAM..
Estimate of the leading term under a probabilistic model. Assuming the singular vectors (u,,... Un)) (Ei,..., Un) of P distributed uniformly random which is the case for example P has i.i.d. Gaussian entries by rotational invariance* the leading term in the expansion of juM, can be estimated expectation as follows. The proof is placed in the Appendix, where we also include high-probabiliig version of the estimate.
Proposition 3.2. Suppose Q, R are fixed and U, V are independently distributed uniformly on the of n X n orthonormal matrices. Then
Tr(S))
(1-2115)) 1|51| Vlogn| Tr(S)
Tr(S)
S
min 15t5n
1 Quy + +1, Rv;
s n
n
where 11-11 denotes the Frobenius norm. particular, provided that
Tr(S) [
2 2 2/ogn(( + c) for
some fixed > O, we have E |minisisn uz Qu, + +0 Rvy] x Tr(S)
as n + cc.
[
depends the average of the eigenvalues of S, when aS < AA and the spectrum of $ is well spread-out. This fact should be contrasted with the case of minimization, where the convergence rate scales the minimum eigenvalue of the Hessian.
Interestingly, when the spectrum of is sparse, the typical behavior of the leading term in the expansion of jM,, min; u, Qu, v, Rey, is quite different, In this case, that quantity depends on the geometric mean of the non-zero eigenvalues of S, rather than the arithmetic mean, as formalized in the following proposition. The proof is placed in the Appendix, along with high-probability version of the estimate.
Proposition 3.3. Suppose Q, R are fixed and U, are independently distributed uniformly on the sei of n x n orthonormal matrices. Lei 81 2 2 > 0 8r+1 ... 82n. the eigenvalues of S.
'Ir P = T has i...d. Gaussian entries, then P has the same law as U PV, for any U, V E On the set of n x n orthonormal matrices. So (U, V) has the same law as TU, V VV). This shows that V) is distributed according to the Haar measure on the product group O, x O.. that is. U and V are independently distributed uniformly on O,,.

---

Table 1: Expansions p (z*)) in and 7) for classical gradient methods
Algorithm
T(2)
VT(=*)
(VVT(=
maxis2n
+ +1fa²)
Sim-GDA
ng(=))
1 n,M
200
W
Sw]
+ 1/
Alt-GDA
sec text
1 17(1 -2AAM + 0
2007
w
Swi
+ +(1)))
EG
7g(2 19(22)
I - 77 - -MM)M
1 2am
w
Swy
- 08 +07+0
Then
min 3 Quy + 03 Rug 55n
2 max sc(l.
e n2 -
1 1
31
[8]
LIE
In particular, E minjsa u/ Qu, + vz Rui] 2 n ? when n - oc and r and s E R' are fixed.
Numerically, the quantity minjgn u Qu, + v Ru, indeed scales as n - under the conditions of the proposition, suggesting that our lower estimate could be tight.
3.2 Convergence rate of discrete-time algorithms
Prop. 3.1 gave an expansion of the normalized convergence rate r /n of gradient methods (for a game with Jacobian at optimum Ma), non-asymptotically in and in the asymptotic limit 17 - 0. In this subsection, we give expansions of the convergence rate r that are non-asymptotic in a and 77.
The algorithms we will consider can written the form 2++1 = T(2*) with the update oper- ator T dependent only on ff and step-size 7). and satisfying 2" T(2*). ). It is that local convergence of T and p(-) denotes spectral radius. Namely, if p(VT(=*)) < then the iterates converge lo- cally with || - 2" O ((p(VT(z*)) + +))),, with > 0 arbitrarily small constant [Ber97, Proposition 4.4.1].
such methods is determined by pl ((TT(= where VT is the Jacobian
In Table 1 we give expansion for p VT(=")) for three classical gradient methods: simultaneous GDA SDm), alternating GDA (Alt-GDA) and Extra-Gradien (EG). Let us clarify immediately that throughout this paper, statements made about "GDA" without further specification apply to both
V -VV
Sim-GDA and Alt-GDA. In the second column we denoted by g(z) =
(z) the skewed gradient field of the game, and in the third column wrote M instead of M, for concision. In
the fourth column, =io, denotes the eigenvalues of A assumed distinct and Wy are the associated eigenvectors equivalently, the singular value decomposition of P is P = Σド= "y and for each j S n, W. Sw; W Sucjan 1/ [u] Qu, + +0² Rwy). We refer the Appendix for the derivation of this table and for explicit bounds the "O(-)" terms.
Informally, as one can directly see from the fourth column, Sim-GDA requires a very small step-size for the first term in 17 to overcome the terms +7)²03. while for EG those terms actually appear with favorable sign, and Alt-GDA neither benefits nor suffers from those terms. We also see that Alt-GDA quite faithful to GF, in that their normalized convergence rates coincide up to terms of order 773 + All these insights are in line with common intuition in the min-max optimization literature [BGP20; Lu22], well as with our numerical experiments for the next section, Fig. 2.
symmetrized formulation of Alt-GDA. In order to derive the rate for AltGDA, we used the following symmetrized formulation of it: we let (x* 12 E Rdd Rd and
Vkk N, Vk N
xb+1 xx V [z* 1////) ghtl= = nh + v ff(( )
and V V
kt
k42
,+1//==
That is, gets updated with the gradient rule integer time-steps, y at half-integer time-steps, and we define x², y at mon-oonndnee non-updating time-steps as the average of the preceding and following updating 22 A
time-steps. Assuming 17
22 fl we show in the Appendix that *41 is indeed
7

---

entirely determined by 2" = (x ) for each &o E N, and that the associated update operator T satisfies
T T(2) = === A(z)g(z) + 0 [[{(=)])) where A(z) Vg(2) Vg(z)
For comparison, the usual formulation of Alt-GDA considers as the iterates (# 8/*)) (a* .y 1//)) We emphasize that (ā*, 3))) and (x*,y" have the same convergence rate they converge exponen- tially, as one can check directly from the definition.
4 Illustration: sparse mixed Nash equilibria of continuous games
In this section we apply the above considerations to a particular class of min-max problems, which is of its interest in game theory. Namely we consider the classical problem of finding the mixed Nash equilibria (MNE) two-player zero-sum games, that is, given strategy spaces X, y and a IR, solving the min-max problem
payoff function f X min (EP())
{F(u,)) v) Be v)],
Here P(2') denotes the space of probability measures representing mixed strategies over X. Let us focus on cases where and y are continuous sets, say, X' x y =T=T' the one-dimensional Euclidean torus,' and f TT T + is smooth. The above min-max problem is then infinite- dimensional, and algorithms to solve it explicitly must be based on reparameterized formulations. More specifically, suppose that the MNE (μ* v²) is unique and "sparse", i.e., has finite supports: supp(æ") = {-7, < < supp(r")))) = {u) S J < M) (this is the case for example if f is sum of separable functions [SOP08]).
In this setting there are two natural reparameterizations and associated algorithms:
1. If the optimal support points (.ī),, {uj), known, then may reparameterize by # = Σm= ard2y, y = ΣM رyōر and optimize over the ay The problem reduces to constrained bilinear game
M ΣΣ orbs f(z) a Pb
min max AEAN BEAM
Fi(a,b)
where AN denotes the standard simplex. classical approach is then to apply Mirror Prox (MP) with entropy link function [Nem04] (MP is the Bregman Bregman-geometry analog of EG).
2. If only the number of optimal support points is known, then may reparameterize by μ Σm= ardz,, v Σx= byōys and optimize over both the weights (ar, by) and the support points (01, The problem reduces to
M
F2(a,z,b,1))
Σ arbs Ren. 1=1==
min (o.)) (b.)) (TI) (TI)a
max
A possible approach is to iteratively update (simultaneously) the b using MP steps with step-size 77 and the x, y using EG steps with step-size 7y7, for some parameter y >> 0. This algorithm is called Conic Particle Mirror Prox in [WC22], but for concision we will refer to it simply "EG" in this section. Note that the main challenge in that reference is to deal with the case where N and M unknown, but here we assume they are known for the sake of simplicity.
In Fig. 2, we show the dependency on y and y of the local convergence rate of MP and EG, as well as that of the analogs of Sim-GDA and Alt-GDA and GF for the problem min max(t.g) (2 xr, 6, y) in order to illustrate the insights from Sec. 3.2. We used a randomly generated payoff function f. and the convergence is measured by the iterates' la distance the solution; see the Appendix for details.
'The choice of X y - T is made for simplicity of exposition. The discussion below extends straightfor- wardly to toruses of any dimension, and could be extended to X, y Riemannian manifolds without boundaries at the cost of more technical notation.
8

---

10a2
10-3
Convergerce rate
10
Converpence
10-1
000000000900 0000009899009000000 000000000000000
Sim-GDA
Sim-GDA
10-4
EG
Alr-GDA
(y
10a
10-3
GF (theory)
GF (theory)
10
10
10
10
10
10"
(a) Convergence rate r vs. y (fixed 1j = 10
(b) Convergence rate vs. 17 (fixed y = 10 10
for various conic particle methods using step-size v for the weights (a, b) and 7 for the positions (Ir, y) and for fixed random draw of f. (left) Fixing 17 = 10-2 we observe rate for GF (we plot 1) fi-) scaling as y² as predicted in Prop. 4.1. Interestingly, Alt-GDA has exactly the same behavior, while the behavior of Sim-GDA and EG differ for small % due to the corrective terms shown in Table 1. (right) Fixing ? 10 we observe a rate scaling as 7 for EG and its variants, and as 17 for MP; the convergence of EG is mostly faster than MP.
Figure 2: Observed local convergence rates r (i.e., - - ((1-
MP (the algorithm based on the reparameterization Fi) converges the MNE for any small enough with an exponential rate at least proportional to n/² [WLZL21], and this scaling is tight numerically (green dots Fig. 2b). Its explicit variant (Mirror Descent-Ascent) and its continuous- time flow are known to diverge for any [BP18] [MPP18].
EG is known to converge locally to the MNE for any small enough (and any Y 0) with an exponential rate at least proportional to 17², despite the non-convexity of F2, under some non- degeneracy assumptions [WC22, Sec. 3. However numerically the convergence rate of EG typically scales as not v/2 (orange dots in Fig. 2b) a fact which we will explain below. The explicit variant of EG and its continuous-time flow have not previously been analyzed; the discussion below will give a characterization of when they converge locally.
Note that, at least for the particular f and used for Fig. 2b, EG converges locally faster than MP for the same (in number iterations, the per- ver-iteration costs differing only by a constant factor), even though the former does not use the knowledge of the {a7]ı, {uī } In other words, when the optimal support points are known, is beneficial to use the overparameterized formulation F2 where also vary the support points.
Overparameterization induces partial curvature. Let us inspect the "Jacobians" optimum for the two dynamics, MP vs. EG with parameter y. Due to the simplex constraints and the non- -ucllden nature the updates for a, b, the relevant matrices are MMP and M,, defined below, in the sense that the exponential convergence rate of each algorithm part + O(7²) (see the Appendix). Namely, omitting half of the antisymmetric off-diagonals for readability,
0 (+)T
D.D,,,D.II, 0
MMP =
where D, Diag( Va*) (square roots being taken component-wise) and 1I, E (N)-N is any matrix such that 11,11 IN-1 and 11 11, = IN Va and likewise for Do and II e (M (M)M)) and for EG,
O
D. (,,
V7 D. PI PID,
0
"Dig 02 pb*) (b))
Da xy
My
(+)
0
0
> Diag( (22 PTa') a*))
where [0,Pl,, = (x) v.), and likewise for P, 02 P. 0 P. P.
For MP, it is clear that the equivalent conditions of Thm. 2.1 are violated for any payoff function f. and so J.MP = O. For FG, depending on and 7, they may or may not violated. For all of the random payoff functions we considered in our experiments, we observed that ju,, > 0, suggesting

---

that the conditions hold generically. They are violated for certain f's however, as shown in the Appendix, so that the scaling 17 of the convergence rate proved in [WC22] is tight in the worst case.
show in the next proposition, assuming that the blocks of My in general position, we expect aM, to scale 7², which is indeed observed in the numerical experiment reported in Fig. 2a. The proof. placed in the Appendix, relies on the same tools as Prop. 3.1, that is, on the asymptotic expansions of the eigenvalues of perturbed matrices.
More precisely
Proposition 4.1. Let S2 symmetric and Ag, A1, A2 antisymmetric real matrices of the form
0
0
0
0
0
0
0
S2
Ao =
A1
A2
0
0
0
and M, = 7S2 + Ao + V A for all y > O. Then jum., = O as 7 -700
Conclusion
We have investigated the local convergence of gradient methods for min-max games and found that they converge generically under partial curvature. In more specific settings, we have obtained quantitative estimates of the local convergence rate which exhibit the average of the eigenvalues of S as the driving quantity for typical problems. For the computation of mixed Nash equilibria of continuous games, this leads behavior of conic particle gradient methods that is more favorable than that described by the worst-case bounds.
More generally, our analysis leads to the following insights: (i) worst-case bounds might be looser min-max optimization (compared to minimization) as they fail to capture the interplay between interaction and potential parts; (ii) the addition of new degrees of freedom with curvature typically accelerates the local convergence, as we illustrated in Sec. 4.
We note that the phenomenon described in this paper is fundamentally consequence of the fact that the skewed gradient field's Jacobian at optimum has a positive-semidefini symmetric part. This property is satisfied at local Nash equilibria of min-max games, i.e., of two-player zero-sum differentiable games, but is not true for general differentiable games.
References
[ALW21]
Jacob Abernethy, Kevin A Lai, and Andre Wibisono. "Last-iterate convergence rates for min-max opumization: Convergence of hamiltonian gradient descent and consensus optimization". In: Algorithmic Learning Theory. PMLR. 2021, pp. 3-47.
[AW20]
Ehsan Amid and Manfred KK Warmuth. "Reparameterizing mirror descent as gradient descent".. In: Advances in Neural Information Processing Systems 33 (2020), pp. 8430- 8439.
[AMLG20] Waiss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. "A tight and unified analysis of gradient-based methods for whole spectrum of differentiable games". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2020, pp. 2863-2873.
[BGP20] James Bailey, Gauthier Gidel, and Georgios Piliouras. "Finite regret and cycles with fixed step-size via alternating gradient descent-ascent". In: Conference on Learning Theory. PMLR. 2020, pp. 391-407.
[BP18)
James P Bailey and Georgios Piliouras. "Multiplicative weights update in zero-sum games" In: Proceedings of the 2018 ACM Conference Economics and Computation.
2018, pp. 321-338.
[Ber97]
Dimitri P Bertsekas. "Nonlinear programming". In: Journal of the Operational Re- search Society 48.3 (1997), pp. 334-334.
[Doa22]
Thinh Doan. "Convergence rates of pro-time-scale gradient descent-ascent dynamics for solving nonconvex min-max problems". In: Learning for Dynamics and Control Conference. PMLR. 2022, pp. 192-206.
10

---

[DPS21]
Carles Domingo-Enrin Enrsch, Fabian Pedregosa, and Damien Scieur. " "Average-case Ac- celeration for Bilinear Games and Normal Matrices", In: International Conference on Learning Representations. 2021.
[DH19]
Simon S Du and Wei Hu. "Linear convergence of the primal-dual gradient method for convex-conead saddle point problems without strong convexity". . In: The 22nd Inter- national Conference on Artificial Intelligence and Statistics. PMLR. 2019, pp. 196- 205.
[Gid+19]
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang. Simon Lacoste-Julies and Ioannis Mitliagkas. "Negative momentum for improved game dynamics". _ In: The 22nd International Conference on Artificial Intelligence and Statistics. PMLR. 2019, pp. 1802-1811.
[GLWM22] Benjamin Grimmer, Haihao Lu, Pratik Worah, and Vahab Mirrokni. "Limiting behav- iors of nonoonccvee minimax optimization via continuous-time systems". In: International Conference on Algorithmic Learning Theory. PMLR. 2022, pp. 465-487.
[GWS21] Suriya Gunasekar, Blake Woodworth, and Nathan Srebro. "Mirrorless mirror descent: A natural derivation of mirror descent". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2021, pp. 2305-2313.
[LM00]
Beatrice Laurent and Pascal Massart. "Adaptive estimation of a quadratic functional by model selection". In: Annals of Statistics (2000), pp. 1302-1338.
[Let+19]
Alistair Letcher, David Balduzzi, Sébastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. "Differentiable game mechanics". In: The Journal of Machine Learning Research 20.1 (2019), pp. 3032-3071.
[LS119] Tengyuan Liang and James Stokes. "Interaction matters: A note non-asymptotic local convergence of generative adversarial networks". In: The 22nd International Conference on Artificial Intelligence and Statistics. PMLR. 2019, pp. 907-915.
[Lu22]
Haihao Lu. "An rresouuiin ODE framework for understanding discrete-time algorithms and applications to the linear convergence of minimax problems". In: Mathematical Programming 194.1 (2022), pp. 1061-1112.
[MPPI8]
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. "Cycles in adversarial regularized learning". . In: Proceedings of the twenty-ninth annual ACM- SIAM symposium on discrete algorithms. SIAM. 2018, pp. 2703-2717.
[MOP20]
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. "A unified analysis of extra- gradient and optimistic gradient methods for saddle point problems: Proximal point approach". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2020, pp. 1497-1507.
[NK17]
Vaishnavh Nagarajan and Zico Kolter. "Gradient descent GAN optimization is locally stable". In: Advances in neural information processing systems 30 (2017).
[Nem04]
Arkadi Nemirovski. "Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems". In: SIAM Journal on Optimization 15.1 (2004), pp. 229-251. Fabian Pedregosa and Damien Scieur. "Acceleration through spectral density estima- tion". In: International Conference on Machine Learning. PMLR. 2020, pp. 7553- 7562.
[PS20]
[Per13]
Lawrence Perko. Differential equations and dynamical systems. Vol. Springer Sci- ence & Business Media, 2013.
[PP+08]
Kaare Brandt Petersen, Michael Syskind Pedersen, et al. "The matrix cookbook". In: Technical University of Denmark 7.15 (2008), p. 510.
[Roc76]
R Tyrrell Rockafellar. "Monotone operators and the proximal point algorithm". In: SIAM journal on control and optimization 14.5 (1976), pp. 877-898.
[SOPO8]
Noah Stein, Asuman Ozdaglar, and Pablo A Parrilo, "Separable and low-rank continuous games". In: International Journal of Game Theory 37.4 (2008), pp. 475- 504.
[Tao08]
Terence Tao. When are eigenvalues stable, Oct. 28, 2008 URL: https : /// terrytao. wordpress, com/ 2008 10 28/ when are eigenvalues stable.
11

---

[VTM07]
Nico Van der Aa, H Ter Morsche, and R Mattheij. "Computation of eigenvalue and eigenvector derivatives for general complex-valuee eigensystem" In: The electronic journal of linear algebra 16 (2007), pp. 300-314.
[Vi109]
Cédric Villani. Hypocoercivity. Vol. 202. 950. American Mathematical Society, 2009.
[Wai19]
Martin J Wainwright. High-dimensionall statistics: A non-asymptotic viewpoint. viewpinn. Vol. 48. Cambridge university press, 2019.
[WC22]
Guillaume Wang and Lénaic Chizat. "An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games". In: arXiv preprint arXiv:2211. 000::2211.112800 1.011000000011 (2022).
[WIZL21] Chen- Yu Wei, Chung-Wai Lee, Mengxiao Zhang, and Haipeng Luo. "Linear Last- iterate Convergence in Constrained Saddle-point Optimization". In: International Conference on Learning Representations. 2021.
[ZWLG22]
Guodong Zhang, Yuanhao Wang. Laurent Lessard, and Roger B Grosse. "Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization". In: International Conference on Artificial Intellignnce and Statistics. PMLR. 2022,
Pp. 7659-7679.
12


Reviews:
[{"review_id": "fw0l4dfTlL", "reviewer": "Reviewer_KFbS", "summary": "This research investigates the local convergence properties of gradient dynamics in two-player zero-sum differentiable games towards Nash equilibria. Existing knowledge suggests that such dynamics converge locally when the symmetric part of the Jacobian at equilibrium, denoted by S, is positive definite (S ≻ 0), and divergence is likely when S equals zero (S = 0). The symmetric part S accounts for the potential function of the game.\n\nThe authors advance this understanding by demonstrating that gradient dynamics can also exhibit local convergence as soon as S is non-zero but fails to be strictly positive definite, which is referred to as partial curvature. This convergence is shown to occur provided the eigenvectors of the antisymmetric component of the Jacobian, denoted as A, occupy a general position relative to the nullspace of S. This result elucidates conditions under which convergence is guaranteed, thereby broadening the scenarios where gradient dynamics can be effectively employed in such games.\n\nThe paper further explores the rates of convergence in the case where the antisymmetric part dominates the symmetric part, represented mathematically as S ≪ A. It is proven that the convergence rates typically depend on the arithmetic mean of the eigenvalues of S, in contrast to the minimization problems analogy that suggests the dependence of rates on the smallest eigenvalue. This counterintuitive finding contributes to a more nuanced understanding of the behavior of gradient dynamics in these games.\n\nTo illustrate the theoretical findings, the problem of computing mixed Nash equilibria in continuous games is considered. The authors reveal that due to the effect of partial curvature, conic particle methods, which concurrently optimize over the weights and supports of mixed strategies, converge generically faster than their fixed-support counterparts. In the context of min-max games, this implies a strategic benefit in adding degrees of freedom exhibiting curvature, presenting yet another advantage of over-parameterization. This practical manifestation of their theoretical insights underscores the significant role of over-parameterization in enhancing the efficiency of Nash equilibria computations in such games.", "questions": "Please answer my concerns at Weaknesses' section", "limitations": "n/a", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The paper impressively contributes a significant degree of originality by extending the traditional notions of regularization and partial curvature in a fresh manner to elucidate the convergence of Gradient Descent Ascent (GDA) to a Nash Equilibrium in continuous differentiable games. The authors’ approach not only offers an intriguing new perspective but also opens up a novel theoretical pathway that future work may explore further. \n\nQuality-wise, the paper exhibits a meticulous level of mathematical rigor in establishing the convergence conditions and rates. The well-structured proofs and clear theoretical arguments bolster the reliability of the results, reinforcing the significance of the paper’s main findings. \n\nIn terms of clarity, the authors deserve commendation for maintaining a high standard of exposition. They have done an excellent job in the paper's organization and presentation of complex concepts in a manner that is accessible and engaging. The lucid language, combined with logically organized sections, facilitates an intuitive understanding of the problem setup, the methodological developments, and the theoretical results.\n\nRegarding significance, the findings of this paper hold substantial implications for the broader research community focused on game theory and optimization. By unveiling the factors that determine the local convergence of GDA in two-player zero-sum differentiable games, the paper paves the way for the development of more efficient and reliable methods for finding Nash equilibria. Moreover, the practical relevance of these findings is underscored by the authors' demonstration of the benefits of over-parameterization in mixed Nash equilibria computations. \n\nOverall, the paper stands out for its innovative approach, rigorous methodology, clear exposition, and high impact on the field of continuous differentiable games. It makes a valuable addition to the literature by advancing our understanding of the roles of partial curvature and regularization in the context of gradient dynamics convergence to Nash equilibria.", "weaknesses": "Certainly, here is the markdown version:\n\n1. **Clarity on Mirror Prox (MP), Exponential Gradient (EG) Methods, and Overparametrization:** The paper could enhance its clarity by offering more detailed explanations and motivations for the application of Mirror Prox and Exponential Gradient methods, particularly in the context of overparametrization. Clear elaboration on how overparametrization interacts with these methods and contributes to convergence could reinforce the paper's argument. \n\n2. **Applicability to Non-Square Games:** It would be beneficial for the authors to clarify if their results extend to non-square games, i.e., when the dimensions of the two players' strategies are different ($n \\neq m$). Currently, the paper does not explicitly address this case, which leaves a gap in the comprehension of the scope of the presented results.\n\n3. **Practical Examples of Slight Curvature Setting:** The inclusion of practical examples or real-world scenarios where the slight curvature condition holds would significantly enhance the paper's impact. Such examples can illustrate the practical relevance of the theoretical findings and provide concrete contexts in which the paper's insights can be applied.\n\n4. **Average Eigenvalues and Convex-Concave Settings:** The paper's discussion on the role of average eigenvalues of the symmetric part of the Jacobian matrix $S$ in determining convergence rates might appear unclear to some readers. It would be advantageous if the authors could elaborate on whether these results are most relevant in non-convex non-concave settings, or in convex-concave settings that are not strongly convex-concave. This would help readers better understand the implications of the paper's results in different game settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of the paper. We address each concern separately.\n1. **Clarity on MP, EG, and Overparametrization:**\nThe benefit of using extrapolated gradient methods such as MP or EG for last-iterate convergence is well-known, for a general min-max optimization context [LS19, Section 3 and references therein].\nFor the problem of computing mixed Nash equilibria, it is shown in [WLZL21] that MP converges while its explicit analog (MDA) diverges [BP18], and in [WC22] that the method called \"EG\" in Section 4 converges while its explicit analog had not yet been analyzed.\nTherefore when writing Section 4 of the paper (on computing mixed Nash equilibria), we chose to focus directly on the methods that are known to converge. \nNevertheless we agree that a reminder of this background information would be helpful.\n\t- Regarding overparametrization, our results suggest that it generically improves the local conditioning of min-max problems. Moreover, this improvement implies that it is not in fact necessary to resort to extrapolated gradient methods for convergence -- although they still have a faster rate than explicit methods.\n\n2. **Applicability to Non-Square Games:**\nOur results apply to non-square games, with the exception of the convergence rate estimates when interaction dominates (Propositions 3.1-3.3 and Table 1).\nFor those, it is straightforward to relax the assumption $n=m$ to $|n-m| \\leq 1$, but not beyond that.\nWe believe that an analogous behavior takes place in the general case $n \\neq m$ (after changing the average eigenvalue of $S$ by a suitable, related, quantity) but we have not yet been able to prove it.\nWe will add an explicit remark about this.\n\n3. **Practical Examples of Slight Curvature Setting:**\nIn addition to the example studied in Section 4, another interesting example is the Augmented Lagrangian method, which is commonly used for real-world constrained optimization problems. We will include a discussion of this setting in revision.\n\n4. **Average Eigenvalues and Convex-Concave Settings:**\nThe relation between average eigenvalues of the symmetric part of the Jacobian matrix $M=S+A$ and convergence rate, is agnostic to convexity-concavity.\nIndeed the relation goes via the algebraic quantity $\\tilde{\\mu}_M$, which determines the local convergence rate of gradient flow by a fully general dynamical system result.\nIn fact our average-eigenvalue results of Section 3 do not require $S$ to be positive semi-definite,\nand so they also apply in non-convex non-concave settings.\nWe chose not to emphasize this fact because we focus on convergence to local Nash equilibria throughout, which automatically implies local convexity-concavity, but we will add a brief remark on it. \n\n[BP18] James P. Bailey and Georgios Piliouras. “Multiplicative Weights Update in Zero-Sum Games”. In: Proceedings of the 2018 ACM Conference on Economics and Computation (2018).\n\n[LS19] 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. PMLR. 2019, pp. 907–915.\n\n[WC22] Guillaume Wang and Lénaïc Chizat. “An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games”. In: arXiv preprint arXiv:2211.01280 (2022).\n\n[WLZL21] Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. “Linear Last-iterate Convergence in Constrained Saddle-point Optimization”. In: International Conference on Learning Representations. 2021."}, {"review_id": "MPNcAUWSDH", "reviewer": "Reviewer_oPMS", "summary": "The authors study the convergence of gradient descent-type algorithms for saddle-point problems of the form $\\displaystyle\\min_{x \\in \\mathbb{R}^n } \\displaystyle\\min_{x \\in \\mathbb{R}^m} f(x,y)$. Let $M$ denote the Hessian of $f$ at a local saddle point: convergence is governed by the minimum real part of all eigenvalues of $M,$ denoted $\\mu_M$. We have $\\mu_M \\ge 0,$ and this inequality is strict for almost all $M\\in \\mathbb{R}^{n\\times m}$, as the authors verify in their Theorem 2.1. This observation motivates the use of regularization/overparametrization for such problem involving quadratic/higher order terms.\n\nDecomposing $M$ into symmetric and antisymmetric parts, $M=S + \\alpha A$, with $\\alpha$ small, and write \n\\begin{equation}\nA = \\left(\\begin{array}{cc} \n0 & P \\\\\\\\\n-P^T & 0\n \\end{array}\\right),\n\\quad \nS = \\begin{bmatrix} Q & 0 \\\\\\\\\n0 & R \\end{bmatrix}.\n\\end{equation}\n\nFor $m=n,$ the Taylor expansion formula of Proposition 3.1 shows that $\\mu_M$ is well-approximated by the expression $\\displaystyle\\min_{1\\le j \\le n} \\left( u_j^T Q u_j  + v_j^T R v_j \\right)$, where the $u_i, v_i$ are the left and right singular vectors of $P = U \\Sigma V^T.$ Assuming $U,V$ are drawn uniformly from $O(n),$ the authors show that this expression (in expectation and with concentration) is asymptotically the average of the spectrum of $S,$ under the assumption that the spectrum is \"spread out\" in the sense $\\operatorname{tr} (S) / \\lVert S \\rVert_F$ is bounded by $\\sqrt{\\log n} $ times some constant greater than 2. As a counterpoint, the authors  consider the \"sparse\" case where $S$ has a fixed number $r$ of nonzero eigenvalues, and derive corresponding asymptotics and concentration bounds. Some experiments illustrating the theory for classical gradient methods are given.", "questions": "line 156: \"In this section we assume $m=n$ for simplicity.\" I assume this is WLOG, since $Q$ and $R$ are arbitrary in your results, and we can just add variables to maintain $A\\gg  S$?\n\nline 208: \"four\" -> \"three\"?\n\nline 225: \"x gets updated\" more precisely, updated with the gradient rule rather than by averaging.", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written overall. I am happy with the mathematical details, having read the main paper and the first two sections of the supplementary material and found no errors. ", "weaknesses": "The main limitation I see is one that the authors have already suggested in the conclusion: namely, it is not clear how the insights developed in this paper could extend to $N$-player games for $N>2$, since the assumption that $S$ is positive definite is needed, and the \"interactions\" among more than two players seem to be more subtle to define.\n\nI also found the experimental section to be rather confusing. It really feels like an afterthought, and far more technical than necessary. What is the connection with the previous sections? If the point is just to illustrate that extra parameters can accelerate convergence, then be clear about that and move the many unnecessary technical details to the appendix. It is rather surprising that your \"randomly-drawn\" $f$ has the property that Theorem 2.1 fails, no? Is it by design that the family of such functions will not have this property? I also think more attention could be drawn to the fact that $M_{\\text{MP}}$ and $M_{\\gamma}$, although not the actual Hessian of the payoff function $f,$ play the same role in the dynamics as $M$ would for vanilla gradient flow. Please make this more clear. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Regarding the second paragraph of \"Weaknesses\":\nSection 4 is not an experimental section, but an application of the previous considerations to a particular class of min-max problems which is of its own interest in game theory:\n$\n    \\min\\_{\\mu \\in \\mathcal{P}(\\mathcal{X})} \\max\\_{\\nu \\in \\mathcal{P}(\\mathcal{Y})} \n    \\left\\lbrace F(\\mu, \\nu) \\coloneqq \\mathbb{E}\\_{x \\sim \\mu, y \\sim \\nu} [f(x,y)] \\right\\rbrace.\n$\nHere \"$f$\" represents a parameter of the problem -- and not a min-max objective function itself (contrary to the notation in Sections 1-3). We will make sure to better draw attention to this change of convention.\nBecause this is an infinite-dimensional problem when $\\mathcal{X}$, $\\mathcal{Y}$ are continuous sets, algorithms to solve it are based on reparametrized formulations, which are the ones we actually analyze.\n\nThe fact that the property from Theorem 2.1 fails for the \"natural\" reparametrization\n$\n    \\min\\_{a \\in \\Delta\\_N} \\max\\_{b \\in \\Delta\\_M} \n    \\left\\lbrace \n        F\\_1(a,b) \\coloneqq\n        \\sum\\_I \\sum\\_J a\\_I b\\_J f(x^*\\_I, y^*\\_J)\n    \\right\\rbrace\n$\nfor randomly drawn $f$, is not very surprising in hindsight. Indeed it is known that Mirror Flow does not converge unless $N=M=1$ [MPP18], so it was to be expected that $\\tilde{\\mu}\\_{M\\_{\\mathrm{MP}}}=0$.\nBy contrast, for the overparametrized formulation\n$\n    \\min\\_{a, x} \\max\\_{b, y} \n    \\left\\lbrace\n        F\\_2(a, x, b, y) \\coloneqq\n        \\sum\\_I \\sum\\_J a\\_I b\\_J f(x\\_I, y\\_J)\n    \\right\\rbrace,\n$\nthe condition from Theorem 2.1 does indeed hold for randomly drawn $f$, as discussed in the paragraph \"Overparameterization induces partial curvature\" of Section 4.\nWe realize that some of this background information is lacking in Section 4, and we will add it.\n\nRegarding the Questions:\n- line 156:\nThe assumption that $n=m$ in Section 3 can be relaxed straightforwardly to $|n-m| \\leq 1$, but not beyond that.\nIndeed for our eigenvalue expansion result (Proposition 3.1) we needed to assume $A$ has distinct eigenvalues, which implies $|n-m| \\leq 1$.\nWe believe that an analogous behavior takes place in the general case $n \\neq m$ (after changing the average eigenvalue of $S$ by a suitable, related, quantity) but we have not yet been able to prove it.\n- line 208: Indeed this is a typo, thank you.\n- line 225: Indeed, this will make the text easier to read, thank you.\n\n[MPP18] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. “Cycles in adversarial regularized learning”. In: Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms. SIAM. 2018, pp. 2703–2717."}, {"review_id": "BgOkoeKcYu", "reviewer": "Reviewer_JUcy", "summary": "This paper focuses on min-max games with partial curvature, i.e., the symmetric part S of the Jacobian is p.s.d. and nonzero, and specifies the necessary and sufficient conditions for the convergence of gradient flow. The authors show that when the interaction term dominates, the convergence rate could depend on the average of the eigenvalues of S.\nThey also use the problem of computing mixed Nash equilibria of continuous games to illustrate the results.", "questions": "Propositions 3.2 and 3.3 require that U and V are uniformly distributed on $O_n$. After taking the expectation over all these problem instances, the averaged convergence rate depends on the average of the eigenvalues of S.\nHowever, in practice, we are faced with a specific instance and such an expectation step might be invalid. When the antisymmetric part of the Jacobian is given in advance, is the convergence rate still related to the average of the eigenvalues of S?", "limitations": "This paper only studies local convergence.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper is well-organized.\n2. The results are novel and interesting.\n3. The analysis is detailed and solid.", "weaknesses": "1. Propositions 4.2 and 4.3 are based on a very restrictive setting (see Questions).\n2. Some expressions are not easy to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The relation between convergence rate and average of the eigenvalues of $S$ is only valid under a randomized setting.\nFor a fixed $S$, in the worst case, the convergence rate does depend on the minimum eigenvalues of $S$ (to be precise, on $\\sigma\\_{\\min}(Q) + \\sigma\\_{\\min}(R)$, by the eigenvalue expansion of Proposition 3.1).\nHowever building the worst-case instance requires a very special alignment between the singular vectors of $P$, $Q$ and $R$.\nThe role of the randomness in our analysis is to reveal the generic behavior of the convergence rate, when the singular vectors of $P$, $Q$ and $R$ are in general position."}, {"review_id": "35VBVbQdEe", "reviewer": "Reviewer_L3Mt", "summary": "This paper studies the convergence of Gradient based methods to local Nash equilibria. The properties of the “potential” and the “interaction” parts of the game are analyzed, and conditions when this leads to convergence of gradient methods are studied.", "questions": "See above", "limitations": "See above", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper provides insights into the convergence of minimax algorithms, and highlights important differences from the minimization setting.", "weaknesses": "The writing and presentation of the results can be improved. \n\n - Is the y-axis in Figure 1(a) the rate of convergence. What is the significance of including the observed and the predicted $\\tilde{\\mu}_M$? \nCan a plot of the the actual iterated of the algorithm for any one particular realization of $P$ also be included? \n[Like how GDA spirals out for a simple bilinear game, how does the trajectory change for this new game? Does the spiraling towards the solution happen in a skewed manner? \nMaybe a plot which shows the trajectories (for one particular P) of GDA diverging for the bilinear game, but converging when the new term is added could help the reader visualize how these algorithms converge\n]\n\n - The proofs on page 4 has a few terms which are overflowing to the left.\n\n - The result showing the dependence on the average of the eigenvalues is surprising. How crucial is this result on the choice of the matrices $U$ and $V$ being distributed uniformly on the set of $n \\times n$ orthonormal matrices? Proposition 3.2 and 3.3 cover the cases when the matrices $S$ is not sparse and sparse, but can a complete characterization on the way $P$ is drawn also be done? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We address each listed Weakness separately.\n- In Figure 1(a), the datapoints shown by circles represent the observed convergence rate $r$ of GDA with step-size $\\eta$, obtained by really running GDA for many iterations for a small $\\eta$.\nOn the other hand the lines represent the quantity $\\tilde{\\mu}\\_M = \\min\\_{\\lambda \\in \\mathrm{Sp}(M)} \\Re(\\lambda)$ where $M$ is the Jacobian matrix, obtained simply by computing the eigenvalues of $M$ for different values of the regularization parameter $\\alpha$.\nThe fact that $r/\\eta$ and $\\tilde{\\mu}\\_M$ coincide confirms the known dynamical systems result that $\\tilde{\\mu}\\_M = \\lim\\_{\\eta \\to 0} r/\\eta$ (the convergence rate of GF).\n\t- Yes, we will add plots of the actual iterates for a particular $P$, in dimension $n=m=2$. The spiraling towards the solution indeed happens in a skewed manner, with the \"axes\" matching the eigenvectors of the Jacobian $M$.\n- The overflow on page 4 will be fixed.\n- Our motivation for studying a randomized setting was to capture the behavior of the convergence rate in the generic situation where the singular vectors of $P$, $Q$ and $R$ are in general position (i.e. do not have a particular form of alignment). \nHence we chose the simplest setting: $(U, V)$ uniformly distributed, and we have not studied any other distribution.\n\t- The precise way $P$ is drawn does not matter, only the way its singular matrices $U$ and $V$ are distributed.\nIndeed $\\tilde{\\mu}\\_{M\\_\\alpha}$ only depends on $S$ and $U, V$ up to $O(\\alpha^3)$ (as a consequence of the eigenvalue expansion of Proposition 3.1)."}]

Author rebuttal:

Meta-review: All four reviewers are positive about this paper and think it should be accepted and I support their decisions. Please take into account the reviewers comments while preparing the final version.
Decision: Accept (poster)