Year: 2021

Abstract:
Minimax problems are receiving an increasing amount of attention in a wide range of applications in machine learning (ML), for instance, reinforcement learning, robust optimization, adversarial learning, and distributed computing, to mention but a few. Current studies focus on the fundamental understanding of general minimax problems with an emphasis on convergence behavior. As a comparison, there is far less work to study the generalization performance. Additionally, existing generalization bounds are almost all derived in expectation, and the high probability bounds are all presented in the slow order O(1/ √ n), where n is the sample size. In this paper, we provide improved generalization analyses and obtain sharper high probability generalization bounds for almost all existing generalization measures of minimax problems. We then use the improved learning bounds to establish high probability generalization bounds with fast rates for classical empirical saddle point (ESP) solution and several popular gradient-based optimization algorithms, including gradient descent ascent (GDA), stochastic gradient descent ascent (SGDA), proximal point method (PPM), extra-gradient (EG), and optimistic gradient descent ascent (OGDA). In summary, we provide a systematical analysis of sharper generalization bounds of minimax problems.

text: √ n), where n is the sample size.
In this paper, we provide improved generalization analyses and obtain sharper high probability generalization bounds for almost all existing generalization measures of minimax problems. We then use the improved learning bounds to establish high probability generalization bounds with fast rates for classical empirical saddle point (ESP) solution and several popular gradient-based optimization algorithms, including gradient descent ascent (GDA), stochastic gradient descent ascent (SGDA), proximal point method (PPM), extra-gradient (EG), and optimistic gradient descent ascent (OGDA). In summary, we provide a systematical analysis of sharper generalization bounds of minimax problems.

heading: 1 INTRODUCTION
text: Minimax learning problems have achieved great success over a broad range of learning tasks in machine learning, with examples including reinforcement learning (Du et al., 2017; Dai et al., 2018), robust optimization (Chen et al., 2017; Namkoong & Duchi, 2017), adversarial learning (Goodfellow et al., 2014), distributed computing (Razaviyayn et al., 2020; Shamma, 2008; Mateos et al., 2010), and AUC maximization (Lei & Ying, 2021b), to just name a few. This framework is formulated as a zero-sum game characterized as two groups of decision variables, one for minimization and one for maximization. The coupling of the two groups of variables makes analysis of minimax problems more complex than the standard statistical learning theory setting, with only one minimization operator (Lei et al., 2021). Researchers have designed various optimization algorithms, for instance, gradient descent ascent (GDA), stochastic gradient descent ascent (SGDA), proximal point method (PPM), extra-gradient (EG), and optimistic gradient descent ascent (OGDA), to solve the minimax optimization problem (Farnia & Ozdaglar, 2021). Current theoretical research in ML literature is mainly devoted to the convergence rate and optimality of these minimax optimization algorithms in different setting, such as convex-concave settings (Nemirovski et al., 2008), nonconvex-concave setting (Rafique et al., 2018), strongly convex-strongly-concave setting (Balamurugan & Bach, 2016), and nonconvex-nonconcave setting (Liu et al., 2021; Yang et al., 2020). In contrast, there is far less work on the generalization performance analysis, which is an important measure to indicate the performance of the learned model based on training samples when generalized to the test data.
To the best of our knowledge, there is only three work on the generalization bounds of minimax optimization algorithms (Zhang et al., 2021a; Farnia & Ozdaglar, 2021; Lei et al., 2021). Among them, (Zhang et al., 2021a) studies the generalization bounds for ESP solution to minimax problems, (Farnia & Ozdaglar, 2021) analyzes the generalization properties of several gradient-based optimization algorithms: GDA, SGDA, GDmax and PPM, and (Lei et al., 2021) provides a systematical generalization analysis of SGDA. However, in the above-mentioned papers, almost all generalization bounds are derived in expectation. Only two high probability bounds exist, proposed in (Lei et al., 2021). Unfortunately, they are of slow order O (1/ √ n).
It is known that the high probability bound is beneficial to understand the robustness of optimization algorithms (Bousquet et al., 2020; Klochkov & Zhivotovskiy, 2021) and is much more challenging to be derived (Bousquet et al., 2020; Lei et al., 2021). In this paper, our goal is to provide the sharper high probability generalization bounds for minimax learning problems. We leverage the lens of algorithmic stability, which is also served as an important tool in (Zhang et al., 2021a; Farnia & Ozdaglar, 2021; Lei et al., 2021). Our contributions are summarized below.
1. In view of the coupling construction between the minimization variable and the maximization variable, minimax learning problems have many generalization measures (Lei et al., 2021; Farnia & Ozdaglar, 2021; Zhang et al., 2021a). In this paper, we provide improved stability analyses for almost all existing generalization measures, based on which we establish sharper high probability generalization bounds. These developed learning bounds can be employed to derive generalization bounds with fast rates for stable minimax learning algorithms.
2. The generalization performance of the ESP solution and gradient-based optimization algorithms stands a central place in the learning theory of minimax problems (Lei et al., 2021). In this paper, we develop high probability generalization bounds with fast rates for ESP solution and several popular gradient-based optimization algorithms: GDA, SGDA, PPM, EG, and OGDA. Overall, we provide a systematical analysis of sharper generalization bounds for minimax learning problems.
The rest of this paper is organized as follows. In Section 2, we briefly discuss the related work. Preliminaries about minimax problems are introduced in Section 3. We provide the main theorem in Section 4. Applications are shown in Section 5. In the last, Section 6 concludes the paper.

heading: 2 RELATED WORK
text: Algorithmic stability. Algorithmic stability is a fundamental concept in learning theory (Bousquet & Elisseeff, 2002), which has a deep connection with learnability (Rakhlin et al., 2005; ShalevShwartz & Ben-David, 2014; Shalev-Shwartz et al., 2010). A training algorithm is stable if small changes in the training set lead to small differences in the output predictions of the trained model. Different algorithmic stability measures have been developed, including uniform stability (Bousquet & Elisseeff, 2002; Feldman & Vondrak, 2018; 2019; Klochkov & Zhivotovskiy, 2021; Hardt et al., 2016; Lei et al., 2020), uniform argument stability (Liu et al., 2017; Bassily et al., 2020), hypothesis stability (Bousquet & Elisseeff, 2002; Charles & Papailiopoulos, 2018), hypothesis set stability (Foster et al., 2019), on average stability (Shalev-Shwartz et al., 2010; Lei & Ying, 2020; Kuzborskij & Lampert, 2018; Zhang et al., 2021b; Lei & Ying, 2021a), locally elastic stability (Deng et al., 2021), collective stability (London, 2017), and PAC-Bayesian stability (Li et al., 2020). These stability measures have been extensively studied in the generalization analysis of the standard statistical learning theory setting (Chen et al., 2018; Zhang et al., 2021b). Several stability measures have also been extended to minimax learning problems, for instance, weak stability, argument stability, and uniform stability (Farnia & Ozdaglar, 2021; Zhang et al., 2021a; Lei et al., 2021). In related work (Farnia & Ozdaglar, 2021; Zhang et al., 2021a; Lei et al., 2021), they mostly focus on the expectation form of these stability measures since they are to derive bounds in expectation. In this paper, we will focus on the last two measures, which are often used when establishing high probability generalization bounds (Feldman & Vondrak, 2018; 2019; Klochkov & Zhivotovskiy, 2021).
Convergence analysis. Convergence analysis has been widely studied in different settings, including convex-concave learning (Nemirovski, 2005; Nedic & Ozdaglar, 2009; Mokhtari et al., 2020; Cherukuri et al., 2017; Mokhtari et al., 2019; Balamurugan & Bach, 2016; Hsieh et al., 2019; Yan et al., 2020; Lin et al., 2020b; Wang & Li, 2020; Yoon & Ryu, 2021), nonconvex-concave learning (Rafique et al., 2018; Kong & Monteiro, 2019; Luo et al., 2020; Grnarova et al., 2017; Thekumparampil et al., 2019; Lu et al., 2020; Namkoong & Duchi, 2016; Sanjabi et al., 2018; Nouiehed et al., 2019; Lin et al., 2020a; Sinha et al., 2017; Chen et al., 2021), and nonconvex-nonconcave learning (Heusel et al., 2017; Balduzzi et al., 2018; Daskalakis & Panageas, 2018; Mertikopoulos et al., 2019; Loizou et al., 2020; Yang et al., 2020; Liu et al., 2021; Lin et al., 2018; Diakonikolas et al., 2021; Wang et al., 2020; Loizou et al., 2021; Fiez & Ratliff, 2021). There are so many studies on convergence, considering the length limit, the references listed here are not complete. Please refer to the related references concerning the above work. We investigate the generalization performance of minimax problems instead of the convergence behavior. Note that the convergence analysis also plays an essential role in this paper, formalized as strong PD empirical risk (please refer to Defi-
nition 1), which is defined on the function value difference and referred to as optimization error or primal-dual gap in some convergence literature (Lei et al., 2021; Nemirovski, 2005; Mokhtari et al., 2019; 2020).

heading: 3 PRELIMINARIES
text: Let X and Y be two parameter spaces in Rd. Let P be a probability measure defined on a sample space Z . We define f : X ×Y ×Z 7→ R and consider the following minimax optimization problem
min x∈X max y∈Y
F (x,y) := Ez∼P[f(x,y; z)]. (1)
The above minimax objective represents a expectation of a cost function f(x,y; z) for minimization variable x, maximization variable y and data variable z. Unfortunately, we typically are not available to the underlying distribution P. In practice, F is approximated by the corresponding empirical risk. Let S = {z1, ..., zn} be a dataset which are independent drawn according to P, the empirical risk is defined as
FS(x,y) = 1
n n∑ i=1 f(x,y; zi). (2)
Let the output of a (randomized) algorithmA on a dataset S beA(S) := (Ax(S), Ay(S)) ∈ X ×Y . Since A(S) is just an empirical approximated solution of the true minimax optimization problem, we are interested in studying how well A(S) generalizes to the unseen data. As claimed in (Farnia & Ozdaglar, 2021; Lei et al., 2021), the coupling between the minimization variable and the maximization variable in (1) makes minimax problems have many different generalization performance measures. These measures are collected in (Lei et al., 2021). For better readability, we use their symbols. Let E be the expectation with respect to (w.r.t.) the randomness of algorithm A and the dataset S. These generalization measures are listed below. Definition 1. (Lei et al., 2021) There are four groups of generalization measures.
1 (Primal Measures.) The primal population risk of a model x is defined as R(x) = supy∈Y F (x,y), and the corresponding primal empirical risk is defined as RS(x) = supy∈Y FS(x,y). Then, when using empirical risk RS(x) to bound R(x), we call this error of the model x the primal generalization error. While using optimal infx∈X R(x) to bound R(x), we call this error of the model x the excess primal population risk.
2 (Plain Measure.) When using FS(x,y) to bound F (x,y), we call the this error of a model (x,y) the plain generalization error.
3 (Strong Measures.) The strong primal-dual (PD) population risk of a model (x,y) is defined as
4s(x,y) = sup y′∈Y F (x,y′)− inf x′∈X F (x′,y),
and the corresponding strong PD empirical risk is defined as
4sS(x,y) = sup y′∈Y FS(x,y ′)− inf x′∈X FS(x ′,y).
Then, the strong PD generalization error4s(x,y)−4sS(x,y) of the model (x,y) is defined as( sup y′∈Y F (x,y′)− sup y′∈Y FS(x,y ′) ) + ( inf x′∈X FS(x ′,y)− inf x′∈X F (x′,y) ) .
4 (Weak Measures.) The weak PD population risk of a (randomized) model (x,y) is defined as
4w(x,y) = sup y′∈Y E[F (x,y′)]− inf x′∈X E[F (x′,y)],
and the corresponding weak PD empirical risk is defined as
4wS (x,y) = sup y′∈Y E[FS(x,y′)]− inf x′∈X E[FS(x′,y)].
Then, the weak PD generalization error4w(x,y)−4wS (x,y) of the model (x,y) is defined as( sup y′∈Y E[F (x,y′)]− sup y′∈Y E[FS(x,y′)] ) + ( inf x′∈X E[FS(x′,y)]− inf x′∈X E[F (x′,y)] ) .
Remark 1. We provide some discussions for the four groups of measures. (1. Primal Measures:) In the context of GANs, the primal population risk R(x) represents a divergence measure between the learned and true distributions, and in the context of adversarial training it represents the learner’s risk under adversarial perturbations (Farnia & Ozdaglar, 2021). One would be interested in the relationship between R(x) and its corresponding empirical risk RS(x), and the relationship between R(x) and its infimum infx′∈X R(x′). (2. Plain Measure:) This generalization measure is a direct extension of the standard generalization error in the minimization optimization. (3. Strong Measures:) 4sS(x,y) is referred to as the primal-dual gap in the optimization literature. 4s(x,y) is the primal-dual gap of the population risk. 4s(x,y) − 4sS(x,y) studies the difference between the population primal-dual gap and its empirical counterpart. (4. Weak Measures:) The difference between the strong and weak measures is that weak measures take the expectation over the randomness of the dataset and the algorithm, for instance, supy′∈Y F (x,y
′)− infx′∈X F (x′,y) in the strong measures and supy′∈Y E[F (x,y′)]− infx′∈X E[F (x′,y)] in the weak measures. Therefore, the upper bounds of weak measures hold in expectation, while the upper bounds of strong measures hold uniformly for any dataset.
Denote the Lp norm of a random variable z ∈ Z as ‖z‖p = (Ez|z|p)1/p. Let ‖ · ‖ be the Euclidean norm and 〈·, ·〉 be the inner product. A differentiable function g : W 7→ R is called µ-stronglyconvex in w if the following inequality holds for every w1,w2:
g(w1)− g(w2) ≥ 〈∇g(w2),w1 −w2〉+ µ
2 ‖w1 −w1‖2,
where∇ is the gradient operator. We say g is µ-strongly-concave if −g is µ-strongly-convex. Definition 2. Let g : X × Y 7→ R. Assume that X and Y are convex feasible sets. Then 1. g is µ-strongly-convex-strongly-concave (µ-SC-SC) if g(·,y) is µ-strongly-convex for any y ∈ Y and g(x, ·) is µ-strongly-concave for any x ∈ X . 2. g is convex-concave (C-C) if g is 0-SC-SC.
We then introduce the definition of algorithmic stability this paper used. Algorithmic stability plays an important role in studying the generalization behavior of a learning algorithm. Intuitively, an algorithm A : Zn 7→ (X ,Y) is said to be stable if the output model (Ax(S), Ay(S)) is insensitive to perturbations. Let S′ be a neighboring dataset that differs at most one single example to S. Definition 3 (Algorithmic Stability). Let A be a learning algorithm and > 0.
1. We say A is -uniformly-stable if for any training datasets S, S′ ∈ Zn we have sup z [f(Ax(S), Ay(S); z)− f(Ax(S′), Ay(S′); z)] ≤ .
2. We say A is -argument-stable if for any training datasets S, S′ ∈ Zn we have ‖Ax(S)−Ax(S′)‖+ ‖Ay(S)−Ay(S′)‖ ≤ .
From Definition 3, one can see that the uniform stability measures the sensitivity of the function values, while the argument stability measures the sensitivity of the arguments.
We finally introduce two standard assumptions in minimax problems. Assumption 1 implies f is Lipschitz continuous w.r.t. both x and y, while Assumption 2 implies f is smooth w.r.t. (x,y). Assumption 1 (Lipschitz continuity). Let L > 0. Assume that for any x ∈ X , y ∈ Y and z ∈ Z , f(x,y; z) satisfies
‖∇xf(x,y; z)‖ ≤ L and ‖∇yf(x,y; z)‖ ≤ L. Assumption 2 (Smoothness). Let β > 0. Assume that for any x1,x2 ∈ X , y1,y2 ∈ Y and z ∈ Z , f(x,y; z) satisfies∥∥∥∥(∇xf(x1,y1; z)−∇xf(x2,y2; z)∇yf(x1,y1; z)−∇yf(x2,y2; z) )∥∥∥∥ ≤ β ∥∥∥∥(x1 − x2y1 − y2 )∥∥∥∥ .
Under Assumption 1, the argument stability implies the uniform stability. Therefore, the argument stability is the main stability measure that we will focus on.

heading: 4 MAIN RESULTS
text: In this section, we provide sharper high probability bounds for the generalization measures of Definition 1, as shown in Theorem 1.
Theorem 1. Let A be a learning algorithm and > 0. Suppose |f(x,y; z)| ≤M for some M > 0 and x ∈ X ,y ∈ Y, z ∈ Z . Fixed any η > 0. There exists an absolute positive constant C. (a.) If the algorithm A is -uniformly stable, then for any δ > 0, with probability at least 1− δ,
F (Ax(S), Ay(S)) ≤ (1 + η)FS(Ax(S), Ay(S)) + C 1 + η
η (M n log(1/δ) + log2 n log 1 δ ) .
(b.) Assume that for all x, the function y 7→ F (x,y) is µ-strongly-concave. If the algorithm A is -argument stable and Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ,
R(Ax(S)) ≤ (1 + η)RS(Ax(S)) + C 1 + η
η (M n log 1 δ + (β µ + 1 ) L log2 n log 1 δ ) .
(c.) Assume that for all x and y, the function F (x,y) is µ-SC-SC. If the algorithm A is -argument stable and Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ,
4s (Ax(S), Ay(S)) ≤ 4sS(Ax(S), Ay(S)) + ηES 4sS (Ax(S), Ay(S)) + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) L log2 n ) log (1 δ ) .
(d.) Assume that for all x and y, the function F (x,y) is µ-SC-SC. If the algorithm A is -argument stable and Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ,
4s (Ax(S), Ay(S))−4sS(Ax(S), Ay(S)) ≤ ηES 4sS (Ax(S), Ay(S)) + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) L log2 n ) log (1 δ ) .
(e.) Assume that for all x, the function y 7→ F (x,y) is µ-strongly-concave. If the algorithm A is -argument stable and Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ,
R(Ax(S)) ≤ (1 + η) inf x∈X R(x)
+ C 2 + η
η (M n log 1 δ + (β µ + 1 ) L log2 n log 1 δ +4sS(Ax(S), Ay(S)) ) .
According to Definition 1 and Jensen’s inequality, we know that 4w(x,y) ≤ E[4s(x,y)] and 4wS (x,y) ≤ E[4sS(x,y)]. By this connection, we have 4w(x,y) −4wS (x,y) ≤ E[4s(x,y)] + |E[4sS(x,y)]|. We therefore obtain the following results for4w(x,y) and4w(x,y)−4wS (x,y). Corollary 1. Suppose the same conditions as Theorem 1 hold.
(f.) If the assumptions of Part (c) in Theorem 1 hold, then with probability at least 1− δ,
4w (Ax(S), Ay(S)) ≤ (1 + η)E4sS (Ax(S), Ay(S)) + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) L log2 n ) log (1 δ ) .
(g.) If the assumptions of Part (d) in Theorem 1 hold, then with probability at least 1− δ,
4w (Ax(S), Ay(S))−4wS (Ax(S), Ay(S)) ≤ |E4sS (Ax(S), Ay(S))| + (1 + η)E4sS (Ax(S), Ay(S)) +C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) L log2 n ) log (1 δ ) .
Remark 2. In Theorem 1, we have established a quantitative connection between the generalization measures and the stability measures. The complete proof of Theorem 1 is provided in Appendix A.
Part (a) provides the relationship between the uniform stability and the plain generalization error of (Ax(S), Ay(S)). If the uniform stability of algorithm A is of fast order O(1/n), then F (Ax(S), Ay(S)) is bounded by (1+η)O ( FS(Ax(S), Ay(S))+ logn log(1/δ) nη ) . Usually for a welltrained model (Ax(S), Ay(S)) over training set, the empirical risk FS(Ax(S), Ay(S)) is small or even zero (Lever et al., 2013; Yang et al., 2019; Cortes et al., 2021). If the empirical risk is of order O(1/n), then we can choose a proper constant for η and the plain generalization error will be of fast order O ( logn log(1/δ) n ) . It is O(1/n) when we hide the logarithmic term. In related work, (Lei et al., 2021) also establish the plain generalization error bound under the same assumptions, but their bound is of slow order O ( log n log(1/δ) +Mn− 1 2 √ log(1/δ) ) . Even if they get a sharper bound
for stability measure , the influence of O ( n− 1 2 √ log(1/δ) ) can not disappear. By comparison, we have completely removed the O(1/ √ n) term. Thus, our plain generalization error bound enables the fast O(1/n) rate when the empirical risk is small. Part (b) provides the connection between the argument stability and the primal generalization error. Similar to the analysis of Part (a), if both the argument stability of algorithm A and RS(Ax(S)) are of order O(1/n), then the primal generalization error implies a fast O ( 1/n ) rate. Considering that we assume the function f is well-behaved, i.e., Lipschitz continuity, smoothness, and the strong-concavity of its population risk F , and that RS(Ax(S)) is data-dependent, thus it is reasonable to assume RS(Ax(S)) is small for a well-trained model Ax(S) (Lever et al., 2013; Yang et al., 2019; Cortes et al., 2021). In (Lei et al., 2021), they also establish a bound for primal generalization error under the same assumptions. However, their bound is O ( Lβµ−1 logn log(1/δ) + Mn− 1 2 √ log(1/δ) ) , limited to the O(1/ √ n) order. In contrast, we successfully removed the O(1/ √ n) term, which makes the fast rate possible. (Farnia & Ozdaglar, 2021) studies the expected primal generalization error, i.e., bounding ES,A[R(Ax(S))] by ES,A[RS(Ax(S))]. They establish the connection between the stability measure and the expected error under the same assumptions as Part (b), which is then used to derive generalization bounds for (S)GDA, (S)GDmax and PPM algorithms. By comparison, our bound is derived in high probability.
Part (c) provides the relationship between the argument stability and the strong PD population risk. If both the argument stability of algorithm A and the strong PD empirical risk are all of the order O(1/n), the strong PD population risk will be of the fast order O(1/n). Note that in our proof for the gradient-based optimization algorithms, the strong PD empirical risk mainly has a dependence on the iterative number T (see Lemma 8 of GDA, Lemma 11 of SGDA, etc.). To obtain sharper generalization bounds, we require T to be associated with n, such as T = O(n2) for GDA, the strong PD empirical risk finally has a dependence on the sample size n. To our best knowledge, this is the first high probability strong PD population risk bound. The expected version of this risk is studied for the ESP solution in (Zhang et al., 2021a). However, the discussion there does not establish the connection between stability and generalization. Their analysis is restricted to the specific ESP problem. Under the same assumptions, they provide the upper bound of orderO (1/n). Compared with their result, our result is presented in high probability. Additionally, our strong PD population risk bound is applicable for any stable minimax optimization algorithms.
Part (d) provides the connection between the argument stability and the strong PD generalization error. Similarly, if both the argument stability of algorithm A and the strong PD empirical risk are all of O(1/n) order, the strong PD generalization error will be of the fast order O(1/n). Although Part (c) and Part (d) have a similar upper bound, they are different generalization measures (Lei et al., 2021). To our best knowledge, this is also the first high probability strong PD generalization error bound. The expected version of this generalization error is studied in (Lei et al., 2021), that is ES,A [4s(Ax(S), Ay(S))−4sS(Ax(S), Ay(S))]. Under the same assumptions, their expected strong PD generalization error is bounded by (1 + β/µ)L √ 2 , which can also be used to obtain O (1/n) order rate when is of order O(1/n). However, this bound is provided for the expected error, while our bound is high probabilistic and holds uniformly for any dataset.
Part (e) provides the relationship between the argument stability and the excess primal population risk. Similar to the analysis of Part (a) and Part (b), if the argument stability of algorithm A, the strong PD empirical risk, and infx∈X R(x) are all of the orderO(1/n), the excess primal population
risk will also be of the fast order O(1/n). Meanwhile, in the minimization learning problems, assuming the optimal population risk F ∗ is small or even zero, i.e., F ∗ ≤ O(1/n), can be found in (Lei & Ying, 2021a; Zhang et al., 2017; Zhang & Zhou, 2019; Srebro et al., 2010; Lei & Ying, 2020). Note that the optimal population risk F ∗ = O(1/n) just to show that the improved bound can be got under low noise conditions. F ∗ should be independent of n. Similar to the assumption on F ∗ and considering that we assume the function f is well-behaved, it will also be reasonable to assume infx∈X R(x) is small. High probability excess primal population risk bound is also studied for SGDA in (Lei et al., 2021). Their bound, however, is of slow order O ( (β/µ)n− 1 2 log n log2(1/δ)
) and is restricted to SGDA. By comparison, our result in Part (e) enables O(1/n) bounds for stable minimax learning algorithms since we have completely removed the O(1/ √ n) term.
We claim a noteworthy difference between (Farnia & Ozdaglar, 2021; Lei et al., 2021) and ours. In Part (a), Part (b), and Part (e), we study the upper bounds of F (Ax(S), Ay(S)), R(Ax(S)) (w.r.t. RS(Ax(S))), and R(Ax(S)) (w.r.t. infx∈X R(x)), respectively, while (Lei et al., 2021; Farnia & Ozdaglar, 2021) study the upper bounds of F (Ax(S), Ay(S)) − FS(Ax(S), Ay(S)), R(Ax(S))−RS(Ax(S)), and R(Ax(S))− infx∈X R(x) (or their expected form). One of our motivations to study such forms is that, in practice, we are often directly interested in the true risk, i.e., how the learned models behave on the testing data, such as F (Ax(S), Ay(S)), instead of the error between the true risk and empirical risk. Note that in the above comparison, for Theorem 1 and the results in (Lei et al., 2021; Farnia & Ozdaglar, 2021), we all take the right side of the generalization bound inequalities to compare, which is fair since our bounds can be written as F (Ax(S), Ay(S))− FS(Ax(S), Ay(S)) ≤ ηFS(Ax(S), Ay(S)) + C 1+ηη ( M n log(1/δ) + log2 n log 1 δ ), etc.
Remark 3. From Remark 2, one can see that compared with (Zhang et al., 2021a; Farnia & Ozdaglar, 2021; Lei et al., 2021), we have established sharper high probability generalization bounds. In the applications of Section 5, we will establish O(1/n) order bounds for two terms in Theorem 1: stability measures and strong PD empirical risk. Hence, the strong PD population risk and the strong PD generalization error will be of the fast orderO(1/n) when applying Theorem 1 to these applications. These bounds are clearly of order O(1/n) and sharper than the results in (Zhang et al., 2021a; Farnia & Ozdaglar, 2021; Lei et al., 2021). For the plain generalization error, the primal generalization error, and the excess primal population risk, to obtain O(1/n) order bounds for these applications, we need to assume the extra corresponding terms F (Ax(S), Ay(S)), R(Ax(S)), and infx∈X R(x) are of order O(1/n), respectively. The clear motivation is that in practice, learning algorithms achieve a small or even zero empirical risk, as discussed in Remark 2.
Remark 4. This remark discusses η in Part (a), Part (b), and Part (e). (1:) When establishing sharper generalization error bound (i.e., Pf −Pnf ), the existence of η is common in the standard statistical learning theory. Specifically, in the uniform localized convergence theory, the generalization error bound in (Bartlett et al., 2005) is of the form Pf ≤ ηη−1Pnf + O(ηr
∗ + η log(1/δ)n ) with η > 1 (see Theorem 3.3 and Theorem 4.1). In the PAC-Bayesian theory, the generalization bounds in (Catoni, 2007) (see Theorem 1.2.6), (Lever et al., 2013) (see Theorem 6), (Yang et al., 2019) (see Proposition 3.1 and Theorem 4.3), etc., also have η. For instance, the Catoni’s bound is of the form PQ ≤ 11−e−η ( ηPnQ + O(KL(Q‖Prior)+log(1/δ)n ) ) with η > 0 (Catoni, 2007). In the algorithmic stability theory, Theorem 1.2 in (Klochkov & Zhivotovskiy, 2021) is of the form Pf ≤ (1 + η)Pnf + 1+η η O(( log n + 1 n ) log( 1 δ )) with η > 0. In the recent Cortes’s deviation margin bounds (Cortes et al., 2021), they also imply a multiplier η. The above bounds can be transformed into the form of empirical risk multiplied by 1 + η, similar to our results. It is discussed in (Lever et al., 2013; Yang et al., 2019; Cortes et al., 2021; Bartlett et al., 2005; Klochkov & Zhivotovskiy, 2021) that this type of generalization error bound can obtain a fast rate when the empirical risk is small. Note that Part (e) also involves generalization error bounds due to the decomposition, see (31). The above generalization error analysis thus holds for Part (e). (2:) Furthermore, in (10), we show that F (Ax(S), Ay(S)) − FS(Ax(S), Ay(S)) ≤ O ( ( MF (Ax(S),Ay(S)) log(1/δ) n ) 1 2 +
log( 1δ ) ) , where M means that |f(x,y; z)| ≤M,∀x,y, z. Using the elementary inequality √ ab ≤ ηa + 1η b for any a, b, η > 0 and by some rearrangements, the form of Part (a) appears. This is the reason why η exists. The corresponding bound in (Lei et al., 2021) is F (Ax(S), Ay(S)) − FS(Ax(S), Ay(S)) ≤ O ( log n log( 1δ ) + Mn − 12 log1/2( 1δ ) ) . Focusing on the dominated term, it is clear that F (Ax(S), Ay(S)) M since F (Ax(S), Ay(S)) is data-dependent, which implies that our plain generalization error bound is sharper. Similar analysis holds for Part (b) and Part (e).
In summary, the above analyses from two different perspectives support our claim that Part (a), Part (b), and Part (e) provide sharper high probability generalization bounds. Remark 5. Different measures quantify different degrees of the generalization error. Thus, deriving different generalization measures requires different assumptions (Lei et al., 2021; Zhang et al., 2021a; Farnia & Ozdaglar, 2021). Strong measures require stronger assumptions compared with the weak (Lei et al., 2021). For instance the term supy∈Y F (Ax(S),y) in4s(Ax(S), Ay(S)), one has to consider the fact that for differentAx(S), y is different, which makes the proof more challenging. While in4w(Ax(S), Ay(S)) and4w(Ax(S), Ay(S))−4wS (Ax(S), Ay(S)), both the supremum over Ax(S) and Ay(S) are outside the expectation operator, thus one does not need to consider the coupling between Ax(S) and y. The upper bounds shown in Corollary 1 directly derived from Theorem 1 are sub-optimal since4w(Ax(S), Ay(S)) and4w(Ax(S), Ay(S))−4wS (Ax(S), Ay(S)) are pretty weak generalization measures (Lei et al., 2021). We list Corollary 1 here to suggest that, when Theorem 1 is established, the fast orderO(1/n) is easy to be achieved for4w(Ax(S), Ay(S)) and 4w(Ax(S), Ay(S)) − 4wS (Ax(S), Ay(S)). On the other hand, the two weak generalization measures in (Zhang et al., 2021a) is studied for the specific ESP solution, while Corollary 1 is applicable for any stable minimax learning algorithms, it thus may be useful in some applications.

heading: 5 APPLICATIONS
text: We now apply Theorem 1 to the ESP solution and several gradient-based optimization algorithms: GDA, SGDA, PPM, EG, and OGDA. Considering the length limit, we postpone the introductions and theorems of these applications to the Appendix. Here, we provide the generalization bounds of these optimization algorithms in Table 1. Since our goal is to prove bounds with better rates, that is, which decrease fast with n 7→ ∞, thus for brevity, we defer the explicit results to the Appendix.

heading: 5.1 DESCRIPTIONS OF TABLE 1
text: Table 1 lists almost all existing generalization bounds in minimax learning. In Table 1, LN means the low noise conditions, i.e., the corresponding F (Ax(S), Ay(S)), R(Ax(S)), and infx∈X R(x) of these applications are of order O(1/n). For instance, for the ESP solution (x̂∗S , ŷ∗S), we assume F (x̂∗S , ŷ ∗ S), R(x̂ ∗ S), and infx∈X R(x) are of order O(1/n) for the plain generalization error, the primal generalization error, and the excess primal population risk, respectively. For other learning algorithms, please refer to the Remarks in the Appendix. In Table 1, we compare our results with (Zhang et al., 2021a; Farnia & Ozdaglar, 2021; Lei et al., 2021) in the way described in the last paragraph of Remark 2, which is fair. (E.) denotes that the bound is derived in expectation, while (H.P.) denotes high probability. Since our results are all established with high probability, we thus omit (H.P.) for brevity. The descriptions of other notations are shown in Appendix H.
In Table 1, (Zhang et al., 2021a) and (Farnia & Ozdaglar, 2021) focus on the expected generalization measures. The learning bounds of the ESP solution in (Zhang et al., 2021a) are improved to high probability guarantees. Compared with (Farnia & Ozdaglar, 2021), we have provided high probability primal generalization error bounds for GDA, SGDA, and PPM. Additionally, we also study other generalization measures. (Lei et al., 2021) focus on SGDA and mainly provide guarantees for weak generalization measures, i.e., weak PD risk and weak PD generalization error. In contrast, we have developed bounds for strong PD risk and strong PD generalization error. Note that the two type of bounds don’t require the LN condition. Moreover, although (Lei et al., 2021) provide two high probability bounds, however, in slow order. Note that in addition to the classical GDA, SGDA, and PPM, we also provide sharper high probability bounds for EG and OGDA in that their widespread use in training GANs (Mokhtari et al., 2019; Daskalakis et al., 2017; Liang & Stokes, 2019).

heading: 6 CONCLUSION
text: In this paper, we provide a systematical analysis of sharper generalization bounds for minimax problems. We first establish sharper high probability bounds for almost all existing generalization measures via algorithmic stability and then apply these bounds to several important applications. We believe that our research can provide in-depth insights into minimax learning problems. For future work, it would be important to relax the assumptions in this paper. Also, it would be interesting to investigate how well other theoretical tools perform on the generalization of minimax problems.

heading: A PROOF OF THEOREM 1
text: We now provide proofs of Theorem 1. For better readability, we restate Theorem 1 below.
Theorem 2. Let A be a learning algorithm and > 0. Suppose |f(x,y; z)| ≤M for some M > 0 and x ∈ X ,y ∈ Y, z ∈ Z . Fixed any η > 0. There exists an absolute positive constant C. (a.) If the algorithm A is -uniformly stable, then for any δ > 0, with probability at least 1− δ,
F (Ax(S), Ay(S)) ≤ (1 + η)FS(Ax(S), Ay(S)) + C 1 + η
η (M n log(1/δ) + log2 n log 1 δ ) .
(b.) Assume that for all x, the function y 7→ F (x,y) is µ-strongly-concave. If the algorithm A is -argument stable and Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ,
R(Ax(S)) ≤ (1 + η)RS(Ax(S)) + C 1 + η
η (M n log 1 δ + (β µ + 1 ) L log2 n log 1 δ ) .
(c.) Assume that for all x and y, the function F (x,y) is µ-SC-SC. If the algorithm A is -argument stable and Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ,
4s (Ax(S), Ay(S)) ≤ 4sS(Ax(S), Ay(S)) + ηES 4sS (Ax(S), Ay(S)) + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) L log2 n ) log (1 δ ) .
(d.) Assume that for all x and y, the function F (x,y) is µ-SC-SC. If the algorithm A is -argument stable and Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ,
4s (Ax(S), Ay(S))−4sS(Ax(S), Ay(S)) ≤ ηES 4sS (Ax(S), Ay(S)) + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) L log2 n ) log (1 δ ) .
(e.) Assume that for all x, the function y 7→ F (x,y) is µ-strongly-concave. If the algorithm A is -argument stable and Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ,
R(Ax(S)) ≤ (1 + η) inf x∈X R(x)
+ C 2 + η
η (M n log 1 δ + (β µ + 1 ) L log2 n log 1 δ +4sS(Ax(S), Ay(S)) ) .
Remark 6. To prove sharper high probability bounds than (Lei et al., 2021), the concentration inequality for a summation of weakly-dependent random variables proposed in (Bousquet et al., 2020) (Lemma 2 in Appendix A) plays a key role in our analysis. However, the direct use of this inequality will inevitably lead to a slow order bound since it contains a sampling error of slow order O(1/ √ n). We exploit the proof techniques of the recent breakthrough work (Klochkov & Zhivotovskiy, 2021) to make new constructions of gi(S) so that the parameter M in Lemma 2 is 0. However, this proof technique of (Klochkov & Zhivotovskiy, 2021) can not be directly extended to minimax problems. The coupling construction between the minimization variables and the maximization variables makes the proofs of minimax problems more difficult than the minimization problem studied by (Klochkov & Zhivotovskiy, 2021). We must proceed with novel decompositions for the generalization measures. Note that different decompositions are required for different generalization measures. A pretty technical decomposition is exploited in the proof of Part (c). Moreover, the proof of minimax problems needs refined analyses due to the minimax structure. For instance, in proving the primal generalization error, we need to quantify the fact that for different Ax(S), the optimal y is different in R(Ax(S)). And the analysis of excess primal population risk in Part (e) is different from the excess risk analysis in (Klochkov & Zhivotovskiy, 2021). The reason is that the supremum operator in infx∈X R(x) makes the Bernstein condition used in (Klochkov & Zhivotovskiy, 2021) not applicable for excess primal population risk. Additionally, (Klochkov & Zhivotovskiy, 2021) only study ERM and GD, while we study more optimization algorithms: SGDA, PPM, EG, and OGDA. In summary, compared with (Klochkov & Zhivotovskiy, 2021), we believe the techniques we develop to adapt to the minimax problems are novel. Remark 7. According to Definition 1 and Jensen’s inequality, we know that 4wS (x,y) ≤ E[4sS(x,y)]. Meanwhile, since we will provide the strong PD empirical risk bounds for several important optimization algorithms in Section 5, it thus implies that we also establish bounds with fast rates for4wS (x,y).
To begin the proof of Theorem 1, we first introduce some key lemmas on concentration inequalities. The first lemma translates a moment bound into a high probability bound. Lemma 1. (Bousquet et al., 2020) Let Z be a random variable with
‖Z‖p ≤ √ pa+ pb
for some a, b > 0 and for any p ≥ 2. Then for any δ ∈ (0, 1) we have, with probability at least 1− δ,
|Z| ≤ e ( a √ log (e δ ) + b log (e δ )) ,
where e is the base of the natural logarithm.
The second lemma establishes a concentration inequality for a summation of weakly-dependent random variables. Lemma 2. (Bousquet et al., 2020) Let S = {z1, ..., zn} be a set of independent random variables each taking values in Z and M > 0. Denote [n] as the set {1, ..., n}. Define S\{zi} be set {z1, ..., zi−1, zi+1, ..., zn}. Let g1, ..., gn be some functions gi : Zn 7→ R such that the following inequalities hold for any i ∈ [n],
• ∣∣ES\{zi}[gi(S)]∣∣ ≤M almost surely (a.s.),
• Ezi [gi(S)] = 0 a.s.,
• for any j ∈ [n] with j 6= i, and z′′j ∈ Z∣∣gi(S)− gi(z1, ..., zj−1, z′′j , zj+1, ..., zn)∣∣ ≤ β. Then, for any p ≥ 2 ∥∥∥ n∑
i=1
gi(S) ∥∥∥ p ≤ 12 √ 2pnβdlog2 ne+ 4M √ pn.
The following definition and lemma give the concentration inequality for non-negative weakly selfbounded functions.
Definition 4. (Weakly Self-Bounded Function) Assume that a, b > 0. A function f : Zn 7→ [0,+∞) is said to be (a, b)-weakly self-bounded if there exist functions fi : Zn−1 7→ [0,+∞) that satisfies for all Zn ∈ Zn,
n∑ i=1 (f(Zn)− fi(Zn))2 ≤ af(Zn) + b.
Lemma 3. (Klochkov & Zhivotovskiy, 2021) Suppose that z1, ..., zn are independent random variables and the function f : Zn 7→ [0,+∞) is (a, b)-weakly self-bounded and the corresponding function fi satisfy fi(Zn) ≥ f(Zn) for i = 1, ..., n and any Zn ∈ Zn. Then, for any t > 0,
Pr(Ef(z1, ..., zn) ≥ f(z1, ..., zn) + t) ≤ exp ( − t 2
2aEf(z1, ..., zn) + 2b
) .
The following lemma is the classical Bernstein concentration inequality.
Lemma 4. (Boucheron et al., 2013) Let z1, ..., zn be i.i.d. random variables and assume that E[zi] = µ. Suppose |zi| ≤ c for any i. Then for any δ ∈ (0, 1), with probability at least 1− δ,∣∣∣ 1
n n∑ i=1 zi − µ ∣∣∣ ≤√2σ2 log(1/δ) n + 2c log(1/δ) 3n ,
where σ2 is the variance of zi.
A.1 PROOF OF PART (A)
We first prove the plain generalization error bound.
Proof. Let S = {z1, ..., zn} be a set of independent random variables each taking values in Z and S′ = {z′1, ..., z′n} be its independent copy. For any i ∈ [n], define S(i) = {z1, ..., zi−1, z′i, zi+1, ..., zn} be a dataset by replacing the i-th sample in S with another i.i.d. sample z′i. We first have the following decomposition
nF (Ax(S), Ay(S))− nFS(Ax(S), Ay(S))
= n∑ i=1 EZ [f(Ax(S), Ay(S);Z)− Ez′i [f(Ax(S (i)), Ay(S (i));Z)]]
+ n∑ i=1 Ez′i [EZ [f(Ax(S (i)), Ay(S (i));Z)]− f(Ax(S(i)), Ay(S(i)); zi)]
+ n∑ i=1 Ez′i [f(Ax(S (i)), Ay(S (i)); zi)]− n∑ i=1 f(Ax(S), Ay(S); zi).
According to the definition of uniform stability (Part 1 of Definition 3), we have
nF (Ax(S), Ay(S))− nFS(Ax(S), Ay(S)) ≤ 2n + n∑ i=1 gi(S),
where we have introduced gi(S) = Ez′i [EZ [f(Ax(S (i)), Ay(S (i));Z)] − f(Ax(S
(i)), Ay(S (i)); zi)]. Thus, by a rearrangement, we have∣∣∣nF (Ax(S), Ay(S))− nFS(Ax(S), Ay(S))− n∑
i=1
gi(S) ∣∣∣ ≤ 2n . (3)
Then, for any i = 1, ..., n, we define hi(S) = gi(S) − ES\{zi}[gi(S)]. It is easy to verify that ES\{zi}[hi(S)] = 0 and Ezi [hi(S)] = Ezi [gi(S)]− EziES\{zi}[gi(S)] = 0− 0 = 0. Also, for any j ∈ [n] with j 6= i, and z′′j ∈ Z , we have the following inequality∣∣hi(S)− hi(z1, ..., zj−1, z′′j , zj+1, ..., zn)∣∣ ≤ ∣∣gi(S)− gi(z1, ..., zj−1, z′′j , zj+1, ..., zn)∣∣
+ ∣∣ES\{zi}[gi(S)]− ES\{zi}[gi(z1, ..., zj−1, z′′j , zj+1, ..., zn)]∣∣ .
For the first term |gi(S) − gi(z1, ..., zj−1, z′′j , zj+1, ..., zn)|, it can be bounded by 2 according to the definition of uniform stability. Similar result holds for the second term ∣∣ES\{zi}[gi(S)]− ES\{zi}[gi(z1, ..., zj−1, z′′j , zj+1, ..., zn)]∣∣ according to the definition of uniform stability. By a combination of the above analysis, we get |hi(S) − hi(z1, ..., zj−1, z ′′ j , zj+1, ..., zn)| ≤ 4 .
We thus have verified that the three conditions in Lemma 2 are satisfied for hi(S). There will hold the following result for any p ≥ 2∥∥∥ n∑
i=1
hi(S) ∥∥∥ p ≤ 48 √ 2 pndlog2 ne. (4)
Furthermore, we can derive that
nF (Ax(S), Ay(S))− nFS(Ax(S), Ay(S))− n∑ i=1 gi(S) + n∑ i=1 hi(S)
=nF (Ax(S), Ay(S))− nFS(Ax(S), Ay(S))− n∑ i=1 ES\{zi}[gi(S)] =nF (Ax(S), Ay(S))− nFS(Ax(S), Ay(S))− nES′F (Ax(S′), Ay(S′)) + nES′FS(Ax(S′), Ay(S′))
Due to the i.i.d. property between S and S′, we know that ES′F (Ax(S′), Ay(S′)) = ESF (Ax(S), Ay(S)).
Thus, combined (3) with (4), we have
‖nF (Ax(S), Ay(S))− nFS(Ax(S), Ay(S))− nESF (Ax(S), Ay(S)) + nES′FS(Ax(S′), Ay(S′))‖p
≤ ∥∥∥nF (Ax(S), Ay(S))− nFS(Ax(S), Ay(S))− n∑
i=1
gi(S) ∥∥∥ p
+ ∥∥∥ n∑ i=1 gi(S)− nESF (Ax(S), Ay(S)) + nES′FS(Ax(S′), Ay(S′)) ∥∥∥ p
= ∥∥∥nF (Ax(S), Ay(S))− nFS(Ax(S), Ay(S))− n∑
i=1
gi(S) ∥∥∥ p + ∥∥∥ n∑ i=1 hi(S) ∥∥∥ p
≤ 2n + 48 √
2 pndlog2 ne ≤ 50 √ 2 pndlog2 ne.
According to Lemma 1, for any δ ∈ (0, 1), with probability at least 1− δ/3, we have
F (Ax(S), Ay(S))− FS(Ax(S), Ay(S)) ≤|ES′FS(Ax(S′), Ay(S′))− ESF (Ax(S), Ay(S))|+ 50 √ 2e dlog2 ne log(3e/δ). (5)
We now begin to bound the term ES′FS(Ax(S′), Ay(S′)) − ESF (Ax(S), Ay(S)). There holds that ESES′FS(Ax(S′), Ay(S′)) = ESF (Ax(S), Ay(S)). We first consider the variance of ES′f(Ax(S′), Ay(S′); zi). By the Jensen’s inequality, we have
Ezi [(ES′f(Ax(S′), Ay(S′); zi))2] ≤ EziES′ [(f(Ax(S′), Ay(S′); zi))2] = EZES′ [(f(Ax(S′), Ay(S′);Z))2] = EZES [(f(Ax(S), Ay(S);Z))2].
Then, by the Bernstein inequality in Lemma 4, we obtain the following inequality with probability at least 1− δ/3,
|ES′FS(Ax(S′), Ay(S′))− ESF (Ax(S), Ay(S))| (6) ≤ √
2EZES [(f(Ax(S), Ay(S);Z))2] log(3/δ) n + 2M log(3/δ) 3n .
Combined (5) with (6), we finally obtain that with probability at least 1− 2δ/3,
F (Ax(S), Ay(S))− FS(Ax(S), Ay(S)) ≤ √
2EZES [(f(Ax(S), Ay(S);Z))2] log(3/δ) n + 2M log(3/δ) 3n + 50 √ 2e dlog2 ne log(3e/δ).
(7)
In the following, we define q = q(z1, ..., zn) = EZ [(f(Ax(S), Ay(S);Z))2] and qi = qi(z1, ..., zn) = supzi∈Z q(z1, ..., zn). So there holds qi ≥ q for any i = 1, .., n and any {z1, ..., zn} ∈ Zn. Also, there holds that
n∑ i=1 (q − qi)2
= n∑ i=1 ( EZ [(f(Ax(S), Ay(S);Z))2]− sup zi∈Z EZ [(f(Ax(S), Ay(S);Z))2] )2 ≤
n∑ i=1 2 ( EZ [ f(Ax(S), Ay(S);Z) + sup zi∈Z f(Ax(S), Ay(S);Z) ])2 ≤n 2 (2EZ [(f(Ax(S), Ay(S);Z))] + )2
≤8n 2q + 2n 4, (8)
where the first inequality follows from the Jensen’s inequality and the definition of uniform stability, and where the second inequality also follows from the definition of uniform stability.
From (8), we know that q is (8n 2, 2n 4) weakly self-bounded. Thus, by Lemma 3, we obtain that with probability at least 1− δ/3,
ESEZ [(f(Ax(S), Ay(S);Z))2]− EZ [(f(Ax(S), Ay(S);Z))2] ≤ √ (16n 2ESEZ [(f(Ax(S), Ay(S);Z))2] + 4n 4) log(3/δ)
= √( ESEZ [(f(Ax(S), Ay(S);Z))2] + 1 4 2 ) 16n 2 log(3/δ)
≤1 2
( ESEZ [(f(Ax(S), Ay(S);Z))2] + 1 4 2 ) + 8n 2 log(3/δ),
where the last inequality follows from that √ ab ≤ a+b2 for all a, b > 0.
Since EZ [(f(Ax(S), Ay(S);Z))2] ≤MF (Ax(S), Ay(S)), we have
ESEZ [(f(Ax(S), Ay(S);Z))2]− 2MF (Ax(S), Ay(S)) ≤ 1
4 2 + 16n 2 log(3/δ). (9)
Substituting (9) into (7), we finally obtain that with probability at least 1− δ,
F (Ax(S), Ay(S))− FS(Ax(S), Ay(S))
≤
√ (4MF (Ax(S), Ay(S)) + 1 2 2 + 32n 2 log(3/δ)) log(3/δ)
n
+ 2M log(3/δ) 3n + 50 √ 2e dlog2 ne log(3e/δ). (10)
According to inequalities √ ab ≤ ηa+ 1η b and √ a+ b ≤ √ a+ √ b for any a, b, η > 0, we have the following inequality with probability at least 1− δ
F (Ax(S), Ay(S))− FS(Ax(S), Ay(S))
≤
√ ( 12 2 + 32n 2 log(3/δ)) log(3/δ)
n +
η
1 + η F (Ax(S), Ay(S)) +
1 + η
η
4M log(3/δ)
n
+ 2M log(3/δ)
3n + 50
√ 2e dlog2 ne log(3e/δ),
which implies that
F (Ax(S), Ay(S))− (1 + η)FS(Ax(S), Ay(S)) ≤(1 + η) (√ ( 12 2 + 32n 2 log(3/δ)) log(3/δ)
n +
1 + η
η
4M log(3/δ)
n
+ 2M log(3/δ)
3n + 50
√ 2e dlog2 ne log(3e/δ) ) ≤C 1 + η
η (M n log(1/δ) + log2 n log(1/δ) ) ,
where C is an absolute constant. The proof is complete.
A.2 PROOF OF PART (B)
We then prove the primal generalization error bound. Before presenting the proof, we first introduce a lemma that quantifies the sensitivity of the optimal y and x w.r.t the perturbation of x and y respectively.
Lemma 5. (Zhang et al., 2021a) Let f : X ×Y 7→ R. Assume that f is µ-strongly-convex-stronglyconcave. Suppose that for any x,x′ ∈ X and y,y′ ∈ Y we have
‖∇yf(x,y)−∇yf(x′,y)‖ ≤ β‖x− x′‖ and ‖∇xf(x,y)−∇xf(x,y′)‖ ≤ β‖y − y′‖.
Define x∗(y) = arg minx∈X h(x,y) and y∗(x) = arg maxy∈Y h(x,y) for any y and x respectively. Then, for any x,x′ ∈ X and y,y′ ∈ Y there holds that
‖y∗(x)− y∗(x′)‖ ≤ β µ ‖x− x′‖ and ‖x∗(y)− x∗(y′)‖ ≤ β µ ‖y − y′‖.
The proof of Part (b) shares similar proof techniques with Part (a), but requires a novel decomposition and several important changes. For instance, Lemma 5 should be needed to quantify the fact that for different Ax(S), the optimal y is different in R(Ax(S)).
Proof. Let S = {z1, ..., zn} be a set of independent random variables each taking values in Z and S′ = {z′1, ..., z′n} be its independent copy. For any i ∈ [n], define S(i) =
{z1, ..., zi−1, z′i, zi+1, ..., zn} be a dataset by replacing the i-th sample in S with another i.i.d. sample z′i. Denote y ∗ S = arg maxy∈Y F (Ax(S),y) and ŷ ∗ S = arg maxy∈Y FS(Ax(S),y). We have the following decomposition
nR(Ax(S))− nRS(Ax(S)) =nF (Ax(S),y ∗ S)− nFS(Ax(S), ŷ∗S)
= n∑ i=1 EZ [f(Ax(S),y∗S ;Z)− Ez′i [f(Ax(S (i)),y∗S(i) ;Z)]]
+ n∑ i=1 Ez′i [EZ [f(Ax(S (i)),y∗S(i) ;Z)]− f(Ax(S (i)),y∗S(i) ; zi)]
+ n∑ i=1 Ez′i [f(Ax(S (i)),y∗S(i) ; zi)]− n∑ i=1 f(Ax(S), ŷ ∗ S ; zi). (11)
Firstly, we have
f(Ax(S),y ∗ S ;Z)− f(Ax(S(i)),y∗S(i) ;Z)
=f(Ax(S),y ∗ S ;Z)− f(Ax(S),y∗S(i) ;Z) + f(Ax(S),y ∗ S(i) ;Z)− f(Ax(S (i)),y∗S(i) ;Z) ≤L‖y∗S − y∗S(i)‖+ L‖Ax(S)−Ax(S (i))‖
≤ ( 1 + β
µ
) L‖Ax(S)−Ax(S(i))‖
≤ ( 1 + β
µ
) L , (12)
where the second inequality follows from Lemma 5 with the fact that F is smooth and µ-SC-SC.
Secondly, we have n∑ i=1 Ez′i [f(Ax(S (i)),y∗S(i) ; zi)]
= n∑ i=1 Ez′i [f(Ax(S (i)),y∗S(i) ; zi)− f(Ax(S),y ∗ S ; zi) + f(Ax(S),y ∗ S ; zi)]
≤ n∑ i=1 Ez′i ( 1 + β µ ) L‖Ax(S)−Ax(S(i))‖+ n∑ i=1 f(Ax(S),y ∗ S ; zi)
≤ ( 1 + β
µ
) Ln + n∑ i=1 f(Ax(S),y ∗ S ; zi),
where the first and the last inequalities follow from (12). Substituting the above two results into (11), we obtain that
nF (Ax(S),y ∗ S)− nFS(Ax(S), ŷ∗S)
≤2 ( 1 + β
µ
) Ln + n∑ i=1 f(Ax(S),y ∗ S ; zi) + n∑ i=1 gi(S)− n∑ i=1 f(Ax(S), ŷ ∗ S ; zi)
≤2 ( 1 + β
µ
) Ln + n∑ i=1 gi(S),
where the last inequality follows from the facts that ∑n i=1 f(Ax(S),y
∗ S ; zi) −∑n
i=1 f(Ax(S), ŷ ∗ S ; zi) ≤ 0 and that we have introduced gi(S) = Ez′i [EZ [f(Ax(S (i)),y∗ S(i) ;Z)]− f(Ax(S (i)),y∗ S(i) ; zi)].
Now we get
nF (Ax(S),y ∗ S)− nFS(Ax(S), ŷ∗S)− n∑ i=1 gi(S) ≤ 2 ( 1 + β µ ) Ln . (13)
For any i = 1, ..., n, we define hi(S) = gi(S)− ES\{zi}[gi(S)].
We also get that ES\{zi}[hi(S)] = 0 and Ezi [hi(S)] = Ezi [gi(S)]−EziES\{zi}[gi(S)] = 0−0 = 0. Moreover, for any j ∈ [n] with j 6= i, and z′′j ∈ Z , we have the following inequality
|hi(S)− hi(z1, ..., zj−1, z′′j , zj+1, ..., zn)| ≤ |gi(S)− gi(z1, ..., zj−1, z′′j , zj+1, ..., zn)| + |ES\{zi}[gi(S)]− ES\{zi}[gi(z1, ..., zj−1, z ′′ j , zj+1, ..., zn)]|.
Denote S(i)j as the set collected by replacing the j-th element of S (i) with z′′j . For the first term |gi(S)− gi(z1, ..., zj−1, z′′j , zj+1, ..., zn)|, we have∣∣∣gi(S)− gi(z1, ..., zj−1, z′′j , zj+1, ..., zn)∣∣∣ = ∣∣∣Ez′i[EZ [f(Ax(S(i)),y∗S(i) ;Z)]− f(Ax(S(i)),y∗S(i) ; zi)] − Ez′i [ EZ [f(Ax(S(i)j ),y ∗ S
(i) j
;Z)]− f(Ax(S(i)j ),y ∗ S
(i) j
; zi) ]∣∣∣
≤ ∣∣∣Ez′i[EZ [f(Ax(S(i)),y∗S(i) ;Z)]− f(Ax(S(i)j ),y∗S(i)j ;Z)] ∣∣∣ + ∣∣∣Ez′i[f(Ax(S(i)),y∗S(i) ; zi)− f(Ax(S(i)j ),y∗S(i)j ; zi)]
∣∣∣. (14) Furthermore, for any z, we have the following result which can help to bound the above inequality.∣∣∣f(Ax(S(i)),y∗S(i) ; z)− f(Ax(S(i)j ),y∗S(i)j ; z)
∣∣∣ ≤ ∣∣∣f(Ax(S(i)),y∗S(i) ; z)− f(Ax(S(i)),y∗S(i)j ; z) ∣∣∣+ ∣∣∣f(Ax(S(i)),y∗S(i)j ; z)− f(Ax(S(i)j ),y∗S(i)j ; z) ∣∣∣
≤L ∥∥∥y∗S(i) − y∗S(i)j ∥∥∥+ L∥∥∥Ax(S(i))−Ax(S(i)j )∥∥∥ ≤ (β µ + 1 ) L ∥∥∥Ax(S(i))−Ax(S(i)j )∥∥∥
≤ (β µ + 1 ) L , (15)
where the third inequality follows from Lemma 5. Thus, we can bound the first term by 2 ( β µ+1 ) L . By a similar analysis, the second term |ES\{zi}[gi(S)] − ES\{zi}[gi(z1, ..., zj−1, z′′j , zj+1, ..., zn)]| can also be bounded by 2 ( β µ + 1 ) L .
We now have verified that the three conditions in Lemma 2 are satisfied for hi(S). We obtain that for any p ≥ 2, there holds∥∥∥ n∑
i=1
hi(S) ∥∥∥ p ≤ 48 √ 2pn (β µ + 1 ) L dlog2 ne. (16)
Thus, combined (13) with (16), we derive that
‖nF (Ax(S),y∗S)− nFS(Ax(S), ŷ∗S)− nES′F (Ax(S′),y∗S′) + nES′FS(Ax(S′),y∗S′)‖p
= ∥∥∥nF (Ax(S),y∗S)− n∑
i=1
gi(S) + n∑ i=1 gi(S)− n∑ i=1 ES\{zi}[gi(S)] ∥∥∥ p
≤ ∥∥∥nF (Ax(S),y∗S)− nFS(Ax(S), ŷ∗S)− n∑
i=1
gi(S) ∥∥∥ p + ∥∥∥ n∑ i=1 hi(S) ∥∥∥ p
≤2 ( 1 + β
µ
) Ln + 48 √ 2pn (β µ + 1 ) L dlog2 ne
≤50 √ 2 ( 1 + β
µ
) Lpndlog2 ne. (17)
Then, according to Lemma 1, for any δ ∈ (0, 1), with probability at least 1− δ/3, we have F (Ax(S),y ∗ S)− FS(Ax(S), ŷ∗S)
≤|ES′F (Ax(S′),y∗S′)− ES′FS(Ax(S′),y∗S′)|+ 50 √ 2 eL ( 1 + β
µ
) dlog2 ne log(3e/δ). (18)
With a similar analysis to the proof of Part (a), we now begin to bound the variance of ES′f(Ax(S′),y∗S′ ; zi).
Ezi [(ES′f(Ax(S′),y∗S′ ; zi))2] ≤ EziES′ [(f(Ax(S′),y∗S′ ; zi))2] = EZES′ [(f(Ax(S′),y∗S′ ;Z))2] = EZES [(f(Ax(S),y∗S ;Z))2].
There holds that ESES′FS(Ax(S′),y∗S′) = ES′F (Ax(S′),y∗S′). Then, by the Bernstein inequality in Lemma 4, we obtain that with probability at least 1− δ/3,
|ES′F (Ax(S′),y∗S′)− ES′FS(Ax(S′),y∗S′)| ≤ √
2EZES [(f(Ax(S),y∗S ;Z))2] log(3/δ) n + 2M log(3/δ) 3n . (19)
Combined (18) with (19), we finally obtain that with probability at least 1− 2δ/3, F (Ax(S),y ∗ S)− FS(Ax(S), ŷ∗S)
≤
√ 2EZES [(f(Ax(S),y∗S ;Z))2] log ( 3 δ ) n + 2M log ( 3 δ ) 3n + 50 √ 2 eL β + µ µ dlog2 ne log (3e δ ) .
(20)
In the following, we define q = q(z1, ..., zn) = EZ [(f(Ax(S),y∗S ;Z))2] and qi = qi(z1, ..., zn) = supzi∈Z q(z1, ..., zn). So there holds qi ≥ q for any i = 1, .., n and any {z1, ..., zn} ∈ Z
n. Also, there holds that
n∑ i=1 (q − qi)2
= n∑ i=1 ( EZ [(f(Ax(S),y∗S ;Z))2]− sup zi∈Z EZ [(f(Ax(S),y∗S ;Z))2] )2 ≤
n∑ i=1 ( EZ [ sup zi∈Z (f(Ax(S),y ∗ S ;Z)) 2 − (f(Ax(S),y∗S ;Z))2 ])2
≤n (β µ + 1 )2 L2 2 ( 2EZ [f(Ax(S),y∗S ;Z)] + (β µ + 1 ) L )2 ≤8n (β µ + 1 )2 L2 2q + 2n (β µ + 1 )4 L4 4,
where the first inequality follows from the Jensen’s inequality and the second inequality follows from a similar analysis to (12) or (15). Now, we know that q is ( 8n ( β µ + 1 )2 L2 2, 2n ( β µ + 1 )4 L4 4 ) - weakly self-bounded. Thus, by Lemma 3, we obtain the following inequality with probability at least 1− δ/3,
ESEZ [(f(Ax(S),y∗S ;Z))2]− EZ [(f(Ax(S),y∗S ;Z))2]
≤ √( 16n (β µ + 1 )2 L2 2ESEZ [(f(Ax(S),y∗S ;Z))2] + 4n (β µ + 1 )4 L4 4 ) log(3/δ)
= √( ESEZ [(f(Ax(S),y∗S ;Z))2] + 1
4 (β µ + 1 )2 L2 2 ) 16n (β µ + 1 )2 L2 2 log(3/δ)
≤1 2
( ESEZ [(f(Ax(S),y∗S ;Z))2] + 1
4 (β µ + 1 )2 L2 2 ) + 8n (β µ + 1 )2 L2 2 log(3/δ),
where the last inequality follows from √ ab ≤ a+b2 for all a, b > 0.
Since EZ [(f(Ax(S),y∗S ;Z))2] ≤MF (Ax(S),y∗S), we have ESEZ [(f(Ax(S),y∗S ;Z))2]− 2MF (Ax(S),y∗S)
≤1 4 (β µ + 1 )2 L2 2 + 16n (β µ + 1 )2 L2 2 log(3/δ). (21)
Plugging (21) into (20), we finally obtain that with probability at least 1− δ, F (Ax(S),y ∗ S)− FS(Ax(S), ŷ∗S)
≤ √√√√(4MF (Ax(S),y∗S) + 12(βµ + 1)2L2 2 + 32n(βµ + 1)2L2 2 log(3/δ)) log(3/δ) n
+ 2M log(3/δ)
3n + 50
√ 2 eL β + µ
µ dlog2 ne log(3e/δ). (22)
By the elementary inequalities √ ab ≤ ηa + 1η b and √ a+ b ≤ √ a + √ b for any a, b, η > 0, we have the following inequality with probability at least 1− δ
F (Ax(S),y ∗ S)− (1 + η)FS(Ax(S), ŷ∗S) ≤ C
1 + η
η (M n log 1 δ + (β µ + 1 ) L log2 n log 1 δ ) ,
where C is an absolute constant. The proof is complete.
A.3 PROOF OF PART (C)
We then prove the strong PD population risk bound. To begin, we introduce the following concentration inequality, which is a moment version of the Bernstein inequality. Lemma 6. (Boucheron et al., 2013) If z1, ..., zn are i.i.d., zero mean and |zi| ≤ M almost surely. Then, for any p ≥ 2, ∥∥∥ n∑
i=1
zi ∥∥∥ p ≤ 6 √√√√( n∑ i=1 Ez2i ) p+ 4pM.
Proof. Let S = {z1, ..., zn} be a set of independent random variables each taking values in Z and S′ = {z′1, ..., z′n} be its independent copy. For any i ∈ [n], define S(i) = {z1, ..., zi−1, z′i, zi+1, ..., zn} be a dataset by replacing the i-th sample in S with another i.i.d. sample z′i. Denote y ∗ S = arg maxy∈Y F (Ax(S),y), ŷ ∗ S = arg maxy∈Y FS(Ax(S),y), x ∗ S = arg minx∈X F (x, Ay(S)) and x̂∗S = arg minx∈X FS(x, Ay(S)).
The proof of Part (c) requires a pretty technical error decomposition, i.e., 4s (Ax(S), Ay(S))
=F (Ax(S),y ∗ S)− inf x′∈X F (x′, Ay(S)) =F (Ax(S),y ∗ S)− FS(Ax(S), ŷ∗S) + ES′FS(Ax(S′),y∗S′)− ESF (Ax(S),y∗S)
+ ESF (x∗S , Ay(S))− ES′FS(x∗S′ , Ay(S′)) + FS(x̂∗S , Ay(S))− inf x′∈X F (x′, Ay(S)) − ES′FS(Ax(S′),y∗S′) + ESF (Ax(S),y∗S) + ES′FS(x∗S′ , Ay(S′))− ESF (x∗S , Ay(S)) + FS(Ax(S), ŷ ∗ S)− FS(x̂∗S , Ay(S)).
Let’s first consider the term F (Ax(S),y∗S) − FS(Ax(S), ŷ∗S) + ES′FS(Ax(S′),y∗S′) − ESF (Ax(S),y∗S). It can be then decomposed into
F (Ax(S),y ∗ S)− FS(Ax(S), ŷ∗S) +
1
n n∑ i=1 Ez′i [ EZ [f(Ax(S(i)),y∗S(i) ;Z)]− f(Ax(S (i)),y∗S(i) ; zi) ]
− 1 n n∑ i=1 Ez′i [ EZ [f(Ax(S(i)),y∗S(i) ;Z)]− f(Ax(S (i)),y∗S(i) ; zi) ] + ES′FS(Ax(S′),y∗S′) − ESF (Ax(S),y∗S),
which can be bounded by the proof techniques in the proof of Part (b). According to (17), we know that
‖F (Ax(S),y∗S)− FS(Ax(S), ŷ∗S) + ES′FS(Ax(S′),y∗S′)− ESF (Ax(S),y∗S)‖p
≤50 √ 2 ( 1 + β
µ
) Lpdlog2 ne. (23)
For the second term ESF (x∗S , Ay(S)) − ES′FS(x∗S′ , Ay(S′)) + FS(x̂∗S , Ay(S)) − infx′∈X F (x
′, Ay(S)), we have the following decomposition nFS(x̂ ∗ S , Ay(S))− n inf
x′∈X F (x′, Ay(S))
=nFS(x̂ ∗ S , Ay(S))− n∑ i=1 EZ [ f(x∗S , Ay(S), Z)− Ez′i [f(x ∗ S(i) , Ay(S (i));Z)] ]
+ n∑ i=1 Ez′i [ f(x∗S(i) , Ay(S (i)); zi)− EZ [f(x∗S(i) , Ay(S (i));Z)] ] − n∑ i=1 Ez′i [ f(x∗S(i) , Ay(S (i)); zi) ] .
It is clear that n∑ i=1 Ez′i [ f(x∗S(i) , Ay(S (i)); zi) ]
= n∑ i=1 Ez′i [ f(x∗S(i) , Ay(S (i)); zi)− f(x∗S , Ay(S); zi) + f(x∗S , Ay(S); zi) ]
≥nFS(x̂∗S , Ay(S)) + n∑ i=1 Ez′i [ f(x∗S(i) , Ay(S (i)); zi)− f(x∗S , Ay(S); zi) ] . (24)
Denote gi(S) = Ez′i [ f(x∗ S(i) , Ay(S (i)); zi)− EZ [f(x∗S(i) , Ay(S (i));Z)] ] . By (24), we now get
nFS(x̂ ∗ S , Ay(S))− n inf x′∈X F (x′, Ay(S))− n∑ i=1 gi(S)
≤− n∑ i=1 EZ [ f(x∗S , Ay(S);Z)− Ez′i [f(x ∗ S(i) , Ay(S (i));Z)] ]
− n∑ i=1 Ez′i [ f(x∗S(i) , Ay(S (i)); zi)− f(x∗S , Ay(S); zi) ] .
Furthermore, according to Lemma 5, we have∣∣∣f(x∗S , Ay(S);Z)− f(x∗S(i) , Ay(S(i));Z)∣∣∣ ≤ (1 + βµ)L‖Ay(S)−Ay(S(i))‖. Similarly,∣∣∣f(x∗S(i) , Ay(S(i)); zi)− f(x∗S , Ay(S); zi)∣∣∣ ≤ (1 + βµ)L‖Ay(S)−Ay(S(i))‖. Thus, we obtain ∣∣∣nFS(x̂∗S , Ay(S))− n inf
x′∈X F (x′, Ay(S))− n∑ i=1 gi(S) ∣∣∣
≤ n∑ i=1 2 ( 1 + β µ ) L‖Ay(S(i))−Ay(S)‖ ≤ 2n ( 1 + β µ ) L , (25)
where the last inequality follows from the definition of argument stability (Part 2 of Definition 3).
Furthermore, we define hi(S) = gi(S) − ES\{zi}[gi(S)]. For hi(S), We have ES\{zi}[hi(S)] = 0 and Ezi [hi(S)] = Ezi [gi(S)] − EziES\{zi}[gi(S)] = 0 − 0 = 0. Moreover, for any j ∈ [n] with j 6= i, and z′′j ∈ Z , we get
|hi(S)− hi(z1, ..., zj−1, z′′j , zj+1, ..., zn)| ≤ 2 ( 1 + β
µ
) L ,
where this inequality follows from a similar analysis to (14) and (15) of the proof of Part (b). We thus can obtain that for any p ≥ 2, there holds
∥∥∥ n∑ i=1 hi(S) ∥∥∥ p ≤ 48 √ 2pn (β µ + 1 ) L dlog2 ne. (26)
Combined (25) with (26), we finally get the bound of the second term:∥∥∥ESF (x∗S , Ay(S))− ES′FS(x∗S′ , Ay(S′)) + FS(x̂∗S , Ay(S))− inf x′∈X F (x′, Ay(S)) ∥∥∥ p
≤ ∥∥∥FS(x̂∗S , Ay(S))− inf
x′∈X F (x′, Ay(S))−
1
n n∑ i=1 gi(S) ∥∥∥ p + ∥∥∥ 1 n n∑ i=1 hi(S) ∥∥∥ p
≤50 √ 2 ( 1 + β
µ
) Lpdlog2 ne. (27)
We then consider the third term−ES′FS(Ax(S′),y∗S′)+ESF (Ax(S),y∗S)+ES′FS(x∗S′ , Ay(S′))− ESF (x∗S , Ay(S)). It is clear that ES [ES′FS(x∗S′ , Ay(S′))] = ESF (x∗S , Ay(S)) and ES [ES′FS(Ax(S′),y∗S′)] = ESF (Ax(S),y∗S).
Moreover, we having the following important property due to the strong convexity and strong concavity of F ,
E [ (ES′f(x∗S′ , Ay(S′); zi)− ES′f(Ax(S′),y∗S′ ; zi))2 ] ≤EES′ [ L2(‖x∗S′ −Ax(S′)‖+ ‖Ay(S′)− y∗S′‖)2
] ≤2L2EES′ [‖x∗S′ −Ax(S′)‖2 + ‖Ay(S′)− y∗S′‖2] ≤4L2µ−1EES′ [F (Ax(S′),y∗S′)− F (x∗S′ , Ax(S′))] =4L2µ−1ES′ [F (Ax(S′),y∗S′)− F (x∗S′ , Ax(S′))], (28)
where the first inequality follows from Jensen’s inequality and the Lipschitz continuity of f (Assumption 1), the second inequality follows from that (a+ b)2 ≤ 2a2 + 2b2 and the third inequality follows from the property of strong convexity and strong concavity of F and the optimality condition, derived as follows,
F (Ax(S ′),y∗S′)− F (x∗S′ , Ax(S′))
=F (Ax(S ′),y∗S′)− F (x∗S′ ,y∗S′) + F (x∗S′ ,y∗S′)− F (x∗S′ , Ax(S′)) ≥µ 2 [ ‖Ax(S′)− x∗S′‖2 + ‖y∗S′ −Ax(S′)‖ ] .
It is clear that E[(Z − EZ)2] ≤ E[Z2]. Therefore, by the variance bound in (28) and applying the moment Bernstein inequality in Lemma 6 to the sum of independent random variables −ES′f(Ax(S′),y∗S′ ; zi)+ES′f(x∗S′ , Ay(S′); zi)+ESF (Ax(S),y∗S)−ESF (x∗S , Ay(S)), we have the following inequality for all p ≥ 2, ∥∥∥ 1 n n∑ i=1 −ES′f(Ax(S′),y∗S′ ; zi) + ES′f(x∗S′ , Ay(S′); zi) + ESF (Ax(S),y∗S)− ESF (x∗S , Ay(S)) ∥∥∥ p
≤ 6 √ ES′ [F (Ax(S′),y∗S′)− F (x∗S′ , Ax(S′))] 4L2p
nµ +
16pM
n .
From Definition 1, we know that the last term FS(Ax(S), ŷ∗S) − FS(x̂∗S , Ay(S)) is actually the strong PD empirical risk4sS(Ax(S), Ay(S)).
Based on the above analysis, we have derived that for each p ≥ 2,∥∥∥F (Ax(S),y∗S)− inf x′∈X F (x′, Ay(S))−4sS(Ax(S), Ay(S)) ∥∥∥ p
≤12 √ ES′ [F (Ax(S′),y∗S′)− F (x∗S′ , Ax(S′))] pL2
nµ +
16pM
n + 100
√ 2 ( 1 + β
µ
) Lpdlog2 ne
≤ η 1 + η ES′ [F (Ax(S′),y∗S′)− F (x∗S′ , Ax(S′))] + 1 + η η
12pL2
nµ +
16pM
n
+ 100 √ 2 ( 1 + β
µ
) Lpdlog2 ne, (29)
where the last inequality holds since for any a, b, η > 0, √ ab ≤ ηa+ bη .
Taking p = 2 and using the Cauchy-Schwartz inequality, we obtain that ES [ F (Ax(S),y ∗ S)− inf
x′∈X F (x′, Ay(S))−4sS(Ax(S), Ay(S)) ] ≤‖F (Ax(S),y∗S)− inf
x′∈X F (x′, Ay(S))−4sS(Ax(S), Ay(S))‖2
≤ η 1 + η ES′ [F (Ax(S′),y∗S′)− F (x∗S′ , Ax(S′))] + 1 + η η
24L2
nµ +
32M
n
+ 200 √ 2 ( 1 + β
µ
) Ldlog2 ne.
Since ES′ [F (Ax(S′),y∗S′) − F (x∗S′ , Ax(S′))] = ES [F (Ax(S),y∗S) − F (x∗S , Ax(S))], we finally get
ES [F (Ax(S),y∗S)− inf x′∈X F (x′, Ay(S))]
≤(1 + η) ( ES 4sS (Ax(S), Ay(S)) + 24L2(1 + η)
nµη +
32M
n + 200
√ 2 ( 1 + β
µ
) Ldlog2 ne ) .
Plugging this inequality into (29), we thus have that for each p ≥ 2,∥∥∥F (Ax(S),y∗S)− inf x′∈X F (x′, Ay(S))−4sS(Ax(S), Ay(S)) ∥∥∥ p
≤η ( ES 4sS (Ax(S), Ay(S)) + 24L2(1 + η)
nµη +
32M
n + 200
√ 2 ( 1 + β
µ
) Ldlog2 ne ) + 12pL2(1 + η)
nµη +
16pM
n + 100
√ 2 ( 1 + β
µ
) Lpdlog2 ne.
According to Lemma 1, for any δ > 0, with probability at least 1− δ, there holds that F (Ax(S),y ∗ S)− inf
x′∈X F (x′, Ay(S)) ≤ 4sS(Ax(S), Ay(S)) + ηES 4sS (Ax(S), Ay(S))
+ C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) L log2 n ) log (1 δ ) , (30)
where C > 0 is an absolute constant. The proof is complete.
A.4 PROOF OF PART (D)
We now prove the strong PD generalization error bound.
Proof. From (30) in the proof of Part (c), we know that for any δ > 0, with probability at least 1−δ, there holds that
4s (Ax(S), Ay(S))−4sS(Ax(S), Ay(S)) =F (Ax(S),y ∗ S)− inf
x′∈X F (x′, Ay(S))−4sS(Ax(S), Ay(S))
≤ηES 4sS (Ax(S), Ay(S)) + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) L log2 n ) log (1 δ ) .
Therefore, the proof is complete.
A.5 PROOF OF PART (E)
We finally prove the excess primal population risk bound.
Proof. Denote x∗ = arg minx∈X R(x) and y∗S = arg maxy∈Y F (Ax(S),y). Firstly, we have the following decomposition
R(Ax(S))− inf x′∈X R(x′) = R(Ax(S))−RS(Ax(S)) +RS(Ax(S))− FS(x∗, Ay(S))
+ FS(x ∗, Ay(S))− F (x∗, Ay(S)) + F (x∗, Ay(S))−R(x∗). (31)
Consider the first term R(Ax(S)) − RS(Ax(S)). From (22) of the Part (b), we know that with probability at least 1− δ,
R(Ax(S))−RS(Ax(S)) ≤ 2M log(3/δ) 3n + 50 √ 2 eL β + µ µ dlog2 ne log(3e/δ)
+ √√√√(4MF (Ax(S),y∗S) + 12(βµ + 1)2L2 2 + 32n(βµ + 1)2L2 2 log(3/δ)) log(3/δ) n .
For the second term RS(Ax(S)) − FS(x∗, Ay(S)), we have RS(Ax(S)) − FS(x∗, Ay(S)) ≤ RS(Ax(S))− infx′∈Y FS(x′, Ay(S)) = 4sS(Ax(S), Ay(S)). Note that under Assumption 1, the argument stability implies the uniform stability. Therefore, for the third term FS(x∗, Ay(S))−F (x∗, Ay(S)), from (10) of Part (a), we know that with probability at least 1− δ
FS(x ∗, Ay(S))− F (x∗, Ay(S)) ≤
2M log(3/δ) 3n + 50 √ 2e dlog2 ne log(3e/δ)
+
√ (4MF (x∗, Ay(S)) + 1 2 2 + 32n 2 log(3/δ)) log(3/δ)
n .

heading: It is clear that F (x∗, Ay(S))−R(x∗) ≤ 0.
text: Since F (x∗, Ay(S)) ≤ supy′∈Y F (x∗,y′) = R(x∗) = infx′∈X R(x), based on the above results, we have the following inequality with probability at least 1− 2δ
R(Ax(S))− inf x′∈X R(x)
≤ √√√√(4MF (Ax(S),y∗S) + 12(βµ + 1)2L2 2 + 32n(βµ + 1)2L2 2 log(3/δ)) log(3/δ) n
+ 4M log(3/δ)
3n +
√ (4M infx′∈X R(x) + 1 2 2 + 32n 2 log(3/δ)) log(3/δ)
n
+ 50 √ 2 eL β + µ
µ dlog2 ne log(3e/δ) +4sS(Ax(S), Ay(S)) + 50
√ 2e dlog2 ne log(3e/δ)
≤ √√√√( 12(βµ + 1)2L2 2 + 32n(βµ + 1)2L2 2 log(3/δ)) log(3/δ) n + η 1 + η F (Ax(S),y ∗ S)
+ 1 + η
η
4M log(3/δ)
n +
4M log(3/δ)
3n +
√ ( 12 2 + 32n 2 log(3/δ)) log(3/δ)
n
+ η
1 + η inf x′∈X R(x) +
1 + η
η
4M log(3/δ)
n
+ 50 √ 2 eL β + µ
µ dlog2 ne log(3e/δ) +4sS(Ax(S), Ay(S)) + 50
√ 2e dlog2 ne log(3e/δ),
where the last inequality follows from the elementary inequalities √ ab ≤ ηa + 1η b and √ a+ b ≤ √ a + √ b for any a, b > 0. Therefore, by a rearrangement, we have the following inequality with probability at least 1− δ
R(Ax(S))− (1 + 2η) inf x′∈X R(x)
≤C 1 + η η (M n log 1 δ + (β µ + 1 ) L log2 n log 1 δ +4sS(Ax(S), Ay(S)) ) ,
that is
R(Ax(S))− (1 + η) inf x′∈X R(x)
≤C 2 + η η (M n log 1 δ + (β µ + 1 ) L log2 n log 1 δ +4sS(Ax(S), Ay(S)) ) ,
where C is an absolute constant. The proof is complete.
Till here, the proof of Theorem 1 is complete.

heading: B EMPIRICAL SADDLE POINT
text: Empirical saddle point (ESP) problem refers to problem (2), which is also known as sample average approximation (SAA) (Zhang et al., 2021a). We denote (x̂∗S , ŷ ∗ S) as the ESP solution to (2), which is analogy to the ERM in stochastic optimization (Shalev-Shwartz et al., 2010). We first provide the main theorem of the ESP solution, as shown below.
Theorem 3. Assume for all z, the function (x,y) 7→ f(x,y; z) is µ-SC-SC. Suppose |f(x,y; z)| ≤ M for some M > 0 and x ∈ X ,y ∈ Y, z ∈ Z . Denote Ax(S) = x̂∗S and Ay(S) = ŷ∗S for (x̂∗S , ŷ ∗ S). Fixed any η > 0. There exists an absolute positive constant C.
(a) If Assumption 1 holds, then for any δ > 0, with probability at least 1− δ, we have
F (x̂∗S , ŷ ∗ S) ≤ (1 + η)FS(x̂∗S , ŷ∗S) + C
1 + η
η (M n log(1/δ) + 4L nµ log2 n log(1/δ) ) .
(b) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
R(x̂∗S) ≤ (1 + η)RS(x̂∗S) + C 1 + η
η (M n log 1 δ + (β µ + 1 )4L2 nµ log2 n log 1 δ ) .
(c) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
4s(x̂∗S , ŷ∗S) ≤ C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ )4L2 nµ log2 n ) log (1 δ ) .
(d) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
4s (x̂∗S , ŷ∗S)−4sS(x̂∗S , ŷ∗S) ≤C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ )4L2 nµ log2 n ) log (1 δ ) .
(e) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
R(x̂∗S) ≤ (1 + η) inf x∈X
R(x) + C 2 + η
η (M n log 1 δ + (β µ + 1 )4L2 nµ log2 n log 1 δ ) .
Proof. To prove Theorem 3, we should derive the strong PD empirical risk bound and the stability bound of (x̂∗S , ŷ ∗ S). It is easy to verify that 4sS(x̂∗S , ŷ∗S) = 0 (Zhang et al., 2021a). We then investigate the stability bound of (x̂∗S , ŷ ∗ S).
Let S = {z1, ..., zn} be a set of independent random variables each taking values in Z . For any i ∈ [n], define S(i) = {z1, ..., zi−1, z′i, zi+1, ..., zn} be a dataset by replacing the i-th sample in S with another i.i.d. sample z′i. We define FS(i) be the empirical risk on dataset S
(i) and define (x̂∗ S(i) , ŷ∗ S(i) ) be the ESP solution on dataset S(i).
Then we have
FS(x̂ ∗ S(i) , ŷ ∗ S)− FS(x̂∗S , ŷ∗S(i))
= 1
n n∑ j=1 ( f(x̂∗S(i) , ŷ ∗ S ; zj)− f(x̂∗S , ŷ∗S(i) ; zj) ) = 1
n ( n∑ j=1,j 6=i (f(x̂∗S(i) , ŷ ∗ S ; zj)− f(x̂∗S , ŷ∗S(i) ; zj)) + f(x̂ ∗ S(i) , ŷ ∗ S ; z ′ i)− f(x̂∗S , ŷ∗S(i) ; z ′ i) )
+ 1
n
( f(x̂∗S(i) , ŷ ∗ S ; zi)− f(x̂∗S , ŷ∗S(i) ; zi) ) − 1 n ( f(x̂∗S(i) , ŷ ∗ S ; z ′ i)− f(x̂∗S , ŷ∗S(i) ; z ′ i) )
=FS(i)(x̂ ∗ S(i) , ŷ ∗ S)− FS(i)(x̂∗S , ŷ∗S(i))
+ 1
n
( f(x̂∗S(i) , ŷ ∗ S ; zi)− f(x̂∗S , ŷ∗S ; zi) + f(x̂∗S , ŷ∗S ; zi)− f(x̂∗S , ŷ∗S(i) ; zi) ) − 1 n ( f(x̂∗S(i) , ŷ ∗ S ; z ′ i)− f(x̂∗S , ŷ∗S ; z′i) + f(x̂∗S , ŷ∗S ; z′i)− f(x̂∗S , ŷ∗S(i) ; z ′ i) )
≤FS(i)(x̂∗S(i) , ŷ ∗ S)− FS(i)(x̂∗S , ŷ∗S(i)) +
2L
n (‖x̂∗S(i) − x̂ ∗ S‖+ ‖ŷ∗S − ŷ∗S(i)‖)
=FS(i)(x̂ ∗ S(i) , ŷ ∗ S)− FS(i)(x̂∗S(i) , ŷ ∗ S(i)) + FS(i)(x̂ ∗ S(i) , ŷ ∗ S(i))− FS(i)(x̂ ∗ S , ŷ ∗ S(i))
+ 2L
n (‖x̂∗S(i) − x̂ ∗ S‖+ ‖ŷ∗S − ŷ∗S(i)‖)
≤− µ 2 ‖x̂∗S(i) − x̂ ∗ S‖2 − µ 2 ‖ŷ∗S − ŷ∗S(i)‖ 2 + 2L n (‖x̂∗S(i) − x̂ ∗ S‖+ ‖ŷ∗S − ŷ∗S(i)‖),
where the first inequality follows from the Lipschitz continuous assumption, and where the second inequality follows from the facts that the µ-SC-SC property of FS(i) and (x̂∗S(i) , ŷ ∗ S(i)
) is the ESP solution of FS(i) .
Similarly, according to the µ-SC-SC property of FS , we have
FS(x̂ ∗ S(i) , ŷ ∗ S)− FS(x̂∗S , ŷ∗S(i))
=FS(x̂ ∗ S(i) , ŷ ∗ S)− FS(x̂∗S , ŷ∗S) + FS(x̂∗S , ŷ∗S)− FS(x̂∗S , ŷ∗S(i)) ≥µ 2 ‖x̂∗S(i) − x̂ ∗ S‖2 + µ 2 ‖ŷ∗S − ŷ∗S(i)‖ 2 (32)
Based on the above results, we have
µ‖x̂∗S(i) − x̂ ∗ S‖2 + µ‖ŷ∗S − ŷ∗S(i)‖ 2
≤2L n (‖x̂∗S(i) − x̂ ∗ S‖+ ‖ŷ∗S − ŷ∗S(i)‖)
≤2L n
√ 2 √ ‖x̂∗
S(i) − x̂∗S‖2 + ‖ŷ∗S − ŷ∗S(i)‖2,
where the last inequality uses the Caucy-Schwartz inequality. Therefore, we have
‖x̂∗S(i) − x̂ ∗ S‖+ ‖ŷ∗S − ŷ∗S(i)‖ ≤ √
2(‖x̂∗ S(i) − x̂∗S‖2 + ‖ŷ∗S − ŷ∗S(i)‖2)
≤4L nµ . (33)
Now, plugging this stability bound into Theorem 1, we obtain generalization bounds of the ESP solution. The proof of Theorem 3 is complete.
Remark 8. When conditions in Theorem 3 hold, we obtain that (a) If Assumption 1 holds and FS(x̂ ∗ S , ŷ ∗ S) = O ( 1 n ) , then for any δ > 0, with probability at least 1 − δ, the plain generalization
error of (x̂∗S , ŷ ∗ S) is of the orderO ( log2 n n log(1/δ) ) . (b) If Assumptions 1 and 2 hold andRS(x̂∗S) =
O (
1 n
) , then for any δ > 0, with probability at least 1 − δ, the primal generalization error of
(x̂∗S , ŷ ∗ S) is of the order O ( log2 n n log(1/δ) ) . (c) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1 − δ, the strong PD population risk and the strong PD generalization error of (x̂∗S , ŷ ∗ S) are all of the order O ( log2 n n log(1/δ) ) . (d) If Assumptions 1 and 2 hold and
infx∈X R(x) = O ( 1 n ) , then for any δ > 0, with probability at least 1 − δ, the excess primal
population risk of (x̂∗S , ŷ ∗ S) is of the order O ( log2 n n log(1/δ) ) .
Remark 9. (Zhang et al., 2021a) also studies the generalization bound of the ESP solution. They provide O(1/n) order bounds for weak PD population risk and expected strong PD population risk. Their proofs also show that the expected strong PD population risk is more difficult to analyze than the former. They have to consider the fact that different x̂∗S corresponds to different y, as discussed in Remark 5. Moreover, the expectation operator in expected strong PD population risk also relaxes the difficulty of proof. Specifically, define S(i) be a dataset by replacing the i-th sample in S with another i.i.d. sample z′i and y
∗(x) = arg maxy∈Y F (x,y), there holds the following important property E [ supy∈Y F (x̂ ∗ S ,y) ] = 1n ∑n i=1 E [ F (x̂∗ S(i) ,y∗(x̂∗ S(i) )) ]
= 1 n ∑n i=1 E [ f(x̂∗ S(i) ,y∗(x̂∗ S(i) ); zi) ] because (x̂∗S ,y ∗(x̂∗S)) and (x̂ ∗ S(i) ,y∗(x̂∗ S(i)
)) are identically distributed and the independence between zi and S(i). On the contrary, when there is no expectation operator, we do not have this property and the proof is much more challenging.

heading: C GRADIENT DESCENT ASCENT
text: We need some notations to state results on GDA. Specifically, assume the initial point satisfies x1 = 0 and y1 = 0. Let {ηt} be a sequence of positive step sizes. At the t-th iteration, GDA updates
xt+1 = xt − ηt∇xFS(xt,yt), yt+1 = yt + ηt∇yFS(xt,yt). (34)
We denote the average of iterates by
x̄T = ∑T t=1 ηtxt∑T t=1 ηt and ȳT = ∑T t=1 ηtyt∑T t=1 ηt . (35)
Here, we first provide an important lemma to connect the argument stability with the strong PD empirical risk, which will also be used in the remaining applications.
Lemma 7. For any i ∈ [n], define S(i) = {z1, ..., zi−1, z′i, zi+1, ..., zn}. Let (xt,yt) be the output produced by FS on dataset S in running a minimax learning algorithm. Let (xit,y i t) be the corresponding output produced by FS(i) on dataset S(i), where FS(i) is empirical risk on dataset S(i). Suppose Assumption 1 holds. Assume for all z, the function (x,y) 7→ f(x,y; z) is µ-SC-SC. For any S(i) and S, we have
‖xit − xt‖+ ‖yit − yt‖ ≤ 4L
nµ + 4
√ 1
µ
√ 4sS(xt,yt).
Proof. Define (x̂∗ S(i) , ŷ∗ S(i) ) be the ESP solution on dataset S(i) and (x̂∗S , ŷ ∗ S) be the ESP solution on dataset S. To prove the stability bound, we consider
‖xit − xt‖+ ‖yit − yt‖ =‖xit − x̂∗S(i) + x̂ ∗ S(i) − x̂ ∗ S + x̂ ∗ S − xt‖+ ‖yit − ŷ∗S(i) + ŷ ∗ S(i) − ŷ ∗ S + ŷ ∗ S − yt‖ ≤‖xit − x̂∗S(i)‖+ ‖x̂ ∗ S(i) − x̂ ∗ S‖+ ‖x̂∗S − xt‖+ ‖yit − ŷ∗S(i)‖+ ‖ŷ ∗ S(i) − ŷ ∗ S‖+ ‖ŷ∗S − yt‖
≤4L nµ + ‖xit − x̂∗S(i)‖+ ‖x̂ ∗ S − xt‖+ ‖yit − ŷ∗S(i)‖+ ‖ŷ ∗ S − yt‖
≤4L nµ
+ √ 2 √ ‖xit − x̂∗S(i)‖2 + ‖y i t − ŷ∗S(i)‖2 + √ 2 √ ‖ŷ∗S − yt‖2 + ‖x̂∗S − xt‖2
≤4L nµ +
√ 4
µ
√ FS(i)(x i t, ŷ ∗ S(i) )− FS(i)(x̂∗S(i) ,y i t) + √ 4
µ
√ FS(xt, ŷ∗S)− FS(x̂∗S ,yt),
where the second inequality uses the result in (33), the third inequality uses the Caucy-Schwartz inequality, and the last inequality uses the strong convexity and strong concavity of FS(i) and FS and the optimality condition (please refer to (32)). As will see in the rest paper, we bound FS(i)(x i t, ŷ ∗ S(i) ) − FS(i)(x̂∗S(i) , ŷ ∗ S(i)
) and FS(xt, ŷ∗S) − FS(x̂∗S ,yt) with the same upper bound since they are all strong PD empirical risk. Thus, for brevity, we derive the following inequality
‖xit − xt‖+ ‖yit − yt‖
≤4L nµ + 4
√ 1
µ
√ FS(xt, ŷ∗S)− FS(x̂∗S ,yt)
≤4L nµ + 4
√ 1
µ
√ 4sS(xt,yt).
The proof is complete.
Remark 10. Lemma 7 provides the connection between the stability bound and the strong PD empirical risk. The subscript t here represents not only the output of an iterative optimization algorithm, but any output of the empirical risk of any minimax learning algorithm. Remark 11. In studying the stability bound of gradient-based optimization algorithms, a popular approach is to use the property of smoothness to establish the nonexpansiveness of gradient mapping, proposed in the seminal work (Hardt et al., 2016). (Farnia & Ozdaglar, 2021; Lei et al., 2021) extend this approach to the minimax problems and use it to analyze the stability bound of SGDA, GDA, PPM, etc. However, their stability bounds are often derived in expectation. In (Lei et al., 2021), the authors also use the Chernoff bounds of Bernoulli variables to establish high probability stability bounds when they are to derive high probability generalization bounds. Unfortunately, these stability bounds are often of slow orderO(1/ √ n). To obtain sharper stability bounds, we established Lemma 7.
The following lemma shows the strong PD empirical risk of GDA. Lemma 8. Suppose Assumption 1 holds and FS(·, ·) be µ-SC-SC with µ > 0. Let {xt,yt} be the sequence produced by (34) with ηt = 1µ(t+t0) . Assume t0 ≥ 0. Suppose supx∈X ‖x‖ ≤ RX and supy∈Y ‖y‖ ≤ RY . Then for (x̄T , ȳT ) in (35) we have
sup y∈Y FS(x̄T ,y)− inf x∈X
FS(x, ȳT ) ≤ µt0(R
2 X +R 2 Y ) T + L2 log(eT ) µT .
If t0 = 0, then
sup y∈Y FS(x̄T ,y)− inf x∈X
FS(x, ȳT ) ≤ L2 log(eT )
µT .
Proof. Firstly, we have
‖xt+1 − x‖2 = ‖xt − ηt∇xFS(xt,yt)− x‖2
= ‖xt − x‖2 + η2t ‖∇xFS(xt,yt)‖2 + 2ηt〈x− xt,∇xFS(xt,yt)〉 ≤ ‖xt − x‖2 + η2tL2 + 2ηt〈x− xt,∇xFS(xt,yt)〉,
where the first inequality holds because of Assumption 1. By the strong convexity of FS(·,yt), we have
2ηt(FS(xt,yt)− FS(x,yt)) ≤ (1− ηtµ)‖xt − x‖2 − ‖xt+1 − x‖2 + η2tL2. Since ηt = 1µ(t+t0) , we further get
2
µ(t+ t0) (FS(xt,yt)− FS(x,yt)) ≤
( 1− 1
(t+ t0)
) ‖xt − x‖2 − ‖xt+1 − x‖2 + ( 1 µ(t+ t0) )2 L2.
Multiplying both sides by t+ t0, we have 2
µ (FS(xt,yt)− FS(x,yt)) ≤ (t+ t0 − 1)‖xt − x‖2 − (t+ t0)‖xt+1 − x‖2 +
L2
µ2(t+ t0) . Since x1 = 0 and ∑T t=1 t
−1 ≤ log(eT ), by taking a summation of the above inequality from t = 1 to T , we obtain
T∑ t=1 (FS(xt,yt)− FS(x,yt)) ≤ µ 2 t0R 2 X + L2 log(eT ) 2µ .
From the concavity of FS(x, ·) we get T∑ t=1 (FS(xt,yt)− FS(x, ȳT )) ≤ µ 2 t0R 2 X + L2 log(eT ) 2µ .
Since this inequality holds for any x, we get T∑ t=1 (FS(xt,yt)− inf x∈X FS(x, ȳT )) ≤ µ 2 t0R 2 X + L2 log(eT ) 2µ .
This implies that
1
T T∑ t=1 (FS(xt,yt)− inf x∈X FS(x, ȳT )) ≤ µt0R 2 X 2T + L2 log(eT ) 2µT .
In a similar way, we have the following inequality
sup y∈Y
FS(x̄T ,y)− 1
T T∑ t=1 (FS(xt,yt)) ≤ µt0R 2 Y 2T + L2 log(eT ) 2µT .
Combined the above two inequalities together we get
sup y∈Y FS(x̄T ,y)− inf x∈X
FS(x, ȳT ) ≤ µt0(R
2 X +R 2 Y ) T + L2 log(eT ) µT .
For optimization algorithm GDA, substituting the strong PD empirical risk bound of (x̄T , ȳT ) into Lemma 7, we get the following stability bound,
‖x̄iT − x̄T ‖+ ‖ȳiT − ȳT ‖ ≤ 4L
nµ + 4
√ 1
µ
√ 4sS(x̄T , ȳT )
≤ 4L nµ + 4
√ 1
µ
√ µt0(R2X +R 2 Y )
T + L2 log(eT ) µT . (36)
Furthermore, for any x ∈ X , y ∈ Y and z ∈ Z , f(x,y; z)− f(0, 0; z) ≤ L‖x− 0‖+ L‖y − 0‖ ≤ L(RY +RY ),
which implies that f(x,y; z) ≤ sup
z∈Z f(0, 0; z) + L(RY +RY ). (37)
Till here, plugging (37), the stability bound in (36) and the strong PD empirical risk bound in Lemma 8 into Theorem 1, we obtain generalization bounds of GDA.
We now write the main theorem of GDA.
Theorem 4. Assume for all z, the function (x,y) 7→ f(x,y; z) is µ-SC-SC. Suppose supx∈X ‖x‖ ≤ RX and supy∈Y ‖y‖ ≤ RY . Let {xt,yt} be produced by (34) with ηt = 1µ(t+t0) . Assume t0 ≥ 0. DenoteAx(S) = x̄T andAy(S) = ȳT for (x̄T , ȳT ) in (35). LetM = supz∈Z f(0, 0; z)+L(RX+ RY ). Fixed any η > 0. There exists an absolute positive constant C.
(a) If Assumption 1 holds, then for any δ > 0, with probability at least 1− δ, we have
F (x̄T , ȳT ) ≤ (1 + η)FS(x̄T , ȳT )
+ C 1 + η
η (M n log(1/δ) + (4L nµ + 4 √ 1 µ √ µt0(R2X +R 2 Y ) T + L2 log(eT ) µT ) log2 n log(1/δ) ) .
(b) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
R(x̄T ) ≤ (1 + η)RS(x̄T ) + C 1 + η
η × (M log 1δ
n + β + µ µ L (4L nµ + 4 √ 1 µ √ µt0(R2X +R 2 Y ) T + L2 log(eT ) µT ) log2 n log 1 δ ) .
(c) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
4s (x̄T , ȳT ) ≤ (1 + η) (µt0(R2X +R2Y )
T + L2 log(eT ) µT
) + C(1 + η)
× (L2(1 + η)
nµη + M n + β + µ µ (4L nµ +4 √ 1 µ √ µt0(R2X +R 2 Y ) T + L2 log(eT ) µT ) L log2 n ) log (1 δ ) .
(d) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
4s (x̄T , ȳT )−4sS(x̄T , ȳT ) ≤ η (µt0(R2X +R2Y )
T + L2 log(eT ) µT
) + C(1 + η)
× (L2(1 + η)
nµη + M n + β + µ µ (4L nµ +4 √ 1 µ √ µt0(R2X +R 2 Y ) T + L2 log(eT ) µT ) L log2 n ) log (1 δ ) .
(e) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
R(x̄T ) ≤ (1 + η) inf x∈X
R(x) + C 2 + η
η (µt0(R2X +R2Y ) T + L2 log(eT ) µT ) +C 2 + η
η (M n log 1 δ + (β µ +1 ) L (4L nµ +4 √ 1 µ √ µt0(R2X +R 2 Y ) T + L2 log(eT ) µT ) log2 n log 1 δ ) .
Remark 12. When conditions in Theorem 4 hold, we obtain that (a) If Assumption 1 holds and FS(x̄T , ȳT ) = O ( 1 n ) , then for any δ > 0, with probability at least 1 − δ, the plain generalization
error of (x̄T , ȳT ) of GDA is of the order O (( 1 n + √ log T T ) log2 n log(1/δ) ) . (b) If Assumptions
1 and 2 hold and RS(x̄T ) = O ( 1 n ) , then for any δ > 0, with probability at least 1 − δ, the primal
generalization error of (x̄T , ȳT ) of GDA is of the order O (( 1 n + √ log T T ) log2 n log(1/δ) ) . (c) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1 − δ, the strong PD population risk and the strong PD generalization error of (x̄T , ȳT ) of GDA are all of the order
O ((
1 n + √ log T T ) log2 n log(1/δ) ) . (d) If Assumptions 1 and 2 hold and infx∈X R(x) = O ( 1 n ) ,
then for any δ > 0, with probability at least 1 − δ, the excess primal population risk of (x̄T , ȳT ) of GDA is of the order O (( 1 n + √ log T T ) log2 n log(1/δ) ) . For the above bounds, we can take
T = O(n2) gradient evaluations to get bound of the order O (
log3/2 n n log(1/δ)
) .

heading: D STOCHASTIC GRADIENT DESCENT ASCENT
text: We need some notations to state results on SGDA. Specifically, assume the initial point satisfies x1 = 0 and y1 = 0. Let {ηt} be a sequence of positive step sizes. At the t-th iteration, SGDA first randomly select an index it form the uniform distribution over [n] := {1, ..., n} and then do the update
xt+1 = xt − ηt∇xf(xt,yt, zit), yt+1 = yt + ηt∇yf(xt,yt, zit). (38)
We denote the average of iterates by
x̄T = ∑T t=1 ηtxt∑T t=1 ηt and ȳT = ∑T t=1 ηtyt∑T t=1 ηt . (39)
Let’s first introduce two concentration inequalities for martingales, which are required in deriving the strong PD empirical risk bound of SGDA. Lemma 9. (Boucheron et al., 2013) Let z1, ..., zn be a sequence of random variables such that zk may depend the previous variables z1, ..., zk−1 for all k = 1, ..., n. Consider a sequence of functionals ξk(z1, ..., zk), k = 1, ..., n. Assume |ξk − Ezk [ξk]| ≤ bk for each k. Let δ ∈ (0, 1). With probability at least 1− δ
n∑ k=1 ξk − n∑ k=1 Ezk [ξk] ≤ ( 2 n∑ k=1 b2k log 1 δ ) 1 2 .
Lemma 10. (Tarres & Yao, 2014) Let {ξk}k∈N be a martingale difference sequence in Rd. Suppose that almost surely ‖ξk‖ ≤ D and ∑t k=1 E[‖ξk‖2|ξ1, ..., ξk−1] ≤ σ2t . Then, for any 0 < δ < 1, the following inequality holds with probability at least 1− δ
max 1≤j≤t ∥∥∥ j∑ k=1 ξk ∥∥∥ ≤ 2(D 3 + σt ) log 2 δ .
The following lemma shows the strong PD empirical risk bound of SGDA. Lemma 11. Suppose Assumption 1 holds and FS(·, ·) be µ-SC-SC with µ > 0. Let {xt,yt} be the sequence produced by (38) with ηt = 1µ(t+t0) . Assume t0 ≥ 0. Suppose supx∈X ‖x‖ ≤ RX and supy∈Y ‖y‖ ≤ RY . Let δ > 0. Then for (x̄T , ȳT ) in (39), with probability at least 1− δ we have
sup y∈Y FS(x̄T ,y)− inf x∈X
FS(x, ȳT )) ≤ 2µt0(R
2 X +R 2 Y ) T + L2 log(eT ) µT
+ 2(RX +RY )
T
(2L 3 + 2L √ T ) log 6 δ + 2L(RX +RY )(2T log(6/δ)) 1 2 T .
If t0 = 0, then with probability at least 1− δ we have
sup y∈Y FS(x̄T ,y)− inf x∈X
FS(x, ȳT )) ≤ L2 log(eT )
µT +
2(RX +RY )
T
(2L 3 + 2L √ T ) log 6 δ
+ 2L(RX +RY )(2T log(6/δ))
1 2
T .
Proof. By a similar analysis to the proof of Lemma 8, we have ‖xt+1 − x‖2 = ‖xt − ηt∇xf(xt,yt; zit)− x‖2
= ‖xt − x‖2 + η2t ‖∇xf(xt,yt; zit)‖2 + 2ηt〈x− xt,∇xf(xt,yt; zit)〉 ≤ ‖xt − x‖2 + η2tL2 + 2ηt〈x− xt,∇xf(xt,yt; zit)−∇xFS(xt,yt)〉+ 2ηt〈x− xt,∇xFS(xt,yt)〉,
where the first inequality holds because of Assumption 1. By the strong convexity of FS(·,yt), we have
2ηt(FS(xt,yt)− FS(x,yt)) ≤ (1− ηtµ)‖xt − x‖2 − ‖xt+1 − x‖2 + η2tL2
+2ηt〈x− xt,∇xf(xt,yt; zit)−∇xFS(xt,yt)〉.
Since ηt = 1µ(t+t0) , we further get
2
µ(t+ t0) (FS(xt,yt)− FS(x,yt)) ≤
( 1− 1
(t+ t0)
) ‖xt − x‖2 − ‖xt+1 − x‖2
+ ( 1 µ(t+ t0) )2 L2 +
2
µ(t+ t0) 〈x− xt,∇xf(xt,yt; zit)−∇xFS(xt,yt)〉.
Multiplying both sides by t+ t0, we have
2 µ (FS(xt,yt)− FS(x,yt)) ≤ (t+ t0 − 1)‖xt − x‖2 − (t+ t0)‖xt+1 − x‖2 +
L2
µ2(t+ t0)
+ 2
µ 〈x− xt,∇xf(xt,yt; zit)−∇xFS(xt,yt)〉.
Since x1 = 0 and ∑T t=1 t
−1 ≤ log(eT ), by taking a summation of the above inequality from t = 1 to T , we obtain
T∑ t=1 (FS(xt,yt)− FS(x,yt)) ≤ µ 2 t0R 2 X + L2 log(eT ) 2µ
+ T∑ t=1 〈x,∇xf(xt,yt; zit)−∇xFS(xt,yt)〉+ T∑ t=1 〈xt,∇xFS(xt,yt)−∇xf(xt,yt; zit)〉.
From the concavity of FS(x, ·) we get T∑ t=1 (FS(xt,yt)− FS(x, ȳT )) ≤ µ 2 t0R 2 X + L2 log(eT ) 2µ
+ T∑ t=1 〈x,∇xf(xt,yt; zit)−∇xFS(xt,yt)〉+ T∑ t=1 〈xt,∇xFS(xt,yt)−∇xf(xt,yt; zit)〉.
Since this inequality holds for any x, we get T∑ t=1 (FS(xt,yt)− inf x∈X FS(x, ȳT )) ≤ µ 2 t0R 2 X + L2 log(eT ) 2µ
+ T∑ t=1 sup x∈X 〈x,∇xf(xt,yt; zit)−∇xFS(xt,yt)〉+ T∑ t=1 〈xt,∇xFS(xt,yt)−∇xf(xt,yt; zit)〉.
By Schwartz’s inequality, we have T∑ t=1 (FS(xt,yt)− inf x∈X FS(x, ȳT )) ≤ µ 2 t0R 2 X + L2 log(eT ) 2µ
+RX ∥∥∥ T∑ t=1 ∇xf(xt,yt; zit)−∇xFS(xt,yt) ∥∥∥+ T∑ t=1 〈xt,∇xFS(xt,yt)−∇xf(xt,yt; zit)〉.
Denote ξt = 〈xt,∇xFS(xt,yt) − ∇xf(xt,yt; zit)〉. Since Eit [〈xt,∇xFS(xt,yt) − ∇xf(xt,yt; zit)〉] = 0, so {ξt|t = 1, ..., T} is a martingale difference sequence. By Schwartz’s inequality and Assumption 1, we know that |〈xt,∇xFS(xt,yt) − ∇xf(xt,yt; zit)〉| ≤ 2LRX . Then, according to Lemma 9, we have the following inequality with probability at least 1− δ/6
T∑ t=1 〈xt,∇xFS(xt,yt)−∇xf(xt,yt; zit)〉 ≤ 2LRX(2T log(6/δ)) 1 2 .
Define ξ′t = ∇xf(xt,yt; zit)−∇xFS(xt,yt). Then we get ‖ξ′t‖ ≤ 2L and T∑ t=1 E[‖ξ′t‖2|ξ′1, ..., ξ′t−1] ≤ 4TL2.
Applying Lemma 10 to the martingale difference sequence {ξ′t}, we have the following inequality with probability at least 1− δ/3∥∥∥ T∑
t=1
ξ′t ∥∥∥ ≤ 2(2L 3 + 2L √ T ) log 6 δ .
That is, with probability at least 1− δ/3∥∥∥ T∑ t=1 ∇xf(xt,yt; zit)−∇xFS(xt,yt) ∥∥∥ ≤ 2(2L 3 + 2L √ T ) log 6 δ .
Combined with the above results, we finally have the following inequality with probability at least 1− δ/2
1
T T∑ t=1 (FS(xt,yt)− inf x∈X FS(x, ȳT )) ≤ µt0R 2 X 2T + L2 log(eT ) 2µT
+ 2RX T (2L 3 + 2L √ T ) log 6 δ + 2LRX(2T log(6/δ)) 1 2 T .
In a similar way, we have the following inequality with probability at least 1− δ/2
sup y∈Y
FS(x̄T ,y)− 1
T T∑ t=1 (FS(xt,yt)) ≤ µt0R 2 Y 2T + L2 log(eT ) 2µT
+ 2RY T (2L 3 + 2L √ T ) log 6 δ + 2LRY (2T log(6/δ)) 1 2 T .
Combined the above two inequalities together we get the result with probability at least 1− δ
sup y∈Y FS(x̄T ,y)− inf x∈X
FS(x, ȳT )) ≤ µt0(R
2 X +R 2 Y ) T + L2 log(eT ) µT
+ 2(RX +RY )
T
(2L 3 + 2L √ T ) log 6 δ + 2L(RX +RY )(2T log(6/δ)) 1 2 T .
Denote E = µt0(R 2 X+R 2 Y ) T + L2 log(eT ) µT + 2(RX+RY )( 2L 3 +2L
√ T ) log 6δ
T + 2L(RX+RY )(2T log(6/δ))
1 2
T . Now, plugging Lemma 11 to Lemma 7, we know that the argument stability bound of SGDA is
‖x̄iT − x̄T ‖+ ‖ȳiT − ȳT ‖ ≤ 4L
nµ + 4
√ 1
µ
√ 4sS(x̄T , ȳT ) ≤ 4 √ 1
µ
√ E + 4L
nµ . (40)
Furthermore, for any x ∈ X , y ∈ Y and z ∈ Z , f(x,y; z) ≤ f(0, 0; z) + L‖x− 0‖+ L‖y − 0‖ ≤ sup
z∈Z f(0, 0; z) + L(RX +RY ), (41)
Note that since SGDA is a randomized algorithm, thus we need the following variant of Theorem 1. Theorem 5. Let A be a randomized learning algorithm and > 0. Suppose |f(x,y; z)| ≤ M for some M > 0 and x ∈ X ,y ∈ Y, z ∈ Z . Fixed any η > 0. There exists an absolute positive constant C.
(a.) If A has -uniform stability with probability at least 1 − δ′ for some δ′ ∈ (0, 1) over the randomness of A, i.e.,
PrA ( sup z [f(Ax(S), Ay(S); z)− f(Ax(S′), Ay(S′); z)] ) ≤ ,
And if the randomness ofA is independent of the training set S. Then for any δ > 0, with probability at least 1− δ′ − δ,
F (Ax(S), Ay(S)) ≤ (1 + η)FS(Ax(S), Ay(S)) + C 1 + η
η (M n log(1/δ) + log2 n log 1 δ ) .
(b.) Assume that for all x, the function y 7→ F (x,y) is µ-strongly-concave. Suppose Assumptions 1 and 2 hold. If the algorithm A is -argument stable with probability at least 1 − δ′ for some δ′ ∈ (0, 1) over the randomness of A, i.e.,
PrA ( ‖Ax(S)−Ax(S′)‖+ ‖Ay(S)−Ay(S′)‖ ) ≤ .
And if the randomness ofA is independent of the training set S. Then for any δ > 0, with probability at least 1− δ′ − δ,
R(Ax(S)) ≤ (1 + η)RS(Ax(S)) + C 1 + η
η (M n log 1 δ + (β µ + 1 ) L log2 n log 1 δ ) .
(c.) Assume that for all x and y, the function F (x,y) is µ-SC-SC. Suppose Assumptions 1 and 2 hold. If the algorithm A is -argument stable with probability at least 1 − δ′ for some δ′ ∈ (0, 1) over the randomness of A, i.e.,
PrA ( ‖Ax(S)−Ax(S′)‖+ ‖Ay(S)−Ay(S′)‖ ) ≤ .
And if the randomness ofA is independent of the training set S. Then for any δ > 0, with probability at least 1− δ′ − δ,
4s (Ax(S), Ay(S)) ≤ 4sS(Ax(S), Ay(S)) + ηES 4sS (Ax(S), Ay(S)) + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) L log2 n ) log (1 δ ) .
(d.) Assume that for all x and y, the function F (x,y) is µ-SC-SC. Suppose Assumptions 1 and 2 hold. If the algorithm A is -argument stable with probability at least 1 − δ′ for some δ′ ∈ (0, 1) over the randomness of A, i.e.,
PrA ( ‖Ax(S)−Ax(S′)‖+ ‖Ay(S)−Ay(S′)‖ ) ≤ .
And if the randomness ofA is independent of the training set S. Then for any δ > 0, with probability at least 1− δ′ − δ,
4s (Ax(S), Ay(S))−4sS(Ax(S), Ay(S)) ≤ ηES 4sS (Ax(S), Ay(S)) + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) L log2 n ) log (1 δ ) .
(e.) Assume that for all x, the function y 7→ F (x,y) is µ-strongly-concave. Suppose Assumptions 1 and 2 hold. If the algorithm A is -argument stable with probability at least 1 − δ′ for some δ′ ∈ (0, 1) over the randomness of A, i.e.,
PrA ( ‖Ax(S)−Ax(S′)‖+ ‖Ay(S)−Ay(S′)‖ ) ≤ .
And if the randomness ofA is independent of the training set S. Then for any δ > 0, with probability at least 1− δ′ − δ,
R(Ax(S)) ≤ (1 + η) inf x∈X R(x)
+ C 2 + η
η (M n log 1 δ + (β µ + 1 ) L log2 n log 1 δ +4sS(Ax(S), Ay(S)) ) .
Therefore, plugging (41), the stability bound in (40) and the strong PD empirical risk bound in Lemma 11 into Theorem 5, we obtain generalization bounds of SGDA. Now, we write the main theorem of SGDA as follows. Theorem 6. Assume for all z, the function (x,y) 7→ f(x,y; z) is µ-SC-SC. Suppose supx∈X ‖x‖ ≤ RX and supy∈Y ‖y‖ ≤ RY . Let {xt,yt} be produced by (38) with ηt = 1/(µ(t + t0)). Assume t0 ≥ 0. Denote Ax(S) = x̄T and Ay(S) = ȳT for (x̄T , ȳT ) in (39). Fixed any η > 0. Let
M = supz∈Z f(0, 0; z) + L(RX + RY ). Let E = µt0(R
2 X+R 2 Y ) T + L2 log(eT ) µT + 2(RX+RY ) T ( 2L 3 +
2L √ T )
log 6δ+ 2L(RX+RY )(2T log(6/δ))
1 2
T andB = 4L nµ+4 √ 1 µ √ E. There exists an absolute positive
constant C.
(a) If Assumption 1 holds, then for any δ > 0, with probability at least 1− 2δ, we have
F (x̄T , ȳT ) ≤ (1 + η)FS(x̄T , ȳT ) + C 1 + η
η (M n log(1/δ) +B log2 n log(1/δ) ) .
(b) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− 2δ, we have
R(x̄T ) ≤ (1 + η)RS(x̄T ) + C 1 + η
η (M n log 1 δ + (β µ + 1 ) LB log2 n log 1 δ ) .
(c) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− 2δ, we have
4s(x̄T , ȳT ) ≤ (1 + η)E + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) BL log2 n ) log (1 δ ) .
(d) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− 2δ, we have
4s (x̄T , ȳT )−4sS(x̄T , ȳT ) ≤ ηE + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) BL log2 n ) log (1 δ ) .
(e) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− 2δ, we have
R(x̄T ) ≤ (1 + η) inf x∈X
R(x) + C 2 + η
η (M n log 1 δ + (β µ + 1 ) LB log2 n log 1 δ + E ) .
Remark 13. When conditions in Theorem 6 hold, we obtain that (a) If Assumption 1 holds and FS(x̄T , ȳT ) = O ( 1 n ) , then for any δ > 0, with probability at least 1 − δ, the plain gen-
eralization error of (x̄T , ȳT ) of SGDA is of the order O (( 1 n + √ log(1/δ)
T 1 2
) log2 n log(1/δ) ) .
(b) If Assumptions 1 and 2 hold and RS(x̄T ) = O ( 1 n ) , then for any δ > 0, with probability at least 1 − δ, the primal generalization error of (x̄T , ȳT ) of SGDA is of the order O ((
1 n +
√ log(1/δ)
T 1 2
) log2 n log(1/δ) ) . (c) If Assumptions 1 and 2 hold, then for any δ > 0,
with probability at least 1 − δ, the strong PD population risk and strong PD generalization error of (x̄T , ȳT ) of SGDA are all of the orderO (( 1 n + √ log(1/δ)
T 1 2
) log2 n log(1/δ) ) . (d) If Assumptions 1
and 2 hold and infx∈X R(x) = O ( 1 n ) , then for any δ > 0, with probability at least 1−δ, the excess
primal population risk of (x̄T , ȳT ) of SGDA is of the orderO (( 1 n + √ log(1/δ)
T 1 2
) log2 n log(1/δ) ) .
For the above bounds, we can take T = O(n4) stochastic gradient evaluations to get bound of the order O ( logn n log 3 2 (1/δ) ) .

heading: E PROXIMAL POINT METHOD
text: One of the classical algorithms studied for solving the minimax problem is the Proximal Point method (Rockafellar, 1976). We denote the t-th iterate of PPM as (xt,yt). The averaged iterate is defined as
x̄T = 1
T T∑ t=1 xt and ȳT = 1 T T∑ t=1 yt. (42)
Given stepsize parameter ν, the PPM generates the iterate {xt+1,yt+1} by
arg min x∈X arg max y∈Y
{ FS(x,y) + 1
2ν ‖x− xt‖ −
1
2ν ‖y − yt‖
} . (43)
{xt+1,yt+1} is the unique solution since the objective function of problem (43) is strongly convex in x and strongly concave in y. From the discussion in (Mokhtari et al., 2019), the update of PPM can be written as
xt+1 = xt − ν∇xFS(xt+1,yt+1), yt+1 = yt + ν∇yFS(xt+1,yt+1), (44)
Assume that the initial point satisfies x0 = 0 and y0 = 0.
We now begin to prove the strong PD empirical risk. Firstly, two lemmas are introduced. Lemma 12. (Nemirovski, 2005) Define vector v = [x,y] ∈ R2d and the operator P : R2d 7→ R2d as
P (v) = [∇xFS(x,y);−∇yFS(x,y)]. (45)
Consider (x̄T , ȳT ) in (42). Suppose the ESP solution exists. Assume the function FS(x,y) is continuously differentiable in x and y. Assume that FS(x,y) is a convex function of x for any y and is a concave function of y for any x. Then for any v = [x,y] ∈ R2d, we have
FS(x̄T ,y)− FS(x, ȳT ) ≤ 1
T T∑ t=1 P (vt) T (vt − v).
Lemma 13. (Mokhtari et al., 2019) Consider the sequence of iterates {vt} ∈ R2d generated by the following update
vt+1 = vt − νP (vt+1),
where P is a monotone and Lipschitz continuous operator, and ν is a positive constant. Then for any v ∈ R2d and for each t ≥ 1 we have
P (vt+1) T (vt+1 − v) =
1
2ν ‖vt − v‖2 −
1
2ν ‖vt+1 − v‖2 −
1
2ν ‖vt+1 − vt‖2.
The following lemma is the strong PD empirical risk bound of PPM. Lemma 14. Let {xt,yt} be the iterates generated by PPM in (44). Assume ν is a positive constant. Suppose the ESP solution exists. Assume that FS(x,y) is a convex function of x for any y and is a concave function of y for any x. Suppose supx∈X ‖x‖ ≤ RX and supy∈Y ‖y‖ ≤ RY . If Assumption 2 holds, then for all T ≥ 1, we have
sup y∈Y FS(x̄T ,y)− inf x∈X
FS(x, ȳT ) ≤ R2X +R 2 Y
2νT .
Proof. The update of the PPM in (44) can be written as
vt+1 = vt − νP (vt+1).
According to Lemma 1 in (Mokhtari et al., 2019), if FS(x,y) is convex-concave and Assumption 2 holds, then P (v) defined in (45) is monotone and Lipschitz continuous. According to Lemma 13, we have
P (vt+1) T (vt+1 − v) =
1
2ν ‖vt − v‖2 −
1
2ν ‖vt+1 − v‖2 −
1
2ν ‖vt+1 − vt‖2.
Taking a summation of the above inequality from t = 0 to T − 1, we obtain T−1∑ t=0 P (vt+1) T (vt+1 − v) ≤ 1 2ν ‖v0 − v‖2 − 1 2ν ‖vT − v‖2. (46)
According to (46), we know that T−1∑ t=0 P (vt+1) T (vt+1 − v) ≤ 1 2ν ‖v0 − v‖2
= ‖x0 − x‖2 + ‖y0 − y‖2
2ν .
Combined this result with Lemma 12, we can write
FS(x̄T ,y)− FS(x, ȳT ) ≤ ‖x0 − x‖2 + ‖y0 − y‖2
2νT ,
which implies that
sup y∈Y FS(x̄T ,y)− inf x∈X
FS(x, ȳT ) ≤ R2X +R 2 Y
2νT .
The proof is complete.
Combined Lemma 7 and Lemma 14, we know that the argument stability bound of PPM is
‖x̄iT − x̄T ‖+ ‖ȳiT − ȳT ‖ ≤ 4L
nµ + 4
√ 1
µ
√ 4sS(x̄T , ȳT )
≤ 4L nµ + 4
√ 1
µ
√ R2X +R 2 Y
2νT . (47)
Furthermore, for any x ∈ X , y ∈ Y and z ∈ Z , f(x,y; z) ≤ f(0, 0; z) + L‖x− 0‖+ L‖y − 0‖ ≤ sup
z∈Z f(0, 0; z) + L(RX +RY ), (48)
Therefore, plugging (48), the stability bound in (47) and the strong PD empirical risk bound in Lemma 14 into Theorem 1, we obtain generalization bounds of PPM, shown as below. Theorem 7. Assume for all z, the function (x,y) 7→ f(x,y; z) is µ-SC-SC. Suppose supx∈X ‖x‖ ≤ RX and supy∈Y ‖y‖ ≤ RY . Let {xt,yt} be produced by (44). Assume ν is a positive constant. Denote Ax(S) = x̄T and Ay(S) = ȳT for (x̄T , ȳT ) in (42). Fixed any η > 0. Let M = supz∈Z f(0, 0; z) + L(RX +RY ). Let E = R2X+R 2 Y 2νT and B = 4L nµ + 4 √ 1 µ √ E. There exists an absolute positive constant C.
(a) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
F (x̄T , ȳT ) ≤ (1 + η)FS(x̄T , ȳT ) + C 1 + η
η (M n log(1/δ) +B log2 n log(1/δ) ) .
(b) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
R(x̄T ) ≤ (1 + η)RS(x̄T ) + C 1 + η
η (M n log 1 δ + (β µ + 1 ) LB log2 n log 1 δ ) .
(c) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have 4s(x̄T , ȳT ) ≤ (1 + η)E + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) BL log2 n ) log (1 δ ) .
(d) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
4s (x̄T , ȳT )−4sS(x̄T , ȳT ) ≤ ηE + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) BL log2 n ) log (1 δ ) .
(e) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
R(x̄T )− (1 + η) inf x∈X R(x) ≤ C 2 + η η (M n log 1 δ + (β µ + 1 ) LB log2 n log 1 δ + E ) .
Remark 14. When conditions in Theorem 7 hold, we obtain that (a) If Assumption 1 and 2 hold and FS(x̄T , ȳT ) = O ( 1 n ) , then for any δ > 0, with probability at least 1 − δ, the plain generalization
error of (x̄T , ȳT ) of PPM is of the order O (( 1 n + √ 1 T ) log2 n log(1/δ) ) . (b) If Assumptions
1 and 2 hold and RS(x̄T ) = O ( 1 n ) , then for any δ > 0, with probability at least 1 − δ, the
primal generalization error of (x̄T , ȳT ) of PPM is of the order O (( 1 n + √ 1 T ) log2 n log(1/δ) ) . (c) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1 − δ, the strong PD population risk and strong PD generalization error of (x̄T , ȳT ) of PPM are all of the order
O ((
1 n + √ 1 T ) log2 n log(1/δ) ) . (d) If Assumptions 1 and 2 hold and infx∈X R(x) = O ( 1 n ) ,
then for any δ > 0, with probability at least 1− δ, the excess primal population risk of (x̄T , ȳT ) of PPM is of the orderO (( 1 n+ √ 1 T ) log2 n log(1/δ) ) . For the above bounds, we can take T = O(n2)
gradient evaluations to get bound of the order O (
logn n log(1/δ)
) .

heading: F EXTRAGRADIENT METHOD
text: EG is a classical algorithm for solving minimax problems introduced by (Korpelevich, 1976). We now introduce some notations. Followed (Mokhtari et al., 2019), we consider the following update of EG: given stepsize parameter ν, we first compute a set of mid-point iterates {xt+ 12 ,yt+ 12 }
xt+ 12 = xt − ν∇xFS(xt,yt), yt+ 12 = yt + ν∇yFS(xt,yt), (49)
we then compute the next iterates {xt+1,yt+1}
xt+1 = xt − ν∇xFS(xt+ 12 ,yt+ 12 ), yt+1 = yt + ν∇yFS(xt+ 12 ,yt+ 12 ). (50)
Consider the averaged iterate
x̄T = 1
T T∑ t=1 xt and ȳT = 1 T T∑ t=1 yt. (51)
Assume that the initial point satisfies x0 = x−1/2 and y0 = y−1/2.
We now show the strong PD empirical risk bound for (x̄T , ȳT ) of EG.
Lemma 15. (Mokhtari et al., 2019) Let {xt,yt}, {xt+1/2,yt+1/2} be the iterates generated by the EG updates in (49) and (50). Assume that the initial point satisfies x0 = x−1/2 and y0 = y−1/2. Suppose the ESP solution (x̂∗, ŷ∗) exists. Assume that FS(x,y) is a convex function of x for any y and is a concave function of y for any x. If Assumption 2 holds and the stepsize ν satisfies the condition ν = c2β for any c ∈ (0, 1), then:
(a) the iterates {xt,yt}, {xt+1/2,yt+1/2} stay within the compact convex set
D := { (x,y)|‖x− x̂∗‖2 + ‖y − ŷ∗‖2 ≤ ( 2 +
2 1− 4ν2β2 ) (‖x0 − x̂∗‖2 + ‖y0 − ŷ∗‖2) } .
(52)
(b) for all T ≥ 1, we have
sup y:(x̄T ,y)∈D FS(x̄T ,y)− inf x:(x,ȳT )∈D
FS(x, ȳT ) ≤ 2β(16 + 332(1−c2) )(‖x0 − x̂ ∗‖2 + ‖y0 − ŷ∗‖2) T .
Combined Lemma 7 and Lemma 15, we know that the argument stability bound of EG is
‖x̄iT − x̄T ‖+ ‖ȳiT − ȳT ‖ ≤ 4L
nµ + 4
√ 1
µ
√ 4sS(x̄T , ȳT )
≤ 4L nµ + 4
√ 1
µ
√ 2β(16 + 332(1−c2) )(‖x0 − x̂∗‖2 + ‖y0 − ŷ∗‖2)
T .
(53)
Furthermore, for any x ∈ X , y ∈ Y and z ∈ Z ,
f(x,y; z) ≤ f(x̂∗, ŷ∗; z) + L‖x− x̂∗‖+ L‖y − ŷ∗‖
≤ sup z∈Z
f(x̂∗, ŷ∗; z) + √ 2L √ ‖x− x̂∗‖2 + ‖y − ŷ∗‖2
≤ sup z∈Z
f(x̂∗, ŷ∗; z) + L √( 4 +
4 1− 4ν2β2 ) (‖x0 − x̂∗‖2 + ‖y0 − ŷ∗‖2), (54)
where the first inequality follows from Assumption 1, the second inequality follows from CaucySchwartz inequality and the last inequality follows from (52). Now, plugging (54), the stability bound in (53) and the strong PD empirical risk bound in Lemma 15 into Theorem 1, we obtain generalization bounds of EG. The main theorem is shown below. Theorem 8. Assume for all z, the function (x,y) 7→ f(x,y; z) is µ-SC-SC. Let {xt,yt} and {xt+1/2,yt+1/2} be the iterates produced by (49)-(50). Assume the stepsize ν satisfies the condition ν = c2β for any c ∈ (0, 1). Denote Ax(S) = x̄T and Ay(S) = ȳT for (x̄T , ȳT ) in (51). Denote the ESP solution as (x̂∗, ŷ∗). Consider the compact convex set in (52). Fixed any
η > 0. Let M = supz∈Z f(x̂ ∗, ŷ∗; z) + L √( 4 + 41−4ν2β2 ) (‖x0 − x̂∗‖2 + ‖y0 − ŷ∗‖2). Let
B = 2β(16+ 33 2(1−c2) )(‖x0−x̂∗‖2+‖y0−ŷ∗‖2)
T and E = 4L nµ + 4 √ 1 µ √ B. There exists an absolute posi-
tive constant C.
(a) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
F (x̄T , ȳT ) ≤ (1 + η)FS(x̄T , ȳT ) + C 1 + η
η (M n log(1/δ) +B log2 n log(1/δ) ) .
(b) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
R(x̄T ) ≤ (1 + η)RS(x̄T ) + C 1 + η
η (M n log 1 δ + (β µ + 1 ) LB log2 n log 1 δ ) .
(c) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
4s(x̄T , ȳT ) ≤ (1 + η)E + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) BL log2 n ) log (1 δ ) .
(d) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
4s (x̄T , ȳT )−4sS(x̄T , ȳT ) ≤ ηE + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) BL log2 n ) log (1 δ ) .
(e) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
R(x̄T ) ≤ (1 + η) inf x∈X
R(x) + C 2 + η
η (M n log 1 δ + (β µ + 1 ) LB log2 n log 1 δ + E ) .
Remark 15. When conditions in Theorem 8 hold, we obtain that (a) If Assumptions 1 and 2 hold and FS(x̄T , ȳT ) = O ( 1 n ) , then for any δ > 0, with probability at least 1 − δ, the plain generalization
error of (x̄T , ȳT ) of EG is of the order O (( 1 n + √ 1 T ) log2 n log(1/δ) ) . (b) If Assumptions 1
and 2 hold and RS(x̄T ) = O ( 1 n ) , then for any δ > 0, with probability at least 1 − δ, the primal
generalization error of (x̄T , ȳT ) of EG is of the order O (( 1 n + √ 1 T ) log2 n log(1/δ) ) . (c) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1 − δ, the strong PD population risk and the strong PD generalization error of (x̄T , ȳT ) of EG are all of the orderO (( 1 n+√
1 T ) log2 n log(1/δ) ) . (d) If Assumptions 1 and 2 hold and infx∈X R(x) = O ( 1 n ) , then for any δ > 0, with probability at least 1 − δ, the excess primal population risk of (x̄T , ȳT ) of EG is O (( 1 n + √ 1 T ) log2 n log(1/δ) ) . For the above bounds, we can take T = O(n2) gradient
evaluations to get bound of the order O (
logn n log(1/δ)
) .

heading: G OPTIMISTIC GRADIENT DESCENT ASCENT
text: OGDA is introduced by Popov (1980), as a variant of the EG method. We introduce some notations to state the result of OGDA. Given a stepsize parameter ν > 0, OGDA do the following update for each t ≥ 0
xt+1 = xt − 2ν∇xFS(xt,yt) + ν∇xFS(xt−1,yt−1), yt+1 = yt + 2ν∇yFS(xt,yt)− ν∇yFS(xt−1,yt−1). (55)
Assume that the initial point satisfies x0 = x−1 and y0 = y−1. Consider the averaged iterate
x̄T = 1
T T∑ t=1 xt and ȳT = 1 T T∑ t=1 yt. (56)
We first provide a lemma on the strong PD empirical risk of OGDA. Lemma 16. (Mokhtari et al., 2019) Let {xt,yt} be the iterates generated by the OGDA updates in (55). Assume that the initial point satisfies x0 = x−1 and y0 = y−1. Suppose the ESP solution (x̂∗, ŷ∗) exists. Assume that FS(x,y) is a convex function of x for any y and is a concave function of y for any x. If Assumption 2 holds and the stepsize ν satisfies 0 < ν ≤ 14β , then:
(a) the iterates {xt,yt} stay within the compact convex set D := { (x,y)|‖x− x̂∗‖2 + ‖y − ŷ∗‖2 ≤ 2(‖x0 − x̂∗‖2 + ‖y0 − ŷ∗‖2) } . (57)
(b) for all T ≥ 1, we have
sup y:(x̄T ,y)∈D FS(x̄T ,y)− inf x:(x,ȳT )∈D
FS(x, ȳT ) ≤ (16β + 12ν )(‖x0 − x̂ ∗‖2 + ‖y0 − ŷ∗‖2) T .
Combined Lemma 7 and Lemma 16, we know that the argument stability bound of OGDA is
‖x̄iT − x̄T ‖+ ‖ȳiT − ȳT ‖ ≤ 4L
nµ + 4
√ 1
µ
√ 4sS(x̄T , ȳT )
≤ 4L nµ + 4
√ 1
µ
√ (16β + 12ν )(‖x0 − x̂∗‖2 + ‖y0 − ŷ∗‖2)
T . (58)
Moreover, similar to (54), we have
f(x,y; z) ≤ f(x̂∗, ŷ∗; z) + L‖x− x̂∗‖+ L‖y − ŷ∗‖
≤ sup z∈Z
f(x̂∗, ŷ∗; z) + 2L √ ‖x0 − x̂∗‖2 + ‖y0 − ŷ∗‖2. (59)
Therefore, plugging (59), the stability bound in (58) and the strong PD empirical risk bound in Lemma 16 into Theorem 1, we obtain generalization bounds of OGDA.
Theorem 9. Assume for all z, the function (x,y) 7→ f(x,y; z) is µ-SC-SC. Let {xt,yt} be produced by (55). Assume the stepsize parameter ν satisfies 0 < ν ≤ 14β . Denote Ax(S) = x̄T and Ay(S) = ȳT for (x̄T , ȳT ) in (56). Denote the ESP solution as (x̂∗, ŷ∗). Consider the compact convex set in (57). Fixed any η > 0. Let M = supz∈Z f(x̂ ∗, ŷ∗; z) + 2L √ ‖x0 − x̂∗‖2 + ‖y0 − ŷ∗‖2. Define B = (16β+ 1 2ν )(‖x0−x̂
∗‖2+‖y0−ŷ∗‖2) T and E = 4L nµ + 4 √ 1 µ √ B. There exists an absolute
positive constant C.
(a) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
F (x̄T , ȳT ) ≤ (1 + η)FS(x̄T , ȳT ) + C 1 + η
η (M n log(1/δ) +B log2 n log(1/δ) ) .
(b) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
R(x̄T ) ≤ (1 + η)RS(x̄T ) + C 1 + η
η (M n log 1 δ + (β µ + 1 ) LB log2 n log 1 δ ) .
(c) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have 4s(x̄T , ȳT ) ≤ (1 + η)E + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) BL log2 n ) log (1 δ ) .
(d) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have 4s (x̄T , ȳT )−4sS(x̄T , ȳT )
≤ ηE + C(1 + η) (L2(1 + η)
nµη + M n + ( 1 + β µ ) BL log2 n ) log (1 δ ) .
(e) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1− δ, we have
R(x̄T ) ≤ (1 + η) inf x∈X
R(x) + C 2 + η
η (M n log 1 δ + (β µ + 1 ) LB log2 n log 1 δ + E ) .
Remark 16. When conditions in Theorem 9 hold, we obtain that (a) If Assumptions 1 and 2 hold and FS(x̄T , ȳT ) = O ( 1 n ) , then for any δ > 0, with probability at least 1 − δ, the plain generalization
error of (x̄T , ȳT ) of OGDA is of the order O (( 1 n + √ 1 T ) log2 n log(1/δ) ) . (b) If Assumptions 1
and 2 hold and RS(x̄T ) = O ( 1 n ) , then for any δ > 0, with probability at least 1 − δ, the primal
generalization error of (x̄T , ȳT ) of OGDA is of the order O (( 1 n + √ 1 T ) log2 n log(1/δ) ) . (c) If Assumptions 1 and 2 hold, then for any δ > 0, with probability at least 1 − δ, the strong PD population risk and the strong PD generalization error of (x̄T , ȳT ) of OGDA are all of the order
O ((
1 n + √ 1 T ) log2 n log(1/δ) ) . (d) If Assumptions 1 and 2 hold and infx∈X R(x) = O ( 1 n ) ,
then for any δ > 0, with probability at least 1− δ, the excess primal population risk of OGDA is of the orderO (( 1 n + √ 1 T ) log2 n log(1/δ) ) . For the above bounds, we can take T = O(n2) gradient
evaluations to get bound of the order O (
logn n log(1/δ)
) .

heading: H AUXILIARY DESCRIPTIONS OF TABLE 1
text: In Table 1, Lip means Lipschitz continuity and S means smoothness. (R)-ESP means the (regularized)-empirical risk saddle point (Zhang et al., 2021a). C-SC means convex-µ-stronglyconcave, and NC-SC means nonconvex-µ-strongly-concave. A function f(x,y) is called nonconvex-strongly-concave if f(x, ·) is strongly-concave for every x. Moreover, a function f(x,y) is µ-weakly-convex-weakly-concave (WC-WC) if f+ µ2 ( ‖x‖2 + ‖y‖2 ) is convex-concave. V-WCWC is a variant of WC-WC, please refer to (Lei et al., 2021). PL means the two-sided PL condition, which relaxes the convex-concavity requirement of the objective function (Yang et al., 2020) and is usually used to guarantee the linear convergence rate (Karimi et al., 2016; Yang et al., 2020). AGDA algorithm is variant of GDA with alternating updates of the primal-dual variables. c is a parameter in the step size, β is a parameter in Assumption 2 and k := β/µ.

heading: I NUMERICAL EXPERIMENTS
text: In this section, we report preliminary experimental results to verify our theoretical results by performing numerical experiments on the simulated data. We study how the generalization error would behave along the number of samples. To this aim, we consider an isotropic Gaussian data vector Z ∼ N (0, Id×d) with zero mean and identity covariance. We will drew n independent samples from the underlying Gaussian distribution to form a training dataset S = {z1, ..., zn}. We set the dimension d of Z as 50. Similar to the strongly-convex-strong-concave case of (Farnia & Ozdaglar, 2021), we consider the following minimax objective function
f(x,y; z) = xT (z− y) + µ 2 (‖x‖2 − ‖y‖2).
In the experiments, we set µ = 1 and constrain optimization variables x and y to satisfy ‖x‖, ‖y‖ ≤ 100 which we enforced by projection. For this minimax objective function, one can verify that
F (x,y)− FS(x,y) = xT (E[Z]− ES [Z]); R(x)−RS(x) = xT (E[Z]− ES [Z]),
where E[Z] = 0 since the mean of the underlying Gaussian distribution is 0, and where ES [Z] = 1 n ∑n i=1 zi. For brevity, we call |xT (E[Z]− ES [Z])| the “generalization error”.
We apply the above experimental settings to validate the theoretical results of GDA, SGDA, EG, and OGDA. We evaluate the generalization error |xT (E[Z] − ES [Z])| and apply these algorithms to S. For GDA and SGDA, we consider the stepsize parameter as 1/t. We iterate GDA with n2 times and SGDA with n4 times. The generalization error of GDA and SGDA with different sizes of training data are reported in Figure 1. And for EG and OGDA, we select the stepsize parameter as 0.003. We run EG and OGDA n2 times. Similarly, the generalization error of EG and OGDA with different sizes of training data are given in Figure 2. From the two figures, we can see that the line of best fit for the generalization error is log
3/2 n n0.98 for GDA, logn n0.98 for SGDA, log0.99 n n0.98 for EG, and logn n1.02
for OGDA. These results match the predictive rates of the plain generalization error and the primal generalization error in Table 1, i.e., log
3/2 n n for GDA, logn n for SGDA, logn n for EG, and logn n for
OGDA, which verifies our theoretical findings.

Review summaries:
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.

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.

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.

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.