Second-Order Algorithms for Finding Local Nash Equilibria in Zero-Sum Games

## Abstract

Abstract Zero-sum games arise in a wide variety of problems, including robust optimization and adversarial learning. However, algorithms deployed for finding a local Nash equilibrium in these games often converge to non-Nash stationary points. This highlights a key challenge: for any algorithm, the stability properties of its underlying dynamical system can cause non-Nash points to be potential attractors. To overcome this challenge, algorithms must account for subtleties involving the curvatures of players’ costs. To this end, we leverage dynamical system theory and develop a second-order algorithm for finding a local Nash equilibrium in the smooth, possibly nonconvex-nonconcave, zero-sum game setting. First, we prove that this novel method guarantees convergence to only local Nash equilibria with a local linear convergence rate. We then interpret a version of this method as a modified Gauss-Newton algorithm with local superlinear convergence to the neighborhood of a point that satisfies first-order local Nash equilibrium conditions. In comparison, current related state-of-the-art methods do not offer convergence rate guarantees. Furthermore, we show that this approach naturally generalizes to settings with convex and potentially coupled constraints while retaining earlier guarantees of convergence to only local (generalized) Nash equilibria.

## 1 Introduction

We consider the setting of smooth, deterministic two-player zero-sum games of the form

$$ $\mathrm{Player\,1:\,}\min_{\mathbf{x}}f(\mathbf{x},\mathbf{y})\,\,\quad\quad \quad\,\,\mathrm{Player\,2:\,}\max_{\mathbf{y}}f(\mathbf{x},\mathbf{y})\quad \quad(\mathbf{x},\mathbf{y})\in\mathcal{G},$ (Game 1) $$

where $f$ can be nonconvex-nonconcave with respect to $\mathbf{x}\in\mathbb{R}^{n}$ and $\mathbf{y}\in\mathbb{R}^{m}$, respectively. In the unconstrained setting, i.e., when $\mathcal{G}$ is $(\mathbb{R}^{n},\mathbb{R}^{m})$, we seek to find a local Nash equilibrium. For the constrained setting, we will assume that $\mathcal{G}$ is convex and seek a local generalized Nash equilibrium.

Mathematical games are commonly studied in decision-making scenarios involving multiple agents in control theory [isaacs1999differential], economics [roth2002economist, rubinstein1982perfect], and computer science [roughgarden2010algorithmic]. In particular, several problems of interest have a natural zero-sum game formulation, such as training generative adversarial networks [goodfellow2014generative], pursuit-evasion scenarios [isaacs1999differential], and robust optimization [ben2009robust].

Several recent efforts [fiez2020implicit, Wang*2020On, chinchilla2023newton, daskalakis2023stay] consider a closely related minimax variant of Game 1, $\min_{\mathbf{x}}\max_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$; however, (local) *minimax* solutions can differ from (local) Nash equilibria in general nonconvex-nonconcave settings.
This difference arises from the *order* of agent interactions. At a Nash solution of Game 1, players controlling $\mathbf{x}$ and $\mathbf{y}$ act *simultaneously*. In contrast, minimax points correspond to Stackelberg equilibria and assert a *sequential* order of play: $\mathbf{x}$ acts first, then $\mathbf{y}$ follows. We highlight this fact to point out that under the assumptions of Game 1, the set of all local Nash points is a subset of the set of all local Stackelberg points [mazumdar2020gradient, ratliff2016characterization]. In particular, local Nash and Stackelberg points have the same first-order conditions but different second-order conditions.

The success of first-order gradient methods for single-agent learning problems made gradient descent ascent (GDA), the multi-agent analog of gradient descent, a natural starting point for solving Game 1. The GDA algorithm tries to find a critical point of $f$, i.e., where $\nabla f=\mathbf{0}$.
GDA is known to get trapped in limit cycles even in the most straightforward convex-concave setting, and several works have tried to modify the gradient dynamics by including second-order information to avoid this entrapment and direct the solution towards a stationary point of the dynamics [benaim1999mixed, daskalakis2017training, hommes2012multiple, mertikopoulos2018cycles, mescheder2017numerics, gidel2019negative]. However, outside of the convex-concave setting, these methods can converge to critical points that are *not* Nash equilibria. This behavior is due to the particular structure of second-order derivatives of $f$ with respect to $\mathbf{x}$ and $\mathbf{y}$, and while they do not arise in the single-agent settings, they are widely documented in the multi-agent zero-sum game setting [balduzzi2018mechanics, mazumdar2020gradient, ratliff2016characterization].

To guarantee that an algorithm only converges to local Nash equilibria, the algorithm’s gradient dynamics must not have any non-Nash stable equilibrium points. To the best of our knowledge, only two previous works, local symplectic surgery (LSS) [mazumdar2019finding] and curvature exploitation for the saddle point problem (CESP) [adolphs2019local], have such guarantees for the unconstrained nonconvex-nonconcave version of Game 1. However, neither of these methods provides any convergence rate analysis. Further, these works do not discuss the constrained setting of Game 1. A variety of Bregman proximal algorithms do find local min-max points in constrained, nonconvex-nonconcave settings with at best linear rates of convergence; however, they operate under the restrictive, blanket assumption that every critical point of $f$ is a local Nash equilibrium [Azizian2024], which is not generally true in nonconvex-nonconcave settings.

In this paper, we introduce second-order algorithms to solve Game 1. We highlight our specific contributions below:

- 1.
We introduce Discrete-time Nash Dynamics (DND), a discrete-time dynamical system that provably converges to only local Nash equilibria of the unconstrained version of Game 1 with a linear local convergence rate, while previous related work does not provide any convergence rates.
- 2.
We modify this dynamical system and construct an algorithm, Second Order Nash Dynamics (SecOND), which can converge superlinearly to the neighborhood of a point that satisfies first-order local Nash conditions.
- 3.
We discuss the constrained setting of Game 1, where $\mathcal{G}$ is a convex set. In this case, we use Euclidean projections to modify DND and develop an algorithm, Second-order Constrained Nash Dynamics (SeCoND), which finds a local generalized Nash Equilibrium point. In contrast, previous work either does not consider this constrained setting and/or is restricted to the convex-concave case.

## 2 Preliminaries

Throughout this paper, $\mathbf{x}\in\mathbb{R}^{n},\mathbf{y}\in\mathbb{R}^{m},$ and $\mathbf{z}=(\mathbf{x}^{\top},\mathbf{y}^{\top})^{\top}\in\mathbb{R}^{n+m}$.

### 2.1 Game-theoretic Concepts

###### Definition 2.1 .

(Strict local Nash equilibrium) A strategy $({\mathbf{x}^{*}},{\mathbf{y}^{*}})\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ is a strict local Nash equilibrium of Game 1, if

$$ $f(\mathbf{x}^{*},\mathbf{y})<f(\mathbf{x}^{*},\mathbf{y}^{*})<f(\mathbf{x}, \mathbf{y}^{*}),$ (1) $$

for all $\mathbf{x}$ and $\mathbf{y}$ in feasible neighborhoods of ${\mathbf{x}^{*}}$ and ${\mathbf{y}^{*}}$ respectively.

Under the smoothness assumption of Game 1, defining first-order and second-order equilibrium conditions can help identify whether a point is a local Nash equilibrium [ratliff2016characterization]. For the unconstrained setting, any point that satisfies the conditions below is said to be a differential Nash equilibrium and is guaranteed to be a strict local Nash equilibrium.

###### Definition 2.2 .

(Sufficient conditions for strict local Nash equilibrium) A strategy $({\mathbf{x}^{*}},{\mathbf{y}^{*}})\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ is a differential Nash equilibrium (and thus, a strict local Nash equilibrium) of Game 1 when $\mathcal{X}$ is $\mathbb{R}^{n}$ and $\mathcal{Y}$ is $\mathbb{R}^{m}$, if

$$ $\begin{split}\nabla_{\mathbf{x}}f(\mathbf{x}^{*},\mathbf{y}^{*})=0,&\quad \nabla_{\mathbf{y}}f(\mathbf{x}^{*},\mathbf{y}^{*})=0\\ \nabla^{2}_{\mathbf{x}\mathbf{x}}f(\mathbf{x}^{*},\mathbf{y}^{*})\succ 0,& \quad\nabla^{2}_{\mathbf{y}\mathbf{y}}f(\mathbf{x}^{*},\mathbf{y}^{*})\prec 0. \end{split}$ (2) $$

We now discuss the constrained version of Game 1. This paper allows the constrained setting to have coupled constraints. In the presence of coupling, the Nash equilibrium sought is a generalized Nash equilibrium.

###### Definition 2.3 .

(Local generalized Nash equilibrium) Assume the set $\mathcal{G}$ is convex. A strategy $({\mathbf{x}^{*}},{\mathbf{y}^{*}})\in\mathcal{G}$ is a local generalized Nash equilibrium of Game 1 if

$$ $\begin{split}f(\mathbf{x}^{*},\mathbf{y}^{*})&\leq f(\mathbf{x},\mathbf{y}^{*} )\,\forall\,(\mathbf{x},\mathbf{y}^{*})\in\mathcal{G}\textnormal{ in a neighborhood around }(\mathbf{x}^{*},\mathbf{y}^{*})\\ f(\mathbf{x}^{*},\mathbf{y}^{*})&\geq f(\mathbf{x}^{*},\mathbf{y})\,\forall\,( \mathbf{x}^{*},\mathbf{y})\in\mathcal{G}\textnormal{ in a neighborhood around }(\mathbf{x}^{*},\mathbf{y}^{*}).\end{split}$ (3) $$

The optimality conditions of generalized Nash equilibria in the above-mentioned settings are well studied [facchinei2010generalized, facchinei2010penalty]. Though a standard treatment would involve defining the Karush-Kuhn-Tucker conditions for Game 1, for our purpose, the following conditions are sufficient for a point to be a local generalized Nash equilibrium.

###### Definition 2.4 .

(Sufficient conditions for local generalized Nash equilibrium) Assume the set $\mathcal{G}$ is convex. Let $\partial\mathcal{G}$ denote the set of boundary points of $\mathcal{G}$ and let $\mathcal{N}(\mathbf{x},\mathbf{y})$ denote a neighbourhood around $(\mathbf{x},\mathbf{y})$. Then:

- •
If for a strategy $(\mathbf{x}^{*},\mathbf{y}^{*})\in\mathcal{G}$,
$\begin{split}\nabla_{\mathbf{x}}f(\mathbf{x}^{*},\mathbf{y}^{*})=0,&\quad
\nabla_{\mathbf{y}}f(\mathbf{x}^{*},\mathbf{y}^{*})=0\text{ and}\\
\nabla^{2}_{\mathbf{x}\mathbf{x}}f(\mathbf{x}^{*},\mathbf{y}^{*})\succ 0,&
\quad\nabla^{2}_{\mathbf{y}\mathbf{y}}f(\mathbf{x}^{*},\mathbf{y}^{*})\prec 0,
\end{split}$
then $(\mathbf{x}^{*},\mathbf{y}^{*})$ is a *strict* local generalized Nash equilibrium of Game 1.
- •
If for a strategy $(\mathbf{x}^{*},\mathbf{y}^{*})\in\partial\mathcal{G}$
$\left(\begin{bmatrix}\mathbf{x}\\
\mathbf{y}\end{bmatrix}-\begin{bmatrix}\mathbf{x}^{*}\\
\mathbf{y}^{*}\end{bmatrix}\right)^{\top}\begin{bmatrix}\nabla_{\mathbf{x}}f(
\mathbf{x}^{*},\mathbf{y}^{*})\\
-\nabla_{\mathbf{y}}f(\mathbf{x}^{*},\mathbf{y}^{*})\end{bmatrix}>0\,\,\forall
\,(\mathbf{x},\mathbf{y})\in\mathcal{G}/(\mathbf{x}^{*},\mathbf{y}^{*})\cap
\mathcal{N}(\mathbf{x}^{*},\mathbf{y}^{*})\,$
then $(\mathbf{x}^{*},\mathbf{y}^{*})$ is a *strict* local generalized Nash equilibrium of Game 1. The strictness is lost if the inequality can hold with equality.

We now describe some concepts from dynamical system theory that determine whether an algorithm can converge to a local Nash equilibrium.

###### Definition 2.1 .

###### Definition 2.2 .

###### Definition 2.3 .

###### Definition 2.4 .

### 2.2 A Dynamical Systems Perspective

We illustrate how considerations of dynamical system theory are naturally motivated in our work through the example of GDA. We define:

$$ $\omega(\mathbf{z}):=\begin{bmatrix}\nabla_{\mathbf{x}}f(\mathbf{x},\mathbf{y}) \\ -\nabla_{\mathbf{y}}f(\mathbf{x},\mathbf{y})\end{bmatrix},\quad J(\mathbf{z}): =\nabla_{\mathbf{z}}\omega(\mathbf{z})=\begin{bmatrix}\nabla^{2}_{\mathbf{x} \mathbf{x}}f(\mathbf{x},\mathbf{y})&\nabla^{2}_{\mathbf{x}\mathbf{y}}f(\mathbf {x},\mathbf{y})\\ -\nabla^{2}_{\mathbf{y}\mathbf{x}}f(\mathbf{x},\mathbf{y})&-\nabla^{2}_{ \mathbf{y}\mathbf{y}}f(\mathbf{x},\mathbf{y})\end{bmatrix}.$ (4) $$

For some stepsize $\gamma$, the GDA update for Game 1 for any iteration $k$ can thus be written as

$$ $\mathbf{z}_{k+1}=g_{\mathrm{GDA}}(\mathbf{z}_{k}):=\mathbf{z}_{k}-\gamma\omega (\mathbf{z}_{k}).$ (5) $$

Equation Equation 5 can be viewed as a discrete-time dynamical system. We may also consider the limiting ordinary differential equation of eq. 5, obtained by taking infinitely small $\gamma$, which leads to a continuous-time dynamical system

$$ $\dot{\mathbf{z}}=-\omega(\mathbf{z}).$ (6) $$

Note that $-J(\mathbf{z})$ is the Jacobian of the continuous-time dynamical system in eq. 6. We now introduce concepts we will build upon to comment on the behavior of any algorithm used to solve Game 1.

###### Definition 2.5 .

(Critical point) Given a continuous-time dynamical system $\dot{\mathbf{z}}=-h_{c}(\mathbf{z})$, $\mathbf{z}\in\mathbb{R}^{n+m}$ is a critical point of $h_{c}$ if $h_{c}(\mathbf{z})=0$. Further, if for a critical point $\mathbf{z}$, $\lambda\neq 0\,\,\forall\,\,\lambda\in\mathrm{spec}(\nabla_{\mathbf{z}}h_{c}(
\mathbf{z}))$, then $\mathbf{z}$ is called a hyperbolic critical point.

We can also define a similar concept for the discrete-time dynamical system counterpart.

###### Definition 2.6 .

(Fixed point) Given a discrete-time dynamical system $\mathbf{z}_{k+1}=h_{d}(\mathbf{z}_{k}),k\geq 0$, $\mathbf{z}\in\mathbb{R}^{n+m}$ is a fixed point of $h_{d}$ if $h_{d}(\mathbf{z})=\mathbf{z}$.

Out of the various critical and fixed point types, we are interested in locally asymptotically stable equilibria (LASE) because they are the only locally exponentially attractive hyperbolic points under the dynamics flow. This means that any dynamical system that starts close enough to a LASE point will converge to that point.

###### Definition 2.7 .

(Continuous-time LASE) A critical point $\mathbf{z}^{*}\in\mathbb{R}^{n+m}$ of $h_{c}$ is a LASE of the continuous-time dynamics $\dot{\mathbf{z}}=-h_{c}(\mathbf{z})$ if $\mathrm{Re}(\lambda)>0\,\,\forall\,\,\lambda\in\mathrm{spec}(\nabla_{\mathbf{z
}}h_{c}(\mathbf{z}^{*}))$.

###### Definition 2.8 .

(Discrete-time LASE) A fixed point $\mathbf{z}^{*}\in\mathbb{R}^{n+m}$ of $h_{d}$ is a LASE of the discrete-time dynamics $\mathbf{z}_{k+1}=h_{d}(\mathbf{z}_{k}),k\geq 0$ if $\rho(\nabla_{\mathbf{z}}h_{d}(\mathbf{z}^{*}))<1$, where $\rho(A)$ denotes the spectral radius of some matrix $A$.

###### Definition 2.5 .

###### Definition 2.6 .

###### Definition 2.7 .

###### Definition 2.8 .

### 2.3 Motivation: Limiting behavior of GDA

To motivate our work, we provide an overview of key results that analyze how GDA performs when applied to Game 1 [balduzzi2018mechanics, mazumdar2019finding, mazumdar2020gradient]. If GDA converges to a hyperbolic point $\mathbf{z}_{\mathrm{GDA}}$, GDA must have converged to a LASE. Thus, from definition 2.7,

$$ $\mathrm{Re}(\lambda)>0\,\,\forall\,\,\lambda\in\mathrm{spec}\Bigg{(} \underbrace{\begin{bmatrix}\nabla^{2}_{\mathbf{x}\mathbf{x}}f(\mathbf{x}_{ \mathrm{GDA}},\mathbf{y}_{\mathrm{GDA}})&\nabla^{2}_{\mathbf{x}\mathbf{y}}f( \mathbf{x}_{\mathrm{GDA}},\mathbf{y}_{\mathrm{GDA}})\\ -\nabla^{2}_{\mathbf{y}\mathbf{x}}f(\mathbf{x}_{\mathrm{GDA}},\mathbf{y}_{ \mathrm{GDA}})&-\nabla^{2}_{\mathbf{y}\mathbf{y}}f(\mathbf{x}_{\mathrm{GDA}}, \mathbf{y}_{\mathrm{GDA}})\end{bmatrix}}_{J(\mathbf{z}_{\mathrm{GDA}})}\Bigg{)}.$ (7) $$

Clearly, if $\mathbf{z}_{\mathrm{GDA}}$ happens to be a strict local Nash equilibrium, from eq. 4, we know that $\nabla^{2}_{\mathbf{x}\mathbf{x}}f(\mathbf{x}_{\mathrm{GDA}},\mathbf{y}_{
\mathrm{GDA}})\succ 0$ and $\nabla^{2}_{\mathbf{y}\mathbf{y}}f(\mathbf{x}_{\mathrm{GDA}},\mathbf{y}_{
\mathrm{GDA}})\prec 0$. Hence, from definition 2.7, it is clear that *all* strict local Nash equilibria of Game 1 are LASE of the GDA dynamics. However, the converse cannot be guaranteed, and thus, a LASE point to which GDA converges may *not* be a local Nash equilibrium.

Let us further examine the structure of $J$:

$$ $J(\mathbf{z})=\begin{bmatrix}A&B\\ -B^{\top}&D\end{bmatrix},\forall\,\,\mathbf{z}\in\mathbb{R}^{n+m}.$ (8) $$

Only two previous works, LSS [mazumdar2019finding] and CESP [adolphs2019local], leverage this structure and propose dynamical systems that have *only* local Nash equilibria as their LASE.
However, the convergence rates of these methods have not been analyzed.
Further, neither of these methods discusses the constrained case, which arises in many practical situations.

This motivates us to develop a novel second-order method with a dynamical system that guarantees that only local Nash equilibria constitute its LASE points, generalizes to the constrained settings, and has an established convergence rate.

## 3 Our Method and Main Results

We are now ready to show our main results. We begin with the unconstrained setting and then move to the constrained setting. All proofs are given in Appendix A.

### 3.1 Unconstrained Setting

We list the common assumptions we make for the entire unconstrained case below, and we discuss their validity in Appendix B.

###### Assumption 1 .

The objective function $f\in\mathcal{C}^{3}$.

###### Assumption 2 .

$J(\mathbf{z}),\nabla^{2}_{\mathbf{x}\mathbf{x}}f(\mathbf{x},\mathbf{y}),\nabla
^{2}_{\mathbf{y}\mathbf{y}}f(\mathbf{x},\mathbf{y})$ are invertible at all $\mathbf{z}$ where $\omega(\mathbf{z})=0$.

###### Assumption 3 .

$\omega(\mathbf{z})$ does not belong to the null space of $J(\mathbf{z})^{\top}$, for all $\mathbf{z}\in\mathbb{R}^{n+m}$.

###### Assumption 4 .

$\omega$ is $L_{\omega}$-Lipschitz, and $J$ is $L_{J}$-Lipschitz.

Motivation. We first introduce a continuous-time dynamical system that employs second-order derivative information, for which we can establish desirable properties and which motivates our main method. Consider the system:

$$ $\dot{\mathbf{z}}=-g_{c}(\mathbf{z})=-\left[J(\mathbf{z})^{\top}J(\mathbf{z}) \left(J(\mathbf{z})+J(\mathbf{z})^{\top}\right)+E_{c}(\mathbf{z})\right]^{-1}J (\mathbf{z})^{\top}\omega(\mathbf{z}),$ (9) $$

where $E_{c}(\mathbf{z})$ is a regularization matrix chosen such that $J(\mathbf{z})^{\top}J(\mathbf{z})\left(J(\mathbf{z})+J(\mathbf{z})^{\top}
\right)+E_{c}(\mathbf{z})$ is invertible, and $\omega(\mathbf{z})=0\implies E_{c}(\mathbf{z})=0$.
Under assumptions 1, 2, 3, and 4 all solutions of eq. 9 converge to a strict local Nash equilibrium in the unconstrained setting of Game 1. This is because strict local Nash equilibria of Game 1 are the *only* LASE points of eq. 9. To prove this, we first show that critical points of $g_{c}$ and $\omega(\mathbf{z})$ are the same.

###### Lemma 1 .

Under Assumptions 1, 2, 3, and 4, the critical points of $g_{c}$ are exactly the critical points of the GDA dynamics $\dot{\mathbf{z}}=-\omega(\mathbf{z})$.

Lemma 1 establishes that at every LASE $\mathbf{z}$ of eq. 9, $\omega(\mathbf{z})=0$. This helps us to prove that eq. 9 converges to only a strict local Nash equilibrium.

###### Theorem 1 .

Under Assumptions 1, 2, 3, and 4, $\mathbf{z}$ is a LASE point of $\dot{\mathbf{z}}=-g_{c}(\mathbf{z})$ if and only if $\mathbf{z}$ is a strict local Nash equilibrium of Game 1.

###### Remark 1 .

(Avoiding rotational instability) It is well documented that oscillations around equilibria are caused if the Jacobian of the gradient dynamics has eigenvalues with dominant imaginary parts near equilibria [mescheder2017numerics, balduzzi2018mechanics, gidel2019negative, mazumdar2019finding, Wang*2020On]. Corollary 1 establishes that this cannot happen for the dynamics eq. 9.

###### Corollary 1 .

Under Assumptions 1, 2, 3, and 4, if $\mathbf{z}$ is a strict local Nash equilbrium of $g_{c}$, then the Jacobian $\nabla g_{c}$ has only real eigenvalues at $\mathbf{z}$.

###### Assumption 1 .

###### Assumption 2 .

###### Assumption 3 .

###### Assumption 4 .

###### Lemma 1 .

###### Theorem 1 .

###### Remark 1 .

###### Corollary 1 .

##### Practical Considerations.

Although the continuous-time dynamical system we introduce in eq. 9 has desirable theoretical properties, it is not yet a practical algorithm that can solve Game 1. To solve Game 1, we require a discrete-time dynamical system. Inspired from eq. 9, we propose Discrete-time Nash Dynamics (DND):

$$ $\begin{split}\mathbf{z}_{k+1}&=g_{d}(\mathbf{z}_{k})\\ &=\mathbf{z}_{k}-\alpha_{k}\left(\left[J(\mathbf{z}_{k})^{\top}J(\mathbf{z}_{k })\left(J(\mathbf{z}_{k})+J(\mathbf{z}_{k})^{\top}+\beta(\mathbf{z}_{k})\right )+E(\mathbf{z}_{k})\right]^{-1}\right)J(\mathbf{z}_{k})^{\top}\omega(\mathbf{z }_{k}).\end{split}$ (10) $$

Regularization $E(\mathbf{z}_{k})$ is chosen to maintain invertibility in eq. 10 and adheres to the condition that $\omega(\mathbf{z}_{k})=0\implies E(\mathbf{z}_{k})=0$. In contrast to the continuous-time system $g_{c}$ in eq. 9, DND in eq. 10 contains an extra regularization term $\beta(\mathbf{z}_{k})$. Adding $\beta(\mathbf{z}_{k})$ guarantees the stability of eq. 10 in accordance with definition 2.8, and is given by

$$ $\beta(\mathbf{z})=\begin{bmatrix}\mathbbm{1}_{\{\lambda_{\mathbf{x}}>0\}}(b_{ \mathbf{x}})I&0\\ 0&\mathbbm{1}_{\{\lambda_{\mathbf{y}}<0\}}(b_{\mathbf{y}})I\end{bmatrix},$ (11) $$

where $\lambda_{\mathbf{x}}$ and $\lambda_{\mathbf{y}}$ denote the minimum and maximum eigenvalues of $\nabla^{2}_{\mathbf{x}\mathbf{x}}f(\mathbf{x},\mathbf{y})$ and $\nabla^{2}_{\mathbf{y}\mathbf{y}}f(\mathbf{x},\mathbf{y})$ respectively. These eigenvalues can be found through computations involving Hessian-vector products, which can be made as efficient as gradient evaluations [pearlmutter1994fast, lanczos1950iteration]. The terms $b_{\mathbf{x}}$ and $b_{\mathbf{y}}$ can be taken to be any constants as long as $b_{\mathbf{x}}>\nicefrac{{1}}{{2}}$ and $b_{\mathbf{y}}<\nicefrac{{-1}}{{2}}$.

$\beta(\mathbf{z})$ is a non-smooth regularization term, but it is differentiable around any fixed point of $\omega$. The following theorem shows that DND inherits all the desirable properties that we established for the continuous-time system $g_{c}$.

###### Theorem 2 .

Under Assumptions 1, 2, 3, and 4, for any $\alpha_{k}\in(0,1]$, DND, with $\beta(\mathbf{z})$ chosen as in eq. 11 satisfies the following:

- 1.
The fixed points of DND are exactly the fixed points of the discrete-time GDA dynamics in eq. 5.
- 2.
$\mathbf{z}$ is a LASE of DND $\iff$ $\mathbf{z}$ is a strict local Nash equilibrium of unconstrained Game 1.
- 3.
If $\mathbf{z}$ is a fixed point of DND, then the Jacobian $\nabla g_{d}$ has only real eigenvalues at $\mathbf{z}$.

We find that DND has a *linear* local convergence rate.

###### Theorem 3 .

Assume that a strict local Nash equilibrium of Game 1 exists. Under Assumptions 1, 2, 3, and 4, if DND converges, it converges to a strict local Nash equilibrium of Game 1. Further, if the step size is chosen as $\alpha_{k}\leq\max\{2|\lambda_{\mathbf{x}}|,2|\lambda_{\mathbf{y}}|\}$ then DND has a linear local convergence rate of

$$ $\lim_{k\rightarrow\infty}\frac{\lVert\mathbf{z}_{k+1}-\mathbf{z}^{*}\rVert}{ \lVert\mathbf{z}_{k}-\mathbf{z}^{*}\rVert}\leq\max\left\{\left(1-\frac{\alpha} {2\tilde{\lambda}_{\mathbf{x}}}\right),\left(1+\frac{\alpha}{2\tilde{\lambda}_ {\mathbf{y}}}\right)\right\}.$ $$

Here, $\alpha$ is the step size at the sequence limit in eq. 10, and $\lambda_{\mathbf{x}},\lambda_{\mathbf{y}}$ refer to the quantities in eq. 11, and $\tilde{\lambda}_{\mathbf{x}}>0,\tilde{\lambda}_{\mathbf{x}}<0$ denote $\lambda_{\mathbf{x}},\lambda_{\mathbf{y}}$ evaluated at the sequence limit.

###### Theorem 2 .

###### Theorem 3 .

##### Can we speed up DND ?

We motivate a modification to eq. 10, which allows for superlinear convergence to a ball-shaped region around a fixed point. If this fixed point is a LASE (and therefore also a local Nash equilibrium), the modification can achieve rapid convergence to a small neighborhood of this local Nash point.
The modification retains desirable stability guarantees and escapes the ball if the fixed point is not a LASE.
The radius of the ball can be treated as a hyperparameter and tuned for good performance.

##### Modified discrete-time system.

We call the modified method Second Order Nash Dynamics (SecOND ), which is given by

$$ $\mathbf{z}_{k+1}=\begin{cases}z_{k}-\alpha_{k}\left(S(\mathbf{z}_{k})\right)^{ -1}J(\mathbf{z}_{k})^{\top}\omega(\mathbf{z}_{k}),&\lVert\mathbf{z}_{k}- \mathbf{z}_{k-1}\rVert>\epsilon\\ g_{d}(\mathbf{z}_{k}),&\mathrm{else.}\end{cases}$ (12) $$

where $\epsilon>0$ is a user-specified constant, the matrix $S(\mathbf{z}_{k})\succ 0$ and can be derived from modifying the off-diagonal terms of $J(\mathbf{z}_{k})^{\top}J(\mathbf{z}_{k})\left(J(\mathbf{z}_{k})+J(\mathbf{z}_
{k})^{\top}+\beta(\mathbf{z})\right)$ with an appropriate $E(\mathbf{z}_{k})$ in eq. 10. We define such a choice in Appendix C.

##### Reinterpretation as a Gauss-Newton method far from fixed points.

Consider the problem

$$ $\min_{\mathbf{z}\in\mathbb{R}^{n+m}}\underbrace{\frac{1}{2}\|\omega(\mathbf{z} )\|^{2}_{2}}_{l(\mathbf{z})}.$ (13) $$

We observe that $\nabla_{\mathbf{z}}l(\mathbf{z})=J(\mathbf{z})^{\top}\omega(\mathbf{z})$. For $\|\mathbf{z}_{k}-\mathbf{z}_{k-1}\|>\epsilon$, we have the system $\mathbf{z}_{k+1}=\mathbf{z}_{k}-(S(\mathbf{z}_{k}))^{-1}\nabla_{\mathbf{z}}l(
\mathbf{z}),$ with $S(\mathbf{z}_{k})\succ 0$, which is a modified Gauss-Newton algorithm for solving eq. 13. By choosing $S(\mathbf{z}_{k})\approx J(\mathbf{z}_{k})^{\top}J(\mathbf{z}_{k})$ (see Appendix C), if the Gauss-Newton system converges to a fixed point $\mathbf{z}_{c}$, we can be guaranteed a *superlinear rate of convergence to that point*.
Moreover, whenever $\|\mathbf{z}_{k}-\mathbf{z}_{k-1}\|>\epsilon$, we may choose step size $\alpha_{k}$ according to any standard line search rule from nonlinear programming [nocedal1999numerical, bertsekas1997nonlinear].
For example, in our implementation, we choose a backtracking line search with the Armijo condition [armijo1966minimization] and choose an $\alpha_{k}$ for some $c\in(0,1)$ such that

$$ $l(\mathbf{z}_{k})-l(\mathbf{z}_{k+1})\geq c\alpha_{k}\omega(\mathbf{z}_{k})^{ \top}J(\mathbf{z}_{k})(S(\mathbf{z}_{k}))^{-1}J(\mathbf{z}_{k})^{\top}\omega( \mathbf{z}_{k}).$ (14) $$

Based on SecOND , we construct Algorithm 1, which converges superlinearly toward the first critical point it encounters, and switches to DND when it is close enough to that point.
If the critical point satisfies the strict local Nash equilibrium sufficiency conditions given in Definition (2.2), SecOND will have reached the point faster than DND would have from the same initialization. If the fixed point does not satisfy strict local Nash conditions, the switch to DND dynamics ensures that iterates escape, and avoids convergence to the spurious fixed point.
More sophisticated variants which allow for switching back and forth multiple times can also be considered.

Figure: Algorithm 1 Second Order Nash Dynamics (SecOND)

###### Theorem 4 .

Under Assumptions 1, 2, 3, and 4, $\mathbf{z}$ is a LASE of SecOND (Algorithm 1) if and only if $\mathbf{z}$ is a strict local Nash equilibrium of Game 1. Further, assume that a strict local Nash equilibrium of Game 1 exists and let $\mathbf{z}_{c}$ be the first critical point to which Algorithm 1 comes near to. If $S(\mathbf{z}_{k})\approx J(\mathbf{z}_{k})^{\top}J(\mathbf{z}_{k})$ (see Appendix C), then Algorithm 1 approaches $\mathbf{z}_{c}$ superlinearly with a rate

$$ $\lVert\mathbf{z}_{k+1}-\mathbf{z}_{c}\rVert\leq L_{\omega}L_{J}M\lVert\mathbf{ z}_{k}-\mathbf{z}_{c}\rVert^{2},\forall~{}k=0,1,\dots.$ $$

Here $M=\sup_{z\in\tilde{\mathcal{B}}}\lVert S(\mathbf{z})^{-1}\rVert$, where $\tilde{\mathcal{B}}$ is the smallest ball centered at $\mathbf{z}_{c}$ which contains $\mathbf{z}_{0}$.

Furthermore, if Algorithm 1 converges, it converges to a strict local Nash equilibrium of Game 1.

Theorem 4 establishes that SecOND inherits the desirable stability properties of DND, while being faster than DND in approaching a critical point.

###### Theorem 4 .

### 3.2 Constrained Setting

##### Notation.

$\Pi_{\mathcal{Q}}[\mathbf{p}]$ denotes the Euclidean projection of some vector $\mathbf{p}$ onto some set $\mathcal{Q}$. $\mathrm{proj}_{\mathbf{a}}(\mathbf{b})$ denotes the Euclidean projection of a vector $\mathbf{b}$ onto another vector $\mathbf{a}$. $\mathrm{int\,}\mathcal{G}\textnormal{ }$and $\partial\mathcal{G}\textnormal{ }$denote the interior and boundary of $\mathcal{G}$ respectively.

Intuitively, any local generalized Nash equilibrium in $\mathrm{int\,}\mathcal{G}\textnormal{ }$is actually also a strict local Nash equilibrium of the unconstrained game. Therefore, if the Euclidean projections of the DND iterates converge to a point in $\mathrm{int\,}\mathcal{G}$, this point must be a local generalized Nash equilibrium. Further, if a step taken by DND at a point $\mathbf{z}$ in $\partial\mathcal{G}\textnormal{ }$is parallel to $-\omega(\mathbf{z})$, then, from definition 2.4, $\mathbf{z}$ is a local Generalized Nash equilibrium as well.

##### Algorithm for Constrained Setting.

Based on the above discussion, we construct Second-order Constrained Nash Dynamics (SeCoND), given in Algorithm 2, for solving a constrained Game 1. SeCoND has the property that if it converges, it converges to a local Generalized Nash equilibrium that follows definition 2.4.
If desired, Algorithm 2 convergence can be accelerated via a Gauss-Newton approach analogous to eq. 12.

###### Assumption 5 .

The set $\mathcal{G}$ is convex.

###### Theorem 5 .

Let Assumptions 1, 2, 3, 4, and 5 hold, and let $\omega(\mathbf{z})\neq 0~{}\forall~{}\mathbf{z}\in\partial G$. Then, if SeCoND (Algorithm 2) converges to a point $\mathbf{z}$:

- 1.
If $\mathbf{z}\in\mathrm{int}G$, then $\mathbf{z}$ is a strict local generalized Nash equilibrium.
- 2.
If $\mathbf{z}\in\partial G$, then $\mathbf{z}$ is a local generalized Nash equilibrium (not necessarily strict).

Figure: Algorithm 2 Second-order Constrained Nash Dynamics (SeCoND)

###### Assumption 5 .

###### Theorem 5 .

## 4 Experiments

We now investigate how well the theoretical properties of our algorithms transfer to practical problems. Our main aims are: (i) to compare the performance of SecOND with previous related work in unconstrained, nonconvex-nonconcave settings, (ii) to determine if modifications made to DND in SecOND are beneficial, (iii) to test whether SeCoND converges to a local generalized Nash equilibrium in the constrained setting. All details of the experimental setup are included in Appendix D.

### 4.1 Two-Dimensional Toy Example

We consider the function

$$ $f(x,y)=e^{-0.01(x^{2}+y^{2})}((0.3x^{2}+y)^{2}+(0.5y^{2}+x)^{2}),\,x,y\in \mathbb{R}.$ $$

This function is nonconvex-nonconcave, and the unconstrained version of Game 1 has three local Nash equilibria, while the GDA dynamical system eq. 6 has 4 LASE points for this function.

##### Baselines.

In this experiment, we tested the performance of SecOND (Algorithm 1) against three baselines: DND, gradient descent-ascent (GDA), and local symplectic surgery (LSS) [mazumdar2019finding], on 10000 random initializations.

Figure: (a) Violin plot of the difference in iterations taken between SecOND and each baseline method (lower is better). SecOND converges faster than baselines for the unconstrained Game 1. Dots represent outliers, (see Section D.1.2).
Refer to caption: extracted/5900128/Images/UnconstrainedToy.png

##### Does SecOND provide faster convergence than baselines?

Figure 1(a) shows the difference in the number of iterations taken to converge within a fixed tolerance by SecOND and each respective baseline. SecOND consistently converged more rapidly than LSS, achieving a still greater performance improvement than GDA.
Finally, we note that we could not compare to the CESP method [adolphs2019local], because it could not reliably converge in our experiments (see Section D.1.1). An additional experiment investigating convergence of all algorithms to a local Nash equilibrium is in Section D.1.3.

##### Does SecOND perform better than DND ?

From Figure 1(a), we observe that SecOND performed similarly to DND in this numerical example. DND outperformed SecOND in some instances, which occurred when SecOND initially went to the neighborhood of an undesirable critical point, at which the quantity $\|\omega(\mathbf{z})\|^{2}_{2}\approx 0$. In such cases, SecOND had to correct its course to go to the desirable fixed points. This made it converge slower than DND, which went to the desirable fixed points in the first place. In the cases when SecOND rapidly approaches a desirable critical point, SecOND converged much faster than DND. This shows that the modification made to DND in SecOND can indeed be advantageous.

##### Does SeCoND converge to a local generalized Nash equilibrium?

We tested SeCoND (Algorithm 2) in this toy setting by including a constraint of the form $(x+10.5)^{2}+(y+5)^{2}\leq 25$,
and found that SeCoND successfully converges to a local generalized Nash equilibrium. As seen in Figure 1(b), SeCoND initially follows DND while iterates remain in the interior of the feasible set. However, after hitting the boundary, SeCoND remains on the boundary before returning to the interior and converging to the same local (generalized) Nash equilibrium as DND. Figure 1(c) is representative of the geometry across the portion where SeCoND remains on the boundary. Because $-\omega(\mathbf{z})$ is not parallel to the constraint gradient here, SeCoND eventually returns to the interior.

Figure: Figure 2: SecOND converges rapidly and to a more accurate solution for a GAN training problem.
Refer to caption: extracted/5900128/Images/gan_comparison.png

### 4.2 Generative Adversarial Network (GAN)

Next, we consider a larger-scale test problem in which $\omega(\mathbf{z})$ is computed stochastically (i.e., via sampling minibatches of data).
To this end, we evaluated GDA, LSS, and SecOND on a GAN training problem where the generator must fit a 1D mixture of Gaussians with 4 mixture components. The distribution that each algorithm learned at different training iterations is plotted in Figure 2. GDA suffered mode collapse early on and only fit two out of the four modes. Both LSS and SecOND successfully found all four modes of the problem.
While LSS initially seems to converge rapidly, continued training degrades performance.
Over time, SecOND outperformed LSS and fit the ground truth distribution more closely by 12000 iterations.

## 5 Conclusion, Limitations, and Future Work

We have provided algorithms that provably converge to only local Nash equilibria in smooth, possibly nonconvex-nonconcave, two-player zero-sum games in the unconstrained (DND, SecOND) and convex-constrained (SeCoND) settings. We have shown that DND has a linear local convergence rate and that SecOND approaches a neighborhood around a fixed point superlinearly. In contrast, the most closely related existing approaches for this setting have no established convergence rates. Empirical results demonstrate that DND and SecOND outperformed previous related works in two test problems.

##### Limitations and Future Work.

There are three key limitations of the proposed method. (i) All approaches in this paper require second-order information, which can be prohibitively expensive to obtain or compute in high-dimensional scenarios. Unfortunately, the fundamental links this problem shares with dynamical system theory necessitate second-order information to provide convergence guarantees. (ii) Like other approaches [mazumdar2019finding], we require Assumption 3 in order to ensure that the critical points of the dynamics we introduce coincide with first-order local Nash points. Finally, (iii) as in other work on zero-sum Nash games [adolphs2019local, mazumdar2019finding, mazumdar2020gradient], we can only provide local convergence analysis, and cannot ensure that the dynamics globally converge (even if local Nash points do exist). Addressing this limitation is a key direction of future work.
Future work should also aim to relax Assumption 3, and
use algorithms introduced in this paper as building blocks for solving dynamic zero-sum games with simultaneous decision-making occurring across multiple time stages.

## Acknowledgments and Disclosure of Funding

DISTRIBUTION STATEMENT A. Approved for public release. Distribution is unlimited.

This material is based upon work supported by the Under Secretary of Defense for Research and Engineering under Air Force Contract No. FA8702-15-D-0001. Any opinions, findings, conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Under Secretary of Defense for Research and Engineering.

© 2024 Massachusetts Institute of Technology.

Delivered to the U.S. Government with Unlimited Rights, as defined in DFARS Part 252.227-7013 or 7014 (Feb 2014). Notwithstanding any copyright notice, U.S. Government rights in this work are defined by DFARS 252.227-7013 or DFARS 252.227-7014 as detailed above. Use of this work other than as specifically authorized by the U.S. Government may violate any copyrights that exist in this work.

This work also acknowledges funding from the following grants: Center of Excellence (AFOSR FA9550-19-1-0169) and Attack-Resilient Mission Planning for Swarms (ONR N00014-22-1-2703).

## Appendix A Proofs

Lemma 1. Under Assumptions 1, 2, 3, and 4, the critical points of $g_{c}$ are exactly the critical points of the GDA dynamics $\dot{\mathbf{z}}=-\omega(\mathbf{z})$.

###### Proof.

$(\implies)$ Clearly,

$$ $\omega(\mathbf{z})=0\implies g_{c}(\mathbf{z})=0.$ $$

$(\impliedby)$
Now assume that $\mathbf{z}$ is a critical point of $g_{c}$ such that $\omega(\mathbf{z})\neq 0$. In this case, due to the choice of our regularization $E_{c}(\mathbf{z})$, $g_{c}(\mathbf{z})$ can be thought of as $g_{c}(\mathbf{z})=M(\mathbf{z})\omega(\mathbf{z}),\text{ where }M(\mathbf{z})$ is full rank. Thus,

$$ $g_{c}(\mathbf{z})=0\implies M(z)\omega(\mathbf{z})=0\implies\omega(\mathbf{z}) =0,$ $$

which is a contradiction. Hence, $g_{c}(\mathbf{z})=0\iff\omega(\mathbf{z})=0$.
∎

Theorem 1. Under Assumptions 1, 2, 3, and 4, $\mathbf{z}$ is a LASE point of $\dot{\mathbf{z}}=-g_{c}(\mathbf{z})$ if and only if $\mathbf{z}$ is a strict local Nash equilibrium of Game 1.

###### Proof.

$(\implies)$ As all LASE points of continuous-time dynamics are also critical points, for any LASE point $\mathbf{z}=(\mathbf{x}^{\top},\mathbf{y}^{\top})^{\top},\,\omega(\mathbf{z})=0$. Thus the Jacobian of $g_{c}$ at $\mathbf{z}$ becomes

$$ $\begin{split}\nabla g_{c}(\mathbf{z})&=\left[J(\mathbf{z})^{\top}J(\mathbf{z}) (J(\mathbf{z})+J(\mathbf{z})^{\top})\right]^{-1}J(\mathbf{z})^{\top}J(\mathbf{ z})=(J(\mathbf{z})+J(\mathbf{z})^{\top})^{-1}\\ &=H(\mathbf{z}):=\begin{bmatrix}\frac{1}{2}\left(\nabla^{2}_{\mathbf{x}\mathbf {x}}f(\mathbf{x},\mathbf{y})\right)^{-1}&0\\ 0&-\frac{1}{2}\left(\nabla^{2}_{\mathbf{y}\mathbf{y}}f(\mathbf{x},\mathbf{y}) \right)^{-1}\end{bmatrix}.\end{split}$ (15) $$

From definition 2.7,

$$ $\nabla g_{c}(\mathbf{z})=H(\mathbf{z})\succ 0\implies\nabla^{2}_{\mathbf{x} \mathbf{x}}f(\mathbf{x},\mathbf{y})\succ 0\text{ and }\nabla^{2}_{\mathbf{y} \mathbf{y}}f(\mathbf{x},\mathbf{y})\prec 0,$ $$

which implies that $(\mathbf{x},\mathbf{y})$ is a strict local Nash equilibrium of Game 1 (from definition 2.2).
Thus, every LASE of $\dot{\mathbf{z}}=-g_{c}(\mathbf{z})$ is a strict local Nash equilibrium of eq. Game 1.
$(\impliedby)$ Consider a strict local Nash equilibrium $(\mathbf{x}^{*},\mathbf{y}^{*})$ of Game 1. From definition 2.2, $\nabla^{2}_{\mathbf{x}\mathbf{x}}f(\mathbf{x}^{*},\mathbf{y}^{*})\succ 0,
\nabla^{2}_{\mathbf{y}\mathbf{y}}f(\mathbf{x}^{*},\mathbf{y}^{*})\prec 0$, and $\omega(\mathbf{z}^{*})=0$ where $\mathbf{z}^{*}=({\mathbf{x}^{*}}^{\top},{\mathbf{y}^{*}}^{\top})^{\top}$. Clearly, $H(\mathbf{z}^{*})\succ 0$ and thus $\mathbf{z}^{*}$ is a LASE of eq. 9.
∎

Corollary 1 Under Assumptions 1, 2, 3, and 4, if $\mathbf{z}$ is a strict local Nash equilbrium of $g_{c}$, then the Jacobian $\nabla g_{c}$ has only real eigenvalues at $\mathbf{z}$.

###### Proof.

From theorem 1, $\mathbf{z}$ must also be a LASE, and by extension, a critical point of $g_{c}$. From lemma 1, $\omega(\mathbf{z})=0$. Consider eq. 15. As the inverse Hessians $\left(\nabla^{2}_{\mathbf{x}\mathbf{x}}f(\mathbf{x},\mathbf{y})\right)^{-1}$ and $\left(\nabla^{2}_{\mathbf{y}\mathbf{y}}f(\mathbf{x},\mathbf{y})\right)^{-1}$ are symmetric, $H(\mathbf{z})$ is symmetric. Because $\omega(\mathbf{z})=0$, the Jacobian $\nabla g_{c}(\mathbf{z})=H(\mathbf{z})$, and $H(\mathbf{z})$ only has real eigenvalues due to symmetry.
∎

Theorem 2. Under Assumptions 1, 2, 3, and 4, for any $\alpha_{k}\in(0,1]$, DND, with $\beta(\mathbf{z})$ chosen as in eq. 11 satisfies:

- 1.
The fixed points of DND are exactly the fixed points of the discrete-time GDA dynamics in eq. 5.
- 2.
$\mathbf{z}$ is a LASE point of DND $\iff$ $\mathbf{z}$ is a strict local Nash equilibrium of unconstrained Game 1.
- 3.
If $\mathbf{z}$ is a fixed point of DND, then the Jacobian $\nabla g_{d}$ has only real eigenvalues at $\mathbf{z}$.

###### Proof.

$(1.\implies)$ The fixed points of the discrete GDA dynamics in eq. 5 are critical points of $\omega$, i.e, where $\omega(\mathbf{z})=0$. Clearly,

$$ $\omega(\mathbf{z})=0\implies g_{d}(\mathbf{z})=\mathbf{z}.$ $$

$(1.\impliedby)$
Now assume that $\mathbf{z}$ is a fixed point of $g_{d}$ such that $\omega(\mathbf{z})\neq 0$. In this case, due to the choice of our regularization $E(\mathbf{z})$, $g_{d}(\mathbf{z})$ can be thought of as $g_{d}(\mathbf{z})=\mathbf{z}-\alpha M(\mathbf{z})J(\mathbf{z})^{\top}\omega(
\mathbf{z}),\text{ where }M(\mathbf{z})$ is full rank and $\alpha$ is the step size. Thus,

$$ $g_{d}(\mathbf{z})=\mathbf{z}\implies M(z)J(\mathbf{z})^{\top}\omega(\mathbf{z} )=0\implies\omega(\mathbf{z})=0,$ $$

which is a contradiction. Hence, $g_{d}(\mathbf{z})=\mathbf{z}\iff\omega(\mathbf{z})=0$.
$(2.\implies)$ As all LASE points of discrete-time dynamics are also fixed points, for any LASE point $\mathbf{z}=(\mathbf{x}^{\top},\mathbf{y}^{\top})^{\top},\,\omega(\mathbf{z})=0$. Thus the Jacobian of $g_{d}$ at $\mathbf{z}$ becomes

$$ $\begin{split}\nabla g_{d}(\mathbf{z})&=I_{n+m}-\alpha(J(\mathbf{z})+J(\mathbf{ z})^{\top}+\beta(\mathbf{z}))^{-1}\\ &=\begin{bmatrix}I_{n}-(2\nabla_{\mathbf{x}\mathbf{x}}f+\mathbbm{1}_{\{\lambda _{\mathbf{x}}>0\}}(b_{\mathbf{x}})I)^{-1}&0\\ 0&I_{m}-(-2\nabla_{\mathbf{y}\mathbf{y}}f+\mathbbm{1}_{\{\lambda_{\mathbf{y}}< 0\}}(b_{\mathbf{y}})I)^{-1}\end{bmatrix}\end{split}$ (16) $$

The eigenvalues of $\nabla g_{d}(\mathbf{z})$ are the eigenvalues of $I_{n}-(2\nabla_{\mathbf{x}\mathbf{x}}f+\mathbbm{1}_{\{\lambda_{\mathbf{x}}>0\}
}(b_{\mathbf{x}})I)^{-1}$ and $I_{m}-(-2\nabla_{\mathbf{y}\mathbf{y}}f+\mathbbm{1}_{\{\lambda_{\mathbf{y}}<0
\}}(b_{\mathbf{y}})I)^{-1}$.
For an eigenvalue $\lambda$ of $\nabla_{\mathbf{x}\mathbf{x}}f$, the corresponding eigenvalue of $I_{n}-(2\nabla_{\mathbf{x}\mathbf{x}}f+\mathbbm{1}_{\{\lambda_{\mathbf{x}}>0\}
}(b_{\mathbf{x}})I)^{-1}$ will be

$$ $1-\frac{\alpha}{2\lambda+\mathbbm{1}_{\{\lambda_{\mathbf{x}}>0\}}(b_{\mathbf{x }})}.$ (17) $$

If $\lambda_{\mathbf{x}}$ < 0, eq. 17 becomes

$$ $1-\frac{\alpha}{2\lambda}>1.$ $$

As $\mathbf{z}$ is an LASE point, from definition 2.8, $\rho(\nabla g_{d}(\mathbf{z}))$ < 1. Thus, appendix A shows that $\mathbf{z}$ cannot be a LASE if $\lambda_{\mathbf{x}}<0$. Thus $\mathbf{z}$ is a LASE $\implies\lambda_{\mathbf{x}}>0\implies\nabla_{\mathbf{x}\mathbf{x}}f\succ 0$. A similar argument by analyzing egeinvalues for $I_{m}-(-2\nabla_{\mathbf{y}\mathbf{y}}f+\mathbbm{1}_{\{\lambda_{\mathbf{y}}<0
\}}(b_{\mathbf{y}})I)^{-1}$ shows that $\mathbf{z}$ is a LASE $\implies\lambda_{\mathbf{y}}<0\implies\nabla_{\mathbf{y}\mathbf{y}}f\prec 0$. Thus, from definition 2.2, $z$ is a LASE implies that $\mathbf{z}$ is a strict local Nash equilibrium of eq. Game 1.
$(2.\impliedby)$ Let $\mathbf{z}$ be a strict local Nash equilbrium. Then, $\lambda_{\mathbf{x}}>0,\lambda_{\mathbf{y}}<0$.
Clearly, from appendix A, all eigenvalues of $I_{n}-(2\nabla_{\mathbf{x}\mathbf{x}}f+\mathbbm{1}_{\{\lambda_{\mathbf{x}}>0\}
}(b_{\mathbf{x}})I)^{-1}$ are smaller than 1. Since $\lambda_{\mathbf{x}}>0,\lambda>0$. Also,$b_{\mathbf{x}}>\frac{1}{2},b_{\mathbf{x}}>\frac{\alpha}{2}$, which means that

$$ $1-\frac{\alpha}{2\lambda+b_{\mathbf{x}}}>1-\frac{\alpha}{2\lambda+\frac{\alpha }{2}}>1-\frac{\alpha}{\frac{\alpha}{2}}>-1.$ $$

Thus $\rho(I_{n}-(2\nabla_{\mathbf{x}\mathbf{x}}f+\mathbbm{1}_{\{\lambda_{\mathbf{x}
}>0\}}(b_{\mathbf{x}})I)^{-1})<1$. Similarly, $\rho(I_{m}-(-2\nabla_{\mathbf{y}\mathbf{y}}f+\mathbbm{1}_{\{\lambda_{\mathbf{y
}}<0\}}(b_{\mathbf{y}})I)^{-1})$ is less than 1. Thus, from definition 2.8, $\mathbf{z}$ is also a LASE.
$(3.)$ The Jacobian $\nabla g_{d}$ at any fixed point $\mathbf{z}$ is the same as that given in eq. 16, in which $\nabla g_{d}$ is clearly symmetric. Thus, $\nabla g_{d}$ only has real eigenvalues at a fixed point $\mathbf{z}$.
∎

Theorem 3. Assume that a strict local Nash equilibrium of Game 1 exists. Under Assumptions 1, 2, 3, and 4, if DND converges, it converges to a strict local Nash equilibrium of Game 1. Further, if the step size is chosen as $\alpha_{k}\leq\max\{2|\lambda_{\mathbf{x}}|,2|\lambda_{\mathbf{y}}|\}$ then DND has a linear local convergence rate of

$$ $\lim_{k\rightarrow\infty}\frac{\lVert\mathbf{z}_{k+1}-\mathbf{z}^{*}\rVert}{ \lVert\mathbf{z}_{k}-\mathbf{z}^{*}\rVert}\leq\max\left\{\left(1-\frac{\alpha} {2\tilde{\lambda}_{\mathbf{x}}}\right),\left(1+\frac{\alpha}{2\tilde{\lambda}_ {\mathbf{y}}}\right)\right\}.$ $$

Here, $\alpha$ is the step size at the sequence limit in eq. 10, and $\lambda_{\mathbf{x}},\lambda_{\mathbf{y}}$ refer to the quantities in eq. 11, and $\tilde{\lambda}_{\mathbf{x}}>0,\tilde{\lambda}_{\mathbf{x}}<0$ denote $\lambda_{\mathbf{x}},\lambda_{\mathbf{y}}$ evaluated at the sequence limit.

###### Proof.

Let $\mathbf{z}^{*}$ denote the local Nash equilibrium to which DND converges, and let $J^{\top}J(\mathbf{z})$ denote $J(\mathbf{z})^{\top}J(\mathbf{z})$. We use Taylor’s Theorem [nocedal1999numerical] applied to $\omega$,

$$ $\omega(\mathbf{z}_{k})-\omega(\mathbf{z}^{*})=\int_{0}^{1}J(\mathbf{z}^{*}+t( \mathbf{z}_{k}-\mathbf{z}^{*}))(\mathbf{z}_{k}-\mathbf{z}^{*})dt.$ $$

For large $k$, as $\mathbf{z}_{k}\rightarrow\mathbf{z}^{*}$, $J(\mathbf{z}^{*}+t(\mathbf{z}_{k}-\mathbf{z}^{*}))\approx J(\mathbf{z}_{k})
\forall t\in[0,1]$. Also for large $k$, from our assumptions $\beta=0$ and $E=0$. Thus we get for large k:

$$ $\begin{split}\lVert\mathbf{z}_{k+1}-\mathbf{z}^{*}\rVert=&\lVert\mathbf{z}_{k} -\mathbf{z}^{*}-\alpha_{k}[J(\mathbf{z}_{k})^{\top}J(\mathbf{z}_{k})(J(\mathbf {z}_{k})+J(\mathbf{z}_{k})^{\top})]^{-1}J(\mathbf{z}_{k})^{\top}\omega(\mathbf {z}_{k})\rVert\\ =&\lVert\mathbf{z}_{k}-\mathbf{z}^{*}-\alpha_{k}(J(\mathbf{z}_{k})+J(\mathbf{z }_{k})^{\top})^{-1}J(\mathbf{z}_{k})^{-1}\omega(\mathbf{z}_{k})\rVert\\ =&\lVert\mathbf{z}_{k}-\mathbf{z}^{*}-\alpha_{k}(J(\mathbf{z}_{k})+J(\mathbf{z }_{k})^{\top})^{-1}J(\mathbf{z}_{k})^{-1}(\omega(\mathbf{z}_{k})-\omega( \mathbf{z}^{*}))\rVert\\ =&\lVert\mathbf{z}_{k}-\mathbf{z}^{*}-\alpha_{k}(J(\mathbf{z}_{k})+J(\mathbf{z }_{k})^{\top})^{-1}J(\mathbf{z}_{k})^{-1}\left(\int_{0}^{1}J(\mathbf{z}^{*}+t( \mathbf{z}_{k}-\mathbf{z}^{*}))(\mathbf{z}_{k}-\mathbf{z}^{*})dt\right)\rVert \\ \approx&\lVert\mathbf{z}_{k}-\mathbf{z}^{*}-\alpha_{k}(J(\mathbf{z}_{k})+J( \mathbf{z}_{k})^{\top})^{-1}J(\mathbf{z}_{k})^{-1}J(\mathbf{z}_{k})(\mathbf{z} _{k}-\mathbf{z}^{*})\rVert\\ =&\lVert[I-\alpha_{k}(J(\mathbf{z}_{k})+J(\mathbf{z}_{k})^{\top})^{-1}]( \mathbf{z}_{k}-\mathbf{z}^{*})\rVert\\ \leq&\lVert I-\alpha_{k}(J(\mathbf{z}_{k})+J(\mathbf{z}_{k})^{\top})^{-1} \rVert_{2}\lVert\mathbf{z}_{k}-\mathbf{z}^{*}\rVert\end{split}$ $$

Now, consider the matrix $D_{k}=I-\alpha_{k}(J(\mathbf{z}_{k})+J(\mathbf{z}_{k})^{\top})^{-1}$. From the structure of $J(\mathbf{z}_{k})$ described in eq. 8,

$$ $D_{k}=\begin{bmatrix}I-\frac{\alpha_{k}}{2}(\nabla_{\mathbf{x}\mathbf{x}})^{-1 }&0\\ 0&I+\frac{\alpha_{k}}{2}(\nabla_{\mathbf{y}\mathbf{y}})^{-1}\end{bmatrix}.$ $$

From the properties of $\lVert\cdot\rVert_{2}$ norm,

$$ $\lVert D_{k}\rVert_{2}=\max\left\{\lVert I-\frac{\alpha_{k}}{2}(\nabla_{ \mathbf{x}\mathbf{x}})^{-1}\rVert_{2},\lVert I+\frac{\alpha_{k}}{2}(\nabla_{ \mathbf{y}\mathbf{y}})^{-1}\rVert_{2}\right\}$ $$

Let $\lambda_{\mathbf{x}},\lambda_{y}$ denote the quantities in eq. 11, evaluated at $\mathbf{z}=\mathbf{z}_{k}$. Further, let $\tilde{\lambda}_{\mathbf{x}},\tilde{\lambda}_{y}$ denote $\lambda_{\mathbf{x}},\lambda_{y}$ evaluated at $\lim_{k\rightarrow\infty}\mathbf{z}_{k}$. Then, from Theorem 2, $\tilde{\lambda}_{\mathbf{x}}>0,\tilde{\lambda}_{y}<0$. Thus we can write

$$ $\lim_{k\rightarrow\infty}\lVert D_{k}\rVert_{2}=\max\left\{1-\frac{\alpha}{2 \tilde{\lambda}_{\mathbf{x}}},1+\frac{\alpha}{2\tilde{\lambda}_{y}}\right\}<1~ {}\forall~{}0<\alpha\leq\max\{2|\tilde{\lambda}_{x}|,2|\tilde{\lambda}_{y}|\}$ $$

Thus,

$$ $\lim_{k\rightarrow\infty}\frac{\lVert\mathbf{z}_{k+1}-\mathbf{z}^{*}\rVert}{ \lVert\mathbf{z}_{k}-\mathbf{z}^{*}\rVert}\leq\lim_{k\rightarrow\infty}\lVert D _{k}\rVert_{2}<1$ $$

This proves that DND has a local linear convergence rate when the step size is chosen as described.

∎

Theorem 4. Under Assumptions 1, 2, 3, and 4, $\mathbf{z}$ is a LASE of SecOND (Algorithm 1) if and only if $\mathbf{z}$ is a strict local Nash equilibrium of Game 1. Further, assume that a strict local Nash equilibrium of Game 1 exists and let $\mathbf{z}_{c}$ be the first critical point to which Algorithm 1 comes near to. If $S(\mathbf{z}_{k})\approx J(\mathbf{z}_{k})^{\top}J(\mathbf{z}_{k})$ (see Appendix C), then Algorithm 1 approaches $\mathbf{z}_{c}$ superlinearly with a rate

$$ $\lVert\mathbf{z}_{k+1}-\mathbf{z}_{c}\rVert\leq L_{\omega}L_{J}M\lVert\mathbf{ z}_{k}-\mathbf{z}_{c}\rVert^{2},\forall~{}k=0,1,\dots.$ $$

Here $M=\sup_{z\in\tilde{\mathcal{B}}}\lVert S(\mathbf{z})^{-1}\rVert$, where $\tilde{\mathcal{B}}$ is the smallest ball centered at $\mathbf{z}_{c}$ which contains $\mathbf{z}_{0}$.
Furthermore, if Algorithm 1 converges, it converges to a strict local Nash equilibrium of Game 1.

###### Proof.

First, we show that the fixed points of SecOND and DND are the same.
From eq. 12, any fixed point $\mathbf{z}$ of SecOND must have $\omega(\mathbf{z})=0$, i.e., fixed points $\mathbf{z}$ of algorithm 1 are same as the fixed points of the discrete-time GDA dynamics. Theorem 2 has already established that the fixed points of the discrete GDA dynamics are the same as the fixed points of DND.

From eq. 12, when far away from $\mathbf{z}_{c}$, SecOND satisfies the condition that every step is in a feasible descent direction. Further, using a line search rule like eq. 14 ensures that for every step that SecOND takes far away from $\mathbf{z}_{c}$, the merit function $\|\omega(\mathbf{z})\|^{2}_{2}$ decreases in value. Thus, when $S(\mathbf{z}_{k})\approx J(\mathbf{z}_{k})^{\top}J(\mathbf{z}_{k}),$ SecOND mimics a Gauss-Newton method and from standard nonlinear programming results [bertsekas1997nonlinear, Proposition 1.1.4], reaches the neighborhood of $\mathbf{z}_{c}$ superlinearly. Now, when SecOND reaches this neighborhood, it changes its dynamics to DND, which has already shown to have only local Nash equilibrium points as its LASE points. Clearly, SecOND has the same LASE points as DND once it switches dynamics, and results from Theorem 2 apply and SecOND only converges to a strict local Nash equilibrium. Let us derive the local superlinear rate now. Let $\mathcal{B}_{\delta}(\mathbf{z}_{c})$ denote a ball of radius $\delta$ centered at $\mathbf{z}_{c}$, and assume that $\mathbf{z}_{0}\in\mathcal{B}_{\delta}(\mathbf{z}_{c})$. Let $S(\mathbf{z}_{k})$ be denoted by $S_{k}$. For iteration $k$ when $\lVert\mathbf{z}_{k}-\mathbf{z}_{k-1}\rVert>\epsilon$:

$$ $\begin{split}\|\mathbf{z}_{k+1}-\mathbf{z}^{*}\|=&\|\mathbf{z}_{k}-S_{k}^{-1}J (\mathbf{z}_{k})^{\top}\omega(\mathbf{z}_{k})-\mathbf{z}^{*}\|\\ =&\lVert S_{k}^{-1}(S_{k}(\mathbf{z}_{k}-\mathbf{z}^{*})-J(\mathbf{z}_{k})^{ \top}\omega(\mathbf{z}_{k}))\rVert\\ =&\lVert S_{k}^{-1}\left(S_{k}-J(\mathbf{z}_{k})^{\top}\int^{1}_{0}J(\mathbf{z }^{*}+t(\mathbf{z}_{k}-\mathbf{z}^{*}))dt\right)(\mathbf{z}_{k}-\mathbf{z}^{*} )\rVert\\ =&\lVert S_{k}^{-1}\left(\int^{1}_{0}\left[S_{k}-J(\mathbf{z}_{k})^{\top}J( \mathbf{z}^{*}+t(\mathbf{z}_{k}-\mathbf{z}^{*}))\right]dt\right)(\mathbf{z}_{k }-\mathbf{z}^{*})\rVert\\ \leq&\lVert S_{k}^{-1}\rVert\lVert\left(\int^{1}_{0}\left[S_{k}-J(\mathbf{z}_{ k})^{\top}J(\mathbf{z}^{*}+t(\mathbf{z}_{k}-\mathbf{z}^{*}))\right]dt\right) \rVert\lVert(\mathbf{z}_{k}-\mathbf{z}^{*})\rVert\end{split}$ $$

By choosing $S_{k}=J(\mathbf{z}_{k})^{\top}J(\mathbf{z}_{k})$, and taking $\delta,\epsilon$ to be sufficiently small (and $\epsilon<\delta$), $\lVert\mathbf{z}_{k}-\mathbf{z}^{*}\rVert$ monotonically decreases and the integral term becomes arbitrarily small for any $k$. Also, due to Assumption 4, $J(\mathbf{z})^{\top}J(\mathbf{z})$ is a Lipschitz function with a Lipschitz constant of $2L_{\omega}L_{J}$, thus from the preceding relation,

$$ $\lVert\mathbf{z}_{k+1}-\mathbf{z}^{*}\rVert\leq M\left(\int^{1}_{0}2L_{\omega} L_{J}t\lVert\mathbf{z}_{k}-\mathbf{z}\rVert dt\right)\lVert\mathbf{z}_{k}- \mathbf{z}\rVert=ML_{\omega}L_{J}\lVert\mathbf{z}_{k}-\mathbf{z}\rVert^{2}$ $$

∎

Theorem 5. Under Assumptions 1, 2, 3, 4, and 5 hold, and let $\omega(\mathbf{z})\neq 0~{}\forall\mathbf{z}\in\partial G$. Then, if SeCoND (Algorithm 2) converges to a point $\mathbf{z}$:

- 1.
If $\mathbf{z}\in\mathrm{int}G$, then $\mathbf{z}$ is a strict local generalized Nash equilibrium.
- 2.
If $\mathbf{z}\in\partial G$, then $\mathbf{z}$ is a local generalized Nash equilibrium (not necessarily strict).

###### Proof.

Assume that SeCoND converges to a point $\mathbf{z}$. We consider two cases, as follows:

- 1.
If $\mathbf{z}\in\mathrm{int\,}\mathcal{G}$, then the immediate neighbourhood around $\mathbf{z}$ which SeCoND would have to traverse in order to reach $\mathbf{z}$ is also in $\mathrm{int\,}\mathcal{G}$. In this neighborhood, the projection step in SeCoND does not have any effect, and the algorithm’s dynamics follow DND.
By Theorem 2, DND would only have converged to $\mathbf{z}$ if $\nabla f(\mathbf{z})=0,\nabla_{\mathbf{x}\mathbf{x}}^{2}f\succ 0,$ and $\nabla_{\mathbf{y}\mathbf{y}}^{2}f\prec 0,$ which from Definition 2.4 implies that $\mathbf{z}$ is also a strict local Generalized Nash equilibrium.
- 2.
If $\mathbf{z}\in\partial\mathcal{G},$ then from Algorithm 2, $-\omega(\mathbf{z})$ must be in the normal cone of $\mathcal{G}$ at $\mathbf{z}$. Because $\omega(\mathbf{z})=\begin{bmatrix}\nabla_{\mathbf{x}}f\\
-\nabla_{\mathbf{y}}f\end{bmatrix},$ this means that at $\mathbf{z}$, a feasible step cannot be taken for which $\mathbf{x}$ or $\mathbf{y}$ can reduce or increase $f(\mathbf{x},\mathbf{y})$, respectively.
Thus, from Definition 2.4, $\mathbf{z}$ is a local (not necessarily strict) generalized Nash equilibrium.

This concludes the proof.
∎

###### Proof.

###### Proof.

###### Proof.

###### Proof.

###### Proof.

###### Proof.

###### Proof.

## Appendix B Note on our Assumptions

We include this note to give the reader intuition about our Assumptions’ validity.
Assumptions 1, 2, and 4 are standard in the literature. Because we propose second-order methods, Assumption 1 ensures that the objective offers meaningful first and second-order derivatives. Assumption 2 ensures that the Jacobians of any dynamical system introduced in the paper can be analyzed at a critical/fixed point. In theory, Assumption 3 is required to ensure that all fixed points of the introduced algorithms are critical points of the GDA dynamics eq. 6, and vice versa. Other previous methods have also had to make similar assumptions for this very purpose [mazumdar2019finding], and the assumption we make is easier to check in comparison. Our experiments do not satisfy Assumption 3. However, the approaches introduced still perform well. Assumption 5 has shown to hold for several problems of practical interest [facchinei2010generalized].

## Appendix C Choice of Regularization Matrices and S in SecOND

Equation eq. 8 provides a natural choice of ${S(\mathbf{z})}$ as:

$$ $S=2\begin{bmatrix}(\nabla_{\mathbf{x}\mathbf{x}}f)^{3}&0\\ 0&-(\nabla_{\mathbf{y}\mathbf{y}}f)^{3}\end{bmatrix}+\lambda I,$ (18) $$

where $\lambda\geq 0$ is regularization that ensures positive definiteness. We show how to choose $\lambda$ below.

##### Choice of S(z) for superlinear Gauss-Newton Interpretation.

We take $S(\mathbf{z}_{k})$ to be $J(\mathbf{z}_{k})^{\top}J(\mathbf{z}_{k})+\lambda_{k}I$ where $\lim_{k\to\infty}\lambda_{k}=0$.

A way of designing regularization matrices is by using the Gershgorin Circle Theorem [horn2012matrix], which states that for a matrix $A\in\mathbb{C}^{n\times n}$, all eigenvalues of $A$ lie in the union of $n$ discs centred at $A_{ii}$ with radii $R_{i}=\sum_{j=1,j\neq i}^{j=n}|A_{ij}|$ for $i=1,\dots,n$. Thus, to regularize $A$ for invertibility, a diagonal regularization matrix $M$ with the $i^{th}$ diagonal entry $M_{ii}=\mathbbm{1}_{\{A_{ii}-R_{i}<0\}}(|A_{ii}-R_{i}|+\lambda_{0})$, where $\lambda_{0}>0$ is user specified and is a lower bound on the real part of eigenvalues of $A+M$. With this, we design:

- 1.
$E_{c}(\mathbf{z})$ in eq. 9: Here, $A=J(\mathbf{z})^{\top}J(\mathbf{z})(J(\mathbf{z})+J(\mathbf{z})^{\top})$, and the regularization matrix
$E_{c}(\mathbf{z})_{ii}=\mathbbm{1}_{\{A_{ii}-R_{i}<0\text{ and }\lVert\omega(
\mathbf{z})\rVert>\delta_{0}\}}(|A_{ii}-R_{i}|+\lambda_{0})$. The constant $\delta_{0}>0$ is also user-specified and ensures that at a critical point, $E_{c}$ is differentiable and that $E_{c}=0$.
- 2.
Design of $E(\mathbf{z}_{k})$ in eq. 10: In this case, $A=J(\mathbf{z}_{k})^{\top}J(\mathbf{z}_{k})(J(\mathbf{z}_{k})+J(\mathbf{z}_{k}
)^{\top}+\beta(\mathbf{z}_{k}))$, and we proceed as above.
- 3.
Design of $S(\mathbf{z}_{k})$ in eq. 12: We can take $A$ as the matrix given in Equation (18) and choose $\lambda=\max_{i}\{(A_{ii}-R_{i})+\lambda_{0}\}$ (and thus $S=A+\lambda I$). For the Gauss-Newton interpretation, we can take $A=J(\mathbf{z}_{k})^{\top}J(\mathbf{z}_{k})$.

In our experiments, we took the values $\lambda_{0}=5$ and $\delta_{0}$ = $5\times 10^{-5}$.

## Appendix D Experimental Details

### D.1 Two-Dimensional Toy Example

#### D.1.1 Baselines

##### Local Symplectic Surgery (LSS).

For the toy example, the LSS method is:

$$ $\mathbf{z}_{k+1}=\mathbf{z}_{k}-\alpha(\omega(\mathbf{z}_{k})+e^{-\xi_{2}\|v\| ^{2}}v),$ $$

where $v=J(\mathbf{z}_{k})^{\top}(J(\mathbf{z}_{k})^{\top}J(\mathbf{z}_{k})+\lambda(
\mathbf{z}_{k})I)^{-1}J(\mathbf{z}_{k})^{\top}\omega(\mathbf{z}_{k})$ and regularization $\lambda(\mathbf{z}_{k})=\xi_{1}(1-e^{\|\omega(\mathbf{z}_{k})\|^{2}})$. Here, $\xi_{1}=\xi_{2}=10^{-4}$. These values have been recommended in the LSS paper for this particular example. Though the authors also described a two-timescale discrete system of LSS, it could not reliably converge for this example, and thus, we resorted to the equation above.

##### (Curvature Exploitation for the
Saddle Point problem (CESP).

The CESP method is given by:

$$ $\mathbf{z}_{k+1}=\mathbf{z}_{k}-\alpha\omega(\mathbf{z}_{k})+\begin{bmatrix} \mathbf{v}_{\mathbf{z}_{k}}^{(-)}\\ \mathbf{v}_{\mathbf{z}_{k}}^{(+)}\end{bmatrix},$ $$

where, for the sign function $\mathrm{sgn:}\mathbb{R}\rightarrow\{-1,1\}$,

$$ $\begin{split}\mathbf{v}_{\mathbf{z}_{k}}^{(-)}&=\mathbbm{1}_{\lambda_{\mathbf{ x}}<0}\frac{\lambda_{\mathbf{x}}}{2\rho_{\mathbf{x}}}\mathrm{sgn}(\mathbf{v}_{ \mathbf{x}}^{\top}\nabla_{\mathbf{x}}f(\mathbf{x},\mathbf{y}))\mathbf{v}_{ \mathbf{x}}\\ \mathbf{v}_{\mathbf{z}_{k}}^{(+)}&=\mathbbm{1}_{\lambda_{\mathbf{y}}>0}\frac{ \lambda_{\mathbf{y}}}{2\rho_{\mathbf{y}}}\mathrm{sgn}(\mathbf{v}_{\mathbf{y}}^ {\top}\nabla_{\mathbf{y}}f(\mathbf{x},\mathbf{y}))\mathbf{v}_{\mathbf{y}}.\end {split}$ $$

Here, $\lambda_{\mathbf{x}}$ and $\lambda_{\mathbf{y}}$ denote the minimum and maximum eigenvalues of $\nabla^{2}_{\mathbf{x}\mathbf{x}}f$ and $\nabla^{2}_{\mathbf{y}\mathbf{y}}f$ respectively. $\mathbf{v}_{\mathbf{x}}$ and $\mathbf{v}_{\mathbf{y}}$ denote the eigenvectors of $\lambda_{\mathbf{x}}$ and $\lambda_{\mathbf{y}}$. We took $\nicefrac{{1}}{{2\rho_{\mathbf{x}}}}=\nicefrac{{1}}{{2\rho_{\mathbf{y}}}}=0.05$. CESP could not converge reliably for the two-dimensional example, and a typical diverging plot is shown in Figure 3.

Figure: Figure 3: CESP [adolphs2019local] diverges for the two-dimensional toy example.
Refer to caption: extracted/5900128/Images/cesp.png

#### D.1.2 Experiment Parameters.

For all algorithms, step size $\alpha$ was taken to be 0.001, except for SecOND which performed Armijo line search. Tolerance for convergence was set at $10^{-5}$, and the maximum number of allowable iterations for every algorithm was 15,000. $\epsilon$ for SecOND (Algorithm 1) was taken to be $10^{-2}$. For Figure 1, data points that were below $Q_{1}-1.5(Q_{3}-Q_{1})$ or above $Q_{3}+1.5(Q_{3}-Q_{1})$ were considered outliers. Here, $Q_{1}$ and $Q_{3}$ denote the first and third quartiles, respectively.

#### D.1.3 Additional Unconstrained Case Result.

We show a comparison of SecOND and DND for the unconstrained toy example to show that our approaches converge to local Nash equilibrium. From Figure 4, it can be seen that only SecOND and DND successfully converge to local Nash equilibrium. CESP and GDA diverged, while LSS converged to a non-Nash point. This behavior of LSS arises due to the assumption they make (Theorem 4, [mazumdar2019finding]), which gets violated. Out of the algorithms which converged, LSS took 75 iterations, DND took 5405 iterations, while SecOND took just 7 iterations.

Figure: Figure 4: SecOND and DND converge successfully to a local Nash equilibrium.
Refer to caption: extracted/5900128/Images/additional.png

### D.2 Generative Adversarial Network

#### D.2.1 LSS Baseline.

For GAN training, we use the two-timescale approximation method for LSS described in [mazumdar2019finding], which is given by

$$ $\begin{split}\mathbf{z}_{k+1}=&\mathbf{z}_{k}-\gamma_{1}(\omega(\mathbf{z}_{k} )+e^{-\xi_{2}\|J(\mathbf{z}_{k})^{\top}v_{k}\|^{2}}J(\mathbf{z}_{k})^{\top}v_{ k})\\ v_{k+1}=&v_{k}-\gamma_{2}(J(\mathbf{z}_{k})^{\top}J(\mathbf{z}_{k})v_{k}+ \lambda(\mathbf{z}_{n})v_{k}-J(\mathbf{z}_{k})^{\top}\omega(\mathbf{z}_{k})). \end{split}$ $$

Similar to the toy example, $\lambda(\mathbf{z}_{k})=\xi_{1}(1-e^{\|\omega(\mathbf{z}_{k})\|^{2}})$, and $\xi_{1}=\xi_{2}=10^{-4}$
In the generative adversarial network (GAN) example in Section 4.2, the zero-sum game is between the generator $G$, which minimizes $\mathcal{F}$, and the discriminator $D$, which maximizes $\mathcal{F}$. Here, $\mathcal{F}:=\operatorname{\mathbb{E}}_{x\sim p_{\mathrm{data}}(x)}[\log D(x)]
+\operatorname{\mathbb{E}}_{\epsilon\sim p_{\epsilon}(\epsilon)}[\log(1-D(G(
\epsilon)))]$, and $x$ and $\epsilon$ denote actual data samples and noise samples, respectively. Table 1 lists the parameter values of the GAN model used in our evaluation.

**Table 1: Parameters of the GAN example in Section 4.2.**
|  | Discriminator | Generator |
| --- | --- | --- |
| Input Dimension | 1 | 1 |
| Hidden Layers | 2 | 2 |
| Hidden Units / Layer | 8 | 8 |
| Activation Function | tanh | tanh |
| Output Dimension | 1 | 1 |
| Batch Size | 128 |  |
| Dataset size | 10000 |  |

We evaluate GDA, LSS, and our SecOND approach. GDA uses an Adam optimizer with a learning rate $10^{-4}$; LSS uses an RMSProp optimizer with a learning rate $2\times 10^{-4}$ for the $x$ and $y$ processes and $1\times 10^{-5}$ for the $v$ process, as reported in [mazumdar2019finding]. SecOND uses an RMSProp optimizer with a learning rate $2\times 10^{-4}$.

##### Remark

As suggested by [goodfellow2014generative], to improve the convergence of GDA, we update the discriminator $k=3$ times more frequent than the generator $G$. Moreover, the GDA generator maximizes $\log(D(G(\epsilon)))$ instead of minimizing $\log(1-D(G(\epsilon)))$. We found the best practical performance with the said setup.

## Appendix E Hardware

The two-dimensional toy examples were run on an Intel i7-11800H 8-core CPU.
The GAN training sessions were run on an AMD Ryzen 9 7950X 16-core CPU.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: Kindly refer to the weaknesses.
soundness: 3
strengths: It's noteworthy that the authors developed an entire family of algorithms for, both, unconstrained and constrained spaces.
summary: The authors design a (family of) second-order algorithms for two-player zero-sum games with the property that, if convergence is achieved, the point of convergence is proved to be a local Nash equilibrium. In particular, such a point of convergence must be a locally asymptotically stable equilibrium.
weaknesses: 1. An obvious weakness is that the suggested algorithms are applicable only to two-player zero-sum games. Could they be modified to support multi-player games?
2. Assumptions 1, 2,  and 4 seem reasonable. I am not quite sure how common Assumption 3 is. I understand that the authors consider the relaxation of Assumption 3 as future work. Could they provide some possible intuition? For example, is their natural subclass of two-player zero-sum games that this assumption is satisfied?

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: Does the assumptions imply unique LASE point? 
Is there any assumption on the uniqueness of the local strict Nash equilibrium?
How far should the initial point be at most from the LASE point in order to have convergence?
Do the proven rates of convergence of the unconstrained case hold in the constrained case?
soundness: 3
strengths: I think that the problem that the authors study is significant and this paper gives new directions to understand it. Their results are good since they give new dynamics and prove local rate of convergence using techniques such as bounding by strictly less than 1 the eigenvalues of the Jacobian matrix. Furthermore, the idea to find a dynamical system s.t. any LASE is a local Nash equilibrium of the initial game is nice.
summary: One of the fundamental problems in algorithmic game theory area is learning algorithms for games. In this paper, the authors study a problem related to this area, particularly an unconstrained two-player zero-sum game with an objective function that can be nonconvex-nonconcave. 

In this direction they study algorithms for convergence to local Nash equilibria taking into account the second order conditions of the function. To do that they propose a dynamical systems approach s.t. under specific assumptions the critical points are also local Nash equilibria to the initial game. They prove that their initial dynamics converges with local linear rate of convergence to a local strict Nash equilibrium and they give an improved algorithm of them with super linear local rate of convergence. Finally, they give an algorithm for the constrained setting based on an Euclidean projection approach to converge to a local generalized Nash equilibrium and experiments to give evidence for their approach.
weaknesses: The results hold under specific assumptions and they only guarantee local convergence. I think the paper needs more elaboration how strict are these assumptions and for the latter how far the initial point should be at most from the LASE point in order to have convergence.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: * Theorem 2 does not provide a convergence analysis, is there any technique difficulty?
* It would be better if the author conducts a numerical experiment on a model that satisfies all the assumptions in Section 3.
soundness: 2
strengths: * The algorithm leverages second-order dynamics to achieve higher convergence rates and avoid common pitfalls like oscillations around equilibrium points.
* The authors validate their approach on a GAN training task, demonstrating the algorithms' robustness and practical utility in adversarial machine learning settings.
summary: This paper tackles the problem of achieving convergence to local Nash equilibria in two-player zero-sum games. While first-order optimization methods struggle with nonconvex-nonconcave settings and often lead to non-Nash equilibria or unstable cycles, this work addresses these challenges by developing algorithms that leverage second-order information to improve stability and convergence specifically towards local Nash equilibria. The author shows that the algorithm achieves local linear convergence and proposes an advanced version enabling superlinear convergence.
weaknesses: * The explanation of assumptions in Section 3.1 is weak, and the example in the numerical experiment does not satisfy Assumption 3.
* The author does not claim the technique contribution.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Besides the question above about the underlying assumptions, is it assumed that the set of constraints has a nonempty interior? For example, what if we are dealing with the probability simplex, which has empty interior? It doesn't seem that the definitions and the approach can handle that case.
soundness: 3
strengths: The paper considers a well-motivated problem that has attracted much attention in recent years. Compared to prior work that focused on local convergence to Nash equilibria in nonconvex-nonconcave min-max optimization, the paper derives explicit rates of convergence, and also addresses the constrained setting as well. I believe that both of those contributions are important. The authors also support their theory by conducting several experiments, showing that the proposed method outperforms quite convincingly the two most related algorithms (LSS and CESP). Moreover, the paper employs interest techniques, mostly relying on dynamical system theory. Although most of those techniques are standard in this area, the way they are combined in this paper appears to be new. The writing overall is of high quality, and the authors do a good job at explaining the key ideas in the main body. The most related papers have been cited, although I would suggest including a more detailed discussion about the paper of Daskalakis et al. (2023) since it is strongly related. All claims appear to be sound.
summary: The paper considers nonconvex-nonconcave zero-sum games. It provides an algorithm with a local convergence guarantee and (local) linear convergence rate. Further, a variant of that method attains local superlinear convergence to a point that satisfies the first-order Nash equilibrium conditions. Finally, the approach is generalized to handle constraints.
weaknesses: The paper has several weaknesses, some of which are in some sense insurmountable. First, the proposed method relies on second-order information, which could limit its practical applicability. Perhaps more importantly, the main result only establishes local convergence. It is unclear whether a local convergence guarantee is a strong enough solution concept. The paper of Daskalakis et al. (2023) provides a global convergence guarantee, but the latter comes without a rate of convergence. At the same time, I believe that computing local Nash equilibria in this setting is intractable (at least in the constrained setting), and so this perhaps justify focusing on local convergence. Regarding the assumptions made in the paper, Assumption 3 seems very artificial and hard to parse. Can the authors elaborate more on what that assumption entails? And why is it a reasonable assumption? Assumption 2 also seems somewhat artificial, but at least its role is quite clear. I believe that the main body should discuss in more detail some of those assumptions.

Meta-review: This paper examines and analyzes a second-order algorithm for learning in non-convex/non-concave min-max games. The algorithm under study can be viewed as a Newton-like variant of an earlier algorithm proposed by Mazumdar et al. (2019), and the authors show that, if the algorithm converges, it converges to a strict local Nash equilibrium, and it does so at a superlinear rate.

This paper received one clear accept recommendation but, otherwise, most of the reviewers were on the fence. The concerns raised during the discussion mostly focused on the following issues: 
1. It was not clear what role Assumption 3 played in the analysis. A similar assumption did appear in a previous paper by Mazumdar et al. (2019), but it did not seem to play the same role there (in the sense that it is not needed for results that are similar to those of the current paper).
2. There were also concerns regarding the positioning of the current paper relative to the work of Mazumdar et al. (2019). In particular, the dynamics considerd in this paper are very similar to the LSS dynamics of Mazumdar et al., but the authors did not adequately discuss the differences between them (either in the paper or during the discussion phase).
3. There are also issues parsing the authors' results as stated. To name but an example, Point (1) of Theorem 2 states that "*the fixed points of DND are *exactly* the fixed points of the discrete-time GDA dynamics*". This means that DND admits stationary points that are critical points of the game, but not necessarily local Nash equilibria. However, if DND is initialized at such a point (or, more generally, at the stable manifold of such a point), it will converge to it, in violation of the authors' claim in L266 of Theorem 3.
4. Similar concerns apply to the statement "$S(\mathbf{z}_k) \approx J(\mathbf{z}_k)^\top J(\mathbf{z}_k)$" in Theorem 4 and the like: despite references to the paper's appendix, the exact meaning of the "approximate equality" sign $\approx$ can only be guessed, and likewise for the quantifier "near" in the same statement: for example, if DND starts at a non-Nash critical point, it will always stay there, contradicting the authors' claim.
5. The computational cost of the proposed algorithm is not adequately discussed. For instance, knowing the functional dependence of one's payoff function on one's individual control variables is quite different from knowing this dependence on the other player's control variables; likewise, assuming access to individual gradients or Hessians - that is, derivates of one's payoff function relative to one's individual control variables - is different than assuming access to gradients and/or Hessians relative to the other player's control variables; and again so for the Armijo-like line search in (14), etc.

After discussing these concerns, it was not possible to make a clear case for accepting the paper "as is" - i.e., without further revisions that would require a fresh set of reviews - and it was decided to make a reject recommendation. This decision was made with the best interests of the paper in mind: the paper is not without its merits, but the current version is not clear on several key issues that end up  undermining the authors' contributions, so a more drastic revision would be in order before the paper could ultimately be accepted.

Decision: Reject