Title: MIN-MAX OPTIMIZATION WITHOUT GRADIENTS: CONVERGENCE AND APPLICATIONS TO ADVERSAR-IAL ML

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.

1. INTRODUCTION:

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 

2. RELATED WORK:

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., 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 2 16 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.

3. PROBLEM SETUP:

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

EQUATION

where x and y are optimization variables, f is a differentiable objective function, and X ⊂ R dx and Y ⊂ R dy are compact convex sets. For ease of notation, let d x = d y = 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. 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.

4. ZO-MIN-MAX: A FRAMEWORK FOR BLACK-BOX MIN-MAX OPTIMIZATION:

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) ,

EQUATION

where d is number of variables, I denotes the mini-batch set of b i.i.d. stochastic samples {ξ j } b j=1 , {u i } q i=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. u i as well as the random direction sampling w.r.t. ξ j . It is known from (Gao et al., 2014, Lemma 2 ) that ∇ x h(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) = E v [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 L h Lipschitz continuous gradients and the gradient of

EQUATION

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 ∇ x f (x, y) and ∇ y f (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

EQUATION

)

where t is the iteration index, ∇ x f denotes the ZO gradient estimate of f w.r.t. x, α > 0 is the learning rate at the x-minimization step, and proj X (a) signifies the projection of a onto X , given by the solution to the problem min x∈X xa 2 2 . For two-sided ZO min-max optimization, in addition to (4), our update on y obeys the ZO projected gradient ascent (ZO-PGA)

EQUATION

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: perform PGA using ∇ y f (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.

5: if f (x (t) ,

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 min x∈X h(x) := min y∈Y f (x, y), which requires the algorithm to obtain the solution to min y∈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.

5. CONVERGENCE ANALYSIS:

We begin by elaborating on assumptions and notations used in analyzing the convergence of ZO-Min-Max (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, y 1 ) ≤ f (x, y 2 ) + ∇ y f (x, y 2 ) T (y 1 -y 2 ) -γ 2 y 1 -y 2 2 for all points y 1 , y 2 ∈ Y.

And f is lower bounded by a finite number f * and has bounded gradients ∇ x f (x, y; ξ) ≤ η 2 and ∇ y f (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 exists L

x , L y > 0 such that ∇ x f (x 1 , y)- ∇ x f (x 2 , y) ≤ L x x 1 -x 2 for ∀ x 1 , x 2 ∈ X , and ∇ y f (x 1 , y) -∇ y f (x 2 , y) ≤ L y x 1 -x 2 and ∇ y f (x, y 1 ) -∇ y f (x, y 2 ) ≤ L y y 1 -y 2 for ∀ y 1 , y 2 ∈ 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) ,

EQUATION

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 + ασ 2 x + Lxµ 2 (7)

where ∆

(t)

x := x (t) -x (t-1) , and

σ 2 x := σ 2 (L x , µ, 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 ασ 2

x and L x µ 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

EQUATION

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:

EQUATION

Proof:

See Appendix A.3.2.

It is shown from (9) that when β is small enough, then the term

EQUATION

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/(4L 2 y ) and α ≤ min{1/L x , 1/(L x /2 + 2L 2 x /(γ 2 β) + βL 2 x /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) )} T t=1 is given by

EQUATION

)

where ζ is a constant independent on the parameters µ, b, q, d and T , P t := P(x (t) , y (t) , ∆

y ) given by (8), c = max{L x + 3/α, 3/β}, ν = min{4 + 4β 2 L 2 y -7βγ, 0}/(2β 2 γ), σ 2

x is variance bound of ZO gradient estimate given in (7), and f * , R, γ, L x and L y 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 -νR 2 , thus, it will not make convergence rate worse. Fourth, P 1 is the initial value of the potential function (8). By setting an appropriate learning rate β (e.g., following Remark 2), P 1 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 L y and strongly concave parameter γ. We next provide Remarks 1-3 on Theorem 1.

Remark 1. Recall that ζ = min{c 1 , c 2 } (Appendix B.2.3), where c 1 = 1/(2β) -2L 2 y /γ and c 2 = 1 α -( Lx 2 + 2L 2 x γ 2 β + βL 2 x 2

). Given the fact that L x and L y 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 β ≤ γ 8L 2 y and α ≤ 1/(L x + 4L 2 x γ 2 β + βL 2 x ), it is easy to verify that c 1 ≥ 2L 2 y γ and c 2 ≥ Lx 2 + 2L 2 x γ 2 β + βL 2 x 2 ≥ Lx 2 + 2L 2 x γ . Thus, we obtain that ζ ≥ min{ 2L 2 y γ , 2L 2 x γ + 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

β = γ 8L 2 y and α = 1/(L x + 4L 2 x γ 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 σ 2 x = 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

EQUATION

)

When function f (x, y) is black-box w.r.t. both x and y, we have the following descent w.r.t. y:

EQUATION

where σ 2 y := σ 2 (L y , µ, 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 ∇ y f (x, y) on the potential function (11) . Such an effect is characterized by the terms related to σ 2 y and µ 2 d 2 L 2 y 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(3L 2 y + 2)) and α ≤ min{L x , 1/(L x /2 + 6L 2

x /(γ 2 β) + 3βL 2 x /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) )} T t=1 is given by

E G(x (r) , y (r) ) 2 ≤ c ζ P 1 -f * -ν R 2 T + cα ζ σ 2 x + cb1 ζ + d 2 L 2 y µ 2 + cb2 ζ + 2 σ 2 y ,

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(3L 2 y +2)β 2 -7βγ,0} β 2 γ , b 1 = L x + d 2 L 2 y (4+βγ) 4β 2 γ and b 2 = 7β 2 γ 2 +28βγ+12 βγ 2

, σ 2 x and σ 2 y have been introduced in (7) and (12), and f * , R, γ, L x and L y 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 σ 2 y 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 ).

6. EXPERIMENTS:

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 l i 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

EQUATION

where x and w ∈ R IJ are optimization variables, and w ij 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 | 1 T w = 1, w ≥ 0}, F ij (x; Ω i , l i )

is the attack loss for attacking the set of images at class l i under model j, and λ > 0 is a regularization parameter. We note that {F ij } 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 {F ij } 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 F ij in (13) as the C&W untargeted attack loss (Carlini & Wagner, 2017) ,

EQUATION

where |Ω i | is the cardinality of the set Ω i , g j (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 ZO-Finite-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. F ij 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 = {z i , t i } n

i=1 denote the training dataset, among which n n samples are corrupted by a perturbation vector x, leading to poisoned training data z i + x towards breaking the training process and thus the prediction accuracy. The poisoning attack problem is then formulated as maximize

EQUATION

where x and θ are optimization variables, F tr (x, θ; D 0 ) 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 -f 2 (x, θ). Clearly, if F tr is a convex loss (e.g., logistic regression or linear regression (Jagielski et al., 2018) ), then -f 2 is strongly concave in θ. Since the adversary has no knowledge on the training procedure and data, f 2 (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. 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. Following (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.

7. CONCLUSION:

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.

APPENDIX A DETAILED CONVERGENCE ANALYSIS A.1 TABLE OF PARAMETERS:

In Table A1 , we summarize the problem and algorithmic parameters used in our convergence analysis. 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 ∇ x h µ (x) = E ξ [∇ x h µ (x, ξ)]

Recall that in the finite sum setting when ξ j parameterizes the jth function, the gradient estimator is given by

EQUATION

)

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

EQUATION

)

Now let's go into the proof. First, we have

EQUATION

Further, by definition, given I, ∇ x h(x) is the average of ZO gradient estimates under q i.i.d. random directions, each of which has the mean 1 b j∈I ∇ x f µ (x, ξ j ). Thus for the first term at the right-hand-side (RHS) of the above inequality, we have

E ui,i∈[q]    ∇ x h(x) - 1 b j∈I ∇ x f µ (x, ξ j ) 2 2 I    ≤ 1 q   2d 1 b j∈I ∇ x f (x, ξ j ) 2 + µ 2 L 2 h d 2 2    ≤ 1 q 2dη 2 + µ 2 L 2 h d 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 ∇ x h(x; ξ) 2 ≤ η 2 and thus 1 b j∈I ∇ x f (x, ξ j ) 2 ≤ η 2 .In addition, we have

EQUATION

)

where the second equality is because ξ j are i.i.d. draws from the same distribution as ξ and 19) and ( 20) into ( 18) finishes the proof.

E[∇ x f µ (x, ξ)] = ∇ x h µ (x), the last inequality is because ∇ x f µ (x, ξ) 2 2 ≤ η 2 by assumption. Substituting (

A.3 CONVERGENCE ANALYSIS OF ZO-MIN-MAX BY PERFORMING PGA:

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 (t) , y (t) , x (t-1) , y (t-1) , . . . , x (1) , y (1) } (21)

F (t) = {x

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:

EQUATION

)

EQUATION

)

When f (x, y) is white-box w.r.t. y, (23) becomes

EQUATION

)

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) :

EQUATION

)

EQUATION

)

First, we will show the descent lemma in minimization as follows.

A.3.1 PROOF OF LEMMA 2:

Proof: Since f (x, y) has L x Lipschtiz continuous gradients with respect to x, we have

EQUATION

Recall that

EQUATION

From the optimality condition of x-subproblem (22), we have

EQUATION

)

Here we use the fact that the optimality condition of problem ( 22) at the solution x (t+1) yields ∇ x f (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 ∇ x f µ (x (t) , y (t) )

EQUATION

Then, we can have

EQUATION

Due to the fact that

E u [ ∇ x f (x (t) , y (t) )] = ∇ x f µ (x (t) , y (t)

), we further have

EQUATION

Finally, we also have

EQUATION

where the first inequality is due to Young's inequality, the second inequality is due to nonexpansiveness of the projection operator. Thus

E u [ ∇ x f µ (x (t) , y (t) ) -∇ x f (x (t) , y (t) ), x (t+1) -x (t) -( x (t+1) -x (t) ) ] ≤E u [α ∇ x f µ (x (t) , y (t) ) -∇ x f (x (t) , y (t) ) 2 ] ≤ ασ 2 x (34)

where σ 2

x := σ 2 (L x , b, q, d) which was defined in (3). Combining all above, we have

EQUATION

and we request α ≤ 1/L x , which completes the proof.

EQUATION

so we are able to obtain from ( 3)

EQUATION

)

Corollary 1.

EQUATION

)

σ 2 y := σ 2 (L y , b, q, d) which was defined in (3).

Proof::

Define

EQUATION

we have t) , y (t-1) ) -∇ x f (x (t) , y (t-1) ), y (t) -y (t-1)

∇ y f µ (x (

= ∇ y f µ (x (t) , y (t-1) ) -∇ y f (x (t) , y (t-1) ), y (t) -y (t-1) -( y (t) -y (t-1) )

+ ∇ y f µ (x (t) , y (t-1) ) -∇ y f (x (t) , y (t-1) ), y (t) -y (t-1) .

Due to the fact that E u [ ∇ y f (x (t) , y (t-1) )] = ∇ y f µ (x (t) , y (t-1) ), we further have

EQUATION

Finally, we also have

EQUATION

)

where σ 2 y := σ 2 (L y , 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

EQUATION

)

where in (a) we use

∇ y f (x (t+1) , y (t) ) -∇ y f (x (t) , y (t) ) ≤ βL 2 x 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

EQUATION

)

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).

A.3.3 PROOF OF THEOREM 1:

Proof:

From Lemma 3, we know

EQUATION

Combining Lemma 2, we have

EQUATION

EQUATION

then we have that there exist positive constants c 1 and c 2 such that P(x (t+1) , y (t+1) , ∆ (t+1) y ) -P(x (t) , y (t) ,

EQUATION

where ζ = min{c 1 , c 2 }.

From (6), we can have

G(x (t) , y (t) ) ≤ 1 α x (t+1) -x (t) + 1 α x (t+1) -proj X (x (t) -α∇ x f (x (t) , y (t) )) + 1 β y (t+1) -y (t) + 1 β y (t+1) -proj Y (y (t) +β∇ y f (x (t) , y (t) ) (a) ≤ 1 α x (t+1) -x (t) + 1 α proj X (x (t+1) -α(∇ x f (x (t) , y (t) ) + 1 α (x (t+1) -x (t) )) -proj X (x (t) -α∇ x f (x (t) , y (t) )) + 1 β y (t+1) -y (t) + 1 β proj Y (y (t+1) +β(∇ y f (x (t+1) , y (t) ) - 1 β (y (t+1) -y (t) )) -proj Y (y (t) +β∇ y f (x (t) , y (t) )) (b) ≤ 3 α x (t+1) -x (t) + ∇ y f (x (t+1) , y (t) )) -∇ y f (x (t) , y (t) )) + 3 β y (t+1) -y (t) (c) ≤ 3 α + L x x (t+1) -x (t) + 3 β y (t+1) -y (t)

where in (a) we use x (t+1) = proj X (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{L

EQUATION

)

After applying the telescope sum on (63) and taking expectation over (64), we have

EQUATION

)

Recall from A1 that f ≥ f * and Y is bounded with diameter R, therefore, P t given by (8) yields

EQUATION

And let (x (r) , y (r) ) be uniformly and randomly picked from {(x (t) , y (t) )} T t=1 , based on ( 65) and (66), we obtain

EQUATION

where recall that

ζ = min{c 1 , c 2 }, c = max{L x + 3 α , 3 β } and ν = min{4+4β 2 L 2 y -7βγ,0} 2β 2 γ .

The proof is now complete.

A.4 CONVERGENCE ANALYSIS OF ZO-MIN-MAX BY PERFORMING ZO-PGA:

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

EQUATION

)

From the optimality condition of y-subproblem in ( 23) at iteration t and t -1, we have

EQUATION

EQUATION

Adding the above inequalities and applying the definition of v (t+1) , we can get t+1) , y (t+1) -y (t) ≤ ∇ y f (x (t+1) , y (t) ) -∇ y f (x (t) , y (t) ), y (t+1) -y (t)

EQUATION

EQUATION

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 ∇ y f (x (t+1) , y (t) ) -∇ y f (x (t) , y (t) ), y (t+1) -y (t) ≤ 3 2γ E ∇ y f (x (t+1) , y (t) ) -∇ y f µ,y (x (t+1) , y (t) ) 2 + γ 6 E y (t+1) -y (t) 2 + 3 2γ E ∇ y f µ,y (x (t+1) , y (t) ) -∇ y f µ,y (x (t) , y (t) ) 2 + γ 6 E y (t+1) -y (t) 2 + 3 2γ E ∇ y f µ,y (x (t) , y (t) ) -∇f y (x (t) , y (t) ) 2 + γ 6 E y (t+1) -y (t) 2 ≤ 3σ 2 y γ + 3L 2 x 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

EQUATION

)

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) ≤ µ 2 d 2 L 2 y 8β + β 2 y (t) -y (t-1) 2 ; (75) and the fact that 3) the ZO estimator is unbiased according to Lemma 1 t) , y (t) ) -∇f µ,y (x (t) , y (t) ), y (t) -y (t-1) = 0;

E ∇f (x (

(76) and E ∇f µ,y (x (t) , y (t-1) ) -∇f (x (t) , y (t-1) ), y (t) -y (t-1) ≤

µ 2 d 2 L 2 y 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) ≤ βσ 2 y ;

(78) and

EQUATION

)

Then, from (71), we can have

EQUATION

which implies

EQUATION

A.4.1 PROOF OF LEMMA 4

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

EQUATION

where in (a) we use ξ (t+1) = ∇f (x (t+1) , y (t) ) -1 β (y (t+1) -y (t) ). Then, we have t+1) , y (t) ) -∇f (x (t) , y (t-1) ), y (t+1) -y (t) .

EQUATION

Applying the steps from ( 73) to (80), we can have

EQUATION

where we use

EQUATION

Combing (81), we have

EQUATION

A.4.2 PROOF OF THEOREM 2

Proof: From (37), we know the "descent" of the minimization step, i.e., the changes from P (x (t) , y (t) , ∆

y ) to P (x (t+1) , y (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β - 6L 2 y + 4 γ a1 E y (t+1) -y (t) 2 (86) - 1 α - L x 2 + 6L 2 x γ 2 β + 3βL 2 x 2 a2 E x (t+1) -x (t) 2 + µ 2 L x + d 2 L 2 y β 1 4 + 1 βγ b1 +ασ 2 x + 7β + 4 βγ 3 γ + 4β b2 σ 2 y .

When β, α satisfy the following conditions:

β < γ 4(3L 2 y + 2)

, and α < 1

EQUATION

we can conclude that there exist b 1 , b 2 > 0 such that

EQUATION

where ζ = min{a 1 , a 2 }.

From ( 6), we can have

E G(x (t) , y (t) ) ≤ 1 α E x (t+1) -x (t) + 1 α E x (t+1) -proj X (x (t) -α∇ x f (x (t) , y (t) )) + 1 β E y (t+1) -y (t) + 1 β E y (t+1) -proj Y (y (t) +β∇ y f (x (t) , y (t) ) (a) ≤ 1 α E x (t+1) -x (t) + 1 β E y (t+1) -y (t) + 1 α E proj X (x (t+1) -α( ∇ x f (x (t) , y (t) ) + 1 α (x (t+1) -x (t) )) -proj X (x (t) -α∇ x f (x (t) , y (t) )) + 1 β E proj Y (y (t+1) +β( ∇ y f (x (t+1) , y (t) ) - 1 β (y (t+1) -y (t) )) -proj Y (y (t) +β∇ y f (x (t) , y (t) )) (b) ≤ 3 α E x (t+1) -x (t) + E ∇ x f (x (t) , y (t) )) -∇ x f (x (t) , y (t) )) + 3 β E y (t+1) -y (t) + E ∇ y f (x (t+1) , y (t) ) -∇ y f (x (t) , y (t) ) ≤ 3 α E x (t+1) -x (t) + E ∇ x f (x (t) , y (t) )) -∇ x f µ,y (x (t) , y (t) )) + E ∇ x f µ,y (x (t) , y (t) )) -∇ x f (x (t) , y (t) )) + 3 β E y (t+1) -y (t) + E ∇ y f (x (t+1) , y (t) ) -∇ y f µ,y (x (t+1) , y (t) ) + E ∇ y f µ,y (x (t+1) , y (t) ) -∇ y f µ,y (x (t) , y (t) ) + E ∇ y f µ,y (x (t) , y (t) ) -∇ y f (x (t) , y (t) ) (c) ≤ 3 α + L x E x (t+1) -x (t) + 3 β E y (t+1) -y (t) + 2σ 2 y + µ 2 d 2 L 2 y

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

EQUATION

After applying the telescope sum on (88) and taking expectation over (89), we have

EQUATION

)

Recall from A1 that f ≥ f * and Y is bounded with diameter R, therefore, P t given by (11) yields

EQUATION

And let (x (r) , y (r) ) be uniformly and randomly picked from {(x (t) , y (t) )} T t=1 , based on ( 91) and (90), we obtain

EQUATION

)

where recall that ζ = min{a 1 , a 2 }, c = max{L x + 3 α , 3 β }, and ν = f (x -δ) := -2(x 1 -δ 1 ) 6 + 12.2(x 1 -δ 1 ) 5 -21.2(x 1 -δ 1 ) 4 -6.2(x 1 -δ 1 ) + 6.4(x 1 -δ 1 ) 3 + 4.7(x 1 -δ 1 ) 2 -(x 2 -δ 2 ) 6 +11(x 2 -δ 2 ) 5 -43.3(x 2 -δ 2 ) 4 + 10(x 2 -δ 2 ) + 74.8(x 2 -δ 2 ) 3 -56.9(x 2 -δ 2 ) 2 + 4.1(x 1 -δ 1 )(x 2 -δ 2 ) + 0.1(x 1 -δ 1 ) 2 (x 2 -δ 2 ) 2 -0.4(x 2 -δ 2 ) 2 (x 1 -δ 1 ) -0.4(x 1 -δ 1 ) 2 (x 2 -δ 2 ), 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. 

C EXPERIMENT SETUP ON POISONING ATTACK:

In our experiment, we generate a synthetic dataset that contains n = 1000 samples (z i , t i ).

We randomly draw the feature vector z i ∈ R 100 from N (0, I), and determine t i = 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 D tr (70%) and the testing dataset D te (30%). We specify our learning model as the logistic regression model for binary classification. Thus, the loss function in problem ( 15) is chosen as F tr (x, θ; D tr ) := h(x, θ; D tr,1 ) + h(0, θ; D tr,2 ), where D tr = D tr,1 ∪ D tr,2 , D tr,1 represents the subset of the training dataset that will be poisoned, |D tr,1 |/|D tr | denotes the poisoning ratio, h(x, θ; D) = -(1/|D|) (zi,ti)∈D [t i log(h(x, θ; z i )) + (1 -t i ) log(1 -h(x, θ; z i ))], and h(x, θ; z i ) = 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.

D ADDITIONAL EXPERIMENT RESULTS:

In Figure A2 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 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.

:

Source code will be released.

Figures and Tables:

-Max, M1C2 ZO-Min-Max, M2C1 ZO-Min-Max, M2C2 ZO-Finite-Sum, M1C1 ZO-Finite-Sum, M1C2 ZO-Finite-Sum, M2C1 ZO-Finite-Sum, M2C2

Figure 1: Convergence performance of ZO-Min-Max in design of black-box ensemble attack. a) Stationary gap of ZO-Min-Max vs. FO-Min-Max, b) attack loss of using ZO-Min-Max vs. FO-Min-Max, and c) attack loss of using ZO-Min-Max vs. ZO-Finite-Sum.

Figure 2: Empirical performance of ZO-Min-Max in design of poisoning attack: a) stationary gap versus iterations b) testing accuracy versus iterations (the shaded region represents variance of 10 random trials), and c) testing accuracy versus data poisoning ratio.

Figure 3: Comparison between ZO-Min-Max and STABLEOPT on testing accuracy versus optimization time.

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 Figure2-(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 Figure3, we compare ZO-Min-Max with STABLEOPT(Bogunovic et al., 2018) in terms of testing accuracy versus computation time. Following(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.

min{4+4(3L 2 y +2)β 2 -7βγ,0} β 2 γ .The proof is now complete.B TOY EXAMPLE IN BOGUNOVIC ET AL. (2018): ZO-MIN-MAX VERSUS BOWe review the example inBogunovic et al. (2018) as below,

where x ∈ R 2 , and C = {x 1 ∈ (-0.95, 3.2), x 2 ∈ (-0.45, 4.4)}.Problem (93) can be equivalently transformed to the min-max setting consistent with ours minimize 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] TBogunovic et al. (2018).

Figure A1: Comparison of ZO-Min-Max against STABLEOPT Bogunovic et al. (2018): a) Convergence performance; b) Computation time (seconds).

Figure A2: Convergence of importance weights learnt from ZO-Min-Max vs. FO-Min-Max.

Figure A3: Success or failure of our ensemble attack versus successful per-image PGD attack.

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.

Table content: <table/>

y) is black box w.r.t. y then

Table content: <table><tr><td>6:</td><td>perform ZO-PGA (5)</td></tr><tr><td>7:</td><td>else</td></tr><tr><td>8:</td><td/></tr></table>

Summary of problem and algorithmic parameters and their descriptions.

Table content: <table><tr><td>parameter</td><td>description</td></tr><tr><td>d</td><td># of optimization variables</td></tr><tr><td>b</td><td>mini-batch size</td></tr><tr><td>q</td><td># of random direction vectors used in ZO gradient estimation</td></tr><tr><td>α</td><td>learning rate for ZO-PGD</td></tr><tr><td>β</td><td>learning rate for ZO-PGA</td></tr><tr><td>γ</td><td>strongly concavity parameter of f (x, y) with respect to y</td></tr><tr><td>η</td><td>upper bound on the gradient norm, implying Lipschitz continuity</td></tr><tr><td>L x , L f  *</td><td>lower bound on the function value, implying feasibility</td></tr><tr><td>σ 2 x , σ 2</td><td/></tr></table>

Peer review (iclr2020):
The authors aim to propose new algorithms for min-max optimization problem when the gradients are not available and establish sublinear convergence of the algorithm. I don*t think this paper can be accepted for ICLR for the following reasons: 1. For Setting (a) (One-sided black-box), the theory can be established by the same analysis for ZO optimization by optimizing y. Even by a proximal step for y, the analysis is essentially the same as ZO where an estimation of the gradient for x is conducted. 2. The assumptions A1 and A2 are hardly satisfied in ML applications, where the objective is essentially smooth. The authors should at least analyze the case where a sub/super-gradients is available. 3. Also, for most ML problems we have today, I don*t find many applications where the gradients are not available, and I thus feel that it is not interesting to consider ZO optimizations.