2\eta_{y}^{2}\left\|\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\right\|^{2}+2\eta_{y}^{2}\left\|\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{y}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2})\right\|^{2}$
$\displaystyle\leq
4\eta_{y}^{2}\ell\left(\Phi(\boldsymbol{x}_{t-1})-f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\right)+2\eta_{y}^{2}\ell^{2}\left(\left\|\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t-2}\right\|^{2}+\left\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\right\|^{2}\right)$
$\displaystyle\leq
2\eta_{y}^{2}\ell^{2}\left\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\right\|^{2}+4\eta_{y}^{2}\ell\left(\Phi(\boldsymbol{x}_{t-1})-f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\right)+2\eta_{x}^{2}\eta_{y}^{2}\ell^{2}G^{2}.$

Unrolling the recursion yields:

$\displaystyle\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}$
$\displaystyle\leq(2\eta_{y}^{2}\ell^{2})^{t-1}\left\|\boldsymbol{y}_{0}-\boldsymbol{y}_{-1}\right\|^{2}+\sum_{j=1}^{t}(2\eta_{y}^{2}\ell^{2})^{t-j}4\eta_{y}^{2}\ell\left(\Phi(\boldsymbol{x}_{j-1})-f(\boldsymbol{x}_{j-1},\boldsymbol{y}_{j-1})\right)$
$\displaystyle\quad+\sum_{j=1}^{t}(2\eta_{y}^{2}\ell^{2})^{t-j}2\eta_{x}^{2}\eta_{y}^{2}\ell^{2}G^{2}.$

Since $\boldsymbol{y}_{0}=\boldsymbol{y}_{-1}$, we have:

$\displaystyle\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}$
$\displaystyle\leq\sum_{j=1}^{t}(2\eta_{y}^{2}\ell^{2})^{t-j}4\eta_{y}^{2}\ell\left(\Phi(\boldsymbol{x}_{j-1})-f(\boldsymbol{x}_{j-1},\boldsymbol{y}_{j-1})\right)+\sum_{j=1}^{t}(2\eta_{y}^{2}\ell^{2})^{t-j}2\eta_{x}^{2}\eta_{y}^{2}\ell^{2}G^{2}.$

Finally, summing the above inequality over $t=0$ to $T$ yields:

$\displaystyle\sum_{t=0}^{T}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}$
$\displaystyle\leq\sum_{t=0}^{T}\left(\sum_{j=0}^{T}(2\eta_{y}^{2}\ell^{2})^{j}\right)4\eta_{y}^{2}\ell\left(\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\right)$
$\displaystyle\quad+\sum_{t=0}^{T}\left(\sum_{j=0}^{T}(2\eta_{y}^{2}\ell^{2})^{j}\right)2\eta_{x}^{2}\eta_{y}^{2}\ell^{2}G^{2}.$

∎

######  Lemma B.4.

For OGDA (Algorithm 2), under Theorem 4.8’s assumptions, the following
statement holds for the generated sequence $\\{\boldsymbol{y}_{t}\\}$ during
algorithm proceeding and $\forall s\leq t$:

$\displaystyle\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})$
$\displaystyle\leq
2\eta_{x}(t-s)G^{2}+\frac{1}{2\eta_{y}}\left(\|\boldsymbol{y}_{t-1}-y^{*}(\boldsymbol{x}_{s})\|^{2}-\|\boldsymbol{y}_{t}-\boldsymbol{y}^{*}(x_{s})\|^{2}-\frac{1}{2}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}\right)$
$\displaystyle\quad+\frac{1}{2\eta_{y}}\left(\frac{1}{2}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}+\eta_{y}\eta_{x}^{2}\ell
G^{2}\right)-\langle\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1}),$
$\displaystyle\quad\boldsymbol{y}_{t}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\rangle+\langle\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{y}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2}),\boldsymbol{y}_{t-1}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\rangle.$

###### Proof.

Observe that:

$\displaystyle\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})$
$\displaystyle\leq
f(\boldsymbol{x}_{t},\boldsymbol{y}^{*}(\boldsymbol{x}_{t}))-f(\boldsymbol{x}_{s},\boldsymbol{y}^{*}(\boldsymbol{x}_{t}))+f(\boldsymbol{x}_{s},\boldsymbol{y}^{*}(\boldsymbol{x}_{s}))-f(\boldsymbol{x}_{t},\boldsymbol{y}^{*}(\boldsymbol{x}_{s}))$
$\displaystyle\quad+f(\boldsymbol{x}_{t},\boldsymbol{y}^{*}(\boldsymbol{x}_{s}))-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})$
$\displaystyle\leq
2(t-s)\eta_{x}G^{2}-\langle\boldsymbol{y}_{t}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\rangle,$

where in the last step we use the concavity of $f(\boldsymbol{x}_{t},\cdot)$.

Plugging in Lemma B.1 will conclude the proof as follows:

$\displaystyle\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})$
$\displaystyle\leq 2(t-s)\eta_{x}G^{2}$
$\displaystyle\quad+\frac{1}{2\eta_{y}}\left(\|\boldsymbol{y}_{t-1}-\boldsymbol{y}\|^{2}-\|\boldsymbol{y}_{t}-\boldsymbol{y}\|^{2}-\frac{1}{2}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}+\frac{1}{2}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}\right)$
$\displaystyle\quad+\frac{1}{2\eta_{y}}\eta_{y}\eta_{x}^{2}\ell
G^{2}-\langle\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1}),\boldsymbol{y}_{t}-\boldsymbol{y}\rangle$
$\displaystyle\quad+\langle\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{y}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2}),\boldsymbol{y}_{t-1}-\boldsymbol{y}\rangle.$

∎

######  Lemma B.5.

For OGDA (Algorithm 2), under the same assumptions made in Theorem 4.8, the
following statement holds for the generated sequence
$\\{\boldsymbol{x}_{t}\\},\\{\boldsymbol{y}_{t}\\}$ during algorithm
proceeding:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\leq\frac{1}{B}\left(2\eta_{x}B^{2}G^{2}+\frac{1}{2\eta_{y}}\left(D^{2}+\eta_{y}\ell
D^{2}\right)+2(3\eta_{x}G^{2}+D)D\right).$

###### Proof.

Let $S=(T+1)/B$, and we choose $s=jB$, $j=0,...,S$. Then by summing over $t$
on the both side of Lemma B.4 we have:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})=\frac{1}{T+1}\sum_{j=0}^{S}\sum_{t=jB}^{(j+1)B-1}\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})$
$\displaystyle\quad\leq\frac{1}{T+1}\sum_{j=0}^{S}\left[2\eta_{x}B^{2}G^{2}+\frac{1}{2\eta_{y}}\left(\|\boldsymbol{y}_{jB-1}-\boldsymbol{y}^{*}(x_{jB})\|^{2}+\frac{1}{2}\|\boldsymbol{y}_{jB-1}-\boldsymbol{y}_{jB-2}\|^{2}\right)\right]$
$\displaystyle\quad\quad+\frac{1}{T+1}\sum_{j=0}^{S}\left(-\langle\nabla_{y}f(\boldsymbol{x}_{(j+1)B-1},y_{(j+1)B-1})-\nabla_{y}f(\boldsymbol{x}_{(j+1)B-2},y_{(j+1)B-2}),\right.$
$\displaystyle\quad\quad\quad\left.\boldsymbol{y}_{(j+1)B-1}-y^{*}(\boldsymbol{x}_{jB})\rangle+\langle\nabla_{y}f(\boldsymbol{x}_{jB-1},\boldsymbol{y}_{jB-1})-\nabla_{y}f(\boldsymbol{x}_{jB-2},\boldsymbol{y}_{jB-2}),\boldsymbol{y}_{jB-1}-y^{*}(\boldsymbol{x}_{jB}\rangle\right)$
$\displaystyle\quad\leq\frac{1}{T+1}\sum_{j=0}^{S}\left(2\eta_{x}B^{2}G^{2}+\frac{1}{2\eta_{y}}\left(D^{2}+\frac{1}{2}D^{2}\right)+2(3\eta_{x}G^{2}+D)D\right)$
$\displaystyle\quad\leq\frac{1}{B}\left(2\eta_{x}B^{2}G^{2}+\frac{1}{2\eta_{y}}\left(D^{2}+\eta_{y}\ell
D^{2}\right)+2(3\eta_{x}G^{2}+D)D\right).$

∎

#####  B.1.2 Proof of Theorem 4.8 for OGDA

In this section we are going to provide the proof of Theorem 4.8 on the
convergence rate of OGDA in both deterministic and stochastic settings.

We start by establishing the convergence rate in deterministic setting.
Before, we first state the formal version of Theorem 4.8 here:

######  Theorem B.6 (OGDA Deterministic (Theorem 4.8 restated)).

Under Assumption 4.7, if we choose
$\eta_{x}=\Theta\left(\min\left\\{\frac{\epsilon}{\ell
G},\frac{\epsilon^{2}}{\ell
G^{2}},\frac{\epsilon^{4}}{D^{2}G^{2}\ell^{3}}\right\\}\right)$,
$\eta_{y}=\frac{1}{2\ell}$, then OGDA (Algorithm 2) guarantees to find
$\epsilon$-stationary point, i.e.,
$\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}\leq\epsilon^{2}$,
with the gradient complexity bounded by:

$\displaystyle O\left(\frac{\ell
G^{2}\hat{\Delta}_{\Phi}}{\epsilon^{4}}\max\left\\{1,\frac{D^{2}\ell^{2}}{\epsilon^{2}}\right\\}\right).$

###### Proof.

From Lemma B.2 we have:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}$
$\displaystyle\leq\frac{\Phi_{1/2\ell}({\boldsymbol{x}}_{0})-\Phi_{1/2\ell}(\boldsymbol{x}_{t})}{\eta_{x}T}+16\ell\frac{1}{T}\sum_{t=0}^{T-1}\left(\Phi({\boldsymbol{x}}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\right)+24\eta_{x}\ell
G^{2}$
$\displaystyle+4\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2},$
$\displaystyle\leq\frac{\Phi_{1/2\ell}({\boldsymbol{x}}_{0})-\Phi_{1/2\ell}(\boldsymbol{x}_{t})}{\eta_{x}T}+16\ell\frac{1}{T}\sum_{t=0}^{T-1}\left(\Phi({\boldsymbol{x}}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\right)+24\eta_{x}\ell
G^{2}$
$\displaystyle+4\frac{1}{T+1}\sum_{t=0}^{T}\ell^{2}(3\eta_{x}^{2}G^{2}+\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}).$

Plugging in Lemma B.3 yields:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}\leq\frac{\Phi_{1/2\ell}({\boldsymbol{x}}_{0})-\Phi_{1/2\ell}(\boldsymbol{x}_{t})}{\eta_{x}T}$
$\displaystyle\qquad+16\ell\frac{1}{T}\sum_{t=0}^{T-1}\left(\Phi({\boldsymbol{x}}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\right)+24\eta_{x}\ell
G^{2}+12\eta_{x}^{2}\ell^{2}G^{2}$
$\displaystyle\qquad+4\frac{1}{T+1}\ell^{2}\left(\sum_{t=0}^{T}\left(\sum_{j=0}^{T}(2\eta_{y}^{2}\ell^{2})^{j}\right)4\eta_{y}^{2}\ell\left(\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\right)+\sum_{t=0}^{T}\left(\sum_{j=0}^{T}(2\eta_{y}^{2}\ell^{2})^{j}\right)2\eta_{x}^{2}\eta_{y}^{2}\ell^{2}G^{2}\right),$

since we choose $\eta_{y}\ell\leq\frac{1}{2}$, we know that:

$\displaystyle\sum_{j=0}^{T}\left(2\eta_{y}^{2}\ell^{2}\right)^{j}\leq 2.$

Hence we have:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}$
$\displaystyle\leq\frac{\Phi_{1/2\ell}({\boldsymbol{x}}_{0})-\Phi_{1/2\ell}(\boldsymbol{x}_{t})}{\eta_{x}T}+(16\ell+32\eta_{y}^{2}\ell^{3})\frac{1}{T+1}\sum_{t=0}^{T}\left(\Phi({\boldsymbol{x}}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\right)$
$\displaystyle\quad+24\eta_{x}\ell
G^{2}+12\eta_{x}^{2}\ell^{2}G^{2}+16\eta_{x}^{2}\eta_{y}^{2}\ell^{4}G^{2}.$

Now we plug in Lemma B.5 to replace
$\Phi({\boldsymbol{x}}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})$:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}$
$\displaystyle\leq\frac{\Phi_{1/2\ell}({\boldsymbol{x}}_{0})-\Phi_{1/2\ell}(\boldsymbol{x}_{t})}{\eta_{x}T}$
$\displaystyle\quad+(16\ell+32\eta_{y}^{2}\ell^{3})\frac{1}{B}\left(2\eta_{x}B^{2}G^{2}+\frac{1}{2\eta_{y}}\left(D^{2}+\eta_{y}\ell
D^{2}\right)+2(3\eta_{x}G^{2}+D)D\right)$ $\displaystyle\quad+24\eta_{x}\ell
G^{2}+12\eta_{x}^{2}\ell^{2}G^{2}+16\eta_{x}^{2}\eta_{y}^{2}\ell^{4}G^{2}.$

Choose
$B=O\left(\frac{D}{G\sqrt{\eta_{x}\eta_{y}}}\right),\eta_{x}=O\left(\min\left\\{\frac{\epsilon}{\ell
G},\frac{\epsilon^{2}}{\ell
G^{2}},\frac{\epsilon^{4}}{D^{2}G^{2}\ell^{3}}\right\\}\right)$,
$\eta_{y}=\frac{1}{2\ell}$, and then we guarantee that
$\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}\leq\epsilon^{2}$
with the gradient complexity is bounded by:

$\displaystyle O\left(\frac{\ell
G^{2}\hat{\Delta}_{\Phi}}{\epsilon^{4}}\max\left\\{1,\frac{D^{2}\ell^{2}}{\epsilon^{2}}\right\\}\right).$

∎

Stochastic setting.

We now turn to presenting the proof of OGDA in stochastic setting. First let
us introduce some useful lemmas.

#####  B.1.3 Useful Lemmas

######  Lemma B.7.

For Stochastic OGDA (Algorithm 2), under the same assumptions made in Theorem
4.9, if we choose $\eta\leq 1/4\ell$ the following statement holds for the
generated sequence $\\{\boldsymbol{y}_{t}\\}$ during algorithm proceeding and
for any $\boldsymbol{y}\in\mathcal{Y}$:

$\displaystyle\mathbb{E}\|\boldsymbol{y}-\boldsymbol{y}_{t}\|^{2}$
$\displaystyle{\leq}\mathbb{E}\|\boldsymbol{y}-\boldsymbol{y}_{t-1}\|^{2}-\frac{1}{4}\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}+\frac{1}{4}\mathbb{E}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}+2\eta_{y}\langle\boldsymbol{y}_{t}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\rangle$
$\displaystyle+\eta_{y}\eta_{x}^{2}\ell(G^{2}+\sigma^{2})+6\eta_{y}^{2}\sigma^{2}-2\eta_{y}\langle\boldsymbol{y}_{t}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\rangle$
$\displaystyle+2\eta_{y}\langle\boldsymbol{y}_{t-1}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{y}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2})\rangle.$

###### Proof.

The proof is similar to deterministic setting. Here we use $\xi_{t-1}$ to
denote the random sample at iteration $t$. According to updating rule of
$\boldsymbol{y}$:

$\displaystyle\boldsymbol{y}_{t}=\mathcal{P}_{\mathcal{Y}}\left(\boldsymbol{y}_{t-1}+2\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1};\xi_{t-1})-\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2};\xi_{t-1})\right)$

Similarly to deterministic setting, we let

$\displaystyle\tilde{\varepsilon}_{t-1}=\eta_{y}(\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1};\xi_{t-1}))-\eta_{y}(\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1};\xi_{t-1})-\nabla_{y}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2};\xi_{t-1}))$
$\displaystyle{\varepsilon}_{t-1}=\eta_{y}(\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1}))-\eta_{y}(\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{y}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2}))$

and re-write the updating rule as:

$\displaystyle\boldsymbol{y}_{t}=\mathcal{P}_{\mathcal{Y}}\left(\boldsymbol{y}_{t-1}+\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\tilde{\varepsilon}_{t-1}\right)$

Due to the property of projection we have:

$\displaystyle(\boldsymbol{y}-\boldsymbol{y}_{t})^{\top}(\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}-\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})+\tilde{\varepsilon}_{t-1})\geq
0$

Using the identity that
$\langle\boldsymbol{a},\boldsymbol{b}\rangle=\frac{1}{2}(\|\boldsymbol{a}+\boldsymbol{b}\|^{2}-\|\boldsymbol{a}\|^{2}-\|\boldsymbol{b}\|^{2})$
we have:

$\displaystyle 0$
$\displaystyle\leq\|\boldsymbol{y}-\boldsymbol{y}_{t-1}-\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})+\tilde{\varepsilon}_{t-1}\|^{2}-\|\boldsymbol{y}-\boldsymbol{y}_{t}\|^{2}-\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}-\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})+\tilde{\varepsilon}_{t-1}\|^{2}$
$\displaystyle=\|\boldsymbol{y}-\boldsymbol{y}_{t-1}\|^{2}-\|\boldsymbol{y}-\boldsymbol{y}_{t}\|^{2}-\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}+2\langle\boldsymbol{y}_{t}-\boldsymbol{y},\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\rangle$
$\displaystyle+2\langle\boldsymbol{y}-\boldsymbol{y}_{t-1},\tilde{\varepsilon}_{t-1}\rangle-2\langle\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1},\tilde{\varepsilon}_{t-1}\rangle.$

Notice that

$\displaystyle-2\langle\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1},\tilde{\varepsilon}_{t-1}\rangle$
$\displaystyle=-2\langle\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1},{\varepsilon}_{t-1}\rangle-2\langle\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1},\tilde{\varepsilon}_{t-1}-{\varepsilon}_{t-1}\rangle$
$\displaystyle\leq-2\langle\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1},{\varepsilon}_{t-1}\rangle+\frac{1}{2}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}+2\|\tilde{\varepsilon}_{t-1}-{\varepsilon}_{t-1}\|^{2}$

So we have:

$\displaystyle 0$
$\displaystyle\leq\|\boldsymbol{y}-\boldsymbol{y}_{t-1}-\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})+\tilde{\varepsilon}_{t-1}\|^{2}-\|\boldsymbol{y}-\boldsymbol{y}_{t}\|^{2}-\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}-\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})+\tilde{\varepsilon}_{t-1}\|^{2}$
$\displaystyle=\|\boldsymbol{y}-\boldsymbol{y}_{t-1}\|^{2}-\|\boldsymbol{y}-\boldsymbol{y}_{t}\|^{2}-\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}+2\langle\boldsymbol{y}_{t}-\boldsymbol{y},\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\rangle$
$\displaystyle\quad+2\langle\boldsymbol{y}-\boldsymbol{y}_{t-1},\tilde{\varepsilon}_{t-1}\rangle-2\langle\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1},{\varepsilon}_{t-1}\rangle+\frac{1}{2}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}+2\|\tilde{\varepsilon}_{t-1}-{\varepsilon}_{t-1}\|^{2}.$

Taking expectation over $\xi_{t-1}$ yields:

$\displaystyle 0$
$\displaystyle\leq\mathbb{E}\|\boldsymbol{y}-\boldsymbol{y}_{t-1}\|^{2}-\mathbb{E}\|\boldsymbol{y}-\boldsymbol{y}_{t}\|^{2}-\frac{1}{2}\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}+2\langle\boldsymbol{y}_{t}-\boldsymbol{y},\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\rangle$
$\displaystyle\quad-2\langle\boldsymbol{y}_{t}-\boldsymbol{y},{\varepsilon}_{t-1}\rangle+6\eta_{y}^{2}\sigma^{2}.$

Now we plug the definition of $\varepsilon_{t-1}$ into above inequality:

$\displaystyle\mathbb{E}\|\boldsymbol{y}-\boldsymbol{y}_{t}\|^{2}$
$\displaystyle\leq\mathbb{E}\|\boldsymbol{y}-\boldsymbol{y}_{t-1}\|^{2}-\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}+2\eta_{y}\langle\boldsymbol{y}_{t}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\rangle$
$\displaystyle\quad-2\eta_{y}\langle\boldsymbol{y}_{t}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\rangle+6\eta_{y}^{2}\sigma^{2}$
$\displaystyle\quad+2\eta_{y}\langle\boldsymbol{y}_{t}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{y}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2})\rangle$
$\displaystyle\leq\mathbb{E}\|\boldsymbol{y}-\boldsymbol{y}_{t-1}\|^{2}-\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}+2\eta_{y}\langle\boldsymbol{y}_{t}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\rangle$
$\displaystyle\quad-2\eta_{y}\langle\boldsymbol{y}_{t}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\rangle+6\eta_{y}^{2}\sigma^{2}$
$\displaystyle\quad+2\eta_{y}\langle\boldsymbol{y}_{t-1}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{y}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2})\rangle$
$\displaystyle\quad+\eta_{y}\ell(\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}+\mathbb{E}\|\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t-2}\|^{2}+\mathbb{E}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2})$
$\displaystyle\stackrel{{\scriptstyle\text{\char
192}}}{{\leq}}\mathbb{E}\|\boldsymbol{y}-\boldsymbol{y}_{t-1}\|^{2}-\frac{1}{4}\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}+\frac{1}{4}\mathbb{E}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}$
$\displaystyle\quad+2\eta_{y}\langle\boldsymbol{y}_{t}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\rangle+\eta_{y}\eta_{x}^{2}\ell(G^{2}+\sigma^{2})+6\eta_{y}^{2}\sigma^{2}$
$\displaystyle\quad-2\eta_{y}\langle\boldsymbol{y}_{t}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\rangle$
$\displaystyle\quad+2\eta_{y}\langle\boldsymbol{y}_{t-1}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{y}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2})\rangle,$

where in ➀ we use the fact that $\eta_{y}\ell\leq\frac{1}{4}$ and hence can
conclude the proof.

∎

######  Lemma B.8.

For Stochastic OGDA (Algorithm 2), under same assumptions as in Theorem 4.9,
the following statement holds for the genserated sequence
$\\{\boldsymbol{x}_{t}\\},\\{\boldsymbol{y}_{t}\\}$ during algorithm
proceeding:

$\displaystyle\mathbb{E}[\Phi_{1/2\ell}(\boldsymbol{x}_{t})]$
$\displaystyle\leq\mathbb{E}[\Phi_{1/2\ell}({\boldsymbol{x}}_{t-1})]+2\eta_{x}\ell\mathbb{E}\left(\Phi(\boldsymbol{x}_{t-1})-f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\right)-\frac{\eta_{x}}{8}\mathbb{E}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t-1})\|^{2}$
$\displaystyle\quad+3\ell\eta_{x}^{2}(G^{2}+\sigma^{2})+\frac{\eta_{x}}{2}\mathbb{E}\|\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{x}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2})\|^{2}.$

###### Proof.

Let
$\hat{\boldsymbol{x}}_{t-1}=\arg\min_{\boldsymbol{x}\in\mathbb{R}^{d}}\Phi(\boldsymbol{x})+\ell\|\boldsymbol{x}-\boldsymbol{x}_{t-1}\|^{2}$.
Notice that:

$\displaystyle\mathbb{E}[\Phi_{1/2\ell}(\boldsymbol{x}_{t})]$
$\displaystyle\leq\mathbb{E}[\Phi_{1/2\ell}(\hat{\boldsymbol{x}}_{t-1})]+\ell\mathbb{E}\|\hat{\boldsymbol{x}}_{t-1}-\boldsymbol{x}_{t}\|^{2}$
$\displaystyle\leq\mathbb{E}[\Phi_{1/2\ell}(\hat{\boldsymbol{x}}_{t-1})]$
$\displaystyle\quad+\ell(\mathbb{E}\|\boldsymbol{x}_{t-1}-\hat{\boldsymbol{x}}_{t-1}\|^{2}+2\eta_{x}\langle
2\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{x}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2}),\boldsymbol{x}_{t-1}-\hat{\boldsymbol{x}}_{t-1}\rangle$
$\displaystyle\quad+3\eta_{x}^{2}(G^{2}+\sigma^{2}))$

According to smoothness of $f(\cdot,\boldsymbol{y})$, we have:

$\displaystyle\langle\hat{\boldsymbol{x}}_{t-1}-{\boldsymbol{x}}_{t-1},\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\rangle$
$\displaystyle\leq
f(\hat{\boldsymbol{x}}_{t-1},\boldsymbol{y}_{t-1})-f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})+\frac{\ell}{2}\|\hat{\boldsymbol{x}}_{t-1}-\boldsymbol{x}_{t-1}\|^{2}$
$\displaystyle\leq\Phi(\boldsymbol{x}_{t-1})-f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\frac{\ell}{2}\|\hat{\boldsymbol{x}}_{t-1}-\boldsymbol{x}_{t-1}\|^{2}.$

So we have

$\displaystyle\mathbb{E}[\Phi_{1/2\ell}(\boldsymbol{x}_{t})]$
$\displaystyle\leq\mathbb{E}[\Phi_{1/2\ell}(\hat{\boldsymbol{x}}_{t-1})]+\ell\mathbb{E}\|\hat{\boldsymbol{x}}_{t-1}-\boldsymbol{x}_{t}\|^{2}$
$\displaystyle\leq\mathbb{E}[\Phi_{1/2\ell}(\hat{\boldsymbol{x}}_{t-1})]+\ell\mathbb{E}\|\boldsymbol{x}_{t-1}-\hat{\boldsymbol{x}}_{t-1}\|^{2}$
$\displaystyle\quad+2\eta_{x}\ell\mathbb{E}\left(\Phi(\boldsymbol{x}_{t-1})-f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\frac{\ell}{2}\mathbb{E}\|\hat{\boldsymbol{x}}_{t-1}-\boldsymbol{x}_{t-1}\|^{2}\right)+3\ell\eta_{x}^{2}(G^{2}+\sigma^{2})$
$\displaystyle\quad+\eta_{x}\ell\left(\frac{1}{2\ell}\mathbb{E}\|\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{x}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2})\|^{2}+\frac{\ell}{2}\mathbb{E}\|\boldsymbol{x}_{t-1}-\hat{\boldsymbol{x}}_{t-1}\|^{2}\right)$
$\displaystyle\leq\mathbb{E}[\Phi_{1/2\ell}({\boldsymbol{x}}_{t-1})]+2\eta_{x}\ell\mathbb{E}\left(\Phi(\boldsymbol{x}_{t-1})-f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\right)-\frac{\eta_{x}\ell^{2}}{2}\mathbb{E}\|\hat{\boldsymbol{x}}_{t-1}-\boldsymbol{x}_{t-1}\|^{2}$
$\displaystyle\quad+3\ell\eta_{x}^{2}(G^{2}+\sigma^{2})+\frac{\eta_{x}}{2}\mathbb{E}\|\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{x}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2})\|^{2}.$

∎

######  Lemma B.9.

For Stochastic OGDA (Algorithm 2), under Theorem 4.9’s assumptions, the
following statement holds for the generated sequence
$\\{\boldsymbol{y}_{t}\\}$ during algorithm proceeding:

$\displaystyle\sum_{t=0}^{T}\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}$
$\displaystyle\leq
4\eta_{y}^{2}\ell\sum_{t=0}^{T}\left(\sum_{j=0}^{T}\left(2\eta_{y}^{2}\ell^{2}\right)^{j}\right)\mathbb{E}[\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})]$
$\displaystyle\quad+\sum_{t=0}^{T}\left(\sum_{j=0}^{T}\left(2\eta_{y}^{2}\ell^{2}\right)^{j}\right)\left(6\eta_{x}^{2}\eta_{y}^{2}\ell^{2}(G^{2}+\sigma^{2})+{6\eta_{y}^{2}\sigma^{2}}\right)$

###### Proof.

According to updating rule of stochastic OGDA:

$\displaystyle\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}$
$\displaystyle\leq\eta_{y}^{2}\mathbb{E}\|2\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1};\xi_{t-1})-f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2};\xi_{t-1})\|^{2}$
$\displaystyle\leq
2\eta_{y}^{2}\mathbb{E}\|\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}+2\eta_{y}^{2}{\sigma^{2}}+2\eta_{y}^{2}\mathbb{E}\|\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2})\|^{2}+4\eta_{y}^{2}{\sigma^{2}}$
$\displaystyle\leq
4\eta_{y}^{2}\ell\mathbb{E}[\Phi(\boldsymbol{x}_{t-1})-f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})]+2\eta_{y}^{2}\ell^{2}(\mathbb{E}\|\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t-2}\|^{2}+\mathbb{E}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2})+{6\eta_{y}^{2}\sigma^{2}}$
$\displaystyle\leq
4\eta_{y}^{2}\ell\mathbb{E}[\Phi(\boldsymbol{x}_{t-1})-f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})]+2\eta_{y}^{2}\ell^{2}(3\eta_{x}^{2}(G^{2}+\sigma^{2})+\mathbb{E}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2})+{6\eta_{y}^{2}\sigma^{2}}.$

Unrolling the recursion yields:

$\displaystyle\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}$
$\displaystyle\leq
4\eta_{y}^{2}\ell\sum_{j=0}^{t-1}\left(2\eta_{y}^{2}\ell^{2}\right)^{t-1-j}\mathbb{E}[\Phi(x_{j})-f(x_{j},y_{j})]$
$\displaystyle\quad+\sum_{j=0}^{t-1}\left(2\eta_{y}^{2}\ell^{2}\right)^{t-1-j}\left(6\eta_{x}^{2}\eta_{y}^{2}\ell^{2}(G^{2}+\sigma^{2})+{6\eta_{y}^{2}\sigma^{2}}\right)+(2\eta_{y}^{2}\ell^{2})\mathbb{E}\|\boldsymbol{y}_{0}-\boldsymbol{y}_{-1}\|^{2}.$

Since $\boldsymbol{y}_{0}=\boldsymbol{y}_{-1}$, we can conclude the proof via
summing $t$ from $0$ to $T-1$:

$\displaystyle\sum_{t=0}^{T}\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}$
$\displaystyle\leq
4\eta_{y}^{2}\ell\sum_{t=0}^{T}\left(\sum_{j=0}^{T}\left(2\eta_{y}^{2}\ell^{2}\right)^{j}\right)\mathbb{E}[\Phi(x_{t})-f(x_{t},y_{t})]$
$\displaystyle\quad+\sum_{t=0}^{T}\left(\sum_{j=0}^{T}\left(2\eta_{y}^{2}\ell^{2}\right)^{j}\right)\left(6\eta_{x}^{2}\eta_{y}^{2}\ell^{2}(G^{2}+\sigma^{2})+{6\eta_{y}^{2}\sigma^{2}}\right).$

∎

######  Lemma B.10.

For Stochastic OGDA (Algorithm 2), under assumptions made in Theorem 4.9, the
following statement holds for the generated sequence
$\\{\boldsymbol{y}_{t}\\}$ during algorithm proceeding and $\forall s\leq t$:

$\displaystyle\mathbb{E}[\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})]\leq
2\eta_{x}(t-s)G\sqrt{G^{2}+\sigma^{2}}+\frac{\eta_{y}\eta_{x}^{2}\ell}{2}(G^{2}+\sigma^{2})+3\eta_{y}\sigma^{2}$
$\displaystyle\quad+\frac{1}{2\eta_{y}}\left(\mathbb{E}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}-\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}-\frac{1}{4}\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}+\frac{1}{4}\mathbb{E}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}\right)$
$\displaystyle\quad+\langle\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1}),\boldsymbol{y}_{t}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\rangle$
$\displaystyle\quad-\langle\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{y}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2}),\boldsymbol{y}_{t-1}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\rangle.$

###### Proof.

Observe that:

$\displaystyle\mathbb{E}[\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})]$
$\displaystyle\leq\mathbb{E}[f(\boldsymbol{x}_{t},\boldsymbol{y}^{*}(\boldsymbol{x}_{t}))-f(\boldsymbol{x}_{s},\boldsymbol{y}^{*}(\boldsymbol{x}_{t}))]+\mathbb{E}[f(\boldsymbol{x}_{s},\boldsymbol{y}^{*}(\boldsymbol{x}_{s}))-f(\boldsymbol{x}_{t},\boldsymbol{y}^{*}(\boldsymbol{x}_{s}))]$
$\displaystyle\quad+\mathbb{E}[f(\boldsymbol{x}_{t},\boldsymbol{y}^{*}(\boldsymbol{x}_{s}))-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})]$
$\displaystyle\leq
2(t-s)\eta_{x}G\sqrt{G^{2}+\sigma^{2}}-\mathbb{E}\langle\boldsymbol{y}_{t}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\rangle.$

Plugging in Lemma B.7 will conclude the proof. ∎

######  Lemma B.11.

For Stochastic OGDA (Algorithm 2), under Theorem 4.9’s assumptions, the
following statement holds for the generated sequence
$\\{\boldsymbol{x}_{t}\\},\\{\boldsymbol{y}_{t}\\}$ during algorithm
proceeding:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}[\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})]$
$\displaystyle\leq\frac{1}{B}\left(2\eta_{x}B^{2}G\sqrt{G^{2}+\sigma^{2}}+\frac{5D^{2}}{8\eta_{y}}+2(3\eta_{x}G\sqrt{G^{2}+\sigma^{2}}+D)D\right)$
$\displaystyle\quad+\frac{\eta_{y}\eta_{x}^{2}\ell}{2}(G^{2}+\sigma^{2})+3\eta_{y}\sigma^{2}.$

###### Proof.

Let $S=(T+1)/B$, and we choose $s=jB$, $j=0,...,S$. Then by summing over $t$
on the both side of Lemma B.11 we have:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T-1}\mathbb{E}[\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})]=\frac{1}{T}\sum_{j=0}^{S}\sum_{t=jB}^{(j+1)B-1}\mathbb{E}[\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})]$
$\displaystyle\leq\frac{1}{T}\sum_{j=0}^{S}\left[2\eta_{x}B^{2}G\sqrt{G^{2}+\sigma^{2}}+\frac{1}{2\eta_{y}}\left(\|y_{jB}-y^{*}(x_{jB})\|^{2}+\frac{1}{4}\|y_{jB}-y_{jB-1}\|^{2}\right)\right]$
$\displaystyle\quad+\frac{\eta_{y}\eta_{x}^{2}\ell}{2}(G^{2}+\sigma^{2})+3\eta_{y}\sigma^{2}$
$\displaystyle\quad+\frac{1}{T}\sum_{j=0}^{S}\left[-\langle\nabla_{y}f(\boldsymbol{x}_{(j+1)B-1},y_{(j+1)B-1})-\nabla_{y}f(\boldsymbol{x}_{(j+1)B-2},y_{(j+1)B-2}),\boldsymbol{y}_{(j+1)B-1}-y^{*}(\boldsymbol{x}_{jB})\rangle\right.$
$\displaystyle\qquad\qquad\left.+\langle\nabla_{y}f(\boldsymbol{x}_{jB-1},\boldsymbol{y}_{jB-1})-\nabla_{y}f(\boldsymbol{x}_{jB-2},\boldsymbol{y}_{jB-2}),\boldsymbol{y}_{jB-1}-y^{*}(\boldsymbol{x}_{jB}\rangle\right]$
$\displaystyle\leq\frac{1}{T}\sum_{j=0}^{S}\left[2\eta_{x}B^{2}G\sqrt{G^{2}+\sigma^{2}}+\frac{5D^{2}}{8\eta_{y}}+2(3\eta_{x}G\sqrt{G^{2}+\sigma^{2}}+D)D\right]$
$\displaystyle\quad+\frac{\eta_{y}\eta_{x}^{2}\ell}{2}(G^{2}+\sigma^{2})+3\eta_{y}\sigma^{2}$
$\displaystyle\leq\frac{1}{B}\left[2\eta_{x}B^{2}G\sqrt{G^{2}+\sigma^{2}}+\frac{5D^{2}}{8\eta_{y}}+2(3\eta_{x}G\sqrt{G^{2}+\sigma^{2}}+D)D\right]$
$\displaystyle\quad+\frac{\eta_{y}\eta_{x}^{2}\ell}{2}(G^{2}+\sigma^{2})+3\eta_{y}\sigma^{2}.$

∎

#####  B.1.4 Proof of Theorem 4.9 for OGDA

In this section we are going to provide the proof for Theorem 4.9, the
convergence rate of OGDA in stochastic setting. We first introduce the formal
version of Theorem 4.9 here:

######  Theorem B.12 (OGDA Stochastic (Theorem 4.9 restated)).

Under Assumption 4.3 and 4.7, if we choose
$\eta_{x}=O(\min\\{\frac{\epsilon^{2}}{\ell(G^{2}+\sigma^{2})},\frac{\epsilon^{4}}{D^{2}\ell^{3}G\sqrt{G^{2}+\sigma^{2}}},\frac{\epsilon^{6}}{D^{2}\ell^{3}\sigma^{2}G\sqrt{G^{2}+\sigma^{2}}}\\})$,
$\eta_{y}=O(\min\\{\frac{1}{4\ell},\frac{\epsilon^{2}}{\ell\sigma^{2}}\\})$,
then Stochastic OGDA (Algorithm 2) guarantees to find $\epsilon$-stationary
point, i.e.,
$\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}\leq\epsilon^{2}$,
with the gradient complexity bounded by:

$\displaystyle
O\left(\frac{D^{2}\ell^{3}G\sqrt{G^{2}+\sigma^{2}}}{\epsilon^{6}}\max\left\\{1,\frac{\sigma^{2}}{\epsilon^{2}}\right\\}\right).$

###### Proof.

Similar to the proof in deterministic setting, first according to Lemma B.8 we
have:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}$
$\displaystyle\leq\frac{\Phi_{1/2\ell}(\boldsymbol{x}_{0})-\Phi_{1/2\ell}(\boldsymbol{x}_{T+1})}{\eta_{x}(T+1)}$
$\displaystyle\quad+16\ell\frac{1}{T+1}\sum_{t=0}^{T}\left(\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\right)+12\eta_{x}^{2}\ell^{2}(G^{2}+\sigma^{2})+24\ell\eta_{x}(G^{2}+\sigma^{2})$
$\displaystyle\quad+4\ell^{2}\frac{1}{T+1}\left(4\eta_{y}^{2}\ell\sum_{t=0}^{T+1}\left(\sum_{j=0}^{T}\left(2\eta_{y}^{2}\ell^{2}\right)^{j}\right)\mathbb{E}[\Phi(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})]\right.$
$\displaystyle\quad+\left.\sum_{t=0}^{T}\left(\sum_{j=0}^{T}\left(2\eta_{y}^{2}\ell^{2}\right)^{j}\right)\left(6\eta_{x}^{2}\eta_{y}^{2}\ell^{2}(G^{2}+\sigma^{2})+6\eta_{y}^{2}\sigma^{2}\right)\right).$

Since we choose $\eta_{y}\ell\leq\frac{1}{4}$, it follows that:

$\displaystyle\sum_{j=0}^{T}\left(2\eta_{y}^{2}\ell^{2}\right)^{j}\leq 2.$

As a result, we can further simplify the bound as:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}$
$\displaystyle\leq\frac{\Phi_{1/2\ell}({x}_{0})-\Phi_{1/2\ell}(\boldsymbol{x}_{T+1})}{\eta_{x}(T+1)}$
$\displaystyle\quad+(16\ell+32\eta_{y}^{2}\ell^{3})\frac{1}{T+1}\sum_{t=0}^{T}\left(\Phi({x}_{t})-f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\right)$
$\displaystyle\quad+12\eta_{x}^{2}\ell^{2}(G^{2}+\sigma^{2})+24\ell\eta_{x}(G^{2}+\sigma^{2})+8\ell^{2}\left(6\eta_{x}^{2}\eta_{y}^{2}\ell^{2}(G^{2}+\sigma^{2})+{6\eta_{y}^{2}\sigma^{2}}\right).$

Plugging in Lemma B.11 yields:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}$
$\displaystyle\leq\frac{\Phi_{1/2\ell}({x}_{0})-\Phi_{1/2\ell}(\boldsymbol{x}_{T+1})}{\eta_{x}(T+1)}$
$\displaystyle\quad+(16\ell+32\eta_{y}^{2}\ell^{3})\frac{1}{B}\left(2\eta_{x}B^{2}G\sqrt{G^{2}+\sigma^{2}}+\frac{5D^{2}}{8\eta_{y}}+2(3\eta_{x}G\sqrt{G^{2}+\sigma^{2}}+D)D\right)$
$\displaystyle\quad+(16\ell+32\eta_{y}^{2}\ell^{3})(\frac{\eta_{y}\eta_{x}^{2}\ell}{2}(G^{2}+\sigma^{2})+3\eta_{y}\sigma^{2})$
$\displaystyle\quad+12\eta_{x}^{2}\ell^{2}(G^{2}+\sigma^{2})+24\ell\eta_{x}(G^{2}+\sigma^{2})+8\ell^{2}\left(6\eta_{x}^{2}\eta_{y}^{2}\ell^{2}(G^{2}+\sigma^{2})+{6\eta_{y}^{2}\sigma^{2}}\right).$

Choose $B=O(\frac{D}{\sqrt{\eta_{x}\eta_{y}G\sqrt{G^{2}+\sigma^{2}}}})$,
$\eta_{x}=O(\min\\{\frac{\epsilon^{2}}{\ell(G^{2}+\sigma^{2})},\frac{\epsilon^{4}}{D^{2}\ell^{3}G\sqrt{G^{2}+\sigma^{2}}},\frac{\epsilon^{6}}{D^{2}\ell^{3}\sigma^{2}G\sqrt{G^{2}+\sigma^{2}}}\\})$,
$\eta_{y}=O(\min\\{\frac{1}{4\ell},\frac{\epsilon^{2}}{\ell\sigma^{2}}\\})$,
and then it is guaranteed that
$\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}\leq\epsilon^{2}$
with the gradient complexity is bounded by

$\displaystyle
O\left(\frac{D^{2}\ell^{3}G\sqrt{G^{2}+\sigma^{2}}}{\epsilon^{6}}\max\left\\{1,\frac{\sigma^{2}}{\epsilon^{2}}\right\\}\right).$

∎

####  B.2 Proof of convergence of EG

In this section, the convergence of EG in NC-C setting has been established.
Before presenting the complete proofs, here we briefly discuss the proof
sketch.

###### Proof sketch

Similar to OGDA, we have the following lemma on $\Phi_{1/2\ell}$:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla\Phi_{1/2\ell}({\boldsymbol{x}}_{t-\frac{1}{2}})\|^{2}$
$\displaystyle\leq\Phi_{1/2\ell}({\boldsymbol{x}}_{-\frac{1}{2}})-\Phi_{1/2\ell}(\boldsymbol{x}_{T+\frac{1}{2}})$
$\displaystyle\quad+O(\ell+\eta_{y}^{2}\ell^{3})\frac{1}{T+1}\sum_{t=0}^{T}\delta_{t-\frac{1}{2}}+O(\ell\eta_{x}^{2}G^{2}).$

Now we need to examine $\delta_{t-\frac{1}{2}}$. To bound this term, we have
the following recursion:

$\displaystyle\Phi(\boldsymbol{x}_{t+\frac{1}{2}})-f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})$
$\displaystyle\leq O((t-s)\eta_{x}G^{2})$
$\displaystyle\quad+\frac{1}{2\eta_{y}}\left(\|\boldsymbol{y}_{t}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}-\|\boldsymbol{y}_{t+1}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}+\frac{\eta_{x}^{2}G^{2}}{2}\right),$

which is derived by the descent property of EG on concave function. Similar to
OGDA, here we also obtain neat recursion, which will yield our desired
complexity bound.

In the following, we present the key lemmas, and complete convergence proof of
EG. First let us introduce some useful lemmas for the deterministic setting.

#####  B.2.1 Useful Lemmas

######  Proposition B.13 ([5], Proposition 4.2).

If $\boldsymbol{p}=\mathcal{P}_{\mathcal{Y}}(\boldsymbol{r}-\boldsymbol{u})$,
$\boldsymbol{q}=\mathcal{P}_{\mathcal{Y}}(\boldsymbol{r}-\boldsymbol{v})$, and

$\displaystyle\|\boldsymbol{u}-\boldsymbol{v}\|^{2}\leq
C_{1}^{2}\|\boldsymbol{p}-\boldsymbol{r}\|^{2}+C_{2}^{2},$

then for any $\boldsymbol{z}\in\mathbb{R}^{d}$ we have:

$\displaystyle\langle\boldsymbol{v},\boldsymbol{p}-\boldsymbol{z}\rangle\leq\|\boldsymbol{r}-\boldsymbol{z}\|^{2}-\|\boldsymbol{q}-\boldsymbol{z}\|^{2}-\left(\frac{1}{2}-\frac{C_{1}^{2}}{2}\right)\|\boldsymbol{r}-\boldsymbol{p}\|^{2}+\frac{C_{2}^{2}}{2}.$

######  Lemma B.14.

For EG (Algorithm 3), under Theorem 4.9’s assumptions, the following statement
holds for the generated sequence
$\\{\boldsymbol{y}_{t}\\},\\{\boldsymbol{y}_{t+\frac{1}{2}}\\}$ during
algorithm proceeding and any $\boldsymbol{y}\in\mathcal{Y}$:

$\displaystyle\|\boldsymbol{y}_{t+1}-\boldsymbol{y}\|^{2}$
$\displaystyle\leq\|\boldsymbol{y}_{t}-\boldsymbol{y}\|^{2}+2\eta_{y}\langle\boldsymbol{y}_{t+\frac{1}{2}}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})\rangle-\left(\frac{1}{2}-\frac{\eta_{y}^{2}\ell^{2}}{2}\right)\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t+\frac{1}{2}}\|^{2}$
$\displaystyle\quad+\frac{\eta_{x}^{2}\eta_{y}^{2}\ell^{2}G^{2}}{2}.$

###### Proof.

According to Proposition B.13, we set $\boldsymbol{r}=\boldsymbol{y}_{t}$,
$\boldsymbol{q}=\boldsymbol{y}_{t+1}$,
$\boldsymbol{p}=\boldsymbol{y}_{t+\frac{1}{2}}$ and
$\boldsymbol{v}=-\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})$,
$\boldsymbol{u}=-\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})$.
We can verify that:

$\displaystyle\|\boldsymbol{u}-\boldsymbol{v}\|^{2}$
$\displaystyle=\eta_{y}^{2}\|\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})-\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\|^{2}$
$\displaystyle\leq\eta_{y}^{2}(\ell^{2}\|\boldsymbol{y}_{t+\frac{1}{2}}-\boldsymbol{y}_{t}\|^{2}+\ell^{2}\|\boldsymbol{x}_{t+\frac{1}{2}}-\boldsymbol{x}_{t}\|^{2})$
$\displaystyle\leq\eta_{y}^{2}(\ell^{2}\|\boldsymbol{p}-\boldsymbol{r}\|^{2}+\ell^{2}\eta_{x}^{2}G^{2}),$

so if we set $C_{1}^{2}=\eta_{y}^{2}\ell^{2}$ and
$C_{2}^{2}=\eta_{x}^{2}\eta_{y}^{2}\ell^{2}G^{2}$, we have the following
inequality holding for any $\boldsymbol{y}\in\mathcal{Y}$:

$\displaystyle\langle-\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}}),\boldsymbol{y}_{t+\frac{1}{2}}-\boldsymbol{y}\rangle$
$\displaystyle\leq\|\boldsymbol{y}_{t}-\boldsymbol{y}\|^{2}-\|\boldsymbol{y}_{t+1}-\boldsymbol{y}\|^{2}-\left(\frac{1}{2}-\frac{\eta_{y}^{2}\ell^{2}}{2}\right)\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t+\frac{1}{2}}\|^{2}$
$\displaystyle\quad+\frac{\eta_{x}^{2}\eta_{y}^{2}\ell^{2}G^{2}}{2}.$

∎

######  Lemma B.15.

For EG (Algorithm 3), under Theorem 4.9’s assumptions, the following statement
holds for the generated sequence
$\\{\boldsymbol{x}_{t}\\},\\{\boldsymbol{y}_{t}\\},\\{\boldsymbol{x}_{t+\frac{1}{2}}\\},\\{\boldsymbol{y}_{t+\frac{1}{2}}\\}$
during algorithm proceeding:

$\displaystyle\Phi_{1/2\ell}(\boldsymbol{x}_{t+\frac{1}{2}})$
$\displaystyle\leq\Phi_{1/2\ell}({\boldsymbol{x}}_{t-\frac{1}{2}})+2\eta_{x}\ell\left(\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\right)-\frac{\eta_{x}}{8}\|\nabla\Phi_{1/2\ell}({\boldsymbol{x}}_{t-\frac{1}{2}})\|^{2}+3\ell\eta_{x}^{2}G^{2}$
$\displaystyle+\frac{\eta_{x}}{2}\|\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}.$

###### Proof.

Let
$\hat{\boldsymbol{x}}_{t-\frac{1}{2}}=\arg\min_{\boldsymbol{x}\in\mathbb{R}^{d}}\Phi(\boldsymbol{x})+\ell\|\boldsymbol{x}-\boldsymbol{x}_{t-\frac{1}{2}}\|^{2}$.
Notice that:

$\displaystyle\Phi_{1/2\ell}(\boldsymbol{x}_{t+\frac{1}{2}})$
$\displaystyle\leq\Phi_{1/2\ell}(\hat{\boldsymbol{x}}_{t-\frac{1}{2}})+\ell\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t+\frac{1}{2}}\|^{2}$
$\displaystyle\leq\Phi_{1/2\ell}(\hat{\boldsymbol{x}}_{t-\frac{1}{2}})+\ell\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t+\frac{1}{2}}\|^{2}$
$\displaystyle\quad+\ell(2\eta_{x}\langle\nabla_{x}f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})+(\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t}-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1}),\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\rangle+\eta_{x}^{2}G^{2})$
$\displaystyle=\Phi_{1/2\ell}(\hat{\boldsymbol{x}}_{t-\frac{1}{2}})+\ell(\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t+\frac{1}{2}}\|^{2}+2\eta_{x}\langle\nabla_{x}f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}}),\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\rangle)$
$\displaystyle\quad+2\ell\eta_{x}\langle\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1}),\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\rangle+\eta_{x}^{2}\ell
G^{2}$

According to smoothness of $f(\cdot,\boldsymbol{y})$, we have:

$\displaystyle\langle\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}},\nabla_{x}f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\rangle$
$\displaystyle\leq
f(\hat{\boldsymbol{x}}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})+\frac{\ell}{2}\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\|^{2}$
$\displaystyle\leq\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})-\frac{\ell}{2}\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\|^{2}.$

So we have

$\displaystyle\Phi_{1/2\ell}(\boldsymbol{x}_{t+\frac{1}{2}})$
$\displaystyle\leq\Phi_{1/2\ell}({\boldsymbol{x}}_{t-\frac{1}{2}})+\ell\|\boldsymbol{x}_{t-\frac{1}{2}}-\hat{\boldsymbol{x}}_{t-\frac{1}{2}}\|^{2}$
$\displaystyle\quad+2\eta_{x}\ell\left(\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})-\frac{\ell}{2}\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\|^{2}\right)+3\ell\eta_{x}^{2}G^{2}$
$\displaystyle+\eta_{x}\ell\left(\frac{1}{2\ell}\|\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}+\frac{\ell}{2}\|\boldsymbol{x}_{t-\frac{1}{2}}-\hat{\boldsymbol{x}}_{t-\frac{1}{2}}\|^{2}\right)$
$\displaystyle\leq\Phi_{1/2\ell}({\boldsymbol{x}}_{t-\frac{1}{2}})+2\eta_{x}\ell\left(\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\right)-\frac{\eta_{x}\ell^{2}}{2}\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\|^{2}+3\ell\eta_{x}^{2}G^{2}$
$\displaystyle+\frac{\eta_{x}}{2}\|\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}.$

∎

######  Lemma B.16.

For EG (Algorithm 3), under Theorem 4.9’s assumptions, the following statement
holds for the generated sequence
$\\{\boldsymbol{x}_{t}\\},\\{\boldsymbol{y}_{t}\\},\\{\boldsymbol{x}_{t+\frac{1}{2}}\\},\\{\boldsymbol{y}_{t+\frac{1}{2}}\\}$
during algorithm proceeding and $\forall s\leq t$:

$\displaystyle\Phi(\boldsymbol{x}_{t+\frac{1}{2}})-f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})$
$\displaystyle\leq 2(t-s+1)\eta_{x}G^{2}$
$\displaystyle\quad+\frac{1}{2\eta_{y}}\left(\|\boldsymbol{y}_{t}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}-\|\boldsymbol{y}_{t+1}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}+\frac{\eta_{x}^{2}G^{2}}{2}\right).$

###### Proof.

Observe that:

$\displaystyle\Phi(\boldsymbol{x}_{t+\frac{1}{2}})-f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})$
$\displaystyle\leq
f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}^{*}(\boldsymbol{x}_{t+\frac{1}{2}}))-f(\boldsymbol{x}_{s},\boldsymbol{y}^{*}(\boldsymbol{x}_{t+\frac{1}{2}}))+f(\boldsymbol{x}_{s},\boldsymbol{y}^{*}(\boldsymbol{x}_{s}))$
$\displaystyle\quad-f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}^{*}(\boldsymbol{x}_{s}))+f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}^{*}(\boldsymbol{x}_{s}))-f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})$
$\displaystyle\leq
2(t-s+1)\eta_{x}G^{2}-\langle\boldsymbol{y}_{t+\frac{1}{2}}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})\rangle$

Plugging in Lemma B.14 will conclude the proof:

$\displaystyle\Phi(\boldsymbol{x}_{t+\frac{1}{2}})-f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})$
$\displaystyle\leq 2(t-s+1)\eta_{x}G^{2}$
$\displaystyle\quad+\frac{1}{2\eta_{y}}\left(\|\boldsymbol{y}_{t}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}-\|\boldsymbol{y}_{t+1}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}+\frac{\eta_{x}^{2}G^{2}}{2}\right).$

∎

######  Lemma B.17.

For EG (Algorithm 3), under Theorem 4.9’s assumptions, the following statement
holds for the generated sequence
$\\{\boldsymbol{x}_{t}\\},\\{\boldsymbol{y}_{t}\\},\\{\boldsymbol{x}_{t+\frac{1}{2}}\\},\\{\boldsymbol{y}_{t+\frac{1}{2}}\\}$
during algorithm proceeding:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\leq\frac{1}{B}\left(2\eta_{x}B^{2}G^{2}+\frac{D^{2}}{2\eta_{y}}+\frac{B\eta_{x}^{2}G^{2}}{2}\right)$

###### Proof.

According to Lemma B.16:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})$
$\displaystyle=\frac{1}{T+1}\sum_{j=0}^{S}\sum_{t=kB}^{(k+1)B-1}\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})$
$\displaystyle\leq\frac{1}{T+1}\sum_{j=0}^{S}\left[2B^{2}\eta_{x}G^{2}+\frac{1}{2\eta_{y}}\left(\|\boldsymbol{y}_{kB}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}-\|\boldsymbol{y}_{(k+1)B-1}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}+\frac{\eta_{x}^{2}G^{2}}{2}\right)\right]$
$\displaystyle\leq\frac{1}{B}\left[2\eta_{x}B^{2}G^{2}+\frac{D^{2}}{2\eta_{y}}+\frac{B\eta_{x}^{2}G^{2}}{2}\right].$

∎

#####  B.2.2 Proof of Theorem 4.8 for EG

In this section we are going to provide the proof for Theorem 4.8, EG part,
the convergence rate of EG in deterministic setting. We first introduce the
formal version of Theorem 4.8, EG part here:

######  Theorem B.18 (EG Deterministic, formal).

Under Assumption 4.7, if we choose
$\eta_{x}=O\left(\min\left\\{\frac{\epsilon}{\ell G},\frac{\epsilon^{2}}{\ell
G^{2}},\frac{\epsilon^{4}}{D^{2}G^{2}\ell^{3}}\right\\}\right)$,
$\eta_{y}=\frac{1}{2\ell}$, then EG (Algorithm 3) guarantees to find
$\epsilon$-stationary point, i.e.,
$\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}\leq\epsilon^{2}$,
with the gradient complexity bounded by:

$\displaystyle O\left(\frac{\ell
G^{2}\hat{\Delta}_{\Phi}}{\epsilon^{4}}\max\left\\{1,\frac{D^{2}\ell^{2}}{\epsilon^{2}}\right\\}\right).$

###### Proof.

According to Lemma B.15:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t-\frac{1}{2}})\|^{2}$
$\displaystyle\leq\frac{\Phi_{1/2\ell}(\boldsymbol{x}_{-\frac{1}{2}})}{\eta_{x}(T+1)}+\frac{1}{T+1}\sum_{t=0}^{T}8\ell\left(\Phi({x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\right)+12\eta_{x}\ell
G^{2}$
$\displaystyle+8\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}.$

For
$\|\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}$,
notice that:

$\displaystyle\|\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}$
$\displaystyle\leq\ell^{2}\|\boldsymbol{x}_{t}-\boldsymbol{x}_{t-1}\|^{2}+\ell^{2}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}$
$\displaystyle\leq\eta_{x}^{2}\ell^{2}G^{2}+\eta_{y}^{2}\ell^{2}\|\nabla_{y}f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\|^{2}$
$\displaystyle\leq\eta_{x}^{2}\ell^{2}G^{2}+2\eta_{y}^{2}\ell^{3}\left(\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\right)$

So we have:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t-\frac{1}{2}})\|^{2}\leq\frac{\Phi_{1/2\ell}(\boldsymbol{x}_{-\frac{1}{2}})}{\eta_{x}(T+1)}$
$\displaystyle\qquad+\frac{1}{T+1}\sum_{t=0}^{T}(8\ell+2\eta_{y}^{2}\ell^{3})\left(\Phi({x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\right)+12\eta_{x}G^{2}+8\eta_{x}^{2}\ell^{2}G^{2}$

Now we plug in Lemma B.17:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t-\frac{1}{2}})\|^{2}\leq\frac{\Phi_{1/2\ell}(\boldsymbol{x}_{-\frac{1}{2}})-\Phi_{1/2\ell}(\boldsymbol{x}_{T-\frac{1}{2}})}{\eta_{x}(T+1)}$
$\displaystyle\qquad+{(8\ell+2\eta_{y}^{2}\ell^{3})}\left(2\eta_{x}BG^{2}+\frac{D^{2}}{2\eta_{y}B}+\frac{\eta_{x}^{2}G^{2}}{2}\right)+12\ell\eta_{x}G^{2}+8\eta_{x}^{2}\ell^{2}G^{2}$

Choose
$B=O\left(\frac{D}{G\sqrt{\eta_{x}\eta_{y}}}\right),\eta_{x}=O\left(\min\left\\{\frac{\epsilon}{\ell
G},\frac{\epsilon^{2}}{\ell
G^{2}},\frac{\epsilon^{4}}{D^{2}G^{2}\ell^{3}}\right\\}\right)$,
$\eta_{y}=\frac{1}{2\ell}$, and then we guarantee that
$\frac{1}{T+1}\sum_{t=0}^{T}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t-\frac{1}{2}})\|^{2}\leq\epsilon^{2}$
with the gradient complexity is bounded by:

$\displaystyle O\left(\frac{\ell
G^{2}\hat{\Delta}_{\Phi}}{\epsilon^{4}}\max\left\\{1,\frac{D^{2}\ell^{2}}{\epsilon^{2}}\right\\}\right).$

∎

Stochastic setting.

In this part, we are going to present proof of EG in stochastic setting. First
let us introduce some useful lemmas.

#####  B.2.3 Useful Lemmas

######  Lemma B.19.

For Stochastic EG (Algorithm 3), under Theorem 4.9’s assumptions, the
following statement holds for the generated sequence
$\\{\boldsymbol{y}_{t}\\},\\{\boldsymbol{y}_{t+\frac{1}{2}}\\}$ during
algorithm proceeding and any $\boldsymbol{y}\in\mathcal{Y}$:

$\displaystyle\|\boldsymbol{y}_{t+1}-\boldsymbol{y}\|^{2}$
$\displaystyle\leq\|\boldsymbol{y}_{t}-\boldsymbol{y}\|^{2}+2\eta_{y}\langle\boldsymbol{y}_{t+\frac{1}{2}}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})\rangle-\left(\frac{1}{2}-\frac{3\eta_{x}^{2}L^{2}}{2}\right)\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t+\frac{1}{2}}\|^{2}$
$\displaystyle\quad+\frac{1}{2}(3\eta_{x}^{2}\eta_{y}^{2}\ell^{2}(G^{2}+\sigma^{2})+6\eta_{y}^{2}\sigma^{2}).$

###### Proof.

According to Proposition B.13, we set $\boldsymbol{r}=\boldsymbol{y}_{t}$,
$\boldsymbol{q}=\boldsymbol{y}_{t+1}$,
$\boldsymbol{p}=\boldsymbol{y}_{t+\frac{1}{2}}$ and
$\boldsymbol{v}=-\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}};\xi)$,
$\boldsymbol{u}=-\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t};\xi)$.
We can verify that:

$\displaystyle\|\boldsymbol{u}-\boldsymbol{v}\|^{2}=\eta_{y}^{2}\|\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}};\xi)-\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t};\xi)\|^{2}$
$\displaystyle\leq
3\eta_{y}^{2}\|\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})-\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\|^{2}+3\eta_{y}^{2}\|\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}};\xi)-\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})\|^{2}$
$\displaystyle\quad+3\eta_{y}^{2}\|\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t};\xi)-\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\|^{2}$
$\displaystyle\leq
3(\ell^{2}\|\boldsymbol{y}_{t+\frac{1}{2}}-\boldsymbol{y}_{t}\|^{2}+\ell^{2}\|\boldsymbol{x}_{t+\frac{1}{2}}-\boldsymbol{x}_{t}\|^{2})+3\eta_{y}^{2}Var(\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t};\xi))$
$\displaystyle\quad+3\eta_{y}^{2}Var(\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}};\xi))$
$\displaystyle\leq
3\eta_{y}^{2}(\ell^{2}\|\boldsymbol{y}_{t+\frac{1}{2}}-\boldsymbol{y}_{t}\|^{2}+\eta_{x}^{2}\ell^{2}(G^{2}+\sigma^{2}))+3\eta_{y}^{2}Var(\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t};\xi))$
$\displaystyle\quad+3\eta_{y}^{2}Var(\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}};\xi))$

so if we set $C_{1}^{2}=3\eta_{y}^{2}\ell^{2}$ and
$C_{2}^{2}=3\eta_{x}^{2}\eta_{y}^{2}\ell^{2}(G^{2}+\sigma^{2})+3\eta_{y}^{2}Var(\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t};\xi))+3\eta_{y}^{2}Var(\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}};\xi))$,
we have the following inequality holding for any
$\boldsymbol{y}\in\mathcal{Y}$:

$\displaystyle\langle-\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}};\xi),\boldsymbol{y}_{t+\frac{1}{2}}-\boldsymbol{y}\rangle$
$\displaystyle\leq\|\boldsymbol{y}_{t}-\boldsymbol{y}\|^{2}-\|\boldsymbol{y}_{t+1}-\boldsymbol{y}\|^{2}$
$\displaystyle\quad-\left(\frac{1}{2}-\frac{C_{1}^{2}}{2}\right)\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t+\frac{1}{2}}\|^{2}+\frac{C_{2}^{2}}{2}.$

Taking expectation on both sides yields:

$\displaystyle\langle-\eta_{y}\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}}),\boldsymbol{y}_{t+\frac{1}{2}}-\boldsymbol{y}\rangle\leq\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}\|^{2}-\mathbb{E}\|\boldsymbol{y}_{t+1}-\boldsymbol{y}\|^{2}$
$\displaystyle\qquad-\left(\frac{1}{2}-\frac{3\eta_{y}^{2}\ell^{2}}{2}\right)\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t+\frac{1}{2}}\|^{2}+\frac{1}{2}(3\eta_{x}^{2}\eta_{y}^{2}\ell^{2}(G^{2}+\sigma^{2})+6\eta_{y}^{2}\sigma^{2}).$

∎

######  Lemma B.20.

For Stochastic EG (Algorithm 3), under Theorem 4.9’s assumptions, the
following statement holds for the generated sequence
$\\{\boldsymbol{x}_{t}\\},\\{\boldsymbol{y}_{t}\\},\\{\boldsymbol{x}_{t+\frac{1}{2}}\\},\\{\boldsymbol{y}_{t+\frac{1}{2}}\\}$
during algorithm proceeding:

$\displaystyle\mathbb{E}[\Phi_{1/2\ell}(\boldsymbol{x}_{t+\frac{1}{2}})]$
$\displaystyle\leq\mathbb{E}[\Phi_{1/2\ell}(\boldsymbol{x}_{t-\frac{1}{2}})]+2\eta\ell\mathbb{E}[\Phi({x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})]-\frac{\eta_{x}}{8}\mathbb{E}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t-\frac{1}{2}})\|^{2}$
$\displaystyle\quad+3\eta_{x}^{2}\ell(G^{2}+\sigma^{2})+2\eta_{x}\mathbb{E}\|\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}.$

###### Proof.

Let
$\hat{\boldsymbol{x}}_{t-\frac{1}{2}}=\arg\min_{\boldsymbol{x}\in\mathbb{R}^{d}}\Phi(\boldsymbol{x})+\ell\|\boldsymbol{x}-\boldsymbol{x}_{t-\frac{1}{2}}\|^{2}$.
Notice that:

$\displaystyle\mathbb{E}[\Phi_{1/2\ell}(\boldsymbol{x}_{t+\frac{1}{2}})]\leq\mathbb{E}[\Phi(\hat{\boldsymbol{x}}_{t-\frac{1}{2}})]+\ell\mathbb{E}\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t+\frac{1}{2}}\|^{2}$
$\displaystyle\leq\Phi_{1/2\ell}(\hat{\boldsymbol{x}}_{t-\frac{1}{2}})+3\eta_{x}^{2}\ell(\sigma^{2}+G^{2})+\ell\mathbb{E}\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t+\frac{1}{2}}\|^{2}$
$\displaystyle\quad+2\eta_{x}\ell\mathbb{E}\langle\nabla_{x}f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})+\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1}),\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\rangle)$
$\displaystyle=\mathbb{E}[\Phi(\hat{\boldsymbol{x}}_{t-\frac{1}{2}})]+\ell(\mathbb{E}\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t+\frac{1}{2}}\|^{2}+2\eta_{x}\mathbb{E}\langle\nabla_{x}f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}}),\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\rangle)$
$\displaystyle\quad+2\ell\eta_{x}\mathbb{E}\langle\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1}),\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\rangle+3\eta_{x}^{2}\ell(\sigma^{2}+G^{2})$

According to smoothness of $f(\cdot,\boldsymbol{y})$, we have:

$\displaystyle\langle\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}},\nabla_{x}f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\rangle$
$\displaystyle\leq
f(\hat{\boldsymbol{x}}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})+\frac{\ell}{2}\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\|^{2}$
$\displaystyle\leq\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})-\frac{\ell}{2}\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\|^{2}.$

So we have:

$\displaystyle\mathbb{E}[\Phi_{1/2\ell}(\boldsymbol{x}_{t+\frac{1}{2}})]\leq\mathbb{E}[\Phi(\hat{\boldsymbol{x}}_{t-\frac{1}{2}})]+\ell\mathbb{E}\|\boldsymbol{x}_{t-\frac{1}{2}}-\hat{\boldsymbol{x}}_{t-\frac{1}{2}}\|^{2}$
$\displaystyle\quad+2\eta_{x}\ell\mathbb{E}\left(\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})-\frac{\ell}{2}\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\|^{2}\right)+3\eta_{x}^{2}\ell(G^{2}+\sigma^{2})$
$\displaystyle\quad+\eta_{x}\ell\left(\frac{1}{2\ell}\mathbb{E}\|\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}+\frac{\ell}{2}\mathbb{E}\|\boldsymbol{x}_{t-\frac{1}{2}}-\hat{\boldsymbol{x}}_{t-\frac{1}{2}}\|^{2}\right)$
$\displaystyle\leq\mathbb{E}[\Phi_{1/2\ell}({\boldsymbol{x}}_{t-\frac{1}{2}})]+2\eta_{x}\ell\left(\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\right)-\frac{\eta_{x}\ell^{2}}{2}\mathbb{E}\|\hat{\boldsymbol{x}}_{t-\frac{1}{2}}-\boldsymbol{x}_{t-\frac{1}{2}}\|^{2}$
$\displaystyle\quad+3\eta_{x}^{2}\ell(G^{2}+\sigma^{2})+\frac{\eta_{x}}{2}\mathbb{E}\|\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}.$

Using the fact that
$\|\boldsymbol{x}_{t-\frac{1}{2}}-\hat{\boldsymbol{x}}_{t-\frac{1}{2}}\|=\frac{1}{2\ell}\|\nabla\Phi_{1/2\ell}({\boldsymbol{x}}_{t-\frac{1}{2}})\|$
will conclude the proof.

∎

######  Lemma B.21.

For Stochastic EG (Algorithm 3), under Theorem 4.9’s assumptions, the
following statement holds for the generated sequence
$\\{\boldsymbol{x}_{t}\\},\\{\boldsymbol{y}_{t}\\},\\{\boldsymbol{x}_{t+\frac{1}{2}}\\},\\{\boldsymbol{y}_{t+\frac{1}{2}}\\}$
during algorithm proceeding and $\forall s\leq t$:

$\displaystyle\Phi(\boldsymbol{x}_{t+\frac{1}{2}})-f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})\leq
2(t-s+1)\eta_{x}G^{2}$
$\displaystyle\qquad+\frac{1}{2\eta_{y}}\left(\|\boldsymbol{y}_{t}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}-\|\boldsymbol{y}_{t+1}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}+\frac{1}{2}(3\eta_{x}^{2}\eta_{y}^{2}\ell^{2}(G^{2}+\sigma^{2})+6\eta_{y}^{2}\sigma^{2})\right).$

###### Proof.

According to Lemma B.21:

$\displaystyle\Phi(\boldsymbol{x}_{t+\frac{1}{2}})-f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})$
$\displaystyle\leq
f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}^{*}(\boldsymbol{x}_{t+\frac{1}{2}}))-f(\boldsymbol{x}_{s},\boldsymbol{y}^{*}(\boldsymbol{x}_{t+\frac{1}{2}}))+f(\boldsymbol{x}_{s},\boldsymbol{y}^{*}(\boldsymbol{x}_{s}))$
$\displaystyle\quad-f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}^{*}(\boldsymbol{x}_{s}))+f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}^{*}(\boldsymbol{x}_{s}))-f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})$
$\displaystyle\leq
2(t-s+1)\eta_{x}G^{2}-\langle\boldsymbol{y}_{t+\frac{1}{2}}-\boldsymbol{y},\nabla_{y}f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})\rangle$

Plugging in Lemma B.19 will conclude the proof:

$\displaystyle\Phi(\boldsymbol{x}_{t+\frac{1}{2}})-f(\boldsymbol{x}_{t+\frac{1}{2}},\boldsymbol{y}_{t+\frac{1}{2}})\leq
2(t-s+1)\eta_{x}G^{2}$
$\displaystyle\quad+\frac{1}{2\eta_{y}}\left(\|\boldsymbol{y}_{t}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}-\|\boldsymbol{y}_{t+1}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}+\frac{1}{2}(3\eta_{x}^{2}\eta_{y}^{2}\ell^{2}(G^{2}+\sigma^{2})+6\eta_{y}^{2}\sigma^{2})\right).$

∎

######  Lemma B.22.

For Stochastic EG (Algorithm 3), under Theorem 4.9’s assumptions, the
following statement holds for the generated sequence
$\\{\boldsymbol{x}_{t}\\},\\{\boldsymbol{y}_{t}\\},\\{\boldsymbol{x}_{t+\frac{1}{2}}\\},\\{\boldsymbol{y}_{t+\frac{1}{2}}\\}$
during algorithm proceeding:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\leq\frac{1}{B}\left(2\eta_{x}B^{2}G^{2}+\frac{D^{2}}{2\eta_{y}}+\frac{B\eta_{x}^{2}G^{2}}{2}\right).$

###### Proof.

Summing over $t=0$ to $T$ on both side of Lemma B.21 yields:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})$
$\displaystyle=\frac{1}{T+1}\sum_{j=0}^{S}\sum_{t=kB}^{(k+1)B-1}\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})$
$\displaystyle\leq\frac{1}{T+1}\sum_{j=0}^{S}\left[2B^{2}\eta_{x}G^{2}+\frac{1}{2\eta_{y}}\left(\|\boldsymbol{y}_{kB}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}-\|\boldsymbol{y}_{(k+1)B-1}-\boldsymbol{y}^{*}(\boldsymbol{x}_{s})\|^{2}\right.\right.$
$\displaystyle\left.\left.\quad+\frac{1}{2}(3\eta_{x}^{2}\eta_{y}^{2}\ell^{2}(G^{2}+\sigma^{2})+6\eta_{y}^{2}\sigma^{2})\right)\right]$
$\displaystyle\leq\frac{1}{B}\left(2\eta_{x}B^{2}G^{2}+\frac{D^{2}}{2\eta_{y}}+\frac{1}{2}(3\eta_{x}^{2}\eta_{y}^{2}\ell^{2}(G^{2}+\sigma^{2})+6\eta_{y}^{2}\sigma^{2})\right),$

which concludes the proof. ∎

#####  B.2.4 Proof of Theorem 4.9 for EG

In this section we provide the proof for Theorem 4.9 on the convergence rate
of EG in stochastic setting. We first introduce the formal version of theorem
here:

######  Theorem B.23 (EG Stochastic, formal).

Under Assumption 4.3, and 4.7, if we choose
$\eta_{x}=O(\min\\{\frac{\epsilon^{2}}{\ell(G^{2}+\sigma^{2})},\frac{\epsilon^{4}}{D^{2}\ell^{3}G\sqrt{G^{2}+\sigma^{2}}},\frac{\epsilon^{6}}{D^{2}\ell^{3}\sigma^{2}G\sqrt{G^{2}+\sigma^{2}}}\\})$,
$\eta_{y}=O(\min\\{\frac{1}{2\ell},\frac{\epsilon^{2}}{\ell\sigma^{2}}\\})$,
then Stochastic EG (Algorithm 3) guarantees to find $\epsilon$-stationary
point, i.e.,
$\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}\leq\epsilon^{2}$,
with the gradient complexity bounded by:

$\displaystyle
O\left(\frac{D^{2}\ell^{3}G\sqrt{G^{2}+\sigma^{2}}}{\epsilon^{6}}\max\left\\{1,\frac{\sigma^{2}}{\epsilon^{2}}\right\\}\right).$

###### Proof.

According to Lemma B.20:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t-\frac{1}{2}})\|^{2}\leq\frac{\mathbb{E}[\Phi_{1/2\ell}(\boldsymbol{x}_{-\frac{1}{2}})-\Phi_{1/2\ell}(\boldsymbol{x}_{T+\frac{1}{2}})]}{T}$
$\displaystyle\qquad+16\ell\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}[\Phi({x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})]+24\eta_{x}\ell(G^{2}+\sigma^{2})$
$\displaystyle\qquad+16\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}\|\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}.$

Observe that:

$\displaystyle\mathbb{E}\|\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}$
$\displaystyle\leq\ell^{2}\mathbb{E}\|(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}$
$\displaystyle=\ell^{2}\mathbb{E}\|\boldsymbol{x}_{t}-\boldsymbol{x}_{t-1}\|^{2}+\ell^{2}\mathbb{E}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}$
$\displaystyle\leq\ell^{2}\eta_{x}^{2}(G^{2}+\sigma^{2})+\ell^{2}\eta_{y}^{2}\mathbb{E}\left\|\nabla_{y}f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\right\|^{2}$
$\displaystyle\leq\ell^{2}\eta_{x}^{2}(G^{2}+\sigma^{2})+\ell^{2}\eta_{y}^{2}\mathbb{E}\left[\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\right].$

So we have:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t-\frac{1}{2}})\|^{2}\leq\frac{\mathbb{E}[\Phi_{1/2\ell}(\boldsymbol{x}_{-\frac{1}{2}})-\Phi_{1/2\ell}(\boldsymbol{x}_{T+\frac{1}{2}})]}{T+1}$
$\displaystyle\qquad+16\ell\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}[\Phi({x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})]+24\eta_{x}\ell(G^{2}+\sigma^{2})$
$\displaystyle\qquad+16\ell^{2}\eta_{y}^{2}\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}\left[\Phi(\boldsymbol{x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})\right]+16\ell^{2}\eta_{x}^{2}(G^{2}+\sigma^{2})$
$\displaystyle\quad\leq\frac{\mathbb{E}[\Phi_{1/2\ell}(\boldsymbol{x}_{-\frac{1}{2}})-\Phi_{1/2\ell}(\boldsymbol{x}_{T+\frac{1}{2}})]}{T+1}+16(\ell+\ell^{2}\eta_{y}^{2})\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}[\Phi({x}_{t-\frac{1}{2}})-f(\boldsymbol{x}_{t-\frac{1}{2}},\boldsymbol{y}_{t-\frac{1}{2}})]$
$\displaystyle\qquad+16\ell^{2}\eta_{x}^{2}(G^{2}+\sigma^{2})+24\eta_{x}\ell(G^{2}+\sigma^{2})$

Plugging in Lemma B.22 yields:

$\displaystyle\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t-\frac{1}{2}})\|^{2}$
$\displaystyle\leq\frac{\mathbb{E}[\Phi_{1/2\ell}(\boldsymbol{x}_{-\frac{1}{2}})-\Phi_{1/2\ell}(\boldsymbol{x}_{T+\frac{1}{2}})]}{T+1}$
$\displaystyle\quad+16(\ell+\ell^{2}\eta_{y}^{2})\frac{1}{B}\left(2\eta_{x}B^{2}G^{2}+\frac{D^{2}}{2\eta_{y}}+\frac{B\eta_{x}^{2}G^{2}}{2}\right)$
$\displaystyle\quad+16\ell^{2}\eta_{x}^{2}(G^{2}+\sigma^{2})+24\eta_{x}\ell(G^{2}+\sigma^{2}).$

Choosing $B=O(\frac{D}{\sqrt{\eta_{x}\eta_{y}G\sqrt{G^{2}+\sigma^{2}}}})$,
$\eta_{x}=O(\min\\{\frac{\epsilon^{2}}{\ell(G^{2}+\sigma^{2})},\frac{\epsilon^{4}}{D^{2}\ell^{3}G\sqrt{G^{2}+\sigma^{2}}},\frac{\epsilon^{6}}{D^{2}\ell^{3}\sigma^{2}G\sqrt{G^{2}+\sigma^{2}}}\\})$,
$\eta_{y}=O(\min\\{\frac{1}{\ell},\frac{\epsilon^{2}}{\ell\sigma^{2}}\\})$,
guarantees that
$\frac{1}{T+1}\sum_{t=0}^{T}\mathbb{E}\|\nabla\Phi_{1/2\ell}(\boldsymbol{x}_{t})\|^{2}\leq\epsilon^{2}$
holds with the gradient complexity is bounded by:

$\displaystyle
O\left(\frac{D^{2}\ell^{3}G\sqrt{G^{2}+\sigma^{2}}\hat{\Delta}_{\Phi}}{\epsilon^{6}}\max\left\\{1,\frac{\sigma^{2}}{\epsilon^{2}}\right\\}\right).$

which completes the proof. ∎

####  B.3 Tightness Analysis

In this section, we provide our tightness analysis showing our obtained upper
bound is tight given our choice of learning rates. In subsection B.3.1, we
introduce our hard example, and show the lower bound on convergence of this
example, and then in subsection B.3.2, we extend the tightness result to
EG/OGDA using the same hard example.

#####  B.3.1 GDA

###### Proof of Theorem 4.10.

Let $L\geq 0$ be some constants to be chosen later. Inspired by [11], we
consider the following function $f:\mathbb{R}\times[-D,D]\to\mathbb{R}$:

$\displaystyle f(x,y)=h(x)y$

where

$\displaystyle h(x)=\begin{cases}\frac{L}{2}x^{2}&|x|\leq 1\\\
L-\frac{L}{2}(|x|-2)^{2}&1\leq|x|\leq 2\\\ L&|x|\geq 2.\end{cases}$

It is easy to verify that $f$ is nonconvex, $2LD$ smooth, and $LD$-Lipschitz.
We choose $L=\frac{1}{D}\min\\{\ell/2,G\\}$ to guarantee that $f$ is $\ell$
smooth and $G$-Lipschitz with respect to $x$. The primal function is
$\Phi(x)=Dh(x)$ attained when $y=D$. After standard calculations, we know that
when $|x|\leq 1$, the Moreau envelope $\Phi_{1/2\ell}(x)$ satisfies

$\displaystyle\Phi_{1/2\ell}(x)=\frac{LD\ell}{LD+2\ell}x^{2},\quad|x|\leq 1.$

By definition, we also know $\Phi_{1/2\ell}(x)\geq 0$ for any
$x\in\mathbb{R}$.

We first claim that if we choose $|x_{0}|\leq 1$, $y_{0}\geq 0$, we have for
any $t\geq 0$, $|x_{t}|\leq 1$ and $y_{t}\geq 0$. We verify this claim by
induction. First note that when $t=0$, the claim holds for sure. Let us assume
it holds for $t=k$. Then for $t=k+1$,

$\displaystyle x_{k+1}=x_{k}-\eta_{x}Lx_{k}y_{k}=(1-\eta_{x}Ly_{k})x_{k}.$

Since $0\leq y_{k}\leq D$, we have $0\leq 1-\eta_{x}Ly_{k}\leq 1$. Therefore
$|x_{k+1}|\leq 1$. For $y_{k+1}$, we have

$\displaystyle y_{k+1}=\mathcal{P}_{[-D,D]}(y_{k}+\eta_{y}h(x_{k})).$

Since $h(x_{k})\geq 0$, we know that $y_{k+1}\geq 0$, which verifies the
claim.

We can also bound

$\displaystyle|x_{T}|=\left|\prod_{t=0}^{T-1}(1-\eta_{x}Ly_{t})x_{0}\right|\geq(1-\eta_{x}LD)^{T}|x_{0}|.$

Since $\nabla\Phi_{1/2\ell}(x)=\frac{2LD\ell}{LD+2\ell}x$, choosing
$x_{0}=\frac{LD+2\ell}{LD\ell}\epsilon$, we have
$\epsilon\geq|\nabla\Phi_{1/2\ell}(x_{T})|\geq 2\epsilon(1-\eta_{x}LD)^{T}$.
Also noting $\hat{\Delta}_{\Phi}=\frac{LD+2\ell}{LD\ell}\epsilon^{2}$, we have

$\displaystyle T=\Omega\left(\frac{1}{\eta_{x}LD}\right)$
$\displaystyle=\Omega\left(\frac{\hat{\Delta}_{\Phi}}{\eta_{x}LD\epsilon^{2}}\cdot\frac{LD\ell}{LD+2\ell}\right)$
$\displaystyle=\Omega\left(\frac{\ell^{3}G^{2}D^{2}\hat{\Delta}_{\Phi}}{\epsilon^{6}}\right).$

∎

#####  B.3.2 EG/OGDA

###### Proof of Theorem 4.11 for OGDA.

We use the same hard example $f(x,y)=h(x)y$ as in proof of Theorem 4.10.
Similarly, we first claim that if we choose $0\leq x_{0}\leq 1$ and $y_{0}=D$,
the following statements hold for any $t\geq 0$:

$\displaystyle(a)\ 0\leq x_{t}\leq 1,\text{and}\ x_{t}\geq
x_{t-1}/\sqrt{2},(b)\ y_{t}=D,$

where we define $x_{-1}=x_{0}$ and $y_{-1}=y_{0}$.

Now we prove the above claim by induction. First, when $t=0$, the claim holds
for sure. Then, let us assume it holds for $t\leq k$. Then for $t=k+1$, we
have

$\displaystyle x_{k+1}$
$\displaystyle=x_{k}-2\eta_{x}LDx_{k}y_{k}+\eta_{x}LDx_{k-1}y_{k-1}$
$\displaystyle=(1-2\eta_{x}LD)x_{k}+\eta_{x}LDx_{k-1}.$

Since $0\leq x_{k},x_{k-1}\leq 1$ and $0\leq\eta_{x}LD\leq 0.1$, we have

$\displaystyle(1-2\eta_{x}LD)x_{k}\leq
x_{k+1}\leq(1-\eta_{x}LD)x_{k}+\eta_{x}LDx_{k-1},$

which implies $0\leq x_{k}/\sqrt{2}\leq 0.8x_{k}\leq x_{k+1}\leq 1$. For
$y_{k+1}$, we know

$\displaystyle
y_{k+1}=\mathcal{P}_{[-D,D]}(y_{k}+2\eta_{y}h(x_{k})-\eta_{y}h(x_{k-1})).$

Since $h(x)=\frac{L}{2}x^{2}$ when $|x|\leq 1$, and
$x_{k}\geq\frac{1}{\sqrt{2}}x_{k-1}$, we know that
$2\eta_{y}h(x_{k})-\eta_{y}h(x_{k-1})\geq 0$ so $y_{k+1}=1$. Till now, we have
proved the claim.

Then, we are going to bound the magnitude of $x_{T}$. According to the
updating rule we have:

$\displaystyle x_{t+1}$
$\displaystyle=x_{t}-2\eta_{x}LDx_{t}+\eta_{x}LDx_{t-1}.$

Solving the above recursion we get the solution for $x_{t}$ as follows:

$\displaystyle x_{t}$
$\displaystyle=\left(\frac{1}{2}+\frac{1}{2\sqrt{\Delta}}\right)\left(\frac{1-2\eta_{x}LD+\sqrt{\Delta}}{2}\right)^{t}x_{0}$
$\displaystyle\quad+\left(\frac{1}{2}-\frac{1}{2\sqrt{\Delta}}\right)\left(\frac{1-2\eta_{x}LD-\sqrt{\Delta}}{2}\right)^{t}x_{0},$

where $\Delta=(1-2\eta_{x}LD)^{2}+4\eta_{x}LD$.

Let $a_{1}=\left(\frac{1}{2}+\frac{1}{2\sqrt{\Delta}}\right)$,
$a_{2}=\left(\frac{1}{2}-\frac{1}{2\sqrt{\Delta}}\right)$, and
$\lambda_{1}=\left(\frac{1-2\eta_{x}LD+\sqrt{\Delta}}{2}\right)$,
$\lambda_{2}=\left(\frac{1-2\eta_{x}LD-\sqrt{\Delta}}{2}\right)$. We observe
the following facts:

$\displaystyle a_{1}\geq\frac{1}{2},a_{2}\leq\eta_{x}^{2}L^{2}D^{2},$
$\displaystyle 1-\eta_{x}LD\leq\lambda_{1}\leq
1,-\eta_{x}LD\leq\lambda_{2}\leq 0.$

Now, we can bound the magnitude of $x_{T}$

$\displaystyle|x_{T}|=\left|a_{1}\lambda_{1}^{T}+a_{2}\lambda_{2}^{T}\right|x_{0}$
$\displaystyle\geq\left||a_{1}\lambda_{1}^{T}|-|a_{2}\lambda_{2}^{T}|\right|x_{0}$
$\displaystyle\geq\left(\frac{1}{2}(1-2\eta_{x}LD)^{T}-(\eta_{x}LD)^{T+2}\right)x_{0}.$

Since $\nabla\Phi_{1/2\ell}(x)=\frac{2LD\ell}{LD+2\ell}x$, by choosing
$x_{0}=\frac{LD+2\ell}{LD\ell}\cdot 4\epsilon$, we have

$\displaystyle\epsilon$ $\displaystyle\geq|\nabla\Phi_{1/2\ell}(x_{T})|\geq
8\epsilon\left(\frac{1}{2}(1-2\eta_{x}LD)^{T}-\frac{1}{4}\right),$

which yields $(1-2\eta_{x}LD)^{T}\leq 3/4$. The rest of proof is similar to
that of Theorem 4.10. ∎

###### Proof of Theorem 4.11 for EG.

We use the same hard example $f(x,y)=h(x)y$ as in proof of Theorem 4.10.
Similarly to our previous proofs for GDA and OGDA, we first claim that if we
choose $0\leq x_{0}\leq 1$ and $y_{0}=D$, the following statements hold for
any $t\geq 0$:

$\displaystyle(a)\ 0\leq x_{t}\leq 1;(b)\ y_{t}=D,y_{t+1/2}=D.$

We prove this claim by induction. First, when $t=0$, the claim holds for sure.
Then, let us assume it holds for $t\leq k$. Then for $t=k+1$, we have

$\displaystyle x_{k+1}$ $\displaystyle=x_{k}-\eta_{x}Ly_{k+1/2}x_{k+1/2}$
$\displaystyle=x_{k}-\eta_{x}Ly_{k+1/2}\left(1-\eta_{x}Ly_{k}\right)x_{k}$
$\displaystyle=(1-\eta_{x}LD+\eta_{x}^{2}L^{2}D^{2})x_{k}.$

Note that since $0\leq\eta_{x}LD\leq 1/2$, we know

$\displaystyle 0\leq 1-\eta_{x}LD+\eta_{x}^{2}L^{2}D^{2}\leq 1,$

which implies $0\leq x_{k+1}\leq 1$. Regarding $y$, note that

$\displaystyle y_{k+1}$
$\displaystyle=\mathcal{P}_{[-D,D]}(y_{k}+\eta_{y}h(x_{k+1/2}))),$
$\displaystyle y_{k+3/2}$
$\displaystyle=\mathcal{P}_{[-D,D]}(y_{k+1}+\eta_{y}h(x_{k+1}))).$

As $h(x_{k+1/2}),h(x_{k+1})\geq 0$ and $y_{k}=D$, we have
$y_{k+1}=y_{k+3/2}=D$. Till now, we have verified the claim.

Note that

$\displaystyle x_{k+1}=$
$\displaystyle(1-\eta_{x}LD+\eta_{x}^{2}L^{2}D^{2})x_{k}\geq(1-\eta_{x}LD)x_{k}.$

Hence we can unroll the recursion and lower bound the magnitude of
$\nabla\Phi_{1/2\ell}(x_{T})$, which is similar to the proof of Theorem 4.10.
∎

###  Appendix C Proof of Stepsize-Independent Lower Bound Results in
Nonconvex-Strongly-Concave Setting

In this section, we prove general lower bounds on the convergence rate of
GDA/EG/OGDA for the NC-SC setting. In subsection C.1, proof of theorem 5.1 is
established giving the lower bound for GDA in NC-SC, and in subsection C.2,
the proof of Theorem 5.2 is established, proving the lower bound of EG/OGDA
for NC-SC problems.

####  C.1 Lower Bound for GDA

######  Theorem C.1 (Theorem 5.1 restated).

For GDA algorithm, given $\eta_{y}=\Theta(1/\ell)$, for any $\eta_{x}$, there
exists a $\ell$-smooth function that is nonconvex in $x$ and $\mu$-strongly-
concave in y, such that for $\|\Phi(x_{T})\|\leq\epsilon$, we must have:

$\displaystyle
T=\Omega\left(\frac{\kappa\ell\Delta_{\phi}}{\epsilon^{2}}\right)$

###### Proof.

Combining Proposition C.2 and C.3 will conclude the proof. Proposition C.3
shows that when $\eta_{x}\in(\frac{1}{\kappa\ell}.\infty)$, GDA diverges, and
Proposition C.2 shows the lower bound on the convergence rate when
$\eta_{x}\in(0,\frac{1}{\kappa\ell}]$. ∎

######  Proposition C.2.

For GDA algorithm, given $\eta_{y}=\Theta(1/\ell)$, for any
$\eta_{x}\in(0,\frac{1}{\kappa\ell}]$, there exists a $\ell$-smooth function
that is nonconvex in $x$ and $\mu$-strongly-concave in y, such that for
$\|\Phi(x_{T})\|\leq\epsilon$, we must have:

$\displaystyle
T=\Omega\left(\frac{\kappa\ell\Delta_{\phi}}{\epsilon^{2}}\right)$

###### Proof.

Recall that we consider the following quadratic NC-SC function
$f:\mathbb{R}\times\mathbb{R}\to\mathbb{R}$

$\displaystyle f(x,y):=-\tfrac{1}{2}\ell x^{2}+bxy-\tfrac{1}{2}\mu y^{2}.$

Recall that $f$ is nonconvex in $x$ (it is actually concave in $x$) and $\mu$
strongly concave in $y$. Assume $\kappa:=\ell/\mu\geq 4$ and choose
$b=\sqrt{\mu(\ell+\mu_{x})}$ for some $0<\mu_{x}\leq\ell/2$ to be chosen
later. Then we know $b\leq\ell/2$, and it is easy to verify $f$ is $\ell$
smooth. Note that the primal function

$\displaystyle\Phi(x)=\max_{y}f(x,y)=\tfrac{1}{2}\mu_{x}x^{2}$

is actually strongly convex. This also justifies the symbol for $\mu_{x}$. We
use GDA to find the solution for $\min_{x}\max_{y}f(x,y)$. Actually, for this
problem, the optimal solution is achieved at the origin. The stepsizes ratio
is chosen as $r=\frac{\eta_{y}}{\eta_{x}}$ and $\eta_{y}=\frac{1}{\ell}$ for
some numerical constants $c$. Then the GDA update rule can be written as

$\displaystyle\begin{pmatrix}x_{k+1}\\\
y_{k+1}\end{pmatrix}=(\mathbf{I}+\eta_{x}\mathbf{M})\cdot\begin{pmatrix}x_{k}\\\
y_{k}\end{pmatrix},$ (85)

where

$\displaystyle\mathbf{M}:=\begin{pmatrix}\ell&-b\\\ rb&-\mu r\end{pmatrix}.$
(86)

Note that (85) is a linear time-invariant system. We need to analyze its
eigenvalues. Let $\lambda_{1}$ and $\lambda_{2}$ be the two eigenvalues of
$\mathbf{M}$, we have

$\displaystyle\lambda_{1,2}=-\frac{1}{2}\left(\mu
r-\ell\right)\pm\frac{1}{2}\sqrt{\left(\mu r-\ell\right)^{2}-4r\mu\mu_{x}}.$

Note that if we choose $\mu_{x}<\ell/8$, plugging into $r=c\kappa$, we can
bound

$\displaystyle 0\geq\lambda_{1}$
$\displaystyle=-\frac{(2\kappa-1)\ell}{4}\left(1-\sqrt{1-\frac{4c\kappa\mu_{x}}{(\mu
r-\ell)^{2}}}\right)$ $\displaystyle\geq-\frac{2\mu r\mu_{x}}{\mu
r-\ell}\geq-4\mu_{x}.$

Let $s_{1}$ be the corresponding eigenvalue of
$\mathbf{I}+\eta_{x}\mathbf{M}$, for small enough $c_{1}\leq 1$, it satisfies

$\displaystyle 0\leq 1-\frac{\mu_{x}}{r\ell}=1-\frac{1}{r\kappa_{x}}\leq
s_{1}=1+\eta_{x}\lambda_{1}\leq 1.$

We adversarially choose the initial point $(x_{0},y_{0})$ such that it is
parallel to the eigenvector of $\mathbf{I}+\eta_{x}\mathbf{M}$ corresponding
to $s_{1}$. We can always choose $x_{0}\geq 0$ for simplicity. Then we have

$\displaystyle\begin{pmatrix}x_{k+1}\\\ y_{k+1}\end{pmatrix}$
$\displaystyle=(\mathbf{I}+\eta_{x}\mathbf{M})^{T}\begin{pmatrix}x_{0}\\\
y_{0}\end{pmatrix}=s_{1}^{T}\begin{pmatrix}x_{0}\\\ y_{0}\end{pmatrix},$

so we can compute the magnitude of $x_{T}$ as $x_{T}=s_{1}^{T}x_{0}$. Choose
$\mu_{x}=\frac{\kappa\ell}{2T}$, and thus we have:

$\displaystyle\|\nabla\Phi(x_{T})\|=\|\mu_{x}x_{0}\|=\mu_{x}\left(1-\frac{1}{r\kappa_{x}}\right)^{T}|x_{0}|\geq\mu_{x}\left(1-\frac{1}{\kappa\kappa_{x}}\right)^{T}|x_{0}|\geq\mu_{x}\exp\left(\frac{2T}{\kappa\kappa_{x}}\right)|x_{0}|\geq\frac{1}{2}\mu_{x}|x_{0}|$

where we use the inequality that $1-\frac{z}{2}\geq\exp(z\ln\frac{1}{2})$ and
$\exp(z\ln\frac{1}{2})\geq\frac{1}{2}$ for $z\in[0,1]$. Recall that we choose
$x_{0}=\sqrt{\frac{2\Delta_{\Phi}}{\mu_{x}}}$, we have:

$\displaystyle\|\nabla\Phi(x_{T})\|\geq\frac{1}{2}\sqrt{{2\mu_{x}\Delta}}=\Omega\left(\sqrt{{\frac{\kappa\ell\Delta}{T}}}\right),$

which means to guarantee that $\|\nabla\Phi(x_{T})\|\leq\epsilon$, we must
have $T\geq\Omega\left(\frac{\kappa\ell\Delta_{\Phi}}{\epsilon^{2}}\right)$.

∎

######  Proposition C.3.

For GDA algorithm, given $\eta_{y}=\Theta(1/\ell)$, for any
$\eta_{x}\in(\frac{1}{\kappa\ell},\infty)$, there exists a $\ell$-smooth
function that is nonconvex in $x$ and $\mu$-strongly-concave in y, such that:

$\displaystyle\|\nabla\Phi(x_{T})\|\geq c$

where $c$ is some constant that does not vanish as $T$ increases.

###### Proof.

Recall the transition matrix in (86). We notice that

$\displaystyle{\textsf{trace}}(\mathbf{M})=\lambda_{1}+\lambda_{2}=L-\mu r.$

Since $r\leq\kappa$, then $\lambda_{1}+\lambda_{2}\geq 0$, which means that
$\max\\{Re[\lambda_{1}],Re[\lambda_{2}]\\}\geq 0$, so:

$\displaystyle\|(\mathbf{I}+\eta_{x}\mathbf{M})^{T}\|\geq\max\\{|1+\eta_{x}\lambda_{1}|,|1+\eta_{x}\lambda_{2}|\\}^{T}\geq\alpha^{T}$

where $\alpha$ is some constant larger than $1$. If we choose the
initialization to be $[x_{0},0]$, the gradient
$\|\nabla\Phi(x_{T})\|={\mu_{x}}\|(\mathbf{I}+\eta_{x}\mathbf{M})^{T}\|x_{0}$
diverges. ∎

####  C.2 Lower bound for EG/OGDA

######  Theorem C.4 (Theorem 5.2 restated).

For deterministic EG/OGDA algorithm, given $\eta_{y}=\Theta(1/\ell)$, for any
$\eta_{x}$, there exists a $\ell$-smooth function that is nonconvex in $x$ and
$\mu$-strongly-concave in y, such that for $\|\Phi(x_{T})\|\leq\epsilon$, we
must have:

$\displaystyle
T=\Omega\left(\frac{\kappa\ell\Delta_{\phi}}{\epsilon^{2}}\right)$

###### Proof of Theorem C.4 for EG.

We consider the same quadratic hard example $f$ and notation used in the proof
of Theorem 5.1. For simplicity, denote $\boldsymbol{w}=(x,y)$. Then the
updating rule for EG can be written as:

$\displaystyle\boldsymbol{w}_{k+1/2}=$
$\displaystyle(\mathbf{I}+\eta_{x}\mathbf{M})\boldsymbol{w}_{k},$
$\displaystyle\boldsymbol{w}_{k+1}=$
$\displaystyle\boldsymbol{w}_{k}+\eta_{x}\mathbf{M}\boldsymbol{w}_{k+1/2}$
$\displaystyle=$
$\displaystyle(\mathbf{I}+\eta_{x}\mathbf{M}+\eta_{x}^{2}\mathbf{M}^{2})\boldsymbol{w}_{k}.$

Therefore, similar to GDA, EG is also a linear time-invariant system with the
difference that the transition matrix now becomes as
$\mathbf{M}^{\prime}=(\mathbf{I}+\eta_{x}\mathbf{M}+\eta_{x}^{2}\mathbf{M}^{2})$.

The rest of the analysis is the same as that of GDA in Proposition C.2. Then,
we are going to show that when
$\eta_{x}\in(\frac{1}{c_{x}\kappa\ell},+\infty)$ for some $c_{x}$, the EG
method diverges. Consider

$\displaystyle f(x,y):=-\tfrac{1}{2}\ell x^{2}+bxy-\tfrac{1}{2}\mu y^{2}.$

Then according to Proposition C.2, we have:

$\begin{split}\textsf{trace}(\mathbf{M}^{\prime})&=\textsf{trace}(\mathbf{I}+\eta_{x}\mathbf{M}+\eta_{x}^{2}\mathbf{M}^{2})\\\
&=1+\eta_{x}(\ell-\mu r)+\eta_{x}^{2}(\ell^{2}+\mu^{2}r^{2}-2rb^{2})\\\
&=1+\eta_{x}(\ell-\mu r)+\eta_{x}^{2}\left((\ell-\mu
r)^{2}-2r\mu\mu_{x}\right)\end{split}$ (87)

Now note that since $r\leq\kappa$, to show
$\textsf{trace}(\mathbf{M}^{\prime})\geq 1$, it is enough to have
$\mu_{x}\leq\frac{(\ell-\mu r)^{2}}{2r\mu}$. However, by choosing
$\mu_{x}=\Theta(\epsilon^{2})$, and by choosing the small enough $\epsilon$,
we can satisfy the condition that $\mu_{x}\leq\frac{(\ell-\mu r)^{2}}{2r\mu}$,
thus we can conclude that under this situation
$\textsf{trace}(\mathbf{M}^{\prime})\geq 1$, which means that same step as the
Proposition C.3 can be taken to prove the divergence of
$\|\nabla\Phi(x_{T})\|^{2}$.

∎

###### Proof of Theorem C.4 for OGDA.

Assuming the same setup as the proof of EG, the update rule can be written as
follows: The dynamics of OGDA is

$\displaystyle\boldsymbol{w}_{k+1}=\boldsymbol{w}_{k}+2\eta_{x}\mathbf{M}\boldsymbol{w}_{k}-\eta_{x}\mathbf{M}\boldsymbol{w}_{k-1}.$

If we initialize $\boldsymbol{w}_{0}$ parallel to the eigenvector of
$\mathbf{M}$ corresponding to $\lambda_{1}$ and let
$\boldsymbol{w}_{1}=\boldsymbol{w}_{0}$, we know every $\boldsymbol{w}_{k}$ is
parallel to it, i.e., $\boldsymbol{w}_{k}=z_{k}\boldsymbol{w}_{0}$ for some
scalar $z_{k}$ which satisfies

$\displaystyle
z_{k+1}=z_{k}+2\eta_{x}\lambda_{1}z_{k}-\eta_{x}\lambda_{1}z_{k-1}.$

The general solution of the above recurrence relation is

$\displaystyle z_{k}=a\alpha^{k}+b\beta^{k}$

for some constant $a,b$ and

$\displaystyle\alpha=$
$\displaystyle\frac{1}{2}\left(1+2\eta_{x}\lambda_{1}+\sqrt{1+4\eta_{x}^{2}\lambda_{1}^{2}}\right),$
$\displaystyle\beta=$
$\displaystyle\frac{1}{2}\left(1+2\eta_{x}\lambda_{1}-\sqrt{1+4\eta_{x}^{2}\lambda_{1}^{2}}\right).$

We have

$\displaystyle 1+\eta_{x}\lambda_{1}\leq\alpha\leq
1,\quad\eta_{x}\lambda_{1}\leq\beta\leq 0.$

Using the initial condition $z_{-1}=z_{0}=1$, we can get the constants

$\displaystyle a=$
$\displaystyle\frac{\alpha(1-\beta)}{\alpha-\beta}=\frac{1}{2}+\frac{1}{2\sqrt{1+4\eta_{x}^{2}\lambda_{1}^{2}}}\geq
1/2,$ $\displaystyle b=$
$\displaystyle-\frac{\beta(1-\alpha)}{\alpha-\beta}=\frac{\sqrt{1+4\eta_{x}^{2}\lambda_{1}^{2}}-1}{2\sqrt{1+4\eta_{x}^{2}\lambda_{1}^{2}}}\leq\eta_{x}^{2}\lambda_{1}^{2}.$

We can bound

$\displaystyle|z_{T}|$
$\displaystyle\geq\frac{1}{2}\left(1+\eta_{x}\lambda_{1}\right)^{T}-|\eta_{x}\lambda_{1}|^{k+2}$
$\displaystyle\geq\frac{1}{2}\left(1-\frac{4c_{1}\mu_{x}}{\kappa}\right)^{T}-\frac{1}{4},$

where we use the fact $|\eta_{x}\lambda_{1}|\leq 1/2$. Similar to the analysis
for GDA, choosing $\mu_{x}=50\epsilon^{2}/\Delta_{\Phi}$, we have

$\displaystyle\left|\nabla\Phi(\bar{x})\right|=\mu_{x}\bar{x}\geq$
$\displaystyle\mu_{x}x_{T}\geq\mu_{x}x_{0}\left[\frac{1}{2}\left(1-\frac{4c_{1}\mu_{x}}{\kappa}\right)^{T}-\frac{1}{4}\right]$
$\displaystyle=$ $\displaystyle
10\epsilon\left[\frac{1}{2}\left(1-\frac{4c_{1}\mu_{x}}{\kappa}\right)^{T}-\frac{1}{4}\right].$

Therefore, if $\left|\nabla\Phi(\bar{x})\right|\leq\epsilon$, we must have

$\displaystyle
T=\Omega\left(\frac{\kappa}{\mu_{x}}\right)=\Omega\left(\frac{\kappa\Delta_{\Phi}}{\epsilon^{2}}\right).$

Now, we will show that Proposition C.3 also holds for OGDA. Consider the
following $4\times 4$ matrix $\mathbf{M}^{\prime}$:

$\mathbf{M}^{\prime}=\left[\begin{array}[]{c;{2pt/2pt}c}(\mathbf{I}+2\eta_{x}\mathbf{M})^{2}&-\eta_x
(\mathbf{I} + 2 \eta_x \mathbf{M}) \mathbf{M}\\\
\hdashline[2pt/2pt]\mathbf{I}+2\eta_{x}\mathbf{M}&\- \eta_x
\mathbf{M}\end{array}\right]$ (88)

It can be easily shown that, the OGDA dynamic can be written as follows:

$\left[\begin{array}[]{c}\boldsymbol{w}_{k+1}\\\
\boldsymbol{w}_{k}\end{array}\right]=\left[\begin{array}[]{c;{2pt/2pt}c}(\mathbf{I}+2\eta_{x}\mathbf{M})^{2}&-\eta_x
(\mathbf{I} + 2 \eta_x \mathbf{M}) \mathbf{M}\\\
\hdashline[2pt/2pt]\mathbf{I}+2\eta_{x}\mathbf{M}&\- \eta_x
\mathbf{M}\end{array}\right]\left[\begin{array}[]{c}\boldsymbol{w}_{k-1}\\\
\boldsymbol{w}_{k-2}\end{array}\right]$ (89)

Now similar to proof of Proposition C.3 for GDA, it suffices to show that the
$\textsf{trace}(\mathbf{M}^{\prime})\geq 1$ given the conditions on the
learning rate. To this end, note that we can write:

$\begin{split}\textsf{trace}(\mathbf{M}^{\prime})&=\textsf{trace}(-\eta_{x}\mathbf{M})+\textsf{trace}(\mathbf{I}+4\eta_{x}\mathbf{M}+4\eta_{x}^{2}\mathbf{M}^{2})\\\
&=1-\eta_{x}(\ell-\mu r)+4\eta_{x}(\ell-\mu
r)+4\eta_{x}^{2}(\ell^{2}+\mu^{2}r^{2}-2rb^{2})\\\ &=1+3\eta_{x}(\ell-\mu
r)+4\eta_{x}^{2}\left((\ell-\mu r)^{2}-2r\mu\mu_{x}\right)\end{split}$ (90)

Now note that since $r\leq\kappa$, to show
$\textsf{trace}(\mathbf{M}^{\prime})\geq 1$, it is enough to have
$\mu_{x}\leq\frac{(\ell-\mu r)^{2}}{2r\mu}$. However, note that we let
$\mu_{x}=\frac{50\epsilon^{2}}{\Delta_{\Phi}}$, thus by choosing the small
enough $\epsilon$, we can satisfy the condition that
$\mu_{x}\leq\frac{(\ell-\mu r)^{2}}{2r\mu}$, thus we can conclude that
$\textsf{trace}(\mathbf{M}^{\prime})\geq 1$ holds. Consequently, similar
argument as the Proposition C.3 can be made to prove the divergence of
$\|\nabla\Phi(x_{T})\|^{2}$. ∎

###  Appendix D Extension to Generalized OGDA

In this section, we analyze the convergence of generalized OGDA (Algorithm 4)
where we utilize different learning rates for descent/ascent gradients and
correction terms. Specifically, we propose to use different learning rates for
$\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})$, and
$\nabla_{x}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})$
terms, and also $\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})$, and
$\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})$,
in order to make the algorithm more stable. We believe this algorithm is more
convenient in practice due to the more flexibility it provides in deciding the
learning rates. We demonstrated this stabilizing effect of generalized OGDA in
our empirical results in Section 6. Also, note that if we let
$\eta_{x,1}=\eta_{x,2}$, and $\eta_{y,1}=\eta_{y,2}$ in Algorithm 4, it
reduces to stochastic OGDA. Theorem D.1 establishes the convergence rate of
generalized OGDA in NC-SC. However, it still remains open to analyze this
algorithm in C-C/SC-SC and NC-C settings.

We remark that the analysis of generalized OGDA was only known for the
restricted bilinear functions, which is established in [39], and convergence
analysis beyond these simple functions previously was unknown that we provide
here.

Algorithm 4 Generalized Stochastic OGDA

Input: $(\boldsymbol{x}_{0},\boldsymbol{y}_{0})$, stepsizes
$(\eta_{x,1},\eta_{x,2},\eta_{y,1},\eta_{y,2})$

for $t=1,2,\dots,T$ do

$\boldsymbol{x}_{t}\leftarrow\boldsymbol{x}_{t-1}-\eta_{x,1}\boldsymbol{g}_{x,t-1}-\eta_{x,2}(\boldsymbol{g}_{x,t-1}-\boldsymbol{g}_{x,t-2})$

$\boldsymbol{y}_{t}\leftarrow\boldsymbol{y}_{t-1}+\eta_{y,1}\boldsymbol{g}_{y,t-1}+\eta_{y,2}(\boldsymbol{g}_{y,t-1}-\boldsymbol{g}_{y,t-2})$

end for

Randomly choose $\bar{\boldsymbol{x}}$ from
$\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{T}$

Output:$\bar{\boldsymbol{x}}$

######  Theorem D.1.

Let $\eta_{x,1}=\frac{1}{50\kappa^{2}\ell}$, $\eta_{y,2}=\frac{1}{6\ell}$.
Also, let $\alpha=\frac{\eta_{x,2}}{\eta_{x,1}}$, and
$\beta=\frac{\eta_{y,1}}{\eta_{y,2}}$. Then assuming $\beta\leq 1$, and
$\alpha\leq 2\kappa^{2}\sqrt{\beta}$, under Assumptions 4.1, and 4.3 for
Algorithm 4 we have:

$\begin{split}\mathbb{E}[\|\nabla\Phi(\bar{\boldsymbol{x}})\|^{2}]&\leq
O\Big{(}\frac{\kappa^{2}\ell\Delta}{T}+\frac{(\kappa+\alpha^{2})\ell^{2}D}{\beta
T}+\frac{\kappa\sigma^{2}}{M_{y}}+\frac{(1+\alpha^{2})\sigma^{2}}{M_{x}}\Big{)},\end{split}$
(91)

where
$D=\max(\|\boldsymbol{y}_{1}-\boldsymbol{y}^{*}_{1}\|^{2},\|\boldsymbol{y}_{1}-\boldsymbol{y}_{0}\|^{2},\|\boldsymbol{x}_{1}-\boldsymbol{x}_{0}\|^{2})$,
and
$\Delta=\phi(\boldsymbol{x}_{1})-\min_{\boldsymbol{x}}\Phi(\boldsymbol{x})$.

A few observations about the obtained rate are in place.

######  Corollary D.2.

Let $\sigma=0$, and pick an $\alpha\leq\sqrt{\kappa}$. Then deterministic
generalized OGDA converges to $\epsilon$-stationary point of
$\Phi(\boldsymbol{x})$ with gradient complexity of
$O(\frac{\kappa^{2}}{\epsilon^{2}})$.

######  Corollary D.3.

For any $\alpha=O(\sqrt{k})$, and any $\mu\leq\beta\leq 1$, if we choose
$M_{x}=O(\kappa\frac{\sigma^{2}}{\epsilon^{2}})$, and
$M_{y}=O(\frac{\kappa}{\epsilon^{2}})$, then stochastic generalized OGDA
converges to $\epsilon$-stationary point of $\Phi(\boldsymbol{x})$ with
gradient complexity of $O(\frac{\kappa^{3}}{\epsilon^{4}})$.

######  Remark D.4.

Theorem D.1 establishes the convergence rate under broad range of primal
learning rates ratio ($0\leq\alpha\leq O(\kappa^{2}))$, and it shows that as
long as $\alpha\leq\sqrt{\kappa}$, we can achieve the same convergence rate as
OGDA if we assume $\mu\leq\beta\leq 1$.

####  D.1 Nonconvex-strongly-concave setting

We follow exact same steps as Lemma A.4, to derive the following lemmas.

######  Lemma D.5.

Let
$\Phi(\boldsymbol{x})=\max_{\boldsymbol{y}}f(\boldsymbol{x},\boldsymbol{y})$,
and
$\boldsymbol{y}^{*}(\boldsymbol{x})=\arg\max_{\boldsymbol{y}}f(\boldsymbol{x},\boldsymbol{y})$.
Also, let
$\boldsymbol{g}_{i}=\boldsymbol{g}_{x,i}+\alpha(\boldsymbol{g}_{x,i}-\boldsymbol{g}_{x,i-1})$,
where $\alpha=\frac{\eta_{x,2}}{\eta_{x,1}}$. Therefore, we have
$\boldsymbol{x}_{i}=\boldsymbol{x}_{i-1}-\eta_{x,1}\boldsymbol{g}_{i}$. Then
for Algorithm 4, we have:

$\begin{split}&\mathbb{E}[\Phi(\boldsymbol{x}_{t})]\leq\mathbb{E}[\Phi(\boldsymbol{x}_{t-1})]-\frac{\eta_{x,1}}{2}\mathbb{E}[\|\nabla\Phi(\boldsymbol{x}_{t-1})\|^{2}]-\frac{\eta_{x,1}}{2}(1-2\kappa\ell\eta_{x,1})\mathbb{E}[\|\boldsymbol{g}_{t-1}\|^{2}]\\\
&\qquad+\frac{3}{2}\eta_{x,1}^{3}\alpha^{2}\ell^{2}\mathbb{E}[\|\boldsymbol{g}_{t-2}\|^{2}]+\frac{3}{2}\eta_{x,1}\ell^{2}\mathbb{E}[\|\boldsymbol{y}^{*}_{t-1}-\boldsymbol{y}_{t-1}\|^{2}]+\frac{3}{2}\eta_{x,1}\alpha^{2}\ell^{2}\mathbb{E}[\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}]\\\
&\qquad+3((1+\alpha)^{2}+1)\eta_{x,1}\frac{\sigma^{2}}{M_{x}}\end{split}$ (92)

###### Proof of Lemma D.5.

Proof is pretty much similar to proof of Lemma A.4, and we only include this
proof for sake of completeness. First, let
$\boldsymbol{\delta}^{x}_{i}=\boldsymbol{g}_{x,i}-\nabla_{x}f(\boldsymbol{x}_{i},\boldsymbol{y}_{i})$.
By definition of $\boldsymbol{g}_{x,i}$, we have
$\mathbb{E}[\boldsymbol{\delta}^{x}_{i}]=0$, for all $i\in[T]$.

Using the fact that $\Phi(\boldsymbol{x})$ is $2\kappa\ell$ smooth, we have:

$\begin{split}\Phi(\boldsymbol{x}_{t})&\leq\Phi(\boldsymbol{x}_{t-1})+\langle\nabla\Phi(\boldsymbol{x}_{t-1}),\boldsymbol{x}_{t}-\boldsymbol{x}_{t-1}\rangle+\kappa\ell\|\boldsymbol{x}_{t}-\boldsymbol{x}_{t-1}\|^{2}\\\
&=\Phi(\boldsymbol{x}_{t-1})-\eta_{x,1}\langle\nabla\Phi(\boldsymbol{x}_{t-1}),\boldsymbol{g}_{t-1}\rangle+\kappa\ell\eta_{x,1}^{2}\|\boldsymbol{g}_{t-1}\|^{2}\\\
&=\Phi(\boldsymbol{x}_{t-1})-\frac{\eta_{x,1}}{2}\|\nabla\Phi(\boldsymbol{x}_{t-1})\|^{2}-\frac{\eta_{x,1}}{2}\|\boldsymbol{g}_{t-1}\|^{2}+\frac{\eta_{x,1}}{2}\|\nabla\Phi(\boldsymbol{x}_{t-1})-\boldsymbol{g}_{t-1}\|^{2}\\\
&\quad+\kappa\ell\eta_{x,1}^{2}\|\boldsymbol{g}_{t-1}\|^{2}\\\
&=\Phi(\boldsymbol{x}_{t-1})-\frac{\eta_{x,1}}{2}\|\nabla\Phi(\boldsymbol{x}_{t-1})\|^{2}-\frac{\eta_{x,1}}{2}(1-2\kappa\ell\eta_{x,1})\|\boldsymbol{g}_{t-1}\|^{2}\\\
&\quad+\frac{\eta_{x,1}}{2}\|\nabla\Phi(\boldsymbol{x}_{t-1})-\boldsymbol{g}_{t-1}\|^{2}\\\
\end{split}$ (93)

Now using $\ell$-smoothness of $f$, and $\kappa$-Lipschitzness of
$\boldsymbol{y}^{*}(\boldsymbol{x})$ (Lemma A.1) we have:

$\begin{split}&\|\nabla\Phi(\boldsymbol{x}_{t-1})-\boldsymbol{g}_{t-1}\|^{2}=\|\nabla\Phi(\boldsymbol{x}_{t-1})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\\\
&\qquad-\alpha\left(\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{x}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2})\right)-((\alpha+1)\boldsymbol{\delta}^{x}_{t-1}-\boldsymbol{\delta}^{x}_{t-2})\|^{2}\\\
&\quad\leq
3\|\nabla\Phi(\boldsymbol{x}_{t-1})-\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}+3\alpha^{2}\|\nabla_{x}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{x}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2})\|^{2}\\\
&\qquad+3\|(\alpha+1)\boldsymbol{\delta}^{x}_{t-1}-\boldsymbol{\delta}^{x}_{t-2}\|^{2}\\\
&\quad\leq
3\ell^{2}\|\boldsymbol{y}^{*}(\boldsymbol{x}_{t-1})-\boldsymbol{y}_{t-1}\|^{2}+3\alpha^{2}\ell^{2}\|\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t-2}\|^{2}+3\alpha^{2}\ell^{2}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}\\\
&\qquad+6(\alpha+1)^{2}\|\boldsymbol{\delta}^{x}_{t-1}\|^{2}+6\|\boldsymbol{\delta}^{x}_{t-2}\|^{2}\end{split}$
(94)

where in the first and second inequalities we used Young’s inequality.

By combining Equations 93 and 94 we have:

$\begin{split}\Phi(\boldsymbol{x}_{t})&\leq\Phi(\boldsymbol{x}_{t-1})-\frac{\eta_{x,1}}{2}\|\nabla\Phi(\boldsymbol{x}_{t-1})\|^{2}-\frac{\eta_{x,1}}{2}(1-2\kappa\ell\eta_{x,1})\|\boldsymbol{g}_{t-1}\|^{2}\\\
&\quad+\frac{3}{2}\eta_{x,1}\ell^{2}\|\boldsymbol{y}^{*}_{t-1}-\boldsymbol{y}_{t-1}\|^{2}+\frac{3}{2}\eta_{x,1}\alpha^{2}\ell^{2}\|\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t-2}\|^{2}+\frac{3}{2}\eta_{x,1}\alpha^{2}\ell^{2}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}\\\
&\quad+3\eta_{x,1}(\alpha+1)^{2}\|\boldsymbol{\delta}_{t-1}^{x}\|^{2}+3\eta_{x,1}\|\boldsymbol{\delta}^{x}_{t-2}\|^{2}\\\
&\leq\Phi(\boldsymbol{x}_{t-1})-\frac{\eta_{x,1}}{2}\|\nabla\Phi(\boldsymbol{x}_{t-1})\|^{2}-\frac{\eta_{x,1}}{2}(1-2\kappa\ell\eta_{x,1})\|\boldsymbol{g}_{t-1}\|^{2}+\frac{3}{2}\eta_{x,1}^{3}\alpha^{2}\ell^{2}\|\boldsymbol{g}_{t-2}\|^{2}\\\
&\quad+\frac{3}{2}\eta_{x,1}\ell^{2}\|\boldsymbol{y}^{*}_{t-1}-\boldsymbol{y}_{t-1}\|^{2}+\frac{3}{2}\eta_{x,1}\ell^{2}\alpha^{2}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}+3\eta_{x,1}(\alpha+1)^{2}\|\boldsymbol{\delta}_{t-1}^{x}\|^{2}\\\
&\quad+3\eta_{x,1}\|\boldsymbol{\delta}^{x}_{t-2}\|^{2}\end{split}$ (95)

We proceed by taking expectation on both side of Equation 95, to get:

$\begin{split}\mathbb{E}[\Phi(\boldsymbol{x}_{t})]&\leq\mathbb{E}[\Phi(\boldsymbol{x}_{t-1})]-\frac{\eta_{x,1}}{2}\mathbb{E}[\|\nabla\Phi(\boldsymbol{x}_{t-1})\|^{2}]-\frac{\eta_{x,1}}{2}(1-2\kappa\ell\eta_{x,1})\mathbb{E}[\|\boldsymbol{g}_{t-1}\|^{2}]\\\
&\quad+\frac{3}{2}\eta_{x,1}^{3}\alpha^{2}\ell^{2}\mathbb{E}[\|\boldsymbol{g}_{t-2}\|^{2}]+\frac{3}{2}\eta_{x,1}\ell^{2}\mathbb{E}[\|\boldsymbol{y}^{*}_{t-1}-\boldsymbol{y}_{t-1}\|^{2}]\\\
&\quad+\frac{3}{2}\eta_{x,1}\alpha^{2}\ell^{2}\mathbb{E}[\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}]+3((1+\alpha)^{2}+1)\eta_{x,1}\frac{\sigma^{2}}{M_{x}}\end{split}$
(96)

where we used the fact that
$\mathbb{E}[\boldsymbol{\delta}^{x}_{i}]\leq\frac{\sigma^{2}}{M_{x}}$ for all
$i\in[T]$.

∎

######  Lemma D.6.

Let $\eta_{y,2}=\frac{1}{6\ell}$, then the following inequality holds true for
generalized OGDA iterates:

$\begin{split}\sum_{i=1}^{t+1}\mathbb{E}[\|\boldsymbol{y}_{i}-\boldsymbol{y}^{*}_{i}\|^{2}]&\leq\frac{9}{7}\mathbb{E}[\|\boldsymbol{y}_{1}-\boldsymbol{y}^{*}_{1}\|^{2}]+\frac{36}{7}\sum_{i=2}^{t+1}\mathbb{E}[\|\boldsymbol{z}_{i}-\boldsymbol{y}^{*}_{i}\|^{2}]+\frac{18}{7}\eta_{x,1}^{2}\kappa^{2}\sum_{i=1}^{t}\mathbb{E}[\|\boldsymbol{g}_{i}\|^{2}]\\\
&\quad+\frac{2T\sigma^{2}}{7\ell^{2}M_{y}}\end{split}$ (97)

###### Proof of Lemma D.6.

Using Young’s inequality, and $\kappa$-Lipschitzness of
$\boldsymbol{y}^{*}(\boldsymbol{x})$ we have:

$\begin{split}\|\boldsymbol{y}_{t+1}-\boldsymbol{y}^{*}_{t+1}\|^{2}&\leq
2\|\boldsymbol{y}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}+2\|\boldsymbol{y}^{*}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}\\\
&\leq
2\|\boldsymbol{y}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}+2\kappa^{2}\|\boldsymbol{x}_{t+1}-\boldsymbol{x}_{t}\|^{2}\end{split}$
(98)

Similar to Lemma A.5, we try to find an upper bound for
$\|\boldsymbol{y}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}$. Let
$\boldsymbol{z}_{t+1}=\boldsymbol{y}_{t}+\eta_{y,1}\boldsymbol{g}_{y,t}-\eta_{y,2}\boldsymbol{g}_{y,t-1}$,
and
$\boldsymbol{\delta}^{y}_{i}=\boldsymbol{g}_{y,i}-\nabla_{y}f(\boldsymbol{x}_{i},\boldsymbol{y}_{i})$.
Then we have:

$\begin{split}\|\boldsymbol{y}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}&=\|\boldsymbol{z}_{t+1}-\boldsymbol{y}^{*}_{t}+\eta_{y,2}\boldsymbol{g}_{y,t}\|^{2}\\\
&\leq
2\|\boldsymbol{z}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}+2\eta_{y,2}^{2}\|\boldsymbol{g}_{y,t}\|^{2}\\\
&\leq
2\|\boldsymbol{z}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}+4\eta_{y,2}^{2}\|\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})\|^{2}+4\eta_{y,2}^{2}\|\boldsymbol{\delta}_{t}^{y}\|^{2}\\\
&\leq
2\|\boldsymbol{z}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}+4\eta_{y,2}^{2}\ell^{2}\|\boldsymbol{y}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}+4\eta_{y,2}^{2}\|\boldsymbol{\delta}_{t}^{y}\|^{2}\end{split}$
(99)

The rest of the proof is exactly same as proof of Lemma A.5. ∎

Similar to Lemma A.6, we have:

######  Lemma D.7.

Let
$\boldsymbol{z}_{t+1}=\boldsymbol{y}_{t}+\eta_{y,1}\boldsymbol{g}_{y,t}-\eta_{y,2}\boldsymbol{g}_{y,t-1}$,
$\boldsymbol{r}_{t}=\|\boldsymbol{z}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}+\frac{\beta}{4}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}$
and $\eta_{y,2}=\frac{1}{6\ell}$. Also let
$\frac{\eta_{y,1}}{\eta_{y,2}}=\beta$, and assume $\beta\leq 1$. Then OGDA
iterates satisfy the following inequalities:

$\begin{split}\mathbb{E}[\boldsymbol{r}_{t}]&\leq(1-\frac{\beta}{12\kappa})\mathbb{E}[\boldsymbol{r}_{t-1}]+12\eta_{x,1}^{2}\kappa^{3}\mathbb{E}[\|\boldsymbol{g}_{t-1}\|^{2}]+\frac{\beta\eta_{x,1}^{2}}{18}\mathbb{E}[\|\boldsymbol{g}_{t-2}\|^{2}]+\frac{\beta\sigma^{2}}{3\ell^{2}M_{y}}\end{split}$
(100)

$\begin{split}\sum_{i=1}^{t}\mathbb{E}[\boldsymbol{r}_{i}]\leq\frac{12\kappa}{\beta}\mathbb{E}[\boldsymbol{r}_{1}]+\frac{2}{3}\kappa\mathbb{E}[\|\boldsymbol{x}_{1}-\boldsymbol{x}_{0}\|^{2}]+145\frac{\eta_{x,1}^{2}\kappa^{4}}{\beta}\sum_{i=1}^{t-1}\mathbb{E}[\|\boldsymbol{g}_{i}\|^{2}]+\frac{4\kappa\sigma^{2}(t-1)}{\ell^{2}M_{y}}\end{split}$
(101)

###### Proof of Lemma D.7.

Let
$\boldsymbol{\delta}^{y}_{i}=\boldsymbol{g}_{y,i}-\nabla_{y}f(\boldsymbol{x}_{i},\boldsymbol{y}_{i})$,
and note that we have
$\boldsymbol{z}_{t+1}-\boldsymbol{z}_{t}=\eta_{y,1}\boldsymbol{g}_{y,t}$. We
have:

$\begin{split}\|\boldsymbol{z}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}&=\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t}+\eta_{y,1}\boldsymbol{g}_{y,t}\|^{2}\\\
&=\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}+2\eta_{y,1}\langle\boldsymbol{g}_{y,t},\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t}\rangle+\eta_{y,1}^{2}\|\boldsymbol{g}_{y,t}\|^{2}\\\
&=\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}-2\eta_{y,1}\eta_{y,2}\langle\boldsymbol{g}_{y,t},\boldsymbol{g}_{y,t-1}\rangle+2\eta_{y,1}\langle\boldsymbol{g}_{y,t},\boldsymbol{y}_{t}-\boldsymbol{y}^{*}_{t}\rangle+\eta_{y,1}^{2}\|\boldsymbol{g}_{y,t}\|^{2}\\\
&=\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}+\eta_{y,1}\eta_{y,2}\|\boldsymbol{g}_{y,t}-\boldsymbol{g}_{y,t-1}\|^{2}+2\eta_{y,1}\langle\boldsymbol{g}_{y,t},\boldsymbol{y}_{t}-\boldsymbol{y}^{*}_{t}\rangle\\\
&\quad-\eta_{y,1}\eta_{y,2}\|\boldsymbol{g}_{y,t-1}\|^{2}-\eta_{y,1}(\eta_{y,2}-\eta_{y,1})\|\boldsymbol{g}_{y,t}\|^{2}\\\
&\leq\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}+3\eta_{y,1}\eta_{y,2}\|\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t})-\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})\|^{2}\\\
&\quad+2\eta_{y,1}\langle\nabla_{y}f(\boldsymbol{x}_{t},\boldsymbol{y}_{t}),\boldsymbol{y}_{t}-\boldsymbol{y}^{*}_{t}\rangle-\eta_{y,1}\eta_{y,2}\|\boldsymbol{g}_{y,t-1}\|^{2}-\eta_{y,1}(\eta_{y,2}-\eta_{y,1})\|\boldsymbol{g}_{y,t}\|^{2}\\\
&\quad+3\eta_{y,1}\eta_{y,2}\|\boldsymbol{\delta}^{y}_{t}\|^{2}+3\eta_{y,1}\eta_{y,2}\|\boldsymbol{\delta}^{y}_{t-1}\|^{2}+2\eta_{y,1}\langle\boldsymbol{\delta}^{y}_{t},\boldsymbol{y}_{t}-\boldsymbol{y}^{*}_{t}\rangle\\\
&\leq\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}+3\eta_{y,1}\eta_{y,2}\ell^{2}\|\boldsymbol{x}_{t}-\boldsymbol{x}_{t-1}\|^{2}+3\eta_{y,1}\eta_{y,2}\ell^{2}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}\\\
&\quad-2\eta_{y,1}\mu\|\boldsymbol{y}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}-\eta_{y,1}\eta_{y,2}\|\boldsymbol{g}_{y,t-1}\|^{2}-\eta_{y,1}(\eta_{y,2}-\eta_{y,1})\|\boldsymbol{g}_{y,t}\|^{2}\\\
&\quad+3\eta_{y,1}\eta_{y,2}\|\boldsymbol{\delta}^{y}_{t}\|^{2}+3\eta_{y,1}\eta_{y,2}\|\boldsymbol{\delta}^{y}_{t-1}\|^{2}+2\eta_{y,1}\langle\boldsymbol{\delta}^{y}_{t},\boldsymbol{y}_{t}-\boldsymbol{y}^{*}_{t}\rangle\end{split}$
(102)

where the last inequality follows from smoothness of $f$, and strong concavity
of $f(\boldsymbol{x}_{t},.)$. Now note that using Young’s inequality we can
write:

$\|\boldsymbol{y}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}\geq\frac{1}{2}\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}-\eta_{y,2}^{2}\|\boldsymbol{g}_{y,t-1}\|^{2}$
(103)

Now plugging Equation 103 back to Equation 102, and letting
$\eta_{y,1}=\beta\eta_{y,2}$, we have:

$\begin{split}\|\boldsymbol{z}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}&\leq(1-\beta\eta_{y,2}\mu)\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}+3\beta\eta_{y,2}^{2}\ell^{2}\|\boldsymbol{x}_{t}-\boldsymbol{x}_{t-1}\|^{2}+3\beta\eta_{y,2}^{2}\ell^{2}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}\\\
&\quad-\beta\eta_{y,2}^{2}(1-2\eta_{y,2}\mu)\|\boldsymbol{g}_{y,t-1}\|^{2}-\beta\eta_{y,2}^{2}(1-\beta)\|\boldsymbol{g}_{y,t}\|^{2}\\\
&\quad+3\beta\eta_{y,2}^{2}\|\boldsymbol{\delta}^{y}_{t}\|^{2}+3\beta\eta_{y,2}^{2}\|\boldsymbol{\delta}^{y}_{t-1}\|^{2}+2\beta\eta_{y,2}\langle\boldsymbol{\delta}^{y}_{t},\boldsymbol{y}_{t}-\boldsymbol{y}^{*}_{t}\rangle\end{split}$
(104)

We can also write:

$\begin{split}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}&=\|\eta_{y,1}\boldsymbol{g}_{y,t-1}+\eta_{y,2}(\boldsymbol{g}_{y,t-1}-\boldsymbol{g}_{y,t-2})\|^{2}\\\
&\leq
2\eta_{y,1}^{2}\|\boldsymbol{g}_{y,t-1}\|^{2}+2\eta_{y,2}^{2}\|\boldsymbol{g}_{y,t-1}-\boldsymbol{g}_{y,t-2}\|^{2}\\\
&\leq
2\eta_{y,1}^{2}\|\boldsymbol{g}_{y,t-1}\|^{2}+6\eta_{y,2}^{2}\|\nabla_{y}f(\boldsymbol{x}_{t-1},\boldsymbol{y}_{t-1})-\nabla_{y}f(\boldsymbol{x}_{t-2},\boldsymbol{y}_{t-2})\|^{2}\\\
&\quad+6\eta_{y,2}^{2}\|\boldsymbol{\delta}^{y}_{t-1}\|^{2}+6\eta_{y,2}^{2}\|\boldsymbol{\delta}^{y}_{t-2}\|^{2}\\\
&\leq
2\eta_{y,1}^{2}\|\boldsymbol{g}_{y,t-1}\|^{2}+6\eta_{y,2}^{2}\ell^{2}\|\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t-2}\|^{2}+6\eta_{y,2}^{2}\ell^{2}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}\\\
&\quad+6\eta_{y,2}^{2}\|\boldsymbol{\delta}^{y}_{t-1}\|^{2}+6\eta_{y,2}^{2}\|\boldsymbol{\delta}^{y}_{t-2}\|^{2}\\\
&=2\beta^{2}\eta_{y,2}^{2}\|\boldsymbol{g}_{y,t-1}\|^{2}+6\eta_{y,2}^{2}\ell^{2}\|\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t-2}\|^{2}+6\eta_{y,2}^{2}\ell^{2}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}\\\
&\quad+6\eta_{y,2}^{2}\|\boldsymbol{\delta}^{y}_{t-1}\|^{2}+6\eta_{y,2}^{2}\|\boldsymbol{\delta}^{y}_{t-2}\|^{2}\\\
\end{split}$ (105)

Now adding
$9\beta\eta_{y,2}^{2}\ell^{2}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}$
to both side of Equation 104, and using Equation 105 we have:

$\begin{split}&\|\boldsymbol{z}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}+9\beta\eta_{y}^{2}\ell^{2}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}\leq(1-\beta\eta_{y,2}\mu)\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}+3\beta\eta_{y,1}^{2}\ell^{2}\|\boldsymbol{x}_{t}-\boldsymbol{x}_{t-1}\|^{2}\\\
&\qquad-\beta\eta_{y,2}^{2}(1-2\eta_{y,2}\mu-24\beta^{2}\eta_{y,2}^{2}\ell^{2})\|\boldsymbol{g}_{y,t-1}\|^{2}-\beta\eta_{y,2}^{2}(1-\beta)\|\boldsymbol{g}_{y,t}\|^{2}\\\
&\qquad+72\beta\eta_{y,2}^{4}\ell^{4}\|\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t-2}\|^{2}+72\beta\eta_{y,2}^{4}\ell^{4}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}\\\
&\qquad+3\beta\eta_{y,2}^{2}(1+24\eta_{y,2}^{2}\ell^{2})\|\boldsymbol{\delta}^{y}_{t}\|^{2}+3\beta\eta_{y,2}^{2}(1+24\eta_{y,2}^{2}\ell^{2})\|\boldsymbol{\delta}^{y}_{t-1}\|^{2}\\\
&\qquad+2\beta\eta_{y,2}\langle\boldsymbol{\delta}^{y}_{t},\boldsymbol{y}_{t}-\boldsymbol{y}^{*}_{t}\rangle\end{split}$
(106)

Now plugging $\eta_{y,2}=\frac{1}{6\ell}$ into Equation 106, and assuming
$\beta\leq 1$ we have:

$\begin{split}\|\boldsymbol{z}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}+\frac{\beta}{4}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}&\leq(1-\frac{\beta}{6\kappa})\left(\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}\right)+\frac{\beta}{18}\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}\\\
&\quad+\frac{\beta}{12}\|\boldsymbol{x}_{t}-\boldsymbol{x}_{t-1}\|^{2}+\frac{\beta}{18}\|\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t-2}\|^{2}\\\
&\quad+\frac{\beta}{6\ell^{2}}\|\boldsymbol{\delta}^{y}_{t}\|^{2}+\frac{\beta}{6\ell^{2}}\|\boldsymbol{\delta}^{y}_{t-1}\|^{2}+\frac{2\beta}{6\ell}\langle\boldsymbol{\delta}^{y}_{t},\boldsymbol{y}_{t}-\boldsymbol{y}^{*}_{t}\rangle\end{split}$
(107)

Taking expectation from both side of Equation 107, we have:

$\begin{split}\mathbb{E}\left[\|\boldsymbol{z}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}+\frac{\beta}{4}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}\right]&\leq(1-\frac{\beta}{6\kappa})\mathbb{E}\left[\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}\right]+\frac{\beta}{18}\mathbb{E}[\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}]\\\
&\quad+\frac{\beta}{12}\mathbb{E}[\|\boldsymbol{x}_{t}-\boldsymbol{x}_{t-1}\|^{2}]+\frac{\beta}{18}\mathbb{E}[\|\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t-2}\|^{2}]\\\
&\quad+\frac{\beta\sigma^{2}}{3\ell^{2}M_{y}}\end{split}$ (108)

Also using Young’s inequality we have:

$\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t}\|^{2}\leq(1+\frac{\beta}{12\kappa})\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t-1}\|^{2}+(1+12\frac{\kappa}{\beta})\kappa^{2}\|\boldsymbol{x}_{t}-\boldsymbol{x}_{t-1}\|^{2}$
(109)

where we used the fact that for any $\alpha>0$,
$\|\boldsymbol{x}+\boldsymbol{y}\|^{2}\leq(1+\alpha)\|\boldsymbol{x}\|^{2}+(1+\frac{1}{\alpha})\|\boldsymbol{y}\|^{2}$,
and $\kappa$-lipschitzness of $\boldsymbol{y}^{*}(\boldsymbol{x})$. Plugging
Equation 109 back to Equation 108, we have:

$\begin{split}\mathbb{E}\left[\|\boldsymbol{z}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}+\frac{\beta}{4}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}\right]&\leq(1-\frac{\beta}{12\kappa})\mathbb{E}\left[\|\boldsymbol{z}_{t}-\boldsymbol{y}^{*}_{t-1}\|^{2}+\frac{\beta}{4}\mathbb{E}[\|\boldsymbol{y}_{t-1}-\boldsymbol{y}_{t-2}\|^{2}]\right]\\\
&\quad+12\kappa^{3}\mathbb{E}[\|\boldsymbol{x}_{t}-\boldsymbol{x}_{t-1}\|^{2}]+\frac{\beta}{18}\mathbb{E}[\|\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t-2}\|^{2}]\\\
&\quad+\frac{\beta\sigma^{2}}{3\ell^{2}M_{y}}\end{split}$ (110)

Therefore, if we let
$\boldsymbol{r}_{t}=\|\boldsymbol{z}_{t+1}-\boldsymbol{y}^{*}_{t}\|^{2}+\frac{\beta}{4}\|\boldsymbol{y}_{t}-\boldsymbol{y}_{t-1}\|^{2}$,
then we have:

$\begin{split}\mathbb{E}[\boldsymbol{r}_{t}]&\leq(1-\frac{\beta}{12\kappa})\mathbb{E}[\boldsymbol{r}_{t-1}]+12\eta_{x,1}^{2}\kappa^{3}\mathbb{E}[\|\boldsymbol{g}_{t-1}\|^{2}]+\frac{\beta\eta_{x,1}^{2}}{18}\mathbb{E}[\|\boldsymbol{g}_{t-2}\|^{2}]+\frac{\beta\sigma^{2}}{3\ell^{2}M_{y}}\end{split}$
(111)

We can derive the following equation, by applying Lemma A.2.

$\begin{split}\sum_{i=1}^{t}\mathbb{E}[\boldsymbol{r}_{i}]&\leq\frac{12\kappa}{\beta}\mathbb{E}[\boldsymbol{r}_{1}]+144\frac{\eta_{x,1}^{2}\kappa^{4}}{\beta}\sum_{i=1}^{t-1}\mathbb{E}[\|\boldsymbol{g}_{i}\|^{2}]+\frac{2}{3}\eta_{x,1}^{2}\kappa\sum_{i=1}^{t-2}\mathbb{E}[\|\boldsymbol{g}_{i}\|^{2}]+\frac{2}{3}\kappa\mathbb{E}[\|\boldsymbol{x}_{1}-\boldsymbol{x}_{0}]\|^{2}\\\
&\quad+\frac{4\kappa\sigma^{2}(t-1)}{\ell^{2}M_{y}}\end{split}$ (112)

Or equivalently we have:

$\begin{split}\sum_{i=1}^{t}\mathbb{E}[\boldsymbol{r}_{i}]\leq\frac{12\kappa}{\beta}\mathbb{E}[\boldsymbol{r}_{1}]+\frac{2}{3}\kappa\mathbb{E}[\|\boldsymbol{x}_{1}-\boldsymbol{x}_{0}\|^{2}]+145\frac{\eta_{x,1}^{2}\kappa^{4}}{\beta}\sum_{i=1}^{t-1}\mathbb{E}[\|\boldsymbol{g}_{i}\|^{2}]+\frac{4\kappa\sigma^{2}(t-1)}{\ell^{2}M_{y}}\end{split}$
(113)

∎

###### Proof of Theorem D.1.

We begin by taking summation of Equation 92 (Lemma D.5) from $t=2$ to $t=T$
which yields:

$\begin{split}\frac{\eta_{x,1}}{2}\sum_{i=1}^{T-1}\mathbb{E}[\|\nabla\Phi(\boldsymbol{x}_{i})\|^{2}]&\leq\Phi(\boldsymbol{x}_{1})-\mathbb{E}[\Phi(\boldsymbol{x}_{T})]+\frac{3}{2}\eta_{x,1}\alpha^{2}\ell^{2}\|\boldsymbol{x}_{1}-\boldsymbol{x}_{0}\|^{2}\\\
&\quad-\frac{\eta_{x,1}}{2}(1-2\kappa\ell\eta_{x,1})\sum_{i=1}^{T-1}\mathbb{E}[\|\boldsymbol{g}_{i}\|^{2}]+\frac{3}{2}\eta_{x,1}^{3}\alpha^{2}\ell^{2}\sum_{i=1}^{T-2}\mathbb{E}[\|\boldsymbol{g}_{i}\|^{2}]\\\
&\quad+\frac{3}{2}\eta_{x,1}\ell^{2}\sum_{i=1}^{T-1}\|\boldsymbol{y}_{i}-\boldsymbol{y}^{*}_{i}\|^{2}+\frac{3}{2}\eta_{x,1}\alpha^{2}\ell^{2}\sum_{i=1}^{T-1}\mathbb{E}[\|\boldsymbol{y}_{i}-\boldsymbol{y}_{i-1}\|^{2}]\\\
&+3((1+\alpha)^{2}+1)\eta_{x,1}\frac{(T-1)\sigma^{2}}{M_{x}}\end{split}$ (114)

Now note that if $\eta_{x}\leq\frac{1}{2\kappa\ell}$ then we can drop
$\|\boldsymbol{g}_{T-1}\|^{2}$ term in above equation. By considering this,
and multiplying both sides by $\frac{2}{\eta_{x,1}}$ we get (also let
$\Delta=\Phi(\boldsymbol{x}_{1})-\min_{\boldsymbol{x}}\Phi(\boldsymbol{x})$) :

$\begin{split}\sum_{i=1}^{T-1}\mathbb{E}[\|\nabla\Phi(\boldsymbol{x}_{i})\|^{2}]&\leq\frac{2\Delta}{\eta_{x,1}}+3\alpha^{2}\ell^{2}\|\boldsymbol{x}_{1}-\boldsymbol{x}_{0}\|^{2}\\\
&\quad-(1-2\kappa\ell\eta_{x,1}-3\eta_{x,1}^{2}\alpha^{2}\ell^{2})\sum_{i=1}^{T-2}\mathbb{E}[\|\boldsymbol{g}_{i}\|^{2}]\\\
&\quad+3\ell^{2}\sum_{i=1}^{T-1}\mathbb{E}[\|\boldsymbol{y}^{*}_{i}-\boldsymbol{y}_{i}\|^{2}]+3\alpha^{2}\ell^{2}\sum_{i=1}^{T-1}\mathbb{E}[\|\boldsymbol{y}_{i}-\boldsymbol{y}_{i-1}\|^{2}]\\\
&+6((1+\alpha)^{2}+1)\frac{(T-1)\sigma^{2}}{M_{x}}\\\ \end{split}$ (115)

We can replace
$\sum_{i=1}^{T-1}\|\boldsymbol{y}_{i}^{*}-\boldsymbol{y}_{i}\|^{2}$ with its
upper bound obtained in Lemma D.6 to get:

$\begin{split}\sum_{i=1}^{T-1}\|\nabla\Phi(\boldsymbol{x}_{i})\|^{2}&\leq\frac{2\Delta}{\eta_{x,1}}+3\alpha^{2}\ell^{2}\|\boldsymbol{x}_{1}-\boldsymbol{x}_{0}\|^{2}+\frac{27}{7}\ell^{2}\|\boldsymbol{y}_{1}-\boldsymbol{y}^{*}_{1}\|^{2}\\\
&\quad-(1-2\kappa\ell\eta_{x,1}-3\eta_{x,1}^{2}\alpha^{2}\ell^{2}-\frac{54}{7}\eta_{x,1}^{2}\kappa^{2}\ell^{2})\sum_{i=1}^{T-2}\mathbb{E}[\|\boldsymbol{g}_{i}\|^{2}]\\\
&\quad+\frac{108}{7}\ell^{2}\sum_{i=2}^{T-1}\mathbb{E}[\|\boldsymbol{z}_{i}-\boldsymbol{y}^{*}_{i-1}\|^{2}]+3\ell^{2}\sum_{i=1}^{T-1}\mathbb{E}[\|\boldsymbol{y}_{i}-\boldsymbol{y}_{i-1}\|^{2}]\\\
&+6((1+\alpha)^{2}+1)\frac{(T-1)\sigma^{2}}{M_{x}}+\frac{6}{7}\frac{(T-2)\sigma^{2}}{M_{y}}\\\
\end{split}$ (116)

Now note that
$\frac{108}{7}\mathbb{E}[\|\boldsymbol{z}_{i+1}-\boldsymbol{y}^{*}_{i}\|^{2}]+3\beta\sum_{i=2}^{T-1}\mathbb{E}[\|\boldsymbol{y}_{i}-\boldsymbol{y}_{i-1}\|^{2}]\leq
15.5\mathbb{E}[\boldsymbol{r}_{i}]$. Therefore we have:

$\begin{split}\sum_{i=1}^{T-1}\|\nabla\Phi(\boldsymbol{x}_{i})\|^{2}&\leq\frac{2\Delta}{\eta_{x,1}}+3\alpha^{2}\ell^{2}\|\boldsymbol{x}_{1}-\boldsymbol{x}_{0}\|^{2}+\frac{27}{7}\ell^{2}\|\boldsymbol{y}_{1}-\boldsymbol{y}^{*}_{1}\|^{2}\\\
&\quad-(1-2\kappa\ell\eta_{x,1}-3\eta_{x,1}^{2}\alpha^{2}\ell^{2}-\frac{54}{7}\eta_{x,1}^{2}\kappa^{2}\ell^{2})\sum_{i=1}^{T-2}\mathbb{E}[\|\boldsymbol{g}_{i}\|^{2}]\\\
&\quad+15.5\ell^{2}\sum_{i=1}^{T-1}\mathbb{E}[\boldsymbol{r}_{i}]+6((1+\alpha)^{2}+1)\frac{(T-1)\sigma^{2}}{M_{x}}+\frac{6}{7}\frac{(T-2)\sigma^{2}}{M_{y}}\\\
\end{split}$ (117)

Furthermore, using Lemma D.7, we can find an upper bound on
$\sum_{i=1}^{T-1}\mathbb{E}[\boldsymbol{r}_{i}]$, and replacing it in above
equation yields:

$\begin{split}&\sum_{i=1}^{T-1}\|\nabla\Phi(\boldsymbol{x}_{i})\|^{2}\leq\frac{2\Delta}{\eta_{x,1}}+186\frac{\kappa\ell^{2}}{\beta}\mathbb{E}[\boldsymbol{r}_{1}]+11\kappa\ell^{2}\|\boldsymbol{x}_{1}-\boldsymbol{x}_{0}\|^{2}+3\alpha^{2}\ell^{2}\|\boldsymbol{x}_{1}-\boldsymbol{x}_{0}\|^{2}\\\
&\qquad+\frac{27}{7}\ell^{2}\|\boldsymbol{y}_{1}-\boldsymbol{y}^{*}_{1}\|^{2}-(1-2\kappa\ell\eta_{x,1}-3\eta_{x,1}^{2}\alpha^{2}\ell^{2}-\frac{54}{7}\eta_{x,1}^{2}\kappa^{2}\ell^{2}-2248\eta_{x,1}^{2}\frac{\kappa^{4}\ell^{2}}{\beta})\sum_{i=1}^{T-2}\mathbb{E}[\|\boldsymbol{g}_{i}\|^{2}]\\\
&\qquad+\frac{62\kappa\sigma^{2}(T-2)}{M_{y}}+6((1+\alpha)^{2}+1)\frac{(T-1)\sigma^{2}}{M_{x}}+\frac{6}{7}\frac{(T-2)\sigma^{2}}{M_{y}}\\\
\end{split}$ (118)

By letting $\eta_{x,1}=\frac{\sqrt{\beta}}{50\kappa^{2}\ell}$, and
$\eta_{x,2}\leq\frac{1}{25\ell}$, it holds that
$-(1-2\kappa\ell\eta_{x,1}-3\eta_{x,1}^{2}\alpha^{2}\ell^{2}-\frac{54}{7}\eta_{x,1}^{2}\kappa^{2}\ell^{2}-2248\eta_{x,1}^{2}\frac{\kappa^{4}\ell^{2}}{\beta})\sum_{i=1}^{T-2}\mathbb{E}[\|\boldsymbol{g}_{i}\|^{2}]\leq
0$. Therefore, with the choice of letting rate
$\eta_{x,1}=\frac{\sqrt{\beta}}{50\kappa^{2}\ell}$ and simplifying the terms,
we have:

$\begin{split}\frac{1}{T-1}\sum_{i=1}^{T-1}\mathbb{E}[\|\nabla\Phi(\boldsymbol{x}_{i})\|^{2}]&\leq
100\frac{\kappa^{2}\ell\Delta}{\sqrt{\beta}(T-1)}+186\frac{\kappa\ell^{2}}{\beta(T-1)}\|\boldsymbol{y}_{1}-\boldsymbol{y}^{*}_{1}+\eta_{y,1}\boldsymbol{g}_{y,1}-\eta_{y,2}\boldsymbol{g}_{y,0}\|^{2}\\\
&\quad+47\beta\frac{\kappa\ell^{2}}{T-1}\|\boldsymbol{y}_{1}-\boldsymbol{y}_{0}\|^{2}+\frac{(11\kappa+3\alpha^{2})\ell^{2}}{T-1}\|\boldsymbol{x}_{1}-\boldsymbol{x}_{0}\|^{2}\\\
&\quad+\frac{27}{7}\frac{\ell^{2}}{T-1}\|\boldsymbol{y}_{1}-\boldsymbol{y}^{*}_{1}\|^{2}+\frac{63\kappa\sigma^{2}}{M_{y}}+6((1+\alpha)^{2}+1)\frac{\sigma^{2}}{M_{x}}\end{split}$
(119)

Using Young’s inequality, and $\ell$-smoothness of $f$, we have:

$\begin{split}\|\boldsymbol{y}_{1}-\boldsymbol{y}^{*}_{1}+\eta_{y,1}\boldsymbol{g}_{y,1}-\eta_{y,2}\boldsymbol{g}_{y,0}\|^{2}&\leq
2\|\boldsymbol{y}_{1}-\boldsymbol{y}^{*}_{1}\|^{2}+2\|\eta_{y,2}(\boldsymbol{g}_{y,1}-\boldsymbol{g}_{y,0})+\eta_{y,2}(\beta-1)\boldsymbol{g}_{y,1}\|^{2}\\\
&\leq
2\|\boldsymbol{y}_{1}-\boldsymbol{y}^{*}_{1}\|^{2}+\frac{1}{9}\|x_{1}-x_{0}\|^{2}+\frac{1}{9}\|y_{1}-y_{0}\|^{2}+\frac{1-\beta}{9}\|\boldsymbol{y}_{1}-\boldsymbol{y}^{*}_{1}\|^{2}\end{split}$
(120)

Plugging this into Equation 119, we have:

$\begin{split}\frac{1}{T-1}\sum_{i=1}^{T-1}\mathbb{E}[\|\nabla\Phi(\boldsymbol{x}_{i})\|^{2}]&\leq
100\frac{\kappa^{2}\ell\Delta}{T-1}+376\frac{\kappa\ell^{2}}{\beta(T-1)}\|\boldsymbol{y}_{1}-\boldsymbol{y}^{*}_{1}\|^{2}\\\
&\quad+68\frac{\kappa\ell^{2}}{\beta(T-1)}\|\boldsymbol{y}_{1}-\boldsymbol{y}_{0}\|^{2}+\frac{(32\kappa+3\alpha^{2})\ell^{2}}{\beta(T-1)}\|\boldsymbol{x}_{1}-\boldsymbol{x}_{0}\|^{2}\\\
&\quad+\frac{63\kappa\sigma^{2}}{M_{y}}+6((1+\alpha)^{2}+1)\frac{\sigma^{2}}{M_{x}}\end{split}$
(121)

which completes the proof as stated. ∎

### References

  * Abernethy et al. [2021] J. Abernethy, K. A. Lai, and A. Wibisono.  Last-iterate convergence rates for min-max optimization: Convergence of hamiltonian gradient descent and consensus optimization.  In _Algorithmic Learning Theory_ , pages 3–47. PMLR, 2021.
  * Basar and Olsder [1999] T. Basar and G. Olsder.  Dynamic noncooperative game theory, vol. 23 (siam, philadelphia).  1999\.
  * Cai et al. [2022] Y. Cai, A. Oikonomou, and W. Zheng.  Tight last-iterate convergence of the extragradient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities.  _arXiv preprint arXiv:2204.09228_ , 2022.
  * Chen et al. [2021a] T. Chen, Y. Sun, and W. Yin.  Tighter analysis of alternating stochastic gradient method for stochastic nested problems.  _arXiv preprint arXiv:2106.13781_ , 2021a.
  * Chen et al. [2017] Y. Chen, G. Lan, and Y. Ouyang.  Accelerated schemes for a class of variational inequalities.  _Mathematical Programming_ , 165(1):113–149, 2017\.
  * Chen et al. [2021b] Z. Chen, S. Ma, and Y. Zhou.  Accelerated proximal alternating gradient-descent-ascent for nonconvex minimax machine learning.  _arXiv preprint arXiv:2112.11663_ , 2021b.
  * Dang and Lan [2015] C. D. Dang and G. Lan.  On the convergence properties of non-euclidean extragradient methods for variational inequalities with generalized monotone operators.  _Computational Optimization and applications_ , 60(2):277–310, 2015.
  * Daskalakis et al. [2017] C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng.  Training gans with optimism.  _arXiv preprint arXiv:1711.00141_ , 2017.
  * Davis and Drusvyatskiy [2019] D. Davis and D. Drusvyatskiy.  Stochastic model-based minimization of weakly convex functions.  _SIAM Journal on Optimization_ , 29(1):207–239, 2019.
  * Diakonikolas et al. [2021] J. Diakonikolas, C. Daskalakis, and M. Jordan.  Efficient methods for structured nonconvex-nonconcave min-max optimization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2746–2754. PMLR, 2021.
  * Drori and Shamir [2020] Y. Drori and O. Shamir.  The complexity of finding stationary points with stochastic gradient descent.  In _International Conference on Machine Learning_ , pages 2658–2667. PMLR, 2020.
  * Fallah et al. [2020] A. Fallah, A. Ozdaglar, and S. Pattathil.  An optimal multistage stochastic gradient method for minimax problems.  In _2020 59th IEEE Conference on Decision and Control (CDC)_ , pages 3573–3579. IEEE, 2020.
  * Gidel et al. [2018] G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien.  A variational inequality perspective on generative adversarial networks.  _arXiv preprint arXiv:1802.10551_ , 2018.
  * Goodfellow et al. [2014a] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio.  Generative adversarial nets.  _Advances in neural information processing systems_ , 27, 2014a.
  * Goodfellow et al. [2014b] I. J. Goodfellow, J. Shlens, and C. Szegedy.  Explaining and harnessing adversarial examples.  _arXiv preprint arXiv:1412.6572_ , 2014b.
  * Gorbunov et al. [2022a] E. Gorbunov, H. Berard, G. Gidel, and N. Loizou.  Stochastic extragradient: General analysis and improved rates.  In _International Conference on Artificial Intelligence and Statistics_ , pages 7865–7901. PMLR, 2022a.
  * Gorbunov et al. [2022b] E. Gorbunov, N. Loizou, and G. Gidel.  Extragradient method: O (1/k) last-iterate convergence for monotone variational inequalities and connections with cocoercivity.  In _International Conference on Artificial Intelligence and Statistics_ , pages 366–402. PMLR, 2022b.
  * Guo et al. [2020] Z. Guo, Z. Yuan, Y. Yan, and T. Yang.  Fast objective & duality gap convergence for nonconvex-strongly-concave min-max problems.  _arXiv preprint arXiv:2006.06889_ , 2020.
  * Hajizadeh et al. [2022] S. Hajizadeh, H. Lu, and B. Grimmer.  On the linear convergence of extra-gradient methods for nonconvex-nonconcave minimax problems.  _arXiv preprint arXiv:2201.06167_ , 2022.
  * Han et al. [2021] Y. Han, G. Xie, and Z. Zhang.  Lower complexity bounds of finite-sum optimization problems: The results and construction.  _ArXiv_ , abs/2103.08280, 2021.
  * Hast et al. [2013] M. Hast, K. J. Åström, B. Bernhardsson, and S. Boyd.  Pid design by convex-concave optimization.  In _2013 European Control Conference (ECC)_ , pages 4460–4465. IEEE, 2013.
  * Hommes and Ochea [2012] C. H. Hommes and M. I. Ochea.  Multiple equilibria and limit cycles in evolutionary games with logit dynamics.  _Games and Economic Behavior_ , 74(1):434–441, 2012.
  * Hsieh et al. [2019] Y.-G. Hsieh, F. Iutzeler, J. Malick, and P. Mertikopoulos.  On the convergence of single-call stochastic extra-gradient methods.  _arXiv preprint arXiv:1908.08465_ , 2019.
  * Jin et al. [2019] C. Jin, P. Netrapalli, and M. I. Jordan.  What is local optimality in nonconvex-nonconcave minimax optimization?  _arXiv preprint arXiv:1902.00618_ , 2019.
  * Kingma and Ba [2014] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kong and Monteiro [2019] W. Kong and R. D. Monteiro.  An accelerated inexact proximal point method for solving nonconvex-concave min-max problems.  _arXiv preprint arXiv:1905.13433_ , 2019.
  * Li et al. [2021] H. Li, Y. Tian, J. Zhang, and A. Jadbabaie.  Complexity lower bounds for nonconvex-strongly-concave min-max optimization.  _ArXiv_ , abs/2104.08708, 2021.
  * Liang and Stokes [2019] T. Liang and J. Stokes.  Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 907–915. PMLR, 2019.
  * Lin et al. [2019] T. Lin, C. Jin, and M. I. Jordan.  On gradient descent ascent for nonconvex-concave minimax problems.  _arXiv preprint arXiv:1906.00331_ , 2019.
  * Lin et al. [2020a] T. Lin, C. Jin, and M. Jordan.  On gradient descent ascent for nonconvex-concave minimax problems.  In _International Conference on Machine Learning_ , pages 6083–6093. PMLR, 2020a.
  * Lin et al. [2020b] T. Lin, C. Jin, and M. I. Jordan.  Near-optimal algorithms for minimax optimization.  In _Conference on Learning Theory_ , pages 2738–2779. PMLR, 2020b.
  * Liu et al. [2019a] M. Liu, Y. Mroueh, J. Ross, W. Zhang, X. Cui, P. Das, and T. Yang.  Towards better understanding of adaptive gradient algorithms in generative adversarial nets.  _arXiv preprint arXiv:1912.11940_ , 2019a.
  * Liu et al. [2019b] M. Liu, Y. Mroueh, W. Zhang, X. Cui, T. Yang, and P. Das.  Decentralized parallel algorithm for training generative adversarial nets.  _arXiv preprint arXiv:1910.12999_ , 2019b.
  * Loizou et al. [2020] N. Loizou, H. Berard, A. Jolicoeur-Martineau, P. Vincent, S. Lacoste-Julien, and I. Mitliagkas.  Stochastic hamiltonian gradient methods for smooth games.  In _International Conference on Machine Learning_ , pages 6370–6381. PMLR, 2020.
  * Loizou et al. [2021] N. Loizou, H. Berard, G. Gidel, I. Mitliagkas, and S. Lacoste-Julien.  Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity.  _Advances in Neural Information Processing Systems_ , 34:19095–19108, 2021.
  * Lu et al. [2020] S. Lu, I. Tsaknakis, M. Hong, and Y. Chen.  Hybrid block successive approximation for one-sided non-convex min-max problems: algorithms and applications.  _IEEE Transactions on Signal Processing_ , 68:3676–3691, 2020.
  * Madry et al. [2017] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_ , 2017.
  * Mertikopoulos et al. [2018] P. Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras.  Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile.  _arXiv preprint arXiv:1807.02629_ , 2018.
  * Mokhtari et al. [2020a] A. Mokhtari, A. Ozdaglar, and S. Pattathil.  A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1497–1507. PMLR, 2020a.
  * Mokhtari et al. [2020b] A. Mokhtari, A. E. Ozdaglar, and S. Pattathil.  Convergence rate of o(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems.  _SIAM Journal on Optimization_ , 30(4):3230–3251, 2020b.
  * Nouiehed et al. [2019] M. Nouiehed, M. Sanjabi, T. Huang, J. D. Lee, and M. Razaviyayn.  Solving a class of non-convex min-max games using iterative first order methods.  _arXiv preprint arXiv:1902.08297_ , 2019.
  * Pethick et al. [2022] T. Pethick, P. Patrinos, O. Fercoq, V. Cevherå, et al.  Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems.  In _International Conference on Learning Representations_ , 2022.
  * Qiu et al. [2020] S. Qiu, Z. Yang, X. Wei, J. Ye, and Z. Wang.  Single-timescale stochastic nonconvex-concave optimization for smooth nonlinear td learning.  _arXiv preprint arXiv:2008.10103_ , 2020.
  * Rafique et al. [2018] H. Rafique, M. Liu, Q. Lin, and T. Yang.  Non-convex min-max optimization: Provable algorithms and applications in machine learning.  _arXiv preprint arXiv:1810.02060_ , 2018.
  * Rafique et al. [2021] H. Rafique, M. Liu, Q. Lin, and T. Yang.  Weakly-convex–concave min–max optimization: provable algorithms and applications in machine learning.  _Optimization Methods and Software_ , pages 1–35, 2021.
  * Sinha et al. [2017] A. Sinha, H. Namkoong, R. Volpi, and J. Duchi.  Certifying some distributional robustness with principled adversarial training.  _arXiv preprint arXiv:1710.10571_ , 2017.
  * Song et al. [2021] C. Song, Z. Zhou, Y. Zhou, Y. Jiang, and Y. Ma.  Optimistic dual extrapolation for coherent non-monotone variational inequalities.  _arXiv preprint arXiv:2103.04410_ , 2021.
  * Thekumparampil et al. [2019] K. K. Thekumparampil, P. Jain, P. Netrapalli, and S. Oh.  Efficient algorithms for smooth minimax optimization.  In _Advances in Neural Information Processing Systems_ , pages 12659–12670, 2019.
  * Tseng [1995] P. Tseng.  On linear convergence of iterative methods for the variational inequality problem.  _Journal of Computational and Applied Mathematics_ , 60(1-2):237–252, 1995.
  * Von Neumann and Morgenstern [2007] J. Von Neumann and O. Morgenstern.  _Theory of games and economic behavior_.  Princeton university press, 2007.
  * Yang et al. [2020] J. Yang, N. Kiyavash, and N. He.  Global convergence and variance-reduced optimization for a class of nonconvex-nonconcave minimax problems.  _arXiv preprint arXiv:2002.09621_ , 2020.
  * Yang et al. [2021] J. Yang, A. Orvieto, A. Lucchi, and N. He.  Faster single-loop algorithms for minimax optimization without strong concavity.  _arXiv preprint arXiv:2112.05604_ , 2021.
  * Zhang et al. [2020] J. Zhang, P. Xiao, R. Sun, and Z. Luo.  A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems.  _Advances in Neural Information Processing Systems_ , 33:7377–7389, 2020.
  * Zhang et al. [2021a] K. Zhang, Z. Yang, and T. Başar.  Multi-agent reinforcement learning: A selective overview of theories and algorithms.  _Handbook of Reinforcement Learning and Control_ , pages 321–384, 2021a.
  * Zhang et al. [2021b] S. Zhang, J. Yang, C. Guzmán, N. Kiyavash, and N. He.  The complexity of nonconvex-strongly-concave minimax optimization.  _arXiv preprint arXiv:2103.15888_ , 2021b.