Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes an adaptive framework, called NeAda, for solving nonconvex-strongly concave (NC-SC) minimax problems which achieves the best-known rates both in the deterministic and stochastic settings up to logarithmic factors, while being agnostic to the problem parameters. These results are achieved when the NeAda framework is run with AdaGrad for the minimizing player. They also provide a set of independent but complementary results such as non-convergence of gradient descent ascent, the high probability convergence of NeAda-AdaGrad and regret bounds for a generalized parameter-agnostic AdaGrad template. The authors also provide a set of experiments demonstrating advantages of their framework.
strengths_and_weaknesses: __Note__: _I was assigned to the paper as an emergency reviewer, therefore I haven’t had long enough time to have a detailed look at the paper and the supplementary. My score is given with caution based on the points that I am confused about. I am willing to engage in discussions with the authors and possibly update my score accordingly. In case I made mistakes or misinterpreted anything while evaluating the work, please indicate them for me so that I will provide a better review and fair judgment of the paper._

The paper is structured in a good way; listing the contributions early on and building upon the idea of parameter-freeness. The possible empirical advantages of the nested framework that runs for multiple ascent iteration per update of the minimizing player are also presented to have a nice basis for the theoretical claims.

The proposed setting with the set of assumptions relaxes some of the restrictive assumptions in the literature, one of which is the removal of bounded stochastic gradients assumption. This assumption appears frequently in the analysis of adaptive AdaGrad-type methods and its removal is a good step forward in my opinion.

Lemma 2.1 provides a set of nice but fairly expectable results (with analogous results known for convex-concave setting). With Figure 1, I think it complements one of the main arguments around the learning rate ratios and shows how NeAda framework is less sensitive to ill-approximation of such a ratio.

Presentation of Theorems 3.1, 3.2 and 3.3 are accompanied with relevant remarks and clarifications. The convergence rate is noise-adaptive, which I think is important.

As an independent results, Theorem 3.4 is a nice contribution in terms of parameter-free online learning and adaptive regret bounds for strongly convex losses.

Experimental results are somewhat encouraging; Figure 2 demonstrates possible scenarios where the nested algorithm proves useful, while Figure 3 gives some clues about the performance improvements it would offer for optimization/generalization tasks.

--

From the very beginning, it must be clarified for which adaptive algorithms the paper provides the convergence analysis and rates under the nested structure. The first bullet point at line 56 suggests that NeAda framework provably works with multiple adaptive algorithms, whereas the paper focuses on AdaGrad and its theoretical behavior. Although the second bullet point clearly states that the almost-optimal rates are achieved for NeAda-AdaGrad, I would suggest to make it clear at all parts of the paper that theoretical results are presented for NeAda-AdaGrad only.

The statement of Theorem 3.2 is not precise enough; it is not clear what quantities are bounded and how it implies the total sample complexity (e.g., no clear reference to $\mathcal E$). I would suggest the same for Theorem 3.3. I believe using the versions from the appendix, or some modification of theirs, would be better. 

The quantity $\mathcal E$ is actually a crucial part of the total sample complexity, and I would suggest to talk about it before Theorem 3.1. This would give some grounds for the results in Theorem 3.2 and 3.3 while explaining implications of the convergence rate in Theorem 3.1

One important contribution of this paper is enabling any linearly-convergent algorithms for strongly convex-minimization to be used in the NeAda-AdaGrad algorithm. However, this also creates a problem. From my understanding, parameter-agnostic property depends on the subroutine $\mathcal A$ and its properties. As long as there exists a parameter-free algorithm that converges linearly under the assumptions of Theorem 3.1 for strongly convex minimization problems, the claims hold. However, I am not sure whether such an algorithm exists. Could the authors please clarify this point for me? 

questions: __Small comments:__
- Theorem 3.1 is referred to as Lemma 3.1 in line 199. It is referred to as a "lemma" in multiple places in the paper.
- What is $\xi_t$ in Algorithm 4, line 4?

__Questions:__
- Lemma 2.1 provides divergence result in terms of the last iterates. I wonder whether there would be any conditions on the learning rate ratios that implies divergence when we consider the average iterates.
- As far as I understand, Ne-Ada framework proposes a concrete parameter-agnostic subroutine for the _minimizing_ player with adaptive step-sizes, however, it assumes the existence of a parameter-agnostic linearly-convergent algorithm $\mathcal A$ without proposing a proof for a particular algorithm $\mathcal A$. Is there any linearly-convergent parameter-agnostic algorithm that works under the precise set of assumptions that the authors propose in the Theorem statement 3.1?
- Although the analysis of NeAda requires a linearly-convergent algorithm to achieve the almost-optimal rates, the regret rate in Theorem 3.4 does not imply that Algorithm 4 converges linearly. Hence it may not satisfy the theorem statement. Is there an immediate extension of the regret rate in Theorem 3.4 that would yield a linear rate in the offline setting? To my knowledge there is no such conversion scheme.

limitations: One comments I have is with respect to subroutine $\mathcal A$ in Algorithm 3. Authors talk about some candidates but there is no clear discussion of whether any such algorithm satisfies the set of assumptions of Theorem 3 while being parameter-agnostic. I would suggest to have a more thorough discussion on this. Other than that, I think authors discuss the limitations and shortcomings of their results with respect to the literature.

To my knowledge, this work does not seem to have any potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Contribution summary:
The authors investigate two frameworks for adaptive minimax optimization: one is a simple (non-nested) adaptive framework, which performs one step of update of x and y simultaneously with adaptive gradients; the other is the nested adaptive (NeAda) framework and
provide the convergence analysis for a representative of NeAda that uses AdaGrad step size. In addition, there are two other complementary contributions which are a proposed AdaGrad step size and high probability convergence results. The authors also include empirical results for comparison with existing algorithms.
strengths_and_weaknesses: Strengths:
- First adaptive nonconvex minimax optimization algorithm? There exists literature for adaptive minimax optimization but not for nonconvex.
- The existing NCSC optimization algorithm has O(1/eps^2) oracle complexity and O(1/eps^4) sampling complexity. While the algorithm achieved the same rate, it does not require knowledge of the parameters like existing algorithms. The analysis of the algorithms does not follow trivially from existing literature. Some results such as theorem 3.1 also do not require common assumptions such as bounded gradient.
- Showed an example where GDA/non-nested methods does not work without prior knowledge of the parameters.


Weaknesses:
It incorporates AdaGrad step size which is widely known, but it seems the theoretical contribution is significant enough.

The algorithm does not necessary converge faster existing algorithms but it does have the advantage of being robust.


questions: N/A
limitations: See weaknesses.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes an adaptive algorithm for non-convex-strongly-concave minimax optimization, where the step size does not depend on the problem parameters, e.g., $L$ of $L$-smoothness, and $\mu$ of $\mu$-strong concavity.
The algorithm has two loops: in the inner loop, the corresponding strongly-concave problem of $y$ given $x$ is approximately optimized by executing an off-the-shelf adaptive algorithm for a sufficiently number of iterations; while in the outer loop, an adaptive gradient descent step is used to update $x$.

strengths_and_weaknesses: The topic of developing adaptive methods with theoretical guarantees is interesting. However, at the current point, I hesitate to recommend the acceptance for the following reasons, and I would like to get some clarifications.

1. While I understand the goal in this paper is to get an adaptive algorithm that does not need the knowledge of the problem parameters, getting a stationary-point guarantee on x for the class of non-convex-strongly-concave minimax optimization via applying adaptive methods on both x and y seems a bit straightforward to me, in my opinion. It would be more helpful for the evaluation if the challenge in the design and analysis of the algorithm can be highlighted.

2. Remark 2 for Theorem 3.1 says "the algorithm attains convergence for the nonconvex variable x with any choice of $\eta >0$".
But from line 185, if we set $\eta = T$, then $A=\Omega (T)$ and therefore the second term 
$\frac{\sqrt{A+ ...} }{\sqrt{T}}$
on the r.h.s. of the bound of the expected gradient norm in Theorem 3.1 will be $\Omega(1)$. So the convergence does not hold for any step size $\eta$.


3. The purpose of introducing Algorithm 4 is not clear to me. Remark 5 mentions that FreeFREXMomenetum and Coin-Betting can be used for the inner loop of Algorithm 2. Given this, what is the point of having Algorithm 4? 


4. (The first inequality on Page 22) How to get the last term on the r.h.s. of the first inequality on Page 22, i.e., $2 \kappa^2 \\| x_t - x_{t+1} \\|^2$? 
It seems to me that the last term arises from bounding the last term on the last inequality on Page 21, i.e., by bounding $\\| y^*(x_t) -  y^*(x_{t+1}) \\|^2$. How to use Lemma A.1 to get the result?


Minor:

There seems a typo in the definition of Assumption 3.2, i.e., $\nabla_x f(x,y_2)$ <- $\nabla_y f(x,y_2)$.


questions: see above
limitations: N/A
review_title: null

Meta-review: metareview: During the rebuttal it was agreed that this paper provides good explanations regarding the machineries 
that allow to guarantee convergence for minimax non-convex - strongly-concave problems.
The nesting technique together with the adagrad stepsize are nicely composed, and the proof technique is non-trivial. I therefore recommend to accept.
confidence: Certain
Decision: Accept