High Probability Generalization Bounds with Fast Rates for Minimax Problems
Authors: Shaojie Li
Yong Liu
Venue: ICLR 2022 Poster (2022)

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 $\mathcal{O}(1/\sqrt{n})$, where $n$ is the sample size. In this paper, we provide improved generalization analyses and obtain sharper high probability generalization bounds for most 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.

Published as a conference paper at ICLR 2022
HIGH PROBABILITY GENERALIZATION BOUNDS WITH FAST RATES FOR MINIMAX PROBLEMS
Shaojie Li Yong Liu
'Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China BBeijing Key Laboratory of Big Data Management and Analysis Methods, Beijing, China 20200002770 edu.cm en, liuyonggsai ruc edu.
ABSTRACT
Minimax problems are receiving an increasing amount of attention in a wide range of applications in machine learning (ML), for instance, reinforcement learning, ro- bust optimization, adversarial learning, and distributed computing, to mention but few. Current studies focus on the fundamental understanding of general minimax problems with an emphasis on convergence behavior. As comparison, there is far less work to study the generalization performance. Additionally, existing gen- eralization bounds are almost all derived in expectation, and the high probability bounds are all presented the slow order ((L/VT), where n is the sample size. In this paper, we provide improved generalization analyses and obtain sharper high probability generalization bounds for most existing generalization measures of minimax problems. We then the improved learning bounds to establish high probability generalization bounds with fast rates for classical empirical sad- dle point (ESP) solution and several popular gradient-based optimization algo- rithms. including gradient descent ascent (GDA), stochastic gradient descent as- cent (SGDA), proximal point method (PPM), guru-ggadient (EG), and optimistic gradient descent ascent (OGDA). In summary, we provide a systematical analysis of sharper generalization bounds of minimax problems.
INTRODUCTION
Minimax learning problems have achieved great success over a broad range learning tasks in ma- chine 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 G
low al.) 2014), distributed computing (Razaviyayn et al. 2020 Shammal 2008 Mateos et al. 2010), and AUC maximization (Lei & Ying, (001bb). to just name a few. This framework is formu- lated as zero-sum game characterized 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 mini- mization operator (Liu et al., [20216] Yin et al. 2020): Li & Liu 2021 Li et al., 2018 Liu et al., 2020 Li & Liu 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 convex- concave settings (Nemirovski et al., 2008). nonconvex-concave set- ting (Rafique et al. 2018), strongly convex convex-strongly --ttosgly-concaay setting (Balamurugan & Bach 2016). and
setting (Liu et al.) 2021a 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 the test data.
To the best of our knowledge, there is only three work on the generalization bounds of minimax op- timization algorithms (Zhang al. 202 la Farnia & Ozdaglan 2021 Lei et 202T Among them,
"Corresponding Author.

---

Published as a conference paper at ICLR 2022
(Zhang et al. 202 la) studies the generalization bounds for ESP solution to minimax problems, (Far- nia & Ozdaglar| (222]) analyzes the generalization properties of several mudieent-bssed optimization algorithms: GDA, SGDA, GDmax and PPM, and (Lei et al., 202I) provides systematical gen- eralization 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 the slow order O (1/ vn).
It is known that the high probability bound is beneficial to understand the robustness of optimization algorithms (Bousquet et al.] 2020 Klochkov & Zhivotovskiy, (02T)) and is much more challenging
to be derived (Bousquet et al.J 2020; Lei et al.) 20121 Lv et al.j (02T). 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., [022]] 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.
RELATED WORK
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 [Shalev- Shwartz & Ben-David 2014, Shalev-Shwartz et al., 2010). A training algorithm is stable small changes in the training set lead to small differences 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 al. 2016 Lei et (0220), uniform argument stability (Liu et al. [|ssisyy et al. 2020). hypothesis
stability (Bousquet& & Elisseeff 2002 Charles & Papailiopoulos 2018), hypothesis set stability (Fos-
ter et al. 2019). on average stability (Shalev-Shwartz et al. 2010, Lei & Ying 2020 Kuzborskij &
Lampert 2018 Zhang et al.] 202Tb] [eib & Ying (021a), |ing]2021a), locally elastic stability (Deng et al.] (021)).
collective stability (London et al. 2016), and PAC-Bayesian stability (Li et al. 2020). These stabil- ity measures have been extensively studied 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 /Zhng et al.
2021a; Lei et al. 2021). In related work (Farnia & Ozdaglan lar] /2han et al. 2021 [0021a]La Lei et al. 2021). they mostly focus on the expecta- tion form of these stability measures since they are 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 202T).
Convergence analysis. Convergence analysis has been widely studied in different settings, includ- ing convex-concave learning (Nemirovski (2005) Nedic Ozdaglar 20099 Mokhtari et 2020
Cherukuri et al. 2017; Mokhtari et | Balamurugan & Bach 2016; Hsich et al.) 20199 Yan
et 20200 Lin et al.] 2020b] Wang Li 20200 Yoon & Ryu 2021). nonconvex-coneave learning
(Rafique et al. [018]] Kong& & Monteiro| 2019;Luu et al. 2020 Grnarova et al., 2017 Thekumpara-
impil et al. [2019 9: Lu et al. [200 Namkoong & Duchi 2016 Sanjabi et al. 2018 Nouiched et al.j
2019 et al. [202aa] Sinha et [017] Chen et al. 2021). and nonconvex-nonconcee
learning
(Heusel et al.
2017 |
Balduzzi et al. [2018] Daskalakis & Panageas 2018 Mertikopoulos et al. 2019
Loizou et al. 2020: Yang al. 2200 Liu et al. [02 Lin et al.) 2018 Diakonikolas et al. 2021
Wang et al. 2020:Loizou Loizou et al. 2021 Fiez & Ratliff 2021). There are so many studies on conver-
gence. Thus, considering the length limit, the references listed here are not complete. Please refer
2

---

Published as a conference paper at ICLR 2022
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 essential role in this paper, formalized as strong PD empirical risk (please refer to Defi- nition T which is defined on the function value difference and referred to as optimization error or prima -dual gap in some convergence literature (Lei et al. 2021 Nemirovski 2005 Mokhtari al.,
2019 2020).
3 PRELIMINARIES
Let X' and y be two parameter spaces R. Let P be a probability measure defined on a sample space Z. We define f X' x y x Z + IR and consider the following minimax optimization problem
min max yxx,y) Ex xEX yEy
(1)
The above minimax objective represents an expectation of cost function [(x, y; for minimiza- tion variable x, maximization variable y and data variable 2. Unfortunately, we typically are not available to the underlying distribution In practice, F is approximated by the corresponding em- pirical risk. Let S = {z1,... J be dataset whose samples are independent drawn according to P. the empirical risk is defined as
1 Ti Σ yxx,y;2)..
Fs y)
Let the output of a (randomized) algorithm A on a dataset S be A(S) := (Ax(S). Ay())) E X ). 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 202 Lei et al., 202T. the coupling between the minimization variable and the maxi- mization variable in (1) makes minimax problems have many different generalization performance measures. These measures are collected in (Lei al.) (021). For better readability, we use their symbols. Let E be the expectation with respect to (w.r..) the randomness of algorithm A and the dataset S. These generalization measures are listed below.
Definition 1. (Leiet al. 2021) There are four groups of generalization measures.
(Primal Measures.) The primal population risk of a model x is defined as R(x) supyey y), and the corresponding primal empirical risk is defined supyey F)( Then, when using empirical risk Rx(x) to bound R(x), we call this error of the model x the primal generalization error. While using optimal infxex R(x) to bound R(x),
Rs(x)
call this error of the model x the excess primal population risk.
2 (Plain Measure.) When using Fs(x,8) 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, is defined
(x = sup F(x, inf y'Ey
F(x' v))
x'EX
and the corresponding strong PD empirical risk is defined as
xx = sup Fs(x,y') inf Fs(x',
y'Ey
x'EX
Then, the strong PD generalization error (xx - y) of the model (x,y) y) is defined as
sup F(x,y') sup Fs(x,y')) + inf Fs(x', inf y'ey
F(x',))
yey
x'ex
x'eX
4 (Weak Measures.) The weak PD population risk of a (randomized) model (x,y) is defined as E[F(x,y') inf
A (x, = sup y'Ey
x'EX E(F(x',)))
and the corresponding weak PD empirical risk is defined as inf E[Fs(x', .y)]. x'EX
(x, sup E[Fs y')l
y'Ey
3

---

Published as a conference paper at ICLR 2022
Then, the weak PD generalization error (x (x y) of the model (x,y) is defined as inf X'EX'
sup (.Fs(xx))))) + ( sup E[F(x,y')l Y'EY
inf (x (x'ssxx')) y)]
y'Ey
x'EX
Remark 1. We provide some discussions for the four groups of measures. (I. Primal Mcasures:) In the context of GANs, the primal population risk R(xx represents 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 202I). One would be interested in the re- lationship between R(x) and its corresponding empiniaal risk (x),), and the relationship between R(x) and infimum en R(x'). (2. Plain Measure:) This generalization measure direct extension of the standard generalization error in the minimization optimization. (3. Strong Mea- sures:) (x. y) is referred to as the primal-dual gap in the optimization literature. 4x y) is the primal-dual gap of the population risk. A y 4 (x. 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 ran- domness of the dataset and the algorithm, for instance, supy'ey y(x.y") - infx'ex F(x', .y) in the strong measures and ey E[ ] infx'xx [x[ (P',))) 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 Ly norm of a random variable Z as |21|,, (E (E2|ZIP)1/P Let ||-|| be the Euclidean norm and (t be the inner product. A differentiable function g W + RR is called p-strongly-convex in w if the following inequality holds for every WI, W2:
g (W1))= g(w2) 2 (Vo(w2),
w2) + |w w11--wl"" w1
2
where the gradient operator. We say g p-strongly-coneeve -g is p-strongly-convex. Definition 2. Let X x y R. Assume that X and y are convex feasible sets. Then
1. g butteongy-comee---tonnnyyooooooo (μ-SC-SC) if y) is p-strongly-converforr for any y E y and .) is y-strongly-concave for any x E X.
2. 9 convex-concave (C-C) if is O-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 learning algorithm. Intuitively, an algorithm A 2 >> (X) is said to be stable if the output model (Ax(S), Ay)) is insensitive to perturbations. Let S' be a neighboring dataset that differs most one single example to S. Definition (Algorithmic Stability). Let be a learning algorithm and > 0.
1. We say A is e-umiformly-stable for any training datasets S, S' E Z" we have sup (S(A AS)); [(Ax(S"), Ay (S"); Se. 2. We say A is e-argument--tubbe if for any training datasets S,S' S' E nn we have
[Ax(S) Ax + [|Ay(S) Ay (S')ll <
From Definition 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 I implies f is Lipschitz continuous w.r.t. both x and y, while Assumption ?implies f is smooth w.r.t. (x,y). Assumption (Lipschitz continuity). Let L O. Assume that for any x E X. y e y and z E Z, ((x,;;2) satisfies
[xf 2]1 <
and [Vyf(x, y: 2) L.
Assumption (Smoothness). Let 3 > 0. Assume that for any X1, X2 E X, y1,32 E y and = E 2, f(x, 2) satisfies
(V - V vx
(x1
xi x2
[y fx
<
y1 y2
Under Assumption [ the argument stability implies the uniform stability. Therefore, the argument stability is the main stability measure that will focus on.
4

---

Published as a conference paper at ICLR 2022
4 MAIN RESULTS
In this section, we provide sharper high probability bounds for the generalization measures of Defi- nition shown as follows.
Theorem 1. Let A be learning algorithm and O. Suppose (f y; M for some M and x E y E v,,2 E Z. Fixed any 1j > O. There exists an absolute positive constant C.
(a.) If the algorithm A is e-uniformly stable, then for any > with probability at least 1
8,
F (S), Ay(5) & (1 F)) Ay(S) + C 1 + M
(x
1 1og(1/6) - =ologg n log 5)
(b.) Assume that for all x, the function y + y) is p-strongly-concave If the algorithm A is e-argument stable and Assumptions) and hold, then for any >> with probability at least 6,
R(Ax(S)) S (1 (s)(((())) + C 1 +
M 1 + (1)1) loge n log }) log 8
Lc
77
(c.) Assume that for all x and y. the function F(x,y y) is p-SC-SC. If the algorithm A is e-argument stable and Assumptions and hold, then for any > O, with probability at least 1 -, 5,
(Ax(S), (3(( Ay + ml 43 Ay
( (-:(1 n) + (1 /r e logo n1 log (T)
+ +C(1 + v)
(d.) Assume that for all x and y. the function F(x, y) is J-SC-SC. If the algorithm A is e-argument stable and Assumptions [nsumppiioss[aad]]22 hold, then for any 5 O, with probability least 1 - 8.
^ (Ax(S), - A3(Ax (S)) S 1 A3 (Ax(S), Ay()))
(,(1++)) (,211 + n)
M
(1 ) m log (t)
+ 7))
mpm
(e.) Assume that for all the function y + F(x,y' y) is y-strongly-concave. If the algorithm A is e-argument stable and Assumptions and 2 hold, then for any O, with probability at least 1 6,
R(Ax(S)) < (1 +1+10 77) inf R(x)
XEX
2 + 7
M
1 log 5 + (L +1+ Lo log, n nog 5
+ C
+ (3)(A
According to Definition 1 and Jensen's inequality, we know that A yx < E[AA y)) and
(x y) < [xA3(x,y]] By this connection, we have A ""(x, "(x,)) v) A (x, y) S [x + [E[A3 y)ll. We therefore obtain the following results for (x, and A 4 x, y) (x.
Corollary 1. Suppose the same conditions as Theorem D hold.
(f.) If the assumptions of Part (c) in Theorem 7 hold, then with probability least 1 - 5,
A (AL()) (1 A Ay), (2 + n) npm
M hold, then with probubility least 1 8.
0 m) log (
C(1 m)
(g.) If the assumptions of Part (d) in Theorem
A "
< |BAS Ay
(2((1+ ( + M + (1
+ loga n) log (
B cL
+ +1+ (4)))
74m
5

---

Published as a conference paper at ICLR 2022
In Theorem[] we have established a quantitative connection between the generalization measures and the stability measures. The complete proof of Theorem iis provided in Appendix
Remark 2.
Part (a) provides the relationship between the uniform stability and the plain generalization ror of A5),, If the uniform stability of algorithm A is of fast order (11/n), then (SAx (S)) is bounded by (1 (F)(((()))))
+ log n (og(1/)))) ). Usually for 7037
well-trained model (S), Ay (S)) over the training set, the empirical risk (A), (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 (1/n), then we can choose a proper constant for r) and the plain generalization error will be of fast order O loog xlog(1/0)). It is (1/nn) when we hide the logarithmic term. In the related work, (Lei et al. 202T also establish the plain generalization error bound under the same assump- tions, but their bound of slow order O( log log(1/ō) + Mn 2 (1g())))). Even if they get can not disappear. By
sharper bound for stability measure e, the influence of On= log(116) comparison, we have completely removed the O(1/v/) term. Thus, our plain generalization error bound enables the fast (1/nz) 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 (S) are of order (11nn), then the primal generalization error implies a fast (1//n) rate. Consider- ing that we assume the function I is well-behaved, i.e., Lipschitz continuity, smoothness, and the strong-concavity of its population risk F, and that (s(AAx()) is data-dependent. thus it is reason- able to assume (Ax(()) is small for well-trained model (S) (Lever et al. 2013 Yang al. 2019 Cortes et al., (02T). In (Lei et al. 202T), they also establish a bound for primal general- ization error under the same assumptions. However, their bound is ([LBy=lclogn (1g() +
Mn /oog((1l))) limited to the O(1/vn) order. In contrast, we successfully removed the
((///n) term, which makes the fast rate possible. (Farnia & Ozdaglar 2021 studies the expected primal generalization error, i.e., bounding a [R([[[(As, (X((((x())))) by Es,A A [Rs (S)). They establish the connection between the stability measure and the expected error under the same assumptions as Part (b). which is then used 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 (L)/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 dependence on the iterative number T (see Lemma g of GDA, Lemma I of SGDA, etc.). To obtain sharper generalization bounds, we require T to be associated with n, such as T O(n²) 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 the specific ESP problem. Under the same assumptions, they provide the upper bound of order O (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 (L/nn) order, the strong PD generalization error will be of the fast order OLLnn). Although Part (c) and Part (d) have a similar upper bound, they are different generalization measures (Lei) et al. (02T). 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,AA (A), (S)) - (A (S), Ay Under the same assumptions, their expected strong PD generalization error is bounded by (1 + Lv which can also be used to obtain O (1 (1) 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 strong PD empirical risk, and x R(x) are all of the order (1/nn,, the excess primal population
algorithm A, the
6

---

Published as a conference paper at ICLR 2022
risk will also be of the fast order (1/m)). Meanwhile, in the minimization learning problems, assuming the optimal population risk F is small or even zero, i.c. F I 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 =((/a) 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 infxxx R(x) is small. High probability excess primal population risk bound also studied for SGDA in (Lei et al. 2021). Their bound, however, is of slow order ((3/p))n= log log (1/6) and is restricted to SGDA. By comparison, our result in Part (e) enables (11/n) bounds for stable
minimax learning algorithms since we have completely removed the O(1/ /n) term.
We discuss 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 (S)) Ay (S)). R (w.rt.
Rs( ((((A(()))))) (S)). and R(A (S)) (w..t. infxex R(x)), respectively, while (Lei et al. 2021 Farnia &
Ozdaglar 2021) study the upper bounds of (S)x Ay() - (s (S), Ay )), R (S))
Rs(Ax(()) )), and (S))
infxex R(x) (or their expected forms). One of our motivations to
study such forms is that, in practice. we are often directly interested in the true risk, i.c., how the
learned models behave on the testing data, such as (S)x Ay))), instead of the error between the true risk and empirical risk. Note that in the above comparison between Theorem [ and the results in (Lei et al. [021]] 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 Ay()))))))))))))))))))))
Fs (S) (5)) 1 nF's (Ax Ay + C ( A log(1/8) + + elog, 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 (11/n) order bounds for two terms in Theorem D stability measures and strong PD empirical risk. Hence, the strong PD population risk and the strong PD generalization error will be of the fast order ((1/n) when applying Theorem to these applications. These bounds are clearly of order OLL/n) and sharper than the results in Zhang et al., 2021a; Farnia & Ozdaglar 2021: Lei et al. 202I). For the plain generalization er- ror, the primal generalization error, and the excess primal population risk, to obtain (11/n) order bounds for these applications, we need to assume the extra corresponding terms (S)x Ay (S)), (S)), and infxxx R(x) are of order ((1/n), respectively. The clear motivation is that in practice, learning algorithms achieve small or even zero empirical risk, as discussed in Remark 2
Remark 4. This remark discusses 17 in Part (a), Part (b), and Part (c). (1:) When establishing sharper generalization error bound (i.e., Pf f) the existence of 1j 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 < -- Pmf O(r + 9log(1/6)) with 27 > 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. (013) (see Theorem 6), (Yang et al. 2019) (see Proposition 3.1 and Theorem 4.3), etc., also have 17. For instance, the Catoni's 's bound of with > 0 Catonni 2007). In the algorithmic stability theory, Theorem 1.2 in (Klochkov & Zhivotovskiy, 2021) is of the form Pf < (1 +1+1 pnf + 1+1 O(( log n + 1,) l)g())) with 1) > O. In the recent Cortes's deviation margin bounds (Cortes et al. (02T), they also imply a multiplier 17. The above bounds can be transformed into the form of empirical risk multiplied by 1 + 17. similar to our results. It is discussed in (Lever) ict 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 fast rate when the empirical risk is small. Note that Part (e) also involves generalization error bounds due to the decomposition,
71
the form PQ V I-e n (nPaQ + O Prio))
see (1I. The above generalization error analysis thus holds for Part (e). (2:) Furthermore, in 10 we show that (S)x Ay - Fs(Ax Ay S (M(MM(Ax(S))A
log(1 (og(1/62)) +
log(!) ()), where M means that yx; S M. yx, z. Using the elementary inequality Vab <
na + 3,b for any a, b, > 0 and by some rearrangements, the form of Part (a) appears. This is the reason why 1) exists. The corresponding bound in (Lei et al. 2021) F(Ax(S), Ay))
(Ax (S)) < (c log(t) + Mn 1 log' / (())). Focusing on the dominated term, it is clear that F(A, Ay) < M since (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).
7

---

Published as a conference paper at ICLR 2022
Reference
Algorithm
Assumption
Generalization Measure
Learning Bound ((1/n)
SC-SC, Lip
Weak PD Risk
ESP
Zhang
SC-SC, Lip, S
(E.) Strong PD Risk
O(1/n)
R-ESP
C-C, Lip
Weak PD Risk
((1/v))
SGDA
SC-SC, Lip, S
(E.) Primal generalization
SGDmax
SC-SC, Lip. S
(E.) Primal generalization
O[1/n
GDA
SC-SC. Lip. S
(E.) Primal generalization
O[1/n
GDmax
SC-SC, Lip.
(E.) Primal generalization
O(1/n
Farnia
РPM
SCp,
(E.) Primal generalization
O(1/n)
PPM
C.C,Lip.
(E.) Primal generalization
((1/Vn)
SGDA
Lip.
(E.) Primal generalization
(T
SGDmax
NC-SC, Lip, S
(E.) Primal generalization
( (1+110L00+
C-C, Lip
Weak PD Risk
((L/V))
C-C,Lip. S
Weak PD Risk
OlIVVn)
SC-SC, Lip
Weak PD Risk
O OlVog n/n
SC-SC, Lip,
Weak PD Risk
(log n/n)
SGDA
C-SC, Lip,
(E.) Excess Primal Risk
O(1/vn)
Lei
C-SC, Lip, S C.C.
(H.P.) Excess Primal Risk
(log nV Vn)
(H.P.) Plain Generalization
Olog n2/ n/Vn)
20pEr1 o (T /n22u43
WC-WC, Lip
Weak PD Generalization
V-WC-WC, Lip, S
Weak PD Generalization
((1/vn) 6214
AGDA
NC-SC, PL. Lip. S
(E.) Excess Primal Risk
(
n
SC-SC, Lip, LN
Plain Generalization
O Olog n
SC-SC, S. LN
Primal Generalization
Olog n
ESP
SC-SC, Lip, S
Strong Risk
Olog n/
SC-SC, Lip,
Strong PD Generalization
Olog n//n
SC-SC, S, LN
Excess Primal Risk
(logn//
SC-SC, Lip, LN
Plain Generalization
O (llon))37
SC-SC, LN
Primal Generalization
O (llogn) n )3/2gn))
GDA
SC-SC, Lip. S
Strong PD Risk
((log n))3///m
SC-SC, Lip,
Strong PD Generalization
O ((log 3
SC-SC. S. LN
Excess Primal Risk
O ((log )
SC-SC, Lip, LN
Plain Generalization
O n/nz
SC-SC, Lip, LN
Primal Generalization
Olog n/n
SGDA
SC-SC, Lip,
Strong PD) Risk
Olog n//n
SC-SC, Lip, S
Strong PD Generalization
Olog
Ours
SC-SC, Lip. S, LN
Excess Primal Risk
Olog n2/1)
SC-SC, LN
Plain Generalization
O n/n
SC.SC, S. LN
Primal Generalization
Olog n/n
PPM
SC-sC,Lip.3
Strong PD Risk
Olog n/n
SC-SC, Lip,
Strong PD) Generalization
Olog n//1
XCSCC,Lip S. IN
Excess Primal Risk
Olog n//n
SC-SC, S. LN
Plain Generalization
Oloo nz/
Lip, LN
Primal Generalization
O n/n
EG
SC-SC, Lip,
Strong PD Risk
Olog n/n
SC-SC, Lip, S
Strong PD Generalization
O n//n
SC-SC, Lip, S, LN
Excess Primal Risk
Ollg 12/n
SC-SC, Lip, S, LN
Plain Generalization
Ollog n
SC-SC, Lip, LN
Primal Generalization
O n/n
OGDA
SC-SC, Lip. S
Strong PD Risk
O n
SC-SC, Lip, S
Strong PD Generalization
O n
SC-SC,Lip. S.
Excess Primal Risk
Olog n//n)
Table Summary of Results. Here, "Zhang" means reference (Zhang al. 2021a
"Farnia" means
reference (Farnia & Ozdaglar (2021), and "Lei" means reference (Lei et al. 2021 The bounds are
established by choosing an optimal iterate number T. "LN" means the low noise condition, see
Section 5.1
Other auxiliary descriptions of Table are shown in Appendix
8

---

Published as a conference paper at ICLR 2022
In summary. the above analyses from two different perspectives support 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, deriv- ing bounds of different generalization measures requires different assumptions (Lei al. 2021
Zhang et al. 2021a] Farnia& & Ozdaglar, [202]) Strong measures require stronger assumptions compared with the weak (Lei et al. 2021). For instance, for the term supyey/ F(Ax(5),)) in (S), (S)), one has to consider the fact that for different AS()), y is different, which makes the proof more challenging. While in (Ax( () (y())) and A Aa(A((S), Ay(S))
(Axx Ay()), both the supremum over (S) and AS) are outside the expectation op- erator, thus one does not need to consider the coupling between (S( and y. The upper bounds shown in Corollary [ directly derived from Theorem 1 are sub-optimal since " (Ax( Ay
and A" (S), Ay(s)) (Ax (S)) (S)) are pretty weak generalization measures (Li et al. 2021.. We list Corollary [ here to suggest that, when Theorem
1 iss established, the fast order O[1/n] easy to be achieved for A (Ax( Ay (S)) and (4Ax((S) (S)) A A (A)(S), Ay On the other hand, the two weak generalization measures in (Zhang et al.) 2021a) is studied for the specific ESP solution, while Corollary iis applicable for any stable minimax learning algorithms, thus may be useful in some applications.
5 APPLICATIONS
We now apply Theorem 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 the Appendix. Here, we list the generalization bounds of these optimization algorithms in Table [
5.1 DESCRIPTIONS OF TABLE 1
Table gives almost all existing generalization bounds in minimax learning. In Table "LN" means the low noise conditions, i.e.. the corresponding F (SA, Ay (5)). (S)), or infxex R(x) of these applications of the order (1/nn) For instance, for the ESP solution $3. we assume F(X-. Y3), R(X5), and inf R(x) are of the order ((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 [ we compare our results with (Zhang et al. 202 a Farnia & Ozdaglar 2021 Lei et al. 202I) in the way described in the last (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
paragraph of Remark
brevity. The descriptions of other notations are shown in Appendix HH
focus on the expected generalization measures. We improve the learning bounds of the ESP solution in (Zhang et al. (02 to high prob- ability guarantees. Compared with (Farnia & Ozdaglar ). 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.c., 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 ion't require the "L.N" condition. Moreover, although (Lei et al. 2021) provides 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
In Table Zhang et al. 2021a and (Farnia & Ozdaglar 2021
Liang & Stokes 2019).
6 CONCLUSION
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 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.
9

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
We appreciate all the anonymous reviewers for their invaluable and constructive comments. This work is supported in part by the National Natural Science Foundation of China (No. 62076234, No.61703396, No. 62106257), Beijing Outstanding Young Scientist Program NO.B/JZZYJH01 (TL.L//HHH0011000000000 Planning Interdisciplinary Platform for the "Double-Fine Class" initiative, Renmin University of China, China Unicom Innovation Ecological Cooperation Plan, Public Computing Cloud of Renmin University of China, Beijing Natural Science Foundation (No. 4222029).
Intelligent Social Governance Platform, Major Innovation &
REFERENCES
Palaniappan Balamurugan and Francis Bach. Stochastic variance reduction methods for saddle-point problems. In Advances Neural Information Processing Systems, 2016.
David Balduzzi, Sébastien Racanière, James Martens, Jakob N. Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n-player differentiable games. In International Conference Ma- chine Learning, 2018.
Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. Annals of Statistics, 33(4):1497-1537 2005.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. In Advances in Neural Information Processing Systems, 2020.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: nonasymp- totic theory of independence. Oxford university press, 2013.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2(3):499-526, 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference On Learning Theory, 2020.
Olivier Catoni. PAC-BAYESIAN SUPERVISED CLASSIFICATION, The Thermodynamics of Statis- tical Learning. 2007.
Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, 2018.
Robert S. Chen, Brendan Lucier, Yaron Singer, and Vasilis Syrgkanis. Robust optimization for non-convex objectives. In Advances in Neural Information Processing Systems, 2017.
Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint 1 2018.
Ziyi Chen, Yi Zhou, Tengyu Xu, and Yingbin Liang. Proximal gradient descent-ascent: Variable convergence under kigeometry. In International Conference on Learning Representations, 2021.
Ashish Cherukuri, Bahman Gharesifard, and Jorge Cortes. Saddle-point dynamics: conditions for asymptotic stability of saddle points. Siam Journal Control and Optimization, 55(1):4865511, 2017.
Corinna Cortes, Mehryar Mohri, and Ananda Theertha Suresh. Relative deviation margin bounds. In International Conference on Machine Learning, pp. 2122-2131, 2021.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Song. Sheed: Convergent reinforcement learning with nonlinear function approximation. In International Con- ference on Machine Learning, 2018
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, 2018
10

---

Published as a conference paper at ICLR 2022
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In International Conference on Learning Representations, 2017.
Zhun Deng, Hangfeng He, and Weijie Su. Toward better generalization bounds with locally elastic stability. In International Conference on Machine Learning, 2021.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael I. Jordan. Efficient methods for struc-
tured eeceonvex-nonconeeee min-max optimization. In International Conference on Artificial Intelligence and Statisties, 2021.
Simon S. Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou Stochastic variance reduc- tion methods for policy evaluation. In International Conference on Machine Learning, 2017.
Farzan Farnia and Asuman Ozdaglar. Train simultaneously, generalize better: Stability of gradient- based minimax learners. In International Conference on Machine Learning, 2021.
Vitaly Feldman and Jan Vondrak. Generalization bounds for uniformly stable algorithms. In Ad- vances Neural Information Processing Systems, 2018.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algo- rithms with nearly optimal rate. In Conference on Learning Theory, 2019.
Tanner Fiez and Lillian J Ratliff. Local convergence analysis of gradient descent ascent with finite timescale separation. In International Conference on Learning Representations, 2021.
Dylan J. Foster, Spencer Greenberg, Satyen Kale, Haipeng Luo, Mchryar Mohri, and Karthik Srid- haran. Hypothesis set stability and generalization. In Advances in Neural Information Processing Systems, 2019.
Ian Goodfellow, Jean Pouget-Abadic, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Infor- mation Processing Systems, 2014.
Paulina Grnarova, Kfir Levy, Aurélien Lucchi, Thomas Hofmann, and Andreas Krause. An online learning approach to generative adversarial networks. In International Conference on Learning Representations, 2017.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: stability of stochastic gradient descent. International Conference on Machine Learning, 2016.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge local nash equilibrium. In Advances in Neural Information Processing Systems, 2017.
Yu-Guan Hsieh, Franck Jutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. In Advances in Neural Information Processing Systems, 2019.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the -ojaakkkeaaiiiiizz condition. In Joint European Conference Ma- chine Learning and Knowledge Discovery in Databases, pp. 795-811, 2016.
Yegor Klochkov and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with conver- gence rate ((1nn). Advances in Neural Information Processing Systems, 2021.
Weiwei Kong and Renato D. C. Monteiro. An accelerated inexact proximal point method for solving conconvex-coneatt min-max problems. arXiv preprint urXiv:/903 13433, 2019.
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Mate- con, 12:747-756, 1976.
IIja Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference Machine Learning, 2018.

---

Published as a conference paper at ICLR 2022
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, 2020.
Yunwen Lei and Yiming Ying. Sharper generalization bounds for learning with objective functions. International Conference on Learning Representations, 2021a.
Yunwen Lei and Yiming Ying. Stochastic proximal auc maximization. Journal of Machine Learning Research, 22(61):1-44 2021b.
Yunwen Lei, Antoine Ledent, and Marius Kloft. Sharper generalization bounds for pairwise learn- ing. In Advances in Neural Information Processing Systems, 2020.
Yunwen Lei, Zhenhuan Yang, Tianbao Yang, and Yiming Ying. Stability and generalization of stochastic gradient methods for minimax problems. In International Conference Machine Learning, 2021.
Guy Lever, François Laviolette, and John Shawe-Taylor. Tighter pac-bayes bounds through distribution-deeendent priors. Theoretical Computer Science, 473:4-28, 2013.
Jian Li, Yong Liu, Rong Yin, Hua Zhang, Lizhong Ding, and Weiping Wang. Multi-class learning: From theory to algorithm. Advances in Neural Information Processing Systems, pp. 1586- 1595, 2018.
Jian Li, Xuanyuan Luo, and Mingda Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. In International Conference on Learning Representations, 2020.
Shaojie Li and Yong Liu. Sharper generalization bounds for clustering. In International Conference on Machine Learning, pp. 6392-6402, 2021.
Shaojie Li and Yong Liu. Towards sharper generalization bounds for structured prediction. In Advances in Neural Information Processing Systems, 2021.
Tengyuan Liang and James Stokes. Interaction matters: A note non-asymptotic local convergence of generative adversarial networks. International Conference on Artificial Intelligence and Statistics, 2019.
Qihang Lin, Mingrui Liu, Hassan Rafique, and Tianbao Yang. Solving weakly-convex-weakky concave aaddee-piint problems as weakly-monotone variational inequality. 2018.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concavv mini- max problems. In International Conference on Machine Learning, 2020a.
Tianyi Lin, Chi Jin, and Michael I. Jordan. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, 2020b.
Mingrui Liu, Hassan Rafique, Qihang Lin, and Tianbao Yang. First-order convergence theory for weakly-convex- wwwaveewwwwaly-cooaaaaa min-max problems. Journal of Machine Learning Research, 22 (169):1-34, 2021a.
Tongliang Liu, Gábor Lugosi, Gergely Neu, and Dacheng Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning, 2017.
Yong Liu, Shizhong Liao, Shali Jiang, Lizhong Ding, Hailun Lin, and Weiping Wang. Fast cross- validation for kernel-based algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(5):1083-1098 2020.
Yong Liu, Jiankun Liu, and Shuqiang Wang. Effective distributed learning with random features: Improved bounds and algorithms. In International Conference on Learning Representations, 2021b.
Nicolas Loizou, Hugo Berard, Alexia Dolicoeur-Martinent Pascal Vincent, Simon Lacoste-Julee Julien, and Ioannis Mitliagkas. Stochastic hamiltonian gradient methods for smooth games. Interna- fional Conference on Machine Learning, 2020.
12

---

Published as a conference paper at ICLR 2022
Nicolas Loizou, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julin Stochastic gradient aascentt-scentt and consensus optimization for smooth games: Convergence
analysis under expected co-coercivity. arXiv preprint arXiv:2107.00052, 2021.
Ben London, Bert Huang, and Lise Getoor. Stability and generalization in structured prediction. Journal of Machine Learning Research, 17(221):7808-7859 2016.
Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive ap- proximation for one-sided non-convex min-max problems: Algorithms and applications. 1EEE Transactions on Signal Processing. 68:3676-3691. 2020.
Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex--tronnlyy-coom Information Processing Systems, 2020.
minimax problems. In Advances in Neural
Shaogao Lv, Junhui Wang, Jiankun Liu, and Yong Liu. Improved learning rates of a functional lasso- type svm with sparse multi-kernel representation. In Advances in Neural Information Processing Systems, 2021.
Gonzalo Mateos, Juan Andrés Bazerque, and Georgios Giannakis. Distributed sparse linear re- gression. IEEE Transactions on Signal Processing, 58(10):5262-5276, 2010.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations, 2019.
Aryan Mokhtari, Asuman E. Ozdaglar, and Sarath Pattathil. Proximal point approximations achiev- ing convergence rate of ((1/k) for smooth convex-concave saddle point problems: Optimistic gradient and extra-gradient methods. 2019.
Aryan Mokhtari, Asuman E. Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradien and optimistic gradient methods for saddle point problems: Proximal point approach. International Conference on Artificial Intelligence and Statisties, 2020.
Hongseok Namkoong and John C. Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Advances in Neural Information Processing Systems, 2016.
Hongseok Namkoong and John C. Duchi. Variance-based regularization with convex objectives. In Advances in Neural Information Processing Systems, 2017.
Angelia Nedic and Asuman E. Ozdaglar. Subgradient methods for saddle-point problems. Journal of Optimization Theory and Applications, 142(1):205-2) 2009.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. Siam Journal on Optimization, 19(4):1574-1609 2008
Arkadi Nemirovski. Prox-method with rate of convergence (11/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. Siam Journal on Optimization, 15())2229-251, 2005.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D. Lee, and Meisam Razaviyayn. Solving a class non-convex min-max games using itcrative first order methods. In Advances in Neural Information Processing Systems, 2019.
Popov. modification of the arrow-hurwicz method for search of saddle points. Mathematical Notes, (8(5):8458845 1980.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv: Optimization and Control, 2018.
Alexander Rakhlin, Sayan Mukherjee, and Tomaso Poggio. Stability results in learning theory. Analysis and Applications, 3(04):397-417, 2005.
13

---

Published as a conference paper at ICLR 2022
Meisam Razaviyayn, Tianjian Huang, Songtao Lu, Maher Nouiched, Maziar Sanjabi, and Mingyi Hong. Non-convex min-max optimization: Applications, challenges, and recent theoretical ad- vances. arXiv preprint 40X1v:2000.08141, 2020
R. Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. Siam Journal on Control and Optimization, 14(5):877-89) 1976.
Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and Jason D. Lee. On the convergence and ro- bustness of training gans with regularized optimal transport. In Advances in Neural Information Processing Systems, 2018.
Shai Shalev-Shwarzz and Shai Ben-David. Understanding machine learning: From theory algo- rithms. Cambridge university press, 2014.
Shai Shalev-Shwarzz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11(90):2635 2670, 2010.
Jeff Shamma. Cooperative Control of Distributed Multi-Agent Systems. 2008.
Aman Sinha, Hongseok Namkoong, and John C. Duchi. Certifying some distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2017.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Optimistic rates for learning with smooth loss. arXiv preprint arXiv: 1009.3899 2010.
Pierre Tarres and Yuan Yao. Online learning as stochastic approximation regularization paths: Optimality and almost-sure convergence. IEEE Transactions Information Theory, 60(9):5716 5735, 2014.
Kiran Koshy Thekumparampil Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algo- rithms for smooth minimax optimization. Advances in Neural Information Processing Systems, 2019.
Yuanhao Wang and Jian Li. Improved algorithms for convex-coneave minimax optimization. In Advances in Neural Information Processing Systems, 2020.
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. In International Conference Learning Representations, 2020.
Yan Yan, Yi Xu, Qihang Lin, Wei Liu, and Tianbao Yang. Optimal epoch stochastic gradient de- scent ascent methods for min-max optimization. In Advances in Neural Information Processing Systems, 2020.
Jun Yang. Shengyang Sun, and Daniel M. Roy. Fast-rate pac-bayes generalization bounds via shifted rademacher processes. In Advances in Neural Information Processing Systems, volume 32, pp- 10802-10812, 2019.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of Systems, 2020.
minimax problems. In Advances in Neural Information Processing
Rong Yin, Yong Liu, Weiping Wang, and Dan Meng. Sketch kernel ridge regression using circulant matrix: Algorithm and theory. IEEE Transactions on Neural Networks, (1):351122335 2020.
TаeHo Yoon and Ernest K. Ryu. Accelerated algorithms for smooth convex-concave minimax prob- lems with (11k2² rate on squared gradient norm. arXiv preprint arXiv:2102.07922, 2021.
Junyu Zhang, Mingyi Hong, Mengdi Wang, and Shuzhong Zhang. Generalization bounds for stochastic saddle point problems. In International Conference Artificial Intelligence and Statis- tics, 2021a.
Lijun Zhang and Zhi-Hua Zhou. Stochastic approximation of smooth and strongly convex functions: Beyond the (11/t) convergence rate. In Conference Learning Theory, pp. 3160-3179, 2019.
14

---

Published as a conference paper at ICLR 2022
Lijun Zhang, Tianbao Yang, and Rong Jin. Empirical risk minimization for stochastic convex op- timization: ([1/n)- and O(1/n")-type of risk bounds. In Conference on Learning Theory, pp- 1954-1979, 2017.
Yikai Zhang, Wenjia Zhang, Sammy Bald, Vamsi Pingali, Chao Chen, and Mayank Goswami. Sta- bility of sgd: Tightness analysis and improved bounds. arXiv preprint arXiv:2102.05274, 2021b.
A PROOF OF THEOREM
We now provide proofs of Theorem I For better readability,, we restate Theorem below.
Theorem 2. Let A be learning algorithu and e > O. Suppose (f(xx < M for some M > 0 and x E X.y E V Z. Fixed any rj > There exists an absolute positive constant C.
(a.) If the algorithm A is e-uniformly stable, for any > O, with probability at least 1 - 8,
F F(Ax(S), (yS) S (1 (s)))))( + C 1 M
log(1/6) ellog ni log 1 $)
(b.) Assume that for all x, the function y + y(x.y) is p-strongly-concav. If the algorithm A is e-argument stable and Assumptions) Aand] hold, then for any > with probability at least 1 1,
M 1 + (+. + +1)Lelog, 1 + /
1 )) log, n log
R(Ax(S)) & (1 + Rs(((()))) + C.
log 8
(c.) Assume that for all x and y. the function F(x, y) is p-SC-SC. If the algorithm A is c-argument stable and Assumptions [anppttiioooonn[ hold,
hold, then for any > O, with probability at least 1 8,
A (A<(S).A,(S)) - 43 (S))
EE 4 (Ax(S),Ay(5))
(1(1+ n)
M + (1+ /
e logg m) log (t))
+ +C m)
(d.) Assume that for all x and y, the function F(x,y) y) is p-SC-SC. If the algorithm A is e-argument stable and Assumptions and hold, then for any O, with probability least 8,
A (3 (S)) S nE A (Ax(S),y((5)
+ + m)
L (2(1+ n)
M
(1
D logg n log (
e
(e.) Assume that for all x, the function y + F(x,y) y) is p-strongly-concave. If the algorithm A is e-argument stable and Assumptions and hold, then for any 8 > O, with probability at least 1 - 5,
R(Ax(S)) < (1 77) inf R(x)
XEX
2 + M
1 + 133 (3)( (s))) ( log 8 + +1 log, n log 5
1
+ C
To prove sharper high probability bounds than (Lei 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 key role in our analysis. However, the direct use this inequality will mevitably lead to slow order bound since it contains sampling error of slow order O(1//n). n We exploit the proof techniques of the recent breakthrough work (Klochkov & Zhiv-
Remark 6.
2021 to make new constructions of 9a(S)) so that the parameter M in Lemma 2 is O. However, the proof techniques of (Klochkov & Zhivotovskiy (02T) can not be directly extended to minimax problems. The coupling construction between the minimization variables and the max- imization variables makes the proofs of minimax problems more difficult than the minimization problem studied by (Klochkov & Zhivotovskiy, 2021). We must proceed with novel decomposi- tions 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).
otovskiy
15

---

Published as a conference paper at ICLR 2022
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 (S)), the optimal y is different in (S)) And the analysis of excess primal population risk in Part (e) is different from the excess risk analysis (klochkov & ZZhvotovskiy 2021). The reason is that the supremum operator in infxex 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 study more optimization algorithms:
SGDA, PPM, EG, and OGDA.
Remark According Definition and Jensen's inequality, we know that (x S [x, y)]. Meanwhile, since we will provide the strong PD empirical risk bounds for several important optimization algorithms in Section 5 thus implies that we also establish bounds with fast rates for (x.
To begin the proof of Theorem we first introduce some key lemmas on concentration inequalities. The first lemma translates moment bound into high probability bound.
Lemma 1,
(Bousquet et al. 2020 Let Z be a random variable with
Il
vpa + pb
for some a, b > 0 and for any p 2 2. Then for any ô E (0,1) we have, with probability at least 1 6,
Z S e (a log (7)
b log ))
where e is the base of the natural logarithm.
The second lemma establishes a concentration inequality for summation of weakly-dependent random variables.
Lemma 2. (Bousquet et al. 2020 Let S = {21,.... 2 be a set of independent random variables
each taking values in 2 and M O. Denote [n] the {1, (1,...,7) ...,... Define S (2) be set (21,..., 2;-1 2i+1. ............ }. Let g1,-.. In be some functions gi : 2 + IR such that the following inequalities hold for any E [n].
(5s((1))9((5))) < M almost surely (a.s.).
Ez, (s()) = a.s.,
for any j [n] with j # i, and 2! E 2
19.(S) - gi (21, 25-1,,,, 1,t 2x)
Then, for any p 2 2
a
a:(S)) S 12v2pm n1 4M /pn.
The following definition and lemma give the concentration inequality for non-negative weakly self- bounded functions.
Definition 4. (Weakly Self- Bounded Function) Assume that b > 0. A function f 2" + [0. +oo) said to be (a, b)-wellly self bounded if there exist functions fo z + +00) that satisfies for all z E Z",
Σ
af
Lemma 3. Klochkov & Zhivotovskiy 2021 Suppose that 21, ... Zn independent random vari-
ables and the function f : 2th 4 00 +oo) is (a, b)-wally self bolfddo and the corresponding
function Js satisfy J((Z)) 2 [(Z") fori =1, 1,..., and any z z", Then, for any O,
Pr(Ef(z1,... 2 f(2), 2nd + S exp (
t2
2alE kn) + 2h
16

---

Published as a conference paper at ICLR 2022
The following lemma is the classical Bernstein concentration inequality.
Lemma 4. (Boucheron et al. 2013) Let 21, 2n. be i.i.d. random variables and assume that B|zi]
μ. Suppose Edl S c.jor any Then for any (0, 1), with probability least 6,
2x log(1/6)
2c log()/))
Σ E=1
14 -
+
3n
where o² is the variance of 24.
A.1 PROOF OF PART (A)
We first prove the plain generalization error bound.
Proof. Let S 1...... 2n be of independent random variables each taking values in 2 and S' -.., 2 be its independent copy. For any i E [n], define S(1 {Z1,..,, 2;-1, z/, 2;+1.-.., 2n be dataset by replacing the i-th sample in S with another i.i.d. sam- ple z/. We first have the following decomposition
mF(Ax((), (F)A - (5)
-
E. (5) (()) (S
+
Σ
). 20] - Σ ((44(1))
1=1
==1
According to the definition of uniform stability (Part of Definition 3) we have
RF
I 2nc + Σ (s(s),
where we
have
introduced gi( =
E E2 (Ax (S(i)) As((()) Z)]
(S())
Ay
Thus, by rearrangement, we have
-
Σ 9:(5) < 2ne.
(3)
Then, for any I,.., n, we define hs) = g:(S) - Es [g, It is easy to verify that
E5 [S)] = O and E., [S)] Ez, [5x] ] - Ez, s.,, (S)) = 0 - = 0. Also, for any
j E [n] with j + and 2 E Z, we have the following inequality
[A.(S) - h.(z1. 2z-11 2 zi+1 2n) S (9:(5) - go (2(21 3j- 24 2j41 "., zn)l
+ |Bs [S:] - Es(( (=1 (0:( 11 25. 2j+1 "..))..., Zn)]
For the first term (g:(S) - ge(21,..., 2j 2" 1j+1, en)). can be bounded by 2 Similar result holds for the sec-
according to the definition of uniform stability. ond term [E ( 1j-1; 2. 2j,1,,..,,, zn)] according to the defini- tion of uniform stability. By a combination of the above analysis, we get (h,(S) h4(21,.., 2j-1, 23)1, 2,) < 4e.
We thus have verified that the three conditions in Lemma 2 are satisfied for h.(S). There will hold the following result for any p > 2
hs(s)
< 48
(4)
17

---

Published as a conference paper at ICLR 2022
Furthermore, we can derive that
n
- - Σ
gi(S)
Σ h,(S)
=m - - Σ [s( [9((S]
==1
=AF(Ax(S) ( Ay - nBg - (AA())
+ +nEg (S),
Due to the i.i.d. property between 5 and S we know that Eg ((A,(S)) = EsF(Ax Ay (S)).
Thus, combined with we have
[IF |
| Σ (:(5)
i=1
"
Σ ((( (S) + nBg (Ax A Ay(8"))|
|nT (
( + +|>5m(()]
2ne -4888/2ee pm poog n
50/2epm log2 n=]
According to Lemma for any (0, 1), with probability at least - 8/3, we have F(Ax(S), (S)) Fs( (S), Ay(S))
nl log(3e/8).
(5)
We begin bound the term Es (s(, Ay (A)) There holds that EsEs: Fs (Ax (S')) = EsF(Ax (S)). We first consider the variance of Esi (S") (S"); 2.). By the Jensen's 's inequality, we have Ay
(Es Ay =)))
E., ( (EE,(
E=E==1(((44(())4444),) (2E),((((44()))))(())))
Then, by the Bernstein incquality in Lemma at least 1 8/3,
we obtain the following inequality with probability
ES Fs (Ax Ay (S') - (S), Ay),
(6)
2E Es (f[AA (S): 2)) (1)) 2M log(388)
n
3n
Combined 5 with 6 we finally obtain that with probability at least 1 - 28/3.
FSAx (S) (S))
2EZES
2))² log(3/0)
2M log(3/0)
+ 550/22ee0oggeeeee n] log(3e/0).
7
3n
In the following, we define 9 = g(2,...,, 2n) = (s), and qi
de (21 zn) sup (n))). So there holds di 2 for any 1,,, and any
18

---

Published as a conference paper at ICLR 2022
{21,.. 2n z". Also, there holds that
0 9))²
(B(( sup E=(((AA(()),((5))2))) ZEE
2 (Ez [(AA(5)) + sup ((A)()),,,(()))2)) 2,2
Snc" <8ne 2nc*
(8)
where the first inequality follows from the Jensen's 's inequality and the definition of uniform stability, and where the second inequality also follows from the definition uniform stability.
From 8 we know that q is (8nc², 2m weakly self-bounded. Thus, by Lemma we obtain that with probability at least 8/3.
(1Nn: 4ne (og()))
log(3/6)
(B<TEA(U((4<<())44((()))))) 2 log (3/6)
16ne
1 1 + Sne² log(3/8), 4
where the last inequality follows from that vab < - for all a, >
Since Ez (,
MF (S)), we have
Es (0F2((74A445.4444077779999-44119 (S) 1 + 16ne log(3/8).
Substituting
9 into
we finally obtain that with probability at least 1 5, (()
F ((Ax(S),
(MF(AA(SS)A,(S)) _ + 32nc (3g(3/))) log(3/5) log(3/)))oo((3
n
2M log(3/6)
3n + 20c log, n log(3e/6).
(10)
According to inequalities vab S na + bb and Va Va for following inequality with probability at least 5 5 (SAx Ay (5))
for any a, 4,44 > 0, we have the
(# 22 + 32ne 10g( log(3/0)
n
(S) 1+ 4M 1og(3/8)
n
1+n
7
n
2M 2M log(3/0)
+ 50 500 n log(3e/6),
3n
which implics that
-
32nc (t02 (fe2+ +2ne log (3/5)) log(3/0) +
+ n 4M log(3/8)
<(1 +
n
"
n
2M log(3/5)
+
+ 50 log, ni log(3e/0)
3n
1 + M
<0
log(1/8) + c clog n log(1/0)
17 n
19

---

Published as a conference paper at ICLR 2022
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 w.r.t the perturbation of and y respectively.
(Zhang el al. 202 Let f: xxx y + R. Assume that I is pusttronglyccomves-srmgggyy concave. Suppose that for any x, x' X and y.y y' y we have
Lemma 5.
[x [x y))l 3 xxIl and VV - V Vx Blyy yyll
Define xy) arg minxex h(x,y) y) and yx) arg maxyey l(x,, y) for any y and x respec- tively. Then, for any x, x' X and y, E EY there holds that
3 xx-x11 Ixy - yx()ll s
3 lly y'll- and |xx x S
1
The proof of Part (b) shares similar proof techniques with Part (a), but requires a novel decompo- sition and several important changes. For instance, 55 should be needed to quantify the fact that for different (S))), the optimal y is different in (((A(())
Proof. Let S = f zn be a set of independent random variables each taking values in Z and S² = { } be its independent copy. For any i E [n]. define s(i) = {Zi,..., 2,-1,, 24, 21+1, ... 2nd be dataset by replacing the i-th sample in S with another i... sam-
ple z/. Denote y = arg maxyey (5)) and ys = arg maxyey (s(Ax y). We have the following decomposition
- (
-5) (. 2)1]
Be| (3) N'uo 2)1 - (((x(((()) ). xyu):
+ (A( (50)))0)))))))))0) Σ ((Ax(S),
(II)
Firstly, we have
- ((
=I(A - (S), 2) + ((Ax(S)) Ysoi 2) - ((A) Ysuss 2)
<111y's - Vosa |l (S) AS(0
<(1+ ( (s,
<(1 + ( Le. Lc.
(12)
where the second inequality follows from Lemma
5 with the fact that F is smooth and JCSC-SC
20

---

Published as a conference paper at ICLR 2022
Secondly, we have
((( +1) +5)
< Exg (1+ 3 L[)Ax(5) - Ax( + Σ (AA((S)
1=1 /1
" <(1+ () Tine [((A
i=1
where the first and the last inequalities follow from we obtain that
12
Substituting the above two results into
nF (A)( -PFs(Ax(S).83)
<2 1 + Lnc Σ f(Ax + Σ gi(S) Σ (Ax(5))
22 1 +
3 Lnn (S))
where the last inequality follows from the facts that (A))
Ei f(Ar 2,) S and that we have introduced g,(S) Ex ). 2)] ((A)
Now we get
(F) - (A) Σ (s) ( L Lnn.
(13)
For any I,..., n, we define h2(S) = g.( Es [
[S)]
We also get that [sy(==)) [S)] = 0 and E,, (S)] (9 (=: [s) 0-0 0. Moreover, for any j E [n] with j * i, and 2 E Z. we have the following incquality
[hv(8) - hi(2),, zz- 2/ 2j+1 ........ 2n)1 S 19:(S) gi(E1, ... Zj-1, 1, Fj+1s zn)l [Bs(=))oo Es((z)) (2, .... 25-1: 23 2j41, 2n]]
Denote 5100 the set collected by replacing the j-th element of 5(() with z/a. For the first term (g:(S) (.. Rj-1, 24/, 2j+1, ... 2x)], we have
9:(S) ge ge (.,,, 2j+1, zn)
E3 [EI]f(Ax Y:y 2)] [001-f(Ax(()) f(Ax( Y5012))
E.: [B2[f((AA
: 2)] (SA g00t
< R2g ())) Ygmi 2)] ((Ax(S)))) ), y 2)
+
E2y (S() ( ((Ax(S))) ggg0 24)
(14)
21

---

Published as a conference paper at ICLR 2022
Furthermore, for any 2, have the following result which help to bound the above inequality.
(( ((Ax(s))). ) g0112)
[(Ax(5 (5())) (1000i2)
((Ax(S()) y 5(0i2)
+ ((AA
((A
<4 1 -5000 + AL((00 )
3 +1 +1) Ax(S(()) - Ax())) ||
11
8 4 +1 +1)l,,
(15)
where the third inequality follows from Lemma Thus, we can bound the first term by 2 ( +1 Le. By a similar analysis, the second term [Es((.)) [s)( - Es (Z1, Zj-1, 2i+1 Zn can also be bounded by 2 _ p Le.
Rj+1,
We now have verified that the three conditions in Lemma 2 are satisfied for (s))). We obtain that for any p 2 there holds
Ar - 48 28m
2 +1) Le [lgg nl. P
(16)
Thus, combined 13 with 16 we derive that
(5) (Ax FA + Fs
(S) Σ (S) + Σ (i(S) Σ Es((t,)la((S))
< (4F Σ E + ||
<2(1 + 11
() Line 48 2 + 1) Le [oggn1 n1
1
<50 2 ( 1+ () cIpp 1og2 [.pplooggn) nl.
(17)
Then, according to Lemma for any d E (0, 1), with probability at least 1 8/3, we have
F(Ax(S), Fs(Ax
F(A Eg Fs
2ee (
( log, n1 log(3e/0). (18)
With a similar analysis to the proof of Part (a), we now begin to bound the variance of
Es (S")
E,, ((L()))
< Es, (ST(A 21))
EZEEs [E 2))
[2Es([f(A Z))
There holds that EslEs FA(x
F(Ax("S) (B .
Then, by the Bernstein inequality
in Lemma 4 we obtain that with probability at least 1 5/3,
|R F ((A,
Es Fs )1 2E (f(x
2)) (3/0)
2M 13g(3/6)
(19)
3n
22

---

Published as a conference paper at ICLR 2022
Combined 18 with 19
we finally obtain that with probability at least 28/33,
F(Ax(S), (S),
2E 2EgEs((fee (F(A 2)) log (3)
2M 2Ml (?)
+ 50 20el 3 [ogg2 nl log
3e
n
3n
8
(20)
In the following, we define q = q(=1, ... 2n) = [=x(((Ax(()) 2)) and = 9:(21, knd =
e ((21, ... 2n). So there holds di 9 for any 1,.., and any { 2n E 2 Also, there holds that
Σ 9 9:)²
(x(
sup (=(([((A((9))33)2))) =,EZ
Ez
sup
(f(A (I)
In 1) 2 (22 +1)
<8n _ 1 Lee²q 2n /
(2
2 ş +1) L'ed
where the first inequality follows from the Jensen's 's inequality and the second inequality follows from a similar analysis to 112 or 15). Now, we know that q is (8m ( + 1) T.ee² 2n ( + +1) -
weakly self-bounded Thus, by Lemma obtain the following inequality with probability at least 1 5/3.
2 16n 3 +1) 12 [= 4n
+
L(e*) log(3/8)
( +
3
2
[BEE)((((AA 2))1
4 1
12622
16n
+
L2e² log(3/0)
1 3
B
[EE2 Z))
+1) LZe2 + 8n
+ 1) 2 log(3/6),
4
where the last inequality follows from Vab < atb for all a. b 0.
2
Since E2((f(A 2)) (F(AA we have
Es -
s / +1)
2.e + 16n
_ /
+1) L 13g(3/
(21)
Plugging 21
into 20 we finally obtain that with probability least 1 5.
F(Ax(S), - FF(
(4)) { +1 T22 + 32n "
+ 1) 2 I log(3/5)) 1og(3/8)
2M 1og(3/8)
50 2 B+1
[log n log(3//)).
(22)
3n
23

---

Published as a conference paper at ICLR 2022
By the elementary inequalities vab na b and +b+ I va + vb for any a. a.b O,
have the following inequality with probability least 1
F(Ax - (1+ + F) - C + 17
M
[H +1 Le logg nog 2)
(
log
+
8
n
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 concen- tration inequality, which is a moment version of the Bernstein inequality.
Lemma 6. (Boucheron et al. 2013) If 21, ... In are i.i.d., zero mean and |as| S M almost surely.
Then, for any p 2 2,
> Ex? + 4pM.
24
S
Proof. Let 5 fzr..., 2n } be set of independent random variables each taking values in 3 and S¹ .z, 2 be its independent copy. For any i E [n], define s(i (Z1,..,, 21-1, z/, Zi+1, 2n be a dataset by replacing the i-th sample in S with another i.i.d. sample z/- Denote y3s arg maxyey (S)) y). Y's arg maxyey (S),) x's arg minxex F(x, (S)) and x3 arg minxex Fs Ax,
The proof of Part (c) requires a pretty technical error decomposition, i.e.,
A (Ax(5), (S))
=F(AA y's) inf F(x', Ay())
x'EX'
=F(Ax(S) Fs(Ax (S),
(.. 34041//399-...44.4...3---5--5-53 (B BBF((()))))
(o.F(xs,Ay(S)) Eg Fs Ax (S)) + (s(Ss, Ay()) - inf F(x', AS()))
XEE
- BB Ps Ay(5') BsP(x's Ay()))
+ (3) -
(S)).
Let's first consider the term (S), (5) + (s)))((A (5) It can be then decomposed into
yS) (S) +
E (()) 2)] - )g))
1 1 Ez (2(((A((S()))
), ysm Z)] (( (AA
(S))
which can be bounded by the proof techniques in the proof Part (b). According to we know that
(5) -
$50V2 2 1 cLpp n].
(23)
For the second term E AS)) Fs Ay()") + Ay()), infvex F(x', Ay())), we have the following decomposition nFs(K's Ay)) inf AS))
xeX
n
A Σ
Ez f(x Ay Z) (x 2
"
Ay A(((0)); E215(x3m; As(s (S( 2)]
-EE Ex [[x ((((9));))
Eg
1=1
24

---

Published as a conference paper at ICLR 2022
It is clear that
Σ Bal [xxss) Ay (y(())):
Bay Ay - /15
2nPs($5: Ay (5)) + Σ Eyy -
(24)
1=1
Denote 9:( = Eeg [ g(0) Ay Ay(5 );)) - [x[s st:) Ay() 2)]] By 24 we now get
n nFs (x5 Ay())
inf F(x', Ay(5) Σ 9:(
X'EX'
Ez (1x3) Z) - B2g 1f (x)))
500) Ay(s))):
Σ Rel A - -(ss) Ay();
Furthermore, according to Lemma 5 we have
((x5:AA(5)) 2) - f( (s()))); 2) S 5(1+ 3 L11As(5) - (s()))
/
Similarly,
Ay(S(0)) 25) - f(x') Ay(s); s x1+ 3 - (S())) (
Thus, we obtain
n Σ 9i(s)) 1=1
( - n inf
x'EX'
Σ 2 ( + ( (5) Ay(s) 2n (1 (1+ 9 Le,
(25)
where the last inequality follows from the definition of argument stability (Part of Definition 3) Furthermore, we define hx(8) (S) - E [S)]. For (S), We have Esy(2)) [S:( = 0
and 12, [S)] = Ex, [S:] - E., (s = 0 - 0 = O. Moreover, for any j E [n]] with j + i, and z!j E 2, we get
2/ Ihx(S) 2 2y.1, 2n)1 S 2 2
8 Le. p
where this inequality follows from a similar analysis (4p and (15) of the proof of Part (b). We thus can obtain that for any p 2 2, there holds
Σ m1)))), < 2pm
B + 1) Le [log n1.
(26)
Combined 25 with 26 we finally get the bound of the second term:
EsF(x', (S)) Es (x Ay()") (X Ay(S))
inf F(x', A,(S))
x'E
< A(())) X'EX
inf F(xx Ay - -
- (S)
Σ n
+
+
550v 1 /1
e.Ipp[oogz n].
(27)
25

---

Published as a conference paper at ICLR 2022
We then consider the third term -Es (Ax (4 Fx (S)). It is clear that Es Es Es Bs (isBBFFs((AA) (S",
Ay
= (x (S)) and
E5F (A)
Moreover, we having the following important property due to the strong convexity and strong con- cavity of F.
E ()) 23) ((A (s:
<' [ - Ax() + (S') ys-11)
$21.
S |||x3 + - 1
(F(A F(x), Ax Ax
F Ax())))
(28)
where the first inequality follows from Jensen's 's inequality and the Lipschitz continuity of f (As- sumption [). the second inequality follows from that (a + b)2 S 2a² + 212 and the third inequality follows from the property of strong convexity and strong concavity of and the optimality condi- tion, derived as follows,
F(Ax(S")) - F(xsr, Ax(5")) =F(Ax - F(xs V's)) + F (xx.).'))) Ax(3))
[1[ - -x'' + Ilyss Ax
is clear that IE[2 - -[[==1 < E|Z.J. Therefore, by the variance bound in (88 and apply-
ing the moment Bernstein inequality in Lemma 6 to the sum of independent random variables
-Es ( + +Eg f(xg.. Ay ( (()( Fxx (S)), we have
the following inequality for all 2,
Ess (AA())))))) + Es [xxr (F Fxs 4 (-11
4L2p
16pM
< 6 Es (F(A - F(x (s)))
np +
n
From Definition 1 know that the last term Fs(Ax(S), - A3($);A((S)) is actually the strong PD empirical risk 43 Ay
Based on the above analysis, we have derived that for each p 2,
(()) - inf F(x,, A5)) - (3( (S), Ay Ay()
xEX
PL2
+ 16pM
/ Es (F((((x(S")) - F(x;, (s)))
+ 100
1 w
n]
71p1
< " Es E (AA) F(X Ax(S)))]
+ n 12pL2
16pM
$ +
nu
n
2 () eLpplog2 n²]
+ 100 2 1
(29)
where the last inequality holds since for any a, b,b,,) > 0, Vab S na 1
Taking p = 2 and using the Sauchy-Schwer inequality, we obtain that inf F(x', A, - (3) Es ((Ax
X'X
F ((),
inf A(x',A((5)) Ay())) Ag(AA Ay())l X'EX
< 17 Es [F(Ax(S)) - 11
1 24L2
32M
77 Tu
+ 200V2(1 (1 19) 11
CL n].
26

---

Published as a conference paper at ICLR 2022
Since (s)(F(4((S). - (x ES)F(4A(S)) F(x3, finally get
(S)) inf F Ay() x'X
s(1 + m) Es 43 (A,(S), + 21T.2 + +))
32M 200 ( el
mun +
n
Plugging this incquality into 29 we thus have that for each p 2 2,
(()
inf X'EX'
F(x', A,(S)) 43(4 Ay()
S1 Es A5 (Ax(5), AS)) + 24L3 32M + 20002(
+ - n ) eo ml
+ 12pl2(1 7)
16pM + 100
2(1+ 1+ 1000
cLp logg nl.
n
According to Lemma
for any 8 0, with probability least 1 6, there holds that
inf F(x', AS)) - (5) + nBs A Ay) (S)
x'EX
(2(1+))
M + 1+ 3 (1+ log log, n) log (5)
+ C(1 + m)
(30)
where > 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 (30p in the proof of Part (c), we know that for any d > 0, with probability at least 1 1- there holds that
6,
A (Ax(S),
(3)
=F(A
inf Flx,,yy8) (S), x'EX
SnES 4 (Ax (S)) + C(L+
(.2(1 + +n) n)
+
M
+
(1+
3 ( EL logg n) log (t)
eo
n
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 minxex R(x) and y arg maxycy (S), Firstly, we have the following decomposition
R(Ax(S)) - inf R(x') = R(Ax(S)) (s(AA(())) + X
- - + Fs(x", Ay(S)) F(x", Ay()) + F(x" AS)) - R(x*). (31)
Consider the first term R(Ax(S)) (S)) From 22 of the Part (b), we know that with probability least 1 5,
2M log(3/0)
+ 2eeL 3 + 1 [lgg n log(3e/8)
R(Ax(S)) Rs(AA(S)) <
3n
r
+ (M))
= +1
2
122 + 32m ( (*+1) 12 log(3/0) log(3/8)
n
27

---

Published as a conference paper at ICLR 2022
For the second term Rs(Ax(S)) - Fs(x', (S)). have Rs(Ax(5)) Fs(x", Ayyx"))y(s)) 1 Rs(Ax(()) - in Fs(x' Ay(S)) = (5)
Note that under Assumption the argument stability implies the uniform stability. Therefore, for the third term Fs(x*, A (5)) Fxx" Ay (5)), from 10 of Part (a), we know that with probability at least 1 δ
2M log(3/8) + 50 5 (log2 n log(3e/))
"s(x""Ay(8) F(x', Ay()))
3n
(AMF(x Ay(S)) ]e² 32me log(3/)))og(3//)
S. Since F(x", (S()) I supy F(x",'' = R(x*) = in R(x), based on the above results, have the following inequality with probability at least 28
is clear that Fxx",
R(Ax(S)) - inf R(x) X'E
(M) + + +1) 2
L222 32n ( + L log(3/0) log(3/6)
n
4M log(3/8)
(4M infxex R(x) + fe² + 32ne
+
3n
B + 1t
+ 22eL
[log2 n log(3e/0) (5) + 50v 2ee [log ni log(3e/0)
1
1 ( +1 L + 32n ( +1
2 log(3/6) log(3/8)
1J (()
n
1+
1 + 4M log(3/8)
4M log(3/8)
(ge2 + 32me (og(3/)) log(3/5)
1
3n
+ 1 + 1)
17
inf R(x)= +
1 1 4M (3//)
E'EX
"
B + # [log2 n| log(3e/8) + 20el.
+ 5002ee 20elog
ni] log(3e/6)
1b
where the last inequality follows from the elementary inequalities vab s na + 1 and va+b= s Va + Vb for any a, 5 > 0. Therefore, by a rearrangement, we have the following inequality with probability least 1
R(Ax(S)) - (1 + 2n) inf R(x)
x'EX
<0
1 + 17
log
1
+
B
+
LE Lelog log, log
1 (38(4(())
that is
R(Ax - (1 + 17) inf R(x)
x'EX
<C 2 + M
log
1
(L
1)) Le
+
1 Lo log,
log 3 + (S),
3
where C absolute constant. The proof is complete.
Till here, the proof of Theorem 1 is complete.
28

---

Published as a conference paper at ICLR 2022
B EMPIRICAL SADDLE POINT
Empirical saddle point (ESP) problem refers problem which is also known sample average
approximation (SAA) (Zhang et al., 2021a). We denote (x V3) as the ESP solution to (2), which analogy 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 2, the function (x, + f(x.y; is p-SC-SC. Suppose y(x, y) S M for some M > and x E X. E V, E Z. Denote Ax(S) X3s and Ay Y's for (Kg. Fixed any 1j > O. There exists an absolute positive constant C.
(a) If Assumption 7 holds, then for any 8 O, with probability least 6, we have
F(85,83) S (1 Fs 93) + C 1 + (M
4L ( log(1/0)
logg log(1/8))
"
mp
(b) If Assumptions and hold, then for any 8 O, with probability least 6, we have
R(x3) < (1 Rs + 1+
M
log + - ( +(+1)
4L2
log, n log 2)
7 n
4
my
(c) If Assumptions 2 [and] hold, then for any 8 O, with probability least 1 - 8, we have
A'(8g. C(1 + m)
( 1.2(1 + n)
M
(1+
3 4T. logz n log (c)-
+
npn
n
p np
(d) If Assumptions 7 andd) hold, then for any 5 > 0, with probability at least 8, we have
! (x$. A3(
<C(1+ + 7)
[12 +n)
+ M
+ (1 (1+
4I2 log, n log (t))
/
(e) If Assumptions 7 andd] hold, then for any 8 0, with probability least 1 - 8, we have
R(x3) (1 7) inf R(x) + C 2+ 17
M 1 3
( +=+1 +1) 1
4L2
log, log 2
log
+
nu
we should derive the strong PD empirical risk bound and the stability bound of (3). It is easy verify that (g( 0 ZZhang al. 2021a). We then investigate the stability bound of (8),88).
Proof. To prove Theorem 3
Let S (z1, ..., 2n} be a of independent random variables each taking values in Z. For any i E [n], define 5(6) (z1,..,, 2;-1, 2/. -..,...,,_] be dataset by replacing the i-th sample in S with another i..dd. sample 2/. We define Fsu be the empirical risk on dataset ((A) and define (o > ) be the ESP solution on dataset S(1)
29

---

Published as a conference paper at ICLR 2022
Then we have
gs( - (s.
f(x3.
n ==1
(3:2)) - (switz)) + f(x50: 93: - fxxs Sss z/)
(f(Sg() Si: (f)izs>>((((aa ( Vinn 11550)35:4 - f(85s Y'snt 2))
n.
=F Esto (Kgrn: 3's F() (x5. y s'm)
1 n
( z1) [X ysi zi) (155 & &3()):
- (J(S Vsi #4) (x yoi z/) + [(xg W3i f(X y gass =())
2L
SFst (Xg() (3)) g() (xg, ygos)
| 51 8sll + 1 - Soo Il)
-Fsco (Xg(0))) (z)())33))) v's) Fs (x go) y Fso) + Fs gin
gighn - Fs (x5. Ks0))
2L
+
(1|* - -x5ll + l1yss - -s
S 2 XSs
11
x r 1y's
ysw 112
2L n
(1 - * + 1y's y II).
where the first inequality follows from the Lipsehitz continuous assumption, and where the second inequality follows from the facts that the p-SC-SC property of Psco and (& x 8ow) is the ESP solution of ggt.
Similarly, according to the --SCC-CC property of Fs. we have
Fs( V3)) Fs Fsu)) = FFs Y's) (s( V') + Fs 93) - Fs(83, goo))
11 - x511 + 2 11l93 - 9 12
(32)
Based on the above results, we have
14 8 300
13,12 2 + nlll's ysos 11
2L
(11550))
- x3ا1 + 1 - Ysolll Il)
2L
/
|8500 x2 + |زا3 St 113
where the last inequality uses the Caucy-Schwarz inequality. Therefore, we have
|850
*311 + 1195 Ysuol |I
/211 - 853 22 + 1 - y3
4L
(33)
np
Now, plugging this stability bound into Theorem 1 we obtain generalization bounds of the ESP complete.
solution. The proof of Theorem 3
D
Remark 8. When conditions in Theorem 3 hold, we obtain that (a) If Assumption holds and
Fs 83) = O (+)) then for any O, with probability at least 1 6, the plain generalization error of (xg. 8's) is of the order O log, Log(1/))). (b) If Assumptions and hold and Rs(xg) =
;. then for any 5 > O, with probability at least - 6, the primal generalization error of
30

---

Published as a conference paper at ICLR 2022
log(1/8)) (c) If Assumptions and 2 hold, then for any O, with probability at least 8, the strong PD population risk and the strong PD generalization error of (8g.8g) are all of the order O lugz log(1/6)). (d) If Assumptions and 2 hold and
(x3,33 is of the order O lox,
infxex R(x) o -(+). then for any > 0, with probability at least 1 8, the excess primal population risk of Yz) is of the order O losg log(1/6))
Remark 9. (Zhang et al. 2021a) also studies the generalization bound of the ESP solution. They provide (1/nn) 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 an- alyze than the former. They have to consider the fact that different X3 corresponds to different y, as discussed in Remark 5 Moreover, the expectation operator in expected strong PD popula- tion risk also relaxes the difficulty of proof. Specifically, define S(i) be dataset by replacing the i-th sample in S with another i.i.d. sample z/ and y" y'(x) = arg maxyey F(x, y). there holds the following important property E [suPyey F(X'. y)]
n E. (F($so gtn ( ))]
E.= EE ((ngnn"""" y" (Xg()):; ); 2:)] because (Xg, (Xg)) and (& y" s(a)) )) are identically dis- tributed and the independence between and S10), On the contrary, when there is no expectation operator, we do not have this property and the proof is much more challenging.
C GRADIENT DESCENT ASCENT
We need some notations state results on GDA. Specifically, assume the initial point satisfies X1 = 0 and yı = O. Let }np} be sequence of positive step sizes. At the t-th iteration, GDA updates
X++1 = X 7t xx),
Yi+1 y: + ni Fs
(34)
We denote the average of iterates by
E
X and Yr
Ee T
XT
(35)
T
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 E [n], define 5(i) (21....,2-1) 2/, 2++1.... Zn) Let (x, be the output produced by Fs on dataset S in running a minimax learning algorithm. Let (x.. be the corre- sponding output produced by Fgga on dataset 5(6,, where Fgu) is empirical risk on dataset 5ti) Suppose Assumption 7 holds. Assume for all 2, the function (x,y) f(x,y;2) is y-SC-SC For any 5t) and S. we have
4L np +
| x + I1yi yell S
1 (x).
Proof. Define (x ste y s(n) on dataset S. To prove stability bound, we consider
be the ESP solution on dataset 5(i) and (3) be the ESP solution
x x + lyf yell
i 8ys0
+ +x - Xt's + +X - xill + Ilxi - Vis + +ig - ys + yell
< i &gco + ||8 -3'll + || - xell + Ily! Sg Il + ||9 -311 + 1 y.ll
4L
||x - 11 + || - x + lly: لل || + ||8 - yrll
4L
22 V | 11 llył و 1|2 + v2 |183 y:112 + || x, 1|
ni
AL
V
Fsco (0 vt) +
4
Fs(x V3)) Fs Yt),
ni
31

---

Published as a conference paper at ICLR 2022
where the second inequality uses the result in (33), the third inequality uses the Caucy-Schware inequality, and the last inequality uses the strong convexity and strong concavity of F and Fs and the optimality condition (please refer to (32). ). As will see in the rest paper, we bound F (x; gon) - Fo - s(a)) and (x(,,, yg) Fs (x yt) with the same upper bound since they are all strong PD empirical risk. Thus, for brevity, we derive the following inequality
||
X + 1 yell
4L
1
+ 41
Fs Fx( v8)
ny
μ
4L
I V (x..
+ A
nu
The proof is complete.
Remark 10. Lemma 7 provides the connection between the stability bound and the strong PD em- pirical risk. The subscript 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. (02I), 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 order (11 / /n). To derive sharper stability bounds, we established Lemma
The following lemma shows the strong PD empirical risk of GDA.
Lemma 8. Suppose Assumption [ holds and Es(:,-) be p-SC-SC with > O. Let Ne) be the sequence produced by 34 with 1)t
p Assume to 2 0. Suppose supxex ||*|| S Rx and
supyey ||yl| S Ry. Then for &T.VT) in 35
we have
ulo (13 +2G) T
L (olg((eT)
sup Fs(XT,y) inf Fs(x, yEy
XEX
nT
If to = 0, then
1 log(eT)
sup Fs((r.y) yEy
inf Fs(x, S XEX
NT
Proof.
Firstly, we have
[|x41 - x|| =
xx: - 7/ XxF's(x - x|1
xx - x|| 2| + n/ V Fs( (X yz 112 2n/ (x- Xx, VxPs(x).
< Ix - x|1 + ny 2 + 21 (x
Xt, Fx yt)).
where the first inequality holds because of Assumption I have
By the strong convexity of Fs)...)) we
2ny (Fs((F v.) Fs(x,y:)) S - x|12 || x||² + n/² 1.2
Since n = [. we further get
2 (F)( Fs(x, vt)) < (1 (1-
1
||x, -x--xx x112 -|x - x112+ + (wit+ to) )²
1
)²12. L2
ptt + to)
(t + to)
Multiplying both sides by t to, we have
2 (Fs(xx.))) Fs(x,y.)) S (t to 1)][x; x|| (t+ (o))o)||x4+1 - x112 + 112 + to)
I
32

---

Published as a conference paper at ICLR 2022
Since X1 = 0 and El= t- I log(eT)) by taking summation of the above inequality from t to T, we obtain
T
1 log(eT)
Σ (Fs( - Fs(x,y.)) - " RRx
1
2
2
From the concavity of Fs(x,)) we get
L log(eT)
toll'3
2μ
Since this inequality holds for any x, we get
inf Fx(x S 10 + (Fs((x.))))
T
M
L log(eT))
XEX
2/
This implies that
T - inf Fs(x,)r)) S 1t 2T
L log(eT))
(F
+
T
XEX
2pT
In a similar way, we have the following inequality
1
1do R2
L log(eT))
sup y))
Σ
(Fs(x., <
yey
T
2T
2μT
1=1
Combined the above two inequalities together we get
udo (133 R2)
L Pog(eT))
sup Fs(Xr.y) inf Fx)
yEy
xEX
T
nT
For optimization algorithm GDA, substituting the strong PD empirical risk bound (Xy.yr) into we get the following stability bound,
Lemma 7
4L
|SSt xrll + lyy
Fr
+
4
Ag(xr,
4L
T
plo +12g)
L logeeT)
<
+
AV
T. +
(36)
ni
nT
Furthermore, for any x E X. and = Z,
f(x,y:2) f(0 2) < L|[x 0|1
Llyy 011 S L(Ry + Ry),
which implies that
f(x,y;z) sup /(0,0; L Ry). =E2
(37)
Till here, plugging 37}. the stability bound in (36 and the strong PD empirical risk bound in Lemma
g
into Theorem
we obtain generalization bounds of GDA.
We now write the main theorem of GDA.
Theorem 4. Assume for all the function (x, f(x, y; z) p-SC-SC. Suppose supxex ||x| <
Rx and supyey ||y|| < Ry. Let (x,, y.) be produced by (34 with nh p[[+t]] Assume to 2 0. Denote (S) = Ry and (S) = Vr for (Xr.yr) in (35). Let M = sup f(0,0; L
Ry.. Fixed any 0. There exists absolute positive constant C.
33

---

Published as a conference paper at ICLR 2022
(a) If A holls, then for any 8 O, with probability at least 8, we have
F F(Tr.TT) - (1+ (XT,
1 M C
1
1o8(1/8) +
AI. mp
+ =44 V=
udol u (R&
R2.))
12 12log(eT))
log, log(1/6))
7 n
T
μ.
(b) If Assumptions
andd
hold, then any ō > O, with probability at least - 6, we have
+
R(xT) (1 7)
C
M log
B + 11
4L 4
pto(It + +R3)
1,2 log(eT)
1 3) log, n log
x
+
7
T
nT
(c) If Assumptions
andd] 2 hold, then for any 8 >> O, with probability at least 1 - 8, we have
plo
+
Ry
L log(eT))
4 (XT, ((T, S (1+m))
+ +C(1+
T
M B + μ m1++m)
AL T1
I
plo
(R& +Rz)
L (Zlog(eT)) L. m1 log (t))
mmm
n
1
+4
V
T
μT
(d) If Assumptions
andd 2
hold, then for any 5 > 0. with probability at least 8, we have
pitol R + R2
I.2 log(eT)
! (x)
(xr, S
+ +C(++
T
n²
(1(++n)
M B + 1
AL
I
pto pto
RRx
R2y)
La Lolog(eTT)
L loga n log (t)
+4
mmm
T
μT
(e) If Assumptions Madd] hold, thenfor any 8 O, with probability least 1 8, we have
R(XT) S (1+1) 17) inf R(x) + c +
2+
ptoo Rxx
R2y)
L log(eT)
+
XEX
T
WT
+0 2 + 11 M
AL ((+1)
(
pllo Ryy R2))
+ 1 log(eT)
log, n log )
log J
ni
jt
T
Remark 12. When conditions in Theorem 4 hold, obtain that (a) If Assumption
| holds and Fs(XT, ( then for any 5 > 0, with probability at least - 5, the plain generalization
error of (KT. of GDA of the order o ((+ 1 log log2 n log((/))) (b) If Assumptions
and 2 hold and Rs (xT) o (+). then for any 8 > with probability least 1 8, the primal
generalization eтror of (Xr, Fr) of GDA is of the order o ((22 Tog log, n log(1/6)) (c) Assumptions and 2 hold, then for any > O, with probability at least 8, the strong PD population risk and the strong PD generalization error of Vr) of GDA are all of the order
((L
and hold and infxex R(x) o then for any 8 0. with probability least 1 - 8, the excess primal population risk of (Xr, Fr) log, log(1/)) For the above bounds, we can take
T
log2 log(1/6) (d) If Assumptions
R
of GDA is of the order ((+ T
+
= Onn²) gradient evaluations to get bound of the order O 2/2 n log log(1/6))
D STOCHASTIC GRADIENT DESCENT ASCENT
We need some notations to state results on SGDA. Specifically, assume the initial point satisfies x1 0 and yı 0. Let (n.) be sequence of positive step sizes. At the 1-th iteration, SGDA
34

---

Published as a conference paper at ICLR 2022
first randomly select an index in form the uniform distribution over [n] == {1, n) and then do the update
X(+1 = x; - 7/ (x, y1, zi,), Y(+1 y: 7/: V. yx, 24,).
(38)
We denote the average of iterates by
XT Ll x
and Yr Eim Yt T
(39)
T
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 al. 2013) Let 21,-.-27 2n be sequence of random variables such that 2i may depend the previous variables 21,..., 2k-1 for all 1,..., n. Consider a sequence of functionals Ex(21,... .... 24), k = 1, ..... n. Assume 15x- Esg [5x] by for each k. Let 5 (0,1). With probability at least - 8
1
a
n b log ))
Σ 1=1
Ek
E EE
2
k=1
Lemma 10. (Tarres & Yao 2014
Let (Ex be martingale difference sequence in IR Suppose
that almost surely ||E& S D and Ek= 1 Ex....e-111)) S of. Then, for any 0 < 5 < 1, the
following inequality holds with probability at least 1
D 3
2 log
max ISJSI
Σ Sx
< 2
0z
8
The following lemma shows the strong PD empirical risk bound of SGDA.
Lemma 11. Suppose Assumption
7 holds and Fs(:;)) :) be P-SC-SC with μ > O. Let (xt,yt} } be the
sequence produced by 338) with 7)t m((+to)' Assume to O. Suppose supxex ||x|| S Rx and
supyey || & Ry. Letd > O. Then for (RT. VT) in 139 with probability at least - 8 we have
2pto (R2- +R2)
L log(eT)
sup (x( inf Fs(x, yEy
I
xEX
T
uT
2(Rx + Ry)
(2 (
6 +
2 Ry (2T log(6/8))
+ 22VT
log
T
3
T
If to = 0, then with probability at least 1 we have
1 log(eT)
2(Rx + Ry)
2L
log 6
sup Fs( - inf Fs(x,,)) yEy
+ 22LTT
xEX
μT
T
3
2L(Rx + Ry R2T log(
T
Proof. This proof follows from
Lei et al. 2021). Firstly, we have
||x+1 x| |xx, T/e Vxf Yei 2. x||
||x; x|2 + vリ²" VV yo; 2m, (x x1, V Vxf(Xx. yo 21,)
||x: 1x-xa x||² ? 2 + 21,, (x Xx, V (ti,
V Vx (xt, + 2n. Xx, VxF' Ux ve)),
where the first inequality holds because of Assumption have
By the strong convexity of Fs(:; ye),
(Fs(x..)) - Fs(x,y))) $ (1 mx)]lx - x||2 ||x+11 - xx|2 +1
+2 Xt, VxI VxFs(xe, Yt))
35

---

Published as a conference paper at ICLR 2022
Since 7)- u(ttta))' further get
2
(X) - Fs((,).)) s (1-
(t to) )l,)l1x ||x, x1|²- -1|x x|1
1
plt to)
+ uut + to)
(mit=
1
2
I2² +
2
(x (x-X Xx, (x Vei (xF5(x(,)1))
u(t + to)
Multiplying both sides by t + to, we have
2 (B3(xx.))))-(xxx..))) +o to- 1)(lx; x11 (t+ 1x) - x11² 12:(1 - 10)
L²
Fs(x.
2 + (x xx, Vxf (xi, V Vxl'((x1) Yr))
/
Since x = 0 and Σ t- S log(ee))), by taking a summation of the above inequality from t =
T. we obtain
T
- -F((xx))))) 1 11 Ro +
1,2 log(eTT
2p
T
+
x (xf(X))1111)) - VxFs(X,, +
Σ xx, (xFs(x..Nt) - (xf(x),)1522))
From the concavity of -) we get
(F Fs(x, S H Rx + L'
2
24
t=1
Σ xx (x
Vx -V
Σ (2,, Vx - Mx)
Since this inequality holds for any x, we get
1 (og((eT)
v.) inf Fs(x, Fr)) S 2 Rx
+
xEX
24
Σ (x, (x, Vx Ps
Σ (2,, (xP3(X(,))) - vxx())
xEX
By Schwarz's inequality, we have
Σ (Fs((t)01)) - inf Fs((, < 41 Ro +
T
L log(eT)
XEX
2p
1=1
+ Rx] Σ [x(((x - VxP'
ve)i| + Σ (x1, (xP - V
Denote & = (xt, (xF.
(x;
Since
Ex,, VxFs(xi, yt)
(x,(x,, O, [.,L = 1,..,, T) is a martingale difference sequence. By Schwarz's
inequality and Assumption Then, according Lemma
we know that [xx,, VxFs(x,,y)) Vxf(xe, yes 21)) < 2LRx.
we have the following inequality with probability at least 8/6
T Xxx (xlF((x.)1) (x. < (2T
Σ 1=1
Define g: (xI
Fs yz). Then we get |&| S 2L and
Σ 1 4TL2.
36

---

Published as a conference paper at ICLR 2022
Applying Lemma 10 to the martingale difference sequence (E/), have the following inequality with probability at least 6/3
Σ
E
<
2L + 22VTT log
6
That is, with probability at least 1 - 5/3
Σ (x Vx vo)
$2(
2
2LVT) log 6 g
Combined with the above results, we finally have the following inequality with probability at least 1 - 6/2
T
pdg Rd
1.2 loge(T)
Ys)
- inf Fs(x. (T)) <
+
T
XEX
2T
2pT
2Rx (2 ( 22LTT) log
6
2LRx (2T (og(//0))
In similar way, we have the following inequality with probability at least 1 5/2
T
utol
L log(ee))
sup vey
(s((T,))
- Σ
(Fs(
2T
2n²
2RY 2L
6
2L (2T log(6/6))
2LVT)
log g
T
Combined the above two inequalities together we get the result with probability at least 5
plo R2x
+
R2y)
I,2 log(eT)
sup Fs(Xr,y)
inf Fs(x, XEX
yEy
T
nT
Rxx + Ry)
2T
6 +
Rx + Ry (27 log (6/0))
+ T
+ 2LVT
log
3
T
Denote E
plu 1 n2
L log(eT)
2 + ny X2 +2L. T log
+ 2L(Rx ny (27 ()g(6)))
T
T
Now, plugging Lemma II to Lemmal we know that the argument stability bound of SGDA is
|| Xrll + Ily Frll S
4L + / f / Ag(xx. 3r) S $/ T
/ V
4L
(40)
nu
Furthermore, for any x E X. y and 2 E Z,
f(x,y; - f(0 2) + L| x 0|l + L|ly 0ll < sup f(0,0: + L(Rx + Ry), 2E2
(41)
Note that since SGDA is randomized algorithm, thus we need the following variant of Theorem] Theorem 5. Let A be a randomized learning algorithm and > O. Suppose (f( & M for
some M. O and X,y V, E 2. Fixed any rj 0. There exists absolute positive constant C.
(a.) A has e-uniform stability with probability least 8' for some 8' (0,1) over the randomness of A, i.e.
Pra sup AA)))
Se.
And if the randomness of A independent the training set S. Then for any 8 0, with probability at least - 8,
M ((A, Ay))) & (1 ())((4(()))) + 1 ( log(1/8) + clogg n log ))
37

---

1 +1+ ( log, log 3 + 43(AA(()) Published as a conference paper at ICLR 2022
(b.) Assume that for all x. the function F'x.y) is p-strongly-concave Suppose Assumptions
7 and [2) hold. If the algorithm A is e-argument stable with probability at least 1 - 8' for some 8' E (0,1) over the randommess of A, i.e.,
Pr (1 (1Ax(()) Ax +1 -1 Sc.
And if the randomness of A is independent of the training set S. Then for any 5 > O, with probability at least
R(Ax(S)) S (1 ()Rs(A((S)) + C C log 8
1 + ( + logg n log
1 5)
(c.) Assume that for all and y, the function F(x, y) is P-SC-SC. Suppose Assumptions hold. If the algorithm A is c-argument stable with probability at least 5' for some 5' E (0. over the randomness of A. i.e.
7 and
Ax() PRA (11A)(5)))) (x(() 11,((5)
(y(1)) (1((())))($(1))) Sc.
And the randomness of A is independent the training set S. Then for any 8 > O, with probability at least - -6
A (Ax(S). S (3), nnS A$ (Ax
( ( n)
M + (1+ e loga n log (7)
+ +C(1 7)
mul
(d.) Assume that for all and y, the function F(x,y) is W-SC-SC. Suppose Assumptions 7 and hold. If the algorithu A is e-argument stable with probability at least 8' for some d' E (0, over the randomness of A. i.e.
Pr (1Ax(() + - (s("))
Se.
And if the randomness of A is independent of the training set S. Then for any 5 > O, with probability at least 8,
A (A,(S),
(5(A (5(A))))))A(((5)))))
S 1) AS (Ax(S),
+ +C m) (.(1+ n)
M
+ (1+ e logg n log (t))
[
n
(e.) Assume that for all x, the function y + y) is p-strongly-comcave. Suppose Assumptions and [2) hold. If the algorithm A is e-argument stable with probability at least 1 - for some
8 E (0, over the randomness of A, i.e.,
PrA (IAx(S) Ax(S')I + [[A((S) Ay(S))l) Sc.
And if the randomness of A is independent of the training set S. Then for any 5 > 0, with probability least
R(Ax(S)) (1 77) inf R(x)
xEX
+ C
2
1
M
1 log
7
Therefore, plugging 41 the stability bound in (40 and the strong PD empirical risk bound in Lemma into Theorem we obtain generalization bounds of SGDA. Now, we write the main theorem of SGDA as follows.
Theorem 6. Assume for all 2, the function (x,y) + f(x, 2) is P-SC-SC. Suppose supxex ||x| S Rx and supyey ||yll Ry. Let {t) be produced by (38) with the 1/(plt + (o)). Assume
to 2 0. Denote (x Xr and AS(S) ýr for (XT. Yr) in 39 Fixed any n > 0. Let
38

---

Published as a conference paper at ICLR 2022
M = 22 2(0,0;2) + L(Rx + Ry). Let ptal u (RR
+R3) 1.2 log(eT)
2 2(xx Ry)
(3z
p
T
2LVT) log g 2 Ry X27 (2716)(6/6) and B
ni +AV VE.. There exists an absolute positive
constant C.
(a) If Assumption D holdds then for any 5 O, with probability least 25, we have
M log (1/(1/8) + - logg n log(1/6))
F(XT, (1 (x ST)
(b) If Assumptions 7 aand hold, then for any 6 > O, with probability at least 20, we have
R(xT)= S (1 ())(((T)) + C + M
log + (Hr + LB
LB log2 n log )
(c) If Assumptions (attippttiioana222 2 then any O, with probability at least
26, we have
[1+ ( + M
3 () BL logg ni log + (1+
& A E (1+ C(1+
mmn
(d) If Assumptions ladd hold, then for any ö > O, with probability least
20, we have
A (XT, (3((x.
SnE+ + +n) (
( (11++)
+ M + +11 ( BL loga n log (3)
(e) If Assumptions [and] hold, then any O, with probability least 28, we have
R(xT) < (1++)) +1) inf R(x) C 2 2+ 1) M log 1=++1 [++)LBBogg, n log E
xEX
" m 8
Remark 13. When conditions in Theorem 6 hold, obtain that (a) If Assumption I holds and Fs(XT,
0 ( then for any > 0, with probability at least - the plain gen-
eralization eπror of (Kr.TT) Vr) of SGDA is of the order ((+ ++ /o0(1//1 log, n log(1/)))
o (A)). then for any 5 O, with prob- the primal generalization error of (Xr, Fr) of SGDA is of the order
(b) If Assumptions and 2 hold and Rs(Xr)
ability at least log, log(1/5)). (c) If Assumptions and hold, then for any d > O. with probability at least 8, the strong PD population risk and strong PD generalization error of T log2 log((/))) (d) If Assumptions excess [og( log, n log log(1/))) T
[og] T
(XT. Fr) of SGDA are all the order O
((+
[og(1/8)
and hold and infxex R(x) = O(t). then for any > with probability at least
primal population risk of (Xr.yr) of SGDA is the order O ((:
For the above bounds, we can take T Onn*) stochastic gradient evaluations to get bound of the order log log (1/6)).
E PROXIMAL POINT METHOD
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 (x), The averaged iterate is defined as
1
XT
x
and
Fr
ye. 1=1
(42)
T
T
1=1
39

---

Published as a conference paper at ICLR 2022
Given stepsize parameter v, the PPM generates the iterate Ne41l by
1
arg min arg max Fs(x.y) xEx
||x
xx1l
lly
yell
(43)
yEy
2v
2v
1Sc+1-Y441 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). can be written as
the update of PPM
Xx+1 = X vV (x Y1+1 y: vV v Yc-)):
(44)
Assume that the initial point satisfies Xo 0 and Yo = 0.
We now begin to prove the strong PD empirical risk. Firstly, two lemmas are introduced.
Lemma 12. Nemirovski 2005) Define vector yx E IR2d and the operator P RR2d R22d as
(45)
Consider (xr- in 42 Suppose the ESP solution exists. Assume the function Fs(x, y) is continuously differentiable in and Assume that Fs(x,y) is convex function of x for any and is a concave function of y for any x. Then for any x y] E RRdd, we have
T S T
Fs(XT. Ps(x,) Ps(x,
(v..)
E=1
Lemma 13. Mokkhari et al. following update
2019) Consider the sequence of iterates (ve} Rd2d generated by the
Vi+1 = -
where monotone and Lipschitz continuous operator, and v is a positive constant. Then for any v E Rd2d and for each 2 1 we have
(e44))((ve+ - v) 2v Vv.
v/I2
V1+1
v/2 [|ve++1 vvll2.
2v
The following lemma is the strong PD empirical risk bound of PPM.
Lemma 14. Let (x1, Yı } be the iterates generated PPM in (44). Assume v is positive constant.
Suppose the ESP solution exists. Assume that Fs(x,y) y) is convex function of x for any and
concave function of y for any x. Suppose supxex [|x] < Rx and supyey llyl S Ry. If
Assumption 2 holds, then for all T T21 1, we have
R + Ry
sup F) inf Fs(x, yey
xex
2//
Proof. The update of the PPM in (44) be written
Vi+1 V, vP((v+1).
According to Lemma in (Mokhtari et al. 2019 if Fs(x. y) is convex-concave and Assumption holds, then P(v) defined in (45) is monotone and Lipschitz continuous. According to Lemma 13 we have
1 V. v/12
P(v (v - v)
V v
|| v.ll2.
2v
2
2v
Taking a summation of the above inequality from = to T 1, we obtain
P(ye41) -v)
2v Vo v112
V/ v/1
(46)
2v
40

---

Published as a conference paper at ICLR 2022
According to (66 we know that
1 P(yer))((ve -v)
20 llvo - vv12
2v
X1o0 - x x|1 + llyo - y12
2v
Combined this result with Lemmal 12 we can write
||x0 - 6010-212-0 + lIyo - -11
Fs(Xr.y) Fx(x,F))
2v'
which implies that
B2 + R2
inf Fs(x, sup Fs( yEy
S
XEX
2/T
The proof is complete.
Combined Lemma 7 and Lemma 14
we know that the argument stability bound of PPM is
4L
|| Xr + 1y - Sr S
4
Ag(XT.
ri41
4T
T
R + RG
(47)
ny
2vT
Furthermore, for any E X. y and Z,
f(x,y; (0) + L| 0|l + D|yy 0|| s sup f(0 0: 2) L(Rx + Ry), 2E2
(48)
Therefore, plugging (48). the stability bound in (47 and the strong PD empirical risk bound in Lemma 14 into Theorem we obtain generalization bounds of PPM, shown as below.
Theorem 7. Assume for all z, the function (x, y) + f(x, y; z) is p-SC-SC. Suppose supxex ||x|| S Rx and supyey lyll I Ry. Let {x,, yı} be produced by (44) Assume is positive
stant. Denote (S ÄT and AS( yT for (XT, in 42 Fixed any 0. Let
M sup+E2 20),0; + L(Rx + Ry). Let E= an absolute positive constant C.
n and B
AL
+ 1 VVV. There exists mp
20T
(a) If Assumptions 7 and 2 hold, then for any 5 O, with probability at least 8, we have
F(XT,3T) (1 F)FFFFFsr..... Fr) + C + M
log(1/6) + 1 log, n log(1/))
1)
(b) If Assumptions 7 Hand hold, then for any 5 >> O, with probubility at least - 8, we have
R(x)) S (1 Rs + C 1 + M
log + (E) (=+1)LBlog log, n logg )
17
(c) If Assumptions [ [and hold, for any 8 > O, with probability at least - 8, we have
[.2 + 1)
M
+ +++
3 P
BL n) log (t)
A ('(8r,81) < (1 +)+
mum
n
(d) If Assumptions and 2
hold, then for any 5 > 0, with probubility at least 1 8, we have
A (XT, (8T
+ m))
(1(++)) mmn
M
3 1 (1+
BL BL n log (7)
n
(e) If Assumptions and hold, then for any 8 > O, with probability least 1 - 8, we have
R(xT) - (1 1)) inf R(x) < C + M log
+ ( +1) LB log, n log F.
XEX
17
41

---

Published as a conference paper at ICLR 2022
Remark 14. When conditions in Theorem holld, we obtain that (a) If Assumption and then for any å > O, with probability at least 1 - 6, the plain generalization
(s((T,,7) PT) ( +
emorr of (x) of PPM is of the order ((: + vz) log2 mlog(1/6)) (b) If Assumptions and 2 hold and (x(xT) o (*)). then for any 8 O, with probability at least 8, the
primal generalization error of (XT: 37) of PPM of the order (( + +++++/)) logz r log(1/6))
(c) If Assumptions I and hold, then for any > O, with probability least 5, the strong PD population risk and strong PD generalization enror of (Xp. of PPM are all of the order
((+ + V () loga n log(1/5)) (d) If Assumptions and 2 hold and infxex R(x) = 0
then for any O, with probability at least 1 - 6, the excess primal population risk of (xx, 9r) of PPM is of the order O ((#+ log2 log(1 For the above bounds, we can take T = (n²))
gradient evaluations to get bound of the order O log n log(1/6)).
F EXTRAGRADIENT METHOD
EG is classical algorithm for solving minimax problems introduced by (Korpelevich 1976). We now introduce some notations. Followed (Mokhtari et al.) [201)) we consider the following update of EG: given stepsize parameter we first compute a set of mid-point iterates {x++ N++4)
x = VVl's
Y++ = yt - Fs
(49)
we then compute the next iterates (xt+1:
X1+1 = X - - vV
X Notz);
Yt+1 = yt + vV Fis (x+ Ne-
(50)
Consider the averaged iterate
1 T
Xx
and yr T
(51)
Assume that the initial point satisfies Xg 1/2 and yo = -1122-
We now show the strong PD empirical risk bound for (&r, Fr) of EG.
Lemma 15. Mookhaar et al.
2019 Let yc). {x141/2. Nt+1/2) be the iterates generated by the EG updates in (49) and (20). Assume that the initial point satisfies Xo x and yo --1122- Suppose the ESP solution [x" . exists. Assume that Fs(x,y) y) is 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 25 for any E (0, 1), then:
(a) the iterates (x), (8441/2-441/1/ stay within the compact convex
D = (x,))lIx x111 lly 111 < (2+
42/2 (1|x0
2
x+112 I1yo - 8-111]
(52)
for all 2 1, we have
28(16 + 21- [[|x0 12 + Ilyo - 111)
33
sup yJED
Fs(XT,y)= inf x((xTr)E
Fs(x,yr) S
T
42

---

Published as a conference paper at ICLR 2022
Combined Lemma 7 and Lemma
15
know that the argument stability bound of EG is
4L
I
| xT|1 182
ST
4
(XT,
nj
4L
T
23(16
2(--0 )11xo - x* 1| + I1yo 11)
4
ny
T
(53)
Furthermore, for any x E y. E y and 2 2,
y:z) & f(x' y ;²) + L| || + -
- -y"l
sup f(x", ;2) 2L / VII 11 + lyy 3-11
sEZ
S f , + L 44+ - 4v 82 (1|x0 - x01 Ilyo - 1-11), (54)
sE2
where the first inequality follows from Assumption [ the second inequality follows from Caucy- Schwarz 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 we obtain generalization bounds of EG. The main theorem is shown below.
Theorem 8. Assume for all the function (x. v)
y: is p-SCCSC. Let (x) and 50 Assume the stepsize v satisfies the con- XT and Ay(S) Yr for &T..r) in 57. Denote the ESP solution as 8))) Consider the compact convex set in (5). Fixed any
{x++1/2, V141/2] be the iterates produced by 449 149--550
dition V
è 23 for any с (0,1). Denote (x)S)
> 0. Let M = supsez f(x" ( ;² + TV (4 1-40332 (11x0 & + Iyo (+))).. Let
+ 4 W.V.. There exists an absolute posi- B 28(16+ Mlixo +lyo 11) and +
rive constant C.
(a) If Asssumption/ 7 Mand] hold, then for any 5 > 0, with probability at least 1- 8, we have
F(XT, (1 F C + M
log(1/8) + Blogg n log(1/)))
rj
(b) If Assumptions 7 aadd hold, then any 5 > O, with probability at least - 8, we have
1 M R(x)) S (1 Rs(xr) +
( --+11) (=+))LBlog, n log 1)
log
n
(c) If Assumptions 7 [add] 2and2kn hold, then for any 8 > O, with probability at least 1 - 8, we have
A ('(x. & (1++)) + (12 1)
+ M
+ (1+
3 BL BL n1 log
mmtr
(d) If A Dand hold, then any 5 0, with probability least 8, we have
A (XI.Fr) (xr,
(2(1+ mun
M + +1+ ( BL (1++)BLOO8) n log (
Sn + C(1 +E++CL++
7)
+ n
(e) If Asssumptioos and hold, then any 8 > O, with probability at least 1 - 8, we have
R(xr) S (1 + n) inf R(x) 2 M
log (( + (11 Bog,
n log + F.
xEX
n
Remark 15. When conditions in Theorem 8 hold, we obtain that (a) If Assumptions and hhold and
Fx(x): FT) 0 then for any 8 > 0, with probability at least 1 - ō, the plain generalization
43

---

Published as a conference paper at ICLR 2022
error of FT) of EG is of the order (( + v+) log2 n log(1/
(b) If Assumptions
and 2 hold and (x(xT) O (+)) then for any 8 > O, with probability at least 1 - 8, the primal
generalization error of (Xr, of EG is of the order (( + +A) logz n log(1/6). (c) If 1 and 2 hold, then for any > O, with probability at least 1 6, the strong PD population risk and the strong PD generalization error of (x) of EG are all of the order O (
Assumptions
/+) log2 n log(1/6)). (d) If Assumptions 1 and hold and infxex R(x) (.)). then for any 5 > O, with probability at least 1 - 6, the excess primal population risk of (xT: 3r) of EG is ((+ + v+) log2 ( For the above bounds, we can take T (n²) gradient
evaluations to get bound of the order O log log(1/6)).
G OPTIMISTIC GRADIENT DESCENT ASCENT
OGDA is introduced by Popov 1980p, as a variant of the EG method. We introduce some notations to state the result of OGDA. Given stepsize parameter 0, OGDA do the following update for each f 2
X = V y1) V
Y--1 = y; + l's /マ (x)-1,
(55)
Assume that the initial point satisfies Xg = x_1 and yo = y- Consider the averaged iterate
Σ X and yr T XT T
1
Σ Yo.
(56)
We first provide lemma on the strong PD empirical risk of OGDA.
Lemma 16. Mokhtari al. 2019) Let (x, be the iterates generated by the OGDA updates in
(55. Assume that the initial point satisfies Xy = x-1 and Yu = y-1- Suppose the ESP solution
xx" y²) exists. Assume that Es Px. y) is convex function x x any and is concave function
y for any x. If Assumption holds and the stepsize v satisfies 0 < v S 1 then:
13
(a) the iterates Fx) stay within the compact convex set
D (xxx)) Iyy y < 2( x11 11yo - 8311)}]
(57)
for all 2 1, we have
(163 (
x1
Ilyo
512)
sup Fs(Xr.y) inf y:(Kr.y)ED
7s(x,Fr) 5
T
Combined Lemma 7 and Lemma 16
we know that the argument stability bound of OGDA is
4T.
X xr + 1
Frll
s
4
(xTr Fr)
np
4L
1
(163 + (1
1+ Iyo
Ilyo ---133
+
AV
(58)
nj
1
T
Moreover, similar to (54, we have
f(x S f(x y :2) ) L|| x
L
1"1 +
< sup f(x ;2) + 2L X #
X*
17.
(59)
Therefore, plugging (59). the stability bound 58 and the strong PD empirical risk bound in Lemma 16 into Theorem obtain generalization bounds of OGDA.
44

---

Published as a conference paper at ICLR 2022
Theorem 9.
Assume for all 2, the function (x,y) + yx is p-SC-SC. Let {xi, yr} be pro-
duced by (55 Assume the stepsize parameter v satisfies < S 43
1 Denote Ax(S) = Xy and
(S)
for (Kr, )r) in (56). Denote the ESP solution as (x*, yy), Consider the compact con-
vex set in 57
Fixed any 17 0. Let M sup=ez fxx",
;²² """";" 2) + 2L 2 / xx 1o 112.
Define B
(163+ 22 10100 Xo x*1 - and E
np AV I V.V. There exists an absolute
41.
positive constant C.
(a) If Assumptions and hold, then any 8 > 0, with probability least 1 we have
F(Xr. $ (1 +1) F) Vr) + + M
log(1/6) + B log, n log()
(b) If Assumptions 7 and hold, then for any 5 >> O, with probability at least 1 - 8, we have
1 M 1
(#) + +1)LBBlgg logz n log })
R(xx)= (1 ()(()) + C
log x
"
(c) If Assumptions 7 and hold, then any 8 O, with probability at least 8, we have
(12 + n)
M
(1..B)B.188 m) log 33
A (x(Tr.3r) S (1 + +
+
+
mum
n
(d) If Assumptions 7 and 2 hold, then for any 6 0, with probability at least 1 8, we have
A (T) - (3((
(1(1+
+ M
3 4 + +(++
BL logo n log (3)
+ +
+
mmm
(e) If Assumptions D [and] hold, then for any 5 >> O, with probability at least 1 - 8, we have
R(XT) s (1+ inf R(x) C 2 + M log 5 (2) + + log, n log g + )
xEX
7
Remark 16. When conditions in Theorem Lacemm@ine hhold, we obtain that (a) If Assumptions [and and hoold and
(x VT) o m then for any 5 > O, with probability at least 1 6, the plain generalization
error of (KT, Vr) of OGDA of the order o ((+ + v+) loga n log(1/0)) (b) Assumptions and hold and (x())) = ( then for any 8 > O, with probability at least 1 8, the primal
generalization error of (Xr, Fr) of OGDA is of the order ((1 ++ + log, n log(1/5)) (c) If Assumptions T and 2 hold, then for any > O, with probability at least - 6, the strong PD population risk and the strong PD generalization enror of (&T.Y) of OGDA
all of the order
(( t then for any 5 > O, with probability at least 1 - 8, the excess primal population risk of OGDA is of the order o ((( v/) log, log (1/8)). For the above bounds, we can take T = Onn)) gradient
((++v)) ( logz n log(1/5)).
(d) If Assumptions and 2 hold and inf x R(x) o
evaluations to get bound of the order O log log(1
H AUXILIARY DESCRIPTIONS OF TABLE
In Table [ Lip means Lipschitz continuity and S means smoothness. (R)-ESP means the (regularize))eempiee risk saddle point (Zhang et al., 2021a).. C-SC means -ottoyyy concave, and NC-SC means panroonve----ttrongyyyooo manconvee--ttrongly-coomm
A function f(x is called
if fxx .) is strongly-concave for every x. Morcover, a function f(x, y) is jeweakly--oonee--veee weweeeeewwwaal--ooneee
[|x| + liy) is convex-concave. V-WC- WC is a variant of WC-WC, please refer to (Lei et al. 2021 PL means the two-sided PL condition, which relaxes the convex-come conexx-con requirement of the objective function Yang et al. 2020) and is usually used to guarantee the linear convergence rate (Karimi et al. 2016 Yang al. 20200. AGDA algorithm is variant of GDA with alternating updates of the primal-dual variables. c is a parameter in the step size, B is parameter in Assumption 2 and is f3/p.
if
45

---

Published as a conference paper at ICLR 2022
I NUMERICAL EXPERIMENTS
In this section, we report preliminary experimental results to verify our theoretical results by per- forming 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 (o, Idxd) with zero mean and identity covariance. We will draw n independent samples from the underlying Gaussian distribution to form training dataset S = {zı.... Zn J. We set the dimension d of Z as 50. Similar to the strongly-come seree---trongooooo
case of (Farnia & Ozdaglar
2021
we consider the following minimax objective function
y;) = x" (z y) + 2 [1xx lyyl!3)
In the experiments, we set and constrain optimization variables x and y to satisfy |xx]|, |lyl| s 100 which we enforced by projection. For this minimax objective function, one can verify that
F(x,y) y) - yx = x" (E|Z) - Es [Z]):
R(x) - Rs(x)= = x² (E|Z) Es [Z),
where E|Z] = 0 since the mean of the underlying Gaussian distribution O, and where Es [Z]
Ei=1 Zi. For brevity, we call |x (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 [x" (B[Z) Es |z|Z and apply these algorithms to S. For GDA and SGDA, we consider the stepsize parameter as 1/t. We iterate GDA with n² times and SGDA with ne times. The generalization error of GDA and SGDA with different sizes of training data are reported in Figure I And for EG and OGDA, we select the stepsize parameter as 0.003. We run EG and OGDA n² times. Similarly, the generalization error of EG and OGDA with different sizes of training data are given in 2 From the two figures, we can see that the line of logn
best fit for the generalization error is log./2 n for GDA, n,9.98 for SGDA, log".99 220.98 for EG, and n1.02 for OGDA. These results match the predictive rates of the plain generalization error and the primal
log
w0.08
generalization error in Table i.e., loga/3 n for GDA, log for SGDA, log for EG, and log n for OGDA, which verifies our theoretical findings.
SGIA
0372
optimaal ling
Gonorol Ovter
Genwral
0.74
0.25
0382
0375
0.25
0233-
0:25
0.502
235
622
300
330
Figure 1: |x (E[Z)
E5 [Z)]
versus the number of samples on GDA (left) and SGDA (right).
0604
0.05
5.000
Sattonn
of cooplee
Number
Figure 2: |x (E|2) Z
Es [Z)
versus the number of samples on EG (left) and OCDA (right).
46


Reviews:
[{"review_id": "Vbb6p-fdth", "reviewer": "Reviewer_RFir", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper generalizes the algorithmic stability notions to the minimax problems and provides high probability bounds for some specific instances of problem/algorithm pairings when the problem has bounded values. I think this is a good contribution.\n\nThere are some issues with presentation and I think some of the statements are a little vaguer than they need to be. Instead of saying \"the plain generalization error is $O(1/n)$\" perhaps one could provide a precise statement about what exactly is $O(1/n)$ as otherwise readers have to go a back and interpret the results. In particular, from what I can see in part (a) of the main theorem, it was shown:\n$$F(x,y) \\le (1+\\eta)F_S(x,y) + \\tilde O\\left(\\frac{M+\\epsilon}{\\eta n}\\right)$$\nNow, how is one to read an $O(1/n)$ rate out of this? The $\\tilde O(M/\\eta n)$ part suggests $\\eta=\\Theta(1)$, but then I have a $2F_S(x,y)$. Is it the case that $F_S(x,y)=0$? This seems unlikely to me, but perhaps I missed something.\n\nIn fact, ALL of the statements made about generalization error rates suffer from this issue: I intuitively expect the thing that we are measuring the \"rate\" of to be True Value - Empirical Value, or maybe \"True value at point produced by algorithm - Optimal True value\", but it appears in Theorem 1 that we are actually looking at True Value - $(1+\\eta)\\times$ Empirical value, which seems a bit weird. Now, I believe that in many of the cases for specific algorithms (e.g. using the empirical minimizer), it might be that the empirical value is $0$ or $O(1/n)$ and so we have do have a fast rate as realized in the later theorems, but I think this is asking for a bit too much jumping ahead by the reader. Instead perhaps it is just the case that Theorem 1 provides a \"self-bounding'' style result that in concert with specific algorithms can be used to obtain a $O(1/n)$ rate?\n\nThese things would be clarified if the statements about generalization error were quantified correctly in equations rather than prose.\n\nHowever, while I am rather dissatisfied with these aspects of the presentation, I believe they can be rectified and if so the contributions are enough to merit acceptance.\n", "summary_of_the_paper": "This paper consider a stochastic minimax problem of the form $\\min_x \\max_y F(x,y)$ where $F(x,y) = \\mathbb{E}[f(x,y,z)]$. The goal is to obtain ``fast'' rates of $O(1/n)$ with a training set of $n$ i.i.d. $z_1,\\dots,z_n$ in high probability.\nIn 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.\n", "summary_of_the_review": "The paper provides new results in high probability that are valuable confirmation that standard algorithms will work well. The presentation leaves something to be desired, but is likely fixable in revision.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "K9c17luskwn", "reviewer": "Reviewer_Wpqu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper overall is written nicely and fairly clear. The problem setup is also interesting and has potential impact for other problems as well.\n\nA concern I have for the results is the comparison of the generalization with respect to the empirical measures: is there a motivation for comparing these measures with a constant (1+eta) multiple of empirical measures? It seems that it would be more reasonable to have results for the case where eta approximates zero---when eta is a non-zero constant, then if we were to look at the difference between the generalization measure and the empirical measure, there would be a dependency on the empirical risk multiplied by eta, which may or may not have the desired dependency on order as expected. \n\nFollowing the same concern as above, take for example the result Theorem 1-b., where the comparison of R(Ax(S)) is made with (1+eta)*R_S(Ax(S)). I took a look at the results of Farnia & Ozdaglar, and it appears that their paper compares the expected generalization risk E(R(Ax(S)-R_S(Ax(S))) which corresponds to eta->0.  Looking briefly at the referenced paper \"Stability and generalization of stochastic gradient methods for minimax problems\" by Lei et al., their results (Theorem 1) also compare the generalization measures directly with the empirical measures, without extra multiples such as (1+eta). Therefore it does seem that the fairness of the comparison can be discussed/explained in more detail.\n\nApart from the above concern, I agree with the authors that it would be interesting to see if assumptions can be relaxed. It would be helpful to have more discussions on the dependency of these assumptions.", "summary_of_the_paper": "High-probability generalization bounds for minimax problems are proposed. The authors establish bounds for four quantities: plain generalization error, primal generalization error, strong primal-dual risk and strong primal-dual generalization error. The main contribution of the paper is in fast rates of the bounds compared to previous work for various applications to popular algorithms.", "summary_of_the_review": "The paper is nicely written. There is a concern regarding the main theorem's dependency on the (1+eta) factor for the empirical measures. This also leads to a concern about the fairness of comparisons with related work. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GB--F7VP_xF", "reviewer": "Reviewer_LsE5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I think this is a timely solid work for the minimax learning problems which covers many interesting topics. \n\n-------------------- pros\n\n1. This paper is very well-written. \n2. It is valuable to move expectation bound to high probability bound or improve high probability bound from $O(1/\\sqrt{n})$ to $O(1/n)$. \n3. It clearly discusses its relationships and differences with previous work. \n4. The proofs are overall right although I cannot check the proofs line-by-line. \n\n-------------------- cons\n\n1. I have one concern is that how is the tightness of the achieved generalization upper bound,  and thus the lower bound might be discussed to illustrate it.\n2. It might be better to add some synthetic empirical experiments to illustrate the tightness and effectiveness of these generalization upper bounds w.r.t. the true population risk. \n\nBesides, I have some questions as follows.\n\n1. Why to define the strong or weak measures (Def. 1) like these? Please give more intuitive explanation.\n2. For Theorem 1, what is the differences between (c.) and (d.)? I think they are the same, do I miss something?\n3. For Theorem 1, what is the effect of variable $\\eta$? Please give more discussions.\n4. In Remark 1, authors repeatedly claims that what if argument stability and the strong PD empirical risk are of the fast order $O(1/n)$. While the argument stability with $O(1/n)$ can be understood, how to understand the strong PD empirical risk has dependence on the sample size $n$?\n\n--------------------- Minor comments\n\nTypos:\n\n1. Page 4. head: $|| z ||_p = (\\mathbb{E} \\| z \\|^p)^{1/p}$.\n\n", "summary_of_the_paper": "As a theory work, this paper considers the generalization of the minimax learning problems which has a wide applications in machine learning. In comparison with the results of the previous work, which either provide expectation bounds or high probability generalization bounds of $O(1/\\sqrt{n})$, this paper gives improved high generalization bounds of $O(1/n)$. Besides, these bounds are applied in many popular optimization algorithms, including ESP, GDA, SGDA and so on.", "summary_of_the_review": "While I think this is a solid theory work, it is better to add some discussions for the tightness of these generalization upper bounds, and some empirical validation experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "2oNVUo6XEL_", "reviewer": "Reviewer_jPJ9", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results obtained in the paper are new and are very nice extension of the existing work on minimax optimization algorithms.  The related work is well cited and the paper is organized well.  I have the following comments and suggestions: \n\n1.  it seems that the paper overly claimed the improvement over the existing work. In the abstract and introduction, the authors claim that \" improved generalization analyses for almost all existing generalization measures of minimax problems which enables the minimax\nproblems to establish sharper bounds of order $O(1/n)$, significantly, with high probability\".  This statement appeared several times in the paper.  From my perspective, it is not correct and misleading since the excess bounds are precisely given in the form of  $O(1/n +  \\epsilon_{stab})$ plus extra terms (e.g.   extra $\\eta F_S(A(S))$,  $\\eta \\bigtriangleup^s_S(A(s))$.  Indeed, the excess strong PD generalization bound is given by $O({1 \\over \\eta n} +  \\epsilon_{stab}  +   \\eta \\bigtriangleup^s_S(A(s)) ).$   For the reason above, the comparison results in Table 1 in page 8 is extremely vague and not precise.  The bounds stated in Theorem 2 and 3 are also incorrect because the extra term (e.g. $\\eta F_S(A(S))$ or $\\\\eta \\bigtriangleup^s_S(A(s))$ or $\\eta\\inf_w R(w)$) is ignored there. \n\n2. I never saw uniform stability for SGDA before:   uniform stability only holds true after taking expectation with respect to the internal randomness of the algorithm.   Indeed, the proof for Theorem 7 is not correct.  In this case, the uniform stability, i.e. inequality of (39) for SGDA holds with high probability.   But the whole of this paper is under the uniform stability assumption (NOT high probability form). Hence, you can not apply Theorem 1 to directly get the results in Theorem 7.  \n\n2.  While the results are new and interesting, the proof techniques are directly modified from Klochkov and Zhivotovskiy (2021). \n\n3. Part (c) and Part (d) are duplicate as they are essentially the same results.\n\n\n", "summary_of_the_paper": "This paper conducted a comprehensive study of high probability generalization bounds for minimax problems in terms of various forms of measuring generalization such as strong/weak PD generalization and primal generalization error.  Given uniform stability $\\epsilon_{stab}$,  it proved sharper bounds of order $O(1/n + \\epsilon_{stab})$  while sacrificing the empirical error (e.g.   extra $\\eta F_S(A(S))$,  $\\eta \\bigtriangleup^s_S(A(s))$ on the bound). The results improves the previous excess generalization bound $O(1/\\sqrt{n}+ \\epsilon_{stab}))$ when  $F_S(A(S))$ or $\\bigtriangleup^s_S(A(s))$ is very small.  The results extend the existing work by Lei et al. (2021) where most of the bounds were derived in expectation and high probability ones are given by f order $O(1/\\sqrt{n} + \\epsilon_{stab})$.  Then, specific bounds were given for GDA, PPM and SGDA for the strongly convex and strongly concave case as they are uniform stable.", "summary_of_the_review": "Overall, the paper presents very nice high-probabilistic generalization bounds for minimax problems and improves the existing ones which are mostly given in expectation.  The main proof techniques are adapted from Klochkov and Zhivotovskiy (2021).  The paper is also well organized and related work is sufficient.  However, the claims about significant improvement over existing work and providing sharper bound $O(1/n)$ are not precise and need to be corrected.  The proof for Theorem 7 is problematic since SGDA is not uniform stability as far as I know:  it is uniform stable only after taking expectation w.r.t. the internal randomness of the algorithm.\n\n\n**The authors have addressed main concerns on uniform stability of SGDA. It is a nice extension of the existing work. I only have minor suggestion on the final version of the paper about modifying the abstract in a modest tone and the caption to Table 1.   I will increase my score.**", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

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