application of Lemma B.3 to control the influence of noise in PPM without
replacement. To this end, we begin by presenting a linearization-based proof
of convergence of full batch PPM, followed by a unified proof of convergence
of PPM-RR and PPM-SO, and conclude with the extension of our proof techniques
to the adversarial shuffling regime by analyzing PPM-AS.

###  D.1 Analysis of Full-batch PPM by Linearization

######  Theorem D.1 (Convergence of full-batch PPM).

Consider the $l$-Lipschitz and $\mu$-strongly monotone operator
$\nu:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ and let $\mathbf{z}^{*}$ denote
the unique root of $\nu$. For any step-size $0<\alpha<1/l$, the iterates
$\mathbf{z}_{k}$ of full-batch PPM satisfy the following recurrence:

$\displaystyle\mathbf{z}_{k+1}-\mathbf{z}^{*}=(\mathbf{I}+\alpha\mathbf{M}_{k+1})^{-1}(\mathbf{z}_{k}-\mathbf{z}^{*}),$

where $\mathbf{I}+\alpha\mathbf{M}_{k+1}$ is invertible and its singular
values are lower bounded as
$\sigma_{\min}(\mathbf{I}+\alpha\mathbf{M}_{k+1})\geq 1+\alpha\mu$.
Consequently, setting $\alpha=1/2l$ gives us the following last iterate
convergence guarantee:

$\displaystyle\left\lvert\mathbf{z}_{K+1}-\mathbf{z}^{*}\right\rvert^{2}\leq(1+1/2\kappa)^{-2K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}.$

###### Proof.

The iterates of full-batch PPM with step-size $\alpha$ satisfy

$\displaystyle\mathbf{z}_{k+1}=\mathbf{z}_{k}-\alpha\nu(\mathbf{z}_{k+1}).$

From the above equation, we conclude that $\mathbf{z}_{k+1}$ is a fixed point
of the operator $\zeta(\mathbf{z})=\mathbf{z}_{k}-\alpha\nu(\mathbf{z})$.
Since $\alpha<1/l$, $\zeta$ is a contraction mapping. Hence, by the Banach
Fixed Point Theorem, we conclude that $\mathbf{z}_{k+1}$ exists and is
uniquely defined. This allows us to proceed in a manner similar to Theorem C.1
and linearize $\nu(\mathbf{z}_{k+1})$ about $\mathbf{z}^{*}$. Thus, by the
Lipschitz continuity of $\nu$ and the Fundamental Theorem of Calculus for
Lebesgue Integrals:

$\displaystyle\nu(\mathbf{z}_{k+1})$
$\displaystyle=\nu(\mathbf{z}^{*})+\int_{0}^{1}\nabla\nu(t\mathbf{z}_{k+1}+(1-t)\mathbf{z}^{*})(\mathbf{z}_{k+1}-\mathbf{z}^{*})\textrm{d}t$
$\displaystyle=\mathbf{M}_{k+1}(\mathbf{z}_{k+1}-\mathbf{z}^{*}),$

where
$\mathbf{M}_{k+1}=\int_{0}^{1}\nabla\nu(t\mathbf{z}_{k+1}+(1-t)\mathbf{z}^{*})\textrm{d}t$
is well defined by Lemma B.1. Substituting this expansion into the PPM update
rule gives us the following:

$\mathbf{z}_{k}-\mathbf{z}^{*}=(\mathbf{I}+\alpha\mathbf{M}_{k+1})(\mathbf{z}_{k+1}-\mathbf{z}^{*}).$
(D.1)

Using the same arguments as in Theorem C.1, we conclude that the $\mu$-strong
monotonicity of $\nu$ implies
$\mathbf{v}^{T}\mathbf{M}_{k+1}\mathbf{v}\geq\mu\left\lvert\mathbf{v}\right\rvert^{2}\
\forall\mathbf{v}\in\mathbb{R}^{d}$. Using this, we lower bound the singular
values of $\mathbf{I}+\alpha\mathbf{M}_{k+1}$ as follows:

Note that for any $\mathbf{v}\in\mathbb{R}^{d}$,

$\displaystyle\left\lvert(\mathbf{I}+\alpha\mathbf{M}_{k+1})\mathbf{v}\right\rvert^{2}$
$\displaystyle=\left\lvert\mathbf{v}\right\rvert^{2}+\alpha\mathbf{v}^{T}\mathbf{M}_{k+1}\mathbf{v}+\alpha\mathbf{v}^{T}\mathbf{M}^{T}_{k+1}\mathbf{v}+\alpha^{2}\left\lvert\mathbf{M}_{k+1}\mathbf{v}\right\rvert^{2}$
$\displaystyle\geq(1+2\alpha\mu+\alpha^{2}\mu^{2})\left\lvert\mathbf{v}\right\rvert^{2},$

where the last inequality follows from the Cauchy-Schwarz inequality since
$\left\lvert\mathbf{v}\right\rvert\left\lvert\mathbf{M}_{k+1}\mathbf{v}\right\rvert\geq\mathbf{v}^{T}\mathbf{M}_{k+1}\mathbf{v}\geq\mu\left\lvert\mathbf{v}\right\rvert^{2}$.

Thus, the singular values of $\mathbf{I}+\alpha\mathbf{M}_{k+1}$ are lower
bounded as $\sigma_{\min}(\mathbf{I}+\alpha\mathbf{M}_{k+1})\geq
1+\alpha\mu>0$. Since $\mathbf{I}+\mathbf{M}_{k+1}$ is a square matrix, this
implies that $\mathbf{I}+\alpha\mathbf{M}_{k+1}$ is invertible and

$\displaystyle\left\lvert(\mathbf{I}+\alpha\mathbf{M}_{k+1})^{-1}\right\rvert=\sigma_{\max}((\mathbf{I}+\alpha\mathbf{M}_{k+1})^{-1})=1/\sigma_{\min}(\mathbf{I}+\alpha\mathbf{M}_{k+1})\leq(1+\alpha\mu)^{-1}.$

It follows that,

$\displaystyle\mathbf{z}_{k+1}-\mathbf{z}^{*}$
$\displaystyle=(\mathbf{I}+\alpha\mathbf{M}_{k+1})^{-1}(\mathbf{z}_{k}-\mathbf{z}^{*})$
$\displaystyle\implies\left\lvert\mathbf{z}_{k+1}-\mathbf{z}^{*}\right\rvert^{2}$
$\displaystyle\leq(1+\alpha\mu)^{-2}\left\lvert\mathbf{z}_{k}-\mathbf{z}^{*}\right\rvert^{2}.$

Thus, by setting $\alpha=1/2l$, we obtain the following convergence guarantee

$\displaystyle\left\lvert\mathbf{z}_{K+1}-\mathbf{z}^{*}\right\rvert^{2}\leq(1+1/2\kappa)^{-2K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}.$

∎

###  D.2 A Unified Analysis of PPM-RR and PPM-SO

######  Theorem D.2 (Convergence of PPM-RR/SO).

Consider Problem (3.3) for the $\mu$-strongly monotone operator
$\nu(\mathbf{z})=\nicefrac{{1}}{{n}}\sum_{i=1}^{n}\omega_{i}(\mathbf{z})$
where each $\omega_{i}$ is $l$-Lipschitz, but not necessarily monotone. Let
$\mathbf{z}^{*}$ denote the unique root of $\nu$. Then, for any
$\alpha\leq\frac{\mu}{5nl^{2}}$ and $K\geq 1$, the iterates of PPM-RR and PPM-
SO satisfy the following:

$\mathbb{E}[\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert^{2}]\leq
2e^{-n\alpha\mu
K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}+\frac{l^{2}\sigma_{*}^{2}\alpha^{3}n^{2}K}{\mu}.$

Setting
$\alpha=\min\\{\mu/5nl^{2},2\log(\left\lvert\nu(\mathbf{z}_{0})\right\rvert
n^{1/2}K/\mu)/\mu nK\\}$ results in the following expected last-iterate
convergence guarantee for both PPM-RR and PPM-SO, which holds for any $K\geq
1$:

$\displaystyle\mathbb{E}[|\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}|^{2}]$
$\displaystyle\leq
2e^{\nicefrac{{-K}}{{5\kappa^{2}}}}|\mathbf{z}_{0}-\mathbf{z}^{*}|^{2}+\frac{2\mu^{2}+8\kappa^{2}\sigma^{2}_{*}\log^{3}(|\nu(\mathbf{z}_{0})|n^{1/2}K/\mu)}{\mu^{2}nK^{2}}$
$\displaystyle=\tilde{O}(e^{\nicefrac{{-K}}{{5\kappa^{2}}}}+\nicefrac{{1}}{{nK^{2}}}).$

###### Proof.

Without loss of generality, we express the iterate-level update rule of PPM-RR
and PPM-SO jointly as

$\mathbf{z}^{k}_{i}=\mathbf{z}^{k}_{i-1}-\alpha\mathbf{\omega}_{\tau_{k}(i)}(\mathbf{z}^{k}_{i}),$
(D.2)

where $k\in[K]$ and $i\in[n]$. Similar to Theorem D.1, the Banach Fixed Point
Theorem guarantees that $\mathbf{z}^{k}_{i}$ is well defined and unique since
$\alpha\leq\mu/5nl^{2}<1/l$.

We note that $\tau_{k}\sim\textrm{Uniform}(\mathbb{S}_{n})$ for every
$k\in[K]$ for PPM-RR (i.e., $\tau_{k}$ is a permutation of $[n]$ that is
resampled uniformly at every epoch) whereas for PPM-SO, $\tau_{k}=\tau\
\forall k\in[K]$ where $\tau\sim\textrm{Uniform}(\mathbb{S}_{n})$ (i.e., the
permutation $\tau$ is uniformly sampled before the first epoch, then reused
for all subsequent epochs). We also define the transposed permutation
$\tilde{\tau}_{k}$ as $\tilde{\tau}_{k}(i)=\tau_{k}(n+1-i)$ for any $i\in[n]$.

The remainder of our proof follows the structure of Theorem C.2. In
particular, we apply the linearization technique as illustrated in Theorem D.1
to PPM without replacement and derive a linearized epoch-level update rule of
the form
$\mathbf{z}^{k}_{0}-\mathbf{z}^{*}=\mathbf{H}_{k}(\mathbf{z}^{k+1}_{0}-\mathbf{z}^{*})+\alpha^{2}\mathbf{r}_{k}$.
This is followed by lower bounding $\sigma_{\min}(\mathbf{H}_{k})$ using the
Lipschitz continuity and strong monotonicity of $\mu$ and upper bounding
$\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]$ using Lemma B.3. The
proof is completed by unrolling the update rule for $K$ epochs and carefully
choosing the step-size.

#### Step 1: Linearized epoch-level update rule

The approach for this step mirrors that of Theorem C.2 and hinges on the
insight that for small enough step-sizes, the dynamics of the iterates
$\mathbf{z}^{k+1}_{0}$ of PPM without replacement can be treated as a noisy
version of full-batch PPM. Complementing this insight with the linearization-
based analysis of full-batch PPM in Theorem D.1 motivates the following
decomposition:

$\displaystyle\mathbf{\omega}_{\tau_{k}(i)}(\mathbf{z}^{k}_{i})$
$\displaystyle=\mathbf{\omega}_{\tau_{k}(i)}(\mathbf{z}^{*})+[\mathbf{\omega}_{\tau_{k}(i)}(\mathbf{z}^{k}_{n})-\mathbf{\omega}_{\tau_{k}(i)}(\mathbf{z}^{*})]+[\mathbf{\omega}_{\tau_{k}(i)}(\mathbf{z}^{k}_{i})-\mathbf{\omega}_{\tau_{k}(i)}(\mathbf{z}^{k}_{n})]$
$\displaystyle=\mathbf{\omega}_{\tau_{k}(i)}(\mathbf{z}^{*})+\int_{0}^{1}\nabla\omega_{\tau_{k}(i)}(t\mathbf{z}^{k}_{n}+(1-t)\mathbf{z}^{*})(\mathbf{z}^{k}_{n}-\mathbf{z}^{*})\textrm{d}t$
$\displaystyle+\int_{0}^{1}\nabla\omega_{\tau_{k}(i)}(t\mathbf{z}^{k}_{i}+(1-t)\mathbf{z}^{k}_{n})(\mathbf{z}^{k}_{i}-\mathbf{z}^{k}_{n})\textrm{d}t.$

We further define $\mathbf{M}_{\tau_{k}(i)}$ and $\mathbf{J}_{\tau_{k}(i)}$ as
follows:

$\displaystyle\mathbf{M}_{\tau_{k}(i)}$
$\displaystyle=\int_{0}^{1}\nabla\omega_{\tau_{k}(i)}(t\mathbf{z}^{k}_{n}+(1-t)\mathbf{z}^{*})\textrm{d}t,$
$\displaystyle\mathbf{J}_{\tau_{k}(i)}$
$\displaystyle=\int_{0}^{1}\nabla\omega_{\tau_{k}(i)}(t\mathbf{z}^{k}_{i}+(1-t)\mathbf{z}^{k}_{n})\textrm{d}t.$

By repeating the same arguments as in Theorem D.1, we note that the
$l$-Lipschitz continuity of $\omega_{i}(\mathbf{z})\ \forall i\in[n]$ implies
that $\mathbf{M}_{\tau_{k}(i)}$ and $\mathbf{J}_{\tau_{k}(i)}$ are well
defined and bounded as $\left\lvert\mathbf{M}_{\tau_{k}(i)}\right\rvert\leq l$
and $\left\lvert\mathbf{J}_{\tau_{k}(i)}\right\rvert\leq l$. It follows that

$\mathbf{\omega}_{\tau_{k}(i)}(\mathbf{z}^{k}_{i})=\mathbf{\omega}_{\tau_{k}(i)}(\mathbf{z}^{*})+\mathbf{M}_{\tau_{k}(i)}(\mathbf{z}^{k}_{n}-\mathbf{z}^{*})+\mathbf{J}_{\tau_{k}(i)}(\mathbf{z}^{k}_{i}-\mathbf{z}^{k}_{n}).$
(D.3)

Substituting (D.3) into the update equation (C.2) for $\mathbf{z}^{k}_{n}$
yields,

$\displaystyle\mathbf{z}^{k}_{n-1}-\mathbf{z}^{*}$
$\displaystyle=(\mathbf{I}+\alpha\mathbf{M}_{\tau_{k}(n)})(\mathbf{z}^{k}_{n}-\mathbf{z}^{*})+\alpha\mathbf{J}_{\sigma_{k}(n)}(\mathbf{z}^{k}_{n}-\mathbf{z}^{k}_{n})+\alpha\mathbf{\omega}_{\tau_{k}(n)}(\mathbf{z}^{*})$
$\displaystyle=(\mathbf{I}+\alpha\mathbf{M}_{\tilde{\tau}_{k}(1)})(\mathbf{z}^{k}_{n}-\mathbf{z}^{*})+\alpha\mathbf{\omega}_{\tilde{\tau}_{k}(1)}(\mathbf{z}^{*}).$

Repeating the same for $\mathbf{z}^{k}_{n-1}$ results in the following:

$\displaystyle\mathbf{z}^{k}_{n-2}-\mathbf{z}^{*}$
$\displaystyle=\mathbf{z}^{k}_{n-1}-\mathbf{z}^{*}+\alpha\mathbf{\omega}_{\tau_{k}(n-1)}(\mathbf{z}^{*})+\alpha\mathbf{M}_{\tau_{k}(n-1)}(\mathbf{z}^{k}_{n}-\mathbf{z}^{*})+\alpha\mathbf{J}_{\tau_{k}(n-1)}(\mathbf{z}^{k}_{n-1}-\mathbf{z}^{k}_{n})$
$\displaystyle=\mathbf{z}^{k}_{n-1}-\mathbf{z}^{*}+\alpha\mathbf{\omega}_{\tilde{\tau}_{k}(2)}(\mathbf{z}^{*})+\alpha\mathbf{M}_{\tilde{\tau}_{k}(2)}(\mathbf{z}^{k}_{n}-\mathbf{z}^{*})+\alpha\mathbf{J}_{\tilde{\tau}_{k}(2)}(\mathbf{z}^{k}_{n-1}-\mathbf{z}^{k}_{n})$
$\displaystyle=(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(2)})(\mathbf{z}^{k}_{n-1}-\mathbf{z}^{*})+\alpha(\mathbf{M}_{\tilde{\tau}_{k}(2)}-\mathbf{J}_{\tilde{\tau}_{k}(2)})(\mathbf{z}^{k}_{n}-\mathbf{z}^{*})+\alpha\mathbf{\omega}_{\tilde{\tau}_{k}(2)}(\mathbf{z}^{*})$
$\displaystyle=(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(2)})[(\mathbf{I}+\alpha\mathbf{M}_{\tilde{\tau}_{k}(1)})(\mathbf{z}^{k}_{n}-\mathbf{z}^{*})+\alpha\mathbf{\omega}_{\tilde{\tau}_{k}(1)}(\mathbf{z}^{*})]$
$\displaystyle+\alpha(\mathbf{M}_{\tilde{\tau}_{k}(2)}-\mathbf{J}_{\tilde{\tau}_{k}(2)})(\mathbf{z}^{k}_{n}-\mathbf{z}^{*})+\alpha\mathbf{\omega}_{\tilde{\tau}_{k}(2)}(\mathbf{z}^{*})$
$\displaystyle=[(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(2)})(\mathbf{I}+\alpha\mathbf{M}_{\tilde{\tau}_{k}(1)})+\alpha(\mathbf{M}_{\tilde{\tau}_{k}(2)}-\mathbf{J}_{\tilde{\tau}_{k}(2)})](\mathbf{z}^{k}_{n}-\mathbf{z}^{*})$
$\displaystyle+\alpha[\mathbf{\omega}_{\tilde{\tau}_{k}(2)}(\mathbf{z}^{*})+(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(2)})\mathbf{\omega}_{\tilde{\tau}_{k}(1)}(\mathbf{z}^{*})]$
$\displaystyle=[\mathbf{I}+\alpha\mathbf{M}_{\tilde{\tau}_{k}(2)}+\alpha(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(2)})\mathbf{M}_{\tilde{\tau}_{k}(1)}](\mathbf{z}^{k}_{n}-\mathbf{z}^{*})$
$\displaystyle+\alpha[\mathbf{\omega}_{\tilde{\tau}_{k}(2)}(\mathbf{z}^{*})+(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(2)})\mathbf{\omega}_{\tilde{\tau}_{k}(1)}(\mathbf{z}^{*})].$

By applying the same process for preceeding iterates and substituting
$\mathbf{z}^{k}_{n}=\mathbf{z}^{k+1}_{0}$, we obtain the following epoch-level
update rule for PPM-RR and PPM-SO

$\displaystyle\mathbf{z}^{k}_{0}-\mathbf{z}^{*}$
$\displaystyle=[\mathbf{I}+\alpha\sum_{j=1}^{n}\left(\widetilde{\prod}_{t=j+1}^{n}(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(t)})\right)\mathbf{M}_{\tilde{\tau}_{k}(j)}](\mathbf{z}^{k+1}_{0}-\mathbf{z}^{*})$
$\displaystyle+\alpha\sum_{j=1}^{n}\left(\widetilde{\prod}_{t=j+1}^{n}(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(t)})\right)\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*}).$
(D.4)

We clarify that the matrix products in (D.4) are in reverse order, and hence
reduce to the empty product, which is defined to be $\mathbf{I}$, when $j=i$.
Furthermore $\tilde{\tau}_{k}$ denotes the transposed permutation
$\tilde{\tau}_{k}(i)=\tau_{k}(n+1-i)$.

We simplify the second term in the right hand side of (D.4) using the
summation by parts identity. To this end, we define $a_{j}$ and $b_{j}$ as

$\displaystyle a_{j}$
$\displaystyle=\widetilde{\prod}_{t=j+1}^{n}(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(t)}),$
$\displaystyle b_{j}$
$\displaystyle=\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*}),$

and observe that,

$\displaystyle\sum_{j=1}^{n}b_{j}=\sum_{j=1}^{n}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*})=n\nu(\mathbf{z}^{*})=0,$

since $\mathbf{z}^{*}$ is the unique root of $\nu$. We now apply the summation
by parts identity to obtain the following:

$\displaystyle\sum_{j=1}^{n}a_{j}b_{j}$
$\displaystyle=a_{n}\sum_{j=1}^{n}b_{j}-\sum_{i=1}^{n-1}(a_{i+1}-a_{i})\sum_{j=1}^{i}b_{j}$
$\displaystyle=-\sum_{i=1}^{n-1}\left[\widetilde{\prod}_{t=i+2}^{n}(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(t)})-\widetilde{\prod}_{t=i+1}^{n}(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(t)})\right]\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*})$
$\displaystyle=\alpha\sum_{i=1}^{n-1}\left[\widetilde{\prod}_{t=i+2}^{n}(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(t)})\right]\mathbf{J}_{\tilde{\tau}_{k}(i+1)}\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*}).$

Hence, we conclude that:

$\displaystyle\sum_{j=1}^{n}\left[\widetilde{\prod}_{t=j+1}^{n}(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(t)})\right]\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*})=\alpha\sum_{i=1}^{n-1}\left[\widetilde{\prod}_{t=i+2}^{n}(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(t)})\right]\mathbf{J}_{\tilde{\tau}_{k}(i+1)}\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*}).$

We define $\mathbf{H}_{k}$ and $\mathbf{r}_{k}$ as

$\displaystyle\mathbf{H}_{k}$
$\displaystyle=\mathbf{I}+\alpha\sum_{j=1}^{n}\left(\widetilde{\prod}_{t=j+1}^{n}(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(t)})\right)\mathbf{M}_{\tilde{\tau}_{k}(j)},$
$\displaystyle\mathbf{r}_{k}$
$\displaystyle=\sum_{i=1}^{n-1}\left[\widetilde{\prod}_{t=i+2}^{n}(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(t)})\right]\mathbf{J}_{\tilde{\tau}_{k}(i+1)}\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*}),$

and substitute the above expressions in (D.4). This gives us the following
noisy linearized update rule for the epoch iterates $\mathbf{z}^{k}_{0}$ of
PPM-RR and PPM-SO:

$\mathbf{z}^{k}_{0}-\mathbf{z}^{*}=\mathbf{H}_{k}(\mathbf{z}^{k+1}_{0}-\mathbf{z}^{*})+\alpha^{2}\mathbf{r}_{k}.$
(D.5)

We observe that (D.5) closely resembles the linearized update rule (D.1) of
full-batch PPM as derived in Theorem D.1 with an additive noise term
$\alpha^{2}\mathbf{r}_{k}$. In fact, for $n=1$, which corresponds to the full-
batch regime, it is easy to see that $\mathbf{r}_{k}=0$ and (D.5) reduces to
(D.1). As we shall see in Theorem D.3, the same update rule also applies to
PPM-AS. Similar to our analysis of GDA, the derivation of an epoch-level
update rule that simultaneously handles PPM-RR, PPM-SO and PPM-AS is a key
component of our analysis.

Thus, we proceed in a manner similar to Theorem D.1 by lower bounding the
minimum singular value of $\mathbf{H}_{k}$.

#### Step 2: Lower bounding $\sigma_{\min}(\mathbf{H}_{k})$

We define the matrix $\mathbf{M}$ as,

$\displaystyle\mathbf{M}$
$\displaystyle=1/n\sum_{j=1}^{n}\mathbf{M}_{\tilde{\tau}_{k}(j)}=1/n\sum_{j=1}^{n}\int_{0}^{1}\nabla\omega_{\tilde{\tau}_{k}(j)}(t\mathbf{z}^{k}_{n}+(1-t)\mathbf{z}^{*})\textrm{d}t=\int_{0}^{1}\nabla\nu(t\mathbf{z}^{k}_{n}+(1-t)\mathbf{z}^{*})\textrm{d}t.$

By following the same arguments as Theorem D.1, we note that the
$l$-smoothness and $\mu$-strong monotonicity of $\nu$ implies that
$\left\lvert\mathbf{M}\right\rvert\leq l$ and
$\mathbf{v}^{T}\mathbf{M}\mathbf{v}\geq\mu\left\lvert\mathbf{v}\right\rvert^{2}\
\forall\mathbf{v}\in\mathbb{R}^{d}$.

By expanding the product terms in $\mathbf{H}_{k}$, we obtain the following:

$\displaystyle\mathbf{H}_{k}$
$\displaystyle=\mathbf{I}+\alpha\sum_{j=1}^{n}\left(\widetilde{\prod}_{t=j+1}^{n}(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(t)})\right)\mathbf{M}_{\tilde{\tau}_{k}(j)}$
$\displaystyle=\mathbf{I}+n\alpha\mathbf{M}+\sum_{j=2}^{n}\alpha^{j}\sum_{1\leq
t_{1}<t_{2}<\ldots<t_{j}\leq
n}\mathbf{J}_{\tilde{\tau}_{k}(t_{j})}\mathbf{J}_{\tilde{\tau}_{k}(t_{j-1})}\ldots\mathbf{J}_{\tilde{\tau}_{k}(t_{2})}\mathbf{M}_{\tilde{\tau}_{k}(t_{1})}.$

We now apply Weyl’s inequality for singular value perturbations, which gives
us the following bound,

$\sigma_{\min}(\mathbf{H}_{k})\geq\sigma_{\min}(\mathbf{I}+n\alpha\mathbf{M})-\sum_{j=2}^{n}\alpha^{j}\sum_{1\leq
t_{1}<t_{2}<\ldots<t_{j}\leq
n}\left\lvert\mathbf{J}_{\tilde{\tau}_{k}(t_{j})}\right\rvert\left\lvert\mathbf{J}_{\tilde{\tau}_{k}(t_{j-1})}\right\rvert\ldots\left\lvert\mathbf{J}_{\tilde{\tau}_{k}(t_{2})}\right\rvert\left\lvert\mathbf{M}_{\tilde{\tau}_{k}(t_{1})}\right\rvert.$
(D.6)

Following the same steps as Theorem D.1, we conclude that
$\mathbf{v}^{T}\mathbf{M}\mathbf{v}\geq\mu\left\lvert\mathbf{v}\right\rvert^{2}$
implies $\sigma_{\min}(\mathbf{I}+n\alpha\mathbf{M})\geq 1+n\alpha\mu$.
Furthermore, we observe that,

$\displaystyle\sum_{j=2}^{n}\alpha^{j}\sum_{1\leq t_{1}<t_{2}<\ldots<t_{j}\leq
n}\left\lvert\mathbf{J}_{\tilde{\tau}_{k}(t_{j})}\right\rvert\left\lvert\mathbf{J}_{\tilde{\tau}_{k}(t_{j-1})}\right\rvert\ldots\left\lvert\mathbf{J}_{\tilde{\tau}_{k}(t_{2})}\right\rvert\left\lvert\mathbf{M}_{\tilde{\tau}_{k}(t_{1})}\right\rvert$
$\displaystyle\leq\sum_{j=2}^{n}\alpha^{j}\binom{n}{j}l^{j}.$

Substituting the above bound in (D.6) gives us the following:

$\displaystyle\sigma_{\min}(\mathbf{H}_{k})$ $\displaystyle\geq
1+n\alpha\mu-\sum_{j=2}^{n}(\alpha l)^{j}\binom{n}{j}\geq
1+n\alpha\mu-\sum_{j=2}^{n}(\alpha nl)^{j}\geq
1+n\alpha\mu-\frac{\alpha^{2}n^{2}l^{2}}{1-\alpha nl}$ $\displaystyle\geq
1+n\alpha\mu-\frac{5\alpha^{2}n^{2}l^{2}}{4}\geq 1+3n\alpha\mu/4,$

where we substitute $\alpha\leq\frac{\mu}{5nl^{2}}\leq 1/5$ wherever required.
Furthermore, since $\sigma_{\min}(\mathbf{H}_{k})\geq 1+3n\alpha\mu/4>0$,
$\mathbf{H}_{k}$ is invertible and
$\left\lvert\mathbf{H}^{-1}_{k}\right\rvert\leq(1+3n\alpha\mu/4)^{-1}\leq(1-n\alpha\mu/2)$,
which holds since $n\alpha\mu\leq 1/5$.

As before, our analysis so far holds for any permutation
$\tau_{k}\in\mathbb{S}_{n}$. Consequently, Steps 1 and 2 directly generalize
to the adversarial shuffling regime without any modifications. We use this as
a starting point for our analysis of PPM-AS in Theorem D.3.

We now control the magnitude of the noise term $\mathbf{r}_{k}$ by bounding
$\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]$ similar to Theorem
C.2. We note that the expectation is taken over the single uniform permutation
$\tau$ for PPM-SO and over independent uniform permutations
$\tau_{1},\tau_{2},\ldots,\tau_{K}$ for PPM-RR.

#### Step 3: Upper bounding
$\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]$

We follow the same procedure as in Step 3 of Theorem C.2 and obtain the
following bound by successively applying
$\left\lvert\mathbf{J}_{\tilde{\tau}_{k}(i)}\right\rvert\leq l$ and Young’s
inequality:

$\displaystyle\left\lvert\mathbf{r}_{k}\right\rvert^{2}$ $\displaystyle\leq
l^{2}e^{2/5}(n-1)\sum_{i=1}^{n-1}i^{2}|1/i\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*})|^{2}.$

We now convert the above inequality into an upper bound for
$\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]$ by applying Lemma B.3
to the term
$|1/i\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*})|^{2}$.
The case of PPM-RR and PPM-SO are discussed separately.

#### Step 3A: $\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]$ for PPM-
RR

We write
$\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]=\mathbb{E}_{\tau_{1},\ldots,\tau_{K}}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]$
to explicitly denote the dependence of the expectation on the uniformly
sampled random permutations $\tau_{1},\ldots,\tau_{K}$, and then proceed as
follows:

$\displaystyle\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]$
$\displaystyle\leq
l^{2}e^{2/5}(n-1)\sum_{i=1}^{n-1}i^{2}\mathbb{E}_{\tau_{k}}[|1/i\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*})|^{2}].$

Since $\tau_{k}$ is a uniformly sampled random permutation and
$\mathbb{S}_{n}$ is a finite group with $n!$ elements, it follows that for any
$\pi\in\mathbb{S}_{n}$,

$\displaystyle\mathbb{P}_{\textrm{Uniform}}\left[\tau_{k}=\pi\right]=\mathbb{P}_{\textrm{Uniform}}\left[\tilde{\tau}_{k}=\pi\right]=1/n!\
.$

Hence, we infer that,

$\displaystyle\mathbb{E}_{\tau_{k}}[|1/i\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*})|^{2}]=\mathbb{E}_{\tilde{\tau}_{k}}[|1/i\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*})|^{2}]=\frac{n-i}{i(n-1)}\sigma_{*}^{2},$

where the last equality follows from Lemma B.3. Note that $\sigma_{*}^{2}$
denotes the gradient variance at the minimax point $\mathbf{z}^{*}$, defined
as
$\sigma_{*}^{2}=1/n\sum_{i=1}^{n}\left\lvert\mathbf{\omega}_{i}(\mathbf{z}^{*})\right\rvert^{2}$.
Substituting the above into the upper bound for
$\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]$ yields,

$\displaystyle\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]$
$\displaystyle\leq
l^{2}e^{2/5}(n-1)\sum_{i=1}^{n-1}i^{2}\mathbb{E}_{\tau_{k}}[|1/i\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*})|^{2}]$
$\displaystyle\leq
l^{2}e^{2/5}(n-1)\sum_{i=1}^{n-1}i^{2}\frac{n-i}{i(n-1)}\sigma_{*}^{2}=l^{2}e^{2/5}\sigma_{*}^{2}\sum_{i=1}^{n-1}i(n-i)$
$\displaystyle\leq l^{2}n^{3}\sigma_{*}^{2}/4.$

#### Step 3B: $\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]$ for PPM-
SO

For PPM-SO, $\tau_{1}=\ldots=\tau_{K}=\tau$ where $\tau$ is a uniformly
sampled random permutation. Consequently,
$\tilde{\tau}_{1}=\ldots=\tilde{\tau}_{K}=\tilde{\tau}$ where $\tilde{\tau}$
is the transposed permutation of $\tau$. Hence, we conclude that,

$\displaystyle\left\lvert\mathbf{r}_{k}\right\rvert^{2}\leq
l^{2}e^{2/5}(n-1)\sum_{i=1}^{n-1}i^{2}|1/i\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}(j)}(\mathbf{z}^{*})|^{2}.$

Proceeding along the same lines as Step 3A, we use the fact that $\tau$ is a
uniformly sampled random permutation to obtain the following:

$\displaystyle\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]$
$\displaystyle\leq
l^{2}e^{2/5}(n-1)\sum_{i=1}^{n-1}i^{2}\mathbb{E}_{\tau}[|1/i\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}(j)}(\mathbf{z}^{*})|^{2}]$
$\displaystyle=l^{2}e^{2/5}(n-1)\sum_{i=1}^{n-1}i^{2}\mathbb{E}_{\tilde{\tau}}[|1/i\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}(j)}(\mathbf{z}^{*})|^{2}]$
$\displaystyle\leq
l^{2}e^{2/5}(n-1)\sum_{i=1}^{n-1}i^{2}\frac{n-i}{i(n-1)}\sigma_{*}^{2}$
$\displaystyle\leq l^{2}n^{3}\sigma_{*}^{2}/4.$

Hence, for both PPM-RR and PPM-SO, $\left\lvert\mathbf{r}_{k}\right\rvert$ is
bounded in expectation as
$\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]\leq
l^{2}n^{3}\sigma_{*}^{2}/4$.

#### Step 4: Convergence analysis

Since $\mathbf{H}_{k}$ is invertible, we write (D.5) as

$\displaystyle\mathbf{z}^{k+1}_{0}-\mathbf{z}^{*}=\mathbf{H}^{-1}_{k}[\mathbf{z}^{k}_{0}-\mathbf{z}^{*}-\alpha^{2}\mathbf{r}_{k}].$

Unrolling for $K$ epochs and setting $\mathbf{z}^{1}_{0}=\mathbf{z}_{0}$
yields,

$\displaystyle\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}=\left[\widetilde{\prod}_{k=1}^{K}\mathbf{H}^{-1}_{k}\right](\mathbf{z}_{0}-\mathbf{z}^{*})-\alpha^{2}\sum_{k=1}^{K}\left[\widetilde{\prod}_{j=k}^{K}\mathbf{H}^{-1}_{j}\right]\mathbf{r}_{k}.$

By the triangle inequality and the bound
$\left\lvert\mathbf{H}^{-1}_{k}\right\rvert\leq(1-n\alpha\mu/2)$, we obtain:

$\displaystyle\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert$
$\displaystyle\leq\left[\widetilde{\prod}_{k=1}^{K}\left\lvert\mathbf{H}^{-1}_{k}\right\rvert\right]\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert+\alpha^{2}\sum_{k=1}^{K}\left[\widetilde{\prod}_{j=k}^{K}\left\lvert\mathbf{H}^{-1}_{j}\right\rvert\right]\left\lvert\mathbf{r}_{k}\right\rvert$
$\displaystyle\leq(1-n\alpha\mu/2)^{K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert+\alpha^{2}\sum_{k=1}^{K}(1-n\alpha\mu/2)^{K-k}\left\lvert\mathbf{r}_{k}\right\rvert,$

and as a result of Young’s inequality,

$\displaystyle\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert^{2}$
$\displaystyle\leq
2(1-n\alpha\mu/2)^{2K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}+2\alpha^{4}K\sum_{k=1}^{K}(1-n\alpha\mu/2)^{2(K-k)}|\mathbf{r}_{k}|^{2}.$

By taking expectations (with respect to the uniform random permutations
$\tau_{1},\ldots,\tau_{K}$ for RR and $\tau$ for SO respectively) on both
sides of the above inequality and substituting the upper bound for
$\mathbb{E}[|\mathbf{r}_{k}|{}^{2}]$ for PPM-RR and PPM-SO as derived in Step
3, we obtain

$\displaystyle\mathbb{E}[\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert^{2}]$
$\displaystyle\leq 2e^{-n\alpha\mu
K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}+2\alpha^{4}K\sum_{k=1}^{K}(1-n\alpha\mu/2)^{2(K-k)}\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]$
$\displaystyle\leq 2e^{-n\alpha\mu
K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}+0.5l^{2}n^{3}\sigma_{*}^{2}\alpha^{4}K\sum_{k=1}^{K}(1-n\alpha\mu/2)^{2(K-k)}.$

This yields the following guarantee that holds for PPM-RR and PPM-SO whenever
$\alpha\leq\frac{\mu}{5nl^{2}}$,

$\mathbb{E}[\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert^{2}]\leq
2e^{-n\alpha\mu
K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}+\frac{l^{2}\sigma_{*}^{2}\alpha^{3}n^{2}K}{\mu}.$
(D.7)

We note that the above inequality is identical to the inequality (C.8)
obtained in Theorem C.2. Hence, we substitute
$\alpha=\min\\{\mu/5nl^{2},2\log(\left\lvert\nu(\mathbf{z}_{0})\right\rvert
n^{1/2}K/\mu)/\mu nK\\}$ in (D.7) and follow the same steps as in Theorem C.2
to obtain the following last-iterate convergence guarantee for both PPM-RR and
PPM-SO, which holds for any $K\geq 1$:

$\mathbb{E}[\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert^{2}]\leq
2e^{-\frac{K}{5\kappa^{2}}}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}+\frac{2\mu^{2}+8\kappa^{2}\sigma_{*}^{2}\log^{3}\left(\left\lvert\nu(\mathbf{z}_{0})\right\rvert
n^{1/2}K/\mu\right)}{\mu^{2}nK^{2}}.$ (D.8)

Suppressing constant terms and logarithmic factors, we obtain the following:

$\mathbb{E}[\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert^{2}]=\tilde{O}(e^{\nicefrac{{-K}}{{5\kappa^{2}}}}+\nicefrac{{1}}{{nK^{2}}}).$
(D.9)

∎

###  D.3 Analysis of PPM-AS

######  Theorem D.3 (Convergence of PPM-AS).

Consider Problem (3.3) for the $\mu$-strongly monotone operator
$\nu(\mathbf{z})=\nicefrac{{1}}{{n}}\sum_{i=1}^{n}\omega_{i}(\mathbf{z})$
where each $\omega_{i}$ is $l$-Lipschitz, but not necessarily monotone. Let
$\mathbf{z}^{*}$ denote the unique root of $\nu$. Then, for any
$\alpha\leq\frac{\mu}{5nl^{2}}$ and $K\geq 1$, the iterates of PPM-AS satisfy
the following:

$\max_{\tau_{1},\ldots,\tau_{K}\in\mathbb{S}_{n}}\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert^{2}\leq
2e^{-n\alpha\mu
K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}+\frac{3l^{2}\sigma_{*}^{2}\alpha^{3}n^{3}K}{\mu}.$

Setting
$\alpha=\min\\{\mu/5nl^{2},2\log(\left\lvert\nu(\mathbf{z}_{0})\right\rvert
K/\mu)/\mu nK\\}$ results in the following last-iterate convergence guarantee
for PPM-AS, which holds for any $K\geq 1$:

$\displaystyle\max_{\tau_{1},\ldots,\tau_{K}\in\mathbb{S}_{n}}\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert^{2}$
$\displaystyle\leq
2e^{\nicefrac{{-K}}{{5\kappa^{2}}}}|\mathbf{z}_{0}-\mathbf{z}^{*}|^{2}+\frac{2\mu^{2}+24\kappa^{2}\sigma^{2}_{*}\log^{3}(|\nu(\mathbf{z}_{0})|K/\mu)}{\mu^{2}K^{2}}$
$\displaystyle=\tilde{O}(e^{\nicefrac{{-K}}{{5\kappa^{2}}}}+\nicefrac{{1}}{{K^{2}}}).$

###### Proof.

The iterate-level update rule of PPM-AS can be expressed as

$\mathbf{z}^{k}_{i}=\mathbf{z}^{k}_{i-1}-\alpha\mathbf{\omega}_{\tau_{k}(i)}(\mathbf{z}^{k}_{i}),$
(D.10)

where $k\in[K]$, $i\in[n]$ and $\tau_{k}$ denotes an arbitrary permutation of
$[n]$ which is chosen by the adversary at the start of epoch $k$. For any
permutation $\tau_{k}$ chosen by the adversary, we denote the transposed
permutation $\tilde{\tau}_{k}$ as $\tilde{\tau}_{k}(i)=\tau_{k}(n+1-i)$.
Furthermore $\mathbf{z}^{k}_{i}$ is well defined and unique due to the Banach
Fixed Point Theorem as $\alpha\leq\mu/5nl^{2}<1/l$.

We recall that Steps 1 and 2 of Theorem D.2 are applicable for any permutation
$\tau_{k}\in\mathbb{S}_{n}$, and hence, can be applied directly to PPM-AS.
Consequently, the epoch-level update rule of PPM-AS is the same as that of
PPM-RR/SO and is given by:

$\mathbf{z}^{k}_{0}-\mathbf{z}^{*}=\mathbf{H}_{k}(\mathbf{z}^{k+1}_{0}-\mathbf{z}^{*})+\alpha^{2}\mathbf{r}_{k},$
(D.11)

where $\mathbf{H}_{k}$ and $\mathbf{r}_{k}$ are as defined in Theorem D.2, and
are given by:

$\displaystyle\mathbf{H}_{k}$
$\displaystyle=\mathbf{I}+\alpha\sum_{j=1}^{n}\left(\widetilde{\prod}_{t=j+1}^{n}(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(t)})\right)\mathbf{M}_{\tilde{\tau}_{k}(j)},$
$\displaystyle\mathbf{r}_{k}$
$\displaystyle=\sum_{i=1}^{n-1}\left[\widetilde{\prod}_{t=i+2}^{n}(\mathbf{I}+\alpha\mathbf{J}_{\tilde{\tau}_{k}(t)})\right]\mathbf{J}_{\tilde{\tau}_{k}(i+1)}\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*}),$

where, as before,
$\mathbf{M}_{\tau_{k}(i)}=\int_{0}^{1}\nabla\omega_{\tau_{k}(i)}(t\mathbf{z}^{k+1}_{0}+(1-t)\mathbf{z}^{*})\textrm{d}t$
and
$\mathbf{J}_{\tau_{k}(i)}=\int_{0}^{1}\nabla\omega_{\tau_{k}(i)}(t\mathbf{z}^{k}_{i}+(1-t)\mathbf{z}^{k+1}_{0})\textrm{d}t$.
Furthermore, by Step 2 of Theorem D.2, $\mathbf{H}_{k}$ is invertible and
$\left\lvert\mathbf{H}^{-1}_{k}\right\rvert\leq 1-n\alpha\mu/2$.

We now proceed to control the noise term $\mathbf{r}_{k}$ by deriving an upper
bound for $\left\lvert\mathbf{r}_{k}\right\rvert^{2}$ that holds uniformly
over all permutations $\tau_{1},\ldots,\tau_{K}\in\mathbb{S}_{n}$. This is
done by following the same steps as that of Theorem C.3, which gives us the
following bound by successive applications of
$\left\lvert\mathbf{J}_{\tilde{\tau}_{k}(i)}\right\rvert\leq l$ and Young’s
inequality:

$\displaystyle\left\lvert\mathbf{r}_{k}\right\rvert^{2}$ $\displaystyle\leq
l^{2}e^{2/5}\left(\sum_{i=1}^{n-1}|\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*})|\right)^{2}$
$\displaystyle\leq
l^{2}e^{2/5}(n-1)\sum_{i=1}^{n-1}|\sum_{j=1}^{i}\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*})|^{2}$
$\displaystyle\leq
l^{2}e^{2/5}(n-1)\sum_{i=1}^{n-1}i\sum_{j=1}^{i}|\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*})|^{2}$
$\displaystyle\leq
l^{2}e^{2/5}(n-1)\sum_{i=1}^{n-1}i\sum_{j=1}^{n}|\mathbf{\omega}_{\tilde{\tau}_{k}(j)}(\mathbf{z}^{*})|^{2}=l^{2}e^{2/5}(n-1)\sum_{i=1}^{n-1}i\sum_{j=1}^{n}|\mathbf{\omega}_{j}(\mathbf{z}^{*})|^{2}$
$\displaystyle=l^{2}e^{2/5}(n-1)(n\sigma^{2}_{*})\sum_{i=1}^{n-1}i\leq
3l^{2}n^{4}\sigma_{*}^{2}/4.$

We note that the above sequence of inequalities hold for any permutation
$\tau_{k}$, and hence, the upper bound
$\left\lvert\mathbf{r}_{k}\right\rvert^{2}\leq 3l^{2}n^{4}\sigma_{*}^{2}/4$
holds for any $\tau_{k}\in\mathbb{S}_{n},\ k\in[K]$.

Since $\mathbf{H}_{k}$ is invertible, we write (D.11) as

$\displaystyle\mathbf{z}^{k+1}_{0}-\mathbf{z}^{*}=\mathbf{H}^{-1}_{k}[\mathbf{z}^{k}_{0}-\mathbf{z}^{*}-\alpha^{2}\mathbf{r}_{k}].$

By unrolling for $K$ epochs and setting $\mathbf{z}^{1}_{0}=\mathbf{z}_{0}$,
we obtain:

$\displaystyle\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}=\left[\widetilde{\prod}_{k=1}^{K}\mathbf{H}^{-1}_{k}\right](\mathbf{z}_{0}-\mathbf{z}^{*})-\alpha^{2}\sum_{k=1}^{K}\left[\widetilde{\prod}_{j=k}^{K}\mathbf{H}^{-1}_{j}\right]\mathbf{r}_{k}.$

By using the triangle inequality and the bound
$\left\lvert\mathbf{H}^{-1}_{k}\right\rvert\leq(1-n\alpha\mu/2)$, we get:

$\displaystyle\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert$
$\displaystyle\leq\left[\widetilde{\prod}_{k=1}^{K}\left\lvert\mathbf{H}^{-1}_{k}\right\rvert\right]\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert+\alpha^{2}\sum_{k=1}^{K}\left[\widetilde{\prod}_{j=k}^{K}\left\lvert\mathbf{H}^{-1}_{j}\right\rvert\right]\left\lvert\mathbf{r}_{k}\right\rvert$
$\displaystyle\leq(1-n\alpha\mu/2)^{K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert+\alpha^{2}\sum_{k=1}^{K}(1-n\alpha\mu/2)^{K-k}\left\lvert\mathbf{r}_{k}\right\rvert.$

Applying Young’s inequality yields the following:

$\displaystyle\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert^{2}$
$\displaystyle\leq
2(1-n\alpha\mu/2)^{2K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}+2\alpha^{4}K\sum_{k=1}^{K}(1-n\alpha\mu/2)^{2(K-k)}|\mathbf{r}_{k}|^{2}$
$\displaystyle\leq 2e^{-n\alpha\mu
K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}+2\alpha^{4}K\sum_{k=1}^{K}(1-n\alpha\mu/2)^{2(K-k)}|\mathbf{r}_{k}|^{2}$
$\displaystyle\leq 2e^{-n\alpha\mu
K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}+(1.5l^{2}n^{4}\sigma^{2}_{*})\alpha^{4}K\sum_{k=1}^{K}(1-n\alpha\mu/2)^{2(K-k)}$
$\displaystyle\leq 2e^{-n\alpha\mu
K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}+\frac{3l^{2}\sigma^{2}_{*}n^{3}\alpha^{3}K}{\mu}.$

Since the above inequality holds for any sequence of permutations
$\tau_{1},\ldots,\tau_{K}$ chosen by the adversary, we obtain the following
uniform guarantee for GDA-AS whenever $\alpha\leq\frac{\mu}{5nl^{2}}$,

$\max_{\tau_{1},\ldots,\tau_{K}\in\mathbb{S}_{n}}\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert^{2}\leq
2e^{-n\alpha\mu
K}\left\lvert\mathbf{z}_{0}-\mathbf{z}^{*}\right\rvert^{2}+\frac{3l^{2}\sigma_{*}^{2}\alpha^{3}n^{3}K}{\mu}.$
(D.12)

We note that the above inequality is exactly identical to the inequality
(C.16) obtained in Theorem C.3. Hence, we substitute
$\alpha=\min\\{\mu/5nl^{2},2\log(\left\lvert\nu(\mathbf{z}_{0})\right\rvert
K/\mu)/\mu nK\\}$ in (D.12) and follow the same steps as in Theorem C.3 to
obtain the following last-iterate convergence guarantee for PPM-AS, which
holds for any $K\geq 1$:

$\max_{\tau_{1},\ldots,\tau_{K}\in\mathbb{S}_{n}}\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert^{2}\leq
2e^{\nicefrac{{-K}}{{5\kappa^{2}}}}|\mathbf{z}_{0}-\mathbf{z}^{*}|^{2}+\frac{2\mu^{2}+24\kappa^{2}\sigma^{2}_{*}\log^{3}(|\nu(\mathbf{z}_{0})|K/\mu)}{\mu^{2}K^{2}}.$
(D.13)

Suppressing constant terms and logarithmic factors, we get,

$\max_{\tau_{1},\ldots,\tau_{K}\in\mathbb{S}_{n}}\left\lvert\mathbf{z}^{K+1}_{0}-\mathbf{z}^{*}\right\rvert^{2}=\tilde{O}(e^{\nicefrac{{-K}}{{5\kappa^{2}}}}+\nicefrac{{1}}{{K^{2}}}).$
(D.14)

∎

##  Appendix E Analysis of AGDA-RR and AGDA-AS

In this section, we present the convergence analysis of AGDA-RR and AGDA-AS
for smooth finite-sum objectives that satisfy a two-sided PŁ inequality. We
begin by stating some useful properties of two-sided PŁ functions which have
been established in prior works and are crucial to our analysis. We then
present our convergence analysis of AGDA-RR and AGDA-AS, which follows the
same broad structure as our analysis of GDA-RR/AS.

###  E.1 Properties of Two-sided PŁ Functions

We begin by presenting three important properties of two-sided PŁ functions
that are used throughout our analysis of AGDA-RR/AS

######  Lemma E.1 (Equivalent optimality conditions for two-sided PŁ
functions).

Let
$F:\mathbb{R}^{d_{\mathbf{x}}}\times\mathbb{R}^{d_{\mathbf{y}}}\rightarrow\mathbb{R}$
satisfy Assumption 3 and let $(\mathbf{x}^{*},\mathbf{y}^{*})$ be any point in
$\mathbb{R}^{d_{\mathbf{x}}}\times\mathbb{R}^{d_{\mathbf{y}}}$. Then the
following conditions are equivalent:

  * •

$(\mathbf{x}^{*},\mathbf{y}^{*})$ is a global minimax point, i.e.,
$\mathbf{x}^{*}\in\arg\min_{\mathbf{x}\in\mathbb{R}^{d_{\mathbf{x}}}}\Phi(\mathbf{x})$
where $\Phi$ is the best response function defined by
$\Phi(\mathbf{x})=\max_{\mathbf{y}\in\mathbb{R}^{d_{\mathbf{y}}}}F(\mathbf{x},\mathbf{y})$,
and
$\mathbf{y}^{*}\in\arg\max_{\mathbf{y}\in\mathbb{R}^{d_{\mathbf{y}}}}F(\mathbf{x}^{*},\mathbf{y})$.

  * •

$(\mathbf{x}^{*},\mathbf{y}^{*})$ is a saddle point, i.e.,

$\displaystyle F(\mathbf{x}^{*},\mathbf{y})\leq
F(\mathbf{x}^{*},\mathbf{y}^{*})\leq F(\mathbf{x},\mathbf{y}^{*}),\
\forall\mathbf{x}\in\mathbb{R}^{d_{\mathbf{x}}},\mathbf{y}\in\mathbb{R}^{d_{\mathbf{y}}}.$

  * •

$(\mathbf{x}^{*},\mathbf{y}^{*})$ is a stationary point, i.e.,

$\displaystyle\nabla_{\mathbf{x}}F(\mathbf{x}^{*},\mathbf{y}^{*})=\nabla_{\mathbf{y}}F(\mathbf{x}^{*},\mathbf{y}^{*})=0.$

###### Proof.

See Lemma 2.1 of Yang et al. [54]. ∎

######  Lemma E.2 (Properties of the best response).

Let
$F:\mathbb{R}^{d_{\mathbf{x}}}\times\mathbb{R}^{d_{\mathbf{y}}}\rightarrow\mathbb{R}$
be an $l$-smooth function satisfying Assumption 3 (with constants $\mu_{1}$
and $\mu_{2}$) and let $\Phi:\mathbb{R}^{d_{\mathbf{x}}}\rightarrow\mathbb{R}$
be the best response function defined as
$\Phi(\mathbf{x})=\max_{\mathbf{y}\in\mathbb{R}^{d_{\mathbf{y}}}}F(\mathbf{x},\mathbf{y})$.
Then $\Phi$ satisfies the following properties:

  * •

$\Phi$ is differentiable and $L$-smooth where $L=l+l^{2}/\mu_{2}$.

  * •

$\nabla\Phi(\mathbf{x})=\nabla_{\mathbf{x}}F(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))$
where $\mathbf{y}^{*}(\mathbf{x})$ is any arbitrary point in
$\arg\max_{\mathbf{y}\in\mathbb{R}^{d_{\mathbf{y}}}}F(\mathbf{x},\mathbf{y})$.

  * •

$\Phi$ satisfies the (one-sided) PŁ inequality with constant $\mu_{1}$, i.e.,

$\displaystyle\left\lvert\nabla\Phi(\mathbf{x})\right\rvert^{2}\geq
2\mu_{1}[\Phi(\mathbf{x})-\Phi^{*}],$

where
$\Phi^{*}=\min_{\mathbf{x}\in\mathbb{R}^{d_{\mathbf{x}}}}\Phi(\mathbf{x})$.

###### Proof.

See Lemma A.2 and Lemma A.3 of Yang et al. [54]. ∎

######  Lemma E.3 (Quadratic growth properties of PŁ functions).

Let $f:\mathbb{R}^{d_{\mathbf{x}}}\rightarrow\mathbb{R}$ be a PŁ function,
i.e., there exists a positive constant $\mu$ such that $\left\lvert\nabla
f(\mathbf{x})\right\rvert^{2}\geq 2\mu[f(\mathbf{x})-f^{*}]$, where
$f^{*}=\min_{\mathbf{x}}f(\mathbf{x})$. Then, $f$ satisfies the quadratic
growth property with constant $\mu$, i.e., for any
$\mathbf{x}\in\mathbb{R}^{d_{\mathbf{x}}}$,
$f(\mathbf{x})-f^{*}\geq\frac{\mu}{2}\left\lvert\mathbf{x}^{*}-\mathbf{x}\right\rvert^{2}$
where $\mathbf{x}^{*}$ is the projection of $\mathbf{x}$ on the set
$\arg\min_{\mathbf{x}}f(\mathbf{x})$.

###### Proof.

See Lemma A.1 of Yang et al. [54]. ∎

Finally, we motivate the necessity of the bounded gradient variance assumption
by presenting the construction of a two-sided PŁ function whose set of global
minimax points is unbounded.

######  Lemma E.4 (2PŁ function with unbounded set of global minimax points).

Consider the function
$f:\mathbb{R}^{2}\times\mathbb{R}^{2}\rightarrow\mathbb{R}$ given by
$f(\mathbf{x},\mathbf{y})=(\mathbf{x}_{1}+\mathbf{x}_{2})^{2}/2-(\mathbf{y}_{1}+\mathbf{y}_{2})^{2}/2$.
Then, $f$ is a two-sided PŁ function with constants $\mu_{1}=\mu_{2}=2$.
Furthermore, the set of global minimax points of $F$ is an unbounded proper
subset of $\mathbb{R}^{4}$.

###### Proof.

We define the functions $\Phi:\mathbb{R}^{2}\rightarrow\mathbb{R}$ and
$\Psi:\mathbb{R}^{2}\rightarrow\mathbb{R}$ as follows:

$\displaystyle\Phi(\mathbf{x})$
$\displaystyle=\max_{\mathbf{y}\in\mathbb{R}^{2}}f(\mathbf{x},\mathbf{y})=\frac{(\mathbf{x}_{1}+\mathbf{x}_{2})^{2}}{2},$
$\displaystyle\Psi(\mathbf{y})$
$\displaystyle=\min_{\mathbf{x}\in\mathbb{R}^{2}}f(\mathbf{x},\mathbf{y})=-\frac{(\mathbf{y}_{1}+\mathbf{y}_{2})^{2}}{2}.$

Furthermore, we note that:

$\displaystyle\nabla_{\mathbf{x}}f(\mathbf{x},\mathbf{y})$
$\displaystyle=[\mathbf{x}_{1}+\mathbf{x}_{2},\mathbf{x}_{1}+\mathbf{x}_{2}],$
$\displaystyle\nabla_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$
$\displaystyle=-[\mathbf{y}_{1}+\mathbf{y}_{2},\mathbf{y}_{1}+\mathbf{y}_{2}].$

From the above inequalities, it follows that:

$\displaystyle\left\lvert\nabla_{\mathbf{x}}f(\mathbf{x},\mathbf{y})\right\rvert^{2}$
$\displaystyle=4[f(\mathbf{x},\mathbf{y})-\Psi(\mathbf{y})]=4[f(\mathbf{x},\mathbf{y})-\min_{\mathbf{x}\in\mathbb{R}^{2}}f(\mathbf{x},\mathbf{y})],$
$\displaystyle\left\lvert\nabla_{\mathbf{y}}f(\mathbf{x},\mathbf{y})\right\rvert^{2}$
$\displaystyle=4[\Phi(\mathbf{x})-f(\mathbf{x},\mathbf{y})]=4[\max_{\mathbf{y}\in\mathbb{R}^{2}}f(\mathbf{x},\mathbf{y})-f(\mathbf{x},\mathbf{y})].$

Thus, $f$ satisfies the two-sided PŁ inequality with constants
$\mu_{1}=\mu_{2}=2$. Consequently, Lemma E.1 implies that the set of minimax
points are exactly the ones satisfying
$\nabla_{\mathbf{x}}f(\mathbf{x},\mathbf{y})=\nabla_{\mathbf{y}}f(\mathbf{x},\mathbf{y})=0$,
i.e., the set of global minimax points is
$\\{(\mathbf{x},\mathbf{y})\in\mathbb{R}^{4}\ |\
\mathbf{x}_{1}+\mathbf{x}_{2}=0,\mathbf{y}_{1}+\mathbf{y}_{2}=0\\}$, which is
an unbounded proper subset of $\mathbb{R}^{4}$. ∎

###  E.2 Analysis of AGDA-RR

######  Theorem E.1 (Convergence of AGDA-RR).

Let Assumptions 1, 3, and 4 be satisfied and let
$\eta=\nicefrac{{73l^{2}}}{{2\mu^{2}_{2}}}$. Then, for any
$\alpha\leq\nicefrac{{1}}{{5\eta nl}}$, $\beta=\eta\alpha$, and $K\geq 1$, the
iterates of AGDA-RR satisfy the following:

$\mathbb{E}[V_{\lambda}(\mathbf{z}^{K+1}_{0})]\leq(1-\mu_{1}n\alpha/2)^{K}V_{\lambda}(\mathbf{z}_{0})+0.42n\alpha^{2}l^{2}\sigma^{2}(3+\eta^{3})/\mu_{1}.$

Setting $\alpha=\min\\{1/5\eta
nl,4\log(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)/\mu_{1}nK\\}$ results in the
following expected last iterate convergence guarantee, which holds for any
$K\geq 1$:

$\displaystyle\mathbb{E}[V_{\lambda}(\mathbf{z}^{K+1}_{0})]$
$\displaystyle\leq
e^{\nicefrac{{-K}}{{365\kappa^{3}}}}V_{\lambda}(\mathbf{z}_{0})+\frac{\mu_{1}+c\kappa^{8}\sigma^{2}\log^{2}(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)}{\mu_{1}nK^{2}}$
$\displaystyle=\tilde{O}(e^{\nicefrac{{-K}}{{365\kappa^{3}}}}+\nicefrac{{1}}{{nK^{2}}}),$

where $\kappa=\max\\{\nicefrac{{l}}{{\mu_{1}}},\nicefrac{{l}}{{\mu_{2}}}\\}$
and $c>0$ is a numerical constant that is independent of $l,\mu_{1},\mu_{2}$
and $\sigma^{2}$.

###### Proof.

Before presenting the convergence analysis of AGDA-RR, we introduce some
additional notation. For any $k\in[K]$ and any random variable $Y$, we use
$\mathbb{E}_{k}[Y]$ to denote the expectation of $Y$ conditioned on all
previous epoch iterates $(\mathbf{x}^{j}_{0},\mathbf{y}^{j}_{0})_{j=1}^{k}$,
i.e., $\mathbb{E}_{k}[Y]=\mathbb{E}[Y\ |\
\mathbf{x}^{1}_{0},\mathbf{y}^{1}_{0},\ldots,\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0}]$.
Similarly, for any two random variables $Y,Z$, we use $\mathbb{E}_{k}[Y\ |\
Z]$ to denote the expectation of $Y$ conditioned on all previous epoch
iterates $(\mathbf{x}^{j}_{0},\mathbf{y}^{j}_{0})_{j=1}^{k}$ and $Z$, i.e.
$\mathbb{E}_{k}[Y\ |\ Z]=\mathbb{E}[Y\ |\
\mathbf{x}^{1}_{0},\mathbf{y}^{1}_{0},\ldots,\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0},Z]$.

Our analysis follows a structure similar to that of GDA-RR/SO and consists of
three major steps: 1. obtaining an epoch level update rule for AGDA-RR that
resembles the update of deterministic AGDA with noise, 2. bounding the noise
in the update rule using Lemma B.3, 3. presenting a convergence analysis with
respect to the Lyapunov function $V_{\lambda}$.

Step 1: Epoch level update rule We begin with the observation that the
$\mathbf{x}$-iterates of AGDA-RR are the same as that of gradient descent
without replacement on $F(\mathbf{x},\mathbf{y}^{k}_{0})$ and thus, can be
treated as a noisy version of full-batch gradient descent. To this end, we
linearize the stochastic gradients
$\nabla_{\mathbf{x}}f_{\tau_{k}(i)}(\mathbf{x}^{k}_{i-1},\mathbf{y}^{k}_{0})$
about $(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})$ and obtain the following
decomposition:

$\displaystyle\nabla_{\mathbf{x}}f_{\tau_{k}(i)}(\mathbf{x}^{k}_{i-1},\mathbf{y}^{k}_{0})$
$\displaystyle=\nabla_{\mathbf{x}}f_{\tau_{k}(i)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})+\left[\int_{0}^{1}\nabla^{2}_{\mathbf{x}\mathbf{x}}f_{\tau_{k}(i)}(\mathbf{x}^{k}_{0}+t(\mathbf{x}^{k}_{i-1}-\mathbf{x}^{k}_{0}),\mathbf{y}^{k}_{0})\textrm{d}t\right](\mathbf{x}^{k}_{i-1}-\mathbf{x}^{k}_{0})$
$\displaystyle=\nabla_{\mathbf{x}}f_{\tau_{k}(i)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})+\mathbf{H}_{\tau_{k}(i)}(\mathbf{x}^{k}_{i-1}-\mathbf{x}^{k}_{0}),$

where
$\mathbf{H}_{\tau_{k}(i)}=\int_{0}^{1}\nabla^{2}_{\mathbf{x}\mathbf{x}}f_{\tau_{k}(i)}(\mathbf{x}^{k}_{0}+t(\mathbf{x}^{k}_{i-1}-\mathbf{x}^{k}_{0}),\mathbf{y}^{k}_{0})\textrm{d}t$.
As before, by Rademacher’s Theorem, the $l$-smoothness of $f_{\tau_{k}(i)}$
guarantees that $\mathbf{H}_{\tau_{k}(i)}$ is well defined and satisfies
$\left\lvert\mathbf{H}_{\tau_{k}(i)}\right\rvert\leq l$.

When substituting the above linearization into the $\mathbf{x}$-iterate
updates, we observe the following:

$\displaystyle\mathbf{x}^{k}_{1}$
$\displaystyle=\mathbf{x}^{k}_{0}-\alpha\nabla_{\mathbf{x}}f_{\tau_{k}(1)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0}),$
$\displaystyle\mathbf{x}^{k}_{2}$
$\displaystyle=\mathbf{x}^{k}_{1}-\alpha\nabla_{\mathbf{x}}f_{\tau_{k}(2)}(\mathbf{x}^{k}_{1},\mathbf{y}^{k}_{0})=\mathbf{x}^{k}_{1}-\alpha\nabla_{\mathbf{x}}f_{\tau_{k}(2)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\alpha\mathbf{H}_{\tau_{k}(2)}(\mathbf{x}^{k}_{1}-\mathbf{x}^{k}_{0})$
$\displaystyle=\mathbf{x}^{k}_{0}-\alpha\nabla_{\mathbf{x}}f_{\tau_{k}(2)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\alpha\nabla_{\mathbf{x}}f_{\tau_{k}(1)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})+\alpha^{2}\mathbf{H}_{\tau_{k}(2)}\nabla_{\mathbf{x}}f_{\tau_{k}(1)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})$
$\displaystyle=\mathbf{x}^{k}_{0}-\alpha(\mathbf{I}-\alpha\mathbf{H}_{\tau_{k}(2)})\nabla_{\mathbf{x}}f_{\tau_{k}(1)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\alpha\nabla_{\mathbf{x}}f_{\tau_{k}(2)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0}).$

Repeating the above steps for subsequent iterates
$\mathbf{x}^{k}_{3},\ldots,\mathbf{x}^{k}_{n}$, we obtain the following epoch-
level update rule for $\mathbf{x}^{k+1}_{0}=\mathbf{x}^{k}_{n}$:

$\mathbf{x}^{k+1}_{0}=\mathbf{x}^{k}_{0}-\alpha\sum_{j=1}^{n}\left(\widetilde{\prod}_{t=j+1}^{n}(\mathbf{I}-\alpha\mathbf{H}_{\tau_{k}(t)})\right)\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0}).$
(E.1)

We further simplify (E.1) using the summation by parts identity. To this end,
we define $c_{j}$ and $e_{j}$ as follows:

$\displaystyle c_{j}$
$\displaystyle=\widetilde{\prod}_{t=j+1}^{n}(\mathbf{I}-\alpha\mathbf{H}_{\tau_{k}(t)}),$
$\displaystyle e_{j}$
$\displaystyle=\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0}).$

We note that $c_{n}=\mathbf{I}$, since
$\widetilde{\prod}_{t=n+1}^{n}(\mathbf{I}-\alpha\mathbf{H}_{\tau_{k}(t)})$
denotes the empty reverse product. Hence, we conclude,

$\displaystyle c_{n}\sum_{j=1}^{n}e_{j}$
$\displaystyle=\sum_{j=1}^{n}\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})=n\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0}),$
$\displaystyle\sum_{i=1}^{n-1}(c_{i+1}-c_{i})\sum_{j=1}^{i}e_{j}$
$\displaystyle=\sum_{i=1}^{n-1}\left[\widetilde{\prod}_{t=i+2}^{n}(\mathbf{I}-\alpha\mathbf{H}_{\tau_{k}(t)})-\widetilde{\prod}_{t=i+1}^{n}(\mathbf{I}-\alpha\mathbf{H}_{\tau_{k}(t)})\right]\sum_{j=1}^{i}\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})$
$\displaystyle=\alpha\sum_{i=1}^{n-1}\left[\widetilde{\prod}_{t=i+2}^{n}(\mathbf{I}-\alpha\mathbf{H}_{\tau_{k}(t)})\right]\mathbf{H}_{\tau_{k}(i+1)}\sum_{j=1}^{i}\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0}).$

We define $\mathbf{r}_{k}$ as,

$\mathbf{r}_{k}=\sum_{i=1}^{n-1}\left[\widetilde{\prod}_{t=i+2}^{n}(\mathbf{I}-\alpha\mathbf{H}_{\tau_{k}(t)})\right]\mathbf{H}_{\tau_{k}(i+1)}\sum_{j=1}^{i}\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0}).$
(E.2)

From the summation by parts identity
$\sum_{i=1}^{n}c_{i}e_{i}=c_{n}\sum_{j=1}^{n}e_{j}-\sum_{i=1}^{n-1}(c_{i+1}-c_{i})\sum_{j=1}^{i}e_{j}$,
we obtain the following:

$\sum_{j=1}^{n}\left[\widetilde{\prod}_{t=j+1}^{n}[\mathbf{I}-\alpha\mathbf{H}_{\tau_{k}(t)}]\right]\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})=n\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\alpha\mathbf{r}_{k}.$

By substituting the above equation into (E.1), we obtain the following update
rule for the epoch iterates $\mathbf{x}^{k}_{0}$:

$\mathbf{x}^{k+1}_{0}=\mathbf{x}^{k}_{0}-n\alpha\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})+\alpha^{2}\mathbf{r}_{k}.$
(E.3)

The epoch-level update rule for the $\mathbf{y}$-iterate is derived in a
similar fashion. We begin by linearizing
$\nabla_{\mathbf{y}}f_{\pi_{k}(i)}(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{i-1})$
as:

$\displaystyle\nabla_{\mathbf{y}}f_{\pi_{k}(i)}(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{i-1})=\nabla_{\mathbf{y}}f(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})+\mathbf{J}_{\pi_{k}(i)}(\mathbf{y}^{k}_{i-1}-\mathbf{y}^{k}_{0}),$

where
$\mathbf{J}_{\pi_{k}(i)}=\int_{0}^{1}\nabla^{2}_{\mathbf{y}\mathbf{y}}f_{\pi_{k}(i)}(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0}+t(\mathbf{y}^{k}_{i-1}-\mathbf{y}^{k}_{0}))\textrm{d}t$
satisfies $\left\lvert\mathbf{J}_{\pi_{k}(i)}\right\rvert\leq l$. As before,
by substituting into the $\mathbf{y}$ iterate updates and unrolling, we
obtain,

$\mathbf{y}^{k+1}_{0}=\mathbf{y}^{k}_{0}+\beta\sum_{j=1}^{n}\left[\widetilde{\prod}_{t=j+1}^{n}[\mathbf{I}+\beta\mathbf{J}_{\pi_{k}(t)}]\right]\nabla_{\mathbf{y}}f_{\pi_{k}(j)}(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0}).$
(E.4)

Once again, applying the summation by parts technique gives us the following
update rule for the epoch iterates $\mathbf{y}^{k}_{0}$:

$\mathbf{y}^{k+1}_{0}=\mathbf{y}^{k}_{0}+n\beta\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})+\beta^{2}\mathbf{s}_{k},$
(E.5)

where $\mathbf{s}_{k}$ is given by,

$\mathbf{s}_{k}=\sum_{i=1}^{n-1}\left[\widetilde{\prod}_{t=i+2}^{n}(\mathbf{I}+\beta\mathbf{J}_{\pi_{k}(t)})\right]\mathbf{J}_{\pi_{k}(i+1)}\sum_{j=1}^{i}\nabla_{\mathbf{y}}f_{\pi_{k}(j)}(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0}).$
(E.6)

Step 2: Controlling the noise terms By applying the triangle inequality on
(E.2) and substituting $\left\lvert\mathbf{H}_{\tau_{k}}(i)\right\rvert\leq l$
and $\alpha\leq 1/5nl$ wherever required, we bound
$\left\lvert\mathbf{r}_{k}\right\rvert$ as follows:

$\displaystyle\left\lvert\mathbf{r}_{k}\right\rvert$
$\displaystyle\leq\sum_{i=1}^{n-1}\left[\widetilde{\prod}_{t=i+2}^{n}\left\lvert\mathbf{I}-\alpha\mathbf{H}_{\tau_{k}(t)}\right\rvert\right]\left\lvert\mathbf{H}_{\tau_{k}(i+1)}\right\rvert|\sum_{j=1}^{i}\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})|$
$\displaystyle\leq l(1+\alpha
l)^{n}\sum_{i=1}^{n-1}|\sum_{j=1}^{i}\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})|\leq
le^{1/5}\sum_{i=1}^{n-1}|\sum_{j=1}^{i}\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})|$
$\displaystyle\leq
le^{1/5}\sum_{i=1}^{n-1}i|\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})+1/i\sum_{j=1}^{i}\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})|$
$\displaystyle\leq
le^{1/5}\left[n^{2}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert/2+\sum_{i=1}^{n-1}i|\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-1/i\sum_{j=1}^{i}\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})|\right].$

By defining
$d_{k,i}=|\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-1/i\sum_{j=1}^{i}\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})|$
and substituting into the above inequality, we obtain,

$\left\lvert\mathbf{r}_{k}\right\rvert\leq
le^{1/5}\left[n^{2}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert/2+\sum_{i=1}^{n-1}id_{k,i}\right].$
(E.7)

By applying Young’s inequality to (E.7), we conclude:

$\left\lvert\mathbf{r}_{k}\right\rvert^{2}\leq
2l^{2}e^{2/5}\left[n^{4}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}/4+(n-1)\sum_{i=1}^{n-1}i^{2}d^{2}_{k,i}\right].$
(E.8)

By Lemma B.3 and the bounded gradient variance assumption, we bound
$\mathbb{E}[d^{2}_{k,i}]$ as follows:

$\mathbb{E}[d^{2}_{k,i}]=\frac{n-i}{i(n-1)}\left[1/n\sum_{i=1}^{n}|\nabla_{\mathbf{x}}f_{i}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})|^{2}\right]\leq\frac{n-i}{i(n-1)}\sigma^{2},$
(E.9)

where the expectation is taken over the uniformly sampled random permutation
$\tau_{k}$. Furthermore, applying Jensen’s inequality to (E.9) gives us the
following bound:

$\displaystyle\mathbb{E}[d_{k,i}]\leq\sqrt{\mathbb{E}[d^{2}_{k,i}]}\leq\sigma\sqrt{\frac{n-i}{i(n-1)}}.$
(E.10)

From (E.10), it follows that,

$\displaystyle\sum_{i=1}^{n-1}i\mathbb{E}[d_{k,i}]$
$\displaystyle\leq\sigma\sum_{i=1}^{n-1}\sqrt{i}\sqrt{\frac{n-i}{n-1}}\leq\sigma\sum_{i=1}^{n-1}\sqrt{i}\leq\frac{2\sigma
n^{3/2}}{3}.$

By taking expectations of (E.7) and substituting the above, we get,

$\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert]\leq\frac{2n^{2}l}{3}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert+\sigma
ln^{3/2}.$ (E.11)

Similarly, from (E.9), it follows that,

$\displaystyle(n-1)\sum_{i=1}^{n-1}i^{2}\mathbb{E}[d_{k,i}^{2}]\leq\sigma^{2}\sum_{i=1}^{n-1}i(n-i)\leq\frac{\sigma^{2}n^{3}}{6}.$

By taking expectations of (E.8) and substituting the above, we obtain,

$\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]\leq\frac{3n^{4}l^{2}}{4}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}+\frac{\sigma^{2}l^{2}n^{3}}{2}.$
(E.12)

We bound $\mathbb{E}[\left\lvert\mathbf{s}_{k}\right\rvert]$ and
$\mathbb{E}[\left\lvert\mathbf{s}_{k}\right\rvert^{2}]$ by following a similar
strategy and obtain:

$\mathbb{E}[\left\lvert\mathbf{s}_{k}\right\rvert]\leq\frac{2n^{2}l}{3}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert+\sigma
ln^{3/2},$ (E.13)
$\mathbb{E}[\left\lvert\mathbf{s}_{k}\right\rvert^{2}]\leq\frac{3n^{4}l^{2}}{4}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}+\frac{\sigma^{2}l^{2}n^{3}}{2}.$
(E.14)

Step 3: Obtaining a convergence guarantee We begin by defining $a_{k}$ and
$b_{k}$ as:

$\displaystyle a_{k}$ $\displaystyle=\Phi(\mathbf{x}^{k}_{0})-\Phi^{*},$
$\displaystyle b_{k}$
$\displaystyle=\Phi(\mathbf{x}^{k}_{0})-F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0}).$

By definition of $V_{\lambda}$, we conclude that
$V_{\lambda}(\mathbf{z}^{k}_{0})=a_{k}+\lambda b_{k}$. Furthermore, we note
that by Lemma E.2, $\Phi$ is $L$-smooth where $L=l+l^{2}/\mu_{2}$. Since
$\alpha\leq 1/5\eta nl$, it follows that $n\alpha L\leq 1$. Using these
properties, we obtain the following:

$\displaystyle\Phi(\mathbf{x}^{k+1}_{0})-\Phi(\mathbf{x}^{k}_{0})$
$\displaystyle\leq\left\langle\nabla\Phi(\mathbf{x}^{k}_{0}),\mathbf{x}^{k+1}_{0}-\mathbf{x}^{k}_{0}\right\rangle+\frac{L}{2}\left\lvert\mathbf{x}^{k+1}_{0}-\mathbf{x}^{k}_{0}\right\rvert^{2}$
$\displaystyle\leq\left\langle\nabla\Phi(\mathbf{x}^{k}_{0}),-n\alpha\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})+\alpha^{2}\mathbf{r}_{k}\right\rangle+\frac{L}{2}\left\lvert-n\alpha\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})+\alpha^{2}\mathbf{r}_{k}\right\rvert^{2}$
$\displaystyle\leq-n\alpha\left\langle\nabla\Phi(\mathbf{x}^{k}_{0}),\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\frac{\alpha}{n}\mathbf{r}_{k}\right\rangle+\frac{L}{2}n^{2}\alpha^{2}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\frac{\alpha}{n}\mathbf{r}_{k}\right\rvert^{2}$
$\displaystyle\leq\frac{n\alpha}{2}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla\Phi(\mathbf{x}^{k}_{0})-\frac{\alpha}{n}\mathbf{r}_{k}\right\rvert^{2}-\frac{n\alpha}{2}\left\lvert\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}$
$\displaystyle\leq
n\alpha\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}-\frac{n\alpha}{2}\left\lvert\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}+\frac{\alpha^{3}}{n}\left\lvert\mathbf{r}_{k}\right\rvert^{2}.$

By taking expectations conditioned on the epoch iterates
$(\mathbf{x}^{j}_{0},\mathbf{y}^{j}_{0})_{j=1}^{k}$ and substituting the bound
(E.12), we obtain the following:

$\displaystyle\mathbb{E}_{k}[\Phi(\mathbf{x}^{k+1}_{0})]-\Phi(\mathbf{x}^{k}_{0})$
$\displaystyle\leq
n\alpha\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}-\frac{n\alpha}{2}\left\lvert\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}$
$\displaystyle+\frac{3n^{3}\alpha^{3}l^{2}}{4}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}_{0}^{k},\mathbf{y}_{0}^{k})\right\rvert^{2}+\frac{n^{2}\alpha^{3}l^{2}\sigma^{2}}{2}.$
(E.15)

We proceed by applying the $l$-smoothness of $-F(\mathbf{x},\mathbf{y})$ in
$\mathbf{x}$, to obtain the following:

$\displaystyle
F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})$
$\displaystyle\leq-\left\langle\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0}),\mathbf{x}^{k+1}_{0}-\mathbf{x}^{k}_{0}\right\rangle+\frac{l}{2}\left\lvert\mathbf{x}^{k+1}_{0}-\mathbf{x}^{k}_{0}\right\rvert^{2}$
$\displaystyle\leq\left\langle\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0}),n\alpha\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\alpha^{2}\mathbf{r}_{k}\right\rangle$
$\displaystyle+\frac{l}{2}\left\lvert
n\alpha\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\alpha^{2}\mathbf{r}_{k}\right\rvert^{2}$
$\displaystyle\leq(n\alpha+\frac{l}{2}n^{2}\alpha^{2})\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}+\frac{l}{2}\left\lvert\alpha^{2}\mathbf{r}_{k}\right\rvert^{2}$
$\displaystyle-(\alpha^{2}+ln\alpha^{3})\left\langle\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0}),\mathbf{r}_{k}\right\rangle$
$\displaystyle\leq(n\alpha+\frac{l}{2}n^{2}\alpha^{2})\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}+\frac{l\alpha^{4}}{2}\left\lvert\mathbf{r}_{k}\right\rvert^{2}$
$\displaystyle+\frac{6\alpha^{2}}{5}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert\left\lvert\mathbf{r}_{k}\right\rvert.$
(E.16)

From (E.11) and (E.12), we infer that:

$\displaystyle\frac{l\alpha^{4}}{2}\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert^{2}]$
$\displaystyle\leq\frac{3n^{4}\alpha^{4}l^{3}}{8}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}+\frac{\sigma^{2}l^{3}\alpha^{4}n^{3}}{4}$
$\displaystyle\leq\frac{3n^{4}\alpha^{4}l^{3}}{8}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}+\frac{\sigma^{2}l^{2}\alpha^{3}n^{2}}{20},$
$\displaystyle\frac{6\alpha^{2}}{5}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}_{0}^{k},\mathbf{y}_{0}^{k})\right\rvert\mathbb{E}[\left\lvert\mathbf{r}_{k}\right\rvert]$
$\displaystyle\leq\frac{6\alpha^{2}n^{\frac{3}{2}}\sigma
l}{5}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}_{0}^{k},\mathbf{y}_{0}^{k})\right\rvert+\frac{4n^{2}\alpha^{2}l}{5}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}_{0}^{k},\mathbf{y}_{0}^{k})\right\rvert^{2}$
$\displaystyle=(\frac{6\alpha^{\frac{3}{2}}nl\sigma}{5})(\alpha^{\frac{1}{2}}n^{\frac{1}{2}}\left\lvert\nabla_{\mathbf{x}}F(x_{0}^{k},y_{0}^{k})\right\rvert)+\frac{4n^{2}\alpha^{2}l}{5}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}_{0}^{k},\mathbf{y}_{0}^{k})\right\rvert^{2}$
$\displaystyle\leq(\frac{n\alpha}{2}+\frac{4n^{2}\alpha^{2}l}{5})\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}_{0}^{k},\mathbf{y}_{0}^{k})\right\rvert^{2}+\frac{18\alpha^{3}n^{2}l^{2}\sigma^{2}}{25}.$

Taking expectations on both sides of (E.16) by conditioning on the epoch
iterates $(\mathbf{x}^{j}_{0},\mathbf{y}^{j}_{0})_{j=1}^{k}$ and substituting
the above inequalities, we obtain:

$F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\mathbb{E}_{k}[F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})]\leq(\frac{3n\alpha}{2}+\frac{13}{10}ln^{2}\alpha^{2}+\frac{3n^{4}\alpha^{4}l^{3}}{8})\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}_{0}^{k},\mathbf{y}_{0}^{k})\right\rvert^{2}+\frac{4\alpha^{3}n^{2}l^{2}\sigma^{2}}{5}.$
(E.17)

We now apply the $l$-smoothness of $-F(\mathbf{x},\mathbf{y})$ in $\mathbf{y}$
to obtain the following:

$\displaystyle
F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})-F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k+1}_{0})$
$\displaystyle\leq-\left\langle\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0}),\mathbf{y}^{k+1}_{0}-\mathbf{y}^{k}_{0}\right\rangle+\frac{l}{2}\left\lvert\mathbf{y}^{k+1}_{0}-\mathbf{y}^{k}_{0}\right\rvert^{2}$
$\displaystyle\leq-\left\langle\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0}),n\beta\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})+\beta^{2}\mathbf{s}_{k}\right\rangle$
$\displaystyle+\frac{l}{2}\left\lvert
n\beta\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})+\beta^{2}\mathbf{s}_{k}\right\rvert^{2}$
$\displaystyle\leq(-n\beta+ln^{2}\beta^{2})\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}$
$\displaystyle+\beta^{2}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert\left\lvert\mathbf{s}_{k}\right\rvert+l\beta^{4}\left\lvert\mathbf{s}_{k}\right\rvert^{2}.$
(E.18)

From (E.13) and (E.14), we conclude,

$\displaystyle
l\beta^{4}\mathbb{E}[\left\lvert\mathbf{s}_{k}\right\rvert^{2}]$
$\displaystyle\leq\frac{3n^{4}l^{3}\beta^{4}}{4}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}+\frac{\sigma^{2}l^{3}n^{3}\beta^{4}}{2}$
$\displaystyle\leq\frac{3n^{4}l^{3}\beta^{4}}{4}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}+\frac{\sigma^{2}l^{2}n^{2}\beta^{3}}{10},$
$\displaystyle\beta^{2}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert\mathbb{E}[\left\lvert\mathbf{s}_{k}\right\rvert]$
$\displaystyle\leq\sigma
ln^{3/2}\beta^{2}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert+\frac{2n^{2}\beta^{2}l}{3}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}$
$\displaystyle\leq(\frac{n^{\frac{1}{2}}\beta^{\frac{1}{2}}}{2}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert)(2n\beta^{\frac{3}{2}}l\sigma)+\frac{2n^{2}\beta^{2}l}{3}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}$
$\displaystyle\leq(\frac{n\beta}{8}+\frac{2n^{2}\beta^{2}l}{3})\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}+2n^{2}\beta^{3}l^{2}\sigma^{2}.$

We proceed by taking expectations on both sides of (E.18) by conditioning on
the epoch iterates $(\mathbf{x}^{j}_{0},\mathbf{y}^{j}_{0})_{j=1}^{k}$ and
$\mathbf{x}^{k+1}_{0}$ and substituting the above bounds. Consequently, we
obtain the following inequality:

$\displaystyle
F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})-\mathbb{E}_{k}[F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k+1}_{0})|\mathbf{x}^{k+1}_{0}]$
$\displaystyle\leq(-\frac{7n\beta}{8}+\frac{5n^{2}\beta^{2}l}{3}+\frac{3n^{4}\beta^{4}l^{3}}{4})\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}$
$\displaystyle+\frac{21n^{2}\beta^{3}l^{2}\sigma^{2}}{10}$
$\displaystyle\leq-\frac{n\beta}{2}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}+\frac{21n^{2}\beta^{3}l^{2}\sigma^{2}}{10}.$

The two-sided PŁ condition on $F$ implies that,

$\displaystyle-\frac{n\beta}{2}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}$
$\displaystyle\leq-n\beta\mu_{2}[\Phi(\mathbf{x}^{k+1}_{0})-F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})],$

which gives us the following:

$\mathbb{E}_{k}[\Phi(\mathbf{x}^{k+1}_{0})-F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k+1}_{0})|\mathbf{x}^{k+1}_{0}]\leq(1-n\beta\mu_{2})[\Phi(\mathbf{x}^{k+1}_{0})-F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})]+\frac{21n^{2}\beta^{3}l^{2}\sigma^{2}}{10}.$

Taking expectations of the above with respect to $\mathbf{x}^{k+1}_{0}$ and
applying the law of iterated expectation, we obtain:

$\mathbb{E}_{k}[\Phi(\mathbf{x}^{k+1}_{0})-F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k+1}_{0})]\leq(1-n\beta\mu_{2})\mathbb{E}_{k}[\Phi(\mathbf{x}^{k+1}_{0})-F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})]+\frac{21n^{2}\beta^{3}l^{2}\sigma^{2}}{10}.$
(E.19)

From (E.2), we obtain the following:

$\mathbb{E}_{k}[a_{k+1}]\leq
a_{k}+n\alpha\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}-\frac{n\alpha}{2}\left\lvert\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}\\\
+\frac{3n\alpha}{100}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}_{0}^{k},\mathbf{y}_{0}^{k})\right\rvert^{2}+\frac{n^{2}\alpha^{3}l^{2}\sigma^{2}}{2}.$
(E.20)

Furthermore, we note that,

$\displaystyle\Phi(\mathbf{x}^{k+1}_{0})-F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})=b_{k}+F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})+\Phi(\mathbf{x}^{k+1}_{0})-\Phi(\mathbf{x}^{k}_{0}).$

By substituting the above into (E.19), we obtain the following:

$\mathbb{E}_{k}[b_{k+1}]\leq(1-n\beta\mu_{2})b_{k}+(1-n\beta\mu_{2})\mathbb{E}_{k}[F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})]\\\
+(1-n\beta\mu_{2})\mathbb{E}_{k}[\Phi(\mathbf{x}^{k+1}_{0})-\Phi(\mathbf{x}^{k}_{0})]+\frac{21n^{2}\beta^{3}l^{2}\sigma^{2}}{10}.$

By substituting (E.17) and (E.2) into the above, we obtain:

$\displaystyle\mathbb{E}_{k}[b_{k+1}]$
$\displaystyle\leq(1-n\beta\mu_{2})b_{k}+(1-n\beta\mu_{2})n\alpha\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}$
$\displaystyle-(1-n\beta\mu_{2})\frac{n\alpha}{2}\left\lvert\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}+(1-n\beta\mu_{2})\frac{9n\alpha}{5}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}$
$\displaystyle+(1-n\beta\mu_{2})\frac{13n^{2}\alpha^{3}l^{2}\sigma^{2}}{10}+\frac{21n^{2}\beta^{3}l^{2}\sigma^{2}}{10}.$
(E.21)

From (E.20) and (E.21), we get the following by substituting
$V_{\lambda}(\mathbf{z}^{k+1}_{0})=a_{k+1}+\lambda b_{k+1}$,

$\mathbb{E}_{k}[V_{\lambda}(\mathbf{z}^{k+1}_{0})]\leq
a_{k}+(1-n\beta\mu_{2})\lambda b_{k}+[n\alpha+\lambda
n\alpha(1-n\beta\mu_{2})]\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}+C_{3}\\\
-[\frac{n\alpha}{2}+\frac{\lambda
n\alpha}{2}(1-n\beta\mu_{2})]\left\lvert\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}+[\frac{3n\alpha}{100}+\lambda(1-n\beta\mu_{2})\frac{9n\alpha}{5}]\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2},$
(E.22)

where $C_{3}$ is defined as follows:

$\displaystyle
C_{3}=[\frac{1}{2}+\frac{13\lambda}{10}(1-n\beta\mu_{2})]n^{2}\alpha^{3}l^{2}\sigma^{2}+\frac{21\lambda
n^{2}\beta^{3}l^{2}\sigma^{2}}{10}.$

By Young’s inequality, the following holds for any $\varepsilon\in(0,1]$:

$\displaystyle\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}$
$\displaystyle\leq(1+\varepsilon)\left\lvert\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}+(1+1/\varepsilon)\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}.$

Substituting this into (E.22), we obtain the following:

$\mathbb{E}_{k}[V_{\lambda}(\mathbf{z}^{k+1}_{0})]\leq
a_{k}+(1-n\beta\mu_{2})\lambda b_{k}+C_{3}\\\
-[\frac{n\alpha}{2}-(1+\varepsilon)\frac{3n\alpha}{100}-\lambda(1-n\beta\mu_{2})[(1+\varepsilon)\frac{9n\alpha}{5}-\frac{n\alpha}{2}]]\left\lvert\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}\\\
+[n\alpha+(1+1/\varepsilon)\frac{3n\alpha}{100}+\lambda(1-n\beta\mu_{2})[n\alpha+(1+1/\varepsilon)\frac{9n\alpha}{5}]]\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}.$
(E.23)

From Lemma E.2, we know that $\Phi(\mathbf{x})$ satisfies the PŁ inequality
with constant $\mu_{1}$. Thus, we conclude that

$\left\lvert\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}\geq
2\mu_{1}(\Phi(\mathbf{x}^{k}_{0})-\Phi^{*})=2\mu_{1}a_{k}.$ (E.24)

Let $\mathbf{y}^{*}(\mathbf{x}^{k}_{0})$ denote the projection of
$\mathbf{y}^{k}_{0}$ on the set
$\arg\max_{\mathbf{y}}F(\mathbf{x}^{k}_{0},\mathbf{y})$. From Lemma E.2, we
conclude that
$\nabla\Phi(\mathbf{x}^{k}_{0})=\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{*}(\mathbf{x}^{k}_{0}))$.
Thus,

$\displaystyle\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}$
$\displaystyle\leq\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{*}(\mathbf{x}^{k}_{0}))\right\rvert^{2}$
$\displaystyle\leq
l^{2}\left\lvert\mathbf{y}^{k}_{0}-\mathbf{y}^{*}(\mathbf{x}^{k}_{0})\right\rvert^{2}$
(E.25)

Furthermore, we note that Assumption 3 implies that
$-F(\mathbf{x}^{k}_{0},\mathbf{y})$ satisfies the PŁ inequality with constant
$\mu_{2}$. Thus, by Lemma E.3, we conclude that,

$\displaystyle
b_{k}=\Phi(\mathbf{x}^{k}_{0})-F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\geq\frac{\mu_{2}}{2}\left\lvert\mathbf{y}^{k}_{0}-\mathbf{y}^{*}(\mathbf{x}^{k}_{0})\right\rvert^{2}.$

By substituting the above inequality in (E.25), we conclude that,

$\displaystyle\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}\leq\frac{2l^{2}b_{k}}{\mu_{2}}.$

We proceed by substituting the above bound in (E.23) to obtain the following
upper bound on $\mathbb{E}_{k}[V_{\lambda}(\mathbf{z}^{k+1}_{0})]$:

$\mathbb{E}_{k}[V_{\lambda}(\mathbf{z}^{k+1}_{0})]\leq\\{1-[\mu_{1}n\alpha-(1+\varepsilon)\frac{3\mu_{1}n\alpha}{50}-\lambda(1-n\beta\mu_{2})[(1+\varepsilon)\frac{18\mu_{1}n\alpha}{5}-\mu_{1}n\alpha]]\\}a_{k}+C_{3}\\\
+[1-n\beta\mu_{2}+\frac{2l^{2}n\alpha}{\mu_{2}\lambda}+(1+1/\varepsilon)\frac{3l^{2}n\alpha}{50\mu_{2}\lambda}+(1-n\beta\mu_{2})[\frac{2l^{2}n\alpha}{\mu_{2}}+(1+1/\varepsilon)\frac{18l^{2}n\alpha}{5\mu_{2}}]]\lambda
b_{k}.$

Hence, we obtain the following update equation for
$V_{\lambda}(\mathbf{z}^{k+1}_{0})$:

$\mathbb{E}_{k}[V_{\lambda}(\mathbf{z}^{k+1}_{0})]\leq C_{1}a_{k}+C_{2}\lambda
b_{k}+C_{3},$ (E.26)

where $C_{1}$, $C_{2}$ and $C_{3}$ are given by,

$\displaystyle C_{1}$
$\displaystyle=1-[\mu_{1}n\alpha-(1+\varepsilon)\frac{3\mu_{1}n\alpha}{50}-\lambda(1-n\beta\mu_{2})[(1+\varepsilon)\frac{18\mu_{1}n\alpha}{5}-\mu_{1}n\alpha]]$
$\displaystyle=1-\mu_{1}n\alpha[1-\frac{3(1+\varepsilon)}{50}-\lambda(1-n\beta\mu_{2})[\frac{18(1+\varepsilon)}{5}-1]],$
$\displaystyle C_{2}$
$\displaystyle=1-n\beta\mu_{2}+\frac{2l^{2}n\alpha}{\mu_{2}\lambda}+(1+1/\varepsilon)\frac{3l^{2}n\alpha}{50\mu_{2}\lambda}+(1-n\beta\mu_{2})[\frac{2l^{2}n\alpha}{\mu_{2}}+(1+1/\varepsilon)\frac{18l^{2}n\alpha}{5\mu_{2}}]$
$\displaystyle=1-\frac{2l^{2}n\alpha}{\mu_{2}}[\frac{\beta\mu_{2}^{2}}{2\alpha
l^{2}}-\frac{1}{\lambda}-(1+1/\varepsilon)\frac{3}{100\lambda}-(1-n\beta\mu_{2})[1+(1+1/\varepsilon)\frac{9}{5}]],$
$\displaystyle C_{3}$
$\displaystyle=[\frac{1}{2}+\frac{13\lambda}{10}(1-n\beta\mu_{2})]n^{2}\alpha^{3}l^{2}\sigma^{2}+\frac{21\lambda
n^{2}\beta^{3}l^{2}\sigma^{2}}{10}.$

By setting $\lambda=\frac{1}{10},\varepsilon=\frac{3}{7}$ and
$\eta=\frac{73l^{2}}{2\mu_{2}^{2}}$ and using $l^{2}\geq\mu_{1}\mu_{2}$, we
conclude:

$\displaystyle C_{1}$ $\displaystyle\leq 1-\mu_{1}n\alpha/2,$ $\displaystyle
C_{2}$ $\displaystyle\leq 1-\frac{l^{2}n\alpha}{2\mu_{2}}\leq
1-\mu_{1}n\alpha/2,$ $\displaystyle C_{3}$ $\displaystyle\leq
0.21n^{2}\alpha^{3}l^{2}\sigma^{2}(3+\eta^{3})$

From the above bounds, it follows that:

$\displaystyle\mathbb{E}_{k}[V_{\lambda}(\mathbf{z}^{k+1}_{0})]\leq(1-\mu_{1}n\alpha/2)V_{\lambda}(\mathbf{z}^{k}_{0})+0.21n^{2}\alpha^{3}l^{2}\sigma^{2}(3+\eta^{3}).$

By taking expectations with respect to the epoch iterates
$(\mathbf{x}^{j}_{0},\mathbf{y}^{j}_{0})_{j=1}^{k}$ and applying the law of
iterated expectation, we obtain the following:

$\displaystyle\mathbb{E}[V_{\lambda}(\mathbf{z}^{k+1}_{0})]\leq(1-\mu_{1}n\alpha/2)\mathbb{E}[V_{\lambda}(\mathbf{z}^{k}_{0})]+0.21n^{2}\alpha^{3}l^{2}\sigma^{2}(3+\eta^{3}).$

By unrolling the above inequality for $K$ steps, we obtain the following:

$\mathbb{E}[V_{\lambda}(\mathbf{z}^{K+1}_{0})]\leq(1-\mu_{1}n\alpha/2)^{K}V_{\lambda}(\mathbf{z}_{0})+0.42n\alpha^{2}l^{2}\sigma^{2}(3+\eta^{3})/\mu_{1}.$
(E.27)

By setting $\alpha=\min\\{1/5\eta
nl,4\log(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)/\mu_{1}nK\\}$ and using
$\eta\leq 37\kappa^{2}$, we observe that:

$\displaystyle n\alpha^{2}l^{2}\sigma^{2}(3+\eta^{3})/\mu_{1}$
$\displaystyle\leq\frac{16l^{2}\sigma^{2}(3+\eta^{3})}{\mu_{1}^{3}}\frac{\log^{2}(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)}{nK^{2}}$
$\displaystyle\leq\frac{c\kappa^{8}\sigma^{2}\log^{2}(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)}{\mu_{1}nK^{2}},$

where $c>0$ is a constant that is independent of $\kappa,\mu$ and
$\sigma^{2}$. By substituting the above into (E.27), we get:

$\mathbb{E}[V_{\lambda}(\mathbf{z}^{K+1}_{0})]\leq(1-\mu_{1}n\alpha/2)^{K}V_{\lambda}(\mathbf{z}_{0})+\frac{c\kappa^{8}\sigma^{2}\log^{2}(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)}{\mu_{1}nK^{2}}.$
(E.28)

To complete the proof, we consider the following cases:

Case 1: $1/5\eta nl\leq 4\log(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)/\mu_{1}nK$

In this case, $\alpha=1/5\eta nl$ and hence, we get:

$\displaystyle(1-n\alpha\mu_{1}/2)^{K}V_{\lambda}(\mathbf{z}_{0})\leq
e^{-n\alpha\mu_{1}K/2}V_{\lambda}(\mathbf{z}_{0})\leq
e^{-\frac{K}{365\kappa^{3}}}V_{\lambda}(\mathbf{z}_{0}).$

Substituting into (E.28), we get:

$\mathbb{E}[V_{\lambda}(\mathbf{z}^{K+1}_{0})]\leq
e^{-\frac{K}{365\kappa^{3}}}V_{\lambda}(\mathbf{z}_{0})+\frac{c\kappa^{8}\sigma^{2}\log^{2}(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)}{\mu_{1}nK^{2}}.$
(E.29)

Case 2: $1/5\eta nl\leq
4\log(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)/(\mu_{1}nK)$

In this case, $\alpha=4\log(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)/\mu_{1}nK$
and we conclude that,

$\displaystyle(1-n\alpha\mu_{1}/2)^{K}V_{\lambda}(\mathbf{z}_{0})$
$\displaystyle\leq e^{-n\alpha\mu_{1}K/2}V_{\lambda}(\mathbf{z}_{0})\leq
e^{-2\log(V_{\lambda}(\mathbf{z}_{0})^{1/2}n^{1/2}K)}V_{\lambda}(\mathbf{z}_{0})\leq\frac{1}{nK^{2}}.$

By substituting into (E.28), we get:

$\mathbb{E}[V_{\lambda}(\mathbf{z}^{K+1}_{0})]\leq\frac{\mu_{1}+c\kappa^{8}\sigma^{2}\log^{2}(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)}{\mu_{1}nK^{2}}.$
(E.30)

By taking the maximum of the right hand side of (E.29) and (E.30), we obtain
the following rate, which holds for any $K\geq 1$:

$\displaystyle\mathbb{E}[V_{\lambda}(\mathbf{z}^{K+1}_{0})]\leq
e^{-\frac{K}{365\kappa^{3}}}V_{\lambda}(\mathbf{z}_{0})+\frac{\mu_{1}+c\kappa^{8}\sigma^{2}\log^{2}(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)}{\mu_{1}nK^{2}}.$

Suppressing constant terms and logarithmic factors, we get,

$\displaystyle\mathbb{E}[V_{\lambda}(\mathbf{z}^{K+1}_{0})]=\tilde{O}(e^{-\frac{K}{365\kappa^{3}}}+\nicefrac{{1}}{{nK^{2}}}).$

∎

#### Bounded iterate assumption

We now demonstrate that our analysis of AGDA-RR easily adapts to the bounded
iterate setting. To this end, we assume that all the iterates of AGDA-RR,
i.e., the iterates $(\mathbf{x}^{k}_{i},\mathbf{y}^{k}_{0})$ and
$(\mathbf{x}^{k}_{n},\mathbf{y}^{k}_{i})$ where $i\in[n]$ and $k\in[K]$ are
contained within a compact set $\mathcal{W}$. Furthermore, we note that the
$l$-smoothness of the $f_{i}$’s guarantees that the function
$G_{\sigma}(\mathbf{x},\mathbf{y})=1/n\sum_{i=1}^{n}\left\lvert\omega_{i}(\mathbf{x},\mathbf{y})-\nu(\mathbf{x},\mathbf{y})\right\rvert^{2}$
is non-negative and continuous. Hence,
$\sigma^{2}=\max_{(\mathbf{x},\mathbf{y})\in\mathcal{W}}G_{\sigma}(\mathbf{x},\mathbf{y})$
is non-negative and finite. Since
$(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\in\mathcal{W}$ and
$(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\in\mathcal{W}$, we conclude that

$\displaystyle
1/n\sum_{i=1}^{n}\left\lvert\omega_{i}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nu(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}\leq\sigma^{2},$
$\displaystyle
1/n\sum_{i=1}^{n}\left\lvert\omega_{i}(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})-\nu(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}\leq\sigma^{2}.$

Substituting the above inequalities into Step 2 of Theorem E.1 shows that our
convergence analysis of AGDA-RR straightforwardly adapts to the bounded
iterate setting. The same argument also applies to our analysis of AGDA-AS.

#### Convergence in terms of $\textrm{dist}(\mathbf{z},\mathcal{Z}^{*})^{2}$

Let $\mathcal{Z}^{*}$ denote the set of all saddle points of the objective $F$
and let $\textrm{dist}(\mathbf{z},\mathcal{Z}^{*})$ denote the distance of a
point $\mathbf{z}\in\mathbb{R}^{d}$ from $\mathcal{Z}^{*}$. As we demonstrate
in Appendix E.4, the Lyapunov function $V_{\lambda}$ used in our analysis
satisfies the following:

$\textrm{dist}(\mathbf{z},\mathcal{Z}^{*})^{2}\leq\max\left\\{\frac{2}{\mu_{1}}(\frac{l^{2}}{2\mu_{2}}+1),\frac{4}{\lambda\mu_{2}}\right\\}V_{\lambda}(\mathbf{z}).$

Using the above relation, the convergence guarantee of Theorem E.1 can be
translated to a guarantee of the form
$\mathbb{E}[\textrm{dist}(\mathbf{z}^{K+1}_{0},\mathcal{Z}^{*})^{2}]=\tilde{O}(e^{-\nicefrac{{K}}{{365\kappa^{3}}}}+\nicefrac{{1}}{{nK^{2}}})$.
Thus, the epoch iterates $\mathbf{z}^{K+1}_{0}$ of AGDA-RR converge (in
expectation) to some saddle point of $F$ at a rate of
$\tilde{O}(e^{-\nicefrac{{K}}{{365\kappa^{3}}}}+\nicefrac{{1}}{{nK^{2}}})$. A
similar argument also applies to AGDA-AS.

###  E.3 Analysis of AGDA-AS

######  Theorem E.2 (Convergence of AGDA-AS).

Let Assumptions 1, 3, and 4 be satisfied and let
$\eta=\nicefrac{{73l^{2}}}{{2\mu^{2}_{2}}}$. Then, for any
$\alpha\leq\nicefrac{{1}}{{5\eta nl}}$, $\beta=\eta\alpha$, and $K\geq 1$, the
iterates of AGDA-AS satisfy the following:

$\max_{\tau_{1},\pi_{1},\ldots,\tau_{K},\pi_{K}\in\mathbb{S}_{n}}V_{\lambda}(\mathbf{z}^{K+1}_{0})\leq(1-\mu_{1}n\alpha/2)^{K}V_{\lambda}(\mathbf{z}_{0})+2n^{2}\alpha^{2}l^{2}\sigma^{2}(2+3\eta^{3})/\mu_{1}.$

Setting $\alpha=\min\\{1/5\eta
nl,4\log(V_{\lambda}(\mathbf{z}_{0})K)/\mu_{1}nK\\}$ results in the following
last iterate convergence guarantee which holds for any $K\geq 1$:

$\displaystyle\max_{\tau_{1},\pi_{1},\ldots,\tau_{K},\pi_{K}\in\mathbb{S}_{n}}V_{\lambda}(\mathbf{z}^{K+1}_{0})$
$\displaystyle\leq
e^{\nicefrac{{-K}}{{365\kappa^{3}}}}V_{\lambda}(\mathbf{z}_{0})+\frac{\mu_{1}+\hat{c}\kappa^{8}\sigma^{2}\log^{2}(V_{\lambda}(\mathbf{z}_{0})K)}{\mu_{1}K^{2}}$
$\displaystyle=\tilde{O}(e^{\nicefrac{{-K}}{{365\kappa^{3}}}}+\nicefrac{{1}}{{K^{2}}}),$

where $\kappa=\max\\{\nicefrac{{l}}{{\mu_{1}}},\nicefrac{{l}}{{\mu_{2}}}\\}$
and $\hat{c}>0$ is a numerical constant that is independent of
$l,\mu_{1},\mu_{2}$ and $\sigma^{2}$.

###### Proof.

Step 1: Epoch level update rule We highlight that the derivation of the epoch
level update rule in Step 1 of Theorem E.1 applies to any permutations
$\tau_{k},\pi_{k}\in\mathbb{S}_{n}$. Thus, repeating the same arguments gives
us the following epoch level update rule for AGDA-AS:

$\mathbf{x}^{k+1}_{0}=\mathbf{x}^{k}_{0}-n\alpha\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})+\alpha^{2}\mathbf{r}_{k},$
(E.31)
$\mathbf{y}^{k+1}_{0}=\mathbf{y}^{k}_{0}+n\beta\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})+\beta^{2}\mathbf{s}_{k},$
(E.32)

where $\mathbf{r}_{k}$ and $\mathbf{s}_{k}$ are defined as follows:

$\mathbf{r}_{k}=\sum_{i=1}^{n-1}\left[\widetilde{\prod}_{t=i+2}^{n}(\mathbf{I}-\alpha\mathbf{H}_{\tau_{k}(t)})\right]\mathbf{H}_{\tau_{k}(i+1)}\sum_{j=1}^{i}\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0}),$
(E.33)
$\mathbf{s}_{k}=\sum_{i=1}^{n-1}\left[\widetilde{\prod}_{t=i+2}^{n}(\mathbf{I}+\beta\mathbf{J}_{\pi_{k}(t)})\right]\mathbf{J}_{\pi_{k}(i+1)}\sum_{j=1}^{i}\nabla_{\mathbf{y}}f_{\pi_{k}(j)}(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0}).$
(E.34)

As before, $\mathbf{H}_{\tau_{k}(i)}$ and $\mathbf{J}_{\pi_{k}(i)}$ are
defined as,

$\displaystyle\mathbf{H}_{\tau_{k}(i)}$
$\displaystyle=\int_{0}^{1}\nabla^{2}_{\mathbf{x}\mathbf{x}}f_{\tau_{k}(i)}(\mathbf{x}^{k}_{0}+t(\mathbf{x}^{k}_{i-1}-\mathbf{x}^{k}_{0}),\mathbf{y}^{k}_{0})\textrm{d}t,$
$\displaystyle\mathbf{J}_{\pi_{k}(i)}$
$\displaystyle=\int_{0}^{1}\nabla^{2}_{\mathbf{y}\mathbf{y}}f_{\pi_{k}(i)}(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0}+t(\mathbf{y}^{k}_{i-1}-\mathbf{y}^{k}_{0}))\textrm{d}t.$

Step 2: Uniform bound on the noise terms Once again, we repeat the same
computations as in Step 2 of Theorem E.1 to obtain:

$\left\lvert\mathbf{r}_{k}\right\rvert\leq
le^{1/5}\left[n^{2}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert/2+\sum_{i=1}^{n-1}i|\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-1/i\sum_{j=1}^{i}\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})|\right].$

Defining
$d_{k,i}=|\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-1/i\sum_{j=1}^{i}\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})|$
and using Young’s inequality gives us the following:

$\left\lvert\mathbf{r}_{k}\right\rvert\leq
le^{1/5}\left[n^{2}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert/2+\sum_{i=1}^{n-1}id_{k,i}\right],$
(E.35) $\left\lvert\mathbf{r}_{k}\right\rvert^{2}\leq
2l^{2}e^{2/5}\left[n^{4}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}/4+(n-1)\sum_{i=1}^{n-1}i^{2}d^{2}_{k,i}\right].$
(E.36)

We proceed by using the bounded gradient variance assumption as follows:

$\displaystyle(n-1)\sum_{i=1}^{n-1}i^{2}d^{2}_{k,i}$
$\displaystyle=(n-1)\sum_{i=1}^{n-1}|\sum_{j=1}^{i}\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})|^{2}$
$\displaystyle\leq(n-1)\sum_{i=1}^{n-1}i\sum_{j=1}^{i}|\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})|^{2}$
$\displaystyle\leq(n-1)\sum_{i=1}^{n-1}i\sum_{j=1}^{n}|\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})|^{2}$
$\displaystyle\leq(n-1)\sum_{i=1}^{n-1}i\sum_{j=1}^{n}|\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla_{\mathbf{x}}f_{\tau_{k}(j)}(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})|^{2}$
$\displaystyle\leq(n-1)(n\sigma^{2})\sum_{i=1}^{n-1}i\leq n^{4}\sigma^{2}/2.$

Substituting the above into (E.36) gives us the following:

$\left\lvert\mathbf{r}_{k}\right\rvert^{2}\leq\frac{3n^{4}l^{2}}{4}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}+\frac{3\sigma^{2}l^{2}n^{4}}{2}.$
(E.37)

Furthermore, by Young’s inequality, we obtain,

$\displaystyle\sum_{i=1}^{n-1}id_{k,i}\leq[(n-1)\sum_{i=1}^{n-1}i^{2}d^{2}_{k,i}]^{1/2}\leq
n^{2}\sigma/\sqrt{2}.$

By substituting the above into (E.35), we obtain the following:

$\left\lvert\mathbf{r}_{k}\right\rvert\leq\frac{2n^{2}l}{3}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert+\sigma
ln^{2}.$ (E.38)

Performing similar computations for $\mathbf{s}_{k}$ gives us the following
bounds:

$\left\lvert\mathbf{s}_{k}\right\rvert\leq\frac{2n^{2}l}{3}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert+\sigma
ln^{2},$ (E.39)
$\left\lvert\mathbf{s}_{k}\right\rvert^{2}\leq\frac{3n^{4}l^{2}}{4}\left\lvert\nabla_{\mathbf{y}}F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}+\frac{3\sigma^{2}l^{2}n^{4}}{2}.$
(E.40)

We highlight that the bounds (E.11), (E.12) (E.13) and (E.14) hold uniformly
for any permutations $\tau_{k},\pi_{k}\in\mathbb{S}_{n}$.

Step 3: Obtaining a convergence guarantee As before, we define
$a_{k}=\Phi(\mathbf{x}^{k}_{0})-\Phi^{*}$ and
$b_{k}=\Phi(\mathbf{x}^{k}_{0})-F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})$
which implies that $V_{\lambda}(\mathbf{z}^{k}_{0})=a_{k}+\lambda b_{k}$.

We follow the same procedure as Step 3 of Theorem E.1 and substitute the
uniform bounds (E.11), (E.12) (E.13) and (E.14) wherever appropriate to obtain
the following inequalities:

$\displaystyle\Phi(\mathbf{x}^{k+1}_{0})-\Phi(\mathbf{x}^{k}_{0})$
$\displaystyle\leq
n\alpha\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}-\frac{n\alpha}{2}\left\lvert\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}$
$\displaystyle+\frac{3n^{3}\alpha^{3}l^{2}}{4}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}_{0}^{k},\mathbf{y}_{0}^{k})\right\rvert^{2}+\frac{3n^{3}\alpha^{3}l^{2}\sigma^{2}}{2},$
(E.41)
$F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})\leq(\frac{3n\alpha}{2}+\frac{13}{10}ln^{2}\alpha^{2}+\frac{3n^{4}\alpha^{4}l^{3}}{8})\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}_{0}^{k},\mathbf{y}_{0}^{k})\right\rvert^{2}+\frac{9\alpha^{3}n^{3}l^{2}\sigma^{2}}{10},$
(E.42)
$\Phi(\mathbf{x}^{k+1}_{0})-F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k+1}_{0})\leq(1-n\beta\mu_{2})[\Phi(\mathbf{x}^{k+1}_{0})-F(\mathbf{x}^{k+1}_{0},\mathbf{y}^{k}_{0})]+\frac{23n^{2}\beta^{3}l^{2}\sigma^{2}}{10}.$
(E.43)

Once again, following the same steps as Step 3 of Theorem E.1, we conclude
that,

$\displaystyle a_{k+1}$ $\displaystyle\leq
a_{k}+n\alpha\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}-\frac{n\alpha}{2}\left\lvert\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}$
$\displaystyle+\frac{3n\alpha}{100}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}_{0}^{k},\mathbf{y}_{0}^{k})\right\rvert^{2}+\frac{3n^{3}\alpha^{3}l^{2}\sigma^{2}}{2}.$
(E.44)
$b_{k+1}\leq(1-n\beta\mu_{2})b_{k}+(1-n\beta\mu_{2})n\alpha\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})-\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}-(1-n\beta\mu_{2})\frac{n\alpha}{2}\left\lvert\nabla\Phi(\mathbf{x}^{k}_{0})\right\rvert^{2}\\\
+(1-n\beta\mu_{2})\frac{9n\alpha}{5}\left\lvert\nabla_{\mathbf{x}}F(\mathbf{x}^{k}_{0},\mathbf{y}^{k}_{0})\right\rvert^{2}+(1-n\beta\mu_{2})\frac{12n^{3}\alpha^{3}l^{2}\sigma^{2}}{5}+\frac{23n^{3}\beta^{3}l^{2}\sigma^{2}}{10}.$
(E.45)

By setting $\lambda=\frac{1}{10}$ and $\eta=\frac{73l^{2}}{2\mu_{2}^{2}}$ and
following the same steps as in Step 3 of Theorem E.1, we obtain the following
update equation for $V_{\lambda}(\mathbf{z}^{k+1}_{0})$:

$\displaystyle
V_{\lambda}(\mathbf{z}^{k+1}_{0})\leq(1-\mu_{1}n\alpha/2)V_{\lambda}(\mathbf{z}^{k+1}_{0})+n^{3}\alpha^{3}l^{2}\sigma^{2}(2+3\eta^{3}).$

By unrolling the above inequality for $K$ steps we obtain the following:

$V_{\lambda}(\mathbf{z}^{K+1}_{0})\leq(1-\mu_{1}n\alpha/2)^{K}V_{\lambda}(\mathbf{z}_{0})+2n^{2}\alpha^{2}l^{2}\sigma^{2}(2+3\eta^{3})/\mu_{1}.$

Since the above holds for any sequence of permutations
$\tau_{1},\pi_{1},\ldots\tau_{K},\pi_{K}\in\mathbb{S}_{n}$, we conclude that:

$\max_{\tau_{1},\pi_{1},\ldots,\tau_{K},\pi_{K}\in\mathbb{S}_{n}}V_{\lambda}(\mathbf{z}^{K+1}_{0})\leq(1-\mu_{1}n\alpha/2)^{K}V_{\lambda}(\mathbf{z}_{0})+2n^{2}\alpha^{2}l^{2}\sigma^{2}(2+3\eta^{3})/\mu_{1}.$
(E.46)

Setting $\alpha=\min\\{1/5\eta
nl,4\log(V_{\lambda}(\mathbf{z}_{0})K)/\mu_{1}nK\\}$ and using $\eta\leq
37\kappa^{2}$, we observe that:

$\displaystyle n^{2}\alpha^{2}l^{2}\sigma^{2}(2+3\eta^{3})/\mu_{1}$
$\displaystyle\leq\frac{16l^{2}\sigma^{2}(2+3\eta^{3})}{\mu_{1}^{3}}\frac{\log^{2}(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)}{K^{2}}$
$\displaystyle\leq\frac{\hat{c}\kappa^{8}\sigma^{2}\log^{2}(V_{\lambda}(\mathbf{z}_{0})K)}{\mu_{1}K^{2}},$

where $\hat{c}>0$ is a numerical constant that is independent of $\kappa,\mu$
and $\sigma^{2}$. By substituting the above into (E.46), we get:

$\max_{\tau_{1},\pi_{1},\ldots,\tau_{K},\pi_{K}\in\mathbb{S}_{n}}V_{\lambda}(\mathbf{z}^{K+1}_{0})\leq(1-\mu_{1}n\alpha/2)^{K}V_{\lambda}(\mathbf{z}_{0})+\frac{\hat{c}\kappa^{8}\sigma^{2}\log^{2}(V_{\lambda}(\mathbf{z}_{0})K)}{\mu_{1}K^{2}}.$
(E.47)

Case 1: $1/5\eta nl\leq 4\log(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)/\mu_{1}nK$

In this case, $\alpha=1/5\eta nl$ and hence, we get:

$\displaystyle(1-n\alpha\mu_{1}/2)^{K}V_{\lambda}(\mathbf{z}_{0})\leq
e^{-n\alpha\mu_{1}K/2}V_{\lambda}(\mathbf{z}_{0})\leq
e^{-\frac{K}{365\kappa^{3}}}V_{\lambda}(\mathbf{z}_{0}).$

By substituting into (E.47), we get:

$\max_{\tau_{1},\pi_{1},\ldots,\tau_{K},\pi_{K}\in\mathbb{S}_{n}}V_{\lambda}(\mathbf{z}^{K+1}_{0})\leq
e^{-\frac{K}{365\kappa^{3}}}V_{\lambda}(\mathbf{z}_{0})+\frac{\hat{c}\kappa^{8}\sigma^{2}\log^{2}(V_{\lambda}(\mathbf{z}_{0})K)}{\mu_{1}K^{2}}.$
(E.48)

Case 2: $1/5\eta nl\leq
4\log(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)/(\mu_{1}nK)$

In this case, $\alpha=4\log(V_{\lambda}(\mathbf{z}_{0})n^{1/2}K)/\mu_{1}nK$
and we conclude that,

$\displaystyle(1-n\alpha\mu_{1}/2)^{K}V_{\lambda}(\mathbf{z}_{0})$
$\displaystyle\leq e^{-n\alpha\mu_{1}K/2}V_{\lambda}(\mathbf{z}_{0})\leq
e^{-2\log(V_{\lambda}(\mathbf{z}_{0})^{1/2}n^{1/2}K)}V_{\lambda}(\mathbf{z}_{0})\leq\frac{1}{nK^{2}}.$

By substituting into (E.47), we get:

$\max_{\tau_{1},\pi_{1},\ldots,\tau_{K},\pi_{K}\in\mathbb{S}_{n}}V_{\lambda}(\mathbf{z}^{K+1}_{0})\leq\frac{\mu_{1}+\hat{c}\kappa^{8}\sigma^{2}\log^{2}(V_{\lambda}(\mathbf{z}_{0})K)}{\mu_{1}K^{2}}.$
(E.49)

Taking the maximum of the right hand side of (E.48) and (E.49), we obtain the
following rate, which holds for any $K\geq 1$:

$\displaystyle\max_{\tau_{1},\pi_{1},\ldots,\tau_{K},\pi_{K}\in\mathbb{S}_{n}}V_{\lambda}(\mathbf{z}^{K+1}_{0})\leq
e^{-\frac{K}{365\kappa^{3}}}V_{\lambda}(\mathbf{z}_{0})+\frac{\mu_{1}+\hat{c}\kappa^{8}\sigma^{2}\log^{2}(V_{\lambda}(\mathbf{z}_{0})K)}{\mu_{1}K^{2}}.$

Suppressing constant terms and logarithmic factors, we get,

$\displaystyle\mathbb{E}[V_{\lambda}(\mathbf{z}^{K+1}_{0})]=\tilde{O}(e^{-\frac{K}{365\kappa^{3}}}+\nicefrac{{1}}{{K^{2}}}).$

∎

###  E.4 Convergence of AGDA-RR and AGDA-AS to a Saddle Point

In this section, we demonstrate that our convergence guarantees for AGDA-RR
and AGDA-AS can be expressed in terms of squared distance to the set of saddle
points of $F$, denoted as $\mathcal{Z}^{*}$. We do so by upper bounding
$\textrm{dist}(\mathbf{z},\mathcal{Z}^{*})^{2}$ in terms of
$V_{\lambda}(\mathbf{z})$. We begin by establishing some basic properties of
$\mathcal{Z}^{*}$ as follows.

######  Lemma E.5 (Set of Saddle Points of 2PŁ functions).

Let
$F:\mathbb{R}^{d_{\mathbf{x}}}\times\mathbb{R}^{d_{\mathbf{y}}}\rightarrow\mathbb{R}$
be an $l$-smooth function satisfying Assumption 3 (with constants $\mu_{1}$
and $\mu_{2}$) and let $\mathcal{Z}^{*}$ denote the set of saddle points of
$F$. Then $\mathcal{Z}^{*}$ is a closed set and
$\textrm{dist}(\mathbf{z},\mathcal{Z}^{*})=\min_{\mathbf{z}^{*}\in\mathcal{Z}^{*}}\left\lvert\mathbf{z}-\mathbf{z}^{*}\right\rvert$
is a well defined continuous function of $\mathbf{z}$. Furthermore, for any
$\mathbf{x}\in\mathbb{R}^{d_{\mathbf{x}}}$, the set
$\mathcal{Y}^{*}(\mathbf{x})=\arg\max_{\hat{\mathbf{y}}\in\mathbb{R}^{d_{\mathbf{y}}}}F(\mathbf{x},\hat{\mathbf{y}})$
is a closed set.

###### Proof.

By the $l$-smoothness of $F$, $\nabla_{\mathbf{x}}F(\mathbf{x},\mathbf{y})$
and $\nabla_{\mathbf{y}}F(\mathbf{x},\mathbf{y})$ are Lipschitz continuous
functions, which implies that
$\eta(\mathbf{z})=[\nabla_{\mathbf{x}}F(\mathbf{z}),\nabla_{\mathbf{y}}F(\mathbf{z})]$
is a continuous map. Furthermore, by Lemma E.1, the set of saddle points of
$F$ are exactly the set of stationary points of $F$, which means,

$\displaystyle\mathcal{Z}^{*}=\\{\mathbf{z}\in\mathbb{R}^{d}\ |\
\nabla_{\mathbf{x}}F(\mathbf{z})=0,\nabla_{\mathbf{y}}F(\mathbf{z})=0\\}=\eta^{-1}(\\{0\\}).$

Hence, $\mathcal{Z}^{*}$ is a closed set as it is the inverse image of the
closed set $\\{0\\}$ under a continuous map. Consequently,
$\textrm{dist}(\mathbf{z},\mathcal{Z}^{*})=\min_{\mathbf{z}^{*}\in\mathcal{Z}^{*}}\left\lvert\mathbf{z}-\mathbf{z}^{*}\right\rvert$
is a well defined continuous function of $\mathbf{z}$.

Consider any $\mathbf{x}\in\mathbb{R}^{d_{\mathbf{x}}}$. Since $F$ is a 2PŁ
function, $-F(\mathbf{x},.)$ satisfies the (one-sided) PŁ inequality. Thus,
$\mathbf{y}\in\mathcal{Y}^{*}(\mathbf{x})$ if and only if
$\nabla_{\mathbf{y}}F(\mathbf{x},\mathbf{y})=0$, i.e.,
$\mathcal{Y}^{*}(\mathbf{x})=\\{\mathbf{y}\in\mathbb{R}^{d_{\mathbf{y}}}\ |\
\nabla_{\mathbf{y}}F(\mathbf{x},\mathbf{y})=0\\}$. By the continuity of
$\nabla_{\mathbf{y}}F(\mathbf{x},.)$, we conclude that
$\mathcal{Y}^{*}(\mathbf{x})$ is a closed set. ∎

The following lemma, which is key to establishing the relation between
$V_{\lambda}(\mathbf{z})$ and $\textrm{dist}(\mathbf{z},\mathcal{Z}^{*})$, is
an adaptation of Lemma A.3 of Nouiehed et al. [40] for 2PŁ functions.

######  Lemma E.6 (Lipschitzness of $\mathcal{Y}^{*}(\mathbf{x})$).

Let
$F:\mathbb{R}^{d_{\mathbf{x}}}\times\mathbb{R}^{d_{\mathbf{y}}}\rightarrow\mathbb{R}$
be an $l$-smooth function satisfying Assumption 3 (with constants $\mu_{1}$
and $\mu_{2}$). For any $\mathbf{x}\in\mathbb{R}^{d_{\mathbf{x}}}$, let
$\mathcal{Y}^{*}(\mathbf{x})=\arg\max_{\mathbf{y}\in\mathbb{R}^{d_{\mathbf{y}}}}F(\mathbf{x},\mathbf{y})$.
Then, for any $\mathbf{x}_{1},\mathbf{x}_{2}\in\mathbb{R}^{d_{\mathbf{x}}}$
and $\mathbf{y}^{*}(\mathbf{x}_{1})\in\mathcal{Y}^{*}(\mathbf{x}_{1})$, there
exists a $\mathbf{y}^{*}(\mathbf{x}_{2})\in\mathcal{Y}^{*}(\mathbf{x}_{2})$
such that,

$\displaystyle\left\lvert\mathbf{y}^{*}(\mathbf{x}_{1})-\mathbf{y}^{*}(\mathbf{x}_{2})\right\rvert\leq\frac{l}{2\mu_{2}}\left\lvert\mathbf{x}_{1}-\mathbf{x}_{2}\right\rvert.$

###### Proof.

Consider any $\mathbf{x}_{1},\mathbf{x}_{2}\in\mathbb{R}^{d_{\mathbf{x}}}$ and
$\mathbf{y}^{*}(\mathbf{x}_{1})\in\mathcal{Y}^{*}(\mathbf{x}_{1})$. Since $F$
is 2PŁ with constants $\mu_{1}$ and $\mu_{2}$, $-F(\mathbf{x},.)$ satisfies
the PŁ inequality for any $\mathbf{x}\in\mathbb{R}^{d_{\mathbf{x}}}$ with
constant $\mu_{2}$. Furthermore, by Lemma E.5, $\mathcal{Y}^{*}(\mathbf{x})$
is a closed set for any $\mathbf{x}\in\mathbb{R}^{d_{\mathbf{x}}}$. Thus, by
Lemma A.3 of Nouiehed et al. [40], there exists a
$\mathbf{y}^{*}(\mathbf{x}_{2})\in\mathcal{Y}^{*}(\mathbf{x}_{2})$ satisfying
$\left\lvert\mathbf{y}^{*}(\mathbf{x}_{1})-\mathbf{y}^{*}(\mathbf{x}_{2})\right\rvert\leq\frac{l}{2\mu_{2}}\left\lvert\mathbf{x}_{1}-\mathbf{x}_{2}\right\rvert$.
∎

Equipped with the above lemmas, we can finally upper bound
$\textrm{dist}(\mathbf{z},\mathcal{Z}^{*})$ in terms of
$V_{\lambda}(\mathbf{z})$.

######  Lemma E.7.

Let
$F:\mathbb{R}^{d_{\mathbf{x}}}\times\mathbb{R}^{d_{\mathbf{y}}}\rightarrow\mathbb{R}$
be an $l$-smooth function satisfying Assumption 3 (with constants $\mu_{1}$
and $\mu_{2}$). Define
$\Phi(\mathbf{x})=\max_{\mathbf{y}\in\mathbb{R}^{d_{\mathbf{y}}}}F(\mathbf{x},\mathbf{y})$,
$\Phi^{*}=\min_{\mathbf{x}\in\mathbb{R}^{d_{\mathbf{x}}}}\Phi(\mathbf{x})$,
$\mathcal{X}^{*}=\arg\min_{\mathbf{x}\in\mathbb{R}^{d_{\mathbf{x}}}}\Phi(\mathbf{x})$
and
$\mathcal{Y}^{*}(\mathbf{x})=\arg\max_{\mathbf{y}\in\mathbb{R}^{d_{\mathbf{y}}}}F(\mathbf{x},\mathbf{y})$.
Moreover, for any $\lambda>0$, define
$V_{\lambda}(\mathbf{x},\mathbf{y})=[(\Phi(\mathbf{x})-\Phi^{*})+\lambda(\Phi(\mathbf{x})-F(\mathbf{x},\mathbf{y})]$.
Then the following holds for any $\mathbf{z}\in\mathbb{R}^{d}$:

$\displaystyle\textrm{dist}(\mathbf{z},\mathcal{Z}^{*})^{2}\leq\max\left\\{\frac{2}{\mu_{1}}(\frac{l^{2}}{2\mu^{2}_{2}}+1),\frac{4}{\lambda\mu_{2}}\right\\}V_{\lambda}(\mathbf{z}).$

###### Proof.

Since the set of saddle points of $F$ is non-empty and $\Phi$ is a PŁ function
(with constant $\mu_{1}$) as per Lemma E.2, we can use the same arguments as
Lemma E.5 to show that $\mathcal{X}^{*}$ is a closed set.

Consider any $\mathbf{z}=(\mathbf{x},\mathbf{y})$. Let $\mathbf{x}^{*}$ be the
projection of $\mathbf{x}$ on the closed set $\mathcal{X}^{*}$ and let
$\mathbf{y}^{*}(\mathbf{x})$ be the projection of $\mathbf{y}$ on the closed
set (as per Lemma E.5) $\mathcal{Y}^{*}(\mathbf{x})$.

Applying Lemma E.3 to $\Phi(\mathbf{x})$, we obtain,

$\Phi(\mathbf{x})-\Phi^{*}\geq\frac{\mu_{1}}{2}\left\lvert\mathbf{x}-\mathbf{x}^{*}\right\rvert^{2}.$
(E.50)

Similarly, applying Lemma E.3 to $-F(\mathbf{x},\mathbf{y})$, we obtain,

$\Phi(\mathbf{x})-F(\mathbf{x},\mathbf{y})\geq\frac{\mu_{2}}{2}\left\lvert\mathbf{y}-\mathbf{y}^{*}(\mathbf{x})\right\rvert^{2}.$
(E.51)

By Lemma E.6, there exists a
$\mathbf{y}^{*}\in\mathcal{Y}^{*}(\mathbf{x}^{*})$ satisfying,

$\left\lvert\mathbf{y}^{*}(\mathbf{x})-\mathbf{y}^{*}\right\rvert\leq\frac{l}{2\mu_{2}}\left\lvert\mathbf{x}-\mathbf{x}^{*}\right\rvert.$
(E.52)

Let $\mathbf{z}^{*}=(\mathbf{x}^{*},\mathbf{y}^{*})$. We note that since
$\mathbf{x}^{*}\in\mathcal{X}^{*}$ and
$\mathbf{y}^{*}\in\mathcal{Y}^{*}(\mathbf{x}^{*})$, $\mathbf{z}^{*}$ is a
global minimax point of $F$. Thus by Lemma E.1, $\mathbf{z}^{*}$ is a saddle
point of $F$, i.e., $\mathbf{z}^{*}\in\mathcal{Z}^{*}$. We now proceed as
follows:

$\displaystyle\left\lvert\mathbf{y}-\mathbf{y}^{*}\right\rvert$
$\displaystyle\leq\left\lvert\mathbf{y}-\mathbf{y}^{*}(\mathbf{x})\right\rvert+\left\lvert\mathbf{y}^{*}(\mathbf{x})-\mathbf{y}^{*}\right\rvert$
$\displaystyle\leq\left\lvert\mathbf{y}-\mathbf{y}^{*}(\mathbf{x})\right\rvert+\frac{l}{2\mu_{2}}\left\lvert\mathbf{x}-\mathbf{x}^{*}\right\rvert.$

Applying Young’s Inequality, we obtain,

$\left\lvert\mathbf{y}-\mathbf{y}^{*}\right\rvert^{2}\leq
2\left\lvert\mathbf{y}-\mathbf{y}^{*}(\mathbf{x})\right\rvert^{2}+\frac{l^{2}}{2\mu^{2}_{2}}\left\lvert\mathbf{x}-\mathbf{x}^{*}\right\rvert^{2},$
(E.53)

which implies that.

$\displaystyle\left\lvert\mathbf{z}-\mathbf{z}^{*}\right\rvert^{2}$
$\displaystyle=\left\lvert\mathbf{x}-\mathbf{x}^{*}\right\rvert^{2}+\left\lvert\mathbf{y}-\mathbf{y}^{*}\right\rvert^{2}$
$\displaystyle\leq
2\left\lvert\mathbf{y}-\mathbf{y}^{*}(\mathbf{x})\right\rvert^{2}+(\frac{l^{2}}{2\mu^{2}_{2}}+1)\left\lvert\mathbf{x}-\mathbf{x}^{*}\right\rvert^{2}.$

Substituting (E.50) and (E.51) in the above inequality, we obtain,

$\displaystyle\left\lvert\mathbf{z}-\mathbf{z}^{*}\right\rvert^{2}$
$\displaystyle\leq\frac{4}{\mu_{2}}[\Phi(\mathbf{x})-F(\mathbf{x},\mathbf{y})]+\frac{2}{\mu_{1}}(\frac{l^{2}}{2\mu^{2}_{2}}+1)[\Phi(\mathbf{x})-\Phi^{*}]$
$\displaystyle\leq\max\left\\{\frac{2}{\mu_{1}}(\frac{l^{2}}{2\mu^{2}_{2}}+1),\frac{4}{\lambda\mu_{2}}\right\\}[(\Phi(\mathbf{x})-\Phi^{*})+\lambda(\Phi(\mathbf{x})-F(\mathbf{x},\mathbf{y}))]$
$\displaystyle\leq\max\left\\{\frac{2}{\mu_{1}}(\frac{l^{2}}{2\mu^{2}_{2}}+1),\frac{4}{\lambda\mu_{2}}\right\\}V_{\lambda}(\mathbf{z}).$

Since $\mathbf{z}^{*}\in\mathcal{Z}^{*}$, we conclude that,

$\textrm{dist}(\mathbf{z},\mathcal{Z}^{*})^{2}\leq\max\left\\{\frac{2}{\mu_{1}}(\frac{l^{2}}{2\mu^{2}_{2}}+1),\frac{4}{\lambda\mu_{2}}\right\\}V_{\lambda}(\mathbf{z}).$
(E.54)

∎

Using Lemma E.7 and E.1, we can conclude that AGDA-RR converges in terms of
$\textrm{dist}(\mathbf{z},\mathcal{Z}^{*})^{2}$ as
$\mathbb{E}[\textrm{dist}(\mathbf{z}^{K+1}_{0},\mathcal{Z}^{*})^{2}]=\tilde{O}(e^{-\nicefrac{{K}}{{365\kappa^{3}}}}+\nicefrac{{1}}{{nK^{2}}})$.
Since $\mathcal{Z}^{*}$ is a closed set, this implies that the final epoch
iterate $\mathbf{z}^{K+1}_{0}$ of AGDA-RR converges (in expectation) to some
saddle point of $F$, with the rate
$\tilde{O}(e^{-\nicefrac{{K}}{{365\kappa^{3}}}}+\nicefrac{{1}}{{nK^{2}}})$.
Similarly, using Using Lemma E.7 and E.2, we conclude that the final epoch
iterate $\mathbf{z}^{K+1}_{0}$ of AGDA-AS converges to some saddle point of
$F$ with the rate
$\textrm{dist}(\mathbf{z}^{K+1}_{0},\mathcal{Z}^{*})^{2}=\tilde{O}(e^{-\nicefrac{{K}}{{365\kappa^{3}}}}+\nicefrac{{1}}{{K^{2}}})$.

##  Appendix F Literature Review

While the convergence properties of SGD (and SGDA) with uniform sampling have
been well studied for a long time, with matching upper and lower bounds of
$\Theta(\nicefrac{{1}}{{nK}})$ for both strongly convex minimization and
strongly convex-strongly concave minimax optimization [44, 13] ($n$ is the
number of components in the finite-sum objective and $K$ is the number of
epochs), advances in the theoretical understanding of without-replacement
sampling for SGD are a fairly recent phenomenon. This is generally attributed
to the unavailability of provably unbiased gradient estimates, leading to a
significantly more complicated analysis that often requires sophisticated
mathematical tools.

Initial progress was made by the pioneering work of Recht and Re [45] who
proposed the _noncommutative AM-GM conjecture_ , and proved that this
conjecture implies the faster convergence of without-replacement SGD.
Unfortunately, the conjecture was recently disproved by Lai and Lim [27].
Subsequent progress was made in Gürbüzbalaban et al. [21], where the authors
establish an asymptotic $O(\nicefrac{{1}}{{K^{2}}})$ convergence rate for GD
with Random Reshuffling (or RR) on functions of the form
$F(x)=1/n\sum_{i=1}^{n}f_{i}(x)$ where $F$ is a strongly convex quadratic and
the components $f_{i}$ satisfy a Hessian Lipschitz assumption. For the same
function class, Gürbüzbalaban et al. [22] established asymptotic
$O(\nicefrac{{1}}{{K^{2}}})$ rates for Gradient Descent with Shuffle Once (SO)
and Incremental Gradient (IG). The analysis in both these works relied on the
following intuition, also proposed earlier in Nedic and Bertsekas [37]: _since
sampling without replacement ensures that each component function is used
exactly once within an epoch, the overall progress made by RR (and IG) over a
complete epoch closely tracks that of full batch GD_. To this end, the key
technique in both these works was to interpret the time evolution of the epoch
iterates $\mathbf{x}^{k}_{0}$ as full batch GD with added noise, and to
subsequently obtain a convergence rate by determining the (asymptotic) rate of
decay for the noise using Chung’s Lemma. This approach still remains a highly
useful strategy for understanding SGD without replacement, and has served as a
key insight for several future works such as Haochen and Sra [23], Ahn et al.
[1]. In fact, formally extending this insight to minimax optimization (and
more generally, to variational inequalities) in a manner that can
simultaneously handle RR, SO and adversarial shuffling, is a cornerstone of
our analysis.

The first nonasymptotic guarantees for RR, which also characterize the
dependence of the convergence rate on $n$, were given by Haochen and Sra [23],
who establish a convergence rate of
$\tilde{O}(\nicefrac{{1}}{{n^{2}K^{2}}}+\nicefrac{{1}}{{K^{3}}})$ assuming
$K\geq C\kappa\log(nK)$ for some $C>0$, for the case when $F$ is a strongly
convex quadratic and the components $f_{i}$ are convex quadratics. Under the
assumption that $F$ satisfies the Polyak-Łojasiewicz inequality and the
components $f_{i}$ are smooth and Hessian Lipschitz, Haochen and Sra [23] also
establish an $\tilde{O}(\nicefrac{{1}}{{n^{2}K^{2}}}+\nicefrac{{1}}{{K^{3}}})$
rate assuming $K\geq C\kappa^{2}\log(nK)$. These rates imply the provable
superiority of RR when $K\geq\Omega(\sqrt{n})$. Subsequent advances were made
by Nagaraj et al. [36], who used sophisticated Wasserstein coupling arguments
to establish a rate of $O(\nicefrac{{1}}{{nK^{2}}})$ for RR which holds under
the epoch requirement of $K\geq C\kappa^{2}\log(nK)$, assuming $F$ is strongly
convex and $f_{i}$ are smooth and Lipschitz. This rate demonstrates the
provable improvement of RR over uniform sampling as soon as the epoch
requirement is satisfied.

Development of lower bounds for SGD without replacement began with Safran and
Shamir [48] where the authors establish a lower bound of
$\Omega(\nicefrac{{1}}{{n^{2}K^{2}}}+\nicefrac{{1}}{{nK^{3}}})$ for RR on
strongly convex quadratic $F$ with $f_{i}$ being convex quadratics, assuming
constant step-sizes. Under the same assumptions, Safran and Shamir [48] also
establish an $\Omega(\nicefrac{{1}}{{nK^{2}}})$ lower bound for SO and an
$\Omega(\nicefrac{{1}}{{K^{2}}})$ lower bound for IG. Further progress on
lower bounds and their tightness was made in Rajput et al. [43] where the
authors establish a
$\tilde{O}(\nicefrac{{1}}{{n^{2}K^{2}}}+\nicefrac{{1}}{{nK^{3}}})$ convergence
rate for RR on strongly convex quadratic $F$ with convex quadratic $f_{i}$.
Rajput et al. [43] also develop a lower bound of
$\Omega(\nicefrac{{1}}{{nK^{2}}})$ for strongly convex $F$ with smooth
$f_{i}$, thereby establishing the tightness of the upper bounds in Nagaraj et
al. [36] modulo logarithmic factors.

Recently, the theory of SGD without replacement has been significantly
advanced by the parallel works of Ahn et al. [1] and Mishchenko et al. [34].
For the case of Polyak-Łojasiewicz $F$ with smooth (but not necessarily
convex) $f_{i}$, Ahn et al. [1] show that RR converges at an optimal rate
(modulo logarithmic factors) of $\tilde{O}(\nicefrac{{1}}{{nK^{2}}})$ when
$K\geq C\kappa\log(n^{1/2}K)$. For the same problem class, Mishchenko et al.
[34] obtain an anytime-valid near-optimal rate of
$\tilde{O}(e^{\nicefrac{{-K}}{{4\kappa}}}+\nicefrac{{1}}{{nK^{2}}})$ under a
bounded gradient variance assumption. This rate matches the optimal rate
modulo logarithmic factors when $K\geq C\kappa\log(n^{1/2}K)$. Ahn et al. [1]
also analyze SO for this problem class and derive
$\tilde{O}(\nicefrac{{1}}{{nK^{2}}})$ rates assuming $K\geq
C\kappa^{2}\log(n^{1/2}K)$. The obtained rate matches the lower bound of
Safran and Shamir [48] modulo logarithmic factors. Concurrently, Mishchenko et
al. [34] present an analysis that covers both RR and SO for strongly convex
$F$ with smooth convex $f_{i}$ and obtain a rate of
$\tilde{O}(e^{\nicefrac{{-K}}{{4\kappa}}}+\nicefrac{{1}}{{nK^{2}}})$. For IG,
Nguyen et al. [39] obtain a rate of $\tilde{O}(\nicefrac{{1}}{{K^{2}}})$
assuming strongly convex $F$, smooth $f_{i}$ and an epoch requirement of
$K\geq 12\kappa^{2}\log(K)$. Moving beyond the PŁ class, the recent work of Li
et al. [28] analyze RR for the case when $f_{i}$ are smooth and $F$ satisfies
a KŁ inequality and, using variable step-sizes, establish an asymptotic
convergence rate of $O(\nicefrac{{1}}{{K^{2}}})$ when the KŁ exponent lies in
$[0,\nicefrac{{1}}{{2}}]$.

Recent works have also analyzed RR and SO in the federated minimization
setting. Notably, Yun et al. [56] developed an extension of the techniques
used in Ahn et al. [1] to analyze RR variants of minibatch and local SGD,
while Mishchenko et al. [35] extended the approach of Mishchenko et al. [34]
to develop federated analogs of RR and SO. Among other developments, Tran et
al. [53] propose a variant of SGD with momentum that is amenable to
theoretical analysis under without-replacement sampling. These developments
are also complemented by the recent negative result of Safran and Shamir [49]
which analyzes the condition number dependence of RR, and through an intricate
lower bound analysis on convex quadratics, show that RR and SO do not
significantly outperform uniform sampling unless $K$ is larger than the
condition number.

Despite the recent wave of developments on SGD without replacement,
theoretical analysis of sampling without replacement for minimax optimization
has remained relatively unexplored. To the best of our knowledge, Yu et al.
[55] and Maheshwari et al. [33] are the only prior works in this domain. Both
these works focus only on Random Reshuffling and are restricted to finite-sum
minimax problems of the form $F(x,y)=1/n\sum_{i=1}^{n}f_{i}(x,y)$ where each
$f_{i}$ is smooth, Lipschitz, convex-concave and has bounded domain. Under
this setting, Yu et al. [55] proposes a stochastic proximal point method with
RR that exhibits a rate of $\tilde{O}(\nicefrac{{1}}{{\sqrt{nK}}})$ whereas
Maheshwari et al. [33] proposes a zeroth-order optimistic gradient method with
RR that exhibits a rate of $\tilde{O}(\nicefrac{{nd^{2}}}{{K^{1/4}}})$, where
$d$ is the dimension of the domain. The analysis in both these works are based
on an application of the Wasserstein coupling technique of Nagaraj et al. [36]
(for the convex case) to smooth, Lipschitz convex-concave minimax
optimization.

##  Appendix G Experimental Details

As described in Section 5 of the main text, we perform our benchmarks on
finite-sum strongly convex-strongly concave quadratic minimax games. The
objective $F$ and the components $f_{i}$ are given by:

$\displaystyle F(\mathbf{x},\mathbf{y})$
$\displaystyle=1/n\sum_{i=1}^{n}f_{i}(\mathbf{x},\mathbf{y})=\frac{1}{2}\mathbf{x}^{T}\mathbf{A}\mathbf{x}+\mathbf{x}^{T}\mathbf{B}\mathbf{y}-\frac{1}{2}\mathbf{y}^{T}\mathbf{C}\mathbf{y},$
$\displaystyle f_{i}(\mathbf{x},\mathbf{y})$
$\displaystyle=\frac{1}{2}\mathbf{x}^{T}\mathbf{A}_{i}\mathbf{x}+\mathbf{x}^{T}\mathbf{B}_{i}\mathbf{y}-\frac{1}{2}\mathbf{y}^{T}\mathbf{C}_{i}\mathbf{y}-\mathbf{u}_{i}^{T}\mathbf{x}-\mathbf{v}_{i}^{T}\mathbf{y},$

where $\mathbf{A}$ and $\mathbf{C}$ are positive definite and $\mathbf{u}_{i}$
and $\mathbf{v}_{i}$ are chosen such that
$\sum_{i=1}^{n}\mathbf{u}_{i}=\sum_{i=1}^{n}\mathbf{v}_{i}=0$. In all our
experiments, we set $n=100$ and $\textrm{dim }\mathbf{x}=\textrm{dim
}\mathbf{y}=25$. We randomly generate the components $f_{i}$ such that 20
randomly selected components are strongly convex-strongly concave. To this
end, the components $\mathbf{A}_{i}$ are selected as follows. We begin by
sampling a random orthogonal matrix $\mathbf{O}_{A}$, and then generate two
$d$-dimensional vectors $\mathbf{m}_{A}$ and $\delta_{A}$, such that each
component of $\mathbf{m}_{A}$ is uniformly sampled from $[\mu_{A},L_{A}]$
whereas that of $\delta_{A}$ is uniformly sampled from
$[\mu_{\delta},L_{\delta}]$. Subsequently, for each $i\in[n]$, we set
$\mathbf{A}_{i}=\mathbf{O}_{A}\Lambda_{i}\mathbf{O}_{A}^{T}$ where
$\Lambda_{i}=\textrm{diag}(-\delta_{A})$ or 20 randomly selected indexes and
$\Lambda_{i}=\textrm{diag}(5\mathbf{m}_{A}/4+\delta_{A}/4)$ for the other 80
components. A similar procedure is followed for generating the matrices
$\mathbf{B}$ and $\mathbf{C}$. For the vectors $\mathbf{u}_{i}$, we generate a
vector $\delta_{u}$ with components that are uniformly sampled from
$[\mu_{\delta},L_{\delta}]$. Then, for 20 randomly sampled indexes, we set
$\mathbf{u}_{i}=-\delta_{u}$ and for the rest, we set
$\mathbf{u}_{i}=\delta_{u}/4$. The vectors $\mathbf{v}_{i}$ are sampled in a
similar fashion. We run each algorithm for $K=100$ epochs using constant step-
sizes of the form $\alpha=\nicefrac{{\gamma}}{{n}}$ where $\gamma$ is chosen
independently for each algorithm via grid search. In all our experiments, we
set $\mu_{A}=\mu_{C}=0.5$, $\mu_{B}=5.0$ and $\mu_{\delta}=50.0$. Furthermore,
we set $L_{A}=L_{C}=2\mu_{A}$, $L_{B}=2\mu_{B}$ and
$L_{\delta}=2\mu_{\delta}$. We perform our experiments on a Jupyter notebook
with a Python 3.7 kernel, executed on a 2.8 GHz Intel Core i7 processor with 8
GB of memory. The total running time is 40 minutes.