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

We thank the reviewer for their detailed comments. We respond to the questions below. We are happy to revise our manuscript based on the following discussion/reviewer's suggestions, and have already added an example with empty interior (see Appendix C of the revised manuscript).

Points raised in the Weakness section.

• Local vs global guarantee: As the reviewer themself point out, the general intractability of the setting is what makes us focus on local (and not global) guarantees. As mentioned in Section 5, working on some global analysis is in the scope of our future work.
• Comparison with Daskalakis et al. (2023): There are two notable differences with the STON'R method introduced in Daskalakis et al. (2023) [A]. These also allow [A] to claim global convergence guarantees, which we currently cannot.
  1. Different solution concept: We solve for strict local Nash equilibria (unconstrained case) / generalized local Nash equilibria (constrained case). These are characterized by the first and second-order conditions we mention in Definitions 2.3 and 2.4. On the other hand, STON'R solves for a different solution concept. The min-max critical points that STON'R solves for only have first-order conditions and thus can be viewed as solving for a relaxation of the true local Nash concept. This means that STON'R can converge to points that do not satisfy Definitions 2.3/2.4. We would like to emphasize that, as mentioned in Section 3, a big motivation for our work is to find methods that satisfy not only first-order conditions but also second-order conditions.
  2. Constraint Structure: The global convergence guarantees of STON'R depend on the constraint set being restricted to a hypercube $(x\in[0,1]^n, y\in[0,1]^m)$, and the authors mention technical challenges in extending the analysis to more general convex constraints (for example, even the unit ball). In comparison, while we cannot offer global convergence guarantees, we do offer at least local convergence in problems with more general constraint structures.
  3. Convergence Rates: As pointed out by the reviewer, [A] does not have convergence rates, while we derive explicit convergence rates.

[A] Daskalakis, Constantinos, et al. "Stay-on-the-ridge: Guaranteed convergence to local minimax equilibrium in nonconvex-nonconcave games." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

We thank the reviewer for their review. We respond to the reviewer's points below.

• Point 1

The explanation of assumptions in Section 3.1 is weak, and the example in the numerical experiment does not satisfy Assumption 3.

Discussion on assumptions is included in Appendix B. We include some further discussion here, and have also revised the manuscript's appendix to reflect the same. Assumptions 1, 2 and 4 are fairly standard in literature, see for example related state-of-the-art methods [A], [B], [C]. Intuition about Assumption 3 can be given through an analogy: consider some smooth function $g(x)$ and the corresponding problem $\min_{x\in\mathbb{R}^n} g(x)$. Any optimization algorithm will produce iterates of the form $x_{k+1} \gets x_k -\alpha_k p_k$ (or $\dot x = - p_k$ in continuous-time). In particular, for any Newton-like algorithm, $p_k = H_k \nabla g(x_k)$ (for example, $H_k$ can be the regularized hessian inverse $(\nabla_{xx}g(x_k)+\lambda I)^{-1}$, for some $\lambda>0$). In order to ensure convergence to a minima, one of the conditions developed in nonlinear optimization thoery is that $p_k$ must not be orthogonal to $\nabla g(x_k)$ when $\nabla g \neq 0$, thus $H_k\nabla g(x_k)$ must not be $0$ for $\nabla g(x_k)\neq 0$. Similarly, in our case, the dynamics (see equations (9), (10)) are iterates of the form $z_{k+1}\gets z_k - \alpha_k M_k J(z_k)^\top \omega(z_k)$ (or $\dot z = -M J(z)^\top \omega(z)$), where $M_k$ (or $M$) is a full rank matrix. Thus, to ensure the second term in the update is zero only when $\omega(z)=0$, $J(z_k)^\top \omega(z_k)$ must not be $0$ when $\omega(z_k)\neq 0$. We hope this makes the requirement of assumption 3 clear. We would like to re-emphasize that a version of this assumption is standard in related work employing dynamical systems. The closest related state-of-the-art work [A], which uses similar dynamical system concepts, also uses a version of Assumption 3 (in Theorem 4 of [A]). In fact, our Assumption 3 is more relaxed than the corresponding assumption in [A]. We have added an example that satisfies Assumption 3 in Appendix C. Please refer to the revised manuscript.

• Point 2

The author does not claim the technique contribution.

We are unclear on what the reviewer means here. We will be happy to respond more clearly if the reviewer can elaborate. Our contributions are listed in Section 1. They are:

1. (Unconstrained) $`DND`:$ Discrete-time dynamical system that provably converges to only local Nash equilibria (LNE), with a linear local convergence rate. In comparison, only two previous related works (LSS and CESP mentioned in the paper) have guarantees of convergence to only LNE, but do not have any rates in comparison.
2. (Unconstrained) $`SecOND`:$ Discrete-time dynamical system that retains the convergence to only LNE guarantee as above, and converges superlinearly to the neighborhood of a point that satisfies first-order local Nash conditions.
3. (Constrained) $`SeCoND`:$ Convergence to only local generalized Nash equilibrium in the presence of (possibly coupled) constraints of the form of a convex set. In contrast, previous work either does not consider this constrained setting (or has a more restrictive constrained settings, like a hypercube) and/or is restricted to the convex-concave case.

• Point 3

Theorem 2 does not provide a convergence analysis, is there any technique difficulty?

The convergence analysis is the subject of Theorem 3. We apologize for any confusion that has occured. To clarify, Theorem 2 establishes that the only LASE of the proposed dynamics $`DND`$ are the local Nash equilibrium of the problem (and vice-versa). Thus, if the dynamics converge, they must converge to an LASE (and thus to a local Nash point). The convergence analysis of this is given in Theorem 3.

• Point 4

It would be better if the author conducts a numerical experiment on a model that satisfies all the assumptions in Section 3.

We have revised the manuscipt and added an example that satisfies Assumption 3 in Appendix C, and our method performs successfully for that example as well. The experiments currently in Section 4 were chosen so as to investigate whether the method empirically performs well even if Assumption 3 is violated, which it does.

[A] Mazumdar, Eric V., Michael I. Jordan, and S. Shankar Sastry. "On finding local nash equilibria (and only local nash equilibria) in zero-sum games." arXiv preprint arXiv:1901.00838 (2019).

[B] Adolphs, Leonard, et al. "Local saddle point optimization: A curvature exploitation approach." The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019.

[C] Azizian, Waïss, et al. "The Rate of Convergence of Bregman Proximal Methods: Local Geometry Versus Regularity Versus Sharpness." SIAM Journal on Optimization 34.3 (2024): 2440-2471.

We thank the reviewer for their detailed comments. Please find our discussion on the weaknesses and answers to the questions below.

Regarding Weaknesses

• Strictness of these assumptions: Assumptions 1, 2, and 4 are standard in the literature (for example, [A], [B], [C]). Assumption 5 has been shown to hold for several problems of practical interest [D]. Assumption 3 is required to ensure that all fixed points of the introduced algorithms are critical points of the GDA dynamics (given in equation (6)), and vice-versa. A version of assumption 3 is also used in related work employing dynamical system concepts. The closest related state-of-the-art work [A], which uses similar dynamical system concepts, also uses a version of Assumption 3 (in Theorem 4 of [A]). In fact, our Assumption 3 is more relaxed than the corresponding assumption in [A]. While relaxing our Assumption 3 is scope of future work, we have deliberately chosen our examples in Section 4 such that Assumption 3 does not hold in order to demonstrate that our methods perform well empirically even without Assumption 3. We refer the reviewer to Appendix B where we discuss all assumptions, and also to our response to reviewer XyrN for a more detailed discussion on Assumption 3. The manuscript has been revised to reflect these discussions in Appendix B.

Response to Questions

• Do the assumptions imply unique LASE point? No, in a problem that satisfies all assumptions, there can be multiple LASE points (and hence multiple local Nash equilibria).
• Is there any assumption on the uniqueness of the local strict Nash equilibrium? No, there is no assumption on uniqueness of local strict Nash equilibrium. Our convergence guarantees are for convergence to a LASE/local Nash point, so depending on different initializations, one can go to different LASE/local Nash points.
• How far should the initial point be at most from the LASE point in order to have convergence? In general, the initial point must be within the region of attraction of at least one LASE point. In nonconvex settings, there is no clear answer for the extent of this region for most local methods. A potential direction of future work consists of constructing Lyapunov functions for the introduced algorithms which can help establish the extent of the region of attraction. However, we note two important points in our current methods: 1) The initial point need not be in a locally convex-concave region, 2) The modified Gauss-Newton method in $`SecOND`$ (Algorithm 1) can reach a critical point with the initialization arbitrarily far away from it, provided any standard line search method developed in nonlinear optimization (for example, Armijo) is done.
• Do the proven rates of convergence of the unconstrained case hold in the constrained case? No, this is because at the boundary, the gradients of active constraints can be arbitrarily aligned with the update step. Thus we have been unable to conduct a meaningful analysis of the convergence rate in the constrained nonconvex-nonconcave setting. To the best of our knowledge, related work is also unable to handle this case. The only results we are aware of pertain to the convex-concave setting (for example, [E]).

We are happy to answer any other questions, and are happy to revise the manuscript to reflect the above discussion as well.

[A] Mazumdar, Eric V., Michael I. Jordan, and S. Shankar Sastry. "On finding local nash equilibria (and only local nash equilibria) in zero-sum games." arXiv preprint arXiv:1901.00838 (2019).

[B] Adolphs, Leonard, et al. "Local saddle point optimization: A curvature exploitation approach." The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019.

[C] Azizian, Waïss, et al. "The Rate of Convergence of Bregman Proximal Methods: Local Geometry Versus Regularity Versus Sharpness." SIAM Journal on Optimization 34.3 (2024): 2440-2471.

[D] Facchinei, Francisco, and Christian Kanzow. "Generalized Nash equilibrium problems." Annals of Operations Research 175.1 (2010): 177-211.

[E] Cevher, V., Piliouras, G., Sim, R., & Skoulakis, S. (2023). Min-max optimization made simple: Approximating the proximal point method via contraction maps. In Symposium on Simplicity in Algorithms (SOSA) (pp. 192-206). Society for Industrial and Applied Mathematics.

We thank the reviewer for their detailed comments. Kindly find our answers below:

Question on more than two players: The reviewer is correct in pointing out that the current method is only applicable to the two-player case. The reason why the current method cannot be directly applied to a case of N>2 players is that our second order dynamics rely on a particular structure induced by the two players. This particular structure can be lost in the more general case of N>2 players. This being said, the two-player case is important in itself, as many problems of interest across computer science, economics, control theory, etc. have a two player zero-sum formulation. Thus, we (and most previous related works also) focus on the two-player setting.

Question on Assumption 3:

• For intuition, we provide an analogy with single player optimization. Consider some smooth function $g(x)$ and the corresponding problem $\min_{x\in\mathbb{R}^n} g(x)$. Any optimization algorithm will produce iterates of the form $x_{k+1} \gets x_k -\alpha_k p_k$ (or $\dot x = - p_k$ in continuous-time). In particular, for any Newton-like algorithm, $p_k = H_k \nabla g(x_k)$ (for example, $H_k$ can be the regularized hessian inverse $(\nabla^2_{xx}g(x_k)+\lambda I)^{-1}$, for some $\lambda\geq0$). In order to ensure convergence to a minima, one of the conditions developed in nonlinear optimization theory is that $p_k$ must not be orthogonal to $\nabla g(x_k)$ when $\nabla g \neq 0$, thus $H_k\nabla g(x_k)$ must not be $0$ for $\nabla g(x_k)\neq 0$ [A, Chapter 3]. Similarly, in our case, the dynamics (see equations (9), (10)) are iterates of the form $z_{k+1}\gets z_k - \alpha_k M_k J(z_k)^\top \omega(z_k)$ (or $\dot z = -M J(z)^\top \omega(z)$), where $M_k$ (or $M$) is a full rank matrix. Thus, to ensure the second term in the update is zero only when $\omega(z)=0$, $J(z_k)^\top \omega(z_k)$ must not be $0$ when $\omega(z_k)\neq 0$. We hope this makes the requirement of assumption 3 clear. We would like to highlight that a version of this assumption is standard in related work employing dynamical systems. The closest related state-of-the-art work [B], which uses similar dynamical system concepts, also uses a version of Assumption 3 (in Theorem 4 of [B]). In fact, our Assumption 3 is more relaxed than the corresponding assumption in [B].
• An example of a sub-class of games where this assumption holds is games where the matrix $J$ is non-degenerate. In fact, a popular class of games that satisfy Assumption 3 are entropy-regularized zero-sum matrix games. The Nash equilibria of such games are called Quantal Response Equilibria, which have important applications [C]. We have revised our manuscript to include an example that uses our method to solve such a game, in Appendix C. We have also revised our discussion of Assumptions in Appendix B to include the above intuition.

We are happy to answer any other questions, and are happy to revise the manuscript to reflect the above discussion as well.

[A] Nocedal, Jorge, and Stephen J. Wright, eds. Numerical optimization. New York, NY: Springer New York, 1999.

[B] Mazumdar, Eric V., Michael I. Jordan, and S. Shankar Sastry. "On finding local nash equilibria (and only local nash equilibria) in zero-sum games." arXiv preprint arXiv:1901.00838 (2019).

[C] McKelvey, Richard D., and Thomas R. Palfrey. "Quantal response equilibria for normal form games." Games and economic behavior 10.1 (1995): 6-38.