# Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved
Complexities

Zhongruo Wang Department of Mathematics, University of California, Davis.
Email<EMAIL_ADDRESS>Krishnakumar Balasubramanian Department of
Statistics, University of California, Davis. Email<EMAIL_ADDRESS>Shiqian
Ma Department of Mathematics, University of California, Davis. Email:
<EMAIL_ADDRESS>Meisam Razaviyayn Department of Industrial and Systems
Engineering, University of Southern California. Email<EMAIL_ADDRESS>
###### Abstract

In this paper, we study zeroth-order algorithms for minimax optimization
problems that are nonconvex in one variable and strongly-concave in the other
variable. Such minimax optimization problems have attracted significant
attention lately due to their applications in modern machine learning tasks.
We first design and analyze the Zeroth-Order Gradient Descent Ascent (ZO-GDA)
algorithm, and provide improved results compared to existing works, in terms
of oracle complexity. Next, we propose the Zeroth-Order Gradient Descent
Multi-Step Ascent (ZO-GDMSA) algorithm that significantly improves the oracle
complexity of ZO-GDA. We also provide stochastic version of ZO-GDA and ZO-
GDMSA to handle stochastic nonconvex minimax problems, and provide oracle
complexity results.

##  1 Introduction

Algorithms for solving optimization problems with only access to noisy
evaluations of the function being optimized are called zeroth-order
algorithms. Such zeroth-order optimization algorithms have been studied for
decades in the optimization literature; see, for example, [CSV09, RS13b, AH17]
for a detailed overview of the existing approaches. In the recent years, the
study of zeroth-order optimization algorithms has gained significant attention
also in the machine learning literature, due to several motivating
applications, for example, in designing black-box attacks to deep neural
networks [CZS+17], hyperparameter tuning [SLA12], reinforcement learning
[MSG99, SHC+17] and bandit convex optimization [BLE17]. However, a majority of
the zeroth-order optimization algorithms in the literature has been developed
for the so-called argmin-type optimization problems, which are of the
following form: find
$x^{*}:=\operatorname*{arg\,min}_{x\in\mathbb{R}^{d}}\left\\{f(x):=\textsf{\text{E}}\,_{\xi}[F(x,\xi)]\right\\}$.
Indeed there are a few exceptions, to the above situation and we refer the
interested reader to [LMW19] for details.

In this work, we study zeroth-order optimization algorithms for solving
nonconvex minimax problems. Specifically, we consider both the deterministic
setting, given by:

$\displaystyle\min_{x\in\mathbb{R}^{d_{1}}}\max_{y\in\mathcal{Y}}f(x,y),$ (1)

and the stochastic setting, given by:

$\displaystyle\min_{x\in\mathbb{R}^{d_{1}}}\max_{y\in\mathcal{Y}}f(x,y)=\textsf{\text{E}}\,_{\xi\sim\mathcal{P}}F(x,y,\xi).$
(2)

Here, $F(x,y,\xi)$ and hence $f(x,y)$ are assumed to be sufficiently smooth
functions, $\mathcal{Y}\subset\mathbb{R}^{d_{2}}$ is a closed and convex
constraint set111One of our algorithms works also in the unconstrained
setting. See Remark B.1 for more details., and $\mathcal{P}$ is a distribution
characterizing the stochasticity in the problem. We allow for the function
$f(\cdot,y)$ to be nonconvex for all $y\in\mathbb{R}^{d_{2}}$ but require
$f(x,\cdot)$ to be strongly-concave for all $x\in\mathbb{R}^{d_{1}}$. The
exact assumptions are provided in Section 2.1. Under these assumptions, we
provide zeroth-order optimization algorithms for solving the above minimax
problem and characterize its oracle complexity (also called query complexity
in the zeroth-order setting). Compared to the analysis of oracle complexity of
zeroth-order algorithms for argmin-type optimization problems, the
corresponding analysis in the minimax situation is more involved.

Our main motivation for studying zeroth-order algorithms for nonconvex minimax
problems is its application in designing black-box attacks to deep neural
networks. By now, it is well established that care must be taken when
designing and training deep neural networks as it is possible to design
adversarial examples that would make the deep network to misclassify, easily.
Since the intriguing works of [SZS+13, LCLS17], the problem of designing such
adversarial examples that transfer across multiple deep neural networks
models, has also been studied extensively. As the model architecture is
unknown to the adversary, the problem could naturally be formulated to solve a
minimax optimization problem under the availability of only noisy objective
function evaluation. We refer the reader to [LLC+19] for details regarding
such formulations. Apart from the above applications, we also note that
zeroth-order minimax optimization problems also arise in multi-agent
reinforcement learning with bandit feedback [WHL17, ZYB19] and robotics [WJ17,
BSJC18].

###  1.1 Related Works

First-order algorithms for minimax problems (aka saddle-point problems) have a
long history in the mathematical programming and operations research
community. The celebrated extragradient method was proposed in [Kor76] and
consequently analyzed by [Tse95, FA96, FP07] for the case of bilinear
objectives and strongly-convex and strongly-concave objectives. Generalizing
the extragradient method, [Nem04] proposed and analyzed the mirror-prox method
for the smooth convex-concave objectives, which was also later analyzed by
[MS10]. A sub-gradient based algorithm was proposed and analyzed in [NO09] to
handle non-smooth objectives. A unified view of extragradient and proximal
point method was provided in [MOP19, AMLJG19] and a stochastic version of
offline minimax problems was considered in [PB16]. Frank-Wolfe algorithm for
saddle-point optimization was analyzed in [GJLJ17], where it was noted that
the first use of Frank-Wolfe algorithm for saddle-point optimization was in
[Ham84]. In the learning theory community, an alternative approach for solving
minimax problems has been considered. This approach involves using an online
convex optimization algorithm for performing saddle-point optimization; see,
for example [DDK11, SALS15, RS13a, CBL06, AW17, BP18] for more details on this
approach. The developed approaches in the learning theory community compare
favorably to the optimal algorithm developed in the mathematical programming
and operations research community (for example, [Nem04]).

In the recent years, there has been an ever-growing interest in analyzing
first-order algorithms for the case of nonconvex-concave objective and
nonconvex-nonconcave objectives, motivated by its applications to training
generative adversarial networks [GPAM+14], AUC maximization [YWL16], designing
fair classifiers [ABD+18], robust learning systems [MMS+17] fair machine
learning [ZLM18, XYZW18, BNR19], and reinforcement learning [PV16, DSL+17,
NSS03, FV12]. Specifically, [LTHC19, RLLY18, NSH+19, SBRL18, LJJ19, TJNO19],
proposed and analyzed variants of gradient descent ascent for nonconvex-
concave objectives. Very recently, under a stronger mean-squared Lipschitz
gradient assumption [LYZ20] obtained the best known complexity for stochastic
nonconvex-concave objectives. Furthermore, [DISZ17, DP18, HLC18, MPP18, PS18,
GBV+18, OSG+18, JNJ19, FVGP19] studied general nonconvex-nonconcave
objectives. Compared to first-order algorithms, zeroth-order algorithms for
minimax optimization problems are understudied. Motivated by the need for
robustness in optimization, [MW18] proposed derivative-free algorithms for
saddle-point optimization. However, they do not provide non-asymptotic oracle
complexity analysis. Bayesian optimization algorithms and evolutionary
algorithms were proposed in [BSJC18, PBH19] and [BN10, ADSHO18] respectively
for minimax optimization, targeting robust optimization and learning
applications. The above works do not provide any oracle complexity analysis.
Recently, [RCBM19] studied zeroth-order Frank-Wolfe algorithms for strongly-
convex and strongly-concave constrained saddle-point optimization problems and
provided non-asymptotic oracle complexity analysis. Furthermore, [LLC+19]
studied zeroth-order algorithms for nonconvex-concave minimax problems,
similar to our setting. A detailed comparison between our results and [LLC+19]
is provided in Section 5. The literature on zeroth-order optimization for the
general argmin-type optimization problem is vast and we do not attempt to
survey it. Instead, we refer the interested reader to the recent excellent
survey [LMW19].

###  1.2 Our Contributions

In this work, we consider both deterministic and stochastic minimax problems
in the form of (1) and (2), respectively. Our contributions could be
summarized as follows:

  * •

Considering deterministic minimax problem, we first design a zeroth-order
gradient descent ascent (ZO-GDA) algorithm, whose oracle complexity improves
the currently best known one in [LLC+19]. The stochastic counterpart of ZO-
GDA, ZO-SGDA, is also discussed and its oracle complexity is analyzed.
Notably, for this algorithm, the set $\mathcal{Y}$ could be constrained or
unconstrained (i.e., the entire Euclidean space $\mathbb{R}^{d_{2}}$).

  * •

We next propose a novel zeroth-order gradient descent multi-step ascent (ZO-
GDMSA) algorithm for the deterministic case, which is motivated by [NSH+19].
This algorithm performs multiple steps of gradient ascent followed by one
single step of gradient descent in each iteration. Its oracle complexity is
significantly better than that of ZO-GDA. To the best of our knowledge, this
is the best complexity result for zeroth-order algorithms for solving
deterministic minimax problems so far under Assumption 2.1 stated below. The
stochastic counterpart of ZO-GDMSA is also discussed and its oracle complexity
is provided.

We emphasize that in our work, the gradient Lipschitz condition in part 3 of
Assumption 2.1 remains the same for stochastic problems. With a stronger
assumption, as in [LYZ20], it is plausible to obtain improved complexities
using variance reduction techniques, which is beyond the scope of this work
though.

##  2 Preliminaries

###  2.1 Assumptions

The following assumptions are made throughout the paper.

######  Assumption 2.1.

The objective function $f(x,y)$ and the constraint set $\mathcal{Y}$ have the
following properties:

  * •

$f(x,y)$ is continuously differentiable in $x$ and $y$, and $f(\cdot,y)$ is
nonconvex for all $y\in\mathcal{Y}$ and $f(x,\cdot)$ is $\tau$-strongly
concave for all $x\in\mathbb{R}^{d_{1}}$.

  * •

The function $g(x):=\max_{y\in\mathcal{Y}}f(x,y)$ is lower bounded. We use
$L_{g}$ to denote the Lipschitz constant of $g$, see Lemma A.3.

  * •

When viewed as a function in $\mathbb{R}^{d_{1}+d_{2}}$, $f(x,y)$ is
$\ell$-gradient Lipschitz. That is, there exists constant $\ell>0$ such that

$\|\nabla f(x_{1},y_{1})-\nabla
f(x_{2},y_{2})\|_{2}\leq\ell\|(x_{1},y_{1})-(x_{2},y_{2})\|_{2},\forall
x_{1},x_{2}\in\mathbb{R}^{d_{1}},y_{1},y_{2}\in\mathcal{Y}.$ (3)

We use $\kappa:=\ell/\tau$ to denote the problem condition number throughout
this paper.

  * •

The constraint set $\mathcal{Y}\subset\mathbb{R}^{d_{2}}$ is bounded and
convex, with diameter $D>0$.

In the above, the first condition details the structure of the objective
function in the minimax problem we consider. The second condition is required
to make the optimization problem well-defined. The third condition places a
restriction on the degree of smoothness to be satisfied by the objective
function and is also standard in the literature. The fourth condition places a
restriction on the constraint set for the strongly-convex maximization part.
This assumption is only required in the analysis of ZO-GDMSA and its
stochastic counterpart. We emphasize that in the analysis of ZO-GDA, the
assumption that $\mathcal{Y}$ is a closed and convex set is not essential –
our results continue to hold when $\mathcal{Y}:=\mathbb{R}^{d_{2}}$. We
utilize the constraint set in both algorithms, to maintain a consistent
presentation. See Remark B.1 for more details. We also make the following
standard assumptions on the (stochastic) zeroth-order oracle, following [NS17,
GL13, BG19].

######  Assumption 2.2.

For any $x\in\mathbb{R}^{d_{1}}$ and $y\in\mathcal{Y}$, the stochastic zeroth-
order oracle outputs an estimator $F\left(x,y,\xi\right)$ of
$f\left(x,y\right)$ such that
$\textsf{\text{E}}\,_{\xi}[F\left(x,y,\xi\right)]=f\left(x,y\right)$ and

$\displaystyle\textsf{\text{E}}\,_{\xi}[\nabla_{x}F\left(x,y,\xi\right)]=\nabla_{x}f\left(x,y\right),\quad$
$\displaystyle\textsf{\text{E}}\,_{\xi}[\nabla_{y}F\left(x,y,\xi\right)]=\nabla_{y}f\left(x,y\right),$
$\displaystyle\textsf{\text{E}}\,_{\xi}[\|\nabla_{x}F(x,y,\xi)-\nabla_{x}f(x,y)\|_{2}^{2}]\leq\sigma_{1}^{2},\quad$
$\displaystyle\textsf{\text{E}}\,_{\xi}[\|\nabla_{y}F(x,y,\xi)-\nabla_{y}f(x,y)\|_{2}^{2}]\leq\sigma_{2}^{2}.$

In the deterministic case, we assume we have access to the exact function
evaluations.

###  2.2 Zeroth-order gradient estimator

We now discuss the idea of zeroth-order gradient estimator based on Gaussian
Stein’s identity [NS17]. For the deterministic case, we denote
$\boldsymbol{u}_{1}\sim N(0,\textbf{1}_{d_{1}})$, $\boldsymbol{u}_{2}\sim
N(0,\textbf{1}_{d_{2}})$, where $\textbf{1}_{d_{1}}$ and $\textbf{1}_{d_{2}}$
denote identity matrices with sizes $d_{1}\times d_{1}$ and $d_{2}\times
d_{2}$, respectively. The notion of the Gaussian smoothed functions can be
defined as:

$f_{\mu_{1}}(x,y):=\textsf{\text{E}}\,_{\boldsymbol{u}_{1}}f(x+\mu_{1}\boldsymbol{u}_{1},y),\quad
f_{\mu_{2}}(x,y):=\textsf{\text{E}}\,_{\boldsymbol{u}_{2}}f(x,y+\mu_{2}\boldsymbol{u}_{2}),$
(4)

and the zeroth-order gradient estimators [NS17] are defined as

$G_{\mu_{1}}(x,y,\boldsymbol{u}_{1})=\frac{f(x+\mu_{1}\boldsymbol{u}_{1},y)-f(x,y)}{\mu_{1}}\boldsymbol{u}_{1},\quad
H_{\mu_{2}}(x,y,\boldsymbol{u}_{2})=\frac{f(x,y+\mu_{2}\boldsymbol{u}_{2})-f(x,y)}{\mu_{2}}\boldsymbol{u}_{2},$
(5)

where $\mu_{1}>0$ and $\mu_{2}>0$ are smoothing parameters. It should be noted
following the arguments in [NS17, BG19] that

$\textsf{\text{E}}\,_{\boldsymbol{u}_{1}}G_{\mu_{1}}(x,y,\boldsymbol{u}_{1})=\nabla_{x}f_{\mu_{1}}(x,y),\quad\textsf{\text{E}}\,_{\boldsymbol{u}_{2}}G_{\mu_{2}}(x,y,\boldsymbol{u}_{2})=\nabla_{y}f_{\mu_{2}}(x,y).$

Hence, the zeroth-order gradient estimators in (5) provide unbiased estimates
of the gradient of Gaussian smoothed functions
$f_{\mu_{1}}(x,y,\boldsymbol{u}_{1})$ and
$f_{\mu_{2}}(x,y,\boldsymbol{u}_{2})$. Similarly, for the stochastic case, the
Gaussian smoothed functions are defined as:

$f_{\mu_{1}}(x,y):=\textsf{\text{E}}\,_{\boldsymbol{u}_{1},\xi}F(x+\mu_{1}\boldsymbol{u}_{1},y,\xi),\quad
f_{\mu_{2}}(x,y):=\textsf{\text{E}}\,_{\boldsymbol{u}_{2},\xi}F(x,y+\mu_{2}\boldsymbol{u}_{2},\xi),$
(6)

and the zeroth-order stochastic gradient estimators are defined as:

$G_{\mu_{1}}(x,y,\boldsymbol{u}_{1},\xi)=\frac{F(x+\mu_{1}\boldsymbol{u}_{1},y,\xi)-F(x,y,\xi)}{\mu_{1}}\boldsymbol{u}_{1},\quad
H_{\mu_{2}}(x,y,\boldsymbol{u}_{2},\xi)=\frac{F(x,y+\mu_{2}\boldsymbol{u}_{2},\xi)-F(x,y,\xi)}{\mu_{2}}\boldsymbol{u}_{2}.$
(7)

One can also show that the zeroth-order gradient estimators provide unbiased
estimates to the gradients of the Gaussian smoothed functions, i.e.,

$\textsf{\text{E}}\,_{\boldsymbol{u}_{1},\xi}G_{\mu_{1}}(x,y,\boldsymbol{u}_{1},\xi)=\nabla_{x}f_{\mu_{1}}(x,y),\quad\textsf{\text{E}}\,_{\boldsymbol{u}_{2},\xi}H_{\mu_{2}}(x,y,\boldsymbol{u}_{2},\xi)=\nabla_{y}f_{\mu_{2}}(x,y).$

In the algorithms, we also need to use mini-batch zeroth-order gradient
estimators, which can reduce the variance of stochastic gradient estimators.
To this end, we define the following notation. For integer $q>0$, we denote
$[q]:=\\{1,\ldots,q\\}$. In the deterministic case, for integers $q_{1}>0$,
$q_{2}>0$ we denote

$G_{\mu_{1}}(x,y,\boldsymbol{u}_{1,[q_{1}]})=\frac{1}{q_{1}}\sum_{i=1}^{q_{1}}G_{\mu_{1}}(x,y,\boldsymbol{u}_{1,i}),\quad
H_{\mu_{2}}(x,y,\boldsymbol{u}_{2,[q_{2}]})=\frac{1}{q_{2}}\sum_{i=1}^{q_{2}}H_{\mu_{2}}(x,y,\boldsymbol{u}_{2,i}).$
(8)

For indices sets $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$, in the stochastic
case we denote

$\begin{array}[]{ll}G_{\mu_{1}}(x,y,\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})&=\frac{1}{|\mathcal{M}_{1}|}\sum_{i\in\mathcal{M}_{1}}G_{\mu_{1}}(x,y,\boldsymbol{u}_{1,i},\xi_{i}),\\\
H_{\mu_{2}}(x,y,\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}})&=\frac{1}{|\mathcal{M}_{2}|}\sum_{i\in\mathcal{M}_{2}}H_{\mu_{2}}(x,y,\boldsymbol{u}_{2,i},\xi_{i}).\end{array}$
(9)

It is easy to see that we then have the following unbiasedness properties:

$\textsf{\text{E}}\,_{\boldsymbol{u}_{1,[q_{1}]}}G_{\mu_{1}}(x,y,\boldsymbol{u}_{1,[q_{1}]})=\nabla_{x}f_{\mu_{1}}(x,y),\quad\textsf{\text{E}}\,_{\boldsymbol{u}_{2,[q_{2}]}}H_{\mu_{2}}(x,y,\boldsymbol{u}_{2,[q_{2}]})=\nabla_{y}f_{\mu_{2}}(x,y),$

and

$\textsf{\text{E}}\,_{\boldsymbol{u}_{1}}\textsf{\text{E}}\,_{\xi_{\mathcal{M}_{1}}}G_{\mu_{1}}(x,y,\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})=\nabla_{x}f_{\mu_{1}}(x,y),\quad\textsf{\text{E}}\,_{\boldsymbol{u}_{2}}\textsf{\text{E}}\,_{\xi_{\mathcal{M}_{2}}}H_{\mu_{2}}(x,y,\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}})=\nabla_{y}f_{\mu_{2}}(x,y).$

Finally, it should be noted that although our gradient estimators are defined
based on Gaussian random vectors, in the literature the use of other random
vectors, in particular, uniform random vectors on the unit-sphere has also
been explored [NY83, FKM05]. Following an analysis similar to that of [Sha17],
it is plausible that our results in this paper could also be extended to such
cases. A detailed investigation is beyond the scope of this paper though.

###  2.3 Complexity Measure

Recall that the minimax problem (2) is equivalent to the following argmin-type
minimization problem:

$\displaystyle\min_{x}\left\\{g(x):=\max_{{y}}f({x},{y})=f(x,y^{*}(x))\right\\},$
(10)

where $y^{*}(x)$ is the maximum $y$ for given $x$. Due to our Assumption 2.1,
that $f({x},\cdot)$ is strongly-concave for any fixed
${x}\in\mathbb{R}^{d_{1}}$, the maximization problem $\max_{y}f(x,y)$ can be
solved efficiently and its optimal solution is unique. However, since $g$ is a
nonconvex function, it is usually difficult to find its global minimum. Hence,
following the standard approach in the literature [Nes18], we will seek for a
stationary point of function $g$. In order to measure the performance of the
algorithms developed in this paper, we need to define some new measures for
optimality. In the definitions that follow, for the deterministic case, the
expectation is taken with respect to the Gaussian random vectors, used in the
zeroth-order gradient estimators. In the stochastic setting, the expectation
is taken both with respect to the Gaussian random vectors and the i.i.d copies
of $\xi$ used in the algorithm. We first note that for argmin-type nonconvex
optimization problem, as in (10), first-order stationary solutions are defined
as follows.

######  Definition 2.1.

We call $\bar{x}$ an $\epsilon$-stationary point of a differentiable function
$g$ if $\textsf{\text{E}}\,[\|\nabla g(\bar{x})\|^{2}_{2}]\leq\epsilon^{2}$.
If $\epsilon=0$, then $\bar{x}$ is called a stationary point of $g$.

Following [LJJ19], we first define a notion of stationarity for the problem
(1), under Assumption 2.1.

######  Definition 2.2.

A point $(\bar{x},\bar{y})$ is called an $\epsilon$-stationary point of
problem (1) if it satisfies the following conditions:
$\textsf{\text{E}}\,[\|\nabla_{x}f(\bar{x},\bar{y})\|^{2}_{2}]\leq\epsilon^{2}$
and
$\textsf{\text{E}}\,[\|\nabla_{y}f(\bar{x},\bar{y})\|^{2}_{2}]\leq\epsilon^{2}$.

It is straightforward to now relate the stationary point of function $g$, as
in Definition 2.1, to the stationary point of the original saddle-point
optimization problem in (1), as in Definition 2.2, as we outline in the
following proposition.

######  Proposition 2.1.

Under Assumption 2.1, if a point $\bar{x}$ satisfies
$\textsf{\text{E}}\,[\|\nabla g(\bar{x})\|^{2}_{2}]\leq\epsilon^{2}$, by using
extra $\mathcal{O}\Bigl{(}\kappa d_{2}\log(\epsilon^{-1})\Bigr{)}$ calls to
the zeroth order oracle in the deterministic setting or by using extra
$\mathcal{O}\Bigl{(}d_{2}/\epsilon^{2})\Bigr{)}$ calls to the zeroth order in
the stochastic setting, a point $(\bar{x},\bar{y})$ can be obtained such that
it is an $\epsilon$-stationary solution of the minimax problem, as in
Definition 2.2.

The proof of the proposition follows verbatim the proof of Proposition 5.1 in
[LJJ19] and we omit it for succinctness. From Proposition 2.1, we note that in
order to obtain an $\epsilon$-stationary solution (as in Definition 2.2) for
the problem (1), it is equivalent to analyzing the rate of convergence to
$\epsilon$-stationary solution (as in Definition 2.1) for the function $g(x)$.
Based on this equivalence, in this work, we concentrate on obtaining
$\epsilon$-stationary point of the differentiable function $g$ in (10).

##  3 Zeroth-order Algorithms for Deterministic Minimax Problems

We now present our algorithms for the deterministic problem (1). We consider
two algorithms. In the first case, we do a vanilla single-step gradient
descent and ascent. Next, motivated by [NSH+19], for each iteration of the
minimization part, we perform multiple steps of gradient ascent for the
maximization part. Notably, this improves the complexity in terms of the
dependency on the condition number of the problem.

###  3.1 Zeroth-Order Gradient Descent Ascent

The zeroth-order gradient descent ascent (ZO-GDA) algorithm for solving
problem (1) is described in Algorithm 1. The algorithm is similar to the
deterministic first-order approach analyzed in [LJJ19] with a few crucial
differences. Specifically, we require a mini-batch gradient estimator with the
choices of the batch size depending on the dimensionality of the problem.

Algorithm 1 Zeroth-Order Gradient Descent Ascent (ZO-GDA)

Initialization: $(x_{0},y_{0})$, stepsizes $(\eta_{1},\eta_{2})$, iteration
limit $S>0$, parameters $\mu_{1}$ and $\mu_{2}$. Set $q_{1}=2(d_{1}+6)$,
$q_{2}=2(d_{2}+6)$.

for $s=0,\ldots,S$ do

$x_{s+1}\leftarrow
x_{s}-\eta_{1}G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{1,[q_{1}]})$ with
$\boldsymbol{u}_{1,i}\sim N(0,\boldsymbol{1}_{d_{1}})$, $i\in[q_{1}]$

$y_{s+1}\leftarrow\text{Proj}_{\mathcal{Y}}[y_{s}+\eta_{2}H_{\mu_{2}}(x_{s},y_{s},\boldsymbol{u}_{2,[q_{2}]})]$
with $\boldsymbol{u}_{2,i}\sim N(0,\boldsymbol{1}_{d_{2}})$, $i\in[q_{2}]$

end for

Return $(x_{1},y_{1}),\ldots,(x_{S},y_{S})$.

The complexity result for ZO-GDA (Algorithm 1) is provided in Theorem 3.1.

######  Theorem 3.1.

Under Assumption 2.1, by setting

$\eta_{1}:=\frac{1}{4\times
12^{4}\kappa^{2}(\kappa+1)^{2}(\ell+1)},~{}~{}\eta_{2}:=1/(6\ell),$ (11)

and

$S:=\mathcal{O}(\kappa^{5}\epsilon^{-2}),~{}~{}\mu_{1}:=\mathcal{O}(\epsilon
d_{1}^{-3/2}\kappa^{-2}),~{}~{}\mu_{2}:=\mathcal{O}(\epsilon
d_{2}^{-3/2}\kappa^{-2}),$ (12)

ZO-GDA (Algorithm 1) returns iterates $(x_{1},y_{1}),\ldots,(x_{S},y_{S})$
such that there exist an iterate which is an $\epsilon$-stationary point of
$g(x)=\max_{y\in\mathcal{Y}}f(x,y)$. That is, ZO-GDA (Algorithm 1) returns
iterates that satisfy $\min_{s\in\\{1,...,S\\}}\textsf{\text{E}}\,[\|\nabla
g(x_{s})\|_{2}^{2}]\leq\epsilon^{2}$. Moreover, the total number of calls to
the (deterministic) zeroth-order oracle, $K_{\mathcal{ZO}}$ is given by,

$K_{\mathcal{ZO}}=S(q_{1}+q_{2})\sim\mathcal{O}\Bigl{(}\kappa^{5}(d_{1}+d_{2})\epsilon^{-2}\Bigr{)}.$

######  Remark 3.1.

We see that the total calls to the (deterministic) zeroth-order oracle depends
linearly on the dimensionality of the problem under consideration. The
dependence on $\epsilon$ is the same as that of corresponding first-order
methods [LJJ19]. But, the dependence on the condition number $\kappa$ is
increased from $\kappa^{2}$ to $\kappa^{5}$ (assuming $d_{1}$ and $d_{2}$ are
of constant order). This is due to the choice of balancing the various tuning
parameters in the zeroth-order setting, in particular $\mu_{1}$ and $\mu_{2}$
which are absent in the first-order setting.

###  3.2 Zeroth-Order Gradient Descent Multi-Step Ascent

In this section, we show that the dependence of the complexity on the
condition number $\kappa$ could be reduced significantly (i.e., from
$\kappa^{5}$ to $\kappa^{2}$) by making a simple modification to the ZO-GDA
algorithm. Specifically, we run $T$ steps of the ascent part, for every
descent step. The approach is presented formally in Algorithm 2 and the
corresponding complexity results are provide in Theorem 3.2. The main idea
behind running multiple ascent steps is to better approximate the maximum of
the stongly-concave function in each step. Subsequently, picking the number of
inner iterations $T$ appropriately, helps us obtain improved dependence on
$\kappa$ while still maintaining the same dependency on $\epsilon$. We
emphasize that [NSH+19] used the multi-step ascent approach to handle certain
non-convex minimax optimization problems that satisfy the so-called Polyak-
Łojasiewicz condition in the first-order setting.

Algorithm 2 Zeroth-Order Gradient Descent Multi-Step Ascent (ZO-GDMSA)

Initialization: $\left(x_{0},y_{0}\right)$, step sizes
$\left(\eta_{1},\eta_{2}\right)$, iteration limit for outer loop $S>0$,
iteration limit for inner loop $T>0$, parameters $\mu_{1}$ and $\mu_{2}$. Set
$q_{1}=2(d_{1}+6)$ and $q_{2}=2(d_{2}+6)$.

for $s=0,\ldots,S$ do

Set $y_{0}(x_{s})\leftarrow y_{s}$

for $t=1,\ldots,T$ do

$y_{t}(x_{s})\leftarrow\mathrm{Proj}_{\mathcal{Y}}(y_{t-1}(x_{s})+\eta_{2}H_{\mu_{2}}(x_{s},y_{t-1}(x_{s}),\boldsymbol{u}_{2,[q_{2}]}))$
with $\boldsymbol{u}_{2,i}\sim N(0,\boldsymbol{1}_{d_{2}})$, $i\in[q_{2}]$

end for

$y_{s+1}\leftarrow y_{T}(x_{s})$

$x_{s+1}\leftarrow
x_{s}-\eta_{1}G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{1,[q_{1}]})$ with
$\boldsymbol{u}_{1,i}\sim N(0,\boldsymbol{1}_{d_{1}})$, $i\in[q_{1}]$

end for

Return $(x_{1},y_{1}),\ldots,(x_{S},y_{S})$.

######  Theorem 3.2.

Under Assumption 2.1, by setting

$\eta_{1}=1/(12L_{g}),\ \eta_{2}=1/(6\ell),\
T=\mathcal{O}(\kappa\log(\epsilon^{-1})),$ (13)

and

$S\sim\mathcal{O}(\kappa\epsilon^{-2}),\
\mu_{1}\sim\mathcal{O}({\epsilon}d_{1}^{-3/2}),\
\mu_{2}=\mathcal{O}(\kappa^{-1/2}d_{2}^{-3/2}\epsilon),$ (14)

ZO-GDMSA (Algorithm 2) returns iterates $(x_{1},y_{1}),\ldots,(x_{S},y_{S})$
such that there exist an iterate which is an $\epsilon$-stationary point for
$g(x)=\max_{y\in\mathcal{Y}}f(x,y)$. That is, ZO-GDMSA (Algorithm 2) returns
iterates that satisfy $\min_{s\in\\{1,...,S\\}}\textsf{\text{E}}\,[\|\nabla
g(x_{s})\|_{2}^{2}]\leq\epsilon^{2}$. Moreover, the total number of calls to
the (deterministic) zeroth-order oracle is given by

$K_{\mathcal{ZO}}=Sq_{1}+TSq_{2}\sim\mathcal{O}\Bigl{(}\kappa\epsilon^{-2}(d_{1}+\kappa
d_{2}\log(\epsilon^{-1}))\Bigr{)}.$

######  Remark 3.2.

Note that compared to Algorithm 1, Algorithm 2 obtains improved dependence on
$\kappa$ while maintaining the same dependence on $\epsilon$. Recall that
$\kappa=\ell/\tau$. Assuming both $d_{1}$ and $d_{2}$ are of constant order,
the dependency of the complexity on $\kappa$ is of quadratic order. Assuming
only $d_{1}$ is of constant order, as long as $d_{2}=o(1/\kappa)$, the
dependence of the complexity on $\kappa$ is improved to be of linear order.

##  4 Zeroth-order Algorithms for Stochastic Minimax Problems

We now consider the stochastic saddle-point optimization problem of the form
(2), under the availability of a stochastic zeroth-order oracle satisfying
Assumption 2.2. This scenario is more practical in the context of zeroth-order
optimization, as often times, we are able to only observe noisy evaluations of
the function and not the exact values themselves [CSV09, AH17]. Motivated by
our analysis of the deterministic case, we now analyze the stochastic versions
of ZO-GDA and ZO-GDMSA.

We first consider stochastic version of the gradient descent ascent algorithm
presented in Algorithm 3. The main difference between Algorithm 3 and its
deterministic counterpart in Algorithm 1 is in the choice of mini-batch size
in the zeroth-order gradient estimator. As opposed to the deterministic case,
where the mini-batch size is independent of $\epsilon$, in this case, we
require a mini-batch size that depends on $\epsilon$. Furthermore, due to the
stochastic nature of the problem, the mini-batch size also depends on the
noise variance parameter $\sigma^{2}$. The complexity result corresponding to
Algorithm 3 is provided in Theorem 4.1.

Algorithm 3 Zeroth-Order Stochastic Gradient Descent Ascent (ZO-SGDA)

Initialization: $\left(x_{0},y_{0}\right)$, step sizes
$\left(\eta_{1},\eta_{2}\right)$, iteration limit $S>0$, smoothing parameters
$\mu_{1}$ and $\mu_{2}$. Indices sets $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$
with cardinality
$|\mathcal{M}_{1}|=4(d_{1}+6)(\sigma_{1}^{2}+1)\epsilon^{-2}$,
$|\mathcal{M}_{2}|=4(d_{2}+6)(\sigma_{2}^{2}+1)\epsilon^{-2}$.

for $s=0,\ldots,S$ do

$x_{s+1}\leftarrow
x_{s}-\eta_{1}\frac{1}{|\mathcal{M}_{1}|}\sum_{i\in\mathcal{M}_{1}}G_{\mu_{1}}\left(x_{s},y_{s},\boldsymbol{u}_{1,i},\xi_{i}\right)$
with $\boldsymbol{u}_{1,i}\sim N(0,\boldsymbol{1}_{d_{1}})$

$y_{s+1}\leftarrow\text{Proj}_{\mathcal{Y}}\Bigl{[}y_{s}+\eta_{2}\frac{1}{|\mathcal{M}_{2}|}\sum_{i\in\mathcal{M}_{2}}H_{\mu_{2}}\left(x_{s},y_{s},\boldsymbol{u}_{2,i},\xi_{i}\right)\Bigr{]}$
with $\boldsymbol{u}_{2,i}\sim N(0,\boldsymbol{1}_{d_{2}})$

end for

Return $(x_{1},y_{1}),\ldots,(x_{S},y_{S})$.

######  Theorem 4.1.

Let $\epsilon\in(0,1)$. Under Assumption 2.1 and 2.2, by setting the
parameters in the same way as Theorem 3.1, i.e., (11) and (12), ZO-SGDA
(Algorithm 3) returns iterates $(x_{1},y_{1}),\ldots,(x_{S},y_{S})$ such that
there exist an iterate which is an $\epsilon$-stationary point for
$g(x)=\max_{y\in\mathcal{Y}}f(x,y)$. That is, ZO-SGDA (Algorithm 1) returns
iterates that satisfy $\min_{s\in\\{1,...,S\\}}\textsf{\text{E}}\,[\|\nabla
g(x_{s})\|_{2}^{2}]\leq\epsilon^{2}$. Moreover, the total number of calls to
the (deterministic) zeroth-order oracle, $K_{\mathcal{SZO}}$ is given by,

$K_{\mathcal{SZO}}=S(|\mathcal{M}_{1}|+|\mathcal{M}_{2}|)\sim\mathcal{O}\Bigl{(}\kappa^{5}(d_{1}\sigma_{1}^{2}+d_{2}\sigma_{2}^{2})\epsilon^{-4}\Bigr{)}.$

######  Remark 4.1.

The $\epsilon$-dependence of Algorithm 3 is the same compared to the first-
order counterpart considered in [LJJ19]. The $\kappa$-dependence is same as
our result in the deterministic case. Finally, the dimension-dependence is
linear, to account for the zeroth-order setting.

We now consider the stochastic version of Algorithm 2. Similar to the
deterministic case, we obtain an improved dependence on the condition number
$\kappa$. The algorithm is formally presented in Algorithm 4 and the
corresponding complexity result is provided in Theorem 4.2.

Algorithm 4 Zeroth-Order Stochastic Gradient Multi-Step Descent (ZO-SGDMSA)

Initialization: $\left(x_{0},y_{0}\right)$, step sizes
$\left(\eta_{1},\eta_{2}\right)$, iteration limit for outer loop $S>0$,
iteration limit for inner loop $T>0$, smoothing parameters $\mu_{1}$ and
$\mu_{2}$. Indices sets $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ with
cardinality $|\mathcal{M}_{1}|=4(d_{1}+6)(\sigma_{1}^{2}+1)\epsilon^{-2}$,
$|\mathcal{M}_{2}|=4(d_{2}+6)(\sigma_{2}^{2}+1)\epsilon^{-2}$.

for $s=1,\ldots,S$ do

Set $y_{0}(x_{s})\leftarrow y_{s}$

for $t=1,\ldots,T$ do

$y_{t}(x_{s})\leftarrow\text{Proj}_{\mathcal{Y}}\Bigl{[}y_{t-1}(x_{s})+\eta_{2}\frac{1}{|\mathcal{M}_{2}^{t}|}\sum_{i\in\mathcal{M}_{2}^{t}}H_{\mu_{2}}(x_{s},y_{t-1}(x_{s}),\boldsymbol{u}_{2,i},\xi_{i})\Bigr{]}$
with $\boldsymbol{u}_{2,i}\sim N(0,\boldsymbol{1}_{d_{2}})$

end for

$y_{s+1}\leftarrow y_{T}(x_{s})$

$x_{s+1}\leftarrow
x_{s}-\eta_{1}\frac{1}{|\mathcal{M}_{1}^{s}|}\sum_{i\in\mathcal{M}_{1}^{s}}G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{1,i},\xi_{i})$
with $\boldsymbol{u}_{1,i}\sim N(0,\boldsymbol{1}_{d_{1}})$

end for

Return $(x_{1},y_{1}),\ldots,(x_{S},y_{S})$.

######  Theorem 4.2.

Let $\epsilon\in(0,1)$. Under Assumption 2.1 and 2.2, by setting the
parameters in the same way as in Theorem 3.2, i.e., (13) and (14), ZO-SGDMSA
(Algorithm 4) returns iterates $(x_{1},y_{1}),\ldots,(x_{S},y_{S})$ such that
there exist an iterate which is an $\epsilon$-stationary point for
$g(x)=\max_{y\in\mathcal{Y}}f(x,y)$. That is, ZO-SGDA (Algorithm 1) returns
iterates that satisfy $\min_{s\in\\{1,...,S\\}}\textsf{\text{E}}\,[\|\nabla
g(x_{s})\|_{2}^{2}]\leq\epsilon^{2}$. Moreover, the total number of calls to
the (deterministic) zeroth-order oracle, $K_{\mathcal{SZO}}$ is given by,

$K_{\mathcal{SZO}}=S|\mathcal{M}_{1}|+TS|\mathcal{M}_{2}|\sim\mathcal{O}\Bigl{(}\kappa\epsilon^{-4}(d_{1}\sigma_{1}^{2}+\kappa
d_{2}\sigma_{2}^{2}\log(\epsilon^{-1}))\Bigr{)}.$

######  Remark 4.2.

Similar to the deterministic case, we improve the dependence of the query
complexity on $\kappa$. The dependence on $\epsilon$ and dimensionality remain
the same.

##  5 Summary and Discussion

In this paper, we analyzed zeroth-order algorithms for deterministic and
stochastic nonconvex minimax optimization problems. Specifically, we
considered two types of algorithms: the standard single-step gradient descent
ascent algorithm and a modified version with multiple ascent steps following
each descent step. We obtain oracle complexities for both algorithms that
match the performance of comparable first-order algorithms, up to unavoidable
dimensionality factors. A summary of our complexity results with those in
[LLC+19] for the zeroth-order setting is provided in Table 1. Note that we
provide improved complexity results in comparison to [LLC+19] for the zeroth-
order gradient descent algorithm. We emphasize that the improvement comes by
our use of mini-batch gradient estimators, along with an analysis of their
approximation properties (as in Lemma A.10 and Lemma A.11). Furthermore, in
Table 2, we compare with existing results on first-order method. We note that
we match the first-order algorithms in terms of dependence on $\epsilon$.
Finally, the linear dimension-dependence is natural in zeroth-order
optimization [DJWW15, NS17, BG18].

Algorithm | $K_{\mathcal{ZO}}/K_{\mathcal{SZO}}$ | Constrain $(x,y)$
---|---|---
ZO-min-max([LLC+19]) | $\mathcal{O}((d_{1}+d_{2})\epsilon^{-6})$ | C,C
ZO-GDA | $\mathcal{O}(\kappa^{5}(d_{1}+d_{2})\epsilon^{-2})$ | UC,C
ZO-GDMSA | $\mathcal{O}(\kappa(d_{1}+\kappa d_{2}\log(\epsilon^{-1}))\epsilon^{-2})$ | UC,C/UC
ZO-SGDA | $\mathcal{O}(\kappa^{5}(\sigma_{1}^{2}d_{1}+\sigma_{2}^{2}d_{2})\epsilon^{-4})$ | UC,C/UC
ZO-SGDMSA | $\mathcal{O}(\kappa(d_{1}\sigma_{1}^{2}+\kappa d_{2}\sigma_{2}^{2}\log(\epsilon^{-1}))\epsilon^{-4})$ | UC,C
Table 1: Zeroth-Order query complexity different algorithms:
$K_{\mathcal{ZO}}$ denotes the complexity of zeroth order oracle in
deterministic case; $K_{\mathcal{SZO}}$ denotes the complexity of stochastic
zeroth-order oracle. All algorithms assume the objective function is nonconvex
and strongly-concave. C denotes ‘constrained’ and UC denotes ‘unconstrained’.

Algorithm | Order | Complexity | Objective function | Constraint $(x,y)$
---|---|---|---|---
GDmax ([LJJ19]) | 1st | $\mathcal{O}(\kappa^{2}\epsilon^{-2})$ | NC-SC | UC,C
SGDmax ([LJJ19]) | 1st | $\mathcal{O}(\kappa^{3}(\sigma_{1}^{2}+\sigma_{2}^{2})\epsilon^{-4})$ | NC-SC | UC,C
Multi-step GDA([NSH+19]) | 1st | $\mathcal{O}(\log(\epsilon^{-1})\epsilon^{-2})$ | NC-PL | C,UC
Multi-step GDA ([NSH+19]) | 1st | $\mathcal{O}(\log(\epsilon^{-1})\epsilon^{-3.5})$ | NC-C | C,C
ZO-GDMSA | 0th | $\mathcal{O}(\kappa(d_{1}+\kappa d_{2}\log(\epsilon^{-1}))\epsilon^{-2})$ | NC-SC | UC,C
ZO-SGDMSA | 0th | $\mathcal{O}(\kappa(d_{1}\sigma_{1}^{2}+\kappa d_{2}\sigma_{2}^{2}\log(\epsilon^{-1}))\epsilon^{-4})$ | NC-SC | UC,C

Table 2: Comparison of results from [LJJ19] in the first-order setting and our
methods in the zeroth-order setting. In the constraint column C denotes
‘constrained’ and UC denotes ‘unconstrained’. In the ‘Objective function’
column, C denotes convex, SC denotes strongly-convex, NC denotes nonconvex,
and PL denotes Polyak-Łojasiewicz . Complexity refers to calls to the
(stochastic) gradient oracle for first-order algorithms and calls to the
(stochastic) zeroth-order oracle for the zeroth-order algorithms.

There are several avenues for future work. First, it is interesting to explore
lower bounds for zeroth-order nonconvex minimax optimization problems. Next,
it is worth exploring various structural constraints (for example, sparsity)
to obtain improved dimensionality dependence. Furthermore, developing zeroth-
order algorithms for non-smooth problems, and developing algorithms for
general nonconvex and nonconcave objective are very interesting and
challenging.

##  Appendix A Technical Preparations

In this section we present some technical results that will be used in our
subsequent convergence analysis. First, we need the follow elementary results
regarding random variables.

######  Lemma A.1.

  * •

For i.i.d. random (vector) variables $\boldsymbol{X}_{i}$, $i=1,\ldots,N$ with
zero mean, we have
$\textsf{\text{E}}\,\|\frac{1}{N}\sum_{i=1}^{N}\boldsymbol{X}_{i}\|_{2}^{2}=\frac{1}{N}\textsf{\text{E}}\,\|\boldsymbol{X}_{1}\|_{2}^{2}$.

  * •

For random (vector) variable $\boldsymbol{X}$, we have
$\textsf{\text{E}}\,\|\boldsymbol{X}-\textsf{\text{E}}\,\boldsymbol{X}\|_{2}^{2}=\textsf{\text{E}}\,(\|\boldsymbol{X}\|_{2}^{2})-(\|\textsf{\text{E}}\,\boldsymbol{X}\|_{2}^{2})\leq\textsf{\text{E}}\,\|\boldsymbol{X}\|_{2}^{2}$
and
$\|\textsf{\text{E}}\,\boldsymbol{X}\|_{2}^{2}\leq\textsf{\text{E}}\,\|\boldsymbol{X}\|_{2}^{2}$.

The following results regarding Lipschitz and strongly convex functions are
also useful.

######  Lemma A.2.

[Nes04, Lemma 1.2.3, Theorem 2.1.8, Theorem 2.1.10]

  * •

Suppose a function $h$ is $L_{h}$ gradient-Lipschitz and has a unique
maximizer $x^{*}$. Then, for any $x$, we have:

$\frac{1}{2L_{h}}\|\nabla h(x)\|_{2}^{2}\leq
h(x^{*})-h(x)\leq\frac{L_{h}}{2}\|x-x^{*}\|_{2}^{2}.$ (15)

  * •

Suppose a function $h$ is $\tau_{h}$ strongly concave and has a unique
maximizer $x^{*}$. Then, for any $x$, we have:

$\frac{\tau_{h}}{2}\|x-x^{*}\|_{2}^{2}\leq
h(x^{*})-h(x)\leq\frac{1}{2\tau_{h}}\|\nabla h(x)\|_{2}^{2}.$ (16)

The following lemmas are from existing literature and we omit their proofs.

######  Lemma A.3.

[LJJ19, Lemma 3.3] The function $g(\cdot):=\max_{y\in\mathcal{Y}}f(\cdot,y)$
is $L_{g}:=(\ell+\kappa\ell)$-gradient Lipschitz, and $\nabla
g(x)=\nabla_{x}f(x,y^{*}(x))$. Moreover,
$y^{*}(x)=\operatorname*{arg\,max}_{y\in\mathcal{Y}}f(\cdot,y)$ is
$\kappa$-Lipschitz.

######  Lemma A.4.

[NS17, Section 2]
$f_{\mu}(x)=\textsf{\text{E}}\,_{\boldsymbol{u}}f_{\mu}(x+\mu\boldsymbol{u})$
is a convex function, if $f(x)$ is convex.

######  Lemma A.5.

[NS17, Theorem 1] Under Assumption 2.1, it holds that

$|f_{\mu_{2}}(x,y)-f(x,y)|\leq\frac{\mu_{2}^{2}}{2}\ell d_{2},\forall
x\in\mathbb{R}^{d_{1}},y\in\mathcal{Y}.$

######  Lemma A.6.

[NS17, Lemma 3] Under Assumption 2.1, it holds that

$\|\nabla_{x}f_{\mu_{1}}(x,y)-\nabla_{x}f(x,y)\|_{2}^{2}\leq\frac{\mu_{1}^{2}}{4}\ell^{2}(d_{1}+3)^{3},\
\|\nabla_{y}f_{\mu_{2}}(x,y)-\nabla_{y}f(x,y)\|_{2}^{2}\leq\frac{\mu_{2}^{2}}{4}\ell^{2}(d_{2}+3)^{3}.$

######  Lemma A.7.

[NS17, Lemma 4] Under Assumption 2.1, it holds that

$\|\nabla_{x}f(x,y)\|_{2}^{2}\leq
2\|\nabla_{x}f_{\mu_{1}}(x,y)\|_{2}^{2}+\ell^{2}\mu_{1}^{2}(d_{1}+3)^{3}/2.$

######  Lemma A.8.

[NS17, Theorem 4] Under Assumptions 2.1 and 2.2, we have

$\textsf{\text{E}}\,_{\boldsymbol{u}_{1}}\|G_{\mu_{1}}(x,y,\boldsymbol{u}_{1})\|_{2}^{2}\leq
2(d_{1}+4)\|\nabla_{x}f(x,y)\|_{2}^{2}+\mu_{1}^{2}\ell^{2}(d_{1}+6)^{3}/2,$
$\textsf{\text{E}}\,_{\boldsymbol{u}_{2}}\|H_{\mu_{2}}(x,y,\boldsymbol{u}_{2})\|_{2}^{2}\leq
2(d_{2}+4)\|\nabla_{y}f(x,y)\|_{2}^{2}+\mu_{2}^{2}\ell^{2}(d_{2}+6)^{3}/2.$

######  Lemma A.9.

[BG18] Under Assumptions 2.1 and 2.2, we have

$\textsf{\text{E}}\,_{\boldsymbol{u}_{1},\xi}\|G_{\mu_{1}}(x,y,\boldsymbol{u}_{1},\xi)\|_{2}^{2}\leq\frac{\mu_{1}^{2}\ell^{2}}{2}(d_{1}+6)^{3}+2\Bigl{[}\|\nabla_{x}f(x,y)\|_{2}^{2}+\sigma_{1}^{2}\Bigr{]}(d_{1}+4),$
$\textsf{\text{E}}\,_{\boldsymbol{u}_{2},\xi}\|H_{\mu_{2}}(x,y,\boldsymbol{u}_{2},\xi)\|_{2}^{2}\leq\frac{\mu_{2}^{2}\ell^{2}}{2}(d_{2}+6)^{3}+2\Bigl{[}\|\nabla_{y}f(x,y)\|_{2}^{2}+\sigma_{2}^{2}\Bigr{]}(d_{2}+4).$

We now bound the size of the mini-batch zeroth-order gradient estimator (8).

######  Lemma A.10.

Under Assumption 2.1 and choosing $q_{1}=2(d_{1}+6)$, $q_{2}=2(d_{2}+6)$. For
any $x\in\mathbb{R}^{d_{1}},y\in\mathcal{Y}$, we have

$\begin{array}[]{ll}\textsf{\text{E}}\,_{\boldsymbol{u}_{1,[q_{1}]}}\|G_{\mu_{1}}(x,y,\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}&\leq
3\|\nabla_{x}f(x,y)\|_{2}^{2}+\mu_{1}^{2}\ell^{2}(d_{1}+6)^{3},\\\
\textsf{\text{E}}\,_{\boldsymbol{u}_{2,[q_{2}]}}\|H_{\mu_{2}}(x,y,\boldsymbol{u}_{2,[q_{2}]})\|_{2}^{2}&\leq
3\|\nabla_{y}f(x,y)\|_{2}^{2}+\mu_{2}^{2}\ell^{2}(d_{2}+6)^{3}.\end{array}$
(17)

###### Proof.

Since
$\textsf{\text{E}}\,_{\boldsymbol{u}_{1,[q_{1}]}}G_{\mu_{1}}(x,y,\boldsymbol{u}_{1,[q_{1}]})=\nabla_{x}f_{\mu_{1}}(x,y)$,
we have

$\begin{array}[]{ll}&\textsf{\text{E}}\,_{\boldsymbol{u}_{1,[q_{1}]}}\|G_{\mu_{1}}(x,y,\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}\\\
=&\textsf{\text{E}}\,_{\boldsymbol{u}_{1,[q_{1}]}}\|G_{\mu_{1}}(x,y,\boldsymbol{u}_{1,[q_{1}]})-\nabla_{x}f_{\mu_{1}}(x,y)\|_{2}^{2}+\|\nabla_{x}f_{\mu_{1}}(x,y)\|_{2}^{2}\\\
=&\frac{1}{q_{1}}\textsf{\text{E}}\,_{\boldsymbol{u}_{1}}\|G_{\mu_{1}}(x,y,\boldsymbol{u}_{1})-\nabla_{x}f_{\mu_{1}}(x,y)\|_{2}^{2}+\|\nabla_{x}f_{\mu_{1}}(x,y)\|_{2}^{2}\\\
\leq&\frac{1}{q_{1}}\textsf{\text{E}}\,_{\boldsymbol{u}_{1}}\|G_{\mu_{1}}(x,y,\boldsymbol{u}_{1})\|_{2}^{2}+2\|\nabla_{x}f(x,y)\|_{2}^{2}+2\|\nabla_{x}f_{\mu_{1}}(x,y)-\nabla_{x}f(x,y)\|_{2}^{2}\\\
\leq&\frac{2(d_{1}+4)}{q_{1}}\|\nabla_{x}f(x,y)\|_{2}^{2}+2\|\nabla_{x}f(x,y)\|_{2}^{2}+\frac{\ell^{2}\mu_{1}^{2}(d_{1}+3)^{3}}{2}+\frac{\mu_{1}^{2}\ell^{2}(d_{1}+6)^{3}}{2q_{1}},\end{array}$

where the second equality is due to Lemma A.1, and the last inequality is due
to Lemma A.8. Thus, the first inequality in (17) is obtained by noting
$q_{1}=2(d_{1}+6)$. The other inequality can be proved similarly and we omit
the details for succinctness. ∎

A similar result can be obtained for the stochastic zeroth-order gradient
estimator (9).

######  Lemma A.11.

Under Assumptions 2.1 and 2.2, for given tolerance $\epsilon\in(0,1)$, by
choosing $|\mathcal{M}_{1}|=4(d_{1}+6)(\sigma_{1}^{2}+1)\epsilon^{-2}$,
$|\mathcal{M}_{2}|=4(d_{2}+6)(\sigma_{2}^{2}+1)\epsilon^{-2}$, for any
$x\in\mathbb{R}^{d_{1}}$, $y\in\mathcal{Y}$, we have:

$\begin{array}[]{ll}\textsf{\text{E}}\,_{\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}}}\|G_{\mu_{1}}(x,y,\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}&\leq
3\|\nabla_{x}f(x,y)\|_{2}^{2}+\varrho_{1}(\epsilon,\mu_{1}),\\\
\textsf{\text{E}}\,_{\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}}}\|H_{\mu_{2}}(x,y,\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}})\|_{2}^{2}&\leq
3\|\nabla_{y}f(x,y)\|_{2}^{2}+\varrho_{2}(\epsilon,\mu_{2}).\end{array}$ (18)

where
$\varrho_{1}(\epsilon,\mu_{1}):=\epsilon^{2}/2+\mu_{1}^{2}\ell^{2}(d_{1}+3)^{3}/2+\mu_{1}^{2}\ell^{2}(d_{1}+6)^{2}\epsilon^{2}/8$,
and
$\varrho_{2}(\epsilon,\mu_{2}):=\epsilon^{2}/2+\mu_{2}^{2}\ell^{2}(d_{2}+3)^{3}/2+\mu_{2}^{2}\ell^{2}(d_{2}+6)^{2}\epsilon^{2}/8$.

###### Proof.

Since
$\textsf{\text{E}}\,_{\xi_{\mathcal{M}_{1}},\boldsymbol{u}_{\mathcal{M}_{1}}}G_{\mu_{1}}(x,y,\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})=\nabla_{x}f_{\mu_{1}}(x,y)$,
we have

$\begin{array}[]{ll}&\textsf{\text{E}}\,_{\xi_{\mathcal{M}_{1}},\boldsymbol{u}_{\mathcal{M}_{1}}}\|G_{\mu_{1}}(x,y,\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}\\\
=&~{}\textsf{\text{E}}\,_{\xi_{\mathcal{M}_{1}},\boldsymbol{u}_{\mathcal{M}_{1}}}\|G_{\mu_{1}}(x,y,\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})-\nabla_{x}f_{\mu_{1}}(x,y)\|_{2}^{2}+\|\nabla_{x}f_{\mu_{1}}(x,y)\|_{2}^{2}\\\
=&~{}\frac{1}{|\mathcal{M}_{1}|}\textsf{\text{E}}\,_{\xi_{1},\boldsymbol{u}_{1}}\|G_{\mu_{1}}(x,y,\boldsymbol{u}_{1},\xi)\|_{2}^{2}+\|\nabla_{x}f_{\mu_{1}}(x,y)\|_{2}^{2}\\\
\leq&~{}\frac{1}{|\mathcal{M}_{1}|}\Bigl{[}\frac{\mu_{1}^{2}L_{1}^{2}}{2}(d_{1}+6)^{3}+2\Bigl{[}\|\nabla_{x}f(x,y)\|_{2}^{2}+\sigma_{1}^{2}\Bigr{]}(d_{1}+4)\Bigr{]}+2\|\nabla_{x}f(x,y)\|_{2}^{2}+\mu_{1}^{2}\ell^{2}(d_{1}+3)^{3}/2\\\
\leq&~{}\frac{2(d_{1}+4)}{|\mathcal{M}_{1}|}\|\nabla_{x}f(x,y)\|_{2}^{2}+2\|\nabla_{x}f(x,y)\|_{2}^{2}+\frac{2(d_{1}+4)\sigma_{1}^{2}}{|\mathcal{M}_{1}|}+\mu_{1}^{2}\ell^{2}(d_{1}+3)^{3}/2+\frac{\mu_{1}^{2}\ell^{2}}{2|\mathcal{M}_{1}|}(d_{1}+6)^{3},\end{array}$

where the second equality is due to Lemma A.1, the first inequality is due to
Lemma A.9 and A.6. Substituting
$|\mathcal{M}_{1}|=4(d_{1}+6)(\sigma_{1}^{2}+1)\epsilon^{-2}$ proves the first
inequality in (18). The other inequality can be proved similarly and we omit
the details for succinctness. ∎

The following result shows that $\nabla_{x}f_{\mu_{1}}(x,y)$ is Lipschitz
continuous with respect to $y$.

######  Lemma A.12.

Under Assumption 2.1, for any $x\in\mathbb{R}^{d_{1}}$,
$y_{1},y_{2}\in\mathcal{Y}$, it holds that

$\|\nabla_{x}f_{\mu_{1}}(x,y_{1})-\nabla_{x}f_{\mu_{1}}(x,y_{2})\|_{2}\leq\ell\|y_{1}-y_{2}\|_{2}.$

###### Proof.

Following the definition of $f_{\mu_{1}}$, Assumption 2.1, and Jensen’s
inequality, it holds that

$\begin{array}[]{ll}&~{}\|\nabla_{x}f_{\mu_{1}}(\boldsymbol{x},y_{1})-\nabla_{x}f_{\mu_{1}}(\boldsymbol{x},y_{2})\|_{2}\\\
=&~{}\|\textsf{\text{E}}\,_{\boldsymbol{u}_{1}}\nabla_{x}f(\boldsymbol{x}+\mu_{1}\boldsymbol{u}_{1},y_{1})-\textsf{\text{E}}\,_{\boldsymbol{u}_{1}}\nabla_{x}f(\boldsymbol{x}+\mu_{1}\boldsymbol{u},y_{2})\|_{2}\\\
\leq&~{}\textsf{\text{E}}\,_{\boldsymbol{u}_{1}}\|\nabla_{x}f(\boldsymbol{x}+\mu_{1}\boldsymbol{u}_{1},y_{1})-\nabla_{x}f(\boldsymbol{x}+\mu_{1}\boldsymbol{u}_{1},y_{2})\|_{2}\\\
{\leq}&\ell\|y_{1}-y_{2}\|_{2},\end{array}$

which proves the desired result. ∎

##  Appendix B Convergence analysis of ZO-GDA (Algorithm 1)

We first show the following inequality.

######  Lemma B.1.

Assume $\\{(x_{s},y_{s})\\}$ is the sequence generated by Algorithm 1. By
setting $\eta_{2}=1/(6\ell)$, the following inequality holds:

$\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s}\|_{2}^{2}\leq\Bigl{(}1-1/(12\kappa)\Bigr{)}\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|_{2}^{2}+\varrho(\mu_{2}),$
(19)

where $\varrho(\mu_{2})=\mu_{2}^{2}d_{2}/6+\mu_{2}^{2}(d_{2}+6)^{3}/36$.

###### Proof.

According to the updates in Algorithm 1, we have

$\begin{array}[]{lll}\|y^{*}(x_{s-1})-y_{s}\|^{2}&=&\|\mathrm{Proj}_{\mathcal{Y}}(y_{s-1}+\eta_{2}H_{\mu_{2}}(x_{s-1},y_{s-1},\boldsymbol{u}_{2,[q_{2}]})-y^{*}(x_{s-1}))\|_{2}^{2}\\\
&\leq&\|y^{*}(x_{s-1})-y_{s-1}\|^{2}+2\eta_{2}\langle
H_{\mu_{2}}(x_{s-1},y_{s-1},\boldsymbol{u}_{2,[q_{2}]}),y_{s-1}-y^{*}(x_{s})\rangle\\\
&&+\eta_{2}^{2}\|H_{\mu_{2}}(x_{s-1},y_{s-1},\boldsymbol{u}_{2,[q_{2}]})\|_{2}^{2}.\end{array}$

For a given $s$, denote by E taking expectation with respect to random samples
$\boldsymbol{u}_{2,[q_{2}]}$ conditioned on all previous iterations. By taking
expectation to both sides of the above inequality, we obtain

$\begin{array}[]{ll}&\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s}\|^{2}\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|^{2}-2\eta_{2}\langle-\nabla_{y}f_{\mu_{2}}(x_{s-1},y_{s-1}),y_{s-1}-y^{*}(x_{s})\rangle+\eta_{2}^{2}\textsf{\text{E}}\,\|H_{\mu_{2}}(x_{s-1},y_{s-1},\boldsymbol{u}_{2,[q_{2}]})\|_{2}^{2}\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|^{2}-2\eta_{2}[f_{\mu_{2}}(x_{s-1},y^{*}(x_{s}))-f_{\mu_{2}}(x_{s-1},y_{s-1})]\\\
&+\eta_{2}^{2}\Bigl{(}3\|\nabla_{y}f(x_{s-1},y_{s-1})\|_{2}^{2}+\mu_{2}^{2}\ell^{2}(d_{2}+6)^{3}\Bigr{)}\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|^{2}-2\eta_{2}(f(x_{s-1},y^{*}(x_{s}))-f(x_{s-1},y_{s-1}))+\mu_{2}^{2}d_{2}\eta_{2}\ell\\\
&+\eta_{2}^{2}(6\ell(f(x_{s-1},y^{*}(x_{s}))-f(x_{s-1},y_{s-1}))+\eta_{2}^{2}\mu_{2}^{2}\ell^{2}(d_{2}+6)^{3}\\\
=&\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|^{2}-(f(x_{s-1},y^{*}(x_{s}))-f(x_{s-1},y_{s-1}))/(6\ell)+\varrho(\mu_{2})\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|^{2}\Bigl{(}1-\frac{\tau}{12\ell}\Bigr{)}+\varrho(\mu_{2}),\end{array}$

where the second inequality is due to the concavity of $f_{\mu_{2}}$ (see
Lemma A.4) and Lemma A.10, the third inequality is due to Lemma A.2 and Lemma
A.5, the equality is due to $\eta_{2}=1/(6\ell)$, and the last inequality is
due to Lemma A.2. This completes the proof. ∎

We now prove the following upper bound of
$\textsf{\text{E}}\,\|y_{s}-y^{*}(x_{s})\|_{2}^{2}$.

######  Lemma B.2.

Consider ZO-GDA (Algorithm 1). Use the same notation and the same assumptions
as in Lemma B.1. Denote $\delta_{s}=\|y_{s}-y^{*}(x_{s})\|_{2}^{2}$ and set
$\eta_{1}$ as in (11), and

$\gamma:=1-\frac{1}{24\kappa}+144\ell^{2}\kappa^{3}\eta_{1}^{2}\leq
1-\frac{5}{144\kappa}<1.$ (20)

It holds that

$\textsf{\text{E}}\,\delta_{s}\leq\gamma^{s}\textsf{\text{E}}\,\delta_{0}+\alpha_{1}\sum_{i=0}^{s-1}\gamma^{s-1-i}\textsf{\text{E}}\,\|\nabla
g(x_{i-1})\|_{2}^{2}+\theta_{0}\sum_{i=0}^{s-1}\gamma^{s-1-i},$ (21)

where

$\alpha_{1}=\frac{9}{12^{8}\kappa(\kappa+1)^{4}(\ell+1)^{2}},\
\theta_{0}=\alpha_{2}\mu_{1}^{2}(d_{1}+6)^{3}+2\varrho(\mu_{2}),\
\alpha_{2}=\frac{1}{8\times 12^{7}\kappa(\kappa+1)^{4}}.$ (22)

###### Proof.

Define the filtration
$\mathcal{F}_{s}=\Bigl{\\{}x_{s},y_{s},x_{s-1},y_{s-1},...,x_{1},y_{1}\Bigr{\\}}$.
Let
$\zeta_{s}=(\boldsymbol{u}_{1,i\in[q_{1}]},\boldsymbol{u}_{2,i\in[q_{2}]}),\zeta_{[s]}=(\zeta_{1},\zeta_{2},...,\zeta_{s})$.
Denote by E taking expectation w.r.t $\zeta_{[s]}$ conditioned on
$\mathcal{F}_{s}$ and then taking expectation over $\mathcal{F}_{s}$. Since
$\kappa>1$, using the Young’s inequality, we have

$\begin{array}[]{ll}\textsf{\text{E}}\,\delta_{s}&=\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s}\|_{2}^{2}\\\
&\leq\Bigl{(}1+\frac{1}{2(12\kappa-1)}\Bigr{)}\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s}\|_{2}^{2}+\Bigl{(}1+2(12\kappa-1)\Bigr{)}\textsf{\text{E}}\,\|y^{*}(x_{s})-y^{*}(x_{s-1})\|_{2}^{2}\\\
&\leq(1-\frac{1}{24\kappa-1})(1-\frac{1}{12\kappa})\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s}\|_{2}^{2}+24\kappa\textsf{\text{E}}\,\|y^{*}(x_{s})-y^{*}(x_{s-1})\|_{2}^{2}+2\varrho(\mu_{2})\\\
&\leq(1-\frac{1}{24\kappa})\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|_{2}^{2}+24\kappa^{3}\textsf{\text{E}}\,\|x_{s}-x_{s-1}\|_{2}^{2}+2\varrho(\mu_{2})\\\
&=(1-\frac{1}{24\kappa})\textsf{\text{E}}\,\delta_{s-1}+24\kappa^{3}\eta_{1}^{2}\textsf{\text{E}}\,\|G_{\mu_{1}}(x_{s-1},y_{s-1},\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}+2\varrho(\mu_{2})\\\
&=(1-\frac{1}{24\kappa})\textsf{\text{E}}\,\delta_{s-1}+\frac{\alpha_{1}}{6}\textsf{\text{E}}\,\|G_{\mu_{1}}(x_{s-1},y_{s-1},\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}+2\varrho(\mu_{2}),\end{array}$
(23)

where the second inequality is due to (19), the third inequality is due to
Lemma A.3. From Lemma A.10, we have

$\begin{array}[]{ll}&\textsf{\text{E}}\,_{\boldsymbol{u}_{1,[q_{1}]}}\|G_{\mu_{1}}(x_{s-1},y_{s-1},\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}\\\
\leq&3\textsf{\text{E}}\,\|\nabla_{x}f(x_{s-1},y_{s-1})\|_{2}^{2}+\mu_{1}^{2}\ell^{2}(d_{1}+6)^{3}\\\
\leq&6\textsf{\text{E}}\,\|\nabla
g(x_{s-1})\|_{2}^{2}+6\ell^{2}\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|_{2}^{2}+\mu_{1}^{2}\ell^{2}(d_{1}+6)^{3},\end{array}$
(24)

where the second inequality is due to Assumption 2.1. Combining (23) and (24)
yields (21) by noting (20). ∎

Now we are ready to prove Theorem 3.1.

###### Proof of Theorem 3.1..

First, the following inequalities hold:

$\begin{array}[]{ll}&g(x_{s+1})\\\ \leq&g(x_{s})-\eta_{1}\langle\nabla
g(x_{s}),G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{1,[q_{1}]})\rangle+\frac{1}{2}L_{g}\eta_{1}^{2}\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}\\\
=&g(x_{s})-\eta_{1}\Bigl{\langle}\nabla_{x}f(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))+\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y_{s})\\\
&+\nabla_{x}f_{\mu_{1}}(x_{s},y_{s}),G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{1,[q_{1}]})\Bigr{\rangle}+\frac{1}{2}L_{g}\eta_{1}^{2}\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}\\\
\leq&g(x_{s})+\|\nabla_{x}f(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))\|^{2}/L_{g}+\frac{L_{g}\eta_{1}^{2}}{4}\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{1,[q_{1}]})\|^{2}\\\
&+\|\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y_{s})\|^{2}/L_{g}+\frac{L_{g}\eta_{1}^{2}}{4}\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{1,[q_{1}]})\|^{2}\\\
&-\eta_{1}\langle\nabla_{x}f_{\mu_{1}}(x_{s},y_{s}),G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{1,[q_{1}]})\rangle+\frac{1}{2}L_{g}\eta_{1}^{2}\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}\\\
\leq&g(x_{s})+\frac{\ell^{2}}{L_{g}}\|y^{*}(x_{s})-y_{s}\|_{2}^{2}-\eta_{1}\langle\nabla_{x}f_{\mu_{1}}(x_{s},y_{s}),G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{1,[q_{1}]})\rangle\\\
&+\eta_{1}^{2}L_{g}\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}+\frac{\mu_{1}^{2}}{4L_{g}}\ell^{2}(d_{1}+3)^{3},\end{array}$

where the first inequality is due to Lemma A.3 and the Descent lemma, the
second inequality is due to Young’s inequality, and the last inequality is due
to Lemmas A.6 and A.12. Now take expectation with respect to
$\boldsymbol{u}_{1,[q_{1}]}$ to the above inequality, we get:

$\begin{array}[]{lll}\eta_{1}\textsf{\text{E}}\,\|\nabla_{x}f_{\mu_{1}}(x_{s},y_{s})\|_{2}^{2}&\leq&\textsf{\text{E}}\,g(x_{s})-\textsf{\text{E}}\,g(x_{s+1})+\frac{\ell^{2}}{L_{g}}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s}\|_{2}^{2}\\\
&&+\eta_{1}^{2}L_{g}\textsf{\text{E}}\,\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}+\frac{\mu_{1}^{2}}{4L_{g}}\ell^{2}(d_{1}+3)^{3}.\end{array}$
(25)

From Lemma A.12, we have

$\eta_{1}\textsf{\text{E}}\,\|\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))\|_{2}^{2}\leq
2\eta_{1}\textsf{\text{E}}\,\|\nabla_{x}f_{\mu_{1}}(x_{s},y_{s})\|_{2}^{2}+2\eta_{1}\ell^{2}\|y_{s}-y^{*}(x_{s})\|_{2}^{2}.$
(26)

From Lemma A.6, we have

$\eta_{1}\|\nabla g(x_{s})\|_{2}^{2}\leq
2\eta_{1}\|\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))\|_{2}^{2}+\frac{\eta_{1}\mu_{1}^{2}}{2}\ell^{2}(d_{1}+3)^{3}.$
(27)

Combining (24), (25), (26), (27) yields,

$\begin{array}[]{ll}&\eta_{1}\textsf{\text{E}}\,\|\nabla g(x_{s})\|_{2}^{2}\\\
\leq&4\textsf{\text{E}}\,g(x_{s})-4\textsf{\text{E}}\,g(x_{s+1})+\Bigl{(}\frac{4\ell^{2}}{L_{g}}+4\eta_{1}\ell^{2}\Bigr{)}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s}\|_{2}^{2}+\frac{\mu_{1}^{2}}{L_{g}}\ell^{2}(d_{1}+3)^{3}+\frac{\eta_{1}\mu_{1}^{2}}{2}\ell^{2}(d_{1}+3)^{3}\\\
&+4\eta_{1}^{2}L_{g}\Bigl{[}6\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}+6\ell^{2}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s}\|_{2}^{2}+\mu_{1}^{2}\ell^{2}(d_{1}+6)^{3}\Bigr{]}\\\
=&4\textsf{\text{E}}\,g(x_{s})-4\textsf{\text{E}}\,g(x_{s+1})+24\eta_{1}^{2}L_{g}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}+\theta_{1}\textsf{\text{E}}\,\delta_{s}+\theta_{2},\end{array}$
(28)

where

$\theta_{1}=\frac{4\ell^{2}}{L_{g}}+4\eta_{1}\ell^{2}+24\eta_{1}^{2}L_{g}\ell^{2}\leq
4\ell+4\eta_{1}\ell^{2}+24\eta_{1}^{2}\ell^{3}(\kappa+1)$ (29)

and

$\displaystyle\theta_{2}=~{}$
$\displaystyle\frac{\mu_{1}^{2}}{L_{g}}\ell^{2}(d_{1}+3)^{3}+\frac{\eta_{1}\mu_{1}^{2}}{2}\ell^{2}(d_{1}+3)^{3}+4\eta_{1}^{2}L_{g}\mu_{1}^{2}\ell^{2}(d_{1}+6)^{3}$
$\displaystyle\leq~{}$
$\displaystyle\mu_{1}^{2}\ell(d_{1}+3)^{3}+\frac{\eta_{1}\mu_{1}^{2}}{2}\ell^{2}(d_{1}+3)^{3}+4\eta_{1}^{2}(\kappa+1)\ell^{3}\mu_{1}^{2}(d_{1}+6)^{3}$
(30)

where we have used the definition of $L_{g}:=\ell(\kappa+1)$. Taking sum over
$s=0,\ldots,S$ to both sides of (21), we get

$\sum_{s=0}^{S}\textsf{\text{E}}\,\delta_{s}\leq\sum_{s=0}^{S}\gamma^{s}\textsf{\text{E}}\,\delta_{0}+\alpha_{1}\sum_{s=0}^{S}\sum_{i=0}^{s-1}\gamma^{s-1-i}\textsf{\text{E}}\,\|\nabla
g(x_{i-1})\|_{2}^{2}+\theta_{0}\sum_{s=0}^{S}\sum_{i=0}^{s-1}\gamma^{s-1-i}.$
(31)

Moreover, from (20) it is easy to obtain

$\sum_{s=0}^{S}\gamma^{s}\leq
36\kappa,\quad\sum_{s=0}^{S}\sum_{i=0}^{s-1}\gamma^{s-1-i}\leq 36\kappa(S+1),$
(32)

and

$\sum_{s=0}^{S}\sum_{i=0}^{s-1}\gamma^{s-1-i}\textsf{\text{E}}\,\|\nabla
g(x_{i-1})\|_{2}^{2}\leq 36\kappa\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}.$ (33)

Substituting (32) and (33) into (31), we obtain

$\sum_{s=0}^{S}\textsf{\text{E}}\,\delta_{s}\leq
36\kappa\textsf{\text{E}}\,\delta_{0}+36\kappa\alpha_{1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}+36\kappa\theta_{0}(S+1).$ (34)

Now, summing (28) over $s=0,\ldots,S$ yields

$\begin{array}[]{ll}&\eta_{1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}\\\
=&4\textsf{\text{E}}\,g(x_{0})-4\textsf{\text{E}}\,g(x_{S+1})+24\eta_{1}^{2}L_{g}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}+\theta_{1}\sum_{s=0}^{S}\textsf{\text{E}}\,\delta_{s}+(S+1)\theta_{2}\\\
\leq&4\textsf{\text{E}}\,g(x_{0})-4\textsf{\text{E}}\,g(x_{S+1})+24\eta_{1}^{2}L_{g}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}\\\
&+\theta_{1}[36\kappa\textsf{\text{E}}\,\delta_{0}+36\kappa\alpha_{1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}+36\kappa\theta_{0}(S+1)]+(S+1)\theta_{2}\end{array}$ (35)

where the second inequality is from (34). Using (29), (22) and (11), it is
easy to verify that

$36\kappa\theta_{1}\alpha_{1}\leq\left(\frac{108}{3\times
12^{3}}+\frac{108}{12^{7}}+\frac{54}{4\times 12^{10}}\right)\eta_{1}\leq
0.021\eta_{1},$

which together with $L_{g}:=(\kappa+1)\ell$ yields

$36\kappa\theta_{1}\alpha_{1}+24\eta_{1}^{2}L_{g}\leq
0.021\eta_{1}+0.0003\eta_{1}=0.0213\eta_{1}.$ (36)

Combining (35) and (36) yields

$\begin{array}[]{ll}&0.9787\eta_{1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}\\\
\leq&4\textsf{\text{E}}\,g(x_{0})-4\textsf{\text{E}}\,g(x_{S+1})+\theta_{1}[36\kappa\textsf{\text{E}}\,\delta_{0}+36\kappa\theta_{0}(S+1)]+(S+1)\theta_{2}.\end{array}$
(37)

Dividing both sides of (38) by $0.9787\eta_{1}(S+1)$ yields

$\begin{array}[]{ll}\frac{1}{S+1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}\leq\frac{4\Delta_{g}}{0.9787\eta_{1}(S+1)}+\frac{36\kappa\theta_{1}\textsf{\text{E}}\,\delta_{0}}{0.9787\eta_{1}(S+1)}+\frac{36\kappa\theta_{1}\theta_{0}}{0.9787\eta_{1}}+\frac{\theta_{2}}{0.9787\eta_{1}},\end{array}$
(38)

where $\Delta_{g}:=g(x_{0})-\min_{x\in\mathbb{R}^{d_{1}}}g(x)$. Now we only
need to upper bound the right hand side of (38) by $\epsilon^{2}$, and this
can be guaranteed by choosing the parameters as in (12). This completes the
proof of Theorem 3.1. ∎

######  Remark B.1.

Note that the term $\delta_{0}$ appearing in (38) is defined as
$\delta_{0}:=\|y_{0}-y^{*}(x_{0})\|_{2}^{2}$. Under the assumption that the
set $\mathcal{Y}$ is bounded, this term could be upper bounded by $D^{2}$.
This is the only place in the proof where we require the constraint set
$\mathcal{Y}$ to be bounded. In the unconstrained case, when
$\mathcal{Y}:=\mathbb{R}^{d_{2}}$, having $\delta_{0}$ being bounded away from
infinity is dependent on the initial values $(x_{0},y_{0})$ supplied to the
algorithm. Hence, as long as the initial values are such that
$\|y_{0}-y^{*}(x_{0})\|_{2}^{2}$ is bounded, the same result hold for the ZO-
GDA algorithm. Indeed this scenario is common in the complexity analysis of
optimization algorithms [Nes18].

##  Appendix C Convergence analysis of ZO-GDMSA (Algorithm 2)

First, we show the following iteration complexity of the inner loop for $y$ in
Algorithm 2.

######  Lemma C.1.

In Algorithm 2, setting $\eta_{2}=1/(6\ell)$,
$\mu_{2}=\mathcal{O}(\kappa^{-1/2}d_{2}^{-3/2}\epsilon)$ and
$T=\mathcal{O}(\kappa\log(\epsilon^{-1}))$. For fixed $x_{s}$ in the $s$-th
iteration,
$\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{T}(x_{s})\|_{2}^{2}\leq\epsilon^{2}$ for
given tolerance $\epsilon$.

###### Proof.

According to the updates in Algorithm 2, we have

$\begin{array}[]{ll}&\|y^{*}(x_{s})-y_{t+1}(x_{s})\|^{2}\\\
=&(\|\mathrm{Proj}_{\mathcal{Y}}(y_{t}(x_{s})+\eta_{2}H_{\mu_{2}}(x_{s},y_{t}(x_{s})),\boldsymbol{u}_{2,[q_{2}]}-y^{*}(x_{s}))\|_{2}^{2})\\\
\leq&\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}+2\eta_{2}\langle
H_{\mu_{2}}(x_{s},y_{t}(x_{s}),\boldsymbol{u}_{2,[q_{2}]},y_{t}(x_{s})-y^{*}(x_{s})\rangle+\eta_{2}^{2}\|H_{\mu_{2}}(x_{s},y_{t}(x_{s}),\boldsymbol{u}_{2,[q_{2}]}\|_{2}^{2}.\end{array}$

For a given $s$, denote by E taking expectation with respect to random samples
$\boldsymbol{u}_{2,[q_{2}]}$ conditioned on all previous iterations. By taking
expectation to both sides of this inequality, we obtain

$\begin{array}[]{ll}&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t+1}(x_{s})\|^{2}\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}-2\eta_{2}\langle-\nabla_{y}f_{\mu_{2}}(x_{s},y_{t}(x_{s})),y_{t}(x_{s})-y^{*}(x_{s})\rangle+\eta_{2}^{2}\textsf{\text{E}}\,\|H_{\mu_{2}}(x_{s},y_{t}(x_{s}),\boldsymbol{u}_{2,[q_{2}]})\|_{2}^{2}\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}-2\eta_{2}\langle-\nabla_{y}f_{\mu_{2}}(x_{s},y_{t}(x_{s})),y_{t}(x_{s})-y^{*}(x_{s})\rangle+\eta_{2}^{2}\Bigl{(}3\|\nabla_{y}f(x_{s},y_{t}(x_{s}))\|_{2}^{2}+\mu_{2}^{2}\ell^{2}(d_{2}+6)^{3}\Bigr{)}\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}-2\eta_{2}[f_{\mu_{2}}(x_{s},y^{*}(x_{s}))-f_{\mu_{2}}(x_{s},y_{t}(x_{s}))]+\eta_{2}^{2}\Bigl{(}3\|\nabla_{y}f(x_{s},y_{t}(x_{s}))\|_{2}^{2}+\mu_{2}^{2}\ell^{2}(d_{2}+6)^{3}\Bigr{)}\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}-2\eta_{2}(f(x_{s},y^{*}(x_{s}))-f(x_{s},y_{t}(x_{s})))+2\mu_{2}^{2}d_{2}\eta_{2}\ell+\eta_{2}^{2}(6L_{2}(f(x_{s},y^{*}(x_{s}))-f(x_{s},y_{t}(x_{s})))\\\
&+\eta_{2}^{2}\mu_{2}^{2}\ell^{2}(d_{2}+6)^{3}\\\
=&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}-(f(x_{s},y^{*}(x_{s}))-f(x_{s},y_{t}(x_{s})))/(6\ell)+\mu_{2}^{2}d_{2}/3+\mu_{2}^{2}(d_{2}+6)^{3}/36\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}\Bigl{(}1-\frac{\tau}{12\ell}\Bigr{)}+\mu_{2}^{2}d_{2}/3+\mu_{2}^{2}(d_{2}+6)^{3}/36,\end{array}$

where the second inequality is due to Lemma A.10, the third inequality is due
to the concavity of $f_{\mu_{2}}$ (see Lemma A.4), the fourth inequality is
due to Lemmas A.5 and A.2, the equality is due to $\eta_{2}=1/(6\ell)$, and
the last inequality is due to Lemma A.2.

Define $\delta=12\ell(\mu_{2}^{2}d_{2}/3+\mu_{2}^{2}(d_{2}+6)^{3}/36)/\tau$.
From the above inequality, we have

$\begin{array}[]{ll}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}-\delta&\leq(\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t-1}(x_{s})\|^{2}-\delta)\Bigl{(}1-\frac{\tau}{12\ell}\Bigr{)}\\\
&\leq(\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{0}(x_{s})\|^{2}-\delta)\Bigl{(}1-\frac{\tau}{12\ell}\Bigr{)}^{t}\\\
&\leq\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{0}(x_{s})\|^{2}\Bigl{(}1-\frac{\tau}{12\ell}\Bigr{)}^{t}\leq
D^{2}\Bigl{(}1-\frac{\tau}{12\ell}\Bigr{)}^{t},\end{array}$

where the last inequality is due to Assumption 2.1. Now it is clear that in
order to ensure that
$\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{T}(x_{s})\|^{2}\leq\epsilon^{2}$, we
need $T\sim\mathcal{O}(\kappa\log(\epsilon^{-1}))$ and
$\mu_{2}=\mathcal{O}(\kappa^{-1/2}d_{2}^{-3/2}\epsilon)$. ∎

We are now ready to prove Theorem 3.2.

###### Proof of Theorem 3.2..

First, the following inequalities hold:

$\begin{array}[]{ll}&g(x_{s+1})\\\
\leq&g(x_{s})-\eta_{1}\langle\nabla_{x}g(x_{s}),G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{1,[q_{1}]})\rangle+\frac{1}{2}L_{g}\eta_{1}^{2}\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}\\\
=&g(x_{s})-\eta_{1}\Bigl{\langle}\nabla_{x}f(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))+\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1})\\\
&~{}+\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1}),G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{1,[q_{1}]})\Bigr{\rangle}+\frac{1}{2}L_{g}\eta_{1}^{2}\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}\\\
\leq&g(x_{s})+\|\nabla_{x}f(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))\|^{2}/L_{g}+\frac{L_{g}\eta_{1}^{2}}{4}\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{1,[q_{1}]})\|^{2}\\\
&+\|\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1})\|^{2}/L_{g}+\frac{L_{g}\eta_{1}^{2}}{4}\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{1,[q_{1}]})\|^{2}\\\
&-\eta_{1}\langle\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1}),G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{1,[q_{1}]})\rangle+\frac{1}{2}L_{g}\eta_{1}^{2}\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}\\\
\leq&g(x_{s})+\frac{\ell^{2}}{L_{g}}\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}-\eta_{1}\langle\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1}),G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{1,[q_{1}]})\rangle\\\
&+\eta_{1}^{2}L_{g}\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}+\frac{\mu_{1}^{2}}{4L_{g}}\ell^{2}(d_{1}+3)^{3},\end{array}$

where the first inequality is due to Lemma A.3, the second inequality is due
to Young’s inequality, and the last inequality is due to Lemmas A.6 and A.12.
Now take expectation with respect to $\boldsymbol{u}_{1,[q_{1}]}$ to the above
inequality, we get:

$\begin{array}[]{ll}&\eta_{1}\textsf{\text{E}}\,\|\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1})\|_{2}^{2}\\\
\leq&\textsf{\text{E}}\,g(x_{s})-\textsf{\text{E}}\,g(x_{s+1})+\frac{\ell^{2}}{L_{g}}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}+\eta_{1}^{2}L_{g}\textsf{\text{E}}\,\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{1,[q_{1}]})\|_{2}^{2}+\frac{\mu_{1}^{2}}{4L_{g}}\ell^{2}(d_{1}+3)^{3}\\\
\leq&\textsf{\text{E}}\,g(x_{s})-\textsf{\text{E}}\,g(x_{s+1})+\frac{\ell^{2}}{L_{g}}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}+\eta_{1}^{2}L_{g}\Bigl{(}3\|\nabla_{x}f(x_{s},y_{s+1})\|_{2}^{2}+\mu_{1}^{2}\ell^{2}(d_{1}+6)^{3}\Bigr{)}+\frac{\mu_{1}^{2}}{4L_{g}}\ell^{2}(d_{1}+3)^{3},\end{array}$
(39)

where the second inequality is due to Lemma A.10. From Lemma A.6 we have

$\begin{array}[]{ll}\textsf{\text{E}}\,\|\nabla_{x}f(x_{s},y_{s+1})\|_{2}^{2}\leq
2\textsf{\text{E}}\,\|\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1})\|_{2}^{2}+\mu_{1}^{2}\ell^{2}(d_{1}+3)^{3}/2.\end{array}$
(40)

Combining (39) and (40), and noting $\eta_{1}=1/(12L_{g})$, we have

$\begin{array}[]{ll}\textsf{\text{E}}\,\|\nabla_{x}f(x_{s},y_{s+1})\|_{2}^{2}\leq&48L_{g}\Bigl{[}\textsf{\text{E}}\,g(x_{s})-\textsf{\text{E}}\,g(x_{s+1})\Bigr{]}+48\ell^{2}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}\\\
&+13\mu_{1}^{2}\ell^{2}(d_{1}+3)^{3}+\mu_{1}^{2}\ell^{2}(d_{1}+6)^{3}/3.\end{array}$
(41)

It then follows that

$\begin{array}[]{ll}&\textsf{\text{E}}\,\|\nabla g(x_{s})\|_{2}^{2}\\\
\leq&2\textsf{\text{E}}\,\|\nabla_{x}g(x_{s})-\nabla_{x}f(x_{s},y_{s+1})\|_{2}^{2}+2\textsf{\text{E}}\,\|\nabla_{x}f(x_{s},y_{s+1})\|_{2}^{2}\\\
\leq&2\ell^{2}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}+2\textsf{\text{E}}\,\|\nabla_{x}f(x_{s},y_{s+1})\|_{2}^{2}\\\
\leq&96L_{g}\Bigl{[}\textsf{\text{E}}\,g(x_{s})-\textsf{\text{E}}\,g(x_{s+1})\Bigr{]}+98\ell^{2}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}\\\
&+26\mu_{1}^{2}\ell^{2}(d_{1}+3)^{3}+2\mu_{1}^{2}\ell^{2}(d_{1}+6)^{3}/3,\end{array}$
(42)

where the second inequality is due to Assumption 2.1, and the last inequality
is due to (41).

Take the sum over $s=0,\ldots,S$ to both sides of (42), we get

$\begin{array}[]{ll}\frac{1}{S+1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}\leq&\frac{96L_{g}}{S+1}\textsf{\text{E}}\,[g(x_{0})-g(x_{S+1})]+\frac{98\ell^{2}}{S+1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}\\\
&+26\mu_{1}^{2}\ell^{2}(d_{1}+3)^{3}+2\mu_{1}^{2}\ell^{2}(d_{1}+6)^{3}/3.\end{array}$
(43)

Denote $\Delta_{g}=g(x_{0})-\min_{x\in\mathbb{R}^{d_{1}}}(g(x))$. From Lemma
(E.1), we know that when $T\sim\mathcal{O}(\kappa\log(\epsilon^{-1}))$, we
have $\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|^{2}\leq\epsilon^{2}$ (note
that $y_{s+1}=y_{T}(x_{s})$). Therefore, choosing parameters as in (14)
guarantees that the right hand side of (43) is upper bounded by
$\mathcal{O}(\epsilon^{2})$, and thus an $\epsilon$-stationary point is found.
This completes the proof. ∎

##  Appendix D Convergence analysis for ZO-SGDA (Algorithm 3)

We first show the following inequality.

######  Lemma D.1.

Assume $\\{(x_{s},y_{s})\\}$ is the sequence generated by Algorithm 3. By
setting $\eta_{2}=1/(6\ell)$, the following inequality holds:

$\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s}\|_{2}^{2}\leq\Bigl{(}1-1/(12\kappa)\Bigr{)}\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|_{2}^{2}+\tilde{\epsilon}(\mu_{2}),$
(44)

where
$\varrho(\mu_{2},\epsilon)=\mu_{2}^{2}d_{2}/3+\mu_{2}^{2}(d_{2}+3)^{2}/72+\mu_{2}^{2}(d_{2}+6)^{2}\epsilon^{2}/576+\epsilon^{2}/72\ell^{2}$.

###### Proof.

According to the updates in Algorithm 1, we have

$\begin{array}[]{lll}\|y^{*}(x_{s-1})-y_{s}\|^{2}&=&\|\mathrm{Proj}_{\mathcal{Y}}(y_{s-1}+\eta_{2}H_{\mu_{2}}(x_{s-1},y_{s-1},\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}})-y^{*}(x_{s-1}))\|_{2}^{2}\\\
&\leq&\|y^{*}(x_{s-1})-y_{s-1}\|^{2}+2\eta_{2}\langle
H_{\mu_{2}}(x_{s-1},y_{s-1},\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}}),y_{s-1}-y^{*}(x_{s})\rangle\\\
&&+\eta_{2}^{2}\|H_{\mu_{2}}(x_{s-1},y_{s-1},\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}})\|_{2}^{2}.\end{array}$

For a given $s$, denote by E taking expectation with respect to random samples
$\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}}$ conditioned on all
previous iterations. By taking expectation to both sides of this inequality,
we obtain

$\begin{array}[]{ll}&\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s}\|^{2}\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|^{2}-2\eta_{2}\langle-\nabla_{y}f_{\mu_{2}}(x_{s-1},y_{s-1}),y_{s-1}-y^{*}(x_{s})\rangle+\eta_{2}^{2}\textsf{\text{E}}\,\|H_{\mu_{2}}(x_{s-1},y_{s-1},\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}})\|_{2}^{2}\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|^{2}-2\eta_{2}[f_{\mu_{2}}(x_{s-1},y^{*}(x_{s}))-f_{\mu_{2}}(x_{s-1},y_{s-1})]\\\
&+\eta_{2}^{2}\Bigl{(}3\|\nabla_{y}f(x_{s-1},y_{s-1})\|_{2}^{2}+\epsilon(\mu_{2})\Bigr{)}\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|^{2}-2\eta_{2}(f(x_{s-1},y^{*}(x_{s}))-f(x_{s-1},y_{s-1}))+2\mu_{2}^{2}d_{2}\eta_{2}\ell\\\
&+\eta_{2}^{2}(6\ell(f(x_{s-1},y^{*}(x_{s}))-f(x_{s-1},y_{s-1}))+\eta_{2}^{2}\varrho_{2}(\epsilon,\mu_{2})\\\
=&\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|^{2}-(f(x_{s-1},y^{*}(x_{s}))-f(x_{s-1},y_{s-1}))/(6\ell)+\varrho(\mu_{2},\epsilon)\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|^{2}\Bigl{(}1-\frac{\tau}{12\ell}\Bigr{)}+\varrho(\mu_{2},\epsilon),\end{array}$

where the second inequality is due to the concavity of $f_{\mu_{2}}$ (see
Lemma A.4) and Lemma A.11, the third inequality is due to Lemma A.2 and Lemma
A.5, the equality is due to $\eta_{2}=1/(6\ell)$, and the last inequality is
due to Lemma A.2. This completes the proof. ∎

We now prove the following upper bound of
$\textsf{\text{E}}\,\|y_{s}-y^{*}(x_{s})\|_{2}^{2}$.

######  Lemma D.2.

Consider ZO-SGDA (Algorithm 3). Use the same notation and the same assumptions
as in Lemma D.1. Denote $\delta_{s}=\|y_{s}-y^{*}(x_{s})\|_{2}^{2}$ and set
$\eta_{1}$ as in (11), and

$\gamma:=1-\frac{1}{24\kappa}+144\ell^{2}\kappa^{3}\eta_{1}^{2}\leq
1-\frac{5}{144\kappa}<1.$ (45)

It holds that

$\textsf{\text{E}}\,\delta_{s}\leq\gamma^{s}\textsf{\text{E}}\,\delta_{0}+\alpha_{1}\sum_{i=0}^{s-1}\gamma^{s-1-i}\textsf{\text{E}}\,\|\nabla
g(x_{i-1})\|_{2}^{2}+\theta_{0}\sum_{i=0}^{s-1}\gamma^{s-1-i},$ (46)

where

$\alpha_{1}=\frac{9}{12^{8}\kappa(\kappa+1)^{4}(\ell+1)^{2}},\
\theta_{0}=\alpha_{2}\varrho_{2}(\epsilon,\mu_{2})+2\varrho(\mu_{2},\epsilon),\
\alpha_{2}=\frac{1}{8\times 12^{7}\kappa(\kappa+1)^{4}}.$ (47)

###### Proof.

Define the filtration
$\mathcal{F}_{s}=\Bigl{\\{}x_{s},y_{s},x_{s-1},y_{s-1},...,x_{1},y_{1}\Bigr{\\}}$.
Let
$\zeta_{s}=(\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}},\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}}),\zeta_{[s]}=(\zeta_{1},\zeta_{2},...,\zeta_{s})$.
Denote by E taking expectation w.r.t $\zeta_{[s]}$ conditioned on
$\mathcal{F}_{s}$ and then taking expectation over $\mathcal{F}_{s}$. Since
$\kappa>1$, using the Young’s inequality, we have

$\begin{array}[]{ll}\textsf{\text{E}}\,\delta_{s}&=\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s}\|_{2}^{2}\\\
&\leq\Bigl{(}1+\frac{1}{2(12\kappa-1)}\Bigr{)}\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s}\|_{2}^{2}+\Bigl{(}1+2(12\kappa-1)\Bigr{)}\textsf{\text{E}}\,\|y^{*}(x_{s})-y^{*}(x_{s-1})\|_{2}^{2}\\\
&\leq(\frac{24\kappa-1}{2(12\kappa-1)})(1-\frac{1}{12\kappa})\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s}\|_{2}^{2}+24\kappa\textsf{\text{E}}\,\|y^{*}(x_{s})-y^{*}(x_{s-1})\|_{2}^{2}+2\varrho(\mu_{2},\epsilon)\\\
&\leq(1-\frac{1}{24\kappa})\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|_{2}^{2}+24\kappa^{3}\textsf{\text{E}}\,\|x_{s}-x_{s-1}\|_{2}^{2}+2\varrho(\mu_{2},\epsilon)\\\
&=(1-\frac{1}{24\kappa})\textsf{\text{E}}\,\delta_{s-1}+24\kappa^{3}\eta_{1}^{2}\textsf{\text{E}}\,\|G_{\mu_{1}}(x_{s-1},y_{s-1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}+2\varrho(\mu_{2},\epsilon)\\\
&=(1-\frac{1}{24\kappa})\textsf{\text{E}}\,\delta_{s-1}+\frac{\alpha_{1}}{6}\textsf{\text{E}}\,\|G_{\mu_{1}}(x_{s-1},y_{s-1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}+2\varrho(\mu_{2},\epsilon),\end{array}$
(48)

where the second inequality is due to (44), the third inequality is due to
Lemma A.3. From Lemma A.11, we have

$\begin{array}[]{ll}&\textsf{\text{E}}\,_{\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}}}\|G_{\mu_{1}}(x_{s-1},y_{s-1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}\\\
\leq&3\textsf{\text{E}}\,\|\nabla_{x}f(x_{s-1},y_{s-1})\|_{2}^{2}+\varrho_{2}(\epsilon,\mu_{2})\\\
\leq&6\textsf{\text{E}}\,\|\nabla
g(x_{s-1})\|_{2}^{2}+6\ell^{2}\textsf{\text{E}}\,\|y^{*}(x_{s-1})-y_{s-1}\|_{2}^{2}+\varrho_{2}(\epsilon,\mu_{2}),\end{array}$
(49)

where the second inequality is due to Assumption 2.1. Combining (48) and (49)
yields (46) by noting (45). ∎

Now we are ready to prove Theorem 4.1.

###### Proof of Theorem 4.1..

First, the following inequalities hold:

$\begin{array}[]{ll}&g(x_{s+1})\\\ \leq&g(x_{s})-\eta_{1}\langle\nabla
g(x_{s}),G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\rangle+\frac{1}{2}L_{g}\eta_{1}^{2}\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}\\\
=&g(x_{s})-\eta_{1}\Bigl{\langle}\nabla_{x}f(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))+\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y_{s})\\\
&+\nabla_{x}f_{\mu_{1}}(x_{s},y_{s}),G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\Bigr{\rangle}+\frac{1}{2}L_{g}\eta_{1}^{2}\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}\\\
\leq&g(x_{s})+\|\nabla_{x}f(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))\|^{2}/L_{g}+\frac{L_{g}\eta_{1}^{2}}{4}\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|^{2}\\\
&+\|\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y_{s})\|^{2}/L_{g}+\frac{L_{g}\eta_{1}^{2}}{4}\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|^{2}\\\
&-\eta_{1}\langle\nabla_{x}f_{\mu_{1}}(x_{s},y_{s}),G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\rangle+\frac{1}{2}L_{g}\eta_{1}^{2}\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}\\\
\leq&g(x_{s})+\frac{\ell^{2}}{L_{g}}\|y^{*}(x_{s})-y_{s}\|_{2}^{2}-\eta_{1}\langle\nabla_{x}f_{\mu_{1}}(x_{s},y_{s}),G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\rangle\\\
&+\eta_{1}^{2}L_{g}\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}+\frac{\mu_{1}^{2}}{4L_{g}}\ell^{2}(d_{1}+3)^{3},\end{array}$

where the first inequality is due to Lemma A.3, the second inequality is due
to Young’s inequality, and the last inequality is due to Lemmas A.6 and A.12.
Now take expectation with respect to
$\boldsymbol{u}_{\mathcal{M}_{1}}$,$\xi_{\mathcal{M}_{1}}$ to the above
inequality, we get:

$\begin{array}[]{ll}\eta_{1}\textsf{\text{E}}\,\|\nabla_{x}f_{\mu_{1}}(x_{s},y_{s})\|_{2}^{2}\leq&\textsf{\text{E}}\,g(x_{s})-\textsf{\text{E}}\,g(x_{s+1})+\frac{\ell^{2}}{L_{g}}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s}\|_{2}^{2}\\\
&+\eta_{1}^{2}L_{g}\textsf{\text{E}}\,\|G_{\mu_{1}}(x_{s},y_{s},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}+\frac{\mu_{1}^{2}}{4L_{g}}\ell^{2}(d_{1}+3)^{3}.\end{array}$
(50)

From Lemma A.12, we have

$\eta_{1}\textsf{\text{E}}\,\|\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))\|_{2}^{2}\leq
2\eta_{1}\textsf{\text{E}}\,\|\nabla_{x}f_{\mu_{1}}(x_{s},y_{s})\|_{2}^{2}+2\eta_{1}\ell^{2}\|y_{s}-y^{*}(x_{s})\|_{2}^{2}.$
(51)

From Lemma A.6, we have

$\eta_{1}\|\nabla g(x_{s})\|_{2}^{2}\leq
2\eta_{1}\|\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))\|_{2}^{2}+\frac{\eta_{1}\mu_{1}^{2}}{2}\ell^{2}(d_{1}+3)^{3}.$
(52)

Combining (49), (50), (51), (27) yields,

$\begin{array}[]{ll}&\eta_{1}\textsf{\text{E}}\,\|\nabla g(x_{s})\|_{2}^{2}\\\
\leq&4\textsf{\text{E}}\,g(x_{s})-4\textsf{\text{E}}\,g(x_{s+1})+\Bigl{(}\frac{4\ell^{2}}{L_{g}}+4\eta_{1}\ell^{2}\Bigr{)}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s}\|_{2}^{2}+\frac{\mu_{1}^{2}}{L_{g}}\ell^{2}(d_{1}+3)^{3}+\frac{\eta_{1}\mu_{1}^{2}}{2}\ell^{2}(d_{1}+3)^{3}\\\
&+4\eta_{1}^{2}L_{g}\Bigl{[}6\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}+6\ell^{2}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s}\|_{2}^{2}+\epsilon(\mu_{2})\Bigr{]}\\\
=&4\textsf{\text{E}}\,g(x_{s})-4\textsf{\text{E}}\,g(x_{s+1})+24\eta_{1}^{2}L_{g}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}+\theta_{1}\textsf{\text{E}}\,\delta_{s}+\theta_{2},\end{array}$
(53)

where

$\theta_{1}=\frac{4\ell^{2}}{L_{g}}+4\eta_{1}\ell^{2}+24\eta_{1}^{2}L_{g}\ell^{2}\leq
4\ell+4\eta_{1}\ell^{2}+24\eta_{1}^{2}\ell^{3}(\kappa+1)$ (54)

and

$\begin{array}[]{ll}&\theta_{2}=\frac{\mu_{1}^{2}}{L_{g}}\ell^{2}(d_{1}+3)^{3}+\frac{\eta_{1}\mu_{1}^{2}}{2}\ell^{2}(d_{1}+3)^{3}+4\eta_{1}^{2}L_{g}\epsilon(\mu_{2})\\\
\leq&\mu_{1}^{2}\ell(d_{1}+3)^{3}+\frac{\eta_{1}\mu_{1}^{2}}{2}\ell^{2}(d_{1}+3)^{3}+4\eta_{1}^{2}(\kappa+1)\ell\epsilon(\mu_{2})\\\
\leq&\mu_{1}^{2}\ell(d_{1}+3)^{3}+\frac{\eta_{1}\mu_{1}^{2}}{2}\ell^{2}(d_{1}+3)^{3}+\eta_{1}^{2}(\kappa+1)\ell^{3}\Bigl{(}2\mu_{1}^{2}(d_{1}+3)^{3}+\frac{\mu_{1}^{2}(d_{1}+6)^{2}\epsilon^{2}}{2}\Bigr{)}+2\eta_{1}^{2}(\kappa+1)\ell\epsilon^{2}\end{array}$
(55)

where we have used the definition of $L_{g}:=\ell(\kappa+1)$. Taking sum over
$s=0,\ldots,S$ to both sides of (53), we get

$\sum_{s=0}^{S}\textsf{\text{E}}\,\delta_{s}\leq\sum_{s=0}^{S}\gamma^{s}\textsf{\text{E}}\,\delta_{0}+\alpha_{1}\sum_{s=0}^{S}\sum_{i=0}^{s-1}\gamma^{s-1-i}\textsf{\text{E}}\,\|\nabla
g(x_{i-1})\|_{2}^{2}+\theta_{0}\sum_{s=0}^{S}\sum_{i=0}^{s-1}\gamma^{s-1-i}.$
(56)

Moreover, from (45) it is easy to obtain

$\sum_{s=0}^{S}\gamma^{s}\leq
36\kappa,\quad\sum_{s=0}^{S}\sum_{i=0}^{s-1}\gamma^{s-1-i}\leq 36\kappa(S+1),$
(57)

and

$\sum_{s=0}^{S}\sum_{i=0}^{s-1}\gamma^{s-1-i}\textsf{\text{E}}\,\|\nabla
g(x_{i-1})\|_{2}^{2}\leq 36\kappa\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}.$ (58)

Substituting (57) and (58) into (56), we obtain

$\sum_{s=0}^{S}\textsf{\text{E}}\,\delta_{s}\leq
36\kappa\textsf{\text{E}}\,\delta_{0}+36\kappa\alpha_{1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}+36\kappa\theta_{0}(S+1).$ (59)

Now, summing (28) over $s=0,\ldots,S$ yields

$\begin{array}[]{ll}&\eta_{1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}\\\
=&4\textsf{\text{E}}\,g(x_{0})-4\textsf{\text{E}}\,g(x_{S+1})+24\eta_{1}^{2}L_{g}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}+\theta_{1}\sum_{s=0}^{S}\textsf{\text{E}}\,\delta_{s}+(S+1)\theta_{2}\\\
\leq&4\textsf{\text{E}}\,g(x_{0})-4\textsf{\text{E}}\,g(x_{S+1})+24\eta_{1}^{2}L_{g}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}\\\
&+\theta_{1}[36\kappa\textsf{\text{E}}\,\delta_{0}+36\kappa\alpha_{1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}+36\kappa\theta_{0}(S+1)]+(S+1)\theta_{2}\end{array}$ (60)

where the second inequality is from (59). Using (54), (47) and (11), it is
easy to verify that

$36\kappa\theta_{1}\alpha_{1}\leq\left(\frac{108}{3\times
12^{3}}+\frac{108}{12^{7}}+\frac{54}{4\times 12^{10}}\right)\eta_{1}\leq
0.021\eta_{1},$

which together with $L_{g}:=(\kappa+1)\ell$ yields

$36\kappa\theta_{1}\alpha_{1}+24\eta_{1}^{2}L_{g}\leq
0.021\eta_{1}+0.0003\eta_{1}=0.0213\eta_{1}.$ (61)

Combining (60) and (61) yields

$\begin{array}[]{ll}&0.9787\eta_{1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}\\\
\leq&4\textsf{\text{E}}\,g(x_{0})-4\textsf{\text{E}}\,g(x_{S+1})+\theta_{1}[36\kappa\textsf{\text{E}}\,\delta_{0}+36\kappa\theta_{0}(S+1)]+(S+1)\theta_{2}.\end{array}$
(62)

Dividing both sides of (62) by $0.9787\eta_{1}(S+1)$ yields

$\begin{array}[]{ll}\frac{1}{S+1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}\leq\frac{4\Delta_{g}}{0.9787\eta_{1}(S+1)}+\frac{36\kappa\theta_{1}\textsf{\text{E}}\,\delta_{0}}{0.9787\eta_{1}(S+1)}+\frac{36\kappa\theta_{1}\theta_{0}}{0.9787\eta_{1}}+\frac{\theta_{2}}{0.9787\eta_{1}},\end{array}$
(63)

where $\Delta_{g}:=g(x_{0})-\min_{x\in\mathbb{R}^{d_{1}}}g(x)$. Now we only
need to upper bound the right hand side of (63) by $O(\epsilon^{2})$. Note
that by the choice of parameters in (12), the right hand side of (63) is
$O(\epsilon^{2})+O(\epsilon^{4})$. Hence, with $\epsilon\in(0,1)$, we get the
required result. This completes the proof of Theorem 4.1. ∎

##  Appendix E Convergence analysis of ZO-SGDMSA (Algorithm 4)

First, we show the following iteration complexity of the inner loop for $y$ in
Algorithm 4.

######  Lemma E.1.

In Algorithm 4, setting $\eta_{2}=1/(6\ell)$,
$\mu_{2}=\mathcal{O}(\kappa^{-1/2}d_{2}^{-3/2}\epsilon)$ and
$T=\mathcal{O}(\kappa\log(\epsilon^{-1}))$. For fixed $x_{s}$ in the $s$-th
iteration,
$\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{T}(x_{s})\|_{2}^{2}\leq\epsilon^{2}$ for
given tolerance $\epsilon$.

###### Proof.

According to the updates in Algorithm 4, we have

$\begin{array}[]{ll}&\|y^{*}(x_{s})-y_{t+1}(x_{s})\|^{2}\\\
=&(\|\mathrm{Proj}_{\mathcal{Y}}(y_{t}(x_{s})+\eta_{2}H_{\mu_{2}}(x_{s},y_{t}(x_{s}),\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}})-y^{*}(x_{s}))\|_{2}^{2})\\\
\leq&\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}+2\eta_{2}\langle
H_{\mu_{2}}(x_{s},y_{t}(x_{s}),\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}}),y_{t}(x_{s})-y^{*}(x_{s})\rangle+\eta_{2}^{2}\|H_{\mu_{2}}(x_{s},y_{t}(x_{s}),\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}}\|_{2}^{2}.\end{array}$

For a given $s$, denote by E taking expectation with respect to random samples
$\boldsymbol{u}_{\mathcal{M}_{2}},\xi_{\mathcal{M}_{2}}$ conditioned on all
previous iterations. By taking expectation to both sides of this inequality,
we obtain

$\begin{array}[]{ll}&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t+1}(x_{s})\|^{2}\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}-2\eta_{2}\langle-\nabla_{y}f_{\mu_{2}}(x_{s},y_{t}(x_{s})),y_{t}(x_{s})-y^{*}(x_{s})\rangle+\eta_{2}^{2}\textsf{\text{E}}\,\|H_{\mu_{2}}(x_{s},y_{t}(x_{s}),\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}-2\eta_{2}\langle-\nabla_{y}f_{\mu_{2}}(x_{s},y_{t}(x_{s})),y_{t}(x_{s})-y^{*}(x_{s})\rangle+\eta_{2}^{2}\Bigl{(}3\|\nabla_{y}f(x_{s},y_{t}(x_{s}))\|_{2}^{2}+\epsilon(\mu_{2}))\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}-2\eta_{2}[f_{\mu_{2}}(x_{s},y^{*}(x_{s}))-f_{\mu_{2}}(x_{s},y_{t}(x_{s}))]+\eta_{2}^{2}\Bigl{(}3\|\nabla_{y}f(x_{s},y_{t}(x_{s}))\|_{2}^{2}+\epsilon(\mu_{2})\Bigr{)}\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}-2\eta_{2}(f(x_{s},y^{*}(x_{s}))-f(x_{s},y_{t}(x_{s})))+2\mu_{2}^{2}d_{2}\eta_{2}\ell+\eta_{2}^{2}(6L_{2}(f(x_{s},y^{*}(x_{s}))-f(x_{s},y_{t}(x_{s})))\\\
&+\eta_{2}^{2}\epsilon(\mu_{2})\\\
=&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}-(f(x_{s},y^{*}(x_{s}))-f(x_{s},y_{t}(x_{s})))/(6\ell)\\\
&+\epsilon^{2}/(72\ell^{2})+\mu_{2}^{2}(d_{2}+3)^{3}/72+\mu_{2}^{2}(d_{2}+6)^{2}\epsilon^{2}/288\\\
\leq&\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}\Bigl{(}1-\frac{\tau}{12\ell}\Bigr{)}+\epsilon^{2}/(72\ell^{2})+\mu_{2}^{2}(d_{2}+3)^{3}/72+\mu_{2}^{2}(d_{2}+6)^{2}\epsilon^{2}/288,\end{array}$

where the second inequality is due to Lemma A.11, the third inequality is due
to the concavity of $f_{\mu_{2}}$ (see Lemma A.4), the fourth inequality is
due to Lemmas A.5 and A.2, the equality is due to $\eta_{2}=1/(6\ell)$, and
the last inequality is due to Lemma A.2.

Define
$\delta=12\ell(\epsilon^{2}/(72\ell^{2})+\mu_{2}^{2}(d_{2}+3)^{3}/72+\mu_{2}^{2}(d_{2}+6)^{2}\epsilon^{2}/288)/\tau$.
From the above inequality, we have

$\begin{array}[]{ll}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t}(x_{s})\|^{2}-\delta&\leq(\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{t-1}(x_{s})\|^{2}-\delta)\Bigl{(}1-\frac{\tau}{12\ell}\Bigr{)}\\\
&\leq(\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{0}(x_{s})\|^{2}-\delta)\Bigl{(}1-\frac{\tau}{12\ell}\Bigr{)}^{t}\\\
&\leq\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{0}(x_{s})\|^{2}\Bigl{(}1-\frac{\tau}{12\ell}\Bigr{)}^{t}\leq
D^{2}\Bigl{(}1-\frac{\tau}{12\ell}\Bigr{)}^{t},\end{array}$

where the last inequality is due to Assumption 2.1. Now it is clear that in
order to ensure that
$\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{T}(x_{s})\|^{2}\leq\epsilon^{2}$, we
need $T\sim\mathcal{O}(\kappa\log(\epsilon^{-1}))$ and
$\mu_{2}=\mathcal{O}(\kappa^{-1/2}d_{2}^{-3/2}\epsilon)$. ∎

We are now ready to prove Theorem 4.2.

###### Proof of Theorem 4.2..

First, the following inequalities hold:

$\begin{array}[]{ll}&g(x_{s+1})\\\
\leq&g(x_{s})-\eta_{1}\langle\nabla_{x}g(x_{s}),G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\rangle+\frac{1}{2}L_{g}\eta_{1}^{2}\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}\\\
=&g(x_{s})-\eta_{1}\Bigl{\langle}\nabla_{x}f(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))+\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1})\\\
&~{}+\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1}),G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\Bigr{\rangle}+\frac{1}{2}L_{g}\eta_{1}^{2}\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}\\\
\leq&g(x_{s})+\|\nabla_{x}f(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))\|^{2}/L_{g}+\frac{L_{g}\eta_{1}^{2}}{4}\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|^{2}\\\
&+\|\nabla_{x}f_{\mu_{1}}(x_{s},y^{*}(x_{s}))-\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1})\|^{2}/L_{g}+\frac{L_{g}\eta_{1}^{2}}{4}\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|^{2}\\\
&-\eta_{1}\langle\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1}),G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\rangle+\frac{1}{2}L_{g}\eta_{1}^{2}\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}\\\
\leq&g(x_{s})+\frac{\ell^{2}}{L_{g}}\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}-\eta_{1}\langle\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1}),G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\rangle\\\
&+\eta_{1}^{2}L_{g}\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}+\frac{\mu_{1}^{2}}{4L_{g}}\ell^{2}(d_{1}+3)^{3},\end{array}$

where the first inequality is due to Lemma A.3, the second inequality is due
to Young’s inequality, and the last inequality is due to Lemmas A.6 and A.12.
Now take expectation with respect to
$\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}}$ to the above
inequality, we get:

$\begin{array}[]{ll}&\eta_{1}\textsf{\text{E}}\,\|\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1})\|_{2}^{2}\\\
\leq&\textsf{\text{E}}\,g(x_{s})-\textsf{\text{E}}\,g(x_{s+1})+\frac{\ell^{2}}{L_{g}}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}+\eta_{1}^{2}L_{g}\textsf{\text{E}}\,\|G_{\mu_{1}}(x_{s},y_{s+1},\boldsymbol{u}_{\mathcal{M}_{1}},\xi_{\mathcal{M}_{1}})\|_{2}^{2}+\frac{\mu_{1}^{2}}{4L_{g}}\ell^{2}(d_{1}+3)^{3}\\\
\leq&\textsf{\text{E}}\,g(x_{s})-\textsf{\text{E}}\,g(x_{s+1})+\frac{\ell^{2}}{L_{g}}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}+\eta_{1}^{2}L_{g}\Bigl{(}3\|\nabla_{x}f(x_{s},y_{s+1})\|_{2}^{2}+\epsilon(\mu_{1})\Bigr{)}+\frac{\mu_{1}^{2}}{4L_{g}}\ell^{2}(d_{1}+3)^{3},\end{array}$
(64)

where the second inequality is due to Lemma A.10. From Lemma A.6 we have

$\begin{array}[]{ll}\textsf{\text{E}}\,\|\nabla_{x}f(x_{s},y_{s+1})\|_{2}^{2}\leq
2\textsf{\text{E}}\,\|\nabla_{x}f_{\mu_{1}}(x_{s},y_{s+1})\|_{2}^{2}+\mu_{1}^{2}\ell^{2}(d_{1}+3)^{3}/2.\end{array}$
(65)

Combining (64) and (65), and noting $\eta_{1}=1/(12L_{g})$, we have

$\begin{array}[]{ll}\textsf{\text{E}}\,\|\nabla_{x}f(x_{s},y_{s+1})\|_{2}^{2}\leq&48L_{g}\Bigl{[}\textsf{\text{E}}\,g(x_{s})-\textsf{\text{E}}\,g(x_{s+1})\Bigr{]}+48\ell^{2}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}\\\
&+13\mu_{1}^{2}\ell^{2}(d_{1}+3)^{3}+\epsilon(\mu_{1})/12.\end{array}$ (66)

It then follows that

$\begin{array}[]{ll}&\textsf{\text{E}}\,\|\nabla g(x_{s})\|_{2}^{2}\\\
\leq&2\textsf{\text{E}}\,\|\nabla_{x}g(x_{s})-\nabla_{x}f(x_{s},y_{s+1})\|_{2}^{2}+2\textsf{\text{E}}\,\|\nabla_{x}f(x_{s},y_{s+1})\|_{2}^{2}\\\
\leq&2\ell^{2}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}+2\textsf{\text{E}}\,\|\nabla_{x}f(x_{s},y_{s+1})\|_{2}^{2}\\\
\leq&96L_{g}\Bigl{[}\textsf{\text{E}}\,g(x_{s})-\textsf{\text{E}}\,g(x_{s+1})\Bigr{]}+98\ell^{2}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}\\\
&+26\mu_{1}^{2}\ell^{2}(d_{1}+3)^{3}+\epsilon(\mu_{1})/6,\end{array}$ (67)

where the second inequality is due to Assumption 2.1, and the last inequality
is due to (66).

Take the sum over $s=0,\ldots,S$ to both sides of (67), we get

$\begin{array}[]{ll}\frac{1}{S+1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|\nabla
g(x_{s})\|_{2}^{2}\leq&\frac{96L_{g}}{S+1}\textsf{\text{E}}\,[g(x_{0})-g(x_{S+1})]+\frac{98\ell^{2}}{S+1}\sum_{s=0}^{S}\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|_{2}^{2}\\\
&+26\mu_{1}^{2}\ell^{2}(d_{1}+3)^{3}+\epsilon(\mu_{1})/6.\end{array}$ (68)

Denote $\Delta_{g}=g(x_{0})-\min_{x\in\mathbb{R}^{d_{1}}}(g(x))$. From Lemma
(E.1), we know that when $T\sim\mathcal{O}(\kappa\log(\epsilon^{-1}))$, we
have $\textsf{\text{E}}\,\|y^{*}(x_{s})-y_{s+1}\|^{2}\leq\epsilon^{2}$ (note
that $y_{s+1}=y_{T}(x_{s})$). Therefore, choosing parameters as in (14)
guarantees that the right hand side of (68) is upper bounded by
$O(\epsilon^{2})+O(\epsilon^{4})$. Hence, with $\epsilon\in(0,1)$, we get the
required result and thus an $\epsilon$-stationary point is found. This
completes the proof. ∎

## References

  * [ABD+18] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach.  A reductions approach to fair classification.  In International Conference on Machine Learning, pages 60–69, 2018\.
  * [ADSHO18] Abdullah Al-Dujaili, Shashank Srikant, Erik Hemberg, and Una-May O’Reilly.  On the application of danskin’s theorem to derivative-free minimax optimization.  arXiv preprint arXiv:1805.06322, 2018.
  * [AH17] Charles Audet and Warren Hare.  Derivative-Free and Blackbox Optimization.  Springer, 2017.
  * [AMLJG19] Waïss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel.  A tight and unified analysis of extragradient for a whole spectrum of differentiable games.  arXiv preprint arXiv:1906.05945, 2019.
  * [AW17] Jacob Abernethy and Jun-Kun Wang.  On frank-wolfe and equilibrium computation.  In Advances in Neural Information Processing Systems, pages 6584–6593, 2017.
  * [BG18] Krishnakumar Balasubramanian and Saeed Ghadimi.  Zeroth-order (non)-convex stochastic optimization via conditional gradient and gradient updates.  In Advances in Neural Information Processing Systems, pages 3455–3464, 2018.
  * [BG19] Krishnakumar Balasubramanian and Saeed Ghadimi.  Zeroth-order nonconvex stochastic optimization: Handling constraints, high-dimensionality, and saddle-points.  arXiv preprint arXiv:1809.06474, 2019.
  * [BLE17] Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan.  Kernel-based methods for bandit convex optimization.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 72–85. ACM, 2017.
  * [BN10] Dimitris Bertsimas and Omid Nohadani.  Robust optimization with simulated annealing.  Journal of Global Optimization, 48(2):323–334, 2010.
  * [BNR19] Sina Baharlouei, Maher Nouiehed, and Meisam Razaviyayn.  Rényi fair inference.  International Conference on Learning Representation, 2019.
  * [BP18] James P. Bailey and Georgios Piliouras.  Multiplicative weights update in zero-sum games.  In Proceedings of the ACM Conference on Economics and Computation, 2018.
  * [BSJC18] Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher.  Adversarially robust optimization with gaussian processes.  In Advances in Neural Information Processing Systems, pages 5760–5770, 2018.
  * [CBL06] Nicolò Cesa-Bianchi and Gábor Lugosi.  Prediction, learning, and games.  2006\.
  * [CSV09] Andrew Conn, Katya Scheinberg, and Luis Vicente.  Introduction to derivative-free optimization, volume 8.  Siam, 2009.
  * [CZS+17] Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh.  Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models.  In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 15–26. ACM, 2017.
  * [DDK11] Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim.  Near-optimal no-regret algorithms for zero-sum games.  In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 235–254, 2011.
  * [DISZ17] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng.  Training gans with optimism.  arXiv preprint arXiv:1711.00141, 2017.
  * [DJWW15] John C Duchi, Michael I Jordan, Martin J Wainwright, and Andre Wibisono.  Optimal rates for zero-order convex optimization: The power of two function evaluations.  IEEE Transactions on Information Theory, 61(5):2788–2806, 2015\.
  * [DP18] Constantinos Daskalakis and Ioannis Panageas.  The limit points of (optimistic) gradient descent in min-max optimization.  In Advances in Neural Information Processing Systems, pages 9236–9246, 2018.
  * [DSL+17] Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song.  Sbeed: Convergent reinforcement learning with nonlinear function approximation.  arXiv preprint arXiv:1712.10285, 2017.
  * [FA96] Sjur Didrik Flåm and Anatoly S Antipin.  Equilibrium programming using proximal-like algorithms.  Mathematical Programming, 78(1):29–41, 1996.
  * [FKM05] Abraham Flaxman, Adam Kalai, and H. Brendan McMahan.  Online convex optimization in the bandit setting: gradient descent without a gradient.  In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, 2005.
  * [FP07] Francisco Facchinei and Jong-Shi Pang.  Finite-dimensional variational inequalities and complementarity problems.  Springer Science & Business Media, 2007.
  * [FV12] Jerzy Filar and Koos Vrieze.  Competitive Markov decision processes.  Springer Science & Business Media, 2012.
  * [FVGP19] Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, and Georgios Piliouras.  Poincaré recurrence, cycles and spurious equilibria in gradient-descent-ascent for non-convex non-concave zero-sum games.  arXiv preprint arXiv:1910.13010, 2019.
  * [GBV+18] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien.  A variational inequality perspective on generative adversarial networks.  arXiv preprint arXiv:1802.10551, 2018.
  * [GJLJ17] Gauthier Gidel, Tony Jebara, and Simon Lacoste-Julien.  Frank-wolfe algorithms for saddle point problems.  In Artificial Intelligence and Statistics, pages 362–371, 2017\.
  * [GL13] Saeed Ghadimi and Guanghui Lan.  Stochastic first- and zeroth-order methods for nonconvex stochastic programming.  SIAM Journal on Optimization, 23, 2013.
  * [GPAM+14] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In Advances in neural information processing systems, pages 2672–2680, 2014.
  * [Ham84] Janice Hammond.  Solving asymmetric variational inequality problems and systems of equations with generalized nonlinear programming algorithms.  PhD thesis, Massachusetts Institute of Technology, 1984.
  * [HLC18] Ya-Ping Hsieh, Chen Liu, and Volkan Cevher.  Finding mixed nash equilibria of generative adversarial networks.  arXiv preprint arXiv:1811.02002, 2018.
  * [JNJ19] Chi Jin, Praneeth Netrapalli, and Michael I Jordan.  Minmax optimization: Stable limit points of gradient descent ascent are locally optimal.  arXiv preprint arXiv:1902.00618, 2019.
  * [Kor76] GM Korpelevich.  The extragradient method for finding saddle points and other problems.  Matecon, 12:747–756, 1976.
  * [LCLS17] Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song.  Delving into transferable adversarial examples and black-box attacks.  International Conference on Representation Learning, 2017.
  * [LJJ19] Tianyi Lin, Chi Jin, and Michael I Jordan.  On gradient descent ascent for nonconvex-concave minimax problems.  arXiv preprint arXiv:1906.00331, 2019.
  * [LLC+19] Sijia Liu, Songtao Lu, Xiangyi Chen, Yao Feng, Kaidi Xu, Abdullah Al-Dujaili, Minyi Hong, and Una-May Obelilly.  Min-max optimization without gradients: Convergence and applications to adversarial ml.  arXiv preprint arXiv:1909.13806, 2019.
  * [LMW19] Jeffrey Larson, Matt Menickelly, and Stefan M. Wild.  Derivative-free optimization methods.  Acta Numer., 28:287–404, 2019.
  * [LTHC19] Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen.  Hybrid block successive approximation for one-sided non-convex min-max problems: algorithms and applications.  arXiv preprint arXiv:1902.08294, 2019.
  * [LYZ20] Luo Luo, Haishan Ye, and Tong Zhang.  Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems.  arXiv preprint arXiv:2001.03724, 2020.
  * [MMS+17] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  arXiv preprint arXiv:1706.06083, 2017.
  * [MOP19] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil.  A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach.  arXiv preprint arXiv:1901.08511, 2019.
  * [MPP18] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras.  Cycles in adversarial regularized learning.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2703–2717. SIAM, 2018.
  * [MS10] Renato Monteiro and Benar Fux Svaiter.  On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean.  SIAM Journal on Optimization, 20(6):2755–2787, 2010.
  * [MSG99] David E Moriarty, Alan C Schultz, and John J Grefenstette.  Evolutionary algorithms for reinforcement learning.  Journal of Artificial Intelligence Research, 11:241–276, 1999.
  * [MW18] Matt Menickelly and Stefan M. Wild.  Derivative-free robust optimization by outer approximations.  Mathematical Programming, pages 1–37, 2018.
  * [Nem04] Arkadi Nemirovski.  Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems.  SIAM Journal on Optimization, 15(1):229–251, 2004.
  * [Nes04] Y. E. Nesterov.  Introductory lectures on convex optimization: A basic course.  Applied Optimization. Kluwer Academic Publishers, Boston, MA, 2004.
  * [Nes18] Yurii Nesterov.  Lectures on convex optimization, volume 137.  Springer, 2018.
  * [NO09] Angelia Nedić and Asuman Ozdaglar.  Subgradient methods for saddle-point problems.  Journal of optimization theory and applications, 142(1):205–228, 2009.
  * [NS17] Yurii Nesterov and Vladimir Spokoiny.  Random gradient-free minimization of convex functions.  Foundations of Computational Mathematics, 17(2):527–566, 2017.
  * [NSH+19] Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason Lee, and Meisam Razaviyayn.  Solving a class of non-convex min-max games using iterative first order methods.  In Advances in Neural Information Processing Systems, pages 14905–14916, 2019.
  * [NSS03] Abraham Neyman, Sylvain Sorin, and S Sorin.  Stochastic games and applications, volume 570.  Springer Science & Business Media, 2003.
  * [NY83] Arkadi S. Nemirovsky and D. B. Yudin.  Problem complexity and method efficiency in optimization.  1983\.
  * [OSG+18] Frans A Oliehoek, Rahul Savani, Jose Gallego, Elise van der Pol, and Roderich Groß.  Beyond local nash equilibria for adversarial networks.  arXiv preprint arXiv:1806.07268, 2018.
  * [PB16] Balamurugan Palaniappan and Francis Bach.  Stochastic variance reduction methods for saddle-point problems.  In Advances in Neural Information Processing Systems, pages 1416–1424, 2016.
  * [PBH19] Victor Picheny, Mickael Binois, and Abderrahmane Habbal.  A bayesian optimization approach to find nash equilibria.  Journal of Global Optimization, 73(1):171–192, 2019.
  * [PS18] Georgios Piliouras and Leonard J Schulman.  Learning dynamics and the co-evolution of competing sexual species.  In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [PV16] David Pfau and Oriol Vinyals.  Connecting generative adversarial networks and actor-critic methods.  arXiv preprint arXiv:1610.01945, 2016.
  * [RCBM19] Abhishek Roy, Yifang Chen, Krishnakumar Balasubramanian, and Prasant Mohapatra.  Online and bandit algorithms for nonstationary stochastic saddle-point optimization.  arXiv preprint arXiv:1912.01698, 2019.
  * [RLLY18] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang.  Non-convex min-max optimization: Provable algorithms and applications in machine learning.  arXiv preprint arXiv:1810.02060, 2018.
  * [RS13a] Alexander Rakhlin and Karthik Sridharan.  Optimization, learning, and games with predictable sequences.  In Advances in Neural Information Processing Systems, pages 3066–3074, 2013.
  * [RS13b] Luis Rios and Nikolaos Sahinidis.  Derivative-free optimization: a review of algorithms and comparison of software implementations.  Journal of Global Optimization, 56(3):1247–1293, 2013.
  * [SALS15] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert Schapire.  Fast convergence of regularized learning in games.  In Advances in Neural Information Processing Systems, pages 2989–2997, 2015.
  * [SBRL18] Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and Jason D Lee.  On the convergence and robustness of training gans with regularized optimal transport.  In Advances in Neural Information Processing Systems, pages 7091–7101, 2018.
  * [Sha17] Ohad Shamir.  An optimal algorithm for bandit and zero-order convex optimization with two-point feedback.  Journal of Machine Learning Research, 18(52):1–11, 2017.
  * [SHC+17] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever.  Evolution strategies as a scalable alternative to reinforcement learning.  arXiv preprint arXiv:1703.03864, 2017.
  * [SLA12] Jasper Snoek, Hugo Larochelle, and Ryan P Adams.  Practical bayesian optimization of machine learning algorithms.  In Advances in neural information processing systems, pages 2951–2959, 2012.
  * [SZS+13] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  arXiv preprint arXiv:1312.6199, 2013.
  * [TJNO19] Kiran Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh.  Efficient algorithms for smooth minimax optimization.  In Advances in Neural Information Processing Systems, pages 12659–12670, 2019.
  * [Tse95] Paul Tseng.  On linear convergence of iterative methods for the variational inequality problem.  Journal of Computational and Applied Mathematics, 60(1-2):237–252, 1995.
  * [WHL17] Chen-Yu Wei, Yi-Te Hong, and Chi-Jen Lu.  Online reinforcement learning in stochastic games.  In Advances in Neural Information Processing Systems, pages 4987–4997, 2017.
  * [WJ17] Zi Wang and Stefanie Jegelka.  Max-value entropy search for efficient bayesian optimization.  In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 3627–3635. JMLR. org, 2017.
  * [XYZW18] Depeng Xu, Shuhan Yuan, Lu Zhang, and Xintao Wu.  Fairgan: Fairness-aware generative adversarial networks.  In IEEE International Conference on Big Data (Big Data). IEEE, pages 570–575, 2018.
  * [YWL16] Yiming Ying, Longyin Wen, and Siwei Lyu.  Stochastic online auc maximization.  In Advances in neural information processing systems, pages 451–459, 2016.
  * [ZLM18] Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell.  Mitigating unwanted biases with adversarial learning.  In AAAI/ACM Conference on AI, Ethics, and Society. ACM, pages 335–340, 2018.
  * [ZYB19] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar.  Multi-agent reinforcement learning: A selective overview of theories and algorithms.  arXiv preprint arXiv:1911.10635, 2019.