marginparsep has been altered.
topmargin has been altered.
marginparwidth has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Stability and Generalization of Stochastic Gradient Methods for Minimax
Problems

Anonymous Authors1

††footnotetext:  1Anonymous Institution, Anonymous City, Anonymous Region,
Anonymous Country. Correspondence to: Anonymous Author
<EMAIL_ADDRESS>
Preliminary work. Under review by the International Conference on Machine
Learning (ICML). Do not distribute.

###### Abstract

Many machine learning problems can be formulated as minimax problems such as
Generative Adversarial Networks (GANs), AUC maximization and robust
estimation, to mention but a few. A substantial amount of studies are devoted
to studying the convergence behavior of their stochastic gradient-type
algorithms. In contrast, there is relatively little work on understanding
their generalization, i.e., how the learning models built from training
examples would behave on test examples. In this paper, we provide a
comprehensive generalization analysis of stochastic gradient methods for
minimax problems under both convex-concave and nonconvex-nonconcave cases
through the lens of algorithmic stability. We establish a quantitative
connection between stability and several generalization measures both in
expectation and with high probability. For the convex-concave setting, our
stability analysis shows that stochastic gradient descent ascent attains
optimal generalization bounds for both smooth and nonsmooth minimax problems.
We also establish generalization bounds for both weakly-convex-weakly-concave
and gradient-dominated problems. We report preliminary experimental results to
verify our theory.

##  1 Introduction

In machine learning we often encounter minimax optimization problems, where
the decision variables are partitioned into two groups: one for minimization
and one for maximization. This framework covers many important problems as
specific instantiations, including adversarial learning (Goodfellow et al.,
2014), robust optimization (Chen et al., 2017, Namkoong & Duchi, 2017),
reinforcement learning (Du et al., 2017, Dai et al., 2018) and AUC
maximization (Ying et al., 2016, Liu et al., 2018, Zhao et al., 2011, Gao et
al., 2013, Lei & Ying, 2021b). To solve these problems, researchers have
proposed various efficient optimization algorithms, for which a representative
algorithm is the stochastic gradient descent ascent (SGDA) due to its
simplicity and widespread use in real-world applications.

There is a large amount of work on the convergence analysis of minimax
optimization algorithms in different settings such as convex-concave
(Nemirovski et al., 2009), strongly-convex-strongly-concave (SC-SC)
(Balamurugan & Bach, 2016), nonconvex-concave (Rafique et al., 2018) and
nonconvex-nonconcave (Liu et al., 2020, Yang et al., 2020) cases. However,
there is relatively little work on studying the generalization, i.e., how the
model trained based on the training examples would generalize to test
examples. Indeed, a model with good performance on training data may not
generalize well if the models are too complex. It is imperative to study the
generalization error of the trained models to foresee their prediction
behavior. This often entails the investigation of the tradeoff between
optimization and estimation for an implicit regularization.

To our best knowledge, there is only two recent work on the generalization
analysis for minimax optimization algorithms (Zhang et al., 2020, Farnia &
Ozdaglar, 2020). The argument stability for the specific empirical saddle
point (ESP) was studied (Zhang et al., 2020), which implies weak
generalization and strong generalization bounds. However, the discussion there
ignored optimization errors and nonconvex-nonconcave cases, which can be
restrictive in practice. For SC-SC, convex-concave, nonconvex-nonconcave
objective functions, the uniform stability of several gradient-based minimax
learners was developed in a smooth setting (Farnia & Ozdaglar, 2020),
including gradient descent ascent (GDA), proximal point method (PPM) and
GDmax. While they developed optimal generalization bounds for PPM, their
discussions did not yield vanishing risk bounds for GDA in the general convex-
concave case since their generalization bounds grow exponentially in terms of
the iteration number. Furthermore, the above mentioned papers only study
generalization bounds in expectation, and there is a lack of high-probability
analysis.

In this paper, we leverage the lens of algorithmic stability to study the
generalization behavior of minimax learners for both convex-concave and
nonconvex-nonconcave problems. Our discussion shows how the optimization and
generalization should be balanced for good prediction performance. Our main
results are listed in Table 1. In particular, our contributions can be
summarized as follows.

1\. We establish a quantitative connection between stability and
generalization for minimax learners in different forms including weak/strong
primal-dual generalization, primal generalization and generalization with high
probability. For the technical contributions, we introduce novel
decompositions to handle the correlation between the primal model and dual
model for connecting stability and generalization.

2\. We establish stability bounds of SGDA for convex-concave problems, from
which we derive its optimal population risk bounds under an appropriate early-
stopping strategy. We consider several measures of generalization and show
that the optimal population risk bounds can be derived even in the nonsmooth
case. To the best of our knowledge, our results are the first-ever known
population risk bounds for minimax problems in the nonsmooth setting and the
high-probability format.

3\. We further extend our analysis to the nonconvex-nonconcave setting and
give the first generalization bounds for nonsmooth objective functions. Our
analysis relaxes the range of step size for a controllable stability and
implies meaningful primal population risk bounds under some regularity
assumptions of objective functions, e.g., a decay of weak-convexity-weak-
concavity parameter along the optimization process or a two-sided PL
condition.

The paper is organized as follows. The related work is discussed in Section
1.1 and the minimax problem formulation is given in Section 2. The connection
between stability and generalization is studied in Section 3. We develop
population risk bounds in the convex-concave case in Section 4 and extend our
discussions to the nonconvex-nonconcave case in Section 5. We report
preliminary experiments in Section 6 and conclude the paper in Section 7.

###  1.1 Related Work

We first review related work of stochastic optimization for minimax problems.
Convergence rates of order $O(1/\sqrt{T})$ were established for SGDA with $T$
iterations in the convex-concave case (Nemirovski et al., 2009, Nedić &
Ozdaglar, 2009), which can be further improved for SC-SC problems (Balamurugan
& Bach, 2016, Hsieh et al., 2019). These discussions were extended to
nonconvex-strongly-concave (Rafique et al., 2018, Lin et al., 2020, Luo et
al., 2020, Yan et al., 2020), nonconvex-concave (Thekumparampil et al., 2019,
Lin et al., 2020) and nonconvex-nonconcave (Yang et al., 2020, Loizou et al.,
2020, Liu et al., 2020) minimax optimization problems. All the above mentioned
work consider the convergence rate of optimization errors, while the
generalization analysis was much less studied (Zhang et al., 2020, Farnia &
Ozdaglar, 2020).

We now survey related work on stability and generalization. The framework of
stability analysis was established in a seminal paper (Bousquet & Elisseeff,
2002), where the celebrated concept of uniform stability was introduced. This
stability was extended to study randomized algorithms (Elisseeff et al.,
2005). It was shown that stability is closely related to the fundamental
problem of learnability (Shalev-Shwartz et al., 2010, Rakhlin et al., 2005).
Hardt et al. (2016) pioneered the generalization analysis of SGD via
stability, which inspired several upcoming work to understand stochastic
optimization algorithms based on different algorithmic stability measures,
e.g., uniform stability (Lin et al., 2016, Chen et al., 2018, Mou et al.,
2018, Richards et al., 2020, Madden et al., 2020), argument stability (Liu et
al., 2017, Bassily et al., 2020, Lei & Ying, 2020), on-average stability
(Kuzborskij & Lampert, 2018, Lei & Ying, 2021a), hypothesis stability (London,
2017, Charles & Papailiopoulos, 2018, Foster et al., 2019), Bayes stability
(Li et al., 2020) and locally elastic stability (Deng et al., 2020).

Algorithm | Reference | Assumption | Measure | Rate
---|---|---|---|---
ESP | Zhang et al. (2020) |  $\rho$-SC-SC, Lip | Weak PD Risk | $O(1/(n\rho))$
$\rho$-SC-SC, Lip, S | Strong PD Risk | $O(1/(n\rho^{2}))$
R-ESP | C-C, Lip | Weak PD Risk | $O(1/\sqrt{n})$
SGDA, SGDmax | Farnia & Ozdaglar (2020) |  $\rho$-SC-SC, Lip, S | Weak PD Generalization111Primal generalization bounds were presented in Farnia & Ozdaglar (2020). However, the stability analysis there actually only implies bounds on weak PD risk. | $O(\log(n)/(n\rho))$
PPM | C-C, Lip, S | Weak PD Risk | $O(1/\sqrt{n})$
SGDA | This work | C-C, Lip (S) | Weak PD Risk | $O({1}/{\sqrt{n}})$
C-$\rho$-SC, Lip, S | (H.P.) Primal Risk | $O({1}/{(\sqrt{n}\rho)})$
C-C, Lip | H.P. Plain Risk | $O(\log(n)/{\sqrt{n}})$
$\rho$-SC-SC, Lip | Weak PD Risk | ${O}(\sqrt{\log n}/(n\rho))$
SGDA |  Farnia & Ozdaglar (2020)tnote:robots-r1 | Lip, S | Weak PD Generalization | $O\big{(}T^{\frac{Lc}{Lc+1}}/n\big{)}$
SGDA | This work |  $\rho$-WC-WC, Lip | Weak PD Generalization | $O\big{(}T^{\frac{2c\rho}{2c\rho+3}}/n^{\frac{2c\rho+1}{2c\rho+3}}\big{)}$
D, Lip, S | Weak PD Generalization | $O\big{(}1/\sqrt{n}+\sqrt{T}/n\big{)}$
AGDA |  $\rho$-SC, PL, Lip, S | Primal Risk | $O\big{(}n^{-\frac{cL+1}{2cL+1}}\big{)}$
Table 1: Summary of Results. Bounds are stated in expectation or with high
probability (H.P.). For risk bounds, the optimal $T$ (number of iterations) is
chosen to trade-off generalization and optimization. Here, C-C means convex-
concave, C-$\rho$-SC means convex-$\rho$-strongly-concave, $\rho$-SC means
nonconvex-$\rho$-strongly-concave, Lip means Lipschitz continuity, S means the
smoothness, D means a decay of weak-convexity-weak-concavity parameter along
the optimization process as Eq. (5.1) and PL means the two-sided condition as
Assumption 3 . AGDA means Alternating Gradient Descent Ascent and (R)-ESP
means the (regularized)-empirical risk saddle point. $c$ is a parameter in the
step size and $L$ is given in Assumption 2.

##  2 Problem Formulation

Let $\mathcal{W}$ and $\mathcal{V}$ be two parameter spaces in
$\mathbb{R}^{d}$. Let $\mathbb{P}$ be a probability measure defined on a
sample space $\mathcal{Z}$ and
$f:\mathcal{W}\times\mathcal{V}\times\mathcal{Z}\mapsto\mathbb{R}$. We
consider the following minimax optimization problem:

$\min_{\mathbf{w}\in\mathcal{W}}\max_{\mathbf{v}\in\mathcal{V}}F(\mathbf{w},\mathbf{v}):=\mathbb{E}_{z\sim\mathbb{P}}[f(\mathbf{w},\mathbf{v};z)].$
(2.1)

In practice, we do not know $\mathbb{P}$ but instead have access to a dataset
$S=\\{z_{1},\ldots,z_{n}\\}$ independently drawn from $\mathbb{P}$. Then, we
approximate $F$ by an empirical risk

$F_{S}(\mathbf{w},\mathbf{v})=\frac{1}{n}\sum_{i=1}^{n}f(\mathbf{w},\mathbf{v};z_{i}).$

We apply a (randomized) algorithm $A$ to the dataset $S$ and get a model
$A(S):=(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))\in\mathcal{W}\times\mathcal{V}$
as an approximate solution of the problem (2.1). Since the model $A(S)$ is
trained based on the training dataset $S$, its empirical behavior as measured
by $F_{S}$ may not generalize well to a test example (Bousquet & Elisseeff,
2002). We are interested in studying the test error (population risk) of
$A(S)$. Unlike the standard statistical learning theory (SLT) setting where
there is only a minimization of $\mathbf{w}$, we have different measures of
population risk due to the minimax structure (Zhang et al., 2020). We collect
the notations of these performance measures in Table A.1. Let
$\mathbb{E}[\cdot]$ denote the expectation w.r.t. the randomness of both the
algorithm $A$ and the dataset $S$.

######  Definition 1 (Weak Primal-Dual Risk).

The weak Primal-Dual (PD) population risk of a (randomized) model
$({\mathbf{w}},{\mathbf{v}})$ is defined as (Zhang et al., 2020)

$\triangle^{w}({\mathbf{w}},{\mathbf{v}})=\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}\mathbb{E}\big{[}F({\mathbf{w}},\mathbf{v}^{\prime})\big{]}-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}\mathbb{E}\big{[}F(\mathbf{w}^{\prime},{\mathbf{v}})\big{]}.$

The weak PD empirical risk of $({\mathbf{w}},{\mathbf{v}})$ is defined as

$\triangle^{w}_{S}({\mathbf{w}},{\mathbf{v}})=\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}\mathbb{E}\big{[}F_{S}({\mathbf{w}},\mathbf{v}^{\prime})\big{]}-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}\mathbb{E}\big{[}F_{S}(\mathbf{w}^{\prime},{\mathbf{v}})\big{]}.$

We refer to
$\triangle^{w}({\mathbf{w}},{\mathbf{v}})-\triangle^{w}_{S}({\mathbf{w}},{\mathbf{v}})$
as the weak PD generalization error of the model
$({\mathbf{w}},{\mathbf{v}})$.

######  Definition 2 (Strong Primal-Dual Risk).

The strong PD population risk of a model $({\mathbf{w}},{\mathbf{v}})$ is
defined as

$\triangle^{s}({\mathbf{w}},{\mathbf{v}})=\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F({\mathbf{w}},\mathbf{v}^{\prime})-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}F(\mathbf{w}^{\prime},{\mathbf{v}}).$

The strong PD empirical risk of $({\mathbf{w}},{\mathbf{v}})$ is defined as

$\triangle^{s}_{S}({\mathbf{w}},{\mathbf{v}})=\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}({\mathbf{w}},\mathbf{v}^{\prime})-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}F_{S}(\mathbf{w}^{\prime},{\mathbf{v}}).$

We refer to
$\triangle^{s}({\mathbf{w}},{\mathbf{v}})-\triangle^{s}_{S}({\mathbf{w}},{\mathbf{v}})$
as the strong PD generalization error of the model
$({\mathbf{w}},{\mathbf{v}})$.

######  Definition 3 (Primal Risk).

The primal population risk of a model $\mathbf{w}$ is defined as
$R(\mathbf{w})=\sup_{\mathbf{v}\in\mathcal{V}}F(\mathbf{w},\mathbf{v}).$ The
primal empirical risk of $\mathbf{w}$ is defined as
$R_{S}(\mathbf{w})=\sup_{\mathbf{v}\in\mathcal{V}}F_{S}(\mathbf{w},\mathbf{v}).$
We refer to $R(\mathbf{w})-R_{S}(\mathbf{w})$ as the primal generalization
error of the model $\mathbf{w}$, and
$R(\mathbf{w})-\inf_{\mathbf{w}^{\prime}}R(\mathbf{w}^{\prime})$ as the excess
primal population risk.

According to the above definitions, we know
$\triangle^{w}({\mathbf{w}},{\mathbf{v}})\leq\mathbb{E}\big{[}\triangle^{s}({\mathbf{w}},{\mathbf{v}})\big{]}$
and $R(\mathbf{w})-R_{S}(\mathbf{w})$ is closely related to
$\triangle^{s}({\mathbf{w}},{\mathbf{v}})-\triangle^{s}_{S}({\mathbf{w}},{\mathbf{v}})$.
The key difference between the weak PD risk and the strong PD risk is that the
expectation is inside of the supremum/infimum for weak PD risk, while outside
of the supremum/infimum for strong PD risk. In this way, one does not need to
consider the coupling between primal and dual models for studying weak PD
risks, and has to consider this coupling for strong PD risks. Furthermore, we
refer to $F(\mathbf{w},\mathbf{v})-F_{S}(\mathbf{w},\mathbf{v})$ as the plain
generalization error as it is standard in SLT. An approach to handle a
population risk is to decompose it into a generalization error (estimation
error) and an empirical risk (optimization error) (Bousquet & Bottou, 2008).
For example, the weak PD population risk can be decomposed as

$\\!\\!\\!\\!\\!\\!\triangle^{w}(\mathbf{w},\mathbf{v})=\big{(}\triangle^{w}(\mathbf{w},\mathbf{v})-\triangle_{S}^{w}(\mathbf{w},\mathbf{v})\big{)}+\triangle_{S}^{w}(\mathbf{w},\mathbf{v}).$
(2.2)

The generalization error comes from the approximation of $\mathbb{P}$ with
$S$, while the empirical risk comes since the algorithm may not find the
saddle point of $F_{S}$. Our basic idea is to use algorithmic stability to
study the generalization error and use optimization theory to study the
empirical risk.

We now introduce necessary definitions and assumptions. Denote $\|\cdot\|_{2}$
as the Euclidean norm and $\langle\cdot,\cdot\rangle$ as the inner product. A
function $g:\mathcal{W}\mapsto\mathbb{R}$ is said to be $\rho$-strongly-convex
($\rho\geq 0$) iff for all $\mathbf{w},\mathbf{w}^{\prime}\in\mathcal{W}$
there holds $g(\mathbf{w})\geq
g(\mathbf{w}^{\prime})+\langle\mathbf{w}-\mathbf{w}^{\prime},\nabla
g(\mathbf{w}^{\prime})\rangle+\frac{\rho}{2}\|\mathbf{w}-\mathbf{w}^{\prime}\|_{2}^{2},$
where $\nabla$ is the gradient operator. We say $g$ is convex if $g$ is
0-strongly-convex. We say $g$ is $\rho$-strongly concave if $-g$ is
$\rho$-strongly convex and concave if $-g$ is convex.

######  Definition 4.

Let $\rho\geq 0$ and $g:\mathcal{W}\times\mathcal{V}\mapsto\mathbb{R}$. We say

  1. (a)

$g$ is $\rho$-strongly-convex-strongly-concave ($\rho$-SC-SC) if for any
$\mathbf{v}\in\mathcal{V}$, the function $\mathbf{w}\mapsto
g(\mathbf{w},\mathbf{v})$ is $\rho$-strongly-convex and for any
$\mathbf{w}\in\mathcal{W}$, the function $\mathbf{v}\mapsto
g(\mathbf{w},\mathbf{v})$ is $\rho$-strongly-concave.

  2. (b)

$g$ is convex-concave if $g$ is $0$-SC-SC.

  3. (c)

$g$ is $\rho$-weakly-convex-weakly-concave ($\rho$-WC-WC) if
$g+\frac{\rho}{2}\big{(}\|\mathbf{w}\|_{2}^{2}-\|\mathbf{v}\|_{2}^{2})$ is
convex-concave.

The following two assumptions are standard (Zhang et al., 2020, Farnia &
Ozdaglar, 2020). Assumption 1 amounts to saying $f$ is Lipschitz continuous
with respect to (w.r.t.) both $\mathbf{w}$ and $\mathbf{v}$. Let
$\nabla_{\mathbf{w}}f$ denote the gradient w.r.t. $\mathbf{w}$.

######  Assumption 1.

Let $G>0$. Assume for all $\mathbf{w}\in\mathcal{W},\mathbf{v}\in\mathcal{V}$
and $z\in\mathcal{Z}$, there holds
$\big{\|}\nabla_{\mathbf{w}}f(\mathbf{w},\mathbf{v};z)\big{\|}_{2}\leq
G\;\text{ and
}\;\big{\|}\nabla_{\mathbf{v}}f(\mathbf{w},\mathbf{v};z)\big{\|}_{2}\leq G.$

######  Assumption 2.

Let $L>0$. For any $z$, the function $(\mathbf{w},\mathbf{v})\mapsto
f(\mathbf{w},\mathbf{v};z)$ is said to be $L$-smooth, if the following
inequality holds for all $\mathbf{w}\in\mathcal{W},\mathbf{v}\in\mathcal{V}$
and $z\in\mathcal{Z}$

$\left\|\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w},\mathbf{v};z)-\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime};z)\\\
\nabla_{\mathbf{v}}f(\mathbf{w},\mathbf{v};z)-\nabla_{\mathbf{v}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime};z)\end{pmatrix}\right\|_{2}\\!\leq\\!L\left\|\begin{pmatrix}\mathbf{w}\\!-\\!\mathbf{w}^{\prime}\\\
\mathbf{v}\\!-\\!\mathbf{v}^{\prime}\end{pmatrix}\right\|_{2}.$

###  2.1 Motivating Examples

The minimax formulation (2.1) has broad applications in machine learning. Here
we give some examples.

AUC Maximization. Area Under ROC Curve (AUC) is a popular measure for binary
classification. Let $h(\mathbf{w};x)$ denote a scoring function parameterized
by $\mathbf{w}$ at $x$. It was shown that AUC maximization for learning $h$
under the square loss reduces to the problem (Ying et al., 2016)

$\min_{(\mathbf{w},a,b)\in\mathbb{R}^{d+2}}\max_{\alpha\in\mathbb{R}}\mathbb{E}[f(\mathbf{w},a,b,\alpha;z)],$
(2.3)

where $p=\mathbb{P}[y=1]$ and
$f(\mathbf{w},a,b,\alpha;z)=(h(\mathbf{w};x)-a)^{2}\mathbb{I}_{[y=1]}/p+(h(\mathbf{w};x)-b)^{2}\mathbb{I}_{[y=-1]}/(1-p)+2(1+\alpha)h(\mathbf{w};x)(\mathbb{I}_{[y=-1]}/(1-p)-\mathbb{I}_{[y=1]}/p)-\alpha^{2}$
($\mathbb{I}_{[\cdot]}$ is the indicator function). It is clear that
$\alpha\mapsto f(\mathbf{w},a,b,\alpha;z)$ is a (strongly) concave function.
Depending on $h$, the function $f$ can be convex, nonconvex, smooth or
nonsmooth.

Generative Adversarial Networks. GAN Goodfellow et al. (2014) refers to a
popular class of generative models that consider generative modeling as a game
between a generator network $G_{\mathbf{v}}$ and a discriminator network
$D_{\mathbf{w}}$. The generator network produces synthetic data from random
noise $\xi\sim\mathbb{P}_{\xi}$, while the discriminator network discriminates
between the true data and the synthetic data. In particular, a popular variant
of GAN named as WGAN Arjovsky et al. (2017) can be written as a minimax
problem

$\displaystyle\min_{\mathbf{w}}\max_{\mathbf{v}}\mathbb{E}[f(\mathbf{w},\mathbf{v};z,\xi)]=\mathbb{E}_{z}[D_{\mathbf{w}}(z)]-\mathbb{E}_{\xi}[D_{\mathbf{w}}(G_{\mathbf{v}}(\xi))].$

While this problem is generally nonconvex-nonconcave, it is weakly-convex-
weakly-concave under smoothness assumptions on $D$ and $G$ (Liu et al., 2020).

Robust Estimation with minimax estimator. Audibert & Catoni (2011) formulated
robust estimation as a minimax problem as follows

$\displaystyle\min_{\mathbf{w}}\max_{\mathbf{v}}\
F_{S}(\mathbf{w},\mathbf{v})=\frac{1}{n}\sum_{i=1}^{n}\psi(\ell_{1}(\mathbf{w};z_{i})-\ell_{2}(\mathbf{v};z_{i})),$

where $\psi:\mathbb{R}\mapsto\mathbb{R}$ is a truncated loss, and
$\ell_{1},\ell_{2}$ are Lipschitz continuous and convex loss functions. A
typical truncated loss is $\psi(x)=\log(1+|x|+x^{2}/2)\text{sign}(x)$ to
compute a mean estimator under heavy-tailed distribution of data Brownlees et
al. (2015), Xu et al. (2020), where $\text{sign}(x)$ is the sign of $x$. The
composition function $F_{S}$ can be nonconvex and nonsmooth since $\psi$ is
nonconvex and $\ell_{1},\ell_{2}$ can be nonsmooth. Following Xu et al.
(2020), it can be shown that $F_{S}(\mathbf{w},\mathbf{v})$ is weakly-convex-
weakly-concave.

##  3 Connecting Stability and Generalization

A fundamental concept in our analysis is the algorithmic stability, which
measures the sensitivity of an algorithm w.r.t. the perturbation of training
datasets (Bousquet & Elisseeff, 2002). We say $S,S^{\prime}\subset\mathcal{Z}$
are neighboring datasets if they differ by at most a single example. We
introduce three stability measures to the minimax learning setting. The weak-
stability and uniform-stability quantify the sensitivity measured by function
values, while the argument-stability quantifies the sensitivity measured by
arguments. We collect these notations of stabilities in Table A.2 in Appendix
A.

######  Definition 5 (Algorithmic Stability).

Let $A$ be a randomized algorithm, $\epsilon>0$ and $\delta\in(0,1)$. Then we
say

  1. (a)

$A$ is $\epsilon$-weakly-stable if for all neighboring $S$ and $S^{\prime}$,
there holds

$\\!\sup_{z}\Big{(}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}\mathbb{E}_{A}\big{[}f(A_{\mathbf{w}}(S),\mathbf{v}^{\prime};z)-f(A_{\mathbf{w}}(S^{\prime}),\mathbf{v}^{\prime};z)\big{]}\\\
+\sup_{\mathbf{w}^{\prime}\in\mathcal{W}}\mathbb{E}_{A}\big{[}f(\mathbf{w}^{\prime},A_{\mathbf{v}}(S);z)-f(\mathbf{w}^{\prime},A_{\mathbf{v}}(S^{\prime});z)\big{]}\Big{)}\leq\epsilon.$

  2. (b)

$A$ is $\epsilon$-argument-stable in expectation if for all neighboring $S$
and $S^{\prime}$, there holds

$\mathbb{E}_{A}\left[\left\|\begin{pmatrix}A_{\mathbf{w}}(S)-A_{\mathbf{w}}(S^{\prime})\\\
A_{\mathbf{v}}(S)-A_{\mathbf{v}}(S^{\prime})\end{pmatrix}\right\|_{2}\right]\leq\epsilon.$

$A$ is $\epsilon$-argument-stable with probability at least $1-\delta$ if with
probability at least $1-\delta$

$\left\|\begin{pmatrix}A_{\mathbf{w}}(S)-A_{\mathbf{w}}(S^{\prime})\\\
A_{\mathbf{v}}(S)-A_{\mathbf{v}}(S^{\prime})\end{pmatrix}\right\|_{2}\leq\epsilon.$

  3. (c)

$A$ is $\epsilon$-uniformly-stable with probability at least $1-\delta$ if
with probability at least $1-\delta$

$\\!\\!\\!\\!\sup_{z}\big{[}f(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S);z)-f(A_{\mathbf{w}}(S^{\prime}),A_{\mathbf{v}}(S^{\prime});z)\big{]}\leq\epsilon.$

Under Assumption 1, argument stability implies weak and uniform stability. As
we will see, argument stability plays an important role in getting primal
population risk bounds.

As our first main result, we establish a quantitative connection between
algorithmic stability and generalization in the following theorem to be proved
in Appendix B. Part (a) establishes the connection between weak-stability and
weak PD generalization error. Part (b) and Part (c) establish the connection
between argument stability and strong/primal generalization error under a
further assumption on the strong convexity/concavity. Part (d) and Part (e)
establish high-probability bounds based on the uniform stability, which are
much more challenging to derive than bounds in expectation and are important
to understand the variation of an algorithm in several independent runs
(Feldman & Vondrak, 2019, Bousquet et al., 2020). Regarding the technical
contributions, we introduce novel decompositions in handling the correlation
between $A_{\mathbf{w}}(S)$ and
$\mathbf{v}_{S}^{*}=\arg\sup_{\mathbf{v}}F(A_{\mathbf{w}}(S),\mathbf{v})$,
especially for high-probability analysis.

######  Theorem 1.

Let $A$ be a randomized algorithm and $\epsilon>0$.

  1. (a)

If $A$ is $\epsilon$-weakly-stable, then the weak PD generalization error of
$(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))$ satisfies

$\triangle^{w}(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))-\triangle^{w}_{S}(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))\leq\epsilon.$

  2. (b)

If $A$ is $\epsilon$-argument-stable in expectation, the function
$\mathbf{v}\mapsto F(\mathbf{w},\mathbf{v})$ is $\rho$-strongly-concave and
Assumptions 1, 2 hold, then the primal generalization error satisfies

$\mathbb{E}_{S,A}\Big{[}R(A_{\mathbf{w}}(S))-R_{S}(A_{\mathbf{w}}(S))\Big{]}\leq\big{(}1+L/\rho\big{)}G\epsilon.$

  3. (c)

If $A$ is $\epsilon$-argument-stable in expectation, $\mathbf{v}\mapsto
F(\mathbf{w},\mathbf{v})$ is $\rho$-SC-SC and Assumptions 1, 2 hold, then the
strong PD generalization error satisfies

$\mathbb{E}_{S,A}\Big{[}\triangle^{s}(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))-\triangle^{s}_{S}(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))\Big{]}\\\
\leq\big{(}1+L/\rho\big{)}G\sqrt{2}\epsilon.$

  4. (d)

Assume $|f(\mathbf{w},\mathbf{v};z)|\leq R$ for some $R>0$ and
$\mathbf{w}\in\mathcal{W},\mathbf{v}\in\mathcal{V},z\in\mathcal{Z}$. Assume
for all $\mathbf{w}$, the function $\mathbf{v}\mapsto
F(\mathbf{w},\mathbf{v})$ is $\rho$-strongly-concave and Assumptions 1, 2
hold. Let $\delta\in(0,1)$. If $A$ is $\epsilon$-uniformly stable almost
surely (a.s.), then with probability at least $1-\delta$

$R(A_{\mathbf{w}}(S))-R_{S}(A_{\mathbf{w}}(S))=\\\
O\Big{(}GL\rho^{-1}\epsilon\log
n\log(1/\delta)+Rn^{-\frac{1}{2}}\sqrt{\log(1/\delta)}\Big{)}.$

  5. (e)

Assume $|f(\mathbf{w},\mathbf{v};z)|\leq R$ for some $R>0$ and
$\mathbf{w}\in\mathcal{W},\mathbf{v}\in\mathcal{V},z\in\mathcal{Z}$. Let
$\delta\in(0,1)$. If $A$ is $\epsilon$-uniformly-stable a.s., then with
probability $1-\delta$ there holds

$\big{|}F(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))-F_{S}(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))\big{|}\\\
=O\Big{(}\epsilon\log
n\log(1/\delta)+Rn^{-\frac{1}{2}}\sqrt{\log(1/\delta)}\Big{)}.$

######  Remark 1.

We compare Theorem 1 with related work. Weak and strong PD generalization
error bounds were established for (R)-ESP (Zhang et al., 2020). However, the
discussion there does not consider the connection between stability and
generalization. Primal generalization bounds were studied for stable
algorithms (Farnia & Ozdaglar, 2020). However, the discussion there is not
rigorous since they used an identity
$nR_{S}(A_{\mathbf{w}}(S))=\sum_{i=1}^{n}\max_{\mathbf{v}}f(A_{\mathbf{w}}(S),\mathbf{v};z_{i})$,
which does not hold. To our best knowledge, Theorem 1 gives the first
systematic connection between stability and generalization for minimax
problems.

######  Remark 2.

We provide some intuitive understanding of Theorem 1 here. Part (a) shows that
weak-stability is sufficient for weak PD generalization. This is as expected
since both the supremum over $\mathbf{w}^{\prime}$ and $\mathbf{v}^{\prime}$
are outside of the expectation operator in the definition of weak
stability/generalization. We do not need to consider the correlation between
$A_{\mathbf{w}}(S)$ and $\mathbf{v}^{\prime}$. As a comparison, the primal
generalization needs the much stronger argument-stability. The reason is that
the supremum over $\mathbf{w}^{\prime}$ is inside the expectation and
$\mathbf{v}^{(i)}:=\arg\sup_{\mathbf{v}^{\prime}}F(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}^{\prime})$
is different for different $i$ ($\mathbf{v}^{(i)}$ correlates to
$A_{\mathbf{w}}(S^{(i)})$ and $S^{(i)}$ is derived by replacing the $i$-th
example in $S$ with $z_{i}^{\prime}$). We need to estimate how
$\mathbf{v}^{(i)}$ differs from each other due to the difference among
$A_{\mathbf{w}}(S^{(i)})$. This explains why we need argument-stability and a
strong-concavity in Parts (b), (d) for primal generalization. Similarly, the
strong PD generalization assumes SC-SC functions.

##  4 SGDA: Convex-Concave Case

In this section, we are interested in SGDA for solving minimax optimization
problems in the convex-concave case. Let $\mathbf{w}_{1}=0\in\mathcal{W}$ and
$\mathbf{v}_{1}=0\in\mathcal{V}$ be the initial point. Let
$\text{Proj}_{\mathcal{W}}(\cdot)$ and $\text{Proj}_{\mathcal{V}}(\cdot)$
denote the projections onto $\mathcal{W}$ and $\mathcal{V}$, respectively. Let
$\\{\eta_{t}\\}_{t}$ be a sequence of positive stepsizes. At each iteration,
we randomly draw $i_{t}$ from the uniform distribution over
$[n]:=\\{1,2,\ldots,n\\}$ and do the update

$\begin{cases}\mathbf{w}_{t+1}=\text{Proj}_{\mathcal{W}}\big{(}\mathbf{w}_{t}-\eta_{t}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\big{)},&\\\
\mathbf{v}_{t+1}=\text{Proj}_{\mathcal{V}}\big{(}\mathbf{v}_{t}+\eta_{t}\nabla_{\mathbf{v}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\big{)}.&\end{cases}$
(4.1)

###  4.1 Stability Bounds

In this section, we present the stability bounds for SGDA in the convex-
concave case. We consider both the nonsmooth setting and smooth setting. Part
(a) and Part (b) establish stability bounds in expectation, while Part (c) and
Part (d) give stability bounds with high probability. Part (e) consider the
SC-SC case. The proofs are given in Appendix C.

######  Theorem 2.

Assume for all $z$, the function $(\mathbf{w},\mathbf{v})\mapsto
f(\mathbf{w},\mathbf{v};z)$ is convex-concave. Let the algorithm $A$ be SGDA
(4.1) with $t$ iterations. Let $\delta\in(0,1)$.

  1. (a)

Assume $\eta_{t}=\eta$. If Assumption 1 holds, then $A$ is $4\eta
G\big{(}\sqrt{t}+t/n\big{)}$-argument-stable in expectation.

  2. (b)

If Assumptions 1, 2 hold, then $A$ is $\epsilon$-argument-stable in
expectation, where

$\\!\\!\\!\\!\epsilon\leq\frac{\sqrt{8e(1+t/n)}G}{\sqrt{n}}\exp\Big{(}2^{-1}L^{2}\sum_{j=1}^{t}\eta_{j}^{2}\Big{)}\Big{(}\sum_{k=1}^{t}\eta_{k}^{2}\Big{)}^{\frac{1}{2}}.$

  3. (c)

Let $\eta_{t}=\eta$. If Assumption 1 holds, then $A$ is $\epsilon$-argument-
stable with probability at least $1-\delta$, where

$\\!\\!\\!\epsilon\leq\sqrt{8e}G\eta\Big{(}\sqrt{t}+t/n+\log(1/\delta)+\sqrt{2tn^{-1}\log(1/\delta)}\Big{)}.$

  4. (d)

Let $\eta_{t}=\eta$. If Assumptions 1, 2 hold, then $A$ is
$\epsilon$-argument-stable with probability at least $1-\delta$, where

$\epsilon\leq\sqrt{8e}G\eta\exp\big{(}2^{-1}L^{2}t\eta^{2}\big{)}\times\\\
\Big{(}1+t/n+\log(1/\delta)+\sqrt{2tn^{-1}\log(1/\delta)}\Big{)}.$

  5. (e)

If $(\mathbf{w},\mathbf{v})\mapsto f(\mathbf{w},\mathbf{v};z)$ is $\rho$-SC-
SC, Assumption 1 holds and $\eta_{t}=1/(\rho t)$, then $A$ is
$\epsilon$-argument-stable in expectation, where
$\epsilon\leq\frac{2\sqrt{2}G}{\rho}\big{(}\frac{\log(et)}{t}+\frac{1}{n(n-2)}\big{)}^{\frac{1}{2}}.$

######  Remark 3.

If $t=O(n^{2})$, then the stability bounds in a nonsmooth case (Part a) become
$O(\eta\sqrt{t})$ and we can still get non-vacuous bounds by taking small step
size $\eta=o(t^{-1/2})$. If we choose $\eta_{j}=1/\sqrt{t}$ for $j\in[t]$,
then the stability bound in Part (b) under a further smoothness assumption
becomes $O(\sqrt{t}/n+n^{-\frac{1}{2}})$, which matches the existing result
for SGD in a convex setting (Hardt et al., 2016). The high-probability bounds
in Part (c) and Part (d) enjoy the same behavior.

######  Remark 4.

The stability bounds of SGDA and GDA were discussed in Farnia & Ozdaglar
(2020) for SC-SC, Lipschitz continuous and smooth problems. We remove the
smoothness assumption in Part (e) in the SC-SC case. The stability of GDA was
also studied there for convex-concave $f$, which, however, implies non-
vanishing generalization bounds growing exponentially with the iteration count
(Farnia & Ozdaglar, 2020). We extend their discussions to SGDA in this convex-
concave case, and, as we will show in Theorem 3, our stability bounds imply
optimal bounds on PD population risks. Furthermore, the existing discussions
(Farnia & Ozdaglar, 2020) require the function $f$ to be smooth, while we show
that meaningful stability bounds can be achieved in a nonsmooth setting (Parts
(a), (c), (e)).

######  Remark 5.

We consider stability bounds under various assumptions on loss functions. We
now sketch the technical difference in our analysis. Let
$\delta_{t}:=\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\|_{2}^{2}+\|\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\|_{2}^{2}$,
where
$(\mathbf{w}_{t},\mathbf{v}_{t}),(\mathbf{w}_{t}^{\prime},\mathbf{v}_{t}^{\prime})$
are SGDA iterates for $S$ and $S^{\prime}$ differing only by the last element.
For convex-concave and nonsmooth problems, we show
$\delta_{t+1}=\delta_{t}+O(\eta_{t}^{2})$ if $i_{t}\neq n$. For convex-concave
and smooth problems, we show $\delta_{t+1}=(1+O(\eta_{t}^{2}))\delta_{t}$ if
$i_{t}\neq n$. For $\rho$-SC-SC and nonsmooth problems, we show
$\delta_{t+1}=(1-2\rho\eta_{t})\delta_{t}+O(\eta_{t}^{2})$ if $i_{t}\neq n$.
For the above cases, we first control $\delta_{t+1}$ and then take expectation
w.r.t. $i_{t}$. A key point to tackle _nonsmooth_ problems is to consider the
evolution $\delta_{t}$ instead of
$\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\|_{2}+\|\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\|_{2}$,
which is able to yield nontrivial bounds by making $\sum_{t}\eta_{t}^{2}=o(1)$
with sufficiently small $\eta_{t}$.

###  4.2 Population Risks

We now use stability bounds in Theorem 2 to develop error bounds of SGDA which
outputs an average of iterates

$\bar{\mathbf{w}}_{T}=\frac{\sum_{t=1}^{T}\eta_{t}\mathbf{w}_{t}}{\sum_{t=1}^{T}\eta_{t}}\
\text{ and }\
\bar{\mathbf{v}}_{T}=\frac{\sum_{t=1}^{T}\eta_{t}\mathbf{v}_{t}}{\sum_{t=1}^{T}\eta_{t}}.$
(4.2)

The underlying reason to introduce the average operator is to simplify the
optimization error analysis (Nemirovski et al., 2009). Indeed, our stability
and generalization analysis applies to any individual iterates. As a
comparison, the optimization error analysis for the last iterate is much more
difficult than that for the averaged iterate. We use the notation
$B\asymp\widetilde{B}$ if there exist constants $c_{1},c_{2}>0$ such that
$c_{1}\widetilde{B}<B\leq c_{2}\widetilde{B}$. The following theorem to be
proved in Appendix E gives weak PD population risk bounds.

######  Theorem 3 (Weak PD risk).

Let $\\{\mathbf{w}_{t},\mathbf{v}_{t}\\}$ be produced by (4.1). Assume for all
$z$, the function $(\mathbf{w},\mathbf{v})\mapsto f(\mathbf{w},\mathbf{v};z)$
is convex-concave. Let $A$ be defined by
$A_{\mathbf{w}}(S)=\bar{\mathbf{w}}_{T}$ and
$A_{\mathbf{v}}(S)=\bar{\mathbf{v}}_{T}$ for
$(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})$ in (4.2). Assume
$\sup_{\mathbf{w}\in\mathcal{W}}\|\mathbf{w}\|_{2}\leq B_{W}$ and
$\sup_{\mathbf{v}\in\mathcal{V}}\|\mathbf{v}\|_{2}\leq B_{V}$.

  1. (a)

If $\eta_{t}=\eta$ and Assumption 1 holds, then

$\triangle^{w}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})\leq 4\sqrt{2}\eta
G^{2}\Big{(}\sqrt{T}+\frac{T}{n}\Big{)}+\eta G^{2}\\\
+\frac{B_{W}^{2}+B_{V}^{2}}{2\eta T}+\frac{G(B_{W}+B_{V})}{\sqrt{T}}.$ (4.3)

If we choose $T\asymp n^{2}$ and $\eta\asymp T^{-3/4}$, then we get
$\triangle^{w}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})=O(n^{-1/2})$.

  2. (b)

If $\eta_{t}=\eta$ and Assumptions 1, 2 hold, then

$\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\triangle^{w}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})\leq\frac{4\sqrt{e(T+T^{2}/n)}G^{2}\eta\exp\big{(}LT\eta^{2}/2\big{)}}{\sqrt{n}}\\\
+\eta G^{2}+\frac{B_{W}^{2}+B_{V}^{2}}{2\eta
T}+\frac{G(B_{W}+B_{V})}{\sqrt{T}}.$ (4.4)

We can choose $T\asymp n$ and $\eta\asymp T^{-1/2}$ to derive
$\triangle^{w}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})=O(n^{-1/2})$.

  3. (c)

If $(\mathbf{w},\mathbf{v})\mapsto f(\mathbf{w},\mathbf{v};z)$ is $\rho$-SC-SC
($\rho>0$), Assumption 1 holds, $\eta_{t}=1/(\rho t)$ and $T\asymp n^{2}$,
then

$\triangle^{w}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})=O(\sqrt{\log
n}/(n\rho)).$

  4. (d)

If $(\mathbf{w},\mathbf{v})\mapsto f(\mathbf{w},\mathbf{v};z)$ is $\rho$-SC-SC
($\rho>0$), Assumptions 1, 2 hold, $\eta_{t}=1/(\rho(t+t_{0}))$ with
$t_{0}\geq L^{2}/\rho^{2}$ and $T\asymp n$, then
$\triangle^{w}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})=O(\log(n)/(n\rho))$.

######  Remark 6.

We first compare our bounds with the related work in a convex-concave setting.
Weak PD population risk bounds were established for PPM under Assumptions 1, 2
(Farnia & Ozdaglar, 2020), which updates
$(\mathbf{w}_{t+1}^{\text{PPM}},\mathbf{v}_{t+1}^{\text{PPM}})$ as the saddle
point of the following minimax problem

$\min_{\mathbf{w}\in\mathcal{W}}\max_{\mathbf{v}\in\mathcal{V}}F_{S}(\mathbf{w},\mathbf{v})+\frac{1}{2\eta_{t}}\|\mathbf{w}-\mathbf{w}_{t}^{\text{PPM}}\|_{2}^{2}+\frac{1}{2\eta_{t}}\|\mathbf{v}-\mathbf{v}_{t}^{\text{PPM}}\|_{2}^{2}.$

In particular, they developed population risk bounds $O(1/\sqrt{n})$ by taking
$T\asymp\sqrt{n}$ for PPM. However, the implementation of PPM requires to find
the exact saddle point at each iteration, which is often computationally
expensive. As a comparison, Part (b) shows the minimax optimal population risk
bounds $O(1/\sqrt{n})$ for SGDA with $O(n)$ iterations. Weak PD population
risk bounds $O(1/\sqrt{n})$ were established for R-ESP (Zhang et al., 2020)
without a smoothness assumption, which, however, ignore the interplay between
generalization and optimization. In this setting, we show SGDA achieves the
same population risk bounds $O(1/\sqrt{n})$ by taking $\eta\asymp T^{-3/4}$
and $T\asymp n^{2}$ in Part (a). We now consider the SC-SC setting. Weak PD
risk bounds $O(1/(n\rho))$ were established for ESP (Zhang et al., 2020).
Since Farnia & Ozdaglar (2020) did not present an explicit risk bound, we use
their stability analysis to give an explicit risk bound $O(\log(n)/(n\rho))$
in the smooth case (Part (d)). As a comparison, we establish the same
population risk bounds for SGDA within a logarithmic factor by taking
$\eta_{t}=1/(\rho t)$ and $T\asymp n^{2}$ without the smoothness assumption
(Part (c)).

We further develop bounds on primal population risks under a strong concavity
assumption on $\mathbf{v}\mapsto F(\mathbf{w},\mathbf{v})$. Primal risk bounds
measure the performance of primal variables, which are of real interest in
some learning problems, e.g., AUC maximization and robust optimization. We
consider both bounds in expectation and bounds with high probability. Let
$(\mathbf{w}^{*},\mathbf{v}^{*})$ be a saddle point of $F$, i.e., for any
$\mathbf{w}\in\mathcal{W}$ and $\mathbf{v}\in\mathcal{V}$, there holds
$F(\mathbf{w}^{*},\mathbf{v})\leq F(\mathbf{w},\mathbf{v})\leq
F(\mathbf{w},\mathbf{v}^{*})$.

######  Theorem 4 (Excess primal risk).

Let $\\{\mathbf{w}_{t},\mathbf{v}_{t}\\}$ be produced by (4.1) with
$\eta_{t}=\eta$. Assume for all $z$, the function
$(\mathbf{w},\mathbf{v})\mapsto f(\mathbf{w},\mathbf{v};z)$ is convex-concave
and the function $\mathbf{v}\mapsto F(\mathbf{w},\mathbf{v})$ is
$\rho$-strongly-concave. Assume
$\sup_{\mathbf{w}\in\mathcal{W}}\|\mathbf{w}\|_{2}\leq B_{W}$ and
$\sup_{\mathbf{v}\in\mathcal{V}}\|\mathbf{v}\|_{2}\leq B_{V}$. Let the
algorithm $A$ be defined by $A_{\mathbf{w}}(S)=\bar{\mathbf{w}}_{T}$ and
$A_{\mathbf{v}}(S)=\bar{\mathbf{v}}_{T}$ for
$(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})$ in (4.2). If Assumptions 1, 2
hold, then

$\\!\\!\\!\\!\mathbb{E}\big{[}R(\bar{\mathbf{w}}_{T})\big{]}-\inf_{\mathbf{w}}R(\mathbf{w})\leq\eta
G^{2}+\frac{B_{W}^{2}\\!+\\!B_{V}^{2}}{2\eta
T}+\frac{G(B_{W}\\!+\\!B_{V})}{\sqrt{T}}\\\
+\frac{(1+L/\rho)\sqrt{32e(T+T^{2}/n)}G^{2}\eta\exp\big{(}L^{2}T\eta^{2}/2\big{)}}{\sqrt{n}}.$

In particular, if we choose $T\asymp n$ and $\eta\asymp T^{-1/2}$ then

$\mathbb{E}\big{[}R(\bar{\mathbf{w}}_{T})\big{]}-\inf_{\mathbf{w}\in\mathcal{W}}R(\mathbf{w})=O((L/\rho)n^{-1/2}).$
(4.5)

Furthermore, for any $\delta\in(0,1)$ we can choose $T\asymp n$ and
$\eta\asymp T^{-1/2}$ to show with probability at least $1-\delta$

$\\!\\!\\!\\!R(\bar{\mathbf{w}}_{T})\\!-\\!R(\mathbf{w}^{*})=O\Big{(}(L/\rho)n^{-\frac{1}{2}}\log
n\log^{2}(1/\delta)\Big{)}.$ (4.6)

Theorem 4 is proved in Appendix E. In Theorem E.1, we also develop high-
probability bounds of order ${O}(n^{-\frac{1}{2}}\log n)$ on plain
generalization errors
$|F(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})-F(\mathbf{w}^{*},\mathbf{v}^{*})|$.

##  5 Nonconvex-Nonconcave Objectives

In this section, we extend our analysis to nonconvex-nonconcave minimax
learning problems.

###  5.1 Stability and Generalization of SGDA

We first study the generalization bounds of SGDA for WC-WC problems. The proof
is given in Appendix F.1. In Appendix F.2, we further give high-probability
bounds.

######  Theorem 5 (Weak generalization bound).

Let $\\{\mathbf{w}_{t},\mathbf{v}_{t}\\}$ be produced by (4.1) with $T$
iterations. Assume for all $z$, the function $(\mathbf{w},\mathbf{v})\mapsto
f(\mathbf{w},\mathbf{v};z)$ is $\rho$-WC-WC and $|f(\cdot,\cdot;z)|\leq 1$. If
Assumption 1 holds and $\eta_{t}=c/t$, then the weak PD generalization error
of SGDA is bounded by

$\displaystyle
O\Big{(}\Big{(}1+\frac{\sqrt{T}}{n}\Big{)}T^{c\rho}\Big{)}^{\frac{2}{2c\rho+3}}\Big{(}\frac{1}{n}\Big{)}^{\frac{2c\rho+1}{2c\rho+3}}.$

######  Remark 7.

If $T=O(n^{2})$, our weak PD generalization error bound is of the order
$O\big{(}n^{-\frac{2c\rho+1}{2c\rho+3}}T^{\frac{2c\rho}{2c\rho+3}}\big{)}$.
This is the first generalization bound of SGDA for nonsmooth and nonconvex-
nonconcave objectives. Farnia & Ozdaglar (2020) also studied generalization
under nonconvex-nonconcave setting but required the objectives to be smooth,
which is relaxed to a milder WC-WC assumption here. Our analysis readily
applies to stochastic gradient descent (SGD) with nonsmooth weakly-convex
functions, which has not been studied in the literature.

We further consider a variant of weak-convexity-weak-concavity. The proof is
given in Appendix F.3.

######  Theorem 6 (Weak generalization bound).

Let $\\{\mathbf{w}_{t},\mathbf{v}_{t}\\}$ be produced by (4.1) with $T$
iterations. Let Assumptions 1, 2 hold. Assume there are non-negative numbers
$\\{\rho_{t}\\}_{t\in\mathbb{N}}$ such that the following inequality holds
a.s.

$\Big{\langle}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}\\\
\mathbf{v}_{t}-\mathbf{v}\end{pmatrix},\begin{pmatrix}\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w},\mathbf{v})\\\
\nabla_{\mathbf{v}}F_{S}(\mathbf{w},\mathbf{v})-\nabla_{\mathbf{v}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\end{pmatrix}\Big{\rangle}\\\
\geq-\rho_{t}\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}\\\
\mathbf{v}_{t}-\mathbf{v}\end{pmatrix}\right\|_{2}^{2},\;\forall\mathbf{w}\in\mathcal{W},\mathbf{v}\in\mathcal{V}.$
(5.1)

Then the weak PD generalization error of SGDA with $T$ iterations can be
bounded by

$O\Big{(}n^{-1}\sum_{t=1}^{T}\Big{(}\eta_{t}^{2}+\frac{1}{n}\Big{)}\exp\Big{(}\sum_{k=t+1}^{T}\big{(}2\rho_{k}\eta_{k}+(L^{2}+1)\eta_{k}^{2}\big{)}\Big{)}\Big{)}^{\frac{1}{2}}.$

Eq. (5.1) allows the empirical objective $F_{S}$ to have varying weak-
convexity-weak-concavity at different iterates encountered by the algorithm.
This is motivated by the observation that the nonconvex-nonconcave function
can have approximate convexity-concavity around a saddle point. For these
problems, we can expect the weak-convexity-weak-concavity parameter $\rho_{t}$
to decrease along the optimization process (Sagun et al., 2017, Yuan et al.,
2019).

######  Remark 8.

If $F_{S}$ is convex-concave, then $\rho_{t}=0$ and we can take
$\eta_{t}\asymp 1/\sqrt{T}$ to show that SGDA with $T$ iterations enjoys the
generalization bound $O\big{(}1/\sqrt{n}+\sqrt{T}/n\big{)}$. This extends
Theorem 3 since we only require the convexity-concavity of $F_{S}$ here
instead of $f(\cdot,\cdot;z)$ for all $z$ in Theorem 3. If
$\rho_{t}=O(t^{-\alpha})$ ($\alpha\in(0,1)$), then we can take $\eta_{t}\asymp
t^{\min\\{\alpha-1,-\frac{1}{2}\\}}/\log T$ (note
$\sum_{t=1}^{T}\eta_{t}^{2}=O(1),\sum_{t=1}^{T}\eta_{t}\rho_{t}=O(1)$) to show
that SGDA with $T$ iterations enjoys the weak PD generalization bound
$O\big{(}1/\sqrt{n}+\sqrt{T}/n\big{)}$. As compared to Theorem 5, the
assumption (5.1) allows us to use much larger step sizes
($O(t^{-\beta}),\beta\in(0,1)$ vs $O(t^{-1})$). This larger step size allows
for a better trade-off between generalization and optimization. We note that a
recent work (Richards & Rabbat, 2021) considered gradient descent under an
assumption similar to (5.1), and developed interesting generalization bounds
for $\eta_{t}=O(t^{-\beta})$ ($\beta\in(0,1)$). However, their discussions do
not apply to the important SGD and require an additional assumption on the
Lipschitz continuity of Hessian matrix which may be restrictive. It is direct
to extend Theorem 6 to SGD for learning with weakly-convex functions for
relaxing the step size under Eq. (5.1). Therefore, our stability analysis even
gives novel results in the standard nonconvex learning setting. We introduce a
novel technique in achieving this improvement. Specifically, let
$\delta_{t}:=\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\|_{2}^{2}+\|\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\|_{2}^{2}$,
where
$(\mathbf{w}_{t},\mathbf{v}_{t}),(\mathbf{w}_{t}^{\prime},\mathbf{v}_{t}^{\prime})$
are SGDA iterates for neighboring datasets $S$ and $S^{\prime}$. For the
stability bounds in Section 4.1, we first handle $\delta_{t+1}$ according to
different realizations of $i_{t}$ and then consider the expectation w.r.t.
$i_{t}$. While for $\rho$-WC-WC problems, we first take expectation w.r.t.
$i_{t}$ and then show how $\mathbb{E}_{i_{t}}[\delta_{t+1}]$ would change
along the iterations.

###  5.2 Stability and Generalization of AGDA and Beyond

We now study the Alternating Gradient Descent Ascent (AGDA) proposed recently
to optimize nonconvex-nonconcave problems Yang et al. (2020). Let
$\\{\eta_{\mathbf{w},t},\eta_{\mathbf{v},t}\\}_{t}$ be a sequence of positive
stepsizes for updating $\\{\mathbf{w}_{t},\mathbf{v}_{t}\\}_{t}$. At each
iteration, we randomly draw $i_{t}$ and $j_{t}$ from the uniform distribution
over $[n]$ and do the update

$\begin{cases}\mathbf{w}_{t+1}=\text{Proj}_{\mathcal{W}}\big{(}\mathbf{w}_{t}-\eta_{\mathbf{w},t}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\big{)},&\\\
\mathbf{v}_{t+1}=\text{Proj}_{\mathcal{V}}\big{(}\mathbf{v}_{t}+\eta_{\mathbf{v},t}\nabla_{\mathbf{v}}f(\mathbf{w}_{t+1},\mathbf{v}_{t};z_{j_{t}})\big{)}.&\end{cases}$
(5.2)

This algorithm differs from SGDA in two aspects. First, it randomly selects
two examples to update $\mathbf{w}$ and $\mathbf{v}$ per iteration. Second, it
uses the updated $\mathbf{w}_{t+1}$ when updating $\mathbf{v}_{t+1}$. Theorem
7 to be proved in Appendix G provides generalization bounds for AGDA.

######  Theorem 7 (Weak generalization bounds).

Let $\\{\mathbf{w}_{t},\mathbf{v}_{t}\\}$ be the sequence produced by (5.2).
If Assumptions 1, 2 hold and
$\eta_{\mathbf{w},t}+\eta_{\mathbf{v},t}\leq\frac{c}{t}$ for some $c>0$, then
the weak PD generalization error can be upper bounded by
$O\big{(}n^{-1}T^{\frac{cL}{cL+1}}\big{)}.$

Global convergence of AGDA was studied based on the two-sided PL condition
defined below (Yang et al., 2020), which means the suboptimality of function
values can be bounded by gradients and were shown for several rich classes of
functions (Karimi et al., 2016). We also refer to the two-sided PL condition
as the gradient dominance condition.

######  Assumption 3.

Assume $F_{S}$ satisfies the two-sided PL condition, i.e., there exist
constants $\beta_{1}(S),\beta_{2}(S)>0$ such that the following inequalities
hold for all $\mathbf{w}\in\mathcal{W},\mathbf{v}\in\mathcal{V}$

$2\beta_{1}(S)\big{(}F_{S}(\mathbf{w},\mathbf{v})-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}F_{S}(\mathbf{w}^{\prime},\mathbf{v})\big{)}\leq\|\nabla_{\mathbf{w}}F_{S}(\mathbf{w},\mathbf{v})\|_{2}^{2},$
$2\beta_{2}(S)\big{(}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}(\mathbf{w},\mathbf{v}^{\prime})-F_{S}(\mathbf{w},\mathbf{v})\big{)}\leq\|\nabla_{\mathbf{v}}F_{S}(\mathbf{w},\mathbf{v})\|_{2}^{2}.$

As a combination of our generalization bounds and optimization error bounds in
Yang et al. (2020), we can derive the following informal corollary on primal
population risks by early stopping the algorithm to balance the optimization
and generalization. It gives the first primal risk bounds for learning with
nonconvex-strongly-concave functions. The precise statement can be found in
Corollary G.3.

######  Corollary 8 (Informal).

Let $\beta_{1},\rho>0$. Assume for all $\mathbf{w}$, the function
$\mathbf{v}\mapsto F(\mathbf{w},\mathbf{v})$ is $\rho$-strongly concave. Let
Assumptions 1, 2, 3 with $\beta_{1}(S)\geq\beta_{1},\beta_{2}(S)\geq\rho$
hold. Then AGDA with some appropriate step size and
$T\asymp\big{(}n\beta_{1}^{-2}\rho^{-3}\big{)}^{\frac{cL+1}{2cL+1}}$ satisfy
($c\asymp 1/(\beta_{1}\rho^{2})$)

$\mathbb{E}\big{[}R(\mathbf{w}_{T})\big{]}-R(\mathbf{w}^{*})=O\Big{(}n^{-\frac{cL+1}{2cL+1}}\beta_{1}^{-\frac{2cL}{2cL+1}}\rho^{-\frac{5cL+1}{2cL+1}}\Big{)}.$

For gradient dominated problems, we further have the following error bounds to
be proved in Appendix H. Note we do not need the smoothness assumption here.

######  Theorem 9.

Let $A$ be an algorithm. Let Assumptions 1, 3 hold. Let
$\mathbf{u}_{S}=(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))$ and
$\mathbf{u}_{S}^{(S)}$ be the projection of $\mathbf{u}_{S}$ onto the set of
stationary points of $F_{S}$. Then,

$\big{|}\mathbb{E}\big{[}F(\mathbf{u}_{S})-F_{S}(\mathbf{u}_{S})\big{]}\big{|}\leq\frac{2G^{2}}{n}\max\Big{\\{}\mathbb{E}\big{[}1/{\beta_{1}(S)}\big{]},\\\
\mathbb{E}\big{[}1/{\beta_{2}(S)}\big{]}\Big{\\}}+2G\mathbb{E}\big{[}\|\mathbf{u}_{S}-\mathbf{u}_{S}^{(S)}\|_{2}\big{]}.$

######  Remark 9.

Note $\|\mathbf{u}_{S}-\mathbf{u}_{S}^{(S)}\|_{2}$ measures how far the point
found by $A$ is from the set of stationary points of $F_{S}$, and can be
interpreted as an optimization error. Therefore, Theorem 9 gives a connection
between generalization error and optimization error. For a variant of AGDA
with noiseless stochastic gradients, it was shown that
$\|(\mathbf{w}_{T},\mathbf{v}_{T})-(\mathbf{w}_{T},\mathbf{v}_{T})^{(S)}\|_{2}$
decays linearly w.r.t. $T$ (Yang et al., 2020). We can plug this linear
convergent optimization bound into Theorem 9 to directly get generalization
bounds. If $A$ returns a saddle point of $F_{S}$, then
$\|\mathbf{u}_{S}-\mathbf{u}_{S}^{(S)}\|_{2}=0$ and therefore
$\big{|}\mathbb{E}\big{[}F(\mathbf{u}_{S})-F_{S}(\mathbf{u}_{S})\big{]}\big{|}=O\big{(}n^{-1}\max\\{\mathbb{E}[1/\beta_{1}(S)],\mathbb{E}[1/\beta_{2}(S)]\\}\big{)}$.
Generalization errors of this particular ESP were studied in Zhang et al.
(2020) for SC-SC minimax problems, which were extended to more general
gradient-dominated problems in Theorem 9. Furthermore, Theorem 9 applies to
any optimization algorithm instead of the specific ESP. It should be mentioned
that Zhang et al. (2020) addressed PD population risks, while we consider
plain generalization errors.

##  6 Experiments

In this subsection, we report preliminary experimental results to validate our
theoretical results222The source codes are available at
https://github.com/zhenhuan-yang/minimax-stability.. We consider two datasets
available at the LIBSVM website: svmguide3 and w5a (Chang & Lin, 2011). We
follow the experimental setup in Hardt et al. (2016) to study how the
stability of SGDA would behave along the learning process. To this end, we
build a neighboring dataset $S^{\prime}$ by changing the last example of the
training set $S$. We apply the same randomized algorithm to $S$ and
$S^{\prime}$ and get two model sequences
$\\{(\mathbf{w}_{t},\mathbf{v}_{t})\\}$ and
$\\{(\mathbf{w}_{t}^{\prime},\mathbf{v}_{t}^{\prime})\\}$. Then we evaluate
the Euclidean distance
$\triangle_{t}=\big{(}\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\|_{2}^{2}+\|\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\|_{2}^{2}\big{)}^{\frac{1}{2}}$.
We consider the SOLAM (Ying et al., 2016) algorithm, which is the SGDA for the
solving the problem (2.3) (a minimax reformulation of the AUC maximization
problem). We consider step sizes $\eta_{t}=\eta/\sqrt{T}$ with
$\eta\in\\{0.1,0.3,1,3\\}$. We repeat the experiments 25 times and report the
average of the experimental results as well as the standard deviation. In
Figure 1, we report $\triangle_{t}$ as a function of the number of passes (the
iteration number divided by $n$). It is clear that the Euclidean distance
continues to increase during the learning process. Furthermore, the Euclidean
distances increase if we consider larger step sizes. This phenomenon is
consistent with our stability bounds in Theorem 2. More experiments on the
stability of SGDA in GAN training can be found in Appendix I.

Figure 1: $\triangle_{t}$ versus the number of passes on svmguide3 (left) and
w5a (right).

##  7 Conclusion

We presented a comprehensive stability and generalization analysis of
stochastic algorithms for minimax objective functions. We introduced various
generalization measures and stability measures, and present a systematic study
on their quantitative relationship. In particular, we obtained the first
minimax optimal risk bounds for SGDA in a general convex-concave case,
covering both smooth and nonsmooth setting. We also derived the first non-
trivial risk bounds for nonconvex-nonconcave problems. Our bounds show how to
early-stop the algorithm in practice to train a model with better
generalization. Our theoretical results have potential applications in
developing differentially private algorithms to handle sensitive data.

There are some interesting problems for further investigation. Our primal
generalization bounds require a strong concavity assumption. It is interesting
to remove this assumption. On the other front, it remains an open question to
us on understanding how the concavity of dual variables can help
generalization in a nonconvex setting.

## Acknowledgments

We are grateful to the anonymous reviewers for their constructive comments and
suggestions. The work of Yiming Ying is partially supported by NSF grants
IIS-1816227 and IIS-2008532. The work of Tianbao Yang is partially supported
by NSF #1933212 and NSF CAREER Award #1844403.

## References

  * Arjovsky et al. (2017) Arjovsky, M., Chintala, S., and Bottou, L.  Wasserstein generative adversarial networks.  In _International Conference on Machine Learning_ , pp. 214–223, 2017.
  * Audibert & Catoni (2011) Audibert, J.-Y. and Catoni, O.  Robust linear least squares regression.  _Annals of Statistics_ , 39(5):2766–2794, 2011\.
  * Balamurugan & Bach (2016) Balamurugan, P. and Bach, F.  Stochastic variance reduction methods for saddle-point problems.  In _Advance In Neural Information Processing Systems_ , pp. 1416–1424, 2016.
  * Bassily et al. (2020) Bassily, R., Feldman, V., Guzmán, C., and Talwar, K.  Stability of stochastic gradient descent on nonsmooth convex losses.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Bousquet & Bottou (2008) Bousquet, O. and Bottou, L.  The tradeoffs of large scale learning.  In _Advances in Neural Information Processing Systems_ , pp. 161–168, 2008.
  * Bousquet & Elisseeff (2002) Bousquet, O. and Elisseeff, A.  Stability and generalization.  _Journal of Machine Learning Research_ , 2:499–526, 2002\.
  * Bousquet et al. (2020) Bousquet, O., Klochkov, Y., and Zhivotovskiy, N.  Sharper bounds for uniformly stable algorithms.  In _Conference on Learning Theory_ , pp. 610–626, 2020.
  * Brownlees et al. (2015) Brownlees, C., Joly, E., Lugosi, G., et al.  Empirical risk minimization for heavy-tailed losses.  _The Annals of Statistics_ , 43(6):2507–2536, 2015.
  * Chang & Lin (2011) Chang, C.-C. and Lin, C.-J.  Libsvm: a library for support vector machines.  _ACM Transactions on Intelligent Systems and Technology_ , 2(3):27, 2011.
  * Charles & Papailiopoulos (2018) Charles, Z. and Papailiopoulos, D.  Stability and generalization of learning algorithms that converge to global optima.  In _International Conference on Machine Learning_ , pp. 744–753, 2018.
  * Chen et al. (2017) Chen, R. S., Lucier, B., Singer, Y., and Syrgkanis, V.  Robust optimization for non-convex objectives.  In _Advances in Neural Information Processing Systems_ , pp. 4705–4714, 2017.
  * Chen et al. (2018) Chen, Y., Jin, C., and Yu, B.  Stability and convergence trade-off of iterative optimization algorithms.  _arXiv preprint arXiv:1804.01619_ , 2018.
  * Chernoff (1952) Chernoff, H.  A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.  _Annals of Mathematical Statistics_ , 23(4):493–507, 1952.
  * Dai et al. (2018) Dai, B., Shaw, A., Li, L., Xiao, L., He, N., Liu, Z., Chen, J., and Song, L.  Sbeed: Convergent reinforcement learning with nonlinear function approximation.  In _International Conference on Machine Learning_ , pp. 1125–1134, 2018.
  * Deng et al. (2020) Deng, Z., He, H., and Su, W. J.  Toward better generalization bounds with locally elastic stability.  _arXiv preprint arXiv:2010.13988_ , 2020.
  * Du et al. (2017) Du, S. S., Chen, J., Li, L., Xiao, L., and Zhou, D.  Stochastic variance reduction methods for policy evaluation.  In _International Conference on Machine Learning_ , pp. 1049–1058, 2017.
  * Elisseeff et al. (2005) Elisseeff, A., Evgeniou, T., and Pontil, M.  Stability of randomized learning algorithms.  _Journal of Machine Learning Research_ , 6(Jan):55–79, 2005.
  * Farnia & Ozdaglar (2020) Farnia, F. and Ozdaglar, A.  Train simultaneously, generalize better: Stability of gradient-based minimax learners.  _arXiv preprint arXiv:2010.12561_ , 2020.
  * Feldman & Vondrak (2019) Feldman, V. and Vondrak, J.  High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.  In _Conference on Learning Theory_ , pp. 1270–1279, 2019.
  * Foster et al. (2019) Foster, D. J., Greenberg, S., Kale, S., Luo, H., Mohri, M., and Sridharan, K.  Hypothesis set stability and generalization.  In _Advances in Neural Information Processing Systems_ , pp. 6726–6736. 2019.
  * Gao et al. (2013) Gao, W., Jin, R., Zhu, S., and Zhou, Z.-H.  One-pass auc optimization.  In _International Conference on Machine Learning_ , pp. 906–914, 2013.
  * Goodfellow et al. (2014) Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y.  Generative adversarial nets.  _Advances in Neural Information Processing Systems_ , 27:2672–2680, 2014.
  * Hardt et al. (2016) Hardt, M., Recht, B., and Singer, Y.  Train faster, generalize better: Stability of stochastic gradient descent.  In _International Conference on Machine Learning_ , pp. 1225–1234, 2016.
  * Hoeffding (1963) Hoeffding, W.  Probability inequalities for sums of bounded random variables.  _Journal of the American Statistical Association_ , 58(301):13–30, 1963.
  * Hsieh et al. (2019) Hsieh, Y.-G., Iutzeler, F., Malick, J., and Mertikopoulos, P.  On the convergence of single-call stochastic extra-gradient methods.  In _Advances in Neural Information Processing Systems_ , pp. 6938–6948, 2019.
  * Karimi et al. (2016) Karimi, H., Nutini, J., and Schmidt, M.  Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition.  In _European Conference on Machine Learning_ , pp. 795–811, 2016\.
  * Kuzborskij & Lampert (2018) Kuzborskij, I. and Lampert, C.  Data-dependent stability of stochastic gradient descent.  In _International Conference on Machine Learning_ , pp. 2820–2829, 2018.
  * LeCun et al. (1998) LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Lei & Ying (2020) Lei, Y. and Ying, Y.  Fine-grained analysis of stability and generalization for stochastic gradient descent.  In _International Conference on Machine Learning_ , pp. 5809–5819, 2020.
  * Lei & Ying (2021a) Lei, Y. and Ying, Y.  Sharper generalization bounds for learning with gradient-dominated objective functions.  In _International Conference on Learning Representations_ , 2021a.
  * Lei & Ying (2021b) Lei, Y. and Ying, Y.  Stochastic proximal auc maximization.  _Journal of Machine Learning Research_ , 22(61):1–45, 2021b.
  * Li et al. (2020) Li, J., Luo, X., and Qiao, M.  On generalization error bounds of noisy gradient methods for non-convex learning.  In _International Conference on Learning Representations_ , 2020.
  * Lin et al. (2016) Lin, J., Camoriano, R., and Rosasco, L.  Generalization properties and implicit regularization for multiple passes SGM.  In _International Conference on Machine Learning_ , pp. 2340–2348, 2016.
  * Lin et al. (2020) Lin, T., Jin, C., and Jordan, M.  On gradient descent ascent for nonconvex-concave minimax problems.  In _International Conference on Machine Learning_ , pp. 6083–6093, 2020.
  * Liu et al. (2018) Liu, M., Zhang, X., Chen, Z., Wang, X., and Yang, T.  Fast stochastic AUC maximization with O(1/n)-convergence rate.  In _International Conference on Machine Learning_ , pp. 3195–3203, 2018.
  * Liu et al. (2020) Liu, M., Rafique, H., Lin, Q., and Yang, T.  First-order convergence theory for weakly-convex-weakly-concave min-max problems, 2020.
  * Liu et al. (2017) Liu, T., Lugosi, G., Neu, G., and Tao, D.  Algorithmic stability and hypothesis complexity.  In _International Conference on Machine Learning_ , pp. 2159–2167, 2017.
  * Loizou et al. (2020) Loizou, N., Berard, H., Jolicoeur-Martineau, A., Vincent, P., Lacoste-Julien, S., and Mitliagkas, I.  Stochastic hamiltonian gradient methods for smooth games.  In _International Conference on Machine Learning_ , pp. 6370–6381, 2020.
  * London (2017) London, B.  A PAC-bayesian analysis of randomized learning with application to stochastic gradient descent.  In _Advances in Neural Information Processing Systems_ , pp. 2931–2940, 2017.
  * Luo et al. (2020) Luo, L., Ye, H., Huang, Z., and Zhang, T.  Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Madden et al. (2020) Madden, L., Dall’Anese, E., and Becker, S.  High probability convergence and uniform stability bounds for nonconvex stochastic gradient descent.  _arXiv preprint arXiv:2006.05610_ , 2020.
  * Mou et al. (2018) Mou, W., Wang, L., Zhai, X., and Zheng, K.  Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints.  In _Conference on Learning Theory_ , pp. 605–638, 2018.
  * Namkoong & Duchi (2017) Namkoong, H. and Duchi, J. C.  Variance-based regularization with convex objectives.  In _Advances in Neural Information Processing Systems_ , pp. 2971–2980, 2017.
  * Nedić & Ozdaglar (2009) Nedić, A. and Ozdaglar, A.  Subgradient methods for saddle-point problems.  _Journal of Optimization Theory and Applications_ , 142(1):205–228, 2009.
  * Nemirovski et al. (2009) Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A.  Robust stochastic approximation approach to stochastic programming.  _SIAM Journal on Optimization_ , 19(4):1574–1609, 2009.
  * Rafique et al. (2018) Rafique, H., Liu, M., Lin, Q., and Yang, T.  Non-convex min-max optimization: Provable algorithms and applications in machine learning.  _arXiv preprint arXiv:1810.02060_ , 2018.
  * Raghavan (1988) Raghavan, P.  Probabilistic construction of deterministic algorithms: approximating packing integer programs.  _Journal of Computer and System Sciences_ , 37(2):130–143, 1988.
  * Rakhlin et al. (2005) Rakhlin, A., Mukherjee, S., and Poggio, T.  Stability results in learning theory.  _Analysis and Applications_ , 3(04):397–417, 2005\.
  * Richards & Rabbat (2021) Richards, D. and Rabbat, M.  Learning with gradient descent and weakly convex losses.  _arXiv preprint arXiv:2101.04968_ , 2021.
  * Richards et al. (2020) Richards, D. et al.  Graph-dependent implicit regularisation for distributed stochastic subgradient descent.  _Journal of Machine Learning Research_ , 21(2020), 2020\.
  * Rockafellar (1976) Rockafellar, R. T.  Monotone operators and the proximal point algorithm.  _SIAM Journal on Control and Optimization_ , 14(5):877–898, 1976.
  * Sagun et al. (2017) Sagun, L., Evci, U., Guney, V. U., Dauphin, Y., and Bottou, L.  Empirical analysis of the hessian of over-parametrized neural networks.  _arXiv preprint arXiv:1706.04454_ , 2017.
  * Shalev-Shwartz et al. (2010) Shalev-Shwartz, S., Shamir, O., Srebro, N., and Sridharan, K.  Learnability, stability and uniform convergence.  _Journal of Machine Learning Research_ , 11:2635–2670, 2010\.
  * Tarres & Yao (2014) Tarres, P. and Yao, Y.  Online learning as stochastic approximation of regularization paths: optimality and almost-sure convergence.  _IEEE Transactions on Information Theory_ , 60(9):5716–5735, 2014.
  * Thekumparampil et al. (2019) Thekumparampil, K. K., Jain, P., Netrapalli, P., and Oh, S.  Efficient algorithms for smooth minimax optimization.  _Advances in Neural Information Processing Systems_ , 32:12680–12691, 2019.
  * Vershynin (2018) Vershynin, R.  _High-dimensional probability: An introduction with applications in data science_.  Cambridge university press, 2018.
  * Xu et al. (2020) Xu, Y., Zhu, S., Yang, S., Zhang, C., Jin, R., and Yang, T.  Learning with non-convex truncated losses by sgd.  In _Uncertainty in Artificial Intelligence_ , pp. 701–711, 2020\.
  * Yan et al. (2020) Yan, Y., Xu, Y., Lin, Q., Liu, W., and Yang, T.  Optimal epoch stochastic gradient descent ascent methods for min-max optimization.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Yang et al. (2020) Yang, J., Kiyavash, N., and He, N.  Global convergence and variance reduction for a class of nonconvex-nonconcave minimax problems.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Ying et al. (2016) Ying, Y., Wen, L., and Lyu, S.  Stochastic online AUC maximization.  In _Advances in Neural Information Processing Systems_ , pp. 451–459, 2016.
  * Yuan et al. (2019) Yuan, Z., Yan, Y., Jin, R., and Yang, T.  Stagewise training accelerates convergence of testing error over sgd.  In _Advances in Neural Information Processing Systems_ , pp. 2604–2614, 2019.
  * Zhang et al. (2020) Zhang, J., Hong, M., Wang, M., and Zhang, S.  Generalization bounds for stochastic saddle point problems.  _arXiv preprint arXiv:2006.02067_ , 2020.
  * Zhao et al. (2011) Zhao, P., Hoi, S. C., Jin, R., and Yang, T.  Online AUC maximization.  In _International Conference on Machine Learning_ , pp. 233–240, 2011.

Appendix for “Stability and Generalization of Stochastic Gradient Methods for
Minimax Problems”

##  Appendix A Notations

We collect in Table A.1 the notations of performance measures used in this
paper.

| Notation | Meaning | Definition
---|---|---|---
Weak Measure | $\triangle^{w}({\mathbf{w}},{\mathbf{v}})$ | weak PD population risk | $\displaystyle\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}\mathbb{E}\big{[}F({\mathbf{w}},\mathbf{v}^{\prime})\big{]}-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}\mathbb{E}\big{[}F(\mathbf{w}^{\prime},{\mathbf{v}})\big{]}$
$\displaystyle\triangle^{w}_{S}({\mathbf{w}},{\mathbf{v}})$ | weak PD empirical risk | $\displaystyle\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}\mathbb{E}\big{[}F_{S}({\mathbf{w}},\mathbf{v}^{\prime})\big{]}-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}\mathbb{E}\big{[}F_{S}(\mathbf{w}^{\prime},{\mathbf{v}})\big{]}$
$\displaystyle\triangle^{w}({\mathbf{w}},{\mathbf{v}})-\triangle^{w}_{S}({\mathbf{w}},{\mathbf{v}})$ | weak PD generalization error | $\displaystyle\big{(}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}\mathbb{E}\big{[}F({\mathbf{w}},\mathbf{v}^{\prime})\big{]}-\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}\mathbb{E}\big{[}F_{S}(\mathbf{w},\mathbf{v}^{\prime})\big{]}\big{)}$
$\displaystyle+\big{(}\inf_{\mathbf{w}^{\prime}\in\mathcal{V}}\mathbb{E}\big{[}F_{S}(\mathbf{w}^{\prime},\mathbf{v})\big{]}-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}\mathbb{E}\big{[}F(\mathbf{w}^{\prime},\mathbf{v})\big{]}\big{)}$
Strong Measure | $\triangle^{s}({\mathbf{w}},{\mathbf{v}})$ | strong PD population Risk | $\displaystyle\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F({\mathbf{w}},\mathbf{v}^{\prime})-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}F(\mathbf{w}^{\prime},{\mathbf{v}})$
$\displaystyle\triangle^{s}_{S}({\mathbf{w}},{\mathbf{v}})$ | strong PD empirical Risk | $\displaystyle\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}({\mathbf{w}},\mathbf{v}^{\prime})-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}F_{S}(\mathbf{w}^{\prime},{\mathbf{v}})$
$\displaystyle\triangle^{s}({\mathbf{w}},{\mathbf{v}})-\triangle^{s}_{S}({\mathbf{w}},{\mathbf{v}})$ | strong PD generalization error | $\displaystyle\big{(}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F({\mathbf{w}},\mathbf{v}^{\prime})-\sup_{\mathbf{v}^{\prime}\in\mathcal{W}}F_{S}(\mathbf{w},\mathbf{v}^{\prime})\big{)}$
$\displaystyle+\big{(}\inf_{\mathbf{w}^{\prime}\in\mathcal{V}}F_{S}(\mathbf{w}^{\prime},\mathbf{v})-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}F(\mathbf{w}^{\prime},\mathbf{v})\big{)}$
Primal Measure | $\displaystyle R(\mathbf{w})-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}R(\mathbf{w}^{\prime})$ | excess primal population risk | $\displaystyle\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F(\mathbf{w},\mathbf{v}^{\prime})-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F(\mathbf{w}^{\prime},\mathbf{v}^{\prime})$
$\displaystyle R_{S}(\mathbf{w})-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}R_{S}(\mathbf{w}^{\prime})$ | excess primal empirical risk | $\displaystyle\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}(\mathbf{w},\mathbf{v}^{\prime})-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}(\mathbf{w}^{\prime},\mathbf{v}^{\prime})$
$\displaystyle R(\mathbf{w})-R_{S}(\mathbf{w})$ | primal generalization error | $\displaystyle\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F(\mathbf{w},\mathbf{v}^{\prime})-\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}(\mathbf{w},\mathbf{v}^{\prime})$
| $\displaystyle F(\mathbf{w},\mathbf{v})-F_{S}(\mathbf{w},\mathbf{v})$ | plain generalization error |
Table A.1: Notations on Measures of Performance.

We collect in Table A.2 the stability measures for a (randomized) algorithm
$A$.

Stability Measure | Definition
---|---
Weak Stability | $\displaystyle\sup_{z}\Big{(}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}\mathbb{E}_{A}\big{[}f(A_{\mathbf{w}}(S),\mathbf{v}^{\prime};z)-f(A_{\mathbf{w}}(S^{\prime}),\mathbf{v}^{\prime};z)\big{]}+\sup_{\mathbf{w}^{\prime}\in\mathcal{W}}\mathbb{E}_{A}\big{[}f(\mathbf{w}^{\prime},A_{\mathbf{v}}(S);z)-f(\mathbf{w}^{\prime},A_{\mathbf{v}}(S^{\prime});z)\big{]}\Big{)}$
Argument Stability | $\displaystyle\mathbb{E}_{A}\left[\left\|\begin{pmatrix}A_{\mathbf{w}}(S)-A_{\mathbf{w}}(S^{\prime})\\\ A_{\mathbf{v}}(S)-A_{\mathbf{v}}(S^{\prime})\end{pmatrix}\right\|_{2}\right]\text{ or }\left\|\begin{pmatrix}A_{\mathbf{w}}(S)-A_{\mathbf{w}}(S^{\prime})\\\ A_{\mathbf{v}}(S)-A_{\mathbf{v}}(S^{\prime})\end{pmatrix}\right\|_{2}$
Uniform Stability | $\displaystyle\sup_{z}\big{[}f(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S);z)-f(A_{\mathbf{w}}(S^{\prime}),A_{\mathbf{v}}(S^{\prime});z)\big{]}$

Table A.2: Stability Measures. Here $S$ and $S^{\prime}$ are neighboring
datasets.

##  Appendix B Proof of Theorem 1

In this section, we prove Theorem 1 on the connection between stability
measure and generalization.

Let $S=\\{z_{1},\ldots,z_{n}\\}$ and
$S^{\prime}=\\{z_{1}^{\prime},\ldots,z_{n}^{\prime}\\}$ be two datasets drawn
from the same distribution. For any $i\in[n]$, define
$S^{(i)}=\\{z_{1},\ldots,z_{i-1},z_{i}^{\prime},z_{i+1},\ldots,z_{n}\\}$. For
any function $g,\tilde{g}$, we have the basic inequalities

$\begin{split}&\sup_{\mathbf{w}}g(\mathbf{w})-\sup_{\mathbf{w}}\tilde{g}(\mathbf{w})\leq\sup_{\mathbf{w}}\big{(}g(\mathbf{w})-\tilde{g}(\mathbf{w})\big{)}\\\
&\inf_{\mathbf{w}}g(\mathbf{w})-\inf_{\mathbf{w}}\tilde{g}(\mathbf{w})\leq\sup_{\mathbf{w}}\big{(}g(\mathbf{w})-\tilde{g}(\mathbf{w})\big{)}.\end{split}$
(B.1)

###  B.1 Proof of Part (a)

We first prove Part (a). It follows from (B.1) that

$\triangle^{w}(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))-\triangle^{w}_{S}(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))\leq\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}\mathbb{E}[F(A_{\mathbf{w}}(S),\mathbf{v}^{\prime})-F_{S}(A_{\mathbf{w}}(S),\mathbf{v}^{\prime})]\\\
+\sup_{\mathbf{w}^{\prime}\in\mathcal{W}}\mathbb{E}[F_{S}(\mathbf{w}^{\prime},A_{\mathbf{v}}(S))-F(\mathbf{w}^{\prime},A_{\mathbf{v}}(S))].$

According to the symmetry between $z_{i}$ and $z_{i}^{\prime}$ we know

$\displaystyle\mathbb{E}[F(A_{\mathbf{w}}(S),\mathbf{v}^{\prime})-F_{S}(A_{\mathbf{w}}(S),\mathbf{v}^{\prime})]$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[F(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}^{\prime})]-\mathbb{E}[F_{S}(A_{\mathbf{w}}(S),\mathbf{v}^{\prime})]$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\big{[}f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}^{\prime};z_{i})-f(A_{\mathbf{w}}(S),\mathbf{v}^{\prime};z_{i})\big{]},$

where the second identity holds since $z_{i}$ is not used to train
$A_{\mathbf{w}}(S^{(i)})$. In a similar way, we can prove

$\mathbb{E}[F_{S}(\mathbf{w}^{\prime},A_{\mathbf{v}}(S))-F(\mathbf{w}^{\prime},A_{\mathbf{v}}(S))]=\frac{1}{n}\sum_{i=1}^{n}\big{[}f(\mathbf{w}^{\prime},A_{\mathbf{v}}(S^{(i)});z_{i})-f(\mathbf{w}^{\prime},A_{\mathbf{v}}(S);z_{i})\big{]}.$

As a combination of the above three inequalities we get

$\triangle^{w}(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))-\triangle^{w}_{S}(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))\leq\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\big{[}f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}^{\prime};z_{i})-f(A_{\mathbf{w}}(S),\mathbf{v}^{\prime};z_{i})\big{]}\Big{]}+\\\
\sup_{\mathbf{w}^{\prime}\in\mathcal{W}}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\big{[}f(\mathbf{w}^{\prime},A_{\mathbf{v}}(S^{(i)});z_{i})-f(\mathbf{w}^{\prime},A_{\mathbf{v}}(S);z_{i})\big{]}\Big{]}.$

The stated bound in Part (a) then follows directly from the definition of
stability.

###  B.2 Proof of Part (b)

The following lemma quantifies the sensitivity of the optimal $\mathbf{v}$
w.r.t. the perturbation of $\mathbf{w}$.

######  Lemma B.1 (Lin et al. 2020).

Let $\phi:\mathcal{W}\times\mathcal{V}\mapsto\mathbb{R}$. Assume that for any
$\mathbf{w}$, the function $\mathbf{v}\mapsto\phi(\mathbf{w},\mathbf{v})$ is
$\rho$-strongly-concave. Suppose for any
$(\mathbf{w},\mathbf{v}),(\mathbf{w}^{\prime},\mathbf{v}^{\prime})$ we have

$\big{\|}\nabla_{\mathbf{v}}\phi(\mathbf{w},\mathbf{v})-\nabla_{\mathbf{v}}\phi(\mathbf{w}^{\prime},\mathbf{v})\big{\|}_{2}\leq
L\|\mathbf{w}-\mathbf{w}^{\prime}\|_{2}.$

For any $\mathbf{w}$, denote
$\mathbf{v}^{*}(\mathbf{w})=\arg\max_{\mathbf{v}\in\mathcal{V}}\phi(\mathbf{w},\mathbf{v})$.
Then for any $\mathbf{w},\mathbf{w}^{\prime}\in\mathcal{W}$, we have

$\big{\|}\mathbf{v}^{*}(\mathbf{w})-\mathbf{v}^{*}(\mathbf{w}^{\prime})\|_{2}\leq\frac{L}{\rho}\|\mathbf{w}-\mathbf{w}^{\prime}\|_{2}.$

We now prove Part (b). For any $S$, let
$\mathbf{v}_{S}^{*}=\arg\max_{\mathbf{v}\in\mathcal{V}}F(A_{\mathbf{w}}(S),\mathbf{v})$.
According to the symmetry between $z_{i}$ and $z_{i}^{\prime}$ we know

$\displaystyle\mathbb{E}\big{[}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F(A_{\mathbf{w}}(S),\mathbf{v}^{\prime})\big{]}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\big{[}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}^{\prime})\big{]}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\big{[}F(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}^{*}_{S^{(i)}})\big{]}=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\big{[}f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}^{*}_{S^{(i)}};z_{i})\big{]},$

where the last identity holds since $z_{i}$ is independent of
$A_{\mathbf{w}}(S^{(i)})$ and $\mathbf{v}^{*}_{S^{(i)}}$.

According to Assumption 1, we know

$\displaystyle
f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}^{*}_{S^{(i)}};z_{i})-f(A_{\mathbf{w}}(S),\mathbf{v}_{S}^{*};z_{i})$
$\displaystyle=f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}^{*}_{S^{(i)}};z_{i})-f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S}^{*};z_{i})+f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}^{*}_{S};z_{i})-f(A_{\mathbf{w}}(S),\mathbf{v}_{S}^{*};z_{i})$
$\displaystyle\leq
G\big{\|}A_{\mathbf{w}}(S^{(i)})-A_{\mathbf{w}}(S)\big{\|}_{2}+G\big{\|}\mathbf{v}^{*}_{S^{(i)}}-\mathbf{v}_{S}^{*}\big{\|}_{2}\leq\big{(}1+L/\rho\big{)}G\big{\|}A_{\mathbf{w}}(S^{(i)})-A_{\mathbf{w}}(S)\big{\|}_{2},$
(B.2)

where in the last inequality we have used Lemma B.1 due to the strong
concavity of $\mathbf{v}\mapsto F(\mathbf{w},\mathbf{v})$ for any
$\mathbf{w}$. As a combination of the above two inequalities, we get

$\displaystyle\mathbb{E}\big{[}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F(A_{\mathbf{w}}(S),\mathbf{v}^{\prime})\big{]}$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\big{[}f(A_{\mathbf{w}}(S),\mathbf{v}_{S}^{*};z_{i})\big{]}+\frac{\big{(}1+L/\rho\big{)}G}{n}\sum_{i=1}^{n}\mathbb{E}\big{[}\big{\|}A_{\mathbf{w}}(S^{(i)})-A_{\mathbf{w}}(S)\big{\|}_{2}\big{]}$
$\displaystyle=\mathbb{E}\big{[}F_{S}(A_{\mathbf{w}}(S),\mathbf{v}_{S}^{*})\big{]}+\frac{\big{(}1+L/\rho\big{)}G}{n}\sum_{i=1}^{n}\mathbb{E}\big{[}\big{\|}A_{\mathbf{w}}(S^{(i)})-A_{\mathbf{w}}(S)\big{\|}_{2}\big{]}$
$\displaystyle\leq\mathbb{E}\big{[}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}(A_{\mathbf{w}}(S),\mathbf{v}^{\prime})\big{]}+\frac{\big{(}1+L/\rho\big{)}G}{n}\sum_{i=1}^{n}\mathbb{E}\big{[}\big{\|}A_{\mathbf{w}}(S^{(i)})-A_{\mathbf{w}}(S)\big{\|}_{2}\big{]}.$
(B.3)

The stated bound in Part (b) then follows.

###  B.3 Proof of Part (c)

In a similar way, one can show that

$\mathbb{E}\big{[}\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}F_{S}(\mathbf{w}^{\prime},A_{\mathbf{v}}(S))\big{]}-\mathbb{E}\big{[}\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}F(\mathbf{w}^{\prime},A_{\mathbf{v}}(S))\big{]}\leq\frac{\big{(}1+L/\rho\big{)}G}{n}\sum_{i=1}^{n}\mathbb{E}\big{[}\|A_{\mathbf{v}}(S^{(i)})-A_{\mathbf{v}}(S)\|_{2}\big{]}.$

The above inequality together with (B.3) then implies

$\displaystyle\mathbb{E}\big{[}\triangle^{s}(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))\big{]}-\mathbb{E}\big{[}\triangle_{S}^{s}(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S))\big{]}$
$\displaystyle=\mathbb{E}\big{[}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F(A_{\mathbf{w}}(S),\mathbf{v}^{\prime})\big{]}-\mathbb{E}\big{[}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}(A_{\mathbf{w}}(S),\mathbf{v}^{\prime})\big{]}+\mathbb{E}\big{[}\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}F_{S}(\mathbf{w}^{\prime},A_{\mathbf{v}}(S))\big{]}-\mathbb{E}\big{[}\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}F(\mathbf{w}^{\prime},A_{\mathbf{v}}(S))\big{]}$
$\displaystyle\leq{\big{(}1+L/\rho\big{)}G}\mathbb{E}\big{[}\|A_{\mathbf{w}}(S^{(i)})-A_{\mathbf{w}}(S)\|_{2}\big{]}+{\big{(}1+L/\rho\big{)}G}\mathbb{E}\big{[}\|A_{\mathbf{v}}(S^{(i)})-A_{\mathbf{v}}(S)\|_{2}\big{]}$
$\displaystyle\leq{\big{(}1+L/\rho\big{)}G\sqrt{2}}\mathbb{E}\Big{[}\Big{\|}\begin{pmatrix}A_{\mathbf{w}}(S^{(i)})-A_{\mathbf{w}}(S)\\\
A_{\mathbf{v}}(S^{(i)})-A_{\mathbf{v}}(S)\end{pmatrix}\Big{\|}_{2}\Big{]},$

where we have used the elementary inequality $a+b\leq\sqrt{2(a^{2}+b^{2})}$.
This proves the stated bound in Part (c).

###  B.4 Proof of Part (d)

To prove Part (d) on high-probability bounds, we need to introduce some
lemmas.

The following lemma establishes a concentration inequality for a summation of
weakly-dependent random variables. We denote by $S\backslash\\{z_{i}\\}$ the
set $\\{z_{1},\ldots,z_{i-1},z_{i+1},\ldots,z_{n}\\}$. The $L_{p}$-norm of a
random variable $Z$ is denoted by
$\|Z\|_{p}:=\big{(}\mathbb{E}[|Z|^{p}]\big{)}^{\frac{1}{p}},p\geq 1$.

######  Lemma B.2 (Bousquet et al. 2020).

Let $S=\\{z_{1},\ldots,z_{n}\\}$ be a set of independent random variables each
taking values in $\mathcal{Z}$ and $M>0$. Let $g_{1},\ldots,g_{n}$ be some
functions $g_{i}:\mathcal{Z}^{n}\mapsto\mathbb{R}$ such that the following
holds for any $i\in[n]$

  * •

$\big{|}\mathbb{E}_{S\backslash\\{z_{i}\\}}[g_{i}(S)]\big{|}\leq M$ almost
surely (a.s.),

  * •

$\mathbb{E}_{z_{i}}\big{[}g_{i}(S)\big{]}=0$ a.s.,

  * •

for any $j\in[n]$ with $j\neq i$, and $z_{j}^{\prime\prime}\in\mathcal{Z}$

$\big{|}g_{i}(S)-g_{i}(z_{1},\ldots,z_{j-1},z_{j}^{\prime\prime},z_{j+1},\ldots,z_{n})\big{|}\leq\beta.$
(B.4)

Then, for any $p\geq 2$

$\Big{\|}\sum_{i=1}^{n}g_{i}(S)\Big{\|}_{p}\leq
12\sqrt{6}pn\beta\lceil\log_{2}n\rceil+3\sqrt{2}M\sqrt{pn}.$

The following lemma shows how to relate moment bounds of random variables to
tail behavior.

######  Lemma B.3 (Bousquet et al. 2020, Vershynin 2018).

Let $a,b\in\mathbb{R}_{+}$ and $\delta\in(0,1/e)$. Let $Z$ be a random
variable with $\|Z\|_{p}\leq\sqrt{p}a+pb$ for any $p\geq 2$. Then with
probability at least $1-\delta$

$|Z|\leq e\Big{(}a\sqrt{\log(e/\delta)}+b\log(e/\delta)\Big{)}.$

With the above lemmas we are now ready to prove Part (d). For any $S$, denote

$\mathbf{v}_{S}^{*}=\arg\max_{\mathbf{v}\in\mathcal{V}}F(A_{\mathbf{w}}(S),\mathbf{v}).$
(B.5)

We have the following error decomposition

$nF(A_{\mathbf{w}}(S),\mathbf{v}_{S}^{*})-n\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}(A_{\mathbf{w}}(S),\mathbf{v})=\sum_{i=1}^{n}\mathbb{E}_{Z}\big{[}f(A_{\mathbf{w}}(S),\mathbf{v}_{S}^{*};Z)-\mathbb{E}_{z_{i}^{\prime}}[f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};Z)]\big{]}+\\\
\sum_{i=1}^{n}\mathbb{E}_{z_{i}^{\prime}}\Big{[}\mathbb{E}_{Z}[f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};Z)]-f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};z_{i})\Big{]}+\sum_{i=1}^{n}\mathbb{E}_{z_{i}^{\prime}}\Big{[}f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};z_{i})\Big{]}-n\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}(A_{\mathbf{w}}(S),\mathbf{v}).$

By the definition of $\mathbf{v}_{S^{(i)}}^{*}$ we know
$\mathbb{E}_{Z}[f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};Z)]\geq\mathbb{E}_{Z}[f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S}^{*};Z)]$.
It then follows that

$nF(A_{\mathbf{w}}(S),\mathbf{v}_{S}^{*})-n\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}(A_{\mathbf{w}}(S),\mathbf{v}^{\prime})\leq\sum_{i=1}^{n}\mathbb{E}_{Z}\big{[}f(A_{\mathbf{w}}(S),\mathbf{v}_{S}^{*};Z)-\mathbb{E}_{z_{i}^{\prime}}[f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S}^{*};Z)]\big{]}+\\\
\sum_{i=1}^{n}\mathbb{E}_{z_{i}^{\prime}}\Big{[}\mathbb{E}_{Z}[f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};Z)]-f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};z_{i})\Big{]}+\sum_{i=1}^{n}\mathbb{E}_{z_{i}^{\prime}}\Big{[}f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};z_{i})\Big{]}-n\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}(A_{\mathbf{w}}(S),\mathbf{v}^{\prime}).$

According to (B.2), we know

$\displaystyle\sum_{i=1}^{n}\mathbb{E}_{z_{i}^{\prime}}\Big{[}f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};z_{i})\Big{]}$
$\displaystyle\leq\big{(}1+L/\rho\big{)}G\sum_{i=1}^{n}\mathbb{E}_{z_{i}^{\prime}}\big{[}\big{\|}A_{\mathbf{w}}(S^{(i)})-A_{\mathbf{w}}(S)\big{\|}_{2}\big{]}+\sum_{i=1}^{n}f(A_{\mathbf{w}}(S),\mathbf{v}_{S}^{*};z_{i})$
$\displaystyle=\big{(}1+L/\rho\big{)}G\sum_{i=1}^{n}\mathbb{E}_{z_{i}^{\prime}}\big{[}\big{\|}A_{\mathbf{w}}(S^{(i)})-A_{\mathbf{w}}(S)\big{\|}_{2}\big{]}+nF_{S}(A_{\mathbf{w}}(S),\mathbf{v}_{S}^{*})$
$\displaystyle\leq\big{(}1+L/\rho\big{)}G\sum_{i=1}^{n}\mathbb{E}_{z_{i}^{\prime}}\big{[}\big{\|}A_{\mathbf{w}}(S^{(i)})-A_{\mathbf{w}}(S)\big{\|}_{2}\big{]}+n\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}(A_{\mathbf{w}}(S),\mathbf{v}^{\prime}).$

As a combination of the above two inequalities, we derive

$nF(A_{\mathbf{w}}(S),\mathbf{v}_{S}^{*})-n\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}(A_{\mathbf{w}}(S),\mathbf{v}^{\prime})\leq\big{(}2+L/\rho\big{)}nG\epsilon+\sum_{i=1}^{n}g_{i}(S),$
(B.6)

where we introduce

$g_{i}(S)=\mathbb{E}_{z_{i}^{\prime}}\Big{[}\mathbb{E}_{Z}[f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};Z)]-f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};z_{i})\Big{]}$

and use the inequality

$f(A_{\mathbf{w}}(S),\mathbf{v}_{S}^{*};Z)-f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S}^{*};Z)\leq
G\|A_{\mathbf{w}}(S)-A_{\mathbf{w}}(S^{(i)})\|_{2}\leq G\epsilon.$

Due to the symmetry between $z_{i}$ and $Z$, we know
$\mathbb{E}_{z_{i}}[g_{i}(S)]=0$. The inequality
$|\mathbb{E}_{S\backslash\\{z_{i}\\}}[g_{i}(S)]|\leq 2R$ is also clear.

For any $j\neq i$ and any $z_{j}^{\prime\prime}\in\mathcal{Z}$, we know

$\displaystyle\Big{|}\mathbb{E}_{z_{i}^{\prime}}\Big{[}\mathbb{E}_{Z}[f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};Z)]-f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};z_{i})\Big{]}-\mathbb{E}_{z_{i}^{\prime}}\Big{[}\mathbb{E}_{Z}[f(A_{\mathbf{w}}(S_{j}^{(i)}),\mathbf{v}_{S_{j}^{(i)}}^{*};Z)]-f(A_{\mathbf{w}}(S_{j}^{(i)}),\mathbf{v}_{S_{j}^{(i)}}^{*};z_{i})\Big{]}\Big{|}$
$\displaystyle\leq\Big{|}\mathbb{E}_{z_{i}^{\prime}}\Big{[}\mathbb{E}_{Z}[f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};Z)]-\mathbb{E}_{Z}[f(A_{\mathbf{w}}(S_{j}^{(i)}),\mathbf{v}_{S_{j}^{(i)}}^{*};Z)]\Big{]}\Big{|}+\Big{|}\mathbb{E}_{z_{i}^{\prime}}\Big{[}f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};z_{i})-f(A_{\mathbf{w}}(S_{j}^{(i)}),\mathbf{v}_{S_{j}^{(i)}}^{*};z_{i})\Big{]}\Big{|},$

where $S_{j}^{(i)}$ is the set derived by replacing the $j$-th element of
$S^{(i)}$ with $z_{j}^{\prime\prime}$. For any $z$, there holds

$\displaystyle\big{|}f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};z)-f(A_{\mathbf{w}}(S_{j}^{(i)}),\mathbf{v}_{S_{j}^{(i)}}^{*};z)\big{|}$
$\displaystyle\leq\big{|}f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S^{(i)}}^{*};z)-f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S_{j}^{(i)}}^{*};z)\big{|}+\big{|}f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}_{S_{j}^{(i)}}^{*};z)-f(A_{\mathbf{w}}(S_{j}^{(i)}),\mathbf{v}_{S_{j}^{(i)}}^{*};z)\big{|}$
$\displaystyle\leq
G\|\mathbf{v}_{S^{(i)}}^{*}-\mathbf{v}_{S_{j}^{(i)}}^{*}\|_{2}+G\|A_{\mathbf{w}}(S^{(i)})-A_{\mathbf{w}}(S_{j}^{(i)})\|_{2}\leq\big{(}L/\rho+1\big{)}G\|A_{\mathbf{w}}(S^{(i)})-A_{\mathbf{w}}(S_{j}^{(i)})\|_{2},$

where in the last inequality we have used the definition of
$\mathbf{v}_{S^{(i)}}^{*}$ and Lemma B.1 with $\phi=F$. Therefore $g_{i}(S)$
satisfies the condition (B.4) with $\beta=\big{(}L/\rho+1\big{)}G\epsilon$.
Therefore, all the conditions of Lemma B.2 hold and we can apply Lemma B.2 to
derive the following inequality for any $p\geq 2$

$\Big{\|}\sum_{i=1}^{n}g_{i}(S)\Big{\|}_{p}\leq
12\sqrt{6}pn\big{(}L/\rho+1\big{)}G\epsilon\lceil\log_{2}n\rceil+6\sqrt{2}R\sqrt{pn}.$

This together with Lemma B.3 implies the following inequality with probability
$1-\delta$

$\Big{|}\sum_{i=1}^{n}g_{i}(S)\Big{|}\leq
e\Big{(}6R\sqrt{2n\log(e/\delta)}+12\sqrt{6}n\big{(}L/\rho+1\big{)}G\epsilon\log(e/\delta)\lceil\log_{2}n\rceil\Big{)}.$

We can plug the above inequality back into (B.6) and derive the following
inequality with probability at least $1-\delta$

$F(A_{\mathbf{w}}(S),\mathbf{v}_{S}^{*})-\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}F_{S}(A_{\mathbf{w}}(S),\mathbf{v}^{\prime})\leq\big{(}2+L/\rho\big{)}G\epsilon+e\Big{(}6R\sqrt{2n^{-1}\log(e/\delta)}+12\sqrt{6}\big{(}L/\rho+1\big{)}G\epsilon\log(e/\delta)\lceil\log_{2}n\rceil\Big{)}.$

This proves the stated bound in Part (d).

###  B.5 Proof of Part (e)

Part (e) is standard in the literature (Bousquet et al., 2020).

##  Appendix C Proof of Theorem 2

In this section, we present the proof of Theorem 2 on the argument stability
of SGDA.

###  C.1 Approximate Nonexpansiveness of Gradient Map

To prove stability bounds, we need to study the expansiveness of the gradient
map

$G_{f,\eta}:\begin{pmatrix}\mathbf{w}\\\
\mathbf{v}\end{pmatrix}\mapsto\begin{pmatrix}\mathbf{w}-\eta\nabla_{\mathbf{w}}f(\mathbf{w},\mathbf{v})\\\
\mathbf{v}+\eta\nabla_{\mathbf{v}}f(\mathbf{w},\mathbf{v})\end{pmatrix}$

associated with a (strongly) convex-concave $f$. The following lemma shows
that $G_{f,\eta}$ is approximately nonexpansive in both the Lipschitz
continuous case and the smooth case. It also shows that $G_{f,\eta}$ is
nonexpansive if $f$ is SC-SC and the step size is small. Part (b) can be found
in Farnia & Ozdaglar (2020).

######  Lemma C.1.

Let $f$ be $\rho$-SC-SC with $\rho\geq 0$.

  1. (a)

If Assumption 1 holds, then

$\bigg{\|}\begin{pmatrix}\mathbf{w}-\eta\nabla_{\mathbf{w}}f(\mathbf{w},\mathbf{v})\\\
\mathbf{v}+\eta\nabla_{\mathbf{v}}f(\mathbf{w},\mathbf{v})\end{pmatrix}-\begin{pmatrix}\mathbf{w}^{\prime}-\eta\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})\\\
\mathbf{v}^{\prime}+\eta\nabla_{\mathbf{v}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})\end{pmatrix}\bigg{\|}_{2}^{2}\leq(1-2\rho\eta)\bigg{\|}\begin{pmatrix}\mathbf{w}-\mathbf{w}^{\prime}\\\
\mathbf{v}-\mathbf{v}^{\prime}\end{pmatrix}\bigg{\|}_{2}^{2}+8G^{2}\eta^{2}.$

  2. (b)

If Assumption 2 holds, then

$\bigg{\|}\begin{pmatrix}\mathbf{w}-\eta\nabla_{\mathbf{w}}f(\mathbf{w},\mathbf{v})\\\
\mathbf{v}+\eta\nabla_{\mathbf{v}}f(\mathbf{w},\mathbf{v})\end{pmatrix}-\begin{pmatrix}\mathbf{w}^{\prime}-\eta\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})\\\
\mathbf{v}^{\prime}+\eta\nabla_{\mathbf{v}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})\end{pmatrix}\bigg{\|}_{2}^{2}\leq(1-2\rho\eta+L^{2}\eta^{2})\bigg{\|}\begin{pmatrix}\mathbf{w}-\mathbf{w}^{\prime}\\\
\mathbf{v}-\mathbf{v}^{\prime}\end{pmatrix}\bigg{\|}_{2}^{2}.$

To prove Lemma C.1 we require the following standard lemma (Rockafellar,
1976).

######  Lemma C.2.

Let $f$ be a $\rho$-SC-SC function, $\rho\geq 0$. Then

$\bigg{\langle}\begin{pmatrix}\mathbf{w}-\mathbf{w}^{\prime}\\\
\mathbf{v}-\mathbf{v}^{\prime}\end{pmatrix},\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w},\mathbf{v})-\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})\\\
\nabla_{\mathbf{v}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})-\nabla_{\mathbf{v}}f(\mathbf{w},\mathbf{v})\end{pmatrix}\bigg{\rangle}\geq\rho\bigg{\|}\begin{pmatrix}\mathbf{w}-\mathbf{w}^{\prime}\\\
\mathbf{v}-\mathbf{v}^{\prime}\end{pmatrix}\bigg{\|}_{2}^{2}.$ (C.1)

###### Proof of Lemma C.1.

It is clear that

$A:=\bigg{\|}\begin{pmatrix}\mathbf{w}-\eta\nabla_{\mathbf{w}}f(\mathbf{w},\mathbf{v})\\\
\mathbf{v}+\eta\nabla_{\mathbf{v}}f(\mathbf{w},\mathbf{v})\end{pmatrix}-\begin{pmatrix}\mathbf{w}^{\prime}-\eta\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})\\\
\mathbf{v}^{\prime}+\eta\nabla_{\mathbf{v}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})\end{pmatrix}\bigg{\|}_{2}^{2}=\bigg{\|}\begin{pmatrix}\mathbf{w}-\mathbf{w}^{\prime}\\\
\mathbf{v}-\mathbf{v}^{\prime}\end{pmatrix}\bigg{\|}_{2}^{2}\\\
+\eta^{2}\bigg{\|}\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})-\nabla_{\mathbf{w}}f(\mathbf{w},\mathbf{v})\\\
\nabla_{\mathbf{v}}f(\mathbf{w},\mathbf{v})-\nabla_{\mathbf{v}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})\end{pmatrix}\bigg{\|}_{2}^{2}-2\eta\bigg{\langle}\begin{pmatrix}\mathbf{w}-\mathbf{w}^{\prime}\\\
\mathbf{v}-\mathbf{v}^{\prime}\end{pmatrix},\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w},\mathbf{v})-\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})\\\
\nabla_{\mathbf{v}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})-\nabla_{\mathbf{v}}f(\mathbf{w},\mathbf{v})\end{pmatrix}\bigg{\rangle}.$

Plugging (C.1) to the above inequality, we derive

$A\leq(1-2\rho\eta)\bigg{\|}\begin{pmatrix}\mathbf{w}-\mathbf{w}^{\prime}\\\
\mathbf{v}-\mathbf{v}^{\prime}\end{pmatrix}\bigg{\|}_{2}^{2}+\eta^{2}\bigg{\|}\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})-\nabla_{\mathbf{w}}f(\mathbf{w},\mathbf{v})\\\
\nabla_{\mathbf{v}}f(\mathbf{w},\mathbf{v})-\nabla_{\mathbf{v}}f(\mathbf{w}^{\prime},\mathbf{v}^{\prime})\end{pmatrix}\bigg{\|}_{2}^{2}.$

We can combine the above inequality with the Lipschitz continuity to derive
Part (a). We refer the interested readers to Farnia & Ozdaglar (2020) for the
proof of Part (b). ∎

We now prove Theorem 2. Let $S=\\{z_{1},\ldots,z_{n}\\}$ and
$S^{\prime}=\\{z_{1},\ldots,z_{n-1},z_{n}^{\prime}\\}$. Let
$\\{\mathbf{w}_{t},\mathbf{v}_{t}\\}$ and
$\\{\mathbf{w}_{t}^{\prime},\mathbf{v}_{t}^{\prime}\\}$ be the sequence
produced by (4.1) w.r.t. $S$ and $S^{\prime}$, respectively.

###  C.2 Proof of Part (a)

We first prove Part (a). Note that the projection step is nonexpansive. We
consider two cases at the $t$-th iteration. If $i_{t}\neq n$, then it follows
from Part (a) of Lemma C.1 that

$\displaystyle\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}$
$\displaystyle\leq\left\|\begin{pmatrix}\mathbf{w}_{t}-\eta_{t}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\mathbf{w}_{t}^{\prime}+\eta_{t}\nabla_{\mathbf{w}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z_{i_{t}})\\\
\mathbf{v}_{t}+\eta_{t}\nabla_{\mathbf{v}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\mathbf{v}_{t}^{\prime}-\eta_{t}\nabla_{\mathbf{v}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z_{i_{t}})\end{pmatrix}\right\|_{2}^{2}$
$\displaystyle\leq\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+8G^{2}\eta_{t}^{2}.$
(C.2)

If $i_{t}=n$, then it follows from the elementary inequality
$(a+b)^{2}\leq(1+p)a^{2}+(1+1/p)b^{2}$ ($p>0$) that

$\displaystyle\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}$
$\displaystyle\leq\left\|\begin{pmatrix}\mathbf{w}_{t}-\eta_{t}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{n})-\mathbf{w}_{t}^{\prime}+\eta_{t}\nabla_{\mathbf{w}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z^{\prime}_{n})\\\
\mathbf{v}_{t}+\eta_{t}\nabla_{\mathbf{v}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{n})-\mathbf{v}_{t}^{\prime}-\eta_{t}\nabla_{\mathbf{v}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z^{\prime}_{n})\end{pmatrix}\right\|_{2}^{2}$
$\displaystyle\leq(1+p)\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+(1+1/p)\eta_{t}^{2}\left\|\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{n})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}_{t}^{\prime};z^{\prime}_{n})\\\
\nabla_{\mathbf{v}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{n})-\nabla_{\mathbf{v}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}_{t}^{\prime};z^{\prime}_{n})\end{pmatrix}\right\|_{2}^{2}.$
(C.3)

Note that the event $i_{t}\neq n$ happens with probability $1-1/n$ and the
event $i_{t}=n$ happens with probability $1/n$. Therefore, we know

$\displaystyle\mathbb{E}_{i_{t}}\left[\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\right]$
$\displaystyle\leq\frac{n-1}{n}\left(\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+8G^{2}\eta_{t}^{2}\right)+\frac{1+p}{n}\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+\frac{8(1+1/p)}{n}\eta_{t}^{2}G^{2}$
$\displaystyle=(1+p/n)\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+8\eta_{t}^{2}G^{2}(1+1/(np)).$

Applying this inequality recursively implies that

$\displaystyle\mathbb{E}_{A}\left[\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\right]$
$\displaystyle\leq
8\eta^{2}G^{2}\big{(}1+1/(np)\big{)}\sum_{k=1}^{t}\Big{(}1+\frac{p}{n}\Big{)}^{t-k}=8\eta^{2}G^{2}\Big{(}1+\frac{1}{np}\Big{)}\frac{n}{p}\Big{(}\Big{(}1+\frac{p}{n}\Big{)}^{t}-1\Big{)}$
$\displaystyle=8\eta^{2}G^{2}\Big{(}\frac{n}{p}+\frac{1}{p^{2}}\Big{)}\Big{(}\Big{(}1+\frac{p}{n}\Big{)}^{t}-1\Big{)}.$

By taking $p=n/t$ in the above inequality and using $(1+1/t)^{t}\leq e$, we
get

$\mathbb{E}_{A}\left[\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\right]\leq
16\eta^{2}G^{2}\Big{(}t+\frac{t^{2}}{n^{2}}\Big{)}.$

The stated bound then follows by Jensen’s inequality.

###  C.3 Proof of Part (b)

We now prove Part (b). Analogous to (C.2), we can use Part (b) of Lemma C.1 to
derive

$\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\leq(1+L^{2}\eta_{t}^{2})\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}$

in the case $i_{t}\neq n$. We can combine the above inequality and (C.3) to
derive

$\displaystyle\mathbb{E}_{i_{t}}\left[\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\right]$
$\displaystyle\leq\frac{(n-1)(1+L^{2}\eta_{t}^{2})}{n}\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+\frac{1+p}{n}\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+\frac{8(1+1/p)}{n}\eta_{t}^{2}G^{2}$
$\displaystyle\leq\Big{(}1+L^{2}\eta_{t}^{2}+p/n\Big{)}\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+\frac{8(1+1/p)}{n}\eta_{t}^{2}G^{2}.$

Applying this inequality recursively, we derive

$\mathbb{E}_{A}\left[\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\right]\leq\frac{8G^{2}(1+1/p)}{n}\sum_{k=1}^{t}\eta_{k}^{2}\prod_{j=k+1}^{t}\Big{(}1+L^{2}\eta_{j}^{2}+p/n\Big{)}.$

By the elementary inequality $1+a\leq\exp(a)$, we further derive

$\displaystyle\mathbb{E}_{A}\left[\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\right]$
$\displaystyle\leq\frac{8G^{2}(1+1/p)}{n}\sum_{k=1}^{t}\eta_{k}^{2}\prod_{j=k+1}^{t}\exp\Big{(}L^{2}\eta_{j}^{2}+p/n\Big{)}$
$\displaystyle=\frac{8G^{2}(1+1/p)}{n}\sum_{k=1}^{t}\eta_{k}^{2}\exp\Big{(}L^{2}\sum_{j=k+1}^{t}\eta_{j}^{2}+p(t-k)/n\Big{)}$
$\displaystyle\leq\frac{8G^{2}(1+1/p)}{n}\exp\Big{(}L^{2}\sum_{j=1}^{t}\eta_{j}^{2}+pt/n\Big{)}\sum_{k=1}^{t}\eta_{k}^{2}.$

By taking $p=n/t$ we get

$\mathbb{E}_{A}\left[\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\right]\leq\frac{8eG^{2}(1+t/n)}{n}\exp\Big{(}L^{2}\sum_{j=1}^{t}\eta_{j}^{2}\Big{)}\sum_{k=1}^{t}\eta_{k}^{2}.$

The stated result then follows from the Jensen’s inequality.

###  C.4 Proof of Part (c)

To prove stability bounds with high probability, we first introduce a
concentration inequality (Chernoff, 1952).

######  Lemma C.3 (Chernoff’s Bound).

Let $X_{1},\ldots,X_{t}$ be independent random variables taking values in
$\\{0,1\\}$. Let $X=\sum_{j=1}^{t}X_{j}$ and $\mu=\mathbb{E}[X]$. Then for any
$\tilde{\delta}>0$ with probability at least
$1-\exp\big{(}-\mu\tilde{\delta}^{2}/(2+\tilde{\delta})\big{)}$ we have
$X\leq(1+\tilde{\delta})\mu$. Furthermore, for any $\delta\in(0,1)$ with
probability at least $1-\delta$ we have

$X\leq\mu+\log(1/\delta)+\sqrt{2\mu\log(1/\delta)}.$

We now prove Part (c). According to the analysis in Part (a), we know

$\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\leq\left(\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+8G^{2}\eta_{t}^{2}\right)\mathbb{I}_{[i_{t}\neq
n]}+\left((1+p)\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+8(1+1/p)\eta_{t}^{2}G^{2}\right)\mathbb{I}_{[i_{t}=n]}.$

It then follows that

$\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\leq\big{(}1+p\mathbb{I}_{[i_{t}=n]}\big{)}\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+8G^{2}\eta_{t}^{2}\big{(}1+\mathbb{I}_{[i_{t}=n]}/p\big{)}.$
(C.4)

Applying this inequality recursively gives

$\displaystyle\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}$
$\displaystyle\leq
8G^{2}\eta^{2}\sum_{k=1}^{t}\big{(}1+\mathbb{I}_{[i_{k}=n]}/p\big{)}\prod_{j=k+1}^{t}\big{(}1+p\mathbb{I}_{[i_{j}=n]}\big{)}$
$\displaystyle=8G^{2}\eta^{2}\sum_{k=1}^{t}\big{(}1+\mathbb{I}_{[i_{k}=n]}/p\big{)}\prod_{j=k+1}^{t}(1+p)^{\mathbb{I}_{[i_{j}=n]}}$
$\displaystyle\leq
8G^{2}\eta^{2}(1+p)^{\sum_{j=1}^{t}\mathbb{I}_{[i_{j}=n]}}\big{(}t+\sum_{k=1}^{t}\mathbb{I}_{[i_{k}=n]}/p\big{)}.$

Applying Lemma C.3 with $X_{j}=\mathbb{I}_{[i_{j}=n]}$ and $\mu=t/n$ (note
$\mathbb{E}_{A}[X_{j}]=1/n$), with probability $1-\delta$ there holds

$\sum_{j=1}^{t}\mathbb{I}_{[i_{j}=n]}\leq
t/n+\log(1/\delta)+\sqrt{2tn^{-1}\log(1/\delta)}.$ (C.5)

The following inequality then holds with probability at least $1-\delta$

$\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\leq
8G^{2}\eta^{2}(1+p)^{t/n+\log(1/\delta)+\sqrt{2tn^{-1}\log(1/\delta)}}\Big{(}t+t/(pn)+p^{-1}\log(1/\delta)+p^{-1}\sqrt{2tn^{-1}\log(1/\delta)}\Big{)}.$

We can choose $p=\frac{1}{t/n+\log(1/\delta)+\sqrt{2tn^{-1}\log(1/\delta)}}$
(note $(1+x)^{1/x}\leq e$) and derive the following inequality with
probability at least $1-\delta$

$\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\leq
8eG^{2}\eta^{2}\Big{(}t+\big{(}t/n+\log(1/\delta)+\sqrt{2tn^{-1}\log(1/\delta)}\big{)}^{2}\Big{)}.$

This finishes the proof of Part (c).

###  C.5 Proof of Part (d)

We now turn to Part (d). Under the smoothness assumption, the analysis in Part
(b) implies

$\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\leq(1+L^{2}\eta_{t}^{2})\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}\mathbb{I}_{[i_{t}\neq
n]}+\left((1+p)\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+8(1+1/p)\eta_{t}^{2}G^{2}\right)\mathbb{I}_{[i_{t}=n]}.$

It then follows that

$\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\leq\big{(}1+L^{2}\eta_{t}^{2}+p\mathbb{I}_{[i_{t}=n]}\big{)}\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+8(1+1/p)\eta_{t}^{2}G^{2}\mathbb{I}_{[i_{t}=n]}.$

We can apply the above inequality recursively and derive

$\displaystyle\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}$
$\displaystyle\leq
8(1+1/p)G^{2}\sum_{k=1}^{t}\eta_{k}^{2}\mathbb{I}_{[i_{k}=n]}\prod_{j=k+1}^{t}\big{(}1+L^{2}\eta_{j}^{2}+p\mathbb{I}_{[i_{j}=n]}\big{)}$
$\displaystyle\leq
8(1+1/p)G^{2}\eta^{2}\sum_{k=1}^{t}\mathbb{I}_{[i_{k}=n]}\prod_{j=k+1}^{t}\big{(}1+L^{2}\eta_{j}^{2}\big{)}\prod_{j=k+1}^{t}\big{(}1+p\mathbb{I}_{[i_{j}=n]}\big{)}$
$\displaystyle=8(1+1/p)G^{2}\eta^{2}\sum_{k=1}^{t}\mathbb{I}_{[i_{k}=n]}\prod_{j=k+1}^{t}\big{(}1+L^{2}\eta_{j}^{2}\big{)}\prod_{j=k+1}^{t}\big{(}1+p\big{)}^{\mathbb{I}_{[i_{j}=n]}}$
$\displaystyle\leq
8(1+1/p)G^{2}\eta^{2}\prod_{j=1}^{t}\big{(}1+L^{2}\eta_{j}^{2}\big{)}\prod_{j=1}^{t}\big{(}1+p\big{)}^{\mathbb{I}_{[i_{j}=n]}}\sum_{k=1}^{t}\mathbb{I}_{[i_{k}=n]}.$

It then follows from the elementary inequality $1+x\leq e^{x}$ that

$\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\leq
8(1+1/p)G^{2}\eta^{2}\exp\Big{(}L^{2}\sum_{j=1}^{t}\eta_{j}^{2}\Big{)}\big{(}1+p\big{)}^{\sum_{j=1}^{t}\mathbb{I}_{[i_{j}=n]}}\sum_{k=1}^{t}\mathbb{I}_{[i_{k}=n]}$

According to (C.5), we get the following inequality with probability at least
$1-\delta$

$\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\leq
8(1+1/p)G^{2}\eta^{2}\exp\big{(}L^{2}t\eta^{2}\big{)}\big{(}1+p\big{)}^{t/n+\log(1/\delta)+\sqrt{2tn^{-1}\log(1/\delta)}}\big{(}t/n+\log(1/\delta)+\sqrt{2tn^{-1}\log(1/\delta)}\big{)}.$

We can choose $p=\frac{1}{t/n+\log(1/\delta)+\sqrt{2tn^{-1}\log(1/\delta)}}$
and derive the following inequality with probability at least $1-\delta$

$\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\leq
8eG^{2}\eta^{2}\exp\big{(}L^{2}t\eta^{2}\big{)}\Big{(}1+t/n+\log(1/\delta)+\sqrt{2tn^{-1}\log(1/\delta)}\Big{)}^{2}.$

The stated bound then follows.

###  C.6 Proof of Part (e)

If $i_{t}\neq n$, we can analyze analogously to (C.2) excepting using the
strong convexity, and show

$\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\leq(1-2\rho\eta_{t})\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+8G^{2}\eta_{t}^{2}.$

If $i_{t}=n$, then (C.3) holds. We can combine the above two cases and derive

$\displaystyle\mathbb{E}_{i_{t}}\left[\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\right]$
$\displaystyle\leq\frac{n-1}{n}\left((1-2\rho\eta_{t})\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+8G^{2}\eta_{t}^{2}\right)+\frac{1+p}{n}\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+\frac{8(1+1/p)}{n}\eta_{t}^{2}G^{2}$
$\displaystyle=(1-2\rho\eta_{t}+(2\rho\eta_{t}+p)/n)\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+8\eta_{t}^{2}G^{2}(1+1/(np)).$

We can choose $p=\rho\eta_{t}(n-2)$ to derive

$\mathbb{E}_{i_{t}}\left[\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\right]\leq(1-\rho\eta_{t})\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+8\eta_{t}^{2}G^{2}\Big{(}1+\frac{1}{n(n-2)\rho\eta_{t}}\Big{)}.$

It then follows that

$\mathbb{E}_{A}\left[\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\right]\leq
8G^{2}\sum_{j=1}^{t}\eta_{j}\Big{(}\eta_{j}+\frac{1}{n(n-2)\rho}\Big{)}\prod_{k=j+1}^{t}(1-\rho\eta_{k}).$

For $\eta_{t}=1/(\rho t)$, it follows from the identity
$\prod_{k=j+1}^{t}(1-1/k)=j/t$ that

$\mathbb{E}_{A}\left[\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}^{2}\right]\leq\frac{8G^{2}}{t\rho}\sum_{j=1}^{t}\Big{(}(\rho
j)^{-1}+\frac{1}{n(n-2)\rho}\Big{)}\leq\frac{8G^{2}}{\rho^{2}}\Big{(}\frac{\log(et)}{t}+\frac{1}{n(n-2)}\Big{)}.$

The stated result then follows from the Jensen’s inequality.

##  Appendix D Optimization Error Bounds: Convex-Concave Case

In this section, we present optimization error bounds for SGDA, which are
standard in the literature (Nemirovski et al., 2009, Nedić & Ozdaglar, 2009).
We give both bounds in expectation and bounds with high probability. The high-
probability analysis requires to use concentration inequalities for
martingales. Lemma D.1 is an Azuma-Hoeffding inequality for real-valued
martingale difference sequence (Hoeffding, 1963), while Lemma D.2 is a
Bernstein-type inequality for martingale difference sequences in a Hilbert
space (Tarres & Yao, 2014).

######  Lemma D.1.

Let $\\{\xi_{k}:k\in\mathbb{N}\\}$ be a martingale difference sequence taking
values in $\mathbb{R}$, i.e.,
$\mathbb{E}[\xi_{k}|\xi_{1},\ldots,\xi_{k-1}]=0$. Assume that
$|\xi_{k}-\mathbb{E}_{z_{k}}[\xi_{k}]|\leq b_{k}$ for each $k$. For
$\delta\in(0,1)$, with probability at least $1-\delta$ we have

$\sum_{k=1}^{n}\xi_{k}\leq\Big{(}2\sum_{k=1}^{n}b_{k}^{2}\log\frac{1}{\delta}\Big{)}^{\frac{1}{2}}.$
(D.1)

######  Lemma D.2.

Let $\\{\xi_{k}:k\in\mathbb{N}\\}$ be a martingale difference sequence in a
Hilbert space with the norm $\|\cdot\|_{2}$. Suppose that almost surely
$\|\xi_{k}\|\leq B$ and
$\sum_{k=1}^{t}\mathbb{E}[\|\xi_{k}\|^{2}|\xi_{1},\ldots,\xi_{k-1}]\leq\sigma_{t}^{2}$
for $\sigma_{t}\geq 0$. Then, for any $0<\delta<1$, the following inequality
holds with probability at least $1-\delta$

$\max_{1\leq j\leq t}\Big{\|}\sum_{k=1}^{j}\xi_{k}\Big{\|}\leq
2\Big{(}\frac{B}{3}+\sigma_{t}\Big{)}\log\frac{2}{\delta}.$

######  Lemma D.3.

Let $\\{\mathbf{w}_{t},\mathbf{v}_{t}\\}$ be the sequence produced by (4.1)
with $\eta_{t}=\eta$. Let Assumption 1 hold and $F_{S}$ be convex-concave.
Assume $\sup_{\mathbf{w}\in\mathcal{W}}\|\mathbf{w}\|_{2}\leq B_{W}$ and
$\sup_{\mathbf{v}\in\mathcal{V}}\|\mathbf{v}\|_{2}\leq B_{V}$. Then the
following inequality holds

$\mathbb{E}_{A}\big{[}\sup_{\mathbf{v}\in\mathcal{V}}F_{S}(\bar{\mathbf{w}}_{T},\mathbf{v})-\inf_{\mathbf{w}\in\mathcal{W}}F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})\big{]}\leq\eta
G^{2}+\frac{B_{W}^{2}+B_{V}^{2}}{2\eta T}+\frac{G(B_{W}+B_{V})}{\sqrt{T}},$
(D.2)

where $\big{(}\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T}\big{)}$ is defined in
(4.2). Let $\delta\in(0,1)$. Then with probability at least $1-\delta$ we have

$\sup_{\mathbf{v}\in\mathcal{V}}F_{S}(\bar{\mathbf{w}}_{T},\mathbf{v})-\inf_{\mathbf{w}\in\mathcal{W}}F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})\leq\eta
G^{2}+\frac{B_{W}^{2}+B_{V}^{2}}{2T\eta}+\frac{G\big{(}B_{W}+B_{V}\big{)}\big{(}9\log(6/\delta)+2)}{\sqrt{T}}.$
(D.3)

###### Proof.

According to the non-expansiveness of projection and (4.1), we know

$\displaystyle\|\mathbf{w}_{t+1}-\mathbf{w}\|_{2}^{2}\leq\|\mathbf{w}_{t}-\eta_{t}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\mathbf{w}\|_{2}^{2}$
$\displaystyle=\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}+\eta_{t}^{2}\|\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\|_{2}^{2}+2\eta_{t}\langle\mathbf{w}-\mathbf{w}_{t},\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\rangle$
$\displaystyle\leq\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}+\eta_{t}^{2}G^{2}+2\eta_{t}\langle\mathbf{w}-\mathbf{w}_{t},\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t};\mathbf{v}_{t})\rangle+2\eta_{t}\langle\mathbf{w}-\mathbf{w}_{t},\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\rangle,$

where we have used Assumption 1. According to the convexity of
$F_{S}(\cdot,\mathbf{v}_{t})$, we know

$2\eta_{t}\big{(}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-F_{S}(\mathbf{w},\mathbf{v}_{t})\big{)}\leq\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}-\|\mathbf{w}_{t+1}-\mathbf{w}\|_{2}^{2}+\\\
\eta_{t}^{2}G^{2}+2\eta_{t}\langle\mathbf{w}-\mathbf{w}_{t},\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\rangle.$
(D.4)

Taking a summation of the above inequality from $t=1$ to $t=T$
($\mathbf{w}_{1}=0$), we derive

$2\eta\sum_{t=1}^{T}\big{(}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-F_{S}(\mathbf{w},\mathbf{v}_{t})\big{)}\leq\|\mathbf{w}\|_{2}^{2}+T\eta^{2}G^{2}\\\
+2\eta\sum_{t=1}^{T}\langle\mathbf{w}_{t},\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\rangle+2\eta\sum_{t=1}^{T}\langle\mathbf{w},\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\rangle.$

It then follows from the concavity of $F_{S}(\mathbf{w},\cdot)$ and Schwartz’s
inequality that

$2\eta\sum_{t=1}^{T}\big{(}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})\big{)}\leq
B_{W}^{2}+T\eta^{2}G^{2}\\\
+2\eta\sum_{t=1}^{T}\langle\mathbf{w}_{t},\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\rangle+2\eta
B_{W}\Big{\|}\sum_{t=1}^{T}\big{(}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\big{)}\Big{\|}_{2}.$

Since the above inequality holds for all $\mathbf{w}$, we further get

$2\eta\sum_{t=1}^{T}\big{(}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\inf_{\mathbf{w}}F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})\big{)}\leq
B_{W}^{2}+T\eta^{2}G^{2}\\\
+2\eta\sum_{t=1}^{T}\langle\mathbf{w}_{t},\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\rangle+2\eta
B_{W}\Big{\|}\sum_{t=1}^{T}\big{(}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\big{)}\Big{\|}_{2}.$
(D.5)

Note

$\mathbb{E}_{i_{t}}\big{[}\langle\mathbf{w}_{t},\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\rangle\big{]}=0.$
(D.6)

We can take an expectation over both sides of (D.5) and get

$\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{A}\big{[}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\big{]}-\mathbb{E}_{A}\big{[}\inf_{\mathbf{w}}F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})\big{]}\leq\frac{B_{W}^{2}}{2\eta
T}+\frac{\eta
G^{2}}{2}+\frac{B_{W}}{T}\mathbb{E}_{A}\Big{[}\Big{\|}\sum_{t=1}^{T}\big{(}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\big{)}\Big{\|}_{2}\Big{]}.$

According to Jensen’s inequality and (D.6), we know

$\displaystyle\Big{(}\mathbb{E}_{A}\Big{[}\Big{\|}\sum_{t=1}^{T}\big{(}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\big{)}\Big{\|}_{2}\Big{]}\Big{)}^{2}$
$\displaystyle\leq\mathbb{E}_{A}\Big{[}\Big{\|}\sum_{t=1}^{T}\big{(}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\big{)}\Big{\|}_{2}^{2}\Big{]}$
$\displaystyle=\sum_{t=1}^{T}\mathbb{E}_{A}\Big{[}\Big{\|}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\Big{\|}_{2}^{2}\Big{]}\leq
TG^{2}.$

It then follows that

$\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{A}\big{[}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\big{]}-\mathbb{E}_{A}\big{[}\inf_{\mathbf{w}}F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})\big{]}\leq\frac{B_{W}^{2}}{2\eta
T}+\frac{\eta G^{2}}{2}+\frac{B_{W}G}{\sqrt{T}}.$ (D.7)

In a similar way, we can show that

$\mathbb{E}_{A}\big{[}\sup_{\mathbf{v}}F_{S}(\bar{\mathbf{w}}_{T},\mathbf{v})\big{]}-\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{A}\big{[}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\big{]}\leq\frac{B_{V}^{2}}{2\eta
T}+\frac{\eta G^{2}}{2}+\frac{B_{V}G}{\sqrt{T}}.$ (D.8)

The stated bound (D.2) then follows from (D.7) and (D.8).

We now turn to (D.3). It is clear that $\big{|}\langle\mathbf{w}_{t},\nabla
F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\nabla
f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\rangle\big{|}\leq 2GB_{W}$, and
therefore we can apply Lemma D.1 to derive the following inequality with
probability at least $1-\delta/6$ that

$\sum_{t=1}^{T}\langle\mathbf{w}_{t},\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\rangle\leq
2GB_{W}\Big{(}2T\log(6/\delta)\Big{)}^{\frac{1}{2}}.$ (D.9)

For any $t\in\mathbb{N}$, define
$\xi_{t}=\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})$.
Then it is clear that $\|\xi_{t}\|_{2}\leq 2G$ and

$\sum_{t=1}^{T}\mathbb{E}[\|\xi_{t}\|_{2}^{2}|\xi_{1},\ldots,\xi_{t-1}]\leq
4TG^{2}.$

Therefore, we can apply Lemma D.2 to derive the following inequality with
probability at least $1-\delta/3$

$\Big{\|}\sum_{t=1}^{T}\xi_{t}\Big{\|}_{2}\leq
2\big{(}\frac{2G}{3}+2G\sqrt{T}\big{)}\log(6/\delta).$

Then, the following inequality holds with probability at least $1-\delta/3$

$\Big{\|}\sum_{t=1}^{T}\big{(}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\big{)}\Big{\|}_{2}\leq
4G\big{(}1+\sqrt{T}\Big{)}\log(6/\delta).$

We can plug the above inequality and (D.9) back into (D.5), and derive the
following inequality with probability at least $1-\delta/2$

$\frac{1}{T}\sum_{t=1}^{T}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\inf_{\mathbf{w}}F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})\leq\frac{B_{W}^{2}}{2T\eta}+\frac{\eta
G^{2}}{2}+\frac{2GB_{W}\sqrt{2\log(6/\delta)}}{\sqrt{T}}+\frac{8B_{W}G\log(6/\delta)}{\sqrt{T}}.$

In a similar way, we can get the following inequality with probability at
least $1-\delta/2$

$\sup_{\mathbf{v}\in\mathcal{V}}F_{S}(\bar{\mathbf{w}}_{T},\mathbf{v})-\frac{1}{T}\sum_{t=1}^{T}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\leq\frac{B_{V}^{2}}{2T\eta}+\frac{\eta
G^{2}}{2}+\frac{9B_{V}G\log(6/\delta)+2B_{V}G}{\sqrt{T}}.$

Combining the above two inequalities together we get the stated inequality
with probability at least $1-\delta$. The proof is complete. ∎

The following lemma gives optimization error bounds for SC-SC problems.

######  Lemma D.4.

Let Assumption 1 hold, $t_{0}\geq 0$ and $F_{S}(\cdot,\cdot)$ be $\rho$-SC-SC
with $\rho>0$. Let $\\{\mathbf{w}_{t},\mathbf{v}_{t}\\}$ be the sequence
produced by (4.1) with $\eta_{t}=1/(\rho(t+t_{0}))$. If $t_{0}=0$, then for
$\big{(}\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T}\big{)}$ defined in (4.2) we
have

$\mathbb{E}_{A}\big{[}\sup_{\mathbf{v}\in\mathcal{V}}F_{S}(\bar{\mathbf{w}}_{T},\mathbf{v})-\inf_{\mathbf{w}\in\mathcal{W}}F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})\big{]}\leq\frac{G^{2}\log(eT)}{\rho
T}+\frac{(B_{W}+B_{V})G}{\sqrt{T}}.$ (D.10)

If $\sup_{\mathbf{w}\in\mathcal{W}}\|\mathbf{w}\|_{2}\leq B_{W}$ and
$\sup_{\mathbf{v}\in\mathcal{V}}\|\mathbf{v}\|_{2}\leq B_{V}$, then

$\triangle^{w}_{S}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})\leq\frac{2\rho
t_{0}(B_{W}^{2}+B_{V}^{2})}{T}+\frac{G^{2}\log(eT)}{\rho T}.$ (D.11)

###### Proof.

Analyzing analogously to (D.4) but using the strong convexity of
$\mathbf{w}\mapsto F_{S}(\mathbf{w},\mathbf{v})$, we derive

$2\eta_{t}\big{[}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-F_{S}(\mathbf{w},\mathbf{v}_{t})\big{]}\leq(1-\eta_{t}\rho)\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}-\|\mathbf{w}_{t+1}-\mathbf{w}\|_{2}^{2}+\eta_{t}^{2}G^{2}+\xi_{t}(\mathbf{w}),$

where
$\xi_{t}(\mathbf{w})=2\eta_{t}\langle\mathbf{w}-\mathbf{w}_{t},\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\rangle$.
Since $\eta_{t}=1/(\rho(t+t_{0}))$, we further get

$\frac{2}{\rho(t+t_{0})}\big{[}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-F_{S}(\mathbf{w},\mathbf{v}_{t})\big{]}\leq(1-1/(t+t_{0}))\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}-\|\mathbf{w}_{t+1}-\mathbf{w}\|_{2}^{2}+\frac{G^{2}}{\rho^{2}(t+t_{0})^{2}}+\xi_{t}(\mathbf{w}).$

Multiplying both sides by $t+t_{0}$ gives

$\frac{2}{\rho}\big{[}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-F_{S}(\mathbf{w},\mathbf{v}_{t})\big{]}\leq(t+t_{0}-1)\|\mathbf{w}_{t}-\mathbf{w}\|_{2}^{2}-(t+t_{0})\|\mathbf{w}_{t+1}-\mathbf{w}\|_{2}^{2}+(t+t_{0})\xi_{t}(\mathbf{w})+\frac{G^{2}}{\rho^{2}(t+t_{0})}.$

Taking a summation of the above inequality further gives

$\sum_{t=1}^{T}\big{[}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-F_{S}(\mathbf{w},\mathbf{v}_{t})\big{]}\leq
2\rho
t_{0}B_{W}^{2}+\frac{G^{2}\log(eT)}{2\rho}+\frac{\rho}{2}\sum_{t=1}^{T}(t+t_{0})\xi_{t}(\mathbf{w}),$

where we have used $\sum_{t=1}^{T}t^{-1}\leq\log(eT)$. This together with the
concavity of $\mathbf{v}\mapsto F_{S}(\mathbf{w},\mathbf{v})$ gives

$\sum_{t=1}^{T}\big{[}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})\big{]}\leq
2\rho
t_{0}B_{W}^{2}+\frac{G^{2}\log(eT)}{2\rho}+\frac{\rho}{2}\sum_{t=1}^{T}(t+t_{0})\xi_{t}(\mathbf{w}).$
(D.12)

Since the above inequality holds for any $\mathbf{w}$, we know

$\sum_{t=1}^{T}\big{[}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\inf_{\mathbf{w}\in\mathcal{W}}F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})\big{]}\leq
2\rho
t_{0}B_{W}^{2}+\frac{G^{2}\log(eT)}{2\rho}+\frac{\rho}{2}\sup_{\mathbf{w}\in\mathcal{W}}\sum_{t=1}^{T}(t+t_{0})\xi_{t}(\mathbf{w}).$

Since
$\mathbb{E}_{A}[\langle\mathbf{w}_{t},\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\rangle]=0$
we know

$\displaystyle\mathbb{E}_{A}\big{[}\sup_{\mathbf{w}\in\mathcal{W}}\sum_{t=1}^{T}(t+t_{0})\xi_{t}(\mathbf{w})\big{]}$
$\displaystyle=2\mathbb{E}_{A}\Big{[}\sup_{\mathbf{w}\in\mathcal{W}}\sum_{t=1}^{T}(t+t_{0})\eta_{t}\langle\mathbf{w},\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\rangle\Big{]}$
$\displaystyle\leq
2\sup_{\mathbf{w}\in\mathcal{W}}\|\mathbf{w}\|_{2}\mathbb{E}_{A}\Big{\|}\sum_{t=1}^{T}(t+t_{0})\eta_{t}\big{(}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\big{)}\Big{\|}_{2}$
$\displaystyle\leq
2B_{W}\bigg{(}\mathbb{E}_{A}\bigg{\|}\sum_{t=1}^{T}(t+t_{0})\eta_{t}\big{(}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\big{)}\bigg{\|}_{2}^{2}\bigg{)}^{1/2}$
$\displaystyle\leq
2B_{W}\left(\sum_{t=1}^{T}(t+t_{0})^{2}\eta_{t}^{2}\mathbb{E}_{A}\|\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\|_{2}^{2}\right)^{1/2}\leq
2B_{W}G\rho^{-1}\sqrt{T}.$

We can combine the above two inequalities together and derive

$\sum_{t=1}^{T}\mathbb{E}_{A}\big{[}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\inf_{\mathbf{w}\in\mathcal{W}}F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})\big{]}\leq
2\rho t_{0}B_{W}^{2}+\frac{G^{2}\log(eT)}{2\rho}+B_{W}G\sqrt{T}.$

In a similar way one can show

$\sum_{t=1}^{T}\mathbb{E}_{A}\big{[}\sup_{\mathbf{v}\in\mathcal{V}}F_{S}(\bar{\mathbf{w}}_{T},\mathbf{v})-F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\big{]}\leq
2\rho t_{0}B_{V}^{2}+\frac{G^{2}\log(eT)}{2\rho}+B_{V}G\sqrt{T}.$

We can combine the above two inequalities together, and get the following
optimization error bounds

$T\mathbb{E}_{A}\big{[}\sup_{\mathbf{v}\in\mathcal{V}}F_{S}(\bar{\mathbf{w}}_{T},\mathbf{v})-\inf_{\mathbf{w}\in\mathcal{W}}F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})\big{]}\leq
2\rho
t_{0}(B_{W}^{2}+B_{V}^{2})+\frac{G^{2}\log(eT)}{\rho}+(B_{W}+B_{V})G\sqrt{T}.$

This proves (D.10) with $t_{0}=0$.

We now turn to (D.11). Since $\mathbb{E}_{A}[\xi_{t}(\mathbf{w})]=0$, it
follows from (D.12) that

$\sum_{t=1}^{T}\mathbb{E}_{A}\big{[}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})\big{]}\leq
2\rho t_{0}B_{W}^{2}+\frac{G^{2}\log(eT)}{2\rho}.$

In a similar way, one can show

$\sum_{t=1}^{T}\mathbb{E}_{A}\big{[}F_{S}(\bar{\mathbf{w}}_{T},\mathbf{v})-F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\big{]}\leq
2\rho t_{0}B_{V}^{2}+\frac{G^{2}\log(eT)}{2\rho}.$

We can combine the above two inequalities together and derive

$\mathbb{E}\big{[}F_{S}(\bar{\mathbf{w}}_{T},\mathbf{v})-F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T}\big{]}\leq\frac{2\rho
t_{0}(B_{W}^{2}+B_{V}^{2})}{T}+\frac{G^{2}\log(eT)}{\rho T}.$

The stated bound (D.11) then follows by taking the supremum over $\mathbf{w}$
and $\mathbf{v}$. The proof is complete. ∎

##  Appendix E Proofs on Generalization Bounds: Convex-Concave Case

In this section, we prove the generalization bounds of SGDA in a convex-
concave case. We first prove Theorem 3 on bounds of weak PD population risks
in expectation.

###### Proof of Theorem 3.

We first prove Part (a). We have the decomposition

$\triangle^{w}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})=\triangle^{w}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})-\triangle^{w}_{S}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})+\triangle^{w}_{S}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T}).$
(E.1)

According to Part (a) of Theorem 2 we know the following inequality for all
$t$

$\mathbb{E}_{A}\left[\left\|\begin{pmatrix}\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\\\
\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\end{pmatrix}\right\|_{2}\right]\leq
4\eta G\Big{(}\sqrt{t}+\frac{t}{n}\Big{)}.$

It then follows from the convexity of a norm that

$\mathbb{E}_{A}\left[\left\|\begin{pmatrix}\bar{\mathbf{w}}_{T}-\bar{\mathbf{w}}_{T}^{\prime}\\\
\bar{\mathbf{v}}_{T}-\bar{\mathbf{v}}_{T}^{\prime}\end{pmatrix}\right\|_{2}\right]\leq
4\eta G\Big{(}\sqrt{T}+\frac{T}{n}\Big{)}$

and therefore

$\sup_{z}\Big{(}\sup_{\mathbf{v}^{\prime}\in\mathcal{V}}\mathbb{E}_{A}\big{[}f(\bar{\mathbf{w}}_{T},\mathbf{v}^{\prime};z)-f(\bar{\mathbf{w}}_{T}^{\prime},\mathbf{v}^{\prime};z)\big{]}+\sup_{\mathbf{w}^{\prime}\in\mathcal{W}}\mathbb{E}_{A}\big{[}f(\mathbf{w}^{\prime},\bar{\mathbf{v}}_{T};z)-f(\mathbf{w}^{\prime},\bar{\mathbf{v}}_{T}^{\prime};z)\big{]}\Big{)}\\\
\leq
G\Big{(}\mathbb{E}_{A}\big{[}\big{\|}\bar{\mathbf{w}}_{T}-\bar{\mathbf{w}}_{T}^{\prime}\|_{2}\big{]}+\mathbb{E}_{A}\big{[}\big{\|}\bar{\mathbf{v}}_{T}-\bar{\mathbf{v}}_{T}^{\prime}\big{\|}_{2}\big{]}\Big{)}\leq
4\sqrt{2}\eta G^{2}\Big{(}\sqrt{T}+\frac{T}{n}\Big{)}.$

According to Part (a) of Theorem 1, we know

$\triangle^{w}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})-\triangle^{w}_{S}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})\leq
4\sqrt{2}\eta G^{2}\Big{(}\sqrt{T}+\frac{T}{n}\Big{)}.$

According to Eq. (D.2), we know

$\triangle^{w}_{S}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})\leq\eta
G^{2}+\frac{B_{W}^{2}+B_{V}^{2}}{2\eta T}+\frac{G(B_{W}+B_{V})}{\sqrt{T}}.$

The bound (4.3) then follows directly from (E.1).

Eq. (4.4) in Part (b) can be proved in a similar way (e.g., by combining the
stability bounds in Part (b) of Theorem 2 and optimization error bounds in Eq.
(D.2) together). We omit the proof for brevity.

We now turn to Part (c). According to Part (e) of Theorem 2 and the convexity
of norm, we know

$\mathbb{E}_{A}\left[\left\|\begin{pmatrix}\bar{\mathbf{w}}_{T}-\bar{\mathbf{w}}_{T}^{\prime}\\\
\bar{\mathbf{v}}_{T}-\bar{\mathbf{v}}_{T}^{\prime}\end{pmatrix}\right\|_{2}\right]\leq\frac{2\sqrt{2}G}{\rho}\Big{(}\frac{\log^{\frac{1}{2}}(eT)}{\sqrt{T}}+\frac{1}{\sqrt{n(n-2)}}\Big{)}.$

Analyzing analogous to Part (a), we further know

$\triangle^{w}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})-\triangle^{w}_{S}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})\leq\frac{4G^{2}}{\rho}\Big{(}\frac{\log^{\frac{1}{2}}(eT)}{\sqrt{T}}+\frac{1}{\sqrt{n(n-2)}}\Big{)}.$