$\displaystyle\left(1-\tfrac{\mu\eta}{2}\right)^{T}\left((d_{\mathcal{M}}(x_{0},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{0},y^{\star}))^{2}\right)+6\overline{\xi}_{0}\eta^{2}\sigma^{2}\left(\sum_{t=0}^{T-1}\left(1-\tfrac{\mu\eta}{2}\right)^{t}\right)$
$\displaystyle\leq$
$\displaystyle\left(1-\tfrac{\mu\eta}{2}\right)^{T}D_{0}+\tfrac{12\overline{\xi}_{0}\eta\sigma^{2}}{\mu}.$

Since
$\eta=\min\\{\frac{1}{24\ell\sqrt{\tau_{0}}},\frac{\underline{\xi}_{0}}{2\mu},\tfrac{2(\log(T)+\log(\mu^{2}D_{0}\sigma^{-2}))}{\mu
T}\\}$, we have

$\displaystyle\left(1-\tfrac{\mu\eta}{2}\right)^{T}D_{0}$ $\displaystyle\leq$
$\displaystyle\left(1-\min\left\\{\tfrac{1}{48\kappa\sqrt{\tau_{0}}},\tfrac{\underline{\xi}_{0}}{4}\right\\}\right)^{T}D_{0}+\left(1-\tfrac{\log(\mu^{2}D_{0}\sigma^{-2}T)}{T}\right)^{T}D_{0}$
$\displaystyle\overset{1+x\leq e^{x}}{\leq}$
$\displaystyle\left(1-\min\left\\{\tfrac{1}{48\kappa\sqrt{\tau_{0}}},\tfrac{\underline{\xi}_{0}}{4}\right\\}\right)^{T}D_{0}+\tfrac{\sigma^{2}}{\mu^{2}T},$

and

$\tfrac{12\overline{\xi}_{0}\eta\sigma^{2}}{\mu}\leq\tfrac{24\overline{\xi}_{0}\sigma^{2}}{\mu^{2}T}\log\left(\tfrac{\mu^{2}D_{0}T}{\sigma^{2}}\right).$

Putting these pieces together yields that

${\mathbb{E}}\left[(d_{\mathcal{M}}(x_{T},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{T},y^{\star}))^{2}\right]\leq\left(1-\min\left\\{\tfrac{1}{48\kappa\sqrt{\tau_{0}}},\tfrac{\underline{\xi}_{0}}{4}\right\\}\right)^{T}D_{0}+\tfrac{\sigma^{2}}{\mu^{2}T}+\tfrac{24\overline{\xi}_{0}\sigma^{2}}{\mu^{2}T}\log\left(\tfrac{\mu^{2}D_{0}T}{\sigma^{2}}\right).$

This completes the proof.

###  E.4 Proof of Theorem 3.3

By the inductive formulas of
$\bar{x}_{t+1}=\textnormal{Exp}_{\bar{x}_{t}}(\tfrac{1}{t+1}\cdot\textnormal{Exp}_{\bar{x}_{t}}^{-1}(\hat{x}_{t}))$
and
$\bar{y}_{t+1}=\textnormal{Exp}_{\bar{y}_{t}}(\tfrac{1}{t+1}\cdot\textnormal{Exp}_{\bar{y}_{t}}^{-1}(\hat{y}_{t}))$
and using Zhang et al. [2022, Lemma C.2], we have

$f(\bar{x}_{T},y^{\star})-f(x^{\star},\bar{y}_{T})\leq\tfrac{1}{T}\left(\sum_{t=0}^{T-1}f(\hat{x}_{t},y^{\star})-f(x^{\star},\hat{y}_{t})\right).$

Plugging the above inequality into the inequality from Lemma E.2 yields that
(recall that $\mu=0$ in geodesically convex-concave setting here)

$\displaystyle{\mathbb{E}}[f(\bar{x}_{T},y^{\star})-f(x^{\star},\bar{y}_{T})]\leq\tfrac{1}{2\eta
T}\left((d_{\mathcal{M}}(x_{0},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{0},y^{\star}))^{2}\right)$
$\displaystyle+\tfrac{1}{T}\left(6\overline{\xi}_{0}\eta\ell^{2}-\tfrac{1}{2\eta}\underline{\xi}_{0}\right)\left(\sum_{t=0}^{T-1}{\mathbb{E}}\left[(d_{\mathcal{M}}(\hat{x}_{t},x_{t}))^{2}+(d_{\mathcal{N}}(\hat{y}_{t},y_{t}))^{2}\right]\right)+3\overline{\xi}_{0}\eta\sigma^{2}.$

Since $\eta\leq\frac{1}{4\ell\sqrt{\tau_{0}}}$, we have
$6\overline{\xi}_{0}\eta\ell^{2}-\tfrac{1}{2\eta}\underline{\xi}_{0}\leq 0$.
Then, this together with
$(d_{\mathcal{M}}(x_{0},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{0},y^{\star}))^{2}\leq
D_{0}$ implies that

${\mathbb{E}}[f(\bar{x}_{T},y^{\star})-f(x^{\star},\bar{y}_{T})]\leq\tfrac{D_{0}}{2\eta
T}+3\overline{\xi}_{0}\eta\sigma^{2}.$

Since
$\eta=\min\\{\frac{1}{4\ell\sqrt{\tau_{0}}},\tfrac{1}{\sigma}\sqrt{\tfrac{D_{0}}{\overline{\xi}_{0}T}}\\}$,
we have

$\tfrac{D_{0}}{2\eta T}\leq\tfrac{2\ell
D_{0}\sqrt{\tau_{0}}}{T}+\tfrac{\sigma}{2}\sqrt{\tfrac{\overline{\xi}_{0}D_{0}}{T}},$

and

$3\overline{\xi}_{0}\eta\sigma^{2}\leq
3\sigma\sqrt{\tfrac{\overline{\xi}_{0}D_{0}}{T}}.$

Putting these pieces together yields that

${\mathbb{E}}[f(\bar{x}_{T},y^{\star})-f(x^{\star},\bar{y}_{T})]\leq\tfrac{2\ell
D_{0}\sqrt{\tau_{0}}}{T}+\tfrac{7\sigma}{2}\sqrt{\tfrac{\overline{\xi}_{0}D_{0}}{T}}.$

This completes the proof.

##  Appendix F Missing Proofs for Riemannian Gradient Descent Ascent

In this section, we present some technical lemmas for analyzing the
convergence property of Algorithm 3 and 4. We also give the proofs of Theorem
D.1, D.2, D.3 and D.4.

###  F.1 Technical lemmas

We provide two technical lemmas for analyzing Algorithm 3 and 4 respectively.
The first lemma gives a key inequality that is satisfied by the iterates
generated by Algorithm 3.

###### Lemma F.1

Under Assumption D.1 (or Assumption D.2) and let
$\\{(x_{t},y_{t})\\}_{t=0}^{T-1}$ be generated by Algorithm 3 with the
stepsize $\eta_{t}>0$. Then, we have

$\displaystyle
f(x_{t},y^{\star})-f(x^{\star},y_{t})\leq\tfrac{1}{2\eta_{t}}\left((d_{\mathcal{M}}(x_{t},x^{\star}))^{2}-(d_{\mathcal{M}}(x_{t+1},x^{\star}))^{2}\right)$
$\displaystyle+\tfrac{1}{2\eta_{t}}\left((d_{\mathcal{N}}(y_{t},y^{\star}))^{2}-(d_{\mathcal{N}}(y_{t+1},y^{\star}))^{2}\right)-\tfrac{\mu}{2}(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}-\tfrac{\mu}{2}(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}+\overline{\xi}_{0}\eta_{t}L^{2},$

where $(x^{\star},y^{\star})\in\mathcal{M}\times\mathcal{N}$ is a global
saddle point of $f$.

Proof. Since $f$ is geodesically strongly-concave-strongly-concave with the
modulus $\mu\geq 0$ (here $\mu=0$ means that $f$ is geodesically concave-
concave), we have

$\displaystyle
f(x_{t},y^{\star})-f(x^{\star},y_{t})=f(x_{t},y_{t})-f(x^{\star},y_{t})-(f(x_{t},y_{t})-f(x_{t},y^{\star}))$
$\displaystyle\leq$
$\displaystyle-\langle\textnormal{subgrad}_{x}f(x_{t},y_{t}),\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})\rangle+\langle\textnormal{subgrad}_{y}f(x_{t},y_{t}),\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle-\tfrac{\mu}{2}(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}-\tfrac{\mu}{2}(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}.$

Recalling also from the scheme of Algorithm 3 that we have

$\displaystyle x_{t+1}$ $\displaystyle\leftarrow$
$\displaystyle\textnormal{Exp}_{x_{t}}(-\eta_{t}\cdot\textnormal{subgrad}_{x}f(x_{t},y_{t})),$
$\displaystyle y_{t+1}$ $\displaystyle\leftarrow$
$\displaystyle\textnormal{Exp}_{y_{t}}(\eta_{t}\cdot\textnormal{subgrad}_{y}f(x_{t},y_{t})).$

By the definition of an exponential map, we have

$\begin{array}[]{lcl}\textnormal{Exp}_{x_{t}}^{-1}(x_{t+1})&=&-\eta_{t}\cdot\textnormal{subgrad}_{x}f(x_{t},y_{t}),\\\
\textnormal{Exp}_{y_{t}}^{-1}(y_{t+1})&=&\eta_{t}\cdot\textnormal{subgrad}_{y}f(x_{t},y_{t}).\end{array}$
(F.1)

This implies that

$\displaystyle-\langle\textnormal{subgrad}_{x}f(x_{t},y_{t}),\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})\rangle$
$\displaystyle=$
$\displaystyle\tfrac{1}{\eta_{t}}\langle\textnormal{Exp}_{x_{t}}^{-1}(x_{t+1}),\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})\rangle,$
$\displaystyle\langle\textnormal{subgrad}_{y}f(x_{t},y_{t}),\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle$
$\displaystyle=$
$\displaystyle\tfrac{1}{\eta_{t}}\langle\textnormal{Exp}_{y_{t}}^{-1}(y_{t+1}),\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle.$

Putting these pieces together yields that

$\displaystyle
f(x_{t},y^{\star})-f(x^{\star},y_{t})\leq\tfrac{1}{\eta_{t}}\langle\textnormal{Exp}_{x_{t}}^{-1}(x_{t+1}),\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})\rangle$
$\displaystyle+\tfrac{1}{\eta_{t}}\langle\textnormal{Exp}_{y_{t}}^{-1}(y_{t+1}),\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle-\tfrac{\mu}{2}(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}-\tfrac{\mu}{2}(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}.$

It suffices to bound the terms in the right-hand side of Eq. (F.1) by
leveraging the celebrated comparison inequalities on Riemannian manifold with
lower bounded sectional curvature (see Proposition C.2). More specifically, we
define the constants using $\overline{\xi}(\cdot,\cdot)$ and
$\underline{\xi}(\cdot,\cdot)$ from Proposition C.2 as follows,

$\overline{\xi}_{0}=\overline{\xi}(\kappa_{\min},D).$

By Proposition C.2 and using that
$\max\\{d_{\mathcal{M}}(x_{t},x^{\star}),d_{\mathcal{N}}(y_{t},y^{\star})\\}\leq
D$, we have

$\displaystyle\langle\textnormal{Exp}_{x_{t}}^{-1}(x_{t+1}),\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})\rangle$
$\displaystyle\leq$
$\displaystyle\tfrac{1}{2}\left(\overline{\xi}_{0}(d_{\mathcal{M}}(x_{t},x_{t+1}))^{2}+(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}-(d_{\mathcal{M}}(x_{t+1},x^{\star}))^{2}\right),$
$\displaystyle\langle\textnormal{Exp}_{y_{t}}^{-1}(y_{t+1}),\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle$
$\displaystyle\leq$
$\displaystyle\tfrac{1}{2}\left(\overline{\xi}_{0}(d_{\mathcal{N}}(y_{t},y_{t+1}))^{2}+(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}-(d_{\mathcal{N}}(y_{t+1},y^{\star}))^{2}\right).$

Since $f$ is geodesically $L$-Lipschitz, we have

$\|\textnormal{subgrad}_{x}f(x_{t},y_{t})\|\leq
L,\quad\|\textnormal{subgrad}_{y}f(x_{t},y_{t})\|\leq L.$

By the definition of an exponential map and Riemannian metric, we have

$\begin{array}[]{lll}d_{\mathcal{M}}(x_{t},x_{t+1})&=&\|\textnormal{Exp}_{x_{t}}^{-1}(x_{t+1})\|\overset{\textnormal{Eq.~{}\eqref{inequality:RGDA-
opt}}}{=}\|\eta_{t}\cdot\textnormal{subgrad}_{x}f(x_{t},y_{t})\|\leq\eta_{t}L,\\\
d_{\mathcal{N}}(y_{t},y_{t+1})&=&\|\textnormal{Exp}_{y_{t}}^{-1}(y_{t+1})\|\overset{\textnormal{Eq.~{}\eqref{inequality:RGDA-
opt}}}{=}\|\eta_{t}\cdot\textnormal{subgrad}_{y}f(x_{t},y_{t})\|\leq\eta_{t}L.\end{array}$

Putting these pieces together yields that

$\displaystyle\langle\textnormal{Exp}_{x_{t}}^{-1}(x_{t+1}),\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})\rangle$
$\displaystyle\leq$
$\displaystyle\tfrac{1}{2}\left(\overline{\xi}_{0}\eta_{t}^{2}L^{2}+(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}-(d_{\mathcal{M}}(x_{t+1},x^{\star}))^{2}\right),$
$\displaystyle\langle\textnormal{Exp}_{y_{t}}^{-1}(y_{t+1}),\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle$
$\displaystyle\leq$
$\displaystyle\tfrac{1}{2}\left(\overline{\xi}_{0}\eta_{t}^{2}L^{2}+(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}-(d_{\mathcal{N}}(y_{t+1},y^{\star}))^{2}\right).$

Plugging the above inequalities into Eq. (F.1) yields the desired inequality.
$\Box$

The second lemma gives another key inequality that is satisfied by the
iterates generated by Algorithm 4.

###### Lemma F.2

Under Assumption D.1 (or Assumption D.2) and the noisy model (cf. Eq. (D.2)
and (D.3)) and let $\\{(x_{t},y_{t})\\}_{t=0}^{T-1}$ be generated by Algorithm
4 with the stepsize $\eta_{t}>0$. Then, we have

$\displaystyle{\mathbb{E}}[f(x_{t},y^{\star})-f(x^{\star},y_{t})]\leq\tfrac{1}{2\eta_{t}}{\mathbb{E}}\left[(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}-(d_{\mathcal{M}}(x_{t+1},x^{\star}))^{2}\right]$
$\displaystyle+\tfrac{1}{2\eta_{t}}{\mathbb{E}}\left[(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}-(d_{\mathcal{N}}(y_{t+1},y^{\star}))^{2}\right]-\tfrac{\mu}{2}{\mathbb{E}}\left[(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}\right]+2\overline{\xi}_{0}\eta_{t}(L^{2}+\sigma^{2}),$

where $(x^{\star},y^{\star})\in\mathcal{M}\times\mathcal{N}$ is a global
saddle point of $f$.

Proof. Using the same argument, we have ($\mu=0$ refers to geodesically
convex-concave case)

$\displaystyle
f(x_{t},y^{\star})-f(x^{\star},y_{t})=f(x_{t},y_{t})-f(x^{\star},y_{t})-(f(x_{t},y_{t})-f(x_{t},y^{\star}))$
$\displaystyle\leq$
$\displaystyle-\langle\textnormal{subgrad}_{x}f(x_{t},y_{t}),\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})\rangle+\langle\textnormal{subgrad}_{y}f(x_{t},y_{t}),\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle-\tfrac{\mu}{2}(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}-\tfrac{\mu}{2}(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}.$

Combining the arguments used in Lemma F.1 and the scheme of Algorithm 2, we
have

$\displaystyle-\langle
g_{x}^{t},\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})\rangle$ $\displaystyle=$
$\displaystyle\tfrac{1}{\eta_{t}}\langle\textnormal{Exp}_{x_{t}}^{-1}(x_{t+1}),\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})\rangle,$
$\displaystyle\langle
g_{y}^{t},\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle$ $\displaystyle=$
$\displaystyle\tfrac{1}{\eta_{t}}\langle\textnormal{Exp}_{y_{t}}^{-1}(y_{t+1}),\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle.$

Putting these pieces together with Eq. (D.2) yields that

$\displaystyle
f(x_{t},y^{\star})-f(x^{\star},y_{t})\leq\tfrac{1}{\eta_{t}}\langle\textnormal{Exp}_{x_{t}}^{-1}(x_{t+1}),\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})$
$\displaystyle+\tfrac{1}{\eta_{t}}\langle\textnormal{Exp}_{y_{t}}^{-1}(y_{t+1}),\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle-\tfrac{\mu}{2}(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}-\tfrac{\mu}{2}(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}+\langle\xi_{x}^{t},\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})\rangle-\langle\xi_{y}^{t},\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle.$

By the same argument as used in Lemma F.1 and Eq. (D.2), we have

$\displaystyle\langle\textnormal{Exp}_{x_{t}}^{-1}(x_{t+1}),\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})\rangle$
$\displaystyle\leq$
$\displaystyle\tfrac{1}{2}\left(\overline{\xi}_{0}(d_{\mathcal{M}}(x_{t},x_{t+1}))^{2}+(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}-(d_{\mathcal{M}}(x_{t+1},x^{\star}))^{2}\right),$
$\displaystyle\langle\textnormal{Exp}_{y_{t}}^{-1}(y_{t+1}),\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle$
$\displaystyle\leq$
$\displaystyle\tfrac{1}{2}\left(\overline{\xi}_{0}(d_{\mathcal{N}}(y_{t},y_{t+1}))^{2}+(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}-(d_{\mathcal{N}}(y_{t+1},y^{\star}))^{2}\right),$

and

$\begin{array}[]{lll}d_{\mathcal{M}}(x_{t},x_{t+1})&=&\|\textnormal{Exp}_{x_{t}}^{-1}(x_{t+1})\|\
=\ \|\eta_{t}\cdot g_{x}^{t}\|\ \leq\ \eta_{t}(L+\|\xi_{x}^{t}\|),\\\
d_{\mathcal{N}}(y_{t},y_{t+1})&=&\|\textnormal{Exp}_{y_{t}}^{-1}(y_{t+1})\|\
=\ \|\eta_{t}\cdot g_{y}^{t}\|\ \leq\ \eta_{t}(L+\|\xi_{y}^{t}\|).\end{array}$

Therefore, we have

$\displaystyle\langle\textnormal{Exp}_{x_{t}}^{-1}(x_{t+1}),\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})\rangle+\langle\textnormal{Exp}_{y_{t}}^{-1}(y_{t+1}),\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle$
$\displaystyle\leq$
$\displaystyle\tfrac{1}{2}\overline{\xi}_{0}\eta_{t}^{2}(4L^{2}+2\|\xi_{x}^{t}\|^{2}+2\|\xi_{y}^{t}\|^{2})+\tfrac{1}{2}\left((d_{\mathcal{M}}(x_{t},x^{\star}))^{2}-(d_{\mathcal{M}}(x_{t+1},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}-(d_{\mathcal{N}}(y_{t+1},y^{\star}))^{2}\right).$

Plugging the above inequalities into Eq. (F.1) yields that

$\displaystyle
f(x_{t},y^{\star})-f(x^{\star},y_{t})\leq\tfrac{1}{2\eta_{t}}\left((d_{\mathcal{M}}(x_{t},x^{\star}))^{2}-(d_{\mathcal{M}}(x_{t+1},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}-(d_{\mathcal{N}}(y_{t+1},y^{\star}))^{2}\right)$
$\displaystyle+\overline{\xi}_{0}\eta_{t}(2L^{2}+\|\xi_{x}^{t}\|^{2}+\|\xi_{y}^{t}\|^{2})-\tfrac{\mu}{2}(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}-\tfrac{\mu}{2}(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}+\langle\xi_{x}^{t},\textnormal{Exp}_{x_{t}}^{-1}(x^{\star})\rangle-\langle\xi_{y}^{t},\textnormal{Exp}_{y_{t}}^{-1}(y^{\star})\rangle.$

Taking the expectation of both sides and using Eq. (D.3) yields the desired
inequality. $\Box$

###  F.2 Proof of Theorem D.1

Since $(x^{\star},y^{\star})\in\mathcal{M}\times\mathcal{N}$ is a global
saddle point of $f$, we have $f(x_{t},y^{\star})-f(x^{\star},y_{t})\geq 0$.
Plugging this inequality into the inequality from Lemma F.1 yields that

$(d_{\mathcal{M}}(x_{t+1},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{t+1},y^{\star}))^{2}\leq(1-\mu\eta_{t})\left((d_{\mathcal{M}}(x_{t},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}\right)+2\overline{\xi}_{0}\eta_{t}^{2}L^{2}.$

Since $\eta_{t}=\frac{1}{\mu}\min\\{1,\frac{2}{t}\\}$, we have

$(d_{\mathcal{M}}(x_{t+1},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{t+1},y^{\star}))^{2}\leq(1-\tfrac{2}{t})\left((d_{\mathcal{M}}(x_{t},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}\right)+\tfrac{8\overline{\xi}_{0}L^{2}}{\mu^{2}t^{2}},\quad\textnormal{for
all }t\geq 2.$

Letting $\\{b_{t}\\}_{t\geq 1}$ be a nonnegative sequence such that
$a_{t+1}\leq(1-\frac{P}{t})a_{t}+\frac{Q}{t^{2}}$ where $P>1$ and $Q>0$. Then,
Chung [1954] proved that $a_{t}\leq\frac{Q}{P-1}\frac{1}{t}$. Therefore, we
have

$(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}\leq\tfrac{8\overline{\xi}_{0}L^{2}}{\mu^{2}t},\quad\textnormal{for
all }t\geq 2.$

This completes the proof.

###  F.3 Proof of Theorem D.2

By the inductive formulas of
$\bar{x}_{t+1}=\textnormal{Exp}_{\bar{x}_{t}}(\tfrac{1}{t+1}\cdot\textnormal{Exp}_{\bar{x}_{t}}^{-1}(x_{t}))$
and
$\bar{y}_{t+1}=\textnormal{Exp}_{\bar{y}_{t}}(\tfrac{1}{t+1}\cdot\textnormal{Exp}_{\bar{y}_{t}}^{-1}(y_{t}))$
and using Zhang et al. [2022, Lemma C.2], we have

$f(\bar{x}_{T},y^{\star})-f(x^{\star},\bar{y}_{T})\leq\tfrac{1}{T}\left(\sum_{t=0}^{T-1}f(x_{t},y^{\star})-f(x^{\star},y_{t})\right).$

Plugging the above inequality into the inequality from Lemma F.1 yields that
(recall that $\mu=0$ in geodesically convex-concave setting and
$\eta_{t}=\eta=\tfrac{1}{L}\sqrt{\tfrac{D_{0}}{2\overline{\xi}_{0}T}}$)

$f(\bar{x}_{T},y^{\star})-f(x^{\star},\bar{y}_{T})\leq\tfrac{1}{2\eta
T}\left((d_{\mathcal{M}}(x_{0},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{0},y^{\star}))^{2}\right)+\overline{\xi}_{0}\eta
L^{2}.$

This together with
$(d_{\mathcal{M}}(x_{0},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{0},y^{\star}))^{2}\leq
D_{0}$ implies that

$f(\bar{x}_{T},y^{\star})-f(x^{\star},\bar{y}_{T})\leq\tfrac{D_{0}}{2\eta
T}+\overline{\xi}_{0}\eta L^{2}.$

Since $\eta=\tfrac{1}{L}\sqrt{\tfrac{D_{0}}{2\overline{\xi}_{0}T}}$, we have

$f(\bar{x}_{T},y^{\star})-f(x^{\star},\bar{y}_{T})\leq
L\sqrt{\tfrac{2\overline{\xi}_{0}D_{0}}{T}}.$

This completes the proof.

###  F.4 Proof of Theorem D.3

Since $(x^{\star},y^{\star})\in\mathcal{M}\times\mathcal{N}$ is a global
saddle point of $f$, we have
${\mathbb{E}}[f(x_{t},y^{\star})-f(x^{\star},y_{t})]\geq 0$. Plugging this
inequality into the inequality from Lemma F.2 yields that

${\mathbb{E}}\left[(d_{\mathcal{M}}(x_{t+1},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{t+1},y^{\star}))^{2}\right]\leq(1-\mu\eta_{t}){\mathbb{E}}\left[(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}\right]+4\overline{\xi}_{0}\eta_{t}^{2}(L^{2}+\sigma^{2}).$

Since $\eta_{t}=\frac{1}{\mu}\min\\{1,\frac{2}{t}\\}$, we have

${\mathbb{E}}\left[(d_{\mathcal{M}}(x_{t+1},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{t+1},y^{\star}))^{2}\right]\leq(1-\tfrac{2}{t}){\mathbb{E}}\left[(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}\right]+\tfrac{16\overline{\xi}_{0}(L^{2}+\sigma^{2})}{\mu^{2}t^{2}},\quad\textnormal{for
all }t\geq 2.$

Applying the same argument as used in Theorem D.1, we have

$(d_{\mathcal{M}}(x_{t},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{t},y^{\star}))^{2}\leq\tfrac{16\overline{\xi}_{0}(L^{2}+\sigma^{2})}{\mu^{2}t},\quad\textnormal{for
all }t\geq 2.$

This completes the proof.

###  F.5 Proof of Theorem D.4

Using the same argument, we have

$f(\bar{x}_{T},y^{\star})-f(x^{\star},\bar{y}_{T})\leq\tfrac{1}{T}\left(\sum_{t=0}^{T-1}f(x_{t},y^{\star})-f(x^{\star},y_{t})\right).$

Plugging the above inequality into the inequality from Lemma F.2 yields that
(recall that $\mu=0$ in geodesically convex-concave setting and
$\eta_{t}=\eta=\tfrac{1}{2}\sqrt{\tfrac{D_{0}}{\overline{\xi}_{0}(L^{2}+\sigma^{2})T}}$)

${\mathbb{E}}[f(\bar{x}_{T},y^{\star})-f(x^{\star},\bar{y}_{T})]\leq\tfrac{1}{2\eta
T}\left((d_{\mathcal{M}}(x_{0},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{0},y^{\star}))^{2}\right)+2\overline{\xi}_{0}\eta(L^{2}+\sigma^{2}).$

This together with
$(d_{\mathcal{M}}(x_{0},x^{\star}))^{2}+(d_{\mathcal{N}}(y_{0},y^{\star}))^{2}\leq
D_{0}$ implies that

${\mathbb{E}}[f(\bar{x}_{T},y^{\star})-f(x^{\star},\bar{y}_{T})]\leq\tfrac{D_{0}}{2\eta
T}+2\overline{\xi}_{0}\eta(L^{2}+\sigma^{2}).$

Since
$\eta=\tfrac{1}{2}\sqrt{\tfrac{D_{0}}{\overline{\xi}_{0}(L^{2}+\sigma^{2})T}}$,
we have

$f(\bar{x}_{T},y^{\star})-f(x^{\star},\bar{y}_{T})\leq
2\sqrt{\tfrac{\overline{\xi}_{0}(L^{2}+\sigma^{2})D_{0}}{T}}.$

This completes the proof.

##  Appendix G Additional Experimental Results

We present some additional experimental results for the effect of different
choices of $\alpha$ as well the effect of different choices of $\eta$ for for
RCEG. In our experiment here, we set $n=40$ consistently.

Figure 3 presents the performance of RCEG when $\alpha=2.0$. We observe that
the results are similar to that summarized in Figure 1. In particular, the
last iterate of RCEG consistently achieves the linearly convergence to an
optimal solution in all the settings. In contrast, the average iterate of RCEG
converges much slower than the last iterate of RCEG. Figure 4 summarizes the
effect of different choices of $\eta$ in RCEG. We observe that setting $\eta$
as a relatively larger value will speed up the convergence to an optimal
solution while all of the choices here lead to the linear convergence. This
suggests that the choice of stepsize $\eta$ in RCEG can be aggressive in
practice.

Figure 3: Comparison of last iterate (RCEG-last) and time-average iterate
(RCEG-avg) for solving the RPCA problem when $\alpha=2.0$. The horizontal axis
represents the number of data passes and the vertical axis represents gradient
norm.

Figure 4: Comparison of different step sizes ($\eta\in\\{0.1,0.05,0.02\\}$)
for solving the RPCA problem with different dimensions when $\alpha=2.0$. The
horizontal axis represents the number of data passes and the vertical axis
represents gradient norm.