Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors study the problem of solving specific classes of non-convex min-max optimization problems. More specifically, they consider the problem when the maximizing player optimizes a Polyak-Lojasiewicz or strongly concave objective. In contrast to existing work, the paper focuses on characterizing the convergence of gradient-based algorithms to local Nash Equilibria that are meaningful in game theoretical settings. The authors show that for non-convex PL games and under a strict saddle property, $\tau$-GDA  asymptotically converges to strict local minmax equilibria almost surely. For the class of non-convex strongly concave games, the authors show that $\tau$-PGDA converges to an approximate $epsilon$-local minmax equilibria. For both cases the complexity rate of the algorithms are provided.
main_review: The paper studies a significant topic that belongs to a vibrant research field. The paper is easy to follow and clearly written.
Despite being extensively studied in the past few years, the authors distinguish the paper by obtaining more stringent convergence guarantees. More specifically, they obtain convergence guarantees in regards to differential Stackelberg equilibria compared to assessing convergence to approximate stationary points in past works. The results presented are not very surprising since Danskin's (or a Danskin's like) theorem holds for these classes of non-convex settings. However, the results are not trivial and cleanly developed. 

I have the following concerns:

1. Some practical examples presented in section 1.2 do not apply to the non-convex PL/SC settings. Also in equation (3), should it be f_i?

2. Line 162: I believe the gradient does not always exist.

3. The authors define the constrained min-max problem, but then study the unconstrained problem. Also why f^* is defined in line 379.

4. A major concern is that the paper lacks experimental results. Motivating the class of problem under study with practical examples and  illustrating the results through empirical results would help improve the paper.



limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors focus on the analysis of gradient descent ascent dynamics with timescale separation to solve unconstrained min-max optimization for landscapes that are non-convex on the min player (say x) and strongly concave or satisfy the PL condition for the max player. They focus on the stability analysis and convergence rates of GDA (and its perturbed variant) to the local minimax points (defined in Jin et al paper "What is locally..."). The definition of local min-max points is that the max player plays local best response and the min player chooses a local minimum for the function \max_{y \in B} f(.,y) where B is a ball of small radius. The authors show that local min-max points are stable/ attracting for GDA dynamics; the learning rate of the max player must be naturally larger than that of the min player in GDA (in some sense y updates more often). They also show convergence in \tilde{O}(1/\eps^2) of GDA to an \esp- local min-max in the case of non-convex stronly concave landscapes and non-convex, PL and \tilde{O}(1/\eps^4) of SGDA for the case of non-convex strongly concave landscapes.  
main_review: I will start by saying that the fact that local minimax points are stable for non-convex strong concave or PL landscapes is not suprising since effectively the hessian with respect to y is negative definite (invertible) and all degenerecies are avoided (we can decide about stability by checking the eigenvalues of the hessian and not cheking third order terms) and moreover use the multiplicative property of the determinant and Schur complement to derive a relation between the eigenvalues of the Hessian, the lower right block matrix of the Hessian and its schur complement. What seems a bit more interesting is that all the other critical points are unstable (I feel that every critical point that is unstable, it is unstable because of the x variables (for the examined landscapes), is this true? The fact that we have convergence to local minimax is not surprising (similar result appears in https://arxiv.org/abs/1902.08297), I like though that the authors use potential argument to show this fact.

The result about SGDA follows standard machinery for perturbed GD dynamics (see Jin et al 2017) and the \tilde{O}(1/\eps^4) was expected. Overall, I think the paper is an interesting but not super strong. Can also the authors argue about constructing functions (non-convex in x and PL condition in y) with a critical point the corresponding matrix of which has at least one imaginary eigenvalue (for the continuous time dynamics)? Which parts of the proofs carry over for constrained min-max optimization?
limitations_and_societal_impact: The paper is theoretical and the reviewer does not see any societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies gradient descent ascent learning dynamics with timescale separation in unconstrained continuous action zero-sum games. The minimizing player faces a nonconvex optimization problem, and the maximizing player optimizes a Polyak-Łojasiewicz (PŁ) or strongly-concave (SC) objective. Like [15], this paper assesses convergence to Stackelberg equilibria instead of only notions of stationary. A differential Stackelberg equilibrium corresponds to a joint strategy at which the minimizing player is at a local optimum to its choice variable along the best response curve of the maximizing player, and the maximizing player is at a local optimum concerning its choice variable. In pursuit of this goal, the authors prove that the only locally stable points of the continuous-time limiting system correspond to strict local Stackelberg equilibria in nonconvex-PŁ and nonconvex-SC games. Specifically, this paper exploits timescale separation to construct a potential function of the nonconvex-PŁ game that gives a global asymptotic almost-sure convergence guarantee to the set of strict local Stackelberg equilibria with the stability and asymptotic saddle avoidance. Moreover, this paper shows that nonconvex-SC games do gradient descent ascent provably converge in an almost sure asymptotic sense and a finite time escape time from saddle points.

Overall, this paper gives some theoretical contributions, with the caveat for the clarifications of the assumptions and the shortage of empirical studies. 
main_review: For the theory, there are a few assumptions that need clarification and further clarification on novelty. Theorem 1 is established for non-convex PŁ games. Theorem 1 looks like a corollary of  [Theorem 1, 15].  Moreover, Theorem 1 does not give the choice of $\tau_*$. Although the PŁ and SC conditions bring the global asymptotic convergence of $\tau$-GDA and $\tau$-PGDA, the results of Sec. 5 and 6 are familiar with non-convex optimization researchers. Therefore, the authors should include the results of [15]  in Table 1. 

Moreover, this paper ignores the empirical studies at all. The authors claim that fair classification, adversarial training, and distributionally robust optimization belong to the class of games they consider. None of these applications are conducted in the paper. It intensified the reviewers’ concerns about the above assumptions. Although the code is in the supplementary material, numerical visualization is an indispensable part. 


limitations_and_societal_impact: Yes
review_title: null

Meta-review: The authors study the behavior of simultaneous gradient descent-ascent with timescale separation (i.e. a slower learning rate for the descent dynamics compared to the ascent dynamics) to solve unconstrained and sequential min_x max_y f(x,y) optimization problems for objectives f(x,y) that are nonconvex wrt the variables of the outer (min) player and strongly concave or satisfy the PL condition wrt to the variables of the inner (y) player. 

They focus on the stability analysis and convergence rates of GDA (and its perturbed gradient variant) to local minimax points. The definition of local min-max points is that the max player plays a global best response to min, while the min player chooses a local minimum for the function \max_{y \in B} f(.,y) where B is a ball of small radius. The authors show that local min-max points are stable/attracting for GDA dynamics, as long as the learning rate of the inner/max player is large enough compared to that of the min player. For nonconvex-strongly concave landscapes, they also show convergence in \tilde{O}(1/\eps^2) of perturbed GDA to an \esp- local min-max  and \tilde{O}(1/\eps^4) of perturbed SGDA.

Prior work had shown convergence to stationary points of \max_{y \in B} f(.,y) (for a slightly different algorithm) and this work does stability analysis to argue that the points it converges to are actually local minima. Stability analyses had also been done for related algorithms. So at a high level the results here are not surprising. Yet, they are not trivial. Doing the complete analysis to establish the results requires quite a bit of work, and this is the first paper that goes beyond stationarity. Given that min-max optimization for objectives that are not convex-concave is an interesting direction for the field, this is a solid contribution. 
Decision: Accept (Poster)