Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
Authors: Sijia Liu
Songtao Lu
Xiangyi Chen
Yao Feng
Kaidi Xu
Abdullah Al-Dujaili
Minyi Hong
Una-May Obelilly
Venue:  (2020)
Keywords: nonconvex optimization
min-max optimization
robust optimization
adversarial attack

Abstract: In this paper, we study the problem of constrained robust (min-max) optimization ina 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.

Under review as a conference paper at ICLR 2020
MIN-MAX OPTIMIZATION WITHOUT GRADIENTS: CONVERGENCE AND APPLICATIONS TO ADVERSAR- IAL ML
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we study the problem of constrained robust (min- unin-max) optimization 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 (7.0) gradient estimator with alternating projected stochastic gradient descent-ascens -ascett method, where the former only requires small number of function queries and the later needs just one-step descent/ascent update. We show that the proposed framework, referred to as (O-Min-Max, has 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-bor -box solvers.
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 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 (Steinhardr et al. 2017 Tran et al. 2018: Jagielski al. 2018). inference time, malicious users can evade detection of multiple models in the form 2018a). Min-max (robust)
of adversarial example attacks (Goodfellow et al. 2014] Liu et al.) 2016
optimization is a natural framework to address adversarial (worst-case) robustness (Madry et al. 2017b Al-Dujaili al. 2018b). It converts a standard minimization problem into 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.c. gradients, to find
approximate robust solutions (Nesterov) 2007 Gidel al.) 2017 Hamedani et al. 2018 Qian et al. 2019 Rafiqqe et al. 2018 (Sanjabi et al.] 2018b] Lu et al. [2199] Nouiehed et al. 2019 Lu 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 tedious compute (Conn 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 adversaries. The extension of min-max optimization from the FO domain to the gradient-free regime is challenging since the solver suffers from uncertainties 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 query-efficien randomized zeroth-order (ZO) gradient estimator with computation-efficient alternating gradient descent-ascent framework, where the former requires a small number of function queries build 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 a powerful and practical tool for generation of black-box adversarial examples

---

Under review as a conference paper at ICLR 2020
to evaluate the adversarial robustness of ML/DL models CCen et al. 2017 y al. 2018 Tu et al. 2018 Tlas 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. alternatives of high-order
2019 Furthermore, ZO optimization provides computationally--fiic..
optimization methods for solving complex MLJDLL tasks, e.g., robust training by leveraging input
gradient or curvature regularization (Finlay & Oberman 2019 Moosavi-Dezzool
et al. 2019) model-
agnostic 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 moodel-agnostic contrastive explanations (Dhurandhar et al. 2019) and escaping saddle
points (Flokas et al. (019). Current studies (Ghadimi & Lan| 2013: Nesterov & Spokoiny] 2015) Duchi et a 2015; Ghadimi et al. 2016 Shamir| 2017; [iu et al. 2019) suggested that ZO methods typically agree with the iteration complexity of FO methods but encounter 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 max black-box optimization problems. (i) We propose scalable and principled framework (ZO-Min-Mas max 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 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 70 gradient estimator, and shows that Z0-Min-Max yields O(1/T + 1/b + d/q) convergence rate, where T is number of iterations, b is mini-batch size, 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
for solving constrained min-
2 RELATED WORK
FO min-max optimization. Gradient- 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 (AI-Dujaili et al. 2018b: Madry et al.) (0)7a). and robust adversarial attack generation (Wang et al., 20T9b). Some of FO methods are motivated by theoretical justifications based on Danskin's 's theorem (Danskin 1966). which implics that the negative of the gradient of the outer minimization problem at inner maximizer is descent direction (Madry let 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 (Sajjaii et al., 2018b) Nouiehed et al. 2019). It was shown in (Lu et al. 2019) that deterministic FO min-max algorithm has O(/TT) convergence rate. In (Qian et al. 2019 Rafique et al. 201 8), stochastic FO min-max methods have also been proposed, which yield the convergence rate in the order of O(L/VT) and (/1/T1/4), respectively. However, these works were restricted to unconstrained optimization at the minimization side. In (Sanjabi et al., (2188)), 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 (1/TT) convergence rate was proved for min-max problems under Polyak- Eojasiewicz 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-man 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..
Source code will be released.
2

---

Under review as a conference paper at ICLR 2020
asymmetric fitness (Jensen 2003 Branke & Rosenbusch 2008 In (Al- (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 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 variables at maximum in SciPy Python library (Jones et al. 2001)
which is even smaller than the size of single ImageNet image. The recent work (Bogunovic et al.
2018) proposed 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 Au-Dujiili ett al. 20) 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 a composition of inner maximization and outer minimization of the objective function f. By black-box, mean that the objective function f is only accessible via point-wise functional evaluations. Mathematically, we have
min max XEX yEy
f(x, y)
where x and y are optimization variables, f is a differentiable objective function, and X' C Rdz and V C Rd are compact convex sets. For ease of notation, let d₂ dy = d. In ( the objective function f could represent either a deterministic loss or stochastic loss f(x, y) = Eg-p [f ; { where & is random variable following the distribution p. In this paper, consider the stochastic variant in
We focus on two black-box scenarios in which gradients (or stochastic gradients under randomly sampled E) of J w.r.t. x or y are not accessed.
(a) One-sided black-box: y( is a white box w.r.t. y but a black box w.r.t. x.
(b) Two-sided black-box: fxx,y) 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 deliherately 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. 20 9a) 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-bor attack setting. By contrast, we provide a solution min-max attack generation under blx ML models. We refer readers to Section for further discussion and demonstration of our framework these problems.
3

---

Under review as a conference paper at ICLR 2020
4 ZO-MIN-MAX: A FRAMEWORK FOR BLACK-BOX MIN-MAX OPTIMIZATION
Our interest is in scalable and theoretically principled framework for black-box min-max problems of the form O To this end, we first introduce a randomized gradient estimator that only requires few number of point-wise function evaluations. Based on that, we then propose ZO alternating projected gradient method to solve ① under both one-sided and two-sided black-box setups.
Randomized gradient estimator. In the ZO setting, we adopt randomized gradient estimator to estimate the gradient of a function with the generic form h(x) Eg Eg[h(x: E)] (Liu et al. 2019
Gao
ct al. 2014).
d[b(x pmi E,) h(x:: 6, u.
<x1(x)=
(2)
by
where d is number of variables, I denotes the mini-batch set of b i.i.d. stochastic samples } {u:)?=1 are q i..dd random direction vectors drawn uniformly from the unit sphere, and μr > 0 a smoothing parameter. We note that the ZO gradient estimator (2) involves randomness from both stochastic sampling w.r.t u, as well as the random direction sampling w.r.t. E,. It is known
from (Gao et al. 2014, Lemma 2) that <x)(x) provides an unbiased estimate of the gradient of the smoothing function of l rather than the true gradient of h. Here the smoothing function of is defined by (x) Ev [h(x + [o)],, 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[]
Lemma 1. Suppose that for all &. h(x; E) has Ln Lipschitz continuous gradients and the gradient of at x E RR., Then E
Mxx; E) is upper bounded as >>x(xx)))1 1²
[xh(x)) = =x))p(x),
2r² 1dn2 + d2 = 0² (L, b
E [[ - (x)1
(3)
9
where the expectation is taken over all randomness.
Proof: See Appendix A.2
In Lemma if we choose μ S 1/vd, then the variance bound is given by 0(1/b + d/q). In our problem setting ( the 70 gradients yx) and /x, y) follow the generic form of (2) by fixing y and letting h-(-) = y( by fixing x and letting h(.) = f(x,)), respectively.
Algorithmic framework. To solve problem ( 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
projx (x (x((-1)-aVxf (x y(t
(4)
where / is the iteration index, Vx denotes the ZO gradient estimate of ʃ w.r.t. x, >> 0 is the learning rate the x-minimization step, and projx (a) signifies the projection of a onto X, given by the solution to the problem minxex ||x all3. For two-sided 70 min-max optimization, in addition to (4), our update on y obeys the 70 projected gradient ascent (ZO-PGA)
y projy (y-t-1) + , (x)), ((,),,()))))
(5)
where 0 is the learning rate at the y-maximization step. The proposed method is named as ZO-Min-Max, see Algorithm
Why estimates gradient rather than distribution of function values? Besides ZO optimization using random gradient estimates, the black-box min-max problem (I) 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 Gaussian process (GP) learnt from the history of function values at queried points. Based on GP, the solution to problem I is then updated by maximizing certain reward function, known as acquisition function. The advantage of BO is
4

---

Under review as a conference paper at ICLR 2020
its mild requirements the setting of black-box problems, e.g., 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[AT] we compare 20-Min-Max with the BO based STABLEOPT algorithm proposed by (Bogunovic et al., (018)) through 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 for details.
Technical challenges in convergence analysis. The convergence analysis of ZO-Min-Max is more challenging than the case of FO min-max max algorithms. Besides the inaccurate estimate of the gradient, the stochasticity of the estimator makes the convergence analysis sufficiently dif- ferent from the FO deterministic case (Lu et al.) 2019; Qian et al. 2019), since the errors in min- imization and maximization are coupled as the algorithm proceeds.
Algorithm 1 10-Mii-Maas solve problem
1: Input: given x()) and y0)),, learning rates and 3, the number of random directions q. and the possible mini-bater size b for stochastic optimization
2: for t = 1.2,..., T do
3: x-step: perform 70-PGD (4
4: y-step:
5: if f(x(") .y) is black box w.r.t. y then
Moreover, the conventioanl analysis of ZO op- timization for single-objective problems cannot
6:
perform ZO-PGA (5)
directly be applied to Z0-Min-Max. Even at the one-sided black-box setting, Z0-Min-Max conducts alternating optimization using one-step ZO-PGD and PGA with respect to x and y re- spectively. This is different from reduced ZO optimization problem with respect to x only by solving problem minxex x h((x) == minyey y(,,,), which requires the algorithm to obtain the solu- tion to minyey f(x y) at given x (when querying hxx) for 70 gradient estimation). However, this process is usually non-trivial or computationally intensive.
7:
else
perform PGA using V (x(() (x(())((())))) ((-11)
8:
ascent direction in 5
9: end if
end for
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-Mer 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 D.
A1: In ( f(x, y) is continuously differenniable, and is strongly concave w.r.t. y with parameter
> O, namely, given x E X. f() < y2) + vy (y: y2) - fly - y2ll² for all points y1.y2 E Y. And ff is lower bounded by a finite number f and has bounded gradients V y; E)ll S 2 and f y: E < n² for stochastic optimization with & ~ p. Here || denotes the & 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 Tony Tyy > 0 such that | S I. X1 X2 || for VxI, X2 E X, and [[V (x1,)) - (x2 S
Vx [x/(xx,
Ly X1 -x2 and | (yf((x)) fxf(x,y2) - Lylly; Y2 for V.I. 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 Nouiched
ct al.
2019 and first-order methods for nonconvex optimization with a single objective function CChen et 2019: Ward et al.) 2019). In A1, the strongly concavity of f 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
5

---

Under review as a conference paper at ICLR 2020
(namely. Lipschitz continuous gradient) is required quantify the descent of the alternating projected stochastic gradient -escent-ascent method. Even for single-objective non-convex optimization, c.g.,
(Chen et al. 2019 Bernstein al. 2018). A2 is needed in analysis. For clarity, also summarize
the problem and a algorithmic parameters used in our convergence analysis in Table AT of Appendix.
We measure the convergence of ZO-Min-Max by the proximal gradient Lu et al. 2016).
2019
Ghadimi
[
(1/a) (x --rroooi -Vxxxx (1/B) (y projy + ].
((x.y)
(6)
where yx is a first-order stationary point of iff |] y) =.
In what follows, we delve into our convergence analysis. First, Lemma shows the descent property of ZODPGD at the x-minimization step in Algorithm[]
Lemma 2. (Descent lemma in minimization) Under AI-A2, let (x((), y()) be sequence generated by Algorithm [
When fxx y) is black-box w.E.t x, then we have following descent property w.r.t. x:
Toe ( ())] S ETS(x") (y0)) - (1 a 2
E[f(x"t),
to0 + Laf
(7)
where A x11 x),-1), and o a² (Liz p. b, q, d) defined in 33.
Proof: See Appendix A.3.1
A.3.I
clear from Lemma that updating x leads to the reduced objective value when choosing a small learning rate a. However, ZO gradient estimation brings in additional errors in terms of
ao² and LnMe² 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; Appendix(A.. A.3
25 in
Convergence rate of ZO-Min-Max by performing PGA. We next investigate the convergence of Z0-Min-Max when FO PGA is used at the y-maximization step (Line 8 of Algorithm[] for solving one-sided black-box optimization problems.
Lemma 3. (Descent lemma in maximization) Under A1-A2, let by Algorithm 7 Nand define the potential function
be a sequence generated
A (0) = [x -00)(x0,,00)) 4 4
-73y
(0 (0)
E A
(8)
2
where 1/) == y(t) - y(t-1), When f(x,y' y) black-box w.r. x and white-box w.r.t. y, then we have the following descent property w.r.t. y:
(+x (4+1) A(41) <P(x (411)
(y())
A
2
122
+ ( ( +
723 2
2 8
(9)
23
γ
Proof: See Appendix A.3.2
is shown from (9) that when 3 is small enough, then the term (1/(23) -
-1 (+1) 2 will
give some descent of the potential function after performing PGA, while the last term in ( 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 Combining Lemma 2 and
Lemma we obtain the convergence rate of Min-Max in Theorem
Theorem 1, Suppose that A1-A2 hold, the sequence x<0,)(()) over T iterations is generated by Algorithm 7 in which learning rates satisfy B < 1/(4L2) and a S min(1/La, 1/(Ln/2 2T2 (7) + 3 312/2)} When f(x, y) is black-box w.r.l. x and white-box w.r.t. y, the convergence rate of 20- under a uniformly and randomly picked (()) from {(x(1) (le(%),(()) y())] is given by
, c cP, - -8" -
T + coo'. clapp
(10)
S
6

---

Under review as a conference paper at ICLR 2020
where Ç is a constant independent on the parameters j.. b, q. d and T, P. == P(x(() y(u) )
given by (8). c = max(Lx Lz + 3/a, 3/3), V = [4 + 4,3 7,37, (2/ o is variance bound of Zo gradient estimate given in (7. and f*, R. 7,. L and Ly have been defined in Al-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 non-trivial lower bound given appropriate learning rates a and | (see Remark that we will show later). Second, the parameter is inversely proportional to a and B. Thus, to guarantee the constant effect of the ratio c/c, is better not to set these learning rates too small; see a specification in Remark 1-2. Third, the parameter v is non non-negative and appears in terms of -vR thus, it will not make convergence rate worse. Fourth, Pi is the initial value of the potential function ( By setting an appropriate learning rate / (e.g., following Remark 2), Pi 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 y. We next provide Remarks 1-3 on Theorem
Remark 1. Recall that minfc1, o2) (Appendix B.2.3), where e = 1/(23) -2L and 222 30 + 2 Given the fact that Lg and Ly are Lipschitz constants and y is the strongly concavity constant, a proper lower bound of Ç thus relies on the choice of the learning rates 41.2 2 siz and a S 1/((1= + 7²B + 3T2,, it easy to verify that e1 2 21 and
02 a (zz
1 - +
a and B. By setting 3
2 2 2 2 2 that ( has a non-trivial lower bound, which will not make the convergence error bound (0) (although the bound has not been optimized over a and (3).
2 1 272 Thus, we obtain that Ç 2 min
21 21 + ). This justifies
7
vacuous
Remark 2. It is not wise to set learning rates a and 3 to extremely small values since is inversely 412
proportional to a and 3. Thus, we typically choose B 81. and a = 11(LLz + 7 + BL2) in Remark I to guarantee the constant effect of c/C.
Remark 3. By setting μ S min(1/vd, 1/VT), we obtain o2 = 0(1/b + d/q) from Lemma and Theorem
1 implies that 70-Min-Max yields O(1/T + 1 1/b + d//)) convergence rate for one-sided black-box optimization. Compared to the FO rate (1/TT) (Lu et al. 2019 Sanjabi et al. 201 Ba), ZO-Min-Max converges only to a neighborhood of stationary points with O(I/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 Z0-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 Obbg) 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-Mar by performing ZO-PGA. We now focus on the convergence analysis of MO-Min- when ZO PGA used at the y-maximization step (Line 6 of Algorithm for two-sided black-box optimization problems.
Lemma 4. (Descent lemma in maxinization) Under AI-A2, let (x(t), y(()) be a sequence generated by Algorithm and define the potential function as
P'(x()) 1,0,,.90 = Eif(x("), ())() + 4(31.3 + 2) - 75 B2
(11)
Bay
When function y(x,y) is black-box w.r.t both x and y, we have the following descent w.r.t. y:
6L3, + 4
P' (x(( ((++1),
,(0+1), ((t1)) < P' (x(())
ElJA
23
72 E A 7-2 + 2837 + 12
6L
33L2
By +
+
+
1 L2g
(12)
3y2
1827
7

---

Under review as a conference paper at ICLR 2020
where og ;= o² (Ly, M4, b. q. given in 33)
Proof: See Appendix A.4.1
4emma is analogous to Lemma by taking into account the effect of 70 gradient estimate fx, y) on the potential function Such an effect is characterized by the terms related to oy and L y in (2].
Theorem 2. Suppose that A1-A2 hold, the sequence (x(11) (y(t))(()) y()) over T iterations is generated by Algorithm in which learning rates satisfy 3 < </((L3 + 2)) and S min 1/(La/2 ( 3 When f(x. y) is black-box w.F.t. both x and y, the convergence rate of ZO-Min-Max under uniformly and randomly picked (x(*), y(") from ((00)) is given by
" (0)) c Pi
-
RRR
Ca 2
( ox Ç
(bh + to
1²
cb2 +2 oz.
T
where Ç' is constant independent on the parameters b, 9. d and T, Pi == ('(x(1), (x(())))r -(l)) A
in HTp. has been defined in TT). V/ min(1++1331 +2,00 13y.00 b Lo + d' (1+ and
8"
4
by 7 of and oy have been introduced in and and f". R. 7 Lo and Ly
3n2 have been defined A1-A2.
Proof: See Appendix A.4.2
Following the similar argument in Remark I of Theorem D one can choose proper learning rates a and obtain valid lower bound on Ç'. However, different from Theorem [ the convergence error shown by Theorem 2 involves an additional error term related to oj and has worse cimension-dependene on the term related to μ²². The latter yields more restricted choice of the smoothing parameter μu: we obtain O(1/ + 1/b + d/q) convergence rate when μ S 1/(dTT).
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., (016) and ResNet-50 (He et al., (016) under ImageNet (Deng et al. 2009). and 2)
design of black-box poisoning attack against 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 20)8a). More formally, let (z, 1) denote legitimate image with the true class label 7, and == x denote an adversarial example, where signifies the adversarial perturbation. Here the natural image z and the perturbed image z + x are normalized to [-0.5, 0.5]4 Considering I classes of images (each group of images corresponding the same class is denoted by Ω2)) and network models, the adversary is to find the universal perturbation x across I image classes and models. The proposed attack problem is given by
minimize maximize xEX
fi(x, w) = Σ/ Elm [w., Fij (2, - A|/w 1/(J3)
(13)
wEW
where x and w E IJ are optimization variables, and myy denotes the j 1h entry of w correspond-
ing the importance weight of attacking image class i under neural network model j. In problem (3)
X denotes the perturbation constraint, e.g., X = {x] ||x||0 S 2
[-0.5, 0.5]d d Yz E U.S.).
W (w 1d w = 1, w 0). F.j (x; 7,) is the attack loss for attacking the set of images at class I; under model j. and X > 0 is regularization parameter. We note that {Fi,] in (13) are black-box functions w.r.t. x since the network models 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 {Fir} are given. Thus, problem belongs to the one-sided blx optimization problem.
blind the adversary, which cannot
In our experiments, we consider J = 2 for Inception V3 and ResNet-50, and /= for two classes, each of which contains 20 images randomly selected from ImageNet (Deng al. 2009). We also
8

---

Under review as a conference paper at ICLR 2020
specify the attack loss Fly in (3) the C&W untargeted attack loss (Carlini & Wagner 2017).
Fs (x; = (1/(9t)
Σ RED,
max (z - xx),, max 95 x)x.
(14)
k
where [9;] is the cardinality of the set S2; 9y + x) denotes the prediction score of class A given the input z + x using model j. In (T3), we also set 5. In A we set a = 0.05, / = 0.01, 10 and μ 5 x 10-3, and use the full batch of image samples in attack generation.
In experiment, we compare ZO-Min-Max with FO-Min-Mar and ZO- FO-Finite-Sum, where the former is the FO counterpart of [ 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-Sume 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-Si consider different loss function, it is baseline from the perspective of attack generation.
16a
ZG-Min-Max
for each model class pair
Man incca
Piniina N012
Max
IDC
10a
Stalionary gep
Attack bos
Mor wilk
modell-
20-1
0.00 0.25 9.30 n.1s 120 1:5
152 175 2000 Number of Iterations
0.0 025 o53 0.75 3:00 125
1.50 1.5
2,05
020 0.5 6.30 0.75 100 125 1:2 L/5 200
Number of Iterations
Number of iterations
(a)
(b)
(c)
Figure 1: Convergence performance of ZO-Min Max in design of black- box ensemble attack. a) Stationary gap ZO- Min-Max vs. 10--Min-Maxx b) attack loss of using ZO-Min-Na 10-Mii--axx vs. FO-Min-Maa and e) attack loss of using ZO-Min-Max vs. ZO-Finite-Sumi
In Figure we demonstrate the empirical convergence of ZO-Min-Mas to solve problem 13 from the stationary gap [[[(x, y)ll given in (6) and the attack loss Fi, under each model-class pair. In Figure (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 MO-Min-Max with FO-Min-Max in Figure I (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 (c). We also compare ZO-Min-Mar with Z0-Finite-
Sum, where the latter minimizes the average loss E'=E'=L Fej over all model-class combinations. As can see, our approach significantly improves the worst-case attack performance (corresponding to MIC1). 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:
MIC1 has the largest weight while M2C2 corresponds 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-univenn unn-unieeral PGD attack (Madry et al. 2017b).
the smallest weight. In Figure A3 of
Black-box poisoning attack against logistic regression model Let D fz,, t denote the training dataset, among which n'' < n samples are corrupted by a perturbation vector x, leading to poisoned training data z; + x towards breaking the training process and thus the prediction accuracy. The poisoning attack problem is then formulated as
maximize minimize |*
fa(x, 0) == Fur (x, 0: Do) A110112
(15)
where x and 0 are optimization variables, (x, 0 Du) denotes the training loss over model parame- ters 0 at the presence of data poison x, and À > 0 is regularization parameter. Note that problem (15 can be written in the form of (1 with the objective function -f2(x, 0). Clearly, if Für is convex

---

Under review as a conference paper at ICLR 2020
loss (e.g., logistic regression or linear regression (Jagielski al. 2018 ). then f2 is strongly concave
in O. Since the adversary has no knowledge on the training procedure and data. f2(x. 0) is a two-sided black-box function. We provide more details problem (1)) in Appendix In Algorithm[] unless specified otherwise we choose b = 100, 4 = 5, a 0.02, 3 = 0.05, and 7 = 50000. We report the empirical results averaged over 10 independent trials with random initialization. We compare our method with rO-Min-Maa and the BO solver for robust optimization STABLEOPT (Bogunovic in the data poisoning example of relatively small problem size.
al.
2018
0.95
Zo-Mi--aax: q=1
20 Mix-Mn-
Z0-Mi-Hax: q=5
0.50
FO Nin Max
Statorary p0p
Zo-Mtt-Kax: q-
20 Z0-Mi Max Q-20
0.85
Testhe accuroo
Nax
0.80
0.80
0.75
0.75
0.70
Min
0.70
No Polson
0.65
10'
16
100 Number of lterations
10'
30
0.60
10a
10'
12
10
10'
10
15
Number terations
Polsoning ratio (74)
(c)
(b)
(c)
Figure 2: Empirical performance of ZO-Min-Mas 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.
In 2 we present the convergence performance of ZO-Min-Max to generate the data poi- soning 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% poi- soning ratio and À 10-3 for problem (15). We examine the sensitivity of the regulariza- tion parameter À in Figure A4
Figure (a) shows the stationary gap defined in (6) obtained by 70-Min-Max under different number of random direction vectors while estimating gradi- ents (2). As we can see, a moderate choice of (e.g., 2 5 in our example) is sufficient to achieve near-optimal solution compared with FO-Min-Max. However, it suffers from a con- vergence bias due to the presence of stochastic sampling, consistent with Theorem I and 2 (bg demonstrates the testing accuracy (against itera- tions) of the model learnt from poisoned training data, where the poisoning attack is generated by ZO-Min-Ne Min-Max (black- box attack) and FO-Min-Max (white-box attack). As Z0-Min-Max yields promising attacking performance compa- rable 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 (c) we present the testing ac- curacy 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 well-trained model. Figure compare 2O-Min-MM with STABLEOPT [Bogunovic et al. 2018) in terms of testing accuracy versus computation time. Fol- lowing (Bogunovic al. 2018). present the best accuracy achieved up 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.
0.35
0.90
see,
F
7.85
0.80
STABLEOPT
0.85
20-Mp-Mae:
10a
10
10F
30P
Optimiation Lime (scconds)
Figure 3: Comparison between ZO-
Min-Max and STABLEOPT on testing accuracy versus optimization time.
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-bon max-max problem. Under mild assumptions, ZO-Min-NM Max enjoys sub-linear convergence rate. It scales 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.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Charu Aggarwal, Djallel Bouneffouf, Horst Samulowitz, Beat Buesser, Thanh Hoang, Udayan Khurana, Sijia Liu, Tejaswini Pedapati, Parikshit Ram, Ambrish Rawat, et al. How can ai automate end-to-end data science? arXiv preprint arXiv: 14436, 2019.
Abdullah Al-Dujaili, Erik Hemberg, and Una-May O' O'Reilly. Approximating nash equilibria for black-box games: bayesian optimization approach. arXiv preprint arXiv: 1804. 10586, 2018a.
Abdullah Al-Dujaili, Alex Huang, Erik Hemberg, and Una-May O'Reilly. Adversarial deep learning for robust detection of binary encoded malware. In 2018 IEEE Security and Privacy Workshops (SPW), pp. (6-82. IEEE, 2018b.
Abdullah Al-Dujaili, Shashank Srikant, Erik Hemberg, and Una-May O' O'Reilly. On the application of danskin's 's theorem to derivative-free minimax optimization. arXiv preprint 1 063222 2018c.
Charles Audet and Warren Hare. Derivative-free and blackbox optimization. Springer, 2017.
Bernstein, Y.-.. Wang, Azizzadenesheli, and Anandkumar. signsgd: compressed optimisation for non-convex problems. ICML, 2018.
Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher. Adversarially robust optimization with gaussian processes. Proc. of Advances in Neural Information Processing Systems, pp- 5765-5775, 2018.
Jürgen Branke and Johanna Rosenbusch. New approaches to coevolutionary worst-case optimization. In International Conference on Parallel Problem Solving from Nature, pp. 144-153. Springer, 2008
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In Security and Privacy (SP), 2017 IEEE Symposium on, pp. 39-57. IEBE, 2017.
Pin-Ye Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15-26. ACM, 2017.
Tianyi Chen and Georgios B Giannakis. Bandit convex optimization for scalable and dynamic loT management. IEEE Internet of Things Journal, 2018.
X. Chen, S. Liu, R. Sun, and M. Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. International Conference Learning Representations, 2019.
A. R. Conn, K. Scheinberg, and N. Vicente. Introduction to derivative-free optimization, volume Siam, 2009.
John M Danskin. The theory of max-min, with applications. SIAM Journal Applied Mathematics, 14(4):641-664, 1966.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, pp. 248-255. IEEE, 2009.
Amit Dhurandhar, Tejaswini Pedapati, Avinash Balakrishnan, Pin- Yu Chen, Karthikeyan Shanmugam, and Ruchir Puri. Model agnostic contrastive explanations for structured data. arXiv preprint arXiv:1906. 10t.190060.0.7... 2019.
C. Duchi, M. I. Jordan, M. Wainwright, and Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEFE Transactions on Information Theory, 61(5):2788-22 2015.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. On the convergence theory of gradient- based model-agnostic meta-learnin algorithms. arXiv preprint arxiv: 1908. 10400, 2019.
11

---

Under review as a conference paper at ICLR 2020
Chris Finlay and Adam M Oberman. Scaleable input gradient regularization for adversarial robustness. arXiv preprint arXiv: 11468, 2019.
Lampros Flokas, Emmanouil- Viniiloui-VVasileioos Vlatakis-Gkaragkuunii, and Georgios Piliouras. Effi- ciently avoiding saddle points with zero order methods: No gradients required. arXiv preprint arXiv:/910. 13021, 2019.
X. Gao, B. Jiang, and S. Zhang. On the information adaptive variants of the ADMM: an iteration complexity perspective. Optimization Online, 12, 2014.
Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
S. Ghadimi, G. Lan, and H. Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2):2673355 2016.
G. Gidel, T. Jebara, and S. Lacoste-Julien. Frank-Wolfe Algorithms for Saddle Point Problems. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54, pp. 362 371. PMLR, 20-27 Apr 2017.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.66 2014.
E. Y. Hamedani, Jalilzadeh, S. Aybat, and U. V. Shanbhag. Iteration complexity of randomized primal-dual methods for convex-concave saddle point problems. arXiv preprint arXiv:1806.044 041 18, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Jeffrey W Herrmann A genetic algorithm for minimax optimization problems. In CEC, volume pp. 1099-1103. IEEE, 1999.
A. Ilyas, L. Engstrom, A. Athalye, and J. Lin. Black-box adversarial attacks with limited queries and information. arXiv preprint FrXiv:8804.0859 2018.
Andrew Ilyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. International Conference on Learning Representations, 2019. URL
.et. fert/forum22 1dd=mm1dd---hhheeemmm
Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, and Bo Li. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. In 2018 IEEE Symposium on Security and Privacy (SP), pp. 19-35. IEEE, 2018.
Mikkel Jensen. A new look at solving minimax problems with coevolutionary genetic algorithms. In Metaheuristics: computer decision-making pp. 369-384. Springer, 2003.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. arXiv preprint arXiv: /902.00618, 2019.
Eric Jones, Travis Oliphant, Pearu Peterson, al. SciPy: Open source scientific tools for Python, 2001.
http://wwwwwiiy.oxo./
Jeffrey Larson, Matt Menickelly, and Stefan M Wild. Derivative-free optimization methods. Acta Numerica, 28:287-404, 2019.
J. Liu, Weiming Zhang, and Nenghai Yu. Caad 2018: Iterative ensemble adversarial attack. arXiv preprint arXiv:1811.03455. 2018a.
S. Liu, J. Chen, P.-Y. Chen, and A. O. Hero. Zeroth-order online admm: Convergence analysis and applications. In Proceedings of the Twenty-Fin International Conference on Artificial Intelligence and Statistics, volume 84, pp. 288-297, April 2018b.
12

---

Under review as a conference paper at ICLR 2020
Sijia Liu, Pin- Yu Chen, Xiangyi Chen, and Mingyi Hong. signSGD via zeroth-order oracle. In Proc. of International Conference on Learning Representations, 2019. URL /ttpptsps/////eeeiiiiis net/ met//oouuee
Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial examples and black-box attacks. arXiv preprint 16I1v0:61..277/00 2016.
S. Lu, I. Tsaknakis, and M. Hong. Block alternating optimization for non-convex min-max prob- lems: Algorithms and applications in signal processing and communications. In Proc. of IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 4754 4758, May 2019.
S. Lu, I. Tsaknakis, M. Hong, and Y. Chen. Hybrid block successive approximation for one-sided non-convex min-max problems: Algorithms and applications. arXiv preprint UrXiv:/922.088 2019.
A. Madry, A. Makelov, Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant 2017a.
to adversarial attacks. arXiv preprint
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 1oXiv:/706006000 1706.66883, 2017b.
Seyed-Mohsen Moosavi-Dezfooli Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Ro- bustness via curvature regularization, and vice versa. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9078-9086, 2019.
Y. Nesterov. Dual extrapolation and its applications solving variational inequalities and related problems. Mathematical Programming. 109(2-3);319-344, 2007.
Y. Nesterov and V. Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 2(17):527-566, 2015.
M. Nouiehed, M. Sanjabi, J. D. Lee, and M. Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. arXiv preprint arXiv: vrXiv:1902.08297, 2019.
Victor Picheny, Mickael Binois, and Abderrahmane Habbal. A bayesian optimization approach to find nash equilibria. Journal of Global Optimization, 73(1):111-192, 2019.
Qi Qian, Shenghuo Zhu, Jiasheng Tang, Rong Jin, Baigui Sun, and Hao Li. Robust optimization over multiple domains. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4739-4746, 2019.
H. Rafique, M. Liu, Q. Lin, and T. Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprint arXiv: 181..020660 2018.
Luis Miguel Rios and Nikolaos Sahinidis. Derivative-free optimization: a review of algorithms and comparison of software implementations. Journal of Global Optimization, 56(3):1247-1299) 2013.
M. Sanjabi, Ba, M. Razaviyayn, and D. Lee. On the convergence and robustness of training gans with regularized optimal transport. In Proceedings the 32Nd International Conference on Neural Information Processing Systems, pp. 7091-7101, 201 8a.
Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and Jason D Lee. On the convergence and robustness of training gans with regularized optimal transport. In Advances in Neural Information Processing Systems, pp. 7091-7101 2018 8b.
Tom Schmiedlechner, Abdullah Al-Dujaili, Erik Hemberg, and Una-May O'Reilly. Towards dis- tributed coevolutionary gans. arXiv preprint arXiv:1807.08794, 2018.
O. Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1-11, 2017.
Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. Certified defenses for data poisoning attacks. In Advances neural information processing systems, pp. 3517-3529, 2017.
13

---

Under review as a conference paper at ICLR 2020
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2818-2826, 2016.
Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. In Advances in Neural Information Processing Systems, pp. 8000-8010, 2018.
C.-C. Tu, P. Ting, P.-Y. Chen, S. Liu, H. Zhang, J. Yi, C.-J. Hsieh, and S.-M. Cheng. Autozoom: Autoencoder- based zeroth order optimization method for attacking black-box neural networks. arXiv preprint arXiv: 1805. 11770, 2018.
Abraham Wald. Statistical decision functions which minimize the maximum risk. Annals of Mathematics, pp. 265-26620222 1945.
Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y Zhao. Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. Neural Cleanse: Identifying and Mitigating Backdoor Attacks in Neural Networks, pp. O, 2019a.
Jingkang Wang, Tianyun Zhang, Sijia Liu, Pin-Yu Yu Chen, Jiacen Xu, Makan Fardad, and Bo Li. Beyond adversarial training: Min-max optimization adversarial attack and defense, 2019b.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. AdaGrad stepsizes: Sharp convergence over nonconvex landscapes. In Proceedings of the 36th International Conference on Machine Leariing pp. 6677-6686, 2019.
Richard A Watson and Jordan B Pollack. Coevolutionary dynamics in a minimal substrate. In Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, pp. 702- 709. Morgan Kaufmann Publishers Inc., 2001.
14

---

Under review as a conference paper at ICLR 2020
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.
Table Al: Summary of problem and algorithmic parameters and their descriptions.
parameter
description
of optimization variables
mini-batch size
# of random direction vectors used in ZO gradient estimation
learning rate for ZO-PGD
B
learning rate for ZO-PGA
strongly concavity parameter of f(x. y) with respect to
upper bound on the gradient norm, implying Lipschitz continuity
Lig, Ly
Lipschitz continuous gradient constant of f'x, y) with respect to x and y respectively diameter of the compact convex set X' or
R
lower bound on the function value, implying feasibility
o
variance of ZO gradient estimator for variable x and y respectively
A.2 PROOF OF LEMMA
Before going into the proof, let's review some preliminaries and give definitions. Define hy (x. E to be the smoothed version h(x, {) and since & models a subsampling process over a finite number of candidate functions, we can further have (x) - Ee[h (x, E)] and (x),(() = [V (x, E)] Recall that in the finite sum setting when E, parameterizes the jth function, the gradient estimator is given by
d[h(x Jmi E,) M(x: E,)] u.
<xh(x)=
(16)
by
where I is set with elements, containing the indices of functions selected for gradient evaluation. From standard result of the zeroth order gradient estimator, we know
Ey En E
(xx(())
|z] = Ez
1 b JEE
V vx
= (xhx(xx..
(17)
Now let's go into the proof. First, have
E
Vxhm((x)13
2
= -Ez
Eu, Lu,l
Fx1(x) -
1 Σ (x)((x
+ Σ Vxlu(xxE,) - Vxh(
JEI
JEI
(an((s))
<2Ex
Σ (x
+
V Vxfu(x,E,) (x)(((x)
I
JET
JET
(18)
Further, by definition, given I. (x) the average of ZO gradient estimates under f.i.d. random directions, each of which has the mean ; Ejez Vxfā(x, E,). Thus for the first term the right-
15

---

Under review as a conference paper at ICLR 2020
hand-side (RHS) of the above inequality, we have
Fab(x) - Ev (x,x(xxEE)
+ 12
I
2d
v
vxf(x,EE)
b
jET
jET
2d12 +
(19)
where the first inequality by the standard bound of the variance of zeroth order estimator and the second inequality is by the assumption that <x;; r72_In addition, we have
1)? s 17² and thus Ciez Ex,,x, s
2
Er
E
b
Σ
V (x)E(x,E)) (x)
JEI
1
E3
(x. (x)
6
JET.
1/2
E [x.xf((xxE) (xhn(x))1
(20)
where the second equality is because &, i.i.d. draws from the same distribution as and B[Vx (x, E)] (x), the last inequality is because [/Vx E) s 17² by assumption.
Substituting 19 and (20) into (18) finishes the proof.
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: define
Since iterates (1),) Vt are random variables, we need to
F(( (x ((), x ((111)
(21)
the history of the iterates. Throughout the theoretical analysis, taking expectation means that we take expectation over random variable at the 7th iteration conditioned on (t--1) and then take expectation over (t-1))
Subproblem: Also, it is worthy noting that performing 4 and ( are equivalent to the following optimization problem:
(0) = min XEX
(x(((x()-1) 1)t- x((-1))
+
|| x - x 11- 11?
(22)
2a
(() max
yey ()(((((t)) (0 (1-1)) (t
1
y- (t-1) 112.
(23)
23
When f(x,)) y) white-box w.r.t. y. becomes
(()) max yEy
(Vyf(x()
y(( 1)
233 ll (1-1 112
(24)
In the proof of ZO-Min-Max, we will use the optimality condition of these two problems to derive the descent lemmas.
16

---

Under review as a conference paper at ICLR 2020
Relationship with smoothing function We denote by fu.a(x, y) the smoothing version of f w.r.t
x with parameter fa >> O. The similar definition holds for fu.g(X.))) y) By taking fu. (x. y) as an example, under A2 f and fu,, has the following relationship (Gao et al. 2014 Lemma 4.1):
Lust
(x)x(x, [(x, y))1
and |V//ux(x S 1l2 <
(25)
2
1n and [yfpn((x - v 12
L
(fug(x,y) - f(x. y))l -
(26)
2
4
First, we will show the descent lemma in minimization as follows.
A.3.1 PROOF OF LEMMA 2
Proof: Since y(x, has bz Lipschtiz continuous gradients with respect to x, we have
fu(x(t+1,,)) y()) Sf((x(0) yy(0) + (Vx(u(x()) , y(t))) x((11) - -x())
Le
-x(00)
+
2
=fa(x!)) ,y()) + (xx1(x(1) ,y(0), x((+1)) - -x(1)
x((++)) -x(1)) 1|2
2
+ (Vxf((x()) (0)) - Fxf(x!1) y x ((+1) - -x()).
(27)
Recall that
x(++1) = projx (x(1) - -x ,x (())),
(28)
From the optimality condition of x-subproblem 22 we have
(x(((()) (t))), x((+1)) x1)) 1
||
(29)
Here we use the fact that the optimality condition of problem 22 at the solution (t-1) yields
(Vxf (x((1) y())) + (x(++) - / x(++1) -x) < 0 for any x E X. By setting x x() we
obtain (29
In addition, we define another iterate generated by (xf((x((') (x())
((1-1) proj
(x) (x)xx)(((+))) a (x y(()))
(30)
Then, we can have
(xx)((x() .-()) xxf(x()) .y((0) ) (c+1) - (x
[Vxsa(>>(1) (0))) (10)) - Fx((x((), ,,((1) (++1) -x(1) -(x(t-1)- - x(1)))
+ +XVxsn( ((()) - {x((x(), (1) (((+1) - -x(0).
(31)
Due to the fact that E. V (x(() ,(10)) = vxfa(x(), (x((x)())((1))) we further have
E. E. (V (1)))) (x((x(()) yy0)) (((+1) xx())]] =
(32)
Finally, we also have
(V (x(()((()), ((1)) Fx((x()),
- ((())))))(()))) x(++1) x((t) -(x(t+1) -x(11))
(1)) ((1))x((++1)
(x(() (0)) Fxf(x()) x + 2a
- || x((1-1) -x(-))x(1) -(x(++1) - {1)))12
1
{aI(Vz/((((()) y(0) - (x
(33)
where the first inequality is due to Young's inequality, the second inequality is due to non- expansiveness of the projection operator. Thus
Em (V.lVxJna (x()(x()) y(0)- - {z((x((), y,()), x((+1) - - x(1)))
<En (0| (x(((x(() ((0) - Fxf(x(()) y S a0?
(34)
17

---

Under review as a conference paper at ICLR 2020
where o2 := oz d) which was defined in (3)
Combining all above, we have
(x y() SE[fa(x!) ,(0)) (1 a
-1 1ix (
xx(0 -x(0 x2
to?
(35)
and we request S 1/ Lzz which completes the proof.
Using (x, - f(x, -
2 we can get
B[[(x(++)) )()) Lap²
[[[((((t))) y(())) + La11²
S (x
(36)
2
able to obtain from
E ( - ([f(x(0)) y())) - (2-11)) 1iz
2 || ||x(0-1] xx10 ao² + Lunt. (37)
Corollary 1.
E (V y((-1)) ((-1)) -V/x(x(0) (((t-(),,(t-1))
y(t-
,((t) y(t)) -y((--1) S Bo
(38)
o3 (2 b, q, d) which was defined in
Proof:
Define
= prrojs(r() -BV (x((0, (((())))
(39)
we have
(VySn(x(0) 1(- - Fx((x(0) (.((-1)) y, y(1) - (((1-1)
=(VySn(x())) y((1=))) ,x (((-1))) y()) -y((-1) -(5(1 -(((-1)))
+ (VyS((x(1) (((-1)) F,((x(1)) y
(t- (((-1)), f(t) - (((-1)).
(40)
Due to the fact that Eu fx(((()) y (yfu(x(()) ,((( further have
E.K V ,(((11)
Fyf(x!") (((11)))))
y((-1)), 50(1) y((11)))]
(41)
Finally, we also have
(x y ((1- fx(((!") (1(11)), (()) - (1((-1) 1) -(5(1) (1(1-1))}1 3
<Eul 2 (VV y (-11) Fxf(x() (1- (t=1)))12 23
y (1) - (t((-1) -(x(1) (t-1)) ))
SB. Vy ((1-1)- Fx y y((-1)) Bo
(42)
where of = a² ( b, d) which was defined in
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 ((), ,(t))(()))))) generated by algorithm When f fxx(9) ,y) white-bon box, we have
Ell y (1+.1) -000 Beg
2
2 Beg
Elly(( (() 11(1-1)123
212
El ((+1)
(x+1)_x(1))
-x(1)
Br2
2 -y(0)
212
+ Bly
- (1 1p? (43)
3
18

---

Under review as a conference paper at ICLR 2020
Proof: from the optimality condition of y-subproblem (24) at iteration t and t 1, we have the following two inequalities:
(Vy5((((+1) ,y((0)- (x(0)) 1 (yy(tt))-
,(0)), - -1( 20, (44)
())((((()) y(-- 3 ((5(1) -ylt ylttt) y(t) 5o.
(45)
Adding the above inequalities, we can get
3 (viCtt) , y((t1) -y(0) = (x -((0) Vx((x(1) (x()) ((((1) -1(0) -x(0)
+ (x(()((())))))))))))))))))))){ (y()) - vyf(x(() y(t ), y((==) - -((0)
(46)
where v(++1) = ylt+1) - ylt) -(y(t) - y(t-
According to the quadrilateral indentity, we know
(vitt)), ((ttt)yy(tt y(t+1) yl()) = 1 (11x((t)) y()) 12 + (++1) || - || y - y-t-1 [1].
(47)
Based on the definition of ((+1)), we substituting
47 into 46 which gives
2B y (o0tt)y(()) 1|2 = (x(t)
1
y 12 2,3 v(t+ ||
2
+ [ 11, y())) - -Vy[(x())
yr(()) (((t)), y(++1) - -
+ Fxf(x()) y(1)) V3f(x(0) (x((_1)),, ,((1+1) -5(00)
(48)
(0)
(())) y 12 (Vys(x((+)) y()) - V) ),(t)) - y(())
2/8
31.
- (1-1) 1 711 (1) - y(1-)) l2
2
(M)
1
(t) (((-1)
1) |2 + 3 -11 l|2
-
2/
1 (1++1) - (1) 12 - (7 2
3 ||| y(()) - y((- ||
+ x
(49)
2ry
where in (a) we use the strong concavity of function f(x, y) in y (with parameter y > 0) and Young's inequality, i.e.,
(x)((((), y(0)) ((1)) vyf(x!!, [x((x(0,,((-11))
(((-1)),, ,,(1))))(((1)) - -y(())
= (x())((()) y((0) - Vxl((((),)() y((t-)), v((+)) + y(t) - y(t-1)
312 y (ly(t)) - -x(t-) 12 + 233
v((+1) 12- ( - -1
(50)
2
and in (b) we apply the Young's inequality, i.e.,
(Vys(x y(t) - (y)(x)))))))))) y(++)) -y())
-((1)) < 27
I22 (+++1) - x(1)) 11+ ? 2 11 -
- y00) pp.
(51)
Therefore, we have
12 1|2
23 y (4+1) -x(1) 1|2 2g y(t) -1((-1)
||
(x(++)) -x(!) 1|2
27
312
+ = ( - y0t) 1
7 -ーー
|1y(t) - - 12 (52)
2
19

---

Under review as a conference paper at ICLR 2020
which implies
2
2 82, 1ly00) -y(t-1)
2L
y (++1))
12 ((+11)
+
872 ||
x (1+1) x(11
B27
2 + y|( (0) 12
21
11 - yy0 ||.
(53)
3
By taking the expectation on both sides of 53 we can get the results of Lemma 5
Lemma 5 basically gives the recursion of || |
(1) 1/ It can be observed that term (4/3 y /
provides the descent of the recursion when 8 is small enough, which will take an important role in when we quantify the descent in maximization.
the proof of Lemma [
Then, we can quantify the descent of the objective value by the following descent lemma.
A.3.2 PROOF OF LEMMA 3
Proof: let f' with respect to the constraint of y. From the optimality condition of sub-problem y in (23) we have
f(x(++1)), ((x((t))),((+))) - 1(y((+1))
and (ly) denote the indicator function
fx((x(++)) y(1)) 3 (y(((+))) (()) (((-1) 0
(54)
where (l9) denote the subgradient of 1(y(t)). Since function y) is concave with respect to y. we have
I' ['(x ,((t)))- ('(x((+)), y(t)) S (Vy((x((t)), yy(1)) y((+))) - y()) - - (1)
(a)
x00 112 (5(0) - _((tt)) ((tt),y('t ,((+1) - )(0)
B
3 (y((tt) - - ( (Vy y(0)- - vy1(x(1), ( y((-1)), y((t)) -y(0)
1
1 (v(ct)) ((++1) ) 3
(55)
where in (a) we use g((+1) V. / (x (x((+1) y(0) (y((+))) - -y()) The last two terms of (55 is
the same as the RHS of (46). We can apply the similar steps from (48) 49) To be more specific, the derivations are shown as follows: First, we know
I' (xx(()+)) ((-1) - [' y(0) s 3 -1y(ttt)-y0 1l
(Vy (0) - fx((x ((( y)),) ((41)) ( y(t)) (v(tt))))((tt))
((++))) -1(0))
(56)
Then, we move term 1/8 1/B(v(++1), y ()( to RHS of 55) and have
s(x((+1) ((++))) - f(x((+1) (0))
1 111 ()) 1|2 + 2/3 ll y(()) - (y(t-1) 12
2 v(t p
28
(v 1) ((0)) fy5(x(()) ((()), (((()))) y(())
+
+ (x((((()) y ((0) (x((x()) (((-
) ((++)) - -
1
| - (0) 122 + (V (x)+ y())) - [x((x(()) ,(()), (((+)))))))))))1)) -y(0)
2/
312
y (1) -1( 1|2 7 (t) ( 2|
+
2
(0)
3 y (t+1) y (1) 112 +
1 || y(()) -y (1-( 1|
28
3L2
BL3
+ 2
x (1-1) (0) 12 (7
|| (0) ((12 1|2
(57)
2
20

---

Under review as a conference paper at ICLR 2020
where in (a) we use
(Vy((x(+=), (x())) - vyf(x((),)1)
(1(+1)
-x(1) 12+ y((+t) - -y10 112 (58)
2
23
which is different from [51 ; also y/!), y((tt) E y so have l'(x((tt),, ((x((ett),y(ttt1)) = s(x((++), ; yletl)
and (((((++),, y(0) = f(x y.
Combing (33) we have
f(x(++2), (1((t1),,((++1) +
2
+
||
- --(0 10-
I
|1y - -0(0) 1|2
g
28
3 27
2
1
(
L2
{f(x(1t)),
+
11 ((1
(10-1]11 112
4
/| - -yl 1??
Ben
23
3
27
1
21
|y((+)) - yy0 1|2+
22 7
3L4
x [t(+1] x 112.
(59)
2/3
2
By taking the expectation on both sides of 53
we can get the results of Lemma
Next, we use the following lemma to show the descent of the objective value after solving x- subproblem by ④
A.3.3 PROOF OF THEOREM 1
Proof:
From Lemma we know
[ (1+1) y ((+1)))] +
2
1 Elll (((+1) y000
-x00) 112)
+ 2/3
B2y
1
2
Elll y (1+1) (0) |2] $ [E[S(( (1+1) (11))
3
27
43
Blly -y(t-11) 11
Elll y-(1) (t- 1121
82g
23
2n
1
213
Bill (t++))111
[13]+
222
312
B||l x (1+1)
xx(1) 117].
(60)
2
7
223
Combining Lemma
we have
(1) y((++))]++
2
+
E - -1(0) 113]
82n
23
12
E y (1) [12]
< (if(x (1) ,((())) +
2 1 E 11)(())))( y [13]
4
27
32
2/3
4
1
12
E
(11x(())
(t 113]
1
2L
E [1t - 11)
B
27
2
7
Lg
2L
3L2
E
(+(() - -x(() (t) 122
+ +ao + Lotk?
(61)
2
3
2
1
3
4L2
and
a
<
2L2
(62)
7
21

---

Under review as a conference paper at ICLR 2020
then we have that there exist positive constants 01 and C2 such that
((x(+11), y(tt1), A P(x!") y((t) Aهه)
s - ||y((t]] y10 [||] c212 [|| [|x(++]]= (1)) ||2] 20zz + 1.ng1
(
s- (x y00 ||2| + [x((+1)) - (2]) + ao² + Lafk²
(63)
where Ç <= min(ei, c2).
From 6 we can have
[
(t))
|| (ct) 11 || + - +1|+= xx(++)) - projjx (x(()) -xVx((x (()) + 1 b -1(00))--00)) -1()
| ||(((t) projy + (x(0))
+ 3
(9) 1
x (1+1) -x
+ 1
projx ((+1) -a(Vx ,(0)) + (x((++)) -axx/xx)) yx()))
1
y ((++)) -11o ||
+ 8
1
prois ((+2) + +3(Vy (111) .1(0) - 1 (y((t)) pr +3V x 1(x(0) ,,)))))))))
+ 8
(b) 3 x ((+1) - + 1 (x((1+)) x(0)) -Fx((x(0) y())) +
3 y -y(t)
(0)
3 + L.x |x(++)] (x) || +|+ 3
(y((t1)-y-1 ||
3
where in (a) we use ((+11) = proj (x (e+1) -V (x(((((())) y(0) - - (x())) (b) we use nonexpansiveness of the projection operator; in (c) we apply the Lipschitz continuous of function yxx,y) with respect to x and y under assumption A2. Therefore, we can know that there exist a constant m La + a B
3 such that
( )1 < (1xx - (0) 112 +
||++|| [|x((tt]] (0)) 112)
(64)
After applying the telescope sum on (63) and taking expectation over (64), we have
e (PI ( Prtt + ao² + Lam?)
Σ (
(1) y (9))
(65)
? T
Recall from A1 that f 22/ f and y is bounded with diameter Rt therefore, Pe given by 8 yields
P. Pz + (min(4 + L3 - 78% 0}
R². Vt.
(66)
2,32g
And let (x()), (()) be uniformly and randomly picked from (66). we obtain
based on 665 and
1 T E, [ 11))
[x
(1)
0000) c
(p
RR
+ ao + Lapk? L
T
T
(67)
where recall that (= min(ci, c= max L2 + 3 }) and min L3, 787.03
23
The proof is now complete. 0
22

---

Under review as a conference paper at ICLR 2020
A.4 CONVERGENCE ANALYSIS OF MO-MIN-MAX BY PERFORMING ZO-PGA
Before showing the proof of Lemma we first give the following lemma regarding to recursion of the difference between two successive iterates of variable y.
Lemma 6. Under assumption I, assume ierates x(),, y generated by algorithm (x y) is black-box, we have
When When function
2 Bay R8| y((t1)) - -000 11=
2 B2
2 Rl -
Elyy (()) -y((-1) 11+
B
6I2 41 7
+4
E
x
(1+1) xx(0) 1
TB|| y0 - ((0-1) 1|2
372
40 3
1 2
+ 43
(68)
By
7
B2y
From the optimality condition of y-subproblem in 23) at iteration t and t we have
(xf(x((t))))1) --(1)
3 (r((t))) - -())),, y,((+t) -y(() 50,
(69)
Fx((x(0) ,(((-1)) (
3 } g(y(0)) - y((-1)),
1
), y((+1) - y(())
50.
(70)
Adding the above inequalities and applying the definition of ((++)), we can get
3 ((vettt) y((t2) - (0) (1( F )((0)) (((-1) -y(0)
Vyl(x(),))) (x(()()) ,((r-))
,((e()))(((+)))) ), ,((+1) - -y((1)
(71)
Next, we will bound E[] and E|I[] separably as follows. First, we give an upper bound of [E[]] as the following,
E
v (x((()))
y(0)) - (x((x()) ((41)) (0 -y(0)
v (x((+1)) y10)) VxJnn y(1))122 + _ y(l)))++)) y s|2
E8
27
+
E
V y u.y (+1) ((()) - VyJna (x(1) (0)) + | (((+1) - 1|2
27
3
E
V,
juy (x( (1) (0) -p y 11)1 + | - y l|
27
302
3L2
x (++) - (1 1| + 2 y 11( 1
(72)
27
where Lemma 0 is used.
23

---

Under review as a conference paper at ICLR 2020
Second, we need to give an upper bound of E[[I] follows:
( yl f(((()) -(l-1) ) y(++1)
-((+))-(()) -y(0)
[(][(x E ,/ v((+))++
+ +y(0- - -y((-1))
V (( (0) VS(x ,((c)))) ), y0(00 -x((1)((1))
(Vinx(x y - vf(x(1) (((1) y(() -y((-1))
(8S(x0)) (()) V/ns(x(()) y(0)) (()) -y((-1))
(Vino(x (0) (((-11) vf(x(' (( 11), y(t)) --(t-1)
(85(x()) -((-1))- -VSpx(' ()) (t) y(t-1)
(xx(() y())) &)(((() (((-1)), v((t1)).
Next, we take expectation on both sides of the above equality and obtain
E(ŌS(xx() (y( - fx(((), ( y((tt)) - ((t))
13112 4 + 1 ||y(0)) (1 1) 112 + 1
w(tt1) 1|2 711 y() - y((t-1)
2
2B
+ 430g
(73)
43
where in (a) we use the fact that 1) y-strong concavity of ff with respect to y:
(Vi(x()) (()) (x((()) y(t- y(0 y" S (1)
-y(1-1) 12:
(74)
and the facts that 2) smoothing property 26) and Young's 's inequality
fx(((() ((()) ) yit) y) 122d012
E (Vy (x (t))
y(t- ||: -11000--((111
(75)
8,3
and the fact that 3) the ZO estimator is unbiased according to Lemma
(ff((()))))))))))))))) (0)) - (x ,,(0), (0) - y(1-1))
E
= 0;
(76)
and
E (v)n(((()) -((-1)) -V(((!),
( y((--1)), - -y(-1)) <
+ 2
B
-1y0)-
(1-1 1?:
83
(77)
and from Corollary
I we have
E f(( (x(-)))())1)))
Vay (xx(),,
()(tt-)),, y0(() -)((-1))
< 30
(78)
and
E
f (x ((0) - -8((x() (((x(),,((--1)))
(((-1)), v(t+1))
33
E
V
(p (x.1, y()) - 6/(x(0) ((0))]2 + v(++1) 2|2
2
33
El
Vfa (x (1) ())) Tfax(x!) 1))1 +
1
v (++1)) 1|2
2
633
33
E V (x()), )(()))) f(((())) y (1
1
v((+1> p|
2
63
1
|| ((++)) 112 3 (1) (1-1 122
5380 +
(79)
23
2
24

---

Under review as a conference paper at ICLR 2020
Then, from 71 we can have
1
Bl| y ((+1) - y 12
-
1
Bll
10:0000y0 -y(1-1) 1|2 - 1
ا v((tt) 1|
28
23
29
3 y +
3L2
B1| (1(+1) - (x)) 12 + _ y(t))) y 1|
γ 27
+
( fxx("
1xx00)y11) ,((1)) - ')((x() (((=))) ) y((+)) - )y("))
Fl| y(0) -y (1-11)1 -y(t-1) 1|2 + 2 y((+)) - y(()) $|2
2
2,
3
BI| x((1)) -x(1) 11 7- /331 1 + 8) () E y())) -y (1-11 ||?
27
30
12d
+ 4,0
+
(80)
43
which implics
2 y2n
E
y((11) --000 -y(0)
113 S
2
El| (() -y(t-1) 1|+ ]
2
Bll B 1|2
B2g
B
E
x x((+1) -x(+) 1|2
4
612 + 4 7
E|| El| - -y 1|
372
B
40 y
3
+ 1² 122 12
+
+48
+ 43
(81)
By 7
A.4.1 PROOF OF LEMMA 4
Proof: Similarly as A.3.2 let ('(x ( =
- f(x((+1),
y((t))) - 1(y((+))), - 1()) denotes the
indicator function and (o) denote the subgradient of 1 (y((t)). Since function f'(x, is concave with respect to y, we have
['xx (+11) y((+2) ('(x((t)), y00) S (V[(x((+1),
,,0))) (((0) y((t)) - -y(0)) - -(010,y(+t)) y((+1) - (0))
(a) B -y(0 112 - -(9(0 - ((tt))y((+)) (((1)) -y0))
-y(0 r (ff(x((+)) ((0)) - =f((((), (1(x(),,((111)) ,((-1)), y(141) - -((1))
--(0
)((1))))(++1))
- -3 ( - y(t))
- 1
(82)
where in (a) we use (((+1)) = f5xx((+1) y(0)) - -)())t)))y(0). Then, we have
- Ef(x(++1), y 1((+1))-- -Ef(x(++)) ((())) + 3 (vr--), y(ett)) - y(t))
1
< (0) 1|2 (+ (())) fs((!0) y(t-1)),
-y
y, (1+22) - y00))
Applying the steps from (33 to 80
we can have
Ef(x(++1), (((+1)) ((x(ttt)),((+11))) - Eff Ex((((+)) (++1) y()))
< 1 3
-1( -y(0) 1|2 + 1
E (())) -y(1-1)11 112
-7-
(3812 #8)) ) 1 - y(t- 1|
2,3
2
3812
22d21
+ 2
El x((=1) -x(1 1/2 + 7,50 +
(83)
43
25

---

Under review as a conference paper at ICLR 2020
where we use
V fx(((t())) y100) - f (((0)))),)11)))) , - y(0))
3
<380 +
- x(1) 12+ Bll (( y(0) 1|?
(84)
23
Combing 81. we have
2
1
4
6L3 +4
(1)x((+1) ([(x((+1),y(tttt))
y((+1)) +
+
B| ( - -x(()) 113
El y((+t) - --00
28
7
<Bf(x((+1) ,,((((()),),)))))) +
2
1
E y y((-1) 1) 113
4
677 +4
E3 y(t)) -y -y((-1) 1|?
1827
28
3
6L2 +4
3,12
E| y ((++1) -y(0 112+
EB| x((++)) _ xx(0
+
23
2
L. y
(1
+ Br )
4 3
+
73 +
+ 73
og
(85)
4
By 7
A.4.2
PROOF OF THEOREM 2
Proof:
From 37 we know the "descent" of the minimization step. i.., the changes from to P'(x((+1), (()), A Combining the "descent" of the maximization step by
P'(x((), (t))
Lemma shown in we can obtain the following:
P'(x((+11 ((+1)) ,((+t), A())))
<P'(x!1) ((() ())
1
67 +
E (|((++))) y(()
(86)
2/3
7
01
D
6
3 2
E
[| [|x((+t])
- (+) 122
2
2 3
42
LL y
1 Br
1 1
4
/3
+ 2
Lg +
+
+ao +
7B +
+ 4,3
og.
B
By
When 3, a satisfy the following conditions:
B 7
and
(87)
4(322 + 2)²
6L2 7
3812
2
we can conclude that there exist b,, by > 0 such that
P'(x(t+1) ((+1) A (1+1))
SP'(x(') (()) A an E
|| (1+1) - y:t)) [22]
xx() |2] + biu² + a0² + bzo
5 C'E [|y((+t)-))1 (0) 2 (+(1)++1) x1 [?7 + bu + a0 + byo²
(88)
where Ç¹ min(a1,a2).
26

---

Under review as a conference paper at ICLR 2020
From
6 have
E
Bll
x (41)) x (0) || + - Ell x (++1) -pooix (x (x(0) -a xx(((x()) .y ((0)))
+ E y (1+1) y(t)) || +  ((th1) -rojjy (1) + 5(x(((()) 11 (())
Bl x (11) x1() + الل
((()) -
([x(()]) ((11)) -
-x ((01) -oroorrooiiioi
Frood (x(10) -aV ( (
(
y(1))) y(1
+ fx(x() 1 ا
+
E
y(0))
- ( (y rrloa
((0o
3
B1 x ((1))
I(tii)
3
(1+1) ((t
(0)) - -V3/(X0 y ||
3
El x ((4) (0)) + - (x y())) V (x (())))
a
+ E
(1) y())) vxf(x y(
3
E
(() + EB| V f(x
(x (++1) (())= - (xlnx(x(( )((t))
E IV
(0) vyfur (x(1) (()))
+ E V
- Vy((x(() (x((()())))))) ,((t))
3
レo E (++1)) x0) ||+ 3
Bl|
|| 20² + pd
where in (a) we use the optimality condition of (0)) -ubbprobbe in (b) we use nonexpansiveness of the projection operator; in (c) we apply the Lipschitz continuous of function y(x, under assumption A2.
Therefore, we can know that
E ((0 s c (1xx(++))x() 1|2 + ( - + 20 + + Ldd
(89)
After applying the telescope sum on 88 and taking expectation over 89). we have
T
E (00>))
Pi < 5 T
--rtt
+ obi 12 caoz Ç' " c
+ cb2
o + 20
dL (90)
Recall from A1 that f 2 f and y is bounded with diameter R, therefore, P. given by 11 yields
P. P + mmin{4 (4 + 4(312 + 2))²² - 7,3,, 0}
R², Vt.
(91)
B2g
And let (x(r), (+)) be uniformly and randomly picked from (x(0))(0))) based on 91 and 900.. we obtain
T
Ep
IE
[[ (r), (1) [111
E (000x)0,((00)))
c P1
fo v/ R²
cbi
cao2
db2 oz + 20
12 +
+ 11
(92)
T
Ç'
3) and v/ m -7
where recall that Ç' = min c= max L, + a
13"
The proof is now complete. 0
27

---

Under review as a conference paper at ICLR 2020
B ToY EXAMPLE IN [BOGUNOVIC ET AL. (2018): ZO-MIN-MAX VERSUS BO
We review the example in Bogunovic et al.
2018 8 as below,
maximize minimize ||1|2gu0.5
(x -2 61) 12.2(1) 81) - 21.2(x) - 61)4
XEC
- - 4 51)2 (x -22)
+11(2g - 62) -3.3(22) - 62) 10(1--0)) -2) 74.8( 52)²
43.3(22
56.9(xz -22)
61) 0.1
81) 2 52)
00.(022 - -04((2-622) 6
62)
-1) -0.4(1) 1211-5)) 81) -2).
(93)
where x E RR,,an and C == f E 3.2. E (-0.45, 4.4)).
Problem 93 can be equivalently transformed to the min-max setting consistent with ours
minimize maximize
-f(x 8).
(94)
[0].250.5
The optimality solving problem 93 is measured by regret versus iteration
Regret(t) minimize f(x* - 8) minimize fxx - -)) |
(95)
[101|250.5
where minimize f(x - 5) = - 4.33 and x = 1-9599, 0.284) Bogunovic et al. (0118)
In Figure/AT] we compare the convergence performance and computation time of 2O-Min-Max with the BO based approach STABLEOPT proposed in BBognnovic et al. (2018). Here we choose the same initial point for both ZO-Min-Max and STABLEOPT. And we the same number of function queries per iteration for ZO-Min Min-Max (with 1) and STABLEOPT. We recall from ( that the larger q is, the more queries ZO-Min-Max takes. In our experiments, we present the best achieved regret to time and report the average performance of each method over 5 random trials. As we can see, 70-Min-Max more stable, with lower regret and less running time. Besides, as & becomes larger, Z0-Min-Max has faster convergence rate. We remark that BO is slow since learning the accurate GP model and solving the acquisition problem takes intensive computation cost.
120
ZO Min Max q=1
10a
ZO-Min-Max q=5
Zo Mo-MMn-Max q=10
STABLEOPT
10a
80
optimal
Total time
ZO Min Max q=1
Regret
ZO-Min-Max q=5
60
10a
Min
STABLEOPT
40
10
0-
10a
30 Number of iterations
Number of iterations
(a)
Figure A1: Comparison of Z0-Min-Max against STABLEOPT Bogunovic al. 2018 a) Convergence
performance; b) Computation time (scconds).
C EXPERIMENT SETUP ON POISONING ATTACK
In experiment, generate synthetic dataset that contains 1000 samples (z,, 4.). We randomly draw the feature vector 2, E 10000 from (O, and determine 4, - o +wa)) 0.5. Here choose 0" as the ground-truth model parameters,
1/(1 + e (x. and Vi (0 10 10-3) as random noise. We randomly split the generated dataset into the train- ing dataset Drr (70%) and the testing dataset Dr, (30%). We specify learning model as the
28

---

Under review as a conference paper at ICLR 2020
logistic regression model for binary classification. Thus, the loss function in problem
15] is
chosen as (x,(x, 0; Du)) := h(xx 0; (t.11) + h(0 8; Du.2), where Dtr = Dur,1 U U1.22. Du.,1 rep- resents the subset of the training dataset that will be poisoned, /uural/ [Dr| denotes the poisoning ratio, 1((x 0;
D) = - (1/1/D)) Li log(h(x, 0; 2.)) + (1 (4) log(1 11 0: (.)]) and
h(x, z. = 1/(1 + e (a. 00)) 9). In problem (55). we also set = 2 and A = 10 3. In Algo- rithm[] unless specified otherwise we choose the the mini-batch size 6 100, the number of random direction vectors 5, the learning rate = 0.02 and 8 0.05, and the total number of iterations 50000. We report the empirical results over independent trials with random initialization.
D ADDITIONAL EXPERIMENT RESULTS
In Figure A2 we show how the importance weights w of individual attack losses are learnt during ZO- Min-Max (vs. FO-Min-M Max). We can see that ZO-Min-Max takes into account different robustness levels of model-class pairs through the design of w.
0.40
Z0-Min Max, MIC1
FO.Min Max, MICI
ZO
FO Max,
0.35
20- Max. M2C1
FO-Min-Mas M2C1
70-Min- Max, M2C2
FO-Min-Max, M2C2
Weights
0.30
0.25
0.20
0.15
0.00
0.25
0.50 0.75
1.00 1.25 1.50 1.75 2.00
Number of iterations
Figure A2: Convergence of importance weights learnt from 70-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 with the attacking difficulty (in terms of required iterations for successful adversarial example) of using per-image non universal PGD attack (Madry 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 large amount of iterations to succeed 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
failure in ensemble attack success in ensemble attack
Number of iterations
10
103
102
10.
10a
M1C1
M2C1
M1C2
M2C2
Model-class pairs
Figure A3: Success failure of 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., À
29

---

Under review as a conference paper at ICLR 2020
However, this leads decrease in clean model accuracy (below 90% at À 1). This implies vobustness-accurasy tradeoff. continues to increase, both the clean and poisoned accuracy will decrease dramatically the training loss in (15) is less optimized.
0.9
Testing accuracy
0.8
0.6
ZO-Min-Max
FO-Min-Max
No Poison
0.5
10
10
10"
10a
Lambda
Figure A4: Empirical performance of 7O-Min-Max in design of poisoning attack: Testing accuracy versus regularization parameter
30


Reviews:
[{"review_id": "SylOV5CfqB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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). \n\nConsidering that the algorithm merely applies the zeroth-order gradient estimator to min-max problems, the algorithm itself only makes up a somewhat novel contribution. However, to the best of my knowledge, it has not been used in this context before and personally I find the algorithm quite appealing. In fact, due to its simplicity it is essentially something that anyone could implement from scratch. \n\nPerhaps a more important contribution is that the authors provide a fairly extensive convergence analysis, which is an important tool in analysing the algorithm and its properties. Unfortunately, it is not trivial to understand the presented convergence results and their practical implications (if any). For instance, equation (10), which is arguably one of the key equations in the paper, contains variables zeta, nu and P1, all of which depend on a number of other variables in a fairly complicated manner. The expression in (10) also contains terms that do not depend on T and it is not obvious how large these terms might be in practice (in the event that the assumptions are at least approximately true in a local region). Even though I am somewhat sceptical to the practical relevance of this convergence analysis, I recognise that it is an interesting and fascinating achievement that the authors have managed to provide a convergence analysis of an algorithm which is based on black-box min-max optimisation. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SkeqZkz-5S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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:\n\n1. 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. \n\n2. 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.\n\n3. 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkxtF2y29H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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 \n1) adversarial attack on ImageNet with deep networks, and \n2) black-box poisoning attack on logistic regression. The results show that ZO-MIN-MAX can provide satisfactory performance on these tasks.\n\nIn general a good paper with dense content, clear organization and writing. However, the experiment part does not seem truly convincing. \n1.\tWhat is the relationship between Eqn.(13) and the proposed ZO-MIN-MAX? It seem that in the experiment you compare using this loss ( Eqn.(13) ) against finite-sum loss, but both with ZO-MIN-MAX algorithm? In figure 1 and 2, I don’t see a competing method. So the point here is that the loss Eqn.(13)  is better, but not the proposed algorithm? I think you should compare different optimization algorithm under same loss, e.g. something like Eqn.(13)+ZO-MIN-MAX vs. Eqn.(13)+FO-MIN-MAX. This is not evident to show that ZO-MIN-MAX is better than other zero-th order methods.\n2.\tI would suggest comparing to more zeroth-order methods in the experiment.\n\nFrom the experiments I cannot tell whether ZO-MIN-MAX is good enough compared with other methods", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes convergence results for zeroth-order optimization.

One of the main complaints was that ZO has limited use in ML. I appreciate the authors' response that there are cases where gradients are not easily available, especially for black-box attacks.

However, I find the limited applicability an issue for ICLR and I encourage the authors to find a conference that is more suited to that work.
Decision: Reject