Finding and only finding local Nash equilibria by both pretending to be a follower
Authors: Xuchan Bao
Guodong Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: game theory
general-sum games
local Nash equilibrium
optimization

Abstract: Finding (local) Nash equilibria in two-player differentiable games is a classical problem in game theory with important relevance in machine learning. We propose double Follow-the-Ridge (double-FTR), an algorithm that locally converges to and only to local Nash equilibria in general-sum two-player differentiable games. To our knowledge, double-FTR is the first algorithm with such guarantees for general-sum games. Furthermore, we show that by varying its preconditioner, double-FTR leads to a broader family of algorithms with the same convergence guarantee. In addition, double-FTR avoids oscillation near equilibria due to the real-eigenvalues of its Jacobian at fixed points. 
Empirically, we validate the double-FTR algorithm on a range of simple zero-sum and general sum games, as well as simple Generative Adversarial Network (GAN) tasks.

Under review as a conference paper at ICLR 2023
FINDING AND ONLY FINDING LOCAL NASH EQUILIB- RIA BY BOTH PRETENDING TO BE A FOLLOWER
Anonymous authors Paper under double-bling review
ABSTRACT
Finding Nash equilibria in two-player differentiable games is a classical problem in game theory with important relevance in machine learning. We propose double Follow-the-Ridee (double-FT) FTR), an algorithm that locally converges to and only local Nash equilibria in general-sum two-player differentiable games. To knowledge, double-FTR is the first algorithm with such guarantees for general-sum games. Furthermore, we show that by varying its preconditioner, double-FTR leads to a broader family of algorithms with the same convergence guarantee. In addition, double-FTR avoids oscillation near equilibria due the eigeviiges of its Jacobian at fixed points. Empirically, we validate the doublc-FIK algorithm on a range of simple zero-sum and general sum games, as well as simple Generative Adversarial Network (GAN) tasks.
INTRODUCTION
Much of the recent success deep learning can be attributed the effectiveness of gradient-based optimization. It is well-known that for minimization problem, with appropriate choice of learning
rates, gradient descent has convergence guarantee local minima (Lee et al., 2016 2019). Based on
this foundational result, an array of accelerated and higher-order methods have since been proposed
and widely applied training neural networks (Duchi et al. 2011 Kingma and Ba 2014 Reddi
al. 2018 Zhang al. 2019b).
However, once we leave the realm of minimization problems and consider the multi-agent setting, the optimization landscape becomes much more complicated. Multi-agent optimization problems arise in
diverse fields such as robotics, economics and machine learning (Foerster et al., 2016) Von Neumann
and Morgenstern 2007: Goodfellow et al., 2014 Ben-TTal and Nemirovski 2002 Gemp al. 2020
Anil et al. 2021).
A classical abstraction that is especially relevant for machine learning is two-player differentiable games, where the objective is to find global or local Nash equilibria. The equivalent of gradient descent in such game would be each agent applying gradient descent to minimize their objective function. However. in stark contrast with gradient descent in solving minimization problems. this seadeent-descent-styleee algorithm may converge to spurious critical points that are not local Nash equilibria, and in the general-sum game case, local Nash equilibria might not even be stable critical points for this algorithm (Mazumdar al. 2020b)!
These negative results have driven surge of recent interest in developing other gradient- based algorithms for finding Nash equilibria in differentiable games. Among them is Mazumdar al. (2019), who proposed an update algorithm whose attracting critical points are only local Nash equilibria the special case of zero-sum games. However, to the best of our knowledge, such guarantees have not been extended to general-sum games.
We propose double Follow-the- Ridge (double-FTR). a gradient-based algorithm for general-sum differentiable games that locally converges and only differential Nash equilibria. Double-FTF FTR is closely related to the Follow-the- Ridge (FTR) algorithm for Stackelberg games (Wang et al. 2019). which converges to and only local Stackelberg equilibria (Fiez et al., 2019). Double-FTR can be viewed as its counterpart for simultaneous games, where each player adopts the "follower" strategy in FTR.

---

Under review as a conference paper at ICLR 2023
The rest of this paper is organized as follows. In Section give background two-player differentiable games and equilibrium concepts. We also explain the issues with using gradient- descent-style algorithm on such games. In Section E present the double-FTR algorithm and prove its local convergence to and only to differential Nash equilibria. We also identify a more general class of algorithms that share these properties. We discuss recent works directly relevant to double-FTR in Section E and other related work in Section S In Section 6 we show empirical evidence of double-FTR's convergence to and only to local Nash equilibria.
BACKGROUND
2.1 TWO-PLAYER DIFFERENTIABLE GAMES AND EQUILIBRIUM CONCEPTS
In a general-sum two-player differentiable game, player aims to minimize f g"+m - with respect to æ IR", whereas player 2 aims maximize g ""*"" E with respect to y E R". Following the notation in Mazumdar et al. (219)). we denote such the game as {(J, -9), R++m).
We also make the following assumption the twice pnic-differentiabiliyy of and g.
Assumption 1. x E R", y R" f and g are twice-dificrentiabll, and the second derivatives are continuous. Also, V and V are invertible.
For two rational, coo-eoopee players. their optimal outcome is achieve local Nash equilib- rium (Ratiiff et al. 2013). A point (x", (x=,y") ) is local Nash equilibriun[] of {(f, -9), R") R=*m) if there exists open sets S. C I Sy C I such that x² Swx y E Sy. and
f(x", y(x".y") f(x,y"), y"), g(x", v(x",²") g(x", "a"""," y), Vx E Sz, Vy Sy.
closely related notion of equilibrium is the differential Nash equilibrium (DNE) (Ratifff et al. 2013). which satisfies a second-order sufficient condition for local Nash equilibrium.
Definition 2.1 (Differential Nash equilibrium), (x", 3²) is a differential Nash equilibrium of (J,-9), B=+m] if the following conditions hold:
fa=", y²)
V Vug("", 2²) = O.
fl= y²) > O and V g (x", y²) < O.
The conditions of DNE slightly stronger than that of local Nash equilibria in that the second-order conditions are definite instead of semi-definite. In this paper, we focus on DNE, as they make up almost all local Nash equilibria in the mathematical sense, and are well-suited for the analysis of second-order algorithms.
2.2 ISSUES WITH GRADIENT- BASED ALGORITHMS
natural strategy for agents search for local Nash equilibria in differentiable game is to gradient-based algorithms. The simplest gradient-based algorithm is the gradient descent-asceni (GDA) (Ryu and Boyd 2016 Zhang al. 202T6 (Algorithm its variants (Zhang al. 2021a
Korpelevich 1976 Mokhtari et al. 2020
Algorithm 1 Gradient descent- (GDA)
Require: Number of iterations T. learning rate
1: for = 1,..., do
7 V f y:) 3: Yt++1 = Yt + 7V Veg 0e, yt)
2: Et+1
4: end for
② and 0 be the learning rate, a gradient-based update algorithm can be written as:
Let
++1 (w(2)) (z:).
Note that local Nash equilibrium is not guaranteed to exist in nonconvex-noncomee games (Cln et al. Proposition 6), although the (non-jexistence of local NE out of the scope of this paper.
2020
2

---

Under review as a conference paper at ICLR 2023
LASE
DNE
LASE
DNE
(a) General-sum
(b) Zero-sum
Figure I: Venn diagrams showing the relationship between the set of locally asymptotically stable equilibria (LASE) the GDA flow set of differential Nash equilibria (DNE) in two-player differentiable games. Note that for general-sum games, there exist DNE that are unstable for GDA flow.
The Jacobian of (z) is defined as J [z) ==
@w((x)
In the case of GDA, we have:
Oz
(GDA(Z) V fz; z) vg ar, y)
22
2 my
JGDA
ya
vy
Using the Jacobian matrix, we characterize the fixed points of equation Definition 2.2 ((Strictly) stable fixed point). =" is stable fixed point of the discrete-time dynamical system in equation]
w(=") 0 and p(I p -T--J(=²")> 1
where pl-) denotes the spectral radius of matrix. If we additionally have p(I ((I=)((=")) 1, then is strictly stable fixed point.
Strictly stable fixed points are important for analysis, they are locally asymptotically conver- gent Galor 2007). L.e. there exists an open set S₂ such that xt E S, and lim; 2t x" Azu E Sz.
A closely related concept the locally asymptotically stable equilibrium (LASE) for the continuous- time system = (2). (Ratlif et al. 2013).
Definition 2.3 (Locally asymptotically stable equilibrium (LASE)). x" is a locally asymptotically stable equilibrium of the continuous-time dynamics = -w(z) if
wxx") O and Re(A) > 0 for AA E spec(J(z"))
where Re(-) denotes the real part of complex number, and spec(.) returns the spectrum (i.e. the set of cigenvalues) of a matrix.
Note that when y O. strictly stable fixed points of equation D are equivalent to LASE of 1 (z). In this paper, we prove convergence results discrete-time (using Definition 2.2 but we often provide intuition using continuous-time concepts such LASE.
Unfortunately, GDA is not guaranteed to converge to DNE, nor are DNE necessarily (strictly) stable fixed points of the GDA dynamics. Even the special case of zero-sum games f).
GDA dynamics can still have stable fixed points that are not DNE (Daskalakis and Panageas 2018 Mazumdar al. 2020b). The relationship is shown in the Venn diagrams in Figure (to eliminate the effect of 7, we show illustration in the continuous-time limit 2 -WDA(=2)
In Figure 2 demonstrate the failure modes of GDA in zero-sume games. In 2a GDA converges to
a spurious strictly stable fixed point which is not DNE. In 26 GDA fails to converge to the unique DNE (Hsieh al. 2020). Instead, it goes into a limit cycle, due the strong rotation introduced by large complex parts in its Jacobian eigenvalues. We stress that these pathologies are not limited to GDA, but common for many other first-order algorithms (Wang al. 2019
DOUBLE FOLLOW-THE-RIDDE
We propose double Follow-the-Ride Ridge (double-FTR), an update rule for general-sum differential games that locally converges to and only to differential Nash equilibria. The double-FTR update is shown in Algorithm 2 (the arguments 24, yt of and g dropped avoid notational clutter).
3

---

Under review as a conference paper at ICLR 2023
Nan Mayhh LASE
Local RaAD
GDA
CDA
0G3A
CD4
DOUDIN-TTR
docktu-F11
1000
-15
-30
-25
0.5
25
5.5
75
15.0 -1.9
-15
-5.0
-25 0.
25
3.0 10.0
(a) f(z, v)
2x
5xy y²
(b) f(, v) g( v) zy c(x²
Two examples of GDA failure modes in finding Nash equilibrium in zero-sum games. (a) GDA converges to the spurious strictly stable fixed point (0, 0), which is not Nash equilibrium. Other first-order methods such the optimistic GDA (OGDA) and extragradient (EG) converge to the spurious fixed point as well. (b) Instead of the unique Nash equilibrium 0), GDA converges limit cycle both when initialized "inside" (green) and "outside" (blue). We use 0.0001, 7 0.01.
Figure 2:
Algorithm 2 Double Follow-the-Ride
Require: Learning rate Y/= and Tly; number of iterations T.
1: for t = ,,..., T' do
2: Ø(+1 + xt The 2 Bly 2 m
VV2
3: Ft++1 f- Y: + Thu و + Tie V 9y
12
V
yz
4: end for
express Algorithm in vectorized form (equation simplify the notation, we drop the subscript t for f and g.
Let 7 The and Thm
2 To
y
-12
1
Vaf
2++1 = - (Z)) (FTR(Z))=
- (r99) V ya
I
3.1 LOCAL CONVERGENCE OF DOUBLE-FTR
In this section, we give our main theoretical result. First, we introduce an additional assumption. Assumption 2. At fixed points of equation JGDA has full rank.
Assumption 2 ensures that in double-FTR, the additional terms the update not exactly cancel out the GDA terms. In practice, E2 regularization might need to be added to the objective functions. Note a similar assumption is introduced Mazumdar et al. (2019) Theorem
Our main theoretical result is stated below.
Theorem 1. Under Assumptions I Hadd and with an appropriate choice of learning rate % is
strictly stable fixed point of the double-FTR FTR update (equation 2 if and only if it is differential Nash equilibrium of the game {(S -UJ, Rn+m). Furthermore, at fixed points of equation 2 all
eigenvalues of the Jacobian J Jrrn := OWETR are real.
dz
Intuitively, the first part of the theorem classifies the strictly stable fixed points of double-FTR, and the second part ensures that there is rotation caused by complex eigenvalues in the neighbourhood Appendix A
of the DNEs. We defer the proof of Theorem |
Corollary (Local convergence). Let 2 be DNE of the game {(f. -9). R R" Under Assump-
tions 1 and 2 and with an appropriate choice of learning rate y, there exists an open set S₂ C R where z Sz. such that when following equation
4 2g E Sz. lim žt zz.
4

---

Under review as a conference paper at ICLR 2023
Proof. The proof follows naturally by combining Theorem with the local convergence of strictly stable fixed points (Galor (2077). Proposition 1.9).
To the best of our knowledge, double FTR the first algorithm with such local convergence result for general-sum games.
3.2 GENERAL PRECONDITIONERS
In the following remark, we show that double-FTR can be generalized to include whole family of algorithms.
Remark Theorem applies to a more general version the double FTR algorithm. In particular, we can generalize equation 2 to allow broader class of "preconditioners":
2++1 2t (ZFTn(Z)) @Frn(*)= Px (eDa(Zz)
a
(3)
-Py]
cV #
where Pa. Py are functions of x, respectively, which satisfy Pa > 72
V V >
and
Pv < byg - O.
Equation corresponds to the special case of Pa - ( (v (V 9)
9) The proof for
Theorem directly applies to the of general preconditioners in Remark
Remark I provides intuition on the convergence properties of double-FTR, Without the preconditioner
Pn and Py double-FTR reduces to Hamiltonian gradient descent (Mescheder et al., 2017: Balduzzi
et al. 2018 Loizou et al. 2020 Abernethy et al. (02T). which is not guaranteed to only converge to local Nash equilibria. It the introduction of the preconditioner that enables strictly stable fixed
points to satisfy the second-order condition of DNE.
Remark T also sheds lights on how derive more practical algorithm. Naively implementing Algorithm might cause instability when V and V Vyy are near singular. In practice we use instead of (f f') in Algorithm 2 (where a small À 0 is the damping parameter). Note that this also allows us to drop the assumption on the invertibility of 2 and V yyg in Assumption |
( axce / mta
/ A
4 CONNECTION WITH OTHER ALGORIHHS
Mazumdar et al. (2019) proposed local symplectic surgery (LSS) gradient-based algorithm whose LASE are exactly local Nash equilibria in two-player zero-sum games. LSS avoids oscillatory behaviour at local Nash equilibria (similar to double-FTR). Compared to LSS, double-FIT appears to have a simpler form and enables a broader family algorithms with such local convergence result in general-sum games.
The Follow-the- thediee (FTR) algorithm (Wang et al. 2019) is closely related to our proposed double- FTR. FTR was proposed for two-player sequential games and is guaranteed to converge and only to local minimax. FTR applies gradient correction term on the follower in a sequential game, so that the agents approximately follow ridge in the landscape of the objective function. The double-FTR can be viewed as a counterpart of FTR for simultancous games. The update rule of double-FTR resembles that of FTR, with the gradient modification term applied on both players.
Another related algorithm is the Hamiltonian gradient descent (HGD) (Mscceeerr et al. Balduzzi et al., 2018 Loizou et al., 2020 Abermethy al. 2021). HGD performs gradient- descent on the Hamiltonian, or the squared norm of the gradient. HGD is guaranteed to converge, as it is essentially a minimization problem. However, general is not guaranteed converge only to local Nash equilibria. Interestingly, our double-FTR can be viewed as preconditioned HGD.
2017
5 RELATED WORK
Mazumdar et al. (2000) introduced a general framework for competitive gradient-based learning. They characterized local Nash equilibria in terms of the critical points of the gradient algorithms.
5

---

Under review as a conference paper at ICLR 2023
20
NannMMahh sq.
>a
10
Figure 3: Left: evolution of GDA and double-FTR in the 2-D toy example from multiple initial points. Middle:
zoom-in near local Nash equilibrium point. Right: zoom-in near non-Nash LASE for GDA algorithm.
They showed the lack of convergence of the gradient algorithm in games, which motivated the development of the double-FTR algorithm.
Much work has focused on improving the dynamics in finding stable fixed points, which crucial in applications such GANs, where oscillation caused by eigenvalues with zero real parts of large imaginary parts in the gradient Jacobian can lead to training instability. MMscchder et al. (2017) proposes Consensus Optimization, which encourages agreement between the two players by introducing regularization term in the objectives of both players. The regularization term results in more negative real-part for the eigenvalues of the gradient Jacobian, therefore reduces oscillation and allows larger learning rates. Balduzzi et al. (018)); Gemp and Mahadevan (2018) proposes Symplectic Gradient Adjustment (SGA), which decomposes the gradient Jacobian into symmetric (potential) and asymmetric (Hamiltonian) parts and adds gradient adjustment term for rapid convergence to stable fixed points. (Shaaee and Anandkumar (019)) proposes Competitive Gradient Descent (CGD), whose update is given by the Nash equilibrium of regularized bilinear approximation of the original game. Compared to other methods, CGD has the advantage of not needing to adapt step size when the interaction strength changes between players. Many other methods have been proposed with different strategies for predicting other agents' moves, such as Learning with Opponent Learning Awareness (LOLA) (Foerster al. 2016) and optimistic gradient descent-ascent (OGDA) (Popov) 1980, Rakhlin and Sridharan] 2013; Daskalakis et al.) 22188) Mertikopoulos et al.) 2018). However, of these existing methods address the problem of spurious (i.e. non-Nash) stable fixed points.
EXPERIMENTS
We conduct simple experiments demonstrate the implications of our theoretical results. In Sec- tion T. we show that the double-FTR algorithm empirically converges to and only to differential Nash equilibria, as predicted by Theorem In Section 6.2 we show that double-FTR is able to converge to local Nash equilibria that naive gradient-play avoids in general-sum linear quadratic games. In Section 6.3 we demonstrate the practical implications of another property of double-FTR eigenvalues of JFTR at fixed points are real.
6.1 2-D TOY EXAMPLE
We consider the zero-sum game [f.-f), R² with the following 2-D function (same as Mazumdar al. (019)):
f(z, = - t.00(=++>)) ((03222 + 2) + (0.5y² + +))
This function has several strictly stable fixed points for the GDA dynamics, among which some DNE and some are not. As shown in Figure B while GDA may converge to fixed points that are not local Nash equilibria, double-FTR avoids such spurious fixed points. Also, in the neighbourhood

---

Under review as a conference paper at ICLR 2023
140
234
Kv.2
Figure 4: Evolution of the loss landscape of general-sum linear quadratic game when optimized by double- FTR. We visualize two 2D slices (K..1, x2,2) and (K.,1, K2,2) and the loss functions fu and f. respectively. As the top levels of the illustration, the loss landscape is "bowl-shaped" convergence, confirming that double-FTR solution satisfies the second-order conditions for DNE.
of local Nash equilibria, GDA exhibits oscillatory behaviour due complex eigenvalues of the Jacobian matrix. In contrast, the double-FTR does not have oscillatory behaviour near local Nash equilibria. For reference, we also show the trajectories of Local Symplectic Surgery (LSS), In this experiment, LSS has similar convergence properties it avoids spurious fixed points and does not have oscillatory behaviour near local Nash equilibria.
6.2 SENERAL-SUM LINEAR QUADRATIC GAME
The linear quadratic (LQ) game is classic problem in multi-agent learning. is extension of the famous linear quadratic regulator (LQR) problem of optimal control to the multi-agent setting. Just as LQR being a simple yet important benchmark problem for studying properties of reinforcement learning algorithms, the LQ game provides valuable insights to multi-agent RL algorithms (Fazel al. 2018 //hang al. 2019a).
Consider the discrete- time linear dynamical system, where z E Rdd is the state, and two players provide control inputs u E Rd and Id respectively.
Az: B, + B, 20 x(20)
Each player adopts linear state-feedback policy: u, -;, - where the parameters Kg Rdd xd. K, Rdd,dd are to be determined by optimization. In general-sum LQ game, each player aims to find their corresponding policy parameters K that minimizes their individual quadratic loss function f (shown in equation Ju(K.. K.) defined analogously using Q. and R.)).
DC
fu(K u. Ko) = EZ)mp(=)
Σ
2, Quz 2: + u R
(Qa > R. > 0)
Despite their simplicity, LQ games are challenging to optimize, because even though the loss functions are quadratic in the states and actions, they are not convex with respect to the player parameters K and K.. Importantly, Mazumdar et al. (2020a) show that in general sum LQ games, using naive gradient-play almost surely avoids some Nash equilibria.
We demonstrate in general-sum LQ games, double-FTRF is able to find the Nash equilibria that are avoided by gradient-play We use a setting mentioned Mazumdar et al. (2020a). where d, = d, = d,, 1, R. R, 0.01, and
0.511 0.064
0 1
0.001
1
0 0.147
A
B.
B
Q
Q.
0.533 0.993
0
0
The initial state 2g is set to 1 or [1 1.1] with equal probability.
Figure and 5 shows an instance where the double-FTR is able to converge to a local Nash equilibrium, the same initial policy parameters K, and
but the gradient-play fails to. For both algorithms, K,. Figure visualizes the loss landscape for f., (K,, K,) and f, (K,, K,) when optimized by double-FTR. confirms that the solution double-FTR converges to is indeed Nash equilibrium (the

---

Under review as a conference paper at ICLR 2023
(a) Double-FTR
(b) Gradient-play
Figure 5: For the general-sum linear quadratic game, visualize the evolution of the field Jacobian through different 2D slices. At each step. contour plot visualizes the quadratic function defined by the current JCDA. centered at the current weight values. In both (a) and (b), the weights are initialized near a DNE that an unstable fixed point for GDA dynamics. (a): using double-FTR. the weights converge to the DNE, where the contour maps). (b): the gradient method avoids
JGDA has negative cigenvalues (shown as saddle-points this unstable DNE, and converges a stable fixed point instead.
Am
-02
155
-4
-00
091 De FTR
-08
SDA
100
1.00
200
350
100
150
200
500
Epplsadd
Figure 6: Weight evolution of the parameterized bilinear game under GDA and double-FTR. Solid line represent the weights for O, and dashed lines represent the weights for Φb.
second-order condition in Definition Figure visualizes the local vector field Jacobian (i.e. JGDA) and shows that the Jacobian contains negative eigenvalues, which makes a saddle point for gradient-play optimization. Indeed, gradient-ple play (shown in Figure 5b). avoids this Nash equilibrium. Instead, it eventually finds another Nash equilibrium that stable fixed point.
6.3 PARAMETERIZED BILINEAR GAME
We consider another zero-sum game, the stochastic parameterized bilinear game, as in Prajapat et al.) (02T). We use this experiment to demonstrate that double-FTR also beneficial for stochastic games, and does exhibit oscillatory behaviour due having real eigenvalues at fixed points.
min r(x,y) Pa
min -r(x, y) where x ~ N(uas o2), y ~ ( oz); r(x, y) = ry.. Py.
The unique Nash equilibrium with respect to (z, y) is (0, 0). However, the learnable parameters are the mean and the standard deviation of the distributions where æ and y are drawn from. We denote the learnable parameters for and as 0 and & respectively. At each time step, we obtain an unbiased estimate of the gradient using REINFORCE over a mini-batch of size
B
(or Φ)
1
Ve lo,, 0)r(2 w.), 0
Mgg 0n
Ver(0, computed analogously.
B
8

---

Under review as a conference paper at ICLR 2023
As is often the case, GDA has oscillatory behaviour due to the complex eigenvalues of its Jacobian fixed points. In this stochastic setting, the oscillation prevents convergence for GDA (Figure p In contrast, the double-FTR algorithm does not have rotational behaviour at fixed points, and converges to the unique Nash equilibrium (æ, y) = (0,0) 0).
Target Density
Density
Density
0.20
0.15
0.10
0.10
0.03
0.05
Figure Mixture Gaussians ID. Left: ground-truth, Middle: generator distribution learned by GDA. Right: generator distribution learned by double-FTR.
Targe:
20
Derster
Earsttnn
Rerition
Deratio 20000
Earycan
Figure 8: Mixure Gaussians 2D. Top: GDA suffers from mode collapse. Bottom: the generator distribution learned by double-FTR recovers all the modes.
6.4 GENERATIVE ADVERSARIAL NETWORKS
The Generative Adversarial Network (GAN) Gooddellow et al, 2014) a popular deep learning application for two-player games. The goal is find the Nash equilibrium where the generator perfectly matches the target distribution, and the discriminator is completely fooled by the generator.
In this experiment, we the GAN framework to learn mixture of Gaussians (MoG). We use the original saturating loss function. Both the generator and the discriminator are multi-layer perceptrons with hidden layers and 64 hidden units in each layer. With neural networks, directly implementing the Hessian would be computationally inefficient or infeasible. Instead, we use conjugate gradient to approximate the Hessian inverse. Details of the experiments can be found in Appendix
As shown in Figure / and g we apply GDA and double-FTR to learn MoG in ID and 2D. In both cases, GDA gets stuck spurious equilibrium and suffers from mode collapse. In contrast, double-FTR recovers all the modes, and the generated distribution closely matches the target.
7 CONCLUSION
We propose double Sallow-the-Rides (double-FTR). gradient-based algorithm for finding local Nash equilibria in differentiable games. We prove that under mild assumptions, double-FTR locally converges to and only to differential Nash equilibria in the general-sum games, and avoids oscillation in the neighbourhood of fixed points. Furthermore, double-FTR leads to broader family of algorithms that share the same convergence guarantee. Finally, we empirically verify the effectiveness of double-FTR finding and only finding local Nash equilibria across broad range of problems.
remark that by varying the preconditioner,

---

Under review as a conference paper at ICLR 2023
8 REPREDUCABILITY STATEMENT
For empirical results, we describe the experiment settings in detail in Appendix C code for all experiments in the supplementary material. For the theoretical results, proofs are included in the appendix.
We also provide
10

---

Under review as a conference paper at ICLR 2023
REFERENCES
J. Abemnethy, K. A. Lai, and A. Wibisono. Last-iterate convergence rates for min max optimization: Convergence of hamiltonian gradient descent and consensus optimization. In Algorithmic Learning Theory, pages 3-47, PMLR, 2021.
C. Anil, G. Zhang, Y. Wu, and R. Grosse. Learning to give checkable answers with prover-verifier games. arXiv preprint arXiv:2108. 12099, 2021.
D. Balduzzi, Racaniere, J. Martens, J. Foerster, K. Tuyls, and T. Graepel. The mechanics of n-player differentiable games. In International Conference Machine Learning, pages 354-363. PMLR, 2018.
A. Ben-Tal and A. Nemirovski. Robust optimizationn-methodllogy and applications. Mathematical programming, 92(3):55-4480, 2002.
Bradbury, Frostig, P. Hawkins, M. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milng and Q. Zhang. JAX: composable transformations of Python+Nummyy programs, 2018. URL
com/ google/jax
C. Daskalakis and I. Panageas. The limit points of (optimistic) gradient descent min-max optimiza- tion. Advances in neural information processing systems, 31, 2018.
C. Daskalakis, A. Ilyas, V. Syrgkamis, and H. Zeng. Training gans with optimism. In International Conference on Learning Representations, 2018.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
M. Fazel, R. Ge, S. Kakade, and M. Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International Conference on Machine Learning, pages 1467-1476. PMLR, 2018.
Fiez, B. Chasnov, and Ratliff. Convergence of learning dynamics in stackelberg games, arXiv preprint arXiv: 1xXi:1190600227,, 2019.
J. Foerster, I. A. Assael, N. De Freitas, and S. Whiteson. Learning to communicate with deep multi-agent reinforcement learning. Advances in neural information processing systems, 29, 2016.
O. Galor. Discrete dynamical systems. Springer Science & Business Media, 2007.
I. Gemp and S. Mahadevan. Global convergence to the equilibrium of gans using variational inequalities. arXiv preprint arXiv: 015511, 2018.
Gemp, McWilliams, C. Vernade, and T. Graepel. Eigengame: Pea as nash equilibrium. In International Conference on Learning Representations, 2020.
I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
I. Goodfellow, Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial networks. Communications of the ACM, 63(1 (3:11))1399144, 2020.
Y.P. Hsieh, P. Mertikopoulos, and V. Cevher. The limits of min-max optimization algorithms: convergence to spurious non-critical sets. arXiv preprint arXiv:2006. 09065,, 2020.
C. Jin, P. Netrapalli, and M. Jordan. What is local optimality in nonconvex-nonccomany minimax optimization? In International conference machine learning, pages 4880-4889, PMLR, 2020.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 2014.
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
11

---

Under review as a conference paper at ICLR 2023
J. D. Lee, M. Simchowitz, M. I. Jordan, and B. Recht. Gradient descent only converges to minimizers. In Conference on learning theory, pages 1246-1257. PMLR, 2016.
J. D. Lee, I. Panageas, G. Piliouras, M. Simchowitz, M. I. Jordan, and B. Recht. First-order methods almost always avoid strict saddle points. Mathematical programming, 176(1):31 1-337, 2019.
N. Loizou, H. Berard, A. Jolicoeur Martinea,,, P. Vincent, S. Lacoste-Julien, and I. Mitliagkas. Stochastic hamiltonian gradient methods for smooth games. In International Conference on Machine Learning, pages 6370-6381. PMLR, 2020.
Martens et al. Deep learning via hessian- free optimization. In JCML, volume 27, pages 735-742. 2010.
E. Mazumdar, L. Radifff M. I. Jordan, and S. S. Sastry. Policy-gradient algorithms have no guarantees of convergence in linear quadratic games. In AAMAS, 2020a.
E. Mazumdar, L. J. Ratliff, and S. S. Sastry. On gradient-based learning in continuous games. SIAM Journal on Mathematics of Data Science, 2(1):103-131, 2020b.
E. V. Mazumdar, M. I. Jordan, and S. S. Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv preprint wxXiv:9901.00833 2019.
P. Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras. Optimistic mirror descent saddle-point problems: Going the extra (gradient) mile. In International Conference Learning Representations, 2018.
L. Mescheder, S. Nowozin, and A. Geiger. The numerics of gans. Advances neural information processing systems, 30, 2017.
A. Mokhtari, Ozdaglar, and 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, pages 1497-1507. PMLR, 2020.
L. D. Popov. A modification of the arrow-hurwizz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845 848, 1980.
M. Prajapat, K. Azizzadenesheli, A. Liniger, Y. Yue, and A. Anandkumar. Competitive policy optimization. In Uncertainty in Artificial Intelligence, pages 64-74. PMLR, 2021.
A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019, PMLR, 2013.
L. J. Ratliff, A. Burden, and S. S. Sastry. Characterization and computation of local nash equilibria in continuous games. In 2013 51st Annual Allerton Conference Communication, Control, and Computing (Allerton), pages 917-924. IEEE, 2013.
S. J. Reddi, S. Kale, and S. Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
E. K. Ryu and S. Boyd. Primer on monotone operator methods. Appl. Comput. Math, 15(1) ):(1) 43, 2016.
F. Schäfer and A. Anandkumar. Competitive gradient descent. Advances in Neural Information Processing Systems, 32, 2019.
T. Tieleman, G. Hinton, et al. Lecture 6.5-rmppoop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
J. Von Neumann and O. Morgenster.. Theory of games and economic behavior. Princeton university press, 2007.
Y. Wang, G. Zhang, and J. Ba. On solving minimax optimization locally: follow-the-ridge approach. In International Conference on Learning Representations, 2019.
12

---

Under review as a conference paper at ICLR 2023
G. Zhang, X. Bao, L. Lessard, and R. Grosse. A unified analysis of first-order methods for smooth games via integral quadratic constraints. Journal of Machine Learning Research, 22:1-39, 2021a. la.
G. Zhang, Y. Wang, L. Lessard, and R. Grosse. Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization. arXiv preprint arXiv:2102.09466 2021b.
K. Zhang, Yang, and T. Basar. Policy optimization provably converges to nash equilibria in zero-sum linear quadratic games. Advances in Neural Information Processing Systems, 32, 201 9a.
M. Zhang. J. Lucas, J. Ba, and G. E. Hinton. Lookahead optimizer: k steps forward, 1 step back. Advances in Neural Information Processing Systems, 32, 2019b.
13


Reviews:
[{"review_id": "RQriX3j0aji", "reviewer": "Reviewer_2z6c", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes the application of Follow-The-Ridge (usage of Shur's complement in Gradient Dynamics) for both players. The authors establish that double Follow-the-Ridge (double-FTR) is an algorithm that locally converges to and only to local Nash equilibria in general-sum two-player differentiable games. ", "summary_of_the_review": "The authors propose double Follow-the-Ridge (double-FTR), an algorithm with local convergence guarantee to differential Nash equilibria in general-sum two-player differential games.", "strength_and_weaknesses": "Strength:\nThe iead of introducing of being the doubly the follower is interesting. It is not surprising that replacing the opponents' strategy by a follower's one will lead to better and safest performance. On the other hand, it seems to be a simpler and more general way (like a blackbox) to doing lookahead than previous approaches by modeling opponents.\n\nWeaknesses:\n1)There is no theoretical guarantee on convergence or approximation bound.\n2)The double Follow the ridge trick may be too simple. Anyway, there should be a comparison with simply lookahead methods and with the following publications:\n\na) https://arxiv.org/pdf/2210.09769.pdf\nb) https://arxiv.org/abs/2112.13826\n3) The method is second-order. ", "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": "PR4bg9YQOxK", "reviewer": "Reviewer_2AFw", "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": "This paper studies general-sum two-player differentiable games and proposes an algorithm (double-FTR) that locally converges to (and only to) differentiable Nash equilibria (DNE). Moreover, extensive empirical validation is provided.\n", "summary_of_the_review": "The paper proposes double-FTR algorithm which locally converges to and only to DNE. This algorithm is quite close to the FTR algorithm of [Wang, Zhang, Ba, ICLR 2019] and its analysis contains limited novelty. On the other side, the paper is well-written and the result is nice. This renders the paper marginally below the acceptance threshold.  ", "strength_and_weaknesses": "The main result of the paper is interesting and clearly presented. The proposed algorithm can be intuitively seen as an extension of the standard GDA algorithm where the update of each player has an additional term that makes use of second-order information. In particular, it seems like a natural extension of the FTR algorithm of [Wang, Zhang, Ba, ICLR 2019]. Having read the appendix, my main concern has to do with the technical novelty and challenges behind the main result. My concerns focus specifically on two aspects: (i) the algorithm is heavily similar to the FTR algorithm of [WZB '19] and (ii) the technical challenges (provided Assumption 2) are mainly algebraic manipulations of the double-FTR dynamics.\n\nI would like to pose the following questions:\n\nQ1. Can the authors highlight the technical novelties and challenges behind the result? Adding a technical overview section in the main body would be helpful. \n\nQ2. Assumption 2 ensures that the updates in lines 2 and 3 of Algorithm 1 do not vanish. Is it possible to drop this assumption or relax it by extending the proposed algorithm?  \n\nQ3. Is it known whether second-order information is truly necessary in order to obtain a result like Theorem 1? As discussed in Section 2, standard GDA fails to converge even in zero-sum games. It would be beneficial to add a more extensive discussion regarding other first-order methods.\n\nIn general, I believe that the paper is nice and well-written. However, I think that the technical contribution of the paper is limited. Nevertheless, I am willing to increase my score after authors' rebuttal depending on the response.\n", "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": "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": "DTDh4k59Aig", "reviewer": "Reviewer_tEUJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors contribute a novel method, Double-Follow-the-Ridge, for solving the problem of computing local Nash equilibria in two-player general-sum differentiable games. This novel method is inspired by the Follow-the-Ridge heuristic algorithm and uses second-order information along with first-order information. In fact, the authors generalize the method to contain dynamics that use preconditioners in place of the second order information as long as some conditions are met. Finally, the paper is complemented with an array of experiments that demonstrate the empirical performance of the proposed method. The convergence guarantees are restricted to the local convergence regime.\n", "summary_of_the_review": "The paper examines a well-established problem (min-max optimization of general-sum differentiable games), and it presents a novel method that builds upon existing work. The result is not particularly surprising although nontrivial. The idea of the novel method builds upon an existing algorithm but (probably justifiably) the authors did not move beyond local-convergence guarantees. As such, I believe the paper is slightly above the bar for acceptance.", "strength_and_weaknesses": "Pros:\n    * the paper is self-contained and all the definitions are provided\n    * the novel method is a natural extension of the Follow-the-Ridge\n\nCons:\n    * the convergence of the algorithm is guaranteed only locally\n    * although the paper contains a lot of preliminaries which is helpful, the main body contains a lot of facts that are standard in min-max optimization and could be moved to the appendix\n    * a standard reference for the limits of gda is not contained in the paper, i.e.,\n\nDaskalakis, C. and Panageas, I., 2018. The limit points of (optimistic) gradient descent in min-max optimization. Advances in neural information processing systems, 31.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "6_QKEcC0Nj", "reviewer": "Reviewer_PeZQ", "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": "  In this paper, the authors consider the problem of designing methods with local convergence for finding second order Nash equilibria in nonconvex two-player general-sum games. Their main result is that, under some assumptions, a variation of the Follow-the-Ridge algorithm is locally asymptotically stable around any second-order Nash equilibria of the game and is not locally asymptotically stable in any other point.", "summary_of_the_review": "  Based on my comments above, I believe that there are some interesting corollaries from the work that is presented in this paper but the paper needs significant changes to reflect that and the current motivation is not correct unless I am missing something. At the current state I cannot recommend acceptance.", "strength_and_weaknesses": "Strengths\n======================\n  - The problem that the authors consider is very important and difficult, and hence even the local convergence results in this area have significant theoretical importance.\n\n  - The paper is well-written and the algorithms and techniques well-explained.\n\n  - The dynamics that the authors provide are simple and intuitive and can potentially have significant practical applications.\n\nWeaknesses - Comments\n========================\n\n  General comment: I believe that the results of this paper are indeed interesting but I think their current motivation is wrong. I will justify this with the comments that I present below.\n\n  1. If we assume that there exists a Differential Nash Equilibrium according to Definition 2.1 and we also assume Assumption 1 then, unless I am missing something, f is convex with respect to x and g is concave with respect to y everywhere.\n  Proof sketch: Let $z^* = (x^*, y^*)$ be a Differential Nash Equilibrium according to Definition 2.1. Assume also that there exist a point $z_0 = (x_0, y_0)$ such that $f$ is not convex with respect to $x$ at $z_0$. This means that $\\nabla^2_{x x} f(z_0)$ has a negative eigenvalue. Consider now the line segment $L$ that connects $z^*$ and $z_0$. We know that the eigenvalues of $\\nabla^2_{x x} f(z^*)$ are all positive and that $\\nabla^2_{x x} f(z)$ is a continuous function of $z$ according to Assumption 1. It is also well-known that the eigenvalues are continuous functions of the matrices. Hence, the minimum eigenvalue of $\\nabla^2_{x x} f(z)$ goes from positive at $z = z^*$ to negative at $z = z_0$ in a continuous way. Since $\\nabla^2_{x x} f(z)$ is symmetric all the eigenvalues are real and hence there should be a point $\\bar{z} \\in L$ such that the minimum eigenvalue of $\\nabla^2_{x x} f(\\bar{z})$ is zero which means that $\\nabla^2_{x x} f(\\bar{z})$ is not invertible which violates Assumption 1. Therefore, f is convex with respect to x and similarly g is concave with respect to y. Am I missing something here?\n  Given the above, it is not an achievement of the proposed algorithm that is it stable only around stationary points that are second-order Nash because only such stationary points exist. So the main motivation of the paper is not correct.\n\n  2. The achievement of the proposed algorithm though is that it is stable around all the simultaneous stationary points of f with respect to x and g with respect to y. This to my knowledge is a not trivial property even when we assume that f is convex with respect to x and g is concave with respect to y. The reason that this is interesting is that this is applied in a general-sum setting. Finding such simultaneous stationary points is as difficult as finding fixed points of any continuous map!\n  Proof sketch: Let $H : \\mathbb{R}^n \\to \\mathbb{R}^n$ be a continuous map and let $f(x, y) = \\|x - H(y)\\|^2$ and $g(x, y) = - \\|x - y\\|^2$. Then it is easy to see that all the simultaneous stationary points of f with respect to x and g with respect to y, correspond exactly to the fixed points of $H$.\n  Finding fixed points of continuous maps is more general that finding solutions of general non-monotone variational inequalities, which is more general than multi-agent general-sum concave games which have a ton of applications in game theory and economics. So the fact that the proposed algorithm is locally asymptotically stable only on those points is an interesting property. Nevertheless, it should be compared to the known results from the variational inequalities community or the computation of fixed points community which is missing from the current version of the paper.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject