Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper establishes lower bounds for finding approximate stationary points of min_x max_y f(x;y), where f is nonconvex in x and strongly concave in y. With deterministic gradients, the lower bound matches the convergence rate of the accelerated "Minimax-PPA" algorithm from [Lin et al. '20b], settling the oracle complexity in this setting, combining the bump-function construction of [Carmon et al. '19] with the classic zero-chain construction for convex optimization. A stochastic gradient oracle is constructed, following the same stochastic zero-chain construction as [Arjevani et al. '19], providing a lower bound scaling as \kappa^{1/3} / \eps^4 times the variance. 
main_review: - This paper settles the oracle complexity of a problem that has seen a flurry of recent theoretical and empirical interest. It fills a clear gap in the literature, and leaves an interesting question about the possible suboptimality of the best known algorithm for the stochastic setting. The exposition is very clear.
- My overall assessment of this paper depends on whether or not the cited work [Zhang et al. 21] ("The complexity of nonconvex-strongly-concave minimax optimization"), which appeared on arXiv on March 29, 2021, counts as concurrent. It is claimed that the proofs and construction are different, but from what I could tell, Zhang et al. also arrive at a "zero-chain within zero-chain" construction, and the proof is not that conceptually different.
- [Zhang et al. '21] themselves refer to concurrent work which was posted 2 weeks prior ([Han et al. '21], "Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction"), which also has overlapping material.
- The treatment of the pure stochastic (as opposed to finite-sum) case is still new, and the modification of the construction to get a stochastic oracle with bounded variance is fairly subtle. However, in my opinion this does not suffice as a standalone novelty.
- If the authors could articulate the differences vs. these works more clearly, this would be helpful towards reaching a conclusion independent of the concurrency issue.

Small typos:
- 247: "effictive"
- 248: "suppose" -> "supposing"
limitations_and_societal_impact: The work is purely theoretical in nature. The discussion of limitations is adequate.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper aims to provide lower complexity bounds for nonconvex-strongly-concave (NC-SC) minimax optimization problems. It shows $\Omega(\sqrt{\kappa}\epsilon^{-2}) for the deterministic setting and $\Omega\left(\sqrt{\kappa} \epsilon^{-2}+\kappa^{1 / 3} \epsilon^{-4}\right)$ for the stochastic setting. The lower bound for the deterministic setting has been nearly matched by several upper bounds, so it should be tight. 
main_review: $\textbf{Originality}$: I believe the work is original. The idea in section 5.1 to glue two zero chains is novel and interesting to me. 

$\textbf{Clarity}$: The structure of the paper is well-organized. The writing is clear, except a few grammar errors, such as in line 177-178. 

$\textbf{Significance}$: To discover the lower complexity bound in NC-SC is an important task. Stochastic algorithms are widely used in practice, but the lower bound in this setting is under-explored. This paper is an initial step. 

$\textbf{Questions and comments}$: 

1. One of my concerns is the contribution of the results. Except [Zhang et. al., 2021], the following paper appearing on arxiv this April also provides the same results for the deterministic NC-SC problems:
 "Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems:
The results and construction. arXiv preprint arXiv:2103.08280, 2021."
Therefore, the lower bound for deterministic setting can be showed by various methods. For the result of stochastic setting, although the paper shows the first result with the dependency in $\kappa$, it does not seem tight to me, and the gap with the upper bound remains. So I am not sure about the potential of this method. 

2. The stationarity measure used in the paper is $L_m\left\|P_{\mathcal{X}}[x-(1 / L_m) \nabla f(x)]-x \right\|_{2} \leq \epsilon$, where $L_m$ is the smoothness constant of the function $f_m = \max_x f(x,y)$. I am not sure whether there is existing upper bound that can nearly achieve this when $x$ is constrained. On the other hand, the upper bound it compares to requires the domain of $y$ to be bounded, while the hard instance the paper uses in the deterministic lower bound has unconstrained $y$.

3. Is it possible to extend the analysis to stochastic setting with the averaged smoothness assumption?
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper consider the lower oracle complexity bound of NC-SC min-max problems in deterministic and stochastic settings. Based on the zero-chain argument in previous first-order optimization literature, the authors proposed a novel hard instance construction and shows that the lower bounds are $\mathcal{O}(\sqrt{\kappa}\epsilon^{-2})$ for deterministic setting and $\mathcal{O}(\sqrt{\kappa}\epsilon^{-2}+\kappa^{1/3}\sigma^2\epsilon^{-4})$ in stochastic case. 
main_review: As pointed out by authors, exploring the lower bound of NC-SC min-max optimization problem is natural and imporatant following many recent works on nonconvex optimization and NC-SC algorithms works. The flow of the paper is very clear.

The main technique of the lower bound proof comes from previous lower bound works on convex optimization [34,36] and nonconvex optimization [3,5,6,13], i.e. the zero-chain argument. While the detailed hard instance construction, in my opinion, is novel and inspiring, especially the design of the subchain, which formulate a multiplication in the dimension numbers to get the final lower complexity results.

This paper considers deterministic and stochastic cases, while as authors pointed out, there is already concurrent works on deterministic case with the same result, the analysis in the stochastic case should be the first nontrivial result specifically in NC-SC min-max literature, even though there is still a large gap in terms of the dependence on the condition number ($\kappa^{1/3}$ vs. $\kappa^3$), this result should still be important.

Some problems:
1. Line 599 in the Appendix, is it $||u'||$ and $||P_C(u')||$, rather than solely $u'$ and $P_C(u')$? Also I think it should be $||\cdot||$, rather than the absolute value sign $|\cdot|$.
limitations_and_societal_impact: This work does not involve issues related to the negative impact of society.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposed a novel first-order oracle lower complexity bound for finding stationary points of smooth min-max optimization problems where the objective function is nonconvex in min variable, and strongly concave in max variable. The lower bound of $\Omega(\sqrt{\kappa}\epsilon^{-2})$ in deterministic setting matches the recent upper bound (up to log factors), hence is nearly optimal. Another lower bound of $\Omega(\sqrt{\kappa}\epsilon^{-2} + \kappa^{1/3}\epsilon^{-4})$ is provided for stochastic oracles, suggesting that the best-known upper bound of $O(\kappa^3\epsilon^{-4})$ is far from optimal in the condition number dependence. Overall, this paper is nicely written. The authors did a fantastic job in reviewing SOTA results, and put the newly derived lower complexity bounds in context. High-level explanations of the construction idea was provided, which makes it much easier to understand the proof and the complexity bound. The obtained results, to the best of my knowledge, are new and significant.
main_review: I only have some minor comments. 

Throughout the paper, the authors assumed the algorithm to be zero-respecting (Definition 4) and claim that there is a standard reduction from a lower bound for zero-respecting algorithms to that for arbitrary deterministic algorithms [3][5]. However, these cited papers are mostly based on the classical resisting oracles initialized by Nemirovski, A.S (to my knowledge)

Nemirovski, A.S.: Information-based complexity of linear operator equations. J. Complexity 8(2), 153–175 (1992)

Nemirovsky, A.: On optimality of krylov’s information when solving linear operator equations. J. Complexity 7(2), 121–130 (1991)

Such resisting oracle seems not easily extended to study general min-max optimization problems beyond the quadratic case; see the following article. 

Ouyang, Y. and Xu, Y. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems, Mathematical Programming volume 185,1–35 (2021). 

It would be better to elaborate this issue more clearly in the paper. 

Theorem 2 is particularly interesting to me, especially the condition number dependence of $\kappa^{1/3}$. Any intuition behind the order? Any insights on which algorithm might achieve this lower bound?  


limitations_and_societal_impact: This is a great paper which presents its ideas clearly and proves a good result, and it should be accepted to NeurIPS. I have no further complaints.
review_title: null

Meta-review: The paper provides a complexity lower bound for first-order optima for smooth non-convex and strongly concave min-max problems. The reviewers were unanimous in their appreciation of the construction of the lower bound and the result of the paper. The main concern with the paper is the presence of concurrent work which decreases the novelty of the result of the paper. The reviewers have nevertheless found the paper solid and the improvements/differences somewhat nicely articulated. I strongly suggest the authors to highlight the differences between the paper and the exisiting works clearly in the final version. 
Decision: Accept (Poster)