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

Authors: Kushagra Gupta, Xinjie Liu, Ross Emerson Allen, ufuk topcu, David Fridovich-Keil
Primary area: optimization
Keywords: game theory, nonconvex-nonconcave optimization, dynamical systems, Nash equilibrium

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 $\textit{linear}$ convergence rate. We then interpret a version of this method as a modified Gauss-Newton algorithm with local $\textit{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.

Decision: reject
Reviewer scores: 8, 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1730684833061

thread_type:
official_review

<thread_object>
creator: reviewer_mjzp

<content>
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.

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730685978188

thread_type:
official_review

<thread_object>
creator: reviewer_s3ww

<content>
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.

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730694872269

thread_type:
official_review

<thread_object>
creator: reviewer_cwfg

<content>
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.

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.

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.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730816412705

thread_type:
official_review

<thread_object>
creator: reviewer_xyrn

<content>
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.

strengths:
It's noteworthy that the authors developed an entire family of algorithms for, both, unconstrained and constrained spaces.

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?

questions:
Kindly refer to the weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731735003184

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of revisions to manuscript

comment:
We have made the following changes to our submission based on the reviewers' feedback:
* Added more discussion about our assumptions, especially intuition about assumption 3 in Appendix B (as requested by multiple reviewers).
* Added an example that satisfies assumption 3 (as requested by reviewer S3WW) and has an empty interior (as requested by reviewer mJzP) in Appendix C.

We are happy to make more changes based on further reviewer feedback.
</content>
</thread_object>

</thread>


Metareview:
metareview:
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.