# Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave
Minimax Optimization

Luo Luo Guangzeng Xie ∗ Tong Zhang Zhihua Zhang Equal Contribution Department
of Mathematics, The Hong Kong University of Science and Technology;
<EMAIL_ADDRESS>Academy for Advanced Interdisciplinary Studies, Peking
University<EMAIL_ADDRESS>Department of Mathematics, The Hong Kong
University of Science and Technology<EMAIL_ADDRESS>of Mathematical
Sciences, Peking University<EMAIL_ADDRESS>
###### Abstract

This paper considers stochastic first-order algorithms for convex-concave
minimax problems of the form $\min_{\bf x}\max_{\bf y}f(\bf x,\bf y)$, where
$f$ can be presented by the average of $n$ individual components which are
$L$-average smooth. For $\mu_{x}$-strongly-convex-$\mu_{y}$-strongly-concave
setting, we propose a new stochastic algorithm which could find an
$\varepsilon$-saddle point of the problem in
$\tilde{\mathcal{O}}(\sqrt{n(\sqrt{n}+\kappa_{x})(\sqrt{n}+\kappa_{y})}\log(1/\varepsilon))$
stochastic first-order complexity, where $\kappa_{x}\triangleq L/\mu_{x}$ and
$\kappa_{y}\triangleq L/\mu_{y}$. This upper bound is near optimal with
respect to $\varepsilon$, $n$, $\kappa_{x}$ and $\kappa_{y}$ simultaneously.
In addition, the algorithm is easily implemented and works well in practice.
Our methods can be extended to solve more general unbalanced convex-concave
minimax problems and the corresponding upper complexity bounds are also near
optimal.

##  1 Introduction

This paper studies the following finite-sum minimax problem:

$\displaystyle\min_{{\bf{x}}\in{\mathcal{X}}}\max_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}},{\bf{y}})\triangleq\frac{1}{n}\sum_{i=1}^{n}f_{i}({\bf{x}},{\bf{y}}),$
(1)

where ${\mathcal{X}}$ and ${\mathcal{Y}}$ are convex and closed. Our goal is
to find the approximate saddle point of problem (1) to guarantee the duality
gap no larger than ${\varepsilon}$.

The formulation (1) includes a lot of machine learning applications such as
AUC maximization [14, 41, 23, 12], robust optimization [7, 39], adversarial
learning [31] and reinforcement learning [34]. We study the fundamental
setting that each component $f_{i}({\bf{x}},{\bf{y}})$ is convex in $x$ and
concave in $y$; $\\{f_{i}({\bf{x}},{\bf{y}})\\}_{i=1}^{n}$ are $L$-average
smooth; and $f({\bf{x}},{\bf{y}})$ is $\mu_{x}$-strongly-convex in $x$ and
$\mu_{y}$-strongly-concave in $y$. In particular, we focus on the unbalanced
case that the condition numbers $\kappa_{x}\triangleq L/\mu_{x}$ and
$\kappa_{y}\triangleq L/\mu_{x}$ could be quite different. Without loss of
generality, we suppose $\kappa_{x}\geq\kappa_{y}$.

Most existing algorithms [17, 11, 29, 24, 5, 26, 1] for general strongly-
convex-strongly-concave (SCSC) minimax optimization do not consider the
difference between two condition numbers $\kappa_{x}$ and $\kappa_{y}$, which
leads to their upper bound complexities depend on
$\max\\{\kappa_{x},\kappa_{y}\\}$. Lin et al. [22] first proposed proximal
point methods for the unbalanced problem with
$\tilde{\mathcal{O}}(\sqrt{\kappa_{x}\kappa_{y}}\log^{3}(1/{\varepsilon}))$
gradient calls111We use notation $\tilde{\mathcal{O}}(\cdot)$ to hide
logarithmic factors of $n$, $\kappa_{x}$ and $\kappa_{y}$ in complexities.,
nearly matching the lower bound [42, 15] of the deterministic algorithm. Wang
and Li [35], Xie et al. [38] improved Lin et al. [20]’s results under refined
smoothness assumption and bilinear setting. Unfortunately, these methods [22,
35] are based on full gradient oracle and ignore the finite-sum structure in
the objective function.

In practice, the number of components $n$ could be very large. It is natural
to use stochastic first-order oracle (SFO) algorithms to reduce the cost of
gradient based methods. The SFO algorithms and their optimality are well-
studied for minimization problems [9, 16, 6, 2, 8, 20, 43, 36], but the
related theory for minimax optimization is still imperfect. In the balanced
case of $\kappa_{x}=\kappa_{y}=\kappa$, Palaniappan and Bach [29] first
introduced SVRG/SAGA [16, 6] to solve the general formulation (1) in big data
regime and obtained $\tilde{\mathcal{O}}((n+\kappa^{2})\log(1/{\varepsilon}))$
SFO upper bound. If $\kappa>\sqrt{n}$, the leading term can be reduced to
${\mathcal{O}}(n+\kappa\sqrt{n})$ by introducing extragradient (EG) or
proximal point iterations [24, 5]. Recently, Tominin et al. [33] proposed an
accelerated stochastic method for unbalanced problem (1) when both
$\kappa_{x}$ and $\kappa_{y}$ are larger than $\sqrt{n}$. They designed a
complicated algorithm which contains three-loops iterations, obtaining
${\mathcal{O}}(\sqrt{n\kappa_{x}\kappa_{y}})$ SFO upper bound under different
smoothness assumptions222Tominin et al. [33] assume each $f_{i}$ is
$L_{i}$-smooth and $f$ is $L$-smooth, where
$L=\frac{1}{n}\sum_{i=1}^{n}L_{i}$, while this paper only requires the weaker
assumption that $\\{f\\}_{i=1}^{n}$ is $L$-average smooth as Definition 1.
Please see the detailed discussion for these two different settings in Section
3.2..

In fact, SCSC minimax problems with finite-sum structure can be classified by
three types of relationships among $\kappa_{x}$, $\kappa_{y}$ and $n$ (recall
we have assumed $\kappa_{x}\geq\kappa_{y}$) :

  1. (a)

$f({\bf{x}},{\bf{y}})$ is extremely ill-conditioned w.r.t two variables:
$\kappa_{x}=\Omega(\sqrt{n})$ and $\kappa_{y}=\Omega(\sqrt{n})$;

  2. (b)

$f({\bf{x}},{\bf{y}})$ is only extremely ill-conditioned w.r.t ${\bf{y}}$:
$\kappa_{x}={\mathcal{O}}(\sqrt{n})$ and $\kappa_{y}=\Omega(\sqrt{n})$;

  3. (c)

the number of components is extremely large:
$\kappa_{x}={\mathcal{O}}(\sqrt{n})$ and $\kappa_{y}={\mathcal{O}}(\sqrt{n})$.

Han et al. [13] provided a general SFO lower bound for all three cases as
follows

$\displaystyle\begin{cases}\displaystyle\Omega\big{(}\big{(}n+\sqrt{n\kappa_{x}\kappa_{y}}\big{)}\log(1/{\varepsilon})\big{)},&\text{for~{}}\kappa_{x}=\Omega(\sqrt{n})\text{~{}and~{}}\kappa_{y}=\Omega(\sqrt{n});\\\\[2.84544pt]
\displaystyle\Omega\big{(}\big{(}n+n^{3/4}\sqrt{\kappa_{y}}\big{)}\log(1/{\varepsilon})\big{)},&\text{for~{}}\kappa_{x}={\mathcal{O}}(\sqrt{n})\text{~{}and~{}}\kappa_{y}=\Omega(\sqrt{n});\\\\[2.84544pt]
\Omega(n),&\text{for~{}}\kappa_{x}={\mathcal{O}}(\sqrt{n})\text{~{}and~{}}\kappa_{y}={\mathcal{O}}(\sqrt{n}).\end{cases}$
(2)

We can observe that the complexity of SVRG/SAGA [29] is near optimal in the
case of (c). Tominin et al. [33]’s algorithm has the upper bound of the form
${\mathcal{O}}\left((n+\sqrt{n\kappa_{x}\kappa_{y}})\log(1/{\varepsilon}))\right)$,
but it requires the stronger assumption that each component $f_{i}$ is
$L$-smooth. We should point out that Case (b) is also an important setting,
which is useful to establish the efficient algorithms for ill-conditioned
strongly-convex-nonconcave (or nonconvex-strongly-concave) minimax
optimization [22, 21, 25].

Algorithm | SFO Complexity | Loop | Reference
---|---|---|---
Extragradient | ${\mathcal{O}}\big{(}n\kappa_{\max}\log\left(\frac{1}{{\varepsilon}}\right)\big{)}$ | 1 | Gidel et al. [11], Korpelevich [17]
SVRG/SAGA/SVRE | ${\mathcal{O}}\left(\left(n+\kappa_{\max}^{2}\right)\log\left(\frac{1}{{\varepsilon}}\right)\right)$ | 1 |  Palaniappan and Bach [29], Chavdarova et al. [5]
A-SVRG/A-SAGA | $\tilde{\mathcal{O}}\left(\left(n+\sqrt{n}\kappa_{\max}\right)\log\left(\frac{1}{{\varepsilon}}\right)\right)$ | 2 | Palaniappan and Bach [29]
L-SVRE | ${\mathcal{O}}\left(\left(n+\sqrt{n}\kappa_{\max}\right)\log\left(\frac{1}{{\varepsilon}}\right)\right)$ | 1 |  Alacaoglu and Malitsky [1] \+ Theorem 2
MINIMAX-APPA | $\tilde{\mathcal{O}}\left(n\sqrt{\kappa_{x}\kappa_{y}}\log^{3}\left(\frac{1}{{\varepsilon}}\right)\right)$ | 3 | Lin et al. [22]
PBR | $\tilde{\mathcal{O}}\left(n\sqrt{\kappa_{x}\kappa_{y}}\log\left(\frac{1}{{\varepsilon}}\right)\right)$ | 3 | Wang and Li [35]
AL-SVRE |  $\tilde{\mathcal{O}}\big{(}\sqrt{n(\sqrt{n}+\kappa_{x})(\sqrt{n}+\kappa_{y})}\log\big{(}\frac{1}{{\varepsilon}}\big{)}\big{)}$ | 2 |  Corollary 2
Lower Bound |  the expression of (2) | – | Han et al. [13]
Table 1: Comparison of SFO complexities in the $(\mu_{x},\mu_{y})$-convex-concave setting. Algorithm | SFO Complexity | Loop | Reference
---|---|---|---
DIAG | $\tilde{\mathcal{O}}\left(n\kappa_{y}\sqrt{\frac{L}{{\varepsilon}}}\log^{2}\left(\frac{1}{{\varepsilon}}\right)\right)$ | 3 | Thekumparampil et al. [32]
MINIMAX-APPA | $\tilde{\mathcal{O}}\left(n\sqrt{\frac{\kappa_{y}L}{{\varepsilon}}}\log^{3}\left(\frac{1}{{\varepsilon}}\right)\right)$ | 3 | Lin et al. [22]
A-SVRG/A-SAGA | $\tilde{\mathcal{O}}\Big{(}\Big{(}n+(\kappa_{y}^{3/2}+n^{3/4})\sqrt{\frac{L}{{\varepsilon}}}\Big{)}\log(\frac{1}{{\varepsilon}})\Big{)}$ | 2 | Yang et al. [40]
AL-SVRE | $\tilde{\mathcal{O}}\Big{(}\Big{(}n+\sqrt{\frac{nL\kappa_{y}}{{\varepsilon}}}+n^{3/4}\sqrt{\kappa_{y}}+n^{3/4}\sqrt{\frac{L}{{\varepsilon}}}\Big{)}\log(\frac{1}{{\varepsilon}}\big{)}\Big{)}$ | 2 |  Corollary 3
Lower Bound | $\Omega\Big{(}n+\sqrt{\frac{nL\kappa_{y}}{{\varepsilon}}}+n^{3/4}\sqrt{\kappa_{y}}+n^{3/4}\sqrt{\frac{L}{{\varepsilon}}}\Big{)}$ | – | Han et al. [13]
Table 2: Comparison of SFO complexities in the $(0,\mu_{y})$-convex-concave
setting, where the result of A-SVRG/A-SAGA [40] requires the assumption of
${\varepsilon}<\mu_{y}$.

In this paper, we propose a Catalyst-type algorithm that we call accelerated
loopless stochastic variance reduced extragradient (AL-SVRE), whose iteration
inexactly solves more well-conditioned minimax problems. We use loopless
stochastic variance reduced extragradient (L-SVRE) [1] as the sub-problem
solver and revise Alacaoglu and Malitsky [1]’s analysis to show L-SVRE solves
balanced SCSC minimax problem in optimal SFO complexity. Combining an
appropriate choice of parameters, AL-SVRE could find an approximate saddle
point of our main problem (1) with SFO complexity nearly matching Han et al.
[13]’s lower bound (2). Additionally, AL-SVRE only applies one times Catalyst
acceleration on AL-SVRE, which leads to the algorithm has two-loops of
iterations in total and it is easily implemented. The empirical studies on AUC
maximization [14, 41, 30] and wireless communication [10, 3, 40] problems show
that AL-SVRE performs better than baselines. In contrast, previous Catalyst-
type methods [22, 35, 33] for such an unbalanced problem need twice Catalyst
acceleration (three-loops of iterations), making these algorithms almost
impractical.

We can also apply AL-SVRE to solve more general finite-sum convex-concave
minimax problems. If we suppose $f({\bf{x}},{\bf{y}})$ is $\mu_{y}$-strongly-
concave in ${\bf{y}}$ and allow it could be non-strongly-convex in ${\bf{x}}$,
AL-SVRE could find an ${\varepsilon}$-saddle point of (1) in

$\displaystyle\tilde{\mathcal{O}}\left(\left(n+D_{x}\sqrt{\frac{nL\kappa_{y}}{{\varepsilon}}}+n^{3/4}\sqrt{\kappa_{y}}+n^{3/4}D_{x}\sqrt{\frac{L}{{\varepsilon}}}\right)\log\left(\frac{1}{{\varepsilon}}\right)\right)$
(3)

SFO complexity, where $D_{x}$ is the diameter of ${\mathcal{X}}$. The upper
bound (3) nearly matches the lower bounds with respect to ${\varepsilon}$,
$L$, $\mu_{y}$ and $n$ simultaneously, and we do not require any additional
assumption on $L$, $\mu_{y}$, $n$ and ${\varepsilon}$, while the state-of-the-
art method [40] implicitly requires that ${\varepsilon}<\mu_{y}$.

More general, if we only suppose the objective function is convex in
${\bf{x}}$ and concave in ${\bf{y}}$, the algorithm could find an
${\varepsilon}$-saddle point in

$\displaystyle\tilde{\mathcal{O}}\left(\left(n+\frac{\sqrt{n}LD_{x}D_{y}}{{\varepsilon}}+n^{3/4}(D_{x}+D_{y})\sqrt{\frac{L}{{\varepsilon}}}\right)\log\left(\frac{1}{{\varepsilon}}\right)\right)$
(4)

SFO complexity, where $D_{x}$ and $D_{y}$ are diameters of ${\mathcal{X}}$ and
${\mathcal{Y}}$ respectively. Note that the upper bound (4) nearly matches the
lower bounds [13] in such a setting. Compared with the the best known
stochastic SFO algorithm L-SVRE [1], our result additionally trades off the
difference between $D_{x}$ and $D_{y}$.

We present comparisons between our results and existing results in Table 1 for
strongly-convex-strongly-concave setting, in Table 2 for strongly-convex-
concave setting, and in Table 3 for convex-concave settings. To the best of
our knowledge, the proposed AL-SVRE is the first algorithm which attains near
optimal SFO complexities for all the above settings.

##  2 Notation and Preliminaries

In this section, we present the notation and some definitions used in this
paper.

Algorithm | SFO Complexity | Loop | Reference
---|---|---|---
Extragradient | ${\mathcal{O}}\big{(}\max\\{D_{x}^{2},D_{y}^{2}\\}\frac{nL}{{\varepsilon}}\big{)}$ | 1 | Gidel et al. [11], Korpelevich [17]
MINIMAX-APPA | $\tilde{\mathcal{O}}\big{(}\frac{nLD_{x}D_{y}}{{\varepsilon}}\log^{3}\left(\frac{1}{{\varepsilon}}\right)\big{)}$ | 3 | Lin et al. [22]
L-SVRE | ${\mathcal{O}}\big{(}\max\\{D_{x}^{2},D_{y}^{2}\\}(n+\frac{\sqrt{n}L}{{\varepsilon}})\big{)}$ | 1 | Alacaoglu and Malitsky [1]
AL-SVRE | $\tilde{\mathcal{O}}\Big{(}\Big{(}n+\frac{\sqrt{n}LD_{x}D_{y}}{{\varepsilon}}+n^{3/4}(D_{x}+D_{y})\sqrt{\frac{L}{{\varepsilon}}}\Big{)}\log\Big{(}\frac{1}{{\varepsilon}}\Big{)}\Big{)}$ | 2 |  Corollary 1
Lower Bound | $\Omega\Big{(}n+\frac{\sqrt{n}LD_{x}D_{y}}{{\varepsilon}}+n^{3/4}(D_{x}+D_{y})\sqrt{\frac{L}{{\varepsilon}}}\Big{)}$ | – | Han et al. [13]
Table 3: Comparison of SFO complexities in convex-concave setting.

######  Definition 1.

For any differentiable function $\psi\colon{\mathcal{Z}}\to{\mathbb{R}}$, we
say $\psi$ is $L$-smooth for some $L>0$ if for any
${\bf{z}},{\bf{z}}^{\prime}\in{\mathcal{Z}}$, it holds that
$\|\nabla\psi({\bf{z}})-\nabla\psi({\bf{z}}^{\prime})\|_{2}\leq
L\left\|{\bf{z}}-{\bf{z}}^{\prime}\right\|_{2}$.

######  Definition 2.

Suppose there are $n$ differentiable functions
$\\{\psi_{i}\colon{\mathcal{Z}}\to{\mathbb{R}}\\}_{i=1}^{n}$. We say
$\\{\psi_{i}\\}_{i=1}^{n}$ is $L$-average smooth for some $L>0$ if for any
${\bf{z}},{\bf{z}}^{\prime}\in{\mathcal{Z}}$, it holds that

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla\psi_{i}({\bf{z}})-\nabla\psi_{i}({\bf{z}}^{\prime})\right\|_{2}^{2}\leq
L^{2}\left\|{\bf{z}}-{\bf{z}}^{\prime}\right\|_{2}^{2}.$

######  Definition 3.

For a differentiable function
$\psi\colon{\mathcal{Z}}\rightarrow{\mathbb{R}}$, we say $\psi$ is convex if
for any ${\bf{z}},{\bf{z}}^{\prime}\in{\mathcal{Z}}$, it holds that
$\psi({\bf{z}}^{\prime})\geq\psi({\bf{z}})+\langle\nabla\psi({\bf{z}}),{\bf{z}}^{\prime}-{\bf{z}}\rangle$.
We say $\psi$ is $\mu$-strongly-convex for some $\mu>0$ if
$\psi(\cdot)-\frac{\mu}{2}\left\|\cdot\right\|_{2}^{2}$ is convex. We also say
$\psi$ is concave ($\mu$-strongly-concave) if $-\psi$ is convex
($\mu$-strongly-convex).

######  Definition 4.

For any function
$f\colon{\mathcal{X}}\times{\mathcal{Y}}\rightarrow{\mathbb{R}}$ and
$\mu_{x},\mu_{y}\geq 0$, we say $f$ is $(\mu_{x},\mu_{y})$-convex-concave if
for any ${\bf{x}}\in{\mathcal{X}}$ and ${\bf{y}}\in{\mathcal{Y}}$, it holds
that $f({\bf{x}},\cdot)$ is $\mu_{y}$-strongly-concave and $f(\cdot,{\bf{y}})$
is $\mu_{x}$-strongly-convex.

In Definition 4, we allow both $\mu_{x}$ and $\mu_{y}$ to be zero. The
notation $(0,0)$-convex-concave means the function is general convex-concave,
and $(0,\mu_{y})$-convex-concave means it is $\mu_{y}$-strongly-concave in
${\bf{y}}$ but possibly non-strongly-convex in ${\bf{x}}$. Similarly, we use
$(\mu_{x},0)$-convex-concave to present the function is $\mu_{x}$-strongly-
convex in ${\bf{x}}$ but possibly non-strongly-concave in ${\bf{y}}$.

We are interested in finding an approximate saddle point which is defined as
follows.

######  Definition 5.

For the minimax optimization problem (1),
$(\hat{\bf{x}},\hat{\bf{y}})\in{\mathcal{X}}\times{\mathcal{Y}}$ is said to be
an ${\varepsilon}$-saddle point if

$\displaystyle\max_{{\bf{y}}\in{\mathcal{Y}}}f(\hat{\bf{x}},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},\hat{\bf{y}})\leq{\varepsilon}.$

We introduce the (stochastic) gradient operator for the ease of presentation.

######  Definition 6.

For problem (1), we define the gradient operator and stochastic gradient
operator as

$\displaystyle{\bf{g}}({\bf{z}})=\begin{bmatrix}\nabla_{\bf{x}}f({\bf{z}})\\\
-\nabla_{\bf{y}}f({\bf{z}})\end{bmatrix}\quad\text{and}\quad{\bf{g}}_{i}({\bf{z}})=\begin{bmatrix}\nabla_{\bf{x}}f_{i}({\bf{z}})\\\
-\nabla_{\bf{y}}f_{i}({\bf{z}})\end{bmatrix}$

where
${\bf{z}}=({\bf{x}},{\bf{y}})\in{\mathbb{R}}^{d_{x}}\times{\mathbb{R}}^{d_{y}}$.

We also conduct the projection operator to address the constraints in the
problem.

######  Definition 7.

We define the projection of ${\bf{z}}$ onto the convex and compact set
${\mathcal{C}}$ as

$\displaystyle{\mathcal{P}}_{\mathcal{C}}({\bf{z}})=\operatorname*{arg\,min}_{{\bf{u}}\in{\mathcal{C}}}\left\|{\bf{u}}-{\bf{z}}\right\|_{2}^{2}.$

This paper focuses on solving finite-sum minimax problems by SFO algorithms
and we give the formal definition as follows.

######  Definition 8.

Consider a stochastic optimization algorithm ${\mathcal{A}}$ to solve Problem
(1). Suppose an initial point $({\bf{x}}^{(0)},{\bf{y}}^{(0)})$ is given, and
let $({\bf{x}}^{(t)},{\bf{y}}^{(t)})$ denote the point obtained by
${\mathcal{A}}$ at time-step $t$. The algorithm is said to be an SFO algorithm
if for any $t>0$, we have

$\displaystyle{\bf{x}}^{(t)}={\mathcal{P}}_{\mathcal{X}}\big{(}\tilde{\bf{x}}^{(t)}\big{)}\text{~{}~{}~{}and~{}~{}~{}}{\bf{y}}^{(t)}={\mathcal{P}}_{\mathcal{Y}}\big{(}\tilde{\bf{y}}^{(t)}\big{)},$

where

$\displaystyle\tilde{\bf{x}}^{(t)}\in$
$\displaystyle\operatorname{span}\big{\\{}{\bf{x}}^{(0)},{\bf{x}}^{(1)}\dots,{\bf{x}}^{(t-1)},\nabla_{{\bf{x}}}f_{i_{t}}\big{(}{\bf{x}}^{(0)},{\bf{y}}^{(0)}\big{)},\dots,\nabla_{{\bf{x}}}f_{i_{t}}\big{(}{\bf{x}}^{(t-1)},{\bf{y}}^{(t-1)}\big{)}\big{\\}},$
$\displaystyle\tilde{\bf{y}}^{(t)}\in$
$\displaystyle\operatorname{span}\big{\\{}{\bf{y}}^{(0)},{\bf{y}}^{(1)}\dots,{\bf{y}}^{(t-1)},\nabla_{{\bf{y}}}f_{i_{t}}\big{(}{\bf{x}}^{(0)},{\bf{y}}^{(0)}\big{)},\dots,\nabla_{{\bf{y}}}f_{i_{t}}\big{(}{\bf{x}}^{(t-1)},{\bf{y}}^{(t-1)}\big{)}\big{\\}},$

and $i_{t}$ is drawn from $\\{1,\dots,n\\}$.

##  3 Accelerating Unbalanced Convex-Concave Optimization

In this section, we first revisit loopless stochastic variance reduced
extragradient (L-SVRE) [1], and show it can be used to solve balanced
strongly-convex-strongly-concave (SCSC) minimax with optimal SFO complexity.
Then we propose a Catalyst-type scheme to accelerate L-SVRE, deriving our new
algorithm _Accelerated Loopless Stochastic Variance Reduced Extragradient_
(AL-SVRE) whose SFO upper bound is near optimal for different types of
unbalanced concave-concave minimax problems.

Algorithm 1
$\text{L-SVRE}~{}\left(\\{f_{i}({\bf{x}},{\bf{y}})\\}_{i=1}^{n},({\bf{x}}_{0},{\bf{y}}_{0}),\tau,p,T\right)$

1: Initialize: $\alpha=1-p$, ${\bf{w}}_{0}={\bf{z}}_{0}$.

2: for $k=0,1,\dots,T-1$ do

3: $\bar{{\bf{z}}}_{k}=\alpha{\bf{z}}_{k}+(1-\alpha){\bf{w}}_{k}$

4:
${\bf{z}}_{k+1/2}={\mathcal{P}}_{{\mathcal{Z}}}(\bar{{\bf{z}}}_{k}-\tau{\bf{g}}({\bf{w}}_{k}))$

5: Draw an index $i\in[n]$ uniformly at random.

6:
${\bf{z}}_{k+1}={\mathcal{P}}_{{\mathcal{Z}}}(\bar{{\bf{z}}}_{k}-\tau[{\bf{g}}({\bf{w}}_{k})+{\bf{g}}_{i}({\bf{z}}_{k+1/2})-{\bf{g}}_{i}({\bf{w}}_{k})])$

7: ${\bf{w}}_{k+1}=\begin{cases}{\bf{z}}_{k+1},~{}&\text{ with probability
}p\\\ {\bf{w}}_{k},~{}&\text{ with probability }1-p\end{cases}$

8: end for

9: Output: $({\bf{x}}_{T},{\bf{y}}_{T})$.

###  3.1 The Optimal SFO Algorithm for Balanced SCSC Minimax

We start our discussion from the optimality of balanced SCSC problems such
that the objective function $f({\bf{x}},{\bf{y}})$ is $(\mu,\mu)$-convex-
concave with some $\mu>0$. Theorem 1 gives an SFO lower bound
$\Omega((n+\sqrt{n}\kappa)\log(1/{\varepsilon}))$ for finding an approximate
saddle point with respect to the square of Euclidean distance to the optimal
solution under average smooth assumptions. This result is slightly different
from previous work which is based on duality gap convergence [13] or under
assumption that each component $f_{i}$ is $L$-smooth [37].

######  Theorem 1.

For any SFO algorithm ${\mathcal{A}}$ and $L,\mu,n,{\varepsilon}$ such that
$L/\mu>2$ and ${\varepsilon}<0.003$, there exist a dimension
$d={\mathcal{O}}(n+\sqrt{n}L/\mu\log(1/{\varepsilon}))$ and functions
$\\{f_{i}({\bf{x}},{\bf{y}})\\}_{i=1}^{n}\colon{\mathbb{R}}^{d}\times{\mathbb{R}}^{d}\to{\mathbb{R}}$
which satisfy that $\\{f_{i}\\}_{i=1}^{n}$ is $L$-average smooth, $f$ is
$(\mu,\mu)$-convex-concave. In order to find an approximate saddle point
$(\hat{\bf{x}},\hat{\bf{y}})$ such that

$\displaystyle{\mathbb{E}}\left[\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|\hat{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}\right]\leq{\varepsilon},$

algorithm ${\mathcal{A}}$ needs at least
$\Omega(n{+}\sqrt{n}L/\mu\log(1/{\varepsilon}))$ SFO calls.

Recently, Alacaoglu and Malitsky [1] proposed the L-SVRE algorithm, which
combines the idea of loopless SVRG [18] and extragradient [17]. The original
motivation of L-SVRE is to solve variational inequalities. We revise its
analysis to adapt the standard finite-sum minimax problem (1) under the
$(\mu,\mu)$-convex-concave assumption. We present the details of L-SVRE in
Algorithm 1 and show its convergence behavior in Theorem 2.

Algorithm 2 $\text{AL-
SVRE}\left(\\{f_{i}({\bf{x}},{\bf{y}})\\}_{i=1}^{n},({\bf{x}}_{0},{\bf{y}}_{0}),\beta,q,K,p,\\{\tau_{k}\\}_{k=1}^{K},\\{T_{k}\\}_{k=1}^{K}\right)$

1: Initialize: $\gamma=\frac{1-\sqrt{q}}{1+\sqrt{q}}$ and
${\bf{u}}_{0}={\bf{x}}_{0}$.

2: for $k=1,\cdots,K$ do

3:
$(\tilde{\bf{x}}_{k},\tilde{\bf{y}}_{k})=\text{L-SVRE}~{}\big{(}\big{\\{}f_{i}({\bf{x}},{\bf{y}})+\frac{\beta}{2}\left\|{\bf{x}}-{\bf{u}}_{k-1}\right\|_{2}^{2}\big{\\}}_{i=1}^{n},{\bf{x}}_{k-1},{\bf{y}}_{k-1},\tau_{k},p,T_{k}\big{)}$

4:
${\bf{x}}_{k}={\mathcal{P}}_{{\mathcal{X}}}\left(\tilde{\bf{x}}_{k}-\tau_{k}\nabla_{{\bf{x}}}F_{k}\big{(}\tilde{\bf{x}}_{k},\tilde{\bf{y}}_{k}\big{)}\right)$

5:
${\bf{y}}_{k}={\mathcal{P}}_{{\mathcal{Y}}}\left(\tilde{\bf{y}}_{k}+\tau_{k}\nabla_{{\bf{y}}}F_{k}\big{(}\tilde{\bf{x}}_{k},\tilde{\bf{y}}_{k}\big{)}\right)$

6: ${\bf{u}}_{k}={\bf{x}}_{k}+\gamma({\bf{x}}_{k}-{\bf{x}}_{k-1})$

7: end for

8: Output: $({\bf{x}}_{K},{\bf{y}}_{K})$.

######  Theorem 2.

Assume that $\mu_{x}=\mu_{y}=\mu$ and $\\{f_{i}\\}_{i=1}^{n}$ is $L$-average
smooth. Then Algorithm 1 with probability parameter $p=1/(2n)$ and stepsize
$\tau=1/(4\sqrt{n}L)$ satisfies

$\displaystyle\mathbb{E}\left\|{\bf{z}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}\leq
4\left\|{\bf{z}}_{0}-{\bf{z}}^{*}\right\|_{2}^{2}\left(1-\frac{1}{4(n+2\sqrt{n}L/\mu)}\right)^{k}\\!.$
(5)

The result of inequality (5) means that L-SVRE could find
$(\hat{\bf{x}},\hat{\bf{y}})$ satisfying
${\mathbb{E}}[\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|\hat{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}]\leq{\varepsilon}$
with ${\mathcal{O}}((n{+}\sqrt{n}L/\mu)\log(1/{\varepsilon}))$ iterations.
Since we select $p=1/2n$ in the theorem, each iteration requires
${\mathcal{O}}(1)$ SFO calls in expectation. Hence, we have proved that the
upper bound complexity of L-SVRE matches the lower bound shown in Theorem 1.

###  3.2 Acceleration for Unbalanced SCSC Minimax

Note that the convergence result of L-SVRE is not perfect when the objective
function is unbalanced. For example, we consider problem (1) in the case of
$\kappa_{x}=\kappa>\sqrt{n}>\kappa_{y}={\mathcal{O}}(1)$. Then Theorem 2
cannot leverage the well-conditioned assumption on ${\bf{y}}$ and leads to SFO
upper bound ${\mathcal{O}}\left(\sqrt{n}\kappa\log(1/{\varepsilon}))\right)$,
which is worse than complexity
$\tilde{\mathcal{O}}(n\sqrt{\kappa}\log^{3}(1/{\varepsilon}))$ achieved by
deterministic algorithms [22].

Our key intuition to establish a better SFO algorithm for unbalanced SCSC
minimax problems is taking the advantage of the optimality of L-SVRE in the
balanced case. We present the new method AL-SVRE in Algorithm 2, whose
iteration applies L-SVRE to solve the following sub-problem

$\displaystyle\min_{{\bf{x}}\in{\mathcal{X}}}\max_{{\bf{y}}\in{\mathcal{Y}}}F_{k}({\bf{x}},{\bf{y}})\triangleq
f({\bf{x}},{\bf{y}})+\frac{\beta}{2}\left\|{\bf{x}}-{\bf{u}}_{k-1}\right\|_{2}^{2}.$
(6)

Since Theorem 2 only provides the convergence rate for L-SVRE by distance, we
introduce additional projection gradient iterations (Lines 4-5 of Algorithm 2)
on the output of the sub-problem solver. These steps help us control the
accuracy with respect to primal and dual functions, which is helpful to
establish the convergence results with respect to the duality gap in our main
result Theorem 3.

######  Lemma 1.

Suppose the function
$f({\bf{x}},{\bf{y}})\colon{\mathcal{X}}\times{\mathcal{Y}}\to{\mathbb{R}}$ is
$(\mu_{x},\mu_{y})$-convex-concave and $L$-smooth. Denote the saddle point of
$\min_{{\bf{x}}\in{\mathcal{X}}}\max_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}},{\bf{y}})$
by $({\bf{x}}^{*},{\bf{y}}^{*})$ and let the condition numbers of $f$ be
$\kappa_{x}=L/\mu_{x}$ and $\kappa_{y}=L/\mu_{y}$. Assume that the point
$(\hat{\bf{x}},\hat{\bf{y}})$ satisfies

$\displaystyle\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|\hat{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}\leq{\varepsilon}.$

We introduce

$\displaystyle\tilde{\bf{x}}={\mathcal{P}}_{{\mathcal{X}}}\left(\hat{\bf{x}}-\eta\nabla_{{\bf{x}}}f(\hat{\bf{x}},\hat{\bf{y}})\right)~{}~{}\text{and}~{}~{}\tilde{\bf{y}}={\mathcal{P}}_{{\mathcal{Y}}}\left(\hat{\bf{y}}+\eta\nabla_{{\bf{y}}}f(\hat{\bf{x}},\hat{\bf{y}})\right),$

then it holds that

$\displaystyle\max_{{\bf{y}}\in{\mathcal{Y}}}f(\tilde{\bf{x}},{\bf{y}})-f({\bf{x}}^{*},{\bf{y}}^{*})\leq\left(\sqrt{2}(1+\eta
L)+2(1+\eta
L)^{2}+2\right)\kappa_{y}L{\varepsilon}+\frac{{\varepsilon}}{2\eta}$

and

$\displaystyle
f({\bf{x}}^{*},{\bf{y}}^{*})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},\tilde{\bf{y}})\leq\left(\sqrt{2}(1+\eta
L)+2(1+\eta
L)^{2}+2\right)\kappa_{x}L{\varepsilon}+\frac{{\varepsilon}}{2\eta}.$

The following lemma shows that we can upper bound the distance from given
point to the saddle point by its primal-dual gap.

######  Lemma 2.

Suppose the function
$f({\bf{x}},{\bf{y}}):{\mathcal{X}}\times{\mathcal{Y}}\to{\mathbb{R}}$ is
$(\mu_{x},\mu_{y})$-convex-concave and $L$-smooth. Denote the saddle point of
$f$ by $({\bf{x}}^{*},{\bf{y}}^{*})$. Then for any
$\hat{\bf{x}}\in{\mathcal{X}},\hat{\bf{y}}\in{\mathcal{Y}}$, we have

$\displaystyle\mu_{x}\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\mu_{y}\left\|\hat{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}\leq
2\left(\max_{{\bf{y}}\in{\mathcal{Y}}}f(\hat{\bf{x}},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},\hat{\bf{y}})\right).$

Then introduces four auxiliary quantities and provide their upper bounds,
which are useful to the analyze the convergence of AL-SVRE.

######  Lemma 3.

We use the notation of Algorithm 2 and denote
$({\bf{x}}_{k}^{*},{\bf{y}}_{k}^{*})$ is the saddle point of $F_{k}$ and

$\displaystyle\Delta_{f}=\max_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}}_{0},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},{\bf{y}}_{0}).$

Then, for each $k\geq 1$, we have

$\displaystyle\mathbb{E}\left[\left\|{\bf{x}}_{k}-{\bf{x}}_{k}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}_{k}-{\bf{y}}_{k}^{*}\right\|_{2}^{2}\right]\leq{\varepsilon}_{k},$
(7)
$\displaystyle\mathbb{E}\left[\max_{{\bf{y}}\in{\mathcal{Y}}}F_{k}({\bf{x}}_{k},{\bf{y}})-F_{k}({\bf{x}}_{k}^{*},{\bf{y}}_{k}^{*})\right]\leq\frac{2\Delta_{f}}{9}(1-\rho)^{k},$
(8)
$\displaystyle\mathbb{E}\left\|{\bf{x}}_{k}-{\bf{x}}^{*}\right\|_{2}^{2}\leq\frac{2\delta_{k}}{\mu_{x}},$
(9)
$\displaystyle\mathbb{E}\left[\left\|{\bf{x}}^{*}_{k}-{\bf{x}}^{*}_{k+1}\right\|_{2}^{2}\\!+\\!\left\|{\bf{y}}^{*}_{k}-{\bf{y}}^{*}_{k+1}\right\|_{2}^{2}\right]\leq\frac{72\beta\delta_{k-2}}{\mu_{x}\min\\{\mu_{x},\mu_{y}\\}},$
(10)

where

$\displaystyle{\varepsilon}_{k}\triangleq\frac{2\mu_{y}\Delta_{f}(1-\rho)^{k}}{3(L+\beta)(7(L+\beta)+2\sqrt{n}\mu_{y})}$

and

$\displaystyle\delta_{k}\triangleq\frac{8\Delta_{f}(1-\rho)^{k+1}}{(\sqrt{q}-\rho)^{2}}.$

Based on above lemmas, we obtain the main result of this paper as follows.

######  Theorem 3.

Running Algorithm 2 with $q=\mu_{x}/(\mu_{x}+\beta)$, $\beta\geq 0$, $p=1/2n$,
$\tau_{k}=1/(4\sqrt{n}(L+\beta))$ and

$\displaystyle
T_{k}=\Bigg{\lceil}4\left(n+\frac{2\sqrt{n}(L+\beta)}{\min\\{\mu_{x}+\beta,\mu_{y}\\}}\right)\log\left(\\!12\\!\left(\frac{2}{1-\rho}\\!+\\!\frac{1728\beta(L+\beta)(7(L+\beta)+2\sqrt{n}\mu_{y}))}{\mu_{x}\mu_{y}\min\\{\mu_{x},\mu_{y}\\}(1-\rho)^{2}(\sqrt{q}-\rho)^{2}}\right)\right)\Bigg{\rceil},$

where $\rho<\sqrt{q}$, then we have

$\displaystyle\mathbb{E}\left[\max_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}}_{k},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},{\bf{y}}_{k})\right]\leq\frac{916\Delta_{f}\left(\kappa_{x}L+\sqrt{n}(L+\beta)\right)\kappa_{y}^{2}}{\mu_{x}(\sqrt{q}-\rho)^{2}}(1-\rho)^{k},$

where
$\Delta_{f}=\max_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}}_{0},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},{\bf{y}}_{0})$.

Theorem 3 shows the ${\varepsilon}$-saddle point can be obtained by calling
$K=\tilde{\mathcal{O}}\big{(}\sqrt{(\mu_{x}{+}\beta)/\mu_{x}}\log(1/{\varepsilon})\big{)}$
times AL-SVRE to solve the sub-problem. By minimizing the product of dominant
terms (ignore logarithmic terms) $\sqrt{(\mu_{x}+\beta)/\mu_{x}}$ and
$\left(n+2\sqrt{n}(L+\beta)/\min\\{\mu_{x}+\beta,\mu_{y}\\}\right)$ in $K$ and
$T_{k}$ respectively, we decide the choice of $\beta$ as follows (since we
have suppose $\mu_{x}\leq\mu_{y}$)

$\displaystyle\beta=\begin{cases}\mu_{y}-\mu_{x},~{}~{}&\text{if
}\kappa_{y}\geq\sqrt{n},\\\ L/\sqrt{n}-\mu_{x},~{}~{}&\text{if
}\kappa_{x}>\sqrt{n}>\kappa_{y},\\\ 0,~{}~{}&\text{otherwise,}\end{cases}$
(11)

Combing the result of Theorem 3 and equation (11), we immediately obtain the
following corollary, which implies AL-SVRE has near optimal SFO upper bound
for unbalanced SCSC minimax optimization.

######  Corollary 1.

Suppose Problem (1) satisfies $\mu_{x}<\mu_{y}$. If running AL-SVRE with the
setting of Theorem 3 and letting $\beta$ as (11), $\rho=0.5\sqrt{q}$ and

$\displaystyle
K=\left\lceil\frac{2}{\sqrt{q}}\log\left(10992\sqrt{n}\Delta_{f}\kappa_{y}\kappa_{x}^{3}\right)\right\rceil,$

then we have

$\displaystyle\mathbb{E}\Big{[}\max_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}}_{K},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},{\bf{y}}_{K})\Big{]}\leq{\varepsilon}$

with the number of SFO calls at most

$\displaystyle{\mathcal{O}}\left(\sqrt{n(\sqrt{n}+\kappa_{x})(\sqrt{n}+\kappa_{y})}\log(n\kappa_{x})\log\left(\frac{n\Delta_{f}\kappa_{y}\kappa_{x}}{{\varepsilon}}\right)\right).$

The design of AL-SVRE aims to sufficiently take the advantage of AL-SVRE’s
optimality for the balanced SCSC minimax problem. Hence, the choice of $\beta$
makes the sub-problem (6) more balanced than the main problem (1). In
contrast, previous catalyst-type methods [22, 35, 33] select a larger $\beta$
to guarantee the sub-problem be well-conditioned in one of the variables.
However, such strategy leads to that the sub-problem is still so unbalanced
and we need two-loops of iterations to solve it. As a result, the
implementation of the whole procedure is more complicated and almost cannot be
used in practical.

#### Discussion

Note that Tominin et al. [33]’s work supposes each $f_{i}({\bf{x}},{\bf{y}})$
is $L_{i}$-smooth, that is

$\displaystyle\left\|\nabla f_{i}({\bf{z}}_{1})-\nabla
f_{i}({\bf{z}}_{2})\right\|_{2}\leq
L_{i}\left\|{\bf{z}}_{1}-{\bf{z}}_{2}\right\|_{2}$ (12)

where ${\bf{z}}_{1}=({\bf{x}}_{1},{\bf{y}}_{1})$ and
${\bf{z}}_{2}=({\bf{x}}_{2},{\bf{y}}_{2})$, which leads to the objective
function $f({\bf{z}})=\frac{1}{n}\sum_{i=1}^{n}f_{i}({\bf{z}})$ is
$L_{G}$-smooth with $L_{G}=\frac{1}{n}\sum_{i=1}^{n}L_{i}$. Furthermore, we
can verify that $\\{f_{i}\\}_{i=1}^{n}$ is $L_{A}$-average smooth, where
$L_{A}=\sqrt{\frac{1}{n}\sum_{i=1}^{n}L_{i}^{2}}$ (c.f. Lemma 11).

Consider a simple class of functions $\\{g_{i}({\bf{z}})\\}_{i=1}^{n}$ such
that $g_{i}({\bf{z}})=\frac{\sqrt{n}L}{2}({\bf{e}}_{i}^{\top}{\bf{z}})^{2}$,
where $\\{{\bf{e}}_{i}\\}_{i=1}^{n}$ is the standard basis of
${\mathbb{R}}^{n}$. It is easily to check that $g_{i}$ is $\sqrt{n}L$-smooth
and

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
g_{i}({\bf{z}}_{1})-\nabla
g_{i}({\bf{z}}_{2})\right\|_{2}^{2}=\frac{1}{n}\sum_{i=1}^{n}(nL^{2})\left\|{\bf{e}}_{i}{\bf{e}}_{i}^{\top}({\bf{z}}_{1}-{\bf{z}}_{2})\right\|_{2}^{2}=L^{2}\sum_{i=1}^{n}(z_{1,i}-z_{2,i})^{2}=L^{2}\left\|{\bf{z}}_{1}-{\bf{z}}_{2}\right\|_{2}^{2},$

which implies that $\\{g_{i}\\}_{i=1}^{n}$ is $L$-average smooth.

Using notations of Tominin et al. [33] on $\\{g_{i}\\}_{i=1}^{n}$, we have
$L_{i}=\sqrt{n}L$ and $L_{G}=\frac{1}{n}\sum_{i=1}^{n}L_{i}=\sqrt{n}L$. Hence,
their smoothness parameter $L_{G}$ is larger than the average-smoothness
parameter $L$ we used in this paper.

##  4 Extensions to Non-SCSC Minimax

We can also apply AL-SVRE to solve convex-concave minimax without SCSC
assumption.

###  4.1 Convex-Strongly-Concave Case

If the objective function $f({\bf{x}},{\bf{y}})$ is $(0,\mu_{y})$-convex-
concave and ${\mathcal{X}}$ is bounded with diameter $D_{x}$, we construct the
auxiliary SCSC function to approximate it as follows:

$\displaystyle f_{{\varepsilon},{\bf{x}}_{0}}({\bf{x}},{\bf{y}})\triangleq
f({\bf{x}},{\bf{y}})+\frac{{\varepsilon}}{4D_{x}^{2}}\left\|{\bf{x}}-{\bf{x}}_{0}\right\|_{2}^{2}.$
(13)

Then the difference of duality gaps between $f_{{\varepsilon},{\bf{x}}_{0}}$
and $f$ should be small. The following lemma presents this fact formally.

######  Lemma 4.

Suppose $f({\bf{x}},{\bf{y}})$ is $(0,\mu_{y})$-convex-concave,
${\mathcal{X}}$ is bounded with diameter $D_{x}$ and
${\bf{x}}_{0}\in{\mathcal{X}}$. Consider the function
$f_{{\varepsilon},{\bf{x}}_{0}}({\bf{x}},{\bf{y}})$ defined as (13). Then for
any $(\hat{\bf{x}},\hat{\bf{y}})\in{\mathcal{X}}\times{\mathcal{Y}}$, we have

$\displaystyle\max_{{\bf{y}}\in{\mathcal{Y}}}f(\hat{{\bf{x}}},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},\hat{{\bf{y}}})\leq\frac{{\varepsilon}}{2}+\max_{{\bf{y}}\in{\mathcal{Y}}}f_{{\varepsilon},{\bf{x}}_{0}}(\hat{{\bf{x}}},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f_{{\varepsilon},{\bf{x}}_{0}}({\bf{x}},\hat{{\bf{y}}}).$

Lemma 4 means that any ${\varepsilon}/2$-saddle-point of
$f_{{\varepsilon},{\bf{x}}_{0}}$ is also an ${\varepsilon}$-saddle-point of
$f$. Hence, we can directly run AL-SVRE on $f_{{\varepsilon},{\bf{x}}_{0}}$
and connect Lemma 4 and Theorem 3 to establish the convergence result for
$(0,\mu_{y})$-convex-concave minimax optimization as follows.

|  |  |
---|---|---|---
(a) AUC, a9a | (b) AUC, w8a | (c) wireless-500 | (d) wireless-1000
Figure 1: We demonstrate comparison on AUC maximization for SCSC minimax in
sub-figures (a) and (b); and wireless communication for general convex-concave
minimax in sub-figures (c) and (d).

######  Corollary 2.

Under settings of Lemma 4, for ${\varepsilon}\leq 4LD_{x}^{2}$, the total
complexity of SFO calls for finding an ${\varepsilon}/2$-saddle-point of
$f_{{\varepsilon},{\bf{x}}_{0}}$, which is also an ${\varepsilon}$-saddle-
point of $f$, is

$\displaystyle{\tilde{\mathcal{O}}\left(\\!\left(n\\!+\\!D_{x}\sqrt{\frac{nL\kappa_{y}}{{\varepsilon}}}\\!+\\!n^{3/4}\sqrt{\kappa_{y}}\\!+\\!n^{3/4}D_{x}\sqrt{\frac{L}{{\varepsilon}}}\right)\log\left(\frac{1}{{\varepsilon}}\right)\\!\right)}$

Recently, Yang et al. [40] also studied Catalyst acceleration for strongly-
convex-concave minimax optimization, but they only considered the special case
of ${\varepsilon}<\mu_{y}$ which leads to that their result does not match the
lower bound.

###  4.2 Convex-Concave Case

In general convex-concave setting, we suppose ${\mathcal{X}}$ and
${\mathcal{Y}}$ are bounded with diameters $D_{x}$ and $D_{y}$ respectively.
Then unbalance of the problem comes from the difference between diameters
$D_{x}$ and $D_{y}$. We introduce the auxiliary SCSC function as follows:

$\displaystyle\begin{split}f_{{\varepsilon},{\bf{x}}_{0},{\bf{y}}_{0}}({\bf{x}},{\bf{y}})\triangleq
f({\bf{x}},{\bf{y}})+\frac{{\varepsilon}}{8D_{x}^{2}}\left\|{\bf{x}}-{\bf{x}}_{0}\right\|_{2}^{2}-\frac{{\varepsilon}}{8D_{y}^{2}}\left\|{\bf{y}}-{\bf{y}}_{0}\right\|_{2}^{2}.\end{split}$
(14)

Similarly, Lemma 5 shows that any ${\varepsilon}/2$-saddle-point of
$f_{{\varepsilon},{\bf{x}}_{0},{\bf{y}}_{0}}$ is an ${\varepsilon}$-saddle-
point of $f$.

######  Lemma 5.

Suppose that $f({\bf{x}},{\bf{y}})$ is convex-concave, ${\mathcal{X}}$ and
${\mathcal{Y}}$ are bounded with diameters $D_{x}$ and $D_{y}$ respectively.
Consider the function
$f_{{\varepsilon},{\bf{x}}_{0},{\bf{y}}_{0}}({\bf{x}},{\bf{y}})$ defined as
(14). Then for any
$(\hat{\bf{x}},\hat{\bf{y}})\in{\mathcal{X}}\times{\mathcal{Y}}$, we have

$\displaystyle\max_{{\bf{y}}\in{\mathcal{Y}}}f(\hat{{\bf{x}}},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},\hat{{\bf{y}}})\leq\frac{{\varepsilon}}{2}+\max_{{\bf{y}}\in{\mathcal{Y}}}f_{{\varepsilon},{\bf{x}}_{0},{\bf{y}}_{0}}(\hat{{\bf{x}}},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f_{{\varepsilon},{\bf{x}}_{0},{\bf{y}}_{0}}({\bf{x}},\hat{{\bf{y}}}).$

Combining Lemma 5 and Theorem 3, we obtain the convergence result of Corollary
3.

######  Corollary 3.

Under settings of Lemma 5, for any ${\varepsilon}\leq
4L\min\\{D_{x}^{2},D_{y}^{2}\\}$, the total complexity of SFO calls for
finding an ${\varepsilon}/2$-saddle-point of
$f_{{\varepsilon},{\bf{x}}_{0},{\bf{y}}_{0}}$, which is also an
${\varepsilon}$-saddle-point of $f$, is

$\displaystyle\mbox{$\displaystyle{\tilde{\mathcal{O}}\\!\left(\\!\left(n\\!+\\!\frac{\sqrt{n}LD_{x}D_{y}}{{\varepsilon}}\\!+\\!n^{3/4}(D_{x}\\!+\\!D_{y})\sqrt{\frac{L}{{\varepsilon}}}\right)\log\left(\frac{1}{{\varepsilon}}\right)\\!\right)}$}.$

The result of Corollary 3 nearly matches the lower bound w.r.t.
${\varepsilon}$, $L$, $n$, $D_{x}$ and $D_{y}$ simultaneously [13]. Note that
the best known upper bound in convex-concave setting [1] is optimal to
${\varepsilon}$, $L$ and $n$, but it regards the diameters as constants and
does not consider the potential unbalance arose from $D_{x}$ and $D_{y}$.

##  5 Experiments

We conduct the experiments on AUC maximization [14, 41, 30] and wireless
communication [10, 3, 40] problems. We evaluate the performance of AL-SVRE and
compare it with baseline algorithms ExtraGradient (EG) [17, 11] and L-SVRE
[1]. We summarize the datasets in Table 4. The empirical results in Figure 1
show that our proposed AL-SVRE performs better than the baselines.

###  5.1 AUC Maximization

AUC maximization [14] considers finding the classifier
${\bm{\theta}}\in{\mathbb{R}}^{d}$ on training set
$\\{({\bf{a}}_{i},b_{i})\\}_{i=1}^{n}$, where
${\bf{a}}_{i}\in{\mathbb{R}}^{d}$ and $b_{i}\in\\{+1,-1\\}$. We denote $n^{+}$
be the numbers of positive instances and let $\hat{p}=n^{+}/n$. Our
experiments focus on the unbalanced SCSC minimax formulation for AUC
maximization [30, 41] as follows

$\displaystyle\min_{{\bf{x}}\in{\mathbb{R}}^{d+2}}\max_{y\in{\mathbb{R}}}f({\bf{x}},y)\triangleq\frac{1}{n}\sum_{i=1}^{n}f_{i}({\bf{x}},y;{\bf{a}}_{i},b_{i},\lambda),$
(15)

where ${\bf{x}}=[{\bm{\theta}};u;v]\in{\mathbb{R}}^{d+2}$, $\lambda>0$ is the
regularization parameter and each component is defined as

$\displaystyle f_{i}({\bf{x}},{\bf{y}};{\bf{a}}_{i},b_{i},\lambda)=$
$\displaystyle\frac{\lambda}{2}\|{\bf{x}}\|_{2}^{2}-\hat{p}(1-\hat{p})y^{2}$
$\displaystyle+\hat{p}(({\bm{\theta}}^{\top}{\bf{a}}_{i}-v)^{2}+2(1+y){\bm{\theta}}^{\top}{\bf{a}}_{i})\mathbb{I}_{b_{i}=-1}$
$\displaystyle+(1-\hat{p})(({\bm{\theta}}^{T}{\bf{a}}_{i}-u)^{2}-2(1+y){\bm{\theta}}^{\top}{\bf{a}}_{i})\mathbb{I}_{b_{i}=1}.$

We set $\lambda=10^{-10}$ and evaluate all algorithms on datasets “a9a” and
“w8a” [4]. We tune stepsize of EG and L-SVRE (or as sub-problem solver) from
$\\{0.02,0.05,0.1,0.2,0.5\\}$. For L-SVRE, we let $p=1/2n$ by the setting of
Theorem 1. For AL-SVRE, we let $\beta=0.01$, $q=\lambda_{x}/(\lambda+\beta)$;
$T_{k}=\lceil 0.3n\rceil$ for “a9a” and $T_{k}=\lceil 0.5n\rceil$ for “w8a”.
We present the results of epochs against $\log\left\|\nabla
f({\bf{x}},{\bf{y}})\right\|_{2}$ in Figure 1 (a) and (b).

###  5.2 The Wireless Communication Problems

We consider the wireless communication problem [40, 3] as follows

$\displaystyle\min_{{\bf{x}}\in{\mathcal{X}}}\max_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}},{\bf{y}})\triangleq-\frac{1}{n}\sum_{i=1}^{n}\log\left(1+\frac{b_{i}x_{i}}{a_{i}+y_{i}}\right),$
(16)

where constrained sets are
${\mathcal{X}}=\\{{\bf{x}}:\left\|{\bf{x}}\right\|_{2}\leq R,x_{i}\geq 0\\}$
and ${\mathcal{Y}}=\\{{\bf{y}}:{\bf 1}^{\top}{\bf{y}}=n,y_{i}\geq 0\\}$. We
can verify the objective function of problem (16) is convex-concave but
possibly be neither strongly-convex nor strongly-concave.

We generate two datasets with (i) $n=500$, $R=1$, ${\bf{b}}={\bf{1}}$,
${\bf{a}}\in{\mathbb{R}}^{500}$ uniformly from $[0,10]^{500}$ and (ii)
$n=1000$, $R=1$, ${\bf{b}}={\bf{1}}$, ${\bf{a}}\in{\mathbb{R}}^{1000}$
uniformly from $[0,50]^{1000}$. We tune the stepsize for all the algorithms
from $[0.01,0.1,1.0]$ and set $p=2/n$ like AUC maximization. For AL-SVRE, we
use the auxiliary function as follows

$\displaystyle\hat{f}({\bf{x}},{\bf{y}})\triangleq
f({\bf{x}},{\bf{y}})+\frac{{\varepsilon}}{8R^{2}}\left\|{\bf{x}}\right\|_{2}^{2}-\frac{{\varepsilon}}{8n^{2}}\left\|{\bf{y}}-{\bf{1}}\right\|_{2}^{2}$

where ${\varepsilon}=10^{-6}/n$. We also set $T_{k}=500$, $q=R^{2}/n^{2}$ and
$\beta={\varepsilon}/(4R^{2})-{\varepsilon}/(4n^{2})$. Since the problem (16)
is constrained, we use evaluation the performance by epochs against the
logarithm of the magnitude of gradient mapping, which is defined as

$\displaystyle{\frac{\left\|{\bf{x}}-{\mathcal{P}}_{{\mathcal{X}}}({\bf{x}}\\!-\\!\hat{\tau}\nabla_{{\bf{x}}}f({\bf{x}},{\bf{y}}))\right\|_{2}+\left\|{\bf{y}}-{\mathcal{P}}_{{\mathcal{Y}}}({\bf{y}}\\!+\\!\hat{\tau}\nabla_{{\bf{y}}}f({\bf{x}},{\bf{y}}))\right\|_{2}}{\hat{\tau}}}$

where $\hat{\tau}$ is set to be $0.1$. We present the empirical results in
Figure 1 (c) and (d).

Table 4: Summary of datasets | a9a | w8a | wireless-500 | wireless-1000
---|---|---|---|---
$n$ | 32,561 | 45,546 | 500 | 1,000
$d$ |  123 |  300 | 500 | 1,000

##  6 Conclusions

In this paper we have studied unbalanced convex-concave minimax problems with
finite-sum structure. We have shown the optimality of L-SVRE for balanced SCSC
minimax and proposed a near optimal algorithm AL-SVRE for unbalanced problems.
AL-SVRE only contains two loops of iterations, making its implementation more
simple and practical than the existing methods for unbalanced SCSC minimax. We
have also extended our algorithm to more general convex-concave minimax
problems and showed the near optimality.

It would be interesting to apply our ideas to solve specific convex-concave
minimax with refined smoothness assumptions and specific bilinear settings
[35, 38, 28]. It is also possible to design accelerated variance reduced
algorithms to solve unbalanced minimax problems in online setting.

## References

  * Alacaoglu and Malitsky [2021] Ahmet Alacaoglu and Yura Malitsky.  Stochastic variance reduction for variational inequality methods.  _arXiv preprint arXiv:2102.08352_ , 2021.
  * Allen-Zhu [2017] Zeyuan Allen-Zhu.  Katyusha: The first direct acceleration of stochastic gradient methods.  _Journal of Machine Learning Research_ , 18(1):8194–8244, 2017.
  * Boyd et al. [2004] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe.  _Convex optimization_.  Cambridge university press, 2004.
  * Chang and Lin [2011] Chih-Chung Chang and Chih-Jen Lin.  LIBSVM: A library for support vector machines.  _ACM Transactions on Intelligent Systems and Technology_ , 2:27:1–27:27, 2011.  Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
  * Chavdarova et al. [2019] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien.  Reducing noise in GAN training with variance reduced extragradient.  In _NeurIPS_ , 2019.
  * Defazio et al. [2014] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien.  SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives.  In _NIPS_ , 2014.
  * Duchi and Namkoong [2019] John C. Duchi and Hongseok Namkoong.  Variance-based regularization with convex objectives.  _Journal of Machine Learning Research_ , 20(68):1–55, 2019.
  * Fang et al. [2018] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang.  SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator.  In _NeurIPS_ , 2018.
  * Frostig et al. [2015] Roy Frostig, Rong Ge, Sham Kakade, and Aaron Sidford.  Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization.  In _ICML_ , 2015.
  * Garnaev and Trappe [2009] Andrey Garnaev and Wade Trappe.  An eavesdropping game with SINR as an objective function.  In _International Conference on Security and Privacy in Communication Systems_ , pages 142–162. Springer, 2009.
  * Gidel et al. [2019] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien.  A variational inequality perspective on generative adversarial networks.  In _ICLR_ , 2019.
  * Guo et al. [2020] Zhishuai Guo, Mingrui Liu, Zhuoning Yuan, Li Shen, Wei Liu, and Tianbao Yang.  Communication-efficient distributed stochastic AUC maximization with deep neural networks.  In _ICML_ , 2020.
  * Han et al. [2021] Yuze Han, Guangzeng Xie, and Zhihua Zhang.  Lower complexity bounds of finite-sum optimization problems: The results and construction.  _arXiv preprint arXiv:2103.08280_ , 2021.
  * Hanley and McNeil [1982] James A Hanley and Barbara J McNeil.  The meaning and use of the area under a receiver operating characteristic (ROC) curve.  _Radiology_ , 143(1):29–36, 1982.
  * Ibrahim et al. [2020] Adam Ibrahim, Waıss Azizian, Gauthier Gidel, and Ioannis Mitliagkas.  Linear lower bounds and conditioning of differentiable games.  In _ICML_ , 2020.
  * Johnson and Zhang [2013] Rie Johnson and Tong Zhang.  Accelerating stochastic gradient descent using predictive variance reduction.  In _NIPS_ , 2013.
  * Korpelevich [1977] GM Korpelevich.  Extragradient method for finding saddle points and other problems.  _Matekon_ , 13(4):35–49, 1977.
  * Kovalev et al. [2020] Dmitry Kovalev, Samuel Horváth, and Peter Richtárik.  Don’t jump through hoops and remove those loops: Svrg and katyusha are better without the outer loop.  In _ALT_ , 2020.
  * Lan and Zhou [2017] Guanghui Lan and Yi Zhou.  An optimal randomized incremental gradient method.  _Mathematical programming_ , pages 1–49, 2017.
  * Lin et al. [2018] Hongzhou Lin, Julien Mairal, and Zaid Harchaoui.  Catalyst acceleration for first-order convex optimization: from theory to practice.  _Journal of Machine Learning Research_ , 18(212):1–54, 2018.
  * Lin et al. [2020a] Tianyi Lin, Chi Jin, and Michael I. Jordan.  On gradient descent ascent for nonconvex-concave minimax problems.  In _ICML_ , 2020a.
  * Lin et al. [2020b] Tianyi Lin, Chi Jin, and Michael I. Jordan.  Near-optimal algorithms for minimax optimization.  In _COLT_ , 2020b.
  * Liu et al. [2020] Mingrui Liu, Zhuoning Yuan, Yiming Ying, and Tianbao Yang.  Stochastic AUC maximization with deep neural networks.  In _ICLR_ , 2020.
  * Luo et al. [2019] Luo Luo, Cheng Chen, Yujun Li, Guangzeng Xie, and Zhihua Zhang.  A stochastic proximal point algorithm for saddle-point problems.  _arXiv preprint arXiv:1909.06946_ , 2019.
  * Luo et al. [2020] Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang.  Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems.  In _NeurIPS_ , 2020.
  * Mokhtari et al. [2020] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil.  A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach.  In _AISTATS_ , pages 1497–1507. PMLR, 2020.
  * Nesterov [2018] Yurii Nesterov.  _Lectures on convex optimization_ , volume 137.  Springer, 2018.
  * Ouyang and Xu [2018] Yuyuan Ouyang and Yangyang Xu.  Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems.  _arXiv preprint arXiv:1808.02901_ , 2018.
  * Palaniappan and Bach [2016] Balamurugan Palaniappan and Francis Bach.  Stochastic variance reduction methods for saddle-point problems.  In _NIPS_ , 2016.
  * Shen et al. [2018] Zebang Shen, Aryan Mokhtari, Tengfei Zhou, Peilin Zhao, and Hui Qian.  Towards more efficient stochastic decentralized learning: Faster convergence and sparse communication.  In _ICML_ , 2018.
  * Sinha et al. [2018] Aman Sinha, Hongseok Namkoong, and John Duchi.  Certifying some distributional robustness with principled adversarial training.  In _ICLR_ , 2018.
  * Thekumparampil et al. [2019] Kiran K. Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh.  Efficient algorithms for smooth minimax optimization.  In _NeurIPS_ , 2019.
  * Tominin et al. [2021] Vladislav Tominin, Yaroslav Tominin, Ekaterina Borodich, Dmitry Kovalev, Alexander Gasnikov, and Pavel Dvurechensky.  On accelerated methods for saddle-point problems with composite structure.  _arXiv preprint arXiv:2103.09344_ , 2021.
  * Wai et al. [2018] Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, and Mingyi Hong.  Multi-agent reinforcement learning via double averaging primal-dual optimization.  In _NeurIPS_ , 2018.
  * Wang and Li [2020] Yuanhao Wang and Jian Li.  Improved algorithms for convex-concave minimax optimization.  _arXiv preprint arXiv:2006.06359_ , 2020.
  * Woodworth and Srebro [2016] Blake Woodworth and Nathan Srebro.  Tight complexity bounds for optimizing composite objectives.  In _NIPS_ , 2016.
  * Xie et al. [2020] Guangzeng Xie, Luo Luo, Yijiang Lian, and Zhihua Zhang.  Lower complexity bounds for finite-sum convex-concave minimax optimization problems.  In _ICML_ , 2020.
  * Xie et al. [2021] Guangzeng Xie, Yuze Han, and Zhihua Zhang.  DIPPA: An improved method for bilinear saddle point problems.  _arXiv preprint arXiv:2103.08270_ , 2021.
  * Yan et al. [2019] Yan Yan, Yi Xu, Qihang Lin, Lijun Zhang, and Tianbao Yang.  Stochastic primal-dual algorithms with faster convergence than ${O}(1/\sqrt{t})$ for problems without bilinear structure.  _arXiv preprint arXiv:1904.10112_ , 2019.
  * Yang et al. [2020] Junchi Yang, Siqi Zhang, Negar Kiyavash, and Niao He.  A catalyst framework for minimax optimization.  In _NeurIPS_ , 2020.
  * Ying et al. [2016] Yiming Ying, Longyin Wen, and Siwei Lyu.  Stochastic online AUC maximization.  In _NIPS_ , 2016.
  * Zhang et al. [2019] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang.  On lower iteration complexity bounds for the saddle point problems.  _arXiv preprint arXiv:1912.07481_ , 2019.
  * Zhou and Gu [2019] Dongruo Zhou and Quanquan Gu.  Lower bounds for smooth nonconvex finite-sum optimization.  In _ICML_ , 2019.

## Supplemental Materials

The supplemental materials are organized as follows. Section A presents
several lemmas for further theoretical analysis. Section B provides the proof
of Theorem 2, which is the convergence result of L-SVRE for balanced SCSC
setting. Section C gives the detailed analysis for AL-SVRE, including the
proof of our main results Theorem 3, Corollary 1 and other lemmas. Section D
provide the proof of Theorem 1, which implies L-SVRE is an optimal SFO
algorithm for balanced finite-sum SCSC minimax. Section E provides the
detailed proofs for the results in Section 4.

##  Appendix A Technical Lemmas

We first present some useful tools for the analysis of constrained
optimization.

######  Lemma 6 (Nesterov [27, Theorem 2.2.9 and 2.2.12]).

Let
${\bf{z}}^{*}=\operatorname*{arg\,min}_{{\bf{z}}\in{\mathcal{C}}}Q({\bf{z}})$,
where $Q$ is smooth and strongly-convex; ${\mathcal{C}}$ is convex and
compact. Then, for any ${\bf{z}}\in{\mathcal{C}}$ and $\eta>0$, we have

$\displaystyle\langle\nabla Q({\bf{z}}^{*}),{\bf{z}}-{\bf{z}}^{*}\rangle\geq
0\quad\text{and}\quad{\bf{z}}^{*}={\mathcal{P}}_{{\mathcal{C}}}\left({\bf{z}}^{*}-\eta\nabla
Q({\bf{z}}^{*})\right).$

######  Lemma 7 (Nesterov [27, Corollary 2.2.3]).

Given a convex and compact set ${\mathcal{C}}\subseteq{\mathbb{R}}^{d}$; and
any ${\bf{u}},{\bf{v}}\in{\mathbb{R}}^{d}$, we have
$\left\|{\mathcal{P}}_{\mathcal{C}}({\bf{u}})-{\mathcal{P}}_{\mathcal{C}}({\bf{v}})\right\|_{2}\leq\left\|{\bf{u}}-{\bf{v}}\right\|_{2}$.

######  Lemma 8.

Given a convex and compact set ${\mathcal{C}}\subseteq{\mathbb{R}}^{d}$, for
any ${\bf{u}}\in{\mathbb{R}}^{d}$ and ${\bf{v}}\in{\mathcal{C}}$, we have

$\langle{\mathcal{P}}_{\mathcal{C}}({\bf{u}})-{\bf{u}},{\mathcal{P}}_{\mathcal{C}}({\bf{u}})-{\bf{v}}\rangle\leq
0.$

###### Proof.

Let $Q({\bf{z}})=\frac{1}{2}\left\|{\bf{z}}-{\bf{u}}\right\|_{2}^{2}$, then
${\mathcal{P}}_{\mathcal{C}}({\bf{u}})=\operatorname*{arg\,min}_{{\bf{z}}\in{\mathcal{C}}}Q({\bf{z}})$.
Using Lemma 6, we have

$\displaystyle\langle{\mathcal{P}}_{\mathcal{C}}({\bf{u}})-{\bf{u}},{\bf{v}}-{\mathcal{P}}_{\mathcal{C}}({\bf{u}})\rangle=\langle\nabla
Q({\mathcal{P}}_{\mathcal{C}}({\bf{u}})),{\bf{v}}-{\mathcal{P}}_{\mathcal{C}}({\bf{u}})\rangle\geq
0.$

∎

Then we provides some properties for convex-concave functions.

######  Lemma 9 (Lin et al. [22, Lemma B.2]).

Assume that
$f({\bf{x}},{\bf{y}}):{\mathcal{X}}\times{\mathcal{Y}}\to{\mathbb{R}}$ is
$L$-smooth and $(\mu_{x},\mu_{y})$-convex-concave. We define

$\displaystyle{\bf{y}}_{f}^{*}(\cdot)$
$\displaystyle\triangleq\operatorname*{arg\,max}_{{\bf{y}}\in{\mathcal{Y}}}f(\cdot,{\bf{y}}),~{}\Phi_{f}(\cdot)\triangleq\max_{{\bf{y}}\in{\mathcal{Y}}}f(\cdot,{\bf{y}}),$
$\displaystyle{\bf{x}}_{f}^{*}(\cdot)$
$\displaystyle\triangleq\operatorname*{arg\,min}_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},\cdot),~{}~{}\Psi_{f}(\cdot)\triangleq\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},\cdot).$

Then, there holds that

  1. _(a)_

the function ${\bf{y}}_{f}^{*}(\cdot)$ is $\kappa_{y}$-Lipschitz,

  2. _(b)_

the function $\Phi_{f}(\cdot)$ is $2\kappa_{y}L$-smooth and $\mu_{x}$-strongly
convex with
$\nabla\Phi_{f}(\cdot)=\nabla_{{\bf{x}}}f(\cdot,{\bf{y}}_{f}^{*}(\cdot))$,

  3. _(c)_

the function ${\bf{x}}_{f}^{*}(\cdot)$ is $\kappa_{x}$-Lipschitz,

  4. _(d)_

the function $\Psi_{f}(\cdot)$ is $2\kappa_{x}L$-smooth and $\mu_{y}$-strongly
concave with
$\nabla\Psi_{f}(\cdot)=\nabla_{{\bf{x}}}f({\bf{x}}_{f}^{*}(\cdot),\cdot)$.

######  Lemma 10.

Assume that
$f({\bf{x}},{\bf{y}}):{\mathcal{X}}\times{\mathcal{Y}}\to{\mathbb{R}}$ is
differentiable and $(\mu_{x},\mu_{y})$-convex-concave, then for any
${\bf{z}}_{1}=({\bf{x}}_{1},{\bf{y}}_{1}),{\bf{z}}_{2}=({\bf{x}}_{2},{\bf{y}}_{2})\in{\mathcal{X}}\times{\mathcal{Y}}$,
we have

$\displaystyle\langle{\bf{g}}({\bf{z}}_{1})-{\bf{g}}({\bf{z}}_{2}),{\bf{z}}_{1}-{\bf{z}}_{2}\rangle\geq\mu_{x}\left\|{\bf{x}}_{1}-{\bf{x}}_{2}\right\|_{2}^{2}+\mu_{y}\left\|{\bf{y}}_{1}-{\bf{y}}_{2}\right\|_{2}^{2}.$
(17)

where
$g({\bf{x}},{\bf{y}})=(\nabla_{\bf{x}}f({\bf{x}},{\bf{y}}),-\nabla_{\bf{y}}f({\bf{x}},{\bf{y}}))$.

###### Proof.

According to $f(\cdot,{\bf{y}})$ is $\mu_{x}$-strongly-convex, we have

$\displaystyle f({\bf{x}}_{2},{\bf{y}}_{1})-f({\bf{x}}_{1},{\bf{y}}_{1})$
$\displaystyle\geq\langle\nabla_{{\bf{x}}}f({\bf{x}}_{1},{\bf{y}}_{1}),{\bf{x}}_{2}-{\bf{x}}_{1}\rangle+\frac{\mu_{x}}{2}\left\|{\bf{x}}_{2}-{\bf{x}}_{1}\right\|_{2},$
$\displaystyle f({\bf{x}}_{1},{\bf{y}}_{2})-f({\bf{x}}_{2},{\bf{y}}_{2})$
$\displaystyle\geq\langle\nabla_{{\bf{x}}}f({\bf{x}}_{2},{\bf{y}}_{2}),{\bf{x}}_{1}-{\bf{x}}_{2}\rangle+\frac{\mu_{x}}{2}\left\|{\bf{x}}_{2}-{\bf{x}}_{1}\right\|_{2}.$

Similarly, by strongly-convexity of $-f({\bf{x}},\cdot)$, we have

$\displaystyle-f({\bf{x}}_{1},{\bf{y}}_{2})+f({\bf{x}}_{1},{\bf{y}}_{1})$
$\displaystyle\geq-\langle\nabla_{{\bf{y}}}f({\bf{x}}_{1},{\bf{y}}_{1}),{\bf{y}}_{2}-{\bf{y}}_{1}\rangle+\frac{\mu_{y}}{2}\left\|{\bf{y}}_{2}-{\bf{y}}_{1}\right\|_{2},$
$\displaystyle-f({\bf{x}}_{2},{\bf{y}}_{1})+f({\bf{x}}_{2},{\bf{y}}_{2})$
$\displaystyle\geq-\langle\nabla_{{\bf{y}}}f({\bf{x}}_{2},{\bf{y}}_{2}),{\bf{y}}_{1}-{\bf{y}}_{2}\rangle+\frac{\mu_{y}}{2}\left\|{\bf{y}}_{2}-{\bf{y}}_{1}\right\|_{2}.$

The desired result just follows from adding above four inequalities together.
∎

The following two lemmas show that the relationship between the smoothness of
each component $f_{i}$, the average-smoothness of $\\{f_{i}\\}_{i=1}^{n}$ and
the smoothness of $\frac{1}{n}\sum_{i=1}^{n}f_{i}$.

######  Lemma 11.

Assume that $f_{i}$ is $L_{i}$-smooth, then $\\{f_{i}\\}_{i=1}^{n}$ is
$\sqrt{\frac{1}{n}\sum_{i=1}^{n}L_{i}^{2}}$-average-smooth.

###### Proof.

By the definition of smoothness, we have

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\|f_{i}({\bf{z}}_{1})-f_{i}({\bf{z}}_{2})\right\|_{2}^{2}\leq\frac{1}{n}\sum_{i=1}^{n}L_{i}^{2}\left\|{\bf{z}}_{1}-{\bf{z}}_{2}\right\|_{2}^{2},$

which is our desired result. ∎

######  Lemma 12.

Assume that $\\{f_{i}\\}_{i=1}^{n}$ is $L$-average-smooth, then
$f({\bf{z}})=\frac{1}{n}f_{i}({\bf{z}})$ is $L$-smooth.

###### Proof.

Note that

$\displaystyle\left\|\nabla f({\bf{z}}_{1})-\nabla
f({\bf{z}}_{2})\right\|_{2}$
$\displaystyle=\left\|\frac{1}{n}\sum_{i=1}^{n}(\nabla
f_{i}({\bf{z}}_{1})-\nabla f_{i}({\bf{z}}_{2}))\right\|_{2}$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}({\bf{z}}_{1})-\nabla f_{i}({\bf{z}}_{2})\right\|_{2}$
$\displaystyle\leq\sqrt{\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}({\bf{z}}_{1})-\nabla f_{i}({\bf{z}}_{2})\right\|_{2}^{2}}$
$\displaystyle\leq\sqrt{L^{2}\left\|{\bf{z}}_{1}-{\bf{z}}_{2}\right\|_{2}^{2}}=L\left\|{\bf{z}}_{1}-{\bf{z}}_{2}\right\|_{2},$

where the first inequality is according to triangle inequality, the second
inequality follows from AM-QM inequality, and the last inequality is due to
average-smoothness of $\\{f_{i}\\}_{i=1}^{n}$. ∎

##  Appendix B Proof of Theorem 2

Following proof is adapted from the proof of Theorem 4.9 in [1].

###### Proof.

By Lemma 8, we know that

$\displaystyle\langle{\bf{z}}_{k+1/2}-\bar{{\bf{z}}}_{k}+\tau{\bf{g}}({\bf{w}}_{k}),{\bf{z}}_{k+1}-{\bf{z}}_{k+1/2}\rangle\geq
0,$
$\displaystyle\langle{\bf{z}}_{k+1}-\bar{{\bf{z}}}_{k}+\tau[{\bf{g}}({\bf{w}}_{k})+{\bf{g}}_{i}({\bf{z}}_{k+1/2})-{\bf{g}}_{i}({\bf{w}}_{k})],{\bf{z}}^{*}-{\bf{z}}_{k+1}\rangle\geq
0.$

Summing above two inequalities, we have

$\displaystyle\langle{\bf{z}}_{k+1}-\bar{{\bf{z}}}_{k},{\bf{z}}^{*}-{\bf{z}}_{k+1}\rangle+\langle{\bf{z}}_{k+1/2}-\bar{{\bf{z}}}_{k},{\bf{z}}_{k+1}-{\bf{z}}_{k+1/2}\rangle$
(18)
$\displaystyle+\tau\langle{\bf{g}}({\bf{w}}_{k})+{\bf{g}}_{i}({\bf{z}}_{k+1/2})-{\bf{g}}_{i}({\bf{w}}_{k}),{\bf{z}}^{*}-{\bf{z}}_{k+1/2}\rangle$
$\displaystyle+\tau\langle{\bf{g}}_{i}({\bf{z}}_{k+1/2})-{\bf{g}}_{i}({\bf{w}}_{k}),{\bf{z}}_{k+1/2}-{\bf{z}}_{k+1}\rangle\geq
0.$

Since
$2\langle{\bf{a}},{\bf{b}}\rangle=\left\|{\bf{a}}+{\bf{b}}\right\|_{2}^{2}-\left\|{\bf{a}}\right\|_{2}^{2}-\left\|{\bf{b}}\right\|_{2}^{2}$,
the first term in inequality (18) can be written as

$\displaystyle
2\langle{\bf{z}}_{k+1}-\bar{{\bf{z}}}_{k},{\bf{z}}^{*}-{\bf{z}}_{k+1}\rangle$
(19) $\displaystyle=$ $\displaystyle
2\langle{\bf{z}}_{k+1}-\alpha{\bf{z}}_{k}-(1-\alpha){\bf{w}}_{k},{\bf{z}}^{*}-{\bf{z}}_{k+1}\rangle$
$\displaystyle=$ $\displaystyle
2\alpha\langle{\bf{z}}_{k+1}-{\bf{z}}_{k},{\bf{z}}^{*}-{\bf{z}}_{k+1}\rangle+2(1-\alpha)\langle{\bf{z}}_{k+1}-{\bf{w}}_{k},{\bf{z}}^{*}-{\bf{z}}_{k+1}\rangle$
$\displaystyle=$
$\displaystyle\alpha\big{(}\left\|{\bf{z}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}-\left\|{\bf{z}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}-\left\|{\bf{z}}_{k+1}-{\bf{z}}_{k}\right\|_{2}^{2}\big{)}$
$\displaystyle+(1-\alpha)\big{(}\left\|{\bf{w}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}-\left\|{\bf{z}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}-\left\|{\bf{z}}_{k+1}-{\bf{w}}_{k}\right\|_{2}^{2}\big{)}$
$\displaystyle=$
$\displaystyle\alpha\left\|{\bf{z}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}+(1-\alpha)\left\|{\bf{w}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}-\left\|{\bf{z}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}$
$\displaystyle-\alpha\left\|{\bf{z}}_{k+1}-{\bf{z}}_{k}\right\|_{2}^{2}-(1-\alpha)\left\|{\bf{z}}_{k+1}-{\bf{w}}_{k}\right\|_{2}^{2}.$

Similarly, the second term in inequality (18) can be written as

$\displaystyle
2\langle{\bf{z}}_{k+1/2}-\bar{{\bf{z}}}_{k},{\bf{z}}_{k+1}-{\bf{z}}_{k+1/2}\rangle$
(20) $\displaystyle=$
$\displaystyle\alpha\left\|{\bf{z}}_{k}-{\bf{z}}_{k+1}\right\|_{2}^{2}+(1-\alpha)\left\|{\bf{w}}_{k}-{\bf{z}}_{k+1}\right\|_{2}^{2}-\left\|{\bf{z}}_{k+1/2}-{\bf{z}}_{k+1}\right\|_{2}^{2}$
$\displaystyle-\alpha\left\|{\bf{z}}_{k+1/2}-{\bf{z}}_{k}\right\|_{2}^{2}-(1-\alpha)\left\|{\bf{z}}_{k+1/2}-{\bf{w}}_{k}\right\|_{2}^{2}.$

Using the fact $\mathbb{E}_{k}[{\bf{g}}_{i}({\bf{z}})]={\bf{g}}({\bf{z}})$,
the expectation of third term in inequality (18) can be bounded as

$\displaystyle\quad
2\mathbb{E}_{k}\left[\langle{\bf{g}}({\bf{w}}_{k})+{\bf{g}}_{i}({\bf{z}}_{k+1/2})-{\bf{g}}_{i}({\bf{w}}_{k}),{\bf{z}}^{*}-{\bf{z}}_{k+1/2}\rangle\right]$
(21)
$\displaystyle=2\langle{\bf{g}}({\bf{z}}_{k+1/2}),{\bf{z}}^{*}-{\bf{z}}_{k+1/2}\rangle$
$\displaystyle\leq
2\langle{\bf{g}}({\bf{z}}^{*}),{\bf{z}}^{*}-{\bf{z}}_{k+1/2}\rangle-2\mu\left\|{\bf{z}}_{k+1/2}-{\bf{z}}^{*}\right\|_{2}^{2}$
$\displaystyle\leq-\mu\mathbb{E}_{k}\left[\left\|{\bf{z}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right]+2\mu\mathbb{E}_{k}\left[\left\|{\bf{z}}_{k+1/2}-{\bf{z}}_{k+1}\right\|_{2}^{2}\right],$

where the first inequality follows from Lemma 10, and the last inequality is
according to Lemma 6 and $\left\|{\bf{a}}+{\bf{b}}\right\|_{2}^{2}\leq
2\left\|{\bf{a}}\right\|_{2}^{2}+2\left\|{\bf{b}}\right\|_{2}^{2}$.

Moreover, by Young’s inequality
$2\langle{\bf{a}},{\bf{b}}\rangle\leq\beta\left\|{\bf{a}}\right\|_{2}^{2}+\frac{1}{\beta}\left\|{\bf{b}}\right\|_{2}^{2}$
and $L$-average-smoothness of $\\{f_{i}\\}_{i=1}^{n}$, there holds

$\displaystyle\quad\mathbb{E}_{k}\left[2\tau\langle{\bf{g}}_{i}({\bf{z}}_{k+1/2})-{\bf{g}}_{i}({\bf{w}}_{k}),{\bf{z}}_{k+1/2}-{\bf{z}}_{k+1}\rangle\right]$
(22) $\displaystyle\leq
2\tau^{2}\mathbb{E}_{k}\left[\left\|{\bf{g}}_{i}({\bf{z}}_{k+1/2})-{\bf{g}}_{i}({\bf{w}}_{k})\right\|_{2}^{2}\right]+\frac{1}{2}\mathbb{E}_{k}\left[\left\|{{\bf{z}}_{k+1/2}-{\bf{z}}_{k+1}}\right\|_{2}^{2}\right]$
$\displaystyle\leq
2\tau^{2}L^{2}\left\|{\bf{z}}_{k+1/2}-{\bf{w}}_{k}\right\|_{2}^{2}+\frac{1}{2}\mathbb{E}_{k}\left[\left\|{{\bf{z}}_{k+1/2}-{\bf{z}}_{k+1}}\right\|_{2}^{2}\right].$

Plugging results of (19), (20), (21) and (22) into inequality (18), we obtain
that

$\displaystyle\quad\alpha\left\|{\bf{z}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}+(1-\alpha)\left\|{\bf{w}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}-\mathbb{E}_{k}\left[\left\|{\bf{z}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right]-\mathbb{E}_{k}\left[\left\|{\bf{z}}_{k+1/2}-{\bf{z}}_{k+1}\right\|_{2}^{2}\right]$
$\displaystyle-\alpha\left\|{\bf{z}}_{k+1/2}-{\bf{z}}_{k}\right\|_{2}^{2}-(1-\alpha)\left\|{\bf{z}}_{k+1/2}-{\bf{w}}_{k}\right\|_{2}^{2}$
$\displaystyle-\tau\mu\mathbb{E}_{k}\left[\left\|{\bf{z}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right]+2\tau\mu\mathbb{E}_{k}\left[\left\|{\bf{z}}_{k+1/2}-{\bf{z}}_{k+1}\right\|_{2}^{2}\right]$
$\displaystyle+2\tau^{2}L^{2}\left\|{\bf{z}}_{k+1/2}-{\bf{w}}_{k}\right\|_{2}^{2}+\frac{1}{2}\mathbb{E}_{k}\left[\left\|{{\bf{z}}_{k+1/2}-{\bf{z}}_{k+1}}\right\|_{2}^{2}\right]\geq
0,$

that is

$\displaystyle(1+\tau\mu)\mathbb{E}_{k}\left[\left\|{\bf{z}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right]$
$\displaystyle\leq$
$\displaystyle\alpha\left\|{\bf{z}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}+(1-\alpha)\left\|{\bf{w}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}-\left(\frac{1}{2}-2\tau\mu\right)\mathbb{E}_{k}\left[\left\|{{\bf{z}}_{k+1/2}-{\bf{z}}_{k+1}}\right\|_{2}^{2}\right]$
$\displaystyle-(1-\alpha-2\tau^{2}L^{2})\left\|{\bf{z}}_{k+1/2}-{\bf{w}}_{k}\right\|_{2}^{2}.$

Consequently, with setting $\alpha=1-p$, $p=\frac{1}{2n}$ and
$\tau=\frac{1}{4\sqrt{n}L}$, we know that $\frac{1}{2}-2\tau\mu\geq 0$,
$1-\alpha-2\tau^{2}L^{2}\geq 0$ and

$\displaystyle(1+\tau\mu)\mathbb{E}_{k}\left[\left\|{\bf{z}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right]$
$\displaystyle\leq(1-p)\left\|{\bf{z}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}+p\left\|{\bf{w}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}.$
(23)

On the other hand, by definition of ${\bf{w}}_{k+1}$, we have

$\displaystyle\mathbb{E}_{k}\left[\left\|{\bf{w}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right]=(1-p)\left\|{\bf{w}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}+p\mathbb{E}_{k}\left[\left\|{\bf{z}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right].$
(24)

Following from results of (23) and (24), there holds

$\displaystyle\quad(1+\tau\mu)\mathbb{E}_{k}\left[\left\|{\bf{z}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right]+c\mathbb{E}_{k}\left[\left\|{\bf{w}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right]$
$\displaystyle\leq(1-p)\left\|{\bf{z}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}+p\left\|{\bf{w}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}+c(1-p)\left\|{\bf{w}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}+cp\mathbb{E}_{k}\left[\left\|{\bf{z}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right],$

that is

$\displaystyle\quad(1+\tau\mu-
cp)\mathbb{E}_{k}\left[\left\|{\bf{z}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right]+c\mathbb{E}_{k}\left[\left\|{\bf{w}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right]$
(25)
$\displaystyle\leq(1-p)\left\|{\bf{z}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}+(p+c(1-p))\left\|{\bf{w}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}.$

Letting $c=\frac{2\tau\mu+2p}{\tau\mu+2p}$ and noticing that $\tau\mu<1,p<1$,
we have

$\displaystyle\frac{1-p}{1+\tau\mu-cp}$
$\displaystyle=1-\frac{\tau\mu-p(c-1)}{1+\tau\mu-
cp}=1-\frac{\tau\mu-\frac{p\tau\mu}{\tau\mu+2p}}{1+\tau\mu-p\frac{2\tau\mu+2p}{\tau\mu+2p}}$
$\displaystyle=1-\frac{\tau^{2}\mu^{2}+p\tau\mu}{\tau\mu(1+\tau\mu)+2p(1-p)}$
$\displaystyle\leq 1-\frac{\tau\mu(\tau\mu+p)}{2\tau\mu+2p}\leq
1-\frac{p\tau\mu}{2(\tau\mu+p)}.$

and

$\displaystyle\frac{p+c(1-p)}{c}=1-p\left(1-\frac{\tau\mu+2p}{2\tau\mu+2p}\right)=1-\frac{p\tau\mu}{2(\tau\mu+p)}.$

Together with inequality (25), there holds

$\displaystyle\quad(1+\tau\mu-
cp)\mathbb{E}_{k}\left[\left\|{\bf{z}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right]+c\mathbb{E}_{k}\left[\left\|{\bf{w}}_{k+1}-{\bf{z}}^{*}\right\|_{2}^{2}\right]$
$\displaystyle\leq\left(1-\frac{p\tau\mu}{2(\tau\mu+p)}\right)\left((1+\tau\mu-
cp)\left\|{\bf{z}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}+c\left\|{\bf{w}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}\right),$

which implies that

$\displaystyle\quad\left(\tau\mu+p\right)\mathbb{E}\left[\left\|{\bf{z}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}\right]$
$\displaystyle\leq\left(\tau\mu(1+\tau\mu)+2p(1-p)\right)\mathbb{E}\left[\left\|{\bf{z}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}\right]+2\left(\tau\mu+p\right)\left[\left\|{\bf{w}}_{k}-{\bf{z}}^{*}\right\|_{2}^{2}\right]$
$\displaystyle\leq\left(1-\frac{p\tau\mu}{2(\tau\mu+p)}\right)^{k}\left(\left(\tau\mu(1+\tau\mu)+2p(1-p)\right)\mathbb{E}\left[\left\|{\bf{z}}_{0}-{\bf{z}}^{*}\right\|_{2}^{2}\right]+2\left(\tau\mu+p\right)\left[\left\|{\bf{w}}_{0}-{\bf{z}}^{*}\right\|_{2}^{2}\right]\right)$
$\displaystyle\leq
4\left(\tau\mu+p\right)\left\|{\bf{z}}_{0}-{\bf{z}}^{*}\right\|_{2}^{2}\left(1-\frac{p\tau\mu}{2(\tau\mu+p)}\right)^{k},$

where we have recalled that $2(1-p)\geq 1$ due to
$p=\frac{1}{2n}\leq\frac{1}{2}$ and $\tau\mu<1$.

∎

##  Appendix C Convergence Analysis of AL-SVRE

In this section, we aim to give the convergence rate of AL-SVRE. We first give
the proof of Lemma 1 and establish the connection between the distance to
saddle point and primal-dual gap. Then, we show upper bounds of some auxiliary
quantities, which is useful to the analysis for AL-SVRE. Finally, we provide
the formal proofs of Theorem 3 and Corollary 1.

###  C.1 The proof of Lemma 1

###### Proof.

The definition of $\tilde{\bf{x}}$ means

$\displaystyle\tilde{\bf{x}}=\operatorname*{arg\,min}_{{\bf{x}}\in{\mathcal{X}}}\left(\langle\nabla_{{\bf{x}}}f(\hat{\bf{x}},\hat{\bf{y}}),{\bf{x}}-\hat{\bf{x}}\rangle+\frac{1}{2\eta}\left\|{\bf{x}}-\hat{\bf{x}}\right\|_{2}^{2}\right).$

Therefore, for any ${\bf{x}}\in{\mathcal{X}}$, we have

$\displaystyle\langle\nabla_{{\bf{x}}}f(\hat{\bf{x}},\hat{\bf{y}}),{\bf{x}}-\hat{\bf{x}}\rangle+\frac{1}{2\eta}\left\|{\bf{x}}-\hat{\bf{x}}\right\|_{2}^{2}\geq\langle\nabla_{{\bf{x}}}f(\hat{\bf{x}},\hat{\bf{y}}),\tilde{\bf{x}}-\hat{\bf{x}}\rangle+\frac{1}{2\eta}\left\|\tilde{\bf{x}}-\hat{\bf{x}}\right\|_{2}^{2},$

that is

$\displaystyle\langle\nabla_{{\bf{x}}}f(\hat{\bf{x}},\hat{\bf{y}}),{\bf{x}}-\tilde{\bf{x}}\rangle$
$\displaystyle\geq\frac{1}{2\eta}\left(\left\|\tilde{\bf{x}}-\hat{\bf{x}}\right\|_{2}^{2}-\left\|{\bf{x}}-\hat{\bf{x}}\right\|_{2}^{2}\right)\geq-\frac{1}{2\eta}\left\|{\bf{x}}-\hat{\bf{x}}\right\|_{2}^{2}.$
(26)

Let $\Phi_{f}({\bf{x}})=\max_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}},{\bf{y}})$
and
${\bf{y}}_{f}^{*}({\bf{x}})=\operatorname*{arg\,max}_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}},{\bf{y}})$,
then it holds that

$\displaystyle\begin{split}&\quad\Phi_{f}(\tilde{\bf{x}})-\Phi_{f}({\bf{x}}^{*})\\\
&=\Phi_{f}(\tilde{\bf{x}})-\Phi_{f}(\hat{\bf{x}})-(\Phi_{f}({\bf{x}}^{*})-\Phi_{f}(\hat{\bf{x}}))\\\
&\leq\langle\nabla\Phi_{f}(\hat{\bf{x}}),\tilde{\bf{x}}-\hat{\bf{x}}\rangle+\kappa_{y}L\left\|\tilde{\bf{x}}-\hat{\bf{x}}\right\|_{2}^{2}-\langle\nabla\Phi_{f}(\hat{\bf{x}}),{\bf{x}}^{*}-\hat{\bf{x}}\rangle\\\
&=\langle\nabla_{{\bf{x}}}f(\hat{\bf{x}},{\bf{y}}_{f}^{*}(\hat{\bf{x}})),\tilde{\bf{x}}-{\bf{x}}^{*}\rangle+\kappa_{y}L\left\|\tilde{\bf{x}}-\hat{\bf{x}}\right\|_{2}^{2}\\\
&=\langle\nabla_{{\bf{x}}}f(\hat{\bf{x}},{\bf{y}}_{f}^{*}(\hat{\bf{x}}))-\nabla_{{\bf{x}}}f(\hat{\bf{x}},\hat{\bf{y}}),\tilde{\bf{x}}-{\bf{x}}^{*}\rangle+\langle\nabla_{{\bf{x}}}f(\hat{\bf{x}},\hat{\bf{y}}),\tilde{\bf{x}}-{\bf{x}}^{*}\rangle+\kappa_{y}L\left\|\tilde{\bf{x}}-\hat{\bf{x}}\right\|_{2}^{2}\\\
&\leq
L\left\|\hat{\bf{y}}-{\bf{y}}_{f}^{*}(\hat{\bf{x}})\right\|_{2}\left\|\tilde{\bf{x}}-{\bf{x}}^{*}\right\|_{2}+\frac{1}{2\eta}\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\kappa_{y}L\left\|\tilde{\bf{x}}-\hat{\bf{x}}\right\|_{2}^{2}.\end{split}$
(27)

where the first inequality is according to $\Phi_{f}$ is $2\kappa_{y}L$-smooth
and convex, the last inequality is due to inequality (26) with setting
${\bf{x}}={\bf{x}}^{*}$.

According to the $\left\|{\bf{a}}+{\bf{b}}\right\|_{2}^{2}\leq
2\left\|{\bf{a}}\right\|_{2}^{2}+2\left\|{\bf{b}}\right\|_{2}^{2}$ and the
Lipschitz continuity of ${\bf{y}}_{f}^{*}(\cdot)$ (cf. Lemma 9), we observe
that

$\displaystyle\begin{split}\left\|\hat{\bf{y}}-{\bf{y}}_{f}^{*}(\hat{\bf{x}})\right\|_{2}^{2}&\leq
2\left\|\hat{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}+2\left\|{\bf{y}}^{*}-{\bf{y}}_{f}^{*}(\hat{\bf{x}})\right\|_{2}^{2}\\\
&\leq
2\left\|\hat{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}+2\kappa_{y}^{2}\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}\\\
&\leq 2\kappa_{y}^{2}{\varepsilon}.\end{split}$ (28)

Next, following from optimality of ${\bf{x}}^{*}$ such that
${\bf{x}}^{*}=\operatorname*{arg\,min}_{{\bf{x}}\in{\mathcal{X}}}\Phi_{f}({\bf{x}})$
and Lemma 6, we have

$\displaystyle{\bf{x}}^{*}={\mathcal{P}}_{{\mathcal{X}}}\left({\bf{x}}^{*}-\eta\nabla_{{\bf{x}}}\Phi({\bf{x}}^{*})\right)={\mathcal{P}}_{{\mathcal{X}}}\left({\bf{x}}^{*}-\eta\nabla_{{\bf{x}}}f({\bf{x}}^{*},{\bf{y}}^{*})\right).$

Hence, by smoothness of the function $f$ and Lemma 7, we have

$\displaystyle\begin{split}\left\|\tilde{\bf{x}}-{\bf{x}}^{*}\right\|_{2}&=\left\|{\mathcal{P}}_{{\mathcal{X}}}\left(\hat{\bf{x}}-\eta\nabla_{{\bf{x}}}f(\hat{\bf{x}},\hat{\bf{y}})\right)-{\mathcal{P}}_{{\mathcal{X}}}\left({\bf{x}}^{*}-\eta\nabla_{{\bf{x}}}f({\bf{x}}^{*},{\bf{y}}^{*})\right)\right\|_{2}\\\
&\leq\left\|\hat{\bf{x}}-{\bf{x}}^{*}-\eta\left(\nabla_{{\bf{x}}}f(\hat{\bf{x}},\hat{\bf{y}})-\nabla_{{\bf{x}}}f({\bf{x}}^{*},{\bf{y}}^{*})\right)\right\|_{2}\\\
&\leq\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}+\eta
L\sqrt{\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|\hat{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}}\\\
&\leq(1+\eta L)\sqrt{{\varepsilon}}.\end{split}$ (29)

Consequently, plugging inequalities (28) and (29) into (27) yields that

$\displaystyle\max_{{\bf{y}}\in{\mathcal{Y}}}f(\tilde{\bf{x}},{\bf{y}})-f({\bf{x}}^{*},{\bf{y}}^{*})$
$\displaystyle\leq\sqrt{2}(1+\eta
L)\kappa_{y}L{\varepsilon}+\frac{{\varepsilon}}{2\eta}+2\kappa_{y}L\left(\left\|\tilde{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}\right)$
$\displaystyle\leq\left(\sqrt{2}(1+\eta L)+2(1+\eta
L)^{2}+2\right)\kappa_{y}L{\varepsilon}+\frac{{\varepsilon}}{2\eta}$

Similarly, by definition of $\tilde{\bf{y}}$, we also have

$\displaystyle\left\|\tilde{\bf{y}}-{\bf{y}}^{*}\right\|_{2}$
$\displaystyle=\left\|\hat{\bf{y}}-{\bf{y}}^{*}+\eta\left(\nabla_{{\bf{y}}}f(\hat{\bf{x}},\hat{\bf{y}})-\nabla_{{\bf{y}}}f({\bf{x}}^{*},{\bf{y}}^{*})\right)\right\|_{2},$
(30)

and

$\displaystyle
g({\bf{x}}^{*},{\bf{y}}^{*})-\min_{{\bf{x}}\in{\mathcal{X}}}g({\bf{x}},\tilde{\bf{y}})\leq\left(\sqrt{2}(1+\eta
L)+2(1+\eta
L)^{2}+2\right)\kappa_{x}L{\varepsilon}+\frac{{\varepsilon}}{2\eta}.$

Furthermore, by inequality (29) and (30), we have

$\displaystyle\left\|\tilde{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|\tilde{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}$
$\displaystyle=$
$\displaystyle\left\|{\mathcal{P}}_{\mathcal{X}}\left(\hat{\bf{x}}-\eta\nabla_{{\bf{x}}}f(\hat{\bf{x}},\hat{\bf{y}})\right)-{\mathcal{P}}_{\mathcal{X}}\left({\bf{x}}^{*}-\eta\nabla_{{\bf{x}}}f({\bf{x}}^{*},{\bf{y}}^{*})\right)\right\|_{2}^{2}$
$\displaystyle+\left\|{\mathcal{P}}_{\mathcal{Y}}\left(\hat{\bf{y}}+\eta\nabla_{{\bf{y}}}f(\hat{\bf{x}},\hat{\bf{y}})\right)-{\mathcal{P}}_{\mathcal{Y}}\left({\bf{y}}^{*}+\eta\nabla_{{\bf{y}}}f({\bf{x}}^{*},{\bf{y}}^{*})\right)\right\|_{2}^{2}$
$\displaystyle\leq$ $\displaystyle
2\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+2\left\|\hat{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}+2\eta^{2}\left(\left\|\nabla_{{\bf{x}}}f(\hat{\bf{x}},\hat{\bf{y}})-\nabla_{{\bf{x}}}f({\bf{x}}^{*},{\bf{y}}^{*})\right\|_{2}^{2}+\left\|\nabla_{{\bf{y}}}f(\hat{\bf{x}},\hat{\bf{y}})-\nabla_{{\bf{y}}}f({\bf{x}}^{*},{\bf{y}}^{*})\right\|_{2}^{2}\right)$
$\displaystyle\leq$ $\displaystyle
2{\varepsilon}+2\eta^{2}L^{2}\left(\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|\hat{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}\right)\leq
2(1+\eta^{2}L^{2}){\varepsilon},$ (31)

where the second inequality is according to the smoothness of $f$. ∎

###  C.2 The Proof of Lemma 2

###### Proof.

Following the convexity of function $f(\cdot,{\bf{y}}^{*})$, we know that

$\displaystyle\frac{\mu_{x}}{2}\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}\leq
f(\hat{\bf{x}},{\bf{y}}^{*})-f({\bf{x}}^{*},{\bf{y}}^{*}).$

Similarly, the concavity of function $f({\bf{x}}^{*},\cdot)$ leads to

$\displaystyle\frac{\mu_{y}}{2}\left\|\hat{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}\leq
f({\bf{x}}^{*},{\bf{y}}^{*})-f({\bf{x}}^{*},\hat{\bf{y}}).$

Together with these pieces, it holds that

$\displaystyle\mu_{x}\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\mu_{y}\left\|\hat{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}\leq
2\left(f(\hat{\bf{x}},{\bf{y}}^{*})-f({\bf{x}}^{*},\hat{\bf{y}})\right)\leq
2\left(\max_{{\bf{y}}\in{\mathcal{Y}}}f(\hat{\bf{x}},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},\hat{\bf{y}})\right).$

∎

###  C.3 The Proof of Lemma 3

###### Proof.

It is easy to verify that that $F_{k}$ is $(L+\beta)$-smooth and
$(\mu_{x}+\beta,\mu_{y})$-convex-concave. We will use induction to prove
inequalities (7) to (10) hold for each $k\geq 1$.

We first assume that inequalities (7) to (10) hold for any $k=1,2\dots,K-1$,
then we prove the statements for $k=K$.

#### Part (a): Inequalities (7) and (8) hold for $k=K$.

By definition of $T_{K}$, we know that

$\displaystyle e^{\theta T_{K}}\geq
12\left(\frac{2}{1-\rho}+\frac{1728\beta(L+\beta)(7(L+\beta)+2\sqrt{n}\mu_{y}))}{\mu_{x}\mu_{y}\min\\{\mu_{x},\mu_{y}\\}(1-\rho)^{2}(\sqrt{q}-\rho)^{2}}\right)\triangleq
R,$

where
$\frac{1}{\theta}=4\left(n+\frac{2\sqrt{n}(L+\beta)}{\min\\{\mu_{x}+\beta,\mu_{y}\\}}\right)$.

Let $\\{{\bf{u}}_{K,t},{\bf{v}}_{K,t}\\}_{t\geq 0}$ be the sequence of using
L-SVRE to solve minimax problem

$\displaystyle\min_{{\bf{u}}\in{\mathcal{X}}}\max_{{\bf{v}}\in{\mathcal{Y}}}F_{K}({\bf{u}},{\bf{v}})$

with initial point
$({\bf{u}}_{K,0},{\bf{v}}_{K,0})=({\bf{x}}_{K-1},{\bf{y}}_{K-1})$ and stepsize
$\tau_{K}=\frac{1}{4\sqrt{n}(L+\beta)}$. Based on Theorem 2, we have

$\displaystyle\begin{split}&\quad\mathbb{E}\left[\left\|{\bf{u}}_{K,T_{K}}-{\bf{x}}_{K}^{*}\right\|_{2}^{2}+\left\|{\bf{v}}_{K,T_{K}}-{\bf{y}}_{K}^{*}\right\|_{2}^{2}\right]\\\
&\leq
4\left(1-\theta\right)^{T_{K}}\mathbb{E}\left[\left\|{\bf{x}}_{K-1}-{\bf{x}}_{K}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}_{K-1}-{\bf{y}}_{K}^{*}\right\|_{2}^{2}\right]\\\
&\leq 4e^{-\theta
T_{K}}\mathbb{E}\left[\left\|{\bf{x}}_{K-1}-{\bf{x}}_{K}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}_{K-1}-{\bf{y}}_{K}^{*}\right\|_{2}^{2}\right]\\\
&\leq\frac{4}{R}\mathbb{E}\left[\left\|{\bf{x}}_{K-1}-{\bf{x}}_{K}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}_{K-1}-{\bf{y}}_{K}^{*}\right\|_{2}^{2}\right].\end{split}$
(32)

Note that

$\displaystyle\begin{split}&\quad\mathbb{E}\left[\left\|{\bf{x}}_{K-1}-{\bf{x}}^{*}_{K}\right\|_{2}^{2}+\left\|{\bf{y}}_{k-1}-{\bf{y}}^{*}_{K}\right\|_{2}^{2}\right]\\\
&\leq
2\mathbb{E}\left[\left\|{\bf{x}}_{K-1}-{\bf{x}}^{*}_{K-1}\right\|_{2}^{2}+\left\|{\bf{y}}_{K-1}-{\bf{y}}^{*}_{K-1}\right\|_{2}^{2}\right]+2\mathbb{E}\left[\left\|{\bf{x}}_{K-1}^{*}-{\bf{x}}_{K}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}_{K-1}^{*}-{\bf{y}}_{K}^{*}\right\|_{2}^{2}\right]\\\
&\leq
2{\varepsilon}_{K-1}+\frac{144\beta\delta_{K-3}}{\mu_{x}\min\\{\mu_{x},\mu_{y}\\}},\end{split}$
(33)

where we have used induction hypothesis (7) and (10).

Plugging (33) into (32), we have

$\displaystyle\begin{split}&\quad\mathbb{E}\left[\left\|{\bf{u}}_{K,T_{K}}-{\bf{x}}_{K}^{*}\right\|_{2}^{2}+\left\|{\bf{v}}_{K,T_{K}}-{\bf{y}}_{K}^{*}\right\|_{2}\right]\\\
&\leq\frac{4}{R}\left(2{\varepsilon}_{K-1}+\frac{144\beta\delta_{K-3}}{\mu_{x}\min\\{\mu_{x},\mu_{y}\\}}\right)\\\
&=\frac{4}{R}\left(2{\varepsilon}_{K-1}+\frac{144\beta}{\mu_{x}\min\\{\mu_{x},\mu_{y}\\}}\cdot\frac{8\Delta_{f}(1-\rho)^{K-2}}{(\sqrt{q}-\rho)^{2}}\right)\\\
&=\frac{4}{R}\left(\frac{2}{1-\rho}+\frac{1728\beta(L+\beta)(7(L+\beta)+2\sqrt{n}\mu_{y}))}{\mu_{x}\mu_{y}\min\\{\mu_{x},\mu_{y}\\}(1-\rho)^{2}(\sqrt{q}-\rho)^{2}}\right){\varepsilon}_{K}\leq\frac{1}{3}{\varepsilon}_{K}.\end{split}$
(34)

Consequently, combing inequality (34) with equation (31) in the proof of Lemma
1, we obtain

$\displaystyle\mathbb{E}\left[\left\|{\bf{x}}_{K}-{\bf{x}}^{*}_{K}\right\|_{2}^{2}+\left\|{\bf{y}}_{K}-{\bf{y}}^{*}_{K}\right\|_{2}^{2}\right]\leq\frac{2(1+\tau_{K}^{2}(L+\beta)^{2})}{3}{\varepsilon}_{K}\leq\frac{2(1+1/16)}{3}{\varepsilon}_{K}\leq{\varepsilon}_{K},$

and

$\displaystyle\quad\max_{{\bf{y}}\in{\mathcal{Y}}}F_{K}({\bf{x}}_{K},{\bf{y}})-F_{K}({\bf{x}}_{K}^{*},{\bf{y}}_{K}^{*})$
$\displaystyle\leq\left(\sqrt{2}(1+\tau_{K}(L+\beta))+2(1+\tau_{K}(L+\beta))^{2}+2\right)\frac{(L+\beta)^{2}}{\mu_{y}}\frac{{\varepsilon}_{K}}{3}+\frac{{\varepsilon}_{K}}{6\tau_{K}}$
$\displaystyle\leq\left[\left(\frac{5}{4}\sqrt{2}+\frac{50}{16}+2\right)\frac{(L+\beta)^{2}}{\mu_{y}}+2\sqrt{n}(L+\beta)\right]\frac{{\varepsilon}_{K}}{3}$
$\displaystyle\leq\left(\frac{7(L+\beta)}{\mu_{y}}+2\sqrt{n}\right)(L+\beta)\frac{{\varepsilon}_{K}}{3}$
$\displaystyle=\frac{2\Delta_{f}}{9}(1-\rho)^{K},$

where we have used $\tau_{K}=\frac{1}{4\sqrt{n}(L+\beta)}$ and

$\displaystyle\begin{cases}{\bf{x}}_{K}={\mathcal{P}}_{{\mathcal{X}}}\left({\bf{u}}_{K,T_{K}}-\tau_{K}\nabla_{{\bf{x}}}F_{K}({\bf{u}}_{K,T_{K}},{\bf{v}}_{K,T_{K}})\right)\\\
{\bf{y}}_{K}={\mathcal{P}}_{{\mathcal{Y}}}\left({\bf{v}}_{K,T_{K}}+\tau_{K}\nabla_{{\bf{y}}}F_{K}({\bf{u}}_{K,T_{K}},{\bf{v}}_{K,T_{K}})\right).\end{cases}$

Therefore, we have proved inequalities (7) and (8) hold for $1\leq k\leq K$.

#### Part (b): Inequality (9) holds for $k=K$.

Let
$\Phi({\bf{x}})\triangleq\max_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}},{\bf{y}})$,
and
$\Phi_{k}({\bf{x}})\triangleq\max_{{\bf{y}}\in{\mathcal{Y}}}F_{k}({\bf{x}},{\bf{y}})=\Phi({\bf{x}})+\frac{\beta}{2}\left\|{\bf{x}}-{\bf{u}}_{k-1}\right\|_{2}^{2}$.
It is easy to check that
${\bf{x}}_{k}^{*}=\operatorname*{arg\,min}_{{\bf{x}}\in{\mathcal{X}}}\Phi_{k}({\bf{x}})$
and $\Phi_{k}$ is $\mu_{x}$-strongly convex by Lemma 9.

Part (a) means we have (8) holds for $1\leq k\leq K$, which implies that

$\displaystyle\mathbb{E}\left[\Phi_{k}({\bf{x}}_{k})\right]-\Phi_{k}^{*}\leq\frac{2\Delta_{f}}{9}(1-\rho)^{k},~{}~{}~{}\text{
for }1\leq k\leq K.$

Consequently, according to the analysis of Catalyst for convex minimization
[20]333The original proof of Proposition 5 in Pages 45-46 of [20] should be
slightly modified by employing
$\Phi({\bf{x}}_{0})-\Phi^{*}=\max_{{\bf{y}}}f({\bf{x}}_{0},{\bf{y}})-f({\bf{x}}^{*},{\bf{y}}^{*})\leq\Delta_{f}$.
In fact, this result means inequality (9) also holds for $k=0$., it holds that

$\displaystyle\mathbb{E}\Phi({\bf{x}}_{k})-\Phi^{*}\leq\frac{8\Delta_{f}}{(\sqrt{q}-\rho)^{2}}(1-\rho)^{k+1}=\delta_{k},~{}~{}~{}\text{
for }~{}~{}0\leq k\leq K.$ (35)

Combing above inequality with the strong convexity of $\Phi$, we have

$\displaystyle\frac{\mu_{x}}{2}\
\mathbb{E}\left\|{\bf{x}}_{k}-{\bf{x}}^{*}\right\|_{2}^{2}\leq\mathbb{E}\Phi({\bf{x}}_{k})-\Phi^{*}\leq\delta_{k},~{}~{}~{}\text{
for }~{}~{}0\leq k\leq K.$

#### Part (c): Inequality (10) holds for $k=K$.

For $K\geq 2$, the definition of ${\bf{u}}_{k}$ and $\gamma<1$ means

$\displaystyle\left\|{\bf{u}}_{K-1}-{\bf{u}}_{K}\right\|_{2}$
$\displaystyle=\left\|{\bf{x}}_{K-1}+\gamma({\bf{x}}_{K-1}-{\bf{x}}_{K-2})-{\bf{x}}_{K}-\gamma({\bf{x}}_{K}-{\bf{x}}_{K-1})\right\|_{2}$
$\displaystyle\leq(1+\gamma)\left\|{\bf{x}}_{K}-{\bf{x}}_{K-1}\right\|_{2}+\gamma\left\|{\bf{x}}_{K-1}-{\bf{x}}_{K-2}\right\|_{2}$
$\displaystyle\leq
3\max\\{\left\|{\bf{x}}_{K}-{\bf{x}}_{K-1}\right\|_{2},\left\|{\bf{x}}_{K-1}-{\bf{x}}_{K-2}\right\|_{2}\\}.$

Thus, we have

$\displaystyle\left\|{\bf{u}}_{K-1}-{\bf{u}}_{K}\right\|_{2}^{2}$
$\displaystyle\leq
9\max\\{\left\|{\bf{x}}_{K}-{\bf{x}}_{K-1}\right\|_{2}^{2},\left\|{\bf{x}}_{K-1}-{\bf{x}}_{K-2}\right\|_{2}^{2}\\}$
$\displaystyle\leq
9\max\\{2\left\|{\bf{x}}_{K}-{\bf{x}}^{*}\right\|_{2}^{2}+2\left\|{\bf{x}}_{K-1}-{\bf{x}}^{*}\right\|_{2}^{2},2\left\|{\bf{x}}_{K-1}-{\bf{x}}^{*}\right\|_{2}^{2}+2\left\|{\bf{x}}_{K-2}-{\bf{x}}^{*}\right\|_{2}^{2}\\}$
$\displaystyle\leq
36\max\\{\left\|{\bf{x}}_{K}-{\bf{x}}^{*}\right\|_{2}^{2},\left\|{\bf{x}}_{K-1}-{\bf{x}}^{*}\right\|_{2}^{2},\left\|{\bf{x}}_{K-2}-{\bf{x}}^{*}\right\|_{2}^{2}\\}$
$\displaystyle\leq\frac{72\delta_{K-2}}{\mu_{x}},$

where the last inequality is according to the fact that (9) holds for $0\leq
k\leq K$.

Next, by strong convexity of $F_{K}(\cdot,{\bf{y}}_{K}^{*})$ and
${\bf{x}}_{K}^{*}=\operatorname*{arg\,min}_{{\bf{x}}\in{\mathcal{X}}}F_{K}({\bf{x}},{\bf{y}}_{K}^{*})$,
we have

$\displaystyle\frac{\mu_{x}+\beta}{2}\left\|{\bf{x}}^{*}_{K}-{\bf{x}}^{*}_{K+1}\right\|_{2}^{2}\leq
F_{K}({\bf{x}}_{K+1}^{*},{\bf{y}}_{K}^{*})-F_{K}({\bf{x}}_{K}^{*},{\bf{y}}_{K}^{*}).$

Similarly, by strong concavity of $F_{K}({\bf{x}}_{K}^{*},\cdot)$ and
${\bf{y}}_{K}^{*}=\operatorname*{arg\,max}_{{\bf{y}}\in{\mathcal{Y}}}F_{K}({\bf{x}}_{K}^{*},{\bf{y}})$,
we have

$\displaystyle\frac{\mu_{y}}{2}\left\|{\bf{y}}^{*}_{K}-{\bf{y}}^{*}_{K+1}\right\|_{2}^{2}\leq
F_{K}({\bf{x}}_{K}^{*},{\bf{y}}_{K}^{*})-F_{K}({\bf{x}}_{K}^{*},{\bf{y}}_{K+1}^{*}).$

Therefore, we can conclude that

$\displaystyle\begin{split}&\quad\frac{\mu_{x}+\beta}{2}\left\|{\bf{x}}^{*}_{K}-{\bf{x}}^{*}_{K+1}\right\|_{2}^{2}+\frac{\mu_{y}}{2}\left\|{\bf{y}}^{*}_{K}-{\bf{y}}^{*}_{K+1}\right\|_{2}^{2}\\\
&\leq
F_{K}({\bf{x}}_{K+1}^{*},{\bf{y}}_{K}^{*})-F_{K}({\bf{x}}_{K}^{*},{\bf{y}}_{K+1}^{*})\\\
&=f({\bf{x}}_{K+1}^{*},{\bf{y}}_{K}^{*})+\frac{\beta}{2}\left\|{\bf{x}}_{K+1}^{*}-{\bf{u}}_{K-1}\right\|_{2}^{2}-\left(f({\bf{x}}_{K}^{*},{\bf{y}}_{K+1}^{*})+\frac{\beta}{2}\left\|{\bf{x}}_{K}^{*}-{\bf{u}}_{K-1}\right\|_{2}^{2}\right)\\\
&=f({\bf{x}}_{K+1}^{*},{\bf{y}}_{K}^{*})+\frac{\beta}{2}\left(\left\|{\bf{x}}_{K+1}^{*}-{\bf{u}}_{K}\right\|_{2}^{2}+\left\|{\bf{u}}_{K}-{\bf{u}}_{K-1}\right\|_{2}^{2}+2\langle{\bf{x}}_{K+1}^{*}-{\bf{u}}_{K},{\bf{u}}_{K}-{\bf{u}}_{K-1}\rangle\right)\\\
&-\left(f({\bf{x}}_{K}^{*},{\bf{y}}_{K+1}^{*})+\frac{\beta}{2}\left(\left\|{\bf{x}}_{K}^{*}-{\bf{u}}_{K}\right\|_{2}^{2}+\left\|{\bf{u}}_{K}-{\bf{u}}_{K-1}\right\|_{2}^{2}+2\langle{\bf{x}}_{K}^{*}-{\bf{u}}_{K},{\bf{u}}_{K}-{\bf{u}}_{K-1}\rangle\right)\right)\\\
&=F_{K+1}({\bf{x}}_{K+1}^{*},{\bf{y}}_{K}^{*})-F_{K+1}({\bf{x}}_{K}^{*},{\bf{y}}_{K+1}^{*})+\beta\langle{\bf{x}}_{K+1}^{*}-{\bf{x}}_{K}^{*},{\bf{u}}_{K}-{\bf{u}}_{K-1}\rangle\\\
&\leq\beta\langle{\bf{x}}_{K+1}^{*}-{\bf{x}}_{K}^{*},{\bf{u}}_{K}-{\bf{u}}_{K-1}\rangle\leq\frac{\beta}{2}\left\|{\bf{x}}_{K+1}^{*}-{\bf{x}}_{K}^{*}\right\|_{2}+\frac{\beta}{2}\left\|{\bf{u}}_{K}-{\bf{u}}_{K-1}\right\|_{2}^{2},\end{split}$
(36)

where we have used that $F_{K+1}({\bf{x}}_{K+1}^{*},{\bf{y}}_{K}^{*})\leq
F_{K+1}({\bf{x}}_{K+1}^{*},{\bf{y}}_{K+1}^{*})\leq
F_{K+1}({\bf{x}}_{K}^{*},{\bf{y}}_{K+1}^{*})$. Hence, it holds that

$\displaystyle\mathbb{E}\left[\left\|{\bf{x}}^{*}_{K}-{\bf{x}}^{*}_{K+1}\right\|_{2}^{2}+\left\|{\bf{y}}^{*}_{K}-{\bf{y}}^{*}_{K+1}\right\|_{2}^{2}\right]\leq\frac{\beta}{\min\\{\mu_{x},\mu_{y}\\}}\mathbb{E}\left\|{\bf{u}}_{K}-{\bf{u}}_{K-1}\right\|_{2}^{2}\leq\frac{72\beta\delta_{K-2}}{\mu_{x}\min\\{\mu_{x},\mu_{y}\\}}.$

We also need to show the induction base to finish the proof of inequalities
(7) to (10).

#### Part (d): Induction base.

Finally, we present the induction base that inequalities (7) to (10) hold for
$k=1$.

Since $F_{1}$ is $(\mu_{x}+\beta,\mu_{y})$-convex-concave, we have

$\displaystyle\quad\frac{\mu_{x}+\beta}{2}\left\|{\bf{x}}_{0}-{\bf{x}}_{1}^{*}\right\|_{2}^{2}+\frac{\mu_{y}}{2}\left\|{\bf{y}}_{0}-{\bf{y}}_{1}^{*}\right\|_{2}^{2}$
$\displaystyle\leq
F_{1}({\bf{x}}_{0},{\bf{y}}_{1}^{*})-F_{1}({\bf{x}}_{1}^{*},{\bf{y}}_{1}^{*})+F_{1}({\bf{x}}_{1}^{*},{\bf{y}}_{1}^{*})-F_{1}({\bf{x}}_{1}^{*},{\bf{y}}_{0})$
$\displaystyle=f({\bf{x}}_{0},{\bf{y}}_{1}^{*})-f({\bf{x}}_{1}^{*},{\bf{y}}_{0})-\frac{\beta}{2}\left\|{\bf{x}}_{1}^{*}-{\bf{x}}_{0}\right\|_{2}^{2}$
$\displaystyle\leq\max_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}}_{0},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},{\bf{y}}_{0})=\Delta_{f},$

which implies

$\displaystyle\begin{split}&\mathbb{E}\left[\left\|{\bf{u}}_{1,T_{1}}-{\bf{x}}_{1}^{*}\right\|_{2}^{2}+\left\|{\bf{v}}_{1,T_{1}}-{\bf{y}}_{1}^{*}\right\|_{2}\right]\\\
\leq&4e^{-\theta
T_{1}}\mathbb{E}\left[\left\|{\bf{x}}_{0}-{\bf{x}}_{1}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}_{0}-{\bf{y}}_{1}^{*}\right\|_{2}^{2}\right]\\\
\leq&\frac{4}{R}\frac{2\Delta_{f}}{\min\\{\mu_{x},\mu_{y}\\}}\leq\frac{1}{3}{\varepsilon}_{1}.\end{split}$
(37)

Similar to the proof in Part (a), we can use Lemma 1, 12 and inequality (37)
to show that (7) and (8) hold for $k=1$.

Moreover, according to Proposition 5 in [20] and the strong convexity of
$F_{1}$, we know that (9) holds for $k=1$.

Note that ${\bf{z}}_{1}-{\bf{z}}_{0}=(1+\gamma)({\bf{y}}_{1}-{\bf{y}}_{0})$,
thus we have

$\displaystyle\mathbb{E}\left\|{\bf{u}}_{0}-{\bf{u}}_{1}\right\|_{2}^{2}\leq
4\mathbb{E}\left\|{\bf{x}}_{1}-{\bf{x}}_{0}\right\|_{2}^{2}\leq\frac{32\delta_{0}}{\mu_{x}}\leq\frac{72\delta_{-1}}{\mu_{x}}.$

Therefore, by inequality (36) in Part (c), we have

$\displaystyle\mathbb{E}\left[\left\|{\bf{x}}_{1}^{*}-{\bf{x}}_{2}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}_{1}^{*}-{\bf{y}}_{2}^{*}\right\|_{2}^{2}\right]\leq\frac{\beta}{\min\\{\mu_{x},\mu_{y}\\}}\mathbb{E}\left\|{\bf{u}}_{1}-{\bf{u}}_{0}\right\|_{2}^{2}\leq\frac{72\beta\delta_{-1}}{\mu_{x}\min\\{\mu_{x},\mu_{y}\\}}.$

As a conclusion, we have proved inequalities (7) to (10) hold for any $k\geq
1$.
∎

###  C.4 The proof of Theorem 3

###### Proof.

Consider that the fact

$\displaystyle{\bf{y}}_{k}^{*}=\operatorname*{arg\,max}_{{\bf{y}}\in{\mathcal{Y}}}\left(f({\bf{x}}_{k}^{*},{\bf{y}})+\frac{\beta}{2}\left\|{\bf{x}}_{k}^{*}-{\bf{u}}_{k-1}\right\|_{2}^{2}\right)=\operatorname*{arg\,max}_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}}_{k}^{*},{\bf{y}})={\bf{y}}_{f}^{*}({\bf{x}}_{k}^{*}),$

then we have

$\displaystyle\left\|{\bf{y}}_{k}^{*}-{\bf{y}}^{*}\right\|_{2}=\left\|{\bf{y}}_{f}^{*}({\bf{x}}_{k}^{*})-{\bf{y}}_{f}^{*}({\bf{x}}^{*})\right\|_{2}\leq\kappa_{y}\left\|{\bf{x}}_{k}^{*}-{\bf{x}}^{*}\right\|_{2}$
(38)

by using Lemma 9.

Therefore, we conclude that

$\displaystyle\quad\mathbb{E}\left[\left\|{\bf{u}}_{k,T_{k}}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|{\bf{v}}_{k,T_{k}}-{\bf{y}}^{*}\right\|_{2}^{2}\right]$
$\displaystyle\leq
2\mathbb{E}\left[\left\|{\bf{u}}_{k,T_{k}}-{\bf{x}}_{k}^{*}\right\|_{2}^{2}+\left\|{\bf{v}}_{k,T_{k}}-{\bf{y}}_{k}^{*}\right\|_{2}^{2}\right]+2\mathbb{E}\left[\left\|{\bf{x}}_{k}^{*}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}_{k}^{*}-{\bf{y}}^{*}\right\|_{2}^{2}\right]$
$\displaystyle\leq\frac{2}{3}{\varepsilon}_{k}+2(\kappa_{y}^{2}+1)\mathbb{E}\left\|{\bf{x}}_{k}^{*}-{\bf{x}}^{*}\right\|_{2}^{2}$
$\displaystyle\leq{\varepsilon}_{k}+4(\kappa_{y}^{2}+1)\mathbb{E}\left[\left\|{\bf{x}}_{k}^{*}-{\bf{x}}_{k}\right\|_{2}^{2}+\left\|{\bf{x}}_{k}-{\bf{x}}^{*}\right\|_{2}^{2}\right]$
$\displaystyle\leq{\varepsilon}_{k}+4(\kappa_{y}^{2}+1)\left({\varepsilon}_{k}+\frac{2\delta_{k}}{\mu_{x}}\right)\triangleq\hat{\varepsilon},$

where the second inequality is due to (34) and (38) and the last one is
according to (7) and (9).

Note that

$\displaystyle{\bf{y}}_{k}={\mathcal{P}}_{{\mathcal{Y}}}\left({\bf{v}}_{k,T_{k}}+\tau_{k}\nabla_{{\bf{y}}}F_{k}({\bf{u}}_{k,T_{k}},{\bf{v}}_{k,T_{k}})\right)={\mathcal{P}}_{{\mathcal{Y}}}\left({\bf{v}}_{k,T_{k}}+\tau_{k}\nabla_{{\bf{y}}}f({\bf{u}}_{k,T_{k}},{\bf{v}}_{k,T_{k}})\right).$

Then, Lemma 1 and 12 implies

$\displaystyle\quad\mathbb{E}\left[f({\bf{x}}^{*},{\bf{y}}^{*})-\min_{{\bf{x}}\in{\mathcal{X}}}g({\bf{x}},{\bf{y}}_{k})\right]$
$\displaystyle\leq$
$\displaystyle\left(\sqrt{2}\left(1+\frac{L}{4\sqrt{n}(L+\beta)}\right)+2\left(1+\frac{L}{4\sqrt{n}(L+\beta)}\right)^{2}+2\right)\kappa_{x}L\hat{\varepsilon}+2\sqrt{n}(L+\beta)\hat{\varepsilon}$
$\displaystyle\leq
7\kappa_{x}L\hat{\varepsilon}+2\sqrt{n}(L+\beta)\hat{\varepsilon}\leq\left(7\kappa_{x}L+2\sqrt{n}(L+\beta)\right)\left((4\kappa_{y}^{2}+5){\varepsilon}_{k}+\frac{8(\kappa_{y}^{2}+1)}{\mu_{x}}\delta_{k}\right)$
$\displaystyle\leq\left(7\kappa_{x}L+2\sqrt{n}(L+\beta)\right)\left(\frac{2\Delta_{f}(4\kappa_{y}^{2}+5)\mu_{y}}{3(L+\beta)(7(L+\beta)+2\sqrt{n}\mu_{y})}+\frac{64\Delta_{f}(\kappa_{y}^{2}+1)(1-\rho)}{\mu_{x}(\sqrt{q}-\rho)^{2}}\right)(1-\rho)^{k}$
$\displaystyle\leq\left(\frac{2(4\kappa_{y}^{2}+5)(\mu_{x}+\mu_{y})}{3\mu_{x}}+\frac{128\kappa_{y}^{2}\left(7\kappa_{x}L+2\sqrt{n}(L+\beta)\right)}{\mu_{x}(\sqrt{q}-\rho)^{2}}\right)\Delta_{f}(1-\rho)^{k}$

Together with inequality (35), we obtain that

$\displaystyle\quad\mathbb{E}\left[\max_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}}_{k},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},{\bf{y}}_{k})\right]$
$\displaystyle\leq\Delta_{f}(1-\rho)^{k}\left(\frac{2(4\kappa_{y}^{2}+5)(\mu_{x}+\mu_{y})}{3\mu_{x}}+\frac{128\kappa_{y}^{2}\left(7\kappa_{x}L+2\sqrt{n}(L+\beta)\right)}{\mu_{x}(\sqrt{q}-\rho)^{2}}+\frac{8}{(\sqrt{q}-\rho)^{2}}\right)$
$\displaystyle\leq\Delta_{f}(1-\rho)^{k}\left(12\kappa_{y}^{2}\kappa_{x}+\frac{128\kappa_{y}^{2}\left(7\kappa_{x}L+2\sqrt{n}(L+\beta)\right)}{\mu_{x}(\sqrt{q}-\rho)^{2}}+\frac{8}{(\sqrt{q}-\rho)^{2}}\right)$
$\displaystyle\leq\frac{916\Delta_{f}\left(\kappa_{x}L+\sqrt{n}(L+\beta)\right)\kappa_{y}^{2}}{\mu_{x}(\sqrt{q}-\rho)^{2}}(1-\rho)^{k}.$

∎

###  C.5 The Proof of Corollary 1

###### Proof.

First, note that
$\beta=\min\\{\mu_{y}-\mu_{x},\max\\{L/\sqrt{n}-\mu_{x},0\\}\\}\leq\mu_{y}-\mu_{x}\leq
L$ and

$\displaystyle\frac{1}{q}=\frac{\mu_{x}+\beta}{\mu_{x}}\leq\frac{\mu_{y}}{\mu_{x}}.$

Together with Theorem 3, we have

$\displaystyle\quad\mathbb{E}\left[\max_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}}_{K},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},{\bf{y}}_{K})\right]\leq
e^{-\rho
K}\frac{916\Delta_{f}\left(\kappa_{x}L+\sqrt{n}(L+\beta)\right)\kappa_{y}^{2}}{\mu_{x}(\sqrt{q}-\rho)^{2}}$
$\displaystyle\leq e^{-\rho
K}\left(\frac{2748\sqrt{n}\Delta_{f}\kappa_{y}^{2}\kappa_{x}^{2}}{(\sqrt{q}-\rho)^{2}}\right)\leq
e^{-\rho
K}\left(10992\sqrt{n}\Delta_{f}\kappa_{y}\kappa_{x}^{3}\right)\leq{\varepsilon},$

where we use that $\rho=0.5\sqrt{q}$.

Recall that

$\displaystyle T_{k}$ $\displaystyle=$ $\displaystyle\left\lceil
4\left(n+\frac{2\sqrt{n}(L+\beta)}{\min\\{\mu_{x}+\beta,\mu_{y}\\}}\right)\log\left(12\left(\frac{2}{1-\rho}+\frac{1728\beta(L+\beta)(7(L+\beta)+2\sqrt{n}\mu_{y}))}{\mu_{x}\mu_{y}\min\\{\mu_{x},\mu_{y}\\}(1-\rho)^{2}(\sqrt{q}-\rho)^{2}}\right)\right)\right\rceil$
$\displaystyle\leq$ $\displaystyle\left\lceil
4\left(n+\frac{4\sqrt{n}L}{\min\\{\mu_{x}+\beta,\mu_{y}\\}}\right)\log\left(12\left(4+\frac{884736\sqrt{n}L^{3})}{\mu_{x}^{2}\mu_{y}q}\right)\right)\right\rceil$
$\displaystyle\leq$ $\displaystyle\left\lceil
4\left(n+\frac{4\sqrt{n}L}{\min\\{\mu_{x}+\beta,\mu_{y}\\}}\right)\log\left(10616880\sqrt{n}\kappa_{x}^{3}\right)\right\rceil,$

where we have noticed that $\rho\leq 0.5$.

Therefore, the total SFO complexity of AL-SVRE is

$\displaystyle\sum_{k=1}^{K}(T_{k}+n)={\mathcal{O}}\left(\left(\frac{2n}{\sqrt{q}}+\frac{2}{\sqrt{q}}\left(n+\frac{4\sqrt{n}L}{\min\\{\mu_{x}+\beta,\mu_{y}\\}}\right)\log(\sqrt{n}\kappa_{x}^{3})\right)\log(\sqrt{n}\Delta_{f}\kappa_{y}\kappa_{x}^{3}/{\varepsilon})\right).$

Observe that

  1. 1.

if $\kappa_{y}\geq\sqrt{n}$, we have $\mu_{y}\leq L/\sqrt{n}$,
$\beta=\mu_{y}-\mu_{x}$, which means

$\displaystyle\frac{n}{\sqrt{q}}$
$\displaystyle=n\sqrt{\frac{\mu_{y}}{\mu_{x}}}\leq n^{3/4}\sqrt{\kappa_{x}}$

and

$\displaystyle\frac{1}{\sqrt{q}}\cdot\frac{\sqrt{n}L}{\min\\{\mu_{x}+\beta,\mu_{y}\\}}$
$\displaystyle=\frac{\sqrt{n}L}{\mu_{y}}\sqrt{\frac{\mu_{y}}{\mu_{x}}}=\sqrt{n}\sqrt{\kappa_{x}\kappa_{y}};$

  2. 2.

if $\kappa_{x}>\sqrt{n}>\kappa_{y}$, we have $\beta=L/\sqrt{n}-\mu_{x}$,
$\mu_{x}+\beta=L/\sqrt{n}<\mu_{y}$ , which means

$\displaystyle\frac{n}{\sqrt{q}}$
$\displaystyle=n\sqrt{\frac{L}{\sqrt{n}\mu_{x}}}=n^{3/4}\sqrt{\kappa_{x}}$

and

$\displaystyle\frac{1}{\sqrt{q}}\cdot\frac{\sqrt{n}L}{\min\\{\mu_{x}+\beta,\mu_{y}\\}}$
$\displaystyle=\frac{\sqrt{n}L}{L/\sqrt{n}}\sqrt{\frac{L}{\sqrt{n}\mu_{x}}}=n^{3/4}\sqrt{\kappa_{x}};$

  3. 3.

if $\sqrt{n}\geq\kappa_{x}$, we have $\beta=0$, which means

$\displaystyle\frac{n}{\sqrt{q}}=n\quad\text{and}\quad\frac{1}{\sqrt{q}}\cdot\frac{\sqrt{n}L}{\min\\{\mu_{x}+\beta,\mu_{y}\\}}=\sqrt{n}\kappa_{x}\leq
n.$

Hence, we can conclude that the total SFO complexity of AL-SVRE is

$\displaystyle\sum_{k=1}^{K}(T_{k}+n)={\mathcal{O}}\left(\sqrt{n}\sqrt{(\sqrt{n}+\kappa_{x})(\sqrt{n}+\kappa_{y})}\log(\sqrt{n}\kappa_{x}^{3})\log(\sqrt{n}\Delta_{f}\kappa_{y}\kappa_{x}^{3}/{\varepsilon})\right).$

∎

##  Appendix D The Proof of Theorem 1

The construction for the lower bound in Theorem 1 follows from the idea of
“zero-chain” property [42, 13]. Since we focus on SFO algorithm without
proximal operator, our analysis is simpler than Han et al. [13] and Xie et al.
[37]’s.

Without loss of generality, we assume that the SFO algorithm starts iteration
at $({\bf{x}}^{(0)},{\bf{y}}^{(0)})=({\bf{0}}_{d_{x}},{\bf{0}}_{d_{y}})$.
Otherwise, we can take the objective function

$\displaystyle\hat{f}({\bf{x}},{\bf{y}})=\frac{1}{n}\sum_{i=1}^{n}f_{i}({\bf{x}}+{\bf{x}}^{(0)},{\bf{y}}+{\bf{y}}^{(0)})$

into consideration.

Consider following function
$H:{\mathbb{R}}^{d}\times{\mathbb{R}}^{d}\to{\mathbb{R}}$ defined as

$\displaystyle
H({\bf{x}},{\bf{y}};\alpha,d)=\frac{\alpha}{2}\left\|{\bf{x}}\right\|_{2}^{2}+{\bf{x}}^{\top}({\bf
B}{\bf{y}}-{\bf{c}})-\frac{\alpha}{2}\left\|{\bf{y}}\right\|_{2}^{2},$ (39)

where

$\displaystyle{\bf B}=\begin{bmatrix}1&&&&\\\ -1&1&&&\\\ &\ddots&\ddots&&\\\
&&-1&1&\\\ &&&-1&\sqrt{\alpha\omega}\end{bmatrix}\in{\mathbb{R}}^{d\times d},$

${\bf{c}}=\left(\omega,0,0,\dots,0\right)^{\top}$ and
$\omega=\frac{\sqrt{\alpha^{2}+4}-\alpha}{2}$.

Furthermore, we define subspaces as follows

$\displaystyle{\mathcal{F}}_{k}=\begin{cases}\operatorname{span}\\{{\bf{e}}_{1},{\bf{e}}_{2},\dots,{\bf{e}}_{k}\\},&k=1,\dots,d,\\\\[2.84544pt]
\\{{\bf{0}}_{d}\\},&k=0,\end{cases}$

where $\\{{\bf{e}}_{1},\dots,{\bf{e}}_{d}\\}$ is the standard basis of
${\mathbb{R}}^{d}$.

Here, we state some properties of the Function $H$ in the above definition.

######  Lemma 13.

For the function $H$ defined in Equation (39), following properties hold.

  1. 1.

$H$ is $\sqrt{8+2\alpha^{2}}$-smooth.

  2. 2.

The saddle point of function $H$ is

$\displaystyle\begin{cases}{\bf{x}}^{*}=(q,q^{2},\dots,q^{d})^{\top},\\\
{\bf{y}}^{*}=\omega\left(q,q^{2},\dots,q^{d-1},\frac{1}{\sqrt{1-q}}q^{d}\right)^{\top},\end{cases}$

where $q=\frac{2+\alpha^{2}-\alpha\sqrt{\alpha^{2}+4}}{2}$.

  3. 3.

For $k<d$, if
$({\bf{x}},{\bf{y}})\in{\mathcal{F}}_{k}\times{\mathcal{F}}_{k}$, then
$(\nabla_{{\bf{x}}}H({\bf{x}},{\bf{y}}),\nabla_{{\bf{y}}}H({\bf{x}},{\bf{y}}))\in{\mathcal{F}}_{k+1}\times{\mathcal{F}}_{k+1}.$

  4. 4.

For $k\leq d/2$ and
$({\bf{x}},{\bf{y}})\in{\mathcal{F}}_{k}\times{\mathcal{F}}_{k}$, we have

$\displaystyle\frac{\left\|{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}}{\left\|{\bf{x}}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}^{*}\right\|_{2}^{2}}\geq\frac{1}{2}q^{2k}.$

###### Proof.

1\. Note that $\alpha\omega=\frac{2\alpha}{\sqrt{\alpha^{2}+4}+\alpha}<1$.
Hence $\left\|{\bf B}\right\|_{2}\leq\left\|{\bf B}\right\|_{1}=2$.
Then for any
$({\bf{x}}_{1},{\bf{y}}_{1}),({\bf{x}}_{2},{\bf{y}}_{2})\in{\mathbb{R}}^{d}\times{\mathbb{R}}^{d}$,
we have

$\displaystyle\quad\left\|\begin{bmatrix}\nabla_{{\bf{x}}}H({\bf{x}}_{1},{\bf{y}}_{1})-\nabla_{{\bf{x}}}H({\bf{x}}_{2},{\bf{y}}_{2})\\\
\nabla_{{\bf{y}}}H({\bf{x}}_{1},{\bf{y}}_{1})-\nabla_{{\bf{y}}}H({\bf{x}}_{2},{\bf{y}}_{2})\end{bmatrix}\right\|_{2}^{2}=\left\|\begin{bmatrix}\alpha({\bf{x}}_{1}-{\bf{x}}_{2})+{\bf
B}({\bf{y}}_{1}-{\bf{y}}_{2})\\\ {\bf
B}^{\top}({\bf{x}}_{1}-{\bf{x}}_{2})-\alpha({\bf{y}}_{1}-{\bf{y}}_{2})\end{bmatrix}\right\|_{2}^{2}$
$\displaystyle\leq
2\alpha^{2}\left\|{\bf{x}}_{1}-{\bf{x}}_{2}\right\|_{2}^{2}+2\left\|{\bf
B}\right\|_{2}^{2}\left\|{\bf{y}}_{1}-{\bf{y}}_{2}\right\|_{2}^{2}+2\left\|{\bf
B}\right\|_{2}^{2}\left\|{\bf{x}}_{1}-{\bf{x}}_{2}\right\|_{2}^{2}+2\alpha^{2}\left\|{\bf{y}}_{1}-{\bf{y}}_{2}\right\|_{2}^{2}$
$\displaystyle\leq(8+2\alpha^{2})\left(\left\|{\bf{x}}_{1}-{\bf{x}}_{2}\right\|_{2}^{2}+\left\|{\bf{y}}_{1}-{\bf{y}}_{2}\right\|_{2}^{2}\right),$

where the first inequality is according to
$\left\|{\bf{a}}+{\bf{b}}\right\|_{2}^{2}\leq
2\left\|{\bf{a}}\right\|_{2}^{2}+2\left\|{\bf{b}}\right\|_{2}^{2}$.

2\. Letting the gradient of $H$ equal to zero, we get that

$\displaystyle\nabla_{{\bf{x}}}H({\bf{x}},{\bf{y}})$
$\displaystyle=\alpha{\bf{x}}+{\bf B}{\bf{y}}-{\bf{c}}=0,$
$\displaystyle\nabla_{{\bf{y}}}H({\bf{x}},{\bf{y}})$ $\displaystyle={\bf
B}^{\top}{\bf{x}}-\alpha{\bf{y}}=0.$

Hence, the saddle point of $H$ satisfies

$\displaystyle{\bf{y}}^{*}=\frac{1}{\alpha}{\bf B}^{\top}{\bf{x}}^{*},$ (40)
$\displaystyle\left(\alpha^{2}I+{\bf B}{\bf
B}^{\top}\right){\bf{x}}^{*}=\alpha{\bf{c}}.$ (41)

Equation (41) are equivalent to

$\displaystyle\begin{bmatrix}1+\alpha^{2}&-1&&&\\\ -1&2+\alpha^{2}&-1&&\\\
&\ddots&\ddots&\ddots&\\\ &&-1&2+\alpha^{2}&-1\\\
&&&-1&1+\alpha\omega+\alpha^{2}\end{bmatrix}{\bf{x}}^{*}=\begin{bmatrix}\alpha\omega\\\
0\\\ \vdots\\\ 0\\\ 0\end{bmatrix}.$

Note that $q$ is a root of the equation $s^{2}-(2+\alpha^{2})s+1=0$, then we
have

$\displaystyle(1+\alpha^{2})q-q^{2}$
$\displaystyle=1-q=\frac{\alpha\sqrt{\alpha^{2}+4}-\alpha^{2}}{2}=\alpha\omega,$
$\displaystyle-q^{d-1}+(1+\alpha\omega+\alpha^{2})q^{d}$
$\displaystyle=q^{d-1}\left(-1+(2+\alpha^{2})q-q+\alpha\omega q\right)$
$\displaystyle=q^{d-1}\left(-1+(2+\alpha^{2})q-q+(1-q)q\right)=0,$

and

$\displaystyle-q^{k}+(2+\alpha^{2})q^{k+1}-q^{k+2}$
$\displaystyle=0,~{}~{}~{}\text{ for }k=1,2,\dots,d-2,$

which implies the solution to Equation (41) is
${\bf{x}}^{*}=(q,q^{2},\dots,q^{d})^{\top}$. Additionally, we have

$\displaystyle{\bf{y}}^{*}=\frac{1}{\alpha}{\bf
B}^{\top}{\bf{x}}^{*}=\omega\left(q,q^{2},\dots,q^{d-1},\frac{1}{\sqrt{1-q}}q^{d}\right)^{\top},$

where we have used that $\alpha\omega=1-q$.

3\. For $({\bf{x}},{\bf{y}})\in{\mathcal{F}}_{k}$ for $k<d$, note that

$\displaystyle{\bf{c}}\in{\mathcal{F}}_{1}\subseteq{\mathcal{F}}_{k+1},~{}~{}{\bf
B}{\bf{y}}\in{\mathcal{F}}_{k+1},~{}~{}{\bf
B}^{\top}{\bf{x}}\in{\mathcal{F}}_{k+1}.$

Therefore we have
$\nabla_{{\bf{x}}}H({\bf{x}},{\bf{y}}),\nabla_{{\bf{y}}}H({\bf{x}},{\bf{y}})\in{\mathcal{F}}_{k+1}$.

4\. For $({\bf{x}},{\bf{y}})\in{\mathcal{F}}_{k}$, we have
$x_{k+1}=\dots=x_{d}=y_{k+1}=\dots=y_{d}=0$ and

$\displaystyle\left\|{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}$
$\displaystyle\geq\sum_{i=k+1}^{d}q^{2i}+\omega^{2}\sum_{i=k+1}^{d-1}q^{2i}+\frac{\omega^{2}}{1-q}q^{2d}$
$\displaystyle=(1+\omega^{2})\frac{q^{2(k+1)}(1-q^{2(d-k)})}{1-q^{2}}+\frac{\omega^{2}q}{1-q}q^{2d}.$

Consequently, there holds

$\displaystyle\frac{\left\|{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}}{\left\|{\bf{x}}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}^{*}\right\|_{2}^{2}}$
$\displaystyle\geq\frac{(1+\omega^{2})\frac{q^{2(k+1)}(1-q^{2(d-k)})}{1-q^{2}}+\frac{\omega^{2}q}{1-q}q^{2d}}{(1+\omega^{2})\frac{q^{2}(1-q^{2d})}{1-q^{2}}+\frac{\omega^{2}q}{1-q}q^{2d}}$
$\displaystyle\geq\frac{q^{2k}(1-q^{2(d-k)})}{1-q^{2d}}$
$\displaystyle\geq\frac{q^{2k}(1-q^{2(d-k)})}{1-(2q^{d}-1)}$
$\displaystyle=\frac{1}{2}q^{2k}\frac{1-q^{2(d-k)}}{1-q^{d}}\geq\frac{1}{2}q^{2k},$

where we have used that $1+q^{2d}\geq 2q^{d}$ and $2(d-k)\geq d$ according to
$k\leq d/2$. ∎

With these pieces in hand, we now construct our adversary problem as follows:

$\displaystyle\min_{{\bf{x}}}\max_{{\bf{y}}}f({\bf{x}},{\bf{y}};\alpha,\lambda,d)\triangleq\frac{1}{n}\sum_{i=1}^{n}f_{i}({\bf{x}},{\bf{y}};\alpha,\lambda,d)=\frac{1}{n}\sum_{i=1}^{n}\lambda
H({\bf U}_{i}{\bf{x}},{\bf U}_{i}{\bf{y}}),$ (42)

where $f:{\mathbb{R}}^{nd}\times{\mathbb{R}}^{nd}\to{\mathbb{R}}$, and
matrices ${\bf U}_{1},\dots,{\bf U}_{n}\in{\mathbb{R}}^{d\times nd}$ consist a
partition of the identity matrix of order $nd$ such that ${\bf I}=[{\bf
U}_{1}^{\top},\cdots,{\bf U}_{n}^{\top}]$. The trick of constructing worse
objective function for SFO algorithms by matrices ${\bf
U}_{1}^{\top},\cdots,{\bf U}_{n}^{\top}$ also can be found in the analysis for
minimization problem [19, 43].

The smoothness, convexity and concavity of $f$ can be characterized as
follows.

######  Lemma 14.

The class of functions $\\{f_{i}\\}$ defined in equation (42) is
$\lambda\sqrt{\frac{8+2\alpha^{2}}{n}}$-average-smooth; and the function $f$
is $(\frac{\lambda\alpha}{n},\frac{\lambda\alpha}{n})$-convex-concave.

###### Proof.

Using the fact $\sum_{i=1}^{n}\left\|{\bf
U}_{i}{\bf{x}}\right\|_{2}^{2}=\left\|{\bf{x}}\right\|_{2}^{2}$, we have

$\displaystyle
f({\bf{x}},{\bf{y}})=\frac{\lambda\alpha}{n}\left\|{\bf{x}}\right\|_{2}^{2}-\frac{\lambda}{n}{\bf{x}}^{\top}\left(\sum_{i=1}^{n}{\bf
U}_{i}^{\top}{\bf{c}}\right)+\frac{\lambda}{n}{\bf{x}}^{\top}\left(\sum_{i=1}^{n}{\bf
U}_{i}^{\top}{\bf B}{\bf
U}_{i}\right){\bf{y}}-\frac{\lambda\alpha}{n}\left\|{\bf{y}}\right\|_{2}^{2}.$

It is clear that $f$ is
$(\frac{\lambda\alpha}{n},\frac{\lambda\alpha}{n})$-convex-concave.

Moreover, for any
$({\bf{x}}_{1},{\bf{y}}_{1}),({\bf{x}}_{2},{\bf{y}}_{2})\in{\mathbb{R}}^{nd}\times{\mathbb{R}}^{nd}$,
it holds that

$\displaystyle\quad\frac{1}{n}\sum_{i=1}^{n}\left(\left\|\nabla_{{\bf{x}}}f_{i}({\bf{x}}_{1},{\bf{y}}_{1})-\nabla_{{\bf{x}}}f_{i}({\bf{x}}_{2},{\bf{y}}_{2})\right\|_{2}^{2}+\left\|\nabla_{{\bf{y}}}f_{i}({\bf{x}}_{1},{\bf{y}}_{1})-\nabla_{{\bf{y}}}f_{i}({\bf{x}}_{2},{\bf{y}}_{2})\right\|_{2}^{2}\right)$
$\displaystyle=\frac{\lambda^{2}}{n}\sum_{i=1}^{n}\bigg{(}\left\|{\bf
U}_{i}^{\top}\left(\nabla_{{\bf{x}}}H({\bf U}_{i}{\bf{x}}_{1},{\bf
U}_{i}{\bf{y}}_{1})-\nabla_{{\bf{x}}}H({\bf U}_{i}{\bf{x}}_{2},{\bf
U}_{i}{\bf{y}}_{2})\right)\right\|_{2}^{2}$
$\displaystyle\quad\quad\quad\quad\quad+\left\|{\bf
U}_{i}^{\top}\left(\nabla_{{\bf{y}}}H({\bf U}_{i}{\bf{x}}_{1},{\bf
U}_{i}{\bf{y}}_{1})-\nabla_{{\bf{y}}}H({\bf U}_{i}{\bf{x}}_{2},{\bf
U}_{i}{\bf{y}}_{2})\right)\right\|_{2}^{2}\bigg{)}$
$\displaystyle=\frac{\lambda^{2}}{n}\sum_{i=1}^{n}\bigg{(}\left\|\nabla_{{\bf{x}}}H({\bf
U}_{i}{\bf{x}}_{1},{\bf U}_{i}{\bf{y}}_{1})-\nabla_{{\bf{x}}}H({\bf
U}_{i}{\bf{x}}_{2},{\bf
U}_{i}{\bf{y}}_{2})\right\|_{2}^{2}+\left\|\nabla_{{\bf{y}}}H({\bf
U}_{i}{\bf{x}}_{1},{\bf U}_{i}{\bf{y}}_{1})-\nabla_{{\bf{y}}}H({\bf
U}_{i}{\bf{x}}_{2},{\bf U}_{i}{\bf{y}}_{2})\right\|_{2}^{2}\bigg{)}$
$\displaystyle\leq\frac{\lambda^{2}(8+2\alpha^{2})}{n}\sum_{i=1}^{n}\bigg{(}\left\|{\bf
U}_{i}({\bf{x}}_{1}-{\bf{x}}_{2})\right\|_{2}^{2}+\left\|{\bf
U}_{i}({\bf{y}}_{1}-{\bf{y}}_{2})\right\|_{2}^{2}\bigg{)}$
$\displaystyle=\frac{\lambda^{2}(8+2\alpha^{2})}{n}\left(\left\|{\bf{x}}_{1}-{\bf{x}}_{2}\right\|_{2}^{2}+\left\|{\bf{y}}_{1}-{\bf{y}}_{2}\right\|_{2}^{2}\right),$

where the first inequality follows from smoothness of $H$ (cf. Property 1 in
Lemma 13). ∎

Each component function $f_{i}$ has “zero-chain” property for stochastic
first-order oracle. That is, the information provided by an SFO call at the
current point $({\bf{x}},{\bf{y}})$ can at most increase the dimension of the
linear space which contains $({\bf{x}},{\bf{y}})$ by 1. We present the formal
statement in Lemma 15.

######  Lemma 15.

Let $({\bf{x}}^{(t)},{\bf{y}}^{(t)})$ be the point obtained by an SFO
algorithm ${\mathcal{A}}$ at time-step $t$ and denote
$k^{(t)}_{i}\triangleq|\\{s\leq t:i_{s}=i\\}|$. Then there holds

$\displaystyle{\bf U}_{i}{\bf{x}}^{(t)},{\bf
U}_{i}{\bf{y}}^{(t)}\in{\mathcal{F}}_{k^{(t)}_{i}},~{}~{}~{}\text{ for }t\geq
0,i=1,\dots,n.$ (43)

###### Proof.

For $t=0$, Equation (43) holds apparently by
${\bf{x}}^{(0)}={\bf{y}}^{(0)}={\bf{0}}$.

Now we suppose Equation (43) holds for $t<T$. It is easily to check that
$k_{i}^{(T)}=k_{i}^{(T-1)}$ for $i\neq i_{T}$ and
$k_{i_{T}}^{(T)}=k_{i_{T}}^{(T-1)}+1$.

Observe that for $i\neq i_{T}$ we have

$\displaystyle{\bf
U}_{i}\nabla_{{\bf{x}}}f_{i_{T}}({\bf{x}},{\bf{y}})=\lambda{\bf U}_{i}{\bf
U}_{i_{T}}^{\top}\nabla_{{\bf{x}}}H({\bf U}_{i_{T}}{\bf{x}},{\bf
U}_{i_{T}}{\bf{y}})={\bf{0}},$

which implies

$\displaystyle{\bf U}_{i}{\bf{x}}^{(T)}$
$\displaystyle\in\operatorname{span}\big{\\{}{\bf
U}_{i}{\bf{x}}^{(0)},\dots,{\bf U}_{i}{\bf{x}}^{(T-1)},{\bf
U}_{i}\nabla_{{\bf{x}}}f_{i_{T}}({\bf{x}}^{(0)},{\bf{y}}^{(0)}),\dots,{\bf
U}_{i}\nabla_{{\bf{x}}}f_{i_{T}}({\bf{x}}^{(T-1)},{\bf{y}}^{(T-1)})\big{\\}}$
$\displaystyle=\operatorname{span}\big{\\{}{\bf
U}_{i}{\bf{x}}^{(0)},\dots,{\bf
U}_{i}{\bf{x}}^{(T-1)}\big{\\}}\subseteq{\mathcal{F}}_{k_{i}^{(T-1)}}={\mathcal{F}}_{k_{i}^{(T)}}.$

Next, Following from Property 3 in Lemma 13, we know that for $t\leq T-1$

$\displaystyle{\bf
U}_{i_{T}}\nabla_{{\bf{x}}}f_{i_{T}}({\bf{x}}^{(t)},{\bf{y}}^{(t)})$
$\displaystyle=\lambda{\bf U}_{i_{T}}{\bf
U}_{i_{T}}^{\top}\nabla_{{\bf{x}}}H({\bf U}_{i_{T}}{\bf{x}}^{(t)},{\bf
U}_{i_{T}}{\bf{y}}^{(t)})$ $\displaystyle=\lambda\nabla_{{\bf{x}}}H({\bf
U}_{i_{T}}{\bf{x}}^{(t)},{\bf
U}_{i_{T}}{\bf{y}}^{(t)})\in{\mathcal{F}}_{k_{i_{T}}^{(T-1)}+1}={\mathcal{F}}_{k_{i_{T}}^{(T)}},$

where we have used the inductive hypothesis that

$\displaystyle{\bf U}_{i_{T}}{\bf{x}}^{(t)},{\bf
U}_{i_{T}}{\bf{y}}^{(t)}\in{\mathcal{F}}_{k_{i_{T}}^{(t)}}\subseteq{\mathcal{F}}_{k_{i_{T}}^{(T-1)}}.$

Therefore, we can conclude that

$\displaystyle{\bf U}_{i_{T}}{\bf{x}}^{(T)}$ $\displaystyle\in$
$\displaystyle\operatorname{span}\big{\\{}{\bf
U}_{i_{T}}{\bf{x}}^{(0)},\dots,{\bf U}_{i_{T}}{\bf{x}}^{(T-1)},{\bf
U}_{i_{T}}\nabla_{{\bf{x}}}f_{i_{T}}({\bf{x}}^{(0)},{\bf{y}}^{(0)}),\dots,{\bf
U}_{i_{T}}\nabla_{{\bf{x}}}f_{i_{T}}({\bf{x}}^{(T-1)},{\bf{y}}^{(T-1)})\big{\\}}$
$\displaystyle\subseteq$ $\displaystyle{\mathcal{F}}_{k_{i_{T}}^{(T)}}.$

The reason for the of result ${\bf
U}_{i}{\bf{x}}^{(T)}\in{\mathcal{F}}_{k_{i}^{(T)}}$ is same. ∎

Now we can show the lower bound for finding an approximate saddle point of
problem (42) by SFO algorithms when $L/\mu=\Omega(\sqrt{n})$.

######  Theorem 4.

For the parameter $L,\mu,n,{\varepsilon}$ such that $L/\mu>\sqrt{10n}$ and
${\varepsilon}<\frac{1}{2}e^{-5}\approx 0.00337$, we set

$\displaystyle\alpha=\sqrt{\frac{8n}{L^{2}/\mu^{2}-2n}},~{}~{}~{}\lambda=\frac{n\mu}{\alpha},~{}~{}~{}d=\left\lfloor\frac{1}{\alpha}\ln\left(\frac{1}{2{\varepsilon}}\right)\right\rfloor-4.$

Then the functions $f({\bf{x}},{\bf{y}};\alpha,\lambda,d)$ and
$f_{i}({\bf{x}},{\bf{y}};\alpha,\lambda,d)$ defined in Problem (42) satisfy
$f$ is $(\mu,\mu)$-convex-concave and $\\{f_{i}\\}_{i=1}^{n}$ is $L$-average-
smooth. Moreover, when we employ any SFO algorithm ${\mathcal{A}}$ to solve
the Problem (42), there holds

$\displaystyle\mathbb{E}\left[\left\|{\bf{x}}^{(t)}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}^{(t)}-{\bf{y}}^{*}\right\|_{2}^{2}\right]>{\varepsilon}~{}~{}~{}\text{
for }t\leq nd/2.$

###### Proof.

By Lemma 14 and definition of $\alpha,\lambda$, it is clear that $f$ is
$(\mu,\mu)$-convex-concave and
$\\{f_{i}({\bf{x}},{\bf{y}};\alpha,\lambda,d)\\}_{i=1}^{n}$ is $L$-average-
smooth.

For $T=nd/2$, let $i=\operatorname*{arg\,min}_{j}\\{k_{j}^{(T)}\\}$. It is
clear that $k_{i}^{(T)}\leq d/2$. Then by Property 4 in Lemma 13, for $t\leq
T$, we have

$\displaystyle\mathbb{E}\left[\left\|{\bf{x}}^{(t)}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}^{(t)}-{\bf{y}}^{*}\right\|_{2}^{2}\right]$
$\displaystyle\geq\mathbb{E}\left[\left\|{\bf
U}_{i}({\bf{x}}^{(t)}-{\bf{x}}^{*})\right\|_{2}^{2}+\left\|{\bf
U}_{i}({\bf{y}}^{(t)}-{\bf{y}}^{*})\right\|_{2}^{2}\right]$
$\displaystyle\geq\frac{q^{k_{i}^{(t)}}}{2}\left(\left\|{\bf
U}_{i}{\bf{x}}^{*}\right\|_{2}^{2}+\left\|{\bf
U}_{i}{\bf{y}}^{*}\right\|_{2}^{2}\right)$
$\displaystyle\geq\frac{q^{d/2}}{2}q^{2}\frac{1-q^{2d}}{1-q^{2}}$
$\displaystyle\geq\frac{q^{d/2+2}}{2},$

where $q=\frac{2+\alpha^{2}-\alpha\sqrt{\alpha^{2}+4}}{2}$,
$\omega=\frac{\sqrt{\alpha^{2}+4}-\alpha}{2}$, and ${\bf
U}_{i}{\bf{x}}^{*}=(q,q^{2},\dots,q^{d})^{\top}$ by Property 2 in Lemma 13.

Next, note that

$\displaystyle(2+d/2)\ln(1/q)$
$\displaystyle=(2+d/2)\ln\left(1+\frac{\alpha(\alpha+\sqrt{\alpha^{2}+4})}{2}\right)$
$\displaystyle\leq(2+d/2)\frac{\alpha(\alpha+\sqrt{\alpha^{2}+4})}{2}$
$\displaystyle<(2+d/2)\alpha(\alpha+1)$ $\displaystyle\leq(4+d)\alpha$
$\displaystyle\leq\ln(1/2{\varepsilon})$

which means that $\frac{q^{d/2+2}}{2}>{\varepsilon}$. The first inequality is
according to $\ln(1+a)\leq a$, the second inequality follows from
$\sqrt{a+b}<\sqrt{a}+\sqrt{b}$, the third inequality is due to
$L/\mu\geq\sqrt{10n}$ and $\alpha=\sqrt{\frac{8n}{L^{2}/\mu^{2}-2n}}\leq 1$,
and the last inequality is based on the definition of $d$. ∎

We remark that the condition ${\varepsilon}<\frac{1}{2}e^{-5}$ can ensure that
$d\geq 1$.

Furthermore, Theorem 4 implies that for any SFO algorithm ${\mathcal{A}}$ and
$L,\mu,n,{\varepsilon}$ such that $L/\mu>\sqrt{10n}$ and
${\varepsilon}<0.003$, there exist a dimension
$d={\mathcal{O}}\left(\sqrt{n}L/\mu\log(1/{\varepsilon})\right)$ and functions
$\\{f_{i}({\bf{x}},{\bf{y}})\\}_{i=1}^{n}:{\mathbb{R}}^{d}\times{\mathbb{R}}^{d}\to{\mathbb{R}}$
which satisfy $\\{f_{i}\\}_{i=1}^{n}$ is $L$-average smooth, $f$ is
$(\mu,\mu)$-convex-concave. In order to find an approximate saddle point
$(\hat{\bf{x}},\hat{\bf{y}})$ such that

$\displaystyle{\mathbb{E}}\left[\left\|\hat{\bf{x}}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|\hat{\bf{y}}-{\bf{y}}^{*}\right\|_{2}^{2}\right]\leq{\varepsilon},$

algorithm ${\mathcal{A}}$ needs at least
$\Omega((\sqrt{n}L/\mu)\log(1/{\varepsilon}))$ steps.

For the case $L/\mu={\mathcal{O}}(\sqrt{n})$, we consider following problem

$\displaystyle\begin{split}\min_{{\bf{x}}}\max_{{\bf{y}}}\hat{f}({\bf{x}},{\bf{y}})=&\frac{1}{n}\sum_{i=1}^{n}\hat{f}_{i}({\bf{x}},{\bf{y}})\\\
\triangleq&\frac{1}{n}\sum_{i=1}^{n}\left(\frac{\mu}{2}\left\|{\bf{x}}\right\|_{2}^{2}+\frac{\sqrt{n}\hat{L}}{2}(x_{i}-1)^{2}-\frac{\mu}{2}\left\|{\bf{y}}\right\|_{2}^{2}-\frac{\sqrt{n}\hat{L}}{2}(y_{i}-1)^{2}\right),\end{split}$
(44)

where $\hat{f}:{\mathbb{R}}^{n}\times{\mathbb{R}}^{n}\to{\mathbb{R}}$,
$\hat{L}=\sqrt{\frac{L^{2}}{2}-\mu^{2}}$.

And we provide the lower bound for finding approximate saddle point of Problem
(44) as follows.

######  Theorem 5.

For the parameter $L,\mu,n,{\varepsilon}$ such that $L/\mu>2$ and
${\varepsilon}<\frac{1}{8}$, the functions $\hat{f}({\bf{x}},{\bf{y}})$ and
$\hat{f}_{i}({\bf{x}},{\bf{y}})$ defined in Problem (44) satisfy $\hat{f}$ is
$(\mu,\mu)$-convex-concave and $\\{\hat{f}_{i}\\}_{i=1}^{n}$ is $L$-average-
smooth. Moreover, when we employ any SFO algorithm ${\mathcal{A}}$ to solve
the Problem (44), there holds

$\displaystyle\mathbb{E}\left[\left\|{\bf{x}}^{(t)}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}^{(t)}-{\bf{y}}^{*}\right\|_{2}^{2}\right]>{\varepsilon}~{}~{}~{}\text{
for }t\leq n/2.$

###### Proof.

It is easily to check that

$\displaystyle\hat{f}({\bf{x}},{\bf{y}})=\frac{\mu}{2}\left\|{\bf{x}}\right\|_{2}^{2}+\frac{\hat{L}}{2\sqrt{n}}\left\|{\bf{x}}-{\bf{1}}\right\|_{2}^{2}-\frac{\mu}{2}\left\|{\bf{y}}\right\|_{2}^{2}-\frac{\hat{L}}{2\sqrt{n}}\left\|{\bf{y}}-{\bf{1}}\right\|_{2}^{2}.$

Hence $\hat{f}$ is $(\mu,\mu)$-convex-concave and the saddle point
$({\bf{x}}^{*},{\bf{y}}^{*})$ of $\hat{f}$ satisfies

$\displaystyle{\bf{x}}^{*}={\bf{y}}^{*}=\frac{\hat{L}}{\hat{L}+\sqrt{n}\mu}{\bf{1}}.$

Next, observe that

$\displaystyle\nabla_{{\bf{x}}}\hat{f}_{i}({\bf{x}},{\bf{y}})=$
$\displaystyle\mu{\bf{x}}+\sqrt{n}\hat{L}({\bf{e}}_{i}^{\top}{\bf{x}}-1){\bf{e}}_{i},$
(45) $\displaystyle\nabla_{{\bf{y}}}\hat{f}_{i}({\bf{x}},{\bf{y}})=$
$\displaystyle-\mu{\bf{y}}-\sqrt{n}\hat{L}({\bf{e}}_{i}^{\top}{\bf{y}}-1){\bf{e}}_{i}.$

Then we have

$\displaystyle\quad\frac{1}{n}\sum_{i=1}^{n}\left(\left\|\nabla_{{\bf{x}}}\hat{f}_{i}({\bf{x}}_{1},{\bf{y}}_{1})-\nabla_{{\bf{x}}}\hat{f}_{i}({\bf{x}}_{1},{\bf{y}}_{1})\right\|_{2}^{2}+\left\|\nabla_{{\bf{y}}}\hat{f}_{i}({\bf{x}}_{1},{\bf{y}}_{1})-\nabla_{{\bf{y}}}\hat{f}_{i}({\bf{x}}_{1},{\bf{y}}_{1})\right\|_{2}^{2}\right)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left(\left\|\mu({\bf{x}}_{1}-{\bf{x}}_{2})+\sqrt{n}\hat{L}{\bf{e}}_{i}{\bf{e}}_{i}^{\top}({\bf{x}}_{1}-{\bf{x}}_{2})\right\|_{2}^{2}+\left\|\mu({\bf{y}}_{1}-{\bf{y}}_{2})+\sqrt{n}\hat{L}{\bf{e}}_{i}{\bf{e}}_{i}^{\top}({\bf{y}}_{1}-{\bf{y}}_{2})\right\|_{2}^{2}\right)$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\left(2\mu^{2}\left\|{\bf{x}}_{1}-{\bf{x}}_{2}\right\|_{2}^{2}+2n\hat{L}^{2}\left\|{\bf{e}}_{i}{\bf{e}}_{i}^{\top}({\bf{x}}_{1}-{\bf{x}}_{2})\right\|_{2}^{2}+2\mu^{2}\left\|{\bf{y}}_{1}-{\bf{y}}_{2}\right\|_{2}^{2}+2n\hat{L}^{2}\left\|{\bf{e}}_{i}{\bf{e}}_{i}^{\top}({\bf{y}}_{1}-{\bf{y}}_{2})\right\|_{2}^{2}\right)$
$\displaystyle=2(\hat{L}^{2}+\mu^{2})\left(\left\|{\bf{x}}_{1}-{\bf{x}}_{2}\right\|_{2}^{2}+\left\|{\bf{y}}_{1}-{\bf{y}}_{2}\right\|_{2}\right)=L^{2}\left(\left\|{\bf{x}}_{1}-{\bf{x}}_{2}\right\|_{2}^{2}+\left\|{\bf{y}}_{1}-{\bf{y}}_{2}\right\|_{2}\right),$

where the first inequality is according to
$\left\|{\bf{a}}+{\bf{b}}\right\|_{2}^{2}\leq
2\left\|{\bf{a}}\right\|_{2}^{2}+2\left\|{\bf{b}}\right\|_{2}^{2}$ and the
last equation follows from

$\displaystyle\sum_{i=1}^{n}\left\|{\bf{e}}_{i}{\bf{e}}_{i}^{\top}{\bf{u}}\right\|_{2}=\sum_{i=1}^{n}u_{i}^{2}=\left\|{\bf{u}}\right\|_{2}^{2}.$

Hence, $\\{\hat{f}_{i}\\}_{i=1}^{n}$ is $L$-average-smooth.

Moreover, by Equation (45) and definition of SFO algorithm, we know that

$\displaystyle{\bf{x}}^{(t)},{\bf{y}}^{(t)}\in\operatorname{span}\left\\{{\bf{e}}_{i_{1}},\dots,{\bf{e}}_{i_{t}}\right\\}.$

Consequently, for $t\leq n/2$, there holds

$\displaystyle\mathbb{E}$
$\displaystyle\left[\left\|{\bf{x}}^{(t)}-{\bf{x}}^{*}\right\|_{2}^{2}+\left\|{\bf{y}}^{(t)}-{\bf{y}}^{*}\right\|_{2}^{2}\right]$
$\displaystyle\geq$
$\displaystyle(n-t)\cdot\frac{\hat{L}^{2}}{(\hat{L}+\sqrt{n}\mu)^{2}}\geq\frac{n}{2}\cdot\frac{\hat{L}^{2}}{2\hat{L}^{2}+2n\mu^{2}}$
$\displaystyle=$
$\displaystyle\frac{n}{2}\cdot\frac{L^{2}/2-\mu^{2}}{L^{2}-2\mu^{2}+2n\mu^{2}}=\frac{n}{4}\left(1-\frac{2n}{L^{2}/\mu^{2}+2n-2}\right)$
$\displaystyle\geq$
$\displaystyle\frac{n}{4(n+1)}\geq\frac{1}{8}>{\varepsilon},$

where we have recalled that $\hat{L}^{2}=L^{2}/2-\mu^{2}$, $L/\mu>2$ and
$n\geq 1$. ∎

Combining Theorem 4 and 5, we obtain the result of Theorem 1.

##  Appendix E The Detailed Proof for Extension Case

In this section, we provide the detailed proof for the results in Section 4,
including the convex-strongly-concave case and the convex-concave cases.

###  E.1 The Proof of Lemma 4

###### Proof.

Just note that

$\displaystyle\max_{({\bf{x}},{\bf{y}})\in{\mathcal{X}}\times{\mathcal{Y}}}|f({\bf{x}},{\bf{y}})-f_{{\varepsilon},{\bf{x}}_{0}}({\bf{x}},{\bf{y}})|=\frac{{\varepsilon}}{4D_{x}^{2}}\max_{{\bf{x}}\in{\mathcal{X}}}\left\|{\bf{x}}-{\bf{x}}_{0}\right\|_{2}^{2}\leq\frac{{\varepsilon}}{4}.$

Therefore, we can conclude that

$\displaystyle\max_{{\bf{y}}\in{\mathcal{Y}}}f(\hat{{\bf{x}}},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},\hat{{\bf{y}}})$
$\displaystyle=f(\hat{{\bf{x}}},{\bf{y}}^{*}_{f}(\hat{{\bf{x}}}))-f({\bf{x}}^{*}_{f}(\hat{{\bf{y}}}),\hat{\bf{y}})$
$\displaystyle\leq\left(f_{{\varepsilon},{\bf{x}}_{0}}(\hat{{\bf{x}}},{\bf{y}}^{*}_{f}(\hat{{\bf{x}}}))+\frac{{\varepsilon}}{4}\right)-\left(f_{{\varepsilon},{\bf{x}}_{0}}({\bf{x}}^{*}_{f}(\hat{{\bf{y}}}),\hat{\bf{y}})-\frac{{\varepsilon}}{4}\right)$
$\displaystyle\leq\frac{{\varepsilon}}{2}+\max_{{\bf{y}}\in{\mathcal{Y}}}f_{{\varepsilon},{\bf{x}}_{0}}(\hat{{\bf{x}}},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f_{{\varepsilon},{\bf{x}}_{0}}({\bf{x}},\hat{{\bf{y}}}),$

where
${\bf{y}}^{*}_{f}(\hat{{\bf{x}}})=\operatorname*{arg\,max}_{{\bf{y}}\in{\mathcal{Y}}}f(\hat{{\bf{x}}},{\bf{y}})$
and
${\bf{x}}^{*}_{f}(\hat{{\bf{y}}})=\operatorname*{arg\,min}_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},\hat{{\bf{y}}})$.
∎

###  E.2 The Proof of Corollary 2

###### Proof.

By the definition of $f_{{\varepsilon},{\bf{x}}_{0}}$, we know that
$f_{{\varepsilon},{\bf{x}}_{0}}$ is
$\left(\frac{{\varepsilon}}{4D_{x}^{2}},\mu_{y}\right)$-convex-concave. The
smoothness of $f_{{\varepsilon},{\bf{x}}_{0}}$ can be verified by

$\displaystyle\quad\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{{\varepsilon},{\bf{x}}_{0},i}({\bf{x}},{\bf{y}})-\nabla
f_{{\varepsilon},{\bf{x}}_{0},i}({\bf{x}}^{\prime},{\bf{y}}^{\prime})\right\|_{2}^{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}({\bf{x}},{\bf{y}})-\nabla
f_{i}({\bf{x}}^{\prime},{\bf{y}}^{\prime})+\frac{{\varepsilon}}{4D_{x}^{2}}({\bf{x}}-{\bf{x}}^{\prime})\right\|_{2}^{2}$
$\displaystyle\leq\frac{2}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}({\bf{x}},{\bf{y}})-\nabla
f_{i}({\bf{x}}^{\prime},{\bf{y}}^{\prime})\right\|_{2}^{2}+\frac{{\varepsilon}^{2}}{8D_{x}^{4}}\left\|({\bf{x}}-{\bf{x}}^{\prime})\right\|_{2}^{2}$
$\displaystyle\leq
2L^{2}\left(\left\|{\bf{x}}-{\bf{x}}^{\prime}\right\|_{2}^{2}+\left\|{\bf{y}}-{\bf{y}}^{\prime}\right\|_{2}^{2}\right)+\frac{{\varepsilon}^{2}}{8D_{x}^{4}}\left\|{\bf{x}}-{\bf{x}}^{\prime}\right\|_{2}^{2}$
$\displaystyle\leq
4L^{2}\left(\left\|{\bf{x}}-{\bf{x}}^{\prime}\right\|_{2}^{2}+\left\|{\bf{y}}-{\bf{y}}^{\prime}\right\|_{2}^{2}\right),$

where the first inequality is according to $(a+b)^{2}\leq 2a^{2}+2b^{2}$ and
the second inequality follows from the smoothness of $\\{f_{i}\\}_{i=1}^{n}$
and ${\varepsilon}\leq 4LD_{x}^{2}$. Hence,
$\\{f_{{\varepsilon},{\bf{x}}_{0},i}\\}_{i=1}^{n}$ is $2L$-average smooth.

Then by Corollary 1, the number of SFO calls of AL-SVRE for finding
${\varepsilon}/2$-saddle point of $f_{{\varepsilon},{\bf{x}}_{0}}$ corresponds
to finding an ${\varepsilon}$-saddle point of $f$, that is

$\displaystyle\tilde{\mathcal{O}}\left(\sqrt{n\left(\sqrt{n}+\frac{2L}{\frac{{\varepsilon}}{4D_{x}^{2}}}\right)\left(\sqrt{n}+\frac{2L}{\mu_{y}}\right)}\right)=\tilde{\mathcal{O}}\left(\left(n+D_{x}\sqrt{\frac{nL\kappa_{y}}{{\varepsilon}}}+n^{3/4}\sqrt{\kappa_{y}}+n^{3/4}D_{x}\sqrt{\frac{L}{{\varepsilon}}}\right)\right).$

∎

###  E.3 The Proof of Lemma 5

###### Proof.

Note that

$\displaystyle\max_{({\bf{x}},{\bf{y}})\in{\mathcal{X}}\times{\mathcal{Y}}}|f({\bf{x}},{\bf{y}})-f_{{\varepsilon},{\bf{x}}_{0},{\bf{y}}_{0}}({\bf{x}},{\bf{y}})|=\max_{({\bf{x}},{\bf{y}})\in{\mathcal{X}}\times{\mathcal{Y}}}\left|\frac{{\varepsilon}}{8D_{x}^{2}}\left\|{\bf{x}}-{\bf{x}}_{0}\right\|_{2}^{2}-\frac{{\varepsilon}}{8D_{y}^{2}}\left\|{\bf{y}}-{\bf{y}}_{0}\right\|_{2}^{2}\right|\leq\frac{{\varepsilon}}{4}.$

For the same reason we got the result in the proof of Lemma 4, we also have

$\displaystyle\max_{{\bf{y}}\in{\mathcal{Y}}}f(\hat{{\bf{x}}},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},\hat{{\bf{y}}})$
$\displaystyle=f(\hat{{\bf{x}}},{\bf{y}}^{*}_{f}(\hat{{\bf{x}}}))-f({\bf{x}}^{*}_{f}(\hat{{\bf{y}}}),\hat{\bf{y}})$
$\displaystyle\leq\left(f_{{\varepsilon},{\bf{x}}_{0}}(\hat{{\bf{x}}},{\bf{y}}^{*}_{f}(\hat{{\bf{x}}}))+\frac{{\varepsilon}}{4}\right)-\left(f_{{\varepsilon},{\bf{x}}_{0}}({\bf{x}}^{*}_{f}(\hat{{\bf{y}}}),\hat{\bf{y}})-\frac{{\varepsilon}}{4}\right)$
$\displaystyle\leq\frac{{\varepsilon}}{2}+\max_{{\bf{y}}\in{\mathcal{Y}}}f_{{\varepsilon},{\bf{x}}_{0}}(\hat{{\bf{x}}},{\bf{y}})-\min_{{\bf{x}}\in{\mathcal{X}}}f_{{\varepsilon},{\bf{x}}_{0}}({\bf{x}},\hat{{\bf{y}}}),$

where
${\bf{y}}^{*}_{f}(\hat{{\bf{x}}})=\operatorname*{arg\,max}_{{\bf{y}}\in{\mathcal{Y}}}f(\hat{{\bf{x}}},{\bf{y}})$
and
${\bf{x}}^{*}_{f}(\hat{{\bf{y}}})=\operatorname*{arg\,min}_{{\bf{x}}\in{\mathcal{X}}}f({\bf{x}},\hat{{\bf{y}}})$.
∎

###  E.4 The Proof of Corollary 3

###### Proof.

By the definition of $f_{{\varepsilon},{\bf{x}}_{0},{\bf{y}}_{0}}$, we know
that $f_{{\varepsilon},{\bf{x}}_{0},{\bf{y}}_{0}}$ is
$\left(\frac{{\varepsilon}}{8D_{x}^{2}},\frac{{\varepsilon}}{8D_{y}^{2}}\right)$-convex-
concave. The smoothness of $f_{{\varepsilon},{\bf{x}}_{0}}$ can be verified by

$\displaystyle\quad\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{{\varepsilon},{\bf{x}}_{0},{\bf{y}}_{0},i}({\bf{x}},{\bf{y}})-\nabla
f_{{\varepsilon},{\bf{x}}_{0},{\bf{y}}_{0},i}({\bf{x}}^{\prime},{\bf{y}}^{\prime})\right\|_{2}^{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}({\bf{x}},{\bf{y}})-\nabla
f_{i}({\bf{x}}^{\prime},{\bf{y}}^{\prime})+\frac{{\varepsilon}}{8D_{x}^{2}}({\bf{x}}-{\bf{x}}^{\prime})-\frac{{\varepsilon}}{8D_{y}^{2}}({\bf{y}}-{\bf{y}}^{\prime})\right\|_{2}^{2}$
$\displaystyle\leq\frac{3}{n}\sum_{i=1}^{n}\left\|\nabla
f_{i}({\bf{x}},{\bf{y}})-\nabla
f_{i}({\bf{x}}^{\prime},{\bf{y}}^{\prime})\right\|_{2}^{2}+\frac{3{\varepsilon}^{2}}{64D_{x}^{4}}\left\|({\bf{x}}-{\bf{x}}^{\prime})\right\|_{2}^{2}+\frac{3{\varepsilon}^{2}}{64D_{y}^{4}}\left\|({\bf{y}}-{\bf{y}}^{\prime})\right\|_{2}^{2}$
$\displaystyle\leq
4L^{2}\left(\left\|{\bf{x}}-{\bf{x}}^{\prime}\right\|_{2}^{2}+\left\|{\bf{y}}-{\bf{y}}^{\prime}\right\|_{2}^{2}\right),$

where the first inequality is according to $(a+b+c)^{2}\leq
3a^{2}+3b^{2}+3c^{2}$ and the second inequality follows from the smoothness of
$\\{f_{i}\\}_{i=1}^{n}$ and ${\varepsilon}\leq
4L\min\\{D_{x}^{2},D_{y}^{2}\\}$. Hence,
$\\{f_{{\varepsilon},{\bf{x}}_{0},i}\\}_{i=1}^{n}$ is $2L$-average smooth.

Then by Corollary 1, the number of SFO calls of AL-SVRE for finding
${\varepsilon}/2$-saddle point of $f_{{\varepsilon},{\bf{x}}_{0}}$ corresponds
to finding an ${\varepsilon}$-saddle point of $f$, is

$\displaystyle\tilde{\mathcal{O}}\left(\sqrt{n\left(\sqrt{n}+\frac{2L}{\frac{{\varepsilon}}{8D_{x}^{2}}}\right)\left(\sqrt{n}+\frac{2L}{\frac{{\varepsilon}}{8D_{y}^{2}}}\right)}\right)=\tilde{\mathcal{O}}\left(\left(n+\frac{\sqrt{n}LD_{x}D_{y}}{{\varepsilon}}+n^{3/4}(D_{x}+D_{y})\sqrt{\frac{L}{{\varepsilon}}}\right)\right).$

∎