Venue: NeurIPS 2022 Conference

Reviews:

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: The goal of the paper is to understand which metrics (when being small) imply that a solution of the minimax problem (using a dataset) also behaves well on the expected loss. First, the authors provide a negative example showing that “generalization error in primal risk” being small is not sufficient. Then, the authors provide a new metric namely “generalization in the primal gap”, which the authors explain is a better metric. They then consider two popular algorithms for minimax optimization - GDA and GDMax and provide conditions under which one is better than the other. 
strengths_and_weaknesses: Strength: The paper considers the important task of understanding the generalization of stochastic mini-max optimization (as an objective function in the primal variable). The problem is well motivated, and has significant potential of impacting practice. My sole reason to suggest a weak acceptance is the relevance of the problem! 

Weakness:  I think the paper has several weaknesses: 
1. At multiple places, authors mention that primal-dual gap is not sufficient, but I was unable to find a counter-example showing this. Did I miss something? 
2. The proof for \zeta^{PG}(A) being small implies a small generalization error is straightforward, but are there cases where $\zeta^{PG}(A)$ is small by  $\zeta^{P}(A)$ is not small? It seems that Lemma 1 and Theorem 2 are bounding $\zeta^{PG}(A)$ by first bounding $\zeta^{P}(A)$, which suggests that $\zeta^{P}(A)$ may very well be the right quantity. 
3. The comparison between GDA and GDMax just seems to follow from comparing the upper bounds. Lower bounds are missing, which suggests that the comparison is vacuous.
4. In that sense, are $\zeta^{PG}(A)$ pr $\zeta^{P}(A)$ metrics? Can you compute them a-priori or using data ? 

It seems that all that the paper is suggesting is that stable algorithm + additional structural properties, implies that minimax learner generalizes. Is that true? Why are the intermediate quantities $\zeta^{PG}(A)$ pr $\zeta^{P}(A)$ needed?

questions: Please find my questions in the strength and weakness section above! 
limitations: No foreseeable societal impact.
review_title: null

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: This paper studies the algorithm-dependent generalization property of stochastic minimax optimization problems in the nonconvex-concave or nonconvex-nonconcave setting. In particular, this paper gives two (non)concave minimax examples to support that generalization error for primal risk may not be enough to quantify the actual generalization error, due to the objective value differences between population and empirical optimal minimax learners. 
To study the generalization error for the primal risk, this paper relies on the tool of $\epsilon$-algorithmic stability [Hardt et al., 2016], and get a bound with sub-linear dependence on the $\epsilon$ for nonconvex-concave problems for the first time. The setting is hard since the Lipschitz continuity and the uniqueness do not hold anymore. Their main idea is to consider a virtual gradient ascent algorithm to fill up this gap.
This paper further investigates the generalization property of GDA and GDmax, and provides two examples and estimate on the capacities to show that GDA generalizes better than GDMax.
strengths_and_weaknesses: Strengths:
1. Solid contribution builds upon recent advances. This paper establishes generalization bounds for stable algorithms in terms of primal risk for (non)convex-concave problems and primal dual risk for convex-concave problems for the first time, relaxing the assumption on the strong concavity or the interchangeability between expectation and maximization. 
2. Analytic examples shed light on the understanding the lower bound and the parameter estimation for the generalization of minimax problems.


Weaknesses:
1. The writing can be improved as it causes difficulty even for experienced readers. Examples include but not limit to 1) Last column in Table 1 should refer to Theorem 7 rather than Theorem 6; 2) Using $r$ to denote the risk for minimization problems and primal risk for minimax problem at the same time is confusing; 3) Overall, the paper is very dense and somehow lack of organization, especially Section 4.  For example, Lemma 2 and Proposition 1 can be combined. Lemma 4 is underfull box. 
questions: 1. The assumption behind Theorem 3 is vague to me. Any references on why the convergence rate on the primal empirical risk can be achieved? The paper by [Du et al., 2019] does not seem to be consistent with the assumption in Theorem 3. 
2. Equation (9) has a positive lower bound while Line 238 suggesting that it could attain an upper bound of 0 when $n=1$. Do I miss anything in this example?
3. Some questions about experiments in Appendix D.5. In Line 715, it says "since the stability is improved by using adaptive methods like Adam...". Any references on why this is true? Why not use the vanilla GDA and GDmax? The generated results on MNIST by GDmax are bad and the norm of the discriminator weights seems way too large, (on a scale of 1e7 for an only 4 layers network). Any comment on the parameter tuning in this case?
limitations: 1. The necessity of proposing the "primal gap" can be checked and I think it is an artifact of writing the paper. In Line 220, we see the relation between the generalization error of the primal gap and primal risk is the extra error between the empirical minimax learner and the population one. This term is of course requiring attention since the final target is always to study the primal population risk defined in (2), but it is also algorithm-independent. The analyses of GDA and GDmax still focus on the generalization error of the primal risk. Overall, I think the main contribution should be Lemma 1 and Theorem 7 in the Appendix, and the title might be a little exaggerated. 
2. Despite it being the first work establishing generalization bounds for $\epsilon$-stable algorithms without strong concavity, the dependence on $\epsilon$ is not as good as before. While it can be argued that the assumption is weaker, it still draws back the primal population risk and primal dual population risk. For example, in the (non)convex minimization counterpart, such dependence is known to be $\epsilon$ [Hardt et al., 2016]. Furthermore, when the empirical risk is considered together in realization of Assumption 5 to study the population risk, it seems provide worse trade-offs.
review_title: null

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 a new metric, the primal gap, to study the generalization of minimax learners. The paper gives an overview of shortcomings of previous metrics for minimization problems (the primal risk and primal-dual risk) when they are applied to minimax problems. Then, it is shown that the primal gap metric works well specifically for minimax problems. Generalization bounds are derived, and as special cases applied to primal risk and primal-dual risk for the nonconvex-concave setting, showing new bounds there. Finally, comparisons between gradient descent-ascent and gradient descent-max are given. 
strengths_and_weaknesses: Overall, the results are interesting and the paper is nicely written. 

**Originality.** 
The paper proposes a new metric, the primal gap, for the generalization of minimax learners. The primal gap appears to be a slightly adjusted version of primal risk and primal-dual risk for the minimax setting. The paper discusses several generalization bounds under the primal gap --- see below sections for questions regarding comparisons with other work.

**Quality and clarity.** 
The paper is nicely written and results are stated clearly. There are some minor typos that are listed here for further revision:
- Table 1 contains a possible error: "in the in the theorems"
- Line 270: "generalizationerror"

**Significance.**
The study of minimax learning is important and the paper brings interesting results into this area. However, there are several issues. After the proposal of the primal gap, the main result is Lemma 1 and Theorem 2, but the example given in Section 3.4 is not very convincing. While the gap between the lower and upper bounds is only a log-factor, which is often ignored, in this case a difference between a constant factor and a log-factor is quite large. Further, it is unclear whether the dependence of $\sqrt{\epsilon}$ is optimal or not --- particularly in the regime with small $\epsilon$, it appears there is a large gap between the results here and previous results although they are given under stronger convexity constraints. The dependence on $C_p$ and $C_e$ is also not clearly addressed, as it appears factors of $n$ may be introduced, as evidenced by the example in Section 3.4.
questions: * Is the dependence of $\sqrt{\epsilon}$ optimal? It appears to be inconsistent for the (albeit different) setting under strong convexity.
* How do the parameters $C_p$ and $C_e$ affect dependence on $\epsilon$ and $n$? The example given in 3.4 shows that factors relating to $n$ may appear. 
* Following the above question, from the examples given in Section 4, $C_p$ and $C_e$ play a key role in comparing GDA and GDMax. Will a similar reasoning throughout the paper, when applied to the other settings given in Table 1, replace dependence of kappa and introduce terms related to $C_p$ and $C_e$? Are there further comparisons between the main results and the previous work? 
limitations: Limitations are not adequately addressed within the paper; see questions above.
review_title: null

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: This paper introduces an example to show that the primal risk metric has inadequacies in studying the generalization for minimax problems.

This paper then proposes a new metric – the primal gap to avoid the issue in the example.

This paper then leverages this new metric to compare the generalization behavior of GDA and GDMax.

Finally, this paper establishes generalization bounds for primal risk and primal-dual risk without assuming strong concavity.
strengths_and_weaknesses: Strengths:

The introduction is very clear. 

The generalization without assuming strong concavity has good contributions.

Weaknesses:

Does Theorem 1 (d) of the paper [1] study a more general stability measure of the primal gap? Can the authors provide a discussion?

Missing reference:

[1] Li, S. and Liu, Y. High probability generalization bounds with fast rates for minimax problems. In ICLR, 2022.


questions: For the minimax problem, good generalization behavior is defined on the primal function. My first question is why good generalization behavior should be defined on the primal function? Is this necessary and is this a unique pattern to measure the good generalization behavior for the minimax problem.

The authors provide the primal gap as a new metric to replace the primal risk. Although there have some explanations below Definition 4, I still do not understand why this metric is a good one. Can the authors provide a clear explanation?
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: This paper addresses the important problem of deriving generalization for minimax optimization algorithms.  It was shown using concrete examples that the existing measures of generalization (primal risk and the primal-dual risk) may fail to characterize the generalization behavior for minimax problems with nonconvexity.  It then proposed a slightly modified new metric called primal gap. Furthermore, the paper resolved an open question in the literature on how to establish generalization bounds for primal risk and primal-dual risk in the strong sense, i.e., without strong concavity. In the rebuttal, it was shown that the obtained rates are indeed optimal.  All reviewers acknowledged these novel contributions.  I recommend its acceptance accordingly.  

As reviewers RYz4 and VSNm mentioned, the presentation and wrting of the paper cause some difficulty in reading the paper and  recognizing the novel contribution of the paper.  I strongly encourage the authors to take their suggestions into account in their revised version. 
confidence: Certain
Decision: Accept