Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper considers a min-max optimization of general nonconvex functions. The paper proposes methods to approximately find stationary points by "smoothing" the max part. Experimental results show the superiority of the proposed approach to previous work. 
main_review: The topic of the paper is quite relevant in the community. The main idea makes sense and the experimental results are quite impressive. 


Technical Issue:
- I am afraid that the gradient of an algorithm is not well-defined. How do you compute the gradient? Probably the paper assumes that the algorithm trains a neural network and its gradient is that of the network. Please clarify it. 
summary_of_the_review: The paper is good enough and it is supported by experimental results.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper focuses on solving minimax optimization when the maximization oracle has a limited amount of computation power and can not compute the max exactly. They provide SGD based and proximal algorithms and analyze them for weakly convex function.
main_review: 1) Their algorithms need $O(\epsilon^4)$ gradient queries. It would be great if the authors can clarify that is this tight bound or can we achieve better complexity and if we can what would be a proper approach.

2)The setting is novel and interesting from a practical and theoretical point of view.

3)Author motivates the subject from a theoretical and practical point of view. 

4)In the introduction, the author reviewed the previous works carefully.

5)The authors successfully provide simulation results for their algorithm.

6)The paper is well-organized and well-written.

7)the code is included.

summary_of_the_review: 1) Their algorithms need $O(\epsilon^4)$ gradient queries. It would be great if the authors can clarify that is this tight bound or can we achieve better complexity and if we can what would be a proper approach.

2)The setting is novel and interesting from a practical and theoretical point of view.

3)Author motivates the subject from a theoretical and practical point of view. 

4)In the introduction, the author reviewed the previous works carefully.

5)The authors successfully provide simulation results for their algorithm.

6)The paper is well-organized and well-written.

7)the code is included.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides a new perspective to solve the nonconvex-nonconcave minimax problems. Specifically, the proposed method turns the nonconvex-nonconcave minimax problem to a nonconvex-concave minimax problem by using a toolkit of multiple smooth algorithms to find a solution of the maximization problem given fixed $x$. Moreover, it studies the convergence properties of the proposed algorithms. Some experimental results on generative gdversarial networks and adversarial training demonstrate the efficiency of the proposed algorithms. 
main_review: Some comments:

1) The authors should provide the gap between the original nonconvex-nonconcave minimax problem $\min_x max_y f(x,y)$ and the obtained nonconvex-concave minimax problem $min_x max_{i\in [k]}f(x,\mathcal{A}_i(x))$ in both the theoretical and experimental aspects. 

2) Assumption 1 given in the paper may be not mild. So the authors should detail whether these assumptions are used in the existing methods.

3) Recently many existing methods have studied the nonconvex-concave minimax problems. The authors should point the differences between the nonconvex-concave minimax problem (1) given in the paper and the generic nonconvex-concave minimax problems studied in the existing methods. 

4) The authors study the convergence properties of the proposed algorithms to solve the nonconvex-concave minimax problem (1) given in the paper. Compared the existing studies on the generic nonconvex-concave minimax problems, what are challenges? 

summary_of_the_review: Overall, I like this paper. I hope the authors can deal with the above comments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper is trying to address the problem of non-convex non-concave min-max optimization under the perspective of application of smoothed algorithms between the two opponents. More precisely,
the paper examine a model where the max-player applied a zero-memory smooth (from differential perspective) algorithm and min-player SGD/SNAG or proximal methods providing results similar with the state of art. The convergence is reassured by "potential" arguments but the fixed point is not an equally game-theoretic notion like Nash Equilibrium.
main_review: Firstly, I would like to mention some technical details in the proofs of the primary appendix sections.

Issue #1.[Lemma 2] In the lemma about the max of L-weak convex functions and its subgradient, the proof shows only the inclusion not the completeness. More precisely, from the proof I can see why the linear combinations of gradients correspond to subgradients of the max-functions. On the other hand, this does not show that all subgradients can be written in this form? 

Please provide a new proof OR correct the statement and explain why a refined statement suffices for our task. A priori, I believe that the result should be correct as a generalization of Danskin's Theorem.

Issue #2.[Lemma 3] The statement of the lemma is correct since they are folklore truths for proximal descent. HOWEVER, the proof that you provide has some mathematical flaws. 
Example: You say that min g(x) = min g_\ell(x) and then you say that  " Thus argmin g(x) = argmin g_\ell(x)". In general this is not correct for two function f_1,f_2 (i.e f_1(x)=|x|,f_2=|x-1|)
The only way that I know to show the result is via the facts that $argmin g(x) = fixpoints(proxGD)$ and 
$argmin g_\ell(x) = fixpoints(proxGD)$

Similarly for item (c), I was not able to parse the argument. Could you please explain in a list the statements of the proof 

MAIN CONTRIBUTION:

I really like the idea of the "smoothed adversary" as a refined benchmark. i agree that a better framework would be if we "constrain" the opponent in order to examine if it is possible to find efficiently a good solution. I appreciate the model and the conceptual, "easily"-understandable results and the well-written part of main paper. I don't like the fact that authors do not explain(hide) explicitly that the smooth adversaries have not memory in comparison with its opponent. If this is correct, I would appreciate some addition in the text which will explain that. Finally, there are two issues about the results:
(1) we don't have convergence to a Nash equilibrium or local \eps-Nash equilibrium but to a point which is biased against the "inner" player. (2) The novelty of the results is limited since the algorithmic concepts ,that are used, are somehow blackboxes. On the other hand, I understand that the main idea is to explain why the case of "smooth adversaries" is a tractable case.

In general I would like some answers in my "complaints"/ "issues" that I raised. I believe strongly that with a satisfying answer I will increase happily my score.
summary_of_the_review: While there are some typos and restriction, I strongly appreciate the model design which consists the backbone of the paper. Shortly describing, I like the main message of the paper even if there are main details that should be clarified and corrected to express the exact result that can be derived from the paper.
review_title: null

Meta-review: The paper addresses the problem of non-convex non-concave min-max optimization under the perspective of application of smoothed algorithms between two opponents.
The paper examines a model where the max-player applied a zero-memory smooth (from differential perspective) algorithm and min-player SGD/SNAG or proximal methods providing results similar with the state-of-art. Convergence guarantees proposed were sound and experimental results on generative adversarial networks and adversarial training demonstrate the efficiency of the proposed algorithms.
Decision: Accept (Poster)