Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper:   In this paper, the authors consider the problem of designing methods with local convergence for finding second order Nash equilibria in nonconvex two-player general-sum games. Their main result is that, under some assumptions, a variation of the Follow-the-Ridge algorithm is locally asymptotically stable around any second-order Nash equilibria of the game and is not locally asymptotically stable in any other point.
strength_and_weaknesses: Strengths
======================
  - The problem that the authors consider is very important and difficult, and hence even the local convergence results in this area have significant theoretical importance.

  - The paper is well-written and the algorithms and techniques well-explained.

  - The dynamics that the authors provide are simple and intuitive and can potentially have significant practical applications.

Weaknesses - Comments
========================

  General comment: I believe that the results of this paper are indeed interesting but I think their current motivation is wrong. I will justify this with the comments that I present below.

  1. If we assume that there exists a Differential Nash Equilibrium according to Definition 2.1 and we also assume Assumption 1 then, unless I am missing something, f is convex with respect to x and g is concave with respect to y everywhere.
  Proof sketch: Let $z^* = (x^*, y^*)$ be a Differential Nash Equilibrium according to Definition 2.1. Assume also that there exist a point $z_0 = (x_0, y_0)$ such that $f$ is not convex with respect to $x$ at $z_0$. This means that $\nabla^2_{x x} f(z_0)$ has a negative eigenvalue. Consider now the line segment $L$ that connects $z^*$ and $z_0$. We know that the eigenvalues of $\nabla^2_{x x} f(z^*)$ are all positive and that $\nabla^2_{x x} f(z)$ is a continuous function of $z$ according to Assumption 1. It is also well-known that the eigenvalues are continuous functions of the matrices. Hence, the minimum eigenvalue of $\nabla^2_{x x} f(z)$ goes from positive at $z = z^*$ to negative at $z = z_0$ in a continuous way. Since $\nabla^2_{x x} f(z)$ is symmetric all the eigenvalues are real and hence there should be a point $\bar{z} \in L$ such that the minimum eigenvalue of $\nabla^2_{x x} f(\bar{z})$ is zero which means that $\nabla^2_{x x} f(\bar{z})$ is not invertible which violates Assumption 1. Therefore, f is convex with respect to x and similarly g is concave with respect to y. Am I missing something here?
  Given the above, it is not an achievement of the proposed algorithm that is it stable only around stationary points that are second-order Nash because only such stationary points exist. So the main motivation of the paper is not correct.

  2. The achievement of the proposed algorithm though is that it is stable around all the simultaneous stationary points of f with respect to x and g with respect to y. This to my knowledge is a not trivial property even when we assume that f is convex with respect to x and g is concave with respect to y. The reason that this is interesting is that this is applied in a general-sum setting. Finding such simultaneous stationary points is as difficult as finding fixed points of any continuous map!
  Proof sketch: Let $H : \mathbb{R}^n \to \mathbb{R}^n$ be a continuous map and let $f(x, y) = \|x - H(y)\|^2$ and $g(x, y) = - \|x - y\|^2$. Then it is easy to see that all the simultaneous stationary points of f with respect to x and g with respect to y, correspond exactly to the fixed points of $H$.
  Finding fixed points of continuous maps is more general that finding solutions of general non-monotone variational inequalities, which is more general than multi-agent general-sum concave games which have a ton of applications in game theory and economics. So the fact that the proposed algorithm is locally asymptotically stable only on those points is an interesting property. Nevertheless, it should be compared to the known results from the variational inequalities community or the computation of fixed points community which is missing from the current version of the paper.
clarity,_quality,_novelty_and_reproducibility: See above.
summary_of_the_review:   Based on my comments above, I believe that there are some interesting corollaries from the work that is presented in this paper but the paper needs significant changes to reflect that and the current motivation is not correct unless I am missing something. At the current state I cannot recommend acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes the application of Follow-The-Ridge (usage of Shur's complement in Gradient Dynamics) for both players. The authors establish that double Follow-the-Ridge (double-FTR) is an algorithm that locally converges to and only to local Nash equilibria in general-sum two-player differentiable games. 
strength_and_weaknesses: Strength:
The iead of introducing of being the doubly the follower is interesting. It is not surprising that replacing the opponents' strategy by a follower's one will lead to better and safest performance. On the other hand, it seems to be a simpler and more general way (like a blackbox) to doing lookahead than previous approaches by modeling opponents.

Weaknesses:
1)There is no theoretical guarantee on convergence or approximation bound.
2)The double Follow the ridge trick may be too simple. Anyway, there should be a comparison with simply lookahead methods and with the following publications:

a) https://arxiv.org/pdf/2210.09769.pdf
b) https://arxiv.org/abs/2112.13826
3) The method is second-order. 
clarity,_quality,_novelty_and_reproducibility: Clarity & Quality: It is well-written paper
Novelty: Not-clear but interesting.

See above.

Clarification question #1: The preconditioning or the regularization with \ell_2 could transform the game to strong convex-concave or not?
Clarification question #2: In https://arxiv.org/abs/1910.13010, cited by (https://arxiv.org/pdf/2210.09769.pdf), difficult non-convex non-concave games are presented. It would be useful to present experiments of double FTR in such so-called hidden games, in order to exemplify the success of local vs global convergence guarantee in some challenging functions (since the presented ones seem in my humble opinion a bit artificial & synthetic)
summary_of_the_review: The authors propose double Follow-the-Ridge (double-FTR), an algorithm with local convergence guarantee to differential Nash equilibria in general-sum two-player differential games.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors contribute a novel method, Double-Follow-the-Ridge, for solving the problem of computing local Nash equilibria in two-player general-sum differentiable games. This novel method is inspired by the Follow-the-Ridge heuristic algorithm and uses second-order information along with first-order information. In fact, the authors generalize the method to contain dynamics that use preconditioners in place of the second order information as long as some conditions are met. Finally, the paper is complemented with an array of experiments that demonstrate the empirical performance of the proposed method. The convergence guarantees are restricted to the local convergence regime.

strength_and_weaknesses: Pros:
    * the paper is self-contained and all the definitions are provided
    * the novel method is a natural extension of the Follow-the-Ridge

Cons:
    * the convergence of the algorithm is guaranteed only locally
    * although the paper contains a lot of preliminaries which is helpful, the main body contains a lot of facts that are standard in min-max optimization and could be moved to the appendix
    * a standard reference for the limits of gda is not contained in the paper, i.e.,

Daskalakis, C. and Panageas, I., 2018. The limit points of (optimistic) gradient descent in min-max optimization. Advances in neural information processing systems, 31.
clarity,_quality,_novelty_and_reproducibility: The paper is well written and well-motivated
summary_of_the_review: The paper examines a well-established problem (min-max optimization of general-sum differentiable games), and it presents a novel method that builds upon existing work. The result is not particularly surprising although nontrivial. The idea of the novel method builds upon an existing algorithm but (probably justifiably) the authors did not move beyond local-convergence guarantees. As such, I believe the paper is slightly above the bar for acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies general-sum two-player differentiable games and proposes an algorithm (double-FTR) that locally converges to (and only to) differentiable Nash equilibria (DNE). Moreover, extensive empirical validation is provided.

strength_and_weaknesses: The main result of the paper is interesting and clearly presented. The proposed algorithm can be intuitively seen as an extension of the standard GDA algorithm where the update of each player has an additional term that makes use of second-order information. In particular, it seems like a natural extension of the FTR algorithm of [Wang, Zhang, Ba, ICLR 2019]. Having read the appendix, my main concern has to do with the technical novelty and challenges behind the main result. My concerns focus specifically on two aspects: (i) the algorithm is heavily similar to the FTR algorithm of [WZB '19] and (ii) the technical challenges (provided Assumption 2) are mainly algebraic manipulations of the double-FTR dynamics.

I would like to pose the following questions:

Q1. Can the authors highlight the technical novelties and challenges behind the result? Adding a technical overview section in the main body would be helpful. 

Q2. Assumption 2 ensures that the updates in lines 2 and 3 of Algorithm 1 do not vanish. Is it possible to drop this assumption or relax it by extending the proposed algorithm?  

Q3. Is it known whether second-order information is truly necessary in order to obtain a result like Theorem 1? As discussed in Section 2, standard GDA fails to converge even in zero-sum games. It would be beneficial to add a more extensive discussion regarding other first-order methods.

In general, I believe that the paper is nice and well-written. However, I think that the technical contribution of the paper is limited. Nevertheless, I am willing to increase my score after authors' rebuttal depending on the response.

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and the result is well-presented. The main issue is the paper's limited technical novelty.
summary_of_the_review: The paper proposes double-FTR algorithm which locally converges to and only to DNE. This algorithm is quite close to the FTR algorithm of [Wang, Zhang, Ba, ICLR 2019] and its analysis contains limited novelty. On the other side, the paper is well-written and the result is nice. This renders the paper marginally below the acceptance threshold.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper concerns the problem of finding Nash equilibria in two-player games where each player has a continuum of actions and smooth payoff functions. The authors' main contribution is a "double-FTR" (follow-the-ridge) policy with the following property: in two-player unconstrained games, a point is strictly stable under double-FTR if and only if it is a differential Nash equilibrium of the underlying game.

This contribution may be seen as an extension of an earlier result of Mazumdar et al. (2019) who showed that in two-player unconstrained *zero-sum* games, a point is stable under a certain preconditioned gradient process if and only if it is a differential Nash equilibrium. The method of the current paper is also a preconditioned gradient process, so the basic differences with the work of Mazumdar (2019) are that (a) the current paper treats general-sum games and (b) the dynamics have a simpler preconditioner.

Since the analysis hinges on the derivatives of the game's defining vector field near a solution, the zero-sum/general-sum extension was deemed relatively incremental compared to the work of Mazumdar et al. The simplification of the preconditioner is more interesting, but as was pointed out during the review phase, it comes at the cost of forcing the game to be convex-concave (because the individual Hessian of each player's loss function must maintain sign throughout, and it must be positive at the equilibrium in hand, so it must be positive everywhere). The authors's response to this point was to propose a change in the preconditioner; however, the proposed change brings the dynamics even closer to those studied by Mazumdar et al, so the proposed fix is somewhat tenuous and would require reviewing the paper from scratch.

There were also concerns that some of the authors' claims are not adequately supported by the theory. One has to do with the link between DNE and stable points of GDA: the authors state correctly that GDA could have stable points that are not DNE, not even Nash (this observation goes back at least to Daskalakis and Panageas, 2018). However, they also state the converse statement, namely that there exist DNE that are not stable under GDA - but the instability figures provided in the paper were not a clear indication of this.

Finally, the authors seem to suggest that double-FTR also avoids spurious limit cycles but, again, the evidence for this is not conclusive - in particular, it was not clear to what extent the avoidance illustrated in the experiments was initialization-dependent or not.

Because of the above limitations, a consensus was reached to make a "reject" recommendation.
justification_for_why_not_higher_score: The authors treat an interesting problem, but given the earlier work of Mazumdar et al. are, the paper's contributions were not deemed sufficient and the change in the dynamics would require a thorough rewrite and a fresh set of reviews.
Decision: Reject