This together with the optimization error bounds in Lemma D.4 and (E.1) gives

$\triangle^{w}(\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{)}+\frac{G^{2}\log(eT)}{\rho
T}+\frac{(B_{W}+B_{V})G}{\sqrt{T}}.$

The stated bound then follows from the choice of $T$. The proof is complete.

Finally, we consider Part (d). Since $t_{0}\geq L^{2}/\rho^{2}$ we know
$\eta_{t}=1/(\rho(t+t_{0}))\leq\rho/L^{2}.$ The stability analysis in Farnia &
Ozdaglar (2020)333Farnia & Ozdaglar (2020) considered the constant step size
$\eta_{t}=\eta\leq\rho/L^{2}$. It is direct to extend the analysis there to
any step size $\eta_{t}\leq\rho/L^{2}$ since an algorithm would be more stable
if the step size decreases. then shows that $A$ is $\epsilon$-argument stable
with $\epsilon=O(1/(\rho n)).$ This together with Part (a) of Theorem 1 then
shows that

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

We can combine the above generalization bound and the optimization error bound
in (D.11) together, and get

$\triangle^{w}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})=O(1/(\rho
n))+O\Big{(}\frac{\rho}{T}+\frac{\log(eT)}{\rho T}\Big{)}.$

The stated bound then follows from $T\asymp n$. The proof is complete. ∎

We now present proofs of Theorem 4 on primal population risks.

###### Proof of Theorem 4.

We have the decomposition

$R(\bar{\mathbf{w}}_{T})-R(\mathbf{w}^{*})=\big{(}R(\bar{\mathbf{w}}_{T})-R_{S}(\bar{\mathbf{w}}_{T})\big{)}+\big{(}R_{S}(\bar{\mathbf{w}}_{T})-F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})\big{)}\\\
+\big{(}F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})-F(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})\big{)}+\big{(}F(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})-F(\mathbf{w}^{*},\mathbf{v}^{*})\big{)}.$

Since $F(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})\leq
F(\mathbf{w}^{*},\mathbf{v}^{*})$, it then follows that

$R(\bar{\mathbf{w}}_{T})-R(\mathbf{w}^{*})\leq\big{(}R(\bar{\mathbf{w}}_{T})-R_{S}(\bar{\mathbf{w}}_{T})\big{)}+\big{(}R_{S}(\bar{\mathbf{w}}_{T})-F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})\big{)}+\big{(}F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})-F(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})\big{)}.$
(E.2)

Taking an expectation on both sides gives

$\mathbb{E}\big{[}R(\bar{\mathbf{w}}_{T})-R(\mathbf{w}^{*})\big{]}\leq\mathbb{E}\big{[}R(\bar{\mathbf{w}}_{T})-R_{S}(\bar{\mathbf{w}}_{T})\big{]}+\mathbb{E}\big{[}R_{S}(\bar{\mathbf{w}}_{T})-F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})\big{]}+\mathbb{E}\big{[}F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})-F(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})\big{]}.$
(E.3)

Note that the first and the third term on the right-hand side is related to
generalization, while the second term
$R_{S}(\bar{\mathbf{w}}_{T})-F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})$ is
related to optimization. According to Part (b) 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\frac{G\sqrt{8e(t+t^{2}/n)}}{\sqrt{n}}\exp\Big{(}L^{2}t\eta^{2}/2\Big{)}\eta.$

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\frac{G\sqrt{8e(T+T^{2}/n)}}{\sqrt{n}}\exp\Big{(}L^{2}T\eta^{2}/2\Big{)}\eta.$
(E.4)

This together with Part (b) of Theorem 1 implies that

$\mathbb{E}_{S,A}\Big{[}R(\bar{\mathbf{w}}_{T})-R_{S}(\bar{\mathbf{w}}_{T})\Big{]}\leq\frac{\big{(}1+L/\rho\big{)}G^{2}\eta\sqrt{8e(T+T^{2}/n)}\exp\big{(}L^{2}T\eta^{2}/2\big{)}}{\sqrt{n}}.$

Similarly, the stability bound (E.4) also implies the following bound on the
gap between the population and empirical risk

$\mathbb{E}_{S,A}\Big{[}F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})-F(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})\Big{]}\leq\frac{\big{(}1+L/\rho\big{)}G^{2}\eta\sqrt{8e(T+T^{2}/n)}\exp\big{(}L^{2}T\eta^{2}/2\big{)}}{\sqrt{n}}.$

According to Lemma D.3, we know

$\mathbb{E}_{A}\big{[}R_{S}(\bar{\mathbf{w}}_{T})-F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})\big{]}\leq\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}}.$

We can plug the above three inequalities back into (E.3), and derive the
stated bound on the excess primal population risk in expectation.

We now turn to the high-probability bounds. According to Assumption 1 and Part
(d) of Theorem 2, we know that with probability at least $1-\delta/4$ that
SGDA is $\epsilon$-uniformly stable, where $\epsilon$ satisfies

$\epsilon=O\Big{(}\eta\exp(L^{2}T\eta^{2}/2)\big{(}Tn^{-1}+\log(1/\delta)\big{)}\Big{)}.$
(E.5)

This together with Part (d) of Theorem 1 implies the following inequality with
probability at least $1-\delta/2$

$R(\bar{\mathbf{w}}_{T})-R_{S}(\bar{\mathbf{w}}_{T})=O\Big{(}L\rho^{-1}\epsilon\log
n\log(1/\delta)+n^{-\frac{1}{2}}\sqrt{\log(1/\delta)}\Big{)},$

where $\epsilon$ satisfies (E.5). In a similar way, one can use Part (d) of
Theorem 1 and stability bounds in Part (d) of Theorem 2 to show the following
inequality with probability at least $1-\delta/4$

$F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})-F(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})=O\Big{(}\log
n\log(1/\delta)\epsilon\Big{)}+O(n^{-\frac{1}{2}}\log^{\frac{1}{2}}(1/\delta)).$
(E.6)

According to (D.3), we derive the following inequality with probability at
least $1-\delta/4$

$\displaystyle
R_{S}(\bar{\mathbf{w}}_{T})-F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})$
$\displaystyle=\sup_{\mathbf{v}\in\mathcal{V}}F_{S}(\bar{\mathbf{w}}_{T},\mathbf{v})-F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})=O\Big{(}\eta+(T\eta)^{-1}+T^{-\frac{1}{2}}\log(1/\delta)\Big{)}.$

We can plug the above three inequalities back into (E.2) and derive the
following inequality with probability at least $1-\delta$

$R(\bar{\mathbf{w}}_{T})-R(\mathbf{w}^{*})=O\Big{(}L\rho^{-1}\eta\exp(L^{2}T\eta^{2}/2)\log
n\log(1/\delta)\big{(}Tn^{-1}+\log(1/\delta)\big{)}\Big{)}+O(n^{-\frac{1}{2}}\sqrt{\log(1/\delta)})\\\
+O\Big{(}\eta+(T\eta)^{-1}+T^{-\frac{1}{2}}\log(1/\delta)\Big{)}.$ (E.7)

The high-probability bound (4.6) then follows from the choice of $T$ and
$\eta$. The proof is complete. ∎

Finally, we present high-probability bounds of plain generalization errors for
SGDA.

######  Theorem E.1 (High-probability bounds).

Let $\\{\mathbf{w}_{t},\mathbf{v}_{t}\\}$ be the sequence 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.
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). Let
$\sup_{\mathbf{w}\in\mathcal{W}}\|\mathbf{w}\|_{2}\leq
B_{W},\sup_{\mathbf{v}\in\mathcal{V}}\|\mathbf{v}\|_{2}\leq B_{V}$ and
$\delta\in(0,1)$. Let
$\widetilde{\triangle}_{T}=\big{|}F(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})-F(\mathbf{w}^{*},\mathbf{v}^{*})\big{|}$.

  1. (a)

If Assumption 1 holds, then with probability at least $1-\delta$

$\widetilde{\triangle}_{T}=O\Big{(}\eta\log
n\log(1/\delta)\big{(}\sqrt{T}+Tn^{-1}+\log(1/\delta)\big{)}\Big{)}+O(n^{-\frac{1}{2}}\log^{\frac{1}{2}}(1/\delta))+O\Big{(}(T\eta)^{-1}+T^{-\frac{1}{2}}\log(1/\delta)\Big{)}.$

If we choose $T\asymp n^{2}$ and $\eta\asymp T^{-3/4}$ then we get the
following inequality with probability at least $1-\delta$

$\widetilde{\triangle}_{T}=O(n^{-1/2}\log n\log^{2}(1/\delta)).$ (E.8)

  2. (b)

If Assumptions 1, 2 hold, then the following inequality holds with probability
at least $1-\delta$

$\widetilde{\triangle}_{T}=O\Big{(}\eta\log
n\log(1/\delta)\exp\big{(}L^{2}T\eta^{2}/2\big{)}\big{(}Tn^{-1}+\log(1/\delta)\big{)}+n^{-\frac{1}{2}}\log^{\frac{1}{2}}(1/\delta)+(T\eta)^{-1}+T^{-\frac{1}{2}}\log(1/\delta)\Big{)}.$

In particular, we can choose $T\asymp n$ and $\eta\asymp T^{-1/2}$ to derive
(E.8) with probability at least $1-\delta$.

###### Proof.

We use the error decomposition

$F(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})-F(\mathbf{w}^{*},\mathbf{v}^{*})=F(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})-F_{S}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})+F_{S}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})-F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})\\\
+F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})-F(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})+F(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})-F(\mathbf{w}^{*},\mathbf{v}^{*}).$
(E.9)

We first prove Part (a). According to Assumption 1 and Part (c) of Theorem 2,
we know that SGDA is $\epsilon$-uniformly stable with probability at least
$1-\delta/4$, where

$\epsilon=O\Big{(}\eta\big{(}\sqrt{T}+Tn^{-1}+\log(1/\delta)\big{)}\Big{)}.$

This together with Part (e) of Theorem 1 implies the following inequality with
probability at least $1-\delta/2$

$F(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})-F_{S}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})=O\Big{(}\eta\log
n\log(1/\delta)\big{(}\sqrt{T}+Tn^{-1}+\log(1/\delta)\big{)}\Big{)}+O(n^{-\frac{1}{2}}\log^{\frac{1}{2}}(1/\delta)).$
(E.10)

Similarly, the following inequality holds with probability at least
$1-\delta/4$

$F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})-F(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})=O\Big{(}\eta\log
n\log(1/\delta)\big{(}\sqrt{T}+Tn^{-1}+\log(1/\delta)\big{)}\Big{)}+O(n^{-\frac{1}{2}}\log^{\frac{1}{2}}(1/\delta)).$
(E.11)

According to Lemma D.3, the following inequality holds with probability at
least $1-\delta/4$

$\displaystyle
F_{S}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})-F_{S}(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})$
$\displaystyle\leq\sup_{\mathbf{v}}F_{S}(\bar{\mathbf{w}}_{T},\mathbf{v})-\inf_{\mathbf{w}}F_{S}(\mathbf{w},\bar{\mathbf{v}}_{T})=O\Big{(}\eta+(T\eta)^{-1}+T^{-\frac{1}{2}}\log(1/\delta)\Big{)}.$
(E.12)

According to the definition of $(\mathbf{w}^{*},\mathbf{v}^{*})$, we know
$F(\mathbf{w}^{*},\bar{\mathbf{v}}_{T})\leq F(\mathbf{w}^{*},\mathbf{v}^{*})$.
We can plug this inequality and (E.10), (E.11), (E.12) back into (E.9), and
derive the following inequality with probability at least $1-\delta/2$

$F(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})-F(\mathbf{w}^{*},\mathbf{v}^{*})=O\Big{(}\eta\log
n\log(1/\delta)\big{(}\sqrt{T}+Tn^{-1}+\log(1/\delta)\big{)}\Big{)}\\\
+O(n^{-\frac{1}{2}}\log^{\frac{1}{2}}(1/\delta))+O\Big{(}(T\eta)^{-1}+T^{-\frac{1}{2}}\log(1/\delta)\Big{)}.$

Analyzing in a similar way but using the error decomposition

$F(\mathbf{w}^{*},\mathbf{v}^{*})-F(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})=F(\mathbf{w}^{*},\mathbf{v}^{*})-F(\bar{\mathbf{w}}_{T},\mathbf{v}^{*})+F(\bar{\mathbf{w}}_{T},\mathbf{v}^{*})-F_{S}(\bar{\mathbf{w}}_{T},\mathbf{v}^{*})\\\
+F_{S}(\bar{\mathbf{w}}_{T},\mathbf{v}^{*})-F_{S}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})+F_{S}(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})-F(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T}),$

one can derive the following inequality with probability at least $1-\delta/2$

$F(\mathbf{w}^{*},\mathbf{v}^{*})-F(\bar{\mathbf{w}}_{T},\bar{\mathbf{v}}_{T})=O\Big{(}\eta\log
n\log(1/\delta)\big{(}\sqrt{T}+Tn^{-1}+\log(1/\delta)\big{)}\Big{)}\\\
+O(n^{-\frac{1}{2}}\log^{\frac{1}{2}}(1/\delta))+O\Big{(}(T\eta)^{-1}+T^{-\frac{1}{2}}\log(1/\delta)\Big{)}.$

The stated bound then follows as a combination of the above two inequalities.

Part (b) can be derived similarly excepting using the stability bounds in Part
(d) of Theorem 2. We omit the proof for brevity. The proof is complete. ∎

##  Appendix F Stability and Generalization Bounds of SGDA on Non-Convex
Objectives

###  F.1 Proof of Theorem 5

In this section, we show the stability and generalization bounds of SGDA for
weakly-convex-weakly-concave objectives. We first introduce some lemmas. As an
extension of a lemma in Hardt et al. (2016), the next lemma is motivated by
the fact that SGDA typically runs several iterations before encountering the
different example between $S$ and $S^{\prime}$.

######  Lemma F.1.

Assume $|f(\cdot,\cdot,z)|\leq 1$ for any $z$ and let Assumption 1 hold. 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. Denote

$\displaystyle\Delta_{t}=\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}^{\prime}_{t}\\\
\mathbf{v}_{t}-\mathbf{v}^{\prime}_{t}\end{pmatrix}\right\|_{2}.$ (F.1)

Then for any $t_{0}\in\mathbb{N}$ and any
$\mathbf{w}^{\prime},\mathbf{v}^{\prime}$ we have

$\displaystyle\mathbb{E}[f(\mathbf{w}_{T},\mathbf{v}^{\prime};z)-f(\mathbf{w}^{\prime}_{T},\mathbf{v}^{\prime};z)+f(\mathbf{w}^{\prime},\mathbf{v}_{T};z)-f(\mathbf{w}^{\prime},\mathbf{v}^{\prime}_{T};z)]\leq\frac{4t_{0}}{n}+\sqrt{2}G\mathbb{E}[\Delta_{T}|\Delta_{t_{0}}=0].$

###### Proof.

According to Assumption 1, we know

$f(\mathbf{w}_{T},\mathbf{v}^{\prime};z)-f(\mathbf{w}^{\prime}_{T},\mathbf{v}^{\prime};z)+f(\mathbf{w}^{\prime},\mathbf{v}_{T};z)-f(\mathbf{w}^{\prime},\mathbf{v}^{\prime}_{T};z)\leq
G\sqrt{2}\Delta_{T}.$ (F.2)

Let $\mathcal{E}$ denote the event that $\Delta_{t_{0}}=0$. Then we have

$\displaystyle\mathbb{E}[f(\mathbf{w}_{T},\mathbf{v}^{\prime};z)-f(\mathbf{w}^{\prime}_{T},\mathbf{v}^{\prime};z)+f(\mathbf{w}^{\prime},\mathbf{v}_{T};z)-f(\mathbf{w}^{\prime},\mathbf{v}^{\prime}_{T};z)]$
$\displaystyle=$
$\displaystyle\mathbb{P}[\mathcal{E}]\mathbb{E}[f(\mathbf{w}_{T},\mathbf{v}^{\prime};z)-f(\mathbf{w}^{\prime}_{T},\mathbf{v}^{\prime};z)+f(\mathbf{w}^{\prime},\mathbf{v}_{T};z)-f(\mathbf{w}^{\prime},\mathbf{v}^{\prime}_{T};z)|\mathcal{E}]$
$\displaystyle+\mathbb{P}[\mathcal{E}^{c}]\mathbb{E}[f(\mathbf{w}_{T},\mathbf{v}^{\prime};z)-f(\mathbf{w}^{\prime}_{T},\mathbf{v}^{\prime};z)+f(\mathbf{w}^{\prime},\mathbf{v}_{T};z)-f(\mathbf{w}^{\prime},\mathbf{v}^{\prime}_{T};z)|\mathcal{E}^{c}]$
$\displaystyle\leq$
$\displaystyle\sqrt{2}G\mathbb{E}[\Delta_{T}|\mathcal{E}]+4\mathbb{P}[\mathcal{E}^{c}],$

where in the last step we have used (F.2) and the condition
$|f(\cdot,\cdot,z)|\leq 1$. Using the union bound on the outcome $i_{t}=n$ we
obtain that

$\displaystyle\mathbb{P}[\mathcal{E}^{c}]\leq\sum_{t=1}^{t_{0}}\mathbb{P}[i_{t}=n]=\frac{t_{0}}{n}.$

The proof is complete by combining the above two inequalities together. ∎

Lemma F.2 shows the monotonity of the gradient for weakly-convex-weakly-
concave functions. Its proof is well known in the literature (Rockafellar,
1976, Liu et al., 2020).

######  Lemma F.2.

Let $f$ be a $\rho$-weakly-convex-weakly-concave function. 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}.$ (F.3)

We are now ready to prove Theorem 5.

###### Proof of Theorem 5.

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 Lemma F.2 and the
Lipschitz continuity of $f$ 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}\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}=\bigg{\|}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}^{\prime}_{t}\\\
\mathbf{v}_{t}-\mathbf{v}^{\prime}_{t}\end{pmatrix}\bigg{\|}_{2}^{2}$
$\displaystyle+\eta_{t}^{2}\bigg{\|}\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime}_{t},\mathbf{v}^{\prime}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\\\
\nabla_{\mathbf{v}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{v}}f(\mathbf{w}^{\prime}_{t},\mathbf{v}^{\prime}_{t};z_{i_{t}})\end{pmatrix}\bigg{\|}_{2}^{2}-2\eta_{t}\bigg{\langle}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}^{\prime}_{t}\\\
\mathbf{v}_{t}-\mathbf{v}^{\prime}_{t}\end{pmatrix},\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime}_{t},\mathbf{v}^{\prime}_{t};z_{i_{t}})\\\
\nabla_{\mathbf{v}}f(\mathbf{w}^{\prime}_{t},\mathbf{v}^{\prime}_{t};z_{i_{t}})-\nabla_{\mathbf{v}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\end{pmatrix}\bigg{\rangle}$
$\displaystyle\leq$
$\displaystyle(1+2\eta_{t}\rho)\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}.$
(F.4)

If $i_{t}=n$, then it follows from the elementary inequality
$(a+b)^{2}\leq(1+p)a^{2}+(1+1/p)b^{2}$ 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}.$
(F.5)

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((1+2\eta_{t}\rho)\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\leq(1+2\eta_{t}\rho+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)).$

Let $t_{0}\in\mathbb{N}$ and $\mathcal{E}$ be defined as in the proof of Lemma
F.1. We apply the above equation recursively from $t=t_{0}+1$ to $T$, then

$\displaystyle\mathbb{E}_{A}\left[\left\|\begin{pmatrix}\mathbf{w}_{T}-\mathbf{w}_{T}^{\prime}\\\
\mathbf{v}_{T}-\mathbf{v}_{T}^{\prime}\end{pmatrix}\right\|_{2}^{2}\bigg{|}\
\mathcal{E}\right]\leq
8G^{2}\big{(}1+1/(np)\big{)}\sum_{t=t_{0}+1}^{T}\eta_{t}^{2}\prod_{k=t+1}^{T}\big{(}1+2\eta_{k}\rho+p/n\big{)}.$

By the elementary inequality $1+a\leq\exp(a)$ and $\eta_{t}=\frac{c}{t}$, 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}\bigg{|}\
\mathcal{E}\right]\leq$ $\displaystyle
8G^{2}\big{(}1+1/(np)\big{)}\sum_{t=t_{0}+1}^{T}\frac{c^{2}}{t^{2}}\prod_{k=t+1}^{T}\exp\Big{(}\frac{2c\rho}{k}+\frac{p}{n}\Big{)}$
$\displaystyle\leq$ $\displaystyle
8G^{2}\big{(}1+1/(np)\big{)}\sum_{t=t_{0}+1}^{T}\frac{c^{2}}{t^{2}}\exp\Big{(}\sum_{k=t+1}^{T}\frac{2c\rho}{k}+\frac{pT}{n}\Big{)}.$

By taking $p=n/T$ in the above inequality, 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}\bigg{|}\
\mathcal{E}\right]\leq$ $\displaystyle
8eG^{2}\Big{(}1+\frac{T}{n^{2}}\Big{)}\sum_{t=t_{0}+1}^{T}\frac{c^{2}}{t^{2}}\exp\Big{(}\sum_{k=t+1}^{T}\frac{2c\rho}{k}\Big{)}$
$\displaystyle\leq$ $\displaystyle
8eG^{2}\Big{(}1+\frac{T}{n^{2}}\Big{)}\sum_{t=t_{0}+1}^{T}\frac{c^{2}}{t^{2}}\exp\Big{(}2c\rho\log\Big{(}\frac{T}{t}\Big{)}\Big{)}$
$\displaystyle\leq$ $\displaystyle
8c^{2}eG^{2}\Big{(}1+\frac{T}{n^{2}}\Big{)}T^{2c\rho}\sum_{t=t_{0}+1}^{T}\frac{1}{t^{2c\rho+2}}$
$\displaystyle\leq$
$\displaystyle\frac{8c^{2}eG^{2}}{2c\rho+1}\Big{(}1+\frac{T}{n^{2}}\Big{)}\Big{(}\frac{T}{t_{0}}\Big{)}^{2c\rho}\frac{1}{t_{0}}.$

Combining the above inequality and Lemma F.1 together, we obtain

$\displaystyle\mathbb{E}_{A}[f(\mathbf{w}_{T},\mathbf{v}^{\prime};z)-f(\mathbf{w}^{\prime}_{T},\mathbf{v}^{\prime};z)+f(\mathbf{w}^{\prime},\mathbf{v}_{T};z)-f(\mathbf{w}^{\prime},\mathbf{v}^{\prime}_{T};z)]\leq$
$\displaystyle\frac{4t_{0}}{n}+\frac{4\sqrt{e}cG^{2}}{\sqrt{2c\rho+1}}\Big{(}1+\frac{\sqrt{T}}{n}\Big{)}\Big{(}\frac{T}{t_{0}}\Big{)}^{c\rho}\frac{1}{\sqrt{t_{0}}}.$
(F.6)

The right hand side is approximately minimized when

$t_{0}=\bigg{(}\frac{\sqrt{e}cG^{2}}{\sqrt{2c\rho+1}}\Big{(}1+\frac{\sqrt{T}}{n}\Big{)}T^{c\rho}n\bigg{)}^{\frac{2}{2c\rho+3}}.$

Plugging it into the Eq. (F.6) we have (for simplicity we assume the above
$t_{0}$ is an integer)

$\displaystyle\mathbb{E}_{A}[f(\mathbf{w}_{T},\mathbf{v}^{\prime};z)-f(\mathbf{w}^{\prime}_{T},\mathbf{v}^{\prime};z)+f(\mathbf{w}^{\prime},\mathbf{v}_{T};z)-f(\mathbf{w}^{\prime},\mathbf{v}^{\prime}_{T};z)]\leq$
$\displaystyle
8\bigg{(}\frac{\sqrt{e}cG^{2}}{\sqrt{2c\rho+1}}\Big{(}1+\frac{\sqrt{T}}{n}\Big{)}T^{c\rho}\bigg{)}^{\frac{2}{2c\rho+3}}\bigg{(}\frac{1}{n}\bigg{)}^{\frac{2c\rho+1}{2c\rho+3}}.$

Since the above bound holds for all $z,S,S^{\prime}$ and
$\mathbf{w}^{\prime},\mathbf{v}^{\prime}$, we immediately get the same upper
bound on the weak stability. Finally the theorem holds by calling Theorem 1,
Part (a). ∎

###  F.2 High-Probability Stability and Generalization Bounds

In this section, we give stability and generalization bounds of SGDA with
nonconvex-nonconcave smooth objectives with high probability. The analysis
requires a tail bound for a linear combination of independent Bernoulli random
variables Raghavan (1988).

######  Lemma F.3.

Let $c_{t}\in(0,1]$ and let $X_{1},\cdots,X_{T}$ be independent Bernoulli
random variables with the success rate of $X_{t}$ being $p_{t}\in[0,1]$.
Denote $s=\sum_{t=1}^{T}c_{t}p_{t}$. Then, for all $a>0$,

$\displaystyle\mathbb{P}\Big{[}\sum_{t=1}^{T}c_{t}X_{t}\geq(1+a)s\Big{]}\leq\Big{(}\frac{e^{a}}{(1+a)^{(1+a)}}\Big{)}^{s}.$

In particular, for all $\delta\in(0,1)$ such that $\log(1/\delta)<s$ with
probability at least $1-\delta$ we have

$\displaystyle\sum_{t=1}^{T}c_{t}X_{t}\leq s+(e-1)\sqrt{\log(1/\delta)s}.$

######  Theorem F.4.

Let $\\{\mathbf{w}_{t},\mathbf{v}_{t}\\}$ be the sequence produced by (4.1)
with $\eta_{t}\leq\frac{c}{t}$ for some $c>0$. Assume Assumption 1, 2 hold and
$|f(\cdot,\cdot;z)|\leq 1$. For any $\delta\in(0,1)$, if
$c\leq\frac{1}{(n\log(2/\delta)-1)L}$, then with probability at least
$1-\delta$ we have

$\big{|}F(\mathbf{w}_{T},\mathbf{v}_{T})-F_{S}(\mathbf{w}_{T},\mathbf{v}_{T})\big{|}=O\Big{(}T^{cL}\log(n)\log^{3/2}(1/\delta)n^{-1/2}+n^{-1/2}\log^{1/2}(1/\delta)\Big{)}.$

###### Proof.

Let $S^{\prime}=\\{z_{1},\ldots,z_{n-1},z_{n}^{\prime}\\}$ and
$\\{\mathbf{w}_{t}^{\prime},\mathbf{v}_{t}^{\prime}\\}$ be the sequence
produced by (4.1) w.r.t. $S^{\prime}$. If $i_{t}\neq n$, it follows from the
$L$-smoothness of $f$ 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}\leq$
$\displaystyle\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}+\eta_{t}\left\|\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z_{i_{t}})\\\
\nabla_{\mathbf{v}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{v}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z_{i_{t}})\end{pmatrix}\right\|_{2}\leq(1+L\eta_{t})\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}.$

If $i_{t}=n$, we have

$\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}\leq$
$\displaystyle\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}+4\eta_{t}G.$

We can combine the above two inequalities together and get

$\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}\leq$
$\displaystyle(1+L\eta_{t})\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}+4G\eta_{t}\mathbb{I}_{[i_{t}=n]}.$

We apply the above inequality recursively from $t=1$ to $T$ and get

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

By the elementary inequality $1+a\leq\exp(a)$ and $\eta_{t}\leq\frac{c}{t}$,
we further derive

$\displaystyle\left\|\begin{pmatrix}\mathbf{w}_{T}-\mathbf{w}_{T}^{\prime}\\\
\mathbf{v}_{T}-\mathbf{v}_{T}^{\prime}\end{pmatrix}\right\|_{2}\leq$
$\displaystyle
4cG\sum_{t=1}^{T}\frac{\mathbb{I}_{[i_{t}=n]}}{t}\prod_{k=t+1}^{T}\exp\Big{(}\frac{cL}{k}\Big{)}=4cG\sum_{t=1}^{T}\frac{\mathbb{I}_{[i_{t}=n]}}{t}\exp\Big{(}\sum_{k=t+1}^{T}\frac{cL}{k}\Big{)}$
$\displaystyle\leq$ $\displaystyle
4cG\sum_{t=1}^{T}\frac{\mathbb{I}_{[i_{t}=n]}}{t}\exp\Big{(}cL\log\Big{(}\frac{T}{t}\Big{)}\Big{)}\leq
4cGT^{cL}\sum_{t=1}^{T}\frac{\mathbb{I}_{[i_{t}=n]}}{t^{cL+1}}.$

By Lemma F.3, for any $\delta>0$ such that
$\log(2/\delta)<\sum_{t=1}^{T}\frac{1}{t^{cL+1}n}$, with probability at least
$1-\delta/2$ we have

$\displaystyle\left\|\begin{pmatrix}\mathbf{w}_{T}-\mathbf{w}_{T}^{\prime}\\\
\mathbf{v}_{T}-\mathbf{v}_{T}^{\prime}\end{pmatrix}\right\|_{2}\leq$
$\displaystyle
4cGT^{cL}\Big{(}\sum_{t=1}^{T}\frac{1}{t^{cL+1}n}+(e-1)\sqrt{\log(1/\delta)\sum_{t=1}^{T}\frac{1}{t^{cL+1}n}}\Big{)}.$
(F.7)

Note that

$\displaystyle\sum_{t=1}^{T}\frac{1}{t^{cL+1}}\leq$ $\displaystyle
1+\int_{t=1}^{T}\frac{\mathrm{d}t}{t^{cL+1}}\leq 1+\frac{1}{cL}.$

Plugging the above bound into Equation (F.7) , we know with probability at
least $1-\delta/2$

$\displaystyle\left\|\begin{pmatrix}\mathbf{w}_{T}-\mathbf{w}_{T}^{\prime}\\\
\mathbf{v}_{T}-\mathbf{v}_{T}^{\prime}\end{pmatrix}\right\|_{2}\leq$
$\displaystyle
4cGT^{cL}\Big{(}\frac{cL+1}{cLn}+(e-1)\sqrt{\frac{(cL+1)\log(1/\delta)}{cLn}}\Big{)}.$

By the Lipschitz continuity of $f$, the above equation implies SGDA is
$\epsilon$-uniformly stable with probability at least $1-\delta/2$ and

$\epsilon=O\Big{(}T^{cL}\sqrt{\log(1/\delta)}n^{-\frac{1}{2}}\Big{)}.$

This together with Part (e) of Theorem 1 implies the following inequality with
probability at least $1-\delta$

$\big{|}F(\mathbf{w},\mathbf{v})-F_{S}(\mathbf{w}_{T},\mathbf{v}_{T})\big{|}=O\Big{(}T^{cL}\log(n)\log^{3/2}(1/\delta)n^{-1/2}+n^{-1/2}\log^{1/2}(1/\delta)\Big{)}.$

The proof is complete. ∎

###  F.3 Proof of Theorem 6

In this section, we prove Theorem 6 on generalization bounds under a
regularity condition on the decay of weak-convexity-weak-concavity parameter
along the optimization process.

###### Proof of Theorem 6.

Let $S=\\{z_{1},\ldots,z_{n}\\}$ and
$S^{\prime}=\\{z_{1}^{\prime},\ldots,z_{n}^{\prime}\\}$ be two neighboring
datasets. Without loss of generality, we assume $z_{i}=z_{i}^{\prime}$ for
$i\in[n-1]$. If $i_{t}\neq n$, then it follows from Assumption 2 that

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

If $i_{t}=n$, then it follows from Assumption 1 that

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

Therefore, we have

$\mathbb{E}_{i_{t}}\left\|\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z^{\prime}_{i_{t}})\\\
\nabla_{\mathbf{v}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{v}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z^{\prime}_{i_{t}})\end{pmatrix}\right\|_{2}^{2}\leq\frac{(n-1)L^{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{8G^{2}}{n}.$
(F.8)

According to (4.1), 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\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+\eta_{t}^{2}\left\|\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z^{\prime}_{i_{t}})\\\
\nabla_{\mathbf{v}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{v}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z^{\prime}_{i_{t}})\end{pmatrix}\right\|_{2}^{2}\\\
-2\eta_{t}\Big{\langle}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix},\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z^{\prime}_{i_{t}})\\\
\nabla_{\mathbf{v}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z^{\prime}_{i_{t}})-\nabla_{\mathbf{v}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\end{pmatrix}\Big{\rangle}.$

Taking a conditional expectation w.r.t. $i_{t}$ gives

$\displaystyle\mathbb{E}_{i_{t}}\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}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+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}+\frac{8G^{2}\eta_{t}^{2}}{n}-2\eta_{t}\mathbb{E}_{i_{t}}\Big{\langle}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix},\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z^{\prime}_{i_{t}})\\\
\nabla_{\mathbf{v}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z^{\prime}_{i_{t}})-\nabla_{\mathbf{v}}f(\mathbf{w}_{t},\mathbf{v}_{t};z_{i_{t}})\end{pmatrix}\Big{\rangle}$
$\displaystyle=\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+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}+\frac{8G^{2}\eta_{t}^{2}}{n}-2\eta_{t}\Big{\langle}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix},\begin{pmatrix}\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\nabla_{\mathbf{w}}F_{S^{\prime}}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})\\\
\nabla_{\mathbf{v}}F_{S^{\prime}}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})-\nabla_{\mathbf{v}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\end{pmatrix}\Big{\rangle},$

where we have used (F.8) in the first step and used the fact

$\mathbb{E}_{i_{t}}\nabla f(\mathbf{w},\mathbf{v},z_{i_{t}})=\nabla
F_{S}(\mathbf{w},\mathbf{v}),\quad\mathbb{E}_{i_{t}}\nabla
f(\mathbf{w},\mathbf{v},z^{\prime}_{i_{t}})=\nabla
F_{S^{\prime}}(\mathbf{w},\mathbf{v})$

in the second step. According to (5.1), we know

$\displaystyle\Big{\langle}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix},\begin{pmatrix}\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\nabla_{\mathbf{w}}F_{S^{\prime}}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})\\\
\nabla_{\mathbf{v}}F_{S^{\prime}}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})-\nabla_{\mathbf{v}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\end{pmatrix}\Big{\rangle}$
$\displaystyle=\Big{\langle}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix},\begin{pmatrix}\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})-\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})\\\
\nabla_{\mathbf{v}}F_{S}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})-\nabla_{\mathbf{v}}F_{S}(\mathbf{w}_{t},\mathbf{v}_{t})\end{pmatrix}\Big{\rangle}+\Big{\langle}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix},\begin{pmatrix}\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})-\nabla_{\mathbf{w}}F_{S^{\prime}}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})\\\
\nabla_{\mathbf{v}}F_{S^{\prime}}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})-\nabla_{\mathbf{v}}F_{S}(\mathbf{w}_{t}^{\prime},\mathbf{v}_{t}^{\prime})\end{pmatrix}\Big{\rangle}$
$\displaystyle\geq-\rho_{t}\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}^{2}+\Big{\langle}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix},\begin{pmatrix}\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})-\nabla_{\mathbf{w}}F_{S^{\prime}}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})\\\
\nabla_{\mathbf{v}}F_{S^{\prime}}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})-\nabla_{\mathbf{v}}F_{S}(\mathbf{w}_{t}^{\prime},\mathbf{v}_{t}^{\prime})\end{pmatrix}\Big{\rangle}.$

It follows from Assumption 1 that

$\displaystyle\Big{\langle}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix},\begin{pmatrix}\nabla_{\mathbf{w}}F_{S}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})-\nabla_{\mathbf{w}}F_{S^{\prime}}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})\\\
\nabla_{\mathbf{v}}F_{S^{\prime}}(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t})-\nabla_{\mathbf{v}}F_{S}(\mathbf{w}_{t}^{\prime},\mathbf{v}_{t}^{\prime})\end{pmatrix}\Big{\rangle}=\frac{1}{n}\Big{\langle}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix},\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z_{n})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z_{n}^{\prime})\\\
\nabla_{\mathbf{v}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z_{n}^{\prime})-\nabla_{\mathbf{v}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}_{t}^{\prime};z_{n})\end{pmatrix}\Big{\rangle}$
$\displaystyle\geq-\frac{1}{n}\Big{\|}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\Big{\|}_{2}\Big{\|}\begin{pmatrix}\nabla_{\mathbf{w}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z_{n})-\nabla_{\mathbf{w}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z_{n}^{\prime})\\\
\nabla_{\mathbf{v}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}^{\prime}_{t};z_{n}^{\prime})-\nabla_{\mathbf{v}}f(\mathbf{w}_{t}^{\prime},\mathbf{v}_{t}^{\prime};z_{n})\end{pmatrix}\Big{\|}_{2}\geq-\frac{2\sqrt{2}G}{n}\Big{\|}\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\Big{\|}_{2}.$

We can combine the above three inequalities together and derive

$\displaystyle\mathbb{E}_{i_{t}}\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\big{(}1+2\rho_{t}\eta_{t}+L^{2}\eta_{t}^{2}\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\eta_{t}^{2}G^{2}}{n}+\frac{4\sqrt{2}G\eta_{t}}{n}\left\|\begin{pmatrix}\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\\\
\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\end{pmatrix}\right\|_{2}$
$\displaystyle\leq\big{(}1+2\rho_{t}\eta_{t}+L^{2}\eta_{t}^{2}\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\eta_{t}^{2}G^{2}}{n}+\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}+\frac{8G^{2}}{n^{2}}.$

Applying the above inequality recursively, we get

$\mathbb{E}_{A}\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\frac{8G^{2}}{n}\sum_{j=1}^{t}\Big{(}\eta_{t}^{2}+\frac{1}{n}\Big{)}\prod_{k=j+1}^{t}\big{(}1+2\rho_{k}\eta_{k}+L^{2}\eta_{k}^{2}+\eta_{k}^{2}\big{)}.$

By the elementary inequality $1+a\leq\exp(a)$ we know

$\mathbb{E}_{A}\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\frac{8G^{2}}{n}\sum_{j=1}^{t}\Big{(}\eta_{t}^{2}+\frac{1}{n}\Big{)}\exp\Big{(}\sum_{k=j+1}^{t}\big{(}2\rho_{k}\eta_{k}+(L^{2}+1)\eta_{k}^{2}\big{)}\Big{)}.$

It then follows from the Jensen’s inequality that

$\mathbb{E}_{A}\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}\leq\frac{2\sqrt{2}G}{\sqrt{n}}\left(\sum_{j=1}^{t}\Big{(}\eta_{t}^{2}+\frac{1}{n}\Big{)}\exp\Big{(}\sum_{k=j+1}^{t}\big{(}2\rho_{k}\eta_{k}+(L^{2}+1)\eta_{k}^{2}\big{)}\Big{)}\right)^{\frac{1}{2}}.$

The stated bound then follows from Part (a) of Theorem 1 and Assumption 1. The
proof is complete. ∎

##  Appendix G Stability and Generalization Bounds of AGDA on Nonconvex-
Nonconcave Objectives

In this section, we give the proof on the stability and generalization bounds
of AGDA for nonconvex-nonconcave functions. The next lemma is similar to Lemma
F.1, which shows AGDA typically runs several iterations before encountering
the different example between $S$ and $S^{\prime}$.

######  Lemma G.1.

Assume $|f(\cdot,\cdot,z)|\leq 1$ for any $z$ and let Assumption 1 hold. 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 (5.2) w.r.t. $S$ and $S^{\prime}$, respectively. Denote

$\displaystyle\Delta_{t}=\|\mathbf{w}_{t}-\mathbf{w}^{\prime}_{t}\|_{2}+\|\mathbf{v}_{t}-\mathbf{v}^{\prime}_{t}\|_{2}.$
(G.1)

Then for any $t_{0}\in\mathbb{N}$ and any
$\mathbf{w}^{\prime},\mathbf{v}^{\prime}$ we have

$\displaystyle\mathbb{E}[f(\mathbf{w}_{T},\mathbf{v}^{\prime};z)-f(\mathbf{w}^{\prime}_{T},\mathbf{v}^{\prime};z)+f(\mathbf{w}^{\prime},\mathbf{v}_{T};z)-f(\mathbf{w}^{\prime},\mathbf{v}^{\prime}_{T};z)]\leq\frac{8t_{0}}{n}+G\mathbb{E}[\Delta_{T}|\Delta_{t_{0}}=0].$

###### Proof.

Let $\mathcal{E}$ denote the event that $\Delta_{t_{0}}=0$. Then we have

$\displaystyle\mathbb{E}[f(\mathbf{w}_{T},\mathbf{v}^{\prime};z)-f(\mathbf{w}^{\prime}_{T},\mathbf{v}^{\prime};z)+f(\mathbf{w}^{\prime},\mathbf{v}_{T};z)-f(\mathbf{w}^{\prime},\mathbf{v}^{\prime}_{T};z)]$
$\displaystyle=$
$\displaystyle\mathbb{P}[\mathcal{E}]\mathbb{E}[f(\mathbf{w}_{T},\mathbf{v}^{\prime};z)-f(\mathbf{w}^{\prime}_{T},\mathbf{v}^{\prime};z)+f(\mathbf{w}^{\prime},\mathbf{v}_{T};z)-f(\mathbf{w}^{\prime},\mathbf{v}^{\prime}_{T};z)|\mathcal{E}]$
$\displaystyle+\mathbb{P}[\mathcal{E}^{c}]\mathbb{E}[f(\mathbf{w}_{T},\mathbf{v}^{\prime};z)-f(\mathbf{w}^{\prime}_{T},\mathbf{v}^{\prime};z)+f(\mathbf{w}^{\prime},\mathbf{v}_{T};z)-f(\mathbf{w}^{\prime},\mathbf{v}^{\prime}_{T};z)|\mathcal{E}^{c}]$
$\displaystyle\leq$ $\displaystyle
G\mathbb{E}[\Delta_{T}|\mathcal{E}]+4\mathbb{P}[\mathcal{E}^{c}],$ (G.2)

where we have used (F.2) and the assumption $|f(\cdot,\cdot,z)|\leq 1$. Using
the union bound on the outcome $i_{t}=n$ and $j_{t}=n$ we obtain that

$\displaystyle\mathbb{P}[\mathcal{E}^{c}]\leq\sum_{t=1}^{t_{0}}\big{(}\mathbb{P}[i_{t}=n]+\mathbb{P}[j_{t}=n]\big{)}=\frac{2t_{0}}{n}.$

The proof is complete by combining the above two inequalities together. ∎

###### Proof of Theorem 7.

Since $z_{i_{t}}$ and $z_{j_{t}}$ are i.i.d, we can analyze the update of
$\mathbf{w}$ and $\mathbf{v}$ separately. 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 Assumption 2 that

$\displaystyle\|\mathbf{w}_{t+1}-\mathbf{w}^{\prime}_{t+1}\|_{2}$
$\displaystyle\leq$
$\displaystyle\|\mathbf{w}_{t}-\eta_{\mathbf{w},t}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t},z_{i_{t}})-\mathbf{w}^{\prime}_{t}+\eta_{\mathbf{w},t}\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime}_{t},\mathbf{v}^{\prime}_{t},z_{i_{t}})\|_{2}$
$\displaystyle\leq$
$\displaystyle\|\mathbf{w}_{t}-\eta_{\mathbf{w},t}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t},z_{i_{t}})-\mathbf{w}^{\prime}_{t}+\eta_{\mathbf{w},t}\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime}_{t},\mathbf{v}_{t},z_{i_{t}})\|_{2}+\|\eta_{\mathbf{w},t}\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime}_{t},\mathbf{v}_{t},z_{i_{t}})-\eta_{\mathbf{w},t}\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime}_{t},\mathbf{v}^{\prime}_{t},z_{i_{t}})\|_{2}$
$\displaystyle\leq$
$\displaystyle(1+L\eta_{\mathbf{w},t})\|\mathbf{w}_{t}-\mathbf{w}^{\prime}_{t}\|_{2}+L\eta_{\mathbf{w},t}\|\mathbf{v}_{t}-\mathbf{v}^{\prime}_{t}\|_{2}.$

If $i_{t}=n$, then it follows from Assumption 1 that

$\displaystyle\|\mathbf{w}_{t+1}-\mathbf{w}^{\prime}_{t+1}\|_{2}\leq$
$\displaystyle\|\mathbf{w}_{t}-\eta_{\mathbf{w},t}\nabla_{\mathbf{w}}f(\mathbf{w}_{t},\mathbf{v}_{t},z_{i_{t}})-\mathbf{w}^{\prime}_{t}+\eta_{\mathbf{w},t}\nabla_{\mathbf{w}}f(\mathbf{w}^{\prime}_{t},\mathbf{v}^{\prime}_{t},z_{i_{t}})\|_{2}$
$\displaystyle\leq$
$\displaystyle\|\mathbf{w}_{t}-\mathbf{w}^{\prime}_{t}\|_{2}+2G\eta_{\mathbf{w},t}.$

According to the distribution of $i_{t}$, we have

$\displaystyle\mathbb{E}_{A}[\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\|_{2}]\leq$
$\displaystyle\frac{n-1}{n}\mathbb{E}_{A}\Big{[}(1+\eta_{\mathbf{w},t}L)\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\|_{2}+L\eta_{\mathbf{w},t}\|\mathbf{v}_{t}-\mathbf{v}^{\prime}_{t}\|_{2}\Big{]}+\frac{1}{n}(\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\|_{2}+2\eta_{\mathbf{w},t}G)$
$\displaystyle\leq$
$\displaystyle(1+\eta_{\mathbf{w},t}L)\mathbb{E}_{A}[\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\|_{2}]+L\eta_{\mathbf{w},t}\mathbb{E}_{A}\big{[}\|\mathbf{v}_{t}-\mathbf{v}^{\prime}_{t}\|_{2}\big{]}+\frac{2\eta_{\mathbf{w},t}G}{n}.$
(G.3)

Similarly, for $\mathbf{v}$ we also have

$\displaystyle\mathbb{E}_{A}[\|\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\|_{2}]\leq$
$\displaystyle(1+\eta_{\mathbf{v},t}L)\mathbb{E}_{A}[\|\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\|_{2}]+L\eta_{\mathbf{v},t}\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t}-\mathbf{w}^{\prime}_{t}\|_{2}\big{]}+\frac{2\eta_{\mathbf{v},t}G}{n}.$
(G.4)

Combining (G.3) and (G.4) we have

$\displaystyle\mathbb{E}_{A}[\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\|_{2}+\|\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\|_{2}]\leq$
$\displaystyle(1+(\eta_{\mathbf{w},t}+\eta_{\mathbf{v},t})L)\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t}-\mathbf{w}_{t}^{\prime}\|_{2}+\|\mathbf{v}_{t}-\mathbf{v}_{t}^{\prime}\|_{2}\big{]}+\frac{2(\eta_{\mathbf{w},t}+\eta_{\mathbf{v},t})G}{n}.$

Recalling the event $\mathcal{E}$ that $\Delta_{t_{0}}=0$, we apply the above
equation recursively from $t=t_{0}+1$ to $T$, then

$\displaystyle\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\|_{2}+\|\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\|_{2}\big{|}\Delta_{t_{0}}=0\big{]}\leq$
$\displaystyle\frac{2G}{n}\sum_{t=t_{0}+1}^{T}(\eta_{\mathbf{w},t}+\eta_{\mathbf{v},t})\prod_{k=t+1}^{T}(1+(\eta_{\mathbf{w},k}+\eta_{\mathbf{v},k})L).$

By the elementary inequality $1+x\leq\exp(x)$ and
$\eta_{\mathbf{w},t}+\eta_{\mathbf{v},t}\leq\frac{c}{t}$, we have

$\displaystyle\mathbb{E}_{A}\big{[}\|\mathbf{w}_{t+1}-\mathbf{w}_{t+1}^{\prime}\|_{2}+\|\mathbf{v}_{t+1}-\mathbf{v}_{t+1}^{\prime}\|_{2}\big{|}\Delta_{t_{0}}=0\big{]}$
$\displaystyle\leq$
$\displaystyle\frac{2cG}{n}\sum_{t=t_{0}+1}^{T}\frac{1}{t}\prod_{k=t+1}^{T}\exp\Big{(}\frac{cL}{k}\Big{)}=\frac{2cG}{n}\sum_{t=t_{0}+1}^{T}\frac{1}{t}\exp\Big{(}\sum_{k=t+1}^{T}\frac{cL}{k}\Big{)}$
$\displaystyle\leq$
$\displaystyle\frac{2cG}{n}\sum_{t=t_{0}+1}^{T}\frac{1}{t}\exp\Big{(}cL\log\Big{(}\frac{T}{t}\Big{)}\Big{)}\leq\frac{2cGT^{cL}}{n}\sum_{t=t_{0}+1}^{T}\frac{1}{t^{cL+1}}\leq\frac{2G}{Ln}\Big{(}\frac{T}{t_{0}}\Big{)}^{cL}.$

By Lemma G.1 we have

$\displaystyle\mathbb{E}[f(\mathbf{w}_{T},\mathbf{v}^{\prime};z)-f(\mathbf{w}^{\prime}_{T},\mathbf{v}^{\prime};z)+f(\mathbf{w}^{\prime},\mathbf{v}_{T};z)-f(\mathbf{w}^{\prime},\mathbf{v}^{\prime}_{T};z)]\leq$
$\displaystyle\frac{8t_{0}}{n}+\frac{2G^{2}}{Ln}\Big{(}\frac{T}{t_{0}}\Big{)}^{cL}.$
(G.5)

The right hand side of the above inequality is approximately minimized when

$\displaystyle
t_{0}=\Big{(}\frac{G^{2}}{4L}\Big{)}^{\frac{1}{cL+1}}T^{\frac{cL}{cL+1}}.$

Plugging it into Eq. (G.5) we have (for simplicity we assume the above $t_{0}$
is an integer)

$\displaystyle\mathbb{E}[f(\mathbf{w}_{T},\mathbf{v}^{\prime};z)-f(\mathbf{w}^{\prime}_{T},\mathbf{v}^{\prime};z)+f(\mathbf{w}^{\prime},\mathbf{v}_{T};z)-f(\mathbf{w}^{\prime},\mathbf{v}^{\prime}_{T};z)]\leq$
$\displaystyle
16\Big{(}\frac{G^{2}}{4L}\Big{)}^{\frac{1}{cL+1}}n^{-1}T^{\frac{cL}{cL+1}}.$

Since the above bound holds for all $z,S,S^{\prime}$ and
$\mathbf{w}^{\prime},\mathbf{v}^{\prime}$, we immediately get the same upper
bound on the weak stability. Finally the theorem holds by calling Theorem 1,
Part (a). ∎

We require an assumption on the existence of saddle point to address the
optimization error of AGDA (Yang et al., 2020).

######  Assumption 4 (Existence of Saddle Point).

Assume for any $S$, $F_{S}$ has at least one saddle point. Assume for any
$\mathbf{v}$, $\min_{\mathbf{w}}F_{S}(\mathbf{w},\mathbf{v})$ has a nonempty
solution set and a finite optimal value. Assume for any $\mathbf{w}$,
$\max_{\mathbf{v}}F_{S}(\mathbf{w},\mathbf{v})$ has a nonempty solution set
and a finite optimal value.

The following lemma establishes the generalization bound for the empirical
maximizer of a strongly concave objective. It is a direct extension of the
stability analysis in Shalev-Shwartz et al. (2010) for strongly convex
objectives.

######  Lemma G.2.

Assume that for any $\mathbf{w}$ and $S$, the function $\mathbf{v}\mapsto
F_{S}(\mathbf{w},\mathbf{v})$ is $\rho$-strongly-concave. Suppose for any
$\mathbf{w}$, $\mathbf{v},\mathbf{v}^{\prime}$ and for any $z$ we have

$\big{|}f(\mathbf{w},\mathbf{v};z)-f(\mathbf{w},\mathbf{v}^{\prime};z)\big{|}\leq
G\|\mathbf{v}-\mathbf{v}^{\prime}\|_{2}.$ (G.6)

Fix any $\mathbf{w}$. Denote
$\hat{\mathbf{v}}^{*}_{S}=\arg\max_{\mathbf{v}\in\mathcal{V}}F_{S}(\mathbf{w},\mathbf{v})$.
Then

$\displaystyle\mathbb{E}[F_{S}(\mathbf{w},\hat{\mathbf{v}}^{*}_{S})-F(\mathbf{w},\hat{\mathbf{v}}^{*}_{S})]\leq\frac{4G^{2}}{\rho
n}.$

###### Proof.

Let $S^{\prime}=\\{z^{\prime}_{1},\ldots,z^{\prime}_{n}\\}$ be drawn
independently from $\rho$. For any $i\in[n]$, define
$S^{(i)}=\\{z_{1},\ldots,z_{i-1},z_{i}^{\prime},z_{i+1},\ldots,z_{n}\\}$.
Denote
$\hat{\mathbf{v}}^{*}_{S^{(i)}}=\arg\max_{\mathbf{v}\in\mathcal{V}}F_{S^{(i)}}(\mathbf{w},\mathbf{v})$.
Then

$\displaystyle
F_{S}(\mathbf{w},\hat{\mathbf{v}}^{*}_{S})-F_{S}(\mathbf{w},\hat{\mathbf{v}}^{*}_{S^{(i)}})=$
$\displaystyle\frac{1}{n}\sum_{j\neq
i}\Big{(}f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S};z_{j})-f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S^{(i)}};z_{j})\Big{)}+\frac{1}{n}\Big{(}f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S};z_{i})-f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S^{(i)}};z_{i})\Big{)}$
$\displaystyle=$
$\displaystyle\frac{1}{n}\Big{(}f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S^{(i)}};z^{\prime}_{i})-f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S};z^{\prime}_{i})\Big{)}+\frac{1}{n}\Big{(}f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S};z_{i})-f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S^{(i)}};z_{i})\Big{)}$
$\displaystyle+F_{S^{(i)}}(\mathbf{w},\hat{\mathbf{v}}^{*}_{S})-F_{S^{(i)}}(\mathbf{w},\hat{\mathbf{v}}^{*}_{S^{(i)}})$
$\displaystyle\leq$
$\displaystyle\frac{1}{n}\Big{(}f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S^{(i)}};z^{\prime}_{i})-f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S};z^{\prime}_{i})\Big{)}+\frac{1}{n}\Big{(}f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S};z_{i})-f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S^{(i)}};z_{i})\Big{)}$
$\displaystyle\leq$
$\displaystyle\frac{2G}{n}\big{\|}\hat{\mathbf{v}}^{*}_{S}-\hat{\mathbf{v}}^{*}_{S^{(i)}}\big{\|}_{2},$
(G.7)

where the first inequality follows from the fact that
$\hat{\mathbf{v}}^{*}_{S^{(i)}}$ is the maximizer of
$F_{S^{(i)}}(\mathbf{w},\cdot)$ and the second inequality follows from (G.6).
Since $F_{S}$ is strongly-concave and $\hat{\mathbf{v}}^{*}_{S}$ maximizes
$F_{S}(\mathbf{w},\cdot)$, we know

$\displaystyle\frac{\rho}{2}\big{\|}\hat{\mathbf{v}}^{*}_{S}-\hat{\mathbf{v}}^{*}_{S^{(i)}}\big{\|}_{2}^{2}\leq
F_{S}(\mathbf{w},\hat{\mathbf{v}}^{*}_{S})-F_{S}(\mathbf{w},\hat{\mathbf{v}}^{*}_{S^{(i)}}).$

Combining it with (G) we get
$\big{\|}\hat{\mathbf{v}}^{*}_{S}-\hat{\mathbf{v}}^{*}_{S^{(i)}}\big{\|}_{2}\leq
4G/(\rho n)$. By (G.6), the following inequality holds for any $z$

$\displaystyle\big{|}f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S};z)-f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S^{(i)}};z)\big{|}\leq\frac{4G^{2}}{\rho
n}.$

Since $z_{i}$ and $z^{\prime}_{i}$ are i.i.d., we have

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

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

$\displaystyle\mathbb{E}\big{[}F_{S}(\mathbf{w},\hat{\mathbf{v}}^{*}_{S})-F(\mathbf{w},\hat{\mathbf{v}}^{*}_{S})\big{]}=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\big{[}f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S};z_{i})-f(\mathbf{w},\hat{\mathbf{v}}^{*}_{S^{(i)}};z_{i})\big{]}\leq\frac{4G^{2}}{\rho
n}.$

The proof is complete. ∎

######  Corollary G.3.

Let $\beta_{1},\rho>0$. Let Assumptions 1, 2, 3 with
$\beta_{1}(S)\geq\beta_{1},\beta_{2}(S)\geq\rho$ and 4 hold. Assume for any
$\mathbf{w}$ and any $S$, the functions $\mathbf{v}\mapsto
F(\mathbf{w},\mathbf{v})$ and $\mathbf{v}\mapsto F_{S}(\mathbf{w},\mathbf{v})$
are $\rho$-strongly concave. Let $\\{\mathbf{w}_{t},\mathbf{v}_{t}\\}$ be the
sequence produced by (5.2) with $\eta_{\mathbf{w},t}\asymp 1/({\beta_{1}t})$
and $\eta_{\mathbf{v},t}\asymp 1/{(\beta_{1}\rho^{2}t)}$. Then for
$T\asymp\big{(}\frac{n}{\beta_{1}^{2}\rho^{3}}\big{)}^{\frac{cL+1}{2cL+1}}$,
we have

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

where $c\asymp 1/(\beta_{1}\rho^{2})$.

###### Proof.

We have the error decomposition

$R(\mathbf{w}_{T})-R(\mathbf{w}^{*})=\big{(}R(\mathbf{w}_{T})-R_{S}(\mathbf{w}_{T})\big{)}+\big{(}R_{S}(\mathbf{w}_{T})-R_{S}(\mathbf{w}^{*})\big{)}+\big{(}R_{S}(\mathbf{w}^{*})-R(\mathbf{w}^{*})\big{)}.$
(G.8)

First we consider the term $R(\mathbf{w}_{T})-R_{S}(\mathbf{w}_{T})$.
Analogous to the proof of Theorem 7 (i.e., the only difference is to replace
the conditional expectation of function values in (G.2) with the conditional
expectation of
$\mathbb{E}[\|\mathbf{w}_{T}-\mathbf{w}_{T}^{\prime}\|_{2}+\|\mathbf{v}_{T}-\mathbf{v}_{T}^{\prime}\|_{2}]$),
one can show that AGDA is $O\big{(}n^{-1}T^{\frac{cL}{cL+1}}\big{)}$-argument
stable (note the step sizes satisfy
$\eta_{\mathbf{w},t}+\eta_{\mathbf{v},t}\leq c/t$). This together with Part
(b) of Theorem 1 implies that

$\mathbb{E}\big{[}R(\mathbf{w}_{T})-R_{S}(\mathbf{w}_{T})\big{]}=O\big{(}(\rho
n)^{-1}T^{\frac{cL}{cL+1}}\big{)}.$ (G.9)

For the term $R_{S}(\mathbf{w}_{T})-R_{S}(\mathbf{w}^{*})$, the optimization
error bounds in Yang et al. (2020) show that

$\mathbb{E}\big{[}R_{S}(\mathbf{w}_{T})-R_{S}(\mathbf{w}^{*})\big{]}=O\Big{(}\frac{1}{\beta_{1}^{2}\rho^{4}T}\Big{)}.$
(G.10)

Finally, for the term $R_{S}(\mathbf{w}^{*})-R(\mathbf{w}^{*})$, we further
decompose it as

$\mathbb{E}\big{[}R_{S}(\mathbf{w}^{*})-R(\mathbf{w}^{*})\big{]}=\mathbb{E}\big{[}F_{S}(\mathbf{w}^{*},\hat{\mathbf{v}}^{*}_{S})-F(\mathbf{w}^{*},\mathbf{v}^{*})\big{]}=\mathbb{E}\big{[}F_{S}(\mathbf{w}^{*},\hat{\mathbf{v}}^{*}_{S})-F(\mathbf{w}^{*},\hat{\mathbf{v}}^{*}_{S})\big{]}+\mathbb{E}\big{[}F(\mathbf{w}^{*},\hat{\mathbf{v}}^{*}_{S})-F(\mathbf{w}^{*},\mathbf{v}^{*})\big{]},$

where
$\hat{\mathbf{v}}^{*}_{S}=\arg\max_{\mathbf{v}}F_{S}(\mathbf{w}^{*},\mathbf{v})$.
The second term
$\mathbb{E}\big{[}F(\mathbf{w}^{*},\hat{\mathbf{v}}^{*}_{S})-F(\mathbf{w}^{*},\mathbf{v}^{*})\big{]}\leq
0$ since $(\mathbf{w}^{*},\mathbf{v}^{*})$ is a saddle point of $F$. Therefore
by Lemma G.2 we have

$\mathbb{E}\big{[}R_{S}(\mathbf{w}^{*})-R(\mathbf{w}^{*})\big{]}\leq\mathbb{E}\big{[}F_{S}(\mathbf{w}^{*},\hat{\mathbf{v}}^{*}_{S})-F(\mathbf{w}^{*},\hat{\mathbf{v}}^{*}_{S})\big{]}=O\Big{(}\frac{1}{\rho
n}\Big{)}.$

We can plug the above inequality, (G.9), (G.10) into (G.8), and get

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

We can choose
$T\asymp\big{(}\frac{n}{\beta_{1}^{2}\rho^{3}}\big{)}^{\frac{cL+1}{2cL+1}}$ to
get the stated excess primal population risk bounds. The proof is complete. ∎

##  Appendix H Proof of Theorem 9

To prove Theorem 9, we first introduce a lemma on relating the difference of
function values to gradients.

######  Lemma H.1.

Let Assumption 3 hold. For any $\mathbf{u}=(\mathbf{w},\mathbf{v})$ and any
stationary point $\mathbf{u}_{(S)}=(\mathbf{w}_{(S)},\mathbf{v}_{(S)})$ of
$F_{S}$, we have

$-\frac{\|\nabla_{\mathbf{v}}F_{S}(\mathbf{w},\mathbf{v})\|_{2}^{2}}{2\beta_{2}(S)}\leq
F_{S}(\mathbf{u})-F_{S}(\mathbf{u}_{(S)})\leq\frac{\|\nabla_{\mathbf{w}}F_{S}(\mathbf{w},\mathbf{v})\|_{2}^{2}}{2\beta_{1}(S)}.$

###### Proof.

Since $\mathbf{u}_{(S)}$ is a stationary point, it is also a saddle point
under the PL condition (Yang et al., 2020) which means that

$F_{S}(\mathbf{w}_{(S)},\mathbf{v}^{\prime})\leq
F_{S}(\mathbf{w}_{(S)},\mathbf{v}_{(S)})\leq
F_{S}(\mathbf{w}^{\prime},\mathbf{v}_{(S)}),\quad\forall\mathbf{w}^{\prime}\in\mathcal{W},\mathbf{v}^{\prime}\in\mathcal{V}.$

It then follows that

$\displaystyle F_{S}(\mathbf{u})-F_{S}(\mathbf{u}_{(S)})$
$\displaystyle=F_{S}(\mathbf{w},\mathbf{v})-F_{S}(\mathbf{w}_{(S)},\mathbf{v})+F_{S}(\mathbf{w}_{(S)},\mathbf{v})-F_{S}(\mathbf{w}_{(S)},\mathbf{v}_{(S)})$
$\displaystyle\leq
F_{S}(\mathbf{w},\mathbf{v})-F_{S}(\mathbf{w}_{(S)},\mathbf{v})\leq
F_{S}(\mathbf{w},\mathbf{v})-\inf_{\mathbf{w}^{\prime}\in\mathcal{W}}F_{S}(\mathbf{w}^{\prime},\mathbf{v})\leq\frac{1}{2\beta_{1}(S)}\|\nabla_{\mathbf{w}}F_{S}(\mathbf{w},\mathbf{v})\|_{2}^{2},$

where in the last inequality we have used Assumption 3. In a similar way, we
know

$\displaystyle F_{S}(\mathbf{u})-F_{S}(\mathbf{u}_{(S)})$
$\displaystyle=F_{S}(\mathbf{w},\mathbf{v})-F_{S}(\mathbf{w},\mathbf{v}_{(S)})+F_{S}(\mathbf{w},\mathbf{v}_{(S)})-F_{S}(\mathbf{w}_{(S)},\mathbf{v}_{(S)})$
$\displaystyle\geq
F_{S}(\mathbf{w},\mathbf{v})-F_{S}(\mathbf{w},\mathbf{v}_{(S)})\geq
F_{S}(\mathbf{w},\mathbf{v})-\sup_{\mathbf{v}^{\prime}}F_{S}(\mathbf{w},\mathbf{v}^{\prime})\geq-\frac{1}{2\beta_{2}(S)}\|\nabla_{\mathbf{v}}F_{S}(\mathbf{w},\mathbf{v})\|_{2}^{2}.$

The proof is complete. ∎

###### Proof of Theorem 9.

Let $S^{\prime}=\\{z^{\prime}_{1},\ldots,z^{\prime}_{n}\\}$ be drawn
independently from $\rho$. For any $i\in[n]$, define
$S^{(i)}=\\{z_{1},\ldots,z_{i-1},z_{i}^{\prime},z_{i+1},\ldots,z_{n}\\}$. 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}$. For each $i\in[n]$, we denote
$\mathbf{u}_{i}=(A_{\mathbf{w}}(S^{(i)}),A_{\mathbf{v}}(S^{(i)}))$ and
$\mathbf{u}_{i}^{(i)}$ the projection of $\mathbf{u}_{i}$ onto the set of
stationary points of $F_{S^{(i)}}$. Then $\nabla
F_{S^{(i)}}(\mathbf{u}_{i}^{(i)})=0$.

We decompose $f(\mathbf{u}_{i};z_{i})-f(\mathbf{u}_{S};z_{i})$ as follows

$f(\mathbf{u}_{i};z_{i})-f(\mathbf{u}_{S};z_{i})=\big{(}f(\mathbf{u}_{i};z_{i})-f(\mathbf{u}_{i}^{(i)};z_{i})\big{)}+\big{(}f(\mathbf{u}_{i}^{(i)};z_{i})-f(\mathbf{u}_{S}^{(S)};z_{i})\big{)}+\big{(}f(\mathbf{u}_{S}^{(S)};z_{i})-f(\mathbf{u}_{S};z_{i})\big{)}.$
(H.1)

We now address the above three terms separately.

We first address
$f(\mathbf{u}_{i}^{(i)};z_{i})-f(\mathbf{u}_{S}^{(S)};z_{i})$. According to
the definition of $F_{S},S,S^{(i)}$, we know

$f(\mathbf{u}_{i}^{(i)};z_{i})=nF_{S}(\mathbf{u}_{i}^{(i)})-nF_{S^{(i)}}(\mathbf{u}_{i}^{(i)})+f(\mathbf{u}_{i}^{(i)};z^{\prime}_{i}).$

Since $z_{i}$ and $z^{\prime}_{i}$ follow from the same distribution, we know
$\mathbb{E}[f(\mathbf{u}_{i}^{(i)};z^{\prime}_{i})]=\mathbb{E}[f(\mathbf{u}_{S}^{(S)};z_{i})]$
and further get

$\mathbb{E}\big{[}f(\mathbf{u}_{i}^{(i)};z_{i})\big{]}=n\mathbb{E}\big{[}F_{S}(\mathbf{u}_{i}^{(i)})\big{]}-n\mathbb{E}\big{[}F_{S^{(i)}}(\mathbf{u}_{i}^{(i)})\big{]}+\mathbb{E}\big{[}f(\mathbf{u}_{S}^{(S)};z_{i})\big{]}.$

It then follows that

$\mathbb{E}\big{[}f(\mathbf{u}_{i}^{(i)};z_{i})-f(\mathbf{u}_{S}^{(S)};z_{i})\big{]}=n\mathbb{E}\big{[}F_{S}(\mathbf{u}_{i}^{(i)})-F_{S^{(i)}}(\mathbf{u}_{i}^{(i)})\big{]}=n\mathbb{E}\Big{[}F_{S}(\mathbf{u}_{i}^{(i)})-F_{S}(\mathbf{u}_{S}^{(S)})\Big{]},$
(H.2)

where we have used the following identity due to the symmetry between $z_{i}$
and $z^{\prime}_{i}$:
$\mathbb{E}[F_{S^{(i)}}(\mathbf{u}_{i}^{(i)})]=\mathbb{E}\big{[}F_{S}(\mathbf{u}_{S}^{(S)})\big{]}.$
By the PL condition of $F_{S}$, it then follows from (H.2) and Lemma H.1 that

$\mathbb{E}\big{[}f(\mathbf{u}^{(i)};z_{i})-f(\mathbf{u}_{S}^{(S)};z_{i})\big{]}\leq\frac{n}{2}\mathbb{E}\big{[}\frac{1}{\beta_{1}(S)}\|\nabla_{\mathbf{w}}F_{S}(\mathbf{u}_{i}^{(i)})\|_{2}^{2}\big{]}.$
(H.3)

According to the definition of $\mathbf{u}_{i}^{(i)}$ we know
$\nabla_{\mathbf{w}}F_{S^{(i)}}(\mathbf{u}_{i}^{(i)})=0$ and therefore
($(a+b)^{2}\leq 2a^{2}+2b^{2}$)

$\displaystyle\|\nabla_{\mathbf{w}}F_{S}(\mathbf{u}_{i}^{(i)})\|_{2}^{2}$
$\displaystyle=\Big{\|}\nabla_{\mathbf{w}}F_{S^{(i)}}(\mathbf{u}_{i}^{(i)})-\frac{1}{n}\nabla_{\mathbf{w}}f(\mathbf{u}_{i}^{(i)};z^{\prime}_{i})+\frac{1}{n}\nabla_{\mathbf{w}}f(\mathbf{u}_{i}^{(i)};z_{i})\Big{\|}_{2}^{2}$
$\displaystyle\leq\frac{2}{n^{2}}\|\nabla_{\mathbf{w}}f(\mathbf{u}_{i}^{(i)};z^{\prime}_{i})\|_{2}^{2}+\frac{2}{n^{2}}\|\nabla_{\mathbf{w}}f(\mathbf{u}_{i}^{(i)};z_{i})\|_{2}^{2}\leq\frac{4G^{2}}{n^{2}},$
(H.4)

where we have used Assumption 1. This together with (H.3) gives

$\mathbb{E}\big{[}f(\mathbf{u}^{(i)};z_{i})-f(\mathbf{u}_{S}^{(S)};z_{i})\big{]}\leq\frac{2G^{2}}{n}\mathbb{E}\Big{[}\frac{1}{\beta_{1}(S)}\Big{]}.$
(H.5)

We then address $f(\mathbf{u}_{i};z_{i})-f(\mathbf{u}_{i}^{(i)};z_{i})$. Since
$\mathbf{u}_{i}$ and $\mathbf{u}_{i}^{(i)}$ are independent of $z_{i}$, we
know

$\mathbb{E}\big{[}f(\mathbf{u}_{i};z_{i})-f(\mathbf{u}_{i}^{(i)};z_{i})\big{]}=\mathbb{E}\big{[}F(\mathbf{u}_{i})-F(\mathbf{u}_{i}^{(i)})\big{]}=\mathbb{E}\big{[}F(\mathbf{u}_{S})-F(\mathbf{u}_{S}^{(S)})\big{]},$
(H.6)

where we have used the symmetry between $z_{i}$ and $z^{\prime}_{i}$.

Finally, we address $f(\mathbf{u}_{S}^{(S)};z_{i})-f(\mathbf{u}_{S};z_{i})$.
By the definition of $\mathbf{u}_{S}^{(S)}$ we know

$\sum_{i=1}^{n}\big{(}f(\mathbf{u}_{S}^{(S)};z_{i})-f(\mathbf{u}_{S};z_{i})\big{)}=n\big{(}F_{S}(\mathbf{u}_{S}^{(S)})-F_{S}(\mathbf{u}_{S})\big{)}.$
(H.7)

Plugging (H.5), (H.6) and the above inequality back into (H.1), we derive

$\sum_{i=1}^{n}\mathbb{E}\big{[}f(\mathbf{u}_{i};z_{i})-f(\mathbf{u}_{S};z_{i})\big{]}\leq\mathbb{E}\Big{[}\frac{2G^{2}}{\beta_{1}(S)}\Big{]}+n\mathbb{E}\big{[}F(\mathbf{u}_{S})-F(\mathbf{u}_{S}^{(S)})\big{]}+n\mathbb{E}\big{[}F_{S}(\mathbf{u}_{S}^{(S)})-F_{S}(\mathbf{u}_{S})\big{]}.$

Since $z_{i}$ and $z^{\prime}_{i}$ are drawn from the same distribution, we
know

$\displaystyle\mathbb{E}\big{[}F(\mathbf{u}_{S})-F_{S}(\mathbf{u}_{S})\big{]}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\big{[}F(\mathbf{u}_{i})-F_{S}(\mathbf{u}_{S})\big{]}=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\big{[}f(\mathbf{u}_{i};z_{i})-f(\mathbf{u}_{S};z_{i})\big{]}$
$\displaystyle\leq\frac{2G^{2}}{n}\mathbb{E}\Big{[}\frac{1}{\beta_{1}(S)}\Big{]}+\mathbb{E}\big{[}F(\mathbf{u}_{S})-F(\mathbf{u}_{S}^{(S)})\big{]}+\mathbb{E}\big{[}F_{S}(\mathbf{u}_{S}^{(S)})-F_{S}(\mathbf{u}_{S})\big{]},$
(H.8)

where the second identity holds since $z_{i}$ is independent of
$\mathbf{u}_{i}$. It then follows that

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

According to the Lipschitz continuity we know

$\big{|}F(\mathbf{u}_{S})-F(\mathbf{u}_{S}^{(S)})\big{|}\leq
G\|\mathbf{u}_{S}-\mathbf{u}_{S}^{(S)}\|_{2}\quad\text{and}\quad\big{|}F_{S}(\mathbf{u}_{S})-F_{S}(\mathbf{u}_{S}^{(S)})\big{|}\leq
G\|\mathbf{u}_{S}-\mathbf{u}_{S}^{(S)}\|_{2}.$

Plugging the above inequality back into (H.8), we derive the following
inequality

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

By Lemma H.1 and (H.2), we can also have

$\mathbb{E}\big{[}f(\mathbf{u}_{i}^{(i)};z_{i})-f(\mathbf{u}_{S}^{(S)};z_{i})\big{]}\geq-\frac{n}{2}\mathbb{E}\big{[}\frac{1}{\beta_{2}(S)}\|\nabla_{\mathbf{v}}F_{S}(\mathbf{u}_{i}^{(i)})\|_{2}^{2}\big{]}.$

Using this inequality, one can analyze analogously to (H.10) and derive the
following inequality

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

The stated inequality follows from the above inequality and (H.10). The proof
is complete. ∎

##  Appendix I Additional Experiments

In this section, we investigate the stability of SGDA on a nonconvex-
nonconcave problem. We consider the vanilla GAN structure proposed in
Goodfellow et al. (2014). The generator and the discriminator consist of 4
fully connected layers, and use the leaky rectified linear activation before
the output layer. The generator uses the hyperbolic tangent activation at the
output layer. The discriminator uses the sigmoid activation at the output
layer. In order to make experiments more interpretable in terms of stability,
we remove all forms of regularization such as the weight decay or dropout in
the original paper. In order to truly implement SGDA, we generate only one
noise for updating both the discriminator and the generator at each iteration.
This differs from the common GAN training strategy, which uses different
noises for updating the discriminator and the generator. We employ the mnist
dataset (LeCun et al., 1998) and build neighboring datasets $S$ and
$S^{\prime}$ by removing a randomly chosen datum indexed by $i$ from $S$ and
$i+1$ from $S^{\prime}$. The algorithm is run based on the same trajectory for
$S$ and $S^{\prime}$ by fixing the random seed. We randomly pick 5 different
$i$’s and 5 different random seeds (total 25 runs). The step sizes for the
discriminator and the generator are chosen as constants, i.e. $\eta=0.0002$.
We compute the Euclidean distance, i.e., Frobenius norm, between the
parameters trained on the neighboring datasets. Note that we do not target at
optimizing the test accuracy, but give an interpretable visualization to
validate our theoretical findings. The results are given in Figure I.1.

Figure I.1: The parameter distance versus the number of passes. Left:
generator, right: discriminator. ’total’ is the mean normalized Euclidean
distance across all layers and the shaded area is the standard deviation.

It is clear that the parameter distances for both the generator and the
discriminator continue to increase during the training process of SGDA, which
is consistent with our analysis in Section F.1 and F.3.