Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: As a theory work, this paper considers the generalization of the minimax learning problems which has a wide applications in machine learning. In comparison with the results of the previous work, which either provide expectation bounds or high probability generalization bounds of $O(1/\sqrt{n})$, this paper gives improved high generalization bounds of $O(1/n)$. Besides, these bounds are applied in many popular optimization algorithms, including ESP, GDA, SGDA and so on.
main_review: Overall, I think this is a timely solid work for the minimax learning problems which covers many interesting topics. 

-------------------- pros

1. This paper is very well-written. 
2. It is valuable to move expectation bound to high probability bound or improve high probability bound from $O(1/\sqrt{n})$ to $O(1/n)$. 
3. It clearly discusses its relationships and differences with previous work. 
4. The proofs are overall right although I cannot check the proofs line-by-line. 

-------------------- cons

1. I have one concern is that how is the tightness of the achieved generalization upper bound,  and thus the lower bound might be discussed to illustrate it.
2. It might be better to add some synthetic empirical experiments to illustrate the tightness and effectiveness of these generalization upper bounds w.r.t. the true population risk. 

Besides, I have some questions as follows.

1. Why to define the strong or weak measures (Def. 1) like these? Please give more intuitive explanation.
2. For Theorem 1, what is the differences between (c.) and (d.)? I think they are the same, do I miss something?
3. For Theorem 1, what is the effect of variable $\eta$? Please give more discussions.
4. In Remark 1, authors repeatedly claims that what if argument stability and the strong PD empirical risk are of the fast order $O(1/n)$. While the argument stability with $O(1/n)$ can be understood, how to understand the strong PD empirical risk has dependence on the sample size $n$?

--------------------- Minor comments

Typos:

1. Page 4. head: $|| z ||_p = (\mathbb{E} \| z \|^p)^{1/p}$.


summary_of_the_review: While I think this is a solid theory work, it is better to add some discussions for the tightness of these generalization upper bounds, and some empirical validation experiments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper consider a stochastic minimax problem of the form $\min_x \max_y F(x,y)$ where $F(x,y) = \mathbb{E}[f(x,y,z)]$. The goal is to obtain ``fast'' rates of $O(1/n)$ with a training set of $n$ i.i.d. $z_1,\dots,z_n$ in high probability.
In this setting there are a variety of convergence measures one might consider, most notably perhaps the gap $\Delta(x,y) = \max_{\hat y} F(x,\hat y) - \min_{\hat x} F(\hat x, y)$. For these measures the fast rates are achieved for various specific problems such as strongly-convex-concave saddle-point detection. The main technique is to generalize classical results on algorithmic stability developed for stochastic minimization towards the stochastic minimax problem, and then to demonstrate that a variety of algorithms (mostly variants on gradient descent) are stable in particular settings.

main_review: This paper generalizes the algorithmic stability notions to the minimax problems and provides high probability bounds for some specific instances of problem/algorithm pairings when the problem has bounded values. I think this is a good contribution.

There are some issues with presentation and I think some of the statements are a little vaguer than they need to be. Instead of saying "the plain generalization error is $O(1/n)$" perhaps one could provide a precise statement about what exactly is $O(1/n)$ as otherwise readers have to go a back and interpret the results. In particular, from what I can see in part (a) of the main theorem, it was shown:
$$F(x,y) \le (1+\eta)F_S(x,y) + \tilde O\left(\frac{M+\epsilon}{\eta n}\right)$$
Now, how is one to read an $O(1/n)$ rate out of this? The $\tilde O(M/\eta n)$ part suggests $\eta=\Theta(1)$, but then I have a $2F_S(x,y)$. Is it the case that $F_S(x,y)=0$? This seems unlikely to me, but perhaps I missed something.

In fact, ALL of the statements made about generalization error rates suffer from this issue: I intuitively expect the thing that we are measuring the "rate" of to be True Value - Empirical Value, or maybe "True value at point produced by algorithm - Optimal True value", but it appears in Theorem 1 that we are actually looking at True Value - $(1+\eta)\times$ Empirical value, which seems a bit weird. Now, I believe that in many of the cases for specific algorithms (e.g. using the empirical minimizer), it might be that the empirical value is $0$ or $O(1/n)$ and so we have do have a fast rate as realized in the later theorems, but I think this is asking for a bit too much jumping ahead by the reader. Instead perhaps it is just the case that Theorem 1 provides a "self-bounding'' style result that in concert with specific algorithms can be used to obtain a $O(1/n)$ rate?

These things would be clarified if the statements about generalization error were quantified correctly in equations rather than prose.

However, while I am rather dissatisfied with these aspects of the presentation, I believe they can be rectified and if so the contributions are enough to merit acceptance.

summary_of_the_review: The paper provides new results in high probability that are valuable confirmation that standard algorithms will work well. The presentation leaves something to be desired, but is likely fixable in revision.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper conducted a comprehensive study of high probability generalization bounds for minimax problems in terms of various forms of measuring generalization such as strong/weak PD generalization and primal generalization error.  Given uniform stability $\epsilon_{stab}$,  it proved sharper bounds of order $O(1/n + \epsilon_{stab})$  while sacrificing the empirical error (e.g.   extra $\eta F_S(A(S))$,  $\eta \bigtriangleup^s_S(A(s))$ on the bound). The results improves the previous excess generalization bound $O(1/\sqrt{n}+ \epsilon_{stab}))$ when  $F_S(A(S))$ or $\bigtriangleup^s_S(A(s))$ is very small.  The results extend the existing work by Lei et al. (2021) where most of the bounds were derived in expectation and high probability ones are given by f order $O(1/\sqrt{n} + \epsilon_{stab})$.  Then, specific bounds were given for GDA, PPM and SGDA for the strongly convex and strongly concave case as they are uniform stable.
main_review: The results obtained in the paper are new and are very nice extension of the existing work on minimax optimization algorithms.  The related work is well cited and the paper is organized well.  I have the following comments and suggestions: 

1.  it seems that the paper overly claimed the improvement over the existing work. In the abstract and introduction, the authors claim that " improved generalization analyses for almost all existing generalization measures of minimax problems which enables the minimax
problems to establish sharper bounds of order $O(1/n)$, significantly, with high probability".  This statement appeared several times in the paper.  From my perspective, it is not correct and misleading since the excess bounds are precisely given in the form of  $O(1/n +  \epsilon_{stab})$ plus extra terms (e.g.   extra $\eta F_S(A(S))$,  $\eta \bigtriangleup^s_S(A(s))$.  Indeed, the excess strong PD generalization bound is given by $O({1 \over \eta n} +  \epsilon_{stab}  +   \eta \bigtriangleup^s_S(A(s)) ).$   For the reason above, the comparison results in Table 1 in page 8 is extremely vague and not precise.  The bounds stated in Theorem 2 and 3 are also incorrect because the extra term (e.g. $\eta F_S(A(S))$ or $\\eta \bigtriangleup^s_S(A(s))$ or $\eta\inf_w R(w)$) is ignored there. 

2. I never saw uniform stability for SGDA before:   uniform stability only holds true after taking expectation with respect to the internal randomness of the algorithm.   Indeed, the proof for Theorem 7 is not correct.  In this case, the uniform stability, i.e. inequality of (39) for SGDA holds with high probability.   But the whole of this paper is under the uniform stability assumption (NOT high probability form). Hence, you can not apply Theorem 1 to directly get the results in Theorem 7.  

2.  While the results are new and interesting, the proof techniques are directly modified from Klochkov and Zhivotovskiy (2021). 

3. Part (c) and Part (d) are duplicate as they are essentially the same results.



summary_of_the_review: Overall, the paper presents very nice high-probabilistic generalization bounds for minimax problems and improves the existing ones which are mostly given in expectation.  The main proof techniques are adapted from Klochkov and Zhivotovskiy (2021).  The paper is also well organized and related work is sufficient.  However, the claims about significant improvement over existing work and providing sharper bound $O(1/n)$ are not precise and need to be corrected.  The proof for Theorem 7 is problematic since SGDA is not uniform stability as far as I know:  it is uniform stable only after taking expectation w.r.t. the internal randomness of the algorithm.


**The authors have addressed main concerns on uniform stability of SGDA. It is a nice extension of the existing work. I only have minor suggestion on the final version of the paper about modifying the abstract in a modest tone and the caption to Table 1.   I will increase my score.**
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: High-probability generalization bounds for minimax problems are proposed. The authors establish bounds for four quantities: plain generalization error, primal generalization error, strong primal-dual risk and strong primal-dual generalization error. The main contribution of the paper is in fast rates of the bounds compared to previous work for various applications to popular algorithms.
main_review: The paper overall is written nicely and fairly clear. The problem setup is also interesting and has potential impact for other problems as well.

A concern I have for the results is the comparison of the generalization with respect to the empirical measures: is there a motivation for comparing these measures with a constant (1+eta) multiple of empirical measures? It seems that it would be more reasonable to have results for the case where eta approximates zero---when eta is a non-zero constant, then if we were to look at the difference between the generalization measure and the empirical measure, there would be a dependency on the empirical risk multiplied by eta, which may or may not have the desired dependency on order as expected. 

Following the same concern as above, take for example the result Theorem 1-b., where the comparison of R(Ax(S)) is made with (1+eta)*R_S(Ax(S)). I took a look at the results of Farnia & Ozdaglar, and it appears that their paper compares the expected generalization risk E(R(Ax(S)-R_S(Ax(S))) which corresponds to eta->0.  Looking briefly at the referenced paper "Stability and generalization of stochastic gradient methods for minimax problems" by Lei et al., their results (Theorem 1) also compare the generalization measures directly with the empirical measures, without extra multiples such as (1+eta). Therefore it does seem that the fairness of the comparison can be discussed/explained in more detail.

Apart from the above concern, I agree with the authors that it would be interesting to see if assumptions can be relaxed. It would be helpful to have more discussions on the dependency of these assumptions.
summary_of_the_review: The paper is nicely written. There is a concern regarding the main theorem's dependency on the (1+eta) factor for the empirical measures. This also leads to a concern about the fairness of comparisons with related work.
review_title: null

Meta-review: This paper establishes high probability generalization bounds of the order O(1/n) for a range of stochastic minimax problems. The reviewers agreed that results are of broad interest and the techniques are non-trivial. I recommend acceptance.
Decision: Accept (Poster)