What is a Good Metric to Study Generalization of Minimax Learners?
Authors: Asuman E. Ozdaglar
Sarath Pattathil
Jiawei Zhang
Kaiqing Zhang
Venue: NeurIPS 2022 Accept (2022)

Abstract: Minimax optimization has served as the backbone of many machine learning problems. Although the convergence behavior of optimization algorithms has been extensively studied in minimax settings, their generalization guarantees, i.e., how the model trained on empirical data performs on the unseen testing data, have been relatively under-explored. A fundamental question remains elusive: What is a good metric to study generalization of minimax learners? In this paper, we aim to answer this question by first showing that primal risk, a universal metric to study generalization in minimization problems, fails in simple examples of minimax problems. Furthermore, another popular metric, the primal-dual risk, also fails to characterize the generalization behavior for minimax problems with nonconvexity, due to non-existence of saddle points. We thus propose a new metric to study generalization of minimax learners: the primal gap, to circumvent these issues. Next, we derive generalization bounds for the primal gap in nonconvex-concave settings. As byproducts of our analysis, we also solve two open questions: establishing generalization bounds for primal risk and primal-dual risk in this setting, and in the strong sense, i.e., without assuming that the maximization and expectation can be interchanged. Finally, we leverage this new metric to compare the generalization behavior of two popular algorithms - gradient descent-ascent (GDA) and gradient descent-max (GDMax) in minimax optimization.

What is a Good Metric to Study Generalization of Minimax Learners?
Asuman Ozdaglari
Sarath Pattathil
Kaiqing Zhang University of Maryland, College Park
Jiawei Zhang
"assaahuseett Institute of Technology {asuman, sarathp, saarthh,jjzzhane jwzhang, kaiqing) @mit. eeuu.
Abstract
Minimax optimization has served the backbone of many machine learning problems. Although the convergence behavior of optimization algorithms has been extensively studied in minimax settings, their generalization guarantees in the stochastic setting, i.e., how the solution trained on empirical data performs on the unseen testing data, have been relatively underexplored. fundamental question remains elusive: What is a good metric to study generalization of minimax learners? In this paper, we aim answer this question by first showing that primal risk, a universal metric to study generalization in minimization, fails in simple examples of minimax problems. Furthermore, another popular metric, the primal-duce risk, also fails to characterize the generalization behavior for minimax problems with nonconvexity, due to non-existence of saddle points. We thus propose new metric to study generalization of minimax learners: the primal gap, to circumvent these issues. Next, we derive generalization bounds for the primal gap in nonconvex- concave settings. As byproducts of our analysis, we also solve two open questions: establishing generalization bounds for primal risk and primal-dual risk in the strong i.c., without strong concavity assuming that the maximization and expectation can be interchanged, while either these assumptions was needed the literature. Finally, we leverage this metric compare the generalization behavior of two popular algorithms gradient descent-ascent (GDA) and gradient descent-max (GDMax) in stochastic minimax optimization.
Introduction
Stochastic minimax optimization, a classical and fundamental problem in operations research and game theory, involves solving the following problem:
min max Eg (w, 0; 2)]. wEW lEe
More recently, such minimax formulation has received increasing attention in machine learning, with significant applications in generative adversarial networks (GANs) [Goodfellow et al. 2014]] adversarial learning [Madry et al. [017]] and reinforcement learning [Chen and Wang 2016 Dai et
2018). Most existing works have focused on the optimization aspect of the problem. i.e., studying the of convergence, robustness, and optimality of algorithms for solving empirical version of the problem where it approximates the expectation by an average over a sampled dataset, in various minimax settings including convex-concave [Nemirovski al., 2009 Monteiro and Svaiter 2010), nonconvex amncoveex-concvve [Lin et al.] 2020 Rafique et 2011 and certain special conconvex-nonconce. [Nouiehed et 2019 Yang al. 2020 problems.
However, the optimization aspect is not sufficient to achieve the success of stochastic minimax optimization in machine learning. In particular, in classical supervised learning, which is usually
CCoresponding Author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

studied as minimization problem [Hastic et al., 2009]. the out-of-sample generalization performance a key metric for evaluating the learned models. The study of generalization guarantees in minimax optimization (and related machine learning problems) has not received significant attention until recently (Arora et al., 2017 Feizi et al., 2020 Yin et al.; 2019 Lei et al. 2021 Farnia and Ozdaglar 2021 Zhang et al. [021b]. Specifically, existing works along this line have investigated two types of generalization guarantees: uniform convergence generalization bounds, and
deepeddend generalization bounds. The former is more general and irrespective of the optimization algorithms being used, while the latter is usually finer and really explains what happens in practice, when optimization algorithms play an indispensable role. In fact, the former might not be able to explain generalization performance in deep learning, e.g., these bounds can increase with the training dataset size and easily become vacuous in practice [Nagarajan and Kolter 2019], making the latter a more favorable metric for understanding the success of minimax optimization in machine learning.
Algorithm-dependentt generalization for minimax optimization has been studied recently in [Farnia and Ozdaglar 2021] Lei et al., 2021 Xing et al.) 2021 Yang et al.) 2022]. These papers build on the algorithmic stability framework developed in [Bousquet and Elisseeff 2002], which are further investigated [Hardt et al. 2016]. In particular, these works have studied primal risk and/or (variants of) primal-dual risk under different convexity and smoothness assumptions of the objective. Primal risk (see formal definition in $ is a natural extension of the definition of risk from minimization problems. Primal-dual risk, on the other hand, is defined similarly but based on the duality gap of the solution. It is know that it is well-defined and can be optimized to zero only when the global anddle-point exists (i.e., min and max can be interchanged). Based on these metries, (Farnia and Ozdaglar 2021 Lei et al. 2021] compare the performance of specific algorithms, e.g., gradient descent-ascent (GDA) and gradient descent-max (GDMax). We provide more thorough literature review in Section A and a detailed comparison in Table
Although these metrics are natural extensions of generalization metrics from the minimization setting, they might not be the most suitable ones for studying generalization in stochastic minimax optimiza- tion, especially in the nonconver settings that is pervasive in machine/deep learning applications, where the global saddle-pois point might not exist. In particular, we are interested in the following fundamental question:
What is good metric to study generalization of minimax learners
In this paper, make an initial attempt to answering this question, by identifying the inadequacies of the existing metric, and proposing a new metric, the primal gap that overcomes these inadequacies. We then provide generalization error bounds for our new metric, and discuss how it captures information not included in the other existing metrics, as well as discussing the tightness of the bounds. We summarize contributions follows.
Contributions. First, we introduce an example through which identify the inadequacies of primal risk, a well-studied metric for generalization in stochastic minimax optimization, in capturing the generalization behavior of nonconvex-concan we propose a new metric- - the primal gap, which provably avoids the issue in the example, and derive its generalization error bounds. Next, we leverage this new metric compare the generalization behavior of GDA and GDMax, two popular algorithms for minimax optimization and GAN training, and answer the question of when does GDA generalize better than GDMax? Moreover, we also address two open questions in the literature: establishing generalization error bounds for primal risk and primal-dual risk without strong concavity or assuming that the maximization and expectation can be interchanged. while at least one of these assumptions was needed in the literature [Farnia and Ozdaglar [222]] Lei al. 2021 Xing et al., [202T] Yang et al. 2022 Xiao al.) 2022]. Finally, under certain assumptions of the max learner, our results also generalize to the nonconvex Nonconvex-nonconcav nonconcave setting.
minimax problems. Second, to address the issue,
2 Preliminaries
2.1 Problem formulation
In this paper, we consider the following (stochastic) minimax problem: min max Ez~P, 0;2). NEW lEE
(I)
2 Hereafter, we use learner and learning algorithm interchangeably.
2

---

We make the following assumption on the sets W and θ throughout the paper.
Assumption 1. W and θ are convex, closed sets, and we further assume that W is compact with ||w]| S MW),, Veu W. Here M(W is constant dependent on the set W.
Let r(w, 0) = ExNP, f(w, 0; z). For a training dataset S = {Z1.".., with n i.idd variables drawn from P., define rs(w,, 0) = Ei=1((u B; 2.). Next, we define the following quantity:
Definition (Primal risk (empirical/populationn). Primal population risk is given by r(w) = maxteo Piz-e,((u (w, 0; 2), and the primal empirical risk is given by: rs(w) max E [ww, 2;).
Throughout this paper, we use (ws, 0g) to denote a solution of the minimax problem: mingew maxpge (w, 0). Notice that (ws, 0s)) need not be a global saddle-point of rs-- Fur- thermore, we use (w", (0) to denote a solution of min maxsge rww, 0). Once again, notice that (w",6% may not be saddle point of r.
The goal in Problem (T) is to minimize the primal population risk r(w). Note that this function can be decomposed
r(w) = rs(w) + (r(w) rs(w))
In practice, we only have access to T's (s, 0). and our goal is to design algorithms for minimizing r(w) using dataset S. Suppose A a learning algorithm initialized at (w, 0) = (0,0). We define (wg, 0g) to be the output of Algorithm A using dataset S.
From Equation (2) it is clear if we ensure rs (w3) ) as well as r(wg) -rrs (wrg) are small, this would guarantee that r(wg) is small, which the goal of Problem (T). Note that we can always ensure that (s(w)) ) is small by using a good optimization Algorithm A (if the problem is tractable). The main goal in the study of generalization is therefore estimate the generalization error of the primal risk, as defined below.
The generalization error for the primal risk defined as: Sgen (A) ElsEA()(g))) rs(wg).. Here the expectations are taken over the randomness in the dataset as well as any randomness used in the Algorithm A.
Definition 2.
This metric has been used to study generalization in stochastic minimization problems, i.c., when the maximization set θ is singleton, well several recent works in stochastic minimax optimization (see (Hardt et al. 2016 Farnia and Ozdaglar
2021
Lei et al. 2021
We are interested in the question of when the solution to the empirical problem wś has good generalization behavior, i.e., when E E'r(w))
min r(w)] is small wy is an approximate minimizer of the primal population risk r. In the next subsection, we briefly describe why the generalization error of the primal risk Sgen (A) is good measure to study the generalization behavior minimization problems.
2.1.1 Syen for minimization problems
Consider stochastic optimization problem of the form
min E [9(w; z)].
(3)
WEW
We define the (minimization) primal risk (population and empirical version respectively) as: r(w) = Es-P,, (w; (ww; 2), and (w) 1 Ex= 9 wr; 2,). The generalization error Sgen PP.min (A) for the (minimization) primal risk is the same in Definition@ussigg the (minimization) primal risk.
Assume that the generalization error of the primal risk for an Algorithm A is small, say cPeminn (A) S 6. This implies that (from Definition 2p: Elr(wg)) < ((rs(wg)) + Note that the expectation is with respect to S and A. Now, in order to show that w has good generalization behavior, we first see that:
E(r(wg)) - min r(w)] < Eirs(w + c- min r(w).
weW
weW
Note that we slightly abuse the notation here by allowing and rss to have inputs that can be both w and (w, 0). The distinction will be clear from context.
3

---

However, note that for minimization problems, since E[rs] = we have tha min r(w) 2 Elminwew rs(w)]. which gives us:
E(r(uş) min r(w)] - [[rs(w])] + E min rs(w)) (((s(W)) min rs(w)] +E=E.
Therefore, for minimization problems, if the generalization error for primal risk is small, the solution to the empirical risk minimization problem has good generalization behavior. Next, highlight some results in the literature which discusses generalization error bounds of the primal risk. These results depend the concept of algorithmic stability we later.
2.2 Stability of algorithms
Stability analysis is a powerful tool to analyze the generalization behavior of algorithms (see [Bous] quet and Elissceff 2002)). In this section, will review some definitions and theoretical results about stability bounds existing in the current literature. More specifically, in this paper, we adopt the following definition of stability:
Definition 3 (c-stable Algorithm). Suppose that A is a randomized algorithm for solving the stochastic minimax problem. We define (wg. 03) the output of Algorithum A using dataset S. We say S and S' are neighboring dataset if they defer only in one sample. An Algorithm is defined to be c-stable if EA (EAllus [l wg. S
aand E 0 0 S e for any neighboring datasets S and S'.
Hardt et al. 2016) gives the following basic result for the generalization error rs(w)).
Theorem 1 ([ardt et al., 2016)). Consider the (stochastic) minimization problem defined in
3
Suppose g(: 2) is I--Lipscitzz continuous, i.e., Vz, it holds that [[g((;;; -eb [(,2;;)] < L W
wall, Vwn, W2 E W. Then, for c-stable Algorithm A, have Eş E
S Lc.
Unfortunately, Theorem | cannot be directly extended to analyze the generalization behavior of minimax learners, because we have additional maximization step before taking expectation. Under certain additional conditions, primal risk can be a valid metric for minimax learners. We provide theoretical justifications in Section B instantiated by adversarial training example. We deal with the more general cases next.
Primal Gap: New Metric to Study Generalization
The main idea which leads to the success of Syen (A) as metric to study generalization for minimiza- tion learners is that Elminwew rw)) S min r(w), which is no longer the case in the minimax case. In fact, in this section, we show that good bound for the generalization error of primal risk does not imply good generalization behavior in minimax problems. We then propose new metric, the primal gap, which circumvents these issues and provides insights into the generalization behavior in minimax problems.
3.1 Primal risk can fail for minimax learners
We provide an example where the generalization error of the primal risk small, but the final solution to the empirical problem has poor generalization behavior. In this example, the minimizer of rs(w) suboptimal for r(w) with high probability, and E.s (r(ws) - -r(w") is large.
Example 1 (Analytical example). Let y NO0, 1/ be a Gaussian random variable in RR Define the truncated Gaussian variable z ~ P. as follows: 2 = y if ly| < Alog n/ vn and 2 = A X n/vn
y 2 \ Alog n/ Vn. Let (w, 0; 2) = 2 w2
2n 82 z0 + w, where w E W = [0, 1
[-nn, Xn] with a sufficiently large X 0, and zi Pg be i.i.d truncated Gaussian variables. Then,
have (s f 2 2
(2 0 Ei
2i B 00+11 w, and
1 w
r(w, 0)
82 + +1) w.
(5)
2
2n²
Note that this leads to the primal population risk function: r(w) = 1 w22 W.
' 'eere use the fact that Es Iming fax x)] S min: Es (x)

---

It is not hard to see that we always have rs(w) 2 r(w). Note that this means Sgen, (A) S O. and thus we have a small generalization error for primal risk. However, we can prove that for large enough
Es(r(ws) r(w"((ww)))) 2 0.02.
(6)
This means that ws has a constant error compared to w" in terms of the population risk, despite that its generalization error is small. This phenomenon is due to that win Tis Ts(w) (W)mmnnwew r(w) > e
for some c > 0, and hence minimizing rs(w) is very different from minimizing rww).
This example shows that the generalization error of primal risk is not a good measure to study generalization in minimax learners. The main drawback is that min rs(w) and min r(w) can be very different. We now introduce another more practical example, from GAN training, to further illustrate this point.
Example 2 (GAN-training example). Suppose that we have a real distribution P. Rdd which can be represented as G* with y E R drawn from a standard Gaussian distribution Po and mapping Rd. For an arbitrary generator G, we define Pg to be the distribution of the random variable G(y) with y ~ Po. So our goal is to find a generator G such that Pg = Py- GAN is popular tool for solving this problem. Consider GAN with generator G, parametrized by w and discriminator D parametrized by 0. The goal of GAN training is to find pair of a generator G and discriminator D that solves the minimax problem:
- :
min max D
(Eo-P,((((s)) + En Pa (0 (D-))
min max ((o(()) + Py-rolo(1 Do #
where : RR R is concave, monotonically increasing and Φ(u) = -00 for u S To connect to the minimax formulation in ( we note that 2 = (I, and P = P. x Po. Also, we denote
r(w, 0) Ez-P, ((D(())) + P 10(1 Do(G
to be the population risk. We now give the empirical version of this problem. Let S1 {21.-... and S2 = {yI..... 3. Let S = S1 U S2 and rs(w, 0) EE (D((zz)) 0(1 Do (B:)))). We assume that PG.. has the same support set as Pr. Moreover, we assume that ||l - w0|l S 0.5 and Gw(yy) is 1-Lipschitz w.r.. w for any y. Here w/ denotes the parameter for which Gw- G Then, combining Theorem B. I in Arora et al. 2017) and the Lipschitz continuity of (y) as well as \|w - -w"ll || I 0.5, we have that the distance between the sets S₁ and (11, (y)))),
Gw(yn) will be larger than 0.6 with probability greater than 1- On2 ) Now, if n is only of polynomial size of d, the optimal discriminator for disjoint datasets outputs 1 on one dataset, and O on the other. On the other hand, when w = -w,, the optimal discriminator for the population problem outputs for any sample receives. Combining these two results, we have: Fis(min rs(w)- min r(w)] 2 (1 - (26(1) (1(112) which is bounded away from O.
Note that in this example, we also have Emini rsww) min r(w)] > 0, implying that using <yen (A) might not be a good way to characterize the generalization behavior in GAN training. To address this issue, we next define new metric, the primal gap, and use its generalization error to study the generalization of minimax learners.
3.2 Primal gap to the rescue
The population and empirical versions of the primal gap are defined as follows:
Definition 4 (Primal gap (empprrica//pouulation).. The population primal gap is defined as
A (w) = r(w)= minwew r(w), and the empirical primal gap is defined as As(w) = rs(w)) min rw)
Notice that these two primal gaps can always take 0 at ws E arg wew Ts(w) and w² e arg win r(w) respectively even the saddle point of problem ( does not exist, Next, we define the expected generalization error of this primal gap as follows:
Definition 5. The generalization error for the primal gap is ( (A) (( As(wg)).
5

---

Notice the fact that
EsEa(r(ws)
min r(w)] EsEl(rs(ws)
min rs [w)) + Sgen( (A).
weW
NEW
If (s min rs(w]] is small and Sgen is small (or large), then Es Es (r(s))))
milleew r(w)] is small (or large).
Now provide bounds Sgen(A) for stable algorithm A, and show that in Example (ge((A) cannot be small (unlike (A)).
3.3 Relationship between generalization and stability
We provide bounds for the generalization error of the primal gap (Definition 5) for an e-stable Algorithm A. We will focus the nonconvex-conean made throughout the rest of the paper.
where the following assumptions
Assumption 2. The function f in Problem ! is noncomvex-concave i.e., =3 is a concave function for all w E W and for all z.
Next we define the notion of capacity, which will play a key role in the bounds we derive for Syen (A). Definition 6 (Capacity). For any E W and any constraint set O we define
θ (w) arg max (w, 0) 0E0
@s(w) arg maxrs 0). 0EB
We define the capacities Cp and Ce as:
(,) = max dist(0, ((w)), wEW
(.(O) = max max dist Os(w)),
S WEW
where dist(p, S) denoies the distance between point p to set S in Euclidean space, iee, dist(p, S) = infges ||p - gll2- For the constraint set in Problem ① we succinctly denote the capacities Cp and Ce, respectively.
The norm of the model parameter (its distance to 0) is usually viewed as the metric for the complexity of the model. In fact, the norm of the optimal solution determines the Rademacher complexity of the function class in statistical learning theory [Vapnik] 1999]. Morcover, in deep learning, minimum- norm solution of overparameterized neural networks is well-known to enjoy better generalization performance (Zhang et al. 2021a]. Hence, we view the capacity constant C. and C, as natural metrics to capture the model complexity for the best response of the max learner, i.e., the power of the maximizer, when using the empirical data set and population data respectively.
Now, we are ready to discuss the relationship between the stability bound and the generalization error of algorithms in innconvex-concav minimax problems. All proofs have been deferred to the appendix. We make the following assumptions throughout the paper:
Assumption 3. The gradient of f is t-Lipschirz-continee
for all z, i.e.. for all a
[ 01: V f(w2, 02i 2)ll < E(]w1 w2ll + ||0: 02l1), Yw1, w2 W, v0,,02 θ.
Moreover, fixing w E W, the partial gradient Vol : 2) is 60 -ipschitt continuous with respect to 0 for all z, i.e., f 01; Vof(w, 0): _ tee ||0 0211, Vw E W, v0,, 02 E O
Assumption 4. For any O C θ we assume that f is L( (iee)))Lpschiiz-coniie fw2,, 0z; 2) < I(O w2ll + 10 Ball), Vwn, W2 E W. 00 E O1, and the gradient ff 0; is uniformly bounded as (V 0)=)] || L() all and w E W, 0 E O₁ Moreover, f(w 2; Li-Lipschitz con- tinuous with respect to where w" E arg miDwew r(w). We also define L = L(((0, 2C,, +))+))
with respect
to E W,6 E O₂ for all z, i.e,, [If ([W],01;2)
and L, L(B(O, r) n O), where B(y,r) r) denotes the l2-ball with radius r centered
Note that we can decompose the generalization error of the primal gap as follows:
PG (A) == F.s ((((gg) - As(ug)) = Cfen (A) + Fisl min rs(w) min r(w)) wEW
WEW
We now provide a generalization error bound for the primal risk CPen (A). To the best of our knowledge, it is the first bound for ( (A) in the nonconvex-concat (not strongly concave) setting.

---

The generalization error of the primal risk of an e-stable Algorithm f minimax problem with concave maximization problem can be bounded by Syen (A) I VALEC3 ve+
Lemma 1.
We show that this dependence is tight in Section D.2 Since we already have the generalization error for the primal risk ( - (rs(w))) from Lemma we only need to estimate
EsEA| min (s(w) - min r(w) Ess min rs(w) WEW
min
r(w)]
[Primal Min Error]. (7)
wEW
weW
wEW
The following theorem gives the generalization bound of the primal gap using the upper bound from Lemma I and bounding the Primal Min Error in Equation 77.
Theorem 2. Suppose Algorithm A is e-stable. The generalization error bound of the primal gap is given by ( (A) S VATAC;
The first term in the bound above is from the generalization bound of the primal risk, as shown in Lemma] [ Note that the bound in Lemma onnly involves Cp. the key in the analysis is to upper-bound the population risk r(wg), ), which requires bounding the power of the maximizer using the population capacity Cp. This reflects the intuition that the power of the maximizer should affect the generalization behavior of minimax learners, and the stronger the maximizer is, the harder for the learner to generalize. On the other hand, the bound in Theorem 2 addiiioonaly involve Ce. the empirical capacity. Technically, Ce (instead of C2)) appears since we need to bound min [w) (defined on the empirical dataset) in the Primal Min Error term in (7). We show the tightness of this bound in Section D.4 The appearance of C. reflects the intuition that the difference between the maximizers of the empirical and population risks should make a difference in characterizing the generalization of minimax learners. This intuition cannot be captured by the generalization error of the primal risk, as in Lemma [ Note that in the minimization case, the Primal Min Error can be upper-bounded directly by zero, and such a distinction disappears, making primal risk valid metric.
3.4 Revisiting Example !
In Example I we have that the primal risk generalizes well, but the solution Wy does not, thereby indicating that the generalization error of the primal risk may not be good metric study gener- alization behavior of minimax problem. Note that in Example]] we have <P (A) 2 0.02 while Spen((A) S O. We already know that this algorithm can not generalize well. Therefore, Syen (A) can capture the generalization behavior better than Cee (A). This shows that the primal min error CPM also plays an important role in analysing the generalization for minimax problems. As shown in the appendix (Proposition 4p. we have
Es Es[min (w()) min r(w) 2 0.005. WEW
(8)
WEW
On the other hand, it is easy to compute that Lã Alog n/ vi and Ce = An log n. Therefore, by Theorem 2 we have an upper bound for the Primal Min Error (see 77 Es [min rw(
min r(w) 4L5C./ /n 4 log n, which is tight up to log factor according to (8). Therefore, the primal gap has a constant generalization error which is consistent with the observation that the solution to the empirical problem does not have good generalization behavior.
3.5 Nonconvex-nonconeee case
In this section, we extend our results to the certain assumptions on the inner maximization problem, we can derive generalization error bounds for the primal risk and primal gap in terms of algorithmic stability. We make the following assumptions on the inner maximization problem:
setting. We will show that under
Assumption 5. For any > O, there exists an algorithm which outputs (w.) (. for the inner maxi- mization problem maxace r(w, 0), satisfying the following conditions: 1) r(w) r(w, (z())) S 7 2) (107,(u)) - (w,))) < Au
7 w|ll w'll with some constant >p for all w.w' E W.
Assumption 6. For any > O, there exists an algorithm which outputs 07 (S). for the inner maximiza-
tion problem max rs(w", 0), satisfying the following conditions: 1) r)rs(=") rs(w", (T()) <
7. 2) For any neighboring dataset S and S', (10 (5') - my
A for some X 0.
7

---

The following lemma gives sufficient conditions for these two assumptions to hold.
Lemma 2. Consider constants De 2 7 and Dy 2 7.
1. Suppose gradient ascent with diminishing stepsizes co/t. for the problem max r(w, 0) has convergence rate r(w)- - r(w, 0²) I Dp/s. Then we define (3) by performing
8 = Dyln steps of gradient ascent. Then, (w) satisfies Assumption
2. Suppose gradient ascent with constant stepsize co for the problem maxgge r(w, 8) has convergence rate r(w) r(w. (*) I Dyni" for some constant O < L 1. Then we define f (w) by 8 = log(Dp/7)) log(1/1) (1)) steps of gradient ascent. Then, (w) satisfies Assumption 5
3. Suppose gradient ascent with diminishing stepsizes caft for the problem maxøee (s( has convergence rate rs(w) - rs( 0*) < Dpjs. Then we define (S) by performing
8 = De/n steps of gradient ascent. Then, 02 (S) satisfies Assumption 6
4. Suppose gradient ascent with constant stepsize co for the problem maxage (w, 0) has convergence rate rs(w) - -rs(w. < Den for some constant O < < 1. Then we define 0% (w) by s = log(DD////eo hat/n)//og/// (og(1/n)) steps of gradient ascent. Then, (2) satisfies Assumption 6
Remark 1. Note that for some practical noncorvex optimization problems in machine learning, grudient descent indeed converges to the global minima at a reusonably fast rate, e.g,, in training deep overparametrized neural networks (Du el al. 22099) robust least squares problems (El Ghaoui and Lebrel 1997y, phase retrieval and matrix completion Ma el al.) 2019/. Our Assumptions annd cean be viewed as an abstract summary of some benign properties of gradient descent for certain nonconvex optimization problems.
Furthermore, we assume that 22) is I--Lipschitz continuous in W x + This, along with Assumptions Sattiionnsnadddg and allows us to derive the generalization error bounds of the primal risk and primal gap in terms of algorithmic stability.
Lemma 3. Suppose that Assumption holds. If a minimax learner A is an e-stable algorithm, have Sgen (4) S LE + VLApVE.
Similarly, we can derive the generalization bound for the primal gap given the above assumptions. Theorem 3. Suppose Assumptions 5 and holdd. Then we have <pen (A) S cP (A) + vLXe/ Vn.
The proof of this theorem is similar to the proof of Lemma 3 and Theorem 2 and hence omitted.
Comparison of GDA and GDMax
In Section 3.3
provide generalization bounds for the primal gap for any e-stable algorithm. In this section, we focus on two algorithms in particular - GDA and GDMax. These two algorithms are described in Algorithms [and 2 in Appendix D
We note that though analyzing the optimization properties of GDA/stochastic GDA for solving the empirical minimax problem is an important topic, our focus in this paper is on studying the generalization behavior of these algorithms. We assume that the empirical version of the stochastic minimax problem can be solved by GDA and GDMax, i.e., we assume that GDA and GDMax satisfy the following assumption:
Assumption 7. Let A be minimax learner, such as GDA or GDMax. Then we assume that A has the following convergence rate: E Ex(rs(w*)- min i (w) I (o + (A(C)))/AA()) where M (W) ) is the maximum of the norms of w, and o (ss). (s)s are nonnegative, increasing functions that tend to infinity as s + co.
For simplicity, throughout this section, we assume that (w, 0: 2)ل < for all w. 0. and z. The next theorem provides a bound for the population primal gap ((wr)) == r(wg) min r(w). Note that the goal of any algorithm is to make this gap as small as possible.
For an Algorithm A and subsets We C W, Oo C O, we define A(Wo, O₂) as the algorithm which restricts A to solve T under constraint sets Wo and On. Specifically, AWW θ) is just A.
'Note that this is different from the L detined for the nonconvex-concat case. Here L captures the Lipschitz constant the whole constraint set. In the nonconvex conncvvveeeeevvveeeeeeeeeeeeeeee case, L = L(B(0) 2C, 1)).
8

---

Theorem 4. Let w's , .3. be the t-th iterate generated by Algorithm A using dataset S. Assume A.t
that 10z'") S Oo -g for t S T with probability 1 (due to the randomness in S) and B(O, Cp) 0 Here B(u,r) denotes the 12-ball with radius centered
Let An = A(W, Oo). Then after iterations of Algorithm A, the population primal gap can be bounded as:
Es Bssrrug) ( min r[w)] S (gen(Ao) + ( @ (CC.())))//A)) A) 4L3C. +6, weW
(o rs(wg is the generalization error of the primal risk of where (Ao) EsEAlr(w
Algorithm Ag-
Remark Theorem builds closer connection between generalization behavior and the dynamics of the minimax learner A. It shows that suitable restriction to the max learner can lead to better minimax learner, in terms of generalization. We make this clear in the comparison of GDA and GDMax by analyzing the three terms in Theorem
4.1 Analyzing the term I
First, we study the generalization error bound of the primal risk, i.e., Syen in Theorem 4 For GDA, we can estimate Spen by using Lemma Therefore, it suffices to estimate the stability of GDA. We do this in the following lemma:
Lemma 4. Let co max Bo). If we use diminishing stepsizes 04 = ao/t and B. Bo/t for GDA for T iterations, we have the stability bound e GDAA < 22gggoA /
Now, since we have bound for Sgen (A) for e-stable Algorithm A in Lemmal the stability bound for GDA from Lemma in this expression to get a bound on (GD.A for GDA. We do this in the next proposition. We can bound Sgen (Ao) for GDA by substituting the stability bound in Lemma 4 into Lemma I (letting c= CGDA)
substitute
Proposition 1. Let Co max 3o3 and assume that f(riz) is Luggox-Lipschitz-oonnnee
inside the set W x @GDA, For GDA with diminishing stepsizes 0o/t,,8ott run for T iterations (denoted by GD AT), the generalization error of the primal risk can be bounded by:
Sgen (GDAT) S (L VSC3/8 Tooe/// T
However, for GDMax, we can not compute a uniform stability bound that vanishes as n goes to infinity. In fact, that is independent of which means that for the case where r(w, 0) is nonconvex-concave, the generalization error of primal risk of GDMax can be undesirable.
show from the following simple example that Sgen (GDMax) can be constant
Example 3 (Constant generalization eπror of primal risk for GDMax). Consider dataset S with elements. Define the objective function: f(w, 6; 2) ( 2)
2n where w E W [-n/a,, nnnn, 0 θ R and z drawn the uniform distribution over {-1/ 1/V We have rs(w) (w) = n2 --- ΣE zi)² and r(w) w²
6²
2n² Therefore, min r(w) = 0. From the definition of the function f and the sets W and θ, we huve E = 1/n2, L= 0(1/
One step of GDMax can attain the minimizer s(w) (since it is one dimensional quadratic prob- ( 2.
lem), i.e., Us = ni Ei= and (swws) = O. Furthermore, we have Esr(ws) = = 1/2 > 0. Thus, cP. (GDMax) = E(r(ws) - (w(ss)) = 1/2 > 0 cannot be made small.
Therefore, from Proposition 1 and Example 3
that the bound for the expected population primal gap contains the term Sgen which cannot be bounded for GDMax, whereas can be bounded for GDA which leads us to the conclusion that GDA generalizes better than GDMax for such problems. However, it is possible to bound C (GDMax) in certain problems, and in this case the other terms in Theorem 4 become crucial. We analyze them next.
Fp
4.2 Analyzing the term !I
As shown in Example [ sometimes GDMax can have good generalization bound for the pri- mal risk. Therefore, we need to analyze the other two terms in Theorem i.c., (0A(Mw)

---

A (Og))) and (,C:( For these two terms, since Lg is fixed, the constant ((,))) is the key term which differentiates the performance of different algorithmss
for GDMax is nearly C. (See Definition 6). Therefore, the population primal gap after I' steps of GDMax is dominated by C. if C. is large. However, the set Y for GDA can be much smaller than θ, which implies that C. (e can be much smaller than Ce. This phenomenon primal stepsize 1, we can attain w = Ws. Then Es (s(r(w mingre r(w)] 2 0.005 from (6) For GDA, we can see that w after one step of GDA with stepsize 1. Therefore, GDA generalizes better than GDMax. Generally, we have the following estimate of (e
By definition, the constant C.
be seen from Example T If we perform one step of GDMax with
Lemma 5. Let Lo max [ww, =); Let co- = max 3. If we use diminishing stepsizes a₂ = aoft and B Bo/t GDA, then after T steps have |00$ S T for [T]]
Therefore, if C. is much larger than Cp. using GDA with Cp S La/e S Ce is better than GDMax. We make this more concrete in the context of GAN training next.
4.3 GAN training
We now study the specific case of GAN training to explore why GDA might generalize better than GDMax. This is numerically verified in the literature, such as Farnia and Ozdaglar (2021). Specifically, we revisit Example 2 and consider a special case: is restricted to a over- parametrized linear function with respect to 0. Define the descriminator D(x) = Tx (z)v + bo where (xx) (I)))).... Lm (x) E R" is the feature matrix and bo R. Also sup- pose that G is parametrized by w and G = Gw.. Then the GAN problem can be written as min maxage r(w,0) f), where
r(w,0 0) = Ee- (o(0 + bo)l + E --- (² bo)].
Here = (v, bo). Assume that V Tmax (EONPOw ((T) (>)))))))))))))))))))))) S maxx/ Vm, where m de- notes the largest singular value of matrix and max 0 is constant. Also assume that Ez-Pew (xx))=² (x) is full rank. Also, we assume that (o'(2) S T.p for any X E [o, 1]. Therefore, we have Ell [w 0; [?] ss Lzo Then it reasonable to assume that || S O(1).
Lemma 6. Suppose (x) is uub-aaussian and the matrix
= [ 2(x2)...
v(Ix) ((Gw()1) ... ((GG(un))
is full column rank (m > n) with probability 1. Then with probability at least 1 - C8 with some constant C, we have [10s(w") "Il 2 Q(yn), where (s(w") E arg maxage rs(w", 0).
Now, for E arg max r(w",0', it can be easily seen that v = 0, bo = 1/2 in this case. Therefore, C Rs 1/2. Finally, combining the previous discussion on GDA in Lemma 5 and using the fact that C. is large from Lemma we see from Theorem that GDA can generalize better than GDMax. More detailed discussion of the GAN-training and Lemma 6 can be found in Section
5 Conclusions
In this paper, we first demonstrate the shortcomings one popular metric, the primal risk, in terms of characterizing the generalization behavior of minimax learners. We then propose new metric, the primal gap, whose generalization error overcomes these shortcomings and captures the generalization behavior of algorithms that solve stochastic minimax problems. Finally, we use this newly proposed metric to study the generalization behavior of two different algorithms GDA and GDMax, and study cases where GDA has better generalization behavior than GDMax. Future directions include further investigation the proposed new metric, the primal gap, and deriving its (tighter) generalization error bounds in other structured stochastic minimax optimization problems in machine learning.
Acknowledgments and Disclosure of Funding
Research was sponsored by the United States Air Force Research Laboratory and the United States Air Force Artificial Intelligence Accelerator and was accomplished under Cooperative Agreement Number
10

---

1A8750-19-2-1000 The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed implied. of the United States Air Force the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. S.P. acknowledges support from Math Works Engineering Fellowship. A.O. and K.Z. were supported by MIT-DSTA grant 031017-00016. K.Z. also acknowledges support from Simons- Simons-Berkeley Research Fellowship.
References
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (GANs). In International Conference on Machine Learning, pages 224 232. PMLR, 2017.
Idan Attias, Aryeh Kontorovich, and Yishay Mansour. Improved generalization bounds for robust learning. In Algorithmic Learning Theory, pages 162-183. PMLR, 2019.
Yu Bai, Tengyu Ma, and Andrej Risteski. Approximability of discriminators implies diversity in GANs. arXiv preprint arXiv:/806. 10586, 2018.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, 2002.
Yichen Chen and Mengdi Wang. Stochastic primal-dual methods and sample complexity of rein- forcement learning. arXiv preprint arXiv: 2016.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. SBEED: Convergent reinforcement learning with nonlinear function approximation. International Conference Machine Learning, pages 1125-1134. PMLR, 2018
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint arXiv: / 2017.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pages 1675- 1685. PMLR, 2019.
Laurent Ghaoui and Hervé Lebret. Robust solutions to least-squares problems with uncertain data. SIAM Journal on matrix analysis and applications, 18(4):0035-106 1997.
Alireza Fallah, Asuman Ozdaglar, and Sarath Pattathil. An optimal multistage stochastic gradient method for minimax problems. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 3573-3579. IEEE, 2020.
Farzan Farnia and Asuman Ozdaglar: Train simultaneously, generalize better: Stability of gradient- based minimax learners. International Conference on Machine Learning, pages 3174-3185. PMLR, 2021.
Farzan Farnia, Jesse M Zhang, and David Tse. Generalizable adversarial training via spectral normalization. arXiv preprint arXiv: 2018.
Soheil Feizi, Farzan Farnia, Tony Ginart, and David Tse. Understanding GANs in the LQG setting: Formulation, generalization and stability. IEEE Journal on Selected Areas in Information Theory, 1(1):304-311, 2020.
2020.
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-playee games. Advances in neural information processing systems, 33:20766-20777 2020a.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. Conference on Learning Theory, pages 1758-1784, PMLR, 2020b.

---

Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems, 27, 2014.
Benjamin Grimmer, Haihao Lu, Pratik Worah, and Vahab Mirrokni. The landscape of the proximal point method for nonconvex-nonconcave minimax optimization. arXiv preprint arXiv:2006.0866 2020.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In 33rd International Conference Machine Learning, ICML 2016, pages 1868-1877. International Machine Learning Society (IMLSS) 2016.
Trevor Hastie, Robert Tibshirani, and Jerome H Friedman. The elements of statistical learning: Data mining, inference, and prediction, volume Springer, 2009.
Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. Advances in Neural Information Processing Systems, 32, 2019.
Minhui Huang, Kaiyi Ji, Shiqian Ma, and Lifeng Lai. Efficiently escaping saddle points in bilevel optimization. arXiv preprini arXiv:2202.03684 2022.
Weiwei Kong, Jefferson G Melo, and Renato DC Monteiro. Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs. SIAM Journal Optimization, (9(4):25662259 2019.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Yunwen Lei, Zhenhuan Yang. Tianbao Yang, and Yiming Ying. Stability and generalization of
stochastic gradient methods for minimax problems. arXiv preprint vrXiv:2005.03793 2021,
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, pages 6083-6093. PMLR, 2020.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. Foundations of Computational Mathematics, 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. stat, 1050:9, 2017.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference Artificial Intelligence and Statistics, pages 1497-1507. PMLR, 2020a.
Aryan Mokhtari, Asuman E Ozdaglar, and Sarath Pattathil. Convergence rate of o(1kk for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, 30(4):3230-3251 2020b.
Renato DC Monteiro and Benar Fux Svaiter. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM Journal on Optimization, 20(6):2755-277 2010.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 1574 1609, 2009.
Nesterov. Introductory Lectures on Convex Optimization: Basic Course, volume 87, Springer Science & Business Media, 2013.
12

---

Maher Nouiched, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-mi max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
Dmitrii M Ostrovskii, Babak Barazandeh, and Meisam Razaviyayn. Nonconvex-nonncomcave min-max optimization with a small maximization domain. arXiv preprini arXiv:21100039550, 2021a. 2021a,
Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash equilibria in cenconvex-conean smooth min-max problems. SIAM Journal Optimization, 31 (4):2508 2538, 2021b.
Leonid Denisovich Popov. A modification of the uurow-huwiicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845-848, 1980.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-convex concave min- max optimization: Provable algorithms and applications in machine learning. arXiv preprint 2018.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Ad- versarially robust generalization requires more data. Advances in Neural Information Processing Systems, 31, 2018.
Shai Shalev-Shwarzz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 1 11:263-22670, 2010.
Vladimir N Vapnik. An overview of statistical learning theory. IEEE transactions on neural networks, (0(5):988-999 1999.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 2010.
Colin Wei and Tengyu Ma. Improved sample complexities for deep neural networks and robust classification via an all-layer margin. In International Conference on Learning Representations, 2019.
Bingzhe Wu, Shiwan Zhao, Chaochao Chen, Haoyang Xu, Li Wang, Xiaolu Zhang, Guangyu Sun, and Jun Zhou, Generalization in generative adversarial networks: A novel perspective from privacy protection. Advances in Neural Information Processing Systems, 32, 2019.
Jiancong Xiao, Yanbo Fan, Ruoyu Sun, Jue Wang, and Zhi Zhi-Quan Luo. Stability analysis and generalization bounds of adversarial training. arXiv preprint 2r0:0:2210.00960, 2022.
Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. Advances in Neural Information Processing Systems, 34, 2021.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for a class of noncomvex-nonconcaae minimax problems. Advances in Neural Information Processing Systems, 153311166 2020.
Junchi Yang, Antonio Orvieto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for minimax optimization without strong concavity. arXiv preprint arXiv:2112.05666 2021.
Zhenhuan Yang, Shu Hu, Yunwen Lei, Kush Varshney, Siwei Lyu, and Yiming Ying. Differentially private SGDA for minimax problems. arXiv preprint arXiv:2201.0900 099040 2022.
Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. In International Conference on Machine Learning. pages 7085-7094 PMLR, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):007-155, 2021a.
13

---

Jiawei Zhang, Peijun Xiao, Ruoyu Sun, and Zhiquan Luo. A single-loop smoothed gradient descent- ascent algorithm for conconvex-concawy min-max problems. Advances Neural Information Processing Systems, 33:7377-7389, 2020.
Junyu Zhang, Mingyi Hong, Mengdi Wang, and Shuzhong Zhang. Generalization bounds for stochastic saddle point problems. In International Conference on Artificial Intelligence and Statistics, pages 568-576 PMLR, 2021b.
Pengchuan Zhang, Qiang Liu, Dengyong Zhou, Tao Xu, and Xiaodong He. On the discrimination- generalization tradeoff in GANs. arXiv preprini
2017.
Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of nonconvex-strongly-come minimax optimization. In Uncertainty in Artificial Intelligence, pages 482-492. PMLR, 2021c.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "vDNmGSJHUMH", "reviewer": "Reviewer_hkx3", "summary": "This paper introduces an example to show that the primal risk metric has inadequacies in studying the generalization for minimax problems.\n\nThis paper then proposes a new metric – the primal gap to avoid the issue in the example.\n\nThis paper then leverages this new metric to compare the generalization behavior of GDA and GDMax.\n\nFinally, this paper establishes generalization bounds for primal risk and primal-dual risk without assuming strong concavity.", "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.\n\nThe 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.\n\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe introduction is very clear. \n\nThe generalization without assuming strong concavity has good contributions.\n\nWeaknesses:\n\nDoes Theorem 1 (d) of the paper [1] study a more general stability measure of the primal gap? Can the authors provide a discussion?\n\nMissing reference:\n\n[1] Li, S. and Liu, Y. High probability generalization bounds with fast rates for minimax problems. In ICLR, 2022.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "V45zIfWqb42", "reviewer": "Reviewer_RYz4", "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. \nTo 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.\nThis 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.", "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. \n2. 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?\n3. 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. \n2. 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. \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. 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. \n2. Analytic examples shed light on the understanding the lower bound and the parameter estimation for the generalization of minimax problems.\n\n\nWeaknesses:\n1. 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FKzaeq1bfFI", "reviewer": "Reviewer_VSNm", "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. ", "questions": "* Is the dependence of $\\sqrt{\\epsilon}$ optimal? It appears to be inconsistent for the (albeit different) setting under strong convexity.\n* 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. \n* 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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the results are interesting and the paper is nicely written. \n\n**Originality.** \nThe 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.\n\n**Quality and clarity.** \nThe paper is nicely written and results are stated clearly. There are some minor typos that are listed here for further revision:\n- Table 1 contains a possible error: \"in the in the theorems\"\n- Line 270: \"generalizationerror\"\n\n**Significance.**\nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9YCMiZluBDV", "reviewer": "Reviewer_Z6Bm", "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. ", "questions": "Please find my questions in the strength and weakness section above! ", "limitations": "No foreseeable societal impact. ", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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! \n\nWeakness:  I think the paper has several weaknesses: \n1. 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? \n2. 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. \n3. 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.\n4. In that sense, are $\\zeta^{PG}(A)$ pr $\\zeta^{P}(A)$ metrics? Can you compute them a-priori or using data ? \n\nIt 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?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept