Year: 2019

Abstract:
In this paper, we study the problem of constrained robust (min-max) optimization in a black-box setting, where the desired optimizer cannot access the gradients of the objective function but may query its values. We present a principled optimization framework, integrating a zeroth-order (ZO) gradient estimator with an alternating projected stochastic gradient descent-ascent method, where the former only requires a small number of function queries and the later needs just one-step descent/ascent update. We show that the proposed framework, referred to as ZO-Min-Max, has a sub-linear convergence rate under mild conditions and scales gracefully with problem size. From an application side, we explore a promising connection between black-box min-max optimization and black-box evasion and poisoning attacks in adversarial machine learning (ML). Our empirical evaluations on these use cases demonstrate the effectiveness of our approach and its scalability to dimensions that prohibit using recent black-box solvers.

heading: 1 INTRODUCTION
text: In numerous real-world applications, one is faced with various forms of adversary that are not accounted for by standard optimization algorithms. For instance, when training a machine learning model on user-provided data, malicious users can carry out a data poisoning attack: providing false data with the aim of corrupting the learned model (Steinhardt et al., 2017; Tran et al., 2018; Jagielski et al., 2018). At inference time, malicious users can evade detection of multiple models in the form of adversarial example attacks (Goodfellow et al., 2014; Liu et al., 2016; 2018a). Min-max (robust) optimization is a natural framework to address adversarial (worst-case) robustness (Madry et al., 2017b; Al-Dujaili et al., 2018b). It converts a standard minimization problem into a composition of an inner maximization problem and an outer minimization problem.
Min-max optimization problems have been studied for multiple decades (Wald, 1945), and the majority of the proposed methods assume access to first-order (FO) information, i.e. gradients, to find or approximate robust solutions (Nesterov, 2007; Gidel et al., 2017; Hamedani et al., 2018; Qian et al., 2019; Rafique et al., 2018; Sanjabi et al., 2018b; Lu et al., 2019; Nouiehed et al., 2019; Lu et al., 2019; Jin et al., 2019). In this paper, we focus on design and analysis of black-box (gradient-free) min-max optimization methods, where gradients are neither symbolically nor numerically available, or they are tedious to compute (Conn et al., 2009). Our study is particularly motivated by the design of data poisoning and evasion adversarial attacks from black-box machine learning (ML) or deep learning (DL) systems, whose internal configuration and operating mechanism are unknown to adversaries. The extension of min-max optimization from the FO domain to the gradient-free regime is challenging since the solver suffers from uncertainties in both black-box objective functions and optimization procedure and do not scale well to high-dimensional problems.
We develop a provable and unified black-box min-max stochastic optimization method by integrating a query-efficient randomized zeroth-order (ZO) gradient estimator with a computation-efficient alternating gradient descent-ascent framework, where the former requires a small number of function queries to build a gradient estimate, and the latter needs just one-step descent/ascent update. Recently, ZO optimization has attracted increasing attention in solving ML/DL problems. For example, ZO optimization serves as a powerful and practical tool for generation of black-box adversarial examples
to evaluate the adversarial robustness of ML/DL models (Chen et al., 2017; Ilyas et al., 2018; Tu et al., 2018; Ilyas et al., 2019). ZO optimization can also help to solve automated ML problems, where the gradients with respect to ML pipeline configuration parameters are intractable (Aggarwal et al., 2019). Furthermore, ZO optimization provides computationally-efficient alternatives of high-order optimization methods for solving complex ML/DL tasks, e.g., robust training by leveraging input gradient or curvature regularization (Finlay & Oberman, 2019; Moosavi-Dezfooli et al., 2019), modelagnostic meta-learning (Fallah et al., 2019), network control and management (Chen & Giannakis, 2018), and data processing in high dimension (Liu et al., 2018b). Other recent applications include generating model-agnostic contrastive explanations (Dhurandhar et al., 2019) and escaping saddle points (Flokas et al., 2019). Current studies (Ghadimi & Lan, 2013; Nesterov & Spokoiny, 2015; Duchi et al., 2015; Ghadimi et al., 2016; Shamir, 2017; Liu et al., 2019) suggested that ZO methods typically agree with the iteration complexity of FO methods but encounter a slowdown factor up to a small-degree polynomial of the problem dimensionality. To the best of our knowledge, it was an open question whether any convergence rate analysis can be established for black-box min-max optimization.
Contribution. We summarize our contributions as follows. (i) We first identify a class of black-box attack and robust learning problems which turn out to be min-max black-box optimization problems. (ii) We propose a scalable and principled framework (ZO-Min-Max) for solving constrained minmax saddle point problems under both one-sided and two-sided black-box objective functions. Here the one-sided setting refers to the scenario where only the outer minimization problem is black-box. (iii) We provide a novel convergence analysis characterizing the number of objective function evaluations required to attain locally robust solution to black-box min-max problems with nonconvex outer minimization and strongly concave inner maximization. Our analysis handles stochasticity in both objective function and ZO gradient estimator, and shows that ZO-Min-Max yields O(1/T + 1/b + d/q) convergence rate, where T is number of iterations, b is mini-batch size, q is number of random direction vectors used in ZO gradient estimation, and d is number of optimization variables. (iv) We demonstrate the effectiveness of our proposal in practical data poisoning and evasion attack generation problems.1

heading: 2 RELATED WORK
text: FO min-max optimization. Gradient-based methods have been applied with celebrated success to solve min-max problems such as robust learning (Qian et al., 2019), generative adversarial networks (GANs) (Sanjabi et al., 2018a), adversarial training (Al-Dujaili et al., 2018b; Madry et al., 2017a), and robust adversarial attack generation (Wang et al., 2019b). Some of FO methods are motivated by theoretical justifications based on Danskin’s theorem (Danskin, 1966), which implies that the negative of the gradient of the outer minimization problem at inner maximizer is a descent direction (Madry et al., 2017a). Convergence analysis of other FO min-max methods has been studied under different problem settings, e.g., (Lu et al., 2019; Qian et al., 2019; Rafique et al., 2018; Sanjabi et al., 2018b; Nouiehed et al., 2019). It was shown in (Lu et al., 2019) that a deterministic FO min-max algorithm has O(1/T ) convergence rate. In (Qian et al., 2019; Rafique et al., 2018), stochastic FO min-max methods have also been proposed, which yield the convergence rate in the order of O(1/ √ T ) and O(1/T 1/4), respectively. However, these works were restricted to unconstrained optimization at the minimization side. In (Sanjabi et al., 2018b), noncovnex-concave min-max problems were studied, but the proposed analysis requires solving the maximization problem only up to some small error. In (Nouiehed et al., 2019), the O(1/T ) convergence rate was proved for nonconvex-nonconcave min-max problems under Polyak- Łojasiewicz conditions. Different from the aforementioned FO settings, ZO min-max stochastic optimization suffers randomness from both stochastic sampling in objective function and ZO gradient estimation, and this randomness would be coupled in alternating gradient descent-descent steps and thus make it more challenging in convergence analysis.
Gradient-free min-max optimization. In the black-box setup, coevolutionary algorithms were used extensively to solve min-max problems (Herrmann, 1999; Schmiedlechner et al., 2018). However, they may oscillate and never converge to a solution due to pathological behaviors such as focusing and relativism (Watson & Pollack, 2001). Fixes to these issues have been proposed and analyzed—e.g.,
1Source code will be released.
asymmetric fitness (Jensen, 2003; Branke & Rosenbusch, 2008). In (Al-Dujaili et al., 2018c), the authors employed an evolution strategy as an unbiased approximate for the descent direction of the outer minimization problem and showed empirical gains over coevlutionary techniques, albeit without any theoretical guarantees. Min-max black-box problems can also be addressed by resorting to direct search and model-based descent and trust region methods (Audet & Hare, 2017; Larson et al., 2019; Rios & Sahinidis, 2013). However, these methods lack convergence rate analysis and are difficult to scale to high-dimensional problems. For example, the off-the-shelf model-based solver COBYLA only supports problems with 216 variables at maximum in SciPy Python library (Jones et al., 2001), which is even smaller than the size of a single ImageNet image. The recent work (Bogunovic et al., 2018) proposed a robust Bayesian optimization (BO) algorithm and established a theoretical lower bound on the required number of the min-max objective evaluations to find a near-optimal point. However, BO approaches are often tailored to low-dimensional problems and its computational complexity prohibits scalable application. From a game theory perspective, the min-max solution for some problems correspond to the Nash equilibrium between the outer minimizer and the inner maximizer, and hence black-box Nash equilibria solvers can be used (Picheny et al., 2019; Al-Dujaili et al., 2018a). This setup, however, does not always hold in general. Our work contrasts with the above lines of work in designing and analyzing black-box min-max techniques that are both scalable and theoretically grounded.

heading: 3 PROBLEM SETUP
text: In this section, we define the black-box min-max problem and briefly motivate its applications. By min-max, we mean that the problem is a composition of inner maximization and outer minimization of the objective function f . By black-box, we mean that the objective function f is only accessible via point-wise functional evaluations. Mathematically, we have
min x∈X max y∈Y f(x,y) (1)
where x and y are optimization variables, f is a differentiable objective function, and X ⊂ Rdx and Y ⊂ Rdy are compact convex sets. For ease of notation, let dx = dy = d. In (1), the objective function f could represent either a deterministic loss or stochastic loss f(x,y) = Eξ∼p [f(x,y; ξ)], where ξ is a random variable following the distribution p. In this paper, we consider the stochastic variant in (1).
We focus on two black-box scenarios in which gradients (or stochastic gradients under randomly sampled ξ) of f w.r.t. x or y are not accessed.
(a) One-sided black-box: f(x,y) is a white box w.r.t. y but a black box w.r.t. x.
(b) Two-sided black-box: f(x,y) is a black box w.r.t. both x and y.
Motivation of setup (a) and (b). Both setups are well motivated from the design of black-box adversarial attacks. The formulation of the one-sided black-box min-max problem corresponds to a particular type of attack, known as black-box ensemble evasion attack, where the attacker generates adversarial examples (i.e., crafted examples with slight perturbations for misclassification at the testing phase) and optimizes its worst-case performance against an ensemble of black-box classifiers and/or example classes. The formulation of two-sided black-box min-max problem represents another type of attack at the training phase, known as black-box poisoning attack, where the attacker deliberately influences the training data (by injecting poisoned samples) to manipulate the results of a black-box predictive model.
Although problems of designing ensemble evasion attack (Liu et al., 2016; 2018a; Wang et al., 2019b) and data poisoning attack (Jagielski et al., 2018; Wang et al., 2019a) have been studied in the literature, most of them assumed that the adversary has the full knowledge of the target ML model, leading to an impractical white-box attack setting. By contrast, we provide a solution to min-max attack generation under black-box ML models. We refer readers to Section 6 for further discussion and demonstration of our framework on these problems.

heading: 4 ZO-MIN-MAX: A FRAMEWORK FOR BLACK-BOX MIN-MAX OPTIMIZATION
text: Our interest is in a scalable and theoretically principled framework for black-box min-max problems of the form (1). To this end, we first introduce a randomized gradient estimator that only requires a few number of point-wise function evaluations. Based on that, we then propose a ZO alternating projected gradient method to solve (1) under both one-sided and two-sided black-box setups.
Randomized gradient estimator. In the ZO setting, we adopt a randomized gradient estimator to estimate the gradient of a function with the generic form h(x) := Eξ[h(x; ξ)] (Liu et al., 2019; Gao et al., 2014),
∇̂xh(x) = 1
bq ∑ j∈I q∑ i=1 d[h(x + µui; ξj)− h(x; ξj)] µ ui, (2)
where d is number of variables, I denotes the mini-batch set of b i.i.d. stochastic samples {ξj}bj=1, {ui}qi=1 are q i.i.d. random direction vectors drawn uniformly from the unit sphere, and µ > 0 is a smoothing parameter. We note that the ZO gradient estimator (2) involves randomness from both stochastic sampling w.r.t. ui as well as the random direction sampling w.r.t. ξj . It is known from (Gao et al., 2014, Lemma 2) that ∇̂xh(x) provides an unbiased estimate of the gradient of the smoothing function of h rather than the true gradient of h. Here the smoothing function of h is defined by hµ(x) = Ev[h(x+µv)], where v follows the uniform distribution over the unit Euclidean ball. Besides the bias, we provide an upper bound on the variance of (2) in Lemma 1. Lemma 1. Suppose that for all ξ, h(x; ξ) has Lh Lipschitz continuous gradients and the gradient of h(x; ξ) is upper bounded as ‖∇xh(x; ξ)‖22 ≤ η2 at x ∈ Rd. Then E [ ∇̂xh(x) ] = ∇xhµ(x),
E [ ‖∇̂xh(x)−∇xhµ(x)‖22 ] ≤ 2η 2
b +
4dη2 + µ2L2hd 2
q := σ2(Lh, µ, b, q, d), (3)
where the expectation is taken over all randomness.
Proof: See Appendix A.2. In Lemma 1, if we choose µ ≤ 1/ √ d, then the variance bound is given by O(1/b + d/q). In our
problem setting (1), the ZO gradients ∇̂xf(x,y) and ∇̂yf(x,y) follow the generic form of (2) by fixing y and letting h(·) := f(·,y) or by fixing x and letting h(·) := f(x, ·), respectively.
Algorithmic framework. To solve problem (1), we alternatingly perform ZO projected gradient descent/ascent method for updating x and y. Specifically, for one-sided ZO min-max optimization, the ZO projected gradient descent (ZO-PGD) over x yields
x(t) = projX ( x(t−1) − α∇̂xf ( x(t−1),y(t−1) )) , (4)
where t is the iteration index, ∇̂xf denotes the ZO gradient estimate of f w.r.t. x, α > 0 is the learning rate at the x-minimization step, and projX (a) signifies the projection of a onto X , given by the solution to the problem minx∈X ‖x− a‖22. For two-sided ZO min-max optimization, in addition to (4), our update on y obeys the ZO projected gradient ascent (ZO-PGA)
y(t) = projY ( y(t−1) + β∇̂yf ( x(t),y(t−1) )) , (5)
where β > 0 is the learning rate at the y-maximization step. The proposed method is named as ZO-Min-Max; see Algorithm 1.
Why estimates gradient rather than distribution of function values? Besides ZO optimization using random gradient estimates, the black-box min-max problem (1) can also be solved using the Bayesian optimization (BO) approach, e.g., (Bogunovic et al., 2018; Al-Dujaili et al., 2018a). The core idea of BO is to approximate the objective function as a Gaussian process (GP) learnt from the history of function values at queried points. Based on GP, the solution to problem (1) is then updated by maximizing a certain reward function, known as acquisition function. The advantage of BO is
its mild requirements on the setting of black-box problems, e.g., at the absence of differentiability. However, BO usually does not scale beyond low-dimensional problems since learning the accurate GP model and solving the acquisition problem takes intensive computation cost per iteration. By contrast, our proposed method is more efficient, and mimics the first-order method by just using the random gradient estimate (2) as the descent/ascent direction. In Figure A1, we compare ZO-Min-Max with the BO based STABLEOPT algorithm proposed by (Bogunovic et al., 2018) through a toy example shown in (Bogunovic et al., 2018, Sec. 5). As we can see, ZO-Min-Max not only achieves more accurate solution but also requires less computation time. We refer readers to Appendix B for details.
Algorithm 1 ZO-Min-Max to solve problem (1)
1: Input: given x(0) and y(0), learning rates α and β, the number of random directions q, and the possible mini-batch size b for stochastic optimization 2: for t = 1, 2, . . . , T do 3: x-step: perform ZO-PGD (4) 4: y-step: 5: if f(x(t),y) is black box w.r.t. y then 6: perform ZO-PGA (5) 7: else 8: perform PGA using∇yf(x(t),y(t−1)) as ascent direction in (5) 9: end if
10: end for
Technical challenges in convergence analysis. The convergence analysis of ZO-Min-Max is more challenging than the case of FO min-max algorithms. Besides the inaccurate estimate of the gradient, the stochasticity of the estimator makes the convergence analysis sufficiently different from the FO deterministic case (Lu et al., 2019; Qian et al., 2019), since the errors in minimization and maximization are coupled as the algorithm proceeds.
Moreover, the conventioanl analysis of ZO optimization for single-objective problems cannot directly be applied to ZO-Min-Max. Even at the one-sided black-box setting, ZO-Min-Max conducts alternating optimization using one-step ZO-PGD and PGA with respect to x and y respectively. This is different from a reduced ZO optimization problem with respect to x only by solving problem minx∈X h(x) := miny∈Y f(x,y), which requires the algorithm to obtain the solution to miny∈Y f(x,y) at a given x (when querying h(x) for a ZO gradient estimation). However, this process is usually non-trivial or computationally intensive.
In particular, one key difficulty stems from the alternating algorithmic structure (namely, primal-dual framework) as the problem is in the min-max form, which leads to opposite optimization directions (minimization vs maximization) over variable x and y respectively. Even applying ZO optimization only to one side, it needs to quantify the effect of ZO gradient estimation on the descent over both x and y. We provide a detailed convergence analysis of ZO-Min-Max in the next section.

heading: 5 CONVERGENCE ANALYSIS
text: We begin by elaborating on assumptions and notations used in analyzing the convergence of ZO-MinMax (Algorithm 1).
A1: In (1), f(x,y) is continuously differentiable, and is strongly concave w.r.t. y with parameter γ > 0, namely, given x ∈ X , f(x,y1) ≤ f(x,y2) +∇yf(x,y2)T (y1 − y2) − γ2 ‖y1 − y2‖
2 for all points y1,y2 ∈ Y . And f is lower bounded by a finite number f∗ and has bounded gradients ‖∇xf(x,y; ξ)‖ ≤ η2 and ‖∇yf(x,y; ξ)‖ ≤ η2 for stochastic optimization with ξ ∼ p. Here ‖ · ‖ denotes the `2 norm. The constraint sets X ,Y are convex and bounded with diameter R. A2: f(x,y) has Lipschitz continuous gradients, i.e., there existsLx, Ly > 0 such that ‖∇xf(x1,y)− ∇xf(x2,y)‖ ≤ Lx‖x1−x2 ‖ for ∀x1,x2 ∈ X , and ‖∇yf(x1,y) − ∇yf(x2,y)‖ ≤ Ly‖x1−x2 ‖ and ‖∇yf(x,y1)−∇yf(x,y2)‖ ≤ Ly‖y1−y2 ‖ for ∀y1,y2 ∈ Y . We note that A1 and A2 are required for analyzing the convergence of ZO-Min-Max. They were used even for the analysis of first-order min-max optimization methods (Lu et al., 2019; Nouiehed et al., 2019) and first-order methods for nonconvex optimization with a single objective function (Chen et al., 2019; Ward et al., 2019). In A1, the strongly concavity of f(x,y) with respect to y holds for applications such as robust learning over multiple domains (Qian et al., 2019), and adversarial attack generation that will be introduced in Section 6. In A2, the assumption of smoothness
(namely, Lipschitz continuous gradient) is required to quantify the descent of the alternating projected stochastic gradient descent-ascent method. Even for single-objective non-convex optimization, e.g., (Chen et al., 2019; Bernstein et al., 2018), A2 is needed in analysis. For clarity, we also summarize the problem and algorithmic parameters used in our convergence analysis in Table A1 of Appendix.
We measure the convergence of ZO-Min-Max by the proximal gradient (Lu et al., 2019; Ghadimi et al., 2016), G(x,y) = [
(1/α) (x−projX (x−α∇xf(x,y))) (1/β) ( y−projY(y+β∇yf(x,y)) ) ] , (6) where (x,y) is a first-order stationary point of (1) iff ‖G(x,y)‖ = 0. In what follows, we delve into our convergence analysis. First, Lemma 2 shows the descent property of ZO-PGD at the x-minimization step in Algorithm 1.
Lemma 2. (Descent lemma in minimization) Under A1-A2, let (x(t),y(t)) be a sequence generated by Algorithm 1. When f(x,y) is black-box w.r.t. x, then we have following descent property w.r.t. x:
E[f(x(t+1),y(t))] ≤ E[f(x(t),y(t))]− ( 1
α − Lx 2
) E‖∆(t+1)x ‖2 + ασ2x + Lxµ2 (7)
where ∆(t)x := x(t)−x(t−1), and σ2x := σ2(Lx, µ, b, q, d) defined in (3).
Proof: See Appendix A.3.1.
It is clear from Lemma 2 that updating x leads to the reduced objective value when choosing a small learning rate α. However, ZO gradient estimation brings in additional errors in terms of ασ2x and Lxµ
2, where the former is induced by the variance of gradient estimates in (3) and the latter is originated from bounding the distance between f and its smoothing version; see (25) in Appendix A.3.
Convergence rate of ZO-Min-Max by performing PGA. We next investigate the convergence of ZO-Min-Max when FO PGA is used at the y-maximization step (Line 8 of Algorithm 1) for solving one-sided black-box optimization problems.
Lemma 3. (Descent lemma in maximization) Under A1-A2, let (x(t),y(t)) be a sequence generated by Algorithm 1 and define the potential function as
P(x(t),y(t),∆(t)y ) = E[f(x(t),y(t))] + 4 + 4β2L2y − 7βγ
2β2γ E‖∆(t)y ‖2, (8)
where ∆(t)y := y(t)−y(t−1). When f(x,y) is black-box w.r.t. x and white-box w.r.t. y, then we have the following descent property w.r.t. y:
P(x(t+1),y(t+1),∆(t+1)y ) ≤P(x(t+1),y(t),∆(t)y ) − ( 1
2β − 2L2y γ
) E‖∆(t+1)y ‖2 + ( 2
γ2β + β 2
) L2xE‖∆(t+1)x ‖2, (9)
Proof: See Appendix A.3.2.
It is shown from (9) that when β is small enough, then the term (1/(2β)− 2L2y/γ)E‖∆ (t+1) y ‖2 will give some descent of the potential function after performing PGA, while the last term in (9) will give some ascent to the potential function. However, such a quantity will be compensated by the descent of the objective function in the minimization step shown by Lemma 2. Combining Lemma 2 and Lemma 3, we obtain the convergence rate of ZO-Min-Max in Theorem 1.
Theorem 1. Suppose that A1-A2 hold, the sequence (x(t),y(t)) over T iterations is generated by Algorithm 1 in which learning rates satisfy β < 1/(4L2y) and α ≤ min{1/Lx, 1/(Lx/2 + 2L2x/(γ
2β) + βL2x/2)}. When f(x,y) is black-box w.r.t. x and white-box w.r.t. y, the convergence rate of ZO-Min-Max under a uniformly and randomly picked (x(r),y(r)) from {(x(t),y(t))}Tt=1 is given by
E‖G(x(r),y(r))‖2 ≤ c ζ (P1 − f∗ − νR2) T + cασ2x ζ + cLxµ 2 ζ (10)
where ζ is a constant independent on the parameters µ, b, q, d and T , Pt := P(x(t),y(t),∆(t)y ) given by (8), c = max{Lx + 3/α, 3/β}, ν = min{4 + 4β2L2y − 7βγ, 0}/(2β2γ), σ2x is variance bound of ZO gradient estimate given in (7), and f∗, R, γ, Lx and Ly have been defined in A1-A2.
Proof: See Appendix A.3.3.
To better interpret Theorem 1, we begin by clarifying the parameters involved in our convergence rate (10). First, the parameter ζ appears in the denominator of the derived convergence error. However, ζ has a non-trivial lower bound given appropriate learning rates α and β (see Remark 1 that we will show later). Second, the parameter c is inversely proportional to α and β. Thus, to guarantee the constant effect of the ratio c/ξ, it is better not to set these learning rates too small; see a specification in Remark 1-2. Third, the parameter ν is non-negative and appears in terms of −νR2, thus, it will not make convergence rate worse. Fourth, P1 is the initial value of the potential function (8). By setting an appropriate learning rate β (e.g., following Remark 2), P1 is then upper bounded by a constant determined by the initial value of the objective function, the distance of the first two updates, Lipschitz constant Ly and strongly concave parameter γ. We next provide Remarks 1-3 on Theorem 1.
Remark 1. Recall that ζ = min{c1, c2} (Appendix B.2.3), where c1 = 1/(2β) − 2L2y/γ and c2 = 1 α − ( Lx 2 + 2L2x γ2β + βL2x 2 ). Given the fact that Lx and Ly are Lipschitz constants and γ is the strongly concavity constant, a proper lower bound of ζ thus relies on the choice of the learning rates α and β. By setting β ≤ γ8L2y and α ≤ 1/(Lx + 4L2x γ2β + βL 2 x), it is easy to verify that c1 ≥ 2L2y γ and c2 ≥ Lx2 + 2L2x γ2β + βL2x 2 ≥ Lx 2 + 2L2x γ . Thus, we obtain that ζ ≥ min{ 2L2y γ , 2L2x γ + Lx 2 }. This justifies that ζ has a non-trivial lower bound, which will not make the convergence error bound (10) vacuous (although the bound has not been optimized over α and β).
Remark 2. It is not wise to set learning rates α and β to extremely small values since c is inversely proportional to α and β. Thus, we typically choose β = γ8L2y and α = 1/(Lx + 4L2x γ2β + βL 2 x) in Remark 1 to guarantee the constant effect of c/ζ. Remark 3. By setting µ ≤ min{1/ √ d, 1/ √ T}, we obtain σ2x = O(1/b+ d/q) from Lemma 1, and Theorem 1 implies that ZO-Min-Max yields O(1/T + 1/b+ d/q) convergence rate for one-sided black-box optimization. Compared to the FO rate O(1/T ) (Lu et al., 2019; Sanjabi et al., 2018a), ZO-Min-Max converges only to a neighborhood of stationary points with O(1/T ) rate, where the size of the neighborhood is determined by the mini-batch size b and the number of random direction vectors q used in ZO gradient estimation. It is also worth mentioning that such a stationary gap may exist even in the FO/ZO projected stochastic gradient descent for solving single-objective minimization problems (Ghadimi et al., 2016).
As shown in Remark 3, ZO-Min-Max could result in a stationary gap. A large mini-batch size b or number of random direction vectors q can improve its iteration complexity. However, this requires O(bq) times more function queries per iteration from (2). It implies the tradeoff between iteration complexity and function query complexity in ZO optimization.
Convergence rate of ZO-Min-Max by performing ZO-PGA. We now focus on the convergence analysis of ZO-Min-Max when ZO PGA is used at the y-maximization step (Line 6 of Algorithm 1) for two-sided black-box optimization problems.
Lemma 4. (Descent lemma in maximization) Under A1-A2, let (x(t),y(t)) be a sequence generated by Algorithm 1 and define the potential function as
P ′(x(t),y(t),∆(t)y ) = E[f(x(t),y(t))] + 4 + 4(3L2y + 2)β 2 − 7βγ β2γ E‖∆(t)y ‖2. (11)
When function f(x,y) is black-box w.r.t. both x and y, we have the following descent w.r.t. y: P ′(x(t+1),y(t+1),∆(t+1)y ) ≤ P ′(x(t+1),y(t),∆(t)y )− ( 1
2β −
6L2y + 4
γ
) E‖∆(t+1)y ‖2
+ ( 6L2x γ2β + 3βL2x 2 ) E‖∆(t+1)x ‖2 + 7β2γ2 + 28βγ + 12 βγ2 σ2y + βγ + 4 4β2γ µ2d2L2y, (12)
where σ2y := σ 2(Ly, µ, b, q, d) given in (3).
Proof: See Appendix A.4.1.
Lemma 4 is analogous to Lemma 3 by taking into account the effect of ZO gradient estimate ∇̂yf(x,y) on the potential function (11). Such an effect is characterized by the terms related to σ2y and µ 2d2L2y in (12).
Theorem 2. Suppose that A1-A2 hold, the sequence (x(t),y(t)) over T iterations is generated by Algorithm 1 in which learning rates satisfy β < γ/(4(3L2y + 2)) and α ≤ min{Lx, 1/(Lx/2 + 6L2x/(γ
2β) + 3βL2x/2)}. When f(x,y) is black-box w.r.t. both x and y, the convergence rate of ZO-Min-Max under a uniformly and randomly picked (x(r),y(r)) from {(x(t),y(t))}Tt=1 is given by
E‖G(x(r),y(r))‖2 ≤ c ζ′ P ′1 − f∗ − ν′R2 T + cα ζ′ σ2x + ( cb1 ζ′ + d2L2y ) µ2 + ( cb2 ζ′ + 2 ) σ2y,
where ζ ′ is a constant independent on the parameters µ, b, q, d and T , P ′t := P ′(x(t),y(t),∆ (t) y ) in (11), c has been defined in (10), ν′ = min{4+4(3L2y+2)β
2−7βγ,0} β2γ , b1 = Lx + d2L2y(4+βγ) 4β2γ and
b2 = 7β2γ2+28βγ+12 βγ2 , σ 2 x and σ 2 y have been introduced in (7) and (12), and f ∗, R, γ, Lx and Ly have been defined in A1-A2.
Proof: See Appendix A.4.2.
Following the similar argument in Remark 1 of Theorem 1, one can choose proper learning rates α and β to obtain valid lower bound on ζ ′. However, different from Theorem 1, the convergence error shown by Theorem 2 involves an additional error term related to σ2y and has worse dimension-dependence on the term related to µ2. The latter yields a more restricted choice of the smoothing parameter µ: we obtain O(1/T + 1/b+ d/q) convergence rate when µ ≤ 1/(d √ T ).

heading: 6 EXPERIMENTS
text: In this section, we evaluate the empirical performance of ZO-Min-Max on applications of adversarial exploration: 1) design of black-box ensemble attack against two neural networks Inception-V3 (Szegedy et al., 2016) and ResNet-50 (He et al., 2016) under ImageNet (Deng et al., 2009), and 2) design of black-box poisoning attack against a logistic regression model.
Black-box ensemble evasion attack via universal perturbation We consider the scenario in which the attacker generates adversarial examples against an ensemble of multiple classifiers and/or image classes (Liu et al., 2016; 2018a). More formally, let (z, l) denote a legitimate image z with the true class label l, and z′ := z + x denote an adversarial example, where x signifies the adversarial perturbation. Here the natural image z and the perturbed image z + x are normalized to [−0.5, 0.5]d. Considering I classes of images (each group of images corresponding to the same class li is denoted by Ωi) and J network models, the adversary is to find the universal perturbation x across I image classes and J models. The proposed attack problem is given by
minimize x∈X maximize w∈W
f1(x,w) := ∑J j=1 ∑I i=1 [wijFij (x; Ωi, li)]− λ‖w − 1/(IJ)‖ 2 2, (13)
where x and w ∈ RIJ are optimization variables, and wij denotes the (i, j)th entry of w corresponding to the importance weight of attacking image class i under neural network model j. In problem (13), X denotes the perturbation constraint, e.g., X = {x | ‖x‖∞ ≤ , z + x ∈ [−0.5, 0.5]d,∀z ∈ ∪iΩi}, W = {w | 1Tw = 1,w ≥ 0}, Fij (x; Ωi, li) is the attack loss for attacking the set of images at class li under model j, and λ > 0 is a regularization parameter. We note that {Fij} in (13) are black-box functions w.r.t. x since the network models are blind to the adversary, which cannot perform back-propagation to obtain gradients. By contrast, it is a white-box and strongly concave function w.r.t. w once the function values of {Fij} are given. Thus, problem (13) belongs to the one-sided black-box optimization problem.
In our experiments, we consider J = 2 for Inception-V3 and ResNet-50, and I = 2 for two classes, each of which contains 20 images randomly selected from ImageNet (Deng et al., 2009). We also
specify the attack loss Fij in (13) as the C&W untargeted attack loss (Carlini & Wagner, 2017), Fij (x; Ωi, li) = (1/|Ωi|) ∑ z∈Ωi max{gj(z + x)li −max k 6=li gj(z + x)k, 0}, (14)
where |Ωi| is the cardinality of the set Ωi, gj(z + x)k denotes the prediction score of class k given the input z + x using model j. In (13), we also set λ = 5. In Algorithm 1, we set α = 0.05, β = 0.01, q = 10 and µ = 5× 10−3, and use the full batch of image samples in attack generation. In experiment, we compare ZO-Min-Max with FO-Min-Max and ZO-Finite-Sum, where the former is the FO counterpart of Algorithm 1, and the latter is ZO-PSGD (Ghadimi et al., 2016) to minimize the finite-sum (average) loss rather than the worst-case (min-max) loss. The comparison with ZOFinite-Sum was motivated by the previous work on designing the adversarial perturbation against model ensembles (Liu et al., 2018a) in which the averaging attack loss over multiple models was considered. Note that although ZO-Finite-Sum consider a different loss function, it is a baseline from the perspective of attack generation.
In Figure 1, we demonstrate the empirical convergence of ZO-Min-Max to solve problem (13) from the stationary gap ‖G(x,y)‖2 given in (6) and the attack loss Fij under each model-class pair. In Figure 1-(a), the stationary gap decreases as the iteration increases, which is consistent with the reduction in the attack loss at each MjCi. Here M and C represents network model and image class, respectively. By comparing ZO-Min-Max with FO-Min-Max in Figure 1-(b), we see that the latter yields faster convergence than the former. However, FO-Min-Max has to access the full knowledge on the target neural network for computing the gradient of individual attack losses, yielding white-box attack rather than black-box attack. In Figure 1-(c), We also compare ZO-Min-Max with ZO-FiniteSum, where the latter minimizes the average loss ∑J j=1 ∑I i=1 Fij over all model-class combinations. As we can see, our approach significantly improves the worst-case attack performance (corresponding to M1C1). Here the worst case represents the most robust model-class pair against the attack. This suggests that ZO-Min-Max takes into account different robustness levels of model-class pairs through the design of importance weights w. This can also be evidenced from Figure A2 in Appendix: M1C1 has the largest weight while M2C2 corresponds to the smallest weight. In Figure A3 of Appendix, we further contrast the success or failure of attacking each image using the obtained universal perturbation x with the attacking difficulty (in terms of required iterations for successful adversarial example) of using per-image non-universal PGD attack (Madry et al., 2017b).
Black-box poisoning attack against logistic regression model Let D = {zi, ti}ni=1 denote the training dataset, among which n′ n samples are corrupted by a perturbation vector x, leading to poisoned training data zi + x towards breaking the training process and thus the prediction accuracy. The poisoning attack problem is then formulated as
maximize ‖x‖∞≤ minimize θ f2(x,θ) := Ftr(x,θ;D0) + λ‖θ‖22, (15)
where x and θ are optimization variables, Ftr(x,θ;D0) denotes the training loss over model parameters θ at the presence of data poison x, and λ > 0 is a regularization parameter. Note that problem (15) can be written in the form of (1) with the objective function−f2(x,θ). Clearly, if Ftr is a convex
loss (e.g., logistic regression or linear regression (Jagielski et al., 2018)), then−f2 is strongly concave in θ. Since the adversary has no knowledge on the training procedure and data, f2(x,θ) is a two-sided black-box function. We provide more details on problem (15) in Appendix C. In Algorithm 1, unless specified otherwise we choose b = 100, q = 5, α = 0.02, β = 0.05, and T = 50000. We report the empirical results averaged over 10 independent trials with random initialization. We compare our method with FO-Min-Max and the BO solver for robust optimization STABLEOPT (Bogunovic et al., 2018) in the data poisoning example of a relatively small problem size.
In Figure 2, we present the convergence performance of ZO-Min-Max to generate the data poisoning attack and validate its attack performance in terms of testing accuracy of the logistic regression model trained on the poisoned dataset. Unless specified otherwise, we set 15% poisoning ratio and λ = 10−3 for problem (15). We examine the sensitivity of the regularization parameter λ in Figure A4. Figure 2-(a) shows the stationary gap defined in (6) obtained by ZO-Min-Max under different number of random direction vectors while estimating gradients (2). As we can see, a moderate choice of q (e.g., q ≥ 5 in our example) is sufficient to achieve near-optimal solution compared with FO-Min-Max. However, it suffers from a convergence bias due to the presence of stochastic sampling, consistent with Theorem 1 and 2.
Figure 2-(b) demonstrates the testing accuracy (against iterations) of the model learnt from poisoned training data, where the poisoning attack is generated by ZO-Min-Max (black-box attack) and FO-Min-Max (white-box attack). As we can see, ZO-Min-Max yields promising attacking performance comparable to FO-Min-Max. We can also see that by contrast with the testing accuracy of the clean model (94% without poison), the poisoning attack eventually reduces the testing accuracy (below 70%). Furthermore, in Figure 2-(c), we present the testing accuracy of the learnt model under different data poisoning ratios. As we can see, only 5% poisoned training data can significantly break the testing accuracy of a well-trained model. In Figure 3, we compare ZO-Min-Max with STABLEOPT (Bogunovic et al., 2018) in terms of testing accuracy versus computation time. Fol-
lowing (Bogunovic et al., 2018), we present the best accuracy achieved up to the current time step. We observe that STABLEOPT is has a poorer scalability while our method reaches a data poisoning attack that induces much worse testing accuracy within 500 seconds.

heading: 7 CONCLUSION
text: This paper addresses black-box robust optimization problems given a finite number of function evaluations. In particular, we present ZO-Min-Max: a framework of alternating, randomized gradient estimation based ZO optimization algorithm to find a first-order stationary solution to the black-box min-max problem. Under mild assumptions, ZO-Min-Max enjoys a sub-linear convergence rate. It scales to dimensions that are infeasible for recent robust solvers based on Bayesian optimization. Furthermore, we experimentally demonstrate the potential application of the framework on real-world scenarios, viz. black-box evasion and data poisoning attacks.

heading: APPENDIX

heading: A DETAILED CONVERGENCE ANALYSIS

heading: A.1 TABLE OF PARAMETERS
text: In Table A1, we summarize the problem and algorithmic parameters used in our convergence analysis.
Table A1: Summary of problem and algorithmic parameters and their descriptions.
parameter description d # of optimization variables b mini-batch size q # of random direction vectors used in ZO gradient estimation α learning rate for ZO-PGD β learning rate for ZO-PGA γ strongly concavity parameter of f(x,y) with respect to y η upper bound on the gradient norm, implying Lipschitz continuity
Lx, Ly Lipschitz continuous gradient constant of f(x,y) with respect to x and y respectively R diameter of the compact convex set X or Y f∗ lower bound on the function value, implying feasibility σ2x, σ 2 y variance of ZO gradient estimator for variable x and y respectively

heading: A.2 PROOF OF LEMMA 1
text: Before going into the proof, let’s review some preliminaries and give some definitions. Define hµ(x, ξ) to be the smoothed version of h(x, ξ) and since ξ models a subsampling process over a finite number of candidate functions, we can further have hµ(x) , Eξ[hµ(x, ξ)] and∇xhµ(x) = Eξ[∇xhµ(x, ξ)] Recall that in the finite sum setting when ξj parameterizes the jth function, the gradient estimator is given by
∇̂xh(x) = 1
bq ∑ j∈I q∑ i=1 d[h(x + µui; ξj)− h(x; ξj)] µ ui. (16)
where I is a set with b elements, containing the indices of functions selected for gradient evaluation. From standard result of the zeroth order gradient estimator, we know
EI [ Eui,i∈[q] [ ∇̂xh(x) ] ∣∣I] = EI 1 b ∑ j∈I ∇xfµ(x, ξj)  = ∇xhµ(x). (17) Now let’s go into the proof. First, we have
E [ ‖∇̂xh(x)−∇xhµ(x)‖22 ] =EI Eui,i∈[q]  ∥∥∥∥∥∥∇̂xh(x)− 1b ∑ j∈I ∇xfµ(x, ξj) + 1 b ∑ j∈I ∇xfµ(x, ξj)−∇xhµ(x) ∥∥∥∥∥∥ 2
2
∣∣∣∣I  
≤2EI Eui,i∈[q]  ∥∥∥∥∥∥∇̂xh(x)− 1b ∑ j∈I ∇xfµ(x, ξj) ∥∥∥∥∥∥ 2
2
+ ∥∥∥∥∥∥1b ∑ j∈I ∇xfµ(x, ξj)−∇xhµ(x) ∥∥∥∥∥∥ 2
2
∣∣∣∣I   .
(18)
Further, by definition, given I , ∇̂xh(x) is the average of ZO gradient estimates under q i.i.d. random directions, each of which has the mean 1b ∑ j∈I ∇xfµ(x, ξj). Thus for the first term at the right-
hand-side (RHS) of the above inequality, we have
Eui,i∈[q]  ∥∥∥∥∥∥∇̂xh(x)− 1b ∑ j∈I ∇xfµ(x, ξj) ∥∥∥∥∥∥ 2
2
∣∣∣∣I  ≤1
q 2d ∥∥∥∥∥∥1b ∑ j∈I ∇xf(x, ξj) ∥∥∥∥∥∥ 2 + µ2L2hd 2 2  ≤1 q ( 2dη2 + µ2L2hd 2 2 ) (19)
where the first inequality is by the standard bound of the variance of zeroth order estimator and the second inequality is by the assumption that ‖∇xh(x; ξ)‖2 ≤ η2 and thus ‖ 1b ∑ j∈I ∇xf(x, ξj)‖2 ≤ η2.In addition, we have
EI Eui,i∈[q]  ∥∥∥∥∥∥1b ∑ j∈I ∇xfµ(x, ξj)−∇xhµ(x) ∥∥∥∥∥∥ 2
2
∣∣∣∣I  
=EI  ∥∥∥∥∥∥1b ∑ j∈I ∇xfµ(x, ξj)−∇xhµ(x) ∥∥∥∥∥∥ 2
2  = 1 b Eξ [ ‖∇xfµ(x, ξ)−∇xhµ(x)‖22 ] ≤ η 2 b (20)
where the second equality is because ξj are i.i.d. draws from the same distribution as ξ and E[∇xfµ(x, ξ)] = ∇xhµ(x), the last inequality is because ‖∇xfµ(x, ξ)‖22 ≤ η2 by assumption. Substituting (19) and (20) into (18) finishes the proof.

heading: A.3 CONVERGENCE ANALYSIS OF ZO-MIN-MAX BY PERFORMING PGA
text: In this section, we will provide the details of the proofs. Before proceeding, we have the following illustration, which will be useful in the proof.
The order of taking expectation: Since iterates x(t),y(t),∀t are random variables, we need to define
F (t) = {x(t),y(t),x(t−1),y(t−1), . . . ,x(1),y(1)} (21)
as the history of the iterates. Throughout the theoretical analysis, taking expectation means that we take expectation over random variable at the tth iteration conditioned on F (t−1) and then take expectation over F (t−1).
Subproblem: Also, it is worthy noting that performing (4) and (5) are equivalent to the following optimization problem:
x(t) = min x∈X
〈 ∇̂xf(x(t−1),y(t−1)),x−x(t−1) 〉 + 1
2α ‖x−x(t−1) ‖2, (22)
y(t) = max y∈Y
〈 ∇̂yf(x(t),y(t−1)),y−y(t−1) 〉 − 1
2β ‖y−y(t−1) ‖2. (23)
When f(x,y) is white-box w.r.t. y, (23) becomes
y(t) = max y∈Y
〈 ∇yf(x(t),y(t−1)),y−y(t−1) 〉 − 1
2β ‖y−y(t−1) ‖2. (24)
In the proof of ZO-Min-Max, we will use the optimality condition of these two problems to derive the descent lemmas.
Relationship with smoothing function We denote by fµ,x(x,y) the smoothing version of f w.r.t. x with parameter µ > 0. The similar definition holds for fµ,y(x,y). By taking fµ,x(x,y) as an example, under A2 f and fµ,x has the following relationship (Gao et al., 2014, Lemma 4.1):
|fµ,x(x,y)− f(x,y))| ≤ Lxµ
2
2 and ‖∇xfµ,x(x,y)−∇xf(x,y)‖22 ≤ µ2d2L2x 4 , (25)
|fµ,y(x,y)− f(x,y))| ≤ Lyµ
2
2 and ‖∇yfµ,y(x,y)−∇yf(x,y)‖22 ≤ µ2d2L2y 4 . (26)
First, we will show the descent lemma in minimization as follows.

heading: A.3.1 PROOF OF LEMMA 2
text: Proof: Since f(x,y) has Lx Lipschtiz continuous gradients with respect to x, we have
fµ(x (t+1),y(t)) ≤fµ(x(t),y(t)) + 〈∇xfµ(x(t),y(t)),x(t+1)−x(t)〉+ Lx 2 ‖x(t+1)−x(t) ‖2
=fµ(x (t),y(t)) + 〈∇̂xf(x(t),y(t)),x(t+1)−x(t)〉+ Lx 2 ‖x(t+1)−x(t) ‖2
+ 〈∇xfµ(x(t),y(t))− ∇̂xf(x(t),y(t)),x(t+1)−x(t)〉. (27)
Recall that
x(t+1) = projX (x (t) − α∇̂xf(x(t),y(t))), (28)
From the optimality condition of x-subproblem (22), we have
〈∇̂xf(x(t),y(t)),x(t+1)−x(t)〉 ≤ − 1
α ‖x(t+1)−x(t) ‖2. (29)
Here we use the fact that the optimality condition of problem (22) at the solution x(t+1) yields 〈∇̂xf(x(t),y(t)) + (x(t+1)−x(t))/α,x(t+1)−x〉 ≤ 0 for any x ∈ X . By setting x = x(t), we obtain (29).
In addition, we define another iterate generated by∇xfµ(x(t),y(t))
x̂(t+1) = projX (x (t) − α∇xfµ(x(t),y(t))). (30)
Then, we can have
〈∇xfµ(x(t),y(t))− ∇̂xf(x(t),y(t)),x(t+1)−x(t)〉 =〈∇xfµ(x(t),y(t))− ∇̂xf(x(t),y(t)),x(t+1)−x(t)−(x̂(t+1) − x(t))〉
+ 〈∇xfµ(x(t),y(t))− ∇̂xf(x(t),y(t)), x̂(t+1) − x(t)〉. (31)
Due to the fact that Eu[∇̂xf(x(t),y(t))] = ∇xfµ(x(t),y(t)), we further have
Eu[〈∇xfµ(x(t),y(t))− ∇̂xf(x(t),y(t)), x̂(t+1) − x(t)〉] = 0. (32)
Finally, we also have
〈∇xfµ(x(t),y(t))− ∇̂xf(x(t),y(t)),x(t+1)−x(t)−(x̂(t+1) − x(t))〉
≤α 2 ‖∇xfµ(x(t),y(t))− ∇̂xf(x(t),y(t))‖2 + 1 2α ‖x(t+1)−x(t)−(x̂(t+1) − x(t))‖2
≤α‖∇xfµ(x(t),y(t))− ∇̂xf(x(t),y(t))‖2 (33) where the first inequality is due to Young’s inequality, the second inequality is due to nonexpansiveness of the projection operator. Thus
Eu[〈∇xfµ(x(t),y(t))− ∇̂xf(x(t),y(t)),x(t+1)−x(t)−(x̂(t+1) − x(t))〉] ≤Eu[α‖∇xfµ(x(t),y(t))− ∇̂xf(x(t),y(t))‖2] ≤ ασ2x (34)
where σ2x := σ 2(Lx, b, q, d) which was defined in (3).
Combining all above, we have E[fµ(x(t+1),y(t))] ≤E[fµ(x(t),y(t))]− ( 1
α − Lx 2
) ‖x(t+1)−x(t) ‖2 + ασ2, (35)
and we request α ≤ 1/Lx, which completes the proof.
Using |fµ,x(x,y)− f(x,y))| ≤ Lxµ 2
2 , we can get
E[f(x(t+1),y(t))]− Lxµ 2
2 ≤ E[fµ(x(t+1),y(t))] ≤ E[f(x(t+1),y(t))] +
Lxµ 2
2 , (36)
so we are able to obtain from (3) E[f(x(t+1),y(t))] ≤ E[f(x(t),y(t))]− ( 1
α − Lx 2
) ‖x(t+1)−x(t) ‖2 + ασ2x + Lxµ2. (37)
Corollary 1.
E 〈 ∇̂f(x(t),y(t−1))−∇fµ(x(t),y(t−1)),y(t)−y(t−1) 〉 ≤ βσ2y (38)
σ2y := σ 2(Ly, b, q, d) which was defined in (3).

heading: Proof:
text: Define
ỹ(t) = projY(y (t) − β∇yfµ(x(t),y(t−1))), (39)
we have
〈∇yfµ(x(t),y(t−1))− ∇̂xf(x(t),y(t−1)),y(t)−y(t−1)〉 =〈∇yfµ(x(t),y(t−1))− ∇̂yf(x(t),y(t−1)),y(t)−y(t−1)−(ỹ(t) − y(t−1))〉
+ 〈∇yfµ(x(t),y(t−1))− ∇̂yf(x(t),y(t−1)), ỹ(t) − y(t−1)〉. (40)
Due to the fact that Eu[∇̂yf(x(t),y(t−1))] = ∇yfµ(x(t),y(t−1)), we further have
Eu[〈∇yfµ(x(t),y(t−1))− ∇̂yf(x(t),y(t−1)), ỹ(t) − y(t−1)〉] = 0. (41)
Finally, we also have
Eu[〈∇yfµ(x(t),y(t−1))− ∇̂yf(x(t),y(t−1)),y(t)−y(t−1)−(ỹ(t) − y(t−1))〉]
≤Eu[ β
2 ‖〈∇yfµ(x(t),y(t−1))− ∇̂yf(x(t),y(t−1))‖2 +
1
2β ‖y(t)−y(t−1)−(ỹ(t) − y(t−1))‖2]
≤Eu[β‖∇yfµ(x(t),y(t−1))− ∇̂yf(x(t),y(t−1))‖2] ≤ βσ2y (42)
where σ2y := σ 2(Ly, b, q, d) which was defined in (3).
Next, before showing the proof of Lemma 3, we need the following lemma to show the recurrence of the size of the successive difference between two iterations. Lemma 5. Under assumption 1, assume iterates x(t),y(t) generated by algorithm 1. When f(x(t),y) is white-box, we have
2 β2γ E‖y(t+1)−y(t) ‖2 − 2 β2γ E‖y(t)−y(t−1) ‖2 ≤ 2L
2 x
βγ2 E‖x(t+1)−x(t) ‖2
+ 2
β E‖y(t+1)−y(t) ‖2 −
( 4
β − 2L2y γ
) E‖y(t)−y(t−1) ‖2. (43)
Proof: from the optimality condition of y-subproblem (24) at iteration t and t − 1, we have the following two inequalities:
−〈∇yf(x(t+1),y(t))− 1
β (y(t+1)−y(t)),y(t+1)−y(t)〉 ≤0, (44)
〈∇yf(x(t),y(t−1))− 1
β (y(t)−y(t−1)),y(t+1)−y(t)〉 ≤0. (45)
Adding the above inequalities, we can get
1 β 〈v(t+1),y(t+1)−y(t)〉 ≤
〈 ∇yf(x(t+1),y(t))−∇yf(x(t),y(t)),y(t+1)−y(t) 〉 + 〈 ∇yf(x(t),y(t))−∇yf(x(t),y(t−1)),y(t+1)−y(t) 〉 (46)
where v(t+1) = y(t+1)−y(t)−(y(t)−y(t−1)). According to the quadrilateral indentity, we know〈
v(t+1),y(t+1)−y(t) 〉 = 1
2
( ‖y(t+1)−y(t) ‖2 + ‖v(t+1) ‖2 − ‖y(t)−y(t−1) ‖2 ) . (47)
Based on the definition of v(t+1), we substituting (47) into (46), which gives
1 2β ‖y(t+1)−y(t) ‖2 ≤ 1 2β ‖y(t)−y(t−1) ‖2 − 1 2β ‖v(t+1) ‖2
+ 〈 ∇yf(x(t+1),y(t))−∇yf(x(t),y(t)),y(t+1)−y(t) 〉 + 〈 ∇yf(x(t),y(t))−∇yf(x(t),y(t−1)),y(t+1)−y(t) 〉 (48)
(a) ≤ 1 2β ‖y(t)−y(t−1) ‖2 +
〈 ∇yf(x(t+1),y(t))−∇yf(x(t),y(t)),y(t+1)−y(t) 〉 + βL2y
2 ‖y(t)−y(t−1) ‖2 − γ‖y(t)−y(t−1) ‖2
(b) ≤ 1 2β ‖y(t)−y(t−1) ‖2 + γ 2 ‖y(t+1)−y(t) ‖2
+ L2x 2γ ‖x(t+1)−x(t) ‖2 − (γ − βL2y 2 )‖y(t)−y(t−1) ‖2 (49)
where in (a) we use the strong concavity of function f(x,y) in y (with parameter γ > 0) and Young’s inequality, i.e.,
〈∇yf(x(t),y(t))−∇yf(x(t),y(t−1)),y(t+1)−y(t)〉 =〈∇yf(x(t),y(t))−∇yf(x(t),y(t−1)),v(t+1) +y(t)−y(t−1)〉
≤ βL2y
2 ‖y(t)−y(t−1) ‖2 + 1 2β ‖v(t+1) ‖2 − γ‖y(t)−y(t−1) ‖2 (50)
and in (b) we apply the Young’s inequality, i.e.,〈 ∇yf(x(t+1),y(t))−∇yf(x(t),y(t)),y(t+1)−y(t) 〉 ≤ L 2 x
2γ ‖x(t+1)−x(t) ‖2+γ 2 ‖y(t+1)−y(t) ‖2.
(51) Therefore, we have
1 2β ‖y(t+1)−y(t) ‖2 ≤ 1 2β ‖y(t)−y(t−1) ‖2 + L
2 x
2γ ‖x(t+1)−x(t) ‖2
+ γ
2 ‖y(t+1)−y(t) ‖2 −
( γ −
βL2y 2
) ‖y(t)−y(t−1) ‖2, (52)
which implies 2
β2γ ‖y(t+1)−y(t) ‖2 ≤ 2 β2γ ‖y(t)−y(t−1) ‖2 + 2L
2 x
βγ2 ‖x(t+1)−x(t) ‖2
+ 2
β ‖y(t+1)−y(t) ‖2 −
( 4
β − 2L2y γ
) ‖y(t)−y(t−1) ‖2. (53)
By taking the expectation on both sides of (53), we can get the results of Lemma 5.
Lemma 5 basically gives the recursion of ‖∆(t)y ‖2. It can be observed that term (4/β−2L2y/γ)‖∆ (t) y ‖ provides the descent of the recursion when β is small enough, which will take an important role in the proof of Lemma 3 when we quantify the descent in maximization.
Then, we can quantify the descent of the objective value by the following descent lemma.

heading: A.3.2 PROOF OF LEMMA 3
text: Proof: let f ′(x(t+1),y(t+1)) = f(x(t+1),y(t+1))−1(y(t+1)) and 1(y) denote the indicator function with respect to the constraint of y. From the optimality condition of sub-problem y in (23), we have
∇yf(x(t+1),y(t))− 1
β (y(t+1)−y(t))− ξ(t+1) = 0 (54)
where ξ(t) denote the subgradient of 1(y(t)). Since function f ′(x,y) is concave with respect to y, we have f ′(x(t+1),y(t+1))− f ′(x(t+1),y(t)) ≤ 〈∇yf(x(t+1),y(t)),y(t+1)−y(t)〉 − 〈ξ(t),y(t+1)−y(t)〉
(a) =
1 β ‖y(t+1)−y(t) ‖2 − 〈ξ(t) − ξ(t+1),y(t+1)−y(t)〉
= 1
β ‖y(t+1)−y(t) ‖2 +
〈 ∇yf(x(t+1),y(t))−∇yf(x(t),y(t−1)),y(t+1)−y(t) 〉 − 1 β 〈 v(t+1),y(t+1)−y(t) 〉 (55)
where in (a) we use ξ(t+1) = ∇yf(x(t+1),y(t))− 1β (y (t+1)−y(t)) . The last two terms of (55) is the same as the RHS of (46). We can apply the similar steps from (48) to (49). To be more specific, the derivations are shown as follows: First, we know
f ′(x(t+1),y(t+1))− f ′(x(t+1),y(t)) ≤ 1 β ‖y(t+1)−y(t) ‖2
+ 〈 ∇yf(x(t+1),y(t))−∇yf(x(t),y(t−1)),y(t+1)−y(t) 〉 − 1 β 〈 v(t+1),y(t+1)−y(t) 〉 . (56)
Then, we move term 1/β〈v(t+1),y(t+1)−y(t)〉 to RHS of (55) and have f(x(t+1),y(t+1))− f(x(t+1),y(t))
≤ 1 2β ‖y(t+1)−y(t) ‖2 + 1 2β ‖y(t)−y(t−1) ‖2 − 1 2β ‖v(t+1) ‖2
+ 〈 ∇yf(x(t+1),y(t))−∇yf(x(t),y(t)),y(t+1)−y(t) 〉 + 〈 ∇yf(x(t),y(t))−∇yf(x(t),y(t−1)),y(t+1)−y(t)
〉 ≤ 1
2β ‖y(t+1)−y(t) ‖2 +
〈 ∇yf(x(t+1),y(t))−∇yf(x(t),y(t)),y(t+1)−y(t) 〉 + βL2y
2 ‖y(t)−y(t−1) ‖2 − γ‖y(t)−y(t−1) ‖2
(a) ≤ 1 β ‖y(t+1)−y(t) ‖2 + 1 2β ‖y(t)−y(t−1) ‖2
+ βL2x
2 ‖x(t+1)−x(t) ‖2 − (γ − βL2y 2 )‖y(t)−y(t−1) ‖2 (57)
where in (a) we use
〈∇yf(x(t+1),y(t))−∇yf(x(t),y(t))〉 ≤ βL2x 2 ‖x(t+1)−x(t) ‖2 + 1 2β ‖y(t+1)−y(t) ‖2 (58)
which is different from (51); also y(t),y(t+1) ∈ Y so have f ′(x(t+1),y(t+1)) = f(x(t+1),y(t+1)) and f ′(x(t+1),y(t)) = f(x(t+1),y(t)).
Combing (53), we have
f(x(t+1),y(t+1)) +
( 2
β2γ +
1
2β
) ‖y(t+1)−y(t) ‖2 − 4 ( 1
β − L2y 2γ
) ‖y(t+1)−y(t) ‖2
≤f(x(t+1),y(t)) + ( 2
β2γ +
1
2β
) ‖y(t)−y(t−1) ‖2 − 4 ( 1
β − L2y 2γ
) ‖y(t)−y(t−1) ‖2
−
( 1
2β − 2L2y γ
) ‖y(t+1)−y(t) ‖2 + ( 2L2x γ2β + βL2x 2 ) ‖x(t+1)−x(t) ‖2. (59)
By taking the expectation on both sides of (53), we can get the results of Lemma 3.
Next, we use the following lemma to show the descent of the objective value after solving xsubproblem by (4).

heading: A.3.3 PROOF OF THEOREM 1
text: Proof:
From Lemma 3, we know E[f(x(t+1),y(t+1))] + ( 2
β2γ +
1
2β
) E[‖y(t+1)−y(t) ‖2]
− 4
( 1
β − L2y 2γ
) E[‖y(t+1)−y(t) ‖2] ≤ E[f(x(t+1),y(t))]
+
( 2
β2γ +
1
2β
) E[‖y(t)−y(t−1) ‖2]− 4 ( 1
β − L2y 2γ
) E[‖y(t)−y(t−1) ‖2]
−
( 1
2β − 2L2y γ
) E[‖y(t+1)−y(t) ‖2] + ( 2L2x γ2β + βL2x 2 ) E[‖x(t+1)−x(t) ‖2]. (60)
Combining Lemma 2, we have E[f(x(t+1),y(t+1))] + ( 2
β2γ +
1
2β
) E [ ‖y(t+1)−y(t) ‖2 ] − 4 ( 1
β − L2y 2γ
) E [ ‖y(t+1)−y(t) ‖2 ] ≤ E[f(x(t),y(t))] + ( 2
β2γ +
1
2β
) E [ ‖y(t)−y(t−1) ‖2 ] − 4 ( 1
β − L2y 2γ
) E [ ‖y(t)−y(t−1) ‖2 ] − ( 1
2β − 2L2y γ ) ︸ ︷︷ ︸
c1
E [ ‖y(t+1)−y(t) ‖2 ]
− ( 1 α − ( Lx 2 + 2L2x γ2β + βL2x 2 )) ︸ ︷︷ ︸
c2
E [ ‖x(t+1)−x(t) ‖2 ] + ασ2x + Lxµ 2. (61)
If β < γ
4L2y and α < 1 Lx 2 + 2L2x γ2β + βL2x 2 , (62)
then we have that there exist positive constants c1 and c2 such that
P(x(t+1),y(t+1),∆(t+1)y )− P(x(t),y(t),∆(t)y ) ≤− c1E [ ‖y(t+1)−y(t) ‖2 ] − c2E [ ‖x(t+1)−x(t) ‖2 ] + ασ2x + Lxµ 2
≤− ζ ( E [ ‖y(t+1)−y(t) ‖2 ] + E [ ‖x(t+1)−x(t) ‖2 ]) + ασ2x + Lxµ 2 (63)
where ζ = min{c1, c2}. From (6), we can have
‖G(x(t),y(t))‖
≤ 1 α ‖x(t+1)−x(t) ‖+ 1 α ‖x(t+1)−projX (x(t)−α∇xf(x(t),y(t)))‖+ 1 β ‖y(t+1)−y(t) ‖
+ 1
β ‖y(t+1)−projY(y(t) +β∇yf(x(t),y(t))‖
(a) ≤ 1 α ‖x(t+1)−x(t) ‖
+ 1
α ‖projX (x(t+1)−α(∇xf(x(t),y(t)) +
1 α (x(t+1)−x(t)))− projX (x(t)−α∇xf(x(t),y(t)))‖
+ 1
β ‖y(t+1)−y(t) ‖
+ 1
β ‖projY(y(t+1) +β(∇yf(x(t+1),y(t))−
1 β (y(t+1)−y(t)))− projY(y(t) +β∇yf(x(t),y(t)))‖
(b) ≤ 3 α ‖x(t+1)−x(t) ‖+ ‖∇yf(x(t+1),y(t)))−∇yf(x(t),y(t)))‖+ 3 β ‖y(t+1)−y(t) ‖
(c) ≤ ( 3
α + Lx
) ‖x(t+1)−x(t) ‖+ 3
β ‖y(t+1)−y(t) ‖
where in (a) we use x(t+1) = projX (x (t+1)−α∇f(x(t+1),y(t))− (x(t+1)−x(t))); in (b) we use nonexpansiveness of the projection operator; in (c) we apply the Lipschitz continuous of function f(x,y) with respect to x and y under assumption A2. Therefore, we can know that there exist a constant c = max{Lx + 3α , 3 β } such that
‖G(x(t),y(t))‖2 ≤ c ( ‖x(t+1)−x(t) ‖2 + ‖y(t+1)−y(t) ‖2 ) . (64)
After applying the telescope sum on (63) and taking expectation over (64), we have
1
T T∑ t=1 E‖G(x(t),y(t))‖2 ≤ c ζ ( P1 − PT+1 T + ασ2x + Lxµ 2 ) . (65)
Recall from A1 that f ≥ f∗ and Y is bounded with diameter R, therefore, Pt given by (8) yields
Pt ≥ f∗ +
( min{4 + 4β2L2y − 7βγ, 0}
2β2γ
) R2, ∀t. (66)
And let (x(r),y(r)) be uniformly and randomly picked from {(x(t),y(t))}Tt=1, based on (65) and (66), we obtain
Er[E‖G(x(r),y(r))‖2] = 1
T T∑ t=1 E‖G(x(t),y(t))‖2 ≤ c ζ ( P1 − f∗ − νR2 T + ασ2x + Lxµ 2 ) ,
(67)
where recall that ζ = min{c1, c2}, c = max{Lx + 3α , 3 β } and ν = min{4+4β2L2y−7βγ,0} 2β2γ .
The proof is now complete.

heading: A.4 CONVERGENCE ANALYSIS OF ZO-MIN-MAX BY PERFORMING ZO-PGA
text: Before showing the proof of Lemma 4, we first give the following lemma regarding to recursion of the difference between two successive iterates of variable y.
Lemma 6. Under assumption 1, assume iterates x(t),y(t) generated by algorithm 1. When function f(x(t),y) is black-box, we have
2 β2γ E‖y(t+1)−y(t) ‖2 ≤ 2 β2γ E‖y(t)−y(t−1) ‖2 + 2 β E‖y(t+1)−y(t) ‖2
+ 6L2y βγ2 E‖x(t+1)−x(t) ‖2 −
( 4
β −
6L2y + 4
γ
) E‖y(t)−y(t−1) ‖2
+ 4σ2y βγ
( 3
γ + 4β ) + µ2d2L2y β2γ . (68)
From the optimality condition of y-subproblem in (23) at iteration t and t− 1, we have
− 〈 ∇̂yf(x(t+1),y(t))− 1
β (y(t+1)−y(t)),y(t+1)−y(t) 〉 ≤0, (69)〈
∇̂yf(x(t),y(t−1))− 1
β (y(t)−y(t−1)),y(t+1)−y(t)
〉 ≤0. (70)
Adding the above inequalities and applying the definition of v(t+1), we can get
1 β 〈v(t+1),y(t+1)−y(t)〉 ≤
〈 ∇̂yf(x(t+1),y(t))− ∇̂yf(x(t),y(t)),y(t+1)−y(t) 〉 ︸ ︷︷ ︸
I + 〈 ∇̂yf(x(t),y(t))− ∇̂yf(x(t),y(t−1)),y(t+1)−y(t) 〉 ︸ ︷︷ ︸
II
. (71)
Next, we will bound E[I] and E[II] separably as follows.
First, we give an upper bound of E[I] as the following,
E 〈 ∇̂yf(x(t+1),y(t))− ∇̂yf(x(t),y(t)),y(t+1)−y(t) 〉 ≤ 3
2γ E‖∇̂yf(x(t+1),y(t))−∇yfµ,y(x(t+1),y(t))‖2 +
γ 6 E‖y(t+1)−y(t) ‖2
+ 3
2γ E‖∇yfµ,y(x(t+1),y(t))−∇yfµ,y(x(t),y(t))‖2 +
γ 6 E‖y(t+1)−y(t) ‖2
+ 3
2γ E‖∇yfµ,y(x(t),y(t))− ∇̂fy(x(t),y(t))‖2 +
γ 6 E‖y(t+1)−y(t) ‖2
≤ 3σ2y γ + 3L2x 2γ E‖x(t+1)−x(t) ‖2 + γ 2 E‖y(t+1)−y(t) ‖2 (72)
where Lemma 1 is used.
Second, we need to give an upper bound of E[II] as follows:
〈∇̂f(x(t),y(t))− ∇̂f(x(t),y(t−1)),y(t+1)−y(t)〉 =〈∇̂f(x(t),y(t))− ∇̂f(x(t),y(t−1)),v(t+1) +y(t)−y(t−1)〉
= 〈 ∇f(x(t),y(t))−∇f(x(t),y(t−1)),y(t)−y(t−1) 〉 + 〈 ∇fµ,y(x(t),y(t))−∇f(x(t),y(t)),y(t)−y(t−1)
〉 + 〈 ∇̂f(x(t),y(t))−∇fµ,y(x(t),y(t)),y(t)−y(t−1)
〉 − 〈 ∇fµ,y(x(t),y(t−1))−∇f(x(t),y(t−1)),y(t)−y(t−1)
〉 − 〈 ∇̂f(x(t),y(t−1))−∇fµ,y(x(t),y(t−1)),y(t)−y(t−1)
〉 + 〈∇̂f(x(t),y(t))− ∇̂f(x(t),y(t−1)),v(t+1)〉.
Next, we take expectation on both sides of the above equality and obtain
E〈∇̂f(x(t),y(t))− ∇̂f(x(t),y(t−1)),y(t+1)−y(t)〉 (a) ≤ ( 3βL2y
2 + β
) ‖y(t)−y(t−1) ‖2 + 1
2β ‖v(t+1) ‖2 − γ‖y(t)−y(t−1) ‖2
+ µ2d2L2y
4β + 4βσ2y (73)
where in (a) we use the fact that 1) γ-strong concavity of f with respect to y:〈 ∇f(x(t),y(t))−∇f(x(t),y(t−1)),y(t)−y(t−1) 〉 ≤ −γ‖y(t)−y(t−1) ‖2; (74)
and the facts that 2) smoothing property (26) and Young’s inequality
E 〈 ∇fµ,y(x(t),y(t))−∇f(x(t),y(t)),y(t)−y(t−1) 〉 ≤ µ2d2L2y
8β + β 2 ‖y(t)−y(t−1) ‖2; (75)
and the fact that 3) the ZO estimator is unbiased according to Lemma 1 E 〈 ∇̂f(x(t),y(t))−∇fµ,y(x(t),y(t)),y(t)−y(t−1) 〉 = 0; (76)
and E 〈 ∇fµ,y(x(t),y(t−1))−∇f(x(t),y(t−1)),y(t)−y(t−1) 〉 ≤ µ2d2L2y
8β + β 2 ‖y(t)−y(t−1) ‖2;
(77) and from Corollary 1 we have
E 〈 ∇̂f(x(t),y(t−1))−∇fµ,y(x(t),y(t−1)),y(t)−y(t−1) 〉 ≤ βσ2y; (78)
and
E〈∇̂f(x(t),y(t))− ∇̂f(x(t),y(t−1)),v(t+1)〉
≤3β 2 E‖∇fµ,y(x(t),y(t))− ∇̂f(x(t),y(t))‖2 + 1 6β ‖v(t+1) ‖2
+ 3β
2 E‖∇fµ,y(x(t),y(t))−∇fµ,y(x(t),y(t−1))‖2 +
1
6β ‖v(t+1) ‖2
+ 3β
2 E‖∇fµ,y(x(t),y(t−1))− ∇̂f(x(t),y(t−1))‖2 +
1
6β ‖v(t+1) ‖2
≤3βσ2y + 1
2β ‖v(t+1) ‖2 + 3βL2y 2 ‖y(t)−y(t−1) ‖2. (79)
Then, from (71), we can have
1 2β E‖y(t+1)−y(t) ‖2 ≤ 1 2β E‖y(t)−y(t−1) ‖2 − 1 2β E‖v(t+1) ‖2
+ 3σ2y γ + 3L2x 2γ E‖x(t+1)−x(t) ‖2 + γ 2 E‖y(t+1)−y(t) ‖2
+ 〈 ∇̂f(x(t),y(t))− ∇̂f(x(t),y(t−1)),y(t+1)−y(t) 〉 ≤ 1
2β E‖y(t)−y(t−1) ‖2 + γ 2 E‖y(t+1)−y(t) ‖2
+ 3L2y 2γ E‖x(t+1)−x(t) ‖2 −
( γ − ( 3βL2y
2 + β
)) E‖y(t)−y(t−1) ‖2
+ 3σ2y γ + 4βσ2y + µ2d2L2y 4β , (80)
which implies
2 β2γ E‖y(t+1)−y(t) ‖2 ≤ 2 β2γ E‖y(t)−y(t−1) ‖2 + 2 β E‖y(t+1)−y(t) ‖2
+ 6L2y βγ2 E‖x(t+1)−x(t) ‖2 −
( 4
β −
6L2y + 4
γ
) E‖y(t)−y(t−1) ‖2
+ 4σ2y βγ
( 3
γ + 4β ) + µ2d2L2y β2γ . (81)

heading: A.4.1 PROOF OF LEMMA 4
text: Proof: Similarly as A.3.2, let f ′(x(t+1),y(t+1)) = f(x(t+1),y(t+1))− 1(y(t+1)), 1(·) denotes the indicator function and ξ(t) denote the subgradient of 1(y(t)). Since function f ′(x,y) is concave with respect to y, we have
f ′(x(t+1),y(t+1))− f ′(x(t+1),y(t)) ≤ 〈∇f(x(t+1),y(t)),y(t+1)−y(t)〉 − 〈ξ(t),y(t+1)−y(t)〉 (a) = 1
β ‖y(t+1)−y(t) ‖2 − 〈ξ(t) − ξ(t+1),y(t+1)−y(t)〉
= 1
β ‖y(t+1)−y(t) ‖2 +
〈 ∇̂f(x(t+1),y(t))− ∇̂f(x(t),y(t−1)),y(t+1)−y(t) 〉 − 1 β 〈 v(t+1),y(t+1)−y(t) 〉 (82)
where in (a) we use ξ(t+1) = ∇̂f(x(t+1),y(t))− 1β (y (t+1)−y(t)). Then, we have
Ef(x(t+1),y(t+1))− Ef(x(t+1),y(t)) + 1 β
〈 v(t+1),y(t+1)−y(t) 〉 ≤ 1 β ‖y(t+1)−y(t) ‖2 + 〈 ∇̂f(x(t+1),y(t))− ∇̂f(x(t),y(t−1)),y(t+1)−y(t) 〉 .
Applying the steps from (73) to (80), we can have
Ef(x(t+1),y(t+1))− Ef(x(t+1),y(t))
≤ 1 β E‖y(t+1)−y(t) ‖2 + 1 2β E‖y(t)−y(t−1) ‖2 −
( γ − ( 3βL2y
2 + β
)) ‖y(t)−y(t−1) ‖2
+ 3βL2x
2 E‖x(t+1)−x(t) ‖2 + 7βσ2y + µ2d2L2y 4β
(83)
where we use
E 〈 ∇̂yf(x(t+1),y(t))− ∇̂yf(x(t),y(t)),y(t+1)−y(t) 〉 ≤3βσ2y +
3βL2x 2 E‖x(t+1)−x(t) ‖2 + 1 2β E‖y(t+1)−y(t) ‖2. (84)
Combing (81), we have
Ef(x(t+1),y(t+1)) + ( 2
β2γ +
1
2β
) E‖y(t+1)−y(t) ‖2 − ( 4
β −
6L2y + 4
γ
) E‖y(t+1)−y(t) ‖2
≤Ef(x(t+1),y(t)) + ( 2
β2γ +
1
2β
) E‖y(t)−y(t−1) ‖2 − ( 4
β −
6L2y + 4
γ
) E‖y(t)−y(t−1) ‖2
−
( 1
2β −
6L2y + 4
γ
) E‖y(t+1)−y(t) ‖2 + ( 6L2x γ2β + 3βL2x 2 ) E‖x(t+1)−x(t) ‖2.
+ µ2d2L2y β
( 1
4 +
1
βγ
) + ( 7β + 4
βγ
( 3
γ + 7β
)) σ2y. (85)

heading: A.4.2 PROOF OF THEOREM 2
text: Proof: From (37), we know the “descent” of the minimization step, i.e., the changes from P ′(x(t),y(t),∆(t)y ) to P ′(x(t+1),y(t),∆(t)y ). Combining the “descent” of the maximization step by Lemma 4 shown in (85), we can obtain the following:
P ′(x(t+1),y(t+1),∆(t+1)y )
≤P ′(x(t),y(t),∆(t)y )−
( 1
2β −
6L2y + 4
γ ) ︸ ︷︷ ︸
a1
E [ ‖y(t+1)−y(t) ‖2 ] (86)
− ( 1 α − ( Lx 2 + 6L2x γ2β + 3βL2x 2 )) ︸ ︷︷ ︸
a2
E [ ‖x(t+1)−x(t) ‖2 ]
+ µ2 ( Lx +
d2L2y β
( 1
4 +
1
βγ )) ︸ ︷︷ ︸
b1
+ασ2x +
( 7β + 4
βγ
( 3
γ + 4β )) ︸ ︷︷ ︸
b2
σ2y.
When β, α satisfy the following conditions:
β < γ
4(3L2y + 2) , and α < 1 Lx 2 + 6L2x γ2β + 3βL2x 2 , (87)
we can conclude that there exist b1, b2 > 0 such that
P ′(x(t+1),y(t+1),∆(t+1)y ) ≤P ′(x(t),y(t),∆(t)y )− a1E [ ‖y(t+1)−y(t) ‖2 ] − a2 [ ‖x(t+1)−x(t) ‖2 ] + b1µ 2 + ασ2x + b2σ 2 y
≤− ζ ′E [ ‖y(t+1)−y(t) ‖2 + ‖x(t+1)−x(t) ‖2 ] + b1µ 2 + ασ2x + b2σ 2 (88)
where ζ ′ = min{a1, a2}.
From (6), we can have
E‖G(x(t),y(t))‖
≤ 1 α E‖x(t+1)−x(t) ‖+ 1 α E‖x(t+1)−projX (x(t)−α∇xf(x(t),y(t)))‖
+ 1 β E‖y(t+1)−y(t) ‖+ 1 β E‖y(t+1)−projY(y(t) +β∇yf(x(t),y(t))‖
(a) ≤ 1 α E‖x(t+1)−x(t) ‖+ 1 β E‖y(t+1)−y(t) ‖
+ 1
α E‖projX (x(t+1)−α(∇̂xf(x(t),y(t)) +
1 α (x(t+1)−x(t)))− projX (x(t)−α∇xf(x(t),y(t)))‖
+ 1
β E‖projY(y(t+1) +β(∇̂yf(x(t+1),y(t))−
1 β (y(t+1)−y(t)))− projY(y(t) +β∇yf(x(t),y(t)))‖
(b) ≤ 3 α E‖x(t+1)−x(t) ‖+ E‖∇̂xf(x(t),y(t)))−∇xf(x(t),y(t)))‖
+ 3
β E‖y(t+1)−y(t) ‖+ E‖∇̂yf(x(t+1),y(t))−∇yf(x(t),y(t))‖
≤ 3 α E‖x(t+1)−x(t) ‖+ E‖∇̂xf(x(t),y(t)))−∇xfµ,y(x(t),y(t)))‖
+ E‖∇xfµ,y(x(t),y(t)))−∇xf(x(t),y(t)))‖
+ 3
β E‖y(t+1)−y(t) ‖+ E‖∇̂yf(x(t+1),y(t))−∇yfµ,y(x(t+1),y(t))‖
+ E‖∇yfµ,y(x(t+1),y(t))−∇yfµ,y(x(t),y(t))‖ + E‖∇yfµ,y(x(t),y(t))−∇yf(x(t),y(t))‖
(c) ≤ ( 3
α + Lx
) E‖x(t+1)−x(t) ‖+ 3
β E‖y(t+1)−y(t) ‖+ 2σ2y + µ2d2L2y
where in (a) we use the optimality condition of x(t)-subproblem; in (b) we use nonexpansiveness of the projection operator; in (c) we apply the Lipschitz continuous of function f(x,y) under assumption A2.
Therefore, we can know that E [ ‖G(x(t),y(t))‖2 ] ≤ c ( ‖x(t+1)−x(t) ‖2 + ‖y(t+1)−y(t) ‖2 ) + 2σ2y + µ 2d2L2y. (89)
After applying the telescope sum on (88) and taking expectation over (89), we have
1
T T∑ t=1 E [ ‖G(x(t),y(t))‖2 ] ≤ c ζ ′ P1 − PT+1 T + cb1 ζ ′ µ2 + cασ2x ζ ′ + cb2 ζ ′ σ2y + 2σ 2 y + µ 2d2L2y. (90)
Recall from A1 that f ≥ f∗ and Y is bounded with diameter R, therefore, Pt given by (11) yields
Pt ≥ f∗ +
( min{4 + 4(3L2y + 2)β2 − 7βγ, 0}
β2γ
) R2, ∀t. (91)
And let (x(r),y(r)) be uniformly and randomly picked from {(x(t),y(t))}Tt=1, based on (91) and (90), we obtain
Er [ E [ ‖G(x(r),y(r))‖2 ]] = 1
T T∑ t=1 E [ ‖G(x(t),y(t))‖2 ] ≤ c ζ ′ P1 − f∗ − ν′R2 T + cb1 ζ ′ µ2 + cασ2x ζ ′ + cb2 ζ ′ σ2y + 2σ 2 y + µ 2d2L2y (92)
where recall that ζ ′ = min{a1, a2}, c = max{Lx + 3α , 3 β }, and ν
′ = min{4+4(3L2y+2)β 2−7βγ,0} β2γ .
The proof is now complete.

heading: B TOY EXAMPLE IN BOGUNOVIC ET AL. (2018): ZO-MIN-MAX VERSUS BO
text: We review the example in Bogunovic et al. (2018) as below,
maximize x∈C minimize ‖δ‖2≤0.5 f(x− δ) := −2(x1 − δ1)6 + 12.2(x1 − δ1)5 − 21.2(x1 − δ1)4
−6.2(x1 − δ1) + 6.4(x1 − δ1)3 + 4.7(x1 − δ1)2 − (x2 − δ2)6 +11(x2 − δ2)5 − 43.3(x2 − δ2)4 + 10(x2 − δ2) + 74.8(x2 − δ2)3 −56.9(x2 − δ2)2 + 4.1(x1 − δ1)(x2 − δ2) + 0.1(x1 − δ1)2(x2 − δ2)2 −0.4(x2 − δ2)2(x1 − δ1)− 0.4(x1 − δ1)2(x2 − δ2),
(93)
where x ∈ R2, and C = {x1 ∈ (−0.95, 3.2), x2 ∈ (−0.45, 4.4)}. Problem (93) can be equivalently transformed to the min-max setting consistent with ours
minimize x∈C maximize ‖δ‖2≤0.5 −f(x− δ). (94)
The optimality of solving problem (93) is measured by regret versus iteration t,
Regret(t) = minimize ‖δ‖2≤0.5 f(x∗ − δ)−minimize ‖δ‖2≤0.5 f(x(t) − δ), (95)
where minimize‖δ‖2≤0.5 f(x ∗ − δ) = −4.33 and x∗ = [−0.195, 0.284]T Bogunovic et al. (2018).
In Figure A1, we compare the convergence performance and computation time of ZO-Min-Max with the BO based approach STABLEOPT proposed in Bogunovic et al. (2018). Here we choose the same initial point for both ZO-Min-Max and STABLEOPT. And we set the same number of function queries per iteration for ZO-Min-Max (with q = 1) and STABLEOPT. We recall from (2) that the larger q is, the more queries ZO-Min-Max takes. In our experiments, we present the best achieved regret up to time t and report the average performance of each method over 5 random trials. As we can see, ZO-Min-Max is more stable, with lower regret and less running time. Besides, as q becomes larger, ZO-Min-Max has a faster convergence rate. We remark that BO is slow since learning the accurate GP model and solving the acquisition problem takes intensive computation cost.
0 10 20 30 40 50 Number of iterations
0
20
40
60
80
100
120
Re gr
et
ZO-Min-Max q=1 ZO-Min-Max q=5 ZO-Min-Max q=10 STABLEOPT optimal
0 10 20 30 40 50 Number of iterations
100
101
102
103
104
To ta
l t im e ZO-Min-Max q=1 ZO-Min-Max q=5 ZO-Min-Max q=10 STABLEOPT
(a) (b)
Figure A1: Comparison of ZO-Min-Max against STABLEOPT Bogunovic et al. (2018): a) Convergence performance; b) Computation time (seconds).

heading: C EXPERIMENT SETUP ON POISONING ATTACK
text: In our experiment, we generate a synthetic dataset that contains n = 1000 samples (zi, ti). We randomly draw the feature vector zi ∈ R100 from N (0, I), and determine ti = 1 if 1/(1 + e−(z T i θ ∗+νi)) > 0.5. Here we choose θ∗ = 1 as the ground-truth model parameters, and νi ∈ N (0, 10−3) as random noise. We randomly split the generated dataset into the training dataset Dtr (70%) and the testing dataset Dte (30%). We specify our learning model as the
logistic regression model for binary classification. Thus, the loss function in problem (15) is chosen as Ftr(x,θ;Dtr) := h(x,θ;Dtr,1) + h(0,θ;Dtr,2), where Dtr = Dtr,1 ∪ Dtr,2, Dtr,1 represents the subset of the training dataset that will be poisoned, |Dtr,1|/|Dtr| denotes the poisoning ratio, h(x,θ;D) = −(1/|D|) ∑ (zi,ti)∈D[ti log(h(x,θ; zi)) + (1 − ti) log(1 − h(x,θ; zi))], and h(x,θ; zi) = 1/(1 + e −(ai+x)T θ). In problem (15), we also set = 2 and λ = 10−3. In Algorithm 1, unless specified otherwise we choose the the mini-batch size b = 100, the number of random direction vectors q = 5, the learning rate α = 0.02 and β = 0.05, and the total number of iterations T = 50000. We report the empirical results over 10 independent trials with random initialization.

heading: D ADDITIONAL EXPERIMENT RESULTS
text: In Figure A2, we show how the importance weights w of individual attack losses are learnt during ZOMin-Max (vs. FO-Min-Max). We can see that ZO-Min-Max takes into account different robustness levels of model-class pairs through the design of w.
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 Number of iterations 1e4
0.15
0.20
0.25
0.30
0.35
0.40
W ei
gh ts
ZO-Min-Max, M1C1 ZO-Min-Max, M1C2 ZO-Min-Max, M2C1 ZO-Min-Max, M2C2
FO-Min-Max, M1C1 FO-Min-Max, M1C2 FO-Min-Max, M2C1 FO-Min-Max, M2C2
Figure A2: Convergence of importance weights learnt from ZO-Min-Max vs. FO-Min-Max.
In Figure A3, we contrast the success or failure (marked by blue or red in the plot) of attacking each image using the obtained universal perturbation x with the attacking difficulty (in terms of required iterations for successful adversarial example) of using per-image non-universal PGD attack (Madry et al., 2017b). We observe that the success rate of the ensemble universal attack is around 80% at each model-class pair, where the failed cases (red cross markers) also need a large amount of iterations to succeed at the case of per-image PGD attack. And images that are difficult to attack keep consistent across models; see dash lines to associate the same images between two models in Figure A3.
M1C1 M2C1 M1C2 M2C2 Model-class pairs
100
101
102
103
104
105
Nu m
be r o
f i te
ra tio
ns
failure in ensemble attack success in ensemble attack
Figure A3: Success or failure of our ensemble attack versus successful per-image PGD attack.
In Figure A4, we show the testing accuracy of the poisoned model as the regularization parameter λ varies. We observe that the poisoned model accuracy could be improved as λ increases, e.g., λ = 1.
However, this leads to a decrease in clean model accuracy (below 90% at λ = 1). This implies a robustness-accuracy tradeoff. If λ continues to increase, both the clean and poisoned accuracy will decrease dramatically as the training loss in (15) is less optimized.
10 4 10 2 100 102 Lambda
0.5
0.6
0.7
0.8
0.9
Te st
in g
ac cu
ra cy
ZO-Min-Max FO-Min-Max No Poison
Figure A4: Empirical performance of ZO-Min-Max in design of poisoning attack: Testing accuracy versus regularization parameter λ.

Review summaries:
The paper presents an algorithm for performing min-max optimisation without gradients and analyses its convergence. The algorithm is evaluated for the min-max problems that arise in the context of adversarial attacks. The presented algorithm is a natural application of a zeroth-order gradient estimator and the authors also prove that the algorithm has a sublinear convergence rate (in a specific sense). 

This paper considers zeroth-order method for min-max optimization (ZO-MIN-MAX) in two cases: one-sided black box (for outer minimization) and two-sided black box (for both inner maximization and outer minimization). Convergence analysis is carefully provided to show that ZO-MIN-MAX converges to a neighborhood of stationary points. Then, the authors empirically compare several methods on