Title: A FRANK-WOLFE FRAMEWORK FOR EFFICIENT AND EFFECTIVE ADVERSARIAL ATTACKS

Abstract: Depending on how much information an adversary can access to, adversarial attacks can be classified as white-box attack and black-box attack. In both cases, optimization-based attack algorithms can achieve relatively low distortions and high attack success rates. However, they usually suffer from poor time and query complexities, thereby limiting their practical usefulness. In this work, we focus on the problem of developing efficient and effective optimization-based adversarial attack algorithms. In particular, we propose a novel adversarial attack framework for both white-box and black-box settings based on the non-convex Frank-Wolfe algorithm. We show in theory that the proposed attack algorithms are efficient with an O(1/
T ) convergence rate. The empirical results of attacking Inception V3 model and ResNet V2 model on the ImageNet dataset also verify the efficiency and effectiveness of the proposed algorithms. More specific, our proposed algorithms attain the highest attack success rate in both white-box and black-box attacks among all baselines, and are more time and query efficient than the stateof-the-art.

1. INTRODUCTION:

Deep Neural Networks (DNNs) have made many breakthroughs in different areas of artificial intelligence such as image classification (Krizhevsky et al., 2012; He et al., 2016a) , object detection (Ren et al., 2015; Girshick, 2015) , and speech recognition (Mohamed et al., 2012; Bahdanau et al., 2016) . However, recent studies show that deep neural networks can be vulnerable to adversarial examples (Szegedy et al., 2013; Goodfellow et al., 2015) -a tiny perturbation on an image that is almost invisible to human eyes could mislead a well-trained image classifier towards misclassification. Soon later this is proved to be not a coincidence: similar phenomena have been observed in other problems such as speech recognition (Carlini et al., 2016) , visual QA (Xu et al., 2017) , image captioning (Chen et al., 2017a) , machine translation (Cheng et al., 2018) , reinforcement learning (Pattanaik et al., 2018) , and even on systems that operate in the physical world (Kurakin et al., 2016) .

Depending on how much information an adversary can access to, adversarial attacks can be classified into two classes: white-box attack (Szegedy et al., 2013; Goodfellow et al., 2015) and black-box attack (Papernot et al., 2016a; Chen et al., 2017c) . In the white-box setting, the adversary has full access to the target model, while in the black-box setting, the adversary can only access the input and output of the target model but not its internal configurations. Among the approaches proposed for white-box and black-box attacks, optimization-based methods (Carlini & Wagner, 2017; Chen et al., 2017b; c; Ilyas et al., 2018) are most effective: they usually achieve relatively low distortions and high attack success rates. However, these methods are far from efficient. In the white-box setting, they need to solve constrained optimization problems (Carlini & Wagner, 2017) , and are usually significantly slower than Fast Gradient Sign Method (FGSM) (Goodfellow et al., 2015) or Iterative FGSM (I-FGM) (Kurakin et al., 2016) . Applying those methods with one or two examples are fine, yet in the case of attacking hundreds of thousands examples, e.g. in adversarial training (Kurakin et al., 2016; Madry et al., 2018) , this is far from satisfactory.

In the black-box setting, it becomes even more severe since they need to make gradient estimations (Chen et al., 2017c) . Therefore, a large number of queries are needed for them to perform a successful attack, especially when the data dimension is large. For example, attacking a 299×299×3 Imagenet image may take them hundreds of thousands of queries. This significantly limits their prac-tical usefulness since they can be easily defeated by limiting the number of queries that an adversary can make to the target model.

In this study, we aim to examine the following questions in this study:

Can we improve the efficiency of the optimization-based attack algorithms? In other words, can we use less time and queries to conduct adversarial attacks?

In this work, we provide an affirmative answer to this question by proposing an efficient Frank-Wolfe optimization framework for both white-box and black-box attacks. In summary, we make the following main contributions:

• We propose a novel Frank-Wolfe based adversarial attack framework. The white-box attack algorithm is an iterative first-order method which admits the fast gradient sign method (FGSM) as the one-step special case. And the corresponding black-box attack algorithm adopts zeroth-order optimization with two sensing vector options (either from the Euclidean unit sphere or from the standard Gaussian distribution) provided. • We show that the proposed white-box and black-box attack algorithms enjoy an O(1/ √ T ) convergence rate. Also we show that the query complexity of the proposed black-box attack algorithm is linear in data dimension d.

• Our empirical results on attacking Inception V3 model with the ImageNet dataset show that (i) the proposed white-box attack algorithm is more efficient than all the baseline whitebox algorithms evaluated here, and (ii) the proposed black-box attack algorithm is highly efficient and is also the only one algorithm that achieves a 100% attack success rate.

2. RELATED WORK:

There is a large body of work on adversarial attacks. In this section, we review the most relevant work in both white-box and black-box attack settings, as well as the non-convex Frank-Wolfe optimization.

White-box Attacks: Szegedy et al. (2013) proposed to use box-constrained L-BFGS algorithm for conducting white-box attacks. Goodfellow et al. (2015) proposed the Fast Gradient Sign Method (FGSM) based on linearization of the network as a simple alternative to L-BFGS. Kurakin et al. (2016) proposed to iteratively perform one-step FGSM (Goodfellow et al., 2015) algorithm and clips the adversarial point back to the distortion limit after every iteration. It is called Basic Iterative Method (BIM) or I-FGM in the literature. Madry et al. (2018) showed that for the L ∞ norm case, BIM/I-FGM is equivalent to Projected Gradient Descent (PGD), which is a standard tool for constrained optimization. Papernot et al. (2016b) proposed JSMA to greedily attack the most significant pixel based on the Jacobian-based saliency map. Moosavi-Dezfooli et al. (2016) proposed attack methods by projecting the data to the closest separating hyperplane. Carlini & Wagner (2017) introduced the so-called CW attack by proposing multiple new loss functions for generating adversarial examples. Chen et al. (2017b) followed CW's framework and use an Elastic Net term as the distortion penalty.

Black-box Attacks: One popular family of black-box attacks (Hu & Tan, 2017; Papernot et al., 2016a; 2017) is based on the transferability of adversarial examples (Liu et al., 2018; Bhagoji et al., 2017) , where an adversarial example generated for one DNN may be reused to attack other neural networks. This allows the adversary to construct a substitute model that mimics the targeted DNN, and then attack the constructed substitute model using white-box attack methods. However, this type of attack algorithms usually suffer from large distortions and relatively low success rates (Chen et al., 2017c) . To address this issue, Chen et al. (2017c) proposed the Zeroth-Order Optimization (ZOO) algorithm that extends the CW attack to the black-box setting and uses a zeroth-order optimization approach to conduct the attack. Although ZOO achieves much higher attack success rates than the substitute model-based black-box attacks, it suffers from a poor query complexity since its naive implementation requires to estimate the gradients of all the coordinates (pixels) of the image. To improve its query complexity, several approaches have been proposed. For example, Tu et al. (2018) introduces an adaptive random gradient estimation algorithm and a well-trained Autoencoder to speed up the attack process. Ilyas et al. (2018) and Liu et al. (2018) improved ZOO's query complexity by using Natural Evolutionary Strategies (NES) (Wierstra et al., 2014; Salimans et al., 2017) and active learning, respectively.

Non-convex Frank-Wolfe Algorithms: The Frank-Wolfe algorithm (Frank & Wolfe, 1956) , also known as the conditional gradient method, is an iterative optimization method for constrained optimization problem. Jaggi (2013) revisited Frank-Wolfe algorithm in 2013 and provided a stronger and more general convergence analysis in the convex setting. Yu et al. (2017) proved the first convergence rate for Frank-Wolfe type algorithm in the non-convex setting. Lacoste-Julien (2016) provided the convergence guarantee for Frank-Wolfe algorithm in the non-convex setting with adaptive step sizes. Reddi et al. (2016) further studied the convergence rate of non-convex stochastic Frank-Wolfe algorithm in the finite-sun optimization setting. Very recently, Staib & Jegelka (2017) proposed to use Frank-Wolfe for distributionally robust training (Sinha et al., 2018) . Balasubramanian & Ghadimi (2018) proved the convergence rate for zeroth-order nonconvex Frank-Wolfe algorithm using one-side finite difference gradient estimator with standard Gaussian sensing vectors.

3. METHODOLOGY:

3.1 NOTATIONS Throughout the paper, scalars are denoted by lower case letters, vectors by lower case bold face letters and sets by calligraphy upper cae letters. For a vector x ∈ R d , we denote the L p norm of x by x p = (

d i=1 x p i ) 1/p . Specially, for p = ∞, the L ∞ norm of x by x ∞ = max d i=1 |θ i |.

We denote P X (x) as the projection operation of projecting vector x into the set X .

3.2. PROBLEM FORMULATION:

According to the attack purposes, attacks can be divided into two categories: untargeted attack and targeted attack. In particular, untargeted attack aims to turn the prediction into any incorrect label, while the targeted attack, which is considerably harder, requires to mislead the classifier to a specific target class. In this work, we follow the literature (Carlini & Wagner, 2017; Ilyas et al., 2018) and focus on the strictly harder targeted attack setting. It is worth noting that our proposed algorithm can be extended to untargeted attack straightforwardly.

Let us define f (•) as the classification loss function of the targeted DNN. For targeted attacks, we aim to learn an adversarial example x that is close enough to the original input x ori and can be misclassified to the target class y tar . The corresponding optimization problem1 is defined as: min x f (x, y tar ) subject to xx ori p ≤ .

(3.1) Evidently, the constraint set X := {x | xx ori p ≤ } is a bounded convex set when p ≥ 1.

Normally, p = 2 and p = ∞ are used to measure the distortions xx ori p , resulting in L 2 attack model and L ∞ attack model respectively. In this work, we study both attack models. In the sequel, since we mainly focus on the targeted attack case, we use f (x) to denote f (x, y tar ) for simplicity.

3.3. FRANK-WOLFE WHITE-BOX ATTACKS:

Frank-Wolfe algorithm (Frank & Wolfe, 1956) , also known as the conditional gradient descent, is a popular optimization tool for constrained optimization. Different from PGD that first performs gradient descent followed by a projection step at each iteration, Frank-Wolfe algorithm calls a Linear Minimization Oracle (LMO) over the the constraint set X at each iteration, i.e.,

LMO ∈ argmin v∈X v, ∇f (x t ) .

The LMO can be seen as the minimization of the first-order Taylor expansion of f (•) at point x t :

min v∈X f (x t ) + v -x t , ∇f (x t ) .

By calling LMO, Frank Wolfe solves the linear problem in X and then perform weighted average with previous iterate to obtain the final update formula.

We present our proposed Frank-Wolfe white-box attack algorithm in Algorithm 1, which is built upon the original Frank-Wolfe algorithm. The key difference between Algorithm 1 and the standard Frank-Wolfe algorithm is in Line 4, where the LMO is called over a slightly relaxed constraint set 

X λ := {x | x -x ori p ≤ λ } with λ ≥ 1, instead of the original constraint set X . When λ = 1, set X λ reduces to X ,

v t = argmin v∈X λ v, ∇f (x t ) // LMO 5: d t = v t -x t 6: x t+1 = x t + γ t d t 7:

if λ > 1 then 8:

x t+1 = P X (x t+1 )

9:

end if 10: end for 11: output: x T

The LMO solution itself can be expensive to obtain in general. Fortunately, applying Frank-Wolfe to solve (3.1) actually gives us a closed-form LMO solution. We provide the solutions of LMO (Line 4 in Algorithm 1) for L 2 norm and L ∞ norm cases respectively:

v t = - λ • ∇f (x t ) ∇f (x t ) 2 + x ori , (L 2 norm) v t = -λ • sign(∇f (x t )) + x ori . (L ∞ norm)

The derivation can be found in the supplemental materials.

Note that when T = 1, λ = 1, substituting the above LMO solutions into Algorithm 1 yields the final update of

x 1 = x 0 -γ t • ∇f (x t )

, which reduces to FGSM2 when γ t = 1. Similar derivation also applies to L 2 norm case. Therefore, just like PGD, our proposed Frank-Wolfe white-box attack also includes FGSM (FGM) as a one-step special instance.

3.4. FRANK-WOLFE BLACK-BOX ATTACKS:

Next we consider the black-box setting, where we cannot perform back-propagation to calculate the gradient of the loss function anymore. Instead, we can only query the DNN system's outputs with specific inputs. To clarify, here the output refers to the logit layer's output (confidence scores for classification), not the final prediction label. The label-only setting is doable under our framework, but will incur extra difficulty such as designing new loss functions. For simplicity, here we consider the confidence score output.

We propose a zeroth-order Frank-Wolfe based algorithm to solve this problem. Algorithm 2 show our proposed Frank-Wolfe black-box attack algorithm. The key difference between our proposed black-box attack and white-box attack is one extra gradient estimation step, which is presented in Line 4 in Algorithm 2. Also note that for the final output, we provide two options. While option II is the common choice in practice, option I is also provided for the ease of theoretical analysis.

As many other zeroth-order optimization algorithms (Shamir, 2017; Flaxman et al., 2005) , Algorithm 3 uses symmetric finite differences to estimate the gradient and therefore, gets rid of the dependence on back-propagation in white-box setting. Different from Chen et al. ( 2017c), here we do not utilize natural basis as our sensing vectors, instead, we provide two options: one is to use vectors uniformly sampled from Euclidean unit sphere and the other is to use vectors uniformly sampled from standard multivarite Gaussian distribution. This will greatly improve the gradient estimation efficiency comparing to sensing with natural basis as such option will only be able to estimate one coordinate of the gradient vector per query. In practice, both options here provide us competitive experimental results. It is worth noting that NES method (Wierstra et al., 2014) with antithetic sampling (Salimans et al., 2017) q t = ZERO ORD GRAD EST(x t ) // Algorithm 3 5:

v t = argmin v∈X λ v, q t 6:

d t = v t -x t 7: x t+1 = x t + γ t d t 8:

if λ > 1 then 9:

x t+1 = P X (x t+1 )

10:

end if 11: end for 12: Option I: x a is uniformly random chosen from {x t } T t=1 13: Option II: x a = x T 14: output: x a Algorithm 3 Zeroth-Order Gradient Estimation (ZERO ORD GRAD EST)

1: parameters: number of gradient estimation samples b, sampling parameter δ t ; 2: q = 0 3: for i = 1, . . . , b do 4:

Option I: Sample u i uniformly from the Euclidean unit sphere with

u i 2 = 1 q = q + d 2δtb f (x t + δ t u i ) -f (x t -δ t u i ) u i 5:

Option II: Sample u i uniformly from the standard Gaussian distribution N (0,

I) q = q + 1 2δtb f (x t + δ t u i ) -f (x t -δ t u i ) u i 6: end for 7: output: q 4 MAIN THEORY

In this section, we establish the convergence guarantees for our proposed Frank-Wolfe adversarial attack algorithms described in Section 3. First, we introduce the convergence criterion for our Frank-Wolfe adversarial attack framework.

4.1. CONVERGENCE CRITERION:

The loss function for common DNN models are generally nonconvex. In addition, (3.1) is a constrained optimization. For such general nonconvex constrained optimization, we typically adopt the Frank-Wolfe gap as the convergence criterion (since gradient norm of f is no longer a proper criterion for constrained optimization problems):

g(x t ) = max x∈X x -x t , -∇f (x t ) .

Note that for the Frank-Wolfe gap, we always have g(x t ) ≥ 0 and x t is a stationary point for the constrained optimization problem if and only if g(x t ) = 0. Also the Frank-Wolfe gap is affine invariant and do not tie to any specific choice of norm, which makes itself a perfect convergence criterion for Frank-Wolfe based algorithms.

4.2. CONVERGENCE GUARANTEE FOR FRANK-WOLFE WHITE-BOX ATTACK:

Before we are going to provide the convergence guarantee of Frank-Wolfe white-box attack (Algorithm 1), we introduce the following assumptions that are essential to the convergence analysis. Assumption 4.1. Function f (•) is L-smooth with respect to x, i.e., for any x, x , it holds that

f (x ) ≤ f (x) + ∇f (x) (x -x) + L 2 x -x 2 2 .

Assumption 4.1 is a standard assumption in nonconvex optimization, and is also adopted in other Frank-Wolfe literature such as Lacoste-Julien (2016); Reddi et al. (2016) . Note that even though the smoothness assumption does not hold for general DNN models, a recent study (Santurkar et al., 2018) shows that batch normalization that is used in many modern DNNs such as Inception V3 model, actually makes the optimization landscape significantly smoother3 . This justifies the validity of Assumption 4.1. Assumption 4.2. Set X is bounded with diameter D, i.e., xx 2 ≤ D for all x, x ∈ X .

Assumption 4.2 implies that the input space is bounded. For common tasks such as image classification, given the fact that images have bounded pixel range and is a small constant, this assumption trivially holds.

Now we present the theorem, which characterizes the convergence rate of our proposed Frank-Wolfe white-box adversarial attack algorithm presented in Algorithm 1.

Theorem 4.3. Under Assumptions 4.1 and 4.2, let

γ t = γ = 2(f (x 0 ) -f (x * ))/(LD 2 T ), denote g T = min 1≤k≤T g(x k

) where {x k } T k=1 are iterates in Algorithm 1 with λ = 1, we have:

g T ≤ LD 2 (f (x 0 ) -f (x * )) 2T ,

where x * is the optimal solution to (3.1). Remark 4.4. Theorem 4.3 suggests that our proposed Frank-Wolfe white-box attack algorithm achieves a O(1/ √ T ) rate of convergence. Note that similar result has been proved in Lacoste-Julien (2016) under a different choice of step size.

4.3. CONVERGENCE GUARANTEE FOR FRANK-WOLFE BLACK-BOX ATTACK:

Next we analyze the convergence of our proposed Frank-Wolfe black-box adversarial attack algorithm presented in Algorithm 2.

In order to prove the convergence of our proposed Frank-Wolfe black-box attack algorithm, we need the following additional assumption that ∇f (0) 2 is bounded.

Assumption 4.5. Gradient of f (•) at zero point ∇f (0) satisfies max y ∇f (0) 2 ≤ C g .

Following the analysis in Shamir (2017) , let f δ (x) = E u [f (x + δu)], which is the smoothed version of f (x). This smoothed function value plays a central role in our theoretical analysis, since it bridges the finite difference gradient approximation with the actual gradient. The following lemma shows this relationship. Lemma 4.6. For the gradient estimator q t in Algorithm 3, its expectation and variance satisfy

E[q t ] = ∇f δ (x t ), E q t -E[q t ] 2 2 ≤ 1 b 2d(C g + LD) 2 + 1 2 δ 2 t L 2 d 2 .

Now we are going to present the theorem, which characterizes the convergence rate of Algorithm 2.

Theorem 4.7. Under Assumptions 4.1, 4.2 and 4.5, let

γ t = γ = 2(f (x 0 ) -f (x * ))/(LD 2 T ), b = T d and δ t = 2/T d 2

, suppose we use Option I in Algorithm 2 and option II for Algorithm 3, then the output x a from Algorithm 2 with λ = 1 satisfies:

E[g(x a )] ≤ D √ 2T L(f (x 0 ) -f (x * )) + 2(L + C g + LD) ,

where x * is the optimal solution to (3.1).

Remark 4.8. Theorem 4.7 suggests that Algorithm 2 also enjoys a O(1/ √ T ) rate of convergence. In terms of query complexity, the total number of queries needed is T b = T 2 d, which is linear in the data dimension d. In fact, in the experiment part, we observed that this number can be substantially smaller than d, e.g., b = 25, which is much lower than the theorem suggests. Note that although we only prove for option I in Algorithm 3, our result can be readily extended to Option II (the Gaussian sensing vector case).

5. EXPERIMENTS:

In this section, we present the experimental results for our proposed Frank-Wolfe attack framework against other state-of-the-art adversarial attack algorithms in both white-box and black-box settings. All of our experiments are conducted on Amazon AWS p3.2xlarge servers which come with Intel Xeon E5 CPU and one NVIDIA Tesla V100 GPU (16G RAM). All experiments are implemented in Tensorflow platform version 1.10.0 within Python 3.6.4.

5.1. EVALUATION SETUP AND METRICS:

We test the attack effectiveness of all algorithms by evaluating on a pre-trained Inception V3 model (Szegedy et al., 2016) and a ResNet V2 50 (He et al., 2016b) model that are trained on ImageNet dataset (Deng et al., 2009) . The pre-trained Inception V3 model is reported to have a 78.0% top-1 accuracy and a 93.9% top-5 accuracy. The pre-trained ResNet V2 model is reported to have a 75.6% top-1 and a 92.8% top-5 accuracy. We randomly choose 500 images from the ImageNet validation set that are verified to be correctly classified by the pre-trained model and also randomly choose a target class for each image. Each image has a dimension of 299 × 299 × 3 and we test all attack algorithms through the same randomly chosen data samples and target labels.

We test for both L 2 norm based and L ∞ norm based attacks. In the white-box setting, we perform binary search / grid search for the best distortion parameter ( in our formulation and c in CW's regularized formulation). In the black-box setting, for L 2 norm based attack, we set = 5 and for L ∞ based attack, we set = 0.05. For white-box attack, we restrict a maximum of 1, 000 iterations per attack for each method. And for black-box attack, we set a maximum query limit of 500, 000 per attack per image for each method.

For all algorithms, we stop the algorithm when a successful attack is found. For our proposed blackbox attack, we use option II in Algorithm 2 and test both options in Algorithm 3. We set the number of gradient estimation samples b = 25 for Algorithm 2. More detailed description on parameter settings can be found in the supplemental materials. We evaluate the final performance through attack success rate where the success is defined as making the classifier output the exact target class label (not any incorrect labels). We also measure average attack time per image, average distortion (only on successful attacked samples) and average number of queries needed (only for black-box attack) per image. For a fair time comparison, even though some of the algorithms including ours can be written in batch form (attack multiple images at one time), all algorithms are set to attack one image at a time.

Due to page limit, we leave all experimental results on ResNet V2 model in the supplemental materials.

5.2. BASELINE METHODS:

We compare the proposed algorithms with several state-of-the-art baseline algorithms. Specifically, we compare the proposed white-box attack algorithm with4 (i) PGD (Madry et al., 2018) (which is essentially I-FGM (Kurakin et al., 2016) ), (ii) CW attack (Carlini & Wagner, 2017 ) and (iii) EAD attack (Chen et al., 2017b) . We compare the proposed black-box attack algorithm with (i) ZOO attack (Chen et al., 2017c) and (ii) NES-PGD attack (Ilyas et al., 2018) .

5.3. WHITE-BOX ATTACK EXPERIMENTS:

In this subsection, we present the white-box attack experiments on Inception V3 model. Tables 1 and 2 present our experimental results for L 2 norm and L ∞ norm based white-box attacks respectively. As we can observe from the tables, the attack success rate is 100% for every method. For the other baselines in the L 2 norm case, CW method achieves the smallest average distortion, yet it comes with an expansive time cost. EAD method does not have either time advantage or distortion advantage in this experiment, probably due to its different motivation in attacking. PGD has moderate average distortion, yet it also costs quite some time to finish the attack. On the other hand, our proposed algorithm achieves the shortest attack time with moderate distortion. It significantly reduces the time complexity needed for attacking data with large dimensionality. For the L ∞ norm case, CW method takes significantly longer time and does not perform very well on average distortion either. In Figure 1 , we also examine the effect of λ in our proposed Frank-Wolfe white-box attack algorithm. We plot the objective loss function value of attacking one example against the number of iterations for both L 2 and L ∞ based white-box attack on Inception V3 model. From the plot, we can see that larger λ indeed leads to faster convergence. 

5.4. BLACK-BOX ATTACK EXPERIMENTS:

In this subsection, we present the black-box attack experiments on Inception V3 model. For blackbox attacks, attack success rate, time and number of queries needed are more meaningful evaluation metrics than distortion distances. Therefore, we omit all the grid search / binary search steps that are used in the white-box setting since extra time / queries are needed for finding parameters that can obtain better distortion distances.

Tables 3 and 4 present our experimental results for L 2 norm and L ∞ norm based black-box attacks respectively. For ZOO method, note that it only has the L 2 norm version and it follows CW's framework and thus uses different loss function and problem formulation (cannot exactly control the adversarial example to be within the distortion limit, we manage to keep the average distortion around for ZOO while other methods have average distortions very close to ). Furthermore, we can observe that ZOO is quite slow in this task. Attack on a single image can take up to 2 hours for ZOO and it is only able to achieve a 74.8% success rate (compared with the 88.9% success rate in the original paper, we think the main reason is the query limit here is only half of the query limit 

6. CONCLUSIONS:

In this work, we propose a Frank-Wolfe framework for efficient and effective adversarial attacks.

Our proposed white-box and black-box attack algorithms enjoy an O(1/ √ T ) rate of convergence, and the query complexity of the proposed black-box attack algorithm is linear in data dimension d. Finally, our empirical study on attacking Inception V3 model with ImageNet dataset yields a 100% attack success rate for our proposed algorithms, even in the setting of black-box attack.

A LINEAR MINIMIZATION ORACLE (LMO) SOLUTIONS:

Denote u = (v -x ori )/(λ ), the linear minimization problem can be written as

min v-xori p≤λ v, ∇f (x t ) = min u p ≤1 λ • u, ∇f (x t ) = max u p ≤1 λ • u, -∇f (x t ) = λ • ∇f (x t ) p * ,

where • p * denotes the dual norm of • p . For p = 2 case, we have

(v -x ori )/(λ ), -∇f (x t ) = ∇f (x t ) 2 . It immediately implies that v = - λ • ∇f (x t ) ∇f (x t ) 2 + x ori .

For p = ∞ case, we have

(v -x ori )/(λ ), -∇f (x t ) = ∇f (x t ) 1 . It immediately implies that v = -λ • sign(∇f (x t )) + x ori .

For the ease of comparison, we show the full update formula (before final projection step) for our algorithm. In detail, for p = ∞ case, our algorithm takes the following update formulate:

x t+1 = (1 -γ t )x t + γ t v t = (1 -γ t )x t -λγ t • sign(∇f (x t )) + γ t • x ori = x t -λγ t • sign(∇f (x t )) -γ t (x t -x ori ),

and for p = 2 case, it takes

x t+1 = x t -λγ t • ∇f (x t ) ∇f (x t ) 2 -γ t (x t -x ori ).

Compared with PGD, the full update (before final projection step) of Frank-Wolfe white-box attack includes an extra parameter λ before the normalized gradient, as well as an extra term (x t -x ori ). This difference makes the behavior of Frank-Wolfe based attacks different from that of PGD based attacks.

B PROOF OF THE MAIN THEORY IN SECTION 4:

B.1 PROOF OF THEOREM 4.3

Proof. For simplicity, we denote f (x t ) by f (x t ) for the rest of the proof. First by Assumption 4.1, we have

f (x t+1 ) ≤ f (x t ) + ∇f (x t ) (x t+1 -x t ) + L 2 x t+1 -x t 2 2 = f (x t ) + γ∇f (x t ) (v t -x t ) + Lγ 2 2 v t -x t 2 2 ≤ f (x t ) + γ∇f (x t ) (v t -x t ) + LD 2 γ 2 2 ,

where the last inequality uses the bounded domain condition in Assumption 4.2. Note that by definition of the Frank-Wolfe gap, we have

f (x t+1 ) ≤ f (x t ) -γg(x t ) + LD 2 γ 2 2 .

Under review as a conference paper at ICLR 2019 Summation over t of the above inequality, we obtain

f (x T ) ≤ f (x 0 ) - T -1 k=0 γg(x k ) + T LD 2 γ 2 2 ≤ f (x 0 ) -γT g T + T LD 2 γ 2 2 ,

where the second inequality follows from the definition of g t . Note that by optimality we easily have f (x t+1 ) ≥ f (x * ). Rearrange the above inequality we have

g T ≤ f (x 0 ) -f (x * ) T γ + LD 2 γ 2 ≤ LD 2 (f (x 0 ) -f (x * )) 2T ,

where the second inequality is achieved when

γ = 2(f (x 0 ) -f (x * ))/(LD 2 T ).

B.2 PROOF OF LEMMA 4.6

Proof. For simplicity we denote f (•) by f (•) for the rest of the proof. Let us denote

ψ i = d 2δtb f (x t + δ t u i ) -f (x t -δ t u i ) u i .

For the first part, we have

E[ψ i ] = E u d 2δ t b f (x t + δ t u i ) -f (x t -δ t u i ) u i = E u d 2δ t b f (x t + δ t u i )u i + E u d 2δ t b f (x t -δ t u i )(-u i ) = E u d δ t b f (x t + δ t u i )u i = 1 b ∇f δ (x t ),

where the third equality holds due to symmetric property of u i and the last equality follows from Lemma 4.1(a) in Gao et al. (2018) . Therefore, we have

E[q t ] = E b i=1 ψ i = ∇f δ (x t ).

For second part, note that ψ i 's are independent from each other due to the independence of u i , we have

E q t -E[q t ] 2 2 = E b i=1 ψ i -Eψ i 2 2 = b i=1 E ψ i -Eψ i 2 ≤ b i=1 E ψ i 2 .

Now take a look at E ψ i 2 :

E ψ i 2 = E u d 2δ t b f (x t + δ t u i ) -f (x t ) + f (x t ) -f (x t -δ t u i ) u i 2 2 ≤ 1 2b 2 E u d δ t f (x t + δ t u i ) -f (x t ) u i 2 2 + 1 2b 2 E u d δ t f (x t ) -f (x t -δ t u i ) u i 2 2 = 1 b 2 E u d δ t f (x t + δ t u i ) -f (x t ) u i 2 2 ≤ 1 b 2 2d ∇f (x t ) 2 2 + 1 2 δ 2 t L 2 d 2 ,

where the first inequality is due to the fact that (a + b) 2 ≤ 2a 2 + 2b 2 , the second equality follows from the symmetric property of u i and the last inequality is by Lemma 4.1(b) in Gao et al. (2018) . Also note that by Assumption 4.1 and 4.5 we have ∇f

(x t ) 2 2 ≤ ( ∇f (0)) 2 + L x t 2 ) 2 ≤ (C g + LD) 2 .

Combine all above results, we obtain

E q t -E[q t ] 2 2 ≤ 1 b 2d(C g + LD) 2 + 1 2 δ 2 t L 2 d 2 .

B.3 PROOF OF THEOREM 4.7

Proof. For simplicity we denote f (x t ) by f (x t ) for the rest of the proof. First by Assumption 4.1, we have

f (x t+1 ) ≤ f (x t ) + ∇f (x t ) (x t+1 -x t ) + L 2 x t+1 -x t 2 2 = f (x t ) + γ∇f (x t ) (v t -x t ) + Lγ 2 2 v t -x t 2 2 ≤ f (x t ) + γ∇f (x t ) (v t -x t ) + LD 2 γ 2 2 = f (x t ) + γq t (v t -x t ) + γ(∇f (x t ) -q t ) (v t -x t ) + LD 2 γ 2 2 ,

where the second inequality uses the bounded domain condition in Assumption 4.2. Now define an auxiliary quantity:

v t = argmin v∈X v, ∇f (x t ) .

According to the definition of g(x t ), this immediately implies

g(x t ) = v t , ∇f (x t ) .

Then we further have

f (x t+1 ) ≤ f (x t ) + γq t ( v t -x t ) + γ(∇f (x t ) -q t ) (v t -x t ) + LD 2 γ 2 2 = f (x t ) + γ∇f (x t ) ( v t -x t ) + γ(∇f (x t ) -q t ) (v t -v t ) + LD 2 γ 2 2 = f (x t ) -γg(x t ) + γ(∇f (x t ) -q t ) (v t -v t ) + LD 2 γ 2 2 ≤ f (x t ) -γg(x t ) + γD • ∇f (x t ) -q t 2 + LD 2 γ 2 2 ,

where the first inequality follows from the optimally of v t in Algorithm 2 and the last inequality holds due to Cauchy-Schwarz inequality. Take expectations for both sides of the above inequality, we have

E[f (x t+1 )] ≤ E[f (x t )] -γE[g(x t )] + γD • E ∇f (x t ) -q t 2 + LD 2 γ 2 2 ≤ E[f (x t )] -γE[g(x t )] + γD • ∇f (x t ) -E[q t ] 2 + E q t -E[q t ] 2 + LD 2 γ 2 2 , ≤ E[f (x t )] -γE[g(x t )] + γD • ∇f (x t ) -E[q t ] 2 + E q t -E[q t ] 2 2 + LD 2 γ 2 2 ≤ E[f (x t )] -γE[g(x t )] + γD • ∇f (x t ) -∇f δ (x t ) 2 + 4d(C g + LD) 2 + δ 2 t L 2 d 2 2b + LD 2 γ 2 2 , ≤ E[f (x t )] -γE[g(x t )] + γD • δ t Ld 2 + 2 √ d(C g + LD) + δ t Ld √ 2b + LD 2 γ 2 2 ,

where the second inequality follows from triangle inequality, the third inequality is due to Jenson's inequality and the last inequality holds due to Lemma 4.6.

Summation over t of the above inequality, we obtain

E[f (x T )] ≤ f (x 0 ) - T -1 t=0 γE[g(x t )] + γDT δ t Ld 2 + 2 √ d(C g + LD) + δ t Ld √ 2b + T LD 2 γ 2 2 ≤ f (x 0 ) -γT g a + γDT δ t Ld 2 + 2 √ d(C g + LD) + δ t Ld √ 2b + T LD 2 γ 2 2 ,

where the second inequality follows from the definition of g a . Note that by the zeroth-order optimality, we have f (x t+1 ) ≥ f (x * ). Rearrange the above inequality we obtain

E[g a ] ≤ f (x 0 ) -f (x * ) T γ + LD 2 γ 2 + D δ t Ld 2 + 2 √ d(C g + LD) + δ t Ld √ 2b ≤ D √ 2T L(f (x 0 ) -f (x * )) + 2(L + C g + LD) ,

where the second inequality is achieved by setting

γ = 2(f (x 0 ) -f (x * ))/(LD 2 T ), b = T d and δ t = 2/T d 2 .

C PARAMETERS SETTINGS FOR SECTION 5

For Frank-Wolfe white-box attack algorithm, we list the parameters we use in Section 5 at Table 5 . Similarly, for Frank-Wolfe black-box attack algorithm, we also list the parameters we use in Section 5 at Table 6 . We also list the hyperparameters we use for baseline algorithms. Specifically, for PGD, we set a step size of 0.05 for L 2 case and 0.01 for L ∞ case. For CW, we set a step size of 0.002 for L 2 case step size of 0.005 for L ∞ case. The confidence is set to 0 and we perform 10 times binary search for the constant starting from 0.01 (L 2 case) and 0.001 (L ∞ case). For EAD, we use a step size of 0.01 and the same binary search strategy as CW and β is set to be 0.001. In terms of black-box experiments, for ZOO, we set a step size of 0.01 and the initial constant is set to be 1 without binary search to achieve better query complexity. For NES-PGD, we set a step size of 0.3 for L 2 case and 0.01 for L ∞ case. Tables 9 and 10 present our experimental results for L 2 norm and L ∞ norm based black-box attacks respectively. We still set = 5 for L 2 case and = 0.05 for L ∞ case.

For the L 2 norm case, ZOO method barely succeeds due to the strict query limit of 50, 00 while it typically requires over 10 6 queries to attack successfully. Our proposed Frank-Wolfe black-box attacks, on the other hand, achieve nearly 60% attack success rate under such a stringent query budget. For the L ∞ norm case, both NES-PGD method and ours achieve over 90% success rate. Even though they share similar average attack time and average number of queries needed, our Frank-Wolfe based methods still achieve the best in terms of all three evaluation metrics.

Figure 3 illustrates the attack success rate against the number of queries plot for different algorithms in both L 2 norm and L ∞ norm based black-box attack on ResNet V2 model. Note that here we have a query limit of 50, 000, which is especially hard for the L 2 norm case. As we can see from the Figure 3 , our proposed Frank-Wolfe black-box attack algorithm (both options) achieves the best performance (highest attack success rate and smallest queries needed for achieving the same success rate).

D.3 VISUALIZATION EXAMPLES:

For the completeness, we also provide some visual illustrations on the adversarial examples generated by various algorithms. 

:

Note that there is usually an additional constraint on the input variable x, e.g., x ∈ [0, 1] n for normalized image inputs.

The extra clipping operation in FGSM is to project to the additional box constraint for image classification task. We will also need this clipping operation at the end of each iteration for specific tasks such as image classification.

The original argument inSanturkar et al. (2018) refers to the smoothness with respect to each layer's parameters. Note that the first layer's parameters are in the mirror position (in terms of backpropagation) as the network inputs. Therefore, the argument inSanturkar et al. (2018) can also be applied here with respect to the network inputs.

We did not compare with FGM (FGSM)(Goodfellow et al., 2015) since it basically has zero success rate for targeted attack on Inception V3 or ResNet V2 models.

Figures and Tables:

Figure 1: Loss against the number of iterations plot for PGD and FW algorithms in both L 2 norm and L ∞ norm based white-box attacks on Inception V3 model.

Figure 4 shows some adversarial examples generated through different L 2 norm based white-box attacks. Figure 5 shows some adversarial examples generated through different L ∞ norm based black-box attacks.

Figure 4: Sample adversarial examples generated through different L 2 norm based white-box attacks. Left side labels denote the original class label and right side labels denote the target class label.

Figure 5: Sample adversarial examples generated through different L ∞ norm based black-box attacks. Left side labels denote the original class label and right side labels denote the target class label.

and Algorithm 1 reduces to standard Frank Wolfe. We argue that this modification makes our algorithm more general, and gives rise to better attack results. Algorithm 1 Frank-Wolfe White-box Attack Algorithm

Table content: <table/>

Comparison of L 2 norm based white-box attacks on Inception V3 model with = 5. We report attack success rate, average time and average distortion.

Table content: <table><tr><td colspan="4">METHODS SUCCESS RATE (%) AVERAGE TIME (s) AVERAGE DISTORTION</td></tr><tr><td>PGD</td><td>100.0</td><td>143.2</td><td>0.74</td></tr><tr><td>CW</td><td>100.0</td><td>169.9</td><td>0.57</td></tr><tr><td>EAD</td><td>100.0</td><td>167.8</td><td>1.09</td></tr><tr><td>FW-White</td><td>100.0</td><td>50.6</td><td>0.85</td></tr></table>

Comparison of L ∞ norm based white-box attacks on Inception V3 model with = 0.05. We report attack success rate, average time and average distortion. This is largely due to the original CW was designed for L 2 norm attack, and in order to apply it to L ∞ norm attack, special design is needed, which sacrifices its performance in terms of runtime. Again, our proposed white-box attack algorithm achieves the shortest average attack time and a moderate average distortion.

Table content: <table><tr><td colspan="4">METHODS SUCCESS RATE (%) AVERAGE TIME (s) AVERAGE DISTORTION</td></tr><tr><td>PGD</td><td>100.0</td><td>39.1</td><td>0.0027</td></tr><tr><td>CW</td><td>100.0</td><td>745.2</td><td>0.0071</td></tr><tr><td>FW-White</td><td>100.0</td><td>13.7</td><td>0.0034</td></tr></table>

Attack success rate against the number of queries plot for different black-box attack algorithms in both L 2 norm L ∞ norm cases on Inception V3 model. in the original paper). NES-PGD method, while greatly improving ZOO's performance, still cannot achieve 100% success rate in both attack models and takes relatively more time and queries. In sharp contrast, our proposed Frank-Wolfe black-box attacks (both option I and option II) achieve the highest success rate in both L 2 norm and L ∞ norm based black-box attacks and further largely improve the attack efficiency.

Table content: <table><tr><td/><td>1.0</td><td/><td/><td/><td/><td>1.0</td><td/></tr><tr><td>Attack Success Rate</td><td>0.0 0.2 0.4 0.6 0.8</td><td>0</td><td>100000</td><td>200000 Queries 300000</td><td>400000 ZOO NES-PGD FW (Opt I) 500000 FW (Opt II) Attack Success Rate</td><td>0.0 0.2 0.4 0.6 0.8</td><td>Queries 0 25000 50000 75000 100000 125000 150000 175000 200000 NES-PGD FW (Opt I) FW (Opt II)</td></tr><tr><td/><td/><td/><td colspan="3">(a) L2 norm based attack</td><td/><td>(b) L∞ norm based attack</td></tr><tr><td colspan="3">Figure 2:</td><td/><td/><td/><td/><td/></tr></table>

Comparison of L 2 norm based black-box attacks on Inception V3 model with = 5. We report attack success rate, average time and average number of queries needed per image. Opt I and Opt II refer to the two options in Algorithm 2.

Table content: <table><tr><td>METHODS</td><td colspan="3">SUCCESS RATE (%) AVERAGE TIME (s) AVERAGE QUERIES</td></tr><tr><td>ZOO</td><td>74.8</td><td>5692.6</td><td>296867.0</td></tr><tr><td>NES-PGD</td><td>96.7</td><td>133.0</td><td>58921.8</td></tr><tr><td>FW-Black (Opt I)</td><td>100.0</td><td>102.9</td><td>45994.5</td></tr><tr><td>FW-Black (Opt II)</td><td>100.0</td><td>100.9</td><td>45156.0</td></tr></table>

Comparison of L ∞ norm based black-box attacks on Inception V3 model with = 0.05.We report attack success rate, average time and average number of queries needed per image. Opt I and Opt II refer to the two options in Algorithm 2.Figure2illustrates the attack success rate against the number of queries plot for different algorithms in both L 2 norm and L ∞ norm based black-box attacks on Inception V3 model. As we can see from the plot, our proposed Frank-Wolfe black-box attack algorithm (both options) achieves the highest attack success rate and best efficiency (least queries needed for achieving the same success rate), especially in the L 2 norm case.

Table content: <table><tr><td>METHODS</td><td colspan="3">SUCCESS RATE (%) AVERAGE TIME (s) AVERAGE QUERIES</td></tr><tr><td>NES-PGD</td><td>98.0</td><td>76.9</td><td>34062.2</td></tr><tr><td>FW-Black (Opt I)</td><td>100.0</td><td>50.4</td><td>22313.2</td></tr><tr><td>FW-Black (Opt II)</td><td>100.0</td><td>50.6</td><td>22424.1</td></tr></table>

Parameters used in Frank-Wolfe white-box attack. PARAMETER L 2 CASE L inf CASE

Table content: <table><tr><td>T</td><td>1000</td><td>1000</td></tr><tr><td>{γ t }</td><td>0.03</td><td>0.005</td></tr><tr><td>λ</td><td>20</td><td>5</td></tr></table>

Parameters used in Frank-Wolfe black-box attack. PARAMETER L 2 CASE L inf CASE

Table content: <table><tr><td>T {γ t }</td><td>10000 0.05/ √</td><td>t</td><td>10000 0.03/ √</td><td>t</td></tr><tr><td>λ</td><td>50</td><td/><td>30</td><td/></tr><tr><td>b</td><td>25</td><td/><td>25</td><td/></tr><tr><td>δ t</td><td>0.001</td><td/><td>0.01</td><td/></tr></table>

Comparison of L 2 norm based white-box attacks on ResNet V2 model with = 5. We report attack success rate, average time and average distortion.

Table content: <table><tr><td colspan="4">METHODS SUCCESS RATE (%) AVERAGE TIME (s) AVERAGE DISTORTION</td></tr><tr><td>PGD</td><td>99.8</td><td>168.2</td><td>0.88</td></tr><tr><td>CW</td><td>98.6</td><td>278.8</td><td>1.45</td></tr><tr><td>EAD</td><td>73.0</td><td>109.2</td><td>2.81</td></tr><tr><td>FW-White</td><td>100.0</td><td>47.1</td><td>0.93</td></tr></table>

Comparison of L ∞ norm based white-box attacks on ResNet V2 model with = 0.05. We report attack success rate, average time and average distortion.In this subsection, we present the white-box attack experiments on ResNet V2 model. Tables7 and 8present our experimental results for L 2 norm and L ∞ norm based white-box attacks respectively. For the other baselines in the L 2 norm case, surprisingly, CW method cannot achieve the best L 2 distortion as it does in Inception V3 model. EAD method is relatively faster than CW in terms of attack time yet it has the largest distortion and a quite low success rate of 73.0%. PGD has the smallest average distortion in this setting, yet it also costs a lot of attack time. On the other hand, our proposed algorithm achieves the highest attack success rate within very short attack time with very small distortion. It significantly reduces the time complexity needed for effective attacking data with large dimensionality. For the L ∞ norm case, CW method takes significantly longer time and does not perform very well on average distortion either. Our proposed white-box attack algorithm, on the other hand, again achieves the shortest average attack time and 100% success rate.

Table content: <table><tr><td colspan="4">METHODS SUCCESS RATE (%) AVERAGE TIME (s) AVERAGE DISTORTION</td></tr><tr><td>PGD</td><td>100.0</td><td>26.8</td><td>0.0031</td></tr><tr><td>CW</td><td>100.0</td><td>538.9</td><td>0.0251</td></tr><tr><td>FW-White</td><td>100.0</td><td>14.9</td><td>0.0031</td></tr><tr><td colspan="2">D ADDITIONAL EXPERIMENTS</td><td/><td/></tr><tr><td colspan="3">D.1 RESNET V2 WHITE-BOX ATTACK RESULTS</td><td/></tr><tr><td colspan="3">D.2 RESNET V2 BLACK-BOX ATTACK RESULTS</td><td/></tr></table>

Comparison of L 2 norm based black-box attacks on ResNet V2 model with = 5. Query limit is set to be 50, 000. We report attack success rate, average time and average number of queries needed per image. Opt I and Opt II refer to the two options in Algorithm 2.

Table content: <table><tr><td>METHODS</td><td colspan="3">SUCCESS RATE (%) AVERAGE TIME (s) AVERAGE QUERIES</td></tr><tr><td>ZOO</td><td>2.4</td><td>696.0</td><td>49495.2</td></tr><tr><td>NES-PGD</td><td>58.0</td><td>75.3</td><td>36748.1</td></tr><tr><td>FW-Black (Opt I)</td><td>57.4</td><td>75.0</td><td>34382.5</td></tr><tr><td>FW-Black (Opt II)</td><td>58.8</td><td>74.7</td><td>34362.8</td></tr></table>

Comparison of L ∞ norm based black-box attacks on Inception V3 model with = 0.05. Query limit is set to be 50, 000. We report attack success rate, average time and average number of queries needed per image. Opt I and Opt II refer to the two options in Algorithm 2.In this subsection, we present the black-box experiments on ResNet V2 model. We again mainly focus on evaluating attack success rate, time and number of queries needed. In previous experiments on Inception V3 model, we show the performance of different black-box attack algorithms given enough number of queries (i.e., 500,000 per attack per image). And it shows that basically all L∞ norm based attack Figure 3: Attack success rate against the number of queries plot for different algorithms in both L 2 norm and L ∞ norm based black-box attacks on ResNet V2 model.algorithms can achieve very high attack success rate (almost 100%). Now we examine a much harder case, where we reduce the the number of allowed queries per attack per image to only 50, 000.

Table content: <table><tr><td>METHODS</td><td colspan="3">SUCCESS RATE (%) AVERAGE TIME (s) AVERAGE QUERIES</td></tr><tr><td>NES-PGD</td><td>90.4</td><td>44.7</td><td>20914.0</td></tr><tr><td>FW-Black (Opt I)</td><td>90.8</td><td>44.1</td><td>19934.6</td></tr><tr><td>FW-Black (Opt II)</td><td>91.6</td><td>44.0</td><td>20004.6</td></tr></table>

Peer review (iclr2019):
 The paper investigates the Frank-Wolfe (FW) algorithm for constructing adversarial examples both in a white-box and black-box setting. The authors provide both a theoretical analysis (convergence to a stationary point) and experiments for an InceptionV3 network on ImageNet. The main claim is that the proposed algorithm can construct adversarial examples faster than various baselines (PGD, I-FGSM, CW, etc.), and from fewer queries in a black-box setting. The FW algorithm is a classical method in optimization, but (to the best of my knowledge) has not yet been evaluated yet for constructing adversarial examples. Hence it is a natural question to understand whether FW performs significantly better than current algorithms in this context. Indeed, the authors find that FW is 6x - 20x faster for constructing white-box adversarial examples than a range of relevant baseline, which is a significant speed-up. However, there are several points about the experiments that are unclear to me: - It is well known that the running times of optimization algorithms are highly dependent on various hyperparameters such as the step size. But the authors do not seem to describe how they chose the hyperparameters for the baselines algorithms. Hence it is unclear how large the running time improvement is compared to a well-tuned baseline. - Other algorithms in the comparison achieve a better distortion (smaller perturbation). Since finding an adversarial with smaller perturbation is a harder problem, it is unclear how the algorithms compare for finding adversarial examples with similar distortion. Instead of reporting a single time-vs-distortion data point, the authors could show the full trade-off curve. - The authors only provide running times, not the number of iterations. In principle all the algorithms should have a similar bottleneck in each iteration (computing a gradient for the input image), but it would be good to verify this with an iteration count vs success rate (or distortion) plot. This would also allow the authors to compare their theoretical iteration bound with experimental data. In addition to these three main points, the authors could strengthen their results by providing experiments on another dataset (e.g., CIFAR-10) or model architecture (e.g., a ResNet), and by averaging over a larger number of test data points (currently 200). Overall, I find the paper a promising contribution. But until the authors provide a more thorough experimental evaluation, I hesitate to recommend acceptance. Additional comments: The introduction contains a few statements that may paint an incomplete or confusing picture of the current literature in adversarial attacks on neural networks: * The abstract claims that the poor time complexity of adversarial attacks limits their practical usefulness. However, the running time of attacks is typically measured in seconds and should not be the limiting element in real-world attacks on deep learning systems. I am not aware of a setting where the running time of an attack is the main computational bottleneck (outside adversarial training). * The introduction distinguishes between "gradient-based methods" and "optimization-based methods". This distinction is potentially confusing to a reader since the gradient-based methods can be seen as optimization algorithms, and the optimization-based methods rely on gradients. * The introduction claims that black-box attacks need to estimate gradients coordinate-wise. However, this is not the case already in some of the prior work that uses random directions for estimating gradients (e.g., the cited paper by Ilyas et al.) I encourage the authors to clarify these points in an updated version of their paper.