Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper introduces a first-order algorithm for nonconvex-nonconcave min-max optimization problems. The proposed algorithm terminates in time polynomial in the dimension and smoothness parameters of the loss function. The points (x*,y*) returned by the algorithm satisfy the following guarantee: if the min-player proposes a stochastic gradient descent update to x^*, and the max-player is allowed to respond by updating y^* using any “path” that increases the loss at a rate of at least \epsilon with high probability, the final loss cannot decrease by more than \epsilon. Then the algorithm is tested in GANs settings on mixtures of Gaussians, MNIST and CIFAR-10 datasets against compared against gradient/ADAM descent ascent and Unrolled GANs. The algorithm is shown to be significantly more stable than GDA (e.g. less mode collapse, cycling, and more stable digit generation).  

The paper works on the hard and ambitious problem of general non-convex non-concave optimization which has multiple AI applications such as GANs. On the proposed approach is novel considering a new solution concept and the paper provides some theoretical and experimental results. On the negative side neither the theoretical nor the experimental results seem particularly strong. 

My main issue on the theoretical side has to do with the solution concept itself. The solution concept seems unnatural to me. Definition 2.1 about \El_\eps(x,y) a critical notion about the ``path" that the max-agent is allowed to use is non-constructive and obtuse. The only closely related solution concept seems to be in a recent unpublished manuscript by Mangoubi and Vishnoi. Given the novelty of the solution concept I think the authors should have spent much more time building intuition about what this concept corresponds to especially in simple settings such as bilinear zero-sum games. It seems that effectively all states satisfy the definition of the provided solution concept in a bilinear game. E.g. suppose that we are arbitrarily far from the max-min equilibrium, the min agent suggests a small improvement step now the max agent can move in the direction of the gradient for arbitrarily long distance negating any gains by the small move of the min agent. This is clearly unnatural and explains why this algorithm can terminate fast, it is because it is willing to accept arbitrarily bad states as solutions. I think that this is a major shortcoming of the solution concept. The authors seem to agree that the solution concept is rather bad at times by explicitly allowing the dynamic to escape from these points with some small probability. The theoretical analysis is definitely non-trivial but if the proposed algorithm fails to solve even simple bilinear zero-sum games then the theoretical guarantees are not particularly strong. 

On the experimental side, the algorithm is being compared against weak benchmarks such as GDA. As the paper itself presents in the related work there have been a lot of recent developments on variations to the standard GDA techniques such as extra-gradient, optimistic methods, different types of averaging, etc which are known to significantly and robustly outperform GDA both theoretically and experimentally across numerous datasets. The reported FID scores are far from the state of the art and even the visual samples seem of relatively poor quality.

Overall, I believe the paper attacks a very hard problem and pursues an interesting idea but both the theoretical and experimental results seem to suggest to me that the proposed approach is not very promising.
review_title: Review

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper treats non-convex/non-concave min/max problems motivated by the respective problems that arise in GAN training. The main contribution is that they develop an ADAM-based algorithm that converges to \eps- local min/max points. The paper seems to be well-written and easy to follow. Moreover the proofs seem correct and sound. That said, my main concerns about this paper are twofold: 

1.The idea of dividing the min/max game into minimization/maximization problems is not new (see for example: Bolte et al. (2020) A Hölderian backtracking method for min-max and min-min problems). Therefore, a reasonable question would be how this work is related with this kind of results.
2. Additionally, it is not true that Extra-Gradient are only applicable for convex-structured problems (see for example: Mertikopoulos et. al ICLR (2019), Yu Guan Hsieh et.al NeuRIPS (2019)). Hence, I think a more detailed justification towards these approaches is needed.

Overall, without being an expert myself, I would gladly raise my score if the author(s) clarify these issues in a more detailed manner.

review_title: This paper treats non-convex/non-concave min/max problems motivated by the respective problems that arise in GAN training.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a new stochastic gradient descent-ascent-based method to approximate a stationary point (or local min-max solution) of a nonconvex-nonconcave minimax problem with application in GANs. The method is similar to the one in the GAN original paper, but the authors incorporate it with an acceptance rule and use a different model for the max problem. The algorithm also uses ADAM instead of standard SGD. The authors also provide some convergence guarantee to a local min-max point in polynomial-time complexity. Unfortunately, the reviewer was unable to verify the proof due to the time limit.

The reviewer finds that it is really hard to understand the proof techniques as well as the meaning of local min-max points defined in this paper especially via a neighborhood D_{x*,y*}. Many places are explained in words which are also hard to verify some of the statements. For example, Theorem 2.3 expresses the complexity in poly(...), which does not know what is the maximum order of epsilon. The proofs are also breaking into different pieces where so many technical details related to high probability statements are used. This makes another difficulty to check the correctness. To this end, the reviewer would like to raise the following question?
1. First, since the problem is nonconvex-nonconcave,  how can the algorithm guarantee that the min-play can always decrease the objective function with a certain amount that is fixed as stated in (5)?
2. Second, it is known that ADAM is not convergent even on a convex problem (see (https://openreview.net/pdf?id=ryQu7f-RZ)), do the authors use a modified variant of ADAM, or what has been changed to guarantee its convergence?
3. Third, in Definition 2, does D_{x*,y*} form a "full" neighborhood of (x*,y*) in the feasible set of f(x, y)?

review_title: A Provably Convergent and Practical Algorithm for Min-Max Optimization with Applications to GANs

Meta-review: All reviewers appreciated the main idea in the paper for solving the nonconvex-nonconcave minimax problems, which is deemed an extremely hard open problem. However, as R1 also pointed out, neither the theoretical nor the experimental results seem particularly strong, given that many variations of GDA and theoretical understanding of different notions of optimality have been recently developed. The paper fails to draw proper comparisons to these existing work. 
Unfortunately, the paper is slightly below borderline and cannot be accepted this time. 

Decision: Reject