Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose an algorithm named TiAda which is a time-scale adaptive algorithm for non-convex-strongly-convex (NC-SC) minimax problems. The algorithm is a single loop and problem-specific parameter agnostic one, which are improvements over the related prior work. The authors provide insight into the design of the algorithm, theoretically analyze the algorithm and empirically validate its usefulness of the algorithm.  The authors also provide some generalization of TiAda to other adaptive methods and empirically validate their usefulness against related baselines.

strength_and_weaknesses: **Strengths:**

1. The proposed method improves upon the main related prior work such as similar implementation in deterministic and stochastic cases (agnostic to the noise level in the gradient). It does not need complex subroutines in the inner loop update for termination.
2. The work provides extensive validation of the proposed method against related baselines, in their experimental setting, and provides an ablation over some proposed algorithm-specific parameters.
3. The intuition of the work is clear and the paper is easy to follow.

**Weaknesses:**

1. The rate obtained in Theorem 3.2 is worse compared to state-of-the-art Na-Ada. Could you explain the reason behind this worse rate?
2. It is unclear how the list of values for r is chosen for results in Figure 2. What is the reason for choosing different orders of ratios for the two other experiments? It seems like NeAda would perform better for smaller choices of r. Furthermore, how was $\eta_x$ (or $\eta_y$) chosen for these experiments?
3. It is not clear why Na-Ada is not included in GAN simulation in Figure 4. 
4. Some typos in the text (e.g. definition in Assumption 3.2). 

clarity,_quality,_novelty_and_reproducibility: The paper is well-written and easy to follow. The intuition behind the algorithm is clear. While the algorithm has some features of prior work, the improvements made by the proposed method are somewhat novel.

summary_of_the_review: The paper proposes a parameter-agnostic adaptive algorithm for solving NC-SC minimax problem. The authors have identified a gap in the literature in this regard and have provided a somewhat novel contribution. The authors provide the intuition as to why their solution addresses the prevailing issues, and theoretically and empirically justify their claims. The algorithm seems to be robust to the hyperparameter choices required by the algorithm, as per the results shown by the authors. The empirical results provided by the authors suggest the proposed methods outperform related baselines. There are some issues regarding the experimental setup in some of the empirical results, as mentioned above under “Weaknesses”. Furthermore, the theoretical results do not improve the prior work in the stochastic setting.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Finding an approximate stationary point of a nonconvex(-strongly-concave) minimax problem usually requires the knowledge of problem-dependent parameters, especially the step-size ratio between $x$ and $y$. The most relevant method, named NeAda, is the first parameter-agnostic (adaptive) gradient method for nonconvex minimax problems, but this is double-loop, does not have the optimal complexity, and has several other drawbacks as mentioned in the paper. This paper thus proposes a single-loop parameter-agnostic (two-time-scale) adaptive gradient method, named TiAda, which resolves aforementioned drawbacks of NeAda. There already exist single-loop two-time-scale adaptive gradient methods, but they only work with the knowledge of the problem-dependent parameters. The main new ingredient of the TiAda is having the effective step-size ratio of $x$ and $y$ being upper bounded by a decreasing sequence, making the ratio eventually decrease below the step-size ratio threshold. TiAda (with theoretical result) and other adaptive variants are found to work well in practice.
strength_and_weaknesses: - S1: The method is parameter agnostic.
- S2: This achieves the optimal complexity for the deterministic case, and the near-optimal complexity for the stochastic case, which improves upon those of NeAda.
- S3: This can be easily generalized to accommodate other existing adaptive schemes.
- W1: Although $\alpha$ and $\beta$ are chosen to be $0.6$ and $0.4$ as a default throughout the experiment, they are hyper-parameters that might ask for tuning in other practical problems.
clarity,_quality,_novelty_and_reproducibility: The contribution and the originality of this work are clearly written in the paper.
summary_of_the_review: This paper constructed a single-loop two-time-scale parameter-agnostic adaptive gradient method, named TiAda, for nonconvex  minimax problems, which resolves issues with the first existing parameter-agnostic method, named NeAda. This TiAda method is a simple modification of existing two-time-scale adaptive gradient methods for minimax problems, but it is quite effective both in theory and practice. I believe this work is an important step towards resolving the non-convergence in practical minimax problems.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors propose a single-loop adaptive GDA algorithm called TiAda for nonconvex minimax optimization that automatically adapts to the time-scale separation. The algorithm is parameter-agnostic and can achieve near-optimal complexities simultaneously in deterministic and stochastic settings of nonconvex strongly-concave minimax problems. The effectiveness of the proposed method is further justified numerically for a number of machine learning applications.
strength_and_weaknesses: Strength: adaptive stepsizes to nonconvex minimax problems in a parameter-agnostic manner.  


Weaknesses: experiment is too simple to verify the algorithm effectiveness. 
clarity,_quality,_novelty_and_reproducibility: clear to follow 

code provided for verification 
summary_of_the_review: The authors propose a single-loop adaptive GDA algorithm for nonconvex minimax optimization that automatically adapts to the time-scale separation. Only some simple experiment are conducted to verify the algorithm effectiveness.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a single-loop adaptive gradient-based algorithm for solving nonconvex-strongly-concave problem with provably efficiency. Previous works only consider directly applying adaptive update scheme to x and y separately thus break the time-scale separation rule which is vital for guaranteeing the convergence. In this paper, the author proposed to adopt a more conservative stepsize for x so that the time-scale separation rule can be followed. The method is simple but effective. The author provide both theoretical and empirical result to verify the effectiveness of their proposed algorithm.
strength_and_weaknesses: Strength:
(1) It seems to be the first provably efficient adaptive gradient-type algorithm in the non-convex-strongly-concave optimization
(2) The technique proof is solid and the method is very nature and intuitive
(3) This paper provides sufficient empirical evidences

Weakness:
The major weakness is the sample complexity result in the stochastic setting, which is slightly worse than the standard result (standard is $\epsilon^{-4}$ and this paper gives $\epsilon^{-4-\delta}$). It seems that this additional $\delta$ is caused by the single-loop structure and the stepsize scheme thus is hard to improve. I notice that in the experiments the value of $\delta$ is not very small, which means that in theoretical the convergence rate is much worse than SOTA.
clarity,_quality,_novelty_and_reproducibility: (1) How would the algorithm performs if the value of $\delta$ is very small, e.g., at the order of 1e-4 ?
(2) I feel like the additional dependence on $\delta$ is mainly caused by the single loop structure. If we design the algorithm in a nested-loop way, in which we apply adaptive gradient update for both x and y separately, then it seems that we have a good chance to obtain a total sample complexity of $\epsilon^{-4}$, which is better than the rate established in this paper. Can the author discuss a little more about that? If that is the case then the contribution of this paper might not be strong enough.
summary_of_the_review: Overall this paper is well-written and easy to follow. The algorithm proposed in this paper is also very interesting and intuitive. The only weakness of this paper is its sample complexity result in the stochastic setting, which could either caused by the nature of the algorithm or the proof technique. I will give borderline accept score for now. If the author can address such an issue later I will consider further increase my score.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a single-loop adaptive gradient-based algorithm for solving nonconvex-strongly-concave problem with provably efficiency. The results achieve the optimal complexity for the deterministic case and the near-optimal complexity for the stochastic case. Moreover, the work provides extensive validation of the proposed method against related baselines, in their experimental setting, and provides an ablation over some proposed algorithm-specific parameters.

The authors have also addressed the concerns from the reviewers properly and most of the reviewers are happy to support its publication. Please consider the comments and suggestions from the reviewers and incorporate them into the final version. 

justification_for_why_not_higher_score: - The results are not really surprising. 
justification_for_why_not_lower_score: - The results achieve the optimal complexity for the deterministic case and the near-optimal complexity for the stochastic case. 
- Moreover, the work provides extensive validation of the proposed method against related baselines, in their experimental setting, and provides an ablation over some proposed algorithm-specific parameters.
Decision: Accept: poster